Authenticated AES 256 CBC HMAC SHA512 - What's the right way to implement in C#?

I'm going to use the answer field as I think the question is about doing a full review, which is typically off topic. However, since the comments are too short, I'll give a few hints and then allow the question to be closed.

You're on the right track if you have to use a password, however:

32 bytes of salt is excessive, you only need 16 bytes / 128 bits at max.

The idea to use dual PKBDF2 is not a good one as an attacker only needs one of the keys to verify a correct guess of the password. That means that per password you'd doing twice the work as an attacker needs to do. It is better to use the output of the first PBKDF2 and either split that up (e.g. using SHA-512 for two 256 bit keys) or derive keys using a KBKDF such as HKDF from it.

CBC mode is still vulnerable to attack if you don't verify the authentication tag first. You should make sure that the correct order is preserved, or use an AEAD scheme.

The IV might as well be set as all zero or be calculated from the password & salt, as the salt already provides the required randomization. You could even use the salt itself as IV.

Generally we write the IV / salt and other static information at the beginning - not the end - of the file. First of all, it's easier to find / parse that way and furthermore, you need the keys before you can start verification and / or decryption.

Base 64 encoding the entire output is fine if text is what is required. Otherwise you should just store the ciphertext and header as binary file.


What is the reasoning behind the PRESENT key schedule?

Question 1

  In simple terms, how does the key schedule protect it from key related attacks?

According to the paper "Lightweight Block Ciphers Revisited: Cryptanalysis of Reduced Round PRESENT and HIGHT", the non-linearity of the key schedule contributes to resistance to related key attacks:

  Related-key differential attacks, on the other hand,
  are also believed to be inapplicable because of the sufficient non-linearity due to [sic] key scheduling algorithm.

The above quote then points to a reference to New Types of Cryptanalytic Attacks Using Related Keys, which mentions the following:

  These attacks are based on the observation that in many blockciphers we can view the key scheduling algorithm as a set of algorithms, each of which extracts one particular subkey from the subkeys of the previous few rounds. If all the algorithms of extracting the subkeys of the various rounds are the same, then given a key we can shift all the subkeys one round backwards and get a new set of valid subkeys which can be derived from some other key. We call these keys related keys.

Then, the description of the key schedule they give is:

  The subkeys for each round are derived from the user-provided secret key by
  the key scheduling algorithm. We provide only the details of the key scheduling
  algorithm of Present-128 as it is the main target of this paper: 128-bit secret
  key is stored in a key register $K$ and represented as $k_{127}k_{126}\dots k_0$. The subkeys $K_i (0 ≤ i ≤ 31)$ consist of 64 leftmost bits of the actual content of register $K$. After round key $K_i$ is extracted, the key register $K$ is rotated by 61 bit positions to the left, then S-box is applied to the left-most eight bits of the key register and finally the round counter value, which is a different constant for each round, is XORed with bits $k_{66}k_{65}k_{64}k_{63}k_{62}$...

So the S-Box in the key schedule provides some non-linearity. And the addition of the counter may also serve to make the key schedule function for each round different and provide some resistance to the attack in [2] - If this is in fact the case, it is not explicitly stated anywhere that I can find.

Question 2

  What if (for instance) we changed the step $S[b_{78}b_{77}b_{76}b_{75}]$ to something else, such as $S[b_{74}b_{73}b_{72}b_{71}]$ or anything else. Would that make it weaker? Stronger? No different?

I presume this is about the main round function and not about the key schedule, since these indices don't appear to be a part of the key schedule.

The S-Box is applied on each group of 4 contiguous bits in parallel, so the answer is that both $S[b_{78}b_{77}b_{76}b_{75}]$ and $S[b_{74}b_{73}b_{72}b_{71}]$ are both performed. Swapping one for the other would have no effect.

As for why the 4-bit wide S-Box would be applied on contiguous sections of 4 bits in parallel, the answer is because it is really the only way to do it. The bit permutation that follows the S-Box scrambles the indices so that successive applications of the S-Box are applied to different groupings of bits. But these are separate steps, and doing something like $S[b_{73}b_{71}b_{72}b_{74}]$ simply re-arranges the permutation step to come before the application of the S-Box, rather than after it, and the S-Box would still be applied on 4 contiguous bits in parallel.

Question 3

  What if the round counters were not in the order 1,2,…,311,2,…,31? What if the round counters were any order of 1−311−31? Again, would this make it weaker, stronger or no different?

The reason they are in this order is for performance. If you examine the assembly instructions, using the round counter this way is the cheapest way to implement the operation. Using a permuted order of values 1-31 would require additional MOV/ADD operations. You want to minimize MOVs when designing a fast permutation.

The job of the counter is to ensure each round is different. So long as it is unique for each round, it does not matter so much what the actual literal value is, and so you may as well simply use the most efficient sequence available.


This is done in Theorem 2.5 of Boneh and Shoup's under-construction textbook.

In short, suppose $|K| < |M|$. Pick some $k \in K$, $m \in M$, and let $c = E(k, m)$. Now, for all possible keys $k' \in K$, there is a set of plaintexts $\{ D(k', c) : k' \in K \} $. But because $|K| < |M|$, there will be some $m'$ not in this set, such that $\mathbf{Pr}[E(k, m) = c] > 0$ and $\mathbf{Pr}[E(k, m') = c] = 0$. But by definition of perfect security, we should have $\mathbf{Pr}[E(k, m) = c] = \mathbf{Pr}[E(k, m') = c]$ for any $m, m'$.

In other words, there are not enough keys to make every possible ciphertext from a message, or every possible message from a ciphertext. This breaks perfect security.


Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony and the signatures protecting the PS3 firmware (they used a fixed k...), but a number of Bitcoin-related "electronic wallet" applications also botched things similarly. This even prompted the specification of deterministic variants of DSA and ECDSA, to avoid the need for randomness. If good randomness cannot always be obtained for (EC)DSA signatures, then one has to assume that good randomness cannot always be obtained either for secure blinding.

Another point is that timing attacks have evolved over time. The "classical" timing attack on RSA, described by Kocher in 1996, only uses a measure of the complete computation time. However, modern, fashionable variants use accesses to cache memory or jump prediction within the CPU to obtain a lot of information from even a single run of the attacked implementation -- especially in contexts where the attacker can run his own code on the same core (hyperthreading) or in a close core (even across virtual machines). It is unclear how well blinding holds against that kind of attack. Common wisdom is that such attacks are very hard to pull off in most cases (and they have not been observed "in the wild" yet), but it is also very hard to ascertain whether they apply, or do not apply, to a particular situation. A general-purpose library has then little choice but to play safe, and go for constant-time code.

Also, in the case of binary curves (curves over a field $GF(2^m)$), Montgomery's ladder (as described by López and Dahab in 1999) can be adapted to binary curve and yields a verify efficient point multiplication algorithm that is both constant-time (provided you use constant-time conditional swaps, which is no hardship) and fast (6 field multiplications per bit). It is not easy to do better than that in all generality, especially on modern x86 hardware with the CLMUL instructions (when field multiplications are slow, point-halving is better, but not when field multiplications are very fast).

Last but not least, many implementers are motivated by the intellectual challenge of coding (especially in open-source projects), and constant-time code is a lot more fun than blinding. Blinding is crude and inelegant. Who wants to spend his weekends implementing blinding ?


Is DSA vulnerable if verifier doesn't check r' > 0?

Let's write down naming conventions explicitly:

We work modulo prime $p$. There is a smaller prime $q$ that divides $p-1$; we write $p = 1 + qn$ for some integer $n$. Traditionally, the sizes of $p$ and $q$ would have been 1024 and 160 bits, respectively; nowadays, we would rather use 2048 and 256 bits.
$g$ is an integer modulo $p$ of order $q$; i.e. $1 < g < p$, and $g^q = 1 \pmod p$.
Private key is some non-zero integer $x$ modulo $q$.
Public key is: $y = g^x \pmod p$
Normal signature generation is:

Generate a random non-zero $k$ modulo $q$.
Compute $r = g^k \pmod p \pmod q$ (we compute the exponentiation modulo $p$, and the result, which is in the $0$ to $p-1$ range, is further reduced modulo $q$). At that point the signer is supposed to check that $r \neq 0$; if that very improbable case shows up, then he should start again with a new random $k$.
Compute $s = (h+xr)/k \pmod q$ where $h$ is the hash of the message, suitably truncated and reduced modulo $q$.

Normal signature verification is:

Verify that $r$ and $s$ are in the $0$ to $q-1$ range.
Verify that $r \neq 0$.
Compute: $w = 1/s \pmod q$
Compute: $r' = g^{wh} y^{wr} \pmod p \pmod q$
Signature is considered valid if and only if $r = r'$.

The question is then: what if the verifier does not check that $r\neq 0$ ? In other terms, if a signature such that $r = 0$ is deemed acceptable, then does this allow attackers to forge signatures?

The attacker succeeds if he can show values $(r, s)$ that fulfill the equation:

$$  g^{wh} y^{wr} \pmod p \pmod q = r $$

where $h$ is a given (hash function output). If $r = 0$, then this simplifies to:

$$ g^{wh} = 0 \pmod p \pmod q $$

If there is an integer $u$ modulo $q$ such that $g^u = 0 \pmod p \pmod q$, and the attacker can find it, then a forgery is easily computed by setting $s = u/h \pmod q$. This can allow forgery for any message, and, interestingly, for any public key $y$ that uses these DSA parameters, since $y$ does not appear at all in the equation.

Now the attacker's problem is finding that value $u$, if it exists. Now comes the hand-wavy part: this problems seems difficult, for the following reason: there are very few solutions.

Namely, $g$ generates a subgroup of size $q$, and there are about $p/q$ values modulo $p$ which are also a multiple of $q$. So the possible solutions $u$ are in the intersection of a set of size $q$ (the subgroup) and a set of size $p/q$ (the multiples of $q$), both sets being subsets of a set of size $p$ (the integers modulo $q$). If both subsets were generated randomly, then the probability of having no common element would be about $((q-1)/q)^q$, which converges to $e^{-1} \approx 0.3679$ when $q$ is large. In other words, in about 37% of the cases, there will be no solution at all, i.e. there would be no signature with $r = 0$ that the verifier would accept. And when there is a solution, there will usually be only one or two.

Thus, the attacker's job is about finding a discrete logarithm $u$, in base $g$, for a single target value. This is exactly the discrete logarithm problem and we assume it to be hard modulo $p$ (otherwise, why would you use DSA at all?). Note that this would hold even if the attacker knows exactly what multiple of $q$ he should target; not knowing that value makes the task only harder for him.

