Cryptanalysis of Linear Feedback Shift Registers

The Berlekamp-Massey algorithm is an iterative algorithm that solves the following problem.

  Given a sequence $s_0, s_1, s_2, \ldots$ of elements of a field, find the
  shortest linear feedback shift register (LFSR) that generates this sequence.

Here, LFSR is a linear array of $n$ elements with initial value
$$(s_0, \quad s_1,\quad  \ldots, \quad s_{n-2}, \quad s_{n-1})$$ and successive values
$$(s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\\
\downarrow\\
(s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\\
\downarrow\\
(s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\\
\downarrow\\
\cdots \quad \cdots$$
where the array contents shift leftwards at each step (clock cycle)
so that the field elements falling
off the left end (the LFSR output) are the given sequence, while
the field elements shown as entering the LFSR on the right*
 are being computed as a linear combination of the LFSR
contents at the previous step.  In particular, for $i \geq 0$,
the state transition can be expressed as
$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\\
\downarrow\\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad \sum_{j=0}^{n-1}c_{n-j} s_{i+j}\biggr),$$
that is, the linear combination
$c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$ of previous
LFSR contents is being fed back into the right end of the LFSR
as $s_{n+i}$
(and hence the name linear feedback shift register).

As mentioned previously, the Berlekamp-Massey algorithm
finds the shortest LFSR that generates the given
sequence meaning it figures out the values of the
$c_i$ elements.  The iterative process consists of finding
the shortest LFSR that generates the first $t$ elements
$s_0, s_1, \ldots s_{t-1}$ and checking if the LFSR
finds $s_t$ correctly. If so, $s_{t+1}$ is checked,
while if not, the $c_i$'s are updated so that the
revised LFSR generates $s_t$. If the sequence was
indeed created by a
$n$-stage LFSR as described above, the Berlekamp-Massey
algorithm finds all $n$ coefficients $c_i$ after
examining $s_0, s_1, \ldots, s_{2n-1}$.  From this
point onwards, the Berlekamp-Massey algorithm can
continue checking the rest of the sequence (if so
desired) but does not need to update the $c_i$'s
because each check of the next symbol simply reports
back that everything is OK.

Let $S(z) = \sum_i s_i z^i$ and $C(z) = -1 + \sum_{i=1}^n c_iz^i$
denote generating functions of the given sequence and
LFSR feedback coefficients. Then, the equation
$$s_{i+n} = c_ns_i + c_{n-1}s_{i+1} + \cdots + c_1s_{i+n-1}$$
is equivalent to saying that the coefficients of $z^{i+n}$
in the product $C(z)S(z)$ is $0$ for all $i \geq 0$. But
the coefficients of $z^0, z^1, \ldots, z^{n-1}$ are not zero.
When only the first $2n$ symbols $s_0, s_1, s_{2n-1}$ have been
looked at, what the Berlekamp-Massey algorithm has solved (thus
far) is the congruence
$$C(z)S(z) \equiv D(z) \bmod z^{2n}$$
where $\deg D(z) < n$.  Indeed, Berlekamp's formulation
of what is now called the Berlekamp-Massey algorithm
envisioned solving congruences
$$C^{(m)}(z)S(z) \equiv D^{(m)}(z) \bmod z^{m}$$
(where $\deg D^{(m)} \leq m/2$) iteratively for
$m=1, 2, \ldots, $ until arriving at the desired
solution at $m = 2n$.

Finally and at long last, the extended Euclidean algorithm
for polynomial greatest common divisors can be used to
solve the congruence
$$C(z)S(z) \equiv D(z) \bmod z^{2n}.$$
Define $\hat{S}(z) = s_0 + s_1z + \cdots +s_{2n-1}z^{2n-1}$
and start the extended Euclidean algorithm to find the
gcd of $z^{2n}$ and $\hat{S}(z)$.  The extended Euclidean
algorithm begins with $r_0(z) = z^{2n}, r_1(z) = \hat{S}(z)$ and
finds the sequence of remainder polynomials
$r_2(z), r_3(z), \ldots$ etc where $r_i(z)$ is the remainder when
$r_{i-2}(z)$ is divided by $r_{i-1}(z)$. It also
expresses each $r_i(z)$ as
$$r_i(z) = \alpha_i(z)r_0(z) + \beta_i(z)r_1(z)$$
where polynomials $\alpha_i(z)$ and $\beta_i(z)$
are computed iteratively.  Consider the smallest
value of $i$ for which $\deg r_i(z) < n$.  We have
$$r_i(z) = \alpha_i(z)z^{2n} + \beta_i(z)\hat{S}(z)$$
and so
$$\beta_i(z)\hat{S}(z) \equiv r_i(z) \bmod z^{2n}.$$

Notice that the Euclidean algorithm processes the
the $s_i$ in descending order of subscripts whereas
the Berlekamp-Massey algorithm processes the $s_i$ in
ascending order of subscripts. The Euclidean algorithm
can be reformulated to process the $s_i$ in increasing
order of subscripts in which case it is virtually
indistinguishable from the Berlekamp-Massey algorithm.
Either way, the algorithms have very similar
computational
complexity.

For details on the extended Euclidean algorithm and its
connections to the Berlekamp-Massey algorithm, see
R. E. Blahut's Algebraic Codes for Data Transmission,
Cambridge Press 2003.


In RSA, why does $p$ have to be bigger than $q$ where $n=p \times q$?

There's no real difference between $p$ and $q$ in RSA. It looks like OpenSSL just has the agreement "$p$ has to be bigger than $q$" for conveniences. One of the numbers has to be bigger than the other (otherwise they would be the same number, and $p = q$ is very bad in RSA).

Just use two examples: $p = 13$ and $q = 11$. $p$ is bigger than $q$, all right. What about $p = 11$ and $q = 13$? In RSA, there is no difference between the two prime numbers, so you can exchange them at will. Both are the same prime pair for RSA, even when the two numbers for $p$ in the examples are different, and "the same prime pair" means in praxis the same key.


There are length recommendations within the HMAC-based One-time Password algorithm, which is simply explained here, and the detail is here.

The important part of this is:-

  The recommendation is made that persistent throttling of HOTP value verification take place, to address their relatively small size and thus vulnerability to brute force attacks.

Just as a cash machine with a 4 digit PIN. They get angry after 3 bad attempts.  RFC 4226 suggests an increasing delay after each registration failure. If you go with the default 6 digit code, you'd get a tad below 20 bits of entropy. But that's to be viewed in conjunction with throttling.  The code would simply look like 872921.

Also there are RSA hardware tokens that use 6 digits, but with a validity period of only about a minute. Adjust accordingly...

Note. This form of HOTP does not mathematically link the code to the time. You'd have to implement that check separately. I don't want to dwell too much on the mechanics of generating/accepting the token. I'm focusing on the IETF recommended entropy aspect of the question within a rate limited environment.


Why is the private key generated first in public key crypto?

In general, the public and private keys are computed together.

For some schemes, the public key is computed from the private key. ElGamal is an example. (The system parameters include a suitable cyclic group $G$ with a generator $g$. Choose a random exponent $a$. Compute $y=g^a$. The public key is $y$, the private key is $a$.)

For other schemes, this is not the case. Some variants of RSA are examples. (Choose primes $p$ and $q$. Compute $n=pq$. Choose (somehow) $e$ relatively prime to $(p-1)(q-1)$. Compute an inverse $d$ of $e$ modulo $(p-1)(q-1)$. The public key is $(n,e)$, the private key is $(n,d)$ (or something equivalent). Notice (a) how the public key is completed before the private key, and (b) it is not in general possible to quickly compute the public key $(n,e)$ from the private key $(n,d)$.)

(For completeness: Note that of course, the private key cannot be quickly computed from the public key. If it could, any adversary could.)


What are these fields in ASN.1 encoding of RSA

The are the $d_P$, $d_Q$ and of course $q_{inv}$ - in that order - in the Wikipedia article. As you can see in the formulas relating to the Chinese Remainder Theorem the primes are also used but $d$, the private exponent, isn't.

The CRT calculations can be used to speed up RSA private key operations, which are the slowest part of the RSA cryptosystem after the prime generation. The calculations also have different side channel attacks linked to them compared to "plain" RSA.


Security issues of a MAC-then-Encrypt-then-MAC approach?

Using a MAC on the plaintext may potentially leak information about the plaintext (MAC algorithms do not necessarily ensure confidentiality of the data they are applied to, although some MAC algorithms like HMAC seem pretty safe). If you want to avoid this (theoretical) problem, then you should encrypt the MAC on the plaintext (i.e. MAC-then-encrypt, not MAC-and-encrypt).

As long as you encrypt the inner MAC along with the plaintext, and the key for the inner MAC is unrelated to the key for encryption, then it is "obvious" that this inner MAC does not induce extra trouble; that inner MAC can be viewed as some plaintext redundancy. (In fact, you could replace the inner MAC with a simple hash function.)

Having two MAC algorithms still seems wasteful, in CPU and data size. If the problem you are trying to fix is a wrong decryption key in an encrypt-then-MAC setup, then a more efficient solution is to derive the encryption key and the MAC key from a single master key, using a KDF. If you do that, then, when the MAC matches, you know that you used the right MAC key, and, by property of the KDF, you also know that the encryption key is the right one. It so happens that deriving encryption and MAC key from a single source with a KDF is a very common situation; so the problem of "lack of plaintext integrity" does not happen in practice. This is why the construction with two MAC you are alluding to does not appear to be much studied.


First of all, for elliptic curves based on a prime field $F_p$, we always work with a prime $p$ that is the same size as our target subgroup.

The reason is quite simple: we could work in a proper subgroup based on a larger curve, but what would that buy us?  It becomes more costly (as all our internal computations are modulo $p$, and if $p$ is larger, those operations are more expensive), and it doesn't make it any more secure; the best attack still involves $O(2^{n/2})$ operations.

A side effect of this decision is to make step 3 quite simple.

$N$ will always be in the "Hasse interval"; $p - 2 \sqrt{p} + 1 \le N \le p + 2 \sqrt{p} + 1$, or in other words $N \approx p$. Since $p$ is an n-bit number, that means that if $N$ were to have an n-bit factor, well, $N$ would have to be that n-bit factor (there is a possibility is that $p = 2^{n} - \epsilon$, where $\epsilon < 2 \sqrt{p}$; in that case $N \ge 2^n$ is possible; I'll ignore that corner case)

So, step 3 is effectively "test $N$ for primality"; that can be implemented quite efficiently.

As for your other questions:

The number of curves you'd expect to go through: if the probability of a curve order being prime is approximately the probability of a random number in the Hasse interval being prime, then we'd have an expected $\log{p}$ iterations.  However, I'm not certain about true that assumption is; I expect it is close.
What size of $p$ do we want?  As above, we pick a cofactor of 1, with $p$ being an $n$-bit prime; again, we could use a larger prime, but there doesn't appear to be any benefit from doing so.


If a nonce $N_i$ is even, then the binary numeral for it its increment $N_{i+1} = N_i + 1$ differs from $N_i$ only in its least significant bit; and if $N_i$ is odd, its increment is even.  This means we can adapt chosen-plaintext attacks against CBC with counter nonces (e.g., from section 4 of this Rogaway paper) to target your scheme.  Given an block cipher $E_k$ with random secret key $k$ and block size $n$, a secret initial nonce $N_1$, and nonce generation rule $N_i = N_{i-1}+1 \mod 2^n$ known to the attacker:

Ask the oracle to encrypt $0^n$ (the one-block plaintext with all zero bits), getting back $C_1 = E_k(N_1 \oplus 0^n)$.
Ask the oracle to encrypt $0^{n-1}1$ (the one-block plaintext with all zero bits except for the least significant), getting back $C_2 = E_k(N_2 \oplus 0^{n-1}1)$.
Ask the oracle to encrypt $0^n$ again, getting back $C_3 = E_k(N_3 \oplus 0^n)$.
If either $C_1 = C_2$ or $C_2 = C_3$, the attacker knows with high probability they're talking to an encryption oracle. Otherwise the attacker knows they're talking to a random oracle.

Proof.  If $N_1$ is even, then its least sigificant bit is $0$, meaning that $N_2 = N_1 \oplus 0^{n-1}1$, and then, given that $C_2 = E_k(N_2 \oplus 0^{n-1}1)$:

$$
\begin{align}
C_2 &= E_k(N_1 \oplus 0^{n-1}1 \oplus 0^{n-1}1) \\
C_2 &= E_k(N_1) \\
C_2 &= E_k(N_1 \oplus 0^n) \\
C_2 &= C_1
\end{align}
$$

If $N_1$ is odd, its least sigificant bit is $1$, $N_2$'s is $0$, and $N_3$ differs from $N_2$ only in its LSB: $N_3 = N_2 \oplus 0^{n-1}1$.  So given that $C_3 = E_k(N_3 \oplus 0^n)$:

$$
\begin{align}
C_3 &= E_k(N_2 \oplus 0^{n-1}1 \oplus 0^n) \\
C_3 &= E_k(N_2 \oplus 0^{n-1}1) \\
C_3 &= C_2 \\
\end{align}
$$


why one just don't encrypt the plain-text message with the public key in the first place?

If you want to send more than one message, the client and server need a shared secret that they can both use to encrypt and decrypt with.

Speed is very important. Encrypting with a symmetric key is much faster than using a set of asymmetric keys when the plaintext becomes longer.


Implementing 5 modes of operation with a hash function

The modes you are referencing are specifically modes of operations for block ciphers, and therefore are not directly applicable to hash functions. Block cipher operations take 2 inputs, the key and a block-sized input value, and output a block-sized keyed permutation of the input. Hash functions take a variable length input, and output a fixed length value.
However, the way 3 of them work can be applied hash functions, by using HMAC or NMAC to turn the hash into a keyed pseudorandom function.
CTR:
In the block cipher we have:
$C_i = P_i \oplus Enc_k(Nonce \ || \ Ctr_i)$
Applying to the hash we have:
$C_i = P_i \oplus HMAC_k(Nonce \ || \ Ctr_i)$
OFB:
In the block cipher we have:
$O_0 = IV$
$O_i = Enc_k(O_{i-1})$
$C_i = P_i \oplus O_i$
Applying to the hash we have:
$O_0 = IV$
$O_i = HMAC_k(O_{i-1})$
$C_i = P_i \oplus O_i$
CFB:
In the block cipher we have:
$C_0 = IV$
$C_i = P_i \oplus Enc_k(C_{i-1})$
Applying to the hash we have:
$C_0 = IV$
$C_i = P_i \oplus HMAC_k(C_{i-1})$
Because of the way these modes work, by not requiring the decryption operation, a keyed one-way function can perform the same function, which is the cryptographic transformation of the input to XOR against the plaintext and generate the ciphertext. They make these schemes stream ciphers.
Because the output size of secure hash functions (SHA256 or SHA512) is generally larger than the block size of a block cipher (AES), using these hash functions may be able to encode a larger amount of plaintext before running into the problems these modes may experience with block ciphers. The additional flexibility of a variable length input also allows the hash functions to have larger nonces/IVs.
However since they are not permutations, the security proofs that apply to block ciphers may not apply to hash functions when used in these modes. Additional security may be provided by truncating the output of the hash function before encrypting the plaintext, but still feeding the full output back in the case of OFB and CFB.
From a performance perspective, most hash functions are slower than most block ciphers, by a wide margin. Using HMAC also requires additional hash operations to generate the secret initial values, however an implementation can do these once per plaintext if the IV and input length of a hash function can changed arbitrarily.


Why doesn't “Classic McEliece” need scrambling?

It seems to me that the answer is highly likely to be as follows. I only had a quick look, so buyer beware:

So, instead of the recovered permuted error vector $\sigma(e)$ ( $e$ is the plaintext, in Niederreiter and Classic McEliece) needing to be scrambled by the opponent to get the unpermuted error vector $e$, the recovery of the correct error vector (for the party holding the private key) is checked by hashing the recovered error vector $e'$ and comparing to the hashed value $h(e)$ included in the plaintext.

The opponent's additional work factor is now the work required to find a hash preimage of the right length (which may or may not be the right $e$).

See the talk here  by Tanja Lange on the project website.


This is a simple substitution cipher, specifically a mixed/deranged alphabet cipher. See wikipedia's description:

  Substitution of single letters separately—simple substitution—can be demonstrated by writing out the alphabet in some order to represent the substitution. This is termed a substitution alphabet. The cipher alphabet may be shifted or reversed (creating the Caesar and Atbash ciphers, respectively) or scrambled in a more complex fashion, in which case it is called a mixed alphabet or deranged alphabet. Traditionally, mixed alphabets may be created by first writing out a keyword, removing repeated letters in it, then writing all the remaining letters in the alphabet in the usual order.
  Using this system, the keyword "zebras" gives us the following alphabets:

 Plaintext alphabet:    ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ciphertext alphabet:    ZEBRASCDFGHIJKLMNOPQTUVWXY


$\mathrm{Hash}(A\|B)$ where $B$ is known, $A$ is unknown. Would knowing $\mathrm{Hash}(A\|C)$ as well as $C$, speed up a brute force search for $A$

The answer depends on your definition of a hash function.
In general hash functions don't guarantee, that they hide their input.
A general hash function gives you three properties:

preimage resistance (given $y = H(x)$ it is hard to find $x^*$ such that $H(x^*) = H(x)$)
second preimage resistance (given $y = H(x)$ it is hard to find $x^*$ such that $H(x^*) = H(x)$ and $x^* \neq x$)
collision resistance (it is hard to find $x_1$ and $x_2$ such that $x_1 \neq x_2$ and $H(x_1) = H(x_2)$)

None of these properties guarantee that the hash function doesn't reveal part of the input - i.e. there are hash functions that reveal $A$.
However, in practice you typically model hash functions as random oracles - for any input, the function yields a randomly chosen output.
In this case it is easy to show that it is hard to find $A$.
You might also want to take a look at length extension attacks, which are a way many hash functions deviate from a random oracle. However, these won't help you in finding $A$, they will however help you in finding (roughly) $H(A \| B \| C)$, given $H(A \| B)$ (without knowing $A$ or $B$).


Finite Automata and Application to Cryptography

In the area of symmetric cryptography , finite automaton have been applied to model the additive differential probability of exclusive-or  and the differential analysis of S-function ref 1 ref 2

another example of automata application on linear model of modular addition ref


Are there any zero knowledge protocols which do not rely on a Group?

Are there any zero knowledge protocols which do not rely on a group?

It depends on your definition of "relying on a group". If you mean "doesn't rely on a group-based assumption like DDH, CDH or DLog or variants thereof", then yes. If you mean "doesn't use a group at some point" then no, because such a protocol would be unimplementable because the most basic operations of a processor and the most commonly used ones in cryptography like XOR and addition form groups.

Assuming the former case the detailed answer is that in theory zero-knowledge proofs only rely on the existence of One-Way-Functions - which can be heuristically instantiated e.g. with appropriate modes of AES. If you want to read the details of this, the relevant paper is "Everything Provable is provable in Zero-Knowledge" from CRYPTO '88.

The core idea of this is though that you take a protocol from IP and transform it so that the verifier only sends randomness (Arthur-Merlin-Protocol). Then the prover commits to the correct responses for that specific randomness input (which requires OWFs) and this is iterated until all specified prover messages are through. Then the prover performs an NP zero knowledge proof that if the verifier were to see the openings to the commitments along with the generated randomness, they would accept the interaction. This works using the actual prover responses as witnesses and exploiting the final verification being a deterministic polynomial time function.

The NP-ZK proof itself is a proof that you know a solution to the graph 3-coloring problem (which is NP-complete and thus you can reduce every problem in NP to it). The basic idea is that the prover has a 3-coloring of the graph and for each protocol run picks a new random permutation of the colors and commits to the coloring of all nodes. Then the verifier requests a random edge, the prover opens the commitment for the connected nodes and the commitments and the difference in color is verified. This is iterated until the verifier is satisfied.


Is there a administrator key that can decrypt all ciphertexts encrypted with different keys by different persons in a group?

Another solution (cf to @Raoul722 comment) is the following:

It is easily feasible with a mix of symmetric and asymmetric encryption.

Assume each user $k$ have a key pair: $(K_{pub}^k,K_{priv}^k)$.
The admin also have his key pair: $(K_{pub}^{admin},K_{priv}^{admin})$ where $K_{pub}^{admin}$ is known by all.

Encryption scheme for a user $k$:

generate a random key $K_{sym}$.
Encrypt your file with a symmetric encryption device such as AES with $K_{sym}$.
Encrypt $K_{sym}$ with assymmetric encryption (RSA, ECC...) with the
$K_{pub}^k$, let's call it $K_k$.
Encrypt $K_{sym}$ with assymmetric encryption (RSA, ECC...) with the
$K_{pub}^{admin}$ let's call it $K_{admin}$.

Decryption scheme for a user $k$:

Decrypt $K_k$ with his private key ($K_{priv}^k$), he will get $K_{sym}$.
Decrypt the file with $K_{sym}$.

Decryption scheme for a user $admin$:

Decrypt $K_{admin}$ with his private key ($K_{priv}^{admin}$), he will get $K_{sym}$.
Decrypt the file with $K_{sym}$.

The sole problem is where do you store the encrypted keys: $K_{k}$ and $K_{admin}$ (maybe in the meta-data of the encrypted files? :) )

About the key privacy: In this scheme, having a asymmetric scheme prevent the admin to know each user private key.

Note: this kind of scheme is useful in company in the following scenario. Assume that everybody encrypt his files. One happens to have a lethal accident (R.I.P.), how do you retrieve his work ?
The problem that will arise is the safe storage of the master key (usually off-line and sealed to prevent malicious usages).


It would be extremily surprising if the ChaCha core was a permutation (as the last P in PRP), although we have no proof it is not (if it was a permutation, it would at least be one we do not known how to invert, see this question).

A better approximation is that the ChaCha core behaves as a Pseudo-Random Function with the additional property $\text{ChaChaCore}(0)=0$. When we use as part of the input a constant secret key, the ChaCha core becomes a plausible Pseudo Random Function family.

The ChaCha core has less remarkable externally visible properties than the Salsa20 core has. $\text{ChaChaCore}(0)=0$ is a simple one. There are however others, including keeping some symmetries in the input into the output; and other properties that a true PRF would not have.

In particular: by definition, $\text{ChaChaCore}(x)=P(x)\boxplus x$ where $\boxplus$ is 512-bit addition with carry removed between 32-bit chunks, and $P$ is some public permutation (with $P(0)=0$) that can be trivially inverted. It follows that knowledge of $\text{ChaChaCore}(x)\boxminus x$ is enough to find $x$, by computing $P^{-1}(\text{ChaChaCore}(x)\boxminus x)$, where $\boxminus$ is to $\boxplus$ what subtraction is to addition.


1) Blinding has been used, for example, to design a version of El Gamal encryption that is resilient to certain side-channel attacks --- see [PK] and the references therein.

2) The goal of the field of leakage-resilient cryptography is to model and study (from a theoretical perspective) what security can be guaranteed against side-channel attacks (including e.g., timing attacks). See this recent survey or this excellent blog post for more details on the type of models that are being considered.

