Do I need to generate unique IV for CBC encryption of a file if I encrypt multiple blocks of data?

The question tells CBC is used. I assume that, even though the suggestions to use CTR are good. I consider a block cipher with block size of $b$ octets (e.g. $b=8$ for DES/3DES, $b=16$ for AES), and that the IV used at encryption (possibly random) is stored in the first $b$ octets of the encrypted file, with the ciphertext following.

With CBC, decryption can start at any position in the file. To decipher from octet at offset $n\ge b$ in the enciphered file (offset $n-b$ in the original file), start reading at offset $b(\lfloor n/b\rfloor-1)$, read $b$ octets from there and use that as IV, start deciphering normally but discard the first $n\bmod b$ octets. When $b$ is a power of two (which is most common), in C or similar languages, start reading the IV at offset ((b-1)|n)-(2*b-1) and skip (b-1)&n octets.

In the case of streaming audio or video, this simplifies to: make $n$ a multiple of $b$ (typically, a multiple of 4096 will do), use the first $b$ octets as IV, and play what's deciphered with a player that mutes until it found a sync pattern.


VMAC was a joint work by Wei Dai and Ted Krovetz. It so happens that Wei Dai at that time was also actively working on his own cryptographic library (Crypto++), which of course also includes VMAC.

You can find the test vectors here and the optimized implementation here.

Two examples for VMAC-AES-128 are:

Key: "abcdefghijklmnop"
IV: "bcdefghi"

Message: ""
MAC: 472766C70F74ED23481D6D7DE4E80DAC
Message: "abc"
MAC: 4EE815A06A1D71EDD36FC75D51188A42


Generating RSA signature, by manipulating shorter message signatures?

We notice that $M=k\cdot m$ with constant $k=2^{512}+1$. Hence the signature $\mathcal S(m)$ of $m$ is $\mathcal S(m)=k^d\cdot m^d\bmod N$.

It follows that for any valid messages $m_0$ and $m_1$ with $m=m_0\cdot m_1$ a valid message, we have $\mathcal S(m)\cdot\mathcal S(1)\equiv\mathcal S(m_0)\cdot\mathcal S(m_1)\pmod N$.

Hence, when we can write $m$ as $m_0\cdot m_1$ with $m_0>1$ and $m_1>1$, we can obtain the signature of $m$ by asking to the server the signature of $m_0$, $m_1$, and $1$. We can then compute $\mathcal S(m)$ as $\mathcal S(m_0)\cdot\mathcal S(m_1)\cdot\mathcal S(1)^{-1}\bmod N$. The last term of the product is obtained by modular inversion modulo $N$, using e.g. the half-extended Euclidean algorithm.
Note: that solution was found by the OP, based on a (strong) hint.

Given the server's limitation, we can get $\mathcal S(m)$ for any composite $m\in[4,2^{504}($, using three oracle queries (or just two when $m$ is a square). We can most often pull a factor $m_0$ using trial division, Pollard's Rho, ECM (all in GMP-ECM). We need GNFS in some difficult cases (e.g. CADO-NFS or Msieve, perhaps as packaged as FaaS).

With the "lengh" of a message counted in bits, I see no solution for prime $m$, or for $m=1$.

If the "lengh" of a message was counted in bytes excluding leading zero bytes, and for those $m$ such that $2m$ has the same length as $m$, then we can use $\mathcal S(m)\,=\,\mathcal S(2m)\cdot\mathcal S(1)\cdot\mathcal S(2)^{-1}\bmod N$ for $m>1$, and $\mathcal S(1)\,=\,\mathcal S(2)^2\cdot\mathcal S(4)^{-1}\bmod N$ for $m=1$. That still leaves quite a few problematic $m$, such as $131$ and $2^{504}-503$.
Note: We have $S(0)=0$ with no query for $m=0$.
Note: $k=F_9$ where $F_m=2^{(2^m)}+1$. The factorization of Fermat integers is well-studied, and it has been known since 1903 that $2424833$ divides $F_9$. But I do not see that it helps.


Non interactive ZKP that encrypted additive elgamal message is in set of valid messages

The standard solution is to use a proof of encryption of zero, coupled with an or proof and a careful choice of ciphertexts.

A proof of encryption of zero is a proof that the decryption of a ciphertext is zero. For ElGamal, this is typically done using a proof of equal discrete logarithm. Recall that an encryption of zero is of the form $(x,w) = (g^r, y^r g^0)$, where $y$ is the public encryption key, so all you need to prove is that $\log_g x = \log_y w$. (This equality of d.log. proof is standard, I believe it is called Chaum-Pedersen or something. It essentially amounts to a Schnorr proof in a carefully chosen group.)

An or proof allows you to prove that one out of several claims is true. In this case, we consider the claims that several different ciphertexts are encryptions of zero, though only one will be. (Again, this is a standard technique for sigma protocols, which the above proof of encryption of zero is. It dates back to the 90s.)

Now, which ciphertexts do you apply the or proof to? You want to prove that $(x,w)$ is an encryption of $v_1$, $v_2$, ..., or $v_L$? Then you apply the or proof to the ciphertexts $(x,w g^{-v_1})$, ..., $(x, wg^{-v_L})$. If the encryption is valid, one of them will be an encryption of zero, allowing you to complete the or proof.


Why can't we find $d$ if we know $e$ and $n$ in RSA?

There are "hidden unknowns" in the notation. Suppose that $n$ is the modulus, $e$ the public exponent, $d$ the private exponent. Given a message $m$, its encrypted value is $c = m^e \bmod n$ (I am ignoring padding here), and you can certainly choose a message $m$ and compute $c$ given the public elements $e$ and $n$ (that's how RSA encryption works). Now, you might want to find $d$ by solving the following equation:
$$ c^d = m \bmod n $$
with only $d$ being unknown.

When working with real numbers, an equation of the form:
$$ a^x = b $$
for given values $a$ and $b$, is solved as:
$$ x = \frac{\ln b}{\ln b} $$
and you could imagine that "solving RSA" is just a matter of computing logarithm with the required precision.

However, this would neglect an important part, which is somewhat hidden in the notation. When we work "modulo $n$", we are actually having the following:
$$ c^d = m + kn $$
for the known ciphertext $c$, message $m$ and modulus $n$, unknown private exponent $d$, and unknown integer $k$. At that point, you have a single equation with two unknowns, and the usual tools of analysis with real numbers (e.g. logarithms) won't help at all.

In all generality, RSA is expressed in algebraic things such as rings of integers modulo $n$, and all equation solving activities in such things have their own rules, quite distinct from what you may have learned with real numbers. Obtaining $d$ from $e$ can be done relatively easily when $n$ is prime, but, of course, the crux of RSA is that $n$ is not prime.

We do not have any proof that factoring $n$ into its factors is really required to recover an unknown plaintext from the ciphertext. We do know that recovering the private exponent $d$ is equivalent to factoring $n$ (i.e. if you factor $n$ you can easily obtain $d$ from $e$, and if you somehow obtained $d$ and $e$ you can easily factor $n$); but there could be a method by which a ciphertext can be decrypted without revealing the private exponent itself. Right now, factoring $n$ is the best attack we know of; and factoring big integers is a problem that has been studied for quite some time (more than 2500 years, in fact), and the only sure thing we know is that there is no obviously easy solution. There might be an efficient factoring method, but it is definitely not obvious.


Problem re-statement and notations: we know three 2048-bit RSA public moduli $N_1$, $N_2$, $N$, of unknown factorizations $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, with $p_1<q_1$, $p_2<q_2$. We additionally know that $p$ is the smallest prime at least $(p_1+p_2)/2$, and $q$ the smallest prime at least $(q_1+q_2)/2$. Can we use that to help finding $p$ and $q$?

The quantity $N^2/(N_1\cdot N_2)$ reveals something about $p_1$ $p_2$ $q_1$ $q_2$ that we had no way to know without $N$. But there's no reason that this quantity would be strongly revealing of $q_1/p_1$ or $q_2/p_2$.

If we ignore the small increments to the next prime, and the Diophantine aspect of things, we have only 5 equations (ignoring inequalities: $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, $p=(p_1+p_2)/2$, $q=(q_1+q_2)/2$) among 6 unknowns ($p_1$ $q_1$ $p_2$ $q_2$ $p$ $q$), with 4 unknowns randomly seeded in a large interval and the other two also varying in a large interval. Given these, $q/p$ (or $q_1/p_1$, $q_2/p_2$) can still vary widely and can't be closely estimated, which would have enabled a Fermat-like factorization.

Thus as far as I can tell: no, we do not know how to find $p$, $q$ much easier than by factoring one of $N_1$, $N_2$, or $N$.


Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function?

I would recommend against using ONLY 15-bits as a key for your encryption algorithm. A key size that small can be broken via brute force by any standard machine. There's a reason that AES (where the key can be 128 bits, 192 bits, or 256 bits) or SHA-256 are so widely used. The extended key lengths of those algorithms add security against brute force attacks from adversaries.


What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions)

Assume $x$ and $r$ are bit strings of same length and $x_i$ and $r_i$ denotes the $i$-th bit of $x$ and $r$ respectively. The operation performed between $r_j,x_j$ is multiplication which is equivalent to AND ($\wedge$) as they can both only take the values $1$ or $0$.

Generally any large symbol like $\displaystyle\sum_jf(j)$, $\displaystyle\bigwedge_jf(j)$ and $\displaystyle\bigoplus_jf(j)$ applies the operation denoted by the large sign "between" each iterated value of $f(j)$, resulting in $\displaystyle\sum_jf(j)=f(j_1)+f(j_2)+\dots$, $\displaystyle\bigwedge_jf(j)=f(j_1)\wedge f(j_2)\wedge\dots$ and $\displaystyle\bigoplus_jf(j)=f(j_1)\oplus f(j_2)\oplus\dots$.

So the formula you gave can be read as follows:
$$b(x,r)=\displaystyle\bigoplus_{j}x_jr_j=\displaystyle\bigoplus_{j}x_j\cdot r_j=x_0r_0\oplus x_1r_1\oplus \dots=(x_0\wedge r_0)\oplus(x_1 \wedge r_1)\oplus\dots$$.


security for PRF when key is changed often

Yes, this is secure since the keys are chosen randomly. Remember that even in the "traditional" PRF game, the adversary can generate keys at random, so the output of F on past keys does not help him (since he can generate such outputs anyway).


Rewinding is used in all sorts of interactive protocols, but it's perhaps easiest to understand it for a zero-knowledge property.

In proving zero-knowledge, we consider a cheating verifier interacting with an honest prover. The prover knows something that the verifier doesn't (say, the factorization of an RSA modulus), and we worry that by cheating, the verifier could gain some information.