Now, of course, the two subsets are not generated randomly. I made some measures with small values. For instance, with $p = 1993$ and $q = 89$, then none of the elements of the subgroup of order $q$ is a multiple of $q$; however, with $p = 1553$ and $q = 97$, using $g = 310$, then $g^6 \pmod p = 776$, which is a multiple of $97$, and $g^{18} \pmod p = 194$, which is also a multiple of $97$.

Generating all possible DSA parameters such that $200 \leq q \leq 500$ and $100000 \leq p \leq 200000$, I find 1218 sets of DSA parameters; for 442 of them (36.3%), there is no solution; for 438 (36.0%), there is exactly one solution; for 231 (19.0%) there are exactly two solutions; and so on. This is compatible with the analysis above: solutions are rare, so finding a solution should be as hard as solving discrete logarithm generically.

(Unless there's some magical math that allows easily finding a solution in that specific case. Sometimes the World does that, just to spite me.)


It may be possible to use the knapsack problem to build a secure cryptosystem, though experience suggests it is tricky and delicate.  There are many known algorithms for attacking the knapsack problem, which may or may not work, depending upon the specific parameters you choose.  Therefore, the security of the scheme will depend on the specific parameter values you use (e.g., the exact strategy you use for choosing all values, and the sizes of each value).

If you choose the weights $w_1,\dots,w_n$ independently and uniformly at random from a large enough space, and if $n$ is large enough, and if $S$ is chosen at random, then I suspect this should be secure (it'll probably be computationally infeasible to find $S$).  But I couldn't tell you exactly what parameter choices you'd need to make.  You'd need to read up on all known attacks on knapsack problems, including LLL-based algorithms and generalized birthday-based methods.  At minimum, I expect you need the weights to be (say) at least 256 bits long and $n \ge 160$, but I don't know if that is sufficient for security.

Are you using this only for one-wayness?  Can you use a standard one-way function (e.g., SHA256) instead, in lieu of the knapsack problem?  Or are you taking advantage of the special structure of the knapsack problem?


Is TLS 1.2 compression methods in client_hello a mandatory field?

Well, it is specified in the ClientHello struct here, and the description reads:

  The ClientHello includes a list of compression algorithms supported
     by the client, ordered according to the client's preference.

And since the client hello is the first message that needs to be send to the server, yes, new sessions should contain this struct, even if the internal value just points to the zero-compression.


Data switching on one time pad and Data leakage

This is just a blown up version of the OTP.

$v_1$ is basically just the normal OTP: To decrypt, it is enough to know $r_1$

And then you give the adversary just another random value: If $r_2$ is drawn uniformly and $r_1$ is fixed, $v_2$ has the very same distribution as $r_2$ itself. Essentially, you are using another OTP to encrypt the key of the first OTP (the minus sign does not change anything)

So in the end, if you transmit both $v_1$ and $v_2$, you just doubled the size of the message. And you have doubled the key size, and key management is the major drawback of OTP. Decryption is possible with knowledge of either $r_1$ (directly) or $r_2$ (indirectly, getting $r_1$ from $v_2$).

This construction can easily be turned into an attacker on OTP and vice versa, so the security is basically the same. But this is only true if you actually use OTP with true random keys. In a stream cipher construction (which people wrongfully call OTP sometimes), the situation might be entirely different, and from intuition I would say it would weaken the security.


Why is this hash function (based on a block cipher) insecure?

If you want a hint as to why your proposed hash function isn't secure (even against preimage attacks), I would note that block ciphers are invertible, that is, given $C_{i-1}$ and $C_i$, we can efficiently compute the value $P_i$ must be so that $C_i = E_{C_{i-1}}(P_i)$ holds.  Question for you to complete the answer: how can an attacker exploit this to create preimages?


How to encrypt files using AES256-GCM cipher under Linux?

LibreSSL supports AEAD ciphers, including aes-256-gcm:

$ openssl enc -aes-256-gcm -nosalt -p -in file.in -out file.out
enter aes-256-gcm encryption password:
Verifying - enter aes-256-gcm encryption password:
key=A744E1091C25BABD36B50E40FB8D311A672722729CEA6E217AD9FA8AF23CAF57
iv =BDEEA37B93BB989C6C40665B

If you don't mind writing your own software, there are plenty of crypto libraries supporting AES-GCM, such as OpenSSL itself (even if not available from the command line tool). Libsodium also provides AES256-GCM and may be easier to use.

That being said, using a common and trusted tool such as GPG would be way safer than implementing your own software, even if the resulting files are not encrypted using AES-GCM.


There has been variants of definition in the literature, but I would say the zkproof.org's effort to standardize these terminology is a good reference. See page 82 here

I recall there's some discussions on Twitter between Benedikt Bunz, Vanishree Rao and others here


DES : Is Double Encryption using same key twice equivalent to single DES using different key but of same size

Can we get the same result as if we would encrypt the plain text using single DES but with different key, say K2.

It has not been formally proven, but it is extremely plausible to assume that there isn't an equivalent 'double key', that is, for a K1, there isn't a K2 where DES(K1, DES(K1, M)) = DES(K2, M) for all values M (or even a number of values of M.
What has been proven (and is somewhat similar) is that there exist K1, K2 values for which there is no K3 for which DES( K1, DES( K2, M )) = DES( K3, M ) always holds; this is known as the 'DES is not a group' theorem (although it is typically expressed differently).  However, this result does not immediately imply what you are asking about.


Are there encryption schemes that can be performed using an adding machine?

That means you have a turing machine, using a small memory is ok, but wasting memory is not desirable (as usual).

You can do all known encryption algorithms with that.


Is it secure to use hexadecimal data for IV instead of raw binary?

An initialization vector is, in fact, always binary.  It's just random bits.  So, if you choose to encode those bits as a hexadecimal string for ease of storage or transportation, that is fine.  However, since it is the binary that is the IV, you will need to decode it back from hexadecimal to a binary value before using it in the decryption process.

As a note, you would certainly not want to use the binary values of the individual characters in a hexadecimal string as an IV, as that would limit you to a tiny set of possible IVs, much smaller than the space you need to generate IVs securely.


Shamir Secret Sharing Scheme - some doubts not answered earlier

You need a finite algebraic object, resulting in exact arithmetic and exact recovery of the secret. So infinite fields such as $\mathbb{C,~R}$ are not suitable.

Since the scheme is based on polynomial interpolation, you need two operations, i.e., a field. It can be a prime field $\mathbb{F}_p$ or an extension field $\mathbb{F}_{p^m}.$

Since each user is assigned their secret by specifying $y_i$ at point $x_i,$ you need at least $n+1$ points, the value at zero of the polynomial normally being used for specifying the secret.


Bundling hash into the initialization vector?

This is a terminally bad idea: much of the confidentiality of the message $M$ is lost, because $A$ and 64 bits of $B=H(A\|M)$ are available in clear. So if $M$ is enumerable (a password, a name, a Social Security Number) among say $2^{48}$, it can be found by a cheap offline attack with little odds of false positive ($2^{-16}$), totally irrespective of the AES cryptography.


Cryptographic random number on interval $[0,n]$ from bytes

Is this safe and does it work?

Well, it works in the sense that it doesn't pagefault or anything; however its output will be strongly biased.  When you think about it, it takes a value $d$ between 0 and 255, and based on that input, outputs a value between 0 and 203; that means that, for at least least 52 pairs of $d$ values will result in the same output, and so those output values will happen with significantly more probability than expected.

The post you linked gave several viable options; I will second those and add one further one (which doesn't give a precisely uniform distribution, but one that is close enough):

The general idea is to generate a (say) 64 bit random number $r$, and compute $r % 204$, and output that.  Again, this won't be exactly uniform; however an observer would need circa $2^{128}$ outputs before he can distinguish it from random, and so it's pretty good.

And, if you're afraid of the bignum math, actually it's fairly simple (given a 16 bit modulo an 8 bit operation); here's some simple pseudocode:

uint_8 r = 0;
for (i=0; i<8; i))
    uint_16 temp = (256 * r + crypto_rng());
        /* We assume that crypto_rng generates 8 bits */
    r = temp % 204;
/* result in r */

It does use up more random bits than other methods; however it is constant time (assuming the modulo operation is constant time), and that can be important.


Why is (gy, gx) signed in STS (station-to-station)?

The 1992 paper http://people.scs.carleton.ca/~paulv/papers/sts-final.pdf by Diffie et al answers the question. It has an example of an insecure variant of the protocol that uses signatures of random challenges. Furthermore, the section "Signing only one’s own exponential" considers a variant where Alice signs only gx. According to the paper, there is an attack on this variant when RSA signatures are used. And it seems open to replay attacks (see DuBuisson's answer).

The section "Signing only the other party’s exponential" considers the variant where Alice signs only gy. For this case the authors of the paper say: "we know of no general attack which applies to this case, but there are some concerns". One concern is that "it is imprudent to sign arbitrary text supplied by a potential adversary".


Is the Vernam (One Time Pad) cipher useful?

As you know, if a thing is useful or not depends upon context.  If you are hungry, will a 4096-bit RSA key with a CAMELLIA256 subkey be useful?  Not really, except perhaps as food for thought.

One-time pads are being used at this very moment by serious and perhaps dangerous people all over the world.  OTPs work.  Ciphertext encrypted with a one-time pad can be heard on HF radio all the time.  Is it useful?  Certainly.  The question is: "for whom?"

Why are one-time-pads useful?  You don't have carry around a lot of equipment.  Paper does not leave an electronic trail.  Paper burns.  Little pads are easy to hide. It's hard to get a kleptotrojan into a pencil.  Paper is cheap.  Vernam cipher is the perfect cipher if the key is truly random, the key was protected, and the key is as long as the message.  When your equipment stops working you can pull out the little book and figure out a way to deliver your message--and its content will remain private.  You can actually see the key destroyed. When you destroy it, it's really gone.  Everything about using a one-time-pad is easy to understand. A one-time pad does not require electricity. If you lose your pad, that might be bad, but you don't have to revoke it in front of everyone.  All of that sounds very useful, right?

So, to answer your question directly, "if we can find a suitable, secure way to generate and share unique keys, does the Vernam cipher become useful?"--yes, it already is very useful to certain people all over the globe, but they are not talking about it.

"Is there anything else that needs consideration in this respect?"

Yes.

It isn't that the key "should not" be used again, as if it were an option.  It must only be used once.
The key must be at least as long as the plaintext.
The key must be truly random in order to be perfect.
The key must have been protected against damage or compromise.
The key must have been shared via a secure means.


Should I calculate two CMACs over two different strings that share common bytes?

By using 6-byte MACs you can only authenticate about $2^{24}$ messages on average before seeing a collision, which would allow an attacker to swap one message for another. There's a decent chance you'll see one much earlier, so in practice you can only safely use a key for some thousands of packets.

So the best option would be to find an implementation of CMAC (or another secure MAC, like HMAC) that allows you to create a single 12-byte authenticator for the whole 20-byte message.

If you do need to go with the 16-byte CMAC implementation for some reasons, I think including the first MAC as part of the second message is better than overlap, which may be shared between two messages. I.e. calculate the second as $MAC(B[11]...B[20]||MAC(B[1]...B[10]))$. You would still be limited in the number of messages you can send before collision.


What is the time requirement for pairing computation and modular exponentiation?

I had to do this comparison one year ago in an article, to justify whether it was desirable to avoid pairings in some protocols. Roughly, if you take the (arguably) most efficient up-to-date curves with and without pairing, counting as 1 the cost of a modular exponentiation in the curve without pairing, denoting $\mathbb{G}_1$ and $\mathbb{G}_2$ the (asymmetric) curves with the pairing,

the cost of an exponentiation in $\mathbb{G}_1$ is 3
the cost of an exponentiation in $\mathbb{G}_2$ is 6
the cost of a pairing is 8

For the comparison, we used Bernstein's Curve25519 for the curve without pairing, and  Barreto-Naehrig curves for the curve with pairing (using the implementation of "High-speed software implementation of the optimal Ate pairing over Barreto-Naehrig curves"). Not that the cost of a pairing is not the only thing that matters, as in the best curves without pairing, there are more efficients algorithms for exponentiation than in the best curves with pairings.

Source: https://eprint.iacr.org/2015/246.pdf


Is it possible to brute force a single smaller variable in $\operatorname{HMAC-SHA512}(k, a\ ||\ b\ ||\ c\ ||\ d)$?

Is is feasible to alter b and produce a valid MAC under the unknown key?

We most certainly hope not.  The fundamental security property of a MAC is that, even if that attacker can get a huge number of valid (Message, MAC) pairs (where he gets to choose the messages), he still is unable to generate a MAC for a message he has not seen.  This fundamental property doesn't change just because the inputs are 'small'.

We believe that HMAC-SHA512 is a secure MAC (assuming an unguessable key); hence we believe that it is secure in your case.


No, assuming your code is running in an environment completely controlled by an adversary (no TPM etc.). Note that if the instructions were encrypted in some way we assume an adversary could simply intercept them after they are decrypted.

Your best shot is to obfuscate the code making it cumbersome for someone else to grasp the logic behind it. This can never give you security in a cryptographic sense.


The security property IND-CCA does not fit with commitment schemes. The IND-CCA game is specified in a certain way, and is usually used w.r.t. encryption schemes. However, a commitment scheme can be more general, because you don't need to be able to reverse the process like decryption.

A very simple model for a commitment scheme is that you have a one-way function with two inputs. One of them is the element you are commiting to, and the other is random. In the unveil phase you show them both, and it can be verified by applying the one-way function on those inputs. Those random coins are required for some security properties.

For the security properties of commitment schemes, there are two properties to look at:

Hiding property: If it is computationally hiding, then it is a difficult problem to find a matching input. If it is unconditionally hiding, then there exists a way to unveil a commitment to every valid input. Basically this is similar to the principle of perfect secrecy.
Binding property: If it is computationally binding, then it is hard to unveil a commitment to any other element, which was not the original input. If it is perfectly binding, then it is not possible to unveil an element to anything else than the original input.

It is easy to see, that unconditionally hiding and perfectly binding are contradictions to each other, and in fact it is impossible to have them at the same time. But there are commitment schemes which are unconditionally hiding and computationally binding, and there are schemes which are computationally hiding and perfectly binding:

$G$ is a prime order group where the DLOG problem is hard, with generator $g$. Then commit to an integer $x$ (in matching bounds) as $Com(x) = g^x$. Unveil is just showing $x$. This is computationally hiding and unconditionally binding.
Pedersen commitment: $G$ again a prime order group where the dlog problem is hard with two generators $g,h$, commit to $x$ as $Com(x,r) = g^xh^r$ with a random integer $r$. In order to unveil, both $x$ and $r$ are shown. This scheme is unconditionally hiding, because if you knew $log_g(h)$, then it would be possible to unveil any value $x$ by calculating the matching value $r$. However, under the assumption that the commiter does not know that discrete logarithm, the scheme is computationally binding.

Besides that, it was one of the first results shown in the UC framework, that it is impossible to realize UC-secure commitments. But it was also shown, that the additional assumption of a common referecne string allows the construction of such a UC-secure commitment scheme.


Rijndael: explanation of Rcon on Wikipedia?

Rcon(9) is 0x1b because 0x80 multiplied by 0x02 is 0x100, which is reduced to 0x00 xor 0x1b in the finite field.

Rcon(10) is twice Rcon(9), and so forth.

Rcon(0) is 0x8d because 0x8d multiplied by 0x02 is 0x01 in the finite field.

If what I mean by finite field is not understood, it is because the numbers you are dealing with are actually polynomials, see: Rijndael's Finite Field


Is the number of creatable torrents limited?

$16^{40}$ is a huge number. For instance, if you consider each torrent to consist in a single byte each (so they are quite uninteresting torrents), and you pack them all on 10 TB hard disks (for a torrent to exist, it must exist on at least one hard disk on the planet), and if each such disk weighs about 100g, then the total weight of the disks is about 24 billions of times the mass of the whole Earth.

So I am quite confident in stating that this number will not be reached.

Risks of collisions are actually higher. If you accumulate 160-bit hash values (outputs of SHA-1) then, on average, the first collisions should appear after about $2^{80}$ values (this is known as the birthday paradox). So the situation you describe may occur much earlier than after exhaustion of the $16^{40}$ space. But $2^{80}$ is still huge, and cannot be practically achieved ($2^{80}$ torrents mean more than one hundred thousand billions of torrents per human being on Earth).

If a hash collision occurred, then streaming either of the two colliding files would most probably cease to work; downloaders would obtain a mixture of both files. Other torrents would remain totally unaffected.

An interesting question is whether you could, given an existing torrent $T$, handcraft another $T'$ which hashes to the same value -- it would be used as a weapon to prevent usage of $T$. To do that, you would have to break second preimage resistance of the hash function. SHA-1 has a few known weaknesses, but for now there is no known method for obtaining a second preimage, except luck (try random values until one matches). Luck (aka "brute force") has average cost $2^{160}$, which is completely out of reach of today's (and tomorrow's and next decade's) technology.


Question about the proof of the change of base formula for the discrete logarithm

Prove that:
$$g \text{ and } \Gamma  \text{ both primitive element of } F_q^* \text{ and } \log_g \Gamma =\gamma \implies \gcd(\gamma , q-1)=1$$
A primitive element in finite field means it is a generator, i.e. $\langle g\rangle = GF(q) =  F_q^* $.
Let  $g \text{ and } \Gamma$ be both primitive elements of $ GF(q)$. By using the contrapositive we will reach the opposite.
Assume that  $\gcd(\gamma , q-1) = d \neq 1$ where $\log_g \Gamma =\gamma$.
We can say that $\gamma = d \cdot k$ for some non-negative integer $k$ and $q-1 = d \cdot t$. $(q-1) \cdot t = \lambda \cdot k$. Therefore; $\lambda = \frac{(q-1)\cdot t}{k}$
$\log_g \Gamma =\gamma$ means $\Gamma = g^\gamma$ now,
\begin{align}
\Gamma &= g^\frac{(q-1)\cdot t}{k} && ;\text{replace } \lambda \text { with } \frac{(q-1)\cdot t}{k}\\
\Gamma^{k} &= g^{(q-1)\cdot t}  && ;\text{take } kth \text{ power}\\
\Gamma^{k} &= 1^t \\
\end{align}
Clearly, $k < q-1$ but we found a power $k$ of generator $\Gamma$ such that $\Gamma^{k} = 1$ this mean $\Gamma$ is not a primitive element. This proves the statement.


Some people define "encryption" in such a way as to exclude analog techniques -- there is no such thing as "analog encryption", they would say, because any analog method of obscuring the contents of a transmission is, by their definition, "scrambling", not encryption.

There have been several such scrambling ("analog encryption") techniques, including:

voice scrambling:

some early analog secure voice techniques, as you already mentioned, which added noise (or classic symphony music) from a phonograph at one end, and subtracted the "noise" from an identical, synchronized phonograph at the receiver.
Some analog voice scramblers do frequency inversion
Some analog "rolling code" voice scramblers frequently jump to a new frequency, hopefully faster than any eavesdropper can track, similar to frequency-hopping spread spectrum
Various combinations of the above -- for example, the analog A-3 and the 5B machine built to "decrypt" it which "the speech spectrum was being split into 5 bands, inverted and translated ... the cipher controlling the switching repeated cyclically after 36 sections."
I've heard rumors that some early speech scramblers used an analog vocoder to dissect voice (using a bunch of analog bandpass filters and an analog envelope detector for each one) into a few "control signals", each of which was transmitted on its own (very narrow) analog band (each one independently frequency-hopped, and random gibberish transmitted on unused bands?), and then the received control signals were used to reconstruct an approximation to the original voice.

Some analog "television scrambling" techniques:

Some scrambling systems transmit the visible part of each line exactly the same as normal analog video, but mangle the Horizontal Sync so that standard analog TV receivers can't lock on.
Some scrambling systems invert the black-white luminance of some lines, each line inverted/normal according to a bit from some pseudorandom number generator synchronized with the video signal.
Some scrambling systems invert the red-blue chroma of some lines, each line inverted/normal according to a bit from some pseudorandom number generator synchronized with the video signal.
Several scrambling systems use various combinations of the above.
Videocipher I, Leitch Viewguard, VideoCrypt-S, and Nagravision Syster all scramble video by sending the video scan lines in a scrambled order.
Telefirst ("Tele1st") apparently used some sort of analog scrambling technique (?)
Zenith Z-Tac cable scrambling system apparently used some sort of analog scrambling technique (?)
VideoCrypt I, VideoCrypt II, and Eurocrypt use line cut-and-rotate -- each line of the image is cut into 2 parts and swapped; the exact cutpoint is determined by a pseudo-random sequence generated by a smartcard from a seed value.

All of these systems were developed under severe cost constraints, so they sacrificed some security for lower cost to manufacture legitimate receivers.
So for a long time there was something like an arms race between the "defenders" (pay-per-view broadcasters, military radio manufacturers, etc.) and the "attackers" ( pirate decryption, military codebreakers and cryptanalysts, etc.).


Is the HMAC of a broken hash such as MD2, MD5, SHA1 etc, also broken?

In 2006, Mihir Bellare, in their article

New Proofs for NMAC and HMAC: Security without Collision-Resistance

proved that if the compression function is a PRF then HMAC is a PRF ( this is a short story, see below).
As a result, HMAC like HMAC-MD5 does not suffer the weaknesses of MD5. However, still prefer HMAC-SHA256 or KMAC of the SHA-3 series. Keep yourself away from MD5 and SHA-1.

However, the story is not finished There:
In 2006, Jongsung Kim, Alex Biryukov, Bart Preneel, and Seokhie Hong showed that they can distinguish HMAC if instantiated with reduced versions of MD5 and SHA-1 or instantiated full versions of HAVAL, MD4, and SHA-0 from a random function or HMAC with a random function.
In 2012, Koblitz–Menezes published a paper Another look at HMAC ( from the abstract);

First, we describe a security issue that arises because of
inconsistencies in the standards and the published literature regarding keylength. We prove a separation result between two versions of HMAC, which we denote $\operatorname{HMAC}^{std}$ and $\operatorname{HMAC}^{Bel}$, the former being the real-world version standardized by Bellare et al. in 1997 and the latter being the version described in Bellare’s proof of security
in his Crypto 2006 paper.
Second, we describe how $\operatorname{HMAC}^{NIST}$ (the FIPS version
standardized by NIST), while provably secure (in the single-user setting), succumbs to a practical attack in the multi-user setting.
Third, we describe a fundamental defect from a practice-oriented standpoint in Bellare’s 2006 security result for HMAC, and
show that because of this defect his proof gives a security guarantee that is of little value in practice.
We give a new proof of NMAC security that gives a stronger result
for NMAC and HMAC and we discuss why even this stronger result by itself fails to give convincing assurance of HMAC security.

from conclusion;

When HMAC is used with a hash function that is not collision-resistant, confidence in its security cannot come from the proof in [1] – or even from our proof in §10 – but rather must be based upon the large number of person-years that engineers and cryptanalysts have devoted to testing it. This is especially the case in an application
where one needs pseudorandomness and where short-term security is not enough.

There is a slide from Bernstein that covers the brawl around the above paper

2012 - The HMAC brawl


Why MACs are so important despite digital signatures doing everything a MAC can do and more

There are many advantages of MAC's over signatures.

For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow).

Instead you can simply agree an authentication key (or a key for an authenticated cipher). This allows much more efficient operations both regarding

the speed of calculation of creation and verification of the authentication tag / signature and
with regards to the size of the authentication tag / signature.

For many protocols the problem that the receiver can also spoof authentication tags is not a (huge) issue. It could be a bigger issue for protocols where the two participants use the same authentication key for both sending / signing messages and receiving / verification of messages. TLS, to name just one protocol, uses separate keys.


Is there a secure source of entropy on a typical microcontroller?

Most microcontrollers that are suitable for crypto I've seen have a variant with a hardware RNG. For example the PIC32 series by Microchip.

However, if not, what you could do is attaching some sensor to an ADC. It would depend on your environment what kind of sensor you could use. It can be anything, which is not easily manipulated (at least not in the LSB(s)).

Then, take the LSB(s) from the ADC, or better yet, use a randomness extractor. How often you can fetch me bits, and how many you can fetch at a time, depends on the ADC, the sensor and the environment, and the security level you want to reach.

If you can go a bit further than just your microcontroller, there are some small hardware circuits that can be used to create randomness. One example is using a diode's avalanche effect.

  Avalanche noise is the noise produced when a junction diode is operated at the onset of avalanche breakdown. It occurs when carriers acquire enough kinetic energy under the influence of the strong electric field to create additional electron-hole pairs by colliding with the atoms in the crystal lattice. If this process happens to spill over into an avalanche effect, random noise spikes may be observed.

In short, we can use a diode with some external circuitry to create random noise spikes. If we then amplify that signal and feed it to a comparator, we get a random bit string.


What does the cipher-text overhead means?

Cipher Text overhead is the positive difference in length between the encrypted text and the plain text.

In stream ciphers, the encrypted length is typically equal to the clear text so there is no overhead. However, when Initialization Vectors are used - this will add to the size.
In block ciphers, there is usually padding involved such that the size of the plain text increases to being a multiple of the blocksize. So the encrypted size is the size of the plain text + padding. Chaining mode and Initialization Vector also adds extra length.

I think your questions refers to stream ciphers where the key is used to generate the stream and then stream is XOR'ed with the plain text to get the encrypted text. i.e. the key itself is not used directly to encrypt the plain text. The key + some state is used to generate the stream. And then stream & plain text are combined (typically by XOR) to create the encrypted text.

OTOH, if you are referring to Hybrid Encryption as suggested in the comments, then this is the explanation - The advantage of PKI is that it does not require the 2 parties to share a common secretHowever, PKI is much more inefficient and slower than symmetric cryptosystems. A hybrid cryptosystem combines the convenience of a PKI with the efficiency of a symmetric encryption.

In hybrid encryption, the symmetric key to be used for the encryption is agreed upon using PKI, but the rest of the communication is encrypted by the symmetric key.

For very long messages, the bulk of the work in encryption/decryption is done by the more efficient symmetric-key scheme, while the inefficient public-key scheme is used only to encrypt/decrypt a short key value.


Yes.  Pollard's $\rho$, a generic method to compute discrete logs, costs only about $2^{128}$ group operations for a group of order about $2^{256}$ so secp256k1 should be considered to have a ‘128-bit security level’, not a ‘256-bit security level’, against discrete logs.  But a 128-bit security level is enough to thwart all adversaries—at least, the ones who don't have a quantum computer or a cryptanalytic breakthrough against secp256k1 in particular.


Distinguishing x25519 public keys from random?

A valid point of an elliptic curve in Weierstrass form satisfies the equation
$$
y^2 = x^3 + ax + b\,.
$$
We can rewrite this as $y = \pm \sqrt{x^3 + ax + b}$, which has either 2 solutions when $x^3 + ax + b$ is a square, 1 solution when $x^3 + ax + b = 0$, or 0 solutions when $x^3 + ax + b$ is not a square.

In X25519, we only see the $x$ coordinate, but we can still make use of the above. The curve equation is
$$
y^2 = x^3 + 486662x^2 + x \bmod 2^{255}-19\,,
$$
from which we have that given a valid public key $x$, $x^3 + 486662x^2 + x$ must have a square root modulo $2^{255}-19$. On the other hand, a random string will be a square only around $1/2$ of the time. By inspecting $n$ candidate public keys, we can improve our certainty to $1 - 1/2^n$.


XTEA brute force 128 bits key, 64 rounds

A 128-bit key contains 2128 possible combinations. Guessing the correct key in an exhaustive search will occur after approximately half that. This is true regardless of what cipher is used. Note that some ciphers are vulnerable to cryptanalysis which creates "shortcuts" to discovering the key. There are no known key recovery attacks against XTEA which can recover the key faster than an exhaustive search, though.


As @MaartenBodewes stated in the comments, just one method of cryptanalysis cannot show a hash function is secure.

Your question

  My doubt is: Is this method right? What bits of the input and output i have to include in the linear approximation, all?

has the following answer. In general, while doing linear cryptanalysis we try all possible subsets of input and output bits and look for biases in the resulting expressions. Thus there is a total of $2^{n+m}-1$ possible expressions to check.

Let $(a_1,\ldots,a_n) \in \{0,1\}^n,$ and $(b_1,\ldots,b_m)\in \{0,1\}^m.$ Then except for the case $(b_1,\ldots,b_n)=(0,\ldots,0)$ all the following expressions
$$
a_1 x_1 \oplus a_2 x_2 \oplus \cdots \oplus a_n x_n \oplus b_1 y_1\oplus \cdots \oplus b_m y_m
$$
need to be computed and their biases tested. We rule out $(b_1,\ldots,b_n)$ being zero since then then we're not computing anything interesting about the output of the hash function, but it is OK to let $(a_1,\ldots,a_n)$ zero since that tests the overall balance of the function, regardless of input.

In terms of more general analysis, there are obviously many other techniques, differential cryptanalysis, looking for collisions, looking for inverse images, etc. the latter two being directly related to hash function goals.


Is the XOR of PRGs sharing the same input a PRG?

Thank you everybody's help. I have known that if $f$ and $f_1$ have some relation, then $g$ can not be PRG.
e.g. $f = f_1$, then we can know, after $f ⊕ f_1$, it always return 0 for $g(x)$, in this case, $g(X)$ will never be a PRG.


"Encrypted hash" totally fails if the encryption uses a malleable mode like CTR. CTR runs AES in a stream-cipher-like mode where the data to encrypt is simply XORed with a key-dependent stream, so the attacker can flip bits with extreme precision; so if the attacker guesses the contents, he can modify them and fix the hash easily.

More generally, if you want a MAC then use a MAC. The "encrypted hash" is just a homemade attempt at a MAC algorithm, and we know that homemade algorithms are rarely strong, and even when they are we cannot make sure that they really are strong.

As for how to combine encryption and a MAC, this is a well-known questions for which a lot of theory and practice has been accumulated; see this question. To sum it up: you want to compute the MAC over the encrypted data, because it avoids any issue with the MAC algorithm leaking information on the processed data, and it protects the decryption implementation from malformed data.

Now, HMAC seems to be reasonably well-behaved and not to leak information about the data on which it is applied. Your setups 1 and 2 are what is used by, respectively, SSH and SSL/TLS. In neither case did it prove fatal; however, the lack of protection on the encrypted format allowed various padding oracle attacks to experience some success on implementations which were not sufficiently careful when decrypting malformed input data.


Anything is permitted as long as it works. The question you have to ask is what role a symmetric encryption plays in the protocol. If it is decrypted at some stage in the protocol potentially to a corrupted party, then you need to be able to simulate that and have it decrypt to the correct value. If it is never decrypted, then why is it ever used in the protocol?

Sorry for the self-citation, but you can read more about this at: https://eprint.iacr.org/2016/046.pdf.


Can a large file be hashed down to 32 bytes, and then reconstructed from the hash?

No, there is no way to compress (or hash or encrypt or whatever) a 5 MB file into a 32 byte hash and then reconstruct the original file just from the hash alone.

This is simply because there are many more possible 5 MB files than there are 32 byte hashes.  This means that, whatever hashing or compression or other algorithm you use, it must map many different 5 MB files to the same 32 byte hash.  And that means that, given only the 32 byte hash, there is no way you can possibly tell which of those different 5 MB files it was created from.

In fact, the same thing happens already if you hash 33 byte files into 32 byte hashes, and then try to reconstruct the original files from the hashes.  Since there are 256 times as many 33 byte files as there are 32 byte hashes, that already means that there must be several different files that have the same hash.  With 5 MB files, it's many, many, many times worse yet.

So how can something like IPFS work, then?

Basically, it relies on the fact that even the number of possible 32 byte hashes is really huge* — much, much larger than the total number of actual files (of any length) that humans have ever created, or are ever likely to create.  So, while we know that there must be many possible files that have the same 32 byte hash, the chance of actually finding two different files that just happen to have the same hash by chance is still so incredibly small that we can basically assume it will never happen.

(Also, cryptographic hash functions like SHA-256 are designed so that, hopefully, there are no practical ways to deliberately find files with the same hash more efficiently than by just hashing lots of files and hoping against all odds for a random collision.)

This means that if we have some kind of a (possibly distributed) database containing a bunch of files and their SHA-256 hashes, then we can be pretty sure that it will never actually contain two files with the same hash, even if that's theoretically possible.

Thus, as long as we have access to such a database, we can use the hash of any file in the database to look it up, and be almost 100% certain that we will only get one matching file back, not two or more.  Technically, the probability of getting multiple matches is not quite exactly zero, but it's so incredibly small that it can be safely neglected in practice.

*) In fact, it's 28×32 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936.


Recognizing and decrypting custom cipher with known plaintext and ciphertext

I figured it out.

keys = [k1, k2, ... , k20]
def encrypt(offset, message):
    ctext = []
    for i in len(message):
        ctext[i] = keys[(offset + i) % len(keys)] ^ message[i]

The "rotation" is caused by the "offset" parameter. The keys are stored in a rotation buffer and xored with plaintext bytes. The keys can be obtained by xoring a plaintext with a ciphertext.


Difficulty of breaking RSA for a given key size

No. Breaking a 1024 bit RSA key is not as difficult as breaking a 128 bit symmetric key. The consensus is that it is considerably less difficult, perhaps more comparable to breaking a 80-bit symmetric key, which is $2^{48}$ times less difficult than breaking a 128-bit key; that's a lot less difficult (a hundred million million times less difficult).

The reason is that breaking a 1024 bit RSA key can be attempted using an integer factorization algorithm, without exhaustively trying divisors. For the state of the art, see this article on the current factorization record.


In ECDSA, without knowing private key and any signature one can sign random garbage (from the Cryptography list)

An ECDSA signature works the following way:

We work in a sub-group of a curve. The generator is $G$ and it has order $q$ (a prime number). With most curves, $G$ actually generates the whole curve.
Private key is $x$, and corresponding public key is $Q = xG$.
To sign a message $m$:

Hash message $m$, with result being truncated/reduced modulo $q$: $h = H(m)$.
Generate a random $k$ modulo $q$ (or a non-random one, if using deterministic ECDSA).
Compute the point $kG$ and get its $X$ coordinate. The first half of the signature is $r = X \pmod q$.
Second half of the signature is $s = (h+xr)/k \pmod q$.

To verify a signature:

Hash message $m$ again, to get $h$.
Compute $w = 1/s \pmod q$.
Compute point $whG + wrQ$ and check that its $X$ coordinate, when reduced modulo $q$, yields $r$. Indeed, if the signature was properly computed, this expression recomputes the point $kG$ that was produced during signature generation.

There is no known forgery attack on ECDSA when expressed as above. The email you quote implicitly considers the case of ECDSA without the hash function. Or, said otherwise, whether one can make a forged value with $h$ considered as "message input".

For instance, take the point $Q$ (the public key) and extract its $X$ coordinate; call that $r$. Then set $s = r$. The $(r,s)$ pair is a valid signature for a message $m$ such that $h = H(m) = 0 \pmod q$. Indeed, it fulfills the verification equations: $w$ will be equal to $1/r \pmod q$, so $wrQ$ will yield simply $Q$, and since $h = 0$, then the $whG$ component will simply vanish. So the verifier will end up with point $Q$, whose $X$ coordinate indeed yields the $r$ value from the alleged signature.

Now this is not a true forgery in that you get a value which is a valid signature for a message that you do not know: the signature is valid for message $m$ which is such that $H(m) = 0 \pmod q$. But good luck with finding a matching $m$...

None of this is new, but it highlights the important role of the hash function in the process: ultimately, the preimage resistance of the hash function is crucial for resistance against forgeries.


Do we have to use an IV for AES encryption to be FIPS 140-2 compliant?

No you don't need to use an IV. However, this limits you to ECB mode only — the only one which doesn't use an IV — and your CAVP (Cryptographic Algorithm Validation Program) AES certificate will indicate so.


Do you need a HMAC if decryption attempts are severely limited?

"Given the above assumptions and limitations, is the encryption scheme still secure?"

No; the attacker can

remove blocks of [IV + rest_of_ciphertext] from either end to remove corresponding

plaintext blocks without affecting any other part of what it decrypts to
change the IV to change the initial plaintext block in the same way as for the OTP,

without affecting any other part of what it decrypts to
change any other plaintext block in the same way

at the cost of garbling the previous block
remove one or more consecutive internal plaintext blocks at the cost of

xoring the next plaintext block with a pseudorandom but predictable value

.   Furthermore, the attacker can combine those things in whatever order they want.

What follows can be improved if the algorithms can be stateful or there can

be associated data, but otherwise the best way to get short ciphertexts is:

key  =  $\langle$auth_string , PRP_key$\hspace{-0.03 in}\rangle$

encrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,iv,m$\hspace{-0.03 in}\big)$  =  PRP$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key ,$\langle$auth_string,m,iv$\rangle \hspace{-0.04 in}\big)$