[PK]: Pietrzak and Kiltz. Leakage Resilient ElGamal Encryption


Adversary model for malicious but selfish adversaries?

There is a close connection between covert adversaries and selfish ones. In particular, if you know the utility function of the selfish adversary, then you can compute the deterrent factor that you need for covert adversary. However, it is important to note that the model of covert adversaries considers corrupt and honest parties, where here corrupt would mean selfish. It does not cover the scenario of all parties being selfish (and so all parties may deviate from the specified protocol if it is in their interest).

In order to see how to model this scenario, a good starting point is Rationality and Adversarial Behavior in Multi-Party Computation by Lysyanskaya and Triandopoulos (from CRYPTO 2006).


We do not know the number of possible combinations, since the exact numbers of 1024 bit primes is unknown, but it is MUCH larger than $2048^{16}$. I do not know how you guessed this number, but here are some estimates:

For N with 2048 you need primes p,q with 1024 bit each. There are $2^{1023}$ numbers with this length (a leading 1 and then 1023 binary digits).

According to the prime number theorem, we get this:
$$
\pi(2^{1024}) \approx \frac{2^{1024}}{ln(2^{1024})} \approx\frac {2^{1024}}{710}\approx 2^{1014.53}
$$

Similar you can approximate the number $\pi(2^{1023})$ to almost exactly 1 bit less, and subtract those primes (all the primes with lower length). This leaves still over $2^{1013}$ prime numbers of the according size.

