How to do unmasked addition on SSS masked shares?

It seems that the question you're asking is about how to add a public (unmasked?) value to a secret-shared value. I suggest you edit the question a bit to clarify that this is not related to AES directly.
With that aside, adding a public value to a secret-shared value depends heavily on what secret-sharing scheme you're using, and also the algebraic structure where you're doing it, of course.
To secret-share a  single bit $b$ using additive secret sharing, you sample random bits $b_1$ and $b_2$ constrained to $b=b_1\oplus b_2$. The pair of shares is then $(b_1,b_2)$. To add a publicly known bit $u$, you only need to add it to one of the shares, say to $b_2$, so the new shares are $(b_1, b_2\oplus u)$. You can check that if you add (i.e. XOR) these together then you get $b\oplus u$, so you effectively added $u$ to the secret.
If you're additively secret-sharing elements of $\mathsf{GF}(2^8)$ instead of single bits the principle is the same, except that XOR is replaced with addition in $\mathsf{GF}(2^8)$. Quite coincidentally though, addition in $\mathsf{GF}(2^8)$ is precisely component-wise XOR, but this didn't need to be the case, specially if you used instead, say, $\mathsf{GF}(3^8)$.
Now, all of this was for additive secret-sharing, but this is not how Shamir secret-sharing works. In this scheme, secret-sharing a value $s$ among $n$ parties with threshold $t$ consists of sampling a random polynomial $f(\mathtt{X})$ of degree at most $t$, constrained to $f(0)=s$, and letting the $i$-th share be $s_i=f(i)$.¹ With this secret-sharing scheme, adding a public value $u$ is done by letting each party (not only one) add this value to its share, getting $(f(1)+u,\ldots,f(n)+u)$ as the vector of shares. I encourage you to check why this is a valid Shamir sharing of $s+u$.
To sum up from the discussion above, I think you are mixing additive with Shamir secret-sharing. The method you described and implemented is for adding a public value to an additive sharing, yet you mention in the title and the text Shamir secret-sharing.

¹ Here, the "numbers" $0,1,\ldots,n$ that we are evaluating into the polynomial are simply symbols to represent different elements of the field you're considering, e.g. $\mathsf{GF}(2^8)$.


Let's assume a password consisting of 15 random longish words from several books.  It's likely then that the password's entropy will exceed 256 bits. (This is actually very difficult to compute accurately as there are linguistic /social /physiological issues to human password creation, but let's skip over those).  That's more than that of an AES-256 key.  So in this case it seems that it's worthwhile attacking the AES key directly as it's got less entropy.

This would be a brute force attack directly against an AES-256 key.  The futility of this is well covered on this site.  I'll just add this link and say that you'd need more than all of the batteries on Earth for the energy demand. And a lot of time measured in age of Universe units.  It's impossible and really not worth doing.

It also opens up the question of what would KDFs be for if you simply bypassed them and attacked the cipher key directly?


Understanding one-way hash functions construction

First, it's important to understand that no one knows how to build a practical hash function that is provably secure.

The stuff you've read about games and advantage are part of a theory for proving schemes secure, but that theory doesn't help you build a provably secure hash function all that much.  Rather, it starts from the assumption that a particular hash function is secure (or a block cipher or stream cipher is secure), and then builds more complicated stuff out of those basic building blocks.  So, that theory doesn't help us design the basic building blocks, like hash functions, in the first place.  (Sometimes the theory is used to help guide the design of the structure of a hash function, where designers build a hash function out of a building block like a compression function.  The designers might use the theoretical analysis to demonstrate that if the compression function is good, then the hash function will be good -- but it doesn't help you with the question of how to design a good compression function.)

For more details on how we know that a hash function is secure, see my answer to a similar question (on the IT Security Stack Exchange site).

Generally speaking, to learn how to build a secure hash function, you start by learning about all of the various attacks on hash functions.  Then, you try to design a hash function that will resist all of those attacks (as well as all others you can imagine).  Therefore, a good starting place for you would be to read about attacks on hash functions.

You could start by reading Chapter 9 of the Handbook of Applied Cryptography.  Also check out Wikipedia's articles on cryptographic hash functions and the Merkle–Damgård construction.
Then, you could read all of the submissions to the NIST hash algorithm competition; most of the submissions should provide a design rationale and security analysis, which should give you a chance to read about some of the attacks on hash functions and design strategies.  They should also cite related papers in the research literature, so next you could read papers in the research literature on hash function cryptanalysis -- you might start by reading the papers cited in the Wikipedia links mentioned above, then proceed to reading papers that are cited in submissions to the NIST competition or that you find through others means.  For instance, it's worth reading about parallel collision search, multicollision attacks, indifferentiability, and the sponge construction.

After several years of study, you'll be well on your way to becoming an expert in hash function cryptanalysis, and then you might be ready to start thinking about designing your own hash function.


How important is hardware based crypto in Quantum-safe TLS in mobile devices?

Ring LWE schemes are relatively simple on a computation level -- the large majority of time is spent doing vector multiplication (another significant portion is sampling the error distribution). This is ideal for parallelization. So typically, RLWE implemented using the AVX2 instruction sets are significantly faster (for example, see a 3x speed improvement for one popular RLWE scheme: New Hope). I'm not sure on the ubiquity of AVX2 instructions on mobile devices, perhaps someone else can chime in.

That said, RLWE just isn't very computationally expensive in general. The paper above mentions that in terms of performance, the AVX2 implementation is in "the same ballpark" as state of the art ECDH implementations that use Curve25519 (which is one of the fastest ECC curves). I couldn't immediately find benchmarks comparing the two, and I don't know how to quantify "the same ballpark", but I've never heard anyone complain that RLWE is too costly performance-wise. So I don't think that the mobile CPU is the bottleneck.

Concerning RLWE, people do complain about the bandwidth of the key exchange. Even the best RLWE schemes still require much more data transfer (see the nice chart in the Frodo paper), which can significantly increase latency for poor connections. This appears to be corroborated by the results of Google's post-quantum TLS experiment, CECPQ1.

So I don't think battery life and/or performance will suffer much at all. Users with poor internet connections will certainly suffer a bit, but let's be honest -- they already suffer. The average page weight is in the megabytes, even for mobile. A few extra kilobytes in the handshake is a pittance compared to the amount of javascript and other assets most websites require. I realize this argument may not be valid for other protocols, but it does show that the average user probably doesn't have to worry about websites aggressively implementing hybrid post-quantum cipher suites.


Digital certificate issuing man-in-the-middle attack

Yes, that man in the middle attack is possible. The problem is that there is no direct way of providing initial trust to the CA. As long as that is not possible - traveling to the CA is rather expensive - there can be no complete trust.

The validation relies on the DNS and the fact that servers generally are on relatively secure connections. I presume that the CA itself doesn't run on public WiFi either. The challenge response protocol makes sure that you have control over the domain. It also makes sure that the challenge (nonce) cannot be copied without having the private key. But in the end it is protection so that nobody can initiate the connection with the CA

And that's what this protocol really does; it makes sure that somebody else doesn't request a certificate in your name. The amount of protection against man-in-the-middle is very limited. If the server or admin PC is hacked then an attacker will of course have little problem performing the steps himself.

Don't do these steps from an insecure PC or over an insecure connection and make sure that your server and server connection are secure as well. Otherwise the chances of MiTM are heightened. Note that this will still take an active attack, and I presume you checked that the connection to the CA is performed over TLS (right?).


Why is this the inverse of a Enigma Machine rotor?

The example is using a shorthand notation for the rotors that somewhat obscures the way they actually work.  For example, the first rotor in your example, BDFHJLCPRTXVZNYEIWGAKMUSQO, actually applies the following permutation of the alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
BDFHJLCPRTXVZNYEIWGAKMUSQO

Applying this rotor in the reverse direction thus, obviously, gives the inverse permutation:

BDFHJLCPRTXVZNYEIWGAKMUSQO
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Now, the same inverse permutation can also be written equivalently as:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
TAGBPCSDQEUFVNZHYIXJWLRKOM

You can check that these are, indeed, the same permutation: both map A → T, B → A, C → G, and so on.  The only difference is the order in which the individual input/ouput letter pairs are listed: in the first version, they are sorted by the output letter, while in the second version they are sorted by the input letter.

Now, the page you're reading is using a shorthand notation where the permutations are always sorted by the input letter, and only the output letters are actually shown.  This gives a nice and compact notation, but it does make it a bit harder to e.g. see whether two permutations are actually inverses of each other.


Isn't code signing just digital signature on code?

Indeed, code signing is a special case of digital signature, and there is no imperious reason to distinguish the two from the standpoint of defining a cryptographic signature primitive.

There are however reasons to special-case code signature from an IT security perspective, by a having a "code signing" attribute in a digital certificate. It is a useful distinction for a certificate wether it's a code-signing or data-signing certificate; that is, if the signature of a piece of data checking against the public key introduced by the certificate should be considered, or not, as and indication that said piece of data is safe to run as executable code. In a Unix file system context, the distinction might correspond to a rule: allow setting the Execute flag or not on the piece of data received.

A similar useful distinction for a certificate is wether it's a certification authority certificate or not; that is, if the signature of a piece of data checking against the public key introduced by the certificate should be considered, or not, as an indication that said piece of data is a certificate. The distinction might correspond to a rule: entering that piece of data, or not, in the list of certificates that can validate a digital signature.

In both cases, the distinction is made with an attribute in the digital certificate, typically with different rules for certificate issuance according to this attribute.

There are efficiency considerations to account for when selecting a signature algorithm according to context, and that has some degree of relevance when choosing such algorithm for code signature:

Simplicity of the signature verification: especially for early boot code, it might be essential that the signature verification code is short and fully auditable (e.g. because it stands in a special, prohibitively-expensive-to-change memory, and much of the rest of the security sandcastle chain depends on that). That's a reason to use RSA, or Rabin signature. That also applies to digital certificate signature.
Speed of the signature verification: especially for low-power embedded systems, it might be essential that code signature verification is fast. That's another reason to use RSA, or Rabin signature. That also applies to digital certificate signature.
Speed of signature generation. That's seldom a consideration for code, which is typically orders of magnitude harder to write or compile than it is to sign.
Size overhead. That's seldom a consideration for code, which nowadays is typically much larger than a signature.


64 bits cipher and birthday boundaries in ECB

First, remember that any cipher must be functionally correct, that is for any valid plaintext $$\operatorname{Dec}_k(\operatorname{Enc}_k(m))=m$$

