Are factorization algorithms parallelizable?

Summary: to a considerable degree, more computers speed up factorization of a given integer; but the expected time decreases significantly slower than the inverse of the number of computers used: we are in the area of sub-linear speedup.

Some high-performance (but not the best) factorization algorithms, in particular ECM, enjoy near-linear speedup with the number of computers used; in practice, only the initial distribution of parameters and the announcement of success by the lucky computer requires communication between computers. Failure of one computer is not a serious problem, its work can be ignored, or redone.

Problem is, the best algorithm we know for integer factorization is GNFS, which is asymptotically faster than ECM for factoring $N=p\cdot q$ with two factors $p$ and $q$ of about equal size, as often used in RSA (and in the theoretical setup in which BBS is typically discussed); the crossover, though dependent on many things, is perhaps $N$ of 300 bits give or take a factor of 2. So what's really needed to attack that mainstream variant of RSA is efficiently running GNFS on multiple computers.

Simplifying greatly, GNFS has two main bottlenecks:

The relation collection step (also known as sieving step), which is efficiently run on ordinary computers sending the relations they found by ordinary broadband network (internet) for the next step; not much of a parallelization problem here.
The matrix step, which can and is routinely distributed between multiple CPUs, but requires massive communication between these (ideally, high-speed shared memory, which is not achieved beyond a few CPUs or cores even on enterprise-grade servers, where 8 heavily interconnected CPUs each with 18 cores each with 2 threads is the current high-end, see SEJPM's comment), and very expensive in high-performance computers which implement the highest level of interconnection between many nodes using specialized technology (such as infiniband).

However, there are parameters in GNFS that allow a trade-of between making more work in the relation collection step, against manipulating considerably less data in the matrix step (again simplifying: only the best relations are sent for use in the matrix step, others are discarded). The issue is complex, well beyond my full grasp, but I'll give two meta-arguments that parallelization helps a lot:

In the record Factorization of a 768-bit RSA modulus (collective, in proceedings of Crypto 2010), "In total 64 334 489 730 relations were collected, each requiring about 150 bytes" "for an average of about four relations every three seconds" "scaled to a 2.2 GHz Opteron core with 2 GB RAM"; that's about 500 000 core⋅day of said core. For the hard part of the matrix step, "doing the entire first and third stage would have taken 98 days on 48 nodes (576 cores) of the 56-node EPFL cluster" of "3.0GHz Pentium-D processors on a Gb Ethernet"; that's 60 000 core⋅day of pragmatically-coupled (rather than coupled-to-the-max) CPUs; even if cores do not quite compare, significantly more work was done on relation collection than in the matrix step. I conclude that the matrix step was not the limiting bottleneck by any metric other than capital investment (and the expensive cluster was not purpose-built, and was only used for months versus years for the computers collecting relations).
Arjen K. Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer's Analysis of Bernstein's Factorization Circuit (in proceedings of Asiacrypt 2002) conclude that with a custom hardware "device that costs a few thousand dollars" proposed by Daniel J. Bernstein to perform the matrix step efficiently, "from a practical standpoint, the security of RSA relies exclusively on the hardness of the relation collection step of (GNFS)".


How to convert a Galois LFSR to a Fibonacci LFSR?

In this answer I will consider the Galois LFSR mentionned at this question: Sequence output by a Galois type LFSR see the image below.

First we assume that the 5 positions of bits are numbered from left to right: 0 .. 4

The Galois representation is as follows:

+--------------------------------------------------------------+
|                         |           |           |            |
|    +-----+     +-----+  |  +-----+  |  +-----+  |  +-----+   |
|    |     |     |     |  v  |     |  v  |     |  v  |     |   |
+--->+  1  +---->+  0  +--+->+  0  +--+->+  0  +--+->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

If we iterate the LFSR for 10 rounds we get:

1 0 0 0 0 : initial state
0 1 0 0 0 -> 0
0 0 1 0 0 -> 0
0 0 0 1 0 -> 0
0 0 0 0 1 -> 0
1 0 1 1 1 -> 1

1 1 1 0 0 -> 1
0 1 1 1 0 -> 0
0 0 1 1 1 -> 0
1 0 1 0 0 -> 1
0 1 0 1 0 -> 0

Assuming now that we have a Fibonacci LFSR but we want to know where the tap are.
We will iterate the lfsr and naming the unkowns by letters.
There are two tricks involved to solve this:

a letter is once set and never modified later (as opposed to the Galois version)
using an initial 10000 state will reveal the positions of the taps.

So we have:

1 0 0 0 0 : initial state
a 1 0 0 0 -> 0            (i)
b a 1 0 0 -> 0
c b a 1 0 -> 0
d c b a 1 -> 0
e d c b a -> 1

Then we can solve it.

f e d c b -> a = 1

By (i), we can deduce that position 0 influence on output: all the other positions are null.

g f e d c -> b = 0 -> b

b would be 1 if only position 0 had an influence. Thus Position 1 is also influencing making it back to 0.

h g f e d -> c = 0

c would be 0 if only position 0 and 1 had an influence. Position 2 is also influencing making it back to 0.

i h g f e -> d = 1

d is the value it should be thus position 3 is not influencing.

j i h g f -> e = 0

e is the value it should be as there is the feedback.

If we continue on the next 5 outputs on both models we have the following stream: 01111

To conclude the Fibonacci representation of the LFSR is the following:

+-------------+-----------+-----------+------------------------+
|             ^           ^           ^                        |
|    +-----+  |  +-----+  |  +-----+  |  +-----+     +-----+   |
|    |     |  |  |     |  |  |     |  |  |     |     |     |   |
+--->+  1  +---->+  0  +---->+  0  +---->+  0  +---->+  0  +-------> ...
     |     |     |     |     |     |     |     |     |     |
     +-----+     +-----+     +-----+     +-----+     +-----+

Here is a small python code to check the equivalence between both.


$\newcommand{\compose}{\mathbin{\circ}}\DeclareMathOperator{\AES}{AES}\DeclareMathOperator{\Round}{Round}\DeclareMathOperator{\Final}{Final}\DeclareMathOperator{\KeyExpansion}{KeyExpansion}\DeclareMathOperator{\SubBytes}{SubBytes}\DeclareMathOperator{\ShiftRows}{ShiftRows}\DeclareMathOperator{\MixColumns}{MixColumns}\DeclareMathOperator{\AddRoundKey}{AddRoundKey}$The AES function is mathematically a composition of other functions:
\begin{align*}
  \AES_k(m) &= \Final_\kappa({\Round_\kappa}^r(m))
    \quad \text{where} \quad \kappa = \KeyExpansion(k), \\
  \Round_\kappa(m) &= \AddRoundKey_\kappa(\MixColumns(\ShiftRows(\SubBytes(m)))), \\
  \Final_\kappa(m) &= \AddRoundKey_\kappa(\ShiftRows(\SubBytes(m))).
\end{align*}
This is a mathematical description.  You can write the same mathematical description as a composition of functions:
\begin{align*}
  \AES_k &= \Final_\kappa \compose {\Round_\kappa}^r
    \quad \text{where} \quad \kappa = \KeyExpansion(k), \\
  \Round_\kappa &= \AddRoundKey_\kappa \compose \MixColumns \compose \ShiftRows \compose \SubBytes, \\
  \Final_\kappa &= \AddRoundKey_\kappa \compose \ShiftRows \compose \SubBytes.
\end{align*}
(Here ${\Round_\kappa}^r$ means $\Round_\kappa$ iterated $r$ times, i.e. $\Round_\kappa \compose \cdots \compose \Round_\kappa$.)

To implement AES, you could write software instructions, or design a circuit, that follows exactly this structure, by making a $\SubBytes$ circuit, and wiring it to a $\ShiftRows$ circuit, etc.  Not all AES implementations do this.  For example, Paulo Barreto adapted the composition of column and row transpositions with a table lookup into just a composition of table lookups (mathematical description, example source code).

Any physical implementation of AES will have physical characteristics like timing and power usage.  Different physical implementations might be different approaches to evaluate the same function.  For example, here are two C implementations of the mathematically same table lookup:

uint8_t S[256];

uint8_t
fast_vartime_lookup(uint8_t b)
{
        return S[b];
}

uint8_t
slow_consttime_lookup(uint8_t b)
{
        uint8_t m, r = 0, i = 0;

        do {
                m = ((b ^ i) - 1) >> 8;
                r |= S[i] & m;
        } while (++i);

        return r;
}

These are two ways to implement the $\SubBytes$ round function, and they could be written mathematically by two different compositions of different mathematical functions, although they always give the same results for the same inputs.

An AES implementation using fast_vartime_lookup and an AES implementation using slow_consttime_lookup could be called implementations of two self-dual ciphers—recall the definition of dual ciphers $E$ and $E'$ as the existence of functions $f$, $g$, and $h$ such that for every key $K$ and plaintext $P$, $f(E_K(P)) = E'_{g(K)}(h(P))$; in this case of self-dual ciphers, $f$, $g$, and $h$ are all the identity function, so that $E_K(P) = E'_K(P)$.

The pragmatic differences of fast_vartime_lookup and slow_consttime_lookup are in the mean and variance of the time they take to execute.  The mean time of fast_vartime_lookup is much shorter than the mean time of slow_consttime_lookup, to the point that if handed an AES implementation using slow_consttime_lookup you would probably throw it away in disgust.  But the variance of slow_consttime_lookup is near zero, whereas the variance of fast_vartime_lookup is significant, and the time that it takes depends on the values of secrets and the state of the machine's CPU cache—this is what enables cache-timing attacks to recover secrets by timing AES computations.  Newer cipher designs like Threefish avoid the temptation to use leaky operations like fast_vartime_lookup in the first place.

The paper you cited is about thwarting different classes of attacks, namely power analysis, by using a circuit implementing a different self-dual cipher (or, just a differently structured circuit implementing the same cipher—same idea) for each round, and randomly chosen for each round, so that the adversary not only has to guess the key and/or plaintext and any other variations in power usage of the device, but also the choice of circuit at any given time when sampling.

This is not the only technique for thwarting power analysis—there is a large public literature on the subject, and doubtless an even larger secret proprietary literature because it usually lies in the domain of hardware manufacturers who clutch at trade secrets like pearls even though most of it is probably rediscovered over and over and over again by different hardware vendors.

Another example countermeasure in hardware is to compute everything simultaneously with its complement; of course, this costs extra area.  Another one—which also works in software—is some form of blinding, typically in asymmetric crypto like RSA which has additional structure that is invariant under the private key operation: $(r c)^d \equiv r^d c^d \pmod n$, so since $r^e r^d \equiv 1 \pmod n$, $c^d \equiv r^e r^d c^d \equiv r^e (r c)^d \pmod n$; thus you can pre-multiply by a random $r$ and post-multiply by $r^e$ so that the base of the modular exponentiation is uniform random and independent of the secret $c$.  This doesn't work generically with AES because AES is designed to destroy all structure coming into it like a supervillain bent on bringing the apocalypse, but the randomization of circuits implementing the round function is a variation on the theme.


Proof generation complexity is large but better than previous ideas.
For the verifier the complexity depends linearly on the size of the function the input and the output $O(|f|+|x|+|y|)$ where $y=f(x)$ the computation to be verified for a particular value security of the parameter.
The proof size is constant.

For more details you can check the papers and implementations in http://www.scipr-lab.org. I think it is the best resource on the subject.


How many different keys can be derived with HKDF before two outputs are identical?

I've seen this a few times, so I want to point out something that is a general misconception. People often think that for key derivation, it's really important that I don't get repetition, since that is a break. However, this is actually very not true, and the opposite is true. I will explain.
The "ideal situation" is to just choose keys, truly at random. In this case, if I am working with 128-bit keys, the birthday paradox still holds. As such, after generating $2^{64}$ truly random keys, they will repeat. This is not a problem at all. On the contrary, it guarantees that even if you saw all of the previously generated keys, you have no information on the next one. Furthermore, all (symmetric) encryption uses an IV, so you'd need the random IV and the key to collide in order to be able to detect that two different people/cases are using the same key.
One would think that it would be better to choose keys purposefully so that they don't repeat. But this would mean that keys get less and less random, and have lower entropy as time goes on. In particular, given past keys, the new key is known to not equal any of those. So, we actually do not want to do that.
Just to stress this, using AES for key derivation directly (e.g., in CTR mode), the quality of the key derivation goes down when you get close to the birthday bound because the keys can't repeat. Thus, since the keys can't repeat, that means that the key does not look like a random one. I know that this is the opposite of most people's intuition, which is why I felt it important to point out.


Is it okay for $T(H)$ to be small, as long as actually finding such a collision is infeasible, or does a small $T(H)$ imply $H$ is weak?

If $H$ is a random function that takes large sized inputs, and produce a fixed sized output, then $T(H) = 1$ with exceedingly high probability.

Let us call then fixed size of the output of $H$ $n$ bits.

Then, for any pair of distinct messages $M, M'$, he have the probability of $H(M) = H(M')$ as $2^{-n}$ (as $H$ is assumed to be a random function).