decrypt$\big(\hspace{-0.04 in}\langle$auth_string,PRP_key$\hspace{-0.03 in}\rangle$,ciphertext$\hspace{-0.02 in}\big)$    =    if PRP-1$\hspace{-0.03 in}\big(\hspace{-0.03 in}$PRP_key,ciphertext$\hspace{-0.02 in}\big)$ parses as

an ordered triple whose left entry is auth_string then that triple's middle entry else $\bot$

auth_string being secret might help against some weakness in the PRP,

but otherwise even letting the attacker choose auth_string would be fine.

The "strong pseudorandom permutation" from Theorem 3.1 is the fastest large-domain PRP I'm aware of, and it will suffice if the number of encryptions is also sufficiently small

compared to ciphertext size.  There are other constructions that handle more queries

and/or ciphertext-space sizes other than powers of 4, with these being the simplest.


RSA How to select a value K such that $e d = 1 + k \varphi(N)$ holds

You apply the extended Euclidean algorithm to $e$ and $\phi(N)$ (which have to have gcd equal to $1$) and we get $x,y \in \mathbb{Z}$ such that

$$xe + y\phi(N) = 1$$

The $x$ (taken modulo $\phi(N)$, if needed) is the $e$ you are looking for. The $k$ is totally irrelevant for encryption/decryption, but it's actually the $y$ in the above equation (rewrite your equation and see).


