Using checksum instead of hash for authenticating ciphers

If we were to use CTR, what would you think of using a checksum on
  plain text then encrypt whole.

That's a really bad idea (from a security perspective).
Here are the reasons for this:

Depending on your checksum, there are immediate obvious attacks on the authenticity of messages. If your checksum is CRC for example then it is linear. This means that an attacker can just compute some $\Delta$ he wants to insert into the message and also computes $\operatorname{CRC}(\Delta)$ and he can just XOR this into your message and it will be accepted as a valid message, because $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)=\operatorname{CRC}(P\oplus \Delta)$. This attack was already known to be
applicable to WEP.
A checksum is less "hardened" than a hash. A checksum doesn't even want to be a cryptographic hash and doesn't want to resist targeted attacks. They may thus expose linear behavior (see above) or other weaknesses which may allow for forgeries. Also see "Are checksums essentially non-secure versions of cryptographic hashes?" on this matter.
Hash-then-Encrypt is a bad idea as a composition. As you've already seen above Hash-then-Encrypt can be vulnerable if your "hash" is linear. However even if it is non-linear and the attacker can take a good guess at the message's contents, he can still compute $H(\text{oldMessage})\oplus H(\text{newMessage})$ and XOR that into your keystream (along with $\text{oldMessage}\oplus \text{newMessage}$) and he has easily achieved a message forgery. Also see "Why is plain-hash-then-encrypt not a secure MAC?" on this subject.
Authenticating and then encrypting is also highly discouraged. Even if your "hash" was an actual MAC, using it first on the message and then encrypting the result is less desirable. There are generic security proofs that assure that Encrypt-Then-MAC is secure and don't give the same guarantees for MAC-Then-Encrypt, so using the latter is discouraged. Also see Prof. Lindell's answer on the question "Should we MAC-then-encrypt or encrypt-then-MAC?".

OK, as asked for in the comments, let's dive a little into the attack I outlined in the first bullet point.
Let's call the ciphertext $C$, the (unknown) message $P$ and the (unknown) keystream $K$, which is internally used by the CTR mode. As you're using a stream cipher $C=M\oplus K$ (with $\oplus$ denoting bitwise XOR) is the encryption function. Note that for all choices of $A$ and $B$ you can come up with a $C$ such that $A=B\oplus C$. Now in the first step we manipulate the message $M$. So we first calculate the difference we want to see appear after decryption, let's call it $\delta$. Now we intercept $C$ and send $C'=C\oplus \delta$ onwards. Note how $C'\oplus K=M\oplus\delta$ will yield the manipulated message upon decryption. So now we split $M$ into the concatenation of the plaintext $P$ and its checksum $\operatorname{CRC}(P)$ as $P\parallel\operatorname{CRC}(P)$. Now also split $\delta=\Delta\parallel\operatorname{CRC}(\Delta)$. Now you see that you'll get $P\oplus\Delta$ upon decryption as the plaintext and $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)$ as the checksum. Now as CRC is linear $\operatorname{CRC}(P)\oplus\operatorname{CRC}(\Delta)=\operatorname{CRC}(P\oplus\Delta)$ which is the valid checksum for the forged message.


What you want does not exists with any secure encryption scheme and collision resistant hash function.

Any encryption scheme that is at least CPA secure¹ cannot be deterministic. Therefore not only can the equality you ask for not hold, it's even true that for $c_1 = \mathsf{Enc}(k,H(m))$ and $c_2 = \mathsf{Enc}(k,H(m))$, it holds with overwhelming probability that
$c_1\neq c_2$. similarly, $h_1\neq h_2$ with overwhelming probability for $h_1 = H(\mathsf{Enc}(k,m))$ and $h_2 = H(\mathsf{Enc}(k,m))$, since the encryption scheme is secure and the hash function is collision resistant.

Furthermore, due to a secure encryption scheme being probabilistic, ist must also be expanding. I.e., for $c = \mathsf{Enc}(k,m)$ it holds that $|c|>|m|$.

Since a hash function compresses inputs to a fixed length, it must therefore hold that $$|\mathsf{Enc}(k,H(m))| > |H(\mathsf{Enc}(k,m))|$$
and thus by extension necessarily that
$$\mathsf{Enc}(k,H(m))\neq H(\mathsf{Enc}(k,m))$$
even if you would try to somehow correlate the randomness used in the two encryptions.

¹This is the absolute bare minimum of what we consider a secure encryption scheme in most cases. As Maarten points out in the comments there are some narrowly defined use-cases in which weaker notions of security may be acceptable.


Encrypting Data with user + custodian private keys

I gave this some more thought over the weekend and came up with a simpler solution. We'll store the data encrypted with the user key. For in-transit encryption we'll use a service key. The user data will be decrypted on read with the user key and then re-encrypted with the service key before transmitting the data. The data consumer will be required to have access to the service key to read it. This will also meet the requirement that the data will be rendered unrecoverable by deleting the user key.


Strong RNG for encryption/authentation algo

RDRAND/RDSEED is the focus of all three of your questions here.  If you're looking for truly random numbers (as indicated by the trng tag),   it's probably worth realising that there is substantial anecdotal and circumstantial evidence that RDRAND/RDSEED isn't a TRNG.  Have a look at my analysis from another question, specifically item 10. That indicates that it's not just me spouting weirdo conspiracy theories.

Since my analysis discourages the cheap Intel approach, you're left with TPMs and HSMs. Clearly a HSM costs waay more than a TPM.  You could argue that a HSM might be more secure/reliable as they tend to be build to international standards like FIPS and commonly accepted in security scenarios.

The entropies should be identical at 8 bits/byte, but I also offer this warning.  How do you know? Computational indistinguishability means that you can't differentiate even a simple construct like $E_k(pepper||time)$ from a truly random sequence. And both hardware are designed tamper resistant, which means that you can't personally audit them. So similarly, look at this TPM criticism.

It's a tough choice as a lot of what applies to my RDRAND/RDSEED thesis also applies to TPMs and HSMs.

As for the remaining two parts:-

Yes, feeding a PRNG from a TRNG seed does lower the mathematical strength of the output. A caveat though is that as long as you create your 128/256 bits of initial Kolmogorov randomness, it should be sufficient for most cryptographic purposes. It just means that the output entropy is no longer truly random. Those 128/256 bits remain a constant no matter the output length. Till you re-seed. This is what occurs inside *nix's \dev\urandom, just using other entropy sources.
RDSEED's raison d'être is key creation and seeding.  If you believe that the output entropy is real, then all you have to do is acquire it.  You get it in batches of 16 - 64 bits via registers. It's a bit dry, but instructions are here.  No KDF is required as it should be truly random at 8 bits/byte and therefore perfectly secure. A KDF is indicated when going from a password to a key.


How to compare security between S-Box and Addition in the block ciphers?

So you have addition with carry bitwise if the sum is smaller than $2^n-1$
as well as the subtraction of $2^n$ if the sum is greater than $2^n-1.$

Helger Lipmaa has analysis that is relevant in
"Efficient Algorithms for Computing Differential Properties of Addition" available at

http://kodu.ut.ee/~lipmaa/papers/lm01/

You can use that work as a starting point.


Basically yes, you can do that. Public keys are meant to be shared. The devil is in the details however:

public keys without trust are pretty useless as you don't know who you are performing the key agreement with;
two static keys will always generate the same key for the same partners if you use a naive DH implementation, something you probably don't want;
you need different keys for the sender and receiver
you need message integrity and authentication once you start sending messages

Etc. etc. etc. Different methods of performing DH are described in NIST SP 800-56A Revision 2. That still doesn't describe the authentication framework though. You could do worse than learning TLS 1.2 and 1.3 for starters.


Several questions about Paillier cryptosystem

Let us briefly recall the Paillier encryption.
Let $k_{pub} = (N = PQ, g)$ be a public key, where $N$ is the RSA modulus.
The secret key is $\lambda = \mathrm{lcm}(P-1,Q-1)$ (or $P,Q$).
The encryption of $p \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_N^*$ is $C = g^p r^N \bmod{N^2}$.

You can verify $\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times \mathbb{Z}_N^*$.
As Paillier wrote, there is a subgroup $G = \{z \mid z = y^N \bmod{N^2}\}$ of order $\phi = (P-1)(Q-1)$.
There is a bijective mapping $\tau$ from $\mathbb{Z}_N^*$ to $G$ which maps $y$ to $z = y^N \bmod{N^2}$. The inversion $\tau^{-1}(z)$ is computed by $y = z^{N^{-1} \bmod{\lambda}} \bmod{N}$. Roughly speaking, this is the RSA decryption with $e = N$.

Answers:

Yes.
You can find such $r$. Since you know the plaintext $p$, you can compute $d = g^{-p}C = r^N \bmod{N^2}$. By applying $\tau^{-1}$, you can find $r$. (See Section 5.)
No. There is only one $r \in \mathbb{Z}_N^*$. (See Lemma 3.)\
Makes sense since there may be even a huge number of ciphertexts representing the same plaintext but they all have to decrypt to just one plaintext. Hence r is unique as long as en- and decryption are executed using the same pair of keys.
No.


How constant value 0x63 in affine transformation is chosen or generated while AES Substitution Box is formed?

According to the Rijndael AES proposal (emphasis mine):

  We  have chosen an affine mapping that has a very simple description per se, but a complicated algebraic expression if combined with the ‘inverse’  mapping. It can be seen as modular polynomial multiplication followed by an addition: $$b(x) = (x^7 + x^6 + x^2 + x) + a(x)(x^7 + x^6 + x^5 + x^4 + 1) \mod x^8 + 1$$ The modulus has been chosen as the simplest modulus possible. The multiplication polynomial has been chosen from the set of polynomials coprime to the modulus as the one with the simplest description. The constant has been chosen in such a way that that the S-box has no
  fixed points (S-box($a$) = $a$) and no ’opposite fixed points' (S-box($a$) = $\bar a$).

I'm not personally aware of any other design considerations in the choice of the additive constant 0x63, although it's worth noting that it does have a fairly nice and simple binary representation (0x63 = 0b0110 0011), which might perhaps simplify some implementations slightly.


Multiple AES Key Derivation from a master key

Multiple Key Generation from a Master key
HMAC-based Key Derivation Function (HKDF) rfc5869 is what you are looking for. HMAC security proof uses the fact that the compression function of the underlying hash is itself a PRF.

HKDF follows the "extract-then-expand" paradigm, where the KDF
logically consists of two modules.  The first stage takes the input
keying material and "extracts" from it a fixed-length pseudorandom
key K.  The second stage "expands" the key K into several additional
pseudorandom keys (the output of the KDF).

Extract:
$$\text{HKDF-Extract}(salt, IKM) \to PRK,$$where  $PRK$ is a pseudorandom key.
If the Input Key Material (IKM) is already a random key, as in your case, then the extract is not necessary, Expand is enough. HKDF can be used without the salt, however, using salt adds to the strengthening of HKDF and supporting source-independent extraction. Two different salts with the same $IKM$ result in fundamentally two different $PRK$s. And, in general, $x$ different salts with the same $IKM$ result in fundamentally $x$ different $PRK$s.
Expand:
$$\text{KDF-Expand}(PRK, info, L) \to OKM,$$where OKM is Output Keying Material. L is the desired key length.
The info can be used for the application-specific tag to derive different keys.
$$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 1"}, 128) \to OKM_1$$
$$\text{KDF-Expand}(\text{Inittal Key}, \text{"application 2"}, 256) \to OKM_2$$

