Measuring entropy of a uniform distribution source

In cryptography and information theory, Shannon entropy $H(X)$ is a characteristic of a source $X$ of discrete symbols; e.g. a characteristic of a dice. It's usually expressed per symbol produced, and with unit the bit (per symbol). It tells the expected/average number of bits necessary to encode the value of a symbol, knowing the characteristics of the source. In particular, the entropy of a known¹ deterministic source (such as a Pseudo Random Number Generator with known¹ seed) is $0$.
Assuming the symbols can take values $x_i$, are produced independently at random (that is, earlier outcomes have no influence on later ones), and each symbol $x_i$ has fixed probability $p(x_i)\ge0$ with $1=\sum p(x_i)$, then
$$H(X)=\ \sum_{i\text{ with }p(x_i)\ne0}p_i\,\log_2\frac1{p(x_i)}$$
For example, a fair dice has entropy $H(X)=6\,\left(\frac16\log_26\right)=\log_26\approx2.585\ldots\,$bit/symbol. Another dice, biased towards generating 6 with probability $1/5$, and the 5 other sides having probability $4/25$, has $H(X)=\frac15\log_25\,+5\,\left(\frac4{25}\log_2\frac{25}4\right)\approx2.579\ldots\,$bit/symbol.
This illustrate the fact that for a given number $n$ of symbols, entropy per symbol is maximal at $\log_2 n\,$bit/symbol when all the symbols have the same probability, that is uniform distribution. The article mentioned in the question has it right!
Intuitive justification: when things have a high probability to be in a corner (uneven distribution), there is less disorder/entropy than when they are spread evenly all around. In the later case it takes more information to describe where each thing is.

¹ What happens if we remove known is a matter of perspective. Any PRNG implementable with finite resources has zero entropy, for we can define all it's output with a finite amount of data. On the other hand, for practical adversaries, a Cryptographically Secure PRNG that outputs integers symbols in $[0,n)$ is indistinguishable from a true RNG with entropy of $\log_2 n\,$bit per symbol and the same output domain.


Show that there is an efficient zero knowledge proof for any language $L \in NP$

Your idea is correct. Although the running times of the honest prover and verifier do increase by the running time of $R$, this (somewhat counterintuitively) does not affect the concrete bounds for soundness and ZK (at least how they are usually defined).
Note that $T$-soundness does not really make sense for a proof system, since it is sound against even unbounded cheating provers. However, it does make sense for an argument system, and here we don’t really “lose” the reduction $R$’s runtime: any $T$-time cheating prover $P_2^*$ for some instance $x \notin L$ is itself a $T$-time cheating prover for the instance $R(x) \notin A$, because it fools the verifier $V$ (for language $A$) without doing any additional computation. The latter does not exist by assumption, so neither does the former.
Similar reasoning holds for ZK: a $T$-time cheating verifier $V_2^*$ for some instance $x\in L$ is itself a $T$-time cheating verifier for $R(x) \in A$, because it plays the role of $V$ in talking to $P$. So, we don’t need any additional computation to “gain knowledge” from an interaction with $P$ about $R(x)$.


Why has the McEliece cryptosystem not gained much acceptance, but now is a candidate for post-quantum cryptography?

The simple answer is that there are two reasons:

The lack of a standard implementation. RSA has an acknowledged standard while McEliece doesn't.
The size of the key. It's huge! In the multi-megabit range. In terms of today's communication networks, that is bad, but - in my opinion - not too bad. It means it takes time to exchange, but once you have built up your local DB of keys for actors that you communicate with, well, so what. But storing the keys is another matter. You can't just pop them in to a varchar field: you need to really think about your local key storage issues.

That said, I think that there is a definite use case for McEliece coming. Especially if you have secrets that have to be secure for a long period of time.

Current PKE used for thanks like SSL and bank transactions is fine: the time to live for the transaction is relatively small. But think of the security around a property transaction using smart contracts: lots of property is held for > 20 years. If the title deeds are proven via a secure document then you need the security on that document to live at least that long - probably many times that length.

Just for fun, I downloaded a version of McEliece called CodeCrypt, compiled that and generated a key. It took 9 minutes of CPU time!

Now, if I have done this all correctly, the public key is only 4K, and the private secret 20K, which is either way too short, or (more probably) I have made a mistake somewhere.


Possible issues with ECIES using a static (non-ephemeral) sender key

What trade-offs exists with this alternate approach?

Unless you need the non-repudiability you produce a larger ciphertext in a slower way for no interesting gain in security when signing and encrypting over using the static keys (apart from the "other downfalls" below).

  Are there any other downfalls of this approach?

Indeed if now either of your long term secret is compromised all ciphertexts can be decrypted unlike in traditional PKE schemes where only one party has such a long-term secret.

  Is this regarded as just a form of ECIES or is it possibly something different since the sending key is not ephemeral?

Technically speaking it doesn't fit the traditional signature of a public key encryption scheme because there the encryption isn't allowed to maintain state and obviously a sender secret can't be part of the public key. The most common name for this I know would probably be crypto_box (taken from NaCl's naming) which does essentially this. Academically speaking the correct name is "public-key authenticated encryption" because it is the public-key equivalent of authenticated encryption.


Is it problematic to use PBKDF2-HMAC-SHA256 to derive a 512-bit XTS key?

Background.
PBKDF2 has a stupid design where generating two blocks of output costs the legitimate user twice as much as generating one block of output, without necessarily putting additional cost on the adversary's task of confirming a password guess.  This is because each block of PBKDF2 output is generated by iterating the PRF on distinct initial inputs, which prevents sharing the work to generate each block: $$\operatorname{PBKDF2}(F, s, p, n, b) = \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert 1)\Bigr] \mathbin\Vert \cdots \mathbin\Vert \Bigl[\bigoplus_{i=1}^n {F_p}^i(s \mathbin\Vert b)\Bigr].$$  Here ${F_p}^i$ is the $i$-fold iteration of the PRF $F$: ${F_p}^0(\sigma) = \sigma$, ${F_p}^{i+1}(\sigma) = {F_p}^i(F_p(\sigma))$.

It would have been more sensible to separate the computation into two stages like HKDF does (for a different but related purpose) with HKDF-Extract and HKDF-Expand: a costly computation to generate a master secret once, and then a collection of cheap computations to generate each block of output.  But PBKDF2 did not do this.

In general, PBKDF2's stupid design hurts security: if the legitimate user can afford to compute $n$ iterations of the PRF, and needs $b$ blocks of output, the number of iterations that the legitimate user can spend on each block independently is at most $n/b$.  If the adversary has a cheap way to confirm a password guess given any one of the blocks of output, e.g. in a password hash, then it is as if the legitimate user had a budget for only $n/b$ iterations and not $n$ iterations of the PRF.

Does this hurt in the case of XTS?
XTS is the tweakable 128-bit block cipher defined on tweak $(i, j)$ in terms of the block cipher $E$ by $$\operatorname{XTS}_{k_1,k_2}(P, i, j) = E_{k_1}(P + T_{ij}) + T_{ij}, \quad\text{where}\quad T_{ij} = E_{k_2}(i) \cdot x^j.$$  Here arithmetic is in $\operatorname{GF}(2^{128})$ represented by the irreducible polynomial $x^{128} + x^7 + x^2 + x + 1$, with your favorite choice of identification of $\{0,1\}^{128}$ with $\operatorname{GF}(2^{128})$, e.g. little-endian.  (Details of ciphertext stealing are omitted because we use sensible block sizes for everything.)

Suppose you use XTS to encrypt your laptop, and the adversary, a thief, has stolen your laptop.  They have a candidate guess for a password, for which they have spent the cost to compute either $k_1$ or $k_2$, but not the other.  How expensive is it to use this partial information to confirm a password guess, vs. spending the additional cost to compute the remaining $k_2$ or $k_1$ and confirm a password guess with full candidate key information?  Assume that $P$, $i$, and $j$ are fixed and known to the adversary.

The adversary has a candidate $k_1$ but not $k_2$.  The question is whether the function $$\phi\colon k_2 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator.  Define $f\colon \sigma \mapsto E_{k_1}(P + \sigma \cdot x^j) + \sigma \cdot x^j$, so that $\phi(k_2) = f(E_{k_2}(i))$.  Let $A$ be a putative distinguisher for $\phi$.  Define $A_0(\mathcal O) = A(f(\mathcal O(i)))$ as a putative PRP-distinguisher for $E$.  Note that $$A(\phi(k_2)) = A(f(E_{k_2}(i))) = A_0(E_{k_2}),$$ so that
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRP}}_E(A_0)
    &= \left|\Pr[A_0(E_{k_2}) = 1] - \Pr[A_0(\pi) = 1]\right| \\
    &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right|,
\end{align*}
where $\pi$ is a uniform random permutation.  Then, if $U$ is a uniform random 128-bit string,
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRG}}_\phi(A)
    &= \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(U) = 1]\right| \\
    &\leq \left|\Pr[A(\phi(k_2)) = 1] - \Pr[A(f(\pi(i))) = 1]\right| \\
    &\quad + \left|\Pr[A(f(\pi(i))) = 1] - \Pr[A(U) = 1]\right| \\
    &= \operatorname{Adv}^{\operatorname{PRF}}_E(A_0)
       + \operatorname{Adv}^{\operatorname{PRG}}_f(A).
\end{align*}
Thus, it effectively reduces to the question of whether $f$ is a PRG.  This is close to the question of whether $\sigma \mapsto \pi(\sigma) + \sigma$ is a PRG, if we model $E_{k_1}$ by a uniform random permutation $\pi$, which is essentially the Matyas–Meyer–Oseas construction as studied by Black, Rogaway, and Shrimpton in 2002.  By a wing-waving argument, I assert that this seems like a reasonable model for most block ciphers (note related-key attacks are not relevant), and I conjecture the answer is no, the adversary can't effectively confirm a guess knowing only $k_1$ without computing $k_2$ unless they've broken $E$.
The adversary has a candidate $k_2$, but not $k_1$.  The question is whether $$\psi\colon k_1 \mapsto E_{k_1}(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j$$ is a pseudorandom generator.  This straightforwardly reduces to the PRP-security of $E$.  Given a PRG-distinguisher $A$, define the PRP-distinguisher
\begin{align*}
  A_1(\mathcal O)
    &= A(\mathcal O(P + E_{k_2}(i) \cdot x^j) + E_{k_2}(i) \cdot x^j) \\
    &= A(\alpha(\mathcal O(\alpha(P))))
\end{align*}
where $\alpha\colon \sigma \mapsto \sigma + E_{k_2}(i)\cdot x^j$ is a permutation, so $A_1(E_{k_1}) = A(\psi(k_1))$, and
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRP}}_E(A_1)
    &= \left|\Pr[A_1(E_{k_1}) = 1] - \Pr[A_1(\pi) = 1]\right| \\
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right|,
\end{align*}
where $\pi$ is a uniform random permutation.  Clearly since $\alpha$ is a permutation, $\alpha(\pi(\alpha(P)))$ has uniform distribution, so
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRG}}_\psi(A)
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(U) = 1]\right| \\
    &\leq \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\
    &\quad + \left|\Pr[A(\alpha(\pi(\alpha(P)))) = 1] - \Pr[A(U) = 1]\right| \\
    &= \left|\Pr[A(\psi(k_1)) = 1] - \Pr[A(\alpha(\pi(\alpha(P)))) = 1]\right| \\
    &= \operatorname{Adv}^{\operatorname{PRP}}_E(A_1).
