Building content-defined chunking with adversarial data preserving guarantees on splitting probability and global stability

The Shape of the problem
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$. This input needs to be chunked.
In the general case, I'll assume there is some hypothetical function chunk_at_index(Data[i-N:i+N]) which can be called to determine if the stream should be cut at index i. Any function that outputs a cut location given a section of the stream can be wrapped to produce this simpler function. This requires that chunking boundaries are stable and determined only by local information.
The general case is impossible
It is impossible to guarantee this in the general case while also ensuring that chunks meet a given (min/max) length criteria or maintain global stability. No such function can guarantee global stability of chunk boundaries after a local edit.
Consider the a string of repeated characters "aaaaaa[...]aaaa"
A function evaluated on a rolling window must either chunk on every byte or leave the entire string intact. No local function can stably decide where to draw chunk boundaries inside the uniform region without considering data outside that region.
Any algorithm that guarantees chunks fall in a certain size range has to be either unstable or use non-local information.
Consider the following string, with a section consisting of repeated 'a' characters. A hypothetical chunking function chunks it up as so. An edit is made and then it is re-chunked.
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aaaHello " "world!
"Hello " "world!aa" "aaaaa" "aaaaa" "aHello " "world!
A change to the second chunk changes a chunk an arbitrary distance away.
A data compression algorithm could probably be built to pre-process the data in order to fix this. It would need some ability to recursively compress its own output to prevent its own output from having similar repeating patterns.
This illustrates the problem of finding features to use to cut the stream up reliably.

Prolly Trees Don't Have that Issue
Fortunately, Prolly trees are used to store sorted data items, typically key value pairs. Assuming the value is stored by a cryptographic hash reference in the serialized data and that the keys are close enough together, a chunking algorithm will have locally unique features with which to make a yes/no chunking decision for a given window onto the string. If an algorithm can't decide reliably where to make a cut it's the algorithm's fault.
Why a Rolling Hash?
A rolling hash takes a window of bytes in the string and outputs a score representing preference for that location as a chunk boundary.
This is a really powerful concept. The score represents how much the algorithm should want to split the stream at a particular spot. It's only dependent on the data near that index which is why chunk boundaries tend to be stable and re-synchronise.
For non-adversarial data a simple threshold works well to decide where to split but if the adversary can manipulate the scores, we need a better algorithm for choosing boundaries.
Requirements for the Rolling Hash
Any rolling hash will have an output range. If the attacker can completely control the output, they can create pathological score profiles that no function can use for choosing split points. Collisions and exact repetitions are quite problematic as are the integer function output limits. Normally an attacker would have to do 2^N work to set N bits of the function value. For universal hashes or anything else that uses tractable math to make calculating the hash over a rolling window efficient the output can be controlled trivially.
It seems necessary to use a strong hash algorithm for generating scores (essentially applying SHA2 or similar to the hash window). This ensures the attacker has to work harder to get a better score and can't cheat. all that's necessary is to build a splitting function that is computationally infeasible to mess with in the long term. Ideally something that gets quadratically or exponentially harder the longer it hasn't marked a chunk boundary.

Notation
The input is a string of bytes $\{D_1,D_2,D_3,...D_n\}$.
we compute a rolling hash function over this string to compute the score for each cut location. S(i) = SHA2(Data[i-A:i+A]). The scores can be seen as an array of values that can be sliced S[i:j].
The off by one issues here aren't too important. I'm similarly going to ignore issues relating to hash values at the start and end of the string where the hash window isn't full. the hash window size A should be a little larger than the minimum chunk size for reasons that will become clear later.

Localized Beauty Contest
A robust way to enforce a minimum chunk size is to select for values that are the smallest inside some local window. For stream index i we check that the score for that index S[i] is the minimum of the slice S[i-A:i+A] where A is the minimum chunk size. A point wins and becomes a chunk boundary if it is the minimum when it is in the center of the window. This can be done on a rolling window by keeping a sorted heap of values or the ascending minima algorithm. It chunks about once every 2*A bytes.
This doesn't enforce a maximum chunk length. If S[i] would win, the attacker can change some bytes around index i+2A to make S[i+A] lower. They repeat this at index i+A finding a change to make S[i+2A] lower still. When graphed out this looks like a stair step pattern.
The attacker does have to make sure these points aren't too good. Statistically, each time a better point arrives, that lower score will be about half the previous score. This ensures normal data has no very long chunks. If the attacker is naive search time roughly doubles for each step. The attacker can choose not to use values that are too low to make future searches easier though. Increasing compute cost per step slows the rate of difficulty increase proportionally making this attack quite practical.
Finding a "Good Place" to Cut an Evil String
The above algorithm provides a hard guarantee on minimum chunk size. Any change that can make additional cuts can break the minimum chunk size guarantee and usually will. Most things involving math on the score values directly will fail badly.
The attacker can also join sections of evil attack parts together. They just need to find a piece of "glue" that gives hash values in the transition region that meet their attack requirements.
One way to prevent that is with a hash tree. The score S[i], being a cryptographic hash, is a commitment on Data[i-A:i+A]. The hash SHA2(S[i] | S[j]) Changes unpredictably if data is changed in the vicinity of either index i or j.
Supposing we run into a stair-step pattern. Points are spaced too closely together to be used as chunk boundaries. Using the scores directly is difficult but we can make a new set of scores by hashing the points with either their left or right neighbor. The local contest algorithm can be applied to these new scores again to winnow down the list of remaining points. The process is repeated until, points are far enough apart to meet minimum chunk size requirements. Keeping the algorithm from making progress requires the attacker to arrange for values in successive layer to be a stair-step pattern This becomes exponentially harder the more layers are involved.
Let me make this all a bit more clear
Assume the indices $\{j_1,j_2,j_3,...j_n\}$ are the indices of all scores s[j] which were the minimum value for a window S[i-A:i+A] passed over by the first algorithm. These are the points in a stair step profile along with other points that "won" and are now chunk boundaries.
Any chunks that are above the maximum chunk size must be processed further.
Take the indices J[n:m] corresponding to a chunk over the maximum size with J[n] and J[m] being that chunk's boundaries.
Look up the corresponding "interesting" first level scores I_1[k]=S[J[k]] for k=n...m.
We construct $I_2[k]=SHA2(I_1[k],I_1[max(n,k-1)])$ for k=n...m, hashing in the left neighbor to get the next level of score values.
This series of $(J[k],I_2[k])$ (index,score) points is processed by a similar beauty contest algorithm that finds local minimum points. Unless there is a similar stair-step pattern in the I_2 points, some points will be eliminated or will win and become chunk boundaries. This can be repeated for successive levels hashing in left and right neighbors alternately at each level and applying the "beauty contest" algorithm to reduce the number of point and pick winners at each level.
Eventually chunks that are oversized will be cut into non-oversized pieces. This works locally too since we don't need to see the ends of a chunk to know it is oversized. Just seeing a long stretch of string with no chunk boundaries tells us we need to apply another layer.
Each additional layer gets exponentially harder for the attacker to add so there's a limit to the number of layers the chunking algorithm will have to look at. This ensures the function can be evaluated locally, requiring a little less than A*(Max layers+2) bytes of context ever be looked at.
I haven't done any analysis, but I'd guesstimate an attacker won't ever get past 40 layers or so.
I could throw together some python code implementing this if you're still confused.
This is an original algorithm so there might be some vulnerability I'm not seeing.


Geometric interpretation of an Edwards curve

The geometric interpretation of the "addition law" on Edward Curves is not the same as for Weierstrass Curves.

The correct interpretation for this kind of curves is "adding their angles".
It works as on a clock. Of course, as for the Weierstrass curves, the geometric interpretation stands for the curve over the real numbers and not in a finite field (useful for cryptography).

You can give a look to the ECCHacks: a gentle introduction to elliptic-curve cryptography (starting at page 6) by Daniel J. Bernstein and Tanja Lange


You seem to have made a mistake in your arithmetic: $$108108 - 72097 = 36011 \ne 36012.$$

The number $36011$ is invertible modulo $256256$, and thus you can find $a$ and $b$ in a straightforward manner.

More generally, you could end up in a situation where both the difference of the ciphertexts $d_c$ and the difference of the plaintexts $d_p$ might share the same common factor $g$ with the modulus $m$.  In that case, what you can do is divide both of the differences and the modulus by this common factor to obtain $d'_c = d_c / g$, $d'_p = d_p / g$ and $m' = m / g$, and solve the reduced recurrence $d'_c \equiv a d'_p \pmod{m'}$.  This will give you the value of $a$ modulo $m'$, which will correspond to $g$ different possible values of $a$ modulo $m$, differing by multiples of $m'$.  If $g$ is relatively small, this can be almost as good for most purposes as obtaining a unique solution, since e.g. to decrypt any additional ciphertext you can just try all the possible solutions and see which of the results makes the most sense.


Looks like you found those algorithms here?

  I found out the point at infinity is (0, 1, 0), even I am not sure if this is correct.

Yes, you are incorrect about the point at infinity in Jacobian coordinates, which is $\infty = (1:1:0)$. See the answer here for more about that. If $P_1 = -P_2$, you have $P_1 + P_2 = \infty$.

I would highly recommend getting your formulas from the Explicit-Formulas Database in the future, or at least using it as a cross-check. They do a great job  sourcing where their algorithms come from.


Can we use a sort of "hash" function in CTR mode instead of a block cipher?

Your intuition is on the right track: if you run a pseudorandom function in counter mode with your secret key, you get a stream cipher.  Some stream ciphers are designed like this, perhaps most notably Salsa20 (and its later variant ChaCha20).

But the key to answering your question, as I see it, is to note that a collision-resistant hash function like SHA-2 is more complicated than what you need for this use:

You don't need the collision resistance property of cryptographic hash functions.
Standard cryptographic hash functions are unkeyed; they don't take a secret key as input.  You are using a custom construction to incorporate a secret key into your use of a hash function, and that means that you have to ask if your construction is secure, or use a standard construction that has been analyzed to be secure.
Hash functions (as normally understood) feature compression—they turn input data of arbitrary length into a fixed output size.  But you're feeding fixed-size inputs to the hash function.

So what you really want is a pseudorandom function that takes these three fixed-size arguments:

The key (secret);
A nonce (not secret);
A block counter value (not secret);

...and produces a fixed-size keystream block.  So if you read for example RFC 7539 ("ChaCha20 and Poly1305 for IETF Protocols") you'll notice that this is precisely the interface of the ChaCha20 block function (section 2.3):

  2.3.  The ChaCha20 Block Function

  The ChaCha block function transforms a ChaCha state by running multiple quarter rounds.

  The inputs to ChaCha20 are:

  A 256-bit key, treated as a concatenation of eight 32-bit little-endian integers.
  A 96-bit nonce, treated as a concatenation of three 32-bit little-endian integers.
  A 32-bit block count parameter, treated as a 32-bit little-endian integer.

  The output is 64 random-looking bytes.

