Encryption for continuous, real-time data over an unreliable connection

On AES per packet: Generally it depends, but if you write there so few details, then I would bet you would implement it insecurely (no offense). There are several reasons:

You need to use a specific mode of operation, but you don't mention any. The mode of operation can have substantial impact on security.
You don't mention initialization vectors / nonces. Wrong handling of them (e.g., using a constant IV) can have bad impact on security, but the exact impact depends on mode of operation.
You don't mention any authentication. Not having any authentication can result in messages modified by attacker – for example, some modes of operation reflect bitflips in ciphertext to plaintext. Also, some other modes of operation can leak some data if used without authentication (see POODLE).
You don't mention any replay attack prevention. Without that, attacker can replay or reorder the messages.

I suggest not to implement it yourself and rather use something existing. DLTS seems to be designed for such case.

There are also some additional concerns that probably need to be handled per application:

In some realtime systems, you might want to have a special handling for delayed packets – some might be pretty outdated at the time of arrival and it might be bad to process them.
In some realtime systems, you might want to add a special reaction to situation when you receive no fresh data for some time, regardless it is accidental or due to an attack.


We use more complex encryption algorithms than XOR  with a random or pseudo-random keystream for a number of reasons:

In order to get a short secret key in symmetric encryption. XOR with a true random stream (One Time Pad) requires storing or/and transfering a secret keystream the size of the data to encipher, which is utterly impractical. Replacing the keystram with a pseudo-random stream (as outlined in the question) solves that key size problem, but see below.
In order to construct Cryptographically Secure Pseudo-Random Number Generators then used as suggested in the question. A weakness in a PRNG could become a weakness in the encryption scheme using its keystream, especially if that's by XOR. We know several demonstrably secure ways to turn a secure block cipher into a CSPRNG, that are reasonably efficient, and (thus) popular.
In order to get direct access to encrypted data. Imagine a large movie stored encrypted as proposed in the question. In order to start viewing it in the middle, we have to run the pseudo-random generator from the start of the file. That's solved by encryption using a block cipher (such as AES) in most common modes, including CTR/CBC/OFB/CFB. For example, AES-CTR does as in the question, with the pseudo-random stream obtained by enciphering a counter (starting from an Initial Value usually stored at start of file), so that we can produce the keystream for any position by adding the IV and the (appropriately scaled) file index, and enciphering the counter values startign from there with AES, yielding the keystream, which allows decryption starting at the desired point.
In order to also get assurance of data integrity and origin, which often turns out to be at least as needed as data confidentiality. Even if we assume a large secret keystream, we need something slightly more complex than XOR with the keystream (e.g. universal hashing) in order to ensure that an adversary did not mess-up with the data (e.g. change "pay \$100" to "pay \$900").
In order to get asymmetric encryption, that is the capability to encipher without needing anything secret (beyond the data to encipher) on the side that enciphers.


Why isn't the maximum security of triple DES 48 * 2 vs 56 * 2?

A meet-in-the-middle attack basically halves the number of bits of the total key size, rounding up. So 3 and 4 both have 2x security and 5 and 6 block cipher encrypts provide 3x security of the original cipher. I think that this is the main misunderstanding of meet-in-the-middle attacks.

The DES cipher itself is protected against meet-in-the-middle attacks, mainly due to how the key is expanded. Note that the key material is related and that there are many rounds within a single DES block encrypt, which makes it different from how block ciphers can be stacked on top of each other. You can see a question about meet in the middle attacks within block ciphers  here (note who is asking the question).
So it isn't that this isn't an active field of crypt-analysis. Actually, many amateur block ciphers will probably fail against the meet-in-the-middle attacks and are thus rendered insecure (assuming that they specify e.g. 128 bit security for a 128 bit key).


final_exp_gadget<>() of libsnark could be a practical example to tune for DLP.
The idea is, "final exponentiation" is a part of Ate pairing, that is verified as a part of check_e_equals_e_gadget<>(), which stands for Groth16 verification equation.


If PRESENT had different permutations s would that protect it against Statistical Saturation Attack?

For your first question, there are two permutations in PRESENT that we could consider changing:

The nonlinear layer, i.e. a parallel application of an S-box.
The linear layer, which is a bitwise permutation.

The statistical saturation attack is not really based on the properties of the S-box, so one might not expect that replacing it helps a lot. However, the S-boxes do contribute to the overall diffusion of the block cipher, so the choice of the S-box does have an impact. The paper that you mentioned contains a detailed discussion of the influence of the S-box in Section 4 (starting on page 12). They conclude that

  It is noticeable that the PRESENT S-box is among the worst possible
  choices to resist our attack.

This is very clear from Figure 14 in Appendix D.

A better countermeasure would be to replace the bitwise permutation, as it is the cause of the vulnerability. The linear layer of PRESENT leads to other attacks as well, in particular linear cryptanalysis. For instance, Cho's Linear Cryptanalysis of Reduced-Round PRESENT is based on the limited diffusion provided by this bitwise permutation in combination with the existence of one-bit trails for the S-boxes.

The paper proposing the recent cipher GIFT contains some ideas on how to choose a good permutation in a PRESENT-like block cipher. They don't revisit the statistical saturation attack though.

For your second question (can we use less than 31 rounds), it depends a lot on what the new S-box and linear layer are. The statistical saturation attack can be stretched up to 24 rounds, see these errata and improvements for the correct complexities. Multivariate linear cryptanalysis can reach at most 26 or (maybe) 27 rounds. Replacing the bitwise permutation with a much stronger linear layer could prevent both of these attacks, but it's not possible to rule out other attacks (especially if we don't know what the replacement is).


how can identify which cryptanalysis is used ( Indistinguishability cryptanalysis against classical ciphers)

Do frequency analysis by counting the number of occurrences of each letter.
For a transposition cipher, the counts will be similar to the underlying language (e.g. E T A O N will be common in English).
For a substitution cipher there will be the same distribution of counts as the underlying language, but the high counts will match with the wrong letters.
For Vigenere, the counts will be more uniform and closer to being equal.
If you have matching plaintext, the counts for transposition will be identical; the counts for substitution will be the same numbers in a different order; the counts for Vigenere will be very different.


Related-key attacks against Salsa20 and ChaCha

Perhaps the best evidence for the related-key security of Salsa20 is in the Rumba compression function proposed by the author:
$$
\mathrm{Rumba}(m_1, m_2, m_3, m_4) = f_1(m_1) \oplus f_2(m_2) \oplus f_3(m_3) \oplus f_4(m_4)\,,
$$
where $f_i$ is Salsa20 with a different initial constant for each variant, and each $m_i$ is 384-bit wide. Clearly, for the author to believe this construction would be secure it would require believing the permutation is secure against Salsa20 attackers who also control the key.

This belief was tested in the "New Features of Latin Dances" paper, which found collisions for 3 rounds in time $2^{79}$—much faster than generic methods. But 3 is a long way from 20, and so there does not seem to be much to fear.

Later, in an early version of a paper introducing SMT solvers to the differential cryptanalysis of ARX, Mouha and Preneel argued that there are no strong differential characteristics for 15 rounds of Salsa20, even in the related-key model. However, there are some subtle issues here, and this should be considered evidence but not proof that Salsa20 is immune to differential cryptanalysis.


Is it correct to concatenate (pseudo-)random byte values before testing them with the NIST suite or tools like dieharder?

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?
Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before?

Yes for both. The fact that others may have obtained (and removed) randomness from the source while it was sampled, or/and that the samples are grouped in some particular way for testing, does not prevent from testing what's obtained. And that can not cause a valid test to fail more often, assuming the source's full output is indistinguishable from random (including for said others trying to make the test pass, or fail).
On the other hand, those same facts could make the test become arbitrarily less capable of detecting some faults. As an extreme example, a source that always repeat each byte that it outputs might become indistinguishable from true random if we sub-sample its output, keeping every odd byte.

The actual underlying problem is how to examine seed values for randomness.

Dieharder or the NIST Statistical Test Suite alone can't give any assurance of that. At best, they can indicate a fail with high confidence, which saves from performing further work (beyond checking that the test was correctly performed/works). If they indicate pass, no other firm conclusion can be reached on that basis alone. It is needed to know how the seed values are generated, and that can't be determined by a test of the seed values.

As a proof that these tests can not validate the fitness for cryptographic purposes of a source of unknown build, consider a RNG with:

a real-time clock keeping UTC time in second, initializing 128-bit register at startup after a delay of 1 second
with the register then repeatedly encrypted using AES-256 and a key to produce the next register value, which concatenated 128-bit values form the bulk of the output, queried over a gigabit Ethernet interface.

This source will pass any black-box testing that does not reject a good generator, including tests scrutinizing power-on, as long as the test does not use AES-256 and the correct key.
But this source is disastrous from a cryptographic perspective. Given the key and when the black box was started, its output is predictable. Given the key and a fragment of a sequence, all the rest can be computed. Some party eating bytes from the source in the background can even decide what another party using the source will get!

As pointed by others, many statistical tests, including some of the DieHarder suite, require megabytes of input. The full Dieharder needs gigabytes.
However, in the context of a cryptographic RNG of proper structure, these tests requiring a lot of input are not needed. The tests that make sense are those on the unconditioned (or lightly conditioned) entropy source, used to seed a CSPRNG. The source is validated by tests which purpose is to ensure that it delivers some entropy. The CSPRNG is validated by examination of its design, and Known Answer Tests. Some monitoring in the RNG should detect a fault in the source and in this case prevent output. The combination might be checked by an extra test of the whole thing, but that's meaningful only if there is some assurance, obtained otherwise, that the overall structure really is the source seeding the CSPRNG, and being monitored.


Designing a protocol to record attendance to lectures

Facing the same problem in an undergraduate class of about seventy students, I know of someone who came up with the following simple and effective solution because signing a paper had proven to be an undependable method for recording attendance:

In front of one of the four assistant instructors, he had the students present their IDs at the front desk as they came in, and an AI actually checked the photo of each student prior to scanning.  Students were not allowed to scan themselves in, and he used an OpenOffice Calc spreadsheet to record their data. This made things reliable--the bar code reader populated the spreadsheet in front of an AI.  It also made it easy to record lateness.  Names were not recorded, only ID numbers, which the AIs did not know. He did not know anyone's ID number off the top of his head, but he could find out all of them.

For this to work in the way you wish, you would need to map each ID number to a new, class-specific number, and only let the certain people in the administration have access to a student's real ID number.

Or you could make an attendance card for each student in your class with a photo and bar code/ QR code, and use a good pseudo-random number generator to create their temporary, class-specific ID number.

Your most difficult parameter looks to be #3:

The teacher should not be able to know who attended the lessons and who didn't until the end of the term.

This is not realistic, even in a large class.  You are asking a teacher not to remember faces and not notice empty seats.

