PPT eavesdroper able to output $m_{0}$ and $m_{1}$ of different lengths

Actually, every encryption algorithm has an associated message space which defines the maximum message size which can be encrypted and the ciphertext is always of size of the associated ciphertext space. If the message at hand is larger than the message space of the encryption algorithm, you have to encrypt the message "block by block" (where a block can also be a bit. For block ciphers there are various ways to realise this, e.g., CBC (see here), for stream ciphers viewing the message space as being a bit it should be obvious how the ciphertext size depends on the message size and for asymmetric schemes in practice this is typically not required since you use hybrid encryption and thus always only encrypt a single "block".

Now for achieving the weakest reasonable security, i.e., indistinguishability under chosen plaintext attacks (IND-CPA) where i'm talking about public key encryption schemes here (actually the argument is the same for one-time computationally-secret as in your referenced question), an adversary providing two challenge messages $m_0$ and $m_1$ and given back the ciphertext $c_b$ has to figure out which one has been encrypted (i.e., determine whether $b=0$ or $b=1$) (here it does not really matter that the adversary can then afterwards ask an encryption oracle for encryptions of messages different from the challenge messages). Clearly, if one of the challenge messages is out of the message space and the other is larger, i.e., requires $>1$ blocks, then it is trivial to distinguish the two ciphertexts.

Consequently, in the attack game one requires that if one message is larger, the second is padded to have the same length as the first to rule out this trivial attack. Then, if both messages are of the same length (and padded) both ciphertexts will be of the same length and then the adversary has to apply a non-trivial strategy to figure out which message has been encrypted as a challenge.

Edit: PrivK Game:

Ok, the PrivK game is defined as follows (I took the definition from this question):

An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is one-time computationally-secret if for any PPT adversary $\cal A$ it holds that $Pr[PrivK_{\cal A}^{eav}(n)=1]−1/2$ is negligible function, where $PrivK_{\cal A}^{eav}(n)$ denotes the output of the following experiment:

(a) The adversary $\cal A$ on input $1^n$ outputs a pair of messages $m_0,m_1$.

(b) Let $k\leftarrow Gen(1^n)$ and let $b\in \{0,1\}$ be chosen uniformly at random. Then a ciphertext $c\leftarrow Enc_k(m_b)$ is computed and given to $\cal A$.

(c) $\cal A$ on input $c$ outputs a bit $b'$.

(d) The output of the experiment is $1$ if $b'=b$ and $0$ otherwise.

Let us assume that we have a block cipher with block size $k$ bits and let the adversary now choose a message $m_0\in \{0,1\}^k$ and $m_1 \in \{0,1\}^{2k}$, i.e., message $m_0$ has one block and message $m_1$ has two blocks. Consequently, $c_0=Enc_k(m_0)$ will be of size $k$ bits and $c_1=Enc_k(m_1)$ will be of size $2k$ bits. Hence, the adversary will always output $1$ and thus $Pr[PrivK_{\cal A}^{eav}(n)=1]=1$ and $Pr[PrivK_{\cal A}^{eav}(n)=1]-1/2$ is $1/2$, which is non negligible. Consequently, we need to require that $|m_0|=|m_1|$ to rule out this strategy for $\cal A$.


Example of a Hash function which is second pre-image resistant but not collision resistant

Let $H$ be a collision resistant hash function. This implies that it is also second preimage resistant.
Let $x_0,x_1$ be two arbitrary values from the domain of the hash function. We define the new hash function $$H'(x):=\begin{cases}H(x)& \text{if }x\neq x_0\\H(x_1)&\text{if }x=x_0\end{cases}.$$
This hash function is trivially not collision resistant, just output $x_0,x_1$. However, it remains second preimage resistant via a simple reduction.


Is it possible to subtract/multiply numbers using homomorphic encryption?

Have you read Wikipedia: homomorphic encryption and
Bruce Schneier: Homomorphic Encryption Breakthrough?

In summary:

  Is it possible to subtract numbers using homomorphic encryption? Is it
  possible to multiply numbers using homomorphic encryption?

Yes, there are many known partially homomorphic cryptosystems, each one can either multiply or add numbers.

To add two encrypted numbers, one could use Benaloh, Damgård–Jurik, or several other known partially homomorphic cryptosystems.
(Many of these "addition-only" cryptosystems can also be tweaked to support subtraction.
Asking "how do I do that" would be a great separate question).

To multiply two encrypted numbers, one could use Unpadded RSA, ElGamal, or several other known partially homomorphic cryptosystems.

  Is it possible to subtract and multiply numbers using homomorphic
  encryption?

To multiply one encrypted number by a plaintext number (which, alas, is not sufficient for fully general computation) and also add two encrypted numbers, one could use Paillier, Naccache–Stern, or several other known partially homomorphic cryptosystems.

Subtraction can be implemented by encrypted "multiply by a plaintext -1" followed by encrypted addition.
(Asking "how do I do that" would be a great separate question).

  Is it practical to express any computation whatsoever as a series of multiplies and subtracts?

Yes. In fact, computations on decimal numbers, text strings, 2D images, etc. are almost always done by converting to binary representation, using a series of Boolean computations internally, and then converting back to a human-friendly representation.
(Boolean computations can, in turn, be implemented using multiplies and subtracts, although that is slightly less efficient).

  Is it possible to encrypt a few numbers, send them to a distant server
  that uses homomorphic encryption to do a series of
  "encrypted subtraction" and "encrypted multiplication" operations
  on those
  numbers, and then sends the encrypted result back -- a message that can be
  decrypted to give the same result as a corresponding series of
  subtractions and multiplications on those numbers?

Cryptographers have been hunting for such a "fully homomorphic encryption scheme" for decades.
After a few decades of searching and coming up empty, cryptographers were starting to think perhaps fully homomorphic encryption is impossible.

The first known fully homomorphic encryption scheme was discovered by Craig Gentry and announced in 2009. It is an amazing theoretical breakthrough.

Alas, in that scheme, the "encrypted subtraction" and "encrypted multiplication" operations are so complicated that it's not really practical.

Now that one fully homomorphic encryption scheme has been demonstrated,
cryptographers have high hopes that other, more practical systems will be discovered.

The current situation is something like the current situation with manned moon missions.
People have been dreaming about traveling to the moon for centuries,
but it was long thought to be completely impossible.
In a great technological breakthrough, one method of traveling to the moon put 12 men on the moon, demonstrating that it is possible.
However, that particular method is so expensive that it is not really practical.
Still, futurists have high hopes that other, more practical systems will be discovered.


Is a stream cipher and a (cryptographically secure) PRNG nearly the same thing?

Stream cipher and CSPRNG aren't the same thing. CSPRNGs must handle initial seeding, post-compromise reseeding, back-tracing resistance among other things; stream ciphers only need to be able to output something indistinguishable from random.
So can we turn a CSPRNG into a stream cipher? Possibly, if we make every generate requests to the CSPRNG idempotent, and drop reseeding. But that wouldn't be as efficient as just using the stream cipher directly - not only does CSPRNGs has extra code paths to execute, its internal state is often larger than that of stream ciphers.


Zero Proof Knowledge for data set information

Your question actually demonstrates a quite common misconception when it comes to zero knowledge. Unfortunately, you will need some basic complexity background to understand what I'm going to answer. Note: I am not going to talk here about practical and efficiency sides of zero knowledge, but rather the theoretical question of what can be proven.

The famous GMW theorem for zero knowledge is often quoted to say that "anything" can be proven in zero knowledge. However, this is a misconception: rather, it says that any language in $\cal NP$ can be proven in zero knowledge. (I am not going to relate to languages in $IP\setminus NP$ since they do not have efficient provers.) Now, this means that in order to apply zero knowledge, you have to make sure that the statement is in $\cal NP$.

Let's say that a prover $P$ holds a database, and wants to prove to the verifier that certain values are in a range. First, you need to define the $\cal NP$ statement. What would it be here? One option is to say "there exists a database $D$ such that it contains the values in the range...". Well, that's actually a trivial language since for a fixed definition of the values the answer is always yes (and irrespective of any input statement $x$). Basically, the problem here is that there is no statement of reference related to your database, and so this is meaningless.

Therefore, the way to solve this is to have the verifier hold a commitment to the file. This can come in many forms, but consider a public-key encryption scheme with key pairs $(pk,sk)$ and denote the database by $D$. Then, the statement is $c=Enc_{pk}(D)$ and the $\cal NP$-witness is the secret key $sk$. The language is all of the pairs $(pk,c)$ where $c$ is an encryption of $D$ under $pk$ (with the specified public key encryption scheme) and $D$ contains values in the range as defined. Note that $pk$ must be included in the statement since otherwise $c$ doesn't uniquely define $D$.


Why is the polynomial in AES MixColumns multiplied modulo a reducible polynomial?

The reason it is not irreducible is because it does not have to be.

For MixColumns, the result must be a polynomial of degree 3 or less, which requires a degree 4 reduction. We are not reducing the elements of the finite field here, but the coefficients of the polynomial generated by multiplication of the fixed and input polynomials. With reduction by $x^4+1$, the reduction can also be represented as replacing the coefficient of $x^0$ with that of $x^4$.

The choice of degree 4 reduction polynomial does not have to be irreducible in $GF(2^8)$ if the fixed polynomial in the matrix multiplication has an inverse, which it does. In the case of $c(x)=3x^3+x^2+x+2$, $c^{-1}(x)=11x^3+13x^2+9x+14$.


Why is ElGamal considered non-deterministic?

In this context, "nondeterministic" means that the algorithm to generate the ciphertext (or the signature) takes a random value as one of its inputs, and it can generate many possible ciphertexts (or signatures) based on the random value.  ElGamal is nondetermanistic because the encryptor selects a random exponent as a part of encryption method.

For public key encryption, this randomization of the encrypted message is important.  If the public key encryption algorithm was not nondetermistic (that is, the encrypted message depended only on the plaintext message and the public key), then someone with an encrypted message $M$ and the public key $PK$ and a candidate plaintext message $P$ could test if the decryption of $M$ was $P$ (simply by encrypting $P$ using the public key $PK$, and checking if the result was $M$).

Because of this, public key encryption is almost always nondetermanistic.  Note that RSA is not an exception; while the core RSA algorithm is determanistic, actual RSA public key encryption also includes a padding method, and this padding method can (and generally does) include randomness.

For public key signatures, there is no corresponding requirement due to the primitive semantics that signatures be generated using some random input; however, some cryptography proof techniques do assume that the signature generation is also nondetermanistic.  On the other hand, in the specific case of ElGamal signatures (DSA), it actually does require a random input, and it turns out that this input really does need to be random, and uniformly distributed.


If the master key is strong (e.g. random 256-bit key), $c=1$ is fine, or you can use HKDF. A high number of iterations is only needed when you derive the key from a password or other low entropy string.
If you can store a 4000 element table securely, you could just use random keys instead of derived ones.
If you need the derived key to depend on a low entropy master key, you could use a randomly generated salt you keep secure. In that case leaking the salt will allow a brute force or dictionary attack on the master key, but without knowing the salt an attacker cannot attack it.

Optimally, your situation is 1. and you don't need to do anything special. 2. is also a secure alternative, but requires you to store more keys. You should only use 3. if you have no other options, and in that case you should use as high a $c$ as you can.

Now the actual question, is such a table secure?

If you have a large enough table that is only used for one key, it will not hurt the quality of the derived key. However, if that isn't the case, it may, since the keys will share the nonuniform probability distribution defined by the table.

An attacker who has the table could of course derive the key just as easily as when no table was used, so it is no better than using a random secret salt like I suggested in 3. above. So I wouldn't recommend using it.


I would highlight Thomas's last point; not only is leaking $m \oplus m'$ failing to provide perfect secrecy, it is often practically insecure.

Exactly how bad this is depends on what those messages actually are (and how they are encoded), but it can be bad indeed.  As one example, in my experience, recovering two ASCII English texts from their xor is about as difficult as solving a newspaper cryptogram.


To see why CBC mode still needs a MAC to guarantee message integrity, first recall how CBC mode decryption works:

$$P_i = D_K(C_i) \oplus C_{i-1}$$

Here, $D_K$ denotes block cipher decryption using the key $K$, and $C_i$ and $P_i$ denote the $i$-th ciphertext and plaintext blocks respectively.

Now, consider what happens if you modify the encrypted message to replace $C_i$ with $C_i' = C_i \oplus X$ for some $i$.  Now, the corresponding plaintext block $P_i'$ will be garbled, since $D_K(C_i')$ will in general bear no predictable resemblance to $D_K(C_i)$.  However, the next plaintext block $P_{i+1}'$ will now become

$$P_{i+1}' = D_K(C_{i+1}) \oplus C_i' = D_K(C_{i+1}) \oplus C_i \oplus X = P_{i+1} \oplus X.$$

Thus, even with CBC mode, you can still flip arbitrary bits in any given plaintext block, provided that you don't mind the previous plaintext block being garbled.  Whether this is actually practical depends on the what the plaintext is supposed to be, but it's generally not safe to assume that it isn't.

Of course, since the garbled block will, in general, be essentially random and unpredictable by the attacker, it might seem plausible that a simple non-cryptographic checksum could detect such modification.  However, it's not entirely implausible for the attacker to be able to predict $D_K(C_i')$, and thus $P_i'$: for example, if the attacker has access to some known ciphertext/plaintext message pairs, this provides them with a bunch of blocks whose image under $D_K$ is known.  If they choose $C_i'$ to be one of such blocks, they'll be able to predict $P_i'$, and if they can also guess the original plaintext block $P_i$, they may be able to spoof many non-cryptographic checksums.

(In particular, if the IV is sent alongside the message — as is usually done — flipping bits in the first plaintext block is particularly easily done just by flipping the corresponding bits in the IV.  Thus, for the first block, CBC mode is just as malleable as CTR or OFB.)

The bottom line of all this is that, if you want to protect the integrity of your messages, you need to use an encryption mode that is actually designed to be provably non-malleable.  In addition to the generic combination of a classical block cipher mode and a MAC, there also exist several authenticated encryption modes specifically designed for this purpose.


Extracting $ x $ given $ g^x, g^{x + y}, y $

Ok, I gave the answer in my comment; however so that you can accept an answer (and so close this question out), I'll repeat my answer here.

Yes, it is still hard to find the discrete log, given $g, g^x, g^{x+y}, y$.  The reasoning is simple; if that were an easy problem, that is, if we had an oracle that, given $g, g^x, g^{x+y}, y$, recover $x$, we could then solve the discrete log problem.  Here's how we would do that: given $g, g^x$, we would select a random $y$, and compute $g^y \cdot g^x = g^{x+y}$.  Then, as we had $g, g^x, g^{x+y}, y$, we could hand those values to the oracle, which would give us $x$, solving the original DLog problem.

You also have an obvious reduction in the other direction; hence your problem is precisely equivalent to the standard DLog problem.


Why use Diffie-Hellman key exchange over RSA (or any public-key encryption)?

Alice could just generate a random number (to be their shared key), sign it, encrypt it with Bob's public key, and send it to Bob.

I, as an eavesdropper, can capture this exchange. In fact, I can capture many of these as I want with other people communicating with Bob. Then, fast forward to some point in the future, if I can compromise Bob's private key, I can now decrypt all those past communications using Bob's compromised private key. Additionally, I can compromise all new secure communications with Bob (since I have his private key, I can do it on the fly, no need to wait).

Compare this with the DH over RSA case, where as you say, Alice and Bob sign the DH elements they transfer to one another. I capture this information as it is transiting the wire and save it. Again, fast forward to some point in the future where I have compromised Bob's private key. What can I do now? Well, I can still MITM subsequent connections as I can masquerade as Bob having his private key. But what about all those prior sessions? There is nothing I can do with those as they have already occurred. There is nothing to decrypt with Bob's private key.

As Ricky pointed out in the comments, this is a property of secure communications knowns as forward secrecy. If long-term private keys have not been compromised at the time of the handshake, going forward even if those private keys do get compromised, our prior sessions are still secure.


Trying multiple private keys against a pcap

META: this is really tool use not crypto and probably should be on superuser.

Open the PCAP file in Wireshark. Find the/a desired handshake; expand the handshake message containing the (server) Certificate message, the Certificates element, the first (EE) Certificate and the signedCertificate; click subjectPublicKeyInfo and rightclick,ExportSelected to a file, for example pubkeyfile.

Write a shell script (or CMD or PS or whatever) to run openssl pkey -in privkeyfile -pubout -outform der and compare the result to pubkeyfile; in Bourne-type shell this could be:

 for p in privkey*; do
     if openssl pkey -in $p -pubout -outform der | cmp -s - pubkeyfile
     then echo FOUND $p; fi; done


What is the difference between information-theoretic and perfect types of security?

Information-theoretic security means that any algorithm (even unbounded) has a negligible probability of breaking the security property (in the security parameter). This is the same as unconditional security: it does not rely on any computational assumption, and is not limited to probabilistic polytime adversaries.
A perfectly secure protocol is such that any (possibly unbounded) adversary has probability $0$ of breaking the security property. It is a special case of information-theoretic security: every perfectly secure protocol is information-theoretically secure, but the converse is not true.
To take a simple example, the distinction often appears when some secret value is masked with a random value, and we ask how hard it is to distinguish the masked value from a uniformly random value. Consider the following protocol: $x$ is an integer, say, between $0$ and $n - 1$. The game is as follows: we first sample a random bit $b$. If $b = 0$, we send a random value $r \gets X$ to the (unbounded) adversary, sampled from some set $R$, while if $b=1$, we sample a random value $r \gets R$ and send $x + r$ to the adversary. Fix a security parameter $k$. We say that the protocol has perfect security if the adversary has probability exactly $1/2$ of guessing the value of $b$ given the input, and that the protocol has information-theoretic security if the adversary has probability $1/2 + \mu(k)$ of guessing the value of $b$, where $\mu$ is a negligible function.
Suppose we identify $[0, n-1]$ with $\mathbb{Z}_n$ and define $R$ to be $\mathbb{Z}_{n}$ as well. The computation of $x + r$ is done over $\mathbb{Z}_n$. In this case, the protocol is clearly perfectly secure, as sampling $r$ from $\mathbb{Z}_{n}$ and returning $x+r$ gives exactly the uniform distribution over $\mathbb{Z}_{n}$, for any $x$.
On the other hand, suppose we set $R = [0, 2^{k} \cdot n]$ and compute $x + r$ over the integers. Then, it is easy to show that any (possibly unbounded) adversary has probability at most $1/2^{k}$ of distinguishing a sample from $R$ from a sample from $x + R$ (the statistical distance between these sets is $1/2^{k}$). Since this is a negligible function in $k$, this variant satisfies information theoretic security, but not perfect security.


How is the TLS 1.2 sequence number generated?

How many bytes is seq_num?

To quote the RFC (section 6.1; item 'sequence number')

 Sequence numbers are of type uint64

That is, they are 8 bytes long

  How is the sequence number generated?

From the same section:

 A sequence number is incremented after each
 record: specifically, the first record transmitted under a
 particular connection state MUST use sequence number 0.

That is, the sequence number for the first record is 0, the sequence number for the second record is 1, the sequence number for the hundredth record is 99.


Your parameters are incorrect.  I don't know how you got them, so I don't know which one is in error; however at least one of them is wrong.

You have $n = 149 \times 191$. The decryption exponent satisfies: $$ed \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)},$$that is, $7d \equiv 1 \pmod{14060}$; the minimal $d$ that satisfies this is $d = 10043$.

