There are issues in the question, some serious. In reading order:

ECIES(Bob's public key, M || ECDSA(Alice's static private key, M)) is sign-then-encrypt, which is perfectly fine. But count the signatures, there's only one (ECIES does not sign). Therefore this is not "sign-encrypt-sign" as described elsewhere.
If we wanted to make sign-then-encrypt-then-sign, just replace the resulting ECIES result X by X || ECDSA(Alice's static private key, X). But take care that the final signature leaks who the signer is, when sign-then-encrypt keeps it confidential to all but the holder of the decryption private key.
The "message for sending" is said to be [Alice's ephemeral public key, Alice's static public key, ciphertext, Mac's tag]. That's not matching the form of an ECIES cryptogram per SEC 1 Ver. 2.0, 5.1.3 Action 9, where Alice's static public key is not part of the output. Strictly stick to ECIES, or use another name. The ECIES result is [Alice's ephemeral public key || Ciphertext || Mac's tag]. If Alice's identity or public key or certificate is needed, it can be part of the message itself.
What's hashed in Kenc || Kmac = KDF(SK) should be the (bytetring representation of the) $x$ coordinate of SK (per 5.1.3 Action 4), without the $y$ coordinate or parity bit. I would note Kenc || Kmac = KDF(SKx) to make the distinction explicit.
In Ciphertext = Encrypt(Message, Kenc) it is not stated what Message is. If that's M, then M is not signed. That Message must be M || ECDSA(Alice's static private key, M) in order to match 1. It is critical that the ECDSA signature is encrypted, else confidentiality of the message is largely jeopardized (it becomes trivial to check a guess, e.g. of a coin toss, name, card number..)
ECDSA's tag = ECDSA(Ciphertext, Alice static private key) comes as a surprise at this point, since Ciphertext is currently ECIES's internal symmetric ciphertext (denoted $EM$ in 5.1.3 Action 7), and not accessible externally from the ECIES black box. That makes reuse of proper ECIES code hairy: it's result must be parsed to extract the Ciphertext portion (as an aside, the question's notation is inconsistent on order of parameters, and use of possessive for asymmetric keys).
HMAC's tag = MAC(Alice's static public key || Ciphertext || ECDSA's tag, Kmac) deviates from ECIES (5.1.3 Action 8). It should be replaced by HMAC's tag = MAC(Ciphertext, Kmac) (or HMAC's tag = MAC(Ciphertext || Sharedinfo2, Kmac) where Sharedinfo2 could be some externally agreed-upon bytestring; that could be Alice's static public key, but I do not see the point).
The order is wrong in "Alice make ECDSA's tag first and after that make MAC's tag based on Alice's static public key, Ciphertext, and ECDSA's tag". For sign-then-encrypt that should be: Alice

makes ECDSA's signature/tag of M (this is typically first, but is independent of the next step and thus order is immaterial);
draws an ephemeral asymmetric key pair, multiplies Bob's public key by the ephemeral private key and forgets the later, extracts the $x$ coordinate of the result, derives from that the symmetric encryption and MAC keys used in the next two steps;
then symmetrically enciphers the concatenation of M and that signature/tag (with said concatenation denoted Message in the question), yielding ECIES's internal symmetric ciphertext (denoted Ciphertext in the question and $EM$ in 5.1.3 Action 7);
then makes MAC's tag based on Ciphertext, and optionally Sharedinfo2;
then concatenates the ephemeral asymmetric public key, Ciphertext, and MAC (not the optional Sharedinfo2) into the ECIES result.

|Alice's ephemeral public key, Alice's static public key, Ciphertext, ECDSA's tag, MAC's tag| is wrong if we are making ECIES, as explained in 2. That should be [Alice's ephemeral public key || Ciphertext || HMAC's tag], per 5.1.3 Action 9 (with the necessary conversion from public key to bytestring implicit), yielding the output of ECIES, which is ECIES(Bob's public key, M || ECDSA(Alice's static private key, M)) of 1.
I fail to parse "this is secure as sign-encrypt-sign". Leaving aside "secure as", it does not hold. With the changes indicated, it is made sign-then-encrypt, which is secure. Without the change, this is encrypt-then-sign-the-symmetric-part-of-the-ciphertext-and-include-that-in-the-MACed-data, this is not ECIES, and while I do not immediately see any attack, that's not a valid indication of security.
"I am not sure that MAC's tag is necessary in this scheme": the MAC is necessary at least for the encryption to be what's named ECIES, and to benefit of its security argument. It also serves as a protection against poor implementations on the receiving side.
In ECDSA's tag = ECDSA(Alice's public key || Ciphertext || Kmac, Alice's static private key), again I do not see why Alice's public key is part of what's signed; and Ciphertext is an internal variable of ECIES, which is dubious.
A reading of the question is that Alice reuses the same private key for ECDSA signature and ECIES decryption, which conceivably could have security implication. Formally, it makes ECIES's security argument invalid, and is explicitly against the ECDSA specification in FIPS 186-4:

  ECDSA keys shall not be used for any other purpose

Summary: The alternative proposed essentially replaces ECIES's MAC with an ECDSA signature (with ECIES's MAC key entering the data signed), and makes a number of other variations of the standard ECIES (at least, including the public key, and hashing the whole ephemeral public key rather than its $x$ coordinate). That's functionally encrypt-then-sign, with something that is not exactly ECIES and does not benefit from its security proof (though I see no attack). Beware however than any encrypt-then-sign reveals the identity of the signer, when the question started with the equation of sign-then-encrypt with ECIES, which demonstrably keeps the identity of the signer confidential until decryption. The question states that it performs sign-encrypt-sign, when it appears that it does not (unless Message is assumed to be M || ECDSA(Alice's static private key, M) ). The question does not state use of separate key pairs for signature and encryption, as required by standards and the security argument of ECDSA and ECIES.

Recommendations:

First decide if functionally the need is to have the signer's identity apparent to anyone by examination of the final cryptogram, or revealed only to the holder of the deciphering private key. For asymmetric/hybrid encryption and signature:

if the signer's identity is to be kept secret, or if in doubt, sign-then-encrypt;
if the signer's identity is to be apparent, encrypt-then-sign (sign-then-encrypt-then-sign also works here, but is not necessary for security when the next two recommendations are applied; it is however sometime justified, for example if cryptograms normally carrying the signer's ID must be transformable into anonymous ones by merely stripping the external signature, but should remain signed and non-repudiable after decryption).

In the above, encrypt should be precisely ECIES, including its ephemeral key generation, symmetric encryption, MAC, and concatenation to yield the result.
In the above, when using ECDSA, sign should be computing the ECDSA signature (including at least one hash step of the whole input) then adding the signature to the input (that can be either by appending or pretending it, as long as it can be unambiguously extracted on verification without risk of triggering implementation bugs).
If the identity, public key, or certificate of the sender needs to be included, add it immediately after or immediately before performing one signing step (or both); that can be either by appending or pretending the information, as long as it can be unambiguously extracted without risk of triggering implementation bugs.
When possible: one purpose, one key.

Nothing in this answer should be construed as an endorsement of anything by anyone.


Using a round function intended for an SP network in a Feistel network?

There is only one requirement for a Feistel round function and that is a good diffusion and confusion. It is not required for the round function to be invertible in a Feistel network. You can use (as asked) a secure mini SPN or even a hash function (Sha3...)

  it doubles the block size, so the number of rounds can be doubled at no perf cost

If you meant to use that $n$-bit secure SPN (such as Rijndael) in your Feistel $2n$-block-cipher, then you will have to make a sufficient number of rounds (at least 4 to get full diffusion : see p. 41). Therefore compared to a parallel CTR encryption method just using that $n$-SPN, you are 2 times slower and you don't really have a gain in security in term of key as the space is the same.


Is OTP useful in modern electronic communication?

The OTP is more a theoretical construction than a real world construction. The OTP suffers from three core problems:

Key Generation.
Key Distribution.
Key Destruction.

Let's deal with each one in turn.

Key Generation

Key generation is surprisingly difficult. In order to get the full security proof for the OTP, you need to each bit to be independent of every other bit and for there to be no bias whatsoever in the output.

Now practically every hardware RNG you're going to get does not fufil this in practice. They almost always run the bits through a hash function or some sort of entropy extraction routine. However, these routines do not carry a security proof that they preserve the underlying independent non-bias nature of the bits passed to them.

It's quite possible that if you the entropy extraction routine over enough bits, that a very small bias would be observed. However, any such bias, no matter how small would destroy the OTP security proof.

So you need to design your own RNG using only de-biasing techniques that maintain the security proof. Worse, you need to build an RNG with no detectable bias whatsoever over gigabits of output.

Key Distribution

Key distribution is a pain because the key has to be as long as the message. This immediately raises the question of why bother with encryption if you already have a secure channel of transmitting the key. Even with this massive key you haven't authenticated the cipher-text! You need provisions for that too.

This limits the OTP to scenarios where you want to time-shift a secure channel. It works okay in scenarios like the following. If Alice lives in Hong Kong and Bob lives in New York, they can meet twice a year and exchange a gigabyte or two of pad and be on their way.

Even if you're using QKD you've just moved the problem elsewhere. The problem now moves from a key distribution problem to an engineering problem. You've got to make a QKD device that is 100% reliable, doesn't have any side channel attacks, and is not susceptible to induced errors. Such as slightly overpowering/underpowering device to get duplicate photons, shinning a laser at the device to subtly break it or some other error inducing attack.

You've got many of the same problems of hardware quality as you had with the PRG. Good luck with that!

Key Destruction

Once you've used the key you have to make sure it is properly destroyed in both places. This is again more tricky than it seems at first.

If you don't do this properly and you use the key-stream twice, you have no security at all. If the program that manages the pad for you suffers some sort of error and fails to delete the used portion of the pad then re-use becomes quite likely.

Worse, because the pad is the same length as the message there's quite a lot of key stream to leak. This can leak in a number of ways. Parts of the key stream might have been paged to disk, for example, during encryption/decryption process.

An attacker could then decipher parts of your ciphertext by simply XORing bytes from your recovered hard-drive against the ciphertext.

Conclusion

The reason that the OTP isn't really fielded is that despite its strong security proof, the practical considerations around it actually render it insecure.

This is actually quite common in cryptography. Things with strong security proofs tend to be unworkable.

For every section of my reply, there is a documented case where precisely the problem I've raised has led to OTP messages being compromised.

OTPs are really hard to use properly and are typically less secure overall than a conventional scheme.

Small secrets, by virtue of them being small, are less likely to be leaked, easier to generate, easier to destroy and easier to transmit. All of these properties make them more secure.


Is this one safe

