Correct use of Fisher-Yates for subsequent selections

Let me start by trying to rephrase your question in more precise terms.  (Please let me know if this rephrasing doesn't match what you intended to ask.)

Let $\textsf{random}$ be a (pseudo)random number generator that, given a positive integer $n$, returns a random integer uniformly sampled from the set $\{0, 1, 2, \dots, n-1\}$.  I assume that the output of this generator is computationally indistinguishable from that of a true source of independent uniformly distributed random numbers.  (Constructing such a generator is the only cryptographically challenging part here.  Everything else is just combinatorics.)

Let me introduce the following helper procedure, which essentially performs one step of the Fisher–Yates shuffle:

  $\text{procedure }\textsf{rand_swap}(A, n, i): \\
\quad j \leftarrow i + \textsf{random}(n-i); \\
\quad (A_i, A_j) \leftarrow (A_j, A_i).
$

That is, given an array $A = (A_0, A_1, A_2, \dots, A_{n-1})$ of (at least) $n$ elements, and a base index $0 \le i < n$ into this array, $\textsf{rand_swap}(A,n,i)$ picks a random second index $i \le j < n$ and swaps the array elements $A_i$ and $A_j$ (which might be the same, if $j = i$).

Using this helper function, the Fisher–Yates shuffle for an $n$-element array $A$ can be implemented as:

  $\text{procedure }\textsf{shuffle}(A, n): \\
\quad \text{for each } i \text{ from } 0 \text{ to } n-1: \\
\quad\quad \textsf{rand_swap}(A, n, i).
$

Also, the same algorithm can be used to implement a partial shuffle:

  $\text{procedure }\textsf{partial_shuffle}(A, n, k): \\
\quad \text{for each } i \text{ from } 0 \text{ to } k-1: \\
\quad\quad \textsf{rand_swap}(A, n, i).
$

After such a partial shuffle, the sub-array $A^{(k)} = (A_0, A_1, A_2, \dots, A_{k-1})$ contains a randomly shuffled uniform sample of $k$ values drawn without replacement from the original array $A$.

Now, we finally get to your question.  Specifically, as I understand it, you wish to repeatedly draw a random sample of $k \le n$ elements from an $n$-element array $A$, and ask which of the following methods will do:

Method 1:

For each sample, initialize $B$ as a copy of the array $A$, call $\textsf{partial_shuffle}(B,n,k)$ and let the sample be the first $k$ elements of $B$.

Method 2:

Let $s$ be the total number of elements sampled so far.  For each new $k$-element sample, while $s + k \le n$, run the following continued partial shuffle:

  $\text{for each } i \text{ from } s \text{ to } s+k-1: \\
\quad \textsf{rand_swap}(A, n, i).
$

and let $(A_s, A_{s+1}, \dots, A_{s+k-1})$ be the sample.  After sampling, increment $s$ by $k$.

Method 3:

Same as method 1, except that we repeatedly (partially) shuffle the same array instead of reinitializing it every time.  That is, for each sample, call $\textsf{partial_shuffle}(A,n,k)$ and let the sample be the first $k$ elements of $A$, retaining the shuffled array $A$ for the next iteration.

The answer is that, as long as our pseudorandom number generator is indeed indistinguishable from a truly random source of uniform independent random integers, methods 1 and 3 are equivalent.  They both generate a sequence of independent random $k$-element samples from the original array, where the elements within each sample are drawn without replacement, but where different samples are fully independent.

This equivalence follows from the observation that, regardless of the initial order of the array $A$, after each call to $\textsf{rand_swap}(A,n,i)$ within $\textsf{partial_shuffle}$, $A_i$ will be uniformly sampled from among the elements of $A$ not already chosen during earlier iterations.

(If the pseudorandom number generator is not perfect, method 3 may be somewhat better at disguising some of its flaws, especially if a full shuffle is used instead of a partial one.  This is because retaining the state of the array $A$ between iterations effectively maintains a large partially hidden state that carries forward some of the randomness from previous shuffles.  This is the main reason why e.g. physically shuffling a previously used deck of playing cards often yields adequately random-looking results after only a few iterations, whereas a new or deliberately sorted deck of cards needs to be much more thoroughly shuffled before it loses all traces of its original order.)

Method 2, however, does something very different: in effect, it draws individual random elements from the original array without replacement, returning these in blocks of $k$ elements.  In particular, if a given element appears in one $k$-element sample, it cannot appear in any other sample drawn from the same array using this method.

Of course, if the array size $n$ is very large compared to the total number of elements sampled from it (squared, due to the birthday paradox), then the probability of ever seeing the same element twice even with methods 1 or 3 is negligible, and so all the methods are effectively indistinguishable.  But in that case, you might as well not bother with shuffling at all, but simply pick random elements from the original array with replacement, since that will also yield only a negligible chance of ever seeing the same element twice.


How Mutual authentication and Forward secrecy in The X3DH Key Agreement Protocol work?

Bob uploads his signed prekey along with its signature to the server. This can be used to check the key integrity.

After Alice does this, Bob learns who Alice is because she sends him her public identity key $IK_A$ and they compute a shared secret ($DH_1$). Then Alice tells Bob who she is by generating an ephemeral public key $EK_A$ and they generate another shared secret ($DH_2$) that they can both confirm. Notice that at this point, Bob and Alice have authenticated themselves to each other, but since Alice is using an ephemeral key which will be discarded, they cannot prove themselves to a third party (deniability). This is why they don't just compute $DH(IK_A, IK_B)$.

Right after she calculates the secret key $SK$ Alice deletes her private ephemeral key and the DH outputs, but she sends the public part $EK_A$ as part of the initial message to Bob, who does the exact same calculations. The important part is that $EK_A$ is ephemeral and so will be deleted, providing forward secrecy.

If there's a one-time prekey and you get a $DH_4$, that only gives the $KDF$ more key material to enhance the security of the secret key. But it serves the same purpose of forward security that $DH_3$ does.


Does Ed25519 support cryptographic threshold signatures?

Threshold (robust) m-of-n variant of Schnorr signature scheme is known:

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could be solved with Shamir scheme (interpolation) for Schnorr signature, namely re-construct response s from shares of k and x (wikipedia notations). No trusted dealer is straightforward for Schnorr scheme while choosing x and k, to meet points 1 and 2.

Schnorr scheme admits efficient verifiable threshold variant without any trusted dealer (like while signing key generation). Efficient means combining partial signatures needs just a single interpolation for a known linear combination of secrets (that is, signing key and k) and another interpolation for random group element gk. Verifiable means any error (like misbehaving participant) will be detected. Threshold means any m honest participants will produce a signature. At last, "threshold" signature is verifiable as usual one, the same equation.

Let me refer to "High-speed high-security signatures", section "The signature system", subsection "EdDSA keys and signatures". Verification equation is similar to Schnorr scheme, with multiplier 8; signature is response S, initial random r, random group element R, actual secret a. It fits well. Ok, we have "-" sign while calculating response with original Schnorr scheme.


Your answer is in the paper Elliptic curve cryptosystems from Neal Koblitz:

Set up an elliptic curve $E$ over a field $\mathbb{F}_q$ and a point $P$ of order $N$ just the same as for EC-DDH  as system parameters.
You need a public known function $f : m \mapsto P_m$, which maps messages $m$ to points $P_m$ on $E$. It should be invertible, and one way is to use $m$ in the curve's equation as $x$ and calculate the according $y$.
Choose a secret key $x \in_R [1,N-1]$ randomly, publish the point $Y=x P$ as public key.
Encryption: choose random $k\in_R [1,N-1]$ , then calculate $C=kP$ and $C'=kY$ and calculate $P_m = f(m)$. The ciphertext is the tuple $(C, C'+P_m)$.
Decryption: From a ciphertext $(C,D)$ calculate $C' = xC$, and retrieve the point $P_m$ with $P_m = D-C' = (k(xP)+P_m)-(x(kP))$. Then calculate the message $m$ with $f^{-1}(P_m)$.


Discrepancy between 3DES in OpenSSL and PyDES

In Python and on that website, you're entering a key. A 3-DES key consists of 24 bytes. You picked a key that's some nice printable text, but a key in general is binary, randomly generated.

With the OpenSSL command line, you're supplying a password (or passphrase, the two words are synonyms). A password is not a key: it's typically not fully random, consists only of printable characters, can have any length, ...

OpenSSL uses a key derivation mechanism to calculate a key from that password. To generate a key from a password, you need to perform stretching and randomize the process with a salt, which OpenSSL does, although not very well.

To get the same result with openssl en, tell it that you're supplying a key, with the -K option.

Generally speaking, the openssl command line is more of a demonstration tool than a tool for serious usage. This is especially true of commands like enc. Don't expect things to be secure unless you have a very precise of what you're doing.

In any case...

  triple DES ECB

Hopefully this is for learning purposes, and even then, neither 3DES nor ECB have any advantage for learning. 3DES is an obsolete algorithm with no benefit over the modern standard AES or modern alternatives such as Camellia and ChaCha20. ECB is not really a proper mode, it's “don't bother with a proper mode”, and it isn't secure (so why bother encrypting?). Use a mode such as CTR or CBC for encryption (and learn to use an IV, which is necessary for any mode), or a mode such as GCM or CCM for authenticated encryption.


Is Finite Field Multiplication Distributive? Moving Affine Transform in AES

From the above question $m = da_0$

At the bit level:

$m\oplus b = [m_7 \oplus b_7 , m_6 \oplus b_6 , m_5 \oplus b_5 , .... , m_0 \oplus b_0 ]$

$
\begin{align*}
2(m\oplus b) =& \operatorname{xtime}(2(m\oplus b)) = \\
=& [m_6 \oplus  b_6 , m_5\oplus b_5 , m_4\oplus b_4, m_3\oplus b_3 \oplus (m_7\oplus b_7), m_2\oplus b_2 \oplus (m_7\oplus b_7) ,\\& m_1\oplus  b_1,m_0
\oplus b_0 \oplus (m_7\oplus b_7),m_7\oplus b_7]\\
\end{align*}
$

Where the multiplication by $02$ is denoted $\operatorname{xtime}(x)$.

$
\begin{align*}
2m =\;& [m_6 ,m_5,m_4,m_3\oplus m_7,m_2\oplus m_7,m_1,m_0\oplus m_7,m_7]\\
2b =\;& [b_6 ,b_5,b_4,b_3\oplus b_7,b_2\oplus b_7,b_1,b_0\oplus m_7,m_7]\\
\end{align*}
$

It follows that:

$2m\oplus 2b = 2(m\oplus b)$