Now, if we have $m > n$, and consider all possible $m$-bit pairs $M, M'$ that differ by one bit, we have $m2^{m-1}$ such pairs.

The probability that no such pair will collide is $(1 - 2^{-n})^{m2^{m-1}} \approx e^{-m 2^{m-n-1}}$, as $m2^{m-n-1}$ is large, this probability is tiny, and hence with high probability, there will be at least one collision that differs by a single bit.

As a collision must differ by at least one bit, we have $T(H) = 1$ (again, with high probability).

  Is this metric actually useful?

Doesn't appear to be; we don't have any way of computing $T(H)$ for any strong hash function, so it's not useful in a practical sense.  And, from a theoretical one, it's 1 for anything that acts like a random function, so I don't see any immediate use there.


Pedersen commitments fulfil two basic properties:

Perfectly hiding.

Since $b$ is uniformly random, $C=aG+bH$ can become any element of the group, independent from the randomness of $a$.

Computationally binding.

If I don't know the discrete logarithm relation between $G$ and $H$, I cannot cheat by opening $C$ to a different $a,b$ pair.

Additionally, Bulletproofs relies on Pedersen commitments being additively homomorphic: for another commitment $C'=a'G+b'H$, we have that $C+C'$ is a commitment to $a+a',b+b'$. To see this: $C+C' = (a+a')G+(b+b')H$. For this to work, we need $H$ to be a fixed point.

So, to sum up: $H$ shouldn't change because we require additive homomorphism, and $H$ does not need to change because it already provides perfect hiding!


Is the AES encryption scheme CPA secure?

You are mistaken about what an encryption scheme is. As CodeInChaos pointed out AES is a primitive and we assume that it is a preudo random permutation. That is an assumption since the way AES is built means that we won't be able to formally prove that it is one. With that PRP we try to build modes of encryption that might or might not be CPA-secure
I encourage you to read Mihir Bellare course notes and especially the chapters about Symmetric encryption and pseudo random functions http://cseweb.ucsd.edu/~mihir/cse207/


From your comment, I replace $p$ with a composite $n$.
The answer is no.

The problem is determining whether $f(x,y) = a x^2 + b y^2 \bmod{n}$ is one-way or not.
We want to find $(x',y')$ such that $f(x',y') = z$, given $a, b, n$ and $z = a x^2 + b y^2 \bmod{n}$.

Let us consdier $f'(x,y) = x^2 + h y^2 \bmod{n}$, where $h = b a^{-1} \bmod{n}$.
The problem is now finding $(x',y')$ satisfying $f'(x',y') = m$, given $m = z a^{-1} \bmod{n}$, $h = b a^{-1} \bmod{n}$, and $n$.

The problem is a basis of the Ong-Schnorr-Shamir signature (STOC 1984, CRYPTO 1984).
We already know that Pollad and Schnorr (1987) cryptanalyzed this scheme without factoring $n$.
The algorithm and example is available in a short note written by Jeffrey Shallit.


Correctly generating cryptographically secure pseudorandom numbers (in C)?

Short answer: Don't do this. The security proof for the One Time Pad requires the use of a True Random Bit Generator. The best you can find on a typical multipurpose system without dedicated hardware support for a TRBG is a Cryptographically Secure Random Bit Generator. The difference is that CSRBG is typically a deterministic algorithm that is seeded with good quality entropy the system is able to collect from various states and events. Because of this, using it for generating an OTP would in fact be no more secure than using a black box stream cipher for generating the key stream.

However, for the sake of argument, let's suppose you are implementing an OTP on a *nix based multipurpose system. What is the best you can hope for?

The key will have to be as long as the message and will have to contain random bits, each with full entropy. This means that the key will have to be stored externally after generation. There will be no way of regenerating the exact same key, except by storing it, transferring it over a secure channel and reloading it. If there is any way at all to regenerate the same key stream from a more compact seed or key (even in theory), it is by definition not an OTP.
/dev/urandom is no better than using a stream cipher. It is unblocking exactly because it is based on an algorithm that generates the output from a small seed. In principle, /dev/random should be implemented to return full entropy bits (which is why it is blocking - it always waits for enough entropy to be generated), but, firstly, there is no guarantee that it estimates the entropy of its input correctly, and, secondly, that it manages to extract that entropy in a completely unbiased manner. In fact, if the extraction is accomplished by e.g. hashing the entropy input, it is even highly unlikely that the extracted entropy will be completely unbiased. It will at best be good enough for all practical purposes, but that doesn't include using it for an OTP.


What curve and key length to use in ECDSA?

SafeCurves lists some ways to compare the security of elliptic curves. Their security criteria are split to "ECDLP security" and "ECC security". Failing the former basically means "there is no way to use this curve securely in general" while the latter "it is difficult to implement this curve securely".

None of the (few) BouncyCastle-supported curves that have been looked at on SafeCurves pass all the criteria. Some fail the "rigidity" ECDLP criteria, which means that there is no way to show that the parameters haven't been chosen so there is a backdoor. If you fear that e.g. NSA has backdoored ECC, you should avoid those curves.

The one that does best is brainpoolp384t1. If passes all the ECDLP criteria as well as having twist security. That means it is the easiest to correctly implement. The other Brainpool curve they've looked at, brainpoolp256t1, also passes all the ECDLP criteria and so can be implemented securely. Without knowing anything about BouncyCastle's implementation, it is impossible for me to know whether the former curve has an advantage or even if both are in fact broken.

Regarding key length, there are various recommendations by different parties. They mostly agree that 256 bits is enough through at least 2030. So either of the two Brainpool curves I mentioned above would fit the bill. 384 bits is enough for Top Secret according to NSA.

In short, then, brainpoolp384t1 would be a conservative choice, since you don't care about computational time or space usage. That's not to say any of the others are bad choices, or that some other curve (e.g. one of the 512-bit Brainpool curves) isn't even better.


How big are the primes used in modern cryptography?

For example, recent versions of OpenSSH typically use either

ECDSA with a curve size of 256, 384, or 521 bits, which requires a prime of the same size, give or take a couple bits, or
RSA with a key size of 1024, 2048, or 4096 bits, which requires two (distinct) primes of half the key size (e.g., a 2048-bit RSA key requires two distinct 1024-bit primes).

The reason for the difference in size is that RSA can be broken significantly faster than by brute force, which means it requires larger keys to achieve the same level of security.


Is there a formal definition of what a distinguisher is?

A distinguisher is an arbitrary algorithm. In fact, we do NOT want to formalize anything about the distinguisher (except that its output is a single bit, although we don't even really need to do this). In definitions, we require that no distinguisher should succeed with non-negligible probability. So, this should hold for any algorithm.

Of course, we do specify the complexity class of the distinguisher (either probabilistic polynomial-time or non-uniform polynomial-time).


How many public keys and private keys are needed for RSA?

So if Alice wants to send a message to Bob, a pair of public and private key is generated. But if Bob wants to send something back to Alice, must another pair of public and private key be generated?

Yes. Bob's public/private key pair, which protected the Alice-to-Bob transfer, is not usable to send data to Alice. However it's usable by anyone [assumed knowing Bob's public key $(n_b,e_b)$, trusting that to be matching Bob's private key $(n_b,d_b)$, and that Bob will not reveal that private key or use it unwisely] in order to send a confidential message to Bob.
Hence each user may need a single public/private key pair, yet the system allow anyone to send a confidential message to anyone.

If this is the case, does it mean that for RSA between $x$ parties, there must be in total $x(x-1)$ keys (public and private) generated?

No. As far as counting how many public/private key pairs there are, a good analogy is public phone number and private phone: we need as many phone numbers, and corresponding phones, as there are users.


How long does it take to decrypt an RSA/ECB encrypted message?

This is basically a substitution cipher where words are converted to numbers and then those numbers are substituted for new numbers as the encryption step.  You'd need to assume the language of plaintext, let's assume it's English.

Every time the word "the" occurs in the original text, it will cause the same number to be output to replace it.  Using some word frequency tables, it may be possible to find patterns that occur in the cyphertext that represent common patterns in English usage.

I guess I would have to look and see if there is a technical definition for decrypt, but even if you managed to puzzle out a possible sentence by analyzing the cyphertext, does that count as a decryption if you cannot reproduce your assumed input generating the same output.

Despite this being a very bad way to use RSA, it would still not make it any easier to officially decrypt the message.  The only way to do this with absolute certainty, is to factor the primes that make up the private key.  Depending on the size of the primes involved, this is a pretty intractable problem...

As the commentor above notes... if a word won't fit into the modulus, then keysize might be pretty small.  The longest word in English is something like 28 letters, so 28*8 is 224 bits.  There is no way that antidisestablishmentarianism was what the question had in mind, so lets make an assumption that any word longer than 8 characters is one that would need to be broken up...  That would be a modulus of 64 bits.  So now, the question is, how long would it take to factor a 64 bit number.  On modern computers, one assumes that could be handled in minutes.  ( https://stackoverflow.com/questions/4244319/how-to-find-all-the-prime-factors-in-a-unsigned-long-long-integer )


Authenticated encryption and file data integrity

the IVs of next blocks are going to be extracted from previous block ciphertext.

Here assuming chunks since CBC requires IV only once per message/chunk.

IV of CBC should be unpredictable, i.e random. It is not a good idea to extract from a known source. Use randomly generated per chunk.

  First option

Enables chaining, you should also add the IV with the ciphertext. You can store the last HMAC since you can generate from the beginning. As you said this prevents the detection of chunks that have errors during transmission. This can cause re-transmit all the chunks.

  Second option

There is an attack on this case. If the same key is used for different messages, and an attacker may replace one chunk with a chunk from an old message and you cannot notice this attack if there is no validation for the message.

Better solution

Use chaining and send the intermediate HMAC results, too. This is actually combing of first and second. It enables to detection of the errored chunks and prevents the replacing attack on the second option.


Is frequency analysis a viable attack on non-text data encoded by substitution?

If one can prove that a large amount of image and audio data doesn't exhibit a frequency patter, only then can we consider frequency analysis as a non-viable attack.

For a modified simple example, let us say each guitar chord is encoded as a byte of audio data. If you analyse about 70+ songs, you will see that 4 chords are the most frequently used (as suggested by Axis of Awesome). Hence, a frequency analysis attack on each byte can be done for such musical data.

On an ending note, we humans are not good at generating data with uniformly distributed frequencies. So intuitively I feel that frequency analysis would be a possible attack for any data set somehow generated by humans (say playing a musical instrument). Is it computationally efficient? That is another question. But a formal prove and analysis of large data is needed either against or for this intuition to answer your question in a precise manner.


Asymmetric keys (e.g. RSA) must be so much longer than symmetric keys (e.g. AES). Why?

Asymmetric algorithms

Asymmetric algorithms rely on mathematical structure. Keys for asymmetric algorithms typically have some kind of structure, as opposed to being uniformly random bit strings. This structure can be exploited to reduce the cost of breaking the system.

Additionally, with asymmetric cryptography, there is more information to work with; The public key has some known relation to the private key, and everyone has the public key. This is in addition to the usual information that you might have from what the system is used for, e.g. plaintext-ciphertext pairs or message-signature pairs.

Symmetric algorithms

Keys for symmetric algorithms do not have structure - They are simply a uniformly random block of bits.

Other than plaintext-ciphertext pairs, you typically do not have any more information about the key. The relation of the key to the bits of the plaintext/ciphertext are extremely complex with no regular or helpful structure to speak of.

Of course, you could have a cipher with a 256-bit key that is vulnerable to an attack that recovers the key in negligible time from a single ciphertext.

Key size

Key size isn't really what is relevant. What is important is the cost of the best attack to break the system.

With a strong symmetric algorithm, the best attack will be brute force guessing the key. So the size of the key more or less directly controls the cost of the best attack against the system.

The structure used by asymmetric algorithms typically results in the existence of attacks better than brute force guessing the key. So the key size has to be increased to compensate. This is visible in RSA as each prime $p, q$ is much much larger than the size required to prevent brute force guessing; Brute force guessing is not the best attack, so the keys are not scaled against the cost estimate that brute force would have.

Note

The above are generalizations that are only approximately true - it is possible to design symmetric algorithms that have structure - But those are not what people usually mean when they say "symmetric encryption".

Additionally, it's also possible to generate at random an AES key that happens to be the product of two somewhat sizable primes; But that won't tend to help cryptanalysis of AES much because that structure doesn't appear to be helpful.


Security estimation of LWE using "On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL"

I asked the question to the author directly.
To answer the first question, authors of NewHope estimate their security very conservatively, whereas the estimator takes many other things into account. Specifically, here is the answer I got from the author.

  Hi, Id' suggest to use their claimed security. To explain the differences:

  The estimate you quote is the paranoid estimate which differs in the leading constant in the exponent from BKZ.sieve
  New Hope conservatively assumes one SVP call suffices (we uses 8n which is less conservative)
  New Hope uses a different technique to amplify success of the dual attack. For the parameter sets considered here, their estimate means amplification is essentially free, whereas the estimator assumes amplification has a considerable costs.

For the second part, the clculation of $\alpha$ was wrong. It should be $\sigma\cdot\sqrt{2\cdot\pi}/q$


Sodium crypto_aead_aes256gcm_encrypt ciphertext length > plaintext length

The result you are getting is the cipher text (the encrypted data) plus 16 bytes of authentication data. The authentication data (mentioned directly below the ciphertext in the resource you cited) ensures that the ciphertext cannot be changed without the change being detected, and is the (most important) thing that distinguishes GCM from regular CTR-Mode.

The authentication data is the same length, no matter how much data you encrypt. So, if you encrypt 1024 bytes, you will still only get 16 bytes of authentication data. This means that you will only have to plan for those extra 16 bytes once and can read / write all remaining data as usual, although it would probably be a good idea to check some open source projects using the same library and cryptography and see how they are doing it, just to be sure you're not making any mistakes (at least that's what I usually do).

Edit: Also note that implementation questions are better suited for Stackoverflow, as the Crypto Stackexchange mostly deals with the concepts and not the implementations of cryptography.


Decrypting two ciphertexts using the same key


Not if

a secure MAC is chosen (e.g., HMAC-SHA256, CBC-MAC)
the MAC is used correctly (e.g., not reusing a CBC-MAC key for encryption), and
the secret MAC key is unknown by the attacker

That's literally the entire point of a MAC.


(This answer assumes a proving system that supports general arithmetic constraints, e.g. R1CS, over a finite field $\mathbb{F}_p$. It can be adapted to other settings but that may be non-trivial.)
Consider that a comparison $0 \leq n < c$ in $\mathbb{F}_p$ has negation $c \leq n < p$. So a constraint system for $b = (0 \leq n < c)$ can be essentially
$\hspace{1em}b: \text{boolean}. \text{ if } b \text{ then assert } 0 \leq n < c. \text{ if not } b \text{ then assert } c \leq n < p$.
It might not be obvious how to make the assertions conditional on $b$ or on $\text{not } b$, but there's a trick for that. Let's say we're using the the approach in appendix A.3.2.2 of the Zcash protocol spec for the assertions, so that the numbers we're checking are actually given as a bit representations. Then, for a plain range check, there would need to be an additional constraint $n = \sum\limits_{i=0}^{k-1} 2^i n_i$.
Instead, pick two integers $x$ and $y$, with bit representations $x = \sum\limits_{i=0}^{k-1} 2^i x_i$ and $y = \sum\limits_{i=0}^{k'-1} 2^i y_i$. Unconditionally check that $0 \leq \langle x_{k-1} \cdots x_0 \rangle < c$ and $c \leq \langle y_{k'-1} \cdots y_0 \rangle < p$. Finally assert:

$\left(n - \sum\limits_{i=0}^{k-1} 2^i x_i\right) \times b = 0$
$\left(n - \sum\limits_{i=0}^{k'-1} 2^i y_i\right) \times (1-b) = 0$

The first constraint here asserts that either $b = 0$ or $n = x$, in other words (given that $b$ is constrained to be boolean) $(b = 1) \Rightarrow (n = x)$. The second asserts that either $b = 1$ or $n = y$, in other words $(b = 0) \Rightarrow (n = y)$. So we can infer that $(b = 1) \Rightarrow (0 \leq n < c)$ and $(b = 0) \Rightarrow (c \leq n < p)$, as required. One of $x$ and $y$ will not be constrained, so we just pick it to be something for which the corresponding range check passes.
Note that some care is required to implement the range checks correctly given that at least one of $k$ and $k'$ will be close to the length of $p$, but that's orthogonal to the main question you asked I think. For the method in appendix A.3.2.2 it should be fine, since that method supports bit representations of arbitrary length.
There's probably a way to optimize this further by not doing two full bit decompositions, but I'm not seeing it right now.


Modified ElGamal encryption (ElGamal encryption with messages in the exponent ) is implemented in a pairing friendly elliptic curve. Is it secure?

Yes! Good observation! Although note that the original Helios paper by Ben Adida does not mention such implementation details, i.e., on which curve to instantiate the ElGamal encryption scheme.
Your observation basically stems from the fact that the decisonal Diffie-Hellman (DDH) assumption does not hold on pairing-friendly curves. On the other hand, one needs to assume the DDH assumption for the semantic security of the applied ElGamal encryption scheme. Therefore, the choice of the ElGamal encryption scheme implicitly implies that one needs to choose a suitable group, where the DDH assumption holds. If a pairing-friendly curve is chosen, then DDH does not hold, hence also the semantic security of the ElGamal encryption scheme is lost.


Does it mean that a binary keyfile of more than 64 random bytes (each having 8 bits of entropy?) is useless with PBKDF2 and a hash of 512 bits like SHA-512? The cost of testing all the hashes directly being cheaper than testing all the keyfiles.

Yes, it does. After 128 to about 256 bits security the amount of security provided by the bits alone doesn't make sense anymore (impossible is impossible).

  Does it also mean that reducing the iteration time to 1 millisecond (or just to 1 iteration if it's even possible?) for such a keyfile doesn't affect the security?

Yes, if the input does indeed have that much entropy (and is therefore not really a usable password or passphrase), then you might as well perform one operation per ms. Or much faster.

  And finally does it mean that using PBKDF2 with such a big keyfile, by reducing its size to just 512 bits, actually lower the security of a LUKS header?

No, that's unlikely. The amount of information lost by performing many, many operations is still minimal, so you will probably maintain the security of the underlying HMAC.

Note that security proofs like salts. Removing the salt entirely may make the calculation - at least theoretically - less secure. So it is probably best to replace the password hash with e.g. HKDF, a key based key derivation function that optionally takes a salt.


Cheating in a commitment scheme based on discrete log

Assuming that Alice verifies that:

$p = 2q + 1$ with $p, q$ prime
$g, g'$ are generators of order $q$

then Bob cannot cheat.

First note that $g$ and $g'$ generate the same subgroup, such that $g' = g^\alpha$ for some integer $\alpha$. Given a signature value $s = g^t g'^r = g^{t + \alpha r}$, there are $q$ possible messages $t' \bmod q$, and for every $t'$ there exists a unique value $r' \bmod q$ such that

$$r' \equiv \frac{t - t' + \alpha r}{\alpha} \pmod q$$

and:

$$g^tg'^r \equiv g^{t'}g'^{r'} \pmod p$$

Without further knowledge of $t$ or $r$, every pair $(t', r')$ that satisfies the signature is equally likely. So if Bob only knows $(p, q, g, g', s)$, he cannot deduce any information from the signature.

Note that if Alice knows $\alpha$, she can cheat by calculating $r'$ for any message $t'$ and revealing $(t', r')$ instead of $(t, r)$.


Is it possible to reduce the tail's file of accumulators for large data set

I've read a little about this area years ago. The naive example of an accumulator is simply multiplying primes together into the accumulator, which can then be checked for their presence simply by division. This obviously results in persistent growth of the accumulator.

I looked for an accumulator that addressed the endless growth issue, but I was never able to find one. However, I was more concerned about the increasing storage capacity required. It seems unlikely to me that one could exist, for they store information after all. It would be magical if it could continuously store information without growing in size.

However, as far as time complexity is concerned, it may be a different matter. The name of what you want would be something like "constant time cryptographic accumulator." For example, a bloom filter allows -- at increasing risk of false positives, but never with false negatives -- for O(1) membership querying on a set of recorded values, which means that time to (probabilistically) determine membership or (with certainty) a lack thereof doesn't grow with the number of elements added.

I would probably look for an accumulator built on a bloom filter if I were worried about time to query and could accept a small risk of false positives.


How is pre-image resistance defined, formally?

$\newcommand{\xs}{\xleftarrow\$}\newcommand{\mc}{\mathcal}$
There is a paper from 2004 (last revised 2009) by Rogaway and Shrimpton "Cryptographic Hash-Function Basics: Definitions, Implications and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance" which talks about this very topic (among others). I shall use it as the primary reference of this answer.

In the paper, there are three definitions given for first pre-image resistance. One which is separate from the others, one somewhat weaker and a strong one (to which quite a few other properties also reduce to). So we shall go through them in order.

Before we can start though, we need to take a moment to acustom to the fact that any hash function is written as $H_K(M)$ from here on, i.e. that the hash functions take a "key" as well. This is done to be able to model them as random functions and in practice this "key" can be assumed to be fixed and e.g. represent the initial internal chaining value of the hash function or a salt-like input to the hash. So from here on, let our hash function be $H:\mathcal K\times \mathcal M\to\mathcal Y$ and let $m$ be an integer such that $\{0,1\}^m\subseteq\mathcal M$, i.e. pick a length $m$ of bit strings that is a valid input length to the hash function. This set is useful because it allows us to reason about a finite subset of the potentially infinitely large hash input and we can make any choice of $m$ to our liking to model a particular string length.

Also all the definitions will talk about advantages for some adversary and some auxilliary parameters. Usually you want to bound this advantage to be negligble (in some security parameter, e.g. the digest length or the input entropy) for all adversaries that run in polynomial cost (i.e. efficiently and don't just enumerate the hash) and for all auxiliary parameters.

Definition 1: everywhere Preimage resistance (ePre)

$$\mathrm{Adv}^{\text{ePre}}_H(A)=\max_{Y\in\mc Y}\{\Pr[K\xs\mc K;M\xs A(K):H_K(M)=Y]\}$$

So what does this definition say? First, iterate over all possible output values $Y$. Next pick a hash function uniformly the selection. Then ask the attacker to come up with a value given the function selection. The attacker "wins" for the given $Y$ value if they actually found a pre-image. Now take the advantage of the attacker to be the maximum over all possible choices of $Y$.

Now this definition essentially says that it should be hard for an attacker to come up with a pre-image for any output value, given that they had no a-priori knowledge of the concrete (secure) variation of the hash.

It may appear that this definition isn't all that useful in practice, because an attacker may just always guess the empty string, but as the range point is fixed first and then the hash is selected uniformly at random, there's a $1/|\mc K|$ probability of being right with the guess, which is negligible. Thanks to Maeher for pointing this error out in a previous version of this answer.

Definition 2: always Preimage resistance (aPre)

$$\mathrm{Adv}_H^{\text{aPre}[m]}(A)=\max_{K\in \mc K}\{\Pr[M\xs\{0,1\}^m;Y\gets H_K(M);M'\xs A(Y):H_K(M')=Y]\}$$

What does this mean? Well, first it asks to iterate over all possible hash selections and fix one, e.g. the concrete instance. Now pick a message uniformly at random. Hash it using the hash instance. Hand the result to the adversary and ask them to come up with a value. If this value is actually a pre-image of the value given hash function then the adversary won.

Now practically speaking it appears that this definition is the one most closely modeling actual hash functions, because you fix the selection of the function and then ask the adversay to find a pre-image for a randomly chosen message.

Definition 3: Preimage resistance (Pre)

$$\mathrm{Adv}_H^{\text{Pre}[m]}(A)=\Pr[K\xs\mc K;M\xs\mc \{0,1\}^m;Y\gets H_K(M);M'\xs A(K,Y):H_K(M')=Y]$$

So what does this mean? Well it first says that you should pick an instance of the hash function uniformly at random. Then we pick a message uniformly at random from the set of bit strings of length $m$. Next we compute the challenge output value $Y$ using the previously determined message and function selection. Finally we give the adversary, ie the attacker both our function selection and the output value and ask it to come up with a value. If that value is indeed a first-preimage then the attacker "won". The advantage an attacker has now is the probability over the choice of the function selection and the value selection that they can come up with a valid pre-image.


How to convert roots of Weber polynomial to Hilbert class polynomial over modulo prime?

Let $j_w$ be the root of Weber polynomial $W_D(X)$ over $F_p$, then the root $(j_h)$ of Hilbert polynomial $H_D(X)$ over $F_p$ is given by

$$j_h=\frac{{(j_w^{24}-16)}^3}{{j_w}^{24}}$$


Ethereum RLPx protocol for inter-node communication - flaws in the encryption

Firstly, CTR mode. This is a stream mode that allows a block cipher (AES here) to work as a stream cipher.

Given $(k,IV)$ where $k$ is a random encryption key and $IV$ is an  initialization vector, CTR mode works in this way:

For the $i$th message $m_i$ (less than the block size):

To encrypt: compute $c_i=E_{k}(IV||i)\oplus m_i$;

To decrypt: compute $m_i=E_{k}(IV||i)\oplus c_i$;

Now the two streams use the same key and IV, so if the plaintext of $m_i$ in one stream is known by an attacker (e.g. this is a fixed field like a header or something), the attacker can recover the plaintext $m_i'$ in the other stream.

Stream 1: $c_i=E_{k}(IV||i)\oplus m_i$;

I know $m_i$, so I can recover the key stream for this block:

$E_{k}(IV||i)\oplus m_i\oplus m_i=E_{k}(IV||i)$

Then given the ciphertext $c_i' =E_{k}(IV||i)\oplus m_i'$ in the other stream, I can recover $m_i'$ because the keystream used in encryption is the same:

$E_{k}(IV||i)\oplus m_i'\oplus E_{k}(IV||i)=m_i'$


What happens to the entropy of a password when you hash it?

Still 30 bits.

A hash function does not add entropy. It could change the entropy rate though. For example if you had 30 bits of entropy in a 64 bit password and hashed it to a 128 bit digest, the rate has gone down ($\frac{30}{64}\approx 0.47$, but $\frac{30}{128}\approx 0.23$). On the other hand, if the password is 500 bits, the entropy rate goes up.

One way to see this would be to look at all the possible values that the password could be. That would be $2^{30}$ since any other character (or bits) are assumed to be known to the attacker (otherwise they would add entropy, right?). Those $2^{30}$ values would be fed into the hash function and result in $2^{30}$ different digests. So there are the same number of passwords as digests. No added entropy.


How can I change the length of PRF output?

I don't understand why you are talking about a 1-1 property; a pseudorandom function is not 1-1. As such, you can always just truncate in order to reduce the output size, and you can just truncate by taking the first $t$ bits that you want (you don't need to apply any other function). In order to extend, if $\ell$ is long enough to be the length of a seed in a pseudorandom generator, then you can apply the PRG to the output of the PRF to get a longer output.