That's always a relative term. One can say for certain that breaking this encryption will be no harder than bruteforcing  the first block of 48 bytes, which is more than doable with a few thousand dollars worth of servers.

Worst case, your first block is made up of a bunch of zeroes, and XOR-ing the key into that will make the first bytes of the ciphertext the key in plaintext, because x ⊕ 0 = x. Hashing those bytes to find the key for the rest of the message is trivial. Likewise, if the format is predictable (most filetypes start with a pre-determined header), recovering the key will be trivial. If any part of the plaintext is known, al subsequent bytes can be recovered this way.

Also, it might be identifiable;
Here's a nice paper on stacking hash functions
It basically states that your scheme is also distinguishable. That is, given an output of the length of SHA265, it is computationally cheap to figure out if it's the hash of the previous hash.

But why roll your own? There are multiple cryptographically secure psuedorandom number generators that have stood years of attack and are probably much faster in performance.


Is this scheme correct ? What should I review/read to make it correct ?

One obvious issue is that the client is willing to decrypt arbitrary ciphertexts with its private key.  Hence, if it uses the private key for any other purpose, well, it's insecure.

  In the article from Digital Ocean you can find that client doesn't send raw data back to server but gets md5 of it and sends only md5. Why so ?

Well, that's to prevent someone from using the client as a decryption Oracle; they still could use it as a "decrypt-and-MD5" Oracle, but that's not nearly as bad.

Personally, I would make three changes:

Replace MD5 with a modern hash (for example, SHA-256) - while MD5 is probably perfectly safe in this use, it has shown enough weaknesses that steering clear is probably the wiser option.
I'd replace the deterministic hash with a randomized one.  That is, I'd have the client pick a random string "r", and return the pair $r, SHA256( r || decryption )$.  That way, the client can't be used as a "decrypt-and-SHA256" oracle either.
On decryption failure, I'd make sure I'd pick a random decryption, and return the pair $r, SHA256( r || random )$ - there's no reason to give people a "is this a valid ciphertext" Oracle.

Actually, personally I'd probably replace this entire thing with a Schnorr proof of knowledge, but I rather assumed you didn't want to wholesale replace everything...


"Secure" is not a binary, black-and-white thing.  Instead, it's about risk management.  Instead of asking whether something is secure, it's better to ask whether it is "secure enough for such-and-such purpose". On the one hand, 1024-bit keys are uncomfortably close to what can be cracked, given lots of computational resources.  On the other hand, for casual use, it's probably fine, and there's no need to go through a painful exercise to replace your key.  But if you're generating new keys, these days it'd be a good call to use a 2048 bit key.

On your third question, someone who recovers your 1024-bit private signing key today would not be able to decrypt past ciphertexts, but they would be able to mount man-in-the-middle attacks on you in the future (which would let them decrypt information that anyone encrypts to you in the future), assuming they are willing to mount active attacks.


If username was treated as the password should be, like salad (salt, pepper, hash, toss / en Français saler, poivrer, hacher, touiller), then

If there is salt, it can't be directly inferred from username. And the alternatives are getting rid of salt (allowing pre-computation and rainbow tables), or test all users (which is going to be prohibitively costly for more than a few users).
If the username doubles as storage of the email, then we can no longer readily send an email to all users. And if we can send such general email, there is the risk that likely usernames can be inferred from email.
Username is even more guessable than password, and (unless treated as an extension of password) if can be found even more easily.

For these reasons, it is typically functionally unacceptable to apply a password hash to username.


CPA-secure of $\Pi$ implies CPA-security of $\Pi||\Pi||\ldots||\Pi$

The proof of (1) is not given in the chapter on symmetric encryption since it requires knowing the hybrid proof technique that is taught in Chapter 7. However, the argument is proven in Chapter 11 for the asymmetric case (see Theorem 11.6 and the proof on page 383). Essentially the same proof holds for the symmetric case as well (except that instead of the reduction $\mathcal{A}'$ on page 385 computing the plaintexts itself for $j<i$ and $j>i$ in steps 2(a) and 2(c) respectively, it asks its encryption oracle to do it and uses the responses).

Regarding CCA security, the proof of multiple encryptions indeed does go through as well. However, unlike CPA security, it does not imply that you can concatenate ciphertexts into one ciphertext. That is, you can encrypt multiple messages, but you cannot encrypt longer messages by concatenating. The reason is that if you encrypt a long message by concatenating ciphertexts (and you call this the new ciphertext) then the attacker can drop the last sub-ciphertext and ask for decryption (it is allowed to ask for decryption since this is not the same ciphertext received).


First off, you are still missing some information. What encryption mode will you be using? What key are you using for the HMAC?

That said, my answer is no. This isn't a good way. The reason being is that unless you are a professional cryptographer, you shouldn't design your own cryptographic protocols/methods. There are too many ways to introduce vulnerabilities in both the design and the implementation that it is risky. Stick with published standards that the cryptographic community has been able to look at and analyze. You can encrypt files using PGP or the open source implementation GnuPG.


Subscript R notation for the finite fields

To quote yyyyyyy from the comments:

  The $_R$ has nothing to do with the field — it is associated to $\in$!
  To quote your first link: "For a set $S$, by $a\in_R S$, we mean that
  $a$ is randomly chosen from $S$."

and to quote SEJPM from the comments:

  If $p\in \mathbb P$ (with $\mathbb P$ being the set of all primes)
  then the notations $GF(p);\mathbb Z_p;\mathbb Z/p\mathbb Z;\mathbb
 F_p$ are equivalent.


The straight-forward way to do this is:

Convert the ASCII string into an array of bytes.
Convert that byte array into a large integer. For that you need a library with support for arbitrary large integers (e.g. BigInteger)
Endianness does not matter for this.
For encryption, the library should already offer some modular exponentiation method, because otherwise you will have to write square-and-multiply yourself, where you apply the modulus after every step.
Decryption is the same as encryption, it's just modular exponentiation again.

Of course this is just for this basic exercise. In an actuall application, you definately need:

A proper padding scheme, e.g. RSA-OAEP
You usually don't encrypt the message directly. Instead, hybrid encryption is used in all cases, so that it doesn't matter how long the message is.
Follow the standards, e.g. PKC#1, section 4 for the data conversion from integers to byte strings (thanks to @MaartenBodewes for pointing that out)
And to be honest: You should just use an implementation of RSA (and other encryption schemes) provided by a cryptographic library.


The logic of preferring PBKDF2 over iterative SHA2

I think you are overstating the complexity of PBKDF2, and also, not matching it feature-wise with your alternative.  Let's dispatch the latter first: as gammatester's comment mentioned, PBKDF2 supports variable output size.  If you built that into your proposal, it would become more complex.

Once we control for that, PBKDF2 is hardly more complex than your iterated SHA-2.  The heart of PBKDF2 is the iterated application of a pseudorandom function (PRF), with the password as its secret key:

$$
F(\mathrm{Password}, \mathrm{Salt}, c, i) = U_1 \oplus U_2 \oplus \dots \oplus U_c
$$

...where:

$$
\begin{align}
U_1 &= PRF(\mathrm{Password}, \mathrm{Salt}\, \|\, \mathrm{INT\_32\_BE}(i)) \\
U_2 &= PRF(\mathrm{Password}, U_1) \\
& \vdots \\
U_c &= PRF(\mathrm{Password}, U_{c-1})
\end{align}
$$

The way that the sequence of values $U_1, \dots, U_c$ is computed is very similar to the way you're proposing to iterate SHA-256, except with the addition that each iteration uses the password as its secret key.  While this isn't necessarily a groundbreaking improvement, it does mean that an attacker who sees an intermediate $U_i$ is not able to pick up from there and compute the rest of the sequence unless they guess the password.  Whereas with your construction, any intermediate value of iteration is sufficient to compute all succeeding ones.

The second difference is that the final value of $F$ is not just $U_c$, but rather the XOR of all the values in the sequence.  This Q&A goes into the motivation of that, and the answers offer several alternative takes.

The third difference is the choice of a PRF as the primitive instead of a hash function like you propose.  This is just conceptually sensible given that we're talking about a scenario where there is a password that plays the role of a secret key; all that PBKDF2 says is that you should iterate a secret-keyed function, using the password as the secret key, and allows for any such choice of function.  The common choice of PRF is HMAC-SHA1, which does make PBKDF2 look a bit complicated if you're missing the observation that it treats its PRF as a black box—it's not concerned at all with HMAC's internal structure.


Why can we ignore $y$ when using the extended Euclidean algorithm to calculate an RSA decryption exponent?

By definition of the notation $a\equiv b\pmod c$, this means $a-b$ is a multiple of $c>0$. Therefore, $17\cdot-7\equiv1\pmod{\varphi(N)}$ means that $(17\cdot-7)-1$ is a multiple of $\varphi(N)$.

Thus the answer to: "how come $17\cdot-7\equiv1\pmod{\varphi(N)}$" is just: because $(17\cdot-7)-1$ is $-120$, which is a multiple of $\varphi(N)=40$.

Addition trying to answer the question in the title: when you found $x$ and $y$ such that $e\cdot x+\varphi(N)\cdot y=1$ using the extended Euclidean algorithm, that implies $e\cdot x-1$ is a multiple of $\varphi(N)$, thus you have an $x$ with $e\cdot x\equiv1\pmod\varphi(N)$, irrespective of $y$.

Now how does it relate to choosing the private exponent in RSA?

Well you can use $d=-7$, it will work, but numerically computing $x^d\bmod N$ will require computing a modular inverse modulo $N$, and raising to the power $7$ modulo $N$ (in any order).

Or you can use that $-7\equiv33\pmod{\varphi(N)}$ and select $d=33$, obtained as $-7+40$; that would be a common $d$. More generally, any $d=x+k\cdot\varphi(N)$ will do from a mathematical standpoint (yet it is most common to restrict to $1<d<N$).

Or you can use $d=13$, which is the smallest positive private exponent possible, obtained by inverting $e$ modulo $\lambda(N)=\operatorname{lcm}(p-1,q-1)=20$ using the extended Euclidian algorithm and keeping the smallest positive representative; that's also common, and can save a little work: raising to power $13$ can be done with $5$ multiplications, rather than $6$ multiplications for power $33$.


Regex searchable word list for space-less monoalphabetic substitution

The simple shift sounds like a Ceasar Cipher.

The simplest crack for this is probably frequency analysis. The most common letter in the English language is E. Count your letters, and guess your shift based on that.

If you want to make it better, you could get the X most common letters in your cipher, calculate what you think the shift is, and compare that to known letter frequencies in English, like ETAOIN SHDRLU. The frequency guess that differs the least (with the lowest edit distance) is probably your candidate.

You can also judge how good the resulting text is by using bigram and trigram frequency tests.

You may also find some of the methods described in these books helpful:
http://www.nsa.gov/public_info/declass/military_cryptanalysis.shtml

UPDATE: It sounds like what you're actually trying to do is detect when you've decoded your ciphertext. You don't necessarily need to match the words in a dictionary to do that.

The above mentioned methods should work quite well, especially if you start using bigram and trigram frequency.

If you get to the point where you need a more sophisticated method to detect when your text is decrypted, I suggest asking on Stack Overflow, and also telling them what your current approach is, and why it's not working for you.

Note that regular expressions are not useful for what you have in mind. A Markov chain would be a much better tool, especially since it can be used to predict where a word has ended and a new word has started.


Pseudorandom function outputting a field element VS pseudorandom function outputting a string

$F_p$ has a one to one mapping with the set of integers $[0, p)$. $\{0, 1\}^n$ has a one to one mapping with the set of integers $[0, 2^n)$. Their sizes are respectively $p$ and $2^n$.

Both $F_p$ and $\{0, 1\}^n$ are common
(co)domains chosen due to nice properties in either efficiency, easy analysis or ease of use in the greater scheme of things. But to analyse a PRF these are fundamentally the same.

You are mapping one set to another. This mapping must be indistinguishable from a random oracle, within security bounds. For the analysis the only fundamental property are the sizes and distributions of the sets you're mapping, not what those sets actually contain.

The birthday attack on secure PRFs roughly dictates that you'll find a collision after $\sqrt{s}$ random outputs, where $s$ is the size of the codomain. So for your question respectively $\sqrt{p}$ and $2^{n/2}$.


Signing a message to make sure that it will not be tampered with when forwarded, without trusting the receivers?

I see this as a mixture of easy and impossible.  A standard digital signature will work to verify the contents, as long as the document+signature is sent to person 1 (or whoever wants to check the document)

The impossible part comes if you only want person 1 to only have the signature and not the document.  Even if person 1 keeps a copy of every signature, Person 2 can send a tampered document with the original signature.  Person 3 would know the document has been tampered, but if 3 wants to be part of the deception they can just send the original signature to person 1.


Security implications of slow-by-design hashes on relative security vs. hash size

You CAN get away with using less memory if the hash is expensive. However, that does not mean you should, and it would rarely make any sense.

So why would you try to "get away with" using smaller hash functions? You could save some storage space, which is definitely appealing. However memory is cheap, and using larger hash functions adds more security, it also has the benefit of being more future proof than a smaller hash.

But in the end, it depends entirely on your data. There are many uses for hash functions, and using a slow hash with ASIC preventative measures for a checksum would be silly. However, if you are storing passwords in a secure database, you would want to add a salt and/or pepper and use an ASIC-safe slow hash.

I also want to address a couple misconceptions:

Your example does not make much sense. A rainbow table is a set of pre-computed hash chains for some expected plaintexts. This means that you could compute a rainbow table for a 1024 bit function for a small factor more memory than a 128 bit function. And if you add a salt to all of your data, it becomes infeasible to use a rainbow table at all.
You say "any partial break of the algorithm is more likely to be devastating" Why is this? A flaw in a hash algorithm is a flaw. Assuming the search space is reduced, the more bits you have the safer you are; however this does not necessarily mean any flaw is "devastating", a flaw is nearly as likely to be devastating as in a larger hash function.


Differential Privacy of the Laplace mechanism with non-deterministic function

The Laplace mechanism only works for deterministic $f$, because the notion of "sensitivity" (the $\Delta f$ in the formulas above) isn't well-defined for random functions. $\Delta f$ is the maximum difference between $f(x)$ and $f(y)$, for neighboring $x$ and $f$. If $f$ is a random function, then that notion of "difference" becomes much more complicated to capture, so in general, you simply assume that $f$ is deterministic.
To extend this to the case where $f$ is random, you could define $\Delta f$ to be the maximum difference between a possible output of $f(x)$ and a possible output of $f(y)$, for all possible values of the random bits used by $f$. That would still allow you to say $\frac{||f(x)-f(y)||}{\Delta f}\le1$. But that doesn't work if that value is unbounded (for example, if $f$ implicitly adds Gaussian noise to the result of the computation), and that's a loose approximation in general; so it's pretty much never done.


MD5 - What happens if message is exactly 64bit block size message?

Padding can be expressed as follows:

Append a bit of value 1.
Append between 0 and 511 bits of value 0. The number of bits to append here must be such that the total length after padding is a multiple of 512.
Append the encoding of the length of the message (not counting the padding bits). That encoding always has size exactly 64 bits.

So, if your input has size 448 bits, then:

After adding the bit of value 1, you get a total length of 449 bits.
You will need to add exactly 511 bits of value 0. Otherwise, the final length won't be a multiple of 512. With these extra 511 bits, length is now 960 bits.
With the length encoding, size is now 960 + 64 = 1024, which is indeed a multiple of 512.

The padded input is then split into blocks of 512 bits, processed in due order.

The sentence in the RFC about a length exactly equal to 448 is meant to clarify the process, in that the extra bit of value 1 is always added. That bit is not optional.

Formally, MD5 takes as input a sequence of bits. However, in most situations, we only hash sequences of bytes. In other words, the input length will always be a multiple of 8. The padding process, when expressed with bytes, becomes:

Append a byte of value 0x80.
Append between 0 and 63 bytes of value 0x00. The number of bytes to append here must be such that the total length (in bytes) after padding is a multiple of 64.
Append the encoding of the length of the message (not counting the padding bytes). That encoding always has size exactly 8 bytes. The length is expressed in bits, i.e. it is eight times larger than the length in bytes.

The padded input is then split into blocks of 64 bytes, processed in due order.

This padding procedure is exactly the same as the one defined for bits; it is just expressed here from a byte-oriented viewpoint.


Pen-and-paper one-way function for externally-anonymous survey

There are techniques for doing online surveys on sensitive subjects.  They don't follow the approach you outlined, but here's a sketch of how they work.

Suppose we want to survey people to determine how many people have ever seriously considered suicide (say), but we suspect many people might be unwilling to answer honestly because of the stigma associated with answering yes.  Here's what we do.  We give the respondent an ordinary 6-sided die.  We ask the respondent to secretly roll the die (where the enumerator can't see it).  If the die comes up 1-4, we ask them to answer honestly; if it comes up 5 or 6, we ask them to reverse their answer (tell us the opposite of their true answer).