This effectively means you must be able to properly decrypt any properly encrypted message. This also means that it cannot happen that $m_1\neq m_2$ with $\operatorname{Enc}_k(m_1)=\operatorname{Enc}_k(m_2)$ can happen. After all, how would you decrypt the result deterministically? To $m_1$ or to $m_2$? You can't decide, thus such a scheme would violate funtional correctness and thus this situation can't happen. Now Blowfish is functionally correct and as per the above argument you'll never see any collisions under the same key. Also you're using ECB where each block is encrypted individually meaning the above argument also applies to longer messages.

With CBC the situation is different, you encrypt as $c_{n}=\operatorname{Enc}(m_n\oplus c_{n-1})$ (where $\oplus$ denotes bitwise XOR). Which means if you find any two $(m_1,c_0),(m_2,c_1)$ such that $m_1\oplus c_0=m_2\oplus c_1$ you've got two resulting cipher texts looking the same (ie a "collision"). Note that $c_0,c_1$ are essentially random, and they're being combined with an unrelated value meaning the result will be essentially random again and you expect a collision among two random strings of length $l$ after $2^{l/2}$ samples.

One final note: If you're trying to use ECB for production, chances are you have the wrong mode. If you need something with random-access and no overhead, use AES-XTS, if you need something with random-access and authentication, chunk it with AES-GCM and in any other case just use (chunked) AES-GCM because it also takes care of authentication for you and will be much faster than Blowfish-ECB if your CPU supports AES-NI.


Multiplication vs exponentiation in pairing based cryptography

The problem is that you are comparing apples and oranges. A group has a single operation associated to it. Depending on your notational conventions you either need to write (1) $e((a+b)P,Q)$ and (2) $e(aP+bP,Q)$ if you write $G_1$ additively or (1) $e(P^{a+b},Q)$ and (2) $e(P^a \cdot P^b,Q)$ if you write $G_1$ multiplicatively. The cost of computing $(a+b)P$ or $aP+bP$ depends on your approach to scalar multiplication, but typically the former approach will be more efficient.


How secure is a 40 bytes hexadecimal string AES256 encrypted with 50 bytes random password

For reference, this is the Ansible Vault format. In short:

It derives an AES key, HMAC key and IV from the password using a 32-byte random salt
It encrypts the data using AES-CTR with the derived key and IV
It MACs the ciphertext (but not the IV) with HMAC-SHA256. Not including the IV is usually bad, but since the IV is derived from the password and salt and it's not stored with encrypted data, it seems OK.

As far as I know, this looks safe if the password is strong enough. In your case, what you call "key" seems to be the password, and is certainly long enough.


Is it possible to obtain AES-128 key from a known ciphertext-plaintext-iv tuple used the encrypt the plaintext?

Ciphers are designed to withstand far more adverse situations than the single known plaintext/ciphertext pair that you describe.  In particular, they are intended to be secure against chosen plaintext attacks, where:

The attacker submits plaintexts of their choice and are shown the resulting ciphertexts, as many times as they like;
The attacker's goal isn't to recover the key, but just telling the cipher apart from random results, which is much easier.

There are no known practical chosen plaintext attacks against AES, and there are security proofs for CBC mode.

There are of course impractical attacks that work only in theory.  You could just attempt $2^n$ distinct keys and you have a $1/2^n$ chance of finding the right one.  But that means that you need $2^{127}$ attempts—about $1.7 \times 10^{38}$, an astronomically large number—to have a 50% chance of success.


Since it sounds a lot like homework, I will only give a hint, not the actual answer.

First, you don't want to mess with $e$, since you can not be sure that a different $e$ is actually a valid exponent ($e$ has to be coprime to $\phi(n)$, which contains at least $2$ as prime factor).
RSA is not IND-CCA. The same attack that works against IND-CCA also works against this.
This attack utilized the homomorphic property of RSA. If you decrypt $c=(ab)^e=a^eb^e$, you get back $m=ab$

edit: textbook-RSA is not IND-CPA either, but the according security game is trivial for the attacker, since the encryption is deterministic. That doesn't help in this case.


How is biometric data used to generate encryption keys?