because they result in the same formula at the bit level. You can see a similar result for multiplication by 3.

However, the question also assumes that it is possible to convert $2da_0 \oplus  3da_1 \oplus  da_2 \oplus  da_3$ to $d(2a_0\oplus 3da_1 \oplus  da_2 \oplus  da_3)$ this is not possible because it would require the original to be written as $d2a_0 \oplus  d3a_1 \oplus  da_2 \oplus  da_3$ but matrix multiplication is not  commutative.


Diffie Hellman: Why is $(\mathbb{Z}_{8191}^*, \times)$ an insecure group?

Besides 8191 being too small for real world use, the factorization of 8190 ($p-1$) has all small values. It's factorization is $2\cdot 3^2\cdot 5 \cdot 7\cdot 13$. Having a group whose order is smooth makes it vulnerable to an attack using the Pohlig-Hellman.


What role plays Quantum Fourier Transformation in Shor's integer factorization algorithm?

To do factoring, Shor's algorithm presents a way of finding the the following problem. If I know some natural numbers $g$ and $N$, with $g < N$, where $\gcd(g, N) = 1$, what is the smallest $r > 0$ such that $g^r = 1 \bmod N$. This is called the problem of finding the order of $g$ modulo $N$.

By Euler's theorem, there will be some such $r$ because $g^{\phi(N)} = 1 \bmod N$ for all $\gcd(g, N) = 1$, where $\phi(N)$ is Euler's Totient function.

The annoying thing about quantum computing, as you may have figured out by this point, is that you can create some arbitrary superposition of states and do computation on all of those states in parallel, but then when you want to get an actual value you only get to see one of those answers, chosen at random from the answer distribution. Say for instance we set $a$ to be some quantum state that is the superposition of all integers from 1 to 10 (each with equal probability). Then we compute $b=2*a$. It will multiply all of the states by 2 in parallel and we will get a quantum state that is the superposition of all even numbers from 2 to 20. Now if we "open" the state of $b$ we get a random even number from 2 to 20. Which is pretty useless. We could have just opened $a$ first and done the computation ourselves.

Now, the Fourier transform takes a function and computes the "waves" that it is composed of. For instance the image below (from this site) shows the wave forms of different instruments and their corresponding Fourier transforms. In particular, notice the spikes in the Fourier transform graphs. The first spike corresponds to the period of the function. The other spikes show various harmonics that exist on top of this.

Now, back to finding the order of $g$ modulo $N$. You start with setting $a$ to be a uniform superposition of all numbers from 0 to $q-1$, for some $q >> N$.

You then compute $(a, g^a \bmod N)$. This will now be a superposition of $q$ tuples.

Now comes the important part. $g^a \bmod N$ is periodic. Specifically, if $r$ is the lowest non-zero integer such that $g^r = 1 \bmod N$, then $g^a \bmod N$ is periodic with period $r$. So, like with the musical instruments, if you were to plot $a$ against $g^a \bmod N$, there would be some visible repeated fundamental frequency and a number of other harmonics on top of this. So now if you compute the Fourier transform on $(a, g^a \bmod N)$ you will get a function showing how often different frequencies appear.

Now we look at the register holding the value of the frequency. There is some chance that we will get one of the higher harmonics, but there is a pretty good chance that we will get the fundamental frequency. This frequency corresponds to the period of $g^a \bmod N$, namely $r$. Since this experiment has a certain probability of failing (picking one of the higher harmonics). But if you repeat it some polynomial number of times, you can make the probability of it failing in all of those times as low as you want.


Attack on key exchange with authentication

No, this scheme isn't secure.

As far as I understand your description you are using the hashed public key of Alice as the symmetric key to a cipher, but as you already just send this hash over the line, the attacker can simply decrypt $k$ himself and thereby $k$ isn't established as a pre-shared key. By the way, there's no way to recover $pk$ from $H(pk)$ and thereby you can't public key encrypt $k$ here.

This can however be fixed in one of two ways: a) you don't hash the public key at all and just let Alice send Bob her public key, which he will subsequently use to asymmetrically encrypt $k$ so only Alice can read it. Or b) you just stay with the hash of the public key (and maybe drop the $k$ which doesn't serve any purpose if the channel is guaranteed to be integrity protecting) and let Alice send her public key over the internet in clear. Bob can verify the public key using the trusted hash of it and if the hash of the received public keys match, he can then use this to encrypt a session key.


Can I use the cipher text ouput of only one DES rotation as plaintext to check validity?

Yes, you can, but it's insecure. DES has a different key schedule for each round to avoid linearity and meet-in-the-middle attacks. Also you reduce the strenght of your cipher since not all encryption round embed the whole key. Be aware that you need to swap left part and right part of your data material after each round otherwise it's going to be terribly insecure.


Does knowing that the exponent is in a certain range help solving discrete log?

The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $\Theta(\!\sqrt{k-j})$ group operations.

Let $h:=c\cdot g^{-j-1}$, which equals $g^{i-j-1}$.
Pick some integer $m\geq\sqrt{k-j-1}$.
Initialize an empty lookup table $T$.
For all $0\leq a<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$.
For all $0\leq b<m$, compute $g^{-b}h$ and check if $g^{-b}h$ is in $T$. When a match is found, return $j+1+m\cdot T[g^{-b}h]+b$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.

Correctness:
If the algorithm returns something, it must be of the form $r=j+1+m\alpha+\beta$ with $0\leq\alpha,\beta<m$ and $T[g^{-\beta}h]=T[g^{m\alpha}]$.
This implies
$$
g^r
= g^{j+1+m\alpha+\beta}
= g^{j+1-\beta+(i-j-1)+\beta}
= g^i
\text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)\bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0\leq a,b<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.


How can padding be disambiguated from data, when encrypting using a block cipher?

The usual padding for block ciphers ("PKCS#7 padding") is not a sequence of zeroes, but a sequence of P = N - (X % N) bytes each with value P.

If the message is a multiple of the block size, then a full block of padding is added (where each byte value is the block size).

For example, is the message is 15-byte long and the block size is 16 bytes, than one byte of padding will be added, and the value of the byte is 1. If the message is 14-byte long, two bytes with value 2 will be added. If the message is 16-byte long, sixteen bytes with value 16 will be added.

With these rules, the padding is unambiguous.


What does a "real" quantum computer need for cryptanalysis and/or cryptographic attack purposes?

For example: the 5-qubit quantum computer created at MIT by using the technique of ion traps succeeded in prime-factorizing 15. Does that mean that since it succesfully managed that, that it is a all-purpose quantum computer which could be used for cryptanalysis and/or cryptographic attacks?

No, not even close.
Attacking e.g. RSA requires a lot more than five qubits.
Going from five qubits to, say, a million, is not a simple matter of just making more of the same thing; the physics and engineering needed to scale a quantum computer to a large system is it's own particular challenge.

Qubits experience errors

The simplest and perhaps biggest problem is that the more qubits your algorithm needs, the lower the chance that the algorithm completes without any qubits undergoing an error.
Suppose we need $n_\text{qubits}=100$ qubits to do a useful computation $[a]$ and suppose the number of logic operations we need for the computation is $n_\text{ops} = n_\text{qubits}^3 = 10^6$.
Qubits typically have a certain probability per time of experiencing an error, which leads to the fact that the probability $P$ that a given qubit has not undergone an error is an exponential function of time,
$$P = e^{-t / T_\text{coh}}$$
where $T_\text{coh}$ is the qubit's "coherence time".
Denoting the time of a single logic operation as $T_\text{op}$, we have
$$\ln P = -n_\text{ops}\frac{T_\text{op}}{T_\text{coh}} \, .$$
Supposing we want the qubit to have a reasonable probability to not have an error, say $P=1/2$, we get
$$\frac{T_\text{coh}}{T_\text{op}} = \frac{- \ln (1/2)}{n_\text{ops}} \approx 1.4 \times 10^6 \, .$$
In other words, the qubit lifetime $T_\text{coh}$ has to be a million times longer than the time of a logic operation.
As far as I know, current state of the art is $T_\text{coh}/T_\text{op} \approx 300$ $[b]$, which is a far cry away from $10^6$.

Now, so far we only talked about single qubits, but in order for the algorithm to succeed, we need all of the qubits to go without errors.
With 100 qubits, that puts the target $T_\text{coh}/T_\text{op}$ at $10^{8}$, which, if you ask me, is hopelessly high.

Error correction

  If that's not the case, what exactly would a "real" quantum computer need [...]?

Note that the arguments given above could be used to say that a normal computer shouldn't work!
Of course, we know that normal computers do work, so what's going on?
Regular computer bits (i.e. transistors) have extremely low error rates because they are self-correcting: if the current through a flip-flop fluctuates a bit, the bias circuitry and feedback keep it stable.
This is not possible with individual qubits essentially because you can't monitor a quantum state without affecting it, so there's no way to feed back on fluctuations.

On the other hand, with groups of qubits we can correct errors.
I'm not going to explain the details here, but it turns out that we can use a group of physical qubits to represent a single error-protected logical qubit.
In other words, by encoding the information of a single qubit into a large group of actual physical qubits, we're able to keep the information stable in the presence of errors on the individual physical qubits.
This is called "quantum fault tolerance" or "quantum error correction".
Fault tolerance requires a large set of qubits, probably arranged in a 2D grid, with fast, accurate measurement and logic gates, and the ability to use the results of various measurements to feed back on the qubits with control signals.$^{[c]}$

  ...think: rough description of expected abilities/specs) to enable its user(s) to use it for cryptanalysis and/or cryptographic attack purposes?

A technical, but somewhat comprehensive discussion is given in a review of the surface code by Austin Fowler.

Summary

The experiment with five qubits factoring 15 was far too small to tackle a cryptographically useful problem.
But even that aside, the underlying system is not fault tolerant, so even scaling that system up to lots of qubits wouldn't make it able to solve crytographically useful problems.
To do that, we need a large system with fast and accurate enough logic gates and measurement that it can do error correction.

  And - ignoring rumours about potentially existing but confidential governmental projects - does any such system already exist today?

No, there are no publicly known quantum computers capable of cracking RSA as of 07 March 2017.

As you've alluded, a lot of work in quantum computing has gone secret (e.g. all but one of the jobs I interviewed for after getting my PhD in experimental quantum computing would have required a security clearance) so we don't really know the full story.
That said, based on my and other people's experience in the field, it seems pretty doubtful that any of the secret projects have built a quantum computer capable of e.g. cracking RSA.

