Is it a cryptographic risk to share the same encrypted data over and over again?

...but the data inside it is identical. And the attacker knows this. Does this open the encryption to any vulnerabilities from a cryptographical standpoint?

No. If it did, then encryption would not be very useful.

In fact, modern encryption schemes are designed to be secure even if:

The adversary already knows the plaintext that the ciphertext represents (known plaintext attack - KPA)

Where "secure" means they cannot recover the key or learn any information from other ciphertexts

The adversary can choose plaintexts, submit them to be encrypted, and obtain the resultant ciphertexts (chosen plaintext attack - CPA)
The adversary can choose ciphertexts, submit them to be decrypted, and obtain the resultant plaintexts (chosen ciphertext attack - CCA)

Even in all of these scenarios, a modern cipher will remain secure. Not only will it protect the plaintext from discovery, no adversary will even be able to distinguish a ciphertext from a random stream of bits with a non-negligible probability.

As long as the encryption provider is:

using a competent algorithm (such as AES-256 mentioned in the question)
in an appropriate mode of operation (e.g. an authenicated mode such as GCM)(edit: AEAD is apparently not relevant in this scenario)
and handles initialization vectors appropriately

then the messages will remain as secure as the passphrase that protects them. How secure the passphrase is will depend on how long/complex it is, combined with how the key is derived from it.


Crypto++: How to re-generate pseudo random integers in Crypto++

Formally, what you're really looking for is a key derivation function (KDF).

The Crypto++ API includes a PasswordBasedKeyDerivationFunction class, but that doesn't really seem optimal for your purposes; since you already have a high-entropy random seed, what you really want is a simple key-based KDF, not a fancy key-stretching KDF meant for use with passwords.

Fortunately, it's not hard to implement one yourself.  A very simple approach would be to use your "seed" as the key for a stream cipher (or to, say, AES in CTR mode), and use the keystream (which you can obtain by encrypting a bunch of null bytes) as your source of random bytes.

