Confusion and Diffusion in the AES functions

I should start by saying that the notions confusion and diffusion can not provide an in-depth understanding of the design of the AES, simply because they are not specific enough. Instead, the key to understanding the choice of the steps in the round transformation is the wide trail strategy.
That said, we can of course try to understand the effect of each transformation with respect to the "confusion" / "diffusion" concepts. Needless to say, the outcome of such a thought experiment is at least somewhat subjective. In any case, a proper definition of "confusion" / "diffusion" is essential. Shannon wrote:

Two methods (other than recourse to ideal systems) suggest themselves
for frustrating a statistical analysis. These we may call the methods
of diffusion and confusion. In the method of diffusion the
statistical structure of $M$ which leads to its redundancy is
“dissipated” into long range statistics—i.e.,into statistical structure involving long
combinations of letters in the cryptogram. The effect here is that
the enemy must intercept a tremendous amount of material to tie down
this structure, since the structure is evident only in blocks of very
small individual probability. Furthermore, even when he has sufficient
material, the analytical work required is much greater since the
redundancy has been diffused over a large number of individual statistics.
The method of confusion is to make the relation between the simple
statistics of $E$ and the simple description of $K$ a very complex and
involved one. In the case of simple substitution, it is easy to
describe the limitation of $K$ imposed by the letter frequencies of $E$.
If the connection is very involved and confused the enemy may still be
able to evaluate a statistic $S_1$, say, which limits the key to a
region of the key space. This limitation, however, is to some complex
region $R$ in the space, perhaps "folded ever" many times, and he has a
difficult time making use of it. A second statistic $S_2$ limits $K$ still
further to $R_2$ , hence it lies in the intersection region; but this
does not help much because it is so difficult to determine just what
the intersection is.

The first comment I would like to make is that diffusion and confusion, if described using the intuitions above, typically only arise by repeated application of the round transformations. Shannon uses the following metaphor (for the construction of "mixing transformations"):

Good mixing transformations are often formed by repeated products of
two simple non-commuting operations. Hopf has shown, for example,
that pastry dough can be mixed by such a sequence of operations. The
dough is first rolled out into a thin slab, then folded over, then
rolled, and the folded again, etc.

For this reason, my answer will mostly be about how each transformation contributes to confusion/diffusion (rather than if these transformations contribute at all).
Diffusion
Paraphrasing to the context of the AES, one might say that diffusion means that the "statistic structure" (this is quite vague) of a plaintext block is spread out over the resulting ciphertext block. For instance, if the first input bit is zero which large probability, this should not be apparent in any small subset of the output bits. (Remark that if this was not the case, one would obtain a strong linear approximation.) This is unfortunately very vague and in fact not really helpful if you are designing a block cipher.
Note that the above interpretation of diffusion is somewhat different from Shannon's "long range statistics", because the latter might be interpreted as "non-neighboring/close bits" rather than "small subsets of bits". I would argue that "small subsets" is what is really meant because Shannon also talks about "long combinations of letters [~bits] in the cryptogram" (emphasis mine).
With this interpretation:

AddRoundKey does not contribute to diffusion. (Well... there are reasons why you could argue that they do, but let's not go into that.)
ShiftRows and MixColumns: these operations mix bits among rows or columns. Hence, you could say that this ensures "non-localized statistics" (again, somewhat vague). Again, the fact that the linear layer has to "mix" bits is not concrete enough to be very useful to a designer - maximizing the number of active S-boxes (cf. wide trail) is the real underlying idea.
SubBytes leads to diffusion at the byte level. If you think of the "symbols" as bytes then you can argue that SubBytes doesn't provide diffusion. I think it is more accurate to say that SubBytes does contribute to overall diffusion.

The last point may need some clarification. It is commonly said that the S-boxes provide confusion (this is correct by the way, see below) rather than diffusion. Nevertheless, consider a cipher such as PRESENT which uses a bitwise permutation for its linear layer. Clearly, if you remove the S-box layer of PRESENT then the result does not satisfy the intuition behind diffusion that was mentioned above. In this context, another answer of mine about statistical saturation attacks seems relevant.
Of course, if you remove SubBytes in AES, the whole cipher becomes affine over $\mathbb F_{2^8}$. More about that below.
Confusion
Confusion, according to Shannon, is all about the secret key. The idea is that the key is mixed into the output in such a "complicated" (this is again vague, for sure) way that a simple/reasonable test statistic $s$ only allows you to conclude that the key must satisfy some complicated equation $f(K) = s$. Shannon notes that if $f$ is sufficiently complicated, it should also be hard to combine the information provided by different statistics.
Now, what is a complicated $f$? This is difficult to formalize, but at least one can think of a few things that $f$ should not be. For example:

If we take $s$ to be the ciphertexts corresponding to one or more known plaintexts, then obviously $f$ should be nonlinear (otherwise one can just solve a linear system of equations). In fact, "nonlinear" is not enough by itself: there is a broad class of so-called algebraic attacks.
If we take $s$ to be the (estimated) bias of a sum of a few plaintexts and ciphertext bits, then the sign of $f(K)$ should not be (roughly) $(-1)^{\kappa}$ where $\kappa$ is some linear combination of key bits. Indeed, this is Matsui's first algorithm for linear cryptanalysis.
... (One can think about most other attacks from this point of view.)

That said, I would conclude the following about the steps in the AES:

AddRoundKey is essential for confusion because you need to have some way of mixing the secret key (which is what confusion is about) with the state.
ShiftRows and MixColumns: these operations are typically associated with diffusion, but they are also necessary to obtain overall confusion. Indeed, if you wouldn't mix columns (or rows), then the equations describing the AES would be easy to solve.
SubBytes are essential for the confusion. In particular, it is nonlinear. Note that SubBytes alone is clearly not sufficient.
The key schedule shouldn't be forgotten. It also contributes (or rather, can contribute) to confusion.

In modern cryptography, "confusion" is often used in a broader sense. For example, one can reasonably talk about confusion even in the absence of a key (e.g. in permutation-based cryptography). That's a different question though.
Conclusion
I should reiterate that "confusion" and "diffusion" are rather vague. At best, these concepts can give you some intuition about why it might be possible at all to construct a secure block cipher. They are not sufficient to really understand the design of modern block ciphers such as the AES.
Just to make sure you get a clear answer to your specific questions:

Can confusion be introduced without a secret (subBytes)?
Can confusion be introduced from the state alone (Mix Columns)?

The answer to the first question is no, but I must remark that SubBytes is not a secret in the AES. (But if "AddRoundKey" was intended, the answer would still be no.)
The second question must also be answered in the negative, see the comments about nonlinearity above.


Using bcrypt for MAC - is it correct and secure?

Although your scheme is secure - especially with a random key of 32 bytes or higher - it won't offer any benefit over HMAC. It's therefore not recommended to use such a scheme.

Also note that `bcrypt has been designed for key stretching which is deliberately not efficient. You have ample entropy in your key so there is no need for key stretching.


about entropy and random number generator

Yes, this is correct. (up to the typos that "so each bit is occurred at" in 1. should read "so each 128-bit value occurs at", and that the unit "bit" is missing at the end of that sentence; as well as the not-mentioned assumption that every time a 128-bit value is randomly picked, its value is independent of the choices take before). If the state of a cryptographically secure PRG is exactly 128 bit, then it's not allowed to "loose" any entropy during operation to be 128-bit secure, and it has to be seeded by a perfectly uniform random source.

The problem is how to choose the initial state. An attacker should have only a chance of $2^{-128}$ to guess the initial state, as (s)he could otherwise just calculate the output of the PRG (after guessing the initial state) to predict its output. So you have to find a way to pick a uniformly distributed random 128-bit value for the initial value, which is a real problem: you need a random source (that cannot be observed by the attacker) and a way to extract 128 bit entropy.


AES - What is the advantage of a 256-bit key with a 128-bit block cipher?

No, this isn't an oversight. AES is a block cipher, which is a keyed permutation. Now if you have a permutation of, say, three elements there are e few permutations possible:

a -> a
b -> b
c -> c

but also:

a -> b
b -> c
c -> a

and

a -> c
b -> a
c -> b

and

a -> c
b -> b
c -> a

(there should be $6$ for $3!$, the factorial of three, I won't write them all out)

Now if you look closely, there are more than 3 permutations possible. The actual number of permutations is higher than the input/output! To be precise, the number of permutations is $(2^{128})!$, which is a lot more than $2^{256}$.

The purpose of the key is to select one of the possible permutations. So the key could be a lot larger than 256 bits and still be meaningful. This also means that there may be multiple keys that map a specific ciphertext block to a specific plaintext block. An attacker may have to validate more pairs to be reasonably sure of success. For instance, in both the last two permutations in the example, a maps to c.

The block size is - as Yehuda Lindell writes in the other answer - needed when many blocks are encrypted. For instance when you choose a random nonce for CTR mode, the blocksize must be high enough or you will get overlaps in the counter that is encrypted to create the key stream (i.e. choosing a twice in the example). In that case the key stream would repeat, breaking the stream cipher.

An example of a block cipher with a much larger maximum key than block size is Blowfish, which has a block size of 64 bits and a key size of max 448 bits. Blowfish is considered deprecated by the author, Bruce Schneier. Besides other issues, the small block size is a major reason for the deprecation. Both followup ciphers, Twofish and Threefish, expand the blocksize.


Why does HMAC need a fixed length padding?

In HMAC, the key $K$ [after it has been replaced by $H(K)$ if $K$ was wider than the hash's internal block size] is padded with zeros to the hash's internal block size. The question asks why this padding.

In a nutshell: the security argument of HMAC would not hold without that.

HMAC's original and improved security arguments make heavy use of the Merkle–Damgård internal structure of the hash, that is:
$$\begin{align}
H_0&=\text{IV}&\text{ initialization with a public constant}\\
H_{i+1}&=F(H_i,B_i)&\text{ process }n\text{ padded blocks with the round function }F\\
\text{output}&=H_n&\text{ final result}
\end{align}$$
Heavily simplified, a central requirement of the proof is that during the first of the two hashes in HMAC, if the adversary knows nothing ultimately exploitable about $H_i$, then even though she might know and be able to manipulate $B_i$, she will know nothing ultimately exploitable about $H_{i+1}$. The padding performed on $K$ is such that $K$ maps (within XOR with constant ipad) exactly to $B_0$, and that is enough to insure that the adversary knows nothing ultimately exploitable about $H_1$; that bootstraps the proof by induction that the adversary knows nothing ultimately exploitable about any $H_i$ for $i>0$, hence knows nothing ultimately exploitable about the output of the first hash in HMAC. By contrast, without padding, the adversary would be able to manipulate in part $B_0$, which is mixed by $F$ with the known $H_0$, and we'd have no bootstrap of the security argument.

The second hash in HMAC transforms said nothing ultimately exploitable about the output of the first hash into an overall HMAC output which is indistinguishable from random; again the proof uses that the adversary does not know the other input $H_1$ of the function $F$ that receives the first hash's output, since that is entirely within $B_1$, thanks to the padding of $K$.

When the key $K$ is larger than a block, HMAC replaces it with its hash. Keeping the key as is, unpadded, would not be satisfactory for the same reason as above: we'd have no security argument (e.g. for 64-byte block size, 20-byte hash size, 84-byte key of which the first 64 bytes are zero).

I think padding with zeros to the next block would provide adequate security. But compared to that option, replacing the key with its hash:

leaves the security argument unchanged (it aims at the security level of the hash width, which is about that of the hashed key substituted to the original);
decreases the computational complexity of processing long keys by a factor of 2 (asymptotically);
only ever increases the number of internal hash rounds (and then only by 1 round out of at least 6) for a narrow range of key size (for SHA-1 and SHA-256: 120 to 128 bytes).


I try to provide a brief intro.

ABE

Attribute-based encryption (ABE) is a relatively recent approach that reconsiders the concept of public-key cryptography. In traditional public-key cryptography, a message is encrypted for a specific receiver using the receiver’s public-key. Identity-based cryptography and in particular identity-based encryption (IBE) changed the traditional understanding of public-key cryptography by allowing the public-key to be an arbitrary string, e.g., the email address of the receiver. ABE goes one step further and defines the identity not atomic but as a set of attributes, e.g., roles, and messages can be encrypted with respect to subsets of attributes (key-policy ABE - KP-ABE) or policies defined over a set of attributes (ciphertext-policy ABE - CP-ABE). The key issue is, that  someone should only be able to decrypt a ciphertext if the person holds a key for "matching attributes" (more below) where user keys are always issued by some trusted party.

Ciphertext-Policy ABE

In ciphertext-policy attribute-based encryption (CP-ABE) a user’s private-key is associated with a set of attributes and a ciphertext specifies an access policy over a defined universe of attributes within the system. A user will be ale to decrypt a ciphertext, if and only if his attributes satisfy the policy of the respective ciphertext. Policies may be defined over attributes using conjunctions, disjunctions and $(k,n)$-threshold gates, i.e., $k$ out of $n$ attributes have to be present (there may also be non-monotone access policies with additional negations and meanwhile there are also constructions for policies defined as arbitrary circuits). For instance, let us assume that the universe of attributes is defined to be $\{A,B,C,D\}$ and user 1 receives a key to attributes $\{A,B\}$ and user 2 to attribute $\{D\}$. If a ciphertext is encrypted with respect to the policy $(A \wedge C) \vee D$, then user 2 will be able to decrypt, while user 1 will not be able to decrypt.

CP-ABE thus allows to realize implicit authorization, i.e., authorization is included into the encrypted data and only people who satisfy the associated policy can decrypt data. Another nice features is, that users can obtain their private keys after data has been encrypted with respect to policies. So data can be encrypted without knowledge of the actual set of users that will be able to decrypt, but only specifying the policy which allows to decrypt. Any future users that will be given a key with respect to attributes such that the policy can be satisfied will then be able to decrypt the data.

Key-Policy ABE

KP-ABE is the dual to CP-ABE in the sense that an access policy is encoded into the users secret key, e.g., $(A \wedge C) \vee D$, and a ciphertext is computed with respect to a set of attributes, e.g., $\{A,B\}$. In this example the user would not be able to decrypt the ciphertext but would for instance be able to decrypt a ciphertext with respect to $\{A,C\}$.

An important property which has to be achieved by both, CP- and KP-ABE is called collusion resistance. This basically means that it should not be possible for distinct users to "pool" their secret keys such that they could together decrypt a ciphertext that neither of them could decrypt on their own (which is achieved by independently randomizing users' secret keys).

Beyond ABE

ABE is just one type of the more general concept of functional encryption (FE) covering IBE, ABE and many other concepts such as inner product or hidden vector encryption (yielding e.g., searchable encryption) etc. It is a very active and young field of research and has many interesting applications (in particular in the field of cloud computing).


What does the acronym "CRT" stand for in the PKCS #1 specification?

Yes. I haven't heard any other possible CRT acronym in direct relation to RSA. Sometimes it is used as file extension for certificates, but those are not addressed in the PKCS#1 standard.

  This specification supports so-called "multi-prime" RSA where the
     modulus may have more than two prime factors.  The benefit of multi-
     prime RSA is lower computational cost for the decryption and
     signature primitives, provided that the CRT (Chinese Remainder
     Theorem) is used.

Besides that, CRT is always used when pointing out the CRT parameters throughout the standard.


A trivial approach would be to let the trusted party generate the commit and send the private vector along the signed commit to the proover, which should like this in your age range checking example:

Notation:
$P$ is the proover, $T$ is the trusted party, $V$ is the verifier, $a$ is the information to convince $T$ of $P$'s age, $A \rightarrow B: x$ means that party $A$ send information $x$ to party $B$.

$P \rightarrow T$: $a$
$T$ generates chooses a random $r$, calculates $C=rG+[age]H$ and signs $C$ using his private key.
$T \rightarrow P$: $r, C, signature$
$P \rightarrow V: C, signature, proof$

Whilst straightforward, the trusted party get's to choose the commit which you may not want depending on how much you trust the trusted party, so here is another approach that allows the proover to choose $C$.

$P$ chooses a random $r$ and calculates the commit $C = rG + [age]H$.
$P$ signs $a$ with $r$ as private key
$P \leftarrow T: C,a, signature_a$
$T$ looks up $P$'s age, calculates $R=C-[age]H$, verifies $signature_a$ against $R$ and sign's $C$ using $T$'s private key.
$T \rightarrow P: signature_c$
$P \rightarrow V: C, signature_c, proof$

Of course, $V$ will have to verify the signature. Instead of a signature, $V$ could also make a request to $T$ to check whether it approves $C$ which allows $T$ to revoke easily but requires you put more trust into the trusted party.

Lastly, I'd like to mention a completely different approach used in Monero's RingCT which uses commits to represent balances and the blockchain to keep track of and to verify them.


How can I encrypt a plain text of length l to a ciphertext of a different length

It is impossible to have a ciphertext shorter than the plaintext, while still being able to decrypt it. This is quite obvious: an $\ell$-bit ciphertext contains at most $\ell$-bit of information, so as long as the messages have more than $\ell$ bits of entropy, some information is lost (and if it is longer than $\ell$ bit but has very little entropy, then you can compress the message before sending it).

In the case of public key encryption, in fact, if your message is $\ell$ bit long, you cannot even have a ciphertext of length $\ell$ if you want some important security properties: encryptions schemes are usually required to satisfy semantic security, which states that if a ciphertext encrypts one of two messages, it is infeasible to determine which one it encrypts (even knowing the plaintexts). But this implies that many ciphertexts must correspond to a same plaintext: if a plaintext is associated to a single ciphertext, one can break this property just by encrypting the two messages and checking equality with the ciphertext. Therefore, to get a probability, say, at most $1/2^{80}$ for the encryption scheme to be broken, a ciphertext will be at least 80 bits longer than the maximum size of a plaintext.

If you want a longer ciphertext, just pad with zeroes. You can make the ciphertext as long as you want that way.


Is it safe to use the same IV for multiple encryptions in AES CBC mode when you are always encrypting random bytes?

No, you're not weakening your data in that case. You could even use ECB in to encrypt random data. Symmetric key wrapping often just uses ECB. But beware that it depends on how many bytes you encrypt.

You may want to make sure all bytes are random (if you know the plaintext size in advance). Think about encrypting a single random byte and filling the rest with zero's or PKCS#7 compatible padding. Identical values would be easily detected.

You may want to very clearly document what you're doing though, because if you add context / structure to your random bytes it would be pretty easy to mess things up.

You could use SIV if you want to have secure, authenticated key wrapping for your random bytes. You would not need to generate a random IV and SIV would handle additional structure well. You would need to have an implementation of SIV and room for the synthetic IV (which is also the authentication tag) though.


Is AES really used for Top Secret stuff?

Decoy for whom?

Security, and cryptography specifically, has a need for public scrutiny. It's been proven time and time again that hiding the nature of the protocol/algorithm/scheme doesn't provide any tangible security. Kerckhoffs' principle explains this:  A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.

It's "secure" up until someone finds out how it works and breaks it. Publically reviewed algorithms are something that people are always trying to break. The more people that try (and fail) to break something, the better that something is. This is important because it's really difficult to design crypto properly.

To answer your question specifically: Yes, AES is used for classified materials. Other algorithms are also used depending on the nature and use of the data.

A quick Google search came back with this PDF doc from NIST: Guideline for Implementing Cryptography In the Federal Government.  It may be out of date, or there may be better documents, but it's an enlightening read.


In RSA, what is faster attacking "d" when plaintext is known, or factoring when M is unknown?

Brute-forcing the private key is never a good idea with RSA, unless the key was generated with a $d$ of an artificially (very) low size. Indeed, for a 1024-bit modulus, factorization is said to have cost about $2^{77}$ (barely feasible, and estimated, with high memory-related costs, so it has not been actually done yet) while a normal $d$ will have length about 1024 bits, for a completely unrealistic exhaustive search cost.

Moreover:

If you find out $d$, then you can easily compute the factors of $n$, so even your brute-force attack on $d$ is, in fact, a factorization attack.
A brute force attack on the smallest of the factors of $n$ is a poor factorization algorithm (known as "trial division"), but still ludicrously faster than brute-force on $d$ ($2^{512}$ against $2^{1024}$).
This is public-key cryptography. Everybody can encrypt, using the public key. So the attacker can have billions of known pairs plaintext/ciphertext if he wishes so, by simply generating then. Chosen ciphertext attacks are another matter, though.
You missed an exponential. When a key has length $x$ bits, brute-forcing it has cost $2^{x-1}$, not $x/2$.
Polynomial complexity has very little relevance to the subject. Complexity classes are about asymptotic behaviour, when operand sizes grow toward infinity. This tells things about performance on a specific operand size only empirically (usually, polynomial algorithms are reasonably fast with values of "practical size", but there is no theoretical basis for why it should be so).

The usual pointer for estimates on key strength is www.keylength.com which contains nice comparators and a lot of pointers.


Why are Random Oracle not achievable in practice?

We don't use random oracles. They are not practical. What we really do is modelling our theoretical work after the random oracle model.

There are many schemes which use hash functions. For some of them we have a proof of security, but only with some special cases. For example the padding scheme Optimal asymmetric encryption padding (OAEP) is proven to be semantically secure under chosen plaintext attacks - but only in the random oracle model. OAEP uses hash functions to randomize the message before encrypting with an asymmetric cipher, but what if these hash functions are not secure? Are they secure? We don't know, but probably not. Many were broken, like MD5 or SHA-1.
How can we prove that a scheme is secure if we are not sure that our underlying algorithms are secure? We can't. That's the reason why we have the random oracle model.

In the Random Oracle Model we just do everything like we always do, but there is a "magical" algorithm which represents a proven secure, perfect hash algorithm. In practice that's not really doable, because for this algorithm to work we need a true random number generator and a (nearly) infinite list of input und output values. That's already hard to do, but what's even more problematic is that every program / person who uses this algorithm has to have access to this number generator and list. How should that be done? Most likely with a central position which accepts messages and outputs the hashes for them. But how would you secure the connection between your program and this central position? It's just not practical doable to get a random oracle as your hash function in algorithms. It's like the one-time pad - nice to look at, provable secure and fully useless except for really special cases. We want fast and easy encryption for our bank details, not secure the Moscow–Washington hotline.

What we really do is just pretending to use them. We create our protocols and say "here we use a random oracle" if we need a secure hash function. Now we can try to prove our protocol and sometimes are even succesful with it. In most cases that works only because we used a random oracle. In reality we still implement something like SHA-256 or SHA-3 then and just ignore the possible problems - as long as nobody knows how to break our hash function and it works indistinguishable like a random oracle we should be save. Having a prove also helps to rule out mistakes in our protocol itself. Either we have a secure scheme or there's a problem with the hash algorithm. Without a prove there could also be a small, but fatal mistake nobody has thought of.

See also the article series "What is the Random Oracle Model and why should you care?" from Matthew Green.


Is .NET DESCryptoServiceProvider secure in this case?

The key space for DES is far too small (56 bits). Therefore, any use of DES is not secure. It doesn't matter what mode you use. If the attacker has one plaintext, ciphertext pair, they can brute force the key space and recover the key in a feasible amount of time (24 hours using the cloud).

  But most importantly, how it could be made secure? Will change to AES help?

Moving to AES will definitely help. What will help the most is first, defining the desired protection model (i.e., what does "secure" mean in your context?). Do you only care about confidentiality? Do you also care about integrity? How about authenticity? Deciding this will help you decide which mode to use. In particular, do you need a MAC or authenticated encryption mode?

Once you have this figured out, choose the cipher and mode to match your needs, not just security needs, but also performance needs.


Embedded devices Authentication, Integrity and Confidentiality

I do not see an immediate flow, but the public-key cryptography seems to be an overkill in your system with a single server. As long as the server keeps some keys of each device $D$, it may as well keep a single symmetric key $K_D$, and use a single authenticated encryption scheme $\Pi$ with key $K_D$, for instance, AES-GCM. This would simplify your system significantly, and you would not need certificates. You would not even need random number generator, except for the key generation.


Proper Way to Encrypt Data with Two Keys?

To begin with, some essential requirements are missing from your question at the time I write this, so I am going to assume:

$User$ trusts $System$.
$System$ trusts that $User$ will not pass $Key_{User}$ to any entity that $User$ does not trust to be $System$.

This implies, in particular:

$System$ is already authenticated to $User$, and $User$ already has a channel for passing $Key_{User}$ to $System$ with preserved authenticity, integrity and confidentiality.
The environment of $System$ is such that there is no risk $Key_{User}$ or $Key_{System,User}$ will be extracted from $System$ by an attacker. Alternatively, there is no risk it will happen without detection, in which case an auxiliary protocol exists for replacing the keys.

If the above conditions are met, both methods you describe in your questions are fine for generating an effective content encryption scheme. Just a few points:

Generating an effective key simply by concatenating two pieces contributed by two separate entities (as in your first method) is an unusual approach. I would probably prefer to combine them using a Key Derivation Function instead of simply concatenating them. However, given that $System$ and $User$ both trust each other, the only compelling reason for using a KDF instead of concatenation, would be if, in some sense, it would be worse if both entities are compromised, compared to if just one of them is compromised. A KDF will be better at hiding the other part of the key material, compared to just concatenation before the AES key schedule.
Encrypting the payload contents twice (as in your second method) is also a bit unorthodox, but it can be done in such way that you will get at least the same security, as with just one encryption key. Hence, you could in such case rather just encrypt $Key_{System,User}$ with $Key_{User}$ using a key wrap encryption scheme, and store the resulting cipher text $System$ side. Using key wrap encryption might provide additional benefits, such as the ability for $User$ to change $Key_{User}$ without $System$ having to decrypt and re-encrypt the entire content cipher test (if the key is used for stored data), and the ability for $System$ to give multiple users ability to decrypt the same cipher text, bu wrapping the same content encryption key using multiple user keys.


Would modifying the key of an arbitrary ARX cipher make it harder to break?

Consider a simple ARX block cipher in which after each block is encrypted, the key is rotated and/or XORed by some variable value

It sounds like you are asking "What if we apply a key schedule at the mode of operation level?"

If the cipher is strong, then there should be no need to modify the key between invocations of the encryption function; The fact that the cipher is strong implies the adversary cannot obtain the key from plaintext-ciphertext pairs, so "more security" is not obtained by modifying the key in any deterministic way.

  Could it somehow make the key less secure?

Yes, absolutely: Assume that your publicly-known deterministic key evolution function simply outputs all $0$, regardless of input; We might say that this is a pathological example, but it's really just an extreme case of "how biased is your function" - your function could produce outputs that are more easily guessed than the input to your function.

  For example, if the key is 0101 and after a block is encrypted the key is rotated left by the last 2 bits (in this case 01). So the key for the next block encrypted will be 1010.

With this specific example, you stand to leak key bits by side channel information: The secret data dependent rotations can leak information about the operands to external observers. If an adversary can somehow cause the encryption method to be invoked at will, and they can observe timing information, then they can potentially use this to recover bits of the key.

Basically, more is not necessarily better when it comes to cryptography: You want to do exactly only what is required to accomplish the goal, and no more; Excess operations simply create more attack surfaces.


Are low security curves for ECDSA not supported?

I'm not sure, but I guess that two different openssl version or just builds could be done with or without support of Elliptic Curves with unsecure security levels.

Furthermore your curves have very low security level, and you shouldn't use them if security is a concern (and if it's not, you probably don't need ECDSA at all).

However, your assumption that "curve support is rather complicated" is wrong.

With libcrypto, the OpenSSL library, not the command line tool, you can use EC_GROUP_get_curve_GF to create your own elliptic curve. If you put in the parameters of those curves, you will be able to use them, with the library, even if the parameters are not encoded in OpenSSL.


Is there a method to break an EC curve for all key-pairs (Q,d) such that (Q=d*G) faster than breaking every single key-pair?

Well, Big-Step/Little-Step can be written as a precompute-table and then lookup type algorithm, however, it doesn't become close to practical with a 160 bit field.

Here's how Big-Step/Little-Step works; we first select two integers $a$ and $b$ with $ab \ge size(group)$ (I consistently talk about group rather than the curve; that's because Big-Step/Little-Step will apply to any finite group.  In terms of Elliptic Curves, for practical purposes we can make the assumption that $size(group) \approx size(field)$.

In the precompute phase, we construct a table with the pair of values $(ib, (ib)G)$  for $(0 \le i < a)$.  This table will contain $a$ rows, and takes $O(a)$ time to construct.  Note that this table does not depend on the point $Q$ that we'll end up computing the discrete log on.

In the lookup phase, we compute the points $Q - jG$ for $0 \le j < b$, and look up each of these points in the table.  If we find one of the points in the table, we have $(ib)G = Q - jG$ (where $i$ is the value in the table, and $j$ is the value we used to compute the point), we then know that $Q = (ib + j)G$, and hence we have the discrete log.  This phase takes $O(b)$ expected time (assuming each lookup can be done in constant time using appropriate data structures).

Now, the total time taken is $O(max(a,b))$; to minimize this value, we generally assume that $a=b\approx\sqrt{size(group)}$, thus giving us a squareroot time algorithm.  However, there is no such hard requirement, and if we're going to reuse the table multiple times, it makes sense to increase the value of $a$ (the one time cost) so we can decrease $b$ (the per-discrete-log cost).

However, once we start talking about a group with circa $2^{160}$ members, well, this doesn't work out.  For one, even in the balanced case, we're talking about a table with $2^{80}$ entries; that in itself is impractically large.  If we consider increasing $a$, the table size becomes even more impractically large.

Now, one obvious idea to reduce the table size is to create a Rainbow table.  It turns out that Rainbow tables will work in the way we want (allowing us to build a table that we can use to lookup $i$ given $(ib)G$ values); however, it turns out not to buy us anything.  Rainbow tables allow us to compress the table by a factor of $k$ by increasing the lookup time by that same factor $k$.  That turns out to be the killer; because the lookup phase involved $O(b)$ table lookups.  We can make the table $O(a/k)$ entries long; however the lookup phase will now take $O(kb)$ work; we haven't gained anything that we wouldn't have gotten by making $a$ smaller by a factor of $k$ and $b$ larger by a factor of $k$.


What does the minimal number of round of "nr" use Keccak to avoid “collision attack”?

Cursory literature search suggests that the best collision attacks reach only six rounds of Keccak:

Kexin Qiao, Ling Song, Meicheng Liu, and Jian Guo, ‘New Collision Attacks on Round-Reduced Keccak’, in Jean-Sébastien Coron and Jesper Buus Nielsen, eds., Advances in Cryptology—EUROCRYPT 2017, April 2017, Springer LNCS 10212, pp. 217–243 (link, preprint)
Ling Song, Guohong Liao, and Jian Guo, ‘Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak’, in Jonathan Katz and Hovav Shacham, eds., Advances in Cryptology—CRYPTO 2017, Part II, Springer LNCS 10402, August 2017, pp. 428–45 (link, preprint)

Of course, attacks only get better, so it would be imprudent to choose six rounds.
 This state of affairs justified the use of a mere twelve rounds in KangarooTwelve at substantial speed increase over the twenty-four used by SHA-3.


Is lattice-based cryptography practical?

Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different types of algorithms, lattice-based algorithms dominate the submissions. These include NTRU and its variants, R-LWE, and FALCON (designed in part by one of our regulars!). Lattice-based cryptography itself is fairly well understood, exploiting lattice problems as a hardness assumption.

Lattice-based cryptography is one of only a few popular designs for post-quantum cryptography. There are others, such as code-based cryptography, multivariate polynomial cryptography, and hash-based signatures. Of those, code-based algorithms are the only class that could realistically compete with lattice-based algorithms, since it is used by the McEliece cryptosystem which itself has been around for quite a while and is well-studied. Multivariate polynomial cryptography is not as popular, and many of the proposed algorithms using it have been broken. Lastly, hash-based cryptography, while quite secure, is only useful for digital signatures, not key exchange. It additionally requires very large signatures. This explains why so many proposed algorithms are lattice-based.

Lattice-based cryptography is also very fast. For example, NTRU performs private key operations even faster than RSA, since the time increases with the cube of the key size for RSA, but quadratically for NTRU. The viability of lattice-based cryptography is undisputed. All we need to do now is iron out the kinks and standardize a particular implementation.


Partial collisions of hashes, why is this important?

This seems to boil down to whether or not anyone would have a reason to truncate a hash. The answer is yes, absolutely. For example, someone who needs a 256-bit digest may want to use SHA-512/256 instead of SHA-256 on a 64-bit processor for improved performance (the former uses 64-bit operations whereas the latter uses 32-bit operations). SHA-512/256 is nothing more than regular SHA-512 with a distinct IV, truncated to a 256-bit value. Likewise if someone wants a hash with 280 collision resistance, they would want to truncate a stronger hash like SHA-256 to 160 bits instead of using SHA-1 which has cryptographic weaknesses that allow collisions to be found faster than predicted by the birthday bound.

Another reason someone might want to truncate a Merkle–Damgård hash function is to resist length extension attacks. SHA-256 is vulnerable to them, whereas SHA-512/256 is not, despite being of the same size. An efficient collision against such a truncated hash could then be considered problematic.


How to prove if a Hash Function is collision resistant

For the function $F(x) = ax \bmod n$, where the inputs are limited to the range $[0, n)$, this function will be a bijection (that is, no collisions) if and only if $a$ and $n$ are relatively prime.

Here is a proof in the direction you're asking about:

Suppose there exists a collision, that is, we have a pair $x, y$ with $0 \le x < y < n$ where $F(x) = F(y)$.  This implies that $a(x-y) \equiv 0 \pmod n$, that is, there exists an integer $k$ with $a(x-y) = kn$.  $x-y$ is not a multiple of $n$ (it is not zero, as $x < y$, and we know that $|x - y| < n$, hence it is not a larger multiple of $n$), hence there exists a prime power $p^k$ where $n$ is a multiple of $p^k$, but $x-y$ is not.

We know that $a(x-y)$ must be a multiple of $p^k$, hence $a$ must be a multiple of $p$, and hence $a$ and $n$ are not relatively prime.

The other direction is easier; suppose $a$ and $n$ are not relatively prime, that is, there exists a prime $p$ for which both $a$ and $n$ are a multiple.  Then, we have $F(0) = F(n/p)$, hence there exists a collision.


Are two outputs of a PRF computationally indistinguishable when the keys are somehow related?

They are indistinguishable because the keys are related only by a value that random from the distinguisher's point of view. More formally, you can argue that your distribution is indistinguishable from one in which all PRF keys are chosen independently. Note that this is very sensitive to the fact that the distinguisher can't query $f(k',\cdot)$.
What you described is this distribution induced by the following process (I will rename $k$ to $k_0$). It is easier to assume that the $x_i$'s are just some arbitrarily fixed values. Even if they are chosen adaptively, it doesn't substantively change the nature of the argument.

Process 0:

$k_0,k' \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + f(k',i)$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

This process uses $k'$ only as a key to $f$, and nowhere else. The PRF security guarantee is that it has a negligible effect on the output to replace distinct outputs of $f(k',\cdot)$ with randomly chosen values. The resulting process is:

Hybrid process 1:

$k_0 \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: choose $r_i \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: set $k_i = k_0 + r_i$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Observe that this hybrid process uses $r_i$ only as a one-time pad to mask $k_0$ (here I'm assuming "+" refers to a group operation like XOR). Since each $r_i$ is used only once in this way, and nowhere else, it means each $k_i$ is distributed uniformly. So we can simplify (with no effect on the output distribution):

Hybrid process 2:

$k_0 \gets \{0,1\}^\lambda$
for $i \in \{1,\ldots,n\}$: choose $k_i \gets \{0,1\}^\lambda$
output $f(k_0, x_0), f(k_1, x_1), \ldots, f(k_n, x_n)$

Now each $k_i$ is chosen uniformly/independently, and used only as a PRF seed. From here you can apply the PRF security and replace each term $f(k_i, x_i)$ with a random value. Technically speaking you would perform $n+1$ hybrids to do this, one for each $k_i$ to which you are applying the PRF security guarantee. The final result will be a process that outputs $n+1$ uniformly chosen values.
For an exercise, think carefully about what step of the argument goes wrong when the adversary is also able to query $f(k',\cdot)$.


What encryption algorithm is context-free, deterministic and symmetric?

There is SIV mode. It essentially computes a MAC over the plaintext and uses it as IV for encryption. It obviously doesn't offer IND-CPA security, but shouldn't leak anything beyond length of the plaintext and if two plaintexts are identical.

There are some generic constructions as well, like 3 to 4 rounds feistel networks, EME, etc.


Strength of key derived from a hash function considering the birthday attack

You—the adversary—have a way to test whether a candidate key $k_i$ might be the true secret key $k^*$.  Since $k^*$ is uniformly distributed among all 256-bit keys, each candidate $k_i$ has probability $\Pr[k_i = k^*] = 1/2^{256}$ of being correct.  No matter what order you try things in, the expected number of guesses is $$\sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k^*] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}.$$  (You may, of course, encounter false positives, which you will have to deal with; they do not affect this expected number of guesses before finding the true key, only the probability of falsely thinking you have found the true key when you haven't.)

Why don't collisions and the birthday paradox appear in this analysis?
Collisions are relevant when you're looking for any $k_i \ne k_j$ such that $H(k_i) = H(k_j)$, but you don't care what either $k_i$ or $k_j$ are.  As you try $k_1, k_2, \dots$, searching for a collision, each new key could potentially collide with every previous key, so the probability of a collision among some pair of $n$ keys grows quadratically—specifically, for $n \ll 2^{128}$, it is $$1 - \biggl(1 - \frac{1}{2^{256}}\biggr) \biggl(1 - \frac{2}{2^{256}}\biggr) \cdots \biggl(1 - \frac{n}{2^{256}}\biggr) \approx \frac{n^2}{2^{256}}.$$  (proof; more on birthday paradox)

Note: There may be a batch advantage in the multi-user setting.  If the way you can test a candidate key $k_i$ is by testing whether $H(k_i) = h$ where you know $h = H(k^*)$, and you actually have many target keys $k^*_j$ and hashes $h_j = H(k^*_j)$, you can save cost in a batch attack like computing Oeschlin's rainbow tables in parallel, for a total expected cost of about $2^{256}\!/t$ trials to find the first of $t$ targets, and in the total expected time of as little as about $2^{256}\!/t^3$ sequential evaluations of $H$ if you parallelize it at least about $t^2$ ways.

However, if each user had used a different function, that is if you have $h_j = H_{s_j}(k^*_j)$ with a unique salt $s_i$ per user, then the multi-target advantage vanishes, and you're back to the expected cost of about $2^{256}$.


Certificate Signature Algorithm differs from Signature Algorithm Negotiated for Connection

Are the Certificate Signature Algorithm and signature algorithm in the
  negotiated connection cipher suite used for different purposes?

Yes they are.
The hash negotiated in the cipher suite is completely irrelevant to the certificate. The verification of the certificate and the signatures in the TLS handshake use the hash / signature pair negotiated in the signature_algorithms extension. The hash from the cipher suite is called the Pseudorandom Function (PRF) which is used for authentication (in HMAC-mode) for CBC cipher suites and to derive the [master_secret][4] from the pre_master_secret.

  Does the upcoming sunset for SHA-1 relate to the Certificate Signature
  Algorithm and signature algorithm in the connection cipher suite?

The sunset of SHA-1 only affects the use of SHA-1 in certificates. The SHA-1 based cipher suites will still be available as HMAC-SHA-1 isn't broken by collisions on SHA-1.

  If I'm using the latest version of Firefox why does the server/client
  negotiation not use the preferred SHA-2 algorithm for the connection?

Usually the server picks the cipher suites himself, i.e. the server picks the cipher suite it considers strongest and unfortunately most clients (including Firefox) don't support AES-256-GCM but AES-256-CBC so AES-256-CBC gets picked. As for why it picks SHA-1 over SHA-2 then, it's again the support question. Firefox only supports CBC with SHA-1 but not with SHA-2 so SHA-1 gets picked because of the stronger key size.

In your case the server prefers DHE_RSA_* over everything else. It prefers DHE_RSA_AES_*_GCM_* first, but Firefox doesn't support them (Firefox only supports GCM with ECDHE_*) so it picks the next suite in the list which is DHE_RSA_WITH_AES_256_CBC_SHA.

From the comments:

  [D]oes it alert on intermediate certs as SHA-1 may impact on the clients
  ability to validate the trust chain?

Yes, the browser automatically trusts intermediate certificates signed by a trusted root CA. Thus it may not have seen the exact certificate before, meaning if somebody could find a colliding certificate and somehow make the root CA sign it, you're trusting a malicious certificate (this is the same with leaf certificates).

  Also why not alert on the root cert?

The browser or the OS have a so-called "certificate store" where they store trusted root certificates. There are three reasons why it collisions on SHA-1 don't matter for root certificates.

If the root certificate is sent by the server, the browser may just compare this one byte-by-byte to the local copy and thus any change would cause the alert, but the SHA-1 hash isn't verified explicitely.
If the root certificate is sent by the server, the browser may just compute the hash of the received certificate and compare with the hash of the stored certificate. You'd need a second-preimage on SHA-1 to break this which is considered infeasible as of now.
Usually the root certificate isn't sent by the server. In this case the browser looks at the issuer of the intermediate certificate and check if this one is in the trust store and accepts it if it is in there.


Help understanding basic Franklin-Reiter related message attack

It seems you are well on your way to understanding the attack. After you compute the GCD of these two polynomials you are left with a polynomial of the form $X - m$. It is clear why—if $f_1(X) = X^3 - C_1$ and $f_2(X) = (X + p)^3 - C_2$ have a common root $m$, then they are of the form $(X - m)g_1$ and $(X - m)g_2$, for some arbitrary $g_1$ and $g_2$.

So,
$-m$ is the coefficient of degree $0$ of this common polynomial, and all that is left to do is to extract it. Here's a worked out example in Sage:

p = random_prime(2^512)
q = random_prime(2^512)
n = p * q # 1024-bit modulus

m = randint(0, n) # some message we want to recover
r = randint(0, n) # random padding

c1 = pow(m + 0, 3, n)
c2 = pow(m + r, 3, n)

R.<X> = Zmod(n)[]
f1 = X^3 - c1
f2 = (X + r)^3 - c2

# GCD is not implemented for rings over composite modulus in Sage
# so we'll do it ourselves. Might fail in rare cases, but we
# don't care.
def my_gcd(a, b):
    return a.monic() if b == 0 else my_gcd(b, a % b)

print m
print - my_gcd(f1, f2).coefficients()[0] # coefficient 0 = -m


So if it's just a permutation of 0s and 1s as we've concluded, what is hard about finding an alternate message string that satisfies the constrains I've mentioned on the permutation outcome?

To be more precise, it is a pseudo-random permutation from $\mathbb{Z}_{2^{1600}}$ to $\mathbb{Z}_{2^{1600}}$. It is not just 0s and 1s changing positions.

Because of the size of $\mathbb{Z}_{2^{1600}}$ (which contains $2^{1600}$ elements!), the input and output are related in a somewhat random (but  deterministic way), and it cannot be predicted without actually evaluating the permutation (or its inverse) on a given input and checking the result.

There are tools such as linear and differential cryptanalysis that can be used to try and predict the output, but keccak-f was explicitly designed so that using these techniques would be computationally intractable.

  It seems like I have a very localized problem

You cannot isolate parts of the state and work on them independently. Changing one bit of the state and then applying the permutation diffuses those changes across the entire state in an unpredictable manner.


Improving differential cryptanalysis of a vulnerable cipher

Your cipher seems quite vulnerable to side-channels the way you describe it. Also, differential cryptanalysis depends mostly on a secure S-box. The steps you describe are superficial, since they don't effectively destroy patterns.
Assuming you're using an SP-network, which is generally what a 16-round block cipher would be, let's see what the steps are to perform encryption:

For each round, you

Perform the nonlinear operation (S-box) on the plaintext
mix the key with your intermediate ciphertext
permutate the bits of your immediate ciphertext, providing diffusion

Your obstructing steps are:

bitwise NOT (optional you make it ot not - randomly),

A bitwise NOT destroys no patterns and provides no nonlinearity
Deciding randomly whether to perform this operation only adds 1 bit per round, and makes side-channels that much more likely. This step is pretty much useless while adding potential for faulty implementation.

xor with 128-bit subkey,

You should be mixing the round key anyway. I don't see how this is any different from a normal round cipher.

moving bits by 0 to 127 places.

This could add 7 bits of security per round... maybe? but would be near-impossible to implement without allowing side-channel attacks. Data-dependent memory accesses are a really bad idea (I assume the amount you move the data would depend on the key, the plaintext, or some wacky logic based on both; this would immediately allow side-channels).
If, however, you mean to move the bits by some predefined amount, congratulations! You've implemented a P-box... Which you should be using anyway, considering you're making an SP-network.

In short,
If you want to resist differential cryptanalysis, the real solution is to design the nonlinear component (S-box) in a way that isn't vulnerable to differential cryptanalysis. Perhaps you could steal the S-box from AES since it's already well-understood?
Addendum: Make sure to defend against slide attacks! Your key cycle should be decently designed, as well, and side-channel attacks are horribly easy to accidentally allow in your implementation.


Is it a good practice to use plain text for derivation of Keys?

The hash can only be calculated once you know the plaintext (and, in your case, the Random Text as well). If you already know the plaintext there is no need to know the key anymore.

So basically you have a scheme here that either offers no security at all, or a scheme that is impossible to decipher, even for the intended users (apart from guessing the plaintext).

In your update you show that you now wrap and unwrap the hash. That would make this scheme feasible, but it would still leak information. If you have identical plaintext then you will also have identical ciphertext, unles you change Random Text each time. You also haven't specified an IV.

If you have a random number generator already then it is much easier to calculate $K_d = KDF(K_{master}, Salt)$ and then $C = E(K_d, P)$. Or you could just use a random IV and (authenticated) encryption.

There is a strong feeling that you've deviced your own protocol because you are unfamiliar with common techniques. That's never a good idea.


Synthetic Jitter to Combat Timing Attacks

Yes, and no.

Adding random jitter makes things harder, but since you cannot force the device to go faster then the minimum number of instructions it would take to perform the computation without interrupts, it would still be possible to perform a timing attack using a large number of traces and statistical tools such as low percentile filters, in a similar way as in this paper by Crosby et al.

In the end, the only reliable way to fight timing attacks is really to have constant time code.
You can read more about constant time crypto on BearSSL's website.

But you can encrypt all the data you're sending over the network, using constant time crypto and that's it.
No need to have the whole network stack constant time, if it's only sending encrypted data!


How are constructs with data-dependent swaps and rotations cryptanalyzed?

Algorithms which swap bytes in an array are notoriously hard to analyze; the two main examples are RC4 (encryption) and MD2 (hashing). Being "hard to analyze" does not mean that they are strong; only that we do not have a generic framework such as differential cryptanalysis to apply to them. Both RC4 and MD2 are, academically speaking, "broken" (there are known attacks which are at least theoretically faster than what would be expected from the key/output length). Cryptanalysis is "ad hoc". For instance, in the case of RC4, the main result is due to Mantin and Shamir: they show that the probability of the second output byte of a RC4 stream to be 0 is about twice what it should be (1/128 instead of 1/256). The mathematics are elementary: they simply follow the algorithm description.

Being hard to analyze is not a good thing. It may slow down an attacker, but it also prevents algorithm designers from working efficiently. Simple, regular structures are preferred: we do not want algorithms that are just difficult to break; we want algorithms that we know are difficult to break.

Also, a RAM-based structure with a mutable array implies heavy implementation costs on very small architectures (smartcards, where RAM is the scarcest resource) and on dedicated circuits (FPGA, ASIC). On a PC, RAM access is relatively fast, but still not as fast as one could hope for. MD2 is known to be very slow and RC4 is outperformed by more recent stream ciphers. Hardness of analysis and performance issues make mutable arrays unpopular in recent algorithm designs.


Is it secure to encrypt random key with block cipher in ECB mode?

In general, this is a bad idea. I won't give you any concrete attacks, but will try to explain why you shouldn't do this. In general, if you want to encrypt a key then you should do it using a secure mode for this purpose. (One is the SIV mode of operation. Another is just to use GCM or CCM.) First, I want to stress that you should always use an authenticated encryption mode, by default. Next, the problem of encrypting with ECB is that it has ramifications that can be problematic. In order to see this, denote by $(c_1,c_2)$ the two blocks encrypting the key $k$ which is 256 bits long. Denote $k=k_1\|k_2$ where each $k_1,k_2$ is 128 bits long (Thus $c_1$ is an encryption of $k_1$ and $c_2$ is an encryption of $k_2$.) Now, given $(c_1,c_2)$, it is possible to replace the two blocks of the encrypted key with $(c_1,c_1)$ or with $(c_2,c_2)$. If an attacker can get some plaintext/ciphertext pairs with $(c_1,c_1)$, then it can learn $k_1$ in time $2^{128}$. It can then do the same with $(c_2,c_2)$ and the result is that the entire 256-bit key can be learned in time $2^{129}$. Now, $2^{128}$ is beyond the capabilities of what can be done. However, if you are using a 256-bit key, then you clearly think that $2^{128}$ is not enough of a margin. By using ECB, you have reduced the security down to $2^{128}$. Beyond this, if you can get encryptions under this key, then you can play around to get encryptions under $k_1\|k_2$, $k_2\|k_1$, $k_1\|k_1$ and $k_2\|k_2$. These are all related keys and there are weaknesses to AES under related key attacks. Even if we don't have a concrete attack on this, it is certainly a threat that should not be ignored.

Bottom line, there is no reason to encrypt with ECB so don't do it. If you do, you certainly run the risk of significantly reducing the complexity of the attack. Make sure that you use an authenticated encryption mode (if you encrypt with CTR then you can flip bits and once again get a related-key attack).


Hash functions vs. keyed hash functions in the context of private key generation

There's actually an algorithm designed exactly for this purpose: generating a sequence of keys from one master key.  It's called HKDF (HMAC-based Key Derivation Function, paper here).

The algorithm essentially boils down to two steps: Extract and Expand.  The Extract step accepts any type of "key material" as input, and outputs a pseudorandom key that will be used in the next step.  The purpose of this step is to eliminate any patterns, structure, or bias in the input key, and produce a uniformly pseudorandom output.

If the master key is already a string of uniformly pseudorandom bytes (i.e. it was generated using a crypto-secure RNG), it's safe to skip the Extract step (but be sure to read the notes in the RFC).

The second step, Expand, uses the pseudorandom key from the first step to produce an arbitrary length output.  Typically, Expand is used to produce a long output, and that output is divided up into smaller keys (e.g. 1024 bits divided into four 256-bit keys).  However, it is also possible to use Expand once for each key, while providing a different value each time for the "info" parameter.  This is likely slower, but may be more elegant from an engineering perspective.

HKDF is carefully designed to avoid the problem you identified.  If any of the output keys are ever revealed to an attacker, the remaining keys are still safe.  Of course, if the master key is discovered, game over.

I suggest reviewing the RFC: it's reasonably straightforward, and includes many helpful suggestions on usage.  Section 2 has a precise description of the algorithm.

With regard to performance, let's assume you skip the Extract step and use HKDF with a hash function whose output size matches the desired key size.  The algorithm can now be simplified to $\operatorname{HMAC}(\mathit{key}, \mathit{info} \| 1)$ (where $1$ is the single byte 0x01).  If performance is important, it's possible to precompute parts of the HMAC calculation given the master key.  Assuming a short "info" parameter, only two invocations of the underlying compression function are needed per key (assuming the use of a Merkle-Damgard hash function like SHA-2, SHA-1, or MD5).

Contrast this with a scheme such as $h(\mathit{key}, \mathit{info})$ (a keyed hash function).  With optimizations, only one invocation of the compression function is needed per key.  However, this gives up (1) the security analysis and arguments provided by HKDF, (2) HMAC's additional security against breaks in the hash function, and (3) forces you to consider length extension attacks, among other things.


Is it OK to use a secret IV as key when creating keyed MD5 checksum for fixed-size data?

So the idea is to use the IV of MD5 as a key to create a MAC. Like CodesInChaos mentions in a comment, it would be pretty much equivalent to using $H(k||m)$, if your IV is randomly chosen.

By only using it on fixed length messages you avoid the length extension attack, but that is not the only attack on hash constructions that try to create a MAC. In this question on $H(k||m||k)$ the answer provides links to an attack that uses internal collisions (pdf, Proposition 4):

  This means that an attacker can replace or delete $w \le s$ trailing blocks, and that the attack is applicable even if the input is of fixed length [...]

It can also be applied here. So, no, it would not be secure. At least strictly speaking: the attack requires seeing $2^{n/2}$ authenticated messages, though a smaller amount could allow an attack with some probability.

You should use HMAC or another standard MAC instead. I would also consider a more secure hash than MD5, if you use a hash based MAC, even though the attacks known for MD5 are not sufficient to break HMAC.


Does the timing of cycle-walking pose a threat?

Your intuition is correct: the timing channel in cycle walking does not affect the pseudorandom permutation (PRP) security of a format-preserving encryption scheme built using cycle walking.

More precisely, it is possible to prove that any FPE scheme which meets PRP security in the standard sense also meets a stronger notion of PRP security in which the time taken to encrypt a point is given to the adversary. Intuitively, this is because the distribution of cycle lengths for a random permutation can be simulated given only the size of the domain. See section 9 of the original FPE paper.


Derive a shared secret between different curves

You can probably come up with some key exchange using different curves, for example if they are isomorphic (a curve and its twist). If you have two curves that are independently chosen, it will become much harder (if not impossible).

With regard to SafeCurves, I would be quite careful making too strong conclusions based on the website. By their logic any curve with a prime number of points is insecure. The reasons are that

Prime order curves do not have a ladder. This is not true. They do have a ladder, the formulas are just not as efficient. Even so, you would usually not want to use a ladder since it prohibits precomputation.
Prime order curves do not have a complete addition law. This is not true. They do have one, it is just not as efficient.
Prime order curves have points that are distinguishable from random. This is not true. There exist an encoding (Elligator Squared).

It is nonsense to conclude that these points make prime order curves insecure. They are perhaps not as efficient as other curves, but in no way more insecure.


CSPRNG's (ELI5) What's the purpose of multiple seeds/ regenerating sources of entropy (i.e. /dev/random)?

Check out NIST SP800-90A.

8.6: Seeds

  Reseeding is a means of restoring the secrecy of the output of the DRBG if a seed or the
  internal state becomes known. Periodic reseeding is a good way of addressing the threat of
  either the DRBG seed, entropy input or working state being compromised over time. In
  some implementations (e.g., smartcards), an adequate reseeding process may not be
  possible. In these cases, the best policy might be to replace the DRBG, obtaining a new
  seed in the process (e.g., obtain a new smart card).

8.6.8: Reseeding

  Generating too many outputs from a seed (and other input information) may provide
  sufficient information for successfully predicting future outputs (see Section 8.8). Periodic reseeding will reduce security risks, reducing the likelihood of a compromise of the data that is protected by cryptographic mechanisms that use the DRBG.

But also:

9.2: Reseeding a DRBG Instantiation

  The reseeding of an instantiation is not required, but is recommended whenever a
  comsuming application and implementation are able to perform this process. Reseeding
  will insert additional entropy input into the generation of pseudorandom bits.

It depends on the random number generator if a reseed is necessary. For hash based algorithms, the time before the algorithm hits the same state is very high, so reseeding is certainly not directly required for that reason.

NIST specifies 2^48 calls as maximum to DRBG (e.g. 10.1, table 2) before the DRBG should be reseeded. Even if you take just one bit, then this would still be more than 10^6 that you mention. This is for the hash and AES based algorithms. The number of calls to the 3DES and Dual_EC DRNG's is much lower though, so in the end it depends on the DRNG in use.

Note that stating that 10^6 of random numbers is enough for anyone is like stating that 64 KiB is enough for anyone. I would not make that statement in the same way that Bill didn't.

Reseeding should not have to happen very often if leakage of the state can be avoided (beware of side channel attacks). Saying that it should never happen is however taking it too far. That said, if my computer wouldn't reseed for a week, I would not loose any sleep over it.


What current authenticated key exchange standards exist?

Since you do not describe why TLS Handshake and IKE are appropriate in your situation, and as long as you don't describe your situation, it's hard to really help you. Also, you haven't stated if it's only IKE that's not appropriate, or if that also includes IKEv2 (which improved the IKE protocol). Therefore, I'll simply assume you meant both.

As an alternative to IKE, the first thing that comes to mind is KINK (Kerberized Internet Negotiation of Keys). It's a protocol defined in RFC 4430. It is used to set up an IPsec security association (SA), similar to Internet Key Exchange (IKE), utilizing the Kerberos protocol to allow trusted third parties to handle authentication of peers and management of security policies in a centralized fashion.

As said — as long as you don't describe your situation, it's hard to pinpoint what might suit it best.

It could well be that your situation might be solved with RFC 6539, as IBAKE provides an Identity-Based Authenticated Key Exchange.

Or maybe "augmented PAKE" is a valid option for your situation. That's a variation applicable to client/server scenarios, in which the server does not store password-equivalent data. This means that an attacker that stole the server data still cannot masquerade as the client unless they first perform a brute force search for the password. Examples include: AMP, Augmented-EKE, B-SPEKE, PAK-Z, SRP, and AugPAKE (RFC 6628).

It's hard to tell when not knowing your situation. But I would check out KINK first… as that should be a close-to-perfect match, being an alternative to IKE.


"Dave Check" for a tweakable P-256 ECDH KDF

This is broken, because possession of Epriv (a function of the public tweak value) allows calculation of the output of tokenECDH(Epub) given knowledge of tokenPub (another public value).

This is stupid obvious now, but it took several days to figure it out.


Iterations of pollards kangaroo attack on elliptic curves

My First Attempts:
So I did some testings on the curve $E: y^2 = x^3 + x^2 + x$ with $F_{131}$ and the points $P = (42,69)$ and $Q = 42 \cdot P$. My results for different $N$:

My result for a different Hash function:

So this got me confused, because I did not see any results for different N and I thought only the hash-function is for optimization. But the real answer is much more complex. My sources are wikipedia, handbook of elliptic and hyperelliptic curve cryptography and the original paper.
Answers:

Yes, the hash-function is a semi-random number generator. But it is important for the algorithm! The runtime of the algorithm and the failure rate depends on the hash-function. If the result set is to small, the runtime gets pretty bad. If the result set is to big, the failure rate increases. With the handbook I got the result set $\{ 1,2,..., \sqrt{(b-a)}/2 \}$ and it works pretty good.

I found the answer in the origional paper: $N$ defines the failure rate. If $N$ is low, the failure rate is bigger. So that's the reason I did not see significant changes in the plots. Hint: I still have no idea, if I have to store all intermediate results of the tame kangaroo or not. ( I will edit the post, if I find the answer )

New Code:
The handbook is the main source for the code optimizations. This python code is used with SageMath:
hashValue = 0
def Hash(P):
    if P == 0: return 1
    return int(P.xy()[0]) % hashValue +int(P.xy()[1]) % hashValue+ 1

def pollardKangaroo(P, Q, a, b):
    global hashValue
    hashValue = math.ceil(sqrt((b-a))/2)
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,math.ceil(0.7*sqrt(b-a))):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    for i in range(0, math.ceil(2.7*sqrt(b-a) ) ):
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return 0

This now always generates a pretty reasonable plot for the wild kangaroo (same curve and basepoint):
Reminder:
There are a lot of improvments of the algorithm. My algorithm is not perfect! My main goal was to understand how the hash-function and the numbers of iterations affect the algorithm. And! I will edit this post, if I will find some more important informations.


This can be broken. The exact nature of the attack will depend what modulus you use for the Hill cipher: are you working modulo a prime number, or working modulo 26?

Working modulo a prime $p$

A simple attack, with no fancy mathematics needed.  One simple attack is to start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ.

Note that after simple substitution, the message AAAA will become the 4-vector $(a,a,a,a)$ for some number $a$, and then we'll encrypt this by multiplying the vector $(a,a,a,a)$ with a matrix that is the Hill cipher's secret key.  Similarly, the message BBBB will become $(b,b,b,b)$ and then will get multiplied by the same matrix.  Since every number has an inverse modulo $p$, there's some constant $c$ such that $b=a \times c \pmod p$ (namely, $c = b a^{-1} \pmod p$).  This means that $(b,b,b,b)$ is a constant $c$ times the vector $(a,a,a,a)$.  Consequently, the Hill-cipher-encryption of $(b,b,b,b)$ will be a constant $c$ times the Hill-cipher-encryption of the vector $(a,a,a,a)$.

Guess what number A maps to; say A maps to the number $a$.  Then each other ciphertext will be a constant multiple of the ciphertext for AAAA, and that constant will reveal what the corresponding letter maps to.  For instance, suppose each number in the ciphertext for BBBB is 9 times the corresponding number in the ciphertext for AAAA; then we know that B maps to $9a \pmod p$.  (In general, it is guaranteed that there will always be some constant we can substitute in place of 9.)  Thus, if we guess correctly what number A maps to, then we will learn what number each other letter maps to.

Now apply a standard attack for defeating the Hill cipher.  You'll repeat this $p$ times, once per guess at the number that A maps to.  You can confirm whether the guess was right, by confirming whether you have successfully broken the Hill cipher and can decrypt the ciphertexts to meaningful-looking plaintext.  One of your 26 guesses will lead to correct-looking plaintext; that's the right guess, and now you're done.

Working modulo 26

A simple attack, with no fancy mathematics needed.
We can generalize the above attack so that it also works if we're working modulo 26.  Now we have to deal with the fact that not all numbers have an inverse modulo 26.

As before, we start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ.  One of those will encrypt to the all-zeros ciphertext; say it is the message QQQQ.  Then you have learned that Q maps to 0.

Another of those ciphertexts will contain only the numbers 0 and 13; say it is the message DDDD that encrypted to this.  Then you have learned that D maps to 13.

Now you can apply a similar attack, by guessing which number A maps to, and then applying similar reasoning.

A fancier attack

There's a more sophisticated way you can attack this, by using some fancier mathematics.  Introduce 26 unknowns $x_A, x_B, \dots,x_Z$.  Here $x_A$ represents the number that A maps to, $x_B$ represents the number that B maps to, etc.  We don't know a priori what these numbers are; that's why they are unknowns (variables).

Also, let the $n\times n$ matrix $M$ denote the Hill cipher matrix used for encrypting $n$-letter messages.  We can think of each of the $n^2$ entries of $M$ as another unknown; i.e., $M_{i,j}$ is an unknown, for each $i,j$.

Now each known plaintext-ciphertext pair gives us a system of equations on these unknowns.  For instance, suppose the message WINK encrypts to the ciphertext $(17,5,20,2)$.  Then we learn the following equation:

$$M (x_W, x_I, x_N, x_K) = (17,5,20,2).$$

Why?  Because after simple substitution, WINK becomes the column vector $(x_W, x_I, x_N, x_K)$.  The Hill-cipher-encipherment then multiplies this by the matrix $M$.  We know what the resulting ciphertext is.

Notice that this is a system of $n$ equations in $n^2+26$ unknowns.  Sadly, they are not linear equations; they are quadratic equations.  Nonetheless, there are techniques known for solving a system of quadratic equations.  We can expect that once we obtain a bit more than $n^2+26$ equations in $n^2+26$, there will be a unique solution.  There are techniques (e.g., relinearization) for computing this unique solution, when the number of equations is large enough.
For instance, if we have at least $(n^2+26)^2$ quadratic equations in $n^2+26$ unknowns, simple relinearization will find us the value of all of those unknowns using $O(n^{12})$ time.  This number of equations can be gathered after observing $(n^2+26)^2/n$ known plaintext-ciphertext pairs.

Getting even fancier

Hey, why stop there?  We can actually solve this purely with linear algebra.

Notice that we can rewrite the previous equation as

$$(x_W, x_I, x_N, x_K) = M^{-1} (17,5,20,2).$$

So now let's choose a slightly different set of unknowns: the unknowns are $x_A, x_B, \dots,x_Z$ (this part is the same as before) and the entries of $M^{-1}$, i.e., $(M^{-1})_{i,j}$ for each $i,j$ (this part is different).  There are still $n^2+26$ unknowns.

With this change, each known plaintext-ciphertext pair gives us $n$ linear equations in $n^2+26$ unknowns.  Now the equations are linear, so they are even easier
to solve.  Once we've obtained a bit more than $n^2+26$ equations, there should be a unique solution, and it can be found using Gaussian elimination in $O(n^6)$ time.  So, if we can gather a bit over $(n^2+26)/n$ known plaintext-ciphertext pairs, we can break the cipher using linear algebra.   Cool, eh?


Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?

This is basically the problem of finding a generator $g$ in a group $G$ of order $2^n-1$, where the factorization of $2^n-1$ is unknown.

Here is a pragmatic solution that should work fine in practice.  Use ECM factoring to find all small factors of $2^n-1$; in this way, find as many prime factors of $2^n-1$ as you can.

Now, pick $g$ uniformly at random.  For each known prime divisor $p$ of $2^n-1$, test that $g^{(2^n-1)/p} \ne 1$.  If this test holds for all known prime divisors $p$, then output $g$.  Otherwise, go back to the beginning and pick a new $g$.

Of course, you can only do this test for the prime divisors that you know of, so in principle, there is some risk that that you were unlucky and accepted a $g$ that isn't actually a generator (because $g^{(2^n-1)/q}=1$ for some prime divisor $q$ that you didn't know of).  The good news, though, is that the probability of this happening is exponentially small.

For instance, suppose we have found all prime divisors of 80 bits or less---something that ECM should easily be able to do.  Then there can be at most 37 additional prime divisors of $2^{2991}-1$.  The probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for a single one of them is $1/q$, i.e., $\le 1/2^{80}$.  Therefore, by a union bound, the probability that $g$ happens to satisfy $g^{(2^n-1)/q}=1$ for any of those 37 prime divisors is $\le 37/2^{80} \le 1/2^{74}$, which is so small it can be safely ignored for all cryptographic purposes.

This assumes there is a good practical reason to want to find a maximal-length LFSR of length exactly 2991, something that sounds pretty dubious to me.

In particular, the algorithm I have in mind for choosing a maximal-length LFSR on $n$ bits is as follows:

Choose a random feedback polynomial, uniformly at random from the set of all monic polynomials of degree $n$.  (As an optimization, make sure the constant term is $1$ and that the number of terms is odd; this will reduce the number of rejections in step 3.)
Choose a random non-zero starting state $S$.
Starting from $S$, step the LFSR forward $2^n-1$ times and check that you get back to $S$.  If not, it is not maximal-length; go back to step 1.
For each known prime divisor $p$ of $2^n-1$: Starting from $S$, step the LFSR forward $(2^n-1)/p$ steps and check that you do not get back to the starting state.  If you do get back to $S$, it is not maximal-length; go back to step 1.
Output the feedback polynomial; it is probably maximal-length.

This algorithm is making use of the following fact:

Theorem. If we randomly choose a feedback polynomial whose period divides $2^n-1$, then the probability that the period of the LFSR divides $(2^n-1)/q$ is $\le 1/q$.

Proof: Suppose $f(x)$ is a feedback polynomial for which the corresponding LFSR has period dividing $2^n-1$.  Then $f(x)$ is irreducible and $GF(2)[x]/(f(x))$ is a finite field of size $2^n$.  But there is only one, unique finite field of size $2^n$, so there is a field isomorphism between $GF(2)[x]/(f(x))$ and $GF(2^n)$, say $\varphi : GF(2)[x]/(f(x)) \to GF(2^n)$.

Now let's look at the next-state function for the LFSR with feedback polynomial $f(x)$.  It corresponds to multiplying by $x$ in $GF(2)[x]/(f(x))$.  Let $g=\varphi(x)$; applying $\varphi$, we see that the next-state function can also be thought of as multiplying by $g$ in the group $G=GF(2^n)^*$.  Note that the order of $g$ is equal to the period of the LFSR with feedback polynomial $f(x)$, since $x^k \equiv 1 \pmod{f(x)}$ iff $g^k=1$.  And, of course, $G$ has order $2^n-1$.

In this way, we obtain a bijection between feedback polynomials $f(x)$ and elements $g \in G$, where the period of the feedback polynomial is equal to the order of $g$.  The probability that a randomly chosen element $g \in G$ has period dividing $(2^n-1)/q$ is $\le 1/q$, from which the theorem follows (by applying $\varphi^{-1}$).


In order for a symmetric block cipher to be considered secure by modern standards, it has to be IND-CPA, that is indistinguishable from a random oracle under a chosen plain text attack. It also has to be IND-CCA and IND-CCA2, but IND-CPA is sufficient for it to also be secure under a known plain text attack.

Presuming TwoFish is still unbroken, it should consequently be safe to use the cipher text of a single known block as a key verifier. Or, to be more precise, storing that chk.blk file together with the encrypted file will not reveal significantly more information about the key.

However, there are other issues with your approach you might or might not already be aware of.

Firstly, do you really think it is feasible to get a user to enter a completely random 128 bit key using a GUI? Most application use pass phrases for such scenarios, and in such case your approach should be slightly different. For starters, where do you store the salt for the PBKDF? Will the key be used for encrypting more than one file? What information will the adversary be able to deduce just by looking at the cipher text of two files that are known to be encrypted using the same key?

Secondly, your approach is really only secure if the only threat is an adversary, without access to the key but with read only access to both the verifier and the actual cipher text, trying to guess the plain text contents corresponding to the cipher text. Your scheme is insufficient to prevent anything beyond that scenario.


Shanks's Babystep Giantstep Algorithm running time BigO

This is because, the elements of the full group conceptually end up in an $n\times n$ table, and the comparison of the column (giant step list) must be done on every row of length $n$ since the overlap of the lists is in a single unique row (which allows you to determine the answer you're looking for, e.g., discrete log uniquely). So you repeat the comparison at worst $n$ times, on average $(n+1)/2$ times until you find a collision.

The presentation on Wikipedia is quite good, their $m$ being your $n$ since your listsize $n$ is $\lceil \#G \rceil$, so roughly the square root of the size of the group.


In RSA, what is $P[x \notin \mathbb{Z}_N^*]$

With fgrieu's idea:

If we consider the generator working on a security parameter of $n$ bits (meaning resistance to $\mathcal O(2^n)$ computational effort), then each of the prime $p$ and $q$ must be at least (about) $n$-bit, otherwise trial division would factor the public modulus. Then, $N=p\,q$ with $p$ and $q$ distinct primes at least $2^n$ implies $P[x \notin \mathbb{Z}_N^*]=1-\frac{(p-1)(q-1)}{p\,q}<\frac1p+\frac1q<\frac2{2^n}$, that is $\mathcal O(2^{-n})$ which is negligible.


TL;DR: It's not secure, due to MITM attacks

Just because Bob receives r + 1, it doesn't mean that he is really talking to Alice. What if Mallory intercepted the key exchange of k and intercepts messages like so:

Mallory intercepts Bob's key exchange to Alice.
Bob and Mallory do the key exchange, Bob thinks that Mallory is Alice.
Mallory and Alice do the key exchange, Alice thinks that Mallory is Bob.
Bob sends r to Alice, but it's intercepted by Mallory.
Mallory forwards the message to Alice and Alice computes r + 1, sends this to Bob (inadvertently via Mallory)
Any data send from Bob to Alice will go via Mallory, without either party knowing.

This way it appears that Alice did r + 1, but Mallory can still read all messages between them. This is solved with authenticated encryption.

For the key exchange, use authenticated (EC)DHE, and for encryption either sign-then-encrypt or encrypt-then-mac for data integrity (though this is more important for stream ciphers, as editing the ciphertext will edit the plaintext correspondingly).

So for example, using ECDSA you could do SymmetricEncrypt(message + ECDSA(message)) for sending data, and for the key exchange, you could use ephemeral key pairs for the (EC)DHE, and use static key pairs to sign the ephemeral ones.

Either party then verifies the signatures of the data received in order to check that they are talking with the person that they think they are.

Here's a worked example, using ECC:

Assume Bob owns sPK1, and sSK1
Assume Alice owns sPK2, and sSK2

Where s means static, PK and SK standing for public key and private key respectively.

Bob creates ePK1, and eSK1
Alice creates ePK2, and eSK2

Where e stands for ephemeral.

Bob sends Alice ePK1, sSK1(ePK1). Bob sends Alice his ephemeral public key and a signature of it, proving Bob is the sender of the key.
Alice sends Bob ePK2, sSK2(ePK2).
Both parties receive and verify the others ephemeral public key. Both parties then combine their own ephemeral private key with the others ephemeral public key, yielding the same result either side. (In this example, this is done with EC Point Multiplication - ECDHE)
Alice and Bob then run the result through SHA(3)_256 for a 256 bit symmetric key.
All messages can be send like: AES-256-GCM(message, sSKn(message)), producing a ciphertext and MAC tag.

Side note: For symmetric encryption, AES-GCM is recommended, as it uses CTR as the underlying AES mode, which is fast as its paralellizable, and produces a MAC tag without the need for a second key to be derived / generated.

EDIT
In order to make sure the static keys (for signing) belong to who they should do, a CA would issue certificates to Alice and Bob, so the static keys are definitely correct, and not forged.


Factorization for special primes $P$, $Q$, and $R$

I don't think that we currently know how to exploit such structure.
The set-up immediately makes one think of Coppersmith's method for factoring RSA moduli with some bits of the factors known. This constructs a two-variable integer polynomial with an unusually small integer solution and uses lattice methods to find the solution.
In this case the polynomial $(10^cX+Y)(10^cY+Z)(10^cZ+X)-N$ has the solution $(X,Y,Z)=(p,q,r)$ with $p,q,r\approx N^{1/6}$. However this is a polynomial in three variables which is beyond our current knowledge of Coppersmith's method. The additional information that $p$, $q$ and $r$ are primes (and indeed that $P$, $Q$ and $R$ are primes) is not used by the methods, but I cannot see anyway to exploit this. If there are additional relationships between $p$, $q$ and $r$ that can eliminate on variable, more might be possible.
If you drop the polynomial-time requirement, then your example with $n=85$ can be solved in four hours for less than $100.


if a hash function has no known preimage attacks, does that mean there are no known attacks against using it in signatures?

Your idea of salting the signature to prevent the collision attack doesn't work, because your salted signing operation is a deterministic mathematical function, and the random choice of salt is only made at signature time, not at verification. Your signature algorithm has to be something like this. For a document $x$ and hash function $H$:

Hash the document: $h = H(x)$;
Generate a random salt $s$;
Apply the signature primitive function: $r = \mathrm{Sign}_{sk}^s(h)$;
Return $(s, r)$—the pair of the salt you picked and the signature primitive's result.  Because verifiers are going to need the value of $s$ you picked on this occasion to verify the signature.

For a document $y$ and a putative signature $(s, r)$, the verification algorithm has to work something like this:

Hash the document: $h = H(y)$;
Apply the verification primitive function: $\mathrm{Verify}_{pk}^s(r)$.

No random choices involved in verification. So if I can craft a pair of colliding documents and convince you to sign the "good" one for me, I can take the signature you produced and give it to somebody along with the "bad" document, and when they try to verify it it'll check out.


Salsa20 (and its variants) has 512 bit blocks, a 64-bit counter and a 64-bit nonce. So it can produce $2^{64}$ independent streams consisting of $512 \cdot 2^{64}$ bits each, for a total of $512 \cdot 2^{128}$ bits.


finding sha256 preimage or secp256k1 private key, which is harder?

To the best of our knowledge, finding a SHA-256 preimage is much harder than finding a secp256k1 private key; however both are current infeasible.

For SHA-256, the best known attack is to simply try lots of images until you stumble across one which hashes to the value you're looking for; that takes an expected $2^{256}$ hashes.

For Secp256k1, there are several known generic attacks (Big-Step-Little-Step, Pollard Rho) which reduces the expected complexity of finding the private key to about $2^{128}$ point additions.

Even though a point addition is considerably more expensive than computing a hash, it's not $2^{128}$ times as expensive, and so attacking secp256k1 is the easier option.

On the other hand, $2^{128}$ point additions is far more than is possible with current hardware (even if you had truly massive amounts of computational resources), and so it is safe.

On the third (gripping) hand, if the attacker can wait for a practical quantum computer to be built, that could recover the secp256k1 private key in a reasonable amount of time; no one knows when such a quantum computer will exist; it's likely not to be for the next decade or so.  However, if you need to be secure past then, you might want to rethink what you're doing.


Test the randomness of a random permutations, that was generated without Fisher-Yates?

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

No, you can't do that, but almost.  A pseudo/truly random sequence has multiple same values, repetitions and +/- runs of digits. Your solely incremental sequence will easily fail the test even when perfectly permuted, probably even fail something as simple as ent.
You test the shuffle algorithm by inference.

Generate a large file from something like /dev/urandom or the windows equivalent.

Sort it into order, either rising or falling.

Then permute that.

Then test for randomness.

The test hypothesis is that since the original sequence was cryptographically random with the correct $\chi^2$ distribution, a proper shuffle will not make it worse. And it will space out the values into random positions. So the standard randomness tests should then pass it.


What does it mean to be simultaneously hardcore?

Hard-core bits are related to one-way functions.

For some intuition on what hard-core bits are, consider a one-way function $f$. SInce it's a one-way function, it's hard to invert: that is, if I select a random $x$ in the function's domain and give you $f(x)$, you cannot find a $x'$ such that $f(x) = f(x')$ with non-negligible probability in probabilistic polynomial time (this is the definition of a one-way function).

So, intuitively, there is "something" about $x$ that is hidden from you in $f(x)$. If you knew everything about $x$ from $f(x)$, you would know what $x$ was. So, there is something that $f$ hides about its input. That something is a "hard-core predicate".

A hard-core predicate is itself a function. Let's say we have a hard-core predicate for $f$ called $\mathsf{hc}$. Since it's a predicate, $\mathsf{hc}$ returns exactly one bit.  So, given $f(x)$, you cannot determine the value of $\mathsf{hc}(x)$ with non-negligible probability (over $1/2$, which you can always get by guessing) in probabilistic polynomial time. In essence, $\mathsf{hc}(x)$ represents something about $x$ that you do not know given $f(x)$ — that is, $\mathsf{hc}$ is a bit related to the input that $f$ hides from you. Another way of looking at it is that $\mathsf{hc}(x)$ is indistinguishable from random (in PPT and all that business). To see this, consider if you were given $f(x)$ and $\mathsf{hc}(x)$. Since you cannot compute $\mathsf{hc}(x)$ from $f(x)$, by definition, you should not be able to distinguish it from a random bit.

Note that a hard-core predicate is a single bit. Instead of a single bit, the paper wishes to talk about multiple different bits each being hard-core simultaneously. So, simultaneously-hardcore bits are a natural extension of hard-core predicates into strings that are multiple bits in length. To be explicit, let $h$ be a hard-core function for $f$. Then, given $f(x)$ for a random $x$ in $f$'s domain, an adversary cannot compute $h(x)$ in PPT. The paper you've linked frames $h$ as being indistinguishable from random, which is equivalent.


How to reduce Computational Diffie–Hellman problem and Decisional Diffie–Hellman problem to Discrete logarithm problem

A reduction here would mean showing that if you had an efficient algorithm A to solve the discrete logarithm problem, then you could use that to construct an efficient algorithm B solving the computational Diffie-Hellman problem. (For starters, assume A always works and construct B that always works. For full credit, given A that works with some probability [over a uniform input], construct a B that works with the same probability [over uniform inputs].)

If you understand what the discrete logarithm and computational Diffie-Hellman problems are, a reduction should be immediate.