RSA encryption with private key and decryption with a public key

Mathematically it work just fine. "Encrypt" with the private key, "decrypt" with the public key. Typically, however, we say sign with the private key and verify with the public key.

As stated in the comments, it isn't just a straight forward signing of the message $m$. Typically a hash function and padding is involved. Also, often one has a separate key pair for signing.

As you can see, there are a number of caveats, but in general you are correct, it is used for sender authentication.


Is iterative sha256 adequate for local password manager?

I will skip the usual don't roll your own speech.
For a local password manager you typically need encryption   not only password based key derivation.
You want to encrypt your various passwords with a key derived from your master password.
There are many methods for doing so, argon2 is one of the best. However iteratively applying a general purpose hash function is also acceptable. An example of how to use a general purpose hash function is: https://en.m.wikipedia.org/wiki/PBKDF2

Note it mixes the password again in it's iteration and xors the results these ensure the space of possible outcomes doesn't shrink with iteration count as it would with naive chaining. Also note the use of a Salt which prevents attacking multiple passwords together or use precomputed dictionaries/rainbow tables.

Argon2 is also memory hard and argon2i is also side channel resistant not sure these are a must.

With such a key derived from your master password you can encrypt the individual passwords with a symmetric cipher of your choice.

Note there are other things to watch out for when building your own password manager. For instance, be sure to ask lock the sensitive memory to never be swapped to disk. Or your master password and key may find themselves on disk  so that anyone can read them.


It's because how ASN.1 (DER, actually) encodes integers.

DER is not a crypto-specific format; it is a method originally designed to encode a large variety of information.  So, when they encode an integer, they provide the possibility of encoding a negative integer (even though that never comes up in crypto, it may be used in other usages).

They encode the integer as a big-endian byte string (where the first byte is the most significant one), and they use the convention that the msbit of the first byte indicates the sign of the encoded integer.

This raises an obvious question: what happens if the msbyte of the integer was, say, 0x80?  If you made that the first byte of the encoding, the decoder would see that this msbit was 1, and so would assume that the integer was negative.  To avoid this possibility, what DER mandates is that, in that case, you prepend a 0x00 byte in front.

This is what is happening; your private key is an integer that just happens to be between $2^{255}$ and $2^{256}$; because the msbit of that msbyte happens to be a 1, a 0x00 is prepended.  This will happen on about half of the private keys you'll generate.


Simplified Fiat-Shamir example generates wrong output

The problem is one of notation for modular arithmetic, at the point of the question reading

  if y^2 equals (x * v^e) % n then..

Likely the textbook is about

  if $y^2\equiv x\cdot v^e\pmod n$ then..

By definition of $a\equiv b\pmod n$, that holds if and only if $n$ divides $a-b$ (or equivalently: $|b-a|$ is a multiple of $n$). In the question, 437 divides 441-4, thus $y^2\equiv x\cdot v^e\pmod n$ holds.

Sometime, $a\equiv b\pmod n$ is written as $a=b\pmod n$, but rigorously the later means that $a$ is the set of solutions to the former. $a\equiv b\mod n$ or $a=b\mod n$ are also used, but the later is best avoided, because it is dangerously close to $a=b\bmod n$, to be read as $a=(b\bmod n)$ and thus rigorously meaning $0\le a<n$ and $|b-a|$ is a multiple of $n$. However, only a strict Vulcan would assume $0\le y^2<n$ when seeing $y^2=b\bmod n$.

Note: On this site, $y^2\equiv x\cdot v^e\pmod n$ can be written as $y^2\equiv x\cdot v^e\pmod n$. A right-click on a rendered formula then Show Math As TeX Commands will reveal the TEX code used. I often use this TEX cheat sheet.


Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

No it does not.

Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is only possible to derive the secret session keys of the session that you've retrieved the private key for.

Perfect forward secrecy - or forward secrecy for short - is obtained because the private key of all the parties of a connection regenerate the public/private key pair for each connection; authentication of the entities within the connection will be performed by other means (if at all). These key pairs are called ephemeral key pairs and the key agreement is called ephemeral-ephemeral key agreement or just ephemeral key agreement for short.

Perfect forward secrecy however doesn't make it impossible to break DH or ECDH. It just means that you would have to perform an attack for each separate connection as you'd have to attack each separate key pair of one of the parties to retrieve the secret value. It doesn't make DH or ECDH a perfect cipher, equivalent to an asymmetric one-time-pad.

So regardless of (perfect) forward secrecy, the only way to make a transport protocol secure (against analysis with a quantum computer) is to use quantum resistant cryptography - that is, post-quantum algorithms that cannot be analyzed using quantum computers.


What do the last chunks of the output string of Scrypt contain?

I should have started here:

sub scrypt_hash {
  my ($key, $salt, $N, $r, $p) = _scrypt_extra(@_);
  return undef unless defined $key && defined $salt && defined $N && defined $r && defined $p;
  return "SCRYPT:$N:$r:$p:" . MIME::Base64::encode($salt, "") . ":" . MIME::Base64::encode($key, "");
}

It explains that the last chunk is actually the base64 encoded key (hashed password). The second part (which I thought was the hashed password), is actually the base64 encoded salt.


If $c$ is a possible encryption for each $m \in M$, that means that for each message $m$ exists a key $k$ such that $Enc_k(m)=c$. Now, if you encrypt, you need to be able to decrypt. Since $c$ is fixed, the only variable for $Dec_k(c)=m$ is $k$. Since you need to be able to use the decryption process to get any value of $m$, that means that you have $|M|$ values of $k$.

In other words, you need to be able to go from the any value in the message space to any value in the ciphertext space (encrypt) and from any value in the ciphertext space to any value in the message space (decrypt), and for that you need $|M|=|C|$ keys.


What will be the MAC size of AES CBC-MAC if there are suppose 10 blocks in the AES CBC-MAC?

Yes, the CBC-MAC algorithm simply issues the last block of CBC mode as authentication tag. For AES this will always be 128 bit as that is the block size of AES (which is independent of the key size used).
The authentication tag is sometimes shortened to fewer bits (taken from the left hand side) for reasons of efficiency. This is however independent of the input size. $Tlen$, the size of the tag, is a security / configuration parameter of most MAC algorithms and authenticated modes of encryption such as CCM. $Tlen$ is commonly larger than 64 bits (smaller sizes will really influence security), a multiple of 8 bits (i.e. a certain number of bytes) and of course smaller than or equal to the output size of the algorithm that produces it.
Generally a protocol specifies the authentication tag size(s) that should be used. Generally the security in bits changes linearly with the authentication tag size for cipher based algorithms such as CBC-MAC. Other (more efficient) algorithms such as GMAC used in GCM however will degrade security faster (!).
Note that CBC-MAC is not AES CMAC, which should be used for dynamically sized messages.


Is this a proper key-exchange implementation?

Can exponent be random number just like it is now or it should be a prime too?

There is no particular advantage to be gained in selecting only prime exponents.

  Is using dynamic modulus and generator better idea?

Whether it makes sense to use dynamic modulii is currently under debate.  There are known algorithms that make attacking multiple discrete log problems under the same modulus not that much more expensive than attacking one; hence some people claim that you should vary the modulus (not to give TLAs a single target to attack).  Other people state that if you use a sufficiently large modulus (and 2048 bits would appear to be sufficiently large), this isn't a concern (and in addition, generating random modulii adds complexity, and that in itself is a security concern).

As for generators, we know the answer is "no, it doesn't help". It's provable that one particular base is not (much) weaker than a random based (of the same order); that is, if you can solve either the DLog or the computational Diffie-Hellman problem with one base, you can leverage that to solve the corresponding problem in any base (of the same order).  It's far more important to select a generator that you know has a large prime order (with possibly a small cofactor).

  Is there anything to improve this key exchange or are there any flaws?

Of course there are flaws.

You state that the modulus is "prime"; that's not sufficient for Diffie-Hellman; instead, you need to know the that it contains a subgroup that's a large prime factor (that is, $p-1$ has a large prime factor $q$).

You use the generator "3".  Small generators can be strong (in fact, "2" is a popular choice), however you should make sure that "3" has a large prime order (that is, it generates a subgroup whose size is a large prime).  One obvious way is to select a prime $p=2q + 1$ for prime $q$; and with $p \equiv 11 \pmod{12}$; if both requirements are true, then "3" will generate a group of size $q$.

You use a 2048 bit exponent; that's considerably more expensive than you need; you do the above checks (make sure that the subgroup that $g$ generates is large and prime), then a 256 bit exponent is quite sufficient (and 8 times faster).

You don't do any authentication; this means that someone in the middle that can modify messages can insert themselves into the conversation, and listen in.

You have the server perform the first modular exponentiation, and before any client verification; this opens up an obvious Denial-of-Service attack.

  Is using SHA256 a proper way to generate 256bit key for AES/CBC?