What is the probability of generating the same key, i.e. collision
It is hard to talk about directly on the HKDF, however, if we model it as a  uniform random function $f$, where $f(x)$ is uniform random HKDF value for each combined input ( $x = salt || IKM $) then we can turn back to birthday collisions.
Let $P(C; n, k)$ denotes the usual collision probability among $n$ people with $k$ possible birthdays. And, the usual way is to calculate from the complement $P(D; n, k) = 1 - P(C; n, k)$, that is all birthdays are distinct. Then we can approximate by
\begin{equation}
  P(C; n, k) = 1 - P(D; n, k) \leq \frac{n^2}{k}.
\end{equation} where $n \leq k/2$. The detail is everyhwere, and therefore skipped.
We have two cases;

The collision on the generating the $x$s. You may consider this as salt collision too if IKM is set fixed. For $n$ inputs $x_1,x_2,\ldots,x_n$ the collision probability is $P(C; n, k)$. When this occurs, that is the conditional probability than the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ will have a collision with probaility 1.

If the inputs $x_i$s are distinct then this has $P(D; n, k) = 1 - P(C; n, k)$ probability. Now, conditionally on this we can have collision on the outputs $f(x_1),f(x_2), \ldots, f(x_n)$ with $P(C; n, k)$ probability.

Now sum up the above, then we have;
$$P(C; n, k) + (1 - P(C; n, k)) \cdot P(C; n, k) \\ = 2 P(C; n, k) - P(C; n, k)^2 \leq 2 \frac{n^2}{k}$$
So, this is just double of the usual collision attack. If you are not going to generate $2^{64}$ keys for a 128-bit key it then is not a problem for you. This case may be a problem with the multi-target attack. This is why you need to use AES-256.
You may notice that $2^{64}$ with 128 makes 2, this is due to the fact that the probability bound is not good for $n \approx \sqrt{k}$, there are tighter bound however when the input passes $\sqrt{k}$ it fastly approaches to 1.
It is important to note that 50% probability is too high in the sense of the adversary. One should stop way earlier than this. If you use AES-256, you should use it ( or ChaCha20 that has a 256-bit key), then the amount generating a collision is beyond us.

Note: There is also old KDF1 and KDF2
$$K_i = \operatorname{KDF}(K_{master}, i) = \operatorname{H}(K_{master} \mathbin\| c)$$ where $c$ is 4 byte encoded $i$, and it was commonly used wiht MD5,SHA-1, and SHA-256.

A sample code with python hkdf that contains the pop count on the output's x-or;
from hkdf import hkdf_extract,hkdf_expand
from binascii import unhexlify,b2a_hex
import sys

def bxor(b1, b2): # use xor for bytes
    parts = []
    for b1, b2 in zip(b1, b2):
        parts.append(bytes([b1 ^ b2]))
    return b''.join(parts)

prk = hkdf_extract(unhexlify(b"8e94ef805b93e683ff18"), b"asecretpassword")
key1 = hkdf_expand(prk, b"application 1", 16)
key2 = hkdf_expand(prk, b"application 2", 16)

print (b2a_hex(key1))
print (b2a_hex(key2))

#count the number of differnt bits by x-or and popup count.
print (bin(int.from_bytes(bxor(key1,key2), byteorder=sys.byteorder))[2:].count('1'))

outputs
 b'd6208cd3e14955c6ae0dc7f5ecd38a68'
 b'3b310a2e8cc9f4854237e966d289d9ba'
 64


What are some good examples of modifying crypto where flaws are not really obvious?

One of the best examples that I know of is "chained CBC" as used in SSL. This looks exactly like regular CBC. The only difference is that instead of sending a new IV with every message, the IV is taken to be the last ciphertext block of the previous message. This is much more efficient since for small packets you don't need to send a large IV each time. In addition, you don't need to generate new randomness for every message (and rely on the randomness on the machine). This looks just like CBC since a single long message exactly has the "chain" effect.

However, this minor modification (and major optimization) is not secure, and resulted finally in the BEAST attack on SSL.


Is the prime P is fixed for an elliptic curve defined over a particular prime field F_p?

In general you start by fixing the field, which translates into fixing the prime, and then you start to look to a suitable (i.e. secure/safe) elliptic curve defined over that field.

Note that, once you've fixed $p$, there are $\sim2p$ isomorphism class of elliptic curves defined over $\mathbb{F}_p$, which grants you a big set where you are supposed to find a curve with all the desired security properties, unless you are looking for very specific properties such as low CM discriminant.

There are two good reasons for it.

First: the field is linked to the curve's cardinality by Hasse's Theorem. which means that by choosing the size of the prime you also strictly bound the size of the cardinality (within a bit).

And second, and most important, a particular choice of the prime provides faster-than-generic modular reductions, which provides performance benefits of elliptic curve computations.

For example, all NIST P curves are defined over Solinas primes (also called generalized Mersenne), except P-521 which is over a Mersenne prime.
The idea is that using Solinas reduction is faster than a generic modular reduction and can be used to speed up the computation.

Similar arguments are used in more modern elliptic curves such as curve25519 which uses a pseudo Mersenne prime ($2^{255}-19$) or FourQ which uses is defined over a field $\mathbb{F_{p^2}}$ with $p=2^{127}-1$.

Note that the Brainpool standard uses random primes, however its deterministic algorithm for curve generation selects first a random prime, and then look for a suitable curve. See appendix A of RFC 5639.


Provided that you use the all 256 bits of SKEY as key then the bit security of this scheme is about $\sqrt2\cdot2^{125}$.

The reason behind the $2^{125}$ as opposed to the security of $2^{128}$ is because, for curve25519, $2^{128}$ is just an approximation. If we use, as it is more commonly done, the number of "operation" for this calculation, then the number of point additions required by Pollard's rho is about $\sqrt{2^{251}}\simeq2^{125}$.

The reason behind the $\sqrt2$ factor instead of $2$ is due to the fact that Pollard's rho allows to compute batch discrete logarithms faster than what would be a two separate application of the algorithm.
For details, see the section "Batch discrete logarithms" in the original curve25519 paper.


