Is this encryption algorithm built from MD5 secure?

The algorithm (now reasonably clear) is reminiscent of a block cipher in CFB mode, with $random$ as the IV (which can be public), $secret$ as the key, and MD5 used as keystream generator instead of the block cipher.

Decryption works as in CFB:
\begin{align*}
M_1 &= C_1 \oplus \operatorname{MD5}( secret\mathbin\|random )\\
M_n &= C_n \oplus \operatorname{MD5}( secret\mathbin\|C_{n-1} )
\end{align*}

If MD5 was secure in the Random Oracle Model, that would be as secure as a 128-bit block cipher in CFB mode. Although MD5 is not secure in the ROM, I do not see an attack compromising the confidentiality of the message in a non-interactive attack, assuming the $secret$ is unguessable and $random$ not reused. In particular, I do not see that the feasibility of MD5 collisions, or MD5's length-extension property, directly enable an attack.

Main issues are:

This is unsafe if $secret$ is short or/and susceptible to enumeration, for there is no key stretching used.
This is unsafe if the attacker can inject something in the message being encrypted, based on earlier ciphertext blocks in the same message.
This is unsafe if the deciphering side reveals deciphered messages that do not make sense, and the attacker can modify the ciphertext.
There is no attempt at protecting the integrity of the message.
No test vectors are given.
This is inefficient compared to a block cipher (but in a context where MD5 is the only efficiently implemented cryptographic primitive, it might still beat a block cipher coded in an interpreted language).
MD5's name is tarnished, it has known weaknesses, and attacks only get better.
The whole thing is not an established algorithm, and nothing in the present answer constitutes any form of endorsement, much to the contrary.


Difference between eavesdropping and traffic analysis

The Wikipedia definitions;
Traffic analysis;

Traffic analysis is the process of intercepting and examining messages in order to deduce information from patterns in communication, which can be performed even when the messages are encrypted

Eavesdropping;

Eavesdropping is the act of secretly or stealthily listening to the private conversation or communications of others without their consent.

This type of network attack is generally one of the most effective as a lack of encryption services are used. It is also linked to the collection of metadata.

Wikipedia definition of Eavesdropping is a bit historical definition. In the cryptographic terms, the Eavesdropper listens to the medium and tries to break the ciphers, and the action is Eavesdropping. We call it also a passive attacker and passive attack, respectively. We don't use traffic analysis to eavesdropping.
Traffic analysis, today, is used in computer security. Traffic analysis can be executed even the channel encrypted with OTP. The time of the message, the frequency of the messages etc. All can be very important to signal intelligence. However, OTP has perfect secrecy so no passive attacker can break it.
For example; If the battleships send to their control center we are alive message for every 8 hours in a normal day with OTP, then any increase of the messages during a day may indicate that there is an action around. So the enemy can concentrate on this region. As you can see, this leaked information. This can be prevented by on-line encryption. There are more examples in Wikipedia;

It is difficult to defeat traffic analysis without both encrypting messages and masking the channel. When no actual messages are being sent, the channel can be masked

Traffic analysis is a very broad term and it came also from the history (part of Signal Intelligence). It can  still be applied if the protocols are not considered to prevent this attack as in Timing Analysis of Keystrokes and Timing Attacks on SSH


Using HMAC SHA256 to protect payment files in local trusted network

With regards to the algorithm, HMAC-SHA256 is considered very secure. As with most symmetric algorithms it can probably not be proven secure, but that should not worry you overmuch.

The most important security consideration with HMAC is to use a time consistent compare when verifying the authentication tag. A 256 bit key could be considered for the simple reason that the overhead won't make any difference when ~2MB files are being protected.

It's probably better to focus on other parts of the system security and make sure you implement the key management well.


How many bits of symmetric security does RSA-3072 actually provide?

The https://www.keylength.com/en web site summarizes reports from well-known organizations to give cryptographic key length recommandations for different kind of algorithms. Also note that

  The lengths provided here are designed to resist mathematic attacks;
  they do not take algorithmic attacks, hardware flaws, etc. into
  account.

Plus, there is a feature which allows you to enter the modulus size to synthetize the results: https://www.keylength.com/en/compare/

So by entering $3072$ as the modulus size, according to all the different organizations mentioned on this web site, it is assumed that the $\texttt{RSA-}3072$ security level is equivalent to a $128$-bit symmetric key.

Note that there can be some discrepancies according to the different organizations. For example, for a $2048$-bit modulus size, ANSSI claims that it has the same security level as a $100$-bit symmetric key while NIST says it is $112$.


How to find the generator of an elliptic curve?

If the elliptic curve has prime order of points, then all of its points are generators.

Almost: The point at infinity is not a generator, but (if the number of points is prime) all finite points are. This is a consequence to Lagrange's theorem.

  If so, how can I find the optimized generator (which generates more points) among them?

This does not make sense: Any generator of a group must generate all the points, otherwise it wouldn't be called a generator (by definition).
Note also that generally, the choice of base point does not matter, thus one typically uses random points or points with "interesting" (e.g. small) coordinates.


How to pick up random number within range using pseudo-random number sequence