\end{align*}
The answer is no, the adversary cannot effectively confirm a guess knowing only $k_2$ and not $k_1$ unless they've broken $E$.

Why couldn't we just make $k_2$ public like an IV?
If we did that, the following chosen-plaintext distinguisher would trivially break it: Submit $(P, i, j)$ and $(P + \delta, i, j')$ for the challenge, where $j \ne j'$ and $\delta = E_{k_2}(i) \cdot x^{j'} - E_{k_2}(i) \cdot x^j$, and test whether their ciphertexts differ by $\delta$.

While this justifies keeping $k_2$ secret in the cryptosystem in general, it's not clear that this power of the adversary is relevant to password-guessing for stolen laptop disk encryption: for every password they guess, the thief who stole your laptop would have to submit to you a chosen plaintext to encrypt in order for them to confirm that password.  It's hard to imagine how this could happen unless you're willing to help me recover a large sum of money from a Nigerian prince I know.

But laptop disk encryption is not the only application of disk encryption.  You might use iSCSI over the network, and the adversary might have compromised the iSCSI storage server without your knowledge, and may be able to control blocks of data written by the iSCSI client.  In that case, the adversary may be able to submit a chosen plaintext derived from the value of $k_2$ for every password they guess, and use the client as an oracle to confirm the password at lower cost than evaluating PBKDF2 again to compute $k_1$.

Conclusion.
In the case of laptop disk encryption with AES-XTS, the stupid design of PBKDF2 does not appear to hurt the way that it might generically.  But that took a lot more work to prove (and there's some gaps: e.g., does it make a difference if the adversary has many blocks of output to confirm a guess?—rewrite $\phi$ and $\psi$ as PRFs of $(P, i, j)$).  And it's possible I posed the wrong question, or made a mistake answering the questions I posed: this is, after all, a pseudonymous internet fowl talking feathery nonsense at you, not a bespectacled cryptographer writing in a respectable peer-reviewed journal.  And there are imaginable applications of disk encryption for which this use of PBKDF2 does hurt security.  It would have been safer to derive a master key with PBKDF2 and then derive subkeys from it with HKDF.

P.S.  You should use scrypt or argon2, not PBKDF2.  They make a much bigger difference than this quibbling!  They also don't have this stupid design.  That, or just generate your passwords uniformly at random from ${\geq}2^{128}$ possibilities.


ECDH/ECDSA key exchange on embedded devices

You can assign each device its own unique certificate with a signature issued by the CA (for example, could be the manufacturer) on the certificate. So each device stores the following: its own unique certificate (its public key), its corresponding secret key, and the signature on its certificate issued by the CA. During key exchange, 2 devices would send each other their respective certificates plus the CA's signatures on those certificates, which can be verified using the CA's public key.


Additive inverse for elliptic curve addition in finite field in jacobian coordinates

The projective form of Weierstrass equation of an elliptic curve is obtained by replacing $x$ by $X/Z^c$ and $y$ by $Y/Z^d$. If $c=d=1$ then we have standard projective coordinates. In this state, point at infinity is $(0:1:0)$. But in Jacobian coordinates($c=2$ and $d=3$), point at infinity is $(1:1:0)$.

As poncho said in comments, The additive inverse of the point $(X:Y:Z)$ is  $(X:-Y:Z)$ .


Why k-lists generalized birthday problem when $k=2$ is classical birthday problem?

They are essentially the same, certainly in terms of complexity. Any collision $x=y$ with $x\in L_x$ and $y\in L_y$ is a collision in a single list $L_x \cup L_y$ of size at most twice the size of the larger list.

Any collision in a single list is compatible with about half the partitions of that list into two equal sized halves. So an algorithm that finds a collision in the union randomly has found a collision in the two-list problem with probability $1/2.$

Moreover in the crypto context the lists contain (pseudo)random outputs of hashes or other crypto primitives.


Calculate number of required pairs for differential cryptanalysis

See Heys' Tutorial on Linear and Differential Cryptanalysis (google it) for a gentle introduction.

Ali Aydin Selcuk has carefully analyzed this success probability in a number of papers.

For differential cryptanalysis roughly $c/p$ plaintext ciphertext pairs are needed where $c$ is a small constant dependent on the cipher.

As for your second question, unless $p$ is much larger than about $2^{-80}$ there is no practical attack. After all, you need to encrypt at least as many as $c/p$ plaintext ciphertext pairs to collect data before you can mount the attack and the quantity $c/p$ is a lower bound on at least your time complexity (possibly also your memory complexity depending on your attack).

However a $p$ value that is appreciably larger than $2^{-k}$ where $k$ is the keylength of the block cipher indicates a weakness in that the cipher is weaker than expected, as in Biham and Shamir's attack on DES.


Why is breaking the Blum Blum Shub PRNG not an undecidable problem?

By the definition of a cryptographically secure PRNG on Wikipedia, given part or all of the internal state, an adversary should not be able to reconstruct the prior stream of random numbers.

That's an engineering specification of what requirements a practical CSPRNG should be evaluated against. The definitions used for pseudorandom generator (PRG) in cryptographic theory are weaker than that. For example in Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where the first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

This is the sort of definition that Blum Blum Schub would be evaluated against, and it doesn't even assume that PRGs have an incrementally updated state.

The engineering requirements (I wouldn't call it a definition) that you're reading are, of course, contemplating a range of practical attacks that the theoretical work abstracts away from. But you'll find that practical cryptographic random generator designs routinely embed something like the theoretical definition as a module. For example, with Fortuna the recommendation for what it calls its "generator" submodule is to use a block cipher in CTR mode, whose state is a key/counter pair that allows trivially to reconstruct earlier states (just decrement the counter). But that state is scoped to individual calls to the larger Fortuna construction:

The key is also changed after every data request (however small), so that a future key compromise doesn't endanger previous generator outputs. This property is sometimes described as "Fast Key Erasure" or Forward Secrecy.

So a generator that doesn't have forward secrecy (a name for the property you ask about) is used as a building block to construct one that does.


How can I ensure forward secrecy when storing encrypted messages in a public blockchain?

As long as you use a post-quantum secure encryption scheme the fact that your messages are on the blockchain is not a problem. Traditionally adversaries are assumed to be capable of recording the traffic on an encrypted channel so theoretically they have always been allowed to keep messages for future decryption.

Currently the best way to get the necessary security is probably to use a symmetric scheme because their security is believed to only halve against a quantum computer. Or you pick your favorite post-quantum crypto scheme and combine it with a traditional one. For example Frodo is pretty conservative in its choices and in the paper the authors describe a combination with ECDHE.

Note that forward secrecy is not actually a property of the stored messages but is about the receiver of the message throwing away the key. The goal is that if somebody compromises the sender or receiver in the future they won't find a key that allows them do decrypt those old messages. In this case the difficult part is for the sender to know the current key. That's why this is only used in interactive protocols in which both parties exchange messages. Otherwise they can not agree on a shared secret without one party proposing it and thus having to encrypt it with some long term key.


Is there any research about cryptography on nondeterministic Turing machines?

Summary. The short answer is: Cryptography would be insecure.  Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm.

Non-determinism is extremely powerful.  If you give everyone access to non-determinism, then secure encryption becomes impossible: the cryptanalysts win.

The Time Hierarchy Theorem isn't relevant here.  Roughly speaking, it says that we can make encryption take as long as we want.  However, that's not the relevant question.  The relevant question is the ratio between the time it takes to break a cryptosystem, divided by the time it takes for legitimate participants to use this cryptosystem.  If you give everyone access to non-determinism, this ratio becomes approximately 1.  You can use the Time Hierarchy Theorem to make encryption take twice as long, and then cryptanalysis will take twice as long, but that doesn't really buy you anything: if an attacker can break the encryption as quickly as you can encrypt, you have no security.

This might be counter-intuitive, but hey, that's non-determinism for ya: it's not exactly an intuitive subject.  I'll work out the technical details below for those interested, but I wanted to start with this summary of the bottom line.

Caveat: my answer is limited solely to encryption beyond the unicity distance (i.e., computational cryptography).  The one-time pad remains information-theoretically secure, if you give everyone access to non-determinism: but that's not very helpful, as the one-time pad is not practical to use in most real-life situations.  If we're not in the information-theoretic realm -- if the total amount of plaintext to be encrypted under a single key is much larger than the length of the key -- you are hosed; anything you do, will be breakable.

Intuition. Before diving into the technical details, let me give a crude analogy, for those who prefer to avoid the technical stuff.  In some really loose way, giving Eve access to non-deterministic computation is like giving Eve the power to read minds.

Suppose we live in a world where everyone can read everyone else's mind.  In a society of telepaths, is secure encryption possible?  No, it's not possible.  No matter what crazy stuff Alice does to encrypt her messages to Bob, it'll always be possible for Eve to read Bob's mind and extract the decryption key (or extract all bits necessary to decrypt).  Consequently, in a world of telepaths, encryption as we are familiar with becomes impossible.

What does non-determinism have to do with reading minds?  Well, suppose we think that every person's observable behavior is a known (or knowable) function of their internal brain state (or sequence of brain states).  Imagine that we observe Zach for a long time.  And, suppose we think that, for any set of observed behavior, there's only a single set of brain states that could have given rise to that behavior.  Then a non-deterministic algorithm can infer Zach's brain states based upon Zach's observed behavior, merely by guessing Zach's brain state and checking whether it is consistent with Zach's observed behavior.  In other words, in some really loose sense, a non-deterministic algorithm can read Zach's mind, based upon his observed behavior.  Here Zach's brain state is sorta like the key and other hidden intermediate values/choice bits used by the encryption or decryption algorithm, and Zach's observed behavior is sorta like the set of messages and ciphertexts produced by the encryption scheme.  "Reading Zach's mind" is kinda like recovering the key and hidden non-deterministic bits/intermediate values used during encryption or decryption.  The restriction that there's only a single set of brain states that are consistent with Zach's observed behavior is roughly analogous to the criteria that we are working with computational cryptography, i.e., beyond the unicity distance.

Now keep in mind that this is an extremely loose analogy.  Please don't take it very seriously, and please don't try to draw too many conclusions from it.  I know it is full of holes and can be criticized in all sorts of ways.  It is only intended for those who don't want to read the technical details and are willing to take it on faith that I know what I'm talking about, and want some gist of the idea without getting overwhelmed with the mathematics.  If you start criticizing my analogy, I will have no sympathy whatsoever: I'm just going point you to the mathematics, below.

The technical details. OK, for those who want to see me spell out the justification for my claims in detail, let's dive into the mathematics.

Let's start with a definition of what it means for a non-deterministic algorithm $A$ to compute some value.  We say that $A$ can yield output $y$ on input $x$ if, when you run $A$ on the input $x$, there exists some execution where $A$ accepts and outputs $y$.

Equivalently, you can think of $A$ as a deterministic algorithm $A_\text{det}$ with a side input $w$ to represent the choice bits used along the way (every place where $A$ makes a non-deterministic choice between two possibilities, it reads the next choice bit from $w$ and uses that to make the choice).  Then, $A$ can yield output $y$ on input $x$ if there exists some $w$ such that $A_\text{det}(x;w)=(\text{accept},y)$.  This formulation is easier to think about it, because it relates only to deterministic algorithms.

What about encryption and decryption?  Suppose we have non-deterministic encryption and decryption algorithms $E,D$.  Recall that for decryption to be correct, we need the decryption of an encrypted message to always return the original message.  In other words, if $E(k,m)$ can yield output $c$, and if $D(k,c)$ can yield output $m'$, then we must have $m=m'$.  One consequence is that if we fix a ciphertext $c$ and a key $k$, then there is a single unique message $m$ such that $D(k,c)$ can yield output $m$.  In other words, if we fix $c,k$ where $c$ is an encryption of $m$, then for every $w$ such that $D_\text{det}(k,c;w)=(\text{accept},\text{something})$, we in fact have $D_\text{det}(k,c;w)=(\text{accept},m)$.

What does it mean to be beyond the unicity distance, i.e., that the total lengths of the messages are much longer than the key length?  One consequence is that, if we have a set of known-plaintext/ciphertext pairs $(m_1,c_1),\dots,(m_n,c_n)$ where the sum of lengths of the $m_i$'s is much longer than the key $k$, then there is only a single key that is consistent with all of these pairs.  In other words, there is only a single key $k$ such that $D(k,c_i)=m_i$ for all $i$.  (OK, technically speaking, there might be multiple such keys, but they'll all be "equivalent", in the sense that if you have multiple keys $k,k'$ that are consistent, then they both decrypt most other messages the same way, so recovering either one counts as a "win" for Eve: either one will let Eve decrypt most of the other ciphertexts she sees.  That's a bit of a technical minutae detail which isn't really important here, and which is not specific to anything about non-determinism: it arises in the deterministic setting too.  We can safely ignore it, knowing that it can be fixed up if strictly needed.)  Nothing about this changes in the presence of non-determinism.

These are all preliminaries and set-up.  Now let's get to the proof of the claim I made in the summary.  Suppose Eve has $n$ known plaintext/ciphertext pairs, $(m_1,c_1),\dots,(m_n,c_n)$.  Here is an attack Eve can use:

Eve guesses the key $k$.
For $i=1,\dots,n$, Eve runs the decryption algorithm to compute $D(k,c_i)$ and checks whether $D(k,c_i)=m_i$.  Note that if the decryption algorithm is non-deterministic, this involves Eve making additional guesses for each $i$ (whatever guesses the decryption algorithm calls for you to make).
If there is any $i$ for which $D(k,c_i)\ne m_i$, Eve rejects.  Otherwise, Eve accepts and outputs $k$.

If you prefer to see the determinized version of this algorithm, it works like this.  $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ is the following:

Parse $w$ as the concatenation $(w_0,w_1,w_2,\dots,w_n)$, where the length of $w_0$ matches the length of the key $k$ and the length of each $w_i$ matches the number of choice bits made during decryption.
Set $k=w_0$  (this corresponds to "guessing" the key $k$).
For $i=1,\dots,n$, run $D_\text{det}(k,c_i;w_i)$ and checks whether $D_\text{det}(k,c_i;w_i)=(\text{accept},m_i)$.
If there is any $i$ for which $D_\text{det}(k,c_i;w_i)\ne (\text{accept},m_i)$, output $\text{reject}$.  Otherwise, output $(\text{accept},k)$.

Notice that $\text{Eve}_\text{det}$ is a deterministic algorithm; it's the equivalent of the non-deterministic algorithm for Eve I gave above.  Eve breaks the cipher if her algorithm accepts and outputs the correct key.  In other words,  Eve breaks the cipher if there exists some $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts and for every $w$ where $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)$ accepts, $\text{Eve}_\text{det}((m_1,c_1),\dots,(m_n,c_n);w)=(\text{accept},k)$.

So, does this attack work?  Certainly $k$ is one possible output of the non-deterministic algorithm for Eve; that much is easy to see.  Is it possible that Eve could accept and output some incorrect key $k'$ (where $k'\ne k$)?  No, that's not possible, by my discussion about the unicity distance.  Remember, there's only a single key $k$ that is consistent with all of the $(m_i,c_i)$ pairs.  Also, remember that decryption is correct: given a fixed key and a fixed ciphertext, there's only a single message the decryption algorithm can output (it's not the case that there are multiple possible decryptions).  So, if Eve happens to guess some other incorrect key $k'$, then there will be some known plaintext/ciphertext pair $(m_i,c_i)$ where $D(k',c_i)$ outputs $m'$ where $m'\ne m_i$.  This means that Eve will reject on all execution traces where she guessed that the key was $k'$.

Consequently, we are guaranteed that Eve's algorithm will output the correct key $k$.  And, $k$ is the only thing that her algorithm can output; she'll never output an incorrect key on any accepting execution.  So, Eve breaks the encryption scheme.  The only facts I used about the encryption scheme are that decryption is correct and that we're beyond the unicity distance, so this break is general.

Parting thoughts on the technical details. Phew.  That's a mouthful.  I expect that very few folks have followed to this point.  Let me just give a little bit of intuition about this proof.  I've basically just mimicked the standard proof that any polynomial-time encryption scheme can be broken using an $NP$ algorithm (i.e., non-determinism suffices to break any standard, deterministic encryption algorithm), but making small adjustments to account for the fact that now we want to allow the encryption/decryption scheme to be non-deterministic.  It turns out that this doesn't change anything important.

Let me share with you one more analogy.  The standard way of defining $NP$ is: a language $L$ is in $NP$ if there is a polynomial-time non-deterministic algorithm that recognizes $L$.  Alternatively, we can define $NP$ without reference to non-determinism: roughly, $NP$ is the set of problems where solutions can be recognized in deterministic polynomial time.  Slightly more precisely, a language $L$ is in $NP$ if there is a polynomial-time deterministic algorithm $V$ such that $x\in L$ if and only if there exists $w$ such that $V(x;w)=\text{true}$; we say that $w$ is a witness or proof to $x$ being in $L$, and the verifier $V$'s job is to check the validity of the proof.

What if we were to generalize the latter notion, to talk about the set of problems where solutions can be recognized in non-deterministic polynomial time?  In other words, what if we defined a complexity class just like $NP$, except where now $V$ is allowed to be a non-deterministic algorithm (so you get to use non-determinism in checking the proof)?  Here's the cute answer: what you get is no larger than $NP$; you get exactly $NP$.

The connection to cryptography is that verifying you've broken the cryptosystem correctly (verifying that you have the correct key) is analogous to the role of the verifier $V$ in the definition of $NP$.  Even if you allow encryption and decryption to be polynomial-time non-deterministic algorithms (corresponding to allowing $V$ to be a polynomial-time non-deterministic algorithm), non-determinism still suffices to break everything (corresponding to the fact that $NP$ is still enough to recover all the corresponding languages).  OK, I realize that maybe this didn't help at all.....


Is it possible to mathematically extract an AES key from black-box encrypt/decrypt hardware?

What you describe is Chosen-Plaintext Attack (CPA) and AES and secure block ciphers are designed to be secure against this.

Having $2^{16}$ chosen-plaintext under one key doesn't help you to extract the AES key. You have to go to the full-brute force to find the key.

Since you have one target, you cannot get help from attacking many keys simultaneously. In some cases, the black box may reside in many days in front of you, thus, during those days, you will get many target keys.

For $t$ targets, the expected cost breaking one of the $t$ keys is $2^{128}/t$ and that will be far below $2^{128}$. If you have a billion target (~$2^{30}$) the cost will be ~$2^{98}$ to find one of the target keys.


One way shared key encryption with NaCl - is it safe to generate a throwaway keypair for the encrypting party

If you want users to be able to send you messages anonymously you can use "sealed boxes" instead of plain boxes.


How can a collision be generated in this hash function by inverting the encryption?

4.4

Merkle–Damgård construction requires a one-way compression function and the common way is to use a block cipher. If you initiate with the simple way;
$$d^i = f_{MD4}(d^{i−1}, m^i)$$ then the message is the key.
Now, consider that we want to find a collision. Take an arbitrary $h$ as the output of the hash function, take two arbitrary but different message blocks $m^2_1$ and $m^2_2$, and decrypts the $h$ for each;
$$ m_1^1 = f_{MD4}^{-1}(h, m_1^2)$$
$$ m_2^1 = f_{MD4}^{-1}(h, m_2^2)$$
Since we used a block-cipher and that is a permutation and each key is select a different permutation from all possible permutations we expect that $m_1^1 \neq m_2^1$ with high probability. Then we find two inputs that have the same hash value. Note that we can find meaningful messages with this approach. If the $m_1^1 = m_2^1$ the choose another $h$ value to begin.

4.5

$$d^i = d^{i−1} + f_{MD4}(d^{i−1}, m^i) \bmod 2^{128}$$
This is the Davies-Mayer construction and its security is proven under the ideal cipher model. SHA-1 and SHA-2 are using this construction.
This construction has a problem with the block cipher, too that one can find a fixed point; that is $h = E(h,m)$ by setting $h=0$. There is no practical attack on this, though.
Block ciphers can have related keys that don't make a problem during the encryption since we are expected to select uniformly random keys. In the hash function, though, this makes a problem and therefore we use a special block cipher for those like SHACAL-1 for SHA-1 and SHACAL-2 for SHA-2 series.

Ideal-cipher model: Consider the set $\mathcal{B}$ as all possible $k$-bit key and $n$-bit block-sized block-ciphers. Then, in the Ideal-cipher model, a block-cipher $E \stackrel{R}{\leftarrow}\mathcal{B}$ is being chosen uniformly from $\mathcal{B}$. For each key, there are $2^n!$ permutations. Each key defines a permutation therefore there are ${2^n!}^{2^k}$ possible block ciphers. When we instantiate our black box, it becomes some particular block-cipher. Consider the AES-128 is one choose from $2^{2^263}$ that one can choose. Note that in 2005 Black showed that "a blockcipher-based hash function that is provably-secure in the ideal-cipher model but trivially insecure when instantiated by any blockcipher".


What do the security definitions of SHA-3 mean, quantitatively?

Aleph's comment and pointer to the Keccak reference goes a very long way to answering this question (p. 9):

The key words here are "workload equivalent to $N$ calls to $\mathrm{Keccak-}f[r + c]$ or its inverse."  Invocations of the Keccak permutation are being used as the unit of time.  Your intuitive take that it's hash function invocations isn't very far off from this, but note that a single SHA-3 call may result in one or more permutation calls, so Claim 1 is more stringent.

In a more abstract setting, where we're talking about the sponge construction in general and not a concrete implementation like Keccak, we talk about the permutation (and its inverse) as an oracle that the adversary can freely call (often people say "query") as they see fit.  Then the security of the construction is expressed in terms of how many queries the adversary makes.  The oracle calls are treated as outputting the result of a random permutation in constant time.

See also: the Keccak team's more generic treatment of sponge functions.


What are the separate single DES keys from a triple DES key?

The single DES keys are commonly just split in three keys, where the first key is used for the first encryption of the message block itself, the second one for the decryption of the previous result and the third one for encryption of the decryption result.

So basically you'd have: $\newcommand{Enc}{\operatorname{Enc}}\newcommand{Dec}{\operatorname{Dec}}$

$$\Enc'_{(k_1, k_2, k_3)} \equiv \Enc_{k_3}(\Dec_{k_2}(\Enc_{k_1}(m)))$$

and of course

$$\Dec'_{(k_1, k_2, k_3)} \equiv \Dec_{k_1}(\Enc_{k_2}(\Dec_{k_3}(m)))$$

where $\Enc'$ and $\Dec'$ are the encryption and decryption operations of TDEA, commonly called triple DES or DES EDE after the order of encryption / decryption. Note that of course the inner functions are performed first, i.e. the functions are executed from right to left.

In pseudo code the encryption function:

c1 = DES_encrypt(k1, m)
c2 = DES_decrypt(k2, c1)
c3 = DES_encrypt(k3, c2)
c = c3;

The keys are defined as separate keys, but most - if not all - libraries simply take the concatenation $k = k_1 \| k_2 \| k_3$ as key input.

So in your case your keys would be k1 = 0123456789ABCDEF, k2 = FEDCBA9876543210 and k3 = 89ABCDEF01234567 (which have the parity bits correctly set).

Most if not all libraries only accept the keys including parity bits. Most libraries do not check the validity of the parity bit, but there may be some that do. The bits commonly do need to be present though; a single DES key can usually not be represented by just 7 bytes.

Note that the least significant bit of a byte is the parity bit over that byte, which should be odd number of set (or indeed unset) bits in the byte.  So both 00 and 01 would be equivalent byte values within the key, with 01 having correct parity. This means that each triple DES key with correct parity has $2 ^ {192 / 8} - 1 = 2^{24} - 1 = 16,777,215$ fully equivalent keys.

Sometimes key generators do act on the effective key size excluding parity bits, so you'd have a function such as $k = \operatorname{Gen}(168)$ to create a triple DES key rather than $k = \operatorname{Gen}(192)$, even though the output is 192 bits / 24 bytes in size.

For 2-key triple DES keys you'd have $k_3 = k_1$, so the key would be $k = k_1 \| k_2$ to get:

$$\Enc'_{(k_1, k_2)} \equiv \Enc_{k_1}(\Dec_{k_2}(\Enc_{k_1}(m)))$$

and to simulate single DES where only triple DES is available:

$$\Enc'_{k} \equiv \Enc_{k}(\Dec_{k}(\Enc_{k}(m)))$$

I'll spare you the decryption functions and pseudo code.

Neither 2 key triple DES or single DES is considered secure anymore, while triple DES still offers some security.

Sometimes the keys are lettered instead of numbered, in that case $k_A = k_1$, $k_B = k_2$ and $k_C = k_3$. So the concatenation of three keys is sometimes also called an ABC key, and the concatenation of two keys an ABA key.

If you don't want to deal with all this "complexity" then use AES instead, which has much better properties and speed compared to triple DES. A fast stream cipher such as ChaCha20 could also be considered.


RSA-4096 vs AES-256 for secure chat application?

RSA and AES do not oppose, and often are rightly used together in hybrid encryption. RSA can do things that AES can not, like allowing encryption to designated recipients, or allowing anyone to check that a message is not altered or from a different person than is apparent. Using AES or other form of symmetric encryption is a must when encrypting more than few hundred characters.

To choose a cryptosystem, you must first define your goals. Secure chat is not nearly precise enough. Confidentiality? Integrity? Proof of origin? Central registry of participants? How is registration and loss of keys handled?


Security implications of not concatenating a 1 to the IV when using GCM

If the counter mode started at $\text{Nonce}\mathbin\|0^{32}$ instead of at $\text{Nonce}\mathbin\|0^{31}\mathbin\|1$ then one could submit an encryption query for $(0^{96},0^{128})$, i.e. the 128-bit all-zero plaintext along with the all-zero nonce. The first block of the ciphertext would then be computed as $E_K(0^{128})\oplus 0^{128}=E_K(0^{128})$ which is just the global GHash key $H$ and the blinding value for the $0^{96}$ nonce.

If you have both of these values, and the latter one is leaked through a similar strategy for each nonce value, you can do arbitrary modifications of the ciphertext, which directly propagate into the plaintext through counter-mode's homomorphic property, and fully recompute the authentication tag yourself and submit that to your decryption oracle, which will accept the tag and return a valid decryption 100% of the time which completely breaks all security notions that try to ensure some form of integrity (e.g. CCA-security, INT-PTXT, INT-CTXT, AE, ...).

And even if you specifically disallow $0^{96}$ as a nonce, you still get the blinding value which allows you to recover $H$ at least for single-block messages given that the tag is $((c_1\cdot H)\oplus (\operatorname{len}(A)\mathbin\|\operatorname{len}(C)))\cdot H\oplus E_K(\text{Nonce}\|0^{32})=c_1\cdot H^2\oplus (\operatorname{len}(A)\mathbin\|\operatorname{len}(C))\cdot H\oplus E_K(\text{Nonce}\|0^{32})=\tau$ which is a quadratic equation in one unknown over a field which is solvable using the standard equation and a square-root computing method.


I don't think there are any. In principle key sizes can be of any bit length, although usually libraries require modulus a multiple of 8 bits and full powers of two are most common. So creating test vectors for all is not really an option.

The NIST test vectors for decryption just list 1024 and 2048 bits and the modular exponentiation primitive for PKCS#1 signature generation is just 2048 bits modulus. But that should be OK; there aren't any differences when it comes to 4096 bits. It's unlikely that your big number implementation behaves any differently. If you want to test against other bit sizes I would propose you generate them from another library instead.

If you use OAEP or PSS then I would strongly recommend that you test the MGF1 separately, using a different library as reference. There are some tricky size based calculations that need to be performed here and it is a good idea to test them well. Testing your I2OSP and OS2IP might be a good idea as well.

The vectors that are out there can be found here.


Homomorphic Encryption for Deep Learning

There are very few (somewhat practical) results about homomorphic deep learning currently. As a good starting point, you might want to have a look at this recent paper from my former colleagues, and references therein. It focuses on optimizing lattice-based somewhat homomorphic encryption schemes, for evaluating deep neural networks.


Password Entropy in bits for passwords of a certain structure

Is my caculation and conclusion (S~40) correct?

Yes, but it's important to state the premises behind these calculations and not relegate them to a footnote.  Namely, that each character in the password is selected uniformly at random, independently of every other one.  We routinely see people talk about password "entropy" in contexts where passwords are evidently not being selected randomly.  And in such contexts your calculation doesn't tell you anything about the password's security.

Keep in mind also that overwhelmingly most people don't select passwords randomly.  These numbers apply in circumstances that are, in real life, exceptional.

  If so; is there a more efficient way of working out equation (b)?

Yes, by using the laws of logarithms, which allow you to work it out by adding small numbers instead of multiplying huge ones:

$$
\log(n \times m) = \log(n) + \log(m)
$$

This is why entropy is normally expressed in bits—the base 2 logarithm of the number of equiprobable alternatives—because it just makes the math much easier.  In this case:

The uniform random choice of one character out of a set of 26 is $\log_2(26) \approx 4.7$ bits.
The uniform random choice of one character out of a set of 10 is $\log_2(10) \approx 3.3$ bits.
The entropy of a sequence of independent random choices is the sum of their individual entropies.

Therefore, a randomly generated eight letter password has entropy of about $8 \times 4.7 = 37.6$ bits, and one randomly generated according to your latter schema has approximately $5 \times 4.7 + 5 \times 3.3 = 5 \times 8 = 40$ bits of entropy.

Addressing this comment:

  @CodesInChaos your comment seems to imply that the order of certain character sets doesn't seem to matter when calculating entropy. I was wary of making this assumption myself when facing potential solutions to this problem.

If the order is predetermined then it doesn't matter, because then there's no choice about the order, therefore no uncertainty.  Another way of looking at this is that there's a bijective function between the set of passwords that look like ABCDE12345 and A1B2C3D4E5, so therefore the uniform random choice of an element out of one set must have the same entropy as from the other.  (The entropy is the base 2 logarithm of the number of alternatives in the uniform case, and in both cases the total number of alternatives is the same.)


What is the fastest block cipher in the (Intel) world?

The fastest block cipher is identity, which leaves input blocks completely unchanged. This is infinitely fast on all platforms; however, it is not secure. So maybe you want the fastest block cipher that still offers some given non-trivial level of security?

Then it depends a lot on what you want to implement the block cipher on. With recent PC, you would have a hard time getting anything faster than AES, because of specialized opcodes -- although you could define a block cipher that is identical to AES except that it has 9 rounds instead of 10. That alternate block cipher would be faster and still secure, but with less "security margin", an intuitive but very poorly defined notion.

During the AES competition, Rijndael was outperformed on some platforms, e.g. on the PC of that day, RC6 was faster. But Rijndael offered the most consistent performance on platforms of that era: there was no software platform (including 8-bit CPU) were it was abysmally slow, and it was perceived to be reasonably hardware-friendly (contrary to, say, RC6).


Is it theoretically possible for the output of SHAKE to be an infinite concatenation of the same 512-bit block?

Minor correction: SHAKE generates either 1088 or 1344 bits per squeeze; not 512.  So, the example you give will give a repeating pattern, but it'd be either 3264 or 4032 bits long, not 512.

Other than that, yes, that is possible, as far as we know.  In fact, a far more likely repeat is:

$$\operatorname{Keccak-}f(A||X) = A||X$$

This would give a repeating pattern of 1088 or 1344 bits long.

In addition, not only is this possible, there's a good likelihood that there actually is such a $A || X$ pattern.  Such a $A || X$ is known as a fixed point of the permutation; a random permutation has at least one fixed point with probability approximately $1 - 1/e \approx 0.6321$; assuming that $\operatorname{Keccak-}f$ does, in fact, act like a random permutation, then it's more likely than not that there is such a fixed point.


Solving a 256-bit discrete log is absolutely doable, and quite quickly, these days; there are public tools that can do it, though they may require some expertise to use.

On that note, even a 1024-bit modulus is not particularly conservative: it is generally agreed that well-funded organizations today could break logs of that size as well, but at a very large cost. The current minimum recommended modulus size for RSA, Diffie-Hellman, SRP, etc is 2048 bits.

That being said, I would also put my money on a client or server-side break-in before arriving at the conclusion that the log was being broken.


TLS 1.3: the key_share in a ClientHello after a HelloRetryRequest

Yes. When the client sends a new ClientHello after a HelloRetryRequest, it replaces the old KeyShare with the one the server requested in the HelloRetryRequest. This is according to my interpretation for the following text in the TLS 1.3 draft 21 here:

  the new ClientHello, the client MUST    replace the original
  "key_share" extension with one containing only a    new KeyShareEntry
  for the group indicated in the selected_group field    of the
  triggering HelloRetryRequest.

If you have any comments to confirm or correct me, please post before I accept my answer.


What does a linear function with huge order mean?

TL;DR Skip to the bottom for update.
As is well known, the mapping $$L:\{0,1\}^n\rightarrow \{0,1\}^n,$$ of a primitive LFSR on $n$ bits has a single very long cycle of length $2^n-1,$ and a cycle of length $1$ (which maps zero to zero).
As a permutation, this mapping has huge order, i.e., the for almost all the state space the smallest $k,$ such that the $k-$fold composition of $L$ gives the identity map is $k=2^{n}-1:$ $$L^{k}(\cdot)=L(L(\cdots(L(\cdot)))).$$
A randomly chosen permutation on $\{0,1\}^n$ has at least one fixed point with probability $(1-e^{-1})$, and considered as a state mapping, it has a lot of short cycles.
The expected number of fixed points of a random permutation is actually 1, but that is not so relevant, the relevance is the relatively large number of small cycles.
In fact the fraction of permutations with no cycles of length $k$ or less is
$e^{-H_k}$ where $H_k=1+2+\cdots+k$ is the Harmonic number. You can use the approximation $H_k \approx\ln k$ to obtain some rough estimates.
Also see this answer on mathoverflow  for some details. This is not desirable here and the permutation must be carefully chosen.
Edit: For more concrete results see the paper by Odlyzko-Flajolet here where for example, it is proved that the expected "rho length" i.e., initial segment followed by a closed cycle from a random starting point in the state space is $O(\sqrt{N}),$ for a permutation on $N$ points (Theorem 7).
Now compare with the $O(N)$ cycle length in the primitive LFSR example with $N=2^n.$


What is the most efficient lattice problem solving algorithm?

What you want is probably a lattice reduction algorithm.

Lattice cryptography usually relies on the Closest Vector Problem (CVP) or the Shortest Vector Problem (SVP). Solving these involves the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, or LLL. This algorithm is the quintessential lattice reduction algorithm, and is probably what you are looking for. This algorithm is used internally by other algorithms, such as Babai's nearest plane algorithm for CVP.

Note that the LLL algorithm is not able to reduce lattices in higher dimensions, which is the case with practical lattice cryptography. Instead, different algorithms are required, such as BKZ 2.0 for NTRU. However for the purpose of learning about lattice reductions, understanding LLL should be sufficient.


McEliece variants that support signatures

There is a variant of the Neiderreiter system by Courtois, Finiasz, and Sendrier found in their paper: "How to achieve a McEliece-based Digital Signature Scheme" from Asiacrypt 2001. The Wikipedia article on the Neiderreiter Cryptosystem provides a brief introduction to this signature. There is an element of trial and error in the signing process that is cumbersome but it should work for all message hashes.


What's the safest TrueCrypt algorithm and hash?

All ciphers offered by TrueCrypt (e.g. AES, Serpent, Twofish) are "impossible to break" to the best of current public knowledge. Which one of them will be successfully attacked first (if at all) is obviously unknown at this time, hence a matter of personal belief. The same applies to hash functions (SHA512, Whirlpool, RIPEMD160) — there are no relevant weaknesses known in any of them. The standard choice would be AES combined with SHA512.


Can you help me to understand the mode XCBC of authenticated-encryption?

Wikipedia states that key whitening increases security:

In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key.
The most common form of key whitening is xor-encrypt-xor -- using a simple XOR before the first round and after the last round of encryption.
The first block cipher to use a form of key whitening is DES-X, which simply uses two extra 64-bit keys for whitening, beyond the normal 56-bit key of DES. This is intended to increase the complexity of a brute force attack, increasing the effective size of the key without major changes in the algorithm. DES-X's inventor, Ron Rivest, named the technique whitening.
In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key (most commonly using a simple XOR) before the first round and after the last round of encryption.

The "post-whitening" consists into applying the whitening after the encryption function: encrypt-xor.


Difference between a circuit and a normal function

A circuit is a representation of a (computable) function. There are many other ways to represent a function (mathematical notation, Turing machines, pseudo-code, etc.), but for some purposes it happens that circuits are the most convenient one.


Are there any signature schemes that protect against collusion by multiple parties?

No, this is not a security feature provided by asymmetric signature schemes, the way the concept is usually understood.

You have Alice's public key. Typically, you got it in a certificate issued by Carol. Let's assume (for the sake of argument) that Carol has a very strict certificate issuance policy, and only issues certificates corresponding to hardware devices with 100% reliable biometric identification mechanisms. Hence, when you receive a signature that verifies OK with Alice's public key, you can be sure Alice was present when the signature was generated. However, the signature doesn't tell you whether Alice was on the phone with Bob when the signature was generated.

If you want a signature to proves that the signer had no out of band communication with anyone at the time of the signature generation, you must make sure that the private key is stored and used in such way that no such communication would have been physically possible. Say, Carol has a policy only to issue certificates of the kind you require for hardware that consists in a remotely monitored Faraday cage that only fits a single person.


Why does Openssh use only SHA1 for signing and verifying of digital signatures?

Because the RFC says so.

  Signing and verifying using this key format is done according to the
    Digital Signature Standard [FIPS-186-2] using the SHA-1 hash
    [FIPS-180-2].

It says the same for RSA half a page down.

Apparently the signature algorithm is a defined part of the public key method's specification, rather than being negotiated separately like the MAC algorithm is.

At a guess, SHA-1 was considered good enough at the time SSH 2 was being written almost a decade ago (the RFCs were published in 2006), and no one wants to bother changing it now.

Notice that ECDSA keys, published in RFC 5656 in 2009, use SHA-2:

  Signing and verifying is done using the Elliptic Curve Digital
     Signature Algorithm (ECDSA).  ECDSA is specified in [SEC1].  The
     message hashing algorithm MUST be from the SHA2 family of hash
     functions [FIPS-180-3] and is chosen according to the curve size as
     specified in Section 6.2.1.

You can see it in action in ssh_ecdsa_sign() in ssh-ecdsa.c and key_ec_nid_to_hash_alg() in key.c.

(I'm not an expert on SSH, so please take this answer with a grain of salt.)


Is there a password hash function with a human component?

Answer: No.

Reason: Useless.

Explanation:

Not necessarily perfectly reproducible as crowds of people may give different output. So you will end up introducing some degree of tolerance.
Once introducing that degree of tolerance, pattern recognition algorithms will be able to automate that and possibly even achieve a higher accuracy than the humans.
NSA will hire many cheap labour agents and manage to get them work for you and cause your hashes to be insecure. NSA is rich, they can hire many of such cheap labour. How can you ensure that the many humans that are solving hashes for you are actually honest people that are not NSA agents?

My opinion: you are trying to solve an existing problem (so the problem actually exists). It's just that your proposed solution is not going to solve the problem. Instead, I even think it will worsen the situation. You seem to be over estimating the uniqueness humans have. Humans are not that unpredictable. Some human-only problems are considered solved by pattern recognitions algorithms. I also think that humans are more predictable than PRNGs. So why not incorporate a seeded PRNG into your hashing function instead? Such seeded PRNGs are less predictable than humans aver all.


No, there is no reason that $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk},\alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$ would be $\alpha\cdot\alpha^{-1}$, including when we spread $\bmod N$ or $\bmod N^2$ here and there.

What does apply is: for overwhelmingly most $\alpha$ and $k$ in $\Bbb Z$, it holds that $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk}, \alpha)^k\bmod N^2)=k\cdot\alpha\bmod N$. We could take $k=\alpha^{-1}\bmod N$ and get $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\textsf{pk},\alpha)^{(\alpha^{-1}\bmod N)}\bmod N^2)=1$, but that's not useful anyway, since $\alpha^{-1}\bmod N$ reveals $\alpha\bmod N$.