Now, if the hash is 4085 (and we'll assume you aren't doing any padding; for a normal sized RSA modulus, you would, however things are too small in this toy example), and so we have:

$S = 4085^{10043} \bmod 28459 = 5023$

With this value of $S$, we see that the signature verifies:

$5023^7 \bmod 28459 = 4085 = X$

Hence, assuming that you got the modulus, exponent and the hash correct, this is the correct value for the signature, not the value you have listed.


How to alter text that was encrypted with AES CBC using PKCSPadding7

First, normally a message authentication function (e.g. HMAC) is used with AES-CBC, specifically to prevent the type of attack described in this question, where the ciphertext is altered by an attacker in an attempt to produce a ‘wanted plaintext’ upon decryption.  See When do I need to use CBC and HMAC? for more info.
Also, the ciphertext that you posted is only one block long (16 bytes, or 128 bits).  So, AES alone (without CBC, and therefore without an IV) could have been used to produce this one block ciphertext.  It’s not clear from your question whether this one block of ciphertext was produced using AES alone, or using AES-CBC (with an IV).
If this one block of ciphertext as produced using  AES-CBC (with an IV), then normally the IV would be sent along with the ciphertext.  Without the IV, the recipient would have no way of decrypting the first block (and in this case, the only block) of the message.  The HMAC (above) is usually taken over the ciphertext and the IV, so that an attacker cannot modify either of these without detection.
In light of the above, there are a few ways to answer this question.

