How does Diffie–Hellman differ from elliptic curve Diffie–Hellman?

You might want to checkout Wikipedia page of elliptic curves to get a basic overview.
The difference between DH and ECDH is mainly the group which is being chosen to compute the secret key(s). While DH uses a multiplicative group of integers modulo a prime $p$, ECDH uses a multiplicative group of points on an elliptic curve:

Alice and Bob agree on an elliptic curve $E$ over a Field $\mathbb{F}_q$ and a base point $G \in E/\mathbb{F}_q$.

Alice generates a (random) secret $k_A$ and computes $P_A = k_A P$.

Bob generates a (random) secret $k_B$ and computes $P_B = k_B P$.

Alice and Bob exchange $P_A$ and $P_B$.

Alice and Bob compute $P_{AB} = k_a P_B = k_b P_A$.
The secret $k_A$ and $k_B$ is a random value $\in \{1, ..., n-1\}$ where $n$ is the order of the group generated by $G$.

The equivalent RFC may be RFC 4753 (not sure, not into RFCs at all).
To agree on a common curve Alice and Bob may either generate a curve them selves or use predefined curves and base points. For this there are a couple of standards defined, see:

Brainpool
IEEE P1363
NIST
NSA Suite B
ANSI X9.63
...

Depending on application for ECDH you might want to choose different curves since some curves have benefits, for example amount of calculation steps for point multiplications.


Collision or second preimage for the ChaCha core?

Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core?

No, likely not.

The Salsa20 and ChaCha cores both consist of a large number of "quarter-rounds" each of which is invertible and bijective. The only reason neither core is a bijection (and thus can have collisions) is the final addition of the input elements into the state.

With Salsa20 flipping the high bits works because it doesn't affect the right side of the quarter-round equations:

b ^= (a+d) <<< 7;
c ^= (b+a) <<< 9;
d ^= (c+b) <<< 13;
a ^= (d+c) <<< 18;

Thus, flipping all the high bits flips them all the way through the rounds and is canceled out by the addition of the input data.

The ChaCha quarter-round doesn't have as simple symmetry:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

Different words get affected a different number of times by a bit flip and by a different kind of operation at first, so there is no simple change that would be left untouched by a quarter-round. Finding collisions is probably hard.

I realize this isn't proof, just a sort of handwaving justification.


I am one of the inventors of SIKE.

There is no actual Diffie-Hellman group in SIKE. If there were, then SIKE would be vulnerable to Shor's algorithm, as you said, largely defeating the purpose of a post-quantum cryptosystem.

Among other reasons, isogenies typically have a domain different from their codomain, so an isogeny cannot be iterated. You can compose two different isogenies (provided that their respective domains and codomains are compatible), but usually not an isogeny with itself.


Terminology: What is the word describing a hash key, a crypto key, and a certificate?

In the case of a digital signature, it was signed with a private key, and you are verifying it with the private key's public key the bits you are authenticating against are the input (encrypted or not) and the digital signature, which is an asymmetrically encrypted cryptographic hash of the input.

For an authenticating cipher mode such as OCB or GCM, the key is simply the cipher key, it is the same used for both authentication and encryption. GCM internally generates a Hash key that is the internal key that performs authentication, and is unique to each cipher key. Other dual key modes exist, in this case the key is generally called the MAC key. Most authenticating cipher modes also require a nonce to be unique and processed as part of either authentication or encryption (or both). The bits you are authenticating against are the inputs (encrypted or not, or both) and the authentication tag.

When using a MAC only construction such as CMAC (OMAC) or HMAC, the key is once again generally called the MAC key, the bits you are authenticating against are the input (encrypted or not) and the message authentication code.

MAC keys, depending on the algorithm, may further be broken down into subkeys, or may be one of the generated subkeys of a larger master key.


Is it possible to have a signature that signs itself?

Is there a signature scheme in which $\text{signature} = \mathsf{Sign}(\text{message} \mathbin\| \text{signature})$ ?

