Why is a MAC verification algorithm required when we can simply create a new MAC and compare the received one with the one calculated?

Signing and signature verification are concepts related to public key cryptography.
In case of message authentication codes, there is a single secret key and one function:
T = MAC ( K, M )

Where:

T - tag
MAC - MAC function
K - secret key
M - message

Messages can be signed by either the client or the server and verified by the other, depending on the case. Both parties calculate MAC the same way, using the same function and secret key, over the same message. There is no separate function for MAC verification. The only extra step on the receiving end is associated with comparing if both received and calculated tags match, and then acting accordingly. But this has nothing to do with a MAC algorithm itself.


Why isn't this HMAC construction/check secure?

OK, there are two issues with this:

First, the MAC length is at most 64 bit, that is an attacker could try to brute-force-find a valid MAC with "merely" $2^{64}$ submissions, which is border-line feasible for large companies today.
If it actually only is 8 hex character, then each hex character encodes at most 4 bits of information and thus you get $8\cdot 4=32$ bits for the MAC security meaning brute-force would take at most $2^{32}$ (around 4bn) tries to recover a valid MAC.

Second, much more severe is the naive verification of the MAC which will probably allow for a classic timing side-channel attack.
Chances are that this multi-byte equality verification is implemented as an "optimized" check, that is (in a python-ish way):

if len(lb)!=len(rb):
   return false
for (lb,rb) in zip(l_input,r_input):
   if lb != rb :
      return false
return true

Which checks the that the input lengths match and then pairs all the bytes at the same position in both inputs and outputs false as soon as a miss-match is detected and true if no missmatch is found.

Now what we can do is to measure the time it takes to verify our MAC. So we would start of with 7 0 characters and prepend each possible value (character) value to this string. We send all to verification. The one that takes longest has a match on the first character. Now we fix this first character that we just verified and continue with the second with the same method. We continue with this process until we have recovered the full MAC and get access in return.

If we get all-equal times for the first character, we take iterate over all possible choices for the first two characters (enlarge as needed). If we know the size of the information $b$ (in bits) encoded in the constant-time verification data structure (eg 8 for byte-wise, 32 for integer-wise, ...) and we know the mac information $l$ in bits, then we take at most the following amount of calls to the verification oracle to recover the valid MAC:

$$n=2^b\cdot(l/b)$$

If in your case 8 hex characters need to be verified this becomes $2^4\cdot 8=256$ calls to the verification oracle (because the effective information of the hash is 32 bits composed of 4 bit elements).


Can the key-complement property of DES be used against 3DES?

yes,it is possible because in meet in the middle attack on 3DES,see below

with Complementation Property of DES in red arrow,you can search $2^{55}$ key space instead of $2^{56}$,and for green arrow,you have $DEC_{K2}(ENC_{K1}(M))$ that without key Complementation Property,you need $2^{112}$ operations but with key Complementation Property of left ENC and middle DEC block,you need $2^{110}$ operation and in total you need $2^{55}+2^{110}\approx 2^{110}$ operations

NOTE: in green keyspace(arrow), you should calculate one encryption and then one decryption for your known plaintext,for both decryption and encryption of DES,if you test one pair key($K_{1}$ and $K_{2}$) and calculate the middle variable,because of Complementation Property of DES,you don't need to have a decryption and encryption for $K'_{1}$ and $K'_{2}$ so with every calculate of $DEC_{K2}(ENC_{K1}(M))$,you test 4=$2^2$ keys


BSGS algorithm requires huge storage space for curves with large order. This storage requirement usually exceeds the total available storage capacity across the whole world by several orders of magnitude.

So, finding an estimation depends on how much memory is available for you. Since you need to store all the generated points in a hash table for BSGS.
If each point requires k-bits of storage and the curve is of order n, the storage requirement is $k * \sqrt{n}$ bits.

Eg: If each points require 32 bits of storage and the curve has order $10^9$ then total storage requirement is approxmiately 4 GB.


Why is the IV passed in the clear when it can be easily encrypted?

Depending on the mode of operation, transmitting the IV encrypted (with the same key as used for the rest of the process) can actually weaken security a lot.

For example, in the CFB and OFB modes, the IV is encrypted and the result XORed with the first block of the plaintext to produce the first block of ciphertext.  Thus, an adversary who knows the encrypted IV can trivially undo the XOR to recover the first block of plaintext!  The same is true for the CTR mode, if the IV/nonce is used directly as the initial counter value.

The CBC mode works differently, and does not break as catastrophically if you encrypt the IV before transmitting it.  However, as Henrick Hellström has pointed out, knowing the encrypted IV still lets an adversary figure out whether the first block of the plaintext consists of all zeros.


Is there a length-preserving encryption scheme?

As @fgrieu mentioned, what you're after is FPE. The papers he linked deal with FPE on a very small domain, but it looks like you're interested in encrypting longer strings.

For that, you need a wide block cipher. Unlike traditional blockciphers, these typically allow different input lengths, which is a plus. They meet your criterion of not revealing shared prefixes/suffixes. Examples (any of which will be secure): EME, EME2, HCTR, HEH, TET, PEP. Tracking down a good implementation might be problematic; I don't know any off-hand. Some, including EME/EME2, are patented (but can be licenced under "reasonable, non-discriminatory" terms). Depending on the mode, they operate at roughly half the speed of standard encryption algorithms.

In terms of providing confidentiality, a result by Bellare and Rogaway ("Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography") shows that you get it for free as long as you can guarantee that all plantexts are distinct (e.g., they already have distinct sequence numbers encoded into them somehow). The only information these ciphers leak is plaintext length, and whether or not a plaintext is repeated.

You said authenticity was not a concern, but perhaps it's worth noting that you can get this fairly cheaply if the plaintext contains some type of redundancy that you check upon decryption.

Finally, these algorithms are tweakable ciphers, which means the take an additional input, called the tweak. You can use (meta)data from any accompanying headers as the tweak (or just used a fixed string). Again, if the tweak is distinct each time, then you have confidentiality even if a plaintext is repeated. But at that point it might be easier to, e.g., take a 64-bit nonce from the headers and use that as the high-order bits of a counter-mode IV.


Reason for 3 rounds ChaCha in ChaCha20Poly1305@openssh

The point of having two ChaCha instances is to make sure that one cannot be used to attack the other. From the draft RFC:

  Two separate cipher instances are used here so as to keep the packet
     lengths confidential but not create an oracle for the packet payload
     cipher by decrypting and using the packet length prior to checking
     the MAC.

Using the unused part of the first block from the same cipher instance as used for the rest of the construction would not seem to allow any kind of attack in this case, because that would always be the same part of the keystream, which is never used for anything else. I guess the proof of independence is easier with two cipher instances, but I suspect it is more about simplicity and extensibility.

By having a separate instance, you can easily decrypt the packet length separately using normal cipher interfaces, without adding any offsets. And by treating the encrypted packet length as additional data for the MAC, you get to use the normal process of verifying the MAC, without needing to decrypt it.

This way is also more extensible if there is a need for more than 32 bytes of additional data. It seems from the author's blog post there are some plans to extend this protection of packet lengths. Maybe that will require more additional data to be outside the main packet to allow earlier processing:

  We're not done yet though - an attacker may still observe the encrypted packets on the network to try to ascertain their length, and right now they are likely to be successful. I hope to add some features to frustrate this sort of traffic analysis some time next year.

I.e. to answer your question explicitly, no, I do not think it is more secure to have a second cipher instead of using the unused 32 bytes. It seems there may just be other practical reasons to do that.


Imposibility of bias-resistant coin tossing (Cleve'86) and its connection to modern notion of fairness in Secure Multiparty Computation

First, I'll discuss Cleve's result really quickly, as there's a natural generalization of it which may be useful for your understanding.
Let $X\sim\mathcal{D}$ be some random variable.
A common notion in sampling random variables is rejection sampling. You have some predicate (function which returns true or false) $\phi$, and you want to sample $X\sim\mathcal{D}$ such that $\phi(X)$ holds.
This is to say that you want to sample $X\sim\mathcal{D}$ from the conditional distribution $X\sim\mathcal{D}\mid \phi(X) = \mathsf{true}$.
You can do this by continuing to sample $X\sim\mathcal{D}$ until you get one where $\phi(X)$ holds. This takes roughly $1/\Pr_{X\sim\mathcal{D}}[\phi(X) = \mathsf{true}]$ samples (so predicates that hold with low probability require "more samples", as you'd expect).
Cleve's result is just noting that an adversary can do this in an interactive protocol via aborting the computation.
Say you have an interactive protocol where each round a single person talks (you can let them broadcast things if you want), and there are $k$ rounds.
Then in the $(k-1)$th round, there's a single participant (call them $P$) who will not hear anything from other participants during the rest of protocol. They already know what their result will be.
To show that fair coinflipping is impossible, you just need to argue that $P$ can rejection-sample on their output value until it is whatever they want it to be, so they can fix the mutually-shared random variable (at the end of the computation) to be whatever they want (but the lower-probability the result they want to occur is, the more aborts they need to do).
To show that fair computation is impossible, you just need to argue that $P$ already knows their value, and via aborting the protocol can withhold relevant information from the other parties in the protocol.
So the two results (impossibility of unbiased randomness generation in interactive protocols, and impossibility of fair computations) come from slightly different arguments, but both of them rely on the existence of one person who is "done with the computation but still needs to talk to other people so they can finish the computation", which is intrinsic to interactive protocols of this form.


What are the standard properties of an S-Box

Another very common criteria for an S-box with $n$ input bits and $m$ output bits with $m\le n$ (as most commonly used S-boxes are) is that each of the $2^m$ output values should be reached for exactly (or at least near) $2^{n-m}$ input values.

The question's criterion 1 can be made strict and become the Strict Avalanche Criterion. There are even stricter /higher-order versions. There also is the Bit independence criterion. The desirability of these properties depends on the overall design of the cryptographic construction using the S-box, and is not easy to assess.

More generally, S-boxes are typically optimized with use as part of a particular cryptographic construction in mind, aiming at improving it's overall resistance against cryptanalytic attacks, as pointed in comment.


I will try to give a simple proof of the expectation. Define $W_t(n,p)$ as the expected number of trials required  to find the $t^{th}$ collision in a set of size $n$ with probability $p.$

Normally, for $W_1(n,p),$ the standard birthday problem with fail probability $p,$ which gives $W_1 = c \sqrt{n},$ with $c$ obtained by solving
$$
\exp\left(\frac{-k(k-1)}{2n}\right) = p = \exp( \ln(p))=\exp(-\ln (1/p))\tag{1}\label{eq1}
$$
for $p=1/2,$ and letting the $k$ obtained to be $W_1(n,p).$

So we're after the total expected wait, call it $$T_k=W_1(n,p_1)+W_2(n,p_2)+\cdots+W_k(n,p_k)$$
 with the assumption that $k$ is much much smaller than $n.$ Let $W_i$ denote the expected wait for the $t^{th}$ collision with probability $p_t,$ which we shall select later.

Solving $\eqref{eq1}$ approximately gives
$$
W_1(n,p)= \sqrt{2 \ln(1/p) n}.
$$
Now note that,
$$\begin{align}
W_t(n,p) &=\frac{n}{n-t+1} W_1(n-t+1,p)\\
&=\frac{n}{n-t+1}\sqrt{2 \ln(1/p) (n-t+1)}\\
&=O\left(\sqrt{2 \ln(1/p) (n-t+1)}\,\right),
\end{align}$$
(both sides are expectations)
since there are already $t-1$ collisions and $t$ is much smaller than $n.$
To explain further, this means that you want the next collision in the remaining $n-(t-1)$ positions but the probability of falling into one of those positions is $q=(n-t+1)/n$ so it takes an expected $1/q$ trials.

Now we can write
$$
T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(1/p_t) (n-t+1)}\right),
$$
but due to the multistage nature of the argument, the overall probability that this sequence of waiting times fails to find the $k$th collision is the product
$$p_1p_2 \cdots p_k.
$$
We want this probability to be $1/2,$ as in the original birthday problem, which we can ensure by choosing $p_t=(1/2)^{1/k},$ for all $t.$ This can be optimized a bit by putting slowly falling probabilities on later epochs and keeping the product of the probabilities fixed, but it won't make a difference to the $O(\cdot)$ answer. Since $\ln(2^{1/k})=k^{-1}\ln 2,$ we have