Older encryption algorithms such as XOR, OTP, Caesar, etc. without authentication, are notorious for being vulnerable to the type of attack that you describe, where the ciphertext is altered to produce a ‘wanted plaintext’ (see examples at https://security.stackexchange.com/questions/33569/why-do-you-need-message-authentication-in-addition-to-encryption).  However, putting aside the CBC part of AES-CBC, AES in and of itself is considered to be resilient to ‘known plaintext’ attacks.  Therefore, knowing the ciphertext and the plaintext of the message does not give an attacker an advantage in finding the encryption key, or mounting an attack like the one that you describe.

If we consider AES with CBC (AES-CBC), and the ciphertext and IV are not authenticated using an HMAC as described above, and the attacker knows the original plaintext, then the attacker can change the IV to cause the decryption to produce any plaintext he wants in the first block (and in this case, the only block) of the message.  See Can you change an AES encrypted message if you control the IV? for more info.

Nothing in this answer so far involves padding.  The fact that you mention padding in your question suggests that perhaps you are thinking of a padding oracle attack.  This type of attack requires the recipient of the message to leak information when it encounters a padding error upon decrypting the message.  In this case, the attacker can gradually deduce the encryption key by repeatedly crafting and submitting ciphertexts to the recipient for decryption, and learning from the recipient which ones produce padding errors.  Once the attacker learns the encryption key, he simply uses it to encrypt the wanted plaintext, so that upon decryption, the ciphertext decrypts to the wanted plaintext.


Is there a KDF that can be computed in an untrusted environment?

Also, I should be able to verify that machine actually performed the
  KDF and didn't just throw back a random key.

This is actually kinda hard, but can be worked-around by carrying out the very first computation of the hash function yourself. Then store this hash for the later verification with delegation or use it to derive your key to encrypt data. You will then verify that the returned result being correct by being able to successfully decrypt the data or by verifying that the "trusted" and the untrusted hash match.

  I'm looking for a [Password-based] Key Derivation Function [...], but which can be computed by a machine you don't trust. Some
  way to give it a derivative of the source password, such that the key
  can be computed from the derivative but the derivative is opaque and
  otherwise useless to the untrusted machine.

This functionality is precisely why our ursine overlord's Makwa has received a special recognition at the end of the Password-Hashing Competition (PHC). However it's has a somewhat "steep" baseline price. Namely you must perform about 300 (normal) modular exponentiations in an modular ring (ie modulo an RSA-like modulus) at setup time, additionally to finding a composite number similar to an RSA modulus. I will sketch the idea of it here, but I strongly urge you to read either the provided C / Java code or the specification (PDF). There are also other methods described / implemented there that will offer information-theoretic security instead of "mere" computational security if your psychology needs that.

To setup the things at your client, delegating the hashing do the following once at system-steup:

Pick a work-factor $w$, values of the form $\delta\in\mathbb N,\gamma\in\{2,3\}: w=\gamma\cdot2^\delta$ are recommended, with usual values being around $\delta=20$
Pick two primes $p,q$ such that it is infeasible to factor $n=pq$ (ie $p,q$ should be around 1024-bit long) and ensure that $p\equiv q\equiv 3\pmod 4$, store $n$ and keep $p,q$ for now
Pick an integer $m$ such that $2^{m/2}$ operations are infeasible, for example $m=300$
Pick $m$ random integers $r_i< n$, compute $\alpha_i=r_i^2\bmod n$ for each of them, compute $\alpha_i'=\alpha_i^{2^w}\bmod n$, use your knowledge of $p,q$ to reduce $2^w\bmod{\varphi(n)}$ first, where $\varphi(n)=(p-1)(q-1)$. Now compute $\beta_i=\alpha_i^{-1}\bmod n$ and store all $m$ pairs of $(\alpha_i,\beta_i)$, you don't need to keep these values secret
Discard $p,q$

To verify / derive the password hash (skip steps 5 and 7 and increase $w$ by one for your initial, trusted run):

Optionally pre-hash the password using HMAC-DRBG
Run the salt and the password through HMAC-DRBG to get $s_b$
Concatenate $s_b$, the password and the password-length to get $\chi$
Pick $m$ random bits $b_i$ using a CSPRNG
For all $j$ for which $b_j$ happens to be $1$: Compute $z=\chi^2\cdot \prod_j\alpha_j$, ie multiply the square of $\chi$ with all $\alpha_i$ where $b_i=1$
Send $n,w,z$ to the untrusted machine, let it compute $z'=z^{2^w}$, ie $w$-repeated-squarings and receive $z'$
Compute $y=z\cdot\prod_j \beta_j$ the same way as in step 5
Use $y$ as your output, which you may want to hash using any ordinary hash function if you intend to use it as a cryptographic key (because some bits won't have probability $\frac12$ of being $0$ or $1$) or if it is simply too large for you (with 256 bytes)


BLS signatures work in any so called gap group, i.e., a group where the computational version of the Diffie-Hellman (DH) problem - the CDH - is hard, but the decisional version of the DH problem - the DDH - is easy. Below I'm using the notation from the wikipedia article on BLS.

Just recall, that the DDH in a group $(G, g, r)$ (where $g$ is a generator and the group $G$ is of prime order $r$) is that, when given $(g, g^a, g^b, g^c)$, it's hard to decide whether $c=ab$.

If you look at the BLS signature verification, one checks whether the signature $\sigma$ for message $m$ has the form $\sigma=H(m)^x$ and writing it as $(g,h=g^x, H(m), \sigma)$, one sees that verification is to check for a valid DDH tuple (CDH needs to stay hard for unforgeability). Note that $H$ is a hash function modeled as a random oracle that maps strings to elements of $G$. So $H(m)$ can be written as $g^\gamma$ for some unknown $\gamma$.

Now, the existence of a pairing $e: G\times G \rightarrow G_T$ (symmetric for simplicity) exactly makes $G$ such a gap group. The check $e(\sigma, g) = e(H(m), h)$ in the signature verification exactly allows you to test if $(g,h=g^x, H(m), \sigma)$  is a valid DDH tuple. Using bilinearity of $e$, this should be easy to see, and I leave it as an exercise to you.

Pairings used in cryptography have evolved into a large (rather quickly changing) field and requires some time to study them. But the above symmetric pairing can be instantiated e.g., by setting $G$ as a subgroup of a supersingluar elliptic curve group, $e$ being the Weil pairing and $G_T$ a subgroup of the multiplicative group of a quadratic extension field of the curve's base field (you may want to look here for details). The choice of $H$ also depends on the setting, but it is crucial that $H$ is constructed such that one does not learn the discrete logarithm to the base $g$ from $H(m)$. You could look at the original BLS paper,who instantiate the scheme in a so called Type-2 pairing setting (in their setting, $G_2$ is the gap DH group). You may also want to look at this paper for how you can instantiate BLS in other Types of pairings.


RSA in general is often considered to be "discouraged" for new projects. For quite some years, the rallying cry has been "switch to elliptic curves", but nowadays there are calls for going straight for so-called "post-quantum" schemes.
RSA benefits from having survived a lot of public scrutiny (arguably, integer factorization is a problem that has been studied for three millennia at least), and while there has been substantial progress in cryptanalysis, 2048-bit RSA key are likely to remain secure for a long time. There are also good and bad ways to use RSA for asymmetric encryption, but RSA-OAEP is about as good as you can get with RSA, so that's fine.
Elliptic curves offer better performance (on the decryption side) and are more fashionable. What this means is that before being actually broken, RSA may become disused, meaning that you will get interoperability issues, and implementations will be poorly maintained at some point. In my view, none of this is critical.
Quantum computers eat RSA keys for breakfast; however, they also munge through elliptic curves at lunch time, so that's not a good argument for switching to curves. It's a fortunate thing that quantum computers don't really exist yet (and whether they will exist at some point is an open question). "Post-quantum" schemes are algorithms that appear to resist quantum computers (specifically, these are algorithms for which no efficient quantum-solving attack is known – which does not mean that such attacks don't exist!). There is no real post-quantum drop-in replacement for classic algorithms yet (there are good candidates, but a lot of standardization and implementation deployment is still needed).


In contrast to asymmetric schemes (notably RSA and El Gamal) which require some sort of computation to generate the key, the only constraint one has when selecting a key for DES or AES (or 3DES) is to make it look indistinguishible from a random stream. That said both El Gamal and RSA require some randomness in key generation, but that phase does not depend just on that.

You could however use any byte stream of sufficient length as a key, irrespective or randomness, at your peril. That's because the security of these schemes (of all schemes really) depends on the inability of some adversary to compute or guess the key in some practical timeframe. It's worth mentioning here that DES keys can be (and have been) efficiently brute-forced because they are short in length. Search this site for randomness test or take a look at the randomness tag to get a better idea.

In practice it's possible to derive a key from a password, passphrase or a random stream of smaller length by using a key derivation function. You may also use any CSPRNG to generate a long enough stream, which you can use as a key.


Are Two Ciphers Better Than One? i.e. RC4 and AES

There exist several ways to combine multiple, distinct encryption schemes. Applying one after the other as you propose is one option but you could for example do a secret sharing first and then encrypt the shares with different algorithms. Each of those has its advantages and disadvantages. I am not aware of a combiner for this that provably amplifies security but you can manage to build a scheme that is guaranteed to be as strong as the weakest cipher used in the combiner (as long as you use independent keys of course). The drawback is obvious: You need to do about twice the work when combining two schemes and so on. Depending on the combiner you might also pay in bandwidth (See the secret sharing combiner). These are the reasons why folks hesitate to use this in practice although it would give far stronger long-term security guarantees if key sizes are chosen appropriately.


Time locked cryptography using Bitcoin difficulty param and/or smart contract?

Those are indeed the main known solutions. Note that your solution A has been explored in the cryptographic community, this paper is an example of a theoretical work on the subject, but I think there are others, more practical proposals for using the blockchain as a timer (it was discussed at length in a slightly different context in this recent paper).

Note 1: as far as I know, no such method has yet been evaluated and experimented in practice, yet alone deployed.

Note 2: a small correction to your first item, "proof of work": actually, a proof of work does not suffice here. This is because if the work involved is parallelizable, meaning the work can be divided across many CPUs, then there is no guarantee about the time it takes to complete the task - did the opponent use 1 CPU and time T, or T CPUs and time 1?

The right solution is to use proofs of sequential work, which demonstrate that the prover has executed T steps of a problem which is conjectured to be impossible to parallelize. Many examples exist, based mainly on the conjectured hardness to parallelize modular squaring (given a random $r$ and a modulus $n$, compute $r^{2^T} \bmod n$, where $n$ is an hard-to-factor RSA modulus). Many recent papers have worked on related constructions, e.g. look up "proof of sequential work" or "verifiable delay function".

A byproduct of using proofs of sequential work is that the work cannot be sped up with more CPUs, so the right user will just use a single CPU dedicated to solving it, which makes the work required somewhat less cumbersome (no need to have thousands of computers "farming" the proof).


Your observations are basically correct. Informally it is as follows: For a uniform PPT algorithm think of a fixed Turing machine that has access to some random tape and the output of the algorithm is a random variable. For non-uniform algorithms it is best to think of a family of circuits indexed by the length of the input (so for every input length the algorithm may exhibit a totally different behavior). But you may also see a non-uniform algorithm as a uniform algorithm that takes an additional input-length dependent "advice string" that helps the algorithm to solve problems of that size (to make a non-uniform algorithm uniform, simply pass always the empty string).

For formal definitions just check your beloved complexity theory book. When it comes to crypto, there has recently been some discussion about these two models (typically reductionists proofs are in the uniform model). You may look at the page of Menezes (non-uniformity) and follow up discussion.


$\log_n(x)$ means the base-$n$ logarithm of $x$. It returns a value $y$ such that $n ^ y = x$.

Since you're working with discrete logarithms, the base will probably be the generator $g$ for your group.

edit

$L_{13}(x)$ appears to be a shorthand way of writing the above. The only way to find out otherwise would be to consult the notation definitions from the paper (or author) if possible, because it could mean something else entirely or something more specific.


What is the difference between an anonymous-encryption scheme and an authenticated-encryption scheme?

authenticated-encryption scheme

This one takes the sender's public key $g^a$ and the recipients public key $g^b$ and using the currently available secret key ($a$ or $b$) computes $g^{ab}$ and derives a symmetric encryption key from that. This is called a static-static Diffie-Hellman key exchange. It provides authentication for the sender because only the sender knows the correct (static) $a$ to come up with the same shared secret as the receiver.

  anonymous-encryption scheme

They work the same as the authenticated one, but this time the sender picks a new $a$ for each message and includes $g^a$ as part of the ciphertext. This way anybody could have picked this $a$ - including an adversary that intercepted the ciphertext, dropped it and computed a new one. This uses a so-called static-ephemeral Diffie-Hellman key exchange and the security guarantees are not unlike those of an unsigned, encrypted PGP message.


Nomenclature of Certificate Authorities and Certificates in PKI

A CA certificate is a certificate which is used to sign other certificates. This is indicated by the Basic Constraints extension
A root certificate is a certificate which is self signed i.e. not signed by another CA cert
An intermediate certificate is any (CA) certificate in a certificate chain between the root and the leaf. Those are also sometimes called Sub CA. Usually, there is one such in a chain.
Super and subordinate means exactly what it says. Remember that you are working with a certificate chain.


Multiple random keys vs multiple keys derived from master key

If we put algorithmic details aside, the two have little to no difference.

But in reality, public-key encryption and key exchange algorithms are limited in the length of data they can directly exchange. For example, the size of the key that can be exchanged with ECC is directly related to the base-2 logarithm of the order of the curve being used.

Next, if we do exchange over-sized symmetric key with, say, bigger curves, we may not necessarily be able to use the entropy present in the exchanged key - the security of the whole cryptosystem is limited to its weakest component. Therefore, encrypting with a 256-bit key then MAC'ing it with another 256-bit key give you only 256-bit security, not 512-bit.

To summarize: Exchanging over-sized key is neither necessarily viable nor necessarily useful. Do use HKDF for saving communication overhead.


Converting Letters into Numbers for Creating an Authenticator

Normalize the input and encode it using UTF-8. That gets you octet strings. Then the particular block size depends on the system you're using. For Poly1305, treat 16-byte long octet strings as little-endian integers. RFC8439 provides the way to convert a message composed of bytes into appropriately sized blocks (for Poly1305, other such systems need different sizes):

o ...divide the message into 16-byte blocks.  The last one might be shorter:

o  Read the block as a little-endian number.

o  Add one bit beyond the number of octets.  For a 16-byte block, this is equivalent to adding 2^128 to the number.  For the shorter block, it can be 2^120, 2^112, or any power of two that is evenly divisible by 8, all the way down to 2^8.

o  If the block is not 17 bytes long (the last block), pad it with zeros.  This is meaningless if you are treating the blocks as numbers.


Eureka: this looks like a variant of Håstad's broadcast attack after all. We workaround the different $e_i$ by using the Least Common Multiple of an adequate subset of the $e_i$, and can still succeed if the bit size of $M$ is low enough.

Among the 11 subsets of $\{1,2,3,4\}$ with more than 1 element, find which minimizes the quantity $\operatorname{lcm}(e_i)/\displaystyle\sum\log_2(N_i)$ where the Least Common Multiple and the sum are computed for $i$ in the subset. In the rest of this section, $i$ varies in this subset.

Compute $e=\operatorname{lcm}(e_i)$. Compute $D_i\gets C_i^{(e/e_i)}\bmod N_i$. It holds that $D_i=M^e\bmod N_i$. That allows to compute $y=M^e\bmod\left(\displaystyle\prod N_i\right)$ using the Chinese Remainder Theorem.

If we are lucky enough that $m<\left\lfloor\sqrt[e]{\displaystyle\prod N_i}\right\rfloor$ (roughly, $m$ of bit size less than $1/e$ of the sum of the sizes of the moduli in the set), then $y$ will be exactly the $e^\text{th}$ power of some integer $x$, we can get that $x$, and it will be $M$.

If not, we can try, for incremental $j$, if any if the $y_j=y+j\displaystyle\prod N_i$ is exactly an $e^\text{th}$ power; that slightly extends the attack.

If that does not work, we are left with generic attacks that do not take advantage of the operational goof of using the same $M$ for multiple recipients:

Common prime: We can compute $\gcd(N_i,N_j)$ for the 6 $(i,j)$ with $i<j$, and if any of these is not $1$, we have factored $N_i$ and $N_j$ (for two-primes RSA). With a full factorization, we can decipher the normal way. This attack has occasionally succeeded on deployed cryptosystems, an example is related there.
The $e^\text{th}$ root attack: perhaps $M$ is small enough that $M^{e_i}<N_i$ for some $i$. We can chose the $i$ with the smallest $e_i\log_2(N_i)$ and try if $\sqrt[e_i]{C_i}$ is an integer, in which case that integer is $M$. We can similarly try $\sqrt[e_i]{k\,N_i+C_i}$ for small $k$.
Search of $M$: If there's context about $M$ (like, it's a credit card number in ASCII, or a password), it might be possible to find it by enumeration. We can check a guess of $M$ with the $(C_i,N_i,e_i)$ allowing the fasted test of $C_i=M^{e_i}\bmod{N_i}$.
Meet-in-the-middle search of $M$: it is reasonably likely that $M=X\,Y$ for sizable integers $X$ and $Y$, $X<Y$, in which case there is an attack of cost $O(Y)$ with $O(X)$ memory. For the appropriate $i$ as in 3, it tabulates candidates $X^{-e_i}\,C_i\bmod{N_i}$, then searches among these candidates $Y^{e_i}\bmod{N_i}$. A match reveals $X$ and $Y$, thus $M$.
Factoring an $N_i$: if any recipient uses a key generator with a flaw, including too small an $N_i$, it might be possible to factor that $N_i$, then decipher normally.

