Is it important to defend against key substitution attack in ECDSA?

So the question may be rephrased to—is it still sane to use raw ECDSA signature in 2019?

It's not insane, but you should use Ed25519 in any new applications: it is faster, simpler, and more confidence-inspiring.

However, the standard notion of security of a public-key signature scheme—EUF-CMA, or existential unforgeability under chosen-message attack—says nothing about whether a signature that is valid under one public key may also be valid under another public key.  Let's call this property public key uniqueness.

Some exotic applications may rely on public key uniqueness, e.g. the Let's Encrypt name ownership verification protocol Acme was accidentally designed to rely on it at first[1], but most signature schemes do not provide this additional property, because most applications don't need it: you don't bother verifying a message with a public key unless you know the public key is good to begin with.

Neither ECDSA, nor RSASSA-PKCSv1_5, nor RSASSA-PSS provides public key uniqueness out of the box.  There are many additional security properties that exotic applications might want: key anonymity, public key uniqueness, signature uniqueness (which Monero accidentally relied on[2] in their exotic application), verifiably unique pseudorandomness (a.k.a. VRF), etc.  But most applications don't need them.

Rather than worry about exotic properties that an application once made the mistake of assuming, you should focus on what your application actually does need, by writing down what resources you rely on, what resources the adversary can control that you take action on, etc.

As it happens, Ed25519 does provide public key uniqueness, because the public key is hashed together with the message as part of making a signature.  This is a generic structure that probably works to turn any EUF-CMA signature scheme without public key uniqueness into one with it, as the note you quoted suggests, although it has the consequence that it essentially rules out another exotic property, message recovery[3].


Pick a coordinate field $\mathbb F_p$, such as $p = 2^{256} - 2^{32} - 977$.  Pick an elliptic curve over $\mathbb F_p$ of the form $y^2 = x^3 + a x + b$, such as $a = 0$ and $b = 7$.  (This is the curve secp256k1 used in Bitcoin.)  Pick a standard base point $G$ of prime order $\ell$, so that $\ell$ is the smallest positive integer such that $$[\ell]G = \underbrace{G + \cdots + G}_{\text{$\ell$ times}} = \mathcal O.$$  Here $\mathcal O$ is the ‘point at infinity’, or the identity of the group.

An ECDSA public key is a point $P$ on the curve with coordinates $(x(P), y(P))$.  An ECDSA signature on a message $m$ under $P$, is a pair $(r, s)$ of integers with $1 < r, s < \ell$ such that the verification equation $$r \equiv f\bigr([H(m) \, s^{-1}]G + [r s^{-1}]A\bigr) \pmod \ell$$ holds, where $f(A) = x(A) \bmod \ell$ is a kind of arbitrary function mapping the $x$ coordinate field $\mathbb F_p$ to the scalar ring $\mathbb Z/\ell\mathbb Z$ (which is a rather weird thing to do, but such is life).

The signer knows the secret scalar $e$ such that $P = [e]G$, in terms of which this equation is $$r = f\bigl([H(m)\,s^{-1}]G + [r s^{-1} e]G\bigr) = f\bigl([H(m) \, s^{-1} + r s^{-1} e]G\bigr),$$ which means the signer can choose a per-signature secret $k$ uniformly at random, derive $r = f([k]G)$, and then solve the scalar equation $$k \equiv H(m)\,s^{-1} + r s^{-1} e \pmod \ell$$ for $s$, by computing $$s := [H(m) \, k^{-1} + r k^{-1} e] \bmod \ell.$$


In PKI, with a hash-encrypted message (first hashed, then encrypted), how is the plaintext ever retrieved?

Signature generation is not encryption with the private key. Still, the basic flow of what you describe is correct for signature generation. However, the verification step is where everything derails.
As indicated in the comments, it is impossible to reverse a cryptographic hash. However, for signature verification, it is assumed that the verifying party knows the signed message M. The verifying party can then re-calculate the hash and use that as input for the rest of the verification procedure. So if the verifying party doesn't have the message M then you simply need to send it together with the signature.

See for instance step 2 in RSA signature verification specified for the PSS signature scheme:

Input:
      M      message to be verified, an octet string
      ...

and then later:

 ...
 2. Let mHash = Hash(M), an octet string of length hLen.
 ...

The verification procedure may indeed involve retrieving the original hash and perform comparison. However, other signature verification functions such as the verification function of ECDSA may simply require the re-calculated hash as input for the verification function. So in that case the original message hash isn't even retrieved from the signature.

There are schemes that perform message recovery. A few of those schemes are outlined in ISO/IEC 9796-2: Digital signature schemes giving message recovery. However, they are not often used anymore. In that case the message itself - or at least part of it - is included with the hash, the message is still not retrieved from the hash.

Remember that signatures do not provide message confidentiality. If you also want to keep your data secret then you should encrypt the data and signature over the data.


From the way I understand your question, your encryption scheme works as follows:

For a message consisting of $\ell$ blocks $m=m_1\|\dots\| m_\ell$ and a key $k$ the ciphertext $c=c_1\|\dots\| c_\ell$ is computed as
$c_1:=m_1\oplus H(k)$ and $c_i:=m_i\oplus H(c_{i-1},m_{i-1})$ for $2\le i \le \ell$.

This scheme has several problems. First of all it's deterministic and therefore cannot be CPA secure, the basic minimum we generally require of an encryption
 scheme.

But it gets worse. In any standard definition of security, it is assumed that the attacker can choose, or at least know, parts of the plaintext. In your scheme, if the attacker knows the $n^{\text{th}}$ plaintext block $m_n$, they can compute $H(c_n,m_n)$ and thereby reveal the next plaintext block (and by extension the rest of the message).


entropy is the measure of surprise

That's informal, short and non-quantitative, but correct within that. In the case of a Random Number Generator, we must make that: entropy is the measure of surprise in the outputs of the RNG, for one skilled person (with arbitrarily large computing power) knowing the RNG design including any parameter (for MT: the Mersenne prime used, and a few others). That's for unknown seed (if any) assumed uniformly random but arbitrarily large computing power of the skilled person (unless otherwise stated).

The entropy considered here is a property of the generator, not that of one particular bitstring that it outputs.

Entropy further can be defined for the total output of a generator, or per output bit. In cryptography we measure the entropy in bit, so that it is 1 bit per output bit for an ideal uniform True RNG.

For any Pseudo RNG, the whole output is predictable from design, parameters and seed, hence the entropy in the whole output is limited to the entropy in what generates its seed, which is finite. And the entropy per output bit decreases to zero as the output size increase towards infinity.

  the Mersenne Twister(MT) has high entropy.

No, because it is a PRNG (see above).

  the MT is also predictable.

Yes, with enough output, and little computing power.

  What's the relationship between entropy and predictability?

If a bitstring generator has the property that it's full output is predictable from a finite length prefix (as is the case for MT), then this generator has finite total entropy (bounded by said finite length in bits for Shannon entropy in bits), and vanishingly small entropy per output bit.

The converse is false for practical definition of (un)predictable. In particular, there exist practical Cryptographically Secure PRNGs (thus of finite total entropy) that are practically unpredictable.

To make things quantitative: consider a generator $G$ of arbitrarily long bitstrings. Note $G_b$ that generator restricted to its first $b$ bits. $G_b$ is susceptible to generate $2^b$ different $b$-bit bitstrings $B$ with respective probability $p_B$ (possibly $0$ for some $B$), with $1=\sum p_B$ (the sum being over $2^b$ terms $B$). $G_b$ has Shannon entropy in bits
$$H(G_b)=\sum_{B\text{ with }p_B\ne0}p_B\,\log_2\left(\frac1{p_B}\right)$$
and its average entropy per bit is $H(G_b)/b$.

For an ideal TRNG (which output is uniformly random independent bits), and any $b$, all $b$-bit bitstrings are equiprobable with $p_B=2^{-b}$ and it comes $H(G_b)=b$.

For any PRNGs with $s$-bit seed (per any distribution), $H(G_b)\le \max(b,s)$. The entropy of the generator's whole output is $H(G)=\displaystyle\lim_{b\to\infty}H(G_b)$. That is maximal with $H(G)=s$ when all seeds generate different outputs and the seed is uniformly random.


Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