If you really are talking about a 1-1 function, then you want to change the output length of a pseudorandom permutation. This is much more difficult, and can be done. A place to look is at the whole body of work on "format preserving encryption", which is problematic in name (it's deterministic so not secure encryption). However, what they really do is construct permutations over domains of arbitrary size.


Should I remove these use cases of MD5/SHA1 from my program?

Do you know the article If You’re Typing the Letters A-E-S Into Your Code You’re Doing It Wrong? This is basically the same, but with a focus on hashes.

There is a quite important misconception in your system:

you stated "One of its design goals was high security."
and then you start implementing your selfmade algorithms, even stating: "same key is used for enc and hmac; yes i know it is considered bad practice, but not really serious so far"

So, what is your goal here? Actual high security, in a real application? Here a few pointers, if that is actually the goal:

You should probably start by throwing out all those parts, which you designed yourself, and start utilizing proper crypto libraries and the correct primitives. E.g. key derivation functions exist for a reason.
Randomness (which you call entropy) is nothing to be taken lightly. Just because you implemented a system, you can't figure out how to break yourself, doesn't mean it is secure. Use a cryptographically secure random number generator and be done with it.
Key management is actually a quite critical topic, which is overlooked quite often. E.g. depending on your application, it can be bad if the keys are stored in the same location as user data, etc. If you can utilize a crypto library to handle the key management, all the better.

Your own suggestion of replacing MD5 and SHA-1 with a truncated version of SHA-256 would be a step in the correction direction (better without truncation), as it would be a lie to call anything based on MD5 and SHA-1 highly secure. However, this is just a minor step, and your actual problems go way deeper than that.


Why does consecutive permutations or consecutive substitutions not enhance security?

The reason two permutations in a row don't increase security is that there is always a third permutation that's equivalent to performing the two permutations in a row. For instance, suppose we have 5 elements, and the following two permutations:
$$\begin{align}
\sigma_1 &: 12345\to34251 \\
\sigma_2 &: 12345\to43512
\end{align}$$

Then if we apply $\sigma_1$ followed by $\sigma_2$, we send $1$ to $5$ by $\sigma_1$ and then to $3$ by $\sigma_2$; if we work out all of the 5 elements, we get
$$\sigma_2\circ\sigma_1 :12345\to52134$$

This is just another permutation (using more common cycle notation, $\sigma_1=(13245)$, and $\sigma_2=(14)(235)$, so $\sigma_2\circ\sigma_1 =(1543)(2)$). As you can see, composing the two permutations just popped out a third permutation; from an attacker's point of view, the fact that we did two permutations is irrelevant, because he can treat it as just one permutation.

With substitutions, it's similar: composing two substitutions gives a third (single) substitution, so there's no difference from an attackers point of view.


When you connect to a secure site the certificate validation happens. Certificate validation failure can happen when:

Fields CN or SAN dont't match the site's domains. That means that the certificate was issued for a different domain.
Invalid digital signature. Certificate has been altered.
Unknown certificate issuer, thus unknown intermediate CA or root CA.
Other common errors such expiration, revocation etc

Notice that an error here will warn the end-user via the browser. So the end-user has the power to trust a forged certificate if possible.

Now, in the case that you suggest, if the browser skips the root CA validation, it will only validate the digital signature in the certificate chain validation process, so it stops when reaching the CA Root. This means that the end-user will only validate digital signatures according to the certificate's Issuer public key until you hit the root CA, then process stops here without checking the key ring/trusted anchors.

This has happened in some crypto libraries among non-browser applications allowing an attacker to MITM a TLS session with forged certificates. Take a look at https://www.cs.utexas.edu/~shmat/shmat_ccs12.pdf


Generally you would use encrypt-then-MAC before encoding. There is no need to process the expanded ciphertext before encoding, and you may be able to send the
message both in binary and ASCII-armored with base 64.

Note that you would have to base 64 encode the authentication tag (the HMAC output) anyway if you would choose encrypt-then-encode-then-MAC, it would be encrypt-then-encode-then-MAC-then-encode.

Choosing the encrypt-then-MAC-then-encode does require you to:

Establish where the tag is situated:

Generally this is performed by just appending the tag and then count 32 bytes backwards (assuming the entire 256 bit output is used for the MAC, the default) or to include a length encoding for the ciphertext. However, a full ASN.1 structure could also be defined to create a so called container format.

Make sure that your base 64 decoder is not vulnerable against attack:

Because the base 64 decoding will now happen before the message is authenticated (but this is also the case if the tag is base 64 encoded separately, so yeah, make sure your base 64 codec is secure).

If you decide on using a container format (CMS or your own container format) then please note that attacking the format may expose security issues before the authentication can be verified. Windows famously had such vulnerabilities before user authentication took place. But many crypto related libraries such as OpenSSL and NSS have suffered similar issues.

EDIT: On Jason

You've specified JSON as message format. That's fine, but please note that JSON doesn't have an explicit way to encode binary values. Therefore you would have yourself to define the exact encoding of the binary message in payload, e.g. base 64 as defined here. Otherwise you may run into interop issues (base64url, padding or no padding, line breaks or no line breaks at specific locations, etc.

Furthermore, HMAC takes binary data as input. So that would mean that you'd have to specify the character encoding as well, at least for calculation of the authentication tag. JSON defaults to UTF-8 (which is compatible with ASCII for base 64 encoded values) but it also allows UTF-16 and UTF-32. Note that the encoding of the JSON and the encoding for the HMAC input could differ.

Because of these kind of issues, it is infinitely easier to just calculate the value over the binary value. You don't want to end up with the XML-digsig standard. Of course you'd still have to define the character set for the JSON message and base 64 encoding for the values within it, but at least a single bit wrong won't break your implementation.


Attack RSA with very big module ($n$) and very small $e$ (7)

I found the problem: my implementation was incorrect. It was indeed a vulnerability where it happens that $m^e \mod n = m^e$. Below there is a Python implementation used to calculate it correctly (the value of $n$ and $c$ is redacted for privacy reasons).

from decimal import *

n = {redacted}
c = {redacted}
e = 7

# https://docs.python.org/3/library/decimal.html
c = Decimal(c)
e = Decimal(e)

getcontext().prec = 500 # Set a big enough precision
root = pow(c, 1/e) # Calculate c^(1/e) = m^(e * 1/e) = m
print(root)

# Decode with no padding
m = hex(int(root))[2:-1] # Number to hex
m = ''.join(chr(int(m[i:i+2], 16)) for i in range(0, len(m), 2)) # Hex to Ascii
print(m)


Has Burdges and De Feo's concept of Delayed Encryption ever been implemented?

There is PoC code for the De Feo-Masson-Petit-Sanso VDF here: https://github.com/isogenies-vdf/isogenies-vdf-sage. It's easily adapted to Delay Encryption.


The hint as stated in the question is that the missing public exponent $n_5$ was constructed "poorly". But it could be that some other public exponents $n_s$ were constructed similarly, and this could reveal what "poorly" is. I'd check if some pattern emerges from

the seven other $n_s$
the five possibly different $n'_s=n_s\bmod\Gamma(R_s)$ for $s$ such that, further, $R_s$ is of known factorization as $P_s^\,Q_s$ so that we can compute the quantities $\Gamma(R_s)=\operatorname{lcm}(P_s-1,P_s+1,Q_s-1,Q_s+1)$
the five $m_s={n_s}^{-1}\bmod\Gamma(R_s)$ for such $s$.

If nothing comes out of it, we can try to decrypt with guesses of $n_5$ and see if the plaintext's characteristics match those of the other plaintexts (e.g. range, padding, being composed in a certain alphabet/language..). Reasonable guesses could be:

the seven other other known $n_s$
the know $n'_s$ if different
the few smallest positive $n$ that are coprime with $\Gamma(R_5)$
$n=m^{-1}\bmod\Gamma(R_s)$ for the few smallest positive $m$ that are coprime with $\Gamma(R_5)$. This simplifies into raising the ciphertext to increasingly large powers $m$, and further speedups are possible for that by precomputing the ciphertext to small even powers.

I do not see that we could mount a discrete logarithm attack as considered in the end of the question, for lack of anything suggesting known plaintext.


Signature Scheme with proof of data possession

If the document is short enough, then its ISO/IEC 9796-2 signature proves data possession, for a simple reason: in so-called total recovery mode, signature verification recovers the document as a byproduct.

ISO/IEC 9796-2 is an RSA or Rabin signature scheme, also requiring a hash. Depending on options, the "recoverable" message (that is, embedded in the signature) can be up to about $n-h-16$ bits, for $n$-bit public modulus and $h$-bit hash. For example, with 4096-bit RSA and SHA-256, the message can be up to 478-octet, embedded in a 512-octet signature.

ISO/IEC 9796-2 mode 1 is in wide use in Smart Cards. However, beware that it has a near-practical weakness allowing forgery from the signature of chosen messages. ISO/IEC 9796-2 mode 3 is functionally compatible with mode 1, and cures that. Both are deterministic, and maximize the size of the embedded message. ISO/IEC 9796-2 mode 2 is randomized, like RSASSA-PSS, which allows a stronger security argument, at the expense of reducing maximum message size for total recovery.

Independently: for any signature scheme with appendix signing a hash, including RSASSA-PSS and (EC)DSA, changing $\mathcal S_\text{priv}(\operatorname H(M))$ to $$\mathcal S_\text{priv}(\operatorname H(M))\|\mathcal S_\text{priv}(\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M))$$proves possession of $M$ as well as a static signature can do. That has the advantage of working with large messages. This is not standardized, but is a straightforward combination of standardized things.