However, the list of all prime numbers is way too huge and does not exist. This is beyond the capability of all computation power on earth for a couple of millenia.


Is it possible for a cryptographic algorithm to limit the number of times a package/ciphertext can be decrypted?

Cryptography itself cannot solve this problem. This problem has long been studied in the field of copyright management to prevent piracy.

The main issue is that it is difficult to keep a state in the ciphertext that records how many times the ciphertext has been decrypted. Even if you can, there is no way in practice to prevent someone reverting the state. I.e. you decrypt, then throw away the new ciphertext, then decrypt using the old ciphertext again.

There have been some interactive protocols designed in the past that use an external trusted server to track the number of decryption. This may work but add some other problems such as privacy (you are essentially tracking the user).


Challenge - Response protocol - how to incorporate client randomness

Using the same certificate/private key for different purposes should not be allowed whenever possible.
The answer to your question firstly relies on the security of the signature scheme you use. If the signature scheme is unforgeable, then you should be largely fine. Unforgeability means the malicious server who can chosen any messages and get the corresponding signatures but still cannot forge a signature of a message which it has not queried. The server gets only signatures of $H(r_s||r_c)$, but cannot generate other signatures. Then the question is how likely $H(r_s||r_c) =m$ where $m$ is something meaningful and the server wants the signature of it. In this case, unforgeability is not enough because the server simply can reuse the signature without needing to forge one. If $H$ you use is collision resistance and $r_c$ is long enough, then $H(r_s||r_c)$ should be a uniformly random value. It is unlikely $H(r_s||r_c)$ is meaningful and the probability of this case is negligible.
The order does not matter and MAC is not needed. Note here the message gets signed is $H(r_s||r_c)$ (this hash value will be hashed by the hash function used by the signature scheme), not $r_s||r_c$.


Generalize the Merkle–Damgård construction for any compression function

You understanding is a bit incorrect. There is no requirement that the output length of the compression function is exactly half of that of the input. Typical compression functions have an output which is much shorter than half the input length.

The Merkle-Damgård construction uses a compression function which takes an input with a length that is the sum of the internal state and one block and an output which is the length of the internal state.

If the size of input and output of the compression function differs by only a single bit, that would lead to a block size of just one bit.

A block size of just one bit would work most of the way. But it would fail in the final block which needs enough room for length padding. You couldn't do length padding in a single bit.

But you could create a new compression function by combining multiple invocations of the original compression function. For example if your original compression function compresses $k+1$ bit to $k$ bits, you could invoke it $k$ times in order to compress $2k$ bits to $k$ bits. Then you could build a Merkle-Damgård construction by using this new compression function.

A different but equivalent formulation would be that you ignore the requirement that the entire length padding fit in a single block in the Merkle-Damgård construction and compensate for any weaknesses that could be introduced from that by still padding to multiples of a block size, which would be large enough to hold the length field.

This construction assumes the compression function is collision resistant, which implies that the output is long enough. If the output was too short a collision could be found by brute force.


How does a non-prime modulus for Diffie-Hellman allow for a backdoor?

How could this allow for a backdoor?

Well, if you do DH modulo a composite, an attacker can recover the shared secret if they can solve the DH problem (or the DLog problem) modulo each of the primes that make up the composite.

There are a couple of ways that could be used by someone who knows the factorization to solve the DLog problem easier than expected.