This scheme does not have indistinguishable encryptions since the encryption function does not use the key, so an adversary can run the decryption function in the same way as the intended recipient.
This scheme is not CPA-secure because it is deterministic (so it does not even have indistinguishable encryptions for multiple messages). To show that it has indistinguishable encryptions for a single message, we first note that if $f$ is a random function, $f(0^n)$ is uniformly distributed and we get a one-time pad. Now, if a distinguisher $D$ can distinguish $m_0\oplus F_k(0^n)$ from $m_1\oplus F_k(0^n)$, we can distinguish $F_k$ from a random function as follows. A distinguisher $D'$ chooses at random $b\in \{0,1\}$ and runs $D$ on $m_b\oplus O_{D'}(0^n)$. $D'$ outputs $1$ if $D$ answers correctly, and $0$ otherwise. If $O_{D'}$ is a true random function, $D$ answers correctly with probability exactly $1/2$. On the other hand, if $O_{D'}$ is $F_k$ for a uniformly chosen $k$, then by hypothesis $D$ answers correctly with probability non-negligibly higher than $1/2$, which translates to a distinguishing advantage for $D'$.
This scheme is CPA-secure, try to apply the idea of the previous one to transform a distinguisher for the encryption scheme into a distinguisher for $F$.


Estimating difficulty of "Memory-Hard Proof-of-Work" based on "size of memory"?

The measure of resource typically used to evaluate memory-hard functions is not the amount of work (i.e., $T$-complexity) but rather the space-time complexity (i.e., $ST$-complexity) of the computation. As the name suggests, it is the product of the maximum amount of space used and the time taken for the computation. (Strictly speaking, we have to also take in account amortization of the cost and the exact measure used is the cumulative space-time complexity, but the notion of space-time complexity still conveys the basic ideas: see [AS] for more details.) Good memory hard functions require $ST=\Theta(n^2)$.

The motivation behind this switch is to discourage the use of ASICs in computing proofs of work. The rationale of using ASICs in computing proofs of work is that they are much faster than CPUs. The speed-up is primarily due to its application-specificity, and the availability of large-scale parallelism. However, there is an asymmetry in the cost of memory (space, i.e.) as it is much costlier in ASICs compared to CPUs. Therefore, if one can construct a function that can be computed “fast” using “sufficient” space (even) on a sequential machine, but takes “more” time if the amount of space used is “lesser” (even with parallelism), then ASICs are not practical anymore as the increased cost of memory counteracts the increased computation power, but computing the function is cheap on a GPU.

Now, to your questions.

  If we use a Memory-Hard-Proof-of-Work scheme, the difficulty of Proof-of-Work is still estimated based on the hashing power? OR based on the size of memory?

The amount of work considered is still in terms of the amount of hashing power, the role of the memory as explained above is just to discourage the use of ASICs.

  In other word, is it feasible to design a Memory-Hard-Proof-of-Work scheme in which we could estimate the Pow difficulty based on the size of memory, instead of hashing power of participants?

There has been a lot of work in the recent years addressing this exact question --- the main motivation being that if space is used instead of work/time as a resource then there would be less energy wasted. The object is called a proof-of-space [D+,A+,F] and the prover/miner is rewarded for dedicating some disk space instead of doing work. (There is also a cryptocurrency, called Chia, that is being deployed based on proofs of space.)

[AS]: Alwen and Serbinenko. High Parallel Complexity Graphs and Memory-Hard Functions.

[A+] Abusalah et al. Beyond Hellman's Time-Memory Trade-Offs with Applications to Proofs of Space

[D+]:  Dziembowski et al. Proofs of Space

[F]: Fisch. Tight Proofs of Space and Replication


Randomly initialised global counter used to encrypt the kth message with $\operatorname{IV} = \operatorname{IV} + k \hspace{5mm} mod \hspace{5mm} 2^n$

A block cipher, per se, does not have a notion of initialization vector.  But a randomized or stateful message cipher may.  If you're building an application, you should forget the concept of ‘block cipher’ altogether: the fact that some cryptographic magic is built out of a pseudorandom permutation family whose name is spelled A-E-S is not important to you; the security contract of the result, including your obligations and the security you get in exchange, is what's important.

For a randomized cipher like AES-CBC, your obligation in the security contract is to choose an IV unpredictably.

If, given the first message's IV, the adversary can guess the second message's IV, the security contract is voided.  This mistake was exploited to recover plaintext in ssh sessions in 2009[1] (paywall-free).
For a stateful cipher like AES-CTR, your obligation in the security contract is typically to choose a nonce uniquely, which you can do by counting.  (The ‘nonce’, for number used once, is sometimes called an ‘IV’, but some authors—like this one—prefer to reserve the term ‘IV’ for unpredictable ones.)

It does not matter if the adversary can predict the nonce in advance, as long as the sender never repeats a nonce.  As a bonus, you can immediately detect buggy implementations by having the receiver require the nonces to be sequential.

One can always safely use state to choose the IV for a randomized cipher, by deriving it by a pseudorandom function of the number of messages so far; and one can choose a nonce randomly for a stateful cipher, but at risk of nonce collision, so it's not so safe.

All this said, you should really use an authenticated message cipher.  Even if an adversary can't read secrets in an encrypted message by eavesdropping, without authentication you might act on adversary-controlled input which causes secrets to leak.  Examples of authenticated ciphers include:

AES-GCM, with a message sequence number for the 96-bit nonce;
NaCl crypto_secretbox_xsalsa20poly1305, with a message sequence number or uniform random nonce, since the 192-bit nonce is large enough to be safely chosen uniformly at random; or,
if you must use AES-CBC, at least use it in encrypt-then-MAC composition with HMAC-SHA256 or similar, and the sender must choose the IV unpredictably for each message.


Are large polynomials secure for order preserving "hashing"? (newbie question)

The basic method is easily cracked: it is well known how to find a polynomial of degree at most $k$ from $k+1$ (input, output) pairs; that's the polynomial interpolation problem. There are numerous ways to efficiently carry it for high degree and large integers (one such method is to carry it modulo some medium primes, and use the Chinese Remainder Theorem in the end).

"pre-transforming" alone does not help at all against the above.

"post-transforming" and "adding a random deviation" makes recovering the polynomial more difficult. However, some simple attacks remain feasible, depending on adversarial model. In particular, if the adversary can query the function for arbitrarily large input: the degree of the polynomial and the highest degree coefficient of the polynomial divided by commonDivisor are easily found; then the attack can be repeated by subtracting known high coefficients, until finding all coefficients; in this setup, commonDivisor does not help much.

I do not see how to make the idea secure in a cryptographic sense.

Also: It does not seem that the "post-transforming" method proposed is guaranteed to maintain the property that distinct input leads to distinct output.

Addition following comment: if input is not known, that makes attack harder; however

you proposed: lets assume I have transformed all integers from 0 to 1000, and in cryptographic terms that's to be assimilated to a lot of known plaintext;
known plaintext has been a standard assumption for about as long as cryptography matured to a science, for reasons similar to the above;
as the saying goes: attacks only get better; they never get worse.


How to sign a CRL file if I have offline keys?

At some point your Root CA has to have control over it's subordinate CAs.  If there was a scheme where it delegates this control to another server (such as your OCSP-like suggestion), the Root CA would still need to have control over this service in some way or another.  In order to assert this control you would at some point need to power up the Root CA.  A scheme where the Root CA delegates full control to another service would mean that the Root CA effectively loses control; which is not what you want.

The standard way is to have the Root CA generate long-lifed CRLs.  This is relatively safe as the only certificates it issues are to a very few subordinate CAs and these CAs are (should be) securely operated in accordance with the PKI's Certificate Policy with a statement describing this operation in the CA's Certification Practice Statement.

Therefore, every (for example) six months:

Switch on the Root CA;
Generate a new CRL;
Export the CRL (for example using a CD/DVD burner);
Switch off the Root CA.

This process should be formalised and if you have concerns about someone running away with a copy of your Root CA's private key, your PKI Management Authority can/should insist on the use of witnesses and/or CCTV or any other scheme it deems fit.


Yes.

Non-ethereum elliptic curve signatures result in the numbers r and s, both of which need to lie in the range [1,n-1], where n is the size of the order of the elliptic curve base point. See Wikipedia - Elliptic Curve Digital Signature Algorithm.

Ethereum transaction signatures, use the secp256k1 curve (which has a fixed n value) and requires the numbers v,r and s. r has the same range as above, however unlike standard elliptic curve signatures, s is restricted to the range [1, n/2+1] (see the Ethereum Yellow Paper - Appendix F). Any values of r and s outside these ranges will generate an invalid signature.

Assuming we stick to r and s values within this range, we must also supply a v value for an Ethereum transaction signature. EIP-155 specifies v = CHAIN_ID *2 + 35 or v = CHAIN_ID*2 + 36.

The r value represents the x-value of a point on the scep256k1 curve. Fundamentally, v, represents the parity (even or odd) of the y-value of the point given by r (i.e the corresponding x-value). This parity determines whether to use 35 or 36 in the specification of v above. The value v is used as the recoveryid or recid in this library for ECDSA recovery on line 89 which is used by go-ethereum. Incorrect v values may make this recovery incorrect and give invalid resulting public keys. Thus, if one were to keep v fixed, and randomize r and s (or equivalently, randomize all numbers) within their range of validities and we were to assume an equal chance of getting an odd or even number, we would expect on average, 50% of signatures to be invalid (because we have an incorrect parity).


Are there any long term RC4 bias based exploits?

I'm happy to have a crack at this one, providing I've understood your question correctly.

Firstly I wouldn't say the cipher possibly exhibits low level bias at any point. It experiences plenty of bias and I'll attempt to explain how we can use it to launch practical attacks. As I'd imagine you know, the strongest bias is found right at the start of the KSA, in fact there are numerous biases in the KSA, but the KSA only represents the first 256 bytes, assuming we don't drop any.

The problem is, there's plenty of evidence (not just speculation) of the biases extending to any point in the key stream (asin the PRNG or PRGA part). See this again.

Your question asked for real world attacks?
Well contrary to some prior belief that because BEAST did not effect RC4 TLS, that RC4 was suitable for TLS, I'd recommend reading this as suggestion otherwise or alternatively this.

The Bar Mitzvah Crypto attack, discovered and demonstrated by Itsik Mantin in 2015, should be the best proof that the IETF were onto something when they introduced the idea to ban RC4 altogether in TLS the year before.

I know you were probably looking for something more in an answer but considering the question, this is about all there is to be said. How practical you think The Bar Mitzvah Crypto attack is, may be a question for debate.... but if we accept that NSA gathering of information, constantly with the same patterns in it (do I really need citations for this?), then it absolutely is the case that long key streams show significant enough bias and having enough of them allows data recovery and even in the circumstances of especially weak keys, key recovery all together.

If we have a heavily biased round (the KSA) and a knowingly biased round (the PRGA) plus a handful of real world exploits, we can assume the attacks will only keep getting worse, but yeah: it's already practical to use bias to attack RC4, even in RC4-drop-768.

EDIT

It's probably worth reading this too Mathy Vanhoef and Frank Piessens, go into huge detail on biases


Hash and sign via trapdoors for lattices

No: the parameter $m$ and the size $B$ of the coefficients of $(s,e)$ would not be the same in both scenarios. In the first (LWE decryption) the matrix $A$ is high and narrow, which makes the function `strongly injective', and decoding is possible. Most images do not have preimages, i.e., only a small fraction of $y$ are decodable, those corresponding to proper encryption. For (SIS) signature the matrix is wide and short, so that most images have many preimages. The term decodable should not be applied here nevertheless, since, well, the preimage is not unique.
No. There is no need to try several times, though care must be taken to avoid `learning attacks' such as this one. This is the role of Gaussian sampling.


Which stream cipher can we replace the RC4 in the SSL?

There are several ways to answer your question:

You cannot "replace" RC4 in SSL. SSL is a standard protocol in which any algorithm may be used only if both client and server support it and agree to use it. Thus, in practice, you do not get to replace algorithms as you wish, unless you control both client and server code; and even then, it would not longer be "the standard SSL (actually known as TLS)" but a custom variant.
If we want to define a TLS variant, then we can define new cipher suites which use a stream cipher distinct from RC4. There are some good candidates for the job, in particular the eSTREAM portfolio: these algorithms did get a fair share of analysis, and "seem strong". There is no known detectable bias in them, contrary to RC4. They also happen to be substantially faster.
Standard TLS now defines cipher suites with GCM. GCM is a block cipher mode of operation which builds on a block cipher with 128-bit blocks (usually AES); the block cipher is used in CTR mode, which actually turns it into a stream cipher. So we can say that using GCM-based cipher suites really is replacing RC4 with another "stream cipher".

Note that SSL/TLS ensures not only confidentiality but also integrity; thus, there must be a MAC somewhere. When using RC4 for the stream cipher, the MAC is HMAC with a hash function (MD5 or SHA-1). If you replace RC4 with a super-fast stream cipher which does only encryption, then the HMAC may become the bottleneck. GCM uses the block cipher for both encryption and the MAC, so a fast block cipher actually speeds up the whole thing. On modern x86 processors, there is hardware support for AES which includes an opcode specially suited for GCM. On smaller architectures, where performance issues are actually much more probable to matter, GCM is not necessarily a good choice ("fast" implementations of the binary field multiplication in GCM use big tables which are not that fast on CPU with a small L1 cache).


Elliptic curve point multiplication — who is wrong?

The (very useful!) computer algebra system sage says the correct result is indeed $(6,14)$:

sage: E = EllipticCurve(Zmod(17), [2, 2])
sage: E
Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Ring of integers modulo 17
sage: P = E(5, 1)
sage: 891 * P
(6 : 14 : 1)

Those "online calculators" you used appear to be broken.


Yes, it is possible. There are a number of different solutions.

One depends on a large random-looking, easily computable permutation $(\pi,\pi^{-1})$ on strings of $Nl$ bits. The master key is the $n$-bit string $\mathit{mk}$, the $i$th key share $k_i$ is an $l$-bit string, there are $N$ key shares and $0^{Nl-n}$ is a string of $Nl-n$ zeros. The concatenation of strings $x$ and $y$ is denoted by $x||y$. Then derive the key shares from the master key using $$k_1 || k_2 || \dots || k_N = \pi(\mathit{mk} || 0^{Nl-n}).$$
To recover the master key from the key shares, compute
$$\mathit{mk} || 0^{Nl-n} = \pi^{-1}(k_1 || k_2 || \dots || k_N).$$

This is secure for a random permutation, so it should also be secure for a random-looking permutation.

You can build a sufficiently large random-looking permutation using a Feistel construction, Luby-Rackoff and a random oracle.

If you want to be able to recover the master key from a subset of the key shares, you need to go to secret sharing. It should be possible to do this, but it is trickier and you don't get information theoretical security. Which probably isn't a problem. (The above permutation-solution doesn't get information theoretical security, either.)


How should I treat a new cipher release like Spritz?

Nobody can tell you not to "have fun with it" but I would strongly recommend you to first study attacks on other ciphers. Spritz (Rivest & Schuldt) fortunately mentions a lot of research on its predecessor, RC4. This makes it a rather good starting point in my opinion.

It is necessary to understand the linguistics and mathematical constructs that are used. Jumping into crypto-analysis without a good understanding of the concepts will not get you any reasonable results.

If your main competence is to create a fast/secure implementation of cipher algorithms, then go for it. In the worst scenario an attack is found or the algorithm never receives wide popularity.

I don't see the big difference between 1) and 3) outside your own state of mind. Again, nobody can tell you not to be exited :)


What is scale-invariance notion of a fully homomorphic encryption scheme?

While @j.p. is correct that the scale-invariant scheme encodes the plaintext a bit differently than in other FHE schemes, this is mostly just a syntactic point that doesn't really get to the heart of scale invariance.  (Indeed, it is easy to switch between the two encodings of the plaintext, simply by multiplying the ciphertext by an appropriate scalar.  See Appendix A of this paper for details.)

The key property of scale-invariant schemes is that homomorphic multiplication increases the error "rate" (relative to the ciphertext modulus $q$) by a fixed factor, independent of the magnitude of the errors in the ciphertexts.  For example, it doesn't matter whether the ciphertexts have error $\approx 10^2$ for modulus $q=10^6$, or error $\approx 10^5$ for modulus $q=10^9$ (for the same error rate of $10^{-4}$): the error rate in their homomorphic product will be, say, $10^{-2}$.  (I'm using artificially small numbers here for the sake of illustration.)

By contrast, homomorphic multiplication in non-scale-invariant schemes is very sensitive to the magnitude of the errors, because the errors are essentially multiplied.  So in the first case above we would end up with error $\approx 10^4$ for modulus $q=10^6$ (which is fine), but in the second case we would get error $\approx 10^{10}$ for modulus $q=10^9$, which would yield garbage upon decryption.

Non-scale-invariant schemes use modulus reduction to convert the second case into something more like the first, to make the ciphertext safe for multiplication.  Scale-invariant schemes don't need to do this (though it's still useful as an optimization, because decreasing precision leads to faster operations).  More significantly, scale-invariant schemes can be based on a parameterization of LWE that is classically (not just quantumly) as hard as worst-case lattice problems, where we need to use a huge $q \approx 2^n$ and a (still huge, but relatively much smaller) error $\approx q \cdot n^{-d}$, where $d=O(\log n)$ (for example) is the multiplicative depth we want the scheme to be able to handle.