Addition per comment: this is out of my head. However, the security argument (not proof) is simple:

$\operatorname{HMAC-H}$ is a standard Message Authentication Code construction from a hash.
A standard single-pass interactive proof of data possession is using $\operatorname{MAC}(R,M)$ where $R$ is a random challenge used as key of the MAC.
Signing that gives insurance that the signer is involved.
Replacing $R$ with the signature of the hash makes it non-interactive and invoking the signer before the HMAC could be computed, yet verifiable.

Still, a dishonest signer can offload all hashing to a third party, but that seems inevitable. And an imprudent signer hashing-and-signing any message can be abused into signing a proof of possession of something s/he did not keep (because HMAC's result is a hash).

Note: I chose this, at the price of requiring two signatures, rather than
$$\mathcal S_\text{priv}(\operatorname H(M))\|\operatorname{HMAC-H}(\mathcal S_\text{priv}(\operatorname H(M)),M)$$
because:

The security argument of the former is more straightforward.
The later succumbs if $H$ turns out not to be collision-resistant: an attacker could find $M$ and $M'$ with $H(M)=H(M')$, give $M'$ to signer, obtain $\mathcal S_\text{priv}(\operatorname H(M'))$ as part of proof of possession of $M'$ by honest signer, and turn that into a (different) forged proof of possession of $M$, when the honest signer never knew that $M$.
Involving the signer at beginning and end of preparation of the proof of possession arguably makes repudiation harder.