Each prime could be set up to admit to a small subgroup attack (that is, each of the primes $p, q$ has $p-1, q-1$ smooth; however that also makes it easier to factor (as Samuel notes). On the other hand, one could have a $p$ and $q$ "partially smooth"; say, both $p-1$ and $q-1$ would include a factor circa 64 bits.  This would give a DLog that takes $O(2^{32})$ time (annoying, but quite feasible); while the $p-1$ factoring method would likely take $O(2^{64})$ time (which is likely that no one would bother trying).

A variant of this approach (if one can select $g$ as well) is to select $p-1 = 2p_1p_2$, where $p_1$ is a (say) 32 bit prime, and $p_2$ is a 479 bit prime, and select $g$ so that (mod $p$) is generates a subgroup of order $p_1$.  And, of course, you do the same for $q$.  The DLog problem that you actually see would take $O(2^{16})$ work, and $pq$ would be hard to factor (unless someone guesses $p_1$, and computes $gcm(pq, g^{p_1}-1)$; the backdoor-installer would be hoping that no one would think of trying that)

Another way would be for have the composite be (say) a factor of 4 256 bit primes, which need not admit to small subgroups.  In that case, to someone knowing the factorization can solve the DLog problem by solving 4 problems modulo 256 bit primes; a bit more effort than what a small group attack can do; however it's still practical (and the composite would still be difficult to factor).

A third method is to select primes $p$ and $q$ to be SNFS friendly; that is, both of the form $r^e + s$, for $r, s$ small.  If $p$ and $q$ use different values for $r$, this would not be immediately apparent.

So, yes, the composite modulus could be a backdoor.


Theoretically, what if I were to change some magic numbers in, say, AES?

How are these (magic) numbers chosen?

It heavily depends on what algorithm and which of its magic numbers. They seldom are entirely arbitrary. In AES, it is often taken the lowest value such that a certain mathematical property holds, with that property (demonstrably or plausibly) working towards security. In other algorithms, it could be values that pre-existed in another context (like mathematical constants), often screened so that some criteria is met (e.g. being odd).

  Are they chosen 'manually'?

Quite often so. Or, as is the case in AES S-boxes, an auxiliary program is used.

  I could theoretically pad the encrypted message with them and 'load' these tables with the numbers before the algorithm is kicked off to encrypt/decrypt, right?

Yes.

  Then why have these numbers as constants in the algorithm?

Occam's razor. And other good reasons, among which:

Introducing parameters rather than constants, especially along messages, could very realistically open to attack. For example, if AES S-boxes where a parameter prefixed to a short AES-GCM message, an attacker could change a bit in these constants in the prefix and see if the message gets nevertheless accepted by the receiver despite that change, meaning with high likelihood that the particular S-box entry for this bit was not active during decryption, which would reveal a lot of information about message and key. That could allow recovery of message and key with a realistic number of attempted decryptions.
Changing constants to variables would make hardware implementations slower, larger, more power-hungry and complex. In the case of AES, the standard constants are carved into modern CPUs.
Changing constants may invalidate complex optimizations (for speed or side-channel leakage) that went into translating the constants to hardware or software. In the case of AES S-boxes, see e.g. Joan Boyar and René Peralta: A Small Depth-16 Circuit for the AES S-Box, in proceedings of SEC 2012.

  You could even consider the table(s) of magic numbers used a sort of "extra key"

There are better ways to obtain that. For example, what's fed to the key input of AES could be obtained with a Key Derivation Function applied to the normal key and extra key.


Here's a solution using RSA as the primitive. There's probably a variant based on elliptic curves. Though maybe not. RSA is great for this kind of stuff.
The protocol
Grace the government worker gives the prover Paul an identity document. One of the document fields is an age threshold proof value. This is a standard RSA signature over some public fields of Bob's identity document (EG:name, picture etc.) that Paul would use to prove he is Paul.
Instead of using the standard RSA signature algorithm to generate the signature, Grace uses a multiple of the private exponent when doing the operation. This is equivalent to applying the private operation multiple times.
age_proof=sig^(d*age) mod N
To verify this signature we have to apply the public operation age times to get back the original signature value.
sig=age_proof^(e*age) mod N
Note that sig, e and N are known to the verifier, age and age_proof are not known.
Suppose Paul is 35. If Alice wants paul to prove he is at least 20 years old, Paul first performs 15 public RSA operations on his proof of age value. He passes this value to Alice who performs an additional 20 exponentiations and gets back the original signature.
This can be seen as a chain of signatures. Grace, by repeatedly applying the private operation to Bob's signature value creates a chain of signature values which can be traversed in the forwards direction to get to the signature value.
What the system provides
Paul has an integer x
Grace provides him with a proof value Px
Alice asks Paul to prove that x is larger than a bound y

Alice gives Paul y
Paul applies x-y public operations to degrade Px into a proof for Py
Paul gives Py to Alice
Alice applies y public operations to degrade Py into P0 which is a signature of some data about the thing that was signed (EG: Who owns the proof.)

Proof of age range
A more practical proof of age system would use two numbers. The numbers would be measured in days or hours and be the difference between the owner's data of birth and a date far in the past (say 1900AD) and a date far in the future (2200AD)
The first number, referenced to a date in the past proves youngness. The larger this number the more recent the date of birth.
The second number, referenced to a date in the future proves oldness. The larger this number the farther in the past the date of birth is and the older someone is.
This avoids the need to reissue or update cards as the card holder ages. The proof of youngness can be useful for businesses that want to implement youth discounts.


Does the secret key used in AES have to prime?

No, it does not have to be a prime.

All you need is an appropriately long and random key:

AES-128 = expects key-length of 16 raw/binary bytes (= 128 / 8 bits per byte)
AES-192 = expects key-length of 24 raw/binary bytes (= 192 / 8 bits per byte)
AES-256 = expects key-length of 32 raw/binary bytes (= 256 / 8 bits per byte)

As a practical example, you could use a hashing function like sha-2 to generate a key from a random password, or from a Diffie-Hellman session key, or from an RSA session key, etc. Of course, if it does not conflict your individual purposes, you would be advised to use a deliberately slow key derivation function such as pbkdf-2, bcrypt, or scrypt together with a random salt instead of SHA-2… but let’s stick with SHA-2 to keep it easy.

Depending on the implementation, SHA-2 will return either raw binary bytes, or – more likely – a hex string representing those raw binary bytes. AES-256 for example takes a 32 byte key, which corresponds to 64 characters in hex encoding. All you need to do is to use those bytes SHA-256 returned as a key for AES-256 and you’re set.

In pseudo-code, it would go something like this:

plaintext = "This is top secret!"
key = sha256("This is the password.")
iv = cryptographically_secure_rng();
ciphertext = aes256(plaintext, key, iv);


What is the threat to a PKI when the root CA certificate is generated using SHA1?

None.

You don't trust the Root CA certificate because it was signed by anything - you trust the Root CA because you (or someone on your behalf) placed it in your trust anchor store.

A Root CA certificate has a signature simply because it is mandatory within the X509 specification - it serves no other purpose.

Technically, the trust anchor doesn't have to be a certificate, but most (all?) operating systems have taken the decision to use the X509 certificate format to store the trust anchor - there are others defined (RFC 5914) that don't have a signature, but as far as I'm aware, they are not used.

SHA1 deprecation has been in the limelight lately.  If your subordinate CA certificates or your end-entity certificates are signed by SHA1, browsers will complain.  However, if you sign your Root CA certificate with MD5 or MD4 (or even something earlier if you can find the tools to do so) then everything will still work.

If you take a look at Google, Facebook, Microsoft (and no doubt many more) you'll find that they still have SHA-1 signed Root CA certificates.


In the Niederreiter system, the plaintext is mapped to some error vector of weight $t$, where the code correction capability is $d=2t+1.$

With the trapdoor information (permutation) this can be decoded by the legitimate receiver by syndrome decoding.

Without the trapdoor information, this is equivalent to decoding a random vector, which is hard, as in the McEliece cryptosystem.


Generic name for (?hash) functions of form $\{0,1\}^n \rightarrow \{0,1\}^{poly(n)}$

I presume you are referring to hardcore, one-way functions (OWF's) with polynomial span?

There have been a flurry of publications in the past 12 months relating to these functions and their implied possibility or practicability.
The challenge with hardcore predicates has been in achieving polynomial span...

Bellare

  "The original conjecture by Goldreich and Levin only provided a hardcore predicate, meaning span one, and by extension logarithmic span."

Bellare gave a construction achieving polynomial hardcore predicate span for any OWF (injective or not) with polynomially bounded pre-image size (PPS), along with an added assumption of input obfuscation (iO).
Garg countered with an example of an arbitrary (?) OWF which does not yield hardcore bits, either with or without auxilliary inputs.
So in summary, there are competing claims as to the plausibility of OWF's with auxilliary input obfuscation.

If you are thinking more along the lines of iterative permutations or perfect hashing functions, you may find the specific characteristics of your definition are more completely addressed in an outline of my own algorithm, via my website:

unitambo.files.wordpress.com/2014/05/one-way-function1.pdf
(A more polished paper is pending.)

So, in answer to your question. The correct-est term I guess, would be; polynomial span, one-way functions with auxilliary input obfuscation.


Determine whether nonlinear boolean function is balanced or not

If $$w_H(f)=\#\{x \in \{0,1\}^N:f(x)=1\}$$ denotes the Hamming weight of the truth table of the boolean function $f$ in $N$ variables, the function is balanced if and only if $w_H(f)=2^{N-1}.$

Equivalently, if we define the Walsh-Hadamard transform coefficient of $f$ as
$$
\widehat{f}(a)=\sum_{x\in \{0,1\}^N} (-1)^{f(x)+a\cdot x}, \quad a\in \{0,1\}^N,
$$
then a function $f$ is balanced if and only if $\widehat{f}(0)=0.$

There are some known constructions of nonlinear boolean functions that are balanced, for example you can find some recent constructions in the paper Construction of Balanced Boolean Functions with High Nonlinearity and Good Autocorrelation Properties by Tang, Zhang and Tang, available on the eprint server here.


Possible to know who is the owner of a message encrypted with RSA public key

Yes, an attacker may be able to distinguish which message is send to which recipient, but it depends on the message.

Imagine the following setting: the moduli of the keys of Stalio and Olio differ (this is a requirement for RSA). The public key is set to a well known constant, say the fourth number of Fermat, 65537. Textbook RSA encryption of the number 1 will result in 1. Not very secure - you can immediately see that the encrypted number must be 1. As the ciphertext is identical regardless of the modulus, you cannot distinguish between one recipient or the other.

Now imagine encrypting a number in such a way that it wraps around for one modulus, but not for the other. In that case you can clearly distinguish that it was encrypted using the smaller or the larger modulus. As the modulus identifies the key and therefore the recipient, you can see for which recipient the message was encrypted.

Textbook RSA is not safe for general use, you need to use a padding scheme such as PKCS#1 OAEP to be secure. Moral of the story: use cryptographically secure padding for RSA (I guess we can add this one to the list, although traffic analysis is already in).


Assumption of difficulty of attack in restricted short time

One area that tries to address such questions is fine-grained cryptography [DVV]. Here the working assumption is that the protocols should be secure "against adversaries with an a-priori bounded polynomial amount of resources but the honest algorithm requires less resources than the adversaries they are designed to fool". A classical example of such a protocol is the Merkle puzzle, which is a key-exchange/public-key scheme that requires $O(n)$ time/queries for the parties carrying out the protocol but it takes an adversary $\Theta(n^2)$ time/queries.

More recently, there have been attempts at building public-key cryptography where the gap is arbitrary (e.g., $O(n^c)$ vs $O(n^{c+1})$ for any constant $c$) and these rely on computation problems such as the orthogonal vector problem [B+] where there is a gap between computation and verification (and this gap is inherent conditioned on SETH). This has also resulted in an interesting notion of proofs of work called useful proof of work [B+] where the goal is to utilize otherwise wasteful work (as for example in Bitcoin).

You can find a nice overview of the area by Alon Rosen here.

[B+] Ball et al, Proof of useful work, Crypto'18

[DVV]: Degvekar, Vaikuntanathan and Vasudevan, Fine-grained Cryptography, Crypto'16.


Simplified ECC non-point public key example, how it works

However, in many ECC examples, take this as example:

That reference doesn't talk about ECC as all; instead, it talks about traditional El Gamal in the group $\mathbb{Z}_p^*$.


Is there a secure multi-party computation (SMPC) scheme that doesn't use secret sharing?

Secret sharing captures a really wide set of techniques, and "not using secret sharing" is a bit ill-defined. Let me take an example: the seminal solution for two-party computation uses Yao's garbled circuits. It works as follows (very roughly):

The sender garbles the circuit of the target function, which gives the following guarantees: given an appropriate key for each bit of the input and the garbled circuit, the receiver can evaluate the full circuit without seeing anything but the end result.

The sender sends the key for each of his input bits, and the receiver uses oblivious transfer to retrieve the key for each of her own input bits, without revealing these input bits. Then, she evaluates the garbled circuit and sends the result back.

Unlike, say, GMW and it's variant, the above is not formulated in terms of secret sharing. However, it's easy to find "secret shares" hidden beneath the surface: for each gate of the circuit, the sender will hold two keys $(K_0, K_1)$, while the receiver will hold the key $K_b$, where $b$ is the result of the gate evaluation. In a sense, $(K_0, K_1)$ and $K_b$ form shares of the secret value $b$: each of them individually leaks no information about $b$, yet knowing both allows to recover $b$. In fact, they even "almost" form additive shares of $b$, since $K_b = b\cdot K_1 + (1-b)\cdot K_0 = b\cdot (K_0-K_1) + K_0$, hence $K_0$ and $K_b$ form additive shares of $b\cdot (K_0-K_1)$, where $(K_0-K_1)$ is a value known to the sender.

So, this was just to say that the notion of secret sharing is so fundamental that it does not make much sense to "not use secret sharing" whatsoever. However, if you're interested into protocols which do not directly build upon known secret sharing schemes, there are many:

Yao's garbled circuits, and all its modern improvements, are perhaps the most natural examples.
MPC protocols based on homomorphic encryption - some protocols from the 2000's used additive encryption, there are also many protocols relying on fully homomorphic encryption.
Some more theoretical MPC schemes achieving various "high end" properties do not inherently build upon secret sharing, like those based on indistinguishability obfuscation.

The reason why you see secret-sharing based techniques being used a lot out there is simple: the more you can rely on secret sharing, or other information-theoretic techniques, the more efficient your protocol will be in practice. Encryption, oblivious transfer, or any other public-key cryptographic primitive are expensive, since they use very heavy algebraic operations, or involve very large key size. On the other hand, secret sharing is as simple and efficient as it can get: a few XORs, perhaps some interpolation.

And the reason why we still hear a lot about garbled-circuit-based MPC, even though secret-sharing-based MPC is more computationally efficient, is because the former allow for secure computation with a constant number of rounds, while protocols built from secret sharing techniques will most of the time involve a much larger number of rounds. And in practice, if you're executing your protocol over the internet, the number of rounds matters a lot.

(actually, some of the latest state of the art MPC protocols get the best of both worlds by combining the two approaches)


Well, AES is not a Feistel cipher because it's a substitution-permutation network instead. If I were taking a test that asked me why AES was not a Feistel cipher, this would be my argument: namely, that the structure of substitution-permutation networks is fundamentally different from that of Feistel networks. (Here one could elaborate on invertibility and other differences.)

That said, your statement is not correct. In a Feistel cipher, the round function is not necessarily invertible (DES's round function is not), but in AES, like any substitution-permutation network, the rounds are invertible. This is a property of the construction itself.


Assuming that there are no other flaws in the scheme, e.g. that the pads are not reused, the bias alone may or may not be practically exploitable.  Whether or not it is mostly depends on how much you know (or can guess) about the plaintext.

For example, let's say you have a fairly short list of candidate plaintexts that the message might encode.  Given each possible plaintext and the known ciphertext, you can now determine what the pad that yields that ciphertext from that plaintext would have to be, and then calculate the probability that the known biased pad generation process would produce that pad.  This will then tell you which of the plaintexts is most likely to be the correct one (or, more precisely, let you update your prior estimates of the likelihood of each plaintext according to Bayes' theorem).

More generally, given sufficient bias in the pad and sufficient redundancy in the plaintext, you may be able to simply guess which characters of the ciphertext are likely to be encrypted with the most common pad values, and then fill in the missing characters.  For example, the ciphertext below encodes a common English pangram, encrypted with a standard mod 26 one-time pad, biased so that a bit over 50% of all the pad characters are A (effectively leaving about half of the plaintext characters unchanged).

EHUICVDPTWNFOXCUAGSOYERTHRLAZEJOG

Can you guess what the plaintext is?


Factoring an RSA modulus given high bits of a factor

Here is the solution to M^e is less than N:

http://asecuritysite.com/encryption/crackrsa2

An alternative method is here as a fun article:

http://asecuritysite.com/encryption/crackrsa5

Do you have the Cipher value?


Chacha20 internal counter/position and nonce

So potentially the nonce can repeat a couple of times in a second, but the internal chacha counter should work to make each nonce unique correct?

No.

YOUR OBLIGATION in the ChaCha security contract is to choose a unique nonce for every message you send; IN EXCHANGE, ChaCha provides IND-CPA security, meaning roughly confidentiality against a passive eavesdropper.

ChaCha does nothing to fulfill its contractual obligations for you if you violate your contractual obligations to ChaCha.  The ‘counter’ is an implementation detail of how ChaCha encrypts a single message; ChaCha itself keeps no state between messages—that is your job.  If you repeat a nonce, the security contract is null and void, and ChaCha provides no security whatsoever.

If you're exchanging messages sequentially in a conversation, I recommend that you simply count the number of messages you have sent so far and use that as the nonce.  This way you can cheaply reject replays too by refusing to accept old message numbers.
If you have no persistent state, but you do have access to an entropy source, you could use XChaCha instead of ChaCha (it is easy to write an XChaCha implementation in terms of a ChaCha implementation); then you can pick the 192-bit nonce independently and uniformly at random for each message, and send it along with the message.  But I recommend using message sequence numbers instead if you can.

By the way: You are actually using ChaCha as part of the authenticated cipher ChaCha/Poly1305, right?  I hope you're not building an application out of an unauthenticated cipher!


What is wrong with using SHA1 in digital signatures? Why is a robust hash function needed?

A digital signature scheme has some size on which it works (e.g. what kind of messages can be signed). This message size is usually related to the key size, and smaller than most interesting messages you would want to sign.

So we use a hash function, which maps an arbitrary-length message (there is some theoretical upper size limit with most hash functions, but this is not relevant in practice) to a fixed length hash, and then use this hash as input to the signing function.

For the use for digital signatures, we need the collision resistance property of the hash function:

It should be very hard to find a pair of messages $x \neq x'$ such that $H(x) = H(x')$.

Without this property, an adversary could produce two different messages with the same hash, give me one (innocent looking one) to sign, and later come and show the other one (for which the same signature will fit, too).

Other interesting properties for cryptographic hash functions are preimage resistance (given a hash $h$, it should be hard to find a message $x$ with $h = H(x)$) – this is not that interesting by itself, since we usually already know the signed message – and second-preimage resistance (given a message $x$, it should be difficult to find a message $x' \neq x$ with $H(x) = H(x')$) – this is needed to prevent the attacker to create a second message which has the same hash as one I already signed.