Security of KDF1 and KDF2 (hash based KDF's)

As far as I know (which, admittedly, might be limited; I do not claim to possess encyclopedic knowledge of attacks on KDFs), there are no known practical attacks against KDF1 or KDF2 (which are also mentioned on this page, following ISO-18033-2) when instantiated with a secure hash function.

Regarding the relative security of these KDFs vs. HMAC-based KDFs like HKDF, it's worth noting that the HMAC security proof is based on the assumption that the compression function of the underlying hash is itself a PRF.  Therefore, when used with any hash function to which the standard HMAC security proof applies, it seems that KDF1 / KDF2 should also be provably secure, at least as long as the master key length equals (or is padded to) the input block size of the hash.


Asymptotically, the fastest provable algorithm for SVP is based on discrete Gaussian sampling, achieving both time and space complexity $2^{n + o(n)}$ in dimension $n$. This algorithm finds a way to obtain samples from a discrete Gaussian on the lattice with a very narrow standard deviation, so that most of the probability mass is concentrated on short lattice vectors, and the probability mass on shortest vectors is sufficiently large that $2^{n + o(n)}$ samples from this distrubition suffice to find one shortest vector. The time to generate even a single sample from such a discrete Gaussian with small standard deviation is however already $2^{n + o(n)}$.

As for algorithms for "discrete Gaussian sampling", there are two different topics to consider here:

A discrete Gaussian with a large standard deviation is very "flat", has a lot of probability mass concentrated around vectors with huge norms, and therefore it turns out to be quite easy to sample from these distributions by first running LLL reduction and then running some polynomial-time sampling algorithm. These discrete Gaussians are commonly used in lattice-based cryptography, e.g. to sample a noise vector in Learning With Errors.
A discrete Gaussian with a small standard deviation is very narrow, has most of the mass concentrated around short lattice vectors, and therefore accurately sampling from these distributions (without some kind of trapdoor information about the lattice) is known to be hard.

What defines "small" and "large" above is related to what is commonly called the "smoothing parameter" (see e.g. here). Sampling "above smoothing" is usually considered "easy" while sampling "below smoothing" is "hard", if you have say an LLL-reduced basis of a lattice.

Note that in "practice", the DGS algorithm for SVP is much worse than enumeration-based approaches (see e.g. here), lattice sieving algorithms (see e.g. here), and BKZ-enumeration hybrids like random sampling reduction. Heuristics for instance suggest you can solve SVP in time and space less than $2^{0.3n + o(n)}$ with sieving, and in practice sieving has been used to solve SVP challenges in dimensions as high as 155.


Why a pseudorandom permutation is used in a simulation based proof but pseudorandom function is not?

I happened to be talking to one of the authors and asked about this. The short answer is: Eventually on page 34 they are considering a malicious adversary. The simulator has to extract the adversary's effective input but it only knows the messages sent by the adversary, which in this case are just the PRP outputs. The simulator knows the PRP key so it can invert the PRP to determine the adversary's effective input. A PRF wouldn't allow this, although a PRF is indeed enough for the semi-honest variant of the protocol starting on page 31.


Can I use signature(hash(message)) instead of signature(message)?

Yes, this should be secure.

I am not familiar with TweetNaCl, so I cannot speak on the concrete implementation. However, the general construction of signing a hash of a message instead of the message should be secure. It is in fact a standard way to sign messages.

In general it should work for any secure signature scheme and cryptographic hash function. The intuition goes like this: assuming the signature scheme is secure, the only way to pass a signature on a message off as a signature of some different message is to find a new message with the same hash as the original message. Thus finding such a message would break 2nd preimage resistance of the hash function.


Does Goldwasser-Micali only encrypts only 1-bit or multiple?

The original scheme by Golwasser and Micali only encrypts one bit at a time.
It is possible to extend it to encrypt multiple bits at the same time using an higher order residue.
Roughly one can encrypt up to $k$ bits using the $2^k$-th residue symbol.


How can my application make sure the right symmetric key is used for decryption?

First of all, you should definitely be using some sort of an authenticated encryption solution. If you can't use AES-GCM or some other mode designed specifically for authenticated encryption, you should probably pick AES-CTR and HMAC-SHA256.

Next, you should encrypt the actual data with a completely random key you have generated and store this key encrypted to the password (using a password based key derivation function, such as PBKDF2). If you want to be really proper, using a standard key-wrapping algorithm for this would be best, but using authenticated encryption works. Do not encrypt the key without authenticating it.

This gives you two benefits:

You can change the passphrase to a file without re-encrypting it fully
You can detect if the passphrase was typed wrong

And included the standard disclaimer: if this isn't for a hobby project - please don't. There's no need to reinvent the wheel - you can implement standard OpenPGP symmetric encryption, for example. And even if you do use a standard - cryptography is hard to implement correctly and it takes a long time to build confidence in an implementation.


sign data and append certificate VS sign data and certificate

Assuming you're using standard PKI certificate standards rather than rolling your own approach there's not really a security benefit to including the certificate chain in the JWT that's covered by the signature.

Each (non-root) certificate is signed by the issuing certificate. So it's already covered by a signature that traces back to your root certificate. Signing it again within the JWT doesn't provide any additional protections.

I also can't see any particular security risk with including the certificate chain within the signed portion of the JWT. A signature exists to prove the authenticity of a known message. So has to be secure when the signed text is known. Including a known certificate chain does not therefore introduce any particular risks.

So really you need to drive this decision from other application design considerations.

Including the certificate chain in the JWT has one advantage I can see which is that you can parse the message using a standard library rather than having to pre-process it.

However in most scenarios that would be out-weighed significantly by the downsides of including the certitificate chain in the JWT which are:

You're signing a lot more content than you need to so are wasting a bit of CPU
You can't seperate the token from the certificate chain. That's likely to reduce the flexibility in the application design.

EOver time you may want to be able to just deal with the license in parts of the application where you know the certificate chain has already been processed, or allow it to be resolved dynamically. By keeping the certificate chain out of the signed JWT you can more easily split the two concerns apart to be dealt with by different parts of the application.

This wil also help if you wanted to move to encrypting the token in future rather than just signing it. By keeping the certificate chain seperate you can work with it before decrypting and checking the token which will make it easier to setup the validation routine.


Bridging the gap between security proofs and "real-world" security

As suggested in the comments, this question does seem broad and an answer would probably fill hundreds of journals. Nonetheless, the introduction to Katz & Lindell's Introduction to Modern Cryptography provides a nice starting point from a (largely) accepted perspective. Starting from a similar perspective, I'd say a provable security proof of some statement -- e.g., scheme S satisfies property P -- asserts nothing about the real-word beyond what is derivable about the real-world from the statement. This is incredibly limiting when you dig deeper, because many provable security proofs assert nothing about the real-world. That said, at least we can agree that the proven statement holds, rather than nothing at all.


Clarification on Size of an Encryption Key

Yes, 64 bits is equivalent to 8 bytes, because there are 8 bits per byte.

"Could it be instead that 64 bits has to be interpreted based on an encoding scheme such as unicode that includes many more characters? "

No - the key does not need to be encoded as either ascii or UTF. Typically crypto algorithms operate either on an array of unsigned characters, or larger words when required (i.e. unsigned long long for 64 bit words).


Is it a variant of Strong RSA assumption?

The modulus $N$ is implicit in the group $\mathbb Z_N^\ast$ that $c$ and $g$ are chosen from. That is, in this context, $g^a$ is taken to mean "the residue class represented by $x^a\bmod N$ where $x$ denotes some representant of $g$'s residue class".

Therefore, when additionally requiring that $a\geq3$ and odd, this notion is equivalent to the strong RSA assumption as defined in Rivest's paper.


Formula for bits of entropy per bit, when combining bits with XOR

Assume that bits $A$ and $B$ each have .5 bits of entropy per bit.

Fair enough (and I'll assume that we're talking about Shannon entropy)

The two-bit result of the concatenation $A‖B$ has 1 bit of entropy total, and it retains the entropy density of .5 bits of entropy per bit.

Not so fast.  The concatenation has between 0.5 and 1 bits of entropy.
The issue is that the bits may be correlated; if the bits are always exactly the same (or exactly the opposite), the concatenation will never have any more entropy than just one of the bits.  If the bits are independent (that is, are uncorrelated), then the concatenation will have 1 bit total.  If they are partially correlated, then the entropy will be somewhere between 0.5 and 1.
This is not a pedantic point; when computing the joint entropy of several events, one always needs to be aware of the possible correlations between these events.

How many bits of entropy would the single-bit result of the exclusive-OR of $A$ and $B$, namely $A \oplus B$, have per bit?

This is a somewhat more complicated situation; if we compute the probabilities involved with a source generating a single bit with 0.5 bits of entropy, well, that's the solution to $p \log_2(p) + (1-p) \log_2(1-p) = -0.5$, and those solutions are $p = 0.110028...$ or $p = 0.889972...$.  When we translate that into the possible entropies of the xor, that has a low of 0 (if the bits are perfectly correlated) to a maximum of 0.760269... (which happens if neither bit are in their low probability state at the same time); if they are uncorrelated, the entropy is 0.713537...
These values were computed by taking the above $p$ values, deriving the corresponding probabilities of the xor, and plugging them into the Shannon entropy formula.

I'm guessing the formula is something like $\mathord{\mathrm{E}}(A⊕B)=1-(1 - \mathord{\mathrm{E}}(A))(1-\mathord{\mathrm{E}}(B))=.75$ bits of entropy per bit. Is this correct?

No, it's not correct (even if we assume independence), at least if $E$ is the entropy function and not the expectation.  I'm not sure if there is a simple formula that gives you that; if $p$ is a solution to $p \log_2(p) + (1-p) \log_2(1-p) = -E(A)$, and $r$ is a solution to $r \log_2(r) + (1-r) \log_2(1-r) = -E(B)$, then the Shannon entropy formula applied to $A \oplus B$ would involve the term $\log_2( p \cdot r + (1-p) \cdot (1-r))$, and there's no immediately obvious way to simplify this term, or combine it with other terms.

Also, do I correctly interpret that you can only approach 1 bit of entropy per bit by XOR-ing bits of less dense entropies but never actually attain it?

Oddly enough, with the right amount of correlation, you can actually get 1 bit of entropy.  Consider the case where both sources generate a 1 with probability $0.25$ (and so have $0.811278...$ bits of entropy).  If they never both generate a 1 bit at the same time, then the probability that exactly one of then generate a 1 bit is $0.5$, and so the xor does yield an entropy of 1.
Of course, if the input bits are uncorrelated, then you are correct (unless one of the input bits already has an entropy of 1).


The length extension attack and security on length shortening of a hashed message by one byte

Could is also be possible to generate $H(\text{message}[1..n-1])$ from $H(\text{message}[1..n])$ if I know the last byte?

No, the length extension attacks are not working exactly like that. Let see how MD5 operates;
MD5 divides a message into 512-bit blocks to operate1 in Merkle–Damgård fashion way. Every message is padded. The messages are padded with 1 and following many zeroes so that the padded message size is multiple of 512 with the message length appended at the end represented in 64 bits. In a minimum way with always 1 is added the number of zeroes can be zero.
More formally, add bit 1 than add as many as required bit 0 until message length in bits $\equiv 448 \pmod{512}$ then add the message length in 64 bits. This also limits the file size that can be hashed with MD5.
So the $message[1..n-1]$ is calculated with $message[1..n-1] \mathbin\| padding$. After the padded message one can execute the length extension attack. The extended message with padding is;
$$\text{message}[1..n-1] \mathbin\| \text{padding} \mathbin\| \text{extension}\mathbin\|\text{padding}$$
To execute a length extension attack, one replaces the initial value of the target hash function with the hash. After this calculate the extended hash as usual hashing. Formally

let $\text{MD5}'(m,\text{MD5IV}) = \text{MD5}(m)$. I.e. $\text{MD5}'$ enables to control of the IV of the MD5.
let $h = MD5(m)$ of a message $m$.
then $h' = MD5'(m', h) = MD5(m\mathbin\|pad_1\mathbin\|m'\mathbin\|pad_2)$ where the $pad_1$ is the padding of $m$ when hashed with MD5 and $pad_2$ is the padding of $m\mathbin\|pad_1\mathbin\|m'$

The $h'$ is the length extended hash.

Might it become possible, when I just want to shorten the message by just one byte in any of MD5, SHA1 or SHA2? Or could I at least reduce the computational cost of a brute force attack?

After SHA3, there are variants of SHA2 like SHA512-256 that calculates a hash of output size 512 bits then truncates to 256. That almost eradicate the length extension attack's possibility. The SHA512-256 has a different initial value from SHA512-512 that separates the domains. In other words, they are different random oracles.
Of course, the pre-image resistance and secondary pre-image resistance and the collision resistance are weakened by $2^8$, $2^8$, and $\sqrt{2^8}$, respectively.

1The dividing is not specific to MD5 and diving size may change with each hash function like SHA512 uses 1024 bit block sizes


Yes, theoretically anyone can compute $\varphi(n)$ from $n$ and thus recover $d$ from $e$. This should be read as "given any $n$, it takes a finite amount of time to compute $\varphi(n)$".

More practically, "computing $\varphi(n)$ given $n$" and "factoring $n$" are equivalently hard. That is, if you can efficiently compute $\varphi(n)$ you can also efficiently factor $n$ and vice versa.

Now, if $n$ is sufficiently small, we can easily factor it and thus compute $\varphi(n)$ (which is what websites do), but as $n$ reaches cryptographically relevant values, it becomes infeasible (using current technology) to factor $n$ and thus to recover $\varphi(n)$.


Verifiable delay functions vs Proof of Sequential Work

A typical thing which you cannot do with a proof of sequential work is achieving time-lock encryption. In time lock encryption, you want the user to be able to retrieve the hidden message only after some time (i.e., you want to "send a message to the future", as its inventors initially put it). With a VDF, you can use the unique secret to mask the secret message $m$ which you want to send to the future; with a proof of sequential work, there is no clear way of masking a message such that retrieving it requires solving the puzzle (except in an interactive way, where another party checks the proof of sequential work and send $m$ if the check passes).

See also the discussion page 23 of this paper: proofs of sequential work fail to replace timed commitments in protocols that seek to achieve fairness. I believe that VDFs, on the other hand, can be used here, since they do not suffer from the limitation that prevents proofs of sequential work to be usable here - namely, that one can lie to the verifier about what was the solution to the puzzle we solved, even though one must still invest a given amount of sequential work to solve the puzzle in the first place. With VDFs, you cannot lie this way.


Is it possible to combine two operations rotation and xor?

The question asks for simple variations of the $*$ operations defined by formulas similar to $A*B=(A\lll3)\oplus(B\lll4)$ or $A*B=(A\lll3)\oplus(B\ggg4)$, where uppercase letters are words of $n=32$ bits, lowercase letters are integers, $\lll$ designates left rotation, $\ggg$ designates right rotation, $\oplus$ designates eXclusive-OR.

There are a number of properties we can use:
$$\begin{align*}
\forall X, \forall Y,           &&X\oplus Y          &=Y\oplus X\\
\forall X, \forall Y, \forall Z,&&(X\oplus Y)\oplus Z&=X\oplus(Y\oplus Z)\\
\forall X, \forall Y, \forall u,&&(X\oplus Y)\lll u  &= (X\lll u)\oplus(Y\lll u)\\
\forall X, \forall u, \forall v,&&(X\lll u)\lll v    &= X\lll((u+v)\bmod n)\\
\forall X, \forall u,           &&X\ggg u            &= X\lll((-u)\bmod n)
\end{align*}$$
where $a\bmod n$ is defined to be the $r$ such that $0\le r<n$ and $n$ divides $a-r$.

It follows that
$$\begin{align*}
(A\lll3)\oplus(B\lll4)&=(A\oplus (B\lll1))\lll3\\
                      &=((B\lll1)\oplus A)\lll3\\
                      &=((A\ggg1)\oplus B)\lll4
\end{align*}$$
which can be considered a simplification (in particular, absent a smart compiler, some of these alternate forms will likely be faster on 8-bit CPUs, and 32-bit CPUs lacking a barrel shifter)

Similarly we can write
$$\begin{align*}
(A\lll3)\oplus(B\ggg4)&=((B\ggg7)\oplus A)\lll3\\
                      &=(A\oplus (B\ggg7))\lll3\\
                      &=((A\lll7)\oplus B)\ggg4\\
                      &=(((A\lll8)\ggg1)\oplus B)\ggg4
\end{align*}$$
with the last form geared for 8-bit CPUs, where rotation by multiples of 8 is relatively efficient.

There's no way to simplify $((A\ggg3)\boxplus(B\lll4))\lll4$, or $((A\oplus B)\boxplus(C\oplus D))\oplus E$, where $\boxplus$ is addition modulo $2^n$. Problem is, we have no simple exact properties of $\boxplus$ with respect to $\lll$, $\ggg$, and $\oplus$.


Could we break MD5 entirely in the future?

If you follow the reference for the alleged preimage attack on MD5, you will see that although the time cost is $2^{123.4}$ steps, the memory cost is $2^{45} \times 11$ words of memory, which has a far higher area*time cost than a smart attacker would use—a smart attacker would fit 32 CPU cores or MD5 circuits in parallel into much less die area and get an answer faster, in $2^{123}$ time.  So that attack gives no reason to treat MD5's preimage resistance as below its advertised level.

But the advertised level—the best preimage resistance that can be provided by a 128-bit hash—is not very high.  A smart attacker will do even better: a smart attacker will attack many targets at once with a parallel brute force machine using rainbow tables, and find one preimage among $n$ target hashes on a machine parallelized $n^2$ ways with probability $p$ at the area*time cost of about $2^{128}p/n$ evaluations of MD5—much cheaper than the cost of about $2^{128}p$ for an attack on a single target, and in the time for $2^{128}p/n^3$ sequential evaluations of the MD5.  This is not an attack on MD5 in particular; this is a generic attack on any 128-bit hash.  Could this happen in practice?  It's within the realm of human feasibility, even for a preimage that is not an easily guessable passphrase.

With an array of $k$ quantum computers large enough to run Grover's algorithm, you could find a single MD5 preimage with probability $p$ in about $2^{64}\sqrt{p/k}$ time.  Whether this will ever be cheaper than the standard generic classical parallel brute force attack depends on how cheaply quantum computers capable of running Grover can be built and powered—at the moment, they do not exist at all.  (Studying the quantum multi-target story is left as an exercise for the reader.)

That doesn't necessarily mean you would find the original input strings—unless you know something about the distribution of the original input strings and restrict your search to that, you might find gibberish that happens to have the same hash as the original input strings.  (In fact, merely knowing an MD5 hash—a 128-bit string—doesn't mean there ever was an ‘original input string’.  Here's an example: 914c24484128dfe05c3060632ee16e3f.  Maybe you can find a preimage for that, but I just pulled it out of /dev/urandom.)  So it would mostly be useful mainly for either (a) filling in very short unknown high-entropy details of large documents the rest of which you know, or (b) inventing substitute strings that will have the same hash and that are useful only in active attacks on systems still using MD5 as a proxy for identity.

As for computing collisions—finding pairs of messages $m_0 \ne m_1$ with $\operatorname{MD5}(m_0) = \operatorname{MD5}(m_1)$, with no control over what the common hash value might come out to be—you don't need a quantum computer to do that.  It's practically a parlor trick at this point, costing under a million MD5 computations to make fresh ones, to say nothing of extending existing collisions into longer ones which costs no computation at all.


TLS Extension signature_algorithms values

Some of these values are sort-of defined in drafts that should become RFC at some point. For instance, the latest (as of today) draft of TLS 1.3 lists in section 4.2.3 the values 0x0804, 0x0805 and 0x0806 (these designate RSA signatures with the new-style "PSS" padding, used with SHA-256, SHA-384 and SHA-512, respectively).

The "000d 0014 0012" values are actually the header of the extension:

000d is the identifier for the "signature algorithm" extension.
0014 is the extension contents length (in bytes).
0012 is the length of the list of values in the extension (because the extension is defined as a list of values, and lists in TLS message encodings take an explicit header that gives the list length in bytes).

Note that while the 16-bit values were initially designed as two successive bytes (first for the hash algorithm, second for the signature algorithm), they now tend to be defined as full 16-bit values that cover the whole signature algorithm with no specific sub-structure.


How is the MAC or HMAC secret shared with the other party for verification?

It is "sent over a secure channel like the AES key".

It is "safe to use the same HMAC secret for each subsequent
AES encrypted message after the initial connection".


Perfect Secrecy with 1 Time Complex Secret Cypher

Is it possible to achieve perfect secrecy, unbreakable, unguessable, uncrackable by using a totally secret cypher?

There are two different questions: Can you obtain perfect secrecy, and can you obtain an encryption algorithm that cannot be broken.

Perfect Secrecy

The One Time Pad is already a well known construction; Supposing that any construction that provides perfect secrecy is effectively equivalent to a One Time Pad, then using a secret cipher to obtain perfect secrecy will not be possible.

Supposing you did develop some other algorithm that provided perfect secrecy, keeping the algorithm would not be necessary or improve anything: Proof of this can be demonstrated with the One Time Pad, in that it is information-theoretically secure, despite the adversary knowing that a OTP was used to encrypt the message.

Unbreakable, Unguessable, Uncrackable, etc

In theory, probably not.

In practice, yes. However, once again, this is something that can/is achieved without resorting to keeping the algorithm secret; It is usually accomplished by creating designs that understand how an adversary will attack.

Then some people might say that this would violate Kerckhoffs's principle, but I disagree.

This is the very definition of a violation of Kerckhoffs's principle: The cryptosystem should be secure even if the enemy knows everything about it except for the key. It appears that you are not disagreeing about whether or not this scheme violates the principle, but whether or not the principle is worth upholding.

The algorithm as a key

Keeping the algorithm secret means that the algorithm becomes the key material. We can (and do) quantify the size of keys in terms of bits; There is a minimum representation of your algorithm that requires a minimum number of bits to represent.

The real problem with this is that symmetric keys should be shared between two parties; A secret algorithm is a symmetric key which must be shared between all parties. This dramatically increases the chances of exposure of the "key" the an adversary.

Because you have to execute it physically somewhere, somehow, you will have to ensure that copies of your program never end up on disk, never hang around in memory, that nobody ever sees the source code, and that nobody can watch what the CPU is doing. It is hard to make these guarantees even when many eyes are scrutinizing the source for mistakes.

Creating a cryptosystem on the assumption that an adversary does not know a single bit of plaintext implies that you only ever encrypt fully random blocks of data. If you are encrypting anything other then random data, this assumption will not be met and any further analysis is a waste.

Keeping the algorithm (and all plaintext messages) a secret in an attempt to thwart cryptanalysis is effectively equivalent to "hoping" that the adversary does not discover any flaws in the algorithm. "Hope" is not what cryptography provides; Cryptography provides certainty, preferably using as few assumptions against as strong of an adversary as possible. Instead of hoping, it is a proven superior practice to understand and design algorithms that can offer provable security.


How does concatenating diverse hash functions affect collision resistance?

Hash3( Hash2( Hash1( text )))

The collision resistance of $H'(x):=H_3(H_2(H_1(x)))$ is most likely $\operatorname{CR}(H')=\min(\operatorname{CR}(H_3),\operatorname{CR}(H_2),\operatorname{CR}(H_1))$, that is the combined scheme is at most as collision resistant as any individual scheme. Of course it has to be admitted that for most choices of the three hash functions, you don't have enough control over the input of $H_2,H_3$ to exploit structural collisions.