Since he isn't yet authenticated, how can I trust those who ask me for this salt? Because if I gave it to anyone who asks for it, it wouldn't make sense to use it.

That's where you went wrong. Salts are public: their purpose is to be unique per derived key, not to be secret. The security analysis of the KDF must assume that any salt used is public, so publishing them to anyone who asks is safe. That's one of the defining properties of a salt, as opposed to a "pepper". Peppers tend to provide no benefit that can't be provided by increasing the cost parameters, and complicate storage, so they're not used much.


Is AES without T-Tables nor S-Box resistant to side-channel?

Is an implementation without any lookup tables resistant to side-channel ?

That's only answerable by no unless it is added some limitation to the attack capabilities of adversaries. No implementation of cryptography involving a secret is resistant to sufficiently advanced side channel-attack. What was resistant a decade ago is no longer now, that's been true for the >3 decades I watched that game (I believe before that), and history will repeat itself, I guess.
Specifically, I'm ready to bet that the first applications to cryptanalysis of the advanced technologies currently developed in quantum computing will be sensitive/fast sensors for side channel-attacks then carried with classical computers.

Secret-dependent if statements, loops and mathematical operations like multiplications may not be constant time, can they make a side-channel attack possible ?

Yes, they have the potential to create a side-channel by timing. But for the AES block cipher, once lookup tables are removed or made constant-time, timing side channels are easily avoided (just don't explicitly test a data or key bit). Other side channels (probing, power analysis, electromagnetic emission), and fault attacks (which are not always classified as side channels, but stand in the same league) are the difficult ones.

Is bitsliced the only solution for a device without AES-NI ?

No. There are security-evaluated AES hardware and even software implementations that do not use bitslicing. Their internal design is typically secret (well-guarded from me, at least), and even their API is under NDA. See this marketing material from a company licensing IP in that field.
And if we restrict to side channels by timing, it is possible to remove theses in software-only AES and keep lookup tables. Fast, simple, secure, portable: pick one, perhaps two.

Can an attack (by side-channel) on an (AES software) implementation without any precomputed tables nor any test on key or data but without any additional security like bitslicing be performed over the network in practice with current technology ?

It depends on what's meant by "attack" and "over the network".

No, for attacks aimed at recovering the AES key being used based on timing measurements of network packets. The precautions stated have fully deprived the adversary of information thru that side-channel. It is even doubtful that we really need the "without any precomputed tables" part of the statement for anything else than a simple thus strong argument.
Yes, otherwise:

Software often ends up using the deciphered data in ways that leak information about that data (not the key under use) thru a timing side channel exploitable by remote timing of network packets. Padding oracle attacks are one class of such attacks. They can reveal a key under transfer.
Exploitation of bugs (buffer overflow…) and miss-configuration in the software using the AES implementation under attack is a very real threat.
When an adversary accessing the machine "over the network" has or gains the ability to run facilitating code on the machine under attack, we can't rule out a side-channel attack: there's a steady flow of new or slightly different architectural CPU side-channels discovered on CPUs which promised process isolation, even recent ones. And there are even more attacks on OSes and virtualization environments with the net effect of breaching process isolation.

The most secure ways to rule out key leak "over the network" involve not manipulating the key with a general-purpose modern computer¹. Like, keeping keys in a dedicated security device (Smart Card, TPM, HSM). That can give strong insurance against key leak, but not key abuse: it remains possible that an adversary remotely deciphers data enciphered with the key.

¹ I nearly wrote a networked general-purpose modern computer, then went back: there are reports of side-channel attacks that could be carried using a nearby compromised networked computer.


Because XTS already solves the problem ESSIV is designed to solve.

Disk encryption modes are meant for retaining some security despite the lack of space for a unique IV. They do this by making use of the sector number so that at least multiple copies of the same data stored in different places end up looking different. That is not sufficient for good general purpose security, but the best that can be done transparently in full disk encryption.

With XTS the sector number is used as a tweak so that every sector is encrypted with an effectively independent FPE transformation. With ESSIV each sector is encrypted with an effectively independent key. Using both would have no additional advantage: different sectors are already encrypted differently with XTS alone and using both would not change the fact that on rewriting the single sector is encrypted deterministically.

Another, more heuristic way to look at it is that using the information (sector number) again does not "add entropy".


Reverse Java seed using outputs generated from nextInt(6)+1

what is the purpose of this line of code?
while (bits - val + (n - 1) < 0);

From a syntactic perspective, it ends the do opened above. From a functional perspective, it makes the pseudo-random number generated uniform on the specified interval. I'll focus on the later aspect.
Assume n was $3\cdot2^{29}\,$ (that is 3<<29) rather than $6$. After the statement bits = next(31); this quantity is uniformly random in $[0,2^{31})$. Therefore val = bits % n; is

bits with probability 75%; and then uniform on $[0,3\cdot2^{29})$
or bits-(3<<29) with probability 25%; and then uniform on $[0,2^{29})$

It follows that before the while, val is in $[0,2^{29})$ with probability 50%, in $[2^{29},3\cdot2^{29})$ with probability 50%. The second interval is twice as large as the first, and we see that val is very far from uniform on the whole interval $[0,3\cdot2^{29})\ $!
The while repeats the loop when in the problematic second bullet, and thus makes the outcome uniform on the full interval $[0,3\cdot2^{29})$.

Alternate explanation with small numbers
Imagine that, starting from $b=0$, four times: we double $b$, then add $1$ to $b$ if we get a tail from a fair coin throw. The outcome is $b$ a nonnegative integer less than $2^4=16$, and each of these $16$ integers is equally likely. That is, the outcome is a discrete uniform random number $b$ in $[0,16)$.
From this we want a uniform random number $v$ in $[0,6)\,$ just like nextInt(6) is tasked to do. Problem is, if we use a fixed assignment of values of $b$ from $[0,16)$ to values of $v$ in $[0,6)$, the outcome can't be uniform. The most even we can get is that $4$ values of $v$ have probability $3/16$, and the $2$ other $2/16$. Think of separating $16$ mints (the $b$) into $6$ persons (the $v$).
A simple solution to that is: when $b$ is in $[0,6)$, that's our $v$. When $b$ is in $[6,12)\,$, our $v$ is $b-6$. Otherwise, we try again, generating another $b$ using coin throws. That's what the code does in it's do … while loop, only with $2^{31}$ using next(31) where our analogy uses $2^4$ and coin throws; using bits for $b$, and val for $v$.

Off-topic: what's up with bits - val + (n - 1) < 0 ?
One wonders how while (bits - val + (n - 1) < 0); manages to do what's described above. bits is in range [0, 0x7FFFFFFF], n is 6, val is bits % n, thus val < bits holds and bits - val is non-negative. But it does not follow that bits - val + (n - 1) is non-negative, because the operations are carried per two's-complement arithmetic over 32-bit.
That's how int works in Java, many other computer languages, and most modern computer hardware when manipulating signed integers as a 32-bit quantities. If the int quantities u and v represent the integers $u$ and $v$, these integers are both in range $[-2^{31},2^{31}-1]$, then u + v is an int quantity representing an integer $w$ in range $[-2^{31},2^{31}-1]$ with $u+v\equiv w\bmod2^{32}$, that is by definition $u+v-w$ a multiple of $2^{32}$, and depending on values of $(u,v)$ that multiple can be $0$, $2^{32}$, or $-2^{32}$. In the end, $w$ is the integer $((u+v+2^{31})\bmod2^{32})-2^{31}$. That arithmetic is commutative, associative, has neutral zero, and every element has an opposite. A caveat: $-2^{31}$, that is -0x80000000, shares with zero the property of being it's own opposite.
So for example if bits was $2^{31}-2$, val is $0$, bits - val is $2^{31}-2$, bits - val + (n - 1) is $((2^{31}-2+(6-1)+2^{31})\bmod2^{32})-2^{31}$, that is $((2^{32}+3)\bmod2^{32})-2^{31}=3-2^{31}$, and that's negative.
For those that just want to move along: the condition bits - val + (n - 1) < 0 is logically equivalent to bits - val >= ((long)1<<31) + 1 - n (with no overflow and only non-negative quantities, thanks long being 64-bit).
It should now be apparent that bits - val + (n - 1) < 0 holds when bit is at the top of its interval [0, 0x7FFFFFFF]. It is left as an exercise to the reader to show that the rest of the interval contains a multiple of n integers, thus all the n values of val on exit of the loop are exactly as likely, under the assumption that all values of bits are.

How does one reverse engineer

That's already done. The question has reverse-engineered the algorithm, and even more than this: simplified the code from what it is in a recent Java environment by removing the thread-safety stuff (or traveling back in time to get the source before that was added); and thought about removing the part of the code that is demonstrably unreachable in the circumstance.

and find the seed from a set of numbers generated from this procedure?

Next step towards that goes: compute the probability that the condition in the while statement is true when n is $6$, and decide what can be done about this case.
Then proceed. There's several paths to resolution:

Brute force, trying all $2^{48}$ initial state values. This is feasible, but inelegant and resource-hungry.
Reducing the above search space by a factor of $6$ by exploiting the first result available.
Using that $6$ is even to get 18 bits of the seed out of 48 (with fair probability), then brute force the rest. That's relatively simple and educative. It's outlined in this answer of mine. Some combinations with the above tweaks work.
A that-could-well-work-but-I-didn't-bother-to-try approach using SAT solvers (in same answer).

Likely there are other approaches, but if there's anything readily applicable here or here, I missed it.
If stuck, state at what point at the bottom of the present question.


Can you identify the public key used to encrypt something?

An RSA ciphertext won't reveal who it is encrypted to, but it might reveal some information about who it isn't.

We'll assume that everyone has an RSA key of the same length (e.g. 2048 bits).  Now, a public key consists of a large modulus N (and an exponent, that's not important for this discussion); a ciphertext consists of a value C between 0 and N-1.

