How can I find the multiplicative inverse in the first transformation of the SubBytes() transformation in AES? In FIPS-197 §5.1.1, it says the first transformation in the SubBytes() transformation is:

  Take the multiplicative inverse in the finite field $\text{GF}(2^8)$ described in Sec. 4.2; the element $\{00\}$ is mapped to itself.

Looking at Sec. 4.2, it says that for a given non-zero polynomial $b(x)$ you can find the inverse $b(x)^{-1}$ by using the extended Euclidean algorithm. My question is basically: how do you do this?

I've looked at a ton of examples, Wikipedia has one in $\text{GF}(2^8)$, but I still just don't understand.

Let $b(x) = x^6+x^4+x+1$, Rijndael has $m(x)=x^8+x^4+x^3+x+1$.

From the relation: $$b(x)a(x)+m(x)c(x)=1 \iff b^{-1}(x) \equiv a(x)\pmod{m(x)}$$ I can't figure out what $a(x)$ and $c(x)$ are.

The higher level explanations maybe assume you know some things, and the basic explanations

only use simple integers with Euclid's algorithm, so it's a frustrating place for a beginner.

They are referring to the formula for Bézout's identity which calculates the greatest common divisor, extended to a finite field, where 1 is the multiplicative neutral element.

  From the relation $b(x)a(x)+m(x)c(x)=1$, $$b^{-1}(x)=a(x)\mod m(x)$$ I cant figure out what $a(x)$ and $c(x)$ are?

In this case, $b(x)$ is the element for which the inverse is desired, and $a(x)$ is the coefficient for some $c(x)$ that results in the equation being correct. Since $a(x)$ must be in the field, it is reduced modulo $m(x)$, becoming the inverse of $b(x)$. The actual calculation of the extended Euclidean algorithm does not require $c(x)$ to find $a(x)$, but it must exist in the formula for the reduction above to be correct:

$$b(x)a(x)+m(x)c(x)=1$$

$$(b(x)a(x) \mod\ m(x)) + (m(x)c(x) \mod\ m(x)) = 1 \mod\ m(x)$$

$$m(x)c(x) \mod\ m(x) = 0$$

$$b(x)a(x) \mod\ m(x) = 1 \mod\ m(x)$$

$$a(x) \mod\ m(x)={1/b(x)}\mod\ m(x)$$

$$a(x) \mod\ m(x)=b^{-1}(x)$$

Any resultant inverse can be multiplied by $b(x)$ to check for correctness, as the result should be 1 modulo $m(x)$. In practice, the multiplicative inverse is calculated using log/antilog tables for non zero elements:

$$a(x) \mod\ m(x)=log^{-1}(255 - log(b(x)))$$

Since the tables are calculated using exponentiation modulo $m(x)$, the resultant $a(x)$ is already reduced and within the field.

Since the inverse is only used in calculation of the sbox, it is not used in most AES implementations, since the precalculated sbox is stored as a table and not generated on the fly.


Random vs. Fixed Paddings Is there any consensus (i.e. are there any research results) on the benefits and drawbacks of various padding schemes?

Generally there seem to be two kinds of them:

random paddings, like ISO10126 that pad with random data
fixed paddings, like PKCS5/7 and X.923 that pad with 0s or some fixed pattern

Is there any reason to prefer one over the other?

In another question of mine it was mentioned that random paddings may be susceptible to subliminal messages, but that answer doesn't cover paddings in general.

In general we nowadays use fixed paddings or a stream mode of operation such as CTR.

Authentication tags are usually used to validate integrity/authenticity. Examples of authentication tags are those created by calculating a MAC or HMAC over the ciphertext and additional data such as the IV. In general known plaintext - including the padding - should not be used to validate integrity/authenticity.

Authenticated ciphers combine a mode of operation and authentication scheme using the same key. Many of them apply CTR mode encryption instead of a mode that requires (internal) padding.

If padding is required, then PKCS#7 padding should be preferred as it seems to be the ad-hoc standard within the defined standards. Basically you should not tie any security claims on the padding though (except possibly the one that subliminal channels are not possible in your particular protocol).


Ring LWE: How can the secret be chosen from the "uniform distribution"? The key generation algorithm for Ring-LWE is as follows. Have a ring $R_p =Z_p[x]/(x^n + 1)$.
Then pick a uniformly random $a$ from $R_p$.
Pick $s$ from an appropriate distribution.
Pick $e$ from the error distribution (typically a constant-size Gaussian).
Compute $b = as + e$. Reveal $(a, b)$ as the public key and $s$ is the secret key.

I've been reading The Homomorphic Encryption Standard. It says that $s$ can be picked as a uniform random element from $R_p$. How is this possible? For instance if the (admittedly insecure) choice $n=1$ was picked, then for any values of $a$, $b$ and $e$ there is some value $s$ which satisfies the equation.
More seriously, the LPR scheme, for instance, assumes that $(re - se_1 + e_2)$ is small in order for decryption to be correct. How can it be small if $s$ is chosen uniformly at random from $R_p$?

You're right that essentially all schemes require that the secrets are small in a concrete sense.
While I'm not terribly familiar with the standard, I believe the tables in question were generated by the LWE Estimator of Albrecht et al. This page of its documentation states various secret distributions they support. I expect "uniform" corresponds to "bounded uniform", but I'm unsure of which particular bound was used to generate that table.


Does the block size of a symmetric cipher impact the security of the cipher itself? Will a 128 bit block have some security implication in post-quantum cryptography?

Does the block size of a symmetric cipher impact the security of the cipher itself?

Yes, absolutely. A small block size limits the amount of data that can be encrypted with a given key, and some block modes are more badly affected by this than others. Additionally, some cryptographic attacks against weak ciphers can be made more practical against a block cipher with a small block size, such as the slide attack, which becomes very difficult to implement when the block sizes are large.

The classical issues with small block sizes are well documented, and other questions on this site on that topic have been answered. Generally, a small block size opens up a can of cryptographic worms regardless of whether or not your adversary is quantum-capable. A 32-bit block size is silly. A 64-bit block size is worrying and can be insecure in certain situations. A 128-bit block size is okay. A 256-bit block size is better. A 512-bit block size is generally excessive. This holds true, quantum or not.

  Will a 128 bit block have some security implication in post-quantum cryptography?

No, a small block size will not generally be affected by quantum computers. The quantum algorithm that would be responsible is Grover's algorithm, which is a search algorithm. All the attacks against block ciphers that rely on a small block size are limited by the amount of ciphertext the attacker has, not by the number of operations an attacker is able to perform. Sweet32, slide attacks, etc. depend on nothing more than being able to collect a lot of ciphertext that has been encrypted under a single key. Once sufficient data has been collected, the number of computations required to break the guarantees of the cipher are not great enough to benefit substantially from Grover's algorithm.

It's important to note, however, that a block cipher used for authentication, e.g. with CBC-MAC, is more vulnerable against a cryptanalytic quantum computer. The reason for this is that a small block size results in a small authentication tag size, and Grover's algorithm can be used to brute force the small tag with more ease. The same is true if the block cipher is used as the core of a hash function, which would result in smaller digests that are easier for a quantum computer to attack.


Pseudorandom zero-sharing: how does it work? TL;DR

How can the shares of the PRZS protocol proposed in [CDI05] reconstruct the "secret" $0$?

Is the number of shares required to reconstruct $0$ equal to $2t + 1$?

Long question

The paper "Share conversion, pseudorandom secret-sharing and applications to secure computation." by Cramer, Damgård, and Ishai shows a protocol for pseudorandom zero-sharing that enables every player $P_j$ to locally compute his share $s_j$ of the polynomial $f_0$ of degree $2t$ from initially distributed keys $r_A^i$, where $t = k - 1$ in a $(k, n)$ secret sharing scheme.

$s_j$ is computed as follows:
$$s_j = \sum_{A \subseteq [n] : |A| = n - t, j \in A} \sum_{i = 1}^{t} \psi_{r_A^i}(a) \cdot f_A^i(j)$$

The authors say that: "it is straightforward to verify that this results in shares consistent with polynomial $f_0$" and that: "$\mathit{deg}(f_0) \leq 2t$ and $f_0(0) = 0$".

If I've correctly understood, if we make $f_A^i(j) = 1, j \in A$ and we consider $\psi$ as an HMAC function, then every player $P_j$ simply sums the HMAC of $a$ with all the keys $r_A$ he has received from all the sets $A$ he belongs to.

How can this result in shares (polynomial $f_0$) that can reconstruct the secret 0? It still remains quite obscure to me.

Furthermore, since $\mathit{deg}(f_0) \leq 2t$, does this imply that to reconstruct $0$ we need $2t + 1$ shares at most?

To your question:

About the HMAC example, maybe the hypothesis that $f^i_A(j)$ is not feasible. Because $f_A(x)$ servers as a role somelike base polynomial while $\psi$ servers as a random scalors of these base polynomials.

$f_A(x)$ is constructed in this way: first, we know $t$ roots of $f_A(x)$, then we assign $f_A(0)=1$. Therefore, $f_A(x)$ is a $t$ degree polynomial whose constant term is 1. Besides, other points like $(j, f_A(j))$ are computed by interpolating. We cannot simply treat $f_A(j)$ as 1.

About reconstructing secret 0. Now that we know the secret is 0, why we need to concern about how to reconstruct the secret. I think maybe the real secret, things we want to hide from is coefficients of non-constant terms in $f_A(x)$, because we usually use PRZS protocol to randomize an existing polynomial whose constant term is a secret.

BTW, there is a simpler version of PRZS:

\begin{equation*}
   f(X) = \sum_{A\subset X\text{, }|A|=n-t}\sum_{j=1}^t \psi_{r_A}(a, j) \cdot X^j \cdot f_A(X)
\end{equation*}

Three observations here:

$f_A(X)$ is a polynomial whose degree is at most $t$ with random constant term.
$X^t \cdot f_A(X)$ is a polynomial whose degree is at most $2t$.
$f(X)$ is divisible by $X$ which means its constant term is 0. Beacause $X^1 \cdot f_A(X)$ contributes $f(X)$'s lowest degree.

Therefore, we come to the conclusion that $f(X)$ is a polynomial that $deg(f) \leq 2t$, and $f(0) = 0$.


Proof that LFSR (with XOR feedback and nonzero seed) will never hit state of all 0s Does anyone know a good proof that a LFSR (with XOR feedback and seeded with non-zero starting state) will never enter zero state?

It is obvious that a zero state will always get stuck in a zero state, but what is the proof that nonzero states cannot cycle into the zero state eventually?

Any linear map (as used in the LFSR next bit computation) gives zero output when loaded by the all zero state, by definition of linearity. So one can never leave the all zero state, which maps onto itself. As @poncho points out the LFSR state mapping is reversible so one can never enter that isolated all zero state from any of the remaining states.


Breaking RSA, given a special kind of oracle that decrypts related ciphertexts for us Let $c=E^{RSA}_{e}(w)$ be the ciphertext belonging to the plaintext $w$ if an $RSA$ system is used. Assume that the public exponent $e$ satisfies $e \le 10$. Furthermore, assume there is an oracle that, on input $r>0$, responds with the value $c_{r}= E^{RSA}_{e} (w + r)$.