And how are you generating the key for the MAC (you are using a MAC with AES/CBC, aren't you???)


When you use a PRF to derive a key, there is the potential for collisions. If you derived a 128-bit key from each possible 128-bit number, you'd expect some of them to collide. Specifically, you'd expect only about 63%  of all the inputs ($1-e^{-1}$) to appear as outputs.

That means you lose less than a bit of entropy even if the original key had the full 128 bits of entropy, like your random 128-bit string. With a lower entropy key you'd lose less. That doesn't matter in practice, since in the worst case it wouldn't even halve attack time. 127-bit security is enough.

In general, if you use a PRF to derive an $n$-bit key from one with $k$ bits of entropy, the resulting key will have at least $\min(n, k) - 1$ bits of entropy, approaching $\min(n, k)$ when $k \ll n$ or $k \gg n$.


Determining Involutary Keys in Substitution Ciphers

If $E(x) = ax+b \bmod n$, and $E(E(x)) = x$, then you need $a(ax+b)+b = x$, or $a^2x + ab + b = x$.  So any (a, b) where $a^2 = 1$ and $b(a+1) = 0$ will do it.  There are always solutions $(1, 0)$ (which corresponds to not encrypting) and $(-1, b)$.  Depending on the value of $n$ there may be other solutions for $a$.  There are only those two for $n = 26$, but there are a total of 4 solutions for $n = 36$.


Is there any weak message for an ECDSA signature?

[Partial answer] In  Generic Groups, Collision Resistance, and ECDSA by D. Brown (see http://cacr.uwaterloo.ca/techreports/2002/corr2002-06.ps or http://eprint.iacr.org/2002/026) on page 17, you have a lot of information about the kind of hash functions that can be used with ECDSA. In your case, taking the identity function as hash and looking at the results you find that two of the proposed weaknesses are particularly relevant to your case:

$z=0$ is a weak value (see Zero-Finder-Resistant Hash)
If the probability that a random number modulo the curve order belongs to your acceptable range of $z$ values is not too low, there also is an attack (see One-Way Hash Function). With 10 bytes long values as suggested, the probability is sufficiently low and you can probably ignore this attack.


The AES key schedule isn't more secure than using PBKDF2 on the data -- but it is a lot faster, and requires many fewer gates in silicon.  Performance is important.

As far as devising your own variant of AES, with more rounds: don't do that.  There's no good reason to do that (it is exceptionally unlikely that AES is the weakest link in your system), and you can easily introduce subtle security vulnerabilities.  Whatever problem you have that you think motivates this, modifying AES isn't the solution.


Your confusion comes from learning the algorithm from it's implementation side and not from it's mathematical principles. First take a look on this wiki page. On the bottom you see the equations for MixColumns stage of the algorithm:

$$d_0=2b_0 + 3b_1+1b_2+1b_3\\d_1=1b_0 + 2b_1+3b_2+1b_3\\d_2=1b_0 + 1b_1+2b_2+3b_3\\d_3=3b_0 + 1b_1+1b_2+2b_3$$

Looks simple, but it's not. We are in Galois finite field so the "addition"
and "subtraction" are actually the same operation known as XOR and multiplication is very complicated and hard to reverse. Your question is actually about one of the "shortcuts" that can be done when implementing the Galois finite field multiplication. (Take a look at C# example here)

We can split the Galois multiplication into two steps.

First we take two values written in binary
$$0x53 \cdot 0xCA = 01010011b \cdot 11001010b$$
and we multiply them the same way as we would multiply two polynomials, keeping in mind that addition here is a XOR operation.
$$ (x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)\\=\\x^{13} + x^{12} + x^{11} + x^{10} + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$
and we convert it back to binary
$$11111101111110b$$

Then we take the result of the previous step and run it through a particular modulo operation. For Galois field we run modulo $x^8 + x^4 + x^3 + x + 1$ which can be written in binary form as $100011011b$ and in hexadecimal as $0x11B$

Smart heads thought about it and they actually found a way of doing both operations at the same time since modulo is pretty much a looped subtraction (in Galois field subtraction is the same XOR operation as addition)

That's why after applying that "shortcut" first we test if the most significant bit is equal to 1 (which is also called by some programmers that "the bit is set") and then we subtract (XOR) that $0x11B$. The value $0x11B$ is using 9 bits ($100011011b$) and when applying this shortcut we have just 8 bits available so we actually subtract (XOR) $0x1B$ ($00011011b$) When the most significant bit is equal to 0 (it's not set) the value is lower than $x^8 + x^4 + x^3 + x + 1$ and there is no need for subtraction (XOR).


Do I need to implement multi precision arithmetic operations?

Whatever the curve, it's needed to use multi-precision integer arithmetic in ECC cryptography, at least for a few modular operations modulo the Ellitic Curve group order, since that's large (192-bit is the bare modern minimum). For the field, where the most compute-intensive operations are, there are alternatives with fields other than prime order groups. See for example Thomas Pornin's Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions (note: in this work, extensions applies to field, not microcontrollers).
For curves on prime-order field (as in the question), it's indispensable to have multi-precision integer arithmetic for field operations, and the performance of modular operations is central to the overall performance. Special attention to side channels, including timing, must be taken when manipulating confidential information (when signing and decrypting, and to some degree when encrypting; that's usually not a concern for signature verification).
For prime field using special NIST primes (as in the question), speed optimizations are possible. That's the reason to use such primes. All correct generic multi-precision integer arithmetic techniques and libraries (including GMP) work with these primes, but in general do not take advantage of the special form for speedup. Such techniques and libraries are thus adequate to get correct results, but not to get the best possible performance. More often that not, they also do not give adequate protection against side-channel leakage. Only some functions of GMP are written with this in mind.


Santanu Sarkar and Subhamoy Maitra show in Some Applications of Lattice Based Root Finding Techniques the deterministic polynomial time equivalence between factoring $N$ ($N=p\cdot q$, where $p>q$ or $p,q$ are of same bit size) and knowledge of $q^{−1} \bmod p$ (cited from the abstract).


Why every access structure is a multipartite access structure?

From p5 of the paper:

  An $r$-partition $\Omega = \{P_1,\ldots,P_r\}$ of a set $P$ is a
  disjoint family of non-empty subsets of $P$ with $P=P_1 \cup \ldots
 \cup P_r$. ... A family of subsets $\Lambda \subseteq \mathcal{P}(P)$
  is said to be $\Omega$-partite if $\sigma(\Lambda)=\Lambda$ for every
  permutation $\sigma$ such that $\sigma(P_i) = P_i$ for every $P_i \in
 \Omega$.

Thus any access structure $\Lambda$ on $n$ parties is trivially an $n$-partite access structure: take the $n$-partition $\Omega = \{\{1\},\ldots,\{n\}\}$; then for any $\sigma$ fixing all sets in the partition (which is only the identity permutation), it holds that $\sigma(\Lambda) = \Lambda$.  Since $\Omega$ contains $n$ partitioning sets, $\Lambda$ is an $n$-partite access structure.

The abstract also says that Shamir's scheme is unipartite.  This is by taking the partition $\Omega = \{\{1,\ldots,n\}\}$, which is a $1$-partition, since for every permutation fixing all sets in the partition (which is every permutation) it holds that $\sigma(\Lambda) = \Lambda$.  This is because of the symmetry in Shamir's scheme: every party can be swapped with any other party and you still have "all subsets of $\{1,\ldots,n\}$ of size at most $t$".


From the original paper[1]:

  DHIES is a Diffie-Hellman based scheme that combines a symmetric encryption method, a message authentication code, and a hash function, in addition to number-theoretic operations, in a way which is intended to provide security against chosen ciphertext attacks.

So the MAC is in this case already part of the scheme. If implemented correctly encryption should result in an ephemeral public key, a ciphertext, and a MAC / tag for the ciphertext being generated. So there's no need to generate another MAC.

[1] The distinction between DHIES and ECIES is simply the type of group being used for the underlying algebra, it isn't important in this context, much like the distinction between DH and ECDH


Indistinguishable encryptions in the presence of an eavesdropper equivalence

I've found an answer to my question, I'm going to post it because it can be useful to someone out there.

The point is that, if we assume that $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=1]\leq 1/2+negl(n)$, then $\mbox{Prob}[\mbox{Priv}_{\mathcal{A},\Pi}^{\mbox{eav}}(n)=0]\leq 1/2+negl(n)$ too (if this were not to happen, then we could create an adversary that solves the experiment with a better probability than $1/2+negl(n)$).

This allows us to use the same argument I've used for proving the first inequality for getting the inequality with absolute value.


Should I salt an AES password at each encryption?

No, it should not be necessary to derive a unique key for each message, although it certainly shouldn't do any harm, either.  CBC mode is provably secure (in the IND-CPA sense, or even IND-CCA2 if combined with a MAC) even if the same key is used for multiple messages, as long as the underlying block cipher is secure (a PRP) and the IVs are distinct and unpredictable.

One potential problem with using a deliberately slow KDF like PBKDF2 to derive a new key for each message is that this needlessly consumes resources, and thus reduces the legitimate user's performance advantage over an attacker (who only needs to run PBKDF2 once to test each password).  Even if one wanted to have a unique key for each message, it would be better to first derive a single intermediate key from the password with PBKDF2, and then use a faster KDF (like HKDF, or even PBKDF2 with an iteration count of 1) to derive the per-message keys from the intermediate key.  Of course, this is less of a concern if messages are typically long and few rather than short and many.


Why should $a,b < N$ for Montgomery Reduction?

Looks like misunderstanding to me: you are asking about Montgomery reduction but your example is about Montgomery multiplication.

Montgomery reduction inputs a number in range $[0..NR-1]$ and outputs a number in range $[0..N-1]$, where $R$ - auxiliary Montgomery modulus.

Montgomery multiplication inputs two numbers $A$ and $B$ in range $[0..N-1]$ and outputs a number in range $[0..N-1]$

Internally, Montgomery multiplication is standard integer multiplication followed by Montgomery reduction; so, formally it is possible to apply Montgomery multiplication to any numbers $A \ge 0$ and $B \ge 0$ such that $AB \le NR-1$. Since $R \gt N$, this is weaker requirement than $0 \le A \le N-1$ and $0 \le B \le N-1$, but I doubt this possibility makes practical sense.


Encrypting (CBC) identical files with same key and different IV, is it less secure?

You don't need to worry. There is no known weakness in CBC mode or AES which would mean that encrypting identical files (with different initialization vectors) makes it easier to retrieve the key, or decrypt the data.

The different initialization vector for CBC makes it sure that even the same file results in different input to the block cipher, and thus different output, so an attacker doesn't even know that these two ciphertexts are the same file (other than for the file size).

To crack AES, now the best known method is to try different keys and encrypt or decrypt one block with each, and compare the output with either captured ciphertext or known (or "guessed") plaintext (where we take the IV or previous block into account), until one matches. (For keys bigger than 128 bit, we might need to check with a second block.) If we don't know anything about the plaintext (which is quite rare, but might occur when encrypting a key), this doesn't work - and here our "twice the same file" can help:

decrypt the same block of both files
XOR each with the previous block each (or the IV in case of the first block)
compare.

This needs about twice the work as an ordinary known-plaintext attack, though, which is already out of any realistic ability to crack, if the key space isn't somehow reduced, i.e. if the key is generated from a password.

Note that there is a "weakness" in CBC which says that the total number of blocks to be encrypted with each key should be limited to about $2^{n/2}$, where $n$ is the block size in bits, to make the probability of repeated outputs (and thus repeated XOR-masks for the next block) neglectible. This doesn't really depend on encrypting the same or different files, though, and for 128-bit blocks, this number is quite high ($2^{68}$ bytes, around 200 exabytes, which is half of the world's total digital content (of 2009)).


Is it possible to find the key of an HMAC-SHA-512 given the input and the hash output?

HMAC

$\operatorname{HMAC}$, in extended form keyed-hash message authentication code or hash-based message authentication code, is a MAC that includes a cryptographic hash function and a secret key.

With these properties, it can be used for data integrity and authentication.

With the used hash function $H$, $\operatorname{HMAC}$ defined as;