All block ciphers leak information.  No matter the mode used there is a limit on the amount of data that should be encrypted with a single key, irrespective of the number of different IVs used, in order to not leak too much information that an attacker might be able to determine some of the encrypted data.  For AES, it seems that the limit seems to be around 64 GB no matter the mode.

See the book Cryptography Engineering: Design Principles and Practical Applications and the paper The Missing Difference Problem, and its
Applications to Counter Mode Encryption.


Statistical properties of hash functions when calculating modulo

The question asks if $\operatorname{SHA-1}(M)\bmod n$ is random, giving the example of $n=2^{80}$.

I'll consider arbitrary $M$ (that is, determined without knowledge of SHA-1, or just of SHA-1's 160-bit initialization constant), and that it makes $\operatorname{SHA-1}(M)$ indistinguishable from $160$ random bits (which is true from a computational perspective, baring any huge theoretical progress).

When $n=2^k$ for $0\le k\le160$ (including $n=2^{80}$ in the question), $\operatorname{SHA-1}(M)\bmod n$ is simply the integer with binary representation the $k$ low-order bits of $\operatorname{SHA-1}(M)$, thus is indistinguishable from $k$ random bits (proof sketch: an hypothetical efficient distinguisher for $\operatorname{SHA-1}(M)\bmod n$ can be turned into an efficient distinguisher for $\operatorname{SHA-1}(M)$).

