Manipulate encrypted file: AES / ECB / PKCS5Padding

A block cipher is a permutation of all possible plaintext blocks and ciphertext blocks. That is: each plaintext block has a corresponding ciphertext block and vice versa. Which one depends on the key and direction of operation (encryption or decryption).

Now ECB just results in a succession of the plaintext blocks converted to ciphertext blocks. There are two things to notice: if a ciphertext block is changed then decryption of that block will always result in a different plaintext block. However, because you don't know the key you don't know which one. So unless you can choose a ciphertext block for which you know (part of) the plaintext, the result will be indistinguishable from random.

If you do know (part of) the plaintext for a ciphertext block then you can use this knowledge to put this plaintext block anywhere in the ciphertext. So you can reshuffle, delete blocks, duplicate blocks and put in blocks for random plaintext as you wish. However, you should always keep to blocks, not individual bytes.

There is only one rule when doing this: the last block should be left alone otherwise the unpadding is likely to fail. You should only replace it with a ciphertext block with correct padding, if at all (you may have received a previous message encrypted using the same key with a known plaintext/padding block that you can reuse).

Note that you require authenticated encryption or encrypt-then-MAC (with MAC'ed or known IV) to avoid the problem of replacing plaintext. Just using CBC or CTR mode - for instance - doesn't protect the plaintext message in any meaningful way.


MAC security and adversaries with memory

Memory of the first round can't help the attacker win the second round.

If it could: the attacker could simulate the first round on his own (picking his own key, pretending to play the game against himself), and then play the second round against the challenger.

So, adversaries like this are not stronger -- not even if they have memory.


Effect of tail cutting and precision of discrete Gaussian sampling on LWE / Ring-LWE security

Tail cutting and precision refer to the problem of distinguishing the actual distribution used in your scheme and the distribution used in the proofs for the scheme. You want to somehow argue that an adversary cannot get any advantage from these two distributions being slightly different.

As you already mentioned, there are currently two more or less widely used approaches in lattice crypto. The traditional way is bounding the statistical distance (SD). Which really computes the difference between two distributions. The second approach is the Renyi divergence (RD). The Renyi divergence computes something like a weighted difference (depending a bit on which one you take). The best thing to do is to really read the paper which proposed this. They also discuss the different orders of Renyi divergence. There are now several follow up papers which improve this approach. Just ask your favorite search engine.

In general, there is not really a rule of thumb to estimate the outcome of such an analysis using either SD or RD.

However, when it comes to the tail cut it is comparatively easy though as the difference between the two distributions is typically known. If the total probability mass in the tails is something like $p = 2^{-k}$ for security parameter $k$, then the statistical distance between the distributions with and without tail is just $p$ and hence negligible. Which means that an adversary cannot distinguish the two distributions better than with probability bounded by $p$. Consequently, the difference in the success probability of any adversary attacking the scheme with one or the other distribution must also be bounded by $p$.

When it comes to the question of floating point precision everything gets more tricky. Here, the difference depends on the algorithm used and the way it is implemented. Hence, you need a new analysis for every implementation.


What are the costs of generating master key for symmetric ciphers?

The cost for generating master keys is not very expensive. It just requires secure random bit string of the same size as the key. Compare this with RSA, where a random prime needs to be generated. This may require repeated calls to the random number generator; you'd expect at least the same number of random bits for the RSA key size. Generally the largest symmetric keys are about 256 bits - far lower than the key size of even moderately secure RSA key pairs.

Now it completely depends on your requirements on the secure random number how much this will cost. If you require your master keys to be build directly upon (whitened) entropy then this may be a very expensive process if your entropy sources are slow. If you're OK with pseudo random numbers or if you have fast entropy sources, it will probably not be slow.

So it depends on the requirements and the implementation of the underlying RNG. I've seen several instances of Linux completely halt when large amount of data is retrieved from the (blocking) /dev/random. Usually it is possible to configure use of /dev/urandom instead. And usually this is as secure.


What is the difference between these AES encryption methods

I can immediately think of four reasons:

They're both not using AES256.  I see in the Obj-C document a direct statement that they are using AES256 (unless you deliberately change it), I don't see any statement in the Visual Basic document that says what key size they're using (unless that's what they mean by "Block Bits").
Different keys.  AES256 takes a key of 256 bits; there's no standard method to take a five character string and convert that into a 256 bit value.  Now, there are a lot of possible methods; there's no particular assurance that they both use the same one.
Different modes of operation.  The AES block cipher takes 128-bit values, and translates that into 128-bit values.  However, not all our messages can fit into 128 bits, and in addition, sometimes there are other things we'd like to do other than message encryption.  A Mode of Operation is a method that takes a block cipher, and uses it as a tool to perform some more generally useful function (such as encrypting a much longer message).  There are a number of standard modes of operations, the Obj-C document states that it is using CBC mode; the Visual Basic document has scary sounding words which might be a garbled explination of CBC mode.
IVs.  Some modes of operation (such as CBC mode) have the encryptor select an "Initialization Vector" randomly; that can be translated along with the encrypted message (because the decryptor will need that value).  One of the things that this Initialization Vector does if you encrypt the message a second time, the second ciphertext will not resemble the first ciphertext at all; that way, someone listening will not be able to deduce that you've just repeated a message.  The Obj-C document specifically says that it will pick a random IV (unless to tell give it one yourself).

As you can see, there are a bunch of reasons why the two ciphertexts may be different.  One thing you can try: hand the ciphertext from one to the other, and ask them to decrypt it; if they can, you can be pretty sure that both sides are doing basically the same thing.

One final warning: the visual basic document has some fairly egregious mistatements in it; either the author doesn't really know what he's talking about, or he is quite bad at explaining things.  I fear it may be the former; I personally would not trust any encryption software written by him.


Padding in Keccak SHA3 hashing algorithm

In FIPS-202 specification, the padding required for SHA3 were not clearly mentioned.

I beg to differ. From the FIPS 202. section B2.:

  For most applications, the message is byte-aligned, i.e., $len(M)
= 8m$ for a nonnegative integer $m$.

  In  this  case,  the  total  number  of bytes,  denoted  by $q$,
  that  are  appended  to  the  message is determined as follows by
  $m$ and the rate $r$:
  $$q = \frac{r}{8} – (m \bmod{\frac{r}{8}})$$

  The  value  of $q$ determines  the  hexadecimal  form  of these  bytes
  in  this  case according  to  the conversion  functions specified in  Sec.  B.1.  The  padded  messages  that  result  are  summarized  in
  Table 6:

+-------------------------+--------------------------------+
|                         |                                |
| Number of padding bytes |       Padded message           |
|                         |                                |
+----------------------------------------------------------+
|                         |                                |
|         q = 1           |  M || 0x86                     |
|                         |                                |
|         q = 2           |  M || 0x0680                   |
|                         |                                |
|         q > 2           |  M || 0x06 || 0x00... || 0x80  |
|                         |                                |
+-------------------------+--------------------------------+

  the notation 0x00... indicates the string that consists of $q – 2 $ “zero” bytes.

If you look at your test vector, for $\operatorname{SHA3-224}$. $224$ means $224$ bits of security. So we have $c = 224 \times 2 = 448$ and $r = 1600 - c = 1152$.

Because message is empty, $len(M) = 0$, therefore $m = 0$. Hence $$q = \frac{1152}{8} - 0 \bmod \frac{1152}{8} = 144$$

Therefore we are in the third case: ($q > 2$).

The padding will be : 0x06 || 144 - 2 zeros || 0x80.Therefore we find back the data to be absorbed :

06 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80

06 followed by 284 0 (or 142 00) then followed by 80. The followings 00 are provided to show that the capacity won't change during the absorption.


A. Find two identical messages with different hashes

This is fundamentally impossible, assuming you're talking about a regular hash and not a keyed hash (like HMAC). As hashes are deterministic, two identical messages will always result in an identical hash.

  B. Find two identical messages with the same hash

This is not only possible, but guaranteed. Two identical messages will always have the same hash.

  C. Find a common hash between two specific messages

Assuming "specific message" refers to a message that you generate, this would be a collision attack. Such attacks are done against the hash function itself, not any existing message. A collision attack generates two messages which differ but which result in the exact same hash output.

  D. Find a common hash between a specific message and a random message

This implies a preimage attack, which is similar to a collision, but you only get to control one message. It's also far harder to exploit than a collision attack because you do not have as much freedom.


Are deterministic adversaries as powerful as probabilistic adversaries?

Following fkraiem's answer, I would share my thoughts.

Generally speaking, we do not know if randomness helps, i.e., P=BPP is an open question. So probabilistic-polynomial-time (PPT) adversaries may not equal to deterministic ones.

However, it seems that cryptography always (correct me if I am wrong) focuses on advantages (or something similar) related to PPT adversaries. In this case, it is sufficient to consider only deterministic adversaries. Here is a simple proof:

Suppose you have a PPT adversary A that has advantage $p$. Then you can fix all possible random coins and get a bunch of deterministic adversaries $A_1, A_2, ..., A_n$, where $A$ runs $A_i$ with probability $p_i$. Since $Adv(A) = p_1Adv(A_1) + \cdots + p_nAdv(A_n)$ and $1=p_1+\cdots+p_n$, there exists $k$ such that $Adv(A_k) \geq Adv(A) = p$. Note that $n$ may be exponential but each adversary $A_i$ runs in polynomial time. Also, knowing that $A_k$ exists does not imply that one can find it in polynomial time.

===================

Update: The above argument can also be adapted to information-theoretic (i.e., computationally unbounded) adversaries.


How decode works in CCA1 scheme based on MP12 construction?

After some time I revisited the problem and found out that before decoding it is necessary to reduce modulo the fundamental region to find a coset, then we have that in the example I gave the internal value $2s+m$ is equal to $[1, 1, \dots]$, and after reduction it turns out to be equivalent to $[1, 0, \dots]$, which is $m$, as needed.


How to compute initial buffer of SHA-512?

What you've done is to shift the 64 bits that you require to the left, before printing out the values. So instead of looking at the bits directly, you are looking at a shifted representation of them. However, if you do that you multiply with a power of two, not a power of ten.

To be precise, if you shift 64 bits to the left then you multiply with $$2^{64} = 18,446,744,073,709,551,616$$
Of course, this number is far from a power of 10, so you would expect it to skew if you look at the result in decimals.