$$
T_k=O\left(\sum_{t=0}^k \sqrt{2 \ln(2) k^{-1}(n-t+1)}\right)=
\sqrt{k} \times O\left(\sqrt{ (n+1)}\right),
$$
which gives (since there are $k$ terms in the sum and a $k^{-1/2}$ multiplying each term)
$$
T_k=O(\sqrt{nk})$$
as required.


Checking the integrity of RSA public key

Can I compute the only hash of the modulus for integrity?

Well, if we allow the attacker to modify the value of $e$ you use (because it's in untrusted storage and you don't verify it), how can he exploit that?  Well, the most obvious approach for him would be to modify $e$ to be the value 1; that would make generating forgeries really quite simple.

Now, if your signature verification software prohibits $e=1$ (and doesn't parse $e=-1$; likely it doesn't); well, it might be safe, as generating alternative values for $e$ where the attacker does know the $d$ value is equivalent to factoring, and there is no other known way to take $e$-th roots that's not equivalent to factoring.  This is, of course, assuming that your PKCS #1 1.5 signature verification code does all the checks; if not, then (depending on which checks are skipped) it's known to be possible to generate a forgery that passes the partial checks with $e=3$.

On the other hand, why take the risk?  It's easy enough to include $e$ in the hash, and that avoids the question entirely.  Alternatively, you can just bolt in $e=65537$ in your verification code; in that case, the attacker can't change it.


Is FIPS 140-2's "Continuous random number generator test" practical?

This requirement is a part of the general "continuous tests", and as such it's primary purpose is to detect "flatline" failures (if you can torture that analogy into making sense). Remember that FIPS-140 was originally written with hardware implementations in mind, so the approaches they take for testing sometimes seem odd for software since hardware failures tend to be different from software failures.

I don't think there's a problem, though. You could choose $n = 16$ and potentially have statistical problems, but you don't have to pick something that small. Build your construction to output the size block that you want it to. Eg, modern constructions like CTR_DRBG from SP800-90 output 16 bytes at a time, which is well outside statistical concern.

Also, you're probably not certifying a TRNG, since there are no non-deterministic RNGs that can be certified.


Which sub operation is more expensive in the AES encryption process?

The table lookup implementations usually combine the SubBytes and ShiftRows steps with the MixColumns step.
Different implementations/hardware/etc make general statements impossible, but this paper gives some  benchmarks and information on a table-lookup implementation.
It won't necessarily be quicker across all systems.  As per this paper:

It must be noted, anyway, that using a large amount
of memory for the look-up tables is too expensive for small systems, like for
instance smart cards, and is considered unsafe, as monitoring the accesses to the
look-up tables may in some cases allow to infer the key.

As an aside, another (better) way to speed up AES is to have the instructions built into the hardware


Man-in-the-Middle attacks are possible for almost all zero-knowledge proofs. Victor can copy everything sent by Alice, the prover, to Bob, the verifier, and reversely to impersonate the Alice. In short, Victor can relay every message.

To mitigate this, time limit can be used to prevent the relay. However, this may not be enough.

A better solution is first creating a secure channel that is free of MitM attack and then use the Fiat-Shamir protocol.


Why is SIV a thing if MAC-and-encrypt is not the most secure way to go?

Skimming these three papers should give you an idea (which I list roughly in the order I recommend you look at them):

Rogaway, Philip.  2004.  "Nonce-based symmetric encryption."
Namprempre, Chanathip, Phillip Rogaway and Thomas Shrimpton.  2014.  "Reconsidering Generic Composition."
Bellare, Mihir and Chanathip Namprempre.  2000.  "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm"

To make a long story short, results about generic composition of encryption and authentication are very sensitive to how you define the concept of "encryption."  In a classic textbook definition, encryption schemes are defined in terms of probabilistic algorithms.  As the Rogaway paper puts it:

  Ever since Goldwasser and Micali’s landmark paper [7], formalizations of encryption schemes have usually made the encryption algorithm probabilistic or
  stateful. In this paper we investigate a different formalization for symmetric encryption: the encryption algorithm is made to be a deterministic function, but
  one of its argument is a user-supplied initialization vector (IV). Effectively, the user and not the encryption algorithm is made responsible for flipping coins or maintaining state.

The Bellare and Namprempre's famous result that encrypt-then-MAC is the only secure composition uses the classic, probabilistic framework for encryption.  But if you start from Rogaway's IV- or nonce-based definitions, as the 2014 Namprempre et al paper does, you get more nuanced results.  Some but not all versions of MAC-and-encrypt—including SIV—turn out to be secure, whereas all versions of encrypt-then-MAC are secure.  As the paper puts it:

  One might interpret our results as saying that the conventional wisdom—that Encrypt-then-MAC is the only safe GC method—is wrong, an artifact of early work having admitted sloppy schemes and considered only pE+MAC → pAE conversion. An alternative interpretation is that the conventional wisdom is essentially right, that Encrypt-then-MAC is the only safe GC method, for it works across multiple definitional settings, whereas the story becomes nuanced for other GC schemes.

  Nothing in this paper should be understood as suggesting that there is anything wrong with BN. If that paper has been misconstrued, it was not for a lack of clarity. Our definitions and results are complementary.


If the key bits are shorter then the message you need to reuse some part of the previous key bits. If this is known, and we can assume by Kerckhoff Principles,
then the enemy can crib-drag on the same message. A more dedicated enemy will always try this case and also the reuse case; the same key is used with another message, too.

As an example;

m = xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
k = KkkkkkkkkkkkkkkkkkkkkkkkKkkkkkkkkkkkkkkkkk

where $x$ represents the message bits, $k$ represents the key bits and $K$ represents the start of the key bits. Divide the message into parts;

m1 = xxxxxxxxxxxxxxxxxxxxxxxx
k  = Kkkkkkkkkkkkkkkkkkkkkkkk
m2 = xxxxxxxxxxxxxxxxxx
k  = Kkkkkkkkkkkkkkkkkk

now, execute crib-dragging.


The likelihood of a decryption failure can be made arbitrarily small. IEEE P1363.1 says in appendix A.4.10:

For ternary polynomials with $d$ $+1$s and the same number of $-1$s, the chance of a decryption failure is given by [B30]:
$$\operatorname{Prob}_{(q, d, N)}(\text{Decryption fails}) = P_{(d, N)} \left( \frac{q - 2}{6} \right)$$
where
$$P_{(d, N)}(c) = N \times \operatorname{erfc} \left( \frac{c}{\sigma\sqrt{2N}} \right)$$
and
$$ \sigma(d, N) = \sqrt{\frac{8d}{3N}}$$

where $\operatorname{erfc}(x)$ is the Gauss error function.
As a practical example, for the EES1087EP2 parameter set where $N=1087$, $q=2048$, and $d=120$, the failure probability is $5.62·10^{-78}$, which is a bit less than $2^{-256}$. Those parameters have been chosen for a $256$-bit security level in general, and the failure probability is also smaller than $2^{-256}$. So exploiting a decryption failure requires just as much work as breaking other parts of the system.
Ps. The [B30] reference is to the paper "Hybrid
Lattice reduction and Meet in the Middle Resistant Parameter Selection for NTRUEncrypt" by P. Hirschhorn, J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman and W. Whyte.


How should I address message size limits in RSA encryption?

I should be able to safely encrypt and decrypt any number with bit lengths L < 513 (256+257) without losing information. Is this correct[?]

No.  The RSA operation $x \mapsto x^e \bmod n$ is unfit to ‘encrypt’ even short messages directly.

Here is what you should do:

Pick a hash function $H$ up front, like SHA-256 or SHAKE128, and bake it into your program.  (Don't let users pick it—users have even less of an idea of what's up.)
Pick a symmetric-key authenticated cipher up front, like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305, and bake it into your program.  (Again, don't let users pick it.)
To encrypt a message $m$, which is a bit string of arbitrary length, for public key $n$:

Choose an integer $x$ with $0 \leq x < n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = H(x)$, where $x$ is encoded as a bit or octet string in some standard way, e.g. little-endian.
Encrypt $m$ using your authenticated cipher under the key $k$, giving a ciphertext $c$.
Send $y$ and $c$.  $y$ is called the encapsulation of the key $k$.

To decrypt a ciphertext $c$ with key encapsulation $y$:

Solve $y \equiv x^3 \pmod n$ for $x$.  (E.g., compute $x = y^d \bmod n$ where $d$ solves $e d \equiv 1 \pmod{\phi(n)}$, or compute $x_p = y^{d_p} \bmod p$ and $x_q = y^{d_q} \bmod q$, and then combine using the Chinese remainder theorem, etc.)
Compute $k = H(x)$.
Decrypt $c$ using your authenticated cipher under the key $k$.

If decryption fails, drop it all on the floor and stop here.  (If you skip this step, you are setting yourself up for efailure.)
Otherwise, it returns a message $m$, which is the plaintext message you return in the end.

This system—generating a symmetric key $k = H(x)$ for uniform random $x$ and concealing it as $x^3 \bmod n$—is called RSA-KEM, and it is an example of a public-key key encapsulation mechanism, which can be generically composed with an authenticated cipher to get public-key (anonymous) encryption.

  Also if L happens to be a 5-bit number, its encrypted version will still be around ~512 bits long?

With the system above, the ciphertext overhead is 128 bits for the authenticated cipher (or more, if it's a particularly inefficient authenticated cipher), plus the size of your modulus $n$, no matter how long the message is.

You should not use 512-bit moduli.  They have been breakable in practice by the public for decades.  You should use at least 2048-bit moduli.  More details.

Alternatively: Just use NaCl crypto_box, or libsodium crypto_box_seal.  Faster, smaller, safer than RSA!


Predicting value of E(k,0) for Block cipher with random and secret key

A block cipher, according to its design purpose, is assumed to be a pseudorandom permutation. This means when the key $k$ is chosen at random, $E(k,\cdot)$ can be viewed as a random permutation. Then, $E(k,0)$ is indistinguishable from a random value of the block length, hence unpredictable.


Confusion about security of quantum key distribution

You are right and you are wrong. Indeed, in the scenario that you describe Eve would perfectly break the system (in a certain way). She would learn information about the secret key without being caught. Note, however, that this only has any chance of success for a small amount of bits. The chance of success when measuring $x$ qubits is $2^{-x}$ (in this idealized setting ignoring all the implementation attacks). That's why you cannot use the the plain exchanged bit string. Instead, you have to use privacy amplification. There are different methods for this. The main idea is that you use some function to turn a long bit string of which Eve possibly knows some bits into a short bit string about which Eve has no information as long as she did not know a lot of the input bits. Choosing parameters right, you can that way ensure that as long as Eve does not learn more than e.g. $128$ bits of the original bit string the output string (used as secret key later) has e.g. $128$ bits of entropy.


It is a block cipher with block size 3. Therefore for a given known-plaintext, we can build the current key's action table that has $2^3=8$ values. We will use the decryption part $$P_i = D(C_i) \oplus C_{i-1} \oplus P_{i-1}$$ with $C_{0} \oplus P_{0} = IV$ with conversion
$$D(C_i) = P_i \oplus C_{i-1} \oplus P_{i-1}$$
P_i          000 001 010 011 100 101 110 111
P_i-1        ??? 000 001 010 011 100 101 110
C_i-1        ??? 111 110 101 100 011 001 000
--- xor-all
x-ored       ??? 110 101 100 011 010 010 001
C_i          111 110 101 100 011 001 000 010

Now built the decryption table and the encryption table is just the reverse of it.
$$\begin{array}{|c|c|}\hline
\text{input} & \text{output} \\ \hline
\texttt{000} & \color{red}{\texttt{010}}\\ \hline
\texttt{001} & \color{red}{\texttt{010}}\\ \hline
\texttt{010} & \texttt{001}\\ \hline
\texttt{011} & \texttt{011}\\ \hline
\texttt{100} & \texttt{100}\\ \hline
\texttt{101} & \texttt{101}\\ \hline
\texttt{110} & \texttt{110}\\ \hline
\texttt{111} & \texttt{???}\\ \hline
\end{array}$$
With the current information, this question is not solvable since the defined block cipher is not reversible. The PCBC mode requires this.
P.S. Maybe I had a mistake with the simple calculations. If so inform me please;


The exact definition of a symmetric encryption

The short answer is that if your encryption routine is a bijection, then the first is fine. However, if it is not surjective, then you need to define what on earth it means to decrypt an invalid element. This could be done by having elements with multiple preimages (as may occur in schemes using bad/misimplemented padding) or output an error symbol $\perp$.

Below the bar is a longer, rather more rambling answer, as initially posted.

This depends on the encryption algorithms in use. If the encryption algorithm is a bijection, then every possible $C$ must have a preimage. Examples of this include block ciphers like AES. In these cases, the decryption algorithm will output a message $m$ such that $E_k(m)=c$. Note that if $c$ has been tampered with by an adversary but is still the same length, then it will be possible to find a preimage under $E_k$ even though it was not produced as such. That is, in these cases:
$D_k(c)$ returns the unique value such that $E_k([D_k(c)])=c$.
In this case it would be fine to define decryption as having simply the message space as it's codomain.

However, theoretically at least, there is no reason my encryption scheme would need to be surjective (it doesn't need to 'fill' the ciphertext space).
For example, I can define a scheme where the message space $M = \{0,1\}^{128}$ and ciphertext space $C=\{0,1\}^{130}$ such that
$$
c = E_k(m) = 00||\mathrm{AES}_k(m)
$$
This would meet the security promises of AES (after all, it is just an embedding). However, consider the decryption function. Writing the ciphertext as $c=x||y||c'$, where $x,y$ are bits and $c'$ is a 128-bit bitstring, then
$$
D_k(c)=D_k(x||y|c')=\begin{cases}
\mathrm{AES}_k^{-1}(c')  & x=y=0
\\\perp & else
\end{cases}$$
In this case, whilst for all valid ciphertexts we can provide a decryption, there is no way any ciphertext valid can be generated that begins with anything other than $00$. So, when asked to decrypt such a message we must provide some form of error message, the standard for which is to use $\perp$ (as in contradiction).

In the case of authenticated encryption, we design our encryption routines such that it is hard to find an element $c$ of the ciphertext space that has a preimage $m$ unless that we have already calculated $E_k(m) = c$.  In these cases, the symbol $\perp$ demonstrates that the attempted decryption of a ciphertext that does not pass the authenticity check.

A possible reference for further related questions would be Section 2.1 of Katz-Lindell, but note that this is given in the probabilistic model. Most modern AE work is performed in a nonce-based setting.


Verify the discrete log of ECDSA is in range

If you give an attacker $G$ and $P := xG$ with $0<x<2^{64}$ then she can calculate a table with $2^{32}$ entries $yG$ for $0\le y<2^{32}$. Finding for any $0\le z<2^{32}$ the value $P-(z\cdot 2^{32}\cdot G)$ in the table yields $x = y + z\cdot 2^{32}$. Space complexity is $2^{32}$ entries and time complexity $\le\log_2(2^{32})\cdot 2^{32}$.

That's why user679128 uses a blinding scalar $b$.


Is it possible to figure out the public key from encrypted text?

Actually, if Eve does have access to Alice's plaintext messages (and Alice doesn't do random padding as she should), then yes, Eve does have a chance, even with only two messages.

Suppose she guesses $e$ (the public exponent), and that it's not a not huge value (say, the common value 65537).

Then, for every plaintext/ciphertext pair $P_i$, $C_i$, she knows that (if $N$ is the unknown modulus):

$P_i ^ e = C_i \mod N$

or, in other words:

$P_i ^ e - C_i = k_iN$

for some integer $k_i$.

So, if she takes two plaintext/ciphertext pairs, and computes the value:

$gcd( P_1 ^ e - C_1, P_2 ^ e - C_2 )$

that is extremely likely to be the value $N$, possibly multiplied by a small integer.  Now, this gcd operation might be on operands of possibly a few hundreds of millions of bits long; not something you want to do every day, but it certainly in the realm of possibility if you're a bit patient.

Now, if Alice does do random padding before doing her RSA encryption, well, Eve doesn't have access to the values $P_i$, so this observation doesn't help her.


Can I use a block cipher in CTR mode to generate keys from a master key?

As Maarten Bodewes points out, you should use a known key derivation function instead of this method (i.e. don't roll your own crypto). Having said that we can still try to understand what happens if you do use this method.

I assume that the method you're describing is something as follows. You take a block cipher $E:\mathsf{K}\times \mathsf{X} \to \mathsf{X}$, and a master key $K\in\mathsf{K}$ and then generate subkeys using
$$K_0 = E_K(0), K_1 = E_K(1), K_2 = E_K(2), \ldots\,,$$
where $0$, $1$, $2$, $\ldots$ are distinct strings in $\mathsf{X}$.

If you only use the subkeys $K_0,K_1,K_2,\ldots$ as keys in the mode, there should not be an issue, since you're basically using the block cipher as a key derivation function. In order to do this, all you need to assume about the block cipher is that it is a secure pseudorandom permutation when keyed with $K$, $K_0$, $K_1$, $\ldots$. This, of course, also assumes that it is meaningful to use the output of $E_K$ as its key, which you can do for AES128, but not immediately with AES256 (you would have to use two block cipher outputs as a key).

However, the downside to the above approach is that you have to switch keys a few times, which might not be so bad depending upon the application, but is undesirable in general. The optimizations performed by modes such as GCM, EAX, and OCB make it so that you do not need to switch block cipher keys. Their trick is to use $E_K$ and the value $L = E_K(0)$ (or something similar) alongside each other in the mode, without ever using $E_L$. In particular, to ensure security this means that the mode needs to avoid outputting $E_K(0)$ as part of a ciphertext or tag, since then you've released $L$ to the adversary.

Just to be clear, neither method will help you against birthday attacks on the mode. As long as the master key stays the same, you will still find attacks with birthday bound complexity. Also, I don't immediately see the benefit in using a longer nonce, since the number of messages you can process using a key is often well below the number of nonces you can generate using half of a block length. For example, your nonce does not need to exceed 64 bits when using AES128 in GCM, since the birthday bound limits you anyway.


In the ideal cipher model, $E_K$ and $K$ are independent, so no amount of information about $E_K$ will tell you anything about $K$ itself.


breaking fully homomorphic encryption schemes

Even though all the operations you described can be performed homomorphically, the result remains encrypted, i.e., the attacker cannot "see" it.  So homomorphic computation is not useful (on its own) as an attack, because the results remain unknown to the attacker.

For example, given two ciphertexts $c, c'$, an attacker can homomorphically compute whether they encrypt the same message.  The result is a ciphertext $c''$ that is an encryption of either 1 ("same message") or 0 ("different messages").  But the attacker cannot decrypt $c''$, so the 0/1 answer remains hidden to him.


Is my protocol that uses hybrid cryptography and AES-GCM secure?

Typically things would go like this:

A generates a random AES key and encrypts it with the public key.
A encrypts the file contents using AES GCM and that key. Nonce can be random or even zero if the key is only used once. AAD can be empty unless something else needs to be authenticated with the file.
A sends over the encrypted key, the nonce if any, and the ciphertext.

The file name only matters if you need to encrypt it too (simplest: encrypt a tar archive instead) or if you need the name authenticated (include it in the AAD).


Difficulty to find the pre-images of a pair of hash result such that given $a,b$, $H(x_1)=aH(x_2)+b$?

Case 1: Assuming $\mathbb{F}_2^n.$ The only scalar constants you can have in characteristic $2$ to are $0$ or $1$? So, you need to define multiplication for quantities in $\mathbb{F}_2^n$ for this to be non trivial.

Let $n=256.$ For any  vectors $b\in \mathbb{F}_2^n,$ your first equation with scalar $a$ is equivalent to

$H(x_2)=b$ if $a=0,$ which takes $O(2^n)$ work (preimage problem).
$H(x_1)\oplus H(x_2)=b,$ which takes $O(2^{n/2})$ work (collision problem).

As for your second equation, it reduces to a quadratic relation which doesn't look meaningful in this context since the multiplication has to be defined for it to make sense.

One can use $\mathbb{F}_{2^n}$ as a representation for $\mathbb{F}_2^n,$ under some canonical basis, maybe a self dual basis, but more cryptographic justification for what you seem to be attempting needs to be provided for such an operation, given that solving quadratics is no easier than solving linear equations.

Case 2: (Thanks to @kelalaka) If you mean to take $\mathbb{Z}_{2^{256}},$ then one might guess that if the hash function is strong, the $a-$multiple $a H(x_1):=H_a(x_1)$ can itself be modeled as a random function and you are now solving a generalized collision problem between two random functions
$$
H(x_2)-H_a(x_1)=b
$$
which again should have complexity $O(2^{n/2}).$

For the second question things are trickier. Firstly there are zero divisors in the ring $\mathbb{Z}_{2^{256}},$ and you should not divide but cross multiply and consider
$$
(H(x_2)-a)(H(x_4)+b)=(H(x_1)-a)(H(x_3)+b)
$$
Let $u_i$ be the largest exponent of $2$ which divides the value $H(x_i)- c_i$ modulo $2^{256}$  where $c_1=c_3=a$ and $c_2=c_4=-b$. If $u_1+u_3\geq 256,$ then we need to have either $H(x_2)=a,$ or $H(x_4)=-b,$ (either happen with probability $2^{-256}$ or $u_2+u_4\geq 256,$ for this equation to have a solution.

Again, modeling these translated hashes as pseudorandom functions $Pr[u_i\geq k]=2^{-k},$ for $0\leq k\leq 255.$ For example, $Pr[u_i\geq 1]=1/2,$ which happens if the LSB of the hash output is 0.

Using this, one can derive actual probabilities for these equations to hold, based on the argument in italics.


Is every pseudorandom generator a one way function?

Prove by contradiction. Assume that it is not a one-way function and that it can be inverted with non-negligible probability. Use this to construct a distinguisher that can distinguish truly random from $G(s)$ with non-negligible advantage. I leave the rest to you...


Is there an encryption format that preserves length and only outputs alphanumerics?

Both of the other answers tackle the question of encryption in a particular format, but I would argue that neither of them is necessarily a good fit for your use case. You want to be able to generate 20 character codes that a server will be able to verify. A symmetric MAC is sufficient for this use case, if you don't need the codes to contain any secret information.

For example, use the format ID||HMAC(key, ID), with ID an arbitrary unique number for each code. You can choose the ID size and then truncate the HMAC to match your length requirements. E.g. 32-bit ID and 168 left bits of HMAC-SHA256. Then encode in the format you want.

IDs can be generated randomly or using a counter or it can include encoded information. The server would store the association between an ID number and whatever the promo code is for etc. An attacker cannot modify a promo code without knowing the MAC key, except by chance with probability $2^{-l}$, where $l$ is the MAC length in bits. You can go as low as $l = 64$ securely. (Perhaps even lower if you make an online guessing attack sufficiently difficult/slow.)


reverse an identicon to its source string

The identicons idea is not bound to some predefined hash, so you will have to look at the specification or at the source code of the specific implementations.

The reversal is obviously is as hard as the hash function used in the particular implementation, if at all possible in case when the identicon representation contains fewer bits than the original data.


A quick look into the PHP code showed that PHP only understands the Tiger hash (the first one with incorrect bit padding).

It also showed that their implementation of Tiger may contain "additional passes", where each pass consists of 8 rounds (only called for values higher than 3). The value of passes is displayed behind the hash function:

#define compress(passes) \
    save_abc \
    pass(a,b,c,5) \
    key_schedule \
    pass(c,a,b,7) \
    key_schedule \
    pass(b,c,a,9) \
    for(pass_no=0; pass_no<passes; pass_no++) { \ <- additional rounds start here
        key_schedule \
        pass(a,b,c,9) \
        tmpa=a; a=c; c=b; b=tmpa; \
    } \
    feedforward

There seems to be no documentation other than this. Don't use cryptographic primitives that lack any description.

I've generated the same C1... hash by adding the 8 additional rounds in a Java application (and then deleted said Java implementation).


HMAC SHA256 vs RSA SHA256 - which one to use

From a security standpoint, HMAC-SHA256 is exceptionally secure, so the move is unlikely to relate much to cryptographic security unless they were using the construction incorrectly, which is improbable.

I freely admit that I know almost nothing about Salesforce, but I can guess at the rationale behind the decision: since HMAC is a symmetric primitive, both sides of a channel need to have a shared, private key. With an asymmetric primitive like RSA, on the other hand, the verifying party needs only the public key (certificate), so the private key is held only by the party who needs to sign.

This means that a Salesforce employee could not, as a hypothetical scenario, steal an authentication key and masquerade as a customer without changing the codebase (which often leaves an audit trail), since the private key is held only by the client. The tradeoff is that RSA is much slower than HMAC, but that doesn't always matter.

Now, as I said, I know almost nothing about Salesforce, so I don't know if this was their thinking or not. But coming from a purely cryptographic POV, that would be the most logical explanation, I think. That said, if you are a customer, you might ask them — maybe you'll get an interesting response from an engineer.


Why Merkle Tree doesn't suffer Birthday attack?

The birthday attack, birthday paradox or - probably most accurately - birthday problem does occur for Merkle-trees. This is both the case for the output of the hash algorithms used for the nodes, the in between hash values in the tree as well as the final hash value.

What's probably confusing you here is that the birthday attack isn't really a practical attack against secure hash functions unless the output size is not large enough. In other words, it is the output size of the hash values that protect against the birthday problem becoming a practical issue.


Calculating characters from the sum of ASCII pairs

It would be impossible i think. But if you consider evolving the encrypion system such as changing pair like  : "he","el","ll","lo","o" it would be way to easy to decrypt.


Actually, I think I found the answer to my question while writing it, but I'll post it anyway, since it might be interesting to others:

Yes, OFB mode is secure even with 8-bit feedback, at least as long as IVs are chosen randomly.

Specifically, in the paper "New proof for old modes" (IACR Cryptology ePrint Archive, 2008), which I've cited earlier here, Mark Wooding proves the IND-CPA security (and, in fact, a somewhat stronger security property termed ROG-CPA, for "real or garbage" indistinguishability) of both CFB-$n$ and OFB-$n$ modes for any number of feedback bits $n$, provided that either:

the IVs are chosen randomly,
the IVs are generated by encrypting a deterministic sequence (a "generalized counter") using the block cipher, or
the IVs are directly chosen according to a deterministic sequence, and $n$ is no less than the block size of the block cipher used.

(The extra limitation on the feedback size $n$ in the case of a deterministic IV sequence is due to that fact that CFB and OFB modes using less than one cipher block of feedback have some rare "weak IVs" that can produce a low-period keystream.  Presumably, a deterministic IV sequence chosen to deliberately avoid such IVs would also be safe.)


Why does my SSH private key still work after changing some bytes in the file?

An ASN.1-encoded SSH private key contains the following integers in order:

The public modulus $n$ and exponent $e$;
The private exponent $d$;
The prime factors $p$ and $q$ of $n$;
The "reduced" private exponents $d_p=d\bmod(p-1)$ and $d_q=d\bmod(q-1)$;
The "CRT coefficient" $q_{\text{inv}}=q^{-1}\bmod p$.

The observation that the value of $d$ in such a key may be irrelevant is due to the following: To speed up exponentiation modulo $n$ by a factor of about $4$, the Chinese Remainder Theorem can be utilized to compute the result modulo $p$ and $q$ separately and subsequently combine them to obtain the "real" result modulo $n$. With this optimization, the values of $n$, $e$ and $d$ are not required, hence are ignored by typical implementations whenever $p$, $q$, $d_p$, $d_q$ and $q_{\text{inv}}$ are available*. This is why changing some characters in the middle of the key need not necessarily destroy it, depending on which of the components you change.

*) at least for OpenSSH, they do not have to be present: setting $p=q=1$ and $d_p=d_q=q_{\text{inv}}=0$ makes the implementation use $n$ and $d$.

To visualize the arrangement of the individual components, I created the following graphic from a typical 4096-bit RSA private key file:

The grey part right in the beginning is ASN.1 header data (encoding the fact that a sequence is about to follow, etc), followed by the integers forming the key as described above. The ASN.1 header data associated to each component (mostly a length field) is colored slightly brighter than the data representing the integer itself. Note that the pictured subdivision is not 100% accurate as one Base64 character encodes roughly $3/4$ raw bytes, hence some boundaries should actually run strictly within a single character.


Adaptivity essentially refers to giving the adversary the power to choose an input which potentially depends on the garbled circuit, i.e., the input is adaptiveley chosen after seeing the circuit.

So if a GC scheme is proven secure in the model where the adversary outputs $x$ after seeing the garbled circuit, yes. Otherwise, no.

For formal definitions see, e.g., [1]

References

[1] https://eprint.iacr.org/2015/1250.pdf


Is the complexity of Pollard rho for discrete logartihm really the modulus?

The complexity of Pollard-Rho is indeed $O(\sqrt{\text{ord}(g)})$, but even though $n$ refers to the modulus, their statement might be correct depending of the context. If the modulus considered in your situation is a "classical" modulus in crypto (e.g. $n = (2q+1)^k$ for a prime $q$ and a small $k$, etc), as the modulus will be in general chosen so that ord$(g)$ is big, $n = t\cdot \text{ord}(g)$ for a small constant $t$ so $O(\sqrt{\text{ord}(g)}) = O(\sqrt{n})$.


Informally, the security of a PRF is defined as follows:
The adversary is allowed to ask questions from its oracle.
The oracle choose one of the functions $F$ or $f$ at the beginning, where $f$ is a truly random function with the same domain and image as $F$.
When the adversary $A$ sends a query on $x$, the oracle returns the answer $F(k,x)$ or $f(x)$, depending on which one it has chosen at the beginning.
We say that $F$ is a secure PRF if $A$ can not distinguish which function the oracle has chosen.
Now whit this explanation, for your first function, the adversary sends a query on a nonzero $x^*$, then  a query on zero, when it receives $k$, it compute $F(k,x^*)$ if it was the same as the answer it has received for $x^*$ from the oracle, it distinguishes that the oracle has chosen $F$.
For the second function, the same attack does not work, because the adversary does not know the whole key yet.


Does the generator (base point) is preshared between the sender and receiver in elliptic curve cryptography?

Yes.

The curve and generator point are part of the domain parameters and therefore made explicit if you use a named curve.


Key, plaintext block and ciphertext block permutations question

The answers very are very easy if you know about binary representations.

$k$-bit means the binary representation contains $k$ binary digits.

xx......xx : k binary digits

For each position can be 0 and 1 so, a $k$-bit can take $2^k$ distinct values.

You can similarly argue for $b$-bit block size, if you know that block size is the input  size for block ciphers.

Since block-ciphers are keyed permutations the input space equal to output space.


Integrity or Confidentiality or Authenticity

You're sending a message without signing it, and without any element which can reliably identify you as the sender, so you're clearly subject to Man in the Middle (MitM) attack. An attacker can intercept your message and replace it by his, he only has to compute a hash, and encrypt it with the receiver public key.

The only thing is guarantied is the secrecy of your message, but the hashing was useless. Signing your message would have been a good solution since it implies a secret shared by the two parties.
An even better option would have been to use an authenticated encryption with associated data (AEAD) such as AES-GCM since it take care both of encryption and authentication, and asymmetric crypto is mostly use for signature and key exchange but not data encryption (I know it's not your point, but I had to say it ;-) ).


Real world performance of (still theoretical) Grover's Algorithm

You are right. Indeed, Grover's algorithm has to evaluate the function that is attacked in each iteration (actually the algorithm complexity measure in which you get the square root speed-up is query complexity). And of course, if you make that function more expensive you also make an attack more expensive -- classical as well as quantum. However, here we are switching from asymptotic statements to exact statements. These tend to depend on the exact architecture of a device. E.g., many functions will have different speed on different CPUs even if the clock speed is the same. The problem is that we do not yet know which architecture a future quantum computer will have.

The common thing in research papers is to measure exact complexity of quantum algorithms in terms of T-gate depth. However, this makes two assumptions. First, that the gate set used will be CNOT, T, and second, that T gates dominate execution time (which in this setting is pretty likely). This makes it hard to determine which kind of functions will be especially slow on a quantum computer.

Moreover, also the relation between cost of memory compared to cost of execution time is still open for quantum computers. Hence, it is not clear if a memory-hard function is better than a function that is slow, independent of the available memory. There exist architectures for qubits where keeping state is a lot easier than manipulating it. In these cases the bottleneck would probably be speed, not memory. However, this is all just a look into a crystal ball..., at most confined guessing.


Is it possible I can open pedersen commitments without revealing r?

So is it possible to make Schnorr Protocol only can be verified by a selected verifier with know public key?

Here's the obvious way using a two dimensional Schnorr proof; this is a proof that, given $A^xB^y = C$, you know $x, y$.  It's a straight-forward extension of the regular Schnorr proof:

The prover selects random $r, s$, and computes $T = A^rB^s$.  He also computes $t = \text{Hash}(T)$ and publishes $T$, $u = x + rt$ and $v = y + st$.
The verifier checks whether $A^uB^v = C T^t$

We'll denote $K$ as the public key of the verifier, that is, she knows the value $k$ such that $G^k = K$.

Then, to do a Selected Verifier Proof that the commitment $C = G^m H^r$ is to the value $m$, the prover generates a two dimensional Schnorr proof that he knows the values $x, y$ such that $H^x K^y = C G^{-m}$.  The valid prover can generate such a proof, because he knows such a pair $(x = r, y = 0)$.  On the other hand, the verifier can not convince anyone else that this proves any specific value $m$, because for any $m$, she can construct a $y$ that allows her to generate such a proof.

Here's another idea that occurs to me; it appears to be a way to have a designated verifier Schnorr proof:

The prover wants to prove knowledge of a value $x$ s.t. $A^x = B$, for public $A, B$.  We'll denote $K$ as the public key of the verifier.
The prover selects two random values $r_1, r_2$, and computes $T_1 = A^{r_1}, T_2 = K^{r_2}$ and $U = G^{r_2}$ and computes $t = T_1 + T_2 \bmod q$ (where $q$ is the size of the subgroup).  Then, he publishes $T_1, U$ and $u = x + r_1t$
The designated verifier uses her private key $k$ to compute $T_2 = U^k$, and $t = T_1 + T_2 \bmod q$.  Then, it proceeds like a standard Schnorr proof,  checking whether $A^u = BT_1^t$

No one can verify this proof without the knowledge of $k$ (as they cannot compute $t$).  The designated verifier knows no one else knows $k$, and hence the prover cannot select $t$ arbitrarily.  And, if the verifier tried to forward this proof (possibly by forwarding the value $T$), this doesn't work (even if she exposed her private key $k$), because it is straight-forward to generate a validating $T_1, U, u$ set with the knowledge of $k$ (for arbitrary $A, B$)

Somebody should vet this 'designated Schnorr' proof before you use it; it looks like it meets the requirements.  Here's the reasoning for the 'proof of knowledge' portion: a putative prover can set an arbitrary $T_1 = A^c B^d$ (for arbitrary $c, d$).  However, in that case, the verification equation is $A^{ckt-u}B^{dkt+1} = 1$; this can be satisfied only if $dkt+1 \equiv 0$ (but to set the value $d$ appropriately, the prover would need to know $k$); otherwise, the prover would know that $x = (ckt-u)(dkt+1)^{-1}$, and so knowledge of $k$ (and $c, d$) would imply knowledge of the discrete log.


Why was the term "discrete" used in discrete logarithm?

The word discrete is used as an antonym of 'continuous', that is, it is the normal logarithmic problem, just over a discrete group.

The standard logarithmic problem is over the infinite group $\mathbb{R}^*$, this group is called 'continuous', because for any element $x$, there are other elements that are arbitrarily close to it.

The discrete logarithmic problem is over a finite group (for example, $\mathbb{Z}_p^*$); in contrast to $\mathbb{R}^*$, we don't have group elements arbitrarily close together; we call this type of group 'discrete'.


How did || come to be used in crypto texts to represent concatenation?

The origin is set theory and not programming languages.  In the context of cryptography, I could describe a set that is
$$x_1 \parallel x_2 \parallel \dots \parallel x_n$$
as a concatenation of the series described by
$$\parallel_{i=1}^n x_i.$$
Furthermore, it's worth noting that + to a mathematician would suggest that it is a commutative, which might not be true depending on the set (as we could have a set of functions).


I'm assuming you're referring to logjam.

Using a common DH prime doesn't by itself compromise a system. But using a DH prime that is potentially within computational reach of an organization, especially one that is widely used, is. The authors estimated that cracking a 1024 bit prime might be possible for an organization such as the NSA, given a huge amount of resources (several hundred million dollars) and time (1 year).

Attacking DH is done by computing the discrete log, using an algorithm called NFS. It turns out that for the classical DH (using the multiplicative group of integers, modulo a prime $p$), the attack can be amortized over all discrete logs in a group. In other words, most of the work needed to solve the discrete log using NFS only requires knowledge of the group (defined by the prime $p$), and not the computed value $g^a$ (different for every connection). This means that the attacker can do a huge amount of precomputation and then attack individual connections very quickly.

So the authors suggest that since most of the internet uses only 1 or 2 specific 1024 bit primes, an organization could invest heavily to do the necessary precomputation. Then individual connections can be broken quickly, by computing the last step in NFS. If you want to know how that works, read the link K.G. gave, or learn how NFS (Number Field Sieve) for the discrete log works.

All this can be prevented in a couple of ways. One, simply use larger primes. Even if the entire world used one specific 2048 bit prime, it would (probably) be impossible for an organization to crack encryption in this manner, amortization or not. Better yet, switch to elliptic curve DH. Elliptic curves don't suffer from the same precomputation woes, meaning attacks on parameters that are barely within computational reach only compromise one connection, rather than all those using that group.


If p mod 4 = 3, does choosing a=1 in the parameters of EdDSA really achieve best performance?

There are probably better ways to do this, but at least this is quite elementary.

Let $p$ be an odd prime, and $\mathbb{F}_p^*=\langle\alpha\rangle$ be the cyclic subgroup of order $p-1$. Let $x\in\mathbb{F}_p^*$ such that $x^2=-1$. Take $t\in\{0,\ldots,p-2\}$ such that $x=\alpha^t$. Then $\alpha^{4t}=x^4=1$, so $4t\equiv 0\bmod p-1$. As $0\leq 4t\leq 4p-8$, there are 4 options:

$4t=0$. Then $t=0$, so $x=1$, a contradiction.
$4t=p-1$. Then $p=4t+1$, so $p\equiv 1\bmod 4$.
$4t=2p-2$. Then $t = (p-1)/2$, so $x^2 = 1$, a contradiction.
$4t = 3p-3$. Then $3p\equiv 3\bmod 4$, so $p\equiv 1\bmod 4$.

In other words, $-1$ is not a square if $p\equiv 3\bmod 4$. This is an explicit assumption in your quote.


TLS handshake proof of private key posession

I have used TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384

That means that client and server are using ECDHE for the key exchange and RSA for verification of the server sent parameters. This is what perfect secrecy does, every time that a TLS handshake occurs, the servers sends with the certificate a list of parameters used for the key exchange along with a digital signature over these, in this case RSA signature. These parameters + signature are contained in the ServerKeyExchange field.

  but any hacker could send a copy of public certificate of any server)

You as a client can validate if the presented certificate matches the entity that you want to connect to. This is done by validating that the received certificate on ServerCertificate field belongs to the entity that you are connecting to (CN & SubjectAltName fields) and that the certificate chain is valid (the Root CA has sign the intermediate CA that has sign the leaf certificate AKA the entity's certificate).

So if the validation is successful you proceed to validate the ECDHE parameters sent by the server in ServerKeyExchange field to prove that the server posses (as you ask) the private key associated to the RSA public key. Just take the RSA public key of the leaf certificate and verificate the digital signature of those parameters. If the digital signature matches the digest (hash) of the parameters + ClientHello.random + ServerHello.random, then you know that those ECDHE parameters have been sent by the server and not by an eavesdropper that tries to establish a symmetric key to impersonate the server.


Combining algorithms for password storage?

The combination of different schemes may be somewhat advantageous with regard to certain custom hardware (ASICs), but I think that the disadvantages outweigh them.

I assume that there is some kind of fixed time that is acceptable to the user. Nobody will use a procedure where she or he has to wait several minutes.
Modern password hashing schemes are characterized by the fact that they are not only time intensive, but also memory-hard. To put it simply, a vector is created in RAM in the time acceptable to the user. If less time is available, this vector is smaller. Splitting the acceptable time over several password hashing schemes results in less time to generate the vector for each single scheme. So the whole process becomes less memory-hard.

Password hashing schemes, like all cryptographic procedures, are potentially susceptible to side channel attacks. This applies, for example, to cache timing attacks. Several schemes offer more targets.

And as the questioner has already correctly pointed out, the susceptibility to bugs is greater with several schemes.

I would rather rely on one scheme such as Argon2id and spend all available time to make this method as memory-hard as possible.


What is a fast good-uniformity hash function that if it's seed and it's hash values are unknown, can be strong as cryptographic hash functions?

A universal hash family[1] (paywall-free) $H_r\colon U \to S$ is a set of functions on an input space $U$ into a hash space $S$ indexed by a random $r$ so that the collision probability $\Pr[H_r(a) = H_r(b)]$ is bounded by a small constant like $1/\#S$ for any distinct $a \ne b$.  Sometimes, we are more concerned with a bound on the difference probability $\Pr[H_r(a) - H_r(b) = \delta]$ for any inputs $a \ne b$ and difference $\delta$, where $S$ has some group structure, e.g. if we are going to use this to make a message authenticator[2]; this implies a bound on the collision probability by choosing $\delta = 0$.

A typical example is a polynomial evaluation hash:

Fix a field $k$, let the hash space $S$ be the field $k$, and let the input space $U$ be the set of polynomials of degree at most $\ell$ over $k$ with zero constant term; then define $H_r(p) = p(r)$ with $r$ uniformly distributed in $k$.  If $H_r(p) = H_r(q)$, then $p(r) - q(r) = 0$, so $r$ is a root of a polynomial of degree $\ell$, of which there are at most $\ell$ possibilities each with probability $1/\#k$, so $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell}{\#k}.$$
To evaluate a polynomial $a_1 r^\ell + a_2 r^{\ell - 1} + \dots + a_\ell r$, you can use Horner's rule $(\cdots ((a_1 \cdot r + a_2) \cdot r + a_3) \cdots) \cdot r + a_\ell$, which costs exactly $\ell$ multiplications and $\ell - 1$ additions in the field $k$.  The simple algebraic structure means you can easily vectorize it in a $t$-way vector unit by precomputing powers $(r, r^2, r^3, \dots, r^t)$ of $r$.

Two popular polynomial evaluation hashes are Poly1305[3] and GHASH[4], over fields of size $\#k \approx 2^{128}$.  They are so popular that your web browser is probably using at least one of them right now to communicate with the crypto.stackexchange.com web servers.  Poly1305 uses the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ which admits fast software implementations; GHASH uses the binary field $\operatorname{GF}(2^{128})$ which admits cheap hardware implementations.  They can process data at under 1 cycle per byte on typical CPUs, many times faster than any collision-resistant hash, even the fastest contenders like BLAKE2b, whose fastest implementations on the fastest CPUs haven't broken 2.5 cpb on eBACS even on messages many times longer than yours and which usually run more like 6-12 cpb on message lengths closer to yours.

A CRC works too—viewed this way, it is called a polynomial division hash[5][6]:

Fix a hash length $n$, let the input space $U$ be the set of polynomials of degree at most $\ell$ over $\operatorname{GF}(2)$, and let hash space $S$ be the set of polynomials of degree $n$ over $\operatorname{GF}(2)$; then define $H_r(p) = (p\cdot x^n) \bmod r$, where $r$ is a uniform random irreducible polynomial of degree $n$, of which there are $\pi_2(n)$ possibilities.*

Note that $H_r(a + b) = H_r(a) + H_r(b)$, so $\Pr[H_r(p) = H_r(q)] = \Pr[H_r(p - q) = 0]$.  In this event, $((p - q) \cdot x^n) \bmod r = 0$, so $p - q \equiv 0 \pmod r$, meaning $r$ must divide $p - q$.  Since $\operatorname{GF}(2)[x]$ is a unique factorization domain, $p - q$, a polynomial of degree at most $\ell$, has at most $\ell/n$ factors of degree $n$, each with probability $1/\pi_2(n)$, so $$\Pr[H_r(p) = H_r(q)] = \Pr[H_r(p - q) = 0] \leq \frac{\ell/n}{\pi_2(n)}.$$  In the best case that $n$ is prime, $\pi_2(n) = (2^n - 2)/n$, so this reduces to $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell/n}{(2^n - 2)/n} = \frac{\ell}{2^n - 2}.$$  However, it is not convenient to use prime bit lengths.  If $n = 2^d$ for some $d$, like $n = 128 = 2^8$, then $\pi_2(n) = (2^n - 2^{n/2})/n$, so we only have $$\Pr[H_r(p) = H_r(q)] \leq \frac{\ell/n}{(2^n - 2^{n/2})/n} = \frac{\ell}{2^n - 2^{n/2}}.$$  Fortunately, this is plenty for security.
To compute a polynomial division hash, you need:

A method to choose irreducible polynomials uniformly at random, like Rabin's[7].

This is considerably costlier than choosing a (near-)uniform random element of a field.  You can make it cheaper by choosing a product of smaller irreducible polynomials instead[8], at a cost to the collision probability that is exponential in the number of irreducible factors.
A method to compute division in $\operatorname{GF}(2)[x]$.

This is cheap in hardware, but most conventional hardware—like the Intel or ARMv8 CPU instructions—is limited to a fixed CRC polynomial so you usually can't take advantage of it unless you're designing custom hardware.

In software, the conventional approach is to precompute a table for byte-sized or word-sized inputs, but precomputing a table is costly—on top of the cost of choosing an irreducible polynomial uniformly at random—and using a table with secret inputs invites timing side channels.  Going bit by bit in constant time instead is extremely expensive.  (Of course, this is not much different from situation with GHASH—which is why Poly1305 is safer than GHASH, and crypto_secretbox_xsalsa20poly1305 is safer than AES-GCM.)

Beware: If the adversary learns anything about the hashes themselves, or finds two messages that collide, then any security of the universal hash evaporates[9].  For example, an adversary with a stopwatch may be able to ascertain whether two elements in a hash table collided, and exploit that for denial of service by flooding it with collisions (‘hash flood’).  If that may happen, what you may want is a PRF, like HMAC-MD5, keyed BLAKE2, KMAC128, etc.  PRFs are generally costlier than universal hashes but may be cheaper than collision-resistant hashes.  A common example of a small PRF used for hash tables is SipHash[10].  Universal hashes can be used to cheaply extend short-input PRFs into long-input PRFs[11].

* The number $\pi_q(n)$ of irreducible polynomials of degree $n$ over the finite field $\mathbb F_q$ is[12][13] $$\frac 1 n \sum_{d \mid n} \mu(n/d) \, q^d,$$ where $\mu$ is the Möbius function.


A sliced biclique over $g$ is two set of states ${Q_{i,j}}$ and ${P_{i,j}}$ such that for every pair $(i,j)$
$$
P_{i,j} = Q_{i,j}.
$$
The states are chosen so that the difference between $Q_{i,j}$ for fixed $i$ is small, and the same must hold for $P_{i,j}$ and fixed $j$.

$Q$ and $P$ map to the same hash value $H$, but it is not state #13, but rather
$$
H = \#1\oplus\#13.
$$
You use this equation to filter out incompatible pairs $(i,j)$. The entire trick is to treat some $Q$ as the same, and similarly with $P$ to reduce the computations.

So to answer your other questions

2) Right

3) These are the numbers of recomputed S-boxes in each round from 1 to 6th. There are $6*64 = 384$ S-boxes in total, so there must be $2^{-2}$ calls, not $2^{-3}$.


Combating traffic analysis over request-response protocols

I would try to exploit the fact that client and server use a unique session, that communications are strictly serialized, and that messages are neither lost nor duplicated (if any such assumption does not hold, I guess it is simple to add a protocol for that). I would also consider the "chat contents" sent back by the server as one the messages (just very big).

To say, let's assume that - as first operation during the handshake- the client and the server agree on a certain randomized dictionary, where each message symbol (letter, group of letters, words, etc) is represented via a communication symbol.

Messages are then communicated only via the new encoding. Moreover, each symbol being produced and received influences the dictionary shared by each end. As result the dictionaries will change constantly, but will remain in sync. Think of an unoptimized adaptive Huffman encoding (if it were really optimized you would give away symbol frequency).

If sessions are long lived, building of the initial dictionary would take negligible bandwidth. I cannot really say what the real bandwidth overhead will be, but if the update mechanism for the dictionary is reasonable, it may be quite low.


The design you described is very close to Geffe generator - it consists of three LFSRs L1, L2, L3 and the output bit is either the output of L2 or L3 depending on the value of the output bit of L1. Essentially, the output filter function is $F(x1, x2, x3) = (x1\wedge x2) \vee (\neg x1 \wedge x3)$.

A classical way of attacking Geffe generator is the correlation attack - Google search for "Geffe generator attack" yields a number of relevant results. It looks like this type of attack would be also applicable to your case.
Another potential attack avenue would be algebraic attacks - output bits are quadratic function of the variables of the internal state, so it might be possible to do linearization attack if you observe enough bits of the output or you have additional data about the content of the registers (e.g. you know decoy bits).

In cryptanalysis, the devil is really in the details, so without posting a full description of the algorithm and a reference implementation, it's difficult to say much more than I already wrote above. This should be a good starting point though.

One more remark regarding attack complexities - while I don't think there is a polynomial time attack on a generator you describe, what we care in practice is concrete (not asymptotic) complexity of the attack. If one can show an attack that has smaller complexity than the best generic attack, it is considered a break of the algorithm.


How can I do minus on plaintexts in the Paillier cryptosystem?

In Paillier, as you note, multiplication in the ciphertext domain translates to addition in the plaintext domain. Thanks to the algebraic structure behind Paillier what you can do to get subtraction is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what decryption will return is something between $0$ and $n-1$. For example, if the result is $-1$, you will see $n-1$. To deal with this, we can set some threshold (will depend on the application). If the decrypted value is greater than that threshold, return that value minus $n$. For example, if we see $n-1$ on decryption, we will return $n-1-n=-1$.


Can SHA256 hash be considered as a secure key proof?

Then I would like to have a proof that the user has/knows the key K. The key will be hashed once with a SHA256 function and the result H will be stored in a database (SHA256(key)). So, whenever I will need to verify that the user has the key K, it will be hashed on frontend and only the H value will be sent to the server, so I can compare it with the value stored in DB.

How does that prove that client (who may be pretending to be the user) knows the key?  He obviously knows SHA256(key), but he might have gotten that from the real user.
Even if the negotiation between the client and the server was encrypted (which you do not specify), one obvious approach for an adversary to get that value is to pretend to be the real server, and have the client attempt to log in (and that client will send that SHA256(key) value as a part of the exchange).


Cryptographically speaking, AesManaged uses AES in CBC mode. To ensure this operates securely, you need to choose the IV randomly, i.e. it should not be possible to predict the IV between iterations. This question has a discussion of non-random IVs:  Using a Non-Random IV with modes other than CBC and this SO question: Why is using a Non-Random IV with CBC Mode a vulnerability? has a discussion about the chosen plaintext vulnerability using non-random IVs.

According to the documentation, Rfc2898DeriveBytes implements PBKDF2, a key stretching function. DeriveBytes is an interesting choice of name, but that's essentially what it'll do - output some bytes from the PBKDF2 algorithm. At its heart, PBKDF2 is a repeated application of SHA1; if you input the same passphrase and IV, you'll end up with the same encryption key.

Unlike a hash, you're not going to be storing this anywhere, as it is your secret key for your symmetric operation, so there's less risk of an attacker trying to find a preimage (recover the passphrase) mostly because they just don't need to. So the uniqueness requirement looks unnecessary - however, hypothetically speaking let us assume for a minute all your users use the same passphrase "I love asking crypto questions on SE". If they do this and you're using a constant salt, they'll have the same key. Non-repeating IVs for our CBC mode will mitigate the problem slightly, but it would be a lot better if the keys weren't all the same in the first place.

So, summary:

Constant Salt: bad. Pick a large salt, unique per user. Randomly picking salts will help you achieve this - if you generate a 64-bit salt that gives you a total possible output space of $2^{64} = 18446744073709551616$, or approximately $2635249153$ unique salts per human being right now. So you are not likely to run out, and guarantee that all your user's keys are unique assuming no collisions in PBKDF2.

Edit thanks to fgrieu - the salt size must be 8-bytes (64-bits) or larger. If you can accommodate larger salts, you should, to avoid birthday attacks. For more information, see the comments.
Constant IV: bad. You definitely want a random IV for CBC mode.


How hard is to invert the function that computes the middle-bits of (x^2)?

This is probably not secure enough for a proof of work.  I'll outline some attacks, of increasing sophistication/complexity and increasing effectiveness (decreasing runtime).

Brute force

The obvious attack is brute force: enumerate all $2^{32}$ possible inputs and check to find the first that produces the desired output.  This takes $2^{32}$ time.  I'm sure you already knew about this attack, and based on your question, it sounds like this is acceptable in your application.

Time-space tradeoff

You can use Hellman's time-space tradeoffs (or rainbow tables, the hyped-up version of that) to solve preimages.  You have to do a $2^{32}$-step precomputation to build up the table.  The table is of size about $2^{22}$.  After you've built up the table, you can find a preimage of $f(x)$ in about $2^{22}$ steps of computation.

Thus, after a one-time precomputation that probably takes a few minutes or at most hours, you can invert the function in a few seconds, using a few tens of megabytes of storage.

Guess the high bits and take a square root in the integers

There's a cleverer attack, which will find the preimage using at most $2^{16}$ simple steps of arithmetic (often quite a bit faster).  This will probably run in much less than a second, maybe at little as milliseconds to find a preimage.

We can write any 64-bit integer in the form $\alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$, where $\alpha$ is a 16-bit integer, $\beta$ a 32-bit integer, and $\gamma$ a 16-bit integer (i.e., $0 \le \alpha,\gamma < 2^{16}$ and $0 \le \beta < 2^{32}$).  Now we don't know the value of $x^2$, but $x^2$ is a 64-bit integer and we know its middle bits, so we can write it in the form

$$x^2 = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + \gamma$$

where we know $\beta$ ($\beta$ is just the output of your hash function) but we don't know $\alpha,\gamma$.

Now iterate over all possible values of $\alpha$.  For each guess at $\alpha$, form the value

$$y = \alpha \cdot 2^{48} + \beta \cdot 2^{16} + 2^{16}-1,$$

take the square root of $y$ in the integers, and round down to an integer.  Let $x'$ denote the result, i.e., $x' = \lfloor \sqrt{y} \rfloor$.  Then check whether $x'$ is the desired preimage, i.e., whether $f(x') = \beta$.

I claim that this attack requires at most $2^{16}$ steps.  There are only $2^{16}$ possible values of $\alpha$, so we do at most $2^{16}$ iterations.  Moreover, in the iteration where we've guessed the value of $\alpha$ correctly, I claim we will successfully recover the preimage $x$.  Let me explain why.  First, the 64-bit integer $y$ will be very close to the 64-bit integer $x^2$: $y - x^2 < 2^{16}$.  Therefore, when you take the square-root, $\sqrt{y}$ will be very close to $\sqrt{x^2}=x$.  How close?  Well, notice that $(x+1)^2 \approx x^2 + 2x + 1$, so for 32-bit values of $x$, consecutive squares will be about $2^{32}$ apart from each other.  That's much larger than the gap between $y$ and $x^2$, so $y$ will be much closer to $x^2$ than to $(x-1)^2$ or $(x+1)^2$.  Thus, taking the square root of $y$ and rounding to the nearest integer will return $x$, not $x-1$ or $x+1$ or anything else (unless $x$ is extremely small, say $x < 2^{14}$, which has very low probability and thus can be ignored).

This means that this attack is guaranteed to succeed after at most $2^{16}$ iterations.

It turns out that not all values of $\alpha$ are equally likely; when $x$ is uniformly distributed, the upper 16 bits of $x^2$ are biased towards small values.  Therefore, if you iterate over all values of $\alpha$ in the sequence $0,1,2,3,\dots,2^{16}-1$, you are unusually likely to succeed early.  The average number of iterations until success is $2^{16}/3$, so the attack is about $3\times$ faster than you might expect based upon a worst-case analysis.


Why doesn't the ability to sample a single random bit imply the construction of a random oracle?

My question is: given the ability to sample a single bit at random, can't we use that to construct a random oracle? Suppose we want to simulate a random function $H:\{0,1\}^m \rightarrow \{0,1\}^n$. Just sample $n$ bits for the output, and keep a log so that all future queries are consistent.

Sure.  You could design a signature scheme where there is a central party—a gnome sitting in a standard box flipping coins—and everyone on the planet has a telephone line directly to the gnome that cannot be intercepted so that everyone gets the same values from the gnome.  That's not a particularly practical way to design a cryptosystem—we might like to be able to sign and verify messages offline, for example—but more importantly, it's not really what the random oracle model is about.

The random oracle model is not a just model for hash functions, but a model for adversaries.  Let's take an example: in the signature game EUF-CMA—existential unforgeability under chosen-message attack—an adversary $A$ is by definition a random algorithm with access to a signing oracle and a public key: $A(S, \mathit{pk})$.  The adversary wins if they can find any $(m, \sigma)$ pair that passes signature verification for any message $m$ they did not pass to the signing oracle $S$.  This is sometimes called the ‘standard model’.

In the random oracle model, we consider a family of signature schemes indexed by a uniform random choice of function $H$.  To make it clear that it depends on the hash function, we might label the signing oracle $S_H$.  For example, in RSA-FDH signature, a public key is a large integer $n$ and a signature on a message $m$ is an integer $\sigma$ such that $$\sigma^3 \equiv H(m) \pmod n.$$  The signing oracle for a legitimate user is typically defined by $$S_H(m) := H(m)^d \pmod n,$$ where the secret exponent $d$ solves $3d \equiv 1 \pmod{\lambda(n)}$.  Then, in the random oracle model, the adversary gets not just a signing oracle and public key as in $A(S, n)$ in the ‘standard model’, but also the hash oracle as in $A(H, S_H, n)$.

A ROM theorem is a statement of the following form:

If there is a random algorithm $A(H, S_H, n)$ which, when $H$ is uniformly distributed, returns a forgery with high probability, then there is an algorithm $A'(y, n)$ which, when $y$ is uniformly distributed, returns a cube root of $y$ modulo $n$ with high probability.

The proof of the theorem is a definition of the algorithm $A'$, which constructs a hash oracle and signing oracle that have the correct distribution to fool the forger, but additionally do enough bookkeeping to extract a cube root out of whatever computations the forger does—without using the secret knowledge of $d$ that the legitimate user would have.

Obviously, internally the random algorithm $A'$ will involve flipping coins just like you described, to implement the hash oracle and the signing oracle.  See my earlier ROM answer for details of the proof, and for more background, history, and literature references; see also the standard Bellare & Rogaway paper for the original proof of the RSA-FDH theorem in particular.

In other words, the random oracle model is an assumption about how adversaries are structured.  Rather than using the somewhat confusing term ‘random oracle model’, some authors prefer to say that the theorem quoted above is simply a theorem about $H$-generic adversaries, meaning adversaries that are defined generically in terms of an arbitrary hash function rather than adversaries that exploit details of a particular hash function like collisions in MD5.

MD5-specific forgers have been exhibited, of course—for example, they figured prominently in an international incident of industrial sabotage by the United States and Israel against Iran—but they do not contradict this theorem, because such forgers only work with extremely low probability when $H$ is uniformly distributed.  In other words, if an RSA-FDH signature scheme instantiated with MD5 goes bad, it's not because the fancy math of RSA-FDH went bad—rather, it's because MD5 went bad, and there's a good chance that using SHAKE128 instead will be fine.


How should k2 be produced in the RC4A stream cipher (A modification of RC4)?

Do the two differing implementations in practice undermine RC4A's security claims by not using a PRBG/PRGA to produce k2?

I wouldn't think so.  I get the impression that the authors just intend k2 to be derived from k1.  They have not amended the algorithm so much as to use a different key schedule for k1.  That leads to the requirement to create a second permutation using the existing key scheduling algorithm, thus a different key has to be found from somewhere.  The truth of this is proven by the fact that different implementations use different techniques.

Frankly it's a little disappointing that the authors didn't address k2's generation more specifically.

  Does it matter what k2 is, how it's produced, or if it's the same as k1?

From a cursory inspection of fig.3, it appears that each alternate output comes from each state permutation. There doesn't seem to be any interaction between them. I posit that if k1 = k2 then the outputs would be identical pairs. This seems consistent with the authors' comments regarding improved security by having more variables. A  PRNG is as good a way as any, but.  Ideally the inner state of the PRNG should be equivalent to the length of the key, but since a RC4 key can technically be 2048 bits, that's a problem.  Few smallish XOR shift or LFSR PRNGs have such a large state.  See below.

  What is the proper way to produce k2 that all implementations should follow?

Again, the fact that differing implementations use differing ways of generating k2 proves that there is no proper way to produce it.  Proper would just be that k1 ≠ k2.  My personal choice would be a simple 256 byte randomly generated S box.  Note: it is confusing that the authors use the term S box to refer to the internal state array.  I'm suggesting a real S box so that k2 = SBOX[k1] for all bytes.

There is a wonderful  alternative solution to both initial key stream bias and generation of the two states.  Two fully widened Pearson hashes can be used.  One derangement makes k1, and a second independent derangement makes k2. Since this is a new variant of RC4, there cannot be any backward compatibility  for passwords anyway.   This means that the entire key scheduling algorithm can be scrapped.  And it's a perfect fit as a fully widened Pearson hash output is exactly 2048 bits.  Yes the maximum state size of such a hash is only 1684 bits, but who uses passwords that have 210 bytes of entropy anyway?

Opinion on the paper

I find section 5 very poor.  Every (even amateur) cryptographer knows that RC4's Achilles heel is bias.  Indeed the authors' motivation is to improve RC4's security.  This must mean bias reduction.  So how can they possibly put forward an RC4 derivative without a bias assessment?  What is the point of section 2 if they then just forget about possible biases of their own creation?

"Diminished" from section 5.3 is not good enough.  It means nothing that their baby passes randomness tests.  The original RC4 did too.  This speaks to the vagueness and generality of current test suites, but also forms a  cop out for the authors.  I don't know if this is intentional.  If they wanted a quick and dirty solution, all they had to do was add a von Neumann extractor after the PRNG component and RC4 becomes bias free.

As pointed out in the comments to you, RC4A can be distinguished now via observation of 2^23 outputs.  The author's began their paper saying that the original RC4 could be distinguished after 2^25 outputs.  They seem to have gone backwards, although in fairness attacks improve with time.


Streaming mode of operation that is more resistant against nonce reuse

For my answer I'll distinguish two cases: a) By "streaming" you mean "online" and b) by "streaming" you mean "can encrypt arbitrarily sized messages". See the CAESAR survey paper for the notions I use here.

There can be no fully nonce-misuse resistant online authenticated encryption scheme, i.e. a scheme where the only information leaked upon nonce reuse is whether two messages are identical. However, there's a weaker notion of nonce misuse resistance that allows the "longest common prefix of the messages" to be leaked. I think this notion may be sufficient to you.

The survey paper I linked above lists some candidate constructions for this property and may be more up-to-date than this answer (especially if the round three candidates are already in).

If you are willing to allow offline schemes (i.e. schemes that need at least some information about the complete message before being able to output cipher texts), then you're lucky. It is possible for those schemes to achieve the strong nonce misuse resistance. The most recent and most efficient example I've seen in this category (with full security proofs) being GCM-SIV by Gueron and Lindell.


what is ctr + 1, ctr+2...?

ctr is the first 128-bit input value processed by the block cipher, ctr+1 is this number incremented by 1, and so forth. In practice, ctr is generally a combination of a 96-bit nonce and a 32-bit incrementing counter.

  Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?

No, || refers to concatenation in this example.

  Is CTR mode one-time execution and not using loop?

No, CTR mode implementations almost always use a loop, and process in increments of a multiple of the block size.


Knowledge of discrete log is needed in the proof of Cramer-Shoup public key scheme?

Of course, it doesn't mean that adversary knows how to solve discrete log.
We just wanted to say that adversary only knows that the point $P$ lies
somewhere on a plain $\cal{P}$ of such form.
We don't suppose that adversary knows actual parameters of the plane.

But it's enough for us to deduce that $\cal{P}$ intersects with another plane $\cal{H}$ (which also has a specific form, though we don't know exact parameters) only by a line, so this intersection is negligible (actually,
a probability for $P$ to lie exactly on the line is negligible).


We don't. As far as I know there is no proof of security for ECDSA in any model. There is, however, almost 2 decades of usage in the wild, including by Bitcoin and Ethereum, which would allow any would-be attacker to make a tremendous amount of profit. The fact that this appears to have never happened is good empirical evidence for its security.

I've also spent a while exploring this problem. I believe that if you model the mapping from a curvepoint to its x-coordinate as a random oracle function you can use a forking lemma argument to prove the signature secure. This is unrealistic but it implies that any forger would need to find a meaningful relationship between points and their x-coordinates, and it's hard to imagine such a thing that wouldn't also solve the discrete log problem.


Attacks of the MAC construction $\mathcal{H}(m\mathbin\|k)$ for common hashes $\mathcal{H}$?

Using $H(m\mathbin\Vert k)$ with hash function $H$, message $m$ and key $k$, is one possible way to build a MAC algorithm. It is not necessarily a good one; it depends on the used hash function. Even when it is a good one, that does not preclude the possibility of other, "better" algorithms (e.g. for performance).

As an illustration of potential security issues, let's define hash function $H$ as being SHA-256 applied on the bit-reversed input; that is, we take the input to the hash function as a sequence of bits, reverse the order of bits (first bit becomes last, second bit becomes next-to-last, and so on). It's a bit of a contrived example, but it should show my point. That function $H$ is (obviously) as resistant to collisions, preimages and second-preimages as SHA-256, so, from that point of view, it is a secure cryptographic hash function. However, using $H(m\mathbin\|k)$ with that hash function would be weak, because $H(m\mathbin\|k) = \textrm{SHA-256}(\textrm{rev}(k)\mathbin\|\textrm{rev}(m))$, for which so-called length extension attacks apply.

So whether $H(m\mathbin\|k)$ is a secure MAC depends on subtle properties of the hash function $H$ which are not covered by the classic assertions of resistance to collisions and preimages. HMAC was defined with two nested function hash function calls precisely so that its security could be proven in the case of hash functions of the Merkle-Damgård type (like SHA-256); a simpler construction like $H(m\mathbin\|k)$ was not amenable to such proofs. So this is the reason why HMAC exists: because we can convince ourselves that it is secure, more readily than with your proposal.

As for performance, you have to consider that hash functions are not necessarily the best in town for processing bulk data. On a modern PC, dedicated MAC algorithms like Poly1305 or GHASH (the MAC part of GCM) are easily 5 times faster (or more) than SHA-256 or SHA-512.


One Time Pad - does it work for long plain texts?

The one-time pad guarantees secrecy for messages of arbitrary length, assuming the key is uniformly random of (at least) the same length. There are no caveats to this information-theoretic theorem, it's just that securely exchanging big amounts of key material may be considered to be impractical in some scenarios.

(But frankly, nowadays you would just hand over an SD card or something and have enough key material for hundreds of gigabytes of messages. If you were to engage in that kind of activities rather than using a modern cipher, that is.)


I assume you are asking how the password a user enters to unlock their saved user data is translated into the keys used by 3DES?  According to this link DES-EDE-CBC, which is only two-key 3DES.  The first and third keys are set equal to each other, resulting in two keys of 56 bits or a total size of 112 bits.

To get that key material from a password, a Password Based Key Derivation Function (PBKDF) is usually used.  The details differ depending on the algorithm, but the key idea is to take the password and run it (one or more times) through a cryptographically secure hash function, which has a fixed size output.  The output is usually longer than what you need, so you just take the first $k$ bits to make a key of size $k$.

Again accoring to the link, Firefox appears to use a SHA1 HMAC with a random salt as the key.  This would output 160 bits, of which you only need 112.

If the user does not set a master password, then the password is actually blank, but with a random salt.  That is equivalent to what you said, i.e. having a random key saved to a file.