It is possible to encrypt a file to multiple users by using CMS Envelope Data.

Firstly, you generate a content encryption key(CEK) to use in file encryption. Then the content-encryption key is encrypted for each recipient. Then store the encrypted data and the encrypted CEKs in an Enveloped Data format. To decrypt a file each client should first decrypt the CEK then use that CEK to decrypt the content itself.

In your scenario you should encrypt each file for the users that you want them to open, and you should encrypt all files for your master user.


Your explanation is "broken in the academically sense" - there is a theoretical way to break the algorithm better than brute force. AES is broken in this way. There's also "broken in the practical sense", which means you can break an cipher in real applications or protocols. AES is still safe in this sense, because you still need too much computation power and even related keys to get the original key.

There are also different attack scenarios. You can have ciphertext-only attacks - the attacker only knows the ciphertext. That's a pretty weak attack scenario and not realistic. What if the attacker knows some of the encrypted plaintext because it has a pattern? That's the known-plaintext attack. There are some more kinds of attacks with even more help for the attacker, but they are harder to do in the real world, but even if an algorithm is broken with one of this harder threats, that doesn't mean that the algorithm can't be used anymore. AES is secure because the attacks still need too much work to get the key.


Relationship among secrecy-constant, key space and message space

HINT: here you can prove the above thing by contradiction. Start with the reverse of what needs to be proved and see you can arrive at contradiction or not. Treat $\epsilon$ as a parameter any, by the way, you are right it can be anything negligible or non-negligible.


Why haven't we proven many things computationally secure yet?

I think @CortAmmon hit the nail on the head: cryptographic structures (hashes, ciphers, etc) are specifically designed to be hard for bad guys to analyse / reverse / find patterns in. It should come as no surprise that this is a double-edged sword: they are also hard for good guys to analyse in the form of mathematical proofs.

As @CortAmmon said: historically, conjectures in geometry and number theory often stood as open problems for hundreds of years before being either proven or disproven. The cannonical example of this is Fermat's Last Theorem which took 358 years, and the development of several new branches of mathematics, to solve.

Due to the nature of cryptography (hiding information inside structure with no discernible pattern), it contains some of the hardest conjectures in all of mathematics. It should not come as a surprise that in the mere 50 years that we have been studying modern cryptography (a spec in the history of mathematics), we still have open problems.

I'll give a few concrete examples:

As far as I know, it is an open problem whether hashes in the SHA family are surjective - ie does every possible string in the output space get mapped to? Why do we not know this? Because hash functions are intentionally hard to analyse.
Many cryptographic schemes do have formal proofs of security. For example, the 1979 paper by Merkle describing a hash-based signature scheme is full of proofs that the signature scheme is as strong as the underlying hash function. It turns out that despite understanding the security of Merkle-signatures very well, we didn't like the idea of huge, slow signatures, so opted for faster / smaller algorithms that are more mathematically complex and we don't understand as well.
As an example: Lattice-based cryptography is one of the leading candidates for quantum-resistant encryption. Steven Galbraith recently gave a talk at the PQCrypto2016 conference where he listed all the branches of mathematics that are involved in understanding lattice-based schemes. He estimated that there are about a dozen people on the planet who are experts in all of those areas of mathematics. How can you hope to find subtle and complex weaknesses when there are so few experts working on the problem?

Bottom line: Math is hard, cryptographic algorithms are specifically designed to be hard to analyse, and modern cryptography is still very young in the history of mathematics.


when to do elgamal exponentiation computation

I use the notation from the linked Wiki page.

What this means is, assuming one potential receiver's public key $h$, that you can choose $y_1,\ldots,y_k$ offline and compute offline
the values $(g^{y_1},h^{y_1}),\ldots,(g^{y_1},h^{y_1})$ and store them. Observe, that these values have nothing to do with the messages you want to encrypt (which are not yet known at this point in time).

Then, when you want to encrypt some message $m$
and send it encrypted to the holder of the public key $h$, you simply take an item from the stored list, say the $i$'th entry, set the
ciphertext as $(c_1,c_2)=(g^{y_i},m\cdot g^{y_i})$ and send it. Observe, that now this only costs a single multiplication of one of the pre-computed values with the message $m$.

After having sent this ciphertext,
you remove the $i$'th entry from the list.


Is it possible to generate a 6-digit number using 256-bit encryption?

I believe the claim of using "256-bit encryption" is primarily being done for marketing purposes.

