From 2-round key-exchange protocol to a public-key encryption scheme CPA-secure

The methods suggested in the comments are useful in practice, but they base on some specific key exchange protocols. It's useful to proove that a public key encryption scheme can be created from any such $KE^{eav}$-secure protocol.

Notation

Let $\langle s_A, m_A \rangle, \langle s_B, m_B \rangle$ denote the state and transmitted message from Alice and Bob within the protocol respectively.
Let $Prot_A(1^n) \rightarrow \langle s_A, m_A \rangle$ denote the process of Alice creating her secret state and the message to be transmitted to bob, $Prot_B(m_A) \rightarrow \langle s_B, m_B \rangle$ be the process of Bob sampling his random state and creating the message based on the random state and Alice's message. We then define the key to be $f(s_A, m_B) = k_A = k = k_B = f(s_B, m_A)$ for $f$ some predefined function.

Construction

Now, we create a public-key encryption scheme as follows:

\begin{align*}
    Gen&(1^n)  \\
    & \langle s_A, m_A \rangle \leftarrow Prot_A(1^n) \\
    & \langle s_k, p_k \rangle = \langle s_A, m_A \rangle \\
    & Output \space \langle s_k, p_k \rangle \\
    %
    %
    Enc_{p_k}&(m): \\
    & \langle s_b, m_b \rangle \leftarrow Prot_B(p_k) \\
    & Output \space \langle m_B, f(s_B, p_k) \oplus m \rangle \\
    %
    %
    Dec_{s_k}&(c): \\
    & \langle m_B, c' \rangle = c \\
    & k = f(s_k, m_B) \\
    & Output \space k \oplus c'
\end{align*}

Correctness

Since $f(s_k, m_B) = f(s_A, m_B) = f(s_B, m_A) = f(s_B, p_k)$ the correctness follows from the correctness of a one-time-pad.

Security

We can proceed to prove CPA-security by reduction. Assume there is an adversary $\mathcal{A'}$ which succeeds at breaking the CPA experiment for our public-key encryption scheme $\Pi'$. We construct an adversary $\mathcal{A}$ breaking the KE experiment as follows:

$\mathcal{A}$ receives $m_A, m_B, \hat{k}$ as input
$\mathcal{A}$ runs $\mathcal{A'}(1^n, m_A)$ and receives $m_0, m_1$
$\mathcal{A}$ samples $b \leftarrow \{0,1\}$ uniformly and computes $c = \langle m_B, m_b \oplus \hat{k} \rangle$
$\mathcal{A}$ runs $\mathcal{A}'(c)$ and receives $b'$
$\mathcal{A}$ outputs 0 iff $b = b'$

Now we have 2 cases to consider -- when $\mathcal{A}$ received the true key ($[K=\hat{k}]$) and when it received a uniformly random string ($K \neq \hat{k}]$). But in the first case, the result of the KE experiment will be 1 exactly when $\mathcal{A}'$ succeeds in the CPA experiment. In the other scenario, since $\mathcal{A}$ samples b uniformly, the result of the experiment will be 1 when $b = b'$ with probability $\frac{1}{2}$. Hence:

$Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1] = \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K = \hat{k}] + \frac{1}{2}Pr[KE^{eav}_{\mathcal{A}, \Pi}(1^n) = 1 | K \neq \hat{k}] =
\frac{1}{2}(Pr[Pubk^{CPA}_{\mathcal{A}', \Pi'}(1^n) = 1] + \frac{1}{2}) =
\frac{1}{2}(\frac{1}{2} + \frac{1}{p(n)} + \frac{1}{2}) = \frac{1}{2} + \frac{1}{2p(n)}$

This contradicts $\Pi$ being $KE^{eav}$-secure, hence $\mathcal{A}'$ cannot exist and $\Pi'$ is CPA-secure.


What should I use for consequent AES key derivation?

Yes, generally you can use a hash as a "poor man's KDF". For instance, look at the Q/A about KDF1 and KDF2 which are little more than glorified hash functions. Of course, as e-sushi noted, the theoretical requirements of a KDF is a little bit higher than those required of a hash.

Some differences:

A KDF doesn't have just one input; besides the Input Keying Material it may also have inputs such as Info containing e.g. a label for the key, a salt and the length of output material to generate;
The inputs of the KDF should be canonically encoded or there may be restrictions on the input parameter so that different input combinations will never generate the same output;
The output of many KDF's is configurable and may extend the output size of the underlying hash function or block cipher (depending if the KDF supports expansion);
The output of the KDF is generally well defined, usually if you want to take 128 bits from a 256 bit hash you take the leftmost bits, but a KDF will have formalized what output should be taken (and yes, I've seen weird / stupid ones);
The output of the KDF should be full randomized, which is theoretically not a requirement for hash functions.

Now e.g. SHA-256 or SHA-512 will have output that is indistinguishable from random, so the last point is mostly theoretical in nature. All the other differences can be ignored or implemented in your own hash function. So yes, it is possible to define your own KDF.

However, I'd suggest you use KDF1 so you'd at least be compliant to an existing KDF where all these design choices are already made. KDF1 is very basic and doens't seem to offer canonical encoding, so you  may want to make sure that OtherInfo has a static size. In the end, you'd still be left with a single call to a hash. A HMAC based KDF such as HKDF would be considered more secure, of course, as there are few primitives that match a PRF such as HMAC with regards to resilience.


You seem to be inventing your own ad-hoc protocol, without authenticated encryption, and using old algorithms with known security weaknesses such as small block size.

I strongly suggest you use a high level modern library such as libsodium and use its crypto_box function for authenticated encryption, as well as Argon for password key derivation to protect the private keys. This will supply fast modern authenticated encryption (which your proposed solution would not provide). There are libsodium "wrappers" for most popular high-level programming languages.

It is much more difficult to go wrong using a known-good, high-level toolbox such as libsodium. With out using something more pre-built, you will have to decide on many security-critical details which are easy to get wrong such as: symmetric modes, authentication mechanisms for your cipher text, padding, key generation, nonce generation and re-use protection, key-wrapping, padding, side-channel resistance, and encoding.

You will still have to compose a few high-level building blocks for your application with something like libsodium, but it won't be nearly as difficult or error-prone.


Does lagrange interpolation work with points in an elliptic curve?

This is "half an answer" while I think about the other half :)

EDIT: other half added below.

The mathematical model that I find most useful for all discrete logarithm based cryptography is that of a vector space over a finite field. In many ways, the multiplicative-group implementation and the elliptic curve implementation are isomorphic, although it can be confusing because it's natural to write the former multiplicatively and the latter additively.

For example, the multiplicative-group setup usually has you pick two primes $p, q$ with $q$ dividing $(p-1)/2$, and the embedding function $x \mapsto g^x \mod p$ where $g$ is an element of multiplicative order $q$ modulo $p$ (e.g. $g^q \equiv 1$ modulo $p$).

In the elliptic curve setup, you have a base point $P$ of order $q$, there is no small-$p$ and the embedding function is $x \mapsto x \times P$.

The important mathematical structure here is that the target of the embedding function is a vector space (of dimension 1) over $\mathbb F_p$ and in this model, the embedding function is linear. That lets you work out a lot of things.

I know of several projects that have done various secret-sharing stuff in the multiplicative-group setting, a lot of them concerned with electronic voting, and all of this should port almost 1:1 to the elliptic curve setting. In fact I wish people would do this. You can indeed generate a (Shamir) secret-shared secret key among some authorities, everyone publishes their local public key and then one computes the global election public key as a linear combination (which is what Lagrange is doing) $Y = \sum_i c_i \times Y_i$ where the $Y_i$ are the local public keys.

In principle you could define a product $\otimes$ on the target space (e.g. the curve) via $(x \times P) \otimes (y \times P) := (xy \mod q) \times P$ since the embedding function is bijective. This makes the target space into a ring and should have most of the properties that you need to do things with polynomials there, answering SO's question (I think). The practical problem here is that actually computing this product is equivalent to solving CDH. This should not be a problem in two cases though: (1) in a security proof where you just want to reason about things, (2) in a secret-sharing scheme where the parties who want to compute this product hold the necessary preimages in the finite field.

EDIT

It should all still work fine. For example:

Over a finite field you can $(k, n)$ share a secret $s$ by setting $a_0 = s$, picking $a_1 ... a_{k-1}$ at random and creating the shares $s_i = \sum_{t=0}^{k-1} a_t i^t$. To recover from $k$ shares $(i, s_i)_{t=1}^k$ you compute $ \sum_{t=1}^k \lambda_t s_t$ where the $\lambda_t$ are the Lagrange coefficients.

If your secret $S$ is in the curve, and if you can pick random curve points $A_1 ... A_{k-1}$ then you can create shares by $S_i = \sum_{t=0}^{k-1} [i^t] A_t$ where $[t]A$ denotes scalar multiplication for a scalar t and curve point $A$.
The recovery formula is $S = \sum_{t=1}^k [\lambda_t] S_t$. The reason this works is that both the $i^t$ and the $\lambda_t$ are scalars so you're never multiplying curve points.