Can the plaintext be decrypted efficiently, given this oracle?

Hint 1: what's the binomial expansion of $E_e^{RSA}(w+r)$?  That is, how can that be expressed as a polynomial in variables $w$ and $r$?  What degree are those polynomials, in terms of $w$?

Hint 2: suppose we ask for $E_e^{RSA}(w+r)$ for $0 < r < e$ (and we also know $E_e^{RSA}(w)$); what can we do with the corresponding $e$ polynomials?


Anonymous offline digital cash scheme Can a digital cash scheme exist that is anonymous and offline using blind signature and anonymous signature?

Blind signatures are online by definition. They involve at least two independent parties that interact during the signature generation process. A protocol is "online" if a successful execution of the protocol requires an exchange of messages between two or more independent parties. Consequently, no application of blind signatures, including a digital cash system, can be completely offline.

Furthermore, any transaction within a digital cash system has to be, to some extent, completed "online". "Digital cash" refers to a system that allows you to complete a transaction by exchanging nothing more than information and in which, somehow, your credits are stored digitally on your device. Your digital cash can't be spent without access to the digital information only you possess.

This means, firstly, that each potential owner of credits in a digital cash system has to appear as a black box to any other potential owner of credits within the same system. The only requirement is that each potential credit owner is able to play out the protocol steps involved in a transaction. There is no way for one party to digitally verify that another party is using specific hardware or software that guarantees that the other party is not tampering with audit trails of transactions that have never been committed to any other party.

With logical necessity: If you want to pay someone some amount, you have to communicate this somehow to someone, or else there will be no transaction. You cannot commit to a transaction if you keep all records of the transaction to yourself, because in such case you could simply delete those records at a later time, and there would be no way for anyone to know that the transaction had ever taken place.


What does "seed" mean in cryptography? I have come across "seed" many times, and at each time, it confuses me more and more. I think it has a well-known meaning in cryptography, so what is it?

  They can usually use the  limited number of results stemming from a
  limited number of seed values to defeat security.

  Not only does complex manipulation not help you if you have a limited
  range of seeds, but blindly-chosen complex manipulation can destroy
  the entropy in a good seed!

Those are some parts of an article I was reading, I understand the context, but I'm not sure about "seed".

The seed of a pseudorandom number generator — whether cryptographically secure of not — is the initial input that defines the pseudorandom sequence of outputs generated from it.
It's not really a term that's specific to cryptography, except insofar as there's a considerable amount of overlap between pseudorandom number generation and cryptography, which might be why you haven't been able to find a good definition of it in crypto literature.
That said, such definitions do exist.  For example, NIST SP 800-90A rev. 1 provides the following, admittedly perhaps not the most easily digestible one:

Seed
Noun : A string of bits that is used as input to a DRBG mechanism. The seed will determine a portion of the internal state of the DRBG, and its entropy must be sufficient to support the security strength of the DRBG.
Verb : To acquire bits with sufficient entropy for the desired security strength. These bits will be used as input to a DRBG mechanism to determine a portion of the initial internal state.
Also see reseed.

(Note: "DRBG" stands for "Deterministic Random Bit Generator", which is essentially the NIST term for a pseudorandom number generator.)
SP 800-90A also includes a more detailed description of seeds in section 8.6 (appropriately titled "Seeds"), which I would strongly recommend taking a look at if you're interested in PRNG seeding in a cryptographic context.  It may, however, be a good idea to start reading a few pages up from section 7 ("Functional Model of a DRBG") to familiarize yourself with the concepts and terminology first.


If I allow arbitrary initial hash values for SHA-256, what would be the weaknesses? The initial hash values (IV) of SHA256 are fixed. However, let's say I modify the SHA256 hash function to allow the attacker to use arbitrary IVs rather than fixed IVs. What kind of weaknesses would this cause? Would it be easier to find collisions, preimages, etc? Would it be possible to insert backdoors?

So far, I've only found one example, as specified here (Using SHA-256 with different initial hash value):

  However, allowing an arbitrary IV renders ineffective one of the two redundant safeguards built into SHA-2's padding scheme. If the message length was removed from the above padding scheme, then an adversary having the ability to decide the different IV could do so nefariously; in particular, such that he knows a secret backdoor block $B$ that can be inserted at the beginning of any message, leaving the hash invariant. Proof: one round of SHA-2 transforms the state $S$ according to $S_{j+1}=F(M_j,S_j)\hat+S_j$, where $F$ is a cipher with the (padded) message block $M_j$ used as key, $\hat+$ is addition with some carries suppressed, and $S_0$ is the IV we are discussing. One able to choose the IV could choose it as $F^{-1}(B,0)$, thus such that $F(B,\mathtt{IV})=0$, thus such that $M_0=B\implies S_1=S_0$.

Are there any other examples of potential weaknesses/attacks that would ensue if I allow the attacker to choose arbitrary IVs for the SHA256 hash function?

Would it be easier to find collisions, preimages, etc?

First note that if you can find preimages for a compressing function (like a hash) you can also find collisions. This means if we can't find collisions, then we also can't find preimages and thelike.

Now, the scenario you are describing is called a "freestart collision attack". Freestart collisions are one of the first signs that a hash functions has a serious flaw, e.g. a freestart collision was found for SHA-1 a couple of years before the full collision. Such a collision would utterly destroy our current faith in SHA-256 and is thus unlikely to be found.

