Is it safe to generate two 256-bit ECC keys from 128 bits of entropy?

The safe way to generate a large amount of entropy from a small seed is to use a CSPRNG. Most CSPRNGs in practice use a stream cipher at their core to expand a small amount of input entropy into a large keystream. The way this is done (and the process of seeding and re-seeding the generator) is very important to security, so it's best to use an existing library or your operating system's built-in CSPRNG.

The multi-target attacks are better described in DJB's page on batch attacks. They're an issue whenever there are a large number of users each with a large number of keys. The chances that an attacker will guess at least one key that at least one user has used can be quite large, even though the chance that the attacker will guess one specific key of any one specific user is still minuscule.

Batch attacks are an issue for AES-128 because 128-bit AES keys are often generated in the ephemeral key exchanges of TLS sessions. Every time a user goes to a new https webpage a new key is generated with them. Consider all users across all https pages on the internet and the chances that the NSA/PLA/FSB/Mossad/etc will be able to decrypt at least some traffic are actually quite high.

Batch attacks are much less of an issue for ECC keys, as they are often quite long term. There simply aren't enough private keys for Monero wallets for this to be a significant issue.


What basic knowledge is required to understand SIKE?

Craig Costello has tried writing precisely what you're interested in, see SIKE for Beginners. It refers to numerous other surveys for isogeny-based crypto which may be useful (lecture notes by De Feo, and surveys by Galbraith-Vercauteren and Smith).
Galbraith also has a book on the math behind crypto. Chapter 25 deals with isogenies, so may be useful for mathematical background (but does not discuss SIKE).


Hashing a password before using for online accounts

Is there any problems from using the approach I am suggesting?

Yes, there are several.

First of all, some sites generate first time passwords, or even long time passwords. You may want to store those too. What if a site requires frequent updates?

If one password is reversed, you'd still loose confidentiality.

  Would it actually be less secure if the server encrypted my already encrypted password?

No, usually not. If you don't know the server's key then using encrypted input will not change encryption. Same goes for password hashing basically. If you don't operate with the same parameters (e.g. salt), then you are unlikely to be vulnerable.

  Should I encode the output in base64 or ascii85, or something similar?

Anything the target site accepts. This points to another issue since the sites may require passwords in a specific format. Both the alphabet (character input) of the password and the size may be restricted. So some sites would be better off with base64, some with base 85 and others with neither of the above. E.g. an 8 character base 64 string only has 48 bits of security, allowing brute force attacks. How are you going to remember which format is best for specific sites?

  Which algorithm would be best suited to this task? Do I need something more secure like SHA-1 or will the more primal MD5 be adequate (would anyone care enough to try to break the hash)?

When constructing security protocols you'd have to assume that somebody "cares". Otherwise you might as well skip the whole thing. That said: no, SHA-1 or MD-5 will likely not influence the choice much.

That all said and despite all the indicated issues, hashing the password is still somewhat more secure than providing a password with extension directly. But since you would need to have a device & application for this anyway, I'd recommend using a password manager instead (that e.g. applies a password hash or PBKDF over the master password to decrypt the database).


Though not my normal recommendation, the SHA-512-based password hash as implemented in Linux is a fine password hashing algorithm.  It is based on a well-understood cryptographically secure hash (SHA-512). It has a significant size salt and configurable number of rounds (default 5000). I would not feel insecure with such a hashing algorithm.

$2$ is indeed bcrypt, but note there are several variants around sometimes marked 2a or 2b and sometimes not marked. So, though bcrypt is considered very secure if you need a standard password hashing function, you need to be careful when choosing bcrypt.


Yes, pretty much the same groups usable for ECDSA are usable for Schnorr signature. That was in [Sc91] (see bibliography in this question):

  It is possible to implement the above signature and authentication scheme using a finite group $G$ other than the subgroup $\mathbb Z_p^*$ of units in  $\mathbb Z_p$ (..) Examples of suitable groups are e.g. class groups and elliptic curves $E(K)$ over a finite field $K$.

It looks like you invented yet another variant of the Schnorr signature algorithm for elliptic curves, not among the about 6 in this answer. Yours sends a group element rather than a hash as the first part of the signature (thus more directly matching the transformation to signature of the Schnorr indetification protocol, and allowing a more direct proof of security). This has a strong taste of EC-FSDSA (Elliptic Curve Full Schnorr Digital Signature Algorithm) of ISO/IEC 14888-3 (OID 1.0.14888.3.0.12), but:

For some reason you compute $H(m\|x_0)$ rather than $H(x_0\|y_0\|m)$ in said standard; hereafter I write $H(\dots)$. For an ideal hash and proofs in the ROM, hashing $m$ first or second is immaterial, and I can't decide if it makes any security difference for practical hashes. Not hashing $y_0$ might cost some security.
Your verification procedure omits to verify that $S_0$ is a point on the curve, which seems risky since you perform point addition on that. The standard mandates this check.
My understanding is that the standard does $Q=-a\times P$ (as suggested by Schnorr as soon a [Sc89]), so that verification can compute $s_2\times P+H(\dots)\times Q$ and compare it to $S_0$, with two advantages:

the computation of $s_2\times P+H(\dots)\times Q$ can use the simplest forms of Shamir's trick, or others
checking that $S_0$ is a point on the curve becomes redundant.

Note: for elliptic curves $y^2\equiv x^3–3x+b\pmod p$ at least (including NIST's FIPS 186-4 curves over prime fields), while you are at not hashing $y_0$ and using something non-standard, you could as well omit $y_0$ from the signature, with verification computing $s_2\times P+H(\dots)\times Q$ and comparing it's $x$ coordinate to $x_0$. That shortens the signature from $6b$ to $4b$ for $b$-bit security, and (for ideal hash) costs at most 1 bit of security (perhaps nothing), since $y$ can be found from $x$ within sign.


How do other, non-RSA algorithms, compare to the PKCS #1 standard?

RSA is two algorithms, one for asymmetric encryption, the other for digital signatures.

For asymmetric encryption, the main competitors of RSA would be:

The Rabin cryptosystem
ElGamal
NTRUEncrypt
Diffie-Hellman key exchange (in practice, key exchange is almost as good as asymmetric encryption, since most usages of asymmetric encryption are for sending a key, followed by symmetric encryption).
McEliece

For signatures, there are variants of the above; for ElGamal-like signatures, the most well-known variant is DSA.

The biggest advantage of RSA over almost any other competing algorithm is that it has a standard (PKCS#1) which unambiguously states where every byte should go. For wide industrial acceptance, such a standard is a must-have -- and it is even a free standard. This alone can explain the current dominant position of RSA. On that point, the only algorithms which can put up a fight with RSA are DSA, its elliptic-curve variant ECDSA, Diffie-Hellman, and elliptic-curve variant thereof. Only the DSA standard itself is free.

For performance, RSA public key operations are very fast, much faster than public key operations for discrete logarithm. On the other hand, elliptic-curve variants of DSA and DH are quite faster than RSA for private key operations. This can be seen by using OpenSSL with the openssl speed command-line tool. On a cheap and not-that-new 1.6 GHz AMD CPU (in 64-bit mode), I get this:

$ openssl speed rsa2048 dsa2048 ecdsap224 ecdhp224
Doing 2048 bit private rsa's for 10s: 1996 2048 bit private RSA's in 9.99s
Doing 2048 bit public rsa's for 10s: 70600 2048 bit public RSA's in 9.99s
Doing 2048 bit sign dsa's for 10s: 7311 2048 bit DSA signs in 9.99s
Doing 2048 bit verify dsa's for 10s: 6218 2048 bit DSA verify in 9.99s
Doing 224 bit sign ecdsa's for 10s: 43073 224 bit ECDSA signs in 10.00s
Doing 224 bit verify ecdsa's for 10s: 9760 224 bit ECDSA verify in 9.99s
Doing 224 bit  ecdh's for 10s: 11474 224-bit ECDH ops in 9.99s
OpenSSL 0.9.8k 25 Mar 2009
built on: Thu Feb 10 01:45:33 UTC 2011
options:bn(64,64) md2(int) rc4(ptr,char) des(idx,cisc,16,int) aes(partial) blowfish(ptr2)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT
-DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -O3 -Wa,--noexecstack
-g -Wall -DMD32_REG_T=int -DOPENSSL_BN_ASM_MONT -DSHA1_ASM -DSHA256_ASM
-DSHA512_ASM -DMD5_ASM -DAES_ASM
available timing options: TIMES TIMEB HZ=100 [sysconf value]
timing function used: times
                              sign    verify    sign/s verify/s
rsa 2048 bits             0.005005s 0.000142s    199.8   7067.1
                              sign    verify    sign/s verify/s
dsa 2048 bits             0.001366s 0.001607s    731.8    622.4
                              sign    verify    sign/s verify/s
224 bit ecdsa (nistp224)  0.0002s   0.0010s     4307.3    977.0
                              op                 op/s
224 bit ecdh (nistp224)   0.0009s               1148.5

(I have slightly edited the output so that numbers are graphically aligned.)

This tests 2048-bit RSA vs 2048-bit DSA, and ECDSA and ECDH over a 224-bit curve, which should supposedly offer similar security. RSA is sorely beaten for private-key performance, but really shines for public-key operations.

Also (this is not apparent on this benchmark), DSA and ECDSA offer shorter signatures than RSA (56 bytes for ECDSA over P-224, vs 256 bytes for RSA-2048).

DSA and Diffie-Hellman got a lot of push from the US federal government in the last century, because at that time RSA was still patented. Otherwise, FIPS 186-3 would not have existed as a free standard. Nowadays, a lot of governmental organizations are pushing for the adoption of elliptic-curve cryptography, because it "feels unsafe" to rely on a single primitive: in case RSA gets spectacularly broken, there should be an alternate set of algorithms already developed.

For the figures above, we can see that ECDSA and ECDH are decent competitors for RSA, and have an edge over it in some specific cases. Yet support is not as widespread as for RSA, because the relevant standards are much more recent and involve higher-level mathematics (at some point, the implementer -- who writes the actual code -- must understand what is going on, and RSA is easier to understand).

In the future, NTRU may be a faster alternative, but right now it is aggressively patented, and still quite new (that's one of the benefits of a patent: it forces the rest of the world to wait a bit before deploying the algorithm, and this leaves time for cryptanalysts to do their job).


You van use DH over elliptic curve or over Zp for authentication. If the authenticating party has a fixed DH key and published in advance the public part $g^a$ (or multiplication for ECDH).
When we want to authenticate we can create a mutual DH key $g^{ab}$ and then the authenticator can prove knowledge of this in many ways.
encrypt a challenge with this as key would be a simple way. Could equally decrypt a challenge, or hash a challenge with the key prepended.
Or something fancier like socialist millionaire which gives zero knowledge proof both sides have the same key.
And if both sides have the other side public dh key it supplies authentication of both sides.


Is a KDF needed when using X25519 for ECDH and XChaCha20-Poly1305 for AEAD?

Generally speaking, there are (at least) three reasons to put a KDF in between an DH shared secret and the bulk encryption.

Improved re-usability. If you don't post-process the shared secret with a KDF there's no way to give the sender and the recipient different keys for each direction or to split up authentication and encryption keys. An additional bonus would be, that if you keep the shared secret, you could easily implement a session resumption feature by increasing some helper counter which is fed into the KDF.
Weaker security reduction assumptions. If you feed the shared secret into a KDF, then you only rely on the CDH problem holding (and model the KDF as a random oracle). If you feed the key directly into a cipher, you rely on the DDH assumption which is known to be broken for some groups where the CDH holds.
Better match with expected key properties. Symmetric ciphers are constructed, modeled and analyzed with only fully random keys in mind (or some computationally indistinguishable variant). However DH and ECDH shared secrets are integers and curve points which exhibit structure which violates the randomness assumption. A quick pass through a KDF doesn't cost much and fixes this.

 Glossary: KDF: key derivation function; CDH: computational diffie-hellman problem; DDH: decisional diffie-hellman problem; DH: diffie-hellman; shared secret: result of a DH key agreement protocol execution; ECDH: elliptic curve variant of diffie-hellman


You're simply appending the userKey to your "sleutel" (aka key) in this piece of code:

$sleutel = $this->sleutel . $this->userKey;

Problem is, doing that can result in $sleutel lengths beyond the expect 256 bits (32 bytes), or - as you are experiencing - less than the expected 256 bits (32 bytes/characters).

As @CodesInChaos correctly mentioned in his comment:

  AES-256 uses a 256 bit or 32 byte key by definition. No more, no less.

So, to fix your problem, you will have to make sure the key you are passing to your cipher function is no more and no less than 32 bytes.

To achieve that, you can simply choose to follow the usual path of encryption by taking your $sleutel and hash your key to the expected 256-bit length with (for example) MD5, like this:

$sleutel = md5($this->sleutel . $this->userKey);

or — if you prefer to choose another hash and a speedier function — you can use PHP's hash function, with it's multiple of available hashes to select from, like (for example) this:

$sleutel = hash('ripemd128', $this->sleutel . $this->userKey);

But… that's not the way I would recommend you to do it! Because, you don't want to use a weak hash like MD5 (which is known to have collisions), and you surely don't want to feed a weak hexadecimal character sequence to your cipher either, do you?

My Recommendation

Following current crypto standards, my recommendation is to use SHA256 the way it is supposed to be used in this case:

$sleutel = hash('sha256', $this->sleutel . $this->userKey, TRUE);

Notice that there's a 3rd parameter which is set to TRUE, which means $sleutel will contain 32 raw bytes (= binary characters) instead of 64 human-readable hexadecimal characters.

I'm sure that will fix your "short-key" related problems, as well as any potential "long-key" problems.


I think you are right (in the other question): “security of protocol $P$ reduces to assumption $X$” is incorrect (or at best too sloppy) language, and has too much potential for confusion. This is both because the intended “direction” of the reduction is not completely clear (does breaking $P$ imply breaking $X$, or the other way around?), and a reduction is supposed to be from one computational problem to another (but “security of $P$” is not a problem).

Saying “security of $P$ is based on assumption $X$” is fine, and is more naturally phrased than “breaking $X$ reduces to breaking $P$.” Though it is perhaps not entirely explicit that there is a formal reduction, because a few authors might say this even without a reduction. (But I think they would be wrong to do so.)

All this is somewhat a matter of opinion, relating to prescriptivism versus descriptivism in language. The descriptivist argument is that words and phrases take on meanings when enough people say they do, so “security reduces to” is fine. But for precise technical and mathematical language, especially where the intended meaning could be one of two completely different things, I would lean toward prescriptivism, and “reduction”/“reduces to” already have established meanings that were inherited deliberately from complexity theory.


Is there a cipher that uses part of the already-computed ciphertext in the encryption scheme?

The concept you mentioned is used in self synchronising stream ciphers. For example, CFB mode of a block cipher uses
$$C_0=IV$$
$$C_n=E_K(C_{n-1})\oplus P_n, \quad n \geq 1$$
with $C_n,P_n$ denoting the $n^{th}$ plaintext and ciphertext blocks.
So if you substitute "block" for "symbol", this is the same as what you want. CBC mode also gives a self synchronising stream cipher.

Moustique is a self synchronising stream cipher designed by J Daemen.


X509 converted to Encrypted and Signing keys

The PKCS12 (p12, pfx) is a standardized keystore where you may store multiple keypairs (key and certificate) or certificates themselves. It can be read/manipulted by multiple tools (OpenSSL, Keytool, keytool-explorer, ...).

You may have multiple certificates in you PKCS12 archive, it's usually a certificate chain with the certificate itself and its issuer (certificate authority). The certificates should be 'chained' (in a hierarchy).

Mutual SSL is used where the trust needs to be mutual (it's not only you want to be sure you speak to the right server (server only SSL), the server wants to be sure the client is who it claims to be). During the SSL handshake (or SSL renogotiation) the SSL server passes a set of trusted certificate authorities and the client then provides its own certificate if it is trusted by one of the offered CAs. Then the identity (private key ownership) is ensured by exchanging encrypted piece of data. It is a very effective method ensuring that only trusted clients are able to connect to the service.

Updated: why are there two certificates with the same user data but different purpose?
You have 2 certificates to the same key? Do they have the same issuer? Technically any certificate could be used to authenticate or to sign data. Legally - it may be different. It is common (e.g. on the eID cards) to have separate certificate for authentication and for signing. So you don't sign anything (legally binding) while you think you are authenticating to a service.. But -if they are both in the same keystore - don't you have the certificate chain there?


How much of Probability do I need to know to study Cryptography?

Not much. All you need can be found in any "Intro. to cryptography" book such as Katz/Lindell. In particular, you don't need any of the fancy measure-theoretic stuff since in cryptography you only work with discrete distributions.


Efficiency of oblivious algorithms vs non-oblivious algorithms?

Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to design an ORAM matching the lower bound.
No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell out of N cells requires $O(1)$ time in non-oblivious case but $\Omega(\log n)$ time in oblivious case, implied by the lower bound. I cannot think of more "useful" algorithms since there are not many lower bound proven.

I'm posting two relevant citations:

Nicholas Pippenger and Michael J. Fischer. Relations Among Complexity Measures. Journal of the ACM, Vol. 26, No 2, April 1979, pp 361–381. ACM PDF
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, Vol. 43, No 3, May 1996, pp 431–473. doi:10.1.1.44.8961 ACM PDF

[follow up]

Adding more relevant (but incomplete list of) papers.

Goodrich, Michael T. "Randomized shellsort: A simple oblivious sorting algorithm." In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1262-1277. Society for Industrial and Applied Mathematics, 2010.
Mitchell, John C., and Joe Zimmerman. "Data-oblivious data structures." In LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
Zahur, Samee, and David Evans. "Circuit structures for improving efficiency of security and privacy tools." In Security and Privacy (SP), 2013 IEEE Symposium on, pp. 493-507. IEEE, 2013.
Goodrich, Michael T., and Michael Mitzenmacher. "Privacy-preserving access of outsourced data via oblivious RAM simulation." In International Colloquium on Automata, Languages, and Programming, pp. 576-587. Springer Berlin Heidelberg, 2011.
Blanton, Marina, Aaron Steele, and Mehrdad Alisagari. "Data-oblivious graph algorithms for secure computation and outsourcing." In Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security, pp. 207-218. ACM, 2013.
Nikolaenko, Valeria, Stratis Ioannidis, Udi Weinsberg, Marc Joye, Nina Taft, and Dan Boneh. "Privacy-preserving matrix factorization." In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 801-812. ACM, 2013.
Keller, Marcel, and Peter Scholl. "Efficient, oblivious data structures for MPC." In International Conference on the Theory and Application of Cryptology and Information Security, pp. 506-525. Springer Berlin Heidelberg, 2014.
Wang, Xiao Shaun, Kartik Nayak, Chang Liu, T. H. Chan, Elaine Shi, Emil Stefanov, and Yan Huang. "Oblivious data structures." In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 215-226. ACM, 2014.


It should be pretty much the same. If you can sign a CSR with RSA you can sign with ECC. The exact same data is signed, what changes is:

The signature algorithm should be the right OID (e.g. ecdsaWithSHA256)
The signature value must be the ECDSA signature encoded as specified in SEC (i.e. an ASN.1 sequence of the two integers in the signature)
The public key value must a SubjectPublicKeyInfo structure with values specified in RFC5480: the algorithm field is an AlgorithmIdentifier whose algorithm field is the OID id-ecPublicKey and whose parameters field is the OID of the curve used. Finally, the subjectPublicKey field in SubjectPublicKeyInfo is the public key encoded as specified by SEC section 2.3.3.


Does the DES s-box only provide confusion, or does it also provide an avalanche effect?

Well it goes a long way towards it.  If you simply consider an S box on it's own, you'll virtually have the avalanche effect across it.  Even with a randomly permuted one.  This is just a function of the input /output non linearity.

The 100% avalanche effect is brought on by DES' S box in conjunction with other components such as permutations and xor operators on the outputs of these, as in the points where the 48 bit subkeys are mixed in.  The number of rounds is also important. Generally, there is  a relationship between the width of the S boxes, the number of adjacent s boxes and the number of rounds. It's entirely possible that without enough rounds, you might only get  say 90% of avalanche effect.

It's easier to describe the avalanche effect itself, rather than the required steps to provide it.  That's why testing is crucial to confirm that a primitive has it.  You can have a pretty good suspicion that a construct might exhibit avalanche effect, but you won't be able to confirm it without testing.

S-Box Modifications and Their Effect in DES-like Encryption Systems is a good article on the DES S boxes and messing with them. Specifically look to section 4.2 regarding DES box 5.


Why do we approximate R-1 rounds during linear or differential cryptanalysis?

is it because we already know the output or why ?

It's one of the strategies we use to turn a distinguisher (which a differential or linear characteristic) into a key recovery attack.

Here's how it goes; suppose we have a distinguisher that works over R-1 rounds, that is, given a number of plaintext/ciphertext pairs, it can tell us (with advantage over random guessing) whether or not those pairs there generated via the R-1 cipher (and an unknown key).

Then, we can then test guesses for the subkey on the last round on the full R round cipher.  We take our guess of the subkey (or a subset of that subkey, if our distinguisher doesn't rely on the entire ciphertext block), and then decrypt it through the round function to get the intermediate state after R-1 rounds.  Then, we can use our R-1 distinguisher to check whether the known plaintext and our guesses that the R-1 state are consistent with the R-1 cipher; if it is, then our guess for the subkey (or subset) is likely accurate.

If successful, this gives us some of the subkey bits; depending on how the key scheduling works, we may be able to deduce some key bits directly; alternatively, we may need to rely on other distinguishers (based on our knowledge of some of the subkey bits) to obtain others.

Obtainly, the details of how this works can vary significantly depending on the details of the cipher; this is just the general strategy.


Calculating entropy within xkcd 936: Password Strength

I don't get nearly the amount of entropy stated in the comic.

Interestingly enough the reasoning for the entropy rating are actually justified in the comic by the little boxes which each represent 1 bit of uncertainty.

This means for Tr0ub4dor&3

It's estimatated that the word itself "Troubador" comes up in dictionaries which contain about $2^{16}$ words
It adds one bit for each of o,a,o of the word to encode whether the letter was replaced or not
It adds one bit to decide whether the word was capitalized or not
It adds one bit for the ordering of the trailing numeral and special character
It adds 3 bits for the unknown numeral, approximating $10$ with $2^3$ instead of $2^4$ which is more accurate
It adds 4 bits for the unknown punctuation, ie which of the approximately 16 standard ones it is

This sums up to $16+3+1+1+3+4=28$

For correct horse battery staple the reasoning is that each of the four words is drawn from a dictionary of size $2^{11}$ which means $4\times 11=44$ bits of entropy.

In both cases it can be assumed that the attacker knows the possible choices influencing the entropy estimation and that it's actually a uniformly random decision which word / pick is done.

If you want an even more thorough explanation of this comic, I can only recommend you read the bear's answer on this over on InfoSec.SE.


If I can crack the AES, how do I crack the wifi

If you "crack the AES", a very hypothetical assumption, then you could simply parse the WiFi packets and decrypt the messages that are being send.

Cracking AES is however considered impossible. AES-256 is even considered secure against attacks that involve (somewhat less hypothetical but still unavailable) quantum computers.

Note that even RC4, which was one of the reasons that WEP was cracked, is considered pretty secure when used correctly. Generally you are better off attacking the protocol or protocol implementations.

If you really want to attack AES itself then side channel attacks are probably your best option.


Authenticated encryption with Signatures

The   nonce || counter   version of CTR mode

satisfies the first two of the following conditions.

If

the symmetric encryption scheme is such that different ciphertexts

with the same nonce will decrypt to different plaintexts
and
the symmetric encryption scheme is secure against a single chosen ciphertext

whose nonce was not used for any of the challenge ciphertexts
and
the signature scheme is strongly unforgeable
and
the lengths of encodings of [message,signature] pairs don't reveal

any more about the messages than the lengths of the messages

then sign-then-encrypt will work for a single pair of users, but won't work with

signature verification keys from parties that aren't supposed to know the plaintexts.

I suspect that should generalize to arbitrary stream ciphers.


Simply hashing the account ID will not prevent people from associating the account because they can just hash the ID themselves assuming they know the ID and have access to the table.

If the data is so sensitive, you need to encrypt the entire table regardless of how you hide the ID. As I don't know your intentions, it's possible to associate an account entirely on the sensitive data.

If encryption of the table still doesn't suit you, and you are just toying with the idea of trying to disassociate an ID with the table entry, you can try a HMAC (Hash-Based Message Authentication Code) which can take an ID with some secret key to make a difficult to reverse hash. Good Luck!


Encrypt a file in a way that decryption requires every recipient's cooperation

There are various ways to do this, but one of the most flexible ways is to use a secret sharing scheme.  These are mathematical methods that allow a secret value (such as a symmetric encryption key, or even an entire file) to be split into multiple "shares", such that a certain number of shares (which does not necessarily need to be all of them) is required to reconstruct it.

For example, a simple $n$-out-of-$n$ secret sharing scheme like you describe can be obtained by taking $n-1$ random bitstrings (from a cryptographically secure true RNG) of the same length as the secret, and constructing the $n$-th share by bitwise XORing together all $n-1$ other shares and the secret.  It's not hard to prove that this last share is then also indistinguishable from random, and in fact that knowing no set of $n-1$ or fewer shares yield any information about the secret (other than its length, that is).  But if you have all $n$ shares, you can just XOR them together to get the original secret value back.

Once you've split the secret into $n$ shares, you can of course then e.g. encrypt each share with a different person's key.  Or you could just directly send each share to the person it belongs to for safekeeping, if that's more practical.

The real power of secret sharing schemes, however, is that you don't necessarily have to require all shareholders to cooperate in order to reconstruct the secret.  Specifically, there exist efficient threshold secret sharing schemes, such as Shamir's scheme, which work basically just like the simple XOR scheme described above, but allow the secret to be reconstructed from any subset of $k \le n$ shares, where $k$ is an arbitrary threshold set when the shares are created.

The mathematics involved are slightly more complicated than in the basic XOR scheme above, but they provide essentially the same guarantee: any $k$ shares uniquely determine the secret, whereas $k-1$ shares do not reveal any information about it whatsoever (not even if the attacker has infinite computing power!).

For example, to implement a general "two-person rule" for accessing some sensitive data (which could e.g. be a key to something else), you could use Shamir's secret sharing with a threshold of $k = 2$ to split the data into $n$ shares, and distribute these among all authorized persons.  That way, any two authorized persons could combine their shares to reconstruct the data.  But as far as a single person acting alone is concerned, their share is just a random number that reveals absolutely nothing about the data unless combined with another share.

There are also hierarchical secret sharing schemes that allow more complex access structures, such that one could require e.g. "any two people in group $A$ and any three other people in group $B$" to access the secret.  I could go into more detail, but we actually have an entire secret-sharing tag with plenty of good questions and answers that you might want to take a look at.


Why should I use Authenticated Encryption instead of just encryption?

The crucial difference between plain encryption and authenticated encryption (AE) is that AE additionally provides authenticity, while plain encryption provides only confidentiality. Let's investigate in detail these two notions.
In the further text, we assume $K$ to be a secret key, which is known to authorized parties, but unknown to attackers.
Goals
Confidentiality (privacy) means that an attacker can not get any information about the plaintext $P$ from the ciphertext $E_K(P)$ except, possibly, for the length. In other words, the ciphertext looks like a random string for those who does not know $K$, even if they have some control over the plaintext. All the folklore encryption methods, from one-time pad to Enigma, provide confidentiality (under some assumptions) and only it.
Data authenticity (integrity) means that an authorized party (receiver), who possesses $K$, can check if the received data $D$ is genuine, i.e. it has been constructed only by a sender who knows $K$. The data can be cleartext or ciphertext, and there is a subtle difference what is authentic in each case: if the ciphertext is authenticated, then we know that the key owner authorized the ciphertext, but not necessarily plaintext. A traditional way to achieve authenticity is to use Message Authentication Code (MAC):
$$
H_K(D) = T,
$$
where $T$ is called tag.
In the world of public-key cryptography, the same goal is achieved with digital signatures.
What you need
A user is usually able to decide which of these properties he is looking for. For instance, if he knows that an attacker can not modify data, he may not need to authenticate it. However, if he needs both, there are secure as well as insecure ways to combine the schemes of two types. For example, a naive approach to use the same key $K$ in both schemes is dangerously insecure for most instantiations. Hence a combined scheme is recommended.
Authenticated encryption
Authenticated encryption (AE) provides confidentiality and data authenticity simultaneously. An AE scheme is usually more complicated than confidentiality-only or authenticity-only schemes. However, it is easier to use, because it usually needs only a single key, and is more robust, because there is less freedom for the user to do something wrong (see also a more elaborative answer).
As a separate feature, an authenticated encryption scheme may authenticate, but not encrypt, a part of its input, which is called associated data. For example, we may wish to encrypt the contents of an Internet packet, but we have to leave its header unencrypted but still bound to the internal data.
Security
We have not specified yet what we mean by a secure scheme. Apparently, there are several security notions, and the user has to choose among them according to the capabilities he expects from an adversary.
For confidentiality-only modes of operation the most popular security notion deals with chosen-plaintext attacks. Let $E$ be an encryption scheme. We assume that the adversary not only knows some plaintexts $P$, but is also able to choose some of them for the encryption (this is quite a practical situation). Hence, we allow the adversary to choose any plaintext for the encryption, and many times in a row. What we still require from a secure scheme is that it outputs randomly looking ciphertexts in each case:
$$
E_K(P_1),E_K(P_2),\ldots, E_K(P_n) \sim RandomString(|P_1|+|P_2|+\cdots+|P_n|)
$$
The adversary can not distinguish the whole set of ciphertexts he obtains from an output of true random bit generator of the same length, even if the adversary repeats his plaintexts. The latter requirement implies that the scheme must be non-deterministic, and indeed, the confidentiality-only modes that satisfy these requirements are either probabilistic or nonce-based.
I note that there are folklore security notions that relate the security of the scheme with the ability to recover the key $K$ itself. This was relevant when the key could be used elsewhere, but this is far less common now, and the security notion described above is prevalent.
The security of authenticity modes is defined in a different way. Let $H_K$ be such scheme with the secret key $K$. We require that if the adversary chooses any data $D$ that has not been authenticated yet, then his chances to guess tag $T$ such that
$$
H_K(D) = T
$$
are negligible. If he submits the pair $(D,T)$ to a verifier, he will get the answer $\perp$ (error).
Note that we have not talked about chosen-ciphertext attacks on confidentiality-only modes. These are attacks when the adversary is also able to send his own ciphertexts for decryption. While this setting also appears in practice (even though less often than chosen-plaintext attacks), the confidentiality-only schemes can not resist such attacks. To establish this sort of security, the user must turn again to the authenticated encryption.
Security of authenticated encryption schemes is defined in two parts. First, similarly to confidentiality-only modes, the adversary must be unable to distinguish the ciphertexts from random strings. Secondly, whatever fake (not created on $K$) ciphertext she sends for decryption, she is likely to get $\perp$ in response.
Therefore, the authenticated encryption modes provides you also security against chosen-ciphertext attacks if it is needed.
How it works
There are numerous integrated authenticated encryption schemes: CCM, GCM, OCB, EAX, etc, where mechanisms that establish confidentiality and authenticity are tightly coupled. The design of these schemes is far beyond the topic. However, there is a simple composed scheme, well-known as Encrypt-then-MAC, that works as follows. Let $K_1,K_2$ be secret keys, $P$ be the plaintext, $E$ be some encryption mode, and $H$ be some MAC. Then the scheme
$$
\Pi_{K_1,K_2}: M\rightarrow E_{K_1}(M) ||  H_{K_2}(E_{K_1}(M))
$$
is a secure authenticated encryption scheme if $E$ is a secure confidentiality mode and $H$ is a secure authenticity mode.
Additional features of authenticated encryption schemes
Besides providing both confidentiality and authenticity, authenticated encryption schemes may have a number of additional features. No scheme has them all, hence the best choice is determined by user's settings.

Security level. A scheme guarantees confidentiality and data authenticity only up to some bound on the amount of encrypted data or decryption requests. This bound is typically much lower than the key space, and for AES-based modes does not usually exceed $2^{64}$.

Parallelism If a lot of resources are available, one may desire to run the encryption, decryption, or verification in parallel. The modes that use  chaining (like the ones derived from the CBC encryption or the sponge construction) are difficult to parallelize.

Online encryption. We say that a scheme is online, if it allows to encrypt immediately when the data is available, without the knowledge of its length.

Use of patents. One of the most interesting AE schemes, the OCB mode, is patented, and is less frequently used and analyzed because of this property. It is often desirable that the scheme is patent-free.

Tag update. Most of the schemes, with a few exceptions like GCM, require to recompute almost entire ciphertext if a small portion of plaintext is modified. If the ciphertext can be updated quickly, it would allow much faster processing of large amounts of encrypted data, e.g., hard-drive encryption.

Use of nonces or random IVs. Nonces and random IVs lead to distinct security models, which are often incompatible (schemes might be secure with nonces, but not with random IVs of the same length, or vice versa). While the nonce uniqueness might be harder to ensure, the random IVs need a separate random-number generation mechanism and leads to the ciphertext expansion.

Variable key, nonce, or tag length. All the three parameters are usually restricted by the application that uses an AE scheme. In turn, AE schemes  have their own, sometimes incompatible restrictions. The more variability the scheme has, the more applications it suits.

Processing of associated data. All the modern schemes allow for the authentication of associated data, which is not encrypted. Some of them, however, can not preprocess AD before the plaintext is over, which might be a penalty on the performance.

Additional reading
The technical report by Rogaway is a comprehensive survey of confidentiality-only modes, MACs, and some authenticated-encryption modes. It also contains all formal details about security notions.


Differences between OWP and OWF and their IND-CPA security

A one-way permutation is just a one-way function in which the function is a permutation (id est, a bijective function). Every OWP is a OWF, the converse is not true.

IND-CPA security is a security notion specifically related to encryption schemes. OWF and OWP are not encryption schemes, hence they cannot be said "IND-CPA secure"; however, one can construct an IND-CPA symmetric encryption scheme from any OWF, or OWP. (for asymmetric encryption schemes, stronger primitives are needed).


MAC forgery using the DES's Complementary Property

Yes, you are on the right track.
Let the MAC is given as

$H_0 = IV$
$H_i=H_{i−1}\oplus E_{M[i]}(H_{i−1})$ and for every $i>0$, and
$tag = (IV,E_{k_1}(H_\ell))$

and the attacker has the tag $t$. The observation is that the message is used as a key in the encryption. If the attackers can use some property of the cipher like a fixed point or more then they can forge. Actually more than the existential forgery, if we omit the keeping the IV same, they can find another message that is exactly the same MAC output.
The simple case: one block message $m$ and its tag;
$$t = (IV, IV \oplus E_{m}(IV))$$ for a fixed IV, and this is hard. We need some weaknesses in the Encryption algorithm. As you noted the DES has complementation property
$$E_K(P)=C \iff E_{\overline{K}}(\overline{P})=\overline{C}$$ then the attacker can use this as;
Let $ C = E_m(IV)$ then with DES complement property $\overline{C} = E_\overline{m}(\overline{IV}) $ Then
$$ \overline{IV} \oplus E_{\overline{m}}(\overline{IV}) = \overline{IV} \oplus \overline{C} = IV \oplus C$$ therefore this is a forge with almost the same tag $t$ with just complemented IV $$t' = (\overline{IV},\overline{IV} \oplus E_{\overline{m}}(\overline{IV})).$$


What is the "artificial abort" technique?

The problem that arises in the security proof is that the adversary who may win the real game with some probability may however cause the simulation to nearly always abort (by issuing a private key query that requires the simulation to abort) and the probability of an abort may be different for different sets of private key queries.

So, the problem is that the reduction may not be able to use the adversary as the simulation may arbitrarily fail (the success probability of the reduction is conditioned on the adversary not causing an abort) and thus the proof does not go trough. The problem is not to "just use the output", the problem is that you would not be able to get the security proof done without any additional measures.

Now, if the upper and lower bound on the probability that the adversary causes an abort are closely related, the adversary can be used in the reduction as you know that the simulation will always abort with the same probability and then the proof goes through. Note that this introduces a loss in the tightness of the reduction.

Waters therefore cleverly introduced artificial aborts, which basically means that the reduction at the end of a successful simulation (one that did not abort) estimates the probability of abort for hypothetical simulations with the adversary for the same set of private key queries. The reduction then artificially aborts with some probability related to the probability computed before. This is quite counter intuitive as the reduction after a successful run aborts, but this allows to prove the closeness of lower and upper bound on the probability of abort and makes the reduction work and the proof go trough.

There is a paper from EUROCRYPT 2009 which shows how to eliminate the requirement of artificial aborts and thus complicated security proofs for the Waters scheme.


Is zero IV with AES-CBC safe if CPA is not possible and indistinguishability is not an issue?

Furthermore, is using AES-CBC this way any safer than using AES-ECB?

Yes, using CBC mode is (almost?) always safer than using ECB mode.

  Is using zero IVs with AES-CBC safe[...]?

No it is not safe, because if you re-use a key with that construction you will leak the common prefix between messages, at block granularity. That is if you have three messages encrypted with CBC with the same IV and key $m=A\parallel B\parallel C\parallel G$ and $m'=A\parallel B\parallel D\parallel G$ and $m''=A\parallel E\parallel F$, with $A,B,C,D,E,F,G$ being 16-byte blocks, you can tell that $m'',m'$ and $m$ share the first block in common and you can tell that $m'$ and $m$ share the first two blocks in common, of course you don't actually directly learn the value of these shared blocks.

Note that either changing the key or the IV for each message fixes the above problem.

  There are more modern modes (which are authenticated) which only leak equality of messages upon a (IV,Key) re-use: That's kinda what I'm
  looking for. Which modes are those?

These modes are called nonce-misuse resistant authenticated encryption modes (nmrAE). The two standard suggestions for this are AES-SIV and AES-GCM-SIV or AES-PMAC-SIV, both of which will offer standard authenticated encryption security if you use different (IV,Key) pairs with each message and will both offer (some) security if such a pair is re-used and of course they offer authentication as well and only leak equality of the underlying messages upon a re-use.


Are attributes of an access structure visible or guessable in a CP-ABE ciphertext?

In CP-ABE, the policy (i.e. which attributes are required to decrypt) is usually public. So Alice knows whether her A, B, C satisfy the policy or not. If not, Alice knows for example, D and E are required, but she does not have. She does not need to guess. She cannot decrypt the ciphertext however, because she does not have the private key corresponding to the missing attributes. The private keys are issued by a trusted party who will only issue to keys after verifying the requesting party does possess the attributes.


Encryption with "constant" initialization vector considered harmful

For block ciphers, it depends on which mode of operation you're using — nobody uses just a plain block cipher for anything, at least not unless all their messages are shorter than a single cipher block (typically 8 or 16 bytes).

ECB mode, which just amounts to chopping the message up into blocks and feeding each block through the cipher, does not use an IV.  As you correctly note, it's also insecure: it leaks information about duplicate blocks in the plaintext.
OFB and CTR modes turn the block cipher into a synchronous stream cipher.  Thus, they have the same security issues as other stream ciphers: if the same key+IV combination is used for two messages, an adversary that captures both can take their difference to eliminate the keystream, leaving only the difference of the two plaintexts (which is often enough to recover at least parts of both of them).  It gets even worse if they can capture more than two messages using the same key+IV.
The CBC and CFB modes are somewhat more resilient to simple IV reuse.  As with all other common operating modes, though, using the same key+IV to encrypt two messages sharing a common prefix (of one or more blocks) will reveal the presence and length of that prefix, since the ciphertexts will be identical up to the point where the first plaintext difference occurs.  CFB mode also leaks the difference of the first non-identical plaintext blocks in the two messages.


Limiting how many key pairs someone can generate without compromising their keys

Anybody can run any of the usual generators for asymmetric primitives as many times as they want. And they can do this without compromising the security of the private key. Generally the trust of a key pair by a user is however not in the private key, but in the public key or certificate around the public key.

Now you could embed a signed token in the certificate, but in that case you must make sure that the token cannot be reused. This could for instance be managed by a trusted third party, such as a Certificate Authority. You could for instance create a certificate extension and require a CA to validate that the token isn't reused. You then have another party to hold responsible if a duplicate token is ever found.

What you cannot do in this digital world is avoiding duplication. This can only be managed if you somehow manage to secure the processing of the data. For more information on that you'd have to look at digital rights management (DRM) rather than homomorphic encryption or zero-knowledge proofs - if you ask me.

And while I generally try and refrain from using buzz, this might be  a case where blockchain technology could actually be helpful in case you don't want to use a CA / centralized management.


Does ElGamal Encryption create a different key for each block sent?

If you have the setting of $G$ being a prime order $p$ group (written multiplicatively) generated by $g$ and your public-secret key pair is $(pk,sk)=(y=g^x,x)$, then encrypting a single message $m\in Z_p$ amounts to choosing $k\in_R Z_p$ and computing $(c_1,c_2)=(g^k,my^k)$.

If you have a message $m=(m_1,\ldots,m_l) \in Z_p^l$, then the ciphertext would be $((g^{k_1},m_1y^{k_1}),\ldots,(g^{k_l},m_ly^{k_l}))$ with the $k_i$'s being distinct (but the public key $y$ is the same, since it is intended for one receiver).

Observe, that when using the same $k$ for two messages, say $m_1$ and $m_2$, then you can infer non-trivial information about the messages from the ciphertexts $(g^k,m_1y^k)$ and $(g^k,m_2y^k)$, since computing $m_1y^k(m_2y^k)^{-1}$ gives you $m_1(m_2)^{-1}$. Consequently, choosing a fresh randomizer $k_i$ for every block is essential.

Nevertheless, if you have to encrypt multiple blocks in practice, you would use KEM/DEM style hybrid encryption for the sake of more efficiency.

A side note: if you encrypt a message $m\in Z_p$ under distinct public-keys $y_1,\ldots,y_n$, then you can re-use the randomness $k$. This means, that instead of choosing $k_1,\ldots,k_n \in_R Z_p$ and sending $((g^{k_1},my_1^{k_1}),\ldots,(g^{k_n},my_n^{k_n}))$, you can choose $k\in_R Z_p$ and send $(g^k,my_1^k,\ldots,my_n^k)$ which saves you computation and bandwidth. You may look here for a general treatment of this so called randomness re-use in multi-recipient encryption: journal paper or the previous paper versions paper1, paper2 for further details.


Meet-in-the-middle with checking complexity

Well, one assumption you appear to be making is that, with 2DES, there will be approximately $2^{56}$ possible key matches.  Actually, there are an expected $2^{48}$ possible key matches; here's why:

Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that is not the correct one).  If DES acts anything like what we expect, we'll arrive with an effectively random 64 bit value.  We will do a trial decryption if that value appears somewhere in the decrypt list; there are $2^{56}$ values on that list, and so that specific random 64 bit value will appear an expected $2^{-8}$ times; hence for each incorrect encryption key, we will need to perform an expected $2^{-8}$ verification tests.  There are $2^{56}$ (actually, $2^{56}-1$, however that difference is lost in the noise) incorrect keys, and hence we expect to need to perform $2^{56} \times 2^{-8} = 2^{48}$ tests on incorrect keys (plus the one test on the correct key).

This gets into the more fundamental question of "what do we actually mean when we give a complexity estimate?".  Well, it isn't as straight-forward as you might think; if we say that a specific attack uses $2^{100}$ foo operations, we do not mean that it uses precisely $2^{100}$ of those operations (and never requires $2^{100}+1$ of them), or that it doesn't require any bar operations; what we mean is that the time the attack takes is bounded by those $2^{100}$ foo operations; the time taken by any additional foo operations, or any needed bar operations doesn't significantly increase the attack time, where significantly means "doesn't increase the attack time by more than a factor drastically larger than 1".

Remember, the goal of these estimates is not because we're actually interested in running the attacks; instead, what they're there for is to allow us to be confident that the attack takes much longer than any possible adversary has the budget for.  A factor of 2 might sound significant; however we typically can't estimate the adversary's budget that accurately (especially if we're talking about adversaries in the future); what we attempt to do is to design our systems so that an attack is (say) $2^{40}$ times what an adversary might have; compared to $2^{40}$, a single factor 2 is actually not significant.

Stepping back to your example, what this means that if we have an attack which acts in two phases:

Generate a potential set of solutions (taking time $A$)
Validate those potential solutions (taking total time $B$)

then we'll say that attack takes time about $max(A, B)$; that's because the time taken is dominated by whichever takes the longer (and if they're both the same, the fact that the attack actually takes twice as long isn't a significant factor).

In the 2DES attack (which follows this model), $A$ is much larger, and so we basically ignore $B$ (not because we don't think that it's important, but it doesn't slow down the attack to a degree that we care about).


Using similar passwords and salts for PBKDF2

If there would be risk from related inputs one would know that because then HMAC would be target to chosen plaintext attacks and hence PBKDF2 would have been fully obsolete. So there's no weakness in using related inputs.
As each cell basically has a different password there's no faster way than brute-force to find out the values. However, if you know how the mapping takes place and you broke r1 and r2, one can fastly calculate the other entries (as fast as the defender did, as there's no entropy left)
I'd suggest you to increase the iteration count to 1000000 as this is far more secure and still takes less than a second on most pcs.
16 bytes for the r-values suffices, if you got "high entropy" in them (80 bits + -> >6 bits per byte)
As pointed out correctly in the comments, PBKDF2 is not a viable choice for password hashing. Rather use scrypt or the winner of the PHC (announced within next two months)


What is the malicious potential of a key-substitution-attack?

As is, the attack seems rather pointless. But one malicious potential is that because $\bar y$ allows to successfully verify a genuine message $(m,s)$, the verifier might grow trust in it and use $\bar y$ instead of $y$ in order to verify other messages. If we assume this, practical issues could arise:

That the attacker can somewhat find $(\bar m,\bar s)$ (with $\bar m\ne m$ and/or $\bar s\ne s$ (depending on definition of security of a signature system) so that $v(\bar m,\bar s,\bar y)=\text{ok}$ ; $(\bar m,\bar s)$ will be accepted by a the verifier and in effect is a practical forgery.
That the legitimate verifier handed some genuine $(m',s')$ pair (such that $v(m',s',y)=\text{ok}$, and $m'\ne m$) finds that $v(m',s',\bar y)\ne\text{ok}$, and rejects the valid message; this in effect is a denial of service.

In many signature systems where the question's attack is possible, 1 or/and 2 is possible.

Elias suggests that if making a $\bar y$ as in the question is possible, then the signature scheme looses non-repudiation. That's an interesting point of view, but mine is that the definition of non-repudiation is a convention between parties, and that it would be a slippery slope (and an unusual one) to allow exhibition of $\bar y\ne y$ such that $v(m,s,\bar y)=\text{ok}$ to be a valid reason to stop accounting the legitimate holder of the private key matching the public key $y$ as responsible for having signed $m$ whenever $(m,s)$ becomes publicly available and $v(m,s,y)=\text{ok}$.

Two technical reasons are that, without breaking the established definition of security of a signature scheme, it could be that $\bar y$ was produced

from $y$ and/or $s$, by anyone;
or additionally with knowledge of the private key for $y$, e.g. by the legitimate key holder wanting to repudiate his/her approval of $m$.

Thus is we allowed what Elias proposes, we'd need to use signature schemes with a stronger and more complex definition of security than we do, for no benefit that I can discern beyond preventing what is explained in the first part of the answer.


How does a perfect hash function have collision-resistant in this case?

Well, when we select a perfect hash function, we take as inputs a set of messages $M_1, M_2, M_3, ..., M_n$, and use them to select a hash function for which $H(M_i) \ne H(M_j)$ (if $i \ne j$)

Now, according to the pigeon hole principle, the output of $H$ must be at least $\log_2 n$ bits long; as $n$ is typically not that huge, that is not a practical problem.

Now, there may be messages $M$ not in the original set for which $H(M) = H(M_i)$ for some $i$; that's ok, as the collision freeness of the perfect hashing function is defined only for the original set of messages, not any additional messages.

And, as cryptostatis has mentioned, we don't have much use for perfect hashing functions in cryptography.  We do use collision resistant hash functions; however by that, we mean that while collisions $H(M) = H(M')$ do exist, it is difficult to find them.


Here is how you do a literature search, to find relevant research papers in the literature:

You identify some search terms related to your topic, and search for them on Google Scholar and other places (e.g., Crypto.SE, via web search, on Citeseer).  (For cryptographic work, also try searching Google with site:eprint.iacr.org and your search terms, to turn up papers on the IACR's ePrint server.)

Go through each paper that you find in this way and very quickly skim the title and abstract of each paper.  Keep all the papers that look relevant or related to your topic of interest, based upon your skim of the title and abstract.
Take the papers you identified in step one.  If there are any research papers that you know are related, add them to the list.  This is your starting set of relevant papers.
For each relevant paper, you use that paper to help you find other papers that may be relevant:

You read the paper's related work section, to see how it describes related work.  Anything that sounds relevant to your interests, you take that citation and add it to your list of relevant papers.
You search for that paper on Google Scholar and on CiteSeer.  You use them to generate the list of all other (newer) papers that cite that paper, and you look through those results.  Keep all the ones that look relevant, and add them to your list of relevant papers.

As you discover new relevant papers, apply the same process to each of them recursively.
Keep doing this until you don't find anything new (i.e., until the set of papers is closed).

The result of this should be a (possibly large) set of relevant papers.  Now go read all of those papers, to understand what they are doing.

Once you have some research papers that look like they might be relevant, here is how you read go about reading them:

Start by reading the abstract and introduction; that should give you a good overview of what the paper's contributions are.  Don't try to read the rest of the paper.  This should take maybe 15-30 minutes.
If the paper still sounds relevant, you read the paper at least once straight through (skip or skim all proofs or other technical parts that take hard thinking to follow); your goal is to understand the main ideas in the paper, but you don't need to grok every little detail.  That should give you an idea of what the paper is doing.  Normally, this should take an hour or two.
If it still sounds useful, you can then do a careful read-through where you try to understand every detail in the paper, and think critically about why they're doing what they're doing and how it's helpful to you.


Can anyone explain to me the difference between the OTP (one-time pad) and Vernam Cipher?

Confusion arises because many people use the terms Vernam cipher and one-time pad interchangeably--but they are not the same thing.
When young Gilbert Vernam, an AT&T research engineer, got his patent in 1919 (for a "Secret Signaling System"), Vernam cipher meant a fast encryption method using an additive stream cipher that was machine-based and used Baudet with modulo 2 addition.
XOR was born.
According to this unclassified NSA historical account (p.2):

Gilbert S.Vernam, working on new developments in telegraphy, came up
with a novel (and relatively simple) scheme for encrypting TTY. He
mixed  two  Baudot-coded  punched  paper  tapes (hole  being  a  “+,”
no  hole  a  “-”): one  tape  contained  the plaintext message and the
other the “key.” These tapes were added  “modulo  2”  (“exclusive
or”)  in  a  mechanical  tape reader producing an output cipher signal.

This was a huge improvement over the tedious codebooks and the German ADFGVX cipher, which was susceptible to cryptanalysis. Interestingly, in 1918, the U.S. Army was uninterested in Vernam's work.
But there were several problems no one understood at the time:
1.  The key had not been generated in a truly random manner
2.  The key was on a looped tape
3.  The key was reused

Not a one-time pad.
Enter Joseph Oswald Mauborgne--artist, cryptographer, and U.S. Army General-- the first person to send a radio signal from an aircraft to the ground.  He had the realization that if the key had been generated in a random manner, then the ciphertext from Vernam's machine would be unbreakable.
Frank Miller, an American cryptographer, had already invented the one-time pad in 1882, but the glory seems to have landed on Gilbert Vernam instead of the two people who had actually figured it out.  This reminds one of how Blaise de Vigenère had a cipher named after him that Giovan Battista Bellaso had invented much earlier.
Vernam cipher and the OTP are not the same thing.  Moreover, when we say OTP that can refer to a physical object, usually one that is easy to hide and destroy.
These days, we mostly think of the OTP as a model for encryption systems.


As Geoffroy Couteau already pointed out, this is not about the output of the OR-function revealing information about the other player's input (as indeed it also does in the trusted third party setting).

The setting is that of 2 players Alice and Bob having access to a bidirectional secure (and noiseless) channel. For simplicity, consider the asynchronous setting, so where we players alternate sending messages to each other. (The argument extends to the synchronous setting.)

Since both players have access to all information on the channel, we can essentially view their communication as one after the other appending information to a publicly visible transcript (e.g. picture both players in a room, one after the other writing a message on a blackboard).

Suppose we could compute the OR-function privately, and consider an execution of this protocol where both player's input bits are 0. At some point during this protocol, one player, say Alice, is first to learn the computed output of the function. Consider the transcript $T$ up to this point. A few observations:

Since Alice's input bit is 0, the output of the function will be equal to Bob's input bit. Thus, Alice is able to learn Bob's input bit from $T$ and her own input and random tape.
$T$ should not give Bob any information about Alice's input bit, since Alice was the first to learn the other player's input bit.
Therefore, $T$ could also have occurred (from Bob's perspective) if Alice's input bit had been 1, otherwise he is able to distinguish based on the transcript and learn Alice's input bit.
If Alice's input bit had been 1, she should not have learned Bob's input bit from $T$.

Points 1 and 4 are clearly inconsistent given observation 3, hence such a protocol cannot exist.


Existing dictionaries of popular words to help solve a random substitution cipher?

One nice way to generate a word list is distilling it from a large amount of texts.

There are a few interesting effects with this creation method:

The word frequency depends a lot on the chosen texts. For example when feeding it wikipedia the language is rather formal, and common every-day words are pretty rare. It might be interesting to compare Simple Wikipedia with the normal wikipedia
For some texts you also get common misspelling of words. That's nice for some uses, but bad if you want to use the list for spell checking. Should be fine in your case

I found a nice wordlist created from the english wikipedia which lists the words ordered by frequency. So you can truncate it if you want fewer words. Unfortunately it doesn't contain the frequency of each word, but since the source is available, adding this feature shouldn't be hard.


Advantages of encrypting a symmetric key with a public key vs using a fixed symmetric key

What is the real advantage of option 2 (asymmetric encryption of firmware)?

As correctly pointed by the question, not much. All I can think of:

It allows to change the symmetric key at each firmware release (actually, the firmware will be encrypted with a random symmetric key, sent asymmetrically encrypted in a header). This advantage is mitigated by the fact that the asymmetric private decryption key can hardly be changed at each release, and must be secret.
The developer/party encrypting the code needs no secret for that. This advantage is mitigated by the fact that the developer/party signing the code needs a private key, which must be secret.


Distortion of the spherical gaussian error through the canonical embedding in Ring - LWE

The section you quote is from the introduction. The paper goes into more technical detail later. For example, equation 3.1 states (roughly) the same equation, and then states that:
$$B = U\Sigma$$
Where $\Sigma$ is the matrix of the canonical embedding, expressed relative to the basis $\{\alpha_1,\dots, \alpha_n\}$, and $U$ is the matrix (defined on page 5):
$$
U = \begin{pmatrix}
I_{s\times s} & 0 & 0 \\
0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{i}{\sqrt 2}I_{t\times t}\\
0 & \frac{1}{\sqrt 2}I_{t\times t} & \frac{-i}{\sqrt 2}I_{t\times t}
\end{pmatrix}
$$
$U$ is unitary, and known to be an isomorphism $(H, \langle\cdot, \cdot\rangle_H)\cong (\mathbb{R}^n, \langle\cdot, \cdot\rangle)$, where $\langle x,y\cdot\rangle_H = \sum_i x_i\overline{y_i}$ is the Hermitian inner product, and $H$ is a certain conjugation-invariant subspace of $\mathbb{C}^n$ that contains the image of the canonical embedding.
This is all discussed on page 5.


Is there a metric (term) for work required to decrypt a public key?

There are multiple metrics for work or effort needed:

Amount of operations it takes (one operations is, for instance, one invocation of hash function or number of modular multiplication operations)
Amount of money it takes
Amount of memory it takes
Amount of time it takes
Strength in bits

Amount of operations

Usually, if amount of operations is large enough so that it cannot be done with all the energy in the solar system even if single operation consumed just one electron, it looks safe enough.

Brute forcing AES-256 bit key is too expensive in amount of operations

Amount of money

If it costs too much to build device for breaking encryption, people assume it cannot be done, or that it is prohibitingly expensive.

Excellent paper of PBKDF algorithms, including cost of breaking a key in a year.

Amount of memory

Sometimes it would be feasible for large organizations to break algorithm according to how long it takes to break it (in number of operations), but it may be that breaking the algorithm takes so much temporary space that it cannot be done, because that temporary space is no where to be found.

Question on duration for attacking Two-Key Triple-DES using all RAM ever built.

Amount of time

Various parties like Prof Arjen Lenstra make estimates how long various kinds of keys take to break, based on the best attacks currently known. These are equations based on algorithm and key length.

These estimates can be found on www.keylength.com, along side other estimates.

Strength in bits

Some parties like NIST estimate algorithm strength in bits. This is: amount of bits symmetric encryption algorithm of equivalent strength against attempt to break would have.

These estimates are based on previous, especially number of operations required.

NIST SP 800-57 Part1: Recommendation for Key Management – Part 1: General contains necessary information to convert various algorithms to bits of strength to make it easier to compare algorithms in apples-to-apples manner.

How strong algorithms we should use then?

Algorithms with strength around 56-64 bits have been typically broken. (Like RSA 768. => Don't use.)
Algorithms with strength around 80 bits typically have not been broken, but are "on edge" and therefore their use is no more recommended. (Like RSA 1024. => Avoid.).
Algorithms with strength 112 bits (like RSA 2048) or more are considered to be safe (according to NIST), until beyond 2030, as long as they are used properly (single key has life time of about 1-2 years etc.)

More exact estimate on cracking RSA can be found here: How to estimate the time needed to crack RSA encryption?. The amount of time to crack other public key crypto will be different. However, if you use key sizes which are currently recommended, as far as public knowledge on cryptography goes, work required is infeasible.


Key Derivation Functions offering better than 2^hlen security?

Note that Krawczyk's paper builds the extract-and-expand paradigm from a notion that he labels computational randomness extractor.  This is a modification of the concept of randomness extractor such that the output of the computational extractor need only be computationally near to a uniform random distribution, while a plain old randomness extractor needs to be unconditionally near to such a distribution.  So an extract-and-expand KDF is a combination of:

A computational extractor, which takes weakly random inputs and "condenses" it into a computationally-strong master key;
A pseudorandom function keyed off the computational extractor's output, which is used to produce expanded pseudorandom outputs.

So a KDF that can extract the maximum entropy that can be extracted from the source key material would replace the composition of these two submodules with a randomness extractor that's capable of producing output with the desired entropy from the source key material.  This is akin to the techniques used in true random number generators to produce full-entropy, uniform outputs from biased or correlated noise sources.

Randomness extraction is a big topic; searching the web for "randomness extractor" produces some technical introductory material.


Is the "decapsulate" function from lattice based cryptography homomorphic?

Kyber claims to be CCA secure. CCA schemes cannot be homomorphic (thinking through this may be a useful exercise).

It may be useful to try to work through this particular example with pen and paper by looking at algorithm 5 in the Kyber paper. Note that what is returned is some hash, which you should not expect to have homomorphic properties.


How is it possible to define differential privacy on two databases that differ more than a single entry?

One of the advantages of differential privacy is composition. That is, if $D_1$ and $D_k$ differ on $k$ entries, then $k\cdot\epsilon$ differential privacy is achieved. This is easily shown by writing a series of equations. Specifically, let $D_1$ and $D_k$ differ on $k$ entries, and let $D_i$ be a database that differs from $D_{i-1}$ on one entry (for $i=2,...,k$). Then,
$$
\frac{\Pr[A(D_1)\in S]}{\Pr[A(D_k)\in S]} = \frac{\Pr[A(D_1)\in S]}{\Pr[A(D_2)\in S]} \cdot \frac{\Pr[A(D_2)\in S]}{\Pr[A(D_3)\in S]}\cdots \frac{\Pr[A(D_{k-1})\in S]}{\Pr[A(D_k)\in S]} \leq (e^\epsilon)^k = e^{k\cdot\epsilon}
$$
where each
$$
\frac{\Pr[A(D_{i-1})\in S]}{\Pr[A(D_i)\in S]} \leq e^\epsilon
$$
by the assumption of differential privacy for databases that differ on a single entry.


Convert numeric value of RSA key to a .key file

In general an RSA private key consists of at least d and n, but this century it is usually stored with added CRT (Chinese Remainder Theorem) parameters as described in Wikipedia and specified more exactly in PKCS1 (Public Key Cryptography Standard 1) which was actually issued by the company RSA (later acquired by EMC and then Dell) but is more conveniently and stably available as several Internet RFCs, currently 8017 at 3.2.

(Native) phpseclib supports several formats for key files.

The first two are de-facto defined by OpenSSL, a widely used open source implementation since about 1995 (originally as SSLeay) of SSL/TLS protocols including the cryptography for those protocols including RSA.

A plain (unencrypted) PEM file simply consists of the PKCS1 RSAPrivateKey structure encoded in ASN.1 DER or BER converted to base64 and wrapped to lines shorter than 80 chars, with delimiter lines -----BEGIN RSA PRIVATE KEY----- and -----END RSA PRIVATE KEY---- added.

An encrypted PEM file consists of the same PKCS1 ASN.1 encoding first encrypted with Password-Based Encryption, then PEMized similarly: base64 plus BEGIN/END lines but adding some RFC822-style headers defining the encryption. This is documented in the man page for the function PEM_write_RSAPrivateKey also on the web for the current release.

The PuTTY format is also Password-Based Encrypted, with encodings of the public and private parts separated in a format defined by PuTTY, an implementation of SSH protocol which like SSL/TLS includes RSA. AFAICT it is not documented, but PuTTY is open source and the source file sshpubk.c effectively defines this format.

The XMLSig/XMLenc format is defined by public standards and using (unsurprisingly) XML. This might be best for your purpose, since it simply contains the various numbers as base64 of canonical big-endian, tagged using XML.

The OpenSSL binding isn't clearly specified but presumably supports the PEM formats supported by OpenSSL; in addition to the two PKCS1 formats described above, this includes plain and encrypted formats defined by PKCS8 which is basically an ASN.1 wrapper around PKCS1, optionally with Password-Based Encryption, similarly available as RFC 5208 optionally combined with PKCS5 and sometimes PKCS12.


What does "Worst-case hardness" mean in lattice-based cryptography?

One line: worst means any and average means random.

Lattice-based cryptosystem

Let me restate.
Fix security parameter $n$.
What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case.

Since we can solve any instance, we can solve the hardest one of dimension $n$.

ElGamal encryption - average-case

We have a reduction that converts a random instance of the CDH/DDH problem into a random problem of one-wayness/indistinguishability game. This means that the security is based on the average-case hardness of the problem.

ElGamal encryption - worst-case

Correctly speaking, the security of the El Gamal encryption scheme can be based on the worst-case hardness of the DL-like problems over the group instead of the security parameter.

Fix a prime-order group. We can convert any instance of the DL/CDH/DDH problem on the group to a random instance of the problem on the same group.
( This property is as known as the random self reducibility.)
Combining it with the previous reduction, we can say the security is based on the worst-case hardness of the problem over the fixed group.


Is the curve25519 algorithm a special(implementation) one of ECDH?

Is the curve25519 algorithm a special (implementation) one of ECDH?

X25519 is a particular Diffie–Hellman function built out of the elliptic curve Curve25519, originally described in the Curve25519 paper.*  Specifically, it is a function from two 32-byte inputs to one 32-byte output with the Diffie–Hellman properties that make it useful for key agreement: $f(a, f(b, u)) = f(b, f(a, u))$.

  And why it need no common params for both sides to config?

Here's one possible way to do design a protocol that does key agreement over the internet.

Protocol designer chooses a secure DH function like X25519* that has been thoroughly vetted by the public cryptography community.
Client and server do DH handshake.

Note an adversary may be modifying the DH handshake over the wire.

Client and server authenticate DH handshake with long-term identity keys.

Here's another possible way to design a protocol that does key agreement over the internet.

Protocol designer defers question of what secure DH function to use and makes it configurable.
Client and server software implementors provide umpteen different configuration knobs with inscrutable names like ecdhk283 and accept arbitrary group parameters (like $g$ and $p$ for finite-field DH over $\mathbb Z/p\mathbb Z$, or $a$, $p$, and $p$ for elliptic-curve DH in $y^2 = x^3 + a x + b$ over $\mathbb F_p$).
Client and server operators bumble around in the dark trying to decide which acronym soup to configure their ECDH cipher suites with.
Client and server talk over the network in an attempt to negotiate a choice of cipher suite and curve.

Note an adversary may be modifying the cipher suite and curve negotiation over the wire, and may suggest curves (or finite-field DH groups) that don't even make any sense.

Client and server act on the choice of curve and do a DH handshake.

Note an adversary may be modifying the DH handshake over the wire.

Client and server authenticate DH handshake with long-term identity keys.

Which way do you think provides adversaries with more room to screw you up?

If it's not obvious, check out FREAK and logjam!

The second way was used for a long time by TLS and SSH; now modern consensus, after decades of experience, is that it is too dangerous, and even for finite-field DH, TLS 1.3 doesn't allow dynamic group negotiation.  It is a lot of work to validate curves, and much easier to implement them securely and efficiently if you don't allow arbitrary fields and parameters—and it is essentially impossible to dynamically validate finite-field DH groups securely.

* A note on terminology: These days, Curve25519 means the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$ over the field $\mathbb F_p$ where $p = 2^{255} - 19$, while X25519 means a specific Diffie–Hellman function based on scalar multiplication using only $x$ coordinates on Curve25519, roughly $\operatorname{X25519}(n, u) = x([n] x^{-1}(u))$—i.e., if $u$ is the $x$ coordinate of a point $P$ on Curve25519, then $\operatorname{X25519}(n, u)$ is the $x$ coordinate of the scalar multiple $[n]P$ on Curve25519.  The Curve25519 paper was written before this terminology was settled, and uses the name ‘Curve25519’ to refer to the DH function.


A block cipher is (or tries to be) a pseudorandom permutation on a given space. Let $\mathcal{M}$ be the set of $n$-bit blocks for a given $n$. There are $2^n$ possible block values, and a permutation on $\mathcal{M}$ sends each block value to another value. There are $2^n!$ such permutations. A block cipher is a mapping from key values (in a given key space $\mathcal{K}$) to permutations on $\mathcal{M}$.

For instance, AES-256 is a block cipher which operates on 128-bit blocks and uses a 256-bit key. Each possible key value ($2^{256}$ possibilities) selects a permutation among the $2^{128}!$ of the space of 128-bit blocks (which has size $2^{128}$).

For the block cipher $\phi$ to have any practical value, it shall be easily computed: given a key $k$ and an input block $x$, applying the permutation $\phi_k$ selected by $k$ on $x$ takes a small amount of computing power. Usually, the inverse permutation is also easily computed: given $k$ and $y$, find $x$ such that $\phi_k(x) = y$.

The main security assumption on block ciphers is indistinguishability: for whoever does not know $k$, the permutation $\phi_k$ should behave as if it had been selected at random and uniformly among the $2^n!$ possible permutations of $\mathcal{M}$. This can be illustrated with the following experiment: suppose that I give two black boxes which compute, respectively, $\phi_k$ and on inputs $x$ of your choosing, and yields the corresponding output. I do not tell you the value of $k$. At any time, when you have sent $q$ requests ($q$ block values $x$ to encrypt), your goal is to predict the output of the box on yet another input $x$ that is distinct from your previous $q$ inputs. Since $\phi_k$ is a permutation, you know that the output will be different from the $q$ previous outputs, so there are $2^n-q$ possibilities. The block cipher is "secure" if you cannot predict the output correctly with probability substantially better than $1/(2^n-q)$.

(This "black box" model is a bit simplified; in fact, I should give you two black boxes computing $\phi_k$ and $\phi_k^{-1}$ respectively, and each of your $q$ request is for one of the boxes, at your choice.)

The "black box" model explains why a simple XOR is a very poor block cipher. If you define $\phi$ such that keys are also sequences of $n$-bits, and $\phi_k(x) = k \oplus x$, then a single request to the encryption black box allows recomputing $k$ (with $k = x \oplus \phi_k(x)$) and thus predict output for all other requests with 100% accuracy.

Terminology is the following:

Known Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ but does not get to choose $x$ or $\phi_k(x)$.
Chosen Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ where he can choose the $x$ values at will.
Adaptive Chosen Plaintext Attack: a CPA attack where the attacker is allowed to think a lot between each two requests; meaning that when he selects the next request $x$ to send to the black box, then he can do so after due inspection of the previously obtained outputs.
Chosen Ciphertext Attack: attacker obtains $q$ pairs $(\phi_k^{-1}(y),y)$ where he can choose the $y$ values at will.
Adaptive Chosen Ciphertext Attack: a CCA attack where the attacker can think between any two successive requests.

The "gold standard" is called IND-CCA2 which means "indistinguishable from a random permutation against adaptive chosen ciphertext attacks".

(The description above is slightly simplified; true formal exposition would use Turing machines and a game between a challenger and a prover; but it should give you the intuition.)

There are limits to the indistinguishability. Indeed, if you allow $q$ to raise up to $2^n-1$ then the notion ceases to be interesting; if the attacker can send requests for all possible block values except one, then he can predict the missing one with probability 1: it is the one output that he did not get yet. Also, indistinguishability cannot hold beyond exhaustive search on the key space: if the attacker can try all possible key values, then he can look for a match with the outputs he got. Once he gets the key, he can predict with probability 1.

It is customary to study algorithms where keys are sequences of $r$ bits (e.g. $r = 256$ for AES-256). The "exhaustive search" attack has average cost $2^{r-1}$ (the attacker needs, on average, to try half the keys before hitting the right one). So, the security of any block cipher tends to break down when the attacker is "allowed" too many requests and/or too much computing power.

In practice, for a block cipher with $n$-bit blocks and $r$-bit keys, we consider an attack to be "academically successful" if it can predict the black box output with the following conditions:

Attacker can send $q$ requests to the encryption or decryption box with $q \leq 2^{n-1}$ (attacker can obtain "half of the code book").
Attacker can spend enough CPU to compute $2^{r-1}$ evaluations of the function.
Attacker also has access to $2^{r-1}$ bits of very fast RAM.
Attacker's probability to predict the next output is at least $3/4$.

With $2^{r-1}$ evaluations of the function, attacker's success with the simple exhaustive search and $2^{n-1}$ requests will be $1/2+2^{-(n-1)}$ (50% chance of having found the key through the search, and, if not, the knowledge that the next output will be in the code book half that the attacker did not get with his $q$ initial requests). Hence the $3/4$ criterion: attacker must be able to do better than this generic attack.

For instance, if you consider 3DES: block size is $n = 64$, and key size is $r = 168$ (the standard says "192 bits" but the algorithm simply ignores 24 of these bits, so for the cryptographer the key size is 168 bits). There is a known "meet-in-the-middle" attack which requires $2^{62}$ bits of storage (for $2^{56}$ words of 64 bits), computational effort equivalent to about $(2/3)·2^{112}$ evaluations of 3DES, and only 2 known plaintexts. This attack cannot be implemented with existing technology (the storage requirement would be quite expensive, since we are talking about half a millions of terabytes of fast RAM; and the CPU requirements is simply completely out of reach because it would requires way more energy than what Mankind produces as a whole). Yet it counts as a break. In that sense, 3DES is "academically broken".

Modes of operation turn a block cipher into something which can encrypt and decrypt messages of almost arbitrary length, not just single block values. Each mode of operation has its own requirements, in particular with any Initialization Vector. For instance, with CBC, in a "black box" model similar to what is described above, the encryption system must generate IV values randomly, uniformly, with values which are not predictable by the attacker (the BEAST attack on SSL/TLS builds on IV predictability, in the sense that the attacker can know the IV before choosing his plaintext for the next request).

As a generic rule, most modes of operation run into trouble when the amount of encrypted data exceeds about $2^{n/2}$ blocks. This is the threshold at which a pseudorandom permutation begins to behave differently from a pseudorandom function (a permutation is injective: it won't give you the same output with two distinct inputs; whereas a random function, on average, is not injective). This is why AES was defined with 128-bit blocks, as opposed to 3DES 64-bit blocks: to give us enough room in practical situations.


As NEWHOPE builds its security proof based upon previous works, and that Google has been experimenting with it, I think I should read the paper more thoroughly and hop along.


Difference between RC2, RC4, RC5 and RC6

RC2
RC2 is a 64-bit source-heavy unbalanced Feistel cipher with an 8 to 1024-bit key size, in steps of 8. The default key size is 64 bits. It was designed in 1987. It has a heterogenous round structure with a total of 18 rounds (16 "MIXING" rounds and 2 "MASHING" rounds). It is a complex cipher using secret indices to select key material. It performs bitwise rotations, AND, NOT, and XOR, as well as modular addition. The key schedule is reminiscent of MD2's internal operations. It is vulnerable to a related-key attack given 234 known plaintexts. It is defined in RFC 2268, though it was originally leaked to a mailing list through reverse engineering software that used it in 1996.
There is never a reason to use RC2. It is an extremely old cipher sponsored by Lotus for their Lotus Notes software and designed by RSA Security, Inc. with input from the NSA. It was meant to be an export-ready drop-in replacement for DES but was created long before we had a good understanding of block cipher design. It is relatively devoid of analysis and could easily suffer from severe security vulnerabilities that have not been discovered. It's an interesting cipher for sure, but not a useful one.
RC4
RC4 is a stream cipher with a 40 to 2048-bit key written in 1987 with a maximum theoretical strength of log2(256!) ≈ 1684 bits. It generates a keystream from a state array composed of a 256-byte permutation by swapping values based on a secret state-dependent index and an incrementing index. The first portion of the RC4 keystream shows a significant bias, though the bias shrinks as more keystream is generated. For that reason, many implementations drop the first few hundred (or even thousand) bytes. Other biases and serious problems such as vulnerabilities in how it uses a nonce exist that can make it difficult to use securely (in particular, the nonce is concatenated with the key, which is an issue as the cipher is vulnerable to related key attacks that enable key recovery). Of the ciphers you mentioned, RC4 is the only stream cipher. Its design was leaked to a mailing list in 1994.
If you ever find yourself needing to use RC4, make sure you combine the key and nonce by putting them through a cryptographic hash function first, rather than concatenating them as traditionally done. Ensure you drop the initial keystream (at least 768 bytes, but ideally up to 3072), and do not use it in applications where the same plaintext may be encrypted an unlimited number of times with different keys. Otherwise, small biases may allow recovery of the plaintext without needing the key.
RC5
RC5 is a block cipher using a 1 to 255 round (12 originally suggested) Feistel-like network with 32, 64, or 128-bit blocks published in 1994. The key size is 0 to 2040 bits. One thing that makes RC5 unique is its use of data-dependent rotations, a feature that theoretically improves resistance to cryptanalysis but which, in practice, often makes the cipher harder to analyze and can leave weaknesses that are only found later. Additional operations involved are modular addition and bitwise XOR. The cipher's key schedule uses magic constants derived from the fractional part of $\phi$ (the golden ratio) and $e$ (the base of the natural logarithm, aka Euler's number). 12-round RC5 with 64-bit blocks is vulnerable to a differential attack using 244 chosen plaintexts. Using 18 to 20 rounds should protect against this. RC5 was published in a research paper from MIT and its specification is described in RFC 2040.
There is no reason to use RC5. RC6 is an improved version which is also better researched. If you do need to use it, use 18 or 20 rounds. Do not use 12 as was initially suggested by the authors.
RC6
RC6 is a 20-round Feistel block cipher based off of RC5, with tweaks done to make it acceptable for the AES competition (including using a fixed block size of 128 bits and supporting 128, 192, and 256-bit keys). It can be viewed as two interweaving parallel instances of a modified version of RC5. RC6 ultimately lost to Rijndael, but did make it to the top 5 (along with Twofish, Serpent, Rijndael, and MARS). RC6 uses the same basic operations as RC5, but also includes multiplication to improve diffusion characteristics of the rotation operation. It is described in the paper that announced it.
Given that it survived the first round in the AES competition, it is thought to be quite secure. No major issues have been found in it. If you find yourself wondering if you should choose RC6 though, the answer is probably no. Stick with the winner of the competition, Rijndael (now referred to as AES).

All of these were created or co-created by Ron Rivest, one of the creators of RSA and the creator of MD2, MD4, MD5, and co-creator of MD6. RC is said to stand for "Ron's Code" or "Rivest cipher". Interestingly, RC1 was never published, and RC3 was broken at RSA Security during development.
In summary:

RC2 is an ancient block cipher that should not be used for anything.

RC4 is an ancient stream cipher that should not be used for anything, yet still is.

RC5 is a slightly newer block cipher and is secure with sufficient rounds.

RC6 is an improvement upon RC5, increasing its security. It lost the AES competition.

RC4 and RC6 are by far the most well-researched. The former is because of its ubiquitous use despite its weaknesses, and the latter because it was part of a competition that involved extensive analysis. However, you still shouldn't use any of these ciphers as there are far better alternatives.


Why FHE takes modulo space $\Bbb Z_p$ as $[−p/2,p/2)$ rather than $[0,p)$?

The notation

Many works on FHE use a function of $a$ and $p$ giving how far above or below the nearest multiple of $p$ the quantity $a$ is. Craig Gentry and Shai Halevi note that quantity as $[a]_p$ in Implementing Gentry's Fully-Homomorphic Encryption Scheme (extended abstract in proceedings of Eurocrypt 2011). It replaces $((a+\lfloor p/2\rfloor)\bmod p)-\lfloor p/2\rfloor$. This $[a]_p$ belongs to $[−p/2,p/2)$.

Nathanael Black in Homomorphic Encryption and the Approximate GCD Problem (page vii) go as far as using $a\bmod p$ rather than $[a]_p$:

  $a\bmod p\;\;$ Denotes reducing $a$ modulo $p$ into the interval $(-p/2, p/2]$

which is equivalent to
$$(a\bmod p)=r\;\iff\;p\text{ divides }a-r\;\text{ and }\;r\in(-p/2, p/2]$$
(the difference in interval boundaries is immaterial for odd $p$).

Alternatively, that variant $[a]_p$ of $a\bmod p$ could be defined as $a-p\cdot\lceil a/p\rfloor$, where $\lceil x\rfloor$ denotes rational $x$ rounded to the nearest integer (rounding up for Gentry et al.). This is similar to the standard $a\bmod p\;=\;a-p\cdot\lfloor a/p\rfloor$.

For both the standard and alternate definitions of operator $\bmod$, it holds that:
$$\begin{align}
((a+b)\bmod p)&=(((a\bmod p)+b)\bmod p)\\
&=(((a\bmod p)+(b\bmod p))\bmod p)\\
\end{align}$$
$$\begin{align}
((a\cdot b)\bmod p)&=(((a\bmod p)\cdot b)\bmod p)\\
 &=(((a\bmod p)\cdot(b\bmod p))\bmod p)\\
\end{align}$$
$$\begin{align}
(a\bmod p)&\equiv a&\pmod p\\
((a+b)\bmod p)&\equiv a+b&\pmod p\\
((a\cdot b)\bmod p)&\equiv a\cdot b&\pmod p\\
\end{align}$$
Note: In the above the notation $r\equiv a\pmod p$ means that $p$ divides $a-r$, and needs no adaptation. It is recognizable from operator $\bmod$ by the use of an opening parenthesis immediately on the left of $\bmod$, and (sometime: or) the use of an $\equiv$ sign somewhere on the left of and paired with $\bmod$.

Why it is useful

With the alternate definition $[a]_p$ of $a\bmod p$ comes an additional useful property, that does not hold for the standard $\bmod$: when $p$ is odd, for all $a$, it holds that $[-a]_p=-[a]_p$. That also holds for large even $p$ and most $a$.

The concept allows an easy extension to signed numbers and subtraction of one of the simplest (partially) homomorphic encryption system: Paillier's encryption. All it takes is defining a modified decryption as $D'(c)=[D(c)]_n$ and restriction of plaintext range; see this.

In some FHE systems, $[a]_p$ matches a signed noise term algebraically added to a signal aligned to multiples of $p$, and $a-[a]_p$ is the pristine signal recovered from the noisy $a$, minimizing the absolute value of noise $[a]_p$.


BouncyCastle Elliptic Curve implementation

I am assuming you are throughly familiar with traditional Diffie-Hellman. If not, read up on it first.

For our purposes here, an elliptic curve is a curve whose points satisfy the equation $y^2=x^3+ax+b$. That right there tells you what $a$ and $b$ are, they are coefficients of the curve.

In elliptic curve cryptography, we need an algebraic group for a number of algorithms (such as Diffie-Hellman). For elliptic curves, we can get this by taking the curve equation above modulo a prime number (in this case the $q$ value in your code), i.e. $x$ and $y$ are elements of $\mathbb Z_q$, and the $+$ and $·$ operations are done in this field.

For diffie-hellman we need a point on the curve that can generate a very large subgroup (for more info see this question). That point is the $G$ in your code. $n$ is the order of the subgroup generated by $G$ and $h$ is the cofactor (basically it tells us how much smaller is the subgroup when compared to the original group, don't worry too much about this one).

The reason they are static is that they are public parameters. Think of regular diffie-hellman. There are typically numbers $p$ and $g$ which need to be known to both parties. $p$ describes the group we are working in $\mathbb{Z}_p^*$ (just like $q,a,b$ describe the elliptic curve group) and $g$ is the generator (as is $G$ for elliptic curves). In regular diffie-hellman $p$ and $g$ can be static in your code (otherwise the 2 parties have to agree upon the values some how).

You now know what the values are and why they can be static. So, are the values you've chosen correct? Well, where did they come from? There are a number of standard curves (for example FIPS 186-3). If I were you, I'd stick to recommended/standard curves.


Is is safe to use MtEtM? (MAC-then-Encrypt and Encrypt-than-MAC)

If the MAC is theoretically secure, but its implementation has a side channel (like by Differential Power Analysis, maybe even timing) leaking information about the MACed message (but not the key), and the encryption is secure including it's implementation, then neither MtE nor MtEtM are safe (because the side channel leaks about the message), but EtM is secure (because the MAC is applied to ciphertext, which can safely leak).
Thus EtM can be secure when MtEtM is not. A better reason to prefer EtM to MtEtM is Occam's razor.


What information to include when calculating the HMAC of ciphertext

Yes, it is best to include all that information in the HMAC. Otherwise an attacker can change those values and you would not get the correct plain text. This would mean that you get either incorrect information, or you leak information that could be used for padding oracle attacks.

In case of the IV, if you don't include it in the HMAC then the attacker can change the first block of plain text you get when you decrypt the first block (assuming CBC mode encryption here).