\begin{align}
  \operatorname{HMAC}(K, m) &= \operatorname{H}\Bigl(\bigl(K' \oplus opad\bigr) \parallel
\operatorname{H} \bigl(\left(K' \oplus ipad\right) \parallel m\bigr)\Bigr) \\
                         K' &= \begin{cases}
                                 \operatorname{H}\left(K\right) & K\text{ is larger than block size} \\
                                 K                              & \text{otherwise}
                                \end{cases}
\end{align}

HMAC is usually written as HM$\operatorname{HMAC-X}$ where the $\operatorname{X}$ represents the used hash function and in your case it is $\operatorname{HMAC-SHA512}$

Security;

Security of $\operatorname{HMAC}$ depends on the deployed key size and hash output. The most common attack is a brute force attack. In your case, the attacker will try all possible keys to match the input and the output. If your key size is above 128 you will be fine for single target attacks. If possible prefer larger key sizes like the 256-bit key size. With SHA-512 one can use key sizes up to 1024 since the limit is determined by the block size of the used hash function.

As proven by Bellare 2006 that if the compression is PRF than HMAC-SHA512 is a PRF. As a result, HMAC doesn't suffer the weakness found in MD5 - the MD5 collision attack.

php hash_hmac supports various hash algorithms, the current list contains 43.

Note 1: HMAC-SHA512 uses the underlying hash function two times to countermeasure against length extension attacks. For the SHA-3 series, there is KMAC that uses SHA-3 directly and SHA-3 has resistance to length extension attacks by design.

Note 2: As of today (21/05/2020), I didn't see a PHP implementation of KMAC.


Is standardizing a modified AES a good idea?

The most likely rationale to change the AES design is political. It's a NIST standard, designed in Western Europe.

It's a bad idea! How much scrutiny has it received? Almost none. How much will it receive? Almost none. Bad idea.


What is the most secure key expansion routine?

There are many possibilities here, depending on the particulars of where exactly you will use it.

Your use case may require a random looking derived key, where the 1024 bytes of entropy have been distributed evenly over all the bytes of the final key. In that case there's no avoiding a key derivation function. You will have to use either a block cipher, a hash function, or something equally complex.
Your use of it in a stream cipher may not care at all, if the entropy will be subsequently diffused over the state anyway (maybe with extra initial rounds). In that case you may as well just set the rest of the bytes to zero, or perhaps concatenate four copies of the original key to increase the speed of initial diffusion.
The second point above may be true, but your cipher may have internal symmetries that could make certain bits or bytes "cancel out". In that case you may have to make sure the initial configuration does not lead to weaknesses due to that symmetry.
You may have some sort of security proof or reduction for the structure of the cipher, like a Feistel network has, for example. That could put requirements on the key, e.g. that certain parts have to differ. HMAC is an example where simply padding the key with two different bit patterns was sufficient for proofs.

In the end, the main guidance I would give out is to look at what other stream ciphers are doing. The eSTREAM winners would be a decent starting place.


Symmetric Encryption, meet in the middle attack, effective key length

I believe I have settled it, please comment below if I have inaccuracies or am missing something:
c=Ek5(Ek4(Ek3(Ek2(Ek1(m))))
We can also represent these as the following: (by applying the appropriate decryptions to either side)
Dk4(Dk5(c)) = Ek3(Ek2(Ek1(m))) _____ OR ______  Dk3(Dk4(Dk5(c)))=Ek2(Ek1(m))
Effective key length: with the mitm attacker, it would take 2^192 operations on one side of the equation to find the "collisions" in the stored lists and determine a set of proper keys by brute force, and 2^128 operations on the other side.
Stated more abstractly, approximately ~|K|^3 + ~|K|^2, but in big O notation O(|K|^3)


Detect MITM with hashed session-key — Is my protocol secure?

If I am able to compare that the session keys and they are the same, can I assume that the connection is secure (no MITM present)?

Yes, baring attack on the extremities. That's a property of the Diffie-Hellman key exchange.

However, it is not satisfactory that the client sends (as envisioned) $\text{ENC}_\text{PK}(\text{Hash}(\text{Sym.Session Key})\mathbin\|\text{Hash}(\text{Password}))$ (without using further encryption with the session key) in order to check that the two ends share the same session key. The security depends on details of the public key encryption used. For example, in some forms of RSA encryption, we would have what's sent equal to $\text{ENC}_\text{PK}(\text{Hash}(\text{Sym.Session Key}))\mathbin\|\text{ENC}_\text{PK}(\text{Hash}(\text{Password}))$, the right term could be extracted by mere passive eavesdropping, then allowing that attacker to authenticate w.r.t. the server.

Also, there's the issue that libhydrogen does not seem to offer public key encryption (at least glancing at the table of content).

The simplest working solution is to send $\text{Hash}(\text{Password})$ within the secret-key authenticated encryption channel, as the first payload, and have the server decipher and check that against the correct value.

A convincing security argument (not proof) that the above is enough for security is that

In a MitM attack modifying what's exchanged before the packet carrying the above payload, an attacker can't impersonate the server w.r.t. the client. The client will abort before anything related to $\text{Hash}(\text{Password})$ is sent.
In an attack (passive or active) starting after that, the attacker has no knowledge of the session key, and that key won't be reused in another session. Hence whatever the adversary intercepts that depends on $\text{Hash}(\text{Password})$ does not leak information about that; and (independently) is of no use in later sessions.
The use of correct authenticated encryption should take care of ensuring that whatever the adversary intercepts that depends on $\text{Hash}(\text{Password})$ is of no use in the current session (in particular, it is necessary that individually authenticated packets can't be replayed; if they could, replay of the packet with $\text{Hash}(\text{Password})$ in the right context could leak information about its plaintext).

However, the above simplest working solution is a tad brittle: if the server's private key leaks, an attacker impersonating the server w.r.t. a client can obtain the hash of the password (which is as good as the password for authentication purposes). And if a session keys leaks, passive eavesdropping allows the same.

Rather (and following the reasoning in the first part), we could send some MAC with key $\text{Hash}(\text{Password})$ and message $\text{Sym.Session Key}$, which the server can check. HMAC-SHA-256 would be suitable. There's an important incentive to further send that MAC thru the secret-key authenticated encryption channel: it prevents an adversary from checking a guess of the password unless s/he has the server's private key.

Note: If password is to be short enough to be conveniently keyed-in, or otherwise low-entropy, then $\text{Hash}(\text{Password})$ should still preferably be with a slow hash intended for passwords.

Note: No matter what, the password should have enough entropy to resist online password guesses, where an adversary attempts to authenticate w.r.t. the server using a dictionary of passwords. Limitation of the number of invalid attempts on the server (perhaps by a mere delay) can help with this.


Without a proof of security or proper cryptanalysis including an argument why it covers all currently known methods:
The value (in the context of cryptography) is zero.
This might sound harsh, but you brought up the main reason yourself: It is basically impossible to design a new secure cryptosystem without the proper knowledge of the field, but amateurs are convinced otherwise and keep on trying. The only solution here is to write a publication in some peer-reviewed context (e.g. crypto conferences). Regarding your experience, it is not clear from your question, because you wrote:

My problem is that 100% of my experience has been academic
Or 2. I sound like I have no idea what I am talking about. The second one is definitely true

Regarding your algorithm:
A lagged Fibonacci generator is a well known construction. It is an improvement over the linear congruential generator, and is related to similar concepts like LFSR, Mersenne Twister, etc.. But that doesn't say much: Those are not cryptographically secure random number generators, and they have no security at all (from today's point of view). So it's quite reasonable, this is also true for your algorithm.
Considering an infinite period: A large period is required for a proper CSPRNG, but it is not sufficient. A well-known counter example is linear-feedback shift registers, which have large periods and were used for stream ciphers in the past. But they are quite easy to break.
Also irrational numbers might offer an infinite period of numbers, but that doesn't mean they are unpredictable or you can't get the seed back from the sequence. I am not aware of any computationally hard problem regarding irrational numbers.


Why is CBC based on AES malleable in blocks other than the first block?

Depending on how malleability is defined, the question actually has some merit.

Given to the Wikipedia definition of malleability, a cipher is malleable if there exists at least one function $g$ over the set of possible cipher texts, and one function $f$ over the set of possible plain texts, such that given any cipher text $c_0$, the cipher text $c_1 = g(c_0)$ will decrypt to $D_k(c_1) = f(D_k(c_0))$ regardless of which key $k$ is used for the decryption.

Given that a function by definition assigns a unique value to each argument, there only exists such a function $f$ for CBC mode that might be known in advance to the attacker and might be determined from $g$ alone, if the corresponding function $g$ only modifies the IV. If the function $g$ modifies any other block, then $f$ will either be a relation (i.e. assign a set of possible values to each argument, rather than a unique value), or it will be a function that depends also on the key $k$.

Still, non-malleability might be defined in such way that the function $f$ only has to exist, without necessarily being known to the attacker in advance. If non-malleability is defined in such way, it is not necessarily a problem that this might imply that $f$ depends also on the unknown key and not just on $g$ and the plain text.


It is not that RSA becomes insecure when used with public exponent $2$. (In fact, the Rabin Cryptosystem does exactly that.) It's that it doesn't  actually work.

The problem is that for $N = pq$ for two primes $p$ and $q$, the function $f : x \mapsto x^2 \bmod N$ is not injective. So it is impossible to invert uniquely. In fact, most elements of the function's range (the set of perfect squares) have $4$ preimages under $f$. (As pointed out by Thomas Pornin, the multiples of $p$ and $q$ have $2$, while $0$ has only one.)

We can get around this problem by choosing $p\equiv q\equiv 3 \bmod 4$ and restricting the domain to the set of quadratic residues. In this case, the function is a trapdoor permutation over the set of quadratic residues if factoring is hard.

One might note, that this is actually a better guarantee than the one we have for the RSA trapdoor permutation, where the security is not known to be implied by the hardness of factoring.


How to protect from Silver–Pohlig–Hellman algorithm

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently.

However, the solution is pretty simple: Choose a safe prime as modulus: $p=2q+1$ (with $q$ prime), or a prime $p$ where $p-1$ contains at least one large factor, so that the BS-GS algorithm for this factor is too large (It has $\mathcal{O}(\sqrt{q})$  memory and time complexity for prime $q$).

For example this is done in DSA: Choose prime $q$ first, then calculate a prime $p$, where $p-1$ is a multiple of $q$. Examples for suggested key lengths $(|q|,|p|)$: (160,1024), (224,2048), (256,2048),...

edit:

To answer your first question: If you choose $p$ randomly, chances are high that your security is MUCH lower than you would expect:

For random $p$ , the chance of $p-1$ being divisible by a low prime $a$ is $\frac{1}{a-1}$. A random $p$ means that $(p-1)$ mod $a$ is uniform distributed in $[0,a-2]$.

Now, if $a$ is small, we can ignore the costs of the BS-GS algorithm for $a$, and you "loose" $\log_2{a}$ bits of security: The remaining problem doesn't have to be solved for group order $(p-1)$ but for $(p-1)/a$.

Since there are quite a lot of small prime numbers, you have a problem. Best to avoid this problem by choosing $p$ not totally random, but with $q$ large enough. (Choose q, calculate some $p$ and test them for primality).


Assuming that $b = 2^k-1$ for some positive integer $k$, XORing two (or more) numbers in the range $[0,b]$ will indeed yield a number in the same range.

If the numbers are random, uniformly distributed over the range and independent, then the result will also be random and uniformly distributed.  In fact, we can even prove a stronger result saying that if even one of the numbers is random and uniformly distributed over the whole range, and independent of the others, then the result will be random and uniformly distributed.

(There are a variety of ways to prove this.  Probably the most straightforward way is to observe that the map $x \mapsto x \oplus c$ is a bijection over the range $[0,b]$ regardless of the value of the constant $c$.  Thus, if $x$ is uniformly distributed over the range, then so is $x \oplus c$; and since this is true for any constant $c$, it's also true even if $c$ itself is a random variable, as long as it doesn't depend on $x$.  For the specific case of XOR, you can also first show the same result for each bit of the number, i.e. reduce the problem only to the case $b=1$, and then generalize to multiple bits.)

Effectively the same result also holds, basically by definition, even if the numbers are only pseudorandom, i.e. computationally indistinguishable from true random numbers.  That's because, if the result of XORing them was not indistinguishable from a truly random number, then this would provide an efficient way to distinguish the original numbers from truly random ones, thus showing that they weren't really pseudorandom in the first place.

Note, however, the the assumption of independence (or indistinguishability from independent random numbers) is important.  Otherwise, there are trivial counterexamples, like picking a truly random number $x$ uniformly from $[0,b]$, and then letting $y = x$.  Thus, both $x$ and $y$ on their own are truly random and uniformly distributed, but $x \oplus y = x \oplus x = 0$.


Why is SHA256/SHA512 not broken for shortish passwords

SHA-256 and SHA-512 were designed to be very fast. Their primary goal ist to verify the integrity of long messages or files. Long means not 10-12 bytes but some megabytes and greater. It is not a good idea, to use hash function that is fast by design for password hashing. Instead, for password hashing should be used functions that need essentially more resources for brute-forcing, e.g. that require relatively much RAM, prevent or limit essentially parallelization and thus limit optimization of brute-forcing. For instance, Argon2, Lyra2, scrypt.
Compare it to cars. Ferrari is good for the cases when the speed is important. It is not correct to say that Ferrari is weak because it cannot carry big load. If you need to move a big load, you better use huge trucks. It is just a matter of choosing a proper tool for the task.


By the definition given there, in a modular protocol design,

  each method or scheme used in the protocol (such as the use of nonces
  or the application of a cryptographic schemes) has a clear goal which
  it is proven to achieve, and sub-protocols can be replaced without
  re-proving the security of the remaining protocol steps.

That's also the meaning used there.

The word modular is used with the meaning it has for an engineer: the ideal of building trustable complex systems from smaller trusted and well understood components, in a way such that a component can be replaced with any other having the required, stated properties. That is actually seldom done in real complex systems.

I pass as to if and why TLS, IPSec, SSH... follow, or try to follow, the modular protocol design principle, or not.


About the Algebraic Normal Form (ANF) of S-Box in DES

Prior to answering this question, I present a preface about ways of demonstrating a "boolean function". There are two broad ways of representing namely "Boolean form" and "polynomial form".
In the boolean form representation, the boolean function is shown in one of the ways of Truth table, d.n.f, or c.n.f. On the other side, the polynomial form representation of a boolean function can be represented in the ANF (Algebraic Normal Form) or WHT(Walsh Hadamard Transformation).
For highlighting the importance of this classification, we can mention that each way exhibits and extracts unique properties of a boolean function. But why this boolean function and its properties are important? Almost all the cryptographic transformations as SBoxes, PBoxes, and even round functions are a kind of boolean functions. Moreover, the majority of cryptographic elements can be described with them, and cryptanalysis methods take advantage of the properties of these boolean functions to reveal their weaknesses, as an example, we can mention the correlation property between inputs and outputs of an SBox.
Turning to ANF, ANF  representation of a boolean function can be defined as:

This means: boolean function f consists of n variables which these variables can either 1 or 0 and the result of this function, as well, can be either 0 or 1. With respect to this definition,  a boolean function consisting of 3 variables in ANF form could be:
              f(x1,x2,x3) = x1x2 + x2x1 + x1x3

which we can easily sketch in our well-known learned schematic diagrams in high school as follows:

In this scheme, the domain consists of three different variables namely, x1, x2, and x3 which any can either 0 or 1 in the function f representation.
But how this ANF rule is defined?
As I told ANF or the other name of "positive polarity reed muller", is a way of showing a boolean function in a polynomial form with xor operator. Actually, this representation is with the presence of all linear combination of monomials. A simple way of clarifying this definition is as follows:

In this representation, each "a" variable can be either 1 or 0. For instance, the global form of a 2 variable boolean function can be defined as:

For example, we can show AND function in the ANF form as follows:

Here a0, a1 and a2 are 0 and a3 is 1.
Before we want to answer the question of why this form of representation is important, we should remark that the part in this representation form that is crucial for cryptographers are coefficients of the terms. As mentioned above example in the AND function ANF representation, the three coefficients a0, a1, and a2 are 0sand the only x1x2 term coefficient is 1.
Returning for explaining the importance of this representation, showing a boolean function with n number variables needs n different number minterms, however, in ANF form, this could be shown with fewer terms and also these few terms give a complete description of that boolean function.
The most important application of ANF form is describing SBoxes with a minimum number of logic elements. The result of this representation indicates the important SBoxes properties such as algebraic order, algebraic weight, linear and affine, completeness, and many others which are widely used in cipher designing and cryptanalysis.


How is PBKDF2 so much better than normal Hashing or even using HMAC

The point is not to make the attack infeasible time-wise. Computational resources (usually, area*time, which is roughly a measure of the monetary cost) needed for the attack is the only thing you can hope to increase here.

As you observed, it is always possible to parallelize brute-force search of passwords, so the best you can do is increase the computational effort it takes to check a single password. Sure, even if checking one password required 10 seconds, the attacker could always put millions of ASICs in parallel and bruteforce everything in 10 seconds. To put it differently: the adversary can always get the password using little time, but this requires a lot of area (i.e., number of parallel computing units used simultaneously). Essentially, the adversary is forced to always invest a large quantity of area $\times$ time.

The point is that doing so will cost a lot of money to the adversary: it is usually considered that area $\times$ time is a decent (rough) approximation of monetary cost of the attack. So the hope is to make this attack less interesting money-wise.

A further note: the quantity area $\times$ time does in fact not perfectly measure monetary cost, as experiments with modern ASICs have shown. However, a lot of research has been devoted to find much better measures that map more closely to monetary cost (e.g. 1, 2). There are a bunch of satisfying candidates, and several constructions of hash functions which provably maximize this measure for the adversary. PBKDF2 does not seem to be the best one out there - but it is an old, well-established alternative which, experimentally, does not perform too bad with respect to the monetary cost it incurs to the adversary.


How many bits of hash are realistically needed for key verification?

I recommend stopping after 20 hex digits, i.e., 80 bits.  That should be enough for security.  Suppose you connect to no more than 128 different servers with self-signed certificates, for which you will use this verification procedure.  Then it would take an adversary $2^{80}/128 \approx 2^{73}$ steps of computation to fool you, which is beyond what is feasible given the current state of technology.

I would not recommend 40 hex digits, i.e., 160 bits.  That offers needlessly poor usability.  If there's one thing we've learned about usable security, it is this: If it's not usable, it won't be secure either.  That's because people will find excuses to avoid the security advice, or to completely evade your security mechanism, or skip the verification step.  Or, they'll be tempted to communicate in the clear and skip the crypto and they'll make up rationalizations for it ("oh, this conversation isn't very secret", "oh, just this once", "what are the odds someone is listening in?", "I'll use coded references and it'll probably be OK"), and historically speaking, that tends to turn out badly.

As @CodesInChaos correctly states, collision attacks are not an issue here, so you don't need to double the number of bits you check.  Therefore, there is no need to check 160 bits.  Instead, as @CodesInChaos explains, this is a multi-target pre-image problem.  In general, if you want to force the attacker to perform $2^b$ steps of operation, and if you connect to $n$ different servers that use self-signed certificates that you verify in this way, then you should verify $b + \lg n$ bits of the hash.  I would suggest using a value of $b$ somewhere in the range 64..80; $b=80$ should be more than sufficient (a conservative choice), and $b=64$ is probably adequate.

I checked my SSH ~/.ssh/known_hosts file, which records all of the SSH hosts I've connected to in the past decade or so.  I found about 117 different hostnames, corresponding to $n=79$ different public keys (sometimes one host has two slightly different hostnames).  So taking $n=128$ seems like a pretty reasonable, conservative choice.

Note that you're not going to get perfect security through this mechanism.  All you need to do is make the MITM attack expensive.  In real life, rather than spending millions of dollars to find a matching public key through some expensive computation, it is more likely that the bad guy will attack some other weaker point in your system (e.g., exploit a zero-day in your software or in the server's software; bribe or impersonate the owner of the server; etc.).  Therefore, realistically, 18 hex digits (72 bits; i.e., 65 bits of security, assuming you connect to no more than 128 such servers) is probably enough to ensure that the crypto is not the weakest link in the system, if you want to cut it fine.  But 20 hex digits gives you a little bit of a margin for error.

If you want to optimize this to the max, you could use a slow hash function (e.g., bcrypt, PBKDF2), which might slightly reduce the number of digits you need to verify.  For instance, if you use 4096 iterations of hashing, you can probably reduce the number of hash digits to check by 3 hex digits (since $4096=2^{12}$, and 12 bits = 3 hex digits).  Also, if your hashing procedure hashed both the public key and the domain name (rather than just the public key), you could eliminate the opportunity for multi-target attacks, reducing the number of bits you need to verify from $b+\lg n$ to $b$ bits (e.g., reducing the number of bits to verify by about 7 bits, or about 2 hex digits).  You could also look at Paŭlo Ebermann♦'s suggestions for how to encode the hash in a way that makes it easier to compare hashes.  For instance, a sequence of words may be easier to verify than a sequence of hex digits, particularly if the dictionary is chosen appropriately.


Does HMAC provide anything that AEAD does not?

If I need to support AEAD sometimes, is it reasonable to just use AEAD all the time and skip HMAC entirely?

Yes, and if you only  need integrity / authenticity of the message then you can put all of the message in the Associated Data.

  HMAC should be faster, but how much? I’ll need to test this, but suspect the difference might not be huge.

It won't be faster than GMAC generally, but if you include the CTR mode encryption  then you may see a difference. This is too dependent on the system config to be able to answer this reasonably.

Some settings or openssl speed may help you with this. In my case AES-GCM was even faster than HMAC-MD5 which is normally quite fast - although the MD5 speed in OpenSSL isn't that great (but it's the only supported version of HMAC for the speed command, unfortunately). And SHA-256 may also have hardware acceleration. This is a muddy field...

  Is there an advantage to HMAC other than speed and being able to debug data that remains in clear text? Only other thing I know is smaller unpadded payload data.

HMAC is a very sturdy algorithm that doesn't suddenly fail. AES-GCM may fail catastrophically if the authentication tag is too small or if the IV is repeated. I'd say that HMAC is less brittle than AES-GCM: the latter is secure, but it doesn't bend - it breaks.

  Slightly aside, but does HMAC or AEAD benefit from including their nonces in the hashed / additional data? My replay attack prevention will mostly revolve around server time delivered to device on connection included in each message.

No. HMAC doesn't contain a nonce (although you may need a message specific nonce to avoid replay attacks). AES-GCM always includes the nonce automatically during the verification of the authentication tag, so adding it separately is useless.


Can we ensure the security of a crypto-algorithm and -implementaton against acoustic cryptanalysis?

The problem is a very old one going back at least as far as the late 1940's early 1950's and has been shown to exist with Quantum Key Exchange as well.

You need to think of it in terms of entropy down to heat pollution where a coherent signal energy steps down due to inefficiency via various transducers to what is basically thermal noise where the noise threshold is significantly above any residual coherent signal.

Most people incorrectly think that TEMPEST is all about EM energy, it's not. It's about any energy (EM, acoustic/mechanical conducted or radiated even gravity) in one or more Shannon channels which have bandwidth, noise and propagation delay giving rise to phase as well as amplitude effects. It's also about transducers which can be bidirectional (a DC Motor/Generator being such a beast, as are some types of microphone/speaker by moving coil or piezo effects).

Put simply, a capacitor is two metal plates with an insulated gap. When current flows into the plates a magnetic field is generated that will cause the plates to move fractionally in sympathy with the current. Also some insulators are dielectrics which have a piezo effect as the voltage rises the dielectric deforms mechanically. Both of these effects will cause the capacitors to emit sound. Likewise inductance effects designers of RF oscillators are well aware that mechanical vibration of the inductive component will cause the resulting output of the oscillator to be modulated, it's frequently called microphonics.

These basic physical effects cannot be prevented only reduced or mitigated. In EmSec you look to reduce the bandwidth of any signal path such that it is less than the information bandwidth and also at signal containment/absorption.

Theses mitigations when done properly all add significant cost to a product. Therefor in a price sensitive market such as PC manufacture anything that is not regulated will cause a race for the bottom. And even where there are regulations (EMC) the market will still look at avoidance rather than meeting the intent of the regulations. One such avoidance is "direct sequence spreading" of the PC master clocks/oscillators such that the energy in a spur/sprog is spread so that it's energy/Hz decreases and thus meets the regulatory masks. Unfortunately the energy is still there and still caries the signal information and only needs de-spreading to recover the signal information.

One solution to "singing caps" is high melt temperature wax or some hot melt glues they absorb the audio signals and reduce the effective channel bandwidth. Another partial solutions is 'sound absorbing foam' that also lets air flow through and the right selection of materials will significantly reduce the audio channel through fan and ventilation grills.

But as I noted all steps are "mitigations" not real "solutions", but may well be sufficiently effective in their own right if (and only if) implemented correctly.


Does Curve25519 only provide 112 bit security?

Some claim that Curve25519 has 112 bit security, others that it has 128 bit security; which is it?

Well, actually, neither - it's actually somewhere in the middle.

For a curve without known weaknesses (and Curve25519 doesn't have known weaknesses), then if the curve order has a large prime factor around $2^{2k}$, then the best known attacks against it take $O(2^k)$ time (where the O-notation conceals a constant which is a bit larger than 1, but is constant for the various types of curves), and so by convention, we say that such a curve as "k-bits of strength".

Now, for Curve25519, the curve order has a prime factor circa $2^{252}$; by the above standard metric, this yields a security of 126 bits.  This is slightly less than the 128 bit security that the curve P256 claims; however it is significantly more than the 112 bit security that was claimed on the IETF mailing list.

Is the difference between 126 and 128 bit security significant?  In my opinion, no; a work effort of 128 bits ought to be sufficiently large that a factor of 4 decrease in the attacker's time still should make this infeasible.

In addition:

  Every known attack is more expensive than performing a brute-force
  search on a typical 128-bit secret key cipher.

Makes a very good point; against an elliptic curve, the fundamental operation that is perfomed during the attack is an elliptic curve point addition; this is significantly more expensive than (say) testing an AES key.  And, I believe this remains true even if you factor in a 4-times speedup on the elliptic curve side.


I think it is often considered a principle in evaluating the quality of a cryptographic setup to start with the assumption that the opponent is aware of the algorithm and the only variable unknown is the key. Given this, there are not many cryptographically motivated security benefits/differences, given you use the same cipher (+ block chaining mode of operation).
Arguably for the human eye, the LUKS header gives away information to the attacker and it feels wrong to do so. I expect we are misled in thinking that because of the perceived amount of information about the specifics of the encryption it is a human emotion to feel bad since one whole point of encryption is to avoid giving away information in the first place.
Yet by using dm-crypt directly I fear most of what is achieved is some additional security through obscurity, something many people are rather skeptical about. Maybe this is because its effect can hardly be estimated. To some extent for instance you might be coerced into using a safe encryption scheme either way and since such a trusted cipher (block-chaining-mode+) does not exist in that great abundance, chances are high that you will use AES 256 CBC or alike. If you were to use some other cipher you maybe might gain potentially some better protection against cryptanalysis that attempts to abuse AES specific weak points. On the other side, not using AES for this inestimable safety might lead you to a cipher XXX that is not as tested and hardened against standard cryptoanalytic attacks.
After all in bullet-point style (things to consider):

LUKS header will defeat much plausible deniability, while dm-crypt pseudo-random hard drive "better" (this is of course not a cryptographic attribute, and would more be focused on http://security.stackexchange.com )
LUKS will use some random data source (I think it is /dev/random even) to create the master key for encrypting the hard drive/partition, which might be considered more entropic than a key derived from a passphrase (if that was the way you provide dm-crypt with a key).
Then again, LUKS will generate key slots that use key derivation functions to accept keys for unlocking the master key.

Consider also that security is a context-dependent concept. For instance, it can be said a LUKS setup is more secure as it protects you from losing the encryption master key since after all it is stored (again encrypted) in the LUKS header. You still can lose access to your data by way of forgetting the passphrase.
Also, LUKS gives some security to lose the information about which cipher was used, as it is directly stored in the header, while that would be something that you need to secure your dm-setup against (you need to remember what you did).


Is there an algorithm for factoring N, which is just as simple as this one, but faster?

Pure nonsense. For choosing the random $\Delta$ between $\sqrt{\min(N, Ň)}$ and $\sqrt{\max(N, Ň)}$ there are too many possibilities for it to work. For example whenever the first and last digits of $N$ differ, you get something like $\frac{1}{10} \cdot \sqrt N$ possibilities (the exact formula doesn't matter).

So you can replace the first formula $\gcd[N, (k × Ň) + Δ]$ with $k=1$ by this one: $\gcd[N, \Delta]$. Try all $\Delta$ between $1$ and $\sqrt N$, the number of possibilities is within some small factor.

Compared to the division, computing $\gcd(N, x)$ has the advantage that at each attempt you try all factors of $x$. This is good in case $N$ has some small factors, which in case of RSA is surely not true.

I see no advantage of the linked algorithm to trial division. Trying all primes up to $\sqrt N$ is probably faster, terminates also when $N$ is prime, and has a bounded time.

Summary: pure nonsense.


A clarification about OTR shared secrets - how long need they be secret?

Yes.
OTR uses the socialist millionaires protocol, which is an interactive protocol Alice and Bob use to establish confidence that their secrets match (without either of them disclosing the secret). If the authentication succeeded, both parties store the public key fingerprint of the other and mark it as trusted. The shared secret is not used any further (e.g., to derive keys used in later stages), thus knowledge of it is useless to an attacker after the initial authentication step has finished. (That is, after the authentication was done, there is no difference to manually having compared the fingerprints.)

Of course, if Alice and Bob authenticate again at a later point in time (e.g., because one of them created a new key pair), they must not use the same shared secret if it is not secret any more. (This should be obvious.)


Paillier cryptosystem preserve ordering of sums for two integer sequences

Paillier is not order preserving, so in your algorithm $x_1+y_1$ IF and ONLY IF $x_1+y_1 <= x_2+y_2 \dots$ simply does not work. You can't do the $\leq$ comparison.

Whether you have the same $r$ or not does not really matter, if we look at the encryption:

$E(m)= g^m r^n$ mod $n^2$

You could try to achieve that by fixing $r^n$ such that the product with $x$ doesn't surpass $n^2$ (and thus isn't reduced any further by the modulus), but that means you have to find $r$ so that $r^n$ is quite low, and then your entire security will go down in flames most likely.


To answer the question, no, you can't hope to get 256-bit IND-CCA2, by encrypting a 256 bit mac key.

Suppose you are playing the IND-CCA2 game and have got to the point where you have submitted two plain text messages $M_1, M_2$ and have got a challenge cipher text $C$. Your job is to decide which plain text $C$ corresponds to, with less than $2^{256}$ calls to the decryption oracle. Since you may choose both the mac and randomize the mac key (by modifying the first blocks of cipher text), the birthday paradox applies, and you are limited only by the collision resistance of the underlying hash function.

Depending on potential vulnerabilities in the underlying hash function, being able to modify the second half of the mac key, while leaving the first 128 bits of the mac key unmodified, might entail vulnerability to chose key attacks.

A more conventional IND-CCA2 secure construct would be:

encrypt(text, enc_key, mac_key)
  iv = generaterandom()
  cipher = iv + aes_cbc_encrypt(enc_key, iv, text)
  return cipher + hmac(mac_key, cipher)

decrypt(cipher, mac, enc_key, mac_key)
  if (hmac(mac_key, cipher) != mac)
    return null;
  iv = cipher[0..127]
  return aes_cbc_decrypt(enc_key,iv,cipher[128..cipher.length-1])

Please note that the usual caveats regarding all block chaining modes for 128 bit block sizes, and CBC mode in particular, apply regarding maximum amount of cipher text and maximum number of messages, before you start loosing security.

If you may choose the enc key and the mac key independently at random, that would be ideal. If not, but you are limited by a fixed size key material (the key in your question), you may extend it and split it, using a standard KDF, such as HKDF.

Please also note that if timing attacks apply, you might want to go ahead and decrypt the cipher text, even if the hmac verification fails (but still discard it in case of mac verification failure). However, if timing attacks against the application layer apply, you would anyway have to put in counter measures at that level.


What is the security concept in printer cartridge?

A company can make more money if the printers it sells only work with the cartridges they sell, which does not work if there is competition. It's cheaper to force a vendor lock-in than it is to innovate and ensure that your product holds up to the competition. All the printer's authentication does is prevent you from using cartridges made by other companies. Think of it like DRM for ink. It's just capitalism.

There is no standard protocol. Each vendor is free to implement this in their own way. Most likely it's some form of challenge-response authentication done between the cartridge and the printer.


Salsa20/8 is used not to enhance cryptographic strength, but to make random-ordered requests to the RAM (and to slower FPGA/ASIC implementation of scrypt). The scrypt uses PBKDF2-HMAC-SHA-256 (PBKDF2 of HMAC-SHA256) to provide such strength.

There is simple variant of scrypt, with parameters p=1 (Parallelization parameter), N=16384, r=8, taken from linked draft and simplified for p=1:

Algorithm scrypt

Input:
        P       Passphrase, an octet string.
        S       Salt, an octet string.
        N       CPU/Memory cost parameter, must be larger than 1,
                a power of 2 and less than 2^(128 * r / 8).
        r       Block size parameter.
        p       Parallelization parameter, a positive integer
                less than or equal to ((2^32-1) * hLen) / MFLen
                where hLen is 32 and MFlen is 128 * r.
        dkLen   Intended output length in octets of the derived
                key; a positive integer less than or equal to
                (2^32 - 1) * hLen where hLen is 32.

Output:
        DK      Derived key, of length dkLen octets.

Steps:

 1. B[0] = PBKDF2-HMAC-SHA256 (P, S, 1, 128 * r)

 2. B[0] = scryptROMix (r, B[0], N)

 3. DK = PBKDF2-HMAC-SHA256 (P, B[0], 1, dkLen)

We can see that there are two PBKDF2 with HMAC SHA256, one before ROMix and one after. They will provide collision resistance for the scrypt.

And here is the scryptROMix, which uses N-sized array, every element of which is equal to scryptBlockMix of previous element (step 2). Salsa is used inside scryptBlockMix and in scryptROMix it defines both transformations of X and the order of read accesses to V array:

Algorithm scryptROMix

Input:
        r       Block size parameter.
        B       Input octet vector of length 128 * r octets.
        N       CPU/Memory cost parameter, must be larger than 1,
                a power of 2 and less than 2^(128 * r / 8).

Output:
        B'      Output octet vector of length 128 * r octets.

Steps:

 1. X = B

 2. for i = 0 to N - 1 do
      V[i] = X
      X = scryptBlockMix (X)
    end for

 3. for i = 0 to N - 1 do
      j = Integerify (X) mod N
             where Integerify (B[0] ... B[2 * r - 1]) is defined
             as the result of interpreting B[2 * r - 1] as a
             little-endian integer.
      T = X xor V[j]
      X = scryptBlockMix (T)
    end for

 4. B' = X


Secure double encryption using CPA and CCA

For CPA security it is actually enough that the first scheme, i.e., $\pi = (gen, enc, dec)$ is CPA secure.

Lets define the CPA game of a general scheme $\pi = (Gen, Enc, Dec)$ against an adversary $A$ as follows:

We sample $(pk, sk) \leftarrow Gen(1^\lambda)$, and send $pk$ to $A$.
$A$ outputs messages $m_0$ and $m_1$.
We sample $b \leftarrow \{0,1\}$ (a random bit), and $c \leftarrow Enc(pk,m_b)$ (here I add the public key as a parameter to $Enc$, to make the key explicit)
$A$ outputs a bit $b'$.

We say $A$ wins if $b = b'$, and the scheme is IND-CPA secure if $A$ has at most negligible advantage.

Now, let $\Pi = (Gen, Enc, Dec)$, $\pi = (gen, enc, dec)$ and $\pi' = (gen', enc', dec')$ be the schemes you suggest in your question. Assume there exists an adversary $A$ with non-negligible advantage against $\Pi$ (i.e., proving $\Pi$ is not IND-CPA secure). Then we can construct an adversary $B$ against $\pi$ as follows:

On input $pk$ from the CPA game $B$ samples $(pk', sk') \leftarrow gen'(1^\lambda)$, and sends $PK = (pk, pk')$ to $A$.
When $A$ outputs $m_0$, $m_1$ $B$ forwards these messages to the CPA game.
On input $c$ from the CPA game $B$ samples $C \leftarrow Enc'(pk', c)$ and sends $C$ to $A$.
When $A$ outputs $b'$ $B$ outputs the same bit.

Now you see that $B$ wins the CPA game against $\pi$ if and only if $A$ would have won the corresponding game against $\Pi$. This means that since $A$ has non-negligible advantage against $\Pi$ and $B$ has provided $A$ with messages exactly as in the CPA game against $\Pi$, it follows that $B$ must also have non-negligible advantage against $\pi$. This, however, contradicts $\pi$ being IND-CPA secure, so no such $A$ can exist. I.e., $\Pi$ is also CPA secure.

Note the security of $\pi'$ really does not matter here.

A similar proof might be possible for CCA security, but I have not attempted one.


How much is slower GCM AES-128 than one of the stream chipher eSTREAM?

eBACS, as given by CodesInChaos, is a great resource, and it provides much more data than I could hope to give in this answer. However, the page is not explicit about whether or not AES-NI was used — looking at the results, it doesn't seem so.

For an extremely shallow analysis, but allowing us to know for-sure about hardware acceleration, we can use the command-line tool gnutls-cli, which uses GnuTLS to benchmark some ciphers. Some sample output:

[reid@reid-pc] ~ % gnutls-cli --benchmark-ciphers
Checking ciphers, payload size: 16384
     SALSA20-256-SHA1 0.30 GB/sec
     AES-128-CBC-SHA1 0.33 GB/sec
     AES-128-CBC-SHA256 0.21 GB/sec
     AES-128-GCM 1.34 GB/sec
            SHA1 0.56 GB/sec
          SHA256 0.29 GB/sec
          SHA512 0.44 GB/sec
        3DES-CBC 26.96 MB/sec
     AES-128-CBC 0.75 GB/sec
     ARCFOUR-128 0.51 GB/sec
     SALSA20-256 0.64 GB/sec

So, on my system (which has an Intel i5 Ivy Bridge and thus the AES-NI instruction set), AES-GCM processes data at about 1.34 GB/sec while Salsa20-256 with HMAC-SHA1 only manages 0.30 GB/sec.

However, it's thanks to the aforementioned AES-NI instruction set that AES-GCM fares so well. gnutls-cli has another argument to turn off hardware acceleration:

[reid@reid-pc] ~ % gnutls-cli --benchmark-soft-ciphers
Checking ciphers, payload size: 16384
     SALSA20-256-SHA1 0.30 GB/sec
     AES-128-CBC-SHA1 175.29 MB/sec
     AES-128-CBC-SHA256 136.43 MB/sec
     AES-128-GCM 169.09 MB/sec
            SHA1 0.57 GB/sec
          SHA256 0.29 GB/sec
          SHA512 0.44 GB/sec
        3DES-CBC 26.97 MB/sec
     AES-128-CBC 0.25 GB/sec
     ARCFOUR-128 0.51 GB/sec
     SALSA20-256 0.64 GB/sec

Note here that Salsa20-256 with HMAC-SHA1 outperforms AES-GCM. So, if your requirements allow you to use the AES-NI instruction set (e.g. the near-latest Intel chips), then AES-GCM is definitely the way to go. On the other hand, if your specs are more modest, you may want Salsa20-256 with HMAC-SHA1.

Another benchmarking tool is openssl speed, but it doesn't support Salsa20. Running a benchmark on AES-GCM with openssl speed -evp aes-128-gcm, I get about 1.33 GB/sec, similar to GnuTLS.


How does a key wrapping like RFC 3394 secure my cryptographic keys?

Yes, you are correct; the keywrap algorithm assumes that you have one long term secure key, which you can use to protect other keys.  The writers of RFC 3394 assume that you do have a secure key-encrypting-key (KEK).

This doesn't appear to be a valid assumption in your case.  In your case, you need to do cryptographical operations even though someone can assume your entire memory space; this sounds like you need White Box cryptography.


2048 bit hashing and 1024 bit symmetric encryption

Because the numbers required to achieve that level of security are much lower, even versus an adversary with a quantum computer. See this question/answer on security.stackexchange for the specifics.

Assuming that 256 bits/512 bits are secure for encryption/hashing, anything greater cannot serve a functional purpose in terms of security (it cannot be "more secure").

The biggest major factor besides security is performance. If the algorithms are not more efficient then their traditionally sized counterparts, then there is no motivation for their creation. Your proposed extremely large algorithms could potentially have performance issues. Using copious amounts of data is not necessarily register or cache friendly. Such large algorithms could also be difficult/expensive to implement on constrained/dedicated hardware.


Which is slower, AES or GCM hash (GHASH), if CPU has no special instructions?

First things first: the passage you quote does not claim that GHASH is slower than AES. What it says is that if you replace AES/CTR with a much faster stream cipher, then the GHASH part will be comparatively expensive.

There are many kinds of implementations, for both AES and GHASH; they have different performance characteristics, and they may be constant-time, or not. I'll use BearSSL here for most measures, because I know how that code works (I wrote it), and I can easily benchmark it. The measure platform here is my laptop (Intel i7-6567U at 3.3 GHz, in 64-bit mode):

AES-128 CTR (big)                170.67 MB/s
AES-128 CTR (ct64)               108.91 MB/s
AES-128 CTR (x86ni)             5307.37 MB/s
GHASH (ctmul)                    214.63 MB/s
GHASH (ctmul64)                  277.17 MB/s
GHASH (pclmul)                  4795.76 MB/s

For the AES implementations:

"big" is a classic table-based implementation (not constant-time).
"ct64" is a constant-time bitslice implementation that uses 64-bit registers and computes 4 AES instances in parallel (which works well with CTR mode).
"x86ni" uses the AES-NI opcodes (it computes four instances in parallel, which maps well to the 4-cycle latency of these opcodes on a Skylake core).

For the GHASH part:

"ctmul" uses 32x32→64 integer multiplications with masking to avoid trouble with carries. It is constant-time.
"ctmul64" uses 64x64→64 integer multiplications with masking; it is also constant-time.
"pclmul" uses the AES-NI opcodes.

The following extra notes apply:

All GHASH implementations in BearSSL are constant-time. It is possible to make non-constant-time GHASH implementations which are faster, by using lookup tables, in particular dynamically generated tables for the specific secret $h$.
There is a constant-time bitslice implementation of AES that leverages SSE2 opcodes, both for extra parallelism (128-bit registers) and more efficient implementation of the linear parts of the algorithm. It would go over 400 MB/s on this machine, and would outperform the constant-time GHASH implementations. Whether it qualifies as "not using special opcodes" is debatable: it is not using the AES-NI opcodes, but not all 64-bit architectures have something similar to SSE2 (it is part of the ABI on 64-bit x86, though).
Combining AES and GHASH may offer speed-ups, if they do not exercise the same compute unit within the CPU. For instance, with the AES-NI opcodes, interleaving the AES/CTR encryption and the GHASH can yield better than the already quite decent 2.5 GB/s that the figures above promise.

An aggregate rule of thumb is that, when using only "basic" operations (i.e. those available in C without inline assembly or compiler intrinsics), you can keep the cost of GHASH to less than half the cost of AES/CTR (if using a non-constant-time AES, it makes more sense to measure against a non-constant-time GHASH).

Now let's compare with ChaCha20 and Poly1305:

ChaCha20 (ct)                    407.74 MB/s
ChaCha20 (sse2)                  590.59 MB/s
Poly1305 (ctmul)                1248.27 MB/s
Poly1305 (ctmulq)               1936.74 MB/s

The "ct" implementation of ChaCha20 uses only 32-bit integer operations; the "sse2" implementation uses SSE2 intrinsics. For Poly1305, the "ctmul" implementation uses basic 32x32→64 multiplications, while the "ctmulq" implementation uses 64x64→128 multiplications (which require some compiler intrinsics or extensions). All of these are constant-time.

What this says to us is the following:

Without AES-NI, ChaCha20 outperforms AES. Actually, constant-time ChaCha20 substantially outperforms all AES, even non-constant-time.
Without AES-NI, Poly1305 is much faster than GHASH.
If you want to make an hybrid out of ChaCha20 and GHASH (this is the context of the previous question that you want to discuss), then the GHASH part is going to be more expensive than ChaCha20, except if you use the AES-NI opcodes for GHASH; but then, if AES-NI opcodes are available, why would you use that ChaCha20 hybrid instead of standard AES/GCM?


Session based AES with random key and static salt

Currently you seem to be using a Password Based KDF (PBKDF); you are using PBKDF2, as defined in Rfc2898. You don't need to do this as randomly generated data is already fine for creating an AES key. So - as you don't need a PBKDF - you don't actually need a salt.

If you need more keys or key data then what is actually required is a Key Based KDF (KBKDF), as your shared secret already contains enough entropy. Passwords usually don't, that's why they require the key strengthening delivered by PBKDF (by using a salt and iteration count). HKDF doesn't require a salt either, but its security properties are significantly enhanced if you do provide a salt.

Note that CBC should not be used by itself to create a secure transport protocol. CBC does not provide integrity nor authenticity. And if error (padding) oracles apply - which is likely - then it doesn't even provide confidentiality, leaving you with nothing. You need to at least add a MAC - HMAC is preferred - and a MAC key. To generate two keys...see the second paragraph and provide two different labels (or "OtherInfo"), one for each key.


Encryption vs. decryption of same plaintext

It very much depends on the encryption scheme you are using.
In a deterministic encryption scheme, the same plaintext is always encrypted to the same ciphertext (when using the same key of course).
This indeed causes a security problem for all deterministic schemes. I.e. no deterministic scheme can be IND-CPA secure.

If you take a look at the IND-CPA game, you can see why: The adversary $\mathcal{A}$ may simply choose two random messages $m_0,m_1$ and submit them to the challenger. After receiving the ciphertext $c$ he asks for an encryption of $m_0$ and receives ciphertext $c'$. Now as the scheme is deterministic, it follows that $c=c'$ if and only if $c$ is an encryption of $m_0$, therefore if $c=c'$ $\mathcal{A}$ outputs $0$, otherwise $1$.

Therefore, to achieve IND-CPA security we need probabilistic encryption. In a probabilistic encryption scheme, the encryption algorithm uses additional randomness to produce the ciphertext. See for example ElGamal encryption, where the ciphertext consists of two parts, one of which is a random group element. Also all secure modes of operations for block-ciphers introduce randomness in the form of nonces or initialization vectors.

An important thing to note about probabilistic encryption is that, because decryption must be deterministic, and a single plaintext corresponds to a larger number of ciphertexts, the ciphertext will always be longer than the plaintext.


What is the meaning of Maximum Expected Differential/Linear Probability (MEDP/MELP)?

The paper you link to gives precise definitions for the MEDP and MELP.  I will attempt to explain the definitions more expansively & clearly.

First, the differential probability (DP) function with respect to a given block cipher takes an input difference $\Delta x$, an output difference $\Delta y$, and a key $k$ as inputs and generates a probability as the output.  This probability can be understood to mean: “the number of pairs of plaintexts $(P_a, P_b)$ such that $P_a \oplus P_b =  \Delta x$ and $E_k(P_a) \oplus E_k(P_b) = \Delta y$ (where $E_k(\cdot)$ is the encryption function of the given blockcipher under the key $k$) divided by the total number of possible pairs of plaintexts where $P_a \oplus P_b =  \Delta x$ (which is just $2^B$ where $B$ is the block-size in bits of the blockcipher).”

The Expected Differential Probability (EDP) is a function that takes an input difference and output difference and finds the simple average DP of that input-output difference pattern (averaged over all possible keys).  Expectation in this case reduces to the simple average because as the paper states we are assuming all keys are equiprobable.  So in plain English, add up the DP of that difference pattern for every key and then divide the resulting sum by the size of the keyspace (e.g. $2^{128}$ for AES-128).

The MEDP is simply the maximum such EDP over all possible pairs of input difference and output difference, excluding the all-zero input/output difference (which if not excluded would trivially be the maximum, but which is not useful for cryptanalysis).  In (hopefully) plainer English, this asks what pattern of input and output differences gives the attacker the best chance (averaged over all keys) of finding a pair of plaintexts that match that pattern, and how much of a chance is that best chance?

The MEDP is used to evaluate how resilient a block cipher is to differential cryptanalysis.  If you can prove that a cipher has a very low MEDP then the cipher is provably secure against that type of attack (“very low” meaning something only slightly higher than the MEDP of a random permutation, i.e. $\dfrac{1}{2^B}$).

Switching to the linear probability (LP), with respect to a given block cipher this is a function that takes an input mask $a$ (a string of bits $B$ long), an output mask $b$, and a key $k$ and returns a probability.  In terms of how these masks are used, $a \bullet X$ means taking the $B$-bit string $a$ and ANDing it with the $B$-bit string $X$, and then xoring together all $B$ bits of the resulting string to get a checksum bit.  As section 5 of the paper describes, the probability generated by the LP function is: $2 \cdot$ “number of plaintext-ciphertext pairs $(P_i, E_k(P_i))$ for which $a \bullet P_i = b \bullet E_k(P_i)$ divided by the total number of possible plaintexts (i.e. $2^B$)” $-1$ all squared.  For example, if the expression $a \bullet P_i = b \bullet E_k(P_i)$ is true for exactly half of the possible plaintexts $P_i$ then the LP would be $(2 \cdot \frac{1}{2} -1)^2 = 0^2 = 0$.  If the number of plaintexts for which the expression is true deviates from 50% (either higher or lower than 50%) then the LP will be higher than 0, and the more the deviation the closer the LP will get to 1.

The ELP is very similar to the EDP in that for a particular pair of input and output masks the ELP gives the average LP (averaged over all possible equiprobable keys).  Like the MEDP, the MELP is simply the maximum ELP over all possible input-output mask pairs (excluding the all zero masks).  Similar to the MEDP, the MELP is used to evaluate how resilient a block cipher is to linear cryptanalysis (a provably very low MELP is a proof that the cipher is secure against that type of attack).

For the last part of your question, the reason why the paper focuses so much on finding the exact MEDP and MELP for 2 rounds of AES is that one can prove that the MEDP and MELP for 4 (or more) rounds of AES is upper bounded by the 2-round MEDP (respectively MELP) raised to the power 4.  So if they find the 2-round MEDP/MELP they immediately can give an upper bound on the MEDP/MELP of the entire cipher.


What challenge should I use in a challenge-response proof-of-work?

A good PRNG can't be exhausted, so your argument against random bytes doesn't matter.

  firstly I'd like the server to be completely stateless.

Sounds impossible to me.

a PRNG needs state. A clock needs state.
An open connection is state too
You probably want to store open challenges too. This part isn't strictly necessary, but very convenient.

You might also want to include something unique to the server in the challenge(for example its domain or IP address) so clients can't be tricked by one server into solving the challenge for another.

I'd go with the server sending 16 random bytes as challenge, and the client responding with something like ServerIP || HMAC(proof, Challenge || ServerID)


How to calculate key size of a security algorithm?

There are lots of security algorithms. One of the way to measure security of a cryptography algorithm is to find out its key size. There are many key size of a single algorithm. But how can I calculate key size of an algorithm? How a single algorithm has different key size?

There is no standardized method that can help you with that. The best way to figure out the key sizes that are applicable is to lookup the standards that the algorithm should comply to. Furthermore, implementations may restrict those sizes further. If you are unlucky they may even expand the possible sizes of the input / output parameters (including the key size).

Lets take a look:

RSA: any key size will do (starting with a ridiculously low minimum), but usually the key size should be a multiple of 8 bits and possibly of a specific size or higher (e.g. > 1024 bits);
DH: the key size consists of two numbers, of which the size of the group is most important for security - specifying the key size is hard;
AES: AES has key sizes 128, 192 and 256 bits and the number of rounds changes for the different key sizes. AES is a subset of Rijndael which has key sizes 128, 160, 192, 224 and 256. The .NET classes that implement Rijndael only support the AES key sizes (but more block sizes);
Blowfish has a configurable key size of 32 bits up to 448 bits with steps of 8 its;
3DES has key sizes of 128 bit or 192 bit total, but the actual key size without parity bits is 112 and 168 bits respectively. The actual effective security is about 63-80 and 112 bits respectively.

This clearly shows you that key size is a tricky subject.

  My algorithm is to change a letter of a plain text by a code suppose a=2H, b=3C, c=8S ......, z=6D

The key size is what you define as the key size. You could define the string 2H3C8S ...... 6D as your key, given you a total key space of $10^{26}$ (for the digit in the code) times $26^{26}$ (for the letter in the code). Then the key size in bits is then $\log^2({10^{26} \times 26^{26}})$ or 20902 bits (!). Obviously the actual key size is somewhat smaller as you should not repeat codes (just like the parity bits for DES are not counted).

The effective key size is of course about zero as this is not a secure modern cipher.


Preserving the format of an email address (see RFC 5322 § 3.4.1) when encrypting it is quite easy. All you have to do is encode the ciphertext in base64 and prepend it to something like @a.invalid if you want to make sure that it cannot be resolved even by accident. This results in emails like this:

3IPRr5/0rrgWuzZBFoRDpl8PYE76xuHxYdRJzfu2mKw=@a.invalid

That is a technically valid email address for a non-existent and non-resolvable domain.

Note that this does not preserve the length of the plaintext. If you wish to do that as well, you could use a dedicated FPE mode of operation as per NIST SP800-38G. Unfortunately, that would likely result in an email address that is invalid due to the fact that the format specified in RFC 5322 is too complex for it.

While not strictly FPE, you may be able to get what you want by using a Vigenère cipher with the key generated by a secure stream cipher, such as ChaCha20. The set of characters in the Vigenère key must be valid for that atom of the address. You must of course skip the @. This will preserve the length. Note however that it requires a more complicated construction as fgrieu pointed out, notably due to the fact that the IV would need to be stored separately or a unique key must be used for each email.


Minimum number of public and private keys depending on signature?

I'm having a little trouble following your reasoning. I think your difficulty comes from an invalid initial assumption.

  Asymmetric: Two key pairs on each branch, e.g., Joe and Jill must each have a public and private key. The number of key pairs is N * (N – 1)

No! It is in fact the main advantage of public-key cryptography that each participant only needs one pair of keys. For $N$ participants, the number of key pairs is $N$.

More precisely, each participant needs one pair of key for each purpose. Using the same keys for encryption and for signature can be ok, but it can also lead to trouble for various reasons:

It can lead to protocol errors where a participant is tricked into signing something, but the thing in question was encrypted with the corresponding public key, and the signature reveals all or part of the content because the signature operation uses the same key that the decryption would.
Conversely, a participant may be tricked into decrypting something, and the result may be used to forge a signature.
Decryption and signature keys typically have different retention policies: you shouldn't keep signature keys around when you want to stop using them, but you often need to keep decryption keys for a long time to decrypt old messages.

Still, that's only two pairs of keys per participant if each participant both signs and decrypts messages. The point is that the number of keys does not grow super-linearly with the number of participants.

  1) If we want to send identical information to the other (N-1) using asymmetric cryptography, but also digitally sign the communication so that the other members know it's from Smith and has not been modified.

When Alice sends a message, she encrypts it $N-1$ times, once with each recipient's encryption public key. Each recipient will decrypt their copy with their decryption private key. Alice signs the message only once, with her signature private key. Each recipient will verify the signature using Alice's verification public key.

That's a total of $N$ key pairs: $1$ signature key pair and $N-1$ encryption key pairs.

  2) The personnel (N-1) must be able to send information back to Smith using asymmetric; assuming the keys are known only to members of the group, how many public and private keys must exist? In this case, Smith does not need to verify the actual identity of the member sending the message.