This provides plausible deniability for respondents.  If they answer "yes", it might be that they have seriously considered suicide; or it might just be that they got a 5 or 6.

It also gives us a way to estimate the fraction of people who have seriously considered suicide.  Suppose a fraction $q$ of respondents answer yes.  Then we can estimate that about $p=3q-1$ of the population of respondents have seriously considered suicide.  We can't identify any specific individual who did or didn't seriously consider suicide, because we only have a noisy view of the truth for any one individual, but we can still compute aggregate statistics.

(Do you see why the formula $p=3q-1$ works?  Suppose a fraction $p$ of the population has seriously considered suicide.  What fraction of people will answer yes, given this procedure?  Well, of the $p$ fraction who have seriously considered suicide, $4/6$ of them will answer yes; of the $1-p$ fraction who have not seriously considered suicide, $2/6$ of them will answer yes; so in total, $4p/6 + 2(1-p)/6$ of the population will answer yes.  A bit of simplification shows that this is equal to $(p+1)/3$.  Of course, we cannot observe $p$ directly, but we can observe this fraction; this fraction is exactly $q$.  So, setting $q=(p+1)/3$ and solving for $p$, we find that
$p=3q-1$.)


I can't give an example illustrating why leakage must be non-negligible for the utility of the mechanism, but I can give a proof of why leakage must be non-negligible for the utility of the mechanism.

Let $\;\; U \: = \: \left\{\langle D,D'\rangle : D,D' \text{ differ in one element}\right\} \;\;\;$.

By the triangle inequality, for all $D$ and $D'$, for all $S$,

$|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|$
$\leq$
number_of_elements $\cdot \operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\}$

If number_of_elements is polynomial and $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})\:$ is negligible, then

for all $D$ and $D'$, for all $S$, $\:|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|\:$ is negligible.

If number_of_elements is polynomial and

$\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible, then $A$ is statistically close to being independent of $D$.

Therefore, if $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible then the mechanism is not useful.


Why use a date-dependent substring of a pre-shared key instead of just the key?

It is definitely not an industry standard solution. It looks like what the system designer wants to enforce is changing the key everyday. Essentially, it is a naive (and not secure) session key scheme such that each session lasts a day.

The idea of using session key is quite common in secure communication. Cryptanalysis becomes easier if the attacker can have more ciphertexts encrypted with a specific key. Thus often we want to limit the amount of data encrypted under a particular key. This is done by key exchange/establishment protocols that generate random, short-lived keys and secure distribute to sender/receiver. The random keys are called session keys because they are only used in one session. The security of the distribution usually requires e.g. a pre-shared key or asymmetric keys.

Going back to the scheme you mentioned, it is not secure because of many design flaws, e.g. the session keys are not randomly generated, are related to the pre-shared key, and can be re-used. It does not provide much additional security, e.g. if the attacker possess the pre-shared key, he can enumerate the session keys without much effort. It may even weaken the security of the system.


Does there exist an agreeable algorithm to substitute XOR function in Shamir's no Key Protocol?

I don't remember reading Shamir's original proposal, but I would strongly suspect that he never endorsed the use of XOR in the protocol; if he mentioned it at all, it was as an illustration.

Instead, here is what is commonly referred to as Shamir's three pass protocol:

Alice and Bob agree on a large prime $p$ (larger than any message Alice wants to send)
Alice wants to send Bob the message $M$
Alice selects a random $a$ (relatively prime to $p-1$)
She computes $M^a \bmod p$ and sends it to Bob
Bob selects a random $b$ (relatively prime to $p-1$)
Bob computes $(M^a \bmod p)^b \bmod p = M^{ab} \bmod p$ and sends it to Alice
Alice computes $(M^{ab} \bmod p)^{a^{-1} \bmod p-1} \bmod p = M^b \bmod p$ and sends it to Bob
Bob computes $(M^b \bmod p)^{b^{-1} \bmod p-1} \bmod p = M$

That is, instead of using XOR, they perform modular exponentiation modulo a prime; with this, recovering $M$ from $M^a, M^b, M^{ab}$ is essentially the computational Diffie-Hellman problem, that is, believed hard given appropriate parameters.


Any Idea on this identification scheme's problem?

Well, here's one obvious attack:

Eve wants to impersonate Alice.
Bob wants Eve to prove that she's Alice.  Bob gives a value $x$ to Eve
Eve turns around, and asks Alice to prove that she (Alice) is Alice.  Eve gives $x$ to Alice
Alice gives the value $y$ to Eve
Eve then gives the value $y$ to Bob