Suppose Alice has a public key $N_{alice}$ and Bob has a different public key $N_{bob}$.  If we were to encrypt a message with Alice's public key, that generates a value $C < N_{alice}$.  Now, if $N_{bob} < N_{alice}$, then it is possible that $C \ge N_{bob}$; if that happens, someone listening in can immediately deduce that $C$ was not encrypted with Bob's public key.

Now, this isn't an inherent problem with RSA; if Alice and Bob cooperated, they could generate keys $N_{alice} \approx N_{bob}$ (say, agree in the first 200 bits); this would make it quite improbable that an attacker would be able to rule out a particular public key,  This doesn't reduce the security of RSA, but it is not generally done.

As for DSA, well, DSA doesn't encrypt messages.  If we look at DL-based encryption systems (El Gamal, IES), we see that the ciphertext doesn't reveal the public key (assuming that the various public keys use similar parameters; for example, the same group).


Public-Key Deterministic Encryption : Why does not provide perfect security?

Deterministic encryption means that if the same plaintext is encrypted twice, it results in the same ciphertext. This is intrinsically a breach of security.

“Absolute security” is not a technical term — but deterministic encryption breaks many definitions of security, including perfect security. If two ciphertexts are identical, it reveals the fact that the plaintexts are identical — and identical plaintexts lead to identical ciphertexts.

This is particularly bad in the presence of an encryption oracle: if the attacker can submit plaintexts for encryption, then the attacker can verify guesses about the plaintext corresponding to a ciphertext.

This is why most encryption algorithms (for example RSA PKCS1 v1.5 with salt, RSA OAEP, block cipher modes for encryption or authenticated encryption such as CBC, CTR, OCB, CCM, EAX, GCM, …) include some form of unique input to the encryption of each message (typically random, though whether more than unicity is important depends on the mode): salt, counter or IV.


Condition on Vector Boolean Function to be Bijective

The condition is that:

$$g(0, x_2, x_3, ..., x_n) \ne g(1, x_2, x_3, ..., x_n)$$

for all $x_2, x_3, ..., x_n$

This can easily be derived from the condition that implies bijectivity of $f$; that is,  $f(x_1, x_2, ..., x_n) = f(y_1, y_2, ..., y_n)$ implies that $x_1 = y_1$, $x_2 = y_2$, ..., $x_n = y_n$


Using single EC cert/keying material to derive symmetric encryption key (for storage)?

You can use ECIES, though it's not widely implemented.


Disadvantage: You don't get the thrill of playing Russian roulette with a dumpster fire of an implementation ecosystem and underspecified protocol!

Disadvantage: You might accidentally reinvent JWT and repeat its errors anew if you're not careful.  (On the other hand, advantage: you might not.)


In general you should avoid changing the cipher for no particular reason. It is unlikely that simply increasing the number of rounds will significantly change the security of the cipher. Although attacks are generally against a limited number of rounds, the following is stated for Salsa20 (source: Wikipedia):

  As of 2015, there are no published attacks on Salsa20/12 or the full Salsa20/20; the best attack known[2] breaks 8 of the 12 or 20 rounds.

And this is with very high memory requirements, and only partially reducing the complexity (without any practical attacks even for the reduced round version).

If Salsa20 is broken it is likely an issue with the operations within a round, or something with regard to pre- or post-processing.

