Provable security of cryptographic hash functions

First this, a nit about the hash function: one can trivially create a collision by appending a 0 value; an appended 0 does not change the hash value, and hence that produces a collision.

If we say that collisions are required to have at least one place there two colliding messages differ with at least one having a nonzero value, then we can show it.  Here is how, given a black box which finds a collision, can perform discrete logs (with good probability).

Suppose we have the elements $G$ and $H$, and which to find the value $k = log_G H$, that is, the solution to $kG = H$.

What we do is select $h_i = r_i G + s_i H$, where $r_i, s_i$ are random values.  Then, present these $h_i$ values (along with the rest of the parameters) to the black box.

The black box will produce a collision, that is, two messages $m, m'$ with $\sum m_i h_i = \sum m'_i h_i$.  Rewriting this, we get $(\sum (m_i - m'_i)r_i)G + (\sum (m_i - m'_i)s_i) H = 0$, or $aG + bH = 0$, for values $a, b$ which we can compute (as we know the $m_i, m'_i, r_i, s_i$ values)

As the $r_i, s_i$ parameters are random values unknown to the blackbox (and at least one of the $m_i - m'_i$ values will be nonzero), it is unlikely that $b$ will be 0; if it is not, then we have $k = -ab^{-1}$


Why does spiped use both nonces and ephemeral keys?

Without the nonces, one could violate explicit authentication

by replaying the group_element || MAC_tag messages.


Find plaintext from two ciphers encrypted with a one-time pad and the same key

First, there seems to be a misunderstanding: The one-time pad is the key. So your equations simplify to
$$ C_1 = L_1 + K \text, $$
$$ C_2 = L_2 + K \text. $$

At this point, you would be right if the $L_i$ could contain arbitrary bit sequences. However, the question imposes a constraint: $L_i\in\{A=\mathtt{1111},B=\mathtt{0011},C=\mathtt{1010}\}$.

Let's look only at the first bit of all the variables (I'll denote these in lower-case). Since $c_1=c_2$ by observation, you know that $l_1=l_2$ from the equations above. Hence given the alphabet from the question, we know that either both $L_1$ and $L_2$ are $B=\mathtt{0011}$, or they are both not $B$. You can proceed similarly for the next bits, and at some point you should be able to reduce the set of possibilities to one unique solution.


Taking $n-1$ bits from hash function will also be hash function?

If $\mathcal{H}=\left(\text{Gen},H\right)$ is a collision resistant hash family does $\mathcal{W}=\left(\text{Gen},W\right)$ where $W_{s}\left(x\right)$ denote the $n-1$ left most bits of $H_{s}\left(x\right)$ is also collision resistant hash family?

In general, no.

Let us assume that $\mathcal{H}'$ is a collision resistant hash family, and define $\mathcal{H}_k(x || b) = \mathcal{H}'_k(x) || b$, where $b$ is a single bit.

$\mathcal{H}$ is collision resistant (as a collision in $\mathcal{H}_k$ would imply a collision in $\mathcal{H}'_k$); however $\mathcal{W}$ is not, as $\mathcal{W}_k(00) = \mathcal{W}_k(01)$


Hash decrypts key, key decrypts cipher... why?

There are several reasons to use a scheme like this:

As several other answers have pointed out, it allows changing the password without re-encrypting the entire file.
Also, it allows re-encrypting the file without changing the password, should this be desired.  In particular, a careful implementation can allow incremental re-encryption, so that the file can be accessed while the re-encryption process is running, and so that the re-encryption process can be safely resumed even if the computer crashes while it's running.
Using an intermediate key also allows multiple passwords to be defined for the same file without having to store all the data twice — just encrypt the same inner key with each password and store them all in the header.

It's also possible to support other authentication methods besides plain passwords; for example, the inner key could be encrypted with the public half of a public/private key pair (RSA, DSA, etc.), with the private key perhaps in turn stored in an encrypted key file and/or on removable media.  You could even have the file accessible both with a password and with a private key file if you like.

(For technical and performance reasons, you do not want to use public-key crypto algorithms to directly encrypt large files, so in practice, whenever you use such keys for file encryption, this is exactly what you do anyway — encrypt the file with a random symmetric key and then encrypt the random key with the public key.)
And yes, it also ensures that two identical files encrypted with the same password won't have the same ciphertext.  Granted, there are other ways of ensuring this, but it's still a useful side effect.


Relation between entropy and min-entropy

There is min-entropy, Shannon entropy, and max entropy. (Plus a few more definitions, but let's only focus on these.) All of these measures are greatest, for a given number of outcomes, when each outcome occurs with equal probability. (In such case all three are equal.)

$$\text{min-entropy} \leq \text{Shannon entropy} \leq \text{max-entropy}$$

Min-entropy describes the unpredictability of an outcome determined solely by the probability of the most likely result. This is a conservative measure. It's good for describing passwords and other non-uniform distributions of secrets.

$$\text{min-entropy} = -\log_2{(p_{\text{max}})}$$

Say you have an algorithm which produces 8 digit numeric password. If the number 00000000 occurs 50% of the time, and the remaining $10^8 - 1$ passwords occur with equal probability, then the Shannon entropy would be about $14.3$ bits, but the min-entropy is precisely $1$, which is $-\log_2{(0.5)}$.

Min-entropy can be associated with the best chance of success in predicting a person's password in one guess.

Shannon entropy is defined to equal $$\sum_{i=0}^n{-p_i\log_2(p_i)}$$ for a probability distribution $p$ with $n$ possible outcomes. Shannon entropy describes the average unpredictability of the outcomes of a system.

It also measures how much information is in a system (on average). Shannon entropy is the smallest possible average file size for a compression algorithm designed specifically with the distribution $p$ in mind.

Max-entropy is defined solely on the number of possible outcomes. It is equal to $-\log_2(n)$. It's not particularly useful in cryptography or passwords. It's a measure of the number of bits you would need to have to designate one bit pattern for every possible outcome.

The three quantities are always the same for a uniform distribution. This is because $p_i = p_\text{max} = \frac{1}{n}$.

$$-\log_2(p_\text{max}) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

$$\sum_{i=0}^n{-p_i\log_2(p_i)} = n(\frac{1}{n} \log_2 (\frac{1}{n})) = -\log_2 (\frac{1}{n}) = \log_2 (n)$$

This is why passwords picked from a uniform distribution (using a secure RNG) are said to be stronger than human generated passwords. Humans are biased in which password they choose. (Their password distribution is non-uniform.)


Share secret non-interactively in a verifiable way

After looking a bit more into it I found a solution which I think should work.
I combined ECDH with AES todo the following:
Message Generation

I generate a new Elliptic Curve key pair (sesPk, sesSk)
I generate a key for each receiver: key_i = ECDH(sesSk, receiverPk_i)
I generate a message for each receiver: msg_i = AesEnc(key_i, sesSk||secret)
I combine the messages: msg =  sesPk||msg_0||...||msg_n

Secret Extraction

I generate my key: key_i = ECDH(mySk, sesPk)
I decrypt my message: sesSk||secret = AesDec(key_i, msg_i)

Secret Verification

I generate all keys: key_i = ECDH(sesSk, receiverPk_i)
I decrypt all messages: sesSk_i||secret_i = AesDec(key_i, msg_i)
I verify that all received the same secret: secret == secret_0 == ... == secret_n
I verify that all used the same session key: sesSk == sesSk_0 == ... == sesSk_n

Reminder

msg is shared over a blockchain so all receiver see the message or none does
receiverPks are known beforehand and thus are not included in msg but they could if necessary

If someone sees a weakness in this approach please share in the comments.


Is hashing data with dynamic keys still worth effort?

Your question is about breaking password hashing schemes (PHSs).

The usual way to break password hashes is by brute-forcing the input until you find a match between the resulting hash and the obtained hash.

Now there're some counter-measures to harden the schemes against various attacks that would allow you to break many passwords very fast, because most passwords are weak.

So let's build some formula to estimate the time you need to break a collection of given hashes $(h_1,h_2,...,h_n)$.

The first thing you do is think about how many values are actually possible for the passwords. Are they restricted to lower-case only? Do they actually use numbers? How long are they? This is expressed in the metric $NumberOfPossibilities$ which can usually be approximated by the size of the dictionary you use times the permutations you try. If you assume clever users you can computer $NumberOfPossibilities=NumberOfPossibleChars^{NumberOfChars}$.

Now we have to consider how much time do you need to actually try any of those passwords. Because if we'd consider 0-time we could instantly brute-force all passwords (which would be boring). This metric is called $TimePerTry$ and good programs use functions that require you to spend 100ms and more per try using PHSs like PBKDF2, scrypt, bcrypt or Argon2.

As you've expicilitly asked for different salt and pepper for each password you also need to consider each password by itself as they all have different salts. This is captured by $NumberOfPasswords$.

Finally you also asked for pepper, which is a value that is assumed to be need to be guessed by the attacker (and sometimes also by the defender). The amount of possible values for the pepper is captured by $NumberOfPossiblePeppers$.

This finally gives you the above mentioned formula $$NumberOfPossibilities \times TimePerTry \times NumberOfPasswords \times NumberOfPossiblePeppers = OverallTime$$ to calculate the overall time to break the scheme. The needed memory requirements (of own interest) and the parallelization can be calculated / inserted in a similar manner as the other values and I'll leave this as an exercise.


Efficient way of generating a random number of N (less than 64) bits with exactly M bits equal to one

I'd guess that you can simply split this into two problems:

create 64 - n random bits, call this R
shuffle n bits where m bits (at any location) are set to 1, call this P

Finally you can simply perform R | P (presuming big endian notation).

Shuffling lists of elements is an operation present in almost any language. If there is any inefficiency it would be in the shuffling algorithm (although Fisher-Yates is optimal, so you'd expect some form of that algorithm, possibly the inefficiency is getting values in a range...).


Generate a per data shared secret vs per session

A session key is used to share a symmetric key over asymmetric encryption. The reason behind this is that symmetric encryption algorithms are faster than asymmetric encryption algorithms, this is also called a hybrid cryptosystem, since it combines symmetric and asymmetric encryption.

The session key is generated randomly at the start of a session and is only valid for one session (hence the name "session key"). The use of session keys provides a feature called forward secrecy. In short, forward secrecy gives assurances that session keys will not be compromised even if the private key of the server is compromised.

Creating a new session key per message would (kind of) violate the use of hybrid cryptosystems, since you'd have to use asymmetric encryption all the time and not just for the first exchange. If your messages are of course very large it would make some sense to use this scheme but this is rarely the case.

It's in genral perfectly fine to use session keys instead of "per-message-session-keys".

  My question is what advantages this has over the persistent shared-secret per session?

It would theoretically provide forward secrecy per message instead of per session and there are indeed new implementations of such cryptographic schemes of what you're describing, like Efficient Ratcheting, which apparently provides session-per-message and is also very performant.


Where and how to store private keys in web applications for private messaging with web browsers

You may want to consider using the Web Cryptography API for client-side cryptography in the web browser.  Then, you can create a keypair using the webcrypto api, and store the CryptoKey object, containing the user's private key, with the .extractable property set to false, using Indexed DB storage.  This way the private key can only be used for decrypting and/or signing messages within the browser - but can not be read (even by client-side scripting in the browser).

For more info, see:

https://pomcor.com/2017/06/02/keys-in-browser/
https://www.w3.org/TR/WebCryptoAPI/
https://developer.mozilla.org/en-US/docs/Web/API/Web_Crypto_API
https://www.w3.org/TR/IndexedDB/
https://www.boxcryptor.com/en/blog/post/building-an-app-with-webcrypto-in-2016/
https://gist.github.com/saulshanabrook/b74984677bccd08b028b30d9968623f5
https://blog.engelke.com/2014/09/19/saving-cryptographic-keys-in-the-browser/


Difference between computationally and perfectly hiding (binding) properties

The words perfect and unbounded refer to basically the same concept*. If something has perfect security with respect to property X, then an adversary that is computationally unbounded can not violate property X. Computationally unbounded means that the adversary is allowed to run for an unspecified amount of time, in particular, $O(2^\kappa)$ for security parameter $\kappa$.

For example, we can ask if AES is a secure block cipher (permutation). What we could do is pick a random key $k\in\{0,1\}^\kappa$, encrypt the messages 1,2,3,4,... and give the results to the adversary.

If we bound the running time of the adversary to be $poly(\kappa)=O(\kappa^c)$ for some constant $c$, the answer is yes, we think AES is indistinguishable from a truly random permutation from $\{0,1\}^\kappa $ to $\{0,1\}^\kappa$.

However, if we allow the adversary to be computationally unbounded then there is a simple attack that can break AES. Say the adversary see $c_i=Enc(k,i)$ for $i=1,2,...,100$. Then with overwhelming probability, there is only one AES key $k$ that results in these $c_i$ values. As such, an unbounded adversary can simply try all $k'\in\{0,1\}^\kappa$ and check which results in the same ciphertexts $c_i$. Since there is likely only one such key the adversary will find it. This is a "brute force" type of adversary.

Note that if we instead used a one-time pad, then an unbounded adversary would not be able to break the encryption.

Now let us answer your question. Perfectly hiding means that an unbounded adversary can not learn any information about the value being committed to. One-time pad is perfectly hiding (but isn't a commitment scheme...). Hiding is a security property you care about when the adversary is the person who receives the committed values.

You can also have a computationally hiding commitment which means no adversary which has running time $poly(\kappa)$ can learn any information about the value by seeing the commitment (except with negligible probability).

Perfectly binding means that an unbounded adversary can not break a commitment and decommit it to more than one value. In other words, there must truly be only one value that the commitment can ever decommit to.

For computationally binding, then any adversary with running time $poly(\kappa)$ must have negligible probability of decommitting to more than one value.

Say our commitment scheme the classic "random oracle" approach where you commit to $x$ as $c=H(x || r)$ where $r\gets\{0,1\}^\kappa$ is a random value. Then this scheme is not perfectly binding. An unbounded adversary could pick some $x'$ and simply try $O(2^\kappa)$ other values of $r'$ until they get $c=H(x'||r')$. They could then "decommit" using either $(x||r)$ or $(x'||r')$. However, this scheme is computationally binding since finding such an $r'$ value requires $O(2^\kappa)$. Note, I'm ignoring some issues with the birthday bound.

There exist commitment schemes that have perfect bind or hiding but not both.

Edit*: as Maeher pointed out, there is a way for a commitment to be secure against an unbounded adversary while still not being perfectly secure. For this we introduce the statistical security parameter $\lambda$. A property X is said to have $\lambda$ bits of statistically security if when you run the (commitment) algorithm there is at most a $1/2^\lambda$ probability that property X does not hold (unconditionally).

For example, let us have some commitment scheme $C(x;r)$ which takes a value $x$ and a random tape $r$ as input. It just so happens that if $r=42$ the scheme completely falls apart. However, if we sample $r\gets \{0,1\}^\lambda$, then the probability that $r=42$ is $1/2^\lambda$ and this scheme can still be considered statistically secure. Importantly, the probability that the scheme fails to have the desired property is a function of the random tape $r$ and not of the running time of the adversary.


Is Bruce Schneier Applied Cryptography, Second ed. up to date?

The Applied Cryptography Second Edition goes back to 1996.  Although there is a 20th-anniversary edition, 2015, it is not updated as one thought. If you look for Schneier's style, you may look at the

Cryptography Engineering: Design Principles and Practical Applications, 2010

There is also another nice practical book by Jean-Philippe Aumasson

Serious Cryptography: A Practical Introduction to Modern Encryption, 2017

And, another one by David Wong as pointed by SAI Peregrinus

Real-World Cryptography, 2019

All three books are good for one to understand the cryptographic techniques at work in common tools, frameworks, and protocols. This will help to make excellent security choices for systems and applications. They are especially good for engineers and IT.


A replay attack simply means that an attacker who intercepts a valid message can re-send that message as many times as they want.  If there's nothing in the message that could not be legitimately repeated, then the recipient will have no reason not to accept it as a valid message.

In general, all encryption modes are potentially vulnerable to replay attacks, depending on how they're used.  The usual way to defend against such attacks is to include some kind of unique identifier and/or a timestamp in each message, so that the recipient can detect repeated messages.  The messages should then also be protected against modification using a message authentication code (MAC) or an authenticated encryption mode, so that the attacker cannot simply change the ID or timestamp.

As the claim you quoted from Wikipedia lacks any references that would let me look at the details of that particular attack (or even verify that it really took place), all I can do to answer your question is offer some guesses as to how ECB mode might be more vulnerable to replay attacks, or how other block cipher modes could be made more resistant to them:

First of all, one weakness particular to ECB mode is that you can take two messages, cut them apart at cipher block boundaries and join the halves together again to get a valid message combining parts of the two original messages.  Depending on how the messages are constructed, this might allow an attacker to e.g. glue the contents of an old message to the ID and timestamp from a new message, which obviously defeats their purpose.
Second, other block cipher modes, such as CBC, CFB, OFB and CTR, all require a unique initialization value (IV) or a "nonce" (essentially a unique identifier).  While preventing replay attacks is not the primary reason why these IVs / nonces are required, since they're there and since they need to be unique anyway, they can also be used to detect duplicate messages.

A potentially convenient feature is that, for many (but not all!) modes, even in the absence of a MAC, trying to modify the IV / nonce will turn the entire message into random garbage when it is decrypted.  This is particularly true of the OFB and CTR modes, which are otherwise very vulnerable to ciphertext modification.  (Of course, this is still not a good substitute for a MAC in other respects.)
Finally, in some applications, it might not be necessary to transmit the IV / nonce at all, since it may be inferred from some external information (such as the number of messages or blocks seen before, if messages are transmitted in strict sequence on a supposedly reliable channel).  In some cases, all messages might even be encrypted and transmitted as a single continuous stream, essentially just one long message.

This obviously makes replay attacks on non-ECB modes difficult or impossible, since repeating an old message would just lead to the recipient trying to decrypt it with the wrong IV / nonce.  However, ECB mode still remains vulnerable due to the property described above, namely that, as each block is encrypted independently and in the same way regardless of its position in the stream, an attacker can shuffle (and delete or duplicate) blocks in any manner without affecting their decryption.

Still, I should note that all of these attacks only apply in the absence of authentication.  Even ECB mode, if combined with a MAC and with unique message IDs to detect duplicates, would be secure against replay attacks.  Of course, the same goes for no encryption at all, but just unique message IDs and a MAC, but at least adding ECB mode encryption to the mix wouldn't make things any worse.


Does TLS 1.3 really send PSKs encrypted?

PSK is encrypted and normally sent after finished message.
If you inspect with wireshark, it appears as application data.
If you decrypt this message, you will find the session ticket including the psk id.

Servers can use psk id for stateless approach.
Servers can encrypt the resumption psk, issue time, and so on..
and use this encrypted message as a psk id.
When the client present psk id, server can fetch those informations to resume by decrypting it.


Entropy when iterating cryptographic hash functions

My estimate of the entropy after $i$ iterations is roughly $128- \lg i$ bits (as $i$ grows large).  I don't have a proof of this, but I'll lay out my rough back-of-the-envelope calculations below.

Here is the general problem:

  Problem 1. Let $F:\{0,1\}^n \to \{0,1\}^n$ be a random, i.e., chosen uniformly at random from the set of all functions with that signature.  Let $F^i$ denote the result of iterating $F$ $i$ times.  Let $X$ be uniformly distributed on $\{0,1\}^n$.  Let $F$ be known to the adversary, and $X$ be secret.  What is the entropy of $F^i(X)$?

I don't know how to solve that problem.  But here is a related problem that I do know how to solve.

  Problem 2. Let $F$ be as above.  Let $f_i$ denote the fraction of $n$-bit values that can appear at the output of $F^i$.  In other words, $f_i = |S_i|/2^n$, where we define $S_i$ to be the the set $S_i = \{F^i(x) : x\in \{0,1\}^n\}$ of all values that can appear as the output of $F$ iterated $i$ times.  What is the value of $f_i$, as a function of $i$?

Note that the answer to the problem 2 gives us a heuristic rough estimate at the answer to problem 1.  In particular, if we assume that $F^i(X)$ is approximately uniformly distributed on the set of all possible values (i.e., on $S_i$), then the entropy of $F^i(X)$ will be approximately $n - \lg f_i$.

And I can give you a reasonable solution to problem 2.  In particular, using a crude heuristic, $f_i$ approximately satisfies the following recurrence relation:

$$f_{i+1} \approx 1 - e^{-f_i},$$

where $f_0 = 1$.  The first few values of $f_i$ are $f_1=0.632$, $f_2=0.469$, $f_3=0.374$, $f_4=0.312$, $f_5=0.268$, $f_6=0.235$, $f_7=0.210$.  This recurrence relation does break down when $i$ gets extremely large, certainly by the time $i$ reaches $2^{n/2}$ or so, but this might not be a major concern for the values of $i$ you care about in practice.

Asymptotically, when $i$ gets large enough (but not so large that it gets close to $2^{n/2}$), I think that a crude approximation to $f_i$ is

$$f_i \sim 2/i.$$

Thus, for large (but not too large) $i$, this gives us a crude estimate for the entropy of $F^i(X)$ as

$$n-\lg f_i \approx n+1-\lg(i).$$

Plugging in $n=128$ in your particular problem, we get $129-\lg(i)$ as an estimate of the entropy after $i$ iterations.  This is within $\pm 1$ bit of my estimate at the top of the answer.

Incidentally, I have in my notes that a better approximation is $f_i \sim 2/(i+\log(i))$, but I don't know where I got this from, so it might be faulty.  If that approximation is accurate, then a better estimate of the entropy of $F^i(X)$ is $n+1-\lg(i+\log(i))$.

Again, as a reminder, all of these estimates are only intended to be used when $i$ gets large (but not crazy large).  When $i$ is small, you can calculate $f_i$ directly using the recurrence relation above.  And all of these estimates are just estimates, that rely upon several approximations, which may be pretty crude.

My thanks to @fgrieu for helpful comments on this answer.


How do I create a secure encryption scheme using addition?

Your idea of addition modulo 10000 is correct.  The correctness follows from the fact that $\mathbb{Z}_{10000} = \{0, 1, \dots, 9999\}$ equipped with addition modulo $10000$ forms a (finite) group.

Let $m \in \mathbb{Z}_{10000}$ denotes a PIN code.  Now choose a uniformly random element $r \in \mathbb{Z}_{10000}$ and define $c = m + r \bmod 10000$.  It is easily seen that $c$ is a uniformly random element in $\mathbb{Z}_{10000}$.


Well this depends on your key size.

But, in general:

A 1024-bit RSA key using OAEP padding can encrypt up to (1024/8) – 42 = 128 – 42 = 86 bytes.
A 2048-bit key can encrypt up to (2048/8) – 42 = 256 – 42 = 214 bytes.

And so on.
It is highly recommended you use at least a 2048-bit key.
If you need to encrypt more data just break it down into blocks of these sizes and send them independently (with different keys).

This however can be rather cumbersome (your server will need to have a few sets of keys) and it is best to simply send a 256-bit key (or any other size) for an authenticated encryption scheme and then use that scheme to transfer the rest of your data.


The Probability to Detect or Identify an Unknown Ciphertext

Is there an algorithm [...] that receives $\it C$  and $s$ as input and the output is the probability that  $\it C$ is encrypted by $s$?

No. Not unless the system $s$ in question is horribly broken.
The reason is simple: Most modern symmetric encryption schemes are built from primitives which are designed to heuristically achieve one of three security models: PRG, PRF or PRP.1
The fundamental property all three of these models have in common is the fact that when given a random input (in the appropriate input slot) then the output will be indistinguishable from a random string.
If you can break this security property for any of these primitives while knowing which you target this is usually worth a peer-reviewed academic paper. Example for Gimli.
Now the output of all non-horribly-broken schemes is indistinguishable from random which means they're also indistinguishable from each other and thus you can't deduce to which a ciphertext belongs. Except of course for horribly broken schemes where you can more clear say whether or not a ciphertext belongs to a scheme. Of course you wouldn't want to actually use any of those schemes but rather use them as examples of how not to design heuristically secure primitives.
Note that the above definitions still leave some wiggle-room as outlined in this Q&A. However this would mostly be length-based (e.g. a direct AES ciphertext is always 16 byte) or based on oracle access to the encryption scheme. Depending on the concrete setup in question this may or may not be applicable (e.g. if outputs are always truncated to 8 byte).

1: For encryption schemes the relevant security property is called IND\$-CPA but these three are the building blocks from which IND\$-CPA security is usually proven.


File using same key on XOR cipher. Using CBC

The "XOR cipher" described does not encrypt more than the first block, even if you do not reuse keys. The subsequent blocks can be "decrypted" by the attacker simply by undoing the XOR – there is no secret involved.

Decrypting the first block and finding the key does require more than one message. It is a case of the many-time pad and can be solved either using a known plaintext or by crib-dragging as described in the link above.


What does this paraphrase of the birthday problem mean?

$x_1 \oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $\oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.


TLS encryption with a self-signed PKI and Python’s asyncio module

Since I stumbled on this checking something else, a few minor points

A CA doesn't sign a CSR; it signs (issues) a cert that has some important data taken from the CSR but much data different.
The Subject names of the CA cert and all server and client certs it issues should be unique, and preferably mnemonic. The CA and client names don't need to be FQDNs, or domainnames at all, although if they are FQDNs that helps make them unique, and usually mnemonic. For a server, either the CommonName part of the Subject or the SubjectAlternativeName extension if used should -- and for many but not all clients must -- match the 'hostname' used by the client(s) to connect to the server. Normally this is the FQDN, but in test and intranet settings it might not; your example shows connecting to the loopback or 'localhost' address 127.0.0.1.
ECDH-AESGCM is not a ciphersuite or even a keyexchange in SSL/TLS; ECDH+AESGM is an OpenSSL shorthand for 8 different cipher suites -- only 2 of which work with an RSA key+cert, namely ECDHE-RSA-AES256-GCM-SHA384 and ECDHE-RSA-AES128-GCM-SHA256.
You don't visibly specify the temporary (ephemeral) ecdh parameters (curve) so you are presumably getting a default from Python; OpenSSL itself doesn't have a default, although 1.0.2 up has a nondefault option to automatically use the client preference.
Since you've chosen everything else pretty strong, you should make sure the ECDHE curve isn't unacceptably weak. I would hope it can be found in the Python source; if not, monitor an actual connection with Wireshark or similar to check.


Coppersmith's method, parameterized by $\epsilon$, finds all roots $\le \frac{1}{2} n^{\beta^2/\delta - \epsilon}$ to a polynomial $f(x)$ of degree $\delta$ modulo an unknown factor of $n$ of size $\ge n^\beta$. In your case, $\beta = 1$ and $\delta = \{4,5,6,7\}$.

Sage defaults $\epsilon = \beta/8$, which in your case would be $0.125$. However, $55555^{1^2/\{4,5,6,7\} - 0.125}$ is, respectively, $\{1.96, 1.13, 0.79, 0.61\}$. Only the first (almost) respects the bound. But if you tweak small_roots with an appropriate $\epsilon$, e.g., f.small_roots(epsilon=0.02), you should get more satisfactory answers.


Well, to answer your questions in order:

How big should $p$ be?  Well, it should be large enough to defend against the known attacks against it.  The most efficient attack is NFS; that has been used against numbers on the order of $2^{768}$ (a 232 digit number).  It would appear wise to pick a $p$ that's considerably bigger than that; around 1024 bits at a minimum, and more realistically at least 1536 bits.  Notes:

What was actually done is use NFS to factor a 232 digit number; NFS can be adjusted to perform discrete logs to bases of the same size without an undue increase of complexity.
Now, you said that the connections need be secure for only a few hours.  Now, NFS on numbers of that size is a large effort, almost certain to take longer than a few hours.  Now, if you really don't care if someone can retrieve the keys after the connection has ended, it might seem safe to use a smaller modulii; I would personally recommend against it.

In addition, there's another important point about $p$; $p-1$ should have a large prime factor $q$, and you should know what the factorization of $p-1$ is (so you can pick a value $g$ that is of the order $q$; that is, the smallest value $x>0$ where $g^x = 1 \mod p$ is $x=q$).  If you pick a random prime $p$, and a random generator $g$, well, you're probably secure, but you won't be certain (and you'll might leak a few bits of the private exponent if the order of your random $g$ happens to have some small factors).
How often should $p$ be changed; well, if you pick good values for $p$ and $g$, they don't need to be changed.
Is there a trade-off between dynamic generation and the size of p?  Well, you're far better off picking one large (and well chosen) prime p and g, and sticking to it.  From the NFS analysis, a 120 digit prime is of some questionable security; a 28-38 digit prime is far from adequate.

Now, as you might be able to tell from the above discussion, picking good $p$ and $g$ values is not straightforward (at least, if you don't understand the mathematics).  One good news is that people have already done the work, and have published good values.  See this for some well chosen $p$ and $g$ values; these were originally intended for use in the IKE protocol, but they can be used for other purposes as well.  I would personally recommend the 2048 bit value.


What's the GCM-SHA 256 of a TLS protocol?

I'll quickly decompose this cipher suite.

TLS - standard starting point
ECDHE - elliptic curve version of the Diffie-Hellman key-exchange using ephemeral keys (/exponents), other values for this position include RSA, DH and DHE
ECDSA - signature algorithm, used to sign the key-exchange parameters, omitted for RSA, other values include RSA
AES_128 - AES with a 128-bit key, AES_256 would denote a 256-bit key, with GCM, only AES, CAMELLIA and ARIA are possible, with AES being clearly the most popular and widely deployed choice.
GCM - Galois/Counter Mode, a modern authenticated encryption with associated data (AEAD) mode of operation for blockciphers with 128-bit blocks.
SHA256 - Secure Hash Algorithm (SHA)-256, the hash-function used as a basis for key-derivation from the master secret in the TLS protocol, as well as for authentication of the finished message. See Maarten's answer for more details.


Has it become easier to pre-compute tables after MD5 collisions?

Not really.
Finding distinct $m_1, m_2$ such that $H(m_1) = H(m_2)$ is a different problem than finding $m_1, d$ such that $H(m_1) = d$. If the first problem is hard it's called collision resistance, if the second problem is hard it's called preimage resistance.
MD5's collision resistance is practically broken - it's quite easy to generate a pair of $m_1, m_2$ that produce the same digest in a few seconds on a consumer CPU. However this result is not useful for creating pre-computed lookup tables at all, the contrary is true - you want as many different digests in such table, rather than collisions.
MD5's preimage resistance is theoretically broken (with a computational complexity $2^{123.4}$ according to Wikipedia), but that's not a practical result. So for example if I know that I still need a digest with value 0xFFFFA3BFFFFFFFFFFFFFFFFFFFFFFFFF in the table there is still no easy way to find an input for that digest.


Is it safe to publicly announce the prime number in Shamir three-pass protocol

But, is it safe to publish the prime number publicly?

It has to be. Otherwise the other party would not have access to it and could not participate in the protocol. It is called a "public prime" and not a "secret prime" for that reason.

  So say, I want to use a prime number p for anyone that wants to communicate with me using Shamir's Three Pass Protocol.

If this isn't a hypothetical question and you actually plan to use this for securing real communications, you will want to consider learning about other more standard techniques such as Diffie-Hellman key agreement and hybrid cryptosystems. There are much more efficient and better studied methods for creating secured communication channels than the three pass protocol. Also, you'll want to find a pre-existing software library that already implements the relevant algorithms.


Are there any issues to doing 2 rounds of AES-128? How is the security compared to AES-256?

Double encryption with 128-bit AES and two different keys does not give 256-bit security. In particular, a classic Meet-in-the-Middle attack applies, with expected cost $2^{128}$ encryptions and $2^{127}$ decryptions. As is, the attack requires ridiculously large amounts of memory, but improvements (using cycle finding with distinguished points) exist that greatly reduce memory requirement. See section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1).
I find it likely that a system has weaker points than AES-128's key size; systems may be vulnerable against key compromise or side-channel attacks for example.


Why do digital signatures use a hash algorithm instead of a checksum?

A digital signature can only sign a relatively small amount of information, which is why the digest is signed instead of the original message. Because of this limitation, the digest must be a faithful representation of the complete message. A cryptographically-secure hash is require to resist collision attacks, second preimage attacks, and preimage attacks, all of which can invalidate the guarantees that people expect from a digital signature. In other words, if one signature is valid for two distinct messages, the signature is useless. A cryptographically-secure hash prevents this.

Also note that digital signatures are not simply encrypted digests. This is a simplified explanation which is common, but technically incorrect. This answer describes signatures for RSA.


How would I convert an arithmetic circuit into a system of bilinear equations?

I don't know if this is exactly what you mean, but you can always consider each one of the wire values in the circuit as variables, and then create an equation per gate which represents the relation that the corresponding wires must have.

For example, if the wires labeled as variables $x$ and $y$ are the inputs of a multiplication gate, whose output is $z$, then you would obtain the equation $x\cdot y - z = 0$. Similarly for addition gates. Overall, you would get a system of $N$ (non-homogeneous) quadratic equations in $n$ variables, where $N$ is the numbers of gates and $n$ is the number of wires.


Secure MultiParty Computation with secret inputs for secret outputs

Yes, that is possible -- that's exactly the problem that secure multiparty computation solves.  You should start by reading standard references on secure multiparty computation.

You might enjoy the following paper, and follow-on work:

Secure Multiparty Computations on Bitcoin,  Marcin Andrychowicz and Stefan Dziembowski and Daniel Malinowski and Łukasz Mazurek, IEEE Security & Privacy 2014.


Shamir's Secret Sharing vs. Asmuth-Bloom scheme

There is one theoretical difference between Shamir's scheme and Asmuth and Bloom's scheme.

Shamir can be done in an informationally secure manner; specifically, if the nonconstant polynomial coefficients were chosen in a random manner (that is, from a uniform probability distribution that's uncorrelated to anything else the attacker can see), then someone with a number of shares that's less than the threshold gains no information about the shared secret.  This is because, for any potential value of the shared secret, there is the same number of possible secret coefficients that is consistent with that secret value - if we assume that those coefficients were chosen uniformly, the attacker has no criteria to say that one set of coefficients is any more likely that the other.

In contrast, Asmuth and Bloom's scheme does leak some probabilistitic information.  Now, any particular value of the shared secret is possible; however different values of the shared secret have different numbers of possible secret value $\alpha$.  Assuming that the attacker knows the probability distribution that $\alpha$ was drawn from, he can then assign different probabilities to the values of the shared secret, should he choose to.

As Asmuth and Bloom's scheme does leak some probabilistic information, while Shamir's does not, well, that seems like a good reason to prefer Shamir's (especially since, as Louis says, Shamir's is actually easier from a practical standpoint)


Usually you'd use one hash per file yes, but often torrents consist of multiple files. So you'd have a hash per file and possibly a top level hash to make sure that all the files are present. This way you can validate each file after it is downloaded; downloading and hashing can be performed in any order and in parallel - e.g. from within their own threads.

In principle you could also split the file in sections and hash those separately / in parallel. But with the speed of most hash algorithms this doesn't make much sense. And for integrity you're probably better off using e.g. PAR2 which provides error correction on top of error detection.

As for the authenticity: either the Merkle tree can be loaded from a secure location or the root may be signed, to name two common methods. So yes, you can use a Merkle tree to authenticate data, but you must be able to trust the tree itself first.


Post-quantum asymmetric encryption algorithms

The NIST post-quantum schemes mainly consist of KEMs and signature schemes due to the fact that quantum computers don't break all existing cryptography.
As per Daniel Bernstein :

...there is no justification for the leap
from “quantum computers destroy RSA and DSA and ECDSA” to “quantum
computers destroy cryptography.”

As such, there is less desire to replace AES than there is to replace RSA/DSA/ECDSA, or whatever is broken by quantum computers.
Meanwhile DJB's tone suggests he doesn't think it's a priority:

Evidently these unnamed “experts” believe—and Magiq would like you to
believe—that quantum computers will break AES, and dozens of other wellknown secret-key ciphers, and Merkle’s hash-tree signature system, and
McEliece’s hidden-Goppa-code encryption system, and Patarin’s HFEv− signature system, and NTRU, and all of the other cryptographic systems discussed in this book. Time will tell whether this belief was justified!


Apply HKDF after Diffie-Hellman Key Exchange

From my understanding, I only need one key for CHACHA20 or AES-256-GCM. Is it a good idea if I only generate one key by HKDF?

In one direction yes, as the MAC and encryption part only requires one key for ChaCha20/Poly1305 and AES-GCM. If you need multiple key parts you can either increase output size and split the result, or you can call HKDF twice using different labels (in the Info component).
Note that you may want to explicitly verify that you generated the same master key on both sides, preferably that should be performed with a separate derived key (and, e.g., HMAC).

One more thing, how can I generate a good salt for this case?

A cryptographic 128 bit salt is fine, as your code seems to be doing at this time.


By Theorem 3 on page 15 of this paper,
no secure-with-abort protocol for equality of long strings can be within 1/5 of fair.

If there is a protocol for equality on a domain of size at least 3 which is

secure against honest-but-curious adversaries, then oblivious transfer protocols exist.

If oblivious transfer protocols exist, then there are protocols for equality which give $P_1$

security-and-guaranteed-output-delivery and have $P_2\hspace{-0.03 in}$'s possible outputs be $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}\perp,\hspace{-0.04 in}=\hspace{-0.02 in}\}$

and give $P_2$ the security that consists of indistinguishability from the ideal functionality

for which [if the inputs are equal then $P_2$ outputs the simulator's choice of $=$ or $\perp]$

and [if the inputs are not equal then the simulator chooses between $[P_2$ outputs $\neq]$

and $[P_2$ has a small chance of outputting $\perp$ and otherwise outputs $\neq_{\hspace{-0.03 in}\perp}\hspace{.02 in}]]$.

Such a protocol can be constructed as follows:

Start with Section 3.2, even though the domains are both super-polynomially large.

Look at $\operatorname{Sharegen}_r$, which is the box at the top of page 9.

If $\: x=y \:$ then set $\: \hspace{.03 in}j = i^* \:$, $\:$ else choose $\hspace{.03 in}j$ uniformly at random from $\: \{1,...,r\}\;$.

Ignore for loop immediately after $\operatorname{Sharegen}_r\hspace{-0.04 in}$'s choice of $i^*\hspace{-0.03 in}$.

Instead, this phase is to set $a_{i^*}$ and $b_j$ to the relation ($=$ or $\neq$) that holds between $x$ and $y$,

give $i^*$ and a share of $a_{i^*}$ to $P_1$, give $\hspace{.03 in}j$ and a share of $b_j$ to $P_2$, and give each of them $r$

real-or-simulated shares for the $a$s and $b\hspace{.02 in}$s in order to hide $i^*$ and $\hspace{.03 in}j$ from $P_2$ and $P_1$ respectively.

Note that either the integer prefixes must have the same length as each other

for the same party, or a stateful MAC must be used instead of concatenation.

Now, look at the box at the top of the next page, but ignore its step 3.

Just like that paper mentions on page 10 in the paragraph that starts with "Proof", the rest

of this paragraph will ignore the MACs and the fact that the parties are to be checking them.

If $P_1$ gets $P_2\hspace{-0.03 in}$'s share of $a_{i^*}$ and $a_{i^*}$ is $=$ then $P_1$ [outputs $=$, sends the next message,

and then halts]. $\:$ Otherwise, $P_1$ will output $\neq$ when $P_2$ aborts or the for loop reaches its end.

If $P_2$ gets $P_1\hspace{-0.04 in}$'s share of $b_j$ and $b_j$ is $=$ then $P_2$ outputs $=$ and halts. $\:$ If the for loop reaches its end

and $b_j$ is $\neq$ then $P_2$ outputs $\neq$. $\:$ If $P_2$ gets the simulated-share for $b_{j-1}$ but does not get

$P_1\hspace{-0.04 in}$'s share of $b_j$ then $P_2$ outputs $\perp$. $\:$ If $P_1$ aborts at any other time then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}$.

Note that for an adversary, acting as either party, the ability to abort and get significant information about whether or not the other party got $\neq$ for [the $a$ or $b$ value which the honest party would learn if both parties were honest] would let the adversary significantly bias the other party's output.

(i.e., significantly beyond what can already be done in the ideal model)

.

For that construction, "a small chance" means "probability $1/r$".

Since it gives $P_1$ gets security-with-guaranteed-output-delivery, which is even stronger than security-with-fairness, the above protocol runs into the limits imposed by the impossibility proof. $\:$ On one hand, just ignoring the subscript on $\neq_{\hspace{-0.03 in}\perp}$ gives $P_2$ security-with-abort,

so doing that must come at the cost of significant unfairness.

On the other hand, doing that and replacing $\perp$ with $=$ gives $P_2$ approximate fairness,

so doing that must come at the cost of security-with-abort.

However, time-lock puzzles are enough to get around that, yielding a protocol such that

$P_1\hspace{-0.04 in}$'s possible outputs are $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.03 in}=_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}=\hspace{-0.02 in}\} \:$ and $P_2\hspace{-0.03 in}$'s possible outputs are $\: \{\hspace{-0.02 in}\neq,\hspace{-0.03 in}\neq_{\hspace{-0.03 in}\perp},\hspace{-0.03 in}\perp,\hspace{-0.03 in}=_{\hspace{-0.03 in}\perp},\hspace{-0.04 in}=\hspace{-0.02 in}\} \;$.

$P_1$ still gets security-and-guaranteed-output-delivery,

but that delivery will take time $T$ when $P_2$ aborts.

$P_2\hspace{-0.03 in}$'s standard-model security (i.e., what applies even if $P_1$ can quickly break the puzzles)

is like it was for the previous protocol, but if the inputs are equal then the simulator

can alternatively choose $=_{\hspace{-0.03 in}\perp}$. $\:$ If the puzzles are secure against $P_1$, then $P_1$ aborting

or not is statistically close to independent of $P_2\hspace{-0.03 in}$’s input and for equal inputs, the probability

of $P_2$ outputting $\perp$ is statistically close to $1/r$ times the probability of $P_1$ aborting.

.

Time-lock puzzles can be brought in to do that as follows:

The initialization phase will produce $\:a_1,...,a_r\:$,$\:$ rather than just $a_{i^*}$. $\;\;\;$ If the inputs are equal then for all elements $i$ of $\:\{i^*,...,r\}\:$,$\:$ $a_i$ will be $=$. $\;\;\;$ Other than that, the $a$s will all be $\neq$.

$P_1$ will get a share of each $a$, but $i^*$ is to stay hidden from $P_1$. $\:$ $P_2$ will get time-lock puzzles that encode shares of the $a$s, rather than real-or-simulated shares of not-necessarily-existing $a$s. $\:$ (Those shares will not need to be at-all hidden from $P_2$, which may make things easier

than they'd otherwise be.) $\:$ An $(r\hspace{-0.03 in}+\hspace{-0.06 in}1)\hspace{-0.02 in}$-time MAC will be used for messages from $P_2$,

since in addition to the puzzles (rather than the encoded-shares directly)

being tagged, $P_2\hspace{-0.03 in}$'s share of $b_j$ will be authenticated with $\: i = 0 \;$.

After the for loop reaches its end, $P_2$ will send that share and its MAC-tag to $P_1$.

Just like in my previous description, the rest of this description will ignore the MACs.

If $P_2$ aborts before sending the puzzle that encodes its share of $a_1$, then $P_1$ outputs $\neq$.

If $P_2$ aborts at any later time, then $P_1$ sets $c$ to be the solution to the most recent puzzle

and outputs $c_{\hspace{-0.03 in}\perp}$. $\:$ If $P_2$ sends its final message then $P_1$ and $P_2$ both output $b_j$.

If $P_2$ does not get $P_1\hspace{-0.04 in}$'s simulated-share of $b_{j-\hspace{-0.02 in}1}$ then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}$.

If $P_2$ gets that but does not get $P_1\hspace{-0.04 in}$'s share of $b_j$ then $P_2$ outputs $\perp$. $\:$ If $P_2$ gets $P_1\hspace{-0.04 in}$'s share of $b_j$

but $P_1$ aborts before sending its final message, then $P_2$ sets $c$ to be $b_j$ and outputs $c_{\hspace{-0.03 in}\perp}$.

.

That sort of idea can in fact be used can be used for securely computing arbitrary functions,

by modifying how I was describing their use for equality so that [for $i$ from $1$ to $i^*\hspace{-0.06 in}-\hspace{-0.06 in}1$,

$a_i$ will be $\perp$ rather than $\neq]$ and [the rest of the $a$s will be set to the function's output] and

replacing ["then $P_1$ outputs $\neq$","outputs $c_{\hspace{-0.03 in}\perp}\hspace{-0.02 in}$","then $P_2$ outputs $\neq_{\hspace{-0.03 in}\perp}\hspace{-0.02 in}$"] with ["then $P_1$ outputs $\perp\hspace{-0.03 in}$",

"if $c$ is $\perp$ then that party outputs $\perp$ else that party outputs $c_{\hspace{-0.03 in}\perp}\hspace{-0.03 in}$","then $P_2$ outputs $\perp \hspace{-0.03 in}$"] respectively.

(That is quite different from the traditional way of using time-lock puzzles for something

resembling fairness, which is to decrease $T$ geometrically between pairs of messages.)

However, protocols using time-lock puzzles as I described

for computing equality has the advantage of offering something non-trivial

in the way of fairness to $P_2$ even if $P_1$ can quickly break the puzzles.

(There was a non-proof after this sentence, but it was just for my conversation

with Yehuda Lindell, rather than being related to the rest of this answer.)


Is it possible to decrypt the 2nd byte of AES-256-CFB-8 ciphertext without decrypting the 1st byte?

Yes, you can do this.  If you want to know how to do it (as opposed to just blindly copying a code snipped written by someone else and hoping it'll work), you'll need to understand a little bit about how CFB mode encryption works.

First of all, CFB is a block cipher mode of operation.  That is, it's a recipe for taking a block cipher like AES, which can only encrypt 16-byte blocks into other 16-byte blocks, and using it to securely encrypt (and decrypt) arbitrary streams of bytes.

Why do we even need a "mode of operation" like CFB?  Why can't we just split the message into 16-byte blocks and encrypt each of them with AES?  Well, yes we can, but such an encryption scheme, known as "ECB mode", turns out to not be as secure as we'd like.  So, instead, we use slightly more complicated schemes like CBC, CFB, OFB or CTR, all of which can be proven to provide full semantic security when used properly.*

This causes a bit of terminology confusion sometimes.  When we speak of "encrypting something with AES", in the context of describing a mode of operation, we mean using the raw AES block cipher to transform a 16-byte input block into a 16-byte output.  (Your crypto library might have a separate API for this, or it might simply expose it as "ECB mode".)  However, the words "encrypt" and "decrypt" are also used for the entire process of applying e.g. CFB mode encryption to the entire message.  This gets particularly confusing when you realize that CFB decryption still uses AES encryption!

Second, there are actually several different CFB modes!  The most common (and efficient) one, which is illustrated in the image included in several earlier answers, is called the "full-block" CFB mode, and works like this (assuming we're using AES as the block cipher):

To encrypt the first 16 bytes of the message, take the 16-byte IV, feed it into AES, and XOR the resulting 16-byte block with the first 16 message bytes to produce the first 16 bytes of ciphertext.  (If the message is shorter than 16 bytes, just truncate the AES output to match its length.)
To encrypt the next 16 bytes of the message, take the 16-byte ciphertext (i.e. the AES output XORed with the message) that we just produced in the previous step, feed it into AES, and XOR it with the 16 message bytes that we want to encrypt to produce another 16 bytes of ciphertext.
Repeat the same process for every subsequent block of 16 message bytes, every time using the previous 16 bytes of ciphertext as the AES input, until you reach the end of the message.  Again, if the last message block is less than the full 16 bytes long, truncate the AES output to match its length.

However, what you seem to be using, based on your code, is the variant of CFB mode that encrypts a single byte at a time, sometimes called CFB-8 (because a byte has 8 bits; full-block CFB using AES would be CFB-128, and there's even a CFB-1 variant that encrypts a single bit at a time).

This CFB-8 mode works exactly the same as the full-block CFB mode, except that you always truncate the AES output to just one byte and XOR it with just one byte of the message to produce a single byte of ciphertext.  (You still always take the previous 16 bytes of ciphertext, prefixed with the IV for the first 16 message bytes, as the AES input.)  That is to say, CFB-8 encryption works like this:

To encrypt the first byte of the message, take the 16-byte IV, feed it into AES, and XOR the first byte of the AES output with the first byte of the message to produce the first byte of ciphertext.  (The remaining 15 bytes of AES output are just thrown away!)
To encrypt the second byte of the message, take the last 15 bytes of the IV plus the first byte of ciphertext that we just produced and, just like before, feed them into AES, take the first byte of the output, and XOR it with the second message byte to produce the second ciphertext byte.
To encrypt the third byte of the message, take the last 14 bytes of the IV, plus the two bytes of ciphertext that we've just produced, feed them into AES and XOR the first byte of the output with the third message byte, just like above, etc.

(Why would you want to use this CFB-8 mode, given that it's about 16 times slower than full-block CFB?  Well, unless you really want to be able to start decrypting the ciphertext at any byte, you really don't — that's the only real advantage it offers over full-block CFB mode.)

In both cases, CFB decryption is just the inverse of this process: to decrypt a (16-byte or 1-byte, depending on the CFB variant used) block of ciphertext, you take the previous 16 bytes of ciphertext (again, with the IV treated as a prefix of the ciphertext for the first 16 bytes), feed them through AES (in the same direction as for encryption!), and XOR the result with the following block (or byte) of ciphertext that you want to decrypt.

Now, while CFB encryption needs to be done sequentially from the start of the message, because you need to encrypt the previous block / byte of the message in order to know the 16 bytes of ciphertext needed for encrypting the next block / byte, CFB decryption can be done in any order (or even in parallel!) because the entire ciphertext is already known.

It turns out that you can, in fact, do this even if your crypto library doesn't give you access to the raw AES block cipher.  The crucial observation here is that, for CFB mode, the IV is really just treated as prefix of the ciphertext that is used to get the encryption / decryption process started.

Thus, to decrypt a CFB ciphertext starting from the $n$-th block / byte, you just take the previous 16 bytes of the ciphertext (prefixed with the actual IV) and pass them to your crypto library as the IV for CFB decryption.

For example, using your CFB-8 "pseudocode" as a basis, you could decrypt a message starting from the $n$-th byte like this:

// key setup
char *key = "whatever";
AES_KEY aes_key;
AES_set_encrypt_key(key, 256, &aes_key);

// encrypt message using CFB-8, prepend IV to ciphertext
unsigned char *in_plain = "helloworld";
const int enc_len = 10;
unsigned char iv_enc[AES_BLOCK_SIZE];
RAND_bytes(iv_enc, AES_BLOCK_SIZE);
unsigned char ciphertext[AES_BLOCK_SIZE + enc_len];
memcpy(ciphertext, iv_enc, AES_BLOCK_SIZE);
unsigned char *out_cipher = ciphertext + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_plain, out_cipher, enc_len, &aes_key, iv_enc, &num, AES_ENCRYPT);

// decrypt dec_len message bytes starting from byte dec_start of ciphertext
const int dec_start = 1, dec_len = 1;
unsigned char out_plain[dec_len];
unsigned char iv_dec[AES_BLOCK_SIZE];
memcpy(iv_dec, ciphertext + dec_start, AES_BLOCK_SIZE);
unsigned char *in_cipher = ciphertext + dec_start + AES_BLOCK_SIZE;
AES_cfb8_encrypt(in_cipher, out_plain, dec_len, &aes_key, iv_dec, &num, AES_DECRYPT);

Note that I'm using a single ciphertext buffer to store both the IV and the ciphertext, and just passing a pointer into that buffer to the encryption / decryption API.  (I do make a copy of the IV, since apparently the OpenSSL API this is based on modifies the IV string in place.)  In a real application, this ciphertext buffer is what you'd send to the recipient after encryption.  For CFB mode, this is a natural arrangement, and allows the IV for decryption to be obtained simply by taking a pointer to AES_BLOCK_SIZE = 16 bytes before the start of the ciphertext portion we wish to decrypt.

Essentially the same code should work for full-block CFB, too, except that you need to ensure that the starting offset dec_start is an integer multiple of the AES block size, so that decryption starts correctly at a block boundary.

*) Basically, semantic security means that an eavesdropper who can see all your encrypted messages (but cannot modify them or feed you fake messages, and does not know the encryption key) cannot learn anything about the plaintext messages except their length.  Note that none of the "classical" encryption modes, including CFB, offer sufficient protection against active attackers who may try to modify or forge messages; for that you need an authenticated encryption mode.


Security impact of signing small data using RSA

If you are using a secure signature algorithm, padding and all, then it must be secure for messages of any length. So in that sense you are good.

However, in many protocols your messages must include something to prevent replay attacks, like an incrementing counter, in which case you shouldn't be signing just a single number if the messages are meant to say anything at all.


How does the key size per data bit influence the security?

Quite apart from the correction that Reid made (it takes $2^{127}$ attempts to achieve a probability of 50% of finding the right key; with $2^{64}$ attempts, the probability of success is $2^{-64}$), with AES, there is no known way to take advantage of known (or even chosen) plaintext to speed up any brute force search; even with $2^{64}$ chosen plaintext/ciphertext pairs, the best known attack is to pick one pair, and apply a brute force search on that pair.


How to encrypt many files with AES-GCM, without running the key derivation function each time?

One serious about password-based cryptography must not walk away from KDF_PBKDF2, but run to Argon2 (or scrypt if it's more readily available)! Bitcoin mining has (in 2020) shown that dedicated ASICs performing SHA-256 at high rate (220 TH/s) and efficiency (15 pJ/H) can become commercially available for few thousand US dollars. This makes it untenable to rely on PBKDF2-HMAC run on standard hardware for stretching of user-chosen passwords in high-security applications.
The method proposed has one characteristic: salt is common to several files if, and for wide random salt only if, they have been encrypted together. This is both a possibly unwanted information leak, and a way to solve the drawback mentioned: the password-stretching code used in decryption can maintain a RAM cache of (salt, key) pairs.
I'd consider replacing AES-GCM with AES-GCM-SIV, for peace of mind in case of stuttering of the RNG, but keeping in mind that two passes are needed over the data.
As much as I advocate trimming the last byte when it counts (e.g. when the data lies on a barcode or goes thru a slow or/and battery-depleting communication medium), I won't recommend saving on salt and nonce size in file encryption like we're in the 1980s.


What is the proper usage of GCM nonce in TLS1.2?

TLS has different keys for the two different directions.  That is, the server-to-client connection is encrypted with one set of keys, and the client-to-server connection is encrypted with another.  Both sets of keys are derived at the same time, however they are distinct.

Because the keys are distinct, using the same nonce isn't an issue.

Technical point that doesn't actually change the answer: actually, what's sent over the wire is actually the latter 64 bits of the nonce; 32 bits of the nonce are also derived when we generate the keys.  Of course, the same 32 bits might be picked for both directions.  On the other hand, even if they do, as above, that collision would be harmless (unless the keys also happen to collide)


uuidgen has consistent 13th digit and it's 4

You can find a full explanation in the Wikipedia article on UUID.

UUID's come in different versions. The 4 you highlighted indicates version 4 was used where the UUID is created by generating a random number. Other versions use for example the date-time and MAC address of your computer.

When you look further at the first character of the next block you will see it is not very random either: it shows only the characters 8, 9, A and B . This is because the two most significant bits are 01 for the variant of this UUID version.


Personally I believe that it could be done properly and address all (or at least some) of the concerns.

Remember what the WebCryptoAPI is:

  This specification describes a JavaScript API for performing basic cryptographic operations in web applications, such as hashing, signature generation and verification, and encryption and decryption. Additionally, it describes an API for applications to generate and/or manage the keying material necessary to perform these operations. Key storage is provided for both temporary and permanent keys. Access to keying material is contingent on the same origin policy. Uses for this API range from user or service authentication, document or code signing, and the confidentiality and integrity of communications.

A lot of the concerns are related to how the code is distributed, hijacking the javascript/security of javascript engine, etc.

Well, for this particular standard, the code is distributed with the browser, not over the http socket. So at least the crypto algorithms should be safe. Furthermore, that would make it difficult for someone to say override the crypto code with attacker supplied code as browser checks can be added.

Hijacking of the content delivered by the HTTP server (say through XSS) to disable crypto or steal crypto keys is a concern. But, it is just a symptom of a larger problem.

It definitely attempts to solve some of the other problems such as key generation, key storage, etc.

A lot of this will depend on actual implementations, however.


Creating SHA256 constant values on the fly without memory usuage

If you look at the specification to understand how those constants were chosen, you'll realize you waste more memory generating them "on the fly".
SHA-256 compression function key schedule constants are calculated as the fraction part of cubic-root of the first 64 prime numbers. You said you coud delete them after use (in the comment), but wouldn't that overlap with DRAM allocated for message buffer or something else? If you need a memory-compact implementation, this would be an anti-optimization.
If you desire a hash function without large memory footprint, you could consider SHA-3/Keccak, it too has some constants, but generating them "on the fly" requires only few additional registers to hold values from a LSFR.


What is the difference in exchanging the Enigma rotors in their slots?

They may look equal but in fact each rotor defines a different letter substitution. A letter substitution is a function that converts each of the 26 letters into another letter. For example $a\rightarrow z$, $b\rightarrow x$, $c\rightarrow y$ and so on. There are many ways this can done. Therefore, exchanging the rotors changes how each letter is substituted in the cipher.

Furthermore, each letter to be encrypted actually goes through all three rotors one after the other, being substituted each time. Also the rotors rotate so that this substitution function changes every letter. This rotation shifts the letter substitution so if in the initial position $a\rightarrow s$ then one rotation along would substitute $b\rightarrow t$ since $b$ and $t$ are the next letters from $a$ and $s$ respectively.

There is other stuff such as reflectors and custom wiring but that is the basics.


Correctness of RSA variation using CRT to decrypt?

What you have won't necessarily give you the original value of $x$; it'll give you an $x$ where $x^3 \equiv x_{orig}^3$, however, it isn't necessarily the original value.

To demonstrate this, let us take as an example $p=43$ and $q=61$.

Consider $x_{orig}=5$.  Then, $y=125$, and $x_p = y^5 \bmod 43 = 8$ and $x_q = y^7 \bmod 61 = 52$; this gives us a $CRT(8, 52) = 1943$, which is not the original $x$.  Now, $1943^3 \bmod (43*61) = 125$, and so it also does give the ciphertext, it's just not the same plaintext that you started out with.


Mutating a SHA-2 input would allow us to have multiple hashes for a single input, would this increase SHA-2's security?

Arbitrary mutation protocol is equivalent to a random permutation (i.e., a random invertible function); so running through $M$ is basically equivalent to encrypting with some random key $K$. You don't need something so complex as a permutation - you could be adding on a fixed prefix, suffix, etc, just as well.

From a hashing perspective, there's no real reason to do this.
Your chances are already $2^{-256}$ anyway for a collision between two inputs (more inputs increase the chance via birthday).  For each change you do and output you're basically increasing the bit-length, so $2^{-512}$, $2^{-768}$, etc. (so you are increasing security). But you could just as well just use SHA-512 if 256 bits isn't enough for you (and it generally runs faster on modern processors)


There is one way of doing this using RSA. So if you have n1 = p1 * q1 and also n2 = p2 * q2 and each of them have a key pair pub1, priv1 and pub2, priv2.

Then if you use the Integer group n3 and n3 = n2 * n1 then for every element in the pair (element from Integer group n2; element from Integer group n1) there would be a map to (element from Integer group n3).

This might sound confusing but then something cool happens. Imagine that Bob has a key pair in n1, pub1, priv1 and that Bobby has a key pair in n2, pub2, priv2.

So if you cipher m1 with pub1(using modulo n1) and m2 with pub2(using modulo n2) and then use the map that I said before so that you get an element from n3. (encWithPub1(m1), encWithPub2(m2)) = (cipheredMessages) and cipheredMessages belongs to the Integer Group of n3.

Then if you send this cipheredMessages message to Bob and Bobby. Bob will decipher with priv1 (modulo n1) and get m1. Bobby would decipher with priv2 (modulo n2) and get m2. So by just sending one ciphertext both Bob and Bobby got their respective clear text.

Sorry if this is confusing but i don't know how to write formulas in here...


What is the difference between Columnar and Grid Transposition?

Both the columnar and and the grid transposition ciphers are certain types of transposition ciphers. Both ciphers normally require a key for enciphering / deciphering. However, you can say that these ciphers, in their simple form can be easily cracked by brute-force.

Columnar Transposition

In a columnar transposition cipher you write the message out in rows of a fixed length. Then you read out column by column, where the columns are chosen in a scrambled order. Normally the key defines the width of the rows and moreover the "scramble" part in column permutation. Take the ciphertext "Thisisaciphertextthatneedstobecracked" and the key "ZEBRAS" for example. "ZEBRAS" defines the permutation in regard to the alphabetical order of the letters, which is "6 3 2 4 1 5" here.

1 2 3 4 5 6                              6 3 2 4 1 5
T h i s i s                              T h i s i s
a c i p h e                              a c i p h e
r t e x t t  --> using key "ZEBRAS" -->  r t e x t t
h a t n e e                              h a t n e e
d s t o b e                              d s t o b e
c r a c k e                              c r a c k e
d X X X X X                              d X X X X X

You get your ciphertext by reading your columns with your new indices, i.e. "ihtebkx iiettax hctasrx spxnocx seteeex Tarhdcd".

Grid Transposition

The grid transposition cipher is similar to the columnar transposition cipher. The difference here is that you introduce row indices in addition to column indices. You first create a grid that can fit all of the letters of your ciphertext and again, fill the extra spaces with X. Take the ciphertext "hiwhatsup" and the key "BAZYFG" for example. Again the key defines the columnar permutation, but also the row permutation. "BAZ" is for the columns and would map to "2 1 3" and "YFG" is for the rows and would map to "3 1 2".

  1 2 3                                   2 1 3
1 b e s                                 3 e d s
2 t c o     --> using key "BAZYFG" -->  1 e b s
3 d e s                                 2 c t o


How would one crack a weak but unknown encryption protocol?

It depends on what information you have. If all you have is that one ciphertext and no way of acquiring more, there's not much you can do.

If you have multiple ciphertexts, you can try to observe any patterns in them. If you have the corresponding plaintexts, you can really start to make some useful observations. If you have some plaintext, ciphertext pairs, you can try to find patterns in the data.

An even stronger attack would having access to the encryption oracle. That is, being able to encrypt plaintexts of your choosing. Here you could try special encryption strings to see if they leak any information about the algorithm. You can try things like "a", "aaaaaaa", or string of null bytes and see what information you can extract about the algorithm.

If the encryption algorithm is insecure, your goal should be to figure out what the algorithm does. Once you know how the algorithm works, you can presumably figure out a way to break ciphertexts or get the key.


In a shamir secret sharing scheme, why can't the secret be a middle coefficient and only the first or the last?

Here's one way to approach the question: if we have a $(n, t)$ Shamir secret sharing system, and we have $t-1$ shares $(x_0, y_0), (x_1, y_1), …, (x_{t-2}, y_{t-2})$, then all we can deduce that the secret polynomial is of the form:

$$P(x) + c \prod_{i=0}^{t-2}(x - x_i)$$

where $P(x)$ is a computable polynomial (exactly what that polynomial is depends on the known shares), and $c$ is an unknown constant (and which we have no information about).

So, the question is: given that the polynomial is of this form (for some $c$), and the secret we want is the $j$th coefficient, can we deduce the coefficient that's the secret we're interested in?

We know the $j$th coefficient for $P(x)$, and so this reduces to whether we know the $j$th coefficient of $c \prod_{i=0}^{t-2}(x - x_i)$; we can if and only if the $j$th coefficient of the polynomial $\prod_{i=0}^{t-2}(x - x_i)$ is 0.  If it is 0, then (no matter what $c$ is) the $j$th coefficient of the entire polynomial will be the $j$th coefficient of $P(x)$ (which we know); if it is nonzero, then (depending on what $c$ is) it could be any value.

For the linear term ($j=0$), this coefficient is $\prod_{i=0}^{t-2}-x_i$, which (because we're in a field) is nonzero if and only if all the $x_i$ values are nonzero (which they are in Shamir's scheme).

For the highest term ($j=t-2$), this coefficient turns out to be 1, hence the secret is never leaked (even if the share $x_i=0$ was issued).

For the second term ($j=1$), this coefficient turns out to be $-\sum_{i=0}^{t-2}x_i$, that is, the secret is revealed if $x_0 + x_1 + … + x_{t-2} = 0$, which (for the case $t=3$) is what you came up with.  Further note that, if we're in an even characteristic field ($1+1=0$), then $x_0 + x_1 \ne 0$ (unless $x_0 = x_1$, which cannot happen), hence in that specific case, the secret is not revealed.

Since I wrote the original answer, I found yet another corner case which is secure; if the field order is $p^z$ (that is, the field has that many elements), and if $t = p^z-1$, and the share $x_i = 0$ is not issued, then all coefficients are secure.  That's because, for any $k$ $(k$ being the share which is not revealed), we have $\prod_{i \in GF(p^z), i \ne 0, k}(x - x_i) = (x^{t} - 1) / (x - k)$, and that doesn't have any 0 coefficients.  For course, this really is a corner case, as there are only $t$ possible shares, and we need all $t$, hence this is a $(t, t)$ secret sharing scheme (and if so, why are we bothering with Shamir anyways; there are simpler methods).

Other than those cases, it is plausible for me to speculate (although I don't have proof) that for any middle coefficients, one can find a set $x_0, x_1, …, x_{t-2}$ that does leak the secret, assuming that the adversary can pick which shares he gets (which is analogous to the CPA assumption).


Finding missing bits mathematicaly in a DLP situation (full problem)

Resolution plan

$N$ is a composite with no trival factor, and our plan will be:

Find what's missing in $r$ (14 decimal digits) from what's known, the values of $N$, $g$, $h$, and the relation $g^r\equiv h\pmod N$, using a minor variation of the baby-step giant-step Discrete Log algorithm.
Similarly find the missing decimal digits in $s$.
Raising $g^r\equiv h\pmod N$ to the power $s$ then substituting $h^s\equiv g\pmod N$ gives $g^{r\cdot s}\equiv g\pmod N$. Hence $r\cdot s-1$, which we now can compute, is a multiple of the order of $g$, and thus has a fair chance to be a multiple of $\varphi(N)/2$.
Note: That's not sure! In the preparatory problem $g$ is of order $\varphi(N)/2$, and it's at best reasonable to hope that in the full problem that order is $\varphi(N)/2$ or $\varphi(N)$. However, if $g$ has been randomly selected, its order likely is a multiple of $\varphi(N)/c$ for some small $c$ dividing $\varphi(N)$, and $c$ can be searched.
Factor $N$ from its value and that of the multiple of $\varphi(N)/2$ just obtained.

Finding the full $r$ with baby-step giant-step

We are working in base $b$ and missing digits of $r$ at index $i$ in set $\Bbb M$ (starting at index 0 on the right), and can write $\displaystyle r=\hat r+\sum_{i\in\Bbb M}x_i\,b^i$ with unknowns $x_i\in[0,b)$. Here $b=10$, $\hat r$ is obtained by replacing @ with 0 in the given form of $r$, and the 14 indexes of the @ starting from the right are $\Bbb M=\{16,106,116,126,137,146,154,163,172,181,191,201,212,229\}$.

We split $\Bbb M$ about evenly into disjoint subsets $\Bbb U$ and $\Bbb V$ and rewrite $g^r\equiv h\pmod N$ as

$$\begin{array}{llll}
g^r&\equiv&h&\pmod N\\
g^{\left(\hat r+\displaystyle\sum_{i\in\Bbb M}x_i\,b^i\right)}&\equiv&h&\pmod N\\\\
g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb M}\left(g^{(b^i)}\right)^{x_i}&\equiv&h&\pmod N\\
g^{\hat r}\cdot\displaystyle\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}&\equiv&h\cdot\displaystyle\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}&\pmod N
\end{array}$$

We pre-compute $g^{-1}\bmod N$ (using e.g. the half-extended Euclidean algorithm), and $\left(g^{-1}\right)^{(b^i)}\bmod N$ for ${i\in\Bbb V}$, then can sequentially compute and store in a data structure allowing fast search all $b^{|\Bbb V|}$ values of $\displaystyle\left(h\cdot\prod_{i\in\Bbb V}\left(g^{(-b^i)}\right)^{x_i}\right)\bmod N$ (alongside the matching tuple of $x_i$ for $i\in\Bbb V$). We start from $h$ for all $x_i=0$ with ${i\in\Bbb V}$ and perform one modular multiplication for each other (we need $|\Bbb V|$ intermediary variables, including $h$).

We pre-compute $g^{\hat r}\bmod N$ and the $g^{(b^i)}\bmod N$ for ${i\in\Bbb U}$, and sequentially compute and search in said data structure $g^{\hat r}\cdot\displaystyle\left(\prod_{i\in\Bbb U}\left(g^{(b^i)}\right)^{x_i}\right)\bmod N$. We start from $g^{\hat r}\bmod N$ for all $x_i=0$ with ${i\in\Bbb U}$ and perform one modular multiplication for each other (we need $|\Bbb U|$ intermediary variables, including $g^{\hat r}$). When we get a match, that gives us all the $x_i\in\Bbb M$ (those from $\Bbb V$ come from the data structure, those from $\Bbb U$ are the one which led to the match), hence the full $r$.

The worst case computing effort is dominated by about $2\,b^{|\Bbb M|/2}$ (here 20,000,000) modular multiplications modulo $N$ (here, costing about $2\,\lceil(\log_2N)/32+1\rceil^2<1500$ elementary multiplications of 32-bit variables and additions of the 64-bit result using schoolbook algorithms). We are talking minutes of runtime, and less than 3 Megabytes of memory (and by making $|\Bbb V|$ one smaller, we reduce memory requirement by a factor $b$, at the expense of runtime).


The following picture shows EAX:

As you can see there is a OMAC calculation (or CMAC as it is usually called) over both $N$ (the nonce) and $H$ (the header / associated data). With regards to security it doesn't matter where you place the nonce and the other data in the header.

I'll not go into the security of XOR'ing the calculated OMAC values for nonce, header and ciphertext. EAX has a security proof, as long as that holds the cipher should be secure.

It would be best to treat the nonce and the rest of the header separately, as that would be the expected way of treating the input data. It also allows you to pre-calculate the header's OMAC value if it remains static. Note that you could remove the size of the plaintext from the OMAC calculation. You could calculate size of ciphertext + tag, and verify that.


Is this the right way to implement ElGamal scheme over Elliptic Curves over prime field?

It does not matter what encoding scheme you use for the message, as long as it is reversible: you should be able to recover the message from e.
Assume you do not know $e$ or $R_x$ (the x-coordinate of $R$). You are given $$e \cdot R_x \mod p$$
For any possible message $e'$ that you could guess, there is some integer $n$ such that $$e'\cdot n \equiv  e \cdot R_x \mod p$$
(exercise: what is this $n$?)

If you could determine which of $e$ and $e'$ was the correct message, then you would be able to tell which of $n$ and $R_x$ is the correct x-value of the shared secret $R$. But we assume that the attacker is not able to distinguish $R$ from a random point on the curve (this is the Decisional Diffe Hellman assumption).

Essentially, you do not need to worry about an adversary "factoring" $R_x \cdot e$, because in the integers mod $p$ there is not a unique way of factoring a number, for exactly the same reason that there is no unique way of factoring into rational numbers: $6 = 3\cdot 2$, but it also equals $4 \cdot \frac{2}{3}$ or $95 \cdot \frac{6}{95}$


Your 102-digit nuber is two digits more than the first RSA challenge RSA-100 that has 330-bit.
This can be easily achieved with existing libraries like;

CADO-NFS ; http://cado-nfs.gforge.inria.fr/

NFS factoring: http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html

Factoring as a service https://seclab.upenn.edu/projects/faas/

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.

The experiment
Factor of a 99 digit number
$n =$ 112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869.

I have tried with Pollard's $p$ -1 algorithm, still running for one and a half-day and did not produce a result, yet. This is what expected due to the B bound must be around $2^{55}$ with success probability $\dfrac{1}{27}$. I've stopped the experiment after the CADO-NFS succeeds. This is self-implemented Pollard's $p$ -1, one can find an optimized in GMP-ECM

Tried the CADO-NFS. The stable version may not be easily compiled for new machines, so prefer the active one from the GitLab.
After ~6 hours with 4 cores, CADO-NFS produced the result. This was an RSA CTF/Challange and I don't want to spoil the fun; here the hash commitments with SHA-512, it is executed with OpenSSL;
echo -n "prime x" | openssl sha512

27c64b5b944146aa1e40b35bd09307d04afa8d5fa2a93df9c5e13dc19ab032980ad6d564ab23bfe9484f64c4c43a993c09360f62f6d70a5759dfeabf59f18386

faebc6b3645d45f76c1944c6bd0c51f4e0d276ca750b6b5bc82c162e1e9364e01aab42a85245658d0053af526ba718ec006774b7084235d166e93015fac7733d

Experiments on RSA challenges with 6 cores using CADO-NFS

RSA Challange
Bit size
Time in minutes

RSA-100
330
270

RSA-110
364
280

RSA-120
397
1049

RSA-129
426
3279

RSA-140
430
Not tested

The core count is very important to reduce the time as 512-bit can be broken as 4 hours in the EC2 platform.

Details of the experiment

CPU : Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz

RAM : 32GB - doesn't require much ram, at least during polynomial selection and Sieveing.

Dedicated cores : 4

Test machine Ubuntu 20.04.1 LTS

CUDA - NO

gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)

cmake version 3.16.3

external libraries: Nothing out of Ubuntu's canonicals

CODA-NFS version : GitLab develepment version cloned at 23-01-2021

The bit sizes;

$n$ has 326 bits
$p$ has 165 bits
$q$ has 162 bits

The cado-nfs-2.3.0 did not compile and giving errors about HWLOC-  HWLOC_TOPOLOGY_FLAG_IO_DEVICES. Asked a friend to test the compile and it worked for them. It was an older Linux version. So I decided to use the GitLab version.

Note: this question did not factor the OPs original number.

Historical note: RSA-100 challenge has 330 bits and broken by Lenstra in 1991.


Collision resistance of hash functions with short, fixed-length inputs?

SHA256
The Max File Size
First of all the variable length has a limit due to the padding of SHA256. A message with length $\ell$ is padded with a 1 with necessary minimal $k$ zero bits so that
$$\ell+1+k ≡ 448 \bmod 512$$
This upper limit, actually, due to the Merkle-Damgård (MD) design of SHA256. MD based hash functions are vulnerable to length extension attacks and appending the length simplifies the security proof.
The Collisions are inevitable
Since the output of the SHA256 is limited to 256 bits and the input to $2^{64}$ bits. By the pigeonhole principle there is a least one hash output that contains more than one input. Therefore, there is always collisions.
Actually, if we consider that the SHA256 behaves uniformly, then we expect that all of the output values are equally distributed. A simple and similar experiment done for SHA-1
The generic collision attack
The generic collision of hash functions is calculated by the birthday paradox, and in cryptography, it is called birthday attack.
For a hash function with $t$ bit output the attacks requires $\mathcal{O}(\sqrt{2^{t}})$-time with %50 probability. For SHA256 this is $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$-time with %50 percentage.
Questions

When I limit the input length of SHA-256 to for instance a fixed 8 bits, the chance of a collision drops to zero (with SHA-256 there are no collisions possible with only 256 inputs, all inputs have a unique output).

You consider the reverse case. You limit the input space to 8-bit, i.e. 64 elements. Seeing a collision here is near to zero. Now you tested it experimentally and it is zero. Actually, this is like one throws 64 balls into the air and you expect them to get some of them into the same bin from $2^{256}$ bins. Hopefully, SHA256 is not such a bad hash function that doesn't have a collision with these very related inputs that have almost 8 bits differs. Theoretically, we expect the hash functions have the avalanche effect that changing one bit flips the output bit with %50 percentage. This distributes them randomly.

How much can I truncate the output of the SHA-256 with a fixed input length of 64 bits so that I keep the same collision resistance strength characteristics as the original SHA-256 with variable-length input?

$2^{64}$ cannot be easily tested for this size due to the memory and CPU requirements, entities like Google can test it like in their SHA1 experiment.
If the time is not a problem then one can build a Rainbow table to see the existence a collision or not. We, however, can calculate a probability for this assuming the $n=2^{64}$ values are chosen randomly, not sequentially.
$$ 2^{64} \approx  \sqrt{2 \times 2^{256} \times p(n)}$$
$$2^{128} \approx 2 \times 2^{256} \times p(n) $$
$$ p(n) \approx \frac{1}{2 \times 2^{128}}$$
This is the probability of having a collision of randomly chosen $2^{64}$ values for SHA256. This is not going to happen.
Small input space
In Cryptography, we want the hash functions to have the pre-image resistance. Almost all cryptographic hash functions are secure against pre-image attacks. There is one special case of this attack that when the input space is small, then the attackers can calculate, too. In this case, the $2^{64}$ Input space may not be enough to protect the data. To mitigate a keyed hash function like HMAC or KMAC is advised.


How to pass an arbitrary signature to a certificate

I'm not quite sure if I understand you correctly.

As far as I understand it, you want to produce a threshold signature on the hash value of an X.509 certificate. It is not sure if you require a distribute key generation of the private key, or you are in possession of the signing key and distribute shares of the key to all stakeholders.

1) Actually, in case of X.509 certificates you sign the hash value of the certificate fields.

2&3) Yes this is possible by using any threshold signature and using the hash-then-sign paradigm. You may look here for a related question.

4) Either run a distributed key generation or generate the keypair for the signature scheme and distribute the shares of the private key to the stakeholders (put the public key in your (self signed) CA cert). Then, to sign an X.509 certificate, compute the hash value and run the distributed signing algorithm on it. Integrate the resulting signature in the X.509 certificate.


Key/IV pairs should not be reused for either AES-CTR and AES-CBC - or for any other symmetric cipher for that matter. As a cipher is a Pseudo Random Permutation (PRP) inserting the same input will result in identical output. If a key/IV pair is reused then information is leaked to an attacker; the attacker can distinguish data with the same contents.

CTR is a streaming mode for block ciphers. In AES-CTR the key stream depends only on the key and the IV, not the plaintext. This key stream is XOR-red with the plaintext. It is possible to find additional information about the plaintext in addition to the issue above; if the key and a counter value are reused then the XOR of two ciphertexts is identical to the XOR of the plaintexts. So the key would still be safe, but the plaintext can be easily retrieved.

Reusing the key for any cipher should be no issue as long as the IV is unique - up to the specified amount of plaintext that the cipher can handle, usually a very large amount. In the case of CTR the IV should be unique enough to make sure that the counter does not repeat. Please read into CTR mode to see what that means when generating an IV. Make sure that it is understood what IV/nonce means for the specific application of CTR; the terms can be mixed up and may be used differently for specific protocols and implementations.

For CBC there are additional constraints: information about the IV should not be available in advance to an attacker that can alter the plaintext (chosen plaintext attack or CPA). Using a 16 byte value that is indistinguishable from random to an attacker should indeed preclude any attacks on the block cipher mode. That IV may simply be prefixed to the ciphertext in plain. If an authentication tag is used over the ciphertext then the IV must however be included in the calculation of the authentication tag (e.g. HMAC value).


Implementation of oblivious transfer with symmetric primitive?

You can take a look at LibOT, which is a C++ implementation of several OT extension protocols.
In the Readme you can find a list with many base and extension Oblivious Transfer protocols.

A protocol that people use a lot is the Simplest OT (although it was announced that the security proof has a bug by one of the authors at the TPMPC2018 workshop).

Another popular option is PVW, the protocol by Peikert, Vaikuntanathan and Waters.
It has two variants.
One DDH-based and another LWE-based.
The first one is particularly easy to understand and implement.