Only attack 1 is specific to multiple keys. The others simply select the most vulnerable key.

All attacks in this answer fails for RSA as correctly practiced. 1 and 5 fail for proper key generator. Other attacks fail when what's raised to the power $e$ modulo $N$ is a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.


How to pad a 448 bit message for SHA256?

The padding method for SHA-256 is (assuming you're byte oriented - it appears you are) is 'append an 0x80 byte, and then add 0x00 byte's until the length modulo 64 bytes is 56.  This implies that if the original message length modulo 64 is 56 or larger, you'll need to do one more hash compression operation.

That means that your computation of the number of hash compression operations you'll need:

if (len % 64) {
    blocks = (len + (64 - (len % 64))) / 64;
} else {
    blocks = (len / 64) + 1;
}

is wrong; if len=56 (in this case), this sets blocks=1 (and thus you don't allocate any space for the padding).  More correct would be:

/* Compute the number of bytes of the message plus mandatory padding */
plen = len + 9;   /* 1 for the 0x80 byte, 8 for the length */

/* Number of blocks is the number of message plus padding bytes */
/* div 64, rounded up */
blocks = (plen + 63) / 64;

Also, the number of 0x00 bytes you'll need to add between the 0x80 byte and the length field is precisely 64 * blocks - plen


Is there a block cipher mode that doesn't use the key input of the block cipher?

This is the difference between block-encryption (with a mode) and permutation-based encryption.

I. Block encryption

Split your message in blocks of the width of the block-cipher, apply a transformation (XOR of the previous ciphertext, XOR of an IV you name it...) and then apply the block cipher.

On a high level, it can be summarized as the following Figure where $K$ is your key, $P_1 \ldots P_n$ are the plaintext blocks, $randomize$ correspond to an operation trying to remove similarity between blocks (remove ECB...) and $C_1 \ldots C_n$ are your ciphertext blocks.

           P_1                 P_2                     P_n

            |                   |                       |
         randomize           randomize               randomize
            |                   |                       |
       +----v----+         +----v----+             +----v----+
       |         |         |         |             |         |
   K ->|    B    |     K ->|    B    |  ...   K  ->|    B    |
       |         |         |         |             |         |
       +---------+         +---------+             +---------+
            |                   |                       |
            |                   |                       |
            v                   v                       v

           C_1                 C_2                     C_n

Of course one could argue that CTR does not work that way, but the principle is the same, you encrypt the counter and XOR the result to the plaintext.
In the end, the process is very similar.

Note: If you are using a different key for each block, you are doing it wrong...

II. Stream encryption

This mode does not requires you to split your plaintext in blocs. You just generate a keystream and Xor it. Nothing fancy, simple, fast and efficient.

                   K

                   |
            +------v-------+
            |              |
       IV -->   Stream     +----+  Keystream
            |              |    |
            +--------------+    |
                                v
Plaintext ----------------------+---> Ciphertext

Examples of this construction are Chacha20, Salsa20...

III. permutation-based encryption

Permutation-based encryption works in a similar fashion as the stream and the block encryption. The key is set at the beginning of the encryption and not used after. The message is split into chunks. This mode is based on a sponge construction

The key stream is then XORed with the message, resulting in the Cipher text.
Examples of this construction are Keyak, Ketje, NORX...

IV. Going further

From that permutation based mode, you can use it in a session style, removing the need to have a key once the session has been initialized.

More readings:

- FSE 2017 - Innovations in permutation-based encryption and/or authenticationInvited Talk by Joan Daemen


We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power cyclotomics for “packing” and SIMD operations on plaintexts.
However, it is simplest to properly define and use RLWE over two-power cyclotomics, in large part because one can easily avoid using the “codifferent” (fractional) ideal $R^\vee$. (Other associated operations, like the NTT/CRT algorithm, are simpler in the two-power case as well.) So, this is probably why people tend to stick with two-power cyclotomics for RLWE.
The use of fields other than two-power cyclotomics can be justified by theory. The original LPR’10 paper proved the hardness of search-RLWE over any number field (not just cyclotomics), based on the conjectured quantum hardness of worst-case approximate-SVP on ideal lattices in that same number field. It also proved the hardness of decision-RLWE, assuming the hardness of search, for any cyclotomic number field (whether two-power or not); it turns out that this proof also works just as well for arbitrary Galois number fields, e.g., multiquadratics. Later, Peikert—Regev—Stephens-Davidowitz’17 directly proved the hardness of decision-RLWE over any number field (whether Galois or not), based on the same assumption as in the first sentence of this paragraph.
As for whether we can use quadratic fields, all of the above applies equally well for them, but the dimension is so small that worst-case SVP is easy—even on arbitrary lattices, not just ideal lattices. Similarly, RLWE over a quadratic field is trivially easy (except possibly if one used an enormous modulus, but this is not typical).


ECDSA signature of a random 32 byte number vs. the hash of the number

Yes, but you probably need to use a cryptographically secure RNG from your OS. Otherwise the input to the signature generation function may be mathematically linked, and the security of the system is not guaranteed. It is of course wise to use a 256 or higher curve, otherwise the security provided by the random number may be lowered.

Besides compressing the input, the hash is used to generate pseudo-random input to the signature generation function. It removes any mathematical links between the input values as cryptographic hash functions are one-way. However, using a small enough, random / independent values should already meet these requirements.

Random number generation by the OS is likely to be significantly slower than performing a single hash over a single block of input.

In that sense you could think of using 128 bit numbers instead of 256 bits and perform full ECDSA on that. You could also think of using deterministic ECDSA as specified in RFC 6979. These changes may well have a larger impact than removing the relatively fast hash from ECDSA. And you'd still be standard-compliant to boot; all of the security requirements on ECDSA would still be met.


Is client certificate mandatory for two-way TLS?

Strictly speaking, there is no such specification as "two-way TLS". It is rather an informal expression. It means a TLS connection with mutual authentication based on PKI.
If you use anything else for client authentication, but not TLS/SSL certificates, then it is not a two-way TLS. I'd suggest to use other words, because improper wording leads to misunderstanding and wrong expectations of all people involved: customers, developers, testers, auditors, etc.
To your questions:

does the client necessarily send its certificate?

Yes. Otherwise it is not a "two-way TLS".

What if the client sends a credentials (E.g token/API key) that the
server knows and validates to verify the identity, is this not a
mutual authentication and two-way TLS?

It is not a "two-way TLS". It does not mean that it is better or worse for particular purpose. It just means we cannot call it "two-way TLS".


What is the usual block cipher mode that goes with CTS

There is a NIST definition of CTS (CipherText Stealing) mode in the addendum to NISTSP800-38A.

The title of that addendum answers the question:

  "Recommendation for Block Cipher Modes of Operation: Three Variants of Ciphertext Stealing for CBC Mode".

The paper is also useful to understand that there are many different ways to do ciphertext stealing.


Testing whether a secret value is zero without security bits (in SPDZ)

Secure zero-testing without working in a large field can be done with a protocol by Lipmaa and Toft, and with similar efficiency to the Catrina and de Hoogh protocols.

The basic idea is to open $m = x+r \bmod p$, where $r$ is a uniformly random field element and the parties have shares of the bits of $r$.

The parties will test whether $m$ equals $r$ by computing shares of the Hamming distance $[H] = \sum_i (m_i + [r_i] - 2m_i[r_i])$ (which is $\sum m_i \oplus r_i$). Note that $x=0$ iff $H=0$.

They test whether $H = 0$ with a polynomial interpolation trick - this can be done with around $\log p$ multiplications since $H \le \log p$, and most of these can be preprocessed in advance (see Section 3.1 of the paper for the details).


How many starting keys should I choose?

The answer lies in the storage size and lookup time in the table. For example; if we split the $2^{40}$ into $t$ and $l$, the size of the chains and the number of chains, respectively. Let say $t = 2^{20}$ and $l = 2^{20}$

$t = 2^{20}$ chains;

Storage: $2* 64 * 2^{20} = 2^{27}$-bit that is $2^{21}$-Byts storage size.
Sorting: Only once you need to sort the $2^{20}$ chains ends by $\mathcal{O}(n\log n )$ time is $\approx 20*2^{20}$
The lookup time: at most for $2^{20}$ chains we have $2^{20} *\log_2(2^{20})$ by binary search.

You can use this site to calculate the parameters.

  If I just use N/k, my intuition would be that all the keys should end up being tested in one chain, but can we be sure of that?

No, we can not be sure about this.

  To me blowfish is bijective (since reversible) on the plaintext, but how can I be sure that two keys won't give the same encrypted text?

There is no problem in the password cracking case; you found a valid one.

  What reduction functions should I use? It seems to me like this would play a crucial role in making sure that all of my search space has been done.

$(H(k_{i-1}+i))$, $H$ is a hash funtion,  $k_{i-1}$ output of the previous node in the chain, $i$ the $i$-th node. Strip the $H$ to 64-bit.

  If the two assumptions above don't hold, is there an efficient way to know which keys still haven't been tested to make sure they are used to generate new chains?

Other than storing them, no.


What is / How would I calculate the number of bits(?) I need to make the probability of a collision very small?

If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret r Base64 characters long, every s seconds, for each of u number of users, where the probability of collision is very small, how would I calculate the length of the string that was needed?

Well, the probability that two specific users get the same r secret is $2^{-6r}$; there are $u(u-1)/2$ distinct pairs of users, hence the probability that there exists a pair somewhere with the same secret is no more than $2^{-6r} u(u-1)/2$ - with the values of $r, u$ you mentioned ($r=32, u=100,000,000$), this is tiny (circa $2^{-138.8}$, and so we can safely ignore that.

Now, the probability that, during a specific s second time interval, that two specific users get the same n character sequence is $2^{-6n}$; again, there are $u(u-1)/2$ distinct pairs of users, hence the probability that there exists a pair somewhere with the same output is no more than $2^{-6n} u(u-1)/2$

Now, you suggest $n=8$, if you plug that into the above equation with $u=100,000,000$, you get a value larger than 1 (hence that provides no meaningful bound on the collision probability, and in practice means that there likely exists several collisions).

To deduce what $n$ would need to be to make the probability bounded by $10^{-6}$, we would need to solve the problem $10^{-6} \ge 2^{-6n} u(u-1)/2$; solving this numerically for $u=100,000,000$ gives $n \ge 12.014...$; that is, an $n$ of 12 isn't quite enough to give you the probability you're looking for (but it's close).

Now, if you want that $10^{-6}$ probability to span over $k$ intervals (that is, that there is a collision anywhere in the $k$ $s$-second span, you'd need to solve $10^{-6} \ge k \cdot 2^{-6n} u(u-1)/2$


Does it make sense to use slow hashes in digital signatures?

No it's not useful to use slow hashing in such a situation.

The relevant attacks against the hash in a digital signature are second pre-images and sometimes collisions. Assuming the hash-function is secure, then there is no way to find collisions with less work than $2^{n/2}$, and second pre-images with less work than $2^{n}$. There is no weak part the attacker can abuse in his attack, so he needs to face the full strength of the cryptographic hash.

As long as the algorithm remains unbroken, we can make the problem exponentially difficult for the attacker, while increasing the cost only linearly(or something similarly low) for the defender. In short we don't fear high computational power, we only fear crypto-analysis.

With password hashing, the relevant attack is a first pre-image. The problem here is that typical passwords have a low entropy, i.e. they're easy to guess. When guessing the original password the attacker doesn't care how strong the hash-function is, he simply executes it with many different inputs. We use slow hashes here, to increase the effective strength of the password by perhaps 20 or 30 bits.

There is no way to slow down the attacker exponentially while slowing down the defender only by a little bit. That's because the attacker has the same knowledge as the password verifier, and does exactly the same thing as the verifier. Any slowdown hits the defender just as much as the attacker.

The only thing we can try is to minimize the advantage an attacker gets from specialized hardware, and make the hashing as slow as the defender can afford. This is a desperate measure that's only used because no good defense is available.


Constructing Bent functions of 8 variables

You cited the theorem wrong. It is:
If $f(x)$ and $g(y)$ are bent, then $f(x) + g(y)$ is bent. The difference is, that the functions are not on the same variables. Otherwise you could use $f(x) = g(x)$, and then you get $f(x) + f(x) = 0$, which clearly isn't bent.

By applying above theorem multiple times, this should be bent:
$f(x_1,\dots,x_8) := x_1 x_2 + x_3 x_4 + x_5 x_6 + x_7 x_8$

I would suggest studying this presentation by Sihem Mesnager, where sections 5 adresses direct constructions and section 6 adresses secondary constructions (built from other bent functions):

Slide 30 has explicit direct constructions
Slide 42 ff. has the above theorem and other constructions from bent functions. Interesting: Slide 44 has a constructions of three bent functions over the same variables.


Ed25519 or more general the EdDSA (Edwards-curve Digital Signature Algorithm) approach can be considered as a variant of ElGamal signatures (such as Schnorr or DSA). They all are signatures following the hash-then-sign approach. This simply means that you can sign arbitrary length messages by hashing them to a constant size string using a secure cryptographic hash function and then applying the signing algorithm to the hash value. Such as other ElGamal type signature schemes like ECDSA, when implemented using elliptic curve groups, the security relies on the elliptic curve discrete logarithm problem on the respective curve group.

The hash-then-sign approach, however, must not be confused with quantum resistant hash-based signatures such as Merkle signatures, Lamport signatures or the Winternitz one-time signature scheme. Such signatures do not rely on any (number theoretic) computational hardness assumption such as factoring or discrete logarithm assumption and thus are not susceptible to quantum attacks.


7-Zip Encryption: Practical Effect of Lacking Salt

The absence of salt is a severe shortcoming only where the cracker seeks access to multiple 7z files. But why would that make a difference?

If there is a password verification method and there is no salt, then password search can be batched. Calculate one hash and test for all targets. If you consider that the 7Zip uses SHA-256 with $2^{19}$ iteration this is a huge reduction in the attacking timing.
The batching is usually performed by building a rainbow table in advance for the small size of passwords including the known passwords. This highly reduces the attack time if the target passwords are on the table.
If the attacker has only one file, then this doesn't matter; instead of building the table, just search. For further usages building the table is preferable.
It seems that 7zip doesn't use a password verification method. One has to decrypt and unzip the file. If during this process there is a format error the process will stop. This severely affects the performance of batching. Still, the attacker can generate the hash of the password and test for all targets this is faster than one by one for each file.
In any case use passwords with good strength like passwords generated from dicewire or Bip-39. If you have a password that has strength > 128 then you are safe against the attacker even the batch.
Note that there is no detailed information about the experiment made with Elcomsoft. Does it a single password or multiple password search. It seems a single search. The article is not well written in this sense.
The less number of password tries is due to the number of iterations.

The absence of salt in 7-Zip is moot if I use some other AES-256 tool with salt to create a 7z file.

Lack of Salt is not a real problem for a power user. Just generate a salt and carry it with the 7zip file. During the key generation prepend the salt to yo your password.
For normal users, the salt must be used against the batch attackers.


Purpose of hashing last block in Merkle-Damgård?

The purpose of hashing the last block is simply to prevent leaking information like, $L$, the length of the input. It's also important so that if $L\leq \langle 2 \rangle$, then $H$ is still compressing the input.

That being said, if you don't hash the last block of the Merkle-Damgård transform, $H$ is still collision-resistant, assuming that $h$ is collision resistant.

Let $\Pi=(Gen,H)$ and $\Pi'=(Gen,h)$. Assume $h$ is a collision-resistant hash function. Suppose for a contradiction that we can find a poly-time adversary $\mathcal{A}$ that finds a collision in $H$ with non-negligible probability $\delta(n)$. We will now construct a poly-time adversary $\mathcal{A}'$ that will find a collision in $h$.

$\mathcal{A}'$ begins by running $\mathcal{A}$ and finding a collision in $H$ such that $H^s(x)=x_B\Vert L=x_B'\Vert L'=H^s(x')$ and $x\neq x'$. Since the length is sent in the open and $x_B\Vert L=x_B'\Vert L'$, then it must be the case that $L=L'$. Define $\mathcal{A}'$ to output whatever $\mathcal{A}$ outputs.

Because $|x|=|x'|=L$, then we can find a collision by proceeding inductively. Since $x\neq x'$, then there must exist some $i$ where $1\leq i\leq B$ such that $x_i\Vert z_{i-1} \neq x_i'\Vert z_{i-1}'$.

Working backwards from the output, find the first such $i$. It must be the case that $h^s(x_i\Vert z_{i-1}) = h^s(x_i'\Vert z_{i-1}')$ and so we have found a collision in $h$. Have $\mathcal{A}$ output $x_i\Vert z_{i-1}$ and $x_i'\Vert z_{i-1}'$.

But this means that we have found a collision in $h$ by calling $\mathcal{A}$ only a polynomial number of times which implies that $\mathcal{A}'$ also runs in polynomial time i.e.
$$\text{Pr[Hash-Coll}_{\mathcal{A}',\Pi'}(n)=1]$$
is not bounded by any negligible function, contradicting the collision-resistance of $h$.


I think i got it.

Query:

Let $m={1,2}$, and query $oracle(m)=(A,B)$

Checking:

Lets compute $s=B^e=(m^er^e)^e=m^{e^2}A$

Lets compute $sA^{-1}=\frac{m^{e^2}r^{e^2}}{r^{e^2}}=m^{e^2}$

if $s=1$ then $m=1$, $m\neq 1$ otherwise

Hopefully logic holds.


What encryption/decryption system should I use for media server

"but it really doesn't discuss the part of users not able to decrypt the files using other tools." ... yes it does, because it discusses key management. As by Kerckhoffs principle, you should not try and secure the algorithm itself, security relies on the keys. Tools that receive the correct keys should be able to decrypt the media.

You can of course embed a secret or private key in the app, and require both the keys from the discussed scheme and the app key. It would however just take a single reverse engineering of the app to nullify the additional protection.

The practical way on how keys can be protected on the specific devices (e.g. using device specific key stores) is off topic for this site.


What is blindness and forgeability in Chaum's blind signature scheme?

It (Blind Signature) is unconditionally blind, because if you take a blind message $m\cdot r^e$ and then sign it, you get $m^d \cdot r$ which distributes like a random element in a subgroup of $Z^{*}_{N}$ so even if you have unlimited computational power you can't extract $m^d$ from looking at $r \cdot m^d$. Even if you factor $r \cdot m^d$ you won't know for sure which parts belong to $r$ and which to $m^d$.

However if you have infinite computational power you can just find $d$ from $(N, e)$, hence it is conditionally (computationally) un-forgable.


Can anyone give an example where (asymmetric) crypto can go wrong due to selection of wrong groups?

Basically, every time you choose a group where the required hard problem is not hard, then you will run into a problem. Even if we have a problem instance that is of size that is considered secure in the setting of asymmetric cryptography.

Lets for instance implement a discrete logarithm style cryptosystem in the group $Z_n$ with addition and let $g$ be a generator. Then the discrete logarithm problem in this group is given $g$, $y$ you have to find the discrete logarithm $x=\log_g(y)$, i.e., compute $x$ such that $y\equiv xg \pmod n$. However, you can efficiently solve this linear congruence by using Euclid.

Consequently, the discrete logarithm problem in the group $(Z_n,+)$ is easy and thus every discrete logarithm based cryptosystem will be insecure in this setting.


Why not authenticate full-disk encryption?

Authentication and probabilistic encryption are two desirable features which each take up a small amount of extra space. And you are absolutely right that the percentage of space consumed is of no concern in most scenarios.

But as the other answers also point out that means you can no longer fit a logical sector inside a physical sector of the same size. That is a significant practical problem.

In terms of reading it is not a major issue. For example if every 512 byte logical sector requires 592 bytes to be physically stored on disk, you could simply store every group of 32 contiguous logical sectors in 37 contiguous physical sectors.

In such a layout you have the small percentage of slowdown for sequential reads which is to be expected. And each seek is also slightly more expensive because you would need to read one extra physical sector each time you have done a seek.

The real problem is writing. Most of the time when writing a range of logical sectors the first and last sector will only need to be partially written. That means the encryption layer has to read the original, update it, and write it back. That costs expensive additional seeks. Moreover the encryption layer might not know beforehand which is the last sector to be written, so it might end up doing the read-modify-write cycle for sectors in the middle of the range to be updated.

But it gets worse. If the operation is for some reason interrupted (for example kernel freeze or power failure), the cycle may not have been completed, which can corrupt your data.

If the physical disk guarantees atomic updates, the logical layer would not guarantee atomic updates. Instead the logical layer would potentially leave you with a logical sector which produce read errors on every attempt to read.

If the physical disk does not guarantee atomic updates, it gets even worse. The last physical sector written could contain data related to two or more logical sectors. If it got corrupted because of a power failure during write, the logical layer would not only lose the logical sector being written but also other nearby logical sectors which were not even being written to at the time of the power failure.

Very similar problems exist at the file system layer, where one common solution is a journal. But introducing another journal at the block layer means more slowdown and extra disk space usage.

This overhead could be mitigated by moving the encryption to the file system layer. But storage encryption is difficult enough to get right as it is, integrating it with the file system layer makes it a lot more complicated and thus more error prone.

There is another layer of complexity once you realize that protecting the integrity of individual sectors is not even sufficient. If each sector is individually protected by a MAC (or similar) an adversary could selectively revert individual sectors to an earlier point in time.

By selectively reverting a subset of sectors the adversary can construct contents which does not match any earlier point in time.

To see why this is bad imagine a file was deleted and the sectors it covered were reused for a different file. The adversary could combine the metadata from when one file existed with the data sectors from when the other file existed. This means the adversary has successfully moved the protected data from one file to another. If one of the files was highly confidential and the other was one that you would happily share with anybody, the adversary would be able to trigger a leak of confidential data.

You could protect against this by computing a hash-tree over the disk and storing a MAC of the root of this tree. This makes updates even more complicated, and updating a sector is now going to take logarithmic time rather than the constant time we were used to.

The worst problem however is that you still need to protect the integrity of the crypto code. If the code to do all the cryptography is not protected, an adversary could simply modify that code to bypass all the security measurements. And not only the crypto code itself, but also all the code used to bootstrap the system to the point where it can start reading the encrypted disk needs to be protected.


How would Keccak attain a 512-bit security level?

The highest capacity possible is 1599, which means you repeat the permutation for every bit you enter into the state.

For a ‘512-bit security level’ (which is (completely meaningless)^2, since a 256-bit security level is already past the threshold of meaning), it suffices to choose capacity 1024 and digest length 1024 to thwart all generic classical and quantum attacks limited to $2^{512}$ cost.

The SHA-3 parameters for the fixed-length functions SHA3-256 etc. were overdesigned partly out of paranoia and partly for political reasons.  The XOFs SHAKE128 and SHAKE256 were more reasonably designed to give a 128- or 256-bit security level, respectively, assuming adequate output length; if ‘SHAKE512’ existed it would use capacity 1024.


Identifying and attacking a proposed cipher (multiple substitution)

The obvious way to approach this would be to attempt to recover the cycle structure of the permutation, and the first place to start is to attempt to reconstruct the order of each letter.

The "order" of a letter is how many times the permutation needs to be applied to the letter before it turns back to that letter.

To start, you believe that you have the matting x -> x; that means that the order of the letter 'x' is 1.

Let us extend that idea, if we have the mapping e -> w -> g -> e, then the order of the letter 'e' (and 'w' and 'g') is 3.

So, how do we estimate the order of a letter?  Well, we start be looking at every 'n'th letter of the ciphertext (that is, positions 0, n, 2n, 3n, etc); if the order of a letter is n (or a divisor of n), then in those positions, that letter will map to itself (and so the character frequency in those positions of the ciphertext will be exactly the character frequency in the plaintext); assuming that the plaintext is English text, it should be fairly straightforward to come up with plausible guesses.

Once you've tried that, and have come up with plausible guesses for the orders of all the letters, we then need to reconstruct the 'cycles' that make up the permutation.  The first obvious place to start is to find the element that e maps to; if we have found that the order of e is 3, we can start by looking at every 3rd element offset by 1 (e.g. at locations 1, 4, 7, 10, 13, etc); in those locations, 'e' will encrypt to whatever letter it is permuted to, and so if in those locations, the letter w happens exceedingly often, we can deduce that e -> w is a likely mapping within the permutation.

Those hints should give you a good start...


What’s the difference between a Fast wide pipe and a Narrow pipe construction?

Of an iterated hash function $$H(m_0 \mathbin\Vert m_1 \mathbin\Vert \cdots \mathbin\Vert m_{n-1}) = g(f(\cdots f(f(\mathit{IV}, m_0), m_1)\cdots, m_{n-1})),$$ for functions $f\colon \{0,1\}^s \times \{0,1\}^k \to \{0,1\}^s$ and $g\colon \{0,1\}^s \to \{0,1\}^h$, narrow pipe, as introduced by Stefan Lucks, just means that the intermediate state is no larger, or not much larger, than the final output: $s = h$.  Wide pipe means $s \gg h$.

In SHA-256, the intermediate state has $s = 256$ bits just like the output; thus SHA-256 is a narrow-pipe iterated hash function.  In SHA-512/256, the intermediate state has $s = 512$ bits and the output has $h = 256$ bits; thus SHA-512/256 is a wide-pipe iterated hash function.  In SHA3-256, the intermediate state has $s = 1600$ bits while the output has $h = 256$ bits; thus SHA3-256 is also wide-pipe.

In principle, SHAKE256-1600 would be considered narrow-pipe too, but such distinctions are not really used much these days; they don't illuminate relevant security properties very well.  The attacks that Lucks hoped to thwart with wide-pipe constructions are usually addressed in other ways instead, and we aim for security targets rather than pipeyness.


Use MDC to provide origin authentication for public key encryption?

Public key encryption uses a public key of the receiver; anybody can encrypt. So origin authentication would only work if you'd also have a shared secret key (in which case the whole public key encryption becomes kind of useless) or a private key (in which case you'd probably use a signature or an authenticated key agreement protocol).


OK, so let's go from start to finish on this.

Note that for a hash function we can model the output bits as independent binary variables and thus apply a binomial distribution model to find out how many bits take a certain value. So the Probability that $k$ bits don't match is $\binom{n}{k}2^{-(n-k)}2^{-k}=\binom{n}k2^{-n}$ (intuitively we aggregate all possible allowed missmatches here). Now we want that at most $k$ bits don't match and thus we can sum: $\sum^k_{i=0}\binom{n}i2^{-n}$. Now note that $2^{-n}$ is a constant factor and thus $p=\sum^k_{i=0}\binom{n}i2^{-n}=2^{-n}\sum^k_{i=0}\binom{n}i=\frac{\sum^k_{i=0}\binom{n}i}{2^n}$, now finally we can use said birthday argument to find the number of messages needed to be $\sqrt{\frac1p}=\sqrt{\frac1{\frac{\sum^k_{i=0}\binom{n}i}{2^n}}}=\sqrt{\frac{2^n}{\sum^k_{i=0}\binom{n}i}}=\frac{2^{n/2}}{\sqrt{\sum^k_{i=0}\binom{n}i}}$ which is the expected result.

Note as mentioned in this answer, this result can be proven more rigourously as well, which was done in "Memoryless Near-Collisions via Coding Theory" by Mario Lamberger, Florian Mendel, Vincent Rijmen and Koen Simoens (PDF).


Is a new block cipher harder to design than a new hash?

There are standard constructions for block ciphers and hashes that can be instantiated with a given "mangling function", where the "mangling function" is a fixed permutation such as keccak-f, or for another example Rijndael without the addRoundKey layer.

There are really two different things you might design: A new construction that uses a permutation, or a new permutation for instantiating a given construction*.

Instantiating a known construction with a new permutation

If you want to develop a new permutation and instantiate a key-alternating block cipher or sponge construction for hashing, then they are more or less challenges of equivalent difficulty. There are some differences.

One of those differences has to do with how you calculate how many rounds the resultant design will require to be secure. A hash function does not use a secret key, and so an adversary has an easier time crafting inputs that will target the weak points of the design. So an unkeyed hash function will tend to require more rounds than a block cipher to achieve the target security goal.

A permutation designed for a hash function may also be larger than one designed for a block cipher. This may seem like a trivial detail, but with vectorized designs MOV instructions into vector registers are expensive, and there usually are no vector rotate instructions. Using SIMD (single-instruction-multiple-data) efficiently is more challenging than not using it at all, but you can't make a big permutation that is fast without it.

A block cipher tends to incorporate a key schedule of some kind, which is a requirement that will not necessarily be present when designing a hash function. If you are using a block cipher in a Merkle–Damgård construction then the key schedule will be relevant to the security - this is where the related-key attack model is relevant.

It may be slightly easier to design a permutation for a block cipher than a hash function if you can get away with a 128-bit block size, due to not having to muck about with SIMD.

Designing new constructions

The other game to play is: Suppose you are given a permutation such as keccak-f. How can you create a block cipher with it? How can you create a hash function with it?

This game is arguably more open-ended and challenging than the previous one. If you want to find a construction that is not simply a variation on a pre-existing construction, you may have a lot of thinking to do.

In this case you can't really answer whether coming up with a new block cipher or hash construction would be more challenging than the other - how can you rate the difficulty of coming up with novel ideas that you don't know of yet? Who's to say whether Merkle–Damgård style hash functions were harder to come up with than Feistel networks, especially when you assume that you don't yet know of the existence of either type of construction?

* It doesn't have to be a permutation (which is invertible), but it helps to keep the answer simple and on-point to only consider permutations.


What is the meaning of h(r) in this protocol?

As Ricky Demer already mentioned, $h$ is a hash function.

In the realms of cryptography, it mostly points to a secure hash function. But in the end, it doesn’t matter if it’s a secure hash or not… $h$ is standard notation for “hash”.


Non-repudiation isn't a part of cryptography?

That is clearly a simplified definition, as cryptography encompasses a large number of ideas. It is likely for the same reason that they do not mention zero-knowledge proofs or proof-of-work systems, despite those very often falling squarely in the relm of cryptography.


How is the One Time Pad (OTP) perfectly secure?

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext.

This is not true as you have observed.

The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this:

  Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$ is perfectly secret if for every
  probability distribution over $\mathcal M$, every message
  $m\in\mathcal M$, and every ciphertext $c\in \mathcal C$ for which
  $\Pr[C=c]>0$:

  $$\Pr[M=m\mid C=c]=\Pr[M=m]$$

In other words, if you have the ciphertext at hand, you won't learn anything new that you didn't already know about the plaintext.

The OTP satisfies this (proved in "Introduction to Modern Cryptography") and thereby is perfectly secret as an encryption scheme. In short it first shows that $\Pr[C=c\mid M=m']=2^{-l}$, then uses this to show that $\Pr[C=c]=2^{-l}$ and concludes via $\Pr[M=m\mid C=c]=Pr[M=m]$ (using Bayes' theorem).


How feasible is a preimage attack or speedups to brute force a substring of MD5?

Right now, the cheapest known algorithms for (partial) preimage search are generic algorithms, costing ${\sim}2^b/t$ to compute a preimage for any of $t$ target $b$-bit strings in time ${\sim}2^b/t^3$ if parallelized $t^2$ ways—here $b = 128 - 24 - 4 - 20 = 80$.

The Sasaki–Aoki algorithm, while perhaps theoretically interesting, costs about a petabyte of memory, when at much lower cost you could power 32 CPUs (or just MD5 circuits) instead and get an answer faster with a naive generic search in parallel.


Are block ciphers used in public key crypto?

Yes, block ciphers are used in public key cryptography, though typically as auxiliary building blocks rather than as the heart of the public key scheme by themselves.

One example is in digital signatures: many use a hash such as SHA-1, to digest the message being signed into a short cryptogram, and/or as part of a Mask Generating Function (loosely speaking: used as a randomizer before applying a public-key primitive). And in turn many hashes, including SHA-1, use a compression function built from a block cipher. Sometime, the function of a Mask Generating Functions is directly performed by a block cipher, as in this proposal.

Also, as rightly pointed in this other answer, block ciphers are often used in combination with public key cryptography, to form a hybrid cryptosystem.


What is an "anonymous admissible timestamp"?

What he meant is quite unclear. It could be that he's referring to a Timestamping Authority (TA) (See related RFC like 3161). What they do is basically sign a document/hash with the current time and date and sequential transaction id (IIRC).

Ideally, the TA is public and anonymous, allowing anyone to submit any hash and get a signed timestamp for it, the list of signed transaction freely available for anyone to check and verify.

If I refer to the scenario, the bar could issue anonymous 'tickets' containing a unique and untraceable identifier, meaning the bar doesn't keep tabs (pun intended) to whom a given identifier belongs to. In practical terms, they might just have a check to avoid giving multiple tickets to the same person. When the user wants to get his beer, he gets a stamp from the TA by submitting the ticket content (or hash thereof), and forward the stamp to the bartender. Receiving the stamp, the bartender execute a lookup request to match the ticket to all the related transactions and check the date of the two last transactions (validating the stamp signature as well obviously). If they are separated by at least an hour, the stamp is deemed valid.


The details are explained in the WinZip documentation. It describes two encryption formats, termed AE-1 and AE-2. The format itself supports 128, 192, and 256-bit keys for AES in CTR mode, using PBKDF2-HMAC-SHA1 with 1000 iterations for key derivation. The salt is random and is half the size of the key. Help with decrypting data using a library is given elsewhere on the site.

You can verify that the decryption is correct by checking the password verification value:

  This two-byte value is produced as part of the process that derives the encryption and decryption keys from the password. When encrypting, a verification value is derived from the encryption password and stored with the encrypted file. Before decrypting, a verification value can be derived from the decryption password and compared to the value stored with the file, serving as a quick check that will detect most, but not all, incorrect passwords. There is a 1 in 65,536 chance that an incorrect password will yield a matching verification value; therefore, a matching verification value cannot be absolutely relied on to indicate a correct password.

The key is derived from the password using PBKDF2, explained as follows:

  Key derivation, as used by AE-1 and AE-2 and as implemented in Dr. Gladman's library, is done according to the PBKDF2 algorithm, which is described in the RFC2898 guidelines. An iteration count of 1000 is used. An appropriate number of bits from the resulting hash value are used to compose three output values: an encryption key, an authentication key, and a password verification value. The first n bits become the encryption key, the next m bits become the authentication key, and the last 16 bits (two bytes) become the password verification value.

General useful information on the PKZip format is also available here.


Generally speaking, a function $f()$ is linear if $f(x+y) = f(x)+f(y)$ and $f(ax) = af(x)$.

The AES S-Box, which is a specific, predefined (key-independent) lookup table, doesn't satisfy these properties. You can do a quick verfication by picking two values $x,y \in GF(2^8)$ and verifying that $S(x+y) \neq S(x)+S(y)$ (where the addition operation is done in the field $GF(2^8)$, and is thus essentially the XOR operation). But the S-Box not being fully linear is not enough. It's very bad if it's just somewhat linear, in the following sense. There are various ways to define it. One of them is the Linear Property of the S-box, $LP(S) = \max_{a,b} (Pr_x(a(S(x)) == b(x)) - \frac{1}{2})^2$ which has to be low. It measures the existence of two linear functionals $a(),b()$ which tend to agree (correlate) or disagree on the input and output of the S-box.
If you were to calculate $LP(S)$ you would find that it is considerably lower than for a random lookup table ("the maximum input-output correlation amplitude must be as small as possible").

As for difference propagation, a similar property exists $DP(S) = \max_{a,b\neq0} (Pr_x(S(x)\oplus a == S(x \oplus b)))$, which measures the existence of two  differences (deltas) $a,b \neq 0$ which propagate through the S-box. Again this has to be minimal, and if you were to calculate $DP(S)$ you would find it is indeed lower than for a random lookup table.

MixColumns offers linearity because it is defined as a linear mathematical operation, not because it is deterministic (the S-Box is also deterministic, but not linear...).


The most important thing you're missing is that you should combine the two strings with an injective function: a function such that every unique combination of inputs determines a unique output.

Your idea to just concatenate the two strings violates this condition.  One example is that "abc" + "def" is the same string as "ab" + "cdef" or "abcd" + "ef".  Whether an adversary can exploit this to their advantage depends on the application, but there's no reason to expose oneself to this risk to start with.

Some techniques for combining strings in an injective fashion:

Put an unambiguous delimiter between the strings
Prepend each string with its length

Another tip: whichever method you pick, write a function that can "split" any combined string back into its components, and a bunch of test cases to show that the property split(combine(strA, strB)) == (strA, strB) holds for all values of strA and strB.


RSA example-calculation: Public Key = Private Key (e = d)

The only reason you are seeing this is because you are dealing with such small primes. With primes like we would use in practice (1024 bits), the probability of this happening is very, very small. And, it can only happen when $e>\sqrt{\lambda(n)}$. Since we typically use $e=65537$ in practice, it is guaranteed to not happen.

Anyways, there is no mistake in your calculations, you just happened to pick an $e$ which is its own inverse.


The overhead of PKCS#1 v1.5 padding is at least 11 bytes. 8 of these bytes are a random value in the range [1..255]. This makes it unlikely that the same ciphertext is generated for identical plaintext input. Note that the padding is placed before encryption. The output size will be identical to the modulus size (in bytes, rounded downwards, if applicable).

Or, as PKCS#1 v2.1 puts it:

  Input:

  (n, e) :  recipient's RSA public key (k denotes the length in octets
              of the modulus n)

  M  :      message to be encrypted, an octet string of length mLen,
              where mLen <= k - 11

and, in case the plaintext message is larger:

  Error: "message too long"

(which in API's is translated into a runtime specific error, e.g. an Exception - which may well have a different error text - in Java).

Note that PKCS#1 v1.5 padding is used both for encryption as well as for signature generation. The v1.5 paddings used are however different for encryption and signature generation. I've focussed on padding for encryption as the padding for signature generation is performed over a message digest (secure hash value). Hash values are limited in size of course, so for practical key sizes the padding overhead doesn't matter.

Notes:

usually the RSA padding is simply used to wrap a newly created symmetric data/session key, which in turn is used to encrypt the data (i.e. the overhead doesn't matter much); this is called a hybrid cryptosystem.


Stream cipher from hash functions: possible

For any cryptographically strong pseudo-random function (PRF) the CTR mode of encryption can be defined. You can build such a PRF from a hash function.

One can achive to produce a key stream by :

$$H(k,0) || H(k,1) || ... || H(k,m)$$ where the $k$ is your symmetic key. Salsa20 and ChaCha20 are examples.

Public key from hash functions: your method? No

  A 48 byte string is generated randomly. This is the private key.
  That 48 byte string produces another piece of data through SHA384: the public key.
  The keys can be shared secretly by exchanging keys (example: Alice tells Bob her private key and it is encrypted with her public key.)

What do we do after this? Do you remember that we need a system to encrypt the data with the public key and decrypt with the private key like RSA.

  I want to know if this is possible because RSA is currently secure but can be broken by quantum computers in the future. Quantum computers can factor large primes but they can't break hash functions. Also, I picked SHA384 because it can't be broken with a quantum computer.

What about quantum-resistant public-key cryptography

NTRU (lattice-based cryptography)
McEliece (code-based cryptography)
Ring Learning with Errors (R-LWE) (lattice-based cryptography)
Multivarite Cryptography
Isogeny-based cryptography such as SIKE conjectured to be infeasible even Shor is ever implemented.

and AES256 which has $2^{128}$ bit security against Grover's algorithm if ever built and run efficiently for the queries.

Now you can use these to achieve Hybrid Cryptosystem.

Also note that to have a resistance for hash functions against the quantum attacks, you need to consider the Brassard et al. method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function. whereas the Grover's method has $\mathcal{O}(\sqrt{n})$-time.

This cost calculation of the quantum attacks hides some metrics like Brassard, the attack requires a huge Quantum circuit. Grover for AES-128, not clear how one will run the $2^{64}$ evluations.


Is there any bias whatsoever in modern hash function outputs?

If there were any detectable bias, I wouldn't be posting about it on a forum of pseudonymous wackos like me on the internet—I would be getting top billing (or beaking, as the case may be) in a top-tier cryptography conference, and the champagne would be popping, and Twitter would be abuzz with speculation, and Hacker News would be extra insufferable.

Specifically, with the exception of 2-pass Snefru[1][2], no major hash function with advertised preimage and collision resistance has ever seen its preimage resistance broken[3] (archive).  (Yes, there's a paper that everyone and their dog cites on an MD5 preimage attack[4], but it's not cheaper than the best generic attack[5].)

P.S.  The formula $\epsilon = 2^{-(s n - k)/2}$ appears to be a quotation from an ID Quantique marketing whitepaper with a garbled definition which Paul read out of context to draw a nonsense conclusion in the self-accepted answer of his own that he cited.


How does one associate the actual identity of a person or organization with a decentralized ID?

A certificate is a document containing a public key, identity information associated with that key, a signature, and information about what entity created the signature. A self-signed certificate is any certificate where the signature was created by the same entity that has the private key of the certificate. A DID is just a self-signed certificate.
By using their private key to sign a challenge the DID holder can verify to others that they possess that private key, and thus are the same entity as they were when the DID was created and added to the blockchain. Nothing about the blockchain ensures that the identity information is correct, of course, only that it hasn't changed. That step has to be done independently. In your example, the university could publish their DID on their web site.
You might note that this doesn't get rid of certificates, it just calls self-signed certificates DIDs.


Whitebox AES: why not steal the whole whitebox?

This is answered in the Whitebox AES paper. I've quoted the relevant section, which occurs on the second page:

A natural question is: if an attacker has access to executing decryption soft-ware itself, why worry about preventing secret-key extraction --- the attacker
could simply use the software and platform at hand to decrypt ciphertext or
access plaintext. The answer (see also section 2.2) is that our techniques are
targeted mainly at software-based cryptographic content protection for Internet
media, rather than at more traditional communications security. In such applications, the damage is relatively small if an attacker can make continued use
of an already-compromised platform, but cannot extract keying material allowing software protection goals to be bypassed on other machines, or publish keys
or software sub-components allowing `global cracks' to defeat security measures
across large user-bases of installed software. Our solutions can also be combined
with other software protection approaches, such as node-locking techniques tying
software use to specific hardware devices.

Their argument is essentially that key extraction can allow you to completely break DRM for all users in a way that "stealing the whitebox" would not. I believe famous DRM breaks (say against the PS3) involved key extraction, so their claim may have been justified by history.