Or, alternatively, feed the exact same inputs to a block cipher like AES.  Block ciphers are pseudorandom permutations (a subset of pseudorandom functions) and thus already keyed, and they work on fixed-size inputs already (they don't feature compression), so they're a good tool for this use.


How are Elliptic Curve private and public keys actually used to encrypt or sign data?

The simplest application of elliptic curves is Diffie–Hellman key agreement.  In a curve $E/k$ over a field $k$ with a standard base point $P \in E(k)$ of large prime order $\ell$ among the $k$-rational points (loosely, the points whose $x$ and $y$ coordinates are in $k$, and not in a field extension of $k$), Alice picks a uniform random scalar $a \in \mathbb Z/\ell\mathbb Z$ and publishes the point $A = [a]P$, the scalar multiplication of the standard base point $P$ by $a$; Bob does likewise with $b$ and $B = [b]P$.  Now Alice can compute $$[a]B = [a]([b]P) = [a\cdot b]P,$$ and Bob can compute $$[b]A = [b]([a]P) = [b\cdot a]P = [a\cdot b]P.$$  They can then both hash this common curve point into a shared secret $k = H([a\cdot b]P)$, and use $k$ for symmetric-key authenticated encryption, such as AES-GCM.

This is a high-level overview—there are, of course, devils in the details like how to choose the curve, how to represent the curve points, how to perform the computation, etc., some of which are addressed in SafeCurves.

But what about public-key encryption and public-key signature?

Encryption

Instead of using a long-term key pair $(a, A)$, when Alice wants to send a message to Bob she can generate a temporary secret scalar $t$, compute a temporary public key $T = [t]P$, compute a temporary session key $k = H([t]B) = H([t\cdot b]P)$, and transmit $T$ as associated data with a symmetric-key AEAD box (authenticated encryption with associated data) under $k$.

Then Bob, on receipt of $T$ and an AEAD box, computes $k = H([b]T) = H([t\cdot b]P)$, and uses that to open the AEAD box.

That's it.  It's just a DH key agreement with a temporary key pair.

Signature

There are a few different signature schemes out there based on elliptic curves.  For a detailed discussion of some of the design choices that go into conventional elliptic-curve signature schemes, see djb's blog post on how to design an elliptic-curve signature system.  Here's a couple of (very different) examples:

Example 1: EdDSA: Edwards-curve Digital Signature Algorithm (simplified)

This is the general form of the widely used Ed25519 signature scheme, which widely deployed and understood and considered by many to be the modern standard signature scheme.

Parameters.
A field $k$, a twisted Edwards curve $E/k: y^2 - x^2 = 1 - d x^2 y^2$ over the field $k$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to \{0,1\}^{512}$.

Public keys.
A public key is the representation of a point $A \in E(k)$.

Signatures.
A signature on a message $m$ is the representation of a point $R \in E(k)$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$ satisfying the verification equation $$[s] B = R + [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)] A.$$  Here $[s]B$ means scalar multiplication of the point $B$ by the scalar $s$, and $\underline R$ means the bit string encoding of the point $R$.

Private keys.
A private key is a secret 256-bit string $k$ chosen uniformly at random.  The 512-bit hash $H(k)$ is split into two 256-bit halves, the first interpreted as a scalar $a \in \mathbb Z/\ell\mathbb Z$ and the second taken as a bit string $h$.

To sign a message $m$, the signer computes the scalar $r = H(h \mathbin\Vert m)$, the point $R = [r]B$, and the scalar $$s = r + H(\underline R \mathbin\Vert \underline A \mathbin\Vert m) a.$$

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.

Example 2: BLS signatures using pairing-based cryptography

The Boneh–Lynn–Shacham signature scheme uses a function called a pairing, which is a bilinear map $e\colon E(k) \times E(k) \to G$ from the group $E(k)$ of $k$-rational -points on a curve $E/k$ with coordinates in the field $k$ to a multiplicative group $G$, typically the multiplicative group $(\mathbb Z/p\mathbb Z)^\times$ of integers modulo a prime $p$.

‘Bilinear’ means that if $X$, $Y$, and $Z$ are elements of $E(k)$, then $e(X + Y, Z) = e(X, Z) \cdot e(Y, Z)$ and $e(X, Y + Z) = e(X, Y) \cdot e(X, Z)$, i.e. that addition of two inputs carries through to multiplication of the outputs.  This further means scalar multiplication $[a]X$ the curve carries through to exponentiation $g^a$ in the target group: $e([a]X, [b]Y) = e(X, Y)^{a b}$.

Pairing-based cryptography is not as widely deployed, and its security is not as well-understood, but it admits very short signatures (half the size of Ed25519 with a curve of comparable conjectured security, for example), and it is simple to state.

Parameters.
A field $k$, an elliptic curve $E/k$, group $G$, a bilinear map $e \colon E(k) \times E(k) \to G$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to E(k)$ mapping messages to curve points.

Public keys.
A public key is the representation of a point $P \in E(k)$.

Signatures.
A signature on a message $m$ is the representation of a point $S \in E(k)$ such that $$e(S, B) = e(H(m), P).$$

Private keys.
A private key is a secret scalar $p \in \mathbb Z/\ell\mathbb Z$ such that $P = [p]B$, the scalar multiplication of $B$ by $p$.

To sign a message $m$, the signer simply computes $S = [p] H(m)$.

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.


Understanding WPA2 authentication in details

The following answers are taken directly from the 802.11 standard (2012 version).

The PTK is generated as follows:
$$\mathrm{PTK} \gets \operatorname{\mathrm{PRF-X}(PMK, ``pairwise \ key \ expansion", \\
min(AA, SPA) || max(AA,SPA)|| \\ min(ANonce, SNonce) || max(ANonce, SNonce)) } $$
where $\mathrm{AA}$ and $\mathrm{SPA}$ are the MAC addresses of the Authenticator and Supplicant, respectively.  The pseudorandom function $\operatorname{\mathrm{PRF-X}}$ is defined as follows for $X = 128,192,256,384,512$:

PRF-X(K,A,B):
   for i = 0 to (X + 159) / 160:
       Z = Z || HMAC-SHA1(K, A || 0 || B || i)
   return LeftBits(Z,0,X)

The MICs are computed using either HMAC-SHA1-128 or AES-CMAC-128 (which one to use is negotiated during the handshake).
The GTK is simply chosen at random by the AP.


Extractability for Simulator in Malicious Model

Let me try. First, one thing needs to be clear: simulation and real execution are two different things. The simulator can learn something does not mean a verifier in real execution can learn the same thing. Thus the fact that a simulator can extract knowledge does not affect the protocol’s zero-knowledge property (which is about the verifier in the real execution).

Why the simulator (or more accurately the knowledge extractor) can extract the knowledge but the verifier cannot? This is because the simulator has some special ability that the parties in the real world don’t have. One example is “rewinding”: the knowledge extractor can rewind the adversary to a previous state. If you are familiar with the Schnorr protocol, you should know rewinding is used to extract knowledge there. But can a real verifier rewind the prover? No.

Then why the knowledge extractor is given such an ability? It is for the sake of writing security proofs. A secure proof of knowledge protocol means that If the prover convinces the verifier, then it must know and use the witness in the protocol. This is hard to prove in fact. So we allow a knowledge extractor with extra ability to help us so that if the witness is used, the knowledge extractor can extract it from the transcript. Thus if the witness can be extracted, we can be certain the witness is used and  the protocol is proof of knowledge.


Attacks on schemes based on elliptic curves when the transmitted points are not on the curve

In this state we have well known attack that is called invalid-curve attack.

Let $E:y^2=x^3+ax+b$ and $E':y^2=x^3+ax+b'$ be two elliptic curves with reduced Weierstrass form. $E'$ is called an invalid curve relative to $E$.

Since formulae for adding and doubling points on $E$ does not involve coefficient $b$ thus addition law for $E$ and $E'$ is same. In this attack, we can send several low order points and find the private key using the chinese remainder theorem.

For more detail you can see "Guide to Elliptic Curve Cryptography" page 182.


Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).

However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P \neq NP$. Intuitively, to fix this, modify your language as follows:

$L=\{(1^n, x',y) ~\mid~ \exists x, |x| = n, x'\le x, \text{ and } f(x)=y \}$,

where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'\le x$ means $x'$ is a prefix of $x$).

Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.


Can RSA-PSS signing be made deterministic without loss of security?

Any probabilistic signature scheme can be made deterministic without any loss of security. The generic transformation is as follows:

Let $(pk,sk)$ be the key-pair of the original signature scheme
Choose a random key $k$ for a pseudorandom function $F$ (you can use HMAC or CMAC), where the output of $F$ is enough randomness used to sign. This key is part of the secret key.
In order to sign on a message $m$: First compute $r=F_k(m)$. Then, sign on message $m$ using randomness $r$.

It is not difficult to prove that the scheme is secure, as long as the probabilistic scheme is secure and $F$ is a PRF. (The bounds of the probabilistic scheme stay the same as well; the only difference is that you add the probability of breaking the PRF, which is insignificant.) In practice, this can be very efficient, by using HMAC or CMAC and then stretching the output to the required length using the result as a key to AES-CTR, or using HKDF or something of the sort.

In fact, it is very unfortunate that this is not the standard way of deploying dSA and ECDSA, since that would resolve the major weakness which is that if the same randomness is used for different messages, then the secret key is revealed.


is another method commonly practiced?

Sample $\lceil \log_2p \rceil+64$ bits, and reduce its corresponding integer modulo $p$.

There will still be a bias, but it is tiny.  And, assuming that you use a constant time modulo operation, it's constant time...


Why is Multiplicative group used in RSA or Euler's theorem but not additive?

Why we don't use additive groups? Is it a security thing?

Yes, it's a security consideration. If we used the additive group $(\Bbb Z_N,+)$ rather than $(\Bbb Z_N^*,*)$  for RSA, public encryption would go $M\mapsto C=e\,M\bmod N$ rather than $M\mapsto C=M^e\bmod N$. Problem is, decryption would be trivial since anyone with the public key $(N,e)$ could compute $d=e^{-1}\bmod N$ (e.g. using the extended Euclidean algorithm) and then decrypt as $S\mapsto M=d\,S\bmod N$, without knowing the factorization of $N$.

This is related to the order of $(\Bbb Z_N,+)$ being $N$ part of the public key $(N,e)$, when the order of $(\Bbb Z_N^*,*)$ is $\Phi(N)$, which is not easily obtained from the public key.