For other $n$ of interest, that is $n=s\cdot2^k$ with odd $s>1$ and $\log_2(s)+k<160$, the low-order $k$ bits of $\operatorname{SHA-1}(M)\bmod n$ are the low-order $k$ bits of $\operatorname{SHA-1}(M)$, and similarly indistinguishable from $k$ random bits. However $\operatorname{SHA-1}(M)\bmod n$ is not uniformly random over the set $\{0\dots(n-1)\}$: low values are more likely than high values. When $n=3\cdot2^{158}$, odds that $\big(\operatorname{SHA-1}(M)\bmod n\big)<{n\over3}$ are $1\over2$, rather than $1\over3$ for a uniform distribution. For example, the generator specified by FIPS 186-1 Appendix 3.1 has such bias (but it does not matter much in the application).

Update: a comment asks a simple algorithm based on SHA-1 that, given an arbitrary input $M$, outputs an integer uniformly random on the set $\{0\dots(n-1)\}$ for some parameter $n$ with $0<n\le2^{160}$.

As previously stated, when $n$ is a power of two, we can use $\operatorname{SHA-1}(M)\bmod n$. This is also the case when $n<2^{90}$ or so, because the adversary gets a negligible advantage for computationally reasonable effort.

Whatever $n$, we can use the following:

$r\gets 0$ ($r$ is expressed as a 16-byte string)
repeat $h\gets\operatorname{SHA-1}(r\|M)$ and $r\gets r+1$ until $h\ge(2^{160}\bmod n)$
output $h\bmod n$.

The output is uniformly random based on the fact that in the final step, $h$ is uniformly random on the set $\{(2^{160}\bmod n)\dots(2^{160}-1)\}$, which contains a number of elements multiple of $n$.


What is the "successive-configuration relation"?

OK, let's first observe the usage of the word in-context:

  Definition 1.3.8 (Oracle Machines): A (deterministic/probabilistic)
  oracle machine is a (deterministic/probabilistic) Turing machine with
  an additional tape, called the oracle tape, and two special states,
  called oracle invocation and oracle appeared. The computation of the
  deterministic oracle machine $M$ on input $x$ and with access to the
  oracle $f:\{0,1\}^*\to\{0,1\}^*$ is defined by the
  successive-configuration relation. For configurations with states
  different from oracle invocation, the next configuration is defined as
  usual. Let $\gamma$ be a configuration in which the state is oracle
  invocation and the content of the oracle tape is $q$. Then the
  configuration following $\gamma$ is identical to $\gamma$ , except that the state is
  oracle appeared, and the content of the oracle tape is $f(q)$. The
  string $q$ is called $M$’s query, and $f(q)$ is called the oracle reply.
  The computation of a probabilistic oracle machine is defined
  analogously. The output distribution of the oracle machine $M$, on input
  $x$ and with access to the oracle $f$ , is denoted $M^f(x)$.