And if you look at the value then you'll see that it is indeed about 1,85 times the number you expect. You get a 7 something instead of a 4 something. In case you don't trust me, here's an interesting calculation for you...

In other words, you interpret the binary digits as if they are digits at the left of the dot, rather than at the right of the dot when you converted them to decimal. It matters where the dot is when you do base conversion and you want to look at the digits.


How to start a classical cryptanalysis on a Substitution + Shift cipher?

Reminder: Analyzing schemes is off topic on crypto.SE. This question will therefore be likely to be closed soon.

Your scheme can be summarized by:
pick a S-box $\sigma$ and two keys $(k_1, k_2)$ and do:

for i in 0 .. len(message) do
  c[i] = σ(m[i])
  if i & 1:
    σ >>> k2
  else
    σ >>> k1
return c

This is broken by frequency analysis with a sufficiently long message:

Find $n$ such that $n \times (k_1 + k_2) \equiv 0 \pmod{26}$.
Remark that every $n \times (k_1 + k_2)$, a character you encrypted with the same key, thus frequency analysis will work.

Worth to be noted:

this is equivalent to a alphabetic Vigenère Cipher with a long key.
modern cryptanalysis (CPA & CCA) breaks this with a 26 chosen plaintext and 1 chosen ciphertext. See bellow.

Query messages:

AA B C D E F .. Z

$\alpha\beta$
These will give the $\sigma$ table.
Assuming that AA is encrypted by αβ query a decryption for the ciphertext: $xαβ$ (prepend a random character). Drop the first character decrypted, the following letters will correspond to the shift distances $k_1$ and $k_2$.

In your example, the query would be:
E(AA) = NT
and
D(XNT) = YDH
leading to
D $\implies k_1 = 3$,
H $\implies k_2 = 7$.


Is garbled circuit a post-quantum primitive?

Garbled circuits are not really a primitive, but more of a protocol.

Furthermore, garbled circuits are generally concealing their semantic values thanks to a cipher such as AES, see this answer to get more details on the whole protocol and the tools it relies on.

So, in order to break garbled circuit, you want to be able to break AES (or whatever cipher used to conceal the values), but the best speed up you might get against AES (and other secure block ciphers) through quantum computer would be thanks to Grover's search algorithm and would be of order $O(\sqrt{n})$, which shouldn't be a problem for AES-256, but could be a problem for AES-128. See also this paper, and its references, to learn more on quantum attacks against AES.

Hence garbled circuits shouldn't really be impacted by quantum computers, even more because you could actually plug a post-quantum cipher (when we got those) in the protocol and keep going.


Summary: ECC over real numbers can be made to work, including for toy-sized security parameters and real numbers arithmetic as directly supported by typical CPUs and spreadsheets. But much more precision would be needed for private keys large enough to hope for security. That would be inefficient if secure; and perhaps just insecure.

We can mathematically define the infinite group of points on an elliptic curve on the continuous plane, e.g. with Cartesian representation in $\mathbb R^2$ under point addition (with an additional neutral element). We can define scalar multiplication on that. For any integers $k_A$ and $k_B$ and any point $g$ on the curve, it mathematically holds that $k_A\times(k_B\times g)=k_B\times(k_A\times g)$, as used by ECDH and ECIES.

However there is at least one huge problem facing a cryptosystem based on that line of thought: when using Floating Point to represent reals in $\mathbb R$ that are coordinates on the curve, $k_A\times(k_B\times g)=k_B\times(k_A\times g)$ no longer exactly holds due to round-off error, and that worsens with larger $k_A$ and $k_B$ for reasons of numerical stability.

The underlying problems are that

When using FP arithmetic, each point addition on the curve involves (among other operations) addition, and the FP version of that is not associative; otherwise said, there are exceptions, occasionally quite notable, to $(x+y)+z=x+(y+z)$.
Independent of FP arithmetic, the effect of a small variation of $g$ on $k\times g$ grows with $k$ (somewhat like the effect of a small variation of $x\in\mathbb R$ on $x^k$ grows about linearly with $k$).

With the $k_j$ in the hundreds of bits, there are many hundreds chained point additions in the computations of $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$, so that discrepancies between the two values at each step (due to 1) will have many chances to appear and grow (due to 2) to the point where the results are extremely different (much like for evaluation of the logistic map in the chaotic region for large number of iterations).

Increasing FP precision will help, but it is hard to tell exactly how precise a FP representation of coordinates on the curve we shall use for $g$, and intermediary values including $k_A\times g$ and $k_B\times g$, so that $k_A\times(k_B\times g)$ and $k_B\times(k_A\times g)$ coincide well-enough to derive a shared secret.
Note: the practical issue of defining that well-enough and turning it into a consistent shared secret is non-trivial, but it can be solved by rounding to agreed-upon number of bits, combined with appropriate error correction like: detecting disagreement and, should that occur, retrying or trying nearby values; sending a small public additive correction, or other form of Forward Error Correction.

Floating Point arithmetic with direct hardware support on modern CPUs (that is typically at most 80-bit with 64-bit mantissa, or 64-bit with 53-bit mantissa) will not be precise enough that results coincide well-enough for realistic $k_j$; but it can be made to work most often for $k_j$ and shared key of a few bits. Making large shared keys from small ones is easy (just make multiple passes and concatenate); but I doubt we could make large private/public key pairs from small ones.

Arbitrary-precision FP arithmetic is possible, but inneficient. Typically it uses arbitrary-precision integer arithmetic, so we would be back to this.

Note: there are other serious numerical issues, including the risk of overflow, and how to extract the shared key from potentially very large coordinates.

I do not know if there is an additional issue with security.

The problem of solving for integer $k$ given $k\times g$ and $g$ (which breaks ECDH) might not be as hard with coordinates of givens in $\mathbb R$ (as approximated by FP arithmetic) as it is for coordinates in $GF(p)$ or $GF(2^m)$. As an illustration that it can't be ruled out summarily, solving for $k$ given $x^k$ and $x$ is believed hard with givens in $GF(p)$ for appropriate choice of $p$, but is easy with givens in $\mathbb R$ (as approximated by FP arithmetic, and assuming no overflow) because $k=\log(x^k)/\log(x)$ (computed with rounding to the nearest for FP).

Also, there are conflicting interactions between the precision used and security:

Too low a precision on $g$ or/and $k\times g$ restricts the size of $k$ for a unique solution $k$, and short $k$ makes finding $k$ easy; there's no solution to that in sight beyond increasing precision.
Overly increasing precision for $k\times g$ (for constant range of $k$) could conceivably make the problem of finding $k$ easier, as we are getting more information about $k$ from low-order bits/digits of $k\times g$.


Is it safe to reuse the same nonce for decryption an indefinite amount of times in this context?

Specifically, is it safe to re-use the same nonce for decryption an indefinite amount of times, if you only use it once for encryption?

Indeed, all good security definitions (under which ciphers are proven secure) will place no restrictions on the input of the decryption algorithm. The intution behind this is that the the input to the encryption algorithm will be send over the network at which point anything can happen to it.

Security only breaks down if you encryption two different messages using the same key-nonce pair.

  Now, the question is, is this procedure safe?

Yes. In fact the encryption scheme is essentially a reinvention and instantiation of PKCS#5's PBES2 which is provably secure1 (even if you were to use a fixed nonce). Your parameter choice in this case is to use randomized-nonce ChaCha-Poly for encryption and scrypt for key-derivation.

1: Our local pedants may note that the security definition of LORX from that paper only implies CPA-security, but an extension to CCA-security definitions should be straightforward as the proof essentially relies on hiding the key from the adversary and then "inheriting" the encryption scheme's security properties.


However, since usernames are unique [...]

But the same user is supposed to get a fresh salt when they change their password.  Salts are not supposed to be bound to usernames as you suggest; they're bound to states of individual password database entries.  If the attacker gets their hands on multiple password entries for the same user in your scenario, those entries will have the same salt and thus there is a work savings they can achieve.

One practical illustration of this is to consider that many password storage APIs have been carefully designed to avoid salt misuse by factoring the process into these two operations:

Generate password token: Take a password as input and produce a password verification token as output.  This token incorporates:

A description of the algorithm that was used and any parameters required to rerun it;
A random salt (generated internally by the API operation);
The raw password hash output.

Verify password: Takes a password and a verification token as input, and outputs true if and only if the password checks out against the token.  Internally this:

Decodes the token to determine the algorithm, parameters, salt and raw hash;
Uses this information to select the password hashing algorithm and parameters;
Hashes the supplied password with those choices;
Compares the resulting raw hash to the one stored in the token.

When you use an API like this to manage your users' passwords, you call operation #1 not only when you enroll a new user, but also when an existing user changes their password.  Which means a new salt is implicitly generated afresh, and you can't make the mistake of reusing the same salt for the same user.

In addition, usernames are broadly predictable just like passwords are (or perhaps more so!).  Notably, an attacker can likely guess a bunch of your usernames even before they ever see your password database.  Which means that username salts are to some extent subject to precomputation attacks—if your scheme was broadly adopted, an attacker could conceivably precompute a rainbow table based on pairs of:

Common passwords (as is already well-known practice);
Usernames known to be common at large, or that have a high probability of being used among a small population of interest (e.g., a foreign adversary's influential politicians).

Which means that although password salts are nonsecret, they ideally should be unpredictable as well.  That sounds like an oxymoron at first, but what it means is that an attacker should not be able to guess what a password entry's salt might be before they actually see the entry.  Random salts trivially ace this test; usernames don't score well on that criterion, and neither do @cypherfox's "site identifiers" or counters, for that matter.


Can one efficiently iterate valid bcrypt hash output values?

bcrypt uses Blowfish, which is a block cipher (albeit with a much enlarged key schedule). As such, Blowfish implements a permutation of the space of 64-bit blocks; and there should be no way to distinguish Blowfish (using a random key) from a permutation extracted at random, with uniform probability, from the set of permutations over 64-bit blocks (there are $2^{64}!$ such permutations).

The best cryptanalysis result so far, about precisely distinguishing Blowfish from a random permutation, is due to Vaudenay: some Blowfish keys can be detected (and thus making the block cipher distinguished from a random permutation) if the number of rounds is reduced to 14 (from 16 for the "normal" Blowfish). There is no attack on the full Blowfish, and even if there was, it would only be about the weak keys (about one key in $2^{15}$ is weak).

Therefore we cannot guess anything about the Blowfish instance, that would not apply to a randomly chosen permutation. This still allows a small remark: since this is ECB encryption, i.e. encryption of three distinct 64-bit blocks, we know that the hash result must consist of three distinct 64-bit blocks, concatenated together. This implies that the space of possible hash values has size $2^{64}(2^{64}-1)(2^{64}-2)$, which is $2^{192}-3\cdot2^{128}+2\cdot2^{64}$, i.e. very slightly lower than $2^{192}$ (but not by a significant amount).

The trickier part of your question is about bypassing the key schedule. The point of bcrypt is to make processing of a single password as slow as possible for the attacker, but not intolerably slow for the honest systems. The use of Blowfish is a good idea here: the key schedule of Blowfish is optimized for systems which have a few Kbytes of fast RAM, and that's a PC. Implementing Blowfish on, say, a FPGA or ASIC, would be a painful experience; and the RAM requirement is likely to impair performance on GPU as well. This still requires that the key schedule itself is not amenable to hidden optimization, that the attacker may use. To my knowledge, there is no known result on the security of the "expanded key schedule" used in bcrypt.

Note that this algorithm is of the kind which uses self-modifying lookup tables, like MD2 and RC4, which are notoriously difficult to analyze: we do not benefit from the usual tools such as differential or linear cryptanalysis. MD2 and RC4 turned out to have weaknesses, but it took an awful lot of time, and nothing currently suggests that Blowfish could have such weaknesses. We still lack a proper mathematical framework to discuss the security of such constructions. So the absence of published results just means that nobody found an actual break; it does not mean that there are known reasons why such a break may or may not exist. My feeling is that the extended key schedule used in bcrypt is robust for what it is used for (i.e. an unavoidable mass of computations for each password guess).

So my answer to your question ("Is there any method...") is: no.


On assumption $x_1 = x_2 = x$ and $a_1 = a_2 = a$, introduce linear polynomials over $F_q$: $X(z) = x z + \eta_x$, $A(z) = a z + \eta_a$, $B(z) = b z + \eta_b$. Consider two group elements: $g_1^{A(z)} g_2^{X(z)} m_1^{-z}$ and $ g_1^{z B(z)} g_2^{A(z) X(z)} m_2^{-z^2}$. First element is a constant (zero degree in $z$) if and only if the assumption holds. Nothing unusual/new at this point yet. Second element is linear in $z$ if and only if assumption holds, and this might look like an extension of Schnorr protocol. Now evaluate polynomials at some $z$ chosen as a challenge and invoke Schwartz-Zippel lemma for a bound on soundness error. At last, Alice must not be able to solve DL in this group (computational soundness) and must not know linear relation with $g_1$ and $g_2$ (setup).


Is this problem on $\mathbb{Z}_p$ really hard?

TL;DR: No, that problem is not hard.

Synopsis: After remapping of $\Bbb Z_p$ by an involution $x\to\overline x$, the function $(x,y)\to\overline{-f(\overline x,\overline y)}$ is mostly associative. We massage it into an Abelian finite group $(\mathcal S,\boxplus)$. This makes $\overline{r_n}$ a linear function of $\overline a$ and $\overline b$ with known scalar coefficients, allowing to efficiently solve the question's problem.

Define $\delta$ and $\hat z$ in $\Bbb Z_p$ with $\delta=(p+1)/2$ and $\hat z=(-3\,\delta^2-z)\bmod p$. The reason will become apparent later, for now consider $\hat z$ as an arbitrary fixed public element of $\Bbb Z_p$.

Define $l$ as the Legendre symbol $l=\displaystyle\biggl(\frac{\hat z}p\biggr)$, and define $m=p-l$.

When $l=+1$, define $\omega$ as a particular solution of $\omega^2=a$ in $\Bbb Z_p$, e.g. the odd one in range $[1,p)$.

Define the set $\mathcal S$ as:
$$\mathcal S=\begin{cases}
\{\infty\}\cup\Bbb Z_p&\text{when }l=-1\\
\{\infty\}\cup\Bbb Z_p-\{0\}&\text{when }l=0\\
\{\infty\}\cup\Bbb Z_p-\{\omega,p-\omega\}&\text{when }l=+1
\end{cases}$$

Define internal law $\boxplus$ in $\mathcal S$ as:
$$x\boxplus y=\begin{cases}
y&\text{when }x=\infty\\
x&\text{when }x\ne\infty\text{ and }y=\infty\\
\infty&\text{when }x\ne\infty\text{ and }y=-x\\
(x+y)^{-1}(x\,y+\hat z)&\text{otherwise}
\end{cases}$$

$(\mathcal S,\boxplus)$ is¹,²,⁶ a finite Abelian group of $m$ elements with neutral $\infty$. With the convention $-\infty=\infty$, the opposite $-x$ of $x$ in group $(\mathcal S,\boxplus)$ is² computed as in $(\Bbb Z_p,+)$ when $x\ne\infty$.

Define scalar multiplication $\boxtimes: \Bbb Z\times\mathcal S\mapsto \mathcal S$ as:
$$k\boxtimes x=\begin{cases}
\infty&\text{when }k=0\\
(-k)\boxtimes(-x)&\text{when }k<0\\
\bigl((k-1)\boxtimes x\bigr)\boxplus x&\text{otherwise}
\end{cases}$$
and for all $x$ in $\mathcal S$ and integers $k$, $k'$, it holds²:
$$\begin{align}
(k\boxtimes x)\,\boxplus\,(k'\boxtimes x)&=(k+k')\boxtimes x&\text{and}\\
k\boxtimes (k'\boxtimes x)&=(k\,k')\boxtimes x&\text{and}\\
k\boxtimes x&=(k\bmod m)\boxtimes x
\end{align}$$

For $x$ in $\{\infty\}\cup\Bbb Z_p$ define $\overline x=\begin{cases}
\infty&\text{when }x=\infty\\
\delta-x&\text{otherwise}\\
\end{cases}$.

Define $\hat{\mathcal S}$ as the set of $\overline x$ for all $x$ in $\mathcal S$. It holds $\hat{\mathcal S}=\mathcal S\iff l=-1$.

A function $f:\hat{\mathcal S}\times\hat{\mathcal S}\mapsto\hat{\mathcal S}$ compatible⁴ with the question's $f$ can²,⁵ now be defined as:
$$f(x,y)=\overline{-(\overline x\boxplus\overline y)}$$

The «restricted commutativity»³ property that $f\bigl(f(x,y),f(y',z)\bigr)=f\bigl(f(x,y'),f(y,z)\bigr)$ is a consequence of the associativity and commutativity of $\boxplus$ , and the fact for all $x$ in $\mathcal S$ it holds $\overline{(\overline x)}=x$.

Define:
$$\begin{align}
\hat s_0&=\overline a\\
\hat s_1&=\overline b\\
\hat s_n&=-(\hat s_{n-2}\boxplus\hat s_{n-1})\text{ when }n>1\\
\hat r_n&=-(\hat s_n\boxplus\hat s_0)\\
\end{align}$$
and for all $n$ it holds²: $\hat s_n=\overline{s_n}$ and $\hat r_n=\overline{r_n}$.

From this we can efficiently compute² integers $u_n$ and $v_n$ in $\Bbb Z_m$ such that:
$$\overline{r_n}=(u_n\boxtimes\overline a)\,\boxplus\,(v_n\boxtimes\overline b)$$

This allows² to solve for $a$ given $b$ and $r_n$, knowing parameters $p$, $z$, $n$. That's significantly easier than a discrete logarithm problem. When $\gcd(u_n,m)=1$, the unique solution is $$a=\overline{(u_n^{-1}\bmod m)\boxtimes(\overline{r_n}\,\boxplus\,(-v_n\boxtimes\overline b))}$$

Notes:

¹ : In particular, $\boxplus$ is² associative!

² : Proof is left as an exercise to the reader.

³ : See document linked in the question.

⁴ : When $l\ne-1$ one of the input of $f$ can be excluded from $S$; assimilate it to $\infty$.

⁵ : $\delta$ and $\hat z$ are chosen such that $\overline{(x+y-1)^{-1}(-x\,y+x+y+z)}=-(\overline x\boxplus\overline y)$.

⁶ : This group has been identified there, if not named.


LSB of the Exponent in the DL Problem Can Be Efficiently Computed for Groups of Even Order

Write $x=x_0+2x_1$ for $x_0\in\left\{0,1\right\}$, so that the goal becomes determining $x_0$. Now compute $y^n$ (in terms of $h$, $x_0$ and $x_1$), and determine its order. What happens when $x_0=0$ and when $x_0=1$? Can we easily differentiate between them?

Note that this is the idea underlying the Pohlig-Hellman algorithm, so it may help to have a look at that.


Are there cryptographic hash functions which do not have any collisions?

This is impossible for any generally useful hash: a hash must map all inputs to a fixed-length output, but you normally want to be able to take variable (and fairly long) inputs. The problem is that there are more inputs than outputs: you normally want to be able to hash any string up to a fairly big length, but the hash itself should not be too long, and there are more long strings than short ones.


How to create and validate potential grids when attacking a Playfair cipher?

Both your suspicions are correct, BTW. (I solved it, and know the key-word).

You have a crib, namely ATTACK, with a typical pattern: two digrams that are each other's reverse, which means that (if we assume that the crib starts at an even position) the cipher text should also have the pattern "abba". I see a CQQC pattern and you note that CQ is frequent after TH, so that fits nicely with CQ = AT, to give THAT.

The text starts with QK = TH, so the next letter could be E (as A would probably be followed by T), so V is one of the letters that E can encipher to, so it must be in the same row (probably) or the same column as E (same column means also that they are next to each other, so same row is more likely). This also fits with your UV/VU supposition. It then follows that E,V,U are all in the same row (or column, less likely). And this row is then in the keyword (by how keyword squares are made: E is far away in the alphabet from U and V).

So from this we already get quite a few ideas on how letters are positioned relative to each other, and at the end of the square we expect some almost alphabetic sequences, like WXYZ (minus letters that go into the keyword), etc.

Fill in some letters (write a program) and guess more letters. If my ATTA guess was OK, you also get CK that becomes KT, which gives us info: overlapping crypto/plain means same row or same column. Etc. etc.

Have fun puzzling it out.


Algorithm for symmetric encryption (diffusion without confusion)?

It should be hard to perform a KPA. I believe the diffusion concept makes it hard to perform such an attack?

Assuming the context of traditional symmetric encryption: confusion (combined with diffusion) is what makes this hard.

For simplicity, suppose we have a 4-bit message. Suppose the equations for each bit of ciphertext are: \begin{align}
c_0 &= m_0 \oplus m_1 \oplus k_0\\
c_1 &= m_1 \oplus m_2 \oplus k_1\\
c_2 &= m_2 \oplus m_3 \oplus k_2\\
c_3 &= m_3 \oplus m_0 \oplus m_1 \oplus k_3
\end{align}

Recovering the bits $k_i$ is trivial when you know $m$:

\begin{align}
k_0 &= c_0 \oplus m_0 \oplus m_1\\
k_1 &= c_1 \oplus m_1 \oplus m_2\\
k_2 &= c_2 \oplus m_2 \oplus m_3\\
k_3 &= c_3 \oplus m_3 \oplus m_0 \oplus m_1
\end{align}

Diffusion by itself is not generically sufficient to protect against known-plaintext attacks.

  Yet I require that $k+x→e, E_e[m]→(c+x)$ where $+$ can be the sum operator in a finite field. I believe this will require to avoid the confusion concept?

This would no longer the realm of traditional symmetric encryption.

You'll be looking for some kind of homomorphic encryption. There might be some kind of lattice-based construction that offers this feature. If I recall correctly, Ajtai's hash function offers some kind of "key homomorphism", but I'm not sure that it works the way that you require.

I can't provide a more precise suggestion of a scheme. Maybe someone else can.


Is there something similar to a Bloom filter that allows you to test arbitrary predicates on the set?

If you want to answer arbitrary queries, no there is nothing like this. Essentially encoding a set into a Bloom filter is a process of lossy compression so that you gain efficiency in space, but the price you pay is that the data structure can answer only a specific query, i.e. set membership. Other information might have been lost because for this query it is not important.

As such, if you have a specific query in mind, you may be able to design an alternative data structure that satisfies your requirement.


How can rainbow tables be used for a dictionary attack?

Finding a decent explanation of rainbow tables was something I struggled with, so firstly I'll cover what they are. I will get to your question in the end. My sources for this are this guide and the wikipedia article.

Why can't I just use a big bucket of hashes?

Firstly the naive way to build a reverse lookup table is this. Let's say we want to generate all the hashes for every 8-digit password in existence, using the set [A-Za-z0-9]. In that case there are 62 unique characters and with that, using the counting function $n^r$ where $n$ is the possible number of outputs and $r$ is the number of choices we can make, then there are $218340105584896$ possible strings in this output space. Navely storing this data we can take a 8 character string as taking 8 bits per character (so each string costs 64 bits) plus a separator character plus the 256-bit output of say sha256, the total cost is then $218340105584896(64+1+256) = 70087173892751616$ bits. Converting that to bytes, i.e. $\frac{70087173892751616}{8*(1024)^3} \approx 8159220$ gigabytes.

Two notes on this:

It only considers exactly 8-character passwords. If you want to consider passwords containing 4-8 entries, you need $62^4+62^5+62^6+62^7+62^8$.
It assumes you're actually going to store that data in raw form. There are probably better ways to handle this.

So the first problem is storage. Above, we simply computed the total output space of a hash function.

What is a rainbow table?

The idea behind rainbow tables is to offset the space issue. To this end, let's define a few things: firstly we have a search domain we'll call $\mathbb{P}$ and a hash output domain we'll call $\mathbb{H}$. Then we have a hash we want to invert we'll define as $\mathcal{H}: \mathbb{P} \rightarrow \mathbb{H}$. i.e. the hash function takes an element of the search domain and produces a value in the hash output domain.

We then introduce a concept called chaining. To do this, consider we could define a function that maps the other way fairly trivially; let's call it $\mathcal{R}: \mathbb{H} \rightarrow \mathbb{P}$. In a rainbow table, a chain starts with a starting value and applies $\mathcal{H}$ then a $\mathcal{R}$ alternately, but always in pairs such that when done you end up with the first and last elements $p_0, p_k \in \mathbb{P}$. This is what you store.

A rainbow table is slightly more complicated than using the same $\mathcal{R}$ for each pair; this has problems relating to collisions. If two chains produce the same value they converge, meaning we waste time spend computing said chains - this is a chain collision. I had trouble visualizing this, so drawing a diagram:

a_1 ----> a_2 ----> a_3 / b_2 --> a_4 / b_3 --> a_5 / b_4 ---> a_6 / b_5
                        |                                         |
b_1 ---------------------                                         -----> b_6.

Instead, a set of functions $\{\mathcal{R}_0, \ldots, \mathcal{R}_{k-1}\}$ are applied, one for each pair of the chain. SO when chains merge using this setup, they always produce the same final value and can then be de-duplicated, saving space - detection of wasted space is also much easier on generation.

Then:

Generating rainbow tables: pick a length $k$ and define the functions $\mathcal{R}_{0}, \ldots, \mathcal{R}_{k-1}$. Then, for a given input $p \in \mathbb{P}$ we compute $c_0 = p, c_{n+1} = \mathcal{R}_{n-1}(r_{n}), r_{n} = \mathcal{H}(c_{n})\;\;(n=0,1,2,\ldots, k)$. These $c$ form a chain $C$. We compute our chains and for each chain we store just the pair $(c_0, c_k)$.
Searching a rainbow table. Now, assume we want to inverse a hash value $h$. To do this we run through this process, starting with $i=k-1$:

Generate chain for $h$ starting at $R_{i}$
Using the end-value of the above chain, search our list of end values for computed chains. If we find a matching end-value, compute its chain term at a time (we can do this because we know the start value). If we find $h$ as say $r_n$ in that chain then the corresponding $c_n$ value is the inverse of $h$. Stop. If we don't find the end value in the chain list, carry on. If we don't find the hash in a generated chain where we did find the chain value, carry on.
If $i \neq 0$ do $i=i-1$ and go back to 1.
If we get here, we haven't found the inverse.

Right so exactly what is the benefit?

It's a space/time trade off. Specifically, the reverse lookup table takes a lot of space. This is a scheme that takes less space, but requires more time per lookup to work. Since the size of a complete reverse table is prohibitive for most people, the increased computational cost is generally preferable. Storage space is reduced massively, but is actually harder to calculate as it depends on $k$, and the $\mathcal{R}$ you use.

Clearly, also, we have different options with rainbow tables in terms of the length of $k$. The longer $k$, the fewer the number of total chains before all elements in $\mathbb{P}$ are covered. However, that also increases the run time of a lookup.

Oh no, now I have no idea how salt comes into this?!

Salt increases the size of $\mathbb{P}$ by increasing the $r$ in $n^r$. This makes both an inverse hash list astronomically big and also increases the size and computation time required for a rainbow table, too.

An attacker then has two options:

Produce a rainbow table specific to a given salt, making it invalid for a different salt.
Produce a huge rainbow table.

And what about slow hashing functions?

So far we've mostly talked about space as a consideration, without regards to the time taken to look up a function. Most cryptographic hashes are designed to be fairly quick, so this is ultimately feasible to do for say MD5.

Now what happens if we choose $\mathcal{H}$ which we know takes approximately a second to calculate each hash? Assuming there are no shortcuts that remove this additional time cost, the giant inverse table will take $218340105584896$ seconds, or approximately $6923519$ years. Your rainbow table is going to take a long time to generate too - assuming you never have collisions and cover the whole domain, just as long as a hash reverse lookup, plus added cost to search, depending on the length of $k$.

Combining both is a fairly effective defense against a rainbow table, making it both specific to a given salt and expensive to generate and use.

Why do password policies mention things like character classes, e.g. must have an upper case, must have a piece of punctuation?

We defined $\mathbb{P}$ as the set [A-Za-z0-9]. If you add punctuation into the mix you increase the size of $\mathbb{P}$ again, and so increase the size of the rainbow table (number of chains needed) again. Password length requirements also do this.

So dictionaries?

The whole premise behind a rather famous XKCD comic is the idea of information entropy. To tread roughshod over a fairly interesting area of science (sorry!) basically what you say is that whilst the total permutations of $\mathbb{P}$ are large, actually, quite a lot of those are totally meaningless to humans and we would not, given a choice, use them. Said XKCD comic was saying that actually, if you make certain judgements about the likely format of passwords, using information entropy as a measure of uncertainty within these formats then longer pass-phrases actually score better than shorter complicated passwords.

There is no reason you cannot produce a rainbow table using a set of reduction functions that takes this sort of assumption into account.

A dictionary is just a simplified version of this guessing - namely you're making the assumption that the thing you are inverting is actually a known dictionary word. You could also generate a rainbow table with known dictionary pass-phrases.

In both cases you are reducing $\mathbb{P}$ which by extension decreases the size of the rainbow table and the time to perform a lookup; however, such a technique is susceptible to the fact your approximate representation of a password just might not be right.

What's the complexity of rainbow tables?

Suppose we want to build a rainbow table to cover a set of $N$ potential passwords.  (In other words, $N = |\mathbb{P}|$.)  Let $t$ denote the average chain length; this is a parameter that you can choose freely, to optimize the cost of the attack.

Then, the cost of building the table is about $1.7N$ hash computations (yes, it is 70% more expensive than a simple exhaustive search on the set). The storage cost is $N/t$ elements of size at least $\lg N$ (but not necessarily much bigger). Attacking a password has cost about $t^2/2$ hash computations, and $t$ lookups (a "lookup" is when you are actually looking for data in the harddisk; it is typically much slower than a hash computation).


Retrieving correct ciphertext from additive ElGamal

The answer is simple if you know the answer to this question:

  Can you use 20 instead of 4 for a plaintext?

If you can they will be the same encryption and no problem since 20 and 4 same for yo.
If you cannot, therefore, you cannot decide the plaintext after you decrypted.

To solve this issue you have to limit your message space into $\pmod{17}$ and divide your longer message block in an appropriate way. Now, you know, you have to take the smallest positive value where $k=0$.

The problem with adding homomorphically is a different issue. Before the computation, you have to consider the upper bound of your calculations and choose your modulus according to it. For example, if you are going to add 4 and 8 there is no problem, however, if you are going to add 10 and 9 you have to consider a bigger modulus.


Probabilistic padding to avoid Håstad’s Broadcast Attack

If you use the same padding on the same messages, sent to multiple different public keys, then you have satisfied the criteria of the Håstad attack.

Randomizing the padding as in OAEP means that you don't use the same padding for each message.  Even better, in a modern system like RSA-KEM, there's no ‘padding’ per se, or even any ‘message’ involved directly in the RSA part of the computation—the sender just

picks $0 \leq x < n$ uniformly at random,
uses $H(x)$ as a secret key for an authenticated cipher to encrypt an arbitrarily long message, and then
sends $x^3 \bmod n$ alongside the authenticated ciphertext.


Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$

I don't think there's anything to worry about here. Remarks 4.2 and 4.3 in the second paper point out that these approaches need to first find a point on a curve with a very large conductor/discriminant, and that seems to be very hard. (Harder than factoring the integer using NFS.)

There are many ways to compute factorings and discrete logarithms where you first do some very hard number theoretic computations (e.g. related to an elliptic curve over the rationals), then easily factor or compute a d.log. I designed such an algorithm myself once, and it was utterly useless.


MD5 and SHA-1 have been broken (from a collision-resistance perspective) due to weaknesses of their compression function, not because they are Merkle–Damgård based.

SHA-2 hashes (SHA-256, SHA-512..) are Merkle–Damgård based, but use more compute-intensive compression functions, and are so far unbroken.

SHA-3 is not Merkle–Damgård based, it uses the sponge construction. One advantage is that the result does not reveal the full state, and that makes the construction immune to the length-extension attack.


Efficient calculation of point coordinates with elliptic curves over binary field

First, break it into a simpler problem: Divide by $u^2$ to rewrite $y^2 + uy + v = 0$ as $$(y/u)^2 + y/u + v/u^2 = 0;$$ then solve for $y/u$, and multiply the result by $u$.

$% Evidently mathjax's \operatorname fails to kern properly, so
% \operatorname{Tr} has an awful gap between T and r.  Worse, the
% \operatorname command blindly substitutes \text{-} for - anywhere
% in its argument, so \operatorname{T\kern-.98pt r} fails.  (This
% kern assumes cmr10 (actually, lmroman10, on which latinmodern-math
% is based), where the true value is (1.5*23.5/36)pt, which is
% approximately .695pt.  No \mathchoice because mathjax doesn't do
% smaller designed font sizes; it just scales cmr10 to other point
% sizes.)
\def\Trname{T\kern-.695pt r}%
\DeclareMathOperator{\Tr}{\Trname}%
\DeclareMathOperator{\GF}{GF}%
% Fake \clap.  Real one is (modulo math mode conditionals):
% \def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\clap#1{\mkern-10mu#1\mkern-10mu}%
$How do you solve $t^2 + t + d = 0$ for $t$?  (Here $t = y/u$ and $d = v/u^2$.)  Suppose we are working in $\GF(2^m)$.  It is necessary that $$\Tr(d) := \sum_{i=0}^{m-1} d^{2^i} = d + d^2 + d^4 + d^8 + \dotsb + d^{2^{m - 1}} = 0,$$ where $\Tr(d)$ is the trace of $d$ over $\GF(2^m)$ as a field extension of $\GF(2)$, for if $\alpha$ is a root of $t^2 + t + d$ in $\GF(2^m)$, then $\Tr(d) = \Tr(\alpha^2 + \alpha) = \Tr(\alpha^2) + \Tr(\alpha) = \alpha^{2^m} + \alpha = 0$.  Now break this down into two cases.

$m$ is odd.  In this case, the half-trace

\begin{align*}
     H(d) := \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i}}
           = d + d^4 + d^{16} + \dotsb + d^{2^{m - 3}} + d^{2^{m - 1}}
   \end{align*}