Of course, that's not the attack that Stinson is looking for...

For the attack that Stinson is thinking of, here's a hint:

For a random quadratic residue $x$, how many values of $y$ are there s.t. $y^2 = x$?
Suppose Bob picks a random value $y$ and computes $x = y^2 \bmod n$ and gives it to Alice, what is the probability that Alice will compute a $y'$ that's neither $y$ nor $n-y$?
If Bob knows $y$ and $y'$, what could he do with those values?  Hint: consider $y^2 - y'^2 = (y + y')(y - y')$


Attacks against RC4 when index $i$ is unknown

The most efficient way I can think of (not that it's all that practical) is to take a very long section of the keystream (think a Gigabyte+), and check it against the known RC4 digraph statistics; some of these biases (actually, most of them) depend on the value of i, and so the value of i that is correct will show up as more strongly biased than incorrect values.

The practical downside is that it requires a lot of keystream; on the other hand, it is computationally efficient (and works even if the RC4 key is large)


What happens if $\gcd(m,N) \neq 1$?

Actually, RSA works just fine; we have $((m^e)^d) \equiv m \pmod N$ in all cases, includes ones which $m$ and $N$ are not relatively prime.

What is an issue is if someone notices that $\gcd(m, N) \neq 1$.  If that is the case (and $m \ne 0$), then $\gcd(m, N)$ is a nontrivial factor of $N$, that is, either $p$ and $q$, and so that rather leaks the factorization of $N$.

Now, the probability of guessing $m$ that is not relatively prime to $N$ is astronomically small for the sizes of $N$ we use in practice, and so we don't worry about it.


What if the p and q used in keys generation of Pailler cryptosystem are composite?

For starters: Paillier and RSA are based on very similar assumptions, and both systems would be broken immediately by an algorithm to factor large composites. Additionally, knowing $\phi(n)$ or $\lambda(n)$ is quite essential to both systems, because the trapdoor for decryption is based on that.

As you can see, the relation to RSA is quite close, and thus the following topics on this site are very relevant:

RSA with probable primes
RSA with composite numbers

Now let's translate that to Paillier:

First off, in most cases if you use $q-1$ and $q$ is not prime, then the entire encryption/decryption will not work, because actually $\lambda(q)\neq p-1$ (with the Carmichael function $\lambda$). This means, that $D(E(x)) = x$ with the encryption $E$ and decryption $D$ is a primality test itself for both primes $p$ and $q$.

But let's assume, that you happen to find numbers $p$ and $q$ with $n = pq=abc$, where $a,b,c> 1$. In the key generation process you calculate $\lambda = lcm(p-1, q-1)$, which is just the Carmichael function for a proper $n=pq$. In order for the normal encryption/decryption to work, the following would have to hold: $lcm(p-1,q-1) = k \cdot lcm(\lambda(a),\lambda(b),\lambda(c))$ for some $k$, where actually $\lambda(n)=lcm(\lambda(a),\lambda(b),\lambda(c))$ is the real order of the multiplicative group (for any odd prime number $x: \lambda(x) = x-1$).

Now I suggest a closer look at Paillier's original paper, e.g. in section 3 the proof that $E_g(x,y)=g^xy^n \mod n^2$ is a bijection if  the order of $g$ is a multiple of $n$. This still holds, even if $n$ has actually more than two prime factors. Similarly, $S_n = \{u < n^2 | u = 1 \mod n\}$ is still a multiplicative subgroup regardless of the prime factors of $n$ and the function $L(u)$ is still well-defined.

Now, let's estimate what the "too large order" effects. Basically, this is similar to RSA, where you can calculate $d$ modulo $\phi(n)$ or modulo $\lambda(n)$: If you use the bigger group where the order is actually less, you get a different $d$ but it works just the same. This is the same in Paillier: $\lambda$ might be a larger number, but it will work regardless (assuming the previously stated assumption is met)

Considering your other questions: The choice of $g$ is not affected by a wrong $\lambda$, especially if using the simplified version with $g=n+1$. The role of $r$ is this: In the decryption you first exponentiate it by $\lambda$, and $r^{n\lambda} = 1$ for any $r$. This is also true, if we our $\lambda$ is a multiple of the real multiplicative group order. A possible problem could arise if $r$ is a zero divisor, but even with multiple large prime factors in $n$ this is negligible. (not sure about this one right now)

About the homomorphic property: Assuming the encryption/decryption still works, this property also still holds. There is no reason why it shouldn't.

And finally about the attacks: Well, this is the same as for RSA, where we still don't know any more efficient attack than just factoring the modulus. And what we know from RSA: With a bigger number of prime factors, some algorithms become faster, e.g. when they scale with the size of the smallest prime factor. Some algorithms scale with the length of the modulus. For some more information about that, I suggest reading the answers to the previously mentioned crypto-SE questions.

As a final note: Just because large prime numbers have a negligible chance of being composite, this doesn't mean you actually have to consider this as a possible weakness: There are plenty of methods of proving or disproving primality and you can get to arbitrary confidence levels (e.g. $1 - 2^{-80}$ is quite common), and they are sufficiently fast. Prime generation itself can be done with a negligible rate of error. And if you think of the Fermat test and Carmichael numbers right now: There are other methods without such curiosities.


The number of NVIDIA TESLA V100 in the Summit supercomputer is documented, and it's reasonable to assume that most of its hashcat performance for SHA-1 would come from that: according  to this source on the Power9 CPU ISA, there is no SHA-1 instructions for the Power CPUs, and then these benchmarks give an order of magnitude on other CPUs.

Isn't that enough for answering the question?

Caveat: a truly powerful specialized SHA-1 cracker would use ASICs, like bitcoin miners do, for even more performance.


Using multiple permutations to strengthen the security of a cipher

At component level, such as Sboxes, you are essentially correct. This is why an (unkeyed, fixed) SBox is never composed with another SBox, without some kind of other mechanism, such as key bit addition, or a permutation of bits between adjacent SBoxes [as suggested by @Paul Uszak].

Note that above, I interpret the word "permutation" as a fixed, unkeyed map. When keys are mixed in, and we view the full cipher globally things change drastically. In this case, the permutation which is the composition of two (or three for triple DES) permutations is extremely difficult to determine since

the search space is so large
there are no shortcuts, the permutations are not presented in lookup table form, plus random keys are involved so we now have essentially random permutations.


Homomorphic Encryption with Addition and Exponentiation

(In most generality..) you're looking for fully homomorphic encryption (FHE), which supports homomorphic addition and homomorphic multiplication. To compute a plaintext's exponentiation, you would run the repeating squaring algorithm (using homomorphic multiplication), to generate an (evaluated) homomorphic ciphertext containing the input-plaintext's exponentiation.

Craig Gentry gave the breakthrough construction of FHE in 2009. Since then, there's been a titanic volume of work improving the techniques, and multiple surveys are available by searching online.

An open-source implementation of modern FHE -- the library HElib by Shai Halevi and Victor Shoup -- can be found here: https://github.com/shaih/HElib


In 2004, Xiaoyun Wang's team first publicly reported collisions in MD5, and in 2007, Marc Stevens, Arjen Lenstra, and Benne de Weger reported a chosen-prefix collision attack on MD5.

Around the same time, the governments of the United States and Israel developed the the Flame malware to sabotage Iran's nuclear program.  Part of the scheme involved forging a Microsoft code-signing certificate using MD5 so that they could sign malicious software without leaving a trail pointing back to themselves.

While studying Flame in 2012, Marc Stevens discovered that the creators of Flame had used an independently developed chosen-prefix attack on MD5 (paywall-free preprint).  We can presume it is independent because if the creators knew about the attack devised by Stevens' group, why would they bother to develop a different way to do the same thing?


Yes, in case of VeraCrypt there is a difference, but it is negligible in practice.

First we need to consider how VeraCrypt actually performs the cascading of the encryption algorithms which is (literally) a block-wise chaining. E.g.:

$$C=E_{XTS}^{1}(E_{XTS}^{2}(E_{XTS}^{3}(M)))$$

where each $E$ is a block cipher run in XTS mode and all using the same XTS parameters in the same position. Of course, keys for each block cipher are still independent, resulting in 1536-bit of key material ($=6\times 256$, XTS uses 2 256-bit keys by itself and each XTS instance has its own keys).

Now the difference of order comes into play when we consider the following result in particular:

  [...] a cascade is at least as difficult to break as the first component cipher.

 From the abstract of: "Cascade Ciphers: The Importance of Being First" by Maurer and Massey (PDF)

So obviously you want the cipher you trust the most in the first position and this is the whole reason why you are given the choice of the order here.

Note however:
Actually using triple encryption is a waste of resources as none of the available ciphers has yet been (notably) broken when independent keys are used and brute-force is already out of the reach for any attacker even if the key-length is "only" 256-bit.


What salt should be used when generating TLS 1.3 CertificateVerify message?

The salt should be generated randomly. This is how PSS encoding is defined: the salt length is an input, and the encoding process generates a random salt of the specified length. The PSS verification process treats the salt read from the signature as an input which can be an arbitrary string of the expected length.
The TLS 1.3 specification states that the salt length must be equal to the length of the hash. (That's the same algorithm used to hash the input and for the MGF — PSS recommends using the same hash, and TLS 1.3 mandates this.) PSS itself allows longer and shorter salts, but using the hash length is very common, even in contexts other than TLS 1.3 where the salt length is not mandated. The security proof of PSS is based on this common choice, but as far as I know there are no known weaknesses for using a shorter, even empty salt, or a non-random salt.
Choosing a non-random (or too short) salt for PSS can reveal the message, since it makes the message guessable from the signature. This is not a concern for a TLS handshake since the message itself contains a random input (ClientHello.random and ServerHello.random).


Yes, SILC is still used daily by a few of us die hards. :-)

I, too, noticed the other day that the official source repos are dead. Perhaps we can get them up on Github or other hosting site.

I haven't heard of any flaws discovered in the protocol itself, but I haven't heard of anyone reviewing it lately either.


Encrypting a small value $m\in\{1,\dots,100\}$ using textbook RSA

If $e$ is "small" (as all typical values of $e$ are!), this is vulnerable to the Franklin-Reiter related message attack.

In a nutshell, given $c_1=x^e\bmod n$ and $c_2=(x+m)^e\bmod n$, for each possible value of $m$, compute
$$f:=\gcd(y^e-c_1,(y+m)^e-c_2)$$
in the polynomial ring $(\mathbb Z/n)[y]$. If you guessed the right $m$, then (possibly except for very rare cases)
$$f=y-x\in(\mathbb Z/n)[y]$$
and you have recovered $x$ and verified that $m$ was correct. Otherwise, $f$ will most likely be $1$. Note that this $\gcd$ is technically not well-defined in all cases, but if you actually encounter a problem with that, you have effectively factored $n$.

Of course, this assumes that $e$ is small enough for this $\gcd$ computation to be feasible, and that the set of possible messages $m$ is small enough to be brute-forceable.


Difference between collision resistance and target collision resistance

Pre-image resistant but not 2nd pre-image resistant? describes the relationship between the three basic hash function security notions: Collision Resistance, Second Preimage Resistance and Preimage Resistance.

In short, Collision Resistance implies Second Preimage Resistance (but not vice-versa) - there is a good diagram on page 4 of RogawayShrimpton04 that illustrates the relationships.

The notion of Target Collision Resistance (which was introduced in BellareRogaway97) is a type of Second Preimage Resistance, and is implied by Collision Resistance.

More formally, Target Collision Resistance describes the ability of an adversary to find a second preimage for a fixed message (compared to the more general notion of Second Preimage Resistance, where the adversary to find a second preimage for a randomly chosen message).

These notions actually sound really similar (and probably in practice are) if you think about real world hash functions, but make more sense when you consider the security notions (and proofs of them) use keyed hash functions - in TCR, the adversary tries to find second preimages for a fixed message over multiple experiments with random keys, while in general 2PIR the message and the key are random in every experiment.


You cannot, without fully specifying the Sbox table. The equations are determined by something like a grobner basis algorithm or some other means which require input of the Sbox specification.
See https://eprint.iacr.org/2017/007.pdf


Enciphering data using AES and moving that to a card without effective security is not enough to solve some very real security issues; including most preeminently the possibility of

returning a prepaid card to its original state, re-crediting it after use (an adversary can copy the original enciphered data, and save it for future use when the genuine card is empty)
making duplicates indistinguishable form the original (which can multiply stored value, or allow to forge duplicates of an access cards)

Update: it was suggested that the content of the card be enciphered and integrity-protected using a symmetric key derived by the reader from the tag's Unique IDentifier and a master key. This effectively prevents an adversary (not knowing the master key) from altering at will the content of a card, or copying the content of a card to another card with different UID. It however gives no protection at all against attack 1 (which copies the original enciphered and integrity-protected data back to the original card); and only blocks attack 2 if an adversary has some difficulty making a duplicate card with the same UID as the original.

Note: Mifare Classic cards do not use a micro-controller, much less a 32-bit micro-controller (as I wrongly thought the question suggested), which are currently used in rather high-end Smart Cards; many Smart Cards ICs used in mobile phones SIMs, bank cards, transport cards, identity documents.. still use an 8-bit CPU, or 16-bit evolved from 8-bit, like these or these.


Is there a way to use bcrypt with passwords longer than 72 bytes securely?

Introduction

BCrypt is a password-based KDF (far from state-of-the-art, but better than PBKDF2, because BCrypt requires sizable RAM, which greatly increases the cost of hardware-accelerated password search).

Bcrypt is based on the block cipher Blowfish, with the initial processing of the password reminiscent of Blowfish's key preprocessing. Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in the proceedings of the first FSE conference, held Dec. 1993) defines that Blowfish's key is of 4 to 56 bytes (32 to 448 bits), with this rationale for the maximum:

  The 448 limit on the key size ensures that the every bit of every subkey depends on every bit of the key. (Note that every bit of $P_{15}$, $P_{16}$, $P_{17}$, and $P_{18}$ does not affect every bit of the ciphertext, and that any S-box entry only has a $.06$ probability of affecting any single ciphertext block.)

Using more than 56 bytes of key for Blowfish is against its definition and design rationale: key bytes beyond the 72nd have no effect whatsoever, and the few before may have somewhat less diffusion (though not nearly as badly as the above quote suggests). Some Blowfish implementations nevertheless accept keys with any positive number of bytes.

Bcrypt, as defined in Niels Provos and David Mazières's A Future-Adaptable Password Scheme (in proceedings of Usenix 1999) accepts a key of 1 to 72 bytes; even with the lowest cost parameter, all key bytes have ample time to reach full diffusion. Bytes beyond the 72nd (if any) have no effect whatsoever. The mapping of password to key is "defined" by:

  take user-chosen passwords as keys

and implementations are known to vary wildly. ASCII only? Some 8-bit codepage extension? Replacement of gremlins with 0x3F bytes? Little-endian or Big-endian UTF16 or UTF32? UTF8, with or without BOM? Length byte, zero-termination? Your guess!

What should be done if the password can be more than 72 bytes?

If there was a formal requirement that it is impossible to exhibit equivalent passwords, or that every character in a password is significant, or with UTF32-encoded passwords (thus only 18 characters), it would be bad to just truncate a password/passphrase to 72 bytes.

The option of replacing Bcrypt's mapping of password to key by a cryptographically secure hash is excellent, if all the characters in the password make it to the input of the hash, and all the bytes in the hash's output make it to the key (I can imagine an implementation where bytes beyond the leftmost 0x00 in the hash, if any, are just ignored; that would be extremely bad, for one in 256 passwords could be replaced by any password with the first byte of its hash equal to 0x00).

The hash should be computationally collision-resistant to a degree significantly better than the strength of the requirement that it is impossible to exhibit equivalent passwords (thus with output of $h$ bits with $h$ significantly above $2k$ if aiming at $k$-bit security level, and unbroken from a collision-resistance standpoint; no MD5, or even SHA-1 from a theoretical standpoint). The strength of all other properties (minimum expected cost for password search by brute force, first and second preimage resistance, resistance to length-extension, and more generally computational indistinguishibility from a random oracle) demonstrably follow from Bcrypt's security.

If there is an entropy of $e$ bits in the input password, and for a hash of $h$ bits indistinguishible from a random oracle, it is expected that there are about $\max(e,h)$ bits of entropy in the key fed to Bcrypt, nearly exactly when $e\ll h$ or $e\gg h$, and within less than about $0.83$ bits in the worst case $e=h$ (see this).

SHA-256 (32 bytes) is thus perfectly fine in practice for any password/passphrase that a human types in (or even more so, memorizes); SHA-512 (64 bytes) can't harm. Ample entropy remains if there was enough in the first place.


If you're using the syntax $<a, b>$ to mean dot-product, then the assumption that you make:

a binary vector is the only vector where $<a,a>=<a,1>$

is incorrect.  It is correct in the ring $\mathbb{Z}$, however we're not in the integers, we're in a finite field.
Counterexamples in finite fields are easy to find; for example, in $GF(11)$ (picked solely because it's large enough to be nontrivial, but small enough for the computation to be easy), we find that for $a = \{ 2, 5 \}$, we have:
$$<a, a> = 2 \cdot 2 + 5 \cdot 5 = 4 + 3 = 7$$
$$<a, 1> = 2 \cdot 1 + 5 \cdot 1 = 2 + 5 = 7$$


The encryption algorithm is probabilistic but the length (or better the entropy) of the ciphertext must be at least the length of the message. If the length of the ciphertext is shorter than the length of the plaintext, then you loose information about the plaintext while encryption process and you cannot decrypt it correctly. And the encryption algorithm is memoryless and does not know anything about older or other messages.

Now, suppose you have the two messages $||m_0|| = l_0$, $||m_1|| = l_1$ and $l_0 << l_1$ (say $l_0 = 1 \, bit$ and $l_1$ is very large $>10G \, bits$). If you receive a ciphertext shorter than $l_1$ you know that $m_0$ was encrypted. I think you can see, that an encryption algorithm, that produces ciphertexts longer than $l_1$ when you only encrypt a single bit, is very inefficient.

The only way to cancel this effect is to restrict the length of the plaintext messages and produce ciphertexts equal or longer than this maximum input length. But in this case, the plaintext of a single bit will be padded and you can directly define the security with equal length messages.


Security proof in pairing based cryptography

The only way i can see to evaluate $e(C_x,D)$ is to recover $D$ from a previous known pairing $e(C_i,D)$. However due to the Fixed Argument Pairing Inversion 1 assumption this is computationally hard.


Is CMAC vulnerable to length extension attacks?

Given $m_1, m_2$ such that $MAC_k(m_1) = MAC_k(m_2)$ is it possible to construct more collisions with pairs of the form $m_1|x, m_2|x$?

Yes, given two restrictions:

$MAC_k$ is not truncated (e.g. if it is based on AES, then the tag is 128 bits long).  This observation does not apply on a collision on (for example) truncated 64 bit tags (assuming that the bits deleted during the truncation don't also happen to collide).

$m_1$ and $m_2$ are either both a multiple of the block size in length, or alternatively both not a multiple of the block size in length.  For example, if we assume AES, then it works if $m_1, m_2$ are $32, 48$ bytes in length (both multiples of 16), and if they are $23, 31$ bytes in length (neither multiples of 16), but not if they are $16, 17$ bytes in length.

Here is how CMAC works (at the end of the message, which is where the interesting part it):

Block $n-1$ is processed, generating an internal chaining value $I_{n-1} = E_k( m_{n-1} \oplus I_{n-2})$

the last block is processed; the block is zero padded (if not full), one of $k_1, k_2$ is selected (depending on whether the block is full), and we do a final computation $tag = E_k( m_i \oplus k_{1,2} \oplus I_{n-1})$

Now, we assume a full block collision, that is, $tag = tag'$.  Using the above definition, we have:
$$E_k( m_n \oplus k_{1,2} \oplus I_{n-1}) = E_k( m'_n \oplus k_{1,2} \oplus I'_{n-1})$$
Removing the encryption, and noting that both sides select the same $k_1, k_2$ value, we can simplify this to:
$$m_i \oplus I_{n-1} = m'_i \oplus I'_{n-1}$$
Now, we can consider what would mapping if we compute the CMAC of the values $m || padding || x$, $m' || padding' || x$ (where $x$ is an arbitrary bits string, and where $padding, padding'$ are the zero pad to bring $m, m'$ to a multiple of block size in length; they are zero length if $m, m'$ is already a multiple of block size).
In this case, at step $n$, the two sides will compute:
$$I_n = E_k(m_n \oplus I_{n-1})$$
$$I'_n = E_k( m'_n \oplus I'_{n-1})$$
These two values are the same; the rest of the CMAC computation depends only on $x$ (which is the same on both sides), and so will result in the same tag; hence giving us another collision.


How does the Flickr length extension attack work?

How can he do that? He could take api_signature = h = md5(m) and use it as the Initialization Vector of the hash function and hash the extra data and another padding. This is the idea behind the hash length_extension attack, isn't it?

Correct.

  My question: The api_signature will change then because it is calculated like: md5(extra || padding) with the old api_signature as an initialization vector. How is this valid?

That is why knowing the length of the data is important. The attacker can use the length extension attack to calculate the MD5 hash of data||original_padding||arbitrary_data by using the original hash value as an IV to calculate the hash h'(arbitrary_data||new_padding), where the new padding uses the total length of the original padded data and the appended data.

  And overall: What does the server expect from a "normal" client when he sends this?

The server expects a request that is "authenticated" with a hash of secret||request. By adding data to the end of the request and massaging the URL sufficiently, the attacker can compute the hash without knowing the secret value, for sufficiently modified URLs as to allow arbitrary requests. (Due in part to another weakness in how URL parameters were encoded for hashing.)


Can I create a random access CSPRNG from a hash?

There is a name for "random access PRG" : it's called a pseudorandom function (PRF). Any block cipher is a pseudorandom function (that's more-or-less the definition of what it means to be a secure block cipher), so you can use, say, AES directly. If all you have is a hash function, then the HMAC construction also gives you a PRF.


The problem with this question is that it doesn't establish if the keys are static or not. If the keys are both static and a static-static (2S) DH protocol is used, then yes, this could guarantee secrecy if the public keys can be trusted to be from the right party, thereby authenticating A to B and B to A. A little used option of TLS is to use Diffie-Hellman based certificates, for instance.

Otherwise you're missing the authentication step, and Mallory could perform a man-in-the-middle by establishing keys A-M and M-B by tricking A and B that they are creating a secure channel to each other. Note that this is an active attack. it only works for Mallory - who can perform active attacks, not for Eve who can only eavesdrop the communication. Therefore "no" is most likely the correct answer.


Security of CBC-MAC fixed length with zero padding

Let's simplify this to one-block messages with a 128-bit block.  Your scheme to authenticate a message whose length in bits $n$ is anywhere from 0 to 128 is $$\operatorname{MAC}_k(m) = \operatorname{AES}_k(\operatorname{pad}(m)),$$ where $\operatorname{pad}(m) = m \mathbin\Vert 0^{128 - n}$, and $0^{128 - n}$ means a string of $128 - n$ zero bits.

Note that for any message $m$ of fewer than 128 bits, $\operatorname{MAC}_k(m) = \operatorname{MAC}_k(m \mathbin\Vert 0)$.  Thus if I can learn, via an oracle, the tag of any message, the same tag will authenticate the same message with zeros appended, or, if it has trailing zeros, the same message with trailing zeros stripped.

The problem is not with AES, or CBC, or CBC-MAC, or the fixed block size, or anything like that.  The problem is that $\operatorname{pad}(m) = \operatorname{pad}(m \mathbin\Vert 0)$.  For each padded message, there must be a unique unpadded message.  This padding scheme fails that.


Calculating power consumption by a cipher program

If any program is run it consumes some power. There is no way to programmatically calculate the power consumption for a given cryptographic primitive, because this not only depend on how you implemented said primitive but also on the hardware (mostly CPU) used. The best thing you can have is to measure the time it took to calculate the primitive.


Can a tree hash with leaf-size of 1 byte support verification of content with elided ranges, at a cost of at most 2 supplied internal-node hashes?

It is not true that there would always be at most two hashes required per elided range.

Suppose you have an eight-byte long content and want to elide all but the last. You need to supply one hash for the left half, one to cover the next two and one more to cover the last one.

Similarly, with 16 bytes of content, eliding the first 15 requires four hashes. And in general, eliding $2^n-1$ bytes out of $2^n$ requires $n$ hashes, so it is not bounded by a constant, but can grow linearly with tree height (logarithm of content length).

There is an additional problem with the scheme: a preimage search depends on the length of content hashed. Suppose that the redacted value is a random 128-bit string (encoded as just the raw 16 bytes). Unguessable, right?

Not if it falls poorly on the hash tree boundaries. It is possible that the redaction algorithm reveals the hash of the first byte, $H(b_1)$, the higher level hash of the next two bytes, $H(H(b_2)||H(b_3))$, etc. The first can be found out with $2^7$ calls to the hash function on average. The next with about $2^{15}$. The rest with $2^{31}$, $2^{63}$, $2^{7}$. Guessing the complete value requires less than $2^{64}$ work. Difficult, but much less than $2^{127}$ and probably doable.

For the redaction to be secure, a much larger block size than one byte would be needed and each redacted block would need to have enough (computational) entropy. You might be able to pair each byte of the document with a 128-bit random number and redact those as well, but clearly that would be a quite inefficient encoding (>16x expansion).


Modelling broadcast functionality in Universally Composable Framework

UC broadcast can be defined by a functionality $\mathcal{F}_{\textrm{BC}}$, which upon receiving a message $x$ from party $P_i$, sends $(x, P_i)$ to all parties and the adversary.

This is formally given in, e.g. Section 3.2 of a paper by Goldwasser and Lindell. However, many higher-level protocols use broadcast without explicitly specifying the functionality, because it is so straightforward.

That paper also contains the following, very simple echo-broadcast protocol for any $t < n$ corruptions:

$P_i$ sends $x$ to all other parties
Every other party re-sends $x$ to everybody else and checks that they received the same values.
If any value is inconsistent, abort. Otherwise, output $x$.

This is secure in a slightly weaker model, where a corrupt party may force some honest parties to abort; however, any honest party who does not abort will learn the correct output.


Encryption scheme with arbitrary length message

As poncho already wrote in the comments, this isn't possible:

Basically the only way to hide the length of a message is to use a padding, which is long enough.
The adversary knows at least the encryption method and implicitly the length of the padding.
If you allow arbitrary messages, he can choose one message really short (e.g. 1 bit) and the other longer than the padding. If your encryption scheme allows arbitrary length messages, this must be possible, e.g. by a mode of operation (known from block ciphers)

You can't adapt the padding length after seeing the messages chosen by the attacker. Otherwise the information about the length might leak other information about the message again, and then you're going in circles.

edit: Oh, and again you might want to explain notation and security games in the question - even if it doesn't actually matter for this one. Writing down clear definitions might help you see problems on your own.


Attack being kind of completely puzzled?

I think the key to comprehending this passage is the first sentence of the paragraph it is in, which refers to a "random oracle paradigm". From wikipedia, a random oracle is essentially a black-box function; deterministic and repeatable, yet its output is indistinguishable from random noise. The random oracle paradigm is defining the security of a cryptographic primitive by comparing it to a random oracle, i.e. does it leak any information about its function such that its output can be distinguished from random noise. This, the paper argues, is a reasonable standard for symetric primitives, but unreasonable for asymmetric ones. The crux of their argument is, in essence, secure symmetric primitives have very complex internal function, but asymmetric primitives are comparable very simple. Thus, as the sentence you provide very unclearly states, it is unreasonable to think that an attacker would have no knowledge of the internal function of asymmetric primitives, and so it is not necessary that an asymetric primitive's output leak no information about its function, i.e. indistinguishable from random noise, for it to be secure.


How can an interactive ZKP become non-interactive?

Warning: Oversimplified.

Most, if not all interactive Zero-Knowledge proofs rely on the randomness of the verifier. Taking the Ali Baba cave example, since Alice cannot predict what path Bob wants her to come out of, it is statistically improbable that she will be able to fake the proof, especially when this "experiment" is done multiple times.

In case you don't know, a hash funtion is a pseudo-random function. This means that, given the same input, it will always generate the same output. A cryptographic hash function is a one-way function, one where it is infeasible to create a preimage attack, or simply put, finding X in H(X)=Y, given only Y.

The Fiat-Shamir heuristic simply replaces the verifier's randomness (and therefore the interaction) with a random oracle, or in concrete terms, a cryptographic hash function. Since the prover cannot predict the output of a cryptographic hash function, this provides the randomness necessary for the scheme to work.

In that case, Alice wants to prove that she can unlock the door in a cave C. She goes inside the cave, generates a hash H(C), and depending on the output, goes in either path A or B and comes out the other path. Bob, without ever telling Alice anything, simply checks that Alice went through the correct path (if H(C)=A or H(C)=B) and that she exited through the other path.

You could adapt this to make it harder to fake, by computing H(C||n) instead of H(C), where n is a number starting from 0 that increases by 1 every time the experiment is conducted, and running the experiment multiple times.

This Wikipedia article is a really good one and gives a more concrete example.


Statistical Tests for Pseudorandom Functions

Nobody uses generic statistical tests to verify correctness of encryption algorithms.

To verify correctness of an implementation, engineers write proofs of correctness for their code, tr running it on known-answer tests, confirm round-trips on randomized inputs, etc.

None of this involves statistical tests, since the point is to implement a specific mathematical function, not to sample stochastically from a distribution—indeed, if you did use generic statistical tests you'd have to decide what to do in the case of false alarms, which would be an absurd way to approach verification of software implementing deterministic mathematical functions.
To assess security of a cryptosystem, cryptographers study specialized statistical tests.

Assuming, following the advice of Kerckhoffs, that the adversary knows the system, what's the best they can do to attack it with that knowledge?  Generic statistical tests like $\chi^2$ tests are stupid because they don't even know the system.  For example, here's a test for distinguishing a 256-bit AES-CTR stream under a uniform random key from a uniform random 256-bit string:

Guess a key $k$ uniformly at random.
Check whether the string $s = s_1 \mathbin\| s_2$ is of the form $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1)$.  If it is, guess AES-CTR; if it isn't, guess uniform random.

This test has distinguishing advantage $2^{-256}$ (or $2^{-128}$ if you use AES-128 instead of AES-256, which I don't recommend[1]), so the best distinguishing advantage for AES can't be worse than $2^{-256}$, but a lot of smart cryptanalysts haven't found a way to do any better than that.  Obviously, you could spend more computation—try it twice, with two different keys $k_1$ and $k_2$—to raise the advantage linearly, so this number should be qualified with a cost factor.

Any putative pseudorandom function family should come either with the paper droppings of a horde of cryptanalysts demonstrating failure to find a better-than-generic distinguisher, or with a proof of a theorem relating the security of the PRF to the security of some underlying primitive.  For example, the best PRF-advantage attainable against AES by any distinguisher making $q$ queries is bounded by the best PRP-advantage attainable against AES, which cryptanalysts have studied for decades now, plus $q(q - 1)/2^{129}$ because AES is always a permutation.

So, put your generic statistical tests in the garbage.  Find the literature on the putative PRF.  Write a proof of correctness of your code.


What are "unspecified" differentials in a differential characteristic?

In these papers they are trying to search for a strong boomerang trail and are semi-exhaustively searching over families of trails where each family has a higher chance of holding than a trail chosen uniformly at random from all possible trails. In these families the unspecified differentials are what we (semi-)exhaust over and the specified parts of the differential are fixed for the family and improve the probability of a typical member of the family above uniform random.
In your example we are looking at two families of differential trails (one upper and one lower) where the fixed differentials for the upper family are lime and white and the fixed differentials for the lower family are pink and white. The fixed parts of the differentials were likely chosen because they have a very high probability of holding and the maximum probability of differentials on the unspecified parts was not as strong. Greedily choosing likely values of the grey differentials gives a large collection of high probability trails for both the upper and lower families. These can then be efficiently pairwise tested using a meet-in-the-middle approach to calculate the probability of the trails combining to make a strong boomerang trail using e.g. a Boomerang Connectivity Table. Trying enough upper and lower trails will hopefully result in a high probability upper trail that combines well with high probability lower trail and a very strong overall boomerang distinguisher.
Note that if more than one strong trail is found, the probabilities reinforce as the same statistical test will detect any trail that has the same start and end points.


Can the birthday attack be extended in this case?

So, as in @poncho's comment, the generalized birthday problem for $m=2^k$ inputs, fixed $k\geq 2$,
$$
H(x_1)\oplus \cdots \oplus H(x_m)=a,\qquad a \in \{0,1\}^n
$$
for any constant $a$ can be solved by using essentially (up to $o(n)$ terms in the exponent)
$$
T=O(m⋅2^{n/(k+1)}),
$$
and
$$
M=O(2^{n/(k+1)})
$$
by the algorithm in Wagner's paper.
If $m$ is not a power of two, one can use the algorithm for the next power of two.
As far as I know, no general algorithm with better complexity than $T=O(2^{n/2})$ is known for the case $m=3.$ Fix one input and do a birthday attack on the sum of the other two, which requires a list of size $O(2^n).$ If you are restricted to use the minimum memory possible, then a list of size $O(2^{n/3})$ suffices (this is also the lower bound from information theory to have a solution with non negligible probability) but it would seem that you need to generate all 2-wise sums from the list with time complexity $O(2^{2n/3})$ and check in the hash sorted list for collisions in constant time for each check.
Perhaps the experts here can enlighten us if the above  is not the case.
Calling the $m=3$ case, the 3XORSUM problem, the similar 3SUM problem for integers (instead of binary vectors) is of interest in algorithmics with many applications, see for example the question here from TCS stack exchange.


What order should these HTTPS ciphers go in to maximize security?

In short, don't bother getting 100 in "Cipher Strength" or "Key Exchange".

It is possible to get 100 in "cipher strength" by only allowing 256-bit ciphers, however, this will break compatibility with considerable amount of clients, slow down your server and have no security benefits. You can also get 100 in "key exchange" by only using >=4096-bit RSA or >=384-bit ECDSA certificate, as well as only allowing >=4096-bit DH or >=384-bit ECDH key exchange. I personally don't recommend it either for the same reason above.

There are some real things to do to improve security. If you are using OpenSSL 1.0.2 or lower, upgrade to 1.1.0 or higher, turn on ChaCha20 cipher and X25519 key exchange. Use 2048 or 3072-bit RSA and 256-bit ECDSA certificate in parallel if possible, and replace your DH parameter to match the length of your certificate key instead of 4096-bit.

The official document for NGINX SSL configuration:
https://nginx.org/en/docs/http/ngx_http_ssl_module.html

By the way, SSL Labs will use a new letter-grade marking scheme and fully deprecate the numeric ones (https://blog.qualys.com/ssllabs/2017/06/30/ssl-labs-grading-redesign-preview-1). Therefore, in the future, getting a 100 will no longer make a difference.

Good luck!


How to get the original list back given a shuffled list and seed?

Yes. Throughout this, I will make the assumption (which appears to be the case) that random.shuffle() permutes the list in a way that only depends on:

The seed used
The length of the list being shuffled

This is to say that, for a fixed seed and fixed length of a list (say $n$), random.shuffle() chooses some permutation $\sigma\in S_n$, and then sends the list:

$$[a_1,a_2,\dots, a_n] \mapsto [a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}]$$

For example, if $n = 4$, and $\sigma$ sends $1 \to 2$, $2\to 4$, $3\to 3$, and $4\to 1$, then for any initial list $[a_1, a_2, a_3, a_4]$, random.shuffle() will permute it to $[a_{\sigma(1)}, a_{\sigma(2)},\dots, a_{\sigma(n)}] = [a_2, a_4, a_3, a_1]$.

Let $ls = [a_1,\dots, a_n]$ be the (initial) list you care about, and let $\sigma(ls) = [a_{\sigma(1)},\dots, a_{\sigma(n)}]$ be the shuffled version of it.
We can "unshuffled" it by using our prior assumption about random.shuffle() to "find" the permutation $\sigma$ that was used before.
In particular, if we set the seed the same, and use a list $\mathsf{perm} = [b_1,\dots, b_n]$ of the same length, we'll have that:

$$\sigma(\mathsf{perm}) = [b_{\sigma(1)}, b_{\sigma(2)},\dots, b_{\sigma(n)}]$$
Then, if we have some way of restoring $\sigma(\mathsf{perm})\mapsto \mathsf{perm}$, we can simply "do these same steps" to $\sigma(ls)$ to recover $ls$.

Because of this, a particularly easy choice of $\mathsf{perm}$ to work with is $\mathsf{perm}= [1,2,\dots,n]$ (we can return to it via sorting).
Note in that $b_i = i$, so $\sigma(\mathsf{perm}) = [\sigma(1),\dots, \sigma(n)]$.

One particularly easy way to "sort $\sigma(\mathsf{perm})$, but apply the same sequence of transpositions to $\sigma(ls)$" is by creating the "zipped list":

$$\mathsf{zipped\_list} = [(\sigma(ls)[0], \sigma(\mathsf{perm})[0]), (\sigma(ls)[1], \sigma(\mathsf{perm})[1]), \dots, (\sigma(ls)[n], \sigma(\mathsf{perm})[n])]$$

Note that each part of each tuple has been permuted precisely the same way! So we can view this as:
$$\sigma([(a_1, 1), (a_2, 2), \dots, (a_n, n)])$$
I.e. our initial list, along with the list $[1,2,\dots,n]$, with the same permutation applied to both of them.
We can then remove this permutation by sorting this larger list based on the second component of each tuple.
This will return the list $\sigma([1,2,\dots,n])$ to $[1,2,\dots,n]$, and will therefore return $\sigma([a_1,\dots,a_n])$ to $[a_1,\dots, a_n]$ as well (as the same sequence of moves, which "cancel out" $\sigma$, are being applied to each list).

In case this theoretical description of what's happening is still not clear, the following python3 code should demonstrate that this works.
I've additionally uploaded it to an online interpreter here.

import random

def shuffle_under_seed(ls, seed):
  # Shuffle the list ls using the seed `seed`
  random.seed(seed)
  random.shuffle(ls)
  return ls

def unshuffle_list(shuffled_ls, seed):
  n = len(shuffled_ls)
  # Perm is [1, 2, ..., n]
  perm = [i for i in range(1, n + 1)]
  # Apply sigma to perm
  shuffled_perm = shuffle_under_seed(perm, seed)
  # Zip and unshuffle
  zipped_ls = list(zip(shuffled_ls, shuffled_perm))
  ls.sort(key=lambda x: x[1])
  return [a for (a, b) in ls]

These should satisfy, for any list ls, and any choice of seed, that unshuffle_ls(shuffled_under_seed(ls, seed), seed) == ls, which you can experimentally validate.


Text encrypted with key1, key1 encrypted with key2, meaningful?

Just two ideas:

If you have some kind of hardware security module (HSM) to protect your K_Azure you might want to avoid using that HSM to encrypt large volumes of data. But since you cannot get the K_Azure out you generate a new key and use that.
If you don't have other randomization in your AES mode you will leak equality information if you use the same key for the same data.


Name of specific cryptography property of XOR

XOR is a linear operation which is inverse of itself too.

k1 $\oplus$ k1 = 0

It is also commutative.

(k1 $\oplus$ k2) $\oplus$ k3 = k1 $\oplus$ (k2 $\oplus$ k3)

Thats why you can decrypt the way you have shown in question. Where as AES is not a linear operation and it is not inverse of itself. Applying AES encryption twice with same key will not produce the orignal Text.

AES(K1, AES(K1, M)) $\neq$ M

AES is also not Commutative

AES(K1, AES(K2, M)) $\neq$ AES(K2, AES(K1, M))

1) Simple XOR operation is not a cipher until its One Time PAD. Encrypting multiple texts with same keys using XOR will be a total break. Its use of the XOR operation which allows to decrypt the way you have shown because XOR is commutative, associative, and its own inverse.

2) The Block Encryption algorithms will not exhibit properties like commutative, associative, and its own inverse. However Cipher can be used to generate a random key stream (Like Stream Cipher) in CTR mode which is then XOR with the plaintext to make ciphertext. So in the End its commutative and associative operation.


Why is a Feistel Network able to both encrypt and decrypt just by using the round keys in a different order

In short because XOR is its own inverse operation. a XOR b XOR b is a again.

To decrypt an encrypted message we have to reverse the round function. For algorithms like AES (which is no Feistel network but a Substitution-permutation network, in short SPN) we have to reverse most operations like the MixColumn operation. This inversion is called InverseMixColumn. Theoretically we also have to do that for any Feistel network, but they nearly always use XOR as the combination of the one half with the changed other half. The inverse of XOR is again XOR, so we don't have to change it, but can just do the same again.

Take a look at a diagram of Feistel networks. Look at the output of the encryption scheme. Now try to reverse this - go back step by step. You can put one half again into the Round function, get and intermediate result and XOR this with the other half. Now you got back the input before this calculation. Repeat this until you are back at the first input which is your original plaintext. The round keys you used while doing this were the same as for the encryption, but in reversed order.


Could someone please explain test vectors of NIST for RSASSA-PSS 1024 bit?

In Result = F (4 - Format of the EM is incorrect - hash moved to left ), the first F says that a correct signature verification implementation must Fail to verify the test vector (for known-good vectors, there is Result = P for Pass). What's in parenthesis following F documents the intention in making the test vector, but that's purely informative.

My guess is that this particular one means that the test vector is believed having been generated with the hash field too much on the left, eating some padding. But looking at EM with hash moved value, this clearly contains an EM for RSAES-PKCS1-v1_5 except the PS field is too short and garbage is inserted on the right, and I can't make sense of that in an RSASSA-PSS test suite. But who cares that a test vector expected to fail is nonsense? The point is that it is rejected; test vectors have poor coverage of possible errors in signature verification code anyway.

Update following comment: There are valid Pass test vectors for 3072-bit RSASSA-PSS in the FIPS 186-3 test vectors, file SigVerPSS_186-3.rsp, from which the question seems to be extracted. The mildly hard thing is extracting them out of the ocean of Fail vectors. Towards this, find immediately above some Result = P the values of SaltVal, S (3072-bit), Msg, d, e, SHAAlg; then somewhere above a value of n (3072-bit); check that d, e, n match by verifying that $2^{ed}\bmod n=2$, then forget about d; you have your test vector! Here is one:

n = ce4924ff470fb99d17f66595561a74ded22092d1dc27122ae15ca8cac4bfae11daa9e37a941430dd1b81aaf472f320835ee2fe744c83f1320882a8a02316ceb375f5c4909232bb2c6520b249c88be4f47b8b86fdd93678c69e64f50089e907a5504fdd43f0cad24aaa9e317ef2ecade3b5c1fd31f3c327d70a0e2d4867e6fe3f26272e8b6a3cce17843e359b82eb7a4cad8c42460179cb6c07fa252efaec428fd5cae5208b298b255109026e21272424ec0c52e1e5f72c5ab06f5d2a05e77c193b647ec948bb844e0c2ef1307f53cb800d4f55523d86038bb9e21099a861b6b9bcc969e5dddbdf7171b37d616381b78c3b22ef66510b2765d9617556b175599879d8558100ad90b830e87ad460a22108baa5ed0f2ba9dfc05167f8ab61fc9f8ae01603f9dd5e66ce1e642b604bca9294b57fb7c0d83f054bacf4454c298a272c44bc718f54605b91e0bfafd772aebaf3828846c93018f98e315708d50be8401eb9a8778dcbd0d6db9370860411b004cd37fbb8b5df87edee7aae949fff34607b
SHAAlg = SHA256
e = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000073b193
Msg = 0897d40e7c0f2dfc07b0c7fddaf5fd8fcc6af9c1fdc17bebb923d59c9fc43bd402ba39738f0f85f23015f75131f9d650a29b55e2fc9d5ddf07bb8df9fa5a80f1e4634e0b4c5155bf148939b1a4ea29e344a66429c850fcde7336dad616f0039378391abcfafe25ca7bb594057af07faf7a322f7fab01e051c63cc51b39af4d23
S = 8ebed002d4f54de5898a5f2e69d770ed5a5ce1d45ad6dd9ce5f1179d1c46daa4d0394e21a99d803358d9abfd23bb53166394f997b909e675662066324ca1f2b731deba170525c4ee8fa752d2d7f201b10219489f5784e399d916302fd4b7adf88490df876501c46742a93cfb3aaab9602e65d7e60d7c4ceadb7eb67e421d180323a6d38f38b9f999213ebfccc7e04f060fbdb7c210206522b494e199e98c6c24e457f8696644fdcaebc1b9031c818322c29d135e1172fa0fdf7be1007dabcaab4966332e7ea1456b6ce879cd910c9110104fc7d3dcab076f2bd182bb8327a863254570cdf2ab38e0cda31779deaad616e3437ed659d74e5a4e045a70133890b81bc4f24ab6da67a2ee0ce15baba337d091cb5a1c44da690f81145b0252a6549bbb20cd5cc47afec755eb37fed55a9a33d36557424503d805a0a120b76941f4150d89342d7a7fa3a2b08c515e6f68429cf7afd1a3fce0f428351a6f9eda3ab24a7ef591994c21fbf1001f99239e88340f9b359ec72e8a212a1920e6cf993ff848
SaltVal = 00
Result = P

If you find some reference telling if the MGF1 function shall use the hash designated by SHAAlg, or SHA-1, please share it!


Security levels in NIST Post-quantum project: e.g. AES-128 vs SHA-256

This is due to the Brassard et al.'s method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function where as the Grover's method has $\mathcal{O}(\sqrt{n})$-time.

Level I: At least as hard to break as AES-128 $\mathcal{O}(\sqrt{2^{128}}) = \mathcal{O}(2^{64})$ - by Grover
Level II: At least as hard to break as SHA-256 $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$ - by Brassard et al.
Level III: At least as hard to break as AES-192 $\mathcal{O}(\sqrt{2^{192}}) = \mathcal{O}(2^{96})$ - by Grover
Level IV: At least as hard to break as SHA-384 $\mathcal{O}(\sqrt[3]{2^{384}}) = \mathcal{O}(2^{128})$ - by Brassard et al.
Level V: At least as hard to break as AES-256 $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$ by Grover

The space-time comparisons of the two quantum hash collisions methods.

\begin{array} {|c|c|}\hline
 & \text{time} & \text{space} \\ \hline
\text{Grover} & \mathcal{O}(\sqrt{n}) & \mathcal{O}(\log{n}) \\ \hline
\text{Brassard et al.} & \mathcal{O}(\sqrt[3]{n}) & \mathcal{O}(\sqrt[3]{n}) \\ \hline
\end{array}

Bernstein has a nice article "Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete" about comparison with parallelized van Oorschot–Wiener. You can also read Squeamish Ossifrage's answer.


Encrypting data with HMAC-SHA1 challenge response as the key

Yes, it is secure to generate the key as long as the $K$ is kept secret.  Although the collision of SHA-1 is broken, HMAC is a PRF under the sole assumption that the compression function is a PRF. It is not affected by the collision of the has function.
The security strength of the HMAC is relay on the size of the key. The usual attack is to search for the key $K$.
Keep in mind that, the attacker will go to search for $E$ if $E<K$. In your case, since both are 20 bytes, so brute-forcing $K$ can be faster, though not possible.


RSA enc/decryption with multiple prime modulus using CRT

The RSA private-key operation (used for decryption and signature generation) amounts to solving for $x$ the equation $y\equiv x^e\pmod N$, knowing $y$, the factorization of the public modulus $N$ into $k\ge2$ distinct primes $N=r_1\dots r_k$, public exponent $e$ such that $\gcd(e,r_i-1)\ne1$, and that $0\le x<N$.

For an efficient implementation, we can solve this equation modulo each of the $r_i$; then use the CRT to combine solutions between products of moduli for which we already have a solution, until reaching a solution modulo $N$. The common way, implicit in PKCS#1v2.2, is:

precompute the following quantities $d_i$ (the CRT exponents) and $t_i$ (the CRT inverses/coefficients), e.g. at key generation time, including the results in the private key:

for $i\in\{1,\dots,k\}$

$d_i\gets e^{-1}\bmod(r_i-1)$, or equivalently $d_i\gets d\bmod(r_i-1)$

$m\gets r_1$
for $i$ from $2$ to $k$

$t_i\gets m^{-1}\bmod r_i$
$m\gets m\cdot r_i$

when needing to use the private key and solve $y\equiv x^e\pmod N$

for $i\in\{1,\dots,k\}$ [note: should be parallelized if possible]

$x_i\gets(y\bmod r_i)^{d_i}\bmod r_i$

$x\gets x_1$, $m\gets r_1$
for $i$ from $2$ to $k$ [loop invariant: $0\le x<m$, $y\equiv x^e\pmod m$ ]

$x\gets x+m\cdot((x_i-x\bmod r_i)\cdot t_i\bmod r_i)$
$m\gets m\cdot r_i$

Correctness follows from the loop invariant. See this question for attribution. See this other one for how the bitsize of $N$ relates to a maximum reasonable number of primes.

Artificially small example with 3 primes:

e=5
r1=931164518537359 r2=944727352543879 r3=982273258722607
N=864102436520313334659779717201860718296307527
d1=558698711122415 d2=566836411526327 d3=785818606978085
                   t2=360227672914825 t3=882117903741868
y=529481440313141057262802385309623737292746309
x1=436496882968258 x2=903092574358267 x3=806961802724
x=710532117316769399313215266414 (when i=2)
x=111222333444555666777888999000000000000000042

The effort saved compared to a standard (non-CRT) implementation is by a factor at most (and near) $k^2$, if modular multiplication has cost $\mathcal O(n^2)$ for arguments of $n$ bits. The time saved can be higher, up to a factor at most (and near) $k^3$ if parallelization is used on $k$ independent modexp units.

It is critical to make a final check that $y\equiv x^e\pmod N$, and not disclose $x$ otherwise. If this precaution was not taken, the implementation would be vulnerable to the cardinal "Bellcore" fault attack: D. Boneh, R. A. DeMillo, R. Lipton; On the Importance of Eliminating Errors in Cryptographic Computations (in Journal of Cryptology 14(2), 2001; or there).

Implementations should be adequately protected from a variety of other attacks, including timing, power analysis, and other side-channel attacks.

The question also mentions encryption, where only the public key $(N,e)$ is known, not the factorization of $N$. Hence, for that RSA public-key operation (also used for signature verification), there is no similar shortcut applying to the computation $y\gets x^e\bmod N$. However, typically, that remains of low cost compared to the RSA private-key operation, because $e$ is small.


"123456" and "password" as crack standards

Using several different encryption algorithms, and not disclosing which is used in each particular case would require password verification to try all possible algorithms. Feasible only when using just a few algorithms.
Truecrypt does this, for example.

This could strengthen security, when implemented properly - but it is much more difficult to implement.

Proper solution - salt.

Do not use MadeUpHashingTechnology without salt.
Do not use  MadeUpHashingTechnology ever, use public, verified crypto.


How to produce a binary output sequence using LFSRs but with increased linear complexity?

One standard way is as follows. Given $n$ primitive LFSRs with lengths $L_i,i=1,\ldots,n$ such that $\gcd(L_i,L_j)=1,$ and a nonlinear boolean function $$f:\mathbb{F}_2^n \rightarrow \mathbb{F}_2$$ with $f(x_1,\ldots,x_n)$
you have output linear complexity
$$
f(L_1,\ldots,L_n)
$$
evaluated over the integers, where output of LFSR $L_i$ is input as the variable $x_i$ of the boolean function. This is called the combination generator.

So if, for example,
$$f(x_1,x_2,x_3)=x_1x_2+x_2x_3
$$
with
$L_1=31,L_2=32,L_3=33,$ the linear comlexity becomes $31\times 32+32\times 33=2048 $.

See the book Encyclopedia of Cryptography and Security on page 233 for a good discussion.


Is there a kind of OS entropy pool on Windows systems?

So far as I know, Windows does not (but you never know, it has an endless series of APIs so anything is possible). However, Intel hardware does. The Microsoft C/C++ compiler (and the Intel compiler) has intrinsics for obtaining a hardware generated random value. That value is obtained by running two circuits backwards so that are unstable. They generate a ton of very random bits which are then cleaned up. Intel has some white papers on it. I don't know if AMD processors have the same thing. I don't have either the name of the functions or the white paper handy, but you can find them with a web search (or, for the functions, look in the header files).