To complement fgrieu's short answer, here is an overview of the two RNG algorithm sets.

Hash-DRBG

The state of Hash-DRBG is composed of a value $V$ (which is updated with each request of new bits), and a same-size constant $C$ (which is only updated on reseeding the generator), and a counter $c$ to track when the next reseeding is needed.

Only $V$ is directly used to generate new bits, by concatenating $H(V), H(V+1), H(V+2), \dots$ until enough bits are generated.

After each generation of new bits, both the constant, the counter and a hashed version of the value are added to the value to generate the new value:

$$V_{\text{new}} = V + H(\text{0x03}||V) + C + c $$

Then $c$ is increased by one.

You can also provide additional input to the generator, in which case another hash call with $V_{\text{new}} = H(\text{0x02}||V||A)$ is done before generating the output.

For initial seeding and reseeding, an adaptable-output-size version $\tilde H$ of $H$ is used (as defined in Section 10.4.1), to generate enough bits for $V$ and $C$.

Hash-DRBG relies on $V$ and $C$ staying secret. For $V$, this is the preimage-resistance of the hash function (as $V$ is hashed to generate the output), while $C$ can be easily derived from two (or three, if the counter value is not known) consecutive values of $V$ (as it is simply added).

From this, the following output can be predicted, until the application adds non-predictable additional data or the state is reseeded.

(Of course, we also need that the output of $H$ is pseudo-random, i.e. has no detectable patterns.)

Initialization: The value $V$ is created by hashing the "seed material", and the constant $C$ then by hashing $V$ (with a prefix byte of $0$) (both producing 440 bits).

HMAC-DRBG

In HMAC-DRBG, the state is composed of a key $K$, a value $V$ and a counter c (to keep track of when a reseed is needed - it is not used for generation itself).

The actual generation of random bits uses

$$ V := HMAC(K, V)$$

in a loop and concatenates these new values of $V$ until enough output is generated.

After this, an update function is called, which changes both key and value by two HMAC calculations:

$$\begin{align*}
   K_{\text{new}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00}) \\
   V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{old}})
 \end{align*} $$

Update can alternatively also incorporate additional data $A$ provided by the application, using four such calls in total:

$$ \begin{align*}
  K_{\text{tmp}} &= HMAC(K_{\text{old}}, V_{\text{old}} || \text{0x00} || A) \\
  V_{\text{tmp}} &= HMAC(K_{\text{tmp}}, V_{\text{old}}) \\
  K_{\text{new}} &= HMAC(K_{\text{tmp}}, V_{\text{tmp}} || \text{0x01} || A) \\
  V_{\text{new}} &= HMAC(K_{\text{new}}, V_{\text{tmp}}) \end{align*} $$

(If additional input is given to the generate-function, update will be called before and after generating more output.) This will also be used for seeding and reseeding, where the additional data contains entropy input (and maybe any application-specific stuff).

HMAC-DRBG's security depends on the key $K$ staying secret (intermediate values of $V$ are output directly as pseudorandom bits), i.e. on the key-retrieval-resistance of the HMAC.

If value of $K$ is known, all the following ones can be derived, until the application adds non-predictable additional data or a reseeding occurs.

But other than this worst-case break, there might be other weaknesses in the hash function's output which make HMAC's output be non-random (i.e. show patterns). Optimally, we want the HMAC output be a pseudorandom function of the input.

Initialization: The HMAC_DRBG_Instantiate_algorithm function sets $K$ to 0 and $V$ to $0x01010101\dots01$, before calling first the Update function with the seed material as "additional data".

Summary

One can see that HMAC-DRBG shuffles stuff around a bit more than Hash-DRBG ... and HMAC itself even contains two hash invocations.  Thus HMAC-DRBG is certainly slower.

But as any possible weaknesses of HMAC will come from weaknesses of the underlying hash function, HMAC can't be
weaker than the hash ... but it could be stronger (i.e. some weaknesses of a hash function will not transfer to the corresponding HMAC). For now, there is no weakness known in either of both constructions, though.


How to express a coin flip based random generator mathematically?

Boneh's definition of a pseudorandom generator stipulates that a PRG is a mathematical function—a mapping from an input domain to an output codomain such that the choice of argument value uniquely determines the result.  In recent programming parlance, this is what people often call a pure function, like in pure functional programming languages (e.g. Haskell)—one whose results depend exclusively on the value of its arguments, and not on the state of the program.

Coin flips clearly do not fit under that definition, because they're non-deterministic—calling the coin-flip "function" (really an imperative programming routine) twice with the same argument is supposed not to always produce the same result.  So a sequence of coin flips is not a PRG.

Mathematically, the concept we'd use to model coin flips is random variables.  The outcome of a coin flip is a random variable.  The outcome of a sequence of coin flips can also be seen as a random variable: you can describe the former as an experiment that repeatedly takes samples of the outcomes of single coin flips.


Where can I double check my elliptic curve results?


Is it possible to weaken a bitcoin private key by “using” it elsewhere?

I'll start with the last point and use the notation for ECDSA from the wikipedia article.

  Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

When using a digital signature scheme, the parameters (used group, e.g., elliptic curve group) as well as the public key,
signatures and all corresponding messages are public knowledge and a secure digital signatures scheme needs to be
even secure if the adversary is allowed to obtain signatures for arbitrary messages of its choice (ECDSA is secure
against such existential forgeries under adaptively chosen message attacks if the used hash function is collision resistant - AFIK the proof is in the generic
group model, but should still give enough evidence that it is secure).

In ECDSA your private key $d_A$ is an integer from $Z_q^*$, i.e., from the set of integers $\{1,\ldots,p-1\}$, where $q$ is the order of your elliptic curve group and
your public key is a point $Q_A=d_A\cdot G$ on the curve where $G$ is a generator of your elliptic curve group and part of the public
parameters.

The problem you are focused when you want to extract the private key $d_A$ from a given public key $Q_A$ is the elliptic curve discrete logarithm problem (ECDLP). Consequently,
ECDSA must be used with an elliptic curve group where the ECDLP is hard enough (also excluding curves that allow efficient pairings to reduce the ECDLP to the DLP in a related field (MOV attack). But this
is not the case if you use standardized curves such as SEC or NIST curves).

Observe also, that when you want to extract the private key from a given
signature you also have to break the ECDLP for point $kG$.

So for your question you have different public keys $d_A\cdot G_1, \ldots d_A\cdot G_n$ on $n$ different curves, where the public keys share the same private key
$d_A$. Additionally, you may know corresponding message-signatures pairs.

Then, to recover the private key you can use either the public key or the signatures you have
available on every curve separately, as you cannot do arithmetic between points on different curves. Even if it happens that there are efficient mappings between the curves, then you could simply take a single public key (e.g., of someone else) and map it to all the other curves and this attack would then also apply to a "single public key setting". Consequently, you rely on the strength of the ECDLP on the weakest of your
$n$ used curves and from my point of view the most efficient way to recover the private key in this scenario is to attack the ECDLP on the weakest of the used curves.

In general, when using ECDSA it is far more dangerous to re-use the randomness $k$ when producing signatures on
the same curve, as two signatures for different messages with same $k$ allows to recover the private key instantaneously as it happened to Sony back in 2011.


Tracking the noise growth of Homomorphic encryption

You can't know exactly how much noise your ciphertext has because when you encrypt a message, you sample random values that are combined to the message and they also make part of the noise (so, the noise is also random). But you can have good estimations for the magnitude of the noise because all the distributions from where we sample the values are known.

That said, the better you can do to keep track of the noise growth is to use the estimative provided (generally) by the authors of the scheme: in general, for the scheme we are using, we know upper bounds to the noise of a ciphertext that is the result of an operation, that is, we know functions $f$ and $g$ such that

if $noise(c_1) \le n_1$ and $noise(c_2) \le n_2$, then

$noise(c_1 + c_2) \le f(n_1, n_2)$ and $noise(c_1 \cdot c_2) \le g(n_1, n_2)$

(For instance, we could have $f(n_1, n_2) = n_1 + n_2 + 128$ and $g(n_1, n_2) = 128 \cdot n_1 \cdot n_2$).

It is worth noting that those estimations are quite pessimist: for instance, on the paper A Comparison of the Homomorphic Encryption Schemes FV and YASHE, authors say that they could select parameters with size about 30% smaller than expected because the noise growth was always below the theoretical upper bound, as they show in the following figure (which is on the 12th page):

That difference occurs because the theoretical upper bound uses a kind of "worst-case analysis", considering the biggest noise that can occur, but in practice, that biggest values of noise will occur only with small probability (remember that, in general, we sample those values following a Gaussian, therefore values close to the mean are more likely to occur...)

  Is it even possible to clip off the unwanted noise and continue with your operation?

Yes. This is called bootstrapping and it consists in running a "refresh" procedure to remove the noise of the ciphertext. But that is not a simple procedure and can be quite expensive computational-wise.

  Now by learning that noise growth what else can I gain?

You can try to reduce the number of times you use the "refresh" procedure removing the noise only when it is needed instead of doing that after each operation.


Which one these alternatives using authentication and encryption will solve this multiple-user database problem?

The first one looks more complicated, but it is wrong. What you should see is that a man in the middle attack by user $B$ can replace it by $E_{pk_D}(R), S_{sk_B}(E_{pk_D}(R)), B$. Now the server will happily verify the signature, decrypt the request, and return the data to $B$ instead of $A$.

This is why in general you cannot trust that available data was only signed by one entity, and this is why in general we use sign-then-encrypt for asymmetric schemes while we tend to use encrypt-then-mac for symmetric schemes. You would not have trouble if you'd only accept signatures from one entity or from fully trusted entities, but that's clearly not the case here.


What does $\Pi$ represent in cryptography?

This is standard mathematical notation and not specific to cryptography. The $\Pi$ symbol means Product in much the same sense $\Sigma$ means Sum. For instance,
$$\prod_{i=0}^2{u_i^{m_i}} = u_0^{m_0}u_1^{m_1}u_2^{m_2}$$


Full diffusion or Partial diffusion between s-box applications?

If the linear diffusion layer were applied twice without applying the s-boxes between them, it is possible there might be an iterative differential characteristic with only four active s-boxes per modified 'round' (i.e. instead of a provable minimum of 25 active s-boxes over 4 rounds there could be as few as 16 active s-boxes over 4 'rounds').

Consider for example a state where all four bytes in a single row are active.  After SubBytes, all four bytes are still active.  After ShiftRows, all four bytes in that same row are still active.  Then after MixColumns all sixteen bytes in the state are active.  Applying ShiftRows again doesn't change the fact that all sixteen bytes are active.  But applying MixColumns again might (assuming the bytes differences are just right) result in a single row of active bytes.  If that row is the same row as the one we started with, and if the resulting differences of the active bytes are the same as the differences we started with, then that is an iterative characteristic that only activates 4 s-boxes in each 'round'.

If you want complete diffusion in a single round while still retaining provable minimum numbers of active s-boxes, you should use a 16 x 16 MDS matrix with a branch number of 17, such as this one.  But even with such a beast, you can only prove a minimum number of 34 active s-boxes over 4 rounds.


