What are the differences between X9.31 RSA operation and PKCS#1 RSA operation?

Well, there are indeed differences between the two standards, as you can see below:

  key pair generation

X9.31 requires that $p-1$, $p+1$, $q-1$, $q+1$ all have prime factors between $2^{100}$ and $2^{120}$, and that $p$ and $q$ differ in at least one of the first 100 bits.  These requirements are there to frustrate suboptimal factoring methods, and have been inherited (albeit in an adjusted form) by FIPS 186.

X9.31 requires that $e$ be between 2 (well, 3 for RSA) and $2^{k-160}$ (where the modulus is $k$ bits); that is, it forbids public exponents close to the size of the modulus.

PKCS #1 does not list any specific requirements on key generation.

  signature generation

X9.31 lists a deterministic signature padding format of the form: 0x6bbbbbb...bbba[hash][hash code], where [hash] is where you insert the hash, [hash code] is a 16 bit value that encodes the hash type, and there are enough b digits to make the value precisely fill the block.  BTW: since X9.31 assumes that the key size is one of a specific set of values, all of which are multiples of 4, there's no problem with the leading hex digit being '6'.

PKCS #1 lists rather different signature padding types; RSASSA-PSS (which is a probabilitic signature type), and RSASSA-PKCS1-v1_5 (which is deterministic).

I've never actually seen the X9.31 padding format used in practice.

  encryption

X9.31 does not address encryption at all.


Is an RSA variant with public exponent $e=f+(p-1)\cdot(q-1)$ safe (for $f$ random in some small interval)?

I can't see any problems, if you use it as specified (with the performance advantage of a factor of 2).

If you start to narrow the interval too much, you're going to get into trouble.  For instance, one factoring method is to compute $c=b^e \pmod n$ for some known base $b$; then try to compute the discrete logarithm of $c$ to base $b$.  We know $c=b^f \pmod n$, so if $f$ comes from a small range, so we can use some algorithm for computing the discrete logarithm when the exponent is known to come from a small range (e.g., baby-step giant-step or Pollard's rho).  This will reveal $f$, if $f$ comes from too small of an interval. For instance, if you pick $f$ from the range $3 \le f \le 2^{80}$, these algorithms will be able to find $f$.  Once $f$ is known, $n$ can be factored, as $e-f$ reveals $(p-1)(q-1)$ which can be used to extract a factor of $n$.

Similarly, if you choose $f$ to have very low Hamming weight, I think you will again get into trouble.  The baby-step giant-step and Pollard's rho algorithms can be adopted to solve the discrete log in cases where the exponent is konwn to have low Hamming weight, so the same method can be used.

For these reasons, I don't think you're going to be able to get a very large performance advantage.

And, I have to say that I would not bet much of my own money on the security of this scheme.  I believe van Oorschot and Coppersmith have some results on factoring $n$ given partial knowledge of $d$ or $p$. The lesson I draw from those results is: when you start giving away partial information on RSA secrets, RSA can lose a lot of security.  I don't know if that applies to your scheme, but I would be reluctant to use it in a high-stakes situation, and I would be especially reluctant to narrow the interval from which $f$ is chosen.


Potentially almost any data input can be used as seed. But in general you don't want to use information that can be trusted to have high entropy and be secret all the time. This rules out stock exchange and the weather for instance, as the stock exchange may be down, and there is not much entropy in a clear blue skye.

Almost all of the sources you mention rely on outside phenomenons, which means you have to trust the source. Moreover, you'll need a trusted path to your source, and the trusted path likely requires a random number generator. So you would get into a chicken/egg situation.

What is usually done is to rely on a local phenomenon and then use highly unpredictive measurements. Local phenomenons can be kept secret and measuring in the extreme will mean that you aren't dependent on large fluctuations. For instance a HDD can be used to inform the system about I/O times, and measuring in nano-seconds will give enough entropy for a few bits of seed.

Of course, you neverk know what kind of system you are going to find. So fortunately it starts to be commonplace to include a random number generator in CPU's. An RNG in the CPU or - for instance - in a TPM is probably the best RNG you can find.


Is Dropbox's hashing method cryptographically secure?

Disclaimer: I have no first-hand knowledge of what hash (or MAC, or whatever method) DropBox uses for de-duplication; about if it is enough to know that (and its key, for a MAC) in order to download something from DropBox; and I see slightly diverging opinions about these points.
If we consider the problem of finding a collision, the 160-bit hash defined by
$$H(M)=\text{CRC32}(M)||\text{MD5}(M)$$
is NOT cryptographically secure, for it is only marginally stronger than $\text{MD5}$ is.
$\text{MD5}$ no longer provides a good protection against collisions: with this Fast Collision Attack on $\text{MD5}$ we can find a collision (for messages at least 128 byte) with cost about $2^{18}$ compression functions (finding collisions for $\text{CRC32}$ is totally trivial). Finding a collision for $H$ is harder than for $\text{MD5}$, but by a dumb method (finding $\text{MD5}$ collisions until one is also a collision for $\text{CRC32}$) only like $2^{32}$ times harder, and $2^{50}$ compression functions is non-trivial but feasible. Update: And as pointed by poncho we can (for messages at least 4 kiB) make that only like $32$ times harder, or about $2^{23}$ compression functions, which is nothing. As the saying attributed to the NSA goes, attacks only get better, they never get worse.

If we consider the problem of finding a second-preimage, $\text{MD5}$ remains impractical to attack as far a we know, and $H$ is at least as strong as $\text{MD5}$ is.
If we consider the problem of finding a first-preimage, $H$ can't be more than $2^{32}$ times easier to attack than $\text{MD5}$ is, likely that can only be approached for short messages where brute-force is the best attack, and for long messages likely this is (at least) about as hard as for $\text{MD5}$, which remains impractical to attack as far a we know.


Known plaintext attack on ElGamal encryption

Your parameters that you provide are incomplete (in what group are you working?).

Anyways, lets assume that you work in $\mathbb{Z}_p^*$, your have a generator $g$ and your public key is $y=g^x$.

Then, if two ciphertexts share the same randomness $k$, they will look like $(c_1,c_2)=(g^k,m\cdot y^k)$ and $(c_1',c_2')=(g^k,m'\cdot y^k)$ for your two messages $m$ and $m'$. So as you know that let say for the first ciphertext the message is $m$, then you can compute the inverse $m^{-1}$ of the message $m$ in $\mathbb{Z}_p^*$ and can find $y^k=c_2\cdot m^{-1}$. Now, as you have $y^k$ (which you can clearly also invert in $\mathbb{Z}_p^*$) and both ciphertexts share the same randomness $k$, you can easily obtain $m'$ from $c_2'$.


What would the implications be of a single randomly discovered SHA-256 collision?

Your question is a contradiction. If it actually is randomly discovered, then there are no implications because it is, well, random. If it were truly the result of luck, then so what? But the more likely explanation is that SHA-256 is really, very badly broken. I personally would not believe that anyone came up with such a collision by chance without testing an enormous number of possibilities.

Note however that, due to the length extension attack, a single public collision could be used to make more collisions with the same prefix. This could have security implications in practice. Additionally, if the collision came about through a non-generic attack against the hash itself, it may be possible to adjust it to find more collisions (see Luis Casillas's answer). This isn't the case if the collision was random.

Think of it another way. If I posted a list of all the passwords you have ever used online, and claimed I just got lucky and was posting random numbers from an RNG, would you believe it, or would you instead suspect that I had hacked your computer and was stalking you?


Why does Apple create a certificate for my push notification key

I'm guessing that the need for a certificate has nothing to do with authenticating the upload, but so that people's iPhones can authenticate the app at install time / runtime.

[Ah, I see your edit that this is not right. I'll leave it here for posterity anyway. Are you sure you can't find documentation for this somewhere?]

As a developer, you create code-signing keys for yourself.
You announce to Apple "Yo Apple, I'm the developer of this app, and here's my code-signing key".
Apple makes a certificate out of your public key, telling the world that Apple agrees that you are the rightful developer of this app.
Apple distributes this certificate along with your app to millions (we hope!) of end-users who download your app.
Any update you push must be signed by the same code-signing key as the original, otherwise the end-user iPhones will reject it. (How to you prevent malicious updates and NSA-style sideloading?)

I'll also address this part of your question:

  Is that signing dance done because SSL supports client certs but does not support bare private keys?

No, SSL does not support "bare private keys" and here's why: how do I know who the private key belongs to? Any bloke can walk up and say "Hi, I'm Christian Aichinger, here's my public key, and I'm going to use the corresponding private key to sign some data". Ok, fine, but how do I know that I'm talking to the real Christian Aichinger, and not somebody pretending to be them.

The commonly accepted way to solve this is to have some third party that we both trust verify that you are who you say you are, and that this public key does in fact belong to you. That trusted third-party is called a Certificate Authority, and that statement that this public key belongs to you is called a Certificate.


Yes, PGP allows different-sized subkeys and subkeys are not derived of the main key, so it is possible to have the earlier key be a subkey of the new one.

How to do it is off topic here, but this should get you started if you use GnuPG.


How should I encrypt filenames in my scenario?

With a good encryption mechanism, knowing any number of plaintext-ciphertext pairs $\{(P_i,C_i)\}$ should reveal nothing about the plaintext corresponding to some extra ciphertext $C$, other than its length. In particular, given the knowledge that $P_1$ encrypts to $C_1$, an adversary should have no way to know whether some ciphertext $C$ also decrypts to $P_1$. This is a consequence of semantic security.

You may wish to weaken the security of the system to allow recognizing ciphertexts corresponding to a previously processed plaintext. That is, knowing plaintext-ciphertext pairs $\{(P_i,C_i)\}$ reveals no information about some ciphertext $C$ which is not one of the $C_i$.

This has dangerous implications that may not be obvious at first glance. In many cases, an adversary can convince the user to encrypt some plaintext (e.g. arrange for the user to download some files). So an adversary who wanted to decrypt some ciphertext file names could make guesses for the plaintext, arrange for the user to create files with this name, and compare the resulting ciphertext to verify these guesses.

Using non-repeated IVs in encryption algorithms avoids this by causing two plaintexts to never be encrypted to the same ciphertext, even if the plaintexts are equal, because the IVs will differ.

If you don't mind considerably weakening the confidentiality of file names, you can use a deterministic IV. Beware that you can't just use any old IV; for example, with CTR or GCM mode, repeating a counter value reveals the xor of the corresponding plaintext blocks, which leaks a lot of information. One method that is safe, other than enabling the encryption oracle guessing method I described earlier, is to make the IV a cryptographic hash of the file name. If the hash function is independent of the block cipher (which it typically is in practice, e.g. the SHA families are independent of AES) then the hash function can be idealized as a random oracle and so using a hash as the IV is equivalent to using a random IV as long as plaintexts are not repeated.

However, I wonder why you need to be able to recognize identical ciphertexts. Your backup tool has the symmetric key, so it can decipher the name of previously backed-up files. To avoid downloading ciphertexts from the server for local decryption, you would keep a local log of what has already been backed up, but backup programs usually have this anyway in some form.

Regarding your updates:

  Use AES/GCM (or CBC) with the same IV for all filenames?

No. GCM requires a unique IV. Repeating the IV with GCM can not only break the confidentiality and integrity of the message, but can even leak information about the key. See How bad it is using the same IV twice with AES/GCM?

CBC with a repeated IV, in addition to making common prefixes obvious, leaks a little information about the plaintext. It also doesn't guarantee integrity.

  Or use ECB mode which does not require IV?

No. ECB is not a proper encryption mode. It is implemented in some libraries for convenience but does not provide any security.

  I can't really use IV for filename encryption (need to save the IV into the crypted filename, which is problematic)

You generally can't use the encrypted filename as a filename anyway, because the encrypted filename is longer than the original, even without counting the IV. Filesystems have forbidden characters, so you'd need some encoding scheme, which costs you bytes in the filename. Most filesystems have a limited filename length. The only case in which you can map plaintext filenames to encrypted filenames is if the source filesystem's filename length limit is sufficiently smaller than the target filename filesystems's length limit.


Is base64 the best two-way hash function to encrypt and transmit a set of integer numbers via the internet?

MD5 – Can I use MD5 as a two-way function? If I can break the data in 64 bit portions, will I be able to recover the original message without a pre-calculated lookup table?

MD5 is a hash function, not a cipher. Differently stated: you will not be able to encrypt or decrypt anything by simply using a hash function.

You could compare MD5 hashes with each other, but that would need you to “pre-calculate” hashes to which you would then compare those other hashes. But hashes will prevent you from learning about the original message (hashes are made to prevent that – among other things). Same goes for recovering the originally hashed data: you can’t. The reason is simple… a hash is not a compression tool which enables you to decompress contained data later on. There’s simply not enough information contained in a hash to do that (if recovering the original file from a hash were possible, everyone would be sharing short MD5 messages and things like torrents would have never been invented).

So – No, you can not use MD5 to recover the original message.

  Base64 – that can be easily used in both ways which is good cause it is easy, but this is also easy for hackers and crackers.

Base64 is nothing but a simple encoding method. A way to represent data. It has nothing to do with cryptography in the sense that it would be able to provide any kind of security. It is neither a hash, nor a cipher. All Base64 does is that it enables you to represent and transmit (mostly binary) data in a human-readable way. For example: Base64 comes handy when I would want to send you a binary file like an executable via email, but can not (or don’t want to) use the option to attach that file. With Base64, I could simply copy-and-paste the data as a message… which you would then need to convert back to binary data after receiving it.

Long story short – You can not (and should not) expect Base64 to provide any kind of security.

  I don’t know how SHA and other kind of checksums and integrity checks work, or if they are aproperiate for this kind of data (numbers).

SHA is also a hash, just like MD5. Hash functions are fundamentally different from checksums like CRC32. Checksums are mainly build and used to verify the integrity of data (for example: during data-transmission, or after data storage), while cryptographic hash functions also target things that go well beyond data integrity checks. You could use a hash to provide what a checksum does, but a checksum can not provide all the things a hash can provide… things like “collision resistance” for example. In that sense, you could say hashes are “smarter” (but also slower to calculate).

To give you a hint related to all of your questions: What you are actually looking for is called a ”cipher”… an  ”encryption algorithm”.

Some humble advice

Now, please don’t get me wrong… but you should really start from scratch with your research, since you are obviously getting most of the things you have been digging up absolutely wrong and trying to implement cryptography in your software with your current knowledge level is bound to fail.

To help you understand the fundamental things you are currently mixing up, I would humbly advise you to start reading the following two:

https://en.wikipedia.org/wiki/Encryption
https://en.wikipedia.org/wiki/Cryptographic_hash_function

After reading (and understanding) those Wikipedia articles, slowly work your way up to the point where you can be confident that you know what you are doing and talking about.

On your way, things like the Handbook of Applied Cryptography (available for free as online version) will definitely come handy as it is easy to read once you grasped some minimal basics of crypto.

As said, please don’t get me wrong and please don’t take my advice as some kind of personal offense. I just do not want to see you fail securing your software or maybe even messing up the security of your game server, just because no one pointed you to the fact that you are currently simply too misinformed to even think about implementing cryptography in your game all by yourself.

On the positive side: you were smart enough to ask before doing something wrong, which is good. Therefore, I am confident that – with a bit time and effort – you’ll quickly reach a point where you’ll look back on this question and smile. Yet, think in weeks… not days or hours. Crypto can’t be learned in a day. In contrast, cryptography can be so tricky to implement that even experts sometimes fail to do it correctly because they missed a tiny detail somewhere. Gaining a somewhat useable level of knowledge so that you can implement it in your game and server surely won’t happen by tomorrow.

EDIT

Adding part of the comments that followed up this answer:

  OP:
  … May you please advise me on finding an easy encrypt/decrypt with acceptable level of security? I prefer the method is common enough so I can use built in libraries while implementing both on server and client sides
  ME:
  Depends on the coding languages you’re using, but AES is available on about every platform and there are many libraries (eg: OpenSSL) out there supporting it. So, that could be an option… especially because you probably have the best chances finding "HowTo" tutorials related to it. Besides that, you’ll have to consider thinks like "keys" and “key exchange” (for authentication and encryption) but all that is too broad to wrap it up in a single answer or comment. If I were you, I would take things step-by-step and when in doubt – ask here or (if it’s source-related) at StackOverflow.
  OP:
  … I am a bit familiar with keys and two way keys concept and I think I can use AES by reading some tutorials …

That should wrap it up completely.


Is knowing the distribution of input domain only way to do cipher text only attacks?

Since for any fixed key the encryption algorithm is a bijection from the set of $n$-bit strings onto itself, the set of all possible ciphertexts is regardless of the key and algorithm always the set of all $n$-bit strings and does not provide any information.


Measure Strength of Mix Mode Modular Arithmetic based Confusion Layer

The same principles (linear and differential cryptanalysis being most prominent) apply to Mixed mode confusion layers, though in general you may be limited to experimental analysis since the theory of such mappings is not so developed, being a mix of different algebraic structures.

If you have to do experimental cryptanalysis  a $64\times 64$ confusion layer will clearly be too large to experimentally compute exhaustive linear approximation tables, or whatever other tool you are using.

One specific innovation by Havard Raddum (see springerlink or his site at researchgate he will probably gladly send you a pdf) in his 4 round cryptanalysis of reduced IDEA-X/2 (a weakened variant) was to include "multiplicative differentials", after all you can apply differential cryptanalysis to any group.

If you focus on the $16\times 16$ substructures operating on "words" you can isolate the groups used in IDEA. However, this is quite difficult as well since a distributive law between the three group operations namely

$16$ bit XOR
Addition modulo $2^{16}$
Multiplication modulo $2^{16}+1$ where the all zero element is treated as the modulus $2^{16}+1.$

does not hold. Nor do the designers ever use the same group operation in a contiguous manner.

You may find reading Raddum's paper interesting since he makes a stab at treating multiple groups in a differential attack. Then you can see the papers which cited his.


Is there any compelling or logical reason to use AES-192 over AES-128 but not use AES-256?

There is no reason to use a AES-192 if you have access to AES-256 (or AES-128).
This question is completely in line with the following thread:
[Cfrg] A little room for AES-192 in TLS? which resulted in this somewhat conclusion:

Dear all,
the related-key attacks against AES were interesting from an academic point of view as they broke the security claim we made for Rijndael.
However, the attacks require very sophisticated manipulations of the secret key by the attacker. For example, even a protocol that would allow an attacker to add (or XOR) a value of her choice to the key before being used in AES would not allow mounting the attack. If you are interested, you can read the paper Vincent and I wrote "On the related-key attacks against AES" available at e.g. http://jda.noekeon.org/
As for including AES-192 in TLS, I don't see any benefits.
Kind regards,
Joan Daemen

TL;DR: To sum up the only real advantage of AES-192 is the insignificant gain of speed compared to AES-256.


Bijective function with unknown reciprocal function

First of all, there is no problem with using SHA256 or SHAKE128/256[1] those would have had $2^{128}$ collision resistance with a 50% probability by the birthday attack. If you really fear that switch to 512-bit versions. Take SHA512 or Shake256/512 both have $2^{256}$ collision resistance with a 50% probability by the birthday attack. Even if you ever hash $2^{80}$ uniform random 256-bit strings then the probability of the collision is $(2^{80})^2/2^{256}/2 = 2^{160 - 256-1} = 1/2^{97}$ and this is not going to happen, and the less the data you have, the more little probability you will get.
If you ever find a collision tell the world that you will be famous. Actually, I would go for the tiny, tiny chance to find a collision in SHA256 or SHAKE128. A simple query for checking the existence of the identifier would find out the collision. There is always such checking already since you might add the same user again.
For direct hashing with SHA-256, you do not need to worry about the collisions, you need to worry about the possible leak of information, and that totally depends on how the data are transmitted and/or stored.
It is possible to use a keyed hashes if you have some HSM to protect the key. The HMAC-X is proven to be PRF if the underlying hash function is PRF. The X stands for a hash function as HMAC-SHA256.
All of the above would solve your problem without any fear.
In short: A good cryptographing hashing is enough if there is no leakage problem. Even a collision resistance is not required at all. It may suffice to use a 128-bit PRF, if the secret key is safe to be used in your application.


Choice between appending or prepending nonces to ciphertexts

The order of the tag, the nonce and the ciphertext doesn't matter at all. Any encoding would perfectly fine, since what gets authenticated is the data itself and not the way it is encoded for transport.

Now, if you can't use counters, and you don't trust the PRG, you may end up reusing nonces, no matter how they are encoded.

You should either use a nonce-misuse resistant scheme such as AES-GCM-SIV, or use a KDF to create the nonce from the ciphertext, some output from the PRG, and a secondary key.


A cipher $E_k(m)$ is malleable if there is a nontrivial binary relation $\sim$ on messages such that given $c = E_k(m)$, it is easy to find $c' = E_k(m')$ with $m \sim m'$.  For example, AES-CTR is malleable because for any $m$ and $m'$ with $m' = m \oplus \delta$, it is easy to compute $$c' = c \oplus \delta = E_k(m) \oplus \delta = E_k(m \oplus \delta) = E_k(m'),$$ in which case $m \sim m' = m \oplus \delta$.  A hash-then-encrypt variant where we encrypt $m \mathbin\| H(m)$ instead is still malleable because it is easy to compute $\delta = (m \oplus m') \mathbin\| [H(m) \oplus H(m')]$ for any desired message $m'$.  Similarly, textbook RSA, where the ciphertext for a message $m$ is $m^e \bmod n$, is malleable because for any $m$ and $m'$ with $m' = m \cdot \eta \bmod n$, it is easy to compute $$c' \equiv c \cdot \eta^e \equiv m^e \cdot \eta^e \equiv (m \cdot \eta)^e \equiv (m')^e \pmod n,$$ in which case $m \sim m' = m \cdot \eta \bmod n$.

As defined by Dolev–Dwork–Naor (paywall-free) and used throughout the literature, a cipher is nonmalleable (NM-) under an attack model (-CPA, -CCA, -CCA2, etc.) if, after interacting with the oracles in the attack model, and upon being presented a challenge ciphertext $c$ for a message of a form chosen by the adversary, the adversary cannot find—even using further interaction with the oracles—a nontrivial relation $\sim$ and a ciphertext $c'$ whose plaintext is related by $\sim$ to the plaintext of $c$.  (Here we rule out trivial relations like $m \sim m$.)

In practical terms, nonmalleability means an adversary can't selectively modify ciphertexts; the worst they can do is denial of service or wholesale replacement.

The Bellare–Namprempre 2000 paper you cited on generic composition of symmetric ciphers and MACs doesn't formally define nonmalleability because nonmalleability is largely not important for the symmetric setting: when the sender and recipient share a key, they generally care about eavesdropping and forgery, but not about selective modification—detecting forgery means detecting selective modifications, and rejecting forgeries prevents abusing selective modifications to leak secrets.

Nonmalleability matters more in the setting of public-key anonymous encryption, like an activist leaking a document to a journalist.  While it may not directly reveal to the adversary what a message was, selective modification can often be exploited in a larger system like an PGP mail client with EFAIL to leak the message when there is no notion of authentication to prevent forgery per se since anyone can anonymously submit documents.  So nonmalleability is defined in the Bellare–Desai–Pointcheval–Rogaway 1998 paper on generic relations between notions of security for public-key encryption.


Will our app be FIPS 140-2 compliant if we use our own AES algorithm implementation?

If you are using an AES library that has not undergone the FIPS validation process, then you are not FIPS compliant (or, at least, your use of AES is not).

FIPS compliant means more than "we use algorithms that FIPS likes", it means "having passed the FIPS certification process"; that is how NIST defines it.

Sorry, but NIST is quite strict about this; if you haven't undergone the full testing, then NIST is concerned that you haven't implemented AES correctly; there may be subtle bugs that affect the security.  And, since NIST makes up the rules for what's "FIPS compliant", well, there's no point in arguing about its likelihood.

In addition, FIPS talks more than what algorithms you use; it also talks about health tests and key zeroization and other such things; the FIPS certification process checks all that as well.

If you need to be FIPS compliant, then your choices are:

Use a FIPS-certified library to perform all the FIPS-approved crypto operations
Go through the FIPS-certification process for your application (or, at least, the crypto pieces of your application).

The FIPS certification process is surprisingly complicated; I'd advise you to use a FIPS-certified library.


RSA-CCA security of $m || H(m)$ as input to modular exponentiation

CCA security assumes CPA security, and $m || H(m)$ is not CPA secure. This is simple to show: say that $C = E(m || H(m))$ is known, then an adversary can simply guess $m'$ and encrypt that. Then $C' = C$ will show the adversary that $m'=m$.

To show a CCA attack you can use this attack. You can of course replace the value $2$ in that question with $y$ where $y = x || H(x)$ for any $x$. In that case you end up with $z \cdot m || H(m)$ after decryption. Calculating $m || H(m)$ will then just consist of division with $z$.

To avoid this it is of vital important that the signature is over data protected by randomized padding, and that this randomization is well distributed over the input to the RSA exponentiation. This is what OAEP does with the MGF(1) padding.

Alternatively a hybrid scheme such as RSA-KEM combined with a block cipher could be used.

Deterministic encryption cannot be fully CPA or CCA secure; some kind of randomness or at least uniqueness is required to be CPA / CCA secure to not leak information for repeated messages.


Why do crypto libs use table lookups when they're vulnerable to timing attacks?

I believe that it is for two reasons:

Nontable based implementations of AES are possible, but (assuming you don't have AES-NI or something similar) are significantly slower than table based implementations (perhaps $10\times$ to $20\times$ slower)
For a lot of uses, timing attacks aren't particularly relevant (as either the attacker can't get the start/stop times, or can't get them to the precision needed to actually perform such an attack against AES)

Remember, when we deal with side channel attacks, there are a number of attack models possible:

At the simplest level, the attacker gets no information about the encryption process; he can (possibly) submit chosen plaintexts and ciphertexts, but the encryption operation looks like an abstract Oracle
The attacker might get some information (to some precision) about how long the encryption process takes
The attacker might also get some information about the memory accesses that the encryption process tables (cache-based side channel attacks)
The attacker might get some information about the state of the electronic gates of the device during the encryption process (DPA, EM-based side channel attacks)
The attacker might be able to cause a miscomputation during the encryption process (Fault Cryptanalysis)
The attacker might get unfettered access to the entire encryption process (White Box Cryptography)

The countermeasures needed as you go down the stack become increasingly expensive; it sounds reasonable that an implementation will say "we'll go down this far and no farther"


Confused by the definition of Linear Complexity of an LFSR sequence?

Length 2: one tap at the rightmost cell, going back into the left side without further additions. Starting with initial filling $01$ we get the sequence $101010\ldots$. The same sequence can also be achieved with two taps on both cells and the xor of them going in the left and the same initial filling. With register length $1$ only constant sequences are possible in Rueppel's definition: I don't think he even really considers such trivial cases.

So (10)* has linear complexity 2.


When to use Argon2i vs Argon2d vs Argon2id?

If you are unsure, then always choose Argon2id. Only choose Argon2d if you need maximum security at the expense of side-channel risk, and only choose Argon2i if side-channel attacks are the primary threat.

The number of passes just increases resistance to time-memory tradeoff attacks (TMTO). What you are probably remembering is that Argon2i is more vulnerable to TMTO attacks, and thus needs more passes to obtain the equivalent level of security. Argon2id uses the Argon2i pass to resist side-channel attacks, and the subsequent Argon2d passes to make up for TMTO resistance that the first pass lacks.

If an attacker performs a perfect side-channel attack and breaks the Argon2d portion, then they will still need to perform a very extensive TMTO attack to break the Argon2i passes. Compare this with pure Argon2d, where a successful side-channel attack completely negates its memory hardness. In other words, a side-channel attack against Argon2id reduces its security to one-pass Argon2i.

Note that some of the more severe TMTO attacks against Argon2i have actually been fixed.


Using hash of plaintext as nonce in NaCl secretbox- bad idea?

In the traditional sense, a nonce is a number that is only used once (with the same key). Though occasionally there are other requirements. For example, we may require that the nonce be unpredictable. For more on this I recommend you read this answer and this answer.

Now, you don't go into enough detail on what you are doing to say whether or not you need unpredictability of the nonce. A hash of the plaintext (depending on how long the plaintext is) will not get you unpredictability. So, if you are using CBC mode, this is definitely risky.

More importantly, however, it is not clear whether you really get the "number used only once" property with your proposal. Will the same plaintext ever be sent encrypted with the same key? If the answer is that is it possible, then your idea is a bad thing to do. Exactly what the outcome would be depends on application level details (most importantly, what block cipher mode you are using) that you have not provided.


Is this design of client side encryption secure?

It sounds like you're trying to set up a "host-proof" system.
( How can one share information using the 'host-proof' paradigm? ; Encryption scheme for social-network-like data sharing data via untrusted server? ; host-proof etc. ).
Sounds like a fascinating problem.

I'm assuming you're trying to set things up so that no data is stored on the client -- not even encrypted.
(That makes things much more difficult, compared to storing the user's private key on the user's client).

encrypted public keys

All the asymmetric systems I've been involved in are careful to generate the private key inside one box and never, ever let that key outside the box, even in encrypted form.

So I'm a little uncomfortable with storing the (encrypted) private key on the server.
However, I'm almost convinced that is excessive paranoia -- several people I respect seem to think it's OK to let a encrypted form of that private key outside the box -- a private key encrypted using a well-vetted algorithm such as AES, encrypted using a key generated from some key-stretching KDF (S2K) such as scrypt or PKDF2, giving the KDF a long passphrase. (Perhaps What is the harm if I publish an encrypted RSA private key publicly? is a better place to talk about encrypted private keys, and How can one securely generate an asymmetric key pair from a short passphrase? is a better place for comparing "encrypted private keys" to the various other ways of obtaining a private key from a passphrase).

message authentication

You may want to add some sort of message authentication code (MAC) or digital signature to the data.
After you do that, there's really no need for another process to check whether the password (or the key generated from it) is valid (see Sending KCV (key check value) with cipher text , Can I determine if a user has the wrong symmetric encryption key? ).

So your server blindly sends (encrypted) files to any person who requests them?
Then the local client does the check to see if the password(s) that person has are valid are performed locally?
I suspect there may be a better way of handling this.
Perhaps some sort of zero-knowledge challenge-response protocol?

protocol

So when Bob wants to send a message to Alice,

Bob types up his message on his own local machine.
Bob somehow obtains that Alice's public encryption key. (This can be a tricky -- how do you keep Charley from tricking Bob into using Charley's public encryption key?).
Bob encrypts his message with Alice's public encryption key (locally), and then sends the encrypted file to your server
Later, Alice pulls a bunch of files from your server:

her encrypted private key
the file Bob posted
some client code. (This is the really tricky bit -- is there any way for Alice to confirm that this code hasn't been maliciously modified, either modified in-flight while it's being transferred from your host to Alice's machine, or worse -- modified by some malicious attacker who has compromised your host?)

(optional) Alice unplugs her local machine from the Internet
Alice types in her passphrase on her local machine into your client code.
The client code runs Alice's passphrase through a slow KDF to get a (symmetric) key, then uses that (symmetric) key to decrypt her private key, and then uses that private key to decrypt Bob's file. (Typically there's yet another file-specific symmetric key involved in that decryption).
Finally, Alice reads the message Bob typed.

other things to think about

Rather than writing new crypto code from scratch,
you might consider using code that other people have already written, debugged, and vetted for security flaws. a b c d

You seem to think that PKDF2 and AES is better than whatever algorithms were around when OpenPGP was standardized.
Rather than completely writing an entirely new system from scratch,
perhaps it would be better to incrementally improve some OpenPGP implementation
so it supports PKDF2 and other things you feel are important.
Most open-source software writers would be happy to receive your improvements.
OpenPGP files generated according to the latest standards (RFC4880)
already support AES.

You might also think about what people at the security stackexchange say about JavaScript. Often they mention "Javascript Cryptography Considered Harmful".

Perhaps you might find convergent encryption ( convergent-encryption ) interesting.


CAUTIONARY NOTE: Beware that the vast majority of countless articles that discuss "image encryption" using computers (rather than using essentially optical means) are junk science. I don't know any article with "image encryption" and "AES" in the title (as the question does) that's worth studying (I welcome a link in comment if I missed one).
Encrypting digitized images (rather than other kinds of digital data) using AES requires no special crypto or preprocessing. As for other kinds of digital data, compression (if used) must be applied before encryption, and decompression after decryption; and then one should examine the consequences of the fact that crypto does not hide the length of what's encrypted.

There's no good reason that the plaintext (what's encrypted) go thru hexadecimal (a system of representation where 4 bits are encoded into a character): this would typically double the size compared to using the raw bytes. Hexadecimal is a way for eyes to see raw bytes, or express the ciphertext (result of encryption) as text (even though there are better encodings for that), but it should not be part of how the plaintext is transformed for encryption.
Learn about AES-CTR (or AES-OFB, even though it's not nearly as common), which let you encrypt data without bothering forming 16-byte blocks (these two modes avoid the need for padding; on the other hand that would be necessary for ECB, a mode of operation notorious for being bad, especially for highly redundant plaintext including uncompressed images).
Then learn about authenticated encryption, which is the modern way to protect data confidentiality and integrity using a symmetric key. Examples of that include AES-GCM(-SIV).


How to deal with concrete security against lots of queries?

Distinguishing distributions is studied in the field of distribution testing. See this survey for more information.
In particular, I believe the survey states that the correct sample bound includes a term roughly of the form $O(|\Omega|/\epsilon^2)$, where $\Omega$ is the support of the underlying distribution.
As for your particular questions:

Generally, query-bounds arise within cryptography when making Renyi-divergence arguments, as one can often make significant gains by bounding the queries (say as $q \leq 2^{64}$, rather than $2^{128}$, which is the "trivial" bound for 128-bit security). See for example this slides of Thomas Prest's (or in general his recent publications --- he has been quite interested in developing renyi divergence arguments in lattice cryptography).

For setting parameters when you're allowed to institute query bounds, see the slides. In particular, he works through the example of a particular algorithm (the Micciancio Walter convolution sampler) that claimed 100 bits of security, and shows that (up to $2^{96}$ queries) the sampler actually achieves 256 bits of security. For a different algorithm, he is able to set parameters such that certain state required for the algorithm is an order of magnitude smaller.

I can't really speak to the third question in any concrete way though.


Hill Cipher how to encrypt and decrypt when both "I" and "J" are in plaintext

"KEYWORD" is a weird format for a Hill cipher, aren't you confused with the Playfair cipher? There you work with a 5x5 matrix where I and J are often conflated into I (as 26 is one too big) and the key-square is filled with a key word.

This is what you seem to be describing.

In the Hill cipher, the key is a 2x2 matrix over some $\mathbb{Z}_n$, often with $n=26$, which is inconveniently non-prime, not a word. No I and J merging are needed there; we can choose any $n \ge 26$ and add extra characters (like spaces) for convenience.

Back to your question, which I think is probably Playfair: the convention is to remove final padding (often X or Z), needed to create bigrams and then context determines whether a received I means I or J. Spaces also need to be filled in, or maybe X is used for that too. It's one of the disadvantages of hand systems with built-in limitations like this.


We call a primitive broken, if there is any attack faster than bruteforce/what we expect of an ideal primitive. Broken does not mean that there are practical attacks.

Even when there were no known collisions in SHA-1, we still called collision resistance of SHA-1 broken, because there is a theoretical attack that can find collisions using fewer than $2^{80}$ calls to SHA-1.

In particular an $n$ bit hash function should have at least the following properties:

$2^n$ pre-image resistance (both first and second pre-image)
The generic attack is simply trying inputs until one fits the hash
$2^{n/2}$ collision resistance
The generic attack is generating inputs, and comparing their hashes against each other. The birthday problem tells you once you have about $2^{n/2}$ different values, two of them will likely be the same. In case of SHA-1 this that finding a collision takes about $2^{80}$ operations.

A function getting broken often only means that we should start migrating to other, stronger functions, and not that there is practical danger yet. Attacks only get stronger, so it's a good idea to consider alternatives once the first cracks begin to appear.


Zero-Knowledgeness of Fiat-Shamir heuristic

In the random-oracle model, it has been shown that the Fiat-Shamir transform preserves the soundness and zero-knowledge of certain families of zero-knowledge (proof of knowledge) protocols (e.g., Sigma protocols) -- see [§5 in BR93,PS00,FKMV12]. Instantiating the random oracle with a concrete hash function is a much harder prospect, but there have been some recent works in this direction as well --- for example, the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19].

P.S. Zero-knowledge is usually easy to show -- it is arguing soundness that usually causes problems in the non-interactive setting.

[BR93]: Bellare and Rogaway: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols
[FKMV12]: Faust et al. On the Non-malleability of the Fiat-Shamir Transform
[PS00]: Pointcheval and Stern: Security Arguments for Digital Signatures and Blind Signatures
[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


Single theorem adaptive vs non-adaptive non-interactive zero-knowledge proofs

It seems to me that the term "adaptive NIZK" is unclear. Where did you encounter it? If you give me the context, I can probably tell you what it was suppose to mean in this context.

Specifically, adaptive NIZK could refer to:

NIZK with adaptive soundness, where the malicious prover first receives the crs as input, then produces a word and a proof, and wins if the word is not in the language yet the proof is accepted;
NIZK with adaptive zero-knowledge, which matches what you mentioned: the simulator is divided into two parts, and first return a simulated crs, then outputs simulated proofs;
NIZK secure against adaptive adversaries in the UC model, which is more complex.

Assuming you meant "adaptive zero-knowledge", I don't think there is any generic way of transforming non-adaptive NIZKs into adaptive NIZKs; in fact, it's an open problem to build adaptive perfect NIZK arguments from standard assumption (those we have are from non-standard "knowledge-of-exponent-type" assumptions, or satisfy only a weaker property, called adaptive culpable soundness).

For your third question, I don't know if there are group signatures that use non-adaptive NIZKs.

For the last question, in a single-theorem NIZK, the zero-knowledge property is only guaranteed for provers that send a single proof after the crs is generated - to perform more proofs, new crs must be generated. Put otherwise, the length of the crs must be proportional to a bound on the number of proofs that will be executed with this crs. In contrast, in a multi-theorem NIZK, the same crs can be reused an arbitrary (polynomial) number of times for generating proofs. There is a generic transformation from single-theorem to multi-theorem NIZKs that uses only one-way functions, see this paper.


What are the advantages of using Leveled Homomorphic Encryption over Somewhat Homomorphic Encryption?

I would take a look at Brakerski's survey to clarify the exact differences between LFHE and SHE.

In the survey it says

  Leveled FHE [...] refers to a family of FHE schemes that allow, for any depth bound $d$, to generate an instance of the FHE scheme that supports the evaluation of depth-$d$ circuits.

And also

  In early works on FHE, the term somewhat homomorphic encryption (SHE) was used to indicate a scheme with homomorphic capabilities against a restricted class of functions (depth bounded). The two terms are sometimes used interchangeably, however in the original SHE scheme [Gen09b, Gen09a] the parameters of the scheme grew exponentially with $d$.

So, even though both of them accept a restricted family of circuits, we see that with LFHE you can "plan" in advance which type of functions you want to compute (i.e. up to what depth) and then you can obtain FHE for that family, whereas with SHE this bound on the depth is more 'universal', in the sense that it doesn't scale well with the depth and hence you're forced to keep a relatively low depth (but you can still use bootstrapping if this depth is large enough).

Notice that LFHE actually makes sense in practice: You probably use an FHE scheme with some specific application in mind, and in that case you can find a suitable LFHE scheme that fits your function.


Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$?

Answer: assuming that the $r_i$ values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0).

We can see this because, for any sets of values $v_i$, there are a unique set of $r_i$ values that is consistent with $\alpha$ being a specific nonzero value, namely, $r_i = \alpha^{-1} v_i$.  So, if someone cannot distinguish the $r_i$ values from random, they cannot determine which nonzero $\alpha$ value is any more likely than any other.

You state that the $r_i$ values are distinct, and so technically that is a correlation.  However, we can show that distinct $v_i$ values translate to distinct $r_i$ values (for any fixed nonzero $\alpha$), and hence any $\alpha$ value will preserve uniqueness.  So, the attacker cannot use this correlation to gain any information.


In Multi-party communication, how can I find that one encrypted value is negative or not?

Assume that there is a such function $f$, that can determine the sign of the number within the ciphertext .

Let the message space $P$
Using the binary technique, then an adversary can actually find the message as; where $c$ is the ciphertext

if  $f( c - E_p( |P|/2 ))$ > 0
  if $f( c - E_p( |P| ))$ > 0
else if $f( c - E_p( 0 ))$ > 0...

As usual binary search.


The sensitivity in differential privacy with deep learning

This is because they're using a definition of adjacency where you only consider two pairs of inputs adjacent when one record has been added or removed, instead of arbitrarily changed.

(…) each training  dataset is a set of image-label pairs; we  say that two of these sets are adjacent if they differ in a single entry, that is, if one image-label pair is present in one set and absent in the other.
   Definition 1.  A randomized mechanism $\mathcal M: \mathcal D\to\mathcal R$ with domain $\mathcal D$ and range $\mathcal R$ satisfies $(\epsilon,\delta)$-differential privacy if for any two adjacent inputs $d,d'\in\mathcal D$ and for any subset of outputs $S\subseteq\mathcal R$ it holds that
$$\Pr[\mathcal M(d)\in S]≤e^\epsilon\Pr[\mathcal M(d')\in S]+\delta.$$

Since each record contributes a value in $[-C,C]$ to the gradient, removing or adding a record will change the total by $C$. It would be $2C$ if the definition included "arbitrarily changing a record".


How to safely derive a value from a secret?

To derive additional identity information from a key you can use a KBKDF - a key based key derivation function. One of the more modern ones is HKDF-expand which is based on HMAC. Any hash or HMAC based function is of course one way; adversaries should not be able to learn any information about the key, unless the key is too short or not random enough in the first place.

KBKDF's differ from password based key derivation functions or PBKDFs such as PBKDF2 in the sense that they do not require a work factor (or iteration count) and they may not use a salt either.

KBKDF's can often contain label or other $\text{Info}$ input parameter to distinguish between output keys, something that PBKDF's commonly do not feature. In this case the label may for instance be a single character "V" to indicate that you are indeed deriving a value for that particular field. This means that the derived key is specific to that input value, other keys derived using an other label will be entirely unrelated to the derived value for "V".

When specifying $\text{Info}$ it may be a good idea to also include some (statically sized) identity strings for the participants, so that the key for sending from Alice to Bob is different from the one used in the other direction.

Note that HKDF is still a relative heavyweight algorithm - if just because it uses HMAC instead of a hash. If the implementation size or speed is a concern then you could replace it with an extremely simple alternative such as ANS X9.63 KDF which consists of a hash over a statically sized key, a label/other info and a statically sized big endian counter of 4 bytes.

In formulas:

$$K_i = \text{H}(\text{IKM} \mathbin \| \text{I2OSP}(i, 4) \mathbin \| \text{Info})$$

and $\text{OKM}$ is the leftmost bytes of $K_1 \dots K_n$ with $n$ set high enough to get the required Output Keying Material, $\text{OKM}$.

Here:

The $K_i$ is a full block of output keying material, each block the size of the hash function $\text H$ being used;
$\text{H}$ is the hash function configured for the KDF, e.g. SHA-256;
$\text{IKM}$ is the Input Keying Material to the KDF ($K$ in your diagram);
The operator $\|$ means concatenation
$\text{I2OSP}$ converts a number to - in this case 4 - bytes, using unsigned big endian encoding;
$\text{Info}$ could be the ASCII string $\texttt{"V"}$ as explained above;
$\text{OKM}$ the output keying material which can be used to create a derived key

For AES the output keying material is the key, as AES simply consists of (pseudo) random bytes.

This creates a variable length output that is specific to the input keying material and the $\text{Info}$ octet string, which makes it possible to derive multiple keys for the same input keying material.

So with all that your key derivation scheme could be e.g. SHA-256(key | 00000001h | "V"). If you need more key information you can simply increase the counter to 00000002h (the point is never to use the same input for the hash of course) and concatenate the output of the result. If you need less than a full number of output blocks then you should simply use the leftmost bytes of the result. If you want to derive more information from a static key then simply introduce another counter.

KDF's are very flexible, often to the point that they are too flexible. this makes it near impossible to standardize on algorithm, so describe the one you are using well.


Calculating the average key search time of DES

At $10^6$ keys per second, going through the full $2^{56}$ keys would take $2^{56}/10^{6}$ seconds, or about 2200 years; the average time would be half that (or a bit more than 1000 years).

Obviously, this is longer than anyone would be willing to wait.  So, why is DES considered brute-forcible?  Well, we can throw considerably more resources at the problem than a single laptop...


Is there any way to find out two numbers such that the XOR between them is a given number?

No. When $(G,\odot)$ is a group, if one knows the value $z=x\odot y$, and nothing else about $x$ or $y$, then $x$ individually can be any element of the group; same for $y$. This applies here, for the group $(\{0,1\}^b,\oplus)$, where $b$ is the block size in bits.

  Can I compute the value of IV or P1 without brute force?

Perhaps. In CBC encryption, the IV is usually public (that, or the receiver has some mean to find it that is not part of CBC encryption per se). It often is the first block of the ciphertext message.


Well, SHA-1 and SHA-256 are both limited to inputs of no more than $2^{64}-1$ bits; the HMAC architecture itself prepends a logical IPAD (which is 512 bits); hence both HMAC-SHA160 and HMAC-SHA256 are both limited to inputs of no more than $2^{64} - 513$ bits, which is about 2 exabytes.

I rather suspect that this is not a serious limitation to your application...

As for potential security weaknesses if you hash messages this large, I am unaware of anything significant.  Here is the most serious I can think of: if we assume HMAC-SHA160, and modify the first block of a $2^{55}$ block message (where each block is 512 bits), we might run into an internal hash collision (which would mean that the HMAC result wouldn't be affected); if the attacker asks us to HMAC $2^{53}$ such huge messages (all of which are the same except for the first block), then there is a good probability of having an internal collision somewhere (and this collision is detectable because the HMACs will be exactly the same); this collision would allow him to generate two other messages that will HMAC to the same value).

However, the amount of work this would take is huge (we're talking about HMACing a total of $2^{114}$ bytes of chosen text; that in itself is totally unrealistic).


Why is the core ChaCha primitive not good for use in a CRCF? Why create BLAKE?

I'm answering the following which was asked in the original question:

Why is stock chacha20 not good as a cryptographic hash? Why create BLAKE?
Why not simply apply the one-way compression function concept on raw chacha20, specifically its quarterround() function, unaltered.

TL;DR: Chacha was meant as a stream cipher, it needs a different kind of security guarantees to become a hash function.
The BLAKE designers tweaked it so that it became one, but they also did more than that. They also had some constraints because of the NIST's SHA3 competitions for which they created BLAKE.
Also, if you ever wondered why BLAKE was using a different direction for its rotation (left shifts instead of right shifts), you might want to read all about it below, because it's amazing!
Why create BLAKE?
If you don't want to buy the book on that topic, written by BLAKE's designers, I'll try to explain some things that might help you understand why we needed BLAKE.
First things first, I'll recall that ChaCha itself is a variant of Salsa20, a stream cipher that was already recognized for its simplicity and high speed.
The fact that it is a stream cipher notably means that when you take a message of size $\ell$, you'll get a ciphertext of size $\ell$ out of it, whereas with a hash function you want a fixed size output.
Now, ChaCha consists of a minimal set of basic operations and repeats the same pattern of addition, rotation, and XOR, called "ARX".
The main reason to choose ChaCha over Salsa20, is that while using the same numbers of operations than Salsa20 to invertible update four 32-bit state words, ChaCha does so in a different order and updates each word twice rather than once, hence giving each input word a chance to affect each output word. And it also has other nice properties about which you can read in the ChaCha paper.
Now, BLAKE designers wanted to compete in the NIST competition for SHA3, so they were notably required to:

produce digests of 224, 256, 384 and 512 bits
support maximum message length of at least $2^{64}-1$ bits
process data in a one-pass streaming mode, reading each message block only once

The BLAKE designers also decided they wanted to have the same interface as SHA2, which implied parsing input byte arrays to 32- or 64-bit words in a big-endian way (unlike MD5 for example).
Now, what part of BLAKE is actually coming from ChaCha?
Well, its core, the "G" function, which consists of 16 operations and is directly inspired from the "quarter-round" function used by ChaCha. But as I said, ChaCha is using 32-bit words!
So, they had to modify it in order to be able to support 64-bit words, they had to if they wanted to be able to match the SHA2 interface so that BLAKE can be a drop-in replacement for SHA2.
You might ask why, and the reason is mostly to allow Blake to take full advantage of the 64 arithmetic that is available on today's CPUs in servers and desktop computers, while still having a 32-bit version with Blake-256 that is more suited for older, or smaller devices.
ChaCha on its side has the goal of being a stream cipher, that is simple, and fast. To do so, and still be compatible with older or smaller devices, having 32-bit words makes sense. Plus, with a stream cipher, you want interoperability between platform without having to choose a specific version depending on your architecture to have better performances, whereas, with a hash function, it is customary to have more choice.
The rest of the design of BLAKE is indeed just a straightforward way to convert ChaCha into a secure hash function, but it still is important to do so while using the right methods, and so you could not "just take ChaCha" to have a hash function, since you still need for example to compress your message into a single fixed-size digest.
Why is stock chacha20 not good as a cryptographic hash?
Well, as mentioned above, ChaCha is a stream cipher, which means that it does not compress a message so that you get a fixed size digest, and it also does not care about the same kind of threats and attacks. (For instance, collision resistance is definitively not something that a stream cipher tries to tackle, but it is crucial to have a secure hash function.)
But as said by SEJPM in his answer, ChaCha is featuring a PRF function at its core, which maps onto the 512-bit space, which is a nice building block for many cryptographic algorithms, from stream cipher to hash function.
So, ChaCha being a stream cipher, it is not fit to be used as a cryptographic hash directly as it stands, but its core ideas were used by BLAKE designers in their compression function with fixed-size output digest. Also, the fact that ChaCha was well understood and studied help the crypto-analysis of BLAKE that ensured it had the right security properties.
Notice also that since you want to hash (almost) arbitrary size input, you need a way to extend the domain of your compression function, and BLAKE is using the HAIFA model to achieve "domain extension" and also its goal of being a secure hash function.
Notice that the later also answers your question about "why there seem to be no Merkle–Damgård like constructions". BLAKE avoids Merkle–Damgård because of its many pitfalls and prefers to use a simplified HAIFA construction instead.
Rough idea of how BLAKE works and its differences with ChaCha
Here I'll try to give you a high-level idea of how BLAKE works, which should also help you spot more differences with how Chacha works.
In order to hash a message $M$ with BLAKE-32 (the closest to Chacha):
The message is first padded so that the length of the padded message is a multiple of 512. But it is always padded with at least 66 bits since it allows for the last 64 bits of the padding to be the binary encoded bit length of the (unpadded) message.
The padded message is then split into 512-bit blocks and iteratively fed to the compression function along with the previous hash value, a 64-bit counter counting the bits already hashed, and an optional 128-bit salt.
Before you ask, the previous hash value for the very first block is an initialization vector (IV) that is defined in the BLAKE specification.
Notice that the compression function has a finalization phase, in which you compute the output hash value using its internal state $v_{0 \leq i \leq 15}$ and the salt $s_{0\leq i\leq 3}$ chosen by the user (0 by default):
$$h'_i \leftarrow h_i \oplus s_{i \bmod 4} \oplus v_i \oplus v_{i+8}$$ for $i = 0,\dots , 7$. The eight $h'_i$ are the output of the compression function. It might be interesting to note that this can be seen as a particular case of a Davies-Meyer-like construction. (See the BLAKE paper for more.)
It is also useful to note that the "core" G function of BLAKE is also differing from Chacha because it feeds 2 input words XORed with constants (that are defined in the specification and that were removed in the design of BLAKE2) into its state at each execution of the G function.
And notice also that the rotation (shifts) used in the G function are right ones, whereas Chacha is using left rotation. (But this is actually not changing much and is only due to a typo in one of the early specifications...!?! ^^ Congrats for making it so far, you deserved to know the truth!)
Finally to have a more visual idea of these latest points, here is the G function of BLAKE:
$$\begin{align}
a &\leftarrow a + b + (m_{\sigma_r(2i)} \oplus c_{\sigma_r(2i+1)})\\
d &\leftarrow (d \oplus a) \ggg 16\\
c &\leftarrow c + d\\
b &\leftarrow (b \oplus c) \ggg 12\\
a &\leftarrow a + b + (m_{\sigma_r(2i+1)} \oplus c_{\sigma_r(2i)}) \\
d &\leftarrow (d \oplus a) \ggg 8 \\
c &\leftarrow c + d \\
b &\leftarrow (b \oplus c) \ggg 7
\end{align}$$
compared to the "quarter-round" function used by ChaCha:
$$\begin{align}
a &\leftarrow a + b \\
d &\leftarrow (d \oplus a) \lll 16\\
c &\leftarrow c + d\\
b &\leftarrow (b \oplus c) \lll 12\\
a &\leftarrow a + b \\
d &\leftarrow (d \oplus a) \lll 8 \\
c &\leftarrow c + d \\
b &\leftarrow (b \oplus c) \lll 7
\end{align}$$
If you really want more details about how BLAKE works, the BLAKE paper is actually not too difficult to read.


From a technical side, there are three general scenarios that should be handled differently:

Scenario 1: You control the configuration of the server your client software will connect to, and expect to retain that control for the life time of your client software. In such case, you only have to (and probably should) enable a single cipher suite, both client side and server side. Given a choice between several cipher suites that all meet your minimum requirements, and presuming there is at least one AES cipher suite in this list, choose that one (for the reasons stated here).

That said, you obviously would have to enable more than one cipher suite if you are bound by a security requirement to have a fall back option, e.g. in case the cipher suite gets broken and your software upgrade mechanism is more likely to fail, than your ability to reconfigure the server. This is however the only technical reason to enable more than one cipher suite in this scenario.

If you know that the server implementation respects the cipher suite preference of the client, it might matter how the client orders the cipher suites. Generally, though, the TLS standard does not specify how the server should pick the cipher suite, so this would be implementation specific and a better question for stackoverflow.

Scenario 2: You do not control the configuration of the server, e.g. because your client software might connect to multiple servers, but you do know the configuration of a required minimum of the servers. If there is more than one cipher suite in the intersection of the cipher suites supported by these servers, and that set contains at least one AES cipher suite, the situation is not much different from scenario 1, except possibly that you might be more likely to be required to include a fall back option in this scenario.

Scenario 3: You do not control the configuration of the server, and your security requirements are different for different servers and different users. The intersection of these requirements is the empty set. In this scenario you are basically out of luck. Your best option might be to make the client cipher suites user configurable for someone with administrator privileges, but that would fall outside of the scope of cryptography and be a better question for IT security.


The Galois Field $\operatorname{GF}(2^4)$ (also represented $\mathbb{F_{2^4}}$) contains $16 = 2 ^4$ elements. The formal definition is;
$\mathbb{F_{2^4}}$ is the quotient ring $\mathbb{F_{2}}[X]/(x^4 = x + 1)$ of the polynomial ring $\mathbb{F_{2}}[X]$ by the ideal generated by $(x^4 = x + 1)$ is a field of order $2^4$.
We can list the elements of $\operatorname{GF}(2^4)$ on the polynomial representation with the defining primitive polynomial, namely $$a_3 x^3+a_2 x^2+a_1 x+a_0$$ where $a_i \in \operatorname{GF}(2)$ for $i=0,1,2,3$.
$\operatorname{GF}(2^4)$ is a Field therefore every element has a unique multiplicative inverse, except the zero.
$x^4$, as we can see, is not an element of the field, however, we can reduce it with the help of the defining polynomial's equation $x^4 = x + 1$. Therefore it has the same representation with $x+1$ in the field, so the inverse is the same.
Also, the multiplication inverse table has $2\times 16$ size, so there is only one row (or column ) to calculate.
\begin{array}{|c|c|}\hline
p(x) \in GF(2^4) & inverse \\ \hline
1  &  1  \\\hline
x  &  x^3 + 1  \\\hline
x + 1  &  x^3 + x^2 + x  \\\hline
x^2  &  x^3 + x^2 + 1  \\\hline
x^2 + 1  &  x^3 + x + 1  \\\hline
x^2 + x  &  x^2 + x + 1  \\\hline
x^2 + x + 1  &  x^2 + x  \\\hline
x^3  &  x^3 + x^2 + x + 1  \\\hline
x^3 + 1  &  x  \\\hline
x^3 + x  &  x^3 + x^2  \\\hline
x^3 + x + 1  &  x^2 + 1  \\\hline
x^3 + x^2  &  x^3 + x  \\\hline
x^3 + x^2 + 1  &  x^2  \\\hline
x^3 + x^2 + x  &  x + 1  \\\hline
x^3 + x^2 + x + 1  &  x^3  \\\hline
\end{array}
The non-zero elements of the field, usually represented by adding a star on the upper right $\mathbb{F}^*_{2^4} = \mathbb{F}_{2^4}- \{0\}$ form a multiplicative cyclic group. $\mathbb{F}^*_{2^4}$ can be generated by $x$, i.e. $\mathbb{F}^*_{2^4} = \langle x \rangle$. The powers of the generator;
\begin{array}{|c|c|}\hline
i & x^i \\ \hline
x^ 1  &  x  \\ \hline
x^{ 2 } &  x^2  \\ \hline
x^{ 3 } &  x^3  \\ \hline
x^{ 4 } &  x + 1  \\ \hline
x^{ 5 } &  x^2 + x  \\ \hline
x^{ 6 } &  x^3 + x^2  \\ \hline
x^{ 7 } &  x^3 + x + 1  \\ \hline
x^{ 8 } &  x^2 + 1  \\ \hline
x^{ 9 } &  x^3 + x  \\ \hline
x^{ 10 } &  x^2 + x + 1  \\ \hline
x^{ 11 } &  x^3 + x^2 + x  \\ \hline
x^{ 12 } &  x^3 + x^2 + x + 1  \\ \hline
x^{ 13 } &  x^3 + x^2 + 1  \\ \hline
x^{ 14 } &  x^3 + 1  \\ \hline
x^{ 15 } &  1  \\ \hline
x^{ 16 } &  x  \\ \hline
\end{array}
$p(x) = 0$ is not included since it has no multiplicative inverse.

Below is the SageMath code used in this answer.
#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^4+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

for p in S:
    if ( p != 0 ):
        print( p, " - ", 1/p )


Why do crypto tools display key components in such an unusual format?

As for the leading zero, I believe the tools are just displaying what's in the ASN.1 as is; the BER/DER encoding rules will insist on a leading 00 byte in some cases.

Specifically, if you encode a positive integer, the msbit of the value stored must be 0 (if it is a 1, the encoded value is assumed to be negative); if the msbyte of the value you want to store has a 1 msbit, then you must prefix a 00 byte byte to the stored value; this 00 byte does not change the value (obviously), but it does make the msbit 0.  In both case you have, the most significant nonzero byte has an msbit of 1; hence, they have a 00 prefix.

Now, you state that other components within the private key do not have a 00 prefix; I expect that, if you examine them, the first byte of those values will be somewhere in the 01-7f range, and so don't need a 00 prefix.


If using large keysizes, is McOE-X actually safe?

Basically they state that to break a key of length $n$, you need "just" $2^{n/2}$ complexity in both the offline and online phase. This is similar to the birthday paradox, where finding a collision also happens after $\approx 2^{n/2}$ steps for a $n$ bit hash.

With today's computation power, something like DES with 56 bits is possible to brute force. If you have a symmetric cipher with 128 bit, this is actually bad news, because $2^{64}$ isn't impossible to brute force (given enough ressources and time - in a realistic amount).

However, there is also that part of the attack, which is: $2^{n/2}$ online steps. If you willingly let that one happen in your system, and your server can actually handle that amount of requests, this becomes an issue. Actually, this might not really be possible in a realistic scenario, because $2^{64}$ is still a lot. And there is quite a difference when you compare the time for an online request from a server and an exeution of a symmetric cipher on an FPGA.

But anyway, going for a keysize of 256 bit solves that issue. Brute forcing 128 bit is well beyond anything we could ever achieve. Speaking in the terms of Universal security; from bits and mips to pools, lakes -- and beyond by Lenstra et al., 2013, this is more than "global security": The required energy would be more than to bring the water of the entire planet to boil.

Im summary, the attack is not a real danger, even with 128 bit encryption. The online phase should be far from realistic in a practical setup, easily noticable and easy to counter with a limit of requests your server answers. But you should nevertheless choose 256 bit keylength at least, and then it should be fine.

The switching of keys for the cipher might allow key-related attacks, like they were studied for AES. Then for the specific cipher of your choice there might be consequences. For example I am not aware if 3DES was analyzed for related-key attacks. But any decent modern symmetric cipher should be okay.


Hash function and outputs of arbitrary length

Keccak uses a sponge construction to output arbitrary length hashes. This is a distinctly serial operation. Although the inner permutation can be perfomed with a certain level of parallelism using bit-slicing, it is faster in software using native 64-bit operations.

P is the message input per block, z are outputs, and f is the inner permutation. In order to output a given length $x$, z is incremented until it meets or exceeds $x$, to which it is then truncated. The quantity of z required will vary due in implementation to the variable rate r not being a constant.

For example, if you need a 384-bit output and r is 128 bits, there will be 3 outputs which are then concatenated, and between each output is an additional permutation past the last input permutation (dashed line)


State level "Weak Diffie-Hellman" working for SRP too?

In the introduction of the Logjam paper, it is stated that

  After a week-long precomputation for a specified 512-bit
  group, we can compute arbitrary discrete logs in that group
  in about a minute.

So it seems that what it actually does is attack the discrete logarithm problem, so any discrete-logarithm-based system which uses a common prime should be equally vulnerable. In particular, in Section 3.2 of RFC 5054, it is stated that

  An attacker who could calculate discrete logarithms % N could compromise user passwords, and could also compromise the confidentiality and integrity of TLS sessions. Clients MUST ensure that the received parameter N is large enough to make calculating discrete logarithms computationally infeasible.

Since RFC5054 specifies only one prime for each bit-length, it will indeed be vulnerable. Even though it does not specify a 512-bit prime, it does specify a 1024-bit one, which is considered vulnerable by the Logjam authors:

  We estimate that even in the 1024-bit case, the computations are plausible given nation-state resources

Using a prime of at least 1536 bits should be sufficient to thwart such attacks, since there is no known "downgrade" attack on SRP.


What is the fastest way to generate a truly random one-time pad without electrical or any other complicated device?

We are going to generate a large number of truly random letters for use as a one-time pad (sometimes also referred to as Vernam Cipher).

Get your hands on about fifty six-sided dice--they are easy to order from a gaming company--and a shakeable box with a lid, and the box is about 30 centimeters square.

Build a random table: on a piece of paper, draw or print a table with six columns and six rows. Number the columns and rows, 1 to 6. Doing that sequentially should be fine. Put the dice in the box and shake, rattle, twist, and roll--use your own judgment. This step should not be short. Let the dice fall to one side of the bottom of the box and put them in rows of two.  Now start filling in your table according to the pairs of dice aligned in the box. Row/Column. 1/4 A, 4/3 B, 5/1 C, etc. Keep going until all letters of your alphabet have been entered.  If you are using a Russian alphabet, you will have three empty spaces.  If you are using an English alphabet, you will have ten empty spaces.

Generate your key: Shake, rattle, twist, and roll--consult the table to get your results:  5/1... C | 6/2... X | 1/1... P | etc. Repeat. Don't take any shortcuts.  Don't look at your results and say they are not random because there are too many of one number next to each other in the box. This is what it can sometimes look like. Don't introduce bias.

Secure your key: physical security is an important issue now.  You have to protect that key against compromise. If you can also share that key securely, then the traffic you create will at least have been enciphered with a real one-time pad.

Furthermore: you also have two additional problems--how will you authenticate your message, and will it have integrity?


Does an anonymous signature hide the sender's identity from the receiver?

It is perhaps more complicated.

Signer anonymity for anonymous signatures means anyone who has the signature but not the message (or does not know enough about the message) cannot reveal the identity of the signer.

Thus it really depends on, in your model, what the receiver or eavesdropper knows. For example, if one sends the signature and the message (in plaintext) together, then even the eavesdropper can know the signer's identity. For receivers, often they are supposed to verify a signature, so they know the identity of the signer. However, if your receivers are not verifiers (e.g. they just receive and store the signatures), then they may not need to know the messages, and if the messages are hidden from them, then they don't know the identity of the signer.


Simple example for CP-ABE (Ciphertext policy attribute-based encryption)

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct.

A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property
\begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = e(g_1,g_2)^{ab}\text{.}\end{align}
For cryptographic usage we also need the properties that the pairing is not degenerated and efficient computable. Your definition of the pairing does not hold all these properties.

Today, pairings are basically implemented with elliptic curves over finite fields ($\mathbb{G}_1$ and $\mathbb{G}_2$) and with an extended finite field ($\mathbb{G}_T$). All the three groups have prime order $p$ so that you can calculate the inverse in the exponent very easily: $g^{1/\beta} = g^{\beta^{-1} \pmod p}$.

I think it is not that easy to generate a toy example for pairing based cryptography, because you need special elliptic curves with known order, embedding degree and other parameters and an efficiently computable pairing function.

If you like to understand pairings better I can recommend the dissertation of Ben Lynn [1]. He also wrote the PBC Library [2] that implements pairings in C and is very easy to use.

[1] https://crypto.stanford.edu/pbc/thesis.html
[2] https://crypto.stanford.edu/pbc/


Any PRNG with a finite state size is eventually periodic. The maximum period possible is $2^n$ for an $n$-bit state, but the average with a well mixed state is $2^{n/2}$.

Here the hash function used is SHA-512, but the state is 1024 bits. A first guess would be a period of $2^{512}$, rather than the $2^{256}$ mephisto gives.

Let's look at the cycles. Both halves of the state are generated with HMAC-SHA512, so they would enter cycles of about $2^{256}$. However, because the inputs are different, they have their separate cycle structure. The two cycles are likely to be different lengths. The overall cycle is about as long as the least common multiple of the two lengths.

Two uniformly distributed random numbers have a small expected GCD, meaning the LCM would be close to their product. The lengths here are not uniformly distributed, but I believe the same is still more or less true. So the cycle length should be close to the $2^{512}$ expected with a 1024-bit state.


Can a key exchange protocol exchange a one time pad instead of a key?

In theory it could work, if you can ensure that the resulting key is actually generated uniformly from the full range, as long as one party chooses its input uniformly.

A rough sketch for a proof: Consider the inputs $x$ and $y$ to the key exchange $f(x,y)$. Then if you consider one input fixed the key exchange has to be a bijection. You need to proof that for every $x$, $f$ is a bijection between $y$ and $f(x,y)$.

But on the practical side, I can't think of any realization of this, where we can actually prove that. The obvious candidate is the DH key exchange. But if we use a generator $g$ for the full group, then we can't prove the above property: Assuming any fixed $x$, then $g^{xy}$ is not always a bijection, there is the counter example $x = 2$. If $g$ is a generator of a prime order group, then this property would hold. However, in this case you can only reach the elements of this particular subgroup and not all group elements. You would need a bijective mapping from the subgroup with $k$ elements to $\{0,1,\dots,k-1\}$ or similar. And that should be difficult, unless you assume you are able to calculate the DLOG. And this problem exists for both classical and EC-based Diffie-Hellman key exchange.


AES cache-timing attacks and nonce-based operation modes

There are multiple ways you can get the key in attacking AES.

Let's say you have the known cipher-text, $ct$, and a list of all S-box lookups used in the last round of AES (maybe from a cache-attack).

We know that $ct$ is equal to $k \oplus y$, where $y$ is the intermediate state after the last S-box computation.

Now, we can go through each byte of $ct$, and for each byte $ct_i$ we attempt a possible key value $k_i$ for each value 0x00-0xff. Then we can get a possible $y_i = ct_i \oplus k_i$. If we run an inverse S-box computation on this $y_i$ and it is contained in the list of S-box lookups we received earlier, then we know that this $k_i$ is a possible byte for the key $k$.

If we do this operation many times through many runs of AES, then we can develop a table of possible $k_i$ values for each byte in $k$. We can use the mode of each key byte $k_i$ to build our correct key $k$. The accuracy of this attack obviously increases with more runs of AES.

As seen in this attack, you do not need to know the input of AES, only the output $ct$ and some last-round S-box information.

Hope this helps.


How secure is a book derived key and what can be done to strenghten it?

The key selection must always be sufficiently random.

The key can never be considered reliably secure if the selection is simple ("Book A, page B") since the number of possibilities is necessarily too low.

Considering poems in Afrikaans has been cracked it's a necessity to NOT rely on a published book being unknown to the adversary.

Secure book based ciphers often include a list of references to individual books, individual pages, and different paragraphs in turn. In this case it is the sum of many independent unpredictable selections that provide the security a key needs.


Problem with calculating the correct value for $(p-1)*(q-1)$?

So, you're given the exponents (and the ciphertext), and are expected to recover the modulus?  That's certainly not the standard way of using RSA.

It turns out that the necessary and sufficient conditions on $p, q$ is that $p-1, q-1$ are factors of $ed-1$; hence we know that $p, q \in \{ 3, 5, 11, 17, 41 \}$ (as those are the primes that meet this criteria), and any such combination of distinct $p, q$ would work (we also know that $pq > c$, however all combinations meet this criteria); by work, I mean that $(m^e)^d \equiv m \bmod{pq}$ for all messages $m$.  Now, with some combinations, the $e, d$ combination might not be minimal; however nonminimal $e, d$ values do happen in practice.

As both $p, q = 5, 11$ and $p, q = 3, 11$ meet the above criteria, both lead to valid answers.  If the original question did not add any additional information, well, they did not specify the question sufficiently.


Real life collision when only using truncated hash

Accidental collisions are interesting for certain applications, and one would expect accidental collisions to occur less frequently in a system than malicious collisions.

So, if you are not worried about malicious collisions, only accidental, it is easy to compute how many digests you would need to compute before seeing an accidental collision. If the output of the hash (either truncated or not) is $n$ bits long, you would expect to see an accidental collision once there are about $2^{n/2}$ digests in your database.

As for what is publicly known for accidental collisions, I haven't come across any data. Probably because accidental collisions are not very interesting. We know exactly how many digests to compute before expecting to see one, so why waste the electricity to experimentally validate what we already know mathematically?

Looking at some numbers for SHA-1 on a GPU, if you can perform $1,746,000,000\approx 2^{30}$ sha-1 operations per second, and we would expect a collision after $2^{80}$ operations, it would take $2^{50}$ seconds (or about $35702051$ years) to see an accidental collision (ignoring future increases in computation power).

On the other hand, the same website lists MD5 at about $5,570,000,000\approx 2^{32}$ MD5 computations per second. A collision would be expected after about $2^{64}$ computations. That equates to $2^{32}$ seconds (or about 136 years).

You can follow the math then to see how long for various truncated versions of both MD5 and SHA1.


Is that simple additive homomorphic scheme secure?

It is not semantically secure. If the adversary asks for the encryption of message $0$ then it gets $r_i,r_i*s$, so it recovers the secret key $s$ and breaks the security game.


AES-256 CTR with ESSIV, is this correct?

It seems in my case IV was supposed to be generated using AES-256 in ECB mode.

ESSIV_IV = E(data=SN, key=HMAC(KEY))

where E is AES-256 ECB, SN is sector number of disk data, extended to 16B (padded with zeros) and KEY is 32B long encryption key (HMAC = SHA-256).


What's the strategy for future directions in cryptography? Bigger numbers/faster searching, or new methods, say, of factoring?

If you're asking about the likely future for public key cryptography, then my opinion is that we are likely to see a transition (gradually over the next number of years) from things such as RSA and DH, and into Elliptic Curve Cryptography.

This is because ECC is just more efficient; we know that we can break RSA and DH in subexponential time; that means that as computers get faster, and we need to make the problems more difficult, the modulii that we need to use for RSA and DH get larger a lot quicker than you would naively expect.  On the other hand, with ECC, the curve sizes don't grow very much at all.  So, instead of going to increasingly large RSA key sizes, I expect that people will gradually transition to ECC (as people become more comfortable with it).

If a new factoring method is found (which, personally, I don't expect), then all that would do is make that transition happen that much faster.

What would be a real game changer would be if someone was able to build a real quantum computer; a large enough one would be able to break RSA and ECC easily.  There are public key algorithms that don't appear to be solvable by a quantum computer (at least, not significantly easier than a conventional one); we'd transition to such an algorithm instead.


Any benefit to encrypting IV and MAC in a mode like AES-GCM or ChaChaPoly?

If a (nonce, key) is reused with two distinct messages A and B, an attacker can learn A⊕B = E(A)⊕E(B).

So, if either plaintext is known, the other one can be immediately decrypted.

This is why nonce-misuse resistant schemes require two passes: a first pass to compute a hash of the message, the second one to perform the actual encryption with an IV, and possibly a subkey derived from that hash.


There is an answer in PKCS#7 in section 11. Signed-and-enveloped-data content type.
Below encryption with the signer's private key means signing process.

"The signed-and-enveloped-data content type consists of encrypted content of anytype, encrypted content-encryption keys for one or
more recipients, and doubly encrypted message digests for one or more
signers. The "double encryption" consists of an encryption with a
signer's private key followed by an encryption with the content-
encryption key.

The process by which signed-and-enveloped data is constructed
   involves the following steps:

    1.   A content-encryption key for a particular content-
         encryption algorithm is generated at random.

    2.   For each recipient, the content-encryption key is
         encrypted with the recipient's public key.

    3.   For each recipient, the encrypted content-
         encryption key and other recipient-specific
         information are collected into a RecipientInfo
         value, defined in Section 10.2.

    4.   For each signer, a message digest is computed on
         the content with a signer-specific message-digest
         algorithm. (If two signers employ the same message-
         digest algorithm, then the message digest need be
         computed for only one of them.)

    5.   For each signer, the message digest and associated
         information are encrypted with the signer's
         private key, and the result is encrypted with the
         content-encryption key. (The second encryption may
         require that the result of the first encryption be
         padded to a multiple of some block size; see
         Section 10.3 for discussion.)

    6.   For each signer, the doubly encrypted message
         digest and other signer-specific information are
         collected into a SignerInfo value, defined in
         Section 9.2.

    7.   The content is encrypted with the content-
         encryption key.

A recipient opens the envelope and verifies the signatures in two
   steps. First, the one of the encrypted content-encryption keys is
   decrypted with the recipient's private key, and the encrypted content
   is decrypted with the recovered content-encryption key. Second, the
   doubly encrypted message digest for each signer is decrypted with the
   recovered content-encryption key, the result is decrypted with the
   signer's public key, and the recovered message digest is compared to
   an independently computed message digest..."


What is the best technique I can use to encrypt inner nodes in B+tree?

We don't know your scheme, so we cannot say which technique is better for you, but in most earlier schemes that use binary vector (or any integer vector) for store information, Secure Inner Product is most used tools for encrypting! And it's useful for searching in some condition and depend on search construction.

P.S. Why you using bloom filter that has false positive issue?
I'm working on SE too.


Pseudo-random generator explanation by Bruce Schneier

This is a about properties of a random sequence in general.

  What does statement "or example, they should have about the same number of ones and zeros, about half the runs(sequences of the same bit) should be of length one, one quarter of length two, one eights of length three, and so on. " mean?

Consider a coin toss with a perfect coin (i.e. one that doesn't land on the side and lands on head or tail with 0.5 chance). Then about half of the time it will be a head or a tail. If you would toss it infinite times then you would have an equal amounts of heads and tails. However, if you toss it some other amount you'd expect about the same number of heads and tails.

If you would toss the coin an odd number of times you would certainly not have the same amount of ones and zeros, even with a perfect coin.

  What does statement "Theere should not be compressible"?

Probably this should read "they should not be compressible". Things are compressible when a pattern can be found (think .zip files). If a pattern can be found then the sequence is not random. Note that small patterns can exist by chance, so this requirement is a rather heuristic (unless there is a different definition of compressible around).

Then again, you should not be able to always compress the random number sequences generated.

  What is number 643,863,99,1357?

That looks like a set of references to me, nothing to do with the random numbers in itself :)


It can guarantee the integrity, because you can not fake another voting with the same hash.
However, this only shows the ballot is casted correctly, but does not prove the ballot is correctly counted. And as you said, it can not provide anonymity, such as buying vote and coercion.


My Sketch on the reduction proof:

Basic Assumption: I got a Cryptosystem #1 that is CCA secure

Based on this Cryptosystem I can build a CPA secure Cryptosystem #2, and I assume, that an adversary can break it with non negligible probability

Therefore I can build a Reduction: R can simulate the CPA game with A and just gives the messages of A to his challenger and the response back to A. R then outputs the result of A.

Because A has a non negligible probability in breaking #2, R also has a non negligible probability in breaking #1, which gives a contradiction to the basic assumption

Therefore CCA implies CPA

I hope the basic idea is correct.


Why is it so hard to make longer hashes?

That article is talking about the core function and state size. It's easy to get a larger output using a whole range of instructions. Using a counter, like your example, does indeed constitute a correct way of generating more output. It's extensively used in constructions for creating a pseudo random function (CSPRNG or DRBG) or key derivation function (KDF).

The problem is that if you want to also have 1024 / 512 bit security you'd need to use a larger state. In that case you'd need a different construct, or you'd have to use 128 bit instructions. Your example doesn't use a larger state and therefore is unlikely to provide full 1024 / 512 bit security. Currently however 128 / 256 bit security is deemed plenty, so there is very little reason to go that way.

If you want to have a hash function with the same security and still larger output, you might have a look at the SHA-3 XOF's: SHAKE-128 and SHAKE-256. Due to the construction of the sponge it's easy to generate more output while the internal state (and thus the security) remains the same. It's basically still SHA-3, it doesn't even need alteration of the core function nor an external construction using a counter.


Read Wikipedia: Trapdoor function

Then read Luca Trevisan's lecture notes (jump straight to section 2. Trapdoor Permutations and Encryption).  Or, read any other textbook or lecture notes that covers trapdoor permutations.

For instance, if $(n,e)$ is a RSA public key, then $f(x) = x^e \bmod n$ is a trapdoor permutation.  It is a permutation, since the function $f:S\to S$ is bijective (where $S=(\mathbb{Z}/n\mathbb{Z})^*$).  It is a trapdoor one-way permutation, since given $x$ and the public key, we can easily compute $f(x)$, but given $y$ and the public key, it is difficult to compute $f^{-1}(y)$; yet with the private key (the trapdoor), we can easily compute $f^{-1}(y)$, given $y$.

That should answer your question.


In counter mode the block cipher operates as a PRNG, essentially like the keystream generator of a synchronous stream cipher. The key and the nonce determines the starting-point of the PRNG, thus if the nonce is ever reused with the same key, the keystream produced is the same.

Why is this bad? Because if you ever figure out the plaintext corresponding to the ciphertext of one message encrypted with the repeating keystream, deducing the keystream is trivial ( ciphertext = plaintext XOR keystream ), and you may easily decrypt any other message encrypted with the same keystream. (Essentially a known-plaintext attack).

To answer your specific questions:

If the same plaintext is encrypted with the same nonce (and the same key), the ciphertext is identical.
If the plaintext is "unique" (different is perhaps more accurate), the ciphertext is different. But as explained above, if the adversary gains knowledge of any plaintext-ciphertext pair, (s)he may decrypt all the other messages.


Proving Pseudo Random Generator from other Pseudo Random Generator?

Well I think you can prove it by reduction:

If there exist an efficient predictor $P$ that given the first $n$ bits of $G'$ is able to predict the $n+1$ bit then we can construct a distinguisher $D$ for $G$ defined as an elementary wrapper of $P$, that can distinguish $G$ from a truly random generator.
Since by assumption $G$ is a (secure?) pseudo-random generator there is not such a $D$.


Isn't the structure of a potential plaintext of a ciphertext generated by a one-time pad dispositive, cryptanalysis-wise?

No that is not correct, here is the thing, given a ciphertext say ezcle, there exists a key such that this would decrypt to hello, another key such that this decrypts to harry, another key which will decrypt to frank, another key which will result in world. And every other 5 letter word in the dictionary, and every other 5 letter combination of letters (I'm restricting to letters to make things simple).

Sure there are a lot of outputs that are garbage, but there are a lot of outputs that are not garbage, but every 5 letter word in the dictionary will also appear. Thus, before doing this cryptanalysis, you had a pretty good idea that the ciphertext encrypted a 5 letter english word say. After your cryptanalysis, you have not eliminated a single 5 letter word from the possible plaintexts. Thus you have gained no extra information by doing the cryptanalysis.


In theory no, there will be no better chance.

The key must be at least as long as the original text. The key must have high entropy (simply said, it should be random enough). Then revealing any part of the original text has no effect on the decryption.

In practice, if the process is realized improperly, there can be some issues:

If the key is shorter that the original message.
If the key is not random enough.
If the the OTP generator is not random enough and the attacker knows a lot of other OTPs produced by this generator.