What are the security implications of multiple hashing?

Multiple hashing, in itself, is not a bad idea.  What's bad is trying to design your own non-standard password hashing scheme, without understanding what features such a scheme needs in order to be secure.

In fact, hashing the password many times can be a very good idea, as long as you do it sufficiently many times.  This is one way to slow down the hashing process, and so make it more resistant to brute force cracking attempts, a technique known as key stretching.  This is something any good modern password hashing scheme should do, and the way many such schemes, like PBKDF2, do it is, in effect, by hashing the password many times.

As for your example of hash(hash(hash(password) + salt) + pepper), this will not, in general, be any weaker than just hash(password + salt + pepper), but it's also not significantly stronger.  To achieve any kind of useful key stretching, you need to iterate the hash at least 1,000 times, and preferably closer to 1,000,000 times (or however many iterations the user is willing to wait for).

Ps. For anyone thinking of designing their own password hashing scheme, or evaluating the security of an existing scheme, here's a quick checklist of the properties such a scheme should, at a minimum, have:

It should not be possible to reconstruct any information about the password directly from the hash.  (This is a very basic requirement.  Even a single application of any cryptographic hash function, like the SHA-2 functions, is enough to ensure this.)
The hash should accept arbitrarily long passphrases, and should depend on every bit of the passphrase.  (Again, this requirement should be obvious, but some very old and/or very badly designed hashing schemes like DES-crypt may fail it.)  If, for the sake of usability, some features of the passphrase (like surrounding whitespace or letter case) are deliberately ignored, the user should be clearly informed of this before they select their passphrase.
The hash should be salted, so that two users having the same password will not get the same hash.  Ideally, the salt should be globally unique and unpredictable; it should certainly not be just the username.  A sufficiently long random string (e.g. 10 or more base64 chars) is OK, but ideally the salt should also comprise other hopefully unique elements (like, say, an SHA hash of the username, server ID and a timestamp) to ensure uniqueness even if the random number generator fails.
In addition to the salt, the hashing scheme may depend on a secret key (sometimes called "pepper").  However, its security should never depend solely on this key remaining secret.
The hashing scheme should be resistant to brute force attacks, meaning that the hash should be slow to compute.  This can be achieved by iterated hashing, as described above, or by other constructions designed for the purpose (as in scrypt).  The slowness should be controlled by an adjustable parameter (and, ideally, should adjust itself to available hardware).  In particular, there should not be any "shortcuts" for checking the validity of a password significantly faster than by the standard method your code uses.  If possible, the hashing scheme should also be designed to be unsuitable for massively parallel implementation (e.g. on a GPU; scrypt is designed like this, PBKDF2 is not).  Also, if possible, in client–server applications, most of the hashing effort should be offloaded to the client (but the server-side part of the hashing scheme should still be secure by itself, even if the client misbehaves).
The users should be encouraged to choose long, randomly generated but easily memorizable passphrases (such as those generated by diceware).  To that end, the user interface may automatically generate and suggest such passphrases to the user.  (If so, care should be taken to ensure that the random number generator used is of high quality, and that the passphrases cannot be captured by an attacker.)  The user should not be forced to comply with inefficient and artificial requirements like "password must contain at least one number", although passwords using a diverse set of characters (including non-ASCII Unicode characters) should certainly not be forbidden (or, worse yet, stripped of such characters).


Salt is not secret. This is the open part of the encrypted data. It should be open to decrypt the data.

Reusing the salt is not good. The whole purpose of salt is to prevent usage of rainbow table. If an attacker has descrypted one text, it should not be easy to use it for other texts. Where as if you reuse the same salt for many texts, it may make sense for the attacker to create a rainbow table because he can then decrypt your multiple texts via the same rainbow table.

To your question, how salt is chosen: As @Swashbuckler said, it should be random. Important: Not once random, but it should be randomly generated for each your text or password.


Should '$a$' be always an integer or can it be a group element itself??

Well, $aP$ is defined to be:

$aP \equiv \underbrace{P + P + \ldots + P}_\text{a times}$

From that definition, we see that this makes sense only if $a$ is an integer; it needs to be a count of the number of $P$'s to add together.


How does hash function in Elgamal signature scheme prevent existential forgery attack?

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack algorithm.

The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything.

Hashing the message before verification requires the attacker, Oscar, to additionally find some data that hashes to his derived message, which is practically impossible.


In fact, if you use the first described password authenticated key exchange protocol (Encrypted Key Exchange, by Bellovin and Merrit, in 1992), it is quite clear that you get forward secrecy for free. Roughly put, this is a Diffie-Hellman key exchange with ephemeral keys, whose messages are then symmetrically encrypted, using the shared secret (the password) as key (this symmetric encryption must be such that decrypting with the wrong password still yields syntactically valid DH public keys). Even if an attacker learns the password, all he can do is to recover the inner DH exchange, that used ephemeral keys.

This is in fact a general property for all PAKE. The point of a PAKE is that both parties have only one long-term secret (the password), so everything else is ephemeral; moreover, since that secret has low entropy and is thus in range of exhaustive search (a "dictionary attack"), a strong PAKE must be such that whenever the attacker tries a potential password, he can never know whether he got the right one. This implies, in particular, that even if the password is revealed after the fact, the key exchange itself must remain impregnable. That password being the only non-ephemeral secret, the property of forward secrecy follows.

Or, said in the other direction: if a PAKE protocol is not forward-secure, and obtaining a copy of the shared password allows unraveling the subsequent data encryption, then that mechanism can be used to "test" passwords (run the break-the-encryption attack for each potential password, see if that yields a key which makes sense); in that case, the PAKE protocol does not fulfill its PAKE properties.

To sum up: contrary to what you fear, you will get forward secrecy because you use a PAKE protocol.

(Of course either party can still do something stupid and, for instance, save the secret key resulting from the PAKE into a file, which then breaks forward secrecy.)


Signal Protocol: What extra features does double ratchet algorithm add to Diffie-Hellman ratchet?

There can be many messages exchanged within the same DH ratchet round. Without the symmetric-key ratchet, all messages encrypted based on the same comprised DH key can be revealed. However, since the symmetric-key ratchet computes a new message key to send or receive each message and deletes old keys (including previous DH results, root keys, chain keys, symmetric message keys, etc.) after each encryption or decryption, the adversary cannot retrieve old message keys to decrypt previous messages if it knows only the current key materials within a DH ratchet round.


Why can't you just clone encrypted data and use it?

Long story short, @GuutBoy is correct. Contactless cards are (in theory, at least), difficult to clone.

Cards with a magnetic stripe are effectively "cloned" by the simple act of reading the magnetic stripe. All of the data on the magnetic stripe is read, verbatim, by a reader. And that magnetic data could be replayed to any third party.

Chip-based cards are not the same; when you read from them, you do not get any of the data on the card. To simplify greatly, you ask the card to authorize you for a charge of a certain monetary value. The card generates a token that authorizes you to charge that amount and hands it to you. You pass this to the card processor. The token cannot be used to perform further charges against the card.

In order to clone the card, it's likely you would have to either take the card for a significant period of time or destroy the card in the process. In either of those cases, at that point you might as well simply steal the card.


Ok, first things first: Your question actually touches on two subjects:

Is it better / as good to sign something with two different half-length keys than with one full-length key?
Is it better / as good to use two half-entropy passwords as one full-entropy password?

The (theoretical) answer to both of these questions is a clear no. However, details matter, which can turn the "no" into a "yes".

To adress the first question: If "half-length" means that each key has a secure keylength to begin with, then yes, this is about as secure as using a full-length key, because each key is unbreakable to begin with, meaning we have "unbreakable" vs "even more unbreakable" at which point other considerations should pitch in. For example it might be easier to ensure correct usage if two keys are forced. It will be harder to extract two keys using side-channels or malware than it will be to extract one.

However, if half-length means that only the full-length key has a secure standard key-length, then this will be completely broken. As an example consider Elliptic Curve keys (such as used by ECDSA in Bitcoin): One 256-bit key is unbreakable right now because you need $2^{128}$ operations to break it, but two 128-bit keys are very much breakable because they require less than $2^{64}+2^{64}=2^{65}$ operations to be broken (because you can re-use parts of the computations).

Now for the specific instance noted in the comments:

  Are you familiar with bitcoin bip39 wallet creation ? My initial
  concern is, if multi-signature wallet created by two accounts with
  both seed of 12 words (128 bits of entropy) is safer or safe same as
  regular single signature account with seed of 24 words (256 bits of
  entropy ) ?

Now this is the question 2) I named above. While yes, this password will only offer 129 bits of security, this is already "unbreakable" at which point we would be discussing about "unbreakable" vs "unbreakable". Now nobody would successfully guess a 128-bit entropy secret, so it has to be stolen. It is harder to steal two secrets (which preferably are at different locations) than it is to steal one secret, so using two keys is actually preferable in this scenario.

  So it would be actually better to set up this account with 2x 24 word
  seed account which will produce 257 bits of [security].

Yes, it would be "better" in a theoretical sense. In a practical sense there's no security gain and all you achieve is making your own life harder by having to remember / type more words. Also see this Q&A on why really long passwords aren't better.

  Out of curiosity, does ed25519 support full security of 256 bits ?

No, Ed25519 has about 126 bits of security. The linked source talks about Curve25519 but can be equally applied to Ed25519 with minimal transformations.

  at some point i've heard that bitcoin developers were saying that it's
  way more secure than Secp256k1 ecdsa

Theoretically no, practically yes. secp256k1 provides the "full" 128-bit security that you would expect and thus is "more secure" than Ed25519. However, Ed25519 is a more modern mode and curve than ECDSA with secp256k1 meaning it is easier to get right and secure against implementation mistakes. This (and the speed bonus) is why it's usually preferred over ECDSA.

  Also - is there any asymmetrical cryptography algorithm with 256 bit
  security, if yes - then why Bitcoin or other crpyotcurrencies are not
  utilising it ?

Yes, if you replace secp256k1 with the P-521 curve, you get about 256-bits of security. However this will also be a lot slower because there are likely less optimizations and the operations are more complex due to larger values. Also see this answer for some discussion on curve sizes larger than 256-bit.

One final note: When I'm talking about "x-bit security" here, I mean that $2^x$ operations are needed to carry out a successful attack. The actual keying material may be bigger than the "security bitlength" which is only the lower bound.


$$(-10+22x+22x^3-22x^6) - 1 = -11+22x+22x^3-22x^6 \equiv 0 \mod 11.$$