Why do curve25519 implementations only have ge_frombytes_negate_vartime, and not a regular ge_frombytes method?

Bernstein only wrote the code required for key-generation, key-exchange and signatures, not a general purpose elliptic curve library. So when an operation is not required for those features it will be missing from the library.

Vartime operations are used during verification as verification does not require side channel resistance.


Avalanche noise RNG for one-time pad use

If this is a good HRNG (look for security reviews) I suppose yes. But it would be excruciatingly slow (HRNG's are not known to be fast, generally you use them to get 256-512 entropy bits to seed a PRNG and go with that) and you still have the key exchange + reuse OTP problem.

Note this tool apparently integrates itself with the Linux entropy pool, so I'm not sure you can actually access its raw output directly without it getting mixed with the rest. Perhaps there is an API for that. Using the Linux pool also means you will starve the system from entropy as your program eats it all to create a one-time pad... probably not a good idea :)

Remember you still need integrity checking.


Randomization attack in voting protocols

Hirt and Sako present such a scenario here. Informal description:

A group of mutually distrusting authorities have encrypted candidates and shuffled their order. The voter expresses their choice by publicly pointing to an encrypted candidate. Outsiders can not tell who the encrypted candidate is, but the voter knows because each authority has secretly told the voter how they shuffled. Because the authorities use a designated verifier proof to convince the voter, only the voter is convinved. If the voter would attempt to pass the proof to the adversary, they would not be convinced, because the proof is constructed in such a way that the voter could have forged it.

The adversary is unable to force a voter to vote for a particular candidate, because the voter is unable to prove to the adversary, which choice (in the encrypted and shuffled list of candidates) corresponds to which real life candidate.
The adversary is able to force a voter to vote for a random candidate, because they can randomly pick a choice in the encrypted and shuffled list and verify that the voter indeed votes for the choice that they picked.


Generally, the security contract for a cipher involving an IV or nonce does not require the IV/nonce to be secret, for the cipher to provide any security.  Not only is there no need to keep the IV/nonce secret, but it often provides negligible additional security to do so, and it often enhances security to use a (public, observable) message sequence number as a nonce.

However, it's anyone's guess what ‘design’ might have gone into WEP, and certainly it had no input from any competent cryptographer, who might have alerted them to the stupidity of their design and to the fact that RC4 was $55v$1@mhadg.production.compuserve.com>, 1994-09-15.">broken within 48 hours of its publication, not to mention the plethora of other ways it has been found to broken since then because people kept using it in protocol after protocol despite being broken.

You could change one small part of WEP's cryptography at a time, and the rest would be just as much of a disaster; the only thing to be done with it is to throw the whole thing out and start over.


Can the round function $F$ in a Feistel Network be practically any non-invertible function?

Yes you could use a hash function as round function, but if you are using the "same key" over all rounds, you are vulnerable to slide attacks. Using a hash function is not a very good idea.

Your round function should not introduce biases, should not lead to special differences (attack: differential cryptanalysis), and it should also not be writable as a linear equation (attack: linear cryptanalysis). You should take care of how your round function will work when the round keys are slightly modified (attack: related key attacks), and you should take care of impossible differentials. If you got all that right, you can use any $F$ which passed these criterions.

Short answer is, $F$ needs to be carefully selected. And “yes” you are interested, that $F$ will "loose as much information about the input" as possible.

Your second question:

  This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible?

Your round function does not need to be invertible, because the classic balanced Feistel construction will create two halves, where only one half is modified, and the other kept in clear text/unmodified. After each round both halfes are exchanged and the modified half becomes the fixed one and the previously unmodified half is now encrypted. If you now reverse the order of the keys/rounds you can decrypt the message again. The Feistel construction itelf is invertible.


Good practices for AES key derivation and management

I know that I need to derive a "cryptographycally good" AES key from this shared secret... I was planning to use HKDF-SHA512 for that, because it seems to be a widely used algorithm and also because a reference implementation is also provided by STMicro. Is it a good choice?

Yes, it is. HKDF is standardized and well regarded.

  I'm confused about the size and the nature of the salt to derive the key. Do you have any advice for that?

If a random is already provided within the protocol you may want to use that. A random of 64 to 128 bits should be plenty. Anything over 256 bits is madness. Note that the salt is complementary; a salt of any size is better than nothing.

The salt must of course be known at both sides, so it will complicate the protocol somewhat if it isn't available yet.

  From what I understood one can use HKDF-SHA512 to generate a key of 256 bits, do you confirm?

Sure thing, you can just take the leftmost 256 bits. You could use 96 bits of the remaining bits for the IV.

  Also regarding the derivation frequency : at what frequency should I derive a new key?

That depends on the use case. For smart cards you may just derive the key once at the start of the protocol and simply halt if too much data is being processed, as smart cards are not meant to be continuously available. But if your secure channel of your transport protocol is just established once then you may want to reestablish after a certain amount of messages.

Hints on how to make sure that the keys are fresh are in chapter 8 of the GCM specification by NIST, specifically chapter 8.3 which specifies how GCM is to be used.

Beware that there are many pitfalls in creating a transport protocol; you may want to have a look at TLS 1.3 or even implement it directly. TLS 1.3 also is able to use GCM as well as HKDF.


Non-interactive public sum of private values

If all the participants have a random secret key which sums to 0. They can each post the sum of their key with their number. Anyone can then some the values posted, the key will cancel out and we what will remain is the sum.

This only works if everybody posts their value and we have an appropriate key distributed.


Decryption with password, compiled code and ciphertext known

Yes, you can, but you may have to reverse-engineer the algorithm. Crypt-analists usually consider the algorithm known. But this is more because the algorithm acts as a single secret if it isn't known.

If the algorithm is really intricate then it may be hard to reverse it from compiled code. If it is however managed, unobfuscated code then it may be pretty simple to decompile. It's quite easy to see that you have all the information present, but it may still be hard to extract it.

I once attacked an amateurish encryption scheme in Java Script (web-page encryption) and as a result I didn't just get the plaintext but also a table with names and passwords - and in that case I didn't even have a password.

So it depends on the ciphertext and application on how easy it is to decrypt. As the algorithm is deterministic and since you have all the inputs: password, code and ciphertext it's clear that it can be done.


Why using AES in ECB (Electronic Code Book) mode a bad idea?

ECB is bad because identical plaintext blocks result in identical ciphertext blocks. Encrypted data is therefore not pseudo-random.

This is how Tux looks like after ECB encryption:

CTR mode doesn't have this problem. Data encrypted with CTR mode is pseudo-random and doesn't show any pattern. So CTR is much better.

CBC and CFB can also decrypt parallel, but not encrypt.


The extract and expand steps of HKDF are just two phases of one algorithm run. The PRK created my the extract step is not meant to be used as a key (even though it would not be a problem securitywise).

So if you need to derive two keys from one IKM value, you run the whole algorithm (that is: extract & expand) once with an appropriate info string (like "key1", for instance) and then you run the whole thing a second time with the same salt and IKM but a different info string (like "key2").


Incorrect Test Vectors for AES' MixColumns?

No, $03 + 02 + 01 + 01 = 01$

The problem is that you are misinterpreting $+$, it's not addition modulo 256; instead, it's the addition operation in the field $GF(2^8)$, which can be computed by performing the exclusive-or on the inputs.

And, $03 \oplus 02 \oplus 01 \oplus 01 = 01$


Why can't Diffie-Hellman be used for signing?

Actually the presentation of digital signatures as "encryption with the private key" is a misleading historical way of explaining RSA signatures; but it really works only for RSA. For such a scheme to work, you need the asymmetric encryption algorithm to be a trapdoor permutation, so that the space of encrypted messages is the same than the space of decrypted messages.

Most asymmetric encryption algorithms are not trapdoor permutations. This does not mean, however, that it is not possible to reuse parts of an asymmetric encryption algorithm to design a digital signature scheme.

Consider Diffie-Hellman. It is not an asymmetric encryption scheme; only a key exchange algorithm (a key exchange algorithm can be viewed as an asymmetric encryption algorithm in which you do not get to choose what is the encrypted message you send). From DH, we can build an asymmetric encryption scheme, and this is what ElGamal is about. An ElGamal public key is much similar to a DH public key: given fixed public parameters which describe a group $G$ of size $q$ and a generator $g$ of that group, the ElGamal private key is an integer $x$ (smaller than $q$) and the public key is $g^x$. To encrypt a message $m$ with the public key, the sender:

chooses a random $y$ modulo $q$;
computes $g^y$;
computes $s = (g^x)^y$;
sends $g^y$ and $m*s$ to the private key owner (this assumes that $m$ can be mapped to a group element, and back).

We recognize Diffie-Hellman in the first three steps: $s$ is the "shared secret" resulting from using DH with the public $g^x$. The fourth steps simply "encrypts" m by multiplying it with the shared secret.

Here, the private key is an integer modulo $q$ and the public key is an element of group $G$, which could be, e.g., an elliptic curve. You cannot swap them and try to encrypt with the private key: encryption needs a group element, not an integer modulo $q$.

Nevertheless, an ElGamal signature scheme has been designed, but it really does not look like Diffie-Hellman. It rather looks like a computational zero-knowledge proof of knowledge of the private key. With $G$ being non-zero integers modulo a prime $p$, signature works like this:

hash message $m$ into value $h$ which you map to an integer;
choose a random value $k$ relatively prime to $p-1$;
compute $r = g^k \mod p$;
compute $s = (h-xr)/k \mod (p-1)$. The signature is $(r, s)$.

To verify:

hash message $m$ into value $h$ which you map to an integer;
verify that $g^h = y^r r^s \mod p$.

So there are modular exponentiations in there, but nothing which is really "just Diffie-Hellman". ElGamal signatures are called such because Taher ElGamal described that algorithm, not because of any specific link with the ElGamal encryption scheme (which is also called ElGamal because it was also published by ElGamal).

Remark: with RSA, when you verify a signature, to process (exponentiate) the signature value with the public key, and this yields $H(m)$ (the hash of the message which is signed), which you them compare with the expected hash value. This does not work so with other signature algorithms, in which the hashed message is an input to the verification algorithm; you cannot recover the hashed message from the signature and the public key alone. RSA signatures are said to be signatures with recovery because you obtain the hashed message out of the signature; ElGamal signatures (and its offsprings DSA and ECDSA) are just "regular" digital signature schemes. Having the "recovery" feature is a byproduct of RSA being a trapdoor permutation.


First, using only a single SHA512 to hash the password is not enough.
You should use something like bcrypt with a long salt to store user password "hashes". A simple SHA512 can be attacked quite powerful with a dictionary attack, just trying millions of possible passwords and calculating the SHA512 hash for that until one matches.

Concerning the encryption of other users passwords.
Best would probably be to use a KDF (key derivation function) like PBKDF2 or SCrypt to derive a key (or keys) from that. These can be used to en/decrypt the stored user passwords.

But do not just apply e.g. AES directly to these passwords. Put the passwords in a suitable format e.g. XML or JSON and encrypt the serialized structure using a good AEAD scheme like GCM etc. Or use CBC but attach a MAC (HMAC or CMAC) to it. But always Encrypt-then-MAC !


Should an AES byte key generated with OpenSSL be converted to hex?

This is an answer to your revised question, although it doesn't seem to make any more sense:

Hex is just another way to represent your data. It is neither more nor less secure than the binary representation or any other representation. Its all about convenience when dealing with this numbers.

As humans we tend to operate with data encoded in the decimal system. Computers on the other hand operate with binary data. However, the problem with binary data is that it tends to get quite long and error prone when you as a human have to deal with it. It is much more easy for us to remember or copy 46 rather than 0b101110.

The hex representation is a a good compromise, because:

A single character encodes four bits, therefore making it shorter than the appropriate binary representation.
It is quite easy for humans to handle. Basically everyone is used to 0-9 and A-F.
Is is really easy to convert data from binary into hex and vice versa.
It can be represented in ASCII without any problems. Random binary data on the other hand looks like complete gibberish and gets messy because of different encodings and such.

Yet, at the end of the day it is all representing the same information.


What does "G2" mean when used with X509 certficates and certificate authorities?

Yes, G stands for "Generation". When CA needs to get a new chain they just increment the generation number.

For example GoDaddy's signatures:

G3 - sha256WithRSAEncryption
G4 - ecdsa-with-SHA384


Can we encrypt part of the XChaCha/XSalsa nonce?

First the XChaCha20-Poly1305 basics

Why one may need XChaCha20
ChaCha20 is 20 round from the ChaCha family. The Bernstein version of ChaChax has a 64-bit nonce and 64 bit counter. Bernstein argued that this should be enough in the XSalsa paper

There is a standard argument that a 64-bit nonce is long enough. Nonce security does not mean unpredictability; it means uniqueness. Applications can generate a nonce as a monotonic timestamp or simply a counter 1,2,3,...

For long-lived keys, the 64-bit nonce of ChaCa20 is too short to use securely since with the birthday attack around the 2^32 messages one will have 50% of hitting the same random nonce that will at least result in the loss of the confidentiality.
XChaCha20 is based on the IETF version that uses 96-bit nonces.

The security of ChaCha20-Poly1305 with random nonces
The ietf' docs say that after around $2^{96}$ messages one should expect a collision with the birthday attack. 50% is very advantageous for the attacker and a more conservative one is generating at most $2^{80}$ nonce so that the collision probability is $\frac{1}{2^{32}}$. And, still, this $2^{80}$ message under one key should be enough for all. Therefore, the XChaCha20 is safe to use with random nonces. The security reduced to the security of the ChaCha20-Poly1305

How the ChaCha20-Poly1305 works

The 128-bit key and the first 128-bit (16-byte) of the uniform random nonce is processed with the HChaCha20
The HChaCha20 returns two 128 bits.
The remaining 64-bit ( 8-byte) of the nonce is appended with 4 null bytes.
xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
     subkey = hchacha20(key, nonce[0:15])
     chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23]

     return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)

Back to Questions

My question is could we encrypt the 2nd part of the nonce by running an additional initial round (HChaCha20) with the 16 bytes of the nonce and the key?

I'm reading this like this
```
xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
     subkey = hchacha20(key, nonce[0:15])
     subNonce = hchacha20(key + nonce[0:15], nonce[16:23])
     chacha20_nonce = "\x00\x00\x00\x00" + subNonce
     return chacha20_encrypt(subkey, chacha20_nonce, plaintext, blk_ctr)
```

To decrypt the other side must follow the same steps since they are not reversible! Therefore you need to send the nonce[16:23] as it is.
Therefore is no need for this since we expect that the nonce is generated uniform randomly. If you want to really do it, you can, you will get no advantage on the brute-force side. The attacker will still need to search over 128-bit. As a result, this adds nothing at all to the security.

I presume this would compromise something somewhere. It seems like a very simple and cheap way to make a brute force more difficult. The additional round(s) would take about 10ms.

It doesn't compromise anything at all but also doesn't provide any at all in the security of the XChaCha20-Poly1305. The brute-force attack, as mentioned above, will still need for a 128-bit key search.


A universal circuit is one that can compute any circuit. Specifically, it receives as input the description of another circuit and an input, and it outputs the computation of the given circuit on the given input. In cases where you want to hide the structure of the circuit being computed, a universal circuit can achieve this for you.


Fermat's little theorem $$a^p \equiv a \pmod{p} \Leftrightarrow a^{p-1} \equiv 1 \pmod{p}(p \nmid a)$$

so next divides $e$ with $p-1$:$$e=(p-1)r+s;$$ $$s\equiv e \pmod{p-1};$$
so we get $$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p}$$
 follow Fermat's little theorem $g^{p-1} \equiv 1\pmod{p}$ finally we get :$$g^{(p-1)r+s} \pmod {p} \equiv (g^{p-1})^rg^s \pmod{p} \equiv g^s \pmod{p}$$ $\Leftrightarrow$
$$g^e \pmod{p} \equiv g^{e \pmod{p-1}} \pmod{p}$$


Does Benford's law hold against encrypted data?

No, Benford's law does not hold.

As a simple example, assume a block size of $8$ bits, so the values are uniformly distributed in the half-open interval $[0, 256)$. Benford's law predicts that the probability of a leading digit occurring is strictly decreasing for increasing digits. However, it's easy to see that values leading with any digit $d \geq 3$ is equally likely.

For $d=3$, the only choices are $x \in [30, 39]$ and $x = 3$, while for $d=4$ the choices are $x \in [40, 49]$ and $x = 4$, and so on for every $d \geq 3$. All of these have exactly $10 + 1 = 11$ choices that occur with equal probability. This contradicts Benford's law's prediction that the probability is strictly decreasing.

We do have a higher chance of $d=1$ and $d=2$, but this is strictly because of the choice of our base. If we chose a base $b$ such that $b^k = 256$ for some integer $k$, then every leading digit is equally likely.


How to judge a determinant equals non-zero in cryptography?

For linear system $Ax = \beta$ with a vector on $n$ unknowns $x$, $A$ is the Vandermonde matrix, produced with powers of $c_i$. For such a matrix, determinant is a product of $(c_i - c_j)$, and so is non-zero for different $c_j$ in the set of field elements.


AES-256, CBC, plaintext length is multiple of block size: Does PKCS #7 padding weaken the encryption?

But does the padding precipitate a weakness in the encryption?

If padding oracle exist then you can decrypt the entire ciphertext in 128 tries per byte (on average). However, similar plaintext oracle attacks may be about as strong, and plaintext oracles are not just about CBC mode either. You will need to use an authenticated cipher (such as AES-GCM) to avoid plaintext oracle attacks.
Otherwise the answer is right, it doesn't weaken the encryption. Good ciphers should be even IND-CPA secure, which means that they are secure even if the adversary controls the plaintext.
And yes, padding may hide some information about the plaintext size, but you should not overestimate the security that this provide. Attackers may for instance try and make you put the plaintext on a block boundary, getting back precision when it comes to plaintext size estimates.

But is this true for AES-256?

AES is a block cipher; padding only applies to the specific mode in which the cipher is used. And in such a sense, it is more an issue for the mode of operation than the cipher. AES-256 is certainly considered a secure block cipher, so the trick is to use it using the correct mode. Generally a cipher mode that doesn't require padding such as the aforementioned GCM mode (which in turn is based on CTR mode) should be preferred.
Actually, only a few modes such as CBC (and the barely mentioned PCBC) and ECB require padding. They are not used too much anymore for new systems by modern cryptographers.


Should I be using RSA to Encrypt and ECC to Sign?

Both RSA and ECC can be used to encrypt/decrypt or sign/verify data. Neither is efficient when it comes to doing either (for larger amounts of data). That's why in general a symmetric cipher such as AES (in a specific mode) is used to encrypt/decrypt the bulk of the data. A secure hash such as SHA-512 is used to perform a one-way compression when doing a sign / verify method. A combined asymmetric algorithm and symmetric algorithm is called a hybrid cryptosystem.

The most common/recent methods would be to use RSA-OAEP and AES-GCM for encryption and RSA-PSS with SHA-512 for signing. For ECC you can do EC-IES with AES-GCM for encryption and ECDSA with SHA-512 for signing. These can be mixed any way you want. Other variants are possible of course.

Generally you would sign the message first and then encrypt it. Otherwise somebody could strip the signature from the file and sign it himself.  You will need a minimum of two key pairs of course, one for the sender and one of the receiver. The AES keys should be generated specifically for encrypting the single message.


Would buffering socket send resist timing attacks

It will only help to a certain degree.

If you want to protect against ciphertext attacks you cannot just add random time. The reason for that is that the random time you add is probably in a range. Or in your case, the period between calls will be in a certain range.

This means that if you have a large enough sample set you can figure out the deviation of the calls. Say you find out the maximum timeout. If the call takes maximum + x then x will be the time that the cryptographic operation takes.

Of course, for this to become a problem, you need to have a bigger data set. Computers and networks are however insanely fast, so usually creating a bigger data set is often not a problem.

If you try to mess with things like buffering of networked data you may also have to protect against attackers trying to circumvent the buffering issue. The network is the initial interface for an attacker, so it will be the primary attack surface.

The network buffering and cryptographic computations are not directly related. This solution would tie the network implementations with the protection of cryptographic algorithms. This is probably not a relationship that you want to maintain.

Your solution will also not protect against DPA attacks or attacks on the CPU itself (using access to the CPU from user accounts). So the protection is limited to the networking interface.

Another issue is that CPU scheduling can be pretty obnoxious. Sometimes an operation may take much longer than average. In that case the timeout may not be sufficient.

All in all, this should definitely not be the only protection against side channel attacks, and the limitations of the approach should be well understood.


Am I understanding AES GCM implementation correctly?

Well, I'm unfamiliar with this specific C# library, and so I can't answer questions about its API.  I could guess, but I suspect you want something better than that.

However, I can answer generic GCM questions.

1a. What does the AAD consist of?

Well, AAD is another service that GCM provides.  When encrypting messages, it is actually quite common to want to bind some context to the encrypted message; specifically so that message cannot be decrypted in a different context.  What GCM does is stir in the AAD along with the ciphertext data when generating the tag; if the decryptor doesn't have this same AAD when he decrypts, he will compute a different tag, and so the decryption attempt will fail.  Hence, this plaintext AAD is bound to the ciphertext; you need both to decrypt.

Here's one example of where you might use this: in a TLS record, you have a record type that is not encrypted, followed by encrypted data.  One of the things you might want to make sure is that an attacker cannot extract an encrypted data, and reinject it with a different record type.  In this case, you can include the record type in with the AAD; then, if the attacker does reuse the ciphertext with a different record type, the decryption will fail, and the record that the attacker modified will be rejected.

1b. Where should the AAD be stored?

That depends on what you're using it for.  You might be authenticating unencrypted data that is included with the encrypted message (as in the TLS example); in that case, the decryptor would just extract it from the message.  You might be authenticating some state that is shared between the encryptor and the decryptor; in that case, the decryptor would extract it from his database.  You might be doing a combination of both; in this case, we'd extract parts of the AAD from different places.

1c. Is it detrimental to the operation of the cipher if I leave the AAD blank?

Not at all.  AAD is a service that GCM provides for you; if you don't need that specific capability, you can just leave it blank.


Why is GCM not vulnerable at the birthday bound for 128 bit IV?

Actually, it turns out that GHASH on 128 bit values is a permutation (unless $H=0$; this happens with probability $2^{-128})$

GHASH of a 128 bit value $X$ simplifies to $\text{GHASH}_H(X) = H \times X$, where $H$ is a function of the key (that is, will always be the same for a specific key), and $\times$ is multiplication in the field $GF(2^{128})$.

This is a permutation, as $GF(2^{128})$ is a field, and multiplication in a field by a fixed nonzero value is always a permutation.

As for the 'collision' you mention in your comments, that actually can't happen.

If we have $H \times I_1 = 128$, that means that $H \ne 0$ and $I_1 = 128 \times H^{-1}$

If we have $H \times ((H \times I_2) \oplus 128) = 0$, that can happen only if $H = 0$ (which can't happen if the first equation holds) or $(H \times I_2) \oplus 128 = 0$, which holds only if $H \times I_2 = 128$, that is, if $I_2 = 128 \times H^{-1}$

Hence, for both to hold, we must have $I_1 = I_2$, and thus this isn't a 'collision'


No, the signer is per definition in possession of the secret signing key and thus can always produce signatures for any message of his choice.

Consequently, a notion of unforgeability is not meaningful with respect to the signer. For a signature scheme one requires unforgeability for parties who are not in possession of the secret signing key but only the public verification key.

You may also look at this answer for a more detailed discussion on attacks and attack models for digital signature schemes.


Question on proof of coin-tossing in "how to simulate it"

Actually, a probabilistic adversary $A$ can be viewed as a deterministic adversary with a random tape: $A$ just picks a random string in the beginning and then run deterministically according to that fixed string. In the proof, the simulator $S$ uses the real-world adversary $A$ as a black box but can control its random tape (because a random tape always contains fair random strings that can be generated by anyone). So, $S$ can simulate the output of a probabilistic adversary $A$ by first choosing a random string $r$ then dealing with the resulting deterministic adversary $A'=A(r)$.


How many bits of entropy can I expect from /dev/urandom in iOS?

I mailed Craig Federighi recently about this, concerned that macOS wasn’t capable of generating >128bit quality keys.

He responded!

  “The source you were referencing is out of date.  You can find more current informations here:   FIPS certification document, section 7: "The NDRNG feeds entropy from the pool into the DRBG on demand.  The NDRNG provides 256-bits of entropy.””


AES is generally very fast when implemented in hardware.  On my laptop, a Core i7 8665U, AES-128 operates at 6758 MB/s.  It is slower when implemented in software, and it is much slower when implemented in software in a constant-time implementation.  A naive software implementation that is not constant time runs as 367 MB/s on my system.
You mentioned that you're looking for smartphone processors.  Some of the newer processors will have AES acceleration available, but not all will.  If you're looking for an algorithm that will perform well on almost all systems, be constant time, and cryptographically secure, I'd recommend ChaCha20, or, if you really need screaming performance, ChaCha12.  ChaCha20 on my system runs at 3513 MB/s and will clearly outperform AES where hardware acceleration is not present.  ChaCha12 performs almost as well as or better than many non-cryptographic PRNGs.  It would be my choice for a PRNG, whether cryptographic or non-cryptographic, because it is fast, secure, and has no weak seeds (unlike many non-cryptographic PRNGs).  It is also the default PRNG for the Rust rand family of crates, and ChaCha20 is used in the Linux kernel to generate random numbers.
Note that any performance comparison of PRNGs also has to consider not just generating the values but getting them into a place where they can be used.  For example, AES-NI instructions would probably perform even better than I listed above if you only encrypt the same data in place using vector registers.  However, the performance drops off when you must load and store data to and from memory because that is more expensive.  I suspect the PCG paper does not take that into account in a practical way.
Of course, performance measurements on my system are not reflective of other systems and if you need to know how things work on a particular system, you should benchmark it yourself.  You may also want to look at SUPERCOP, which benchmarks many cryptographic primitives on various types of hardware to answer your questions.  It's likely that you'll find hardware that is comparable to modern and older processors, including a variety of ARM and ARM64 hardware.
A final note about performance: you don't always need to use the fastest algorithm for a job.  It is likely that in most applications, the generation of random numbers is not the bottleneck, and the benefits of using an algorithm like ChaCha (such as its lack of weak states and better quality) may outweigh the fact that it is slightly slower.  Your benchmarking would need to focus on identifying places that are a bottleneck, and improving those whenever possible.


RSA: Given $n$ and $\varphi(n)$, find $e$ such that $e=d$

If you know the factorization of $\phi(n)$, this can be done like this:

The factorization gives you various prime powers as factors of $\phi(n)$, let's call those $p_i^{e_i}$. Then:

For each $p_i^{e_i}$ with $p_i>2$, the roots of the polynomial $x^2 - 1 = 0 \mod p_i^{e_i}$ are $1$ and $p_i^{e_i}-1$ and there are no other roots. This can be proven by using Hensel lifting for the two roots of the polynomial $x^2-1 \mod p_i$.
For powers of $2$, Hensel lifting the polynomial $x^2-1$ also gives you solutions, but it's more complicated if you want to find all of them, because $f'(r)=2r$ will be $0$ for some root $r$. If you want to find just one, then just use $x=1 \mod 2^x$, where $x$ is the power of $2$ in the factorization of $\phi(n)$. Edit: As an example, every odd number is a square root of $1$  modulo $8$, and modulo $16$ the square roots of $1$ are $\{1,7,9,15\}$.
For each prime power you have a set of two roots $r_1$ and $r_2$ (in a formal prove, you should have indices for the prime powers as well). Choose for each prime power either $x=r_1 \mod p_i^{e_i}$ or $x=r_2 \mod p_i^{e_i}$. If you don't want the trivial solutions $1$ and $-1$, make sure to avoid the 'all $1$' and 'all $p_i^{e_i}-1$' roots.
Use Chinese remainder theorem to assemble the solution $x \mod \phi(n)$

Edit: In the question you only wanted square roots of $1$, which is either $1$ or $-1$ mod any prime $p$. More generally, if you want to find square roots of arbitrary elements, there are also algorithms for that, e.g. Tonelli-Shanks, which work for any prime $p$. Hensel lifting then gives you the roots in the prime powers (but you need to adapt the polynomial), and then assemble the solution via CRT.

Edit:
Of course the choice $e=d$ makes the RSA cryptosystem with public key $(N,e)$ completely unsafe - the value of $e$ is public and you have to assume by Kerckhoff's principle that the attacker knows your system, in this case that you use such a defining equation.


Constructing an integer with specific totient without factorization

Remark: $p$ and $q$ are distinct odd primes (if not, we can factor $N$), thus $\phi(N)=(p-1)(q-1)$. Define $p'=(p-1)/2$ and $q'=(q-1)/2$. It holds $\phi(N)=4\,p'\,q'$.

What's asked is not always possible. As a counterexample, assume $k=2$ (which is a possible $k$, from above remark), and $p\equiv 3\equiv q\pmod4$ (which covers about 25% of RSA keys). If we could find $N^*$ with $\phi(N^{*})=\phi(N)/k$, it would hold $\phi(N^*)=2\,p'\,q'$ with $p'$ and $q'$ odd. Therefore¹ $N^*$ would be of the form $2^s\,r^t$ with $r$ prime, with $\phi(N^*)=(r-1)\,r^{t-1}$. Therefore we could factor $N^*$, yielding $r$ and $e$, thus $\phi(N^*)$, thus $\phi(N)$, allowing to factor $N$.

Still with $k=2$, $p\equiv3\pmod4$, but this time $q\equiv5\pmod8$ (which covers another about 25% of RSA keys), we have $\phi(N^*)=4\,p'\,q''$ with $p'$ and $q''=(q-1)/4$ odd, and the two possible (non-exclusive) options are²

that $N^*$ is of the form $2^s\,r^e$ with $r$ prime, which we handle as above.
that $N^*=(2\,p'+1)\,(2\,q''+1)$ with $(2\,p'+1)$ and $(2\,q''+1)$ distinct primes, in which case $N^*=p\,((q+1)/2)$, thus $\gcd(N,N^*)$ will be $p$, yielding a factorization of $N$.

More generally, if what is asked was possible, there is some chance that at least one of the following holds:

$\gcd(N,N^*)$ reveals a factor of $N$.
we can factor $N^*$ (including but not limited to $N^*=2^s\,r^t$), then can compute $\phi(N^*)$, thus $\phi(N)$, allowing us to factor $N$.

I have a feeling that's a fair chance for random $N$ when $k$ is small.

Independently: When $k$ is large, and especially when it is prime, it's value is revealing: it must divide $p-1$ or $q-1$, thus $\gcd(N,j\,k+1)$ will be $p$ or $q$ for some $j$, and it is worth trying to find $j$ by enumeration at least when $\sqrt N/k$ is small enough and there is no reason to believe that $\max(p,q)/\min(p,q)$ is large.

When $k$ has a large prime factor $k'$ that we can find, that $k'$ must divide $p-1$ or $q-1$, and we may be able to use the same approach to factor $N$. And with a bit of luck, the product $k'\,k''$ where $k''$ is a large factor of $k/k'$ will divide $p-1$ or $q-1$, allowing to factor $N$. And even if we can't fully factor $k$, because the largest factor we find is composite, it  still has a fair chance to divide $p-1$ or $q-1$, allowing to factor $N$.

I vaguely conjecture (would not bet the house) that there are vanishingly few semiprimes $N$ such that an oracle knowing its factorization could reveal $k$, $N^*$ as in the question without the combination of the above techniques being of great help to factor $N$. In other words, what's asked would demonstrably be impossible for overwhelmingly most $N$.

¹ This uses the following lemma: if $\phi(m)\equiv2\pmod4$, then $m$ is of the form $2^s\,r^t$ with $r$ prime. Proof of that lemma can be by contraposition using the expression of Euler's totient: $$\phi\left(\prod_{p_i\text{ distinct primes}} {p_i}^{e_i}\right)=\prod_{\text{same }(p_i,e_i)}(p_i-1)\,{p_i}^{(e_i-1)}$$

² This is left as an exercise to the reader, using the same kind of argument as for the above lemma.


Difference between stream cipher and block cipher

A block cipher is a deterministic and computable function of $k$-bit keys and $n$-bit (plaintext) blocks to $n$-bit (ciphertext) blocks. (More generally, the blocks don't have to be bit-sized, $n$-character-blocks would fit here, too). This means, when you encrypt the same plaintext block with the same key, you'll get the same result. (We normally also want that the function is invertible, i.e. that given the key and the ciphertext block we can compute the plaintext.)

To actually encrypt or decrypt a message (of any size), you don't use the block cipher directly, but put it into a mode of operation. The simplest such mode would be electronic code book mode (ECB), which simply cuts the message in blocks, applies the cipher to each block and outputs the resulting blocks. (This is generally not a secure mode, though.)

Some early encryption schemes like the one used by Caesar could be categorized as a "block cipher with 1-character blocks in ECB-mode". Or generally, everything that has a code book.

We usually use other modes of operation, which include an initialization vector and some kind of feedback, so that every block of every message is encrypted a different way.

A stream cipher is a function which directly maps $k$-bit keys and arbitrary length plaintexts to (same arbitrary length) ciphertext, in such a way that prefixes of the plaintext map to prefixes of the ciphertext, i.e. we can compute the starting part of the ciphertext before the trailing part of the plaintext is known.
(Often the message sizes might be limited to multiples of some "block size", too, but usually with smaller blocks like whole bytes or such.)

If a part of the plaintext repeats, the corresponding ciphertext usually is not the same – different parts of the message will be encrypted in different ways.

Often such stream ciphers work by producing a keystream from the actual key (and maybe an initialization vector) and then simply XOR-ing it with the message – these are called synchronous stream ciphers.  Other stream ciphers might vary the encryption of future parts of the message depending on previous parts.

Some block cipher modes of operation actually create a synchronous stream cipher, like CTR and OFB mode.

You should never reuse a key (and IV, if applicable) of a synchronous stream cipher (which includes block ciphers in streaming modes) for different messages, since this can lead to compromises. (And even for the same message it will show that you repeated a message.)

Note that in actual usage you will also want a MAC, e.g. integrity protection, for your message. (Some schemes are broken in case of a chosen-ciphertext attack, for example, and such a MAC will prevent this (if you only pass the message to the decryptor after checking the MAC).)


Is it secure to choose d in a RSA key pair?

Selecting a small $d$ is known to be insecure.

Wiener has shown in 1990 that if $\log d \leq \frac14 \log N$, the private exponent $d$ can be reconstructed from the public key $(N,e)$.

If you're interested in making the private computational cost cheaper, then I would suggest that RSA is not the best solution; I would recommend you start looking at Elliptic Curve based solutions.


What is required to decrypt an encrypted file?

KeyCzar is a cryptosystem on its own. It defines a container format, with a header, IV, ciphertext and possibly a (symmetric) signature. The keys it uses are also not just keys, they contain additional information. These "keys" may even contain multiple keys, i.e. an additional one for the signature creation.

To decrypt KeyCzar encrypted files you need a program that is compatible with KeyCzar. Many libraries can be downloaded from the KeyCzar GitHub site. Alternatively you can implement your own library given the specifications hosted on the same site. KeyCzar can be used from the command line as well.

In general you need to understand the protocol (and protocol version) that is being used to encrypt/decrypt files. Just specifying that something is encrypted using AES-256 doesn't say much at all.

Note that KeyCzar also contains methods for asymmetric encryption. You should however first be able to trust the public key of the receiver for that to be useful.


Using non-standard constants for SHA-256

Those are "nothing up my sleeve" numbers, their values aren't central to the security of the algorithm. Nevertheless an intent to arbitrarily choose different and thus incompatible values probably means something else you're doing is a bad idea.


Standard format to encode AES cipher and random IV

Is there a standard or at least "commonly used" format to format the result?

PKCS #7 (and CMS which is a further development) describes a standard format for encrypted data. While it's mainly meant for public key encrypted data, it also has options for symmetric keys. It's rather complex due to all the features it supports, however, so unless you can find a library that does all the encoding and parsing for you, you may want to do something simpler if you only need the format for your own use.

Another "format" that's probably quite commonly used is simply to concatenate the IV and the encrypted message (and then MAC, if applicable). However, that's not very discoverable.

  E.g. /usr/bin/openssl seems to concatenate "Salted___" + IV + cyphertext and then base64 encode everything. Would this be a recommended way?

Actually, "Salted___" in OpenSSL indicates password-based encryption, and the value that follows is not an IV for the cipher, but a salt for deriving the key and IV from a password. If you are using a key directly, rather than a password, you shouldn't reuse that format, or it'll just cause confusion.

  I want to store the encrypted text and still be able to decrypt it in 10 years with any PHP/Python/Java library.

Other than PKCS #7 or CMS, I would suggest using just plain ASCII to describe the format, cipher and mode and then concatenating the binary IV + data. It will expand the data, but space if usually cheap, and ASCII will always be readable.


Attack of the Middle Square Weyl Sequence PRNG

Lets look at the computations that the function does to the internal state.
We'll denote the state of the variables when we start the attack as $x_0 = (a, b)$ and $w_0 = (c, d)$, where I will use the notation $(i, j)$ to mean the 64 bit number which has $i$ as the upper 32 bits, and $j$ as the lower 32 bits (and so $a, b, c, d$ are 32 bits each).  Note that $x_0, w_0$ need not be the initial state of the PRNG, instead it's the state when the initial output was generated.
Then, the previous step exposes $b$ (and so that is known to the attacker).
Then, it squares $x_0$ modulo $2^{64}$, replacing $x_0 = (a, b)$ with $x_0^2 = (2 a b + (b^2 >> 32), b^2\  \bmod 2^{32})$.  As the attacker knows $b$, the attacker can replace this with the linear operation $x_0^2 = (h_0 a + h_2, h_1)$, where $h_0, h_1, h_2$ are known (to the attacker) constants (as it gives the same mapping from previous state to new state).
Then, the algorithm adds $w$ to $x$, that can be modeled as:
$x_0^2 + w_0 = (h_0 a + h_2 + c + \epsilon_0, h_1 + d)$, where $\epsilon_0$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened.
Then, it adds the constant $s$ to $w$, this can be modeled as $w + s = (c + s_{hi} + \epsilon_1, d + s_{lo})$, where $\epsilon_1$ is either 0 or 1, depending on whether a carry from the lower 32 bits happened (and $s = (s_{hi}, s_{lo})$
Then, it rotates $x$, giving $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$, and outputs the lower 32 bits $h_0a + h_2 + c + \epsilon_0$.
The new state is $x_1 = (h_1 + d, h_0a + h_2 + c + \epsilon_0)$ and $w_1 = (c + s_{hi} + \epsilon_1, d + s_{lo})$; that is, it is one of 4 linear functions of the previous state (depending on the values of $\epsilon_0, \epsilon_1$)
Continuing on for three more iterations, the resulting states will remain one of a small number of known linear functions of the initial state; the output will also be a linear function of the state.  With four outputs, the attacker can iterate through the possible $\epsilon$ values, and solve for the initial states.  If you go through the equations, you'll find that you can recover $c, d$ from the third and fourth outputs; using the value $c$ gives you the value of $a$ from the second output (and you're given $b$ as the first output).


What are the ways to generate Beaver triples for multiplication gate?

Nowadays, the most standard method is to use oblivious transfers. Oblivious transfer involve a sender with two messages $(m_0,m_1)$ and a receiver with a selection bit $b$. At the end of the protocol, the receiver learns $m_b$ (and gets no information about $m_{1-b}$) while the sender gets no information about $b$.

Suppose Alice and Bob want to generate a random Beaver triple over $\mathbb{F}_2$ (that is, a Beaver triple of shared bits). Alice picks $(x_A,y_A)$ at random from $(\mathbb{F}_2)^2$ and Bob picks $(x_B,y_B)$ at random from $(\mathbb{F}_2)^2$. Alice now picks a random bit $r_A$ and acts as sender in an oblivious transfer with the following pair of inputs: $(r_A, x_A \oplus r_A)$ ($\oplus$ denotes the xor). Bob uses $y_B$ as selection bit. If $y_B$ is $0$, Bob learns $r_A$; else, he learns $ x_A \oplus r_A$. Therefore, Bob learns $x_Ay_B \oplus r_A$.

The players now do the same thing in the other direction with a random bit $r_B$ and the bits $(x_B, y_A)$, so that Alice learns $x_By_A \oplus r_B$. Alice computes $z_A \gets r_A \oplus x_Ay_A \oplus x_By_A \oplus r_B$ and Bob computes $z_B \gets r_B \oplus x_By_B \oplus x_Ay_B \oplus r_A$. You can easily check that $z_A \oplus z_B = (x_A \oplus x_B)\cdot(y_A\oplus y_B)$, therefore $(x_A,x_B), (y_A,y_B)$, and $(z_A,z_B)$ form shares of a Beaver triple over $\mathbb{F}_2$.

Oblivious transfers require (expensive) public key primitives; the most common construction are based on the Decisional Diffie-Hellman assumption (like the ElGamal cryptosystem). However, it was shown some years ago that one can generate an arbitrary number of oblivious transfers, starting from a constant number of OT (say, 80) and "extending" them using only very cheap primitives. Therefore, players can generate arbitrarily many Beaver triples while using only a constant number of public key operations, and then only cheap primitives (hash functions). This is the reason why OT is nowadays seen as the best choice to construct Beaver triples. Other classical primitives used to generate Beaver triples include homomorphic encryption. The advantage, which might make it relevant in some cases, is that it allows to generate Beaver triples over large order fields without having to rely on the bit decomposition of one of the inputs (generating a single Beaver triple on a large order field $\mathbb{F}$ requires $O(\log |\mathbb{F}|)$ oblivious transfers in general, although there are methods to improve that).


Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?

The usual technique for having a group of prime size $q$ is to work modulo a prime $p$ such that $q$ divides $p-1$. The target group is then the subgroup of $q$-th roots of $1$ in $\mathbb{Z}_p$. To build such a group, first choose $q$, then selects random values $r$ until you find one such that $p = qr+1$ is prime. This is the way it is defined in the DSA standard.

The remaining part is: how to build $H_1$, the hash function which produces elements in the target group ? For that, you first use a hash function which produces values modulo $p$ (e.g. you use a PRNG seeded with the hashed data, and produce bit sequences of the size of $p$ until you find one which is between $0$ and $p-1$); then, you raised that value to the power $(p-1)/q$. The result is necessarily a $q$-th root of 1, and the whole is a "hash function".

As far as I know, such a group would fulfill the CT-CDH assumption -- i.e. there is no known way to break it. CT-CDH is a "weaker" assumption than standard CDH, but there is no proof that it is strictly weaker.

For your additional question: $R$ knows the $a_j$, which are random non-zero integers modulo $q$. $R$ can thus compute each $a_j^{-1}$ modulo $q$ (that's regular modular inversion). In the expression "$(D_j)^{a_j^{-1}}$, $D_j$ is part of a group of size $q$, so any exponent can be taken modulo $q$.


Why do we have fixed output length in the algorithm SHA1

SHA-1 is derived from MD4 and MD5, which are Merkle–Damgård type hash functions with a compression function based on a block cipher.

The initial values to an MD type hash function are essentially the plaintext to the block cipher, with the input to the hash function becoming the key. The maximum length of the hash is determined by the amount of bits of initial value, which is the same size as the block width of the cipher. A block width of five 32-bit words gives SHA-1 a state size and maximum output of 160 bits.

For SHA-1, there is no truncation of the block cipher state prior to output, so we have 160-bits in, and 160-bits out. This provided the required collision resistance of 80-bits as required by the lifespan estimate of how long the hash function was to be in service, which as of about 5 years ago was bumped to 112-bits.

If they so desired, a variable length output could have been implemented like they did with SHA-512/t, but since the maximum output length was the minimum security required, that was neither necessary nor wanted.


Constructions of PRF (Pseudo Random Function)

The most common efficient PRFs from specific assumptions are:

The Naor-Reingold PRF, which is based on the decision Diffie-Hellman assumption (DDH), and

The BPR PRF, which is based on the learning with error assumption (LWE).

Perhaps slightly less well-known is the NRR PRF, which is based on the hardness of factoring.


The Boneh-DeMillo-Lipton fault attack (RSA CRT)

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed does not hold.


What are the benefits of being able to choose (most of) the public key in a PKC?

That property lets a trusted n2-byte random string be
enough to make the rest of public keys fit into n bytes.
In particular, forward secrecy can be more efficient if the sender can store such a string, since the string can have been generated by the same party as generates the rest of the public keys.

Also, if for random private keys and independent n2-byte random strings r0 and r1,

the distributions
$\langle$ rest_of_public_key_(r0,priv_key) , r0 $\rangle$    ,    $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$
are indistinguishable

and

"encryptions" with   $\langle$ rest_of_public_key_(r1,priv_key) , r0 $\rangle$

provide confidentiality even against the private key holder

,   then you get a one-message-in-each-direction

oblivious transfer protocol against semi-honest receivers.


Can we replace the XOR operation in DES with some other operation?

Within the DES block cipher itself, the XOR operation is used at two different places:

On the input of S-boxes, XOR-ing 48 bits per round: 48 bits from a subkey (extracted from the 56-bit key), and 48 bits that are the output of expansion E. The 48-bit result forms the eight 6-bit inputs of the S-boxes.
On the output of S-boxes, XOR-ing 32 bits per round: 32 bits from the former (left) half of the state, and 32 bits formed by the eight 4-bit outputs of the S-boxes. The 32-bit result forms the new (right) half of the state.

If in 1 XOR is replaced by addition modulo 248 (or eight additions modulo 26), in both encryption and decryption, the cipher remains operative, in the sense that decryption remains the reverse of encryption. For something comparable in 2, XOR can be replaced with addition modulo 232 (or eight additions modulo 24) during encryption, and subtraction during decryption (with the negated input being the output of S-boxes). For interoperability, such changes would need to define unambiguously the limits and ordering of input and output bits.

Any of these changes would remove one notable property of DES: the complementation property, stating that $\operatorname{DES}_\overline K(\overline P)=\overline{\operatorname{DES}_K(P)}$. Depending on context, that could be neutral (e.g. with any bit in plaintext fixed), a benefit (e.g. adding one bit of resistance to brute force), or a disaster (e.g. when the complementation property is part of a strategy against side channel attacks).

These changes would potentially slow down implementations of DES, both in hardware (due to carry propagation) and software (by breaking common optimizations).

The impact on security is debatable. Only one thing is obvious: the S-boxes have been carefully designed in a context with XOR for near-optimal resistance to differential cryptanalysis (and later found fair against other attacks), thus we'd be moving into uncharted territory. Resistance against side-channel attacks could be lessened, even without consideration for the lost complementation property. I would be surprised if practical security was otherwise lessened under the assumption of a single unknown key, but would not bet on related-key attacks, or firmly commit on anything.

All in all, I see no good rationale for such change.


How can i calculate prime of Elliptic Curve?

This prime $p$ corresponds to the size on the base field $\mathbb F_p$ on which is defined the elliptic curve. It has not been computed, it has been chosen. It is chosen to satisfy a few properties, like, of course, being prime, but also being large enough (here, 256 bits), and allowing fast computations modulo $p$.
Maybe when you say "prime elliptic curve", you mean elliptic curves with a prime number of points? The number of points is not the prime $p$, and is computed using the Schoof-Elkies-Atkin algorithm.


Cryptographic algorithms comparison, AES vs Camellia

Both AES and Camellia are block ciphers with a block size of 128 bits and three different key sizes: 128, 192 and 256 bits.

In both cases, when using a bigger key size, like 192 or 256, the cipher will do additional rounds. AES will do respectively 10, 12 and 14 rounds for 128 bits keys, 192 and 256, while Camellia do 18 rounds for 128 bits keys and 24 rounds for both 192 and 256 bits keys.

So far so good, all this information can be found on Wikipedia.
So, you want to compare both, but what kind of metrics do you want to use?
What are the key performance indicators you're valuating most? Is it the raw speed? Is it the security against differential power analysis? Is it the parallelization of the computation? Is it the number of line of code in an implementation? Is it the maximal code footprint? Is it the resistance against algebraic attacks?

I'll do the assumption that what you really want to do is comparing "implementations" of both ciphers, not the underlying algorithms (there certainly are papers doing so for both ciphers).

In order to compare implementations, you have two options:

Either you take reference implementations, without much optimization and compare then
or you take the "best" implementations out there and compare them.

As stated by Maarten in comments, AES being the most used block cipher nowadays, the currently best implementations all rely on the fact that there are hardware accelerators for them in almost all processors. However, it appears that Camellia can also be accelerated using some of the same tricks as AES [1]. I recommend you to take a look at this thesis, since the author is comparing different block ciphers, including both AES and Camellia, and tries to optimize their raw speed.
According to its results, Camellia is still 4 time slower than AES, even using the AES-NI tricks.

Now that last paragraph takes into account only the "raw speed" of the implementations, but an implementation can also be hardened against certain kind of attacks depending on the threat model scenario it tries to address. For instance, bit-sliced DES introduced by [2] is faster than standard DES (and is constant time), but there might be other hardening methods which are not necessarily improving the performance, like for instance the "infective countermeasures for RSA" against fault attacks, which add an overhead, or the "masking" used in RSA implementations meant to resist to DPA attacks.

In order to perform such comparisons between the "features" of the implementations, then you need to probably review the code and check what's being done. (Or have a list of the "features" the implementations sports.)

In the end you could also compare the usage of both ciphers, or the patents, or the amount of paper written about both, etc.

Notice that you can also look for existing benchmarks out there, if you what you care about is the speed, like for example the ones done by Crypto++, or the ones found in the above-mentioned thesis.

References

[1] Kivilinna, Jussi. "Block Ciphers: Fast Implementations on x86-64 Architecture." MSc diss., University of Oulu, 2013.
[2] Biham, Eli. "A fast new DES implementation in software." In FSE, vol. 1267, pp. 260-272. 1997.


How to calculate y value from ((y*y) mod prime) efficiently

By "ECC-224", I suppose that you mean "NIST curve P-224". This actually matters.

To compute the square root of $z$ modulo a prime $p$, there are several methods which depend on $p$. If $p = 3 \pmod 4$ then it suffices to compute:

$$ y = z^{(p+1)/4} \pmod p$$

If $z$ is indeed a square, this will yield a value $y$, and the other square root will be $-y$ (to check whether $z$ is really a square, just compute $y^2 \pmod p$ and see if it yields back your value $z$ or not).

Now, in NIST curve P-224, computations are done modulo a prime $p$ which is such that $p = 1 \pmod 4$, and the method above does not work. You have to use Tonelli-Shanks algorithm which is slightly more complex, and, in the general case, requires knowledge of a value modulo $p$ which is not a square (half o values modulo $p$ are not squares, so finding one is not hard, but this is enough to make the algorithm, in all generality, probabilistic).


Birthday attack for combination of hashes

We first need to refine the definition of the problem.

The most natural assumption in a cryptographic context is that "How many hash values do you have to calculate" implies that we consider a strategy that minimizes that number of hashes.

In theoretical cryptography, a common assumption is that we are allowed arbitrarily large amount of memory, and use of arbitrary computing power. We'll assume we use that to cache the hash computation, but healthily check the required amount of memory and processor time in the end, for bonus points.

We'll also assume that we are actually asked the expected number of hash calculations required by one of the best possible strategies. And as common in cryptography, we'll be content with approximations, and/or disregarding low $n$, if that helps.

We need to define "collision". When talking about collision in a hash, it is understood $x$ and $y\ne x$ with $h(x)=h(y)$. But here the later condition is replaced by $h(x)\oplus h(y)=h(r)\oplus h(s)$, so what about the rest? That could be:

$(x,y)\ne(r,s)$. In that case the answer is zero assuming $n>0$ : we take any two distinct $x$ and $r$ and we know that $(x,x)$ and $(r,r)$ is a solution, without making any hash. $(x,r)$ and $(r,x)$ does the trick too. We'll disregard that option 1 from now on.
Distinct $x$, $y$, $r$, $s$; at least four hashes are required.
$x$, $y$, $r$, $s$ such that possible equality between terms does not result in a collision irrespective of the hash lagorithm; for $n=3$ that can be (showing inputs and outputs in binary)

$x=\mathtt{000000}$ with $h(x)=\mathtt{010}$
$y=\mathtt{000001}$ with $h(y)=\mathtt{001}$
$r=\mathtt{000010}$ with $h(r)=\mathtt{010}$
$s=y$; that works specifically because $x=r$.

Options 2 and 3 are not equivalent; option 2 falsely looks simpler (we fall into this trap later..).

The result obviously depends on the particular "hash algorithm", which in a cryptographic context is assumed known. Perhaps we could find an answer by looking at this algorithm. But it is not given in the question, thus in a cryptographic context our default fallback option is to consider that the expected number of hashes is for a random function $h:\{0,1\}^{2n}\to\{0,1\}^n$ (that notation merely states the size in bit of input an output of $h$). There are $2^{(n2^{2n})}$ such functions, thus $2^4=16$ for $n=1$, $2^{32}$ for $n=2$, and a whooping $2^{192}$ for $n=3$.

There's an easy way to plausibly justify that $2^{n/4+1/2}$ hashes allow to find a collision with fair odds for all but small $n$. Argument:

Evaluate $h(i)=h_i$ for $2^{n/4+1/2}$ incremental values of $i$ starting from $0$, assimilating integers to bitstrings in big-endian binary (as common in cryptography); that is, for $n=4$, $h_5=8$ means that $h(\mathtt{00000101})=\mathtt{0100}$.
For all $(x,y)$ with $0\le x<y<2^{n/4+1/2}$ consider $h'(x\|y)\gets h(x)\oplus h(y)$ and tabulate the nearly $2^{n/2}$ values $h'(x\|y)$.
$h'$ is not a random function, but if we nevertheless abuse the birthday problem for cryptographic hashing (a common thing in cryptography), that tells us there are near 40% odds of collision for $h'$ in the standard definition of that for hashes.
Such collision would allow one for $h$ as asked, always matching our option 3.
The collision is not quite always one per option 2; but odds that is does not are vanishingly low, considering that it occurs only if we found a collision for $h$ in the standard definition of that for hashes, after a mere $2^{n/4+1/2}$ hashes.

By turning that strategy into one that searches for collision of $h'$ for incremental values of $i$ (rather than having computed all hashes $h_i$), we can make the resulting strategy optimum for a near complete subset of option 3, including option 2; see below.

We now proceed to reason about what an optimum strategy must do.

It must computes hashes only for different inputs (otherwise we could devise a better strategy that does).
And since the function $h$ is random, what said different inputs are does not matter to the desired expected number of hashes (that is, the mean number of hashes for all possible $h$). So we can restrict to strategies always using inputs in lexicographic orders, as we did in example 3. We can safely state that the "..a $2\cdot n$ bit number.." part of the question is large enough that this strategy won't run out of input values; that would still hold if we removed the factor of two, including for $n=1$.
After having computed $h_i$, the strategy must stop if the computed hashes now allows to exhibit distinct $x$, $y$, $r$, $s$ at most $i$ with $h_x\oplus h_y=h_r\oplus h_s$. At least one of $x$, $y$, $r$, $s$ must be $i$ (otherwise the strategy would not be optimum), and reordering $x$, $y$, $r$, $s$ in non-decreasing order leaves a strategy valid and optimal.
An optimum strategy as restricted must thus try increasing $s$ and stop precisely

for option 2, when $s>2$ and the $h_s$ just computed and cached matches $h_x\oplus h_y\oplus h_r$ for some $x$, $y$, $r$ such that$0\le x<y<r<s$; which case $x$, $y$, $r$, $s$ is a collision.
for option 3, additionaly

when $s\ge2$ and the $h_s$ just computed mathches an earlier $h_r$ with $0<r<s$, in which case $x=0$, $y=0$, $r$, $s$ is a non-trivial collision;
or when $s>1$ and $h_s=h_0$, in which case $x=0$, $y=1$, $r=1$, $s$ is a non-trivial collision;
or when $s=1$ and $h_s=h_0$, in which case $x=0$, $y=0$, $r=0$, $s=1$ is a non-trivial collision.

One implementation option for option 2 is four nested loops with $s$ growing starting from $0$ at the outer, computing and caching $h_s$, then for $r$ from $2$ to $s-1$, $y$ from $1$ to $r-1$, $x$ from $0$ to $y-1$, terminating if the newly computed $h_s=h_x\oplus h_y\oplus h_r$, in which case $x$, $y$, $r$, $s$ is a collision.

There are $s(s-1)(s-2)\over6$ combinations of $x$, $y$, $r$ for a given $s$. Each corresponds to some $h_x\oplus h_y\oplus h_r$, these are not necessarily different, and finding a collision among these does not by itself allow the algorithm to stop. We consider all $h$, thus for each new $h_s$, odds $p_s$ that the strategy stops having computed $h_s$ assuming that it did not previously stop are (at most) $\tilde{p_s}={s(s-1)(s-2)\over6}\,2^{-n}$. It holds that $p_s\lessapprox\tilde{p_s}$, with equality when it happens that the $s(s-1)(s-2)\over6$ values of $h_x\oplus h_y\oplus h_r$ all are distinct.

Odds of stopping before computing $h_j$ (that is, having computed $j$ hashes or less) are
$$q_j\;=\;1-\prod_{3\le s<j}(1-p_s)\;\lessapprox\;\sum_{3\le s<j}p_s\;\lessapprox\;\sum_{3\le s<j}\tilde{p_s}\;\lessapprox\;{6\over2^n}\sum_{3\le s<j}(s-1)(i−2)(i−3)$$
with that approximation tight as long as $j\ge4$ is small enough that $q_s$ remains small and there are few collisions among the $(j-1)(j−2)(j−3)\over6$ values of $h_x\oplus h_y\oplus h_r$ previously computed when $h_{j-1}$ gets computed.

Further, induction shows that
$$\sum_{3\le s<j}(s-1)(i−2)(i−3)\;=\;{j(j-1)(j−2)(j−3)\over4}\lessapprox{j^4\over4}$$
and that approximation is tight for all except small values of $j$.

Therefore odds of stopping having computed $j$ hashes or less are $q_j\lessapprox{3\over2}j^4 2^{-n}$, and this approximation is tight as long as $k$ is not too small, but is small enough that said odds remain small and there are few collisions among the $\approx{j^3\over6}$ values of $h_x\oplus h_y\oplus h_r$ considered.

Thus the best algorithm for option 2 can not find a collision with sizable odds faster than $O(2^{n/4})$; this shows that our simple algorithm has the right assymptotic.

Moreover, $j\le{1\over\sqrt[4]3}2^{n/4}\implies q_j\le{1\over2}$ holds. Beware that this later approximation is far from tight: we expect more than few collisions among the values of $h_x\oplus h_y\oplus h_r$ (by abusing the birthday problem for cryptographic hashing, consciously ignoring the fact that the $\approx{j^3\over6}$ values are not independent); and the approximation where we changed the product into sum is no longer tight. That establises some upper bound (not approximation) for the median of the number of hashes required by any optimum strategy; we aim at the mean, which is slightly higher.

Image credit: Cmglee; source; Creative Commons license.

We have shown nearly rigorously that the expected number of hashes for an optimum strategy and large $n$ must be $k=O(2^{n/4})$ as $n$ grows; and have plausible argument that $2^{n/4+1/2}$ gives nearly 40% odds of collision.

Because that $k$ is well under the birthday bound $\approx2^{n/2}$, it is very unlikely that for large $n$ a hash collision for $h$ alone is reached before $k$ steps, and the distinction between the two definitions of "collision" that we did not reject matters only for small $n$.

We know various strategies leading to the minimum number of hashes according to 2 or 3, plausibly running in $O(2^n)$ time with $O(2^{n/4})$ or $O(2^{n/2})$ words of memory (for a computer with words of at least $n$ bits; beside this, a multiplicative factor of $\log n$ applies for both). We could make exact calculations of the expectancy for very small $n$ (but that will depend on the definition of collision). We could make randomized simulations for up to perhaps $n=32$. Finding strategies requiring less work (perhaps at the expense of more memory, or computing somewhat more hashes than needed) in order to tackle larger $n$ is an interesting problem.

This answer is incomplete (we still miss a rigorous and tight bound), overly long and complex with the potential to be confusing (especially from the moment we seek an optimum strategy), and spoils an interesting homework assignment (asked in vague terms, but perhaps that's on purpose by the teacher, or OP). I hope that at least the redaction will differ, and that the OP will make the aforementioned exact and simulated computations. After all, it is all too possible that I left a serious error somewhere.


Understanding LFSR stream ciphers and the content scrambling system

How would I go about finding the period of each LFSR?

If the polynomial generating an LFSR is primitive polynomial then the LFSR has maximal period, $2^\ell-1$ where $\ell$ is the length of the LFSR. It is general practice that they are chosen as primitive polynomials. In your case periods are $2^{17}-1$ and $2^{25}-1$ for $L_1$ with length 17 and $L_2$ with length 25, respectively.

In LFSR's there might be a negligible chance that the key is all-zero then the stream will be all-zero. To eliminate an all-zero case, the fourth-bit is injected with 1 for $L_1$ and $L_2$.

  Why does the content scrambling system use different LFSR lengths?

If the LFSR lengths and taps are the same, then there might be the case that the two LFSR produce the same stream to cancel each other. We can call this a weak-key.

More importantly, an LFSR is linear and linear systems are not secure in Cryptography. You need to add non-linearity. One way to achieve this is by Filtering the states of an LFSR with a non-linear function or using a combining function like in CSS.

In CSS the combining function is 8-bit adder. After 8-clock, which produce 8-bit per LFSR, these 2 bytes are added. The carry is saved for the next addition.

Since addition is non-linear in bit case, the non-linearity is achieved. Of course for security non-linearity is necessary but not sufficient. A good read for LFSR with non-linear combing functions is the correlation attack. A famous article is Decrypting a class of stream ciphers using ciphertext only by Siegenthaler (pay-walled). He showed that a correlation attack can be performed on non-linear combiners.

  How would I go about brute-forcing it, and what would the complexity of the brute force attack be?

To execute a brute force, you need keystream from the cipher. Assuming that you have;

$2^{40}$- the keyspace is not hard to reach in 1996. The reason for low keyspace is well stated in Wikipedia;

At the time CSS was introduced, it was forbidden in the United States for manufacturers to export cryptographic systems employing keys in excess of 40 bits
In 1999 Stevenson showed 3 attacks including brute-force on CSS.
Even DES with $2^{56}$- keyspace can be easily searched with special hardware §,‡ or cluster during 1999s.
There is also a correlation attack that recovers the key with $2^{16}$ complexity.
One can also, attack with guessing $L_1$ and determing the $L_2$ with $2^{16}$ complexity

  If I simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify the information out of it)?

It will be completely linear and will be much more easy to attack; first, produce algebraic equations then solve by Gaussian elimination. As explained before, the basic countermeasure is adding non-linearity.

  Would a known plain text attack prove effective?

You need a keystream to attack therefore you need to know the plaintext.

§ RSA DES challange in 1997

‡ DES hardware machines since 1997


Secret community forming based on zero-knowledge proof (IOT)

How big is the secret key that defines a community?

If it is trivial, say a number between 1-100, then an attacker can easily calculate 100.000 hashes to know in which community each user is.

If the secret s is long, say 64 bytes, then I don't see the usefulness to generate 1000 hashes for each option. Then it would be best to just send your hash H(s+n), with a random nonce n you used (as knowing the nonce and the hash would not help anyone else to know the secret).


Stream ciphers in general are more efficient but less secure than a block cipher, provided all else being equal in terms of each construction following both necessary and preferred principles (Katz & Lindell, 2009; Boneh, 2013).

Shannon's “confusion and diffusion” refers to good confusion and diffusion of message block bits and secrecy bits based upon linear and non-linear functions as you mostly point out.

There are different kinds of stream ciphers as there are different block ciphers. Some stream ciphers did not pass two or more critical statistical tests to show powerful diffusion.

In general you are correct: stream ciphers either have low or even slow diffusion rates. However, linear masking and improve initialization processes helps reduce vulnerability to linear and side attacks. Stream cipher Hc-256 is a good candidate to test further.

Stream ciphers are faster than block ciphers, but block ciphers with proper construction have higher diffusion – still, pseudo-randomness can be generated from a block cipher to stream ciphers to reduce attack vulnerabilities.

Additional reading:

http://publications.drdo.gov.in/ojs/index.php/dsj/article/view/1435/4669
http://www3.ntu.edu.sg/home/wuhj/research/publications/wuhongjun_thesis.pdf

Same author as thesis but shorter and more straightforward:

http://www3.ntu.edu.sg/home/wuhj/research/hc/hc256_fse.pdf


Prove integer is within the interval [a,b]

As I mentioned in a comment, you are looking for a range proof, see my previous answer to a related question.

You specifically ask for a solution not limited to powers of two, and for numbers known to be between 0 and 100. Let $0 \leq a < b \leq 100$ be the interval you consider. Let $m$ be your secret integer. The simplest solution I can think of works as follows:

Commit to $m$, using the Pedersen commitment scheme over a prime-order group $\mathbb{G}$ of order $p$. That is, let $\mathbb{G}$ be a prime-order group (e.g. an appropriate elliptic curve where the discrete log is hard), and let $g$, $h$ be generators of $\mathbb{G}$. To commit to $m$, pick $r$ at random from $\mathbb{Z}_p$ and send $c\gets g^mh^r$.
Commit to the bits $b_6, b_5, \cdots, b_0$ of $m-a$, using again the Pedersen scheme and $7$ random coins $r_6, r_5, \cdots, r_0$ from $\mathbb{Z}_p$, chosen uniformly at random subject to the following constraint: $\sum_i 2^i r_i = r$. For $i=0$ to $6$, let $c_i \gets g^{m_i}h^{r_i}$. Note that $m-a \leq m \leq 100 < 2^7$ so seven bits are sufficient.
Prove for each $c_i$, using a zero-knowledge proof, that it commits to a bit. As the verifier can check herself that $\prod_i c_i^{2^i} = c\cdot g^{-a}$ (because $\sum_i b_i\cdot 2^i = m-a$, and the random coins $r_i$ have been chosen to ensure that this relation will hold), if she is convinced that the $b_i$ are bits, they indeed form the bit decomposition of $m-a$, which proves that $m \geq a$ (otherwise, $m-a$ would be considerably larger than seven bits, due to the modulo reduction with $p$).
Repeat the two steps above, but using the bit decomposition of $b-m$ instead of $m-a$ this time. This will prove that $b-m \geq 0$, hence that $m \leq b$.

The only missing ingredient is a proof that a Pedersen commitment $C$ commits to a bit. There are two natural way to implement a $\Sigma$-protocol for this task.

The first possibility that comes to mind is to use an OR proof, showing that $C$ commits to $0$ OR $C$ commits to $1$. See for example the answer to this question.

The second possibility for such a ZK proof is quite simple: prove that you know $(x, s, s')$ such that $C = g^x h^s$ and $C = C^xh^{s'}$. This shows that you know an opening of $C$ to both $x$ and $x^2$; by the binding property of the commitment scheme, this ensures that $x = x^2$, hence that $x$ is a bit.


SRP protocol is quite abstract so to provide matching implementation for version 6a you need to know following:

N, g - group parameters
H - hash function, there can be different hash functions used for different values
how is private key x calculated
how is shared session key K calculated
how are evidence messages (M1, M2) calculated

In addition you need to know what is internal representation of numbers (byte order, padding) and what is the format of messages being exchanged between client and server.

Without that knowledge all you can do is reverse enginner (even without disassembling binary ie. you could deduce what might be hash function based on size of M1) or try your luck with different configurations. For example (based on RFC 5054 and SRP-6a summary):

byte order: big endian
encoding: UTF-8 (for username and password)
N = 2048 bit prime from appendix A
g = 2
H = SHA1
x = H(s | H(I | ':' | P))
k = H(N | PAD(g))
u = H(PAD(N) | PAD(B))
K = H(S)
M1 = H(H(N) xor H(g), H(I), s, A, B, K)
M2 = H(A, M1, K)

As for the test vectors I haven't found others then those at RFC 5054 and on Stanford SRP demo page.


What do $0^n$ and $1^n$ mean in cryptography?

Typically that means a string of either $n$ zeros or $n$ ones.


$X_ {i_1}, . . . , X_{ i_ k} $ are IID random variables or not?

My first understanding was yes, but in fact, it depends.

First understanding: You can view them as IID, unless you have some knowledge about the secret $s$ and enough other variables. Take for example a Shamir Secret, a simpler secret sharing scheme which is a special case of this. A Shamir secret allows to reconstruct $s$ with any set of $k$ parts from $n$ shares. It is built by choosing a random $k-1$ degree polynomial such that $f(0)=s$. Any set of $k$ or more distinct points allows you to reconstruct this polynomial curve and thus learn it's value for $x=0$. Any set of $k-1$ points (except $(f(0),0)$) would be unauthorized and insufficient to reconstruct the secret. Since each coefficient of the polynomial (except $s$, that you have no knowledge of, including it's distribution) is chosen randomly, every set of point. Conditioning on $k-1$ shares doesn't change in any way the distribution of the $k^{th}$ share: it is still random.

But in fact it's not necessarily the case: only parts of these shares must be randomly distributed. Take these Shamir secrets: every share is a tuple $(x,f(x))$, and given their construction and a tuple $(x_1,f(x_1))$, you would expect the next tuple not to have $x_2 \neq x_1 $, so that even if $f(x_2)$ would be independent of $(x_1,f(x_1))$, $(x_2,f(x_2))$ would not. Conversely, you could choose $x$ as random every time, risking a possible $x_2 = x_1$, but making all the shares IID.


From the first definition;

To see that a function is negligible, you have to find an $n >N$ for every positive polynomial $p(n)$ such that after $f(n) < 1/p(n)$ is holds. Here two examples;

consider $p(n)= 10^6$ then $n \geq 800$ then $1/2^{800/2} = 1/1048576 < 1/10^{-6}$
consider $p(n)= 10^{3}$ then $n \geq 200$ then $1/2^{200/2} = 1/1024 < 1/10^{-3}$

  From the second definition;
  $\lim_{\lambda \rightarrow \infty} p(\lambda) f(\lambda) =0?$

For your $f(\lambda) = 1/2^{\lambda/2}$ we have to see that the limit is 0 whatever the polynomial $p(\lambda) = a_n \lambda^n +\ldots + a_0$

$$\lim_{\lambda \rightarrow \infty} p(\lambda)f(\lambda) = \frac{p(\lambda)}{2^{\lambda /2 }} = \lim_{\lambda \rightarrow \infty} \frac{a_n \lambda^n +\ldots + a_0}{2^{\lambda /2 }} = 0,$$

since if you take the L'Hôpital's rule the $n$-times the numerator will be 1 and eventually zero. The denumerator, however, goes to infinity.


What is the most light-weight symmetric cipher thats still usefull?

Salsa/ChaCha and the other eSTREAM winners are likely to be the "fastest but still secure" options today.

Don't forget authentication of course. Reduced-round ChaCha/Poly1305 is likely to be the fastest software-only option, due to tuned implementations in the libsodium and NaCl libraries.

UPDATED: The following slide deck has good info on state of the art lightweight block ciphers vs. legacy (along with source code links). Considers code size, RAM, and cycles/byte metrics for many algorthims).

Stream ciphers such as those from eSTREAM may be a better option than block ciphers. Even choosing RC4 and hardening it by dropping the first 512 bytes may be a good solution; code size doesn't get much smaller than RC4.


Importance of supersingularity of elliptic curves

Your questions are a bit too rambly, so I'll just answer the title question. We use supersingular curves because ordinary curves don't have enough isogenies. Specifically, for supersingular curves, the graph of $\ell$-isogenies defined over $\mathbb{F}_{p^2}$ has good expansion properties. For ordinary curves, the graph of $\ell$-isogenies does not have good expansion properties. In most cases the latter graph is just a union of disjoint cycles. You can get graphs of ordinary isogenies with good expansion properties, but in order to do so you have to do something like take the union of $\ell$-isogeny graphs over various different $\ell$.


RSA: Letting $p$ and $q$ have different bit-size

No, there is no specific vulnerability associated to choosing $p$ and $q$ with size differing by $i$ bits (or $2\cdot i$ bits as in the statement) for small $i$. However, if $i$ gets too big:

That improves the odds that ECM will manage to factor $n$ for some fixed size of $n$, and at some point ECM will become the best algorithm; this is the case if $i$ is about one fourth of the modulus size, perhaps lower.
That reduces the speed benefit one can gain from CRT for the private key operation.

Also: unless $i$ is a multiple of $32$ or $64$, that implies one at least of $p$ or $q$ does not have a bit size exactly multiple of $32$ or $64$; in turn, that implies an implementation using the CRT can't assume that $p$ and $q$ have a bit size exactly multiple of $32$ or $64$, which is customary and slightly simplifies implementation.

And more generally, $i\ne0$:

Is not standards-conforming: in the venerable ANSI X9.31:1997, and its current successor FIPS 186-4, $p$ and $q$ of an RSA modulus must both have exactly half the bit size of the modulus (among other requirements).
Reduces the odds that a key generated on some device can be successfully used as a private key on a different device (it has no impact on usability as a public key, as long as the modulus size remains standard). Addition: an hypothetical CRT implementation of the private exponent exponentiation modulo $n$ that fails to handle one of the exponentiation modulo $p$ or $q$ because of its unusual size, and does not check its final result using the public key, much likely leaks information leading to factorization of the modulus; thus the issue is not only an interoperability issue, it could be a security issue too.

Most importantly, precautions aimed at insuring that $\Delta=|p-q|$ is big enough are technically pointless: the justification given to such precautions is protection against Fermat factoring, which in its most basic form enumerates integers $b$ from $0$ onwards, stopping when $n+b^2$ is a square $a^2$, revealing $q$ as either $(a+b)/2$ or $(a-b)/2$. However, all known improvements of Fermat factoring have fully negligible odds to succeed in factoring $n=p\cdot q$ with $p$ and $q$ of equal size at least $256$ bits, but otherwise mostly random (for the number of $b$ to enumerate by the basic Fermat factoring method is $|p-q|/2$, which is higher than $2^{212}$ with odds better than $1-2^{-40}$, and none of the known improvements lowers that $2^{212}$ steps to something workable). If $p$ and $q$ are known to have the same size and the same leading $50$ bits, GNFS is still a much better choice than Fermat factoring .

As an additional argument, if the adversary had a Fermat factoring variant with sizable odds to factor $n$ knowing that $p$ and $q$ are of equal size, then that method likely can be adapted to $q$ known to be $i$ bits bigger than $p$, much like the basic Fermat factoring can be adapted to the situation $q\approx2^i\cdot p$: enumerate odd $b$ stopping when $2^{i+2}\cdot n+b^2$ is a square $a^2$, revealing $q$ as whichever of $(a+b)/2$ or $(a-b)/2$ is odd.

According to my memories of Robert Silverman's account: the requirement in ANSI X9.31 (kept in FIPS 186-4) that $|p-q|$ must be more than $100$ bits less than half the modulus bit size (for $1024$-bit modulus and higher) was introduced to please the bankers chairing at the standard's committee, who wanted that there is a simple rebuttal to a court argument on the tune of: " I claim that my client did not produce that signature! One simple explanation is that the modulus has been factored. An expert has testified that Fermat factoring, known since the 17th century, potentially could do that, and allow such forged signature. No precaution against it was taken! Whoever carelessly specified that signature system must bear the consequences! "