So you'd gain next to nothing while sacrificing performance and - probably more importantly - compatibility.

If you want better security you can use another stream cipher - or block cipher in stream mode - to XOR the ciphers together. You could also look at (ciphers with) hardware support to provide better protection of the key and possibly the algorithm (with regards to side channel attacks).


Can I apply "encrypt with public key and decrypt with private key concept" using ECC certificate?

You are right that (EC)IES essentially consists of a Diffie-Hellman key agreement and authenticated symmetric encryption, but the protocol flow is different. In particular, IES is a "one-shot" public-key encryption scheme: Assuming that Alice knows Bob's public key beforehand, she can encrypt a message for Bob "offline" without any interaction, just like with RSA.

In summary, ECIES consists of the following steps:

Assume Alice knows Bob's public key $Y=[y]P$.
Alice generates a random private key $x$ and computes $[x]Y$.
She derives a symmetric key $k$ from $[x]Y$.
Using some authenticated symmetric encryption algorithm, she encrypts her message using $k$ as the key, yielding a ciphertext $c$.
She transmits the pair $([x]P,c)$ to Bob.

Based on this, we can answer your questions:

1.
No, in IES the receiver (Bob) does not need Alice's long-term public key because she generates a fresh ephemeral key pair (whose public part is transmitted as part of the ciphertext) for each message. In fact, Alice does not even need to have a long-term key to be able to encrypt messages for Bob! This is in line with the general public key encryption setting: Everybody can encrypt, only Bob can decrypt.

2.: Yes, the encryption procedure for RSA is different from IES. But the protocol flow is not! Both are public-key encryption schemes.

3. No, according to 1.


Is it fair to say a PBKDF is a specialization of KDF?

Sure. A PBKDF is a KDF, just one that uses a password/passphrase as the entropy source.

OTOH, a KBKDF (key-based KDF, if you want to call it that) is also a specialization of a KDF. A different specialization, which is why it may not be a good idea to treat them as a single thing.

  Will a software interface that support the five parameters above be sufficient?

There are a couple of common parameters that are missing:

Many password hashing functions have a second cost parameter indicating how much memory will be used. (E.g. scrypt, most of those from the currently running Password Hashing Competition.)
Another relatively common parameter is a pepper. You can just include it as part of the salt if needed, but then the same is true for your context information parameter.

I also don't think your parameters, even with the above additions, are the best way to define such an interface.

For one, I don't think a salt should ever be left out, so I don't see why it should be optional.

For another, there is a significant difference in how a key derivation function is normally used, compared to how a password hash is used:

With a key derivation function, you are going to need a key of a certain size as output.
With a password hash it is useful to get an opaque return value that can be passed as the only additional parameter into a verification routine:

verify(password, combined_hash)

(Cf. Modular Crypt Format.)

This way the iteration count, salt, etc. is easily stored with the hash, and different hashed can have different parameters, allowing one to upgrade the strength with time as attackers' computational power increases.


why can't use only one way function to construct a PRG, and don't use the hard core predicate?

The first one is really simple, you already said it yourself:

  as i read , we can't just construct a PRG from just OWF , but we need to use the hard core predicate of the OWF, why is that?

I guess you're familiar with the formal statements, but informally speaking we have:

A function $f:\{0,1\}^* \rightarrow \{0,1\}^*$ is one-way, if we give the adversary $y = f(x)$ and the length $|x|$, and he has a negligible probability of finding $x'$, s.t. $f(x') = y$.
a PRG is a function $g:\{0,1\}^n \rightarrow \{0,1\}^m$, where the output is indisinguishable from $U^m$, denoting the uniform distribution over $m$ bits, and $m > n$

Now consider the following construction: $f'(x) = f(x)|1$, with $f$ being a OWF. Just concatenating a $1$ doesn't change much w.r.t. the security property of an OWF. And in fact, any adversary able to break $f(x)$ can easily be turned into an adversary for $f'(x)$ and vice versa. So $f'$ is a OWF iff $f$ is a OWF.

But it is quite obvious, that $f'$ is not a PRG, because the output of $f'$ can easily be distinguished from a uniform distribution, by just looking at the lowest ordered bit (always $1$ vs uniform).