$[a]$: I'm not talking about RSA here, I'm talking about the most basic but useful algorithm you might be able to do on a quantum computer.

$[b]$: That's in superconducting qubits but that was a few years ago and there may be better results in other systems now that I don't know about.

$[c]$: I'm being a little loosey-goosey here; not all fault tolerant protocols have the same requirements.
I'm commenting on the ones that I think are most likely to be implemented due to the fact that they have the most forgiving requirements.


What makes AES look like an ideal cipher?

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is indistinguishable from random if the adversary can choose the plaintext input to the cipher themselves (IND-CPA).

The next question is why people think that AES is better than other ciphers with the same key size. Cryptographers generally don't really think that. There are other ciphers that may have better characteristics when it comes to protection against side channel attacks. Other ciphers have a larger % of rounds to spare when it comes to protection against certain attacks. Or they may have a larger block size, or they do not have a clear mathematical structure etc. etc.

AES has been studied a lot, and few attacks have come close to breaking AES. It is relatively fast compared with other block ciphers, and it has a serviceable key and block size. The algorithm is well understood, and there are many hardware implementations of AES, including newer x64 and ARM CPUs. So it is standardized, popular, well understood, but not necessarily the most secure cipher. It doesn't need to be, for most situations it is secure enough.

When you are talking about implementing an ideal cipher you seem to go over the key requirements of a one time pad. The one time pad requires a key the same size as the plaintext / ciphertext. Moreover, you won't be able to distinguish a good key from a bad key for a single block. But what happens if you have multiple blocks to compare? With each block a specific key becomes more likely. As such, it makes very little sense to try and create an ideal block cipher.

The ideal cipher is mainly a theoretical construction, useful in proofs. But beware that inserting an actual block cipher in place of an idealized block cipher may not result in a secure construction. For instance, a hash function could well be secure when constructed using an ideal cipher, while it could be vulnerable with AES-256 due to related key attacks.


What signature schemes allow recovering the public key from a signature?

Well, lets go through the issues:

  It seems to be possible to retrieve the (public) key used for creating an ECDSA signature just from the signature alone

Nope, not quite.  You also need the message being signed. And, with that, it doesn't give you the unique public key; it does allow you to narrow it down to two possibilities (assuming you're using a curve with a cofactor of 1; almost always the case nowadays), however from a single signature, you don't know which of the two possiblities it is.

  In some circumstances, the private key can be recovered as well