is related to the trace $\Tr(d)$ by

\begin{align*}
     H(d)^2
       &= \sum_{i=0}^{\clap{(m - 1)/2}} \bigl(d^{2^{2i}}\bigr)^2
        = \sum_{i=0}^{\clap{(m - 1)/2}} d^{2^{2i + 1}} \\
       &= d^2 + d^8 + d^{32} + \dotsb
          + d^{2^{m - 2}} + d^{2^m} \\
       &= d^2 + d^8 + d^{32} + \dotsb
          + d^{2^{m - 2}} + d \\
       &= \Tr(d) + H(d) + d,
   \end{align*}

since squaring is linear in $\GF(2^m)$.  If $t^2 + t + d$ has a root so that $\Tr(d) = 0$, then we have $H(d)^2 + H(d) + d = \Tr(d) = 0$; hence $H(d)$ is a root of $t^2 + t + d$.
$m$ is even.  This case is a pain, and therefore left as an exercise for the reader who is less lazy than I am.  (Hardly anyone ever uses elliptic curves over even-power binary extension fields in cryptography; usually the power is an odd prime.)


Minimizing exchanges for ZK proof of a message with given SHA-256

To answer every part of this question in full details would require almost a book. Here, I’ll attempt to address all sub-questions and give a brief summary together with pointers each time. If you want me to develop some specific aspect, you can ask in the comments. Most of what I will say will not be specific to proving knowledge of a SHA-256 preimage, but follows from general results about zero-knowledge proofs.
EDIT: Bottom Line
Since my answer is long, here is a shorter bottom line:

There exists zero-knowledge proofs of knowledge for arbitrary NP statements (in particular, proving knowledge of a preimage to SHA256) with

Tiny information flow (e.g. 768 bits in total, independently of the size of the statement)
Minimal interaction (single round, assuming a global trusted reference string available to all parties)
"Implementable" concrete efficiency (like, those proofs systems have been implemented, are used, and have reasonable performances on sufficiently simple statements)
Bonus point : these proof systems (typically, SNARKs) have a tiny verifier computation (even shorter than checking that the statement is true given the witness!)

However, these "optimal features" come usually at a cost: high prover computation. The prover cost is often "asymptotically reasonable" (e.g. quasilinear in the size of the circuit checking the statement), but concretely very high (large constants are involved). Therefore, in practice it will most commonly be the case that one will prefer to give up on some of these optimal features, in exchange for a more reasonable prover cost. For example, the NIST candidate post-quantum signature Picnic v2 uses the latest developments in the line of work on ZK proofs from MPC-in-the-head (a line of work to which ZKBoo belongs), which leads to a proof linear in the size of the circuit, but much better computational costs. There are also tradeoffs, like Ligero, with "intermediate" prover costs, and smaller proof sizes on large instances (square root of the circuit size).
Additional Note: this is completely orthogonal to your question, but since you mention explicitly SHA256, you might be interested in knowing that there are important and fruitful lines of work that pursue the opposite direction: building new candidate collision-resistant hash functions (or block ciphers, stream ciphers, etc) which are zero-knowledge-friendly, in the sense that their structure is tailored to some existing zero-knowledge proof systems and seek to optimize the efficiency of proofs for these primitives. Standard examples include LowMC, Rasta, Trivium, Kreyvium, and many others. For example, the Picnic NIST candidate signature scheme is in fact a proof of knowledge of a preimage of a LowMC-based hash function.

Below is the detailed answer to the question.

Are there firm lower bounds on the necessary information flow in both
directions, number of exchanges, and probability $\varepsilon$ of reaching a
wrong conclusion?

This is a deep and vast question. Let me cut it into pieces.

Are there firm lower bounds on the number of exchanges?

What follows should also answer your last question:

Independently, can such proof be non-interactive (becoming a static
proof that knowledge of m hashing to ℎ was used in making the proof,
with no indication about the proof's origin or freshness)?

I gave some partial answer to this question here. The answer changes fundamentally if we assume that the parties are given access to some common reference string (CRS), generated honestly and given to all parties before the start of the protocol, or if we consider zero-knowledge in the plain model (where we do not assume a CRS, or any other trust assumption). Quoting from my answer:
Without a CRS:
« Assuming only one-way functions, we need a superconstant number of rounds to get zero-knowledge proofs for NP. Assuming further the existence of collision-resistant hash functions, we can build five rounds zero-knowledge proofs for NP. This is essentially the best we can hope for: under black-box simulation, a 4-round zero-knowledge proof for NP would collapse the polynomial hierarchy (but there exists some candidate constructions based on exotic assumptions, such as knowledge-of-exponent assumptions or keyless multi-collision resistant hash functions, with non-black-box simulation). Even with non-black-box simulation, a 3-round ZK proof for NP would break indistinguishability obfuscation. Furthermore, 2-round ZK proofs can simply not exist for languages outside BPP. »
With a CRS:
« Every language in NP has a non-interactive (1-round) zero-knowledge proof, under standard assumptions (e.g. factorization). »
Hence, without a CRS, 2 rounds is hopeless and 3 rounds seems very unlikely; with a CRS, one round suffices under standard assumptions.
(cautionary note: for the sake of simplicity I did not distinguished between common reference strings and common random strings; if one wants to delve into the full details of these characterization, this difference matters, but it is not of utter importance for a high level overview).

Are there firm lower bounds on the necessary information flow in both directions?

A trivial lower bound is that to reach soundness error $\varepsilon$, the total length of the prover messages must be at least $\log(1/\varepsilon)$: by the zero-knowledge property, there must exist one sequence of messages that cause the verifier to accept, even when proving a wrong statement (otherwise, we could not simulate), and just guessing this sequence would already contradict the soundness error bound if the total length is less than $\log(1/\varepsilon)$.
In fact, we cannot do much better - because we know zero-knowledge proof with very small information flow. Much, much smaller than the size of the statement itself. More precisely:
Interactive setting:
In the interactive setting, assuming collision resistant hash functions, every length-$n$ statement in NP can be proven in zero-knowledge using only $O(\log n)$ bits of total communication. This is the famous Killian protocol.
Non-interactive setting:
In the non-interactive setting (one round of communication, but we assume a CRS, which is necessary), this is more messy. In the random oracle model, you can apply the Fiat-Shamir heuristic and make Killian’s protocol non-interactive. This gives you a heuristic candidate non-interactive zero-knowledge argument (NIZK) with $O(\log n)$ communication.
But we can do even better!

Assuming a specific and very strong ‘knowledge of exponent’ assumption, there exists a NIZK proof system for any statement in NP, with total communication of 4 group elements - i.e., 1024 bits of total communication for any statement (assuming a 256-bit elliptic curve).

In the generic group model (which gives a heuristic construction in the standard model), we can even go further down, to only three group elements (768 bits).

Can we go even lower? A single element is impossible (in a model that treat the group as a black box). 2 group elements is open, as far as I know.

Eventually, assuming the very strong notion of indistinguishability obfuscation (iO), we can achieve optimally small NIZKs in the designated-verifier setting (where the verifier is allowed to have a secret key to check the proof): under iO, there is a designated-verifier NIZK which achieves soundness $1/2$ with a single bit of communication (hence, by parallel amplification, it achieves soundness error $\varepsilon$ with a communication $\log(1/\varepsilon)$). Since iO is completely inefficient, this construction is only of theoretical interest.

Summary: under strong assumptions and assuming a CRS, we can have both minimal communication and minimal interaction.

How far from that are current implementations?

It depends how computationally efficient you want your system to be - i.e., are you willing to pay for having small communication?

Succinct non-interactive proofs of knowledge (SNARKs), with constant-size proofs, are implemented and available. Here is an example; but since SNARKs are used in important applications, such as the cryptocurrency zcash, there are probably dozen of implementations available. Many should achieve constant size proofs, with 768 or 1024 bits in total.

However, the above solutions will usually be computationally very heavy on the prover side (not even mentioning that it relies on rather extreme assumptions). If you want better computational efficiency, it is common to trade it for proof size, and rely on proof systems with larger proofs (but smaller prover computation). ZKBoo is one possible choice, but it’s not state of the art anymore. The latest result in this line of work is the scheme of Katz et al, which refines ZKBoo and ZKB++ by introducing new techniques to improve the MPC-in-the-head paradigm on which these proof systems rely. The resulting proof is still of size linear in that of the boolean circuit computing the function you care about (in your case, SHA256), but with much smaller constants and a much better soundness error. This result is the basis of the latest version of the Picnic NIST candidate post-quantum signature scheme Picnic v2. This candidate has been fully implemented, optimized, and benchmark, and you should find all the data you want in their detailed specifications.

(Quick note: all the above are described as NIZK, but what they do is in fact constructing an interactive zero-knowledge proof system, and then making it non-interactive and heuristically secure using the Fiat-Shamir heuristic).

There are many other tradeoffs in between SNARKs and Picnic. Here, I could mention dozen of candidates (Aurora, STARKs…). One particularly interesting « middle spot » is Ligero: it achieves proof size $O(\sqrt{|C|})$ ($C$ being the boolean circuit computing SHA256, in the concrete case you consider), at reasonable computational costs. Actually, this protocol was used as the basis for a company providing solutions for decentralized anonymous cryptocurrencies.

Answering questions from the comments

One thing I do not get is which techniques would "just" encode SHA-256 as a boolean-SAT problem, or if (and how and to what degree) it is critical to make use of regularities. Like a lot of XOR, or a lot de 32-bit additions can come for free according to section 5.1 there. This matters because I could come with an approximation of the size fo SHA-256 as 3-SAT, but I do not understand if that's relevant.

Right, theoretical cryptographers have a tendency to forget about the "practical" issue of encoding your instance into the appropriate model the ZK proof is built upon :) But here are some details:

protocols built from the MPC-in-the-head technique (ZKBoo, ZKB++, Picnic, Picnic v2) can essentially benefit from any "MPC-style" optimization. There are way too many variants of MPC protocols to cover every subtlety, but a good rule of thumb is as follow: MPC will deal with boolean circuits, or arithmetic circuits. XORs, or additions, will cost nothing. The default "cost" is the number of ANDs, or multiplications. If your function is well written as a mixture of arithmetic and boolean operations (like, XOR, AND, and addition over $\mathbb{Z}_{32}$), then you can use MPC protocols tailored to evaluate these operations efficiently. But I cannot tell you by default what will be the best choice: that depends on the current MPC literature, and that's hundreds of new papers per year.
If I use the Picnic signature scheme as an example, they use an MPC protocol which works especially well when the circuit is a boolean circuit, with XOR and AND gates, with an arbitrary number of XOR gates but as little AND gates as possible. This is why they replace SHA256 by another hash function, LowMC, chosen to minimize the number of AND gates in its boolean circuit.
SNARKs, which achieve minimal proof sizes, rely on a different representation: quadratic span programs. Hence, to get a SNARK for SHA256, you must first encode SHA256 as a quadratic span program. I do not know how efficiently this can be done, but it has already been done: SHA256 is implemented in libsnark.
Ligero relies on representing the function (e.g. SHA256) as an arithmetic circuit. Then, for each gate of the circuit, a constraint is added to some list of constraint, depending of the gate type, and an "Interactive PCP" is built on top of this representation as a list of constraints. As for ZKBoo and others, they can get a better result by not decomposing the additions over $\mathbb{Z}_{32}$ as XOR and ANDs, but by treating these ring additions as individual constraints directly (see the Ligero paper, page 2100). SHA256 is explicitly used as a benchmark in their paper: they achieve proof size 34kB, prover runtime 140ms, and verifier runtime 62ms.

Answering more globally the first part of your question:

One thing I do not get is which techniques would "just" encode SHA-256 as a boolean-SAT problem, or if (and how and to what degree) it is critical to make use of regularities.

All techniques can "just" encode SHA256 into the right representation (boolean circuit, arithmetic circuit, or quadratic span program). All concrete implementations will try to optimize as much as they can this representation ,e.g. by finding a way to deal directly with the ring operations involved in SHA256. Unfortunately, people do not usually implement the "naive, brainless" representation together with the optimized one, so it is hard to estimate what is the cost of not optimizing the representation. But just to give a very rough sense of it, naively representing SHA256 solely with XOR and ANDs can give a representation up to two orders of magnitude larger than when dealing with the ring additions in a more clever way.


I've seen answers here and elsewhere discussing how well the WWII Enigma could hold up to modern cryptanalysis, ...

Ehm, quote? I would say, the general opinion about the Enigma is actually the very opposite. The Enigma is the prime example why such a drastic change in the cryptographic mindset was necessary, where it is not enough if you can't break your own cryptosystem yourself.

Cryptanalysis has gone a long way since then, and today it is not enough to be resistant to ciphertext-only attacks. Back then, the attacks on the Enigma were made much easier by having some partial known plaintexts.
Today we even assume the attacker to have a lot of plaintext/ciphertext pairs. And known-plaintext attacks are the very least what we consider secure today.

So building a new scheme from an old-and-broken design is quite a bad idea. In today's binary world (in computers) using any other alphabet does't make sense.

And then there is one more thing: You suggest having an RNG responsible for the choice of the rotors. They are what provides confusion and diffusion in the Enigma... but randomly chosen functions are really bad at that. There is a reason, why those steps are never chosen randomly in block ciphers.

So to answer your questions: Probably you can break it with a known plaintext attack within seconds on a normal computer. Brute force or ciphertext-only attacks don't matter at all (unless brute-force is the best known stragety). So even if the brute-force attack cannot be done within reasonable time, it doesn't matter.


Does iterative hashing of mouse/keyboard input improve its properties as an entropy source?

The biggest problem with capturing mouse & keyboard input is that the number of likely things a user does within a small timeframe is limited.

Imagine that you hash 3 alphanumeric characters of userinput H(X1 + X2 + X3) (assuming + means concatenation and H is a cryptographic hashing function). The number of possibilities from 000 to ZZZ would be about 62^3. Now if instead you would use H(X3 + H(X2 + H(X1))) the number of possibilities would still be 62^3. You could even use something like pbkdf2 with a ridiculous number of iterations without changing the number of possible outputs.


Pailler and Gentry - homomorphic encryption

You seem to have some conceptual misunderstanding. A homomorphic property of an encryption scheme does not necessarily mean that it is deterministic.

There are examples like textbook RSA which has a multiplicatively homomorphic property (multiplying ciphertexts modulo the modulus gives you a ciphertext to the product of the two hidden plaintexts modulo the modulus), but is insecure due to its deterministic property, i.e., no IND-CPA security. Loosely speaking, you can test against given ciphertexts by trial encryptions using the respective public key with candidate plaintexts.

What is clearly true is that homomorphic encryption schemes can not be secure against adaptively chosen ciphertext attacks (IND-CCA2) as the homomorphism prevents this type of security. But everything below is possible. For instance, Paillier is secure against chosen plaintext attacks (IND-CPA), but is additively homomorphic.

Another (from the point of math) more simple example is additively homomorphic aka "exponential" ElGamal, which is simpler for illustration.

There you work in a cyclic group of prime order $q$, e.g. the order $q$ subgroup of $Z_p^*$ with $p$ being a safe prime, generated by $g$. This version of ElGamal is IND-CPA secure (and thus probabilistic) and works as follows: Let $y=g^x$ be the public key and $x\in Z_q^*$ be the private key. You encode a message $m\in Z_q^*$ as an element $g^m$. To encrypt this message $m$ you choose a random $k\in Z_q^*$ (the randomizer) and the ciphertext is $(g^k, g^m\cdot y^k)$ (note that decryption yields $g^m$ and you have to compute discrete logarithms to get back $m$ - so this is only attractive for small message spaces but this does nothing to the example here). It is easy to check that given two ciphertexts to $m$ and $m'$ and randomizers $k$ and $k'$ respectively and multiplying them componentwise gives you a ciphertext to $m+m' \bmod q$. Note that the resulting ciphertext is a ciphertext with respect to randomness  $k+k'  \pmod q$ and if both $k$ and $k'$ are random and hidden (which is the case) so is  $k+k'  \pmod q$. So this scheme is additively homomorphic but still probabilistic (IND-CPA). Same holds for Paillier and FHE schemes are usually also probabilistic - as it is the case for Gentrys first construction (I just used ElGamal as it is simpler to present).

Hope this helps - its hard to type such answers on a mobile :)


It is believed to be hard. In fact, even given $G, xG, x^2G,\dots,x^{n-1}G,x^{n+1}G,\dots,x^{2n}G$, you still can't compute $x^nG$; this is called the Generalized Diffie-Hellman Exponent assumption (see Fig. 1 here).


Arguing security of an encryption scheme