Despite the best efforts of industry experts there are many people with a limited understanding of cryptography, and they associate "bigger key sizes" with "better security."  (While this is generally true, it's a very narrow view that excludes many important security factors; besides, key size differences become almost trivial beyond a certain threshold.)  Sadly, that's a surprisingly large number of people.

Marketers know the money coming from people who don't understand the details spends just as well as money from people who do.

So what can you do about it, or what should you do about it?  Perform a security analysis reviewing what the product is capable of, given the facts you have.  Is six digits enough to stop people from guessing in the time limit given them?  Do they have a three-tries-then-lockout mechanism?  What is the value to you of the system they're protecting?  What is your risk exposure should it be violated?  Are there other access controls in place, and should there be?


what does the leading byte represent for the initial point G?

But what does the 04 at the beginning mean?

It means 'this elliptic curve point is specified in uncompressed format', that is, the $x$ and $y$ coordinates are given explicitly.

The other alternatives are :

02, which means 'this is a compressed point, where we give the $x$ coordinate explicitly; of the two possible $y$ coordinates that are compatible with that $x$ coordinate, select the one with the 0 lsbit.
03, which is the same, except you select the $y$ coordinate with a 1 lsbit.

The compressed formats are about half as long (saving space), but requires more computation (a modular square root) to use if you perform an operation that requires the $y$ coordinate.


Using HMAC-SHA256 with short passwords and sliced outputs for short-lived secure hashing

It is very hard to estimate time it takes for attacker to brute-force password.
This is because HMAC-SHA256 can be calculated billions of times per second on some devices, and there are some devices existing which take millisecond to calculate one  HMAC.

BTW, I understood that password is actually a 128-bit cryptographic key, i.e. it can may contain any bytes, right? Usually term password is used for something that is much weaker.

If your adversary has thousands of high-end GPUs or dedicated ASIC chips, it is amazing how many passwords they can try. For this reason, it is very hard trying to estimate how strong is strong enough.

Earlier very good answer from T. Pornin to question on brute-forcing: Cost of brute-forcing AES-128. Although AES-128 is different algorithm than HMAC-SHA256(128 bit key), similar formula can be used to estimate costs. Short answer: if password is 16 truly random bytes, you would not break it even if you had all the money in the world.

The output of HMAC-SHA256 indeed is 32 bytes. Should you truncate it, depending on how you use HMAC, you may risk collisions. When the HMAC is used as MAC (message authentication code), it is in fact almost customary to truncate the output. (HMAC-SHA256-128 i.e. truncated to 128 bits is quite common.) If you use it in some "hash-like" application, or if you use the function vary many times, the 128 bits is indeed below what is recommended due to the birthday effect.

BTW, when working with time estimate like 20 years, you need to remember that processing power double every two years or so (Moore's law). For that reason, if something takes 20 years, large part of processing is done within the last three years. Also, 20 years may expect that there will be some new ways to crypto analyze SHA256 can be found during the time frame (but not full break.).


You may have a look at the Schneier's blog https://www.schneier.com/blog/archives/2018/05/lc4_another_pen.html

There are two ciphers described (LC4 and Solitaire).

I am not sure a  card-pack based cipher would fulfill #4, but imho still having good strength for a field hand-only cipher

edit: now I noticed Maarten linked the Solitaire cipher too,


What are fixed points and length extension attack in hash functions?

If $H(x) = x$, $x$ is a fixed point. If for a value the output of the function is the same as the input, it is called a fixed point.

A length extension attack is unrelated to the concept of fixed points. There is a good question about understanding length extension attacks here.


Breaking an instance of (textbook) RSA encryption is: given $(n,e)$ and $c$, finding $m$ such that $c\equiv m^e\pmod n$ (meaning by definition: $n$ divides $m^e-c\ $), and $0\le m<n$.

For proper establishment of $(n,e)$, there is a single such $m$ for each integer $c$.

If we are additionally (or instead of $c$) given an integer $x$ such that $c\equiv x^e\pmod n$ (meaning by definition: $n$ divides $x^e-c\ $), then we can compute the desired $m$ as $x\bmod n$. That is the uniquely defined $m$ such that $n$ divides $x-m$ and $0\le m<n$.

For non-negative $x$, we can compute $x\bmod n$ as the remainder of the Euclidean division of $x$ by $n$. For negative $x$, we can use that $x\bmod n$ is $(n-1)-((-x-1)\bmod n)$, where $(-x-1)\bmod n$ is computed as the remainder of the Euclidean division of $-x-1$ by $n$.


Proportion of RSA moduli factorable by NFS with less effort than average?

The core difference between the SNFS and the GNFS is that the polynomials $f(x)$ and $g(x)$ for the SNFS have short coefficients, where typically the largest coefficient of $f$ is $O(1)$ and the largest coefficient of $g$ is $O(n^{1/(d + 1)})$. On the GNFS, coefficients are typically closer to $n^{1/(d+1)}$ on both sides, which results in much larger integers to test for smoothness.

So the question is: for a randomly selected integer $n$, can we find a set of polynomials, plus a shared root $m$ modulo $n$, such that their coefficients are significantly smaller than average? The answer is somewhat unsatisfying. I'll exemplify with a simple unsophisticated example, but the principle holds in general.

There are many polynomials that can fit the bill, if we don't restrict their size too much. If we let coefficients be bounded by $n^{1/(d+1)}$, then we have $n^{(d+2)/(d+1)}$ possible $f(x)$ polynomials and shared root, $n^{1/(d+1)}$ of which satisfy $f(m) = 0 \bmod n$. This would be $2^{146}$ for $n \approx 2^{1024}$ and $d = 6$.

But what happens when we try to approximate to the SNFS, by keeping $m$ fixed but reducing the coefficients of $f$? Assuming coefficients are uniformly and independently distributed, the number of available polynomials starts decreasing proportionally to the factor we want to reduce them by. For example, for $n \approx 2^{1024}$ and $d = 6$, as before, if we want to reduce coefficients from $\approx 170$ bits to $\approx 170 - 20 = 150$ bits, we find that there are only $2^{146} / (2^{20})^{6+1} \approx 78$ suitable polynomials! Significantly bigger reductions would be unlikely to exist at all, except for a few rare cases, like SNFS-friendly numbers.

All of the above was simply a counting exercise. But the idea is simple—polynomials with small coefficients, which also satisfy the GNFS requirements, are vastly outnumbered by the number of integers to factor.

Even so, it would be great to be able to find optimal polynomials for any integer $n$, even if they don't approach SNFS quality. But we don't really know how to find such optimal polynomials other than essentially brute force search and some heuristic techniques, which are nevertheless very much worth it. Given the mismatch between lower bounds and current algorithms, if the state of the art of polynomial selection were to suddenly improve significantly the answer to your question would be "every modulus".

In case I failed to convey the argument, I'll refer to §12.12 of Buhler et al., §4 Bernstein and Lenstra, §2.3.2 Murphy, §2.2.4 Coxon, or §6.2.7 Crandall and Pomerance, all of which discuss this polynomial selection issue.

Some fine print: size is not the only factor in practice to select a good polynomial. In particular, having many roots modulo small primes seems to help in finding smooth numbers. But as far as asymptotics are concerned, size is the only factor we're concerned with.


Can a computationally unbounded adversary break any public-key encryption scheme?

Yes, a computationally unbounded attacker can break any public key system.

One easy way to see this is to consider the KeyGen algorithm, which takes takes as input a value R (which in normal use is the output of some random number generator), and outputs a public key PK and a private key SK.

Now, what a computationally unbounded adversary can do is consider all possible inputs R, and see which one produces the public key that he has been given.  We know that there is at least one such input R (the one that was used when the public key was created); we can then use the corresponding private key to decrypt the message.

The obvious objection to this is "what if there are multiple such R's which generate the same public key, but different private keys?".  Actually, it turns out that this is not a problem; because each such private key SK was generated correctly by the key generation function and corresponds to the public key under attack, it must still satisfy the formula:

$Dec_{SK}(Enc_{PK}(M)) = M$

Hence, it must correctly decrypt the message, even if it was not the exact private key that the legitimate user had.


Could we use a more efficient hash for signature generation?

As mentioned in the comments already, you do not need collision resistance. You can get away with target collision resistance (TCR). The security game for TCR considers families of hash functions and requires the adversary to select the message it will find a collision for before it learns under which function of the family it has to find it. This is applicable in hash-and-sign signature schemes where you have a fixed length signature scheme that works without first hashing the message (like RSA) and then add a hash function to handle arbitrary length messages by signing their hash (like RSA-FDH). With TCR, you select a random function index and sign it with the hash.

One problem here, if you want to go for standard model security, is that the function indexes (keys) have to have length logarithmic in the message length. At least we do not know any domain extenders for TCR better than this. However, I will omit the details. A "heuristic" construction is the RMX construction by Halevi and Krawczyk.

For Fiat-Shamir based constructions like (EC)DSA things are not that easy as you cannot just "additionally" sign the index. What you can do however is to reuse the random nonce (think of $g^r$ in Schnorr) as index as pointed out by Mironov  in this paper. Actually, that paper discusses a lot of the things I just wrote in more detail.

If you want to go weaker you start getting to run into issues. If you use the hash to compress the message you are signing, you need some sort of collision resistance (which TCR is). At least, you definitely need second-preimage resistance (which one might also consider a variant of collision resistance as you actually output a collision...). If your hash is not second-preimage resistant a malicious party, after seeing a message signature pair, can always come up with a colliding message for which the signature is valid.


Can I do a forward secure half-round ephemeral-static ECDH?

I am curious if we can possibly ensure the forward secrecy under this scenario with only one round of communication.

I do not believe so; the protocol can be summarized as:

Alice publishes her long term key
Bob does some work (without having Alice do anything)
Alice does some work, and retrieves the message

If, anywhere between points 1 and 2, Alice's state was copied, then the copy of Alice's state would be able to perform step 3 just as well as Alice did, and so you don't get PFS.

Also, terminology correction: you asked whether this can be done with only one round of communication; actually, it can, by having Alice send a message at the start of step 2.  Obviously, this doesn't work for your project; what you need is actually a 'half round' exchange.


Proof that Alternating Step Generator and modifed ASG' have equivalent security?

Okay, I had a look at your source [12], e.g. ON EDIT DISTANCE ATTACK TO ALTERNATING STEP GENERATOR.

The original ASG defines the key stream Z = {z_i} from three shift registers X = {x_i}, Y = {y_i} and C = {c_i} via these steps:

  Initially, l = 0, t = 1.
  If ct = 1, then l = l + 1;
  Output z_t = x_l ⊕ y_(t−l) , where ⊕ is XOR operator;
  t = t + 1 and go to step 2.

E.g. we step one them depending on c_t, and use the latest output of both.

For the variant, we define w_i = z_i ⊕ z_(i-1), u_i = x_i ⊕ x_(i-1), v_i = y_i ⊕ y_(i-1), e.g simply the "difference sequences" of the original ones.

U = {u_i} and V = {v_i} can easily be created by LFSRs of the same length as these for X and Y, simply by adding or removing one feedback link. (And if we have the registers for U and V, we can get the registers for X and Y back.)

It now shows that we can derive W = {w_i} not only directly from Z, but also from U, V and C, using the modified construction:

  Initially l = 0, t = 1;
  If c_t = 1, then l = l + 1 and output w_t = u_l ;
  If c_t = 0, output w_t = v_(t−l).
  t = t + 1, go to step 2.

Why? Simply put the formulas:

If c_t = 1, then

w_t =      z_t        ⊕        z_(t-1)
    = (x_l ⊕ y_(t−l)) ⊕ (x_(l-1) ⊕ y_((t-1)−(l-1)))
    = (x_l ⊕ x_(l-1)) ⊕ (y_((t-1)−(l-1)) ⊕ y_(t−l))
    =      u_l        ⊕ (y_(t−l) ⊕ y_(t−l))
    =      u_l        ⊕         0
    =      u_l.

If c_t = 0, then

w_t =     z_t         ⊕     z_(t-1)
    = (x_l ⊕ y_(t−l)) ⊕ (x_l ⊕ y_((t-1)−l))
    = (x_l ⊕ x_l) ⊕ (y_(t−l) ⊕ y_((t-1)−l)
    =       0     ⊕ (y_(t−l) ⊕ y_((t-l)−1)
    =       0     ⊕      v_(t-l)
    =                    v_(t-l).

It is a bit confusing because of 1 and l looking quite similar here.

So, how would we do our attack on Z, given an attack on W?

Transform the observed sequence of Z into a sequence for W, by calculating differences of consecutive elements.
Break W, get formulas for C, U and V.
Transform the formulas for U and V back into these for X and Y by adding/removing
one feedback link.


Reusing the random exponent for ElGamal encryption with different plaintexts

No,  you can't. In this case, an attacker can compute $m_1/m_2$ by multiplying the first ciphertext for the inverse of the second and, for instance, determine if $m_1=m_2$ or not. This should not be possible in a secure scheme.


How does blockmix in scrypt work? What is the meaning of the H function in scrypt?

I'll sum up the comments: according to the original paper, $H$ is any hash function which, ideally, uses limited parallelism$^1$, with Salsa20/8 being a candidate.

Footnote 1: In order to make the resulting memory-hard function less susceptible to attacks (which make an essential use of parallelism).


It is indeed safe to send it along with the ciphertext; the attacker can't learn anything from it (other than possibly how many packets has been generated so far, if you use a counter to generate the IVs), and if the attacker modifies the IV, the resulting message will fail to decrypt (with high probability).

Existing protocols that can use GCM (TLS, IPSec) do exactly that: prepend the IV in front of the AES-GCM data.


Hash system to generate same (specified) hash from multiple datasets?

No (assuming by “better” you mean “cryptographically strong”). What you are trying to do is finding a pre-image of $X$ under the extra condition that $D_i$ must be a prefix of the pre-image. Cryptographic hash functions are designed to make finding pre-images computationally infeasible.


How to show that a function is not a PRP?

To show that a family of functions is not a PRP, you have to either show that the functions are not permutations or that they do not behave pseudo-randomly. As it is already established that the functions are in fact permutation you need to show the latter.

For a family of permutations to be a PRP means that it is computationally infeasible to distinguish a random member of the family (i.e. the function with a randmly chosen key) from a truly random permutation with non-negligible probability.
So what you need to do is present an efficient distinguisher. I.e., describe an algorithm that can in fact decide whether it is given access to a member of the family or to a random permutation.
To do that, you should consider the property that the parity of $f_k(x)$ is always equal to the parity of $x$. So for any fixed $x$ $$\Pr[\operatorname{parity}(f_k(x)) = \operatorname{parity}(x)]=1.$$ Now consider what the same probability is for a truly random permutation $g$.
$$\Pr[\operatorname{parity}(g(x)) = \operatorname{parity}(x)]=??$$


Without completely restructuring how CBC mode works, that would not appear to be possible.

Your generalized CBC mode encryption would be defined as:

$$C_i = Enc_k( P_i \circ C_{i-1} )$$

for some operator $\circ$ (which need not be commutative, or even associative).

What this means is that, during decryption, we have:

$$Dec_k(C_i) = P_i \circ C_{i-1}$$

To make decryption, that is, the recovery of $P_i$ feasible, we must have an easy way, given $A, B$, to find the solution $x$ for $A = x \circ B$.

In the problem you're asking to be infeasble, that is, $P_i\circ C_{i-1} = x\circ C_{j-1}$, if we set $A = P_i\circ C_{i-1}$ and $B = C_{j-1}$, we see that must also be an easy problem (otherwise decryption would be difficult)


How is the MD2 hash function S-table constructed from Pi?

I sent an email to Ron Rivest and got an answer back.

The digits of $\pi$ are used as a sort of random number generator that is used in the Durstenfeld shuffle (see also Knuth vol 3, sec 3.4.2).

Below is some pseudocode adapted from the description and code he sent me.

S = [0, 1, ..., 255]
digits_Pi = [3, 1, 4, 1, 5, 9, ...] # the digits of pi

def rand(n):
  x = next(digits_Pi)
  y = 10

  if n > 10:
    x = x*10 + next(digits_Pi)
    y = 100
  if n > 100:
    x  = x*10 + next(digits_Pi)
    y = 1000

  if x < (n*(y/n)): # division here is integer division
    return x % n
  else:
    # x value is too large, don't use it
    return rand(n)

for i in 2...256: #inclusive
  j = rand(i)
  tmp = S[j]
  S[j] = S[i-1]
  S[i-1] = tmp

The next function just steps through the digits of pi. You'll notice that rand does not use some of it's possible outputs. Dr. Rivest says that using these values would not give a uniform distribution as they are too large.


Take the field with $2^{15}$ elements, identify its elements with 15-bit 0/1-strings (in any linear way -- the polynomials will be dependent on the choice, but not the resulting maximal Hamming weight) and find the polynomial $p(X)$ of degree $2^{15}-1$ with $p(x) = S[x]$ for all $2^{15}$ values $x$ via Lagrange or Newton interpolation. If $p(X) = \sum_{i=0}^{2^{15}-1} p_i X^i$ then the degree you are looking for is the maximum of all Hamming weights (= number of zeros in binary representation) of exponents $i$ where $p_i\ne 0$.

So if for example $p(X) = p_7 X^7 + p_{257} X^{257}$ with $p_7\ne 0$, $p_{257}\ne 0$ then the degree is $3$, as maximum of Hamming weight(7) = Hamming weight($2^2+2^1+2^0$) = 3 and Hamming weight(257) = Hamming weight($2^8+2^0$) = 2.


How can I use Weierstrass curve operations with a=-3 for implementing operations for a=0?

I have not thoroughly investigated golang's elliptic library (or Go at all), but I have implemented elliptic curves (with Jacobian coordinates) and I would say that your guess is correct. The "$a$" parameter is not used in the addition of two distinct points, but it appears in the formulas for doubling a point. With Jacobian coordinates, a normal implementation will include core functions such as addJacobian() and doubleJacobian(), which are used only through wrappers which filter out the special cases (if both operants to an "add" are identical, then it must be a "double"; if one operand is the point-at-infinity, then the result is the other operand).

The $a$ curve parameter is supposedly used when doubling a point, and when deciding if a point is on the curve or not (by applying the curve equation). It would also be used in point (de)compression, a kind of marshalling which saves a bit of space; but point compression does not appear to be implemented in the code you link to (it is optional and rumoured to be patented, which is why it is often avoided).

I am not entirely sure that the code is correct, though. In ScalarMult(), the multiplier is not reduced modulo the curve order, so an oversized value k could imply calling addJacobian() on a point and itself, something which does not appear to be handled in the code (this should be checked: if $n$ is the curve order, try $k = n+2$; this should yield $2G$ if the code is correct).


Question on Tokenization and the need to maintain a value to token lookup

You could use for example an asymmetric keys pair, where the private key is stored on the user's device, and where the public key is saved in the server side.

At sign-in, the server send a challenge request (random bytes + current timestamp), the client need to sign the challenge and the server can verify the signature.


Which attacks are possible against raw/textbook elliptic curve?

None of those schemes define any formatting

You don't needs any input formatting for ECDSA, you just feed your plaintext into the hash function.
You only need a formatting if you want to exchange public keys and / or private keys (I'll count "with yourself" in the future as exchange here).
As far as ECIES goes, the situation is a bit more complicated. There are standards defining formats for ECIES (so you can decide how the payload was encrypted for example), but they haven't seen wide adoption (may be due to the pay walls) yet. Refer to this paper for a comparison of the standards.
EC-ElGamal isn't widely used and it's already hard to find good standards to achieve IND-CCA2 security with (EC-)ElGamal. I'd strongly recommend against using (EC-)ElGamal unless you need the homomorphic property.

  Does that mean that there a no know attacks against the raw schemes?

These schemes are different from RSA in that they are fairly "recent" and people already learned how to describe schemes when defining them, whereas the issue with RSA is that it's "just a modular exponentiation with the right exponents", these schemes are comparable in detail of specification to PKCS#1 (i.e. RSA-OAEP and RSA-PSS).

As for the security:

ECIES is a secure public key encryption scheme (IND-CCA2) assuming the hash can be modeled as a random oracle(RM) and the elliptic curve computational diffie-hellman(ECCDH) problem holds
ECDSA is a secure signature scheme (existentially unforgeable under chosen message attacks (EUF-CMA)) assuming the EC discrete logarithm problem (ECDLP) holds
ECDH is a secure key agreement scheme (provided that you authenticate the exchange and that you hash the derived point) assuming ECDDH (EC decisional DH) (or ECCDH + RM-Hash) holds.
EC-ElGamal is a somewhat secure public key encryption scheme (IND-CPA and maybe IND-CCA1, but not IND-CCA2) assuming that ECDDH holds

See our canonical "IND-" question for the basic notions.


If the implementation ensures that no (COUNT, IV#1, IV#2) tuple can ever be used more than once, and if no tuple is ever used to generate more than 264+4 bytes of keystream output, then this scheme is as secure as any instantiation of AES-CTR can be.  Of course, as CTR is not an authenticated encryption mode, it will still be malleable unless combined with a MAC.

Conversely, if an attacker can cause two plaintexts to be encrypted with the same COUNT, IV#1 and IV#2 values, then they can easily obtain the bitwise XOR of the plaintexts, which may be sufficient to at least partially recover the plaintexts themselves.  In particular, if an attacker can cause a plaintext of their choosing (or at least known to them) to be encrypted with a chosen COUNT, IV#1 and IV#2, then they can fully decrypt any other plaintext (of equal or lower length) encrypted with those same values.

Your question does not contain enough information to let us tell which of these two scenarios applies, and so we cannot say whether this specific AES-CTR instantation is secure (in the usual IND-CPA sense one would expect of CTR mode) or not.

That said, the short length of IV#1 certainly raises some concern.  You have not described exactly what constitutes a single "transmission" in this protocol, but whatever it is, there can be only 32 of them in this scheme before you'd need to rekey (assuming that nothing prevents two transmissions from using the same COUNT values).  That seems like it might be a problem.


In AES-256-CFB, does using a pseudo-unique key circumvent the weakenesses of reusing keys?

Goal: Encrypt multiple messages using the same key

That's what an IV is for! You can mitigate all the dangers of key reuse by using a unique initialization vector. The reason they exist is so that you can encrypt multiple messages without needing to go through the expensive process of changing keys (whether by generating a new random, truly independent key or by expanding one key into a number of keys with an algorithm like HKDF).

  Hypothesis: If we use, as the actual encryption key, a reused secret key concatenated with a publicly known yet varying (and never repeated) part, would that prevent exploits based on key reuse?

Your entire scheme is excessively complex and I haven't analyzed it. What I can say though is that you usually can concatenate a secret key with a public counter or other unique identifier and still treat the key as secure. A vulnerability that allows an attacker to violate some security principle of the cipher when multiple keys are used that are all secret but which differ in specific known ways is called a related key attack. Only ciphers that are badly broken, such as RC4, are vulnerable when used this way.

There is a better, standard way to expand one key into multiple though, and that is HKDF. It is a hash-based algorithm which expands a single key into any number of unique keys that can be treated as independent. This is useful because you don't have to sacrifice any part of the key by turning it into a public value. You can start with a 256-bit secret and derive any number of 256-bit secrets.


Looking for a formula for "Given $x_1$, $\ldots$, $x_{n-1}$, the output $F(x_1,\ldots,x_n)$ is dependent of $x_n$ and is of $l$-bits security"

To be well defined as a function, you need to specify lengths of the $x_i$, which is not the same thing as their entropy. Also, the $H(h_i)$ in your equation should probably be $H(x_i).$

Let's assume each $x_i$ are binary vectors of length $n$ for concreteness. Then what you want in a more general version of this problem would be
$$
\mathbb{H}(F(x_1,\ldots,x_n) | x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_n) \geq \mathbb{H}(x_i) \quad \forall i=1,\ldots,n
$$
which also takes care of the unequal entropy case for the different $x_i.$


Using a RSA signature to confirm the sender of a physical letter?

A QR code can hold a bit over 2kiB. That's plenty for a short letter and a signature. If more is needed, use more than one QR code, and number them for ease of use.


Is the length limit of AES-GCM per key or per (key, nonce) pair?

It is per message. I.e. per (key, nonce) -pair.

The reason it exists is that GCM uses CTR mode for encryption with (normally) a 32-bit counter. That means you can only encrypt $2^{32}$ blocks, i.e. $2^{39}$ bits with AES. The 256 bits that are subtracted are due to authentication.

So you can encrypt multiple maximum-length messages securely.


How does hashing help improve password security?

First, you don't actually send a hash on subsequent connection attempts, you still send the plaintext password. Second, even if you would send a hash, the same hash, every time, this hash would effectively be your new password.

Now for your actual question:

  What if someone intercepts the data at this time? What am I missing
  here?

The fact that HTTPS is used. HTTPS stands for HTTP-Secure, which means it's HTTP over TLS. Now if your browser properly validates the data it gets from the server (which all browsers do), then you can be sure that the party at the other end of the encrypted TLS connection actually is facebook.com, at which point you also know for sure that the connection hasn't been intercepted.

  It says that plaintext is not secure so servers store only hashes of
  the passwords. How this works exactly.

Assume we have a secure connection between the client and the server, that is the client knows for sure who the server is (eg facebook.com). TLS achieves this. Now for the registration send the server the username and the password you want to use. The server password-hashes the password and stores it alongside the username. Now on subsequent log-ins you send the password again, the server retrieves some parameters from your username, applies the password hash again and compares the result with the stored value. If they match, you are authenticated, if not, then not.

Why the hashing on the server? Suppose the database of the server where all the password hashes and usernames are stored gets compromised (eg an attacker gets root access to the server or can dump the database using an SQL injection), now if you have stored plaintext passwords, the attacker can immediately use these against your service and any other sevice these users may use (assuming they re-use passwords, many do). Now if you have hashes, the attacker first needs to find inputs that map to these hashes, for this they usually need to try out a lot of passwords, which is infeasible for really good passwords and even for weaker passwords takes a moment of time. So now the passwords aren't complete and utterly compromised when the server's security fails.


Is authenticated encryption unnecessary if the message is digitally signed?

Yes, message authentication can be omitted when using an appropriate digital signature on the ciphertext.

A digital signature hashes the message, then encrypts the hash with a nonce and asymmetric key, which makes the security similar to HMAC.

The reason authenticated encryption is preferred is that it is generally less computationally expensive than a digital signature, and easier to build a MAC construct that is side channel resistant.


What is preventing chaotic cryptology from practical use?

All chaotic crypto papers I have seen lack rigorous security analysis, their main shortcoming being that there is no understood mathematical machinery of the type used in non-chaotic crypto such as:

low differential probability
low linear bias
guaranteed period, window, nonlinearity properties

Also, most chaotic systems are continuous, need infinite precision real numbers to represent, so since sampling/quantization will be needed, some of the properties of chaos may be lost.

Most chaotic crypto papers appear in the general physics/engineering literature, and are not even seen by most crypto researchers.

So, why would anyone use them when there are well understood techniques with long history of resisting cryptanalysis. The chaotic crypto authors display computational evidence (equidistribution only, in most cases) and quit.

If they dont properly cryptanalyze their designs no one else will. However, typical chaotic systems are almost impossible to analyze theoretically, their state trajectories are uncontrollable, by definition.


Are GPUs inefficient for calculations on big numbers? Is RSA and EC cypto generally done on CPU only?

If you run RSA speed tests in OpenSSL you'll see that many operations are pretty fast, with the possible exception of RSA key pair generation. However, for that reason key pair generation is generally not used very often - RSA is generally not used to provide forward security in transport protocols, for instance.
CPU's have been upgraded as well, and they can perform up to 512 bit operations on large numbers nowadays - see e.g. Intel's AVX-512. Although those still come with some drawbacks I would expect that those disappear as the technology matures.
Using GPU instructions has the following drawbacks:

for top performance you generally need vendor specific code;
not all (security minded) servers will have fast GPU support;
the CPU instructions used for the asymmetric primitives are generally not the bottleneck - bulk encryption would take much more CPU power.

Furthermore, latency introduced by the PCIe bus makes the GPU most applicable for parallel operations, and the amount of parallelism for e.g. performing private key operations is usually limited.
Of course, I would imagine that e.g. a double ratchet that uses a lot of (EC)DH operations could still benefit from CUDA. But it would be a lot of work to create, to secure and to maintain.
Note: that said, I didn't perform or lookup any benchmarks for GPU's - I do run OpenSSL speed tests now and then - if just to test the new hardware that I buy.


What the specification is saying is that prior to processing, the message is padded to a full block length, with the empty message padded to a single block.

The spec on page 4 describes the input into the algorithm as:

Define $||a||_n = max\{1, \lceil|a|/n\rceil \}$, where the empty string counts as one block
Let $m = ||M||_n$
Partition $M$ into $M[1] ... M[m]$, where $|M[i]| = n$ for $ 1 \le i < m$

i.e. The number of blocks of size $n$ in a message $M$ is rounded up, and must be at least 1 before it can be passed to the $CBC{-}MAC$ portion of the algorithm.

The padding applied to the last block (which is an empty block for the empty message) is defined in formula $(1)$. In byte terms it translates to:

Set the first byte to $0x80$ (i.e. set the high bit)
Set all remaining bytes to $0$

In implementation terms, this means that you would buffer up to (and including) a complete block, and only process that block when either more data arrives, or the MAC is finalised - an empty message is thus treated as a 0 byte block that needs padding, and a full last block is not padded.

If you're not trying to implement from the spec as an exercise, the Bouncy Castle CMAC implementation should make the buffer/padding scheme clear (CMAC being the NIST standarised name for OMAC1).


Is there a system where multiple people can encrypt a message and then decrypt it in any order?

Yes, systems that allow this have a name: commutative encryption.

In practice, there are two varieties:

If A, B, C just xor in a keystream, it all commutes.  Of course, anyone seeing the intermediate results can deduce quite a lot; this may make this unacceptable for some uses.
Pohlig-Hellman (not related to the Pohlig-Hellman algorithm); we pick a global prime $p$, and everyone selects a secret value relatively prime to $p-1$; A picks $a$, B picks $b$, and C picks $c$.  Then;

Alice encrypts $M$ by computing $M^a \bmod p$
Alice decrypts $C$ by computing $M^{a^{-1} \bmod p-1} \bmod p$

If you go through the math, you'll see that:

Encryption and decryption are inverses of each other, e.g. $\operatorname{Dec}_a(\operatorname{Enc}_a(M)) = M$
It commutes just like you asked: $\operatorname{Enc}_b(\operatorname{Enc}_a(M)) = \operatorname{Enc}_a(\operatorname{Enc}_b(M))$, etc
No one can deduce anything by observing intermediate results (assuming that the prime is large enough to make the DLog and Diffie-Hellman problems hard)


Given $n$ bits, how many "truly random" sequences/numbers can be constructed?

I'm not certain but aren't there ways to evaluate a given sequence as random with some given satisfied error? Given n bits, how many "truly random" sequences/numbers can be constructed?

If you define "truly random" as meaning prior to generating the sequence, that each bit has an independent 50% chance of being 0 or 1, then all $2^n$ bit strings are equally likely. By that definition you can reject none of them.

So, there is not a way to "evaluate a given sequence as random". However, some random data may contain detectable signals. Good RNGs produce these signals sometimes because they are in the set of all possible results. Badly-constructed software RNGs produce these detectable signals more frequently than by chance. A well-known example of a bad RNG like this is the randu generator.

The NIST tests, and those like it (I've used the Dieharder suite for a PRNG), do not detect randomness. Instead they detect signals in the noise. If a RNG produces a clear "FAIL" signal for every (or nearly every) sequence that it produces, then it is considered a poor RNG, because an attacker who wanted to predict its output could use knowledge of that signal to reduce the amount of guessing they need to do to (to figure out a secret key, for instance).

If a good RNG produces a "FAIL" signal every now and then, then this is  not very meaningful. In fact you normally just set a p-value for the test, and a good RNG will fail with that exact probability each time you use that test against its output. You could even run a meta-test, where a good RNG can be expected to generate a certain number of failures from a test. In that case, you need to define a p-value for the meta test, which of course the generator might fail, and you could have a meta-meta-test . . .

If a specific sequence produces a "FAIL" signal from a test like one of the NIST suite, this is generally meaningless. Ideally, you should go back to your source and generate another sequence to see if that signal is consistently appearing in its output - i.e. you should test your RNG source, not the sequence itself.

You cannot meaningfully say: "This sequence is not random."
You can meaningfully say "This RNG is predictable."

It is still possible to assess a large enough individual sequence against the NIST tests or similar, and to declare it fit for some purpose or other. For instance, perhaps you have an RNG which you don't trust (it could hardware fail, or might be tampered with)? In which case you could decide to reject "suspicious" outputs from it. There is no fixed standard for that. You get to decide where to set the bounds. Worse than that, by filtering out test "FAIL" sequences, you make the output less than truly random. However, as that would be by some small factor - perhaps 5% of sequences might get rejected - it would not give an attacker much of an advantage, so it is something you could consider if you had good reason - such as a real possibility of someone tampering with your system's RNG.

This sort of sequence rejection is close to your proposed $F(n)$. You would have to implement a specific version of it before you could answer "what is sum $F(n)$ over all $n$?". You would want to keep that value as high as you can whilst cleanly rejecting sequences that represented hardware failure, tampering, use of incorrect RNG, or other failure modes that your test was protecting your system against. Allowing a low value - e.g. accepting only 1 in 10 attempts as being "random enough" - would make your RNG process less efficient, and might make your RNG more predictable to an attacker.

You could look at analysis like the Receiver Operating Curve if you need to quantify how well your system disambiguates systemic failure of the RNG compared to normal variation in a good RNG. Optimising the area under the curve would be a sign that you have a good series of tests, then you can set test p-values depending on the risks associated with false positives (rejecting random data) versus false negatives (accepting tampered data, or from a bad RNG).

If we take a very naïve view of the NIST test suite, we can set upper and lower bounds of "Sum $F(n)$ over all $n$" as follows:

There are 15 separate tests listed on NISTs web site.
You arbitrarily set a rejection p-value of 0.01 for your test, and reject any sequence that fails 1 or more tests.
The proportion of sequences that pass any single test is almost exactly 0.99 - by definition, you are rejecting 0.01 of anything that could happen.
A lower bound on your value is when each test finds a mutually-exclusive set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" > $0.85 * 2^n$

This is not a correct assumption, but it does set a lower bound. This is quite an encouraging value, since rejecting 15% of sequences from a perfect RNG does not give an attacker much to work with, and you have clearly included obvious failure modes such as all bits 0 or 1, and many repeated patterns.

An upper bound on your value is when each test finds the same set of "suspicious" bit strings. That would suggest "Sum $F(n)$ over all $n$" < $0.99 * 2^n$

This is not a correct assumption, because otherwise there would be no point in having the separate tests.


Is there any additively homomorphic schemes that can make range proof?

Yes, you can use Paillier encryption as the homomorphic encryption scheme, and prove the encrypted plaintext falls within a range.

An interactive protocol can be found in Appendix A of this paper: Fast Secure Two-Party ECDSA Signing, by Yehuda Lindell, Crypto 2017.

A non-interactive protocol can be found in this paper: Non-interactive Zero-Knowledge Arguments for Voting, by Jens Groth, ACNS 2005.


Binary neural network encryption quality

What you are trying to do is fundamentally incompatible with cryptographic methods as would be described by this site.  You are looking at an analog input, and analog output, and a lossy compression.  Neural networks by definition have a stochastic behavior because the axon->dendrite interface is inherently unreliable.
There is a body of work in the encryption of analog signals with chaotic oscillators.  I would personally not call it encryption because there is loss, but the brain or machine learning can figure out the output.
The basis of this is Chua's Circuit, and if you look dig around in libraries you can find how these different compression methods were handled in the 90s during the analog to digital channel transistion.


Security effects of the seed's length in OAEP

Let's start with the preliminaries. The basic scheme has encryption defined as follows:

$$\mathcal{E}^{G, H}(x) = f(x \oplus G(r) || r \oplus H(x \oplus G(r)))$$

Some definitions:

$f: \{0,1\}^k \rightarrow\{0, 1\}^k$ is a trapdoor permutation where $k$ is the security parameter
$x$ is the message to encrypt
$n = |x|$ is the bit length of the message
$k_0 = k - n$ (the value of interest in out case)
$G: \{0,1\}^{k_0} \rightarrow\{0, 1\}^n$ is a "generator" from $k_0$ bits to $n$ bits
$H: \{0,1\}^n \rightarrow\{0, 1\}^{k_0}$ is a "hash function" from $n$ bits to $k_0$ bits
$r \gets \{0, 1\}^{k_0}$ is a randomly selected $k_0$ bit string

The general idea behind setting $2^{k_0}$ to be much larger than the adversaries run time is to prevent the adversary from having a non-negligible chance of brute forcing the value of $r$. Recall that $r$ is a random $k_0$ bit string so there are $2^{k_0}$ possible values of $r$.

Suppose that $k_0$ was selected to be only a couple bits, in this case $\mathcal{E}^{G, H}$ is not secure under a chosen plaintext attack (IND-CPA). For an intuition of how to prove IND-CPA see this graphic. Briefly, if an adversary submits messages $m_0, m_1$ to be encrypted by $\mathcal{E}^{G,H}$ and gets back $c$ it needs to determine if $c$ is the encryption of $m_0$ or $m_1$. Here's how it does that:

$G$, $H$, and $f$ are all public , so the only unknown in the equation is $r$, which was randomly sampled. If $r$ is small enough (i.e. if $k_0$ is small) then an adversary can compute $\mathcal{E}^{G, H}(m_0)$ and $\mathcal{E}^{G, H}(m_1)$ for all possible values of $r$. Once it computes a value that matches $c$ the adversary knows that $c$ is the encryption of whichever message was input into $\mathcal{E}^{G, H}$, which means it has a non-negligible advantage in the IND-CPA game (i.e. the scheme is not IND-CPA).

So naturally we want to pick a $k_0$ that is large enough such that an adversary is unable to brute force the value of $r$. This implies the definition that $k_0$ be chosen such that the adversary's running time is significantly smaller than $2^{k_0}$ steps.

So to conclude, for values $k_0$ that are very small the results are catastrophic as you lose semantic security. For values $k_0$ that are very large there's no security drawback, but your permutation $f$ needs to be bigger which generally translates to a slower scheme (think RSA2048 vs RSA4096 for example).


Prove that the following MAC is insecure

I won't give the answer to homework questions, but I will give a hint.

Suppose you learn the tags for $m_1 || m_2$ and $m_3 || m_4$; what other messages could you deduce the tags for?


Prove you computed $hash^r(input)$ for some cryptographic hash function

Though a formal proof eludes me at the moment. I believe I can make a compelling argument this can't be done.

If what you want is for a prover to supply the output and some extra evidence. And the verifier should be able to convince himself with high probability it is correct with effort orders of magnitude less then computing the hash himself.

Even if the prover provides the full chain, a forger will be able to swap just a singls hash and compute any additional stuff on the forged chain. Other then checking the single forged hash( 1 in r) there is no way for the verifier to catch this. If the verifier checks even half of the steps at random that still gives the forger a 50% chance of succeeding(going undetected). You presumbly want the verifier to check only a handfull of hashes but that would give the forgery excellent chances of going undetected.

In order to get high confidence the verifier would have to do almost all the work of computing the r hashes himself.


Is it possible to derive the midstate of a sha256 hash?

SHA-256 is computed by first padding a message $m$ and then breaking $\operatorname{pad}(m)$ into $\ell$ blocks $m_1, m_2, \dots, m_\ell$ of 512 bits each.  The padding appends some bits to the message so that it is an integral multiple of 512 bits long.  Then the SHA-256 hash of $m$ is $$f(\cdots f(f(\mathit{iv}, m_1), m_2) \cdots, m_\ell)$$ where $f$ is the SHA-256 compression function and $\mathit{iv}$ is the standard initialization vector.  This means that given $\operatorname{SHA256}(m)$ you can compute $\operatorname{SHA256}(\operatorname{pad}(m) \mathbin\| m')$ for any suffix $m'$.  But you can't necessarily compute $\operatorname{SHA256}(m \mathbin\| m'')$ unless $m''$ coincides with the padding on $m$.


Is $H'(M) = 5M + 9H(M) \pmod{2^n}$ a secure hash function?

Consider

$$H(M)= 9^{-1} (E(M) - 5M) \pmod {2^n}$$

where $E$ is encryption using a random permutation with an efficiently computable inverse $D$. This is a secure hash for the same reason the  Matyas–Meyer–Oseas construction is.

Now using your definition of $H'$ we obtain:

$$H'(M)=5M+9H(M) = 5M + (E(M) - 5M) = E(M) \pmod {2^n}$$

Thus $M = D(H'(M))$ can be recovered and $H'$ is not a secure hash for all secure hashes $H(M)$.


mixing two asymmetrical random number generator streams

You can slow the faster stream down to match the slower (e.g. throw away about half the bytes) and use Knuth's algorithm. You will only run at the speed of the slower, but that's the only way to assure full entropy when only one of the streams is unpredictable.

If you want to also account for cases where both streams are only partially unpredictable, you could use a hash instead. E.g. take the SHA-256 of the concatenation of 40 bytes from stream A and 17 bytes from stream B, then truncate that to 17 bytes. For example, if the high bit in each input byte was predictable, this hash would still be completely unpredictable, while the XOR would not.

However, hashing may lose some entropy in the case where stream A is completely predictable, but stream B completely unpredictable.


If your alphabet (set of all possible characters) has size $s$ and your password has length $l$, a randomly generated password has a strength of $\log_2s^l = l\cdot\log_2s = l\cdot\frac{\log_{10}s}{\log_{10}2}$ bits.

This means if you want to create a 128-bit password using a 80-character alphabet, you need at least $\left\lceil128\cdot\frac{\log_{10}2}{\log_{10}80}\right\rceil = \left\lceil20.25\right\rceil = 21$ characters.

In practice, humans aren't very good at creating random passwords; and the greater the alphabet gets, the greater gets the bias. Non-random password (e.g., sets of dictionary words) are even worse (as low as 1 bit of entropy per character).

If possible, you should generate your passwords randomly (with a program, not by hand) and store them with a password manager, or use a KDF (as Thomas already suggested in the comments). Trucrypt actually uses PBKDF2 for key derivation. (source)


Is there a quick way to know the length of a message hashed using SHA3?

In some specific cases the answer is yes, in other cases the answer is maybe. SHA-3 has four flavors 224, 256, 384, and 512. Now the “block length” given a particular version is 1152, 1088, 832, and 576 bits respectively. Block length is in quotes because this is only the first step in message pre-processing.

All this means is that given the particular variation of SHA-3 that is being processed, the input message will be broken down into 1152, 1088, 832 or 576 bit chunks. Keep in mind this step is completed before any padding actually occurs so the last chuck doesn’t necessarily have to be one of previously mentioned lengths.

Now you have a_set_of_bit_strings, and we’re interested in the last location, or a_set_of_bit_strings[-1] as per python’s notation. At this particular location if the length of the bit string is not one of the following values 1152, 1088, 832 or 576 it will be padded to one of those lengths as outline in FIPS 202.

Next based on the particular SHA-3 implementation all bit strings contained in a_set_of_bit_strings will be back appended with zeros until their length is 1600 bits as per the width specified in FIPS 202. For the purpose of my explanation I DON’T consider this step padding, because it’s not variable based on input message length. People like to use "sponge" to describe this, but I feel it just adds confusion (I don't mean the crypto definition, I mean it's just misinformation). It just means that over each iteration of SHA-3 security(ie collision resistance) is achieved through bits that aren't included in each "block", because in reality the XOR operation can be manipulated to shift all leading bits to either 1 or 0, but you have no control over tailing bits. Hence the strongest version SHA-3(512) splits the message input into the least number of bit chunks!

Things get interesting when the message you’re trying to hash has a bit length that is an integer multiple of one of the following values 1152, 1088, 832 or 576. In this particular situation no padding occurs, and instead an empty string is appended to the end of your message. Why this happens you can determine for yourself.  It’s also important to note that this empty string is then passed to the padding protocol outline in FIPS 202. So to answer your question if the bit length of your message is an integer multiple of 1152, 1088, 832 or 576, and matches with its respective SHA-3 implementation, then yes, if you hand me a_set_of_bit_strings[-1] and it’s equal to ‘’ (An empty string) then I’ll know the input message’s length is an integer multiple of 1152, 1088, 832 or 576. But this is a very specific situation. Past this I have not investigated.

I’ve included my SHA-3 bit orientated code below, it’s gross and hacky but it might help you see what’s happening at the end points. The function you’d be interested in would be sb(), and should investigate value set_main[-1] in sb() . If you want to check it against other open source implementations use online_convert().

Link to SHA-3 Code

I will investigate values that aren’t multiples of 1152, 1088, 832 or 576.


What is the difference between zk-SNARK and NIZK?

A ZK-SNARK is a NIZK (more precisely, a non-interactive zero-knowledge argument of knowledge in the common reference string model) which is succinct, meaning that both the proof size and the verification time grow sublinearly with the witness size.
Therefore, every ZK-SNARK is in particular a NIZK (but not all NIZKs are ZK-SNARKs).
Pinocchio provide a ZK-SNARK (using their general scheme that targets arbitrary NP computation), which is therefore also a NIZK.


Need to generate new DH keys for every message in OTR

Well it makes the arguments about PFS stronger.

If they would not frequently do a re-keying and securely erasing the old key (note that then they can not even read their own past messages anymore) an adversary that breaks either into Alices or Bobs computer and gets the shared secret can read and link all the previous communication between Alice and Bob. Re-keying eliminates this problem. If you do a re-keying and key erasure after each message, you have the strongest forward secrecy guarantee (although this may be a bit paranoid - but it does not cost really much either).

Note also that the deniabiliy is only concerned with the MAC keys and does not reveal the encryption keys. If you have the DH shared secret you can recompute all keys (in particular the encryption keys) previously used. Someone other may use a previously published MAC key to generate some MAC for a message (deniabiliy), but note that the corresponding correct encryption key can only be known to someone who knows the shared secret. So the adversary can tell apart original from "faked" messages. The longer you use the same shared secret the longer the conversation history the adversary can reconstruct.


How to provide integrity even though using Authenticated Encryption?

There are several concepts of integrity. Authenticity can be thought of as integrity of the association between data and its creator/modifier/sender. There is also integrity of the internal structure of data and multiple integrity definitions inside database management.

Note also, that cryptography cannot help to prevent integrity violations, it can merely help to detect them. Thus, when I mention that integrity is enforced cryptographically, it means that there are cryptographic means to detect unauthorized modifications, not to actually prevent any. In its strictest sense of the word, cryptography can not preserve integrity either.

Not all integrity concepts are straightforward to enforce cryptographically. Thus, the answer to the question depends on the exact definition of data integrity: if we consider the individual data item or content structure visible to Alice, the integrity of that is preserved.

However, considering the integrity of the history of versions of the database, integrity is not preserved.

If Eve has such access to the database that she is able to masquerade as Alice to the database, not much can be done. I assume in the following that Eve's access to the database does not include access to the database private keys or the authentication process between database and Alice.

To prevent unauthorized rollbacks such as these, versioning control is basically required. The database should have internal structures (metadata) indicating the latest update number, and Alice should include this number in her authenticated data. To enforce the association cryptographically, the database would need to sign the db-internal version number together with the version sent by Alice during each update. Bob can then compare the signed db-internal version to the version by Alice inside her authenticated data.

An alternative method to do this is, of course, blockchains. They are append-only databases, where rollbacks are not feasible. With blockchains, Eve's access to the database could be wider, and still rollbacks would be unfeasible. However, integrating blockchain-functionality into conventional databases would be a separate topic in itself - but if the rollback is a major problem in a database designed for some large-scale but well-defined function, blockchains might be worthwhile.


Yes, because instead of a Caesar cipher you now have a One-time pad.
In particular, it meets the requirements of a key that is random and as long as the message. So as long as the key is kept secret and never used for another message, you have OTP security.


EdDSA point encoding difference between documentation and implementation

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?

First of all note that;

# Points are represented as tuples (X, Y, Z, T) of extended
# coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

So the zinv comes from there and

x = P[0] * zinv % p
y = P[1] * zinv % p

Uses to find x and y
Now the last line does what the RFC describes in a simple way.

int.to_bytes(y | ((x & 1) << 255), 32, "little")

The code is just a demonstration of the result. In your programming environment, you can use copy bit by bit, and it will be way slower.
A bitwise or operation is much faster than bit by bit copy. Also, as you can see there are no range check or if to check boundaries. Since the formula is fixed you can use whatever optimization is needed as longs as your code doesn't leak information.
Final note: you restrict yourself with the bit-by-bit copy. Doesn't the result copy the values into the return value?


Does a masked look-up table prevent cache timing attacks?

After going through this, you can use bit slicing to mask power and timing of data.  This is because it does not leak any information if you interrupt that calculation that is useful to reconstruct and identify the type of calculation.  Having said that, it's very slow and you wouldn't want to do it.  I'm going to just use my cache description from a previous side-channel attack question.

The general idea behind cache timing attacks is that you can create a memory collision in the tag table of the cache so that you can know which index is being reloaded.  This attack works very well against a lookup table, which is how everyone would probably calculate this in software, which is a pre-calculated array.

Can you calculate this bit-wise in software to get around these attacks?  Absolutely, but it will be very slow to execute.  I did this type of implementation for the AES S-Box because I was trying to support simulation for my semiconductor implementation and I wrote it an BASH. It was terrible, but it gave me an easy way to extract strobes (For this same purpose, I have a complete AES implementation in BASH and it's not pleasant.  It takes about 1 second to compute a single block with AES256).

There's a paper by Satoshi et al that I used for the mathematics, which gives
$$\left(n_1x+n_0\right)^{-1}=n_1\left(n_1^2\lambda+ n_0\left(n_1+n_0\right)\right)^{-1}x
+\left(n_0x+n_1\right)\left(n_1^2\lambda+n_0\left(n_1+n_0\right)\right)^{-1},$$
which becomes the following circuit:

You would have to make a bit-slice implementation for each of those blocks in the figure.  And having done that, i'm going to guess that in a C implementation it's going to be 100x slower at a minimum than just using a lookup table, but I do not believe that you will leak any useful data because there's no way to identify from cache misses or power the values that you are calculating.

If you have a "masked" value, it must not be logically masked, but functionally masked.  The means that branch-index returns must not be used for values, and everything must be explicitly calculated. Therefore a XOR mask alone is insufficient to hide the data.


Entropy as defined in information theory and cryptography is a difficult concept. One of the most common fallacies is that a piece of data has or "contains" entropy by itself. People who misunderstand this talk about bit streams having entropy, or measuring entropy of a piece of data. Or measuring entropy of a RNG.

To measure entropy you need a data source, plus a model. You compare the predictions given by the model (which are usually a-priori probabilities of certain results) with results from the data source (actual values received, and the probability of getting that result that the model provided before you looked) in order to assess the entropy generated by the data source with respect to the model*. What that means is the value you get for entropy varies depending on how you construct your model.

When considering security of a system, you can look for an "attack" model that tries to reduce the entropy of the system it measures by predicting its results. A successful attack model has a low measure of entropy against its target system.

Generally when looking at attacking cryptographic RNG systems, we look for the best possible model, and declare that the source being attacked has X entropy under that model. This sometimes gets conflated into saying a source (or password) has so many bits of entropy.

With that view, there is a sharp divide between good quality PRNGs and TRNGs. Namely, if your model of the PRNG is accurate and includes the correct seed then a PRNG has effectively zero entropy. But without the seed, and assuming a good quality PRNG, then we don't know of any practical models that can differentiate between a PRNG and a TRNG (also assuming the latter is properly whitened). That is, all known models fed with output from either a PRNG with unknown seed or TRNG will measure the same entropy (with statistical variation within expected bounds) Theoretical models can differentiate, because you could demonstrate a finite state by running e.g. $2^{256}$ iterations and seeing repetition.

This is partly self-defining. If a practical model was found that could separate a PRNG used for cryptography from a TRNG, and that demonstrated by showing a lower measure of entropy, then the PRNG would likely be abandoned for cryptographic use.

  Does a TRNG generally provide more security than a PRNG?

In a theoretical model where you could make enough observations to figure out some of the state of a PRNG, then a TRNG that was essentially the same PRNG plus regular re-seeding from an unpredictable source would have higher entropy against that model.

The caveat is having an unpredictable source. TRNG sources are measurements of physical processes which have been chosen to be very difficult to predict (or for thermal noise or quantum sources, where the best theories to date model them as inherently random). The assertions about the source being unpredictable could turn out wrong. Or a more likely problem is that either the source or measurement process could be tampered with or intercepted.

So a short answer, with caveats, could be "Yes, a typical TRNG design could be considered more secure than its own PRNG component, because successful attacks against it would involve more work."

However, that is not the same as saying "This PRNG supplies less entropy than this TRNG" - without a qualifying model, the statement is meaningless.

* It is sort of possible to estimate entropy contained in a piece of data, but this is not as well defined, and is usually based on some assumption such as comparison with a simple model of a TRNG, compressibility etc. It is unwise to use these kinds of estimates when dealing with more formal definitions of randomness.


Is it possible to narrow down the possible keys used for AES CBC encryption, knowing a given plaintext and its ciphertext, where IV=0?

Very simple, attacks on the block cipher mode of operation do not translate to attacks on the block cipher itself. The block cipher is simply a component within the mode of operation after all.

The only time where the block cipher may come under attack is if the key is somehow changed to a related key in the scheme. This is somewhat of an issue for AES-256 if it is used as component for a secure hash algorithm, where the key schedule becomes an issue. That has absolutely nothing to do with CBC mode for a particular key as in your question.

AES, as a block cipher, is supposed to be not vulnerable against known plaintext attacks. As such, the key cannot be found by knowing any information about the plaintext. So you are indeed dead in your tracks.


Is there a simplified article, video, or blog about bulletproofs?

I found this blog post on the MIT Digital Currency Initiative's website super informative yet introductory. Hopefully, you find it helpful as well.


First: Analyzing code is off-topic on this site, don't expect much.

To the question: "Never write your own crypto" is a statement, that is all too often disregarded. Without digging deep, it looks like some self-made (and totally insecure) algorithm: The key is not used at all, therefore it is basically a streamcipher (one symbol at a time) with a deterministic keystream.

Recommendation: Do not use this, and don't use their crypto implementations in the future. Not every error is as easy to detect as this one. And in crypto you can do lots of things wrong.


Simulation based proofs: Simple examples

I have written a tutorial on how to write simulation-based proofs. I think that it should be helpful.


Why do we need to hash both the message and the $h$ value in ElGamal signature?

It's not a complete answer because an adversary needs control on the random choice of a signing algorithm.

First let me define ElGamal signature to not get lost in notation.
$x \in N$ is the secret key.
$p$ is a prime, it defines $Z_p^*$.
$g$ is a generator of $Z_p^*$.
$y=g^x$ and the public key is $(p, g, g^x)$.
Then $k$ is picked at random from $0<k<p-1$,
$r = g^k \bmod p$, $s = (H(m) - xr)k^{-1} \bmod (p-1)$ and the signature is
$(r,s)$.
Suppose we know two signatures of the message $m$ for different $k$-s:
$\sigma_1 = (g^{k_1} \bmod p, (H(m) - xr)k_1^{-1} \bmod (p-1)) = (r_1, s_1)$ and
$\sigma_2 = (g^{k_2} \bmod p, (H(m) - xr)k_2^{-1} \bmod (p-1)) = (r_2, s_2)$.

Let $\sigma_3=(r_1r_2 \bmod p, s_1 + s_2 \bmod (p-1))$.

Verification of $\sigma_3$ leads us to an equation $(k_1+k_2)(k_1^{-1}+k_2^{-1})\equiv 1 \bmod (p-1)$. If an attacker can choose $k_1, k_2$, then he can probably find proper $p$ and $k_1, k_2$. Otherwise - still a problem.


Is this a safe way to prove the knowledge of an ECDSA Signature?

Any EU-CMA-secure signature is indeed a proof of knowledge of either a signature of this document or the private key.
So, what you have done is using of second ECDSA signature as a proof of knowledge of discrete logarithm $s$. This completely makes sense, and I don't see any attacks on this.
Between, as a proof of $s$ you can use also Schnorr signature or Schnorr NIZKP - it has a property of zero-knowledge in random oracle model (while DSA has no such property).
Also, this idea of chaining signatures in this way is used in identity-based Galindo-Garcia signature, where 2 Schnorr signatures are chained.

But I can't answer you completely with a proof of security.
 At first, we need a rigorous formal model of attacker.
This cryptographic primitive (proof of knowledge of signature) is not very widespread and seldom considered.
Some works are devoted to this problem though, you can look here: https://link.springer.com/chapter/10.1007/978-3-540-47942-0_9# .
 Aldo, DSA signature has poor provable security in general (compare to Schnorr one).
E.g., if you used Schnorr signatures in this way - I would exactly say that it's secure (because Galinda-Garcia identity-based scheme is provably secure).
And, this solution could be safe on practice, but it lacks ZKP property for sure, so researchers mostly devote their efforts on other constructions, which provide ZKP.

Don't consider my answer as complete and accurate, this is just general abstract thoughts. I hope it will help you a bit.


What's the proper choice for the block size of a sponge-based hash?

The "block size" matters for Merkle-Damgård functions because the HMAC security proof relies on that block size. For other functions, and in particular sponge functions, the block size for HMAC is mostly a matter of convention.

In fact, HMAC uses two nested calls to the function because such a construction is more or less needed to ensure security with MD function. This is widely considered to be a flaw in the Merkle-Damgård construction. Sponge functions are supposed not to have that flaw, so a simple $H(K || M)$ should be a secure MAC (assuming a proper definition for the concatenation to avoid ambiguities).

So why HMAC is not formally needed to make a MAC out of a sponge function, it can still be used, and any "block size" will work, with no problem to security. The only constraint is that the block size must be larger than the hash function output size, because HMAC mandates that when the key is longer than the block size, the hash of the key is used instead; this cannot work if the block size is smaller than the hash output.

In the case of Keccak, the submission package states in section 5.1.1:

  Several standards that make use of a hash function assume it has an input block length and a
  fixed output length. A sponge function supports inputs of any length and returns an output
  of arbitrary length. When a sponge function is used in those cases, an input block length and
  an output length must be chosen. We distinguish two cases.

  For the four SHA-3 candidates where the digest length is fixed, the input block length
  is assumed to be the bitrate r and the output length is the digest length of the candidate
  n ∈ {224, 256, 384, 512}.
  For an instance with variable-length output, the output length n must be explicitly
  chosen to fit a particular standard. Since the input block length is usually assumed to
  be greater than or equal to the output length, the input block length can be taken as an
  integer multiple of the bitrate, mr, to satisfy this constraint.

And then, in section 5.1.3:

  HMAC [1, 25] is fully specified in terms of a hash function, so it can be applied as such using
  one of the Keccak candidates. It is parameterized by an input block length and an output
  length, which we propose to choose as in Section 5.1.1 above.

  Apart from length extension attacks, the security of HMAC comes essentially from the
  security of its inner hash. The inner hash is obtained by prepending the message with the
  key, which gives a secure MAC. The outer hash prepends the inner MAC with the key (but
  padded differently), so again giving a secure MAC. Of course, it is also possible to use the
  generic MAC construction given in [6], which requires only one application of the sponge
  function.
  From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing
  attack that requires much fewer than 2c/2 queries and significantly less computation than
  a pre-image attack.

So, in the case of Keccak (thus, presumably, SHA-3 too), the "block length" for HMAC is to be $1600 - 2x$, where $x$ is the hash output length, in bits (the "bitrate" and the "capacity" are such that their sum is $1600$, and the capacity is twice the hash output length).


Comparison: complexity measures vs. security

Not sure what you are trying to do but are you not approaching it the wrong way?

NIST already recommends algoorithms/ciphers for use in their environments. This means they have vetted these and are deemed secure. Now you want performance as well. So use openssl and see which of the algorithms are of acceptable performance to you. Like you said choose key lengths that provide the same level security when comparing different algorithms. That way your performance numbers will be comparable.

Also I wouldn't try to go beyond any algorithms NIST recommends. For example AES is good for any application. There is no reason to use or try twofish. There are enough ways to shoot yourself in the foot just by using AES itself. Stick to one and that way even if you are creating some recommendations for your users/employees its less complicated.

Hope that helps.


How to break an arbitrary XOR and Rotation based encryption?

XOR operations, fixed bit movements (as in taking the 2 topmost bits or
concatenating bits etc.) and data dependent rotations form a
functional complete set of operations. This means that you can realize
any function between fixed length binary strings, including all possible
blockciphers, using them.

To show that these operations form a functional complete set one can show that
all operations of another functional complete set can be realized. For example
the set {NOT, AND}:

Realizing a NOT operation is easy, since this is only a XOR operation with
a 1 constant.
Realizing an AND operation requires the data dependent rotations. Given the
inputs $a$ and $b$ construct the value $v = RotLeft_{a}(0b)$. The leftmost
bit of $v$ is now the result of the AND operation of $a$ and $b$. This can
be verified by looking at the possible input values: If $a$ is zero the
rotation is does nothing and the leftmost bit stays zero. If $a$ is one the
rotation will move the value of $b$ to the leftmost bit and the result is
one exactly if $b$ is also one.

This would turn any algorithm that could break any cipher based on these
operations efficiently into an algorithm that breaks any arbitrary cipher
efficiently, unlikely to exist and certainly not known.

Nevertheless I would not assume that most or even many of the ciphers
constructed from these primitives are secure. For example: if there are only
few data dependent rotations and it is feasible to enumerate all possible
rotation count combinations, the system can be broken by just trying to solve
the resulting linear system for each combination.


Is there such a thing as shortcutable key stretching?

Let $p$ and $q$ be secret uniform random primes, and define $n = pq$.  Consider $s = 2^{2^t} \bmod n$.

Without knowledge of $p$ or $q$, the best way we know to find $s$ is to start with $2$ and square it $t$ times successively.  We can tune $t$ to force the other party to take arbitrarily many steps.
With knowledge of $p$ and $q$, we can use the shortcut $2^e \equiv 2^{e \bmod \lambda(n)} \pmod n$ by Carmichael's theorem, since $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$; then it only takes one division of $t$ by $\lambda(n)$ and about $\log_2 n$ squarings and multiplications modulo $n$ to compute the answer, no matter what $t$ is.

But suppose you use this protocol.  What happens when one of the parties skips town just before the protocol is done?

  BOB: Hey, Alice, the combination to the box the magic words are in is $2^{2^{t_b}} \bmod n_b$ where $t_b = 1\,000\,000\,000\,000$ and $n_b = \dotsb$.

  ALICE: Great!  The secret to the meaning of life, the universe, and everything is encrypted with the key $2^{2^{t_a}} \bmod n_a$ where $t_a = 3\,141\,159\,265\,359$ and $n_a = \dotsb$.

  BOB: Awesome, thanks!  By the way, $n_b = p_b q_b$ where $p_b = \dotsb$ and $q_b = \dotsb$.

  ALICE: Ha-ha, sucker!  Have fun chasing meaning while I go open your box of magic words!

  BOB: Blast!  It will take my ASIC three hundred years to compute this.

Another approach you could try—which doesn't involve shortcuts—is to have each party reveal the secret bit by bit (or letter by letter) in lock-step:

  ALICE: The first letter of my secret is C.

  BOB: The first letter of my secret is V.

  ALICE: The second letter of my secret is H.

  BOB: The second letter of my secret is L.

  ALICE: The third letter of my secret is U.

  BOB: The third letter of my secret is F.

  ALICE: The fourth letter of my secret is M.

  BOB: The fourth letter of my secret is E.

  ALICE: The fifth letter of my secret is P, spelling out CHUMP, because you've given me enough to guess the rest of your secret by brute force and I ain't given you diddly squat!

The trouble is twofold:

Bob shouldn't have proceeded to divulge any of the secret without a verifiable proof that what Alice gave is actually part of her secret.
The protocol favors whichever party has more computational power—that party can abort the protocol at any time and leave the other one in the dust.


Example of calculating a primitive root for large prime?

The first question to ask is "are you looking to find a primitive root (that is, a value $g$ such that $g^x \bmod p$ takes on all possible values in $\mathbb{Z}_p^*$), or are you looking to find a generator to the subgroup of order $q$?

Depending on what you are trying to do, either may make sense.  If you are trying to get a subgroup for a DLog-based cryptosystem, the second may be what you want.  On the other hand, sometimes we really want a primitive root.

The procedure you gave is a fine way to find a generator to the subgroup (assuming that you include a check that the value $w$ you get is not 1); however it is guaranteed not to give you a primitive root.

If you really want a primitive root, there are a couple of obvious possibilities:

One is to pick a random value, and check if it happens to be a primitive root (which happens often enough to make this practical).  This is easy if you know the factorization of $p-1$; that is, $x$ is a primitive root if, for all prime factors $s$ of $p-1$, we have $x^{(p-1)/s} \not\equiv 1 \pmod p$
We can also do it be construction; for example, if $(p-1)/2$ is also prime (that is, $r=2$ in your formulation), and $p \equiv 3 \pmod 8$, then $w=2$ will always be a primitive root.

BTW: common usage nowadays is that a "safe prime" is a prime $p$ where $(p-1)/2$ is also prime (also known as a Sophie Germain prime).  It used to have other meanings associated with it as well; however it's been a while since I've heard those other meanings used.  Using the term now with a meaning other than what is common is likely to confuse people.  If you need to use a different meaning, I'd suggest using different terminology.


One example of such a system is ElGamal over a group $G$ generated by $g$. The public key is $y$ and an encryption $(x,w)$ of a message $m$ is of the form $(g^r, y^r m)$ for some integer $r$.

You have three ciphertexts $(x_1, w_1)$, $(x_2, w_2)$ and $(x_3, w_3)$ which are encryptions of $m_1$, $m_2$ and $m_1m_2$, respectively. The random integers used is $r_1$, $r_2$ and $r_3$, respectively. Note that $r_3$ isn't $r_1+r_2$, it is a random number. You want to produce a proof that the encryptions are correct.

The idea is to observe that the ciphertext $(x_1x_2/x_3, w_1 w_2 / w_3)$ is an encryption of $1$. As such, you only need to prove that it is an encryption of $1$. This amounts to proving that the logarithm of $x_1x_2/x_3$ to the base $g$ equals the logarithm of $w_1w_2/w_3$ to the base $y$, which is done using a standard proof of equality of discrete logarithms.

You asked about additively homomorphic cryptosystems, and above I outlined a solution using multiplicative ElGamal. However, the approach works just as well for an additive variant of ElGamal or Paillier.


For simplicity assume that the Merkle tree is a perfect binary tree. Let the number of data blocks is $n$ which are linked to the leaf nodes. Therefore the total number of tree nodes are $|nodes| = n + n/2+ \cdots +1$. If we assume that $n =2^k$ for simplicity than $$|nodes| = 1 + 2 + 2^2 + \cdots + 2^k = \frac{2^k-1}{2-1} = 2^k-1 = n-1.$$ In total, we have $n+ n -1 $ nodes, that is together with the data blocks. As a result the number of nodes are $\mathcal{O}(n)$.

In another approach, you can consider the height of the tree as the search complexity, $h = c \log n$ then the maximum number of a binary tree with $h$ is $2^h-1 = 2^{c \log n}-1 = n 2^c-1 \in \mathcal{O}(n)$. Adding the data block will not change the complexity.

Note: In a complete binary tree, if we say that the root is level 1 then the $i$-th level contains $2^{i-1}$ nodes. Each level will contain a double of the previous level.


Are there any multiparty homomorphic encryption schemes?

The one I'm most familiar with is the SPDZ protocol. The authors have implementing AES via SPDZ with up to 10 parties.


Is storing original file size in an encrypted file header a bad idea?

The 16-byte IV and ciphertext (which together are part of the output of $e_m$) are assumed to be intercepted by an adversary. That reveals the number $b$ of 16-byte blocks in the ciphertext. With CBC and PKCS#7 padding, $b=\big\lceil{{n+1}\over16}\big\rceil$ where $n$ is the byte size of the plaintext (the file size). Putting $n$ itself in a header thus reveals a little extra information: $n\bmod16$, which is worth 4 bits. In some cases, e.g. if what's encrypted is yes ($n=3$) or no ($n=2$), this is enough to ruin security. Thus no, it is not always safe to include the original file size in clear. But in practice, it is often assumed that the length of the data can be public; then it can be sent in clear.

There's a fix to solve the networking problem as originally exposed while revealing no more information about the length of the plaintext than implied by the use of CBC and PKCS#7 padding: in the header, put the number of blocks $b$ in the ciphertext (not counting IV), or equivalently $\big\lceil{{n+1}\over16}\big\rceil$, where $n$ is the size in bytes of the file to encipher.

But caveat emptor: the above fix is mostly of theoretical interest. While it maintains security in the yes or no case, it does not work for my_answer_is_yes ($n=16$) versus my_answer_is_no ($n=15$); or if the plaintext is a JPEG image known to be either out of focus (thus quite compressible, thus small), or well-focused (thus less compressible, thus bigger). Most encryption modes leak a lot information about the length of the plaintext, and this can be exploitable. This effect can be the basis of attacks on VOIP encryption. In most cases where the size of the data reveals information to an adversary, standard operating modes such as CBC are just inadequate.

Update following edit of the question: the networking problem as now explained could be solved by having $b$ computed from $n$ and sent in clear at the beginning of each of the 3 streams involved; the PKCS#7 padding performed by the process reading the file and sending it to $e_m$ (not by $e_m$); and the PKCS#7 un-padding performed by the process retrieving the output of $d_m$ (not by $d_m$). But then the block size (16 bytes) needs to be known by all 4 processes involved, when we would want to isolate that detail, and padding, to the two processes $e_m$ and $d_m$.

It is also possible to have the file size as the first block of the plaintext, CBC-encrypted as the rest. This allows to have everything regarding encryption, its block size, etc.. isolated to $e_m$ and $d_m$. If the length is encoded in a single dedicated block (e.g. the first of the plaintext, thus the one XOR-ed with the random IV), it does not leak more information about the size of the plaintext than implied by CBC-encryption with PKCS#7 padding, just as in the original fix.

Note: I now realize the title mentions an encrypted header, and the question mentions an unencrypted file size in the header. I've been considering the later in all except the previous paragraph.

Note: There is nothing to protect integrity of the data; that is often a very real problem.


If ChaCha20 is being used just as a CSPRNG, is nonce needed?

No it doesn't matter, as you won't be switching the nonce on a per message basis, just outputting a stream of random data.
However, remember, your key will only produce an output stream valid until the internal counter overflows.
Consider XChaCha20.
IETF ChaCha20 uses a 96-bit nonce and 32-bit counter, XChaCha20 uses a 192-bit nonce and 64-bit counter. The 64-bit counter lets it encrypt 1 Zettabyte of data, i.e. output a large random dataset.


Yes, there are true asymmetric (public-key) ciphers beside RSA. Elgamal encryption is an example, and matches the question's definition when we allows that definition's encryption transformation $E_e$ to be randomized (as we must: otherwise, anyone could use the public $E_e$ to verify a guess of the message, which would be a disaster in many practical applications, e.g. enciphering the name of some guy on the class roll).

Using the notation in Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984),

Parameters are a large prime $p$ with $p-1$ having at least one large prime factor, and a generator $\alpha$ (e.g. with $q=(p-1)/2$ prime, and $\alpha\in[1,p)$ with $\alpha^q\bmod p\ne 1$ ). Parameters are public, or part of individual public keys.
The definition's encryption/decryption pair $(e,d)$ is the combination of parameters and long-term public-private key pair $(y_B,x_B)$ used by recipient Bob. More precisely, $e$ is $(p,\alpha,y_B)$ and $d$ is $(p,\alpha,x_B)$, with $x_B$ a random secret and $y_B=\alpha^{x_B}\bmod p$.
The definition's encryption transformation $E_e$ accepts as input a message $m$ in $[0,p)$. As part of each invocation of $E_e$, the sender (Alice) draws ephemeral random $k$, computes $K={y_B}^k\bmod p$, $c_1=\alpha^k\bmod p$, $c_2=Km\bmod p$. The ciphertext is $(c_1,c_2)$.
The definition's decryption $D_d$ accepts as input a ciphertext $(c_1,c_2)$ in $[0,p)^2$. The receiver (Bob) computes $K={c_1}^{x_B}\bmod p$, and $m=K^{-1}c_2\bmod p$.

Note: In the version described here and in the original paper, ElGamal encryption is not CPA secure. For a start, $m=0\iff c_2=0$. And even if we exclude message $m=0$, the Legendre symbol $\displaystyle\biggl(\frac m p\biggr)$ can be found from $(p,\alpha,y_B,c_1,c_2)$, and that leaks one bit of information about $m$.

Regarding EDIT2 (about as it stands less a few typos):

  we can have $D_d(E_e(m))=m$ for all $m\in M$, but we can't have $D_d = E_e^{−1}$.

To my eyes, the two statements are equivalent by any sensible definition of $E_e^{−1}$, which must be a transformation taking the output of $E_e$ and returning what was the input. And the Elgamal cipher matches that. The second quoted definition looks correct to me.

I would agree with "we can't have $E_e= D_d^{−1}$", because multiple inputs of $D_d$ have the same output, making $D_d$ impossible to invert for the classical definition of that. And yes, this is a reason why Elgamal cipher can't be used for digital signatures using the techniques allowing RSA signature.

RSA is not quite the only public-key cipher internally using a trapdoor permutation, usable for both encryption and signature scheme (which turns out to be the meat of the question's introductory phrase). There is at least the Rabin cryptosystem, which can be thought as RSA with even public exponent. I fail to name another which got sizable traction.

Note: RSA as in the original paper and PKCS#1 does not match the "unique key $d$" requirement. For this to hold, we need to reduce $d$ modulo $\lambda(N)$ (where $\lambda$ is the Carmichael function), as in FIPS 186-4.


Can I still use insecure curves/ciphers for time relevant encryption?

Let's assume I need to encrypt data only for one minute, after that time the data is useless. Couldn't I still use ECC2K-130 as it would require 525600 times more PlayStations to crack it in a single minute instead of a year?

!!! NO !!!
Decryption by an unauthorized party could occur within a fraction of a second following the release of the ciphertext.
In ECC encryption (and more generally public-key encryption), the appropriate start time for the attack interval is

NOT the release of the ciphertext to adversaries
NOT the encryption time (even if there's a side channel¹)
is the release of the public key used for encryption to adversaries²
could be the generation of the public/private key, if there's a side channel¹.

At issue is that attackers can start working long before the encryption occurs or the data to encrypt even exists. They can start as soon as they get the public key (or, in 4, side channel data). That's when time of attack starts ticking. It is reset only by a key change.
In the question, the entity making the encryption uses the public key, thus is not the one who generated the keypair. The question suggests that the time considered is from encryption to when knowing the data becomes dull, which would be 2 in the above.

¹ In side-channel attacks, adversaries get information beyond the ciphertext in often unexpected ways, like timing of encryption, electromagnetic or acoustic emissions, leakage from a CPU process to another.
² In symmetric cryptography, that would be when the first ciphertext is obtained by adversaries.


Why would we want parallelizable authentication?

If you have a vector unit on your CPU that can be used only by a single thread at a time but remains powered whether you're using it or not, it takes less time, and is therefore cheaper, to compute a parallelizable function using the entire vector unit than to compute nonparallelizable function using only a part of the vector unit.

If you have only three cycles per byte to spare in your computing budget, there is no way you will fit HMAC-SHA256 in that.  But you can easily fit Poly1305.  The more parallelizable the function, the more flexibility you have to adapt it to vector units of different sizes to maximize throughput subject to your power constraints.

The alleged quantum threat to these constructions posits the asinine model where the legitimate user reveals quantum superpositions of secret function evaluations to the adversary.  If you do your cryptography on a classical computer on ordinary bits, then the model is irrelevant.  If, under the currently unrealistic premise that quantum computers were actually capable of it, you did your cryptography on a quantum computer and enabled this attack model, you would be an idiot.  This model gives amusing theoretical results, but it is totally irrelevant to the real world.


How can I prove/disprove that a construction yields a secure PRG?

If there exists a secure PRG, then there is a secure PRG

whose last bit of output is always equal the last bit of its input.

If the last bit of G's output is always equal to the last bit of G's input, then the

function G' constructed as described in the question will not be a secure PRG.


Why is the whole initial state used in the final addition of Salsa20 and ChaCha?

Note that, in Salsa20, the loads and additions of the key words ($x_1$, $x_2$, $x_3$,
  $x_4$, $x_{11}$, $x_{12}$, $x_{13}$, $x_{14}$) are critical for security, since the double-round function is
  trivially invertible. One might think that the remaining loads and additions could
  be skipped without sacrificing security, achieving almost half of the HSalsa20
  savings. However, this change would interfere with the vector loads and vector
  additions used in many high-speed Salsa20 implementations.

from D. J. Bernstein - Extending the Salsa20 nonce

Since you need to supply the nonce/counter to pass them to the next block, you need to keep track of them anyways, eliminating the space savings.


Are LRC (Longitudinal Redundancy Check) or CRC (Cyclic Redundancy Check) of any use in modern day computing?

I still see some uses of CRC in the case of encrypted protocols.
The secure parts are embedding hashes and/or MACs in a data field, then it checks the integrity of the whole message a second time with an extremely lighter algorithm (CRC).

This way in embedded cryptography with high speed, you avoid yourself cryptographical computation if the transmission failed and the CRC/LRC is wrong.

Anyway, if you don't look at performances and don't work with microcontrollers, you're right it should desappear behind modern hash and MACs.


DSA: If signature is accepted then signature is correct

This isn't completely standard terminology, so you should check the precise definitions in your lecture notes. But I can't think of anything else that the exercise should be.

You have a definition of the DSA signature process: given some parameters $(p,q,g)$, a private key $x$ and a message $m$, generate a nonce $k$ and calculate $(r,s)$ given by a certain formula. You also have a definition of the DSA verification process: given some parameters $(p,q,g)$, a public key $y$, a message $m$ and a candidate signature $(r,s)$, make a certain calculation and output “accepted” or “rejected”. This is a signature scheme if every output of the signature process is accepted by the verification process, that is, if you take the $(r,s)$ given by signing and perform the verification process on it, the output is “accepted”.

This exercise asks you to prove a dual property which is a practical necessity, while not sufficient for security: given parameters $(p,q,g)$, a key pair $(x,y)$ and a message $m$, if the verification process for $y$, $m$ and the signature candidate $(r,s)$ outputs “accepted”, then there exists a nonce $k$ such that the signature process for $x$ and $m$ yields the output $(r,s)$.

   The calculation itself is easy: take $k = s^{-1} (m + x\,r)$, inverting the formula used to compute $s$ from $k$ and $r$ during the signature process. The verification process basically checks that $g^k = r$, so if the signature is accepted, that means that it's the output of the signature process for this $k$.

This property is practically necessary for security because if the adversary can efficiently find $(r,s)$ which is not the output of the signing process, that means that they can craft an invalid signature. I'm not sure if the mere existence of a valid signature that no one can find efficiently would disqualify the signature scheme.