What is the difference between SHA-3 and SHA-256?

The main differences between the older SHA-256 of the SHA-2 family of FIPS 180, and the newer SHA3-256 of the SHA-3 family of FIPS 202, are:

Resistance to length extension attacks.
With SHA-256, given $H(m)$ but not $m$, it is easy to find $H(m \mathbin\| m')$ for certain suffixes $m'$.  Not so with any of the SHA-3 functions.

This means, e.g., that $m \mapsto H(k \mathbin\| m)$ is not a secure message authentication code under key $k$ when $H$ is SHA-256, because knowing the authenticator on one message lets you forge the authenticator on another.  The length extension property partly moviated the development of HMAC.

In contrast, the key-prefix construction is secure as a MAC when $H$ is any of the SHA-3 functions—or either of the newer SHA-2 functions SHA-512/224 and SHA-512/256.  For SHA-224, which is essentially the 224 bit truncation of SHA-256 (but with a different IV), the adversary has a $2^{-32}$ chance of guessing the discarded bits of output in a single trial—small but not negligible.
Performance.
The SHA-2 functions—particularly SHA-512, SHA-512/224, and SHA-512/256—generally have higher performance than the SHA-3 functions.  Partly this was out of paranoia and political reasons in the SHA-3 design process.

(In response, one of the SHA-3 finalists was spun out into the much faster BLAKE2, also widely used on the internet today, and the SHA-3 winner Keccak was spun out into the much faster KangarooTwelve.)
Completely different internal design.
SHA-2 uses the Davies–Meyer structure, an instance of the Merkle–Damgård structure, with a block cipher (sometimes called SHACAL-2) built out of an ARX network, like MD4; SHA-3 uses the sponge structure with the Keccak permutation.

There is no user-visible difference here, but it made a difference for cryptographers' confidence in the designs after many DM/ARX designs based on MD4 were broken in the late '90s and early 2000s.

History.  There has been a long line of hash functions standardized by NIST in FIPS 180, the Secure Hash Standard, and later FIPS 202¸ the SHA-3 Standard: Permutation-Based and Extendable-Output Functions.  More details and history, including the related MD4 and MD5 hash functions on which SHA-0, SHA-1, and SHA-2—but not SHA-3—were based:

\begin{equation}
\begin{array}{ccc}
\text{hash} & \text{year} & \text{coll. res.} & \text{size (bits)} & \text{design} & \text{broken?} \\
\hline
\text{MD4} & 1990 & 64 & 128 & \text{32-bit ARX DM} & 1995 \\
\text{SHA-0 (SHA)} & 1993 & 80 & 160 & \text{32-bit ARX DM} & 1998 \\
\text{MD5} & 1993 & 64 & 128 & \text{32-bit ARX DM} & 2004 \\
\text{SHA-1} & 1995 & 80 & 160 & \text{32-bit ARX DM} & 2005 \\
\hline
\text{SHA-256 (SHA-2)} & 2002 & 128 & 256 & \text{32-bit ARX DM} & \\
\text{SHA-384 (SHA-2)} & 2002 & 192 & 384 & \text{64-bit ARX DM} & \\
\text{SHA-512 (SHA-2)} & 2002 & 256 & 512 & \text{64-bit ARX DM} & \\
\hline
\text{SHA-224 (SHA-2)} & 2008 & 112 & 224 & \text{32-bit ARX DM} & \\
\text{SHA-512/224} & 2012 & 112 & 224 & \text{64-bit ARX DM} & \\
\text{SHA-512/256} & 2012 & 128 & 256 & \text{64-bit ARX DM} & \\
\hline
\text{SHA3-224} & 2013 & 112 & 224 & \text{64-bit Keccak sponge} & \\
\text{SHA3-256} & 2013 & 128 & 256 & \text{64-bit Keccak sponge} & \\
\text{SHA3-384} & 2013 & 192 & 384 & \text{64-bit Keccak sponge} & \\
\text{SHA3-512} & 2013 & 256 & 512 & \text{64-bit Keccak sponge} & \\
\text{SHAKE128} & 2013 & {\leq}128 & \text{any} & \text{64-bit Keccak sponge} & \\
\text{SHAKE256} & 2013 & {\leq}256 & \text{any} & \text{64-bit Keccak sponge}
\end{array}
\end{equation}

In 1993, NIST published FIPS 180, the Secure Hash Standard, defining SHA-0, originally just named SHA for Secure Hash Algorithm, intended for use with the newly published DSA.  SHA-0 is a single 160-bit hash function aimed at 80-bit collision security (and now completely broken), based on the relatively new and fast design of MD4 in 1990.
In 1995, NIST quietly withdrew FIPS 180 and replaced it by FIPS 180-1 defining SHA-1, which differs from SHA-0 by the inclusion of a single one-bit rotation.  Like SHA-0, SHA-1 is a single 160-bit hash function aimed at 80-bit collision security (and now completely broken).

No public explanation was given for the change, but it was not long prior that Eli Biham had published differential cryptanalysis and the academic community realized that the NSA's tweaks to the DES S-boxes in the 1970s actually improved security (never mind that they reduced the 128-bit key size of Lucifer to 56 bits for DES, completely destroying security at the same time).  The same year, Dobbertin broke MD4[1], and the next year, severely damaged MD5[2].  Not long after that, in 1998, Florent Chabaud and Antoine Joux reported a $2^{61}$-cost collision attack on SHA-0[3].
In 2002, NIST published FIPS 180-2, defining SHA-2, a family of related hash functions with different sizes: SHA-256, SHA-384, and SHA-512, named for their output sizes and aiming respectively at 112-, 128-, 192-, and 256-bit collision resistance.  The SHA-2 functions continued the design principles of MD4, MD5, SHA-0, and SHA-1, with more rounds and bigger state.  Not long after that, in 2004, Xiaoyun Wang's team reported full collisions on MD5 and other hash functions[4], and in 2005, published a $2^{69}$-cost attack on SHA-1[5], substantially cheaper than generic.  With many of the designs based on MD4 having been broken now, the everyone got nervous about that design, so…
In 2007, NIST launched the SHA-3 competition to design a successor to SHA-2, in case the design turned out to be bad.  The competition would take place over several years.
Meanwhile, in 2008, NIST updated the Secure Hash Standard with FIPS 180-3, adding SHA-224 to the SHA-2 family, and then in 2012, NIST updated it again with FIPS 180-4 (2012), adding SHA-512/224 and SHA-512/256, faster 256-bit and 384-bit hash functions on 64-bit machines with resistance to length extension attacks that let one compute $H(m \mathbin\| m')$ given $H(m)$ and certain $m'$ without knowing $m$.
In 2013, the SHA-3 competition concluded with Keccak as NIST's chosen winner, which they published in FIPS 202.  SHA-3 includes four fixed-size hash functions, SHA3-224, SHA3-256, SHA3-384, SHA3-512, and two extendable-output hash functions SHAKE128 and SHAKE256 which attain up to a 128-bit or 256-bit security level if the output is long enough.

The design of SHA-3 is completely different from SHA-2, which gives confidence that cryptanalytic breakthroughs on line of designs based on MD4 probably won't affect SHA-3, although a decade and a half after the bloodbath of the early 2000s there hasn't been much progress on SHA-2 either.  The parameters chosen for the fixed-size SHA-3 functions were kind of accidentally overdesigned for political reasons[6], so SHA-3 functions like SHA3-256 are slower than they need to be, and you should generally just use SHAKE128 or SHAKE256.


Is there a practical security difference between OTP with letters and OTP with numbers?

There is no security difference. Of course, purely random characters with entropy rate $\log M$ where $M$ is the size of the alphabet should be independently generated and used for the OTP, whatever the size $M$ of the alphabet.


Different modes of operation have different requirements. For example, the IV for CBC mode should be generated with a CSPRNG, where as the IV for CTR mode just needs to be unique for each encryption.  In terms of cryptography, the 'random' functions found in many languages are more predictable than you might imagine.

That being said, there's absolutely no need to encrypt your IV.  It doesn't need to be secret, and can be transmitted/stored as clear text.

Encrypting the IV might add some level of security, but if you plan to do that then you should use a key which is independent of the key used for the initial encryption.  Independent not only means unique, it also means that it's derived from a different source (which can make things unnecessarily complicated).


monoalphabetic substitution perfect secrecy

IF $K$ is randomly chosen (and well distributed over the key space with size 26! - the total number of possible permutations) then each $C$ (ciphertext letter) is also equally likely. An attacker may choose any $K$ but it is impossible to gain any advantage by that; each message $M$ is still as likely as before.

Basically this scheme is a one-time-pad using a per-character permutation rather than XOR as often used.

As indicated by the first IF, what's missing is the requirement that the choice of $K$ is perfectly random. Generally we try and proof ciphers correct by looking at the set $\operatorname{Gen}, \operatorname{E}, \operatorname{D}$. The $\operatorname{Gen}$ is missing from the question.


Elliptic Curve Digital Signature algorithm fails

In the question, $p$ designates the modulus of the base field $\mathbb Z_p$, as confirmed by the fact that for  $p=977$ and the curve $y^2\equiv x^3+x+1\pmod p$, it holds that $19\times(0,1)=(396,650)$ and $17\times(0,1)=(699,739)$.
Problem is, in other steps, the question reduces $r$, $s$ and related quantities modulo that same $p$, rather than modulo the order $n$ of the group generated by $G$. That's more than enough to cause the observed failure.
As an aside, the ECDSA specification requires that $n$ is prime . In the question, the curve and $G$ is such that $n=987=3\cdot7\cdot47$ is composite. One consequence is that nearly half the choices of $\text{random key}$ are invalid, and I'm uncertain about if it otherwise makes some signature unverifiable. We do not care about the possible security implications since $p$ is so small as to make the whole thing insecure anyway.
I suggest $p=1033$, which will give a prime $n=1061$.


Well, successive calls rand() just produce numbers that "look random".

Now, rand() doesn't take a seed; that means that everytime the program runs, calls to rand() will generate the exact same sequence of numbers.  This is a deliberate design decision; that means that the program behavior is reproducible (which can be important if you're debugging).  If you don't want this behavior, well, that's why srand() is provided.

As for what "looks random" means, well, it essentially means "if you eyeball the output, no obvious pattern jumps out at you".

When working with cryptography (you did ask in the crypto stack exchange), we don't have much use for rand(); even if you feed in a seed via srand(), that seed is generally too small to be useful, and even if the rand() output isn't obviously patterned, crypto has much higher criteria for randomness.

On the other hand, other uses need not have such high standards.  I believe rand() may be useful within some randomized algorithms; just not cryptographical ones.


As CodesInChaos notes in the comments, having more ciphertext–plaintext pairs doesn't help with brute force guessing attacks.

Well, that is, except for the minor issue of unicity.  Basically, to narrow the results of your brute force attack down to a single key, you do need to have enough ciphertext–plaintext pairs that the length of the known plaintext exceeds the length of the key (by some reasonable amount — but one extra cipher block is more than enough).

For example, if you were trying to break AES-256 using just one block (i.e. 128 bits) of known plaintext (and somehow had a magic supercomputer that could actually test 2256 keys by brute force), you'd end up with about 2128 false positives — wrong keys that produce the correct ciphertext for the known plaintext block just by chance — in addition to the correct key.  Testing a second ciphertext–plaintext block pair would narrow that down to just one false positive (on average; you might get none, or you might get two or even more if you're unlucky), and a third pair would almost certainly (with probability about 1 − 1/2128) eliminate the false positives completely.