(You can then convert these random bytes into uniform random integers in your desired range e.g. by rejection sampling: to generate a random number between $0$ and $m$ inclusive, first find $k = \lceil\log_2m\rceil$, i.e. the length of $m$ in bits, then generate a random $k$-bit string.  If this bitstring, interpreted as a binary number, is less than or equal to $m$, you're done; else, toss it out and repeat.  It's not hard to prove that, on average, you'll end up rejecting less than half of all bitstrings (since $m \ge \frac12 2^k$).  Note, however, that this does potentially leak some statistical timing information about the most significant bits of $m$, which might matter if you want to keep it secret.)

Alternatively, with only slightly more work, you can implement a standard construction like HKDF (RFC 5869), or one of the DRBG algorithms from NIST SP 800-90A (note: do not implement Dual_EC_DRBG!).  CTR_DRBG, in particular, is very similar to the simple "use seed as key to AES-CTR, take keystream" suggestion above.


Number of operations for Elgamal cryptosystem

Roughly speaking, in order to achieve $k$ bits of security, encryption and decryption for Elgamal, RSA, and ECC, require $\mathcal{O}(k^3)$ operations, while encryption and decryption for lattice-based systems require only $\mathcal{O}(k^2)$ operations.

That quote uses "$k$ bits of security" where there should be "a security parameters of $k$ bits" or "key size of $k$ bits". In particular, having RSA and ECC together can only mean that a confusion is made between security in bits (that I now note $b$) and key size $k$. As an aside, the quote uses $\mathcal{O}$ where formally there should be $\Theta$ or $\Omega$, see this for the difference. That's a common, I do it often!
Let's independently derive the cost counted as instructions on standard computers with fixed-width word (as customary), for $b$-bit security meaning $\Theta(2^b)$ work for an attacker to break the system,
Consider RSA with $k$-bit public modulus, and ElGamal as originally formulated, that is the group $\Bbb Z_p^*$ with $p$ a $k$-bit public prime and a generator for all or most of the group. The cost of the private-key operation is dominated by $\Theta(k)$ modular multiplications. Each of these has costs $\Theta(k^2)$ work using common algorithms, $\Theta(k^{\approx1.6})$ for large parameters with Karatsuba, $\Theta(k^{\approx1.5})$ for huge parameters with Toom-Cook, $\Theta(k\log k)$ in theory only. Ignoring anything better than Toom-Cook, we get $\Theta(k^3)$ to $\Theta(k^{2.5})$ work. For RSA, subtract $1$ from the exponent for public-key use (encryption, signature verification) and fixed public exponent.
The two algorithms considered are vulnerable to GNFS, with heuristic cost $L_{(2^k)}\left[1/3,\sqrt[3]{64/9}\,\right]$ in L-notation. Assuming this remains the best attack, and keeping only the first parameter in the interest of simplicity and a little safety margin (from the standpoint of the legitimate user), we have like $\Theta(k^{1/3})$-bit security.
At $b$-bit security, the work for ElGamal as originally formulated, and RSA signature/decryption, thus comes out roughly as $\Theta(b^9)$ to $\Theta(b^{7.5})$.


Can nesting different ciphers with different keys ever decrease security?

In your construct:

EncryptAB(K1||K2, PT) = EncryptA(K1, EncryptB(K2, PT))

it is easy to show that, as long as the keys K1 and K2 are independent, that this cannot be any less secure than the stronger of EncryptA and EncryptB.

Here is a sketch of how this is shown; suppose that there is a chosen plaintext attack against EncryptAB; that is, the attacker submits known values to EncryptAB, examines its results, and somehow rederive the value K1||K2.  Then, this method can be used to attack EncryptA; the attacker would choose a random value for K2; he would take his chosen plaintexts, EncryptB them with his K2 value, and then submit them as chosen plaintexts to the EncryptA with the known key.  Then, he can use those encrypted values to rederive the K1||K2 values, which includes the value K1 which he was interested in.  The attack against EncryptB works in exactly the same manner.

Now, this method doesn't prove that EncryptAB is any stronger than the stronger of EncryptA and EncryptB (and, indeed, it might not be); however, it does show that using the two of them doesn't make things any worse.  Also, we need to assume that that keys K1 and K2 are independent, because this simulation has the attacker picking one of those values; if they are interrelated, he wouldn't be able to do that.

Now, for your related question: how about interleaving the rounds of two different ciphers.  That doesn't have any such security reduction, and in practice, it would give me the willies.  Encryption round functions don't have that much strength in themselves (that's why we use multiple rounds); what a good round function is designed to do is play nicely with the round functions that'll be next to it in the designed cipher.  For example, if there is a good differential through one round, it's going to be the case that it doesn't have any good paths through the next one (or the one after that).  This is not by accident; the cipher designer (at least, if they knew what they were doing) went through some serious analysis to make sure that was the case.

In contrast, if you interleave the round functions from two different ciphers, well, no one has done any such analysis.  Yes, it might be secure, but without someone spending a lot of time looking at it, you couldn't be certain.  It'd be far better to use your original suggestion, and do a full set of rounds from your first cipher, and then do a second set of rounds from your second.


Unique GCM/CCM initial counters without recipient side message counters

Perhaps a workaround for this would be to instead use deterministic nonce generation with AES-GCM-SIV, which has been formally proposed in a paper by Shay Gueron and Yehuda Lindell. The core idea is to use the MAC over the plaintext as part of the initial counter for encryption and reuse that as a tag on decryption.

This can be bolted onto any AES and GCM implementation if you have the ability to call GHASH standalone.

This has several advantages:

The counter only needs to be kept for re-keying, but no longer needs to be sent over the network in any way.
You gain IV/nonce reuse resistance (though it still leaks whether two messages were identical), possibly allowing randomized nonces safely.
You're back on the “beaten path” so that you're back in an area where cryptanalysis exists, rather than homegrown cryptography.

But also disadvantages:

You need an initial extra AES call to derive the internal keys when initially setting up keys, plus an extra call with a separate context for every authentication tag.
The scheme is inherently dual-pass, once to derive the authentication tag and once for the encryption/decryption, so it may be unacceptably slow for your use case.

Technically, this meets your criteria:

  Implicit packet counters can't be used to ensure that the initial counters are unique,

Non-uniqueness no does not lead to a loss of confidentiality with AES-GCM-SIV. You can avoid using a counter and instead use a randomized nonce (or a fixed nonce if you know all messages will be unique, e.g. by making the counter part of the message body instead).

  Explicit packet counters shouldn't be sent as plain text, due to implementation-specific side-channel attacks. (When packets are sent out of order, it is due to things happening sender side the attacker shouldn't be unnecessarily made aware of, and that would be significantly harder to spot using frequency analysis only.)

The packet counter does not have to be sent in any way with AES-GCM-SIV.

  Additionally, the following requirements should be met if possible:

  No additional AES context should have to be maintained for each connection. i.e. if AES encryption is used in any way, it has to be done using the same key as for bulk encryption.

AES-GCM-SIV unfortunately requires a second AES context to encrypt the GHASH output with, but this requirement is only a “should”.

  The size of the packets should be kept as small as possible. The overhead of the ciphertext should be equal to the 96-bit nonce, 128 bit MAC, plus optional padding that might be used to mask the length of the plain text.

Depending on how exactly you implement this, the size of the packets will actually go down if you use a fixed nonce and unique message bodies.

  I don't want to consider all possible security implications of letting the recipient simply try all possible implicit packet counter values in order (DOS-attacks, timing attacks, etc).

There won't be any packet counter values to try because it's completely out of the attacker's hands.


Why are side channel attacks such as SPA/DPA/ CPA based on the AES SubBytes routine?

The values targeted by CPA are of the type $S(p\oplus k)$ where $p$ is a plaintext and $k$ a key byte, and $S$ maps bytes bijectively to bytes. One finds the correct key $k_0$ by correlating the Hamming weight of $S(p\oplus k)$ with the power consumption, as the absolute value of the correlation is expected to be the highest for the correct key $k_0$ at the time $t_0$ when the $S$-box output is processed in the CPU.

Now assume that for a second key $k_1\ne k_0$ the values of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ differ only by a single bit for all plaintext bytes $p$. Then also their Hamming weights differ only by 1, and therefore the Hamming weights of $S(p\oplus k_0)$ and $S(p\oplus k_1)$ are strongly correlated. So whenever $k_0$ gives a high correlation between current consumption and predicted Hamming weight, so does $k_1$, which makes both keys difficult to distinguish, if one wants to know, which one is the correct one.

If $S$ happens to be linear, then $S(p\oplus k_0)\oplus S(p\oplus k_1) = S(k_0\oplus k_1)$ is independent of $p$. So if $S(k_0\oplus k_1)$ has Hamming weight 1, one is exactly in the bad situation (for the attacker) of the last paragraph. For $S$ bijective linear, this occurs for $8$ different key bytes $k_1$'s.

As the $S$-boxes have to protect the crypto-algorithm against linear and differential attacks, they are chosen such that $S(x)$ and $S(x\oplus\Delta)$ are "linearly as independent as possible". In particular, also their Hamming weights have as little correlation as possible. So if you have a high correlation with $S(x)$ (think $x=p\oplus k_0$), you will not have much correlation with $S(x\oplus\Delta)$ (think $\Delta=k_0\oplus k_1$), making different key bytes easily distinguishable.

Differently phrased, real $S$-boxes fulfill the basic assumption of DPA that wrong keys give random predictions for the current consumption, whereas linear $S$-boxes violate it.

In conclusion, any $S$-box good for "classical" cryptography is bad (=good target) for side-channel attacks like CPA, and vice versa. (There are some papers published about finding $S$-boxes good for both purposes, but to my knowledge none were found yet, and I'd be surprised if there will be.)

I do not know the article you ask about, but judging from the abstract the authors are only interested in an efficient (time+space) HW-implementation of the AES S-box, and not at all in security against side-channel attacks (they would mention it).

For the security against CPA it doesn't matter how an intermediate value you try to attack was created in the HW, only if it (or something else correlated to it) shows up leaking side-channel information (like power consumption).

Trying to fight side-channel attacks without using dynamic random (dynamic = freshly generated each time the algorithm is run) I wouldn't bet on. Just take a look at how easily all white-box implementations got broken using DPA-like techniques.


paradox on fully homomorphic equality checking

This is somewhat a paradox. It seems that if the server cannot know when equality is reached, how can it return only those documents. Surprisingly, it can be done, under the assumption that an upper bound is given on the number of documents (and at the cost of that upper bound).

Assume first that only one document matches, and this is known. Denote by ${\cal X}=X_1,\ldots,X_n$ the documents, and assume that there exist lists ${\cal L}=L_1,\ldots,L_n$ such that $L_i$ is the list of keywords in $X_i$. (This is just to simplify the explanation.) Then, let $f(a,L_i)=1$ if $a$ is in the list $L_i$, and otherwise $f(a,L_i)=0$. Clearly, $f$ can be computed inside FHE. Then, the server can compute the function $g(a,{\cal X},{\cal L})=\sum_{i=1}^n f(a,L_i) \cdot X_i$ inside FHE and return the result to the client. Since we are guaranteed that only one document matches, we have that $f(a,L_i)$ will equal 0 in all but one place. Thus, if $a\in L_j$, then the result will be $X_j$ only.

In order to extend this to the general case where an upper bound $t$ is given on the number of matches, the following can be done. Define $f_m(a,i,{\cal L})$ to be a function so that $f_m(a,i,{\cal L})=1$ if $L_i$ is the $m$th list $(1\leq m\leq t)$ in ${\cal L}$ containing $a$, and otherwise equals 0. Then, define $g_m(a,{\cal X},{\cal L})=\sum_{i=1}^n f_m(a,L_i) \cdot X_i$. Finally, the server computes and returns to the client the (encrypted) values $g_1(a,{\cal X},{\cal L})$, $g_2(a,{\cal X},{\cal L})$, up to $g_t(a,{\cal X},{\cal L})$.

In this way, the communication is just $t$ ciphertexts, and thus not everything needs to be returned.

Note that if you don't have any upper bound on the number of responses, then you can't do this, and you end up sending everything. In order to solve this, the client can first send an encryption of $a$ to the server, who then computes a function that just returns the number of lists that $a$ appears in. The client can then decrypt and send this to the server who continues as above. This does require interaction, but solves the problem of knowing a reasonable upper bound on the size of the output.


Scalar product of vectors over polynomial rings

To encode vectors following that technique, you just have to generalize it.

For any two $(d+1)$-dimensional vectors $a = (a_0, a_1, ..., a_d)$ and $b = (b_0, b_1, ..., b_d)$, define the polynomials $a(x) = a_0 + a_1x + ... + a_dx^d$ and $b(x) = b_d + b_{d-1}x + b_{d-2}x^2 + ... + b_0x^d$.

Then, when multiplying $a(x)$ by $b(x)$, among all the coefficients that we multiply, we will multiply $a_0$ by $b_0x^d$, also $a_1x$ by $b_1x^{d-1}$, $a_2x^2$ by $b_2x^{d-2}$, and so on... Notice that all that multiplications are of the form $a_kx^k \cdot b_kx^{d-k}$, which result in $a_kb_kx^d$. Therefore, if we look to the $d$-th coefficient of the product polynomial we will see

$$\left( \sum_{k=0}^d a_kb_k \right) x^d$$

and that summation is exactly the inner product between the vectors $a$ and $b$.

It is worth noting that if this summation is greater than the module of the plaintext ring (usually a parameter $t$ or $p$), than the decoding will not work. Also, that representation is only possible if that value $d$ is smaller than the degree of the polynomial used to define the quotient ring (usually a cyclotomic polynomial).


Not unexpectedly, the correlation immunity of a vectorial boolean function $$S:\mathbb{F}_2^n\rightarrow \mathbb{F}_2^m,$$
is defined as
$$
CI(S)=\min \left\{ CI(a^{\top} \cdot S(x)): a \in \mathbb{F}_2^m, a\neq 0_m\right\},
$$
where $0_m$ is the all zero vector of length $m.$ Thus, it is the minimum correlation immunity of all the possible nonzero XOR sums of the output bits of $S$. In the absence of further knowledge about the Sbox, you need to compute a boolean correlation immunity $2^{m}-1,$ times and take the minimum.

In the Rijndael specification, as well as in the book \textit{The Design of Rijndael}, there is a nice chapter entitled Propagation and Correlation, where this is explored from an algebraic point of view. This helps in analysing compositions of functions, when one looks at multiple rounds or cascaded functions.


Is TLS finished message encryption at record protocol redundant?

If you do Finished after change_cipher_spec, and since Finished has to be the first message after setting the cipher spec, you get the added benefit of requiring a successful decryption of a message before any (potentially sensitive) user data is transmitted. This step serves as an extra "checksum".

From Section 7.4.9 of RFC 5246: (emphasis mine)

  The Finished message is the first one protected with the just
        negotiated algorithms, keys, and secrets.  Recipients of Finished
        messages MUST verify that the contents are correct.  Once a side
        has sent its Finished message and received and validated the
        Finished message from its peer, it may begin to send and receive
        application data over the connection.

Edit:

You wonder if encrypting Finished is unnecessary given that verify_data provides sufficient authentication against tampering. I claim that an sending an unencrypted Finished message would be quite disastrous for TLS.

The end of a normal TLS handshake looks as follows:

$\text{client} \rightarrow \text{server}:$ change_cipher_spec

$\text{client} \rightarrow \text{server}:$ Finished $a_k$

$\text{server} \rightarrow \text{client}:$ change_cipher_spec

$\text{server} \rightarrow \text{client}:$ Finished $a_k$

$\text{client} \rightarrow \text{server}:$ encrypted application data transmits... $m_k$

Here, $a_k$ and $m_k$ are the authenticaton code for Finished and session data keyed by $k$. It's important to reiterate that before a change_cipher_spec message is received, the current cipher suite offers no encryption or authentication; it's still pending the negotiated parameters upon receipt of change_cipher_spec.

Now imagine Andy Adversary on the network observing this handshake. In the special case where the negotiated cipher suite only handles authentication and not encryption, Andy removes the change_cipher_spec messages, so that the client and server never update their cipher suites and thus never enable authentication or encryption with the negotiated parameters. Welcome to catastrophe. Now Andy sits in the middle, stripping off authentication fields from Finished messages and later sensitive session data. So now you have no authentication either.

Here's the modified, defeated handshake:

$\text{client} \rightarrow \text{adversary}:$ change_cipher_spec

$\text{client} \rightarrow \text{adversary}:$ Finished $a_k$

$\text{adversary} \rightarrow \text{client}:$ Finished $a$

$\text{server} \rightarrow \text{adversary}:$ change_cipher_spec

$\text{server} \rightarrow \text{adversary}:$ Finished $a_k$

$\text{adversary} \rightarrow \text{client}:$ Finished $a$

$\text{client} \rightarrow \text{adversary}:$ unencrypted application data transmits... $m_k$

$\text{adversary} \rightarrow \text{server}:$ unencrypted application data transmits... $m$

It's easy for Andy Adversary to strip off the MAC field since there's no encryption. So now he has not only access to unencrypted, unauthenticated messages, but he can also forge whatever messages he likes.

If encryption were part of the cipher suite as is normal, the attack is much harder, but the point is that by passing in Finished after change_cipher_spec, you eliminate even the possibility of the attack.

What I have described here comes directly from Wagner and Schneier, who knew of this attack by 1997. As a matter of fact, they note that Netscape's SSL 3 implementation was vulnerable to it. Read Section 4.3 of that paper for more details.

Their recommendation to prevent such attacks?

  The simplest fix is to require that a SSL implementation
  receive a change cipher spec message before
  accepting a finished message.

They recognize this as a basic flaw in the specification of SSL, which of course was corrected in TLS:

  Some readers might complain
  that this requirement ought to be obvious with a moment’s
  reflection, even if it is not explicitly stated in
  the SSL specification. We cannot fault such clarity of vision.

In general, this is not the only attack that can be prevented by the "checksum" argument, or what Bellare and Rogaway call matching conversations, where both client and server verify encryption and authentication before transmitting sensitive data. See Section II-1 for another.

Conclusion: sending an encrypted Finished after change_cipher_spec is the simplest solution to protect the change_cipher_spec message.


Why don't we use Blowfish if it hasn't been cracked?

The reason is well-known, it has 64-bit block size and therefore it is vulnerable to birthday attacks. This is done for HTTPS and for more information see sweet32;
$$\text{Sweet32: Birthday attacks on 64-bit block ciphers in TLS and OpenVPN}
$$

Is it safe to use Blowfish to encrypt strings of less than 30 characters?
If I don't use it for HTTP, just for storing small strings, is it still insecure?

There is no problem. GnuPG made a recommendation for Blowfish;  Blowfish should not be used to encrypt files larger than 4Gb in size. If you want to use a block-cipher from Bruce Schneier use the successor, the Twofish algorithm, as he said.
This recommendation 4GB makes $\approx 2^{33}$-bytes therefore, they recommended using at most $2^{30}$ blocks of encryption under the same key. With the birthday probability if you encrypt $2^{30}$ blocks you will have
$$(2^{30})^2/2^{64}/2 = 2^{60 - 64-1} = 1/2^{5}$$ probability of collision. This is still a high probability in the attacker's advantage.

What is Sweet32 in short:
The attack performed on the CBC mode of operation where the encryption is $$c_i = E_k(m_i \oplus c_{i-1})$$ wiht $c_{-1}$ is the nonce for the CBC.
Once one encrypts $2^{n/2}$ blocks with one key by the birthday attack we expect a collision on the ciphertext with 50% probability that can be observed by an eavesdropper. This means that $c_i = c_j$ with $i \neq j$ is observed. Since a block cipher is a fixed permutation under a key this implies that the inputs of $c_i$ and $c_j$ must be the same;
$$ m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$ with changing the side of the values we get $$m_i \oplus  m_j = c_{1-1} \oplus c_{j-1}.$$ That is the eavesdropper knows the x-or of the two message blocks.

A short note padding oracles;
Padding oracle is first described by  Serge Vaudenay in 2002;

Security Flaws Induced by CBC Padding Applications to SSL, IPSEC, WTLS

years later real attacks are performed. Vaudenay applied it to RC5 in CBC mode, and it applies to any cipher that uses CBC mode as long as the server sends the padding-fail as an error. With the padding oracle attack, all messages can be revealed since it is a decryption oracle. Encrypt-than-Mac will prevent this attack.

Update for the comment;
It turns out that OP has X/Y problem; the short string is a password then the obvious choice is the well-known solutions like the argon2 which is the password hashing competition, winner. It has two modes;

Argon2d: is faster and uses data-depending memory access. Data dependency immediately enables side-channel. This is suitable for cryptocurrencies and applications with no threats from side-channel attacks.
Argon2i: uses data-independent memory access and this is preferred for password hashing and password-based key derivations.
If you are not sure about which one to use then you can use the combined mode Argon2id.


TLS: Does Diffie-Hellman make private keys useless

TL;DR: The host signs his public DH key

  When we are using TLS these days we use DH to establish a session key.

That depends, the RSA_ ciphersuites - that encrypt the session key using the RSA public key of the server key pair - can still be used even with TLS 1.2. They will be completely deprecated for TLS 1.3 as it looks now.

There are the ephemeral-static protocols as well - DH_ instead of DHE - although these are commonly not used in practice; they require a special X.509 certificate with DH or ECDH keys.

  So where in the TLS protocol do we determine that the host that we're talking to actually possesses the private key corresponding to the x509 certificate that it provided earlier?

Absolutely. Let's take a look at the 1.2 standard:

  When Diffie-Hellman key exchange is used, the server can either
     supply a certificate containing fixed Diffie-Hellman parameters or
     use the server key exchange message to send a set of temporary
     Diffie-Hellman parameters signed with a DSA or RSA certificate.
     Temporary parameters are hashed with the hello.random values before
     signing to ensure that attackers do not replay old parameters.  In
     either case, the client can verify the certificate or signature to
     ensure that the parameters belong to the server.

And this is apparent in the ServerKeyExchange message (in C):

case dhe_rsa:
    ServerDHParams params;
    digitally-signed struct {
        opaque client_random[32];
        opaque server_random[32];
        ServerDHParams params;
    } signed_params;

signed_params
    For non-anonymous key exchanges, a signature over the server's
    key exchange parameters.

  Or is this no longer required?

Of course this is required, unless another method of authentication - such as a pre-shared key (PSK) - is used. How would you otherwise authenticate the server?

Just possessing the public certificate is obviously not enough; the server needs to show that it can use the private key associated with the server certificate (within the verified & validated chain of certificates build by the client).


What is the meaning of the notation $\langle a, b\rangle$ in certain cryptography papers?

In mathematics, $\langle a,b \rangle$ represents the inner product of two vectors and this is a generalization of the dot product. It is one of the multiplications of the vectors in a Vector space and the result is a scalar.

An inner product satisfies these properties

$\langle c+a,b\rangle =\langle c,a\rangle +\langle a,b\rangle $.
$\langle \alpha a,b\rangle = \alpha\langle a,b\rangle$ where $\alpha$ is a scalar.
$\langle a,b\rangle =\langle b,a\rangle$.
$\langle a,a\rangle = 0 $ and equal if and only if $v=0$.

The fourth condition is the positive definite condition. Some authors define the inner product with only the first 3 conditions with a weaker 4th condition $\langle a, b \rangle =0$ for all $b$ then $a=0$.

As noted in the comments by @levgeni, if the field is $\mathbb{F}_2$ then

$$\langle (1,1),(1,1) \rangle = 1 \cdot 1 + 1 \cdot 1 = 2 = 0$$ and
$$\langle (1,1),(1,0) \rangle = 1 \cdot 1 + 1 \cdot 0 = 1 = 1$$ therefore, the weaker condition is required.

The inner product definition changes according to the vector space. In the context of the paper, let

$$a =(a_1,\ldots,a_n)$$
$$b =(b_1,\ldots,b_n)$$

be two n-dimensional vectors then;

$$\langle a, b \rangle = a_1 \cdot b_1 + \cdots + a_n \cdot b_n $$


I think what Bruce has done is to use Sign and Decrypt interchangeably, he has done same for Validate and Encrypt. I think it is because - to sign a message - Alice uses her private key. Now in terms of encryption / decryption, a private key is used to decrypt the message and a public key is used to encrypt the message.

So instead of saying:

Vm(Db(Eb(Sa(M)))) = Vm(Sa(M))

he is saying:

Em(Db(Eb(Da(M)))) = Em(Da(M))

Which I believe is same thing on implementation level.

So OP is correct, author has used different terms without specifying they are same. This is mentioned it in the next paragraph.


Effective security of block cipher – equal the key size, or half the key size?

I just read that chapter of the book, and the authors don't really justify their claim.

They also talk about "using random data to prevent collision and precomputation attacks" (which would then give you back the full key-size crypto strength) – this is about using random initialization vectors and such.

But if you are using an insecure mode of operation, or a non-random IV where a random one is required, using a bigger key-size doesn't really help, as the attacks possible here are not really key-recovery attacks.

Where such stuff could work would be for hash functions (which have at most $2^{n/2}$ tries collision resistance, assuming $n$-bit output), and a secret key included in the hash makes the brute-forcing impossible. But this certainly is not "symmetric encryption".

Another possibility which would reduce complexity to half the key-size would be assuming a (large enough) quantum computer – that could do a brute-force key search in $2^{n/2}$ steps instead of $2^{n}$ steps. But the text in the chapter doesn't really look like they are referring to this.

The crypto strength of an ideal symmetric cipher in absence of new generic attacks is equal to its key size (i.e. you need in average $2^n/2$ tries for a brute force key search attack).

Generally this is valid for all non-broken encryption algorithms, too (just by definition of "non-broken"): A symmetric cipher with key-size $n$ bit should offer $n$ bit crypto strength.

So my say would be: "Use a bigger key-size if you are concerned about future quantum computer attacks (or generally attacks on the algorithm which shave off some of the security, but not all of it), otherwise stay at 128 bit."


How hard is it to recover $p$ if I can get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$?

Let $x = h(p)\oplus h(p^*)\oplus r$. If $h(x) = h(r)$, then either $p = p^*$ or you've found a collision for $h$ (which happens with low probability). Since $p$ is generated from some low-entropy distribution, I assume it's feasible to brute-force over all possible values of $p$, allowing you to recover $p$ by checking whether $h(x) = h(r)$ for each guess $p^*$.


Is there a tangible benefit in keeping the number of PBKDF iterations secret and not storing them with the ciphertext?

I don't think it is a good idea, for two main reasons.

Firstly, you are basing your security on the obscurity of a parameter that was not designed initially for being secret, which is a risky practice. It is similar to hiding the salt.

Secondly, following your example, you may in principle think that a random number of iterations between 10 and 100,000 is providing you with (roughly) 17 bits of additional entropy. That is, in addition to your initial secret password (with $K$ bits of entropy), you have to store the number of iterations, so your final secret is $K+17$ bits long. However, you are not actually gaining that additional level of security, since the iterative process for key derivation is, indeed, iterative, and for each password attempt, the partial results of each iteration can be reused for the next one.

The cost of a brute-force attack against a standard key derivation method will roughly be $2^p\cdot C \cdot N$, where $p$ is the bit length of the initial password, $C$ is the cost of each iteration (typically a hash-based function), and $N$ is the default number of iterations (e.g., 1000 iterations).

The cost of a brute-force attack against your approach will roughly be $2^p\cdot C \cdot 2^{17} = 2^{p+17}\cdot C$, since for each password you will perform $2^{17}$ iterations in the worst case. That is, your approach is, in the worst case for the attacker, equivalent to the standard one with the "highest feasible number of iterations" (as you put it in the question). To see this, consider the following example of brute-force attack to your approach: the attacker is trying different possible passwords (first "aaaaa", next "aaaab", etc.). In your approach, the attacker doesn't know the number of iterations. Let's assume she is trying the i-th password, for instance, "aabhjk". It is clear that the attacker cannot reuse the work for previous passwords. The attacker starts brute-forcing "aabhjk" with the minimum number of iterations (1000), with no luck. Next, she has to try "aabhjk" for 1001 iterations, but she doesn't start from scratch. She reuses the work done before with the 1000 iterations, and perform an additional one. This strategy is repeated until reaching "the highest feasible number of iterations", as you put it. That is why, at the end, your approach is similar (in terms of a brute-force attack) to simply using a very high number of iterations.

If instead of following your approach, you append those extra bits (i.e., the bits required for storing the number of iterations) to your password, and simply use the standard key derivation method, then the cost of a brute-force attack is $2^{p+17}\cdot C \cdot N$.

That is, your approach is, in fact, weaker than simply using the number of iterations as a suffix to the password. From a quantitative perspective, it could be approximately $N$ times weaker, where $N$ is the default number of iterations.


Compressing BLS signature with a hash function

but I'm wondering if there are any other issues with using this scheme:

  $H_2(e(P, H(m))) \stackrel{?}{=} s$

The obvious problem is that anyone with the public key can compute everything on the left side, and hence forge a signature to any message they want.


Security of Keccak/SHA3 against birthday attacks

Let us correct some of your numbers. The size of the capacity is twice the size of the expected security margin (against a birthday attack). This is the idea of flat sponge clain etc

  When using a random sponge as a security reference, one considers the success of a particular attack. Such a success probability depends not only on the nature of the attack considered but also on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the upper bound on the random oracle differentiating advantage [Bertoni et al., Eurocrypt'08], which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity $c_{\mathit{claim}}$. [source]

Thus if you aim for a security margin of $128$ bits, you need to have a capacity of $256$ bits.

  In this approach, one designs a permutation $f$ on $b=r+c$ bits and uses it in the sponge construction to build the sponge function $F$. In addition, one makes a flat sponge claim on $F$ with a claimed capacity equal to the capacity used in the sponge construction, namely $c_{\mathit{claim}}=c$. In other words, the claim states that the best attacks on $F$ must be generic attacks. Hence, $c_{\mathit{claim}}=c$ means that any attack on $F$ with expected complexity below $2^{c/2}$ implies a structural distinguisher on $f$, and the design of the permutation therefore attempts to avoid such distinguishers. Note that the existence of a structural distinguisher for $f$ does not necessarily imply an attack or weakness in $F$. For example, any distinguisher for $f$ that has success probability zero below $2^{c/2}$ forms no threat, as the flat sponge claim expresses no security against adversaries that may send more that $2^{c/2}$ queries. [source]

TL;DR: the security margin is half the capacity. If you aim for 128 bits, you need a capacity of 256 bits.

That being said, we can move to your misunderstanding. You are right to say that if you take an output length of $1$ bit, you won't have the $64$ bits security claim... because you are looking for a collision in the output.

When you use $\operatorname{Keccak}$, you can retrieve the full size of the bit rate ($r$). You can also extend this output and because these outputs are related  (as you basically always know the content of the bit rate part). Thus the only part that you don't know is the capacity. If you are able to guess or have a collision on this part, then the output is compromised.

The capacity is the only part of the state that you don't know.

When you want a collision, you look either to have a collision on the capacity part or on the bitrate part which is usually bigger than the capacity...

Let $a,b$ be two inputs and $c,c_1,c_2$ the capacity part. You have a collision when :
$$f(a) \to [\theta \mathbin\| c_1]\\f(b) \to [\theta \mathbin\| c_2]$$
where $[\theta \mathbin\| c]$ is full state and $\theta$ is the resulting output (here your output length is important).

The other way to find a collision is to manage to get:
$$f(a) \to [\alpha \mathbin\| c]\\f(b) \to [\beta \mathbin\| c]$$
(collision in the capacity), because then you can have (due to the simplified sponge construction):
$$\begin{align}
f(a \mathbin\| 0) & \to [\alpha \mathbin\| c] &\Rightarrow&&& f([\alpha \oplus 0 \mathbin\| c]) \to \theta \\
f(b \mathbin\| \beta \oplus \alpha) & \to [\beta \mathbin\| c] &\Rightarrow&&& f([\beta \oplus \beta \oplus \alpha \mathbin\| c] ) = f([\alpha \mathbin\| c]) \to \theta
\end{align}$$

TL;DR 2: as @CodeInChaos said Collision resistance is $\min(c/2,n/2)$ and preimage resistance $\min(c/2,n)$ where n is the output size.. But most papers search collisions on $\operatorname{Keccak}[1600]$ thus why they usually state this more generic security margin ($2^{\mathit{capacity}/2}$).


Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in zero-knowledge, the argument is that the adversary learns nothing since it can generate anything it sees by running the simulator itself. However, when using complexity leveraging, the adversary actually cannot run the simulator (since it is in a lower complexity class). Nevertheless, in some cases, it can be meaningful. For example, let's consider a security notion that is "game-based" or indistinguishability based. We then prove that if an adversary running in polynomial-time can break our scheme, then there exists an adversary running in time say $n^{\log n}$ who can break a hash function (or anything else; this is just an example). Now, if the hash function is assumed to be secure for any adversary running in time $n^{\log n}$ then this is enough to guarantee the security of our scheme.
I am personally not a big fan of complexity leveraging. Beyond the definitional disadvantages in some cases (e.g., with simulation), there is also a big disadvantage in that it requires a much stronger assumption (not that a primitive cannot be broken by poly-time adversaries, but by super-poly-time adversaries for some specific function). However, it has been used successfully to achieve things that are otherwise unknown. In addition, in many cases, a first construction used complexity leveraging, and then later constructions succeeded in getting rid of the assumption.
========
Added later: The reason why stronger assumptions are needed is as follows. Assume that you have a reduction from ZK to OWFs so that any algorithm distinguishing the simulation from a real execution with non-negligible probability can invert the OWF with non-negligible probability. Now, assume that you use quasi-polynomial simulation. In order to argue that the adversary learns nothing, you need to assume that the one-way function is secure against quasi-polynomial inverters. This is because, in order to replace the real proof execution with a simulated one, you need to run in quasi-polynomial time. So, now you have a quasi-polynomial time adversary who is actually running. Then, the reduction to the OWF will only work if the adversary cannot break that OWF. (Of course, this is all handwaving, but this is what happens in proofs.)


What is the most secure encryption algorithm to encrypt my password database?

The number denotes the size of the key used - for a given algorithm, the larger the key, the more secure it is - hence AES-256 is better than AES-192 is better than AES-128.

The key size is measured in bits - so in terms of its protection against a brute force attack (attacker tries all possible keys) a 256 bit password is not twice as hard to break as a 128 bit password, it is 34000000000000000000000000000000000000 times as hard.

But there are other ways to attack encryption - exploiting mathemetical flaws/coincidences in the algorithm. Although 3DES uses 3 56 bit keys, the effective key size is only around 120 bits. But it is still considered better than RC2-128.

  Which algorithm is the most secure?

Of those you have listed, AES-256

  Does the algorithm provider matter?

No. In effect, it is just a list of available algorithms. But you do need to ensure the algorithm is available anywhere you want to decode the data.


How do I derive the time complexity of encryption and decryption based on modular arithmetic?

I'll be assuming the question considers time complexity in big-O notation only, because that's common, the simplest, and there is no indication of the contrary. The price to pay for this simplicity is that the resulting time complexity is often a poor way to compare the efficiency of different algorithms.

In this section I restrict to the standard algorithms for addition, multiplication and division (taught in elementary school using base $10$), because they are the simplest, and often used in cryptography (with a higher base like $2^{32}$, but that does not change the time complexity in $O()$ notation).
Computing $A+B$ or $A-B$ in $\mathbb Z$ has time complexity $O(a)$, where $a$ is the number of digits of $A$ (in any base), and $b=O(a)$ using the same convention for $b$. In a cryptographic context, we take the liberty of writing that time complexity $O(\log(A))$.
Computing $A·B$ in $\mathbb Z$ has time complexity $O(a·b)$, or $O(\log(A)·\log(B))$. When $b=O(a)$, that time complexity is $O(a^2)$, or $O(\log(A)^2)$.
Euclidian division of $A\in\mathbb Z$ by $N\in\mathbb{N^*}$, that is computing $R\in[0…N-1]$ and $Q\in\mathbb Z$ such that $A=N·Q+R$, has time complexity identical to that for computing $N·Q$, that is $O(n·q)$, or $O(\log(N)·\log(Q))$.
When performing modular multiplication $A·B\bmod N$ in a cryptographic context, it is typical, and assumed unless otherwise stated, that $a=O(n)$ and $b=O(n)$. It follows that the time complexity of modular multiplication is $O(n^2)$, or $O(\log(N)^2)$.
Modular exponentiation $A^B\bmod N$ with $B>0$ requires at least $\log_2(B)$ modular multiplications (baring shortcuts possible using the factorization of $N$), and less than ${3\over2}·\log_2(B)$ using square-and-multiply. It thus has time complexity $O(n^2·b)$ or $O(\log(N)^2·\log(B))$.
With standard RSA assumptions, computing $C^d \bmod N$ has time complexity $O(\log(N)^3)$; that's because $d$ has size in bits or digits proportional to that of $N$ (and further, close to that), thus the size of $d$ is $O(\log(N))$. This remains unchanged when the CRT technique is used and there is a fixed number of prime factors in $N$ (which reduces the computational cost "only" proportionally to the square of the number of factors).
In RSA, if the public exponent $e$ is fixed, or of bounded size (which is common, and mandated by FIPS 186), then computing $M^e\bmod N$ has time complexity $O(\log(N)^2)$; that's because it is done with a fixed or bounded number of modular multiplications (e.g. $17$ for the common $e=2^{16}+1$). On the other hand, $e$ is sometime allowed to be of the same order of magnitude as $N$ (e.g. in PKCS#1), in which (rare) case $M^e\bmod N$ has time complexity $O(\log(N)^3)$.
$O(\log(N)^3)$ is, of course, not the same as (and more than) $O(\log(N)^2)$. In practice, the RSA private key operation (using $d$) is often much slower than the public key operation (using $e$).
The most commonly taught algorithm to compute the modular inverse $k^{-1}\bmod N$ is the Extended Euclidian algorithm. It is easy to show that it requires at worse $O(\log(N))$ steps, and that the time complexity of any step is $O(\log(N)^2)$ in the worst case (e.g. on the first step for $k\approx\sqrt N$), which is enough for some to give the time complexity as $O(\log(N)^3)$. However, this is grossly pessimistic: the worst case in term of number of steps corresponds to steps of time complexity $O(\log(N))$, and longer steps correspondingly reduce the number of further steps. By induction, I come to the conclusion that the time complexity really is $O(\log(N)^2)$ (but I would not bet the house on that; I welcome a reference, a refutation, or a proof).
Computing $M·k\bmod N$ with the same assumptions as in standard RSA regarding $N$ and $M$, and assuming that $k$ has size proportional to that of $N$, has obviously the same time complexity as modular multiplication, $O(\log(N)^2)$.
Using the same assumptions, computing $C·k^{-1}\bmod N$ has time complexity $O(\log(N)^2)$; that is dominated by the modular inversion step, for any implementation I can think of that uses comparable care in the modular inversion and the modular multiplication.

Notice the importance of the assumption: standard algorithms for multiplication and division. By using the Karatsuba technique for multiplication and Barett reduction for Euclidian division, modular multiplication has time complexity less than $O(\log(N)^{1.585})$ rather than $O(\log(N)^2)$; that's useful, and used in some software implementations of RSA, reducing the time complexity of the private (resp. public) key operation to less than $O(\log(N)^{2.585})$ (resp. $O(\log(N)^{1.585})$). The exponent can go further down using Toom–Cook, which generalizes Karatsuba. Schönhage–Strassen multiplication has time complexity $O(\log(N)·\log\log(N)·\log\log\log(N))$.
Update: the ultimate theoretical technique is $O(\log(N)·\log\log(N)$, by David Harvey and Joris van der Hoeven's Integer multiplication in time $O(n\log n)$, published in Anals of mathematics, March 2021.
The crossover between classical and sub-quadratic algorithms depends a lot on the quality of the implementation, and in particular on how close to the CPU architecture it gets (that's an area where assembly language shines over C, which obstructs access to the carry bit, and often to the whole result of the product of two unsigned integers of the widest size natively supported). While nearly optimal implementations of the classical algorithms using assembly language are relatively common, implementations of sub-quadratic algorithms are often quite sub-optimal, or/and complex (and thus hard to prove right in all corner cases, with the possible exception of Karatsuba).
My usual online references for multiple-precision arithmetic are section 14 in the HAC, and Modern Computer Arithmetic.


Tackling encryption problems with "Zipf's law"?

No, it is not possible to semi-reliably "decrypt" an encrypted message by using the statistical distribution of symbols, if some modern encryption scheme is used, and its secret/private key does not leak. Modern encryption is practically immune to known distribution or other characteristic in the plaintext.

The goal of modern encryption, that it reaches in practice, is that given the ciphertext, but lacking the key (or the private key for public-key encryption), the only thing that can be determined about the plaintext is its length (and then perhaps, only the order of magnitude of that).

Modern encryption does not create a one-one match between symbols in plaintext and ciphertext (as is the case for monoalphabetic substitution, or Electronic CodeBook); that indeed would be a weakness.


What kind of Quantum cryptography technology(protocols) can be used for Mobile Ad hoc networks(MANETS)?

QKD aims at exchanging key material to be used with encryption based on OTPs between two parties and thus to achieve perfect secrecy for transmitted messages.

There are, however, several drawbacks for practical use in a wired setting of QKD (required hardware and their vulnerability to hacks, limited distance) which does not support their use for end-to-end confidentiality over longer distances. Consequently, it is required to run QKD between single hops and thus re-encryption is required and the plaintext is revealed to the intermediate hops). For the latter, nevertheless, there are some ideas to overcome this problem.

In the non-wired setting as it is the case for MANETs, however, it is very questionable if QKD could bring any benefit. This is due to required hardware (presumably not available at the nodes) and the missing fiber optic links. Regarding the latter issue, there are some studies with single photon sources doing QKD at night over the air - presumably far away from civilisation - and at a very low bit rate, but that seems rather esoteric at the moment.

Edit As Frédèric pointed out in his comment, over the air QKD is not that esoteric as I assumed, since there are works, e.g., this one, demonstrating feasability of over the air QKD at daylight.
/Edit

The most important issue from my perspective, however, in a MANET setting is due to missing infrastructure. With whom you want to exchange keys using QKD? Presumably, you do not trust your neighbours and then it makes no sense to exchange keys with them using QKD, since the respective node could read your messages. If you want to encrypt something for some far away party and therefore require end-to-end confidentiality, then you will very likely not be able to exchange a key using QKD with this party. So why using QKD in such a setting (besides the above mentioned problems)? Then you could pre-distribute key material, but using OTPs will be impractical due to the large key material required. So you will very likely drop the perfect secrecy requirement and come back to traditional (secret key or public key) encryption schemes.


How do cryptographic systems handle such situations? … What actually is done in real life?

In real life, cryptography handles situations like the one you describe by using “authentication”. Authentication links an action, a message or a situation to an identity. In the example you describe, this will practically boil down to a validation of something an entity knows… like a password, a key, or another kind of secret.

Simplified, you could think of authentication as something which enables you to validate if an entity is actually who they claim to be, or allowed to do something, by showing they know a secret that only they could know. (Note that “authentication” does not always mean an entity proves its individual identity; it can also be used to prove an entity is part of a group of entities knowing a certain secret.)

For better understanding of what “authentication” is, it may be helpful to know there are also other forms (better: factors) of “authentication”. Chances are, you’ve already have met such “authentication” in real life yourself, since “authentication” can be proven by something an entity has – like a passport, a smartcard, a token device, or something similar.

Besides that, “authentication” can be proven by an entity by something an entity is. For example: humans have specific, individual features. These can also be used for “authentication”… which makes up one of the areas biometrics covers. If you‘ve ever had your fingerprint or iris scanned, or if you ever saw that in a movie… well, that’s what we call “authentication” in the realms of cryptography.

As said, in your example Bob and Alice will use a shared secret to enable mutual authentication. Not knowing the secret, Mallory will not be able to successfully authenticate her messages as Bob will detect the missing or wrong authentication factor (the secret) and reject and/or ignore Mallory’s messages/attacks accordingly.

Of course, authentication alone won’t make a protocol secure. Besides authentication things like secure connections (using encryption, etc.) are needed to wrap a secure shield around things. But authentication is an important part of cryptography, as it allows (for example) to learn if the entity you are communicating with is indeed the entity you expect to be communicating with… and not some kind of adversary who tries to inject or even replace messages which you might think are secure. They may be secure due to encryption, but without authentication that’s not worth all too much. Yet, the combination of both make up a pretty solid way of exchanging information between two entities.


Effect of message length on collision attacks

The short answer is that for any secure hash it is impossible to generate collisions or second preimages, regardless of message length.

If you look at theoretical attacks, however, message length can be a factor. When looking for another message that hashes to the same value as a specific message you are talking about second preimage resistance (or target collision resistance) and there the length of the target message may matter. For example, with Merkle-Damgård hash functions there are attacks that find second preimages for messages faster the longer they are.

With a collision attack, where you look for any pair of messages hashing to the same value, I do not know of a case where message length matters. Beyond allowing enough input length to exhibit collisions, of course: finding e.g. 1-byte collisions is impossible.


Selective Forgery of a Digital Signature - Goldwasser et al

The reference is Shafi Goldwasser, Silvio Micali, Ronald L. Rivest, A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks, in SIAM Journal on Computing, 1988.

It defines

  Selective forgery. Forge a signature for a particular message chosen a priori by the enemy.

Here, "a priori" means, informally, that the message is to some degree chosen by the adversary (or at least restricted) before the attack is carried, as opposed to being entirely a result of the attack.

The authors do not give a formal definition. One could be that the adversary must define, before being given the public key, a suitably small subset of the full message set among which s/he will later be able to exhibit a forgery (that is, an acceptable message/signature pair for which s/he has not obtained the signature by asking a signing oracle).


Do Carmichael's and Euler's totient functions in RSA generate the same keys?

There is no standard definition of "same" when applied to cryptographic keys.

There is a precise definition of equivalent keys: keys which always yield the same effect when used for their designated usage, e.g. encryption, decryption, signature generation or verification. For example, in DES, low order bits of key bytes play no role, thus 0123456789ABCDEF (in hexadecimal) is a key equivalent to 0022446688AACCEE, if the later is considered valid. In TEA, 0123456789ABCDEF0123456789ABCDEF is equivalent to 8123456709ABCDEF8123456709ABCDEF.

In RSA, Carmichael's and Euler's totient functions generate equivalent keys, even though (in the variant of RSA where the private exponent $d$ is generated from the public exponent $e$) the resulting values of $d_\lambda=e^{-1}\bmod\lambda(n)$ and $d_\varphi=e^{-1}\bmod\varphi(n)$ often are not equal. Example:$$\begin{align}
n&=5\times11=55\quad&e&=3\\
\lambda(n)&=\operatorname{lcm}(4,10)=20\quad&d_\lambda&=7\\
\varphi(n)&=4\times10=40\quad&d_\varphi&=27
\end{align}$$

In the (original) variant of RSA where the public exponent $e$ is generated from the private exponent $d$, we'd often have different $e_\lambda=d^{-1}\bmod\lambda(n)$ and $e_\varphi=d^{-1}\bmod\varphi(n)$.

Note: we do not even have a universally accepted definition of equal keys. Are two DES keys represented as 16 characters 0123456789ABCDEF and 0123456789abcdef equal? Does LF vs CR/LF matter in RSA keys as PEM files?


Lamport suggested the use of hash chaining in 1981 in Password Authentication with Insecure Communication, Communications of the ACM 24.11 (November 1981), pp 770-772.

He cites 3 prior papers:

Diffie, W., and Hellman, M.E. New directions in cryptography.
IEEE Trans. Inform. Theory 1T-22 (Nov. 1976), 644-654.
Evans, A., Kantrowitz, W., and Weiss, E. A user authentication
scheme not requiring secrecy in the computer. Comm. A CM 17, 8
(Aug. 1974), 437-442.
Wilkes, M.V. Time-Sharing Computer Systems. American
Elsevier, New York, 1972.

[1] is the paper which essentially invented Public Key Cryptography in the open literature. Lamport refers to the use of a one way function F, as described there, as hash functions in his chain.

[2] and [3] are cited for "the widespread use of such a function", e.g., storing $y=F(x)$ instead of $x$.

So it seems to me Lamport may well be the first to suggest the use hash chaining.

Edit: Thanks to @Gilles for pointing out Merkle patented hash trees in 1979.


The private keys are integers $x$ with $2^{254} \leq x < 2^{255}$ and $x \equiv 0 \pmod 8$, or just $x \in 2^{254} + 8\{0,1,2,\dots,2^{251} - 1\}$, so there are exactly $2^{254}/8 = 2^{251}$ of them.


Yes, there are attacks. Hash functions aren't designed for massive related message first preimage attacks. In an ideal scenario. Where the attacker can get a MAC for any string he wants that's what the hash has to stand up against. The one way function inside MD4 has to resist being reversed even when fed with lots of attacker controlled message blocks. This isn't something it was designed to do.
MD4 is similar to most of its successors (MD5 SHA1, SHA2) in that it's built from a Davies–Meyer compression function. There's an internal 128 bit state. To process a message block, the state is encrypted using a 128 bit block cipher keyed with the message block (512 bits --> 32bits x 16 words). To make the function one way, the input value is added to the output before processing the next block.

So, consider this a sort of fault injection attack. We get to flip bits of the round keys and see the resulting cipher-text (with the plaintext as an offset) we can vary the other message blocks to vary the plain-text that will be encrypted and then added to the result before we get it. The goal is to recover the plain-text.
The block cipher here has 48 rounds. There's about 200 nonlinear operations, with pretty good mixing between rounds. This sounds pretty horrible right?
Well the rounds are actually split into three groups of 16 rounds and the key schedule isn't too complex. Each of the 16 rounds in a group uses one of the 32 bit words in the current message block as a round key. Any bits we flip in a message cause a bit flip in three of the round keys.
Let's say we flipped two bits, one in one round key and another in a later round key. It's possible that the first bit flip would be cancelled by the second. Its also possible for this to repeat itself for the same bit flips in the second group of rounds. That would leave only the bit flips in the final group of rounds which are close enough to the final value we see that we might be able to distinguish that case.
Taking a look at section 3.4 of the MD4 spec, pairs (5,9) and (6,10) look promising. They aren't used too far apart in the first and second round groups while also being close enough to the end in the third round group not to have the differences spread too much before the end
(11,14) would be better but are more limited since 14 is part of the padding (the message length) which limits the bit flips we can do.
So we need the differences to cancel in the first and second round groups. We detect the lack of significant change in the hash output. This gives us information about the internal state where the cancellation happened.
Once this happens, we can make a slight change in the area of the first cancellation and then make further changes afterwards until there's a cancellation in the second round group. This gives more information. As our information improves we become limited by the probability of the second cancellation since getting that to happen is blind luck. Eventually though, we would have the full state in the area of the first collision. Just work backwards from that to get the input, the thing we were trying to get.
What does this get you?
Case 1: The secret key is the initial hash state.
The attacker can recover the initial state used as the MAC key. They can now MAC any message they want.
Case 2: the secret key is prepended to the message data and the message and key fit in a single block.
This complicates the attack but likely not that much. This would directly recover the secret key.
Case 3: The secret key is prepended to the message but padded to take up the whole first block.
Now the attacker can't recover the key but , like with case 1, can recover the secret internal state required to MAC arbitrary messages.
Case 4: The minimum message size is several blocks.
Now the attacker can't recover the key. They can only work backwards 1 block at a time. Every output value used in attacking the second to last block has to be gotten by repeating the whole attack process for the last block. If attacking one block takes N queries, attacking two takes N^2 and 3 N^3 queries. They'll likely be able to change the last block but nothing else.
Is there any way to mitigate this without using HMAC?
Yes! Add 55 bytes (64 byte block - (8 byte length + 1 byte min padding)) of constant value padding to your message before hashing. This is enough to keep all message data out of the last block. Now the attacker can't get access to the output value of the last block for which they supply message data. None of the interesting behaviour is visible to them except through an entire block of nasty behaviour.
That other statistical attack
There is one other failure mode worth mentioning. Thanks to the birthday paradox, submitting on average 2^64 plain-texts where a single block is tweaked will yield a collision. If they do the same for a second block they'll also get a collision. The important point is, this is a collision in the internal state so where A and A' are the first set of colliding blocks MAC(AB)=MAC(A'B)=MAC(AB')=MAC(A'B'). The internal state after processing block A is the same as after processing block A'. This is known as a multicollision and generalizes to multiple chained blocks. Using MD4-HMAC does not help with this since this is a fundamental statistical weakness of Merkle–Damgård construction.
What about other hash algorithms (MD5, SHA1, SHA256 ...)
They would be a lot harder to attack if not impossible. The same properties that make this kind of attack function also make it easier to find collisions. MD5 has four round groups with more shuffling of sub-keys. All other variants have a real key schedule with messy nonlinear operations used to expand the message block into multiple round keys. The probability of touching something deep inside and not completely changing the output is negligible.


Block Cipher CTR mode when offset is not known by receiver

Most protocols are like TLS, where you can't start in the middle. In most protocols, the counter is implicit, the receiver needs to count blocks from the beginning, if the receiver doesn't know the current value they can't decrypt.

The reason this is not a problem with live streaming video on the internet is that in modern video livestream, the video is cut into little 5 second chunks encoded in multiple resolutions for clients with different effective bandwidth, and the client uses TLS download of each 5 second chunk of the video, switching to smaller or bigger version depending on how long it took to download the previous 5 seconds of video. See HTTP Live Streaming.

Most protocols do not support "tune-in in the middle of broadcast, already have shared symmetric key, start decrypting in middle of stream".

If you are developing something like encrypted broadcast with shared key, you need your protocol to insert "resync" metadata every few seconds (maybe every second) for the benefit of clients tuning-in just now [1]. Maybe the resync provides only markers, and the "handshake" protocol the joining client uses to receive the shared symmetric key will also give the client the counter value for the next marker.

1 - Video codecs also need to do that if the video is not cut into separate 5 second video files (see "Periodic Intra Refresh" in x264).


Encoded Binary Value: 11000001 (Is this regarded as the ciphertext?)

Yes. Or at least it is considered a block of ciphertext, as in, the output of a block cipher. A block cipher in itself is not a CPA secure cipher, as identical input messages (plaintext) will lead to identical output.

  Finally convert, the encoded binary value back to ASCII: ? (Could someone please explain how this is done?)

You look up 0110 on the top row listing the high order bits, and then lookup 0101 in the low order bits, so you'll find the lower case e again. Of course most computer languages have functions such as CHR$ to do this for you.


Calculating G for a give cyclic group mod P

How is this done efficiently on the fly for Diffie Hellman?

For Finite-Field Diffie-Hellman, you usually pick $p$ such that $q=(p-1)/2$ is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is $p-1=2q$. This leaves us with four divisors: $1,2,q,2q$. Once you know that, you can simply test that your chosen candidate $g$ doesn't have order $1$ nor $2$ which you can test by checking that $g^2\neq 1\pmod p$. If you now explicitly want either of the other two orders you can test whether $g^q=1\pmod p$ and if yes you have a generator of order $q$ and if not then it has order $2q$. As to whether we can actually find the two interesting cases, Sylow's theorems guarantee this and usually you would start with $g=2$ and count up until you have a suitable candidate.


How many bits in the resultant hash will change, if the x bits are changed in its the original input?

For any one of the SHA hashes, the hash should be indistinguishable from pseudo-random. That means each and every bit flips with a chance of 50%. So on average half of the amount of bits gets flipped, as long as the input message doesn't repeat (because that will match 100% with the hash of the identical message, of course). It doesn't matter how many input bits are removed, added or altered, this is always the case as long as the input message isn't identical to the previous one.

Hashes are likely well distributed, so the likely number of bits that get flipped is a bell curve like you would get by throwing dice. Same thing for the number of zero bits - or one bits of course. So you cannot give an absolute number as an answer to this question. The result is not a function on $x$ if $x$ is the number of bits flipped in the input - as long as $x$ is larger than zero.


Zero-knowledge proof for the product of additive Paillier ciphers

Assuming entities do want Bob to decrypt the sum, but not be able to decrypt individual ciphertexts: enitites would send commitments to plaintext to Bob while sending ciphertexts to Alice. Commitment scheme should be additively homomorphic such that Bob could open the result (over commitments collected) with plaintex decrypted as verification. This would prevent Alice from manipulating ciphertexts collected (assuming honest entities).

Please note plaintext is not an integer in Paillier scheme modulo $n^2$, but a ring element modulo $n$.


How is the usual way of using PKCS5/7 when a weird data is given?

The PKCS 5/7 encoder would not do anything since it has all 16 bytes (1 block size required by AES cipher).

That's where you're wrong.

Padding should be always applied. If the user is encrypting a plaintext that is already a multiple of the block size, then the PKCS#5/#7 padding schemes will add an additional full block of padding, so that there is no ambiguity when decrypting.

In your example, that would mean this is the padded plaintext that is encrypted:

05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 05 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

There are of course padding schemes that don't add an additional block (for example PHP's zero padding), but that's not how PKCS#5 or PKCS#7 works.


Why does Salsa20 algorithm require incrementing word[8] and word[9] after producing cipher text message

This code only increments word 9 when word 8 is zero. Just like when counting you increment the next digit whenever the previous digit is zero, going from 9 to 10.

This is equivalent to having a 64-bit counter and putting the lower half into word 8 and the upper half into word 9.


Will knowing clear text value behind encrypted data help hacker find password?

OK, so what you are doing right now is the following:

The user enters the password.
It gets run through a PBKDF.
The resulting key is used to verify that a stored string decrypts to "foo bar"
If it does, the derived key is used to decrypt the database.

While this should work and there's no risk with publishing "foo bar" because the data stays inaccessible. It would be a nice idea (from a design point of view) to use a proper verification primitive here. This can be something simple, like verifying that the stored HMAC-value is actually the HMAC of an empty string using the derived key.

While an attacker can swap out said encrypted string in theory, this would gain him nothing with regards to the actual data and only allow him to inconvience the user a bit. Now you could argue that using such a string could inconvience the attacker, but all he would have to do, is to reverse-engineer the application to find the string.

Also note that you must not use the an easier password-based key derivation function for either the password verification or the database decryption because the attacker then gets to chose against which he wants to brute-force.


Build a cipher that is secure against message recovery attack but not semantically secure

The basic idea of constructing such a cipher is to exploit the fact (and the main difference between the definitions!) that $m$ is sampled uniformly at random from the message space for message-recovery security and can be chosen very specifically for semantic security.

This means that the easiest solution probably special-cases the encryption output for one specific input and acts securely for all others. The chance of hitting this one special-case is then negligible with message-recovery security, but can be made arbitrarily high with semantic security, allowing the special case encryption to be distinguished from any other encryption.


There is no such method.  The only reliable way to "fix" a backdoored RNG is to mix its output with another, secure RNG.

Specifically, let's consider a backdoor similar to that described by Becker et al. (2013), which essentially transforms the Intel TRNG into a deterministic PRNG using AES in OFB mode, with a 32-bit initial seed (occasionally reseeded) and a fixed key chosen by the attacker.

Between reseedings, the output stream of the compromised RNG is completely determined by the initial seed, which can take only $2^{32}$ distinct values.  Thus, an attacker who knows the hidden key can, after observing only slightly more than 32 bits of the output, look them up in a database to recover the seed (or just iterate through all possible seeds to find the correct one).

Alternatively, if the RNG output is used, say, to generate an public/private key pair, an attacker who knows the hidden key and the keypair generation method can easily generate all the possible keypairs and check which one of them matches a given public key.

The important point to realize is that no amount of deterministic post-processing can prevent these attacks — the attacker just needs to incorporate the same post-processing into their own output generation code.  The only thing that can stop such an attack is the addition of some other source of randomness, not predictable by the attacker, to the output.

(Actually, if I read the Becker et al. paper right, the specific attack they describe can be thwarted even without any external source of randomness, simply by feeding the compromised RNG output into a sufficiently large (e.g. 128-bit) entropy pool.  The reason this works is that their attack does still allow about 32 bits of true randomness to be output whenever the compromised RNG is reseeded, and mixing this into a non-compromised entropy pool will build up a considerable amount of randomness over time.  That said, presumably their backdoor could be modified to leak even less actual randomness into the output.)


AES-- Brute force attack versus Known plain text attack

I believe this question is only answerable if $F_k$ is easily invertible. In other words, if you can compute $M=F^{-1}_k(F_k(M))$. Then a standard meet-in-the-middle attack applies.

Given message $M$, ciphertext $C = E_k(M)$ for unknown $k \in \{0,1\}^{128}$, an efficiently-computable function $X$ such that $k = X(k_1, k_2)$ for some $k_1, k_2 \in \{0,1\}^{64}$, and an invertible function $F$ such that $E_k(m) = F_{k_1}(F_{k_2}(M))$ when $k = X(k_1, k_2)$, do the following:

Let set $K_1 = \{F_{k_1}(M):k_1\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
Let set $K_2 = \{F^{-1}_{k_2}(C):k_2\in\{0,1\}^{64}\}$. Computing and storing this requires on the order of $2^{64}$ steps and $2^{64}$ memory.
Find for $k_1\in K_1$, $k_2 \in K_2$ s.t. $k_1 = k_2$. We know that some such pair must exist based on the definitions of the functions $F$ and $X$. A simple way to do this is to simply sort the sets $K_1$ and $K_2$ ($2 \times\left(2^{64} \times \log(2^{64})\right)$ operations) then you can use a linear algorithm to find a matching pair ($2 \times 2^{64}$ steps).
Compute $k = X(k_1, k_2)$.

If you add together the time complexities given, it is easy to see that this algorithm requires on the order of $2^{75}$ operations and on the order of $2^{65}$ memory.


What is a known answer test

It appears to be a publicly available set of parameters and values that allow you to check the correctness of an implementation.

If so, then they're more commonly referred to as "test vectors".

  why is it useful?

Since the output of cryptographic algorithms are almost invariably supposed to "look random", it is very hard to know whether or not things are functioning correctly by just looking at the output.

With outputs that are known to be correct, you can supply the corresponding parameters to the software and test your outputs against the known correct answers.

If the two do not match, then something is wrong with the implementation that you're testing.

If the two do match, then it is probable that the implementation is (at least partially) correct.

It is possible to pass one test and fail another due to some kind of programming error, so a passing unit test does not mean that the implementation is guaranteed correct with 100% certainty (but it is probably correct with high probability if it passes all of the tests).


Statistical tests for PRNG that generates a sequence which is not binary

Randomness testing uses asymptotic properties. Thus, as the length of your input increases the effect you are concerned about will disappear.

Specifically, there is no need to convert ternary $1$ or $2-$tuples to binary. If you let $n$ increase you cover the interval $\{0,1,\ldots,3^n-1\}$ and then you convert these integers to binary, paying at most a 1 trit (Shannon's term for entropy in base 3) penalty in entropy. Since a decent ternary source should yield not much less than $$\left(\frac{\log 3}{\log 2}\right)n$$ bits or $n$ trits of entropy, there is nothing to worry about.


Proving knowledge of a preimage of a hash without disclosing it?

I'm not sure what I can add that wasn't covered in the talk. The approach is that Alice commits to the preimage and sends the commitment to Bob. The commitment has homomorphic properties, meaning it is possible to do computation on the value.

For example, if Alice commits to $x$ and $y$, Bob may be able to compute a commitment to $z$ where $z=f(x,y)$ for some function $f$. For example, if the commitments are additively homomorphic, Bob can add two commitments or multiply by a constant for free.

Alternatively, $f$ may not be directly computable. In this case, Alice who knows the actual values computes $z$, sends a commitment to $z$ to Bob asserting that it is correct. Bob holds commitments to $x$, $y$, and $z$; as well as knowing $f$. Alice can then interactively prove that for $f$, the commitment containing $z$ does contain the correct output for the inputs contained in the commitments to $x$ and $y$.

The Cramer-Damgaard paper shows how to do these proofs for a simple Turning-complete set of both boolean and arithmetic gates (for example, NAND and modular addition/multiplication).

The size of the circuit implementing SHA-1, expressed with only NAND gates for example, will be very large and infeasible. The art to doing the proof in practice is breaking it into subprotocols that are best represented by either boolean or arithmetic circuits and switching between the proof systems as appropriate. For certain SHA operations, he works at the bit level with boolean operations and for other operations, he works with integers in a finite field.


Why does KangarooTwelve only use 12 rounds?

I. Intuition: collision only on 6 rounds.

KangarooTwelve aims at fast hashing but also claims 128-bits security. This can be seen in the fact that the capacity is set to 256 allowing a rate of 1344 for a faster absorption.

Note that while the base sponge construction uses only the 12 finals rounds of Keccak, it is applied twice on each bit in the case of a message longer than 8129 bytes. You compute first the CVs values and then hash it with the first string (see bellow).

KangarooTwelve(M,C):  S_0 || S_1 || ... || S_n = M || C
  F = Sponge[Keccak-p[1600,nr=12],r=1344,c=256] (or mini Keccak)

                          +------------+
                          |    S_0     |
                          +------------+
                               ||
                          +----------+
                          |  `110*`  |
                          +----------+
                               ||
+-----------------+   F   +----------+
|     S_1  ||`110`|------>|   CV_0   |
+-----------------+       +----------+
                               ||
+-----------------+   F   +----------+
|     S_2  ||`110`|------>|   CV_1   |
+-----------------+       +----------+
                               ||
       ...                    ...
                               ||
+-----------------+   F   +----------+
|     S_n  ||`110`|------>|  CV_n-1  |
+-----------------+       +----------+
                               ||
                          +----------+
                          | r_e(n-1) |
                          +----------+
                               ||
                          +------------------+   F
                          |  0xFFFF  || `01` |------>  output
                          +------------------+

Other reasons that lead to consider K12 safe are the current absence of collisions for more than 6 rounds, implying a security margin of 100%. This same round-reduced approach is also used in Keyak and Ketje.

If you want to have more security, you can use Marsupilami 14, it is Kangaroo 12 but with the last 14 rounds of Keccak instead of 12 and a capacity of 512 bits.

II. The complexity arguments.

Joan pointed this to me: in this note, it is noted that the complexity of the zero-sum distinguisher are

for 18 rounds: $2^{1370}$
for 14 rounds: $2^{257}$
for 12 rounds: $2^{129}$

In the case of KangarooTwelve, the capacity is 256 bits. A generic attack on a sponge with such capacity leads to a complexity of $2^{128}$, thus the complexity of the zero-sum distinguisher for 12 rounds is higher, rendering the efficiency of this attack worse than bruteforce.

As for the 14 rounds of MarsupilamiFourteen and its capacity of 512 bits, the arguments is the same.

Also to generate the zero-sum structure, one need to start in the middle of the iterations. This attack surface is reduced by the way KangarooTweleve operates due to all the fixed constants.


if Ed25519 has gone through rigorous cryptanalysis

It is based on Curve25519 which has gone through extensive cryptanalysis. The Ed25519 signature scheme as well is being heavily reviewed and adoption is rapid. There are already a number of papers on the algorithm itself, as well as a few papers on specific implementations. Every part of the algorithm and design decisions are justified in the paper introducing it.

  if there are any possible backdoor in the algorithm?

The algorithm is based on simple* and easy to explain parameters. This is explained here, where various ECC curves are compared and contrasted. Compared to many other common curves, Curve25519 does not use any long, strange, inexplicable parameters like some other curves do. Ed25519, naturally, uses the same curve with the same explainable curve parameters: $y^2 = x^3 + 486662x^2 + x$, modulo $p = 2^{255} - 19$. These parameters are all justified in the relevant paper introducing the curve. Compare this with, say, the NIST curves which all have very strange, long, and unexplained parameters.

Additionally, the algorithm was designed by Daniel J. Bernstein, a cryptographer who is well-known for going to court and fighting against the government when it tried to weaken cryptography. It is not designed by a nameless cryptographer or pushed by a sketchy group.

* Simple if you're familiar with elliptic curve mathematics.


Given a secret - how does one generate a reproducible private key from it?

Yes, generating private keys from passphrases / passwords is possible.1

However, I strongly advise against basing your public key exclusively on your password and not proper (pseudo)randomness.

If you publish your public key, everybody will be able to brute-force your password which will allow for passive decryption (encryption keys), identity theft (signature keys) or impersonation (signature keys / password re-use).

So let's get into the technicalities.

What ever the methods say here. Always pre-process the password with the strongest password-based key deriviation function you can find (eg Argon2, you may have to turn the salt off for this).
If your preferred library has a plug-in architecture for the RNGs, you can just replace the RNG with a contruction which is deterministic in your password input. AES-CTR would be a good example here.
If not, your best bet is to restrict yourself to discrete-logarithm-based cryptography where the private key literally is just an integer, which you can get trivially from the transformed password. From there you use static group parameters and generate the public key on-the-fly as usual.

1: Bitmessage for example allows you to do that


Independently choose lanes and threads param on Argon2

There is nothing fundamentally wrong about using fewer threads. It does mean you may not be able to make use of all the memory bandwidth you have, resulting in memory being filled a bit more slowly, but it will not damage the memory-hardness of Argon2. This is not ideal for you as the defender because parallelism is not meant to increase the number of operations you can perform in any given timeslice, but to increase the memory fill rate. A single hardware thread on an x86 CPU even at its maximum clock rate cannot saturate the memory bus. It takes multiple cores to do that. In fact, because it's the fill rate that matters, using more than a few threads on most x86 hardware will actually not speed things up!

The attacker is bound not by the computation rate (in fact, the compression function in Argon2 is very simple), but by the total amount of memory required to calculate the hash. Forcing them to use more execution units would not increase the total cost of the attack nearly as much as a bit more memory.

Benchmarks of single-pass Argon2d using an Intel i7-4500U processor from the paper:

Threads  Cycles/byte  Bandwidth (GB/s)
1        1.3          2.5
2        0.9          3.8
4        0.6          5.4
8        0.6          5.4


Chance to find HMAC key/salt when having knowledge of the hashed data?

Assuming you mean a normal HMAC with a strong unknown key, no amount of MAC values for known, or even chosen messages would help you find the key. That would mean a failure of HMAC's forgery resistance, which is expected of MAC algorithms.

(It would be a very bad case of forgery attack, since it would allow forging MACs for any messages. Even much lesser attacks, like being able to forge a single valid MAC for another message, would be considered significant breaks.)


Difference between computational and statistical indistinguishabilities

Computationally indistinguishable typically means that your adversary is computationally bounded and that because of this they cannot distinguish between, for example, two messages.

For example, say you encrypt (with proper padding) the messages $0$ and $1$ using RSA and send them to the adversary. We would not want the adversary to be able to distinguish which encrypts the $0$ and which encrypts the $1$. If the adversary is not computationally bounded, however, they can break RSA via factoring, recover the private key, and decrypt each ciphertext to get the plaintext. Then they would be able to distinguish.

Statistical indistinguishability is when the adversary is not computationally bounded. They should still not be able to tell the difference between, for example, two ciphertexts. An example of this would be the one-time-pad. Encrypt a message of all 1's with one pad and a message of all 0's with a different pad. The adversary, no matter how powerful, can not distinguish between the two.


Sending KCV (key check value) with cipher text

I suspect that KCV's are in general not used because they don't add enough to be worth the small overhead.

There are a number of cryptographical attacks on encrypted methods that involve the attacker modifying a valid ciphertext, and then having the receiver decrypt the modified message (and watch how the receiver reacts).  Because of these attacks, it is generally wise to include an authentication tag along with the message; if the authentication tag does not check out, then the receiver rejects the message (and in a way that is independent of how the message was modified; this prevents the attacker from deducing any information).

There are a number of ways to authenticate the message; you can generate a MAC of the ciphertext, you can sign the plaintext, you can use a cipher mode of operation that encrypts and authenticates (e.g. GCM).  One thing which is not a valid method would be adding a KCV value (a valid KCV value means only that the KCV value was computed by someone who knew the keys; it doesn't say anything about whether the rest of the message was modified).  So, if you use a KCV, you still would need an authentication method as well.

Which brings up a question: if you're already including an authentication method, what extra does a KCV bring to the table?  Well, I can't see much.  If the sender made a mistake, the receiver would be able to catch it earlier; however, that's not something we typically care about optimizing for (one possible exception would be a password-keyed file encryption method; you might not want to have to decrypt a full multigigabyte file before noticing that the password was wrong).  You might hope to try to distinguish the cases where the sender uses the wrong keys versus he makes another type of error; I don't see how that would be useful in general (and note that an attacker would be able to simulate both types of errors depending on how he modifies the ciphertext; hence if one type of reaction is useful to him, he can induce that).

KCV's don't add much expense (another cipher block evaluation and a few more bytes of encryption overhead), but if they don't bring any benefit (and except for that one case I mentioned above about file encryption, I don't see how they do), it's hard to see why to pay that small additional expense at all.


How to find a small generator with small inverse? Does it have negative impact to security? (for Schnorr subgroup of $\mathbb{Z}/P\mathbb{Z}$)

Q3.) Would a small $g, g^{-1}$ have any impact to security?

It would not appear so.  It is easy to show that, if we had a generator $g$ that makes the Discrete Log (or the Computational Diffie-Hellman) problem easy, then the Discrete Log/CDH problem is easy with respect to any base $h$ that's within the same subgroup.

Suppose we had a way that, given $g, g^x$, gave us the value $x$.  Then, what we could do, given $h, h^y$ is first find the value $z$ such that $g^z = h$ (by solving the discrete log to the base $g$), and then the value $w$ such that $g^w = h^y$ (again, solving another discrete log to the base $g$); then, we have $h^{wz^{-1}} = h^y$; since we know $w$ and $z$, that tells us the discrete log.  Similar (but more complicated) logic allows us to solve the Computational Diffie-Hellman problem, given a CDH oracle with respect to base $g$.

However, this is not a complete answer to the question; it might be that the existence of a small $g, g^{-1}$ makes all discrete log/CDH problems easy.

I don't know of a way this can be disproven.  However:

None of the known discrete log methods have significant speed-ups when given a small $g, g^{-1}$ (by significant, I mean more than speeding the operation of multiplying by $g$)
For just about any prime, there will be tiny $g$ values that generate groups that contain the Schnorr group as a subgroup.  If there were a fast way to complete discrete logs with a tiny $g$ in this group, then you could use that to compute discrete logs in the Schnorr group (and although this argument doesn't take into account the tiny $g^{-1}$, there's no obvious way to use that).


Fortuna: why are source ID and data length added together with entropy data into the pools

You can't contaminate the pool with low entropy data. Hash functions "extract" up to the output size or the hash - slightly less, because of collisions.

The source number makes the output different for different sorces even if the input is the same.

The length is needed because else we could not differate two small inputs from one large input with special patterns. This depends on the usage of the hash function.


Is this streamable combination of encryption and MAC secure?

It looks like your protocol is secure for integrity purposes, i.e. the receiver will only accept a stream if it is the same as the one sent by the sender (assuming the MAC is not broken).

But if your possible attack scenarios contain a (partial) chosen plaintext attack, the use of CBC makes it weak against the BEAST-like attack against the confidentiality part, mentioned in the comment by CodeInChaos.

For CBC to be secure against chosen-plaintext attacks of the BEAST-style, it is important that each block's "effective initialization vector" (i.e. the previous block or the IV for the first block) is sent not earlier than the content of the block is fixed. If you send your stream in MAC-block pieces (i.e. $m_i || c_i$) and you send one such full piece before the (plaintext of) the first block of the next piece is known, an attacker which can both observe the ciphertext and chose this block of plaintext can use this to verify guesses about other parts of the ciphertext.

In your context of file encryption, quite likely the full file is already fixed when you start encrypting it, thus this attack is not possible. But make sure you document this limitation when creating your program. Alternatively, use other modes like CTR instead of CBC, which are not weak against chosen plaintext attacks.


G'day. LUKS stores multiple copies of the master key in what it terms key slots. Each key-slot contains an encrypted copy of the master key, and it can vary in its password-based KDF parameters (and even algorithms). The parameters and algorithms can sometimes be wildly different, giving rise to the circumstance where forcing one key-slot may be infeasible, while another is fundamentally weak. (Both will yield the master key.)
For LUKS1, the best option for the password-based KDF is PBKDF2. For LUKS2, an additional option exists to use Argon2, which gives you the potential to make it even harder to force a corresponding key-slot... but in all cases this will depend on the hardness parameters chosen, as well as the relative strength of the password. (In LUKS2 both options can exist in parallel.)
First, create a file to play with: fallocate -l 32M testing.encrypted.iso and xxd -c32 -l256 testing.encrypted.iso
Now turn it into a LUKS container, noting our two key-slots, both wildly different in terms of relative strength of the password-based KDF:
cryptsetup --type=luks2 --pbkdf=pbkdf2 --pbkdf-force-iterations=1000 --hash=sha384 --luks2-metadata-size=16k --luks2-keyslots-size=$((512*1024)) luksFormat testing.encrypted.iso
cryptsetup --type=luks2 --pbkdf=argon2id --pbkdf-memory=1048576 --pbkdf-parallel=4 --pbkdf-force-iterations=8 --key-slot=5 luksAddKey testing.encrypted.iso

(In fact, our Argon2 key-slot might be derived from pwd awesomedud, while our PBKDF2 one might be 'rp6eq25dgt2orn/mnf. d4r6tj'n2uhpsqsbv.b!)
xxd -c32 -l256 testing.encrypted.iso
cryptsetup luksDump testing.encrypted.iso
cryptsetup luksDump --key-slot=5 --key-file=- --dump-master-key testing.encrypted.iso

Now clean up: shred -z testing.encrypted.iso and rm testing.encrypted.iso.
MASTER KEY RECOVERY
Once the slot key is derived from the password, the alogorithm must then retrieve the encrypted master key from the key-slot area in the header. From https://gitlab.com/cryptsetup/cryptsetup/-/wikis/LUKS-standard/on-disk-format.pdf, figure 5, p11, Fruhwirth '18:

(Apologies for the screenshot, feel free to transcribe this text and replace...)
ANTI-FORENSIC SPLITTING
You may have noticed a function in the previous pseudo-code, AFmerge? My crude understanding is as follows: in the LUKS header, the individual bytes that make up each key-slot are interspersed (intermingled, interleaved) throughout the key-slot area of the header at a particular interval. Cumulatively, the key-slot area will contain n key slots, which are all interleaved. To recover the master key from any given key-slot, you need access to all of the blocks that contribute, otherwise the key won't be recovered.
The reason for this is to reduce the likelihood that any part of the key will be recovered after the user chooses to destroy the header. It is also the reason why you should consider more than one key-slot (ie. a high-entropy recovery key), but regardless, it's critical to keep a reliable backup(s) of the header (edit if you value the data within the container):
cryptsetup luksHeaderBackup --header-backup-file=testing.enciso.header testing.encrypted.iso

More detail on this here - https://clemens.endorphin.org/nmihde/nmihde-A4-ds.pdf, s5.2 p75+, Fruhwirth '05 - but fundamentally:

If the probability to destroy a certain block of data is 0 ≤ p ≤ 1, then the probability that the block survives is 1−p. Given a set of data consisting of n data items, the probability to erase the whole data set becomes worse since p^n becomes smaller as n becomes larger.

... the remaining task is to construct a data vector from an original data item and to make the destruction of a single vector part crucial for the survival of the whole information contained in the data vector.


Does this proof sketch show that finding a SHA-1 preimage is NP-hard?

they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard

No, they don't.  The definition of a problem being NP-hard is "if you have an Oracle that can solve instances of this problem in polynomial time, you can solve any problem in NP in polynomial time"; as we can quickly find SHA-1 preimages using a huge lookup table, we can easily see that finding SHA-1 preimages is not NP-hard (unless P=NP, in which case every problem is NP-hard)

What they do (at best) is show is a class of problems that are jointly NP-hard (of which finding SHA-1 preimages may be an instance).  However, that doesn't tell us anything about the concrete difficulty of SHA-1; NP-hard problems can have easy instances (trivial example: travelling salesman problem over every city in the world; is there a circuit that's at most 1 kilometer total distance?  Even though the traveling salesman problem is NP-hard, this is a trivially solved instance)


Diffie-Hellman should size of group be a prime?

This contradicts an answer

In what sense do they contradict?

The first one states that, for a safe prime, we have subgroups of size $q$ and $2q$.

The second one states that we typically use a $g$ that generates a subgroup whose size is a prime.

These two statements do not contradict each other; combined, that would mean that (to follow both) we select a $g$ that generates a subgroup of size $q$.  This is always possible (in fact, $g=4$ is always such a generator).

Your computations show that, for $p=83$, then $g=2$ is not such a generator.  What that means is that, to follow the advise of the second statement, you'd pick a different generator (and, in fact, $g=3$ works, that is, generates a subgroup of size $q$, for $p=83$)