So the two main strategies to find collisions in this construction are:

Find a structural collision for Hash1, i.e. something like what was found for SHA-1 or MD5, or
Find a generic collision against any of the three hash functions, i.e. run through $2^{n/2}$ messages for $n$ being the minimum of the hash function output lengths in bits. Note that if an intermediary has a small output, e.g. 128-bit then finding a collision there will propagate the collision to the end.

  Does the birthday attack mean in this case that I must double the input data set size of every hash function starting from the end?

No, see above.

  If so, does it mean that if the output hash function had to have a 128 bits digest, the middle one must have a 256 bits long digest, and the first one 512 bits in order to gain a collision resistance that takes 2^64 trials?

No, see above. Also note that we usually model hash functions as outputting random values and no matter what you do with that output, you can't deterministically make more messages than could have been generated. That is, if you have $2^{128}$ possible hash outputs, you can't magically, deterministically make $2^{256}$ possible inputs to the next hash function out of that.


The cited paper, as well as the theorem of R-LWE in that paper only requires $f$ to be irreducible over the rationals. For this requirement one usually uses $f = x^n+1$ with $n$ a power of $2$. This polynomial is reducible modulo $q$ but it is okay for the proof to go through.

The cited paper suggested to use cyclotomic polynomial $\phi_n = 1+x+x^2+...+x^{n-1}$ with $n$ prime. This polynomial is irreducible over $Z$. For some prime $q$, it is also irreducible over $Z_q$.

Ex:
$n = 11$, $q=17$,
$\phi_n = x^{10} + x^9 + x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x + 1$ is irreducible mod $q$.


What is the significance of $\prod \limits_{i=1}^{t}m_i > p \prod \limits_{i=1}^{t-1}m_{n-i+1}$ in Asmuth–Bloom threshold SSS?

One of the required properties with a secret sharing scheme is that if you have $t-1$ shares (where $t$ is the threshold), then you can't eliminate any possible values from being the shared secret.

Now, suppose that we had $t-1$ shares; with the Asmuth-Bloom scheme, we would learn the most if they happened to be shares $(y_{n-t+2})$ through $y_{n}$.  If you had those shares, then you could deduce the value $y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1}$

You also know that:

$0 \le y < M$
You really want the value $y \bmod p$

For you to learn nothing, we need to have all possible values of $y \bmod \prod \limits_{i=1}^{t-1}m_{n-i+1} + pk$ to be in the range $[0, .., M-1]$