Rob in his answer elaborated a bit about whether or not the found collisions (or second preimages) would be of a valid message format. While it might be that collisions with invalid messages are easier to find, with a brute-force collision search we can principally create messages of any valid format (as long as there are enough bits left to manipulate) with any given hash. If the hash function is secure, brute-force is the best way to find (second) preimages or collisions, and then the hash output size (as well as the time for one hash evaluation) becomes the limiting factor for security. (Assuming, of course, that the signature scheme itself is secure.)

For MD5, the collision resistance is effectively broken, i.e. it is not that hard to create two messages, which only differ in some part in the middle, and have the same hash. This was used in a famous attack to let a CA sign a bogus certificate.

As SHA-1 has a similar structure as MD5, it is expected that there will be found weaknesses, too, and SHA-2 (i.e. SHA-256 or SHA-512) are preferred today.

There was a competition running to define SHA-3, which should be even more secure than SHA-2. The Keccak hash function family won this competition, and in 2015 the SHA-3 standard was officially released in FIPS 202. SHA-3 has a quite different structure than MD5, SHA-1 and SHA-2, so it is expected that any weaknesses there will not carry over.

When designing a new protocol, try to do it in a way that the hash function can switched out, so you can use either SHA-2 or SHA-3 when the other one shows creaks.


What is the correct way to notate elliptic curve properties

There is no standard way, and I think it's impossible to find universal agreement.

However, it is pretty common to use lowercase letters for integers and uppercase letters for elliptic curve points.
And it is very common to indicate as p the prime defining the field $\mathbb F_p$ over which the curve is defined.

For the order of the curve you can use $\#E(\mathbb F_p)$, sometimes n is used but it is also common to use n to indicate the order of the largest prime order subgroup (note that if $\#E(\mathbb F_p)$ is prime then the two indicate the same value). Bernstein notably uses l to indicate the order of the largest prime order subgroup.

h is (I think) universally used to indicate the cofactor, such that $\#E(\mathbb F_p) = hl$

Also the curve's parameters are indicated as lowercase. For short Weierstrass curves you have a and b. For Twisted Edwards you have d and a.

For the points G, P, Q, B are quite common and if G is used then it indicates the generator of the largest prime order subgroup. Note that Bernstein uses B for the generator (Base).


Calculating Multiplicative Inverse for Rijndael S-box using EEA

To do EEA on a finite-field, you can't perform the operations using the operations in the ring of the integers (and they're not precisely the same operations in the field either, as you're working with bit vectors, not field elements).  In particular:

When you do "addition", you need to perform the addition as done in even characteristic fields (that is, you actually do an exclusive-or).
"Subtraction" is actually the same as "addition", so you use exclusive-or for that as well.  Yes; addition and subtraction are the same thing; we're not in Kansas anymore.
The "multiplication operation" is actually a bit shift, as so we would have something like:

new_r = old_r ^ (r << quotient);

What you want is to have (r << quotient) cancel out the msbit of old_r; To make this work, your 'divide' operation needs to effective compute how far the r needs to be shifted left so that the exclusive-or will cancel out the msbit (and hence reduce the size of r).
The test at the bottom (if t is out of range) looks differently.  It turns out (with the above changes) t will never be negative; it might be larger than 255

The Extended Euclidean algorithm can be made to work.  On the other hand, I'm having a hard time seeing a situation where it is a best algorithm for this job.  It's not nearly as fast as a simple table lookup, and it's not even slightly side channel resistant.


Yes, with most operating modes of AES, the length of the encrypted string is the same regardless of key size (128, 192 or 256 bits).

That's because AES-128, AES-192 and AES-256 all are 128-bit block ciphers, meaning they operate on 128-bit data blocks, regardless of key size. The key determines the mapping of 128-bit plaintext blocks to 128-bit ciphertext block, but the key size is independent of the block size.


Has SHA256 been broken by Treadwell Stanton DuPont?

[Update, 2019-09-12: Upon being exposed, and/or after taking advantage of market manipulation by their fraudulent announcements, the scam artists of Treadwell Stanton DuPont have retracted their claim, with more meaningless waffling technobabble about ‘laboratory equipment flaws’ and ‘ambiguous results’—yet they are still selling the same snake oil!  I leave the commentary below as a record of their fraud, including magic market prediction oracles they continue to hawk as well.]

[Update, 2019-09-18: Now the scam artists of Treadwell Stanton DuPont are just straight up asking for donations, perhaps because the world pointed out they don't actually have anything to sell but they still want to take your money and haven't found a productive way to contribute to society in exchange for it.]

  How credible is this claim in the wider cryptographic community?

It is balderdash by scam artists trying to bamboozle people into buying fintech snake oil, using meaningless technobabble (plus quantum!), a virtual office address on Wall Street, and a slick-looking web site with sleek gadget photos and impossible claims about market prediction.

There is no merit to this claim.  If they actually had this capacity, they could easily demonstrate it by showing a SHA-256 collision, or a message whose SHA-256 hash is all bits zero.  Since they are running an elaborate fraud, rather than doing cryptography, obviously they cannot do this.  But for fun, and to make an indelible record on the web for the chumps who at least have the good sense to search the company's name, let's take a look at these scam artists.

From the press release, archived in case anyone tries to memory-hole it to evade prosecution for fraud.

  "While we have successfully broken all 64 rounds of pre-image resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's director of newly formed Hardware Engineering Division, "it is not our intention to bring down Bitcoin, break SSL/TLS security or crack any financial sector security whatsoever."

Seiijiro Takamoto does not appear to exist on the web outside the fraudulent press release issued by ‘Treadwell Stanton DuPont’.

  Up to now, it was thought impossible to use the output of the hash function to reconstruct its given input.

They don't seem to be clear on what a preimage attack does.  (If the input is longer than the output, what a preimage attack finds is almost certainly not the original input but another one with the same output.)

  In accordance with its disclosure policy, Treadwell Stanton DuPont won't be saying exactly how they did it — because once the proof-of-concept is out, anyone with enough computing power will be able to produce a SHA-256 collision, rendering the algorithm both insecure and obsolete.

They can't keep their story straight about whether it's a preimage attack or a collision attack.

From their web site, archived:

  While the exploit won’t be detailed here, it does take quite some computing power to achieve, overlapping into the quantum computing realm. So much, in fact, that combinatorial optimization is used, along with a fully connected/coupled 32,768-bit scale, 256-bit gradation solution space, which translates to a maximum of 1.158x1077 gradations of large-scale, precision parallel processing.

wat

  Remember: this is not brute force.

