Why is there no "ephemeral non-DH EC" key exchange in TLS?

"Maybe difficulties to use an EC keypair for encryption?"; yes exactly, as there are no direct EC encryption primitives that can be used. ElGamal EC encryption is possible, but it requires all kinds of tricks to get it working. There is the mapping of the message to an EC point, for instance. There is ECIES, but that really comes down to performing ECDHE in the first place, with the additional disadvantage of needing a cipher.

Besides that, for RSA, key pair generation is one of the slowest algorithms that you may see. Not only is it slow, but it is also very unpredictable as it is unknown when the two required primes are found. With EC, it is very easy:

create a random number between 1 and N (exclusive);
perform point multiplication of that number with the base point G to get to the public point.

So basically it is as fast as the DH operation itself. There is no long waiting time for primes to be generated at all. So because the key generation itself does not pose much of a problem, there is no pressing need to change either.

One important idea of TLS 1.3 was bringing down the number of round trips. It even guesses the algorithms present at the other end for the initial key agreement. It can then immediately send the ephemeral public key of the client to the server, which responds with the server's ephemeral public key to setup the channel. That way the encrypted channel can (and will) be setup after only two messages. With encryption the client (who has to initiate the connection) first asks for the public key, receives it and then encrypts with it.

That is, ECDH speeds things up if the client doesn't use session resumption, a separate trick to speed things up.

Another smaller difference is that the random key in ECDH is now dependent on the random data of two parties. The various clients may have different strengths of random number generator, and encryption of a secret has the disadvantage that the secret itself is not fully random, e.g. when a RNG is used that is not cryptographically secure. However, with ECDH is does mean that a completely failing RNG will completely show the established shared secret as the ephemeral private key may become known.

Note too that simply bringing the number of options down was an important initiative in TLS 1.3. Having options just for the sake of it only makes a protocol less secure, not more secure. IMHO it doesn't even make sense to have different security levels for the various algorithms used for a specific ciphersuite (not including the difference with the security level of the certificates used for authentication).


How was the special DES key 0E329232EA6D0D73 found?

That value 0E329232EA6D0D73 was found by brute force. I would be surprised if there was a significantly better method: that would be tantamount to a cryptanalytic break of DES, very different from the few we know.

A sketch of the brute force method (with details about parallelization omitted) goes:

for each $K$ of 64 bits among the $2^{56}$ valid DES keys

decrypt with key $K$ a ciphertext block consisting entirely of zeroes, giving $P$
if the eight bytes in $P$ are equal

output $K$ and stop

output nothing found and stop.

For a perfect cipher, $P$ would be essentially 8 random bytes for each $K$ tried, therefore the if condition would be met with odds $2^{-56}$ for each $K$. Under that approximation for DES (which is not invalidated by the complementation property, since the ciphertext is fixed), odds that nothing found is output are $(1-2^{-56})^{(2^{56})}\approx1/e\approx36.8\%$. Correspondingly, odds that a value of $K$ is found are $1-(1-2^{-56})^{(2^{56})}\approx1-1/e\approx63.2\%$.

It turns out that we are in the second (and most likely) case (proof: the assertion in the question holds). Knowing this, finding a solution $K$ by the method outlined requires at most $2^{56}$ decryptions. That's not much harder than finding a DES key by brute force from plaintext/ciphertext pairs, which was feasible in few days with a budget of \$250,000 (including NRE) in 1998, see the EFF DES Cracker. The only difficulty compared to that is the slightly unusual stop condition. But in a FPGA-based implementation like Copacobana, or a GPU-based one, that adds very little cost.

Update: the EFF DES Cracker was designed to have a flexible enough stop criteria, and was used to first publicly find that particular key, as a demonstration that it works. Quoting the EFF¹:

  The EFF DES Cracker first solved a challenge posed [circa 1996] by world-renowned cryptographer and AT&T Labs research scientist, Matt Blaze. The "Blaze Challenge" was designed to only be solvable by "brute force" cryptanalysis of DES. Mr. Blaze challenged the world to find matching pairs of plaintext and ciphertext numbers, consisting of nothing but repeated digits. Blaze himself was unaware of any such pairs until the EFF DES Cracker revealed the first known pair. It found that a hexadecimal key of 0E 32 92 32 EA 6D 0D 73 turns a plaintext of 8787878787878787 into the ciphertext 0000000000000000.

¹ This links to an archive of the original. Some of that material is still on the current EFF website, but sadly the date was lost in modernization, becoming August 2016 rather than July 1998.


Knowing that $G(s)$ is a PRG, is the following construction $G'(s) = G(s||0)$ a PRG?

Maybe.

  If $G(s)$ is a PRG, then why $G(s||0)$ can't also be a PRG?

$G'$ can "also be a PRG". (It's just not necessarily also a PRG.)

  How can the distribution over $G(s||0)$ be distinguished from a truly uniform distribution of the same output range?"

$G$ can be such that the last bit of its output is always equal to the last bit of its input.


Provable data possession (PDP) VS Merkle tree

I'd say that like with the naive variant of simply asking for the hash of the data, the server can just throw away the data and store the hashes and still answer queries. It is important for such schemes that a query requires the server to use sufficient randomness together with the data in the computation of the answers. Then precomputing the potential answers will require too much storage and it is then actually less costly to keep the data itself.


Can AES-CTR add values without decryption?

No, with AES in CTR mode, it is not

  possible to add/subtract(or XOR?) plaintext values on encrypted data

nor define operator $\boxplus$ such that $\operatorname{AES-CTR}(4)\boxplus\operatorname{AES-CTR}(6)=\operatorname{AES-CTR}(4+6)$ that works for unknown key and plaintexts. Informally: if that worked, it would be a weakness of the encryption scheme, which would be leaking information about plaintexts from the ciphertexts.

Notice that the above notation is misleading, as the result of AES-CTR depends on 3 parameters: Key, IV and plaintext, with IV normally random (making the argument above non-rigorous). But still, even if we assume fixed IV, what's asked can't be done: it is asking an operator $\boxplus$ such that $\forall s,\forall x,\forall y, (s\oplus x)\boxplus(s\oplus y)=s\oplus(x+y)$ where $\oplus$ is XOR, and $s$ is whatever the IV encrypts to under the key considered; which is impossible.

More generally, no secure mode of operation of any secure block cipher allow homomorphic encryption.


Existence of PRF $\implies$ existence of PRG

Your proof did not convince me at first.

  Given access to a function $\mathcal O$ which is either a random function $\{0,1\}^m\to \{0,1\}^l$ or $F_k$, then $D'$ outputs precisely the accept/reject choice of $D$ on the string $\mathcal O(x_0)$.

The word "then" threw me off. The output of $D'$ is not a consequence of the first clause. I'd reword this to explicitly state that we're constructing a $D'$ that uses $D$ in a particular way. This may seem silly, but this did make me do a double take.

  By construction $D'$ wins if and only if $D$ accepts. By assumptions, since $F$ is a PRF, the former event has probability bounded above by $\frac{1}{2} + \text{negl}(n)$ for some negligible $\text{negl}$, and hence the same is true for the latter event.

The first sentence isn't true. In the PRG game, sometimes $D$ will actually be given a random string instead of $G(s)$, and in those cases, $D$ should reject the input, not accept it, to win. Perhaps you mean $D'$ wins if and only if $D$ wins?

Furthermore, there isn't really a justification (even a sketch of one) given. The reader needs to work out the details of $\mathcal{O}(x_0)$ on his own to even understand the argument; that's its failing. A proof's correctness is only half the battle: it must also convince the reader of its correctness, which can be far harder.

Why is it the case that $D' = D(\mathcal{O}(x_0))$ is a distinguisher for $F$, and thus must have negligible advantage? That is the meat of the proof -- which you've omitted.

I think a proof by contradiction is easier to understand. Let's also try to be explicit in our reasoning.

We're given a PRF $F_k$ and we want to show $G(s) = F_s(x_0)$, where $x_0$ is a fixed constant in $\{0,1\}^m$, is a PRG.

Assume (toward a contradiction) that $G$ is not a PRG, so there exists an efficient distinguisher $D$ with non-negligible advantage in the PRG indistinguishability game for $G$.

We will build an efficient distinguisher $D'$ in the PRF experiment using $D$. In that experiment, $D'$ will be given either:

a uniform function $\mathcal{O} \in \mathsf{Func}_m$, or
the function $\mathcal{O}(x) = F_k(x)$ where $k$ is a uniform string in $\{0,1\}^n$

Conveniently, if we evaluate $\mathcal{O}(x_0)$, we get either

a uniform value in $\{0,1\}^m$, by definition of $\mathcal{O} \in \mathsf{Func}_m$, or
the value $F_k(x_0) = G(k)$

Notice that the possible values of $\mathcal{O}(x_0)$ exactly match the parameters of the PRG indistinguishability game for $G$. As a result, $D$ can distinguish between the two above situations with non-negligible advantage, since we assumed $G$ is not a PRG.

Therefore, if we let the output of $D'$ be the output of $D$, then $D'$ has non-negligible advantage in the PRF game for $F_k$. This violates our assumption that $F_k$ is a PRF. Therefore, our original assumption that $G$ is not a PRG must be false, i.e., $G$ must be a PRG.

The above proof may not be as rigorous as some would like, but I think it's acceptable enough as a brief sketch (and could be filled-in with real mathematical details if necessary).

Notice that I did not really say anything different than your post -- I was just more explicit. I did switch to a proof by contradiction, but that's because when I went to state the conclusion, it ended up sounding like a proof by contradiction anyway.


Is a number generator based on hashing an incremental string considered random?

No, the next number in the sequence of the generator in the question cannot be safely considered unpredictable. At least one reason for that: we can infer from the example seed value "something" that the seed is not entropic enough. An adversary knowing the method, the hash, and the first 3 outputs or so could very plausibly enumerate likely seeds from a dictionary of common English words, find one that matches known output, and use that to predict further outputs with fair confidence. Even with less output, the adversary can get a slight advantage compared to a random guess.

The scheme proposed would be computationally indistinguishable from true random under some reasonable but unstated hypothesis:

The counter never cycles or otherwise resets, which is not trivial to ascertain in practice (e.g. when adversaries can cut power at any time).
The computations are performed secretly and correctly; no untold leak of seed or intermediary results, or fault, occurs. This is hard to ascertain in practice (for a start, who knows there's no trojan in that computer? Also, side-channel/fault attacks are a real thing).
The seed is secret, large and random-enough that it can not in practice be found by enumeration using the computational power available to an adversary. It is acknowledged that 128-bit entropy is safe with current technology, and twice that more than safe enough even assuming hypothetical quantum computers usable for cryptanalysis. 128-bit entropy can be obtained with $\lceil128/\log_2(26)\rceil=28$ lowercase letters chosen independently and uniformly at random.
The hash is computationally indistinguishable from a Pseudo Random Function. As far as we know SHA-256 would be good enough in practice, especially with truncation of the output as we have here. SHA-512 would be even safer. Further, the HMAC construction could be used (instead of hashing the hash of a concatenation) to combine seed (used as key) and counter (used as the data input) in a manner giving more assurance against hypothetical attacks on the hash.
Note; standard properties of hash funcions are lesser than being a PRF, and do not even include having near equidistributed output for random input.
Leading zeroes in the hash are kept (which is not entirely clear in the question's statement), so that integers less than 256 are not underrepresented.


Is it possible to build short proofs of arbitrary computations over a big list?

Merkle aggregation can help you compute aggregation functions over the leaf data in a Merkle tree.

The technique is described in detail in Crosby & Wallach's paper on history trees [1], an append-only Merkle tree. Merkle aggregation can be used to provably compute things like $\max(\cdot,\cdot)$ functions over all leafs.

The idea is quite straightforward.
Each node can have an attribute and there's an aggregator function $\alpha(l, r)$ which takes the attributes from the two children and returns the parent's attribute. For example, the aggregator function can be $\max(\cdot,\cdot)$.

By recursively applying $\alpha(\cdot,\cdot)$ starting with the leafs, attributes can be computed or aggregated for all nodes in the tree, all the way up to the root. Furthermore, the computed attributes are hashed in the Merkle tree. Specifically, a node's hash is no longer just $H(h_l, h_r)$ but $H(h_l, a, h_r)$, where $h_l,h_r$ denote the left and right child hashes and $a$ denotes the aggregated attribute computed via $\alpha(l,r)$.

Including the attributes in the Merkle hashing enables a prover to convince a verifier that the aggregation was performed correctly. Of course, the Merkle proof is a bit different now. Specifically, a Merkle path from a leaf to the root consists not just of the hashes along the sibling path, but also of the attributes along the path and the sibling path, so as to verify the aggregation.

Hope this helps!

References

[1] "Efficient Data Structures for Tamper-Evident Logging", by Scott A. Crosby, and Dan S. Wallach


Whatsapp E2EE - Why scanning the QR-code?

Are there any advantages in scanning a QR-code?

Yes.
But to understand why this provides an advantage we first need to introduce the man-in-the-middle attack (MitM attack). In this attack setup, the adversary sits between you and your communication partner and you are doing your cryptographic computations (the key exchange) with the adversary who then initiates a key exchange with your intended partner and then forwards (some) of your messages to make sure you don't notice the attack. It needs to be noted that you indeed are having a session with the attacker and not with your intended recipient in this case which in particular means two things:

You will see the adversary's public key and not your intended target's and
You will share the agreed key with the adversary and not with your intended target.

On the web, i.e. when you browse websites this is mitigated by so-called certificates which effectively state in a trust-worthy manner "this public key belongs to this entity". Then an adversary can't go ahead and send his public key as the entity's key because he can't come up with the statement / certificate.

However in this scenario, i.e. instant messaging you can't have one central source which says "this key belongs to X" if you don't trust the service provider which end-to-end encryption (E2EE) is all about. So we need another way to ensure that we are actually directly communicating with our intended target. This is where the additional QR-code / number come in. They are essentially a processed version of your public key and the other party's public key. Now if you transmit this information to your intended target in an authentic manner and the information matches you know that you are using their public key and thus that there is no active attack going on.


Negative exponents in Shoup's threshold RSA?

There is nothing wrong with any negative exponent $\lambda$, just modular division for $(-\lambda)$, modulo $n$. That is, one would calculate modular exponentiation for positive $(-\lambda)$ first and modular inverse (division) next.


Why isn't there a final permutation on SPN-based ciphers?

Because a fixed and published permutation is known, linear and ever so reversible. It's very much like a bait & switch move, but without the switch(substitution). Security is built piecemeal from units of permutation & substitution(rounds). We can undo a singular publically published permutation, and it doesn't take any notice of a key(as it's fixed), thus it adds nothing security wise. Nobody really gets confused and the diffusion effects can easily be reversed.

As a kiddie, slightly similar example, think about ROT13 so called encryption.


Key generation for AES-GCM-256 file encryption

In general, your concept looks OK to me. I do have a few remarks, though:

Hashing the password before feeding it to scrypt is useless
scrypt can process binary data, so there is no need for the base91 encoding step. Avoid steps that do not have a good reason
Using the slow password hashing function scrypt fo every file will result in a bad performance if you want to encrypt or decrypt a lot of files. Rather create a single masterkey from the password with scrypt and then create the file depending keys using a fast KDF like HKDF.
The biggest problem I can see: You are using a unique key for each file, but that is created by a random salt and not some file information. An attacker would be able to switch the content of two files (without altering it or learning the content) without you noticing it. To prohibit this, you should use some file metadata (preferable a unique file identifier like a file name/path) in the process. Either inject it into the key derivation process (using it as the salt) or authenticate it as additional data with AES-GCM.


Can we possible to solve the LPN problem using Arora-Ge algorithm?

It is natural to wonder if Arora-Ge can break LPN, but as you suspect, it does not work. The essential problem is that, because the modulus is $q=2$, the method does not find the unique solution $s$, nor does it even narrow down the set of possible solutions.
The reason is that the first step of the algorithm converts each LPN sample into a quadratic (in $s$) equation that encodes the condition $\langle a_i, s \rangle = b_i \text{ or } b_i +1 \pmod{2}$. It then linearizes these equations and solves for $s$. However, observe that any $s’$ is a solution to these equations, because the right-hand side is always “0 or 1.” So, the system set up by the algorithm does not carry any information about $s$, from the very start.
Arora-Ge works for LWE because/when the modulus $q$ is larger than the number of possible error values. Then, the condition “$\langle a_i, s \rangle = b_i \text{ or } b_i+1 \text{ or } b_i-1 \ldots$” captures a nontrivial constraint on the secret $s$, and enough such equations can uniquely specify it.


Extending the Socialist millionaire problem to three parties

A tripartite version of EKE would appear to work.  Here's how it works:

We select a pairing friendly elliptic curve, with a point $G$ that generates a prime order subgroup.
We define an invertible keyed hash function $F_k(H)$ that maps (based on the key) a point in the subgroup to a point in the subgroup (and so that, for two different keys $k_1, k_2$, we don't know the discrete log of $F_{k_1}(H)$ to the base of $F_{k_2}(H)$

So, what Alice does is take her networth $n_A$, and selects a random value $a$; she computes $A = F_{n_A}(aG)$ and publishes it.

Similarly, Bob and Carol also publish their $B = F_{n_B}(bG)$ and $C = F_{n_C}(cG)$.

Alice computes $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a$ and publishes that.  Bob and Carol do the same computations and publish their values.

If $n_A = n_B = n_C$, this joint computation is $e( F_{n_A}^{-1}(B), F_{n_A}^{-1}(C) )^a = e(bG, cG)^a = e(G,G)^{abc}$, and hence they will publish the exact same value.

If those three values are not the same, for example, if $n_A \ne n_B$, then $F_{n_A}^{-1}(B) = F_{n_A}^{-1}(F_{n_B}(bG))$ is effectively a random point, and so Alice will generate a value that is distinct from what anyone else generates.

On review, this idea doesn't quite work, if we have $n_A \ne n_B$ and $n_B = n_C$, then B and C will compute the same value.  I believe that, from the problem statement, we want to jointly compute the value $n_A = n_B \land n_B = n_C$; we end up leaking more than that...

I'll leave this answer open in case someone can fix it...


How secure are public hashed passwords (with a salt)?

The main problem will be the password policy and users. If you let the users to choose any password, then they will tend to use 1234 as a password. A malicious user in your system can easily bruteforce all widely used insecure passwords. If you have a good policy, the only way is brute-forcing since we cannot reverse the hash and the salt prevents rainbow tables. For a general guideline for passwords, see NIST Digital Identity Guidelines 800-63B.

While considering the attack risks, we already assume that an attacker access the database of the users and we design our password systems as a last defense against the attacker. According to this, we design our system not by security by obscurity. So, you already in this stage.

Actually, we don't use a simple hash technique to store passwords. For example, iteration as in PBKDF2 can decrease the time of the attacker like 10000 times. Also, you need to protect against massive parallelization as in GPU usage of hashcat.

You should use PBKDF2, Bcrypt, or better argon2  which is the winner of the password hashing competition.

Also, for general advice see the How to securely hash passwords? from Information Security.


How to prove security of a randomized encryption algorithm?

What you want to do is the right way. However it's not an easy one.

What you really want to do is to show the following implication:
$$
\newcommand{\hard}{\operatorname{hard}}
\newcommand{\assumption}{\text{assumption}}
\newcommand{\secure}{\operatorname{secure}}
\hard(\assumption_1)\land\ldots\land\hard(\assumption_n)
=\bigwedge_{i=1}^n\hard(\text{assumption}_i)\\
\implies\secure(\text{cryptosystem})$$

for a (hopefully) small number of assumptions which are already well-studied.

The usual intuition for such proofs is a proof-by-reduction, which is a logical contraposition:
$$\neg\secure(\text{cryptosystem})\implies\bigvee_{i=1}^n\neg\hard(\assumption_i)$$
Meaning that you would need to show that breaking the security of your cryptosystem implies that any of your assumptions is not hard.

Of course you first need to find out what "$\hard(\assumption_i)$" and "$\secure(\text{cryptosystem})$" actually mean. The latter is a (preferably) strong security definition, most likely from this list. The former very much depends on the actual assumption at hand and you need to look at the actual, precise definition of said assumption. For example this blog post covers RSA and this one covers the typical DH assumptions.

Now the final and actually hardest part: How to actually make the proof. There's no simple answer to this question. For example you could give game-hopping a look as well as simulation based proofs. You could also look whether proof / verification tools can help you along the way, such as described by Biv here and here. There isn't much more to say on this, except for: Look at the references given, work your way from there through the references they give, continue going through the references until you have an understanding of these proofs and are able to carry out the one you need. It will probably be a hard and / or long journey, but it will pay off.


Is there a practical way to crack an AES encryption password?

Yes, in the question's situation, a password-recovery attacks is entirely reasonable.

The question considers a (partially) known plaintext attack, where e.g. some header of the encrypted file(s) is known, for a file encrypted with AES, where the key has been determined from a user-supplied password. In this scenario, it is not important to consider the expected number of AES operations for brute-force search of the AES key ($2^{127}$ for AES-128, $2^{255}$ for AES-256) because that's not the best (nor a credible) attack strategy.

The reasonable attack strategy is password cracking: try passwords, approximately from most to least likely to have been chosen, and for each attempt decryption up to the point where known plaintext is reached, and move on to the next password if this test fail. Attack cost will depend on:

How the password was chosen. Users vary widely on that, and 123456 will be easier to find than MdSm2aZ!t&5u*Z5. That varies widely with the context, and motivation of users. See the obligatory XKCD.
How the password is transformed into an AES key. A password-based key derivation function should be used here, parametrized so that it adds a sizable cost.

The cost for an attack grows roughly as $2^E$ times the cost of the PBKDF (assuming that dominates the cost of testing a password), where $E$ is the password entropy in bits. For example, if the password is 6 random decimal digits ($E=\log_2(10^6)\approx19.9\,\text{bit}$), and the PBKDF + plaintext testing uses 0.1 second of CPU time (300000 CPU cycles @3GHz), a competent attacker will use an average of $10^6\times10^{-1}/2=50000\,\text{s}<14\,\text{h}$ of CPU time to find a password, that is less than 2 hours of wall clock time with a single 8-core PC, minutes for a powerful adversary.


There are no percentages, fractions, real or floating point numbers involved.

When using modular arithmetic, the "division" operation is defined differently. If you have some values $a, b$ that have been multiplied together into $ab$, what you want from division is that $\frac{ab}{b} = a$, or stated alternatively that $\frac{a}{a} = 1$.

When working with modular arithmetic, you need a different division operation than the "normal" one taught in basic math classes. This is easy to see with an example. Suppose that you have $$a=5\\b=7\\N=19\\ab \equiv 16 \bmod N$$ It is easy to see that dividing (in the traditional sense) $16$ by $7$ is not going to yield $5$.

Instead, you can multiply $16$ by $11$, which happens to be equivalent to $5$ modulo $19$. This fulfills the behavior expected of the division operation, which is what we really care about.

A value $\frac{1}{b}$ such that $\frac{ab}{b} \equiv a \bmod N$ is called a modular multiplicative inverse.

Back to the specific question

In the case of RSA, $e$ and $d$ are modular multiplicative inverses: $ed \equiv 1 \bmod \lambda(N)$.

Alternatively, you can denote $d$ by $\frac{1}{e}$ or $e^{-1}$; These are different ways of writing the same value.

A multiplicative inverse exists if the element is coprime to the modulus $N$. To actually find a modular multiplicative inverse of an element, you can use the extended euclidean algorithm.


If you iterate a cryptographic permutation long enough will you map the input to itself?

Any permutation $f$ (cryptographic or not) on a finite set $X$ satisfies $f^n=id$ for some $n>0$.

To see this, note that there's only finitely many functions from $X$ to itself. Hence $f,f^2,f^3,\dots$ aren't all distinct, so $f^k=f^l$ for some $k$ and $l$ with $l<k$. Now $$id=f^{-l}f^l=f^{-l}f^k=f^{k-l}$$ so we can set $n=k-l$.


How to choose between AES-CCM and AES-GCM for storage volume encryption

TL;DR if you're reading this in 2020, applications should be using GCM mode.

CCM (Counter with CBC-MAC)

Message authentication (via CBC-MAC) is done on the plaintext not the ciphertext.  (This is generally not a desireable feature.)

On the encrypt operation, the encryption and MAC could happen in parallel, but generally do not (typically because there is just one AES engine in a chip, just one AES thread at a time, etc.).  Similar statement is true for decrypt.

Performance costs essentially 2 x AES operations per block
Cannot be parallelized
CCM ciphers are available in OpenSSL as of TLS 1.3 (2018), but disabled by default.

GCM (Galois Counter Mode)

GCM ciphers are the most widely used block ciphers worldwide. Mandatory as of TLS 1.2 (2008) and used by default by most clients.
Message authentication (via GMAC/GHASH) is done on the ciphertext.  (This is desirable most of the time.)  Note that in most implementations, the auth check and decryption happen in parallel for performance reasons.
Performance costs 1 x AES operation and 1 x GHASH per block (GHASH generally faster than AES, so GCM is faster)
Encrypt/decrypt of multiple blocks can be parallelized nicely

GCM should be considered superior to CCM for most applications that require authenticated encryption.  Because of the authentication that happens, GCM is not susceptible to the bit flipping and other attacks that can be mounted against counter mode or other stream modes.

There are some nuances that should be noted before using GCM that involve maximum size of the encrypted message and the MAC size.  These are called out in the standard (NIST SP800-38D).


How to calculate the needed encryptions in salted passwords?

In your case, you say the salt only has 16 bits of entropy, which is pretty weak.

To see whether 'one particular password' was used, the attacker would have to attempt 65,536 possible Salt combinations, for each 'particular password' that must be tested. The number of users does not  matter because we have now established a need to brute-force the (weak) salt, and only try a single particular password.

On the other hand, with a properly implemented modern Password Hash, where sufficiently strong (e.g. 72 bits of entropy) salt is used, if the attacker fails to acquire the salt, then there would be no practical way for him to brute-force the hash.


So why can't AES keys be generated from shared keys, and why not use only AES for message encryption after this point?

That is exactly what is done.

  if there is a shared key from a DH key exchange, why are we still talking about ElGamal asymmetric message encryption

Remember, DH is just one way to exchange a key. DH has its problems (no authentication). Using ElGamal is another way someone could exchange a key. It would typically be used as follows: Use AES to encrypt a large message with a random key for Bob. Encrypt that random key using Bob's ElGamal (or RSA if you prefer) public key. Send both to Bob. Bob decrypts the random key using his private key, then uses AES to decrypt the message. You are correct in that ElGamal (or any public-key cipher for that matter) is rarely used to send encrypted messages.

  Isn't learning Elgamal unnecessary and confusing?

If you are only learning DH and nothing else, then definitely not. DH does not provide digital signatures, does not provide authentication, does not provide encryption. It only exchanges a key (and is succeptible to a man-in-the-middle attack). Learning about ElGamal can provide the opportunity to discuss all these other things that you do not get with DH alone. That said, when I took a network security class we didn't discuss ElGamal at all. We instead learned about RSA as a way of doing digital signatures, signing a DH key exchange, exchanging a key, etc.

So, a question you didn't ask, but might be thinking now:

  If we learned about DH and RSA, isn't ElGamal unnecessary?

The answer is no. ElGamal has some other interesting properties and uses that a professor might still want you to learn about. ElGamal is semantically secure out of the box (RSA is only semantically secure if you have random padding). ElGamal has homomorphic properties that make it useful in applications like e-voting. You can create an elliptic curve variant of ElGamal. ElGamal also leads to a fairly simple threshold cryptosystem.

That said, I can see why some professors would skip ElGamal in an undergraduate crypto or network security course.


Breaking ZIP 2.0 encryption without password

I will start with all relevant references I found, then tentatively answers the question. Feel free to improve this community wiki.

It was originally asked the effort to break PKZIP 2 encryption, described in section 6.1 of the .ZIP File Format Specification (with some refinements in the derived Info-ZIP appnote), assuming a high-entropy password (that is, next to 96-bit entropy for the internal key after password preprocessing), and a single file in a zip archive.

A most relevant attack on this cipher was made by Eli Biham and Paul C. Kocher: A known plaintext attack on the PKZIP stream cipher (1994, in proceedings of the 2nd FSE workshop).

That was improved by Michael Stay: ZIP Attacks with Reduced Known Plaintext (in proceedings of FSE 2001).

Peter Conrad's PkCrack is an implementation of the above with source and additional comments. It is the basis of the PKZIP section in Mark Stamp and Richard M. Low's Applied Cryptanalysis: Breaking Ciphers in the Real World (2007, Wiley-IEEE Press), nicely summarized in these slides.

In a single-file setup, these attacks depend heavily on the availability of some of the plaintext (formed by a 12-byte header, and the compressed form of the original file). At least about 13 known plaintext bytes are required (for a complexity of $2^{39}$ operations), more plaintext makes the attack easier. In the aforementioned 12-byte header, at least 1 byte is always known (part of the CRC in the archive's directory), or 2 bytes in archives made to be decipherable by PKZIP prior to version 2. Depending on the encryption/archiving program, some of the 11 or 10 other header bytes maybe low-entropy, for they are generated by a non-cryptographic RNG (sometimes rand() with 31-bit state as described in Michael Stay's article, or a variant where the additive constant is omitted according to this source; for a generator once in PKZIP 1.xx, refer to the Paul Kocher's ZIPCRACK documentation).

Further improvements are claimed by Kyung Chul Jeong, Dong Hoon Lee and Daewan Han's: An Improved Known Plaintext Attack on PKZIP Encryption Algorithm (in proceedings of ICISC 2011, paywalled); from the abstract, there seem to be improvements including in the single-file setup.

The following is thus very relevant (and unstated in the original question):

the exact program that generated the archive (that may be ambiguous from the archive);
the compression format/parameters (mostly known from the archive's directory);
the type/extension of the file (typically known from the archive);
whatever else is known about the plaintext and context of the creation of the zip file.

I have so far failed to locate information about details relevant to cryptanalysis:

the RNG (and its seeding) as in various versions of PKZIP 2;
the nature of the changes documented in late PKZIP 2 (see whatsnew.204) as:

  The security of (encryption) has been significantly improved in PKZIP/PKUNZIP 2.04c

how many files enciphered under the same password, each giving 1 plaintext byte, allow carrying an efficient attack (but that's irrelevant to the question).

It was added:

  The archive was created with PKZIP 2.04C and there is nothing known about the filename extension and nothing known about the plaintext.

Notice that in this sentence plaintext likely refers to the original file data, when everywhere else in this answer (following the terminology in the quoted literature) plaintext refers to the 12-byte header and the compressed form of the original file data.

It would be unusual that the filename and extension are not in the archive: by default, PKZIP 2 includes it in clear starting at offset 30, and before the PK marker at offset -22 from end-of-file. At least, the compression method used to produce the plaintext from the original file data, and one byte of the 12-byte header (taken from CRC), are bound to be in any undamaged archive (and readily shown by opening it with a modern zip tool such as 7-zip). The file name and extension, and ensuing reminiscence of the legitimate file owner, usually give some information on the original file. Let's, however, consider that a random file was given as input.

As stated, I found no analysis of the RNG used to prepare the 11 bytes of the header in PKZIP 2.04c and later; I'm incompetent about x86 code reverse-engineering; and anyway, from the whatsnew.204 citation above, likely this RNG is not nearly as bad as it was assumed to be in early ZIPCRACK, so I can best describe these bytes as random. I am not aware that the compression methods in PKZIP leave an easily modeled redundancy in their output. The only method that I can imagine to recover the (internal) key is to subject some of $2^{88}$ candidates to an impractically expensive test: that the plaintext could not have been generated by the compression method used (assuming the file is compressed rather than stored, I guess that a test of the CRC of the deciphered and uncompressed file can not help by a huge factor: if the original file data is short enough that this test is relatively inexpensive, too many candidate keys will remain that pass whatever automatic test we apply). Baring hypothesis change or progress in some of the above, it is inconceivable that the original file data can be recovered from the archive using anything remotely comparable to the computing effort that a GPU cluster can make in its operational life: if we had a thousand units of some kind each weeding a hundred thousand keys per microsecond for a century, odds are one in a thousand that the right key would be found.

Addition following partial quotation: I want to stress that the above bold statement makes multiple hypothesis:

a single file is encrypted; this is often not the case with real ZIP archives; multiple files enciphered with the same key, including in the same zip archive, do ease breaking PKZIP crypto;
nothing exploitable is known about the file's content; like, it is fully random, including its start; this is seldom the case for real files, to the point of making my statement theoretical in nature;
PKZIP 2.04g was used (which has become increasingly uncommon);
the PKZIP 2.04g TRNG has no major weakness (which I have not verified, and may depend on context; like, running in a VM);
the key has 96-bit entropy (most passwords used in practice have much less entropy);
the compression method used does not introduce exploitable redundancy (I only stated that I am not aware that this occurs).


Generating bilinear pairing parameters - running time of finding member of p-torsion group

In your step 2 replace $p$ by $p^2$. That should do it.

But you should really be looking for points Q on the sextic twist. See the original Barreto-Naehrig paper.


An elliptic curve whose polynomial has repeated roots is not in fact an elliptic curve, but a singular cubic curve, as it has a singular point where the group law breaks down. Still, we can remove those broken points and treat the remaining ones as a group. There are 3 possible cases:

$y^2 = x^3 \bmod p$. This curve has a triple root, and is isomorphic to the additive group of integers modulo $p$. Therefore the order here is $p$.
$y^2 = x^2(x + a) \bmod p$, square $a$. This curve has a double root, and is isomorphic to the multiplicative group of integers modulo $p$. Therefore the order here is $p-1$.
$y^2 = x^2(x + a) \bmod p$, nonsquare $a$. This curve has a double root, and is isomorphic to the group of integers in $\mathbb{F}_{p^2}$ of norm $1$. Therefore the order here is $p + 1$.

The full treatment of all these cases is given in several places, e.g. Husemöller or Washington or Silverman.

The simplest case is the first one, where you have $y^2 = x^3$. Here's the outline: show that you can represent a point unambiguously as $t = x/y$ ($t = 0$ for the point at infinity), since $x = 1/t^2$ and $y = 1/t^3$. Since there are as many $t$ as there are field elements, the group size is the same, $p$.

The other two cases follow the similar approach of bijectively encoding a point as a single $\mathbb{F}_p^*$ (or $\mathbb{F}_{p^2}^*$) element.


Main purpose for Carmichael's Function in RSA

You're have everything basically right.  Modern RSA-based cryptosystems, as in PKCS#1, do indeed use the Carmichael function.  Usually we pick $e = 3$ or $e = 2^{16} + 1$, try a different modulus if $e$ divides $\lambda(n)$, and otherwise use $d \equiv e^{-1} \pmod{\lambda(n)}$.

I'm not sure how you conclude that the extended Euclidean algorithm is not utilized—usually that is how we compute $d$.  The EEA, given $e$ and $\lambda(n)$, computes coefficients $c$ and $d$ satisfying Bézout's identity $c\lambda(n) + d e = \gcd(e, \lambda(n)) = 1$, meaning that $d e \equiv 1 \pmod{\lambda(n)}$, or $d \equiv e^{-1} \pmod{\lambda(n)}$.  Of course, we require $\gcd(e, \lambda(n)) = 1$ or else $e$ doesn't have an inverse modulo $\lambda(n)$ or $\phi(n)$ at all.

You can use $e > \lambda(n)$ or $d > \lambda(n)$, but it's no different from using $e \bmod \lambda(n)$ and $d \bmod \lambda(n)$, so there's no sense in wasting space for a larger number except in exotic applications.  You can also pick $e$ at random, but it offers no security and only hurts performance: roughly, the Hamming weight of $e$ determines the number of multiplications modulo $n$ to compute the public key operation, and $\lfloor\log_2 e\rfloor$ determines the number of squarings modulo $n$ needed to compute it.  (Certain exponents may also admit more efficient Lucas chains than the naive square-and-multiply algorithm.)

You want to minimize these because they make up the bulk of the public key operations.  Using the fastest option $e = 3$ is perfectly fine for sane RSA-based cryptosystems like RSA-KEM and RSA-FDH signature, and even the standard and fairly widely used RSAES-OAEP and RSASSA-PSS, but people are terrified of $e = 3$ because there are some ways to use RSA stupidly that enable, e.g., decryption or forgery by computing real number cube roots, so $e = 2^{16} + 1$ is a more popular choice.  $e = 2$ brings you into the territory of Rabin cryptosystems, which are qualitatively a little different, but have a neat reduction to factorization.

(If you pick $d$ small to speed up the private key operation instead of picking $e$ small to speed up the public key operation, you expose yourself to Wiener's attack.)


Are there any disadvantages of using libsodiums helpers for en-/decoding/comparision instead of the native ones?

Functions often become timing resistant by not using short circuit evaluation. There is conceivably a small performance price to be paid by not using short circuit evaluation.

In reality, this is probably not a bottleneck or serious concern. Edit: It also might be possible that libsodiums function is faster anyways.

I would have commented with this, but I don't have enough rep to comment. There may be more to consider.


Why are vectors approximately orthogonal after Gaussian lattice reduction?

When the algorithm ends, $m = 0$, which means that

$$\left| \frac{v_1v_2}{||v_1||^2} \right| \le \frac{1}{2}$$

otherwise, the nearest integer would not be zero (and $m$ would be different from zero).

Now, you just use the well-known cosine similarity: since both vectors are non-zero (because they belong to a basis of the lattice), we have that  $v_1 v_2 = || v_1 || || v_2 || \cos \theta$.

Combining those two expressions, we get

$$\left| \frac{v_1v_2}{||v_1||^2} \right| = \left| \frac{|| v_1 || || v_2 || \cos \theta}{||v_1||^2} \right| = \left| \frac{|| v_2 || \cos \theta}{||v_1||} \right| =  \frac{|| v_2 || \left| \cos \theta \right|}{||v_1||}  \le  \frac{1}{2} $$

which gives us $\left| \cos \theta \right| \le \frac{||v_1||}{2||v_2||}$, the expected inequality.

-- EDIT

As galvatron commented, the inequality involving the angle $\theta$ is obtained simply by using the fact that $||v_1|| \le ||v_2||$, which together with the first inequality, gives you $| \cos \theta | \le \frac{||v_2||}{2||v_2||} = \frac{1}{2}$. Therefore, $- \frac{1}{2} \le \cos \theta \le \frac{1}{2}$.

But $\cos \theta$ equals $\frac{1}{2}$ when $\theta = \frac{\pi}{2}$ and equals $-\frac{1}{2}$ when $\theta = \frac{2\pi}{3}$.


Are there AES-128 keys such that first round key equals last round key?

Not an answer but larger than a comment.
You can ask automated solvers to provide you with keys where the first and last rounds keys match.  Existing solvers likely won't terminate quickly on AES-128 for reasons mentioned in the question and comments.
AES-256, on the other hand, does yield results. For example the keys:

0x623cacba4d7fc6b7914b6bd000a2bcccf0967f268cbafde97ffc5bae4be5d2,
0xfea74943353b4d96d69457a2e6fbe56b1029ca48dc179d1967200df51cee7 and
0xf4e810b7b1c9253e75683304ac4f03f90be6534757600685706d8f6a97bee

all retain the property that expandedKey[0] == expandedKey[nrRounds].


How do you get the original salt after it's been hashed to the user's password in the database?

Did you read what you found? Quote: Save both the salt and the hash in the user's database record. and Retrieve the user's salt and hash from the database.

So, you simply store the original salt you used to the database, from where you can later read it. There is no need to "unhash" anything as you have the original salt available at all times… stored next to the salted hash in your database.

More practical:

Let's say for some user you use salt 123 and hash the user password with that salt. You then store both 123 and the hash result to your database:

ID   | salt | hashResult
-----+------+-------------
1    | 123  | F7A4…

When you later want to compare some password, you read the stored salt 123 and hash the password you want to compare using that salt you have previously stored in your database.

In simpler words, this roughly boils down to:

Does "User input hashed with stored salt 123" produce the same result as "the stored hash value"? If the answer is "yes" because the resulting hash matches the hash value you previously stored, the passwords match… if the answer is "no" because both hash results are different, the passwords don't match.

I guess what you've missed is that you always have the salt available — stored next to the related password hash. If you wouldn't do that, you would indeed not be able to recover the salt later on.

Also note that storing the salt in your database next to the hash result isn't a problem because a salt is not a "secret", while the password is a "secret".

For more information on what a salt is and what it does, check "Can you help me understand what a cryptographic “salt” is?"


It depends upon what trust you have in the cloud.  If you don't trust the cloud provider, a malicious model (treating the cloud as malicious) might make sense.

The so-called "semi-honest" threat model almost never makes sense in practice.  It amounts to assuming that someone is malicious ... but not malicious enough that they'll deliberately, actively try to subvert your security.  That's a very weird kind of assumption to make.  The "semi-honest" threat model is basically a theoretical construct that has no good practical motivation in its own right.  There may be a few special places where the "semi-honest" threat model might make sense in practice.  However, my view is that the "semi-honest" threat model is inappropriate for most practical systems engineering purposes.

Please understand: if you're using (say) Amazon EC2 for your cloud provider services, usually the threat to worry about isn't that Amazon is deliberately out to get you.  Rather, the more realistic threat is that Amazon gets penetrated by some malicious third party and the attacker is then out to get you.  Or, that an Amazon insider (e.g., one of Amazon's sysadmins) tries to get you.  Or, that Amazon has an inadvertent security breach that exposes your data.  For conciseness, we often summarize those by saying "Amazon is untrusted" or "the cloud is untrusted", but that doesn't mean that our primary concern is about Amazon the company itself.

Conversely, just because I'm pretty sure that Amazon the company isn't out to get me doesn't mean that it's safe to treat the cloud as trusted.  I still have to worry about whether there might be an inadvertent vulnerability or breach in Amazon's systems that lets the attacker take control of Amazon EC2 and thereby attack me.  If I'm worried about that sort of thing, I need a protocol that essentially treats the cloud provider as untrusted.


What is the best practices for storing ed25519 private keys which is used by nodes of my application to communicate with each other?

If you are storing the file on disk then PKCS#12 Personal Information Exchange Syntax format is best practice. It is commonly referred to as a key store. But note that PKCS#12 relies on secret key encryption to encrypt the key store entries. That generally means that entries in such a store are encrypted with password based encryption. Which of course means that the library that performs the encryption has to be passed a password.

The entries themselves are generally wrapped using PKCS#8: Private-Key Information Syntax Specification which can also be used on it's own. PKCS#8 is a format to store a single encrypted key. It consists of an outer layer which defines the methods of encryption and an inner format that is used to describe what kind of key is encrypted. Sometimes the inner format itself is used to describe keys stored in plaintext (or wrapped by some other means).

Finally there are formats to describe the key themselves. These are again used within the PKCS#8 entries (much like Matryoshka dolls). Generally these use the X9.63 format for EC keys to describe the keys using ASN.1 (which is also the method of encoding PKCS#12 and PKCS#8). The ed25519 curve is however rather new so it seems to be lacking an official ASN.1 specification. There is however an internet draft that describes (a possible) standard format.


Is an efficient integer factorisation algorithm a threat to security anymore?

AES is a secret-key cryptosystem, and as such can't replace a public-key cryptosystem like RSA, or an ECC-based one.
Examine how the certificate of a web server is signed and you'll see RSA is far from dead, and actually remains king when it comes to static signature of certificates, for excellent reasons. If you look at the present server, not only the certificate is RSA-signed, but the key signed is actually RSA.
Thus yes, an integer factorization algorithm faster than GNFS for balanced biprimes would be a big deal. If it makes factoring a 1984-bit (or even 1536-bit) RSA modulus borderline feasible for well-funded adversaries, or factoring a 1024-bit RSA modulus feasible for more casual hackers, it could be a threat to the current IT infrastructure. 2048-bit RSA is extensively used, or 1984-bit when 255 bytes is a sound barrier, 1536-bit on occasions, and 1024-bit in legacy systems including some door locks (but it's easy to kick these open or sneak in).
I'm far from ruling out we'll see the RSA-1024 (former) challenge openly factored in the next 5 years, or that this size is already factored covertly. I'm ready to bet we'll get there unless a global disaster strikes, and that it won't first be with a quantum computer.

Addition: when RSA is used for encryption, factorization of the public key remains a threat as long as the encrypted data remains of interest and did not leak. Thus even if Post-Quantum Crypto had a fast adoption rate (contrary to human nature of not changing what works unless that's indispensable within a defined time frame), factoring RSA moduli will remain of practical interest decades after.


What does the mask generation function in PKCS#1 output if the generated mask is shorter than the specified mask length?

In MFG1, the size of $T$ in octets of the provisionally generated mask is never smaller than the specified $maskLen$ at the point where we want to

  Output the leading $maskLen$ octets of $T$ as the octet string $mask$.

That follows from the fact that $T$ was built as the concatenation of $\lceil maskLen/hLen\rceil$ hashes, each of $hLen$ octets.

See the algorithm given in PKCS #1 V2.2, section B.2.1. Notice that the notation $\lceil maskLen/hLen\rceil$ means that the division is with the rounding upwards. In C and Java, if maskLen > 0, that is obtained as (maskLen - 1)/hLen + 1. This can not cause overflow, and the final + 1 nicely cancels with the prescribed - 1 in $\lceil maskLen/hLen\rceil-1$.


A most common use of "trusted" in cryptography is to state that what's qualified as "trusted", by hypothesis, behaves/works/performs per a certain precise set of rules (which depends on context), and will perform no less and no more. That's the case in trusted third party, and trusted server.

A special case is "trusted" applied to data, e.g. trusted key. There, trusted means that the data is assumed to possess some property, which depends on context. Typically, having been generated by a certain party in a certain way and not having been altered by any adversary; or/and being unknown to any adversary. Data can become trusted after having passed a cryptographic check, e.g. a digital signature or Message Authentication Code verification; or be initially trusted (e.g. a Root Certification Authority public key).

In marketing talk like trusted platform module or trusted computing, "trusted" means intended for implementation of something trusted in the above cryptographic sense. Experience often shows otherwise, but confusion between intent and fact is the lesser of the many kinds of lies in marketing (which also has plain lies, damned lies, and statistics).

"Trustless" means not requiring something "trusted". For a protocol, that's not requiring a trusted arbitrator, typically replacing that with users that still are expected to largely play by some rule, because they have no long-term interest in doing otherwise (perhaps, unless enough users band together to rip the others).


AES MDS matrix: can we maintain security if we change the arrangement of elements in the matrix?

An $n\times n$ circulant matrix $A$ with all entries nonzero is known to generate an MDS matrix. Here $n$ is 4, with alphabet $GF(2^8).$

An MDS matrix guarantees maximum diffusion in the MixColumns step. See the answer to the following question how-to-calculate-active-s-boxes-from-branch-number on why the fact that the minimum (symbol) Hamming weight achieving the maximum possible value of $n+1$ is important.

As pointed out by @Amin235 the new matrix you obtain is still MDS, but not being circulant, you've sacrificed computational speed. Since all MDS codes have the same weight distribution, not only the minimum possible diffusion, but all diffusion properties for all input/output vectors are identical between your new matrix and the original AES MDS matrix.


Is there an equivalent to an RSA UFO in lattice-based cryptography?

According to your link, RSA UFO means:

  Random moduli are also called RSA UFOs (Unkown Factorisation Objects).

If the definition of an RSA UFO is a modulus generated so that no one knows the factorization, this issue does obviously not exist in lattice-based cryptography, since the factorization problem is never used there. More generally, it is much easier to securely and distributively generate the random parameters of various cryptographic constructions in lattice-based cryptography; distributively and securely generating an RSA modulus with unknown factorisation is a notoriously very hard problem, whose solutions are usually quite inefficient (the link you give ends up with a modulus of total size 81kbits, which is quite huge). In contrast, public parameters in lattice-based cryptography will in general just need to be primes and some public random matrix, which is easy to generate securely and efficiently.


The valid advice of adding an Error Detection or/and Correction Code after encryption rather than before has two unrelated justifications:

If the cipher is weak, adding redundancy to the plaintext (as EDC/ECC before encryption does) might allow attack. In particular, it is possible to test if a key is valid by checking if the redundancy in tentatively deciphered plaintext is valid (a refinement of that is used to break the GSM cipher in the question's reference). However, that consideration is not a concern for good modern ciphers, since these should be resistant to chosen-plaintext attack.
EDC/ECC is typically optimized to detect/correct errors affecting few bits of the transmitted message. If encryption is applied after EDC/ECC, and correspondingly decryption applied before EDC/ECC on the receiver side, then errors on the transmitted message tend to get amplified by decryption (depending on the cryptosystem, as detailed hereafter). When this happens, desirable EDC/ECC properties such as insurance of detecting/correcting any at-most-N-bit error in the transmitted message tend to be lost, or greatly reduced.

for stream ciphers, CTR mode, and OFB mode, only errors on setup parameters or the IV will get amplified, but the effect of any such error will ruin the whole decrypted message;
in ECB mode, a 1-bit error is amplified to potentially one block;
in CBC mode (resp. CFB mode), a 1-bit error is amplified to potentially one block, and 1 bit in the next (resp. previous) block;
other modes exist such that error is amplified to the message after the error, or to the whole message;
with authenticated modes, practically any error will prevent decryption.


Can a zero knowledge proof (or MAC) be generated from human-typable input?

The usual way to encode long random bitstrings, so that they can be easily memorized and/or entered by humans, is to break them into blocks of (typically) 10 to 12 bits and map each block to an entry in a fixed dictionary of common words.  This approach is commonly used for secure passphrase generation, e.g. by Diceware, S/KEY and PGP.

Assuming an 11-bit (i.e. 2048 word) dictionary, which seems to be close to the "sweet spot" for English (in terms of difficulty of memorization per bit), you could compute a MAC of the current time using the shared secret key, truncate it to 88 bits and map these to a sequence of eight words for the user to enter.

Ps. The optimal choice of words to include in your list depends somewhat on the use case and especially the entry method you're envisioning.  For typed entry, shortness is important, whereas for spoken entry you want longer words with easily recognizable sounds.
For typed passphrase generation, I've personally found a good starting point to be the set of exactly 4-letter words in any basic English dictionary (which should give you around 2000 to 3000 words, depending on the size of the dictionary), optionally filtered to remove any inappropriate, obscure or confusingly similar words.

Edit: I didn't see your clarification before posting this answer.  Honestly, I'm not sure if the method I describe will help you in your task "to create a voting scheme that doesn't require a lot of crypto infrastructure", but then, I'm not really sure what would, either.  In the answer above, I implicitly assumed that storing the secret key and calculating the MAC would be done by a computer, with only the MAC entry stage being done by hand.  If you want the MAC calculation to be done by a human too, this becomes a very different (and much more difficult) challenge.


Are there any protocols that are truly secure from active and passive MITM attacks?

In short:

If you assume no shared secret, you can not build anything. For some theory on this, a similar assumption is formalized in the Dolev Yao model (all messages are send via the attacker, assumes perfect encryption), where no unauthenticated key exchange is possible.

If you assume a shared secret, then it depends on the kind of secret to run a number of protocols:

MITM for key exchange like Diffie-Hellman usually results in a different key for the connection between Alice and Eve and the connection between Bob and Eve (due to DLOG still being hard). So you start with a normal key exchange, but don't use this key for your session straight away.
run a one-way function on both the session key from the first part and the shared secret. For example you could use a key derivation function on the cocatenation. Eve should not be able to calculate this key, since she does not know the secret.
Use the derived key as session key or MAC key, or whatever you want to do with it. Eve should not know it, and it can be used to check message integrity (or to notice if Eve already tempered with the first key exchange).


Is there an encyption scheme that combines additive homomorphism with ability to proxy re-encrypt?

The schemes by AFGH in this paper are pairing based ElGamal type non-interactive, single-use (single-hop) and unidirectional IND-CPA secure proxy re-encryption schemes.

Although by their construction they are multiplicatively homomorphic (the authors do not mention it in the paper, but it works analogously to ElGamal), you can use the same trick as in "exponential ElGamal" to make them additively homomorphic.

This means that you represent the message $m$ to be encrypted as power of the generator $g$ of the target group ($G_2$ in their paper), i.e., as $g^m$ for messages in $Z_p$ (with $p$ being the order of the prime order group). Then, you are, however, limited to "small" message spaces as decrypting involves computing discrete logs in $G_2$. I do not know your application, but in many scenarios that should be sufficient.

As far as I know it has never been used in this context and there are no papers I am aware of that use additively homomorphic proxy re-encryption.

There may also be other schemes (as the one from INDOCRYPT 2013 pointed out by xagawa - however, this scheme is multi-hop - which may render it impractical for some applications but may allow others not feasible with one-hop schemes), but this one should be a good starting point. As already stated by Reid, Gentry's scheme can also be used for that, but fully homomorphic encryption schemes are not yet practically efficient.


Best practices (if any) to add metadata to encrypted files

This is pretty common. The method of encryption is public information, so it is safe to leave in the clear.

In your post you made no mention of authentication. This is something you absolutely must use, otherwise you have no way of knowing if your data has been modified and leaves you open to many attacks.

Consider using HMAC with SHA-256, or a block cipher mode with built-in authentication (e.g. GCM). Everything needs to be authenticated (any metadata, header, IV, ciphertext, etc).


Allow everyone to decrypt a message, but don't allow anyone to encrypt it

This is a scenario where your description would be much improved if you explicitly considered the following questions, which you should always ask in cryptography:

Who are the "honest" parties? (See at the bottom for an explanation of the scare quotes.)
Who are the adversaries?

In particular, you've not taken enough care to describe who the adversaries are.  The first obvious thing we can imagine is that there are third parties—neither your software nor its clients, both of whom would count as "honest parties"—that would eavesdrop on the broadcast and would like to know its plaintext.  If that's the model, then a simple solution would be:

All the messages are encrypted with a symmetric algorithm whose key is shared by the broadcaster and all the clients;
The broadcaster signs every broadcast with its own asymmetric keypair, and all clients verify the signature on every broadcast.

But there's a problem with this way of looking at it: should the clients really be modeled as "honest" parties, or are they actually a type of adversary?  Encryption only protects message confidentiality if the recipient is an honest party, who keeps the keys and plaintexts secret.

The problem with your scenario then is that you're disclosing information to another party and expecting them not to disclose it to anybody else.  That works if and only if the other party is "honest," and it could easily fail if the other party is an adversary.

Note that in cryptography, "honest party" is not a moral term.  It's a party to some protocol who can be counted on to execute it faithfully.  While an adversary is a party that cannot be counted on to follow the rules.


How well does scrypt perform on different architectures / OSes?

I've heard claims that it's relatively slow on Windows and/or Intel compared to Linux/AMD.

The claim that it could be Windows/Linux is a little off. It is more likely to be Intel/AMD, if anything. This will be an implementation detail based on the relative costs of processor instructions on each architecture; for example inc instructions are cheap on AMD, but costly on core 2 processors (relative to the speed of processors. You won't notice this difference unless you measure it).

In order to see numbers I suggest having a read of the x86 latency measurements made during the development of libgmp. They're slightly dated, but give you a fair idea that in fact not all assembly instructions cost equal.

Does this mean scrypt performs better on one processor or the other? Not at all. It means the implementation of scrypt measured performs better on one processor or the other. You should be able to produce optimised versions of scrypt for each architecture. This is, internally, what libgmp does for your multiprecision arithmetic - the optimised code for your architecture is the one you link to.

I'm not really a compiler expert, so I can't really comment on the behaviour of C compiled versions, but to achieve full optimisation you'd likely need to start from the assembler output of a compiler anyway.


Cracking passwords with more than 10 characters in a few hours?

Like Ricky Demer suggested, qeadzcwrsfxv is a common finger pattern (similar to something like asdfghjk).

The second example falls in the pattern of: Take dictionary word (besancon is the name of a city), uppercase the first letter and add a couple of digits after it (usually 123, 321, 007 or a year like 1998). Then a couple of rule-based alterations are tried: add a random letter, change a letter to a symbol (e.g. s => $) and so on.

A third way one of these passwords could have been cracked is by them being reused from another hack (e.g. the user used a variation of the password he used from linkedin).

In short, humans are very predictable in how they generate passwords.

A truly random password looks like this: T8vWdvLGhpRi9Gb. No discernable words or patterns. Numbers, lowercase and capital letters properly mixed together.  A password like this could only be broken by being reused on multiple websites or by being intercepted somehow.


If your software needs to decrypt the data and you want to prevent even those with physical access from decrypting without your software, you are basically out of luck. It is impossible to achieve purely in software, since even if a good white-box algorithm existed, an attacker could copy it into their software and be able to decrypt (without directly knowing the key, but who cares).

However, if you are willing to ignore those attacks and only protect the data against those who do not have access to the exact device and its software, you should use device specific keys, not hardcoded ones. That way even if an attacker would extract the key from their device, they would not be able to use that to attack other devices.


Why do we need multiple adversaries in a game-based definition?

It is a way of formalizing a security definition as an interactive game played against an adversary.
In an interactive game between an adversary and challenger, the adversary outputs some value, then the challenger responds, then the adversary chooses another value, etc etc. It's possible to define things at this level of formality (by using phrases like "adversary outputs a value and gets another value in response"). But sometimes you also want to introduce some precise notation about this interaction.
One way to do this is to think of the adversary (and challenger) as "next message" functions. This paper is considering $A_1$ to be the algorithm that outputs the adversary's first thing, $A_2$ is the algorithm that takes the challenger's response as input and outputs the adversary's second thing, etc. This kind of notation is formal and precise, but clunky. It's often also necessary to allow $A_1$ to pass its internal state ahead to $A_2$, etc. In the paper that you link, the goal is to apply to literally any interactive security game, thus the more formal style.
Here's an example for chosen plaintext security for public-key encryption. A perfectly reasonable way to define it would look like this:

Challenger chooses $b\gets \{0,1\}$, generates a keypair $(pk,sk)$, and gives $pk$ to the adversary
Adversary chooses plaintexts $m_0,m_1$
Challenger encrypts $m_b$ and gives the result to the adversary
Adversary outputs a guess $b'$, and wins the game if $b'=b$

A more "formalistic" way of defining the same interaction might read:

$b \gets \{0,1\}$ [challenger chooses random bit $b$]
$(sk,pk) \gets \textsf{KeyGen}$ [challenger chooses key]
$(m_0,m_1,\textsf{state}) \gets A_1(pk)$ [adversary gets public key and chooses two plaintexts]
$c \gets \textsf{Enc}(pk,m_b)$ [challenger encrypts one of the plaintexts]
$b' \gets A_2(\textsf{state}, c)$ [adversary gets ciphertext and outputs a bit $b'$]
declare the adversary winner if $b = b'$


Is there a ready report about character order frequency in most common passwords?

In terms of English language, what you are asking about are digram frequencies.

http://www.viviancook.uk/SpellStats/DigFreqs.html


The adversary has

a ciphertext encrypted under your key;
a copy of the key with $k$ bytes erased; and
knowledge of which $k$ bytes have been erased.

The adversary can try to decrypt the ciphertext and decide if the decryption makes sense in time $T$.

To find the key, the adversary need only do $2^{8k}$ trial decryptions, for a total time cost of $2^{8k} T$.

The key point is that there's usually no sensible way to make $T$ big.

Ergo, when $k$ is $4$, this is obviously easy.


$t$-out-of-$n$ Secret Sharing over $\Bbb Z_2$?

The question does not ask specifically for being in Shamir. This is a very interesting question, and has been studied in depth, with Ronald Cramer leading the effort. I refer you to the paper Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computations over Small Fields as a starting point in your research.


Is the following construction of a secure PRG is also a secure PRG?

Indeed, your intuition is perfectly correct and the distinguisher $D$ you're trying to build is basically $D'$ itself.
To see that this is the case, simply divide the experiment for $G'$ into two cases: either the chosen input is palindrome or it is not.
The first case occurs with negligible probability, so we can focus in the second case, but now it's easy since this case corresponds to the original experiment for $G$.

If you want to be formal, just keep in mind that
\begin{multline*}
\mathbb{P}\left[D'(G'(x)) = 1\right] = \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is palindrome}\right]\cdot\overbrace{\mathbb{P}\left[x\text{ is palindrome}\right]}^{\delta}
\\ + \mathbb{P}\left[D'(G'(x)) = 1|x\text{ is not palindrome}\right]\cdot\underbrace{\mathbb{P}\left[x\text{ is not palindrome}\right]}_{1-\delta}
\end{multline*}
and
$$\mathbb{P}\left[D'(r) = 1\right] =
\delta\cdot\mathbb{P}\left[D'(r) = 1\right] + (1-\delta)\cdot\mathbb{P}\left[D'(r) = 1\right].$$
Now, when you take the difference
$$\begin{align*}
\left|\mathbb{P}\left[D'(G'(x)) = 1\right] - \mathbb{P}\left[D'(r) = 1\right]\right|
\end{align*}$$
try to associate terms appropriately and apply some straightforward inequalities to show this is negligible.


Applicability of physical unclonable functions for public-key cryptography

Caveat: my understanding of Physically Unclonable Functions is partial, and my limited exposure to would-be PUF systems is old. I offer a tentative current opinion, hopping there will be constructive contradiction, and that I'll learn something new.

I know no practical system (or credible blueprint for such) where possession of a PUF can be assimilated to possession of a private key (the way we can with a Smart Card holding a private key, as long as it does resist attempts to extract the private key, as designed).

It is known how to achieve that after enrolling of a PUF with some PUF reading device (hereafter reader):

The reader+PUF can perfom a private-key operation.
When the PUF is separated from the reader, the private key can't be extracted from the reader (even if the reader is not tamper-proof), and the reader can no longer perform private-key operation.
The PUF itself can't be cloned in such a way that the unmodified reader will accept the cloned PUF (and perfom private-key operation).

However:

Moving the PUF to a new reader can only move the private key associated with the PUF to that new reader if some associated enrollment data is also moved to that new reader (e.g. thru an online connection, or with some traditional data storage moved along the PUF).
An attacker with the PUF, and said enrollment data, and the reader's full design (or the reader itself if not tamper-proof) can find the private key, then perform private-key operations without the PUF or/and simulate reader+PUF.

Some realizations (existing at least at the prototype stage) integrate the PUF, the reader, and perhaps enrollment data on the same piece of silicon. This does prevent attempts to make exact silicon-level copies, but won't resist extraction of the private key or more educated attacks.

Note: all the above holds if we replace private key by secret key.


Is it usual for a signed message to contain the public key of the signer?

I'd say that most of the time the signature is accompanied by the certificate of the signer. This certificate contains the public key. Most container formats such as CMS (used in S/MIME, also known as PKCS#7) or XML digsig contain specific fields that may contain certificates - and usually do.

When the certificate is received the Public Key Infrastructure (PKI) can be used to verify the certificate. In case of X.509 PKI that would for instance include verifying the chain of certificates leading to a trusted certificate (probably published by a Certificate Authority and included in a browser or system key store). Of course additional validation/verification should be performed, such as testing validity of the certificate and the revocation status. As you already noted, the other way is to validate the certificate or public key through a web of trust, such as used for (open) PGP.

The PKI is indeed a trust framework, although I would not directly call it a "trusted channel".

For specific protocols it may be that the public key is simply looked up in a trust store based upon a user name or key id. This is for instance the case in SSH, where the public keys are stored in a file containing trusted public keys and bound to the specific user.


Can a Vigenère cipher be solved if the alphabet is modified (custom)?

Basically, yes you can. To jump from alphabet to numbers without forgetting the + and / you can store the ASCII values in an array of 64 values.

Considering the order, it doesn't really matter as long as the cipher program and the decipher program use the same alphabet in the same order. You could use the ASCII order (symbol, numbers, uppercase, lowercase) or more probably the base64 order (uppercase,lowercase,number,symbol).

The list of the ascii values:

[43, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]


ECDSA key recovery - floating point values

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-1} \text{ mod } n$.


Cracking linear congruential generator knowing a, b, m and scaled numbers

Given an equation (for any modulus $Y$)

$$X_n = a_1 X_{n-1} - a_2 X_{n-2} \mod Y$$

you can just transform it into:

$$X_{n-2} = a_2^{-1}(a_1 X_{n-1} - X_n) \mod Y$$

So with $X_n,X_{n-1},a_1,a_2$ you can calculate $X_{n-2}$ directly. Furthermore: $a_2^{-1}$ is not division in the real numbers, but the multiplicative inverse in a finite group / ring, also called modular multiplicative inverse. If $a_2$ is coprime to $Y$, this inverse exists.


If I hear you correctly, you are trying to solve the problem of securely transporting $w$ and $v$ values, under the constraint of minimizing the ciphertext size.

So, what you're doing is taking the $w$ and $v$ values, selecting a random $r$ value, concatinating them into a 32 bit block, and then sending that block through Speck32 (with some key with unspecified derivation), and that's you're ciphertext.

With that procedure, I see these possible attacks:

Someone brute forces the key; Speck32 has a 64 bit key.  While brute-forcing the key would be beyond the capability of a random hacker, it would be within the capabilities of a determined large organization.  If your threat model requires you to be secure against such large adversaries, it's not good enough.
Someone recovers the key in another way.  You don't say how you keys are exchanges, but if (for example) you have a global key that everyone uses, then if someone breaks in one device, and grabs the key, then he has everyone's keys.
Looking for repeated values.  If someone sees the same ciphertext twice, then he knows the $w$ and $v$ values are repeated (and $r$, but he doesn't care about that).  Assuming that $r$ is generated randomly, then you are likely to see a repeat after perhaps 16 repeats of $w, v$ values.
Modifying the ciphertext block; if the attacker is able to modify the ciphertext, he can modify it to a value to a value he hasn't seen (which would cause the decrypted $w, v$ values to be effectively random).  Alternatively, he could modify it to be a ciphertext he has seen before (in which case, the decrypted $w, v$ values will be what we sent before.

So, to answer your questions:

  Even with the low entropy, are the messages individually secure (i.e. the compromise of some doesn't undermine the security of the others)?

Well, assuming that the attacker can't do a key recovery attack, then the best he can do is look for repeated values.  If he does see a repeat, and he knows the value in one case, he obviously knows the value in the other.  This doesn't tell him anything about any other ciphertext.

  Can successful guessing/statistics across a large enough set of messages compromise the key?

No, it doesn't help the attacker.  If he has the resources, he can perform the brute force attack on a handful of messages (assuming he can recognize plausible $w, v$ values); more ciphertexts doesn't help him.

  There's a temptation to use the last 8 bits for a MAC and/or CRC, but I fear that would make statistical attacks even better. Is that fear warranted?

Well, if you have a fixed value there (dependent on $w, v$), that increases the probability of a repeated ciphertext.  Also, if you go with using $r$ as the authentication, I wouldn't bother doing a CRC or a MAC on $w, v$; those are already stirred into the ciphertext.  What I would do is either use fixed bits (say, 0; those are easy to generate/verify, and is no less secure than a function of $w, v$), or if you want to add some protection against copy/paste attacks, make $r$ a function of the ciphertext context (e.g. a function of the message sequence number), and have the decryptor check it.  Now, it's not great (a random change would still have a 1/256 chance of being accepted), but it's better than nothing).

Some final comments:

One thing you need to worry about is key distribution; that's quite often the Achilles heel of crypto systems.  The best crypto system doesn't help if you make it easy for the attacker to learn the keys
Might I suggest you consider using Speck48?  Not only does it allow larger keys (making brute force attacks considerably harder), but it allows the $r$ value to be 16 bits larger; if you select $r$ randomly, this means that practically speaking repeated ciphertexts won't happen; if you select $r$ as a function of the message context, that means that a change will have a very good probability of being detected.  Of course, that means that you'll have 16 more bits to transmit; you'll need to decide whether that's a viable option.


is MAC double-hashing enough to prevent length extension attacks?

$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message))$$

is mac double-hashing enough to prevent length extension attacks?

Double hashing is defined by Ferguson and Schneier in their book Practical Cryptography in Chapter 6.3.1  to countermeasure again length extension attacks (and SHA256D used in Bitcoin). The details in their book, I don't have a copy. So, we can assume it has resistance to length extension attacks. Or, one can give a simple argument as;
To execute the length extension attack, the attacker needs to produce $$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad\mathbin\|message_2\mathbin\|pad_2))$$ But they can only control the $h$ and the actual length extenstion attack can work on the outer call like this
$$mac=\operatorname{SHA1}(\operatorname{SHA1}(secret\mathbin\|message\|pad)\mathbin\|message_2\mathbin\|pad_2)$$. And even the attacker can forge the mac (i.e. the result is same) it will fail since it will not work.

In order for someone to do a length extension attack of that, won't they either have to bruteforce the secret or bruteforce the initial SHA1 itself? (the first of which should be unfeasible with a good secret, and the second of which should be just as expensive, or maybe even more expensive, than just bruteforcing the new hash itself?)

So, you want to use this as a Message Authentication Code (MAC).
If the secret is at least 128 bits, then there is no way to brute-force the secret.
Bruteforce the initial here is called a preimage attack that is given a hash value $h$ find an input $x$ such that $h=H(x)$ ( or $h=H(H(x))$). The cost of the generic pre-image attack is $\mathcal{O}(2^n)$ where $n$ is the output size of the hash function $h$. For SHA-1 this makes $\mathcal{O}(2^{160})$. SHA-1 is shattered but not broken in the pre-image resistance. Therefore pre-image attack is infeasible. Actually, the pre-image attack doesn't guarantee to return the actual message used to create the hash value. One may fail there too.
There is no security proof of this construction as far as I know as a secure MAC. There is one extensive answer that on the upper level  $H(k\mathbin\|H(k\mathbin\|m))$.
Instead, use the proven one; the HMAC-SHA256, or the new one with SHA3; KMAC. Since SHA3 has resistance to length extension attacks, the construction of KMAC is much easier.
SHA3 design makes the prefix construction $H(k\mathbin\|m)$ a secure PRF, and come with built-in PRF mode, the keyed KMAC. Is comes with a theorem that connects the security of the PRF to the primitive.
Also, note that the trimmed versions of SHA2 series also have resistance to length extension attacks like SHA-512/256. The trim prevents to add an extension message and the padding to continue to hashing. One has to guess/try the trimmed amount that is impossible if the trim > 120.

update: I've looked into the book section 6.4. It turns out that they propose two methods and a new one in the new book.

propose is replacing $m \to h(m)$ with $m \to h(h(m)\mathbin\|m))$. And they defined $h_{DBL} := h(h(m)\mathbin\|m))$
They believe that if $h$ is a secure cryptographic hash function with $n$ nit output then it has a security level $n$. This is slow and you need to has the entire message twice.

propose is the double hashing $h(h(m))$ with only claimed claimed that it is has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.

proposal is in the new book Cryptography Engineering: Design Principles and Practical Applications 1st Edition

$$h_d := h(h(0^b\mathbin\|m)$$
and claimed that it has $min(k,n/2)$ where $k$ is the security level of $h$ and $n$ is the output size.


What does this notation stand for when describing a code?

$Z_2^5$ means that you are working in $GF(2)^5$.

$GF(2)$ is the Finite Field with two elements: 0 and 1 with the addition and multiplications defined:

$0 + 0 = 0\\
0 + 1 = 1\\
1 + 0 = 1\\
1 + 1 = 0$
It is equivalent to XOR.

$0 \times 0 = 0\\
0 \times 1 = 0\\
1 \times 0 = 0\\
1 \times 1 = 1$
It is equivalent to AND.

the $ ^5$ is the dimension of the space (or the size of the vectors). Here you are using a space of dimension 5, hence 5 coordinates.

$(0,1) \in Z_2^2\\
(0,1,0) \in Z_2^3\\
(0,1,0,1,1) \in Z_2^5$

The exponent notation represent the Cartesian product of the spaces:

$Z_2 \times Z_2 = Z_2^2\\
Z_2 \times Z_2 \times Z_2 \times Z_2 \times Z_2 = Z_2^5$


Breaking Insecure Elliptic Curve Cryptography

You mention your point has order
$$93556643250795678718734474880013829509\\196181230338248789325711173791286325820$$
 which factorizes as

$$2^2\cdot 3\cdot 5\cdot 7\cdot137\cdot593\cdot 24337\cdot 25589\cdot3637793\cdot5733569\cdot106831998530025000830453\cdot1975901744727669147699767.$$

Without much computing power, we can apply the Pohlig-Hellman algorithm to obtain
$$t\bmod4, t\bmod3,t\bmod5,\ldots,t\bmod5733569.$$

Using the Chinese Remainder Theorem, we can combine all these results to get

$$t\bmod\left(4\cdot3\cdot5\cdots5733569\right),$$
i.e.
$$t\bmod443208349730265573969192476820.$$

As @Ruggero remarks, the other primes are only about 80 bits. So with $\approx 40$ bits of computing power we could also break that discrete logarithm. It takes a little more effort than the others though, so if $t < 400\cdots 0$, then you may as well only do the easy ones.


encrypted with the TPM’s private EK

There's something wrong with the document you're reading. Encrypting with a private key is nonsense. A private key can be used to decrypt or to sign. Here, “signed” is clearly meant instead of “encrypted”. That's a sign that the author of the document doesn't know what they're talking about. I strongly recommend reading more reliable material.

In addition, the EK isn't used to sign a platform attestation. That's an AIK. Using an EK to sign a platform attestation would be a privacy violation. The EK is used inside the TPM to decrypt data as part of the AIK enrollment protocol.

The part about hashes of software is correct. The main CPU and the TPM cooperate to calculate a hash of all the code that is executing on the main CPU. Upon request, the TPM can sign a message that says “the hash of the code that is executing on the main CPU is …”. This message is signed with an AIK, which is a key pair for which only the TPM has the private part. When a verifier wants to know the state of the platform, it sends a request to the TPM containing a nonce. The nonce is included in the signed reply.
$$
\mathsf{verifier} \rightarrow \mathsf{TPM}: \mathrm{nonce} \\
\mathsf{TPM} \rightarrow \mathsf{verifier}: \mathrm{hash}, [\mathrm{nonce}, \mathrm{hash}, \ldots]_{\mathrm{AIK}_{\mathrm{priv}}} \\
$$
The fact that the message has a correct signature guarantees that it was produced by the TPM at some point in the past. The fact that the correctly signed message includes the nonce guarantees that it was produced by the TPM at some point after the verifier generated the nonce: this prevents replay attacks.

A valid attestation authenticates the platform. In addition, it guarantees that the platform is in a certain state. This alone does not say anything about the integrity of the platform. In order to guarantee the integrity of the platform, the verifier must know what the correct value is for the hash of the platform state (or a set of correct values, if more than one value is possible).

This protocol does not require a trusted third party once the TPM has been provisioned with an AIK and the verifier has enrolled this AIK. However, in practice, an infrastructure will often separate the verifier from the relying party. The relying party is an entity that wants to communicate with the platform, and is only willing to do so if the platform is in a good state. However the relying party does not know what a good state is, so it relies on a trusted third party to perform the verification.


"Efﬁcient, Compromise Resilient and Append-only

Cryptographic Schemes for Secure Audit Logging"  (PDF)

gives a publicly verifiable approach that allows fine-grained verification,

but it is in the Random Oracle Model.

The Simple Method:

The verifier and logger start with a seed for a

forward-secure pseudo-random number generator.

To denote a valid ending of a log, put the string of

the next $b$ bits of the PRNG's output into the log.

To add a log entry, get the next $\:b+k\:$ bits of the PRNG's output,

put into the log the encryption of the log entry and the mac of that

ciphertext using the last $k$ of the $\:b+k\:$ bits of PRNG output as the

mac key, then erase those $\:b+k\:$ bits and the previous PRNG state.


JSON AES-128: Security against known plaintext attack

Suppose the attacker knows [some part of the plaintext]
Does this reveal information that could lead to a security exploit

Given the rest of your notes, that you're using CBC mode (and depending on how you manage the IV), then yes, it can allow the attacker to modify messages such that the attacker can control the decrypted plaintext. For instance, an attacker could likely modify {"d":{"status":"success"}} to {"X":{"status":"success"}}. This could be a significant exploit or not.

(the attacker finding the key)?

Not directly. That isn't computable, even if you know the full plaintext and ciphertext. While the math is slightly different, this is similar to the problem of coming up with a plaintext that generates a given SHA-256 hash. AES is intended to make this computation no more efficient than a brute-force search.
However, if you are using a password to generate the key, and your KDF is incorrect, then there are definitely very good attacks against the password, and through it, the key. Knowing things about your data format will make these attacks faster (and if you fail to create a proper IV, they will be even faster). There are a lot of little pieces to correct AES encryption. If you get any of them wrong, then all the "AES is unbreakable" claims go out the window. Properly Encrypting With AES With CommonCrypto covers the main issues. They are the same for .NET as they are for ObjC.

If so, what would prevent this?

To the initial problem (data integrity / authentication), as Simon Johnson says, ideally use an authenticated mode such as CCM or GCM rather than CBC.
Alternately, if you do not have an authenticated mode available, use an HMAC to authenticate your data and demonstrate that it has not been modified. I would recommend draft-mcgrew-aead-aes-cbc-hmac-sha2 as a good approach to this. RNCryptor is similar and designed to address this issue, but there is not yet a C# implementation. (If you are interested in this problem, it is very easy to implement the RNCryptor data format in C#, and I'd be happy to work with you to build an open source version.)

If there is no security risk, what property of encryption prevents it from being an issue?

Let us consider the more basic version of this question. Get rid of block cipher modes, IVs, authentication, etc. Let's get back down to just AES. All AES does is transform 16 bytes into a different 16 bytes.
Encrypting with a key K and plaintext P yields a ciphertext C.
E(K, P) = C

For AES, there exists an efficient inverse of E called D such that:
D(K, C) = P

This just says that it is possible to encrypt something with a key, and then decrypt it with the same key. I.e.:
D(K, E(K, P)) = P

What you're asking for is some efficient function X such that:
X(P, C) = K

There are many functions E and D for which an efficient X exists. For example, if E is the xor function, then D is also the xor function and X interestingly enough is also the xor function. However, the AES function is such that there is no known efficient X (I don't believe that this is currently proven, but we certainly do not know what that X is).
This is a very long-winded way of saying that there is no known Known-plaintext attack on AES.
(I'm making a somewhat sloppy and broad claim here. There are some known attacks against AES that are not related to known-plaintext. There is a known attack that can recover an AES-128 key in complexity 2^126.1, which for cryptographers is a really powerful finding, but for most common uses is not a major concern.)


Quick scan which data (hmac/fernet) can be decrypted with a key?

Found a stupidly simple solution: Create an index of md5(key).

Alternatively, replace md5 with hash method of your choice.


What does AES256-CTS-HMAC-SHA1-96 mean in relation to Kerberos?

Decoding AES256-CTS-HMAC-SHA1-96

AES256 = AES using 256-bit key
CTS = ciphertext stealing
HMAC-SHA1-96 = HMAC using SHA-1 hash function with mac truncated to 96 bits.

The benefits of HMAC truncation are discussed in FIPS PUB 198-1, chapter 5.
For HMAC-SHA1 96 bits is very common truncation, used for instance by IPsec/ESP.

For figuring out what key material is used, it is decided by Kerberos. Please, read the appropriate standards.


Is it reasonable to assume that $\text{Keccak-}f[25n]$ block permutation is defined for any value of $n$?

From a standardization point of view, $\text{Keccak-}f[25w]$ (i.e. $\text{Keccak-}p[25w, r]$ with $r = 12 + 2\lceil \log_2 w\rceil$) is simply not defined in FIPS PUB 202 when $w$ is not a power of two. Specifically, the Keccak permutation is only standardized for $w = 2^\ell$ with $\ell \in \{0, 1, \ldots, 6\}$. This means that, even if you can define the permutation for other values of $w$, it will be nonstandard.

That said, if $w$ is not a power of two the permutation will be less efficient (per bit). Ideally, your processor has instructions to operate on $w$ bits. In practice, one expects $\ell \ge 3$ for most applications. This is probably the main reason why the standard/original specification do not mention other values of $w$. Also, $w$ isn't allowed (in the standard) to be arbitrarily large because that would be overkill.

From a mathematical point of view, one could also define the permutation for $w$ not a power of two (despite the lack of a good reason). Let's consider each step separately:

$\theta$ just uses xors of bits and generalizes to all $w$, but as discussed below it is not necessarily invertible.
$\rho$ rotates each word. This works for any word length.
$\pi$ is a word permutation which clearly works for any $w$.
$\chi$ is bitwise along rows, so again no problem.
$\iota$ adds a constant to one of the lanes. This step requires more changes.

The problem with $\theta$ (thanks to poncho for pointing to this) is that it is not invertible for all values of $w$. In particular, if we represent the state as an element of the ring $\mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ as in the reference, $\theta$ can be written as

$$\theta(\alpha) = p_\theta \alpha = (1 + (1 + y + y^2 + y^3 + y^4) (x + x^4 z))\alpha,$$

Hence, we must have $1/p_\theta \in \mathbb{F}_2[x, y, z] / \langle x^5 + 1, y^5 + 1, z^w + 1\rangle$ and this not true for all $w$.

The reason why the $\iota$ function does not immediately generalize is because it adds  $\ell + 1$ round constant bits to bits $2^j - 1$, $j = 0, \ldots, \ell$. The natural generalization would be to do the same thing but with $\ell = \log_2 \lceil w\rceil$. The problem occurs when $\ell > 8$. The round constants are computed using an 8 bit LFSR. If you want more bits, you need a larger LFSR. For all $\ell \le 6$, the same LFSR is used but some output bits are ignored. So you will need to specify another LFSR...
That said, it is not even essential that one uses an LFSR to generate round constants so you could argue that this isn't a major problem.

If $\ell$ is very large, I'm also not sure if $r = 12 + 2 \ell$ rounds would really be sufficient. I'm not going to make that analysis here, though.