When substracting a constant from a polynomial, you do not subtract it from every term, only from the constant term.

If you need a refresher, see addition and subtraction of polynomials.


What do people use non-extractable WebCrypto keys for?

What are the actual use cases for non-exportable keys? Why would people want to go that far while risking key losses?

One of the main ideas of key stores is that access to the keys is minimized; as long as you don't export a key, you can be sure that no other service is using the key.

Don't most people want to be able to reuse and back up their keys, especially since they're used for identity and encryption purposes?

That depends.
Private keys used for decryption you may want to be backed up. Note that the term "exportable" is probably taken from PKCS#11 used for HSM's and Smart Cards. And note that HSM's do often allow for secure backup, e.g. to another HSM.
As for signature generation: consider losing a smart card with a single key. In that case you may simply request a new card. The signatures can still be verified as long as the public key is available (and not revoked because the private key has been compromised).

If #2 is true, and there is no way to securely store extractable keys inside a browser, how do people build a secure app using WebCrypto?

I'm not sure about that. I must say that I find WebCrypto a pretty ill thought out API. To be honest, I think they just copied the exportability part from PKCS#11 / cryptoki.

Finally, isn't storing keys on the browser fundamentally insecure whether extractable or not? Even if the key cannot be exported, a website sign a message on behalf of the user (or decrypt a message intended for the user and send it to their server) without the user knowing, and that's a huge security issue.

The main issue with WebCrypto is establishing trust with the browser; that's nigh impossible even for the server providing the code and pages. Still, you could use it to encrypt with a public key. That could provide some protection against passive attacks against a past TLS session, for instance.


Clarifications regarding ciphers and Nmap scan

Even though I have added the TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA256
  as a cipher in my server, it wasn't available in the Nmap results,
  what might be the reason for this?

Your server probably uses a RSA-based certificate and the second part of the name states "ECDSA" which means that this ciphersuite indicates an ECDSA-based certificate. As none has been found, the server didn't actually offer this ciphersuite.

  As per the doc, the Ciphers marked as "E" is the weak cipher and in
  another way can I consider the cipher marked as "A" as the strong
  cipher?

It would appear that "E" means "practically exploitable if you have enough money / time", as example issues seem to include the use of 3DES which is bad for the small block size or the use of DES which has a easily brute-forced keylength.

"A" here probably means "not practically exploitable if decently implemented", which is the only thing I can come up with as the use of CBC and non-DHE suites have been flagged "A".

  TLS_RSA_WITH_AES_128_CBC_SHA is marked as "A" here, but in some
  discussions, I have observed it is mentioned as WEAK. Is it because of
  the SHA1 usage?

This suite has two main issues. The use of SHA1 (which is used in HMAC), is not one of them.

It uses CBC mode which has been a major cause of worry in TLS in the past and gave rise to many attacks on TLS implementations.
It uses key-transport RSA, that is if your private key leaks from your server (eg because of something like heartbleed), all transcripts of past sessions can be decrypted. This is not the case if a (EC)DHE suite is used.

  if so why this is rated as "A" in NMAP?

Apparently the nmap developers chose a different notion of "good" as most cryptographers / Google did, in that they define anything as "good" that is "effectively unbreakable if decently implemented" whereas cryptographers want more fancy properties like "hard to get wrong" and "still somewhat secure if compromised in the future".

  but the ciphers such as SSL_RSA_WITH_RC4_128 is not available in the
  Nmap output, instead, there are ciphers like TLS_RSA_WITH_RC4_128,
  what is the reason for this?

This is a naming difference. Your implementation chose the prefix to be SSL_, nmap chose it to be TLS_, the objects identified are still the same.


Signature scheme with two private keys, neither derivable from the other

Well, one obvious way to do this would be using RSA with a large 'public' exponent.  That is, it is the traditional RSA sign/verify operation except that, instead of the usual optimization of having a small 'e' value, you would have a large one (a bit smaller than the modulus); and then derive d from e, p and q in the usual manner.

As for the requirement that it has no special structure, the only special structure that either exponent has is that they are odd; any odd value is a potential exponent (note: to avoid biases, it may be advisable to, when generating the p and q values, you exclude values where p-1 (and q-1) have small odd factors).