But as you stated yourself: With a hardcore predicate, you can get a length extension. Maybe these lecture notes make it more clear how to achieve that (and why it's necessary). Informally speaking: A OWF does not need to be impossible to invert for all parts of its output - while a PRG needs to be indistinguishable from randomness over all its output.

  why constructing prg in the following way is wrong G(s) = f(s) assuming |f(s)| > |s|?

If we specify $f(x):\{0,1\}^n \rightarrow \{0,1\}^n$ a length preserving OWF, and use the construction above, we get $f':\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, which is also a OWF. This fulfills the length criteria of a PRG, but it is distinguishable. Being a OWF is not sufficient to be a PRG.

  f is a permutation function , if f gets a random x then is f(x) also random?

A permutation is a bijection from a set, e.g. $\{0,1\}^n$ into itself. This means, there are no collisions and every element has a single preimage. Thus, if we consider an input drawn uniformly at random from $\{0,1\}^n$, then the output is also uniformly distributed over $\{0,1\}^n$ - because the permutation has a 1-to-1 relationship between inputs and outputs. But that is also fullfilled for example by $p(x) = x + 1 \mod n$ over $\mathbb{Z}_n$, and I don't think that's what you meant. But this is entirely unrelated to the concept of one-way functions and PRGs.


Fermat's factorization method on weak RSA modulus

In general, it is not sizably easier to tell from an RSA modulus that Fermat factorization will succeeds, than it is to perform such factorization.

However here, it is visually easy to notice the long sequence of 00 and ff in the modulus. That translates into noticing that the modulus to factor is $2^{2048}+\mathtt{21a}_h\cdot2^{1024}-\mathtt{107bb}_h$, or equivalently $2^{2048}+538\cdot2^{1024}-67515$.

Per comment: the number is 257-byte, with the left 01:00:00:00:, thus just over $2^{2048}$. Cutting where the long ff:ff:ff: starts, the right fragment has 128 bytes, thus has a value just shy of $2^{1024}$, and the :00:00:00:02:19:on its left contributes for an additional $\mathtt{219}_h\cdot2^{1024}$, totaling near $\mathtt{21a}_h\cdot2^{1024}$. The correction to subtract is one more than the bitwise complement of the right fragment :ff:ff:ff:fe:f8:45.
In other words, the modulus is $2^{2048}+\left(\mathtt{0000000219}_h+1\right)\cdot2^{1024}-(\overline{\mathtt{fffffffef845}_h}+1)$.

That $2^{2048}+538\cdot2^{1024}-67515$ suggests to try if the modulus could be $(2^{1024}+a)(2^{1024}+b)$ for integers $a$ and $b$ of small absolute value, that is if the system $a+b=538\text{ and }a\cdot b=-67515$ has an integer solution. We can

Solve the second degree equation $x^2+538x-67515=0$ which roots will be $a$ and $b$, and check these are integers. We get roots are $-\dfrac{538}2\pm\sqrt{\left(\dfrac{538}2\right)^2+67515}$, which indeed are integers $643$ and $-105$, and that gives us the factorization as $(2^{1024}+643)(2^{1024}-105)$.
Or factor $67515=3\cdot5\cdot7\cdot643$, which invites to try $a=643$ and $b=-3\cdot5\cdot7=-105$, with indeed $a+b=538$.

Notice the above factorization method works only because the hex fragments in the middle and in the right of the modulus given have a highly specific property: $\left(\dfrac{\mathtt{0000000219}_h+1}2\right)^2+\overline{\mathtt{fffffffef845}_h}+1$ is the square of an integer. Otherwise that method leads nowhere, and it is likely Fermat fails too.

Fermat factorization works on the given moduli because it is of the form $(2^{1024}+a)(2^{1024}+b)$ with $a$ and $b$ small integers, thus the product of two close integers. Fermat works for many 2049-bit integers not of this form, but still only a negligibly tiny fraction of 2049-bit integers.


What is the difference between PIR and OT?

In general, PIR mainly guarantees that the server should not know which item is retrieved, as does OT. However, in contrast to PIR, OT also guarantees that the user should not learn information about other items.

----update based on Lindell's comment----

Another difference between PIR and OT is the requirement of sublinear communication cost for PIR. Note that PIR with linear communication is trivial and hence not interesting as the server can simply send the whole database to the user. However, this does not work for OT because sending the whole database reveals all other database items to the user.


The key derivation process you describe is reasonably secure in a technical sense, but not a good choice—it's not very flexible, it will raise auditors' eyebrows, and SHA3-512 is just not a good design.

Security if we model SHA3-512 as a uniform random function $H$:
Each of the 512 bytes of $H$ on distinct DH secrets is independently uniform random, so the string of 256 odd-position bytes is uniform random and the string of 256 even-position bytes is independently uniform random.  The probability of collision between the even-position bytes and the odd-position bytes is negligible, and in the event of no collision, the resulting keys are independent uniform random.

Why is it a bad choice?

It's not very flexible.
What happens when you want to derive another key?  You've used up all the bytes (or, most of them, anyway); you'll need to find a different mechanism for this purpose, and it'll be another ad hoc thing that the remaining reasons still apply to.  This fragility may hurt security: Will your successor who needs to extend the protocol make a decision that remains secure?
It will raise auditors' eyebrows.
This is not a standard construction for key derivation.  By adopting this, you make an auditor's job harder by forcing them do cryptographic reasoning like the paragraph above, which auditors would rather not do.  They don't want to think about the even-position and odd-position bytes of a SHA3-512 hash.  They'd rather spend their effort simply confirming that you're using a well-studied and well-understood construction without having to think about it, so they can move on to higher-level protocol issues that will actually be more important in assessing the security of your application.
SHA3-512 is just not a good design.
SHA3-512 pays extra for an unimaginably high security level that doesn't matter to you for two reasons:

Collision attacks are not relevant to your application, but SHA3-512 pays a premium for collision resistance.
For political reasons rather than technical reasons, SHA3-512 was overdesigned to meet a meaningless security target.

General advice aside: Ignore SHA3-256 and SHA3-512.  Use SHAKE128 (with sufficiently long outputs) for a 128-bit security level.  Use SHAKE256 only if you're a paranoid worrying about hedging against modest cryptanalytic advances, like for use with Ed448.

So what should you do instead?  Here are a couple options:

Use HKDF with your favorite hash function.  SHA-256 is a perfectly respectable choice.  If you insist on using SHA-3, you could use SHA3-256, but SHAKE128-256 would be faster for essentially same security—or you could just use SHAKE128 or KMAC128 directly, below.

HKDF comes in two stages, which some APIs weld together:

HKDF-Extract takes initial key material and a salt and hashes them into a master key.

The initial key material is a high-entropy but possibly nonuniform secret, like the outcome of a DH key agreement.
The salt is optional; if it is merely distinct for each user, then it serves to mitigate multi-target attacks.  For a DH key agreement that already achieves a 128-bit security level, like X25519, this is not necessary.  But it doesn't hurt.
The master key is a short secret bit string that is effectively uniform random.

\begin{equation*}
    k_{\mathrm{master}} = \operatorname{HKDF-Extract}(\mathit{dhsecret})
  \end{equation*}

You must never reuse the same initial key material.  (Actually, in practical terms, if you reuse it with distinct salts, you won't get into security trouble—but you will make the auditor's job harder which will make your life harder and hurt your user's confidence in your system.)
HKDF-Expand takes a master key and an info parameter that uniquely describes a purpose and derives a subkey from them.

The master key is what you got out of HKDF-Extract.  (Aside: It could also be from a password hash like Argon2 or PBKDF2, or any short uniform random secret key that you got from somewhere else and you just want to derive multiple subkeys from.)
The info parameter distinguishes the subkeys for different purposes: for each distinct info, there is an effectively independent uniform random subkey; it is as if you generated the subkey independently, but you can get it deterministically and reproducibly from the master key by passing in the same info.
The subkey is what you then use as an AES-256 key or whatever.

\begin{align*}
    k_{\mathrm{AES}} &= \operatorname{HKDF-Expand}_{k_{\mathrm{master}}}(\text{‘AES encryption key’}), \\
    k_{\mathrm{KMAC}} &= \operatorname{HKDF-Expand}_{k_{\mathrm{master}}}(\text{‘KMAC authentication key’}).
  \end{align*}

You must never reuse the same info parameter for two different purposes.  The auditor will want it to be easy to confirm that every purpose for which you derive a subkey has a distinct info parameter, so you should clearly document what each info parameter is used for, and if you ever programmatically format info parameters, make sure that you use a unique encoding of whatever data you put in them to ensure they will be unique.

Use KMAC128, or SHAKE128, directly.
For KMAC128, you can safely just feed in the DH secret as the KMAC128 key, and uniquely encode the salt and info parameters as the KMAC128 message.  Similarly, you could also just uniquely encode the DH secret, the salt, and the info parameters as the SHAKE128 message: $\operatorname{SHAKE128}(\text{32-byte DH secret} \mathbin\| \text{32-byte salt} \mathbin\| \text{‘AES key’})$.

This may be simpler for your application, and it doesn't hurt security.  As long as it's conceptually structured the same way as HKDF—never reuse a DH secret except with distinct info parameters—it should be straightforward for an auditor to follow.


Encryption & decryption in AES CBC mode - Which is faster?

I notice that AES-CBC encryption is faster than the description, is my result is correct?

It is plausible for a software-only implementation if single-threaded or if CPU time is cumulated across the multiple threads. For an implementation using AES instructions, the difference in speed can be barely noticeable or in either direction. For a competently made multi-threaded implementation with concurrently running threads and speed measured according to wall clock time elapsed, decryption of large amounts of data should be much faster than encryption.

Among reasons why AES CBC decryption can be slower than encryption (contrary to AES CTR which typically is nearly the same speed in both directions, since only IV generation differs)

AES CBC decryption involves the AES block cipher in decryption mode (when AES CTR does not), and in AES (contrary to DES) the design of the block cipher has reasons to make it slower in decryption mode:

The MixColumns step of encryption purposely uses a matrix with many coefficients at 1, when the inverse MixColumns used in decryption does not, thus requires more field operations. However that often makes no speed difference in hardware-assisted implementations.
The derivation of the AES round subkeys from the main key can be performed as the rounds are applied in encryption mode, but not in decryption mode, where the first subkey used is the last derived one. However that will make no difference for implementations that compute round subkeys only once, which is typical of software implementations optimized for many blocks.

Implementations of decryption that both decipher in place and process data blocks in the order used in encryption (rather than reverse) need to keep a copy of the previous ciphertext block in order to decipher the next, and that can add some time.
Sometime decryption is just not optimized as carefully as encryption is.

Among reasons why AES CBC decryption can be faster:

Decryption can be trivially parallelized on multiple CPUs, when encryption cannot (because the output of the previous block encryption needs to be known to prepare the input of the next block encryption). That leads to less wall clock time for decryption of multiple blocks in multi-threaded implementations when multiple CPUs or even simultaneous multithreading is available.
For the same reason, on architectures with high instruction latency, a single thread can interleave the decryption of multiple blocks from the same encrypted data stream and reach higher performance than for encryption (BearSSL uses that, as noted by SEJPM).
Decryption does not need to generate a random IV, when encryption does.


Basic explanation of Elliptic Curve Cryptography?

There are some widely used cryptographic algorithms which need a finite, cyclic group (a finite set of element with a composition law which fulfils a few characteristics), e.g. DSA or Diffie-Hellman. The group must have the following characteristics:

Group elements must be representable with relatively little memory.
The group size must be known and be a prime number (or a multiple of a known prime number) of appropriate size (at least 160 bits for the traditional security level of "80-bit security").
The group law must be easy to compute.
It shall be hard (i.e. computationally infeasible, up to at least the targeted security level) to solve discrete logarithm in the group.

DSA, DH, ElGamal... were primarily defined in the group of non-zero integers modulo a big prime p, with modular multiplication as group law. The characteristics we look for are reached as long as p is large enough, e.g. at least 1024 bits (that's the minimal size for discrete logarithm to be hard in such a group).

Elliptic curve are another kind of group, appropriate for group-based cryptographic algorithm. An elliptic curve is defined with:

A finite field, usually consisting in integers modulo some prime p (there are also other fields which can be used).
A curve equation, usually $y^2 = x^3 + ax +b$, where $a$ and $b$ are constant values from the finite field.

The curve is the set of pairs of values $(x, y)$ which match the equation, along with a conventional extra element called "the point at infinity". Since elliptic curves initially come from a graphical representations (when the field consists in the real numbers $\mathbb{R}$), the curve elements are called "points" and the two values $x$ and $y$ are their "coordinates".

Then we define a group law, called point addition and denoted with a "$+$" sign. The definition looks quite artifical, with all the business about tracing a line and computing the intersection of that line with the curve; but the bottom-line is that it has the characteristics required for a group law, and it is easily computable (there are several methods; as a rough approximation, it costs about 10 multiplications in the base field). The curve order (the number of points on the curve) is close to $p$ (the size of the finite field): the curve order is equal to $p+1-t$ for some integer $t$ such that $|t| \leq 2\sqrt{p}$.

Compared to the traditional multiplicative group modulo a big prime, elliptic curve variants of cryptographic algorithms have the following practical features:

They are small and fast. There is no known efficient discrete-logarithm solving algorithm for elliptic curves, beyond the generic algorithms which work on every group. So we get appropriate security as soon as $p$ is close to 160 bits. Computing the group law costs ten field operations, but on a field which is 6 times smaller; since multiplications in a finite field have quadratic cost, we end up with an appreciable speedup.
Creating a new curve is uneasy. Generating a new big prime is a matter of
a fraction of a second with a basic PC, but making a new curve is much more expensive (the hard part is figuring out the curve order). Since there is no security issue in using the same group for several distinct key pairs, it is customary, with elliptic curves, to rely on a handful of standard curves which have been created such that their order is appropriate (a big prime value or a multiple of a big enough prime value); see FIPS 186-3. The implementations are thus specialized and optimized for these particular curves, which again considerably speeds things up.
Elliptic curves can be used to factor integers. Lenstra's elliptic curve factorization method can find some factors in big integers with a devious use of elliptic curves. This is not the best known factorization algorithm, except when it comes to finding medium-sized factors in a big non-prime integer.
Some elliptic curves allow for pairings. A pairing is a bilinear operation which can link elements from two groups into elements of a third group. A pairing for cryptography requires all three groups to be "appropriate" (in particular with a hard-to-solve discrete logarithm). Pairings are an active research subject because they can be used to implement protocols with three participants (e.g. in electronic cash systems, with the buyer, the vendor and the bank, all mathematically involved in the system). The only known practical pairings for cryptography use some special elliptic curves.

Elliptic curves are usually said to be the next generation of cryptographic algorithms, in order to replace RSA. Performance of EC computations is the main interest of these algorithms, especially on small embedded systems such as smartcards (in particular Koblitz curves over binary fields); the biggest remaining issue is that public-key operations with group-based algorithms are a bit slow (RSA signature verification or asymmetric encryption, as opposed to signature generation and asymmetric decryption, respectively, is extremely fast, whereas analogous operations in the group-based algorithms are just fast). Also, involved mathematics are a bit harder than with RSA, and there have been patents, so implementers are a bit wary. Yet elliptic curves become more and more common.


Time efficiency of Bitcoin Multi-signature Vs. threshold signature

There are some possible advantages to threshold signing. First, it enables a more flexible setting where the key can be divided into $n$ parts and any subset of $t$ can be used to sign. Second, you can go from holding a single key in one place to distributing it and back without making any changes. Third, you can achieve a type of proactive security by generating a new resharing of the signing key at frequent intervals.

However, you are right that for the very basic usage, multi-sigs will be much simpler. (I don't think that efficiency is a huge issue here since you typically wouldn't be doing a huge number of transactions all the time. Bitcoin isn't good for many fast transactions.)


Create a potential input for sha-256 hash given a substring of input?

SHA-256 is¹ a cryptographic hash function. As such, it has preimage resistance: given a hash value, there is no way to find a string with that hash, except by trying all strings until you find one that works. Therefore you'll have to try all possible inputs, i.e. all strings that contain the known substring. (You can of course be smart about it: try the most likely strings first, if there's such a thing as most likely in your scenario.)

If you do find a string, you can be confident that it's the right one. Cryptographic hash functions also have the collision resistance property: it is infeasible (i.e. practically impossible) to find distinct strings with the same hash. There is no way to find another string with the same hash, of length N or otherwise.

¹  As far as anybody knows, or at least anybody who speaks publicly on the topic.


Can I use guids / uuids as counters for key derivation?

Yes, in practice this will be fine.

Expert cryptographers will give you grief and tell you that you should be using a PRF, and technically speaking, they will be right.  So, if you want to spare yourself from having that conversation, replace SHA256 with a PRF, such as AES-CMAC or SHA256-HMAC or PBKDF2 (using the master key as the key and the uuid as the seed).  This is the technically proper way to do it, and I'm thoroughly sympathetic with those who argue you should do it this way.

That said, even if you went ahead and used your original proposal (SHA256), you'd almost certainly be fine.  So, if I saw you using SHA256 instead of a PRF, I wouldn't get too worried about it.

P.S. I see a lot of confusion in the comments.  The following are not identical: PRF, MAC, HMAC.