Criticism of the question:

It is not defined in which group it is computed $\alpha^{-1}$, and that matters.
$\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk}, \alpha) \cdot \textsf{Enc}(\textsf{pk}, \alpha^{-1}))$ will be $\alpha+\alpha^{-1}\bmod N$, which may or may not be $\alpha+\alpha^{-1}$.


How is HMAC(message,key) more secure than Hash(key1+message+key2)

The construction you are proposing is called the "envelope" or "sandwich" MAC, it predates HMAC, and it is in fact secure—provided the key and message are appropriately padded. That is,

$$
\text{SHA256}(k \parallel m \parallel 1 \parallel 0^{b - 1 - (|m| \bmod b)} \parallel k)
$$

is secure, as long as $k$ is the underlying hash function's block length $b$ ($b = 512$ in the case of SHA256), or is padded to that effect. Note that the padding after the message is crucial: without making sure the second key is in its own block the security of the envelope MAC is lower than that of HMAC. This was proved by Yasuda, and later Koblitz and Menezes (§6) argue that there is no sound theoretical reason to prefer HMAC over (correctly padded) envelope-MAC, beyond the former's more established nature.


Note that re-encrypting the output of CBC-MAC with the same key as it was calculated with is equivalent to appending a single all-zero cipher block to the message:
$$E_K(\text{CBC-MAC}_K(m)) = E_K(\text{CBC-MAC}_K(m) \oplus 0^b) = \text{CBC-MAC}_K(m \,\|\, 0^b),$$
where $0^b$ represents a $b$-bit block of all zero bits and $b$ is the block size of the cipher.