This is guaranteed if $p \cdot \prod \limits_{i=1}^{t-1}m_{n-i+1} \ge M$, which (if we remember that $M = \prod \limits_{i=1}^t m_i$ is precisely the restriction they give.

BTW: what is this fascination with Asmuth-Bloom?  In my opinion, Shamir Secret Sharing is a better way of solving the problem; it's simpler, a lot easier to set up, has smaller shares, and it doesn't leak any probabilistic information like Asmuth-Bloom does.


Is there a field guide to ECC for the IT Security layman?

By non-standard do you mean when to use custom curves? Like in crypto++ where you can specify your own parameters?

Given that the standards recommend certain sets of domain parameters (and interesting enough US government departments are forbidden from using their own parameters) it's sounds like the answer is no, for reasons of avoiding the risks of self implementation and the worthlessness of "security by obscurity". Tiresome, but this is how i answer all the "should I do my own" question, sorry.

I do know that NIST curves have certain computational advantages over any old curves because there are some just more convenient numbers for the Projective coordinates calculations. Also this wikipedia page seems to think the number of prime curves and binary curves affects security and implimentation efficiency (I have no idea why though, but there is a link in the "NIST-recommended elliptic curves" section )


Is my proof of Asmuth-Bloom scheme's perfection correct?

Okay, so i was finally able to figure out a solution for this.
The scheme does indeed yield 138 valid results to guess the secret from. However, since they already know the secret lies in $\mathbb{Z}_{m_0}$ there are only (in the example above) 42 possible secrets anyways. Since $a$ is uniformly distributed, the scheme does indeed leak some probabilistic information about the secret when you apply $\bmod 43$ to all 138 possible values, as seen in:

So for example, an attacker could determine that 2,3 or 4 are more likely than for example 0 or 1.
However, there is no information leaked about the secret itself.


It is known that (m,n)-threshold schemes are equivalent to n-1 m-dimensional mutually orthogonal latin m-hypercubes. For m=2, there is a basic construction (Latin Squares) for prime n. For m > 2 you would need higher dimensional tables, there should still exist a simple way to generate them for prime n.


mbed tls DTLS v1.2 system with -ECDHE-ECDSA, mutual auth and pre-installed public/private keys, no unnecessary messages or ASN.1/X.509 decoding

You can write your own protocol instead of using DTLS. But there's no realistic chance that you'll get it right. Designing a secure protocol is hard, and you should definitely use a proven and tested one rather than roll your own.

You can do DTLS with raw public keys, which would avoid X.509 altogether. This saves a number of things: code size, RAM usage (but not a lot, compared to a self-signed certificate), and handshake message size. You still need two round trips to establish a session using raw public keys. This does have security and deployment drawbacks: you have to distribute all the peers' public keys before you can start communicating, and you have to manage repudiation on your own.

If you find an implementation of it, that is. Mbed TLS doesn't support it, although there's an old pull request for it. Reportedly tinydtls can do it.

Do use session caching and resumption whenever possible. Session resumption removes the cost of public-key cryptography and reduces the number of round trips to start the connection from 2 to 1.

TLS 1.3 will let you establish a session with a single round trip, but DTLS 1.3 isn't ready yet.

In the absence of a usable implementation of DTLS with raw public keys, you may be forced to partially roll your own: use DTLS with pre-shared symmetric keys (this is widely supported by (D)TLS implementations), and use a separate protocol to distribute the symmetric keys. But it would be safer to achieve this by using DTLS to effectively distribute the symmetric keys, and session resumption to avoid doing asymmetric cryptography every time.


What is the advantage of XTS over CBC mode (with diffuser)?

XTS vs. Undiffused CBC. The issue here is malleability. Both XTS and CBC prevent an attacker from learning information about encrypted data. However, neither one completely succeeds in preventing an attacker from tampering with encrypted data.

However, it's arguably easier to tamper with an (undiffused) CBC ciphertext than it is to tamper with an XTS ciphertext. Let's say that an attacker happens to know some message says

  "blah blah Give Alice \$400 ... blah blah blah".

If this message is encrypted using CBC, the attacker can tamper with the ciphertext in such a way that it will now decrypt to

  "blah blah !^%@^^ Give Alice \$800 blah blah blah"

The \$400 has become \$800. This is what your quote about "AES-XTS prevents an attacker from changing one specific bit in a data unit" refers to. Here I write !^%@^^ to indicate that the previous 16-byte block will become gibberish once decrypted, and this gibberish will be beyond the attacker's control.

On the other hand, using XTS prevents this attack. The attacker can corrupt a message by turning any 16-byte block into random gibberish, but he will not be able to have the same degree of control as he did in the CBC example.

But Microsoft decided not to use XTS anyway. The reason is that the ability to corrupt a 16-byte block could still be damaging. Here's the quote from the paper dchest linked:

  For example, there could be
  a configuration file (or registry entry) with a value that, when set to 0, creates a security
  hole in the OS. On-disk the setting looks something like "enableSomeSecuritySetting =
  1". If the start of the value falls on a 16-byte boundary and the attacker randomizes the
  plaintext value, there is a $2^{16}$ chance that the first two bytes of the plaintext will be 0x30
  0x00 which is a string that encodes the ASCII value ’0’.

(This quote is referring to the LRW tweakable cipher, but the XEX tweakable cipher used in XTS has the same problem).

Adding a diffuser. Using a diffuser is Microsft's solution to this problem. The idea here is to "mix" the plaintext up before encrypting it so that an attacker can't change \$400 to \$800 --- meddling with part of the ciphertext will change almost the entire plaintext, not just small parts of it.

This sounds good, but there's a catch: No one actually knows if Microsoft's diffuser actually is secure. To my knowledge, it hasn't received any published formal analysis from cryptographers. This means you should be skeptical about relying on it. Microsoft acknowledges this:

  On the disadvantage side, the diffuser is a new unproven algorithm, and this inevitably
  leads to questions. Without extensive public scrutiny and analysis of an algorithm, there
  is a justified skepticism about its security. People are reluctant to trust new algorithms.
  So why did we choose this option anyway? In our final analysis, we decided this was the
  better choice for our product. The performance gain over the alternatives was important
  enough to outweigh the disadvantages of a new diffuser algorithm. Time will tell whether
  we made the right choice.

The bottom line.
XTS is less malleable than undiffused CBC. However, CBC+Diffuser is probably less malleable than XTS, at least for practical purposes.

An important aside.
Neither CBC nor XTS were designed to be non-malleable. Ensuring that ciphertexts are not tampered with is a separate problem, one that should be solved by using Message Authentication Codes (MACs), such as HMAC-SHA256. The reasons MACs aren't typically used for full-disk encryption algorithms are (1) performance issues and (2) using a MAC requires storing extra information with the ciphertext, which makes adding it transparently a bit tricky.

A middle ground between MACs and diffusers would be to use a wide-block encryption mode, such as CMC, EME, or HEH. You can think of these as having a "built-in" diffuser, that makes them non-malleable. Unlike Microsoft's diffuser, these algorithms have formal security definitions and peer-reviewed mathematical proofs. They are secure under the assumption that AES is secure. Microsoft opted not to use these because of (1) performance issues and (2) patents.


I'm not sure how to answer the question about "trust" in the assumption. I suppose that is a matter of personal belief more than science. We don't know the truthfulness about any cryptographic assumptions, although obviously some have received more scrutiny than others. I'd say that the KEA assumptions have received relatively little attention, and so should be avoided if possible. However, I suspect that if you're asking the question, then it's not possible to avoid it.

As to the reducibility question, it's not reducible to anything that one might call a "standard" assumption. This is in fact by design. Standard assumptions, such as the RSA assumption or the DDH assumption, are "falsifiable" in the sense that if the assumption is false, then it is (in principle) easy to show a counterexample. In the case of RSA or DDH, the counterexample would be an algorithm A that successfully breaks the hard problems. Even if you have no idea how A works, it'd be pretty easy to verify that A is in fact a valid attacker just by sampling RSA composites/DDH tuples at random and seeing how often A succeeds.

By contrast, the knowledge of exponent assumption is one of the few non-falsifiable assumptions that cryptographers use. (The most common non-falsifiable "assumption" would be the concept of a random oracle, although that's not really an assumption per se.) It's possible that KEA1 is false, but it's not possible for me to prove to you that it's false just by showing you some simple witness to this claim.


Construct another ciphertext that decrypts to same message without knowing key in Elgamal

The key is here the probabilistic Encryption

  Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts

The first probabilistic encryption was proposed by Shafi Goldwasser and Silvio Micali Probabilistic encryption & how to play mental poker keeping secret all partial information in 1982. You randomize the encryption with a random for each message so that even the same messages get different encryptions.

This is why we call encryption can be probabilistic, but the decryption is deterministic. A plaintext can have  different encryptions but all must decrypt to the original plaintext

To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

  I think that ElGamal is not determinstic in the way each message can have several legal encryptions:

Yes, ElGamal is not deterministic. During the encryption, we select a random value for the encryption that makes each encryption different for the same ciphertexts. During the calculation of the shared secret, we select a random $k \in\{1\ldots q-1\}$ and continue with the following parameters; $(G,q,\alpha,b)$ as the public key;

$G$ is the cyclic group
$q$ is the size of $G$
$\alpha$ is the generator of $G$
$b=\alpha^a$ where $a$ is the private key.

Then the encryption performed as following;

select a random $k \in\{1\ldots q-1\}$
compute $s = b^k$ - the shared secret
compute $c_1 = \alpha^k$
compute $c_2 = m\cdot s$

If we encrypt $m$ with the random $k$ than the ciphertext pair is; $$(c_1,c_2)= (\alpha^k, m\cdot s)$$ Encrypting wiht a another random $k' \neq k$ will result in a different ciphertext; $$(c'_1,c'_2)= (\alpha^{k'}, m\cdot s'=b^{k'})$$

  Rerandomization: How to create new encryption of this cyphertext without knowing the plaintext and private key.