I should certainly hope not.  If you can recover the private key with a signature and the message being signed (and you can throw in the public key if you want), then the signature scheme is "broken"; I rather doubt that Mr. Brown claims that ECDSA is broken.

  this can be an advantage (shorter messages, as the public key or a key id doesn't have to be attached)

Well, it's not that much of an advantage; not only does the verifier need to know what the public key is, he also needs to know that it's the correct public key; that is, it is the public key whose private key is held by the person you think is signing the message.  There are a number of ways a verifier can ascertain that; however he must do so; just passing a public key somehow (either explicitly or implicitly) doesn't cut it.

  this can be a disadvantage (if confidentiality is required, the signature has to be encrypted)

Not so much; if confidentiality (rather, anonymity) is required (specifically, you don't want an evesdropper to be able to verify who signed the message), then you need to hide the signature anyways.  If you don't, then the evesdropper does get a copy of Alice's public key, and has a guess for the message can simple check if the message is from Alice by running the signature verification method using his copy of Alice's public key.  This doesn't require any special properties of the signature method.

  Which other cryptographic signature schemes have that property?

I'll go through the ones you listed:

RSA; if the public exponent isn't large, and you use a deterministic padding method, then you can recover the RSA public key from two signatures (of two different messages)
Ed25519; I don't believe that you can recover the public key.  The verification process involves a hash of data including the public key; there's no way to quickly check which public key would make the hash come out correctly.
DSA: I don't believe that you can recover the public key.  The distinction between DSA and ECDSA is that the DSA verification process involves an outer "mod q" operation; that operation discards information that would be needed to recover the public key.


Challenge Response at Application Layer of BLE using ECDSA

Regarding your Q1, well, ECDSA is fine as long as you have a good random generator on the signer side, while deterministic ECDSA tries to address the randomness issues and thus is good (as long as you do not include fault attacks in your model). I personally prefer Ed25519 amongst the deterministic signatures scheme, but that is a question of personal taste, I'd say.

Now, because your challenge is 20 bytes, if you have enough entropy to be sure to generate random challenges, or a way to ensure the increment of a counter value on each challenge in a non reversible way, then you won't be concerned with replay attacks (which would otherwise be a concern with really small challenges).

As for Q2, your biggest concern would be the lack of Threat model! Or if you have one, you should have provided us with it, because the scheme might seem good if you only consider active eavesdroppers, but is broken as soon as you consider fault attack in your threat model (ie. the attacker has the device and can make it perform faults during its computation).

Since the device which would be performing the signature is a phone, I'd say you won't be subject to private key recovery through faults.

On the other side, the Offline BLE device is most likely subject to faults, which may allow to trick the signature validation. See for example the work of Riscure to bypass Secure Boot using Fault Injection, where they bypass such a single verification easily.

Now, another concern is that you have to use an OOB (out of bound) channel to transmit the private key to the phone, which means that you may as well have transmitted a secure LTE key using that same OOB method and you would have arguably (don't hit me) achieved the same goal: only the device knowing that key would be able to communicate with your device...
(Okay, with your scheme, if the Offline Device is stolen, it does not allow private key recovery, but if someone has the ability to recover a key from a BLE device, I'd say they have the ability to perform faults on the signature verification process and trick the device into believing he's speaking with someone who's got the key... thus achieving the same result. Unless you were to authenticate every message sent to the device, in which case it might be a bit harder, but faults of LE devices are generally really easily to perform.)

I don't see any other concern with your design, except that low energy devices generally don't have the power to perform ECDSA signatures, from what I know... But maybe this is old news and not the case anymore.

By the way, you might want to check the http://www.gattack.io/ website, and more specifically to read their whitepaper (even if it seems a bit dated).
From what I've read, it looks like you really should use BLE 4.2, which features ECDH for the LTE key exchange. (Yet, I haven't found much information on that topic). If you are compelled to use a prior norm, or can't rely on ECDH, then it seems like only BLE link-layer in OOB mode is actually secure.


Is there a cipher that avoids double bigrams?

The Playfair cipher would partially avoid this in that it does not encipher two letters that are the same. So the letter pair "LL" would be enciphered as "LX" "L_" (or sometimes just "LX"), producing different ciphertext letters for each pair.  It would allow ciphertext letter repeats of the form "AB BC" where "AB" is one pair of letters that are enciphered together, and "BC" is the next pair of letters that are enciphered together.  Indeed, this would occur when enciphering "at ta" (such as in "attack").

Looking at a list of classical ciphers, I don't see any others that would even avoid double letters to that extent.

You may want to look here which discusses the frequency of double letters in bigram frequencies.  In particular, "LL" is the most common double letter bigram in English, and  occurs 0.577% of the time, and only "LL", "SS", "EE", "OO", and "TT" (and almost "FF") beat the random bigram frequency of 0.148%.  I'm not sure if this counts repeats of the form "at the" or not.  So if the bigram frequency depends on the plaintext, double letters bigrams would generally be less common than other bigrams.

Another factor that probably comes into play is that "aa" is more noticeable than "ax", even if the frequencies are the same.


How much would an unexpected hash collision undermine the security of a hash function?

In many cases the collision might be exploitable to create many other collisions.  In almost all common constructions you could use the collision to build a collision of messages with arbitrary suffix.
Building a useable collision for most attacks like colliding pdfs requires something about the prefix.
But even without a known attack on the relevant prefix I would be worried a different exploitation scenario exists.
Also I would be very worried about such "luck" which may suggest either:
a. The chance of collision is much higher than it seems
b. There is an efficient way of generating collisions it's simply not public.

Furthermore the structure of the collision may give important cryptographic insights.

So for a random collision I don't know of an exploitable attack. I worry there is such, I worry the collision could be extended, the crypo is weaker than it seems and may have already been broken. I would migrate away.


I think it'd be more accurate if one says "if IV were chosen arbitrary and / or unknown, then backdoors might be possible".

From what I know, the SHA256 IVs are chosing from the fraction parts of well known irrational numbers (though I'm not sure it's sqrt(2) or pi or something else). This way, the only being(s) capable of crafting a backdoor, would be the supreme being(s) beyond our Universe.

Similarly, in RFC 3526, modulus is chosing using pi to avoid backdoors. As a side note, sadly, small modulus are vulnerable to mass pre-computation attacks.


Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$?

While this is not a total answer (it does not discuss polynomial arithmetic), the Big Integer Design section of the BearSSL page seems like a good resource to share on this problem. Many of the algorithms are roughly similar to those in chapter 14 of Handbook of Applied Cryptography, but care has been made to make them constant time (not all of the algorithms in chapter 14 are by default). In general BearSSL aims to be a "pedagogical" implementation of TLS. Practically speaking, this means it is well-documented, and algorithmic decisions seem to be explained well.
I have not yet looked into algorithms for $\mathbb{Z}/n\mathbb{Z}[x]$ or $\mathbb{Z}/n\mathbb{Z}[x]/(f(x))$, so won't accept an answer until I get to there (or someone else suggests references).


Error Detection/Correction technique for Encypted Data

Not only is it easier to do error correction/detection after encryption, it is risky to do the error correction before encryption.

This is because the attacker would know parity check relations (in the typical case of a linear code being used) between the bits of the plaintext, which could get them started on an attack.


They trick you with the IV. The IV must be the same for encryption and decryption so that the encryption has the functionality that is;
$$ m = D_k(IV,E_k(IV,m))$$
To surprise you, they modify the IV according to their desire but you failed to see that. This is the more general case of the Bit-Flipping attack on the CBC mode.
This attack works because the message has only one block and the change on the IV only modifies the first block. Nothing special there.


Parallel variant of Carter-Wegman MAC with incremental property

How about GMAC?  It's a Carter-Wegman MAC that meets the requirements of being fast to compute, and parallelizable.

In addition, it can be securely updated, that is, given a long message, you can compute the MAC of a modified version of that message faster than recomputing the entire MAC. For example, suppose you have a message/nonce/tag triple of $(N, M, T)$, and you want to change block $i$ of the message $M$ from the value $a$ to the value $b$ (where $i$ counts backwards; $i=0$ is the last block, $i=1$ is the next to last block).  To do that, you create a fresh (never used before) nonce $N'$, and compute:

$T' = T \oplus (H^{i+2} \times (a \oplus b)) \oplus AES_k(Pad(N)) \oplus AES_k(Pad(N'))$

With the result being the triple $(N', M', T')$, where:

$k$ and $H$ are the key and secret values within GMAC
$\times$ and $H^{i+2}$ are computed within $GF(2^{128})$
$\oplus$ is exclusive or (which is addition within $GF(2^{128})$)
$i+2$ is computed with normal addition (not $GF(2^{128})$ addition).
$AES_k(X)$ is the AES block encryption (ECB mode) of the 128 bit block $X$
$Pad$ converts the nonce into a 128 bit value (for 96 bit nonces, this is just postpending 4 0x00 bytes; for other sizes, it's more complicated).

This takes $O(\log(i))$ time (and can be done faster if you precompute $H^x$ of various values of $x$), which I believe meets the incremental requirement.


"Perfect Steganography" is not well defined. Whatever that is, it must obey Kerckhoff's principle: adversaries know all about the system, except non-public keys. That's enough to exclude many steganography systems in actual use.

I'll use the following largely standard terminology:

Payload is digital data one wants to transmit covertly; that's the question's "concealed message". Only its size is constrained.
Carrier is the data in which a payload might be concealed.
Channel is the vehicle by which said carrier is transmitted, and imposes a set of constraints on the carrier (like: being a bytestring of at most such size conforming to JPEG syntax, though perhaps with stricter constraints on padding and comment fields)
Original (if any) is data from which the carrier is prepared, with a set of constraints of its own (like, being the output of a consumer digital camera) and prescribed relation with the carrier (typically, a rendition of the carrier for human perception must be perceived as one for the original; or at least as a reduced-quality version of the original).

A steganography system must allow a sender holding a key (perhaps, public) and possibly a payload to construct a carrier; and a receiver with a key (same symmetric key, or private key matching public key) to determine if there was a payload in that carrier, and in the affirmative recover the payload.

An adversary's goal is to distinguish if a carrier carries a payload or not (better than random). The receiver must be extra careful not to leak that info, and that's hard, especially against active adversaries. We can assume that the adversary has the choice of payload within size constraints, much like modern cryptography assumes chosen plaintext.
Note: the question's goal "extract the concealed message" could mean that an adversary tries to reduce the size of the carrier while keeping the possibility to recover the payload when latter given the key, but that is not a usual goal, and I won't consider it further.

Payload confidentiality follows from security under chosen payload (argument: if the payload was intelligible, comparison with chosen payload would yield a distinguisher). It would anyway be trivial to add payload encryption on top of steganography if chosen payload was not assumed.

Often, extra properties are required:

The original must be a valid carrier per the channel constraints.
The security goal is met even if the adversary get holds of the original from which the carrier was prepared.
When there's no payload in a carrier, the carrier must exactly match the original.
The process by which an original is transformed into a carrier when no payload is embedded is constrained (e.g. is a certain pre-existing program).

Property 3 implies 1, and is incompatible with 2. There is overlap between channel constraints and constraints in 4.

Note: I've left aside watermarking, even though there is overlap with steganography.

The possibility (or not) of making a demonstrably secure steganography system depends heavily on the constraints set: on channel, original, payload size, and extra properties. There are many combinations of constraints depending on use case. Channel and original constraints vary immensely. Payload size can range from the text GO to terabytes.

The simplest demonstrably secure steganography system are those where constraints allow to embed a little more uniformly random bits in a carrier than the payload length (after compression). We can set these bits of the carrier either to true randomness (for no payload), or to the ciphertext of some authenticated encryption of the payload having the property that ciphertext is indistinguishable from random (which is easy and common). The receiver extracts the bits, perform the decryption/integrity check, concludes there's no payload if the integrity check fails, and otherwise has recovered the payload.

Such system must match whatever reasonable definition of perfect steganography is chosen (if a reusable key is not required, we can even use an information-theoretic MAC and replace encryption by a One-Time-Pad, to become information-theoretically secure regardless of the adversary's computing power).

Here is an example with properties 2 and 4, where original is any JPEG file, and channel is a PDF file with a PAdES digital signature made using 4096-bit RSA per RSASSA-PSS with SHA-512. I posit existence of a program that transforms JPEG files into signed PDF with said signature that uses a CSPRNG at step 4 of EMSA-PSS-ENCODE, reading:

  Generate a random octet string salt of length sLen

In the context, sLen is 4096-64-512 = 3520 bits, which can legitimately be random per the channel's constraints and property 4. That is enough for a 64-bit MAC per HMAC-SHA-256, a 64-bit IV for the most significant bits of a counter for AES-256-CTR, and 424 bytes of payload (over 1k byte of compressed text), used instead of the random octet string when there is a payload.

When the channel allows no bit that can be arbitrary random, it becomes much more difficult to make a demonstrably secure steganography system. In particular, with property 3, it becomes critical that the adversary can't have a better model of the original than the system assumes.


Standard serialization format for libsodium-based messages

Any serialization library that can efficiently encode binary data can be used, and MessagePack is an excellent choice for this purpose.


How are trapdoor functions developed/found and where can I find existing ones?

There are some theoretical constructions of TDP and you can find two examples in the technical report by Oded Goldreich. It is concerned with enhancements of trapdoor permutations, why they are required and two constructions of the enhanced TDP (in appendix) based on RSA and Rabin's collection.


How do unkeyed hash functions (for MDCs) provide security?

Your question is ill-posed; to determine whether they provide "security", we need a specification of what you mean by security.

So I'll answer about just one potential use of hash functions:

Are you thinking about using hashing together with encryption to try to protect the integrity of the message against tampering?  If so, generally speaking, unkeyed hash functions do not provide security against tampering with the message.  You should not use them for message authentication or integrity protection.

(Some people used to recommend appending an unkeyed hash of the message to the end of the message, and then encrypting, in hopes that this would prevent tampering with the message.  They called the hash function a "MDC".  We now understand that this construction is not secure.  Therefore, you should not use this approach.)

Instead, you should use either authenticated encryption or use a message authentication code (MAC).  Both constructs are keyed functions.

If this is not what you were asking -- or even if it was -- you need to revise your question to clarify what you mean by "security".  Security against what threats?


Should I use SHA256 or Blake2 to checksum and sign scrypt headers?

Note that Blake2's security goals are a superset of those of SHA-256:

SHA-256 is conjectured to be collision resistant, preimage resistant and second preimage resistant.
Blake2 is conjectured to be random oracle indifferentiable, a stronger property that SHA-256 doesn't have, and which implies the three classic hash function properties.

So yes, this substitution should be safe if Blake2 is safe.  One thing to note is that for this step:

  signs the concatenated work factors and checksum using HMAC SHA-256, appending the signature to the header

...you wouldn't want to use HMAC, since Blake2 has a built in optional keyed mode with the same MAC/PRF goals as HMAC.  (HMAC-Blake2 is not unsafe—it's just not the canonical way of using Blake2 as a MAC.)

  If I use Blake2-256, would I cut off 16 bytes for the checksum (this seems to be not recommended), use 32 bytes or just keep it as is using SHA-256?

The answer you linked doesn't say that truncating a Blake2 is always unsafe.  The gist of it is that:

It's generally wiser and safer to stick to well-trodden paths than to improvise your own; if there's a well-understood, standard way of achieving X, then that should generally be your default choice.  (Note that this implies you should stick to SHA-256 for the application you describe!)
When hashing to a custom output size, it's sometimes safer to make the hash output depend on the desired output size, to close off attacks where somebody is able to trick a system into hashing the same input in different contexts but truncated to different lengths.  (More generally, whether truncating a hash function is safe or not depends on how it's used.)

In your situation, I would go back to the fact that you're taking an already designed protocol and replacing its use of SHA-256 with Blake2.  This means that if the protocol is secure, then your substitution should be secure as well, because if Blake2 is secure then it should have all the properties that the protocol expects from SHA-256.  So if the original protocol truncates the output of SHA-256, then it should be no worse to truncate the output of Blake2.


How can Peggy prove she knows one of Victor's passwords in zero knowledge?

Yes, there is.

Assuming Peggy and Victor will be honest about their inputs, they can achieve exactly this functionality with garbled circuits. Victor can generate a circuit which will check for equality between Peggy's input and his list of passwords, then he proceeds to garble the circuit. Victor and Peggy cooperate in oblivious transfers for Peggy to get the circuit keys related to her input and she proceeds to evaluate the garbled circuit. She returns her output to Victor who can then clearly see whether or not the input Peggy provided is actually equal to one of his passwords, and he does not know which one. Such a protocol can be made maliciously secure as well.

It can also be implemented with secret sharing as well as other secure multiparty computation algorithms, but garbled circuits is usually one that is fairly intuitive for many.


Am I using these key derivation functions correctly?

Can I use a KDF like argon2 for this purpose? Of course I would have to extract the key and the salt along with the settings from this string to make this work.

Yes, but preferably you would not use the part of the function that creates a string.
Basically a password hash and PBKDF (password based key derivation function) are identical functions. The string that is put out is not part of a description of a PBKDF though, it is the output that is generated if it is used as a password hash (and then only for a specific format).
It is a bit annoying if the string is the only possible output, because the last part of the string is the password hash in base 64 (it's the "digest" in the this description). Now strings are pretty hard to delete from memory in most runtime environments, so you cannot easily clean up after decoding the derived key.
Preferably then you'd find or isolate the PBKDF function itself and use the resulting byte array before it is encoded. Or you could of course use another library that provides this functionality.


Your understanding is correct. They experimented NewHope RLWE key exchange while maintaining X25519 as backup, in case there is something wrong with NewHope. By combining two key exchange algorithms, it should be good.


Is there a scheme where two cipher texts can be proven to have the same (unencrypted) content?

Consider that I, as an attacker, suspects what you're sending in your secret messages.  If what you propose were possible, then I could know your plaintext by comparing my encryption of what I thought you were sending to what you actually sent, and brute for variations until I could confirm what you had sent.  This would be VERY bad.  Therefore, I assume you understand why I hope what you want is impossible as you proposed.

What could be done, would be to hash the message before encrypting it, and then comparing the hashes... this would again, especially with rainbow tables, lead to what I said above... the ability to know the message without decrypting it.


There is no such specific algorithm to find the best S-box but you can construct a Diference Distribution Table(DDT) like this and check out the values in it .A DDT is a matrix containing input differences as rows and corresponding output differences in column.

A better S-box has-
1- Lower values in its DDT
2- Less occurence of higher or highest value


Difference between known-plaintext attack and forward search attack

In context of public key encryption it is not really meaningful to consider known-plaintext attacks in the way this is done in context of symmetric encryption schemes (where an adversary gets hold of ciphertexts and knows the corresponding plaintexts and wants to recover the secret key). In public key encryption, everyone (as the public key is public) can produce ciphertexts for arbitrary messages of his choice. Consequently, an adversary can produce such pairs for any ciphertext of its choice and has not to wait to eavesdrop such pairs.

However, what is interesting in public key encryption is that an adversary who intercepts ciphertexts can not figure out which message is hidden in this ciphertext even if the adversary knows that the respective plaintext comes from a known set (in formal models this is reduced to a set of two elements, as discussed below).

The "forward search attack" in the HAC is a strategy the adversary can choose, i.e., to simply "trial encrypt" every element from the set and check if the ciphertext matches the intercepted. This attack strategy is feasible for
every deterministic public key encryption scheme (such as textbook RSA), where multiple encryptions of the same message with respect to the
same public key always yield the same ciphertext.

To formally treat security of public key encryption, we do not consider single attack strategies but a goal an adversary has to achieve within a concrete security model (attack class) and is typically modeled as a game between the adversary and a challenger. In indistinguishability games, the adversary can choose two messages and then gets back the ciphetext for one of these two and has to determine which message is hidden inside the ciphertext (where the adversary is given different "power", depending on the class of attack).

In the formal treatment of public key encryption, there is a model called indistinguishability under an
eavesdropping attack, which essentially says that an adversary is allowed to choose two messages, then gets the ciphertext for one of these messages and has to determine which one has been encrypted significantly better than guessing. As, however, in public key encryption, the adversary can built its own encryption oracle by means of knowledge of the public key, this aforementioned notion is equivalent to the well known notion of indistinguishability under chosen plaintext attacks (IND-CPA). This
attack game is essentially identical to the aforementioned, but the adversary additionally has access to an encryption oracle throughout the security game.

In the case of textbook RSA, an adversary can use this "forward search attack" as strategy to win the IND-CPA game. More precisely, when receiving the challenge ciphertext (one of the two submitted messages), then the adversary
simply calls the encryption oracle for one of the two candidate messages. If the response ciphertext of the oracle is identical to the challenge ciphertext,
the adversary knows that the message submitted to the oracle is in the challenge ciphertext, and the other one otherwise. By turning textbook RSA in a probabilistic scheme, e.g., by using OAEP, RSA can be made IND-CPA secure and this attack is no longer possible. It satisifies even the strongest notion of security, i.e., IND-CCA2 (see below).

In context of public key encryption schemes, the weakest notion of security considered today is IND-CPA (which is equivalent to the above mentioned eavesdropping) and the common stronger notions are indistinguishability under chosen ciphertext attacks (IND-CCA1) and a indistinguishability under adaptively chosen ciphertext attacks (IND-CCA2). In the latter two security games the adversary has additionally access to a decryption oracle during the security game (only before seeing the challenge in IND-CCA1 and also after seeing the challenge in IND-CCA2).


What does this Big-O notation mean based on appendix?

In general these definitions are similar everywhere and you can find a definition on Wikipedia.
Also, there is some silly confusion here. You are looking at the wrong thing! You are looking at "Proposition A.2" but you need Chapter/Section A.2 right below.


AES 256 CBC - Storing local data, how to save IV vector?

If you are using AES-CBC, You can store the IV however you like.  It is not important to keep the IV secret; you just need to make sure that an adversary cannot predict the IV in advance.

However, you have the right intuition that you should generally always use an authenticated cipher like AES-GCM.  AES-CBC is bad for other reasons too having to do with padding—AES-GCM provides a much better security contract all around than AES-CBC.  For AES-GCM, the only requirement of the nonce—sometimes also called an IV—is that it must be distinct for every message: you cannot reuse a nonce between two messages under a single key, and the consequences are fatal if you do.

That said…

  My main intention is to hide data from user and not allow them to change the data.

…it sounds like you are treating the user of your software as an enemy on their own computer.  If you're trying to do some kind of digital restrictions management (DRM) scheme, forget about it.  Not only is this hopeless—if it's happening on the user's own computer, the user can get the key anyway—but it is morally wrong to try to commandeer your users' own computers to work against their interests, and then penalize the ones who lack technical competence to work around your abuse of authority to run code on them.


Let us ignore all kinds of encoding or protocol details. We are looking for some string such that $yourprogram(string)=h$, where $h$ is a specific hash value. You will try to crack that password, rather than SHA-256.

Let us assume that all the possible messages you have are the 26 lowercase letters of English alphabet. That means that, for every letter in your password, you would multiply by 26 the amount of possible passwords. For instance, there are $26^{10}$ passwords of 10 letters. Then, if you try to brute force (try every possible solution until you hit the jackpot), it would be enough to use a longer password to prevent your attack. Sure: it would be longer than a password with a longer character set (uppercase, numbers, special characters), but it could be somehow manageable.

The problem is that humans are very bad at producing and remembering randomness. The fact that we are discussing this issue occurs mostly because "hquekl" is, despite being meaningless (to me, at least), easier to remember and communicate than "a{çè_". Which means that most passwords are likely to be "words". A word, in this sense, is a broad term, since it is just a string that we can remember. It can be an English word (password), a Spanish word (clave), a pattern (qweqweqwe), an English word backwards (drowssap) or a phrase (iloveyou). Some languages have a name for the word "dictionary" that can be roughly translated as "wordbook". As an attacker, this is the goal: collect the sets of words that compose the most likely passwords and create a list. Now, as an attacker, using a dictionary makes your job easier.

If you do not use salt, your scheme will be victim of determinism. Let us say that (for a very innocent hash algorithm) $hash(password)=5$. You do not know the value of $password$, but you steal a list of password hashes and see several entries of $5$. Not only that increases the likelihood of $password$ being in a dictionary: that means that several users have the same password. Furthermore, you can check a rainbow table: a gigantic list of precomputed hashes. Maybe someone already found out a value of $password$ that hashes to $5$, and even the dictionary attack will be unnecessary.

If you use salt, keep in mind that the value of salt is intended to be considered public, but has to be long enough. You can always make it difficult to the attacker, by asking increasing long passwords and blacklisting passwords that can be found in a dictionary. But you will make it even more difficult for your legitimate users.


Mapping between NIST test and TRNG features

It's difficult to map each of the 15 tests to a particular qualitative descriptor. Adjectives like robust are not mentioned in the 800-22 documentation.

The null hypothesis of randomness ($H_0$) in all tests fundamentally requires samples from a stationary and ergodic process. Otherwise the tests would be inconsistent with respect to time, and could not accurately model the samples' shifting distributions or test score expectations.  Or the test scores for this million bits would differ widely from that million's. Although be mindful of some variability implicit in any random process.

The requirement for independence within each test varies though. §2 of 800-22 details the mathematical assumptions underpinning each test. NIST doesn't always highlight the level of significance of independence within each test.  They often don't attempt to debate the causality of a $H_0$ sequence, just it's effect and characteristics.

Some are explicitly discussed.  The Discrete Fourier Transform (Specral) test is an example of a test that specifically targets independence in the mathematical sense.  It looks for correlations between samples spaced $n$ samples apart.  Maurer’s "Universal Statistical" test is similar, exploiting correlation for compressibility. As is the Binary Matrix Rank test. Conversely the Frequency (Monobit) test doesn't.  It will accept any degree of correlation as long as the ones and zeros are evenly matched in line with a half normal distribution.

The sensitivity to independence is harder to identify with some of the other tests. You may have to decompose the statistics beneath  tests like the Serial or Cumulative Sums (Cusum) tests.

Don't confuse the recommended input lengths with non ergodicity.  The recommendations are there simply to facilitate some of the test metrics' reference distributions, or to limit processing time.


How do I convert the definition of E-521 into a curve definition a la Bouncy Castle?

Bouncy Castle does not support curves of the Edwards form (such as the one E-521 has). See related question: Elliptic Curves of different forms
Bouncy Castle's FpCurve supports curves of the Weierstrass simple form. You can convert Edwards curves to this form by a series of (complex) calculations. SafeCurves shows you the necessary equations. First convert the Edwards curve to Montgomery form, then to Weierstrass form.
Unfortunately doing this will result in absolutely huge numbers, which - on top of the fact that Edwards curves are computed faster than Weierstrass curves - results in poor performance.

Appendix: Curve forms

Weierstrass: $y^2 = x^3 + ax + b$
Montgomery: $By^2 = x^3 + Ax^2 + x$
Edwards: $x^2 + y^2 = 1 + dx^2y^2$


The probability of someone 'getting lucky' with a guess at a key for a decent cryptosystem is crazily low, but yes: it is possible. However, there are methods that can 'survive' even this.

For example, consider the one time pad.  In this system the key and plaintext are xor'd together to form the ciphertext, and to decrypt you xor the ciphertext and key.
So, what happens if the attacker guesses the correct key? Well, he can xor it with the ciphertext, and will be left with the plaintext. However, what happens if he guesses a different key? This will also leave him with a possible plaintext, which to the best of his knowledge could have been the intended message. Thus even if he guesses the correct key, he won't have any way of knowing that he was right.

This is called information theoretical security: If the ciphertext does not contain any information (in the formal sense) about the plaintext, there is no way that an attacker could possibly know when he has correctly found the key.

eg: Suppose the message $m=11111111$ and the key is $k=10101010$. Then we have the ciphertext $c=m\oplus k = 01010101$.

An attacker intercepts $c$, and starts guessing keys. He guesses two possible keys: $k_1=10101010$ and $k_2=01010101$, leading to him reaching two candidate messages:
$$ \begin{aligned}
   m_1 &= c \oplus k_1 = 01010101 \oplus 10101010 = 11111111
\\ m_2 &= c \oplus k_2 = 01010101 \oplus 01010101 = 00000000
\end{aligned}$$

He has no way of knowing if either of these guesses was correct, even though we (as the original sender) know that in fact he was correct with his guess $k_1$. To him, each possible message $m_i$ is equally likely, so he can conclude nothing. In our example, he has no way of knowing if every bit is set, no bit is set, or indeed something in between.

As an interesting corollary to this, one can (by guessing the wrong OTP key) come up with a possible plaintext that might contain more sensitive data than the original plaintext! For example, if I encrypt $m=\text{I'm just going to buy some milk}$ with key $k$, if the attacker guessed key $k'=k\oplus m \oplus \text{Nuclear launch code=4923...}$ (where 4923... is replaced with the actual launch codes), when they try to decrypt my innocuous message, they would be left with a plaintext telling them the nuclear launch codes. Pretty cool really.


Does having an SHA256 hash compromise PBKDF2 secrecy?

If the party that controls the server also controls the client application then the server will always be able to retrieve the password. In that sense protecting against the server only works if very strict auditing is taking place, and then only maybe.

If the server receives a hash over the password then it can of course perform a (augmented) dictionary attack against the hash. When multiple hashes are collected then rainbow tables will also be an option. All the additional protection delivered by bcrypt of PBKDF2 will be null and void.

So yes, if the password could be found with an attack, and then PBKDF2 can be performed using the found password in your scheme. Very strong password will still offer protection against the server, of course.

PS No, the more iterations the better for PBKDF2. Cycles only occur after many more iterations, and are nothing to worry about here.


Does "hash than sign paradigm" apply to ECDSA cryptography?

Quick answer: You do not have to hash the inputs to Ed25519 because hashing is already part of Ed25519 itself.  If you do hash inputs in advance, you become vulnerable to collisions in the hash function you use.

Longer answer:

This rule does not make sense, period, because hashing is an integral part of a secure signature scheme.  It is a design principle to use a hash function to compress a message into an element of a mathematical structure that can be combined with a private key to yield a signature verifiable by the related public key.  This was first described by Michael Rabin in 1979.  Today, every serious signature scheme involves a hash of the message as a first step, with some variations.  Any system or textbook that tries to separate the steps of ‘hashing and then signing’ is dangerous.

Here's an example of an RSA-based signature scheme: A signature on a bit string $m$ under a public key $n$, a large integer with large prime factors, is an integer $s$ such that $$s^3 \equiv H(m) \pmod n,$$ where $H$ is a random function from bit strings to positive integers below $n$.

The hash $H$ is an integral part of this signature scheme because if you didn't use it, and instead used the equation $s^3 \equiv m \pmod n$, then I could trivially forge the signature $s = 0$ on the message $m = 0$, or $s = 2$ on the message $m = 8$.  The use of $H$ means I can't use the advanced technique of computing integer cubes on my pocket slide rule to forge signatures, because I don't have a hope of finding an $m$ with any prescribed hash value.

In the case of Ed25519, a signature on a bit string $m$ under a public key $A$, a point on an elliptic curve, is (roughly, with details of encoding and cofactors elided; see the Wikipedia article for more detail and references) a pair $(R, s)$ of a point $R$ on the curve and an integer $s$ such that $$[s]B = R + [H(R, A, m)]A,$$ where $B$ is a standard base point on the curve, $H$ is a random function from two curve points and a bit string to an integer below the order of $B$, and $[s]B$ etc. denote scalar multiplication on the curve.

Hashing a per-signature randomization and the public key together add some security beyond the simple RSA-based scheme above: hashing in per-signature randomization obviates the need for $H$ to be collision-resistant in practical realizations (the lapse of which in practical systems using MD5 has had serious consequences), and hashing in the public key mitigates multi-target attacks and prevents key malleability—finding two distinct keys under which a signature is valid.


Fundamental ideas:

$ a \oplus a = 0$

$ a\oplus 0 =  a$

also if $K = B_{1}$ , $E_{1} = 0$ and as per your scheme $ B_{2} \oplus E_{1} = E_{2} = B_{2} $

As a result of you setting $K = B_{1}$  you cannot decrypt the first block if you do not know $B_{1}$.
This system is fundamentally broken, it can never be used in practice. This assignment question sadly does not give the correct idea of CBC . Practical CBC mode of Block Ciphers like AES work in a very different way.
For example if we have an Encryption function $E_{k}$ then this is how CBC encryption works.

$C_{0} =E_{k}(IV\oplus M_{0})$

$C_{1} =E_{k}(C_{0}\oplus M_{1})$
and so on...
As you can see there is an application of a very strong encryption function $E_{k}$ which could be something like AES. Here you are doing a simple XOR.
Prima facie, your your scheme is subject to known - plaintext attacks and a 64 bit key is always brute force search able. I might have missed some crucial points but this is what I can think of now !!!


Pairing-based cryptography VS ZK-proofs: what's more efficient for threshold systems?

If you care only about verification, and your protocols are such that the pairing-based approach requires one pairing, while the alternative (so-called "zk-proof") approach requires, say, 2~4 multiplications, one addition, and one hash, then yes, you are right: the pairing-based solution is less efficient. For a rough comparison, see page 14 of my paper: if you pick some of the most common best choices for a pairing-friendly elliptic curve and a pairing-free elliptic curve, then the cost of a pairing will be roughly 8 times the cost of a multiplication (or exponentiation, since we were using multiplicative notations in this paper) in the pairing-free curve. There are two reasons behind that: not only do pairings require more computation than multiplication, it is also the case that the best-known pairing-free curves allow for more efficient operations than the best-known pairing-friendly curves.


SHA-256 Reversing A String of Equal Length

SHA256 gives 256 bits, which is 32 bytes, not 64 "characters" (please use the well-defined bits and bytes). When written in hexadecimal notation, you need 64 characters from 0-9a-f, but the length of the hash is 256 bits.

Yes, you could invert the hash. Unfortunately, a straightforward lookup table would be too large to store, but you can still do brute force without memory. This would take you on average $2^{255}$ tries (that's many).

There have been papers, like "Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family" which discuss preimage resistance attacks on the SHA-2 family, but they're, as far as I know, all academical breaks (meaning they cannot really be exploited efficiently.


Point halving on elliptic curves of even order

Supposed $Q = (q_x,q_y)$ is a point on elliptic curve $E$ defined by $y^{2} = x^{3} + ax^{2} + bx + c$. To  find the half point $P$ of  $Q$, we need to do the following:

Write down the equation for the derivative of $E$ at $P$. letting $\lambda$ be the derivative, we have
$\lambda = \dfrac{3x^{2} + 2ax +  b}
    {2(x^{3}  + ax^{2} + bx + c)^{1/2}} \tag{1} \label{1}$
Write down the equation for  the tangent line to $E$ at $P$:
$y-p_y = \lambda(x-p_1) => y = \lambda(x - p_x) + p_y \tag{2}$.
Write the equation for the intersection of the tangent line with E:
$y^{2} = (\lambda(x - p_x) + p_y)^{2} = x^{3} + ax^{2} + bx +
    c \tag{3}$.
Write down $\lambda$ in terms of $p_x$:
The equation from (3) comes out
to a monic cubic polynomial. Since it is monic,
    the sum of the roots add up to minus the coefficient of $x^{2}$. The
    roots are the intersection points. Hence $p_x$ will be a double root, and $q_x$ will be the third root. If you simplify this equation, you will see that the coefficient of the $x^{2}$ term is $a - \lambda^{2}$. Therefore $2p_x + q_x = \lambda^{2} - a $ and so $\lambda^{2} = 2p_x + q_x + a  \tag{4} \label{4}$
Set equation from (4) and equation from (1) equal to  eachother.
Combining equation $\eqref{4}$ with the equation for $\eqref{1}$ and replacing $x$ with $p_x$, we get
$\lambda^{2} = 2p_x + q_x + a
    =  \dfrac{(3p_x^{2} + 2ap_x +  b)^{2}}{2(p_x^{3}  + ap_x^{2} + bp_x + c)} \tag{5} \label{5}$.
Simplifying this equation and moving everything over to
    the left hand side will yield a quartic polynomial in $p_x$. The roots of this polynomial are the x-coordinates of the half points of Q..

The relationship  between  the half points of $Q$ is the  same as  the relationship between  the roots of $\eqref{5}$. It will change depending on the nature of $E$. Here are a few things we can say for certain.

Since neither $q_y$ nor $p_y$ make an appearance in this quartic polynomial, each quartic polynomial will actually give the  halves for two separate points. The quartic from $\eqref{5}$ gives us the half points of $Q = (q_x,q_y)$ as  well as the half points of $-Q=(q_x,-q_y)$.
To find out if a half point exists for a point $Q$, there is a value you can calculate based on $a,b,c$ of $E$ and $q_x$. This procedure can be found on page 5 of Quartic Equations and 2-division on Elliptic Curves (Most of the results from this answer are directly from this paper).
If the points on E make up an odd ordered group, then each point $Q$
only has one point $P$, and hence the quartic equation will only
have one root. This follows from the fact that
elements in odd groups have unique square roots.In this case, the factors of the quartic polynomial will be a linear equation and an irreducible resolvent cubic.
Equation (5) is equal to $(x-s)^{2}(x-t)^{2} <=> Q$ is a 2-torsion point. In this
case, $Q$ will have two distinct halves, one where $x=s$ and another
where $x=t$. $-Q$ will also have halves with these x-coordinates.
Equation (5) is equal to $(x-s)^{4} <=> Q$ is a singularity.


The short answer is: $2^{128}$ operations, no known birthday-like attack.

The long answer: when HMAC was first published, it came with a security proof, tailored for iterated constructions like Merkle-Damgård. In a MD hash function (MD4, MD5 and the whole SHA family are MD hash functions), the data to hash is processed by blocks with a compression function: the compression function takes as input the block and the current state (the state is a 128-bit value for a function with a 128-bit output), and produces the new state (which will be used as input for the processing of the next block). The final state is the function output.

The original proof claimed that if the compression function is a PRF (i.e. the choice of a block value "selects" the compression function as if randomly among functions which take the state as input and produce the corresponding output) and the hash function is collision-resistant (in a "weak" way; it needs not be resistant to all kinds of collisions) then HMAC is secure. That proof worked up to $2^{n/2}$ invocations of the compression function (for a hash function with a $n$-bit output). Later on, Bellare published a new security proof which removes the condition on weak collision resistance, and enhances proven security up to $2^{n}$ .

Now the fine print: the security proof works only as long as the PRF assumption holds. However, if the PRF assumption holds, then the hash function which uses that compression function in the MD construction is necessarily resistant to collisions up to $2^{n/2}$. Therefore, if a MD-like hash function is proven not to be collision resistant up to $2^{n/2}$, then this implies that its underlying compression function is not as PRF as it should. This is true, in particular, for MD4, MD5, SHA-0 and SHA-1. For these functions, the PRF assumption cannot be held, hence the HMAC security proof is not applicable to HMAC/MD4, HMAC/MD5, HMAC/SHA-0 and HMAC/SHA-1. This does not mean that we know a way to turn collision attacks into attacks on HMAC. Indeed there is no known attack faster than $2^{128}$  on HMAC/MD5. However, there is a known forgery attack on HMAC/MD4. Note that this attack has cost $2^{58}$, which is quite a lot (and explains why the attack was never actually demonstrated), whereas resistance of MD4 to collisions is, by itself, zero (generating the collision takes less time than simply hashing the two messages to verify that it works).

Also, all these proofs are for MD-like constructions and do not apply, directly, to non-MD functions. However, one can say that HMAC is defined as it is, with its two nested hash function invocations, precisely to overcome some shortcomings of the MD construction. So there is "no reason" why a non-MD hash function would not do fine in HMAC. Most SHA-3 candidates include statements and/or proofs of security of the hash function when used in HMAC.


Hill Cipher the point of a known plaintext attack question

Indeed. If the matrix is $n$ by $n$, and you have $n$ many known plaintext blocks with corresponding ciphertext, you get $n^2$ linear equations in $n^2$ unknowns (the matrix elements) (modulo the alphabet size), which very often can be solved uniquely.


Yes, it is possible that AES is slower than DES. There is no limit to the slowness of un-optimized software!

Some factors that I have witnessed slowing a software AES implementation:

not using tables for computation of the S-box(es) (an extreme example is the implementation there, when compiled with BACK_TO_TABLES undefined; another possibility is using a formula intended for hardware or bitslicing, perhaps in order to remove timing variations).
using hexadecimal ASCII (or binary) strings for everything, perhaps with the excuse that there is no built-in 128-bit type;
using an interpreted language (one without built-in XOR will insure particularly poor performance)
leaving debug code that dumps every intermediary result, even if that's effectively to /dev/null or equivalent;
to a moderate degree, recomputing subkeys at each invocation when the mode of operation allows to factor that out;
to a small degree, using 256-bit keys (it is hard to lose more than a factor of two with this one).

This is also applicable to DES to a large degree.

I should have mentioned that for decently and comparably optimized implementations, AES is typically faster than TDES and often than DES, and illustrated that with throughput; but that other answer does it nicely.


How big does M need to be in Blum Blum Shub?

The usual definition for the Blum-Blum-Shub (BBS) generator goes as follows:
Let $N$ be a Blum-Integer of unknown factorization. Let $j$ be the "extraction rate". Let $x_0$ be a uniformly random non-negative integer smaller than $N$. Define $x_{i+1}=x_{i}^2\bmod N$. For a request of $M=jk$ random bits, compute all $x_i$ up until at least $x_k$ and concatenate the $j$ least significant bits of each of those values as the random output.
The classic, original BBS construction used an extraction rate of 1. Later analysis (PDF) suggested that $j$ can safely be of order $O(\log\log N)$. Follow-up concrete analysis (PDF) suggests the following bound (Theorem 3):

The BBS Generator is $(T_A,\varepsilon)$-secure if $$T_A\leq \frac{L(n)}{35\delta^{-2}n\log_2 n}-2^{2j+9}n\delta^{-4}$$ where $\delta=(2^j-1)^{-1}M^{-1}\varepsilon$, n being the bitlength of $N$, $L(n)$ being the effort to factor $N$, and $(T_A,\varepsilon)$-secure meaning that an adversary can distinguish the output from random with effort $T_A$ and success probability $\varepsilon$.

Now let's pick $n=3072$ for fun for which the standard estimate is $L(n)\approx 2^{128}$ work effort. Let's also pick $j=4$ and $k=32$ extracting 4 bit from each squaring and wanting 128 bit. Let's also suppose we want $\varepsilon=2^{-1}$ success probability for the adversary. This gives us $\delta=(2^{1}\cdot 31\cdot 128)^{-1}\approx 2^{-13}$. This in turn gives us $2^{2\cdot 4+9}\cdot n\cdot 2^{52}\approx 2^{79}$ and $\frac{2^{128}}{35\cdot 2^{26}\cdot n\cdot \log_2 n}\approx 2^{81}$. Therefore an adversary in this scenario requires about $2^{81}$ work to break this BBS generator with success probability $1/2$.
Using the above, you can also try and estimate other parameter values, but I guess you already noticed that for BBS to be secure you either need rather large moduli or extract at a very slow rate and / or only extract a few bits from a seed. In general, you're better off using a generator like AES-CTR DRBG.


Breaking the 40 bit DVD CSS stream cipher

There is a Berlekamp-Massey algorithm that constructs the shortest LFSR for a given binary sequence.
For an LFSR of length $L$ given $2L$ output sequence from the LFSR, it is enough to construct the LFSR. To construct a 25-bit LSFR, 50 bits is enough. Note that, the algorithm doesn't need to know the taps. It just constructs the minimum LFSR that can produce the given sequence.
Looking at the 20-byte (160-bit) you can make sure that the remaining 110-bits are output from the LFSR. We don't expect that with a negligible $1/2^{110}$ probability the LFSR will succeed to produce the random bits.
To Study the LFSR's

Solomon W Golomb's book Shift Register Sequences: Secure And Limited-access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models (Third Revised Edition), is advised.


How to name a signature algorithm that has no hashed component

If the RSA signatures you are doing are the ones standardly identified by the names you reference, corresponding to OIDs 1.2.840.113549.1.1.{2,4,5,11-16}, namely the scheme that was 'block type 1' in PKCS1v1 and retronymed RSASSA-PKCS1-v1_5 in PKCS1v2, it requires the hash algorithm identifier to be included in the padding; see step 2 of 9.2 in RFC8017 and the Notes on the following page, or the equivalent sections in earlier versions. Thus you cannot have an v1_5 signature which does not identify a hash algorithm, even if you didn't actually use that hash in computing the signature. (This is why openssl pkeyutl -sign for RSA with padding specified or defaulted as pkcs1 requires you to specify -pkeyopt digest:name to get the correct result even though it doesn't actually do the hash.)

For ECDSA (and DSA) although the standards (FIPS 186, X9.62, SEC1) require using a suitable hash, it is technically possible for the algorithms to generate and verify signatures using any bitstring of the correct size (not necessarily from any hash algorithm). FWIW, the usual Java cryptoprovider(s) -- Sun/Oracle/OpenJDK SUN and SunEC -- provide these as "NONEwithDSA" and "NONEwithECDSA" (casing only nominal, because in JCA algorithm names are case-insensitive), and BouncyCastle provides nominal "NONEWITHDSA" and "NONEWITHECDSA" with the former also aliased as "RAWDSA"; these do not have corresponding OIDs. IBM might be different, as might Android.

(Bouncy actually also provides "RSA" aliased as "NONEWITHRSA" and "RAWRSA", but as above they produce nonstandard and noninteroperable results, unless you handle the DigestInfo encoding yourself. And SunJCE and Bouncy support as a Cipher (not Signature) different versions of the semantically wrong but traditional "RSA encryption with private key".)


A common method for constant-time comparison goes

$r←0$
for each bit/byte/word $x_i$ and $y_i$ to compare

$r←r ∨ (x_i⊕y_i)$   where $∨$ stands for bitwise OR and $⊕$ stands for bitwise XOR

all the $x_i$ match the corresponding $y_i$ if and only if $r$ is now $0$

The point is that the duration is independent of the data compared, thus measuring that duration does not reveal anything about the data.

Other methods are possible, like hashing all the $x_i$, and all the $y_i$ (perhaps with the same random prefix), then comparing the result (preferably, using a similar constant time method). This could be less sensitive to other forms of side-channel attacks.


In cryptography, what is "fractionation"?

...looks like a kind of substitution.

It's perhaps more similar to encoding, say to ASCII, Baudot code or "dits & dahs" (morse code). And as the name implies, fractionation breaks up the message characters into smaller pieces (fractions) that then exactly represent those characters.

It was used in the more classical ciphers like transpositional ones.  Probably before the common use of computing machines.  The transpositions occurred on a character by character basis. The coordinates on a Polybius square can serve a similar function to that of an index into an S-box/lookup table. Or they can be otherwise manipulated in ways that a single character can't be.  Since the advent of modern computers, this fractionation occurs automatically when the characters are represented as bits within a block of bytes.  The term does not seem to appear in contemporary cryptography.

I suggest that the benefit is not for elimination of message redundancy, but for assisting with diffusion.  Substitution and permutation are entirely mathematically possible with a human alphabet.  You'd just have multi-character substitution boxes, so a three character substitution box would accept input like ggn and output yqy.  You'd permute single letters between them as we do today. It would be cumbersome though as such an s-box would be at least 19,683 entries long ($(26 + 1)^ 3$).  Numbers extra.  And their efficient generation via polynomials would be problematic. Algebraic qualities, avalanche and linearity were not well appreciated then.

So now we fractionate/encode to numbers and bits, and manipulate, substitute and permute them instead.


where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling

Actually, it doesn't look bad at all; that's 128 linear equations in 128 variables (over $GF(2)$); Gaussian elimination should be able to give you an answer in $128^3 \approx. 2,000,000$ bit operations; hardly infeasible (and certainly easier than any fault attack).

The only tricky bit is that the 128 equations are likely not linearly independent (a random set of 128 $GF(2)$ linear equations over 128 variables is linearly independent circa 29% of the time); if they are not linearly independent, then there will be multiple solutions (or none at all); multiple solutions imply multiple keys that are all correct solutions; your Gaussian elimination code will need to deal with that situation.


Firstly, the checksum would seem irrelevant to me given I'm using an AEAD (AES256GCM) cipher. What am I missing here?

Well, what you're missing is what TLS does with the specified hash.  Contrary to your assumption, it does not append a hash to each record; as you point out, that'd be silly.
Instead, it uses it for two purposes:

Within the Key Derivation Function, that is, as a part of the infrastructure that maps P521 shared secrets and public data to actual keys

To summarize the exchange transcript (to detect downgrade attacks)

Which leads us into your next question:

is my risk here (assuming my attacker can find collisions for SHA384 but NOT for SHA512) that my attacker can inject false messages into my communications or could it (very remotely) strengthen my attacker's ability to decrypt my communications?

If the attacker is attempting to listen into a negotiation between two honest parties, he doesn't get to chose what is hashed; that means that a collision attack wouldn't apply (because a collision attack assumes the adversary has the capability to select both values that hash to the same one).  And, even if the adversary were able to inject his chosen plaintext (e.g. via a Javascript applet), that wouldn't help, because what is hashed is selected by the TLS implementations and not the applications.

My question to crypto.SE is- what am I losing in terms of encryption security by having client browsers supporting a max of SHA384?

It wouldn't appear that you're missing much at all; other parts of the system would appear to be more vulnerable.


Does encryption using PRP mean indistinguishable encryption against an eavesdropper?

The PRP encryption scheme is secure in your security definition, but this security is very weak. It only achieves "one-time security" and is also weaker than perfect secrecy, i.e., the adversary's advantage is not exactly 1/2.

I think the security can be stronger (but still cannot be IND-CPA for instance). With PRP security, we can view $F_k$ (and hence $Enc_k,Dec_k$) as a real random permutation $f$ (except for a negligible PRP security advantage). Then, even if the adversary knows $p$ message-ciphertext pairs, it still cannot distinguish $m_0,m_1$ if they do not belong to the known $p$ messages.


The Goldreich-Goldwasser-Micali Construction with bad PRGS

I know I'm answering my own question, but there's actually quite a nice worked example which completely refutes my question. I thought I'd share.

Suppose I use the GGM construction with the underlying PRG being RC4.

RC4 has a lot of problems, one of which is the fact that the second byte is basically twice as likely to be zero than it should be: $2\over 256$.

For longer key-streams, the biases settle down and the cipher can be used relatively safely. Google, for example, uses RC4 for in SSL.

However, the GGM really punishes RC4. Every stream that RC4 generates is short. An attacker can use this to distinguish the resulting PRF from random very easily. Here's how.

The attacker requests that you compute your PRF on values of his choice. He can craft those values so that the tree that is navigated in GGM always returns the left hand side of the expanded bit stream. These are the first bytes out of RC4.

He can then simply look at the second byte of the result of PRF(x) and count the number of times its zero. After a pretty trivial number of queries, he's clearly able to distinguish the PRF from a random function.

We're now in a position where the GGM has actually has poorer security than the underlying PRG! This nicely refutes my question.

The message is that a bias in the PRG should be assumed to render GGM insecure.


Is 50% of bits changed in every round always gives 50% of changed bits in the end?

If we have such property that every round change 50% of bits, how to be sure that in many rounds in the end we will also end up with 50% of bits changed?

Well, obviously one can construct artificial examples where this doesn't happen; the most obvious (and trivial) being if round 1 and round 2 are inverses of each other (that is, round 1 followed by round 2 gives you the original plaintext); even if both rounds were individually ideal, we still don't get the avalanche effect after two rounds (even though we had it after one).
Symmetric ciphers are generally don't have enough structure to allow us to construct proofs that this doesn't happen (and adding structure generally makes the cipher weaker, not stronger; adversaries can also take advantage of structure); we generally have to rely on plausibility arguments.


How is the matrix A related to the lattice space L in SIS?

About the basis
As stated in the other answer, the lattice directly related to SIS is actually the $q$-ary lattice defined as
$$\mathcal{L}_q^\bot(A) := \{ u \in \mathbb{Z}^n : Au = 0 \mod q \}.$$
And its basis is not the matrix $A$. To construct a basis to this lattice, one usually suppose that $A$ has $n$ linearly independent columns (let's say, the first $n$) and write $A = [A_1 \quad A_2]$ with $A_1$ being an $n\times n$ matrix invertible over $\mathbb{Z}_q$, then the following matrix $B$ is a basis:
$$
B =
    \begin{pmatrix}
    ~q\cdot I_n~  & -A_1^{-1}A_2 \\
    ~\vec 0~  & I_{m-n}
    \end{pmatrix} \in \mathbb{Z}^{m \times m}
$$
About the hardness
Actually, it could be a hard problem regardless its connections with lattice problems. But it is connect to lattices in several ways. First, it is obvious that finding short vectors in $\mathcal{L}_q^\bot(A)$ gives us solutions to SIS. Moreover, it has been proved that if one can solve SIS in polynomial time in average, then one can solve hard lattice problems.
Roughly speaking: if you had an algorithm to solve SIS with non-negligible probability (for instance, your algorithm could work one time out of one million), then you would have an algorithm to solve approximate versions of GapSVP and SIVP).
About the value $\beta$
The value $\beta$ is a parameter of the problem. It is easy to find $u$ such that $Au = 0 \mod q$ (just use Gaussian elimination), what may be hard is to find a short vector satisfying this equation. But how do you define short? Using $\beta$ as an upper bound to the length.
These are standard facts: if $\beta \ge q$, then $u = (q, 0, 0,..., 0)$ is a valid solution, therefore, SIS is trivial for such values of $\beta$. If $\beta$ is too small, then maybe there is no valid solution. If $\beta \ge \sqrt{m}$ and $m \ge n\log q$, then it is guarantee that there exist at least one valid solution.


The closest that I can think of is a "symmetric bilinear group" (a.k.a. Type-I pairing group) that was popular when bilinear groups were first introduced. This is actually a pair of groups $(G, G_T)$ together with an efficient non-degenerate bilinear map $\otimes: G \times G \to G_T$. Obviously DDH is easy in $G$, since one can on input $(g, U, V, W) \in (G_1)^3$ test whether $g \otimes W = U \otimes V$. But the pairing will not necessarily help you compute CDH in the source group, since the map $(\cdot \otimes g)$ is not meant to be easy to invert.

These kinds of groups are constructed based on various types of elliptic curve, my intuition is that a pairing "out of" a curve group won't help you compute new elements in the group itself.

This kind of group appeared in Boneh, Boyen and Shacham (eprint 2004/174) where they used the Decision Linear assumption instead of DDH, since DLIN can be hard even in the presence of a pairing.


Making attacks on password hashes less economical

I had been thinking of this question for quite a time, but without a satisfying answer: it seemed to be a problem that had never really been considered in the literature (at least, not in the theoretical cryptography community).

Incidentally, I was just checking the ePrint archive this morning, and stumbled upon this paper which was added today to the archive, which focuses exactly on your question. It introduces a new complexity measure that accounts for the fact that time-memory trade-off do not scale linearly with respect to the hardware cost. I've not read it in details yet (I plan to), but the authors are among the leading researchers on memory-hard functions (subsets of the authors developed the theoretical model for analyzing MHFs, described the best known attacks on Argon and Balloon, gave new constructions, and proved the maximal memory hardness of Scrypt). It should be worth reading.


What is the point of separate links to the download and its digital signature

They don't expect that everybody uses their infrastructure. So, someone, a Man-in-the-Middle can change the executable or you are downloading it from alternative download sites that can contain malicious code.

One way to make sure that the file is not tempered is publishing the hashes on their website. Hash is very common for ISOs of the Linux distributions. This protects as long as you can access the hash values correctly. Another method is signing that also gives us information about the signer.

In the case of their website is hacked, you may be very unlucky to be in the middle of the attack that we expect it is a short time. If, however, they use a chained certificate and you know it before you can still check the signature. The attacker to be successful must somehow access the signature key. In general, to be on the safe side, the companies sign the files with an off-line computer so that the signature key cannot be accessed from an online attacker. As usual, the corresponding public key can be published.

So, in short, if the signature key does not belong to a trusted key chain that is verifiable, don't accept the file. Everybody can create a file with a signature and publish it with a verification key.


No way to do ECDH with OpenSSL from the command line?

Here's one way to do roughly what you described:

openssl genpkey -out alice.pem -algorithm EC \
  -pkeyopt ec_paramgen_curve:P-256 \
  -pkeyopt ec_param_enc:named_curve
openssl pkey -pubout -in alice.pem -out alice.pub
openssl genpkey -out bob.pem -algorithm EC \
  -pkeyopt ec_paramgen_curve:P-256 \
  -pkeyopt ec_param_enc:named_curve
openssl pkey -pubout -in bob.pem -out bob.pub
openssl pkeyutl -derive -out alicebob.key -inkey alice.pem -peerkey bob.pub
openssl pkeyutl -derive -out bobalice.key -inkey bob.pem -peerkey alice.pub
cmp alicebob.key bobalice.key

But, who knows whether this implements a secure DH system?  You should really consider using X25519, e.g. via NaCl crypto_box, rather than stringing together generic OpenSSL incantations like this.


One-way function with combination sets as output / image

From what I know, there's a prior art here.

The random oracle / hash function used in BLISS signature scheme hashes a certain bit string into a sparse vector (see section 4.4). And the way they do it, is similar to what you just described.

I've got an old code sample lying around you can reference, I've incorporated a few later improvements.


Why is this not a viable key exchange algorithm?

I've simplified the Alice random bytes to ARB and Bob random bytes to BRB. Then the protocol follows as;
Alice knows $key$ and $ARB$ and sends $$C_1 = key \oplus ARB$$
Bob knows $C_1$ and $BRB$ and sends
$$C_2 = C_1 \oplus BRB = key \oplus ARB \oplus BRB$$
Alice calculates $C_2 \oplus key \oplus ARB =  key \oplus key \oplus ARB \oplus BRB = BRB$
Alice knows $key, ARB,$ and $BRB$  and sends
$$C_3 = (C_2 \oplus ARB) = key \oplus ARB \oplus BRB \oplus ARB = key \oplus BRB$$
Now, first of all, this requires a three-pass protocol.
Now, an observer sees
\begin{align}
C_1 & = key \oplus ARB \oplus {}\\
C_2 & = key \oplus ARB \oplus BRB\\
C_3 & = key \oplus \phantom{ARB}\oplus BRB \\
\end{align}
A passive observer (eavesdropper) simply x-ors all to derive the key $$key = C_1 \oplus C_2 \oplus C_3.$$ Therefore it is insecure against the weak assumption on the attacker; passive!.
So, you rely on the xor, however, did not check what an observer can get and calculate from them.
The Diffie–Hellman key exchange (DHKE), on the other hand, leaks $g^a$ and $g^b$ where Alice selects a random integer $a$ and sends $g^a$ and Bob select a random integer $b$ and sends $g^b$. Finding $a$ or $b$ from them is the discrete logarithm problem. On the other hand, The Computational Diffie–Hellman (CDH) assumption, is asked to find $g^{ab}$ given $g^a$ and $g^b$, and the DHKE is relayed on this. If the discrete logarithm is easy then CDH is easy. We don't know the reverse, in the general case.


Distinguishing attack on stream cipher created from a block cipher in counter mode

For a truly random stream, since there are $2^n$ possible $n$-bit blocks, we expect a repeated n-bit block after looking at (roughly) the first $2^{n/2}$ blocks, by the birthday paradox argument.

For the stream generated by this block cipher, provided that each input block is distinct (i.e. the counter does not start repeating) , the output blocks are distinct (since the block cipher is a permutation). So choosing the IV length small enough (or indeed taking the whole block for the counter and not using an IV), we are guaranteed that no block is repeated for the first $2^k$ blocks, where $k \leq n$ is the length of the counter.

This way, provided $k$ is large enough, we can distinguish between two such streams by searching for a repeated block.