With standard RSA signatures (RSASSA-PKCS1-v1_5, RSASSA-PSS of PKCS#1), that's possible if one chooses the public/private key pair for that purpose, as a function of the message. On top of that one can even make the signature nearly anything (any bytestring the size of the public modulus except two¹: the all-zero bytestring, and its variation with the last byte 0x01).

I'll use RSASSA-PKCS1-v1_5 with RSA-2048 and SHA-256, because that's simple and common. I'll silently assimilate bitstrings to integers per big-endian convention.

Choose our arbitrary message $M$. Choose our 256-byte signature $S$ of 2048-bit, other than 0 or 1, and not overly close to $2^{2048}$ (say, the first byte is not 0xFF). Hash $M\mathbin\|S$ with SHA-256, yielding $H$, and form the 256-byte representative per EMSA-PKCS1-v1_5
$$R = \mathtt{00\,01}\,\underbrace{\mathtt{FF…FF}}_{202\text{ bytes}}\,\mathtt{00\,30\,31\,30\,0d\,06\,09\,60\,86\,48\,01\,65\,03\,04\,02\,01\,05\,00\,04\,20}\mathbin\|H$$

There remains to build a public/private RSA key pair $(N,e,d)$ with $N$ of 2048 bits such that $S^e\bmod N=R$ and $S<N$, which will insure that $S=\mathsf{Sign}_{(n,d)}(M\mathbin\|S)=S$, as asked.

The central idea is to choose $N$ the product of two primes $p$ and $q$ such that we can find odd $e_p$ with $S^{e_p}\equiv R\bmod p$ and $e_q$ with $S^{e_q}\equiv R\bmod q$, with $(p-1)/2$ and $(q-1)/2$ coprime, and product of distinct small primes. We'll then find $e$ by using the Chinese Remainder Theorem. Refer to this answer for details.

That takes like 30s in Python, Try It Online! (revised 2020-06-13).

¹ For deterministic schemes, there can be a few more forbidden signatures, depending on message. That's because when $R=S$ the method described won't work. However, exhibiting a concrete example would be a break of the hash.


Is this approach secure or there is some naive issue?

There are some issues, see below. Most naive ones at the top.

You need to trust the public keys to create an authenticated connection. I don't see any part of the protocol where you verify public keys.
Instead of signing "the message" you need to sign the key agreement parameters. If you just sign the message you're open to man-in-the-middle attacks. Once you've established session keys you just need authentication tags. This should also answer question #2.
Depending on the algorithm you may need an encryption key and a MAC key. Alternatively you could use an authenticated mode of encryption.
It's usually best to use separate client & server keys, assuming that you require two-way communication.
You're directly using a hash as Key Derivation Function (or, as TLS calls it, the PRF). Although that may not directly pose problems, it's probably better to use a true KDF, e.g. HKDF.

  What is the suggested ecc key size for this? If I calculate the SHA-384 of the shared secret, is the same ecc key size (so using curve P-384) a good choice? Should I use the biggest key possible (P-521)? Is even a smaller one enough (P-192)?

Using a hash of 384 bits and P-384 is nicely in balance. You can check the NIST recommendations at keylength.com, second table after >> 2030. The only thing currently worry about would be quantum computing as it could attack ECC cryptosystems in general.

Nitpicks:

You cannot generate an ECC key, you can generate a public/private key pair;
I don't see where you generate key pair for the server;

Why not take a look at the draft TLS v1.3. They specifically rewrite TLS there to make sure they solve all the loose ends of TLS v1.2. That should give a good insight in all the pitfalls of creating a transport protocol.

Of course for production purposes using TLS v1.2 is a good idea, don't roll your own.


Is it possible to split a large AES encrypted string and decrypt the parts one by one?

Absolutely. The key point is that, whilst in CBC mode, the encryption can be thought of as using the previous ciphertext as the IV - have a look at this diagram from wikipedia:

I assume from what you've said that you have a function that will "do" AES-CBC decryption on large amounts of data, and you wish to use this. So, you simply run:
$$
   D_k^{IV}(c_1\ ||c_2\ ||\dots||c_n\ ) = m_1\ ||m_2\ ||\dots||m_n\
\\ D_k^{c_n}(c_{n+1}||c_{n+2}||\dots||c_{2n}) = m_{n+1}||m_{n+2}||\dots||m_{2n}
$$

That is, wherever you 'break' the flow from the CBC output, you simply use the previous ciphertext as the IV to start the next section.


Is the RSA cipher alike to the Shift/Caesar cipher?

You are close but not exactly. In short, RSA is a trapdoor permutation.

Let $(n,e)$ is a RSA public key, then $y = f(x) = x^e \bmod n$ is a trapdoor permutation. RSA is a permutation since the function $f:\mathbb{Z}_n^*\to \mathbb{Z}_n^*$ is bijective.

RSA is a trapdoor permutation. Normally you can find the inverse a permutation if it is given explicitly. In RSA, however, given $x$ and the public key $(n,e)$, we can easily compute $f(x)$. If one is given a $y$ and the public key $(n,e)$, it is difficult to compute $f^{-1}(y)$. If one has the private key (the trapdoor),  can compute $f^{-1}(y)$.

RSA is not a shift-cipher. Although, a shift-cipher is also a permutation, seeing a randomly generated 2048-bit RSA public key that acts like just a shift-cipher will amuse any cryptographer. Actually, this is not possible with small public exponents.

Like any permutation, for textbook RSA, one can write a table and store it, so that you can revert it very easily. The encryption oracle is free. However, there are problems with this;

Today RSA requires at least 2048 or more bits to be secure. Therefore the table for the reverse permutation is infeasible. You cannot store it, however, you may perform short message attacks if textbook RSA is used. Generate all small short messages and compare them.
Textbook RSA is not used in practice and should never be used. For encryption there are padding schemes like PKCS#1 v1.5 padding or Optimal Asymmetric Encryption Padding (OAEP). The former is hard to implement and has attacks occur, again and again, Bleichenbacher and Manger attack. PKCS#1 v1.5 padding has no security proof, however, OAEP has one. If one ever consider encrypting with RSA should consider OAEP. These paddings have random bits that prevent getting the same result for the same input. Therefore with these paddings, the RSA permutation is randomized.

In practice, RSA is not used for encryption. It can be used for;

digital signatures with Probabilistic Signature Scheme (PSS)
Key encapsulation mechanisms
Hybrid encryption : RSA-KEM with Data Encapsulation Mechanism (DEM). Composition of a KEM and a DEM provides us the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack if an authenticated encryption mode is used like AES-GCM, ChaCha20-Poly1305, or
crypto_secretbox_xsalsa20poly1305


Can Skein be used as a secure MAC in format H(k || m)?

Length extension attack

The reason why $H(k \mathbin\| m)$ is insecure with most older hashes is that they use the Merkle–Damgård construction which suffers from length extensions. When length extensions are available it's possible to compute $H(k \mathbin\| m \mathbin\| m^\prime)$ knowing only $H(k \mathbin\| m)$ but not $k$. This violates the security requirements of a MAC.

Like all SHA-3 finalists Skein does not suffer from length extensions, so this attack does not apply.

State collision attack

There is also a potential attack based on state collisions where an attacker searches for a pair of messages which collide for all (or at least many) keys. This does not work for the sequential mode of Skein when computing $H(k \mathbin\| m)$, since it consumes the key before the message and the attacker thus doesn't know the internal state when the message gets hashed.

This attack applies in theory when using $H(k\mathbin\|m)$ in the treed mode of Skein since only the first node will have key dependent state and state collisions in other nodes can be searched for without knowledge of the key. This also applies to $H(m\mathbin\|k)$ in the sequential mode.

But since Skein has a 512 bit internal state, finding collisions by brute force costs $2^{256}$ operations, which is ridiculously infeasible.

Still collisions are usually the first property to fall to advancing cryptanalysis, so I have more confidence in MACs where this attack is not applicable at all, instead of merely being infeasible.

Built in MAC mode

Skein has a built in MAC mode, where the key is passed in as a separate parameter. The way it consumes the key is pretty similar to $H(k\mathbin\|m)$ but it doesn't simply concatenate them.

This mode has a few advantages over the simple $H(k\mathbin\|m)$:

It cleanly separates the domains of key and message
The initial state depends on the key for all nodes in a tree, not just the first
The key is consumed before any other parameter
The authors supplied an explicit security proof for this mode.
You can cache the state after consumption of the key improving performance for fixed keys (but reducing performance for single use keys). You can achieve a similar effect by padding the key to 512 bits (the block size) with $H(k\mathbin\|m)$, but implementations are unlikely to have support for that.

Properties 2 and 3 mean that the state collision attack does not apply even if you use some of Skein's additional features.

Unfortunately not every implementation includes the keyed Skein feature.

Conclusion

$H(k\mathbin\|m)$ is secure as MAC. But it's preferable to use the built in MAC mode where available, especially if you use any advanced Skein features such as trees.


While there are no prevailing private entities associated with the accreditation of security standards, the NIST does provide the Cryptographic Module Validation Program that "validates cryptographic modules to Federal Information Processing Standards (FIPS)140-1 Security Requirements for Cryptographic Modules, and other FIPS cryptography based standards.." (http://csrc.nist.gov/groups/STM/cmvp/index.html)

As I understand it, one could seek the status of a Validated FIPS Module via an NVLAP accredited Cryptographic and Security Testing (CST) Laboratory.

"Cryptographic modules are tested against requirements found in FIPS PUB 140-2, Security Requirements for Cryptographic Modules [ PDF ]. Security requirements cover 11 areas related to the design and implementation of a cryptographic module. For each area, a cryptographic module receives a security level rating (1-4, from lowest to highest) depending on what requirements are met." (http://csrc.nist.gov/groups/STM/cmvp/standards.html)

As such, one could leverage the FIPS security level validation from the NIST to publicly validate the security of their solution.


The best one is the most reputable one. That is, the one which had been widely used, studied, and standardized.
If both fall into that class, choose the one which uses more secure or larger-state primitives under the hood.
Example: when comparing the NIST-standard Hash-DRBG using SHA-256 versus HMAC-DRBG with SHA-1, I would personally choose the first due to larger state and security margin of SHA-256.


You need to allow queries before the attacker outputs $m_0,m_1$ since maybe the queries help the attacker choose $m_0,m_1$ that are "easier" for it to attack.

You need to allow queries after the attacker receives back the challenge ciphertext $c=E_k(m_b)$ since knowing $c$ may make it possible to generate a plaintext whose encryption helps to know what $c$ is.


Is it possible to brute-force a hash algorithm of 32 bits

You'd still need to iterate over all the possible passwords to do this, using a brute force or dictionary attack (i.e. a pre-image attack with regards to the hash). That is, unless the hash algorithm used isn't one way; i.e. you can retrieve more information about the passwords. A 32 bit hash is not common, so this could be possible.

Fortunately most passwords do not have a very high entropy, especially if they are limited to 80 bits (information taken from the comments). However, I don't think they are just limited to 80 bits (which would take too much time to crack). Usually passwords aren't made up of control characters and such; you'd need to know how the 80 bits are encoded - i.e. which character encoding was employed. Probably you can at least bring it back to 70 bits by always keeping the highest bit to 0 (keeping just to ASCII, in other words).

One advantage of 32 bit hashes is that it isn't likely that a strong password hash was used. That means that testing the passwords could be pretty fast. A disadvantage would be that there may be multiple passwords that match a specific hash.

That's useful information to an attacker, who's just interested in gaining access instead of the actual password. If you need to know the exact password though you might have some trouble for some passwords. That said, 32 bit could be just enough to have relatively few of those.

From the information you've given this may just be feasible. It depends on too many other parameters such as the strength of the hash function and the restrictions on the password to calculate the time precisely. Given a strong hash function it's however still directly (and probably linearly) related to amount of possible passwords.


How do I properly calculate an inverse element for curve25519 when implementing Sphinx password store protocol?

While point coordinates lie in the finite field over which the curve is defined, in this case $GF(p)$ with $p=2^{255}-19$, the scalars that you use lie in a field defined by the order of the generator, which is different from $p$.

Therefore when you invert using feInvert you invert with respect to the wrong prime.

You need to invert in $GF(n)$ with $n=2^{252} + 27742317777372353535851937790883648493$.

Unfortunately for you, X25519 never use arithmetic in $GF(n)$ and the only operation required by ed25519 in $GF(n)$ is the modulo reduction, not the inversion.
Therefore there is no readily available code for that in the reference implementations, and you have to either look for some code that implemented it or build your own.


What is the difference between any secret sharing scheme and arithmetic secret sharing scheme

As far as I can tell, it seems that the term "arithmetic secret sharing" was coined by Cascudo, Cramer and Xing in their 2011 paper "The Torsion-Limit for Algebraic Function Fields and Its Application to Arithmetic Secret Sharing".  Certainly, all the mentions of the term in the crypto literature that I could find with a few minutes of searching seem to cite this paper, and the term does not seem to appear in the literature (or, really, anywhere on the web) before 2011.  So if you want an exact and authoritative definition of what it means, that paper seems like the obvious place to look.

Indeed, the introduction to the paper by Cascudo et al. cited above provides the following, unfortunately rather technical, definition:

  An $(n, t, d, n - t)$-arithmetic secret sharing scheme (with uniformity) for $\mathbb F_q^k$ over $\mathbb F_q$ is an $\mathbb F_q$-linear secret sharing scheme where $k, n, t ≥ 1$, $d ≥ 2$, the secret is
  selected from $\mathbb F_q^k$ and each of the $n$ shares is an element of $\mathbb F_q$. Moreover, there is $t$-privacy (in addition, any $t$ shares are uniformly random in $\mathbb F_q^t$) and, if one considers the $d$-fold “component-wise” product of any $d$ sharings, then the $d$-fold
  component-wise product of the $d$ respective secrets is $(n - t)$-wise uniquely determined by it.

Almost the exact same definition, with the omission of only some conditions on the parameters $k$, $n$, $t$ and $d$, is also given directly in the abstract.  In section 5 of the paper, the authors also give the following alternative (and unfortunately even more technical) definition:

  DEFINITION 10 (ARITHMETIC SECRET SHARING SCHEME).
  An $(n, t, d, r)$-arithmetic secret sharing scheme for $\mathbb F_q^k$ (over $\mathbb F_q$) is an $n$-code $C$
  for $\mathbb F_q^k$ such that $t ≥ 1$, $d ≥ 2$, $C$ is $t$-disconnected, $C^{∗d}$ is in fact an $n$-code for $\mathbb F_q^k$, and $C^{∗d}$ is $r$-reconstructing. $C$ has uniformity if, in addition, it is $t$-uniform.

So, what exactly is an arithmetic secret sharing scheme, and what are they good for?

After quickly skimming the paper, I'm not yet 100% sure myself.  Certainly, they seem to be information-theoretically secure threshold secret sharing schemes constructed using finite field arithmetic, much like Shamir's secret sharing scheme.  Based on just my cursory reading of the paper, I'm not 100% sure whether Shamir's scheme itself falls within the scope of "arithmetic secret sharing", or whether it's merely possible to somehow construct arithmetic secret sharing schemes based on Shamir's scheme.  In any case, "arithmetic secret sharing", in the general sense, seems to be a fairly broad umbrella term that encompasses a number of schemes independently introduced in earlier papers by other authors, as cited by Cascudo et al.

As for what they're good for, apparently, one major application is secure multi-party computation, and specifically secure multiplication.  According to the paper's introduction, they can also be used for constructing error-tolerant secret sharing schemes, as well as for verifiable secret sharing.


Bit Commitment - from any One Way Permutations

It is "computationally" concealing --- that is it conceals only to a computationally bounded adversary. Note that computationally hiding, perfectly binding and computationally binding, perfectly hiding commitment schemes are, both, possible.


Secure multiparty computation... where one entity owns all parties

No.

If you split the data between the parties, say using additive secret sharing, anyone controlling all parties can recover the full data. That is part of the very definition of secret sharing. If you want to ensure that the data will remain hidden even when the adversary controls all parties, then you cannot simply run a secure MPC protocol on shares of the input, you need something that will hide your input even when the state of all parties is known. Homomorphic encryption is indeed the most natural solution that comes to mind.


Differential privacy what does "where the probability is taken over the randomness used by the algorithm" mean?

So here $\mathcal{M}$ is, as you wrote, a "randomized mechanism", so it means that for one entry $D$ it can output different values. For example, you can imagine that on entry $D = 1$, $\mathcal{M}$ outputs $0$ with probability $1/4$ and $1$ with probability $3/4$. To make it more concrete, you can imagine that in order to choose which output $\mathcal{M}$ will output, $\mathcal{M}$ can have access to a coin that it can toss (or, equivalently, to a random string $r \in \{0,1\}^n$ of sufficiently large size that can represent the result of a bunch of coin tosses that was tossed before). That way, in this example, $\mathcal{M}$ can toss the coin 2 times, and chose to output $0$ iff both coins are head (or, equivalently, it can output $0$ if the first two bits of the random string $r$ are equal to $0$, and it outputs $1$ otherwise).
When we write "where the probability is taken over the randomness used by $\mathcal{M}$", it is exactly this idea that we fix $D$, $S$, and $D'$, and check what is the probability for that $\mathcal{M}$ to output an element of $S$ when given $D$ as output.
In our example, if we take $S = \{1\}$ and $D = 1$, then:
$$\Pr[\mathcal{M}(D) \in S] = \Pr[\mathcal{M}(D) = 1] = \frac{3}{4}$$


I didn't get the hash length extension attacks

OK, so the general idea of MD5 and SHA-1 and SHA-2 is that they process the data in blocks. For the last block the algorithms first append a padding to the plaintext data and the encoding of the length to create the final block. If the padding and length do not fit then an additional block is used.

Now the problem with these algorithms is that the intermediate state, that is: the state after a block encrypt is directly used as the output for the final block. So if you have three blocks then the value of the last block operation is used as output. So if you have a message that consists of the first block and then two blocks that mimic the last part of the message, padding and length indication then the intermediate value between block 3 and block 4 will be identical to the output of the previous calculation. After that you can add any data and keep processing as usual.

Let's put this in a scheme, ignoring the secret for now:

| message_b1 | message_b2 | message_p3 | padding_p3 | length__p3 |
| process_b1 | process_b2 |              process_p3              |
| h_state_b1 | h_state_b2 |              h_state_p3              |

can be extended using

| message_b1 | message_b2 | message_b3 | message_p4 | padding_p4 | length__p4 |
| process_b1 | process_b2 | process_p3 |              process_p4              |
| h_state_b1 | h_state_b2 | h_state_p3'|              h_state_p4              |

For this to happen message_b3 must of course consist of message_p3 | padding_p3 | length__p3 otherwise h_state_p3' will be different from h_state_h3 and therefore h_state_p4 the final output will be invalid.

If the secret is (part of) message_b1 then the verifier will automatically prefix the secret for you. So you just need to provide the message itself, but it must consist of the special format.

SHA-3 post processes the hash, so the length extension is not possible anymore as the final hash cannot be an intermediate value of another hash calculation.


SHA-256 Hash identical on two similar but not exact items

The hash value of each file, though stored in the same folder with the
  same content differed between the two files.

That is because MS Word encodes things like who last changed the file in its actual file instead of just in the filesystem metadata. Thus this change indeed affects the hash.

  Is there an easy explanation for what two cds with files having
  different modification dates be identical?

CodesInChaos provided the answer in the comments:

  Change dates are part of the filesystem metadata and not of the file
  content itself, and thus don't get considered when hashing the file
  content.


Is it secure to use so many iterations of AES-CBC as a KDF so that it's slow even using AES-NI?

Here's an answer that takes your question down a different path. RFC 2898, "PKCS #5: Password-Based Cryptography Specification: Version 2.0" is the document that defines the PBKDF2 function, in section 5.2.  Although PBDKF2 is normally instantiated with HMAC, the spec says that any pseudorandom function (PRF) may be used, with the implicit proviso that the PRF must accept variable-length keys (since the password is used as the key).

RFC 4615, "The Advanced Encryption Standard-Cipher-based Message Authentication Code-Pseudo-Random Function-128 (AES-CMAC-PRF-128) Algorithm for the Internet Key Exchange Protocol (IKE)" defines such a variable-length key PRF on top of AES-CMAC (RFC 4493):

  The AES-CMAC-PRF-128 algorithm is identical to AES-CMAC defined in [RFC4493] except that the 128-bit key length restriction is removed.

CMAC itself is a CBC-like mode that was designed to fix the shortcomings of the CBC MAC (which is only secure for fixed-length message spaces).

So by plugging in those reasonably standard components together you get an AES-based password-based KDF that is a bit different from your diagram but you might find close enough for your purposes.


In practice you should use the tools already provided.  SSL/TLS and by extension HTTPS are very powerful tools that provide proper implementations of key exchange, authentication and privacy.  As far as I can tell this solves all of your problems.

AES-CBC alone is problematic.  As Thomas pointed out you lack authentication.  A common solution to this problem is using an HMAC and here is a good discussion of HMACs and encryption.


This doesn't work, because it is easy to compute $a$ from $ap \bmod N$ given $p$ and $N$. More precisely, it is easy to compute some $a'$ such that $a'p \equiv ap \pmod N$; $a'$ will not necessarily equal $a$, but that doesn't matter since $a'(bp) \equiv b(a'p) \equiv b(ap) \pmod N$, so the secret is correctly recovered.

In other words, this is Diffie-Hellman in the additive group mod $N$, and it doesn't work because discrete logs are easy to compute in such groups.


If your system already has some other unique user identifier (be it an ID, user-name, or an EmailAddress) is there any effective decrease in your security if you simply use that value as your salt?

The salt in a hash actually forms two different purposes. Generally, it is acceptable for a salt to be known, so let us consider H() a hash function, S, some data and P something to protect. From this information we store H(S+P) and S. There are two consequences for the attacker in generating a rainbow table for H(S+P):

Either they can generate a huge rainbow table for the entire set of possibilities that might be S+P. The longer the data you wish to reverse in a hash, the larger the data storage requirement of the rainbow table, so extending the length of the hashed data makes it infeasible to reverse the hash by generating a generic rainbow table.
The attacker can generate a rainbow table for the specific fields of input missing for a specific salt. Clearly, the usefulness of a rainbow table is then restricted to a specific set of hashes to attack, since in theory all other hashes should be useless.

In the case of 1) anything you add as salt will do, quite literally. The problem is the case of two. The reason for using unique, random salts is that the chances of colliding salts for a specific hash output are vastly reduced. For example, hashing userid:fred:mypassword and userid:fred:myotherpassword, a rainbow table generated knowing the salt userid:fred and the correct construction of the hashed text would work across both cases.


With the current requirements, it seems like any member of $H(C(P)) \bmod q$ should work.

Where:

$H$ is the set of secure hash functions, e.g. SHA-512;
$C$ is the set of canonical encoding schemes of the points, e.g. a compressed point representation (02+X or 03+X depending if Y is odd or not);
$P$ a the set of possible points on the curve;
$q$ is the order of the curve (already specified).

This is certainly one way and collision free, as long as the used curve and hash function outputs are large enough. But note that it is not well distributed over $\mathbb{Z}_q$ (especially if the hash is shorter than $q$ of course, when viewed as an unsigned number).


Understanding the "cube-root math" behind an RSA signature forgery


What algorithm does .NET use to generate primes for RSA and how can I verify it?

There is an implementation of RSA in C# .net,

That depends on what you mean by "implementation".

In .NET Framework there are two built-in classes which provide RSA functionality:

System.Security.Cryptography.RSACryptoServiceProvider (mscorlib.dll)
System.Security.Cryptography.RSACng (System.Core.dll)

In .NET Core there are 3.5 classes:

System.Security.Cryptography.RSACryptoServiceProvider (System.Security.Cryptography.Csp.dll, some functionality Windows-only)
System.Security.Cryptography.RSACng (System.Security.Cryptography.Cng.dll, Windows-only)
System.Security.Cryptography.RSAOpenSsl (System.Security.Cryptography.OpenSsl.dll, non-Windows-only, requires OpenSsl 1.0.x on the system)
The opaque type returned by System.Security.Cryptography.RSA.Create() (System.Security.Cryptography.Algorithms.dll)

None of those actually "implement" RSA, in that none of them really understand modulus, exponent, or CRT.

  What value of $e$ they are choosen?

All of the inbox providers use F4 / 65537 / 0x010001 as the value for the public exponent with their default options.

  I want to know what is the algorithm that they use to generate prime $p$ and $q$

That's up to the underlying library.  In some cases, that's up to an underlying library for the underlying library.

RSACryptoServiceProvider (.NET Framework, .NET Core on Windows)

The key is created with CryptGenKey.

Unless configured differently with a CspParameters value in the constructor(s) which accept(s) one the type uses PROV_RSA_AES with the default provider for that ProvType (MS_ENH_RSA_AES_PROV / "Microsoft AES Cryptographic Provider") and a key in the AT_EXCHANGE slot.

RSACryptoServiceProvider (.NET Core on non-Windows)

Skip ahead to RSA.Create(), this is just a compatibility type on non-Windows systems.

RSACng (.NET Framework, .NET Core on Windows)

The key is created with NCryptCreatePersistedKey using a null name (making it an ephemeral key) and the Microsoft Software Key Storage Provider provider.

To create keys using other providers someone can call a CngKey.Create overload and pass the pre-created key to new RSACng(CngKey).

RSAOpenSsl (.NET Core, non-Windows)

Keys are created using RSA_generate_key_ex with a fixed $e$ = $65537$, and an RSA* created with RSA_new (the default engine).

RSA.Create() (.NET Core)

On .NET Core an opaque type is used for platform-independent RSA functionality.  On Windows it's functionally equivalent to using RSACng.  On Linux (and any other *NIX other than macOS (or including macOS for the 1.0 or 1.1 releases)) it's functionally equivalent to using RSAOpenSsl.

Starting with .NET Core 2.0 the macOS version is powered by a non-public type which creates the key using SecKeyGeneratePair.

Completing the matrix

RSAOpenSsl doesn't exist at all on .NET Framework, and throws PlatformNotSupportedException on .NET Core for Windows.  RSACng throws PlatformNotSupportedException on .NET Core for systems-other-than-Windows.

On .NET Framework RSA.Create() emits an instance of RSACryptoServiceProvider, unless configured differently via CryptoConfig.

Other types

RSA is an open type, so anyone is free to write an RSA provider for .NET.  This post contains all of the types that ship as part of .NET (Framework or Core) and provide RSA functionality... for any other types you'd need to track down their owners.

So, I know that doesn't really answer your question; but it does give you places you can go to further hunt things down if you want to know the answers.

The proof of these statements for .NET Core can be found at https://github.com/dotnet/corefx/.  RSACng on .NET Framework at http://referencesource.microsoft.com/, and for RSACryptoServiceProvider on .NET Framework a combination of referencesource and a debugger (the actual call to CryptGenKey lives within clr.dll, which is not published on referencesource).

Oh, and Mono and Xamarin are probably doing something completely different.


Best choice of finite field for AES on a 4-bit microcontroller?

While $GF(2^8)$ is indeed isomorphic to $GF((2^4)^2)$ (and to the other fields you have mentioned), if you use the latter you will need a conversion routine to change the field representation from and to $GF(2^8)$. This will probably defeat any performance gain with the alternative representation (and I'm not sure there would be any). Another related issue is that the "nice" constants used in MixColumns (2 and 3) may not be so nice in the converted form, hurting performance when you multiply by them.

You can simply represent a $GF(2^8)$ element using two 4-bit words.


It could be straight-forward with verification equation quadratic in challenge, compared to well-known equation of Schnorr protocol that is linear in challenge.

In particular, for well-known responses like
$X = xc + \alpha$, $Y = yc + \beta$, $R, R', Z$
and equations for $C_1, C_2$ do it:
$(g^{R'} h_1^X h_2^Y)^Z = C_3^{c^2} D_1^c D_0$

Produce explicit formulae for $D_1$ and $D_0$ to complete this homework.

$(g^{r' c + \delta} h_1^{x c + \alpha} h_2^{y c + \beta})^{z c + \gamma} = C_3^{c^2} D_1^c D_0$

This approach with higher-degree polynomials in challenge rely on an upper bound for number of roots, two in this particular case.


Why are asymmetric cryptography keys more vulnerable to brute force attack than symmetric ones?

For your first question:
The main point here (at least that comes to mind) is that of how the key is made, used, and subsequently how it is attacked. Good symmetric ciphers are designed so that the best possible attack is brute force, i.e. simply trying with each possible key, which are typically random (or as good as). With a 128-bit key you have $2^{128}$ possible keys. Trying all of these takes a lot of time.

With an asymmetric cipher however, the private and public keys have a mathematical relation between them, and asymmetric ciphers are based on problems that are computationally hard to solve. An example of this is RSA, where the keys are based on two large (and secret) prime numbers, $p$ and $q$, then multiplied to create an even larger number, $n$. The result is then used for encryption and decryption (i will not go into further details of RSA here). To crack this system the most straight forward way is to find $p$ and $q$ by factoring $n$ (which is not secret).

Checking $2^{128}$ (or $2^{127}$ on average) symmetric keys with todays computational power is simply not possible within any conceivable time-frame. Factoring a 128-bit number however, takes about a second (depending on hardware and optimization). Thus, one needs larger keys for RSA than symmetric ciphers, e.g. 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.

For your second question:
Encryption and (even more so) decryption with asymmetric ciphers are often a lot more computationally intensive than a symmetric cipher (if i remember correctly is RSA typically about 1000 times slower than AES). This makes asymmetric ciphers impractical for encrypting large chunks of data. Subsequently, for encrypting e.g. internet traffic: asymmetric ciphers are typically used for securely exchanging keys that are used to encrypt/decrypt using a symmetric cipher.

EDIT: As rightly pointed out by @fgrieu the statement "128 to 256-bit symmetric keys are typically approximated to equal 2048 to 4196-bit asymmetric keys." is not correct, and comes from a writing-mistake on my part. The correct statement was supposed to be that 128-bit symmetric keys are typically approximated to equal 2048-bit RSA keys.


What's the reasoning behind the design of the TLS 1.2 PRF?

Read Marsh Ray's analysis. PRF in TLS is designed to be the most conservative aspect of TLS (the last part of TLS to break). Mr. Marsh calls it "the slowest, most conservatively designed stream cipher in common use".

TLS PRF seems to be NIST sp800_108 in "Double Pipeline Mode". What Tim McLean contemplates above as a potential alternative is sp800_108 in "Counter" mode.

The "Double Pipeline Mode" is the most conservative sp800_108 mode, and is also subject to several papers (ex. by Koutarou Suzuki and Kan Yasuda) that prove certain "feel-good" properties about it that are not present in other modes.

TLS (IMHO) is trying to ensure that its PRF survives even when the underlying hash function gets utterly broken (ex. assume something even more broken than MD5).


Managing data access through asymmetric cryptography

This is simple to do by combining symmetric and asymmetric encryption.

For example:

Generate data encryption key $s$.
Encrypt the data $d$ using symmetric algorithm $A$: $A_s(d)$.
Encrypt the symmetric key with the relevant parties public keys: $E_i(s)$.

The key can be per data field, or shared by various fields with equivalent permission requirements. When authorized requests access to the data, they would receive the encrypted symmetric key, be able to decrypt it and thus the data itself.

When you revoke access you have two options:

Only delete the encrypted symmetric key corresponding to that party.
Re-encrypt everything under a new symmetric key.

In the latter case you also prevent someone who has looked at the data earlier (and saved the symmetric key) from being able to decrypt the current version later. However, it can require more computation if the data is large.

As a compromise you could mark the data for re-encryption when next modified, under the assumption that since they had access they could already know the current value and must only be prevented from knowing future values.


In RSA encryption, why does the public exponent (usually, 'e') have to be coprime with $\varphi(n)$?

Textbook RSA encryption goes $c\gets m^e\bmod n$ with $n=p\,q$, and $p$ and $q$ primes (all quantities non-negative integers throughout). The question states

  $d$ is defined as $(k\,\varphi(n)+1)/e$

Yes¹, for some integer $k$ such that this division yields an integer. And that can only be the case if $\gcd(e,\varphi(n))=1$. Proof: Let $r=\gcd(e,\varphi(n))$. This $r$ divides $e$ and $\varphi(n)$. Let $f=e/r$, and $z=\varphi(n)/e$, both integers. We have $d=(k\,\varphi(n)+1)/e$, thus $e\,d=k\,\varphi(n)+1$, thus $r\,f\,d-k\,r\,z=1$, thus $r\,(f\,d-r\,z)=1$. When the product of two integers is $1$, both are $\pm1$; thus $r=1$. Thus by construction of $r$, we must have $\gcd(e,\varphi(n))=1$.

The definition of $d$ in the question implies $\gcd(e,\varphi(n))=1$. But the question also asks:

  If I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message. What (..) is the mathematical reason behind this?

That's asking for a seldom given proof of: if a decryption of textbook RSA encryption can be consistently made, then $\gcd(e,\varphi(n))=1$ must hold. Here we go.

We want RSA decryption to be uniquely possible, the encryption transformation $m\mapsto m^e\bmod n$ must thus be injective over $[0,n)$, which we assume in the following. This implies three facts:

$e\ne0$. Proof: otherwise, all messages $m$ in $[1,n)$ would encrypt to $c=1$. There are more than one such $m$, contradicting injectivity.
$p\ne q$ or $e<2$. Proof: if otherwise, that is if $p=q$ and $e\ge2$, then all $m$ multiple of $p$ encrypt to $0$, since for all $i$ it holds $(i\,p)^e=i^e\,p^{e-2}\,p^2$, hence $(i\,p)^e$ is a multiple of $p^2$, hence $(i\,p)^e\bmod n=0$. There are more than one such $m$, contradicting injectivity.
$\gcd(e,\varphi(n))=1$, which the question asks to prove.

If $e=1$, then $\gcd(e,\varphi(n))=1$ holds. Given fact (1.), we can restrict the proof of (3.) to $e\ge2$, and we do so in the following.

Given fact (2.), $\varphi(n)=(p-1)(q-1)$. Thus
$$\begin{align}
\gcd(e,\varphi(n))=1&\iff\gcd(e,(p-1)(q-1))=1\\
&\iff\gcd(e,p-1)=1\text{ and }\gcd(e,q-1)=1
\end{align}$$
Thus for the proof of (3.) it is enough that we prove $\gcd(e,p-1)=1$ (the same proof applies for $q$, giving the desired result). We do so in the following.

Given that $p$ is prime, the multiplicative group $\Bbb Z_p^*$ (that is the integers $[1,p)$ under multiplication modulo $p$) has $p-1$ elements. It is known to be a cyclic group, thus there exists a generator $g$ with $x\mapsto g^x\bmod p$ a bijection on $[1,p)$, with $p-1\mapsto 1$.

Let $r=\gcd(e,p-1)$. This $r$ divides $e$ and $p-1$. Let $f=e/r$, $s=(p-1)/r$, and $h=g^s\bmod n$. It holds $h^e={(g^s)}^e=g^{s\,e}=g^{f\,r\,s}=g^{(p-1)\,f}={(g^{p-1})}^f$. Hence $h^e\bmod p=1$.

Given fact (2.) and $p$ and $q$ prime, $p$ and $q$ are coprime. Thus by the Chineese Remainder Theorem there exists² $t\in[0,p\,q)$ with $t\bmod p=h$ and $t\bmod q=1$.

It follows that $t^e\bmod p=h^e\bmod p=1$, and $t^e\bmod q=1^e\bmod q=1$. Again by the CRT, it follows that $t^e\bmod n=1$.

It also holds $1^e\bmod n=1$. For RSA encryption $m\mapsto m^e\bmod n$ to be injective, we must thus have $t=1$, therefore $h=1$. Since $x\mapsto g^x\bmod p$ is a bijection on $[1,p)$, and transforms $x=p-1$ into $1$, and $s$ into $h=1$, it must hold $s=p-1$.

By construction $s=(p-1)/r$ and $r=\gcd(e,p-1)$, thus $\gcd(e,p-1)=1$, Q.E.D.

Note: for proper generation of $N$ the condition $p=q$ is extremely improbable, and even if it occurs it leads to vanishingly few $m$ which encryption could not be uniquely deciphered, which is why $p\ne q$ is sometime omitted in the definition of textbook RSA. However when $\gcd(e,\varphi(n))\ne1$, the proportion of $m$ which encryption could not be uniquely deciphered becomes sizable, which is why condition (3.) on $e$ or an equivalent is always required. An argument for this sizable proportion is that there are many generators $g$ leading to distinct $h$, and for each $h$ that we exhibited there are $q$ messages $t$ encrypting to the same $c$.

¹ A standard proof is that if $e\,d\equiv 1\pmod{\varphi(n)}$, then decryption per $m\gets c^d\bmod n$ works for most messages in $[0,m)$, and for all such messages when $n$ is squarefree. The converse does not hold.

² That $t$ is unique and could be computed as $\left((p^{-1}\bmod q)(h-1)\bmod q\right)\,p+1$.


Simulation aborted because the adversary doesn't use the random oracle

Your proof certainly has to work even if the adversary doesn't use the random oracle. One technique that you can try is to begin by proving a separate lemma that if the adversary doesn't ask a certain query first, then it definitely cannot succeed in distinguishing. Then, you proceed to prove the simulation conditioned on it asking this query.

However, if you can't prove this, then you may have to go back to the construction and change it. This reminds me of the double-encrypt-plus-NIZK way of getting CCA-secure encryption in the standard model. In that construction, the NIZK is needed since the simulator can only decrypt one of the two ciphertexts in the reduction, and cannot tell that the other is an encryption to the same. However, if it's not an encryption of the same, then in the real world this would decrypt to invalid. Nevertheless, you can't get rid of the NIZK. The simulator has to know what would happen in the real execution. Sorry for the pessimism.


Is SSL broken? If so, what can I do about it?

I don't think NSA can break the underlying encryption primitives. What they may do is record the whole SSL traffic and decrypt the whole traffic using server private key.
So you can use introduce perfect forward security as the blog article “SSL/TLS & Perfect Forward Secrecy” suggests.
In addition man in the middle can be performed with fake certificates. This is relatively easy and not only NSA, but also a hacker can do this. So if you consider other parties except NSA you should look in to this.


Would a pictographic, phoneme-based, hand cipher be difficult to crack with computer crypt-analysis?

Yes, of course it would deter computers...

... if it were done as substitution and every instantiation of a symbol had a new meaning. This would avoid frequency analysis.

But you are going to be drawing a lot of pictures, and your correspondent is going to need a thick book of hand-drawn symbols if you have a lot of traffic (will each of your hand-drawn symbols look exactly alike each time you draw it?).

Moreover, you now have a physical security problem. And keep in mind that this isn't art class--it's cryptography. But what you propose was widely done in the past, especially in the sixteenth century, and it was serious business.

However, the sixteenth century is over.

If you go ahead anyway, you should not reuse your symbols if they map one-to-one to an individual phoneme (if you only use substitution and not transposition). If you are ambitious and you enjoy drawing, you could create a system in which you map a phoneme to a different pictogram each time, which would surely be effective--but, again, this would all be time-consuming.

Nothing is gained by using phonemes, and perhaps nothing is gained by drawing the symbols by hand (unless you do not trust your computer).  Just use ASCII or extended ASCII.

Let's skip the fact that not only will the language have to be agreed upon, but also the dialect. Doing this for English (at least) is going to become a rat's nest of uncertainty very quickly. Which system of phonemes to use also needs to be determined, and this will not be easy. Will you use IPA?  Will you say there are 42 or 44 phonemes? Which English dictionary will you use to determine/check the pronunciation?  What is the pronunciation? If you look at various English dictionaries, you might be surprised to discover that they sometimes disagree about proper pronunciation.

Anyway, let's consider this ciphertext (plaintext "go up") based on English phonemes:

  β ┤ Ω ♯

Is a computer going to be able to break it without knowledge of your code book?  No.  Without knowledge of your preshared secrets, cryptanalysis is going to hit a wall.

Is this cryptography?  Yes. According to Claude Shannon:

  ... “true” secrecy systems where the meaning of the message is
  concealed by cipher, code, etc., although its existence is not hidden,
  and the enemy is assumed to have any special equipment necessary to
  intercept and record the transmitted signal.

But do we want to go back to this the kind of primitive cryptography? Other methods exist which are much easier and far better--and may offer an integrity check and authentication.


Using a one-time pad with a block cipher

Well, no.

What you are describing is ECB mode of operation. ECB mode of operation is insecure as repeats of plaintext blocks leads to repeats of ciphertext blocks. This is a leak of information so it breaks confidentiality. So even if you would leak less information because of key reuse, you would still leak information if it happens.

Furthermore it is possible to find out if a key is (likely) correct by validating a ciphertext block against partial information within plaintext blocks. To that breaks the perfect secrecy provided by a One Time Pad.

I'll try and explain that last section further.

Note that there aren't $2^n$ possible permutations, there are $2^n!$ possible permutations. To be perfectly secure you should allow each one of them (with the same probability, no less).

That would mean that for any sensible $n$ the key size would grow out of proportion. Furthermore, you would have to have a cipher that would map all those keys to exactly one permutation, something that is not true for usual block ciphers.

So even if you have a key of n bits with m < n bits of known plaintext then it is likely that you can tell with a probability higher than $0.5$ if it is the correct one or not, breaking perfect secrecy for the remaining n - m bits.


What adequate tools are available for estimating entropy?

I'm assuming that you're referring to physical entropy sources, rather than Shakespeare and such.
You can go the compressive approach using strong archivers as discussed elsewhere. However, that will always leave you with a feeling of whether it's accurate enough? And this is an uncommon approach though it works for me.
The standard way, is to simply calculate $H_{\infty}$ based on the most probable value in your data set. Autocorrelation? Remove it. So ironically, your tool is a pseudo random number generator. And ent.
There is the concept of $(\epsilon, \tau)$ entropy per unit time, where $\epsilon$ is the sampling resolution and $\tau$ is the temporal sample lag.  And it goes like this:-

Sample source at $(\epsilon, \tau^{-1})$ per second. Eg. 4 bits @ 10 kSaS.
Perform IID test on sample using permutation testing.
If sample = IID, run ent -c and get ${Pr_{max}}$.
$H_{\infty} = -log_2(Pr_{max})$. Done.
If sample $\ne$ IID, reduce $\epsilon$ or increase $\tau$. Eg. 3 bits @ 5 kSaS.
Goto 1.

Permutation testing is what's done by NIST's 90B ea_iid. Or roll your own. Or use mine. That link has a lot of NIST detail. The reason the bounds are tighter is that you set them yourself as to what constitutes IIDness.  NIST uses p=0.01 and my slow test uses p=0.1 rather than relying on the perceived strength of your compressor.


BLS12-381 is a Type 3 curve, yes. I'm not aware of any difficulty of assuming SXDH for BLS12 curves, and there's no reason BLS12-381 in particular would be special in this respect.
(Almost all pairing-based protocols defined recently are designed for Type 3 curves, and almost all curves defined recently for pairing-based crypto are Type 3. If you come across anything else, it's probably quite an old protocol or curve that hasn't taken into account later cryptographic developments, and you should be quite suspicious of that.)


(How) Can we use HOTP for file encryption?

I had only a quick read through the source, and I am not particularly fluent in C#, so I may have gotten something wrong. That said the process appears to be:

Generate a random encryption key, encrypt the database with it.
Generate (up to six) HOTP tokens, derive a key from those, use that to encrypt the database key.
To read:

Ask for the HOTP tokens, derive the key, check that it matches.
Decrypt the database key, so it can be read.
Generate new HOTP tokens, use those to re-encrypt the database key for  next access.

So by hashing several HOTP tokens you get enough entropy for a strong key – up to ~160 bits if you use the full six tokens with eight decimals each. Additional computational entropy may be added by the iterated hashing process.

By always encrypting the key with a new set of tokens you ensure they are only used once.

The HOTP secret is stored in encrypted form, so it can only be used to derive tokens when a set of matching tokens has been received.


Does "Shattered" actually show SHA-1-signed certificates are "unsafe"?

Yes, SHA1-signed certificates are unsafe.

The SHAttered paper is instructive.  From the introduction:

  The MD-SHA family of hash functions is the most well-known hash function family, which includes MD5, SHA-1, and SHA-2 that have all found widespread use.  This family originally started with MD4 in 1990, which was quickly replaced by MD5 in 1992 due to serious security weaknesses.  Despite early known weaknesses of its underlying compression function, MD5 was widely deployed in the software industry for over a decade.  A project MD5CRK that attempted to find a collision by brute force was halted in early 2004, when a team of researchers led by Xiaoyun Wang demonstrated collisions in MD5 found by a groundbreaking cryptanalytic attack that pioneered new techniques.  In a major development, Stevens et al. later showed that a more powerful type of attack (the so-called chosen-prefix collision attack) could be performed against MD5.  This eventually led to the forgery of a Rogue Certification Authority that in principle completely undermined HTTPS security in 2008.  Despite this, even in 2017 there are still issues in deprecating MD5 for signatures.

Let me draw out the timeline here:

MD4 published.
-
MD5 published.
-
-
SHA-1 published.  Hans Dobbertin reports collisions in MD4 within seconds.
Hans Dobbertin reports collisions in the MD5 compression function.  Cryptographers advise against the use of MD5.  SHA-1 is available as an unbroken alternative.
-
-
-
-
-
NIST publishes SHA-2 in FIPS 180-2.
-
Xiaoyun Wang's team reports collisions in MD5 in a few hours.  It is sheer idiocy to use MD5 at this point.  SHA-2 is available as an unbroken alternative.
Xiaoyun Wang's team reports a $2^{69}$-cost collision attack on SHA-1, later lowered to $2^{63}$.  Cryptographers advise against the use of SHA-1, and even go out of their way to tell engineers to use SHA-2 instead of MD5 or SHA-1.  Cryptographers realize there are sheer idiots out there and try to persuade them to stop using MD5 by making colliding pairs of x.509 certificates, albeit only sharing the same names.
-
Stevens et al. demonstrate chosen-prefix collision attacks on MD5, enabling potential forgery of certificates with different names.
Cryptographers realize that even the operators of certification authorities are sheer idiots and try to persuade them to stop using MD5 by forging x.509 certificates in real time on a real CA.  Some HTTPS CA operators grudgingly acknowledge that there might be a problem.
-
-
CA/Browser Forum writes down first draft of Basic Requirements so web browsers can formalize justification for kicking out incompetent HTTPS CAs.
BLAKE2 is published based on a SHA-3 finalist.  The governments of the United States and Israel are documented to forge code-signing certificates using an independently developed chosen-prefix collision attack on MD5 in the Flame malware deployed in an international incident of industrial sabotage attacking Iran's nuclear program.  This attack was presumably developed before 2007—otherwise, why not use the published attack?
-
CAB Forum votes to sunset SHA-1 next year.
HTTPS CAs whine and demand to push SHA-1 sunset back a year.  NIST publishes SHA-3 in FIPS 202.
HTTPS CAs whine and demand to push SHA-1 sunset back another year.  CAB Forum votes to require random ≥64-bit serial numbers, the first mitigation for chosen-prefix collision attacks on certificates (but not on signatures in general) in eight years since MD5 certificate forgery was demonstrated in practice.
Stevens et al. report collisions in SHA-1.  It is sheer idiocy to use SHA-1 at this point.  SHA-2, SHA-3, and BLAKE2 are available as unbroken alternatives with high confidence from years of analysis.
-
[Update, 2019-05-10: Gaëtan Leurent and Thomas Peyrin report chosen-prefix collisions in SHA-1 at only a few times the cost of SHAttered, a major step toward certificate forgery.]

The technique demonstrated in the SHAttered paper is an identical-prefix collision attack.  Specifically, the attack takes a prefix $p$ and finds two pairs of message blocks $(m_0, m_1) \ne (m'_0, m'_1)$ such that $$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$.  In contrast, the MD5 certificate forgery used a chosen-prefix collision attack, which takes two prefixes $p \ne p'$ and finds middle parts $m \ne m'$ such that for any suffix $s$, $$\operatorname{MD5}(p \mathbin\Vert m \mathbin\Vert s) = \operatorname{MD5}(p' \mathbin\Vert m' \mathbin\Vert s).$$

Can this specific attack on SHA-1 be used to forge x.509 certificates?  Probably not.  Can someone find a chosen-prefix collision attack on SHA-1?  It took one year from first collision to identical-prefix collision attacks on MD5.  It took two more years from identical-prefix to chosen-prefix collision attacks on MD5.  We already have identical-prefix collision attacks on SHA-1.  I hope that we don't need to demonstrate another CA forgery in practice before people will listen to advice to stop using SHA-1.  [Update, 2019-05-10: We now have chosen-prefix collision attacks on SHA-1 at only a few times the cost of the identical-prefix attacks of SHAttered.]

There are mitigations like randomized serial numbers, so maybe for public HTTPS certificates—which by CA/Browser Forum Baseline Requirements 1.5.9 §7.1 must use randomized ≥64-bit serial numbers for all certificates issued after 2016-09-30—it is sufficient that SHA-1 be eTCR, enhanced-target-collision-resistant, which is a much weaker property than collision resistance.

Of course, the CAB Forum requirements also (§7.1.3, p. 44) forbid new certificates signed using SHA-1 starting 2016-01-01 anyway—as is sensible!  Do all HTTPS CAs respect that rule?  I hope so, but if they don't respect it, maybe they won't respect the rule for random serial numbers either.

But there are many other kinds of certificate out there, like the code-signing certificates that were forged for Flame.  Even if you restrict your question to x.509 certificates, e.g., the openssl ca command-line tool—which many people build private CAs out of—suggests and makes it easy to use sequential serial numbers and doesn't advertise a built-in way to randomly generate serial numbers.

P.S.  No matter how many caveats you put on them, questions like this are frustrating to cryptographers because they provide fodder for self-important Hacker News readers to disregard all the context around the specific individual scientific result and instead conclude that the specific individual scientific result does not tattoo a collision on their foreheads and that therefore there's no need to replace SHA-1 yet.


Why is OpenSSL generated 256-bit AES key 64 characters in length?

The key is hexadecimal. So every two characters makes up one hexadecimal byte, which brings the length down to 32 actual bytes. There are 8 bits per bytes, so 8*32 = 256.


How to generate $k$ random numbers that add upto a number $d$ and are coprime with respect to $p-1$

My guess is that the actual requirement is: given

RSA modulus $n$ (odd and square-free)
$\lambda(n)$ per Carmichael's function
Note: $\lambda(n)=\dfrac{(p-1)(q-1)}{\gcd(p-1,q-1)}$ if $n$ is the product of distinct primes $p$, $q$
an RSA private exponent $d$, thus with $\gcd(d,\lambda(n))=1$
moderate $k>1$

draw $k$ positive integers $d_i$ less than $\lambda(n)$ at random except they are such that

$\gcd(d_i,\lambda(n))=1$ for all $i$
$x^d\bmod n\ =\ \left(\displaystyle\prod_{i=0}^{k-1}x^{d_i}\bmod n\right)\bmod n$ holds for all $x$

The condition 1 is equivalent to $\gcd(d_i,p-1)=1$ of the question applied to all primes $p$ dividing $n$. It insures that $x\mapsto x^{d_i}\bmod n$ is a bijection of $[0,n)$, which possibly is desirable in the context of 2.

The question requires $d=\displaystyle\sum_{i=0}^{k-1}d_i$. That's not necessary for 2 to hold. We'll relax that requirement to $d\equiv\displaystyle\sum_{i=0}^{k-1}d_i\pmod{\lambda(n)}$, which is equivalent to 2, gives more choices for the $d_i$, makes the selection simpler.

Update: no matter what, we still must restrict to odd $k$: since $\lambda(n)$ is even, $d$ and all $d_i$ must be odd.

The limit $\lambda(n)$ for the $d_i$ is usual in modern expositions of RSA. It is pointless to choose a larger upper limit, for RSA exponents are equivalent modulo $\lambda(n)$.

Following closely the approach suggested in Daniel's comment, we can

for $i$ from $1$ to $k-1$

pick $r$ random in $[0,\lambda(n)/2-1]$ and set $d_i\gets2r+1$ until $\gcd(d_i,\lambda(n))=1$

compute $d_0=\left(d-\displaystyle\sum_{i=1}^{k-1}d_i\right)\bmod\lambda(n)$
if $\gcd(d_0,\lambda(n))\ne 1$

pick a random $i$ in $[1, k-1]$
pick $r$ random in $[0,\lambda(n)/2-1]$ and set $d_i\gets2r+1$ until $\gcd(d_i,\lambda(n))=1$
proceed at 2

Note: if we fixed $i=1$ in step 3, we'd end up with a slightly biased, but probably tolerable choice.

A comment states

  we need to find the inverse of $d_i\bmod p$

Perhaps that really means computing $e_i={d_i}^{-1}\bmod\lambda(n)$, which allows to verify $y_i=x^{d_i}\bmod n$ because for all $x$ in $[0,n)$ that's equivalent to $x={y_i}^{e_i}\bmod n$.

Beware however that we can't distribute public-key encryption in this way, for knowledge of $n$, $e_0$, $e_1$, $x^{e_0}\bmod n$ and $x^{e_1}\bmod n$ allows recovery of $x\bmod n$ when $\gcd(e_0,e_1)=1$, which is not unlikely.


Security trade-off when using low number of rounds with SHA256

As described in the comment, lets assume the password reset tokens is one-time token generated when a user requests its password.

The PBKDF (salt hashing in the loops) is used to make the password guessing much more expensive in case the database is compromised. The whole problem of PBKDF is based on observation that the user passwords are having low entropy.

  Given that I'm hashing random 256-bit values, would it be safe for me to decrease the number of rounds to as low as 1000?

Lets assume that the password reset token is plain.
The worst case what can happend is that the attacker (having read access) could reuse an existing reset token or create a new one (requesting a new password).

So you need some hashing to hide the original token value, but if the reset token is having enought entropy (is random and long enough) you would be ok with a simple hash. The length and randomness would deny the dictionary guessing process instead of expensive PBKDF function.


Enigma works with the idea of one time pad, it's a machine that automates key generation. In the one time pad, we have to generate a random key with the same length as plaintext but in Engima we make few setups, and the machine creates a that random key.
Here is the enigma procedure

A day key has the form

Plugboard setting: A/L–P/R–T/D–B/W–K/F–O/Y
Scrambler arrangement: 2-3-1
Scrambler starting position: Q-C-W

Sender and receiver set up the machine the same way for each message
Use of message key: a new scrambler starting
position, e.g., PGH

first, encrypt and send the message key, then set the
machine to the new position and encrypt the message
initially, the message key is encrypted twice


Are there parts of a SHA-512 hash that occur more often then others?

In short: Will every possible 'final' password be equally likely?

Yes, we expect that they equally likely. Cryptographic hash functions expected to have a well-distributed output. If you find any bias, you can convert this into an attack. Even there is a tiny bias then that can be used to attack for the hash function.

You seem like you are going to use the SHA-512 hash function as a password generator. Your scheme's weak point will be your master password. One can still write a password cracker for your construction. And Cryptographic hash functions are not designed to be slow, they are designed to be fast. That is why we use iteration on Key Derivation Functions. A better solution using PBKDF2 or Argon2, and use their output. You can use the iteration number as the next try if not occur. So first look at, 100000 then 100001, etc.


When an elliptic curve is said to be "over a field $K$", we mean that the curve is the set of "points" $(x,y)$, where both $x$ and $y$ are elements of $K$, such that the curve equation is fulfilled. The curve equation may have various representation, but a typical one is $y^2 = x^3 + ax + b$ for two constants $a$ and $b$ which are also elements of $K$. An additional formal point, the "point at infinity" (denoted $\mathcal{O}$), which has no $x$ and $y$ coordinates, is also part of the curve.

In cryptography we are mostly interested in finite fields. A finite field is traditionally denoted $\mathbb{F}_q$ for some integer $q$, which is the size (cardinality) of the field; it so happens that when two finite fields have the same number of elements, they are isomorphic to each other, which more or less means that they have the same structure; morally, both are "the same" field, which is why we can afford to say "the field $\mathbb{F}_q$. There exists a finite field $\mathbb{F}_q$ if and only if $q = p^f$ for a prime $p$ and an integer $f\geq 1$. When $f = 1$, i.e. the field cardinality is a prime integer $p$, then the field $\mathbb{F}_p$ is (isomorphic to) the set of integers modulo $p$.

In a finite field $\mathbb{F}_q$, there are $q^2$ pairs $(x,y)$, so the curve cannot contain more than $q^2+1$ points (including the point at infinity), which means that the curve is also a finite set of points. The cardinality of the curve is its size: the number of points it contains (again, including the point at infinity). Actually, the curve cardinality is close to $q$: if we define $t$ such that the cardinality of the curve is equal to $q+1-t$, then it can be proven that $|t| \leq 2\sqrt{q}$ (that's Hasse's theorem).

Roughly speaking, for about half of the $q$ possible values $x$ in the field $\mathbb{F}_q$, there can exist a curve point $(x,y)$, and when there is one, there usually are two. The "two" and the "half" mostly cancel out, and you end up with about $q$ points on the curve.

For practical usage of elliptic curves, we use a conventional generator which is a point $G$ on the curve. That point has an order: the order $n$ of the point $G$ is the smallest integer $n \geq 1$ such that $nG = \mathcal{O}$. There are $n$ points $kG$, for all integers $k$ from $0$ to $n-1$, and these are, collectively, a subgroup of the curve. This implies that $n$ is a divisor of the curve cardinality. We usually look for curves and generators such that $n$ is a big enough prime; if possible, we arrange for the curve cardinality to be itself prime, and then $G$ generates the whole curve (in particular, any point on the curve, except $\mathcal{O}$, can be used as generator).

For real-world encryption on the curve, well, we do not really encrypt. We use Diffie-Hellman. The DH algorithm produces a shared secret value, which happens to be a curve point. The point selection is basically random, but a shared random value is good enough because it can be used as key (after a suitable hashing) for symmetric encryption. There is a name for that combination: ECIES. But some standards just do the DH and then use their own symmetric encryption system (typical of SSL/TLS with the "ECDHE" cipher suites).

ElGamal could also be used, but it would require mapping, in a reversible way, a "message" $m$ into a curve point. This would be interpreting the message as the coordinate $x$ (in $\mathbb{F}_q$) of a curve point, and computing a matching $y$. However, only about half of the $x$ values can be the first coordinate of a curve point, so some "variability" would be needed (some bits which can be adjusted until a possible $x$ is reached), or some other trick (e.g. not using one curve but two curves which complement each other). Since the size of the message $m$ would be severely limited (no bigger than $q$), this is hardly worthwhile, and nobody does that. People use Diffie-Hellman.

The guide to elliptic curve cryptography is a good reading for a practical view on how things are done. The chapter on finite fields can be downloaded for free, so I warmly encourage you to read it first.


Off the top of my head, I see no obvious theoretical reason why a hypothetical Enigma-like rotor machine cipher with publicly known rotor wiring couldn't be secure, even by modern standards.  It would presumably need many more rotors and a much more complex stepping scheme than the WWII Enigma had, but that's just engineering detail.

A basic rotor machine cipher can be described mathematically as consisting of two alternating types of layers: the rotor wiring itself, which is an arbitrary (but fixed) invertible map applied to the symbol being encrypted, and the offset between the rotors, which is a simple linear shift of the symbol space that depends on both the key (i.e. the initial rotor positions) and the position of the symbol within the message.  That is, mathematically, we can write the encryption process as:

$$ \begin{aligned}
x_0 &= p, \\
x_i &= f_i(x_{i-1} +_A s_{i-1}) \quad\forall i \in \{1,\dots,n\}, \\
c &= x_n +_A s_n,
\end{aligned} $$

where $p$ is the plaintext input symbol, $c$ is the corresponding ciphertext output, $n$ is the number of rotors, $+_A$ denotes addition modulo the cipher alphabet size $A$, the invertible function $f_i: \{0,\dots,A-1\} \to \{0,\dots,A-1\}$ denotes the fixed non-linear permutation of the cipher alphabet applied by the $i$-th rotor wiring, and $s_i = s_i(K,t)$ is the relative offset between the $i$-th rotor and the next one at message position $t$ with the initial key $K$ (with $s_0$ and $s_n$ denoting the absolute offsets of the first and the last rotor respectively).

(Note that the abstract rotor machine described above doesn't even try to include various Enigma-specific features like the reflector or the plugboard, since those are really just tricks for squeezing extra encryption complexity out of the limited number of rotors the Enigma had.  With enough rotors, you won't need them.)

Here's a schematic drawing to better illustrate the description above:

Looking at the schematic above, you might note that it looks vaguely similar to various modern block cipher designs, such as a substitution–permutation network like AES.  In fact, we can regard the abstract rotor machine described above as a kind of a tweakable block cipher operating on blocks of one symbol, with the wheel wiring $f_i$ acting as an invertible S-box (applied to the whole block at once, so that an explicit P-box is unnecessary) and the key-dependent stepping scheme serving to $s_i$ mix the initial key $K$ and the per-symbol tweak $t$ with the cipher state between each S-box application.

As far as I know, there exists no general attack on the structure described above even if the permutations $f_i$ are publicly known.  In fact, if I'm not mistaken, with sufficiently many rotors and a sufficiently complex stepping scheme, the abstract rotor machine described above can in principle compute any permutation of the cipher alphabet even if all the rotor permutations $f_i$ are identical and completely trivial (e.g. swapping a single pair of symbols and leaving everything else unchanged).  Thus, it would seem that any attack must necessarily exploit either some weakness in the stepping scheme (or in the number of rotors) and/or the limited size of the cipher alphabet.

For a typical modern block cipher, of course, the alphabet size of a typical Enigma-like rotor machine (corresponding to a block size of about 5 bits) would be utterly insufficient, as an attacker could trivially enumerate the permutation the cipher computes based on just a handful of known ciphertext / plaintext symbol pairs.  On the other hand, a mechanical rotor machine with an alphabet size of, say, $2^{64}$ or $2^{128}$ symbols (like in DES or AES) would be utterly impossible to manufacture.

However, to compensate for its small block size, a rotor machine has one major advantage over typical block ciphers: the rotors rotate.  Thus, each symbol in any given message is effectively encrypted with a different permutation of the cipher alphabet.  With a sufficiently complex stepping scheme, this should effectively scramble the permutation between each encrypted symbol, so that even an attack with access to an encryption oracle will only receive one plaintext/ciphertext symbol pair for each $(K,t)$ pair, and will hopefully have no effective way of correlating these pairs to obtain any useful information about the key (or about past or future messages encrypted using it).

The tricky part, of course, is coming up with such a sufficiently good stepping scheme, especially if you need it to also be simple enough that it could be practically implemented without modern electronics.  That's the part that I will leave as an exercise for the reader. :)


What you are describing is called $(t,n)$-threshold signature, where you need at least $t$ parties (out of a total of $n$) to create a signature. Considering your description, it seems that in your case $t=n$, so it is necessary that all the keys are used for creating the signature.

This answer assumes that you want to verify the signature with a single public key (i.e., $n$ signatures, 1 verification). If you want to use $n$ public keys, then you can just require $n$ independent signatures.


The first claim has three steps to it:

Assumption of Primitivity: We want to make sure that the matrix $A$ isn't such that the function $x\mapsto Ax\bmod q$ (equivalently, $A$ viewed as a linear operator $\mathbb{Z}_q^m\to\mathbb{Z}_q^n$) "misses" most of its codomain. Imagine that $A$ is the all zero's matrix --- then the claim can't possibly be true!

If $q$ were prime we could assume that $A$ is "full rank" and this issue would disappear. We often don't like to restrict to the case that $q$ is prime though (for example, $q = 2^k$ is common in practice), so our matrices become defined over rings-that-aren't-fields, and "rank" can be a slightly problematic construct to work with (In particular, consider the lattice with basis matrix $\mathsf{diag}(2,1,1,\dots,1)$. If $q$ is not prime, this may not be equivalent to the identity matrix, so despite being "full rank" it will not surject).

Instead, we assume that $A$ is surjective as a map. This can be described several different ways in the literature (here it is "the columns generate the codomain", other places the term "is a primitive matrix" is used. When $A$ is a vector one can specify "the GCD of its entries is one"). This ends up being the right analogue of "$A$ is full rank" to use when working over rings-that-aren't-fields like $\mathbb{Z}/2^k\mathbb{Z}$. I believe this notion still works over number fields (so in the RLWE case) as everything can be viewed as an integer lattice still, but am less familiar with this area.
Near-uniformity of Discrete Gaussians mod the lattice: Lemma 2.8 states the following:

  Let $\Lambda, \Lambda'$ be $n$-dimensional lattices with $\Lambda'\subseteq\Lambda$. Then, for any $\epsilon\in(0,1/2)$, any $s\geq \eta_\epsilon(\Lambda')$, and any $c\in\mathbb{R}^n$, the distribution of $(D_{\Lambda, s, c}\bmod \Lambda')$ is within statistical distance of at most $2\epsilon$ over $(\Lambda\bmod\Lambda')$

A useful simplification here is to set $\Lambda  =\mathbb{Z}^n$. Then, this states that for any $n$-dimensional integer lattice $\Lambda'$, that for "large enough $s$" that $(D_{\mathbb{Z}^n, s, c}\bmod \Lambda')$ is within $2\epsilon$ being uniformly distributed over $\mathbb{Z}^n\bmod\Lambda'$, the fundamental domain of $\Lambda'$.

This is "what the smoothing parameter is defined for". The smoothing parameter specifies the "phase transition" between the Discrete Gaussian being non-uniformly distributed over the fundamental domain of $\Lambda'$ (when working mod the lattice of course), and it being very close to uniformly distributed (for a graphical demonstration of this, look at this other question). As long as we take $s$ larger than the smoothing parameter of the relevant lattice, the uniformity follows easily as a consequence.
The quotient group:
It's worth mentioning explicitly what we should "expect $\mathbb{Z}^m/\Lambda^\perp$ to look like". Let $q$ be prime so everything is simpler. Recall that:

  $$\Lambda_q^\perp(A)  = \{x\in\mathbb{Z}^m \mid Ax \equiv 0 \bmod q\}$$

When $q$ is prime, this is just the kernel of the linear map $A : \mathbb{F}_q^m\to\mathbb{F}_q^n$. Then the group $\mathbb{Z}_q^m/\ker(A)\cong \mathsf{im}(A)$ by the first isomorphism theorem (for abelian groups). Of course we're dealing with $\mathbb{Z}^m/\ker(A)$ (no $\bmod q$ upstairs), but this doesn't actually matter --- as $\Lambda_q^\perp(A)$ is always $q$-ary (contains the sublattice $q\mathbb{Z}^m$), we have that all points in $\mathbb{Z}^m$ which differ by a point in $q\mathbb{Z}^m$ will be identified anyway, so we may as well pick representatives for these points and call them $\mathbb{Z}_q^m$, and "continue evaluating the quotient".

I'm under the impression this argument extends to the case of composite $q$ if one makes the appropriate substitutions of "linear algebraic arguments" to "module-theoretic arguments" along the way, but I haven't made the substitutions myself before, and don't feel like going through with it here. If someone has a reference I'd be interested.

Putting it together:

From here everything is fairly mechanical.
We want to analyze the distribution of $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$.
By the second point this is within $2\epsilon$ (in statistical distance) of $\mathsf{Unif}(\mathbb{Z}^m/\Lambda_q^\perp(A))$. By the third point the underlying set of this is (assuming $q$ prime for simplicity) isomorphic to $\mathsf{im}(A)$, so the uniform distribution on the first set is identical to $\mathsf{Unif}(\mathsf{im}(A))$. Then, by the first point we have that $\mathsf{im}(A)\cong \mathbb{Z}_q^n$, so this distribution is simply $\mathsf{Unif}(\mathbb{Z}_q^n)$. In total, we end up with $(D_{\mathbb{Z}^m, s, c}\bmod\Lambda_q^\perp(A))$ being within $2\epsilon$ in statistical distance of $\mathsf{Unif}(\mathbb{Z}_q^n)$, which is the first claim.


Good enough deterministic PRNG based on hashes

A deterministic PRNG is pretty much the same thing as a stream cipher. So you could go with AES-CTR or AES-OFB where available. They're standard, and are much faster than all these HMAC-SHA-512 based constructions.

But if you really want to use a hash, then I'd go with the similar HKDF construction:

Extraction Step:

PRK = HMAC-SHA512("", seed)

Expansion step:

T(0) = empty string (zero length)
T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)
T(2) = HMAC-Hash(PRK, T(1) | info | 0x02)
T(3) = HMAC-Hash(PRK, T(2) | info | 0x03)

Where info is some string describing the purpose of your output(can be empty if you don't use a single PRK for more than one purpose), and you output T(0) | T(1) | T(2) | ...

The standard HKDF only uses a single byte, but if you need longer output, you could use a larger counter, such as a four byte integer.

With your construction, using plain SHA-512 for the first step, and HMAC-SHA-512 for the other steps is problematic. In particular if the seed is longer than 128 bytes it becomes totally insecure. Use HMAC for all steps.

If you use HMAC for every step, your construction essentially becomes OFB mode, except that you use a keyed hash instead of a block cipher.


How did the Koblitz/Menezes papers affect the cryptography community?

My impression (which is limited) is that the most researchers are pretty content with the state of security proofs, and it did not have much impact on changing the research agenda of the community. In fact, a related paper was strongly opposed by leading cryptographers. That is not to say the papers were ignored. They generated lots of discussion and maybe some self-reflection.

They are also, unfortunately, sometimes cited by people who do not really understand the issues and just have an axe to grind against papers being too technical.


Send a symmetric key generated by one user to other users (more than two) using a server

The best way is to keep things simple. Once the key has been generated, keep it on the server and make sure only authenticated users can request the key from that location. Make all the clients request the key from the server.


Naming convention for NIST elliptic curves in OPENSSL

The good thing about standards is that there are so many to choose from.

The P-192, P-224, P-256, P-384 and P-521 names come from the FIPS DSS (Latest version of which is FIPS 186-4):

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

The secp224r1, secp384r1 and secp521r1 names come from SEC2:

https://www.secg.org/sec2-v2.pdf

The prime192v1 and prime256v1 names come from RFC3279:

https://www.ietf.org/rfc/rfc3279.txt

They're all the same curves though.


"128-bit security" or "128 bits of security"?

The term used in the Security level article in Wikipedia is n-bit
 security or for example: 128-bit security level

  In cryptography, security level is a measure of the strength that a cryptographic primitive — such as a cipher or hash function — achieves. Security level is usually expressed in "bits", where n-bit security means that the attacker would have to perform $2^n$ operations to break it, but other methods have been proposed that more closely model the costs for an attacker. This allows for convenient comparison between algorithms and is useful when combining multiple primitives in a hybrid cryptosystem, so there is no clear weakest link. For example, AES-128 (key size 128 bits) is designed to offer a 128-bit security level, which is considered roughly equivalent to 3072-bit RSA.

This NIST spec uses the same term of n-bit security

  SHA-1 does provide the 112 bits of preimage resistance that is needed
  to achieve the 112-bit security strength for HMAC


Is there a cryptographic hash function that can be performed with pencil and paper?

I don't think doing this by hand is the right way to do this. Pencil and paper systems are unreliable because humans just aren't as good at being robots as, well, robots! Most of the work in computing a secure MAC is hugely monotonous and a single mistake, anywhere during the process, could completely destroy any security you thought you had.

If your library computer has web access, then it executes Javascript with very high probability. Javascript is enough to conquer this problem.

Just create a static HTML with some Javascript in it. You have two HTML input fields with a single button. When you click, it computes the $HMAC(site,password)$ using SHA-256 or something, then encode the result as printable characters.

There is the problem of key loggers etc, grabbing your master password but they could just as easily covertly film you as you carry out the computation by hand!

There's a limit to the countermeasures that be deployed when the machine is fundamentally untrusted. However, you can mitigate against key loggers by simply making the master password be entered, character by character, via a dropdown box.


If shared_secret is a plain text password as we are told, then the second method, which sends
   RSA-OAEP(data||shared_secret) || SHA-256(data||shared_secret)
is unsafe.

That's because a guess of data allows to mount an off-line check of the password by comparison to the known SHA-256(data||shared_secret). That's ideal for password cracking. That also applies if we change SHA-256(data) to HMAC-SHA-256(shared_secret, data), which is a way of constructing a MAC from a hash with a security proof/argument.

For the same reason, that construction also compromises the confidentiality of data.

It remains to determine if A sending
   RSA-OAEP(data||shared_secret)
to B (computed with B's public key), and having B decipher (with B's private key) and verify shared_secret, is enough for insuring integrity and authenticity of data; assuming of course, that no adversary could have learned shared_secret.

My answer is: no, that does not give the desired insurance of integrity and authenticity, at least for some possible ways of establishing or using shared_secret. In particular:

If there was any prior use of shared_secret by any party knowing it, that involved sending
  RSA-OAEP(something||shared_secret)
per B's public key, then poof goes the desired integrity and authenticity of data, because an adversary can reuse that cryptogram to abuse B into believing that data is that unrelated something.
That includes if shared_secret is merely used for several iterations of the protocol involving different values of data.
Independently, it is quite possible that the check B makes of that message can be used as an oracle to test shared_secret; if that is a password (as we are told), this is bad (though not nearly as bad as with the other protocol, because that's an online attack). Then, after shared_secret leaked, the sky is the limit.

On the other hand, if shared_secret was a wide secret of fixed length established by XOR of secrets chosen by authenticated parties, and RSA-OAEP(data||shared_secret) was the only time shared_secret is used other than as the key of a symmetric algorithm, then I see no reason why the objective would not be met. This is no insurance.


You should not use a Password Based Key Derivation Function (PBKDF) for this. Instead you need a Key Based Key Derivation Function (KBKDF). You could use for instance NIST SP 800-108 (PDF) or HKDF. Both specify means for key derivation using some kind of context which is used as input for the KDF (e.g. a label or sequence number).

A salt is used in a similar fashion in PBKDF, but a salt has a different purpose than context data. Furthermore, it is not that likely that you need key strengthening which is delivered by the salt and iteration count commonly used in PBKDF's. If your master key is strong enough, then the derived keys should be safe without additional measures. PBKDF's are deliberately slow, KBKDF's aren't.

Note that KDF implementations may not be that widespread. They are however relatively easy to compose using the MAC or HMAC primitives that supply the necessary PRF functionality. If you go that way, don't forget to test against the available test vectors though.

If you go for the NIST defined KBKDF's I would advice for a counter mode KDF based on either HMAC using SHA-256 or AES-CMAC as they are easiest to implement and seem to be the most common implementations in the field.

[EDIT] When using HKDF it is advisable use use a Salt value even if your input key material (the master key) provides a lot of entropy. It is however not required for this use case. Neither do you have to use the extract function of HKDF, but normally you would want to perform it anyway for the sake of compatibility. Basically: only skip the Salt and extract function if you have strong resource constraints.


A pretty good answer to the question can be found here
I try to give a shorter and more precise answer: The Curve25519-standard uses a pretty specific modulo-algorithm. A pseudocode of the algorithm looks like this:
def fastModulo(num, prime):
    # Basecase:
    if num < prime: return num
    if num < 2*prime: return num-prime
    # Split number in upper and lower bits:
    upper = upperBits(num)
    lower = lowerBits(num)
    # calculation:
    factor = differenceToPowerOfTwo(prime)
    nextnum = factor * upper + lower
    # recursion:
    return fastModulo(nextnum, prime)

The algorithm is faster if factor is smaller. So the difference to a power of two is important for the speed of the standard. Therefore the biggest 255 Bit prime was chosen instead of the biggest 256 Bit prime, because a significant speed boost is more important than a non signficiant security boost.


Does encrypting a hash of the message yield a secure MAC?

Yes, your MAC is secure.  It's probably not quite as secure as you're expecting it to be, and it's not a construction I would recommend to anyone, but it should be secure.

Let's start with a simpler variant: $F_K(M) = E_K(H(M))$ where $H(\cdot)$ is a 128-bit collision-resistant hash (say, the first 128 bits of SHA1) and where $E_K(\cdot)$ is a 128-bit block cipher in ECB mode.

This is secure, under the assumption that $H$ is collision-resistant and $E$ is a secure block cipher, as can be shown using standard methods.  Since $E$ is a secure block cipher, it is a secure PRP, which implies that it is a secure PRF (by the PRP/PRF switching lemma).  Now it is known that applying a PRF to the hash of a message yields a secure MAC.

However, this still isn't a very good construction to use in practice.  It offers weaker security than, say, SHA1-HMAC.  Indeed, the authors of SHA1-HMAC explicitly considered something like this and rejected it; instead, they decided to design something new that would be better.  Read the SHA1-HMAC research paper for details (it is very readable and a classic), but concisely, one problem with your scheme is that it is susceptible to offline attacks.  Someone can try to find a collision in the hash function using an offline attack, and if they succeed, they immediately have broken the MAC.  SHA1-HMAC does not have this limitation.

Now I know that's not quite what you proposed, but it's still instructive.  What you proposed is a more complicated version of that scheme, but the complications don't really make it much better; they just it make it harder to analyze its security.

For instance, let's look at the scheme where encrypt the SHA256 hash using AES in ECB mode.  Is this secure?  Yes, it's secure, but less secure than you might expect.  If an attacker has observed the MAC on $m$ known messages, then the attacker knows a set of $2m$ known plaintext/ciphertext pairs for AES; let $\mathcal{P}$ denote the set of known plaintexts for which the corresponding ciphertext is known to the attacker.  Now suppose the attacker picks a new message $M$ (different from any of the $m$ known messages) and checks if he knows enough to predict its MAC.  Let $X,Y$ denote the left and right half of SHA256($M$), respectively.  If $X \in \mathcal{P}$ and $Y \in \mathcal{P}$, then the attacker can predict the MAC on the message $M$ with certainty, which is a break of the scheme.  What's the probability that this happens?  The probability is

$$\Pr[X \in \mathcal{P} \wedge Y \in \mathcal{P}] = \Pr[X \in \mathcal{P}] \times \Pr[Y \in \mathcal{P}] = |\mathcal{P}|^2/2^{256} = 4m^2/2^{256}.$$

So, if the attacker picks a message $M$ at random, he has a $m^2/2^{254}$ chance of being able to guess its MAC.  If the attacker picks $2^{90}$ messages $M$ at random, there's roughly a $m^2/2^{154}$ chance that one of their MAC's can be predicted, which breaks the scheme.  The attacker can do all of those calculations offline.  So, if we consider an attacker who observes the MACs on $m$ known messages and who does $2^{90}$ offline calculations, that attacker can break your scheme with probability $m^2/2^{154}$.  If $m=2^{77}$, this is a break with probability close to 1.

This attack is not a serious problem in practice.  However, it demonstrates that the security level is less than one might expect from a 256-bit MAC.  For this reason alone, I don't recommend your scheme.  Instead, something like AES-CMAC or SHA256-HMAC is a better choice.

The good news is that I would expect that one can prove that this is the best an attacker can do (modelling SHA256 as a random oracle, and assuming the block cipher is secure).  I haven't tried to write out and verify all the details, so take this with a grain of salt, but I fully expect that the proof should work out.

I haven't tried to think about what happens if you encrypt the SHA256 hash using AES in CBC mode.  That seems a bit sketchy; I'm not sure why we'd introduce an extra IV and lengthen the MAC for no apparent reason.  I don't think the construction is of any practical interest, given that better schemes exist, and that the better schemes are well-vetted and plenty good enough in practice.


Explanation of the Fiat-Shamir heuristic

The initial idea of Fiat and Shamir was to eliminate the interaction in public coin protocols (note that public coin means that the random choices of the verifier are made public) and was used to convert three move public coin identification scheme into conceptually simple signature schemes (it has later been proven by Pointcheval and Stern that under the random oracle model such signature schemes provide existential unforgeability under chosen message attacks).

If you apply the Fiat-Shamir heuristic to interactive zero-knowledge proofs you

firstly collapse the protocol rounds which all the small challenge space of $\{0,1\}$ into one round using a larger challenge space (e.g., $\mathbb{Z_p}$, where the size of the message space controls the soundness error) at the cost of only being honest-verifier zero-knowledge, and
secondly you do not longer let the verifier sample the challenge (public coins), but compute the challenge as output of a hash function with input the previous protocol messages. The hash function is modelled as a random oracle (outputs random strings that are not distinguishable from truly random strings), which models the unpredictability of the verifier.

Why public coin? Because it is inherent to the Fiat-Shamir transformation, which basically exchanges the public coins of the original protocol with public coins obtained from the hash function.


Why a key pair is used in OpenSSL ECDSA_sign or ECDSA_do_sign instead of only private key ?

ECKEY object may contain:

Group
Private key
Public key

Both Group and Private key are needed to be able to calculate signature. It is most convenient to use generic ECKEY object (from API perspective), as it easy to e.g. convert between commonly used PKCS#8 PEM encoded EC private keys and ECKEY objects, and because just a BIGNUM would not be sufficient.

It is possible to use ECKEY object that does not have public key field filled in for ECDSA signing. Likewise, certain functions (most notably verify operation, where private key usually is not accessible) can be used with ECKEY that does not private key filled in (i.e., it is NULL).


Can I find a number, such that the its SHA-256 hash is all-0

For any output $z\in \{0,1\}^{256}$ it is very unlikely that there is no input mapping to it, since the input space is astronomically larger than the output space, and SHA256 has been carefully designed as a pseudorandom function. So, most likely yes such an input exists.
The number of trials you need to find such an input (no shortcut better than trying random inputs is known) is approximately $2^{256},$ this is the first preimage problem in hash function theory.


Using NIST SP 800 - 90Ar1 Test Vectors for HMAC_DRBG with Reseeding and AdditionalInput

The other two AdditionalInput are to be used with the Generate function.

Page 47 of the spec describes it.

Step 2 of the algorithm performs:

 If additional_input ≠ Null then (Key, V) = HMAC_DRBG_Update (additional_input, Key, V)

Now, you might wonder why there are two strings AdditionalInput. Well, as described in the test spec there are two calls to the generate function for each test vector, so you have two additional inputs.
Note that only the second output of the generate is printed in the test vector.


Length of password requirement using openssl aes-256-cbc

When using a utility to encrypt data, you are not directly using the password you enter as the encryption key. Instead, the key is passed through a KDF, or Key Derivation Function, which converts it into the appropriate length. This allows you to use a password smaller or larger than the cipher's key size. In the case of OpenSSL, a single iteration of either MD5 or SHA-256 (depending on version) is used.

A very simple example of a KDF (although not one considered secure for these purposes) would be the SHA-256 function applied directly on the input. Your one-letter password is hashed into a 256-bit value which can then be used directly as the key. The same thing happens if your password is longer.

SHA-256("a") = ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

Note that the OpenSSL command line utility is not secure, as it is designed for testing the library's functions. It is not to be used for general purpose encryption. The biggest issue is that the KDF it uses is not slow (it uses only one hash iteration, whereas a secure one like PBKDF2 can use tens of thousands or more), which makes brute force and dictionary attacks far more efficient. However, it has other problems such as the lack of integrity. You should use a tool designed specifically for secure encryption, such as GnuPG (which uses a secure KDF called S2K) with its symmetric encryption functionality.