What happens if the sender is at another point in the sequence? ...
  the key is pressed while out of range to the car.

In a rolling code (code hopping) system,
the keyfob transmitter maintains a synchronization counter C,
incremented every time a button is pushed.
The car receiver stores the most recent
validated synchronization counter it has received N.

When a rolling code receiver gets a message with a keyfob serial number that seems to match one of the authorized keyfobs in its internal memory,
it extracts the keyfob's synchronization number C from the message and compares it to the most recent validated synchronization number N.

In the normal case:

C in the rolling window of acceptance -- C is more than but within "a few" codes K of the last validated transmission ( 0 < C-N < K+1 ).

When the counter C in the message is in the window of acceptance, then the car accepts that message as an authentic message,
the car overwrites N with the latest value C, and the car unlocks the doors or does whatever else the message says to do.

(As long as you hold down the button, the keyfob will repeatedly transmit bit-for-bit the same message over and over several times a second. It isn't until you let up the button and press it down again that it transmits a message with the next sequential counter number).

  So it is possible that the sender will get out of range of the k
  accepteded codes?

Yes. The AVR411 receiver defaults to WINDOW_SIZE = 100.
So with a typical AVR411 system, if the car doesn't hear 100 consecutive button-presses,
then the car will ignore the keyfob when it finally gets back in range.

With a typical KeeLoq system, if the car doesn't hear 16 consecutive button-presses, then the car will not unlock the doors on the first button-press of the keyfob when it finally gets back in range. However, if the car then hears 2 consecutive button-presses within the resynchronization window ( K < C-N < Resynchonization_Window ),
typically over a thousand button-presses,
the car will resynchronize and unlock the doors.
With a typical HCS301 system, if the car doesn't hear a few thousand consecutive button-presses,
then the car will ignore the keyfob when it finally gets back in range.

  How does they sync the point of the sequence?
  ...
  How are they
  implemented?

Before the keyfob can be used, the car must "learn" the keyfob.
Typically holding down the "learn button" ("learn switch") for 10 seconds erases the receiver's memory of every keyfob; then letting up on that button makes the receiver go into "learn mode".
Typically, pressing both the lock and the unlock button simultaneously on the keyfob makes the keyfob transmit its unique secret key to the receiver.
The receiver -- in learn mode -- memorizes the keyfob serial number(s) it hears as authorized keyfobs,
and also memorizes the secret key and the current synchronization counter N.
After everything is quiet for 10 consecutive seconds with no button presses, the receiver times-out of learn mode and goes into normal mode.

After that, that receiver -- in normal mode -- is now synchronized to the keyfobs.

The tiny amount of battery power available to the keyfob,
and the fact that the keyfob only transmits -- never receives -- makes it difficult or impossible to use many cryptographic algorithms.

For details on two popular rolling code implementations, see:

Wikipedia: rolling code
Atmel: "AVR411: Secure Rolling Code Algorithm for Wireless Link"
Microchip: "HCS301: KeeLoq Code Hopping Encoder"
Microchip: "AN661: "Code Hopping Decoder Using a PIC16C56"
Microchip: "AN1248: KeeLoq Receiver System"
Andy Carvell: RKE Analysis
Mike Szczys "Key fob programming"


Was the Enigma's double stepping mechanism intentional?

I suspect it was a semi-deliberate feature.  That is, while it probably wasn't a design goal in and of itself, it neatly solved a mechanical issue that would otherwise have required a more complicated and failure-prone solution.

What was the issue?  Simply, it was making the third wheel only advance one step at a time, rather than 26 steps in a row.  That's what would happen if the Enigma's notch, pawl and ratchet mechanism was modified to eliminate double stepping without making any other changes to it.

To see why this would happen, you need to note a couple of things about the way the Enigma stepping mechanism works:

Each wheel has 26 different positions it can be in, corresponding to 26 different shifts of the cipher alphabet.  Every time a key is pressed, a pawl tries to push each wheel one position forward.
Each wheel has a flange (an "index ring") with a notch at one (or, in some of the later wheels, several) of these 26 positions.  When the wheel is not in the notched position, the index ring holds up the next wheel's pawl and prevents it from rotating the wheel.

What this means is that:

The first wheel rotates one step on every keypress (since there's no other wheel before it to disengage its pawl).
The second wheel (normally) rotates on every 26th keypress, whenever the first wheel is in the notched position.
The third wheel only rotates when the second wheel is in the notched position — and if the second wheel would stay in the notched position when that happened, then it would keep rotating 26 times in a row (i.e. a full turn) until the second wheel would move out of the notched position again!

If the Enigma worked like that, its wheel positions would repeat with a period of only 26 × 26 = 676 keypresses, far less than intended and potentially less than the length of a single longish message.  But by letting the third wheel's pawl also engage the second wheel via the index ring and push it immediately out of the notched position as soon as the third wheel has rotated once — i.e. "double stepping" it — the period is extended to 26 × 25 × 26 = 16900 keypresses, i.e. to over 96% of the theoretical maximum of 263 = 17576 keypresses.

Also, the mechanical effect behind the double stepping, i.e. the pawl also pushing the notch it has dropped into, is something that kind of happens naturally in a mechanism like this.  While it probably could have been avoided by suitably adjusting the shape of the pawls and the notches, in this case it would've been counterproductive to do so.

The alternative solution, of course, would have been to redesign the mechanism to only rotate the third wheel when the second wheel moves into (or out of) the "notched" position.  That would certainly have been possible, even with early 1900s tech: a mechanical odometer, like you'd find in any old car, works exactly like that.

But the pin and gear mechanism used in odometers has more moving (and potentially breakable) parts than the Enigma's simple pawl and ratchet, and would probably have made swapping the wheels more complicated and error prone.  And, perhaps more importantly, odometers are often subject to "gear lash", especially if the mechanism is worn down, causing the later wheels to fail to rotate a full step when engaged.  While such misalignment is harmless in an odometer, and tends to correct itself on the next step, it could be a serious problem for something like the Enigma that relies on the wheels making a precise electrical contact with each other.

So I suspect the designers of the Enigma chose to go with the simpler pawl and ratchet mechanism, and accept an about 4% shorter period in exchange for mechanical simplicity and robustness.


When is public-key crypto used / when is symmetric crypto used?

One of the biggest drawback of the currently known public key schemes are the performances: it is slow. For instance, when using RSA, nowadays, one has to work with numbers in the range $\left[2^{2047},2^{4096}\right]$, which are really huge.

You've effectively understood correctly: generally, one encrypts data using a symmetric algorithm, which is fast, using a random "data encryption key" and then encrypts this key using public key cryptography.

This is the case for PGP, for instance. So when you are sending a mail encrypted with PGP, most of the time, the actual data is encrypted using AES, while only the AES key is encrypted using RSA.
This is generally called a "hybrid cryptosystem".

Symmetric encryption is effectively used to encrypt data, most of the time. This is true for all current schemes and protocols: TLS, PGP, etc. all rely on the fast symmetric encryption for the data.
Asymmetric encryption (also known as public-key) is generally only used to encrypt small packets, like a key.

Another use of public-key cryptography is for signatures, but when you are signing a message, what you'll sign is actually the hash of the message, so you benefit from the speed of the hash function and the slow public-key operation are only performed on a hash.
This also means that public key crypto is at the heart of the certificates everybody uses on the internet nowadays, since those are a special case of public key signatures in order to build a "chain of trust".

Finally, you mentioned the key management, and public-key cryptography is also used there to perform key exchanges, in order to establish a common key between two parties over an untrusted channel, given that they both have each other public key. That common key is then generally used to encrypt data over that same channel with a symmetric algorithm.


They used Miller's algorithm, which is explained in the next chapter.

(To be concrete, they used a implementation in Magma which is available in the author's website)


Lifting a congruence $f(X) \equiv gh (\textrm{mod} \ p)$ to a higher power moduli

One way to raise solutions to higher powers of the modulus is Hensel's Lemma.

First, you need to express your element as a root of a function: $g(u)= hu - (X-1)$
Find the solution modulo 2, which you already did.
Use the Lemma to raise this solution to higher powers of 2. Maybe it is useful to do this in several steps. Find the solutions mod 4,8,16 and then 32.


How fast can a SHA-256 implementation go?

Ryzen supports special instructions for SHA-256, achieving 1.9 cpb on long messages according to eBACS (graph). Assuming a 4 GHz clock, this corresponds 2.1 GB/s, 17 Gbit/s or 30 ns per block.

From the 22.5 cpb value for an 8-byte message (a single block), we get 180 cycles per block, 2.8 cpb or 45 ns for a single unpadded 64-byte block.


The simplest solution to this would be to encrypt Bob's pass phrase under Alice's pass phrase.

In particular the following steps would be carried out for that:

Generate a salted password hash (using e.g. Argon2 or bcrypt) from Alice's pass phrase, call it $SK$
Use $SK$ to encrypt Bob's pass phrase symmetrically, e.g. using AES-GCM

If you want to be fancy and allow Bob to update his pass phrase you can also symmetrically encrypt a private asymmetric key in step 2 and use the corresponding public key to encrypt the new pass phrase whenever Bob updates it.

This can also be integrated into the standard password-hash based authentication flow by using a fast hash (like a SHA256) of $SK$ as the stored database hash value.


Everything that happens on computers requires some energy. This includes the very act of looking up random values from any source.

There is a mythical beast called reversible computing which is basically computing without using up energy. It's unclear whether it can exist at all; but laws of physics (as we currently understand them) imply that reversible computing must also be logically reversible. This is known as Landauer's principle: if some information is erased in a process, then entropy (the physical notion) rises and this requires usage of some energy. Thus, computing a hash function necessarily requires some energy.

Note that this notion is about the conservation of information: it's not obtaining randomness that matters; it's about what you do with it.


Why not use ordinary hash functions for password hashing?

What's proposed, and PBKDF2 alike, give significantly less protection than scrypt or Argon2. That's because adversaries trying many passwords on parallel hardware can do so at lesser cost, for a given time or CPU × time on the legitimate user's side. With scrypt or Argon2, but not the question's construct or PBKDF2:

A significant amount of memory is required to compute the function. This implies that the adversary has to invest in that memory for each instance of password searcher, and can't use GPUs efficiently. Password cracking for PBKDF2 (or worse) entropy stretching is common practice, using GPUS, FPGAs, I guess ASICs. I conjecture government agencies do this routinely. Bitcoin mining ASICs are close to being usable to attack the question's construct at high rate (but are not AFAIK), and PBKDF2 has comparable complexity.
Multiple CPUs on the legitimate user's side are leveraged. This allows to perform more work on the legitimate side for a given user's wait (raising attack cost correspondingly). That's useful when the limiting factor for parametrization of the effort per password is the user's waiting time.

The question's construct is close to PBKDF1 and comparable to PBKDF2. The main operational differences are that

PBKDF1 and PBKDF2 have variable size output; PBKDF1 has built-in truncation, and PBKDF2 additionally allows large output. That makes them usable in more situations. But large output is immaterial for password storage, and PBKDF2's way of generating large output is poor, as noted by CodesInChaos in comment.
The question's construct (and PBKDF1) has the dubious property that for all $\mathsf{password}$, $\mathsf{salt}$, and bytestring $b$, it holds $F(\mathsf{password}\mathbin\|b,\mathsf{salt})=F(\mathsf{password},b\mathbin\|\mathsf{salt})$, which PBKDF2 avoids. This is typically immaterial for password storage, but conceivably could be an issue in some other uses of PBKDF2. However PBKDF2 used with HMAC (as it almost always is) has another potentially undesirable regularity, as noted in said comment: a long $\mathsf{password}$ and its hash are equivalent.
For 1 iteration of SHA-256 and uniform random input, the (likely) entropy in the output is only about $256-0.827\dots$ bit (see this), and that keeps on decreasing as the number of iterations grows (see this and this). That contrasts with PBKDF2-HMAC-SHA-256 for 256-bit output (probably) next to fully and uniformly covering it's output space, with no marked decrease as the number of rounds increases, for near 256-bit entropy. However that effect in the question's construct and PBKDF1 remains beyond experimentally observable as far as we know (that would imply an attack on SHA-256), nearly disappears anyway for significantly truncated output, and has no practical significance.


Quantum Secure Signing Algorithm with a 256 bit signature & key. Am I missing anything? Can I remove tradeoff?

In most cases, multiphases is fine. After all, Lamport is essentially multiphase.. send public key, send signature.

Not quite - with Lamport (or any other signature scheme), after seeing the public key and the signature, an attacker still cannot forge a signature; with your technique, he can.  Almost all uses of signatures rely on this property, and so your technique cannot be considered a general replacement.

If what you have meets the requirements of your problem space, that's fine.  Just realize that it really is a niche solution...

Actually, if you're happy with the limitations of your method, it can be simplified somewhat: to "sign" a message $M$, pick a random string $R$, and transmit $H(R, M)$ and $M$.  Then, in phase 2, transmit $R$.  This uses one fewer hash (and the hash can be of shorter length, as we're not giving away half the bits in the commit phase).


Ranking "amount of randomization" in a sequence

The various nist tests look for patterns which should not be present in random data.
For any such pattern, e.g imbalance, repetition etc. you can ask youself what is he likelyhood of this strength imbalance or worse occuring in random data. this is the pValue.
If we toss a coin multiple times we can count heads and tails. The closer they are to even the better. We can quantify this as probability. We then look at longer sequences and also expect them to show up more or less with equal frequency and again we can calculate pValue to quantify how likly discrepencies found are to be chance.
Most Nist tests already come with this built in.
We also like to analyze the cycle size of PRNGs even when they are too long to detect in a quick black box test this is another measure of "randomness".
Remember these tests are not sufficient for a PRNG to be secure. And though failing any means the stream is distinguishable from random it may still be decent for some cryptographic operations (Solitaire cipher as an example of a biased yet reasonably secure stream cipher).


Is it impossible to have a decentralized service using email addresses as login?

The core of your question is "Is there an attribute that an 'owner' of userA@example.com can be proven to have, and which no on else can be proven to have?" This heavily depends on the security of the email system, which, in general, is quite poor. Another central question is what "registration" even means. Presumably, it means "proving" one's identity, but proving it to whom, and how do others know that it has been proven? There has to be some process by which the "network" verifies identity, and then there has to be some process by which users verifies that the network has verified identity. Fully answering your question requires a precise formulation of what those processes are.

Ultimately, the only two possible unique attributes that an "owner" could have is the ability to send email, and the ability to receive/read email. Any other attributes, such as the ability to sign with a private key (asymmetric encryption) would mean that you're not basing it solely on email anymore. At that point, it's like asking "Is it possible to open a bottle with a spoon, if you also have a bottle opener?"

If you are confident on being able to detect email spoofing, then you can just have someone choose a private and public key, send their public key from their email to the nodes, and then sign everything with their private key.

If you're not confident that you can detect email spoofing, but you are confident that it is possible to send a message in such a way that only the "owner" of an email address can read it, then it's impossible for any single message to generate any attribute unique to the new user; any information sent in the email, the sending node also has. So you will have to have "the network" in general send multiple messages from multiple nodes, each with their own token.


What's the advantage of using OFB/CFB/CTR modes over a stream cipher

There is no real advantage, other than the fact that it allows you to convert a block cipher into a stream cipher securely.  Since there has been a large amount of research put into block ciphers and ciphers such as AES are commonly implemented in hardware (such as AES-NI), it allows for reuse of the primitives.

Side note: the nonce generally does not need to be random to be secure, it just needs to be unique.  Since it will be irreversibly and unpredictably permuted by the block cipher it can be predictable unlike an IV, but a nonce reuse is significantly more devastating than an IV reuse.


Should I assume that all exponent syntax in the description of a Diffie-Hellman-based protocol implies modding?

but does the use of a modulus or are the exponents literally meant to be exponents alone?

Well, in SPAKE2+, all operations are done within some finite group, typically either a prime multiplicative group, or an elliptic curve group.

If we decide to use a prime multiplicative group, then yes, addition, subtraction and multiplication are all done implicitly modulo the prime (division needs to be computed differently, doing a school book division and then taking the modulus does not work).

Because this is so universal in cryptography, we generally don't insert all the 'mod p' operations (and if you're using an elliptic curve group, that wouldn't apply anyways)


While poncho's answer gives an interesting example, why this can go wrong in practice, it does not necessarily answer the question from a theoretical point of view.
After all, we don't know whether $f(x) = AES_k(x) \oplus x$ is one-way. (Even if it might be reasonable to assume that.)

So, let's give a theoretical example.
Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$

From this function, we now construct a new function
$$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows:
$$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$
where $|x_1|=|x_2|=n/2$.

It is easy to show via reduction that $f$ is one-way whenever $h$ is one-way.
Let $\mathcal{A}$ be an attacker against the one-wayness of $f$, then we construct an attacker $\mathcal{B}$ against the one-wayness of $h$ as follows:
Upon input of $y$, $\mathcal{B}$ invokes $\mathcal{A}$ on input $0^{n/2}\Vert y$. Eventually, $\mathcal{A}$ outputs $x_1'\Vert x_2'$ and $\mathcal{B}$ outputs $x_1'$.

It is trivial to see that if $\mathcal{A}$ runs in polynomial time (in input length $n$) then $\mathcal{B}$ also runs in polynomial time (in input length $n/2$).

It is also easy to see the following holds: $$\Pr[\mathcal{B}(y) \in h^{-1}(y)] = \Pr[\mathcal{A}(0^{n/2}\Vert y) \in f^{-1}(0^{n/2}\Vert y)].$$
Therefore it follows that $f$ is one-way whenever $h$ is.

Now lets use this function $f$ in the proposed construction:

$$g(x) = f(x)\oplus x = (0^{n/2}\Vert h(x_1) ) \oplus x_1\Vert x_2 = x_1\Vert (h(x_1)\oplus x_2)$$

This is obviously not one-way. An attacker upon seeing an image $x_1\Vert y$ can simply output $x_1\Vert (y\oplus h(x_1))$ as a valid preimage.


RSA/DSA: Wouldn't it make sense to sign using decoding the data hash?

Your question appears to be "why do we use the terminology 'encoding' when talking about what we do as a part of the signature operation".  Well, we don't (at least, I don't, and I don't remember hearing that terminology from someone else).

As for RSA, well, the terminology you use is moderately irrelevant (as long as you do the cryptographical operations correctly, it doesn't matter what you call them); on the other hand, encoding would appear to imply that you are taking a 'signal', and putting it into a different representation, while decoding would appear to imply that your reversing that operation, and are putting the signal back into its original state.  While I suppose you could call the signature operation an "encoding" one, calling it a "decoding" one would appear to me to be an abuse of the terminology.

AS for DSA, well, your description of "encrypt the signature and he would get the hash" is not how DSA verify works; instead, the verifier inserts the signature, values from the public key and the hash into a formula, and if both sides of the formula are the same value, then the signature verifies.  There's nothing that can be usefully described as "decoding" here.


Definition of symmetric cipher and definition of asymmetric cipher

In simplest terms:
Symmetric encryption
Symmetric encryption uses the same key for encryption and decryption.
This key is called "secret key", because it has to be kept secret at all times or else someone could decrypt the encrypted message.
Examples of symmetric encryption:

AES
Vigenère

Asymmetric encryption
Asymmetric encryption uses one key for encryption and a different key for decryption.
The key for encryption is public knowledge and is called "public key". The key for decryption on the other hand is kept secret and called "private key". This is to ensure that only the possesser of this private key can decrypt a message, that has been encrypted with the corresponding public key.
Examples of asymmetric encryption:

RSA
Diffie-Hellman (Actually here the asymmetric part is the key-exchange and not a full encryption of a message.)


Timing vulnerability of byte array equality test?

The comparison c == 0, like the rest of your code, will probably run in constant time.

However, there's no guarantee that it will, and it's just barely conceivable that there might be some compiler and CPU combination out there where it might not.  Of course, that's basically true of any code not written in assembly for a specific CPU model and version.

After all, the C language standard does not actually offer any guarantees about execution times, and it would be perfectly valid for a smart enough compiler to look at your code, go "Hey! It looks like you're trying to compare two byte arrays for equality!" and decide to replace your code with a call to memcmp() or something equivalent.  And, as you can see from the results below, modern compilers actually are getting close to that level of cleverness, if they're not quite there yet.

Indeed, I suspect that the real reason why your code isn't getting optimized away like that is because compiler authors have more or less consciously decided not to make their compilers recognize it as a memory comparison, on the assumption that if you're writing your comparison code in such a convoluted way, you're probably doing something unusual and don't want it replaced by memcmp().

You can take a look at how common compilers translate your code into assembly using the Godbolt Compiler Explorer.  It turns out that, even on the same CPU architecture, the result depends a lot on the compiler and the optimization level chosen.

(I've included a fairly long discussion of the x86-64 assembly produced by various compilers below, since it's kind of interesting in itself, but it's really only relevant as an illustration of how much the compiler output varies.  Feel free to skip it.)

As a fairly typical example, when told to optimize your code for minimum size (-Os), GCC 7.2 generates a rather nice and simple piece of assembly code:

equal(unsigned char*, unsigned char*, int):
  xor eax, eax
  xor ecx, ecx
.L3:
  cmp edx, eax
  jle .L2
  mov r8b, BYTE PTR [rdi+rax]
  xor r8b, BYTE PTR [rsi+rax]
  inc rax
  or ecx, r8d
  jmp .L3
.L2:
  test cl, cl
  sete al
  ret

The last three lines of assembly correspond to your return (c == 0) statement, and indeed that part of the output seems to look pretty much the same (modulo register choices) for all compilers (for the x86-64 platform, that is) and optimization levels.  I would indeed expect it to run in constant time, assuming that the timing of test isn't data-dependent, which it really shouldn't be.

(At worst, if it wasn't constant-time on some CPU architecture, I'd expect the most likely timing differences to most likely be between the cases c == 0 and c != 0, which the code reveals through its return value anyway.  Of course, if you don't want that return value leaked through timings, e.g. because it's used as just one input to a more complex condition whose individual inputs should be secret, then even that leak could be too much.)

Of course, what typical timing attacks target isn't the final byte test, but the comparison loop itself.  And that's where the compiler differences really come in.  For example, at optimization level 1 or level 2, GCC's output looks quite similar to the code above.  (The main difference is that the loop condition test is moved to the end and an explicit test for len <= 0 is inserted at the top of the code instead.)  At optimization level 3, however, something weird happens and the output turns into this unrolled monstrosity:

equal(unsigned char*, unsigned char*, int):
  test edx, edx
  jle .L9
  mov rcx, rdi
  lea r8d, [rdx-1]
  mov r9d, 17
  neg rcx
  push rbp
  push rbx
  and ecx, 15
  lea eax, [rcx+15]
  cmp eax, 17
  cmovb eax, r9d
  cmp r8d, eax
  jb .L10
  test ecx, ecx
  je .L11
  movzx r8d, BYTE PTR [rdi]
  movzx r10d, BYTE PTR [rsi]
  xor r10d, r8d
  cmp ecx, 1
  je .L12
  movzx eax, BYTE PTR [rdi+1]
  xor al, BYTE PTR [rsi+1]
  or r10d, eax
  cmp ecx, 2
  je .L13
  movzx eax, BYTE PTR [rdi+2]
  xor al, BYTE PTR [rsi+2]
  or r10d, eax
  cmp ecx, 3
  je .L14
  movzx eax, BYTE PTR [rdi+3]
  xor al, BYTE PTR [rsi+3]
  or r10d, eax
  cmp ecx, 4
  je .L15
  movzx eax, BYTE PTR [rdi+4]
  xor al, BYTE PTR [rsi+4]
  or r10d, eax
  cmp ecx, 5
  je .L16
  movzx eax, BYTE PTR [rdi+5]
  xor al, BYTE PTR [rsi+5]
  or r10d, eax
  cmp ecx, 6
  je .L17
  movzx eax, BYTE PTR [rdi+6]
  xor al, BYTE PTR [rsi+6]
  or r10d, eax
  cmp ecx, 7
  je .L18
  movzx eax, BYTE PTR [rdi+7]
  xor al, BYTE PTR [rsi+7]
  or r10d, eax
  cmp ecx, 8
  je .L19
  movzx eax, BYTE PTR [rdi+8]
  xor al, BYTE PTR [rsi+8]
  or r10d, eax
  cmp ecx, 9
  je .L20
  movzx eax, BYTE PTR [rdi+9]
  xor al, BYTE PTR [rsi+9]
  or r10d, eax
  cmp ecx, 10
  je .L21
  movzx eax, BYTE PTR [rdi+10]
  xor al, BYTE PTR [rsi+10]
  or r10d, eax
  cmp ecx, 11
  je .L22
  movzx eax, BYTE PTR [rdi+11]
  xor al, BYTE PTR [rsi+11]
  or r10d, eax
  cmp ecx, 12
  je .L23
  movzx eax, BYTE PTR [rdi+12]
  xor al, BYTE PTR [rsi+12]
  or r10d, eax
  cmp ecx, 13
  je .L24
  movzx eax, BYTE PTR [rdi+13]
  xor al, BYTE PTR [rsi+13]
  or r10d, eax
  cmp ecx, 14
  je .L25
  movzx eax, BYTE PTR [rsi+14]
  xor al, BYTE PTR [rdi+14]
  or r10d, eax
  mov eax, 15
.L4:
  mov ebp, edx
  pxor xmm1, xmm1
  sub ebp, ecx
  mov r8d, ecx
  xor r9d, r9d
  mov ebx, ebp
  lea r11, [rdi+r8]
  xor ecx, ecx
  shr ebx, 4
  add r8, rsi
.L6:
  movdqu xmm0, XMMWORD PTR [r8+rcx]
  add r9d, 1
  pxor xmm0, XMMWORD PTR [r11+rcx]
  add rcx, 16
  cmp ebx, r9d
  por xmm1, xmm0
  ja .L6
  movdqa xmm0, xmm1
  mov ecx, ebp
  and ecx, -16
  psrldq xmm0, 8
  por xmm1, xmm0
  add eax, ecx
  movdqa xmm0, xmm1
  psrldq xmm0, 4
  por xmm1, xmm0
  movdqa xmm0, xmm1
  psrldq xmm0, 2
  por xmm1, xmm0
  movdqa xmm0, xmm1
  psrldq xmm0, 1
  por xmm1, xmm0
  movaps XMMWORD PTR [rsp-40], xmm1
  movzx r8d, BYTE PTR [rsp-40]
  or r8d, r10d
  cmp ebp, ecx
  je .L7
.L3:
  cdqe
.L8:
  movzx ecx, BYTE PTR [rdi+rax]
  xor cl, BYTE PTR [rsi+rax]
  add rax, 1
  or r8d, ecx
  cmp edx, eax
  jg .L8
.L7:
  test r8b, r8b
  sete al
  pop rbx
  pop rbp
  ret
.L14:
  mov eax, 3
  jmp .L4
.L9:
  mov eax, 1
  ret
.L12:
  mov eax, 1
  jmp .L4
.L13:
  mov eax, 2
  jmp .L4
.L10:
  xor eax, eax
  xor r8d, r8d
  jmp .L3
.L15:
  mov eax, 4
  jmp .L4
.L16:
  mov eax, 5
  jmp .L4
.L19:
  mov eax, 8
  jmp .L4
.L17:
  mov eax, 6
  jmp .L4
.L11:
  xor eax, eax
  xor r10d, r10d
  jmp .L4
.L18:
  mov eax, 7
  jmp .L4
.L20:
  mov eax, 9
  jmp .L4
.L21:
  mov eax, 10
  jmp .L4
.L22:
  mov eax, 11
  jmp .L4
.L23:
  mov eax, 12
  jmp .L4
.L24:
  mov eax, 13
  jmp .L4
.L25:
  mov eax, 14
  jmp .L4

It looks like GCC has vectorized the XOR/OR loop to process 16 bytes at a time using SSE instructions, with a bunch of additional special case code to handle the possibility that len might not be a multiple of 16.  At a glance, I suspect this may still run in constant time (for any given len value), but I wouldn't be more than pocket change on it.

FWIW, replacing the len parameter with the constant 16 gets rid of all the special-case handling and yields this very elegant assembly code with no jumps or loops whatsoever.  Literally translated back into C / C++, what it basically does is:

bool equal(unsigned char *a, unsigned char *b) {
    uint128_t c = *(uint128_t *)a ^ *(uint128_t *)b;
    c |= (c >> 64);
    c |= (c >> 32);
    c |= (c >> 16);
    c |= (c >>  8);
    return (unsigned char)c == 0;
}

As for other compilers, Clang's output looks pretty similar to GCC's at low optimization levels, but at -O2 and above, things get even weirder than with GCC.  Again, that's clearly vectorized with SSE, but (if I'm parsing the code correctly) it's only reading the input 4 bytes at a time and doing some really weird within-register byte shuffling.

The core loop of ICC's output at -O3 looks similarly vectorized as GCC's, although the rest of the code is quite different.  FWIW, if you fix the length at 16 bytes, ICC doesn't vectorize the code at all, although it does unroll it.  Also, ICC at -O2 and above is the only x86-64 compiler I found that doesn't use the test + sete combo for the final c == 0 test; it uses test + cmove instead:

  mov edx, 1
  test al, al
  mov eax, 0
  cmove eax, edx

Anyway, in practice, the only way to be really confident that your code runs in constant time is to (first examine the assembly output for any telltale signs of potential timing issues, and then) test it.

For example, here's a quick and dirty online benchmark showing that (at least for the specific platform, compiler, options and parameters used) your code does seem to be constant-time:

The first two tests (AllDifferent and AllSame) are general baseline timing tests, the next two (FirstHalfSame and LastHalfSame) exercise the comparison loop to see if its execution time depends on the length of the matching prefix / suffix, and the last two (CaseFlipped and LSBFlipped) exercise the final c == 0 test by comparing two strings which differ only by having a specific bit in each byte flipped.

Of course, in practice, you should carry out your benchmark using the specific compiler and hardware you're targeting (or as wide a selection of both as possible, if you don't have a specific target) and using realistic inputs (e.g. not just constant strings) to reduce the chance of compiler optimizations messing up your benchmarks.

(For example, while making the quick benchmark above, I noticed that assigning the output of the comparison to a global variable was necessary to stop the compiler from optimizing out all the comparisons entirely(!) and making them all run at same speed as the "Noop" baseline loop.  Also, in the AllSame test, I found that Clang is in fact smart enough to optimize out the comparison if both inputs point to the same address, so I had to use two separate strings with the same content to properly test it.  Benchmarks can be tricky like that.)


It is not accurate to say that the keystream from AES-CTR is a pseudorandom function. However, it is a pseudorandom generator. Furthermore, the construction that you gave is close to working but it's unclear where the key fits in. I will therefore elaborate on what we can exactly say.

Let $F$ be a pseudorandom function, and for simplicity assume that the key length, input length and output length are all the same (and of length denoted $n$). We denote by $F_k(x)$ the output of the PRF on input $x$, with key $k$. Then, we have the following two facts:

$G(k) = F_k(0)\cdot F_k(1) \cdot F_k(2)\cdots$ constitutes a pseudorandom generator.
$F'_k(x) = F_k(0 \cdot x) \cdot F_k(1 \cdot x) \cdot F_k(2 \cdot x) \cdots$ constitutes a pseudorandom function. Note that in this construction, $x$ has to be shorter than $n$ to provide "space" for the counter.

You want the first case when you want a PRG using AES. Especially when you have AES-NI this is a very fast option.

You want the second case when you want a PRF with input length $n$ and a larger output length. There are a number of ways of doing this. Another way is $F'_k(x) = G(F_k(x))$ where $G$ is any PRG.


Why is it not ideal to rely on interactive assumption to build PRF?

The advantage of a non-interactive assumption is that you prove something in general . In contrast in an interactive assumption you prove a specific instantiation of the problem. Think a variety of DL problems like DDH. The game starts with the challenger choosing the challenge. The challenge is given to the adversary and then the later is trying to solve it. That means for any instance of the problem. In contrast in an interactive assumption there is a learning phase like in CPA proof whereby the adversary is learning: is asking queries to the encryption oracle. That being said the proof is specific for that interaction. In some sense it is weaker because you cannot predict if there is a craft query that will break the system.


Security of Salsa20 with some known plaintext?

Yes, because there are no known weaknesses in (full) Salsa20.

http://www.researchgate.net/publication/226808260_The_Salsa20_Family_of_Stream_Ciphers


What is the probability of the first half of a hash output being identical to the first half of another hash output?

Let's say for example that I encrypt a password with some hash function and receive a 256-bit hash in return.

You cannot encrypt a password using a hash function, you can only create a hash value as the name implies.

  What are the chances that the first 128-bits (half) of this key are identical to the first 128-bits of another key?

The hash value can be used as a key, but usually you'd use a KDF for that. Hash functions can be used as KDF, but you're better off using a real KDF such as HKDF.

Obviously if the amount of possible "key" or "password" input is (next to) infinite then the amount of "keys" that map to a certain hash value is infinite as well. The same goes of course for the first 128 bits of the output.

The trick is that finding this particular input is hard as hashes are one-way. Basically you'd have to iterate over all possible inputs to find the hash, and iterating over that large an amount is (completely) infeasible.

Once you've chosen a key / password then you would have to perform a pre-image attack. In that case the hash is secure then you'd simply have a chance of $1 \over 2^n$ that another key / password hashes to the same value, where $n$ is the output size. So that's $1 \over 2^{128}$ for 128 bits of output and $1 \over 2^{64}$ for 64 bit of output.

If you just generate a large number of passwords then the chances of collisions between the set of hashes grows as well. In that case you have to assume that the birthday attack applies. The security then depends on the amount of hashes. For very large lists you should use 128 bits of output (giving about $2^{64}$ bits security for $2^{64}$ outputs).


It's not related to the possibility of backdoors in curve25519, no one thinks that curve25519 can have backdoors.
It's related to having a trusted procedure to generate publicly verifiable random numbers, which is an interesting thing to have, not only related to elliptic curves.

There is the need for a way to generate curves, any possible way is arbitrary.
You can lower the number of degree of freedom (see the bada55 paper), but at the end some choices need to be made and people can have different preferences.
These are not only related to the (unlikely) possibility of having backdoors but mostly related to more or less conservative options for curves.

For example, taking the case of curve25519,
Bernstein made some choices with Curve25519 with the purpose of achieving efficient implementation, particularly with the choice of the prime $2^{255}-19$, which is a pseudo-Mersenne prime, and it is not congruent to $3 \mod 4$, which is a very common choice as these primes allow an efficient square root calculation and a better cofactor for the twist curve(see "twist security" in 6.1 of the million dollar curve paper).
Basically he says that the curve is rigid because it is the fastest among those with a similar security level. But speed depends on implementations and platforms and one might wonder if this is a good way to measure rigidity.

His method doesn't allow for an algorithm to generate curves at arbitrary security levels, therefore some people might prefer to have a procedure, more than a curve, that they can trust. I think this is one of the advantages of the "million dollar curve" project.

Others have argued that having a prime whose bitsize is not a power of two is strange because it doesn't meet the usual definition of security level. In fact, in the common definition of security level, curve25519 doesn't meet the 128 bit security level, see this answer.

That is why, for example, Microsoft NUMS curves requires a prime of 256 bit for a 128 bit security level.

Others, again, tends to prefer random primes (e.g. Brainpool), and not  primes of special form. Random primes have some advantages (over pseudo-mersenne prime) when protection against side-channel is required, and are considered a more conservative choice (because they don't belong to a family they are not subject to some possible attack exploiting properties of that family. Not that such an attack exists on Elliptic Curves, but it exists for multiplicative groups).

I think it is an interesting project, but it's not going to replace curve25519 or P-256 in implementations or protocols.


If it's replaced by another function with the same length output, then I assume tweetnacl will use its output just as happily?

Yes, it seems to be a normal collision-resistant cryptographic hash function, replacing it by any other will not significantly alter the security properties (unless one of them is broken) but will of course break interopability.

In fact if you could find a security-relevant difference between two secure hash functions (given only oracle-access) at least one of them would be broken.


Is it safe to use a counter as IV for AES256-GCM

See page 20 of the NIST recommendations (28 in the pdf, 20 on the page) - basically this is the deterministic construction (assuming you're doing less than $2^{64}$ messages), so yes this should be fine - assuming (!) that you don't reuse IV (even across restarts / crashes).

Alternatively, you can use the RBG construction, and use a secure random source to generate the IV.


Suggestions for improving encrypt-then-mac flow

The primary purpose of the MAC in an Encrypt-then-MAC scheme is not to detect attempts to decrypt with the wrong key (although it may accomplish that as a side effect, depending on how the encryption and MAC keys are derived), but rather to make the scheme non-malleable, and thus:

protect the user's data from tampering by an attacker who can modify the ciphertext, and
protect the encryption part of the scheme from attacks (such as padding oracle attacks against CBC mode encryption) which are based on feeding malformed ciphertext to the decryption algorithm.

Thus, if you want your scheme to resist such attacks, you really do need to apply a MAC to the actual ciphertext that encodes the user's data.  Only MACing the (encrypted) item keys will not protect the user's data from tampering.  Thus, your "option 1" is definitely insecure.

Your option 2, on the other hand, does appear reasonable, at least as far as you describe it.  (I cannot, of course, tell if there are security flaws in the parts that you haven't described, or in the way that you implement the parts you do describe.)

Note that the iterated key stretching aspect of PBKDF2 is only needed when the input is a user-entered password or some other potentially low entropy string.  In your case, since you already have a high-entropy master key as input, you may safely reduce the iteration count to 1, or even use a non-iterating KDF such as HKDF.

Alternatively, I don't see any reason why you couldn't just double the length of your master key, and split it into two parts like you currently do for the item keys, except that this will require slightly more storage space for the master key.  But since you only have one of those, I doubt that would be a major issue.

If you wish to minimize the overhead of storing and authenticating the item keys, I could suggest something like that following scheme:

Store a single base master key (of, say, 256 bits); use HKDF-Expand (or PBKDF2 with an iteration count of 1) to derive a master encryption key and a master MAC key from the base master key.
For each item, store a single base item key (again of, say, 256 bits) encrypted with the master encryption key and authenticated with the master authentication key.
Derive an item encryption key and an item MAC key from the base item key using HKDF-Expand (or PBKDF2 with an iteration count of 1), exactly the same way as for the master key in step 1.
Use the derived item encryption and MAC keys to encrypt and authenticate the user's data.

This should consume no more space than your current scheme (assuming that the MAC tokens aren't longer than 256 bits, which they really have no reason to be), while protecting both the item keys and the items themselves from tampering.

As an extra precaution, you may also wish to include some metadata (such as user and item IDs) as "associated data" in the MAC calculations in steps 2 and 4.  This will prevent an attacker from, say, replacing one encrypted item and its item key with the corresponding data and key of another item.  Whether such attacks are actually a relevant threat for you will depend on things like what these "items" are actually used for, but since they're easily enough prevented, you might as well do it anyway.


I think of it this way: think of a distinguisher as an adversarially-chosen statistical experiment that attempts to support or refute some hypothesis, that again is adversarially selected.  This means that the honest party doesn't get to assume what meaning the adversary assigns to $0$ or $1$; their PRG has to behave like a random distribution no matter what the adversary does (with the proviso that the adversary's experiment must complete within polynomial time).

For example, a distinguisher could be an algorithm that takes the output of the PRG, chooses a random position in the bit string, tests whether the bits starting from this location are equal to some ASCII representation of the Gettysburg Address, and outputs $0$ if they are, $1$ otherwise.  If that's the statistical test the adversary wants to use, they can do it.


Partial hash code protocol for security tokens providing signatures

The answer is in the CEN-EN 14890-1:2009, 7.3 General Aspects, and in the SHA-1 and SHA-2 specifications. The output of the hash algorithm for both SHA-1 and SHA-2 is the state of the hash algorithm (specified by $H^{(0..N)}_x$), after the last block is processed. So the output size is identical to the running state, possibly truncated to the leftmost bits.

The following calculations are for SHA-1 and SHA-224/256, for the other SHA-2 hash algorithms the block size is 128 bytes and the length encoding takes 16 bytes. To understand the calculations it is necessary to have read FIPS-180-4.

So first the message is split up into 64 byte message blocks, where the final block consists of 1 to 64 bytes. All the blocks are processed outside the token, up to - but not including - the last message block. The internal state and the amount of bits encoded so far is send to the token, together with the last bytes. Then one or two blocks of padded data - see 5.1 of FIPS 180-4 - have yet to be hashed by the card (expressed as a kind of regular expression on bytes represented as hexadecimals):

MM{r} 80 00{x} LL{8}

where $x = 53 - r$ for $r$ between $1$ and $53$ inclusive (one block) or $x = 117 - r$ for $r$ between $54$ and $64$ (two blocks) where $r$ is the amount of remaining bytes to be hashed.

Then the hash function calculates the final running state and truncates it to calculate the hash output, which in turn is used as input for signature generation.


The Salsa20 core preserves diagonal shifts?

The input of the Salsa20 core is a 4x4 array of 32-bit words. If you move all the inputs diagonally (wrapping), the output will be the same as the original output, except that it's moved by the same offset.

$P^\prime_{i,j}=P_{i+k,j+k}$ implies $C^\prime_{i,j}=C_{i+k,j+k}$ (indices reduced modulo 4)

This symmetry follows directly from Salsa20 applying the same operations to all columns and all rows.

The full Salsa20 uses four fixed input words, which ensures that no matter how you choose the remaining inputs, you can never find two different inputs which could be transformed into each other using such a diagonal shift.


What machine learning accuracy is assumed to be predictable for TRNG/PUF application?

No we still idealistically target 50% inter hamming distance for PUFs, but being probabilistic and cumulative it's not set in stone.  It's just that you achieve 100% material efficiency at 50%. Or you can use the Jaccard index which should tend to zero, as in the variance of sets A and B  :-

I can't find many academic papers that claim a successful PUF implementations at a 60%/40% hamming distance or 0.5 Jaccard index.  It's even worse commercially, as technology like Maxim's ChipDNA is mired in patents and industrial secrecy.  Maxim only distributes it's security user guide for those chips on request (and I didn't).

That said, the following table lists some   tests for differing PUF constructs. Be aware though that they are not real.  They're based on Monte Carlo simulations which obviously requires pseudo random inputs.  The Flip-Flop PUF seems inefficient.  The bottom entry for the TV-PUF is what the authors are proposing, at ~50%.

From: Saha, Sehwag, V-PUF:A Fast Lightweight Analog Physical Unclonable Function. Paper.

Remember that the fuzzy extractor can do a lot with these values.  Given commercial confidentiality, it's quite hard to get to the bottom of what the physical PUF can do, and what the helper data and it's cunning algorithm glosses over.  It's easy create an extractor that will accept 128-bit input values and guarantees that challenges within 8 bits of each other will produce the same output with over 0.9999 probability .

Depending on your opinion of eprint.iacr.org, here's a DRAM PUF from Carnegie Mellon University which gives a Jaccard index < 0.25 (success). So as I opened, it's not set in stone at 50% hamming or 0 Jaccard.  You can always leverage the helper data given a large enough non-deterministic component.

It's worth noting that TRNGs and PUFs are kinda opposites. A PUF is ultimately required to be entirely deterministic, whilst a TRNG needs exactly the opposite behaviour. Non reproducibility is not   the same as non determinism.   Although it's not impossible, one construction tends not to be used for the other as that's not very efficient.


How to impelement mapping point Curve25519 to weierstrass point?

I'm not sure what is your question, I'm assuming you are not understanding why the mapping gives that particular result...

In ECC, all computations are carried out in a finite field. For Curve25519, all computations are done modulo $p = 2^{255}-19$.

To compute $u + A/3$, the division by three is actually $A$ multiplied by the inverse of $3$ modulo $p$. This inverse is the value that, when multiplied by 3, given 1 modulo $p$. This inverse is 0x5555555555555555555555555555555555555555555555555555555555555549; you can check that if you multiply this by $3$ and compute the remainder of the division by $p$ it will give $1$. Carring out the rest of the computation (always reducing modulo $p$) will give the expected result 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaad245a.

The modular inverse can be computed using the extended Euclidean algorithm or using Euler's theorem (which is computing the exponentiation by $p-2$).


How to prove Security of Onion Layers of encryption?

In CryptDB, it is not really cascaded. According to encryption schema the layers are decrypted. At the end, the lowest level is the your security.

The current layers are RND (Highest Security) , DET (For Joining queries), SWP (Search), HOM (Add), OPE (Sort) etc.  OPE being least secure as it allows more inferences about the underlying data fields than others. A data field that is encrypted all these Onion layers offer security only as strong as the weakest (OPE or similar) !

The fact that there is no need for the removal of the layer implies there is no need to layers.


XOR cipher with fixed key and known relation among plaintexts

I'm somewhat new at this, so there might be a better way to solve this, but this is how I solved it. If I understand right, the extra parameter given is written as:
$$\mathtt{}({e}_{1} \oplus k) \oplus ({e}_{2} \oplus k) = e_{3} \oplus k$$
(that is, the decoded contents of e1 xor'd with the decoded contents of e2 is equal to the decoded contents of e3)
The brackets only provide readability, and so the equation is the same without them. This means that we have $$\mathtt{}{e}_{1} \oplus k \oplus {e}_{2} \oplus k = e_{3} \oplus k$$
There are 2 "$\mathtt{}\oplus k$"'s on the left hand side here, so they can be removed to get the following:
$$\mathtt{}{e}_{1}\oplus {e}_{2} = e_{3} \oplus k$$
The right hand side can also be replaced with $\mathtt{}m_{3}$ to denote decrypted $\mathtt{}e_{3}$:
$$\mathtt{}{e}_{1}\oplus {e}_{2} = m_{3}$$
$\mathtt{}e_{1}$ and $\mathtt{}e_{2}$ are given, and by xoring them we can get:
$$\mathtt{}{m}_{3} = 1101001100$$
and we also know that:
$$\mathtt{}{m}_{3} = {e}_{3} \oplus {k}$$
Now we have both $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$, and we can now solve for $\mathtt{}k$:

xor both sides by $\mathtt{}e_{3}$
$$\mathtt{}{m}_{3} \oplus {e}_{3} = {e}_{3} \oplus {e}_{3} \oplus {k}$$
remove $\mathtt{}e_{3} \oplus e_{3}$ from right hand side:
$$\mathtt{}{m}_{3} \oplus {e}_{3} = {k}$$
substitute in $\mathtt{}m_{3}$ and $\mathtt{}e_{3}$'s values:
$$\mathtt{}1101001100 \oplus 11010110101 = {k}$$
giving...:
$$\mathtt{}k = 10111111001$$

You can now decode all 3 encrypted messages:
$$\mathtt{}m_{1} = 10011000011$$
$$\mathtt{}m_{2} = 11110001111$$
$$\mathtt{}m_{3} = 01101001100$$
Hope that helps.


A public-key encryption algorithm cannot rely exclusively on "public" randomness.  The reason comes down to the fact that encryption is a public algorithm that can be run by anyone. If the algorithm's output included all the random coins that it used, then an adversary could determine the message from the ciphertext, by running the encryption algorithm with the (given) coins and each of the two candidate messages from the IND-CPA experiment. The true message (and only that message) would yield the target ciphertext.

In some cryptosystems, the decryption algorithm recovers all of the encryption randomness. Examples include encryption schemes based on injective trapdoor functions like RSA. There's no contradiction with security here because one needs the secret key to recover the randomness.

For your second question, we can't go so far as to say that all publicly recoverable randomness is non-security influencing, i.e., replaceable by a fixed public constant (which is the contrapositive of your question).  For example, consider a PRG that uses some random public parameter along with a secret random seed (e.g., an LWE-based PRG).  Now consider an encryption algorithm that chooses both a public parameter and a seed for the generator, to produce a pseudorandom string for the "real" encryption, and outputs the parameter as part of the ciphertext. This would be secure, but might not be if we fixed the public parameter to be, say, all zeros.


Can N, q be shared for multiple users when using SRP-6A

You can pre-compute and hardcode N and g into your client and server. There's no harm in doing this. I do not believe that using per-user N will provide any additional security.

It is common practice to define SRP parameters for a particular application or (larger) protocol, see e.g. RFC 5054.


Encrypting messages without revealing length?

This is a complementary answer to the Model Nest's answer, and will concentrate on how to achieve the constant size for messages. We assume that the files have confidentiality, integrity, and authentication while sending/ receiving.
First of all, in the security proofs like the CPA game, we assume the messages have the same length, otherwise, the advantage of the adversary is 1.
With 10 MB file limit

Encryption time
Here we assume that the application limits the message size to 10MB. This makes 10485760 bytes and therefore one needs 655360 AES encryptions per file.
If you have the AES-NI then the time is not the issue see AES-NI can reach 5.4107GB per second on my machine. That is far from the 10MB. Some ARM has the AES-NI instructions, and the performance is not included in this answer.

Sending time The 4G LTE

Download: 20Mbps and theoretical ones of 150Mbps and it will take 4 seconds with 20Mbps to download
Upload: 8Mbps on average and 50Mbps that will make 10 seconds to upload.

If the message size is fixed to 10MB then the chatting will be slow and people will start to complain. An alternative method is using two sizes if the leaked information that is the distinction of a message is sent or a file is sent then this is applicable.
Therefore here we can say that the limit does not come from the encryption time but due to the network speed. 5G calculations are not included.
Padding options

PKCS#7: When we talk about padding the first that comes to mind is the PKCS#7 padding. However, that is not applicable here since it can support up to 256 bytes since each byte represents the length of the padding.

Zero one padding: This is fine as long as the underlying Encryption algorithm is CPA secure and the (Key,IV) is not reused as in AES-GCM. If used this padding will produce a cheap reveal of some part of the messages. One can use a nonce misuses resistant scheme like AES-GCM-SIV or a faster version AES-PMAC-SIV to mitigate this problem.
SHA-3 padding is also applicable

ANSI X9.23 with a little extension this padding can be used; the last 32 bits can represent the padding size and the space between the data and size is filled with 0.

ISO 10126 This is similar to ANSI X9.23 except instead of filling with zero, random bytes are filled. This seems like the best candidate.

Results:

We can hide the length of the messages with a prefixed size.

The encryption time is not an issue if AES-NI is available.

The upload and download time can be the issue of chatting.
As a matter of the fact, constant size is achievable in secure message applications but not preferable for general users.


period of the lfsr sequence after some manipulations

If you pick every 4th term in the sequence, since the original period $P$ is
$$
(2^{L_1}-1)(2^{L_2}-1)(2^{L_3}-1)=2^{L_1+L_2+L_3}-2^{L_1+L_2}-2^{L_1+L_3}-2^{L_2+L_3}+
\sum_{i=1}^3 2^{L_i}-1,$$
and relatively prime to 4, except for trivially small choices for the $L_i,$ you get a proper decimation and a reordering of the sequence. There is no truncation.

Thus $LC_{new} \leq LC_{old}.$ But note that each of the component maximal length sequences can be written as $\mathrm{tr}(c_i \alpha_i^t),$ where $\alpha_i$ is a primitive element in $GF(2^{L_i})$ and the constant $c_i$ from the same field is used to adjust the phase.

However, the trace map is linear under repeated squaring $$\mathrm{tr}(x)=\mathrm{tr}(x^2)=\mathrm{tr}(x^4),$$ (constant on cyclotomic cosets) and decimation by 4 is equivalent to taking the fourth power, so I contend that the linear complexity also stays the same.

In addition, the weight of the decimated sequence obviously doesn't change.

The weight of the original sequence will simply be $(P+1)/2,$ since the function is balanced and the all zero point $f(0,0,0)=0$ is missing from the truth table.


Why not use random world events instead of a proof-of-work algorithm?

A true source of randomness or a Common Reference String (CRS) as it's referred to in cryptography, could potentially be used in some cases in the place of Proof-of-Work, although as forest pointed out it isn't immediately clear how to achieve this or whether it is possible, especially in settings such as blockchains where something closer to a Random Oracle (RO) is needed. However, it may be possible to substitute the two in settings such as Proof-of-Stake, like Ouroboros is doing. In the latter case, because of the design of the system, a CRS is not really needed – the participants can generate their randomness locally.

However, for the sake of argument, I will now describe some reasons for which using the types of events you mentioned as a CRS is inappropriate for designing cryptographically secure decentralized systems.

Public verifiability. It is easy for any machine to locally verify proof of work in polynomial time. If you give a piece of proof of work to a mobile phone or a laptop, they can check to make sure it has been computed correctly. However, they cannot do so for thunders, unless they constantly monitor the earth. Public verifiability means that anyone can verify, even after the fact.
Consensus. Participants can easily agree on whether a piece of proof-of-work is correct. The condition is clear and well-defined. However, for real world events, this may not be so. For instance, there are weird physical phenomena which may be considered thunder by some scientists and not by others, or a thunder may be captured by one observer, but not by others, even if they are actively monitoring for such events. This disagreement can break consensus protocols which require that all participants agree.
Sustainability. Proof-of-work is a system which will continue to work ad infinitum, because it is based on a mathematical formula. Systems such as stock indices may not. Stock exchanges close down and indices are redefined or sunset. While these events may be rare, if we are building the economy of the future which we want to last for more than a hundred years, we want a system that can continue to function regardless of such changes. If these changes do happen and we rely on them instead of proof-of-work, we would have to redefine our systems every time a change happened, and such a redefinition would require making difficult consensus decisions (which can lead to forks in the case of blockchains).
Centralization. It is difficult to define an objective source of truth for the values of these events. If the source of truth is defined as, say, the stock exchange website, then the central party that runs the website can manipulate the values that are displayed there. This makes the system prone to centralized manipulation. For instance, a court can order the exchange website to display false data in order to subvert the system.
Distribution. It is difficult to say what kind of distribution is followed by various sources of randomness such as the stock market. The fact that the stock market is just a random walk is controversial, and using this hypothesis to ensure our economy's future is an incorrect approach, especially because we cannot quantify it and prove our claims. While there exist ways to extract good randomness from skewed randomness, some quantification of the entropy in the source is needed, for which we also have a limited understanding.
Manipulation. This is related to the last two points above. Some of the systems you are proposing may be possible to manipulate by participants, given enough incentives. For example, if I am a rich investor, I could buy or sell a particular stock to change the value of the index, skewing the randomness in a particular predictable manner. If this artificial biasing is something I can use in my favour to make more money than I need to invest to cause the skewing, then it may be rational to act in that manner. It is difficult to give a game theoretic argument that such acts are impossible. With proof-of-work, the outcome cannot be artificially manipulated.


Neither mode provides authentication, so in that sense they are both not very secure. CBC has more error propagation obviously, but as the last paragraph of the quote in the question states, error propagation is mostly ignored by now.
CBC requires an unpredictable IV (for the attacker), while CTR mode just requires a nonce. However CBC fails less dramatically if the IV is repeated or when too many data packets are encrypted.
CBC is vulnerable against padding oracle attacks in the correct setting, which makes the mode more vulnerable (if you count padding as part of the mode). However, both are vulnerable against plaintext oracles, and CTR mode then allows each bit to be changed individually, which is just as dangerous in my opinion.
So in the end, which one is more secure depends on how the mode is used. Both can be used to create a secure system by providing confidentiality. CTR has more practical benefits in the end (parallelism, nonce), which is likely why it is ending up as underlying encryption scheme for authenticated modes such as CCM, GCM and EAX.


What are alternatives to Proof of Work for consensus of a blockchain that doesn't contain anything of value?

a blockchain that doesn't contain anything of value

Do you mean a blockchain with no associated token? If the data really has no value, no one will be interested in storing it on a blockchain.
If there is a limited amount of writers (i.e. up to ~100 nodes), it is possible to create a consortium network and deploy a blockchain using a Byzantine Fault-Tolerant (BFT) consensus (e.g. Proof of Authority). These blockchains do not require a token/cryptocurrency for the consensus. This is typically referenced to as a permissioned blockchain (as opposed to a permissionless/public blockchain such as Bitcoin or Ethereum).
Permissioned blockchains have different very different tradeoffs compared to permissionless blockchains. The blockchain is controlled entirely by permissioned nodes which are the only ones allowed to perform writes (in a public permissioned blockchain anyone is able to read). This model generally support a much higher throughput (more transactions per second) compared to permissionless consensus. Since nodes are authenticated in BFT protocols, the consensus model is designed to resists against malicious nodes up to a certain threshold (e.g. 1/3 of malicious nodes).
As a side-node, the flowchart in Fig. 1 from Do you need a Blockchain? can help to determine if a Blockchain is the appropriate solution for a problem.


Where can I find open source code for Encryption Switching Protocol?

I am one of the authors of this paper. We did not implement encryption switching protocols, and as far as I know, they were never implemented. If you plan to implement them, I will be happy to answer questions about specific points. However, I cannot really give general insights about how to implement them: it's a long paper, with a relatively large number of rather complex constructions. The first step would probably be to implement our new variant of ElGamal - good implementations of the Paillier encryption scheme, which we also use, are already available.


The approach is deeply flawed in many ways.

It is very plausible that the whole buffer is returned at zero under heavy load, which is something that an attacker can often intentionally cause (e.g. with a flood of network traffic requiring high CPU load; starting a number of https connections comes to mind). That's likely to be a practical disaster.
Mechanism: the three threads launched by ThreadedSeeder are set to Lowest-priority, thus it is reasonable that they won't do anything before the Thread.Sleep(10). If the machine has higher-priority-than-Lowest things do during that pause, execution can proceed to doThread = false before the Add thread has ever tested doThread, thus with Add performing nothing related to buffer. The same could hold for Multiply and Shift too, but that's immaterial, as these threads can not un-zero buffer even if they run.
More generally there is little insurance about the number of times DateTime.UtcNow.Ticks is called; that could be very few, including less than once per buffer entry, thus always leaving all the other entries at zero. The busiest the machine, the more likely it is that a buffer entry has no, one, or very few readings of DateTime.UtcNow.Ticks to influence it.
I see no mechanism preventing Multiply or Xorshift from competing with Add about what element of buffer it operates on, and thus void a change Add makes meanwhile. This is an uncontrolled race condition, and it can loose some of the entropy gathered.
DateTime.UtcNow.Ticks can be closely approximated by adversaries. That's supposed to be the UTC time, which is not a secret. Further, common mechanisms such as RFC 7323 high-resolution TCP time stamps allow to find what a particular machine believes the UTC time is, even when it is poorly synchronized. And when the machine is under light load, with one CPU running each thread including Add at full blast, the difference between readings will be reasonably repeatable.
The transformation made from DateTime.UtcNow.Ticks to what is in each element of the buffer is one among relatively few public transformations. And each of these possible transformations is trivially reversible (modular multiplication by an odd constant modulo a power of two is reversible in Multiply, as well as each of the three bitwise operations in Xorshift). Combined with 4, it trivially allows a very selective distinguisher on each buffer element output whenever there is only a single DateTime.UtcNow.Ticks that influenced it, also revealing which transformation occurred. It looks like this could be extended to a few such influences.
Neither the code nor the text of the question shows any effort to create explicit diffusion of the entropy gathered: elements of buffer are never mixed. Absent such mixing or/and post-conditioning before use of buffer, some degree of 2/4/5 can be a practical disaster.
Timing execution won't gather any entropy in some precisely controlled execution environments, including VMs/simulators used by hardware engineers or reverse-engineering of malware. Ultimately, the state of buffer on output, and whatever is deterministically derived from that, will dependent only on when the task is launched.


chaining multiple key derivation functions together

Yes, there's an issue: you're adding needless complexity, which gives you absolutely no benefit.

The whole point of a PBKDF is to be slow; passwords are low-entropy, and the only way to mitigate brute-force is to make it take time to compute hashes. It can't take too long to log in, so you have to balance "fast for a user" and "slow for an attacker." Attackers use hashes differently than users; an attacker will be trying many, many, many combinations, possibly on specialized hardware, while a user only tries one password at a time.

The trouble with combining hashes is that you only have a certain amount of time and resources you can give your hashing process. If you take 200ms for PBKDF2, 200ms for bcrypt, and 200ms and 16 MB for scrypt, your system takes 600ms to compute a hash. Suppose that PBKDF2 hardware implementations are \$1.00 per 100 threads of PBKDF2; bcrypt ones are \$50.00 per 100 threads of bcrypt; scrypt ones are \$100 per 100 threads of scrypt (these numbers are wholly made up). Then an attacker can attack 300 hashes at once for a cost of \$151; this will check a new hash every 2ms on average. If you just used scrypt with 600ms and 16 MB required, then an attacker would need 300 scrypt threads to get that throughput; this is \$300.

Basically, the issue with combining them is that you're shifting hash time from a stronger algorithm (where it's expensive for the attacker to do things faster than you) into a weaker algorithm (where it's cheap for the attacker to do things faster you).


In the RSA DES challenges, how did the contestants know they had found the right key considering they weren't given any plaintext?

One can still access the challenge rules from the archive.org

  Each contest is based on a specified cipher. A brief piece of printable ASCII text (containing byte values in hexadecimal notation from 0x20 to 0x7e) will be appended to the fixed 24-character string "The unknown message is:". The result will be padded and then encrypted with the associated cipher under a randomly-generated key.

The message is also padded by PKCS#5 padding. Thus, the attacker has three options to test their results;

Check the beginning of the message; it must start with "The unknown message is:"
A valid PKCS#5 padding at he the end.
And, one general rule when only ciphertexts are given; one can check the result is valid (English) language. For this, one block may not be enough, since there are many valid words in the 64-bit block. One block will result in many keys. To narrow the keys, additional ciphertexts are required. This approach can be work even 1. and 2. cases are not known. For this specific challenge the range of the characters given between 0x20 and 0x7e, i.e. between  and ~

distributed.net  found this message in DES Challenge II-1;

The secret message is: Many hands make light work.

Note : It is interesting that the Wikipedia says; The secret message is: where the source is lists.distributed.net, however, the RSA archives says The unknown message is:.


No, this system is not secure. Knowledge of the private key immediately gives enough of the public key that we can immediately encrypt an arbitrary message.

The NTRU decryption key includes a polynomial $f$; the encryption key is essentially $f^{-1}g$, where $g$ is a polynomial with coefficients in the set $(0, p, -p)$.  Anyone with the private key can immediately compute $f^{-1}$; while they won't be able to recover the value $g$ (that's not actually referenced within the private key), what the attacker could do is just pick a legal $g$, and then use that to encrypt any message he wants (as no one else with the decryption key will be able to determine that's not the current $g$ value. It won't be the same key as the legitimate encryptor; however it will be accepted by anyone with the decryption key.  Alternatively, he can just get any known text signed by the correct encryption key; that'll give him enough information to recover the correct $g$.

It sounds like what you want is a signature method; that is, a way where someone with the private key can 'sign' a message, and anyone with the public key can verify that signature (but cannot generate their own signatures).  There are lots of signature methods known; some proposed methods are based on NTRU, but the unbroken ones are fairly new; I'd personally wait for cryptanalytic results against them, but if you have your heart set on an NTRU-based method, you can look at this paper.  That would certainly be more secure than what you're doing now.