For $N-1$ participants to send encrypted data to Smith, only one key pair is necessary: the senders encrypt with Smith's encryption public key, and Smith decrypts with his own decryption private key.

  3) The (N-1) members of the group must be able to send information to Smith using asymmetric cryptography. Assuming the keys are only known to member of the group, what is the minimum number of private and public keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication.

Each of the $N-1$ senders signs their own message with their own signature private key. Smith verifies using the sender's verification public key.

  4) The (N-1) members of the group must be able to send information to the Smith using symmetric cryptography. Assuming the keys are only known to appropriate members of the group, what is the minimum number of symmetric keys to accomplish the task? Smith must be able to verify the identity of each group member sending a communication and verify each message has not been modified using the digital signature of the message hash.

Here, $N-1$ symmetric authenticated encryption keys are needed, or $2 (N-1)$ if you count encryption keys and authentication keys separately. There's the AE key that Alice shares with Smith, the AE key that Bill shares with Smith, the AE key that Charlie shares with Smith, etc.


Why is SKEYSEED derived using the nonce as a key?

The reason why the nonces are used as key is that there are some legacy PRFs, RFC 7296 mentions two, AES-XCBC-PRF-128 and AES-CMAC-PRF-128, that use a fixed key length (128-bit in this case, so only 64 bits of each nonce are used). Any DH key exchange that produces a longer shared secret would be rendered ineffective if its output was used as key with such PRFs.
So the nonces, which must be long enough to serve as half the key for any negotiated PRF (at least 128-bit each, most IKE implementations currently use 256 bits), are used instead to initialize the PRF and the DH shared secret as variable length seed to derive pseudorandom output from it.