At the end of the semester when grading, he sorted out the numbers and names and assigned attendance grades, etc.  It worked, and it was fast. Come to think of it, you could use public-key cryptography to have the instructor(s) sign the completed attendance document, thereby giving you non-repudiation for that too.


Where to obtain a common/weak password list (black list)?

Well, you could just google it!  This is the top 100,000 broken passwords from the UK's National Cyber Security Centre (GCHQ).  It's probably trustworthy. Top password is 123456. Probably shouldn't use it then. That article is dated 21 April 2019, which is a while ago. Not sure when updates will happen, but again, more googling...
Your note could also refer to an internal list of compromises only known to a particular organisation. Companies try not to publicise such breaches if possible/legal, but clearly they happen so lists could be compiled.


Can AES be broken by factorization (using Quantum Period Finding)?

Two things:

Firstly, the paper is not talking about factorization at all; instead, it is using the Quantum Computer as a "constant-that-doesn't-change-the-output" algorithm (that is, find an $s$ such that $f(x) = f(x \oplus s)$ for all $x$) to break certain message authentication algorithms (which may just happen to use AES).

The paper notes that, with these specific message authentication algorithms, if you are able to find such a constant, that also gives you enough information to break the message authentication code.

Secondly, this is not actually a practical break.  They run their attack in a "Quantum Oracle" model, where the attacker is given an Oracle where he can submit superpositioned queries, and get a superpositioned response.  Now, in practice, this superposition state is extremely delicate; it would take rather complicated Quantum Error Correction logic to maintain it (which is actually a bit more than what we can actually implement just now).  It would be quite impossible to send such a query over the internet and hope to get the correct response.

What the attacker would have to do is take this Oracle and build it in his Quantum Computer (which would implement this complication Quantum Error Correction logic), and use the attack that way.  Which leads to the question: if the attacker has access to the actual implementation with the secret keys (so that he can reconstruct it within his quantum computer), why doesn't he just look inside for the keys?


PKCS#1, "the" RSA standard, describes how a signature should be encoded, and it is a sequence of bytes with big-endian unsigned encoding, always of the size of the modulus. This means that for a 2048-bit modulus, all signatures have length exactly 256 bytes, never more, never less.

PKCS#1 is the most widely used standard, but there are other standards in some areas which may decide otherwise. Mathematically, a RSA signature is an integer between $1$ and $N-1$, where $N$ is the modulus. In some protocols, there can be some wrapping around the signature, e.g. to indicate which algorithm was used, or to embed certificates. For instance, in CMS, a "signature" contains the RSA value itself, but also quite a lot of additional data, for a virtually unbounded total size (I have seen signatures of a size of several megabytes, due to inclusion of huge CRL).


AMD's implementation of RDRAND instruction

These circuits use an asynchronous counter that is ringing, and are sometimes combined with a seed from the unique processor ID (you blow these with e-fuses during test)

If you take 32 ring oscillators in parallel that each supply a single bit, you will see a random 32-bit value every time you sample.  The randomness introduced is due the Poisson process of charge arriving at different times across the channel of the device, and this is why ring oscillators are "noisy".  This is why do not need a seed, you just need a few moments that taken when the CPU resets to achieve electrical chaos.  I would probably even keep a few ground ties weak to substrate through the resistors to increase the charge distribution.

I also have seen an implementation of this were the a few inputs were then put into SHA-1 that was XOR'd with the processor ID, but just from the standpoint of physics, you could have just have the ring oscillators.  I assume this approach was used because it's outlined in a NIST spec.

addendum:

The most approachable discussion of this noise is probably this paper:

R. Sarpeshkar, T. Delbruck, and C. A. Mead, “White noise in MOS transistors and resistors,” IEEE Circuits and Devices Magazine, vol. 9, no. 6, pp. 23–29, 1993.


Can I use PGP to sign a message without providing cryptographic non-repudation?

Yes, there's an indirect way to perform what's asked with PGP and variants.