False.  This is a brute force assault on hapless victims by a barrage of technobabble.

  It is not our intention to bring down Bitcoin, which is why only 25 PHAEDRA A3497 and 25 PHAEDRA A3487 Compute Nodes will ever be constructed. Even though preliminary design, manufacturing specification and initial construction work has already begun, it will likely be 12 months before the first compute nodes are delivered to clients, worldwide.

The fraudsters are creating the illusion of scarcity to scare chumps into giving them money as soon as possible, and setting a deadline that gives them plenty of time to walk off with the money and find another scam.

  PHAEDRA A3497 will start shipping around mid-October 2020 at a rate of one per week. PHAEDRA A3487 will follow suit starting around mid-November 2020. Shipped on a first come, first served basis (S&H not included), if you have secured a place amongst any of the two lists (10 BTC and 6 BTC respectively), you can still climb to a higher rank by submitting or resubmitting an accumulative higher bid.

It's first-come-first-served, except if you pay more you can skip the queue!  But you have to pay in BTC, it seems.  I'm sure this is for principled reasons about evil central payment processors like ‘Visa’ who could be capriciously subverted by the judicial overreach of a court order about fraud, and certainly not because BTC transactions are irreversible.

  Timeline:

  Founding.  Treadwell Stanton DuPont is created to research and develop stock market prediction algorithms using artificial intelligence neural networks.

Curious that they waited until 2017 to register their domain name, nine years after their scam was founded.

Their main web page, amazingly, manages to be worse:

  There's only one proven method to beat the stock market: accurate, precise and timely world-class stocks and securities forecasting. It's like having an oracle at your beck and call. Like clockwork, know what's going to happen beforehand, every single time and take the guesswork —and risk— out of wise stock market investing.

In principle there could be a cryptanalytic attack on SHA-256, but the market will be deterministically predictable only when birds like me hang out with airborne pigs.

Here's another product with their name on it, the NEBULA6 SSE Stock and Securities Forecasting Neural Net platform, sold—as a 100 USD brochure—on eBay:

  If you're a sophisticated investor, hear this: Even your initial investment appreciates over time! Treadwell Stanton DuPont accounts are scarce and highly sought-after, and only a few dozens are available (it's free to register). Their value will SKYROCKET in the next, upcoming months, with many standing in-line for a chance to grab an account. ABSOLUTELY NOTHING TO LOOSE! This is a NO-RISK, ZERO LOSS, FAIL-SAFE, FOOL-PROOF investment! EASY TO USE: Even a total newbie who knows next to nothing of the stock market can get up and running in LESS THAN 15 minutes! TSD does not sell securities - they offer extremely accurate stock forecast charts with a degree of precision previously unheard-of, that has until now been the domain of some of the biggest and most established financial players (aka large investment banks).

I'm ready to line up outside their virtual office at 30 Wall Street which is so exclusive anyone on the web can rent it and make my millions!

Maybe they broke into the cryptobabble fintech space because the sketchball eBay fintech predictimacator market was too smart and got wise to them too fast.


Secure and efficient encryption of a continuous data stream on behalf of a third party using asymmetric cryptography

$\DeclareMathOperator{\X}{X25519}\DeclareMathOperator{\H}{HSalsa20}$Here is a candidate protocol.

I have amended the obviously insensible criterion of having the server hand the user a secret key.  Since you haven't identified your specific performance constraints—how many CPU cycles, nanoseconds, or joules are available in your budget for cryptography per data record, on average and/or in the worst case, for the user and the server?—I picked a widely available, widely accepted composition of specific cryptographic primitives: NaCl crypto_box_curve25519xsalsa20poly1305.

Setup.
The user generates an X25519 secret $u$ and public key $U = \X(u, \underline{9})$, using NaCl crypto_box_keypair, and configures server with $U$.

Data arrival.
On receipt of a set $\{d_0, d_1, \dots, d_{n-1}\}$ of $n$ data records of bounded length at time $t$, the server

generates an X25519 secret $s_t$ and a public key $S_t = \X(s_t, \underline{9})$ using NaCl crypto_box_keypair;
computes the shared secret $k_t = \H(\X(s_t, U))$ using NaCl crypto_box_beforenm;
authenticates and encrypts each record $d_i$ with XSalsa20-Poly1305 under key $k_t$ and nonce $i$ giving authenticated ciphertext $c_i$ using NaCl crypto_box_afternm;
transmits $(S_t, i, c_i)$ to the user for each $i$, which adds 32 + 8 + 16 = 56 bytes of overhead per message; and
erases $k_t$, $s_t$, and each $d_i$.

Data usage.
On receipt of a tuple $(S_t', i', c_i')$, the user

retrieves a cached shared secret $k_t'$ for public key $S_t'$, or computes the shared secret $k_t' = \H(\X(u, S_t'))$ using NaCl crypto_box_beforenm and caches it for subsequent records with $S_t'$;
verifies and decrypts the ciphertext $c_i'$ with XSalsa20-Poly1305 under key $k_t'$ and nonce $i'$—or rejects it if a forgery—giving record $d_i'$ if not forged, using crypto_box_open_afternm; and
processes the record $d_i'$.

(The prime marks are a reminder that what the user receives may be a forgery, not what the server transmitted.  The standard adversary can of course generate their own public key altogether and forge messages using that with wild abandon, but can't selectively modify messages transmitted by the server.  See the caveats below.)

Cost.
The main cost is the $\X(a, B)$ calculation, which is very roughly about half a million CPU cycles on typical widely available hardware, or half a millisecond at 1 GHz.  See https://bench.cr.yp.to/impl-dh/curve25519.html for more detailed measurements on specific hardware, and https://bench.cr.yp.to/results-dh.html for comparison of different DH functions (warning: not all DH functions listed there have the same security level or defense against side channel attacks).

Sharing the key between multiple data records, and caching it when processing nearby data records, may significantly reduce the time and/or energy cost—under certain usage patterns.

Can the server work on records in batches, or must it lose its ability to decrypt each individual record the moment it transmits that record to the user?  If the largest batch of records the server can sensibly ingest is $n = 1$, then you can simplify the protocol but there's no faster option short of picking a different DH function or KEM, which will invariably be less widely adopted, such as FourQ.  But if the server can work on larger batches, then it can save time and/or energy by reusing each shared secret for multiple records.

If the server can work in batches, does the user process nearby records together, or are the access patterns uniformly distributed?  If the user processes nearby records, then the user can save time and/or energy by caching the shared secrets in a memo table and skipping X25519 computations.

Note that if the user processes records strictly sequentially, then you can save much more time and energy by eliding the public-key business altogether with a method left as an exercise for the reader.

Caveats.

Don't use the same key material for anything else.  If you are tempted to do so, study domain separation.
The standard adversary—who can adaptively control the data and control the channel from server to user—can't decrypt records or partially modify records, but can forge completely new records, and can block records of their choice, and can waste the user's memory up to the longest data record size by transmitting an attempted forgery of that size.  It is left as an exercise for the reader to identify exactly what potentially relevant security properties this protocol does and doesn't provide.

Payment.
Please send payment for this cryptography engineering consulting work to

  Mx. Squeamish Ossifrage
  Room 641A
  521 Mersenne Curve
  Anytown, ST 25519
  Untied Steaks of Armorica


What is the SSL private key file format?

Copy / paste that key into http://phpseclib.sourceforge.net/x509/asn1parse.php and you'll see that there are several different integers in there. $p$ is there, $q$ is there as is the exponent and several other integers to speed things up by taking advantage of the Chinese Remainder Theorem.
The key is encoded using DER and derives semantic meaning via ASN.1. The following URL elaborates:
https://datatracker.ietf.org/doc/html/rfc8017#appendix-C
Quoting I understand the mathematics of RSA encryption: How are the files in ~/.ssh related to the theory?:

The ASN.1 syntax for that DER-encoded string is described in
RFC8017 (aka PKCS1):
  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

DER encoding uses a tag-length-value notation. So here's a sample
private key:
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUp
wmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ5
1s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQABAoGAFijko56+qGyN8M0RVyaRAXz++xTqHBLh
3tx4VgMtrQ+WEgCjhoTwo23KMBAuJGSYnRmoBZM3lMfTKevIkAidPExvYCdm5dYq3XToLkkLv5L2
pIIVOFMDG+KESnAFV7l2c+cnzRMW0+b6f8mR1CJzZuxVLL6Q02fvLi55/mbSYxECQQDeAw6fiIQX
GukBI4eMZZt4nscy2o12KyYner3VpoeE+Np2q+Z3pvAMd/aNzQ/W9WaI+NRfcxUJrmfPwIGm63il
AkEAxCL5HQb2bQr4ByorcMWm/hEP2MZzROV73yF41hPsRC9m66KrheO9HPTJuo3/9s5p+sqGxOlF
L0NDt4SkosjgGwJAFklyR1uZ/wPJjj611cdBcztlPdqoxssQGnh85BzCj/u3WqBpE2vjvyyvyI5k
X6zk7S0ljKtt2jny2+00VsBerQJBAJGC1Mg5Oydo5NwD6BiROrPxGo2bpTbu/fhrT8ebHkTz2epl
U9VQQSQzY1oZMVX8i1m5WUTLPz2yLJIBQVdXqhMCQBGoiuSoSjafUhV7i1cEGpb88h5NBYZzWXGZ
37sJ5QsW+sJyoNde3xH8vdXhzU7eT82D6X/scw9RZz+/6rCJ4p0=
-----END RSA PRIVATE KEY-----

Here's the hex encoding:
3082025c02010002818100aa18aba43b50deef38598faf87d2ab634e4571c130a9bca7b878267414
faab8b471bd8965f5c9fc3818485eaf529c26246f3055064a8de19c8c338be5496cbaeb059dc0b35
8143b44a35449eb264113121a455bd7fde3fac919e94b56fb9bb4f651cdb23ead439d6cd523eb081
91e75b35fd13a7419b3090f24787bd4f4e196702030100010281801628e4a39ebea86c8df0cd1157
2691017cfefb14ea1c12e1dedc7856032dad0f961200a38684f0a36dca30102e2464989d19a80593
3794c7d329ebc890089d3c4c6f602766e5d62add74e82e490bbf92f6a482153853031be2844a7005
57b97673e727cd1316d3e6fa7fc991d4227366ec552cbe90d367ef2e2e79fe66d26311024100de03
0e9f8884171ae90123878c659b789ec732da8d762b26277abdd5a68784f8da76abe677a6f00c77f6
8dcd0fd6f56688f8d45f731509ae67cfc081a6eb78a5024100c422f91d06f66d0af8072a2b70c5a6
fe110fd8c67344e57bdf2178d613ec442f66eba2ab85e3bd1cf4c9ba8dfff6ce69faca86c4e9452f
4343b784a4a2c8e01b0240164972475b99ff03c98e3eb5d5c741733b653ddaa8c6cb101a787ce41c
c28ffbb75aa069136be3bf2cafc88e645face4ed2d258cab6dda39f2dbed3456c05ead0241009182
d4c8393b2768e4dc03e818913ab3f11a8d9ba536eefdf86b4fc79b1e44f3d9ea6553d55041243363
5a193155fc8b59b95944cb3f3db22c9201415757aa13024011a88ae4a84a369f52157b8b57041a96
fcf21e4d058673597199dfbb09e50b16fac272a0d75edf11fcbdd5e1cd4ede4fcd83e97fec730f51
673fbfeab089e29d

The 30 is because it's a SEQUENCE tag. The 82025c represents the
length. The first byte means the length is of the "long form" (82 & 80) and that
the next two bytes represent the length (82 & 7F). So the actual length of the
SEQUENCE is 025c. So after that is the value.
Then you get to the version. 02 is of type int, 01 is the tag length
and 00 is the value. ie. it's a two-prime key as opposed to a
multi-prime key.
More info on the Distinguished Encoding Rules.
Trying to understand ASN.1 is a lot more complicated and a lot of it,
for the purpose of understanding the formatting of RSA private keys,
is unnecessary. For X.509 it becomes more necessary but RSA keys
aren't nearly as complicated, formatting-wise, as X.509 certs.
Hope that helps!


GCM encryption for 256-bit and 512-bit block ciphers

You could, however the one part that doesn't translate in an obvious manner is the Galois field representation; you would need to pick a field representation for $GF(2^{256})$ and $GF(2^{512})$, because those have not be predefined for those sizes.

Here's the issue; GCM does field multiplications internally; that is, it takes two $N$-bit vectors (where $N$ is the block size of the cipher), interprets them as field elements in $GF(2^N)$, multiplies those two elements, and those maps that result back into an $N$-bit vector.

Why is this a problem?  Well, exactly what is the mapping between bit vectors and field elements?  It turns out that there are a lot of plausible mappings; from a security standpoint, it doesn't matter (the GCM proofs all work regardless of the representation); however it matters a great deal for interoperability.

For the fields $GF(2^{128})$ and $GF(2^{64})$, that's all defined by the standard; in both cases, we use a polynomial representation, using the irreducible polynomial $x^{128}+x^7+x^2+x+1$ for $GF(2^{128})$ and the irreducible polynomial $x^{64}+x^4+x^3+x+1$ for $GF(2^{64})$ (and the bit order is backwards from what you'd expect; so the multiplicative identity (1) is represented by the bit pattern $80$ $00$ $00$ $00$ .. $00$).