If the adversary knows $L$, then he can find $L^{-1}$, the multiplicative inverse of $L$ modulo $q$ where $q$ is the order of $g$. Then he can compute $g^r =((g^L)^r)^{L^{-1}}$. Once he find $g^r$, he can compute $m$ by eliminating $g^r$ from $m\cdot g^r$.

If the adversary knows only $g^L$, then it is ok. This case is like El Gamal. Let $h=g^L$, what you reveal is $(h^r,m\cdot g^r)$. Your private key is $L^{-1}$.


Most efficient conceivable padding mode, and with no padding oracle

Your scheme leaks information about the plaintext, outside of the length of the message. To be precise, it may leak the information that the last byte is between 1 and 16 or not.


You are forgetting that messages usually consist of many blocks and that many messages contain much more structure than just English text. For example an RSA private key will, when encoded, have a easy to distinguish header and will consist of many blocks of plaintext / ciphertext when encrypted with a block cipher. The same is true for Word documents, XML messages, images and many other formats.
Otherwise, it is a simple game of chance. At each block that decrypts correctly according to the available information, you get more confident that you've found the right message. However, you can choose a block for which you have the most information and only continue decrypting the next block once you've found a match. That way you can very quickly filter out wrong keys.
For instance, for English text you'll generally know at least one bit: the highest one bit of ASCII text is always zero, so that already makes 8 bits per block that you need to get right. Assume that you've got another 2 bits per byte / character simply by checking if the English text is consistent after that. Then you only need to advance to the next block once in $2^{8 \cdot 3} = 2^{24} = 16,777,216$. During the calculation of cryptographic strength, we can safely ignore that kind of detail. If the message is very small then such analysis will indeed fail, and you cannot tell if the key is correct or not. This is easy to show by looking at single bit encryption, e.g. using stream cipher mode such as CTR.
As indicated in the comments, generally we also assume that messages have integrity protection and provide message authentication, usually through authenticated cipher modes or explicit inclusion of a Message Authentication Code (MAC) / authentication tag. In that case, the correctness of the key can also be verified through that code. For most modes that add at least 64 bits to test (128 bits for most authenticated modes and 256 or more if HMAC is used).
Usually, for attacks, we assume that (part of) the message is known, i.e. known plaintext for a known-plaintext attack at the very minimum. Ciphers are expected to be even more secure than that: allowing the attacker to choose which messages get encrypted while leaking no information about the data (other then information about the message size). In other words, the ciphertext should be INDistinguishable from random under a Chosen Plaintext Attack, i.e. IND-CPA secure.


RSA-OAEP versus RSA with Fujisaki-Okamoto construction

The Fujisaki-Okamoto construction requires a non-deterministic public key encryption scheme. Textbook RSA is not randomized, but deterministic, and so it cannot be applied to it to obtain CCA-security. It can be applied to schemes like Elgamal and Paillier that take randomness to create indistinguishable encryptions of the same message.


Selective format-compliant JPEG encryption?

While I haven't heard of previous work on this exact problem,
splicing together some standard solutions to a few other problems almost solves this problem.

There is a loophole in the pigeonhole principle:
if the output file is bigger than the input image,
it is possible to store "extra" information.

Starting from the blurred image you want everyone to see,
you somehow want to add more information to it so that the appropriate people can extract an unblurred image.

picture frame

Perhaps you could keep every pixel of that blurred image unmodified, and add something like a picture frame above, below, or all the way around the image to store extra data,
like the way dotless QR codes store extra data without modifying the center parts of the image.
There's been a lot of work on designing barcodes in such a way that it's possible to recover all the original data, even when the barcode is distorted far worse than simply uncompressing a JPEG and then recompressing with worse quality settings.
If you have a very wide bezel picture frame, it may be possible to encode (an encrypted version of) the entire (unblurred) original image file in the frame in the form of a standard barcode.
If you create a "residual image", the difference between the (unblurred) original JPEG file vs the blurred JPEG image in the middle of the frame, that residual image should be all-zeros except for the regions that were blurred out, and so (a compressed and then encrypted version of) the residual image should require far fewer bits to encode than the entire original image, and therefore require a narrower frame around the blurred image.

borderless

If you want steganography and you think the frame is too much of a giveaway, there seems to be a bunch of research on digital watermarking designed to be robust enough to survive uncompressing a JPEG, making minor modifications to it, and recompressing.
Perhaps you can tweak such watermarking and steganography techniques enough to store (a compressed and then encrypted version of) the residual image.
"Hide data in files with easy steganography tools";
"How can you hide information inside a jpg or gif photo?";
etc.
If that doesn't give you enough storage space to store the entire residual image, perhaps you could scale up the image (each pixel of the blurred original image expands to 4 pixels of the expanded image),
giving more area to encode data.
Or perhaps you could scale up the blurred image, and then apply something like DataGlyph halftoning to create an image that from a distance looks like your blurred JPEG file, but the Dataglyph digital halftoning contains (a compressed and then encrypted version of) the residual file or the entire (unblurred) original file.


Decrypt all RSA ciphertexts if you can break 1% of them

The attacker wants to find $m = c^d$ but doesn't know $d$, but they can find $m'=(c')^d$ for a significant fraction of random $c^\prime$s. Assume that $\mathrm{GCD}(c, n)=1$.

The attacker chooses a random $r$ with $\mathrm{GCD}(r, n)=1$ and computes a new ciphertext $c^\prime$:

$c^\prime = c \cdot r^e$

This ciphertext is uniformly distributed among all ciphertexts with $\mathrm{GCD}(c^\prime, n)=1$. So the attacker has a 1% chance that they can compute the corresponding message $m^\prime$. If it doesn't work, the attacker simply chooses a new $r$.

Relate $m'$ to existing variables:

$m^\prime = (c^\prime)^d  = c^d \cdot r^{e \cdot d} = c^d \cdot r = m \cdot r$

Solve for $m$:

$m = m' \cdot r^{-1}$

$r^{-1}$ can be efficiently computed using the extended Euclidean algorithm. This means that an attacker who can break a significant fraction of messages can break all of them.

We assumed that GCD(c, n)=1. If it's not, that GCD is a factor of $n$. In the two-prime RSA case this is a complete break. In multi-prime RSA divide out that factor and you're back to the GCD(c, n)=1 case.


Advantages/disadvantages of using symmetric encryption function as hash function?

The disadvantage of this approach is that block ciphers are not necessarily designed with this goal in mind. Specifically, AES has related-key problems, and DES completely breaks in Davies-Meyer. In general, block ciphers are not necessarily ideal ciphers and should be used as intended which is as pseudorandom permutations. In contrast, SHA256 and the like were constructed specifically with the collision resistance goal in mind. It doesn't mean that they achieve this goal, but they have a far better chance.


Randomized public-key encryption as binding commitment / "collision-resistance"?

Yes, this is a property that most randomized public-key encryption schemes have. In fact, every standard public-key encryption scheme you could think of satisfies this property (e.g. RSA-OAEP, ElGamal, Goldwasser-Micali, Paillier...).

However, the binding property is not implied by the semantic security of an encryption scheme. In fact, under very strong cryptographic assumptions (the existence of a primitive called indistinguishability obfuscation), there exists public-key encryption schemes which are deniable, in the sense that for any ciphertext $c$ and any plaintext $m$ (possibly different from the one encrypted in $c$), a party can always find a randomness $r$ such that $c = \mathsf{Enc}(m;r)$ (see this paper). Such encryption schemes are interesting objects (intuitively, they would allow to guarantee security even if the government break into your house, point a gun on your head, and asks you to reveal the random coins that you used to encrypt a message - with a deniable encryption scheme, you will always be able to lie and to claim that you encrypted an innocent message). By definition, such encryption scheme are semantically secure but not binding.


A video camera can obtain entropy, but only at a fairly low rate and only if allowed to see "unusual" scenes… like someone making funny faces, unusual movements, etc. Of course, this only works in a room with no video bugs.

Theoretical explanations…

Depending on your knowledge-range, the following sources may be able to explain ways webcams can be used for random number generation:

Patent US 5732138 A — "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system."
Inventors: Robert G. Mende, Landon Curt Noll, Sanjeev Sisodiya
Original Assignee: Silicon Graphics, Inc., Filing date: 1996-01-29, Publication date: 1998-03-24
Random Numbers Generated from Audio and Video Sources
2013, I-Te Chen, Department of Healthcare Administration & Medical Informatics,  Taiwan
Random Number Generated from White Noise of Webcam
Jer-Min Tsai, I-Te Chen, Jengnan Tzeng
2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing
ISBN: 978-0-7695-3762-7

Getting more practical…

If the above is too theoretical for you and you want a more practical explanation of how it can be done, there's a cool "how-to" article at inventgeek.com that shows how to create an "alpha radiation visualizer" from scratch within an hour… using a webcam and a regular smoke-alarm device as radiation source.

EDIT

Sometimes I stumble upon a wave of disinformation wobbling through the internet (and I’m not talking about Crypto.SE in this case, which seems to have escaped this particular wave so far). Most of the time I manage to keep my mouth shut, but this is one of those rare occasions where I felt the urge to draw a clear line between amateur chit-chat and actual cryptographic security. After all, when creating your own “randomness” thingy, you do not want to step into the most obvious pitfalls… do you?

Always remember that it only takes a tiny glitch to make your “randomness” thingy as insecure as leaving your key stuck in your front-door.

For example: I repeatedly have to disagree with people telling the world it‘s OK to rely on JPEGs provided via their webcam software, which are auto-stored on their disks and later fetched to extract “randomness” from those images. Let’s be clear on something: when doing so you are actively ignoring several issues, both from a cryptographic as well as from an infosec point of view.

Time to dive into some stuff, just for the fun of providing some food for thought…

Trust

How trustworthy is that 3rd-party webcam software you are relying on?

Think about it for a second before we simply skip this rather tin-foil hatted question, assuming you absolutely trust your webcam software because (for example) you coded it yourself.

To further limit the scope of my edit, I’m also skipping the talk about the potential issues arising from storing those images to HDs, USB sticks, or whatever storage medium you might be using. Besides the fact that this would quickly wander off into InfoSec realms, only you can know if we can or should assume your disks and system to be safe from any 3rd party access at all times because (for example) you’re the best sysadmin known to humanity and never sleep anyway.
JPEG is not even close to raw signal data!

Do not just jump for the next image format available, unless you know what the specific image format (read: file format) actually contains, how that format may influence the security of your implementation, and how potential implications of individually chosen image/file formats can be secured.

If you don‘t plug into the webcam hardware directly, at least be smart enough to use as much raw signal data as you can get… and one thing is for sure: using JPEG is not the smartest choice. Remember that JPEGs (like most image formats) introduce a repeated and predictable data block (the image header), and lose some of the wanted entropy (due to the lossy data compression – among other things) while all that post-processing takes time. To lift related issues, you‘ld have to post-process the already software-processed “random data” which created the (to stay with the example) JPEGs. By now, your own logic should already be screaming at you that using raw image data extracted directly from your webcam hardware is the smarter, safer, and faster choice.

Personally, I’ld advise you to either use raw signal data (available via hardware modification), or to grab raw image data directly from your webcam (using appropriate software and/or drivers).
“Webcams only offer JPEG” and “Webcams don’t offer raw image data” are blunt lies!

Sooner or later, you will stumble upon some people that try to tell you it’s not possible to grab raw image data from webcams and that webcams only provide JPEG output. While I somewhat admire the boldness of people pushing out such balony into the digital voids, I honestly can’t help feeling the need to explicitly state that they are absolutely wrong.

What those people are forgetting (or actively ignore) is the fact that it‘s not the webcam itself, but the webcam software which produces those JPEG images from raw image date that software grabs from the webcam. Besides potential licensing restrictions related to individual hardware, there is no reason why you wouldn’t be able to do the same raw image data such webcam proggies use – without applying JPEG compression or other image processing.

For your convenience, here are some hints of software projects which are able to grab raw image data from webcams… just in case you ever feel like proving such claims wrong:

fswebcam (quote: RAW - Reads images straight from a device or file.)
AviRaw - read raw webcam AVIs (which is – among other things – used to look at the stars)
An Image Grabber for the Creative WebCam Go

Please feel motivated to do your own research. Search engines tend to spit out truckloads of alike software solutions and sourcecodes which practically enable you to grab the raw image data from various webcams and related systems.

From this point on, be confident that anyone claiming it can‘t be done is either not informed, or bluntly hiding his/her ignorance behind an easy to uncover lie. Don’t waste your time on such people – simply turn around, take a deep breath, and try to find someone smarter to talk to.
Always “Combine & Hash”

It doesn’t take a 3-letter agency sitting in a black-windowed van to ruin your “randomness”. In fact, even that old microwave oven your neighbour uses might be that ill-placed that it influences the noise which you hope to gain from your hardware. Badly shielded speakers also tend to do their badness. And 3rd-party wifi activity as well as mobile phones outside of your home also have a good chance to skew your noisy pattern. Shielding your webcam as well as the rest of your hardware might be an option, but to keep it short: one should always assume raw signal data can and will be messed with actively and/or passively… and it’s pretty unlikely you will be able to detect such influences ad-hoc, if at all.

Due to that, I heartly recomend to generally push the captured (raw) signal data – preferrably combined with additional random data from other sources – through a cryptographically secure hash. Sure, a cryptographically secure hash takes its time to be computed… but it‘s much better to invest time in a good hash than in some superfluous image format processing (and post-processing to lift related issues) as described above in #2.

Depending in your individual setup and scenario, a HMAC might be even more applicable as it can help protect you in some of the extremer “failing randomness” situations where a regular (cryptographically secure) hash might fail to protect you.

Or you could get a bit crazy like I did when I created something related as a hobby project a few years decade ago. I ended up feeding some randomness sources to AES in CTR mode, while pulling random IVs and keys from a hashed combination of other randomness sources… think: encrypting combined random sources with IVs and passwords generated from hashes of other combined random sources, where all random sources are absolutely independent of eachother. Most of you will surely agree that this setup was more of a “crypto-overkill”… still, it was able to blow “blindly trusting what webcam & co. provided” out of the water. To my defence: I was young and über-motivated… ever since, I’ve learned to create smarter things with less overhead. ;)