Also note that the quoted passage talks about a variant of SHA-256 that removes the length padding to describe an attack. This attack is prevented by the length padding (and is the main reason why it's there).


Two-party equality computation Alice and Bob each secretly chooses an integer between 1 and 10, a and b. They want to know (with high probability) whether or not a equals b, without revealing any other information. Can they?

Sure they can, it's called the socialist millionaires problem. The most common solution is to use Yao's protocol: Alice sends a garbled circuit of the equality function to Bob, and then Alice use oblivious transfers to send the keys necessary for the evaluation of the circuit to Bob. Another option is to rely on additively homomorphic IND-CPA encryption: Alice sends an encryption $E(a)$ of her input $a$, Bob computes $E(r\cdot (a-b))$ from this ciphertext, using his input $b$ and a uniformly random value (over the plaintext space of the scheme) $r$. Alice decrypts and outputs yes if the result is 0, and no otherwise. As the scheme is IND-CPA, Bob learns nothing on Alice's input (the protocol is therefore computationally private for Alice); because of the random coin $r$, the decrypted value statistically masks $b$ when $a \neq b$ (the protocol is therefore statistically private for Bob).


How to thwart a cleartext message's size? Here is a question I don't find addressed in my cryptography books:

let's say Alice want to send Bob a message of length N.
what is the proper way for Alice to hide N?

I am thinking Alice should do something prior to encrypting her message.
Let's say N is the length of Alice's cleartext message, along
with its cryptographic signature.

I guess Alice can prepend her N bytes with some M random bytes, and
append P random bytes at the end.
But, how to choose M and P?
Should they even be chosen according to N?

Thanks!

This is a complex question. There exists no formal treatment of this question and the parameters you choose will depend on your application. A method that is typically used is, like you said, to append some padding to your plaintext. Note that you don't need to both append and prepend; appending is sufficient. Also, the padding doesn't have to be random, it can be deterministic (for instance 0x0000 or something else that is convenient for your file format).

A method that is typically used is to split your data into certain prespecified buckets of a certain size; for instance 1KB, 10KB, 50KB, 1MB and 10MB. Then when your data is transmitted, you round up to the nearest bucket by appending padding.

A few years ago, I worked for the Twitter Product Security team where I performed length-based attacks and defences. This "bucket" technique is something the Twitter product security team does nowadays to avoid profile fingerprinting.

Here's the attack. Suppose I'm your ISP and I want to find out if a certain "suspicious" Twitter profile belongs to one of my customers (we suspect that this attack has actually happened in the real world with devastating consequences [0]). The way I do this is I monitor all of the HTTPS responses that contain the twitter.com SNI. I look at the length of these responses and I count how many times you visit a page of a particular length during a short period of time, say, a few minutes. Specifically, I look at "bursts" of responses which correspond to a particular mouse click and contain multiple files such as HTML, CSS, and JPG. For all of these files, I can calculate the length of the ciphertext. In case of newest HTTPS protocol versions, I can only get a global length for this particular "burst", but this should be enough to fingerprint.

The length I see you visit most often likely corresponds to the length of the page corresponding to your own twitter feed (i.e., what you see when you go to twitter.com). Now, because the "suspicious" Twitter profile I'm interested in has a public list of people they follow, I can reconstruct that feed, because all it contains are tweets by the people they publicly follow (assuming here that secret tweets are rare). In this reconstruction, I know which avatars of which people should appear in the feed. Those will have to be transmitted as images over HTTPS and their sum is added to what I see. I can also reasonably predict if and when some of them are being cached so that they're not retransmitted. Therefore, if the page you visit most often has a similar length to the feed of the "suspicious" Twitter profile feed, I can deduce that it's you.

In the bucket defence, avatars always have a certain size among 10 different sizes. The way this is achieved is that padding is added as needed. There's also a maximum size that you can't upload beyond.

If you have rigorous requirements about what kind of thing you want to hide, you can look at differential privacy [1]. This can help you understand exactly how much noise you need to add in order to confuse the adversary to a certain degree. It will also allow you to quantify how many queries the adversary would need to perform in order for them to get to your length within a specified margin of error. This depends on your application. If you provide more comments about what you're trying to do and what your threat model is, it would be helpful.

There are some details related to this attack that are interesting and can cause engineering challenges, but they can be overcome. The first is that stream ciphers preserve byte length between plaintext and ciphertext, but block ciphers do not preserve it exactly. This can cause problems in measurements, but they only delay the attack, because there is still enough information to be gained if you just round up to the closest 256th bit. This is something we explored in our work [2] where we augmented BREACH to work against AES and not only RC4. The second is that data is compressed and compression is a complex thing which composes multiple algorithms which can compress across different sources of data. Again, this may make things more difficult, but still allows statistics to be run. Last, there's noise in all of these pages, such as ads, recommendations and so on that the adversary cannot predict. But these do not affect the page lengths dramatically, and in any case they can be modelled as "uniformly random noise" which, on average, adds a constant length to the response. In fact, the existence of appropriate compression and the adversarial manipulation of noise can allow an adversary to vastly improve their attack. For some of the techniques we developed to this end, as well as some defences, see our collaborative work at [3, 4, 5, 6].

For a formal treatment, you can consult our incomplete and unreadable manuscript on the theory [7]. Sadly, I do not think this manuscript will ever be finished and I don't think I can take the security games and proofs to where I wanted.

[0] McGahan, Jason. "She Tweeted Against the Mexican Cartels, They Tweeted Her Murder". October 2014. Accessed May 2018.

[1] Dwork, Cynthia. "Differential privacy: A survey of results." International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 2008.

[2] Karakostas, Dimitris and Zindros, Dionysis. "Practical New Developments on BREACH". Black Hat Asia 2016. Presentation.

[3] Grigoriou, Dimitris. "Extending the Rupture compression attack framework against real world systems". University of Athens 2017.

[4] Karakostas, Dimitris and Kiayias, Aggelos and Sarafianou, Eva and Zindros, Dionysis. "CTX: Eliminating BREACH with Context Hiding". Black Hat Europe 2016.

[5] Karakosats, Dimitris. "Probabilistic Attacks Against Compressed Encrypted Protocols". National Technical University of Athens 2016.

[6] Sarafianou, Eva. "Creating a Tool for Attacking Compressed Encrypted Protocols". National Technical University of Athens 2017.

[7] Karakostas, Dimitris and Kiayias, Aggelos and Zindros, Dionysis. "On the (in)security of encryption over compression in TLS". Unfinished manuscript. Source.


How did || come to be used in crypto texts to represent concatenation? In RFC5647, NIST SP 800-38D, etc., || is used to denote concatenation. How did that come to be?

In most programming languages || represents "or" and + denotes concatenation and the fact that crypto texts just kind of mixed it up seems to make for an easy gotcha.

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


Differential privacy what does "where the probability is taken over the randomness used by the algorithm" mean? The definition of differential privacy is as follows:
A randomized mechanism $\mathcal{M}$ is $(\epsilon, \delta)$-differentially private, where $\epsilon \leq 0$ and $\delta \leq 0$, if for any database $D \in \mathcal{X}$ and $D' \in \mathcal{X}$, differing on at most one record, and for any possible output $S \subseteq Range(\mathcal{M})$, the following in-equation holds
\begin{align}
      \Pr[\mathcal{M}(D) \in S] \leq e^{\epsilon} \cdot \Pr[\mathcal{M}(D') \in S] + \delta
  \end{align}
where the probability is taken over the randomness used by $\mathcal{M}$.
What does the part "where the probability is taken over the randomness used by $\mathcal{M}$" mean?

So here $\mathcal{M}$ is, as you wrote, a "randomized mechanism", so it means that for one entry $D$ it can output different values. For example, you can imagine that on entry $D = 1$, $\mathcal{M}$ outputs $0$ with probability $1/4$ and $1$ with probability $3/4$. To make it more concrete, you can imagine that in order to choose which output $\mathcal{M}$ will output, $\mathcal{M}$ can have access to a coin that it can toss (or, equivalently, to a random string $r \in \{0,1\}^n$ of sufficiently large size that can represent the result of a bunch of coin tosses that was tossed before). That way, in this example, $\mathcal{M}$ can toss the coin 2 times, and chose to output $0$ iff both coins are head (or, equivalently, it can output $0$ if the first two bits of the random string $r$ are equal to $0$, and it outputs $1$ otherwise).
When we write "where the probability is taken over the randomness used by $\mathcal{M}$", it is exactly this idea that we fix $D$, $S$, and $D'$, and check what is the probability for that $\mathcal{M}$ to output an element of $S$ when given $D$ as output.
In our example, if we take $S = \{1\}$ and $D = 1$, then:
$$\Pr[\mathcal{M}(D) \in S] = \Pr[\mathcal{M}(D) = 1] = \frac{3}{4}$$


NMaster key from n secret key I have to derive master key from N secret key. With the help of master key, i can collect all the secret keys which is used to derive master key.

key1, key2,..keyN ==> single master key

and

single master key ==> key1, key2,..keyN

is this even possible??

Yes, it is possible. There are a number of different solutions.

One depends on a large random-looking, easily computable permutation $(\pi,\pi^{-1})$ on strings of $Nl$ bits. The master key is the $n$-bit string $\mathit{mk}$, the $i$th key share $k_i$ is an $l$-bit string, there are $N$ key shares and $0^{Nl-n}$ is a string of $Nl-n$ zeros. The concatenation of strings $x$ and $y$ is denoted by $x||y$. Then derive the key shares from the master key using $$k_1 || k_2 || \dots || k_N = \pi(\mathit{mk} || 0^{Nl-n}).$$
To recover the master key from the key shares, compute
$$\mathit{mk} || 0^{Nl-n} = \pi^{-1}(k_1 || k_2 || \dots || k_N).$$

This is secure for a random permutation, so it should also be secure for a random-looking permutation.

You can build a sufficiently large random-looking permutation using a Feistel construction, Luby-Rackoff and a random oracle.

If you want to be able to recover the master key from a subset of the key shares, you need to go to secret sharing. It should be possible to do this, but it is trickier and you don't get information theoretical security. Which probably isn't a problem. (The above permutation-solution doesn't get information theoretical security, either.)


How to test an encryption against different attacks For the last while I have been reading up on cryptography and the different kinds of methods for encryption (public key, blocks, etc) and the attacks against them. This got me wondering how to implement or calculate how well an attack would work against a encryption of my own creation.

What are the kinds of attack channels that most encryption have to protect against and how do they do it? I've read into some such as timing and information leakage, but is there a complete list out there somewhere along with information depicting on how to test a cipher against these attacks?

How are attack vectors described once one is found? I saw that some older encryption schemes depict how secure they are based on their key length (such as RSA and the private/public key bitness), and others on how many rounds minimum before a cipher is not secure (like for AES). What do these values, specifically the rounds for block ciphers like AES, mean?

Basically if I create a block cipher, what kinds of attacks should/can I test, and how would I test these attacks, against my cipher?

Thanks.

P.S: If people could comment free encryption related books on this subject of testing of attack vectors I would appreciate it.

Cryptograph Network Security by William Stallings is pretty decent read I had to read in my crypto class. Each encryption method is different, the way you can test its effectiveness as a encryption method is by what they call avalanche effects , where by changing one bit in decryption it changes a lot of other bits throughout the process.

Also I recommend checking out capture the flags online that have cryptography categories to use for real world practice. Just a simple google search will find you free sites online to practice, and you can even see write ups for the challenges to get better ideas how to attack the encrypted flag.

Hope this helps, cryptography just takes some time then you will understand it really easy. Good luck


Four-Square cipher and its keyspace Am I thinking about this correctly?

  Consider that the keyspace of the Playfair cipher is equivalent to all permutations of the alphabet, e.g. the number of distinct permutations of 25 objects, and is equal to $1.551 · 10^{25}$. (A lot!)

  1)    What is the keyspace of Four-Square, when considering both keys, as presented in this class?

Reading through the modules presented in this class, one may find:

  Like Playfair, the four-square cipher is a polygraphic substitution cipher. However, this cipher uses four 5 by 5 (four squares) boxes instead of one.

Using wolfram , you can see that $1.551 · 10^{25} =$ a very large #.
Since 4 square uses 4 boxes instead of one, we get: $1.551 · 10^{25} · 4 = 6.204·10^{25}$, which is our keyspace (another huge number).

  2)    If the alphabet for a Four-Square type cipher contained: uppercase, lowercase, the digits zero to nine, and the ligatures 'ae' and 'ce', in that ordering, (that is 64 codons); and the Four-Square tables were also extended in size to hold all of these characters, without omitting Q or combining I and J, what would the keyspace be? Would there be any problem working with this cipher?

Now there are 64 objects to deal with instead of 25.  Consider if this was a Playfair cipher: $1.551 · 10^{64}$
Again, since 4 square uses 4 boxes instead of one, we: $1.551 · 10^{64} · 4 = 6.204 · 10^{64}$.  Even though this is a lot more than our 25 codon keyspace, there shouldn’t be any problem working with this cipher (although you may need a super computer):

  The encryption procedure is simple; find the first character of the plaintext digraph in the box that is keyed with $k_1$, and the second character of the digraph in the box that is keyed with $k_2$. Then complete the square, giving the first character of the cipher text digraph is that is located in the upper-left box; and giving the second character that is located in the lower-right box.

Your math is off.

The key space of "four squares of random letters" is not four times as big as the one provided by one square, but the fourth power of that size.

To see this easier, consider the case of one $2×2$-square (or four ones), where you can still calculate everything by hand.

There are $4! = 24$ possible ways to fill a $2×2$-square. If you have four such squares, independently of each other, each has 24 ways to fill, so you get $24·24·24·24 = (4!)^4 = 331776$ ways to fill the four squares. This is a lot more than $4·(4!) = 96$. As an exercise, try to find more right groups of 4 such squares than 96 to see that this is actually true.

(An easier exercise would be to try this with 4 1×1 squares, though that is a bit less obvious to understand. There is only one $= 1! · 1! · 1! · 1! = 1!^4$ way of filling the four squares, instead of four $= 4 · 1!$ ways.)

A playfair cipher based on a 2×2 square would be trivial to break even by brute force, as the effective key space has a size of 6 (there are 4 equivalent squares each obtained by swapping rows and columns) ... and for each plain text pair, 4 of the six key pairs just act by swapping the plain text "letters" with each other. Also, you would have a plain text alphabet of size 4 (or better 3, so you have one letter left for inserting when you have double letters). You can try to break one by hand.

For our 25 square, this means that when one square gives 25! ways of filling it, four squares give $25!^4 \approx 5.7887 · 10^{100}$ different ways of filling them. That is your key space for the four-square cipher.

For the 8×8-square, you have $64!$ ways of filling them. But this is not $1.551⋅10^{64}$ (you can't simply convert factorials to powers this way), it is around $1.269·10^{89}$.

Four squares of that caliber give more than the google calculator can handle, i.e. $64!^4 = 2.592 · 10^{356}$.

To use this cipher, you don't need a computer at all (other maybe for generating your random squares), much less a super computer.

The strength of such a cipher is nevertheless much lower than a modern cipher with a similar (or even much lower) key space size would offer. Don't use such a cipher in real live.


Zero knowledge proof for opening of Pedersen commit and discrete logarithm I am looking for a proof of knowledge as such:

$PK\{ (x,r) : C = g^xh^r \land V = g^x\}$

Where $C, V, g$ and $h$ are public information and $x$ and $r$ is known only to the prover.

I.e. I have a Pedersen commit and a public key and I want to prove in zero knowledge that the committed value is the private key. Is there such a construct available?

It can be done with two Schnorr proofs, which can be interactive or noninteractive.

This is a simple way of proving knowledge of a discrete log; in the noninteractive version, to prove the knowledge of $x$ s.t. $a = g^x$ (assuming a public hash function $H$), the prover picks a random value $r$, computes $t = g^r$, $c = H(t)$, and then publishes $t$ and $s = r + cx$.  The verifier then checks whether $g^s = t a^c$

To prove the statement you want, you first publish a proof that you know $x$ s.t. $V = g^x$

The second proof is that you know $r$ s.t. $C V^{-1} = h^r$

The two combined is equivalent to the statement you are interested in.


Hash function and outputs of arbitrary length I know that Skein can output a digest of arbitrary size, with a kind of counter mode. Blocks of the resulting digest can be computed in parallel.

What about Keccak ? I know that a sponge function can generate a hash of arbitrary length, but is it possible to generate this output with a parallel algorithm ?

Keccak uses a sponge construction to output arbitrary length hashes. This is a distinctly serial operation. Although the inner permutation can be perfomed with a certain level of parallelism using bit-slicing, it is faster in software using native 64-bit operations.

P is the message input per block, z are outputs, and f is the inner permutation. In order to output a given length $x$, z is incremented until it meets or exceeds $x$, to which it is then truncated. The quantity of z required will vary due in implementation to the variable rate r not being a constant.

For example, if you need a 384-bit output and r is 128 bits, there will be 3 outputs which are then concatenated, and between each output is an additional permutation past the last input permutation (dashed line)


Exchanging encrypted messages, and decrypting without a public key? I know very little about encryption, but I was hoping someone could shed light on this cipher text exchange scheme I worked out in my head this morning:

Bob wants to send Alice a message but doesn't want anyone in the middle to discover what the message is.

We'll call the message $p$ and encode it as a number. This is how it goes; Bob chooses a random but secret number $x$. He calculates $p \times x = c$ and sends his cipher text $c$ to Alice.  Alice then chooses a random but secret number $a$. She calculates $a \times c = q$ and then sends $q$ back over to Bob.  Bob does $q / x = f$ and sends it back to Alice.  Alice then does $f / a = p$.

Sorry if it makes no sense, but what kind of encryption is this called when there's no public key yet a message is transferred encrypted and deciphered without any secret passwords being exchanged?

You're describing a form of three-pass protocol, which is a communication mechanism where neither party needs to know each other's secret key. Wikipedia describes a helpful metaphor using a box that can be locked by two padlocks:

First, Alice puts the secret message in a box, and locks the box using a padlock to which only she has a key. She then sends the box to Bob through regular mail. When Bob receives the box, he adds his own padlock to the box, and sends it back to Alice. When Alice receives the box with the two padlocks, she removes her padlock and sends it back to Bob. When Bob receives the box with only his padlock on it, Bob can then unlock the box with his key and read the message from Alice.

I assume you're using multiplication and division simply as example functions, but as others have mentioned these aren't suitable operations for this task because they're too easy to reverse. However there do exist actual encryption and decryption functions which do work this way - the necessary property is for the operations to be commutative, so that the encrypting and decrypting do not need to be done in a certain order.

In order for the encryption function and decryption function to be suitable for the Three-Pass Protocol they must have the property that for any message m, any encryption key e with corresponding decryption key d and any independent encryption key k, D(d,E(k,E(e,m))) = E(k,m). In other words, it must be possible to remove the first encryption with the key e even though a second encryption with the key k has been performed. This will always be possible with a commutative encryption. A commutative encryption is an encryption that is order-independent, i.e. it satisfies E(a,E(b,m))=E(b,E(a,m)) for all encryption keys a and b and all messages m. Commutative encryptions satisfy D(d,E(k,E(e,m))) = D(d,E(e,E(k,m))) = E(k,m).
...
A [further] necessary condition for a three-pass algorithm to be secure is that an attacker cannot determine any information about the message m from the three transmitted messages E(s,m), E(r,E(s,m)) and E(r,m).

This second condition eliminates multiplication and division, since we could look at the three transmitted messages s*m, r*s*m, and r*m and easily compute m from them.


Homomorphic Encryption operation for regression I must be missing something, and I am sorry if this is a novice question...

I have seen in places (eg. https://crypto.stanford.edu/~dwu4/talks/SecurityLunch0214.pdf page 13) that linear regression is possible on the cipher text of a fully Homomorphic Encryption system.

My question is:
if you can generate the inverse of the matrix (X^T X), then can't you generate the cipher version of the identity matrix, and determine what E(1) is? And if you have E(1) can't you generate E(2) ... E(n) using either encrypted addition or plain text multiplication?

if you can generate the inverse of the matrix (X^T X), then can't you generate the cypher version of the identity matrix, and determine what E(1) is?

I believe that the point you're missing is that homomorphic encryption is probabilistic; there are lots of legal representations of $E(1)$.  The encryption process takes the plaintext (1 in this case), and some random values (we call them random coins); different values for the coins give you different ciphertexts.

Yes, you can generate values which you know is an encryption of 1 (in fact, they can be a lot easier than doing a full matrix multiply, if you have the public key, you can just take 1 and encrypt it yourself).

And, because there are many different ways of representing $E(1)$, just because you know one of them doesn't mean that you can recognize the others (in fact, we hope there's no such way, otherwise (as you implied) the whole system is broken).


Why haven't any SHA-256 collisions been found yet? I've been thinking about this for a few days, a SHA-256 algorithm outputs 64 characters which can either be a lowercase letter or a number from 0-9. Which should mean that there are 64^36 distinct SHA-256 results.

How has a collision never been found? If I decide to find the hash for a random input of increasing length I should find a collision eventually, even if it takes years. I imagine this can also be done where the input is a large file and you just change one byte and calculate the hashes until you find a collision. Why hasn't' this happened?

I think you underestimate just how large $2^{256} \gg 64^{36}$ is.

  How has a collision never been found?

It will take a very, very, very, $\text{very}^{\text{very}}$ long time to find one. For comparison, as of January 2015, Bitcoin was computing 300 quadrillion SHA-256 hashes per second. That's $300 \times 10^{15}$ hashes per second.

Let's say you were trying to perform a collision attack and would "only" need to calculate $2^{128}$ hashes. At the rate Bitcoin is going, it would take them

$2^{128} / (300 \times 10^{15} \cdot 86400 \cdot 365.25) \approx 3.6 \times 10^{13}$ years. In comparison, our universe is only about $13.7 \times 10^9$ years old. Brute-force guessing is not a practical option.


Information leak in ElGamal encryption with message in base group Assume a finite commutative base group $\mathbb B$, some $g$ in $\mathbb B$, and $\mathbb{G} = \langle g\rangle$ the subgroup that $g$ generates, with choice of $\mathbb B$ and $g$ such that ElGamal encryption would be secure for a random message in $\mathbb G$ (semantically/under CPA).

ElGamal encryption still allows decryption if we use a random message in $\mathbb B$ rather than in $\mathbb G$. How much information about the message can leak if we do this? If necessary to get a result, restrict to $\mathbb B=\mathbb Z^*_p$, perhaps with $p$ an odd prime, and/or to $\mathbb G$ of prime order.

Notation: order of $\mathbb G$ generated by $g\in \mathbb B$ (noted multiplicatively) is $q$; private key $x$ is uniformly random with $0<x<q$; public key is $h=g^x$. Encryption of $m$ random in the message space ($\mathbb G$ for the  standard definition of ElGamal encryption, $\mathbb B$ in the question) generates one-time $y$ uniformly random with $0<y<q$, and computes $c_1=g^y$, $s=h^y=g^{x\,y}$, $c_2=m\,s$. Ciphertext is $(c_1,c_2)$. Decryption recomputes $m$ as $c_1^{q-x}\,c_2$.

It is known that if $\mathbb B=\mathbb Z^*_p$ with $p$ a large prime and $\mathbb G$ of prime order $(p-1)/2$, there's an information leak of one bit: we can determine from the ciphertext if the plaintext is a quadratic residue or not; but nothing else as far as we know. I'm unsure about the many other cases ($\mathbb G$ of smaller prime order, or not of prime order; other base groups).

My motivation for that problem came while answering this question.

Let a prime $p = 2qs + 1$.  Consider the subgroup $\mathbb{G} = \langle g \rangle$ of order $q$.  Public key is $h = g^x \bmod p$ while private key is $x \in \mathbb{Z}_q$.  The encryption of $m$ is given by $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = m \cdot h^r \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Semantic security mandates that message $m$ belongs to $\mathbb{G}$.

Let $z$ be a generator of $\mathbb{F}_p^*$.  So we can write $m = z^M \bmod p$ for some $M \in \mathbb{Z}_{p-1}$.

Raising $c_2$ to the power of $qs$ yields $${c_2}^{qs} \equiv z^{Mqs \bmod (p-1)} \equiv (z^{qs})^{M\bmod 2} \equiv (-1)^{M\bmod 2} \pmod  p$$
The value of $(M \bmod 2)$ indicates whether or not message $m$ is a square in $\mathbb{F}_p^*$.
Raising $c_2$ to the power of $2q$ yields $${c_2}^{2q} \equiv z^{M2q \bmod (p-1)} \equiv (z^{2q})^{M\bmod s} \pmod  p$$
If $s$ is small or smooth, an attacker can recover the value of $(M \bmod s)$ as the discrete logarithm in $\mathbb{F}_p^*$ of ${c_2}^{2q}$ with respect to base $z^{2q}$.

Let a cryptographic function $H \colon \mathbb{G} \to \mathbb{F}_p^*$  viewed as a random oracle. Semantic security can be met with message space $\mathbb{F}_{p}^*$ by defining the ciphertext as the pair $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = [m \cdot H(h^r \bmod p)] \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Decryption of $(c_1, c_2)$ is obtained as $m = [c_2 /H({c_1}^x \bmod p)] \bmod p$.

Another option to get semantic security without random oracles is to take $s = 1$ ($p = 2q+1$ is a safe prime).  The set of valid messages is restricted to $\mathcal{M} = \{1, \dotsc, (p-1)/2\}$.  The encryption of a message $m \in \mathcal{M}$ is given by the pair $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = m^2 \cdot h^r \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Decryption of $(c_1, c_2)$ is obtained in two steps as $m^2 = c_2 /{c_1}^x \bmod p$ and then $m$ as the square root (modulo $p$) of $m^2$ in the set $\mathcal{M}$.  Note that if $m \in \mathcal{M}$ then $-m \bmod p = p-m \notin \mathcal{M}$.


Does encrypting a hash of the message yield a secure MAC? Is $mac = enc(hash(x))$ a secure MAC for hash = SHA256 and enc AES in CBC mode or ECB mode. Normally AES-CBC is malleable. But in this case I use a hash function for the one-way property.

For example, an attacker can change the iv vector:

In CBC c[0] = enc(m[0] ^ iv) an attacker chooses m'[0] and computes iv' by m[0] ^ iv = m'[0] ^ iv'. So, in this case I find 2 digests with the same MAC: hash(x) = m[0]||m[1] and hash(x') = m'[0]||m[1]. But I have found 2 digests, I can't find x' than hash(x') = m'[0]||m[1].

Is my MAC a secure MAC?

Yes, your MAC is secure.  It's probably not quite as secure as you're expecting it to be, and it's not a construction I would recommend to anyone, but it should be secure.

Let's start with a simpler variant: $F_K(M) = E_K(H(M))$ where $H(\cdot)$ is a 128-bit collision-resistant hash (say, the first 128 bits of SHA1) and where $E_K(\cdot)$ is a 128-bit block cipher in ECB mode.

This is secure, under the assumption that $H$ is collision-resistant and $E$ is a secure block cipher, as can be shown using standard methods.  Since $E$ is a secure block cipher, it is a secure PRP, which implies that it is a secure PRF (by the PRP/PRF switching lemma).  Now it is known that applying a PRF to the hash of a message yields a secure MAC.

However, this still isn't a very good construction to use in practice.  It offers weaker security than, say, SHA1-HMAC.  Indeed, the authors of SHA1-HMAC explicitly considered something like this and rejected it; instead, they decided to design something new that would be better.  Read the SHA1-HMAC research paper for details (it is very readable and a classic), but concisely, one problem with your scheme is that it is susceptible to offline attacks.  Someone can try to find a collision in the hash function using an offline attack, and if they succeed, they immediately have broken the MAC.  SHA1-HMAC does not have this limitation.

Now I know that's not quite what you proposed, but it's still instructive.  What you proposed is a more complicated version of that scheme, but the complications don't really make it much better; they just it make it harder to analyze its security.

For instance, let's look at the scheme where encrypt the SHA256 hash using AES in ECB mode.  Is this secure?  Yes, it's secure, but less secure than you might expect.  If an attacker has observed the MAC on $m$ known messages, then the attacker knows a set of $2m$ known plaintext/ciphertext pairs for AES; let $\mathcal{P}$ denote the set of known plaintexts for which the corresponding ciphertext is known to the attacker.  Now suppose the attacker picks a new message $M$ (different from any of the $m$ known messages) and checks if he knows enough to predict its MAC.  Let $X,Y$ denote the left and right half of SHA256($M$), respectively.  If $X \in \mathcal{P}$ and $Y \in \mathcal{P}$, then the attacker can predict the MAC on the message $M$ with certainty, which is a break of the scheme.  What's the probability that this happens?  The probability is

$$\Pr[X \in \mathcal{P} \wedge Y \in \mathcal{P}] = \Pr[X \in \mathcal{P}] \times \Pr[Y \in \mathcal{P}] = |\mathcal{P}|^2/2^{256} = 4m^2/2^{256}.$$

So, if the attacker picks a message $M$ at random, he has a $m^2/2^{254}$ chance of being able to guess its MAC.  If the attacker picks $2^{90}$ messages $M$ at random, there's roughly a $m^2/2^{154}$ chance that one of their MAC's can be predicted, which breaks the scheme.  The attacker can do all of those calculations offline.  So, if we consider an attacker who observes the MACs on $m$ known messages and who does $2^{90}$ offline calculations, that attacker can break your scheme with probability $m^2/2^{154}$.  If $m=2^{77}$, this is a break with probability close to 1.

This attack is not a serious problem in practice.  However, it demonstrates that the security level is less than one might expect from a 256-bit MAC.  For this reason alone, I don't recommend your scheme.  Instead, something like AES-CMAC or SHA256-HMAC is a better choice.

The good news is that I would expect that one can prove that this is the best an attacker can do (modelling SHA256 as a random oracle, and assuming the block cipher is secure).  I haven't tried to write out and verify all the details, so take this with a grain of salt, but I fully expect that the proof should work out.

I haven't tried to think about what happens if you encrypt the SHA256 hash using AES in CBC mode.  That seems a bit sketchy; I'm not sure why we'd introduce an extra IV and lengthen the MAC for no apparent reason.  I don't think the construction is of any practical interest, given that better schemes exist, and that the better schemes are well-vetted and plenty good enough in practice.


With ECDSA is there a way for the verifier to calculate any properties of $k$? With ECDSA, given $(r,s)$ and $m$, is there a way for a verifier to calculate any (boolean) properties of $k$, without knowing $k$ or the private key $D_A$?

(I understand that $k$ should be random, or follow RFC6979, but I'm curious.)

In particular, could the verifier compute, given a signature $(r,s)$ and a message $m$, that:

$k$ is odd
$k$ has some mathematical relation to one of the curve parameters
$k$ has some mathematical relation to the public key $Q_A$
$k$ has some mathematical relation to the (truncated) message hash $z$
$k$ was deterministically generated with RFC6979 https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#cite_note-4

for the value of $k$ which was used to generate the signature.

(Variable names taken from https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

There are no relation we are currently aware of.
The reason is as follows. The map
$$k \mapsto (k G).x$$ is assumed to be a good pseudo random number generator.
(The NSA infiltration of the Dual EC drgb has nothing to do with that fact).
This basically says that k and r can be seen as independant random variables.


Security model for privacy-preserving aggregation scheme. Suppose that $S=(E,D)$ is an additively homomorphic encryption scheme. Now I want to design a protocol $P$ such that given inputs $x_1,x_2,..,x_n$, the adversary $A$ (who can decrypt) can only learn $\sum x_i$ and nothing else. To do that, $P$ first generates random values $r_1, r_2,..,r_n$ such that $\sum r_i = 0$. Then, $E(x_1+r_1)\times..\times E(x_n+r_n) = E(\sum x_i)$.

The trouble I have is when adversary has some domain knowledge of $x_i$. For example, if it knows that $x_i \geq 0$, and later decrypts $E(\sum x_i)$ to learn that $\sum x_i = 0$, it can learn that $x_i = 0$ for all $i$.

How could I formulate a security game that takes into account such attacks based on domain/auxiliary knowledge? Would IND-CPA security model be sufficient? How's about IND-CCA?

I've read the paper [1], but I don't think it addresses the domain/auxiliary knowledge.

[1] Shi et al. Privacy-preserving aggregation of Time-series Data (NDSS'11)

This is tricky and I don't know that there is a generic way to take care of all domain/auxiliary information.

The way we typically do proofs in multi-party computations is by defining an ideal world and show that the information generated in the ideal world (usually the encrypted inputs and the outputs) could be used to simulate the real world protocol transcript (at least in the semi-honest case). If the simulator can generate the transcript, then clearly the transcript contains no additional information beyond what is already present in the info generated in the ideal world. Therefore, the protocol cannot leak additional information.

Given the protocol you've described, the ideal world would be a trusted party which cannot be corrupted is given encrypted inputs from each party. The trusted party decrypts them all (we don't need homomorphic encryption in the ideal world), adds them up and returns the answer. Well, if the answer is $0$ as you suggest, this leaks information. But, that information is leaked in the ideal world as well as in the real, so we don't consider it a breach of the protocol.

The most natural way then to deal with this problem in the ideal world is to have the trusted party check the output for certain cases (e.g., $0$) before outputting the answer. If one of those cases is achieved, the trusted party output $\bot$. You can definitely implement this functionality in your real world protocol using a secure comparison of some sort. Your protocol will obviously be more complex, but such is life.

That shows how you would handle a specific case. There are definitely other cases where domain/auxiliary information combined with the answer will allow adversaries to infer additional information. I don't know of any generic way to handle all of this, and quite possibly it is impossible to handle in a generic way.

Consider the following, assume we have a generic multi-party comptuation protocol $\pi$. Furthermore, assume this protocol is proven secure for up to $n-1$ adversarial parties.

Now, we might be tempted to use this protocol to compute the sum you describe in the question. But, there is a problem. If there are $n-1$ adversarial parties, they can all set their inputs to $0$. The single honest part sets its input to the proper input say $x_h$. The output of the computation is clearly $x_h$ so the honest party's input is leaked. This would happen in the (standard) ideal world too, though. So even though the protocol can handle up to $n-1$ adversarial parties, the specific functionality we are computing can only handle up to $n-2$ adversarial parties. This suggests that the functionality to be computed must have an impact on the adversary model we choose, and seems to suggest that a generic solution to the problem you mention might not be possible.

So then, it seems the path forward would be to list all possible corner cases for a computation where some undesired leak occurs due to domain/auxiliary information, then adjust the computation accordingly. Then the security could be proven using standard methods. This could then potentially be extended to classes of computations, etc.


Why does DES use a block size of 64 bit? Why do we use 64 bit as block size for the DES algorithm? Is there a reason not to use another block size, for instance 72 bits?

A minimum block size is required for a block cipher mode of operation to be considered secure. If the block size is too small then issues may arise.

Many modes of operation for instance use an IV that has the same size as the block size. If the block size would be smaller then a randomly generated IV could repeat. This will happen quickly especially if many messages are encrypted using the same key.

Worse, a mode such as CBC uses the last ciphertext as vector for the next step, so the ciphertext could repeat as well, which means that the ciphertext could leak information about the plaintext. For counter (CTR) mode the counter could start to repeat, which could lead to a complete loss of confidentiality of the plaintext message.

So using a block cipher with a small block size will lead to security issues, even if the block cipher itself is considered secure.

On the other hand a block should not be too big. Larger block sizes require a more complex cipher and likely require more internal state. This is especially a problem if space is an issue, and space always is for hardware implementations of the block cipher.

Also note that modes of operation always require at least one operation of the full block cipher for the last bytes of the message. So if 1 byte is encrypted the full block cipher still needs to be executed for that single byte. Many modes of operation output a multiple of the block size, so there may be additional storage / communication overhead for larger block sizes (on top of the larger IV).

So using a block cipher with a larger block size will increase the memory requirements and as well as the CPU and storage overhead required for the ciphertext.

To simplify calculations, enhance memory efficiency (alignment) and so forth, many computer algorithms perform operations using powers of two. Although it would probably be possible to specify a block cipher as an algorithm of 65 bits the algorithm and implementation would be tricky to design correctly. Ciphers are generally specifies using byte boundaries and preferably using powers of two.

Furthermore, it makes sense to make the (encoded) key size and the block size match up. That way it is easy to encrypt one key with the other. A DES key consists of 56 bits and 8 parity bits. That means that a 64 bit DES key can be directly encrypted (wrapped) by another DES key, without requiring any mode of operation.

AES-192 - which has a key size of 192 bits and a block size of 128 bits - is awkward to correctly use because 192 is not a multiple of the block size of 128 bits.

In the end the block size is selected by the designers with the above three points in mind. The block size is therefore a compromise between security and efficiency.

Modern ciphers do not use a block size of 64 bits anymore; most cryptographers would consider 64-bit block ciphers outdated. They may not be broken, but the 64 bit block size makes them insecure in many situations. Single DES is of course considered broken, mainly because of the small effective key size.

AES has a block size of 128 bits, as this was mandatory for every AES candidate during the AES competition. But even 128 bits is sometimes considered not that secure anymore. Counter mode encryption and many authenticated ciphers that rely on it have limitations, mainly when the 128 bits are used for different purposes (a 64 bit random nonce and 64 bit counter, for instance).

So other block ciphers even use a larger block size. Threefish (which is part of Skein, one of the SHA-3 candidates) uses a block size of 256 bits. This helps it being used as a tweakable block cipher within the Skein hash algorithm.

With Blowfish using 64 bit block size, Twofish using 128 bits and Threefish using 256 I guess you can see where we're heading. That said, a block size of 256 / 512 bits may be large enough for most purposes, so this trend to larger block sizes will likely not continue forever.

Note that many modern CPU's have been designed with 64 bit and SIMD operations and may be more efficient for larger block sizes and / or larger internal state. So a smaller block size may not always be more efficient; for instance SHA-512 is commonly both more secure and faster than SHA-256 on a CPU with an AMD64 instruction set, especially for large messages.


SHA-1 collision resistance I'm researching on the SHA-1 algorithm and looking for reasons why it has fallen prey to differential cryptanalysis. I have read the research papers by Merc Stevens and Wang both of which describe how to attack and reduce the complexity of the attack on sha1 but none provide a way to reduce its vulnerability. Please help me out by explaining how to increase the strength of a hash function against differential cryptanalysis.

Probably the biggest vulnerability is that the message expansion is too linear. The linearity of the SHA-1 message expansion is why we are able to find such good differential paths. There can be differences at the beginning of the message and by the end of the message expansion they are mostly canceled out.


Can insecure algorithms be combined to form a secure algorithm? This is hypothetical as I can't think of any reason to do this, but out of curiosity...

Could I, for example, take the MD5 digest of a message and concatenate it with the SHA-1 digest (not quite broken, but getting close), to form a secure concatenated digest? Intuitively, I would think the chances of finding a collision that crossed the two algorithms would be low enough to make this secure, but I'm not sure how to verify that.

At the time of answering, the question was can insecure algorithms be combined to form a secure algorithm?

Yes: Think of any secure round-based block cipher. The independent rounds are not secure, but put together the overall cipher is. I think my favourite example is (currently) the Even Mansour cipher,
which combines two xor operations and one unkeyed permutation to form a secure cipher.

 nb: I know this isn't a direct link, but its the best introduction I know of

For a good discussion of the hash example in your question, read this question.


Can a block cipher with fixed point permutations be a good PRP? Let $E:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$ be a good PRP and consider blockcipher $\widetilde{E}$ defined as follows
$$\widetilde{E}(K,X) = \begin{cases}K & \text{if } X=K \\ E(K,K ) & \text{if } X = E^{-1}(K,K)\\ E(K,X) & \text{otherwise}\end{cases}$$
Black used this to show that Matyas-Meyer-Oseas construction which is proven in the ideal-cipher-model can fail in the standard model, i.e. it will fail if we instantiate it with $\widetilde{E}$;

So $\widetilde{E}$ is the same block cipher as $E$  with one change: we now have the invariant  that $E(K, K)= K$ for all $K \in \{0, 1\}^n$. Clearly   $\widetilde{E}$
  is a good PRP since have $E$ was:  for a randomly chosen key $K, \widetilde{E}(K,\cdot)$
 is computationally indistinguishable from a random permutation.

Is the claim computationally indistinguishable from a random permutation true?
We can say that for a fixed key $K$, $\widetilde{E}$ we will always output $K$ if $ K = X$
The probability of getting a single point is fixed from all permutations of $k$ elements is $\frac{(k-1)!}{k!} = \dfrac{1}{k}$.
If we turn this into permutations generated by the $n$-bit block cipher. Then we have $\dfrac{1}{2^n}$. Therefore the permutations of $\widetilde{E}$ is distinguishable and $\widetilde{E}$ cannot be a good PRP.
Any missing point?
Could one provide a formal proof for this an example?

Short answer
As Maeher said, the adversary cannot recognize which points are reprogrammed or distinguish $\widetilde E$ from $E$, given oracle access to $\widetilde E$ (or $E$). This is because the adversary who detects such points can also be used to break the PRP security of $E$ by finding the key $K$.
Formal proof
It suffices to prove that no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access. That is, we will prove that for any efficient $A$ with $q$ query to the oracle such that
$$
|\Pr_{K}[A^{E(K,\cdot)}()=1] - \Pr_K[A^{\widetilde E(K,\cdot)}() =1]|=\epsilon, \label{1}\tag{1}
$$
it holds that $\epsilon$ is negligibly small.
To measure the advantage in a different term, first note that a difference in the oracle access to $E$ and $\widetilde E$ only happens if the adversary query $(K,K)$ or $(K,X)$ for $X=E^{-1}(K,K)$ to the oracle. Otherwise, both oracles work exactly the same and there is no chance to figure out the difference. Let's say the above event by $\rm Bad$. Then it holds that
$$
\epsilon \le \Pr_K[A^{E(K,\cdot)}()=1|{\rm Bad}] \le \Pr_K[A^{E(K,\cdot)}()|{\rm Bad}].\label{2}\tag{2}
$$
Note that whether the oracle is $E$ or $\widetilde E$ doesn't make any difference. We choose $E$ here.
What is the probability of $\rm Bad$? We define a new adversary $B$ having oracle access to $E$ to find the key of PRP as follows.

Choose a random $1 \le i \le q$.
Run $A$ with the given oracle right before $i$-th query. Let the input of $i$-th query by $X$ and with probability, $1/2$ do either

output $X$, or
query $X$ to the oracle and output the answer $E(K,X)$.

Suppose that in the $i$-th query the $\rm Bad$ event occurs. If the first case of $\rm Bad$ occurs, i.e. $A$ queries $K$ to the oracle, then $B$ outputs $K$ with probability $\epsilon/2q$ by the first action (output $X$ directly).
On the other hand, if $A$ queries $E^{-1}(K,K)$, the second action outputs $E(K,E^{-1}(K,K))=K$ that also has probability $\epsilon/2q$.
Overall, the algorithm $B$ outputs $K$ with probability $\epsilon/2q$.
However, the PRP security of $E$ says that this probability is negligibly small. This implies $\epsilon$ is small as well since $q$ is polynomially bounded (given that $A$ is efficient). Thus no efficient algorithm can distinguish $E$ from $\widetilde E$ via oracle access, and since $E$ is PRP, $\widetilde E$ is a PRP as well, which is as we desired.


Is it safe to truncate/compress SHA256? I am writing a small personal project where I would like to use AES to encrypt some documents. It seems to work pretty well, but I was wondering about one point of my code. The current structure is user inputs password -> key = sha256(password) -> compress(key) -> AES(document, key). Where compress XORs the key with itself. So for 128 bit AES the first half is XORed with the second to get a 128bit key. I do a similar operation for 192 bit AES. I have a few questions about this:

Is it safe? If not, could I just drop the extra bits?
Is there a better way to go from a password to a key? I think for the average password entropy is pretty low.
Could I use this method to generate an IV for some other block cipher mode?

Someone else should chime in here just to be sure, but as far as I know truncating SHA256 is "safe", in the sense that it would be as good as any other "safe" 128 bit hash. I don't think XORing helps in any way, dropping the bits is probably better. Your application of a truncated SHA256, however, is not safe.
Yes, there is absolutely a better way. Like you said, average password entropy is low. Your key therefore has low entropy. Brute forcing a low entropy key is easy, when the key derivation is a simple SHA256 round. You need to use a specialized password hashing function. SHA256 is designed to be fast, you need a function that is designed to resist such brute force attacks. Examples include Argon2, scrypt, and PBKDF2.
This depends on the design. An IV should not be predictable. What kind of password would you be using to generate an IV? Would you use it multiple times? Are there reasons why you can't use a random IV?


How does $g^{x^2} \bmod p$ help you find $x$? I was thinking about the Diffie-Hellman key exchange. One fact that we seem to know is that given a group generator $g$, a prime $p$ and the expression $g^x \bmod p$ its believed to be hard to find $x$; or more accurately $x \bmod(p-1)$.
Now the question is, what if we gave away some extra information. Such as $g^{x^2} \bmod p$.
My guess is that surely this should help us find $x$ in some fashion, but it’s not clear how.
Finding an exponent that sends $g^x$ to $g^{x^2}$ is as hard as finding $x$ given just our usual initial data. So that’s probably not the right way to exploit this information.

It is not known that knowing $g^{x^2}$ would help in any meaningful way to solve the discrete logarithm problem.
What you are describing can be generalized to asking whether in a group $\mathbb{G}$ giving an attacker $$(g, g^x,g^{x^2},\dots,g^{x^q})$$ for some $q$ and a uniformly chosen $x \in |\mathbb{G}|$ makes it feasible to recover $x$.
It is generally assumed that this is not the case. In fact the assumption that recovering $x$ remains hard is called the $q$-strong discrete logarithm ($q$-SDL) assumption and has been used before. [GOR11] Similarly, the bilinear variant is also assumed to be hard. [FS20]
While the $q$-SDL assumption itself is not used very often, it is actually implied by a variety of much more commonly used variants of $q$-strong Diffie Hellman assumptions. [TS10]

[GOR11] Vipul Goyal, Adam O'Neill, and Vanishree Rao. "Correlated-Input Secure Hash Functions". TCC 2011
[FS20] Nils Fleischhacker and Mark Simkin. "Robust Property-Preserving Hash Functions for Hamming Distance and More". Cryptology ePrint Archive, Report 2020/1301, 2020
[TS10] Naoki Tanaka and Taiichi Saito, "On the $q$-Strong Diffie-Hellman Problem". Cryptology ePrint Archive, Report 2010/215, 2010


Using similar passwords and salts for PBKDF2 I'm trying to generate a bunch of pseudo-random keys for AES using PBKDF2, where the AES ciphers will be used in CTR mode as pseudo-random number generators. My goal is to create a 2-dimensional array, where each entry is a pseudo-random sequence generated by a separate PRNG. The reason for using separate PRNGs is simply because I want each cell to have equal cost to calculate (due to the PBKDF).

So I have two random strings, r1 and r2 (user provided), and I'm generating the AES key for cell (x,y) as PBKDF2(i || r1, r2 || j), where i and j are single characters bijectively mapped to x and y respectively, and || denotes concatenation. I'm using HMAC-SHA256 for the PRF, and nominally 1000 iterations of the PBKDF2. Currently r1 and r2 are 16 bytes each, but I can make them basically any size.

So my questions are:

Is there any weakness in using such closely related inputs to PBKDF2, in particular when used as AES keys for CTR more?
Is there any shortcut for calculating the result of the PBKDF2 for different cells that is any faster than having to calculate it from scratch for each cell?

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


Necessity of Randomness of Salts? Given the desire to have unique salts for each user of your system, is it actually necessary to create a cryptographically-random salt for each user?

If your system already has some other unique user identifier (be it an ID, user-name, or an Email address) is there any effective decrease in your security if you simply use that value as your salt? It results in a unique salt for each user, and does not require the additional generation and tracking of a new value per user.

If your system already has some other unique user identifier (be it an ID, user-name, or an EmailAddress) is there any effective decrease in your security if you simply use that value as your salt?

The salt in a hash actually forms two different purposes. Generally, it is acceptable for a salt to be known, so let us consider H() a hash function, S, some data and P something to protect. From this information we store H(S+P) and S. There are two consequences for the attacker in generating a rainbow table for H(S+P):

Either they can generate a huge rainbow table for the entire set of possibilities that might be S+P. The longer the data you wish to reverse in a hash, the larger the data storage requirement of the rainbow table, so extending the length of the hashed data makes it infeasible to reverse the hash by generating a generic rainbow table.
The attacker can generate a rainbow table for the specific fields of input missing for a specific salt. Clearly, the usefulness of a rainbow table is then restricted to a specific set of hashes to attack, since in theory all other hashes should be useless.

In the case of 1) anything you add as salt will do, quite literally. The problem is the case of two. The reason for using unique, random salts is that the chances of colliding salts for a specific hash output are vastly reduced. For example, hashing userid:fred:mypassword and userid:fred:myotherpassword, a rainbow table generated knowing the salt userid:fred and the correct construction of the hashed text would work across both cases.


What's a random involution? What are the properties of random involution? What is the difference between random involution and random permutation?

An involution is a function $f$ from a set to itself, such that $f\circ f$ is identity (i.e. applying the function $f$ on the result of the function $f$ gets back to the original element, i.e. $f=f^{-1}\,$). Recall that $\circ$ is function composition.
A permutation is a function $f$ from a set to itself, such that there exists a function $g$ from that set to itself, such that $g\circ f$ is identity (i.e. applying the function $g$ on the result of the function $f$ gets back to the original element). Equivalently, it's a bijection from that set to itself.
It follows that every involution is a permutation. And a permutation $f$ is an involution if and only if $f\circ f$ is identity.
A random involution (resp. permutation) is one chosen (implicitly: uniformly) at random among these over a certain finite set.
There are $n!$ (OEIS A000142) permutations of a set of $n$ elements, but much less involutions (A000085) for $n>2$. Orange is the number of permutations and blue is the number of involutions.

Among differences of cryptographic significance: a permutation can be one-way, but an involution can't (since any algorithm implementing an involution implements its inverse).
Also: for all $k\in[1,n]$, iterating a random permutation starting from a fixed point cycles on or before $k$ step(s) with probability $k/n$, while for a random involution that's certain when $k\ge2$, and with probability above $1/n$ for $k=1$ and $n>2$.


Are safe primes $p=2^k \pm s$ with $s$ small less recommandable than others as a discrete log modulus? I take the definition of safe prime as: a prime $p$ is safe when $(p-1)/2$ is prime.

Safe primes of appropriate size are the standard choice for the modulus of cryptosystems related to the discrete logarithm problem, such as Diffie-Hellman.

A modulus $p=2^k \pm s$ with $s$ small makes exponentiation $\bmod p$ appreciably simpler (the problem of quotient estimation in classical Euclidean division all but vanishes, and the cost of modular reductions becomes negligible compared to multiplications). This, and the desire to use a non-arbitrary, compactly stored modulus, makes it tempting to prefer such choice of $p$. Like "the modulus shall be the biggest 2048-bit safe prime, which is $p=2^{2048}-1942289$".

Are there any major reason not to do that, like a much faster algorithm for the discrete logarithm problem?

Short answer: Yes.

The discrete logarithm can be attacked in a multitude of ways: Baby-step giant-step (BSGS), Pollard's Rho, Pohlig-Hellman, and the several variants of Index Calculus, the best of which currently is the Number Field Sieve.

Let $n$ be the order of the generator of our field $\mathbb{F}_p$; it is $n = p-1$. We are trying to find $x$ given $a$ and $b=a^x$ in the above field.

Pollard's Rho and BSGS

In Baby-step giant step, we are trying to find $i$ and $j$ such that $b(a^{-m})^i = a^j$, where $m = \lceil \sqrt{n} \rceil$. Once we find such a pair, the discrete logarithm $x = i m + j$ follows, as $ b(a^{-m})^i = a^j \Leftrightarrow a^{x - m i} = a^j \Leftrightarrow x \equiv mi + j \pmod{n}$.

To do so, we first compute a table of all $a^j$ for all $j$ up to $m-1$. Then we iterate through all $i$ up to $m-1$, and compare $b(a^{-m})^i$ with $a^j$. Ignoring arithmetic costs, the runtime of this method is at most $2(m-1) = O(\sqrt{n})$ (with the same space requirements).

Due to the large space requirements, BSGS is rarely used in practice. Instead, we turn to Pollard's Rho. The crux of this method is to find a colliding nontrivial pair $(i,j)$ and $(k,l)$ such that $a^ib^j \equiv a^kb^l$. It follows that $x = \frac{k-i}{l-j} \pmod{n}$, since $a^i a^{xj} = a^k a^{xl} \Leftrightarrow a^{i + xj} = a^{k + xl} \Leftrightarrow i + xj \equiv k + xl \pmod{n}$.

So Rho comes down to finding a collision quickly. This can be done with various algorithms, Floyd's being the oldest and best known. The good news is that we can try and find a collision without an enormous table; the not so good news is that the algorithm is probabilistic, although the birthday paradox tells us we should expect a collision in about $\sqrt{n}$ steps.

In any case, these attacks are no good against a safe prime, where the order large enough that $\sqrt{n}$ is computationally unfeasible.

Pohlig-Hellman

The Pohlig-Hellman approach relies on the observation that there is an homomorphism $\phi$ from $a$ and $b$ from their group of order $n$, to the subgroup of order $p_i^{e_i}$ dividing $n$. In general, given $n = p_1^{e_1}p_2^{e_2}\ldots p_m^{e_m}$,

$$
\phi_{p_i^{e_i}}(a) = a^{n/p_i^{e_i}}
$$

This allows us to compute the discrete logarithm of $\phi_{p_i^{e_i}}(a)$ and $\phi_{p_i^{e_i}}(b)$, which really is the discrete logarithm of $a$ and $b$ modulo $p_i^{e_i}$. From this observation, it is a matter of computing the logarithm modulo all prime divisors of $n$ (using the methods in the previous section) and combining them together using the Chinese remainder theorem.

If $n$ has many small prime divisors, i.e., it is smooth, this method is very much faster than Rho or BSGS. In a safe prime, however, this is not the case, since the order $n$ is the product $2q$, for a very large $q$. Pohlig-Hellman doesn't help much here.

Index Calculus

Index Calculus is the basis for the best-performing algorithms to compute discrete logarithms modulo safe primes. Suppose we know the logarithms of $2$ and $3$; finding the logarithm of $12$ is easy: $\log_a12 = 2 log_a2 + log_a3$, since $12$ factors into $2^2\times 3$.

We can generalize this method to arbitrary elements. Start by defining the factor base, i.e., all the primes up to some bound $B$. Then, find the logarithms of all the elements of the factor base (this is the tricky part). Finally, factor $b$ into the factor base, and simply add all the logarithms corresponding to the factorization you find. If $b$ does not factor completely into the factor base, multiply $b$ by some known exponent of $a$ and try again.

Finding the logarithms of all the primes up to $B$ requires some trickery. It has two major steps:

For $k_i \in [1..n]$, find (usually by sieving) at least $\pi(B)$ elements $a^k$ that factor completely into the factor base. Store both $a^{k_i}$ and its complete factorization.
Now we have the linear system (modulo $n$):
$$
\begin{eqnarray}
e_{1,1} \log_a 2 &+& e_{1,2} \log_a 3 &+& \ldots &+& e_{1,{\pi(B)}} &=& {k_1} \\
e_{2,1} \log_a 2 &+& e_{2,2} \log_a 3 &+& \ldots &+& e_{2,{\pi(B)}} &=& {k_2} \\
&&&&\ldots&&&& \\
e_{{\pi(B)},1} \log_a 2 &+& e_{{\pi(B)},2} \log_a 3 &+& \ldots &+& e_{{\pi(B)},{\pi(B)}} &=& {k_{\pi(B)}} \\
\end{eqnarray}
$$
Solving the above linear system gives us the needed logarithms for the factor base.

The runtime of this method, for appropriate choice of $B$, is $\exp{((2+o(1)((\log n)^{1/2}(\log \log n)^{1/2}))}$. This is not strictly polynomial, but is a big improvement on the previous methods.

Number field sieve

The number field sieve is currently the best algorithm for both integer factorization and discrete logarithms over finite fields. For the discrete logarithm, it is analogous to the above index calculus, with a few major modifications:

We are working in the number fields $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$ instead of the integers; there is, however, a map from such fields to the integers under some conditions. The number fields are defined by the polynomials $f_1$ and $f_2$ of degree $d_1$ and $d_2$; there must exist an integer $m$ such that $f_1(m) = f_2(m) = 0 \pmod{p}$.
The factor base is formed by the primes in both $\mathbb{Q}[\alpha]$ and $\mathbb{Q}[\beta]$, up to bounds $B_1$ and $B_2$.
During sieving, we look for pairs $(x,y)$ such that $N_{f_1}(x + \alpha y)$ and $N_{f_2}(x + \beta y)$ are $B_1$ and $B_2$-smooth, respectively, where $N_{f_i}$ is given by
$$
N_{f_i}(x + \alpha y) = y^{d_i} f_i(x/y)
$$

The speed of the number field sieve hinges on the speed of finding $(x,y)$ with smooth norms $N_{f_i}(x,y)$. In turn, the probability of $N_{f_i}(x,y)$ being smooth is linked to its size: the smaller it is, the more likely it is to be smooth. And in turn, the size of $N_{f_i}(x,y)$ is determined by $x$ and $y$ (obviously), but also by the coefficients of $f_i$! When $f_i$ has very small coefficients, the number field sieve becomes asymptotically faster, from

$$
\exp ( (1.923 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3})
$$

to

$$
\exp ( (1.526 + o(1))( (\log n)^{1/3}(\log \log n)^{2/3}).
$$

When one chooses a prime $p$ very close to $2^k$, it becomes easy to find a sparse polynomial that has a root modulo $p$. In your example, $p = 2^{2048} - 1942289$, we can find the degree $8$ polynomial

$$
x^8 - 1942289,
$$

since $2^{2048} - 1942289 = (2^{256})^8 - 1942289$. This polynomial has very small coefficients, that render the number field sieve for the discrete logarithm in this field much faster that it would be for a random 2048-bit prime.


Is cryptographic function used in MAC/HMAC public knowledge? I would like to store password digests in structure that contains information how digest were generated; There will be concatenated these three values:

{Name} of hashing functions used for computing HMAC (e.g. SHA256)
{Salt} - randon 32 bytes of key data
{Digest} - derived digest from {Salt} and cryptographic function {Name}

As divider I would like to use "$" (U+0024, DOLLAR SIGN) and encode it into Base64, this encoded value I would like to store in database.

Something like this:

SHA256${...salt data...}${...digest data...}

Reason why to store hashing function name is because backward / forward compatibility (authenticating).

Question - is information about hash function in this structure a security vulnerability? Is hashing function public knowledge?

is information about hash function in this structure a security vulnerability? Is hashing function public knowledge?

According to Kerckhoffs' principle  the adversary is allowed to know everything about the system except the key, and that includes the algorithm itself. Shannon formulated this as "the enemy knows the system".

Assuming that the system is respecting Kerckhoffs' principle, then your question is actually an assumption in the security analysis. But this depends on what kind of analysis was done for the actual system in question.

If we're looking just at the usage of any of the commonly used, state-of-the-art cryptographic functions (e.g. SHA256), then this is not a problem: The knowledge of the algorithm itself is not a vulnerability. Security is based on the key being secret and nothing else.


What does the minimal number of round of "nr" use Keccak to avoid “collision attack”? What does the minimal number of round of "nr" use Keccak to avoid collision attack?

$$nr = 12+2L$$

Cursory literature search suggests that the best collision attacks reach only six rounds of Keccak:

Kexin Qiao, Ling Song, Meicheng Liu, and Jian Guo, ‘New Collision Attacks on Round-Reduced Keccak’, in Jean-Sébastien Coron and Jesper Buus Nielsen, eds., Advances in Cryptology—EUROCRYPT 2017, April 2017, Springer LNCS 10212, pp. 217–243 (link, preprint)
Ling Song, Guohong Liao, and Jian Guo, ‘Non-full Sbox Linearization: Applications to Collision Attacks on Round-Reduced Keccak’, in Jonathan Katz and Hovav Shacham, eds., Advances in Cryptology—CRYPTO 2017, Part II, Springer LNCS 10402, August 2017, pp. 428–45 (link, preprint)

Of course, attacks only get better, so it would be imprudent to choose six rounds.
 This state of affairs justified the use of a mere twelve rounds in KangarooTwelve at substantial speed increase over the twenty-four used by SHA-3.


What is the most popular cipher suite used in TLS 1.2 for HTTPS? I'm trying to do some performance (time) calculations over TLS. I have the data I need for a variety of cipher suites but in order for the calculations to generalize well, I need to know if there is a clear most popular choice for TLS 1.2 cipher suite. Data to back up any answers would be appreciated.

The first web search hit I find is:

https://scotthelme.co.uk/alexa-top-1-million-analysis-february-2018/

This claims that the most widely supported cipher suite among the Alexa top 1m sites is ECDHE-RSA-AES256-GCM-SHA384, supported by 147 985 servers.  Raw data and methodology are at the link.

Other links found by a quick search that may have similar data about HTTPS servers:

https://jve.linuxwall.info/blog/index.php?post/TLS_Survey
https://www.ssllabs.com/ssl-pulse/

(This answer will be outdated within a year or two, if not in months.)

If you are trying to decide what cipher suites to configure your HTTPS server to use, based on what browsers you want to support and what software you're running on the server, you should use this tool: https://mozilla.github.io/server-side-tls/ssl-config-generator/

If these don't answer your question, you'll need to be more specific about why the quick web search results aren't what you're looking for.

Beware that AES, GCM, RSA, and ECDH in that cipher suite are likely to be vulnerable to timing side channel attacks if implemented in software!


Can a TLS certificate using ECC secp384r1 as PK algorithm uses RSA for signature If a TLS certificate public-key algorithm is ECC secp384r1 or ECC prime256v1, is it possible to have RSA as a signature algorithm? Or does it use ECDSA for signature? Or can it use any of them (ECDSA or RSA)?

No, RSA cannot be used as a signature algorithm if the certificate has an EC public key in it - you're restricted to ECDSA. You would not be able to verify the signature using the public key after all. The algorithm used must comply with the public key algorithm. However, some keys can be used for different related signature schemes, e.g. RSASSA-PKCS1-v1_5 and RSASSA-PSS (although TLS 1.3 only allows PSS style signatures).

Previously RSA could also be used for session key establishment / authentication using encryption / decryption of the master secret value: the cipher suites starting with RSA_. That use has been deprecated in TLS 1.3, but it is certainly incompatible with EC certificates in versions earlier than TLS 1.2.


Formal Proof of Shamir's Secret Sharing Scheme Security Shamir's Secret Sharing scheme is perfectly secure.

Could you please suggest where I can read a formal proof of Shamir's Secret Sharing scheme being perfectly secure?

Let's recall Shamir's Secret Sharing. We work in a finite field $\mathbb{F}_q$ of cardinal $q$. The secret to share is $s$; we want $n$ shares with a threshold $t$. We suppose that $n < q$ (otherwise, the scheme does not work). We conventionally name $n$ non-zero values of $\mathbb{F}_q$: $x_1$, $x_2$... $x_n$. Exactly how we choose them is unimportant, as long as they are all distinct from zero and from each other, and everybody knows which is which. If $q$ is prime (field $\mathbb{F}_q$ is $\mathbb{Z}_q$, i.e. the integers modulo the prime $q$), then we will traditionally choose $x_i = i \bmod q$ (since $n < q$, this works: none of the $x_i$ is zero, and they are all distinct from each other). By convention, I also define $x_0 = 0$ (this will help in my notations).

To share $s$, we generate a random polynomial $A = \sum_{i=0}^{t-1} a_i X^i$, where:

$a_0 = s$
For all $i = 1$ to $t-1$, $a_i$ is chosen randomly and uniformly in $\mathbb{F}_q$ (notably, each $a_i$ can be zero with probability $1/q$).

By construction, $A(0) = s$. The share of each user $i$ is $v_i = A(x_i)$. The polynomial $A$ has degree "at most $t-1$" (degree of $A$ may be lower than $t-1$ since it is possible that $a_{t-1} = 0$).

To rebuild the secret, $t$ share holders use their respective shares to recompute polynomial $A$, and thus compute $A(0)$, which is the secret Reconstruction uses the Lagrange polynomial. I now suppose that the shares used for reconstructions are $v_1$, $v_2$,... $v_t$ (this simplifies notations, but since the conventional naming of $x_1$, $x_2$... is arbitrary, this assumption that not reduce generality). We define the Lagrange polynomial $L_i$ as the polynomial of degree $t-1$ such that $L_i(x_i) = 1$, but $L_i(x_j) = 0$ for any $j \neq i$ (for $1\leq i,j\leq t$). The Lagrange polynomial is computed as:
$$ L_i = \frac{\prod_{1\leq j\leq t, j\neq i}(X - x_j)}{\prod_{1\leq j\leq t, j\neq i}(x_i - x_j)} $$
Since all the $x_j$ are distinct from each other, the denominator is necessarily non-zero, so the division works; and with $L_i(x_i)$, numerator and denominator end up being identical products, this $L_i(x_i) = 1$.

With Lagrange polynomials, one can find a matching $A$ has:
$$ A = \sum_{i=1}^{t} v_i L_i $$
Since then:
$$ A(x_j) = \sum_{i=1}^{t} v_i L_i(x_j) = v_j $$

That $A$ is the unique solution can be proven with a counting argument: there are exactly $q^t$ possible tuples $(v_1, v_2,\cdots v_t)$ ($t$ values in $\mathbb{F}_q$), and, for each of them, the reconstruction with Lagrange polynomials yields a matching polynomial $A$ of degree at most $t-1$. However, there are only $q^t$ polynomials of degree at most $t-1$. Thus, there cannot be more than one matching polynomial per tuple; otherwise, you'd run out of polynomials at some point.

(It is in fact a more general result that a polynomial of degree at most $t-1$ is uniquely defined by its values over $t$ distinct inputs; this also works in infinite fields. A special case is for $t = 2$, and this really means that by any two distinct points, there passes exactly one line. The general result is proven with more algebra; for finite fields, the counting argument above is a lot simpler.)

Note that secret reconstruction is interested only in the secret $s = A(0)$; having the complete polynomial is only a mean to that, and it is not fully necessary. Indeed, we have:
$$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$
The values $L_i(0)$ depend on which share holders are involved (i.e. the choice of $x_1$, $x_2$... $x_t$), but not the share values ($v_1$, $v_2$... $v_t$). Thus, the $L_i(0)$ can be precomputed. This is especially convenient when doing multiple reconstructions with the same share holders; one typical case is when working with $q = 256$ (the finite field with exactly 256 elements) and applying Shamir's Secret Sharing on byte-per-byte basis on a multi-byte secret value.

The security of the scheme hinges on the following result: for any set of $t$ values in $\mathbb{F}_q$, there is exactly one matching polynomial $A$.

To simplify notations, I now suppose that you have shares $v_1$, $v_2$... $v_{t-1}$. These are $t-1$ shares, i.e. less than the threshold. To prove the absolute security of the scheme, we need to show that these $t-1$ shares yield no information whatsoever on the secret $s$. To do that, we note that:
$$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$
Therefore:
$$ v_t L_t(0) = s - \sum_{i=1}^{t-1} v_i L_i(0) $$
Note also that $L_t(0) \neq 0$:
$$ L_t(0) = \frac{\prod_{1\leq j\leq t-1}(0 - x_j)}{\prod_{1\leq j\leq t-1}(x_i - x_j)} $$
(All the $x_j$ and all the $x_i-x_j$ are non-zero, so the products are non-zero.)

It follows that, given share values $v_1$ to $v_{t-1}$, for any possible value of $s$, there is exactly one value of the missing share $v_t$ that would yield that $s$. Thus, the $t-1$ shares $v_1$ to $v_{t-1}$ yield no information at all about the secret, since all possible values of the secret are still possible and equiprobable at that point.

Note the subtlety here about "equiprobability". The counting argument says that there are exactly $q^{t-1}$ polynomials $A$ of degree at most $t-1$ such that $A(0) = s$, for a given secret $s$. With $t-1$ shares, i.e. knowledge of $t-1$ values $v_i = A(x_i)$, you don't know enough to pinpoint a single polynomial $A$; in fact, you have exactly $q$ matching polynomials, one for every possible value of the secret $s$. This establishes a bijection between the possible values of the secret $s$, and the possible values of the missing share $v_t$ (the formula above makes that bijection explicit). The bijection transports the information: every piece of information, even statistical, that you may know on the secret $s$, can be transformed through the bijection into the same information on the missing share $v_t$, and back. This really means that the $t-1$ shares, by themselves, teach you nothing more. Real-life secret values $s$ are not completely random and uniform, but that's not the point; the point is that without the missing share $v_t$, you don't know more on $s$ than you already knew about it before. This is the sense in which Shamir's Secret Sharing is unconditionally secure.

Some extra notes:

All of this hinges on the idea that the initial sharing polynomial $A$ was chosen really randomly and uniformly. In practice, this is not easily achieved: "true" randomness is elusive. We customarily use pseudorandom generators that expand a given seed, assumed "random", into an arbitrarily long sequence of bytes that are indistinguishable from randomness... as long as attackers have finite computing resources that do not exceed a given value. Moreover, the "seed" itself is obtained from some physical process which is supposed to be unpredictable, but this also assumes limitations on the abilities of attackers at obtaining information from the physical world. Thus, the "unconditional" security of Shamir's scheme is actually conditional on a number of other things.

(Physicists tell us that there is a fundamental uncertainty about the state of any physical system, but not many alleged "random generators" really tap into that. Moreover, from an epistemological point of view, using a quantum-uncertainty-powered RNG is not "stronger" than a cryptographically secure PRNG; you are just putting more trust in Niels Bohr than in Alan Turing.)
The security of the scheme relies on the fact that the polynomial $A$ is single-use. If you use the scheme to do a byte-per-byte sharing of a multibyte secret value, then you MUST generate a new random polynomial $A$ for every byte that is to be split into shares. If you reuse the same $A$ for several bytes, then all the security goes to naught.
A practical implementation may leverage the bijection between share tuples and polynomials, by NOT generating the coefficients $a_i$ randomly; instead, it would generate the first $t-1$ shares randomly and uniformly, then compute shares $v_t$, $v_{t+1}$,... $v_n$ with formulas such as the one described above, where the $L_i(0)$ values can be precomputed (even hardcoded in the implementation source code). The bijection guarantees that this is safe.