We do not know how to extract a cryptographically secure key $K\in\{0,1\}^k$ for traditional symmetric encryption from biometric data $b$ such as fingerprints, by way of a function $F(b)\mapsto K$. As noted in the question, problem is that when the biometric data is re-acquired, the naturally occurring $b'$ will be slightly different from $b$ and we'll have $F(b)\ne F(b')$ unacceptably often, for about uniform $K$ of cryptographic interest (e.g. $k\ge80$ bits). That's including if how $F$ operates (e.g. minutiae extraction) is carefully tailored to the characteristics of the biometric data [#].

Allowing $F(b')$ used for decryption to generate several guesses of $K$ (with the right one sorted out thanks to authenticated encryption) does not seem enough to get a workable system.

What does work is extracting a secure sketch as $S(b)\mapsto s$ so that

for naturally occurring variations $b'$ of $b$, with high likelihood, the same key $K\in\{0,1\}^k$ can be extracted from $(b,s)$ and $(b',s)$ (and some public nonce $n$ if we want multiple $K$), using a function $F(b,s)$ or $F(b,s,n)$
$s$ can be published without compromising the confidentiality of $K$ or/and $b$; including if $s'=S(b')$ gets published for several naturally occurring variations $b'$ of $b$.

A search for articles on secure sketch returns a lot of bibliography.

However the interest of biometric data as encryption key is dubious: biometric data, in particular fingerprint, is hard to keep secret, which is the primary attribute desired for an encryption key. Using fingerprints as a means of identification makes much more sense.

[#] Note: all claims to the contrary that I met fall into at least one of these pitfalls:

the error rate is unacceptable, like for >5% of a population, an attempt to obtain the same $K$ a day after fails, even will allowance of two retries;
some ancillary data (similar to $s$ above) is required along $K$ or stored in the scanning device (thus in the later case the number of users is limited, replacement of a failed single scanning device cause disruption, and multiple scanning devices must communicate in order to produce the same $K$);
$K$ has very low entropy (say <40 bits), making it vulnerable to better-than-brute-force key search, and even conceivable that two users accidentally end up with the same $K$ if nothing but their biometrics is an input;
some part of the method must remain secret, and is how the previous issue is masked.


If you're really interested in practical problems and want to know what people care about when actually deploying crypto in practice, then you can start by e.g. reading through the messages of the IETF Crypto Forum Research Group mailing list. The discussions cover mostly crypto standards, which means that it's as practical as it can get. Archived discussions can be found here:

http://dir.gmane.org/gmane.ietf.irtf.cfrg

You won't find any homework problems there, but you can find discussions that will lead up to future standards.


Can I update sha-256 digest chunk-wise instead of the whole array at once?

TL;DR: As long as the concatenation of all the binary input to the update / final operations, in order is identical then the secure hash function should return the same output hash.

The hash function implementations generally have a buffer the size of the block size. This internal block size is generally hidden to the user. For SHA-256 the block size is 512 bits, 64 bytes or - as SHA-256 is build using 32-bit operations - sixteen 32-bit words.

So what happens is that during update the buffer is filled until it is full, which is then processed by the internal compression function, altering the internal state. Then the buffer is filled again and again until all the blocks have been processed. The last part of the update will leave the buffer empty or partially filled. When a new update is processed the whole situation is repeated, starting with the values in the buffer from the last update (if any).

When the final is called then the input data for the final operation is processed as if it was an update. Then the internal bit padding (a one bit followed by X zero bits) takes place and the encoding of the total length is added. This forms the last one or two blocks which are then processed in order.

So with the description above, it is clear that passing the whole array at once produce the same hash as passing it's chunks one by one. This is because the the same buffers will be processed and the internal state will therefore be updated in exactly the same way. The required padding and total length is the same as well. That's all the input to the block operations within SHA-2 so the final output must be identical too.

If you get a different result then you may have run into encoding issues. SHA-2 processes binary data: bits or - for most implementations - bytes. If you perform a different encoding on a string (e.g. UTF-8 vs UTF-8 with Byte Order Mark) then the input will differ and the hash result will differ as well. In principle, the implementation could be faulty as well, but usually this is not the case; there aren't all that many input variants / edge cases to test and test vectors exist.

Notes:

It depends on the implementation if the final operation can contain input data or not. If it does it is identical to having an additional update with the given data and then performing the final operation with the padding and length encoding.
SHA-224 uses the same block size / 32-bit operations as SHA-256; SHA-512 uses 1024 bit blocks and 64-bit operations internally, and so does SHA-384 and the less common SHA-512/224 and SHA-512/256 hash functions.
SHA-3 uses a different internal scheme (a construction using a sponge instead of a Merkle-Damgard construction) but the description of the buffering and block size is still valid.


Why does the following SIS-based decision language not make sense?

This is equivalent to an LWE language.

More specifically, if A is non-singular, write it as $A = [B | C]$ with $C$ is square and invertible mod q, and set $A' = C^{-1} A = [B' | I]$. Then $C^{-1} u = A' x = B' x_1 + x_2$ where $x = (x_1,x_2)$ is small. Relabel $s=x_1$ and $e=x_2$.


Diffie-Hellman: difficulty of computing $g^{x^2}$ given $g^x$?

Let's call the problem Square Diffie-Hellman (SDH).
SDH is at least as hard as CDH in groups of known order and the reduction goes as follows.$^*$ Given an adversary $\mathsf{A}$ that breaks SDH, our goal is to construct an adversary $\mathsf{A}'$ that breaks CDH. Given the CDH challenge $(g,g^x,g^y)$, $\mathsf{A}'$ runs $\mathsf{A}$ thrice -- first on $(g,g^x)$, then on $(g,g^y)$ and finally on $(g,g^{x+y}=g^xg^y)$ -- to obtain $X=g^{x^2}$, $Y=g^{y^2}$ and $Z=g^{(x+y)^2}$, respectively. Now $\mathsf{A}'$ can extract the solution to CDH, i.e., $g^{xy}$, by computing $(Z/XY)^{1/2}$. The correctness of the solution can be argued using the identity $(x+y)^2=x^2+y^2+2xy$.
Note that the ability to compute a square root is crucial for the reduction to go through. Therefore the reduction above holds only for prime-order groups or any group of known order. (I am not aware of a reduction from CDH to SDH for groups of unknown order.)
As @poncho points out in the comment, this means that SDH is equivalent to CDH since the reduction in the other direction is straightforward as described next. Given an adversary $\mathsf{A}$ that breaks CDH, we construct an adversary $\mathsf{A}'$ that breaks SDH works. On input the SDH challenge $(g,g^x)$, $\mathsf{A}'$ computes $(g,g^x,(g^x)^r)$ for a random $r$ and sends it to CDH adversary $\mathsf{A}$. The CDH solver returns $g^{x^2r}$ from which it can retrieve $g^{x^2}$ by computing the $r$-th root.
$^*$ This is an example where we know a Turing reduction but not a Karp reduction.


Computational Assumption For the extended discrete logarithm

Let $\mathbb{G}$ be a (multiplicatively written) group of order $q$ and let $g$ be a generator of $\mathbb{G}$. The $r$-SDH assumption (Strong Diffie-Hellman) [BB08] states that given
$$
g,g^x, g^{x^2}, \dots, g^{x^r}
$$
as input, it is hard to compute a pair $(a, g^{1/(x+a)})$ for some $a \in \mathbb{Z}_q$.

Writing group $\mathbb{G}$ additively and letting $P$ be a generator of $\mathbb{G}$, the $r$-SDH assumption is: Given
$$
P, sP, s^2P, \dots, s^rP
$$
as input, it is hard to compute a pair $(a, 1/(s+a)P)$ for some $a \in \mathbb{Z}_q$.

Your assumption is related to the $1$-SDH assumption in a cyclic subgroup of points on an elliptic curve over a finite field.  It is however weaker as the attacker is given the value of $a$ (in the SDH assumption, the attacker is free to choose the value of $a$).

[BB08] D. Boneh and X. Boyen, Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups, Journal of Cryptology, 21(2), pp. 149-177, 2008.


Why does error propagation in CBC mode encryption affect two blocks?

Encryption process in CBC mode is performed as
\begin{align}
C_1 &= Enc_k(P_1 \oplus IV)\\
C_i &= Enc_k(P_i \oplus C_{i-1}),\;\; 1 < i \leq nb,
\end{align}
where $nb$ is the number of blocks.

CBC is designed for chaining, therefore while encryption, if there is one block error at position $i$, it will affect the rest of ciphertext. This also can be seen from below if write the equation of encryption of $j$-th block.

$$C_j = Enc_k(P_j \oplus Enc_k(P_{j-1} \oplus \cdots Enc_k(P_1 \oplus IV)\cdots)).$$ If $i < j$  then the $j$-th plaintext block will be affected.

However, while decryption of the ciphertext, that is encryption of the plaintext that contains the errored block, you will get only one block with error, the errored plaintext block. Or simply, you will get what you encrypted if there is no error/corruption on the ciphertext blocks.

Note: if there is an error on one of the ciphertext blocks, it can affect one or two plaintext blocks depending on the index of the ciphertext block. One block if the last ciphertext block is corrupted, two blocks otherwise, see bit flipping attack to visiualize. The question is on the error on the plaintext.


PBKDF2 is an acronym for Password Based Key Derivation Function, #2. As you already have a key you need a Key Based Key Derivation Function or KBKDF instead. Currently the most up to date one is probably HKDF, which was - very quickly - also recognized by NIST. There are other KDF's such as KDF1 and KDF2 which are easier to construct (not many libraries contain KBKDF's by default).

You don't require Diffie-Hellman if you already have a shared secret, unless you also require Forward Secrecy.

What you can do is store device keys on the device, send over some device ID to the server that uses that to calculate the device keys from a master key. That way, if one device is compromised, you don't loose the master key (the device is fitted with the device key upon creation using the same algorithm).

Similarly you can use a key derivation from the device key using some unique session based information or large enough random to establish session keys. I would create 2 to 3 session keys:

for explicit authentication using a MAC (you don't want to use your secure channel for implicit authentication - trust me on this)
for encryption of the secure channel
for authentication of the secure channel (unless you use one key for encryption and authentication as in GCM)

It's best to use different session keys for client and server (e.g. by reordering the client ID and server ID) otherwise you may run into nonce reuse, replay attacks etc.

Note that the authentication data used for explicit authentication should contain as much data as possible, including one or more randoms, client ID, server ID and something to identify the session with.

So basically you don't require asymmetric primitives for such a scheme, although you may gain additional benefits from it. Forward secrecy is one, but you might also want to achieve anonymity to name just one other (I presume this is less important for your use case though).


Is there an easy way to recover $p$ and $q$?

Yes (in all cases except for $B, D$ are both multiples of $N$, or $k=0$, and assuming that $p, q$ are distinct primes)
Let us assume that $B$ is not a multiple of $N=pq$; then:

If $B$ is not a multiple of $p$, then $\gcd(A, N) = q$ (because $A=Bq^k$ is a multiple of $q$ but not $p$); simple division also recovers $p$

If $B$ is a multiple of $p$, then it is not a multiple of $q$ (by assumption); in that case $\gcd(B, N) = p$


A substitution based on a matrix vector product

We call an operation F linear if the following holds:

$F(X+Y) = F(X) + F(Y)$

for all $X, Y$ within the appropriate set, and for some group operator $+$.

Now, if we consider matrix multiplication by a fixed matrix $A$, we do have the identity:

$A \cdot (X+Y) = A \cdot X + A \cdot Y$

for arbitrary vectors $X$, $Y$, and where $+$ is vector addition.  Hence, matrix multiplication by any fixed matrix $A$ is linear.

When you are designing a block cipher, it is critically important that, for any group operator $+$, there be some component that is nonlinear with respect to that operator.  Hence, matrix multiplication is probably not an ideal selection.

You appear to have some understanding of this; so what are you confused about?


Difference entity authentication and implicit key authentication

In entity authentication, the parties do not necessarily exchange a session key, but authenticate to each other by providing some proof related to their identites. For instance, if one party signs a challenge given by its partner, this party proves its identity.

Implicit key authentication merely guarantees that the partner (with whom you are talking right now, but who could be unidentified) is holding the same key, and no one else is.

Example:

A chooses random $x$ and sends $g^x$ to B.
B chooses random $y$ and sends $g^y$ to A.

Only A and B can know $g^{ab}$, but they do not authenticate to each other. Hence, the protocol provides implicit key authentication but no entity authentication. The above protocol is actually not secure against man-in-the-middle attacks; it merely serves as an separation example.


How does the birthday paradox apply to random keys?

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.

Yes, this is correct.  If you have $n$ (randomly chosen) valid keys out of $N$ total, then the probability of a single key being valid is $p = n/N$, and so the average number of keys one needs to test to find a single valid one is $1/p = N/n$.

Where the birthday paradox comes into play is in key generation.  Specifically, if you have a total of $N$ possible keys, and you independently and randomly pick $n$ of these possible keys to be valid, then there's a risk that some of the keys you pick will be identical.  In particular, the expected average number of duplicate pairs will be $(n^2-n)/(2N)$.  (This is also an upper bound on the probability of there being at least one duplicate; this upper bound is a good approximation of the true probability whenever it is much less than one, i.e. when $n \ll \sqrt N$.)

What this means, in practice, is that if the number of valid keys $n$ is much less (say, less than one thousandth of) the square root of the total keyspace size $N$, then you probably don't need to worry about collisions in key generation at all, since the probability of having even a single collision is less than one in a million.  Once the $n$ gets closer to $\sqrt N$, though, collisions become likely, and you will need to implement a mechanism for dealing with them.

(If you have a centralized database, dealing with collisions is pretty trivial; just pick a new random key and repeat.  This is very efficient unless your keyspace is almost full (say, $n > N/2$), in which case you have bigger problems than slow key generation anyway.  In some crypto schemes, however, one needs to avoid collisions without using any kind of central key database.  In this case, the only possible solution is to increase the keyspace size far above the square of the highest foreseeable number of valid keys, so that having even a single collision becomes extremely unlikely.)


The role of IV when AES is used as $PRF$

AES does not itself have a concept of ‘initialization vector’—initialization vectors are basically an artifact of ciphers for long messages built out of fixed-size components.  AES is just a keyed family of permutations of 128-bit strings.

You can use the AES permutation as such as you described—with the caveat that you should use AES-192 or AES-256 if you want a standard ‘128-bit security level’.  Of course, then you need a 256-bit key which you can't get by a single invocation of AES  One way you can use AES-256 to generate 256-bit keys is to alternate between even and odd inputs: derive the $i^{\mathit{th}}$ subkey $k_i$ from the master key $k$ by $$k_i = \operatorname{AES256}_k(2i) \mathbin\| \operatorname{AES256}_k(2i + 1).$$  You'll never get a key that consists of the same 128 bits repeated twice, but the probability of that was negligible anyway; the standard PRF/PRP switching lemma provides bounds on the probability of a problem from this.  Essentially this structure is used by, e.g., AES-GCM-SIV (or at least the last incarnation of it that I saw).  However, there's another couple of caveats about AES:

In software, changing AES keys is expensive.
In software, there is a conflict between fast AES implementations and secure AES implementations that don't leak secrets through timing side channels.

Systems like AES-GCM-SIV were designed under the premise that you can actually audit your software stack all the way down to the assembly code to guarantee that you're actually getting hardware AES support.  There's a much simpler, safer, and more confidence-inspiring way to do it, which doesn't even involve a PRF/PRP switching cost: use a PRF designed for security in fast software like ChaCha instead.


This is a very difficult question. But first the standard information:

Don't roll your own crypto if anyhow possible. (which isn't the case here)
No protocol should be considered secure until formally proven secure. (TLSv1.2 is)

That being said I can still provide "ad-hoc" security argumentations why it's likely that your handshake is (in)secure.I can't prove protocols secure. For this need you have to consult special companies or cryptographers who have actually published such proofs.

If a protocol downgrade (which is trivial here) doesn't hurt you you should be safe.
Your encryption key currently is $EK=KDF(KDF(MS||SHA_{256}(MS||Ver||Rand))||Rand)$. I think that just deriving this key like $EK=KDF(MS||Rand)$ is equally secure and a bit faster and you can expand it to $(EK||AK)=KDF(MS||Rand)$ with $AK$ being the authentication key.
The generation of the session ID like this is a nice idea to authenticate the random value at the same time (maybe using the suggestion below).
I'm not fully sure what you mean by this question. But the Rand value is essential to be different each time to get different session keys (what your protocol tries to achieve), so hardcoding them would be a very bad idea.

Some other notes:

You mentioned HMAC for authentication. Please use a standard AEAD construction (->GCM,EAX,...) if anyhow possible.
You may want to consider, if sending the SessionID, that you check the SessionID on the client side, as it is an "authentication tag"
You may also want to consider using a different IV/Nonce for each message and exclude it from the handshake as it doesn't seem to provide any purpose. However, after the handshake it's an interesting idea to exchange random messages to check the key exchange worked.
You may further want to consider replacing the SHA-256(MS||Ver||Rand) by $HMAC_{MS}(Ver||Rand)$ and thus "authenticate" the random value and the version to defend against tampering, this means you also need to actually transmit the tag (which you were already doing).
You may want to consider using a TLS-PSK cipher suite, like TLS_PSK_WITH_AES_256_GCM_SHA384, but then you'd loose the session key property of having different keys as all session keys will be equal (somewhat defeating the purpose of your protocol), but you could use the "other_secret" field to insert some random negotiated data (using your above protocol) and be confident that you use "fully" TLSv1.2 and have key-freshness.


Is K=1 a valid random integer in ElGamal signature?

Why $K=1$ is not excluded? You can also ask why $K=2$ is not excluded. It always possible to calculate $g^2$ and by keeping $(g^2,2)$ in a lookup table, you can also recover the secret key if you see $S_1 = g^2$, in which case $K$ happen to be 2. So as $K =3$, $K= 4$ and so on so forth. As you can see, 1 is not that special.

The reason why they are not excluded is because that $K$ is chosen at uniformly random from the range. For an adversary who has only limited computational capacity, it can only guess polynomial number of $K$ and does the computation, but if the signer picks his $K$ at uniformly random, the probability of the adversary guessing the right $K$ is negligible. So as long as the signer does his job properly, we don't need to worry about $K$ being a specific value.


The danger of Hash collision in Schnorr NIZK

First, I do not think reversing the hash function will help you disclose skey as nothing in the Hash needs to be private. The Hash in Schnorr NIZK is a practical instantiation of the random oracle, not perfectly though. Here the random oracle is used to commit or sign V, so that you can not choose V based on c. Note that it is trivial to get V given y, c, g, r, and pass the verification $Vy^c = g^r$.

As for the danger of collisions, it may not be very relevant to the security proof. Hash functions are just how we implement random oracles in practice. I think a better way to look at this is as follows. If one can forge a proof, then c should be equal to the output of the random oracle with input (g, V, pkey, ...). This happens with small probability, as a random oracle always outputs a purely random value given a new input.


Is there a hash tree scheme designed for complex data structures?

The general technique for tree hashing (independently of the issue of partially revealing content) is to define the hash of nodes as the hash of the concatenation of the hash of their leaves, with a suffix (or prefix) that makes the input of the hash different for leaves and nodes. Demonstrably, this inherits from the cryptographic hash it's properties of collision-resistance, preimage-resistance, and security in the Random Oracle Model. Proof is left as an exercise to the reader.

The devil is in the details, in particular in

defining a canonical form of things that must have identical hashes;
defining if the order of leaves matters;
if nodes are typed or/and named beyond being a leaf or not (in which case that type/name extension must be hashed);
making sure that the format of the input of hashes used for such extensions can not lead to collision (perhaps deliberately).

I know no ready-made hash standard for JSON, aka ECMA-404. I hereby semi-seriously propose to pick a cryptographic hash such as SHA-512, and define SHA-512-JSON-V1 as:

The hash of a JSON array is the hash of the concatenation of the hash(es) of its value(s), ordered as they occur in the array; and a final octet 41h (ASCII A).
The hash of a JSON object is the hash of the concatenation of an even number of hashe(s), with the first hash of a pair the hash of the name of a member of the object, and the second the hash of the corresponding value, with the pair(s) ordered in lexicographic order of the concatenation of the two hashes of that pair; and a final octet 4Fh (ASCII O).
The hash of any other JSON value (that is string including a name, number, the special values true, false, null, and anything else not defined by ECMA-404) is the hash of the concatenation of their UTF8 character representation (excluding leading and ending " for strings that came with that, and with conversion to lowercase for the three special values); and a final octet

53h (ASCII S) for string including name
4Eh (ASCII N) for number
56h (ASCII V) for yet other value.

Notes on object:

Order of leaves never matters to the hash, since (quoting ECMA-404)

  JSON syntax (..) does not assign any significance to the ordering of name/value pairs

Case matters including in names. Doing otherwise would be a nightmare with unicode, unless we restricted case normalization to ASCII letters.
Multiple occurrences of the same name in the leaves of an object can be tolerated (as in ECMA-404), or not, without changing the hashing scheme.
Update per comment: the proposal orders the pairs of hashes (one per per name:value pair in an object) per the concatenation of the two hashes (one for name, the other for value). That ensures the hash result is identical regardless of the order of nodes. If we ordered per the hash of the name only, or per the name, this would not be insured for multiple occurrences of the same name in an object (which is possible, see above bullet). Further, ordering directly per what's hashed allows to substitute ordering with any order-independent hash, enabling a sizable optimization for large objects; see last section of this answer.

Notes on coding of value:

UTF8 has the advantage that it is compact, endian-neutral, and assigns each unicode point a single representation as octet string (including if it has no UTF-16 representation).
For example, the hash of JSON's "4\u00e9\u144E\uD834\uDD1E" (the four-character string "4éᑎ" , with the last character represented by the last two hexadecimal escape sequences), is the hash of the 11 octets
  34h C3h A9h E1h 91h 8Eh F0h 9Dh 84h 9Eh 53h
with 1 (resp. 2, 3, 4 and 1) octet(s) for the first character (resp. second character, third character, fourth character, and suffix octet).
The question uses a JSON relaxation in which a string used as the name of a field needs not be quoted. It is thus intentionally specified that in an object, age: 35, false:0, True:true, 1e0:42,{}:{},[0]:{} (if accepted by a parser) hashes the same as "age":35, "false":0, "True":true, "1e0":42, "{}":{}, "[0]":{} even though some of the derogatory names could otherwise be of type value, number, object, array.
Specifying that special value true is hashed in lowercase leaves unspecified if and where True is valid and its type, but specifies that if it is a special value assimilated to JSON's true, then it must hash as the later does.
More generally, freedom is left for parsing relaxation/extensions: for example, an extra ',' can be allowed before ] or } at the end of an array or object as in the question, or alternatively it can be allowed to omits null after a ','. The hash will follow whatever convention the parser uses.

