Is it meaningful to consider the leakage of master key of KGC?

There are plenty of papers on forward-secure IBE, one could just google that term.

Here, I will focus on IBE with a property that I would call "key forgetting",

and work toward a candidate construction for depth-O(1) HIBE with that property.
One could apply either of the sections "Random Oracles, depth-O(1) adaptive-ID security,

and (lack of) Completeness" and "Hashing and Recovery" without applying the other,

but if one applies both then one should apply them in that order.

Discussion and Inherent Limitations:

In such a scheme, the KGC is able to update the main private key (that is, the KGC's secret) in order to "forget" the private key corresponding to a specific ID. $\:$ After it does so, the main private key should

be sufficient to compute the private keys corresponding to other IDs, but should not be sufficient to

violate confidentiality on that particular ID. $\;\;\;\;$ For n such that $\: 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n \leq 2^L \:$, $\:$ one can consider an

arbitrary set B of $\:2\hspace{-0.04 in}\cdot \hspace{-0.04 in}n\:$ identities whose lengths are each $L$, and imagine having the KGC forget the provide keys corresponding to an $n$-element subset S of B. $\:$ Confidentiality implies that encrypting a

long random plaintext for an ID in B, having the KGC run extract on that ID, and applying decryption

with its output to the ciphertext, should have a negligible probability of resulting in the original plaintext.

On the other hand, functionality implies that doing the same for an ID in B-S

should have an overwhelming probability of resulting in the original plaintext.

Thus, doing that for each ID in B should have an overwhelming probability of recovering the set S.

Since there are at least 2^n such subsets of B, it follows that the probability of the main

private key being shorter than $\:\lfloor n/2\rfloor\:$ bits long is at most negligibly more than $\:1/2^{\lfloor n/2\rfloor}\;$.

Thus the size of the main private key must grow at least

linearly with the number of secret keys forgotten so far.
Now, suppose additionally that the scheme has sufficient completeness to make the next sentence true.

The not-necessarily-feasible procedure that takes as input (the public key and) the main private

key and outputs the set of IDs for which the extract procedure has a probability greater than

half of neither giving a valid private key nor successfully blaming anyone else for that failure,

always outputs a subset of the set of IDs for which the KGC has run the "forget" procedure.

Furthermore, confidentiality and computational soundness of the blame testing implies that

the procedure I just described should have an overwhelming probability of outputting all of

the IDs for which the KGC has run the forget procedure, which means the main private key is

overwhelmingly likely to uniquely determine that set of IDs. $\:$ Thus, that completeness condition

essentially requires the KGC to store a list of all IDs for which it has run the forget procedure.
Those limitations apply even to IBE schemes that only need confidentiality to hold for random IDs.

Positive Results from BTE:

Binary Tree Encryption directly allows for the construction of

selective-ID HIBE for fixed-depth-and-fixed-piece-length IDs with key-forgetting at each level, by just concatenating the parts of the IDs together to determine the relevant node, and to forget a key, store the keys corresponding to the nodes that differ from the relevant node in their last bit but nowhere else, and then erase the keys corresponding to the nodes that are prefixes of the relevant node.
Although potential encryptors would have to be informed somehow,

any KGC at any level could otherwise independently, by putting the time period before the ID, implement forward-security and revocation at the additional cost of requiring decryptors

to get a private key during each time period, which would also make it so that the KGC's

storage requirements only depend on the keys forgotten during the current time period.
By, for example, putting a 1 before each "real" part of IDs and appending an

all-zero ID-piece, one can use IDs of bounded depth, rather than just fixed depth.

By using a prefix-free code, one can also handle IDs whose pieces have bounded length,

although the next part of this answer will assume the ID-pieces are still fixed-length.

Random Oracles, depth-O(1) adaptive-ID security, and (lack of) Completeness

In order to go from selective-ID security to adaptive-ID security in the Random Oracle Model, one picks a Random Oracle whose inputs are interpreted as having two parts, the main one of which will be IDs, and whose outputs are much longer than its inputs, and an XOR-almost-universal family of hash functions whose domains are the space of IDs and whose codomains are the set of

bit strings whose lengths are each the same unit fraction of the oracle's output length.

(Multiplication in a binary field is an example of such a hash family.) $\:$ The master private key is has ident_set and func_set both initialized as empty sets, along with what the master private key would

be for the selective-ID scheme with ID-piece lengths equal to the length of the oracle's outputs.

The public key contains a list of [that fraction's denominator] claimed samples from that hash family, one of which was generated by the master KGC and the others of which weren't, the public key for

the selective-ID scheme, and a random string that will be used as the minor part of the oracle's input.

As long as the hashes chosen all do not depend on that random string (in particular, if they are all chosen before the random string), confidentiality will hold even if the hashes are all chosen maliciously.
For any real ID, let F(ID) denote the list that is [[the random oracle applied to the random string and the real ID-piece] xor [the concatenation of the hashes of the real ID-piece]]  for each piece of the real ID. $\:$ To encrypt and decrypt, use F(ID) in the selective-ID scheme. $\:$ To forget a user's private key, the KGC puts ID and F(ID) into the sets ident_set and func_set respectively, and then runs the selective-ID scheme's forgetting procedure on F(ID). $\:$ To extract, a KGC does as follows: if F(ID) is not in func_set then run the selective-ID scheme's extract algorithm on F(ID) and return that algorithm's output,

else if ID is in ident_set then reject, else [indicate a completeness failure, find the value ID' ident_set such that F(ID') = F(ID), and give the pair ID,ID' as a publicly-verifiable proof that all of the hashes in the public key came from a particular subset of their values that, unconditionally, is exponentially unlikely].

The last part is somewhat unsatisfying, since I don't see any

reason why one shouldn't hope for perfect completeness.
Although potential users would have to be informed somehow, any KGC at

any level could otherwise independently use a different list of such hashes.
The resulting bounded-depth-and-fixed-piece-width HIBE scheme is such that attacking an ID

that differs in at most $\Delta$ pieces from a pre-selected ID of depth at most d, by making at most

q Random Oracle queries, corresponds to attacking the selective-ID scheme on one of a list of

of at most $\:((\Delta \hspace{-0.04 in}+\hspace{-0.04 in}d\hspace{.03 in})\hspace{-0.02 in}\cdot \hspace{-0.02 in}(1\hspace{-0.04 in}+\hspace{-0.04 in}q))^{\Delta}\:$ randomly chosen IDs. $\;\;$ In particular, the resulting scheme is

adaptive-ID secure for IDs of depth O(1), where the constant does not need to be chosen a-priori.

Hashing and Recovery

In order to remove the fixed-ID-length restriction, one can try hashing IDs.

However, the issue is that completeness when IDs collide.

That can be dealt with by using a collision-resistant (cryptographic) hash family such that each

hash is associated with a unique and computationally-indistinguishable-from-uniform secret,

one can efficiently sample pairs consisting of one of those hashes and the secret for that hash,

and one can efficiently recover that secret from a hash collision.

(I will give a candidate construction of such families at the bottom of this answer.)
I'm getting really bored with typing this up, so for now I'll just say that

the KGC encrypts its original key with the hash, so that it will be able to

decrypt that and preserve completeness whenever it sees a collision.

Hopefully I'll finish this sometime soon.

The hash families I'm talking about are given by a (strongly) hard-core function and

concatenation of Pedersen commitments, for groups of known prime order p such that

there is an efficiently-computable, but not necessarily efficiently invertible, injective map

from the group to {0,1,2,3,...,n-2,n-1} for a known n such that (p^2)/((p^2)-n) is noticeable,

and the secret is the concatenation of values of the hard-core function on the discrete logs.


How come hash salt doesn't make a hash ineffective?

The salt is stored in plaintext next to the hash and the same salt is used when checking a password.

Its purpose is to slow down attackers who obtained a copy of the database:

They must attack each password on its own (they need to try each input for each hash instead of trying each input and comparing the output to all hashes at once).
They can't make use of huge precomputed lookup tables ("rainbow tables") since salting is essentially equivalent to giving each user their own hash function.

There is no need to keep the salt secret or store it more safely than the corresponding hash.

(This is as opposed to pepper, which is mixed into the hash in the same way but is fixed per application and not stored in the database. This tries to defend against attackers who obtained database access, but not the application's program code or configuration files.)


How does the split mask countermeasure work on AES?

Given some intermediate data $x$ as two shares $x=x_1\oplus x_2$ take some fresh random $r$ to calculate new shares $x_1' = ((x_1\oplus r)\oplus x_2)\oplus(n\oplus r)$ [parenthesis indicating the order of evaluation] and $x_2' = n$. Now you can use $x_1'$ ($=x\oplus n$) as input for both tables.

The answer to "So how should it be computed?" is not at all. It is not needed. I think this is just a warning that it would be a problem to have (2) as intermediate value, because $m$ is kept constant for many plaintexts. Strangely enough, the inventors of the split mask countermeasures didn't realize that keeping $n$ constant for many plaintexts poses the same risks. A very short look at the paper you linked to, gave me the impression that it will expose this weakness in later chapters.


I think it's better to define the  keyspace of an unkeyed function as having one element.

Some advantages:

Computing the key size as $log_2 1$ correctly tells you it's a 0 bit key
For encryption you pick one key from the set. You can pick an element of a single element set, but can't pick from an empty set
Functions with multiple inputs are often defined to take the Cartesian product of their inputs. For example for encryption this could be $M \times K \to C$ where $M$ is the space of messages, $K$ the key space, and $C$ the ciphertext space. One again, this only works correctly if you use a single element set as key space.


Why mounting/dismounting an encrypted file container takes only a few seconds?

Think of it this way.
When you plug in a non encrypted external hard drive, does your computer read all of the data? No, it reads the partition table and some of the directory structure/MFT in order to display disk space usage and the root directory. The same thing occurs when an encrypted drive is mounted, whether it is Truecrypt, LUKS, or Bitlocker.
Disk encryption is block based, each block can be encrypted or decrypted independently of other blocks, to enable random access to the encrypted data. Only the data that needs to be read is read in order for the computer to understand what is being mounted, and thus only the blocks that need to be decrypted are decrypted.
Prior to disk access occurring, the mounting process must first determine the key and encryption method using the password or key material provided, this is very quick unless you have a custom iteration count.
Additionally, on many drives, the read/write speed is far slower than the cryptography speed the computer is able to handle, so there is no perceptible loss of performance due to encryption overhead.


Encrypting a JPG, where the output is a scrambled JPG

I wrote several papers on such a topic. I called it end-to-display encryption. But it is more commonly called "pixel-domain encryption" There are several easy ways to do this. My way included adding a header with RSA encrypted AES Keys.

In essence, you take the picture, extract the pixels, XOR with the bitstream created through AES in Countermode, increase the counter with every iteration, convert that to pixels, save as PNG (important, not jpeg or any other lossy compression, you lose bits with that, and decryption needs every bit to work properly). Thats it. And the same way back.

But sorry, no tool available. But its easy to implement.

I may extend on the thing with the JPEG in the question. Encrypting JPEG in the pixel domain will not work properly. The compression is lossy, so you lose information. There are compression methods on JPG, but they are much more complex, because they work mostly on the DCT factors, not on the pixels itself. These can also be viewed as pictures. That said, its another application field, as i wanted to decrypt pixel streams in the HDMI cable, that would not have worked as intended, or only with much more complex systems.


If you perform the distribution digitally (using networks) then you have a problem. Unless you use another one time pad you lose the perfect confidentiality as the distribution itself won't deliver perfect security. But using another one time pad is pointless: you would lose exactly as many key bits as you are distributing, while you are only protecting the data for confidentiality, not integrity and authenticity.

So basically you'll probably have to physically distribute the keys. That kind of burden is probably not very useful. Hence we mostly treat the one time pad as a theoretical cipher. One very big reason for this is that - although not proven secure - there are many (stream) ciphers that are thought to be secure. There is simply no need for a one time pad.

So the key management / key distribution is extremely awkward for one-time-pads not just because of the size, but also because anything you do with the key breaks the perfect secrecy you are trying to achieve.


Practical probabilistic proof systems not based on polynomials

You can look the Groth-Sahai proof system; Its practical and has been well studied and it's not reliable to The Schwarz-Zippel lemma.
But it depends of the form of the equations you want to prove.


How do I calculate Base64 conversion rate?

However, I do not know what length I need to have the signature at so when I encode it, it can be that exact size.

Well, base64 uses 4 characters (from an alphabet of size 64) to encode 3 bytes (3 bits contain 24 bits; 24/4 = 6 bits per base64 character).
Hence, if the signature was 72 bytes long, that would translate to 72/3*4 = 96 characters you require.
Now, base64 typically has a === trailer to signify the end of the encoding; are you counting that?


Is there a standard for OpenSSL-interoperable AES encryption?

Since this is still open and the issue keeps coming up:

TLDR: There are lots of things in OpenSSL that implement standards including AES, but the key derivation part of enc is partly nonstandard (at least by default)

First, OpenSSL has several commandline operations it calls commands (although they usually aren't separate programs, as typical commands are on Unix), and a whole range of library calls, that do encryption and decryption with numerous symmetric algorithms of which AES is only one as well as several asymmetric algorithms. Major ones are PKCS#7/CMS and semantically equivalent S/MIME; PKCS#8/rfc5208 and PKCS#12/rfc7292; and the SSL/TLS protocols for which it is named.

The file format with Salted__ is used by one specific OpenSSL command enc. Although if the commandline executable is given a cipher name instead of a command it silently translates to enc -- for example openssl aes-128-cbc ... becomes openssl enc -aes-128-cbc ... -- so people often perceive and describe this as 'OpenSSL AES-128-CBC encryption' as if it were the only AES-128-CBC encryption OpenSSL does.

enc can encrypt and decrypt files (including anything the OS can provide as standard input and output, such as a pipe) with a wide range of options in (mostly) two dimensions:

the symmetric cipher algorithm and mode, and padding. OpenSSL library provides and enc can use several algorithms, which may vary depending on build but currently default to Blowfish CAST DES DES-EDE(3) (usually called TripleDES TDES or TDEA) IDEA RC2 RC4 Camellia SEED and AES; I haven't bothered linking all the standards. Some algorithms, especially AES, have options for key size. All except RC4 are block ciphers and must be used with a mode such as CBC ECB or CTR; although algorithms and modes are actually defined by separate standards, enc (and the EVP API) combines them in a single name like aes-128-cbc above. (added) A list of the algorithm-and-modes is available through version 1.0.2 from openssl list-cipher-commands or just openssl enc -?, or version 1.1.0 from openssl enc -ciphers. Do not use openssl ciphers which shows something quite different: the ciphersuites available for SSL/TLS protocol communication.

Some block modes (CBC and ECB) require data be a multiple of the cipher's block size; since in general real data doesn't do this, it is necessary to add padding when encrypting and remove it when decrypting. By default OpenSSL uses the padding scheme defined by PKCS#7 which extends a scheme defined in PKCS#5, and therefore is usually still called PKCS#5 or just PKCS5 padding. If you specify -nopad this is not done, and (for these modes) encrypting (or decrypting) wrong-size data gives an error.
all symmetric ciphers require a key, and some modes require an Initialization Vector (IV). enc can use a 'raw' key and if applicable IV specified on the commandline, with -K (uppercase!) and -iv and in hexadecimal. However its default and usual mode is to do Password Based Key Derivation (combined with encryption to give Password-Based Encryption, PBE), and this in turn has several options.

The password can be entered several ways, using legacy option -k (lowercase) or -kfile or newer option -pass or prompted for and typed with no terminal echo (if possible).

The newer, preferred and default option is salted key derivation, which strengthens the derivation (but see below) by using 8-byte random salt. It is also possible to specify a specific salt with -S in hex, or disable salting with -nosalt. If salt is used, random or not, a very simple header is added to the ciphertext consisting of the ASCII characters Salted__ and the 8 bytes of salt. (Standardized PBEs like PKCS#12 also convey the salt, but use much more extensive and flexible formats.)

The key derivation process is based on PBKDF1 from PKCS#5/rfc2898 but modified, and is implemented by the API function EVP_BytesToKey whose man page should be available in any Unix system with OpenSSL installed and on the website. A bit confusingly, and inconsistent with more recent best practice, this 'key derivation' actually derives both the key and IV if applicable. To lay out the relationship exactly:

PBKDF1 uses a choice of hash from MD2 MD5 SHA1, and an iteration count, and (required) salt. It initially forms password || salt and hashes it, then hashes the first hash, then hashes the second hash, iterating to a total of count times. PKCS5 PBES1 uses PBKDF1 to produce both key and IV -- but only for RC2 and (single) DES, neither of which is acceptable today.
EVP_BytesToKey uses any hash supported by EVP, which may depend on build options but currently defaults to MD4 MD5 MDC2 RIPEMD RIPEMD160 SHA1 and the original SHA2 family (but not the later '512 slash' additions), plus iteration count and optional salt. It does one block like PBKDF1 as H^count (password||salt) with the salt omitted if not used, but if the required 'key material' is more than one block, it then does additional blocks as H^count (prevblock||password||salt) ditto. Whether the EVP_BytesToKey result is used for IV depends on the caller.
enc uses EVP_BytesToKey with salt by default (but see options above); (edit) hash MD5 by default through 1.0.2 or SHA256 by default in 1.1.0 released 2016-08 but you can specify otherwise with the option -md which was only documented from 1.0.0 but actually available before; and iteration count ONE. Thus the key and IV if applicable used by enc before 1.1.0 defaults to

key[||IV] = b0=md5(t=pw[||salt]) || b1=md5(b0||t) || b2=md5(b1||t) ...

This is a poor PBKDF. Because all the available hashes (including default MD5 or SHA256) are fast and this PBKDF 'iterates' only once, an attacker can quickly try large numbers of possible passwords to find yours, unless your password contains enough entropy without any significant 'strengthening' -- and most people don't choose, and even if given can't remember, such strong passwords.
But we are stuck with it for backward compatibility.

Thus for examples:

openssl rc4-128 [-e|-d] -k sekrit -nosalt
# uses RC4 with 128-bit key (RC4 is a stream cipher and uses no IV)
# derived using no salt, MD5 (unless 1.1.0), and count 1 from 'sekrit'

openssl aes-256-cbc [-e|-d] -k sekrit -md sha1
# uses AES in CBC mode with 256-bit key and 128-bit IV
# (both) derived using random salt, SHA1 and count 1 from 'sekrit'
# and adds the Salted__ header with the salt to the ciphertext

And finally, if you specify -base64 or the abbreviation -a, the ciphertext (including header if any) is encoded to base64 on encryption, and decoded from base64 on decryption; this is fairly commonly needed because some applications, systems, or protocols cannot handle the arbitrary (quasi-random) binary bytes needed for ciphertext. (edit) Similarly if you specify -z plaintext is compressed before encryption or decompressed after decryption, but only if OpenSSL was built with compression (zlib), and after the CRIME and BREACH attacks some builders or packagers disable compression entirely. These options are independent of the cipher and key/PBKDF, and in fact you can use them alone to only base64 encode/decode or zlib compress/decompress without doing encryption or decryption at all.

Base64 is used with slight variations in many standards but OpenSSL mostly follows the original PEM in 4.3.2.4 (no internal hyperlink because 1993 was before WWW became popular). Two caveats: base64 decoding silently ignores part and sometimes all of a line with a non-base64 character; this is useful when OpenSSL uses it internally to read PEM-format files, but may not be so in other applications. And before 1.1.0, it silently ignores lines longer than the 76-character limit specified in MIME unless you add -A (uppercase). zlib compression is related to, but not quite the same as, gzip.

Inter-version compatibility: (added) using password-based encryption and decryption depends critically on using the same parameters and especially the same hash in the PBKDF for both operations. As noted above, the default hash used by the enc command changed in 1.1.0 to SHA256 versus MD5 in lower versions. Thus data encrypted using the default hash in lower versions won't decrypt with the default in 1.1.0 or vice versa.

if data was encrypted with the default (MD5) on an older version, decrypt in 1.1.0 (and presumably higher when released) with -md md5
if data was encrypted with the default (SHA256) on 1.1.0 (or presumably higher), decrypt in an older version (at least back to 0.9.8, possibly before) with -md sha256
to proactively prevent a problem, specify -md consistently for both encryption and decryption even when it's redundant

UPDATE: OpenSSL 1.1.1 (2018-09) adds an option for -pbkdf2 -- with default iteration count 10000 -- and an option -iter to change that count -- and gives a warning when you don't use these i.e. when you default to the old scheme, described above. This is the standard PBKDF2 from PKCS5v2/RFC2898, although 10k is rather low (but much better than 1!); even my aging laptop with a Celeron can do 100-200k without noticeable delay. Compare
Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value?
https://security.stackexchange.com/questions/110084/parameters-for-pbkdf2-for-password-hashing/
https://security.stackexchange.com/questions/3959/recommended-of-iterations-when-using-pkbdf2-sha256 .
But the iteration count isn't recorded in the file, so you must either remember it (which makes varying it inconvenient) or store it elsewhere such as the filename or other metadata like an NTFS alternate stream.
Also, it still uses the traditional enc behavior of deriving both the key and IV (if needed), not choosing the IV by a separate random process, as the encryption scheme PBES2 in PKCS5v2 does.


Stateless and deterministic number generation

I want a stateless deterministic pseudorandom generator.

I don't see how that can work.

"Stateless" - the generator is always in the same state

"Deterministic" - given the same state (and inputs, but there's no inputs here), the generator always generates the same output.

Hence, you end up with something that always generates the same output; hardly pseudorandom.

The comparison with SPHINCS doesn't appear to be quite valid; the original SPHINCS is not deterministic (it selects the path through the hypertree randomly); you could make it deterministic (by depending on the message being signed to seed your randomness), but that's making it depend on an input that your pseudorandom number generator doesn't have.


First thing to note is that, if your paradigm is the hash the message into a 512 bit value, and then map that 512 bit field into a value $(0, p-1)$, then (unless $p$ happens to be a power of 2, and very few primes are) there will always be some bias.  $p$ is not a divisor of $2^{512}$, and hence some values will have more 512 bit preimages than others (and going to a complicated hash-of-a-hash method doesn't change this).

Secondly, if this is the paradigm we need to live with, your method 1 (compute $hash \bmod p$) achieves the minimal possible bias; some values will have $\lfloor 2^{512}/p \rfloor$ preimages (and hence occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor$, others will have $\lfloor 2^{512}/p \rfloor + 1$ preimages (and so occur with probability $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$; no other possibilities.

Thirdly, the amount of this bias (for $p \approx. 2^{300}$) is truly tiny; the ratio between $2^{-512} \lfloor 2^{512}/p \rfloor$ and $2^{-512} \lfloor 2^{512}/p \rfloor + 2^{-512}$ is circa $1 + 2^{-212}$; to even detect a bias that tiny (and an undetectable bias cannot be exploited) you'd need to sample circa $2^{424}$ hashes before the bias can be detected; and you will never ever generate that many.

Fourthly, one nice thing about the modulo method is that it is easy to test (assuming you're using a vetted modulo routine).  With the methods that involve exceptions, well, those can be trickier (because you need to go through all the possible cases to make sure those are handled properly); with the modulo, there is only one case.


Does absence of second pre-image resistance infer absence of pre-image resistance?

No, it is easy to show that (assuming that there are preimage-resistant functions at all) there are functions that the preimage-resistant, but not second-preimage resistant.

If we assume that SHA512 is preimage resistant, one such function is:

$$H(x) = SHA512(Trunc(x))$$

where $Trunc(x)$ just returns $x$ with the last byte removed.

$H$ is not second-preimage resistant; given $H(x)$, we can change the last byte of $x$ to another value that hashes to the same value.  However, given a target hash value $z$, we can't find a value $x$ with $z = H(x)$; if we did, then we could find preimages to SHA512.

And, in practice, it doesn't only come up only in artificial hash functions (as above); in real hash functions, we can often come up with a way to 'tweak' the message in such a way so that the intermediate state of the hash function happens to be unchanged after the tweak (which would imply that the hash value is unchanged).


Algebraic cryptanalysis on public-key schemes

Of course, it is possible.  It is possible to take a public key encryption algorithm which takes the private key and the known ciphertext into the known plaintext, convert that into a set of equations in $GF(2)$ with the private key as unknown variables, and solve for those unknown variables.  Alternatively, you can take the key generation algorithm, which takes some random bits and converts that into the public and private keys; convert that into a set of equations with the public key output as known, and solve for the private key (and the random bits).

However, the relevant question is "is this (converting the problem into a form that has known NP-hard instances) easier than solving the hard problem directly?"  I don't believe it is.


Side-channel resistant discrete uniform sampling on $d\neq 2^t$ values?

Off the top of my head, here's a somewhat more efficient rejection sampling algorithm.  It involves maintaining a (possibly non-secret) bit counter $k$ and a secret $k$-bit value $0 ≤ s < 2^k$.

Initially, let $k = 0$ and $s = 0$.
To sample a uniform integer $x$ from $\{0, \dots, d-1\}$ for a given upper bound $d$:

Let $t = \lceil \log_2 d \rceil$ and $g = 2^t - d$.
If $t > k$, generate a uniformly distributed random $t - k$ bit number $z$ and let $r = s + 2^kz$; else let $r = s \bmod 2^t$.  (That is, we take $r$ to be the lowest $t$ bits of $s$, adding extra random bits at the top if needed.)  Now $r$ is uniformly distributed on $\{0, \dots, 2^t-1\}$.
If $r ≥ g$, update $k \leftarrow \max(0, k - t)$ and $s \leftarrow \lfloor s \mathbin/ 2^t \rfloor$ and return $x = r - g$.
Else let $h = \lfloor \log_2 g \rfloor$.  If $r ≥ 2^h$, subtract $2^h$ from both $r$ and $g$ and repeat this step.  (In other words, while $g$ and $r$ have the same highest set bit, clear that bit and repeat.  This process will eventually stop, since we know that $0 \le r < g$; it's not hard to show that clearing the highest bit preserved this invariant, and that $r$ is always uniformly distributed on $\{0, \dots, g-1\}$.)
(Now $r$ is uniformly distributed on $\{0, \dots, 2^h-1\}$.) Update $k \leftarrow h + \max(0, k-t)$ and $s \leftarrow r + 2^h \lfloor s \mathbin/ 2^t \rfloor$ and repeat from step 1.

Note that I'm assuming that we can do comparisons and basic arithmetic (i.e. addition, subtraction and bit shifts) on secret values without leaking any information about them (other than the result of the comparison).

Basically, the idea is to split the interval $\{0, \dots, g\}$ of rejected values into a sum of intervals of power-of-two sizes (which can be conveniently obtained from the binary expansion of $g$), find out into which of these intervals the rejected sample belongs to, and add that many bits of randomness from the rejected sample back into the entropy pool $s$.

(In particular, note that the number of bits in the entropy pool $s$ is always strictly less than the length of the longest requested value.  In particular, if $d$ is constrained to be at most $2^n$, then an $n$-bit integer variable can be safely used to store $s$.)


Is there an encryption scheme that is url-safe AND compact?

TL;DR You should use format-preserving encryption which is designed to solve your problem.
There are various solutions some of which are easier than others to implement. I'll estimate their sizes based on your example token and url.
Some less than perfect solutions
As suggested in the comments, a bitwise stream cipher (such as ChaCha) or block cipher in streaming mode (such as AES-CTR) followed by base 64 encoding and url tokenising will only make your string about 42% longer plus any IV overhead. You may or may not want to worry about the ability of the user to modify the data. A user who can identify their token data could then forge tokens of the same or shorter length.
Estimated token length with 128-bit IV: 61 characters.
Estimated url length: 92 characters.
By adding a MAC you can defend against token manipulation but add another 21-22 characters to both lengths. Modern authenticated encryption methods may integrate authentication codes automatically.
You can shave off some characters with shorter IVs and MACs, but I wouldn't recommend going below 64-bits. These would save you 10-11 characters.
Estimated token length with 64-bit IV: 50 characters (61 with 64-bit MAC).
Estimated url length: 81 characters (92 with 64-bit MAC).
If we assume that your tokens use a character set of size 65 {A-Za-z0-9@|.} You could index the set and use a mod 65 stream cipher which would preserve the character set. Again IVs and MACs would be advisable, but could be expressed in the character set. There aren't any off the shelf mod 65 stream ciphers, but one could be constructed based on established stream cipher designs.
Estimated token length: 40 characters (52 with short MAC)
Estimated url length: 71 characters (73 with short MAC)
My laptop browser has a 65 character address bar and so I like urls with fewer than 64 characters to inhibit malicious url suffixes such as @http://evil.com/malware.exe. None of these solutions manage to achieve this for your example.
The designed and standardised solution
You can create url-friendly tokens and then use format-preserving encryption for 0 overhead. NIST have a standard for FPE and googling for "FF3-1 open source" should find an implementation in your language of choice.
Estimated token length: 27 characters
Estimated url length: 58 characters
58 character urls are still longer than the address bar on my phone browser, but this is still pretty good.


A query on Learning with errors(LWE) problem

It is easy to reduce this problem to LWE, since adding any element to a uniformly random value gives a uniformly random distribution.

For example, here, $(A',b')$ is distributed the same as if $A'$ was drawn uniformly randomly, and $R$ set as $A'-A$. You're now in the setting of the LWE assumption and can replace $b'$ by a uniformly random value without anybody (PPT) noticing it. With more details:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b'^t := s^t A'+ e^t, e\gets \chi^m,$$

is distributed identically to:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b'^t := s^t A' + e^t, e\gets \chi^m,$$

which is computationally indistinguishable from:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b' \gets \mathbb{Z}_q^{m}.$$

You can then switch back to normal generation of $A'$: the previous distribution is identical to:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b' \gets \mathbb{Z}_q^{m}.$$

Edit: added more details to clarify the answer.


Why are huge prime numbers important in cryptography?

Preposterously large primes are not useful for cryptography in and of themselves, but the tools and techniques developed to find them (such as massively parallel distributed computing, algorithms that can efficiently confirm primality, etc) are important for cryptography.  The prizes are meant to spur innovation in those areas.  See e.g. https://www.eff.org/awards/coop


Based on @Cort Ammon suggestion and some additional consultation i think the below will work

  Each of the 5 parties could publish Hash(vote || random bytes), because of the random bytes it would not be possible to find the vote by hashing guesses. Then after all commitments are published or 24 hours has passed each party would publish the plaintext = (vote || random bytes), and all other parties could hash that to verify that it is equal to the original commitment.


Clipper chip (SKIPJACK) key exchange protocol

Wikipedia is wrong in this case - just like the NIST publication describing SKIPJACK already implies by being titled "SKIPJACK and KEA Algorithm Specifications". In fact, on page 17 of that paper, you will find infos about KEA exchange for Email and on page 12, there's a summary of a full KEA exchange between devices A and B…

A summary of a full KEA exchange between devices A and B (page 12)

A summary of an Email KEA exchange between devices A and B (page 17)

On a side-note: If you check the Wikipedia entry, it shows that Wikipedia entry has been edited meanwhile, just like @ilmari-karonen already mentioned in a comment.


What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithms?

In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple.

Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient quantum algorithm for the Fourier transform. Then, applying this Fourier transform twice (once for $a$ and once for $b$) on a quantum superposition of values $g^a\cdot x^{-b}$ and measuring yields a pair $(c,d)$ with $d\equiv -cr\pmod{p-1}$. Thus, you can recover $r$ (if the gcd of $c$ and $p-1$ is $1$) directly with a simple division modulo $p-1$. [If the gcd is a small number it is also easy to conclude]

Unfortunately, doing this Fourier transform directly is only easy when $p-1$ is smooth (which is an uninteresting case since dlogs are easy with a classical computer in that case) and technicalities arise because of this. These technicalities involve replacing the Fourier transform modulo $p-1$ by a Fourier transform modulo $q,$ where $q$ is smooth and not too far from $p-1$.  A similar technique is used for factoring: it is simpler than the general discrete logarithm case because a single application of the Fourier transform is enough in that case.


Distinguishing between two probabilities and the uniform probability

Perhaps a proof by contradiction? Either they are both indistinguishable from uniform or not. If so, they are indistinguishable from each other. Since that contradicts the premise, at least one must be distinguishable from uniform.


OTP same message encrypted twice (with different keys)

The most an attacker can find out is that $c_1 \oplus c_2 = m \oplus k_1 \oplus m \oplus k_2 = k_1 \oplus k_2$. But since both $k_1$ and $k_2$ are fully random and not reused it won't help the attacker to find either $k_1$ or $k_2$. Basically each key stream is still encrypted with the other key stream.

Note that for OTP $k_1 \ne k_2$ is an invalid constraint; the keys should be fully independent of each other. For instance, if you have $k_1 = C | 0$ and $k_1 = C | 1$ where $C$ is a constant then $k_1 \ne k_2$. Those keys do however not represent valid OTP key streams; those must be fully random. Fully random also means that $k_1 = k_2$ is a possibility. If you know that the message is always identical then $k_1 \ne k_2$ means that if you get $c_1 = c_2$ that the messages differ.

So given the invalid constraint that $k_1 \ne k_2$ is true, then the answer of the question is yes - the security is lowered. If the keys are truly random then the answer is no.


Why is the following RSA PRNG cryptographically secure?

Perhaps you are thinking of the Micali-Schnorr PRNG, as described in Algorithm 5.37 of the Handbook of Applied Cryptography?
Algorithm 5.37 in HAC never states that $e$ is known to the adversary, or even that $n$ is known. Also, Algorithm 5.37 outputs only the least significant bits of the number, on each iteration. So I think you are confusing RSA as typically used and RSA as used in the Micali-Schnorr PRNG. What you describe does not match what is found in Algorithm 5.37.  Yes, for the generator you describe, given $x_i$, $e$ and $n$, the adversary could compute $x_{i+1}$, but in the Micali-Schnorr PRNG, it appears that we assume that $e$ (and even $n$) is unknown to the adversary.

Note 5.39 states that the security of this PRNG is based on stronger assumptions than just the intractability of the RSA problem. In general, this is not a good thing. In crypto we generally want as weak of assumptions as possible.


Forgery attack against Textbook RSA with simple redundancy

The usual methods of RSA signature with message recovery (that is, embedding a part of the message in the signature, known as the revoverable message) are those in ISO/IEC 9796-2:2010 (partial preview). There are three:

Scheme 1; it is an ad-hoc scheme that essentially concatenates the recoverable message, the hash of the whole message, and a little fixed data (about two bytes when there's more to the message than the recoverable part), forming the padded message; to which the raw RSA private function is then applied. This scheme is insecure if the adversary can obtain the signature of many chosen messages, see Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann, Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures, in proceedings of Crypto 2009; or full PDF
Scheme 2; in addition to hashing, it uses salting and an unbalanced two-rounds Feistel construct using a Mask Generation Function, so that the input of the raw RSA private function is indistinguishable from random (except for about two bytes, and without knowledge of the salt assumed random). It aims at demonstrable security similar to (and by the same means as) the Probabilistic Signature Scheme introduced in version 2 of PKCS#1, and pioneered by Mihir Bellare and Phillip Rogaway: The exact security of digital signatures - how to sign with RSA and Rabin, in proceedings of Eurocrypt 1996; or better PDF.
Scheme 3; that's precisely scheme 2 with no salt. It is deterministic (when the size of the recoverable portion of the message is fixed), and has the same message embedding capacity as scheme 1. It has the demonstrable security of Full Domain Hash; see Jean-Sébastien Coron, On the Exact Security of Full Domain Hash, in proceedings of Crypto 2000, or better PDF.

Noticing that left-padding a message $M$ with zero bits leaves its value unchanged when bitstrings are assimilated to integers using big-endian conventions (as customary), the last paragraph of the question asks how to attack the trivial RSA signature scheme giving message recovery where

the signature of message $M$ is defined as $\mathcal S(M)=M^d\bmod N$ (just as in vanilla Textbook RSA message signature), restricted to $M$ of (perhaps: at most) $m$ bits with $m$ fixed, positive, and such that $m\ll \log_2N$;
the verification procedure recovers $M$ from $\mathcal S(M)$, as $M=\mathcal S(M)^e\bmod N$, then checks that $M<2^m$ (that is, checks the padding consists of zero bits).

Another way to look at this is: vanilla Textbook RSA message signature, with the message omitted (as it can be recovered from the signature), and restricted to be exactly (or at most) $m$ bits.

Just as in vanilla Textbook RSA message signature, it is easy to make an existential forgery out of nothing, in the sense that the message consisting of $m$ bits at zero has signature $0$, and the message consisting of $m-1$ bits at zero followed by a single bit at one has signature $1$. Also, if the public exponent $e$ is small, for any positive integer $S$ less than $2^{m/e}$, $S$ is the signature of message $M=S^e$.

Just as in vanilla Textbook RSA message signature, it is easy to make a forgery for a large fraction of valid messages $M$ one wishes to obtain a signature for, when having access to a signing oracle (that is, mean to obtain signature of any desired valid message, except for the messages subject to forgery). One method is to try to factor $M$ into $M_0\cdot M_1$ for $1<M_0\le M_1$, which is possible for a large fractions of messages $M$ (including all even $M\ge4$, and more generally all $M$ divisible by a small prime and larger than this prime). It holds that $\mathcal S(M_0)\cdot\mathcal S(M_1)\bmod N=\mathcal S(M)$, and that allows computing the signature of $M$ from that of $M_0$ and $M_1$.

Note: a former version of the present answer explained how to forge a slightly less vulnerable trivial RSA signature scheme giving message recovery, which (it turned out) did not match that intended in the question.


If you have two inputs of the same length, are there theoretically collissions in both MD5 and SHA-256?

It is possible such collisions exist, but because SHA-256 is collision resistant, finding any collisions would be computationally infeasible.  You may safely assume without further checking that if two files have the same SHA-256 hash, then they contain the same content.
You can so safely assume that, given current cryptographic knowledge, that there's no reason to use MD5 at all; you can just use SHA-256.  In fact, you should actively avoid MD5 if at all possible.


Reasoning behind SHA-3 state array indexing

First let us have a look at the state representation.

  For all triples $(x,y,z)$ such that $0 \le x < 5$, $0 \le y < 5$, and $0 \le z < w$, $$A[x,y,z]=S[w(5y+x)+z].$$
  For example, if $b = 1600$, so that $w = 64$, then

A[0,0,0] = S[0]     A[1,0,0] = S[64]     A[4,0,0] = S[256]
A[0,0,1] = S[1]     A[1,0,1] = S[65]     A[4,0,1] = S[257]
A[0,0,2] = S[2]     A[1,0,2] = S[66]     A[4,0,2] = S[258]

A[0,0,61] = S[61]   A[1,0,61] = S[125]   A[4,0,61] = S[317]
A[0,0,62] = S[62]   A[1,0,62] = S[126]   A[4,0,62] = S[318]
A[0,0,63] = S[63]   A[1,0,63] = S[127]   A[4,0,63] = S[319]

and

A[0,1,0] = S[320]   A[1,1,0] = S[384]     A[4,1,0] = S[576]
A[0,1,1] = S[321]   A[1,1,1] = S[385]     A[4,1,1] = S[577]
A[0,1,2] = S[322]   A[1,1,2] = S[386]     A[4,1,2] = S[578]

A[0,1,61] = S[381]  A[1,1,61] = S[445]    A[4,1,61] = S[637]
A[0,1,62] = S[382]  A[1,1,62] = S[446]    A[4,1,62] = S[638]
A[0,1,63] = S[383]  A[1,1,63] = S[447]    A[4,1,63] = S[639]

If you look into the position of the bits. you notice that you can consider your state as an array of $\texttt{u_int64}$ (numbering $0 \to 63$, $64 \to 127, \ldots$), this explains the $w$ in the formula.

If you look at the ordering of the bits, you notice that we have the first plane ($y = 0$), then the second etc. Thus taking the 320 first bits select the first plane and so on.

Now if you look at the operations in Keccak:

$\iota$ operate on the lane $(0,0)$,
$\theta$ operates on column but depends on the parity of its neighbor columns,
$\pi$ and $\rho$ operates directly on the lane position
$\chi$ is applied to a row.

$\chi$ can also be seen as a 5-bits S-box that has been bit-sliced and to be applied $64$ times in parallel (see bellow).

We can thus select 320 bits and apply $\chi$ directly, the bits are grouped in such way that loading them consecutively will be fast (instead of fetching them at different positions). So we have a first reason to prefer this ordering.

Then we can have a look at $\theta$, it works mainly on columns but you can also consider doing it directly on planes (thus 320 times in parallel !).

Thus selecting the states by bloc of 320 bits and adding them from a vector point of view makes it fast.

We thus have here two operations ($\theta$ and $\chi$) which benefit greatly from the $w(5y+x)+z$ ordering.

Now if you assume the other ordering ($w(5x+y)+z$), notice that:

you have to fetch bits from 5 different position when you want to apply $\chi$.
you can only work on $\theta$ with a parallelism over the column and not the slate anymore.

TL;DR: $\chi$ and $\theta$ parallelism benefits a lot from this ordering (and also from a hardware point of view).


And in which case would it be more interesting to use one or another?

So SHA3-$n$ offers $n$ bits of security against preimage and second-preimage attacks and $n/2$ bits of security against collision attacks.
On the other side SHAKE-$n$ offers at $n$ bits of security against preimage and second-preimage attacks and also $n$ bits of security against collision attacks (assuming the digest is at least $2n$ bits long). So when to use which?

When you are forced to use "an approved hash function", you use SHA3, because SHAKE doesn't qualify.
When you need a really long hash output (or an XOF in general), you use SHAKE.
When you really need more than 256 bits of security against preimage or second-preimage attacks you use SHA3.
When you want to be compatible with more other systems, you probably want to use SHA3.
When speed matters to you (and you still want to use SHA3 / SHAKE) and you are happy with an all-arond $n$-bit security level (for $n\in\{128,256\}$), you use SHAKE.

This last point follows from the fact that the higher preimage resistance in SHA3 is paid for with lower rate (=number of new bits processed per internal permutation invocation) which is usually higher in SHAKE than in SHA3 (SHAKE256 has the same as SHA3-256).


DHKE
In an exponential Diffie-Hellman, denoted by DHKE, one takes a group $G$ with a generator $g$ with its order $n$.
The Alice and Bob, during the key exchange, generates random number $a$ and $b$ in the range $a,b\in (1,n)$ and transmits $g^a$ and $g^b$ and finally, they establish the key as $g^{ab}$ then use a KDF to derive a symmetric key and IV/nonce.
There is also Elliptic Curve version of DHKE and it is denoted by ECDH and it is more used than the classical exponential version.
Prime
In DHKE, we choose prime to be a safe prime, that is $p = 2 \cdot q + 1$ with $q$ is also a prime. The $q$ is called a Sophie Germain prime.
This is a countermeasure against Pohlig-Hellman algorithm that benefits from the small factor of the $p-1$. If a safe prime is used than the factors are $2$ and $q$. Having a large factor is a countermeasure against the Pohlig-Hellman.
There is also Schnorr group with $p = r\,q + 1$. This can be considered as a generalization of the sage primes. The sage prime is optimal.
Prime Generating
The naive approach generates a prime $q$ then check for the primality of $2 \, q +1$ (Menezes:  Algorithm 4.86). In pseudocode;
do
   p = randomPrime(k-bit integer)
while ((p − 1)/2 is composite)

There are faster methods

Double-Speed Safe Prime Generation by David Naccache, 2003
as the title suggests, this speed this up by about a factor of two by testing both $2q + 1$ and $(q − 1)/2$ for primality.
The idea is using the random prime $p$ as safe prime or Sophie Germain prime;
do
  p = randomPrime(k-bit integer)
while ((p − 1)/2 and 2p + 1 are composite)

Safe Prime Generation with a Combined Sieve by Michael J. Wiener, 2003.
They proposed sieving small primes up to $2^{16}$. This provides $15x$ speed up than the naive algorithm.
The idea starts with this observation; both $q$ and $q=2p+1$ must be congruent to $2$ modulo $3$. Therefore one can eliminate the candidates with which are $0$ modulo $3$ and $1$ modulo $3$.
This can be generalized to any odd prime $r$. Eliminate $q$'s that are conguruent to $(r-1)/2$ modulo $r$ since in this case $p$ is divisible $r$.
Take a set $S$ all odd prime $<B$. Then $\prod_{r\in S}(r-2)/r$ of the candidates will survive the sieve.
If $B=2^{16}$ it is estimated that it can produce $\approx \times 15$ speed up.

Collision
Now we will look at the probability of arriving the same random number if there are $k$ people using the same DHKE modulus. We are assuming that the $k$ people using the same secure (unpredictable) random number generator to generate their random keys. To simplify this, we can assume that there is one person who generates random numbers. In this case, this is completely the birthday-paradox and in Cryptography we look at this is the birthday attack to find a collision with 50%. This is a common way to look at the collision of the hash functions.
Let $H$ be the range of the random number generator, and the $p$ represents the probability we want, then $n(p; H)$ be the smallest number of values we have to choose;
$$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$$
In the classic hash collision case, we set $p=1/2$ and this approaches
$$n(0.5;H) \approx 1.1774 \sqrt H$$ and we usually represent as $\mathcal{O}(\sqrt{H})$
Now, let's look at some actual numbers.

2048-bit prime
Assume that $n$ is 2048-bit number, remember $n$ was the order of the generator $g$. Then
$$n(p;2^{2048})\approx \sqrt{2\cdot 2^{2048}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{2048})\approx 2^{1204}$$
As a result, you need to generate $2^{1204}$ random numbers to hit one again with 50%. Not feasible.

4096- bit prime
$$n(p;2^{4096})\approx \sqrt{2\cdot 2^{4096}\ln\frac{1}{1-p}}$$
With 50% probability $$n(0.5;2^{4096})\approx 2^{2048}$$
As a result, you need to generate $2^{2048}$ random numbers to hit one again with 50%. Not feasible.
Pre-Compute the dlog table.

Since the modulus are pre-determined by the standards, one can argue that some organizations with superpowers built some DLog table for the modulus.
This is not a danger, too. Let assume that they can build a table up to $2^{64}$ then the probability of your random hit is $$\frac{\ell \, 2^{64}}{2^{2048}}$$ with $\ell$ try. Put the possible key generation number of your group into $\ell$. So, 2048-bit is a really big number to deal with.


SSL/TLS is a secure protocol that encorporates the negotiation of cryptographic parameters for asymmetric and symmetric algorithms, integrity algorithms, and verification algorithms.  You can read more about this on How does TLS work?  You can find more information on the cipher suites used for negotiations in this answer.  The same API used for SSL/TLS is generally used for symmetric decryption/encryption.

Mozilla both use versions of the open source (MPL) NSS library for their SSL implementations.  Since it's open source there are differences between the two, but the guts should be the same.

Chrome used to use a version of NSS, and originally stated that they would switch to OpenSSL.  However, in the wake of various implementation vulnerabilities Google has decided to make their own clean version of OpenSSL called BoringSSL.

Internet Explorer is tied directly into Windows SChannel (Secure Channel) which is run and handled by Windows' LSASS process.  It would surprise me if Windows Edge didn't use this as well.  It uses WinHTTP, and is only available (for now) on Microsoft Windows platforms.


What does it mean when 1 bit goes into an s-box but two (or more) come out?

It's very simple.  You've just gotten the wrong end of the stick.  Yes, the s box is 4 bits wide.  That means it contains 2^4 lookup values as:-

So it can accept any input ranging from 0000 to 1111 in binary.  When we say one bit goes in, we mean an active bit.  This refers to the  bit representing input data to the cipher that's not a zero.  Think of the inputs to the s box as physical wires.  Not all wires carry information all the time, but there are 4 wires permanently attached to each s box.  For example, the value 0010 entering the s box is considered to be one active bit.  There's just one "1", no matter it's position in the nibble.  If 0010 goes in, 0110  comes out as per the PRESENT substitution above (2 → 6).  There are now two "1"s to propagate further.

The concept of the active bit is important, as the combination of s boxes and permutation layers means the active bits can appear, disappear and wildly change relative position.  In the above example, one active bit went in and two came out.  The wires return to their original positions in three rounds, but the active bits will be all over the place as they will have effectively jumped wires.  This is substitution and permutation leading to Shannon's confusion and diffusion.

There's an s box tag that will show you a huge list of related questions that might flesh out what I've written, as well as detail the nuances of a good s box.  Not all s boxes are created equal.


Is quantum key distribution safe against MITM attacks too?

No, Quantum Key Distribution is not any safer than conventional crypto is against an active Eve impersonating as Bob to Alice using the same equipment and knowledge as the rightful Bob (or/and impersonating as Alice to Bob using the same equipment and knowledge as the rightful Alice). Otherwise stated, QKD can resist Man Eve In The Middle only inasmuch as Eve lacks some initial shared secret known only to legitimate parties Alice and Bob (or there is an independent channel with known integrity, but that's impractical).

The best QKD claims to achieve is turn an authenticated channel (or a short shared secret) into a channel safe from any eavesdropping (or an arbitrarily longer shared secret), against any attack active or passive (including by MITM). E.g. Alice and Bob start from a shared secret of say 512 bits (that could be the conventional hash of a pass phrase), assumed unknown to Eve. Alice and Bob apply some protocol with photons and mirrors, plus some conventional operations¹ on bits for post-processing; and end up with some kilo bits (per second of experiment) of random secret material unknown to Eve. Alice and Bob can use that secret material to encipher data using a One Time Pad (perhaps while they are generating that secret material, so they need not store it).

Non-quantum cryptography routinely does the same (or better: the initial trusted data needs not be secret, e.g. Alice and Bob can exchange their public key; this makes it easier to safely use asymmetric non-quantum cryptography than it is to use QKD). However non-quantum cryptography relies on assumptions on the hardness of some problem, such as the discrete logarithm problem, or/and finding more plaintext/ciphertext pairs given examples for a blockcipher; whereas QKD, and more generally Quantum Cryptography, attempts to rely only on the laws of physics.

The security track record of QKD systems is poor: one security problem has been that imperfections of single-photon sources could be exploited; another rather spectacular one was active blinding; now I'm hearing of double blinding. QKD is not practicable with the current fiber infrastructure (quantum repeaters, if any, exist in labs only). Combine with the fact that QKD solves a problem that is already solved in practice, more conveniently, by classical cryptography, and many reach the conclusion that QKD is a marvelous accomplishment but pointless in practice, except perhaps as a justification for funneling out money.

Update: the need for an initial shared secret (or a channel trusted for integrity) is acknowledged in this whitepaper by ID Quantique², a supplier of KQD equipment:

  Key distillation is then complemented by an authentication step in order to prevent a “man in the middle attack”. In this case the eavesdropper would cut
  the communication channels and pretend to the emitter that he is the receiver and vice versa.
  Such an attack is prevented thanks to the use of a preestablished secret key in the emitter and the receiver, which is used to authenticate the communications on the classical channel. This initial secret key serves only
  to authenticate the first quantum cryptography session. After each session, part of the key produced is used to replace the previous authentication key.

¹ Despite the inevitable errors in the quantum communication, these conventional operations can be simple, secure, and robust: pick at most two attributes! Perhaps the most cited considered to reaching the later two is the cascade protocol in: Gilles Brassard and Louis Salvail's Secret-Key Reconciliation by Public Discussion, in proceedings of Eurocrypt 1993.

² Originally available there.


Don't even use the system RNG if you don't trust it but do trust K.

Use K to seed a secure PRNG; then generate keys from that RNG instead. (For example, ChaCha. Not RC4, because it's obsolete and insecure, but other secure stream ciphers work.)
Or use K with a key derivation function. If you don't need to follow standards then use HMAC with K for its key. Every time you need a symmetric key up to 512 bits long, increment a counter, HMAC the counter value, then take however many bits you need from the output.

Why?

You could encrypt the output of an RNG. Symmetric key encryption is supposed to produce ciphertext which is indistinguishable from a uniform random bit source. Encrypting a random or pseudorandom sequence isn't any better than encrypting some simple non-repeating sequence like a counter.

However, you could mess up the encryption by reusing nonces, using a block size that's too small, using a bad algorithm, or using a buggy implementation. I say don't use the system RNG if you don't trust it because encrypting its
output is at best equal to the alternatives I listed.

If your system RNG is biased or isn't seeded with enough entropy, then you have the problem of nonce reuse if you encrypt with a (not sufficiently) random IV. If you can prevent nonce reuse with a deterministic algorithm, then you can also prevent nonce reuse with secure PRNG or maintain a counter for the HMAC construct I mentioned.

You should be able to trust your operating system's secure RNG. But if you don't have access to one or you know it wasn't seeded with enough energy then that is reason to use something else.

You can't really make a better unpredictable non-deterministic RNG than what the OS can provide you. Userland attempts at entropy-gathering (non-deterministic) RNG algorithms don't have a good track record.

If you have a high entropy key, a secure algorithm, and ability to prevent nonce reuse, then PRNG/KDF output will be good.


Can combining two secure block ciphers be insecure?

It depends on what you mean by "a secure block cipher", but under a strong enough definition (which is thought to hold in practice), the answer is "no" for boring reasons. If we had some block cipher $F_k$ such that $F_{k}^{-1}$ was also a secure block cipher, then the composition:
$$(F_k\circ F_k^{-1})(x) = x$$
Would trivially not be a secure block cipher.
Therefore, if we want to justify this (contrived) counterexample, we would need $F_k$ being a secure block cipher to imply that $F_k^{-1}$ is as well.
This does not hold for the "standard" notion of security of block ciphers (distinguishing the PRP from random), but does hold if you also allow the adversary to query the "inverse" function.
Most block ciphers in practice are thought to satisfy this stronger definition, but this kind of insecure construction (composing a block cipher with its inverse) is a "dumb" attack on your idea, and relies on the two block ciphers ($F_k$ and $F_k^{-1}$) sharing a great deal of structure mathematically.


How to verify if g is a generator for p?

Steps:

Factor $p-1$, that is, find the primes which, multiplied together, produce $p-1$.  In your case, $2685735182215186 = 2 \times 1342867591107593$
For each prime factor $q$ of $p-1$, verify that $g^{(p-1)/q} \not\equiv 1\pmod p$

If every such $q$ verifies (that is, they were all not 1), then $g$ is a generator.


However, I couldn't find any information on how that sequence number is validated. What happens if some messages get dropped or corrupted during transit?

SSH, similar to TLS, assumes that it is running over a reliable [1] transport protocol (such as TCP).  If something goes wrong (e.g. some message is corrupted or dropped), then the system assumes that the system is under attack, and the connection is dropped.

This is explicitly stated in section 9.3.5 of RFC4251, which states:

This protocol is designed to be used over a reliable transport.  If
transmission errors or message manipulation occur, the connection is
closed.  The connection SHOULD be re-established if this occurs.

[1]: By reliable transport, I (as well as the RFC) mean that it delivers bytes correctly and in order, assuming that the system is not under attack.


Would a non-deterministic (read: randomized) compression algorithm be crypto-safe?

... a compression algorithm that randomly shifts stuff around ...

This is a contradiction in terms, surely? The extent to which any block of data can be compressed is directly related to the entropy of this data. The more predictable the data is, the lower its entropy and the more compressible it becomes.

If you apply random transformations to your data, you are increasing its entropy and making it less compressible. This defeats the purpose of your compression algorithm. Ultimately, you will end up with data that is indistinguishable from random noise, making it completely incompressible.


One-way function and uninvertible function

One-way in the context of cryptography is usually defined to mean that, given an element from the range of a function (or even a series of elements from the range), it is not possible in time polynomial in the input (or maybe output) size to identify the element(s) in the domain that yields the range element(s).  This is purely a bound on computational complexity.  I can absolutely identify every input for any deterministic encryption algorithm by simply exhaustively searching all possible inputs until the desired output is found.  It's only that that will take time($O(2^n))$) for $n$-bit inputs.

Uninvertible is usually defined as a mathematical property of a function which says that an inverse for each element of the range is not guaranteed to exist, or at least to uniquely exist.  For example, let $f(a,b)=a\wedge b$, and let $x$ be an output of $f$.  What are the values of $a,b$ that produced it?  They could be any of $(0,0), (0,1), (1,0)$  if $x=0$, so $f$ is not uniquely invertible.

My guess is that what you really want to show is something like this:  Let $f$ be some computable function and let $x=f(a)$ be the output of $f$ at some unique $a\in dom(f)$.  If $f$ is one-way (as defined above), then $a$ cannot be computed in time poly($|a|$) given only $x$.

This re-statement assumes definitions for what you mean by one-way and uninvertible.  But with that assumption, the proof is simple--just apply the definitions.  Intuitively, if you could compute $a$ from $x$ in polynomial time, then $f$ is not one-way by the definition.  More formally, suppose there exists a deterministic, polynomial-time algorithm $A$ such that $A(x)=a$ for all $x\in dom(f)$ and $f(a)=x$.  Then the pre-image of $x$ under $f$ can be computed in polynomial time, and so $f$ cannot be one-way.  This is a contradiction, so $A$ cannot exist.  qed.


How much work is required to find multiple collisions for a hash function?

The expected effort to find $k$ distinct collisions on an ideal hash function of output size  $n$ is about $\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$ (for $k << 2^{n/2}$).

One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is $2^{-n}$; if we generate outputs for $\sqrt{2k} \cdot 2^{n/2}$ distinct inputs, there are $(\sqrt{2k} \cdot 2^{n/2} \cdot (\sqrt{2k} \cdot 2^{n/2}-1))/2 \approx 2^nk $ pairs of outputs; if the collision probabilities are independent (which they approximately are if we stay $k << 2^{n/2}$), then the expected number of collisions we get in the set of outputs is $2^{-n} \cdot 2^nk = k$

Note that for $k=1$, we get about $\sqrt{2}\cdot 2^{n/2}$ expected outputs for a single collision.  That's not a contradiction to the $2^{n/2}$ rule of thumb; $\sqrt{2}\cdot 2^{n/2}$ is a slightly more precise value.


Yes.

For DES, it looks like the composition $T_i\circ T_j^{-1}\circ T_k$ is normally not a $T_l$ with another key $l$.

I do not have a proof of this fact.

So DES is not a pure system, and otherwise triple-DES would not more secure than DES itself.

In a comment, fgrieu linked a proof for a weaker fact, that DES is not a group (by Campbell and Wiener).

They actually did some experiments searching keys $i, j, k, l$ so that $(T_l \circ T_k \circ T_j \circ T_i)(\mathtt 0) = c$, with 50 different random values $c$ messages randomly selected from the full $2^{64}$ block set. They found such a set of keys for all 50 values $c$.

Since the set $K$ of DES keys has only size $2^{56}$, also the set $T_*(\mathtt 0) = \{T_m(\mathtt 0) \mid m\in K\}$ has at most size $2^{56}$. The probability that all 50 messages would be in this set $T_*(\mathtt 0)$ was estimated as $\leq (2^{-7})^{50} = 2^{-350}$. So very probably $(T_l \circ T_k \circ T_j \circ T_i)$ is usually not a $T_m$, i.e. the set of DES encryptions is not closed under composition.

The paper also provides some lower bounds on the size of the subgroup spanned from all the DES encryptions by calculating the cycle sizes of $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$ applied to various messages, which all must be factors of the order of the cyclic group spanned by $T_{\mathtt{1...1}} \circ T_{\mathtt{0...0}}$, which itself is a subgroup of the group spanned by all DES encryptions (and decryptions). The lowest common multiple they got was more than $10^{2499}$, much larger than the number of all DES keys (or even all triple DES keys).

What does this mean for our question?

DES (or any set of permutations $\{T_i \mid i \in K\}$) being a group (subgroup of the set of permutations) would include that for each key $i$ and $j$ the composition $T_i \circ T_j$ is a DES encryption $T_l$, and also each
decryption $T_j^{-1}$ is an encryption $T_m$. From that we could conclude that $T_i \circ T_j^{-1} \circ T_k$ is also a member of the group, i.e. that the set would be a pure set.

The reverse doesn't follow that easily, and neither is the proof directly applicable to our situation (both look at different corollaries from the group property).

I suppose one could do similar experiments as they did, search keys $i,j,k$ so that $(T_i \circ T_j^{-1} \circ T_k)(\mathtt 0) = c$ for random messages $c$ and argument similarly that this should give not as many matches as it does when that would be in $T_m$.

The other point of view is the practical one: If DES were pure, triple DES would be essentially the same as DES, and would be already broken by appliying a DES brute forcer on a triple-DES encrypted message. I can't believe nobody tried that yet.


When you are e.g. sending TLS encrypted data over a SSH tunnel, there are two things in particular that should be noted:

The TLS handshake will only commence, once the SSH connection has been established.
The bulk encryption keys of TLS will be completely independent of the SSH encryption keys.

Since the handshakes and keys are completely independent, there is normally no reason to worry about any bad interaction between the two layers. The TLS data is no different from any other kind of data, from the perspective of SSH. The SSH connection is no different from any other kind of serialized physical connection from the perspective of TLS.

That said, in some corner cases there might still be security issues with such combinations, but only if you e.g are using the same broken random generator for the pre master secrets, etc.

  I am curious as to how much more difficult a scenario like this would make it for an attacker to break the encryption (assuming they could somehow bruteforce 128/256-bit keys).

Most likely, not at all. If you picture yourself being targeted by an adversary with the ability to brute force 256 bit keys (which of course is not realistic), adding a second layer with 128 bit security will not increase the hardness in any significant way. This is (if not for any other reason) because the outer layer might be attacked separately. The TLS handshake is not encrypted, so a theoretical brute force attack on the SSH transport encryption will still only require a $2^{256}$ work factor.


What weaknesses would SHA256 hash array building and hashing the result have for password storage?

The question's construction is an attempt at making a memory-hard function. This is more difficult than it seems, and the construction proposed has several flaws:

An adversary performing a password dictionary attack needs only a little over half a megabyte of memory per concurrently running process. This is because adversaries are not bound to "put 31,250 copies of the first hash to fill the array"; they can take advantage of the fact that the last copy will not get changed (become different from the but last) until the last of the passes in the process. For large $n$, this allows running nearly $2n$ processes interleaved (that is, with their stages of progress evenly distributed at a given time) using only $n$ megabytes of memory.

Independently, an adversary can save about 1/16 of the hashing effort by noticing that typically, in the step reading "hash the entire array salted with the hash 8 times", the beginning of what's hashed (on average, 0.5 MB out of 8 MB) is identical to what it was in the previous step.

It is hard to rule out that an adversary using an ASIC (or perhaps FPGA) for a password dictionary attack can organize things so that some of the (half-)megabyte of memory needed per process can be in relatively slow/cheap memory such as off-die DRAM, and only very little in fast on-die static RAM or flip-flops.

In a SHA-256 internal block hash, a sizable part of the computational effort goes into the so-called expansion of the 64-byte message block. Because most of the data hashed by the overall algorithm is hashed many times and with the same alignment to 64-byte blocks, it is theoretically possible to cache expanded message blocks and save most of that expansion work. That's quite worthwhile when repeatedly hashing the same data block, which happens nearly half of the time due to flaw 1.

Flaw 1 can be fixed by adding an outer loop performed many times, so that during all except the first of these loops the 32-byte blocks of the memory array have different and arbitrary-like content. However, that exacerbates the risk that flaw 3 becomes serious, and/or that memory even slower/cheaper than DRAM becomes usable.
Flaw 2 can be fixed by incrementing the first word of the first block before starting each hash.
Flaw 3 is the theoretically hardest to repel. Using data-dependent addresses might help, but tends to slow down legitimate use too, and may introduce undesirable side channel leakage.
Flaw 4 becomes merely theoretical after flaw 1 has been fixed: exploiting it requires a lot of extra memory, so that's most likely not worthwhile in practice.

Memory hard functions are like most crypto: anyone, from the most clueless amateur to the best cryptographer, can create one they can't break (Bruce Schneier). Thus the prudent thing is to use the ones that passed scrutiny; or if the objective is learning, study that. The current recognized standard is Argon2. It's worth reading about Balloon, too.


Difference between the TLS cipher suites?

Ok so first thing, RSA is a signature  algorithm where DSS is a signature standard that currently uses the DSA algorithm with fixed parameters. For more details, see this great explanation.

So what we are actually comparing is RSA and DSA. The main difference is, that they rely on completely different hardness assumptions. I will try to explain them in a simplified manner as the underlying  math is very complex, so please forgive me some abstractions.

DSA (as ElGamal) relies on the  assumption that the discrete logarithm is hard in some special  (sub)groups, meaning in those groups dlog is believed to be computationally hard.
In contrast, RSA bases its security on the (assumed) hardness of factoring, meaning given only a large number N that is the product of 2 primes p and q, it is hard to compute p and q from N.

So in the unlikely case that researchers
find an effective factoring algorithm for example, RSA is broken but DSA is still fine. In contrast, if dlog is easy, DSA can not be used anymore and RSA is still secure.

Given that, it seems to be a good idea to have several algorithms which rely on different assumptions just for the case that one is not true.

I hope this gives you a rough idea of the conceptual difference of those two signature algorithms.


VKO GOST R 34.10-2001 (described in RFC4357), Key Agreement Algorithm. Looking for its implementation/detailed description/examples

You can start by reading:
https://github.com/openssl/openssl/blob/OpenSSL_1_0_2-stable/engines/ccgost/README.gost
It has examples on how to generate GOST certificates.

After that I would suggest running a test SSL/TLS connection with those certificates and openssl s_client and openssl s_server utilities. If it works, you may then recompile OpenSSL and make it dump all needed intermediate data during SSL handshake to stdout. You can then have as many reference examples as needed.

Also, have a look at
https://github.com/openssl/openssl/blob/c64879d3f3cc4c7f1c436a9fe3bd109847a23629/test/gost2814789test.c
to have an idea on how to call GOST algorithms from OpenSSL.


How to implement correctly an Integrated Encryption Scheme?

You have the right idea!  There's a very general construction for public-key encryption called KEM/DEM that works as follows to encrypt a message $m$:

Key encapsulation mechanism, KEM: Generate a key $k$ and an encapsulation $y$ using a public key.
Data encapsulation mechanism, DEM: Use $k$ to authenticate and encrypt $m$ giving an authenticated ciphertext $c$.
Transmit the encapsulation $y$ along with the ciphertext $c$.

The recipient, with the secret key, can recover $k$ from $y$ and then decrypt $c$.

For RSA, you can make a KEM as follows with a public key $n$:

Pick an integer $x$ between $0$ and $n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = H(x)$, where $H$ is (say) SHA-256.

The recipient uses secret knowledge of the solution $d$ to $3d \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ if $n = pq$, to recover $x = y^d \bmod n$, and then computes the same $k = H(x)$.

The security requirement for a DEM is modest.  An authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305, with nonce set to zero, will do just fine.  (I recommend AES-256 if you must use AES, to avoid multi-target attacks; I recommend crypto_secretbox_xsalsa20poly1305 over AES-GCM, to avoid side channel attacks on AES and GHASH in fast software implementations.)

ECIES is an example of the KEM/DEM structure—for a public key $A$ on an elliptic curve with standard base point $B$, you pick a scalar $t$ uniformly at random, compute $T = [t]B$, derive the key $k = H([t]A)$, and use $T$ as the encapsulation of the secret key $k$ which you use in an authenticated cipher to encrypt the message; the recipient knows the secret $a$ such that $A = [a]B$, and given $T$ recovers $H([a]T) = H([a\cdot t] B) = H([t\cdot a]B) = H([t]A) = k$ to decrypt the authenticated ciphertext.

You can also generate $k$ independently and shoe-horn it into an encapsulation like RSAES-OAEP.  But, while this is probably the most common way to do RSA encryption out of inertia, it is more complicated than necessary.


NAND is not the appropriate combiner for RSA malleability , and can causes the issue observed by making what's produced larger than the public modulus $N$.

RSA malleability applies to textbook RSA, where encryption goes $$x\to \text{Enc}_{(N,e)}(x)=x^e\bmod N$$ and malleability is the property $$\text{Enc}_{(N,e)}(x_1\cdot x_2\bmod N)=\text{Enc}_{(N,e)}(x_1)\cdot\text{Enc}_{(N,e)}(x_2)\bmod N$$ where $\cdot$ stands for integer multiplication (just nothing to do with NAND).

Verifying this with plaintext consisting of files with bytes containing 1 and 2 requires extracting $N$ from the public key, and large-integer arithmetic modulo $N$.


This question asked for the DES years ago. To achieve this kind of attack you need to first show that the target encryption algorithm is closed under functional composition i.e. forming a group.

The easiest might be is showing that it is not forming a group as in DES.

Although you may get one $K$ for only one block with the negiligible probability it will work for the other blocks.

Actually, we don't expect such property exists for good block ciphers. The keys, as you remember, select one permutation from all possible permutation randomly. What you are asking is a very specific cipher which is not random.

In short, It is not expected!.


How can the Diffie-Hellman key exchange be extended to three parties?

Alice computes $A=g^a$, Bob computes $B=g^b$ and Charlie computes $C=g^c$.
$A,B$ and $C$ are published.
Alice computes $AC=C^a$ and $AB=B^a$ and Bob computes $BC=C^b$.
$AB,AC$ and $BC$ are published.
Alice computes $ABC=BC^a$, Bob computes $ABC=AC^b$ and Charlie
computes $ABC=AB^c$.
Everybody shares $ABC=g^{abc}$.

This can be generalized for any number of participants in a tree construction, however it becomes increasingly inefficient, because the number of rounds increases.


AES process candidates implementations and usages

Well, not all of the AES-candidates have been considered good. In fact one of them even got broken at the presentation (within 20min!).

I'll list any (non-author) occurence of algoriths I'm aware of. Note: This list doesn't claim to be complete and may be extended by other people.

Now for a list of algorithms, for which I know there're an option

SAFER, well it's predecessor, SAFER-K and SAFER-SK are available at least in the Crypto++ library
CAST-256, available in the Crypto++ library
MARS, finalist, available in the Crypto++ library, because of the finalist status it may be an option in other programs
RC6, finalist, available in the Crypto++ library, available in Jetico's encryption tool, may be an option in other places as well as it's simpler than MARS and also has finalist status, according to wikipedia it was used pre-AES by the NSA. Furthermore usage of this algorithm can be costly as RSA Labratories seem to hold patents on it, as RC6 didn't win the AES-competition.
Serpent, finalist, 2nd place of the AES process, back then it was believed to be the most secure available candidate, adopted in Crypto++ and available in Jetico's tools and in TrueCrypt and it's derivatives (e.g. CipherShed and VeraCrypt).
Twofish, finalist, 3rd place of the AES process, back then it was approximiately as fast as Rijndael but it was believed to be more secure, adopted in Crypto++, TrueCrypt, by Jetico and in KeePass (1.x, 2.x as plug-in), and is part of the OpenPGP standard.


Does Composition of compressing Collision Resistant Hash Functions $H^{*}=H_2(H_1(x))$ is Collision Resistant?

Assume that, $H_1 \text{ and } H_2$ are collision resistant and $H^*$ is not. We will show that one of the $H_1 \text{ and } H_2$ can not be a collision resistant.

Let $x_1 \neq x_2$ be inputs such that $$H^*(x_1) = H^*(x_2).$$ $$H_2(H_1(x_1)) = H_2(H_1(x_2)).$$i.e we have a collision pair.

Now, if $H_1$ is collision resistant then $$y_1 = H_1(x_1) \neq H_1(x_2) = y_2 .$$

Note : The equality holds only with negligible probability, then $H_2(H_1(x_1)) = H_2(H_1(x_2))$ is a collision with a negligible probability.

Now, $H_2(y_1) = H_2(y_2)$ since $H^*$ is not collision resistant. But we found a collision for $H_2$ given a collision for $H^*$. This is a contradiction since $H_2$ is collision resistant therefore this implies that $H^*$ is collision resistant, too.


Logically I think that should also be a synchronous stream cipher. The word refers to the fact that the keystreams must be synchronized between the encrypter and the decrypter to allow decoding. With anything other than a self-synchronizing cipher that is the case.

However, that does not mesh with existing usage. You will find many texts (example) saying that with synchronous stream ciphers the keystream is independent of the plaintext and ciphertext. So you should definitely not use that term.

Asynchronous is not very good either, for the reason you mention, but you will find it used to describe such ciphers (e.g. Helix here, pdf). So that is probably more understandable than calling them synchronous, even if it too can be confusing.

If you need to write about it, I would avoid the issue and just call it a stream cipher with a plaintext-dependent keystream. You can say that it is not self-synchronous if you need to make that distinction.


Which of these 3 AES 128 symmetric encrypt/decrypt routines is most secure?

GCM mode is best, as it can not be attacked using padding oracle attacks, which are much more common than commonly thought. It is also the only one providing integrity protection, something that is certainly much overlooked.

Make really sure your NONCE is random though, or use one that is uniquely defined (even in time) within the database.

SquareRootOfTwentyThree makes a valid objection to say that the comparision should have been between GCM mode and symmetric ciphers + HMAC. There are several reasons why I would favor GCM mode over HMAC:

two separate/unrelated keys are needed for encryption and HMAC
you need to match the security of the hash in the HMAC with that for encryption
there is more room for error when using HMAC (provide a MAC over the wrong data)
you need to communicate two different algorithms to the other party
you need to check if HMAC is actually performed

This is opinionated as all can be made secure.

The last point about the HMAC check sounds obvious, but see what happened to XML encryption in WS-security where in most implementations the signature validation could be switched off, leading to padding oracle attacks. Creating a protocol that simply performs GCM mode has fewer points of failure.

Note that the drawback regarding the NONCE mentioned by CodesInChaos is a valid one. Unfortunately any of these algorithms is affected if the IV or NONCE is not used correctly.

GCM is started to be used by updates of several protocols (TLS, XML encryption) and has been approved by NIST.


Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?


Can AES-CBC be safely used in combination with RSA, or must it be CBC-MAC?

It depends on the system if RSA + CBC mode is secure. It could be but better options are available.

CBC mode, if correctly applied, can certainly provide confidentiality of the message. In that case however you must make sure that padding oracles and - more generically - plaintext oracles do not apply to CBC mode. If RSA with PKCS#1 v1.5 padding is used - often the default - then padding oracles may also apply to RSA (Bleichenbacher attack).

CBC mode doesn't supply integrity / authenticity of the plaintext message. Although an attacker cannot flip each individual bit (like with CTR mode), an attacker may still garble plaintext blocks by changing, moving or inserting/deleting  blocks of plaintext. Then again, as anybody with the public key can perform RSA encryption. So an attacker may as well generate a complete message and encrypt that. The addition of CBC-MAC or authenticated modes of encryption like GCM encryption won't help you achieve authenticity / integrity of the message.

If you want to achieve integrity / authenticity then it is recommended to first sign the message with a private key and then encrypt both using hybrid encryption. If you would not encrypt the signature then you would loose the anonymity property and you could leak the hash over the message. You would of course need a key pair generated by the sender for that, and the receiver should trust the public key of the sender.

CBC mode would still be vulnerable against padding oracles this way so although you could use it then you are better off using e.g. AES in counter mode (making sure that the IV is properly random or at least unique).

In the end I'd recommend something like RSA-OAEP (or RSA-KEM if you can find a good implementation) with CTR mode. If you need integrity and authenticity then perform RSA-PSS with a SHA-2 512 or SHA-3 512 bit hash and encrypt both the message and the signature.

Notes:

Performing encrypt-then-sign - where the ciphertext is signed - is more dangerous as anybody could replace the signature. This is a problem if the keys of the attacker are trusted by the system.
Your security parameters aren't all that well balanced; RSA-2048 has a strength of about 112 bits (according to NIST, 2017). Using that with AES-256 with a strength of 256 bits is fooling yourself. I'd use a combination of AES-128 with a 3072 bits key or use AES256 and a much higher key size such as 8192 bits or beyond. If you want optimal security you could think of switching to Elliptic Curves or an asymmetric encryption algorithm that delivers post quantum cryptography.


System parameters in identity-based encryption

The pairing description (type, q, h, r, etc.) is the definition of the field that the elliptic curve of some type operates on. The actual curve is identified by its type and is baked into the framework (e.g. PBC) you're using.

This definition corresponds to $q$ (group order, same as q), $\mathbb{G}, \mathbb{G}_T$ (groups defined by pairing description and curve) and $\hat{e}$ (pairing function $\hat{e}:\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$). $\hat{e}$ greatly depends on the actual elliptic curve, because different algorithms or parameters are used. All the other parameters are unique to the scheme that is devised using bilinear pairing.

The pairing description is necessary to have for doing any calculation with the described scheme. It must be known to all participants. Of course, if you're always using the same pairing description, you don't have to send it along with every message of your system. It can be baked into the client software.

Remember to generate a fresh and valid pairing description before you deploy your system into production. This makes it a little harder for attackers to break a system. If every one uses the same defaults, then pre-computation on that single group can break a lot of systems.


Decrypting a blowfish cipher with three keys

The encryption is EDE with Blowfish CBC. To decode the cryptotext ct reverse the encrytion, ie do

CBC_Decrypt(key3, iv3, ct, t3)
CBC_Encrypt(key2, iv2, t3, t2)
CBC_Decrypt(key1, iv1, t2, pt)

After this the plaintext pt will start with:

El truco estaba en desencriptar utilizando el metodo 3DES pero con distintos algoritmos de encripcion. Aunque usualmente se utiliza 3 veces DES, es posible utilizar 3 algoritmos distintos con el metodo de 3DES ....


HKDF on output key material of previous HKDF

It's not necessarily unsafe to create keys that way, but:

the x-coordinates of the public key are already used for calculating Z, so I don't see why inclusion in the KDF makes any difference;
without the x-coordinates, you may as well use HKDF-extract only to derive key0;
key2 is now derived from key1, while it is better to derive them both from key0.

As for point 3, there is no need for the security of key2 to rely on both key0 and key1.

Generally KDF's are interchangeable and even less well studied ones commonly use one-way functions such as hash algorithms with well distributed pseudo random output. However, HKDF comes with 2 advantages:

a more rigorous security proof and;
a split between extract and expand.

It would make sense to use it for those reasons.


Does this scheme break under a DHP adversary?

Now I want to know if we have a passive adversary Eve who is able to
  solve the Diffie-Hellman Problem, gain access to $(u,v,w)$, can she get
  back $m$.

Yes. But first you may want to note that this is the classic three-pass protocol, also called Shamir 3-pass protocol or Massey-Omura protocol which has been shown by Sakurai and Shizuya in 1998 to (sorry for the paywall) in general require a stronger assumption than (C/D)DH for security.

But now for the attack, which is directly derived from the above security relation result. First note that $u=m^a,w=m^b,v=m^{ab}$ and that $p$ is known. So now suppose that you have an oracle $\mathcal O$ that given $(g^a,g^b,g,p)$ returns $g^{ab}$ that is a classic Computational Diffie-Hellman (DDH) Oracle. Now for a second, call $v=g$ and note that $u=g^{b^{-1}}$ and $w=g^{a^{-1}}$. Now feed $(u,w,v,p)$ to the oracle and get $g^{a^{-1}b^{-1}}=(m^{ab})^{a^{-1}b^{-1}}=m$ back.

If you "only" have a Decisional Diffie-Hellman (DDH) oracle, note that you can still guess a message $m$, that is guess the return value of the above CDH oracle if there are only a few possible messages (not excluded in general in cryptography) and thus confirm your guess.


Did a certain cryptography method get abandoned due to security flaws in the past?

You could be thinking about the Merkle-Hellman knapsack cryptosystem. It was invented in 1978 and everything seemed well and good until it was completely broken six years later in 1984 by Shamir - it was a complete and total break, i.e. the cryptosystem became unusable overnight.

That said I don't know if the knapsack cryptosystem was ever "popular" in the modern sense (it was 1978 after all) but it was certainly an early public key cryptosystem that met an unfortunate end.

On the other hand, for an example of a progressively worn-down algorithm (as opposed to one being broken immediately) there is of course MD5's collision resistance.


You can prove that a document was signed after a certain date by including data that was not known to anyone before that date, such as stock market data.

You cannot prove that a document was signed before a certain date by purely cryptographic means. Information doesn't go stale, so when you show a signature, it could have been signed at any time.

You can prove that a document was signed before a certain date by non-cryptographic means. Showing the signed document to someone (a trusted third party) is an easy way to do that: if you trust that entity to vouch for having seen the signature at a certain date, then the signature has to be older. The third party doesn't need to see the document, only its signature (containing a hash of the document); if you need to prove that the document was signed, you can reveal the document later.

None of this is what you need, though. You would like to prove that a document was not signed before a certain date — the date when your private key was stolen. The thief could create a signature and pretend that the signature had been made a long time ago (but they will of course not be able to prove it: it would be your word against his).

One way to accomplish what you want is to require that any valid signature be “notarized”: the recipient must be instructed never to trust your signature alone as genuine, only your signature validated by a trusted third party (the notary), which would demonstrate the existence of the signature at the date it was seed by the notary.


Question on the disprove of CCA security

When the oracle gets $(r,s')$ this means that it gets $m'  =  0\mathbin\|1^{n−1}$ or $m' = 1\mathbin\|0^{n−1}$ because the oracle sent the adverary either the encryption of $m_0$ or $m_1$ that is $(r,s)$.
$0\mathbin\|0^{n−1}$ or $1\mathbin\|1^{n−1}$ is not the case since the bit flipping doesn't affect the $F$. The oracle will get $(r,s')$ then it will calculate $F(k,r)$, then the stream will be x-ored with $s'$. If we represent the bits by sub-indexes
$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{s'_0},F(k,r)_1 \oplus s'_1, \ldots, F(k,r)_{n-1} \oplus s'_{n-1}\right]$$ then we have
$$F(k,r) \oplus s' = \left[F(k,r)_0 \oplus \color{red}{\overline{s_0}},F(k,r)_1 \oplus s_1, \ldots, F(k,r)_{n-1} \oplus s_{n-1}\right]$$
As we can see, only one position has affected, the first position.


Is it possible to find plaintext from ciphertext if (n) and (a) are known for RSA?

For small numbers the easiest ways to break RSA are:

Brute force the private (decryption) exponent. I.e. find the smallest value $b$ such that $(x^a)^b \mod n = x$ for all $x$.
Factorize the modulus (trial division is simplest and works fine for small numbers), then use the factors to generate the private exponent.

Assuming you are supposed to use the maths, 2. is probably expected.


Key Distribution. Key distribution is, well, the process of distributing (cryptographic) keys to different parties. Usually this involves mechanisms which are considered "out-of-band", i.e. mechanisms that don't use the later communication channel for the transport of keys. Alternatively key distribution can be done by relying the distribution of new keys upon the safe distribution of old keys, that's what a KDC is doing.

Key management. Key management is, well, the process of managing (cryptographic) keys, the usual meaning implies management over the whole lifetime of the key. Key distribution is a part of key management, but it also includes key generation, key escrow (for backup purposes), key deletion, key revokation, key usage and key trust management. If you want to learn more about key management, the Handbook of Applied Cryptography has an entire chapter devoted to it (PDF).


This is
a) no attack on the security model, but an attack in the security model of EUF-CMA, and
b) a generic attack on any signature scheme that signs the hash of a message instead of the message itself (as done in RSA-FDH).

The idea is that if you can find a collision for the used hash function $H$, i.e., two messages $m_1, m_2$ such that $H(m_1) = H(m_2)$, then they have the same signature: $\sigma = \textrm{sign}(sk,m_1) = \textrm{sign}(sk,m_2)$.
To see this consider RSA-FDH as example: The signature on $m_1$ is $\textrm{sign}(sk,m_1) = (H(m_1))^d \mod N$ for private exponent $d$ and modulo $N$. The signature on $m_2$ is $\textrm{sign}(sk,m_2) = (H(m_2))^d \mod N = (H(m_1))^d \mod N = \textrm{sign}(sk,m_1),$ where the mid equality follows from $m_1,m_2$ being a collision.

In the EUF-CMA setting you are allowed to ask for signatures on arbitrary messages and have to come up with a signature on a new message. So given collision $m_1,m_2$, you ask for a signature $\sigma$ on $m_1$ and then output the pair $(m_2, \sigma)$ as forgery.