If you have a uniform sampler for integers in the interval $[0, 2^k)$, such as an LFSR (which is not very uniform, but let's pretend it were) or any cryptographic PRNG truncated to $k$-bit outputs, the standard way to sample from integers in the interval $[0, n)$ when $n < 2^k$ and $n$ is not a power of two is by rejection sampling.

Consider reducing an integer $x$ in $[0, 2^k)$ modulo $n$, giving $y = x \bmod n$.  For each of the $n$ possible values of $y$, there are either $\lfloor2^k/n\rfloor$ or $\lceil2^k/n\rceil$ possible values of $x$ giving $y$—that is, either $2^k/n$ rounded down, or $2^k/n$ rounded up, depending on whether or not $y$ has an ‘extra’ representative $x \geq n\cdot\lfloor2^k/n\rfloor$.

For example, if $k = 4$ so $2^k = 16$, and if $n = 3$, then for $x \in \{0,3,6,9,12,15\}$, of which there are $\lceil16/3\rceil = 6$ possibilities, we have $y = 0$.  But for $x \in \{1,4,7,10,13\}$ or $x \in \{2,5,8,11,14\}$, of which there are $\lfloor16/3\rfloor = 5$ possibilities each, we have $y = 1$ or $y = 2$, respectively.  Thus $\Pr[y = 0] = 6/16$, but $\Pr[y = 1] = \Pr[y = 2] = 5/16$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y =  0  1  2  0  1  2  0  1  2  0  1  2  0  1  2 *0

If we first sample an integer from $[0, 2^k)$ uniformly at random, and then reduce modulo $n$, the result will be biased toward the values of $y$ that have an extra possible representative $x \geq n\cdot\lfloor2^k/n\rfloor$, such as the representative $x = 15$ for $y = 0$ in the example above.  That gives a nonuniform distribution on integers in $[0, n)$.  This bias is sometimes called the modulo bias, although it happens whether the map from $x \in [0, 2^k)$ to $[0, n)$ is $x \mapsto x \bmod n$ or anything else—you can never fit 16 pigeons into 3 holes and get the same number of pigeons per hole, no matter what order you put them in.

If we repeatedly sample integers from $[0, 2^k)$ uniformly at random, and reject some fixed subset of them, say $x = 15$ in the example above, then we can ensure that the only set of values for $x$ we will consider divides evenly into equal-size sets of representatives for $y$.  It doesn't matter which subset of values for $x$ we reject, as long as they divide evenly—we could also reject $x = 0$, or even $x = 3$.

x =  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
y = *0  1  2  0  1  2  0  1  2  0  1  2  0  1  2  0

One easy choice is to reject all values of $x$ below $2^k \bmod n$, because that bound can be computed in $k$-bit unsigned integer arithmetic by the simple expression $(-n) \bmod n$, since
\begin{array}{}
2^k \bmod n &= 2^k \bmod n - 0 \\&= 2^k \bmod n - n \bmod n \\&= (2^k - n) \bmod n.
\end{array}

This gives the following algorithm for sampling an integer in $[0, n)$ uniformly at random given a uniform random sampler for integers in $[0, 2^k)$:

Sample $x$ uniformly at random from integers in $[0, 2^k)$.
If $x < 2^k \bmod n$, start over.
Return $x \bmod n$.


Excel 2007 (12.0) and up uses an iterated hash and AES encryption by default if you use the native, non-backwards compatible XML format (.xlsx), so the weak point is for sure the password. Depending on how safe you need to keep the document, you can use simple passwords, or you can use more complex character sets and combinations of words. If you are using an earlier version of Office or not using the .???X file format, assume it is insecure.

The encryption process itself uses with Windows crypto provider, and the default settings are generally secure; AES 128-bit encryption in CBC mode on 4KB chunks of data, the OS random number generator for salt and IV based on that salt, and an iterated hash (at least 50000) based on SHA-1 or SHA-2, depending on the version of Office. These settings be changed, if you are concerned I would suggest checking the encrypted document, the XML format will define the type of encryption used.

For high security, I require an 80-bit strong password. If you are using random characters from the default alphanumeric 62 character set, a secure password length is 14 characters, and would be considered unbreakable by normal means, 22 characters would match the strength of AES.

If your password is NOT random characters (rather actual words or phrases), then there are methods to estimate password strength, but they can be very inaccurate, usually telling you it is stronger than it really is. Easy to remember words and phrases are generally easier to crack, the algorithms used by password cracking software are quite effective at cracking even long passwords if the password is not random.

If you need actual words, I suggest you choose at least 6 random words from the dictionary that are at least 5 characters long. You can also use the PGP wordlist, which allows you to easily use bytes from a random number generator to get them. You would need at least 10 words to be secure, and 16 to match the strength of AES. Other wordlists are acceptable, such as the diceware list, if you are aware of how much strength there is per word (12.9 bits for diceware).


Performing differential cryptanalysis for randomly generated S-boxes

With DES, the issue is the size of the s-box. The DES s-boxes are highly tuned for their security properties, but if you compare their nonlinearity to the larger AES s-box, the are quite inferior.

Note than random s-boxes and key dependent s-boxes are not the same thing. Random = fixed random, key dependent = permuted s-boxes based on the key. A random set of key dependent s-boxes is a different story, essentially, you are generating random s-boxes using key material.

If you tried to apply random key dependent s-boxes to DES, it can indeed make the whole algorithm weaker. With enough ciphertext/plaintext pairs, and knowledge of the the algorithm less s-boxes and keys, it is quite possible to perform key recovery. The biases are substantially larger with inferior s-boxes. I believe it reduced the data requirements of a differential attack by more than 10000X. Since the attack is much more effective than brute force, the additional complexity of using key material to generate the s-boxes does not strengthen it enough, only by about 32 times vs fixed random. See CS0816 for more detail.

A variant of DES exists where extra key material is used to reorder the standard s-boxes into one of 32 orders known to increase the strength of the algorithm, it is similar to having a key dependent s-box, and it does make the DES variant stronger.

With larger s-boxes and better design (and more importantly, larger keys), key dependent s-boxes work. Twofish is a great example of this. The key dependent s-boxes are not random, they are generated in a specific way from the key material as to be strong. However from a purely mathematical perspective they are not as strong as the AES s-box, but they have the advantage of not being known to the attacker. This may or may not be an advantage in the face of improving attacks. The additional advantage Twofish has is multiple s-boxes, which leaves less attack surface is one of the s-boxes does have a problem, but increases implementation complexity.

Another example is Khufu and Khafre, which are quite similar, but Khufu has key dependent s-boxes, and is more secure.

Overall, Twofish is thought to have better security than AES, and the key dependent s-boxes are one of the reasons why. DES in comparison, is not designed for key dependent s-boxes, which is why using them can weaken it more than it can strengthen it. The modified order however does work, and combined with DES-X style whitening, makes DES essentially invulnerable to linear and differential analysis, since the amount of plaintexts would be at least $2^{60}$ for linear, maybe more, and exceed the codebook for differential.

EDIT
Here is a new paper where AES variants with a secret s-box are attacked. Integral cryptanalysis was the method of attack.


Modes for encrypting small binary blobs?

You can use a key wrap scheme.  Frankly, any authenticated encryption mode would probably be fine, but a key wrap scheme is designed for exactly this purpose: encrypting one key under another key.  So, you might as well use one of the accepted key wrap schemes.


An adversary who can compute discrete logs modulo $p$, given oracle access to $H_a$ for unknown $a$, can compute $\log_2 H_a(2) \equiv \log_2 2^a \equiv a \pmod p$ with a single query to the oracle.

After that, given $h = H_a(M)$ for unknown $M$, they can compute $$h^{a^{-1}} \equiv (M^a)^{a^{-1}} \equiv M^{a\cdot a^{-1}} \equiv M \pmod p,$$ where $a^{-1}$ is the inverse of $a$ modulo $\phi(p) = p - 1$.

If $p$ is 256 bits, adversaries can compute discrete logs modulo $p$ today.  You need $p \gg 1024$ to be safe, among other criteria.

It might be helpful to go into more detail about why you need these properties, and what you are trying to achieve more generally.


Symmetric vs non-symmetric pairing based crypto

This lecture by Dan Boneh should answer all your questions and more:

https://www.youtube.com/watch?v=F4x2kQTKYFY

ps. I saw you also had a question about NIZK proofs, so you should check out the full list of videos

https://www.youtube.com/playlist?list=PLXF_IJaFk-9C4p3b2tK7H9a9axOm3EtjA

which has almost 3 hours of lectures on Groth-Sahai proofs by Jens Groth which might interest you.


Elliptic Curve vs RSA key length comparison

The comparison can be made according to know attacks and their timings. Your source doesn't provide a reference and date backs to 2015, so that is not a good site as keylength.com. The current values of this answer is taken for 2019.

ECC

For ECC 128 bit security means we need 256-bit curves due to the generic discrete log attacks that have $\mathcal{O}(\sqrt{n})$-time. Your cited page also matches this.

RSA

For RSA it is more complicated since there are different methods around. For example, NIST gives 112-bit for RSA-2048.

There is a good cost estimate with Batch NFS for RSA-2048 in area-time cost per key of about $2^{103}$ taking $o(1)$ as zero, rather than the cost $2^{112}$ advertised by keylength.com, NIST, etc.

Commercial National Security Algorithm, Information Assurance Directorate at the NSA IAD-NSA give 256-bit security for RSA-3072 and ECC with 384 bit.


I think this simply comes down to the definition of Unix time, which is given in the Wikipedia article:

  Unix time (also known as POSIX time[1][2] or UNIX Epoch time[3]) is a system for describing a point in time. It is the number of seconds that have elapsed since 00:00:00 Thursday, 1 January 1970,[2] Coordinated Universal Time (UTC), minus leap seconds. Every day is treated as if it contains exactly 86400 seconds,[2] so leap seconds are to be subtracted since the epoch.

Although I would have described it as "without taking leap seconds into account" myself. Generally you should be able to get the Unix time from some time API or old API function, but otherwise (a) seems to be most reasonable. The Wikipedia article also contains ways of converting from different time formats, specifically UTC.


Why can you reverse a modulo function when knowing its primes

What i don't understand is how it gets easier to reverse this function when you know the primes that you used to calculate the divisor

Well, we know how to compute square roots modulo a prime; that is, how to solve the problem $a \equiv x^2 \pmod p$, for prime $p$ (assuming, of course, if there is a solution; there might not be one).

In addition, if we know the solution to $a \equiv x^2 \pmod p$ and we know the solution to $a \equiv x^2 \pmod q$, then we know the solution to $a \equiv x^2 \pmod{lcm(p,q)}$ (which is $a \equiv x^2 \pmod{pq}$ if $p$ and $q$ are relatively prime.

What this means that if we know the complete factorization of $n$, then we can solve $a \equiv x^2 \pmod n$ (by looking at each prime factor $p$ of $n$, solving $a \equiv x^2 \pmod p$, and then combining all the answers).  (Actually, I haven't gone into what you would do if $n$ had a factor $p^2$, however that isn't that much more difficult).

With that said, what if you don't know the factorization of $n$; how can you solve $a \equiv x^2 \pmod{n}$?  Well, if $n$ is large (that is, large enough to make factorization impractical), then that looks like a hard problem.  In fact, if you could solve that problem, it turns out you can factor $n$ (by selecting a random $r$, and then trying to solve $r^2 \equiv x^2 \pmod{n}$.  It turns out for composite (more specifically, has at least 2 prime factors) $n$ that there are (at least) four possible answers, and for at least half the answers $s$, $gcd(n, r-s)$ is a nontrivial factor, so that has a good probability of yielding a factor.  Hence, if we have a way to solve this equation modulo a composite, this gives us an efficient way to factor that composite.

So, if we assume factoring is a hard problem, so is computing square roots modulo a composite.


Is using different public keys for different peers safer than reusing the public key, beyond forward secrecy?

Generally for forward secrecy you should not just limit the use of the private key (and thus public key) in time, but also per connection. For that reason, you can assume that in most implementations that require forward secrecy that there will be one ephemeral key pair per connection, not per time frame.

Similarly, you're assuming that a new key pair is generated regularly, but please note that this kind of wording may be interpreted as once in a certain time frame. It makes a lot of difference how much the key is actually used within that particular time frame. So I think in your scheme you're using the private keys too much (you could tie that to forward secrecy, but you haven't made is explicit that you did see this tie to PFS).

One of the big disadvantages of your scheme is that the delivery of the public keys is required for each party. Some parties actually may not be active at all, and therefore distribution of the keys would be waste full. It also means that there must a central distribution point, which could wreak havoc in a distributed design.

Possibly you should simply exchange public keys each time you want to generate a new symmetric key, tying the validity of the private key to the symmetric key. How long you want to keep that symmetric key active is another matter. I'd say you could keep it active for a certain amount of actions within a specific time frame; having two rather than one limit for invalidating key pair and generating new ones. I'd certainly do that for each connection separately as indicated in the first section.


Conditions for Perfect Secrecy with the Vigenere Cipher

As far as I can tell, your original reasoning is correct.  To obtain perfect secrecy with a Vigenère cipher, the key must not repeat.  The key does not repeat whenever it is at least as long as the message, so option 2 is clearly a sufficient (and indeed necessary) condition for perfect secrecy, at least as far as only key length is considered.  Options 3 and 4 are subsets of option 2, so if choice 2 is correct, then they must be correct as well.  Thus, the correct answer (unless this is a trick question) should be (2, 3, 4).

Note, however, that there are conditions on the perfect secrecy of a Vigenère cipher other than key length.  In particular, to obtain perfect secrecy with a Vigenère cipher:

the key must be at least as long as the message,
each of the key letters must be selected independently and uniformly at random from the entire ciphertext alphabet, and
the same key must not be used for more than one message.

The options in the question you quote make no mention of the second and third conditions, so arguably, none of them is sufficient to guarantee perfect secrecy.  While I would consider this to be a rather nasty trick to play on the test-taker (especially given that such an argument would seem to contradict the "correct" answer to the other question you quote), technically this would be a valid answer (and arguably the valid answer) to the question.

Ps. One possible interpretation, which just occurred to me, is that your course might be using a definition of perfect secrecy which is violated if the length of the message is revealed to the attacker (and is not the same for all valid messages).  This is actually a reasonable definition to adopt: if the attacker knows in advance e.g. that your message is either yes or no, then simply learning the length of the message will tell them which one it is.

Since Vigenère encryption does reveal the message length, this would rule out option 2, leaving only options 3 and 4 (where revealing the message length gives no information to the attacker, since all valid messages have the same length) as correct answers.


How does GHASH used in GCM behave as a universal hashing function?

Indeed $H=E_k(0)$ is used to choose from the family. This is not a problem, and here is some intuition on why.
The output of the hash function is not leaked in clear, it is "hidden" by xoring with $E_k(iv,ctr=0)$ which is different per each encrypted message (in contrast to $H=E_k(0)$). Otherwise it would be indeed trivial to recover H as the UHF is linear.
Intuitively, the property used is that UHF should be hard to blindly predict the difference for any two inputs without knowing the key, even with multiple attempts, but without revealing the UHF value on each attempt.
Note that the "difference" matters here because in forgery attempts you are allowed to reuse the nonce, so guessing the right difference would suffice for a break. For example, given $$(iv,m,t),~~ t=E_k(iv,ctr=0)\oplus GHASH(m))$$ and guessing the difference $\Delta = GHASH(m)\oplus GHASH(m')$ would allow to forge
$$
(iv,m',t'),~~ t'=t\oplus \Delta=E_k(iv,ctr=0)\oplus GHASH(m').
$$


Which is the most overall 'compatible' encryption type?

A lot of (non-US federal) clients I work with request a shared Dropbox or Box for file transfer. If they want to feel "extra secure", non-tech-savvy clients in the past have enjoyed getting hardware-encrypted flash drives the most because they like how "simple and easy" it is to handle them. I don't necessarily endorse these approaches; as mentioned in the comments, marketing influences what your clients want, regardless of their requirements, but I have rarely been in a position to change their minds.

More grizzled war stories follow.

Sadly, the situation is more like "Client #1 wants MP3s, Client #2 needs WAVs, Client #3 will only talk to me if we go listen to concert music together", etc. I don't think you will find any particular format will scale to an arbitrary number of clients, who all have (or believe they have) specific needs.

Here is a sample of the scenarios I have encountered in the past decade or so:

Scientific data (C code, Fortran-77 code, text, Excel spreadsheets) sent to my lab:
password-protected DVD, client would send password in e-mail
Financial data from an insurance company: set up secure FTP server with developers on their side
Transmitting data within a company itself: Data is put into a MySQL database and I was asked to "please delete the data in a few days"
Financial data from a bank: Sent us an email that opened a web application that required a password so that we could download some data
Getting data from a university partner: Mailed us a USB-C drive with a keypad to enter a password, which...was written on a sticky-note

I'm not sure what kinds of clients you have, but I guarantee you that you will have one that will surprise you with what they want soon, if you haven't already had this happen to you!


A classic linear feedback shift register is in fact a representation of operations in a modular ring of binary polynomials. In mathematical terms, you have a base field, which is $\mathbb{Z}_2$, the field with two elements (0 and 1); then a register of $n$ bits is a polynomial of degree at most $n-1$ in $\mathbb{Z}_2[X]$, and shifting the register is equivalent to multiplying the polynomial by $X$ modulo a given polynomial $P$ of degree $n$; that polynomial $P$ corresponds to the "feedback bits", i.e. which elements of the register you take to compute the new bit.

This model naturally extends to the case of using another base field or ring. For instance, if you use bytes and additions, then you are working with $\mathbb{Z}_{256}$, i.e. the integers modulo 256. With $n$ bytes, you still have polynomials of degree at most $n-1$, but this time in $\mathbb{Z}_{256}[X]$ (and it is still linear). Like the classic LFSR, taken alone as, say, a pseudo-random generator, it is still quite weak; moreover, $\mathbb{Z}_{256}$ is not a field, which tends to make matters worst (to express it "with the hands", additions modulo 256 will propagate carries only toward higher bits, so, in particular, the low bits of each byte will only depend on each other, not on the higher bits).

Now, symmetric algorithms are almost always built by assembling several (many) operations which, by themselves, would not constitute a cryptographic algorithm of any decent quality; for instance, SHA-256 is made out of about 2500 very simple elementary operations, the most complex of which being a simple addition. As such, LFSR expressed over various rings or fields can be used, and have been used, as building elements of larger algorithms. See for instance the Sosemanuk stream cipher, or the RadioGatún hash function.

A non linear feedback shift register would entail using operations that are not additions in some field of ring, i.e. not additions on integer or XOR. You could try some multiplications, but it will make analysis more complex with no clear immediate benefits. Remember that what is sought in symmetric algorithm design is a good trade-off between "mixing" (a generic terms for various concepts such as non-linearity and avalanche effects) and performance; moreover, we cryptographers really like to feel that we understand what we are doing, therefore "hard to analyse" is a bad thing, not a good thing.


There is no separate "digital signature exchange." A certificate is a self-contained thing; it contains an "issuer" field (with a DN of the CA that signed it) and a "signature" field (with a signature from that CA). A server does not just send its certificate in the ServerCertificate message; it sends a whole chain of certificates, starting with theirs, then having their CA, then their CA's CA, and continuing to a trust root (that the server hopes the client trusts).

For DHE and ECDHE (which have signatures used in cipher parameter exchange), the signature on those parameters is part of the ServerKeyExchange message that has the parameters. Again, there is no separate signature exchange.

As for which hash algorithm to use: This doesn't actually inherently have to do with the cipher suite, as certificate signatures are an X.509 thing. The signature algorithm is also included as a mandatory certificate field. An X.509 certificate contains all the information you need to authenticate it except the Issuer's public key. Certain cipher suites don't allow certificates that aren't signed with the right algorithm, but that comes later -- you can still verify the signature as soon as you get the certificate chain.

In response to your comment: The signature verifies a certificate, not a server. The server is implicitly verified because other operations prove they have the private key corresponding to the public key in that certificate. As a separate matter, nothing is at any point encrypted with a private key; this is a popular and wrong idea of signatures. A signature algorithm takes a message (not a hash) and outputs a signature; any hashing is part of the signature algorithm.

Edit 2: Let me try explaining the certificate validation process a bit more. Here's a picture of a sample certificate chain; blue arrows are "is identical" (e.g. Issuer DN is the Subject DN of your CA), and green arrows means "generates" (i.e. by signing, which is not encrypting and you shouldn't call it encrypting):

The server presents all four of those certificates in the Server Certificate message. The client then verifies the server certificate, using the following general certificate-validation process:

If the certificate is identical to something in the preset list of "trusted certificates" (e.g. a trusted root CA cert, or if you've manually added a trusted root certificate), then accept the certificate. If it's not and this is the last certificate in the chain, reject it (you don't trust whoever verified it).
If not, check that the certificate isn't expired and that the date it starts being valid isn't in the future (these are attributes I didn't show).
Check the Issuer, the signature algorithm, and the signature on the certificate. If there's a next cert in the list of certs you received, verify that that certificate's Subject DN is this one's Issuer DN.
Using the public key from the next certificate and the signature algorithm from this certificate, verify the signature on this certificate.
Verify that the next certificate has the CA attribute.
Validate the next certificate down the line using this same process.

If any of steps 2-6 fail, reject the certificate. This is all done using only the information in the Server Certificate message, which contains the full chain of certificates (OK, so technically you can leave out the self-signed root CA and the TLS client will check its trust root for a cert with the appropriate Subject DN, but that's a minor detail). At the end, you know that the server cert is the start of a chain of certs, each signed by the next one, where the last one is one you inherently trust (it's a root CA). There is no separate signature exchange; these signatures are part of the certificates.


How to prove that weak one way functions cannot have polynomial-sized ranges?

Here is a sketch of the proof, I will let you figure out the details. Let $n$ be your security parameter. If the function $f$ has polynomial size range $\{y_1, \cdots, y_{p(n)}\}$, then its domain can be partitioned as the union of a polynomial $p(n)$ disjoint subsets $S_i$, where each $S_i$ contains all values $x$ such that $f(x) = y_i$. Now, the game is as follows: the challenger picks $x$ at random, and returns $y = f(x)$. The goal is to find a preimage $x'$.

I claim that, except with negligible probability, the set $S_i$ associated with $y$ has inverse-polynomial density over the set of all possible preimages; that is, it contains a fraction $1/q(n)$ of all preimages for some polynomial $q$. This is simply for the following reason: if it is not the case that $S_i$ has polynomial density, then the probability that the value $x$ sampled by the challenger belongs to $S_i$ is negligible, and there are only polynomially many sets.

Now, this suggests a simple algorithm for inverting the function: sample $q(n)\cdot \omega(\log n)$ random inputs $x'$ from the domain, and compute $f(x)$. Then, the probability that none of the sampled inputs belong to $S_i$ is negligible ($2^{-\omega(\log n)}$). Hence, except with negligible probability, this algorithm will invert the function $f$ successfully on $y$, contradicting the claim that $f$ is a weak one-way function.

Of course, this is just a sketch, and some additional work is required to formally prove that everything works out fine, but it should not be too hard.

A little remark on how this should be properly formalized: working with "negligible" versus "non-negligible" would not work, since there can be weird intermediate things between "negligible size" and "inverse polynomial size". The right approach is to start from a specific $1/d(n)$-weak OWF (where each algorithm fails at inverting $f$ on a random output with probability at least $1/d(n)$), and construct through the above approach an algorithm that succeeds with better than $1-1/d(n)$ probability at inverting the function. To do so, consider all sets $S_i$ with density at most $1/(p(n)\cdot d^2(n))$: the union of all those $S_i$ has density at most $1/d^2(n)$, hence the random input $x$ of the challenger will be in a set of density at least $1/(p(n)\cdot d^2(n))$, except with probability $1/d^2(n)$. When this happens, sampling $p(n)d^2(n)\omega(\log n)$ random inputs gives a preimage with overwhelming probability, hence our algorithm succeeds with probability at least $1-1/d^2(n)-\mathsf{negl}(n)$ ($\mathsf{negl}(n)$ denotes a negligible function), contradicting the $1/d(n)$-weak one-wayness.


You got it right.
Email consists of several components:
A "From:" address, a list of recipient addresses (To, CC, BCC), several headers used for correctly routing the email to its destination, a "subject" message, and a "body" message (which includes attachments). You likely want to guarantee the integrity of all of these, and the secrecy of at least the subject and the body.
PGP only deals with the body. Nothing else is kept secret, and nothing else is authenticated. It considers everything else (including the "subject" message) to be "data packet header fields".
This means that a PGP signature of an email message will still validate when the subject is altered, the recipient is different, the sender is different, or other headers change. EG if you forward an email and change the subject line to start with "FW: " you'll be the sender, the new recipient will replace the original in the "To" field, the rest of the headers will differ, but the signature will remain valid.
Likewise if an attacker modifies the "From" to trick you into thinking someone else sent the message, changes the subject, or just wants to read the subject or correlate who is talking to whom, they can.
Unfortunately there's no way to fix these vulnerabilities without breaking backwards compatibility with unencrypted email. I therefore recommend avoiding email encryption, and using a system designed for security to begin with such as Matrix or Signal.


Why is it said that if we know few bits of pseudo random sequence we can predict the whole of it?

All psuedo random generators keep some limited state to calculate the next number in the sequence. you can think of it like a function $\delta(S)= \{output, S'\}$ with $S$ the internal state of the generator and represented by a finite number of bits.

This means that the number of states is limited (though it can be very big: a standard mersenne twister holds 2500 bytes of state)

As such if you get $n$ bytes of output with $n$ is larger than the number of bytes in the state then you can reasonably predict the current state of the output given enough time.

Note that if you group 256 bytes of output together and pass it though a sha-256 then it will take a very long time for you to restore first the original output of the generator and then the state when you know only the hash output. This is exactly how a secure PRNG works.


What is the most computationally efficient way of generating pseudo-random permutations?

Use format-preserving encryption. The current NIST standards-track mode FFX should be sufficiently fast for your purposes. For your domain size, you might also want to try the swap-or-not shuffle, a new construction that is also pretty fast and dead simple to implement. To get the absolute best speed form these schemes you should use a single AES call as your PRF, preferably with AES-NI instructions if you have them.
EDIT: Any PRP generator based on an oblivious card shuffle should work for your purposes. Here's another reference explaining what that is.


Multiplication/Division in Galois Field (2^8)

In GF(28), 7 × 11 = 49.  The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication.  In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example.  Noting that 7 = 1112 and 11 = 10112, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication.  But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      1112 + 11102 + 1110002 = 101012 + 1110002 = 10011012 = 77,

in GF(2n) addition is done bitwise without carries (i.e. GF(2n) addition is the same as bitwise XOR), and thus we get

      1112 + 11102 + 1110002 = 10012 + 1110002 = 1100012 = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)


I don't know much about the library you're using but it looks like you're trying to encrypt/decrypt the cipher-text using RSA directly.

Using RSA in this way isn't secure unless extreme care is taken.

This isn't the correct way to use RSA. Typically, what you do is use RSA to encrypt a secret key. This secret key is then used with a conventional symmetric cipher, such as AES, to encrypt your payload. Then your payload can be any length you like.

There are standards such as PCKS#1 v2.0 that deal with how to do this securely.


Likelihood of signature collision with EdDSA

Can we provably state that for a given payload and given private key, there is only one valid signature in the 512-bit signature space?

No.
If you consider EdDSA verification a legitimate signer can generate more than one signature of a given message, and all will pass EdDSA verification.
However, only the signature generated with the EdDSA signing procedure will pass cofactorless verification.
More details about how to generate alternative valid signatures are provided in this answer.
Regarding the more broader question:

Taking EdDSA as an example, given the length of a signature is
512-bits for a given data payload, what is the probability of a
collision where there is another 512-bit value that is also a valid
signature?

Requiring specifically to pass cofactorless verification only (to avoid the other valid signatures generated by the above technique), there should be a valid $S$ for each possible value of $r$. Since $R$ depends fully on $r$, and $0 \le r < L$, there are at least $L$ possible valid signatures, where $L$ is the order of the large prime subgroup. For ed25519, $L = 2^{252}+27742317777372353535851937790883648493$


The problem about fixed  points of discrete logarithms is  known the Brizolis problem. In particular for the average number of solutions
$$N(p)=\frac{1}{\varphi(p-1)}\sum_g\left|\{0\le x\le p-1:g^x=x\pmod p\}\right|$$ is known that (Grechnikov, 2012) $N(p)=1+S(p)$, where
$$-C(\varepsilon)p^{-1/4+\varepsilon}\le S(p)\le \exp(C'\mathrm{Li}((\log p)^{c\frac{\log\log\log\log p}{\log\log\log p}})).$$

It is also necessary to say that inversed problem is easier: for a given $x$ one can take $R=x^{x^{-1}\bmod (p-1)}.$


Ensuring no unintended leaking before authentication

Here are my comments in no particular order:

Don't create your own crypto.
We don't analyze designs on this website because it is hard work and you shouldn't create your own anyway.
It seems that for this protocol to work the server will have to store the user password in plaintext. That seems like a bad idea.
Using this scheme will allow an attacker to brute force the user password using only the information that has been transmitted since he can validate

auth_key = PBKDF2(password_guess, salt, cost, 768))

HMAC(cost.to_string + salt, auth_key) == auth_hash. That also seems like a bad idea.


Can we calculate AES-CBC-PKCS7 ciphertext length based on the length of the plaintext?

PKCS7 uses mandatory padding. Even if the length of your data is a multiple of your block size, it will pad.

output_size = input_size + (block_size - (input_size % block_size))


What is the actual difference between security through obscurity and true encryption?

We often mock "security through obscurity", but it is not without value, especially in today's web environment.

Most attacks today are statistical in nature:  a virus attempts to infect 10,000 computers by blasting out random attacks.  If it infects even two more computers out of those 10,000, it has achieved its goal.

Those viruses are aggressive in volume, not precision.  They don't all do a port scan, analyze the responses to determine OS version, they don't do a vulnerability assessment, then launch a precise attack the way a human would.  Instead, they try to exploit a common weakness - a buffer overrun exploit in PHP, or SQL injection vulnerability in a Wordpress plugin.  Anything the system administrator does to alter their defaults:  changing the base URL from "index.html" to "index.htm", or changing the database names in MySQL, might keep a particular automated attack from harming his system.  It doesn't remove the vulnerability, it merely changes it so that an attack relying on the defaults will not succeed.

Will this keep out a determined attacker?  Of course not.  But it will reduce the number of low-level threats that can still surprise anyone if they exploit a 0day vulnerability.  And those low-level threats can quickly escalate to be every bit as damaging as an Advanced Persistent Threat.

That's why obscurity, which I define here as to be "any implementation settings changed from the default", still improves your overall security picture.  It may only reduce a few particular attacks, or delay them by a few days, but those days can be enough to get a real patch installed.  In practice, preventing a threat from becoming a successful attack is the true job of security, regardless of whether it was based on bad theory.


If Blum Blum Shub is modified to use a prime modulus, is it still secure?

I suggest you read the paper about the generator, because that question is answered there:
A Simple Unpredictable Pseudo-random Number Generator, Blum, Blum, Shoup, 1986

They don't have any formal expression of what is called "state compromise extension" there, but they already state in the section 6. The $1/p$ generator is predictable on page 6 exactly the case of using a prime modulus.

Their main point is: Yeah, it might look nice and have nice properties, but you can "calculate forward and backwards in the sequence with about $2|p|$ digits of information."

For more details I suggest reading the paper.


Is there a way to know if a cleartext substring is present in a hash?

Short answer: not really.  I think the closest thing you're going to find is a "cryptographic accumulator." I can accumulate the separate hashes of the strings A,B,C,D.  But even then, testing whether A is in the result requires more than just the accumulator itself - you also needs a piece of data called a "witness for A" - which is a separate number that "proves" that A is in the accumulator.

Merkle trees have the same problem - to prove that A is in the tree, you need more than just the final total of the tree.  You also need to know where A appeared in the tree, and the hashes of the other branches of the tree.


As you can see in the Wikipedia article a ciphertext block is used for two different things during decryption:

as input to the block cipher to calculate the output, which is then XOR'ed with the previous ciphertext block to create the corresponding plaintext block at the same position;
as input to the XOR to calculate the next plaintext block, together with the next decrypted block.

You can see it clearly in the picture, by following the arrows of one of the ciphertext blocks:

(XOR is denoted by $\oplus$ )

As the block cipher is a pseudo random permutation the plaintext block at the same position is indistinguishable from random even if only one bit is changed. The fact that it is XOR'ed with the value of the previous ciphertext block does not change this fact. There is only one restriction: the result is not identical to the plaintext block that would be calculated without the change.

Things are different with the next plaintext block. Only those bits that have flipped in the ciphertext block will be flipped in the next plaintext block. So the change is localized and not random.

Next or previous blocks are not affected as the affected ciphertext block, intermediate values or plaintext blocks are not used as input anywhere else.


RSA: How effective is this keypair-trash attack

Without waiting to get a collision, there is a more annoying scenario : compute the gcd of all public keys you can scan over the net. Experience did show that a lot of systems do not generate enough unique entropy (Lenstra, A., et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, February 2012). Based on that scenario where everyone in a pool of 2000000 public keys use the same 4000 primes, the probability that 2 users get the very same combination of 2 primes is not so remote (the birthday paradox ....), and the response to your question is : yesterday, at latest. It did occur.

Let's assume that pseudoprimes from probabilistic testing do not interfere (they do, with a jackpot lottery probability!) ... when randomness is weak for integer generation, it is weaker for probabilistic tests.

Let's assume that you don't care about safe prime, strong primes, extra strong safe primes, and all the paranoid method of prime generation which might exclude all of them, because none is really strong and safe enough ....

Assuming your integer selection does not strictly follow some standards which only check the first prime candidate at the end of a prime gap, thus excluding all primes at the start of a prime gap.

Considering the evolution of software and electronics, Elliptic Curve is approximately 10 times faster at equivalent security levels and equivalent source code optimization levels. Monica's database will never fill.

Assuming Cloud Quantum Computing is approximately 60-70 years ahead and Wiki leaks  reveals in 30 years that NSA already has a 2048 quBit computer in a vault, this gives a end-of-life of 30 years to Monica database.

Assuming ....

Now, assuming that key generation is fair, everyone is using RSA2048 with 2 x 1Kbit primes and these prime numbers are evenly distributed in the range $[\sqrt{2} \cdot 2^{1023}, 2^{1024}]$, and are safe prime, i.e. $(p-1)/2$ is also prime. There are approximately c =

10474478420880630540417976938987964186481756527689107725320293990926166280934544
54955114259503095991159974600201604222625579123974838523076493430916373173064804
47871510202082442494709247560640274359031066510018408132368005212283030654515197
893087986785888352332881597122452139709939124879383308130303597

such 1 Kbit primes.

Assuming you like to play the national lottery and are familiar with a low probability $10^{-10}$ to see the first fateful collision event ( http://en.wikipedia.org/wiki/Birthday_problem ) and using a birthday paradox formula, then  $10^{-10} = 1 - \exp(-d^2/(2c))$.

You would need this number of keys:

$$d = \sqrt{ \ln(1.0000000001)\cdot 2c)}$$

d = 552129915947348069547969241673542619236474053
1711023498369601774599992268056593071378343449425
9320014789158954279395322381058948290665165722107332

At a rate of 1 new key per nanosecond, your key storage cloud solution must absorb 1 terabit of continuous throughput, plus the little 600% overhead of https connections, disconnections, you might require a computer the size of the universe (including the 99% of it which is supposed to exist amd has not been formally proved, and there will be no energy left to generate enough keys). But let's assume ....

The response is : you need

34195165591218423336373586540577052517638203484900091229
87420239096781423943440303949716847304675114278446095972
125316749920908117079065 years 92 days 3 h. 23 m. 10 s.

for a 0.000000001 % chance to witness a RSA key collision in your database.


Cryptography Engineering - Design Principles and Practical Applications - Chapter 9 Generating Randomness - Section 9.4 The Generator

This section talks about Fortuna, where it uses a block cipher with a 128-bit block and a 256-bit key size. The cipher is used in CTR mode. In the CTR mode, if an attacker can access the internal state than then the security is lost ( the key and current counter value), therefore after a request, 2 new blocks are generated and used as a new key, and the old key is forgotten to eliminate exposure of the old requests.
All talk is about distinguishing the PRP from PRF in the CTR mode. In the CTR mode with a PRP, if you encrypt with one key then $2^{128}$ blocks are distinct since it is a permutation, but we don't expect this from a PRF. So the PRP-PRF switching lemma applies to distinguish the statistical deviation. After $q$ messages the security lost is proportional to $q^2\!/2^{128}$.
In the classical birthday attack, when the outputs are random we expect collisions, remember the CTR mode doesn't generate one with PRP. For a PRF with 128-bit output, approximately

Once we generate $2^{64}$ outputs there will be  $$\approx (2^{64})^2/2^{128}/2 = 2^{128 - 129} = 1/2$$ change collision. But we will not see one in the Fortuna, it uses PRP in CTR mode! Therefore this is a distinguisher.

if you only generate $2^{16}$ blocks for a single key then the probbaility is $$\approx (2^{16})^2/2^{128}/2 = 2^{32 - 129} = \dfrac{1}{2^{97}}$$ this means this distinguish probability is negligible.

Requesting $2^{97}$ blocks is the reverse of the birthday attack. Since one has $\dfrac{1}{2^{97}}$ change of seeing a collision for $2^{16}$ blocks then you need to request $2^{97}$ blocks to see a collision within a $2^{16}$-block. Therefore the cost is $2^{97}\cdot 2^{16} = 2^{113}$.
For 256-bit block sizes, the collision is no more a threat since you need to $2^{128}$ blocks to see one with 1/2 probability.
$$\approx (2^{128})^2/2^{256}/2 = 2^{256 - 257} = 1/2$$
The $2^{113}$ is continuation from the 128-bit attack cost, since $$(2^{113})^2/2^{256}/2 = \dfrac{1}{2^{32}}$$


Is there an existing AE protocol with forward secrecy for embedded devices?

I've finally found a solution - some variants of key ratcheting, e.g. the one used in SCIMP, provide perfect forward secrecy assuming an initial shared secret is established without any asymmetric crypto, and they don't even require a secure random number generator on any of the endpoints!

In this case all we need for an authenticated and encrypted protocol with perfect forward secrecy a symmetric cypher, an authenticated encryption mode for said cypher (e.g. EAX) and a hash. We can even ditch the RNG on the embedded device.

This is not a complete protocol, but gets us most of the way to one, and it's dramatically simpler both in the implementation and the number of required primitives than TLS.

The hard part is proper handling of message losses on the wire without opening up to downgrade attacks, but it's easier than correct custom implementations of asymmetric crypto.

Ironically, nobody I asked could tell me about using such key ratcheting for perfect forward secrecy. Our team has come up with the scheme on its own and only after that I've found it in literature.


Deduplication: Encrypting the SHA-256 hash of a file chunk

Information leakage in systems that do data deduplication typically involves timing hints that the data is already stored and related leverage of that information.  See the comments in https://security.stackexchange.com/questions/7142/online-backup-how-could-encryption-and-de-duplication-be-compatible/7146#7146 for insights there. Suggest you consider your attacker's profile and see of any of those issues apply as a confidentiality threat.

Efficient deduplication needs to maximize the capture of identical data and thus is typically done at the file level or some subset that will always produce the same chunks in the same file.  If your chunk boundaries plan addresses that you are good otherwise consider it.

Finally, encrypting a hash with a method that always produces the same output would appear to add very little protection if any.  The hash is by definition not reversible so the only potential value is in protecting against someone who can recreate the hash and wants to know if they are correct about the guessed plain text or binary.  That attack assumes the attacker can see the resulting hash.  If that is the case then seeing the predictably encrypted result adds very little to the attackers task as he only needs to see that the data is not moved to storage but rather already exists in the system (see first point about information leakage).


Provably Secure Password Authenticated Key Exchange Based on RLWE for the Post-QuantumWorld

A password authenticated key exchange (PAKE) scheme assumes that the two parties have some shared secret (the password) with too little entropy. They now want to agree on a key and authenticate each other using this password.

The trick is to do this in such a way that an attacker cannot brute force the password with recorded data. This ensures the password remaining secure in spite of the low entropy because you always have to talk to one of the parties to try a guess.

So 1. and 2. are out of scope for PAKE schemes. The password is just assumed to be pre-shared. 3. and 4.: Yes, $\mathcal{C}, \mathcal{S}$ identify the client and the server. These must usually be included  in authentication protocols to avoid tricky relay attacks. I recommend Boyd's book for details.


For all units $u$,  $(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)$  is a factorization of $c$, and  $a^{-1} \hspace{-0.06 in}\cdot \hspace{-0.04 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)$  and  $\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.04 in}b^{-1}\hspace{-0.04 in}\right)^{\hspace{.04 in}-1}$  both give $u$, so [either factor and which side it is] is enough to deduce $u$.

Let "the modified factors" be  $a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u$  and  $u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b$ ,  let N be the number of units,

and suppose the guesser makes at most q+1 guesses.

Game 0:  The guesser wins if and only if at least one of its guesses is $u$.

Game 1:  The guesser wins if and only if at least one of its

guesses is [either modified factor and the modified factor's side].

Game 2:  The guesser wins if and only if at least one

of its guesses is at least one of the modified factors.

Game 3:  The guesser may indicate at most one of its guesses as "final", but regardless,

it wins if and only if at least one its guesses is at least one of the modified factors.

Game 4:    The guesser may indicate at most one of its guesses as "final".

After each guess that is not indicated as final, the guesser is sent 0.

The guesser wins if and only if at least one of its guesses is at least one of the modified factors.

Game 5:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final]

which is one of the modified factors, the guesser is sent 1.  The guesser wins

if and only if at least one of its guesses is at least one of the modified factors.

Game 6:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1.  The guesser wins if and only if

[it indicated a guess as final] and that guess was at least one of the modified factors.

Game 7:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0.  After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1.  The guesser wins if and only if

[it indicated a guess as final] and that guess was the modified factors.

Game 8:    The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 0.  After each [guess that's not indicated as final] which is one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 1.

The guesser wins if and only if [it indicated a guess as final] and that guess was $a,\hspace{-0.02 in}b$.

In Game 0, there are only q+1 guesses for N equally-likely possibilities,

so the probability of winning Game 0 is at most (q+1)/N.

As explained before, $u$ can be deduced from [either modified factor and the

modified factor's side], so for each Game-1 guesser, there's a Game-0 guesser with the

same winning probability.  Thus the probability of winning Game 1 is also at most (q+1)/N.

For each Game-2 guesser, there's a Game-1 guesser with half the winning probability (just guess the side at random), so the probability of winning Game 2 is at most twice the maximum probability of winning Game 1.  Thus the probability of winning Game 2 is at most (2*(q+1))/N.

For each Game-3 guesser, there's a Game-2 guesser with the same winning probability.

(Just ignore the presence or absence of a "final" indication.)

Thus the probability of winning Game 3 is at most (2*(q+1))/N.

For each Game-4 guesser, there's a Game-3 guesser with the same winning probability.

(Just send it 0 after each guess that's not indicated as final.)

Thus the probability of winning Game 4 is at most (2*(q+1))/N.

Game 4 and Game 5 only differ when a win is already guaranteed,

so the probability of winning Game 5 is at most (2*(q+1))/N.

The only difference between Game 6's winning conditions and Game 5's winning condition

is that the former's winning condition is a restriction of the latter's winning condition, so the probability of winning Game 5 is at most (2*(q+1))/N.

For each Game-7 guesser, there's a Game-6 guesser

with at least as large a winning probability.

(Just pick one part of its indicated-as-final guess).

Thus the probability of winning Game 7 is at most (2*(q+1))/N.

For each $u$, the equations $\;\;\; a\cdot u \: = \: c \;\;\;$ and $\;\;\; u^{-1} \cdot b \: = \: d \;\;\;$ both have a unique solution, so exactly N choices of $a,\hspace{-0.02 in}b,\hspace{-0.02 in}u$ yield modified factors $c,\hspace{-0.02 in}d$. $\;\;\;\;\;\;\;\;$ That means the

distribution of modified factors is uniform, so identical to the distribution of $a,\hspace{-0.02 in}b$.  Thus the probability of winning Game 8 is at most (2*(q+1))/N.

Finally, observe that Game 8 is exactly the game for guessing $a,\hspace{-0.02 in}b$ given $c$ and [at most q queries to the test function].  Therefore, for all adversaries which make at most q oracle queries, their success probability is at most (2*(q+1))/N, where N is the number of units.

As mentioned by Chris Peikert,

Input: $R$

Output:  $R,\hspace{-0.02 in}R$

is "an algorithm to parameterize a list of ideals $I_1,I_2$ such that $(c)=I_1\cap I_2$".

That will be "the same as listing all solutions $x,y$

such that $c=xy\in R$" at least when $R$ is commutative.

(Finiteness might also be enough; I can't figure that out right now.)

However, there are rings in which $1$ can be factored into two non-units.


ISO 9564-1 format 4 does not need a IV since it adds entropy to the plaintext PIN before encrypting.  There is no need to append a random value to the PIN.

The Format 4 PIN block algorithm is illustrated above.  The PIN and the PAN are both padded.  The padded values are called the plain text PIN field and the plain text PAN field.  The last $8$ bytes of the padded PIN field are random.  The plain text PAN has deterministic padding. The plain text PIN field is encrypted and then XORed with the plain text PAN field and the result is then encrypted again, yielding the encrypted PIN block.
Format 4 is typically used with a fixed AES key for each encryption operation on a particular device.  Since there are only $8$ bytes of mixed-in entropy for each PIN-PAN combination, Format 4 has the potential to be vulnerable to a chosen plaintext dictionary attack.  An attacker could capture an encrypted Format 4 PIN Block.  The attacker could then recover the PIN by repeatedly encrypting all possible PIN values until by chance the encrypted PIN block is the same as the encrypted PIN block the attacker is attempting to decode.
There are $64$ bits of random data in the plain text PIN Block. The PIN is between $4$ and $12$ decimal digits and thus adds at least $13$ bits of entropy.  Therefore above attack would require at least $2^{77}$ chosen plaintexts.
It would difficult to obtain $2^{77}$ chosen plaintexts from any single device.  Furthermore, the PCI PTS standard requires compliant devices to rate limit PIN encryption to $120$ PINs per hour.  As such, the above attack is not feasible.


Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

Once an attacker knows $2L$-bits of an $LFSR$ of length $L$ with unknown taps, they can use the Berlekamp-Massey algorithm to construct your LFSR. If the taps are known, then only $L$ bits are required. Therefore your PRNG based on a single LFSR will fail. They were popular but anymore.

LFSR's has no next-bit security. From previous known states, the next bit is exactly can be found.
More generally, an attacker that knows the current state, they have more power than predicting the next outputs, they know the next states of your random number generator.
LFSR's can be run backward, which will reveal the previously generated random numbers. Once an attacker accesses the system, they will able to decrypt the previously encrypted messages. See the Double ratchet which is used by Signal.


Check the validity of a rsa key pair with only the public key?

While there are some obvious checks you can do, you can't cover everything:

You can check that the modulus is a composite odd number of the appropriate size
If you want to put in the effort, you can do a quick check if the modulus has any small factors
You can check if the public exponent is an odd number > 1

However, you can't check beyond that; you can't check if the modulus might not be specially built to be easy to factor, and you can't check if the public exponent is actually relatively prime to $\phi(N)$.  What is likely more important to you, RSA doesn't provide a way to verify that the public key entered is the specific public key of the intended receiver.

BTW: you said that this is a big security risk; what is the scenario that you fear that an attacker might introduce a bogus key, and gain some advantage?  If it's the fear that someone might substitute their public key, well, since they're likely to substitute a valid key, a validity check on the key isn't likely to protect you.  Instead, you need some other mechanism to tie the public key with the identity.


Can public key help attackers to break RSA encryption faster?

Can really good attacker(hacker) use public key for his advantage and break RSA encryption faster?

No; we always assume that the attacker knows the public key (that's what "public" means, after all).

  Is there some advantage to have each RSA key with different bit size?

No; the most efficient approach known to attack an RSA key is to use the Number Field Sieve algorithm; which that approach, the attacker picks one RSA key, and attacks it.  It doesn't matter if the keys he selects from has different sizes; he's likely to pick the smallest and/or the one that protects data of the most value.


Attacking AES without transposition using ShiftRow and Mixcolumn layers

After the key expansion, there would be 16 different mappings for each of the 16 bytes in a block.

Suppose we are attacking the block cipher itself (in ECB mode), with each byte having 256 different values, we can query 256 ciphertext blocks (all-bytes-0, all-bytes-1, ... all-bytes-255) to get the exact plaintext-to-ciphertext mapping for all 16 bytes's 256 values.

To decrypt future blocks, you just need to have a 16x256=4096 byte (1 memory page) table of the inverse map which you can easily create now.


Are there deterministic private-key encryption schemes that are CPA-secure?

Summarizing fkraiem's comment, a CPA-secure encryption scheme can not be deterministic.

The reason is simple: the attacker is challenged to distinguish between the encryption of $m_0$ and $m_1$, but he also has access to an encryption oracle (and he can query the oracle at whatever input he wants!). If the encryption scheme yields the same ciphertexts each time it's queried on the same plaintexts, the attacker can simply ask the oracle for an encryption of $m_0$ and an encryption of $m_1$, and compare which one is equal to the given challenge ciphertext.


Pseudorandomness of ring learning with errors

Let $R$ be the ring $\mathbb{Z}_p[X]/(X^n+1)$, where $n$ is a power of 2.  The Ring-LWE assumption says that for any randomly chosen, fixed $s\in R$, the distribution of $$((a_1,a_1s+e_1),\ldots,(a_k,a_ks+e_k))$$ is indistinguishable from the distribution $$((a_1,u_1),\ldots,(a_k,u_k)),$$ where $a_i,u_i$ are uniformly random in $R$ and $e_i$ are chosen from some distribution with small coefficients.

Of course, if one $only$ outputs $((a_1s+e_1),\ldots,(a_ks+e_k))$ without also revealing the $a_i$, then this distribution is trivially uniformly random (assuming that $s$ is invertible in $R$, but this is a minor issue) because the $a_i$ are uniformly random.  This would be a pretty useless property.

The interesting part in Ring-LWE is that even when the $a_i$ are revealed, the distribution still looks uniform.  Basically, the small additional entropy of the $e_i$ allows one to create a new uniform-looking element with larger entropy.


You did not mention the mode of operation for any block cipher that is necessary.

CBC mode requires the IV random and unpredictable so this is not your way.

CTR mode requires an $(IV,Key)$ pair never occurs more than once. One must never use the same $(IV,key)$ pair again, otherwise, confidentiality is lost.
CTR mode generally uses 96-bit nonce and 32-bit counter to form the Initial value. If the nonce reoccurs and counters repeat then these blocks can be revealed with crib-dragging. The nonce can be chosen randomly that will have a 50% probability of collision after $2^{48}$ random nonce generation. Counter/LFSR-based nonce generation is also recommended by NIST.

CTR mode can be a solution for you.
The above modes don't provide you more than confidentiality. We can, and we should go more;

GCM provides you confidentiality, integrity, and authentication. Since GCM uses the CTR mode for encryption, you will have the same (IV, key) reuse problem.
If the IV has 92-bit length then $J_0 =IV || 0^{31} ||1$ is passed to the CTR mode as the IV where the 32 bits is used as a counter which starts  form $1$. SO if you reuse the same IV under the same key, you will have the same problem in the CTR mode.

XChaCha20-poly1305 is ChaCha20 with an extended nonce that we can use random nonce more securely. It has 192-bit nonce sizes and one has a collision with 50% probability once generates $2^{96}$ random nonces under the same key. Though this has the same $(IV,key)$ problem the probability of getting it is not-going-to-happen.

There is also AES-GCM-SIV mode. This is nonce-misuse resistant and even the IVs are the same the mode will only leak that the messages are the same. This requires additional passes over the data.

Therefore, one can use AES-GCM-SIV to mitigate all possible problems or use xChaCha20-poly1305.
For the user, you should note that the IV/nonce of the encryption is never meant to be secret. They can be stored, usually prepended, with the ciphertext. During the client-side encryption, they can be created. Therefore the user doesn't need to know anything about the IV/nonce after the encryption, the server can store them with the ciphertext. The user only needs the secret key and must keep it secret all the time.


Are these functions pseudo random? Why or why not?

Whether $F′$ is a pseudorandom function revolves around: can it be efficiently distinguished from a random function? That is, can you design an experiment (distinguisher) that has better-than-random chance to recognize a box computing $F_k′(x)$ given $x$ for some random unknown fixed $k$, from one which computes some random function (a random oracle)?

For one of your two cases, you can, thus $F'$ is not a pseudorandom generator. To prove that, just find and expose how your distinguisher works, and prove that it works better than random.

Hint 1: one way is to find some number of distinct $x$ such that $F_k$ will be evaluated with the same input, and detect that with fair odds from the output of $F_k'$.

Hint 2: In the present situation, said number is at least 2.

Hint 3: The proof that the distinguisher works better than random requires $n>2$, which can be assumed.

For the other case, you can't make a distinguisher , thus $F′$ is a pseudorandom generator. The usual formal proof technique is contraposition: assume a distinguisher for $F′$, and derive a distiguisher for $F$, which by hypothesis does not exists.

Here, there's a more intuitive approach: $F_k'(x)$ is made by concatenation of outputs of $F_k$; and such outputs are indistinguishable from random (for one not knowing $k$), except that the same input to $F_k$ yields the same output. Thus if the outputs of $F_k$ are for distinct inputs whenever we evaluate $F_k'$ for distinct inputs, then the overall output of $F_k'$ for distinct inputs is indistinguishable from random, and $F'$ is pseudorandom.


Symmetry between a public and a private key

The public key and private key are related, but that does not mean that they have to be symmetric, and normally they are not. For instance with a public/private key in RSA, the public exponent is normally a small value, while the private exponent has a larger value. They can have the same properties though - making them symmetric in that sense - but this is not common.

As for EC public and private keys, these have different properties. One is actually a vector and the other a point. So there is no symmetry there.

What is common is that the public and private key share some properties. For RSA keys this is the modulus, and with EC keys the domain parameters should be equal for the algorithms to work.

I don't think it is wise to think of a public and private key to be symmetric, even though both keys are part of the same mathematical framework.


Diffie-Hellman explicit key confirmation

The major thing missing from Diffie-Hellman is that it provides no protection from someone running a man-in-the-middle attack.  Your changes don't actually do anything to prevent that.

That is, suppose Eve was between Alice and Bob; when Alice sends the first message to Bob, Eve intercepts the message, and performs the exchange with Alice.  At the same time, Eve forwards her own exchange to Bob.  If Alice and Bob were attempting to perform this exchange to create secret keys, well, they will really share keys with Eve; when Alice sends a message, Eve will receive that encrypted message, decrypt it with the key she shares with Alice, examine it, and then encrypt it with the key she shares with Bob, and forwards it.  That way, Eve sees all the traffic between Alice and Bob without being aware of it.

There is nothing that this key confirmation does that makes this any more difficult for Eve; she can compute $H(k_1, k_2)$ just as well as Alice and Bob, and so she will be able to impersonate Bob to Alice (and impersonating Alice to Bob).

Now, if the question was "is it secure if we don't have to worry about man-in-the-middle", the answer is "well, straight Diffie-Hellman is secure in that scenario; your additions don't appear to have made anything worse".


Diffie Hellman Problem (DHP) and Discrete Logarithmic Problem (DLP)

DH for reference:

  Alice takes a random $a$ and sends $g^a$ to Bob.
  Bob picks a random $b$ and sends $g^b$ to Alice.
  Both compute $g^{ab}$ Alice as $(g^b)^a$, Bob as $(g^a)^b$.

As you already explained breaking DLOG will break DH in the following way:

An attacker can e.g.

take $g^a$ and compute $a$ by solving the DLOG problem.
use $g^b$ to compute $(g^b)^a = g^{ab}$.

At this point the attacker knows the shared secret $g^{ab}$ and DH is broken.

However what about the other way around? Does breaking DH mean that we can compute DLOGs? The situation is not so clear...

Breaking DH means that the attacker is given $g, g^a, g^b$ and is able to find the shared secret $g^{ab}$.

The question is can we somehow leverage this knowledge of $g^{ab}$ to find $a$ or $b$.

If yes, DH and DLOG would be equivalent because breaking one always means breaking the other.
If no, DLOG would be strictly harder than DH because we can break DH without breaking DLOG but not the other way around.


Which is more secure for hashing: SHA512 or BCrypt with the same salt reused over and over?

bcrypt is a password hashing method. That means that it expects a password as input parameter. It has been designed so that it is hard to perform an offline test of guessed passwords by having an explicit work factor.

It accepts (or requires) a salt so that:

repeated passwords do not show up;
that it is impossible to build a (rainbow) table.

Now your entry is not a password. It is a secret value consisting of 16 bytes or 128 bits. That it is encoded as 32 hexadecimal digits doesn't make any difference, assuming that each hexadecimal digit is equally likely.

Correctly guessing a fully random 128 bit secret is similar to guessing a 128 bit AES key. This is not likely to happen soon. For this reason you do indeed not need bcrypt for the additional work factor

Similarly, if it is indeed fully random, then you do not need a salt either. The salt makes the result probabilistic, so that you don't get the same value back. However, this seems at odds with your requirements to lookup the hash.

If you don't want to expose your secret then you could use a key based key derivation function (KBKDF) rather than a password based key derivation function (PBKDF). Such a function transforms a secret into another secret of given size. If you don't use a salt then the result will be deterministic and you can check for the value in a table. HMAC-expand is one of the later algorithms that you could use.

For your use case you could also use a more generic Pseudo Random Function (PRF) directly. HMAC is a good example of a PRF that can be used for derivation as well. If push can to shove you could also use a SHA-256 I suppose, as a poor man's KDF / PRF. Theoretically hash functions may not adhere to strict requirements for key derivation, but in practice a symmetrical-crypto-based hash function such as SHA-2 will probably fit your need.

Whichever scheme you use, it makes sense to make sure that your scheme doesn't perform the same operation on the original secret as the KDF/PRF/Hash. If you want to make sure that it doesn't: use a KBKDF with a specific label and/or static random value.


In SKE, can we assume without loss that the ciphers of a fixed plaintext distribute identically?

Is this possible without using any cryptographic assumptions which don't already follow from the existence of an IND-CCA1 secure SKE?

Yes, symmetric-key encryption implies the existence of "uniform" symmetric-key encryption. But I don't know of a particularly direct way to show it. Below is an extremely convoluted, theoretical, impractical way to do such a transformation.

If CPA-secure symmetric-key encryption schemes exist, then so do one-way functions. This is shown in Impagliazzo-Luby.

If one-way functions exist, then PRGs exist; this is the classic "HILL" result.

If PRGs exist then PRFs exist; this is the classic GGM result.

Once you have a PRF you can construct an authenticated encryption scheme based on counter mode with a MAC like Carter-Wegman. This scheme will have the property that you need, since the ciphertext is a deterministic function of the (uniform) initialization vector + key + plaintext, and no two choices of initialization vector give the same output (since the IV is included in the output). Hence the output is uniform over the support.


Using plain Diffe-Hellman for server authentication with known public key

An adversary can (repeatedly) submit $h$ as $g^c$ to get a random $N_s$ such that the adversary will

be able to test, with heuristically overwhelming accuracy, whether or not $\: \operatorname{KDF}(N_s,h^s) = x \;$.

An adversary could also attempt to learn something more about what session key the

server obtained, by sending an alleged ciphertext to the server after the key agreement.

(In particular, an adversary could do those things after seeing the client's actual value of $g^c$.)

It would be tricky to show security against such an attack without also showing

security against the case where, for each $h$ value, the adversary will learn

$\langle N_s,\operatorname{KDF}(N_s,h^s)\rangle\:$ for a random $N_s$ (chosen after the adversary chose $h$).

Such a security result would be somewhat analogous to CCA2 security; the analogy would be better

if $N_s$ was the same each time. $\;\;$ Unlike when I previously addressed a similar construction, I am now convinced that this will hold under $\:$KEA1 + KDF-is-a-random-oracle + computational-diffie-hellman$\:$ .

Under those three assumptions, the key agreement will be secure against an adversary

that can choose the server nonces $N_s$, including the ability to cause them to repeat.

The four signing algorithms that you might prefer over the above are BLS,BB,ECDSA.

(That's four because the middle one gives a variant that does use a random oracle.)

However, there are potential efficiency improvements that can be

obtained for only a known and very minor decrease in security.

In particular, in three of your four examples, it will only decrease security against an

active adversary that nonetheless does not have reliable communications with both honest parties.

For the first example and the last two examples, the encryption or MAC with $K_s$ or $K_m$ respectively

will defend against an adversary that [can modify a message in transit but will later

be unable to communicate with either $C$ or $S\hspace{.02 in}$] carrying out a "weak misbinding".

(I use the term "weak" because that is something an adversary with full control over

the communiations channel can necessarily do, no matter what protocol is used.)

Furthermore, for the first example, the encryption won't necessarily

succeed at that goal, although I suspect that it heuristically should.

For STSsao, encrypting the signature will (also) stop a passive eavesdropper

from being able to show that the server carried out a key agreement.

Those are the only reasons to use $K_s$ and $K_m$.

If one declines to use the relevant key, then one obviously should also not derive that key.


How used nonce in CTR Mode of AES-EAX Encryption?

I already figured it out myself. Lol
So, in paper "The EAX Mode of Operation" by M. Bellare, P. Rogaway, and D. Wagner explained that in CTR algorithm and i wasn't aware. The 128-bit auth nonce will be encrypt in ctr mode and concatenate with encrypted nonce+1 until encrypted nonce+m-1, which m is amount of block plaintext. And at last xor it with plaintext.


What (if any) information can an eavesdropper infer in this scenario when using DES in OFB mode?

For DES we generally assume that an attacker can find out all information as the attacker can simply brute force the key. For a more secure protocol you could use another 64 bit block cipher such as triple DES (in three key mode, i.e. with keys of 168/192 bits) or another cipher such as Blowfish. However, if you want to use a streaming cipher you could also use AES, e.g. CTR or CFB mode; OFB isn't used all that often anymore and may not be available in all runtimes.

A block cipher is deterministic. This means that any repeating 8-byte message that is directly encrypted with it will result in the same ciphertext as the previously encrypted message with the same contents. This will therefore leak information to an attacker. Modes of operations such as OFB require a unique IV for each message so that this information is hidden. So no information can be inferred if the IV is indeed unique (assuming that the message size is indeed always constant).

Notes:

Note that encryption does not automatically protect the message for integrity / authenticity. You need a MAC or authenticated encryption (e.g. GCM mode) for that;
You may need to keep in mind that you should design for key change. If you for instance use a 64 bit (8-byte) random value then you may run into collisions after many messages and this will completely destroy the confidentiality of those messages in OFB mode;
You clearly need expert help. If you cannot afford that you may want to look into using transport security such as TLS or SSH or a lightweight protocol for embedded systems instead of trying to figure our your own protocol.


Probability that an attacker wins the discrete logarithm game when exponents are drawn from a subset

Assume there exists an adversary for your q-subset DL problem that will be successful with probability $\mathsf{succ(\lambda)}$.
If you just use this adversary to attack the original DL problem, he will get an input that comes from the set it expects with probability $q/p$ and will therefore be succesfull with probability at least $q/p \cdot \mathsf{succ(\lambda)}$.
However we know that the DL problem is hard.
Thus, we can bound the success probability of the adversary:
$$\mathsf{negl}(\lambda) \ge q/p \cdot \mathsf{succ(\lambda)}$$
$$p/q\cdot\mathsf{negl}(\lambda) \ge \mathsf{succ(\lambda)}$$

Thus we get a bound for the success probability against your q-subset DL problem.

Whether this bound is helpful, depends on $q$. As long as $p/q$ is polynomial, the upper bound is still a negligible function. So at least in theory this is still a hard problem.

In practice and for a fixed group size that is of course a completely different story.

Of course, if $p/q$ is superpolynomial, then the all bets are off and this upper bound does not help you in any way.


How to prove a cipher resistant to differential cryptanalysis?

The design documents for Rijndael explain exactly how the designers proved its resistance to differential cryptanalysis.

Read their submission to the AES competition process, particularly Section 8.2 and the Annex.  To understand their approach, it will probably help to understand differential cryptanalysis and read some of the related literature.  You can find a more detailed explanation in their book, The Design of Rijndael: AES.

You might enjoy the following research papers:

The Wide Trail Design Strategy
Provable Security against Differential and Linear
Cryptanalysis for the SPN Structure


General-purpose non-interactive multi-party computation protocol

It depends on what you mean by interaction.

Some protocols for secure multiparty computation, e.g. those based on Shamir secret sharings and the GMW protocol, require the servers to communicate a lot during the computation.

In other protocols, such as those based on Yao's garbled circuits (e.g. Fairplay MP), the interaction between servers is reduced in that the servers only need to communicate during a constant number of rounds, that is, a number of rounds that is independent of the size of the function they compute. But still, a lot of data traffic between the servers are needed during these rounds.

Some work has been done to further reduce the interaction required by secure multiparty computation. See for example this paper: Secure Computation on the Web: Computing without Simultaneous Interaction. This is in some sense non-interactive secure multiparty computation, but unfortunately the paper shows that it only works for a limited class of functions.


A strange phenomenon of the composition of permutations of order 2

So it turns out that there is nothing strange about the composition of random permutations of order 2. The thing is that the distribution of the size of the orbit of an element under the operation $g\circ f$ where $f,g$ are involutions strongly depends on the number of fixed points the functions $f,g$ and if $f$ or $g$ have large quantities of fixed points, then $g\circ f$ has small orbits.

When computing the iterates $(f\circ g)^{k}(x)$, when one encounters a fixed point of the function $f$ or of the function $g$ before going back to $x$, one begins to uncompute the iterates $(f\circ g)^{k}(x)$. After one uncomputes the iterates $(f\circ g)^{k}(x)$, one eventually uncomputes back to $x$, and at this point, one starts computing $(f\circ g)^{-k}(x)$. When computing $(f\circ g)^{-k}(x)$, one eventually encounters another fixed point of the function $f$ or of the function $g$. At this point, one reverses the direction of computation until one returns to $x$ in a complete orbit. The amount of time it takes to find the first fixed point follows an exponential distribution, and the amount of time it takes to find the second fixed point after crossing $x$ also follows an exponential distribution with the same parameter. Therefore, the amount of time it takes to make a complete orbit will be $X+X$ for some exponential distribution $X$. The probability density function of $X+X$ is $xe^{-x}$ up to renormalization however.

Observe that every permutation can be written as the composition of two involutions. However, some permutations have a much higher probability of arising as the composition of two involutions than other permutations.

Suppose $1\leq r\leq k$. If $h:[k]\rightarrow[k]$ is a random permutation, then the probability that the size of the orbit with respect to $h$ of a random element $x$ is $r$ is precisely $\frac{1}{k}$. Suppose that $f,g:[2k]\rightarrow[2k]$ are permutations selected at random subject to the condition that $f,g$ have no fixed points. Then let
$P_{k,r}$ denote the probability that the orbit with respect to $g\circ f$ of a random element $x\in[2k]$ has cardinality $2r$. Then, after one performs an exact computation of $P_{k,r}$, by taking a limit, one obtains $\lim_{n\rightarrow\infty}n\cdot P_{n,\lfloor nx\rfloor}=\frac{1}{2\sqrt{1-x}}$ for all $x\in(0,1)$ (in other words, $x$ probably has a very large orbit).

Now suppose that $f,g:[k]\rightarrow[k]$ are randomly selected permutations subject to the conditions that $\{x\in[k]|f(x)\neq x\}=2m,\{x\in[k]|g(x)\neq x\}=2n$. Then let $P_{m,n,k,r}$ denote the probability that the orbit of a random element has length $r$.

Then for $x>0$, we have $\frac{k\cdot P_{n,n,k,v}}{k-2n}\rightarrow xe^{-x}$ as $v\cdot\frac{k-2n}{k}\rightarrow x,k\rightarrow\infty,v\rightarrow\infty$. (I may probably give more details as to why this is the case later on).

Now, take note that the expected value of the distribution with probability density function $x\cdot e^{-x}$ is $2$. Therefore, the expected value of the size of the orbit of a random element approaches $\frac{2k}{k-2n}$. In the scenario outlined in the question, the functions $f,g$ typically have $O(\sqrt{|X|})$ many fixed points which would ensure that there are around $\frac{2k}{k-2n}$ many fixed points.


Your file is in "RAR4" format (alternatively called 2.9). This means it is not using PBKDF2 as version 5 is, but it still uses an iterative hash. A custom one based on SHA-1, with $2^{14}$ "iterations" each feeding some amount of data into SHA-1. Depending on the length of the password and whether a salt is used, this may not correspond exactly to $2^{14}$ iterations of the SHA-1 compression function.

Assuming a one-to-one correspondence between iterations and SHA-1, your 185000 passwords per second corresponds to about 300 million SHA-1 hashes per second. According to what I can find online (e.g. this), the raw SHA-1 hash rate of your GPU should be about 10x that, but considering the somewhat special structure of the RAR hashing function, it is not obvious that it should reach that, especially with all password/salt lengths.

I.e. your result is not unreasonable, though there may be room to push it further by a factor of ten or so if the hardware is problematic or the software poorly optimized.

(There is no public format definition for RAR formats before 5.0. The above is based on reading the proprietary, but freely available UnRAR source.)


How to properly AES encrypt a string, deriving the key from the same string?

My question: Unless there is a better approach, what would be the best strategy to strengthen the security, e.g. generating secure keys?

When you want to derive key for cipher, do use a KDF, ciphers require high-entropy key on all it's length to avoid potential weaknesses. Also, this way you avoid any problems with strings longer than your key size is.

But it appears that you don't need encryption at all. You can just get hash for every item. Then you can check list for duplicates, and request for original text, which then you can validate because you have hash. This is very same as encryption, except you can theoretically get collisions (but if you find collision in modern hash, that would be something special - nobody yet managed it).


What (Where) is the formal definition of Multiparty Computation?

The wikipedia page on Multiparty Computation (MPC) would be a good start.
It gives a good introduction to the topic, and it will mention the relation with Oblivious Transfer.

I would say that, in general,

  MPC studies the development of protocols that allow a set of $n$ parties $P_1,\ldots,P_n$, where each $P_i$ has a private input $x_i$, to compute a function $(z_1,\ldots,z_n) = f(x_1,\ldots,x_n)$ of these inputs in such a way that party $P_i$ only learns the value $z_i$.

If you want a more precise definition you would have to define, among other things, the terms I have written in bold.
Some of the definitions can be found in the book Secure Multiparty Computation and Secret Sharing by Ronald Cramer, Ivan Bjerre Damgård and Jesper Buus Nielsen.
Even though this book is for a particular type of MPC, which is Information-Theoretic MPC, most of the definitions apply for the general case.

Intuitively:

A party is just some computer program running some code. It is typically formalized as a Turing machine, but it's precised by an interactive Turing machine in order to model the networking.
A protocol is just a set of rules that the parties follows.
Think of it as the source code of the program itself.
It indicates the parties what to do at what times in order to achieve the desired result
A party only learns $z_i$ if anything it has learned from the protocol can be simulated from only its input $x_i$ and the output $z_i$.
This is much harder to precise, and it is typically done via de Universal Composability framework (read the book I referenced above, for instance).

Now, Oblivious Transfer (OT) is just a particular function to be computed, and an OT protocol is simply an MPC protocol that allows for secure computation of this function.
The function can be described as $f(b,(m_0,m_1)) = (m_b,\lambda)$, where $\lambda$ simply means that the corresponding party gets no output.

Moreover, although a protocol for OT is an MPC protocol that only works for this specific function, it can be proven that you can build a general purpose MPC protocol (i.e. a protocol for any function) from an OT protocol.
Therefore, in some sense, OT and MPC are "the same" (more precisely, they are equivalent, in some specific sense).


Is it possible take a piece of data in secret?

As Ricky Demer points out, you can take something blindly. It is called oblivious transfer. There are ways to add access control. See this paper as an example.


For any hash value, is there an infinite number of inputs that hash to it?

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by removing the length limitation and taking the message length modulo $2^{64}$.

It is not known, in the mathematical sense of that, that there is an infinite number of messages that hash to each possible value; that's both if we define possible value as one of the $2^{160}$ bitstrings of size 160 bits; or even if we define it as one of the (conceivably less than) $2^{160}$ bitstrings such that there exists a message that hashes to that value.

However, we expect that each of the $2^{160}$ bitstrings is the result of hashing an infinite number of messages.

Given the structure of SHA-1 (a Merkle-Damgård hash), this would follow from the plausible conjecture that modifying two consecutive message blocks except for the last 72 bits (of padding and length) is enough to reach any desired value. Or more precisely: that for any $I$ and $K$ of 160 bits, and any suffix $S$ of 72 bits, there exists $A$ of 512 bits and $B$ of 440 bits, such that $\mathcal F(\mathcal F(I,A),B\|S)=K$, where $\mathcal F$ is the compression function of SHA-1 (with first argument the 160-bit hash state, and second argument the 512-bit block input). This conjecture allows to explicitly construct $2^{160n}$ messages of $1024n+952$ bits hashing to any value $K$ (for $n=0$ we set $I$ to the initialization constants of SHA-1, and $S$ to $\text{0x80}$ followed by the length $952$ over 64 bits; we proceed by induction, postfixing previous messages with the former $S$, and setting the new $S$ to $\text{0x80}$ followed by $(1024n+952)\bmod2^{128}$ over 64 bits).

That conjecture seems extremely plausible is we model $\mathcal F$ as a random function of its inputs; or if we model the cipher that it uses internally as an ideal cipher, followed by addition modulo $2^{32}$ of each of the 5 words of input and output (an even better model of what SHA-1 is). The argument goes like: it is likely that for any 160-bit intermediary $J$ we can find $B$ allowing to reach any $K$ as $\mathcal F(J,B\|L)$, for we have $2^{440}$ choices of $B$ and only $2^{160}$ values of $K$ to cover, with the square of the later number much larger than the former. Even if there was some exceptions because $\mathcal F$ or its internal cipher is too regular, we have a large (arguably full or next to full) choice of $J$ by varying $A$, and that will help fully covering the possible $K$. Note: I fell more confident about this argument with belt and suspenders than I would be with a single round of $\mathcal F$.

Back to the actual definition of SHA-1 with limited input length, the above plausible conjecture would imply that more than $2^{(2^{61})}$ messages hash to any given value. That's practically infinite for all but a mathematician.


Does this guarantee a unique 32 bit Hash?

As far as I understand, the scheme is:

$$MD5(x) = a_1||a_2||a_3||a_4 \, \, \Longrightarrow \, \, H(x) = a_1 \oplus a_2 \oplus a_3 \oplus a_4,$$

with $a_i$ 4-byte/32-bit words.

Obviously you can't guarantee a unique 32-bit hash from an unbounded domain, due to the pidgeonhole principle. Neither can you make finding collisions infeasible, since $2^{16}$ MD5 invocations takes a few seconds if that.

If MD5 was an ideal 128-bit hash, it wouldn't matter whether you take the first 4 bytes, XOR the 32-bit words or anything else. All of them would be ideal 32-bit hashes. However, it isn't and you can find collisions in about $2^{33}$ operations. That doesn't directly lead to an attack on this, because it's slower than brute force, but it's possible it could be extended. There's a chance the XOR could make such an attack slightly harder or easier than truncation, but it really doesn't matter with a 32-bit hash since brute force is sufficient.

Assuming you don't let an attacker control the inputs (since that would be totally broken), the question isn't about the collision resistance, but pseudorandomness of MD5. MD5 is still thought to behave like a PRF in the sense that if the input strings are chosen "randomly", the output is uniformly random as well. (Which is why HMAC-MD5 is secure.) XOR doesn't affect that, so you should have the 32-bit hash behave like a PRF as well.

So, with inputs that aren't under the attacker's control, you should see collisions at the birthday bound. No sooner or later, other than what variance you expect with a 32-bit hash. However, there's no real benefit to the XOR, so you might as well just use the first 4-byte word.