To rerandomize a ciphertext, take a new random $k' \in\{1\ldots q-1\}$ and calculate $b^{k'}$ and $\alpha^{k'}$ now mutiply the pair.

$$(c_1 \cdot \alpha^{k'},c_2 \cdot b^{k'}) = (\alpha^k \cdot \alpha^{k'}, m \cdot b^{k} \cdot b^{k'}) = (\alpha^{k+k'}, m \cdot b^{k+k'}) = (c_1'', m \cdot s'')$$

Therefore the new encryption is based on the combined shared secret which is $b^{k+k'}$. Of course, there is a problem that $k+k'$ can exceed the $q-1$, however that is no problem since the little Fermat theorem.

The two ciphertexts are different since $\alpha^{k+k'} \neq \alpha^{k}$.

Decryption:

$s'' = (c_1'')^a$, $c_1'' = \alpha^{k''}$ then $(c_1'')^a = \alpha^{xk''} = \alpha^{k''}$
Compute $s''^{-1}$ by ext-GCD.
Compute  $m=c_{2}\cdot s''^{-1} = m \cdot s'' \cdot s''^{-1} =m$

Therefore the rerandomization works.


Obtaining the key length of a columnar transposition, given a known plaintext word

Both the Vigenère and autokey ciphers are classified as polyalphabetic substitution ciphers, so the cipher in your exam is not likely to be either of those.  Rather, the phrasing of the question suggests that it belongs to the other branch of classical ciphers, transposition ciphers.

Indeed, looking at the letter frequencies of the ciphertext strongly suggests that, being similar to the frequency distribution of plain English text:

A (8) ########
T (8) ########
S (6) ######
E (5) #####
R (5) #####
H (3) ###
I (3) ###
N (3) ###
D (2) ##
K (2) ##
B (1) #
G (1) #
M (1) #
Q (1) #
U (1) #
W (1) #

The question also implies that this cipher has a key, so we're looking at a keyed transposition cipher.  The simplest one of those is probably a columnar transposition.  These come in two varieties: regular and irregular.  If this were the regular kind, the length of the ciphertext (51 letters) would be a multiple of the key length; but since the only factors of 51 are 3 and 17, neither of which seems likely for a key length, we can guess that we're dealing with the irregular type.

Now, the obvious way to try to guess the key length (even without knowing anything about the plaintext) would be to note that the ciphertext contains exactly one Q and one U.  Those letters very often follow one another in English, as in the word "earthQUake", so we can assume that they're probably adjacent in the plaintext.  So we should try to divide the ciphertext into n groups (where n is, say, between 4 and 10) of approximately equal length (since this is an irregular columnar transposition, some of the groups will be one letter longer than the others) such that the Q and the U end up at the same position within their groups.  Also, since we know the surrounding letters of the QU pair, we should check that those (particularly the Ks, of which there are only two) also end up in suitable positions.

If we try that for various values of n, we might find that dividing the ciphertext into six groups of eight and nine letters each looks promising:

aaatrksam sitahbne trsweursr hetiaadn ettrhtea kgtsnqids

Notice how the Q, U and K all line up in the fifth position of their groups.  We can now try to write these groups one per line and try rearrange them to form "earthquake" vertically:

6 kgtsnqids
3 trsweursr
4 hetiaadn
1 aaatrksam
5 ettrhtea
2 sitahbne

This is looking very promising: we almost have the word "earthquake", and the surrounding letters start to form meaningful-looking words.  However, there are a few problems left: the fifth group doesn't quite line up with the rest, and the longest groups are not all at the top as they should be.  Let's try to fix the first issue by shifting group 5 right by one letter:

6 gtsnqids
3 trsweursr
4 hetiaadne
1 aaatrksam
5 ttrhteak
2 sitahbne

Now group 6 looks misplaced, but the fix is obvious — it clearly belongs at the bottom, not at the top:

3 trsweursr
4 hetiaadne
1 aaatrksam
5 ttrhteak
2 sitahbne
6 gtsnqids

And now we can read the plaintext from top down:

thats great it starts with an earthquake birds and snakes rem

(Ps. If you don't recognize the reference, listen to this.)

I do have to admit, however, that if there's some simple shortcut to reliably determine the key length without (mostly) solving the cipher, I'm not aware of it.

Edit: I did think of one shortcut: if the keylength were less than 6, the sixth letter of "earthquake", Q, would have to line up with one of the earlier letters of the same word, and thus follow it in the ciphertext.  Since the only Q in the ciphertext follows an N, which is not found in "earthquake", the keylength must be at least 6.  We can also see that keylength 6 does look plausible (the pairs EU, AA, RK and TE are all found int the ciphertext), while 7, 8 and 9 are impossible (neither RE, EK nor EE are found in the ciphertext).  Alas, this method doesn't let us conclusively rule out keylengths of 10 or more, even if they do seem a priori unlikely.


First I must state that a secure RSA encryption must use an appropriate padding, which includes some randomness. See PKCS#1 for details.

That being said, $d$ is the "private exponent" and knowledge of $d$ and $n$ is sufficient to decrypt messages. $n$ is public (by construction) so $d$ must be kept private at all costs. If it is very small then an attacker can simply try values for $d$ exhaustively.
On a more general basis, if the size of $d$ is lower than 0.29 times the size of $n$ (in bits) then there exists an efficient key recovery attack. The accepted wisdom is that trying to get a $d$ much smaller than $n$ is a bad idea for security.

On the other hand, there is no problem in having a small $e$, down to $e = 3$. Actually, with RSA as you describe, there is a problem with a very small $e$: if you use $e = 3$ and encrypt the very same message $m$ with three distinct public keys, then an attacker can recover $m$. But that's not really due to using a small $e$; rather, it is due to not applying a proper padding.


questions about modular reduction algorithm over $F_{2^m}$

So let's take sect113r1. $f(x)$ is $x^{113}+x^9+1$. It seems like $z^m$ would be $x^{113}$ and $r(z)$ would be $x^9+1$. Is that a correct assumption?

Correct, we have $m = 113$, hence $z^m = z^{113}$ and $r(z) = z^9 + 1$.

  The algorithm uses $c$ and $C$ and I'm wondering if they're the same thing.

They are very closely related, $c(z)$ is a univariate polynomial in $z$ (with coefficients in $GF(2)$), and $C$ is the representation of that polynomial using words of size $W$ (in bits). So if we have $c(z) = z^7 + z^3 + z + 1$ and $W = 8$, we would have $C = (C[0]) = (10001011)$. $C$ gives us an unambiguous way of representing $c(z)$.

  So for the "Add $u_k(z)$ to $C\{j\}$" step... I assume that means to add by doing XOR? What if $u_k(z)$ and $C\{j\}$ are of different sizes? Do we pad both of them with 0's on the right or left side?

I believe the addition algorithm is specified earlier in that section but yes, if you are representing univariate polynomials as described above then you can XOR the values to get the result of addition (since XOR is addition in $GF(2)$). If you follow the convention that the coefficient of the highest degree term in the polynomial is the MSB in the last word ($C[n]$), then you don't need to zero pad. If you have less words in one polynomial than the other, you can skip addition (since XOR by all 0 is the identity function) and just take those words as is. As an example, with $W = 4$

$$a(z) = z^7 + z^3 + z  + 1$$
$$b(z) = z^3 + z^2$$
$$c(z) = a(z) + b(z) = z^7 + 2z^3 + z^2 + z + 1 = z^7 + z^2 + z + 1$$
$$A = (1000, 1011)$$
$$B = (1100)$$
$$C = (1000 (\oplus 0000), 1011 \oplus 1100) = (1000, 0111)$$

  So let's say $W$ equals 8...The concern I have is... let's say $C\{j\}$ is 0. At that point the result would be $x^{16}+x7$, which is bigger than $W$ and I'd kinda expect it to less than W.

Why must the result be less than $W$ (bits)? If $W = 8$ then clearly we need more than one $W$ bit word to represent a polynomial with degree 113. There's no reason we can't have intermediate values that are also greater than one word. Again, see my answer above as to how represent a polynomial with multiple words.

  In the last step it says "Return($C[t−1],...,C[1],C[0]$)". What is $t$ supposed to be? It's not defined or referenced anywhere else. Maybe it's supposed to be the length of C?

Remember that $C$ represents a polynomial with degree up to 224. But we are reducing by $f(z)$ which is of degree 113, so we don't need all the words of $C$. In the introduction to Section 2.3 "Binary field arithmetic" it states "Let $t = \mathrm{ceiling}(\frac{m}{W})$", hence $t$ is the maximum number of words need to represent an element $\bmod{f(z)}$ where $m$ is the degree of $f(z)$.


The Tiger hash function was mainly a notable thing back in the days as it was designed to make efficient use of 64 bit processors.

Besides some other uses, Tiger was (and sometimes still is) often used for file integrity verification purposes in file sharing proggies, by using the Tiger hash function to build a Merkle tree… resulting in a so called “Tiger Tree Hash”. (The main advantage of such a tree is that you can verify the integrity of each subtree, even when the data is not yet completely available… as it happens – for example – when downloading torrent files).

Personally, I don't see many advantages to SHA-2 or BLAKE. Especially, since Blake etc. were also build with an eye on efficiency when it comes to 64 bit processors – which are somewhat standard for desktop computers et al nowadays.

As CodesInChaos already indicated, the only reason to use Tiger at all would be compatibility with existing protocols. For new protocol designs, I personally would skip looking at Tiger.


The security of this variant is no better than regular DES. To see this, consider an attacker with access to $\text{ENC}(M) = \text{DES}_k(M \oplus k_1)$ and $\text{DEC}(C) = \text{DES}^{-1}_k(C) \oplus k_1$, its inverse:

Obtain one (or more) plaintext-ciphertext pair $M, C$;
Iterate through all $2^{56}$ DES keys;
For each candidate key $k$, obtain $k_1 = \text{DEC}(C) \oplus \text{DES}^{-1}_k(C) = M \oplus \text{DES}^{-1}_k(C)$;
For the correct key $k$, $k_1$ is also correct. This can be confirmed by checking against a few known plaintext/ciphertext pairs.

DESX avoids these trivial attacks by making it impossible to obtain $k_1$ without knowing $k_2$, or vice-versa. Hence DESX's security for $56+64+64$ bits of key being only $2^{56 + 64}$ instead of $2^{56 + 64 + 64}$. The paper by Kilian and Rogaway goes into detail on this, but the gist of it is: iterate through $k$ and $k_1$, and get $k_2$ for free, as above.


How can a learnable function be obfuscable?

I am not sure what definition of obfuscation you care about, but in cryptography, we usually consider the virtual black-box obfuscation (VBBO) or indistinguishability obfuscation (IO). And as far as I can say, both definitions allow to extract learnable information from the obfuscated program (here learnable means learnable by querying the oracle having access to the original function). That is, the cryptographic obfuscation essentially does not hide anything about the learnable functions.
In other words, the cryptographic obfuscations do not rule out to learn something from the oracle access to the program. Instead, the cryptographic obfuscations do rule out the possibility to learn anything except the oracle access, or input-output behavior of the program. In particular, using the VBBO or IO, it is meaningless to obfuscate the learnable function with respect to security.
Let me briefly describe the (in-)formal definition of VBBO. A compiler $C$ that takes a program $P$ and outputs another program $C(P)$ is called VBBO if the following hold:
For any efficient algorithm $A$ that learns anything about $C(P)$, there is a simulator $S$ that learns exactly the same thing only via oracle access to $P$. More formally, it holds that
$$\Pr_{C,A} [A(C(P))\rightarrow 1] \approx \Pr_S[S^P ()\rightarrow 1].
$$
I omitted security parameters, negligible difference, etc. This definition does not prevent learning by querying the oracle having access to the original program.
Perhaps you are interested in this discussion.


Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently

Given a composite $N$, it is asked to construct a random $u$ in $\mathbb Z_N^*$ with $\big({u\over N}\big)=+1$ that is not a square $\pmod N$.

The method proposed in the question does not work. Counterexample: $N=77$; $x=7$; $y=53$ which is such that $x^2<y<(x+1)^2\le N$ and $\big({y\over N}\big)=+1$. However $y$ is a quadratic residue since $53\equiv19^2\pmod {77}$. Problem is, it is asked that $y$ is not a square $\pmod N$, but the construction method proposed in the question only insures that $y$ is not a square in $\mathbb N$.

Here is a method that works assuming we know just one fixed $s$ in $\mathbb Z_n^*$ with $\big({s\over N}\big)=+1$ that is not a square $\pmod N$:

generate a random $x\in\{1\dots N-1\}$, until $\gcd(x,N)=1$;
compute and output $u=s\cdot x^2\bmod N$.

Using multiplicative properties of the Jacobi symbol, that $\big({s\over N}\big)=+1$ and $\big({x\over N}\big)\ne 0$, it follows from the construction of $u$ that $\big({u\over N}\big)=+1$. And because $x^2\bmod N$ is a non-zero quadratic residue, and $s$ is a non-zero non-quadratic residue, their product $u\pmod N$ is a  non-zero non-quadratic residue. $u$ is random-like because $x$ is random. I conjecture (without proof) that $u$ is uniform on the desired set; that would follow from proof that each distinct $x^2\bmod N$ with $\gcd(x,N)=1$ has an equal number of square roots $\pmod N$.

It remains to construct $s$. That seems impossible in the general case without knowing the factorization of $N$; however, in some practical cases, $N$ could be generated so that its factorization is known but secret, which allows to efficiently generate $s$; then $(N,s)$ can be made public and the factorization of $N$ forgotten.

Here is how the generation of $(N,s)$ could go:

generate two large random distinct primes $p$ and $q$;
compute $N=p\cdot q$;
generate a random $s\in\{1\dots N-1\}$ until $\big({s\over p}\big)=-1$ and $\big({s\over q}\big)=-1$;
output $(N,s)$.

Using multiplicative properties of the Jacobi symbol, $\big({s\over N}\big)=+1$. Because $\big({s\over p}\big)=-1$ and $p$ is prime, $s$ is not a quadratic residue $\pmod p$; thus $s$ is not a quadratic residue $\mod{p\cdot q}$.

Update following Poncho's answer: if $N=p\cdot q$ with $p$ and $q$ primes such that $p\equiv3\pmod4$ and $q\equiv3\pmod4$, then $s=N-1$ does the job.


What happens if a SHA-256 input is too long (longer than 512 bits)?

If the input message is longer than 512 bits, the input is chopped in “chunks” (read: pieces) with fitting length (512 bits) and those are successively fed to the hash compression function.

See, in layman’s terms, SHA-256 processes things like this:

init SHA-256
while there are input chunks,
update hash compression function with the next input chunk (pad to 512 bits if needed)
finalize SHA-256 and return the result (which is the hash output)

As mentioned in “2”, when SHA-256 reaches a chunk which is less than 512 bits, it is padded accordingly… so that all input chunks fed to the hash compression function are exactly 512 bits long. For details on the padding itself, see “How is input message for SHA-2 padded?” and “SHA256: Padding a 512 bits length message”.

A note aside: The maximum message size which can handled by SHA-256 is $2^{64}-1$ bits, which means SHA-256’s compression function can handle up to $\lceil(2^{64}+64)/512\rceil$ of 512-bit input  chunks. In the (unlikely) case when you try to feed more input than the maximum, the hash function should refuse output (read: fail with error).


Relationship between special RSA modulus and quadratic residue in CL (Camenisch-Lysyanskaya) signature

The standard RSA ($c=m^{e}$ $mod(n)$) is not semantically secure, since it reveals one bit information about the message. This information is jacobi symbol of the message. You can find many resources about jacobi symbol but basically it states that a value is in $QR_n$ or not. In CL signature, we can handle with this situation easilly, since we determine the base values for exponentiation operations. If we choose the base values from $QR_n$, any exponentiation operation using them outputs another value from $QR_n$. Thus, there is no revealed information. Ofcourse, it comes with a disadvantage that any output of exponentiation is in $QR_n$ we decrase the number of possible outputs that we can get.


Multiplication and squaring the binary polynomials

What do you mean by trace of "bits" of $X$? How do you define $x_i$?

Since $263$ is prime, the field $\mathbb{F}_{2^{163}}$ has no subfields other than the prime field $\mathbb{F}_2.$ This means that the trace function $$Tr:\mathbb{F}_{2^{163}}\rightarrow \mathbb{F}_2$$ is the only trace which exists for this field. However, this means that the function $Tr(u)$ is equidistributed on $\mathbb{F}_{2}$, which means it is $0$ half the time and $1$ half the time as $u$ ranges over $\mathbb{F}_{2^{163}}.$

This property would also apply to any "bit" of $X$, reasonably defined as the coordinate of $X$ with respect to some basis element.

Edit:  If as in my comment $u=\alpha^i$, squaring gives $u^2=\alpha^{2i}.$
So square of $e_i$ is $e_{2i}$ but if $2i\geq n=163$  it needs to be reduced mod the field defining polynomial.

In $\mathbb{F}_{2^4}$. defined by $\alpha^4+\alpha+1=0,$
$\alpha=e_1=0010,$ $\alpha^2=e_2=0100,$ but $\alpha^4=\alpha+1=e_1+e_0=0011.$


I think PBKDF2 may be better than Scrypt? Looking for someone to point out my logical error

There's no point in using either an ASIC or a GPU to calculate a single password hash.  That's true whether you use PBKDF2 or scrypt or Argon2 or whatever.

What massively parallel devices like GPUs or ASICs are good for is hashing millions or billions of passwords at the same time.  That's useful if you're mining a cryptocurrency or trying to crack a hash for which you don't know the password, but not if you're just trying to test a single user-entered password to see if if it matches the account's password hash or not.  For that, it's much easier and more efficient to just calculate the hash on the CPU.

Basically, what parallel devices like GPUs and ASICs do is give an edge to the attackers, who have billions of passwords to test and don't really care about latency (i.e. the time it takes for a single password to get hashed) as long as the throughput (i.e. the average number of passwords hashed per second) is good.  That's why modern password hashing schemes like scrypt or Argon2 are designed to make GPU/ASIC hashing as hard as possible, so that the edge they give to attackers over legitimate authenticators is minimized.

(And yes, a botnet of compromised personal computers could indeed be used to crack scrypt hashes.   However, especially if most of those computers had half-decent graphics cards, they'd be even better at cracking PBKDF2.)


Can an RSA (private) modulus contain (hex) zeroes?

There is no such thing as a "private modulus". There are the secret primes and the secret exponent, and there is the public modulus. Assuming you are talking about the primes or the secret exponent, are these bits in the most significant (leftmost) position, or are they somewhere in the middle or end? If they are in the most significant position, then they do not count towards the size of the integer. After all, any finite integer at all can be thought of as having an infinite number of leading zeros! If the zeros are somewhere within the integer, they serve to change its value. A random integer is expected to have a few null bytes.

Think about it this way: there is no difference between 0123 and 00123 (both are the same number), but there is a big ten-fold difference between 1230 and 12300, despite both adding a single zero. Of course this is base 10 whereas hex is base 16, but the principle is the same and zero means the same thing.

You can easily calculate the size of your key by taking the ceiling of the binary logarithm of the public modulus. That is, you can calculate $\lceil\log_2(N)\rceil$ for an integer representation of the public modulus $N$.


Difference between SHA 512, SHA 512 Half, SHA 256

SHA-256 is a function with up to $2^{64}$ bits of input, which are broken into 512-bit blocks, and with a 256-bit output.  It is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 128-, 256-, and 256-bit security levels, but it has the unfortunate property that given $\operatorname{SHA-256}(m)$ but not $m$, it is relatively easy to compute $\operatorname{SHA-256}(m \mathbin\Vert p \mathbin\Vert m')$ for an arbitrary suffix $m'$, where $p$ depends only on the length of $m$.

SHA-512 is a function with up to $2^{128}$ bits of input, which are broken into 1024-bit blocks, and with a 512-bit output.  It is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 256-, 512-, and 512-bit security levels, but it has the unfortunate property that given $\operatorname{SHA-512}(m)$ but not $m$, it is relatively easy to compute $\operatorname{SHA-512}(m \mathbin\Vert p \mathbin\Vert m')$ for an arbitrary suffix $m'$, where $p$ depends only on the length of $m$.

‘SHA-512half’ is probably SHA-512 truncated to 256 bits.  Thus it takes up to $2^{128}$ bits of input, broken into 512-bit blocks, and yields a 256-bit output.  Like SHA-256, it is conjectured to be collision-, preimage-, and second-preimage resistant at (resp.) 128-, 256-, and 256-bit security levels.  Unlike SHA-256 or SHA-512, to compute $\operatorname{SHA-512half}(m \mathbin\Vert m')$ for any $m'$ (whether with the padding $p$ or not) given only $\operatorname{SHA-512half}(m)$ and not $m$, it is conjectured to cost at least an expected $2^{255}$ SHA-512 computations.

The functions SHA-256 and SHA-512 resemble independent uniform random choices of function, except for the length extension property, whereas SHA-512 and SHA-512half are obviously not independent since SHA-512half is just half the output of SHA-512 on the same input.  SHA-512/256 is like SHA-512half, except it it uses different initialization vectors and thus resembles another independent uniform random choice of function.


Firstly, I assume you use the $\ll$ not as in number theory where $f(\ell)\ll g(\ell)$ means $f(\ell)=O(g(\ell))$ but as much less than, which usually means $$f(\ell)\leq \frac{g(\ell)}{h(\ell)}$$ where $h(n)$ is some increasing function of $\ell.$ The crucial question is how fast is $h(\ell)$ growing?

To break the cryptosystem in parallel polynomial time, you need an exponential number of processors, unless $h(\ell)$ is itself growing very fast in $\ell.$ In fact this argument could apply to any cryptosystem which is considered secure, such as AES, for example. And this is NOT far better than brute force, it is just parallel brute force in the presence of the obvious embarrassing parallelism in the key space, since you need to deploy an exponential number of processors, as in the EFF key search attacks on DES.

What I am trying to say, not very well, is that any secure cryptosystem is insecure under parallel computation to some extent. So I'd say in answer to your first question, this is not a real weakness.

As to your second question, yes, if $S(P,K)$ is subexponential in size, this is a real weakness.

And finally, since you are talking algebraic attacks, presumably you have an algebraic specification of what $S(P,K)$ looks like, which you can use in your attacks.


Can I discard a specific X509 signature from file?

Cryptographically speaking, a digital signature provides the property of non-repudiation -- the signer cannot deny signing once signed. So, you either have to keep the unsigned version if you can't strip the signature from the document, or sign another document invalidating the previous signature if the previous document has been released.


Is CBC block cipher mode susceptible to reordering attacks?

CBC is almost as vulnerable to reordering attacks as ECB. Sometimes you can get garbage, but you can certainly move e.g. two blocks and know that the second block will decrypt to the same plaintext as the original.

With ECB you cannot easily change the last block if padding is used. If the last block doesn't contain correct padding then an error may be generated during decryption. With CBC this is extended to (the last part) of the first-to-last block of the ciphertext.

All this is quite useless though. To protect modes such as ECB and CBC against change you should simply add an authentication tag over the ciphertext (and IV, if that is send). If active attacks are possible then padding oracle attacks may be possible as well; an authentication tag would protect against both.

So adding an authentication tag (MAC) or using authenticated encryption (such as GCM mode) is the best way to protect the message integrity and authenticity. That way you don't have to rely on the plaintext message / padding to detect errors.

You can of course have two ways of reordering ciphertext when it comes to CBC. You can reorder the blocks in a message or reorder the messages themselves. Sequence numbers protect against the latter.

This is quite a separate issue; reordering messages can be performed regardless of which mode is used. CBC certainly won't protect against the reordering of messages.


Meaning of $\operatorname{UOWH}(k; u_1, u_2)$

If you look up the reference [BR97] in the paper, it clearly states that $k$ is the key which is used to select a hash function from a family of hash functions and the rest of the part of the input i.e. $u_1, u_2, u_3 ...$ is the input to the selected hash such that $u_i$ is the input to $UOWH(k;u_1,u_2,...,u_i-1)$


The recovery rate is unaffected by feeding Fortuna with a single source.

This is Fortuna:

The 32 entropy pools live inside the accumulator.  The accumulator collects entropy via the following function:-

function AddRandomEvent
input: R prng state, modified by this function.
s Source number in range 0, ... , 255.
i Pool number in range 0, ... , 31. Each source must distribute its
  events over all the pools in a round-robin fashion.
e Event data. String of bytes; length in range 1, ... , 32.

Ferguson et al. suggest feeding the pools in a round robin fashion. I disagree as they never catered for a steady entropy rate.  They have developed /invented this equation to bound the recovery time:-

with t = time, i = 13 and t being time.  At 8 bits /s, this leads to t being 1/8th second. I can't get my head around it and believe it to be technobabble to paper over the fact that they have no input entropy estimator.  They explicitly state that input entropy measurement is irrelevant to the security of the PRNG. From the architectural diagram above, your entropy enters the accumulator at a rate of 8 bits /s.  Fortuna's creators have decided that 128 bits of security is sufficient.  It follows then that even with a fully compromised generator state, total recovery to design level security should occur in 8 seconds. And the generator is always seeded with at least pool 0, so I suggest feeding entropy directly into that pool only.

There is a get out of jail card for the authors in their statement limiting the feasible attack vectors. They disallow the attacker controlling the destination pool for his attack entropy.  Hence the round robin method of securing the reseeding.

For the life of me, I cannot fathom the wisdom of multiple entropy pools.  If all pools are eventually used for reseeding, why can't you have a single pool as the default Linux generator has?  That works. I think that some of the analysis problems might be to do with the huge complexity of design.  There are so many variables that it's difficult to perform a rigorous mathematical analysis.  The main confounding factor is the automatic reseed rate affected by rapid output.  I suspect that only a Monte Carlo simulation can resolve this accurately.  Remember that these guys invented Yarrow and that didn't work well enough to stay with. And I don't like it as it's too complicated and unpredictable(!).


Miller's algorithm is a loop over the group size; let's say it has $n$ bits. (The group size is usually near the prime $p$ of the underlying field)

Each iteration of the loop computes a point doubling and maybe a point addition, and a bunch of field multiplications (or squarings). That sets a upper limit of a constant number of field multiplications in each iteration. The complexity of naive multiplication is $O(n^2)$; with Karatsuba it is $O(n^{\log_2{3}}) = O(n^{1.585})$. Therefore that's the complexity of each iteration.

Thus, since there are $n$ iterations, the complexity of Miller's algorithm is $O(n^3)$ with naive multiplication and $O(n^{2.585})$ with Karatsuba.


Why should one use a cypher-based message authentication code (CMAC) instead of symmetric encryption and CRC?

The main reason to use a proper cryptographic authentication code is to ensure the very properties you listed. Your proposal of ciphertext and CRC (encrypted or not) fails to provide those.
Let's consider three possible arrangements of data transmission with CRC:

Plaintext message and CRC:
CRC (Cyclic Redundancy Check) is meant to detect errors in transmission or storage.
It is a straightforward algorithm with a single input (the message) and a single output (the CRC code). As such it cannot provide protection against willful modification of the data as anyone can compute the new CRC code.
This means we would need to ensure the CRC cannot be manipulated.
Let's take up your first proposal:

Encrypted message, plaintext CRC:
One big problem here: CRC is not a cryptographic hash function, nor was it ever supposed to be. It has too many chances of leaking information about the plaintext.
The properties in the next section also mean that they can modify the encrypted message AND properly modify the CRC.

Encrypted message and CRC:
One notable property of CRC is that $\operatorname{CRC}(x \oplus y) = \operatorname{CRC}(x) \oplus \operatorname{CRC}(y)$.
block ciphers modes operate using the XOR operator over a mix of plaintext, key, IV, previous ciphertext, etc...
In some cipher modes, XORing the ciphertext is the same as XORing the plaintext. For example, the counter block cipher mode boils down to: $\text{ciphertext} = \text{plaintext} \oplus \operatorname{AES}(IV)$
To fake the message, I can compute $\text{diff} = \text{plaintext} \oplus \text{desired_plaintext}$ and return the following:

new ciphertext: $\text{ciphertext} \oplus \text{diff}$
new encrypted CRC: $\text{encrypted_crc} \oplus \operatorname{CRC}(\text{diff})$

I have effectively modified the message and its CRC without having to break the encryption.
You can find further reading and references in the data integrity section of the CRC wiki page.

[EDIT: credit goes to Maarten Bodewes] CRC size limitations:
CRC's are generally limited to 32 bits (although 64 bit CRC's have been defined), which is not enough to provide 128 bits security. Just trying in the order of $2^{32}$ random messages (or separate connections) would give you a chance of ~0.63 to get one right. That's simply to high of a chance even if CRC could not be attacked by other means.
Now it is possible to create a MAC by performing a relatively fast operation over blocks of 128 bits / 16 bytes and then encrypt the result. These kind of techniques are used for GMAC (in AES-GCM) and Poly1305 used within ChaCha20/Poly1305 used in - for instance - TLS 1.2 and 1.3. These still rely on a block cipher for security, but the block cipher is only used once or twice instead of for each block of the message.
Note that GCM and ChaCha20/Poly1305 operate on the ciphertext rather than the plaintext, but that can be considered an implementation detail. Generally you want to verify message authenticity before decryption.

You may also be interested in one of the secure OCB modes (1 & 3) which integrates both authentication and encryption, doing away with any additional (computationally intensive) operations on the data.


How Pairwise Transient Key is derived or generated?

The page you linked to directly gives the algorith to calculate ${\rm PRF}(K, A, B, Len)$:

$\hspace{2em} \textbf{for }i \leftarrow 0 \textbf{ to } (Len+159)/160 \textbf{ do} \\
\hspace{4em} R \leftarrow R \mathbin\| \text{H-SHA-1}(K, A, B, i) \\
\hspace{2em} \textbf{return } \text{L}(R, 0, Len)$

The helper function $\text{H-SHA-1}$, the string concatenation operator $\|$ and the meaning of the parameters are all defined just above this code on the page.  The helper function $\rm L$ does not seem to be defined on the page you linked to, but from context, it seems likely that ${\rm L}(R, 0, Len)$ is meant to return the first $Len$ bits (i.e. the first $Len/8$ bytes) of the string $R$.  You'll probably find its precise definition somewhere earlier in the document.

(Also, the algorithm as given doesn't specify the initial value of the string $R$, but it seems obvious enough that it's meant to be initially empty.)

Below this algorithm, the page defines five specific "wrapper functions" $\text{PRF-}X$, for $X \in \{128, 192, 256, 384, 512\}$, simply as $$\text{PRF-}X(K, A, B) = \text{PRF}(K, A, B, X).$$  Note, however, that the page also says that different definitions of these wrapper functions, given at the end of the page and the beginning of the next page, are to be used in some cases ("When the negotiated AKM is 00-0F-AC:5 or 00-0F-AC:6...").

In any case, this looks like a common way to extend the HMAC pseudorandom function, which has a variable input length but a fixed output length, into a variable-output-length PRF by repeatedly invoking it with the same input combined with an incrementing counter, and concatenating the results.  It looks quite similar to e.g. HKDF-Expand, although HKDF also feeds the previous HMAC output as input to the next HMAC call in order to (hopefully) make any cryptanalytic weaknesses in the underlying hash function harder to exploit.  (See section 7 of the HKDF paper for the designers' rationale for this.)


Why use symmetric encryption in a protocol like UPORT?

It's multi-layered encryption. If you "layer" your encryption you gain quite some nice flexibility features which is what they have done here.

You have some secret ($A$) which you only wish to share with parties $X,Y,Z$ for which you also know the public key. So what you do is that you first pick a random public-private-keypair $R$ yourself and derive a new shared secret with each of them. Now you have three shared secrets which would mean you'd have to encrypt three different copies of your message $A$. Instead you only encrypt a key $k$ three times using the shared secrets (using DLIES) and then in turn use $k$ to grant access (by means of symmetric encryption) to $A$. This approach saves you quite a bit of bandwidth and computational power there as you only need to encrypt a large message once instead of three times.

In a graphic, this process would look like this (don't forget that $k$ is small and $A$ is potentially large):


Is post-quantum Oblivious Transfer possible

Post-quantum oblivious transfer protocols are possible. If you base the security of the OT in a post-quantum assumption, this should give you an OT conjectured to be robust to quantum attackers. Besides the already mentioned OT based on supersingular isogeny (in comments), I can give you some other examples:

Code-based: https://eprint.iacr.org/2008/138.pdf , https://ieeexplore.ieee.org/document/6089575

Lattice-based: https://eprint.iacr.org/2018/530

There are also some constructions for OT ,secure in the Universally Composable framework and based on post-quantum assumptions, such as

https://link.springer.com/chapter/10.1007/978-3-319-12280-9_10

based on the LPN assumption, and the ones that can be instantiated using the frameworks of:

https://eprint.iacr.org/2007/348.pdf

and

https://eprint.iacr.org/2017/993.pdf

using post-quantum encryption schemes.


Don't truncate one-time-macs (e.g. GHash or Poly1305) because a successful forgery reveals part of the key. Poly1305 might be fine, if the receiver ensures nonce uniqueness and you derive the complete Poly1305 key from the nonce (i.e. both the multiplier and the mask).

On the other hand, truncating HMAC or MACs based on CBC-MAC (e.g. CMAC) is fine (I think it even avoids the prefix-weakness of plain CBC-MAC).

I would not consider CRC32, it's unkeyed and I can't think of an easy to build a secure MAC from it (GHash is probably the closest thing to a secure CRC).

I recommend going with a truncated HMAC. It's designed to be a PRF and since truncated PRFs are still PRFs, you can be certain that it has no weaknesses beyond the obvious $2^{-32}$ forgery chance.


Seen this? http://www.cvnguyen.ngocnga.net/tech/enigma/

This guy seemed to have it working on GPU back in 2009


Why is the simulation required in these identity-based encryption security proofs?

(I assume you are asking about this paper based on your previous questions.)
They do not prove BDDH in their security proofs.

  Assume that an attacker $A$ breaks IND-sMID-CPA of the above scheme
  with probability greater than $\epsilon$ within time $t$ [...]. We show that using $A$, one can construct an attacker $B$ for solving the
  BDDH problem.

In security proofs by reduction, we assume the proposition is not true (here: assume the proposed scheme is not IND-sMID-CPA) and show the proposition being false would imply some contradiction (here: solving BDDH problem which is believed to be hard). In this case assuming existence of attacker $A$ against IND-sMID-CPA security of the proposed scheme, they construct algorithm $B$ for solving the BDDH problem. Attacker $A$ is expected to participate in IND-sMID-CPA experiment, so through the reduction algorithm $B$ should simulate the experiment for $A$ and since this proof is in the random oracle model, $B$ should simulate random oracle as well.

  problem B is reducible to problem A if an algorithm for solving problem A efficiently (we call this algorithm $A$) (if it existed) could also be used as a subroutine to solve problem B efficiently.

In this context:

A = breaking IND-sMID-CPA
B = BDDH problem

reduction algorithm $B$ uses adversary $A$ as a subroutine. $B$ doesn't know how $A$ works; the only thing $B$ knows is that $A$ is expecting to attack problem A. so given an input instance of problem B (here BDDH), reduction algorithm should generate (simulate) an instance of problem A for $A$.

Chapter 3.3.2 of Introduction to Modern Cryptography explains "proofs by redcution".