Notes on coding of number:

As is, numbers that are equal (in some sense unspecified by JSON) can still have different hashes. For example zero can be (among an infinity of possibilites)
  0   -0   0.0   0e0   0E0   0e+0   0e-0   0e00314
If we wanted to fix this, there are choices to be made, and they are not easy. For a C compiler, 0.0 and 0 are not the same. For an experimental physicist, 1.2e4 and 1.20e4 are not the same.

Note: It is used a suffix rather than a prefix because that nicely aligns data for object and array, especially for hash algorithms which internal data block size is twice the output size, such as SHA-512.

Efficiency: SHA-512-JSON-V1 allow computation of the hash of any JSON of length $n$ in time $\mathcal O(n\log n)$. The $\log n$ term is only due to sorting of the hashes of a large object. We could get rid of this term, and often considerably reduce the memory used, with the technique in the second section of this answer, which outlines how to make an order-independent hash with an online algorithm using constant memory beyond input. We leave this for future extension!


How to hide bit frequency of the inter-packet delays covert channel?

With Steganography, we take a short message, and embed that into a much larger signal, with the goal being that someone seeing the larger signal cannot tell that there's the embedded message.  Now, this larger signal (which might be JPEG, a handwritten message, or in your case, interpacket delays) has a natural distribution; one way of viewing the goal of Steganography is that we want to generate an artificial signal; we pick it in such a way to mimic the natural distribution (so that someone cannot tell that we picked it artificially), however the precise signal we did pick encodes the message we want.

Usually, we do Steganography by taking a real signal, and tweaking it slightly to form the artificial signal.  The hope is that the tweaks do not move the signal significantly out of the natural distribution (at least, not enough to be detectable).  This means that we don't have to understand the entire natural distribution (e.g. if we were embedding our messages into JPEG files, which files would look plausible and which wouldn't); instead, we just need to understand it well enough to know which tweaks don't disrupt the distribution detectably.

However, that's not what you're doing.  You don't have a real signal (that is, there is no original interpacket delay source); you are individually crafting the interpacket delays yourself.  In that case, you really need to answer the question "what does the natural distribution look like"; that is, what do real interpacket delays look like?

Well, we could guess what these delays might look like (perhaps approximately normal distributed with a certain mean and standard deviation), however if you are serious about this, you will need to actually select a real packet source, and measure the delays.  This is more subtle than just measuring the distribution of delays; it also involves (at least) looking at the short term correlations between delays.

Once you have a reasonable model of the probability distribution of a real source, it should not be difficult to craft a way of selecting an element from that distribution.  However, until you have such a model, you really don't have much hope of fooling an intelligent evesdropper who is actively looking for a signal.


Question on Simplest Oblivious Transfer Protocol

As you have said, let's say the receiver chooses $c = 1$. Then his $B = Ag^b$. So In Alice's case, the $k_0 = H(B^a) = H((Ag^b)^a) = H(g^{a a} g^{a  b}) = H(g^{a a + a b})$. Similarly, $k_1 = H((\frac{B}{A})^a) = H(g^{ab})$. Receiver's own key $k_R$ is also, $H(A^b) = H(g^{ab})$. So you see, his key is similar to the senders key $k_1$. That is why, even though the sender is sending both encryptions, the receiver can only decrypt one of these. The one for which the keys are the same, i.e. message 1!


Homomorphic/Paillier crypto system for use case?: overflow for multiple counter exponent possible? Different cipher factor needed all the time?

It won't work anyways because even in case it would be secure with one $r$ and the exponent can get overflow for each candidate the ciphertext with same exponent will be different after an overflow happened.

  Do you really mean deterministic (that is, one particular m always maps to the same c)

Given two ciphertext with same exponent ($\mod n$) before and after overflow. The 2nd would be result after adding $n$ times one vote to first.
$c_0 = g^0 \cdot r^n \mod n^2$
$c_{i+1} = c_i \cdot c_{add+1} = c_i \cdot g^1 \cdot r^n = g^i \cdot r^{in+n}$
$c_a=g^a \cdot r^{an+n} \not=g^{a+n} \cdot r^{an+n^2+n}=c_{a+n}$ $\mod n^2$
(because $r^{\phi(n^2)}=1$ and $n^2 \not = \phi(n^2)$  )
Decryption resolve in same $a$ but exponent of $r$ is different and with this those two ciphertexts.


No, you can divide and distribute, but if you do anything else (such as filtering for candidates) then it would not officially be a brute force attack anymore. You will have to iterate over the full key space one way or another.

With DES I guess it is acceptable to forget about parity while iterating over the key space, only effective key bits have to be traversed.

Finally, there may be specific methods required to filter out possible candidates if it isn't a known plaintext attack (which is however assumed in the question).


Is obfuscation considered a cryptographic primitive?