So the context we have is: Turing Machines!

Now if we look at the formal definition of a turing machine, we will spot a relation $\delta:(Q\setminus F)\times\Gamma\to Q\times \Gamma\times\{L,R\}$. Note how a function is actually just a relation.

This above function defines, when in a given state and looking at a given cell content, which cell content shall be written, where state shall be entered and which direction the head shall be moved. Thus, this relation defines the successive configuration for every configuration. However I'd guess that the relation used for the turing machine in question is a little bit more complicated than the one of the "basic" turing macine (also accounting for the special states and the extra tape).


Is it possible to figure out whether a plain TCP packet is (aes) encrypted or not?

Without knowing anything about the application layer protocol on top of TCP, it's very hard to answer this question.

A good symmetric cipher (like AES) will produce uniformly random bytes. So if the data in the packet looks uniform, there's a very good chance it's been encrypted. You won't be able to distinguish between different algorithms, though, and you probably won't be able to distinguish between different modes of operation.

Your best bet is to figure out the application protocol being used, and look at the corresponding messages establishing the connection.


How to encrypt file with RSA and AES that anyone with RSA key can decrypt them?

It sounds like you're looking for a hybrid crypto solution.  Some libraries provide APIs for this, e.g. libsodium.  Others, you have to build it yourself with the RSA and AES primitives provided, e.g. OpenSSL.

Without more information from you on your environment (e.g. programming language) it's really hard to provide any specific help.


What is the encoding protocol for passphrase protected RSA private keys?

This file format, which is used by OpenSSH below 7.8 by default for RSA, is actually defined and implemented by OpenSSL, which documents it fairly tersely on the man page for a group of library routines including PEM_write_RSAPrivateKey near the bottom at the heading "PEM ENCRYPTION FORMAT". Quoting for convenience and because of many Stack-ers' linkophobia:

The line beginning with Proc-Type contains the version and the protection on the encapsulated data. The line beginning DEK-Info contains two comma separated values: the encryption algorithm name as used by EVP_get_cipherbyname() and an initialization vector used by the cipher encoded as a set of hexadecimal digits. After those two lines is the base64-encoded encrypted data.
The encryption key is derived using EVP_BytesToKey(). The cipher's initialization vector is passed to EVP_BytesToKey() as the salt parameter. Internally, PKCS5_SALT_LEN bytes of the salt are used (regardless of the size of the initialization vector). The user's password is passed to EVP_BytesToKey() using the data and datal parameters. Finally, the library uses an iteration count of 1 for EVP_BytesToKey().
The key derived by EVP_BytesToKey() along with the original initialization vector is then used to decrypt the encrypted data. The iv produced by EVP_BytesToKey() is not utilized or needed, and NULL should be passed to the function.

EVP_BytesToKey itself is documented on its own man page and covered in numerous Stack questions or answers including one of my longer ones (which is actually about commandline enc but the EVP_BytesToKey part applies additionally to 'legacy-PEM' encryption).
The decrypted plaintext is the same as the unencrypted form, PKCS1 (rfc8017 et pred).
The ursine answer to this Q over in security also covers this and related formats in some detail.
For clarity note there are many other file formats for RSA keys, even within OpenSSL and OpenSSH much less other software; this is a scheme for some passphrase-protected RSA private keys but not the scheme for all such keys.


Can it ever be impossible to invert a PRNG?

I've read about the possibility of inverting the Mersenne Twister after 624 numbers of output. 624 matches the state size of my implementation of the Twister. Coincidence? If the generator only output 623 numbers, i.e. less than the state size, might inversion still be possible with really clever maths? Or is this mathematically and logically impossible?

No, it's not a coincidence. The period is related to the state size, and a smaller sample cannot allow unique inversion due to the fact that every shorter number sequence appears in the total output of MT (with equal frequency to boot).

In general the same does not have to be true. A PRNG can use its state "wastefully" in such a manner that not every state is possible and inversion can happen much earlier than state size. Or it can have correlations that break it even without inversion. Contrarily, an actual cryptographically secure PRNG is expected to produce much more output than the state size without ever being invertible.

So I doubt your equation holds without additional assumptions.


What is the overhead of GCM? And how are GCM tags signed by RSA/PKI?

If we're using the cyphersuite TLS_AES_128_GCM_SHA256; and GCM is using Encrypt-then-MAC (which appears to be always?) and is configured to use a 128-bit tag; and AES_128 is encrypting plaintext in blocks of 128 bits; then is GCM adding a 128-bit tag onto each one of those blocks (thus, halving the amount of cyphertext that can ultimately fit into the data payload of the L3 packet)?

No, the GCM is performed on the entire record; hence the overhead added by the GCM tag is 128 bits per record.  That is, the GCM encryption operation is given the plaintext (which is the original unencrypted record), the AAD (which is made up by the record header plus the record sequence number) and the nonce (the 8 bytes given in the record plus 4 bytes from the key negotiation step), and it produces the ciphertext (which is exactly as long as the plaintext) and a 16 byte GCM tag.  TLS doesn't worry about what GCM does to perform this operation.
The table you cite gives the overhead per record (however, it is mislabeled as per packet; TLS records do not correspond to 'packets'; there may be several records per TCP packet (segment), or a single record may extend over several packets).

How/where exactly is SHA and RSA (or any signature algorithm) used in this process?