So, the signing key S would be the value (d-1)/2, and the verification key would be the value (e-1)/2, with the modulus being treated as public data (that is, there is no need to encrypt it).  That this is secure (and you can't derive one from the other) follows directly from the standard RSA assumptions. That it meets requirement 4 follows from the idea that (d-1)/2 can take on any integer value.


Why are there limitations on using encryption with keys beyond certain length?

There are many different cryptography laws in different nations. Some countries prohibit export of cryptography software and/or encryption algorithms or cryptoanalysis methods.

In some countries a license is required to use encryption software, and a few countries ban citizens from encrypting their internet communication. Some countries require decryption keys to be recoverable in case of a police investigation.

Issues regarding cryptography law fall into four categories:

Export control, which is the restriction on export of cryptography methods within a country to other countries
or commercial entities. There are international export control agreements, the main one being the Wassenaar Arrangement. The Wassenaar Arrangement was created after the dissolution of COCOM (Coordinating committee for Multilateral Export Controls), which in 1989 "decontrolled password and authentication-only cryptography."
Import controls, which is the restriction on using certain types of
cryptography within a country.
Patent issues, which deal with the use of cryptography tools that are
patented.
Search and seizure issues, on whether and under what circumstances, a
person can be compelled to decrypt data files or reveal an encryption
key.

Restrictions on the import of cryptography

Countries may wish to restrict import of cryptography technologies for a number of reasons:

Cryptography may increase levels of privacy within the country beyond
what the government wishes.
Citizens can anonymously communicate with each other, preventing any
external party from monitoring them.
Encrypted transactions may impede external entities to control the
conducting of business.
Imported cryptography may have backdoors or security holes,
intentional or not, which allow foreigners to spy on persons using
the imported cryptography; therefore the use of cryptography is
restricted to that which the government thinks is safe, or which it
develops itself.

The Electronic Privacy Information Center and Global Internet Liberty Campaign reports use a color code to indicate the level of restriction, with the following meanings:

Green: No restriction
Yellow: License required for importation
Red: Total ban

Here is List of Countries, each with their level of import restrictions.

and List of Countries with their import/export restrictions details and explanation

Import Limits on Cryptographic Algorithms in Java

Due to import regulations in some countries, the Oracle implementation provides a default cryptographic jurisdiction policy file that limits the strength of cryptographic algorithms.

If stronger algorithms are needed (for example, AES with 256-bit keys), the JCE Unlimited Strength Jurisdiction Policy Files must be obtained and installed in the JDK/JRE.

It is the user's responsibility to verify that this action is permissible under local regulations.


Why is Serpent faster than AES in this benchmark?

AES has fewer rounds than Serpent so AES should be faster.

The number of rounds by itself is meaningless. Some ciphers have a few complex rounds and others have many simple rounds. See my answer to Why does SHA-1 have 80 rounds? for a related explanation.

  There is no speed decrease with bigger key size in Serpent while there is in AES.

The performance is determined by the number of rounds, and not directly influenced by the key-size.

The AES designers decided that 14 rounds are required for a 256 bit security level and 10 rounds for a 128 bit security level. So AES-256 is about 1.4 times as expensive as AES-128. If you add overhead the relative difference becomes a bit smaller.

The Serpent designers decided to use 32 rounds for all key sizes, so performance is the same for larger keys.

  How would you explain the great results for Serpent?

When operating on a single block Serpent is more expensive than AES. This was one of the reasons why Rijndael was chosen over Serpent to become AES.

When operating on multiple blocks in parallel, Serpent profits from an implementation technique called bit-slicing. So Serpent is faster in modes that allow parallelization.

CBC encryption is sequential (You need the previous block of ciphertext to start encrypting a block), so Serpent is slow here. CBC decryption supports parallelism, since you already know the previous ciphertext block at the start, so Serpent is fast here.

XTS always allows parallelism since the encryption/decryption of different blocks is independent. So Serpent is fast in XTS mode.

It's also possible to implement AES using bit-slicing, but it doesn't profit as much as Serpent since it's possible to use lookup tables to produce an implementation of AES that's fast even for a single block. Some people prefer bit-sliced AES implementations since they avoid timing attacks associated with lookup tables.


Here is an example curve with smooth order $E/\mathbb{F}_p:y^2=x^3+ax+b$, generated with Magma.

\begin{align*}
p &= 2^{31}-1 \\
a &= 1456400922 \\
b &= 2005615003 \\
n &= 2^5\cdot 3^7 \cdot 5\cdot 17\cdot 19^2.
\end{align*}

I'd expect that if you are able to run PH, you should also be able to generate some test vectors yourself. The code is

p := 2^31-1;
Fp := GF(p);

repeat
    ct := 0;
    repeat
        a := Random(Fp);
        b := Random(Fp);
        D := 4*a^3+27*b^2;
    until D ne 0;
    E := EllipticCurve([Fp|a,b]);
    F := Factorization(#E);
    for f in F do
        if f[1] gt 25 then
            ct := 1;
        end if;
    end for;
until ct eq 0;


CTR is the most used one with some additional authentication


Security of secure two-party computation with a trusted dealer during offline phase?

This is the so-called Common Reference String (CRS) model, or Correlated Randomness model. A good reference to it is the paper On the Power of Correlated Randomness in Secure Computation.

Secure multiparty computation (MPC) can be expensive (in terms of computational or communication complexity) when a trusted party (the one doing all the computation in secrecy) doesn't exist. Secure MPC is easy when a central trusted party can execute all in secrecy, but this is what everybody doesn't want.

With the CRS we have an interesting model: the creator of the randomness is usually a trusted party. But, this trusted party can be unaware of the computation the parties intend to execute. So the model separate who knows the joint randomness, and who execute the computation. And by supposing a CRS, we can reach secure MPC at a low price. Therefore, the belief that the CRS can't be compromised is a cornerstone of the model: it doesn't compute, but if it leaks the randomness, everything falls flat.


How exactly is signature verification done in SSH v2 authentication?

Yes, the server reconstructs the signature pre-image and then verifies that the signature is valid.
From a purely protocol perspective, I think you effectively answered your own question - the protocol defines the format with which the signature is sent to the server and it doesn't contain the session identifier.  On page 1 it mentions:

When this protocol starts, it receives the session identifier from
the lower-level protocol (this is the exchange hash H from the first
key exchange).  The session identifier uniquely identifies this
session and is suitable for signing in order to prove ownership of a
private key.  This protocol also needs to know whether the lower-
level protocol provides confidentiality protection.

This means that not only does the server already have the session identifier, but is specifically using it to connect the communication channel that is being authenticated to the private key.  Since this exchange hash is secret but tied to the current communication channel (as described in RFC 4432), it makes sense to be cautious about sending it unnecessarily.
Regardless, from a protocol perspective this is sufficient evidence that the signature pre-image must be reconstructed.  But for what it's worth, this can also be seen in the OpenSSH source code where the buffer, b, is constructed using a series of sshbuf_put_* operations and then ultimately passed into sshkey_verify.


How to encrypt a short string and keep the length secret

Instead of saving the padding length as rossum explained, you can also put a length encoding in front of your plain text. A standardized way to do this would be DER encoding (which uses a dynamic number of length bytes), but in your case you could also use a 2 byte short. Then just add 00h bytes padding up to X times the block size, and encrypt using a cipher without padding.

The advantage is that during decryption you can simply discard the bytes, and you don't need no unpadding mechanism, just discard any bytes behind the plain text.

This method is used e.g. in the PKCS#11 standard (for hardware tokens).


Can one passively load-balance HTTPS traffic based on TLS SNI?

The SNI extension is plain text in the ClientHello. This means that it is possible to passively snoop the value and redirect the traffic. This is already used in practice, i.e. haproxy has this feature for several years.


Is this Diffie-Hellman key exchange variant vulnerable to man-in-the-middle attacks?

It is secure against private key exposure but not against replay attacks by Eve. A three-way protocol avoids this, and doesn't need to use timestamps. The description below is from Delfs and Knebl's book Introduction to Cryptography.

  Each user, say Alice, has a key pair
  $(e_A, d_A)$ for encryption and another key pair $(s_A, v_A)$ for digital signatures.

  It is assumed that everyone has access to Alice’s authentic public keys, $e_A$
  and $v_A$, for encryption and the verification of signatures. Define the signature algorithm as the pair $Sign(),Verify(),$ the encryption algorithm is DH, using public key $e_A$, e.g.

  Alice chooses $r_A$ at random, sets $t_1 := (B, r_A)$ (where $B$ represents
  Bob’s identity), $s_1 := Sign_{s_A}(t_1)$
  and sends $(t_1, s_1)$ to Bob.
  Bob verifies Alice’s signature, checks that he is the intended
  recipient, chooses $r_B$ and a session key $k$ at random, encrypts
  the session key with Alice’s public key, $c := E_{e_A}(k)$, sets $t_2 :=
(A, r_A, r_B, c)$, signs $t_2$ to get $s_2 := Sign_{s_B}(t_2)$ and
  sends $(t_2, s_2)$ to Alice.
  Alice verifies Bobs signature, checks that she is the intended recipient
  and that the $r_A$ she received matches the $r_A$ from step 1
  (this prevents replay attacks). If both verifications pass, she is
  convinced that her communication partner is Bob. Now Alice decrypts
  the session key $k$, sets $t_3 := (B, r_B)$, $s_3 := Sign_{s_A}(t_3)$ and
  sends $(t_3, s_3)$ to Bob.
  Bob verifies Alice’s signature and checks that the $r_B$ he received
  matches the $r_B$ from step 2 (this again prevents replay attacks).
  If both verifications pass, Bob and Alice use $k$ as the session key.


What are the public key and output sizes for the four remaining PQC KEM candidates?

Throughout this answer the following conventions are used:

CT = Ciphertext or transmitted output of the encapsulation algorithm
PK = Public key or transmitted output of the key generation algorithm
Cat 1 / 3 / 5 = NIST security categories with the following specification:

Any  attack  that  breaks  the  relevant  security  definition  must  require  computational resources comparable to or greater than those required for key search on a block cipher with a 128/192/256-bit key

The following table gives you the tools to calculate the desired sizes from the given parameter sets - wherever I could figure out the relevant formulas from the supporting documentation PDF.

Scheme
PK size
CT size
Additional Notes

Classic McEliece
$mt\lceil k/8\rceil$
$\lceil mt/8\rceil+\lceil\ell/8\rceil$
$k=n-mt,\ell=256$

Kyber
$12kn/8+32$
$d_ukn/8+d_vn/8$

NTRU
$\lceil(n-1)\log_2q/8\rceil$
$\lceil(n-1)\log_2q/8\rceil$

SABER
?
?
Sizes pre-computed

Unfortunately the SABER documentation was rather unclear on how the sizes are computed (it appears they want one to infer them from the sizes of the packed objects). Fortunately the relevant sizes are already precomputed in a table in their paper.
For NTRU there were two models of computation given, for the sake of comparability I have chosen the weaker ("local") model of computation as the other one didn't have a single named parameter set with category 5 security.
The following table uses the above formulas to compute the sizes for the smallest specified parameter sets that satisfy a given security category as assigned in the supporting documentation of the submission.

Scheme
Cat1 CT
Cat1 PK
Cat3 CT
Cat3 PK
Cat5 CT
Cat5 PK

Classic McEliece
128B
261,120B
188B
524,160B
240B
1,044,992B

Kyber
768B
800B
1,088B
1,184B
1,568B
1,568B

NTRU
699B
699B
930B
930B
1,230B
1,230B

SABER
736B
672B
1,088B
992B
1,472B
1,312B


What if the bitlength of the value evaluated in Barrett reduction is greater than 2k the modulus?

This depends upon how close $\mu/2^{2k}$ is to $1/n$.
In Barrett reduction we approximate the integer $q=[a/n]$ with $q'=[a\mu/2^{2k}]$ in the operation
$$a\mapsto a-qn.$$
If we write $\delta=1/n - \mu/2^{2k}$ then the difference between $a/n$ and $a\mu/2^{2k}$ is $a\delta$ and if this is less than 1 then $q$ and $q'$ differ by at most 1 (which is why Barrett has a possible extra $-n$ step). In general, we know that $\delta<1/2^{2k}$ and so $a\delta<1$ for $a<2^{2k}$. For larger values of $a$, note $q-q'$ can be as large as $[a\delta]+1$ and so the number of surplus multiples of $n$ could be that large. In the worst cases, if $a$ is $m$ bits where $m>2k$, then we could be off by $2^{m-2k}$ multiples of $n$. We can of course apply Barrett iteratively or do more conditional subtracts, but this soon stops being efficient in comparison to direct computation of $q$.
Of course, there are also good very good cases where $\delta$ is small (a lower bound is $\delta\ge 1/2^{2k}n$) and we get good behaviour for a large range of $a$ (up to $a<n2^{2k}$ in the best case).
If you want a more accurate generalisation, you can for example use $\mu=[2^{m}/n]$ and shift $a\mu$ right by $m$ and conditional subtract. This is guaranteed fine for $a<2^{m}$, but be careful how $a\mu$ fits into various word sizes. The size $2k$ is chosen simply because it useful when multiplying two numbers less than $n$ together and reducing modulo $n$.


Is it OK to use a data-encryption key for key wrapping, too?

That's a really bad idea. The general rule is that a symmetric key can either be used for key wrapping or for data encryption, but never for both.

I assume that the keys already in the devices are currently used for processing data. If such keys are now also used for key wrapping, an attacker may abuse the existing protocols and processing facilities and use the device as an oracle to unwrap the new key packages you are about to send. Whether that is really a problem depends on how the key are really used, but in general it is very dodgy and it should be avoided in the first place. If that's not possible, you need to carry out some serious analysis to verify that cannot happen.

Note that the same problem exist even if you derive the actual wrapping key from the existing key material.

The rule is fairly obvious and well known. If you need a reference, you can rely on Clulol's paper "On the security of PKCS#11", Section 2.2.


Exchanging session keys over symmetric-key channel?

With symmetric encryption, any key exchange protocol you run inside the encrypted channel must also be secure when run in plain text, if you want perfect forward secrecy. That means you can only rely on the previously established keys for authentication (you are using authenticated encryption, right?), but not for hiding the new keys.

Diffie–Hellman key exchange is probably the simplest option. Generate random keys, exchange the public parts inside the existing channel and derive the shared secret that you can use to derive any session keys you need. On its own it is vulnerable to MitM, but if you run it inside the authenticated channel you avoid that.

Related: Why do we need asymmetric algorithms for key exchange?


Encrypting text using Caeser cipher in CFB mode

Caesar cipher

You are confusing Caesar cipher with block ciphers.

In Caesar cipher the ciphertext is calculated as

$$c_i = p_i + 3 \bmod 26$$

There is no security in Caesar Cipher. A ciphertext only attack possible, as worst scenario.

CFB Caesar cipher

$c_i = c_{i-1} + 3 + p_i \bmod 26 $, with $c_0 = IV$

And, the decryption;

$p_i = c_i - 3 -c_{i-1} \bmod 26 $, with $c_0 = IV$

Example : $P=lucozade = \{11,20,2,14,25,0,3,4\}$

Let choose $IV = f = 5$

\begin{align}
  c_1 &\equiv IV + 3 + p_1 \bmod 26 \equiv 5 + 3 + 11 \bmod 26 \equiv 19 \text { that is } T\\
  c_2 &\equiv c_1 + 3 + p_2 \bmod 26 \equiv 19 + 3 + 20 \bmod 26 \equiv 16 \text { that is } Q\\
  c_3 &\equiv c_2 + 3 + p_3 \bmod 26 \equiv 16 + 3 + 2 \bmod 26 \equiv 19 \text { that is } T\\
  c_4 &\equiv c_3 + 3 + p_4 \bmod 26 \equiv 19 + 3 + 14 \bmod 26 \equiv 10 \text { that is } K\\
\end{align}


CFB mode has no such length restrictions; it can be used to encrypt an arbitrary length plaintext.

Perhaps you misunderstood what was said.


Does an encrypted random sequence conserve its "randomness"?

Yes. If $r\colon\;\Omega\to X$ is a uniformly distributed random variable, and $f\colon\;X\to Y$ is a bijective function (such as, for instance, a symmetric cipher instantiated with some key), then $f(r)\colon\;\Omega\to Y$ is uniformly distributed as well.

The proof is simple: For all $y\in Y$, we have
$$\Pr[f(r)=y] = \Pr[r=f^{-1}(y)] \text,$$
and the latter probability is independent of the choice of $y$ since $f$ is a bijection and $r$ is uniformly distributed. Hence $f(r)$ is.


First of all, I think I want to correct you at one point; in step 2, you aren't actually that interested in whether the operation is commutative, what you're actually interested in is that the operation is associative, that is, if $(a \oplus b) \oplus c = a \oplus (b \oplus c)$.  In essence, your operator $\oplus$ in step 2 turns out to be a group operation.

Hence, your proposed hash function can be expressed as:

$H(P_1, ..., P_n) = G( \sum_i F( P_i, i ) )$

where:

F is the your so-called 'cipher mimicking counter-mode encryption' (bad terminology, btw) in step 1, which outputs group members
$\sum$ is the group operation sum over all the group members
G is finalization operation in step 3, which takes as input a group member, and outputs the actual hash (and may also take the file length as input; that detail is irrelevant)

Now, assuming that F and G are well-chosen (for example, that it's infeasible to find collisions or preimages in F), the obvious way to attack this construct is to find a collision at the summation step;

for second-preimage on a hash of $P_i$, find a distinct set of blocks $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$
for a collision attack, find distinct sets of blocks $P_i$, $Q_i$ such that $\sum_i F(P_i, i) = \sum_i F(Q_i, i)$

Now, I have good news, and I have bad news.

The good news is that there exists groups where the above problems are NP-hard (!), and even better, one such group is integer addition modulo a large number.  There are also groups where the above problems are easy (such as the group of bitstrings where the group operation is bit-wise exclusive or's), so we'll need to be careful when choosing a group.

Now, the bad news; just because the problem is NP-hard doesn't mean that there aren't shortcuts.  One such short-cut to the second-preimage problem is a square-root attack which works by dividing the blocks $Q_1, ..., Q_n$ into two sets $Q_1, ..., Q_{n/2}$ and $Q_{n/2+1}, ..., Q_n$, collecting sums from both subsets, and scanning the sums for a pair that sum to the target value.  This attack allows us to find a set that sums to the target N-bit value in $\sqrt N$ time; hence the group members must be — at least — twice as big in order to keep the second-preimage problem as difficult as expected.

The update of this observation is that for an $N$ bit hash, the internal sum must be over $2N$ bit values; that means that your $F$ function must generate strong $2N$ bit values, and so ends up being considerably harder to compute than the leaf compression function in a hash-tree construction.


“Randomly derived” is not standard phrasing and I suspect that it isn't what the author meant to write. From context, what is necessary here is to have a distinct key for each message. This can be achieved either by randomly generating a key (I think that's what the author meant to write) or by deriving a key using a key derivation function with a unique input. The second possibility could be called “pseudorandomly deriving a unique key”, because a KDF should be indistinguishable from random if you don't know its secret input, but usually we just say “deriving”.

Since the problem to solve here is the absence of a unique input that's distinct for each message, deriving a key is unlikely to be possible. However, it could be possible if there is a unique input for each message, but it isn't a simple counter, rather it's some long string. With a KDF to derive a key, a unique input of any length is fine. But to derive an 8-byte nonce, a KDF doesn't help, because no matter how it's done, a randomly or pseudorandomly generated 8-byte strings has a $\approx 2^{-32}$ chance of colliding if you generate two of them, increasing as the number of messages increases.

If you derive a key from a password and a salt, that's a pseudorandomly derived key. From the same password and the same salt, you always get the same key. Never use a key that's derived from a password to encrypt actual data: if you ever want to change the password, you'd need to decrypt and re-encrypt the data. Instead, use K only to encrypt a master secret S. Then, on a password change, you only need to decrypt S and re-encrypt it with the new K. Although S can be the key that you use to encrypt data, I recommend adding another level of indirection: it gives you more flexibility. For each message or each conversation, use S as the secret input to an ordinary key derivation function (e.g. KDF1 or KDF2 or HKDF) with two public inputs: a public nonce which is sent with the message (or the first message in the conversation), and a version number which is initially 0 and which you'll increment if you ever want to use S for different things in the future. Once you have that per-message or per-conversation key L, it doesn't matter how it was generated. For each distinct L, if you use L for multiple messages, each needs to have a distinct nonce. If you have different keys L₁ and  L₂, you can use the same nonce twice, once for each key.


What are the safe ways to derive HMAC key using block cipher?

Well, if you are using CBC mode in the recommended way (always using an unpredictable IV), then it turns out to be easy.

With CBC mode, the value that is presented to the encryptor is always a plaintext block exclusive-or'ed with an IV or a previous ciphertext block.  If plaintext blocks are uncorrelated with both the IV and the previous ciphertext block (and the latter just means we didn't deliberately pick plaintext blocks depending on what the previous ciphertext block looked like), that means that what is presented to the block cipher are effectively random values, with no specific value being any more probable than any other.

So, if we need a bit of additional keying data, what we can do is pick an arbitrary block value $B$ (perhaps the all-zero block), encrypt that using the block cipher in ECB mode, and use that $Encrypt_{key}(B)$ value as the HMAC key.  The attacker will gain information on that value only if the CBC mode cipher also happens to present that exact value $B$ while encrypting some text, that is, $B = Plaintext_0 \oplus IV$ or $B = Plaintext_n \oplus Ciphertext_{n-1}$.  However, by the above argument, the values on the right hand side are effectively random, and so if we have a $b$-bit block cipher and are encrypting no more than $2^{b/2}$ blocks (going past that is not recommended because of the birthday bound; you'll be leaking plaintext blocks at that point), then the probability of that happening will be less than $2^{-b/2}$; if $b=128$, this is usually considered sufficiently small.

If you are ultraparanoid about that slight possibility, what you could do is select two blocks $B$ and $B'$ (for example, the all-zeros block and the all-ones block), and use the value $Encrypt_{key}(B) \oplus Encrypt_{key}(B')$.  The attacker will know that your HMAC key is not the all-zeros value; other than that, he will gain information on the value only if both $B$ and $B'$ happen to crop up during the CBC operation; that would be bounded by $2^{-b}$

The above analysis rather assumed that you need only one block of information for your HMAC key; if you happen to need multiple, it is easy to extend this analysis to $Encrypt_{key}(B_0), Encrypt_{key}(B_1), ... , Encrypt_{key}(B_n)$ for preselected distinct values $B_0, B_1, ..., B_n$


Wrong Miller's Weil Pairing implementation?

The reason your implementation fails is most likely because the result of the Weil pairing is 1 in this case, which is the most degenerate case and the one most likely to encounter division by zero errors.

Your elliptic curve $y^2 = x^3 + 3x + 8$ over $\mathbb{F}_{13}$ is cyclic. In this case, $P$ is a generator of $E$ (as is $Q$), and $P$ and $Q$ satisfy the relationship $Q = 4P$, so the Weil pairing is trivial:
$$
e(P,Q) = e(P,4P) = e(P,P)^4 = 1^4 = 1
$$
(The second-to-last equality above follows from the antisymmetry property of the Weil pairing.)

If you want a non-trivial Weil pairing, you need a non-cyclic elliptic curve group, such as the curve from the first example. In cryptography one usually uses an elliptic curve defined over an extension of a prime field instead of a curve defined over a prime field, in order to guarantee that the group is non-cyclic.


Using ECB as RSA encryption mode when encrypted messages are unique?

The Java algorithm string "RSA/ECB/PKCS1Padding", as you already found out, does not implement ECB; it only encrypts/decrypts a single block. The Bouncy Castle cryptographic security provider has a better named algorithm string, "RSA/None/PKCS1Padding", which better indicates that no mode of operation is used. It is likely that "/ECB" was just included to mimic the cipher string for  block ciphers. So you would have to call the cipher "RSA/ECB/PKCS1Padding" multiple times to implement ECB.
"PKCS1Padding" indicates RSA with PKCS#1 v1.5 padding for encryption. This padding is indeterministic - i.e. it uses a random number generator. This explains why each ciphertext block will be different.

To make RSA secure it is required to use a secure padding scheme. If PKCS#1 v1.5 padding is used then there is a significant (11 byte) overhead for each block of plaintext. The padding consists of at least eight bytes of positive random values which explains why the ciphertext is always different even if the same plaintext block is encrypted. If you would use RSA in ECB mode then you would end up losing the padding overhead for each block. That means that the ciphertext would be significantly larger than the plaintext.
Furthermore, RSA operations require a lot of CPU resources. The RSA encryption/decryption operations are based on modular exponentiation with extremely large numbers. Using RSA operations on many blocks will therefore use a lot of CPU time. This is especially true for decryption; encryption has the advantage that the public exponent is generally relatively small. But even RSA encryption will be a lot more CPU-expensive than any symmetric cipher.
To encrypt larger messages you should be using a hybrid cryptosystem where asymmetric (RSA) encryption is paired with a fast, efficient symmetric cipher such as AES. In your case where you encrypt a large amount of numbers it is better to aggregate them in a structure, encrypt the structure using AES and then encrypt the AES key using your RSA public key.

Notes:

OAEP is more secure than PKCS#1 padding. If you choose OAEP then the padding overhead is even larger, making ECB even less efficient;
It is also possible to use RSA-KEM or any other technique to establish the symmetric key - those techniques are however not present in the Java JCA library as of now;
For block ciphers ECB performs the block cipher operation for each block in the plaintext. This is not secure in most situations, independent of the padding used. It is however useful as a lower level operation such as key wrapping of a symmetric key;
Instead of designing your own protocol you could be using container formats such as the Cryptographic Message Syntax (CMS) or Pretty Good Privacy (PGP); both formats already implement a hybrid cryptosystem;
Increasing the key size only to support larger messages is generally not recommended: it would require a huge increase of CPU time during encryption and decryption, only dwarfed by the time it takes to generate the larger RSA key pair;
You may want to sign the message before encryption for additional security (sometimes it makes more sense to sign afterwards, it depends on the use case);
Using all possible bytes for PKCS#1 v1.5 padding comes with a downside: the random padding is only ~64 bits so there is a possibility of a collision with an earlier padding due to the birthday bound - it is better to use an overhead of 19 bytes instead of 11 bytes and have ~128 bits of padding.


Building cryptographic primitives using additive maps?

Yes, take an elliptic curve group $E$ with a point $P$ of prime order $p$ such that the discrete logarithm problem is hard. Then we have a cyclic subgroup $\langle P\rangle$ of $E$ generated by $P$ of order $p$.

Define the map $F: \mathbb{Z}_p \rightarrow \langle P\rangle$ as $F(a):=a\cdot P$ (scalar multiplication) which gives you such a linear map (homomorphism and actually it is an isomorphism) as you have that $F(a+b)=F(a)+F(b)$.  Apparently, if the discrete logarithm problem is hard, this map is one-way. The first addition is in $\mathbb{Z}_p$ and the second addition is the "abstract" addition in the elliptic curve group.

This fact is used in various constructions when instantiating DL based crypto with elliptic curves, such as homomorphic commitments, making ElGamal additively homomorphic (aka exponential ElGamal) etc.


How is the keystream actually generated in AES CTR

How the counter and nonce are related is specified in e.g. NIST SP 800-38A: Recommendation for Block Cipher Modes of Operation Methods and Techniques, Appendix B: Generation of Counter Blocks.

I'll list the second approach, as the first approach - just concatenating all the messages - is stupid and really never used:

  A second approach to satisfying the uniqueness property across messages is to assign to each message a unique string of $b/2$ bits (rounding up, if $b$ is odd), in other words, a message nonce, and to incorporate the message nonce into every counter block for the message. The leading $b/2$ bits (rounding up, if $b$ is odd) of each counter block would be the message nonce, and the standard incrementing function would be applied to the remaining $m$ bits to provide an index to the counter blocks for the message. Thus, if $N$ is the message nonce for a given message, then the $j$-th counter block is given by $T_j = N \| [j]$ , for $j = 1...n$. The number of blocks, $n$, in any message must satisfy $n < 2m$. A procedure should be established to ensure the uniqueness of the message nonces.

So in bytes you would have NNNNNNNNCCCCCCCC where each character is one byte, with the most significant byte to the left and the least significant to the right. Here N is a byte or octet which is part of the nonce and C is part of the counter.

For AES this means a 8 byte (random, serial or otherwise unique) nonce and a 8 byte / 64 bit counter part, containing a statically sized, unsigned big endian encoding.

Most libraries simply allow any kind of scheme and will treat the 16 byte IV simply as initial counter value, and start counting as if it was an unsigned big endian 128 bit value (note that the increase operation is very lightweight and doesn't need any special big-number magic, you just increase the byte values right to left). So basically the counter is considered CCCCCCCCCCCCCCCC. This is kind of dangerous if you decide e.g. to have a larger nonce and smaller counter, as you may overflow the counter into the nonce at the left of it. So in that case you must make sure that the message size limitations are adhered to yourself.

Usually the counter part is initialized to all zero bits, so that the overflow happens only when the entire counter space is used up.

In principle NIST will allow any scheme that produces a unique counter for each block (for the same key). However, due to common usage, you'll likely not find many counter schemes that uses little endian. Sometimes the nonce consists of different fields though, and some implementations also accept smaller nonces as input variable, that are then placed at the leftmost side (and the counter starting at zero).


I was reading about how a one time pad output can be changed by a third party without the receiving person realising. Surely the output at the other end would be garbage?

There's no guarantee either way that it will or it won't.  And in fact, OTPs have one very unfortunate (but by no means fatal) property: an active adversary that flips one bit of the ciphertext will cause plaintext bit at the same position to flip (relative to the true plaintext) when the adulterated ciphertext is decrypted.  The recipient must therefore be able to tell that the decrypted message is wrong from a single bit flip.

One key concept you're missing here is that in cryptography we generally assume that the adversary may have partial knowledge of the plaintext.  Even though we often informally say that the goal of a cipher is to prevent the adversary from learning anything about the plaintexts, what that actually means is preventing them from learning anything more than what they already knew beforehand.

In real life, adversaries may know a lot about the plaintexts that the honest parties encrypt.  Like, for example, they might know that the plaintext is an HTTP request to a certain path within the server, and the values of some but not all request parameters.  And that sort of knowledge might be enough for the adversary to modify the ciphertext to produce a plaintext that the recipient cannot tell is a forgery.

And even if the adversary doesn't have certain knowledge of any part of the plaintext, they might have a bunch of reasonable guesses.  So they might just repeatedly try and modify the ciphertexts according to those guesses and see if they get lucky.  Even if most of the guesses result in garbage at the other end, this is much more dangerous than you're giving it credit for, because nowadays the other end is almost always a computer, not a human being.  Programmers are routinely careless, and computers are really good at blindly following instructions even when the program's preconditions have not been met.  They're also really fast, so the attacker could possibly get to try a ton of guesses before any human being spots it, and even if they don't succeed at their goal they could cause a ton of collateral damage by getting the computer to act funny and damage all sorts of data and business processes.

  Also, could you not generate a crc for the output, encrypt it with the same random sequence so at the other end it could be decrypted and checked to make sure nothing has changed?

Nope, that's easy to defeat.  If you flip one bit of the original message, it's easy to compute the bits that you must flip on its CRC to produce the CRC of the adulterated one.  And this means you can just flip the corresponding encrypted CRC bits in the ciphertext as well.


How can AES-256-CTR be used to construct a CSPRNG?

To improve, use NIST SP 800-90A Rev. 1 Recommendation for Random Number Generation Using Deterministic RBGs, section 10.2.1: CTR_DRBG.

  Does it matter whether one encrypts 65536 bytes of zeroes at a time, or 16 bytes of zeroes at a time (i.e. should the size of the plaintext be no more than the cipher's block size)?

No, however you might wonder if you want to store that much data in memory. Stuff may be evicted from cache and I'm not sure that a 64 KiB buffer is much faster than a 1 KiB buffer.

  Would this scheme stretch the 256-bit + 128-bit entropy (initial AES key + intial AES IV) equally across the 65536 bytes of ciphertext?

Yes it does, but note that that is different than saying you've achieved a security strength of 384 bits.

  How does this translate to each IV sliced out of it? Would each IV have at least 128-bits of entropy or would the entropy of each IV be reduced in some way?

The output of a DRBG should probably not be confused with entropy, which is usually the input of a DRBG. You should be concerned if the output is distinguishable from random, and to that the answer is probably no.

The main difference between your scheme and the NIST version is that you directly use /dev/urandom instead of the INITIALIZE and UPDATE functions. I don't think it will usually pose a problem, but you'd lose any security NIST has put in that scheme.

Note that /dev/urandom is just a block device, the security of /dev/urandom depends strongly on the implementation. Some implementations may return data before enough entropy has been gathered; /dev/random does not have this problem, but can and does block even after enough entropy has been gathered.


This is a tentative guess at answering my own question.

Perhaps the "Fast Prime" method alluded to in the question's citation is that of these two papers (the second polishing the first):

[JPV2000]: Marc Joye, Pascal Paillier, and Serge Vaudenay; Efficient generation of prime numbers, in proceedings of CHES 2000
[JP2006]: Marc Joye and Pascal Paillier; Fast Generation of Prime Numbers on Portable Devices: An Update, in proceedings of CHES 2006 (slides).

Several things match:

The objective of the articles is clearly the one pursued by the technique used.
"Fast Prime" is two words from the title of [JP2006].
"date back to the year 2000" is matched by the publication of [JPV2000].
"use started around ten years later after thorough reviews" allows [JP2006] to get published and reviewed.
From what we know, the prime generator makes heavy use of an $M=P_n\#=\displaystyle\prod_{i=1}^n p_i$, essentially as [JPV2000] and [JP2006] do (their $\Pi$ is $M/2$).

However, the technique in [JP2006] is proven to generate almost random primes, and is not susceptible to the ROCA attack. Hence if my theory is right, there has been a serious implementation goof.

The fact that $65537^a$ occurs makes me wonder if the cause of the goof might be a deliberate attempt, gone horribly wrong, to make it faster to compute $e^{-1}\bmod p$ with $e=65537$; or perhaps just insure that it is defined.

Update: as noticed in comment, Daniel J. Bernstein and Tanja Lange's blog confirms an attempt at implementing [JP2006] gone wrong:

  A related algorithm "GenPrime" was published by Joye and Paillier in 2006. The Joye–Paillier generator, like Lehmer's generator, starts from a new random number $r$ coprime to $L$ and then multiplies repeatedly by a constant $g$ modulo $L$, obtaining $r$ times a power of $g$. This can produce any number modulo $L$, and produces only a slight bias in the resulting primes. The guess was that (company) was oversimplifying and generating merely a power of $g$; this produces far fewer numbers modulo $L$.

  The authors wrote back promptly, confirming that this guess was correct but not revealing more details.


Your wording is rather off, "entropy" is not a verification algorithm, so it is impossible to use it as "data removal verification tool".

To test the (pseudo-)randomness it is possible to use any random data testing tool, such as the testing framework of NIST described in FIPS 140-2. It should be used at least on data filled with zero and the data after the wipe; in that case the original data cannot influence the result.

Note that the tool won't be able to distinguish between random data and data that was designed to look random. You will also need a rather large amount of data - so you cannot use this for single, relatively small file for instance.

Generally single pass overwrites are OK for modern storage devices, but the problem is that the data may be copied somewhere else before it gets overwritten. This is why you should e.g. use the secure erase function on modern SSD's and HDD's to be sure to get rid of the data. Or you can throw away the key of encrypted files so that the data becomes inaccessible rather than destroyed altogether.


Can you create asymmetrical encryption algorithm from symmetrical, without knowing how the algorithm works?

It is not known whether it is possible to construct secure public-key encryption schemes from private-key ones (and by extension, from one-way functions). From Barak's recent survey:

  One could ask if there really is an inherent difference between public-key and private-key cryptography or maybe this is simply a reflection of our ignorance.  That is, is it is not possible to build a public-key cryptosystem out  of an arbitrary one-way function and hence base it on the same assumptions as private-key encryption? The answer is that we do not know

In fact, this is one of the most important open questions in cryptography, along with the question of whether one-way functions exist. So, in practice you can consider that it is not possible, and consult the above for a survey of the known methods to construct public-key cryptosystems.

See also Impagliazzo's "Five Worlds"; your question can be reworded as: is it possible that we live in Minicrypt, the world where one-way functions exist but public-key cryptography does not?


Simple digital signature example that one could compute without a computer?

The main difference between what you want an example for (digital signatures) and secure communication is this: the roles of the public and private keys are reversed.

Also, the content being encrypted is different. For secure communication, the entire message is encrypted. For digital signatures, the message format is irrelevant; you are trying to prove authenticity, not protect message content. Rather, it is a digest, hash, or checksum of the message that is encrypted.

The signature algorithm computes the digest, encrypts it with the private key (known only to the sender), and includes this encrypted digest (the signature) along with the message, to prove its authenticity.

The verification algorithm takes the public key (known to everyone) and uses it to decrypt the signature, as well as computing the hash or digest of the message itself. It then compares its computed hash of the message to the decrypted signature. If they are identical, verification was successful. If not, verification fails.

This is in contrast to security usage, protecting the content of a message. In this case, the message is encrypted using the public key of the recipient, and thus can only be decrypted by that intended recipient who has the matching private key.

So if you have an existing pen and paper example for security purposes, you could just use that same example, reversing the roles of the private and public keys. It's just a matter of understanding the differences in the process.

The only additional piece is the digest or hash. You can choose any mathematical function for this; a checksum or simple equation would be fairly easy to compute by hand. A checksum for example could be used to make a digest this way:

Message: HELLO

We can make it simple: A = 1, B = 2, etc. So we have

  H = 8
  E = 5
  L = 12
  L = 12
  O = 15

The checksum is then computed by multiplying the position of each letter by its value, and summing them all up. So now we have

checksum(HELLO) = (8*1)+(5*2)+(12*3)+(12*4)+(15*5)=8+10+36+48+75=177

Now we encrypt 177. If our encryption method is xor (to simplify things on paper) and our private key is 915, the xor result is

177^915

Simplify using place values:

=(1^9)*100+(7^1)*10+(7^5)

Simplify again using binary:

=(0001^1001) | (111^001) | (111^101)

Now we can easily compute the binary xor operations and add the results:

=1000 | 110 | 010

Back to decimal:

=8*100+6*10+2=862

So we send the message HELLO862 probably along with some way to specify the message length. In most cases the signature might not be distinguishable from the message itself without knowing in advance how long the message is.

Then take 862, the signature, back through the decryption process. In our case we used xor which is a symmetric encryption, so it sort of defeats the purpose, but when using RSA, your private key and public key are two different numbers.


why the SSL is not under the TCP ( Transport layer ) ?

Because SSL can use TCP [1] to transport SSL records, and so SSL relies on TCP as a service.

That is, SSL takes the user data stream, and converts it into a series of records; it then gives these records to TCP to transmit.  On the other side, the receiver's TCP stack gets these records and gives it to SSL to decrypt.

Similarly, TCP takes the data it has been given, and converts it into a series of segments; it then gives these segments to IP to transmit (hence TCP is shown on top of IP).

[1] There's no requirement that SSL has to use TCP; it's just what is used in practice.


Is it safe to encrypt random data using ECB mode?

ECB leaks if blocks are identical. For uniformly random data identical blocks become likely when you encrypt about $2^{n/2}$ blocks with an $n$ bit block cipher. CBC and CTR mode develop similar weaknesses when they encrypt that much data.

=> As long as you encrypt reasonable amounts (up to a petabyte or so) of random data with a 128 bit block cipher, like AES, a passive attacker doesn't learn anything useful from observing your ECB encrypted messages.

Still I see little reason to use ECB when you could use something stronger. You're coupling the security of your encryption to assumptions about the data you're encrypting. If a future version of your software changes the properties of the data, you need to remember that you need to replace the encryption.

Against active attackers you need to add some kind of MAC, either via a generic encrypt-then-mac combination or by using an authenticated mode of operation, like GCM.


Does a high exponent compensate for a low degree of certainty?

Well, no, having a longer exponent really doesn't compensate for low degree of certainty in the RSA key generation.

As you are well aware, the most common method for generating RSA keys involves finding primes by picking numbers, and using a probabilistic method to verify whether those numbers are prime.  These probabilistic methods have a small probability of claiming that a composite number is prime; the certainty factor that some implementations ask for is an indication of how small this error probability should be.

Now, if the certainty factor is too low, the error that might result is that one of the "primes" that are picked isn't really a prime.  This can cause two errors:

The RSA key might not work (or, at least, not consistently).  For example, if the RSA key is used for public key encryption, the private key might not correctly decrypt something encrypted with the public key.
The RSA key might work; this will happen if the 'prime' that got chosen happens to be a Carmichael number; that is, a composite number $n$ for which $x^n = x \mod n$ holds for all $x$.  Now, Carmichael numbers are rare (far rarer than primes), but they do exist.  The potential problem is that Carmichael number often have small factors; if someone notices that the RSA key has a small factor, they might be able to figure out the other factors of the Carmichael number, and thus factor the RSA key.

In both cases, using a larger public exponent won't help.  A larger RSA key also won't help much for case 1 (other than making it less likely that a nonprime will sneak through).  It might for case 2, but I wouldn't be real confident about it.

Now, if the key generation software doesn't allow you to specify a certainty factor, it means that either:

The software has a preset certainty factor build in; one would hope that it is set fairly conservatively (perhaps about as likely as hardware error), but you can certainly ask
The software doesn't use a probabilistic method.  There are deterministic methods of finding primes (such as the Shawe-Taylor algorithm, see A.1.2.1) that are approximately as efficient as probabilistic methods; perhaps those libraries do that.

On the other hand, if you don't trust some key generation software to do the right thing, perhaps you shouldn't use them.  There are some nasty things that a bugged RSA key generation software can do.


1. Before Bob computes $S_B(\mathit{B_K, A_K})$ does he hash $B_K$ and
      $A_K$ using $SHA256$ for example so Alice can hash them herself and compare the hashes?

Generally the signature generation function already includes a hash operation (which might be SHA-256) so requiring a separate hashing step isn't required; it should be configured for the signature generation function.

You could use a separate hash if you don't want to involve the private key early in the protocol - but that's the only reason I can think of.

  2. Does Bob use plain $K$ for encryption or does he use a key
      derivation function like $HKDF$?

Depends.

Generally key agreement (which seems to be missing entirely from your protocol) will generate a shared secret. But this secret may not be well distributed and / or may be too large. So in that case a separate KDF is required.

Note that sometimes a KDF is already configured within the key agreement protocol, so in that case a separate KDF is not required - just like with the hash function for the signature generation algorithm. Of course you could still use a separate KDF to derive more keys or keys with a different size if that's needed in your protocol.

  3. If Bob uses $HKDF$ can he include the salt at the end of the data he
      sends to Alice?

Sure, or the salt can be left out altogether. But HKDF does mention that adding a salt is preferred to achieve high amount of security.


The function SHA-1 is defined on a message $m$ that is a sequence of bits.  It works as follows—this form is named Merkle–Damgård after the people who suggested it in days of yore:

Let $m' = m \mathbin\| 1 \mathbin\| 0^p \mathbin\| \operatorname{length}(m)$ be the result of padding $m$ with a one bit, $p$ zero bits, and a 64-bit message length, so that the length of $m'$ is an integral multiple of 512 bits.
Break $m'$ into 512-bit blocks $m_1, m_2, \dots, m_n$.
Compute $f(\cdots f(f(\mathit{iv}, m_1), m_2)\cdots, m_n)$.

Here $f\colon \{0,1\}^{160} \times \{0,1\}^{512} \to \{0,1\}^{160}$ is the compression function which compresses a 160-bit starting state and a 512-bit block into a 160-bit subsequent state, and $\mathit{iv}$ is the standard initialization vector.

In the case of SHA-1, the compression function is $f(h, m) := E_m(h) + h$ where $E_k$ is the SHACAL-1 block cipher—building $f$ out of a block cipher this way is called the Davies–Meyer construction.

The procedure SHA1_Compress computes $f$, the compression function that SHA-1 is built out of.  Since the $w_i$ are initialized as an output of SHA-1 itself, another way to look at the procedure described here is as an incremental computation of SHA-1—you might use a typical init/update/finalize style of API for this—which periodically treats the current state as a hash itself, which works because SHA-1 has no output filter.


How does the certificate authority generate a signature F?

As far as I understand the question, you ask how a (client-)certificate is issued and generated.

Normally this works like this:

Get an account at the page of the CA. (this is important in later steps)
Validate your identity against the CA, f.ex. using documents like driver-license or passport. Your account will then be listed as "verified as owned by XYZ"
Then you'll create a CSR (certificate-signing-request). This is basically an unsigned X.509 certificate, containing all relevant data about you (=name and your public key)
You send the CSR over to the CA. They will check the your signature on  the CSR to make sure you own the private key associated with the public key. They will also validate that the data in the CSR matches with the data they verified about you.
Now they know that this request is valid. So they'll form a X.509 certificate by taking your CSR and adding their data (where to get CRLs from, validility period, the CA-data,...). Now the certificate is signed by them and the certificate is send back to you. The hash is not stored (as far as I know) and just an intermediate value.

As a formula this would look like this: $Cert=F||S_{CA}(SHA256(F))$.
Where $S_{CA}(X)$ means the signature of the CA on X.

I hope this answers your question. If not use the comments or edit the question.


Actually, the public exponent doesn't have to be prime; any odd number works just fine there.  The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement.

Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make sure that $p-1$ and $q-1$ are both relatively prime to the public exponent $e$.  If the public exponent $e$ happens to be prime, then this is equivalent to saying that $p \ne 1 \pmod e$ and $q \ne 1 \pmod e$; these can be easy tests to fold into the prime search.  If $e$ is composite, then the conditions are slightly more complex -- certainly not impossible to accomplish, to be sure.

That said, the private exponent need not be a prime number.  All the private exponent $d$ is is a number such that $de \equiv 1 \pmod{ \operatorname{lcm}(p-1, q-1) }$; $d$ will always be odd, but there's no specific reason why it can't be (say) a multiple of 3.


Firstly a hash function $H : \{0,1\}^* \to \{0,1\}^{k}$ is preimage resistant if

Given any hash $y$ it is infeasible to find any message $x$ such that $H(x)=y$ .

Now for your case lets assume that one of the functions, say $g$, is not preimage resistance.
Now suppose we have a $h-$hash of unknown message $x$, we know, from the construction of $h$ , that the last m bits of our hash are equal to $g(x)$.

Since $g$ is not preimage resistant we somehow are able to find the value of $x$, which obviously means that we have found the message $x$ that results in a certain $h$-hash


See the page below

https://www.bsi.bund.de/DE/Themen/Kryptografie_Kryptotechnologie/Kryptografie/Zufallszahlengeneratoren/zufallszahlengeneratoren_node.html

I looked at it with the Google translator.

There are quite a few useful links there. If you want full blown code for tests, you'd probably need to write your own.

Related question:

https://security.stackexchange.com/questions/89020/what-comprises-the-ais-31-standard-for-trngs


Small subgroup confinement attack on Diffie-Hellman

The proof provided in the question is correct, but as Chris Peikert pointed out in comments, there is an easier way to prove that $S \in \mathbb{G}_w$:

$ord(\alpha^k) = \frac{ord(\alpha)}{ord(\alpha) \wedge k} = \frac{p - 1}{(p-1) \wedge k} = \frac{p - 1}{k} = w$ so it implies that $\alpha^k \in \mathbb{G}_w$.

As $A^k = (\alpha^a)^k = (\alpha^k)^a$ is a power of $\alpha^k$, it also implies that $A^k \in \mathbb{G}_w$.

In the same way, $S$ is a power of $A^k$ so $S \in \mathbb{G}_w$.


There is not one commonly accepted definition of "cost" in cryptography, other than the definition of "cost" in a common dictionary; this is not jargon or slang to my knowledge.

Here is the most logical definition from Merriam Webster:

  b: the outlay or expenditure (as of effort or sacrifice) made to achieve an object

I'd say that "object" is not a particular object here, it should be read as "objective".

Usually "cost" refers to CPU time, commonly counted using the number of CPU cycles as unit for a particular CPU.

Depending on the context it may also refer to memory usage requirements or even energy expenditure. For hardware it may also relay to transistor count, die size or other costly elements within chip design.


How secure is it to use password as AES key?

Passwords are commonly used for both authentication and encryption. Sometimes this is done securely. "Commonly" is an interesting word here, because passwords are commonly turned into encryption keys in ways that do not follow good security practices, and also passwords commonly do not have enough entropy to be suitable for generating encryption keys.

Generally the term "x is only as good as y" would apply to encryption keys and passwords, such as "key is only as good as password", but the method used to convert the password into the key is more important for the majority of password choices. If you were using a long string of random characters, even MD5 could be acceptable... but you probably are using a shorter password built from real words and phrases. Let me be clear that MD5 is not acceptable to convert passwords into keys.

A 'Password Based Key Derivation Function' (PBKDF) is what is needed to convert your password into a suitable encryption key. There is debate over the specific features and properties a PBKDF should have, but its purpose is to compensate for the poor entropy of commonly chosen passwords, among other things, such as properties of the cryptographic primitives that PBKDFs are built from.

Cryptographic hash functions and block ciphers are commonly used to build PBKDFs, and they do an excellent job, but they are extremely fast and use minimal resources such as memory and cpu cores, which can be a profound advantage to an attacker. Thus a PBKDF is mainly used to slow it down, usually by iterating the primitive thousands or even millions of times. More modern PBKDFs also consume larger amounts of memory, and some may only operate quickly (for verification) by using multiple cores. A 'salt' is used as an input to the PBKDF to prevent the same password from generating the same key unintentionally when used in different situations or by different users. The salt is stored where the password would be processed in order to get the correct key.

Best practice is to use a PBKDF to generate a 'key encryption key' (KEK), then a full entropy random key is used to encrypt the data, and the KEK is used to encrypt that key. That way a password change does not require reencryption of all the data, just the key. The KEK is never stored, only used to encrypt and decrypt the data key. The encrypted data key and PBKDF salt are stored with the encrypted data.

You may not have control over the password a user enters, but you do have control over how it is processed into a key, and you may be able to make recommendations to your users as to good password choices. Attacks only get better, passwords should be as long as possible while still being memorable. Estimating password entropy is difficult, so the PBKDF is extremely important to preventing it from being cracked. If you can accurately estimate entropy you may be able to warn a user that their password may be insufficient.

You should be very open with your users about how you convert their password into a key, it is "common" for secrecy of the method to be associated with extremely bad security practices, and more and more people are starting to realize it (due to an ongoing string of hacks and stolen password databases with lots of press coverage). Additionally, if an individual that understands cryptography can be confident in the security it provides, they may be inclined to recommend the product. I certainly would be.

Note that security is only as strong as the weakest link. If you are using an excellent PBKDF but have poor programming leaking key material into virtual memory, the product is not secure. Do not rely on good cryptographic components to do the work of security for you, it is more complex and difficult than that. It is an entire system. Sorry for the long answer.


Obtain 384 bits from a 256bit MasterSecret

You don't actually need 384 bits of key material.  The IV for GCM does not need to be secret, and may be chosen deterministically, e.g. as an incremental counter.  Thus, you only need 256 bits for the AES key, which you already have.

That said, if you did actually need more key material, you could use any standard KDF to expand your 256 bits.  Since you presumably already have a 256-bit hash function available (for PBKDF2), I'd personally suggest using HKDF-Expand.  Since your master secret is already a pseudorandom bit string, you may safely skip the Extract part of HKDF; see §3.3 of the RFC.

(You could also request more bytes directly from PBKDF2, but this is rather needlessly inefficient.  If you need more than one hash block of output from PBKDF2, it's better to combine it with a key-based KDF such as HKDF.  Technically, you could also use a second PBKDF2 pass with an iteration count of 1 instead of HKDF, but this feels a bit "untidy", as PBKDF2 was not really designed to be used like this.)


Consequences of Flipping a bit in an RSA public key

First note that $e=17=10001_2$ and thus that $e'=11001_2=25$ with $e'$ being the one with the flipped bit. Now note that $M^{e'}\equiv C_1\pmod n$ and $M^{e}\equiv C_2\pmod n$.

Next note how $C_2/C_1\equiv M^{25}/M^{17}\equiv M^8 \pmod n$.
Now compute $M^{17}/M^8\equiv M^{9}\pmod n$ and continue this.
$M^{9}/M^{8}=M \pmod n$ and you are done.

Note that all divisions here are in $\mathbb Z^*_n$, that is, they are multiplications with the multiplicative inverses $\bmod n$.


Is it possible to build a CPA-secure encryption scheme which remains secure even when the encryption of secret key is given?

You're in luck!  Essentially every secure public-key encryption scheme on bit strings that is actually in use already has this property—and, even better, not just IND-CPA but often IND-CCA2/NM-CCA2*—because they can all be factored into a KEM/DEM structure via a hash function $H$ like SHAKE128:†

(KEM) Generate a uniform random $k$ and encapsulation $y$ using $\mathit{pk}$.

Examples:

RSA-KEM: $\mathit{pk} = n$, a large integer; choose $x$ uniformly at random in $0, 1, 2, \dots, n - 1$, and compute $y = x^3 \bmod n$ and $k = H(x)$.

The recipient will recover $x = y^d \bmod n$ with secret knowledge of $d \equiv e^{-1} \pmod{\lambda(n)}$.
RSA-OAEP KEM: $\mathit{pk} = n$, a large integer; choose $k$ and $r$ uniformly at random, compute $a = k \oplus H(0 \mathbin\| r), b = r \oplus H(1 \mathbin\| a)$ (of appropriate bit lengths so they fill a $\lfloor\log_2 n\rfloor$-bit integer), and $y = (a \mathbin\| b)^3 \bmod n$.

The recipient will recover $a \mathbin\| b = y^d \bmod n$ with secret knowledge of $d \equiv e^{-1} \pmod{\lambda(n)}$, and then solve for $k$.
DH-based KEM: $\mathit{pk} = h$, an element of prime order in a group $G$ generated by a standard base $g$; choose $x$ uniformly at random, and compute $y = g^x$, and $k = H(h^x)$.

The recipient will recover $k = H(y^z)$ with secret knowledge of $z$ such that $h = g^z$, so that $h^x = (g^z)^x = (g^x)^z = y^z$.

(DEM) Use $k$ as a one-time key for a one-time authenticated cipher $\operatorname{AE}$ to encrypt the message $m$ as $c = \operatorname{AE}_k(m)$.

Any authenticated cipher works here, like AES-GCM or crypto_secretbox_xsalsa20poly1305; technically the security requirements of a DEM are lighter than AEAD, e.g. you could just use most of $k$ as a one-time pad and the rest as a one-time authenticator key, but it is simplest—and most common—to use an authenticated cipher.
Transmit $(y, c)$, the encapsulation $y$ of the one-time key $k$ and the authenticated encryption $c$ of the message $m$.

The one-time key $k$ is (effectively) independent of the secret key $\mathit{sk}$, so there is no problem with the symmetric encryption $\operatorname{AE}_k(\mathit{sk})$ used here.

This notion of security is sometimes called circular security or key-dependent message (KDM) security.

In 2001, Camenisch and Lysyanskaya defined circular security and proved that $(m, r) \mapsto E_{\mathit{pk}}(r) \mathbin\| (H(r) \oplus m)$ for uniform random $r$ has it if $E_{\mathit{pk}}$ is semantically secure[1].
Independently, in 2002, Black, Rogaway, and Shrimpton defined the slightly stronger KDM security and suggested but could not prove that KEM/DEM hybrid constructions like this would have it[2].
Then in 2014, Davies and Stam finally found formal techniques to prove that KEM/DEM via $H$ generically has KDM security[3].

Skipping the hash $H$, of course, can ruin the security, as in many cryptosystems.  If for some reason you need a system that is secure even without a hash, then the Camenisch–Lysyanskaya and Black–Rogaway–Shrimpton papers are a good starting point for a literature search, with over a thousand papers citing them, from a cursory glance.

Of course, if you need additional structure—e.g., the homomorphic property of Elgamal encryption $(h^r, g^r m)$ for a highly restricted message space—then the answer may be different, because such additional structure is incompatible with NM-CCA2.  But in that case, you'll need to ask a more specific question about your specific additional structure.

* Well, some of the practical ones fail IND-CCA2/NM-CCA2, like S/MIME and OpenPGP, because their designers made foolish decisions leading to EFAIL[4].  But those particular mistakes don't imply problems with circular/KDM security: they are still effectively factored into KEM/not-quite-DEM.

† In academic cryptography jargon, the security here is usually presented in the ‘random oracle model’.  Essentially, this means that we can prove any attacker that doesn't depend on the details of $H$ can be used, if parametrized by $H$, as a subroutine in a procedure to factor large semiprimes, compute discrete logs, etc.  In principle, it could be that particular choices of hash function $H$ could interact with the public-key mathematical structure to enable other attacks; pathological examples have been exhibited[5] where any choice of hash function is insecure.  But these pathological examples are of little consequence in the real world, and they give no reason to doubt the practical security of the KEMs actually in widespread use today like these; these pathological examples are more of an interesting quirk of the formalism than anything else.  More on the random oracle model.


Can you construct a key agreement system from public-key-encryption system?

Yes, you can create a key agreement system from a public key encryption system. Or at least you can create a key establishment scheme using RSA. The term "key agreement" is often used for schemes that are explicitly used for Diffie-Hellman (DH) type of key establishment where the keys are calculated rather than distributed.

The RSA based ciphersuites have been part of TLS up to version 1.2. In this scheme the RSA public key of the server is used to encrypt a random generated on the client. This random is decrypted at the server using the RSA private key and can then be used to derive the session keys from the established secret.

This is a very simple scheme, but it does have some drawbacks because RSA key pair generation is slow and may require a lot of random data. As such it is commonly not used to generate ephemeral (i.e. temporary) key pairs, as it commonly done for DH.

Because of this, the RSA key pair of the server is the static key associated with the certificate of the server. This means that this key must be usable for decryption, while it is really there to perform authentication (signature generation). Generally we try to use the private key for one type of purpose.
If the private key ever leaks then all stored TLS sessions generated with this key can be decrypted with it. In other words: it doesn't provide forward secrecy.

Because of above, the RSA based key establishment has been dropped from TLS 1.3.

And yes, you can also use DH-style key agreement to perform encryption / decryption. IES and - for Elliptic Curve cryptosystems - ECIES is probably the most well known scheme. Simply said, the sender creates a temporary key pair (which is quite fast for DH and ECDH) and uses the private key of it to derive a secret key together with the trusted public key of the receiver. It then sends the temporary / data public key together with the ciphertext to the receiver. The receiver can use this public key together with its own private key to establish the same secret key and decrypt the ciphertext.

As derivation and encryption with a secret key is always required, IES is by definition a hybrid cryptosystem: it mixes the asymmetric DH key agreement with symmetric encryption with the secret key.

Notes:

Personally I use the term "key establishment" in favor of "key exchange" for the establishment of secret keys because it more clearly includes key agreement - where the keys are not distributed by value. Both terms are commonly used to mean the same though.
IES is a description of a scheme rather than a specific protocol; it is not clearly specified how the public key and ciphertext are combined, nor should you take it for granted on how the secret key is used to encrypt the data.
DH is only one form of key agreement: I'm not sure you can answer the question: "can you construct a public key encryption system from a key agreement system" in the generic form. I guess it depends on the key agreement scheme used.


How useful is proxy re-encryption if we end up needing a symmetric key?

Let's look at an example of proxy re-encryption:

User A encrypts a some specific number (which is the message) under their own public key producing ct.
User A sends ct to a proxy.
User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct and recover the number.
Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_B$ or ct$_C$. The proxy must store all three versions of the ciphertext (original + two re-encrypted versions). The requesting users only get their corresponding ciphertext.
Users B and C can use their secret keys to decrypt their corresponding ciphertexts.

There is a size limit at which messages can be encrypted, because ElGamal-style schemes work in cyclic groups which permit only elements (numbers) of a specific size.

If we want to encrypt messages that are larger, we need to use some kind of strategy to wrap the whole large message in an additional security layer. This can be symmetric encryption. When combined with asymmetric encryption is called hybrid encryption.

User A generates a random AES key and encrypts the large message using AES under that AES key producing the symmetric ciphertext ct$_s$. Then the AES key is converted to a number and encrypted under their own public key producing the asymmetric ciphertext ct$_a$.
User A sends ct$_s$ and ct$_a$ to a proxy.
User A determines that users B and C should be able to decrypt ct and uses their public keys and A's secret key to produce two re-encryption keys which are sent to the proxy. The proxy doesn't have any secret key that can be used to decrypt ct$_s$ or ct$_a$ and recover the number or the original message.
Users B and C can identify themselves against the proxy which will use the corresponding re-encryption keys to produce the final ct$_{a,B}$ or ct$_{a,C}$. The proxy must store all three versions of the asymmetric ciphertext (original + two re-encrypted versions) and only one version of the symmetric ciphertext. Each requesting user receives the symmetric and their corresponding asymmetric ciphertext. For example, user B receives ct$_{a,B}$ and ct$_s$.
Users B and C can use their secret keys to decrypt their corresponding asymmetric ciphertexts and then use the recovered numbers to convert them to AES keys and decrypt the symmetric ciphertexts.

When the messages get large, only the asymmetric ciphertext requires additional processing and storage for each additional user. Depending on the used primitives, the asymmetric ciphertext typically has a size of 512 to 4096 bits. The size of the non-duplicated symmetric ciphertext almost the same as the size of the original message (differs only by a constant amount such as at most 256 bit for AES with a sensible mode).

The crucial part is that user A must generate a fresh and random AES key for each message they want to send if the recipients might be different. But this kind of key-wrap method can be used to deduplicate multiple messages further when they are always intended to be received by the same group of users. Then user A must assign each group of users a unique and random AES key (which doesn't leave the system of user A).


How to compute secure sum using secure multparty computation?

In general, there are many techniques for secure multiparty computation. However, the problem of voting is much broader than this, and if you are really interested I suggest looking into the voting literature in depth.

One of the big questions is the model: typically, you cannot run a regular MPC protocol since that requires interaction among all the parties. One solution (which is an old work, but one that I really like), separates between an election service provider and the actual election being held. Actually the work talks about auctions, but a similar idea can be used. See Privacy Preserving Auctions and Mechanism Design.

For more modern work on elections, see Helios (which is the scheme used by the IACR). I suggest looking at Wikipedia - end-to-end verifiable voting for some sources, but note that a lot of research is needed. In general, secure tallying is a tiny part of what is needed for a real election (and the easiest to solve).


Is it safe to use the same password/secret for both VeraCrypt volume and its HMAC?

Assuming your password is secure, yes it is (and I've seen your YouTube channel so I guess that's a non-issue). If you use the same key in both, an attacker would still have to find your key. Since your data this encrypted this requires breaking either the encryption or the HMAC'd hash - even if the hash is broken, they may find a collision but your key would be significantly harder to obtain, since collisions usually don't involve finding the original data.
The point of HMAC is to pair the data with the hash. Someone may tamper with the data, but without the key they can't make the hash collide with the new data. You can use one or multiple keys, it really doesn't matter.
Also, don't forget to store 2 separate hashes. That way, if one has a collision attack developed later on, you can still verify the authenticity using the other. SHA-512 and BLAKE2b? (C'mon, don't tell me forked their official implementation for nothing)
Just kidding, but really... Store the hash with 2 separate algorithms.


Is there a problem with this specific RSA protocol?

The proposed system is close to the safe RSA-KEM, with some exceptions:

The condition $\gcd(P-1,e)=1$ and $\gcd(Q-1,e)=1$ is missing. This must be checked when generating $P$ and $Q$. In the case of prime $e$ (as in the question) this simplifies to $P\bmod e\ne1$ and $Q\bmod e\ne1$.
The random key is 512‑bit, when in RSA-KEM it is typically drawn in $[0,P\,Q)$, thus about 4096‑bit. This is believed (without formal proof) to be without dire consequences since $512\,e\gg4096$. It would however be a total disaster with $e=3$, because taking the $e^\text{th}$ root of the ciphertext would reveal the secret; and I would not caution it blindly for $e=5$.
The random key reportedly is directly used as the encryption/decryption key for some symmetric cipher, without going thru some Key Derivation Function as customary. That's probably OK for most practical ciphers, but in theory we should worry about interactions with properties of the cipher. For example, with an hypothetical cipher where a key and the same shifted by some number of bits give related decryptions, an attacker could take advantage of that to force the legitimate receiver to decipher under a related key.
The generation and uses of $P$ and $Q$ must leave them (and secret derived quantities, such as $\varphi(P\,Q)$, $\lambda(P\,Q)$, any private exponent $d$…) secret, which is easier stated than done.

Assuming $e=2^{(2^4)}+1$ as apparent in the question: ignoring 1 would lead to problem in practice for about one key in $2^{15}$. We'd get away with 2. We'd likely get away with 3, but there's not enough context to affirm it. 4 is standard in RSA crypto.
As usual: for a real system, it's unwise to devise one's crypto.


Which of the following hash functions is collision resistant?

looks like it it is collision resistant, as hashes the message "twice"
Is collision resistant, as a part of the digest is collision resistant.
Is always $0$, so not collision resistant
Collision resistant, as it hashes the message twice and outputs a valid hash of a valid message (the hash of the message)
Always the same. Not collision resistant
Always the same for messages of the same length. Not collision resistant.
Depends on your definition of collision resistant. By itself it's a subset of a collision resistant hash function it is collision resistant if the subset is large enough. So from a theoretical point of view there's no faster attack than brute-force to find a collision, making it a collision resistant 32-bit hash function. From a practical point of view or if you consider it a n-bit hash function with n the digestsize of $H$ it's not collision resistand as one can find one with $2^{16}$ hash function calls.

So the answer is 1,2,4 and maybe 7.


Well, first of all, the answer to your question depends quite a lot on whether your asking about RSA specifically, or public key algorithms in general (of which RSA is one example).

For raw RSA, the core operations to convert between the plaintext $M$ and the ciphertext $C$ is:

$C = (M^e) \bmod N$

$M = (C^d) \bmod N$

where the private key is the pair $(N, d)$ and the public key is the pair $(N, e)$.  At this very high level, it is obvious that the operation is symmetric, and there's no inherent reason why one couldn't "encrypt" with the private key, and "decrypt" with the public (although "encryption" isn't quite the correct terminology if anyone can decrypt it).

However, it is rarely appropriate to use raw RSA as such; RSA has a homomorphic property that can easily leak information.  To avoid such weaknesses, we generally perform padding before and after.  So, for RSA public key encryption, we usually do:

$C = (Pad(M)^e) \bmod N$

$M = Depad( (C^d) \bmod N )$

and for performing signature operations, we do:

$C = (Pad(M)^d) \bmod N$

$M = Depad( (C^e) \bmod N )$

Now, it still looks symmetric; however, the security properties we need for the Padding operation differs between public key encryption and signatures.  For example, we don't care if an attacker can use the homomorphic properties to cobble together a valid looking $Pad(M)^e$ value; we rather assume that he can compute that directly.  However, we have to ensure that, for a signature, he absolutely cannot cobble together a valid looking $Pad(M)^d$ value.

The bottom line: if you want to use RSA to perform signature operations (which is what people usually mean when they ask about 'encrypting with the private key'), you should look at PKCS #1, and do what it says; it's subtler than it looks.

On the other hand (going back to your original question), if you're asking about public key algorithms in general, well, no, you can't usually "encrypt" with the private key; RSA is about the only public key algorithm that can be described as doing signatures that way.  Other algorithms (such as DSA) work entirely differently.