I don't think this can be answered with facts or definitions - so this answer is just my opinion:

If you have a specific obfuscation with some cryptographic security property in mind, e.g. IO, and use it to build something else: Then yes, it is. If you just use it as a general term to describe something possibly non-cryptographic (code obfuscation, etc.), then it isn't.

Generally, I think the word obfuscation alone is underspecified. So the first counter-question probably should be: What do you mean? At least in the context of cryptography, definitions matter a lot. And if in doubt: Assume the 'wrong' meaning and say "No, it isn't".


Confusing XOR notation in textbook sample solution

The notation $c=\oplus~c_i$ is (terrible) shorthand for $$c=\bigoplus_{i \in I(c)} c_i$$ where the sum sign should be replaced by the big xor sign which could also be written as $$ c=\sum_{i \in I(c)} c_i,$$where $\sum$ denotes vector addition modulo 2.

An example of this decomposition (for length 8 vectors) is
$$c=(1,0,1,0,0,0,1,0)=$$
which is nonzero in positions 1,3, and 7, and satisfies
$$c=(1,0,0,0,0,0,0,0)\oplus(0,0,1,0,0,0,0,0)\oplus(0,0,0,0,0,0,1,0)$$
$$=c_1\oplus c_3 \oplus c_7=\bigoplus_{i \in I(c)} c_i$$ where $I(c)=\{1,3,7\}.$

Then, since $E$ is assumed to be linear, all the places you marked with an arrow make sense.


decrypt a saml 2.0 response having aes 128 and rsa

For a definitive answer, you really should see the documentation for the data format you're dealing with, but just quickly looking at the XML response, it would seem that you're dealing with a hybrid encryption scheme.

That is, your encrypted message consists of two parts:

The actual data (in xenc:EncryptedData), encrypted using AES-CBC with a single-use per-message key.
The AES key used to encrypt the data, itself encrypted (in xenc:EncryptedKey) with RSA-OAEP.

The main reason for using this kind of hybrid encryption, instead of directly encrypting the data directly with RSA, is that public-key encryption algorithms like RSA tend to be rather slow, increase the message length considerably, and generally be poorly suited for encrypting long message.  They work just fine for encrypting AES keys (which are just random bitstrings 16 / 32 bytes long), though.  So we use AES to encrypt the message (which is fast and only adds a few bytes to the message length), and then encrypt the AES key with RSA so that the intended recipient can decrypt it.


Security of this deterministic encryption scheme

Correctly implemented, it should be secure deterministic authenticated encryption. In fact, it is SIV, in the wider sense of using the "SIV construction" as defined in Deterministic Authenticated-Encryption by Rogaway and Shrimpton (except for lacking a header input). The proof of the security of the SIV construction is that:

  We will now show that if $F$ is PRF-secure and $Π$ is IND\$-secure then $SIV[F, Π]$ is DAE-secure.

So in this case AES-CBC must be IND\$-secure and HMAC-SHA256 must be a secure PRF. With those assumptions, the mode as described is a secure deterministic authenticated encryption scheme.

Those are slightly stronger requirements than we usually use. HMAC-SHA256 is normally only required to be a secure MAC. Being a secure PRF implies it, but the converse is not implied. In practice there are other protocols that do rely on its PRF security and we have no indication that it would be insecure.

Caveat: the keys being the same actually invalidates the proof, so in the strict sense it is not proved secure. However, for key reuse between HMAC-SHA256 and AES to be exploitable would be an incredible coincidence.

Now, in practice there are some problems with the use of CBC mode. While it is provably secure, practical implementations have been known to be weak. Most relevant here is the padding oracle attack. There are ways to avoid it, but without looking at the source of the library I do not know if they are used:

Always verifying both padding and MAC in constant time avoids the side channel leak. The error returned must also be the same. This is difficult to ensure.
If the MAC is verified before the padding, the attack is not possible. I.e. the MAC is either over the ciphertext (not the case here) or over the padded message (possible here).
Ciphertext stealing avoids the need for padding. (Not used here.)

On the other hand, the choice of HMAC and CBC does also have some advantages. Namely, it breaks less badly as you get close to the birthday bound:

CMAC is gets insecure after $2^{64}$ invocations, and is recommended to be only used for $2^{48}$ blocks (see SP 800-38B, appendix B).
With CTR an IV (or block input) collision means subsequent blocks also collide. CBC usually only leaks individual, random blocks, which is potentially harder to exploit.


Complexity of solving the discrete logarithm problem for the group formed from product of 2 safe primes

What's that group?

Algebraically, it is isomorphic to the group $\mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} = \mathbb{Z}_{p'} \times \mathbb{Z}_{q'} \times \mathbb{Z}_2 \times \mathbb{Z}_2$.

  Does $\mathbb{Z}_N^*$ guarantee computing discrete logarithm is hard?

It can be shown that it is at least as hard as factoring $N$ (as if you can compute discrete logs, you can factor).

Hence, if factoring $N$ is infeasible, so is computing discrete logs.

  Since $\mathbb{Z}_N^*$ is not a group of a prime order, is there any guarantee $g$ is a generator.

Actually, there is a guarantee that $g$ is not a generator for the entire group; that's because $\mathbb{Z}_N^*$ is not a cyclic group, and hence does not have a generator.

In particular, the subgroup generated by a single value $g$ will never contain both elements $a$ and $b$ where:

$a \bmod p$ is a Quadratic Residue $\bmod p$, and $a \bmod q$ is a Quadratic Nonresidue $\bmod q$
$b \bmod p$ is a Quadratic Nonresidue $\bmod p$, and $b \bmod q$ is a Quadratic Residue $\bmod q$

(Such elements $a$ and $b$ will always exist in $\mathbb{Z}_N^*$)


Simplified universal composability (SUC): can I model the use of encryption? Can I prove fairness?

Since fairness cannot be modeled, does that mean I cannot prove that a voting scheme, for example is fair (that is, that either the protocol finishes execution and everybody learns the result or nobody learns anything)?

In the UC model, fairness is a property of the ideal functionality itself. A "fair functionality" is one that gives output to everybody or to nobody. If a protocol securely realizes a "fair functionality", then you would say that the protocol is "fair."

In SUC you are not even allowed to talk about a fair functionality. All communication from the functionality is inherently "unfair" as part of the underlying communication model. So you are correct, you cannot prove fairness properties in SUC.

  And does the second part of the quotation mean that I cannot model the use of encryption and signatures in whatever protocol I'm using? I doubt that, but the wording used in the article got me a bit confused.

The short answer is, no you are not prevented from using encryption/signatures in your protocols.

The long answer is: we don't typically define security of encryption/signatures using the language of MPC, since these schemes consist of noninteractive algorithms. Yet it is possible to define an ideal functionality $F$ with the following property: "an encryption scheme is CCA secure if and only if that scheme is a secure protocol for $F$ (after translating some syntax appropriately)."

Such a functionality $F$ is really weird compared to typical MPC functionalities. When party $P$ talks to $F$, the response only goes to party $P$, and the adversary gets no notification about this exchange between $P$ and $F$! This models the fact that when $P$ wants to encrypt, he does so inside his head, and doesn't have to talk to anyone (how can an adversary know when I'm encrypting stuff in the privacy of my own brain?).

The SUC model can't handle this kind of functionality. In SUC, when a functionality generates an output for a party, the adversary must always learn the fact that output was produced (maybe he/she doesn't see the contents of the output). So in SUC you can only write a functionality for an interactive "traditional MPC" kind of thing.

So all this is saying is that you can't talk about weird UC functionalities that try to characterize CCA encryption / existentially unforgeable signatures. Again, this is a restriction on the kinds of functionalities you can write in SUC. There is no restriction on the kind of protocol you can write. You can definitely use encryption/signatures in your protocol. In that case, your security proof should then use the standard, game-based definitions of security.


How many possible Enigma machine settings?

Depends on the exact model. Wikipedia is your friend: "Combining three rotors from a set of five, the rotor settings with 26 positions, and the plugboard with ten pairs of letters connected, the military Enigma has 158,962,555,217,826,360,000 (nearly 159 quintillion) different settings."

More in detail: if you consider an Enigma with 3 rotors out of 5 rotors of model known to the cryptanalyst, and a plugboard with 10 wires

the 3 rotors out of 5 can be ordered in ${5!\over(5-3)!}=60$ ways.
for each rotor, the relative position of the wiring to the rest of the rotor can be set to 26 positions; for $26^3=17,576$ combinations.
each of the 20 extremities of the 10 wires can be plugged into any of 26 positions not otherwise occupied, with the two extremities of a given wire equivalent, as well as the 10 wires themselves; for
${26!\over(26-20)!\cdot2^{10}\cdot10!}=150,738,274,937,250$ combinations.

There are thus
$${5!\over(5-3)!}\cdot26^3\cdot{26!\over(26-20)!\cdot2^{10}\cdot10!}=158,962,555,217,826,360,000$$
possible settings, for a definition of that not including the initial rotor position, even though that's not initially known to the cryptanalyst.


Consider the following system involving a message authentication code like HMAC-SHA256:

Alice generates a key and shares it with Bob, and Bob alone.
Alice authenticates a message with the key.
Bob acts on the message only if it can be verified with the key.

Of course, Alice can verify messages too, and Bob can forge messages too.  Indeed, anyone who has the key can verify or forge messages: the key necessarily grants the power to do both.  Consequently, Alice can't present a cryptographic proof to a third party that a message came from Bob, because Alice could have forged the message; and vice versa.  Thus this system has ‘deniability’, or lacks third-party verifiability.

Consider the following system involving a digital signature scheme like RSASSA-PSS or Ed25519:

Alice generates a key pair and shares the public key with Bob, and Bob alone.
Alice signs a message with her private key.
Bob acts on the message only if it can be verified with Alice's public key.

Only Alice can sign messages; anyone with the public key can verify them but not sign them.  You asked that only Bob be able to verify messages.  Can the public key be kept secret so that Bob alone can verify them?

The standard for signature security is existential unforgeability under adaptive chosen-message attack, or EUF-CMA, which means that an adversary who can query an oracle for the signature of any message of their choice nevertheless can't forge a signature for any message they didn't query the oracle for.  Nothing prevents an EUF-CMA signature scheme from simply including a copy of the public key in the signature itself, so that won't keep Alice's public key secret.

There's a nonstandard property of some public-key cryptosystems called key privacy—formalized for public-key encryption schemes, it means that given two public keys and a ciphertext the adversary can't tell which public key the ciphertext corresponds to.  Of course, this doesn't carry over naturally to signatures because if you had the public keys and message you could just verify the signature.