PRFs / hash functions with a parameter amount of 'hot' bits?

I will answer the question for PRFs, I don't know whether it's possible to securely hash into the respective set.
So, what is it we are actually trying to achieve here? We want to create a family of pseudorandom functions with the co-domain of all bit-strings of a certain length $\ell$ of Hamming weight $w$. I.e., the set
$$Y_{\ell,w}=\bigl\{y\in \{0,1\} \mid \mathsf{hw}(x) = w\bigr\}.$$
I will actually answer a more general question.
Theorem.
Let $Y$ be a set and let $\mathcal{S}$ be an efficient (i.e. PPT) algorithm that samples uniformly from $Y$. We denote by $y := \mathcal{S}(r)$ the output of $\mathcal{S}$ when sampling with random coins $r$. There exists a family of pseudorandom functions with co-domain $Y$, if a regular family of pseudorandom functions (i.e. with co-domain $\{0,1\}^n$ exists.
Proof. Let $p$ be a polynomial that bounds the runtime of $\mathcal{S}$.
Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^{p(n)}$ be a family of PRFs.¹
We construct a family of PRFs $G \{0,1\}^n \times \{0,1\}^n \to Y$ as $G(x) := \mathcal{S}(F(x))$.
We can show that $G$ is a PRF using a trivial reduction to the security of $F$. Let $A$ be an arbitrary PPT distinguisher for $G$. We construct a distinguisher $B$ for $F$ as follows.
Upon input the security parameter $1^n$ and given access to an oracle, $B$ invokes $A(1^n)$. Whenever $A$ queries its oracle with input $x$, $B$ forwards $x$ to its own oracle, receiving $y$ as a response and returns $\mathcal{S}(y)$ to $A$.
Eventually $A$ will outputs bit $b$, which $B$ will also output.
If $B$ has access to an oracle implementing a truly random function $f$, then its responses to $A$ are by definition of $\mathcal{S}$ uniformly distributed and thus, $B$ is perfectly simulating a random function $g : \{0,1\}^n \to Y$ in this case. If, on the other hand, $B$ has access to an oracle implementing $F(k,\cdot)$, then it's perfectly simulating $G(k,\cdot)$.
Thus, $B$ distinguishes $F$ from a random function with the same advantage as $A$ distinguishes $G$ from a random function. Since $F$ is a PRF, the advantage of $A$ must thus be negligible and $G$ is therefore also a PRF. $\tag*{$\square$}$
What remains to show, is that $Y_{\ell,w}$ can be uniformly sampled in strict polynomial time. Sadly, this is not the case.² The straightforward way of sampling uniformly from $Y_{\ell,w}$, is to sample $w$ unique indices $i_1,\dots,i_w \in \{0,\dots,\ell-1\}$ and returning the bitstring representing $$\sum_{j=1}^w 2^{i_j}$$ in big-endian.
The issue with this strategy is that it involves successively sampling uniform integers between $0$ and $\ell-j$ for $j = 1,\dots,w+1$. That's however not possible in strict polynomial time using binary random coins, unless $\ell-j$ is a power of $2$. We can however do two things:

We can sample uniformly in expected polynomial time using rejection sampling. However, this means our reduction above now no longer runs in strict polynomial time, so we would need to deal with that, which gets ugly very quickly.
We can sample arbitrarily close to uniform in strict polynomial time. This works by sampling an integer $I$ between $0$ and $2^a \gg \ell$ and setting $i=I \bmod \ell$. In this case, even in the uniform case, $\mathsf{S}$ does not sample uniformly. However, it samples statistically arbitrarily close to uniform, which allows the above proof to still go through.

¹ Note that PRFs with co-domain $\{0,1\}^n$ and $\{0,1\}^{p(n)}$ are existentially equivalent for any polynomial $p$.
² I have no proof for this right now, but I would be very surpised if there exists some strategy to do this.


New to cryptology, studying key exchange

Key stretching usually means using a Password-Based Key Derivation Function (PBKDF), these are designed to be more resource intense than standard hashing, which is designed to be as fast as possible. A salt is used to prevent that two derived keys are differentely so that you'd need to brute-force each password independentely.
Usually you derive a key from a master secret if you negotiated a key beforehand and need a key for a cipher or a MAC. Key-Derivation-Functions are usually hash-functions with some slight modifications. A real world sample would be TLS, where you derive a key after negotiating a master secret using either DHE or ECDHE. TLS v1.2, see Chapter 5
There's no difference between PFS and FS other than naming. Wikipedia


Weak one way functions from strong one way functions

No, $g$ is certainly not even weakly one-way. In particular, in order to invert $g$ you just need to be able to sample a $y$ such that the first bit of $f(y)$ equals the first bit of $f(x)$. Now, since one-way functions work on random input, it is clearly not hard to sample an input with the same first input bit as $f(x)$, since $x$ was randomly chosen.


Is it possible to obtain AES-128 key from a known ciphertext-plaintext pair?

As far as is publicly known, no, you can't.

If you could, that would constitute a practical known-plaintext key recovery attack on AES, and the existence of such an attack would mean that AES would be considered totally insecure by modern cryptographic standards.

If you do figure out how to do that, publish it and you'll be famous.
(Or, if you'd prefer money over fame, take it to your local/favorite intelligence agency or organized crime syndicate.  But note that this option carries some significant risk, since whoever you sold that information to would now have a considerable interest in preventing you from selling it to anyone else).

One exception to this is the case where the keyspace is (or you suspect it may be) sufficiently small to allow a brute force exhaustive search of it.  That could e.g. be the case if the key is derived from a passphrase that may not have been chosen securely (that is, at random from a sufficiently large pool of combinations).  In that case — especially if no delibrately slow key derivation function was used to strengthen the key — you could just write some code (or build some hardware) to try all likely passphrases until you find one that gives the correct encryption.


Secure Multiparty Computation with Secret Output

Yes, all of them support this.

Garbled Circuits
I'll focus on the 2-party case when it comes to garbled circuit based schemes. In these schemes, you typically have one party that garbles the circuit and their own inputs. The second party executes the garbled circuit. To input their values into the computation, an oblivious transfer protocol is often used.

So, say the party that should receive the output is the one executing the circuit. If the party who constructed the circuit, constructs it so that the output "wires" are plaintext, then the executing party gets the answer. Now they simply just don't send the output to the first party and the output remains private to them.

On the other hand, if the party that should receive the output is the one who garbles the circuit, they can simply mask the output wires with a random value. Then the party doing the circuit execution cannot know the outputs. That party sends the output values to the first party, who can unmask them.

Secret Sharing
The other type of MPC we typically see is secret sharing based. In this variant, each party secret shares their inputs with the other parties in the computation. They then compute on the secret shares. At the end, they have shares of the output values. If everyone is suppose to know the output, the parties simply broadcast their shares of the output to all other parties. If only some parties are suppose to know the output, each party can instead send their shares of the output to those authorized to know the output. As long as the thresholds of non-corrupt parties are met, a corrupt party who is not suppose to learn the output cannot.


Security implications of the key padding in HMAC

Ordinarily, the keys for a MAC algorithm are assumed to have a fixed length.  (If they don't, e.g. if the "keys" are actually user-supplied passwords, then you should run them through a suitable KDF anyway.)  When HMAC is used that way, there is no problem, since the padding process cannot map two keys to the same output.

(If the input keys are longer than the hash input block length, HMAC specifies that they are to be hashed before padding.  In this case, two keys can end up getting hashed to the same value, but actually finding two such equivalent keys is as difficult as finding a collision for the hash function.  The hashing step does reduce the effective keyspace size of HMAC to the hash output length; that's only an issue insofar as it makes a brute force key recovery attack as easy as a single brute force MAC forgery.  But for normal applications of HMAC, the latter is already considered a break, and thus the hash output size should be chosen to make it infeasible.)

That said, precisely because of its flexibility and its strong security properties (PRF-ness), HMAC is not only used as a generic MAC, but also for other purposes such as, notably, as a component of password-based KDFs like PBKDF2.  In such uses, the key padding (and hashing) in HMAC could cause issues if one isn't careful:

For keys longer than the hash input block size, $k$ and $H(k)$ are equivalent HMAC keys.  This could be an issue e.g. in a carelessly designed application that used $H(k)$ as a key check value, and thereby revealed it to attackers.
Conceivably, a lazy application designer could be tempted to take advantage of HMAC's flexible key length and derive auxiliary keys from a master key simply by appending various suffixes to it.  In such a case, using two suffixes of different length (including, possibly, the empty suffix) that only differed by the longer one having one or more null bytes appended to it could potentially yield equivalent subkeys.
Similarly, when HMAC is used for password hashing (e.g. as part of PBKDF2), two passwords that only differ by appended null bytes would be equivalent.  Of course, people rarely use (or even allow) null bytes in passwords, and anyone who does is likely to run into bigger problems anyway (like the fact that many systems may store user input as a null-terminated string, effectively truncating it at the first null byte).  And even if someone did somehow end up using such an equivalent null-padded password, the security implications would be essentially the same as if they'd simply reused the original password.

In practice, all of these issues are easily avoidable simply by being aware of them and not doing silly things like using null bytes in passwords or in subkey suffixes.  The real problem with HMAC's key padding scheme is simply that it presents a subtle trap for careless cryptographers, and requires anyone analyzing HMAC-based schemes to be aware of its internal structure.  It would be nicer and simpler if we could just treat HMAC as an ideal black-box PRF, but alas, due to the possibility of equivalent keys, that's not quite the case.


The PKCS#11 standard has transitioned from RSA to the OASIS group:
https://www.oasis-open.org/committees/tc_home.php?wg_abbrev=pkcs11

I am not sure why RSA/EMC's site doesn't mention this.

I believe that v2.30 was close to finalization, but was never formally released.  I am not sure what happened but v2.40 is now the current release candidate.

v2.20 is the current revision and header files are accessible by following the link that Mr. Stone provided.

CryptSoft (Tim Hudson is a PKCS#11 leader) has a very good resource page:
http://www.cryptsoft.com/pkcs11doc/


Is there a way to inercept encrypted https connections by mimicking a cert authority?

Yes, this works, but the trick is that you'd need a certificate and private key signed by a certificate authority that authenticates the specific location you are browsing to. This certificate has to be part of a certificate chain that leads to a CA certificate that has to be trusted by your browser. The video makes you believe that a CA has to say "yes" which is incorrect.

So lets go to real life scenarios. Basically there are two possiblities:

You somehow have a trusted certificate in your browser that authenticates your connection. This could for instance happen if you're browsing through a company proxy that also proxies the HTTPS connections. These proxies exist; they basically look at the content of the connection and then send it through the HTTPS connection to the server. The proxy then acts as a HTTPS client. In general the IT dept makes sure you've got a company or proxy specific certificate in your browser store. The connection would fail if you'd use a stock browser.
A trusted CA is compromised and gives out bad certificates, either deliberately or unintentionally. A good example would be the DigiNotar debacle here in the Netherlands, where DigiNotar signed an end certificate for google.com, among others.

In both cases an unaware user would be tricked into accepting the connection, even though the underlying certificate chain would differ from the original one. Closer inspection could however show that different certificates are being used then the original one.


MIGJAoGBAKv4...................3VpXAgMBAAE=
30818902818100 ABF8... ...DD5A57 0203010001
        7                             5

Overhead & public exponent are 7 + 5 = 12 bytes. You have a 1024 bit modulus = 128 bytes.
So a correct encoding would be 12 + 128 = 140 bytes, requiring ceil(140 / 3) = 47 * 4 = 188 base 64 characters.

You however seem to have 182 characters, so there are 6 characters missing in action. These characters are part of the modulus (because they cannot be anywhere else, you clearly have the head and tail of the public key). That means you have to find 6 * 6 bits that can have basically any value, for a total of 36 bits or 2^36 = ~69 billion possible values. The 6 bit values may be at any location as well. That would multiply the number of options with over 8 billion if I'm not mistaken or 33 bits. Unfortunately 69 bits is out of range for brute force efforts.

The best thing you can do is guess that you are missing very specific bytes.
Prime suspects are + and / signs, but it would be a long shot inserting 6 of these characters at every possible place, testing the modulus using whatever valid public key operation you are able to perform.

But in general, this is not an operation that is likely to succeed.


Statistical Analysis of Cryptographic Hashing Algorithms

You simply create a hashed counter.  So output = SHA-256(n) whilst incrementing n. You'd make n a large multi-byte variable, say 16 bytes, and seed it at a random value from some PRNG you find lying around. That way you can perform repeat runs to generate different sequences. I find that you need >10MB for some of the template tests to complete fully.

I won't bother repeating  Natanael's comment to you :-)


Need some understanding on RSA public key exponent

The exponent and the totient of the modulus should be coprime. (i.e. $\gcd(\varphi(p\cdot q),e)=1$) The easiest way to reduce the chances of them sharing factors is to make the exponent prime. There is a tiny chance that the totient of the modulus will have the exponent as a factor, making them not coprime, but it's a simple check for $\varphi(p\cdot q)\equiv 0\pmod e$ (should be false). I'm not fully keen on the details as to why exactly, but I believe it's due to biases that are present if the exponent and the totient share factors.

Though this is easy to get around, as the exponent doesn't need to be unique to each key. It's common practice to simply use a fixed value of 65537 and perform the check mentioned above.


Can multiple hashing weaken the password?

Do I really weaken the password?

To some degree, yes.

The function is considered public, and the attacker can test random passwords with it and check the output and compare it to your key. Then he finds the correct password, even if he actually just guessed one of those permutations you defined. In your example:

Actual password is carphagen
The key is: key is $Key = Key1 + Key2 + . . . + KeyN$
The attacker tries the password ncarphage, which is the passwords permutation to generate $Key2$.
The attacker gets as output: $Key2+\dots$.
He still can easily detect that the partial key is the same as in the given output, even if it's not at the same location.

One more thing to consider: Your idea takes $N$ times the computation time of a single BCrypt call. But an attacker can actually check one password with a single call to BCrypt (if he's not interested in checking the permutated passwords). And that's quite bad - testing a password for the attacker surely should not be less than regular usage.

Here's an alternative idea:

Use BCrypt to generate $k_0$ from your password - with enough iterations that it fits your requirements.
Use a different key derivation function to generate values $k_1,k_2,k_3,\dots$, by using $k_0$ and a counter as input. If the function utilizes iterations, just use one.
If you want to increase the computation time, increase the number of iterations to generate $k_0$, don't apply them to the computation of $k_1,k_2,\dots$ .

For the second step, there are various possibilities for a KDF. For example you could use a keyed hash function (also called MAC), a CSPRNG seeded with $k_0$, a PRF, ...

A second alternative: Use another password-based KDF, which supports variable length output. BCrypt is quite old and there are more recent alternatives, two examples would be Argon2 or scrypt.


Yes, the nonce will be used with a counter appended in order to generate the CTR mode keystream.

It will also be used as an input to GHASH: which is a polynomial MAC used to authenticate the data.

The nonce itself does not have to be random, it can be a counter. But it absolutely must be unique for each message encrypted with the same key. Using GCM on two different messages with the same key and nonce basically allows an attacker to decrypt both messages and forge further messages. (There are some limitations, but they aren't significant enough for it not to be devastating to the cryptosystem.)

So you can either have each side keep track of a counter as the nonce, or you can send it in the clear before each message; so long as it's unique.

For an example in a real-world protocol, see the GCM spec for TLS 1.2: https://tools.ietf.org/html/rfc5288#section-3. It concatenates a value from the handshake and a counter to form the nonce.


How is LUKS dm-crypt secure if the key is stored with the encrypted data?

The key is not stored with the encrypted data, the encrypted key is. This is part of the header. In short, when the volume is created a random key (the master key) is generated and this random key is encrypted using a key derived from the passphrase, and spread out (using an algorithm called 'afsplit'). This key derivation is designed to take a relatively long time (half a second or so), so it's relatively expensive to try passphrases as an attacker.
By design the system's security depends on the passphrase's quality; a bad passphrase is somewhat protected due to the long time per try, but would fail in the end. The header also contains an independent check to see that the passphrase that was entered has resulted in the correct master key.

The header is not secret but essential to open the volume: it contains all the parameters that have been used when the volume was created, so that (with a correct passphrase) the master key can be recomputed from the header (and this key is used to decrypt the actual file system data). So it's always stored with the data. It is recommended to backup the header (to a separate system, say a USB drive), but this is just to prevent data loss when the header would get corrupted (if a bit is changed, you cannot recompute the correct master key any more).


Can I use PGP key for RSA /AES encrpyption

My client provided PGP public key for data encryption. Can I use any OpenSSL [RSA or AES or any encryption] APIs to encrypt the data with this key?

That depends. If the key is an RSA key or - to use the more modern method - contains an RSA encryption subkey, then you should be able to do this.

OpenPGP certainly allows hybrid encryption that uses AES.

  What are the different types of keys available for asymmetric key encryptions?

You can use either the old ElGamal or you can use RSA with PKCS#1 v1.5 padding. Note that sometimes ElGamal is sometimes (incorrectly) also referred to as DH as it uses the same underlying Discrete Logarithm problem (DLP).

There is also an old proposed internet standard RFC-6637: Elliptic Curve Cryptography (ECC) in OpenPGP that indicates how you can use ECIES to derive session keys rather than to wrap / unwrap them.

  Is it possible to convert keys from one format to another?

No. Calculating the public key requires the private key - the public key must be part of a key pair after all. So it is not possible to derive a public key using a public key that uses a different algorithm.

But PGP does allow the holder of the private key to define subkeys. These subkeys could be using any algorithm. Those subkeys need to be signed by the main private key. The sender can then choose any of the valid subkeys to encrypt. Of course this does require you to retrieve an updated "certificate" (PGP container with the public key) containing the public keys.

Beware that OpenPGP may be vulnerable to padding oracle attacks on several levels. You'd better make sure that you do not automate decryption procedures.


SHA-1 collision for strings of two symbols

No, that's actually pretty easy to compute, because you only have to compute all possible hashes of possible two strings, which would be $n^2$, where $n$ is the number of possible characters / symbols.

Edit:

As fgrieu correctly explained in the comment: Because of the birthday attack we would expect a natural collision between two SHA-1 hashes to occur at $\approx 2^{80}$ hashes.

And $2^{80}$ is a lot larger than $1,111,998^2$.

2nd Edit:

There are a lot of different sources for the exact amount of Unicode characters / symbols there could be (see comments below), but most of them are around $1'100'000$ and are either way far too small to reach $2^{80}$.


Sweet32: Can a single 8 byte block session ID be exploited by this vulnerability?

What I understand from the sweet32 papers, ciphers relying on a single block without any CBC or something will be safe right?

Yes Sweet32 applies to ciphers with block sizes of 64 bits in CBC mode. The idea is to collect enough ciphertext to find a collision (which due to the birthday problem will be around $2^{32}$ blocks), in other word two ciphertext blocks that are equal.

We can write these blocks as $E_k(C_{i-1} \oplus P_i), E_k(C_{j-1} \oplus P_j)$, as in CBC mode we encrypt the XOR of the plaintext block and the previous ciphertext block. We note that since the blocks are equal it must hold that $C_{i-1} \oplus P_i = C_{j-1} \oplus P_j$. We know what the ciphertext is so if we write the equality as $C_{i-1} \oplus C_{j-1} = P_i \oplus P_j$ we know the lefthand side and recovering the plaintext blocks becomes equivalent to solving a two time pad.

Note that beside only working on 64 bit ciphers in CBC mode, this attack also requires a huge amount of data. I think in the paper the researchers observed hundreds of gigabytes of ciphertext before finding a collision. Given the amount of data needed (I doubt you have hundreds of GBs of session IDs), and the fact that you are not using CBC mode you are not at risk.


How does `d-KCA` help secure the zcash protocol?

Two points:

Bob does not know $P$ which is partly the point of the protocol.
Alice could respond with the $\alpha$-pair $(a',b') = (\beta g, \alpha\beta g)$, there is nothing wrong with that. This implies that her coefficients are $c_0=\beta, c_i=0$ for $i>1$.

However, this will only do her any good if her coefficients $(c_0, \cdots, c_d)$ actually present a solution to the QAP.


Pre-determined points in Shamir's secret

Based on your question, it is not entirely clear exactly how the $x_i$ and $y_i$ values are coupled.

As I understand it, you want to make a situation where when someone has all $x_i$, they can recover all $y_i$. A simple way to do this would be to encrypt all the $y_i$ with a strong symmetric algorithm, e.g. AES-256-GCM, using a key $k$ and make the encrypted blob public. Then use Shamir's with the $x_i$ to protect the key $k$. Then, when all $x_i$ are assembled, the key $k$ can be recovered and the encrypted blob decrypted, rendering the $y_i$ values.

This may or may not be what you actually want, depending on your use case.


How can a message encrypted with the public key be decrypted with the private key?

Perhaps a simplified example or two might help you intuitively understand the concept.

Let's say you want to let your little brother and sister encrypt messages so that either of them can encrypt any message, but only you can decrypt them.  To keep things simple, let's say that the messages are simply numbers from $1$ to $10$.

Your siblings have been recently learning about addition in school, so you come up with a simple encryption scheme based on that.  Specifically, you tell your brother and sister to encrypt their messages like this:

add $7$ to the number to be encrypted, and
take only the last digit of the result.

Your brother and sister do know about subtraction, and they're smart enough to realize that they could try to decrypt a message by just subtracting $7$ from it.  But when they try it, they realize that it only works when the encrypted message is $8$ or $9$ — otherwise, they're not quite sure what to do, since they haven't had negative numbers at school yet (and zero as a number is still kind of an advanced concept for them, too).

You, of course, know how to decrypt the messages, even without using any negative numbers at all!  You just add $3$ to the encrypted message, and again take only the last digit (or $10$, if the last digit is $0$!).  This works because $3+7 = 10$, and adding $10$ to a number leaves its last digit unchanged.

Eventually, your brother and sister work this out on their own, so you have to come up with a better encryption scheme.  Fortunately, by this time your siblings have learned how to multiply numbers, so you base your new scheme on that.  Specifically, you tell them to:

multiply the number to be encrypted by $7$,
if the result is bigger than $10$, subtract the first digit from the second, and
if the result is now negative, add $11$.

(Steps 2 and 3 are, of course, equivalent to reducing the result modulo $11$, but explaining it like that would be a little too advanced for your little siblings — they've only just started learning about division!)

Again, your siblings quickly come up with the idea of trying to divide the encrypted numbers by $7$, but this works even worse than subtraction did with the first scheme — sure, they can calculate $7 \div 7 = 1$, but none of the other numbers between $1$ and $10$ are divisible by $7$.  You, of course, know the trick for decrypting the messages — you just multiply them by $8$, and then repeat steps 2 and 3 above (i.e. reduce the result modulo $11$).

This trick works because $8 \times 7 = 56 = 5 \times 11 + 1$.  Thus, for any number $x$, $8 \times 7 \times x$ equals $5 \times 11 \times x + 1 \times x$; and when you take the remainder modulo $11$, you're just left with the original number $x$!  In other words, $8 \times 7 \equiv 1 \pmod{11}$, so $8$ is the modular multiplicative inverse of $7$ modulo $11$.

This new scheme is a lot harder for your siblings to break, because their grade school math curriculum doesn't really cover modular arithmetic.  Eventually, they do come up with a brute force solution — they just write down every number from $1$ to $10$ and its encrypted result, and use this table to look up which number each encrypted message corresponds to:

$$\begin{array}{lrrrrrrrrrr}
\text{Plaintext:} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\text{Encrypted:} & 7 & 3 & 10 & 6 & 2 & 9 & 5 & 1 & 8 & 4 \\
\end{array}$$

But you just change your scheme to work on two-digit numbers instead, using $101$ as the modulus.  It's a bit more work for you, since you now have to multiply by $29$ to decrypt, but at least your siblings are too lazy to compile a 100-element table.  As long as they choose their messages to be large enough (so that multiplying by $7$ gives a result over $100$) and don't repeat a message whose encryption the other one already knows, this means they can't easily decrypt each other's encrypted messages.

You even briefly think about increasing the modulus to $1{,}001$, but realize that you'd have to choose a different public multiplier, since $1{,}001 = 7 \times 11 \times 13$, and so $7$ is not invertible modulo $1{,}001$.  You kind of like the number $7$, but in this case, $6$ or $8$ would work better.  Or you could just skip all the way to $10{,}001$, which has no small factors.

The multiplicative encryption scheme works great (at least with a large enough modulus to resist brute force tabulation), until your sister one day stumbles across a web page about the extended Euclidean algorithm.  Being clever, she realizes that she can use it to quickly calculate the modular inverse for any public multiplier, and thus read any encrypted message, no matter what the public multiplier or the modulus is!

Suddenly, you need to come up with something even more secure.  The obvious next step would be to replace the multiplication with exponentation, something like this:

raise the number to be encrypted to the $e$-th power, and
take the remainder of the result modulo $n$.

You're hoping that, if you choose the right exponent $e$ and modulus $n$, you might be able to find another exponent $d$ such that raising the encrypted number to the $d$-th power modulo $n$ would just happen to "cancel out" the $e$-th power, leaving you with the original number.  In other words, you'd need a modulus $n$ and two exponents $e$ and $d$, such that $(x^e)^d \equiv x \pmod n$ for all numbers $x$.

It's not exactly obvious that such pairs of exponents should exist, but you're feeling optimistic — after all, it worked for addition and multiplication, so why not exponentiation too?  In fact, you remember a number theory class you took in college mentioned something about modular multiplicative groups that might've been relevant.

Looking through your notes, you realize that, since $(x^e)^d = x^{e \times d}$, you really just need to find a number $\lambda$ such that $x^{\lambda+1} \equiv x \pmod n$ for all $x$; then adding or subtracting multiples of $\lambda$ from the exponent won't change the result, and so you can simply use the same extended Euclidean algorithm you used to generate the private keys for the previous encryption scheme (and which your sister used to break it!) to find $e$ and $d$ such that $e \times d \equiv 1 \pmod \lambda$.

You can even choose $e$ freely (as long as it doesn't share a factor with $\lambda$!) to make the calculations easier for your siblings.  For example, letting $e = 3$ might be a good choice.  Of course, the resulting secret exponent $d$ probably won't be so convenient, but that's all right — you know an efficient algorithm for exponentiation modulo $n$.

Your notes even mention that the smallest such $\lambda$, for a given modulus $n$, is given by Carmichael's reduced totient function.  (Euler's totient function $\phi$, which is always a multiple of $\lambda$, could of course be used, too.)

But there's a problem!  On one hand, you need to know $\lambda$ to calculate $e$ and $d$ — but if anyone else (like your too-clever-by-half sister) could figure it out, they could break the encryption!  So you somehow need to choose the modulus $n$ so that you can easily calculate $\lambda(n)$, but nobody else can.

Obviously, choosing a prime modulus like $101$ would be right out (never mind that your siblings have had programming classes at school by now, and could easily write a program to calculate a 100-element lookup table), since $\lambda(n) = n-1$ for prime $n$.  But what if you took two random primes $p$ and $q$, and multiplied them together?  Then $\lambda(p \times q)$ would just be the least common multiple of $p-1$ and $q-1$, which is easy to calculate.  But you're pretty sure that, given just $n = p \times q$, even your sister won't find it easy to break $n$ back into its prime factors, and so won't be able to calculate $\lambda$.

And that's basically where we are today with RSA.

As long as we choose the prime factors $p$ and $q$ of the modulus $n$ to be large enough (and they do need to be quite large, at least several hundred digits long, to resist the most advanced factoring algorithms and the most powerful computers) and make sure that our messages don't repeat and aren't too small (to resists brute force attacks and simple attempts to take the $e$-th root; this is generally achieved by padding the messages appropriately), there's no known efficient way to calculate $x$ from $x^e \bmod n$.

That is, unless you happen to know the secret number $d$, chosen so that $e \times d \equiv 1 \pmod \lambda$, in which case you can just raise the encrypted message to the $d$-th power modulo $n$, and obtain $(x^e)^d = x^{e \times d} = x^{k\lambda+1} \equiv x \pmod n$.


Why use a 1-2 Oblivious Transfer instead of a 1 out of n Oblivious Transfer?

Oblivious transfer is mostly studied as a theoretic construction, as it is an important component in achieving interesting protocols (like secure two-party computation and secure function evaluation).

The interest in 1-2 OT is that it is a minimal definition theoretically, and most results that limit themselves to 1-2 are designed to improve some basic properties (number of rounds) or advanced security properties (full simulatability, plain model, UC-secure, etc), as opposed to being designed for real-life implementations. Although some proposals claim to be "efficient", that typically means they are efficient for the level of security they realize, and this level is usually much higher than something you would need for implementation.

A second reason for the interest in 1-2 OT is that OT is often used to securely evaluate boolean circuits. In this particular application, the circuit in constructed from binary gates have only two outputs: so 1-2 OT suffices. However if gates were replaced with more complicated truth tables or if transfers were batched together, 1-N OT might be of interest.

OT is a primitive that rarely finds its way into an implemented/deployed tool. The only application I know of is two-party computation tools based on Yao's garbled circuits, for which some implementations exist. One example is FairPlay and it its original paper, there is some interesting discussion on the overall efficiency of switching between different types of OT. It does however leave implementing 1-N OT for future work.

A MPC tool was also used to run a Danish beets auction however it did not employ OT. Many two-party or multi-party computations try to avoid using the general construction based on OT since it is very inefficient, the OTs themselves are usually the most expensive part, and typically the jump from two-party to multi-party computation means using a different blueprint based on secret sharing instead of OT.


Is ElGamal still unforgeable if the adversary knows r?

It seems that you mix things up.

ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function.

Given the type of forgery in your question that works, you compute your $m$ as $m=es \bmod p-1$ and have no full control over the choice of $m$. Note that you would have to find $M$ such that $m=H(M)$ for your forgery to be valid, which means that you need a preimage $M$ of $m$ under $H$ which is not feasible if $H$ is secure. This is because the verification algorithm will get $M$ and signature $(r,s)$ and will check if $$y^r r^s\equiv g^{H(M)} \pmod p $$ holds.

You could modify the computation to $m=H(M)\|r$ and to adapt the verification algorithm to check if $y^r r^s\equiv g^{H(M)\|r} \pmod p $, but I do not see any immediate reason why you should do so. AFAIK hashing the message prevents any existential forgeries of ElGamal signatures as long as $H$ is secure.


Is AES reducible to an NP-complete problem?

There are some complexity-theoretic reasons to believe that cryptography can't be based on NP-completeness. For one example, see this paper by Akavia et al. Basically it all boils down to the mismatch between average-case hardness required for cryptography, and worst-case hardness required for NP-hardness. Moreover, many (most? all?) hard algebraic problems which serve as the basis for cryptography are in NP $\cap$ co-NP (for one such example, consider factoring). Such problems cannot be NP-complete unless NP = co-NP. You can see more discussion in this stackoverflow thread.

Finally, AES is a finite-domain function. It is invertible / distinguishable from a random permutation in (large but) constant time. The definitions of P, NP, etc., refer to asymptotic behavior -- that is, as the input size grows to infinity. Because of the algebraic structure of AES, it is probably possible to define a "generalized AES" for infinitely many key lengths (though there are many semi-arbitrary choices to be made). We could then ask about the asymptotic behavior of such a generalized AES. I'm not sure if anyone has done so.


How comparable is OFB to a one-time pad?

As @CodesInChaos said, OFB is a stream cipher.  The one-time pad is a stream cipher, too.  One difference is that the one-time pad is information-theoretically secure, while OFB is computationally secure.


You just want to pick a leader so that only the leader knows? Do you need it to.be at random? By votes?
If you only want to pick a leader at random. Each party picks a large random number and a random index of a party.  Using multi party computation we output the random number matching the modular sum of the indices.
Whoever recognizes his number is the leader. The others just get another random number not their own.


Would a non-envelop, prefix only, SHA2 built MAC be susceptible to key recovery attacks?

None of these constructions will lead to key recovery unless the underlying hash function is spectacularly broken in the sense of preimage resistance, which pretty much none of them are (archived).

But key recovery is not usually what's directly relevant to your application.  If you're using one of these constructions as a MAC, for example, what's relevant to your application is forgery—and while key recovery is one path to forgery, it's not the only path to forgery.  In MAC applications, length extension is fatal: it is trivial to forge MACs under $m \mapsto \operatorname{SHA256}(k \mathbin\| m)$.

These days, it's all an academic concern, because:

the world has settled on using HMAC to get a PRF out of SHA-256 so it's ubiquitous and ready at hand essentially everywhere,
there are much cheaper MACs like GHASH and Poly1305 built into authenticated ciphers like AES-GCM and crypto_secretbox_xsalsa20, and
SHA-3 and BLAKE2 natively provide keyed variants anyway with PRF security so you don't need to construct your own—and making the prefix construction secure was an explicit design criterion for the SHA-3 competition if you really still want to use it.


Error during transmission with one plaintext block (Cipher block operation)

First, Let us write the encryptions as an equation;

\begin{align}
c_1 & = \text{IV} \oplus \operatorname{Enc}(k,p_1) \\
c_2 & = P_1 \oplus \operatorname{Dec}(k,p_2)\\
\end{align}
and the last

\begin{align}
c_3 & = p_{n-1} \oplus \operatorname{Dec}(k,p_3) \\
c_4 & = P_n \oplus \operatorname{Dec}(k,p_4)
\end{align}

As one can see the chaining(?) is constructed(?) within two by two blocks. However, there are more serious problems than the original question.

The decryption of $p_2$; $$p_2 = \operatorname{Dec}(p_1 \oplus c_2)$$ If one look at the encryption of $p_2$ they will see that $\operatorname{Dec}$ is used. Therefore, unless the block cipher is a very sepcial cipher that $\operatorname{Enc}=\operatorname{Dec}$ than this is not possible to get $p_2$. Thas is the blockcipher chooses an involution for every key, see OEIS A000085.
This is similar to the first; This time always $\operatorname{Dec}$ is used. So we don't expect even decryption.

Now back to corrected one, that is for encryption $\operatorname{Enc}$ is used and for decryption $\operatorname{dec}$. Then, as stated above, the blocks are operated two by two and this means that an error can only affect at most two blocks. $c_1$ affects two blocks and $c_2$ affects one block, etc. It is also not clear how the odd number of blocks are encrypted. One can guess that there is a special padding mechanism.


How is SSL secure from rogue Certificate Authorities?

SSL offers protection against Man-in-the-Middle only if the client can make sure that what it believes to be the server's public key is, indeed, the true server's public key. X.509 certificates aim at providing this information, but this is relative that no rogue CA was involved. A "rogue CA" is here one of:

An evil or gullible root CA ("subverted" CA might be a more neutral term).
An evil or gullible intermediate CA, whose own certificate was issued by another CA (going up to a trusted root).

In fact, rogue CA are out of scope of X.509. It is a strange assertion, but its meaning is that X.509 works on damage containment:

If a mishap occurs, revocation is used to limit damage in time.
Though nothing technically prevents a rogue CA from issuing a fake certificate, it leaves traces; namely, the fake certificate points at the rogue CA for being, indeed, rogue. Fear of retaliation is supposed to keep CA honest and robust.

Even though a basic OS or Web browser tends to trust a hundred root CA or so by default, and that this trust is limited by the weakest of all of them, it so happens that "mishaps" involving a subverted CA are rare, about once a year or so. This means that the system kind of works in practice. Your understanding of the problem is correct, but experience shows that the mitigations which are in place (retaliation from legal/police forces, and revocation and OS/browser patches) make the attack "not worth it" for the attacker (it won't work for long, and it is risky), which explains why such attacks remain infrequent. I daresay that X.509 is not the weakest link in SSL-powered Web site (and SSL is not the weakest link either; the Web site is the usual problem).


Identity Based Encryption: Known Random Value

Thanks. I guess $K=g^s$. It seems trivial if Carol knows the random integer $r$ then she can learn the message. As you mentioned everybody could compute $T_{id}$ because both $Q_{id}$ and $K$ are public amongst the network. Since Carol knows $r$ then she can compute $Z=T_{id}^r$ and hash of this result!
To learn the message, she has to calculate,

  $$m=v \oplus H(Z)=m \oplus H(T_{id}^r) \oplus H(T_{id}^r)=m \oplus (H(T_{id}^r)\oplus H(T_{id}^r))=m \oplus 0=m$$

In general, Carol does not need to know the master secret key $s$ to read the message. The Encryption phase is randomized by the integer $r$ and for a Chosen Ciphertext Carol can learn the message. While we know she can not compromise the forward and backward secrecy of the scheme because the Discrete Logarithm is hard and the random integer for next ciphertext will be sampled, independently.


Number of keystreams generated in Kreyvium for a single key/IV pair

Trivium is designed as an 80-bit key and 80-bit $\operatorname{IV}$. Noted in Algorithms, key size and parameters report 2014. Technical report, ENISA - European Union Agency
for Network and Information Security, 2014. increasing the key size was not an easy task.

Kreyvium is defined in Stream ciphers: A Practical Solution for Efficient
Homomorphic-Ciphertext Compression by Canteaut et al. as 128-bit IV and 128-bit key variant of Trivium. Actually they consider a solution to this problem.

  In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob’s public key pk and to send the ciphertext $c = \operatorname{HE}_{pk}(m)$ to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting $c$ as efficiently as possible from Alice to Charlie.

They gave the maximum length as

  Our first aim is to offer a variant of Trivium with 128-bit key and $\operatorname{IV}$, without increasing the multiplicative depth of the corresponding circuit. Besides a higher security level, another advantage of this variant is that the number of possible $\operatorname{IVs}$, and then the maximal length of data which can be encrypted under the same key, increases from $2^{80}N_{trivium}(d)$ to $2^{128}N_{kreyvium}(d)$.

Bolds are mine

What is the Kreyvium

A picture can tell a thousand words. From the article;

They added the 256-bit IV and key bits into 288-bit internal state. Full defitinion can be found on the 8th page of the article.


If there exists an IND-CPA symmetric encryption scheme (where the key is shorter than the total length of the messages, i.e., the scheme is not the OTP), then there are one-way functions. A sequence of articles have shown how to construct pseudorandom generators out of OWFs (culminating with this paper). By the GGM construction, pseudorandom generators can be used to construct PRFs. Therefore, IND-CPA symmetric encryption implies PRFs.


DES hardware implementation of substitution lookup table [ ReWorked ]

A simple way to think of the S-boxes of DES when it comes to a hardware implementation is: 8 independent ROM ICs, each with 6 address input lines and 4 data out lines. In an educational physical implementation with retro standard ICs, two such ROMs fit a 4 kiB EPROM (a 2732). Some actual software implementations of DES do group S-boxes two by two in order to reduce the number of table lookups.

Another way is: 8 times, 4 independent boolean functions of the same 6 input bits; for a total of 32 independent boolean functions of 6 input bits out of 48 input bits (which themselves come from the key, with a wiring dependent on the round and if we are enciphering or deciphering). It is well known how to build any boolean function of 6 input bits (e.g. using Karnaugh maps), hence in principle build these 32 boolean functions. However Karnaugh maps do not yield efficient/compact circuits in the case of DES S-boxes.

There is little exploitable regularity in the DES S-box functions. The most striking one is that each line of numbers of the spec of the S-box values (FIPS 46-3 appendix 1) is a permutation of $\{0\dots15\}$.
It follows that we can model each of the 32 boolean functions by: 4 functions of 4 input bits (coding columns on that spec) set for precisely 8 out of 16 combination of these 4 inputs, followed by selection of the appropriate of the 4 results of these 4 functions according to 2 other input bits (coding line in the S-box).
This translates into a trivial systematic construction of the functions using NAND gates with at most 8 inputs, of depth 3 (including input inverters) plus the final 1-out-of-4 multiplexer stage.
Using this structure, it is very easy to fit two S-boxes in a generic PAL with 12 inputs plus internal feedback and 10 outputs, at least 8 of which having at least 8 input terms. The once-popular PALCE22V10 is ample.

The problem of minimizing the complexity of these 32 functions, including considering that they are evaluated together and some work can be shared among the 4 functions belonging to the same S-box, has been extensively studied; for example by Matthew Kwan: Reducing the Gate Count of Bitslice DES, 2000, eprint 2000/051; however he is focusing on 2-input gates and considers XOR of unity cost, which is fine for software, but hardware has different constraints.


Monoalphabetic cipher using different languages in the same plaintext

I don't think that this will make cracking the code that much harder. You could not use statistical "most popular letter" anymore, but I don't think that in English or Italian there are that many words that are exactly five letters and letters 3 and 4 are identical like in "gatto". We could also check what four and three letter words that share the same final two letters sometimes appear next to each other like in "know how".

And what if someone knows that the message is about a cat? He just has to check for that word in two languages, and he will get three (or in this case four) bits of the key.


What exactly does $0...0$ and $1...1$ mean usually?

This simply means a (more or less) long string of $0$s or $1$s or more clearly $000000...000000$ and $111111...111111$.

Related notiational notes, you may have to use soon:

Sometimes the notation $0^n$ and $1^n$ is also used for these strings with exactly $n$ zeroes and ones.

Even more generally it's usually expected that people see the pattern, namely that nothing changes (or else there would be a note about this), for example $\lambda_0,...,\lambda_n$ is expected to be filled with $\lambda_i$ with $i\in \mathbb N_0, 0\leq i\leq n$ or relatedly $(\alpha,...,\alpha)\in \mathbb R^n, \alpha \in \mathbb R$ would be the same principle, that you'd have to fill the blanks with as many $\alpha$s as needed.

One last note: If you'd want to indicate that you want a leading string $0$ and a trailing string $0$ and stuff you don't care about in the middle you'd usually notate it as $n\in\{0,1\}^*$ and $0||n||0$ which means "place an arbitrary string of arbitrary length between the zeroes".


No, you should not use a password directly as an HMAC key.

However, it is fine to use HMAC as part of a key derivation function, which generates keys from a password. However, do not mistake the output as naturally having higher entropy than whatever you put in. "password" has essentially 0-bits of entropy, and running it through a KDF will not magically give it 256 more.

Using PKDF2 with HMAC-SHA256 as its PRF to generate a key from a password which will then be used as an HMAC key for other purposes is completely fine. The iteration must be high enough, which at this point in time is around a quarter of a million, which takes about 0.1s on a moderately fast computer.


Are there security issues with discrete logarithm keys not being uniformly distributed?

The discrete logarithm problem can be attacked with either a specific or a generic algorithm. A specific algorithm is one that tries to exploit structural weaknesses of the specific group in which discrete logarithm is used; e.g. Index Calculus when we are talking about exponentiation modulo a big prime. Generic algorithms only use the group law and thus work on "any" group. For normal elliptic curves (excluding those which allow for an efficient pairing), no specific algorithm is known.

For a group with $N$ elements, where the private key is chosen uniformly, the best generic algorithms work with cost $O(\sqrt{N})$; so with a 160-bit group you have security $2^{80}$. If the private key is not chosen uniformly, then the generic algorithm can be adjusted to take that into account: ultimately, this is equivalent to reducing $N$. In your examples, the "equivalent" $N$ is no smaller than $q/2$, so you reduce your security by no more than a $\sqrt{2}$ factor: not really worth worrying.

However, in (EC)DSA signature generation, a new value (called $k$ in FIPS 186-3) must be generated modulo $q$ for each signature; it is sometimes called a "transient private key". Contrary to the private key $x$, the value $k$ MUST be generated uniformly. For instance, if $k$ is chosen by selecting a sequence of random bits of length one less than the length of $q$, or if $k$ is selected by taking a sequence of random bits of the same length than $q$ and reducing it modulo $q$, then the private key $x$ can be reconstructed by observing many signatures and total cost $2^{63}$, which, while still big, is substantially lower than the expected $2^{80}$. This was found by Bleichenbacher in 2001; I am not sure it was formally published anywhere (Vaudenay talks of it as a "private communication"). The problem here is not in the discrete logarithm per se, but in how $k$ and $x$ are used in the computation of $s$ (the second half of an (EC)DSA signature).

The current FIPS 186 (FIPS 186-3) fixes that issue by generating a bit sequence at least 64 bits longer than $q$, then reducing it modulo $q$ (this makes the bias small enough to be unimportant). In X9.62-2005 (the ECDSA standard), they simply generate bit sequences of the length of $k$ and start again if this yields a value which does not lie between $1$ and $q-1$.

Either way, for a properly secure (EC)DSA signature generation, you must have a way to generate reasonably unbiased $k$ values; hence, you can use the same generator for producing the private key $x$.


Confusion regarding computing Multiplicative Inverse Modulo P?

Indeed, theoretically $$X'\equiv C^{a^{-1}}\equiv A^{x*a^{-1}}\equiv g^{x}=X\pmod p$$

should hold, given $gcd(a,p-1)=1$.

However there are two reasons why you won't get this equation to hold.

You calculated $a^{-1}$ using the wrong modulus. As it is in the exponent you need to calculate $a^{-1}\bmod q$ with $q$ being the group's order instead of $a^{-1}\bmod p$. In your example $q=p-1=10$.
The value you have for $a$ makes it impossible to invert. For $a^{-1}\bmod q$ to exist $gcd(a,q)=1$ must hold, but $gcd(6,10)=2\neq1$ so there's no $a^{-1}\bmod q$ for your specific choices of $a$ and $q$.


TL;DR: It allows the parameters to be backdoored and the solution is a simple primality test.

  What exactly is a composite group [and why does it matter]?

First, we need to get a quick understanding of the Diffie-Hellman Key-Exchange. Diffie-Hellman (DH) works on a mathematical construct named group, which is a set and an operation which adhere to some basic requirements. You can call any set with an operation that adheres to these requirements "group". Now the idea of DH is that you have two parties pick positive integers $x,y$ and let them compute and exchange $X=g^x,Y=g^y$ for some agreed-upon group element $g$. In practice this means that $g$ is an integer such that $1<g<n$ for some $n$, which we call modulus and the actual operation is $X=g^x\bmod n$ (same for $y$), using modular arithmetic which basically means "if you get beyond $n$, subtract $n$ from the number until it's smaller than $n$ again". Now it can be shown that multiplication with modular reduction ("applying the $\bmod$ operation") and the set of all integers $<n$ form a group, which we typically call $\mathbb Z_n^*$. What this is about is the case where $n$ is composite, ie not prime.

  "So why is a composite group bad?"

Well, it turns out that the security of DH relies on the fact that given $X,g,n$, you can't recover $x$ from $X=g^x \bmod n$. Now when we apply some special precautions to the structure of $n$ and the choice of $g$ this is actually assumed to be secure for sufficiently large parameter choices. However, when $n$ is large and composite and you now the factors of $n$ (and they're sufficiently small) you can in fact recover $x$. "Good, then I have a solid key-backup system now", you may think, but in fact such backdoored parameters have already been exploited in other cases, where an attacker replaced these parameters with their own, so they could eavesdrop on communication.

  "OK, so how does this work then?"

There's a mathematical trick, called the Chinese Remainder Theorem (CRT) which allows you to split your instance of $\mathbb Z_n^*$ into several smaller groups like $\mathbb Z_p^*,\mathbb Z_q^*$. Now if you can do an operation in all these groups you can transfer the result back into the larger group with minimal effort. So let's just for the fun of it suppose we wanted to do this. We'd pick an $n=a\cdot b\cdot c\cdot d$ where $a,b,c,d$ are 512-bit long each and $n$ is 2048-bit long. Factoring $n$ or taking the discrete logarithm in $n$ would take on the order of $2^{112}$ operations using the best known algorithm (the GNFS), but computing the discrete logarithm in $\mathbb Z_a^*$ (and the other three groups) takes a week of pre-computations for each group, followed by a few seconds to minutes per group and discrete logarithm (PDF), which is definitely feasible.

  How would I test if given parameter set describes a composite group?

In theory it's simple: You run a standard primality test against the parameters you receive and deny the connection if a composite modulus is used and accept the connection if the modulus is prime. The cost of this however is several times more expensive than not bothering and just accepting the parameters...

  [T]he modulus is a prime in this case

In this case we need a bit of background on group theory. Especially the fact that there are $\varphi(p)=p-1$ elements in $\mathbb Z_p^*$ and the fact that each subgroup has $q$ elements where $q$ divides $\varphi(p)=p-1$. This means that you have at least one subgroup with two elements (because primes $> 2$ are odd and $p-1$ is thus even) and one with $(p-1)/2$ elements. Ideally you want this number to be a prime (and thus $p$ being a safe prime) to avoid the Pohlig-Hellman attack. If it is not a prime, then you can split the (full, "composite") group into (many) smaller groups and solve the discrete logarithm problem in all those subgroups (which can be significantly faster than in the full group) and recombine the result using the CRT again. Now if you pick $(p-1)/2$ to be composite consisting of let's say 128-bit primes it's gonna be hard for other people to find these factors, especially if you use 16 und it's easy for you to compute discrete logarithms, having only a cost of about $2^{70}$ (which should be feasible) instead of $2^{112}$. So again it allows parameters to be backdoored and can be prevent with a "simple" primality test on $(p-1)/2$


Is there any advantage on encrypting the CMAC together with the message?

If a MAC is encrypted using CTR specifically then specific bits can still be flipped by an attacker. So although the MAC isn't known, specific bits can still be altered in transit. This may allow certain attacks, depending on the error handling of the receiver of the protected messages.

[The question I cannot readily answer is if such a small authentication tag gains nothing from being encrypted. Please alter.]

A CMAC should indeed already be secure by itself. Encryption of a MAC should not be necessary.

In the protocol you are describing the CMAC is however truncated to a very low number of bits. Look at this snippet from RFC 4493, section 2.4:

  It is possible to truncate the MAC.  According to [NIST-CMAC], at
     least a 64-bit MAC should be used as protection against guessing
     attacks.  The result of truncation should be taken in most
     significant bits first order.

No, it's not a "typical approach" in the sense that newer protocols usually calculate an authentication tag over the ciphertext instead of the plaintext.

There are however protocols where MAC-then-encrypt is used, notably Transport Layer Security (TLS). This actually opens up TLS to some attacks such as the Lucky Thirteen attack, although that attack also requires CBC mode encryption instead of CTR mode encryption.


Password Hashing Security Using Scrypt & Argon2

This home-made construction is pointless and unnecessarily complex, Complexity is often the source of vulnerabilities. In this case, for example, I’ll wager you’re not securely handling the intermediate variables as you chain the multiple password hashes together.

Simply use argon2 only and increase the work factors. “Double scrypt” is fairly meaningless as scrypt also has work factor parameters which can simply be increased.


How much stronger is RC4 if it is keyed with an RSA private key?

RC4 has several known weaknesses, including:

Rather strong biases in the initial parts of its keystream
Weaker biases in the rest of the keystream.

Now, RC4 does take a variable length key, potentially up to 2048 bits (256 bytes).  So, if you wanted, you could take a 2048 bit RSA modulus, and use that as the RC4 key.  However, doing so would not affect most of the known biases; these occur independent of the key size.  What RC4 does internally is effectively take the key it is given, and repeat it until it has something 256 bytes long (and uses that to stir the initial permutation).  Most of the biases do not occur because of repeats in this expanded key, and so are unaffected by a larger key.

Now, I say "most of the biases" because there is one bias in the initial keystream that would be cleared up by a larger key; a 32 byte key would cause a bias at locations 32, 64, 96 (and gradually dying out until you hit location 256); a larger key would eliminate that bias.  However, there are plenty of other biases in the initial keystream; just eliminating this one doesn't solve the problem.


Building large S-Boxes from smaller ones

Yes , there are others such as SPN (CLEFIA , Khazad Middori-128 ,etc)

in addition to xor-based Feistel  structure , the Kuznyechik is based on product-based Feistel  structure.

I suggest to read this thesis (it summaries all) : CRYPTANALYSIS, REVERSE-ENGINEERING AND DESIGN OF SYMMETRIC CRYPTOGRAPHIC ALGORITHMS


Key derivation with implicit certificates

Yes, the certificate $cert$ and the private key are linked. For $cert' \ne cert$, the private key will be different (except for a negligible collision probability).
Alice's secret $\alpha$ is known by herself only (only $\alpha G$ is sent in the first step of the protocol). This prevents a third party from deriving her private key.


What is the recommended x length in the Diffie-Hellman algorithm?

Actually, RFC3526 does have recommendations for the random number size; see section 8, and the table listing "exponent size".

Now, it gives two different recommendations (which sounds rather less useful than giving one); the summary is that if the size of the random number you pick is $x$ bits, then an attacker can recover the shared secret with no more than $2^{x/2}$ work.  If you're happy with 80 bit security, then selecting a 160 bit random $x$ is sufficient.  If you want significantly more than 80 bit security, well, you might want to rethink the 1024 bit group.


Was, as you stated, a MAC "are both generated and verified using a shared secret key", while with a digital signature, the signatures are generated with one key, and are verified with another (and it is infeasible to sign anything with the verifier key alone).

So, with digital signatures, we can give someone the ability to verify signatures, but not generate them; with a MAC, we cannot do so.

Is this difference important?  Well, that depends entirely on what we're doing, and whether we can whether someone who can verify messages can also create them.

For example, consider the case of Alice sending messages to Bob.  Bob wants to make sure those messages really come from Alice, and so they share keys; Alice signs/MACs the messages, and Bob verifies those messages.  If that's the only what that key is used, we don't mind if Bob can also use his key to generate messages, because we can trust that he won't.  After all, the only one who will ever validate a message is, in fact, Bob.  If Bob does generate his own message, well, the only one he would be able to fool with it would be himself, and there's no point to that.

For an example in the other direction, consider the example of distributed stock quotes, where (say) the New York Stock Exchange publishes the current price of stocks.  Now, people will need to be able to determine if these quotes came from NYSE, and so they need to be verifiable somehow.  If these quotes were MACed, that means that NYSE would need to distribute the MAC secret key (so people can verify quotes); that would mean that someone could generate a fake stock quote (one that says that, say the price of GM just went drastically down); because he has the MAC secret key, he can compute the correct MAC, and that would fool someone else, causing them to dump all their GM stock.  To prevent this, any such system would need to use a signature method, with the NYSE signature key being distributed.  That way, anyone could validate a stock quote, but they wouldn't be able to generate fake quotes of their own.

Now, the next obvious question is "if a digital signature can do everything a MAC can do, why would we ever use a MAC"?  Well, the answer is that while a digital signature could be used where we currently use a MAC, it is also much more expensive; a MAC is much (several orders of magnitude) cheaper to compute and verify, and is also somewhat shorter.  No one uses a digital signature when a considerably cheaper MAC would do the job.


Would this authentication on a Diffie-Hellmann-key-exchanged channel work?

In the question as it stands now, nothing prevents Eve to relay Do you have a cat? to Bob, get the answer A = Yes by testing A for Yes or No against hash(e_bob+A) obtained from Bob, then send hash(e_alice+A) to Alice and defeat the protocol.

In a now-gone comment, it was added that we

  should use "strong values" for A; only Q is sent, plain A is never sent.

Notice that then, in order for Alice to perform a check, A must be known to Alice in advance. If this "strong value" (or even the convention to use it the way described) is known to Alice and Bob, but not Eve, then the technique works.

If only the "strong value" is unknown to Eve, it acts as a secret key in an ad-hoc protocol (for something academic we'd want to use this "strong value" as key to HMAC of message e)

If the convention is unknown to Eve, that's not cryptography in the modern sense of Kerckhoffs's second principle; and that's brittle, and can't be generalized.


Encrypting the relationship between two database tables

Provided that any user, who is supposed to have access to any relationship, may be granted access to all relationships, one solution would be to use a SQL engine that supports table level access control through table encryption, and encrypt the Join Table. In such case a decently implemented symmetric encryption scheme would be sufficient.

An attacker who gains physical access to the database files, will need the key for the Join table to be able to extract information from it. Conversely, if the attacker gains guest access to the database through the SQL interface, privilege elevation would be required to gain Join Table access.

However, such solutions are not sufficient e.g. in scenarios where any client is supposed to be able to run a query for his or her own lawyers, or conversely, where some lawyers are not allowed to run queries for any clients but their own. In such case, a trivial solution would be to encrypt each record separately, using a symmetric encryption scheme under a randomly generated content encryption key that, in turn, is encrypted using e.g. RSA-OAEP and the public RSA key of each user that is supposed to have access to the record, with the RSA cipher texts being stored in a fourth table. Such schemes would require the join process to be implemented to run locally (since the process would need access to the RSA private key).

Another alternative altogether would be to use Predicate Encryption, but such schemes are arguably very far from "common"-


Source for examples with broken cryptography

If you want to look back in time, ENIGMA was the standard used by the nazis in the 30-40's. It would be useless to encrypt anything with it now.

More recently, pratical attacks have been done against parts of the GSM standard (what cell-phones use). The cipher A5/2 which is considered completely broken and has for this reason been remove from the standard. Actually, A5/3, supposed to be better, is not looking great either right now as an attack requiring a regular computer has been done recently (2010, see wikipedia link).

These are example of practical attacks against "real life" algorithms.

You also have algorithms which never made it outside academia because of their weakness. For instance, MacGuffin was broken at the same conference it was presented!

At last, "broken" is a rather vague concept. An algorithm is usually considered "broken" if attacks much more efficient than brute-force can be done... But that does not mean they are pratical! For instance, PUFFIN (a lightweight cipher) is considered broken due to vulneranility against differential cryptanalysis. However, the amount of data required to perform the attack remains unpractically high.

For this reason, you may consider DES to not be broken because no attack is more efficient than brute-force in its case (as far as I know). However, the problem is that a brute-force attack is possible nowadays because the key size (56 bits) is too small.


A fast non-cryptographic hash function that is "strong enough"?

So what you need is a fast cryptgraphically secure hash function?
There are some.
If you're in hardware Keccak might be an option as it uses many bit-permutations.

If you're in software there are Skein and Blake2b/s/bp/sp. Skein was the fastest hash-function of the SHA-3 competition and Blake2 is the successor to BLAKE, the second fastest hash-function in the SHA-3 competition.

You might find this page helpful.