Thus, the classic attack on unmodified CBC-MAC with variable-length messages can be easily adapted to your scheme.  Specifically, let $$\begin{aligned} t\phantom{'} &= E_K(\text{CBC-MAC}_K(m)), \\ t' &= E_K(\text{CBC-MAC}_K(m')), \end{aligned}$$ and construct the message $m'' = m \,\|\, 0^b \,\|\, (t \oplus m')$, where $t \oplus m'$ represents $m'$ modified by XORing its first block with $t$.  Then $$E_K(\text{CBC-MAC}_K(m'')) = E_K(\text{CBC-MAC}_K(m')) = t'.$$


Is it secure to concatenate two 16-bit random numbers into a 32-bit one?

The Intel post which I think you mean was discussed in this question and as I wrote there, the limitation only applies in the case of trying to combine PRNG outputs into values larger than the seed entropy (two 256-bit values in their case). Also mentioned there: cryptographic mixing does not increase the entropy you have, so if concatenation is insecure, just mixing is as well.

So, whether you can concatenate two 16-bit values depends on how the library/hardware works:

If you are getting raw noise readings it is unlikely it has 16 bits of entropy per value. You would need to collect many and mix them into a single value if you wanted truly random values. And you would need to find out what sort of correlations the data has to determine the entropy rate.
More likely, there is already some mixing/whitening going on that tries to assure full entropy for the output values. If that is the case, you can combine them just fine.
If the library uses a PRNG to generate more output values than the input entropy from the hardware you again cannot combine two values and retain full entropy.


Item (2) is not part of the definition of a standard CSPRNG. If you look at where this definition was taken from in Wikipedia, this item refers to a "forward secure CSPRNG". So, this is a definition of forward security and not the standard notion.

Also, the next-bit test is one way of defining, but certainly not the only way.

In any case, it is easy to construct a CSPRNG that is not forward secure; simply always store the initial state.


Can CBC-encrypted files be modified in-place?

If you could use the same IV, then yes, you would need to rewrite everything after the modified block.

But you shouldn't do that; every time the contents change, you should generate a new IV, which would require the whole file to be rewritten. Otherwise an attacker can learn more information than it should about how the file changed (precisely by checking which blocks of the file have changed).


Not provably. Maybe, since it's not a permutation, but you couldn't verify it practically.

Just use all-zeroes: it's easily recognizable as a null value, and thanks to pre-image resistance, no-one knows what hashes to that.


How to save the data in a non-trustworthy db, so the next time I read from the db, I know that I've read actual and not an old version of the data?

I'm not a professional cryptographer, but you don't seem to be asking a cryptography question. Set aside the encryption part for a second, and I think you're asking for something impossible.

The two parties in your example are only communicating over the storage system.
The only way they are alerted to new versions is by checking the storage system.
And yet, you also say that the storage system is unreliable, or can be hacked.

In that case literally anything can happen.

Even if both parties "remembered" the last versions they saw, either one of them could change the state of the system, do something bad, and then flip it back to an earlier state before the other one noticed. Or, a third party could do the same and fool both of them.

If you had one secure channel, you could use it to prove some things about an insecure channel. But in your example that doesn't exist.


FIPS 140-2 compliance and RSA encryption

There's a difference between FIPS approved and FIPS allowed algorithms.  RSA is an allowed algorithm for doing key wrap and key transport, however it's not FIPS approved for that purpose.  It's only approved for digital signatures.
If you're using a FIPS validated module take a look at the security policy for the module you're using and see if RSA is allowed or not for key wrap or key transport.  It must be documented there.  If it's not then you can't use it (and claim compliance) even if it's available in the module.
And no, there are no approved generic asymmetric encryption algorithms, they're only approved for digital signatures.


SpongeWrap without padding and frame bit

Is it necessary to pad every input (not just last) to sponge for authenticated encryption to be secure?

Yes. The purpose of the padding is to make every possible input unique. So a full block must result in a different bitstring than any padded non-full block. There is no way to pad only the incomplete block and still have it differ from all the full blocks.

If you didn't use such padding, two different messages could lead to an equal state.

  What is purpose of frame bit in SpongeWrap?

The purpose of the frame bit is domain separation. To quote the pdf (4.1.5):

  The duplex (or equivalently, sponge) inputs to generate key stream blocks and those to generate tag blocks are in separate domains. Every duplex response that is used to encipher the next block has as input a string ending with a frame bit 1, whereas every duplex response that is used to form a tag has as input a string ending with a frame bit 0.

If this wasn't the case, the authentication tag and the "next block" keystream could be equal. This would allow an attack where you truncate the message and forge an authentication tag from the ciphertext, if you know the plaintext of the last block of the message. Because of the frame bit they are independent, so the ciphertext cannot help you with forgeries.


First contact when using Public-key cryptography?

You're asking for techniques to establish trust in a public key upon first connection. There are three major approaches to this problem:

Out-of-band-verification. This generally relates to methods which use methods which don't go over the current communication channel to verify a public key.

Pinning. If you use pinning, you hard-code your public key (or a hash thereof) somewehere (for example in your app) and then validate that the pin matches the public key. This is also done in browsers, for example Chrome pins the Google certificates. Also there are ways for webservers to signalise that they want their current public key pinned (HPKP).
Physical verification. In this scenario you likely want to confirm the public key associated to some physical entity so you go to that person, verify their identity and then associate the public key they claim to belong to them (in person) with them.
Other channels. In this scenario you generic "other channels" for your verification. For example if you want to exchange PGP keys, you confirm the hash of the key over Twitter or your favorite messaging app.

Certificate Authorities (CAs). This is the approach where one (or a set of) entity(-ies) certifies a public key to belong to a specific entity (eg a person). The signing keys  of the CA(s) are verified out of band (as per 1).

SSL PKI. For the web, the summary basically describes what is done.
DANE. DANE means that you put your public key (or a hash thereof) in the DNS so it can be confirmed "out-of-band" that way. This is placed under "CAs" because the DNS itself is secured by DNSSEC which has a strict CA hierarchie.

Web-of-Trust (WoT). In this scenario everybody becomes a CA basically and certifies other people's key depending on the verification they have reached out-of-band. This allows you to traverse the graph that the WoT forms and find a path from you to the new public key, maybe because two of your friends already have seen and verified said public key.

PGP WoT. The above is basically how the PGP WoT works.
Notary-like Approaches. This is a slightly different approach but is also based on the idea of "many CAs". Basically you have a set of (more or less trusted) notaries and each time you encounter a new website you ask them what public key they see. If these match what you see you have some confidence that your key is good if not, you know you're attacked.

Trust-On-First-Use. This approach is the most straightforward one. Assume the first connection is ok and keep the public key or a hash for verification against later connections. Obviously this doesn't solve your problem.


Does the Balloon hashing paper deprecate Argon2?

Does the recent Balloon hashing paper and the included attack on
  Argon2 effectively negate the result of the Password Hashing
  Competition?

No.
The main result of the PHC was not a single new fancy password hashing function (i.e. Argon2), but a massive advancement in the research of password hashing. We understand password hashing and how to do it much better after the competition than we did before it. That's the most important and main result.
Examples of this include new security reductions for time-memory trade-offs (Catena) and completely new ideas like workload delegation (Makwa).

Now for the actual attack. It appears that the attack reduces the time-memory product of one- and two-pass Argon2i (as of v1.2.1) by a factor of 5 (or less). While this is certainly not good, it doesn't completely destroy Argon2i either. So you can still use it, but have to keep in mind that there may be trade-offs against it.

Now for the mitigations:

After this very paper was released, there was an update to the Argon2 specification, adding the paragraph 5.2 to the security analysis, they documented the TL;DR of the attack and how they mitigated it in version 1.3. With Argon2 v1.3 you only need to avoid single-pass Argon2i, with two-passes and more the attack shouldn't apply anymore.
The idea of Argon2i originally was to allow for data-independent memory-hard password hashing, especially to avoid side-channel attacks like cache-timing attacks. However, if your threat model doesn't include attackers sitting on your machine while you're doing the password hashing, you should use Argon2d anyways, which uses data-dependent operations (similar to scrypt) and is not affected by these recent attacks.
The last mitigation of course is to use other password hashing functions. Either the special recognitions from PHC (i.e. Lyra2, Catena, yescrypt and Makwa) or the good old ones like scrypt and bcrypt. Of course you should note that while the old ones have probably seen more scrutiny, they have their own respective weaknesses (e.g. bcrypt doesn't help much against FPGAs and scrypt also has some weaknesses and doesn't protect against side-channel attacks too well either).

In the comments to the question were also two other papers mentioned. "Efficiently Computing Data-Independent Memory-Hard Functions" by Alwen and Blocki which provides asymptotic bounds on the time-memory-product for a variety of password hashing constructs (including Argon2i, Catena and Balloon Hashing).
The other paper mentioned, "Towards Practical Attacks on Argon2i and Balloon Hashing" by Alwen and Blocki improves on the result of the previous paper, focusing on the old and the new Argon2i version and on Balloon Hashing, again reporting successful (conretely instantiated) attacks on both schemes and noting that 10 passes would be required to regain (full) security for Argon2i.

TL;DR: Use Argon2d if you don't mind with side-channel attacks and use high-pass-counted (e.g. 10 passes) Argon2i if you do mind.


The difference between being not strongly collision resistant, and not weakly collision resistant?

I prefer using definitions that explicitly specify who does what.

Weak collision resistance: After Bob creates some message x1, it is "computationally infeasible" for an attacker Mallory to compute some other message x2 such that h(x1) == h(x2).

Strong collision resistance: It is "computationally infeasible" for an attacker Mallory to find any two messages x1 and x2 such that h(x1) == h(x2).

The negations would be:

Weak collision vulnerability: After Bob creates some message x1, it is "computationally feasible" for an attacker Mallory find a bound collision -- to compute some other message x2 such that h(x1) == h(x2).

Strong collision vulnerability: It is "computationally feasible" for an attacker Mallory to find a free collision -- to find any two messages x1 and x2 such that h(x1) == h(x2).

Specific examples:

The "XOR checksum" (and each non-cryptographic hashe in general) is weak collision vulnerable -- and therefore is strong collision vulnerable.
The MD5 hash is now known to be strong collision vulnerable, but (as far as we know) it still has weak collision resistance.
The SHA3 hash (as far as we know) has strong collision resistance -- and therefore also has weak collision resistance.

Strong collision resistance implies weak collision resistance, in the random oracle model,
as Vijay Ganesh points out in
"Cryptographic Hash Functions".
(Vijay apparently thinks the term "infeasible" is useful in this context).

Klaus Schmeh apparently made up the "bound collision" and "free collision" terminology for the book "Cryptography and Public Key Infrastructure on the Internet".

Therefore,
weak collision vulnerability implies strong collision vulnerability, in the same model.

One might argue that strong collision vulnerability implies weak collision vulnerability:
After Mallory creates two messages x1 and x2 that collide,
it is theoretically possible that Bob might create a message exactly the same as x1, and then Mallory could easily remember the x2 message that Mallory generated earlier.
In practice, any protocol where Mallory influences Bob into using a message generated by Mallory (a chosen-plaintext attack) is already considered broken in other ways.
In practice, we assume that, without such influence, the probability that Bob coincidentally picks such a message generated by Mallory is negligible.

I suspect otus is alluding to the fact that people who work with keyed hash functions have their own definitions for these terms that are incompatible with the definitions used by people who work with unkeyed hash functions.
Shoichi HIROSE mentions this conflicting terminology in the introduction of his 2005 paper "Weak Security Notions of Cryptographic Unkeyed Hash Functions and their Amplifiability".


What happens when i sign a public key with its private key pair?

Signing the public key is safe.

The general assumption is that the adversary is allowed to ask any message that he knows to be signed, and that operation must not leak information about the private key (or otherwise generate a signature for a message that was not signed by the legitimate signer).

In this model, the adversary knows the public key (it's assumed to be public, after all), and he can submit that as something to be signed.  Hence, if that signature leaks anything untoward, that shows that the signature algorithm is broken.

In practice, it can be seen not to matter; for any signature operation I've seen, you first hash the message to be signed (and perform the signature operation on the hash); this hashing operation would muck up any relation between the message and the public key, even if that were any issue.


Why are 48 bytes appended to Libsodium encrypted messages if nonce is 24 bits?

Notice that $\operatorname{secretbox}$ has a $16$-byte MAC too. For reference, I've included $\operatorname{box}$ too.

$$
\operatorname{secretbox} : \text{24 nonce} + \text{0 xsalsa} + \text{16 poly1305}\\
\operatorname{box} : \text{32 curve25519} + \text{24 nonce} + \text{0 xsalsa} + \text{16 poly1305}
$$

However, the nonce is user-controlled and normally not included in the ciphertext overhead as it is usually never sent, often a protocol-level counter.

You say "secret box" but you mean the normal "box" which uses a public key. Your ciphertext is expanded with your $32$-byte ephemeral public key and the $16$-byte MAC.


With AES encryption and a known key and plaintext, can an attacker create a different key and plaintext resulting in the same ciphertext?

For basic AES, it is easy to find two keys in this way. Take any $key1$ and $plaintext1$ and compute $c=AES_{key1}(plaintext1)$. Then, take any $key2$ and compute $plaintext2 = AES^{-1}_{key2}(c)$. It follows that $AES_{key1}(plaintext1) = AES_{key2}(plaintext2)$. Having said this, if AES is used in an authenticated encryption mode with a MAC, this may not necessarily be possible. I wish to stress that there is no guarantee that not, and such a thing would need to be proven. In particular, if you did the standard encrypt-then-MAC (with different keys), then this would be vulnerable in exactly the same way, since the "encryption" part is unchanged. Bottom line, this should be possible to achieve, but it's certainly not guaranteed, and often doesn't hold at all.


What is the best strategy to avoid getting even orders in Shor's algorithm?

I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.

Not really; to factor, all you need is a value $e$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$); it doesn't matter if $e$ is even or odd.

And Shor's will hand you such an $e$ with quite high probability.

  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?

You can't; or at least, not to any significant extent.  If the attacker gets his hands on such an $e$, then the time taken by the classic-side of Shor's is utterly tiny compared to the Quantum side of things...

  is $N=pq$ --- where $p, q$ are safe primes --- the hardest integer for Shor's algorithm?

In some odd sense, that's the easy case.  If the attacker obtains any $x, e$ pair with $x^e \equiv 1$, $x \not\equiv 1, N-1$ and $e > 0$ and not ridiculously huge, it's straight-forward to factor $N$ with simple algebra.  In contrast, if we select $p, q$ with $\gcd(p-1, q-1)$ large, these simple algebraic methods often don't work; the attacker might have to resort to simple number theoretical attacks (but, as above, other than taking a small amount of additional time, they don't really have a drawback...)


What encryption to choose from the SSL library in python 3?

You may need a 1.2 and 1.3 scheme, so I'd include at least one of both, giving priority to 1.3 as it is the latest / greatest protocol.

Then there is ECDSA and RSA, indicating the certificate based authentication used. ECDSA is more performant for similar security (and you may not even get any certificates above RSA-4096). That may be important if you can choose the certificate type. However, once you've chosen your TLS certificate type, you don't get to choose between the two cipher-suites, and you just include the one that is compatible with your certificate.

If you do Business-to-Business (B2B) then I'd choose TLS 1.3 due to the fast session resumption may achieve.


Which algorithms are used to factorize large integers?

The three main general-purpose algorithms for factorization are the quadratic sieve (QS), the elliptic curve method (ECM) and the number field sieve (NFS).

On Complexity

The running time of these algorithms is expressed with the L-notation: $L_n[a,c]$ means that the asymptotic complexity of factoring a number $n$ is $O(e^{(c+o(1))(\log n)^a(\log \log n)})^{1-a}$. We recognize "$\log n$" as "the size of the number $n$" so the main parameter to look at is the "$a$", but, for a given "$a$", "$c$" must not be neglected. Also, this is an asymptotic complexity, valid when $n$ is "big enough" and there is no telling whether the everyday "$n$" values (e.g. RSA keys) are "big enough" for the expression to be a precise estimate of the actual factorization effort. Last but not least, running time is only about CPU consumption, it does not cover memory usage, and memory is the bottleneck for 1024-bit integers.

Quadratic Sieve

A description of QS can be found in chapter 3 of the Handbook of Applied Cryptography. It is more thoroughly detailed in "A Course in Number Theory and Cryptography", a highly recommendable book for whoever is interested in such subjects (contrary to the Handbook, this one is not free, but it is well worth its price).

The main idea of QS is to try to find two integers which are square roots of the same value modulo $n$. If we consider $n = pq$ (with $p$ and $q$ big primes), then most integers which have a square root modulo $n$ actually have four square roots; this can be seen with the Chinese Remainder Theorem (CRT), which roughly states that when you compute modulo $n$, you are actually computing modulo $p$ and modulo $q$ at the same time. If $z$ is a quadratic residue modulo $n$ (it is the square of some integer modulo $n$), then $z$ is also a quadratic residue modulo $p$ and modulo $q$. Modulo $p$, $z$ has two square roots (if $u$ is a square root of $z$, then so is $-u$), and $z$ also has two square roots modulo $q$, yielding four possible combinations through the CRT. The four square roots of $z$ are $u$, $-u$, $v$ and $-v$ for two values $u$ and $v$.

So if we find $x$ and $y$ such that $x^2 = y^2 \mod n$, then $x$ and $y$ are two square roots of the same value modulo $n$. The bad case is then $x = ±y \mod n$, because this yields no information: this is when $x$ and $y$ are $u$ and $-u$, or $v$ and $-v$. However, there is a 1/2 probability that $x$ and $y$ are $±u$ and $±v$, respectively. At that point, a simple GCD between $n$ and $x+y$ will yield $p$ or $q$.

In QS, we set two bounds $A$ and $B$, and we look for $B$-numbers in a set $S$ of integers. A $B$-number is a number which is $B$-smooth, i.e. such that all its prime divisors are smaller than $B$. The set $S$ consists in the integers $t^2-n$, for values of $t$ which are between $\sqrt{n}$ and $\sqrt{n}+A$. So the values in $S$ are "small" integers which are each equal to the square modulo $n$ of a "bigger" integer.

Suppose that we found two $B$-smooth integers $s_1$ and $s_2$, such that $s_1 = gh^5$ for some small primes $g$ and $h$ (smaller than $B$), and $s_2 = g^3h^3$. Neither is an "obvious square" (i.e. a square in the plain integers, not computing modulo $n$); but $s_1s_2 = g^4h^8$, which is the square of $g^2h^4$ (square in the plain integers, but this then also holds true modulo $n$). However, $s_1$ and $s_2$ are also squares modulo $n$ of some $t_1$ and $t_2$, respectively, so $s_1s_2$ is a square of $t_1t_2$ modulo $n$. This yields two values $x = t_1t_2$ and $y = g^2h^4$ such that $x^2 = y^2 \mod n$, exactly what we were looking for.

The gist of QS is the generalization of this process. We accumulate many $B$-smooth values from $S$, in the hope that we will find a product of such $B$-smooth values where each prime divisor will have an even exponent, because this then yields an "obvious square" which we can equate to a "non-obvious square" obtained from the way the set $S$ was defined.

Finding $B$-smooth integers in the set $S$ involves "sieving", which in this case can be thought of as an offspring of Eratosthenes' Sieve. We "lay out" a sequence of values from $S$, then we "mark" all multiples of $r$ for every prime $r$ smaller than $B$; if one of the values has accumulated enough marks, then it is a product of "many" small primes, and thus a good candidate for being $B$-smooth.

The two parts of the algorithm are thus sieving, which can be distributed over many machines, each looking for $B$-smooth integers in a relatively small range (for big integers, we are still talking about using a few gigabytes of RAM in each machine). Then, all $B$-smooth integers are accumulated in a big matrix: one row per $B$-smooth value $s$, one column per prime $r$ smaller than $B$. The slot at row $s$ and column $r$ is a 1 if the factorization of $s$ includes $r$ with an odd exponent; otherwise, this is a 0. The matrix reduction step tries to find sums of rows (in $\mathbb{Z}_2$) which yield an all-zero row (summing two rows is equivalent to multiplying the corresponding $s$ values, and an all-zero row means that the product will have even exponents for all small primes, hence an obvious square).

The sieving will work in a reasonable time if $B$ is sufficiently big (it is easier to find $B$-numbers if you allow bigger "small primes"). On the other hand, the matrix reduction step will have good probability of finding full relations (products of $s$ values which are obvious squares) only if we have found more than $B$ such $B$-numbers; and the final matrix will have size $B^2$, which can become unbearably huge. So there is a trade-off. It has been proven (given some "reasonable" assumptions) that the optimal choice leads to a running complexity of $L_n[1/2,1]$.

A variant is known as the Multiple Polynomial Quadratic Sieve, in which $S$ may accept other kinds of integer, beyond the "$t^2-n$" format. See the main paper from Silverman.

Factoring with Elliptic Curves

The ECM factorization algorithm relies on the following idea: we compute points on an elliptic curve, using values modulo $n$ as if $n$ was prime (which it is not), fervently hoping that things will go sour at some point: we want to hit a value which is not invertible modulo $n$, because then a simple GCD will yield a non-trivial factor of $n$.

An Elliptic Curve is the set of points $(X,Y)$, where $X$ and $Y$ are from a field, such that a given cubic equation holds, usually $Y^2 = X^3 + aX + b$ for some constants $a$ and $b$. On such a set of points, we can define a group law; this requires a "neutral point", an extra conventional point called "point at infinity" which does not have $X$ and $Y$ coordinates in the field. The EC group law is easily computable, with formulas which imply a division (pay attention, this is the interesting point for ECM): to add point $(X_1,Y_1)$ to point $(X_2,Y_2)$, we must divide some value with $X_2 - X_1$. When we add two points with the same $X$ coordinate but not the same $Y$, we get the point at infinity (which somehow explains its name: we are "dividing by zero").

Since we can add points together, we can define the multiplication of a point by an integer: to multiply $P$ by $f$, we repeatedly add $P$ to itself ($f-1$ times). This can be done efficiently with a double-and-add algorithm. If we work with a finite field, then the curve is a finite group, and this implies that when adding $P$ to itself we necessarily end up with the point at infinity. Actually, any point $P$ has an order, which is an integer $d$ such that $fP$ is the point at infinity whenever $f$ is a multiple of $d$.

Integers modulo $n$ are not a field. However, if $n = pq$, then, when we compute with curve points with coordinates modulo $n$, we are actually computing points over two curves simultaneously: the curve in the field of integers modulo $p$, and the curve in the field of integers modulo $q$. This is what the Chinese Remainder Theorem is all about. So the ECM works like this:

We choose random constants $a$ and $b$ modulo $n$, and a random point on the curve.
We repeatedly multiply that point with integers $r^x$ for small primes $r$, and exponents $x$, such that $r^x$ is no bigger than a given bound $B$.
We hope that at some point we will try to do a division modulo $n$ by a value $X_2-X_1$ which will turn out not to be invertible, at which point we will have won (a GCD of $n$ and that value will yield a non-trivial factor of $n$).

The ECM relies on the hope that the point on the curve modulo $p$ (but not modulo $q$) will have a $B$-smooth order; thus, multiplying by all the $r^x$ will reach modulo $p$ (but not modulo $q$) the point at infinity, i.e. a "division by zero". Since we work modulo $n$, we will notice that division by zero as a case of "inversion modulo $n$ does not work".

The boundary $B$ is configured so that we do not spend too much time on a given curve. If we exhaust all small primes lower than $B$, then we try again with another curve (other random $a$ and $b$ constants).

There are variants which can give a boost to the performance of ECM; see this report for details.

The running complexity on a "balanced" integer (a RSA modulus $n = pq$ where $p$ and $q$ have the same size) is similar to that of the quadratic sieve. However, the complexity of ECM primarily depends on the size of the smallest factor of $n$, not the size of $n$, so this is the algorithm of choice for attacking big "unbalanced" integers (e.g. integers which have not been specially generated as RSA modulus).

Number Field Sieve

The Number Field Sieve is a very complex algorithm which I will not attempt to detail here, if only because I am quite sure that I would not get it right. As an extreme over-simplification, NFS is like QS with polynomials instead of integers everywhere. It relies on quite of lot of number theory. However, it still has the two basic steps:

a sieving step, which can be easily distributed over many machines (each having a hefty but not implausible amount of RAM);
a matrix reduction step, which can not be easily distributed over many machines, and which involves applying a theoretically simple operation (Gauss-Jordan reduction) to a matrix of humongous size.

An extra initialization step is needed to choose the parameters; it is often known as "polynomial selection" and requires quite a lot of thinking and non-negligible CPU work.

The running time of NFS on random integers (known as the General Number Field Sieve) is $L_n[1/3,c]$ for a constant $c = (64/9)^{1/3}$. It is faster than QS and ECM for integers larger than about 350 bits; all factorization records beginning with RSA-130 (430 bits) up to and including the current RSA-768 (768 bits) used GNFS. There is a variant called SNFS (Special Number Field Sieve) which is applicable only to integers which have a special format (and thus not applicable to RSA key cracking), but which has a better complexity ($L_n[1/3,c]$ with $c = (32/9)^{1/3}$, which means that SNFS can potentially factor integers twice bigger than GNFS). SNFS was used to factor a 1024-bit integer which was a divisor of $2^{1039}-1$.

For big integers, the bottleneck in factorization is the matrix reduction step, which requires terabytes of very fast RAM and cannot be easily distributed. Rumor has it that the polynomial selection for a 1024-bit "general" integer factorization has begun, but if the sieving step appears doable (though it will take several years), nobody knows yet how the matrix reduction step will be performed (even accounting for what five or ten years of technological advances will bring us).

Quantum Computers

Shor's algorithm easily factorizes very big integers. Its only drawback is that it works only on a quantum computer, which does not exist (yet).

On Scientific Progress

We may note that QS, ECM and NFS are all algorithms from the 1980s. No new, efficient algorithm has been discovered in the last 20 years. However, many optimizations have been discovered in the meantime, leading to algorithm variants (e.g. MPQS, ECM with "stage 2"...) which are widely faster than their original description, so there has been substantial progress -- but description of this progress requires going into the technical details of each algorithm.


How is a re-encryption done with elGamal?

First, I can't find a copy of the RSA mental poker report, so I cannot say for sure what kind of "commutative encryption" they wanted to use, but one type is the Pohlig-Hellman cipher, where you encrypt a group element $x$ using a key $k$ by computing $x^k$. To decrypt $y$ using the key $k$, you compute $y^{k^{-1}}$, where the inverse is computed modulo the group order.

In this case, what is meant is to use it like in Shamir's three-pass protocol. Alice encrypts using $k_A$. Bob encrypts using $k_B$. Alice decrypts using $k_A$. Bob decrypts using $k_B$.

Second, ElGamal is a public key cryptosystem, so encrypting a ciphertext doesn't immediately make sense. However, as it turns out, it is possible to do something similar with ElGamal.

So Alice has a public key $y = g^a$ and Bob has a public key $z = g^b$.

Alice has encrypted a message $m$ as $(x,w)$ with $x = g^k$ and $w = y^k m$.
Bob reencrypts $(x,w)$ as $(x', w')$ with $x' = x g^u$, $w' = w y^u (x')^b$.
Alice "redecrypts" $(x',w')$ as $(x'',w'')$ with $x'' = x' g^v$, $w'' = w' z^v (x')^{-a}$.
Bob decrypts $(x'',w'')$ as $w'' (x'')^{-b}$.

Note that

$x' = g^{k+u}$ and $w' = y^{k+u} \; m \; z^{k+u};$ and
$x'' = g^{k+u+v}$ and $w'' = y^{k+u} \; m \; z^{k+u+v} y^{-k-u} = m z^{k+u+v}$

so $w'' (x'')^{-b} = m$. Here, $(x,w)$ is an encryption of $m$ under $y$, $(x',w')$ is an encryption of $m$ under $yz$ and $(x'',w'')$ is an encryption of $m$ under $z$.

I suspect that these encryptions may be sufficiently independent to be useful in this context, but there is some proving to be done.


Quantum key exchange skepticism/confusion

Let’s take your questions in order. Note that I’m a physicist working in quantum cryptography, so my opinion on this might be biased
1. What about authentication ?
The classical channel between Alice and Bob has to be authenticated in order for the protocol to work. Formally, this is a pre-requisite for quantum key distribution (QKD), and is not part of the protocol.
In practice, we often uses information theoretically secure schemes (see this answer for pointers), which consume secret keys. The point is to generate key through QKD faster than the authentication consume it, making the whole system a key expansion system.
2. Wait ! Can’t Eve guess half of the basis (filters) without being detected ?
No ! That’s the whole point. Eve does indeed know half of the key, but she’s detected by Alice and Bob. Eve choice and Bob’s choice are independent, so, Eve will have chosen the wrong filter for half of the photons kept by Alice and Bob, and this wrong filter choice would change the photon polarization, inducing errors in Alice and Bob strings (in this case $\tfrac12\times\tfrac12=25\%$ error.) detected in step 5. of your description of the protocol. This lead us to the next question .
3. What is the maximal error rate ? And why ?
An exact answer to this question is still a research subject, and is obviously protocol dependent, but the same ideas (with different numbers) are essentially valid for all protocols.
The attack you proposed is known as an intercept-resend attack, describing an attack where Eve measures the photons and resends something to Bob depending on her measurement. It is proved that there is no way for Alice and Bob to extract a secret key when such an attack occurs, which corresponds to 25% error rate for BB84 protocol. However, this is only an upper bound on the tolerable error rate, and this attack has no reason to be optimal.
To find a lower bound, one uses different techniques to optimize over the sets of attacks, which also depend on the exact way the final key is extracted (after error correction and privacy amplification, in order to use the lefover hash lemma). A commonly used lower bound is $e=11\%$ which corresponds to a case where Eve gather as much mutual information on Alice's string as Bob, but some research papers have some way to tolerate a higher error rate.
4. We always assume Eve is passively oberving ...
NO ! The whole point of QKD is that she cannot passively observe ! Heisenberg uncertainty principle ensures that any observation is active and disturbs the system. Usually, we assume Eve can do anything, but the tricky part is to properly define “anything”, and optimize over this set.
5. How does the leftover hash lemma actually work
I’m a physicist, and I will not give you a theoretical answer on this. You can read the publications of Renato Renner to have a rigorous analysis of this lemma in the presence of a quantum adversary.
On a practical point, Alice and Bob use error correcting codes (ECC) to correct the errors in order to have the same key. Doing that, they leak some information to Eve (at most the number $c$ of exchanged ECC bits, $c≥h(e)$ for BB84). This leakage is added to amount of information which has leaked during the photon exchange, and which can be evaluated from the error rate $e$ (at most $h(e)$ for BB84). Alice and Bob pass their key through a universal hash function, with an output small enough ($<1-c-h(e)$) to ensure the leftover hash lemma applies.
Bonus question (from the comments) : is QKD relevant ?
I’m an academic, and I find it interesting from a fundamental point of view. It clearly changes the way physicist think about quantum mechanics, and is relevant in this aspects.
Whether it will soon be relevant to use QKD now in an industrial setting is a question of engineering, economics, future prediction and beliefs on what the NSA actually does ...
QKD is more difficult to implement than classical cryptography, because it needs specific hardware and has a limited range. However, it is indeed possible today to make QKD systems working over 200km, and small networks exist across a few cities. Some people work to make it practical and cheaper, and they may succeed.
In my opinion, the only reasonable application of QKD today is on securing expensive data which should stay secret for more than a decade (i.e. on an horizon where technological evolution is difficult to predict). The two properties which make QKD useful in this case are :

Its security relies on something completely independent than classical cryptography and it is easy to combine the two such that both have to be broken in order to break the scheme.
In order to break an imperfect implementation of quantum cryptography (aka quantum hacking), one need to break it at the moment where the photon exchange take place. You cannot record the messages in the hope that a weakness in the protocol will later be  found.