Padding is dangerous. CBC mode with padding is secure against chosen-plaintext attacks, where the adversary can convince the legitimate party to encrypt messages and obtain the ciphertexts. But it is usually not secure against chosen-ciphertext attacks, where the adversary can craft ciphertexts and obtain information about the corresponding plaintext. Specifically, padding tends to be vulnerable to padding oracle attacks, where the adversary sends specially-crafted ciphertexts and does not obtain the corresponding plaintext, but finds out whether the padding in the ciphertext is valid. The adversary might find out, for example, because the decryptor emits an error message if the ciphertext is invalid, or because the decryptor does not carry out the action that it would carry out on a valid message, or because the decryptor takes a different amount of time to process messages with valid or invalid padding.
How devastating padding oracle attacks are depends on the nature of the padding and how much partial plaintext the adversary is likely to know. A well-known example is the Lucky Thirteen attack, where the conjunction of allowing up to 256 bytes of padding, and having 13 bytes of known plaintext in a message header, leads to a practical attack to fully decrypt a TLS connection against an unprotected implementation in many realistic scenarios.
In your case, the opportunities are more limited for the attacker, but the scheme is still vulnerable. Suppose the adversary knows or can guess the first 15 bytes of plaintext in a block and would like to know the last byte. The adversary can send that block to be decrypted as a 16-byte message, and learn at least whether the last byte is a valid value (1 to 16). This is not a complete breach of confidentiality, but it is a breach of confidentiality.
Padding oracle attacks depend on the adversary learning whether the padding is correct. A defense is to not have any invalid padding. An easy tweak to your scheme has this property: make the top 4 bits of the last byte random as well. This way no padding is invalid and therefore no padding oracle attack is possible as such. However, the adversary may still be able to learn the length of the plaintext (for example by measuring very precisely how long it takes to process), and if the ciphertext was one crafted by the adversary, this length could be in fact a confidential byte of the message.
To have an actual secure cipher, you need to use authenticated encryption. Authenticated encryption is not vulnerable to chosen-ciphertext attacks because the attacker cannot forge a superficially valid ciphertext: all valid ciphertexts include an authentication tag which cannot be calculated without the secret key. You can build authenticated encryption by taking unauthenticated ciphertexts and adding a MAC (“encrypt-then-MAC”), and that works even if the encryption part is padded CBC. On this topic, see Should we MAC-then-encrypt or encrypt-then-MAC?. However, CBC has no advantage over streaming mode, and all common proper authenticated encryption modes use CTR mode for the encryption part.