The zero-knowledge property means that "whatever the verifier outputs from this interaction, he could have generated without interacting at all". If that's true, then the interaction must not have conveyed any meaningful "knowledge" to the verifier.

So how do we prove the statement in quotes? We say: first suppose you have a cheating verifier $V$. When $V$ talks to an honest prover, it outputs (a distribution of) some transcript $t$. We have to show how to sample the same (or very close) distribution of $t$, without talking to any honest prover. It's not likely that we can analyze the code of $V$ to "figure out what it's doing." Instead, we have to treat $V$ as a kind of black-box. Recall that $V$ is designed to operate in an interactive fashion, so we have to feed protocol messages into $V$, pretending to be the honest prover.

We might feed into $V$ a simulated "message 1" from the prover, and then later a simulated "message 2". Then, after seeing how $V$ responded, we might go back to a previous internal state of $V$ and feed in a different simulated "message 2" -- that's rewinding. We can rewind and invoke $V$ many different times, as long as we are careful to spend only polynomial time overall (assuming $V$ itself is polynomial-time).

BTW, there are some security frameworks (e.g., Universal Composability) which do not allow rewinding.


Equal length of primes in paillier cryptosystem

In your question, you already pointed out, that the necessary condition is

  More generally largest prime minus one does not consists of smallest prime as a prime factor

therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient way, anyway, it should be efficient enough for key generation. The main drawback for efficiency would occur if you repeatedly generate unsuitalbe keys, but the probability of that would depend on the length difference you allow for the two primes.

However, in general I think that the security of the scheme depends on the size of the smallest prime, however, the efficiency depends on the size of the obtained modulus $N = pq$, therefore it is probably reasonable to just use equal size primes for the best security and efficiency. Hence, I would guess that the main reason for noting that this property can be ensured by taking equal length primes, is to make sure that no additional work is required to check this during key generation.

I can not point out any schemes that definitely require equal length primes.


Error correcting codes that are indistinguishable from random

The actual message n is encrypted by a symmetric encryption scheme using some shared secret

The symmetric encryption is keyed by what key?  Is it something that the encryptor picks?  If so, how does it get to the decryptor (as the decryptor would need it before he can attempt a decryption).  Is it something that both sides share?  If so, how is this 'public key encryption' (which typically assumes that the encryptor has access only to publicly available information)?
  And, if you do have a shared symmetric key, what are you bothering with asymmetric crypto?

On the other hand, might I suggest considering thinking about this 'indistinguishability from random' option (and why it is a requirement)?  In general, we usually don't need something that is literally indistinguishable from a set of random bits (some cases do arise; they're comparatively rare).  Instead, it is generally enough to have 'indistinguishable from a random selection from a specific set' (and it doesn't matter what that set it); that formulation preserves the IND-CPA property we are typically interested in.  And, if you just generate the 256 bit indistinguishable-from random word, and then apply your error correcting code to it, this set becomes 'the set of all valid code words in your error correcting code', which is enough for most purposes.

I had to put in some cavaet language in there, because there are some uses that really do require 'indistinguishability from a set of random bits'; what is your use case?


Many ABE schemes support Threshold Cryptography in the sense that the policy that is used to share a random secret supports threshold gates. This is also not limited to Ciphertext-Policy ABE. Key-Policy ABE schemes also support threshold policies.

The threshold policy is usually written with the of operator such as

  2 of (attribute1, attribute2, attribute3, attribute4)

or more complex examples such as

  2 of (a1, a2, a3, (a4 and a5 and (a6 or a7 or a8)))

The paper you linked to (BSW07) describes a high-level view of the threshold policy in section 4.1 and a more detailed view in the Encrypt and Decrypt paragraphs of section 4.2. The functionality is very similar to Shamir Secret Sharing executed for each gate in the policy.

Access trees are not the only access structures that are used for policies in ABE schemes. LSSS matrices are also very popular. Liu et al. have published an algorithm in "Efficient Generation of Linear Secret Sharing Scheme Matrices from Threshold Access Trees" (2010) to transform boolean threshold formulas into threshold LSSS access structures.


Are there public slow-but-strong algorithms out there that resist brute-force attacks better?

Bruteforcing the AES algorithm itself (i.e. trying all possible keys to encrypt or decrypt some blocks to see if they give the right result in a known-plaintext attack or similar) is not really a problem, even in the 128-bit key version.

(This takes on average 2127 tries. If you can try 230=109 AES-keys per second, it will still take around 5·1021 years, much longer than the universe existed, and any life will exist. Parallelizing this makes it faster, but there is some limit, too ... if you can calculate on 109 processors in parallel, it still needs 5·1013 years ... about three times the estimated age of the universe until now.)

So, the attackable point is not bruteforcing the AES key, but bruteforcing the derivation of a key from a password. And here is where we have to enforce our design. You should not use the password directly (maybe with padding) as an AES key. Instead, use a slow password derivation function, and incorporate some salt.

NIST proposes the PBKDF2 construction based on iterated calling of some fast hash function. Setting the iteration number high enough will make it slow enough.
PBKDF2 is easily parallelizable on GPUs, which makes brute-forcing slightly faster than we would wish, though.

Other alternatives might be bcrypt, or the newer scrypt.
These are firstly slow hash functions for secure password storage, but I think one can also reuse their output as a key for AES or any other symmetric cipher of the right key size. (You just have to think of a protocol to transfer the salt.)


Can I always derive a key pair from password+salt with libsodium?

Is it safe to recreate the key pair using the password+salt every time I need to use it so I don't have to store the keys (encrypted or not) anywhere in the system?

The problem with that is that your public key then effectively becomes a password hash, meaning anyone who sees it will be able to mount a dictionary attack on your password to generate the private key that corresponds to it. They will need access to the salt for the attack, of course, so in that case your salt effectively becomes a secret.

So there is not really a great difference to storing an encrypted (random) private key vs. storing a (random) salt that allows deriving the private key. However, when deriving the key directly from the password you should use a strong random number as a salt, not something unique but guessable, like a timestamp or an email address.


password generation: random length or max length

Having a random length makes very little total difference in the entropy of your password compared to the entropy you would get using just the maximum length allowed. This is because there are a lot more passwords of, say, length 10 than any shorter length (in fact, there are more 10-character passwords than any other shorter password). So if your attacker has the ability to brute force 10-character passwords, he can easily brute-force passwords from 1 to 10 characters with more or less the same amount of work.

In fact, many password cracking programs take advantage of this by going through the shorter passwords first, as checking them takes a negligible amount of time compared to checking all the longer ones, so if you chose a 9-character password in an effort to thwart your opponent, your password will probably take a fraction of the time a 10-character password would have taken. In other words, choosing a random length is a very bad move, always choose the longest possible length (up to some limit dictated by the software you use or your ability to manage that password).

To justify why they do this, let's get some numbers. For instance, assume a charset of 96 symbols (typical ASCII + special characters stuff). How many 10-character passwords are there?

Answer: $96^{10} \approx 6.64 \times 10^{19}$

Now how many passwords of length shorter than 10 are there:

Answer: $\sum_{k = 1}^9 96^k \approx 7 \times 10^{17}$

And so:

$$\frac{\text{Number of passwords length less than 10}}{\text{Number of 10-character passwords}} = \frac{7 \times 10^{17}}{6.64 \times 10^{19}} \approx 0.01$$

What does this mean? It means that if someone took, say, one year to search through all 10-character passwords, it would only take him about 4 days to search through all passwords of length 1 to 9. Clearly, that person might as well search them too if he isn't sure of the length, for very little additional cost. And he may as well do them first to spare himself a year of waiting in case you picked one of the shorter passwords.

You can do the math for other lengths and charsets, and you'll see that in general, it's not worth it.

To conclude, if an opponent has the ability to brute force passwords of length $l$, then picking a random password of length between $k$ and $l$ where $k < l$ offers very little additional protection, and may in fact decrease security as shorter passwords are generally searched first.


What are the consequences (and potential mitigation) to poor entropy/RNG on server-side during ephemermal key generation and DH exchange

In the worst case the result is key pair known to the attacker, in which case an attacker can act as a man-in-the-middle or eavesdrop, leaving you with no security whatsoever. There is nothing the client can do about that; even if his own key pair is fully random then the DH calculations can still be replayed by the attacker.

There is not all that much that a client can do other than to check if the public key received from the server hasn't been send yet. You could store all the public keys and compare new public keys them with previous values. This would catch repeating public keys; if one is found then stop the protocol: the server is insecure.

Fully testing the strength of the server-side RNG is very likely out of reach.

Note that with the advance of hardware-based RNGs the best mitigation against this can be done server side: use RDRAND. This is a user-level instruction that should be available from client VM's. If not used directly it can at least be used to put additional entropy in the randomness pool.

AMD uses the same instruction in their newer chips. The T1 systems from Sun/Oracle also have a hardware RNG. VIA uses a different mechanism (I/O based instructions) but with similar functionality. This kind of random number generation should be very high on your wish list for headless machines.

It could be that VM's also have some ways of mitigating risks (plugging entropy from the host system into the client VM), but I'm no VM expert.


XOR instead of Multiplication in ElGamal encryption

One small question, from the DDH assumption we know $g^{xy}$ is random.

Actually, that's not true.  What the DDH assumption says is that we cannot distinguish $g^{xy}$ from $g^z$; however it does not say that we can't distinguish either from a random string.

Indeed, we can; if the order of $g$ has no small factors, then $g$ must be a quadratic residue (that is, there must exist a value $h$ with $h^2 = g$; this is easily tested); and hence $g^{xy}$ must also be a quadratic residue.  However, a random string is not a quadratic residue with probability 0.5, hence that serves as a distinguisher.

And, if $g$ is not a quadratic residue, then neither the DDH assumption nor indistinguishability from random hold, assuming the attacker can see $g^x$ and $g^y$; that's because $g^{xy}$ is a quadratic residue iff at least one of $g^x$, $g^y$ is a quadratic residue (hence the attacker can compute whether $g^{xy}$ is, even though he doesn't know the value).

This is why Yehuda is telling you to hash $g^{xy}$ first; $g^{xy}$ is distinguishable from a random string (although not necessarily due to a bias in any of the individual bits), $\text{hash}(g^{xy})$ is not.


Using an alternative to shamir's secret sharing

Many problems (if not all) in cryptography can be made "trivial" if you have a mutually trusted third party. The argument is something along the lines of:

Multi-party Computation can describe many (if not all) primitives within Cryptography as jointly computing some functionality
MPC is made trivial in the presence of a mutually trusted third party (this is the basis for the "ideal vs. real" proof strategy)
If given a mutually trusted third party, one can securely implement any function which can be implemented using Multi-Party Computation

Implementing access control as you describe is simply implementing access control with a mutually trusted third party.
If you believe this exists in your situation then you can gain efficiency by using it.
But if you are "wrong", and someone manages to corrupt your server, you "lose everything".

Note that this is somewhat the case for secret sharing already.
Generally secret sharing schemes can be written as two functions: $\mathsf{MakeShares}$ and $\mathsf{Reconstruct}$.
If a server which is running the $\mathsf{Reconstruct}$ protocol is compromised during reconstruction, you "lose everything" (under naive Shamir's secret sharing).

You're (essentially) suggesting implementing $\mathsf{Reconstruct}$ with a stateful trusted third party. You could even make this explicit by having your server first run Shamir's secret sharing on the secret, then "renaming" the Shamir's shares using some arbitrary encoding (which you "store" in a table on the Server to be able to undo later).
But as your solution requires the state for correct reconstruction, if your server is ever compromised, you "lose everything" immediately.

Another application your algorithm can't replace Shamir's in is when the protocol participants don't trust eachother.
Someone has to "have all the shares" to be able to implement the access control, and if there's no natural candidate then your protocol doesn't work, but Shamir's still does.

That all being said, for implementing access control where all participants are part of the same organization, you could use non-cryptographic techniques (such as yours) due to the presence of a mutually trusted third party.


Is it generally considered acceptable for app owners to be able to retrieve private keys from users when their apps offer end-to-end encryption?

If you define E2EE as the promise "that data sending between two endpoints can be decrypted by only those two endpoints", then by definition, if the app owner can decrypt, what you have is not E2EE and you shouldn't advertise it as such.


You have to distinguish "implement" from "define".

Brakerski defines his scheme over fractions, but implements it using integers just because it is easier to implement, more efficient and less error prone. If you represent the fractions with floating values, then you have precision issues. And if you represent them with two integers (denominator and numerator), then you probably use more space than what is needed.

That is why he says in the end of section 1.2:

  Finally, working with fractional ciphertexts brings about issues of precision in representation and other problems. We thus implement our scheme over $\mathbb{Z}$ with appropriate scaling.

Thus, this implementation choice has nothing to do with the security aspects of the scheme.

That said, TFHE does something similar: it is defined over $[0, 1[~\subset \mathbb{R}$, but if you check the code, you will see that integers are also used there.

For example, see the following lines on the file torus.h:

// Idea:
// we may want to represent an element x of the real torus by
// the integer rint(2^32.x) modulo 2^32
//  -- addition, subtraction and integer combinations are native operation
//  -- modulo 1 is mapped to mod 2^32, which is also native!
// This looks much better than using float/doubles, where modulo 1 is not
// natural at all.
typedef int32_t Torus32;
typedef int64_t Torus64;


How does TLS generate the shared secret?

Selection of the Diffie-Hellman parameters

If you are asking about the TLS cipher suites that use a Diffie-Hellman exchange (basically the ones containing "DH" or "DHE"), it depends on whether static or ephemeral Diffie-Hellman certificates are used.

The ephemeral cipher suites (DHE_DSS, DHE_RSA, DHE_anon and the various elliptic counterparts) transmit the generator, the prime modulus and the public value in the server and client key exchange messages.
The static cipher suites using Diffie-Hellman (DH_DSS, DH_RSA) use the (fixed) parameters embedded in the server certificate. If a client certificate is used, the parameters have to match the server's.

Not all cipher suites use a Diffie-Hellman exchange, though; in the (widely used) RSA_* cipher suites, the client sipmly selects a random premaster secret and encrypts it using the server's public RSA key.

Purpose of the client/server random values

The client and server randomness serves to avoid ever using the same emaster secret twice; for example, when a static Diffie-Hellman ciphersuite is used with a client certificate, the server's and the client's Y value don't change between sessions. This is done by securely hashing the premaster secret (which might or might not be equal for different sessions) and the client and server random values (which are required to be different for different sessions).

Reusing the master secret could allow replay attacks or cause the symmetric cipher to reveal information about the payload data.


Why do the non-leaf Nodes of Merkle tree need to be hashed?

The benefit of the Merkle Tree is that you store only one element, the top hash. You don't need to store any other elements to verify the data. The hash of each element is in the chain to the top hash.

In your proposal, if one needs to get A, then you return Hash(Leaf A) || Hash(Leaf B). But, wait; how one can verify it by the top hash. To verify we need to store Hash(Leaf A) || Hash(Leaf B). So there will be many elements to store. Thus, if you stick the Merkles' idea you will have the benefit.

For the comments;

The layer of hashing is necessary since we can store only one element the top hash and we can return only the intended element since the elements are on the leaf level we only need to transfer the requested leaf and path the root hash.
Some purposes: Memory verifications against fault attacks. Also, storing files on the cloud. This will prevent the rollback attack, i.e. an attacker replaces the old version of a file. The Merkle Tree enables detection with negligible false acceptance.


Why have 4th and 5th steps in Needham-Schroeder Protocol?

Notice that $N_b$ has not been seen until step 4, so it is generated by B. In step 5, A sends $N_b-1$ back to B. This proves to B that A knows $K_{ab}$ otherwise A could not have recovered $N_b$.

This is done to prevent A from replaying the message in step 3 and therefore authenticating. For example, suppose Eve sees Alice send the message in step 3 $\{K_{ab},A\}$.

B receives this message, uses $K_{bs}$ to decrypt it and sees the identifier $A$ and therefore believes that Eve is A.

I think where most people get confused with Needham-Schroeder is that they assume that after step 3, Eve does not know $K_{ab}$ (which is correct) and therefore if B starts encrypting further session information with $K_{ab}$, Eve will not be able to decrypt those message (which is also correct). The problem is there is no guarantee that the rest of the session is encrypted. Needham-Schroeder places no such requirement on users of Needham-Schroeder (as it is simply an authentication protocol and the security of it should not be tied to how an application uses resulting keying material).


In RSA encryption, can I calculate d given only m,n,c and e?

No!

RSA is public-key encryption and in public-key encryption, the known plaintexts are free. Given a public key $(n,e)$ we can find many $(p_i,c_i)$ such that $c_i = p_i^e \bmod n$. If this is a weakness, on the first day it will be broken.


Why use randomness in digital signature algorithms?

The main benefit of adding randomness in RSA signature padding is that it simplifies and strengthens security arguments. At least that's claimed by PKCS#1v2, paragraph above 8.1.1 (emphasis mine)

  RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a “tighter” security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures-How to Sign with RSA and Rabin (in proceedings of Eurocrypt 1996)] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [Jean-Sébastien Coron: On the Exact Security of Full Domain Hashing (in proceedings of Crypto 2000)].

De-randomization can be used to turn a randomized signature scheme (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random salt) into a deterministic one: we use some CSPRNG seeded with the (hash of the) message to be signed instead of true randomness, essentially transforming the scheme into a deterministic one (similar to deterministic RSA-FDH), with a security proof. The weakness in that simple argument is that an adversary that hypothetically could get benefit of some characteristic the random portion may have, can now try messages until finding one with the corresponding pseudo-randomness having that characteristic, then obtain a signature; so quantitative security bounds on the number of signature queries (rather than any kind of oracle queries) necessary to make a forgery is not as good as with the original randomized scheme.

Update following comment: in the above I'm considering a truly secure CSPRNG, but one that is known to the attacker, which can thus run it without querying the signature-producing device/oracle. That conceivably could matter: a real-life attacker might have a low and hard limit on the number of signatures for chosen message she can obtain from a remote server, but can run the CSPRNG (and whatever other computation involving the public key) at high speed with her own CPUs.

Note: My answer above is at the hand-waving level, with no proof, rather than a precise comparison of the security of RSA-PSS and RSA-FDH for stated security criteria and hypothesis on RSA; which is complex.

While some fault-based attack (like Dan Boneh, Richard A. DeMillo, Richard J. Lipton's On the Importance of Checking Cryptographic Protocols for Faults, in proceedings of EuroCrypt 1997) indeed are blocked by a randomized message, this is an a posteriori rationalization; such attacks should be blocked by independently checking any signature produced against the public key before it is output.

Randomized rather than deterministic padding has an influence for side-channel attacks, but it is debatable that randomizing improves security; when doing some DPA attacks, a known random input is often the ideal setup (note that the padded message gets known to the adversary in any RSA signature scheme).


Euler's Totient function for semiprime numbers

You can get the 2nd equation from the first with some simple algebra.

$$(p-1)(q-1)$$
$$pq-p-q+1$$
$$n-p-q+1$$

I'm not really sure what you are asking though. Are you asking if computing the second is faster than the first?

I suppose you could argue that you have to do the $pq$ multiplication anyways, so why not reuse it. If that is your argument, then doing the calculation with the 2nd equation you gave for $\varphi$, then you get the multiplication for free and only have to do 2 subtractions and an addition. Using the first equation, you have to do two subtractions (although only a minus 1) and one multiplication. Multiplication is much more expensive, so the 2nd equation would be more efficient.


Ideally, each key $k$ select a permutation of all possible permutations $2^n!$ for a block cipher with block size $n$. So when we say 128-bit key we expect that they represent $2^{128}$ permutations from possible ones. Some keys might be very bad, maybe just inverting the plaintext or some acts as a counter, we don't know.

Your calculations are correct if the random selection has no collisions, i.e. there may be two keys that represent the same permutations. We don't expect this collision since $2^{128}$ is very small compared to $2^n!$.

In general, we don't talk about the number of permutations that the key-size represents. We talk about the provided security by key length in bits.


PGP digital signature vs SHA256 HMAC Comparison

PGP [1024-bit] digital signature vs SHA256 HMAC Comparison...

First, you can compare asymmetric and symmetric algorithms. A 1024-bit asymmetric key provides about 80-bits of security. A SHA256 HMAC provides about 128-bits of security. With all other things being equal, the HMAC is stronger.

Second, I believe PGP (or is it GnuPG) uses Lim-Lee primes and they don't provide the prime factorization. So you can't test that they are any good in practice.

Third, the random key used in the HMAC may not be random. And the random numbers used to generate the asymmetric keys might have problems too. Randomness is a lot like bugs. To borrow from Dykstra, you can test for the absence of randomness, but the presence of it.

Fourth, both systems sound like they might be subject to forgeries. So you might want to ensure surreptitious forwarding, replays and other tricks don't occur.

Fifth, ... (favorite threat here).

Also, storing the private key or the symmetric key is the Unattended Key Storage problem described by Gutmann in his book Engineering Security. Its a problem without a solution.

  other attacks that attempt to derive the private or secret key?

OK, this is easier. The adversary will not attempt to break the crypto. They will go around it. They will go around it by breaking into the system, getting root, and then reading the key from the filesystem.

There are only two crypto attacks I am aware. First was the factoring of the TI Signing Key, and second was the Flame malware. The TI factoring occurred on a 512-bit asymmetric key; while the Flame malware took advantage of MD5 collisions on Microsoft CA certificate.

Breaking into the system is a much more cost effective attack. It will probably start by phishing one of the ladies in HR or Accounts Receivable. That's how it started with with a few high profile attacks, like RSA Data Securities and one of the other big ones, like Sony (IIRC).

  Based on current computing power, how long should we have reasonable assurance that either technology would be relatively secure?

I think 80-bits of security is within reach of a few well funded adversaries. But out of reach of most others.

128-bit security will likely never be within reach of anyone.


Is being cryptanalyst synonymous with being a code breaker?

First up, please note that this Q&A is primarily opinion based. Therefore, I’ll be focusing on the symmetric part and nothing else you’ve mentioned and/or asked for in your question.

  99% of cryptanalysis are not code breaker.
   If you try a PhD in cryptanalysis and expect to break code, you are dreaming.

In movies such as Mercury Rising, Imitation Game or A Beautiful Mind, you see cryptanalyst (or child) breaking codes just by being exposed to the cipher text.

Academics consider this kind of attacks as weak. We now works something similar to a Lunchtime attacks. We consider the internals of the algorithm to be know by the attacker and the goal is now to find weakness in it. We are not looking for deciphering a single ciphertext.

Attacks that are used on these algorithm are far more complex (have a look at Differential cryptanalysis, Linear Cryptanalysis, Related keys...)

About the maths level, are required: Probabilities (a lot!), Finite Fields, Affine Varieties and other tools, all of them are about Bachelor-Graduate level.

What is the current state of the art?

In symmetric crypto, using the correct algorithm we are already post-quantum. Should you use strong enough algorithm, even the NSA won't be able to read what you are hiding.

In asymmetric crypto, the research is currently being done to get post-quantum assurance. We have things like New Hope.

EDIT:

As stated at the beginning of my answer, the question is off-topic by definition. The reason why it still exists and has been locked (by e-sushi♦) for “Historical significance”, is that we thereby gain a Q&A for all those newcommers to cryptography (and our site), who are confusing “fiction” (read: code breaking in movies) with “reality” (read: modern cryptanalysis in the real world). By keeping this Q&A around, we now have a place to point them to… hoping they learn something from it.


A Smart Card is small portable physical device, typically flat and in the format of a traditional credit card (sometime much smaller: an example is the SIM card in a mobile phone), embedding:

An Integrated Circuit with memory providing permanent data retention; that's using EEPROM, Flash, or FRAM in most of today's Smart Cards.
Temporary coupling means with a reader device allowing to power that IC, and communicate with it; that may for example be contacts, often according to the ISO/IEC 7816-3 standard; or a few turns of conductive material in the card, forming an inductive loop operated at 13.56 MHz, often according to the ISO/IEC 14443 standard.
Inhibiting means restricting read or/and write access to that memory according to some policy. This can go from a few logic gates, to microprocessor(s) with cryptographic accelerators for 3DES, AES, RSA, and ECDSA.

Wired logic Smart Cards

The first commercially successful Smart Card was a pre-paid phone card, used for over two decades in public phone booths in France, replacing coins (which made phone booths too much an attractive target). It had 256 bits of memory, implemented in EPROM technology with 21V programing voltage, plus one physical fuse. The contacts allowed to reset an 8-bit address counter, increment it, read the selected bit, and program the selected bit. Its memory access policy was: any bit can be read; any bit can be programmed (from 0 to 1) when the fuse is not blown; only the last 160 bits can be programmed when the fuse is blown (this is implemented by a logic function of the fuse's state and the three hight bits of the address counter); erasing (from 1 to 0, by exposing the bare IC to ultraviolet light) erases all bits, and normally occurs only in a late manufacturing stage of the IC. The first 96 bits contained issuing information, written before the fuse was blown. Some of the last 160 bits (as defined by issuing information) each represented a certain prepaid value, when still erased. Programming one of these bits reduced the remaining value in the Smart Card. Erasing did not help an adversary, for the issuing information could not be restored after erasure. That information was also protected by a checksum (a 7-bit field containing the binary expression of the number of 0 bits in like 88 other bits of that information; this corruption detection system is such that altering any number of bits in the same direction makes the information invalid).

Fraud by simulation (which was possible due to the lack of cryptographic protocol and secret key in that early Smart Card, and did occur) never was a seriously damaging issue, although about two billions of that Smart Card have been made. That was the kind preferred by Roland Moreno, often credited for the invention of the Smart Card circa 1974 (full disclosure: we have been close friends from 1983 till his death in 2012).

Microprocessor Smart Cards

Many contemporary Smart Cards have a built-in microprocessor, usually on the same die as the long-term memory, implementing the access control policy, in the form of a program rather than wired logic. The access control policy can thus be almost arbitrarily complex (including contained in the memory itself, and alterable as part of the access control policy). That processor can be anything from a 1 MIPS 8-bit CPU, to a much faster 32-bit RISC core. There can be dedicated co-processors for cryptographic algorithms: DES/3DES, AES, RSA (and other cryptography based on exponentiation in $\mathbb{Z}_{n}$), ECDSA (and other cryptography based on elliptic curves), complete with sophisticated protection against side-channel attacks; hardware TRNG+PRNG with testability features; shield against intrusion; detectors of abnormal operating conditions (shield breach, light, temperature, supply voltage glitches..); bus encryption; parity or SECDED on memory; perhaps two CPUs, with hardware checking they obtain equivalent results, for added protection against fault injection attacks; and more.

For a tour (absolutely recommended) of a high-end Smart Card IC, see e.g. that Security Target (alternate link), starting with the block diagram on page 20.

Access control policy implemented in Smart Cards

As an illustration of a common feature, the Smart Card's permanent data memory can contain a Personal Identification Number and a counter of consecutive PIN presentation errors. The usual PIN access control policy will block PIN presentation if the counter of consecutive PIN errors reaches 3; increment the counter at each PIN presentation, then if the PIN is correct reset the counter and enable some function until power off: reading from or writing to some section of the memory; or/and using some information in the memory as the secret key of a cryptographic MAC allowing the Smart Card to be part of a challenge/response protocol. Such PIN policy makes the Smart Card safe against misuse in case of loss of the Smart Card without the PIN, with high confidence (0.03% risk for a 4-digit PIN).

Smart Cards are also useful a containers for an individual's or server's credentials in a Public-Key Infrastructure, in the form of a private key, generated within the Smart Card, or injected into it. The policy will typically include no function allowing the private key to leave the Smart Card, restricting the use of that key to, say, RSA signature of (the hash of) a message supplied to the Smart Card. That prevents compromise of the confidentiality of the key (but not misuse), should the Smart Card be connected to a compromised device/PC.

A lot of work goes into the access control policy of a modern Smart Card; see for example this (highly technical) two parts specification aimed at e-government applications; or (that's relatively simple) what pertains to the card in the European Regulation specifying the Digital Tachograph for trucks, in Annex 1B, appendix 2, and appendix 11 for the RSA + 3DES cryptography.

Comments on what ought to be added welcome!


How to generate hard subset sum instances

How can we generate hard instances of the subset sum problem that are not solvable in polynomial time, or more specifically, require exponential time to solve?
Is it sufficient to use any size set and with elements such that $\text{density}=1$? Assume that all set elements are uniformly random and of size $\operatorname{log}(\operatorname{max}(S))$
Supposing we can generate problems that require exponential time to solve, what parameter is the problem exponential in?

Conditions and Parameters
The hardest instances have $\text{density} = 1$.
An instance of the problem with $\text{density} = 1$ will require time exponential in the number of elements that are summed together.
To generate hard instances of the problem, ensure that:

The number of elements in the set $k$ is equal to the the size of the largest element in the set (in bits)
All elements in the set are approximately that size (you can't have a single element of size $\operatorname{log}(k)$ and the rest of the elements small).
Each instance should sum ($k / 2)$ of the elements of the set together.

If you were to sum $k - 1$ elements of the set together, then you could solve an easier problem (namely: subtract elements from the sum of the entire set until you find which one(s) isn't a member of the target subset)

Cost
Basically, you need $k$ uniformly random elements of size $\operatorname{log}(k)$ for a hard instance of the problem. This implies that a hard instance of the problem will require $O(k^2)$ space.
There is a quantum attack against the subset sum problem that runs in time $O((0.241... + O(1)) * n)$, which we will round to $O(.25 * n)$ to make the following math more convenient:
Assuming the complexity of the quantum attack cited above using the conditions laid out above, the computational cost to solve a subset sum problem of size $k$ is $O(2^{k / 8})$.

To generate instances of the problem that require approximately $O(2^{128})$ computational cost against a quantum adversary, set $k = 1024$.

This will use $1024^2 = 1048576$ bits of space.

Is a higher density necessarily more difficult?

No, instances of the problem with $\text{density} > 1$ are more easily solved.


The fastest way to solve your problem instance is as outlined in the above comments.

First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$.

Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$.
$m \equiv c^3 \pmod n$
$m \equiv c^{17} \pmod n$
$m \equiv c^{65537} \pmod n$

If none of the above equations held you have two choices, based on the effort you're willing to spend and the probability that $e$ is rather small.

If you suspect $e<\frac{1}{3}N^{\frac{1}{4}}$, then you should use Wiener's attack on small decryption exponent RSA with the lost public exponent taking the role of the decryption exponent to find. Wikipedia explains the basics and Wiener's original attack.
As Maarten points out in the comments below this attack is very fast and consumes moderate amounts of memory.

If you think / know that $e<2^{40}$ and/or you're not willing to implement Wiener's attack you can use the following approach, as you can always come back to Wiener's attack in case you think that you've tried long enough.
The brute-force approach would work as follows ($i=3$, optimized using fgrieu's comment):

Set $c_m \gets (c * c) \bmod n$,
Check if $c \equiv m \pmod n$ or $c_m \equiv m \pmod n$, if the first holds, output 1, if the second holds, output 2.
Set $c_3 \gets (c * c_m) \bmod n$
Check if $c_{i}\equiv m \pmod n$ holds. If yes, output $i$
Set $c_{i+2}\gets (c_i*c_m) \bmod n$, goto step 3

If you can not apply Wiener's attack and you consider brute-force "way too inefficient" there are still two methods left:

Use your favorite factorization algorithm to factor $n$ and deduce $e$ from $(d,p,q)$
Use your favorite discrete logarithm algorithm to solve $c^e \equiv m \pmod n$ for $e$.


Construction of secure Elliptic Curve subgroup over a much larger field

Hasse's theorem notes that for an elliptic curve over a finite field with $\mathcal{Q}$ elements (which would mean $\mathcal{Q}=p$ for a prime field $\mathbb{F}_p$) that has $N$ points, the following holds:

$|N-(\mathcal{Q}+1)|\le 2 \sqrt{\mathcal{Q}}$

For the sake of illustration, let's take $\mathcal{Q}=p=8191$. This gives us $|N-(8191+1)| \le 2\sqrt{8191}$, leading to this range of possible numbers of points (rounded): $8011 \le N \le 8373$. Since this gives a hard lower and upper bound on the number of points, clearly, a prime-order curve over a large field with the constraint that the order of the curve $q$ is significantly smaller than the field prime $p$ isn't possible.

Thus you need to ignore prime-order curves and instead have a large group $\ell$ and a significantly smaller prime subgroup given by cofactor $h$ on which we operate. The worst case impact of a large cofactor is limited to a speedup of a factor of $\sqrt{h}$ compared to the standard Pollard $\rho$ attack—but that focuses on the large group $\ell$, not the cofactor itself. With $\ell$ being the “cofactor” and the real main group being what normally is considered a cofactor, things seem to get hairy and unclear in their actual impact.

Even if this is an acceptable risk, Igor E. Shparlinksi and Andrew V. Sutherland, Finding Elliptic Curves With a Subgroup of Prescribed Size, 2017 gives you a very dense outline of what an algorithm could look like to find curves with a cofactor in a pre-determined range. Even then, the runtime of the algorithm is painfully slow for sufficiently large $p$ for $\mathbb{F}_p$ (assuming you're in the 2048-bit range for $p$), namely $mp^{1/2+o(1)}$ to the point that it is likely impractical.


How many possible input files are there who's length can be stored in 63-bits?

For a given file length L bytes the combinations for that length is 256^L. The total combination is the sum of combinations for all file lengths L from zero to (2^63)-1. Just substitute parameters in the formula for summing the n first terms of a geometric series. The rest is left as an exercise to the reader :-)

If all you need is a rough order-of-magnitude estimate it is really sufficient to just look at the highest order term, which provides a quick lower-bound estimate and which will already tells you the ratio is a very large number (very large for cryptographic purposes), which means the factor you have "reduced entropy" is a number very close to zero (once again, for cryptographic purposes).


How to figure out the size of the output of a cryptographic checksum function

The question states that the probability of finding a collision is $2^{-64}$. This is incorrect. The probability depends on the number of available messages, as we will see below.

If you take two random messages, the probability of them having the same $m$-bit hash is $2^{-m}$. So you're going to have to try around $2^{m}$ pairs before you find a collision.

But you can do this without generating $2^m$ messages.

Consider this:

With $n$ different messages, you can generate $C(n,2)$ different pairs of messages

$C(n,2) = \dfrac{n!}{2(n-2)!}$

$= \dfrac{n(n-1)(n-2)!}{2(n-2)!}$

$=\dfrac{n(n-1)}{2}$

$=\dfrac{n^2 -n}{2}$

So with $n$ different messages, we can generate $\dfrac{n^2 - n}{2}$ unique pairs.

Now we need to figure out how many messages are required to have a good probability ($\geq$50%) of finding two colliding messages.

$\dfrac{\frac{n^2 - n}{2}}{2^m} \geq 0.5$

$\dfrac{n^2 - n}{2^{m+1}} \geq 0.5$

$n^2 - n \geq 2^m$

So it turns out we need just over $2^{m/2}$ messages. This is usually simplified to exactly $2^{m/2}$ since we're dealing with such large numbers that the difference is negligible. There are other ways of calculating it, but they all work out to the same approximation (see Birthday Problem, Birthday Attack).


accepted wisdom that OTP encrypted messages are secure & unbreakable

OTP encrypted messages are secure & unbreakable assuming the pad is secret, uniformly random, and not reused... and the message does not otherwise leak! The last point is where the "Bit Flip" attack comes to play.

Imagine the message is conventionally a digit send in ASCII, and parsed as such by the receiver after decryption; and that the context tells the adversary that a particular message is 1 or 2, that is the bitstring 00110001 or 00110010. With the OTP (or a stream cipher), the adversary can flip the 5th bit of ciphertext, and know that changes the plaintext to 00111001 or 00111010, that is the character 9 or :. Now if the adversary can sense whether the receiving system accepts the result as a digit, or rejects it, the confidentiality is lost!

More generally, when users of cryptography need encryption for confidentialitty, they tend to additionally need assurance of integrity and origin. The OTP only gives confidentiality, and as illustrated not unconditionally in some quite practical cases.

However, assurance of integrity can be obtained with an information-theoretic substitude to a MAC, or universal hash, such as Carter-Wegman; and when the OTP is shared among only two parties that gives assurance of origin. That consumes some of the OTP, but manageably so. And it can help mitigate the above attack (an altered message will be rejected before it is tested that it is decimal).

There remains two reasons making the OTP impractical:

It is easy for an adversary to mount a denial of service attack that de-synchronize sender and receiver (that can be solved to a degree, but is not trivial)
The random pad must be sent in advance by secure means, and kept secret on both sides.


Efficient parameters for group Diffie-Hellman

You'd need to compute $K^{(a^{-1})}$. Only those who hold the private key $a$ can do this. Multiplying with $(g^a)^{-1} = g^{-a}$ would subtract $a$ from the exponent, not divide the exponent by $a$.

So your optimization isn't possible in practice. Take a look at the alternatives at Can one generalize the Diffie-Hellman key exchange to three or more parties?. Thomas Pornin describes a two-round shared key algorithm based on DH and links to an single-round scheme that uses advanced crypto.


Subgroups generators with respect to group generators of composite order

If $\mathcal{G}$ is of order $N$ (who doesn't look like a prime number btw) and $g$ is a generator of $\mathcal{G}$ then $g$ has order N. Since $(g^{nq})^p=1$ and $\forall 1\le k <p, (g^{nq})^k\neq 1$ (g has order $N$ and $knq<N$) then $g^{nq}$ generates a subgroup of $\mathcal{G}$ of order $p$ and there's only one such subgroup : $\mathcal{G_p}$.
The reasoning is the same for the rest.
Hope it's clear and correct


How to show that the following function is not a OWF?

Any $x$ is fine. Since $F$ is a PRP, for any key $x$ and output string $z$ there is an input string $y$ such that $F_x(y) = z$.


Differential and Linear Cryptanalysis on Random Sbox

Typical attacks on Secret SPNs (i.e. with secret uniform S-Boxes) are integrals, see e.g. [1].
Even for AES: the S-Box is too good against differential/linear attacks (strong mixing in MixColumns is also necessary), so best attacks are of another kinds. (Not counting related-key attacks, which allow to deactivate many S-Boxes).
More to the question: in some special cases it may be indeed useful to consider differential cryptanalysis with ``random'' difference. See for example [2], where the output of the Feistel function is very small so that it does not matter which difference to choose - the differential will be sufficiently strong anyway.
[1] Biryukov, A., Khovratovich, D., & Perrin, L. (2017). Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs. IACR Transactions on Symmetric Cryptology, 2016(2), 226-247. https://doi.org/10.13154/tosc.v2016.i2.226-247
[2] Orr Dunkelman, Abhishek Kumar, Eran Lambooij, Somitra Kumar Sanadhya:
Cryptanalysis of Feistel-Based Format-Preserving Encryption. IACR Cryptol. ePrint Arch. 2020: 1311 https://eprint.iacr.org/2020/1311


Why is ISAAC not a pseudo random number generator?

Trying to distinguish a synchronous stream cipher from a CSPRNG seems to me a bit like trying to distinguish ice from frozen water.  Any secure stream cipher is a CSPRNG, and any CSPRNG can be used as a stream cipher.

Insofar as there is any difference, it mostly comes down to intended purpose and API design.  A typical CSPRNG API might take an initial seed value (equivalent to the key of a stream cipher), and allow the user to request small chunks of random output bits, whereas a typical stream cipher API would be initialized with a key and (usually, for modern cipher designs) an IV / nonce, and allow the user to pass in plaintext or ciphertext to be XORed with the output keystream.

Also, speed may not be as important a design criterion for general CSPRNGs as for stream ciphers, since one rarely needs a lot of pseudorandomness quickly unless one is using it as a keystream for encryption.

Now, the ISAAC reference implementation definitely provides a PRNG-style API: you pass in a seed array of 256 32-bit integers, and then request output in 32-bit chunks (either one at a time, or 256 chunks at a time by directly accessing the input/output buffer).  The C API does effectively allow treating the seed / output buffer as an array of 1024 bytes (as shown e.g. in the ISAAC challenge code, which seeds the generator with an ASCII string), but the conversion is implicit and platform-dependent (due to endianness issues).

However, while the ISAAC API is that of a PRNG, the algorithm itself is clearly designed with performance in mind, and intended to be competitive with earlier stream cipher designs such as RC4.  So, yes, ISAAC as presented by Jenkins is primarily a PRNG, but it's meant to be usable as a stream cipher.


Unless I am missing something, I believe that you can simply compute $R = s*B - h*A$ using point subtraction.


Why 64 bits output hash function is insecure

The answer is easy if you know about the current computing power around the world

Bitcoin miners in 2020/1/17 they reached 126.1314 Exahashes per second, that makes

$2^{67}$ SHA256 double hashes in a second, and
$2^{92}$ SHA256 double hashes in a year.

With 64 bit output from the hash function, you will have

64-bit pre-image resistance, broken less than a second.
64-bit second pre-image resistance, broken when you click the enter.
32-bit collision resistance due to the birthday attack that has a 50% chance of collision. You will find a collision while your finger on the enter key.

In today's standard, the recommended has size is at least 224 bit by SHA256-224 if you consider all available NIST hash families after the SHA-1 which has 160-bit output.

There are also single super computers like Summit, that can reach ≈$2^{63}$ SHA-1 hashes around one hour, ≈$2^{72}$ hashes in one year.
1


Can one deduce the symmetric key size used to encrypt a given a piece of ciphertext?

No, that's not possible because of the reasons given in the other answer. Unless the block size is linked with the key size, or if the cipher is not cryptographically secure, you should not be able to find out the key size by just looking at the ciphertext. This is true even if you know the algorithm.

Note that this does not take side channel attacks into account. It's pretty reasonable to assume that ciphers take longer to compute when a larger key size is used. This is for instance true for AES, where there is a difference in the number of rounds used for each defined key size. Even if this is not the case then you should expect that e.g. the key expansion that is usually used will take more time for larger key sizes.

Note that the key size - just like the algorithm - is usually not considered to be a secret. So most protocols simply define the key as a constant or as part of protocol negotiations.


The line:
  default_r1cs_ppzksnark_pp::init_public_params();

is used to specify the public parameters used by the proving system ($\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, \mathbb{F}_p,$ ... etc). These are known by the generator, prover, and verifier and therefore are not secret.
You are 100% correct that the prover and generator should be different entities - the generator uses random "toxic waste" values to generate the keying material. Anyone who knows these toxic waste values can break the soundness guarantees of the protocol and forge proofs for statements of which it doesn't know a witness.
To answer your other questions:

How should the generator step be separated from the prover step?

The generator should only run once by a trusted party and publish the resulting proving and verifying keys. In practice, secure multiparty computation (MPC) protocols are used such that as long as $1$-out-of-$n$ of the participating parties are honest, the toxic waste is never learned by any of the participants. This is what ZCash did for instance: https://z.cash/technology/paramgen/

The prover has everything (public and private info), so he can indeed generate the circuit from scratch, but the verifier should "not" accept the keypair from the prover, correct?

This is correct. In fact, anyone can generate the circuit (and some corresponding prover/verifier keys) from scratch, because a witness is not required in order to generate these. However, a verifier should never blindly trust keys that were given to it.

Finally, the generator (who knows everything, public and private info) prepares the keys, sends them to the prover and the verifier. The prover constructs its own pb (protoboard) because he needs the pb.primary_input() and pb.auxiliary_input() to create the proof, then uses its own pb with the generator's proving key to generate the proof. In my experiments the keys generated by the generator and by the prover are the same even if I initialise 2 different pbs, this is counter intuitive to me because the prover can impersonate the generator. Are the keys the same because the init process of the protoboard is the same?

I have a feeling that your experiments are off. Libsnark gets randomness from /dev/urandom, so two different invocations of the generator should result in different toxic waste values, and accordingly different keying material. The generator is executed on the line:
const r1cs_ppzksnark_keypair<default_r1cs_ppzksnark_pp> keypair = r1cs_ppzksnark_generator<default_r1cs_ppzksnark_pp>(constraint_system);

If you run this step multiple times, you'll receive a new keypair each time.


What is the best way to forge a tag for a determined message?

I think it must be:

$$\Pr[forgery]=\sum_{n=0}^{m-1} \frac{1}{2^{128}-n} $$

This is not correct; this can be seen in the simple case where there are four possible keys and you get three guesses.  By the above logic, the probability of guessing the correct key would be $1/4 + 1/3 + 1/2 = 13/12 > 1$, which is absurd (as probability are never greater than 1).  The subtle error you make here is that you can add probabilities only when they are disjoint (and refer to the same event), and in the $m=2$ case (which is the easiest), you're adding a normal probability that the first key is correct ($1/2^{128}$) to the conditional probability that the second key is correct (assuming that the first key is not) ($1/(2^{128}-1)$.

Instead, the correct probability of guesses the correct value (given $m$ guesses), assuming that you will always make $m$ distinct guesses, is:

$$\Pr[forgery] = m / 2^{128}$$

In addition, to be precise, there are actually two ways that the attacker can win.  The first is that, in one of his $m$ guesses of the key, which is what you covered.

The other way he can win is if he selects an incorrect key, however the HMAC of that key just happens to be the right one (by shear chance).  If we assume that HMAC acts like a random oracle, and that we using an untruncated (256 bit) HMAC (I say this because it is quite common to truncate the HMAC output when transmitting it), then (assuming that all the guessed keys are incorrect, and that the adversary checks to see if two of his guesses just happen to be the same, and if so, selects a different key) the probability that we win this way is:

$$m/2^{256}$$

So, the probability that either one of these events occur (and so the attacker wins) is:

$$Pr[forgery] = 1 - (1 - m/2^{128})(1 - m/2^{256})$$

If you want to ignore this second case (which is, in fact, a quite low probability event), and say that it's $m/2^{128}$, well, that's reasonable...


What does the number 256 in pairing curve BN256 indicate?

It's the size of the prime number of the underlying field in G1, G2 and GT.

In BN256, G1 is $E(\mathrm{GF}(p))$, G2 is a subgroup of $E(\mathrm{GF}(p^{12}))$ (or $E'(\mathrm{GF}(p^{2}))$ when using a twist) and GT is a subgroup of $\mathrm{GF}(p^{12})$.

Elements of G1 requires the same number of bits as $p$ for each elliptic curve point coordinate. Note that not all prime-friendly curves support cofactor 1, which means that in some cases we need a larger prime for a particular group order. (This is not the case in BN curves).

Elements of G2 require the same as $p^{k}$ for each elliptic curve point coordinate, where $k$ is the embedding degree of the curve. When using twists, we can reduce this by 2, 3, 4 ou 6 depending on the curve. BN curves have embedding degree 12 and support sextic twists, so we can use elements with the same size as $p^{12/6} = p^2$.

Elements of GT require the same size as $p^{k}$.


Cryptographic pseudo-random generation of address subsets

It is possible to build a hybrid between your first two solutions, to trade off between their advantages and disadvantages.

Let $E_K : \{0,1\}^{32} \to \{0,1\}^{32}$ be a block cipher with a 32-bit block.  You will select a single global key $K$, that will be stored on every device.  Also, for each device, select a few starting points $s_1,\dots,s_m$, say $m=8$ of them.  These are specific to each device.  The idea is that the device has a pool of $nm$ addresses, namely, the values $E_K(s_1), E_K(s_1+1), \ldots, E_K(s_1+n-1)$, $E_K(s_2),E_K(s_2+1),\dots,E_K(s_2+n-1)$, $\ldots,E_K(s_m+n-1)$.  Each time the device changes its address, it selects a new address from its pool -- either randomly, or cycling through the addresses in the pool, whichever you prefer.  Here you should select $n,m$ so that $nm=X$, so that each device has $X$ different addresses in its pool.

Now you select different start points $s_1,\dots,s_m$ for each device, and select the starting points so the devices' address pools don't overlap.  One approach is to choose each $s_i$ to be a random multiple of $n$, uniformly and independently at random, sampling without replacement (i.e., you discard a starting point if it has been previously selected).  In this way, you can arrange to have up to about $2^{32}/(nm)=2^{32}/X$ devices.

This scheme requires each device to store $m+1$ values, the starting points $s_1,\dots,s_m$ and the global key $K$.  The security you get is pretty decent.  If no device is compromised, this scheme is as good as your first solution (and as good as you can get, assuming 32-bit addresses): it'll take $nm$ or $\approx \sqrt{nm}$ address-changes before a device ever repeats its address (depending upon how the device selects from its pool, either cycling or random selection).  If a device is compromised, not all is lost: you still have some security remaining; in particular, you get security equivalent to a pool of $m$ addresses.

This now lets you tune the parameters to trade off between storage cost vs level of security.  My suggestion would be to pick $m$ as large as you can reasonably afford, given the amount of storage available for this security mechanism.

As fgrieu points out, in this scheme the block cipher must have a 32-bit block size, which is not as common as 64-bit or 128-bit block, but still well studied as part of Format Preserving Encryption, including by Granboulan and Pornin (in proceedings of Fast Software Encryption 2007); Bellare, Ristenpart, Rogaway and Stegers (in proceedings of Selected Areas in Cryptography 2009); Morris, Rogaway, and Stegers (in proceedings of Crypto 2009).  (Paragraph and links copied from fgrieu's comment; my thanks to fgrieu.)


The standard definition of CCM is NIST SP800-38C.  Not all of the symbols you cited appear in NIST SP800-38C.  If you're using a different reference, you'll need to cite it to get a more specific answer.

  [C]an anyone explain what the difference is between $B_i$'s and $m$?

The $B_i$ are the blocks of input for CBC-MAC, derived from encoding the nonce, associated data, and payload uniquely into a bit string.

$m$ is the number of 128-bit blocks needed to cover the payload to be encrypted.

  Is the nonce value for $B_i$'s and $A_i$'s the same?

The CCM encryption operation takes a nonce $N$, an associated data string $A$, and a payload $P$, and returns an authenticated ciphertext.  These inputs are all uniquely encoded into a sequence $B_0, B_1, \ldots, B_r$ of 128-bit blocks for authentication.  Thus, the nonce $N$ is used to compute some of the $B_i$ blocks, and the associated data string $A$ is used to compute some of the other $B_i$ blocks.

The symbol $A_i$ does not appear in NIST SP800-38C.

  What is $l(a)$ and $L$?

These symbols $l(a)$ and $L$ don't appear in NIST SP800-38C.

  What is the minimum value of size of $m$?

The minimum value of $m$, the number of 128-bit blocks needed to cover the payload $P$, is zero: the payload may be empty, in which case CCM reduces to a message authentication code.

  Does authentication process use the data of $m$?

$m$ is a number of blocks.  CCM does authenticate the nonce $N$, the associated data $A$, and the payload $P$.  Without knowledge of the secret key, changing the lengths of any of these strings will, with high probability, cause the recipient to reject a message as a forgery.

Details.
For a 128-bit block cipher $E_K$, the inputs to CCM are:

a key $K$,
an octet string $N$ of between 7 and 13 octets inclusive, the nonce;
an octet string $A$ of any length, the associated data; and
an octet string $P$ of any length, the payload.

The authentication tag in CCM is computed first by encoding the tuple $(N, A, P)$ as a sequence of 128-bit blocks $B_0, B_1, B_2, \ldots, B_r$, as described in §A.2, pp. 12–14; then by computing $Y_0 = E_K(B_0)$, $Y_1 = E_K(B_1 \oplus Y_0)$, $Y_2 = E_K(B_2 \oplus Y_1)$, etc., setting $T = Y_r$, and revealing $$T \oplus E_K(N \mathbin\Vert 0).$$  $T$ is effectively the CBC-MAC tag for the string $B_0 \mathbin\Vert B_1 \mathbin\Vert B_2 \mathbin\Vert \cdots \mathbin\Vert B_r$.  Since CBC-MAC on variable-length messages is not itself a secure MAC, the actual authentication tag in CCM is the CBC-MAC tag $T$ concealed by the single-block one-time pad $E_K(N \mathbin\Vert 0)$.

The ciphertext is computed by adding to the payload $P$ the first $|P|$ bits of the one-time pad $$E_K(N \mathbin\Vert 1) \mathbin\Vert E_K(N \mathbin\Vert 2) \mathbin\Vert \cdots \mathbin\Vert E_K(N \mathbin\Vert m)$$ generated by the block cipher $E_K$ in CTR mode, where $|P|$ is the number of bits in $P$ (written $\mathit{Plen}$ in the standard) and $m = \lceil|P|/128\rceil$ is the number of 128-bit blocks needed to cover the length of the payload $P$.


If he chooses $s$ at random, then the scheme will be stateless but will fail after using the same $s$ twice, which should happen after giving approximately $\:$$\Theta$$\big(\hspace{-0.05 in}$
$2^{H/2}$$\hspace{-0.01 in}\big)\:$ signatures.

If he chooses $s$ by applying a PRF to $g(m)$, then the scheme will be deterministic and stateless,

but can be expected to fail after giving approximately $\:\Theta\left(2^{H/2}\right)\:$ signatures.

If he keeps an initially empty list as state, chooses $s$ at random from the leaves that are not on the list, puts $s$ into the list, and makes the list empty again if at this point it contains all of the leaves , then the scheme will need to keep an amount of state that grows linearly with the number of signatures given.

In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures.

If he chooses $s$ to be one more than the previous value of $s$ when there is a previous

value of $s$ and such a leaf, and chooses $s$ equal to $0$ in all other cases,

then the scheme will be deterministic but will need to keep $H$ bits of state.

In this case, the scheme will fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ signatures, and until that point,

each signature will also reveal and authenticate how many messages were previously signed.

That will stop an adversary from reordering the messages but will also reduce the signer's privacy.

(The following option was suggested by Paŭlo Ebermann in the comments.)

If he chooses $c$ in the way the previous paragraph described him choosing $s$, and chooses

$s$ by applying a PRP to $c$, then the scheme will be deterministic and need to keep $H$ bits

of state and fail after giving $\:2^H\hspace{-0.045 in}+\hspace{-0.03 in}1\:$ bits of state. $\:$ In this case, the scheme will enable

anyone who has the PRP's key (this will usually just the signer, although anyone else who

learns the signing key will know the PRP key too) to determine how many messages were

signed before a specific signature was given, and hide that information from everyone else.

I suspect that the most important thing is that the scheme be deterministic and stateless.


Derivation of birthday paradox probability

The probability becomes more intuitive when one pictures the $t$ persons entering one by one in the room.

Before the first person enters, there's no collision/coincidence of birth-date, thus probability of no collision is $P_0=1$.

When the first person enters, there can't be a collision/coincidence of birthdate, probability of no collision is $P_1=1$.

When the second person enters, there is one chance in $365$ that his/her birthday is the same as the first person's birthdate, thus the probability of no collision is $P_2=1-\frac1{365}$.

When the third person enters, either
- there was a collision at the previous stage, and then the probability of no collision is $0$;
- or there was no collision at the previous stage, thus there was $2$ persons with different birth-dates in the room, and the probability that the third person has one of their birth-dates is $2$ in $365$, thus the probability of no collision is $1-\frac2{365}$.
The total probability of no collision after the third person enters is obtained by adding these two probabilities weighted by the probability conditioning them. We thus have $P_3=(1-P_2)\,0+P_2\,\bigl(1-\frac2{365}\bigr)$, thus $P_3=\bigl(1-\frac1{365}\bigr)\bigl(1-\frac2{365}\bigr)$

The same reasoning gives $P_{i+1}=(1-P_i)\,0+P_i\bigl(1-\frac i{365}\bigr)$, that is $P_{i+1}=P_i\bigl(1-\frac i{365}\bigr)$.

From which it comes $P_t=\displaystyle\prod_{i=0}^{t-1}\,\Bigl(1-\frac i{365}\Bigr)$.

For derivation of formulas used in a cryptographic context where the numbers are huge, see my Birthday problem for cryptographic hashing, 101.
Note: $P$, $t$, and $365$ here are $q$, $n$ and $k$ there.


How to ensure confidentiality of an encrypted but public message given that computation power increases?

This adversary can simply wait some years for computation speed to increase and then might launch a brute force attack once it becomes feasible.

TL;DR: we don't need to protect against brute force attacks because we can choose a key size large enough to withstand those kind of attacks.

Computation speed is often linked to Moore's law. That used to say that the number of transistors / the size of the transistors doubles every two years or so. Moore's law, however, hasn't held for the last 6 years or so and is slowing down (and Intel's 10 nm roadmap is slipping as we speak, slowing it down even more).

Let's assume that computational speed doubles every two years as well. It obviously doesn't as the speed of memory / cache operations doesn't double every two years, but OK. In that case, after 10 years you would gain a speedup of 2 * 2 * 2 * 2 = $2^5$. That means that an AES-128 bit key would be $2^5 = 32$ times easier to break. You could say that AES would not offer 128 bits of security but 123 bits of security because ${2^{128} \over 2^5} = 2^{123}$. However, 123 bits of relative security is still plenty to disallow brute force.

There are other physical limits that prevent brute force, for instance, power requirements to perform the calculations. It requires 1/100th of the power consumption of the world to attack a 128-bit symmetric key, if each try uses the absolute minimum of energy required to perform the calculation. You'd better have a nuclear fusion reactor sitting next to your CPU.

So does that mean that - for instance, 128 bit AES - is enough for the foreseeable future? Not necessarily.

First of all, a fully operational quantum computer, with enough reliable, interconnected qubits, could use Grover's algorithm to bring down the security strength to $2^{64}$. Although such a quantum computer is still a very distant possibility it could be that such a QC would be fast enough to perform that many operations. You should switch to AES-256 if you're afraid of this situation. However, this won't work for many asymmetric ciphers such as RSA. You would need to switch to another algorithm that protects against attacks using quantum computers; so called post-quantum cryptography / PQC.

Furthermore, neither AES nor RSA cannot be proven to be secure. So it is theoretically possible that an attack on AES can be found that allows attacks that are faster than brute force (and do not use impossible amounts of memory). In that case, AES-128 and even AES-256 could become insecure. Fortunately, these algorithms have withstood years of attacks and we know much more about cryptography and crypt-analysis than we did in the entire human history, so finding an attack will be very hard.

Then again, modern crypto has only existed for about 50 years and many algorithms have been broken (let's assume 1970 or so to be the emergence of publicly available crypto) so it might be wise to assume that crypt-analysis will advance even more. Crypto is a relatively new field after all.

Practically speaking you may just want to monitor the advisories on key size of the different agencies in the world. One website that does this is https://keylength.com and it helpfully links to the documents issued by the agencies themselves.

Or you could go all the way and implement quantum-based key establishment and use a one-time-pad to encrypt your messages. This is provably secure against brute force attacks. It's very cumbersome though, and initial implementations fell quite ungracefully against side channel attacks.


Preserving Confidentiality and Integrity in a Public channel

Which cryptographic algorithm would they want to use?

That will really depend on the situation. To select the algorithms one should ask himself (at least) the following questions:
Which standards do you trust? Which standard do you have to use? What computations can you afford?

  Symmetric, or public key based?

It again depends on the situation. Usually you'll use a combination of both, however there are valid use-cases for using only public key cryptography (usually extremely short messages) and for using only symmetric cryptography, usually when performance is a constraint or when a shared secret has already been established (i.e. with embedded devices or in a  session resumption scenario).

  Also what type of algorithm suites best and in what key size?

The algorithms really depend on the situation given. Generally however, 128 - 256 bit symmetric encryption, 256 - 512 bit hash functions, 256 - 512 bit elliptic curves and / or 2048 - 4096 bit classical asymmetric cryptography (RSA, DSA, ...) is in use.

Considering your third paragraph:
In a nutshell, you're right. You first negotiate a symmetric key using asymmetric cryptography (RSA or (EC)DH) and then use symmetric crypto to protect your payload. What you described is basically opportunistic encryption, because neither party takes measures to ensure the authenticity of the other party. This means a man-in-the-middle attack would certainly be possible and thus an active attacker could break the scheme.

  Is there a safer way?

There is: Transport Layer Security (TLS).
TLS is the standard solution for secure real-time data transport and even has some nice security proofs. TLS can take care of all the situations you can possibly encounter: You can use a pre-shared key, you can authenticate against a server with a password (via SRP), you can use a certificate (or just a public key) for only one or both parties and even is widely deployed with famous libraries being OpenSSL, LibreSSL, BoringSSL, ....


Given a hash function; assuming domain % codomain = 0 and uniform collision distribution; how is entropy lost by collisions (not output truncation)?

Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective.

You seem to be using the standard technical term ‘uniform distribution’ in a confusing way.  Normally the uniform distribution on a finite set $A$ means the probability distribution $P$ with $P(x) = 1/\#A$ for all $x \in A$, where $\#A$ is the number of elements in $A$.

But you haven't mentioned a probability distribution so far; you seem to be abusing the term ‘uniform distribution’ to mean a function $f\colon A \to B$ with the following property: There is a single number $n$ such that for every $y \in B$, the number of elements in the domain mapped to $y$ is $\#f^{-1}(y) = n$.  (One might call such a function ‘balanced’, particularly if it's a boolean function—i.e., a function defined on bits whose output is a single bit—but this nomenclature is not standard like ‘uniform distribution’ is in probability theory.)

  It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection,

When you say ‘randomly selecting’, that doesn't specify what probability distribution you're randomly selecting by.  But if the entropy of the selection is log2(4), then clearly you mean the uniform distribution on the domain.  I recommend you specify a distribution whenever you talk about a random selection.

  and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

Yes, if $f$ is injective then $H[f(X)] = H[X]$ for all random variables $X$ with any probability distribution, including the uniform distribution.

  If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy.

Again, only if the random selection is uniformly distributed over the whole domain.

  Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

Yes, if by ‘uniform distribution’ you mean a function that has the same number of preimages $\#f^{-1}(y) \subseteq A$ for any element $y \in B$ in the image.

  In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

Let's take a concrete example.

Define $f(x) = x \bmod 4$ on $\{0,1,2,\dotsc,15\}$.  You can easily confirm that $f$ has the property you called ‘uniform distribution’—every element of the image $\{0,1,2,3\}$ has exactly four preimages.  That is, under $f$, the following sets of inputs obviously collide:

$\{0,4,8,12\}$
$\{1,5,9,13\}$
$\{2,6,10,14\}$
$\{3,7,11,15\}$

Consider the following two probability distributions on the domain of $f$:

$P(x) = 1/4$ for $x \in \{0,1,2,3\}$, and zero otherwise.
$Q(x) = 1/4$ for $x \in \{0,4,8,12\}$, and zero otherwise.

Clearly $P$ and $Q$ have the same entropy—2 bits.  What is the effect of $f$ on the entropy?

Let $X \sim P$.  Then $f(X)$ has four possible outcomes each with equal probability 1/4, so the entropy is the same: $H[f(X)] = H[X] = 2\,\mathrm{bits}$.
Let $X \sim Q$.  Then $f(X) = 0$ with probability 1.  So $H[f(X)] = 0$.

Obviously neither $P$ nor $Q$ is the uniform distribution on the domain of $f$.  If we define $U$ to be that distribution—that is, $U(x) = 1/16$ for each $x \in \{0,1,2,\dotsc,15\}$, and draw $X \sim U$—then sure, $H[f(X)] = 2\,\mathrm{bits}$, the maximum possible.


This would of course depend on your protocol and or algorithm, so it's hard to give too specific advise without details of those.

Returning the point at infinity is not necessarily an error. The usual scenario would be a point $P$ of order $n$, and some secret scalar $k$. You would want to choose $1\leq k\leq n-1$, so that $k\cdot P$ will never end up being at infinity. However, one common scenario is side-channel sensitive implementation, where we would want to blind the scalar $k$. That is, we compute $(k+\lambda n)\cdot P$ for some random $\lambda$. The result will be the same, since $P$ has order $n$, but in this scenario you could run into the point at infinity at some intermediate step.

Another case would be a computation of the form $k_1 P+k_2 Q$, which is commonly done in signature verification. Also here it is not true that you never run into the point at infinity. A more general case of this would be when you start using endomorphism-based routines. Essentially the more complex the algorithm, the harder it is to prevent running into the point at infinity.

Note that for large primes, this will never happen (that is, it is extremely unlikely). However, there may be scenarios where an attacker can control input. In that case it is possible to force the algorithm to end up at the point at infinity, which may be exploitable.

How would you deal with this? It depends. If a 30-50% slowdown is not of crucial importance (I'd argue it rarely is), then there are complete formulas. These work even when you input the point at infinity. It is well-known for Edwards and Hessian curves, but a rather recent result shows that you can also do this on prime order curves. This would solve all your problems.

If you don't want to do this, you'd have to take a close look at your protocol. Is there any possibility of a scalar becoming larger than the order of a point? Is there any point where the attacker has influence on the input data? If so, is it exploitable?


Does this polynomial have to be unique per message?

Yes, if two messages $m_0, m_1$ were encrypted with the same $r$ (resulting in ciphertexts $c_0, c_1$), we would have:

$$m_0 - m_1 = c_0 - c_1$$

This would allow the attacker to directly rederive many of the bits of $m_0, m_1$ (and it gets a lot worse if more than two messages were encrypted with the same $r$.

In addition, if the attacker recovered one of the messages, he can immediately rederive the other.

Bottom line: don't do it.


Something like $t = a m + b + c m^2$ does not seem to work, as $m^2$ is not evenly distributed in $\mathbb{Z}_p$. (Am I missing something?)

You are missing something.  Given two solutions $(m_0, t_0), (m_1, t_1)$ to the equation $t = cm^2 + am + b$ (for unknown $a, b, c$), any third solution $(m_2, t_2)$ will hold with probability $1/p$ (assuming $m_2 \ne m_0, m_1$); if $p$ is large, this exactly satisfies the criteria you're looking for.  You can see that by fixing $m_2$ and considering the possible $t_2$ values between $0$ and $p-1$; for each such $t_2$ value, there is a unique set of $a, b, c$ values that make all three equations work, and as $a, b, c$ were generated randomly (so any no set has any higher probability than any other), this means that all possible $t_2$ values are equiprobable.

This is precisely the insight that makes Shamir Secret Sharing work.

It doesn't matter that $m^2$ isn't equally distributed.  If it really bothers you, you can perform the operations in $GF(2^n)$ rather than $GF(p)$. In $GF(2^n)$, $m^2$ is evenly distributed (but, as above, it's not actually a concern).


How to compute ElGamal decryption by hand

We're not trying to compute $3^{-5}\ast 2$, but instead we're trying to compute $3^{-5}\ast 2\mod p$ for some prime $p$.
This is notation for $(3^{-1})^5\ast 2\mod p$, so if we can compute what $3^{-1}\mod p$ is, you can just plug that value in and do computations like you'd expect.
Note that $3^{-1}\mod p$ means the element $u\in(\mathbb{Z}/p\mathbb{Z})^\times$ such that $u\ast 3\equiv 1\mod p$.
For example, because $2\ast 2\mod 3 \equiv 1\mod 3$, we have that $2^{-1} \mod 3= 2$.
Or, because $2\ast 3\equiv 1\mod 5$, we have that $2^{-1}\mod 5\equiv 3$.
The quantity $u^{-1}$ ends up being uniquely defined (when it exists --- $2\ast 3\equiv 0\mod 6$ means that $2^{-1}\mod 6$ can't exist), but note that it depends on both $u$ and $p$.

A computationally inefficient (but conceptually simple) way to compute $3^{-1}$ is via Fermat's Little Theorem, which states that:

  If $a\in\mathbb{Z}$, then $a^p\equiv a\mod p$

If $a\neq 0$, this is equivalent to $a^{p-1}\equiv 1\mod p$, and therefore $a^{p-2}\equiv a^{-1}\mod p$.
So we can compute $3^{-1}\mod p\equiv 3^{p-2}\mod p$, which you can do by hand.
If $p$ is large this might be annoying, but there are some tricks to speed it up (known as exponentiation by squaring).

A more computationally efficient way to compute this quantity is the Extended Euclidean Algorithm. This requires more explanation though, and if you want to know more about it you can probably find some resources online explaining it (it's a standard topic in elementary number theory courses).


Knapsack Public to Private (Superincreasing knapsack)

Here's the idea: given $w$ and $n$, we find a number $v$ such that $vw \equiv 1 \pmod{n}$.  In your case of $w=7$ and $n=173$, we have $v=99$; such a $v$ will always exist if $w$ and $n$ are relatively prime, and can be found by the extended Euclidean algorithm.  The value $v$ allows us to map from the "hard values" to the "superincreasing ones".

Here's how it works, suppose someone wants to send you a message corresponding to the first, third and fifth indicies: to encrypt it, he takes the public key, looks up the first, third and fifth indicides and adds them $21 + 77 + 128 = 226$; he sends the value $226$ as the ciphertext.

What you (the holder of the private key) would do is multiply the ciphertext (226) by $v$ modulo $n$; that gives $226 \times 99 \equiv 57 \pmod{173}$.  You then go through the original superincreasing list to decode that, and easily see that $57 = 43 + 11 + 3$; that is the first, third and fifth indicies, correctly decoding the message.

This decoding method works quite well -- the problem with this crypto system is that it can be broken; this paper shows how an attacker can quickly decode even without the private key.


Yes, it is safe. The answer of @kelalaka (the first part, before update) it not correct.

The OP is saying that the password is a strong string which is hard to bruteforce. That's why the answer of @kelalaka the attacker, firstly, will try to brute-force is not relevant to the question. Everything @kelalaka is saying about password stretching is correct, but it is not relevant to this particular question.

I am curious why would you want to use SHA256 instead of password, if your password is complex and is hard to bruteforce. But this is another story.

I would suppose that some readers who didn't read the question attentively will vote  my answer down. Some people don't think much and just apply patterns that they have in their minds, like Password? --> hashing is bad --> use stretching instead But guys, read the question once again.


Is it possible to use the root function to attack RSA?

If root is just the function from calculus, then

at most ceil(root(n,3)) elements cleartext of  {0,1,2,3,...,n-2,n-1}

are such that root(cleartext,3) is an integer
and
when its output is not an integer, that output is not a valid signature,

since valid signatures must be elements of  {0,1,2,3,...,n-2,n-1}

.

If root is modular, then for carefully chosen large moduli n, there's no publicly known

feasible classical way to have a non-negligible probability of computing root.

However, quantum computers change things quite significantly.


Keyed digest function with odds of collision below the birthday bound?

Quite a difficult question. What you seem to need is a one-way permutation $P$. Indeed, suppose you have it of width $d$, then consider the function
$$
F(K,S,R_S) = E_{K_2}(P(E_{K_1}(S,R_S))),
$$
where $E$ is any good 64-bit block cipher (say, Simon) and $K_1,K_2$ are derived from $K$.  This function $F$ should fulfill (2) because of the encryptions of both sides and (4) because it is a permutation. To satisfy (1) and (3) the permutation $P$ must be moderately easy to compute and difficult to invert.

It is quite hard to construct such permutations on so small domains as 48-64 bits. There are so called trapdoor permutations, which are easily invertible given a secret $K'$. However, this secret can probably be found very quickly in this domain, whether we talk about RSA or HFE.

I would consider algebraic constructions. There are some interesting permutations that have a compact description but no trapdoors, hence usually overlooked by cryptographers. For instance, how about
$$
\left(X^{2^k}+X+a\right)^{s}+X
$$
 over  $\mathbb{F}_{2^n}$ from a 2010 paper? Here $a$ is a field element, and $s,k$ are integers; restrictions on them are given in the paper. Even though I am not aware of any inversion algorithm, some generic methods like Groebner basis algorithms may find a preimage faster than $2^n$. In this case, if the permutation is fast enough, you may iterate it several times as long as you still conform to property (1).


Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

Bruce Schneier foresaw your skepticism and directly answered this question in "Applied Cryptography":

  Known-plaintext attacks and chosen-plaintext attacks are more common than you might think. It is not unheard-of for a cryptanalyst to get a plaintext message that has been encrypted or to bribe someone to encrypt a chosen message. You may not even have to bribe someone; if you give a message to an ambassador, you will probably find that it gets encrypted and sent back to his country for consideration. Many messages have standard beginnings and endings that might be known to the cryptanalyst. Encrypted source code is especially vulnerable because of the regular appearance of keywords: #define, struct, else, return. Encrypted executable code has the same kinds of problems: functions, loop structures, and so on. Known-plaintext attacks (and even chosen-plaintext attacks) were successfully used against both the Germans and the Japanese during World War II. David Kahn's books [794, 795, 796] have historical examples of these kinds of attacks.

Here are the referenced books:

D. Kahn, The Codebreakers: The Story of Secret Writing, New York: Macmillan Publishing Co., 1967.
D. Kahn, Kahn on Codes, New York: Macmillan Publishing Co., 1983.
D. Kahn, Seizing the Enigma, Boston: Houghton Mifflin Co., 1991.