(You can create a random curve point by picking a random scalar $r$ and computing $[r]P$. Creating a random curve point where you don't know the dlog is harder, but unnecessary here.)

What's going on under the hood here is that, since every curve point has exactly one discrete logarithm, we can define $s$ such that $S = [s]P$ and $a_1 ... a_{k-1}$ such that $A_t = [a_t]P$ where $P$ is the base point. Using linearity, the way we create the shares is thus $S_i = \sum_{t=0}^{k-1} [i^t a_t] P$ so if we choose $s_i$ such that $S_i = [s_i]P$ then for recovery we get $\sum_{t=1}^k [\lambda_t s_t]P = [\sum_{t=1}^k \lambda_t s_t] P$. But the coefficient in the brackets here is exactly the recovery formula for secret sharing over a finite field, so we recover $[s]P = S$ as expected.

(This is incidentally also an example of how you can happily reason about taking discrete logs in security proofs.)


Can we map SHA-256 output bits to fixed-length input bits?

No this is not possible.

Basically SHA-2 consists of many rounds where the input is confused using irreversible functions. Each time such an irreversible function is called another variable is introduced. Furthermore these functions are not operating on a single input/output bit (of course) - they are dependent on all the input bits due to the inherent transposition.

So the reverse function will consist of many many variables, that cannot be simplified to a function without one. Any SAT solver will happily break its teeth on it. And that's why you cannot just create a generalized mapping function.

For attacks usually a reduced number of rounds are used, trying to expand them to the full hash later. And if your input $N$ is small enough then you could simply use brute force or an attack using a rainbow table... but that's about it.


What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

a key pair generator, which produces a pseudo-random key pair;
a signature generator, which uses the private key to produce a signature over some piece of data;
a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might want to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.


How do we prove that AES, DES etc. are secure?

We don't prove schemes like AES and DES secure. Instead, cryptanalysts try very hard to find attacks against the scheme. If, after much effort, no attack is found, we may with some justification consider the scheme secure.

The statement that a scheme is secure usually takes the form "any adversary that breaks the scheme with this much advantage must use at least this much time". For symmetric cryptography, this is often equivalent to saying that exhaustive key search is the best attack. Note that "breaking the scheme" is a technical notion, and the precise definition is often complicated.

Sometimes, schemes can be proved secure against certain classes of attacks. I think AES has been proved secure against certain forms of differential and linear cryptanalysis. This does not prove that no other attacks exist, of course.

Sometimes, schemes can be proved secure under the assumption that a smaller scheme is secure in some sense. E.g. the Merkle-Damgård construction shows that hash functions can be constructed from compression functions.

Sometimes, we can prove that a scheme is secure under number-theoretic or complexity-theoretic assumptions. Unfortunately, these schemes are often very slow compared to schemes like AES. It is also not a priori clear why a "natural mathematical problem" must be harder than the "man-made problems" posed by schemes like AES.

In idealized models, there are many provably secure schemes (typically indifferentiability proofs) that are both interesting and valuable, but these do not describe the real world, so the results must be interpreted and used with care.


AES-128 (2000) has been around for 20 years and there is no attack faster than brute-force, except the multi-target that affects all block ciphers and hash algorithms. As you can see, an algorithm can withstand attacks for a long time with a good design.
SHA-1 (1995) has 160-bit output, which results in 80-bit generic collision resistance. It was good for the 1990s.  The NIST removed it from signatures in 2013. Today, this is already low, by today's standards where it is considered that we need at least 112-bit security. The chosen prefix-collision attack on SHA-1 (2017) is faster than the generic collision attack; it is faster 100,000s ($\approx 2^{16}$) of times. Maybe in the future, one can present faster collision findings like MD5's imminent collision findings, we don't know.
Now, SHA-256 (2001) has 128-bit generic collision resistance with a 50% probability under the birthday attack. The 128-bit is not easily accessible. The public example is the Bitcoin Miners that they can collectively reach $2^{92}$ double SHA-256 hashes per-year (it is almost $2^{93}$ after two years). Therefore they need $2^{36}$-year to find a collision with 50% probability.
SHA-512 (2001), on the other hand, has 256-bit generic collision resistance. 256 bit is not vulnerable.
SHA-3-512 has the same generic collision resistance as the SHA-512. The main differences are these; the SHA-3  series uses sponge construction and has resistance to length-extension attack whereas the SHA-2 series uses MD construction and if not trimmed, they have no length-extension resistance.
There is also a quantum attack side of the story like the work of Brassard et. al dropped collision finding into the $\mathcal{O}(2^{n/3})$-time and requiring $\mathcal{O}(2^{n/3})$ storage in the total cost of $\mathcal{O}(2^{2n/3})$. This and other quantum attacks are theoretical and should not be considered a real threat. Actually, they are not better than classical algorithms like the parallel $\rho$ based collision search algorithm of Van Oorschot and Wiener based has $\mathcal{O}(2^{n/2})$. See in details in this answer

So, like 10 years after the original publication, the hash algorithm already wasn't deemed secure enough anymore to be trusted.

NIST and the designers of the SHA series (except SHA3) has come from a long way to design a better hash algorithm from the MD5 and earlier MD hashes, SHA-0, & SHA-1. We don't compare something by saying that if $x$ was broken in $y$ years then since $z$ is $y$ years old it must no longer be secure. We compare according to published attacks. SHA-256 has been there for almost 20 years withstanding the classical attacks. Yet no problem seems on the horizon. If you want to be secure for the foreseeable future use SHA-512, besides it has 64-bit CPU support ( SHA-256 has 32-bit CPU support).

SHA-2 was published in 2001, given the advancements in computing power, does it even make sense to use SHA-2 in new technology? Isn't it reasonable to expect that very soon it won't be trustworthy anymore, seeing how SHA-1 wasn't trustworthy anymore 10 years after inception? Shouldn't we use SHA-3-512 wherever possible to be on the safe side looking forward?

The computing power has limits. We have already seen that reaching $2^{100}$ is not easy, and $2^{128}$ has a long time to be secure for direct brute-force.
If there are no new attacks that are going to be performed and much better than the SHA-1's attacks on SHA-2, then there is no problem for the SHA-2 family. However, we always assume that the attacks always become better, not worse.
Conclusion:
Normally SHA-256 is fine with 32-bit CPUs; 128-bit is classically impossible to break. To take the advantage of 64-bit CPUs use SHA-512. Similarly, you can use SHAKE128/256 and BLAKE2 that has both 32 and 64-bit CPU designs. To take advantage of parallel hashes use  ParallelHash (parallel version for SHA-3) and BLAKE3 (parallel).

Currently, the best public attacks break preimage resistance for 52 out of 64 rounds of SHA-256 or 57 out of 80 rounds of SHA-512, and collision resistance for 46 out of 64 rounds of SHA-256.

This is the short story of the big picture

The cost for 52 out of 64 round pre-image attacks of SHA-256 is $2^{255}$
The cost for 57 out of 80 round pre-image attacks of SHA-512 is $2^{511}$

These attacks are on the reduced round of the SHA-256 and SHA-512, i.e. if the SHA-256 uses 52 rounds then the cost of finding pre-images will be $2^{255}$ instead of $2^{256}$ and even on average you will find the pre-image with brute-force with $2^{255}$-time
As we can see, the cost is already far from reachable. While reading an attack in hash functions one must look at all requirements; the complexity compared to generic attack, the memory requirements, possible reduced rounds, or the success of the attack on how many rounds.


Prove in Zero Knowledge the execution of a function

Yes, what you describe is an example of a zero-knowledge proof.

ZKP systems such as libSNARK, libSTARK, pepper-project, etc. can help the prover generate a proof that he/she knows private $a$ and $b$ such that $Y = a * b$ and then a verifier can check that the computation was done correctly without ever knowing $a$ and $b$.

What you describe is the knowledge-of-factorization example and I recently implemented that in the pepper-project here.


Export from US of crypto software with key-size > 56 bits still needs permission?

First of all, this is not legal advice. However, I've been in the unfortunate position where I've had to deal with this legal nightmare. The new agreement which regulates export of cryptography internationally is called the Wassenaar Arrangement. If your product is what is called a mass market product, i.e available for purchase to the general public without restriction, you can ignore any export restrictions. You can also skip this if your software is open source and available for free for everyone. There's more exclusions such as if your only use is in DRM , if the input to the cryptographic algorithms can no be changed.

If you restrict your sales to a select subset of customers or if your product is exclusionary in some attribute, e.g price is too high to be considered mass market, you need to contact your local government body responsible for Wassenaar compliance.

The section you would be interested in is DUAL-USE LIST - CATEGORY 5 – PART 2 – "INFORMATION SECURITY".

If you feel you might fall under this arrangement it's best to follow the following rules:

If your encryption is based on a symmetric algorithm, keep the key size at 56 bits or less. (e.g AES, DES, Blowfish...)
If your encryption is based on the difficulty of factoring integers, keep the key size at 512 bits or less. (e.g RSA)
If your encryption is based on the difficulty of computing discrete logarithms in a multiplicative group of a finite field, keep the size at 512 bits or less. (e.g Diffie Hellman over Z/pZ)
If your encryption is based on discrete logarithms in a group other mentioned previously, keep the size at 112 bits or less. (e.g Diffie-Hellman over an eliptic curve)

If you do not follow these rules you will come under control of the government body responsible for Wassenaar compliance. Which is extremely likely to become a huge bureaucratic burden on your organization as export controls are extremely poorly set up to deal with things like software where you may have many thousands of customers. It is best to avoid it unless cryptography is an integral part of your product. Most companies and individuals are unaffected by the arrangement as it tries to be narrow enough to only capture the companies which trade with foreign governments.

If your system does any sort of cryptoanalytic work it's generally considered even more sensitive and your odds of being in export controlled territory increases.


Extended Euclidean Algorithm (back substitution)

$d=7$ is correct; this can easily be verified by computing:

$$43 \times 7 \bmod 60 = 301 \bmod 60 = 1$$

So, the source of the problem lies somewhere in your "practice"; as you didn't share the details of what that was, I can't point out exactly where the problem is.


It's performed using the PRF, as indicated by the RFC specifying the TLS 1.2 specification you pointed to. The PRF is identified by the cipher suite - commonly as last part of the cipher suite string.

How the PRF works is specified by section 5 of the TLS 1.2 specification:

  In addition, a construction is required to do expansion of secrets
     into blocks of data for the purposes of key generation or validation.
     This pseudorandom function (PRF) takes as input a secret, a seed, and
     an identifying label and produces an output of arbitrary length.

And the specification then says:

 master_secret = PRF(pre_master_secret, "master secret",
                      ClientHello.random + ServerHello.random)
                      [0..47];

followed by:

key_block = PRF(SecurityParameters.master_secret,
                  "key expansion",
                  SecurityParameters.server_random +
                  SecurityParameters.client_random);

after which the output key_block is split into the session keys required.

So the entire spec relies on the PRF, which relies on the iterated P_hash, which relies on HMAC_hash which relies, finally, on a secure hash such as SHA-256. Otherwise it is just concatenation and splits of octet string (also known as byte arrays). I won't copy the algorithms here, they are well described in the TLS specification.

As it doesn't rely on any other cryptographic primitives the cipher suite string simply lists the hash function used as configuration parameter for the PRF, for instance SHA-1 in TLS_RSA_WITH_AES_128_CBC_SHA and of course SHA-256 in TLS_RSA_WITH_AES_128_CBC_SHA256, both from appendix C of the specification.

Note that the DH handling of TLS 1.2 is a bit strange in the fact that it uses the minimal size encoding of the DH result as pre_master_secret. Generally the output of DH Is considered static, and of the same size as the prime field (i.e. 1024 bit for 1024 bit DH). So you should not left-pad with zeros for TLS 1.2. This has been fixed in TLS 1.3 draft specification (to be precise after I mentioned it in the mailing list, in draft 13).

Note that the generation of keys using the PRF is generally known as (key based) key derivation. The PRF is therefore used as TLS-specific Key Based Key Derivation Function or KBKDF.


What happens if you increment MAX counter in AES-CTR?

In AES-CTR, the ‘IV’ and ‘counter’ are different concepts.  To encrypt a message, you specify a nonce, like a message sequence number—sometimes called an ‘IV’.  The nonce is usually 64 or 96 bits, but it could be anywhere from 0 to 128 bits long.  For security, you must never reuse a nonce with a key.  The length of the nonce for the particular AES-CTR system you're using determines the maximum message length: inside AES-CTR, the remainder of a 128-bit string after filling part of it with a nonce is used to count blocks within a message.

So, for example, if you send the message $m_1 \mathbin\| m_2 \mathbin\| m_3$, and then the message $m'_1 \mathbin\| m'_2$, you might in your protocol choose the nonce 42 for the first message, and the nonce 69 for the second, and the ciphertexts will be internally computed as:

\begin{align}
  c &= \bigl(m_1 \oplus \operatorname{AES}_k(42 \mathbin\| 0)) \mathbin\| (m_2 \oplus \operatorname{AES}_k(42 \mathbin\| 1) \mathbin\| (m_3 \oplus \operatorname{AES}_k(42 \mathbin\| 2)\bigr), \\
  c' &= \bigl(m'_1 \oplus \operatorname{AES}_k(69 \mathbin\| 0)) \mathbin\| (m'_2 \oplus \operatorname{AES}_k(69 \mathbin\| 1)\bigr).
\end{align}

(Here the $m_i$ and $m'_i$ are exactly 128 bits long apiece; it is inside AES-CTR that the block counter 0, 1, 2, …, is maintained.)

For (say) AES-CTR with a 96-bit nonce, the maximum message length is $2^{32}$ 128-bit blocks, or $2^{36}$ bytes.  What happens if you try to encrypt a $(2^{36} + 1)$-byte message?  It's simply not defined in that case—like dividing by zero.  You should avoid designing a protocol in which this question might even arise; what an implementation might do may vary: it could silently wrap around, effectively encrypting messages with a two-time pad; it could fail noisily and abort the computation; it could make demons fly out of your nose.

What if you use a 0-bit nonce, so that the maximum message length is $2^{128}$ 128-bit blocks, or $2^{132}$ bytes?  You don't have that many bytes and you don't have enough time to wait for all the computers in the world to encrypt that many bytes.

What if—internal block counter aside—you use a 64-bit message sequence number as a nonce?  Will you have to worry about wrapping around?  Hint: You are doing this in sequence.  Let's say it takes you a nanosecond to encrypt each message.  How many centuries do you have to wait for a 64-bit message counter to overflow?


BLAKE2: What is the difference between the salt and the personalization?

Context should be constant for one "keystore": that is the property of the KDF that is used for namespacing the salt space and make sure that two different application (or keystore) will not reuse the same salt.

Subkey_id, however, needs to be different for each key within a given key store and it is NOT to be used for namespacing. It can be constant for a given subkey ID though (even when the unhashed data changes).

The purpose if to make sure different applications can safely generate unique salt values without having to perform a full scan: all you need if for each app to have it's own context and then they can use a simple counter for subkey ID.


Get the parameters of an elliptic curve's equation

04 indicates the uncompressed form of the public key.
The first half is the $x$-coordinate and the second half is the $y$-coordinate of the public key.
x= 5e:ff:47:19:80:be:93:5f:8f:51:14:45:d5:
   40:41:79:ca:48:be:85:97:bd:e2:0f:2b:a0:
   b2:7d:6c:37:74:39:44:ff:50:67:74:30:a8:
   10:ac:89:a6:6a:80:5a:1a:c9:

y =82:ff:2a:51:84:38:c8:f6:af:e0:46:e7:9f:
   d5:66:1b:20:75:7f:87:42:46:d9:6e:12:4f:
   74:38:4d:f4:9f:b1:13:27:9a:10:a8:0c:6b:
   4b:1f:f6:6c:bf:32:ee:a3:10

The parameters you are looking for are defined in the last part.
ASN1 OID: secp384r1
NIST CURVE: P-384

The parameters can be found in FIPS PUB 186-4 or SEC 2: Recommended Elliptic Curve Domain Parameters as sextuple
$$T = (p, a, b, G, n, h)$$
p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFF

$$ p = 2^{384} − 2^{128} − 2^{96} + 2^{32} − 1$$
The curve $E: y^2 = x^3 + ax + b$ over $F_p$ is defined $b$;
a = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    FFFFFFFF FFFFFFFE FFFFFFFF 00000000 00000000 FFFFFFFC

b = B3312FA7 E23EE7E4 988E056B E3F82D19 181D9C6E FE814112
    0314088F 5013875A C656398D 8A2ED19D 2A85C8ED D3EC2AEF

The basepoint $G$ in compressed form (03) indicates
G = 03 AA87CA22 BE8B0537 8EB1C71E F320AD74 6E1D3B62 8BA79B98
       59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7

The basepoint $G$ in uncompressed form (04) indicates
G = 04 AA87CA22 BE8B0537 8EB1C71E F320AD74 6E1D3B62 8BA79B98
       59F741E0 82542A38 5502F25D BF55296C 3A545E38 72760AB7
       3617DE4A 96262C6F 5D9E98BF 9292DC29 F8F41DBD 289A147C
       E9DA3113 B5F0B8C0 0A60B1CE 1D7E819D 7A431D7C 90EA0E5F

$n$ is the order of the basepoint $G$
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF
    C7634D81 F4372DDF 581A0DB2 48B0A77A ECEC196A CCC52973

and the cofactor $h$ is:
h = 01

The cofactor is caluclated by $$h = \frac{|E(\mathbb{F_p})|}{n}$$

Printing via OpenSSL
Using OpenSSL Command-Line Elliptic Curve Operations it is possible to print the values, too
openssl ecparam -name secp384r1 -out secp384r1.pem
openssl ecparam -in secp384r1.pem -text -param_enc explicit -noout

The compression
The 0x02 or 0x03 indicates the distinction of $Y$ or $-Y$. Since in the elliptic curve $$Y^2 = X^3 + aX + b$$ if $(X,Y)$ is a point then $(X,-Y)$ is also a point on the curve. This is due to the square of $Y$ in the elliptic curve equation.
The distinction designed by the least significant bit of $Y$, 0x02 for 0, and 0x03 for 1.


Could completely public passphrase hashes ever be reliably secure?

For any value $x$ chosen randomly in a set of size $N$, and hash function $h$, publishing $h(x)$ allows for an exhaustive search on $x$ with average cost $N/2$. This is unavoidable.

The problem with passwords is that, by virtue of fitting in the brain of a human, they tend to come for a set of potential passwords of relatively small size $N$. We try to cope with that by making $h$ a slow function, and using a new variant of $h$ every time (that's what salts are about). See this answer for details on password hashing.

Now that's just an average. Though most humans will have trouble remembering many fat random passwords, a normal human can remember a really random password with enough entropy to defeat exhaustive search. This will imply some effort, so a lot of users won't do it.

Entropy is the key word. An entropy of $n$ bits means a set of passwords of size $N = 2^n$ (that's a simplification: I am assuming that all potential passwords have an equal probability of being selected). In the case of the famous comic which describes the "correct horse" method, an entropy of 44 bits is claimed. This is mathematically correct (see that answer for an analysis). However, 44 bits are not a lot, certainly not enough to defeat exhaustive search. Cryptographers have long required at least 80 bits, as a rule of thumb for "unbreakable through brute force"; and the relentless progress in technology, as well as an aesthetic appeal for powers of two, now make "128 bits" to golden rule. It can be argued that 128 bits of entropy ought to resist brute force for quite some time.

Basically, the "correct horse" password generation method assumes a list of 2048 words, and four words are selected randomly and uniformly in that list. That is, there are four successive selections of one word in the list, and the selections are independent of each other (so the same word can be selected several times). Make that twelve words instead of merely four, and your password will be rock solid, even if you publish the hash of it.

(If you use slow hashing with a salt and enough iterations, these twelve words can be reduced to, say, nine or ten words.)


PRGs exist if computationally secret encryption schemes exist

I don't know of any direct way of doing this. In particular, in contrast to the way most encryption schemes work in practice, in theory there is no requirement that the output of an encryption scheme look random at all. The only way that I know to do this is to prove that computationally secret encryption implies one-way functions (not hard to show, but not completely trivial, since it is only true when the amount being encrypted is larger than the key size). Then, using HILL, one can construct a PRG from any one-way function.


Yao's Garbled Circuit- Why does Alice need to rearrange the circuit?

Alice does not need to hard-code her input and does not need to shuffle the gates (it is only necessary to shuffle the ciphertexts inside each gate). Bob needs to hold a key on every input wire. For the input wires associated with Alice's input, she can just send the appropriate key (this reveals nothing since both the 0 and 1 values are just random).


To answer your question: it's expected, because you're using the wrong modulus.

CodesInChaos pretty much gave you the correct answer; I'll try to explain in more detail about what's actually going on.

We can define an elliptic curve based on any finite field $GF(p^k)$; in the case of P=256, we have p=FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF (in hex), and k=1.

The points on the elliptic curve are actually solutions to a specific cubic equation within the field (plus an artificial "point at infinity"); these solutions, plus a specific point addition operator +, form a finite mathematical group.

A mathematical group is set along with an operator for which certain identies always hold, such as $(A+B)+C = A+(B+C)$, for any group members $A, B, C$.

Because of these identities, we can uniquely define point multiplication $nG$ as the point $G$ added to itself $n$ times (for example, $5G$ is defined as $G+G+G+G+G$).  And, we have the property $a(bG) = b(aG) = (ab)G$, as you have observed.

Now, for any finite group, if the group has $q$ members (that is, the set that makes up the elements of the group is of size $q$), when we know that $ab \equiv c \ (\bmod\  q)$ implies that $abG = cG$, for any group member $G$.

This value $q$ is known as the order of the curve.  However, $q$ is not the value $p$ we used above; instead, for the curve P-256, it is the value q=FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551 (in hex).

That is, if you compute $c = ab \bmod q$ for that value of $q$, you'll find that $abG = cG$


It has been implemented, of course. In addition to the reference implementation, there are some crypto libraries with it like libsodium.
It has not yet seen much use in applications or protocols, because it is relatively new and security people tend to be conservative. (And two years simply is not that long.)

Stronger, at least in theory. The resistance to GPGPU does depend somewhat on parameter choices. E.g. the more memory you use, the harder time GPUs have using all their execution hardware.
The argon2d variant is meant to be even more resistant to GPU compute, at possible expense of side channel resistance in comparison to argon2i.


How does hashing twice protect against birthday attacks?

A collision in any hash function gives a collision in a "squared" variant of the hash function. This is easy to see. If hash(x)==hash(y), then hashing the outputs will also be the same.

So the wiki entry is wrong. To see the real purpose of the double hash see this question and answers.


Number of bits specified in standards implementation?

I'm not sure if you talk about generic products or your own product, but generally 1024 bits is not considered enough anymore, and 2048 is considered borderline secure. It's still used a lot, but I'd say 2048 bits is now the bare minimum.

You're not naming any standard so we don't know if it can handle larger bit sizes. If you're talking about the RSA / DSA standards themselves: sure they can handle any kind of bit size. Implementations commonly only allow bit sizes that are a multiple of 8 or 32 bits, but that's an implementation detail.

A 1024 bit key only offers up to 80 bits of security (against the best attacks) and 2048 bit keys offer about 112 bits of security (source: NIST / keylength.com. For higher strength ciphers it is often better to look at Elliptic Curve cryptography which offers higher security for smaller sized keys. Unfortunately both RSA and EC are not secure against (large scale) quantum computers.

Corporations and banks cannot solve anything in days. To name just one issue: bank cards (smart cards) often can only handle up to 2048 bit RSA. But even if they support 4096 bits then it will be impossible to update or replace all the cards in days. Performing large scale redeployment of all keys would certainly also pose issues.


Are there any other highly trusted and secure symmetric encryption algorithms besides AES?

ChaCha20

Provides 128 or 256-bit key space.
The best attack against 6 (128-bit) or 7 (256-bit) of 20 rounds
Stream cipher requires 64-bit nonce and 64-bit position counter
Used in TLS 1.3, OpenSSH, as well as BSD and Linux kernel RNGs
Part of ESTREAM portfolio

Serpent

Provides 128, 192, or 256 bit key space.
Best attack against 11 or 12 of 32 rounds
Block cipher with 128-bit block
AES competition finalist

Twofish

Provides 128, 192, or 256 bit key space.
Best attack against 6 of 16 rounds
Block cipher with 128-bit block and Feistel network design
AES competition finalist
Used in disk encryption software, OpenPGP standard, numerous applications

Deoxys-II

It provides 128 or 256-bit keyspace.
Authenticated encryption scheme with a 120-bit nonce, nonce misuse resistant
Based on 16-round tweakable block cipher using AES round function
Designed to provide better security than AES-GCM
Part of CAESAR portfolio for use case 3 (maximum security)

Camellia

Provides 128, 192, or 256-bit key space.
Block cipher with 128-bit block and Feistel network design
Patented but royalty-free
Used in OpenSSL, optional in OpenPGP and numerous other standards
Part of NESSIE and CRYPTREC portfolios

SEED

Provides 128-bit key space.
Best attack against 8 of 16 rounds
Block cipher with 128-bit block and Feistel network design
Used primarily in South Korea

CAST-256

Provides 128 to 256 bit security in 32-bit increments
Best attack against 28 of 48 rounds
Block cipher with 128-bit block and Feistel network design

There is the generic multi-target attack on n-bit key ciphers that requires less than the $2^n$ cipher evaluations.


Combatting traffic shape analysis with spurious packets

Well, this isn't a new idea.  One place (and probably not the first place) this has appeared before is in IPsec RFC4303, see dummy packets in section 2.6.

Now, IPsec differs from your suggestion in that it isn't using some output from a CSPRNG.  Instead it just grabs some arbitrary amount of data of the right length (with the marker that it is a dummy packet), and just encrypts it just like it would a real packet.  This is just as indistinguishable as a CSPRNG would be, and (at least for IPsec) it is a bit more convenient (because you can reuse the same infrastructure that does encryption, rather than having a separate CSPRNG infrastructure).

Now, the problem with this idea is that it can be hard to do, at least, if you want something that can fool an intelligent listener.  For example, suppose that you are protecting some TCP traffic.  Now, with TCP, one side sends a message (a TCP packet with data), and the other side immediately responds with a reply message (the TCP acknowledgement).  The problem that this behavior causes is that if one side just sends a dummy packet, and the other side doesn't reply, well, the attacker can pretty much figure out that the two sides aren't really communicating, and that's what we're trying to hide.  To effectively hide this, what we'd need to do is send a dummy packet, and have the other side respond with its own dummy packet (with approximately the same timing as a real TCP ack would have).  To further complicate things, TCP isn't the only protocol in use; another example might be RTP (which is mostly unidirectional); disguising that would take a different strategy.

On the other hand, if you do know enough about the protocol you're protecting to effectively mimic it, this idea can work.


Why is it difficult to encrypt large amounts of information using quantum key distribution?

I believe the end goal is to use the QKD data as a one-time pad, so the QKD rate would need to be the same as the plaintext data rate.  That is the only guaranteed-secure method.  (Although I think QKD might be a bit of a scam.)

Also, you can't use a key forever.  I recently made a 400Gbps AES-GCM encryptor.  You're not supposed to send more than 2^32 blocks with the same key, because it starts to get easy to forge tags after that.  This corresponds to ~8 hours' worth of data.


Assuming that you can indeed guarantee that the keys will never be reused, both schemes should be secure.

The only requirement for the nonce in CTR mode is that it must be unique (and, if used directly as the initial counter value, not equal to any intermediate counter value used in the past or in the future).  If you're only encrypting one message with a given key, the nonce $0$ is as unique as any other.

As you correctly note, your second scheme provides somewhat less information to an attacker who can guess some of the plaintext.  (Reading between the lines in your question, I'm assuming you're not planning to store the nonce along with the ciphertext, but to re-derive it from the master key on decryption.)  Whether it's "better" is hard to say — it only makes a difference if the cipher you're using is broken, and at that point it will depend on just how it's broken — but it's at least unlikely to be worse.


weaknesses in ElGamal with public key of small order

Well, your problem is that you choose a specific bad private key ("-1"), which only generates a group with two elements. However, this is a very specific weak case, and the chance to select the according private key is negligible.

But in general, there are a couple of problems with choosing a generator for the whole group $\mathbb{Z}_p^*$, because it is leaking some information. For example, if $\beta$ is a quadratic residue, but $c=m\cdot \beta^i$ is not a quadratic residue, then $m$ is a quadratic non-residue.

The general solution is to use Schnorr groups, where the generator only generates a part of the multiplicative group, but has a large prime order itself (which is also the order of all elements except the neutral element).


Number generation for Fujisaki-Okamoto commitment scheme parameters

If you can select the distinct secret primes $p$ and $q$ such that $(p-1)/2$ and $(q-1)/2$ are also prime, then it becomes easy.  For a random value $r$, $g = r^2$ will have order precisely $(p-1)(q-1)/4 \approx n/4$ unless $r, r-1$ or $r+1$ happens to not be relatively prime to $n$ (which, if you select $r$ randomly in the range $[2, n-2]$, happens with probability less than $3/p + 3/q$, which is negligible.  And, if you select $h$ the same way (select a different random value $s$ and square it $h = s^2$), then it is guaranteed to be in the group generated by $g$.

So, it boils down to:

When it comes time to select $p$ and $q$, select safe primes (which takes rather a bit more time, but is still doable)
To select $g$ and $h$, select independent random values $r, s \in [2, n-2]$, and set $g = r^2 \bmod n$ and $h = s^2 \bmod n$

You could replace that last step by selecting a random exponent $\lambda$ and computing $h = g^\lambda$; I assume that you would prefer not knowing the discrete log of $h$ yourself.


One ciphertext, multiple keys, multiple messages

This functionality is usually called deniable encryption. It is feasible for (innocuous/incriminating) pairs of a few messages.

Wikipedia:

  Deniable encryption makes it impossible to prove the existence of the plaintext message without the proper encryption key. This may be done by allowing an encrypted message to be decrypted to different sensible plaintexts, depending on the key used. This allows the sender to have plausible deniability if compelled to give up his or her encryption key. The notion of "deniable encryption" was used by Julian Assange and Ralf Weinmann in the Rubberhose filesystem and explored in detail in a paper by Ran Canetti, Cynthia Dwork, Moni Naor, and Rafail Ostrovsky in 1996.

There are related questions and answers, e.g., is-there-an-encryption-decryption-algorithm-that-can-give-two-different-outputs, and deniable-encryption-from-simple-primitives as well as a few others.


How would multiple uses of a vigenère cipher be decrypted on paper (classic)?

My impression is that it would at most take a longer ciphertext to be decrypted. Imagine first the scenario where the different keys have the same length:

$K_1=hello$

$K_2=world$

In that scenario, the keys add up and the result of applying $E_{K_2}(E_{K_1}(m))$ can be expressed as one single operation: $E_{K*}(m)$, where $K*=dscwr$. Therefore, not a lot is two encryptions are nested with keys of the same length.

If you use keys of different lengths, you'll meet the same combination of letters at some point. Let's say you have a key of length 3 and a key of length five:

$K_3=abc$
$K_5=rolex$

After the position 15 ($5 \cdot 3$), you'll encrypt again a value with the same combination as in the position 1. Therefore, it is as if you had two 15-character keys:

$K_{15}'=abcabcabcabcabc$

$K_{15}*=rolexrolexrolex$

So, for this case in particular, you win nothing.

Now, for the most general case, keep in mind that no paper cipher is a serious rival against the existent computational power. However, if by some clever narrative you manage to limit the powers of the adversary to just paper based attacks, there are paper algorithms much stronger than Vigenère. You can start by taking a look at Solitaire: https://www.schneier.com/cryptography/solitaire/


Right usage of PBKDF2 and login system questions

You should not SHA512(PBKDF2(password)). Your AES encryption key and the password hash are correlated (which may be a vector of attack in the future). A better solution is:

Generate a secure random string $r_1$ of like 64 characters
Generate another secure random string $r_2$ of like 64 characters
Derive the AES key by PBKDF2($r_1$ || password, 32)
Get a password hash from login by PBKDF2($r_2$ || password, 128)

Due to the two distince random strings used as salts both, the AES key and the password hash are much harder to correlate. You can, if you want to make the derivation of the AES key/password hash harder, use multiple rounds:

Round 0: $x_0$ = password
Round 1: $x_1$ = PBKDF2(r1 || $x_0$)
Round 2: $x_2$ = PBKDF2(r1 || $x_1$) = PBKDF2(r1 || PBKDF2(r1 || password))
...
Round n: x = PBKDF2(r1 || $x_{n-1}$)

PS:

|| means to concatenate two strings
PBKDF2(str, length) means generate a hash of length 32 bytes from the string str


BB84 Why does Bob generate a random key?

What I don't understand: what would be the problem if, after Bob receives $\psi$, he simply announces this fact without choosing $b'$ and making measurements.

At the current state of technology, Bob needs to take a measurement of $\psi$ when he receives it; he can't hold it.  It may be that future technology will be able to hold $\psi$ for a nontrivial period of time in an unmeasured quantum state until Alice announces $b$ (and, at that point, Bob cuold then take the appropriate measurement); however, we don't know how to do that now (and it certainly wasn't possible when BB84 was invented).

And, of course, Bob can't measure $\psi$ in both the $X$ and $Z$ basis; that's forbidden by QM (and the security of BB84 relies on that).


What exactly are an untrusted memory and a trusted CPU?

As the name implies, the memory or CPU are partially or entirely untrusted.

An adversary who can control your memory and/or access patterns can learn a great deal about your data, even if it is encrypted. ORAM hides both the data and access patterns. ORAM may extend to disk or network storage, not just local memory.

An adversary who can control your CPU / program can do any arbitrary computations they want, including skipping safety checks or leak sensitive information outside the trusted container.

Trusting a public service on untrusted hardware

A public service may use SGX to verify to their users that they run the open source code that they commit to. I.e. to prove they don't have access to personal information, while their system actively processes the sensitive unencrypted information.

SGX only verifies the program that is running. Depending on the program and how it uses memory, a hypervisor may be able to observe the memory accesses (but not the internal program state) and learn properties of the secrets. ORAM protects against the latter case.

Neither trusted nor untrusted are ideal when we have more than 1 party. If you can use verified protocols instead, then you do not need to place trust in another party - because they cannot cheat (without being detected).


Detecting steganography in the stream of short messages

Proof of security:

Let $(x_1, ..., x_n)$ be the messages you caught.

Let $(p_1, ...)$ and $(q_1, ...)$ be three streams of random messages known to both communication partners. Let these be from a true random number source generating non-autocorrelated data.

Let $(n_1, ...)$ be another stream of data from the same source.

Since there is no correlation, it is impossible to distinguish $p_k$ from $q_k$ or $n_l$ without knowing the actual data stream.

To communicate, now pick $p_k$ if bit k of your message is $0$ and $q_k$ if it is one. If you do not wish to communicate simply send $n_k$.

Note: This all depends on a true RNG. When utilizing a PRNG, this is possible, however there exist security proofs http://en.wikipedia.org/wiki/Blum_Blum_Shub that have a security guarantee that makes this at least as hard as integer factorization.

For your twists, it really becomes a question of how much information you and the attackers have:

No. Again, Cryptographically secure RNGs are indistinguishable from true RNGs with reasonable computation power (otherwise they would not be secure...) and therefore, without knowing more about its seed, any sequence of messages is a legitimate output. Even slight shortcomings can be circumvented by utilizing an injection method like the above that uses another (differently seeded) PRNG of the same type.
Sure. Just break it. If you restrict the number of possible messages to 1, injection is only possible through side channels (e.g. the number of messages, their arrival timing, etc). Whether you can detect these depends on your exact setup.
At this point, it is not even about PRNGs anymore. If your adversary just added a MAC http://en.wikipedia.org/wiki/Message_authentication_code to their messages, they can detect your attempts at forging. (Note that this is only very losely related to question 2).


This is indeed best way to do it. As the final $(cbc\oplus cipher)$ encrypted by a different key even if we pass 0 messages it do not reveal any information. Previously passing on 0 messages gave encrypted cbc (which is later $\oplus$ed encrypted ($cbc\oplus cipher$) to reveal information) now as the key used is different even if the encrypted cbc (on passing 0 messages) is known it wont reveal information.

Hope this helps.


First of all, the usual way to do this is to generate a new random AES key and then wrap it with the public key. Generally you don't encrypt with the private key at all.

Yes, SHA-256 is a one way hash so you can do this. The problem is that you would still need to encrypt with a public key to let the other party know the AES key (unless you use the key to encrypt for yourself, of course).

There are however a few pitfalls:

the private key needs to be encoded as bytes, and not all encodings are canonical; i.e. you could use different encodings for the same private key. If this ever happens in your scheme you would not be able to generate the same AES key;
you'd need a separate input - e.g. a counter (nonce) - if you want to generate more keys;
SHA-256 is not a KDF, you could use HKDF instead (which just requires a hash function to work).
Sometimes hashes over private keys are used as key identifiers. You must make sure that this is not the case. For RSA however the key identifier is usually generated by a hash just over the public modulus.
You'd forgo the option to store the private key within a security module, as direct access to the components that make up the private key would likely not be available.

The biggest question that you should ask yourself is this: why do you need an AES key for encryption at the location of the private key. That's a strange use case.


The ANSI X9.63 uses SHA-1 for Key Derivation Function:

  Ingredients: The key derivation function employs the hash function SHA-1 specified in Section 5.6.2

NIST SP800-108 uses PRFs:

  This Section defines several families of key derivation functions that use PRFs.

First look at their dates;

1998 : ANSI X9.63
2009 : NIST SP800-108

And, SHA-1 is no longer recomended. So you should prefer NIST SP800-108

There are two other reasons for not to use SHA-1:

SHA-1 is shattered, you can also read these two articles:

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?
After Google's collision attack, is RSA-SHA1 signature still safe?.

Reaching $2^{80}$ for the generic birthday attack is not that far since the Bitcoin miners reached $\approx2^{92}$ for SHA256 hashes per year in 06 Agust 2019.
Also, SHA-256 is approximately 2.2 times slower than SHA-1 on hashcat 2080Ti

Note: Depending on your case, there is also password-based key derivations; as PBKDF2


Difficulty to find any preimages $a$ and $b$ for given $V$ so that $H(a) \oplus H(b) = V$?

$ Pr(H(a) \oplus H(b) = V)$ is independent of $V$ For a good hash, as pointed out in the comments. Pick your input space to be the output space of SHA-224 so with probability $1/2$ (1) holds.

The range of $H$ is a group under $\oplus$. So (2) holds.

3 won't hold by the same group property. Another $2^{112}$ trials will likely yield $a',b'$ satisfying (3) with probability $1/2$.


Secure MAC implies that probability of same tags on different messages is negligible

Is this a homework problem?

Here's a hint: Suppose that the probability of getting the same tag on two different messages is $p$.  Show how to construct an adversary that breaks the MAC (i.e., forges a valid tag), and that has success probability $p$.  Assuming the MAC is secure, what can you conclude about the possible range of values for $p$?


Why is ElGamalEngine in bouncy castle restricting input data to be less than the length of the group parameter p?

Originally we had restrictions like this in place as the alternative was emails about bugs in ciphers like RSA resulting from people not understanding the implications of modular arithmetic (if you are going to push right to the boundary you really have to understand what's going on). Having said that, I actually think we'd outgrown this by the time ElGamal appeared (around BC 1.12).

Oh dear, looks like there's another test further down. Perhaps partially outgrown would be a better way of putting this.

Okay, this is now fixed and checked in it should appear on github shortly.


What should I be aware of when implementing algorithms myself?

Does matching all the test vectors mean my implementations are valid mathematically?

Basically the comments got it, but test vectors are designed to attempt to hit lots of cases, but with high probability will not catch every single mistake. Should you do it? Definitely. Does it mean everything is perfect? No.

  Is implementing mathematics correctly not enough because there are other things I need to plan ahead for?

Like you mention, side channel attacks are of concern. Another concern which has little to do with security is efficiency. That said, if your library is too slow, others might disable it. This could be developers or users (if that option exists in the software).

I am all for doing things for learning purposes. It is a good exercise and can teach a lot. I am a "do it to learn it" kind of person. So I don't want to discourage you from that. If projects you are writing need crypto, and they are to be used by others, you are probably better off using stuff that is out there and has presumably been reviewed by cryptographers.


How to find collisions in a hash function knowing its coefficent?

We can easily find collisions for this system.

Let $x=(x_1,...,x_n) $ be a sequence such that $h(x)=k$. For finding collision we can do this:

Select $x'=(x_1',...,x_{n-1}')$ and then compute:

  $$x_n'=({a_n}^{-1}\cdot(k-\sum_{i=1}^{n-1}a_ix_i')) \bmod N$$

Now we have  $h(x)=h(x')=k$.


efficient authentication with broadcast encryption?

The answer to your question is yes this is possible, but if we don't use assymetric cryptography, we need an alternate source of assymetry. One option is using time-delayed schemes. In such schemes, the key for the MAC is not initially disclosed, but only after some time interval.

See here for TESLA that accomplishes this. TESLA has a drawback in that it requires an initial digital signature to send the initial parameters. A second variation of TESLA, uTESLA  achieves this without digital signatures.


OCB-AES: Ambiguous definition of "Encipher" in RFC document

The 256-bit K of OCS-AES must first go thru FIPS 197's

  KeyExpansion(byte key[4*Nk], word w[Nb*(Nr+1)], Nk)

where it is key[4*Nk] to be transformed into w[Nb*(Nr+1)] (32×4×(14+1) = 1920-bit), which is the last input of

  Cipher(byte in[4*Nb], byte out[4*Nb], word w[Nb*(Nr+1)])


How does second pre-image attack on Merkle Signature Scheme work?

Hoes does second pre-image attack on Merkle Signature Scheme work?

Lets take a simple example; suppose the attacker sees a valid Merkle signature; in that signature, he sees the bottom-most Merkle tree node of the form:
$$A = H( B, C )$$
where $H$ is the Merkle tree combination function, $B$ and $C$ are the left and right child nodes, and $A$ is the node value.  He also obtains from that signature the authentication path from node $A$ to the root.
The attacker's goal is the generate a forgery; to do that, what he does is generate his own OTS private key, and the corresponding value $X$.  Then, the second pre-image attack is to find a value $Y$ with:
$$A = H( X, Y )$$
If he succeeds, then he can generate a forgery with any message he wants.
What he does is generate the OTS for that message with the public key $X$ (which he can do; he has the private key).
Then, to form the authentication path, the first node of the path is the value $Y$; the rest of the path is copied from the valid authentication path he has seen.
When the validator examines the forgery, he'll compute the OTS public key, which will result in the value $X$.  He will then walk up the authentication path; the first step will be computing $A = H(X, Y)$ (as $Y$ is the value he sees in the authentication path; the rest of the path will proceed precisely as the valid signature, resulting in the expected public key value, and so the signature validates.


Yes, it is possible. Like SEJPM suggested, you can use a variant of the Franklin-Reiter related-message attack to accomplish this. Let $\Delta = r_2 - r_1$. Compute $\gcd(X^{e} - c_e, (X + \Delta)^{s} - c_s)$ over $\mathbb{Z}/n\mathbb{Z}[X]$, which yields the linear polynomial $X - (m + r_1)$. Recovering $m$ is now trivial. This, of course, will only be reasonably efficient for small exponents $e$ and $s$; but it should be quite doable for common exponents below $65537$.


Generating HMAC(SHA256) keys using WebCrypto deriveKey() API

NIST SP 800-107, section 5.3.4 which reads

Let C denote the bit length of the internal hash value that is
denoted H in FIPS 180-4. (This H is often called the “chaining value”
in descriptions of Merkle–Damgård-style hash functions.) Note that C
is not (necessarily) equal to L, the bit length of the hash function’s
output (see, for example, SHA-384 or SHA-512/t for any t < 512, for
which L < 512 = C). In all currently approved hash functions, L ≤ C
(with L = C for SHA-1, SHA- 256, and SHA-512).
The effective security strength of the HMAC key is the minimum of the
security strength of K and the value of 2C. That is, security strength
= min(security strength of K, 2C).

It looks like the API aims to produce HMACS with security strength of 512-bits according to the NIST document, though it also appears that the API comments do not reflect this. I would assume that the intent is to follow NIST and the documentation is at fault.

Following the NIST publication, a uniform random 512-bit key would be required to make best use of the full security offered by the SHA-256 algorithm.


Why is MAC using nonce+message+hash(nonce+message+identifier) not the standard?

It has the disadvantages of any MAC-then-encrypt scheme, which I'm quoting from the linked answer below. In addition:

It has the property that you need both a nonce and a hash, so for equivalent security it requires more message space.
The nonce has to be random, so it requires strong random numbers for each message, unlike e.g. AES CTR + HMAC.
Doesn't work if you need deterministic encryption, for some reason.

From the link:

  Does not provide any integrity on the ciphertext, since we have no way of knowing until we decrypt the message whether it was indeed authentic or spoofed.

This means that it may allow some chosen-ciphertext attacks that encrypt-then-MAC would protect from. It also means more time is wasted on incorrect messages, which could e.g. help with denial-of-service attacks.

  If the cipher scheme is malleable it may be possible to alter the message to appear valid and have a valid MAC code. This is a theoretical point, of course, since practically speaking the MAC secret should provide protection.

In your scheme the nonce and ID take the place of the MAC secret, which could be weaker if the encryption is weak and the hash function isn't a strong MAC in that mode, but can't be any stronger. Still theoretical, as long as you choose a strong, unknown nonce.


How secure is a 128 bit ideal substitution cipher

A block cipher is a keyed permutation. The number of possible permutations is quite high. There are of course $2^{128}$ ways of mapping a single 128 bit plaintext block to a 128 bit ciphertext block. Actually, the number of ways of mapping all possible plaintext blocks to each and every ciphertext blocks is $2^n!$ where $n$ is the block size in bits.

The key is used to choose one of these possible permutations. That means that your key table would have more than $10^{10.000.000.000.000.000.000.000.000.000.000.000.000.000}$ entries. That's a gargantuan number; there are a lots of ways how to map $2^{128}$ values to $2^{128}$ after all.

Is a 128 bit ideal block cipher secure? Sure, it's ideal - so it is secure, by definition, for any block size.

Is a 128 bit ideal block cipher practical? No, the key space is ever so slightly too large for life.

An ideal block cipher is possible up to a block size of about 4 bits, however that block size is way too small to be usable in any block cipher mode of operation (such as CBC) for any kind of data. It's therefore a theoretical construction rather than a practical construction.


RC6 is secure, and has no effective limit on input size.

RSA is an asymmetric cipher. It is not designed for general purpose encryption, and so has a very tight limit on the amount of data that can be encrypted. In fact, unlike symmetric ciphers, textbook RSA is based on a mathematical problem, so the ciphertext is the plaintext raised to an public exponent, modulo a large public integer. This modular operation puts a hard limit on the length of the plaintext to be encrypted. Note that RSA is not used to encrypt anything directly. It is used to encrypt a smaller symmetric key which is then used to protect the confidentiality of further communications.

RC6 is a symmetric block cipher. The amount of data that can be encrypted with a single key depends on the mode of operation in use, as well as the block size of the cipher. For a cipher with 128-bit blocks, like RC6, the amount of data it can securely encrypt is vast. To put it into hard numbers, in order to have an already astronomically small 2-32 chance of leaking a little bit of information from one 128-bit block in CBC mode, you need to encrypt more than four petabytes of data with one key. A mere five megabytes is nothing.

There are no known attacks which weaken RC6 to the point that breaking it is practical. As it did not win the AES competition however, it has received comparatively less analysis. A large amount of information on its security can be found by searching "rc6 cryptanalysis pdf".

Obligatory disclaimer: Choosing the cipher is the easiest part of implementing a secure cryptosystem. If you are designing your own cryptosystem, don't. Simply using RC6 is not enough to provide security. You need to choose the proper mode of operation, use authentication, use a secure KDF if the key is to be derived from a password, mitigate a variety of attacks if used on the network (reflection, replay, man-in-the-middle, etc). Don't think that, just because you are using a secure cipher, that the data you encrypt is secure.


Security of key schedule that only XORs a key with constants

This key schedule is Totally Linear. If two Master Keys $MK$1 and $MK$2 have a difference of d, all the round keys will have difference of d with probability of 1. This makes the cipher vulnerable to Related key Attack. But its hard to workout and comment without the knowledge of the cipher description that how badly such key-schedule effects the security of cipher

The PRINCE – A Low-latency Block Cipher for Pervasive Computing Applications have very simple key-schedule, and its designers say

  for our cipher it holds that decryption for one key corresponds to
  encryption with a related  key.  This  property  we  refer  to  as
  α-reflection

For more information about key-schedule requirements see "What are the requirements of a key schedule?"


Understand LWE(Learning With Error) negligible error probability

The probability of error is negligible "as a function of $n$", meaning that the probability of error will decrease (quickly) as $n$ grows. Increasing $n$ should solve your issue.


Which TLS features are vulnerable to chosen-prefixes collision on SHA-1?

Executive summary:

The history of attacks on SHA-1, especially by Marc Stevens et al since about 2012, made people realize SHA-1 will get broken soon enough and it's time to stop using it. This process was complete before SHA-1 got completely broken, so nothing terrible happened with the latest publication.

So let's review how TLS uses hash functions.

As PRF to derive shared secret values (symmetric keys, IVs, nonces, MAC keys, etc.) from key exchange.

The PRF of TLS 1.1 and below uses SHA-1, but in HMAC. HMAC-SHA1 is not affected by the latest break.

SHA-1 is used in HMAC-SHA1 as MAC for the TLS Record Protocol, in cipher suites that use HMAC (i.e. cipher suites whose names end in "_SHA").

HMAC-SHA1 is not affected by the new break of SHA-1, so those cipher suites are not affected. You shouldn't use them anyway because it's MAC-then-Encrypt and there are many bad implementations in the wild (lots of Lucky13 variants, lots of POODLE variants).

SHA-1 can be used to issue leaf certificates and intermediate certificates.

SHA-1 certs have not been allowed for a few years (both leaf certs and intermediate certs). At the time, Facebook, Cloudflare and Symantec fought for SHA-1 certificates, the first two because they saw some traffic from clients that only support SHA-1 certificates and the latter because they had customers who were willing to pay a lot of money for such certificates to enable support for old hardware that can't be patched to enable SHA-256 certificates. A few CAs got caught issuing SHA-1 certificates after the deadline and were punished by browsers. This is all old news by now.

SHA-1 was known to be weak long enough in advance that the Web PKI TLS ecosystems is unaffected.

I suppose private PKIs using TLS are affected if they don't follow the best practices enforced by Web PKI, the CA/Browser Forum Baseline Requirements, Chrome security (as the largest browser, when they deprecate something it's dead), etc.

SHA-1 can be used for authentication, to sign the handshake key share messages ServerKeyExchange (DHE and ECDHE cipher suites) and CertificateVerify (only used with client certificates).

TLS servers that perform SHA-1 signatures over ServerKeyExchange message and TLS clients using client certificates that perform SHA-1 signatures in CertificateVerify messages using the key of their certificate might be vulnerable (I suppose those are almost exclusively RSA-SHA1 signatures, though I suppose other kinds can be used too).

I was under the impression that SHA-1 signatures produced by the TLS server itself have also been not allowed, but now I see that the TLS RFC doesn't say that, and there is a proposal to change the RFC.

Chrome removed support for ECDSA-SHA1 signatures in 2016.

Google said that they really want servers to support SHA-256 or SHA-512 for signing ServerKeyExchange (and Chrome might treat servers not supporting "modern TLS" as insecure), but I guess Chrome does not require it yet, so existing TLS 1.2 servers might sign ServerKeyExchange using SHA-1. I don't think the current attacks on SHA-1 let you do anything with this (it's a signature over client random, server random and server DH params).

Conclusion:

I think the current attacks only break SHA-1 CAs, and only those that issue certificates with predictable serial numbers (all of that has not been allowed for a while for publicly trusted certificates).

Recommendation: Don't use SHA-1 certs even if they are not publicly trusted, don't support SHA-1 signatures in the TLS handshake, use SHA-256 and SHA-512 instead.


Is there any serious discussion about using blinding intermediaries in digital currency scenarios?

It may be an interesting avenue to explore. I've read the highlight reel of the digital cash literature but I do not know it well enough to know how well these issues have been addressed.

A few things to consider for #2:

In a quick read of Lucre, it seems that the payee does no verification before passing the coin onto the mint. It seems, if the mint has a known public key, that the process may be improved if the payee can do some basic verification (is it actually signed?) before asking the mint if it has been double spent. Your solution #2 would make any payee verification difficult since it is working with a blinded value.
As I understand it, the payee submits the coin for verification but does not consider the transaction complete until they hear back from the mint that the coin is valid. For this reason, the verification must be realtime. This creates a timing attack problem (the same basic one that exists in all proxy systems including Tor) where a corrupt payee sends the coin at time $t_0$ and the corrupt mint receives the coin from the intermediary at $t_0 + \Delta t$. If $\Delta t$ is small and not many transactions happen within the window, the mint and payee can still trace the coin through the intermediary. In particular, the payee could adjust when they send the coin if it would help the attack. There are countermeasures in the Tor and mix network literature on this.
The #2 attack is made worst if there are more than one intermediary and users choose whichever they trust. The payee knows which intermediary the blinded coin is sent to and the mint knows which one it has received a coin from, so this information reduces the anonymity set of the possible origins of a given coin. It is now the set of coins per intermediary sent within a small window of time, and this is more likely to be a singleton set. Perhaps there is an alternate architecture where the user sends the coin to the intermediary instead of the payee, however be mindful of the next consideration.
Since the mint and payee are no longer directly communicating with each other, they can not mutually authenticate. How does the mint establish who the payee is? The mint has to credit the amount to the payee. It seems the user would have to sign a transaction saying to credit the coin to the payee, and only the user can do this because this singed transaction itself would also have to be blinded (alongside the coin). In this case, it seems the payee can be cut out of the first part of the protocol. The user sends the coin and transaction through the intermediary to the mint, the mint verifies everything and then credits the payee, then the mint informs the payee the amount that has been credited, and the payee releases the purchased goods to the user.

Anyways, the fact that there are maybe a few challenges with using an intermediary actually makes the question more interesting, rather than less interesting. It is no longer a simple clean-cut solution; it requires some thought and would make a better contribution if you could iron out all the issues.


Favor hash size or field size when systems are disparate?

MQV has been standardized by IEEE P1363 (specified in P1363 2000, and amended in P1363a 2004), but it does not involve hashing, and therefore can't provide an answer to the OP's question. HMQV standardization proposal has been submitted to IEEE, but it does not contain the specific details that @jww is asking for. I went through the relevant P1363 docs and have not found answers to the @jww's questions. If you think that those details (acceptable hash functions for HMQV, mapping between them and the allowed curves, method of conflict resolution if hash output size is greater or smaller than L) are provided there (and I just missed them) - please be so kind and post the exact reference (document name/number and the page number) here.

Now, since I did want to find the answer, and since Hugo Krawchyk is the author of HMQV, it seemed best to ask him directly. Here's what Hugo replied:

  I assume the question refers to the hashing that results in the values d and e.

  Let L denote log_2(q) where q is the order of the group.

  There are two choices for the length of d and e.
  They may be of full length L in which case I would take the output of the hash  and reduce it mod q (resolving the issue of longer hash values, but truncation to L bits would also work).
  Or, you can follow the optimization used in the HMQV paper where e and d are of length L/2, in this case the hash value is to be truncated to L/2 bits.

  I would note that this L/2 optimization does not buy you anything if you optimize the multi-exponentiation to compute sigma in HMQV. Such optimized multi-exponentiation will cost the equivalent of 1.16 exponentiations even with a full size (i.e., L) values d and e. In this case I would not recommend using L/2 length for d and e but rather the full size L.

  If the length of the hash is less than L but more than L/2 you can just use the output as is for the values d and e. But I would not recommend to use a hash function with less than L bits of output and definitely not one with less than L/2.

  Hope this answers the question.

From the above I conclude:

In your C++ code use the field element size (or rather the order of the group) as the decisive factor, and match/measure the supplied hash function against it.
If the hash output size that your caller provided is at least as big as L, use it and truncate its output if/when needed.
If the hash output size is less that L, probably still allow it (maybe the caller did know what he's doing) as long as it is greater than L/2.
If the supplied hash is smaller than (or equal to) L/2, refuse to instantiate the object and throw an exception.

This approach should apply to FHMQV as well.


How much safer is RSA-OAEP compared to RSA with PKCS#1 v1.5 padding?

RSA PKCS#1 is still secure if padding oracles do not apply. If padding oracles apply, for instance when a server verifies the padding after decryption and somehow leaks the result (through an error message or by leaking information about the the verification time) then OAEP is much more secure.
Note that in principle OAEP can also leak information through timing attacks, so just using OAEP is no panacea.

[EDIT] Another problem with PKCS#1 v1.5 is that it allows for a relatively small amount of randomness - 8 bytes in the range 1..255 - to be used for larger messages. This can be avoided by using hybrid cryptography (where a symmetric cipher actually encrypts the message) or simply by using smaller messages. However, the MGF1 function of OAEP should be better protected against abuse.

Furthermore, OAEP also has a security proof that the padding should be secure as long as RSA is deemed secure. Although there are no known attacks on PKSC#1 - besides the aforementioned padding oracle attack - the algorithm doesn't have a formal security proof so it is possible that attacks do exist.

These kind of things cannot be easily quantified. RSA has about no security if PKCS#1 padding oracles apply. The lack of security proof may lead to an attack in the future, but this is - very likely - independent of the key size. Neither calculations nor rules-of-thumb apply. You should rather take a good look at your use cases, threat-model and attack  vectors.

Or just use OAEP. Many libraries support OAEP because PKCS#1 is deemed less secure. Using RSA-KEM would also be a good option if that's available to you (and it is relatively easy to create if you have raw RSA available).


No, it is not guaranteed that in a 2048-bit RSA key, the prime factors $p$ and $q$ of the modulus are exactly half of the length of the modulus or 128 octets; much less so for $d_p$, $d_q$, and $q_\text{inv}$ .

In particular, PKCS#1v2.2 allows almost total freedom on size of $p$ and $q$ (and even allows more than two prime factors for the public modulus). $p$ and $q$ being of exactly equal size however follows from requirements mandated by some common standards, in particular FIPS 186-4, which requires $p$ and $q$ to be in the interval $(2^{1023.5},2^{1024})$ for a 2048-bit modulus.  This can be traced to its ancestor on RSA matters, ANSI X9.31 (1998).

While having $p$ and $q$ of exactly half the modulus is definitely common, there are implementations around which generate $p$ and $q$ of different size, and even standards like ETSI TS 102 176-1 with recommendation that clearly allow that, and have been interpreted as favoring it:

  $p$ and $q$ should have roughly the same length, e.g. set a range such as $0,1 < | \log_2p - \log_2q | < 30$;

Even if $p$ and $q$ are exactly 1024-bit, this does not insure that $d_p$, $d_q$, and $q_\text{inv}$ are exactly 1024-bit or 128-octet. They are often slightly smaller: the high order bits of $q_\text{inv}$ behave about as if $q_\text{inv}$ was random in interval $(0,p)$, thus $q_\text{inv}<2^{1016}$ with probability I guess at least $1/256$ (I welcome a proof or refutation of the estimate, or/and a better one).


Authentication of machine before installation (to stop piracy)

Thinking "crypto"…

One way I could imagine how you achieving at least some kind of copy-protection on your PHP-based scripts is to use solutions like these random search results: sourcecop, sourceguardian, phpcipher, … or the more well-known, and well-vetted Zend Guard or IonCube PHP Encoder who prevent reverse engineering through PHP encoding and obfuscation and thereby protecting your PHP code from unauthorized use.

But while those (partly cryptographic) script-protection solutions protect your PHP sourcecode, they (mostly) will not lock the scripts down to a single machine…

Blending in additional "security"…

To make the "encrypted PHP scripts" idea usable in your case, you could make your encrypted scripts dependent on some kind of self-coded PHP extension/module that locks itself to a single machine by letting the module verify a machine fingerprint (which includes several serial numbers, hardware configuration, etc.). Somewhat like cryptographically secure RNGs are seeded, but you would be looking for fixed and unique instead of variable and random hardware infos.

Thinking about it, you would probably be able to solve your problem by starting out with that PHP module and make it (a) machine-dependent, and (b) handle the cryptography of your encrypted scripts. If the module isn't in place and verified it's running on the correct machine, the scripts would not execute either as they would look to the PHP interpreter as if they were random digital garbage.

But the downsides of such an approach are pretty clear too, indicating that this is not an option for regular intranet projects. You would need to code (C/C++) a PHP module from scratch, you would need to get the crypto right, you would need to handle potential bottlenecks and slowdowns due to the PHP module's calculations, and much… much more.

And even then, someone who's able to reverse-engineer your module (or emulate the hardware environment parameters the module checks) would be able to "break" your protection. After all, if an attacker can grab your PHP files from your intranet server, he won't have too much of a problem grabbing your PHP module too. The rest of the attacker's job would boil down to a reverse-engineering effort.

Reality-Check…

Obviously, there are some potential options that could tackle the problem, but unless you are working on a big project for some government/corporation/institution, it'll be "overkill" to even think about practically implementing them as they will simply use up too much time and manpower to create from scratch.

From my point of view, the cheapest, the fastest, and the safest way to protect your PHP scripts would not be by means of modern cryptography, but by buying a good lock for your server-room. After all, restricting physical access is the safest way to stop an attacker from copying files from the (locked-in) intranet server. And if you're really fond of cryptography, get one of those electronic locks with a nice interface to put next to the server-room's door… it looks good and entertains you with lock-codes. ;) Throw Zend Guard or IonCube PHP Encoder on top of that and you should be able to say "mission accomplished" — but only for non-critical, civilian purposes where the sole goal is to protect your PHP scripts from being stolen and executed/run on another computer system.


Your input alphabet is 95 chars, within the 128 character 7-bit ASCII space. You need the ciphertext to specifically be within the 95 char input alphabet. I assume the microcontroller byte size is 8-bits, and I hope you have 32-bit registers.

The best solution would be to use a 6-bit output alphabet (64 entries) and use an intermediate conversion between the input and OTP to perform XOR. You will of course run into a space penalty as your input is not within the 6-bit encoded space, but it will make up for it with the performance of the algorithm, which is quite quick.

The OTP can be stored as 8-bit per char raw data to save space and read in 6-bit intervals (24 bits = 3 bytes or 4 6-bit chars), or stored as 6-bits per byte. If you stored the OTP as encoded ASCII, it will need to be converted back into a 6-bit stream representing the index of the characters in the alphabet. If you store as 8-bit, you do not have to perform the intermediate conversion before XOR on the OTP, which you will need to do if it is stored as 6-bit.

The plaintext will be converted into a 6-bit stream either from its byte data (8 bits of data, read 6 at a time) or from an encoded 7-bit representation of the first 128 ASCII chars (7 bits read 6 at a time). If the microcontroller has 32-bit registers, you can pack 4 7-bit characters or 5 6-bit characters. 16-bit registers get you 2 7-bit or 6-bit characters. Now you can XOR with the OTP, and you can use several performance-space tradeoffs. You can read the OTP into the full register space (32-bits OTP for 28 or 30 bits of plaintext, 16-bits OTP for 14 or 12 bits of plaintext) and truncate after XOR. Or you can read the exact amount of bits from the OTP as required, which requires additional shift operations but uses less pad data.

After XOR, pack the result 12 or 24 bits at a time, and encode to a 6-bit printable alphabet. I have a high performance alphabet that allows me to use integer operations to encode instead of table lookups like Base64, if your processor is slow at lookups the integer method can be several times faster.

Treating the 7-bit input alphabet as 8-bit entries before encoding is faster, but you loose 1 bit per character of OTP and output space, this may be useful if storage and bandwith is plentiful but you want lower computation or code size. Using 6-8 and 8-6 for input, output, and OTP data means less code, and more simple algorithms:

Input = 7-bit printable ASCII
Inter1 = 8-bit (0 || input char)
Inter2 = 24-bit packed integer (3 x Inter1)
OTP = 6 or 8-bit data
InterOTP = 24-bit packed integer (24 bits of OTP)

XOR integers, encode resultant 24-bits to 4 6-bit characters (65% efficient)

  24-bits of OTP, 32-bits of ciphertext used for 21 bits of plaintext

If you want better efficiency, the input is treated at 7 bits instead of 8. You can read full bytes of OTP if you do not need efficiency of pad storage:

Input = 7-bit printable ASCII
Inter2 = 28-bit packed integer (4 x input char)
OTP = 8-bit data
InterOTP = 28-bit packed integer (32 or 28 bits of OTP)

XOR integers, encode resultant 28-bits to 5 6-bit characters (70% efficient), or treat 3 28-bit blocks as 14 6-bit chars (maximum 75% efficient)

  28-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
  32-bits of OTP, 40-bits of ciphertext used for 28 bits of plaintext or
  84-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext or
  88-bits of OTP, 112-bits of ciphertext used for 84 bits of plaintext

There are more space efficient methods, but the computation cost is astronomically high, and unsuitable for a microcontroller. You can pack 9 characters of 95-char alphabet into a 64-bit MMX register using extended precision FP math, encrypt with 64-bits of pad, and encode back into 10 chars using some VERY ugly and cycle hungry math, but it works and is 90% efficient, well beyond the max 6-bit encoding efficiency of binary data (75%).


Has anyone implemented the BB84 protocol?

Has anyone implemented the BB84 protocol and put it in production?

There are a number of commercial QKD devices on the market, including ones by IDQuantique, QuintessenceLabs, MagicQ and SeQureNet.  In addition, there are a number of other companies that are working on it (and may be actively marketing them as well).
Some of these companies use an internal protocol similar to the original BB84 protocol; others use other versions of quantum key exchange.

I am thinking of incorporating the BB84 protocol into the network list of protocols at the IETF

Now, the IETF (actually, the IRTF) has a research group, the Quantum Internet Research Group, that is already chartered to cover QKD (although that is not their main focus).  I'm not sure what your master list of network protocols is, but it should already be there.


No.

There is a difference between the type of a cipher and the construction of a cipher. If a cipher is of a specific type for which there are known IND-CPA secure constructions then that doesn't mean that an entirely different construction is secure. There are known attacks on stream ciphers, including "modern" stream ciphers such as RC4.

A stream cipher must be used correctly for the encryption scheme to be IND-CPA secure.

If the generated key stream is secure then the XOR of the plaintext with the key stream will of course also be secure (up to the specified limits of the stream cipher anyway).


How to analyze the off-by-one error's impact on the entropy of the result?

First of all the first Entropy calculation is not correct. Recall the definition of (Shannon) entropy:

$$H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_{\,b} \mathrm{P}(x_i)}$$

If uniformly chosen a digits entropy is

$$H(X) = -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 3.3219280...$$

Case $<250$ with 16 digits;

\begin{align}
H_1(X) &= 16 \cdot - \sum_{i=1}^{10}{\frac{1}{10} \log_2\left(\frac{1}{10}\right)}\\
H_1(X) &= 16 \cdot 10 \cdot -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 53.15084951...\\
\end{align}

See the calculation at Wolfram Alpha
Case $\leq250$ with 16 digits;

$$H_2(X) = 16 \cdot - \left( \frac{26}{251} \cdot \log_2\left(\frac{26}{251}\right)+9 \cdot \frac{25}{251} \cdot
\log_2\left(\frac{25}{251}\right) \right) = 53.14921795...$$

See the calculation at Wolfram Alpha

It seems this is a mistake in the book. The current errata doesn't include this.

The difference is tiny but can make a difference since 0 will occur more and that is distinguishable. For example, take a 1.000.000 sample occurrence of 0 is around  103,500 – approximately 10.36%.

For the visualization of the difference read this nice blog Anatomy of a pseudorandom number generator – visualizing Cryptocat’s buggy PRNG


RSA Signing: SHA512 incompatible with PSS?

Yes, this is expected, if the RSASSA-PSS signing code/test uses salt the width of the hash, which is customary. In that case, a $h$-bit hash (with $h$ multiple of 8) requires an RSA public modulus at least $2h+9$ bits.

That's semi-clearly stated in PKCS#1 v2.2, section 9.1.1, condition on enBits, with actual test in step 3. That's because the message representative needs to convey $h$ bits for the message hash, $h$ bits for the salt, $8$ bits for a one-byte identifier¹, and then some.

In PSS, the salt length can be made a parameter, rather than fixed to the hash width as usual. Also, it can optionally be deterministic or fixed, rather than random as usual. But far from all APIs allow that.

There are similar limitations for RSAES-OAEP (without flexibility: the tag's hash always is as wide as the hash, even when the tag is empty/absent, as it often is).

¹ That identifier BCh plays a role when using PSS padding for Rabin signatures or when it is used $r\to\min(r^d\bmod N,N-(r^d\bmod N))$ instead of the textbook RSA private key operation, in order to allow immediate textbook-RSA encryption of the signature with any public key with public modulus of the same size as the one used for signature.


Group Signatures with VLR Revocation Check

I do not have access to the paper you have linked, but I certanly can answer the first question and maybe answer the third question:

$(\hat{u}, \hat{v}) \in G_2^2$ is a short version of $(\hat{u}, \hat{v}) \in (G_2 \times G_2)$ which is a short version of "$\hat{u} \in G_2$ and $\hat{v} \in G_2$".
Since I don't have access to the paper I'm gonna make some assumptions to answer the third question:

$e$ is a bi-linear mapping of the form $G_1 \times G_2 \rightarrow G_3$. I make this assumption based on the fact the second parameter is element of a group called $G_2$ which hints at the existence of a group $G_1$.
$\psi$ is a linear homomorphism from $G_2$ to $G_1$. This would make sense as the first parameter of $e$ would be an element of $G_1$ under the first assumption. Also $\psi(g_2)$ must be $g_1$ for the math below to check out.

Be $x, y \in Z_q$ with $\hat{u} = g_2^x$ and $\hat{v} = g_2^y$, then $u = g_1^x$ and $v = g_1^y$ since $\psi(g_2) = g_1$. This leads to:

$e(v^{\alpha}, \hat{u}) = e((g_1^y)^{\alpha}, g_2)^x = e(g_1^{\alpha y}, g_2)^x = e(g_1, g_2)^{(\alpha y) x} = e(g_1, g_2)^{(\alpha x) y} = e(g_1 ^ {\alpha x}, g_2^y) = e((g_1^x)^{\alpha}, g_2^y) = e(u^{\alpha}, \hat{v})$

AS stated above, this only works under the assumptions above, which are assumptions. If these are not correct feel free to leave a comment or edit.


Decryption of message in IBE without random oracle using bilinear pairing registration?

I don't know whether it is correct

$$e(c_1,d_1) = e(g^s, mk\cdot(y^{id\cdot h})^r)$$

$$=e(g^s,mk)\cdot e(g^s, (y^{id\cdot h})^r)$$

$$= e(g^s , g_1^\alpha ) \cdot e(g^r , (y^{id\cdot h})^s)$$

$$= e(y , g_1^\alpha ) \cdot e(g^r , (y^{id\cdot h})^s)$$

$$e(c_2,d_2)  = e((Y^{id\cdot h})^s , g^r)$$

$$= e((Y^{id\cdot h})^s , g^r)$$

therefore $e(c_1,d_1)/e(c_2,d_2) =  e(y , g_1^\alpha )$


I don't think it will become popular. AES-SIV has a main usage as key wrapping mechanism for its deterministic encryption properties. But keys are generally pretty small; parallel computation is certainly not required for minimal amounts of data.

With regards of performance: yes it can be parallelized. But on a modern machine you may need a lot of enhancements to beat AES in CTR mode + AES CMAC on a single thread that uses hardware acceleration. Intel's AES-NI + GCM acceleration can get throughput of 2 Gbps (that bits, mind you) on a single core of a Westmere chip (that's an old chip doing 2.4 GHz) - and that's within an actual IPSEC tunnel. You may want to go faster, but it might be that other components of your system cannot keep up. For server components that can have any amount of connections: if you have a 8 core chip (and 8 connections) you may easily saturate a 10 Gbps network card.

AES-PMAC still requires a single AES block encrypt per plaintext block. So even though it can be parallelized it will be outperformed by special MAC constructs such as GMAC or Poly1305 that do not require block cipher calls for each block of plaintext. You'd need at least another thread to make up for the difference in performance, and they you'd still need to manage the multi-threading.

I presume that the authentication tag is relatively secure, even if only the first x bytes are used for authentication tag. That's maybe nice for embedded platforms, but those commonly don't go for multi-threading / parallel computation. It's certainly an advantage over other MAC constructs that do not have this property, but not over others such as AES-SIV, AES-EAX or AES-CCM.

The one good reason why it may get popular is when the cryptographic community decides to switch from authenticated encryption to encryption that is largely impervious to nonce reuse (nonce misuse resistance).

But note that GMAC, as used in GCM mode, may actually performed in parallel as well; putting the parts together requires some additional calculations displayed here. So GCM-SIV may also be executed in parallel, using a less computationally expensive MAC calculation. GCM in SIV mode sidesteps the issues with the nonce that makes it extremely sensitive to nonce reuse. MAC calculations that use a block cipher are simply not that efficient.


Can I increase strength of ECB by decorrelating input data with compression

One problem with this approach is that both most compression algorithms and most block ciphers in ECB mode are deterministic. In other words, if you encrypt the same text twice, even if it has been compressed before, this fact will be obvious from the ciphertext.

I'd recommend you to have a look at counter modes, in particular AES-GCM (Galois/Counter Mode). They allow you to perform encryption in parallel without suffering from the problem outlined above (provided you use different IVs for each plaintext, as you should).


Do I need to know the "mode of operation" to decrypt a message encrypted with a block cipher?

Yes, of course you need to know the mode of operation in order to decrypt.

On the other hand, the mode of operation isn't usually explicitly transmitted in the ciphertext.  Using the same key with different modes of operation may cause unexpected weaknesses.  For example, consider one message encrypted with CFB mode with IV=2 (which is perfectly secure) and another message encrypted with CTR mode with IV=0 (also secure).  If we give the attacker both ciphertexts, he knows a relationship between the first block of the CFB mode plaintext and the third block of the CTR mode plaintext; this is a leakage that does not happen with either mode individually.

Because of this, we restrict a specific key to one mode; that is, both sides agree that this specific key will be used with that specific mode.  If there are multiple modes possible, the two sides will agree to the mode at that time.

Now, there are some cases where a key is used only once; one such case happens we're using public keys to encrypt the file.  In this case, the encryptor will pick a random AES key, public key encrypt that AES key (using the receiver's public key), and then use the random AES key to encrypt the actual message.  In that case, you can encrypt the mode (and other details, such as whether we're using AES and not 3DES) along with the random key.