All is well and good for the two block sizes specified by NIST, but you are asking about 256 and 512 bit block sizes; even if we stay with a polynomial representation (and the same backwards bit-ordering), you'd still need to select irreducible polynomials of the correct degree.

Looking through the web, I see a claim that the polynomials $x^{256}+x^{10}+x^5+x^2+1$ and $x^{512}+x^8+x^5+x^2+1$ are irreducible; I cannot confirm that (and the web site has a cavaet as well); however if so, they would be viable options.  This paper also lists some primitive (and hence irreducible) polynomials, however they aren't minimal (which would be the obvious one to use)


How to find common answers without revealing differences?

I'm not well versed in cryptography, but it seems like private set intersection may be what I'm looking for?

Yes. In private set intersection (PSI) if we have elements from a universe $U$ (e.g. the set of 128 bit integers) and Alice has $N_A$ elements and Bob has $N_B$ elements, most good PSI protocols will try to give you $O(N_A+N_B)$ communication and computation complexity. However, if $|U|\approx N_A\approx N_B$, e.g. when you have a dictionary of 100 fruits most of which are liked by both parties with high probability, then there's another way to go about this. Namely you could also consider this as a generic 2-party computation of $|U|$ parallel AND gates using the bitvector encoding used in the question.
So, as a guidance:

For small scales, e.g. $|U|\leq 2^8$ use setup-less PSI protocols, e.g. this DH-based one.
For large scales, e.g. $|U|\geq 2^{20}$ and small set sizes, i.e. $N_A,N_B\leq \frac1{\log_2|U|}|U|$ use dedicated PSI protocols, e.g. OT-Phasing.
In all other cases consider using OT-Extension based AND gate evaluation, i.e. one party entering their interest vector as the choice vector and the other party entering an all-zero vector for the zero-bits and their interest vector for the 1 bits. Then have receiver share the received bitvector with the sender.


does the cipher become entirely affine and hence trivially weak?

Yes; the AES sbox is the only source of nonlinearity (the ShiftRows and MixColumns are linear, and AddRoundKeys for a fixed key is affine), and so if you replace it with a linear/affine one, the entire cipher becomes affine.


How does using salt reduce rainbow table attack?

The point of a rainbow table for password cracking is to allow attacking multiple password hashes with only a little less work than for cracking a single password hash.

Building a rainbow table takes about as much time as worst time for cracking a single password hash (just calculating the crypto operations, not the table overhead). This is about double the time of the average cracking time, assuming an equal distribution.

This means for attacking a single password, a rainbow table only has the advantage that it can be build before we actually know the hash that is searched. A rainbow table only really pays when attacking multiple passwords, since the lookup is quite faster than building the table (the actual lookup time depends on the space used for the table).

When we build a new table for each single salt, we lose both advantages – we can't build the table before knowing the salt, and we can't use it for more than one password (assuming the salt is unique).
So you still can attack a salted password with a rainbow table, but this is more costly than attacking it directly – in other words, a rainbow table is useless.


Bruce Schneier, encryption, public keys and digital-signature.

Say you ask the holder of the private key to decrypt something that you've encrypted for him. You've however lost the original data. So the holder of the private key decrypts the seemingly random data and returns the result.

Now imagine that instead of a ciphertext you send a message to be signed or a hash over the message to be signed. The holder of the private key will try to decrypt it. However, because $D(x) = S(x)$ what is returned is a valid signature over the message. This could be the case for, for instance, raw RSA.

However, for most encryption algorithms this won't be possible in real life. For instance, raw RSA is insecure, so PKCS#1 padding is used. Not only is PKCS#1 padding different for encryption and signature generation, but remember that we have to unpad for decryption and pad for signature generation.

So it depends on the algorithm used, but for often-used encryption primitives the problem is usually not applicable. Still, it is always preferable to use a different key pair for authentication, signing (or rather, non-repudiation) and encryption.

If you have to create your own protocol for, for instance, homomorphic encryption, where raw primitives are more common then sure, remember Bruce's advice.


A thorough read through of the excellent wikipedia article on the history of enigma cracking does give quite a few times the rotor wirings were deduced without any direct knowledge.
Most of these exploited the operational flaw where the same three character key was transmitted twice at the beginning of each message, giving insight into correlation between letters at fixed intervals apart. Over time, you could compile these small clues and make some assumptions. Given that the same 3 wheels were used for an entire day, you can learn a lot about the rightmost wheel over the course of the day. Sometimes they had captured code sheets, so knew the wheels, but didn't know the wiring. This would certainly help deduce the wiring over time.
My favorite anecdote from that page is this one that describes pretty much exactly your scenario:

Mavis Lever, a member of Dilly Knox's team, recalled an occasion when there was an extraordinary message.
The one snag with Enigma of course is the fact that if you press A, you can get every other letter but A. I picked up this message and—one was so used to looking at things and making instant decisions—I thought: 'Something's gone. What has this chap done? There is not a single L in this message.'
My chap had been told to send out a dummy message and he had just had a fag [cigarette] and pressed the last key on the keyboard, the L. So that was the only letter that didn't come out. We had got the biggest crib we ever had, the encypherment was LLLL, right through the message and that gave us the new wiring for the wheel [rotor]. That's the sort of thing we were trained to do. Instinctively look for something that had gone wrong or someone who had done something silly and torn up the rule book.

So yes, new rotor wirings could be deduced, but practically at the time they relied on a combination of espionage, operational shortcomings, and ingenuity to solve such things.


Yes, the classic example is Randomized response: when doing a survey with a yes/no question that is sensitive (for example, "are you currently an undocumented immigrant living in the US"), you ask each respondent to flip a coin first. If the coin hits tails, you tell them to answer randomly (by flipping a second coin), otherwise, ask them to answer honestly. Then, you remove 25% of the "yes" answers to take into account people who answered randomly, and you get a noisy total count that has differential privacy.

It corresponds to this idea of "adding noise to each record" instead of adding noise to the end-result (in this case, the total number of illegal immigrants). The main advantage is that you don't need a trusted third-party that has all the "real" data. The main disadvantage is that the result is more noisy for the same privacy property.

You can compute more complex statistics with this randomized response idea. For example, things like "which websites are most commonly used as home pages in Google Chrome" are computed using RAPPOR. The method is described in their paper.

More recently, Vincent Bindschaedler, Reza Shokri, and Carl Gunter have detailed a generic method to generate a synthetic dataset from real data, with differential privacy guarantees. It's not exactly "adding noise record by record", but it's similar to this idea of releasing not simply noisy statistics, but a full dataset that can be used for data mining.


Why blinding integer $r$ needs to be co-prime with $N$ in blind RSA signature

Why is this a requirement?

Well, if $r$ has (say) $p$ as a factor, then it makes the unblinding step rather difficult.
The original $m$ has $N = pq$ possible, as does $m^d$; if $r$ is a multiple of $p$, then $mr^e$ has only $q$ possible values; if we pass it to the signer, it'll come back to us with a value $m'^d$ that also has only $q$ possible values.  We cannot map $m'^d$ back to $m^d$ (as a single $m'^d$ value would map back to $p$ possible $m^d$ values, and we don't know which one it is.

A follow up a related question: after $s$ (unblinded signature) and $m$ (original message) are revealed, can anyone (and not only the signing authority) check the validity of the signature by checking $s^e=m \bmod N$?

Yes, anyone with the public key can validate it.  This is generally true for public key signature algorithms.


Why doesn't preimage resistance imply the second preimage resistance?

Consider the function $H$ transforming a message $m$ to the SHA-512 hash of the first 1024 bits of $m$ (right-padded with $1024-n$ zero bits if the bit length $n$ of $m$ is less than 1024).

$H$ is first-preimage resistant, but not second-preimage resistant: once you have a first preimage $m_1$, it is trivial to get another $m_2$ with the same hash (e.g. append a zero bit, $m_2=m_1||0$).

Edit: what was suggested to huyichen also works: the hash function $H'$ constructed as suggested is such that for any preimage $m_1$, there is a different preimage $m_2$ with the same hash, obtained from the first by complementing the added input bit $b$, and the other input bit which is combined with $b$.


Given that you use the SHA-3 hash (which is resistant against length extension attacks), would you still need to go through that procedure in order to produce a secure MAC?

No, you don't need to do that, but you can.

  Needless to say we'd still use a key, which we prepend or append to the message, but is that sufficient for a MAC?

Yes, you can prepend the message with the key, i.e. use $H(K||M)$.

Quoting the Keccak (SHA3) website:

  Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.