Draw a an asymmetric public/private key (of a type that can sign), protected by a passphrase. Publish the passphrase-protected private key. Discard the public key (it's in the private key anyway). Use the passphrase as you would use a symmetric key: share it by trusted means between sender and receiver (perhaps together with the passphrase-protected private key). Generate, transmit and verify a detached signature (sig file) of a file to integrity-protect as you would do for a MAC of the file.


Hash functions vs Stream Ciphers in terms of Speed

There is a lot of confusion in this question. Hash functions provide collision resistance. However, under a pretty reasonable assumption, they can be used to obtain a PRG or a PRF. Thus, hash functions and stream ciphers can be used to obtain a pseudorandom generator. This is true. (Although RC4 is broken and CANNOT be used for this purpose any more.)

Now, the question is: what is faster? A hash function, a stream cipher, a block cipher, and so on. The answer is very simple! It depends on the function in question and on the platform. If you have an AES-NI instruction set, then this is incredibly fast. It is also a very good option since its security is better studied than any stream cipher that hasn't yet been broken. Hash functions (like the SHA family) are actually pretty slow in comparison. Once Intel puts SHA-2 into hardware, then we'll have to see, but from what I understand it will be slower than AES. If you don't have AES-NI, then things like Salsa20 are a good option. However, my preference is always AES, and unless you really can't use it for some reason, that is always my recommendation.


Correctness of ideal protocol of MPC in presence of malicious adversary

If the honest parties have commitments to the malicious parties' inputs or [encapsulations generated by honest parties] of those inputs, then the function can be modified to check those.  Otherwise, the value computed by the trusted party "taking honest party inputs

and modified inputs of corrupted parties" by definition results in a correct output.


Learning to encrypt/encryption algorithms

Concerning "As a new programmer...":

Probably you don't know this yet, but as a rule of thumb: Do not use your self-implemented crypto for anything unless you are really an expert in the field. This might seem counter-intuitive for the outside, but anything else has to be considered insecure.

The reason for this is that for most aspects of programming and computer science the average case is the most important one. It is not too important if there is a very unlikely flaw in a system since it probably won't happen anyway. But in crypto, the attacker will exploit this flaw to break the system on purpose. Therefore, not the average case is important, but the worst case. For example, you can find statements like "the probability of the attacker to guess right is no more than $\frac{1}{2^n}$" (worst case estimation).

The above statement is not entirely true, but it depends on the abstraction layer: If you utilize standard implementations of encryption, hash functions, key exchange, TLS, etc... you can use those primitives in a high level protocol and most likely you are "secure".

But if you start writing your own crypto primitives, you will probably overlook something. Even worse, if you start using your primitive in a larger context, there is not only a small problem in a single function... you make the entire system insecure. Security is like a chain, and it breaks with the weakest link, not the "average strength".

Back on topic:

You can implement encryption schemes for practice or to learn something, but I advise heavily against using this.

For practice, this depends largely on your experience as a programmer. For the very start, you might want to consider using historical ciphers like Caesar, Vigenere in order to get comfortable with the principles (they are not secure, tho). If you want to have something more useful, you can implement a stream cipher (XOR cipher with some kind of random number generator). Some public key cryptosystems can be easily implemented, too. For example ElGamal encryption, plain RSA, DSA, etc. ... just stay away of elliptic curve crypto, unless you understand what those actually are.

For usage you might want to learn how to import and use standard crypto libraries, for example, "Cryptlib", "Bouncy Castle", "OpenSSL", etc. E.G. this is a list of libraries.


How does one calculate a primitive root for Diffie-Hellman?

In the general case, for proper security with Diffie-Hellman, we need a value $g$ such that the order of $g$ (the smallest integer $n \geq 1$ such that $g^n = 1 \mod p$) is a multiple of a large enough prime $q$. "Large enough" means "of length at least $2t$ bits if we target $t$-bit security". Since $n$ necessarily divides $p-1$, $q$ divides $p-1$.

We normally want to know $q$, so $q$ is generated first, then $p$. Namely, we create a random prime $q$ of size $2t$ bits, then we produce $p = qr+1$ for random values of $r$ until we hit a prime. This is what is done for generating DSA key parameters, which have the same structure than Diffie-Hellman key parameters (see the DSA standard). Note that producing a random prime $p$ would already yield a "large enough" $q$ with overwhelming probability (but we wound not know the value of $q$, only that it is very improbable that the largest prime factor of $p-1$ is smaller than $2t$ bits).

Then, to get the "generator" $g$, we can just use any random integer modulo $p$: the probability that $q$ is not a divisor of the order of a random non-zero integer modulo $p$ if $1/q$, i.e. so small that you will not hit it in practice (the overall security of Diffie-Hellman relies on the practical impossibility of obtaining events which are billions of times more probable than that). Nevertheless, some people get nervous in the face of probabilities, and will feel safer if we test the generator. The procedure then becomes: create a random integer $u$ modulo $p$ and compute $g = u^{(p-1)/q} \mod p$. If $g = 1$, then try again with a new random $u$ (this is the very improbable event that you will not get in practice); otherwise, it can easily be shown that $g$ has order exactly $q$, and thus is a good generator for Diffie-Hellman.

Another method is to get a very large $q$, i.e. generate $p$ such that $p = 2q+1$ and $q$ is prime. We then call $p$ a "strong prime". It can be seen that the order of a random non-zero integer $g$ modulo $p$ is either $1$, $2$, $q$ or $2q$; order $1$ is possibly only with $g=1$, and order $2$ is possible only with $g=p-1$. Any other integer modulo $p$ will be fine for Diffie-Hellman. In particular, you can use $g=2$ as generator, which can yield a bit of a computational speed-up.

But really, the fastest way to get $p$ and the generator is to abstain from generating them. There is no security issue with Diffie-Hellman (or DSA) if you reuse previously generated $p$, $q$ and $g$; several people can share these values for their respective key pairs and this does not weaken the system in any way. So you can pick up "standard" values, e.g. the ones described in RFC 2409 (section 6.2) or RFC 5114 (sections 2.1 to 2.3).


Is the concept of provably secure hash the same as entropy smoothing hash functions?

Ricky already gave the answer, but here are some additional details.

"Entropy smoothing" hash functions are randomness extractors. Extractors are functions that extract almost uniform bits from weak sources of entropy. In a way, they spread the min-entropy of the input source almost evenly over the (shorter) extracted source, hence the smoothing.

The Leftover Hash Lemma asserts that a strong randomness extractor can be constructed using a family of pairwise independent hash functions. So, if $\mathcal{H}$ in your statement were such a family, you get $(k, H_k(\delta)) \approx (k, h)$.


It happens that a line usually (not always) cuts three points in a elliptic curve by the Bezout theorem. This is the case for the points and the curve you are asking for.

So the sum of two points are defined like the inverse of the third point intercepted by the line that cut $P$ and $Q$ (let's name it $R$). So we need to find $-R$ because $P+Q=-R$ by definition (the inverse is calculated by multiplying the $y$ component of $R$ by $-1$).

The line equation that cuts $P$ and $Q$ has the form $y=ax+b$. So let's calculate $a$ (the slope) with:

$
a=\frac{5-4}{2+1}=\frac{1}{3}
$

To calculate b, we use the fact that we know the $x$ and $y$ values for $p(-1,4)$:

$
4=a*-1+b
$

Solving this equation we get $b=\frac{13}{3}$.
So, the equation line that cuts $P$ and $Q$ is $y=\frac{1}{3}x+\frac{13}{3}$.

The third point can be obtained by solving the next equation system (formed by the equations of the line and the curve):

$y=\frac{1}{3}x+\frac{13}{3}$

$y^2=x^3+17$

This system has three solutions (as expected):

$x=-1, y=4$ (this is the point $P(-1,4)$)

$x=2, y=5$ (this is the point $Q(2,5)$)

$x=-\frac{8}{9}, y=\frac{109}{27}$ (the point $R$)

So the sum of $P$ and $Q$ is $-R$, this is:

$P+Q=-R=(-\frac{8}{9}, -\frac{109}{27})$


All passwords are salted with the same salt.

Duplicate / reused passwords will show up because the resulting password hash is identical. Cracking the password database will become easier as all the passwords can be cracked at once using a specialized rainbow table or simple comparison against all the passwords in the database.

An attacker could also setup a website with the same salt and hope that users will repeat their passwords; in that case duplicates will show up even if the username is different.

There is still one advantage left for the salt: hacking multiple databases at the same time using rainbow tables or dictionary attacks is still thwarted (unless the salt is reused, e.g. when using "007" as salt, and other implementations do so as well).

  The application does not use salting, but end users choose their passwords by appending to them a (random) salt. We make the assumptions that these users are able to remember them, and that an adversary has access to both the identities of users and the salts that have been used in the associated passwords.

That depends on the quality of the salt; but given that the users should remember them they might as well use a longer, unique password. Because they are going to forget that salt, especially if it is specified as e.g. hexadecimals.

Using a unique (hash over a) username as salt is possible, but that means that the password must be refreshed if the username is ever taken; repetition of the password by the same user may show up. You should add a static "pepper" - a secret constant salt - to this kind of salt to make it unique for your specific database.


How difficult is it to check if a group element is in a sub group?

If the group $G$ is finite and cyclic (and hence Abelian), it has exactly one subgroup of order $s$, for each $s$ which divides the order of $G$.

Since any subgroup of a cyclic group is also cyclic and hence Abelian, you might easily implement the operation in $H$ that is the equivalent of modular exponentiation in $Z_n^*$.

If you also already know the order $s$ of $h$, you know that, because of associativity and commutativity, that $(h^s)^t = (h^t)^s = 1$ for any $t$. Hence, checking that $x \in H$ is just a question of checking that $x^s = 1$.


You could cheat and use different keys for each recipient. That would work assuming the recipients don't know each other (and cannot compare keys).

Mix networks are by design hard to trace so it depends on the network.

EDIT:
Sending a message to Bob implies Alice knows how to find Bob in the first place, or knows someone who knows where Bob is, without Bob having to directly reveal his location to Alice. The Tor network has implemented this through hidden services which guarantees that both Alice and Bob remain anonymous to each other. The webpage has some diagrams as well and explains how it works, but I won't go into much detail about it because your question isn't about Tor.

It is important to note that public key cryptography doesn't guarantee anonymity or privacy or protection from identification. It's not designed for it. It just protects a message. Tor has managed to do a decent job at protecting two parties who wish to talk to each other and is reasonably mature but mutual anonymity really depends on the (onion) network Alice and Bob are using - not on the PK scheme.


How does TLS 1.3 work with PQC signatures?

Not necessarily; this varies from signature scheme to signature scheme. In some lattice signature schemes (e.g. FALCON) it is important not to produce two signatures for the same private key and hash value. In the case of FALCON it is therefore specified that the message be randomly salted before hashing and signing (see section 2.2.2 of the FALCON submission). Others require that the message be hashed to a particular mathematical structure and so require more hash data from XOF variants such as the SHA3 SHAKE functions. The wide range of PQC proposals for signature schemes make it impractical to do a comprehensive treatment, but if there is a particular scheme of interest more can be said.


What is Phase space reconstruction attack on chaotic encryption algorithm?

In cryptography, "phase space reconstruction attack" seems used only in the field of cryptography based on chaotic systems, which itself is too often happy with vague arguments and definitions where math is due. Accordingly, this field is markedly underrepresented in cryptographic publications with a peer-review system that I trust.

We are told by the OP in comment:

  I am working on final year project where I am trying to improve the algorithm Image encryption using chaotic logistic map. Therefore I have no other option. I have to check whether my improvements can deter this attack or not.

Multiple alarm bells are ringing.

This article was published in Image and Vision Computing, a journal with "primary aim the provision of an effective medium of interchange for the results of high quality theoretical and applied research fundamental to all aspects of image interpretation and computer vision". That is, not cryptography.

Further, the article makes a most basic, serious, and common error in cryptography based on chaotic systems: it fails to consider the issue of number representation, numerical precision, and rounding, when it defines the iteration studied as:
$$\begin{align}X_{n+1}&=3.9999\,X_n(1-X_n)\\
Y_{n+1}&=3.9999\,Y_n(1-Y_n)\end{align}$$
The (same) iterator used for $X$ and $Y$ is the well-studied logistic map. It is indeed chaotic, thus small errors due to the approximate representation of real numbers using floating point matter immensely: even the approximate value after a few iterations depends non only on the starting point, but on which of internal format (there has been many) is used for number representation, and rounding rules. Results (including ciphertext, and difficulty of cryptanalysis) depend heavily on if computations are done with this or that spreadsheet, programming language, compiler, options...

The OP appears locked into a final year project starting from work easily identifiable (by one with a sound scientific background) as not proper cryptography.

Addition towards actually answering the question: the iterated $X$ and $Y$ have independent state variables, and are bound to become periodic (because there are finely many values for a state in whatever computer implementation is considered). Their period depends on floating point details, and can be quite small for some choices of parameters and starting value.

It follows that each of $X$ and $Y$ will ultimately (and in practice often quickly) be in a certain (but only indirectly observable) phase in its final cycle. I vaguely get that a phase space reconstruction attack tries finding the two phases, or some fixed relation between these. Such attacks might use that the cycle lengths often share a large GCD, or can even be equal; this is made plausible by the fact that the same iterator is used for independent $X$ and $Y$.


Proof of $\sqrt{\pi/2}$ in birthday paradox?

The paper you are looking for is:

"Random Mapping Statistics" by Flajolet and Odlyzko, first published in  Advances in Cryptology — EUROCRYPT ’89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434.

It is freely available via SpringerLink and via Archives-Ouvertes (PDF).

The relevant statistic you are looking for is probably the rho-length, which specifies the specifies the average length of a cycle to be $\sqrt{\pi n/2}$ where $n=2^k$ in your case.

The abstract reads as:

  Random mappings from a finite set into itself are either a heuristic
  or an exact model for a variety of applications in random number
  generation, computational number theory, cryptography, and the
  analysis of algorithms at large. This paper introduces a general
  framework in which the analysis of about twenty characteristic
  parameters of random mappings is carried out: These parameters are
  studied systematically through the use of generating functions and
  singularity analysis. In particular, an open problem of Knuth is
  solved, namely that of finding the expected diameter of a random
  mapping. The same approach is applicable to a larger class of discrete
  combinatorial models and possibilities of automated analysis using
  symbolic manipulation systems (“computer algebra”) are also briefly
  discussed.


Difference between Key Scheduling and Key Generation?

Key generation is just a process

Anything is "just a process", executing any algorithm is "just a process". So lets ignore this part of the sentence as it doesn't make sense.

  while key scheduling is about the calculation of key in the algorithm.

That's right. If the algorithm requires a key in a different form, e.g. expanded from the original form, then the key schedule is the part of the algorithm that performs that calculation.

However, this argument is true when we're talking in the context of a block cipher. Key schedule could mean other things in other contexts.

  So now the sentence reads "Means (the process or procedure that is taking place in generating a key) is called key generation, am I right here?".

That sentence is self-evident. However, as long as "generation" is not further clarified, it carries no weight.

  Moreover, what we will be called if we calculate a key using any method in our algorithm

That depends if we're still talking in the context of a block cipher I  suppose. If you're deterministically transforming your key within your algorithm then I suppose you can call it a key schedule. You can also call it something else; it is your algorithm after all.

  Just for example say that I calculate a key using different chaotic equations. Combine these equations in a particular way and generate a final key.

If you do that deterministically and within your algorithm then nobody would raise an eyebrow if you call it a key schedule. It would help if your algorithm would be a block cipher.

They would raise an eyebrow if you try and use it to increase the key strength or if the method takes lots of time, because that is not what key schedules are generally about.

  Is it will be key scheduling or key generation?

Key generation supposes randomness, and randomness supposes some source of entropy. If no source of randomness is given then we can confidentially say that it is not key generation.

If it is a key schedule is already discussed above. There are other options such as key establishment. However, if there is a single key as input, and if the supposed key schedule is happening within your algorithm, then it makes sense to call it a key schedule.


It is my understanding that a KDF adds entropy, whereas a hash loses information.

Password Based KDFs can be seen as hash functions (or families of hash functions, depending on your definition), just ones with a lot of complexity. It is sometimes said that they "add entropy" but that usually means either

they combine entropy from a salt into the password hash (which you can do with any hash function), or
they make the password more computationally difficult to crack as if it had more entropy (also called computational entropy).

PBKDFs and hashes are irreversible; meaning that it is impossible to find a password without performing a brute force or dictionary attack. PBKDF's make it computationally harder to perform a brute force search and the salt makes it impossible to find matching passwords within a database.

Both PBKDFs and hashes "lose information" in the sense that their image (output) is smaller than their input domain. That does not make them stronger, however, since if two passwords give the same output hash, either can be used as authentication.

So using a hash after a KDF is at best redundant and can lead to less security through e.g. increased collisions.


Why do stream ciphers like A5/1 and ZUC have "frames"?

What is the rationale behind these "frames" and why not just go for full random access if they want this?

That's because they're used in mobile communications.  There, packets can easily be dropped in transit (e.g. by a bit of electrical noise that just happens to come in at the wrong time); possibly with the receiver not even knowing that he missed one.

Because of this, it is necessary to design our crypto system to be able to decrypt even if packets are missing; using a system that can decrypt only if it has successfully received the previous packets just doesn't work.  One approach to do this is to put in a frame number; by using the frame number, the decryptor can work even if he missed some packets.

Now, you might think that we might also try to make the system reliable, by having the sender retransmit packets that the receiver didn't get (just like TLS does).  This really doesn't work out for voice communications; not only does it consume extra bandwidth (which is precious), live voice is time sensitive; if the next audio segment does come in late, the receiver can't do anything with it, and so there's no point in retransmitting it.

As for why they use serial numbers, rather than another approach (e.g. a random nonce), serial numbers are needed to tell the receiver when this segment of the voice should be replayed, and so voice communications have serial numbers in there anyways; using the same thing for two different purposes reduces on the bandwidth used (and, as I said, that's a major concern for wireless).


There is a generalisation of the Diffie-Hellman problem to multi-linear groups known as the multi-linear Diffie-Hellman problem (MDHP, see this paper for example). Specifically, for a group $G_1$ endowed with an $n$-multi-linear map $e$ to a group $G_2$ the MDHP is: given $g, g^{a_1}, g^{a_2},\ldots, g^{a_{n+1}}\in G_1$ compute $e(g,g,\ldots,g)^{a_1a_2\cdots a_{n+1}}\in G_2$.
Your problem is clearly no harder than the MDHP for $n=2$ (take $a_1=a$, $a_2=b$, $a_3=b$), and if we can take square roots in either $G_1$ or $G_2$ then a solution to your problem solves MDHP with $n=2$.
To turn your problem into a 2DHP solver in the case where we can take square roots in $G_1$, $a=a_1$ and let $g^{b_1}=g^{a_2}g^{a_3/2}$ so that $b_1=a_2+a_3/2$ and $g^{b_2}=g^{a_2/2}/g^{a_3/2}$ so that $b_2=a_2/2-a_3/2$, then
$$e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}=e(g,g)^{a_1a_2a_3}.$$
Likewise if we can take square roots in $G_2$ let $b_1=a_2+a_3$ and $b_2=a_2-a_3$, then
$$\left(e(g,g)^{ab_1^2}/e(g,g)^{ab_2^2}\right)^{1/4}=e(g,g)^{a_1a_2a_3}.$$
Note that square roots are easy to take in cyclic groups of known odd order, which covers a great deal of cryptographic applications.


Can future Bitcoin hashes be considered a good source to generate random numbers?

As Bonneau et al. showed a Bitcoin block header has high min-entropy, approximately 68 bits. So, in theory you could extract randomness for your protocol or application from Bitcoin block headers, but bear in mind that blockchain's entropy is malleable as shown by Pierrot et al.

For example, if you run a lottery whose randomness is extracted from the Bitcoin blockchain, a miner could interfere with this randomness by withholding blocks whose entropy is not profitable for her. She might want to do this, if she is participating in the lottery and the prize of the lottery is larger than the block reward.

To deter such an attack you might want to use verifiable delay functions(VDF). VDFs make impossible to learn the randomness derived from the block before some time-out (say 1 hour), since it requires sequential work to compute, therefore massive parallelization does not help here. Furthermore once the output of the VDF function is calculated it is easy to verify the computation given a small proof. By applying VDFs even the miner does not know the output of the VDF before the time-out. Therefore there would be no more financial incentive for the miner not to publish her block, since she would forfeit her block reward.


X.509 CSR: Why does CA remove signature?

If the CA issued something with a CSR as the dominant part of the To-Be-Signed field, it wouldn't be a X.509 certificate and hardly any existing software would know what to do with it. I guess the original CSR could be added as an extension, though.

Therefore, I suppose you are really asking why the X.509 certificate format wasn't originally specified to include the signatures of both the subject and issuer. I guess the reason was that if a PKI application trusts a specific CA, then that application trusts that the CA adds correct information (pairing a subject with a public key) in all of the certificate fields before issuing it. Adding the signature of the subject wouldn't add anything security-wise.


Is there a way to sign a message without being allowed to see it?

Generally hashing is part of the signature generation. You can use an additional hash or perform the hashing beforehand (splitting the signature generation process), and then only present the hash to the signer. If the message is complex enough then the one-way-hash function hides the message so it cannot be guessed.

You can always include a large enough (128 bit or so) random value with the message so it is impossible to guess the input to the hash value. Of course the receiver has to receive the message and the random value to verify the signature.

A much bigger problem is to make sure that the signer signs the actual message displayed on screen, and not a different hash. So the normal use case of a signature is actually harder to accomplish than your specific task to hide the message.


Relation between $N = P \times Q$, and $\Phi(N)$

What does the order of $U(N)$ has to do with RSA key generation?

The usual notation is $\Bbb Z_N^*$ for the multiplicative group modulo $N$, that the question names $U(N)$, and $\Phi(N)$ or equivalently $\varphi(N)$ for its order (number of elements), as given by Euler's totient function.

$\forall x\in\Bbb Z_N^*$, it holds $x^{\Phi(N)}\equiv1\pmod N$. This implies:
$$\forall x\in\Bbb Z_N^*,\ \forall k\in\Bbb N,\ \text{ it holds }\ x^{(k\,\Phi(N)+1)}\equiv x\pmod N\tag{1}\label{eq1}$$

We want the RSA encryption exponent $e$ and decryption exponent $d$ (both strictly positive integers) to be such that textbook RSA encryption of a plaintext $m$ followed by decryption consistently returns the original plaintext. That is, we want that $\forall m\in[0,N)$, it holds $((m^e)\bmod N)^d\bmod N=m$. We can write this goal as:
$$\forall m\in[0,N),\ \text{ it holds }\ m^{(e\,d)}\bmod N=m\tag{2}\label{eq2}$$

We can now see what $\Phi(N)$ has to do with RSA key generation: if
$$e\,d\equiv 1\bmod\Phi(N)\tag{3}\label{eq3}$$
then by definition of that, and given that $e$ and $d$ are strictly positive integers, $\exists k\in N$ such that $e\,d=k\,\Phi(N)+1$, and we nearly can use $\eqref{eq1}$ to prove that $\eqref{eq2}$ holds. The one gap is that we only prove the weaker
$$\forall m\in[0,N),\ \text{ if }\ \gcd(m,N)=1\ \text{ then }\ m^{(e\,d)}\bmod N=m\tag{2'}\label{eq2'}$$

We have proven that condition $\eqref{eq3}$ is sufficient to insure that textbook RSA encryption of a plaintext $m$ followed by decryption returns the original plaintext, at least when $\gcd(m,N)=1$. Since $N$ is the product of large primes, $\gcd(m,N)=1$ holds for most $m$.

Further, under the extra condition that $N$ is squarefree (including $ N=p\,q$ with $p$ and $q$ distinct primes), it can be proven that for all $m$ textbook RSA encryption followed by decryption returns the original plaintext.

Otherwise said: one way to see RSA is as working with message and ciphertext in the group $(\Bbb Z_N^*,*)$, but that restricts the message space. It can be extended to $(\Bbb Z_N,*)$ when $N$ is squarefree, that is when $N$ is not divisible by the square of any prime.

We first prove that $\eqref{eq3}$ implies that $m^{(ed)}-m\equiv0\pmod{p_i}$ for each prime $p_i$ dividing $N$, by treating separately the case $m\equiv 0\pmod{p_i}$. The integer $m^{(ed)}-m$ is thus divisible by each $p_i$, thus by their product, which is $N$ when $N$ is squarefree, thus $m^{(ed)}-m\equiv0\pmod N$.

Notice that the condition $\eqref{eq3}$ is sufficient, but not necessary. For a necessary and sufficient condition, we want
$$e\,d\equiv 1\bmod\lambda(N)\tag{3'}\label{eq3'}$$
where $\lambda$ is the Carmichael function.

Notations:

$\forall$ is read "for all". $\in$ is read "in". $\exists$ is read "exists".
$\Bbb N$ is the set of natural numbers: $\Bbb N=\{0,1,2,3,4,5,\ldots\}$.
$\Bbb P$ is the subset of $\Bbb N$ consisting of primes: $\Bbb P=\{2,3,5,7,11,\ldots\}$.
$\Bbb Z$ is the set of (signed) integers: $\Bbb Z=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$.
$(\Bbb Z,+)$ is a group.
$x\equiv y\pmod n$ is read "$x$ is equivalent to $y$ modulo $n$".
It means that $n$ exactly divides $x-y$ (for $n$ a strictly positive integer).
Alternative notations are $x\equiv y\ \ [n]$ or $x=y\pmod n$ or $x=y\ \ [n]$.
$x=y\bmod n$ is read "$x$ is set to $y$ modulo $n$" or "$x$ equals $y$ modulo $n$".
It means that (after the setting, if any) $0\le x<n$ and $x\equiv y\pmod n$ (see above for the meaning).
When $y\ge0$, the quantity $y\bmod n$ is the remainder of the Euclidean division of $y$ by $n$. The quantity $y\bmod n$ is $0$ when $n$ divides $y$ (and the C programmer writesx = y % n for a computation orx == y % n for a test). When $y<0$, we can compute $y\bmod n$ as $n-1-((-y-1)\bmod n)$.
Note: Textbook RSA encryption and decryption reduce their result $\bmod N$, ensuring that the ciphertext and the deciphered plaintext are in $[0,N)$.
$\Bbb Z_n$ is the finite set of integers modulo $n$. That is, the elements of $\Bbb Z$ equivalent modulo $n$ are regrouped into a single element of $\Bbb Z_n$. Thus $\Bbb Z_n$ has $n$ elements.
$(\Bbb Z_n,+)$ is a group. With multiplication noted $*$ when not omitted, it becomes the ring $(\Bbb Z_n,+,*)$.
When the modulo $n$ is prime, $(\Bbb Z_n,+,*)$ is a field, because all elements except $0$ have a multiplicative inverse. As practice of notation: $\forall p\in\Bbb P$, $\forall x\in\Bbb Z_p$, if $x\ne0$ then $\exists y\in\Bbb Z_p$ such that $x*y=1\pmod p$ (also noted $x\,y=1\pmod p$ as a shortcut).
$\Bbb Z_n^*$ is the set of the elements of $\Bbb Z_n$ that have an inverse under multiplication, that is the set of $x$ with $n$ and $x$ having no common positive divisor beyond $1$, that is $\gcd(x,n)=1$.
$(\Bbb Z_n^*,*)$ is a group including when $n$ is not prime. It has $\Phi(n)$ elements.


$(\epsilon, \delta)$-differential privacy: main motivation of $\delta$

I help implement and ship anonymization strategies based on differential privacy in a large tech company. In my experience, the $\delta$ is mainly used for two reasons.

Partition selection: when computing histograms on an unbounded space, you can threshold the results (or do smarter things) and, at the cost of a non-zero $\delta$, avoid having to specify the full list of partitions in advance>.
Gaussian noise: since Gaussian is based on the $L_2$ sensitivity, it is very convenient to use when adding noise to a lot of metrics at once; if a single user can influence $k$ metrics, the noise needs to be scaled by $\sqrt{k}$ instead of $k$ with Laplace noise$^1$. But Gaussian noise doesn't give you pure $\varepsilon$-DP, you have to have a non-zero $\delta$.

Gaussian noise is particularly used for machine learning use cases. In such contexts, you also often want to use results on amplification by sampling, which also require a non-zero $\delta$.


If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Is that backtracking-resistant?

No, as mentioned in the comments, if the PRF itself can be inverted when you know the key, the PRG is not backtracking resistant.

  I thought it would be backtracking resistant because if we compromise the internal state of the PRG at time $t+1$ (meaning the adversary gets $k$ and $B_{i+1}$), then we can't find any of the previous blocks $B_i$ (for $i < t+1$), since the PRF is hard to invert.

Being hard to invert when the key is known is not a required property of a PRF and many practical PRF constructions (like block ciphers) lack it.

  Apparently it's not backtracking-resistant because the key isn't being changed, whereas other PRGs such as HMAC-DRBG are, because they update the key.

Indeed. If you overwrite the key with data generated using the old key, there is no way to backtrack unless the PRF is invertible (to state and key) by those without the (old) key.


Can anyone briefly explain the 'theta step' of compression box in SHA3?

Can you tell me the 'theta' step of compression box

Keccak/SHA3 has no compression function, the inner function is a permutation.

  In this step all the indices should be taken modulo 5.

Yes that is correct.

  Do we have have to rotate it after taking mod 5 ??
  And C[X-1] is left rotate or just putting the values of x as 0,1,2,3,4 and then taking mod 5.

C is a 64-bit temporary value, as is D. The index is done mod 5, not the value. X-1 mod 5 is the same as X+4 mod 5 for the index, addition is less likely to cause problems in code, and is generally easier to read, but is listed as subtraction in the specification for reasons which I hope are obvious.

  And ROTC[X+1,1] is right circular rotation by 1 bit after taking mod 5, right??

Actually it is a left rotation on the 64-bit value by 1 bit. This is because the first bit is considered the least significant, so moving it by 1 bit to the next significant location is a left rotation when the least significant bit is on the right end of the value in memory.

If we look at theta without any loops, it looks like this:

C[0] = A[0,0] xor A[0,1] xor A[0,2] xor A[0,3] xor A[0,4];
C[1] = A[1,0] xor A[1,1] xor A[1,2] xor A[1,3] xor A[1,4];
C[2] = A[2,0] xor A[2,1] xor A[2,2] xor A[2,3] xor A[2,4];
C[3] = A[3,0] xor A[3,1] xor A[3,2] xor A[3,3] xor A[3,4];
C[4] = A[4,0] xor A[4,1] xor A[4,2] xor A[4,3] xor A[4,4];

D[0] = C[4] xor (C[1] <<< 1);
D[1] = C[0] xor (C[2] <<< 1);
D[2] = C[1] xor (C[3] <<< 1);
D[3] = C[2] xor (C[4] <<< 1);
D[4] = C[3] xor (C[0] <<< 1);

A[0,0] = A[0,0] xor D[0]; A[0,1] = A[0,1] xor D[0]; A[0,2] = A[0,2] xor D[0];
A[0,3] = A[0,3] xor D[0]; A[0,4] = A[0,4] xor D[0];
A[1,0] = A[1,0] xor D[1]; A[1,1] = A[1,1] xor D[1]; A[1,2] = A[1,2] xor D[1];
A[1,3] = A[1,3] xor D[1]; A[1,4] = A[1,4] xor D[1];
A[2,0] = A[2,0] xor D[2]; A[2,1] = A[2,1] xor D[2]; A[2,2] = A[2,2] xor D[2];
A[2,3] = A[2,3] xor D[2]; A[2,4] = A[2,4] xor D[2];
A[3,0] = A[3,0] xor D[3]; A[3,1] = A[3,1] xor D[3]; A[3,2] = A[3,2] xor D[3];
A[3,3] = A[3,3] xor D[3]; A[3,4] = A[3,4] xor D[3];
A[4,0] = A[4,0] xor D[4]; A[4,1] = A[4,1] xor D[4]; A[4,2] = A[4,2] xor D[4];
A[4,3] = A[4,3] xor D[4]; A[4,4] = A[4,4] xor D[4];

Where A[x,y] is one of the lanes of the state with row index 'x' and column index 'y', and '<<<' is a left rotation of the value to the left by the bits to the right.


Homomorphic encryption diagram and trouble about a paper

The author starts talking about multiples of $p$, because he wants to talk about the problem of find a $gcd$ (great common divisor) of a list of numbers (in this case, the $gcd$ is the secret $p$). He is somehow trying to make you understand why we cannot encrypt the binary messages $m \in \{0, 1\}$ by simply adding them to $q_i p$.

It means it would be insecure to use $qp + m$ as an encryption of a bit $m$, because encrypting a lot of bits $m_1, m_2, ..., m_N$ as $q_1p + m_1, q_2p + m_2, ..., q_Np + m_N$ would give the attacker a chance to recover the secret key $p$ from this list of encrypted values.

Therefore, to guarantee the security of the encryption process, we add a small noise. And to guarantee that the decryption will work, we chose this noise to be even, this is why we pick a small value $r$ and use $qp + 2r + m$ as the encryption of $m$.

Thus, the noise is introduced on the encryption. But, when we add or multiply two ciphertexts, we generate a third ciphertext whose noise is bigger than the noise of those two, so, we may say that the noise is also introduced when we operate over the ciphertexts.

And answering your comment: no, the sender does not choose the value of $2r$. It must be a random value. The only thing known is the interval in which the values of $r$ are sampled from and that interval is defined by the parameters that the sender chooses for the scheme (of course, following the restrictions that those parameters must respect).


Is the 64-bit blocksize a fatal issue when encrypting TBs of data with Blowfish CBC?

I didn't find anything about the exact way Crashplan encrypts files, only that it uses Blowfish in CBC mode. The block size of Blowfish is 64 bit, so there are $2^{64}$ different input blocks and the same number of output blocks. All in all $147573953$ terabytes of different output data. The problem with this is the birthday attack. Summarized it says that the problems with too much encrypted data (for CBC mode) start at ca. $\sqrt{2^{n}} = 2^{\frac{n}{2}}$ (n denotes the block size in bit). For Blowfish we get approximate 34 gigabyte. You'r mentioned "TBs of data" are much more than this.
The accepted answer from "poncho" to the question "Importance of block size in CBC mode" shows why it is no good idea to encrypt much more than the mentioned limit with a single key. It would be a good idea to change the algorithm to a higher block size variant or change the key after ca. 34 gigabyte or even less.

To analyse the ciphertext of Crashplan you have to know how the program saves the encrypted data. Try to convert the saved file into the original output blocks of Blowfish and then look for equal blocks. As soon as you find two equal blocks you can use the attack in the answer of poncho mentioned earlier. If you know the plaintext block of one of the block (due to some patterns or something else) you can calculate the value of the other block.

How bad is this attack? Well, the attacker has to have good luck with finding equal blocks. The bigger the ciphertext, the higher the probability for equal blocks. After that the attacker has to know some patterns of the plaintext. Many identical or just similar files (like many pictures saved in PNG format) can help the attacker to exploit patterns. And that's only for the hardest attack someone could use, a Ciphertext-only attack (the enemy only knows the ciphertext, but nothing concrete about the plaintext). If the attacker has the ability to save his or her own files in your backup (like a employee maybe could do it) there's no way to prevent him or her from getting special patterns into your plaintext.

There's no publicly known way to break Blowfish. Even if your key is a weak key (or will be hashed into a weak key) it won't harm the encryption in any known way. The mentioned attacks only work for a reduced-round Blowfish.


Can a hash of the original plain text file be used to brute force an encrypted copy?

It depends on the contents of your files. If the contents has high entropy and is unpredictable then you're probably safe.

However, if the contents is a password or a pin number, then brute forcing it should be trivial, it is for this reason that we use slow hashing.

Another scenario might be if the contents had a value which was commonly known (ie, a pirated movie). If the hash of that file is common knowledge, then so is the contents of your encrypted file.

To err on the side of caution, it's probably better to ensure the integrity of your file with a HMAC or Authenticated Encryption. You might want to read this thread.


What's the state of the attack to get the first pre-image on MD4?

The latest I know about is indeed "MD4 is Not One-Way." by Gaëtan Leurent (PDF) FSE 2008. Some of the more interesting and more recent publications to check on are "Advanced Meet-in-the-Middle Preimage Attacks: First Results on Full Tiger, and Improved Results on MD4 and SHA-2", Jian Guo/San Ling/Christian Rechberger/Huaxiong Wang, 2010 (PDF) and the paper Henrick Hellström mentioned in his comment. I don't think you'll find any more recent and/or note-worthy discoveries.

In 2011 there was RFC 6150 (http://tools.ietf.org/html/rfc6150) which stated that MD4 aka RFC 1320 (http://tools.ietf.org/html/rfc1320) is "historic"; meaning: "obsolete". I guess, due to the now "historic" status of MD4, there won't be too much interest to expand further on the issue.


The attachments are processed as follows (source is the WhatsApp's White Paper);
First time of the attachment is sent

The sender generates a 32-byte random AES-256 key, $k_1$, and another random 32-byte key $k_2$ for $\operatorname{HMAC-SHA256}$
Encrypts the attachment $a$ with this key $c_a = \operatorname{AES-CBC-256}(k_1,a)$ and append the MAC of the $c_a = \operatorname{HMAC-SHA256}(k_2)$ to it.
The sender uploads this to the server in a blob store.
The sender encrypts the $k_1,k_2$, and SHA256 hash of the encrypted blob and URL of the blob to the receiver.
The receiver decrypts the message, receives the encrypted blob, verifies the SHA256 of it, verifies the MAC then decrypts it.

This is a media caching technique.
The attachment is forwarded
The receiver wants to forward the message;

Encrypt the URL and the key $k_1,k_2$, and SHA256 hash of the attachment that is received from the sender and forwards to someone else.

How can Whatsapp identify forwarded attachments

Simply add a "forwarded" tag into the message that contains the  $k_1,k_2$, and SHA25 of the attachment. Even forwarding has a counter to limit the fan out and WhatsApp doesn't know about it.

So do they hash the attachment in the client and store the hash?  So they would know what attachments I forwarded and when?

Not because of it, they don't the internal of the messages, however, the blob has stored in the WhatsApp server contains enough information to execute a traffic analysis if they want to execute.

Store this information; who uploaded the blob; when the blob is uploaded.
Store who wants to access this blob and when.

Now, the attacker can make graphs.
This is traffic analysis doesn't expose the message, however, if one of the receivers is breached the circulated attachment can give information about others.


Is XChaCha20-Poly1305 nonce misuse-resistant?

The documentation on libsodium AEAD constructions provides more details.

Namely, it lists Hk(random ‖ m) as a way to compute a synthetic XChaCha20 nonce. Even if random is not unique, the nonce is unlikely to be the same for different messages.

Even more relevant are the sections on nonce-misuse resistance and short nonces.

Note that like all other nonce-misuse resistance schemes, this requires two passes over the data.


How far into the future is AES considered secure?

NIST doesn't make recommendations based on just the cipher alone. NIST SP 800-57 Part 1 includes some discussion of this. Section 5.2 (on page 44) explains rationale for having "cryptoperiods". They list many factors affecting long term security, with an emphasis on key exposure. It's not as simple as guessing the security of AES because AES is just one piece of a larger implementation, with many avenues for key exposure.

If you're looking for a number for how long to keep using a symmetric data encryption key, they say the following on page 50:

  A maximum recipient usage period of 3 years beyond the end of the
  originator usage period is recommended

This is not because they think AES is going to be practically broken in 3 years; it's because it's difficult to keep entire systems secure long term, and rotating the key periodically is a good idea.  For your use case,  I think the suggestion to change the key every 3 years is reasonable.

Now, it's very hard to give a direct answer to your question about AES itself. It's a very heavily studied cipher and currently the best known attacks are completely impractical. That's the best we can say about any cipher. Nobody knows what kind of attacks will be available 30 years from now. Some may argue for a 192 or 256 bit key length due to the threat posed by quantum computers implementing Grover's algorithm, but this is not currently feasible with any known QC and speculating on when it will become so is probably impossible.


How can the 'randomness' of a finite sample of binary keys from a finite key space be estimated?

There are a few things to notice here:

any tested sequence is finite by definition, we cannot run tests on infinite sequences;
the size of the output is interesting, but if it is sufficiently random then the concatenation of the 20 bit sequences should also be random;
we cannot say for certain that a sequence is truly random, as many algorithms can generate output that seems random, but isn't - like a part of Pi from a particular offset;
peculiarities/bias/inter-bit-dependencies are not acceptable for key generation.

Great, that out of the way, let's advance to the answers:

the die-harder tests and any other tests seem fine for your particular problem;
the fact that you generate 20 bits at a time is not a particular issue, as long as it is random;
you should understand the properties of the random number generator and test to see if it is supposed to be random given those properties - basically you cannot and should not test for randomness without description of the RNG itself;
if you are afraid that your results are biased then you should at least whiten the generated stream and / or use it as input to a Deterministic Random Bit Generator (DRBG or CSPRNG).

As for (4), it seems you already assume that your protocol takes care of possible bias ( although you also talk about using the randomness as key data). In that case I would try and prove that the bias does not pose a problem. Furthermore, I'd make sure that then RNG cannot be used for other parts of the application that do require a cryptographically secure random number generator.

Finally, note that die-harder and similar suites work best on (very) large data sets. A few GB is kind of the minimum. I hope your generator is fast enough for that.

Caveat: I'm not a super-expert on this area and cannot answer about local properties your stream exhibits. I do think that the idea that the generic test suites won't pick up on this is flawed though. I'm pretty sure that suites like die harder will pick them up - but I'm not sure about the clarity of the returned results.


By Lagrange interpolation...

  Does Shamir Secret Sharing provide integrity?

No

  Can an adversary forge a share?

Yes


Is a PRNG-generated sequence with a truly random seed considered a cryptographically secure PRNG?

Not necessarily. If you have a PRNG algorithm that has not been designed with security in mind then just giving it a random seed doesn't make it a Cryptographically Secure PRNG (CSPRNG). If a PRNG has not been designed to be a CSPRNG then it is extremely unlikely to be one by chance.

  How does a CSPRNG-generated sequence differ from a PRNG-generated sequence?

This is a bit of a weird question since a CSPRNG is of course a PRNG. Let's compare the CSPRNG against a non-secure PRNG instead.

The output of a CSPRNG should not leak any information about previous or following outputs of the PRNG. It should be impossible to recreate the state of the PRNG (at any point in time) without recovering the seed information, which all the output depends on. This isn't a generic requirement for a PRNG. For instance, the  Mersenne Twister, which does otherwise pass the Diehard tests, does allow an attacker to calculate the state vector given enough output.

A CSPRNG may have additional constraints such as a very low bias on the outputs, providing a well distributed output. It is possible to argue that these would be required for any PRNG, but PRNG's could be build for speed - providing good enough output for specific applications. Cryptographic applications generally require a very high level of unbiased, well distributed output.

Note that many CSPRNG algorithms may reseed at any time, mixing in the new seed entropy into the current state. There isn't necessarily one seed. Of course there is at least one initial seed; otherwise the CSPRNG cannot generate the initial output.


It really depends on the block mode that you are going to use. If you want to use something like CBC, have a look into PKCS#7. If you were to use CTR mode, then you do not require any padding, as the input will always be in chunks of 16 bytes, and you use as much of it as you require.


It is exactly $2^{64}$. You need to look for all possible keys for a successful brute-force. One cannot guarantee that the key will be in the half, $2^{63}$, that you are going to search. In, CS there is an adversary argument, that the adversary can always force you to the worst case. Tell him how you the search, he will produce a case that you are not going to find in $2^{63}$ key-space.

Actually, $2^{63}$ is the average case that you will find your keys during the brute-force.

If you have multiple known-plaintext with encrypted different keys then with a multi-target attack you can find some keys faster. The expected cost of finding a key from $t$ target is $2^{64}/t$.


Allow message inspection by proxy without ability to modify it

Can anyone think of a way to allow the proxy to verify that the encrypted message is what it is supposed to be, without being able to replace it with it's own encrypted message?"

The standard solution is for the server to have its own public/private signature keypair.  The server's public key is given to the proxy and the client in some secure way (that is, in a way that the proxy knows that it is the correct key - we don't care about privacy here).  Then, when the server generates an encrypted message, the server signs it using his private key, and the proxy (who has the server's public key) verify the signature (using his copy of the public key).  Then, when the client gets the encrypted message, he also verifies the signature (to check that the proxy has not modified the message).

You may also need to include something to allow the client to detect if the proxy replaced an encrypted message with a previous encrypted signed message (which would pass the signature check); perhaps a time stamp or a sequence number that always increases.

Can this work in your scenario?


cryptographic function that changes with time?

Normally we don't keep functions secret (Kerckhoffs principle). But let's assume that $T$ depends on a secret key $s$ and that we keep that secret. See $s$ as a rather large constant within $T$ if you must.

In that case we can use $T_s(t) = \operatorname{KDF}(s, t)$ to derive a secret $k$ that depends on the time. We can use $k$ as input of a key pair generation function $\operatorname{Gen}(k)$ that outputs a private key $sk$ and public key $pk$. If we choose Elliptic Curve cryptography we could just use $sk = k$ and then calculate $pk$ by multiplication with base point $g$, an efficient calculation.

So now the function $f(p)$ could simply be $\operatorname{Enc}_{pk}(p)$, giving $c$. The function $f'(c)$ would be $\operatorname{Dec}_{sk}(c)$. Here $p = x$ is the plaintext message and $c$ is of course the ciphertext. For Elliptic Curves the $\operatorname{Enc}$ and $\operatorname{Dec}$ functions would be provided by the ECIES encryption / decryption scheme.

So we now have an $sk$ that can only be created if $s$ and $t$ are known. The function $f(x)$ is simply encryption with a public key that can be published - you don't even need $t$. And you can only decrypt if you know $s$ and $t$: otherwise you would not be able to calculate $sk$ required for decryption.

Of course having $T$ both create $f$ and perform the decryption is not really possible. You need a function $T$ to create the key pair and a function $f'$ to decrypt.


Knowing interval of discrete log for elliptic curve

As mentioned in your answer to your other similar question, Pollard's $\lambda$ algorithm is still a good choice. If your search interval is $[a,b]$, then it may find the result in $O(\sqrt{b-a})$ time using very small storage.

That "may" in the previous paragraph illustrates the trade-off you must consider. Baby step, giant step requires more memory, but it is deterministic and thus guaranteed to finish in $O(\sqrt{b-a})$ time. Pollard's $\lambda$ can be parallelized which could speed up the run time (depending on your resources), but as it's probabilistic, the run time is not guaranteed at all.


Are there any existing ASN.1 structures for transferring symmetric keys?

For the algorithm you should use the AlgorithmIdentifier type of RFC5280. Block size and key size can be derived from the algorithm id and the key itself, so there is no need to store them.

So, if you want something really lightweight, just store that into a sequence:

SymmetricKey ::= SEQUENCE {
  algorithm AlgorithIdentifier,
  key       BIT STRING
}


Solve System of Equations including XOR and Modular Addition

Ok, this would appear to be homework, so I won't give the full answer; I'll get you started.

First thing to do (with this attack approach) is to write out the full equations of the system, as in:

$$T_0 = P_0 \oplus K_0$$

$$T_1 = P_1 \boxplus T_0$$

$$T_2 = T_0 \oplus T_1$$

$$T_3 = T_2 \oplus K_1$$

$$C_1 = T_3 \boxplus T_1$$

$$C_0 = T_3 \oplus C_1$$

where you know $P_0, P_1$ (the plaintext), $C_0, C_1$ (the ciphertext), and you don't know $K_0, K_1$ (the keys) or $T_0, T_1, T_2, T_3$ (the internal states of the cipher at various points).  And, we'll assume that we have a single plaintext/ciphertext pair (that will turn out to be sufficient against this cipher).

Where to do go from here?  Well, the first obvious step is to notice the last relation $C_0 = T_3 \oplus C_1$; we know $C_0, C_1$, and so we can deduce the value $T_3 = C_0 \oplus C_1$.  Then, we notice the relation $C_1 = T_3 \boxplus T_1$, we know $C_1$ and $T_3$, and so we can deduce the value $T_1 = C_1 \boxminus T_3 = C_1 \boxminus (C_0 \oplus C_1)$.  Where do we go next?

Now, this approach takes apart this two round cipher quite nicely; however it doesn't scale very well; adding a third round to this toy cipher will break the relations this depends on.  On the other hand, I suppose it might be a start in learning how to think about how to attack a cipher, although you will need to find other ways to attack less trivial ciphers. fgrieu's suggestion about looking at the lower-order bits first is a more general approach that'll work in cases where this won't.


I was wondering, would calculating the entropy of the resulting plaintext not serve the same purpose, if not to a better degree seeing as it's not confined to the english language?

First note that a cipher is susceptible to frequency analysis if it doesn't change the frequency at which characters occur. That is the "probability" of each substituted letter occuring is the same as the probability of the cleartext language. Now remember how the entropy is usually computed:

$$H(X)=-\sum_{x_i\in X} \Pr[X=x_i]\cdot \log_2(\Pr[X=x_i])$$

while replacing the probability terms for the measured approximation. Now as you can see entropy doesn't care where each probability value sits, if the same set of probabilities occurs you'll get the same entropy. And the set of probabilities is the same for each key for a given ciphertext susceptible to frequency analysis.

So "no", entropy will not help you here.


What language classes beyond NP allow constant-round zero-knowledge proofs?

The sumcheck protocol can be made non-interactive, both in the random oracle model and under strong cryptographic assumptions. Good starting points to read about that are this paper and this paper. The high level intuition that even if Fiat-Shamir fails in general for interactive protocols with many rounds, it holds whenever the protocol satisfies some stronger notion of round by round soundness which the sumcheck protocol does satisfy.
This gives you a non-interactive argument for $\#\mathsf{P}$ in the ROM. I believe that it should be relatively easy to make it zero-knowledge. It might extend to all of PSPACE, though one would have to check the details - I do not think it has been written formally anywhere.
Edit: An important point, though, is that this result in the ROM will not be easy to extend to the standard model, at least not with standard cryptographic assumptions. This is because to get a constant-round argument for a language outside of NP, we would need a cryptographic assumption (for the soundness) which withstands even attacks from prover which are given the power of this larger complexity class, and this is typically not something given by standard cryptographic assumptions.


Alternatives to FHE for secure function evaluation

Yao's garbled circuit is simple to understand. First of all, note that if we can securely compute $\mathsf{NAND/NOR}$ of two input bit, we can perform any boolean operation. Yao's garbled circuit tries to achieve the same. Lets look at scrambled $\mathsf{OR}$ gate.

Alice creates a set of four keys, $K_{x=0},K_{x=1},K_{y=0},K_{y=1}$
She then creates 4 “boxes” for each of the table entries, $B_{00}=0,B_{01}=1,B_{10}=1,B_{11}=1$.
She then encrypt each box with the corresponding keys, for example, $B_{00}$ is encrypted with $K_{x=0},K_{y=0}$, permutes the box and send the box to Bob.
Bob gets the key corresponding to Alice's input from Alice and the key corresponding to his input by using $\mathsf{OT}^2_1$.
Bob computes the output by decrypting the only box he can.

NOT gate is even simpler and I leave it for exercise for you. Else, you can always fall on the famous GMW paper, "How to play any mental game."

For attribute based cryptography, you can have a look at the bibliography at the webpage of Liang. There is a good talk given by Waters at MSR website on his work on Unbounded HIBE and Attribute based Encryption.

Now to include few questions later asked by Mike,

Computation overhead: a lot of overhead, for sure. Theoretically, you are fine as long as the overhead is polynomial which is the case in Yao's garbled circuit. But in practice, it is a lot.
Any circuit: yes, as long as they are boolean circuit. NOR and NAND are universal gates.
Interaction is a requirement if you are trying to do Secure party computation. If you are fine with Secure function evaluation, then you can do away with interaction. All you need is a non-interactive zero knowledge proof. The drawback is that that NIZK is proven zero knowledge only in random oracle model. Recall that NIZKP helps in proving to the other party that the gates are constructed properly without any interaction. This will work fine if you are doing SFE because there is no binding on the second party to share the output to the first party.
The result are in clear, but here you are assuming authenticated secure channel. If you are in standard model of communication, there are ways to go around this as well in a very standard way.
Reusuability of the garbled circuit is a different issue. You can use proactive cryptosystem to make it reusable. Stand-alone Yao's garbled circuit is not reusable. (Proactive cryptography works in the scenario where you don't change the shares after some time epoch. It is first studied in the realms of secret sharing, where the first share are formed as in normal SS, but later on, when you need to redistribute the share for same secret, you construct a polynomial with constant 0 and redistribute the share as in normal SS.)
Jarecki and Shmatiko made a garbled circuit secure against active adversary by incorporating that the first party proves in ZK-way the correctness of every gate. Note that in garbled circuit, one party construct the circuit and other computes. It thereby, does not prevent against unfair adversary. Till now, there is no way to get fair computation using Yao's method
They can be made verifiable by a very standard way. I am not sure if all the standard methods can be applied or not.

The advent of FHE helps in most of these areas, but at the moment FHE is still in a baby-stage. I cannot wait for it to become very efficient.

Summary

|System | plaintext output | Circuit size | Reusable          | Verifible | Currently Practical | 1 block of AES |
------------------------------------------------------------------------------------------------------------------
|FHE    |       N          |      Any     |     Y             |     N?    |          N          |     1 week     |
------------------------------------------------------------------------------------------------------------------
|GC     |       Y          |      Any     | Y (special        |     Y     |          Y
|       |                  |              |    constructions) |           | (with caveats)      |    0.2 sec     |
------------------------------------------------------------------------------------------------------------------
|FE     |       Y          |       ?      |         Y         |     Y     |          ?          |       ?        |
------------------------------------------------------------------------------------------------------------------


How can I encrypt more than 128 bits of data with AES?

No, the state of the AES is the internal state of the block cipher. It is not used to store the plaintext message. After a block encrypt the state of the block cipher isn't required anymore. Generally only the subkeys are kept so they don't have to be recalculated using the key schedule anymore.

AES, being a block cipher, is not a generic / secure cipher in itself. To use it as a cipher you need to use a mode of operation. The mode of operation is independent of the block cipher itself, although it of course does depend on some parameter such as the block size. The best known mode of operation to create confidentiality is probably CBC. However you will get much more security when using an authenticated mode of operation such as GCM mode.

Now the CBC mode and GCM implementations also require state, and this state needs to be kept up to date. For CBC this is at least a block of plaintext as it is impossible to encrypt partial blocks. For GCM it is possible to encrypt partial blocks because it uses counter mode underneath. However, you would still have to store the intermediate results required to calculate the authentication tag (usually stored at the end of the ciphertext) and at least one block for the key stream used to encrypt.

As the input / output of a block cipher is one block, and since there must be some kind of vector to link the blocks into one message, you should expect around two blocks of memory for the state, not including the subkeys. That's not that much and probably insignificant compared to the other memory requirements (in-memory tables) required for a fast software implementation of the cipher itself.


Many time pad if cleartext contains arbitrary bytes

I think you misunderstand the concept of the one-time pad encryption method since the one-time pad treats messages like a binary sequence.

What is done is actually for a message $m$ (this message could be an image, a text, anything, ...), you use its binary representation and XOR its binary value with a binary key $k$ : $m$ $\oplus$  $k$.
So it doesn't matter what kind of characters your message contains, you still can't break the security of the scheme when using the same key.

Check out this question: Taking advantage of one-time pad key reuse?


Is the reduction from left-or-right IND-CPA to real-or-random IND-CPA tight?

Here's an artificial example:  Start with some secure encryption scheme with encryption function $\mathcal{E}(\cdot)$, and construct a new scheme with encryption function $\mathcal{E}'(\cdot)$, which for any input message $m$ copies the first bit, $b$, of the message, and outputs $b||\mathcal{E}(m)$, where $||$ denotes concatenation.

For such a scheme, there exists a LoR adversary $\mathcal{A}_{lor}$ with Advantage 1 using only one query.  $\mathcal{A}_{lor}$ merely has to submit a query $(m_0,m_1)$, where $m_0$ starts with a 0 and $m_1$ starts with a 1.  Assuming wlog that the Challenger has a coin $c$ and returns the ciphertext $\mathcal{E}'(m_c)$, $\mathcal{A}_{lor}$ then bases its guess for the value of the Challenger's coin on the first bit of the returning ciphertext (i.e. for a returning ciphertext with first bit $b$ it outputs the guess $c = b$).  This guess will always succeed, because with such a query, the first bit of the ciphertext does indeed equal the Challenger's coin $c$.

However, the RoR advantage for any adversary similarly restricted to just one query can be no greater than $1/2$ (again assuming that the underlying scheme we started with is secure).  Because the underlying scheme is secure, any adversary $\mathcal{A}_{ror}$ must base its guess entirely on the first bit of the resulting ciphertext and whether that first bit is equal to the first bit of its query.  Wlog we can assume $\mathcal{A}_{ror}$ submits a query $(q)$ with the first bit set to 1.  If the output ciphertext starts with a 1 then $\mathcal{A}_{ror}$ guesses the Challenger is running the $Real$ oracle, and if the output starts with 0 it guesses the Challenger is running the $Random$ oracle.

Recall the definition of the RoR adversarial advantage function,

$$\mathbf{Adv}^{ror-cpa}_{\mathcal{E}',\mathcal{A}_{ror}}(k) = \Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] - \Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real].$$
If the Challenger is running the $Real$ oracle then the first bit of the output ciphertext will be a 1 with probability 1, and so $\Pr[\mathbf{Exp}^{ror-cpa-real}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1$.  However, if the Challenger is running the $Random$ oracle, then it will return the ciphertext $\mathcal{E}'(*)$ for some random string $*$ equal in length to the query $q$.  The first bit of $*$ will be a 1 with probability $1/2$, and so $\Pr[\mathbf{Exp}^{ror-cpa-random}_{\mathcal{E}',\mathcal{A}_{ror}}(k)=Real] = 1/2$.

As such, for adversaries restricted to one query, the maximum RoR advantage versus $\mathcal{E}'$ is half the maximum LoR advantage.


Authenticity of the data assures that the data in question was created or modified by an authorized party (a key holder). Without authenticity, anyone could present an arbitrary block of data as a valid ciphertext. Though it is overwhelmingly likely that decrypting such a block will result in a garbage plaintext, it can still disrupt the application that is attempting to use the data. This is different from integrity, in that integrity assures you that a given piece of data has not been modified (either by an unauthorized party or by more mundane sources of data corruption such as bad hardware/line noise/cosmic rays/etc).

  So the authentication of the additional data corresponds only to the property that it is received in the same condition that it was sent out, without modifications?

Technically, integrity is what guarantees that the data was received in the same condition as it was sent out. Authenticity assures that the data originated from an authorized party.

Integrity can be seen as a subset of Authenticity. For example, you can obtain integrity by hashing a message. This does not provide authenticity though. For that, you require a MAC.


One-time pad using RSA and Diffie-Hellman functions

This feels like homework, and so I won't give you the answer; I'll give you hints:

  If F(x) = x^e mod n, and (n, e) pair is public, will the first 1024 bits of both plaintext and ciphertext be enough for Eve to read the entire message?

If Eve knows the first plaintext $M_0$, and the ciphertext $M_0 \oplus (r^e \bmod n)$, how can Eve recover $r^e \bmod n = F(r)$?  Given that, how can she reconstruct $F(kr) = (rk)^e \bmod n = r^e \cdot k^e \bmod n$?

  Same for F(x) = g^x mod p, and public (g, p) pair.

Again, given $F(r) = g^r \bmod p$, how can Eve recover $F(kr) = g^{kr} \bmod p = (g^r)^k \bmod p$?

  Are the cases described above good examples of public-key cryptography?

Nope; they're not examples of public-key cryptography as all.  We know this based on your description:

  Suppose that Alice and Bob use an encryption algorithm based on ... r, a secret key shared between Alice and Bob

Public key cryptography doesn't use a secret key shared between the two parties.

Also, please don't describe these algorithms as 'one-time-pad'.  That has a very specific meaning (where the pad is generated in a truly random fashion, and not algorithmicly); this is not that.


With DES, is ECB encryption mode equivalent to CBC with null IV for short data blocks?

The CBC mode processed as $c_i = E_k(p_i \oplus c_{i-1})$ with $c_0 = IV$
The ECB mode processed as $c_i = E_k(p_i)$

If you set the first block with $$c_o = IV = 0$$ in the CBC mode, than it is calculated as $$c_1 = E_k(p_1).$$ This is exactly as ECB mode.

The next blocks, however, will not be equal;

in ECB mode $$c_i = E_k(p_i)$$
whereas in CBC mode $$c_i = E_k(p_i \oplus c_{i-1}) \neq E_k(p_i) \text{ for } 1 < i \leq m$$ where $m$ is the number of blocks.

Therefore the equality is only valid for the first block.


Basic question about design of program with data encryption

How do I deal with user changing password (The key will be generated from password.)?

Generate a random master key K. Use K to encrypt the files. Use the user's password to generate a second key, K'. Encrypt the master key using K'. Then when the user changes his password, all you need to do is decrypt the master key using the old password and re-encrypt it using a new key derived from the new password.

How to actually verify the password?

If you encrypt the master key using AES-GCM, then decryption will fail if the password isn't correct. (Make sure that you take advantage of GCM's authentication feature; for Bouncy Castle specifics, see sections 3.3 and 3.4 of http://blog.philippheckel.com/2014/03/01/cipherinputstream-for-aead-modes-is-broken-in-jdk7-gcm/#Example-AES-GCM-with-three-CipherInputStream-implementations.) This would not be the case if you used, e.g., AES-CTR or AES-CBC.

I would strongly encourage you to look pre-existing solutions to encrypting file systems or volumes. There's lots of ways to screw up a design or implementation, and this is the safest (and probably easiest) solution. (But kudos to you for choosing a mode like GCM, that protects both the privacy and integrity of the data.)


Correlation among Psuedo Random Sequences generated from seeds which are correlated

Caveat: LFSRs outputs are vulnerable to known plaintext attacks using the Berlekamp Massey algorithm.

Given a maximal length sequence $s(t)$ of period $2^n-1$ generated by a primitive LFSR, all its windows of length $\ell \geq n$ are unique so partial period correlation of such lengths can uniquely determine the phase, thus the seed.

All primitive LFSR sequences of this length are obtainable by regular decimations of this sequence, i.e., $s(dt)$ where $gcd(2^n-1,d)=1.$

So this is an exploitable correlation.

Another relevant property is the shift and add property

$$s(t+k)\oplus s(t)=s(t+z(k))$$

that comes from the fact that the maximal length sequence and its cyclic shifts together with the all zero vector form a linear code. This is another source of correlation.Here $$a^{z(k)} =1+ a^k$$ defines the so called Zech logarithm $z(\cdot)$, if we use the trace representation $$s(t)=Tr(a^t)$$ with $a \in GF(2^n).$

The book by Golomb and Gong and a survey by Sarwate and Pursley in the Proceedings of the IEEE are good places to start.


Garbled circuits: How can the sender safely retrieve the output?

There are two separate issues here:

Guaranteed output / fairness: how does the protocol prevent Bob from withholding Alice's output (guaranteed output), or at least prevent him from learning the output himself when he decides to withhold output from Alice (fairness)? The short answer is that garbled circuit protocols do not provide any such guarantees. The standard definition of malicious security in this area is "security with abort". This model allows a malicious party to learn their output first and subsequently prevent the honest party from receiving output.

The reason for this is that it is impossible to guarantee fairness in general, for 2-party secure computation. This is due to an old result of Richard Cleve (Limits on the security of coin flips when half the processors are faulty, STOC 1986). Since fairness is impossible for some 2-party functions, and garbled circuits give you secure 2PC of any function, you cannot hope for a typical garbled circuit protocol with fairness.

Output authenticity: how does the protocol prevent Bob from lying about the output to Alice, in the case that Bob doesn't withhold her output altogether? There are several approaches but one I like is to just have Bob present the output wire labels back to Alice. Wire labels have an "authenticity" property: the evaluator only learns one on each wire and cannot guess the complementary one. Hence they act as a kind of "proof" to Alice that this was indeed the correct output.

This is the main idea but there are quite a few pitfalls to avoid. It helps if all circuits in the cut-and-choose have the same output wire labels. But then if some of those circuits are opened during cut-and-choose, it breaks the "authenticity" property. So you have to arrange things in a clever order: After Bob evaluates the circuits, he commits to the output wire labels. Then the check-circuits can be opened. If they are all good, only then does Bob open the commitment to the output wire labels.

Two-output Secure Computation With Malicious Adversaries:
abhi shelat and Chih-hao Shen, Eurocrypt 2011 (uses a different technique but focuses explicitly on getting output to the sender)
Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation: Payman Mohassel and Ben Riva, Crypto 2013 (uses the wire-label-authenticity idea I mentioned)
Zero-Knowledge Using Garbled Circuits: Marek Jawurek and Florian Kerschbaum and Claudio Orlandi, CCS 2013 (uses the wire-label-authenticity idea as the basis of a ZK proof: possibly malicious GC evaluator has to convince the GC generator of the circuit's output)


Hardness of problem related to bilinear pairings

What you present is a generalized version of the so called fixed-argument pairing inversion (FAPI) problem. The FAPI problem is given an element $z\in G_T$ and an element $h\in G$ to compute $f\in G$ such that $e(h,f)=z$.

Note, that FAPI is implied by the computational Diffie Hellman problem: Given $(g,g^a,g^b)\in G^3$, call the FAPI oracle with $z\gets e(g^a,g^b)$ and $h\gets g$ and clearly we have that $f=g^{ab}$ which is a solution to the CDHP in $G$.

The generalized (GPI) version is that when given $z\in G_T$ to compute $h,f\in G$ such that $e(h,f)=z$. Obviously, GPI implies FAPI.

Pairing inversion is AFAIK generally believed to be hard. You may study this paper or this blog post for more details.


Can the EdDSA signature scheme be customized with OpenSSL?

The first thing to clarify is the definition of “EdDSA”. EdDSA was introduced in Bernstein et al.'s High-speed high-security signatures in 2011. Various parameters it implicitly assumed were declared more generally in the 2015 paper Bernstein et al., EdDSA for more curves. This culminated in an RFC Edwards-Curve Digital Signature Algorithm (EdDSA), RFC 8032 from 2017.
All of them describe EdDSA abstractly and then instantiate it with a set of concrete parameters. Thus, Ed25519 and Ed448 are specific sets of parameters for EdDSA that form a concrete signature scheme that can be implemented.

Is it possible to use EdDSA with a custom algorithm (signature scheme) for instance a different curve and a different hashing algorithm like SHA-1?

Yes, this is possible, assuming you do not mean the specific instantiations in the first paper and RFC 8032.
In fact, the Monocypher cryptography library's crypto_sign() does exactly that, swapping out SHA-512 in favor of BLAKE2b.

Is this not possible because of an RFC standard?

As noted above, this is possible, but the result obviously wouldn't be able to be called “Ed25519” or “Ed448” because it'd be incompatible with those specific instantiations.

Does this mean that EdDSA is rigid by design?

It isn't, no. The 2015 paper even goes out of its way to add a bunch of.
EdDSA as specified in all of these documents is somewhat inflexible with regards to the underlying curve, however: It assumes that the cofactor $h=2^c$ has $c\in\{2,3\}$, which rules out prime-order Weierstrass curves for example. The required modifications to be able to not require $c$ with a prime-order curve are both trivial and obvious, but this specific set of permissible values for $c$ mandated by all specifications of EdDSA.

Does this have to do with OpenSSL not having the feature implemented?

No, nobody specifying EdDSA cared what OpenSSL does because that'd be putting the cart before the horse: OpenSSL can't implement EdDSA before it is specified.


Are ZKPPs possible with server-side hashed passwords?

Short answer: YES. (Though see the note on "hashed" below.)

Intro

The remote authentication protocols where server does not know the plaintext password are generally known as augmented password authenticated key agreement (PAKE). You can see this wikipedia article for details of PAKE algorithms (augmented and non-augmented). You may find this reference useful to find out more about the common protocols.

Not hash

Usual symmetric key cryptography is not sufficient for creating augmented PAKE mechanisms. Therefore,  in augmented PAKE mechanisms (as far as I know them) it is not sufficient for the server to store hash of password. They mechanisms are based on operations commonly used in public-key cryptography (such as Finite Field Cryptography) and thus, the material stored by server is commonly something akin to a public key instead of hash. (Functionally this can be considered to be similar, but the storage space consumed per user is more than traditional password hashes require.)

The augmented PAKE ZKPP algorithms include e.g. SPEKE, Augmented-EKE, and SRP.


Why we need to use a modulus in public cryptography?

The DH, ECDH and RSA problems require modular operations. They are fundamental in the problem space that they operate in (where problem is a mathematical term). Please go through an introduction of number theory for cryptography to understand why - or take it for granted if you don't want to delve that deep.

Besides that, performing exponentiation on large numbers is definitely more troublesome without modulus than with a modulus. Imagine raising a number of, say 2048 bits to the power of a private exponent of 2048 bits. The resulting number would have a value of about $2^{{2048}^{2^{2048}}}$. Now I don't know about you, but I'm pretty sure that number is too big to handle. Modular arithmetic is much more efficient than non-modular arithmetic as well; you can easily get a feel for this yourself, what's the last digit of $2459 \times 9823$ or $9823^4$?

Finally, we don't need to have an asymmetric primitive such as RSA to handle large plaintext/ciphertext; we can use symmetric primitives for that, creating a hybrid cryptosystem. For instance we can use a cryptographic hash (such as SHA-256 or SHA-512) to create signatures together with RSA-PSS. And we can use a symmetric cipher together with RSA-OAEP or RSA-KEM to create a secure cryptosystem. That way we can handle larger plaintexts / ciphertexts without having to deal with the size limitations of asymmetric primitives.