Using same AES-GCM setup for multiple packets?

In the context of packet communications, it feels like it would be optimal to setup key and IV once and then use that single initialisation in some way for all packets on the same channel.

It might be optimal for efficiency standpoint, but we also care about security; it isn't necessary very good for security.  You mentioned that, with CBC mode, you can use the last cipherblock as the next IV; well, you could, but there are known weaknesses with that involving chosen plaintext.  Other modes don't share this specific weakness.

As for GCM, well, it was designed to be used in a very specific manner (and proven to be safe in that manner).  However, if you use it in a different manner (such as reusing the same GCM state to both output an authenticate tag for one message, and continue to encrypt with another) would be, at best, playing with fire.

Now, to answer the questions you asked:

  Are there implementations that allow you not to reset the state when finalising a packet (i.e. making encryption and authentication dependent on the previous packet)?

I should hope not.  Using the same nonce with two different messages is known to be VERY BAD, and the obvious way to do it with continuing to use the current GCM state would appear to fall into that weakness.

  Failing that, what would be a safe way to derive consequent IVs from an initial IV value?

This one is easy: the only requirement that GCM has for IVs (nonces in GCM terminology) is that you can't use the same one twice; you can use any method of generating them that abides with this requirement.

Hence, one easy way to generate IVs is to generate them sequentially, as in:
 $$IV_{next} := IV_{previous} + 1$$

Oh, and you did mention that:

  I have no idea if there is a significant cost to setting up GCM with an IV

Assuming you use a 96 bit IV (which is the cheap size for GCM), the total cost is "one AES block encryption" operation.

Hence, selecting a new IV for each packet is both moderately cheap, and safe.

And, on a side topic: you mention that you were intending this for use with "packet communication".  Well, normally with this level of communication, you need to be able to deal with packet drops; that is, if the sender transmits a packet, but the receiver doesn't receive it correctly (or at all).  Because of this, I suspect you'll want to design you system so that the receiver can process packet 5, even if has never received packet 4.  Among other things, this implies that you might not be able to use implicit IVs; you may need to send them explicitly in the encrypted packet.


Does ChaCha20-Poly1305 need random nonce?

No, it doesn't need a random nonce.  Yes, if you use an incrementing counter, that works.

As the RFC says, the only requirement is uniqueness; as long as you make sure that each nonce you use is different, you have met the requirements - an incrementing counter does that quite nicely (and, in fact, is commonly used in practice)