So you do need at least two, and preferably three, blocks of ciphertext–plaintext pairs to uniquely determine the correct key for AES-256.  For AES-128, one block may be enough if you're lucky, but you preferably want two.

All that said, having even more ciphertext–plaintext pairs than that won't help with brute force attacks — once you've got enough to uniquely identify the correct key, any more is useless.

Having more known plaintext does typically help with cryptanalytic attacks.  For example, the biclique attacks of Bogdanov, Khovratovich and Rechberger can, given 256 ciphertext–plaintext pairs, speed up AES key recovery by a factor of about four (4 = 22) compared to simple brute force.  Obviously, this is still a completely infeasible attack in practice, but it does mean that, technically, having more ciphertext–plaintext pairs does make AES key recovery faster.  (Well, that is, except for the fact that the extra complexity of the biclique attack would almost surely slow it down by far more than the factor of 4 that it theoretically gains over plain brute force, were anyone to try to actually implement it.  But in principle it works...)

Similarly, the related-key attack by Biryukov and Khovratovich requires about 299.5 ciphertext–plaintext pairs, encrypted under distinct keys satisfying a specific relationship, to recover the actual keys for AES-256.  This is still not a practical attack, and using properly chosen keys (generated randomly or using a secure KDF) defeats it completely, but it is technically an example of a situation where having more (suitably chosen) ciphertext–plaintext pairs helps to recover the key.

In any case, the reason why you should not use ECB mode has nothing to do with key-recovery attacks.  (In fact, ECB is generally no worse than any other mode of operation in this respect.)  Rather, the reason ECB mode is insecure is simply that it leaks which plaintext blocks are identical, and thus isn't semantically secure.


Is there a cumulative commitment scheme?

It sounds like you are thinking about this the wrong way.  Verifying a commitment is very fast, if you choose the commitment scheme properly.

In particular, I recommend that you use a hash-function-based commitment scheme: C(i) = Hash(x(i) || open(i)).  Then verifying an opened commitment requires just one hash evaluation, which is very fast.  Based on my measurements with openssl speed sha1, you should be able to verify several million commitments per second, if you use a SHA1-based commitment.

The question talks about modexps.  That suggests that you are considering the wrong kind of commitment scheme.  Modexps are much slower than hash evaluations.  If you are choosing a modexp-based commitment scheme, you are going to end up with something significantly slower than the best possible.  Rather than trying to make up for the suboptimal choice of commitment scheme by looking for fancy batching tricks, I recommend you simply move straight to a fast commitment scheme (based on a cryptographic hash), and then you won't need anything fancy.  My guess is that straightforward use of a hash-based commitment is going to be faster than any modexp-based commitment scheme, even with batching.


TLS Handshake : Server authentication or only Server ‘s Certificate authentication?

But if Server’s certificate is checked sucessfully by Client, how is
  it possible to consider that Server has been authenticated by Client,
  while at this time none message signed with Server’s private key has
  been sent to the Client and verified by it ?

If only consider the key exchange to be what the RFC says it is, then yes this key-exchange can be broken by an attacker having the right certificate.

However this is not how TLS works in practice. In practice you'd never stop after the ClientKeyExchange message as you have set-up the connection to actually do something. This is why most formal analysis considers ChangeCipherSpec and the Finished messages as part of the key-exchange for their proofs.
And it only matters that the server is successfully authenticated after they complete key-exchange, not at some "randomly chosen" point in the protocol.

The exchange turns out to be secure and properly authenticated by verifying the Finished message which contains a MAC on all previous (handshake) messages. Because a fake server can't decrypt the pre-master secret and hence can't compute the master secret, he can't compute the neccessary MAC and the client will respond with a fatal_alert, killing the connection.

I don't know why the designers of TLS chose this "through the backdoor" authentication method but I can only guess they wanted to avoid yet another computationally intensive private key based operation for the server.

TL;DR: The finished message gives you authentication with its MAC only being available to the private key holder.

  Is it correct to talk about "Authentication by Certificate"
  (assuming based on Certificate verification via CA root public key)
  instead of authentication via digital signature?

You never authenticate by only presenting a certificate.
The only situation where you may do it is with secure tokens holding key-files to access some physically restricted facility where the tokens will never actually be plugged into a real computer (aside from new file assignment).

In an internet-based scenario you'd never do this as every eavesdropper could impersonate the owner of the certificate, rendering it completely useless.

What TLS does (and may be meant by your question) is encryption-based / certificate-based authentication. This is basically some sort of challenge-response protcol, where you send some party a random nonce and an asymmetrically encrypted key and expect the MAC on the nonce using that key as response. One can do that, but this is rather "abusing" the encryption to do things it was not intended to, as we have dedicated constructions for that: digital signatures.
So usually a designer would rather go with a digital signature and an encryption ( / decryption) (or even better DH) as today it's pretty cheap to do both operations, whereas you may need to use the encryption based approach for very constrained devices where only one such operation is "allowed" / feasible or where actually can't perform signatures (by padding, rather unusual).

TL;DR: Solely certificate based authentication is bad and only feasible in physical access restriction scenarios and otherwise you can do challenge-response with encryption but should prefer signatures.


Changing an Encryption scheme from AES to ChaCha20

Now, how feasible it is to move from AES to ChaCha20? What are pros and cons of this?

This entirely depends on the platform and implementation. There's no way we can answer this definitively. However it's usually not particularly difficult to change one cipher to another.

Will ChaCha20 be faster than in-built hardware support for AES?

Software ChaCha20 will be slower than hardware AES, but not by much. It will however be much faster than software AES, which is why many people use it. It's also easier to write a side-channel-free implementation in software (hardware AES is resistant to side-channel attacks, but software implementations of AES that are resistant are often much slower).

Can ChaCha20 provide better security over AES over the years?

No way to know. They're both very secure and show no signs of meaningfully weakening.

Do we have any comparison document where it shows performance(cipher speed) over various resolution starting from 576i to 4K over various bitrate from 2mbps to 20 mbps?

A cipher doesn't care about resolution, just data. Any data-based comparison would require knowing exactly what hardware you use and what software you run on it. Let's assume ChaCha20-Poly1305 vs AES-GCM. The answer is simply that the former is faster in a software-only implementation, but AES comes out ahead if the device has anything like AES-NI (even more so if it can also accelerate GCM with something like PCLMULQDQ). But you're probably looking in the wrong place for an optimization. You won't gain much speedup by switching ciphers.

Related: What's the appeal of using ChaCha20 instead of AES?


The main reason is that true random data is hard to obtain; whether it is from:

A user's password since people only remember them so long
Or from a random source such as an operating system that reads random measurements like disk latencies since it can only produce so much randomness per unit time.


Could affine transformation mod 2^128 be a side-channel attack problem

I do not know of this cipher; however, if you explicitly calculate everything, ie: do not use arrays or lookup tables, you are not susceptible to timing attacks.  Basically, you treat the mathematics like you are on hardware, using only base logic, and it's quite slow, but it's safe because it takes equal time to calculate every value.
Having said that, you basically could not easily calculate something that large in this manner.  $2^{64}$ is a huge number, and 64-bits quickly explodes into something large in the world of logic gates.


The signature validation logic from RFC7091 is effectively:

$$r \stackrel{?}= abs( h^{-1}sP - h^{-1}rQ )$$

where $r, s$ are values from the signature, $h$ is the message hash (converted into an integer), $P$ is the EC group generator, and $Q$ is the public key, and $abs$ is a function that maps a point to its x coordinate.

You know everything except for $Q$; you can recover that by using simple algebra; you would find the two points $R, R'$ with $r$ as an x-coordinate, and then $Q$ is one of:

$$r^{-1}(sP - hR)$$
$$r^{-1}(sP - hR')$$

(where you compute $r^{-1}$ modulo the curve order)


Is it safe to use same private key in two or more EC signature algorithms?

In general, using the same key in different algorithms is bad practice, and indeed having two public keys on different curves with the same private key could reveal information. I don't know how, but I am sure that you cannot prove a reduction from one to another (unless you can map one group to another, which is doubtful).

Having said the above, if you use the same curve, but just different algorithms for signing, then I believe that one could prove security (but I won't do all the details). This is because EdDSA is actually a Schnorr signature, and so it is a zero-knowledge proof of knowledge of the secret key, secure in the random oracle model. Thus, one could proof that if you can break ECDSA given ECDSA and EdDSA signing oracles, then you could break ECDSA given only an ECDSA signing oracle (by simulating the EdDSA signing oracle yourself in the random oracle model). Thus, if ECDSA is secure then using the same key for Schnorr doesn't harm anything.


Public key encryption and decryption with private key

You are trying to encrypt and decrypt with AES, which is a symmetric algorithm, using your RSA keys (which are meant to work with RSA, which is an asymmetric algorithm).

To use AES, both sides need to know the same secret key - there aren't separate public and private keys. The way you would usually do this is to choose a random secret key for AES (often called a data encryption key or DEK), encrypt the file using that key and the AES algorithm, then use RSA to encrypt that DEK using your friend's public key. You would give your friend both the encrypted document and the encrypted DEK. She would decrypt the DEK first using her RSA private key, then use the recovered DEK to decrypt the document. This technique is commonly called envelope encryption.


Is there any general description language for block ciphers?

I think what is meant by this paragraph is the language defined in report NES/DOC/TEC/WP2/007/2, "A System for Assisting Analysis of Some Block Ciphers", by Arueh Bibliowicz, Pnina Cohen, Eli Biham. It is listed on the "NESSIE public reports" page.

The language is something like a special-purpose programming language for block ciphers. It supports functions (with special notations for S-boxes and "Selections", rounds, key schedules), variables, constants, primitive arithmetic/binary operations (AND, OR, XOR, ADD, SUB, MULT, ROL, ROR, SHIFTL, SHIFTR).

The appendix contains DES as an example.

The analyzer tool mentioned there (which interprets the language and does some automated cryptanalysis) seems to be not public, though.


Security when using same salt for different passwords, compared to using different salts?

For example, someone suggested improving UNIX authentication by defining 3 different passwords for a user that are stored in the shadow file. All three passwords are stored with the same salt value. When a user wants to authenticate to some system, he must provide in the i attempt to login, the i mod 3 password. For example, in the first attempt he will provide the first password, in the second and fifth attempt he will provide the second password. Is such alteration to UNIX system increases security or not?

I cannot see how it increases security. As long as you don't limit the amount of attempts the attack surface only increases.

  what happens when all passwords are stored with different salt value?

You cannot see if one of the three passwords is identical to one of the other three. The reason to choose an identical salt is presumably to make sure that each password is different from each other.

Note that the passwords could still be very similar. The only way to check that is to compare the three passwords and for that you need all passwords at the same time.

It would also decrease attack speed by a factor of three (as an attacker cannot check a candidate password against all three hashes). This is of course assuming that the attacker obtained the hashes in the first place or that the password validation is sufficiently fast.


Do you really need a KDF when you have a PRF?

Maybe.

The security contract of a PRF requires that the key be a uniform random bit string.  If you have a DH secret or a diceware phrase, then what you have is not uniform random as a bit string, and so your contractual obligations are not satisfied and the PRF may give no security.  You need something a little stronger to hash a DH secret or diceware pass phrase into a uniform random bit string, which is what the ‘extract’ step does.

Here's an example.  Let $F_k$ be a PRF and let $H$ be a random oracle.  Define $$F'_{x,y}(s) := F_{H(u)}(s), \quad u = (y^2 - x^3 - 7) \bmod p,$$ where $p = 2^{256} - 2^{32} - 977$.  $F'$ is also a PRF, because when $(x, y)$ is uniformly distributed among 512-bit strings, the probability of collisions in $u$ is small.  But if $(x, y)$ is the outcome of a DH key agreement on secp256k1, then $y^2 \equiv x^3 + 7 \pmod p$ so $u$ is always zero and hence $F'_{x,y}(s) = F_{H(0)}(s)$ for all $x$ and $y$—that is, the DH key agreement doesn't affect the output at all, so the system gives no security whatsoever!

If what you have is a uniform random bit string as a master key already, and you just need to derive subkeys from it with distinct labels, then a PRF is all you need, and the ‘expand’ step is, in fact, a PRF.  If you look closely at HKDF, for example, you will see that $$\operatorname{HKDF-Expand}_k(L) = \operatorname{HMAC-}\!H_k(L \mathbin\| \mathtt{0x01}),$$ if the desired output size matches the output size of $H$; if more bytes are requested, just repeatedly call $\operatorname{HMAC-}\!H$ with consecutive counters and the previous chunk prepended to $L$, and concatenate the outputs.  You could, of course, substitute for $\operatorname{HMAC-}\!H$ your favorite PRF like keyed BLAKE2b, KMAC128, KangarooTwelve, Kravatte, prefix-keyed Gimli-Hash, or ChaCha $\circ$ Poly1305, and while it wouldn't be HKDF it would be just as good for deriving subkeys.

  My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo a number that is not a power of 2, and is thus non-uniform if represented as a bit-string).

Correct: The purpose of collecting the concepts of extract-with-salt and expand-with-label into a single term KDF is that often the two steps are close by—you have a DH secret, or a master diceware phrase, which is not uniform in bit strings but which has high entropy, and you want to derive many secret keys from it for different labeled purposes.

  Yet, I am not sure there are modern symmetric algorithms that require the secret to be uniformly distributed. Sure their security might be defined with a uniform key, but using a KDF feels a bit like a cheat since there is no new entropy added, and it's not slow either. Am I missing something?

The security contract for many cryptographic primitives requires the input to be uniform random.  Violate the contract, and the security may evaporate.  Obviously you can choose the input by a pseudorandom function under a uniform random key—if that broke the composition, merely using the composition would then serve as a distinguisher for the pseudorandom function.  But it's not a priori clear whether highly structured keys like the bit encodings of points on particular curves might be exploitable in downstream cryptosystems.  Maybe you'll be bitten by a bad interaction like in the contrived secp256k1 example above; maybe you won't be.  Using HKDF-Extract, or otherwise hashing the input, renders these concerns moot so you don't even have to think about them.


Suppose that you generate a brand new RSA key pair, that you will use, say, to authenticate yourself when connecting to a SSH server. This will be done through some library that implements RSA key pair generation (say, OpenSSL). That library will produce the key elements by generating random integers of the right length until such integers appear to be prime number.

The random generation uses a seed obtained from "true randomness" and then expanded into an arbitrarily long sequence of random bits with a cryptographically secure PRNG. The point is to make it infeasible for an attacker to predict the bits you came up with.

Now suppose that the seed is of low entropy (e.g. 40 bits) or the PRNG is poorly designed and reduces the entropy. Saying "40 bits entropy" more or less means "there are only 240 possible values for the seed or internal PRNG state". Take note that in the synthetic description above, the conversion from seed to generated private key is completely deterministic. Thus, an attacker can generate all these 240 states, and, for each of them, work out the private key that your application would have come up with, starting with that seed value. It then suffices for the attacker to check these keys against your public key (which is public, as the name says) to learn your private key. And impersonate you. Which is bad.

This actually happened in Debian in 2008 and people had to regenerate new SSH keys (both client and server).


Which is faster, PRF based on AES-CTR and PRF based on BLAKE{2,3}?

As @SEJPM pointed out above, there's no one answer to this question. Everything varies based on what hardware you've got and what the length of your input is. As a first step, I'd start by looking at SUPERCOP performance measurements. You can find AES-CTR measurements at https://bench.cr.yp.to/results-stream.html, and BLAKE3 measurements at https://bench.cr.yp.to/results-hash.html. There's an enormous amount of data in both pages, because there's a lot of different hardware to consider. (And of course, lots of stream ciphers and hash functions to measure.)


security in format preserving encryption

Usually FPE is $Rank-LPE-DeRank$ Where LPE is length preserving encryption. The advantages of FPE schemes Preserving Formats and Lengths could be used against it too.

There are two attack vectors specific to FPE (but they are by design !)

Length Preserving
This might aide to brute force attacks if the domain is too small. For example encrypting an IP Address using FPE , the Cipher text is just $32$ bits, Where as encrypting with traditional AES would result in $128$ bits.

Inferences
FPE ciphers may reveal more inferences about the underlying data. For example encrypting an IP Address still looks like an IP Address, this leaks inference that the underlying  data types are.  An attacker getting access to encrypted logs might find it difficult to guess what the underlying data is if it looks random strings but if the encrypted logs have format preserving data this might leak the nature of the data is. One could argue this to be advantage too data that does not look random might not raise any suspicion etc.

It also depends on the over all system design what additional layers of security exist.

Also this particular paper[1] explains in much detail in theoretical jargon.

[1] http://arxiv.org/ftp/arxiv/papers/1506/1506.04113.pdf


Are there any masking methods for integer multiplication masking?

Generally speaking, there's not a way to mask the power of a circuit without dual-rail encoding.  With dual rail encoding, you pass but $x$ and $\bar{x}$ so that have skew free, self-clocking circuits; however, an separate advantage is that you mask the power.  Although this is used in asynchronous systems, it's fine in a synchronous system as well, and showed up in literature in 1955.

HSPICE does model the meantime to collisions in the circuit well, so you don't see the "hiss" of the transistors.  In fact, no models actually describe channel noise.  If you break the multiply unit into an addition-based Montgomery tree, it will be constant time and the power will likely disappear into the noise floor if you do it at either a bit or byte widths.   If you have a device physicist handy, you can likely prove that the change in power with bits is not actually able to be seen on a "unit scale".


Is OMEMO vulnerable in case of compromised jabber server?

Suppose Alice has never met Bob before—never in her life heard of this ‘Bob’ personage.

Bob initiates a chat with Alice over a Jabber server, which facilitates (a) sending the messages along, and (b) giving Alice and Bob each others' public keys for the first time.

They do a Diffie–Hellman key agreement, of course, so that a passive eavesdropper has no hope of finding the conversation key from the network transcript (more details of how it works).  But Mallory, a NITM (enby-in-the-middle) may have compromised the server.  Here are three possibilities:

The server is honest and uncompromised.  In this case, Alice and Bob get to have a secret conversation about how many Nazis are on Twitter and how many statist tools advocate state surveillance and censorship to suppress the Nazis without realizing—or perhaps without saying—how dangerous state censorship regimes are for marginalized groups like queer people.
The server is compromised by the NSA.  In this case, Alice is actually having a conversation with her personal FBI agent Mallory, who is collecting dossiers on anarchist agitators like me who threaten authoritarian state surveillance regimes.
The server is honest and uncompromised, but Bob is Alice's personal FBI agent Mallory who is collecting dossiers, etc.

If Alice has no prior information about Bob, she has no way to distinguish these cases, no matter how secure the protocol is.  It's the same for OTR, OMEMO, WhatsApp, Signal, the post, or Twitter.


No, if it is possible then it defeats the purpose of using salts. For example, one can build one rainbow table, mapping each possible password together with a fixed salt value to a hash value. Then given another salt value and password hash, one can find the password in the table if what you asked is possible.


LFSR for small numbers with large periods

Contrary to what's stated in the question and its comments, extracting any $m\le n$ bits from the sequence of the states of an $n$-bit LFSR still result in a sequence with period $2^n-1$, assuming the state of the $n$-bit LFSR is not zero and its generating polynomial is primitive. Proof sketch: by a fundamental property of LFSR with primitive feedback polynomial, its period has $2^n-1$ states not including the all-zero state. It follows that any bit has period $2^n-1$ with $2^{n-1}$ ones and $2^{n-1}-1$ zeroes.

Further, the sequence is as closely evenly distributed as an $m$-bit sequence of period $2^n-1$ can be: each of the $2^m$ values is reached $2^{n-m}$ times, except $0$ which is reached $2^{n-m}-1$ times. In fact, that's much too evenly distributed to be random.

Hence taking (say) the low 5 bits of a maximal-length 16-bit LFSR will result in a sequence with period 65535, and during that period each of the 32 values will be reached 2048 times, except 0 reached 2047 times. However that's NOT going to make even a passable non-cryptographic RNG: if the LFSR uses the Fibonacci construct, 4 bits of any output directly come from the previous output, and the situation is hardly better with a Galois construct (or not at all, depending on polynomial). For example, using the 16-bit generator in the updated question (which, per the convention I favor, use the polynomial $x^{16}+x^5+x^3+x^2+1$ rather than its reflexion $x^{16}+x^{14}+x^{13}+x^{11}+1$)

#include <stdio.h>
int main(void){
  unsigned x = 1, j = 128, y; // initial sate, number of outputs, output
  do {
    y = x&31;
    printf("%02X%c", y, --j&15?' ':'\n');
    x = x>>1 ^ 0xB400&-(x&1);
  } while(j);
return 0;}

we get this:

01 00 00 00 00 00 00 10 08 14 1A 0D 16 0B 05 02
01 00 10 08 04 02 11 08 14 0A 05 02 11 18 0C 16
1B 1D 1E 0F 17 1B 0D 16 0B 15 1A 0D 16 0B 05 02
11 08 04 12 19 1C 1E 0F 17 0B 05 12 19 1C 0E 17
1B 1D 0E 07 03 01 10 18 1C 0E 17 1B 1D 1E 0F 07
13 09 14 0A 05 12 19 1C 0E 07 13 19 1C 1E 1F 1F
1F 1F 1F 0F 07 13 09 14 1A 1D 0E 07 03 01 10 18
1C 1E 1F 0F 07 13 09 04 12 09 14 0A 15 1A 1D 1E

and it is painfully apparent that the right hex digit of any output is always the previous output right-shifted by 1.

One possible solution to that is to steps the LFSR $m$ times for each output of $m$ bits, collecting 1 bit at each step. One problem is that when $\gcd(m,2^n-1)\ne 1$ the period is reduced by that factor (and the proof of even distribution no longer works).

Rather, I formerly proposed to output y = ((0x6D9B*x+0xDB75)&0xFFFF)>>11. It does improves things, but some of the problem with y = x&31 remains: the distribution of two consecutive outputs is quite poor. Something like y = 0x6D9B*x, y = (y<<4 ^ y)*0xDB75, y = (y<<2 ^ y)>>11 & 31 further improves things, while provably keeping the period and uniform distribution (because, until the >>11 & 31 steps, the transformation from the low 16 bits of x to the low 16 bits of y is a mapping).

Caution: even perfecting that by using an even more complex transformation of output, the resulting sequence is not cryptographically strong, by any measure, and can't be made so without much more state bits.


Can we place the WOTS scheme into a Merkle tree structure?

This question is essentially "can we put the HORS scheme on a tree".  And the answer is yes, as it is the basically HORST.
The question adds confusion by mentioning a Merkle tree and not mentioning an index.  The actual question is (or should've been) "can x HORS public key sets be put on trees with each HORS tree being used to sign each of the x bytes".
Maybe it is not normal to think of HORS/T as WOTS compressed (or Lamport inflated) on an index/tree, but I will leave the question in case it helps anyone else who does.


Not all encryption schemes have the property that all strings are ciphertexts of something. For instance, if you created a version of RSA where you added an extra 0 at the end of every ciphertext, this would still be a valid encryption scheme, but any ciphertext with a 1 at the end would not be an encryption of anything.

In a public-key cryptosystem, to prove that a ciphertext is an encryption of something, you can prove that you have some plaintext $x$ such that $Enc_k(x)=y$ where $k$ is the public key and $y$ is the ciphertext.

There are generic techniques which allow you to create proofs of arbitrary computable statements, namely that you know some value $x$ such that $f(x) = y$. There are also generic techniques that allow you to do this in a non-interactive way. By definition, these techniques reveal nothing about $x$ except that it satisfies the given statement.

Note: For certain functions, we know of more efficient ways to do zero knowledge proofs. Some answers in the question you posted refer to some more efficient ways of doing this in the case of public key cryptosystems. But for any computable function there is always some way of making a zero-knowledge proof using generic techniques.

EDIT

I don't really understand how the generic protocols work under the hood, but I do understand the following:

First, you can represent the function as a circuit. As long as you have bounds on how long a function will take to do this (e.g. the max number of iterations of a for loop), you can always represent a function this way. (May not be very efficient though.)
Then you convert the circuit into a list of constraints that need to be satisfied. This article by Vitalik Buterin has, among other things, a good explanation of how this step is done.
Finally, there are tools such as libsnark that, given a set of constraints and a correct input provide a way to generate a Short Non-Interactive Argument of Knowledge (SNARK) that the constraints were satisfied. This is the part where I don't understand how it works.

By Non-interactive, it means that once the person encrypting has generated a SNARK, $\pi$ that they know the plaintext to a ciphertext $y$ and has sent this proof to the verifier, no more interaction is needed. Since no interaction is needed, anyone who gets access to $\pi$ and $y$ can verify that $y$ is an encryption of something.


Figuring out seed/internal state from HMAC-MD5 output

If you could do that, then you could publish a paper about how you did it in a top-tier cryptography journal!

Currently, MD5 remains unbroken against preimage attacks.  Even if the underlying compression function turned out not to be a PRF, which would render moot the standard security reduction of the PRF-security of HMAC over a Merkle–Damgård hash function like MD5 to the PRF-security of the underlying compression function, it would be a remarkable feat to actually recover the key.

You have a much better bet trying to guess the state of the Python random number generator, which is probably the notoriously bad Mersenne twister.  Finding how to do that is left as an exercise for the reader!


You could use the hash value as seed for a deterministic CSPRNG and then use a prime number generator also used for RSA key pair generation. Note that the size of the prime number must be relatively high (1536 bits for 128 bits of security, e.g. for an RSA key of 3072 bits).

The usual caveats of deterministic RSA key pair generation apply. For instance, the algorithms must remain the same, otherwise a different prime value is calculated for the same hash value.

Generally the method of generating the prime value is available separately in math or crypto libraries that come with the runtime. For instance, Java has the BigInteger(int bitLength, int certainty, Random rnd) constructor.

Beware that the time it takes to find a prime is unknown in advance. The generation may take a long time (and in the case of Java may also take a ridiculous number of bytes from the DRBG - just tested this).


Can Base64 be seen as a way of encryption if we use different index table?

Can we see Base64 with this new table as some sort of [..] encryption [...]?

Yes, technically it does constitute a form of encryption as knowledge of a secret key is required to recover plaintext from ciphertext.

  Can we see Base64 with this new table as some sort of safe encryption [...]?

NO! This is essentially a monoalphabetic substitution cipher applied on the Base64 encoded data. This can be seen as you can always take your table $T$ and then find a new $T'$ that undoes the base64 table encoding first and then applied after standard Base64 encoding.

Now while the key size is (theoretically) respectable with $\log_2 (64!)\approx 296$ bit, this cipher suffers from all the usual problems such ciphers have, including:

Ciphertext-only attacks are possible using frequency analysis, as there are only 64 valid plaintext values and they will probably occur with different frequencies.
Known- and chosen plaintext attacks are devastating as there are only 64 mappings to be uncovered and usually plaintexts have quite a bit of structure allowing to guess the rest / uncover significant parts of the plaintext.


DES key schedule takes the 64-bit key and PC-1 (Permuted Choice 1) discards the parity check bits and applies a permutation to the remaining.

Then for the rest they key bits are divided into 28-bit halves and for the each round

They are rotated left one or two specified for each round. Then
48-bit bits are selected by PC-2 (Permuted Choice 2) which is another permutation that discards some bits.

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline
\text{Number of Round} & 1  & 2 & 3& 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16\\ \hline
\text{Number of Left rotations} & 1 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 2 & 2 & 1 \\ \hline
\end{array}

  Is there a known way to use these round keys to reconstruct the original secret key from it?

Giving a round key of DES, apply reverse PC-2. With this, you will get the 48-bit of the 56 bits key. You can either complete this by using brute-force for the remaining key bits or use another round key to fill the missing 8 key bits.

  Is there a feasible way to reconstruct the key from the (Triple-)DES round key?

For the Triple DES, you need round keys for each different DES key if the keys are independently generated.

Though the reversibility of a key schedule is not really required, for older systems non-reversible key schedule makes the decryption require more process time or more memory.


What's an entropy measure for the sequence $0, 1, 0, 1, 0, 1, ...$?

Let's just fill it in! Your generator has two possible outcomes, both with certain probabilities. For the every element of your sequence, you're certain about its outcome, thus:

\begin{align*}
E(S)&=-p_0\log p_0 - p_1\log p_1\\
    &=-p_0\log p_0 - (1-p_0)\log (1-p_0)\\
    &\mathrel{\mathop{=}_{p_0\to1}} -1\log 1 - 0\\
    &=-1\cdot0=0
\end{align*}

Seems like your source does not convey any information (zero bits), because indeed you already know what it will produce! Talking about entropy of a source only makes sense when the source has a stochastic behaviour; when it has an element of unpredictability.


Understanding padding oracles - is an attack plausible in my scenario?

If I understand your scenario correctly, padding oracle attacks are probably not a massive concern, but not for the reasons you seem to believe. Padding oracle attacks have nothing to do with maintained open channels, lack of garbage collection, or time the cipher is kept in memory.

A padding oracle attack requires two things: a ciphertext whose contents you wish to read, and a "padding oracle": more or less, a way to tell if a ciphertext that you've forged passed through the decryption algorithm successfully. If you never decrypting information directly received from users, then you are probably not significantly vulnerable. If users can supply ciphertexts to be decrypted, you are probably vulnerable. If an attacker can write to your database through something like SQL injection, you retrieve and decrypt ciphertexts from the database, and your service can be instructed to decrypt something stored in the database, you have bigger fish to fry, but you are probably also vulnerable to padding oracle attacks.

Long story short: if it is at all plausible that an attacker can feed you ciphertexts to decrypt, you should authenticate ciphertexts. Consider also if the contents of your ciphertexts should remain secure even in the face of other exploits. Since it's very hard to reason about what a motivated attacker might be able to do if given access to your system, you should absolutely default to using an AEAD mode unless you have a overwhelmingly compelling reason not to.

With that out of the way, you should highly reconsider how you handle passwords and encryption keys. SHA-512 by itself is not "key stretching", and the left half of SHA-512 plus bcrypt for digests, plus the right half for keys is tantamount to sprinkling cryptography around like magic pixie dust, expecting it to magick away security concerns.

For password digests, you should use BCrypt. SHA-512 plus BCrypt is probably not worse, per se, but it's unnecessary, and gains you nothing.

Your key derivation, however, is extraordinarily weak. SHA-512 is fast, and an attacker can trivially brute force his way through common passwords and use trial decryption to expose ciphertexts of users with weak passwords. You should use an actual key-stretching function such as PBKDF2. For each user, generate a cryptographically random 128-bit value. Compute the PBKDF2 of the user's password using this value as the salt, SHA-256 as the PRF parameter, an output length corresponding to the key length of your encryption algorithm (16 bytes for AES-128, 32 bytes for AES-256), and a number of iterations calibrated to take around 0.1s on your server hardware. Store the number of iterations and the salt. The output of this function should be used as your encryption key.

And, of course, don't overlook generating unique IVs for each encryption with a given key.


What is the name of this kind of protocol

The name I would use for this protocol is "broken".

It is insecure.  An eavesdropper gets to observe $Q_0 = P \oplus CM$, $Q_1 = Q_0 \oplus SM = P \oplus CM \oplus SM$, and $Q_2 = Q_1 \oplus CM = P \oplus SM$.   Notice that we have the relation
$$Q_0 \oplus Q_1 \oplus Q_2 = (P \oplus CM) \oplus (P \oplus CM \oplus SM) \oplus (P \oplus SM) = P.$$
Therefore, an eavesdropper who xor's the three messages he observes can recover the message $P$.  In other words, this protocol is completely insecure.

If I recall correctly, I believe that an early version of the Bluetooth specification used this algorithm for key exchange.  Fortunately, the error was caught and fixed.

You may be thinking of the three-pass protocol for key exchange.  It is basically the same concept as what you have, but using something other than xor.  With xor, this is insecure, but if you replace xor with an appropriate other operation, you can get something secure.  The most well-known instantiation is to replace xor with Pohlig-Hellman exponentiation-based encryption.  In that scheme, we set $Q_0 = P^c \pmod{p}$, $Q_1 = Q_0^s \pmod{p}$, $Q_2 = Q_1^{c^{-1}} \pmod{p}$, and then S can compute $P = Q_2^{s^{-1}} \pmod{p}$, where everything is done modulo a large prime $p$.  However, the three-pass protocol has no advantages over standard public-key key-exchange systems, so it is rarely (if ever) used.  For instance, its security is roughly equivalent to the security of Diffie-Hellman key-exchange, so it has no clear advantages over Diffie-Hellman or RSA.


Stuck on finding M2 knowing M1 in One Time Pad

If you know M1 XOR it to both sides of M1 XOR M2 = C1 XOR C2 which gives you M2

  M2=C1 XOR C2 XOR M1

Even if you didn't know M1, if it is long enough it (or M2) might have a common substring, i.e., a crib such as "the", "this".

You might use the crib as an estimate of part of M1 to obtain a guess for a part of M2 by using the equation above focusing on 3 letter substrings.

If you obtain as M2 a substring that looks like it could be English, you may have guessed part of the OTP key.


Why are ed25519 keys not recommended for encryption?

You seem confused about a few things.  Bear with me, this is a very common confusion!
Encryption is defined with the intent of confidentially transporting information: if you encrypt information, it is meant to be hidden until decrypted by the receiving party.  Note that in your pseudo code
hash = doHash(message)
signature = doAsymetricEncrypt(hash, privateKey)

hash == doAsymetricDecrypt(signature, publicKey) //true

... it is impossible to retrieve message from your "ciphertext" signature: you can only retrieve the hash.  Secondly, you are encrypting with a private key, and  decryption happens with the public key, which means that any party can decrypt your hash, because your publicKey is obviously public.
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents (wikipedia).  Note that this is never defined in terms of encryption. Let me stress this: if you have a teacher that claims that "a signature is an encryption with a private key", they are wrong.  If you have a book that claims this, throw it out, burn it -- don't give it away, because it clearly causes confusion -- and get a better book.  Encryption is for confidentiality, signatures are for authenticity.
That said: the source of this confusion is in the mathematics of RSA.  In RSA (and not in ECC!), the operator for text-book signatures is the same operator as for encryption, with the key material swapped.  Note that the mathematical operation is the same thing, not that signatures "are encryption with the key swapped", although they look like they do.  Also note that this is for text-book RSA, which is never deployed as-is, but requires padding and randomization that is different between signatures and encryption.
So, while your pseudo-code might or might not work with RSA (depending on the library you use), it will not be secure at all, and will simply not work with ECC because the key material cannot be swapped, because the mathematics behind it simply do not support it.

Now, to finally answer your question, encryption with elliptic curves exists, is widely used, and is called ECIES. It indeed boils down to a Diffie-Hellman exchange and using a symmetric algorithm afterwards.  There is also ElGamal encryption, if you have very short messages.
It is another question whether it is secure to reuse the same key for ECIES and EdDSA signatures at the same time though.


Why RSA-sig authentication VPN need its own private key?

In my understanding, RSA-sig authentication only requires its own Public Key so that the peer authenticates it using Root CA's public key.

No, that is not how PKI (Public Key Infrastructure) works.  Yes, the CA does issue a certificate (authenticated by the root CA's public key), however the certificate just says "this specific public key corresponds to a private key owned by themasterplan".
That is, a certificate is a way to bind a public key (which is a series of random-looking bits) to an identity (a label that is meaningful to the reader of the certificate); it is one way to solve the question "how do we know that this particular public key is from who we want to talk to".
So, to meaningfully authenticate yourself with a certificate, you need your own private key (so that the certificate can refer to your public key); that is the public/private key that StrongSwan requires.
And, a StrongSwan service authenticates itself by sending its certificate (so that the peer knows and can verify the public key), as well as a signature (to prove that the StrongSwan implementation has the private key that the certificate refers to).


Where can I read about DER certificate structure - fields and its registered values?

ASN.1 is defined by the International Telecommunication Union (the ITU). ASN.1 stands for Abstract Syntax Notation One, and is a schema definition language. DER, as well as its base form BER, are serialization formats of the data defined by the ASN.1-specified schema.
ASN.1 and DER/CER/BER are specified in ITU-T-X series standards, available at the official ITU website. Information about OIDs are available at http://oid-info.com/


The PGP, which is well known, uses what is in your mind, hybrid solution. Here a short documentation for your cause.


What is the difference between forward secrecy and key freshness?

The term ‘perfect forward secrecy’ is bad.  Rather than talking about whether a protocol has perfect forward secrecy, you should talk about when in the protocol you erase keys.  Then, although ‘key freshness’ isn't a common technical term in cryptography, this suggests a clear answer:

Key freshness is presumably about when you generate new keys so that future interactions can't be broken even if the old keys are compromised.
Key erasure is when you erase old keys so that past interactions can't be broken even if your current memory is compromised.


Computing/using RSA modulus without knowing its factors

It is possible to do this with secure multiparty computation. There are several papers about this problem, but the most recent state of the art is:

  Tore Kasper Frederiksen and Yehuda Lindell and Valery Osheter and Benny Pinkas: Fast Distributed RSA Key Generation for Semi-Honest and Malicious Adversaries


Why do wireless keyboards only use 128-bit AES? Why not 256?

AES-256 isn't "better" than AES-128 in any practical sense. A crack of AES-128 will almost certainly bring down AES-256 anyway, and there's no practical difference between 128-bit keys and 256-bit keys — nobody will crack a 128-bit key in the future of humanity as a species.

On the other hand, AES-256 likely requires more power draw than AES-128 for this piece of hardware. I'll take an extra hour of battery life over a meaningless difference in security. Hell, I'd take an extra five minutes of battery life.


Do I need two keys for AES CBC and HMAC or can I use the same key for both operations?

I'd advise you to use a library with a higher level API, such as Keyczar.

That being said:

Don't generate the key using SHA-256. Use a password hash function such as bcrypt or scrypt.
Yes, you must use different keys. For example, you can use the password hash function to generate 64 bytes of key material, and use the first 32-byte half for encryption and the second half for authentication.
Make sure the IV comes from a good randomness source (e.g. /dev/urandom)
Make sure your padding is correct. Or simply use CTR which does not require padding.


This does not compromise the private key as long as the hash function is preimage resistant, i.e. given $H(M)$ it is hard to find $M$ (or any  $M'$ giving the same $H(M)$). SHA-3 is assumed to be preimage resistant.


Calculating the privacy that Renyi ($\epsilon, \delta$) Differential Privacy satisfies

I don't think your interpretation of $\varepsilon$ in DP is correct. You can find a decent explanation of this parameter in this crypto.SE question and links therein.
The best intuition I have for Rényi privacy is that it bounds the average of the privacy loss) $L(O)$: instead of being a worst-case property, like DP ("for all outputs $O$, $L(O)$ is lower than $\varepsilon$"), Rényi privacy is an average-case property ("when we average $L(O)$ across all possible outputs $O$, the result is lower than $\varepsilon$"). The $\alpha$ parameter determines which kind of average we're using: used: $\alpha=1$ bounds the arithmetic mean of $L(O)$, $\alpha=2$ bounds the arithmetic mean of $e^{L(O)}$, $\alpha=3$ bounds the quadratic mean of $e^L(O)$, etc.


Per my understanding of these comments, the question's test takes $\ell=64$ bytes from a Windows RNGCryptoServiceProvider, makes it $n=2\ell=128$ groups of $b=4$ bits, counts the number $n_i$ of groups with each of the $2^b=16$ bit patterns $i$, computes $p_i=n_i/n$, and for a limit $x=0.9$ checks
$$x\le-\frac1b\sum_{p_i\ne0}p_\,\log_2\left(p_i\right)$$
The question's test should only fail very rarely. The probability that it does even once in one million tests (as reported) seems to be less than $0.2\%$ according to my simulation: I have seen $25$ events for $18\times10^9$ samples tested. Something is at odds, independently of what follows.

The test is inspired by the formula for Shannon entropy per bit of a source of $b$-bit independent values of known probability $p_i$, but here we do not compute a Shannon entropy, because we are operating on a sample, not on the source, and Shannon entropy is not defined for a sample. The $p_i$ are experimental frequency, not a probability for the source. I can't see how this formula can be justified.
Update: I have asked about that test there, and got a detailed answer. It turns out to be known as the G-test or Woolf's log likelihood ratio test, and a sound alternative to Pearson's $\chi^2$ test.

Can I use something like Shannon entropy to determine the suitability of a symmetric key?

If the source was known for certain to be from a construction aiming at being a CSPRNG, no. Tests on such output can only give a fallacious insurance of security, or detect gross errors. The correct method is to scrutinize the specification and if possible the implementation of the CSPRNG.
But that's not what the question is about.

I am worried that employing such a filter to protect against human error may in turn create a security risk.

It does not in practice. The two following nitpicks are theoretical only:

Restricting to keys that pass the test obviously reduces the keyspace to some (imperceptible) degree.
Performing the test may leak information about the key, if side channel attacks are an issue. However, if they are, that's the problem, not the test.

I do have serious reservations on trusting that test to catch a bad CSPRNG:

The most common issue with CSPRNGs is improper seeding, and the test won't catch it.
More generally it is demonstrably impossible to prove or even meaningfully confirm the quality of a CSPRNG from its output: we can make CSPRNGs that pass any pre-existing test, yet are extremely weak for who knows their internals.

Independently, as already stated, if only a million tests have reported a fail (and the key is 64 bytes as stated), that's most likely an anomaly. It could be in the test, or in how the generator is used, or in the assumptions on what the generator is designed to output, rather than in the generator itself.

A poorly chosen key was installed into the system by mistake

The test indeed has some chance to catch some forms of that, and if the small false-positive rate (much less than one in 100 million keys if I get it correctly) is tolerable, why not? However, attempts to detect errors from the value of the key itself are bound to be unreliable. For example, the test won't catch a favorite test key for DES, 0123456789ABCDEF, repeated.
A preferable practice is to have procedures that prevent such mistakes. Like, transmitting keys using dedicated devices, or data blobs with integrity protection, or as a last resort well-thought Key Check Values.


Is it generally possible to employ brute force methods when the encryption scheme is not known? Why or why not?

This is called ciphertext-only cryptanalysis*, and it's pretty difficult unless the cipher is quite weak.  Therefore, the first priority for a cryptanalyst in such a situation is usually to try to find more information about the algorithm.  Fortunately (for the cryptanalyst), as Kerckhoffs' principle suggests, there are often ways to find out how the algorithm works.  For example:

If the string was encrypted (or meant to be decrypted) by a computer program, one could try to obtain a copy of the program and inspect it in a debugger to determine the algorithm.
Similarly, if the encryption and/or decryption was done by a hardware device, one could try to obtain such a device and reverse engineer it.
One might also try to obtain a copy of a manual explaining how the cipher is used, or design documents explaining how it works, or even look for hints in public articles written about it.  Or one could even try to capture someone who knows how the cipher works and interrogate them.

That said, there are some things that can be done even without knowing the algorithm in advance, particularly if the cipher is a simple one:

One can look at the character frequencies in the cipher, or more generally at $n$-gram frequencies or at correlations between characters $n$ positions apart.  Many simple classical ciphers can reveal characteristic patterns under such an examination, allowing the algorithm and perhaps eventually the key to be guessed.
More generally, one can look for patterns that may reveal information about the algorithm.  For example, modern ciphers usually operate on bytes, or blocks of bytes, while classical ciphers typically use a smaller alphabet of letters and maybe a few symbols.  Some modern operating modes may reveal the block size of the cipher; also, comparing the length of the ciphertext with that of the plaintext, if known, may reveal the presence (or absence) of an IV and/or a MAC.  And sometimes, e.g. when used in ECB mode, even the output of a modern block cipher may have patterns that can reveal information about the plaintext, and, incidentally, the cipher and mode used.
Finally, one can simply try known algorithms and variants of them and see if they work.  This works particularly well if one has already narrowed the choices down somehow, and/or has additional information available (such as knowing the key but not the algorithm).

For an interesting historical example, see the cryptanalysis of the Enigma (and of the other WWII axis ciphers), which provides examples of several of these methods and their combinations.

* The term "ciphertext-only cryptanalysis" is also used for the broader situation where the algorithm is known but no information about the key or the plaintext is available.  Even that can be quite challenging, although obviously easier than if even the algorithm used is uncertain.


Why is adaptive security stronger than CCA1 security, and weaker than CCA2 security?

The word adaptive security could possibly refer to:

security with respect to the definitions of IND-CCA2, possibly emphaizing that is the adaptive case of IND-CCA (IND-CCA1 is called non-adaptive)
Real-time adaptive security, but that's not really in the field of cryptography but network security.
Gartner published a paper Designing an Adaptive Security Architecture for Protection From Advanced Attacks (behind a paywall), and is referred to in various blogs. It seemed to have stirred some interest, but google mostly gives you results for "what is adaptive security", and after a quick glance none of those articles seem to be about cryptography. It seems to be mostly about network security and business management (including things like risk management, incident response, continuous monitoring etc. )

I don't think there is any (commonly used) security definition stricly between IND-CCA1 and IND-CCA2.


Are there actual consequences of padding oracle attacks?

I mean this is the server bug that it doesn't take a key in the first place and check if it's correct :)

What do you mean with that? The key must be the right one, and the padding oracle attacks actually change the ciphertext encrypted with that key on the other side to perform the attack.

but what about say c2, c3 which are in the middle of whole message, we know c3 and c2 but we dont know and we will never know either p3(plaintext of course) nor intermediate state IS3

No, a padding oracle attack is able to completely decrypt a message. This is precisely because the XOR influences the next block.
Note that padding oracle attacks are just one form of plaintext oracle attack. For instance, you can also perform plaintext oracle attacks on XML-enc, even without using the padding itself.

I am asking to know if this attack is just a one with no real world implications and no real data decryption capabilities(actual data) .

Yes, that's utterly and completely wrong. A padding oracle attack can decrypt the whole message using 128 tries per byte, and other plaintext oracles can actually be even more effective.
Besides that, having the receiving end accept a changed plaintext is possibly as dangerous as loosing confidentiality. For that reason you should use authenticated encryption - or rather a protocol that utilizes authenticated encryption instead of unauthenticated CBC.


Is password-based AES encryption secure at all?

You are correct in that the best strategy for an adversary would be to guess the password, as opposed to cryptanalysis of AES plaintext/ciphertexts. However, this does not make encryption pointless - password based key derivation is a challenge unto itself, separate from encryption, but one that does have practical solutions.

We can strengthen this weak link by making it require a large amount of time to derive the key from the password. If an adversary can only test a handful of passwords per second, then the probability that they will be able to crack a given password drops dramatically.

Granted, this is not a perfect solution - You might need to derive your key on a slow, old computer, while your adversary might have access to a distributed network armed with GPUs and FPGAs. So there is a balance to be had between how long it takes you to derive your key (which must be quick enough) and how long it takes an adversary to guess passwords (which must be slow enough).

Typically a duration of 1 second per derivation attempt is considered appropriate. However, the actual time duration required to compute a hash does not remain constant, even if you iterate the function a constant number of times. This is due to the way computing power scales with time - the iteration count you use to secure your password today may not protect you nearly as well in a few years.

As to whether or not a 22 character password is equivalent in strength to an 128 bit key, this is not a question that can be answered with a simple "yes" or "no" - for example, if your 22 character password is 1010101...10, then no, it absolutely does not have nearly as much entropy as a uniformly random 128 bit value. If your 22 character password consists of 3-4 english words with spacing, it does not have nearly as much entropy as a 128 bit random value.


How to create reduction functions in rainbow tables?

Is it necessary to have 50 000 different reducing functions to avoid the collisions?

Yes. If you do not have different functions it is not a rainbow table. It is just a table of hash chains which is less efficient, especially for high coverage tables. However, the functions do not have to be unrelated, just different.

  How do I create those reduction functions (not just take the n-first letters of the hash for instance) ?

Any way you want, as long as it leads to an even distribution and different functions. The simplest is to:

Use the size of the search set (of passwords, keys or what have you) and take the hash value modulo that, so the last bits/bytes if the set size is a power of two.
Then, to create different reduction functions you can add the index of the function to the value. I.e. you add nothing for the first, 1 for the second function and so on. This is sufficient, since the next hashing step will cause these small changes to again give a completely different output.
Finally you turn the value into an element of the search set. E.g. encode it into lowercase letters if that is what you are looking for.

The simplest example is if you are looking for a binary key. For example, you are building a rainbow table for DES, which has 56-bit keys (ignoring parity) and 64-bit output.

You can use the last 56 bits of the output (i.e. the whole output modulo $2^{56}$) and add $i$ (again modulo $2^{56}$) for the $i$th reduction function. Pseudocode:

def R(i, x): # i'th reduction function
    return (x + i) % (2**56)

In the case of passwords, suppose you build a table for eight-letter lowercase passwords hashed with MD5. There are $26^8$ such passwords, so you can take the hash value, interpreted as a 128-bit integer and compute (x + i) % (26**8) instead.

(Or you could take the latter half of the hash as a 64-bit integer, then do the same.)


Is it possible to decrypt the entire message with one half of the key in this example?

There are two major problems with this method.

The first problem is that Susan is likely to be able to recover significant amount of data from a series of such blocks.

For example, if Susan knows $subkey_1$, then she could recover the value $subblock_1 \oplus subblock_2 \oplus subkey_2$; if a single block is encrypted with this key, she can't deduce anything from this (as she has no information about $subkey_2$; however if multiple blocks are encrypted with the same key, then she can exclusive or the values, obtaining the value $subblock_1 \oplus subblock_2 \oplus subblock_3 \oplus subblock_4$; if she has a guess about the encrypted data, this is likely to reveal more.

The second problem is that someone with the entire key is unable to uniquely decrypt.

Here's why: someone with the encrypt key could decrypt $ciphertxt_1$ to compute $subblock_1 \oplus subblock_2 \oplus subkey_2$, and thus recover $subblock_1 \oplus subblock_2$

And, they could decrypt $ciphertxt_2$ to recover $subblock_2 \oplus subblock_1$

At this point, they have the value $subblock_1 \oplus subblock_2$, howqever without any further information, they cannot recover either the values $subblock_1$ or the value $subblock_2$.  Yes, if the decryptor had some side information about either of those values, he could determine the other; however we generally don't assume that the legitimate decryptor has such side information.

Hence, this method makes things possible for the attacker, and not possible for the legimate user.


I believe you are being confused by what $k^{-1}$ means.  It doesn't mean "interpret $k$ as a real number, plug it into a calculator, and hit the $1/x$ button".

When we use the $k^{-1}$ notation, what we mean to say is that $a = k^{-1}$ is equivalent to saying that $a \times k = 1$.

You will say "doesn't that mean doing exactly what a calculator does?".  Well, it would, if the multiplication was performed in the field of the reals.  However, we're doing everything modulo $n$ (within the field $GF(n)$, as $n$ is prime), and so the multiplication is done modulo $n$; hence we really have $a \times k = 1 \pmod{n}$.

In this context, when we write $k^{-1}$, we really do intend the modular inverse.  And, when we derive $k = \frac{z_1 - z_2}{s_1 - s_2}$, we're not ignoring the modulo operation; it's been assumed implicitly; what we really mean is $k = (z1 - z2) \times (s_1 - s_2)^{-1} \bmod n$, there $(s_1 - s_2)^{-1}$ is the multiplicative inverse (modulo $n$) of $s_1 - s_2$.

When you derive $k = \frac{z_1 - z_2}{s_1 - s_2 + n*(i-j)}$, well, since everything is done modulo $n$, including the internal additions, we effectively have $n=0$ (because, modulo $n$, those are the value), and so $i$ and $j$ drop out, and we're left with the original derivation.

Since you explicitly asked questions, I'll answer them (even if they ought to be obvious once the above has been clarified):

  Mathematically, is there another way to retrieve $k$, even if the $k^{−1}$ part is really large? Maybe using some inverse modulo?

Yes, an inverse modulo is precisely what you're looking for.

  Why is it that many implementations use the inverse modulo instead of $k^{−1}$? (I've seen it in two libraries so far)

The inverse modulo that the libraries do is what is meant by $k^{-1}$

  Why doesn't it work when I change the implementation to use $k^{−1}$?

The mathematics of ECDSA assume that the math works out in one specific field (the field $GF(n)$); if you do the computations in a different field (say, the field of real numbers), well, it won't work.


Is it possible to decrypt a ciphertext with a different private key?

No, it's not possible. If it was possible it would have a devastating impact on asymmetric cryptography in general.

Most asymmetric cryptosystems rely on mathematically problems that cannot be solved in polynomial time (such as integer factorization, or discrete logarithm).

Let's look at RSA:
you choose your $K_{pub} = (n,e)$ and $k_{priv} = (d)$ with $e \in \{1,2,\dotsc , \Phi(n) - 1\}$ to fulfill  the following equations:

$$\Phi(n) = (p - 1) \cdot (q - 1)$$
$$\operatorname{gcd}(e, \Phi(n)) = 1$$
$$d \cdot e \equiv 1 \bmod \Phi(n)$$

Every element in a group can have one inverse element at maximum, you can not find a $d'$ for which:

$$d' \cdot e \not\equiv 1 \bmod \Phi(n)$$

So instead of:

$$d_{k_{priv}}(y) = d_{k_{priv}}(e_{k_{pub}}(x)) = (x^e)^d \equiv x^{de} \equiv x \bmod n$$

you will compute:

$$d_{k'_{priv}}(y) = d_{k'_{priv}}(e_{k_{pub}(x)}) = (x^e)^{d'} = x^{d'e} \equiv m' \not\equiv m \bmod n$$

So you will be able to compute the decryption with a different $d'$, but your result $m'$ will have nothing in common with the original $m$.


Is an AEAD the recommended method to add encryption + HMAC to a protocol?

I think you're a bit unclear about the factoring and abstraction layers here.  A correctly designed AES + HMAC construction is AEAD.  This is because AEAD is about what interface and contract the cryptography should expose to its callers; while the choice between GCM vs. encrypt-then-HMAC is a choice between implementations.  Ideally, the code that calls an AEAD would do so through an interface that abstracts away the difference between the two implementations you propose, and the code that implements your AES + HMAC construction would expose the same caller interface as AES-GCM.

If you're looking cooking up your own AES + HMAC combination, I'd recommend you rather put some effort into finding a ready-made and well vetted third-party library.  Whether it uses AES-GCM or an AES + HMAC construction isn't the most important thing.  As the saying goes, don't roll your own.


Partial proof of work: an hash function that validates parts of input, insensitive to the rest

If you give me enough information to evaluate $h$ on inputs of my choice, then I can easily check whether $h$ is sensitive to the $i$th bit of input --- just evaluate it on two strings that differ only in their $i$th bit and see if the outputs are the same. So it is not possible to hide this property in the description of a public function.


Key derivation: Does it make sense to use KDF and PRF consecutively?

Assuming the KDF is actually secure,There is no clear advantage other than domain separation, and certainly some severe disadvantages (code complexity and size).

If you have the ability to change things, I would simply use one call to HKDF-SHA256 or HKDF-SHA512 once to get all the bytes you need.  SHA-256 is hardware accelerated on some platforms so you might prefer that.

Many crypto libraries have HKDF, if not it is trivial to implement correctly if you have an HMAC primitive available.

UPDATE: I now see that the latest ANSI X9.63 still specifies SHA-1 as its hashing primitive. SHA-1 is broken in terms of collision-resistance. While that doesn’t immediately affect a KDF (which relies on pre-image resistance), it does means you should clearly replace it with something stronger as soon as possible. SHA2-256, SHA2-512, SHA-3, BLAKE2 are all reasonable choices.


Thoughts on This Encryption Method, Please?

That looks like a (polyalphabetic) substitution cipher, with a less-straightforward method of entering the key. As already mentioned in the comments, close to the Vigenère cipher, which is rather well known. IIRC ciphers like that were used (and broken) in times before WWI (or WWII?), The Code Book by Simon Singh has material about historical ciphers, among other books, if you are interested.

As for not knowing the algorithm, it's usually taken as granted as the algorithm will be known (Kerckhoffs's principle), as it's hard to keep it hidden if the system is used widely enough and there is sufficient interest in it. Either the algorithm is widely available and can be bought, or it will be found out by old-fashioned spying, or in case of a single criminal using it, law-enforcement will be happy to read the software off your computer... (Since you need to have an unencrypted copy of the encryption program anyway.)

As for the system, consider that using words as keys isn't that unpredictable, passwords are attacked with dictionaries daily, and the range of 26 letters out of 256 values is also quite small (if mostly lower-case letters.) Also, this isn't strictly true:

  To decrypt the file, you had to reverse the process [...], using the original passwords in reverse order.

The algorithm has a property that makes the order of the keys irrelevant. Perhaps you can find it?


Security of SRP-6a against impersonating server choosing small/wrong N

I don't see how the server can directly learn $x$; what a server would be able to is perform a single exchange with the client (recording the initial parts of the protocol), and then go through a dictionary, and test various passwords (that is, various possible $x$ values), and realize when he finds the right one.

The idea here would be to select a prime value $N$ where $N-1$ is smooth (that is, a product of small factors); this makes solving the discrete log problem modulo $N$ easy.

With that, when the client sends $g^a$ as its initial exchange, the server can immediately recover $a$.  It then sends back random values for $B$ and $s$.
The client then sends its verifier $H[H(N) \oplus H(g) | H(I) | s | A | B | K_{Client}]$.

After that, it's easy; if the server has a guess for the password, it can compute the corresponding $x$ value, and then the shared key that the client computes; $K_{Client}=H( (B − kg^x)^{a + ux} )$; where $B, k, g, a, u$ are known values, and $x$ depends only on the password.  Then, we can go back to the verifier and recompute it based on the possible $K_{Client}$ value (as $K_{Client}$ is the only value that the server does not know; if the computed value matches the value that the client sent, then we have correctly guessed the password (or we found a collision in the hash function).

This isn't likely the only game we could play with a malformed group; it is likely to be the most serious.

The moral of this story: either the client must verify that the group proposed by the server is secure (both $N$ and $(N-1)/2$ are prime; $g$ is a generator, that is, $g^{(N-1)/2} = -1$ and $g \ne -1$); or the client needs not to work with arbitrary $N$, $g$ values, but instead only with preconfigured ones that it knows are secure.


Non-outsourceable digest-free signature scheme

I will be basing this construction on Schnorr signatures, since I am most familiar with those. I will also use elliptic curve, for the same reason; see ECDH.

Recall:

Schnorr signatures are a Fiat-Shamir transformation of the Schnorr identification protocol. Fiat-Shamir transforms an interactive proof of knowledge into a signature.
The Schnorr identification protocol (interactively) proves the knowledge of a discrete logarithm; i.e., Alice (who signs $m$) has access to a secret key $x$, with corresponding public key $Y=xG$. Now $x$ is said to be the discrete logarithm of $Y$.

Applying this terminology to your question, I would say we want to prove that Alice has access to $m$ and $x$. Alice can, for example, prove that she knows the discrete logarithm $ms$ of $mxG=mY$. She can do this by applying a regular Schnorr signature using public key $Y'=mY$ and secret key $x'=mx$:

Let $k$ be a random field element; set $R = kG$.
Let $e=\mathcal{H}(R)$
Let $s=k-x'e=k-mxe$

The signature is $(s,e)$. Bob verifies:

Let $R_v=sG+eY'=sG+emY$
Let $e_v=\mathcal{H}(R_v)$

The signature is valid iff $e=e_v$, since $R_v=sG+eY'=(k-mxe)G+emY=kG-mxeG+emxG=kG$.

Of course, this supposes that it is feasible to multiple your (potentially large) message $m$ with the secret key. This also assumes that $m<q$ (smaller than the order of the field $\mathbb{F}_q$, since Eve can otherwise compress $|m| \bmod q$. You can circumvent this by signing in blocks of size $m_i<q$.


AFAIK vigenere cipher is a plain subsitution algorithm with arbitrary key length, destroying statistical patterns (f.e. of natural languages) but not conducting any transposition.

Btw. a classic approach to crack a vigenere cipher is the Kasiki-Test (https://en.wikipedia.org/wiki/Kasiski_examination) which might give you information reagrding the key length.

If you try to decrypt a file format (jpeg, gif, zip etc.) you actually know at least the first bytes (fileheader) as they are defined by convention:
f.e. a zip file always starts with 0x04034b50 (https://en.wikipedia.org/wiki/Zip_%28file_format%29) which gives you the first 4 bytes for your decryption table.


Given an encrypted file, what are possible ways to find its encryption algorithm?

One of the important properties of a modern cryptographic algorithm is that it resist distinguishing attacks. Distinguishing attacks are any way to tell the encrypted data apart from random data. So if you can tell what the algorithm used was simply by looking at the ciphertext the algorithm is vulnerable to this attack.

Unless there is a header or such that tells you the algorithm and mode used, or a weak cipher was used, determining the algorithm used from the ciphertext is impossible.


Why should the primes used in RSA be distinct?

The main reason why the prime factors $p$ and $q$ of RSA modulus $N$ must be distinct is stated in the question: if they are equal, given $N$ (which by definition is public in RSA), it is trivial to find $p=q=\sqrt N$.

A secondary reason is that with $p=q$, a few messages $x\in\{0\dots N-1\}$ can't be reliably deciphered from $x^e\bmod N$: all those $x$ such that $x\equiv0\pmod p$ encipher to $x^e\bmod N\;=\;0$. This would not be so much of a problem, because those $x$ are rare when $p$ is large, and in practice (when proper padding is used) $x$ is substantially random over $\{0\dots N-1\}$, thus the problematic $x$ are used with negligible probability.

Update: as pointed by Ricky Demer, there's an additional reason: with $p=q$, the private exponent $d$ would need to be computed with $d\equiv e^{-1}\pmod{p\cdot(p-1)}$ rather than the usual $d\equiv e^{-1}\pmod{\operatorname{lcm}(p-1,q-1)}$

If $p$ and $q$ are suitably large and randomly chosen, they are distinct with overwhelming probability, thus the need that they are distinct is often not specified without invalidating quantitative theoretical results. In an implementation, if an explicit test is made, it can only hope to ever catch some gross malfunction of the key generator; same for customary tests that $p$ and $q$ are different enough, like FIPS 186's prescription that $|p-q|>2^{\lfloor\log_2(N)\rfloor/2-100}$ .


Is openssl rand command cryptographically secure?

Yes, it is cryptographically secure, pseudo random output, seeded by retrieving secure random data from the operating system.

If it is random or not depends on the fact if the OS RNG is random. This is usually the case on normal desktops,  but you'd better be sure for e.g. limited embedded systems. If no truly random data can be retrieved  - according to RAND_bytes - then rand will exit with an error.

Added note: Of course you are dependent on the implementation. Famously OpenSSL was broken for Debian because a maintainer ran a program to find memory errors and disabled all entropy sources rather than the one that was (deliberately) failing the property that no uninitialized memory should be used. So it is of importance to review security reports and keep your system up-to-date / on long term support.

Any random source that you add using -rand [file][:file]* is used as additional seed data - in other words, the output will always be random, even if you supply the same seed.

As the pseudo random generator provided by OpenSSL generally runs in the application space on the main thread, it may be faster than asking a lot of data from /dev/urandom. But to be honest, most of the time using /dev/urandom suffices (and current implementations are pretty fast as well).

You can see that it is random when you look at the link to the RAND_bytes manual page which is the function that lies behind command line rand and is linked to from the manual page (in the "see also section, but yeah"):

  RAND_bytes() puts num cryptographically strong pseudo-random bytes into buf. An error occurs if the PRNG has not been seeded with enough randomness to ensure an unpredictable byte sequence.

That RAND_bytes() is used can be found in the source file for the rand command, rand.c, so yes, this is indeed the function that is called.


Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and 321:42:36. Therefore, merely not reusing exact index values is not sufficient; you should refrain from using two index values from the same word. This reduces the lifetime of a given book as a cipher key.

Another problem is in the "random choice". When you want to encrypt a letter, you must choose one of the index values in the book which correspond to that letter. Human beings are very bad at making random choices in their head. But non-random choices can exhibit biases. So the encryption process is important, and not completely described. An unbiased process would have you use dice to select at random the page, line and column; and if that does not correspond to your target letter, try again. That's tedious.

Also, in order to avoid reusing a given index, you must keep a list of the index places you have used, e.g. by marking the already used letters in the book. The book then ceases to be an inconspicuous object: instead of a brain-only key ("use this book"), you have a physical key ("use this, I mean that specific printed instance, book").

And, of course, anybody who has scanned millions of book and extracted the text into searchable computer structures, can easily try all existing books in a few minutes, and report a hit when the decryption result appears to look like meaningful words. So you are at the mercy of Google (and of whoever acquires Google's services).


Is it a good or bad idea to include a password's salt in the calculation of a MAC?

It seems unwise to give an attacker enough information to run an off-line attack against a password even if you're using a good PBKDF. PAKE would probably be better.

Assuming you have a strong key your question still holds. I interpret it as:

Given a key $k_1$ and a salt $r$ you derive $k_2 = KDF(k_1|r)$. You then send $m, r$ and $MAC_{k_2}(m|r)$.
Is it safe to do this given that a change to $r$ will change both $k_2$ and $m|r$ or is there a chance that $MAC_{k_2'}(m|r') = MAC_{k_2}(m|r)$?

And my answer is, there is no chance of that happening because it would constitute a forgery. Given a good KDF $k_2'$ will be indistinguishable from random so a valid MAC for anything under that key including $MAC_{k_2'}(m|r')$ would be a forgery.


I assume that for a fixed key $K$, you are asking why $f(m) \overset{\underset{\mathrm{def}}{}}{=} <STREAM> \oplus\ m $ is not a PRP, where $<STREAM>$ is the stream that is generated from the key $K$. $f$ verifies at least two properties that PRP in general do not verify:

$f(m_1) \oplus f(m_2) = m_1 \oplus m_2$
$f(f(m_1)) = m_1$


Why should CAST5 and 3DES not be used for encrypting files over 4GB?

If you use a key for close to $2^{n/2}$ blocks in CBC mode, then the chance of getting a collision in the ciphertext is getting rather high because of the birthday paradox. As the ciphertext is used as a vector for the next calculation, and since that vector should be unpredictable, you would likely lose confidentiality.

Note that the author seems to have put his mark at about $1 / 148$ as the chance for a collision to occur (see the calculation by fgrieu in the comments). That may be either too low or too high depending on the context. That is if bytes are meant instead of bits, otherwise it would be $1/9445$ - a somewhat more sensible value most of the time, but you would be left with only 512 MiB for a single key.


Different patterns of different paterns, wildcard

Generally, that is possible.

crypto-analytics

Including solutions that collect statistical information, there are several solutions which are used during cryptographic analytics that can cope with shifting (read: changing) values, frequencies, and pattern detections.

Yet, merely having knowledge of the cyphertext will not be enough most of the time. For example, it's not really helpful when a modern encryption algorithm has been used since such algorithms twist and mix the bits so that it is "near to impossible" to trace or guess how a single bit (or byte) of the message was encrypted.

exploiting partial break

Additionally, you have to count in that - due to the fact your example shows you have part of the plain-text which was used to generate the encrypted message - there are additional hints for analysts that could show how the encrypted message may have been encrypted. This in itself weakens the encrypted text in this specific situation, as it represents a "partial break" which can be build upon.

practical approach

I could go on and practically approach your example to show you step-by-step how I would be able to decode your encrypted message, but while writing this answer I have decided to not do that to prevent going off-topic, because:

  analyzing or decyphering a block of data are off-topic here, as the results are rarely useful to anyone else.

I'm sure you understand.


Best practices when encrypting a file with three different ciphers

I) There is no minimum. Maximum in your case is $2^{64} * 16$ bytes with same key.

II) No. No. GnuPG takes care of that.

III) No. Compressing does not weaken encryption.

IV) I don't think it matters because it is not authenticated encryption.

V) Yes, passphrases must be different.

VI) In your case you can get maximally 256-bits of security per cipher. You should use around 50 characters (depending on complexity) per passphrase. More does not hurt.