However, the original standard does not specify this MAC mode, only a hash function.

There is now a specification (pdf) of KMAC (and other constructions) based on SHA-3, or specifically the SHAKE extendable output functions. The changes from "prepend key to message" are key padding as well as the inclusion of constants and the output length, which are all done for domain separation.

It is possible to implement KMAC in this form using SHAKE128/SHAKE256 but not using the other SHA-3 variants.


AES plaintext is smaller than 128 bits - how to expand?

A block cipher is an invertible transformation that maps an $n$ bit block of bits to an $n$ bit block of bits, under the control of a key (and where $n=128$ in the case of AES)

Now, we most often need to do things other than mapping blocks of $n$ bits; how we do that is using the block cipher within a Mode of Operation.  A mode of operation is just a way to use the block cipher to solve some problem we want solving.

There have been quite a number of modes of operations defined; the most common ones are CBC and CTR (counter).  The majority of them (including CBC and CTR) solve the problem 'how do I encrypt an arbitrarily sized message'.

As for 'how to handle odd sized messages', CBC and CTR take two different approaches.

With standard CBC, we assume that the message is always a multiple of $n$ bits; so, what we do is add padding to the message before we do that actual CBC-mode transformation.  This padding fills out the message to a multiple of $n$ bits; this padding is designed so that the decryptor can easily remove it after decryption.  Note: I said standard CBC because there are fancier ways to avoid this padding within CBC mode; they involve handling the last partial block as a special case.

With CTR mode, it doesn't assume that the message is a multiple of $n$ bits at all.  It doesn't actually send the message through the block cipher; instead, it generates a keystream by sending an incrementing pattern through the block cipher (so the first $n$ bits of the keystream may be generated by encrypting the value 1, and the second $n$ bits of the keystream may be generated by encryption the value 2, etc).  One we have such a key stream, having the message not being a multiple of $n$ bits is not an issue; we just discard the parts of the keystream we don't need to encrypt.


Background: $ab + e \bmod P$ is the public key operation for a trapdoor function I am researching. The same expression, usually with more terms/in a higher dimension, is quite prevalent in many lattice based cryptosystems.

My work is available on github, and consequently I happened to receive some analysis from another user there. The following is a transcription of the users comments.

  The "EPQ" key exchange program given here is vulnerable to a Lagarias-Odlyzko style lattice attack. The usual upper triangular lattice basis matrix is formed by taking an identity matrix and replacing the rightmost column with a vector made from the public key, system parameters, and ciphertext. This 3 dimensional lattice contains a short vector that exposes the plaintext, allowing us to recover it with an SVP oracle.

  I've experimentally verified the attack using fpLLL as the SVP oracle, and had successful key recovery in every trial. For concreteness and convenience, the lattice basis I've used is (where P is the system modulus, K is the public key, and C is the ciphertext):

  $\begin{pmatrix} 1 & 0 & P \\ 0 & 1 & K \\ 0 & 0 & C \end{pmatrix}$

  I actually used vanilla fpLLL on the command line, and manually typed in the numbers generated by the program. To demonstrate, I've generated this keypair just now:

  Public: 914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999

  Private: 2502644320274784300686027905786577204651695824856428916800576785188468831099194056968432976701679611038222704877942453351051289674522482331865454722815092306

  And encrypted a random key to get this ciphertext: 31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801
  (The random key was: 101020355786439301914818388108389342468906297672328361246394394849844032365586)

  Then I entered this into the command line by hand (the flag -a svp tells fpLLL to act as an SVP oracle):

  ...:~\$ ~/codes/fplll/fplll/fplll -a svp

  $\begin{pmatrix} 1 & 0 & P_i  \\
0 & 1 & K_i  \\
0 & 0 & C_i
 \end{pmatrix}$

  [values taken out of the matrix for readibility and horizontal space saving] with
  $P_i=$90539821999601667010016498433538092350601848065509335050382778168697877622963864208930434463149476126948597274673237394102007067278620641565896411613073030816577188842779580374266789048335983054644275218968175557708746520394332802669663
  and
  $K_i=$914984079037409997753646956896411367020716296641338957641608068567317657086975832590795630339277510788727851945111403187181412830140879040014025475367233381190196941804342169193880920240279264797993403702890997094738006766532630568999
  and
  $C_i=$31156599101993645275226400017248608173867507193910625562695392661378570296553738808446028840212848623662312900007512235634449530713883849145685393866636831069585880990434485646285032107701202733953935100342846543008476824530843873800801

  fpLLL short vector output:

  [203453603089198469384658317783196545918051882397653184390372945748471804449, -20132211511540947010614907531449286044959891949349819581130241666199997596098,  101020355786439301914818388108389342468906297672328361246394394849844032365586 ]

  Which is of the form: [-modular_reduction_value, -s_value, plaintext] which correctly recovers the plaintext 101020355786439301914818388108389342468906297672328361246394394849844032365586 as well as the random s value used during encryption.

  As for parameters that foil this attack, I found that the lattice starts to contain many unrelated short vectors if either s or e are increased in size by around 16 bits, but this causes the lower 16 bits of the shared key to be corrupted, and these 16 bits can be searched by brute force...

Conclusion

So as you can see, it seems like the real question is "with what parameter sizes is $ab + e \bmod P$ hard to invert?", and we basically happen to have a question about that here.

However, it looks like in order to really quantify that, we have to know what problem the cryptosystem reduces to (if any); Then, we can find out what the most efficient algorithms for solving that problem are and how they scale, and use that information to select secure parameter sizes.


Why is an RSA public key BITWRAP-ed in ASN.1 DER encoding?

That is a Subject Public Key Info structure defined by the X.509 standard:
   SubjectPublicKeyInfo  ::=  SEQUENCE  {
        algorithm            AlgorithmIdentifier,
        subjectPublicKey     BIT STRING  }

The reason it's BITWRAP-ed is that the structure of the wrapped public key depends on the algorithm. It could be a RSA public key as you described, but it could be an elliptic curve or DSA public key too. Without wrapping, the ASN.1 parser would need to be aware of the algorithm it has just parsed to know how to parse the subjectPublicKey, which is cumbersome. With wrapping, it just parses the whole structure and subjectPublicKey can be interpreted later.
(The big question for me it's why it uses a BIT STRING instead of a OCTET STRING...)


Why aren't public-private keys sufficient to build a block chain? Why do we need proof of work/stake?

Since Blockchain is a decentralized system, it has to stop malicious behaviour [which may just be disruptive if not benefiting the attacker directly] and collusion.
Proof of work achieves that by introducing a very large computational cost.
It also removes the burden on the nodes of checking transaction ordering. Also the code is running in parallel in multiple nodes so how is theany transaction ordering going to be universal without local copies being different?


How do you interpret the p-values from the Dieharder testsuite to evaluate an RNG?

I've read that a good RNG will have a range of p-values that follows a uniform distribution; values between 0 and 1 should happen with about equal probability. Why should that be so?

It comes straight from the definition of p-values. The p-value indicates the probability you'd get at least that skewed a result if the source is truly random.

So you expect a p-value $\le 0.05$ 5% of the time. You expect a p-value $\le 0.10$ 10% of the time. Thus, you expect a p-value in the interval $[0.05, 0.10]$ 5% of the time. Similarly for any other intervals between zero and one.

Of course, a uniform distribution will not produce an equal number of results in each range, so you will always get a randomly skewed distribution of p-values as well. In practice, you can probably just rely on dieharder to tell you you've passed the tests... keeping in mind that it does not prove you have a good (cryptographic) random number generator.


Difference between hash functions and algorithms?

Strictly speaking, an algorithm is a method of computing a function. The function is the thing you stick an input into and get an output from. The algorithm is how it does it. In the context of cryptography, however, hash function and hash algorithm are often used interchangeably. People will know what you mean by it.

I believe hash function is the more common term though. Plain old hash is  totally fine as well.


Is there an existing authorative definition of the cryptographic term 'pepper'

I have found one source that claims to have invented the word "pepper".
-- But this doesn't mean that they were the first or the only inventors. I guess it may have been invented and reinvented several times.
1999 Paper
Kedem, G., & Ishihara, Y. (1999, August 23-26). Brute Force Attack on UNIX
Passwords with SIMD Computer. Paper presented at the 8th USENIX Security
Symposium, Washington, DC.
They invent "pepper" on page 6 like this: (line breaks added for readability)

The main idea is to add random bits to the password encryption, similar to the “salt” bits that are currently used to protect passwords against dictionary attacks.
We call the new bits: “pepper” bits. Unlike the “salt” bits that are saved with the encrypted password, the pepper bits are used to encrypt the password, but are never saved.

But I think there are likely to be many different definitions of the term "pepper", simply because people know what "salt" is and like to extend analogies.
I don't think K&I's 1999 definition ever really caught on. To me at least, "pepper" is a cryptographic secret, that is stored but stored somewhere else than the salt.


The principle of SSH is to implement secure (i.e. confidential and authenticated) communication channels in a client–server session. The new release of SSH (known as SSH2) uses public-key infrastructures in order to authenticate servers. This is typically heavy stuff, but the user can easily bypass it: he just has to click “OK” anytime there is a ,security warning.

SSH2 uses DSS for server authentication and Diffie-Hellman key agreement for setting
up a symmetric session key (previous versions were entirely based on RSA). Both
are based on some generator g which generates a subgroup of Z∗
p of prime order q.

The client picks a random ${x ∈ \{1,..., q − 1\}}$, computes ${e = g^x mod p}$, and
sends it to the server.

The server picks a random ${y ∈ \{1,..., q − 1\}}$, computes ${f = g^y mod
p}$ and ${K = e^y mod p}$.

Now server computes the Hash H using various other values and signs it, ${s=sig(H)}$.where ${K_S}$ is his public key, and sends
${K_S}$, f , and the signature s to the client.  This H could be generated from SHA-1.
Now, When you connect to a machine for the first time you will be told that the authenticity can't be established and presented with a key fingerprint to check.
This fingerprint is generated from the server public key may be SHA1 or SHA256.
you can use:-  $ ssh-keygen   -lf   ~/.ssh/id_rsa.pub


Has there been any research on entropy efficient information-theoretically secure PRNGs?

Since you are looking for an algorithm that guarantees entropy for the output if the input it entropic, you are not actually looking for a PRNG, which would expand a seed to a longer random output, but only a transformation from a binary sequence to arbitrary values.

You can achieve this using arithmetic coding, or range encoding, which is the same thing in a slightly different manner. It is a way to encode values from arbitrary probability distributions into minimal size. In your case you can decode a random "seed" sequence to extract random values in any interval(s).

Caution: normally it is fine to be slightly inexact in the encoder math as long as everything is deterministic, since that only worsens the encoding rate slightly. In your case, for secure random numbers the possible outputs must be equally probable so typical implementations may not work for you. Rounding must be done in a way that ensures this.