Cryptography is only as smart as you implement it.

It should be noted that hashing data (either via a hash or a hmac) surely won’t save you from breaking your neck in every potential scenario, but when you watch your steps by combining raw webcam data with other independent randomness sources, hashing the lot holds the potential to increases the chances of (cryptographic) survival of your home-made “randomness” thingy.

Nevertheless, things like “still images” hold the potential of providing not enough entropy. Which is one of the main reasons why you shouldn’t generally assume ”any pic is OK” and – whenever possible – mix randomness extracted from your webcam with other randomness providers (either hardware or software based). If you don’t know what other randomness source to use, here’s a hint: at the time of writing, all major operating systems provide their own way of extracting cryptographically secure data via software. If that’s news to you, RTFM.

/* Nota Bene: Since point #4 might inspire some cool Crypt.SE questions, I’ll leave it standing as unspecific as-is. */
To build a new car, you don’t have to reinvent the wheel.

Be sure not to get caught up in an “I‘ll create my own…” mantra just because you‘re fiddling with your own hardware. There are dozens of well-vetted solutions in the realms of cryptography that may be able to fit your individual setup, implementation, and/or needs – which practically means there might be no need for you to “create your own”. In case of doubt, click that “ASK” link and throw in your question with a short but on-point description of what you’re trying to achieve. There are ample experts around here at Crypto.SE who are able to answer near to any crypto-related question you might have. It’s always better to ask for help and infos, than to be sorry later on.


Associative but NOT Commutative Reducing Function Construction with Existing Hash Function(s)

I don't believe that any such function can meet the requirements of associativity, pre-image resistance and the 'hard to find commuting operands' simultaneously.

Here's why: suppose we have a preimage $a$; we first check if $H(a,a)=a$.  If it is, we found a preimage.

If $H(a,a) = b \ne a$, then we have $H(a,b) = H(a,H(a,a)) = H(H(a,a),a) = H(b,a)$ (because of associativity), and hence we found a commuting pair.


How (generally) do modern schemes deal with an adversary with the capacity to either instantly, or over time, corrupt a majority of parties

There is a model, typically called proactive security (and sometimes also called a mobile adversary), that considers the case that parties can be corrupted and later uncorrupted. Time is divided into epochs and security holds as long as the appropriate threshold of parties is honest in each epoch. In the dishonest majority case, this means that unless all of the parties are corrupted in a single epoch, security is preserved. These protocols work by rerandomizing secret sharing and enforcing correctness.


Which compound algorithms would weaken cipher, not strengthen it?

Moving my reply from the comments into a proper answer. The general case of double-encrypting is formally explained by Yehuda Lindell in this answer on crypto.SE. Summing up:

Same Algorithm, same key: It may or may not be secure, depending on the properties of the cipher. It is definitely not always secure, but may be secure for practical cases.
Same Algorithm, different keys: Secure, because otherwise people who do not know the key could break the encryption by encrypting with a different key, which would be... strange, and not very logical.
Different Algorithms, different keys: Secure, for the same reason. Otherwise, sending PGP-encrypted eMails over a TLS connection would be unsafe, which would be ridiculous.
Different Algorithms, same keys: Insecure. Never reuse keys for different encryption algorithms (even when not double-encrypting). For example: If you are using the same RSA keys to sign and encrypt, and the adversary can get you to sign a value for them, it can use you to decrypt data, because signature = encryption with the private key = decryption of data encrypted with the public key.

Summing things up: "Don't double encrypt" is a pretty general hint that definitely doesn't always apply, but it serves as a good baseline to avoid critical mistakes. The more nuanced version is "Don't reuse keys for different algorithms, and to be sure, don't double-encrypt with the same key and algorithm, either, it may hurt you".


No, you can use the same HMAC key for any message, including an already HMAC'ed message (regardless if the HMAC value is encrypted or not).

The key in HMAC is protected by the one-way hash function used internally, so getting the key should be hard.

The collision resistance and other security properties will also prevent an attacker from generating a HMAC based on a previous HMAC value. The way that HMAC is preventing length extension attacks may be very important in that regard, because Merkle-Damgård based hashes do (generally) not protect against those. MD5, SHA-1 and SHA-2 (but not SHA-3) are all MD-hashes and vulnerable to length extension attacks.

It is much harder to proof that using the same key for AES is also secure. There may be a mathematical way of retrieving key data if the key is reused in any kind of algorithm. The chance that it is possible to use relations between the algorithms to get information on the key or plaintext message is rather small though. Still, most cryptographers would prefer to use a separate key for different algorithms unless any weakness has been ruled out (as in most AEAD schemes that use a single key, for instance).

Note that this answer is for the security of the HMAC construction itself rather than the security of the entire protocol. Attackers may still perform replay attacks where a previous message and authentication tag are resend to the receiver by the attacker. The protocol should prevent those (e.g. by including a unique message ID in the message).

As Yehuda has already hinted: it isn't apparent if this scheme would be beneficial in any way; you may perform an additional run of HMAC without security benefits. If this is the case or not depends on your use case (maybe you do want to store the decrypted plaintext message together with valid, pre-generated HMAC; that would be a strange use case, but we don't know).


How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?

Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ is the number of bits of the modulus $N$, i.e. the key size of RSA. So 4096 for 2048-bit RSA, double that for 4096-bit.

This paper (PDF) has an algorithm using $2n+3$ qubits, where $n=\log_2 (N)$, where $\log_2(N)$ is the way to calculate the number of bits in $N$.

  How many qubits are required to break Curve25519?

Breaking elliptic curves requires (pdf, see 6.2) roughly $6n$ qubits where $n$ is the order or key size of the curve, which for Curve25519 would be $6 * 255 = 1530$. Less than secure RSA sizes require, but much more than has been accomplished.

  I want to work out the relationship between the key length and number of qubits required to break that key length.

See above.

  Edit: I have found this answer. Anyway if I plug in N = 2048 to the Θ(log(N^2)) equation, this gives me 15.25 qubits required to factor RSA 2048. RSA 4096 bits is not much better, requiring only 16 qubits. Is that correct?! Why is everyone not running around with their hair on fire?

You are using the wrong value for $N$. It is the modulus, not the bit length. The actual number of qubits needed for 2048-bit RSA is about 4096.

Note (from removed comment to the present answer):  We're talking about ideal qubits here. Error correction might increase the number of physical qubits beyond these numbers.