VII) I don't think you can tweak anything. It is "best security" by default.

It is important to note that GnuPG does not authenticate files encrypted with symmetric encryption, which means you cannot detect, if it has been modified.

You can read more about cascade encryption here: https://blog.cryptographyengineering.com/2012/02/02/multiple-encryption/


In TLS 1.3 handshake, what's "PSK binders" used for?

The current TLS 1.3 draft (-28) talks about the binder value:

  The PSK binder value forms a binding between a PSK and the current
  handshake, as well as between the session where the PSK was
  established and the current session.  This binding transitively
  includes the original handshake transcript, because that transcript
  is digested into the values which produce the Resumption Master
  Secret.  This requires that both the KDF used to produce the
  resumption master secret and the MAC used to compute the binder be
  collision resistant.  See Appendix E.1.1 for more on this.  Note: The
  binder does not cover the binder values from other PSKs, though they
  are included in the Finished MAC.

So the idea seems to be that the binder value can be used to somewhat "prove" to the server that the client knows the pre-shared key associated with a given identity (and it's the same the server remembers). This also ensures that they won't just go ahead and run a PSK handshake when they don't actually have a PSK.

Additionally it binds the previous session ('s handshake) to the current session ('s handshake) which could e.g. allow the server to discover that the client previously suffered from a MitM attack when the attacker forwarded the identifier but naturally got a different PSK on both ends and is gone for the session resumption.

To see the first property have a look at section 4.2.11.2 and section 7.1. In section 7.1 you see that the binder_key is rather immediately derived from the PSK. Now for session resumption the PSK is the resumption_master_secret. But more importantly section 4.2.11.2 tells us

  The PskBinderEntry is computed in the same way as the Finished
  message (Section 4.4.4) but with the BaseKey being the binder_key
  derived via the key schedule from the corresponding PSK which is
  being offered

and so knowledge of the binder key immediately implies knowledge of the PSK. And knowledge of the binder key is confirmed by verifying the bound message.


PHP AES-256 CBC faster than AES-128 CBC?

I'll answer in order:

No, you may not be doing something wrong. This is just the compiler warming up and performing optimizations. The second run you see that AES-128 is already about as fast, which is what you would expect (it should be ever so slightly faster in the end, but that might not even be noticeable).
Don't know, you'd have to debug, because that's certainly wrong.
The key should not be in any kind of encoding. The key used by OpenSSL should consist of bytes indistinguishable from random. You can use hexadecimals for storing keys in string (something that's rather questionable as well) but you should decode it before using it.
Same as for the encryption key; you'd use openssl_random_pseudo_bytes or another secure random number generator. Then you may encode it to hexadecimals or base 64, as long as you decode it again to binary before you use it.

Note that if you provide a 16 byte key as 32 hexadecimals that you might be using AES-256 without realizing it yourself. Best test against another framework / crypto library (but NOT mcrypt).

You should not store your users passwords encrypted. Instead you should use a password hash such as bcrypt.


Is a nonce considered 'secret' enough for HMAC?

No, the nonce is not fit to be a HMAC key, because anybody can view the nonce in transit. If - on the other hand - the TLS connection does deliver enough security then you would not need the HMAC.

It's fine to use the nonce as one time code, but you don't need the HMAC for that. If an attacker can obtain nonce's send to clients than the attacker can always replace the original nonce with another one by redoing the HMAC calculations.

Note that your solution space may be empty if you cannot trust the client application. That sounds a lot like trying to implement a DRM scheme.


Why are the mixcolumns in AES in a fixed order? Can the order be changed?

What do you mean by "order"? Each column is "mixed" independently using the same operation. If you are talking about the MixColumns matrix, of course you can change it, but

the operation defined by the matrix must be bijective;
the matrix should have low linear and differential branching numbers (optimal in case of the AES MixColumns).