SHA and RSA are not involved at all during the record encryption/decryption process, so none of your three options describe the situation.  They may be used (and generally are) during the connection set up phase (which verifies that the server is who he claims to be (and optionally the client as well), and also generates the symmetric keys that GCM uses.


Converting a pre-image resistant hash to second pre-image resistant

Yes.  I believe this is the standard conversion.

(That link is to the paper "Universal One-Way Hash Functions via Inaccessible Entropy".)


Cryptanalysis of AES on SSD with TRIM enabled

A conceivable attack is inspired by this extract of LUKS On-Disk Format Specification
Version 1.1.1, section 1:

  A partition can have as many user passwords as there are key slots. To
  access a partition, the user has to supply only one of these
  passwords. If a password is changed, the old copy of the master key
  encrypted by the old password must be destroyed. Peter Gutmann has
  shown in [Gut96], how data destruction shall be done to maximise the
  chance, that no traces are left on the disk. Usually the master key
  comprises only 16 or 32 bytes. This small amount of data can easily be
  remapped as a whole to a reserved area. This action is taken by modern
  hard disk firmware, when a sector is likely to become unreadable due
  to mechanical wear. The original sectors become unaccessible and any
  traces of key data can’t be purged if necessary.

Assume that a weak or compromised password has been used, then the password changed with hope of restoring security. Due to wear-leveling on the SSD, the master key enciphered using the weak or compromised password may remain physically on the drive, although it is no longer logically mapped. In theory, reading the bare flash in the drive (either physically, or using some undocumented commands that may or may not exist in the SSD firmware, perhaps after loading an instrumented version of that) may allow reading the block(s) still containing the master key enciphered using the weak or compromised password, which in turn trivially breaks the whole encryption. It is hard to tell if the " anti-forensic information splitter " of LUKS can prevent that.

This attack is in theory also relevant in the context of blocks that become bad on traditional hard drives (the original data then becomes logically unmapped while potentially physically there, unless the drive physically erases it after remapping, which is not an advertised feature); but the odds that precisely the block(s) enabling the attack becomes bad are minuscule. The odds are less low with a SSD, especially soon after the password is changed.

TRIM likely impact the odds of the attack to succeed, because it modifies the blocks erased by the wear-leveling algorithm, but I can't tell if that will increase or decrease the odds. I can vaguely imagine algorithms in which the periodical erasing of TRIM makes it unnecessary to use backup means to recover unused space, making it more likely that blocks logically rewritten in seldom rewritten areas still have their former values physically there.

I guess that reading logically-rewritten but still-physically-there blocks in SSD has become a forensic trick for high-value target and some SSD. But I have no indication that the LUKS attack I discuss was ever attempted, much less successful. I would fear, much more, a compromise of password or master key by more traditional means (key-logger, camera, paper backup of password, configuration goof, compromized software, DMA memory grabber..)


Statistical attacks on a list of MD5/SHA-1 hashes?

The comments sum it up perfectly…

  Poncho’s comment:
    None are known, and it would be a significant result, as you really do see hashes like that in practice...

and

  Maarten Bodewes’s comment:
    MD5 and SHA-1 have been broken for collision, but then the input should still be formatted in a specific way. More importantly for your question: there is still no chance of finding the input (without "guessing" it correctly); they are still one-way-functions.


Can we get the msg when we know tag and key in Poly1305

Can we get the $msg$ from this?

Yes, as long as we know the nonces, and as long as $msg$ is no more than $128n$ bits long, and $n$ isn't too incredibly huge (the latter might not be a required assumption, I just need it for my approach).

Poly1305 can be modeled as computing a tag this way:

$$tag = c_a r^a + c_{a-1} r^{a-1} + … + c_1 r^1 + z - 2^{128} k \bmod {2^{130}-5}$$

where (in your scenario) you know the value $r$ and $z$ (they're a function of the key and the nonce, which you know) and don't know the values $c_a, c_{a-1}, …, c_1$ (that's an encoding of the message) and the value $k$ (which is between 0 and 3); $k$ is here to account for the outer '$\bmod 2^{128}$ operation that Poly1305 performs.

If we have $n$ such tags, we can set this up as $n$ simultaneous linear equations in the unknown $c_a, c_{a-1}, …, c_1$ variables.  We don't know the $k$ variables, hence we would need to go through the $4^{n}$ combinations of the $n$ different $k$ variables, and solve each one individually (and after obtaining a solution, we would check the message to see if Poly1305 processes the message as expected - it may encode the message to a different set of $c$ variables, or assign a different value for a $k$ variable.

If $n \ge a$, this gives us enough equations to find a solution; if $n > a$, this solution is likely to be unique.

This involves assuming $4^{n}$ sets of $n$ linear equations; as long as $n$ isn't too large, this is practical.


How do I calculate a password space if the password only has eight alphabetic characters (not case sensitive)

The choice of 8 fully random characters is exactly 3 bits as $\log_2(8) = 3$. So to calculate the strength in bits you simply multiply with the size of the password: e.g. 16 * 3 = 48 bits of strength for 16 characters.

To translate that to the password space - the number of possible passwords - you simply can perform $2^{48}$ which means that there are 281,474,976,710,656 possible passwords. A little known trick to get an idea of the number of decimal digits is to multiply by 3 and then divide by 10 and round up: so $\large\lceil\normalsize{48 * 3 \over {10}}\large\rceil\normalsize = 15$, i.e. above number contains 15 digits. A more direct method is to simply perform exponentiation with the password size: $8^{16}$ will give you the same large number. However, I use the trick above to perform such calculations without calculator.

Note that protection against brute force should require key stretching by e.g. using a password hash. For such kind of passwords additional protection (such as account locking) should be implemented. The system needs to deal with low entropy passwords.

The trick above depends on a little known constant: 3.3219280948873626. This is the result of $\ln(10)\over\ln(2)$, i.e. each decimal digit takes about 3.3219280948873626 bits to be represented. It's quite close to 3.3333 wich makes calculations rather efficient. The little difference makes it so that $2^{10} = 1024$, or just over a thousand (a kilo in ancient Greek).


If a computer is doing the selection of PIN numbers, then you would be very lucky indeed to guess a PIN in three times. The entropy - assuming that all numbers are valid - is of course $\log_2{10^8} \approx 26.57$ bits.

The chances of guessing the PIN correctly in 3 tries is $$1 - \frac{x-1}{x} \cdot \frac{x - 2}{x-1} \cdot \frac{x-3}{x-2} = 1 - \frac{x-3}{x} = \frac{x}{x} - \frac{x-3}{x} = \frac{x}{x} + \frac{-x+3}{x} = \frac{3}{x}$$ where $x$ is $10^8$, so $3\times 10^{-8}$ or just $0.00000003$. This is basic math (which I managed to get wrong quite a few times, thanks to Max O. for correcting me the last time around).

Once you have a limited number of tries, the different technologies make no difference anymore. Quantum computing will allow faster computations, but since you only get 3 tries, speedup is not of any interest.

If a user creates a PIN then PIN numbers such as 00000000 are  very likely, and your chances depend very much on the person choosing the PIN. Some banks will therefore disallow the exceptionally stupid ones, leaving just the normally stupid ones. Even smart persons have been shown to be terribly bad at generating random numbers. How bad they are is hard to know, it very much depends on the target audience, I presume.


It would help to understand the context a little.  I'm assuming you're trying to arrive at a password-based key and you're trying to maximize the brute-force time required to guess the key.  But maybe this data will be used as a tag, or you're interested in maximizing the time to create a password-key dictionary or something.

I would consider the search space an attacker would have to go through in making your decision.  The first one has a search space of $|passwordBytes|\times|salt|$.  The second has a search space of $|passwordBytes|\times 2\times|salt|$, so requires $O(2^{|salt|})$ more computation.  Doubling the iteration count just doubles the computation (i.e. adds one bit of complexity).  The time to compute a dictionary would be higher for your second option.

However, it would actually be easier to say something about just the first 20 or just the last 12 bytes in the second scheme (since it uses a lower iteration count), which could allow brute-forcing the other half even more trivially.  To prevent this, you'd do better to follow CodesInChaos's suggestion and cascade operations, but make sure the final output is a single output from a secure primitive.  For instance, you might use $tmp = PBKDF2(passwordBytes, salt1, 50000)$ to get $|passwordBytes|$ of data, then use $SHA256(PBKDF2(tmp, salt2, 50000))$ (or even just $SHA256(tmp || salt2)$) to get 32 bytes.  This makes the search space as big as $|passwordBytes|\times 2\times|salt|$ but doesn't leak information from just one or the other halves of the output.

In any case, depending on how you're using the data, I suspect some other primitive (like SHA-256) might be useful for you.


How does the security parameter within a digital locker help prove that it unlocked correctly?

They mention $H(nonce, key)$ is modeled as a random oracle.
Then, $H(nonce, key) \oplus M\cong U\oplus M$ where $U$ is uniformly random, so the encryption scheme (essentially) becomes the one time pad.
This is a fairly standard construction.

One "flaw" with the one-time pad is that everything has a valid decryption.
Given that this is the case, how can you be sure you have the "right" key for some ciphertext?
The solution they mention is looking for the string $0^s$ at the end of your plaintext.
This will:

Always appear if you have the correct key for some ciphertext
Almost never appear if you have the incorrect key for some ciphertext (specifically, it will appear with probability $2^{-s}$, so you'll detect the incorrect key was used with probability $1-2^{-s}$).

This is morally equivalent to something like a checksum, and can probably be formalized using the terminology of error-correcting codes (but I won't attempt to).


You don't appear to have done anything wrong; you can double check your result by computing:

  $16657^5 \bmod 16781$

and find that it is indeed 5347; that is, 16657 is the number that, when encoded with the public key, results in the value you were given.

I suspect that moral of this story is that random examples on the internet might be worth just as much as you pay for them.


Can this be done?

In general, there is a way: you can prove the statement you sketch using zero-knowledge proofs. Due to [1] we know that zero-knowledge proofs for any language in NP exist. Let us write down what you want to prove as an NP language $L$. Therefore let $\sf (sk, pk)$ be the key pair, consisting of a secret key $\sf sk$ and a public key $\sf pk$, and let $\sf pk'$ be the public encryption key (corresponding to some secret decryption key $\sf sk'$) used to encrypt $\sf sk$ so that $C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)$, i.e., the ciphertext $C$ contains an encryption of $\sf sk$ under public encryption key $\sf pk'$ and $\rho$ denotes the randomness used upon encryption. In addition we may assume without loss of generality that there exists an efficient algorithm $\sf VKey$ which takes as input a key pair $\sf (sk, pk)$, and outputs $1$ whenever $\sf sk$ is the key corresponding to $\sf pk$ and $0$ otherwise. Now we can write down $L$ as follows:
$$
L = \{ ({\sf pk'}, C, {\sf pk}) ~|~ \exists~({\sf sk}, \rho) : {\sf VKey}({\sf sk},{\sf pk}) = 1 ~\land~ C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)\},
$$
Clearly, if we know $({\sf sk}, \rho)$ corresponding to a tuple $({\sf pk'}, C, {\sf pk})$ we can efficiently verify membership in $L$. Therefore $L$ is indeed an NP language.

Efficient instantiations?

Regarding efficient instantiations one needs to be careful, as the most efficient approach no longer allows to obtain $\sf sk$ upon decryption but only $\sf pk$. In particular, assume that we have some group $\mathbb{G}$ of prime order $p$ generated by $g$ where we assume the decisional Diffie-Hellman assumption to hold. Now assume we use some scheme where the $\sf sk$ is a random element in $\mathbb{Z}_p$ and the corresponding public key is its "image" in the group with respect to $g$, i.e., ${\sf pk} = g^{\sf sk}$. Additionally assume that we choose to use exponential ElGamal in $\mathbb{G}$ as encryption scheme, (i.e., ${\sf Enc}({\sf pk}', {\sf sk}) := (g^r, {\sf pk}'^r \cdot g^{\sf sk})$ for some uniformly random $r$ in $\mathbb{Z}_p)$. Now, one may observe that we can no longer efficiently obtain $\sf sk$ upon decryption but only $\sf pk$. However, if your use case does not require to be able to recover $\sf sk$ upon decryption the aformentioned instantiation is very efficient: one can make use of $\Sigma$-protocols (see, e.g., [2]).

If your use case also requires to be able to efficiently recover $\sf sk$ upon decryption, you will require more costly zero knowledge proofs: for example encrypting a bit-wise representation of the key and proving the statement with respect to this bit-wise representation of the key, or to use Paillier as an encryption scheme, which however may require zero-knowledge proofs over groups of different orders (see e.g., [3]).

Instantiations using a symmetric encryption scheme?

In case you want to use a symmetric encryption scheme things will get a lot more expensive as this would require to prove statements over general circuits and also to somehow make the link to the algebraic setting where the keypair $({\sf sk}, {\sf pk})$ lives in. You could have a look at this paper [4] to find out more about how this could be instantiated.

Also note that, in contrast to asymmetric encryption schemes, symmetric encryption schemes are typically not binding. Thus such an instantiation will require some additional measures to ensure that the encryption key you use to prove the statement is indeed the key it should be.

Bottomline

I think that using an asymmetric encryption scheme will be preferable in practice - if your use case allows it at all. Even if one might have to do ZK proofs over groups of different orders this will be much more efficient and much simpler to implement compared to using a symmetric encryption scheme.

References

[1] http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

[2] http://www.cs.au.dk/~ivan/Sigma.pdf

[3] https://pdfs.semanticscholar.org/ad71/f5dcef871bdfaad01be9da6d378b010b36d4.pdf

[4] https://eprint.iacr.org/2016/583.pdf


How to generate a 128 bit IV from a 32 bit value for AES-128 OFB

OFB mode directly uses the IV as input to the block encryption - in this case by AES. So generally there is no 32 bit IV possible, it must be exactly the same size as the block size of the block cipher. OFB does not define any way to go from a 32 bit nonce to a 128 bit IV - if such an operation is defined then it is defined outside of the OFB definition in NIST Special Publication 800-38A: Recommendation for Block Cipher Modes of Operation.

Usually however the 32 bits are simply defined as leftmost bits of a 128 bit value, with zeros appended to the right hand side. Putting the values on the right hand side may also be a possibility however. Actually the bits can be put through any operation and put in any place as long as the result remains unique. But it seems unlikely that such an operation takes place at it would not have any function. Just try copy the bytes into the front or the back of a 128 / 8 = 16 bytes buffer and try if you guessed correctly.

Or ask the person that created the protocol of course, it never hurts to ask such a thing because they should have defined it for you.


Where was the stand-alone model for simulation-based MPC proposed first?

The standard (stand-alone) definitions were developed over many years, including the original GMW, Beaver, Goldwasser-Levin, and Micali-Rogaway. However, the standard definition used today is by Canetti, and was published in the Journal of Cryptology in 2000. That paper also proved the modular sequential composition theorem. Here is a link to that paper: https://eprint.iacr.org/1998/018.

It is worth nothing that the above paper actually only deals with the honest majority setting. However, the changes needed for a dishonest majority are minor and straightforward, and make no difference to the proof of the modular sequential composition theorem.


For any reasonable RSA-based encryption (or signature) scheme, exponent $e = 3$ is a perfectly good choice and provides the best performance for the public-key operation short of qualitatively different Rabin-type schemes.

Don't use RSAES-PKCS1-v1_5.
RSAES-OAEP of PKCS#1 v2 is reasonable in this sense, though it is unnecessarily complicated.
RSA-KEM is even more reasonable and much simpler.

But there are people out there who have PTSD from decades of bad crypto engineering with horrible flaws that are sort of halfway patched over by using larger exponents like $e = 65537$.  So some auditors might summarily reject $e = 3$ when they see the letters R, S, and A, without looking at the elephant in the room of what specific encryption or signature scheme you're using that involves RSA.


Limit the length of AES encoded output to certain value

AES operates on 128 bits of data. We can use modes of operation to turn AES (and any block cipher for that matter) into something that can handle longer (or shorter) data. If you want the ciphertext to be limited to X bits (above you said characters, I'm switching this to bits to make things easy), X must be at least as long as the plaintext data (compression may change that, but you must be very careful).

Using a stream-like mode (which would turn AES into a stream cipher) such as CTR mode, the plaintext text length and ciphertext length will be the same. Using a mode like CBC, the ciphertext will be slightly larger (at most 255 bits longer).

The two modes I listed above only provide confidentiality guarantees. This can be devastating to security, however. Especially if you are using a stream-like mode. To add integrity, you can use something like HMAC or an authenticated encryption scheme. If at all possible, you should do this as it would prevent entire classes of attacks. Authenticated encryption will make the output of the cipher longer than the plaintext, because it adds an authentication tag to the data.


Efficient algorithm for remainder calculation over prime field for ECC implementation?

See section D.2.2 of FIPS 186-3. The modular reduction can be expressed as two additions and two subtractions of values which are assembled by concatenating selected 32-bit words of the 448-bit value which is to be reduced. Note that these additions and subtractions are modular, so you may have to mind some carries.


What is the difference between Shannon entropy and saying that tossing a 6-sided die 100 times has more than 256-bit entropy?

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits.

That is wrong: $-6\cdot\frac16\cdot\log_2\frac16$ is the entropy of a single die roll. Assuming the $100$ die rolls are independent, you can simply sum the entropies of the individual rolls to obtain
$$ 100 \cdot\left(-6 \cdot\frac16\cdot\log_2\frac16\right) \approx 258.49625 \text, $$
which is precisely $\log_2(6^{100})$ as expected.


AES is  a block cipher which actually only "maps" (encrypt) a 128 bit block (plainblock) to a 128 bit block (cipherblock) and vice versa. This "mapping" is key dependent.

To encrypt some data you normally apply an encryption mode like CBC, CTR, GCM etc. using e.g. AES as block cipher within this mode. These modes normally require an IV or Nonce.

So, not the actually AES requires an IV but the mode used to actually en-/decrypt data.


In the Linux Kernel 4.8+, does the CSPRNG update the entropy pool?

The CSPRNG is updated from the input pool from time to time (at most every 5 minutes by default). It does not feed back into the input pool since it is derived entirely from it in the first place.

Prior to 4.8, the input pool would periodically feed into the blocking pool and non-blocking pool at long enough intervals to provide a "catastrophic reseed" that mixes in enough entropy that it could not be brute forced even given knowledge of the prior state. These two pools were identical, with the exception that the blocking pool would track entropy estimates and block if the estimate drops too low. Since 4.8, the non-blocking pool has been replaced by a CSPRNG based on the ChaCha20 stream cipher.

From Documentation and Analysis of the Linux Random Number Generator, version 2.5


Role of long-term asymmetric keys in a forward secrecy instant messaging protocol?

I don't think you are wrong on any of the points.

"Perfect forward secrecy" is a confusing name. Indeed it means that somebody who gets hold of one of the keys cannot use it to decrypt messages from the past.

There are two more properties you usually want:

When somebody does impersonate Alice or Bob as you suggest this should cut the real partner out of the conversation to make it detectable.
When somebody acquires a key he should not be able to decrypt messages after Alice and Bob have switched to a new key. Sometimes called backward secrecy.

There are probably more that I didn't think of right now and it case of group messaging it becomes even more complicated.
Dealing with these will make your steps (3.) - (5.) much more complex!


How much computing resource is required to brute-force RSA?

It's not possible.

The number of primes smaller than $x$ is approximately $\frac{x}{\ln x}$. Therefore the number of $512$ bit primes (approximately the length you need for $1024$ bit modulus) is approximately:

$$\frac{2^{513}}{\ln 2^{513}}-\frac{2^{512}}{\ln 2^{512}} \approx 2.76×10^{151}$$

The number of RSA moduli (i.e. pair of two distinct primes) is therefore:

$$\frac{(2.76×10^{151})^2}{2}-2.76×10^{151}=1.88×10^{302}$$

Now consider that the observable universe contains about $10^{80}$ atoms. Assume that you could use each of those atoms as a CPU, and each of those CPUs could enumerate one modulus per millisecond. To enumerate all $1024$ bit RSA moduli you would need:

\begin{eqnarray*}
1.88×10^{302}ms / 10^{80}&=&1.88×10^{222}ms\\
&=&1.88×10^{219}s\\
&=&5.22×10^{215}h\\
&=&5.95×10^{211} \text{years}
\end{eqnarray*}

Just as a comparison: the universe is about $13.75×10^9$ years old.

It's not a question of resources, it's simply not possible.

Also, it would not make any sense to do that. There are much faster ways to find out a secret key. In fact there are algorithms with sub-exponential running time for factoring integers.


Is there an algorithm to check if an elliptic curve is secure?

Let's suppose that you work in field $\mathbb{F}_p$ for a prime $p$; i.e. the $x$, $y$, $a$ and $b$ values are integers modulo $p$. The curve order $n$ is the number of points on the curve. By Hasse's theorem we know that $n$ is relatively close to $p$; namely, the theorem states that:
$$|n-(p+1)| \leq 2\sqrt{p}$$
So you get a range of possible values for $n$. The exact value depends on $a$ and $b$.

For cryptography, you normally need $n$ to be the multiple of a big enough prime. "Big enough" means $2b$ bits if you are after a "security level" of $b$ bits (i.e. resistance to attacks for a work factor of at least $2^b$). In practice, to make things simpler, you will want $n$ (the complete curve order) to be prime. So the algorithm you seek is roughly:

Compute the curve order. This uses Schoof's algorithm or a variant thereof. This yields $n$.
Check that $n$ is prime. If not, try again with new values for $a$ and/or $b$.
Do some extra checks.

The "extra checks" are about the MOV and FR attacks, which use pairings. This is a complex matter; to make the story short, there is a value called the embedding degree which is the smallest integer $k \geq 1$ such that $n$ divides $p^k-1$. Your curve will be safe if $k$ is high enough; it suffices that $k\geq 100$ (and that's with a wide error margin). In practice, with random $a$ and $b$, $k$ will be very high with overwhelming probability; however, testing all values $k$ from $1$ to $100$ is easy enough, so testing it is not a big issue. ANSI X9.62 recommends that test.

Schoof's algorithm (step 1) is deterministic. There are deterministic algorithms for primality, but usually we use Miller-Rabin, which is probabilistic but much more efficient. In any case, difference between deterministic and probabilistic has little practical relevance, because there is no computer which is really 100.0% reliable; a stray cosmic ray can still flip a transistor at the right time (or the wrong time, depending on your point of view). If you use Miller-Rabin with 50 iterations, you will get as much certainty of primality as you could ever get in the Physical World.

All of the above assumes that $a$ and $b$ are chosen randomly. Actually, $a$ can be fixed to some value (many standard curves use $a = p-3$, which yields a slight computational advantage in some implementations of point addition). If $a$ and $b$ are not chosen randomly, but with specific features, then you could obtain a weak(er) curve. Or you could loop forever; for instance, if you choose $a$ and $b$ such that the curve is a Montgomery curve, then $n$ is always a multiple of $4$, hence never a prime.

(See the Handbook of Elliptic and Hyperelliptic Curve Cryptography for details. The Guide to Elliptic Curve Cryptography is also a nice book; less complete but still full of information, and possibly clearer in its practical aspects.)


AES-256 with random key generation instead of hash

We know that you can't invert the AES encryption to determine it's key at present.  So you're fine there, as long as you are able to generate all 256 bits in the uniformly distributed way.  Any decent random number generator will be able to do this as long as it can be seeded correctly.  If there is some mathematical relationship between the files (you derive from) and the key, you'll need to make sure that the file entropy fits into the random number generators state space.  This can be a little tricky sometimes, and there are examples like the seeding mechanism of RC4 that's quite poor and can lead to /induce weak states.  This then has a detrimental effect on the generator's output.  Similarly, correctly seeding a large state generator like the Mersenne Twister is difficult. This is all however an implementation issue.

One security issue lies with the IV.  This is stored in plain form.  In order to maintain security, the IV must be generated from a cryptographically secure generator.  Otherwise it might be quite simple to determine an insecure generator's state and thereby predict all IVs. Since you need a CSRNG for the IV, you might as well use the same generator for the 256 bit key.  The same issue of correct seeding still remains however.

The other issue is if you transmit the same file repeatedly.  The purpose of the IV is to make sure that the cipher text is unique per transmission, even if the plain text is the same.  If the IV /key pair are directly (and only) related to the encrypted file contents, the cipher text will always be identical.  This may not be an issue for disk storage, but can be for copying /transmission as it leaks some information.

My sense would be to have some form of salt anyway.  Without it, the system feels very predictable as all the information is there in hard coded form.  Something that only you know would improve the security.


Proper number of salt bytes for Rfc2898DeriveBytes/PBKDF2

Short Answer: 8 bytes are fine

Longer answer: The point of the salt in a password hash is, to prevent the precalculation of a list of hashes, usually done in the form of rainbow tables. If someone still wants to do precalculation, he will have to build one rainbow table for every single possible salt value, thus you are increasing the storage requirements of your adversary.

With a 8 byte salt, the adversary will need to build $2^{64} \approx 10^{19}$ tables. The size of those tables varies depending on the types and length of password you are trying (you can find a nice overview here), but you typically expect something in the 2-3 digit gigabyte range ($10^{11}-10^{12}$ byte). Putting this together, storing rainbow tables for 8 bytes of salt would require something in the range of $10^{30}$ bytes, which is completely impossible.


Why is $e=0$ allowed in Schnorr signatures?

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed?

Because $e = 0$ is not unique in this regard. Every single $e$ is equally "insecure", i.e. you may as well ban $e = 23$ with the same reasoning.

To exemplify, assume $e = 23$ arbitrarily (holds for any value of $e$ with the same reasoning). For that $e$, I can easily compute a signature by choosing a random scalar $0 \leq s < n$ and computing $R = sG+eP$. By definition, $(R,s)$ is a valid signature.
For $e = 0$, this is probably the attack you had in mind.

Of course, in reality this attack is not going to be successful because if I try to choose $R$ "cleverly" for a specific $e$, with overwhelming probability this is not going to be the $e$ with $e = H(R||M)$ (assuming the hash function is good). The trick here is that $e$ is only fixed after $R$ is already chosen, which makes it secure.

There is a deeper reason behind all this linked to the security proof, which does not at all care about any $e$. I'm not doing the proof justice with the following sketch, but very, very, very roughly, the reduction runs the attacker twice: once with $e$ and once with some other hash value $e'\neq e$ (modeling $H$ as a random oracle). The reduction only requires $e - e' \neq 0$ (which is the actual "weak spot 0", but it only occurs in the security proof) to compute the signature's secret key given a successful attacker. If you are interested, I recommend a look into Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures.