Perfect secrecy, in the sense defined by Shannon, means that observing the ciphertext does not allow an attacker (who has no knowledge of the key) to learn any new information about the plaintext beyond what they already possess.

(Note that there are no restrictions on what the attacker may already know about the plaintext; for example, they might already know that the plaintext is one of two specific messages, and just want to know which one.  Also, for technical reasons, we generally assume that there's an upper bound on the length of the plaintext, and that this upper bound is public information, i.e. already known to the attacker.  This is because no cipher capable of encrypting arbitrarily long messages can perfectly hide their length.)

Importantly, unlike more modern computational definitions of security (such as semantic security), the definition of perfect secrecy does not assume anything about the amount of computing power available to the attacker.  Thus, for example, the attacker is free to generate any number of candidate keys and to try to decrypt the ciphertext with each of them.

Based on this, it's easy to show that no cipher can possibly provide perfect secrecy unless the number of possible keys is at least as large as the number of possible plaintexts.  If there are $k$ possible keys and $n$ possible plaintexts, then the attacker (who, in this case, is assumed to know nothing about the plaintext in advance except that it's one of the $n$ possibilities) can simply try to decrypt the ciphertext with each of the $k$ keys, and thus obtain (up to) $k$ distinct decrypted messages.  If $k < n$, the attacker has thereby just learned something about the plaintext: namely that it's not one of the $n - k$ possible messages that the ciphertext did not decrypt to using any of the keys.

(We can also extend the same result into a proof that no cipher can provide perfect secrecy if the same key is used to encrypt multiple message, unless the key is at least as long as the combined length of all the messages.)

A block cipher like AES normally has a fixed key length (e.g. 128 bits for AES-128, or 256 bits for AES-256).  While in principle a block cipher like AES could provide perfect secrecy if the messages were no longer than the key, and if each key was only used to encrypt one message, in practice an encryption scheme capable of only encrypting up to 256 bits of plaintext per key would be pretty useless.

Thus, normally, AES is used with a mode of operation that allows it to be used to encrypt multiple messages of (more or less) arbitrary length.  Such modes of operation make AES into a practical general-purpose encryption scheme — but, as an inevitable side effect of allowing longer and/or more messages to be encrypted with the same key, the resulting encryption scheme cannot possibly provide perfect secrecy.

(Fortunately, they do still provide provable practical security against computationally limited real-world attackers who cannot just test every 256 bit AES key by brute force — something which appears to be safely beyond the reach of mankind.)


Are there secure stream ciphers that cannot be parallelized?

As Thomas notes, most stream ciphers cannot be parallelized (in the sense that generating a single keystream would be significantly faster with multiple processors than with one) or randomly accessed (in the sense that the mimimum time needed to compute the $k$-th bit of the keystream would be sub-linear in $k$).

Examples of stream ciphers that cannot be parallelized include:

As far as I know, ther's no known way to parallelize the RC4 stream cipher in any useful way.
Block ciphers used in OFB mode are not parallelizable, except insofar as the underlying block cipher itself can be parallelized.  I suspect it might even be possible to prove this, given suitable indistinguishability assumptions on the block cipher, although I'm not personally aware of such a proof.

Nonetheless, some stream ciphers do exist which can be parallelized or even randomly accessed.  Particularly notable among these is the CTR mode of operation, which turns a block cipher into a randomly accessible (and thus also fully parallelizable) stream cipher.

Some modern stream ciphers are also designed to exhibit at least a limited degree of parallelizability in hardware.  For example, the Trivium stream cipher is designed so that it can be used to generate anywhere from one up to 64 bits in parallel.  However, any reasonable software implementation of Trivium would already exploit this parallellism to a high degree by operating on 32- or 64-bit blocks of data, so, for all practical purposes, Trivium in software is not (further) parallelizable.

More generally, eseentially all synchronous stream ciphers (including all those mentioned above) may be written in the following form:

$$\begin{aligned}
x_0 &= i \\
x_n &= f(x_{n-1}) &\forall n \in \{1,2,3,\dotsc\} \\
o_n &= g(x_n) &\forall n \in \{1,2,3,\dotsc\}
\end{aligned}$$

where

$i$ is the initial state of the cipher (derived based on, and possibly including, the key as well as any IVs, tweaks, etc.),
$x_n$ denotes the internal state of the cipher at step $n$,
$o_n$ is the keystream output at step $n$,
$f$ is the function that updates the internal state at each step, and
$g$ is the function used to map the internal state into the output.

For most stream ciphers, which are not efficiently parallelizable, the cryptographic strength comes from the internal update function $f$, while the output function $g$ is fairly trivial (typically just extracting some part of the internal state).
On the other hand, to allow random access into the keystream (as with CTR mode), the update function $f$ must be trivial (for CTR mode, just incrementing a counter by one), so that $x_n$ can be quickly computed from $x_0$ for any $n$, while the cryptographic strength must come solely from the function $g$ (which, for CTR mode, is the underlying block cipher).

One reason why the random access type of stream cipher design is not more widely used is that relying on $g$ instead of $f$ for strength puts much harder demands on it: the fact that $f$ is iteratively applied to its own output allows its strength to build up gradually over many steps, whereas any security coming from $g$ must come from just one single application of it.  Most of the update functions $f$ used in traditional stream ciphers like RC4 would be hopelessly insecure if used as $g$ with a trivial $f$.

(Also, if you do manage to design a function that can be used securely as $g$ with a trivial $f$, what you have is basically a secure block cipher or something very close to one.  So, in that sense, the CTR mode construction is the generic random access stream cipher, with any other random access stream cipher being essentially the same thing with just cosmetic differences.)

However, I should note that there's another kind of parallelism which may be more relevant: if an attacker wants to crack the cipher by brute force, he will typically do so by generating multiple keystreams from different keys and seeing which of them yields a meaningful decryption.  In that case, even if the generation of a single keystream is not parallelizable, the attacker can just take multiple processors (or, say, cores in a GPGPU) and set each of them to generate a different keystream.

This kind of parallelism is quite hard to avoid, since, fundamentally, the generation of many independent keystreams is an embarrassingly parallel task regardless of how each individual keystream is generated.  One way to try to slow down such attacks is to make the keystream generation (or other computation) require a lot of memory, on the basis that, with current technology, it's a lot cheaper to build a lot of simple parallel processors than to provide each of them with a large amount of memory to work with.

One example of such a design is the scrypt key derivation function, which is designed to use an adjustable amount of random access memory in an essential way, such that, hopefully, any attempts to compute the function using significantly less memory would only be possible at the expense of a prohibitive increase in computation time.

In fact, reading the scrypt paper, what the ROMix construction used in scrypt does is to first use a non-random-access stream cipher (actually, an iterated hash function) to construct a large (pseudo)random lookup table, and then to use that lookup table to perturb the state of the stream cipher while generating the actual keystream (the end of which, in ROMix, is then taken as the output).  It certainly seems feasible to apply a similar construction to actual stream ciphers, although there are various subtle details, as noted in the scrypt paper, to consider.


Is the IEEE 1363.1 standard of NTRU post-quantum secure?

what are the major differences between the IEEE 1363.1 NTRU standard vs. the NTRUEncrypt NIST PQ submission

The only differences would be the parameters that are standardized. This answer gives one parameter set, specifically EES1087EP2. Unfortunately, the IEEE Std 1363.1-2008 document itself is behind a paywall, so I am unable to view the other parameter sets. It seems like at least some of the parameters are the same. In particular, NTRU-743 from the design document submitted to NIST has $N = 743, q = 2048, p = 3, d = 247$ (see table 1), which is the same parameter set as one standardized in 1363.1, according to an analysis of parameter sets (see table 3).

On the upside, there are public implementations which use the standardized parameters, so those can be consulted. It looks like the version of NTRU submitted to the competition comes with only a few parameter sets for evaluation, which may change later on in the contest. The IEEE, on the other hand, standardizes a large number of parameter sets for NTRU.

  Is there a difference in the parameter sets to enable PQ security vs. the parameters in IEEE 1363.1?

The parameter sets are chosen to maximize security, not to maximize post-quantum security in particular. Secure parameters will be secure against both classic and quantum algorithms. I do not believe you can construct parameters for NTRU that are secure against classical computers, but insecure against hypothetical cryptoanalytic quantum computers.

Table 5 in the above-linked design document compares the lattice strength for various parameter sets under the best known classical and quantum sieving algorithms.

  Is it correct to claim that the IEEE 1363.1 is PQ secure as well?

Yes. All unbroken versions of NTRU use lattice-based cryptography, which involves mathematical problems that are not known to be solvable using a quantum computer. If the IEEE version is PQ secure, then the NIST PQ submission should be as well, and vice versa.


How to calculate $v_k(s)$ in Quadratic Arithmetic Program?

The canonical algorithm to construct the QAP polynomials from an arithmetic circuit does not yield a polynomial in the standard form ($a_0 + a_1x + \dots$), but as a set of $(x,f(x))$ points. In order to compute $f(s)$ for arbitrary $s$, as required by the protocol, you have to run some interpolation algorithm to reconstruct the polynomial from all the points. (This is indeed one of the major flaws of Pinocchio, because interpolation is a very expensive operation and takes most of the execution time, even though it is not a crypto operation.)


OpenVPN uses two different protocols. For the standard and most common settings, a TLS link called the control channel is used to exchange a symmetric key. This symmetric key is then used to encrypt a second protocol, the data channel, which uses the OpenVPN protocol itself. The protocol is not identical to IPSec, but it is based off of IPSec ESP, a protocol for secure transport of data over the UDP protocol, which plain TLS cannot do (at the time the protocol was created, DTLS, which is TLS over UDP, did not yet exist). Note that this means that you may be using multiple ciphers for encryption. You may find the control channel using AES to exchange a key that will be used to encrypt the data channel with Blowfish.

Using the control channel with TLS is not the only way to key the data channel. You can also configure OpenVPN to use preshared static keys which will directly be used to derive the symmetric key for data channel encryption. This loses forward secrecy, but gets around the need to use the control channel to exchange a key using TLS.


What is the reason for length differences in RSA?

Three reasons:

Technical: often the integrity and origin of a piece of data becomes immaterial after the data is acted upon; and for long-term use (e.g. document signing), if the security of the signature becomes questionable, there is often the option to stop considering the key valid, and make a new signature with a larger key size, restoring security. When for encryption (one of the common goal of key establishment), we can't make the ciphertext disappear from the adversary's archive. Therefore, at any given time, we arguably need less security margin (smaller RSA modulus) for signature than for key establishment targeting long-term confidentiality.
Scope: my reading of NIST's FIPS 186 standard is that it specifies modulus sizes mostly for interoperability purposes, with security level not in the core scope; when NIST SP 800-56B is a recommendation with security level in scope. At least, only the later includes comparison with symmetric cryptography key sizes.
Historical: FIPS 186-4 (July 2013) is a standard with a long history, with RSA included in FIPS 186-1 (December 1998) which as RSA is concerned essentially approved a subset of ANS X9.31, with minimal key size set to 1024-bit for both; that size then made a lot of sense. When NIST SP 800-56Br1 is more recent (September 2014), revising earlier NIST SP 800-56B (August 2009) which still allowed 1024-bit RSA.


The access structure itself need not be non-empty, so the universe doesn't have to be in the structure. Of course, any non-empty access structure will have $\{1,2,\dots,n\}$ as an element.

In the context of ABE, it suffices to consider monotone access structures if the scheme supports an expressive policy set, because any subset $\mathbb{B}$ of $2^{\{1,2,\dots,n\}}$ (i.e., any not necessarily monotone access structure of universe $\{1,2,\dots,n\}$) can be encoded as a monotone access structure $\mathbb{A}$ of the universe $\{\pm1,\pm2,\dots,\pm n\}$ as follows:
$$\begin{aligned}\mathbb{A}'&{}=\Bigl\{{\{i\,|\,i\in X\}\cup\{-j\,|\,j\notin X\}}\,\Big|\,X\in\mathbb{B}\Bigr\},\\\mathbb{A}&{}=\Bigl\{A\,\Big|\,\mathbb{A}'\ni A'\subseteq A\subseteq\{\pm1,\pm 2,\dots,\pm n\}\Bigr\}.\end{aligned}$$
In English, this means you prepare positive/negative literals for every member of $\{1,2,\dots,n\}$, then encode any subset of it by explicitly putting negative literals for non-members into it, which gives you $\mathbb{A}'$. Then you take the smallest monotone access structure $\mathbb{A}$ containing $\mathbb{A}'$.

Monotone access structure gives rise to secret-sharing schemes, which are an important ingredient in many ABE constructions. Note that secret-sharing schemes can only handle monotone access structures, because gaining more shares only makes reconstruction easier.


How to compute the dataset size required by dieharder tests?

I'll be so bold as to say that no one knows for sure how much data you really need. There is no guidance on the homepage, the manpage and this thread from Duke is equally unspecific. Anecdotal evidence suggests that a 'few' GB will return a sane PASS/FAIL answer, but there will still be rewinds. For a 4 GB /dev/urandom test:-
...snip
# The file file_input_raw was rewound 43 times
      rgb_lagged_sum|  27|   1000000|     100|0.75608263|  PASSED
# The file file_input_raw was rewound 46 times
      rgb_lagged_sum|  28|   1000000|     100|0.88574962|  PASSED
# The file file_input_raw was rewound 49 times
      rgb_lagged_sum|  29|   1000000|     100|0.69532845|  PASSED
# The file file_input_raw was rewound 52 times
      rgb_lagged_sum|  30|   1000000|     100|0.93874399|  PASSED
# The file file_input_raw was rewound 55 times
      rgb_lagged_sum|  31|   1000000|     100|0.59282678|  PASSED
# The file file_input_raw was rewound 58 times
      rgb_lagged_sum|  32|   1000000|     100|0.88988310|  PASSED

58 times!
In your case (input file), a rewind is just that; start again from the beginning. Eight rewinds is good. I've seen 1849 rewinds. Honestly I can't understand the reasoning behind that, as all it does is retest what's been tested. All we know for certain is that Dieharder uses a lot. Your paper and my research shows that a free run of Dieharder (with no rewinds) needs approximately 225 - 250 GB! Notice that $58 \times 4 \text{GB}= 232 \text{GB}$.
There are other tests though. A more common test in the TRNG scientific literature is NIST's Statistical Test Suite, (SP 800-22). It's sample requirements are much more predictable.
And now a warning. You have to resist manipulating any randomness tests in order to get a PASS. Tweaking test parameters or selectively choosing individual tests to produce your expected result is dangerous, as a random sample is random no matter how you test it. From the manpage:-

...where a file that is too small will "rewind" and render the test results where a rewind occurs suspect.

My version 3.31.1 will not allow the number of p samples to be changed via the -p switch.


I'm unsure about the proper steps to store the e-mail password on the user's computer.

There are two ways I would recommend (in tandem if possible).

First, some SMTP servers (like Google) allow you to create an Application Password.  This password has limited access (for instance just for email) and can't be used to change the users password.

Secondly, use .Net's built in capability to encrypt the web.config/app.config.  The nice part here is that the configuration sections can just be read by your application, it doesn't know they are encrypted or not, .Net takes care of it for you.

  This may have been a bit unclear from the above, but I want to allow some person, for which I set up an Outlook account, to send mails to other persons

If the application is sending an email from the computer Outlook is installed on, you may want to consider How to open Outlook new mail window.


If the adversary takes $x, y \in \{0, 1\}^n$ such that $(0 \parallel x) = (y \parallel 1)$ then

$$G_K(x) = F_K(0 \parallel x) \parallel F_K(x \parallel 1)$$
$$G_K(y) = F_K(0 \parallel y) \parallel F_K(y \parallel 1) = F_K(0 \parallel y) \parallel F_K(0 \parallel x)$$

The left half of $G_K(x)$ is equal to the right half of $G_K(y)$, which lets the adversary distinguish $G$ from a random function.


How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model?

Particularly, if the probability over $Gen$ that there exists some $r_2, r_2'$ with $Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$ is negligible, then this almost works.

Actually, if the public key $pk$ is a valid public key (that is, corresponds to an actual secret key), the probability is 0.

Here's why: we have $Dec(sk, Enc(pk, x, r)) = x$ for all $x, r$.  Hence, $Dec(sk, Enc(pk, b, r_2)) = b \ne Dec(sk, Enc(pk, 1-b, r_2')) = 1-b$, and so $Enc(pk, b, r_2) \ne Enc(pk, 1-b, r_2')$

On the other hand, this still leaves open the question of "what if the committer were to pick an invalid public key (which does allow collisions)", for example, RSA with $e$ not being relatively prime to $(p-1)(q-1)$.

Hence, if we were to use this commitment scheme, we would reveal $r_g$ as well; this allows the verifier to construct the public key for himself (and verify that the $pk$ in the commitment was done honestly).


As for your first question "is the S-box indistinguishable from a random permutation?", well, there are likely some subtle biases.  For one, we know that, after exactly 4096 steps, the combination $j=1$ and $SBox[1] = 1$ is impossible; that's because $i=0$ after 4096 steps, and the combination $j=i+1$ and $SBox[j]=1$ is known to be impossible (given the standard RC4 key setup; this was first observed by Hal Finney).  Because of this, there is likely a bias away from $SBox[1] = 1$ after exactly 4096 steps, and so this would appear likely to be a distinguisher (albeit not a strong one) from a random permutation.

As for your second question "are the bytes generated indistinguishable from random data?", the answer for that is "definitely not".  We know how to distinguish a roughly Gigabyte output of RC4 from a random stream; see this paper for the details; note that discarding an arbitrary amount of RC4 keystream before you start sampling does not affect this attack.


Is it possible to derive related signature?

Here is one idea about how to do a signature that specifies a specific range (and which makes it easy to enlarge the range):

We will assume a bounded range for the 'age', say, 0 to 150 ($max$), and we assume that $\text{H}$ is a preimage-resistant hash function, and $\text{H}^k$ denotes $\text{H}$ iterated $k$ times.

Then, we have a signature that has several parts:

The values $MinAge, MaxAge$
The value $max = \text{H}^{MaxAge}( r_1 )$
The value $min = \text{H}^{max-MinAge}( r_2 )$
The values $\text{H}^{max}( r_1 ), \text{H}^{max}( r_2 )$
The signature for $\text{H}^{max}( r_1 ), \text{H}^{max}{r_2}$, and the rest of the clause (name: John).

The above signature states that John's age is between MinAge and MaxAge; the original signer (who knows the age) can generate a signature with $MinAge = MaxAge = \text{John's real age}$

This signature can be verified by verifying that $\text{H}^{max - MaxAge}(max)$ matches the $\text{H}^{max}(r_1)$ value, that $\text{H}^{MinAge}(min)$ matches the $\text{H}^{max}(r_2)$ value, and that the signature verifies.

The range that this signature denotes can be enlarged; the MaxAge can be increased to $MaxAge'$ by updating the value $MaxAge$ and replacing the value $max$ by $\text{H}^{MaxAge' - MaxAge}(max)$.  Similarly, the MinAge can be decreased to $MinAge'$ updating the value $MinAge$ and replacing the value $min$ by $\text{H}^{MinAge - MinAge'}(min)$.  Note that the range cannot be decreased, because that would require generating a preimage of $\text{H}$, which we assume is infeasible.


Out of the $10001$ possible outputs

$7295$ occur with a probability exactly equal to $429497$ in $2^{32}$.
$2705$ occur with a probability exactly equal to $429496$ in $2^{32}$.
One value, specifically the value ten thousand, occurs with probability exactly equal to $1$ in $2^{32}$.

The mean value of the distribution is approximately $4999.5$. It is approximately a uniform distribution over the range $[0, 9999]$. It is much more uniform than a real-world fair die roll's distribution, but it's also a huge bias in the world of cryptography.

It's not a bias large enough to discourage gamblers. Cryptographers aren't going to be inclined to gamble even for more fair odds based only on the odds and payouts (A lot like the story/rumor about physicists' conferences being unwelcome in Vegas. However that's not to say mathematically minded people might still be irrational or find other reasons for playing.)

Ignoring the value $10000$, each of the $7295$ over-represented values deviates from its expected probability by a factor of $1.0000006298$ and each of the other $2705$ values deviates by a factor of $0.9999983015$.

The multiplication method (using exact math, floating-point arithmetic is not necessarily exact) of transforming one uniform distribution to another uniform distribution over a smaller range has the same amount of bias as the naive division-remainder (without rejection sampling) method that people warn programmers not to use. The bias for the multiplication method, however, is more subtle because it doesn't lead to the over-represented elements all being low elements.

For this specific distribution $0$, $1$, and $2$ are all slightly over-represented. $3$ is slightly under-represented. $4$, $5$, $6$ over-represented, $7$ under-represented, $8$, $9$, $10$ over-represented, $11$ and $12$ over-represented, $13$ under-represented. I think most (or all) of the over-represented elements occur in runs of two or three. And the under-represented in runs of one.

As for the protocol you described, I can't say much about the specifics because you aren't precise in your description.

I can say that the output of algorithms like SHA-512, and by extension HMAC-SHA-512, can safely by treated as a uniform distribution of all 512-bit long bit-strings. Hash functions are often modeled as a random oracle. Wikipedia describes it as:

  In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted.

The hash output can begin with 00000000 or FFFFFFFF or any other 32-bit value. In fact, every possible prefix of a given length $n$ is expected to occur each with the probability $2^{-n}$.

It is possible to create a fair shared random value between multiple parties using hash functions. Two parties choose a random secret number, exchange those numbers between each other simultaneously (so no one can cheat by changing their number), and create a new agreed-upon shared random value by hashing the two secrets. (They obviously need to agree on the order they hash each number.)

A commitment scheme is used to prevent parties from changing their secret number after observing the other player's number. They send each other hashes of their own secrets. They don't reveal to each other the actual value of their secret by exchanging hashes. It's not possible to determine the input from just the hash function's output assuming the input is sufficiently unpredictable. (Having high entropy.) A player cannot swap out the secret value they commit to without finding a collision in the hash function. (Using a prepended random nonce makes finding collisions even harder because you cannot use precomputed collisions.)

The final hash of both secrets, the nonce, and whatever other data is involved results in a random value from a uniform distribution (under the assumption that the hash function behaves like a random oracle). Any change in input to a hash function results in unpredictable changes to the output. This means that one party doesn't have to trust that the other party's secret is random as long as their own number was chosen randomly.

However, even with commitment schemes, it is still possible to cheat if aborting the protocol allows the second person to walk away with a smaller loss by not cooperating by revealing their secret than the loss they would incur by cooperating. (Sort of like people who hit the reset button on their game consoles when they're losing to another player. Or flipping a chess board off the table.) The second person has enough information to calculate the result of the game on their own, and so they might pretend to have their computer crash to avoid paying out larger winnings.

And again, your description of the protocol is vague, so we can't say whether the actual protocol is secure or not. (And even if the protocol were secure it's another matter whether or not the implementation is correct.)


Verifying multiplicative inverse on a prime field in NIST's ECDSA_Prime.pdf

You are using the wrong value as the modulus; you ought to be using the value $r$ (which is also listed in the document).

$p$ is the characteristic of the field that the elliptic curve you're using is defined on.  In this case, we're not interested in that; instead what we're interested in is the order of the curve, that is, that value $r$ such that $rP = 0$ for all points $P$ on the curve (note: strictly speaking, we're interested in the order of the generator point, however in this case, that's the same).  That value $r$ is as listed.

$K$ and $K_{inv}$ are not inverses modulo $p$; instead, $K \times K_{inv} = 1 \ (\bmod \ r)$


Background: Secret Sharing and Multiplication Triples

For the second question. The mistake was exactly that the asker did the XOR as
$$
d_a = x_a \oplus a \\
d_b = x_b \oplus a
$$
But the correct way is
$$
d_a = x_a \oplus a\\
d_b = x_b
$$
Thus to compute the shares for
$$
[z] = [c]\oplus e[x]\oplus d[y]\oplus ed
$$
You would set
$$
z_a = c_a \oplus ex_A \oplus dy_a \oplus ed\\
z_b = c_b \oplus ex_b \oplus dy_b
$$
You can check that this gives the expected result.

I am not sure what you first question is about. The purpose of the having secret shared a random multiplication triple $[a],[b],[c]$ is solely to use it later in this protocol to perform a multiplication operation (in this case AND). Not sure if this answers you question.


How is a Yubikey static password derived from the AES key?

The password is the result of encrypting the fields used for OTP, but with fixed values:

me@mine:~$ ykparse 00000000000000000000000000000000 ncejelrjvjvvciclerknrlihnteljrcb
Input:
  token: ncejelrjvjvvciclerknrlihnteljrcb
          b0 38 3a c8 f8 ff 07 0a 3c 9b ca 76 bd 3a 8c 01
  aeskey: 00000000000000000000000000000000
          00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Output:
          00 00 00 00 00 00 ff ff ff ff ff ff ff ff 0f 2e

Struct:
  uid: 00 00 00 00 00 00
  counter: 65535 (0xffff)
  timestamp (low): 65535 (0xffff)
  timestamp (high): 255 (0xff)
  session use: 255 (0xff)
  random: 65535 (0xffff)
  crc: 11791 (0x2e0f)

Derived:
  cleaned counter: 32767 (0x7fff)
  modhex uid: cccccccccccc
  triggered by caps lock: yes
  crc: F0B8
  crc check: ok

This can be reproduced with OpenSSL:

me@mine:~$ key=00000000000000000000000000000000
me@mine:~$ fixed='\x00\x00\x00\x00\x00\x00\xff\xff\xff\xff\xff\xff\xff\xff\x0f\x2e'
me@mine:~$ modhex -h $(echo -ne "$fixed" | openssl enc -aes128 -nopad -K $key -iv "" \
                       | hexdump -v -e '/1 "%02x"')
ncejelrjvjvvciclerknrlihnteljrcb

You can't quite reproduce it with ykgenerate because that tool always includes a genuinely unpredictable random: field.


Is it possible to validate an email address without the user actually revealing the email address?

Your idea is exactly what is achieved in a recent paper:

  Blind Certificate Authorities.  Liang Wang, Gilad Asharov, Rafael Pass, Thomas Ristenpart, abhi shelat. At IEEE S&P 2018.

The server and client use secure multiparty computation to jointly make an SMTP+TLS connection to a mailserver, generating the appropriate encrypted packets to send an email to username@domain.com, so that the server doesn't learn username and the client doesn't learn the random challenge in the body of the email.


Hypothetical DES weakness: dual encryption identical to single encryption with specific keys

I will take this to mean that it's possible to efficiently find a $k_3$ so that

$$E(k_2,E(k_1,M))=E(k_3,M)$$

which would mean the cipher $E$ has too much structure and given a keylength $n,$ a double encryption like above is as weak as a single encryption and brute force key search would take $O(2^n)$ encryptions at worst.

Mind you, a meet in the middle attack on double encryption for an arbitrary cipher $E$ can break it in time $O(2^n)$ and a few plaintext/ciphertext pairs $(M,C)$ if
memory of size $O(2^{(n+\log n)})$ is also available. First form a hash-sorted list of $$\{(k_2,E(k_1,M)):k_1 \in \{0,1\}^n\}$$ sorted on the second coordinate
and then keep computing $E^{-1}(k_2,C)$ as $k_2$ ranges over $\{0,1\}^n,$ and looking up to see if it is in the table.

If you find a hit, then try with another P/C pair to confirm the guess is not spurious. This is because the composite permutation may have fixed points.

Edit:. I didn't originally want to make this too abstract, but as pointed out in the comments, what you're asking is whether $E$ forms a group, which it most certainly does not when $E$ is DES.


How can a recipient recognize which encrypted messages are intended for them?

Are there any cryptographic primitives/protocols allowing the sender to signal to the recipient faster that the message is intended for them, yet not reveal the true recipient to everyone else and allow them to quickly skip trying to decrypt the message?

It doesn't appear that the problem of recognizing the message (without leaking who the message is for) can be significantly faster than public key decryption.  Let me be more precise; suppose we had a way such that:

Alice can publish some public information
Bob can use this information to generate a 'tag'
Alice can check to see if this tag was generated with her public information
No one without Alice's private information can do so (if not, anyone can check if the tag was flagged to be of interest to Alice).

If we have a primitive that can do that, then Alice can use that primitive as a public key encryption method; the method isn't very efficient (in the simplest case, Bob would generate a series of 'tags', where each tag encodes a bit - one bits are tagged with Alice's information, and zero bits are not); however it is sufficient to indicate that the problem isn't inherently easier than the general public key encryption problem.
So, what can we do?  Well, the best I can suggest is use a public key encryption method that's more efficient than RSA; here are two ideas:

ECIES; here, the decryption operation is a point multiplication (and a handful of symmetric operations); significantly cheaper than RSA

NTRU; this is a NIST postquantum level 3 candidate with (to use a technical term) honkin' fast decryption; for example, the ntruhps2048677 parameter set is listed as using only 59,729 Haswell cycles.

Of course, you could also separately RSA encrypt the message along with the tag; however, given that by validating the tag, you've essentially done most of the work, you might want to just use ECIES or NTRU.
Also, one comment on your idea:

One thing I came up with is, as the number of participants and messages passed grows exponentially, gradually increase the number of leading bits of the recipient's public key getting revealed with new messages

Does that mean that, in the ciphertext, you expose k bits of the public key, where k gradually increases as the number of messages increases?  Well, one problem with that is, while an eavesdropper can't generally be certain who the message is for, he can be pretty sure who it is not for - that many be just as bad...


$F'_k(x)$ is not necessarily pseudo-random.

Proof:
Changing one output does not affect PRGness, so if there is a PRG

that stretches by a factor of 2 then there is a PRG that stretches

by a factor of 2 and sends all-zero strings to all-zero strings.

For all $n$ and $k$ and $x$, if $G$ is such a PRG then $F'_k(x)$ is the string of $n$ zeros.

For all $n$, if $\: n\neq 0 \:$ then there are other strings with that length.

Therefore $F'_k(x)$ is not necessarily pseudo-random.

(Of course, this doesn't prove that your construction can't be pseudo-random.)


Differential cryptanalysis tutorial of Howard M. Heys

There is no assumption of obtaining any outputs of an internal round at all.

Having done the analysis, the attacker submits enough plaintext pairs with fixed difference $\Delta P$ so that he can be sure with high probability that the most common ciphertext difference is $\Delta C$.

Note that in his example, the 2nd and 4th Sboxes are active, so the target key bits are those at the output of Sboxes $S_{4,2}$ and $S_{4,4}$.

Now he can do a loop where he tries all the $2^8$ possible key bit hypotheses
$$(\widehat{K_{5,5}},\widehat{K_{5,6}},\widehat{K_{5,7}},\widehat{K_{5,8}},\widehat{K_{5,13}},\widehat{K_{5,14}},\widehat{K_{5,15}},\widehat{K_{5,16})},$$
and under each hypothesis (since he knows the ciphertexts) he can determine the hypothetical differentials (correct subject to the key guess being correct) at the output of the Sboxes $S_{4,2}$ and $S_{4,4}$ which by inverting the Sboxes can be converted to hypothetical input differences of the form $\Delta U_{4,5},\ldots,\Delta U_{4,16}$.

Whichever key combination gives the most likely differential $$\Delta U_4=[0000~0110~0000~0110]$$ is declared the most likely key guess for the last round.
So he would keep a count corresponding to each hypothesized round 5 key as the loop runs and check which value gave the maximum count.

Then the rounds can be peeled off one by one as in the comments.


Zero-knowledge proof with only a ciphertext

Yes, this is possible: every statement in NP can be proven in zero-knowledge, meaning, without revealing anything more than the very fact that the statement is true. In fact, this result can be extended to proofs of knowledge, where the prover does not only show that a statement is true, but also that he does know a witness (still without revealing it).

Of course, general techniques are very inefficient. For standard symmetric ciphers, the best approaches will use general zero-knowledge proofs for statements represented by boolean circuit - see my answer to the question that AleksanderRas links to in the comment section. You should also note that if you replace the symmetric cipher by a cipher with a strong algebraic structure, such as ElGamal, then much (much) more efficient solutions exist - for example, in ElGamal, proving knowledge of a plaintext requires only exchanging a few string (about twice more communication than simply sending the ciphertext - so really not much).


Easy explanation of "IND-" security notions?

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most reasonable approach is to define constraints strong enough to satisfy some definition of security. The $\operatorname{IND-}$ notation provides such definitions in terms of games, where a challenger keeps his key secret, and an adversary has certain capabilities and his target is to break the encryption system.

To keep it general, an encryption scheme will have a key generation algorithm $KG$, which will generate a key pair $K_E$, $K_D$, an encryption algorithm $E$ and a decryption algorithm $D$. Encryption is always revertible, but the encryption and decryption key can be different (covering public key crypto): $D(K_D, E(K_E, M))=M$

  IND-CPA: INDistinguishability under Chosen Plaintext Attack

In words: the adversary generates two messages of equal length. The challenger decides, randomly, to encrypt one of them. The adversary tries to guess which of the messages was encrypted.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary: $m_0, m_1 = $ choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time including calls to the encryption oracle.
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$. Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time including calls to the encryption oracle. Output $guess$.
If $guess=b$, the adversary wins

Further comment: the main concept introduced by this scenario is the polynomial bound. Now, our expectations from crypto are weakened from probability of winning is negligible to probability of winning within a reasonable timeframe is negligible. The restriction for the messages to be of the same length aims to prevent the adversary to trivially win the game by just comparing the length of the ciphertexts. However, this requirement is too weak, especially because it assumes only a single interaction between the adversary and the challenger.

  IND-CCA1: INDistinguishability under Chosen Ciphertext Attack

In words: the target of the game is the same as in IND-CPA. The adversary has an additional capability: to call an encryption or decryption oracle. That means: the adversary can encrypt or decrypt arbitrary messages before obtaining the challenge ciphertext.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary (a polynomially-bounded number of times): call the encryption or decryption oracle for arbitrary plaintexts or ciphertexts, respectively
Adversary: $m_0, m_1 = $ choose two messages of the same length
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time. Output $guess$
If $guess=b$, the adversary wins

Further comment: IND-CCA1 considers the possibility of repeated interaction, implying that security does not weaken with time.

  IND-CCA2: INDistinguishability under adaptive Chosen Ciphertext Attack

In words: In addition to its capabilities under IND-CCA1, the adversary is now given access to the oracles after receiving $C$, but cannot send $C$ to the decryption oracle.

Algorithm:

Challenger: $K_E, K_D$ = KG(security parameter)
Adversary (as many times as he wants):  call the encryption or decryption oracle for an arbitrary plaintext/ciphertext
Adversary: $m_0, m_1 = $ choose two messages of the same length
Challenger: $b=$ randomly choose between 0 and 1
Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
Adversary: perform additional operations in polynomial time, including calls to the oracles, for ciphertexts different than $C$. Output $guess$.
If $guess=b$, the adversary wins

Further comment: IND-CCA2 suggests that using the decryption oracle after knowing the ciphertext can give a reasonable advantage in some schemes, since the requests to the oracle could be customized depending on the specific ciphertext.

The notion of IND-CCA3 is added based on the reference provided by @SEJPM. I add it for completeness, but it seems important to point out that there are few resources about it, and my interpretation could be misleading.

  IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

In words: It is not possible to create a valid forgery with non-negligible probability. The adversary is given two pairs of encryption/decryption oracles. The first pair performs the intended encryption and decryption operations, while the second one is defined as follows: $\mathcal{E}_K$: returns encryptions of random strings. $\mathcal{D}_K:$ returns INVALID. Instead of being presented as a game, it is presented using the mathematical concept of advantage: the improvement of the probability of winning by using the valid oracle against the probability of success under the "bogus" oracle.

Formula: $\mathbf{Adv}^{ind-cca3}_{\pi}(A)=Pr\left[K\overset{\$}{\leftarrow}\mathcal{K}:A^{\mathcal{E}_K(\cdot),\mathcal{D}_K(\cdot)}\Rightarrow 1\right] - Pr\left[A^{\mathcal{E}_K(\$|\cdot|),\perp(\cdot)}\Rightarrow 1\right] $

Further comment: the paper where IND-CCA3 is introduced a focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

Note that in the case of public-key cryptography the adversary is always given access to the public key $K_E$ as well as the encryption function $E(K_E, \cdot)$.


Using related pair of cryptographic keys to open/seal plaintext

You are effectively using symmetric encryption.

The crypto_box function uses elliptic curve Diffie–Hellman on Curve25519. With a given input private key and public key it always generates the same symmetric key, which is then used for authenticated encryption. By using the private and public key from the same key pair you are generating the point $a^2G$, which with a random $a$ is just a random point on the curve. This point is then used to derive a symmetric key for authenticated encryption.

Of course, it would be more efficient to just use that derived key (or a random key) in the first place, but as long as you keep the key pair secret, what you are doing is secure.


Coefficients of Elliptic Curve over Finite Fields

$A$ and $B$ can be non-integers if you're working with an extension field. For example, this happens with pairing-friendly curves where you need to work with elliptic curves over e.g. $\mathbb{F}_{p^2}$.
Depends on the algorithm. For counting elliptic curve points, the "hard" part is computing $\#E(\mathbb{F}_p)$. If you compute that, than it's easy to compute $\#E(\mathbb{F}_{p^k})$; see this answer. In the Koblitz curve case it's even easier since computing $\#E(\mathbb{F}_{2})$ is trivial (it's either 2 or 4 depending on the curve).


Is this encryption scheme perfectly secure?

The modulo operator keeps the result of the addition of $M$ and $K$ within the set $Z$.

For example, if $m$ is 10, $M$ is 6 and $K$ is 5, $M + K$ would be 11 which is no longer in the set $Z$.  Taking 11 mod 10 results in 1 which is in the set $Z$.

The definition of perfect security is:

  An interesting special case is perfect security: an encryption
  algorithm is perfectly secure if a ciphertext produced using it
  provides no information about the plaintext without knowledge of the
  key. If E is a perfectly secure encryption function, for any fixed
  message m there must exist for each ciphertext c at least one key k
  such that $c = E_{k}(m)$. It has been proved that any cipher with the
  perfect secrecy property must use keys with effectively the same
  requirements as one-time pad keys.


Lehmer random number generator cipher - looking for differentials

Do you see any differentials here?

Yes; consider a differential where one side is the value $X$ and the other side is the value $2^{127}-X$.
Your cipher consists of three operations:

Multiplying the current value by an odd value $a_i$ modulo $2^{128}$

This operation preserves the differential with probability 1; one side would evaluate to $a_i \cdot X$ and the other side would evaluate to $a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X$

Negating the current value (which is done as a part of rounds 2-10)

This operation preserves the differential with probability 1; this happens because $-(2^{127} - X) = 2^{127} - (-X)$

Reversing the bits in the current value

This operation preserves the differential with probability 0.5; namely, if the lsbit of $X$ (equivalently, $2^{127} - X$) is a 1.  This happens because, when the lsbit is a 1, this relationship is equivalent to the relation that $X \oplus (2^{127}-X) = 2^{127}-2$.  This later relation is preserved when you reverse the bits, and hence the former one is as well.
This gives you a differential that holds with probability $2^{-10}$ through the ten rounds of the cipher.


ECC - Point Addition/Point Multiplication

The arithmetic done during a point addition is done using the addition and multiplication operations in the field; when you are using a prime field, that is equivalent to doing addition and multiplication modulo the prime (23 in this case).

Now, because we're doing the arithmetic modulo 23, we get to notice that $147 \equiv 9 \bmod 23$, and so those refer to the same field element; that is, in any field equation, we can replace one with the other without changing anything, or in other words $147 / 4 = 9 / 4$

Now, what does division mean in this case?  Well, what $a / b = c$ means is that $a = b \times c$ (and since this is done within the field, this actually means $a = b \times c \bmod 23$).  What we do is define the multiplication inverse $b^{-1}$ defined by $b \times b^{-1} = 1$, and so we have $a / b = a \times b^{-1}$.  And, in this case, we have $4^{-1} = 6$ (because $4 \times 6 \equiv 1 \bmod 23$).

Combing these two, we get $147 / 4 = 9 \times 4^{-1} = 9 \times 6$

Now, the obvious question that you will ask is "how do we find multiplicative inverses"?  After all, when dealing we numbers between 1 and 22, it's easy enough to find it via brute force, however how do we find these when we're dealing with modulii hundreds of bits in length?

The answer to that is the extended Euclidean Method; that gives an efficient way to find such inverses.

Now, I'll leave you with one last point; the references you give might give you some background as to why the point addition operation makes sense, however there are a bunch of optimizations they don't discuss (because they get in the way of explaining the basics).  On reference (that doesn't talk about the why, but considerably more about the what) is this IETF RFC; the "projective coordinate" method of representing points turns out to be considerably more efficient than more naive methods.


Should I use ECB or CBC encryption mode for my block cipher?

The really simple explanation for the difference between the two is this:

ECB (electronic code book) is basically raw cipher. For each block of input, you encrypt the block and get some output. The problem with this transform is that any resident properties of the plaintext might well show up in the ciphertext – possibly not as clearly – that's what blocks and key schedules are supposed to protect againt, but analyzing the patterns you may be able to deduce properties that you otherwise thought were hidden.
CBC mode is short for cipher block chaining. You have an initialization vector which you XOR the first block of plaintext against. You then encrypt that block of plaintext. The next block of plaintext is xor'd against the last encrypted block before you encrypt this block.

(Public domain image from Wikimedia Commons.)

The advantages of CBC over ECB are many – with ECB, assuming many things, you could manage a partial decryption and easily fill in the blanks, for example if extracting data from an encrypted hard disk. With CBC, if you are missing a few blocks in the sequence encryption becomes impossible. However, there is one downside to CBC – ECB naturally supports operation in parallel since each block can be encrypted independently of the next. However, with CBC this is harder, since you have to wait on each block. (You can still parallelize decryption, though.)

CBC itself can also be considered vulnerable in certain situations, specifically the use of predictable IVs and unauthenticated decryption can allow you to guess plaintexts as explained in this answer and in more detail here.

The IV problem is resolved by using unpredictable (cryptographically random) IVs. The authentication problem is traditionally resolved using message authentication codes - however, implementation of these is not perfect. Dedicated modes have been invented which tackle the issue of authentication too, for example EAX and Galois Counter Mode.

Other modes exist to deal with specific scenarios, e.g.:

Counter Mode uses the fact that a block cipher's output in ECB mode should be indistinguishable from random, and XOR's the result of encrypting a counter+iv combination as a stream cipher.
XTS is a mode of operation used in disk encryption.

The key point to take away is that each mode has a number of merits and implementation concerns and these must be weighed up carefully (and correctly implemented). And, where possible, avoid ECB.

Expanded explanation for how resident properties propagate into ciphertext with ECB

When writing this answer, I tried to not post a picture of the typical ECB-encrypted linux penguin, but I've been asked to expand on "resident properties in the plaintext" so what follows will be the same idea, just in text form. If you don't need it, feel free to skip.

Firstly, let's use a format I know something about - the mp3 frame. Like most plaintext this is far from "indistinguishable from random" - indeed for example, the MP3 frame header begins with 11 bits set to 1.

There are two important properties of block ciphers:

On a block level, operations are deterministic. If I encrypt "Cryptography Stack Exchange" and this fits in a single block, I expect to get the same output for given parameters every time. This sounds like a crazy critera (of course we need this) but it's worth highlighting.
On a block level, the output is indistinguishable from random - more formally there's no advantage for an attacker over using a random permutation, at least in a way that is realistically computable. My terminology might be a bit off because I am self taught, but I believe if the advantage is non-zero you've got a bias and this makes the cipher a candidate for linear cryptanalysis.

These statements apply considering only a single block; however obviously in the real world we want more than that - we want to encrypt multiple blocks.

Suppose we live in an imaginary world where people think block ciphers with a block size of one byte are a good idea. Now let's imagine this is otherwise a totally fine block cipher. Now imagine you have some MP3s of Justin Bieber music and you'd very much like the NSA not to find out about this. So you take your block cipher and you encrypt your MP3.

Now, one of those blocks, making some assumptions about file alignment, is going to be 0xFF - that's 8 of your 11 ones from the frame header in the MP3. These are always there at the beginning of each frame. Now our cipher is indistinguishable from random so we get perfectly random ciphertext, say 0x1c. But it is also deterministic and we're using ECB, so every frame header that was 0xFF becomes 0x1c.

All of a sudden we're giving away information to our attacker - specifically they can deduce where the frame headers are if they suspect this to be an MP3. Cryptanalysis is sometimes about guessing correctly and a correct guess in this case will give them an idea of exactly how long the audio samples are and allow them to identify the format.

Moreover, every other ciphertext block 0x1c is now decodable too. That's not information we intended to give away, but we did.

This problem is common particularly when you consider much of what we encrypt has a rigid data format. You have to make some assumptions about alignment on the blocks, but the larger the data the more this problem becomes apparent.

This is what I mean by residual plaintext properties becoming evident in the ciphertext. These are the structure inherent to and wanted in the plaintext that inadvertedly become exposed to the attacker.

The original purpose of CBC mode was as a form of identifying corrupt messages and the security of CBC for this purpose is treated in this paper. I can't find the original realization of this idea in terms of papers, but you might be able to find it. Certainly most books on block ciphers that I have read mention it and other issues.


Use of symmetric keys rather than asymmetric keys for transport security

The main reason is efficiency; asymmetric cryptography requires a large overhead with regards to CPU time and bandwidth, while symmetric encryption does not. The time to perform RSA decryption for instance is slower than AES:

  Doing 4096 bit private rsa's for 10s: 48 4096 bit private RSA's in 10.10s

That's clearly somewhere about 2,4K/s for a reasonable key size for RSA, and that's excluding overhead, so say about 2 KB/s.

  Doing aes-128 cbc for 3s on 64 size blocks: 6221203 aes-128 cbc's in 3.00s

So that's over 128 MB/s, just slightly faster.

You'd need both confidentiality and integrity / authenticity though. So to add a signature and MAC you should about half the speed for both.

Asymmetric encryption is not usable for bulk encryption.

There are more reason to use short term session keys. One is that you can achieve forward secrecy when you derive the session keys using ephemeral-ephemeral key agreement. If that is used the session remains secure even if the private keys become compromised. In such a scheme the asymmetric key pairs are only used for authentication. This will be the default for TLS 1.3.


Quantum Cryptography Used in a messaging application

NO, if "messaging application" is software running on an stock consumer-grade computer or variant (including mobile phone, tablet): in any of its standard meanings, Quantum Cryptography requires specific hardware.

For Quantum Key Distribution (actually quantum privacy amplification), which is how quantum cryptography does encryption, you'd need a specific interface; an optical fiber running to the recipient or ultra-precise alignment towards the receiving device in line-of-sight (with no fog/smog); AND the inconvenience of exchanging initial secret keys in sealed envelopes or equivalents (see this). QKD is a working solution looking for problems, and failing at that.

Quantum Computers are currently about as common as manmade objects on Mars, and as useful to make or break practical cryptography. Quantum Computing is an immature technology, and it is uncertain when (and even if) it will metamorphose into something practical, in particular for cryptography. At even odds, I would bet that controlled fusion will be first (that would make the energy wasted on cryptocurrency mining a non-issue).

Among doable things with a sensible use of the word "Quantum", I only see "Quantum-Safe Encryption", or otherwise said "Encryption by Post-Quantum Crytography". That is encryption believed safe even from hypothetical quantum computers usable for cryptanalysis. Using the common AES-256-GCM qualifies, and is easy, but that's symmetric encryption. For the convenience of public-key cryptography, we'd have to pick something in the realm of Post-Quantum cryptography; the state of that nascent art is presently competing there.

Another semantically justifiable thing is bragging for a "Quantum Random Number Generator". The OS's cryptographically secure RNG likely qualifies (any TRNG or matter is ultimately quantum-based anyway), and if it was not it would be hard to disprove the claim that it is.


Is SHA-256 secure as a CTR block cipher?

Well, as far as we know, the mode you suggest should be secure.  Now, to be honest, AES256 versus your mode isn't quite a fair comparison; your mode gives somewhat less theoretical security; if you encrypt a known $2^n$ block message, the key can be recovered with $2^{256-n}$ effort; however, this observation doesn't really affect the practical security.

However, as for why AES might be preferable:

AES is faster.  Performance, of course, varies wildly between platforms and implementations; but taking as an example the CryptoC++ benchmarks, we see AES256 listed as 18.2 cycles per output, while SHA256 takes about 31 cycles per output.  Note: SHA256 is listed as 15.8 cycles per byte; however, that is bytes of input; a single SHA256 compression evaluation takes 64 bytes of input, and hence takes 1011 cycles; in your use, you use a single SHA256 compression evaluation to generate 32 bytes of keystream; hence 1011/32 = 31.6 cycles per byte of output.
AES can be used on contexts other than counter mode.  That is, AES is invertable (if you know the key); that sometimes comes in handy.
However, the most important point is: AES has been far more extensively analyzed in this context.  SHA256 has been analyzed fairly heavily for collision resistance; however, I don't know if anyone has really looked at the question "if we have a large number of hashes of related but unknown images, can we gdeduce what the image is?".  With AES, we known that people have been attacking it with this question in mind.


Algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state of an LFSR?

If the initial state is $b_0,b_1,\dots,b_{k-1}$ and the recurrence relation is $b_k = \sum_{i = 0}^{k-1} a_ib_i$, then in linear-algebraic terms we have
$$ \begin{pmatrix}
b_1 \\ b_2 \\ \vdots \\ b_k
\end{pmatrix} = U \begin{pmatrix}
b_0 \\ b_1 \\ \vdots \\ b_{k-1}
\end{pmatrix}, $$
and more generally
$$ \begin{pmatrix}
b_{n} \\ b_{n+1} \\ \vdots \\ b_{n+k-1}
\end{pmatrix} = U^n \begin{pmatrix}
b_0 \\ b_1 \\ \vdots \\ b_{k-1}
\end{pmatrix}, $$
where of course
$$ U = \begin{pmatrix}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & 1 \\
a_0 & a_1 & a_2 & \cdots & a_{k-1}
\end{pmatrix}. $$
And $U^n$ can be computed efficiently by standard exponentiation algorithms.


Can a one-way accumulator be used in place of a digital signature?

The approach of one-way accumulators aren't a satisfying alternative to DS algorithms. Basically its just another way of using hash functions to generate a Message authentication code by hashing a message and a shared secret, while the author replaces the shared secret with the identities of all participants.

While MACs are a commonly used approach of detect data manipulation, since an attacker can't forge a MAc without knowing the secret key (of course there a several attacks on different MAC schemes and several ways of finding collisions, but an overview of collision resistance, preimage resistance resistance and second preimage resistcance would go beyond the scope of the discussion), nobody can prove the senders identity of a received message.
Because all participants share the same key, everybody could have computed the MAC.

Digital signatures use key pairs of $(k_{pub},k_{priv})$ for every party in the protocol, so you can be sure the messages origin way Alice, if the message is signed with Alices $k_{priv}$. The most basic attack on schoolbook DS are replay attacks: An attacker Eve just need to record the message of Alice and replay it later. To prevent this (and other attacks), a challenge-response-protocol is the best way to prove your identity to somebody.

To refer to one-way accumulators, you can say:

You can verify to be in possession of these data, all participants computed their identity against. But this is just a  combination of a shared secret (participants list) and your own identity.  I'm not even sure, if you can call it a MAC at all.
You can not verify other messages data. ($\neq$ message integrity)
You can not prove your identity, since the scheme is vulnerable to replay attacks. ($\neq$ nonrepudiability)
You can not verify the identity of a messages originator.($\neq$ origin integrity)

Since the design relies on a shared message (the participants list), you also have to perform all computations again, if a member is removed or added, which would having a devastating impact for the usage of this scheme.


Generate secp256k1 ECC key pair with libsodium

Your question has been asked on the GitHub, too:

Is there some way with sodium/libsodium to make all crypto_sign_* methods use SECp256k1?

And the answer was given as

No, there isn't, and there never will be.
Libsodium is an opinionated API. You get one good algorithm for every use case. Fewer knobs and levers + more secure constructions = less crypto vulns in software that consumes the API.
For public key cryptography, you get ECDH and EdDSA over Curve25519. No Weierstrass or Koblitz curves.


How do you work out the private key in a RSA cryptosystem knowing a certain public key?

In your case you can factor $N (= 85)$ and use that to compute $\phi(N)$, which in turn allows you to compute $d = e^{-1} = 19^{-1} \text{ mod } \phi(N)$. Factoring $N$ yields $5 * 17 = 85$ which in turn means $\phi(N) = (5-1)(17-1) = 64$. Finally, $d = 27 = 19^{-1} \text{ mod } 64 $.

Note that for most actual instances of RSA $N$ is usually at least 1024 bits, and as such cannot be efficiently factored by pretty much anyone. Hence recovering $d$ from just $(e, N)$ is considered unfeasible. This is critical to the security of RSA. It intuitively makes sense too, if you can recover the private key using only the public key then the private key isn't very private.


SSL pinning - how to safely hide the certificate?

You don't need to hide the certificate at all. The certificate only contains the public key and additional info of the owner (in this case the server). It shouldn't contain any private information. What you need to do is to store the certificate in such a way that you can trust the origin of the certificate.

So what you need to think about is certificate management. For instance, what happens if you need to replace the certificate? Is an update of the software enough?

The private key is not part of the certificate. This may not be obvious from certain API's such as the Microsoft API. You must make sure that you only export the X509 certificate(s) excluding the private key. If you are exporting a PKCS#12 (PFX) file then you may be doing something wrong.

The key pair should be generated on the system where you intend to use the private key. Access to the private key should be kept to an absolute minimum. The public key and certificate may be distributed freely.


Gaussian elimination to equations with errors

$q$ is the number of samples and $S$ is the set of indices such that $\sum_{i\in S}x_i = (1,0,...,0)$. In your example, we have $q=3$ and $S=\{1,3\}$. The first bit of the secret $s$ is equals to $\sum_{i\in S}b_i \mod 2$, but with probability $1/2+2^{-\Theta(n)}$ not $1$, because the noises are also considered in this summation. So we need to repeat this procedure $2^{\Theta(n)}$ times to reduce the error probability.


The fact that few bits change at the input of ChaCha's "core" function does not compromise the security of the ChaCha20 stream cipher.

The design principle of the stream ciphers Salsa and Chacha is to use a "core" function $C:\,\{0,1\}^{512}\to\{0,1\}^{512}$ over the set of 512-bit bitstring (equivalently the set fo 16 words each 32-bit). Among the 512 input bits, 128 are set to arbitrary public constant values $c$, turning the remaining into some function $C_c:\,\{0,1\}^{384}\to\{0,1\}^{512}$.

$C_c$ behaves essentially like a function chosen at random in the set of functions with such input and output domains. In particular, it is conjectured that not knowing $k$ of the 384 input bits chosen at random, the function $C_c$ can't be distinguished from a random function with works less than $2^k$ operations (each requiring a sizable number of CPU cycles), for $k$ up to some comfortable limit (like 160 to 256).

Of the 384 input bits of $C_c$, $k=$256 are for the key, 64 for the nonce/IV, 64 for the counter. The full 512-bit output forms the keystream. As long as the key is random and secret, and the combination of IV and counter value does not repeat, the above conjecture demonstrably implies security of the stream cipher in all common security models, including for related keys.

That's even though, for most blocks of a large keystream, the input of the core function differs by a single bit from the input for another block, and 256 bits (including all those that vary) at the input of the core function are public.

The supporting argument for the stated security conjecture is the design of the core function per $C(x)\gets G^r(x)\boxplus x$ where $G$ is a bijection iterated for $r$ rounds, and $\boxplus$ is a group operation on $\{0,1\}^{512}$. Bijection $G$ is optimized for fast diffusion when iterated.

Note: diffusion is the main area where ChaCha improves (slightly) on Salsa. Another it is that it removes a harmless class of collisions in $C$, see this.


HMAC doesn't suffer the issue with collision resistance (in other words: the birthday bound does not apply). This is simply because an attacker doesn't have the secret key used to generate the HMAC authentication tag, so there is no way to build a huge table of possible outputs that can be compared against.
So usually the security of a hash is defined as half the number of output bits because of the birthday bound. To get the same level of security you can therefore output half of the output bits of HMAC because the birthday attacks do not apply.
You can use HMAC-SHA-512 to generate 128 bits of security by using the leftmost 128 bits (and it may even be slightly faster than HMAC-SHA-256 for large messages on a 64 bit CPU). However, it won't deliver the maximum security that can be provided by HMAC-SHA-512 - not that you would ever need 512 bits of security.

Note that the 80 bit security is half the output size of SHA-1 (or RIPEMD-160 for that matter). Nowadays 80 bits is not considered (all that) secure anymore.


A "one time pad" can be thought of a Vigenere cipher with

(1) is the correct answer.  The Vengiere cipher phrase is a distractor.  Basically all alphabets are in the cipher.

Note that the key does not need to be infinite, merely the same length as the plaintext and random.  So in that regard, all of the answers are incorrect... But (1) is the "best" answer as it is the answer with the most entropy or randomness, which is the point of a one-time pad. You cannot draw any conclusions about entropy from the other answers.


HMACSHA256 2.5 times faster than HMACSHA512

SHA-512 internally hashes blocks of 128 octets, versus 64 for SHA-256. That can give a speed advantage on 64-bit CPUs in term of octets hashed per second, but only for large messages. I'd try 8192 where there is 64, and 200 where there is 10000.

The SHA-512 compression function typically requires significantly more time than that of SHA-256: structure is close, with variables twice the size, and there are 80 rounds versus 64 (25% more). There's also about twice as much data moved, and that typically incurs some penalty. However the time required overall can be less than twice as much, and since twice as much message is hashed, there can be some benefit overall for large message.

The question compares HMAC-SHA-512 to HMAC-SHA-256. The HMAC construction adds at least 3 compressions (more so for long keys) compared to a straight hash, which further increases the message size threshold before the 64-bit version can have an edge. With a 64-octet message, HMAC-SHA-512 performs 4 compressions, and HMAC-SHA-256 performs 5 (320 rounds for both). For a 8192-octet message, that goes 68 vs 132 compressions (5440 vs 8448 rounds), which gives HMAC-SHA-512 a chance.

Also, speed of algorithms, especially crypto, depends a lot on the quality of their implementation and how well it is tailored to the hardware at hand. From where we stand, we can't even tell if HMACSHA512 or HMACSHA256 are native code, Just-In-Time-compiled, or interpreted. Benchmarking anything but native code is both rather pointless (if performance really matters, the critical section should be native) and harder (results tend to be unstable).


The correct answer would be:

  1 . “Cryptography is under the security field”.

Let me try to explain it a bit…

Cryptography

Modern cryptography concerns itself with 4 objectives:

Confidentiality: the information cannot be understood by anyone for whom it was unintended.
Integrity: the information cannot be altered in storage or transit between sender and intended receiver without the alteration being detected.
Non-repudiation: the creator/sender of the information cannot deny at a later stage his or her intentions in the creation or transmission of the information.
Authentication: the sender and receiver can confirm each other’s identity and the origin/destination of the information.

Information Security

Now, if you look at information security (what you simply call “security”), you’ll notice that – besides the four points mentioned above – there’s a whole universe of other security-related things that information security handles. To name just a few examples of what information security  additionally covers (besides cryptography):

risk management,
access control,
security classification of information,
business continuity,
disaster recovery planning,
laws and regulations,
etc.

Nota Bene

In the end, this might also help you understand why StackExchange has a Security.SE – which  covers information security in general, and a Crypto.SE – which explicitly focuses on cryptographic details like algorithm design, protocol analysis, etc.

EDIT:
More of an aside, but it may help understand things even better… I just noticed that Wikipedia has a nice Contents-listing in their InfoSec article, from which you can see how Cryptography fits into Information Security as a sub-category (6.5).


Seeding the Fortuna PRNG for the first time

You have to appreciate that Bruce and Niels' paper isn't source code. They wrote "We assume there are several sources of entropy in the environment" and "feel free to
choose AES (Rijndael), Serpent, or Twofish for this function".  It's a bit of a concept paper without a hard implementation.  That's been left to others.

An example of this is on Silicon Labs micro controllers.  That implementation is ultimately seeded with real entropy from reading the internal temperature sensor.  Those tend to jitter somewhat, creating true randomness. Even they though add this proviso: "The user is encouraged to implement additional entropy
sources."  The implementation of FreeBSD palms this off to various device drivers to call the random_harvest_*() function themselves.

This entropy input step is outside of the Fortuna construct. They clearly couldn't predict where Fortuna would be running so it was correct to leave this to particular implementations.  It could easily be avalanche diodes, keyboard key scanning firmware or even the internal temperature sensors that are scattered throughout desktop motherboards these days.


The only downside to SHA-2 over SHA-1 is that SHA-2 is a little slower.

In this case, that is of no practical consequence whatsoever because you're trying to make something slow to compute, and it is only a matter of raising the number of iterations to make it cost a certain number of bit operations in serial.

However, please consider using the modern memory-hard password hashes scrypt or argon2 instead of PBKDF2, to limit the advantage that attackers with highly parallel low-memory GPUs, FPGAs, or ASICs can attain over the defenders using ordinary CPUs.

Of the SHA-2 family, SHA-512 is a little faster than SHA-256 on CPUs with native 64-bit integer arithmetic, which are the vast majority of personal computing devices today.  So it provides a tiny advantage to the defender to use SHA-512 instead of SHA-256.


Pohlig-Hellman Algorithm: Adding up the solution via CRT

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.


A SHA-256 implementation usable on several blocks can be turned it into an HMAC-SHA-256 implementation usable on several blocks, as follows:

If the key is larger than 64 bytes, replace it by its 32-byte SHA-256 hash; now the key is at most 64-byte long.
Start a SHA-256 hash.
Set a 64-bytes buffer to all 0x36; XOR the key into that buffer (leaving unchanged any byte past the key length); hash that buffer.
Hash the blocks of data to authenticate (as several blocks if necessary).
Finalize the hash of steps 2/3/4, giving the 32-byte T.
Start another SHA-256 hash.
Set a 64-bytes buffer to all 0x5c; XOR the key into that buffer (leaving unchanged any byte past the key length); hash that buffer.
Hash the 32-byte T.
Finalize the hash of steps 6/7/8, giving the desired 32-byte result.

That simply applies the definition of HMAC.


Why we use a fixed inverse Multiplication Matrix in AES

The matrices are inverse of each other. Specifically, we work in a vector space of dimension $4$ over the finite field $\mathbb{F}_{256}$. That finite field (also often denoted by "GF(28)", with "GF" meaning "Galois field") is the one defined in section 4 of the AES standard. From there, matrix inversion is classic algebra.

Now, about the process... These matrices have been defined in the following way:

The AES designers thought real hard to make matrices that ensure good security properties, in particular proper behaviour with regards to differential cryptanalysis, while at the same time trying to achieve good performance for a large variety of implementation strategies, notably hardware circuits. Not all matrices are equivalent to each other in terms of security, by far.
Since it is actually nigh impossible to guarantee that you did not goof up with the security analysis, the only known method to get some decent security is to show your creations to hundreds of other cryptographers and have them mull over it for a few years. In the case of AES, this was organized as the AES competition.

Therefore, if you want to set out and "change the matrices", then, rationally, you would have to follow the same process:

Think real hard about the properties you want to achieve, and find matrix values that fulfill them.
Somehow induce hundreds of other cryptographers to themselves think real hard over your creation.
Wait for a few years.
If none of these cryptographers has found anything bad in your new matrix values, then rejoice! Process is done.

Understanding the maths behind finite fields and matrix multiplication are merely the first step of a very long journey.


Quoting the original answer at StackOverflow

  Haven't got enough time to look up the details, but I would guess that you're applying (or not applying) padding correctly. That would cause the right result to come up for some input lengths, but not for others.

  I guess I'll look into this more, but I wanted to get something in under the bounty wire :)

  Edit: Ok, found an error. Not sure why you're getting it, but if it's fixed, then the right answer comes out. In your not-working example, you calculate w (s^-1 mod q) as

 w =  702955297882281869313155599553522395227576660460 // s^-1 mod q

  but I get

 w =  702955297882281869313155599553522395227576660458

  off by 2! Really, really close values though. And it can be shown that mine is right:

s * your_w mod q = 308227306159276200906356361486529830038073078504

s * my_w mod q = 1

  If you plug in this w value, you then get

u1 = 536931432138658080437983667536052790245747416035
  u2 = 591698847955233800072578903940910445457030802333
  v = (g^u1 * y^u2) % p % q = 666804200764671083282351405489424949903645052927
  r == v

  Hope that helps.


It is wanted a partial collision (over $b=32$ bits) between hashes of strings starting in distinct strings 1 and 2. I won't directly answer homework, but my hints outgrew a comment.

The solution presented should work, though details allowing to output the colliding strings are left out, and there are inefficiencies. Towards guiding optimization, I suggest estimating (perhaps, in big-$\mathcal O$ notation)

the expected number of steps in the algorithm,
the expected cumulated size of the hashed strings;
the expected number of insertions (and searches);
required memory size (which depends on the aforementioned details).

If 4 becomes outrageous, be smarter: minimize what's in the dictionarie(s), and make a second hash pass to detect the other colliding string; or store a value allowing to reconstruct that string, rather than the string itself.

You'll find that 2 suggests that (at least when $b$ grows), the naive method of obtaining the hash of a string by hashing it from the start dominates the cost of the calculation. That can be fixed in at least two ways: hashing shorter strings (hint: as suffix, combine space and some other character with similar rendering, such as non-breaking space); or if that's not allowed, being smarter at computing the hash of long strings with the same start (hint: keep appropriate hash states).

After these tweaks, if insertions and searches in the dictionaries become a serious bottleneck, or if one is tight on memory, or otherwise want to get rid of dictionaries, one can use Floyd's cycle finding algorithm with an appropriately defined function (hint: craft a function $f$ over $\{0,1\}^b$ such that finding a collision for $f$ solves the problem with odds about 50%). This is a great way to solve the problem, although it requires somewhat more hashes than techniques using a dictionary.

If $b$ grows to the point that the hashing needs to be distributed, see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website).


Digital Signature Algorithm signature creation?

It depends how you define what a "public key" is.

Typically it is the value of the key itself ($y$), plus information about the group (safe prime $p$, subgroup size $q$, generator of subgroup $g$). For signing a message, you do not need the value of the public key itself. So if you are strict in defining a "public key" to only be $y$, it is not needed to sign (only to verify).

On the other hand, you do need the group description ($p,q,g$) to sign a message, as well as the secret key ($x$). If you are liberal and define "public key" to include the group description, then the public key (or parts of it) is needed to sign.

I am not sure what is meant by PU$_\mathrm{G}$ in the diagram, but I suspect it is the group description? In that case, Stallings is being liberal in his definition of a public key in that it includes the group information ($p,q,g$).

As an aside, even though you do not need the public key, you do need $g$ and $x$ and since $y=g^x$, you do "know" the public key at signing time even if you do not use the value $y$ explicitly.


Why is multiplication uncommon in cryptographic primitives?

There's at least 5 reasons why multiply is not more often used in symmetric ciphers and hashes:

For use as mixer, multiplication requires more hardware/energy/time than other hardware constructs of comparable cryptographic interest. This is an argument mostly for hardware implementations, but many ciphers (and a few hashes) are designed so as to be fast in hardware (that was the explicit implementation target for DES, and an explicit target for AES, which often is in hardware nowadays).
It is far from universal (and used to be uncommon) that wide multiplication is single-cycle, and the number of cycle(s) listed might not be the end of the story; often there is latency, and that cost extra cycles if the result is used for the next few instructions (for x64 otus pointed this source, the same applies to some ARM).

Worst there is often timing dependency on one operand (opening an avenue for timing attacks), and no way to control which operand from the comfort of a high-level language (other than by forcing some high-order bits in both operands). For example, the common 32-bit ARM Cortex M3 has UMULL (32x32->64-bit result) documented as requiring 3 to 5 cycles, with

  early termination depending on the size of the source values.

Multiplication only does bit mixing to the left: if $C=A\;B$ then bit $C_j$ is independent of bits $A_i$ and $B_i$ for any $i>j$. Fixing this requires computing the product with more precision than its operand (and some post-processing), which might not be fast/easy in high-level language.
Multiplication by a constant is linear, and ciphers require non-linearity. While some derivatives of multiplication (like squaring) are not linear, multiplication as the sole source of non-linearity could open to algebraic attacks.
As pointed in  comment, when truncating the result of a multiplication (effectively working modulo some power of two), $F_A: B\mapsto F_A(B)=A\;B\bmod 2^k$ is a bijection only for odd $A$, and can loose a lot of entropy for other $A$, which is undesirable in a normal mixer.

The only widely used cipher I can name that heavily uses multiplication other than by constant is IDEA, where it is followed by modular reduction modulo the prime $2^{16}+1$, in order to fix issues 3 and 5.

Multiplication is in wide use in asymmetric cryptography: RSA, DSA, Elliptic Curve cryptography over a prime field..


Is it safe to use shared secret as a symmetric key in one way communication?

Consider a device A and a device B. Let me paraphrase what I believed you just said.

Communication happens only from A to B. We have public keys $PK_A$, $PK_B$, and the private keys $PrK_A$, $PrK_B$.

Devices A and B apply the Diffie-Hellman key exchange protocol to obtain a shared secret, $SS$. You say that it is logical to use $SS$ as a key for AES symmetric cryptography. It is sensible that the shared secret obtained from the DH protocol is used to derive symmetric keys from.

You say that the shared secrets derived from DH are not uniformly distributed. This is indeed the case. Hashing the obtained shared secret will solve this, as any different shared secret will produce a vastly different digest. $K_{AB} = H(SS)$

Let $r$ denote a random number. You propose $H(SS|r)$ (appending pseudorandom numbers, then hashing it) but this is will not result in a differently distributed digest space than omitting the $r$. You'll have to communicate $r$ to $B$ as well so there is no security gain but only a costs increase.

You also said that in the case of $K_{AB}$ being compromised, at least one of the devices must change its key pair. To my understanding this is not true. A new Diffie-Hellman key exchange can take place with different domain parameters, since the private keys of A and B are not compromised in this scenario.


Yes, there is an important one; The Non-Reputation;

Non-repudiation refers to a situation where a statement's author cannot successfully dispute its authorship or the validity of an associated contract

The HMAC key is a symmetric key therefore there is no non-repudiation. Both sides can not claim that the other side sends them the message $m$. I.e. They both can forge messages and claim that the other side sent them.
In the RSA case, the signer uses their private key and the receiver verifies it with the singer's public key. Therefore, the sender can not refute the message and this can be used as proof in the courts. This is the digital version of the physical signatures, signing a paper.
In other words, both have integrity and authentication however only public-keys have Non-Repudiation. HMAC (it is a MAC) protects against message forgery against an attacker who doesn't have the key. Public key protects against message forgery against all except the owner.

HMAC (MACs)
RSA signature (PKCS signature)

Integrity
Yes
yes

Authentication
Yes
Yes

Non-Repuditiation
No
Yes


No, it is not the output size of the PBKDF2. The problem is when you enter an incorrect password the PBKDF2 generates an incorrect key for you with the correct key size. When you perform decryption of the ciphertext, the library will test the validity of the PKCS#7 padding on the plaintext. Since the key is incorrect you will get a garbage message with the padding part is also garbage. The library is throwing the exception of BadPaddingException. With some low probability, you will get no exception but the padding will be correct. Like with $(1/256)$ probability you will get 01 at the end and this will be valid padding although the message is garbage. This is why you need integrity, too.

You should not use the ECB mode, which is insecure, leaks pattern, and even we don't call it a mode of operation.

PKCS#7 padding is also vulnerable to padding oracle attacks on networks. Returning bad padding is not a good idea.

If you want to get rid of padding you can use CTR mode which doesn't require any padding at all. The CTR mode turns a block cipher into a stream cipher where there is no need for padding. Similarly, the CFB and OFB don't require padding/

Actually, all the above modes, ECB, CTR and including the CBC, are an archaic mode of operations of block ciphers. In modern cryptography, we use and advise authenticated encryption modes like AES-GCM and ChaCha20-Poly1305. They provide you Confidentiality, Integrity, and Authentication in a bundle. The AES-GCM internally uses CTR mode inside.

Note 1: In GCM mode never reuse the IV/nonce. The result can be catastrophic.

Note 2: A padding can be applied to the plaintext even there is no access to the encryption key, i.e. padding mechanism is independent of the encryption. Only the block size is required. And reversely, it can be removed from the plaintext.

Note 3: If the reason for the bad padding not clear, then reasons can be;

The IV is incorrect: An encoding/decoding issue or not transmitted at all?
The Key is incorrect: entered the wrong key or used an incorrect password to the KDF.
The encoding: The data sent over the network in binary instead of base64 or similar encoding. Binary data can confuse some protocols.
Data corrupted: The message is corrupted during transmission and you didn't have any mechanism to detect it.


Block cipher fixed points (plaintext equal to ciphertext)

The question makes a number of statements that are incorrect.  It is not correct that a fixed point is guaranteed to exist.  It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist.  Moreover, the existence of fixed points has only an extremely tenuous connection to security.

Assume $E$ is a secure block cipher.  A reminder of standard notation: $E_k(x)$ denotes the encryption of plaintext $x$ under key $k$ using this block cipher.

Here are some results on the number of fixed points, for different mappings derived from the block cipher $E$:

If we fix a key $k$ and look at the mapping $x \mapsto E_k(x)$, then we expect this to look like a random permutation.  The expected number of fixed points in a random permutation is 1, but this number varies from permutation to permutation.  The probability that a random permutation has no fixed points is $1/e \approx 0.37$.  For more facts on fixed points of a random permutation, see Random permutation statistics.
If we fix a plaintext $x$ and look at the mapping $k \mapsto E_k(x)$, then for most modern block ciphers we'd expect this to look like a random function.  If the key has the same size as the ciphertext, then the expected number of fixed points (treating it as a random function) is again 1.  The probability that a random function has no fixed points is again $1/e \approx 0.37$.

See also Does AES have any fixed-points?, and also The Ideal Cipher Model (wonky) on Matt Green's excellent blog.

The reason a longer key provides extra security has nothing to do with fixed points.  It has to do with the fact that a longer key provides better resistance against certain other attacks (e.g., brute-force keysearch).

In short: I think you are laboring under some misconceptions about the existence of fixed points in block ciphers, and their relevance to security.


Is Encrypt(m||k2, k1) secure authenticated encryption?

Would it not be easier simply to send $E(m||s,k)$ where s is a salt shared across the system?

Yes, that would be simpler; however, that would not (in general) be secure.

The assumption you are making is that if someone modifies the ciphertext in any way, then the last few bits of the resulting plaintext must also be modified.  This is often not the case:

If we are using CTR mode, then someone modifying byte $i$ of the ciphertext will cause byte $i$ of the plaintext to be modified, without any other changes.  So, the attacker can avoid this protection by simply limiting his changes to the first part ($len(m)$) of the ciphertext
If we are using CBC mode, then someone modifying block $i$ of the ciphertext will cause blocks $i$ and $i+1$ of the plaintext to be modified; assuming that attacker does not modify that last two blocks of the ciphertext, his modifications will be undetected.


What was the problem in the SSL version 2.0?

RFC 6176 lists four reasons why SSL 2.0 must not be used, in its section 2:

  Message authentication uses MD5 [MD5].  Most security-aware users
    have already moved away from any use of MD5 [RFC6151].
  Handshake messages are not protected.  This permits a man-in-the-
    middle to trick the client into picking a weaker cipher suite than
    it would normally choose.
  Message integrity and message encryption use the same key, which
    is a problem if the client and server negotiate a weak encryption
    algorithm.
  Sessions can be easily terminated.  A man-in-the-middle can easily
    insert a TCP FIN to close the session, and the peer is unable to
    determine whether or not it was a legitimate end of the session.

However not all reasons are equivalent in gravity. The main security issue with SSL 2.0 is that it has no notion of verified closure: the SSL 2.0 connection ends when the underlying TCP connection is closed. An active attacker can force that, and neither client nor server can know whether the closure is really what the peer wanted. This is a problem when the protocol within the SSL tunnel uses the closure in a semantic way; e.g., with HTTP when there is no Content-Length header or chunked encoding (a rarity nowadays).

The three other reasons are less imperious, and can be debated:

Though MD5 is thoroughly broken with regards to collisions, it still is quite strong when used in other ways, e.g. to build a MAC (as long as you do it properly). You should not use MD5 in new designs, but that does not mean that MD5, as it is used in SSL 2.0, can trivially be broken (or even non-trivially).
Through the lack of protection of the handshake messages, attackers can force client and server to use a weaker cipher suite than what they could have used -- but one could say that the real issue here is that the client and server agree to use a weak cipher suite at all.
Indeed, when the negotiated encryption is weak (a 40-bit "export cipher"), the MAC key is equally weak. But, there again, if the client and server agree to use weak crypto, they only get what they deserve.

Apart from that, SSL 3.0 is more extensible and offers extra features:

SSL 3.0 supports more generic key exchange mechanisms, such as Diffie-Hellman (SSL 2.0 is RSA-only). In particular, this opens the possibility of ephemeral Diffie-Hellman, which grants forward secrecy, a nice thing to have.
SSL 3.0 allows for re-handshake: doing a new handshake within the context of the first. This allows for things such as requesting certificate-based client authentication conditionally, based on what was previously exchanged over the connection.
SSL 3.0 supports optional compression (not always a good idea, but sometimes a nice thing to have).
SSL 3.0 is extensible with room to put extensions in the ClientHello and ServerHello. This has been used extensively, e.g. to fully support elliptic-curve cryptography.


AEAD without explicit authentication tag

As discussed in RFC 5116, AEAD is the tuple of encryption and decryption function:

An encryption function that takes a key, a nonce, a plaintext and a header (associated data), and produce a ciphertext and a tag.
A decryption function that takes a key, a nonce, a ciphertext, and a header, and produces either 1) the plaintext, or 2) decryption failure indication.

The tag part you're concerned with is used to verify the decrypted plaintext (roughly speaking).

However, there's a requirement that can sometimes be a pitfall in the real world: the nonce must be unique for most AEAD algorithms to be secure. So the clever people invented "deterministic authenticated encryption" (DAE in short, a.k.a. key-wrap in some contexts). These encryption algorithms advertise the property of "misuse-resistance".
And AES-SIV is one such example.


Perfect Secrecy for two distinct messages

Let $m_i := 0$ and $k_i := \langle 0, 1 \rangle$. Then $c_i = Enc_{k_i}(m_i) = m_i \oplus k_{i0} = 0\ \oplus\ 0 = 0$. But then $m'_i = Dec_{k_i}(c_i) = c_i \oplus k_{i1} = 0\ \oplus\ 1 = 1$, and we have $m_i \neq m'_i$. The same holds for $m_i := 1$ and $k_i := \langle 1, 0 \rangle$. So your encryption scheme might give perfect secrecy, but it does not allow you to decrypt the message.

This is because your encryption scheme effectively loses information from the message when encrypting with a key of $k_i = \langle 0, 1 \rangle$ or $k_i = \langle 1, 0 \rangle$, and for these keys the ciphertext $c_i$ is solely determined by the key:

$Enc_{\langle 0, 1 \rangle}(0) = 0\ \oplus\ 0 = 0\\
Enc_{\langle 0, 1 \rangle}(1) = 1\ \oplus\ 1 = 0\\
Enc_{\langle 1, 0 \rangle}(0) = 0\ \oplus\ 1 = 1\\
Enc_{\langle 1, 0 \rangle}(1) = 1\ \oplus\ 0 = 1$

If you reduce the keyspace to $\mathcal{K} = \{\langle 0, 0 \rangle, \langle 1, 1 \rangle\}^l$ you effectively have a regular one-time pad.


Practical sources of entropy on an Android device?

Just use SecureRandom and let the OS take care of it.


what is the impact of smaller bit size sbox

the differential property , linear property , algebraic order is larger for 8 bit s-boxes compared to 4 bit s-boxes.

The optimal differential/linear  probability is 2^-6 for 8-bit s-box while it is 2^-2 for 4-bit s-boxes, therefore less number of active s-boxes needed (less rounds) to achieve minimum differential/linear security bound using 8-bit s-boxes.

However, 4-bit s-boxes are good for light implementation and threshold masking to resist side channel analysis.


Yes, you have control over $32$-byte key + $8$-byte nonce + $8$-byte counter totalling to a $384$-bit key and this is perfectly safe.

Your only responsibility for this function is to ensure that the $(\text{Key}, \text{Nonce})$ tuple never repeats. The PRG will increment and wrap the counter so this may start randomized. You can still increment the nonce. You could (but probably shouldn't) increment the key.

Alternatively you can use the much more standard IETF variant of chacha20 with a 96-bit nonce and $32$-bit counter or the Xchacha20 variant with $192$-bit randomized nonces and no exposed counter.

Edit: How are we certain that chacha20 is not capped to 256-bit security?

The constants, key, nonce and counter are all treated equally such that a $1$-$2$ bits changing in the counter is safe. The constants exist to weigh the control of the function away from the adversary. The adversary can control the $8$-byte nonce and $8$-byte counter, not the $32$-byte key nor $16$-byte constant. $16 / 64 = 1 / 4$. If the adversary could control the constants then they have $1 / 2$ of the input. A full $384$-bit key gives the adversary only the public constants worth of knowledge (and they know the counter increments). A $512$-bit key means the adversary knows no inputs.


Using zk-snarks to check if value is greater than another

To do range proofs with zk-snarks, you have to compute an inequality over an arithmetic circuit. The way this is done is by subtracting the two numbers and then checking if the result is negative.

For example - say you want to see if 3 < 10.

You calculate 3 - 10 = -7
Do a bit decomposition of -7 using 2's compliment. The result is 100111.
The first bit of the result is 1, so output 1, signifying that yes, 3 is smaller than 10.

Zokrates has inequalities built into their DSL, so you can use this out of the box.

While this is doable, using proof systems that are catered specifically to range proofs is often beneficial. For example, Bulletproofs have a batching mechanism for range proofs, so if you do enough of them, its proof size becomes comparable to Zk-Snark protocols. Since bulletproofs do not require a trusted setup, this can end up saving you a lot of computation time overall.

Current implementations of bulletproofs include a rust implementation, a haskell implementation, and this summary).