There's a related notion of anonymous signature schemes, where an adversary presented with two public keys and a signature but not the message can't tell which public key made it, which typical RSA-based signature schemes fail by the German tank problem to the chagrin of the Australian Department of Human Services who hoped it provided privacy it didn't.  Schnorr-type signature schemes in a standard group like Ed25519 do tend to provide anonymity in this sense.

There's another related notion of key indistinguishability (paywall-free) where an adversary presented with two public keys and a signing oracle can't tell whether the public keys have the same private key, but this is in an exotic context where a set of many users can sign messages with their respective private keys, but only one party can distinguish signatures made by the users.

Which of these do you want?  I don't know—it's not clear to me what you're trying to accomplish at a higher level, so it's hard to give more specific advice.


Why AEAD instead of encrypting with a simple hash?

So suppose we define our encryption scheme as follows:
$E(K, M) = \operatorname{CTR}(K, M || H(M))$,
where $H$ is a hash function (e.g., SHA2-256), and $\text{CTR}$ is the counter mode-of-operation of some underlying blockcipher (e.g., AES-128). Now suppose we observe the ciphertext $C = C_M || C_T $ of a known message $M$ and want to modify some bits in $C$ so that it decrypts to some other message $M'$. Here $C_M$ denotes the part of the ciphertext which contains the encrypted part of the message itself, while $C_T$ contains the encrypted part of the hash of the message. In more detail:
$C = \overbrace{10000110100011}^{C_M} || \overbrace{1100010}^{C_T}\\
\phantom{C} = \overbrace{00100011110010}^{M} || \overbrace{0010100}^{T = H(M)} \\
\hspace{3.5cm} \oplus \\
\phantom{C =}\ \underbrace{10100101010001 || 1110110}_{\text{CTR keystream}}$
For simplicity, suppose we want to create $M'$ by flipping bits 1, 3, and 13 in the original message $M$. First we start by simply flipping bits 1, 3, and 13 in $C_M$. This gives
$C' = \overbrace{\color{red}{0}0\color{red}{1}001101000\color{red}{0}1}^{C_{M'}} || \overbrace{1100010}^{C_T}$
When the $C_M'$-part is decrypted, this will yield $M'$ due the properties of the CTR mode-of-operation:
$\overbrace{\color{red}{0}0\color{red}{1}001101000\color{red}{0}1}^{C_{M'}}\\
\hspace{1.5cm} \oplus \\
10100101010001 \dots \quad (\text{CTR keystream})\\
\color{red}{1}0\color{red}{0}000111100\color{red}{0}0 \quad = M'$
However, now the hash won't match anymore. So we also need to modify $C_T$ into $C_{T'}$ such that when $C_{T'}$ is decrypted it yields $T' = H(M')$, i.e., the correct hash of our modified message $M'$. But this is easy since we know $M$ and $C_T$: first compute $T' = H(M')$ and suppose $T$ and $T'$ differs in bits, say, 2, 3, and 7, i.e. $T' = H(M') = 0\color{red}{10}010\color{red}{1}$. Now we simply flip bits 2,3, and 7 in $C_T$ to get $C_{T'}$, and this will decrypt to $T'$. Thus our full ciphertext is:
$C' = C_{M'} || C_{T'}$,
which when decrypted yields:
$C' \oplus \text{CTR keystream} = M' || T' = M' || H(M')$.
Note that this attack won't work as-is on another mode-of-operation which doesn't provide integrity. However, analogous attacks are usually easy to come up with. For example, see here for the analogous attack on CBC-mode.
In conclusion: your suggested scheme, albeit natural, fails to provide integrity. That is why modes like GCM, CCM, and EAX exist.


How the FHE encrypts a k-bit message just with one-bit encryption scheme?

One-bit FHE schemes, as you call them, are actually sufficient to implement a full adder.

You just have to encrypt each bit of the messages, then use the homomorphic logic gates to execute the circuit that you want.

For instance, if you have 2-bit messages $a = (a_0, a_1)$ and $b = (b_0, b_1)$, just encrypt the four bits, obtaining $c_{a, i}$ and $c_{b, i}$ (for $i = 1, 2$), use the homomorphic logic xor gate to add two bits and logical and gate to obtain the carry, that is, representing XOR by + and AND by $\cdot$, we have

First bit of the result: $r_0 := c_{a,0} + c_{b,0}$ (thus, $r_0 $ encrypts $a_0$ XOR $b_0$)

First carry: $c_0 := c_{a,0} \cdot c_{b,0}$

Then, second bit of the result: $r_1 := c_{a,1} + c_{b,1} + c_0$.

Second carry: $c_1 := (c_{a,1} \cdot c_{b,1}) + (c_{a,1} \cdot c_0) + (c_{b,1} \cdot c_0)$

Third bit of the result: $r_2 := c_1$ (just use the last carry as the most-significant bit)

Therefore, the resulting message is $(r_0, r_1, r_2)$.

You may want to check the TFHE project. They implement several circuits homomorphically (in particular, in the tutorial that link, you can run a circuit that computes the maximum of two values).


Using raw encrypted network data for randomness

For Linux at least, the randomness that goes into /dev/urandom is already taken from the network. The difference between its scheme and yours is that it takes timing data instead of raw encrypted data. The reason for this is that timing data becomes harder to predict as you get farther away from the target, whereas raw traffic contents can be recorded trivially at any point in the path. This timing data comes from nanosecond timestamps of interrupts sent by the network interface device (NIC).
Taken from another answer I posted on another Stack Exchange site:

In modern hardware, an interrupt is a signal emitted by hardware to alert the CPU to a status change. It allows the CPU to avoid rapidly polling every hardware device for updates and instead trust that the device will asynchronously alert it when the time comes. When an interrupt occurs, an interrupt handler is called to process the signal. It turns out this handler is the perfect place to get randomness! When you measure the nanosecond-level timing of interrupts, you can quickly get a fair bit of randomness. This is because interrupts are triggered for all sorts of things, from packets arriving on the NIC to data being read from a hard drive. Some of these interrupt sources are highly non-deterministic, like a hard drive which relies on the physical motion of an actuator.

One caveat is interrupt coalescing, a feature supported by many modern NICs that batch interrupts to reduce per-packet overhead, rather than sending a separate interrupt for each received or transmitted packet. Depending on how it is implemented (count-based or timeout-based), it can potentially reduce the amount of entropy that can be gathered by the NIC. However, most NICs let you disable it.


How many passwords are possible in this scenario?

for one 1 char passwords, one can only put $26$ different characters
for one 2 char passwords, one can only put  $26^2$ different characters
for one 3 char passwords, one can only put  $26^3$ different characters
...
for one 8 char passwords, one can only put $26^8$ different characters

In short, think each box can contain how many letters from the given alphabet and multiply the values in the boxes. Finally, sum them.
$$\sum_{i=1}^8 26^i = \frac{26^9-1}{26-1}-1$$
The name of the formula is Sum of Consecutive powers of a number;
$$\sum_{i=0}^n a^i = \dfrac{a^{n+1} -1}{a-1}$$
and $-1$ since $i=0$ is not a case here.

Update : a more general case;
Let assume that you want to build a web application and want to determine the security level of the passwords. Here a calculator;

Assume that the alphabet has $l$ letters,
$m$ numerals, and
$p$ non-alphanumeric.

If we set the passwords to require at least;

$n_m$ numerals
$n_p$ non-alphanumeric,with
passords's length to $$min \geq n_k+n_a \geq 6,\text{and}$$
$max > min$, then

What is the password space, $\mathcal{S}$?
$$ \mathcal{S} =  m^{n_m} + p^{n_p} + \sum_{i=1}^{max - ({n_m} + {n_p})} (l+m+p)^i$$
Under these assumptions, let

$l = 26$

$m = 10$

$p = 20$

$min = 6$

$max=20$

$n_m=2$

$n_p =1$, then we have;
$$ \mathcal{S}_{6:20} =  10^2 + 20 + \sum_{i=1}^{17} (56)^i = 533361663473057950558105648760 $$

$ \mathcal{S}_{6:20}$ has 99 digits in binary form.
if max is;

$6 \text{ then } S = 178928$
$7 \text{ then } S = 10013424$
$8 \text{ then } S = 10013424$
$9 \text{ then } S = 560745200$
$10\text{ then } S = 31401724656$ is 35-bit.

WolframAlpha calculator;
m^{n_m} + p^{n_p} + sum (l+m+p)^i, i=1 to (max - (n_m + n_p))


Related keys are keys with any mathematical relationship that leads to exploitability in the cipher. This can be a simple relationship, such as having many bits in common. This was the case with RC4 when used in WEP, where each packet is encrypted with a key composed of 104 bits of unchanging key material and 24 bits for an IV, leading to the FMS attack. The relationship might be more subtle, with keys sharing a complex differential relationship, as with the related key boomerang attacks in 256-bit AES.

A trivial example of related keys would be two keys which cause a collision in the cipher's key schedule, resulting in distinct keys having a relationship that allow them to resolve to the same round keys. Full collisions in the key schedule result in equivalent keys, such as with TEA where certain flipped bits in the key cause collisions. Related key attacks often (but not always) are caused by a weakness in the key schedule. A good cipher should not suffer from related key attacks, and all keys should be equally good.

It may be tempting to think that related key attacks don't really matter. After all, any good protocol will have each and every new key completely distinct from each previous key. However, the problem of related key attacks comes up if the cipher primitive is later used in other constructions, such as for a hash function. This was the case with TEA which was abused by Microsoft in the Xbox as a hash. This is an issue because many hash constructions such as Davies–Meyer use each (attacker-controlled) message block as a key. Related keys in the underlying block cipher could then manifest as collisions.

The most severe related key attacks are ones where keys can be related by chance or due to the way they are used in the protocol. It's more common that the relationships are so complex as to be very unlikely to ever arrive by chance and typically need an attacker to influence the choice of keys. As mentioned above, this is typically an issue when a block cipher is used to construct a hash function.


Can the same One-Time-Pad be re-used with some tricks

Based on comments it seems the question asks if this is as secure as OTP as opposed to finding a practical attack.

It is clearly not as secure as OTP. It is not information thetorical secure. With sufficient messages totalling more than key size we can brute force the key, just iterate over possible keys until you find one which works with all messages.

With a OTP when the total message size never exceeds the key size, no compute power will allow you to brute force the key, all messages are equally likely and knowing part of the message doesn't help as the key is never reused.

Edit: Even an attack with $O(2^{kn})$ is sufficient to make it not information theoretical secure. but we can do at least somewhat better.

With $O(k)$ message pairs we can break the key with O(n*2^k) work. work one segment at a time. Iterate over all $2^k$ possible key segments, and check the messages, each message will exclude a bad key with probability 0.5 so we only need a few message pairs to rule out all false keys.

I reserve judgment regarding security of this with large k, and secure hash.


How to correctly implement an archetypal encrypt-then-MAC AES-CTR + HMAC mode cipher?

You are describing encrypt-then-MAC using AES-CTR for encryption and HMAC for the MAC. This indeed results in authenticated encryption.
There may be better choices for the key derivation function, but I'm not very familiar with the options, so I'll let others comment. I don't understand why you salt the KDF when deriving the key. This just means that you will need to re-key for each ciphertext. In some ways, re-keying is better for security (maybe not here with low-entropy passwords seeding the key), but usually people like to avoid re-keying for the sake of performance.
The IV is only $8 \text{ bytes} = 64 \text{ bits}$, so you will start to expect collisions after encrypting $2^{32} =$ a few billion ciphertexts. This doesn't seem very good to me. You are devoting a full $8 \text{ bytes} = 64 \text{ bits }$ to the counter. Do you really need to support ciphertexts that are $2^{64}$ blocks long? A better balance between IV+counter  length would be preferable. For example, with a 12-byte IV and 4-byte counter, you avoid IV collisions up to 2^48 and can support ciphertexts that are $2^{32}$ blocks long ( $2^{32} \times 128 \text { bits } = 0.5 \text{ terabits} = 64 \text{ gigabytes} ).$


Password vs public key for authentication?

We don't want to compare a password and a public key. The password needs to be kept secret from adversaries trying to impersonate its owner, while the public key is intended to be freely disseminated, and is not a mean of authentication.

We want to compare a password and the private key of a public/private key pair (asymmetric cryptography) as mean of authentication. The core difference is that the password has no equivalent to the public key: something that's safe to reveal but allows to check possession of the authentication mean.

Consequently, a huge drawback of the password is that each entity with which the password is used can get to know it. As usually practiced in web server access: just by keeping a copy of the password at registration or log in; and at any time with more work (by trying enough likely passwords and applying at high speed the method normally used to check if the password is right, until hitting the right one; for typical passwords, there's a high risk the password is found with less cost than it is worth, at least for some users; that's including with password protocols like SRP, seldom used). That's one reason it is recommended not to use the same passwords for different servers.

Also, as usually practiced, if an an adversary manages just once to impersonate the legitimate entity that verifies the password (e.g. by making a fake server looking like the original), s/he can receive the password from its unsuspecting owner, and then impersonate the owner at will (including to other servers if the same password was used for different servers, another reason to avoid this).

By contrast, a public/private key pair can safely be used to authenticate with respect to any number of entities/servers, even careless or dishonest. Also, it is possible to obtain a certificate from an authority binding one's public key with an ID (domain name, email, name..); that allows to authenticate as associated to this ID to an entity trusting that authority, without prior enrollment with said entity. A password only allows that if the trusted authority checks the password, and confirms that it did to said entity by some online communication (example: using one's Google ID to authenticate on StackExchange).

A public/private key pair allows the holder of the private key to sign a document/file, offline, in a way verifiable against the public key, so that anyone can check that the document was signed by the holder of the private key. A password does not allow that.

When it comes to trust in the equipment used, authentication by password or private key are about equally vulnerable: if the user's computer manipulating the password or private key is rigged, poof goes security as long as the password or key pair is not revoked. Keeping the private key in a Smart Card improves things because the private key is safe in the Smart Card, but only partly: if the computer is not trusted, while the Smart Card is connected to a rigged computer, the Smart Card can be misused without the legitimate user knowing.

Private keys have one serious drawback compared to password: they are too long to memorize or key-in on a regular basis, even if we use techniques towards that goal. There is a wide a gap between high-level security and the 44-bit XKCD password, or anything a user is willing to type regularly; that gap can't be conveniently bridged with key strengthening, at least on current convenience devices.

As an aside, use of private key as an authentication mean requires complex calculations, versus a minimum of none for password. However that has become a lesser issue with powerful CPUs everywhere.

There's something in-between password and private key as an authentication mean: secret key (of symmetric cryptography), shared with the other party. That has all the worst properties of private key and password combined, with a few exceptions:

Cryptograms necessary for one authentication can be small (like 6 digits), thus can be keyed-in. That's used by authentication dongles.
Secret keys are shorter than typical private keys; but it is equally hard to come-up with a safe and convenient way such that they could be memorized or regularly key-in.
Calculations are slightly less complex than for private key; but they still require a CPU, thus that's an edge only when limited to very lost power/cost CPU.


Bit commitment, two blobs with same bit, without revealing it?

Give a zero-knowledge proof that $y_1 \times y_2$ is a Quadratic Residue.

[Extra verbage included because a one line answer feels too brief]

If we have $y_1 = x_1^2 t^{b_1}$ and $y_2 = x_2^2 t^{b_2}$, then $y_1 y_2 = (x_1x_2)^2 t^{b_1 + b_2}$.

If $b_1 = b_2$, this product is either $(x_1x_2)^2$ (if $b_1 = b_2 = 0$), or $(x_1x_2t)^2$ (if $b_1 = b_2 = 1$), in both cases a Quadratic Residue.

If $b_1 \ne b_2$, this product is $(x_1x_2)^2 t$, which is a Quadratic Nonresidue, hence we would not be able to generate a Zero Knowledge Proof that it is.


Is there an existing cryptography algorithm / method that both encrypts AND compresses text?

So I'm trying to find a method of encryption that not only obfuscates text, but also compresses the result.
  For example, if I encrypted ninechars, the ideal result would be less than nine characters.

Even without encryption, it's not possible for a reversible data compression scheme to shorten all of its inputs.  This can be easily proven using the pigeonhole principle: for any given length $\ell$, there are fewer strings of length strictly less than $\ell$ than there are strings of length at most $\ell$.  Thus, if the compression scheme maps all strings of length at most $\ell$ to strings of length less than $\ell$, it must necessarily map some distinct input strings to the same output string, and thus be irreversible.

(In fact, a similar argument can be used to show a stronger result, namely that, if a lossless compression scheme makes any input string shorter, then it must also make some input string longer.  I'll leave proving that as an exercise.)

  Otherwise, if this is not possible, is there a method where I can set a limit on the amount of characters in the result? In other words, no matter how long the input is, the result will always be 50 characters long.
  TL;DR I pretty much need a "hash function" that is reversible.

This is also impossible, by a similar argument.  There is a finite, fixed number of strings of length 50 (namely, $k^{50}$ for a $k$-letter alphabet), whereas the number of possible input strings of unbounded length is infinite.  Thus, not only does any function mapping arbitrary unbounded inputs to 50-character outputs need to map some distinct inputs to the same output, but it actually has to map infinitely many inputs to some output.

In fact, to show that such a function cannot be reversible, it's enough to consider only inputs that are 51 characters long.  Clearly, there are more 51-character inputs than there are 50-character outputs, so some distinct inputs have to map to the same output.

Of course, if you allow some inputs to increase in size, then you can make other inputs shorter.  This is basically what ordinary data compression algorithms like LZW do — they rely on the fact that most of the possible inputs to the compressor look essentially like random noise, whereas most of the typical inputs (like plain text, program code, uncompressed image or audio data, etc.) have a lot of repetitive, non-random structure.  Such repetitive data can be encoded more compactly, making it a lot shorter; meanwhile, if the input does not happen to be repetitive enough to compress well, the compressor will just insert a short marker (at a minimum, a single bit, but in practice usually a few bytes) indicating that the data could not be compressed, and then include the input verbatim.  Thus, the compressor can compress some common types of inputs significantly, at the cost of very slightly increasing the length of the random-looking inputs that make up the bulk of the full input space.

Anyway, none of this really has anything to do with cryptography.  If you want to both compress and encrypt data, the standard way is to first compress it, and then encrypt it.  (You cannot compress it after encryption, since encrypted data does look random to anyone who doesn't know the key, and has no apparent structure that a compressor could exploit.)

As other answers have pointed out, though, even this standard method has risks.  One risk comes from the fact that any encryption scheme that can handle arbitrarily long messages must necessarily reveal at least some information about the length of the message.  This may allow an attacker to, say, distinguish the message YES (three characters) from the message NO (two characters).

This is true even without compression, and needs to be kept in mind when designing any cryptosystem, but adding compression to the mix makes it harder to predict and defend against.  For example, even if you were careful to always use fixed-length messages (like, say, POSITIVE and NEGATIVE instead of YES and NO), it's quite likely that running such messages through a compressor will produce output whose length varies.

More importantly, if the attacker can control some of the data being compressed and encrypted, they may be able to learn information about the other parts by observing the length of the compressed message.  For example, let's say the attacker can make you generate, compress and encrypt messages of the form TO <ID>: STATUS <POSITIVE/NEGATIVE>, where <ID> can be controlled by the attacker.  The attacker may then be able to request two encrypted messages, one for <ID> = POSITIVE and one for <ID> = NEGATIVE, and see which one compresses better.

Of course, these are all just toy examples, but similar weaknesses have led to real attacks.  For example, as mentioned in otus's answer, the CRIME and BREACH attacks on SSL are based on the same principle as the chosen-plaintext toy attack described in the previous paragraph.  Even the passive attack described earlier above, based on just observing naturally occurring message lengths, may be used to e.g. eavesdrop on encrypted VoIP conversations.

That said, the lesson to take home here is not just that data compression is dangerous and should be avoided.  Rather, it's that the leakage of plaintext length is dangerous, and, since it cannot be completely avoided, must be kept in mind when analyzing any crypto protocol.  Compression is an additional complication on top of that, since it can make the message length depend on its content in non-trivial and non-local ways.


Is OpenPGP vulnerable to the "crypto doom principle"?

The answer (to the title question) is no, due to a slight mixup in terminology. What Moxie says is (emphasis added)

  if you have to perform any cryptographic operation before verifying the MAC on a message you’ve received, it will somehow inevitably lead to doom.

Notice that he says MAC and not signature. The PGP group has discussed this too, so you are not alone in your concern.

In other words, mac-then-encrypt is not the same thing as sign-then-encrypt. Sign-then-encrypt is preferred to encrypt-then-sign. For more discussion on sign-then-encrypt see this question and answers.


Any downside to encrypting original signed message with the private key?

There are actually a few downsides which mostly depend on the size of the original message.

So recall that for signing purposes, the hash (or message digest) is used to sign the document. Thus assuming that the message is large we can face several possible issues:

1. Efficiency: Recall that signature schemes use asymmetric encryption which is much slower than symmetric encryption. So if you were to sign the entire message it could take some time. (Hash or message digest is relatively small in size and thus fast to sign)

2. Integrity: Given the message is too large (for the signature space) the message may be required to be split into separate blocks (separate messages). Now each message created must now be signed differently and the order of the message blocks may need to be preserved which is an additional overhead.

3. Compatibility: Some signature schemes such as RSA can not operate on Bit strings so it adds extra difficulty re-configuring the message or changing the signature scheme.

Of course, if the message is small, it can get away with the first two issues with small overheads, but it's probably better to use a key-sharing encryption scheme with signatures rather than have to go through all this overhead.

Let me know if that raises any other questions, Cheers!


Man-in-the-middle attack on Diffie-Hellman with shared public keys?

Yes, for sure, you can perform what is called ephemeral-static Diffie-Hellman or static-static Diffie-Hellman where one or two parties are authenticated respectively.

Multiple schemes have been described in NIST SP 56A: Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography, sections 6.2 and 6.3.

You would of course need an additional (random) nonce if you use two static public/private key pairs. Otherwise there are no variable values in the equation and you would always generate the same session keys.

If you want to have a view of ephemeral-static Diffie Hellman then you don't have to look further than TLS 1.2, any ciphersuite that starts with DH or ECDH (without the E after it). They are not used much, generally ephemeral-ephemeral Diffie-Hellman is used with a separate authentication using RSA or ECDSA signatures. Certificates with a DH or ECDH public key are very rare indeed.

Key pair generation creates both the public and private keys and takes place on the machine of the owner of the key pair. Generally the private key should not leave this machine, except for backup purposes.

I'm not sure your sample algorithm complies with DH as specified in this standard document.


Mapping the hash of message to a point of elliptic curve for signature

That's insecure.
In BLS signatures: for private key $x$ and public key $X = xP$, the signature is computed as $T = xS$, and the verification checks if $e(T, P) = e(S, X)$, which works because:

$e(T, P) = e(xS, P) = e(xS, P) = e(S, P)^x$
$e(S,X) = e(S, xP) = e(S, P)^x$

If you know that $S = kP$, then you can forge a signature for a message with hash $k'$ from a signature of a message with hash $k$ by simply computing $T' = k'k^{-1}T$, which works because:

$T' = k'k^{-1}xS = k'k^{-1}xkP = xk'P = xS'$


Is cryptography an interesting field for research?

Cryptography is a nice field in which not only problems to solve are a-plenty, but it is also one of these fields where individuals can make significant discoveries in a relatively short time. A PhD student in cryptography will typically write three or four articles during his thesis; by comparison, a "pure mathematics" PhD student will generally produce a single article in the same time. Informally, to make new advances, you have to first learn the existing science; in cryptography, this means getting up to date with about 40 years of research. In mathematics, that's closer to 200 years, hence the comparatively higher effort to reach the "publishable" state.

Moreover, cryptography is an applied field, by which I mean that it has immediate practical applications. This means money: you can make a very nice living out of cryptographic expertise. A PhD is a very good key to unlock such things (I have a PhD and I am a consultant in cryptography, and my experience is that both facts are related). Intellectual fulfilment is of primordial importance to a balanced life, and money does not make happiness; but money is still some super useful stuff, and being able to live out of doing intellectually rewarding things is a nice combination to achieve.

In any case, mathematics are always useful for anything related to computers. A lot of computer users and developers can get along with a very low understanding of the underlying principles, but the maths are what explains why computers work that way. Mathematics allow to look beyond the magic.


Encryption algorithm which produces comparable results for substrings

It is somewhat unclear what you mean by comparable strings. But from the example you give, one might construe that you want the same substrings in different plaintext messages to be encrypted in the same way. This property is obviously very bad for an encryption scheme (given a number of plaintext/ciphertext pairs it would be easy to derive a lot of information about the encryption scheme).

There are however early instances of encryption with such a bad property like the monoalphabetic substitutions (Caesar's cipher for example).


How does the security risk arise?

Because you can simply drop or reorder signatures for single block. Assume you have a message $m$ and you split it up in blocks $(m_1,m_2,\ldots,m_n$) and get signatures $(\sigma_1,\sigma_2,\ldots,\sigma_n$). Then you could just drop for instance $\sigma_2$ and get a signature for message $(m_1,m_3,\ldots,m_n)$. You can also replace arbitrary sub-signatures, e.g., $(\sigma_2,\sigma_1,\ldots,\sigma_n)$ which is a valid signature for $(m_2,m_1,\ldots,m_n)$. Now you could say that you introduce increasing sequence numbers, but if you got two signatures you could simply exchange sub-signatures from these two signatures to obtain valid signature for "mixed messages". Ok, now you could say you use unique sequence numbers per message, but there may be too many other attacks that you do not consider.

  If I do not want to include a hash function for signature schemes with appendix, can I break the message up into blocks of fixed lengths and sign each block?

So why introducing such additional assumption where you may overlook something that is specific to your application scenario.

Besides removing these problems it is far more efficient to firstly hash the message before signing and then sign a single block.


AES input size is exactly 16 bytes. But you can apply AES endlessly if you divide your data into a stream of blocks of 16 bytes. – rustyx

rustyx is party right. Just splitting the data is called ECB mode and it is insecure as you can detect repeated plaintext blocks. AES is not a full cipher, it is a block cipher. To create a real cipher from it you need to use it within a mode of operation. To have full CPA security this also requires a unique IV.

The amount of data that can be processed depends mainly on the mode of operation and the width of the block cipher (the block size). Generally modes of operation can handle at least 64 GiB of data in the worst case scenarios (e.g. for authenticated mode of operation such as GCM.


Security of Homomorphic encryption schemes

Why does it not follow the $2^n$-bit security?

They follow the usual way of describing schemes, i.e., $n$ bits of security means $2^n$ operations to the best attack. So, taking $n = 80$, you impose "an effort" of $2^{80}$ to the attacker.

  Is this secure enough?

This is a tricky question. That depends on what you want to do with the scheme and how powerful the attacker is supposed to be.

Anyway, I think the main reason to have $n = 80 $ in this kind of paper, is that homomorphic encryption schemes are very expensive and authors just want to show a proof of concept. Anyone that wants to use these cryptosystems is free to instantiate them with larger values of $n$.


Enc-Mac (AES CTR+CBC) mixing AES-256 and AES-128 and splitting keys

Don't share keys (or derive new keys with a simple method like splitting the original key) for different purposes. If you can't generate truly seperate keys, get a "master key" and derive two keys for encryption and MAC with a strong hash function.

Sharing a key for encryption and authentication with ECBC-MAC is really bad. Splitting the key to generate new ones sounds insecure, but it could also be secure - do you know it? In any case your scheme will break totally if an attacker learn either your encryption or MAC key. That itself is already bad, but with your scheme it's really simple to get the respective other key, compromising both.


A circuit is just a way to represent a computation. There is nothing specifically cryptographic about a circuit. It just means a straight-line computation (no looping or flow-control constructs) consisting of just operations on bits, like AND, OR, NOT.

A garbled circuit is a way to "encrypt a computation" that reveals only the output of the computation, but reveals nothing about the inputs or any intermediate values. We use the term "circuit" because garbled circuits work by taking the computation you care about, expressed as a circuit, and then doing some cryptographic stuff for each operation (AND, OR, NOT) in the circuit.

If we want to be a little more precise, a "garbling scheme" consists of:

(Garble) A way to convert a (plain) circuit $C$ into a garbled circuit $\widehat C$.
(Encode) A way to convert any (plain) input $x$ for the circuit into a garbled input $\widehat x$. You need the secret randomness that was used to garble the circuit to encode $x$ into $\widehat x$.
(Evaluate) A way to take a garbled circuit $\widehat C$ and garbled input $\widehat x$ and compute the circuit output $C(x)$. Anyone can do this, you don't have to know $x$ or the secret randomness inside $\widehat C$ to evaluate and learn $C(x)$.

I'm simplifying a little bit here. But the main idea of security is that $\widehat C$ and $\widehat x$ together leak no more information than $C(x)$. In particular, they reveal nothing about $x$, yet they allow the computation $C(x)$ to be done (obliviously). This is what I mean by "encrypting a computation".

The main application for garbled circuits is secure two-party computation. Imagine that Alice has private input $x$ and Bob has private input $y$. They agree on some function $f$ and agree that they both want to learn $f(x,y)$, but don't want their opponent to learn anything more than $f(x,y)$. To achieve this, they can do the following (this is Yao's classical protocol):

The parties agree on a way to express $f$ as a (plain) circuit. Alice garbles the circuit $f \mapsto \widehat f$. She sends $\widehat f$ to Bob as well as her own "garbled input" $\widehat x$.
Alice knows how to encode any input for $f$ into a "garbled" input, but only Bob knows his private input $y$. So the parties arrange for Bob to pick up a garbled version $\widehat y$ without Alice learning what $y$ was. This can be done with a primitive called oblivious transfer.
Now Bob has the garbled circuit $\widehat f$, and a garbled input $\widehat x, \widehat y$ for that circuit. He can then run the evaluation procedure and learn $f(x,y)$. He can reveal $f(x,y)$ to Alice.

We can argue that the protocol reveals no more than $f(x,y)$ in the following way:

Alice doesn't see anything other than the final answer $f(x,y)$ in this protocol (the security of oblivious transfer ensures that she learns nothing in step 2).
Even though Bob sees $\widehat f$, $\widehat x$ and $\widehat y$, the security of garbled circuits ensures that these values don't reveal anything beyond $f(x,y)$.

This approach works when Alice & Bob are semi-honest (i.e., they follow the protocol as instructed). But when Alice is malicious she can garble some other function $f'$ instead of the $f$ that they agreed upon. So other things need to be added to the protocol to prevent this from happening, when we want security against malicious adversaries.

Reference material:

The Yao Construction and its Proof Of Security
 (video), Yehuda Lindell
A Proof of Yao's Protocol for Secure Two-Party Computation, Yehuda Lindell & Benny Pinkas
Foundations of Garbled Circuits, Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
A Brief History of Practical Garbled Circuit Optimizations, a video of mine. The first several slides cover the "classical" construction of garbled circuits.


DSA relies on $k$ being independent from $d$. You define $k$ as:

$k=z^\prime d\mod n$

Substituting $k$ in the signing equation you get:

$s = k^{-1} (z+rd) \mod n$

$s z^\prime d = z + rd \mod n$

$d=z (sz^\prime -r)^{-1}  \mod n$

The attacker knows everything on the right side and can recover the private key.