What is the signifcance of inside threat in "How to Construct Multicast Cryptosystems ... Secure Against CCA2" In How to Construct Multicast Cryptosystems Provably Secure Against Adaptive Chosen Ciphertext Attack, the paper states under preliminaries:

  We consider the scenario where a single party, called the center,
  sends messages, over insecure channels, to a group U of n parties
  who are denoted members of the group. In such a setting, the center
  often has a special role. Since it is often distributing information
  of its own choice, it is assumed to have control over the group
  membership, i.e., the center is allowed to make decisions about who
  can join the group and whose membership should be revoked. This is in
  line with almost all multicast schemes such as [25, 4, 26, 27, 22, 23,
  24].

  We assume a computationally bounded adversary who is allowed to attack
  the system from both outside and inside the group. The insider’s
  attack is modelled by allowing the adversary to corrupt and gain total
  control of up to t group members where t is a predefined
  threshold. We only consider non-adaptive adversary who chooses what
  members to corrupt before the key generation.

Since the center U authorized the inside attacker, it seems disingenuous to claim that an inside attacker can ultimately access the message.

What is the significance of inside attacker or threat? Why should we care about it in this case?

The "significance of inside attacker or threat" is making the problem non-trivial.

We "should we care about it in this case" because the

protocol apparently claims to provide some sort of revocation.


You are asking two different questions in the title and the body. The answer to both questions is "You can't", but for different reasons.

Finding $n$:

You're asking how to find $n$, given $X=n\cdot G$ and $2\cdot X=2n\cdot G$, where $G$ is the generator of some group $\mathbb{G}$ and $n$ is sampled uniformly.
We first note, that being given $X$ and $2\cdot X$ is equivalent to just being given $X$. We could just compute $2\cdot X$ ourselves. Consequently, finding $n$ is equivalent to solving the discrete logarithm problem in $\mathbb{G}$. As the discrete logarithm problem is assumed to be hard in the used group, that's not going to happen.

Finding $G$:

You are asking how to find the generator $G$ of group $\mathbb{G}$, given $n\cdot G$ and $2n \cdot G$. This is impossible in general. Most groups have more than one generator, the group you propose to use is no exception to that. Given two generators $G,G'$ there by definition exists an $x$ such that $G = x\cdot G'$. Therefore, $n \cdot G = nx \cdot G'=n'\cdot G'$ and $2n \cdot G = 2nx \cdot G'=2n'\cdot G'$ and given no further information about $n$, it is impossible to decide which of the two generators was originally used.


Proof that padded RSA is CPA-secure I'm referring to page 383 of J. Katz and Y. Lindell's Introduction to Modern Cryptography.  The book presents a padded RSA:

${\bf Key Generation:}$ same as Textbook RSA (given security parameter $1^n$, generate public key ($N,e$), secret key ($N,d$), such that $N = pq, ed \equiv 1 \mod{(p-1)(q-1)}$)
${\bf Encryption:}$ given public key ($N,e$), and message $m$ of length $l(n) \leq 2n - 2$, choose random bit string $r$ of length $2n - l(n) - 1$, and interpret the padded message $r||m$ (where $||$ is concatenation) as an element of $(\mathbb{Z}/N\mathbb{Z})^*$.  Output the ciphertext $c := (r||m)^e \mod{N}$.
${\bf Decryption:}$ given secret key ($N,d$), and cipertext $c$, compute $m' := c^d \mod{N}$, and ouput the $l(n)$ low-order bits of $m'$

The book claims that if $l(n) = O(\log{N})$, then the padded cryptosystem is CPA-secure.  Unfortunately, it states that the full proof is beyond the scope of the book.  Where can I find the full proof of the CPA-security of this version of padded RSA?

This result is proven in the following research papers:

Johan Hastad, Mats Naslund.  The Security of all RSA and Discrete Log Bits.  Journal of the ACM, Oct 2003, pp.1--45.
W. Alexi, B. Chor, O. Goldrech, C. Schnorr.  RSA and Rabin functions: Certain parts are as hard as the whole.  SIAM Journal on Computing, vol 17 no 2, pp.194--209.

They show that if you can predict the least significant bit (or the $O(\log \log N)$ least significant bits), then you can break RSA.  See also the citations in that article for similar results.

I can give you a taste for why this might be true, by sketching how to prove a much weaker version: if you have a way to compute the least significant bit of $x$ from the RSA encryption $E(x)$, then I can break RSA.

Let me start with a warmup.  Suppose you have a black box that, given a ciphertext $E(x)$, can answer the yes-or-no question ``is $x$ in the range $[0, N/2)$?''.  Suppose your black box is perfect: it always gives the right answer.  Let me show you how I can use your black box to break RSA.

Notation: Here $E(x)$ denotes the RSA encryption of message $x$, i.e.,
$E(x) = x^e \bmod N$.  Notice that there is no padding and no randomization in my definition of $E(\cdot)$.  Also note that RSA is homomorphic, so $E(2x) = 2^e E(x) \bmod N$.  In other words, given $E(x)$, I can derive $E(2x)$ even without knowing $x$.  I will use the notation $[a,b)$ to represent the set of integers $a,a+1,a+2,\ldots,b-1$.

Now let's solve the warmup problem.  We are given $E(x)$, and we want to find $x$.  Basically, we're going to use binary search.

First, we query your black box with $E(x)$ to learn whether $x$ is in the range $[0,N/2)$ or in the range $[N/2,N)$.  Suppose we learn that $x$ was in the range $[0,N/2)$.
Next, we query your black box with $E(2x)$.  This tells us whether $2x$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[0,N/4)$ or in $[N/4,N/2)$.  Suppose we learn that $x$ is in the range $[N/4,N/2)$.
Next, we query your black box with $E(4x)$.  This tells us whether $4x \bmod N$ is in the range $[0,N/2)$ or in $[N/2,N)$.  Note that $4x \bmod N = 4x-N$ (given what we know about the range $x$ is in).  So, we know whether $4x-N$ is in the range $[0,N/2)$ or in $[N/2,N)$, which in turn tells us whether $x$ is in the range $[N/4,3N/8)$ or in $[3N/8,N/2)$.
Keep going like this, until $x$ is completely known.

This requires $O(\lg N)$ queries to your black box. If your black box always gives the correct answer, then at the end we learn the exact value of $x$.

In other words, if you have a black box like that, then given any RSA ciphertext $E(x)$, I can derive $x$: which is a total break of RSA.  (Conversely, if we assume RSA is secure, then such a black box is impossible to build.)

The warmup above might start to give you some idea of what it might look like to try to prove the stronger result.

For instance, suppose you don't have a black box that answers the question "is $x$ in the range $[0,N/2)$?", but you do have a green box that answers the question "is the least significant bit of $x$ one?".

Well, given a green box, we can build a black box.  Given $E(x)$, we query the green box on $E(2x) = 2^e E(x) \bmod N$; if it answers "yes", then $x$ is in the range $[0,N/2)$, otherwise $x$ is in the range $[N/2,N)$.  So, the green box's answer to $E(2x)$ reveals how the black box should respond to the query $E(x)$.

Therefore, if you have a green box that can compute the least significant bit, you can break RSA (by constructing a black box and applying the binary search method as above).  Conversely, if we think RSA is secure, then there should be no way to build a green box like this.
As another example of a generalization, suppose your black box doesn't always give the right answer; it answers correctly with probability $1/2 + \epsilon$, and incorrectly with probability $1/2 - \epsilon$, for some $\epsilon>0$.  Then we have an instance of a game of 20 questions, where we have only a noisy view of our answer.  It turns out there are algorithmic ways to deal with this noise, though it does take a lot of difficult technical work.  For the details, see the papers mentioned above.


PRNG output with truly random noise I am considering a situation where an adversary does not have access to the $n$-bit output string of a PRNG, but instead receives a noisy version of it, where each bit of the string is flipped with probability $p$. We assume that this noise which causes the bits to flip is truly random.

What can we say concretely about the difficulty of distinguishing this noisy PRNG output from a truly random string? Of course, for $p=0$ we recover the standard scenario for the PRNG and the problem is as hard as solving the underlying computational problem, and for $p=\frac12$ the string is truly random. But what about intermediate values of $p$? Does the distinguishing problem become significantly more difficult even if $p\ll 1$?

Usually what you call "information theoretic hardness" is denoted as statistical indistinguishability. And it is pretty much black and white only: Two distributions are distinguishable or not.

When you ask "how much harder", you already drift into the area of computational indistinguishability. There are plenty of ressources for that keyword, including most books about introduction into cryptography.

So the actual answer to your question would be "If the distribution of p is distinguishable (which is the case for any $p\neq1/2$), and the distribution of the PRNG is distinguishable, then your construction is distinguishable (from a truly random distribution)"


Reusing one-time-pad with random plaintext I understand that by definition one-time-pad keys cannot be reused but I was thinking about the case where it is used to send random data and couldn't find anything on the subject so here is my idea:

Sending y-bits of data using x-bits of random data as a key where y > x.

Step 1: Both parties agree on a x-bits key (With DH or a safe communication).
EDIT: This is only so users can remotely agree on a key, they could also physically share a key.

Step 2: Either agree on a pseudo random data generator before hand or submit an array of random bits to the receiver(The size depends on the algorithm used on Step 4).
EDIT: This data doesn't need to be a secret.

Step 3: I xor the bits generated on Step 2 with the key to get another random array.

Step 4: Use the result of Step 3 on a PRNG or hash function to add more security. Without this step a many-time-pad attack would be possible (Or "easy" at least).

Step 5: xor y with the data to be encrypted to obtain the cipher version.

With this, as long as the algorithm use in Step 4 is random the key can be reused without any worries. The only problem is that one could brute-force it. But since the key doesn't have a size limit all we would need to do is to use a key with a decent size (256 or 512 bits).

Could this be a replacement for AES? If I'm not mistaken only a brute force attack can find the plain-text without the key. Considering that Steps 2 & 4 add enough randomness.

This question is not really well defined. If by "Would this actually work?" you mean "Will this be as good as using a one time pad of length y" then the short answer is No. Anything susceptible to a brute force attack is not as secure as a one time pad.

What are you trying to achieve? If you already agreed on a key of 512 bits and assume this is the difficulty of brute forcing your algorithm, why not use any common symmetrical encryption algorithm such as AES? It seems you are attempting to design a symmetrical encryption algorithm. This is a great exercise to do, and there are many considerations to be made. For an introduction to some of these considerations, but without too much delving into the theory, I highly recommend the book Cryptography Engineering.

To go into specifics, I'll address a few issues:

Step 1:
A one time pad is agreed upon by physically giving 2 or more parties the same key (or by using leveraging quantum key distribution (QKD), but we'll leave this aside for the moment). Any other type of key exchange is only as secure as the key exchange protocol itself.

Step 2:
By random generator, you must mean pseudo-random generator (PRNG), for two reasons:

If two generators generate the same string, they are definitely not random (again, excluding QKD).
If you have a truly random generator, there is no need for this scheme, as you can already generate a one time pad of arbitrary length.

So we have now established that the security of the bits in step 2 is at most that of the pseudo random generator. The word security can have different definitions, and is commonly expressed in number of bits, a system with 128 bits of security is as secure as a 128 bit random key, i.e. to brute force it you would need to do on the order of 2^128 computational steps.

Step 3:
This would not be necessary. If step 2 gave you a truly random array, this would be no more secure. If step 2 gave a pseudo-random array, this would only add a little more security to the randomness by mangling it with x. But as x is reused (because it is shorter) it could be brute forced.

Step 4:
This again is only as secure as the PRNG used (hash functions and AES are not truly random)


I don't understand RSA encryption (specific questions)? So I've been studying RSA for a class and I'm having a hard time understanding how it works.
Why do we choose the value of e such that e is relatively prime to the totient (as opposed to just being relatively prime to n?) How does e being relatively prime ensure that there is only one possible value for d? And are the calculations based on the totient of n just an arbitrary way of encrypting or is there significance to them?

Also, if both e and n are public then how is that secure at all (or is this article wrong about e being public?) I guess I'm confused because if everyone is receiving the same public key then isn't the inverse operation going to be the same for everyone and thus not secure? And since we know that ed mod totient(n) = 1, and we know both n and e can't d easily be calculated?

Thank you for your help and patience :)

Why do we choose the value of e such that e is relatively prime to the totient (as opposed to just being relatively prime to n?)

The final goal of RSA encryption is to have $m = c^d \bmod n$, which is the same as $m = (m^e)^d \bmod n \rightarrow m = m^{ed} \bmod n$, i.e., if you encrypt and then decrypt, you get the same original message. For that last equality to be true, raising to $ed$ needs to be the same as raising to $1$.

When you work with powers modulo some number, you eventually "go back to the start". For example, if you compute $m^1 \bmod n$, $m^2 \bmod n$, $m^3 \bmod n$, the result will eventually go back to $1$ (unless $m\bmod n=0$). The exponent where this happens is called the order of $m$. If $n$ is the product of two distinct primes, then this happens at $\phi(n) = (p-1)(q-1)$ (it happens sooner: at $\lambda(n) = \operatorname{lcm}(p-1, q-1)$, the Carmichael's Function; or sooner depending on $m$; but it doesn't matter for this explanation).

Therefore, we know that $m^{\phi(n)} = 1 \bmod n$ and therefore $m^{\phi(n)+1} = m \bmod n$. And if you add any multiple of $\phi(n)$ to the exponent the result stays the same. In short, in the exponent, you're working modulo $\phi(n)$. And since you need $ed$ to be the same as $1$ in the exponent, then $d$ must be chosen such that $ed \equiv 1 \pmod{\phi(n)}$

  Also, if both e and n are public then how is that secure at all? I guess I'm confused because if everyone is receiving the same public key then isn't the inverse operation going to be the same for everyone and thus not secure?

Each person has a different public key and matching private key. Thus the inverse operation is not going to be the same for everyone, it's the same for each person (each public key holder). The values $e$ and $n$ are indeed public, because the secret value (the private key) is $d$. Each person has their own $e, n, d$ values (tough $e$ is usually the same for everyone, but the others should always be different).


How to know the type of encryption method If I have a program that take a string to give me the ciphertext, nothing stored, using the same keys. The ciphertext is a base64. Can I figure out the type of encryption by the amount of characters in the base64 string?

Is it true that, 17 character string gives:

16 Bytes = MD5,
20 Bytes = SHA-1,
24 Bytes = 3/DES,
32 Bytes = AES?

If that is true, what is the range of bytes for each encryption by specific encrypted text length?

I'm a beginner, so please tell me if there are any other notes or hints...

Ciphertext should be indistinguishable from random. The same goes for hash functions such as MD5 and SHA1. But as you already found out, this is only for the given output domain: the set of all possible ciphertext or hashes. It depends on the algorithm how much variation there is in ouput domains:

for hash functions the output size is part of the definition of the hash function, e.g. 160 bits for SHA-1;
for RSA - an asymmetric cipher primitive - the ciphertext is within 0 and N, the public modulus of the key used;
for DES, triple DES and AES, which are block ciphers, the size of the output is exactly the block size.

Now if we focus on the block ciphers: block ciphers are used in a mode of operation. Without the mode of operation the output of AES is not secure; in other words, AES needs a mode of operation to be used as generic, secure cipher.

It depends on the mode of operation what the size of the ciphertext will be. For instance for CTR mode the output is the same size as the plaintext - it doesn't need to be padded. For CBC some kind of padding is required and the output will always be a multiple of the block size.

So where does that leave us? Well, basically we cannot tell all that much from the ciphertext itself. We can tell that ciphertext is certainly not the result of some kind of ciphers.

For instance a 6 byte ciphertext cannot be the output of a cryptographic hash function and is not the output of 3DES or AES in CBC mode. This means that the analyst can skip these algorithms when trying to find the right one from a particular set.

On the other hand the same 6 byte ciphertext can be the result of AES or triple DES in CTR mode. Which one cannot be determined by the ciphertext alone.

So the encryption mode can often not be determined that way. Note that the encryption method is generally considered known by the attacker. It is not considered a secret by the parties using the cryptography.

This is known as Kerckhoffs principle. This is basically because the method of cryptography is only one static known fact, part of the protocol description. Hiding the cipher only makes the life of an attacker slightly harder; relying on secret cipher algorithms has resulted in spectacular failures in the past.

Note that for your question base 64 encoding really doesn't matter. You simply reverse the encoding before analyzing the ciphertext.


Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators? Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows:

Let $s \in \{0,1\}^n$ be the input seed and denote $s =s_0$.
For every $i = 1,\ldots,p(n)$, compute $(s_i,\sigma_i) = G_1(s_{i-1})$.
Output $(\sigma_1,\ldots,\sigma_{p(n)})$.

Now, we know that if $G_1$ is a pseudorandom generator, then $G$ is also a pseudorandom generator - i.e. in order for the construction of $G$ to yield a pseudorandom generator it is sufficient for $G_1$ to be a pseudorandom generator.

My question is as follows: Is it also necessary that $G_1$ is a pseudo-random generator? In other words, is it true that $G$ is a pseudorandom generator if and only if $G_1$ is a pseudorandom generator - i.e. is it possible to prove that if $G_1$ is not a pseudorandom generator, then $G$ is not a pseudorandom generator?

More generally, if the above is not true, given $G_1$, is there any way to construct a deterministic poly-time algorithm $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ such that $G$ is a pseudorandom generator if and only if $G_1$ is a pseudorandom generator?

Or, if this is not possible, given a permutation $f:\{0,1\}^n \rightarrow \{0,1\}^n$, is it possible to construct a deterministic polynomial time algorithm $G:\{0,1\}^n \rightarrow \{0,1\}^{2n}$ such that $G$ is a pseudorandom generator if and only if $f$ is a one-way permutation?

For context: I am working through each step of the classical construction of pseudorandom functions from one-way functions:

OWF $\rightarrow$ hard-core predicate $\rightarrow$ $n+1$ PRG $\rightarrow$ $2n$ PRG $\rightarrow$ PRF

we know that if $f$ is a one-way permutation, then this construction yields a pseudorandom function. I would like to understand whether it is necessary that $f$ is a one-way function for this construction to work - i.e. if I am given an inversion adversary for $f$, can I construct an adversary for the pseudorandom function given by the above construction? More generally, given a permutation $f$, I would like to construct a function which is pseudorandom, if and only if $f$ is a one-way permutation, and I was curious whether the typical construction of pseudorandom functions has this property.

It is not necessary, that $G_1$ is a PRG.

Let $G_2: \{0,1\}^{n-1} \rightarrow \{0,1\}^n$ be a PRG, define $G_1: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$ as
\begin{align*}
G_1(s_1||\ldots||s_n) := 1||G_2(s_2||\ldots||s_n).
\end{align*}
and consider the distinguisher $\mathcal{D}_1$, which returns the first bit $w_1$, when given the $n+1$ bit string $w := w_1||\ldots||w_{n+1}$ as input.

For $s_1 \leftarrow \{0,1\}^n$ and $r_1 \leftarrow \{0,1\}^{n+1}$ we have
\begin{align*}
\Big|\text{Pr}[\mathcal{D}_1(G_1(s_1))=1] - \text{Pr}[\mathcal{D}_1(r_1)=1]\Big| = \Big|1 - \frac{1}{2}\Big| = \frac{1}{2} > \mathsf{negl}(n),
\end{align*}
which implies that $G_1$ is not a PRG.

Nevertheless, we can still prove, that $G$ is a PRG, by using a slight modification of Katz' and Lindell's proof for theorem 6.20 in "Introduction to Modern Cryptography". (I assume you are familiar with it, since you are using the exact same notation.)

We construct a distinguisher $\mathcal{D}_2$ for $G_2$ using another distinguisher $\mathcal{D}$ for $G$, with
\begin{align*}
\Big|\text{Pr}[\mathcal{D}(G(s))=1] - \text{Pr}[\mathcal{D}(r)=1]\Big| =: \epsilon(n).
\end{align*}

Let $\mathcal{D}_2$ behave as follows, when given a $w := w_1 || \ldots || w_n \in \{0,1\}^n$ as input.

$i \leftarrow \{0, \ldots, p(n) - 1\}$
$r \leftarrow \{0,1\}^i$
$p := G(1||w)$
Construct a bit-string $w'$ as the concatenation of $r$, $w_{n}$ and the first $p(n) - i - 1$ bits of $p$.
Output $\mathcal{D}(w')$

You can easiliy verifiy the following two statements:

If $i = 0$ and $w = G_2(s_2)$ for $s_2 \in \{0,1\}^{n-1}$, then $w' = G(s)$ for $s = b||s_2$ and $b \in \{0,1\}$.
If $i = p(n) -1$ and $w = r_2 \leftarrow \{0,1\}^n$, then
$w' \leftarrow \{0,1\}^{p(n)}$.

Using the same argument as Katz and Lindell, we obtain
\begin{align*}
\mathsf{negl}(n) \geq \frac{\epsilon(n)}{p(n)} && \Longrightarrow && \mathsf{negl}(n) \geq \epsilon(n),
\end{align*}
which means, that $G$ is a PRG.

Similar arguments apply to your other two questions.


Finite Automata and Application to Cryptography The automated inverse theory in cryptography, points to autonomous finite automata, which is relative to the canonical form for one-key cryptosystems based on finite automata, the public key encryption based on finite automata for one-key cipher can be executed by finite automata.
A finite automaton is considered as a natural model for ciphers. The method of converting Ra Rb has been introduced to deal with the structural problem of such automata; then, the public key encryption based on finite automata and a focal type for one key cipher that can be executed by finite automates with limited error propagation and without spreading data is provided.

What is the application of Finite Automata in cryptography?

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

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


Find the generators of multiplicative group of units efficiently? Say you're give some prime numbers $p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1$ (which is assumed to be also prime) and a list of numbers $L$ and you're asked to find the generators of the multiplicative group of units of $Z_p$.

What would be an efficient way to do so?

This question comes from a cryptography course so that the prime numbers are really big and also the list of numbers is formed by big numbers so that I'm having trouble to apply this kind of method.

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $F_g$, starting from $1$, $p-1$ times, cycles back to $1$.

By definition, $g$ is a generator of $\mathbb Z_p^*$ if and only if that cycling does not occur before these $p-1$ iterations. The smallest $k>0$ where the cycling occurs divides $p-1$ (that $k$ is the order of $g$). Proof sketch: if that $k$ did not divide $p-1$, $k'=(p-1)\bmod k$ would be a smaller $k'>0$ for which the cycling occurs.

It follows that we can test if some $g$ not divisible by $p$ is a generator of $\mathbb Z_p^*$ by checking if $g^k\bmod p\ne1$, with $k=(p-1)/q$ for $q$ each of the distinct prime factors of $p-1$.

Here, for $g$ each of the integers in list $L$, we check if $g\bmod p\ne0$, and $g^{(p-1)/2}\bmod p\ne1$, and $g^{(p-1)/p_1}\bmod p\ne1$, and $g^{(p-1)/p_2}\bmod p\ne1$, and $g^{(p-1)/p_3}\bmod p\ne1$. In the affirmative, and only then, $g$ is a generator of $\mathbb Z_p^*$.

Additions:

Computing $g^k\bmod p$ is feasible with a modest computer, and common, for integers of many thousands of bits: $2\log_2(k)$ modular multiplications are enough to compute $g^k\bmod p$; see modular exponentiation.
If the list $L$ was not a given, we could try $g$ at random (or small primes by increasing orders, which is slightly more efficient than trying small integers by increasing order). If all the primes dividing $(p-1)/2$ are large (which is the case here), nearly 50% of candidates will work, thus a search won't be too long.
Often, we want a generator of a subgroup of order one of the large primes dividing $p-1$, say $p_3$; we can get that as $g'=g^{(p-1)/p_3}\bmod p$.


What are these twist attacks with cost $2^{58.4}$ on NIST P-224 curve, and when do they apply? This page on Twist security mentions a combined attack and a twist rho attack, applicable in particular to NIST P-224 curve with cost $2^{58.4}$ something, with no mention precise definition of protocols concerned by the attack(s), beyond:

  Some of the ECDLP security requirements for the twist are overkill for DH on the original curve: DH does not actually reveal nQ to Eve, so there is no obvious way for Eve to apply (e.g.) an additive transfer. There are, however, other ECC protocols that make full use of both the original curve and its twist, and twist security is important for these protocols.  See, e.g., 1986 Kaliski, 1988 Kaliski, and 2001 Boyd–Montague–Nguyen.

What are theses attacks (in the simplest meaningful terms possible please, including some introduction to the twist)? To what class of protocols (perhaps: signature, key establishment..) and operational setup (number/nature of queries to signer/server..) do they apply?

Note: the present question is closely related to (and inspired by) this more technical one.

I don't consider the following a complete answer, but it is a start, and best I can do with  my very limited knowledge. I hope someone could fix it or improve it.

These type of attacks are only possible against specific implementation of higher level protocols.
I will start by describing an invalid-curve attack against a specific ECDH based protocol.

Simple Pairing protocol:
Entity A wants to establish an encrypted and authenticated channel with Entity B, and both support the same pairing protocol, based on ECDH using P-224

Entity A sends its own ECC public key ($pub_A$) to B
Entity B sends its own ECC public key ($pub_B$) to A
Both devices computes ECDH, thus generating a shared point ($SP = priv_A*pub_B = priv_B*pub_A$)
Individually they run this shared point through a KDF, generating $K_{ENC}$ and $K_{MAC}$
Entity A starts communicating to B using AES CTR to encrypt the communication and AES CMAC to authenticate the ciphertext.

Let's now suppose B is malicious and wants to recover A's private key.

Conditions for the attack to succeed:

A doesnt't check if the B's public key, or computed shared point, actually lie on P-224.
Public keys are exchanged with both $x$ and $y$ coordinates and both are used in the scalar multiplication algorithm.
The scalar multiplication algorihtm doesn't use the value of $b$ in the computation (this is very common for short Weierstrass curves)

B generates elliptic curves $EC'$ over the same field $F_p$ of P-224 with the same $a$ parameter but different value for the $b$ parameter. B computes the order of those curves, and factor it, looking for small primes divisors.
Let's suppose he finds a suitable curve with order of form $17*h$ where $h$ is a composite not divisible by $17$. This means that there is a subgroup of $EC'$ with order $17$.
B finds a point of this small subgroup, calls it $pub_B$ (his public key) and sends it to A.

A will compute $SP = priv_A*pub_B$, derive $K_{ENC}$ and $K_{MAC}$ and starts the secured communication.
Note that A will in fact compute the scalar multiplication over $EC'$ and therefore $SP$ has only $17$ possible values.
In this way he finds the value of $priv_A\mod17$

He repeats the attack with other small groups having order coprime to each other (he can use several $EC'$), and then uses the $CRT$ to recover $priv_A$.

Let's now discuss the case where the scalar multiplication doesn't use the $y$ coordinate.
Premise: Hereafter I will assume that a x-coordinate only ladder can be used on the original curve and on the twist. The answer to this question explains how a twist curve can be used for short Weierstrass curves.

Now the job of B is much more complicated because he can't easily provide to A a public key on a generic $EC'$ since the $y$ coordinate is key for this, as without the $y$ A will compute the scalar multiplication on $EC$ and not on $EC'$. But, since A algorithm will work for the twist also (as in our premise) then B can use a non trivial quadratic twist of $EC$.

There is one set of isomorphic curves, each curve within the set is defined through a $c$ that is not a quadratic residue in $F_P$, by $y^2 = x^3 + c^2ax + c^3b$.
$a$ and $b$ are the original curve's parameter, and this set is the $twist$.
These curves have order different from the order of $EC$, namely $p+1+t$ where $t$ is the trace of $EC$. If the order factors in many (relative) small primes then it opens the door to an invalid curve attack, where B sends public keys lying on small subgroups of the twist.

For P-224 the order of the twist factors to:
$$3^2 * 11 * 47 * 3015283 * 40375823 * 267983539294927 *
177594041488131583478651368420021457$$
So he can use the small subgroups of orders $3,11,47,3015283,40375823,267983539294927$.
He needs to bruteforce on $K_{MAC}$ for each subgroup so this attack requires about $2^{log(267983539294927)} = 2^{47.93}$ operations to get by CRT the value of: $$priv_A \mod(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927) $$
Now B can computes the actual value of $priv_A$ by Pollard's kangaroo. He uses the information he just got, limiting the search to $n/(3 * 11 * 47 * 3015283 * 40375823 * 267983539294927)$ which is about $2^{105.32}$. Due to Pollard's kangaroo complexity it requires about $2^{105.32/2}=2^{59.34}$ operations, which dominates the complexity analysis.

Note this number is close but not equal to Dr. Bernstein's number of $2^{58.4}$ operations.
In this page he shows that he calculates the complexity of the combined attack as $log(\pi/4*l)/log(4)$ where $l$ is the largest prime in the divisors of the order (that is exacly our $n/(3*11*47*3015283*40375823*267983539294927)$, which approximate to the $2^{58.4}$ value of the question. I don't know where his formula come from, most likely from a much better knowledge of Pollard's Kangaroo running time.

Edit1: understood calculation from bernestein, modified the premise since my question was answered.


Why is Rabin encryption equivalent to factoring? I don't understand the proof of equivalence I've read everywhere (e.g., in Rabin's paper or on Wikipedia).

Here's my objection: let's say you have a Rabin decryption oracle that takes n and c and returns one of the square roots of c mod n. It always returns the same square root for a given n and c, but the choice of output root is otherwise random over combinations of n and c. In this case, the oracle would decrypt the ciphertext somewhere between 25 and 50% of the time (depending on the number of roots of the ciphertext), but it's unclear to me how you could factor n on this basis.

I agree that an oracle that pops out both s and r allows one to easily factor n, but it's not necessary to do that to break Rabin at least 25% of the time.

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations.

More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same applies modulo q, and makes four combinations. What you look for is a pair of values (a,b) such that both are square roots of the same value (i.e. a2 = b2 mod n), a = b mod p, and a = -b mod q (or vice versa). If you have such a pair, then c = a-b mod n will be an integer that is equal to 0 modulo p but not modulo q; in other terms, c will be a multiple of p but not of q, so a simple GCD computation between c and n will reveal p.

Suppose that you have a box that can compute square roots modulo n. Then, the attack works thus: generate a random a modulo n; compute a2 mod n and send it to the box. The box will return a square root b (one of the four possible square roots). If the box returns a itself, or n-a, then this round fails, and the attacker must start again with another random a. This happens 50% of the time. But if the box returns one of the two other square roots of a2 then the GCD explained above reveals a factor of n.

There is no square root choosing strategy from the box that can prevent this attack from working, because the attacker chooses a completely at random.

The above does NOT show that "Rabin encryption is equivalent to factoring". What it shows is that the general ability to extract square roots modulo n is equivalent to knowing the factors of n. The term "general" here means that the ability works for a substantial proportion of values which are squares modulo n. Anybody can compute square roots for some values (e.g. if we work modulo n and you challenge me with the value "9" then I can answer that a square root of that value modulo n is "3", and I can do that even without knowing the factors of n); but if you can do that for a non-negligible fraction of all integers modulo n then you can factor n.

There is no actual standard that specifies Rabin encryption, but if there was, then that standard would probably entail some sort of padding, because, as explained above, a square has four square roots. The decryption engine must choose which one is the right one. A simple strategy for that is to add some redundant padding: when encrypting message m, convert it to an integer x by appending h(m) to m (for some hash function h) and then interpreting the whole as an integer. Then, upon decryption, recompute the hash to know whether you got the correct square root, and not one of the three others. (The padding would also have to include some randomness to avoid brute force on the plaintext.)

With such a padding, a box that can decrypt things may return the decrypted value, OR it could say "this does not decrypt to anything that is properly padded". Then the attack explained above no longer works; the attacker will have to find a value a such that another square root b (which is neither a or -a) ends with a proper padding, otherwise the decryption oracle won't return it. Depending on how the padding is exactly defined, then the probability to hit such a value could be too small to actually happen.

Therefore, while extracting square roots modulo n is equivalent to factoring n, it cannot be said, in all generality, that practical Rabin encryption is equivalent to factoring. This depends on the details of padding and usage, details which are not, currently, defined.


Can I make fixed-length ciphertext with AES-256-GCM? I have a question about AES-256-GCM encryption.

Can I make a fixed-length encryption output?

In my understanding, I cannot make a fixed-length ciphertext. To me, the fixed-length output is much more secure so that no one can guess the input length. If we cannot make a fixed-length output, can someone explain why this is still secure enough?

Can I make a fixed-length encryption output?

Sure you can - on encryption, you can first pad out the plaintext to a fixed length (and then perform the GCM encryption).  On decryption, you perform the GCM decryption, and then depad.

Obviously, the padding will need to contain a 'amount of padding I added' field (so that the depadding operation can remove the correct amount) - there are several obvious ways to accomplish that.  Someone looking at the ciphertext cannot determine anything about the contents, including the pad length.

Because GCM does integrity checking (that is, if someone modifies the ciphertext, GCM will detect it), you don't have to worry about padding oracle attacks.


S-box and Side Channel Attacks S-boxes with non-linearity greater than 112 are considered prone to side channel attacks.
If a non-linear S- box with non- linearity greater than 112 (excluding bent functions with non-linearity of 120) is implemented through lookup tables, then the amount of power consumption should be similar to 112 S-box. In other words, side channel attacks shouldn't be able to distinguish between the two S-boxes. The question is, if an S-box with non-linearity greater than 112, implemented through look ups is safe or not?

I think you have mis-understanding and misconception of how nonlinearity of sbox influences on side channel.

The 112 is nonlinear value of good properties sbox (such as AES) , I have not seen sbox with greater value in my literature.

I will go beyond you question, to evaluate s-box against side channel attack such as differential power analysis (DPA), other parameters are taken : Transparency order (TO) (the lower the TO, provides higher resistance to DPA) and signal to noise ratio (SNR) ( the lower the SNR ,provides  higher resistance to DPA).

Prouff showed in his paper (DPA Attacks and S-Boxes), the highly nonlinear s-box are prone to DPA and   the construction of highly-nonlinear S-boxes with small transparency order (close to 0) is an open problem.

I recommend you download the SET tool from this link and start to play it with different constructions of Sbox to gain more knowledge


File integrity checking: why use a hash tree instead of a hash list? File sharing systems sometimes use the likes of a Tiger Tree Hash to check the integrity of a file as it is downloaded.

Hash trees in general are useful to check integrity of the tree leaves without downloading the full tree, instead needing only the root and tree branch that contains the interesting leaf (plus necessary stubs in the branch).

My question is: why use a tree at all for file integrity checking when what one presumably wants is to download the full file? A plain hash list (a hash per file block + a hash of the list) would have been trivial to implement and manage, and only be marginally bigger than the tree. The list's hash still works as well as the root hash in the tree case.

In fact I only know one file sharing client that allows one to select parts of a file to be downloaded, so the whole use case looks atypical.

So, is this a case of early, marginal, mostly unused optimization? Or am I missing something?

Looks like the question itself needs some correction. My characterization of what happens in "file sharing" was too simplistic, and adding detail to it explains the matter.

eDonkey/eMule in the 00's did use Tiger Tree Hashes, which are a kind of Merkle trees.

But by then, looks like BitTorrent's torrent files only contained a simple list of hashes corresponding to the blocks of the torrented file. The number of blocks was fixed, but their size could be adjusted. This made for big torrent files, which stressed web servers; but minimizing torrent file size forced big file blocks in the torrent, which was also bad.

So around 2009, BEP 30 introduced a way to reduce the size of the torrent files AND to reduce the size of the hashed file blocks: the new style of torrent file contains only the root of a Merkle tree (so its size is minimal, relieving the web server), and the tree is created internally by seeders. The pieces of the tree needed for each block transmission are sent in-band, making it self-contained and verifiable with the root.

The key point is that the tree is not transmitted by itself, but generated by seeders and transmitted piecewise as needed. This piecewise transmission probably generates a lot of redundancy, but this redundancy is in the P2P protocol, so this inefficiency is much less important than the relief to the web server.

A hash list as the one I described in the question might be workable as a substitute of the tree, but would cause even greater inefficiency in the protocol, and would need storage of the whole list of hashes (linear to the size of the torrented file) even if the client is not interested in some blocks.


ECIES public key distribution I am trying to implement ECIES (using BouncyCastle and FlexiProvider) across mobile app and server communication whereby the mobile app will encrypt a data and server will decrypt the same. Now how should I pass the public key of ECIES to the mobile app for encryption.

I see three options for you, each with strengths and weaknesses.

Use a PKI with some sort of trusted signing authority and validate that the certificate is signed by a trusted signing authority and that it has some identifier in it that should be present for your app to trust. For example, the certificate could have a Subject field embedded within it that has a value of my-really-cool-app.com. If presented with a certificate signed by the trusted authority with the correct Subject field, you trust the certificate and continue with the connection. This would happen every time you connect.
Use trust on first use. This means, the first time you connect, you accept whatever certificate you are given. On subsequent connections, you only accept connections that present the same certificate. If a new cert is given, you error out or something. This is similar to how SSH is used most often. In SSH the user is presented with the server's public key certificate fingerprint, but my guess is no one checks that and just trusts it the first time. If it ever changes SSH complains.
You ship your app with the desired public key certificate (or fingerprint) within it. On making a connection, if the certificate has changed, don't continue the connection. This is pinning.


Making a one-way function harder to reverse Let's suppose that for a crypto protocol a 32-byte-to-32-byte one-way function is needed. Proposals are:

$\textrm{sha256}(x)$
$\textrm{hmac}(\textrm{sha256}, x, x)$
$\textrm{hmac}(\textrm{sha256}, x, f(x))$, where $f$ is a 32-byte-to-32-byte function whose inverse is easy to compute, e.g. bytewise reverse (whose inverse is itself).

Are #2 and #3 any harder to reverse than #1 (plain SHA-256)? Is there an even harder to reverse proposal?

I understand that if the attacker has access to a generic method with which it's possible to reverse any 32-byte-to-32-byte function, then #1, #2 and #3 are equally easy to reverse, and thus they are equally secure.

Let's suppose that in the future someone finds a fast way to compute the inverse of SHA-256 on 32-byte inputs, but there is no other fast generic reversing method is available. (The attacker is highly motivated to reverse SHA-256, because doing so can possibly break many crypto protocols.) This doesn't help finding the inverse of #2 or #3, because they have an outer SHA-256 call whose input is 64 bytes.

(2) and (3) are expected to cost slightly more to invert than (1), no matter what the distribution on $x$ might be, because the only known preimage search algorithms treat them as black boxes to be evaluated forward and search more or less by guessing and checking (optimized with rainbow tables or quantum computers).

The expected cost of any such algorithm is the cost of evaluating the function, times the expected number of times you must evaluate it.  The cost of evaluating (2) and (3) is the same, but they both cost about twice what (1) costs.  You can make things much costlier by using a modern password hash such as scrypt or argon2.

However, if the only possible values of $x$ are the strings red and blue with equal probability, then the difference in cost is negligible.  The adversary has a 50-50 chance of getting it right in one try.

So a much more important question is: How are you using this in your application?  How does it fit into the protocol?  What security properties do you hope to achieve by it?  What costs do you hope to impose on an adversary trying to break the system?

If the distribution on $x$ has >=128 bits of entropy, or if there are actually two inputs of which one is a secret with >=128-bit entropy and the other maybe has low entropy, there's no reason to try to raise the costs of evaluating the function by iterating SHA-256 or using scrypt or argon2.  On the other hand, if you're storing password hashes, then you should absolutely use something designed for password hashes that raises the area*time cost and thwarts attackers with high levels of parallelism.


Distinguishing between two probabilities and the uniform probability Say I have a polynomial adversary $A$ that can distinguish with a non-negligible adventage between $x$ generated from a probability $X$ and $y$ generated from a probability $Y$.

Obviously, this implies that it is possible to either efficiently distinguish between $X$ and the uniform distribution, or between $Y$ and the uniform distribution (or both).

How can this be proven?

Can $A$ be directly used to construct another adversary that distinguishes between $X$ and uniform (or $Y$ and uniform) ?

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


Is bcrypt better than GnuPG's iterated+salted hashing method? GnuPG has slow hash built-in in form of iterated+salted S2K.

Does it have disadvantages in comparison with bcrypt or scrypt? Is GnuPG's slow hash method easily automated in GPUs?

OpenPGP's "Iterated and Salted S2K" is just a single hash instance over a very long input, which consists in the repeated concatenation of the salt and the password. This is extremely GPU-friendly, especially when using a hash function which is built over 32-bit elementary operations (this category includes MD5, SHA-1, SHA-256 and RIPEMD-160; GPU are not as good at dealing with 64-bit operations, e.g. SHA-512). Consequently, an attacker will get a good boost out of GPU when trying to attack a password which has been processed with that key derivation function.

Note that this puts S2K in the same category than PBKDF2: although their internal structures differ quite a lot, they have similar usage patterns on the hardware. Comparatively, bcrypt and scrypt need much more fast access RAM, which puts GPU at a disadvantage. Bcrypt still fits in a few kilobytes of RAM, hence is still susceptible to optimizations through FPGA; scrypt looks even better, but it is shiny because it is new, which is not a good thing in cryptosystems (like good wine, good crypto must wait a few years for optimal quality; see this answer for a more thorough discussion).

Let me stress out that, in practical terms, OpenPGP's S2K (or, for that matter, PBKDF2) very rarely turns out to be the weakest part of a given system. For all its shortcomings, S2K is much better than a simple non iterated hash-with-salt, and a fortiori an unsalted hash invocation, as is unfortunately still commonly encountered in deployed applications.


Correlation of linear trail When I am studying about linear cryptanalysis, I have a question about correlation of linear trail.

Let $U=(u_0, u_1 , ...,u_n)$ be a linear trail

Then we can compute a correlaton of linear trail $U$ such that $C_{U}=\prod_{i}C^{r_i}_{u_{i}u_{i-1}} $

where $C^{r_i}_{u_{i}u_{i-1}}$ is a correlation of $r_i $th round.

My question is why we compute correlation of linear trail by producting round correlation?

Is there any mathematical proof of this point?

Thank you.

This is due to the modelling approach called Markov Ciphers, by Jim Massey (I think).

Basically the hypothesis is that round by round independence applies and correlations can be concatenated by using conditional probabilities and multiplying the probabilities. Since you must have the previous and current round correlations to build up a trail step by step, you apply conditional probability.

Daemen and Rijmen (designers of AES) state:

The Markov cipher theory [18] has inspired many research on iterative block ciphers, including ours. It can be considered as the first approach to design block ciphers resistant against differential cryptanalysis. A Markov cipher is an (iterative) cipher for which the average difference propagation probability over one round is independent of the round’s text input. For such ciphers, the assumption of independent round keys allows to compute the average DP of a characteristic as the product of the probabilities of the individual round. Here the average is taken over all the round keys, considered as independent variables. The average DP of a differential can be computed —in principle— as the sum of the probabilities of all characteristics with input difference a in the first round, and output difference b in the last round. Estimating the average probability of a differential to be equal to the fixedkey probability for almost all keys, is called making the hypothesis of stochastic equivalence. After the publication of linear cryptanalysis, Markov cipher theory has been extended to the resistance against linear cryptanalysis (e.g. see [26, 30]), leading to analogous conclusions for the LP of linear approximations (hulls) over the cipher. In [27] Markov theory was used to show that the average DP values in a Markov cipher employing differentially 2-uniform mappings converges exponentially fast to a flat distribution with high probability.

The quote above is from  their paper https://eprint.iacr.org/2005/212.pdf


Difference between RC2, RC4, RC5 and RC6 Can anyone point out the core differences between RC variations?

RC2
RC2 is a 64-bit source-heavy unbalanced Feistel cipher with an 8 to 1024-bit key size, in steps of 8. The default key size is 64 bits. It was designed in 1987. It has a heterogenous round structure with a total of 18 rounds (16 "MIXING" rounds and 2 "MASHING" rounds). It is a complex cipher using secret indices to select key material. It performs bitwise rotations, AND, NOT, and XOR, as well as modular addition. The key schedule is reminiscent of MD2's internal operations. It is vulnerable to a related-key attack given 234 known plaintexts. It is defined in RFC 2268, though it was originally leaked to a mailing list through reverse engineering software that used it in 1996.
There is never a reason to use RC2. It is an extremely old cipher sponsored by Lotus for their Lotus Notes software and designed by RSA Security, Inc. with input from the NSA. It was meant to be an export-ready drop-in replacement for DES but was created long before we had a good understanding of block cipher design. It is relatively devoid of analysis and could easily suffer from severe security vulnerabilities that have not been discovered. It's an interesting cipher for sure, but not a useful one.
RC4
RC4 is a stream cipher with a 40 to 2048-bit key written in 1987 with a maximum theoretical strength of log2(256!) ≈ 1684 bits. It generates a keystream from a state array composed of a 256-byte permutation by swapping values based on a secret state-dependent index and an incrementing index. The first portion of the RC4 keystream shows a significant bias, though the bias shrinks as more keystream is generated. For that reason, many implementations drop the first few hundred (or even thousand) bytes. Other biases and serious problems such as vulnerabilities in how it uses a nonce exist that can make it difficult to use securely (in particular, the nonce is concatenated with the key, which is an issue as the cipher is vulnerable to related key attacks that enable key recovery). Of the ciphers you mentioned, RC4 is the only stream cipher. Its design was leaked to a mailing list in 1994.
If you ever find yourself needing to use RC4, make sure you combine the key and nonce by putting them through a cryptographic hash function first, rather than concatenating them as traditionally done. Ensure you drop the initial keystream (at least 768 bytes, but ideally up to 3072), and do not use it in applications where the same plaintext may be encrypted an unlimited number of times with different keys. Otherwise, small biases may allow recovery of the plaintext without needing the key.
RC5
RC5 is a block cipher using a 1 to 255 round (12 originally suggested) Feistel-like network with 32, 64, or 128-bit blocks published in 1994. The key size is 0 to 2040 bits. One thing that makes RC5 unique is its use of data-dependent rotations, a feature that theoretically improves resistance to cryptanalysis but which, in practice, often makes the cipher harder to analyze and can leave weaknesses that are only found later. Additional operations involved are modular addition and bitwise XOR. The cipher's key schedule uses magic constants derived from the fractional part of $\phi$ (the golden ratio) and $e$ (the base of the natural logarithm, aka Euler's number). 12-round RC5 with 64-bit blocks is vulnerable to a differential attack using 244 chosen plaintexts. Using 18 to 20 rounds should protect against this. RC5 was published in a research paper from MIT and its specification is described in RFC 2040.
There is no reason to use RC5. RC6 is an improved version which is also better researched. If you do need to use it, use 18 or 20 rounds. Do not use 12 as was initially suggested by the authors.
RC6
RC6 is a 20-round Feistel block cipher based off of RC5, with tweaks done to make it acceptable for the AES competition (including using a fixed block size of 128 bits and supporting 128, 192, and 256-bit keys). It can be viewed as two interweaving parallel instances of a modified version of RC5. RC6 ultimately lost to Rijndael, but did make it to the top 5 (along with Twofish, Serpent, Rijndael, and MARS). RC6 uses the same basic operations as RC5, but also includes multiplication to improve diffusion characteristics of the rotation operation. It is described in the paper that announced it.
Given that it survived the first round in the AES competition, it is thought to be quite secure. No major issues have been found in it. If you find yourself wondering if you should choose RC6 though, the answer is probably no. Stick with the winner of the competition, Rijndael (now referred to as AES).

All of these were created or co-created by Ron Rivest, one of the creators of RSA and the creator of MD2, MD4, MD5, and co-creator of MD6. RC is said to stand for "Ron's Code" or "Rivest cipher". Interestingly, RC1 was never published, and RC3 was broken at RSA Security during development.
In summary:

RC2 is an ancient block cipher that should not be used for anything.

RC4 is an ancient stream cipher that should not be used for anything, yet still is.

RC5 is a slightly newer block cipher and is secure with sufficient rounds.

RC6 is an improvement upon RC5, increasing its security. It lost the AES competition.

RC4 and RC6 are by far the most well-researched. The former is because of its ubiquitous use despite its weaknesses, and the latter because it was part of a competition that involved extensive analysis. However, you still shouldn't use any of these ciphers as there are far better alternatives.


What do the signature security abbreviations like EUF-CMA mean? From time to time, one stumbles across formal security definitions. This includes security definitions for signature schemes.

The most common ones are the *UF-* ones, advertising security against specific classes of attackers.
Now these notions may not be that well-understood by many people so I ask hereby for a canonical answer, that explains what the following security notions mean. A (simple) description of the formal attack scenario is preferred.

Please don't restrict the answer to "you can chose this and if you can break it with this it isn't EUF-CMA". Please at least outline the formal attack (like f.ex. generate a new signature).

The following list is in order of strength for the same suffix (x)or prefix:

UUF-KMA
SUF-KMA
EUF-KMA
UUF-CMA
SUF-CMA
EUF-CMA

(Notation. Sets are represented using the calligraphic font and algorithms using the straight font. Throughout, $\Sigma:=(\mathsf{K},\mathsf{S},\mathsf{V})$ denotes a signature scheme on a key-space $\mathcal{K}$, message-space $\mathcal{M}$ and signature-space $\mathcal{S}$.
Since only a single key-pair is involved in the discussion, to avoid cluttering, let's drop the security parameter, public key and secret key when invoking $\mathsf{S}$; similarly, let's drop the security parameter and public key while invoking $\mathsf{V}$. That is, we regard:
  $\mathsf{S}:\mathcal{M}\rightarrow\mathcal{S}$ and
  $\mathsf{V}:\mathcal{S}\times\mathcal{M}\rightarrow\{0,1\}$.)

As in the case of encryption schemes, security is modelled for a signature scheme $\Sigma$ using a game between a challenger and an adversary $\mathsf{A}$ (a polynomial-time probabilistic machine). The game models a possible scenario where $\mathsf{A}$ tries to break $\Sigma$ using an attack when the challenger is using the scheme $\Sigma$. $\Sigma$ is said to be secure in the  $\mathtt{break}$-$\mathtt{attack}$-model (i.e., $\mathtt{break}$-$\mathtt{attack}$-secure) if it is "difficult for any $\mathsf{A}$'' to $\mathtt{break}$ $\Sigma$ under $\mathtt{attack}$ (the precise definition is given in the end). Hence, for the case of signature schemes $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}---it is possible to consider any combination of these.

For ease of exposition, let's start with the description of the "weakest" model, called universal forgery  (UF) under key-only attack (KOA).

  1: UF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\in\mathcal{M}$

b. Receive as response (to the challenge) a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

That is, in the UF-KOA model, the adversary has forged on a message chosen by the challenger (i.e., a universal forgery) given just the public key (i.e., the key-only attack). In this model, the adversary has the hardest-possible task: it is given only the bare minimum required to forge---i.e., the public key---and has no choice on which message to forge on.

In practice, an adversary could have means to obtain more information than this---e.g., it might procure, through some channel, a signature issued by the signer. This is not captured by the UF-KOA model and hence the reason to deem it weak. There are two ways to strengthen it: one, we could make the task of the adversary easier (e.g., let it forge on a message of its own choice); and/or two, we could provide it more information (e.g., give it signatures on messages of its choice). Let's now take a look at a model, called UF under known-message attack (KMA), that does the latter.

  2: UF-KMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Sample $q=q(n)$ arbitrary messages $m_1,...,m_q\in\mathcal{M}$, and generate signatures $\sigma_i\leftarrow\mathsf{S}(m_i)$, $1\le i \le q$
a. Send the set $\{(m_1,\sigma_1),...,(m_q,\sigma_q)\}$ to $\mathsf{A}(1^n)$, and challenge it on an arbitrary message $m^*\not\in \{m_1,...,m_q\}$

b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Although $\mathsf{A}$ has to still produce a universal forgery, it now gets---unlike in the UF-KOA model---a bunch of signatures on messages it knows (the known-message attack). The model can be further strengthened by allowing $\mathsf{A}$ to query and obtain signatures on messages of its choice. This yields the model, given below, called UF under chosen-message attack (CMA).

  3: UF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, responds with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$
a. Challenge $\mathsf{A}$ on an arbitrary message $m^*\not\in\mathcal{M}'$

b. Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Next, let's look at strengthening the model from the second aspect, i.e., by weakening the notion of what it means for an adversary to break the signature scheme. We go from universal forgery, which was discussed in the first experiment, to selective forgery (SF) and finally to existential forgery (EF) in the setting of KOA.

  4: SF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Receive from $\mathcal{A}$ the commitment $m^*\in\mathcal{M}$: $\mathsf{A}$ has to forge on $m^*$ in the end
Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

Note that although $\mathcal{A}$ has to a priori commit to the message it forges on, it still has more freedom than in the UF-KOA game---for EF-KOA, this restriction is also lifted.

  5: EF-KOA$^{\mathsf{A}}_\Sigma(1^n)$

Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$
Receive as response from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$

In a similar vein, it is possible to define the models $\mathtt{break}$-$\mathtt{attack}$ for $\mathtt{break}\in${SF,EF} and $\mathtt{attack}\in${KMA,CMA}. The strongest model of the lot---i.e., EF-CMA---is defined below as it is considered to be the model on which security of signature schemes should be based on.

  6: EF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\mathsf{S}(m)$, and add $m$ to $\mathcal{M}'$
Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $m^*\not\in\mathcal{M}'$

That is, in the EF-CMA-model, the adversary can obtain a bunch of signatures on messages it chooses adaptively, and, in the end, can forge on any fresh message. A stronger version of this definition ---called the strong EF-CMA (sEF-CMA)---is also considered desirable.

  7: sEF-CMA$^{\mathsf{A}}_\Sigma(1^n)$

a. Sample key $(sk,pk)\leftarrow\mathsf{K}(1^n)$ and run the adversary $\mathsf{A}(1^n,pk)$

b. Initialise a set $\mathcal{M}'=\emptyset$.
If $\mathsf{A}$ queries for signature on a message $m\in\mathcal{M}$, respond with $\sigma=\mathsf{S}(m)$, and add $(m,\sigma)$ to $\mathcal{M}'$
Receive as output from $\mathsf{A}$ a forgery $(m^*,\sigma^*)$: $\mathsf{A}$ wins if $\mathsf{V}(\sigma^*,m^*)=1$ and $(m^*,\sigma^*)\not\in\mathcal{M}'$

That is, the adversary can forge on a message on which it queried for a signature as long as the forgery is different from the one it received as a response to the query (i.e. a strong existential forgery).

P.S.

Definition. A signature scheme is said to be $\mathtt{break}$-$\mathtt{attack}$-secure if for all probabilistic polynomial-time adversaries $\mathsf{A}$
$$\Pr[\mathsf{A}\ wins\ \mathtt{break}-\mathtt{attack}_\Sigma^{\mathsf{A}}(1^n)]=negl(n).$$
where $\mathtt{break}\in${UF,SF,EF} and $\mathtt{attack}\in${KOA,CMA,KMA}.
Although, only signature schemes are discussed, the definitions can be easily adapted for message-authentication codes (MACs). In particular:

As the key generation algorithm generates only the symmetric key $k$, in Step 1 of the security models, there no key to be handed over to $\mathsf{A}$. As a consequence, UF-KOA is difficult in an information-theoretic sense.
Instead of querying for a signature on messages, $\mathsf{A}$ queries for tags.

There are other variants of attacks and breaks --- see [GMR], for example.

References:
[GMR]: Goldwasser, Micali and Rivest. A digital signature scheme secure against adaptive chosen-message attacks. (PDF)


When we encrypt-then-MAC, how do we defend the 2 parts? When we encrypt-then-MAC (which is the recommended case), do we send both in the same package? Both can be modified along the way, isn't it? how do we defend the 2 parts?

When we encrypt-then-MAC (which is the recommended case), do we send both in the same package?

Yes

  Both can be modified along the way, isn't it?

Yes, but not without the MAC check failing.

  how do we defend the 2 parts?

You don't need to do anything else. The MAC is the protection.


What advantages does Keccak/SHA-3 have over BLAKE2? Keccak/SHA-3 is new NIST standard for cryptographic hash functions.  However, it is much slower than BLAKE2 in software implementations.  Does Keccak have compensating advantages?

(Disclosure: I'm one of the authors of BLAKE2, but not BLAKE.)

Here are the slides from a presentation I gave at Applied Cryptography and Network Security 2013 about this. (Note: the performance numbers in those slides are obsolete — BLAKE2 is even faster now than it was then.)

The slides include quotes from NIST's 3rd-round Report on the SHA-3 Competition which show some of the advantages and disadvantages of BLAKE (not BLAKE2) compared to Keccak, in NIST's opinion.

Here's a blog post I wrote to accompany the slides.

The main reason that NIST gave was that BLAKE was more similar to SHA-2 than Keccak was. When the SHA-3 contest was designed, the whole point of it was to provide a new hash function that would be ready in case SHA-2 got broken, so it made sense to require the winner to be different from SHA-2. However now, with almost a decade more of research and SHA-2 looking no weaker, a hash function being similar to SHA-2 doesn't seem bad, and might even be good.

There was another reason that NIST gave that I omitted from the slides, which was that Keccak is more efficient in ASIC implementation.

That reason may be more important if you are a large organization, like the U.S. military or U.S. government, who is going have special hardware built for your project, but more flexible/general-purpose performance is more important to me. (See Adam Langley's blog post on this topic.)

Besides, everything is fast in hardware! See this catalog of hardware implementations of secure hash functions. ASIC implementations of BLAKE can process about 12.5 GB/s, compared to Keccak, which can process about 44 GB/s. An ASIC implementation of BLAKE2 would be probably about 40% faster than a similar implementation of BLAKE, i.e. around 17.5 GB/s.

But even 12.5 GB/s seems more than sufficient for most uses of a secure hash function.


Is AES restricted to only 64 characters for the key/password? I am wondering if AES only supports 64 character passwords?

When using truecrypt, the maximum character limit on passwords is 64 characters; however, when using WinRAR, the limit is 128 characters.

What determines the length of passwords I can use with AES?

Key sizes for AES are 128-bit, 192-bit and 256-bit. Depending on how you pack characters into bits, will determine how many characters that makes up. For example, you could pack 1000 characters into a 128-bit encryption key using something like PBKDF2 or scrypt.

That said, I wasn't aware that Truecrypt only supports 64 character passwords. Assuming that is correct (and I have no reason to doubt you yet), you could always use a keyfile with Truecrypt if you need a longer password, but keep in mind that a randomly chosen, 64 character password is surely infeasible to break any time soon.


Is One Time Pad considered Chosen-Plaintext Attack Secure? If we're considering Chosen-Plaintext Attack setting, then the adversary has access to the Encryption Oracle right, and we know that OTP is only considered secure if we use the key only once. How would we ensure that the adversary uses the key only once?

Or would it not matter how the adversary uses the encryption oracle since in the end they will be presented with a ciphertext corresponding to a plaintext not queried and the adversary would not be able to decrypt it because they don't know the key. Making it CPA-Secure. Is this second train of thought the correct way to think about OTP in CPA setting?

Thank you!

Note: In this answer, I stick to a definition of the One Time Pad where the random pad is used only One Time; at least, I've the name of it as support! Otherwise, it is well known that the OTP encryption scheme consisting of XOR with a repeated key is insecure by even the weakest standard (unknown plaintext with redundancy).

Late addition: further, I stick to the definition of IND-CPA given for ciphers in standard literature and quoted below. See this other answer for a different definition, which applies to the OTP, and is met.

INDistinguishability under Chosen Plaintext Attack applies to encryption schemes; there's no way the OTP can be made to match the definition of an encryption scheme, thus the formal definition of IND-CPA does not apply to the OTP.

Specifically, the OTP does not fit definition 3.7 in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, first edition (CRC Press, 2008):

  A private-key encryption scheme is a tuple of probabilistic
  polynomial-time algorithms ($\text{Gen}$, $\text{Enc}$, $\text{Dec}$) such that: (..)

  The key-generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k$; (..)
  The encryption algorithm $\text{Enc}$ takes as input a key $k$ and a plaintext message $m\in\{0,1\}^*$, and outputs a ciphertext $c$. (..)
  The decryption algorithm $\text{Dec}$ takes as input a key $k$ and a ciphertext $c$, and outputs a message $m$. (..)

  It is required that for every $n$, every key $k$ output by $\text{Gen}(1^n)$, and every $m\in\{0,1\}^*$, it holds that $\text{Dec}_k(\text{Enc}_k(m))=m$.

where $\{0,1\}^*$ is the set of all (finite-length) binary strings.

There's no way the OTP can fit this framework:

If we try to assimilate the random pad and the key, we hit the problem that in the above definition the same $k$ can be used for several messages (and further that some messages can be larger than the key, but that's secondary); the OTP does not allow that (due to the One Time requirement of OTP).
If we try to fit the random pad into $\text{Enc}$, and still keep the ciphertext as it is in the OTP (including, of the same size as the message), then we have no way to build a working $\text{Dec}$.

Note: some practical encryption schemes use message spaces deviating from $\{0,1\}^*$, like the set of all bytestrings up to some size, or even a fixed-size bytestring, perhaps even shorter than the key (which is common in block ciphers); and it is accepted to twist the definition of an encryption scheme to allow that. However it is an essential point of any encryption scheme that the total size of plaintext enciphered with a given key is allowed to increase significantly above the size of the key; again, the OTP does not allow that.


Why can an RSA signature be authenticated ONLY with the signer's public key? I'm an undergraduate Math student currently taking a cryptology course. I have a question about the RSA signature authentication mechanism.

An RSA signature can be authenticated with the public key of the signer. However, I'm wondering why it can ONLY be authenticated with the signer's public key. Why can't it be mistakenly authenticated with someone else's public key?

Let me clarify with an example. Suppose two people use random texts $p_1$ and $p_2$ for their signatures. Their private keys are $d_1$ and $d_2$ respectively, and their public keys are $(e_1,n_1)$ and $(e_2,n_2)$ respectively. So, the signature of the first person is

$s_1 = {p_1}^{d_1} \mod n_1$

Now, I understand the Math that this signature can be authenticated with the first person's public key i.e.

${s_1}^{e_1} \mod n_1 = p_1$

However, how can we claim that the following is never true?

${s_1}^{e_2} \mod n_2 = p_2$

The probability of such a "collision" occurring randomly, with honestly-generated RSA keys, is extremely low. Mathematically justifying that assertion can be tiresome, but the idea is the following:

Let $s$ be a RSA signature, i.e. an integer of size $k$ bits for some $k$ (e.g. $k = 2048$). We consider RSA keys $(n,e)$ where $n$ is the modulus (of size $k$ bits) and $e$ is the public exponent, of size $r$ bits (in practice most people use $e = 65537$, i.e. $r = 17$; Windows' CryptoAPI cannot tolerate public exponents longer than 32 bits anyway). We want to estimate the probability that $s^e = m \pmod n$.

If $s^e = m \pmod n$ then $n$ divides $s^e-m$. $s^e - m$, as an integer, has size roughly $k2^r$ bits. That integer cannot admit more than $2^{r+1}$ distinct prime divisors of size $k/2$ bits. Even if $s^e-m$ is indeed the product of $2^{r+1}$ distinct prime integers of size $k/2$ bits, then there are only about $2^{2r+1}$ distinct products of two such primes which divide $s^e-m$. In other words, with $k = 2048$ and a given 32-bit exponent $e$, then there can be at most about $2^{65}$ (and in practice much fewer) modulus values $n$ such that $s^e = m \pmod n$. However, there are roughly $2^{2048-20} = 2^{2028}$ possible 2048-bit RSA moduli (products of two 1024-bit primes), a vastly bigger value. Thus, probability of collision is very low.

If we allow the public exponent to be large ($r = 2048$) then the answer is not as simple, because the computation above will yield a maximum number of matching moduli of about $2^{4097}$, which is completely exaggerated and not actually possible. In fact, for a given $e$, the integer $s^e-m$ will be large and may be assumed to be "typical", in that its factorization in prime factors will use factors of various sizes. The Hardy-Ramanujan theorem tells us that an integer of size $k2^r$ bits will be the product of, on average, $\log r$ distinct primes, yielding $(\log r)^2$ possible matching moduli. This leads to the same conclusion as before, albeit with an assumption of $s^e-m$ to be "typical" as far as factorization is concerned.

The above is for a random collision. However, we can ask ourselves whether such an occurrence could be forced. It turns out that it can be done. That is, consider a message $m$ (padded hash value) and a signature $s$ produced with a key pair $(n,d,e)$. We have $s^e = m \pmod n$ and $s = m^d \pmod n$.

Now, take $m'$ (another message, or the same as $m$, it works in both cases). Then one can compute a new RSA key pair $(n',d',e')$ such that $s^{e'} = m' \pmod {n'}$, and this can be done with $s$ and $m'$ alone (without knowing anything about the original key pair). The idea is the following: select random small prime integers $p_i$; for each small prime, compute $e_i$ such that $s^{e_i} = m' \pmod {p_i}$. This is a discrete logarithm which is very easy if $p_i$ is small. Once you have enough $p_i$, compute $n'$ as their product. The public exponent $e'$ is then such that $e' = e_i \pmod {p_i-1}$ for all $i$, so $e'$ is easily recomputed with the Chinese remainder theorem. At that point, you have $n'$ and $e'$, and you know the prime factorization of $n'$, so computing the private key $d'$ is straightforward.

Of course, this yields a rather weird RSA key: $n'$ is the product of small primes (but this won't be seen until someone actually tries to factor $n'$), and $e'$ is large (much larger than 32 bits). Whether a similar construction can work while keeping $e'$ small is not known. The discussion on random collisions above tells us that, "morally speaking", targeting a small $e'$ ought to be hard. Indeed, if we target a fixed $e'$, then $n'$ will have to be one of the $(\log r)^2$ (at most) possible values; since we should end up with $(n',d',e')$, then this means that this reconstruction yields a partial factorization of $s^{e'}-m'$, and we know that integer factorization is hard (indeed, RSA relies on it).

One alternate way to see it is the following: when trying to build $(n',d',e')$, we are actually trying to find factors of $s^{e'}-m'$ such that their product has the right size for a RSA modulus; we can do that if we are allowed to alter $e'$ and/or $m'$ so that $s^{e'}-m'$ is easy to factor. The more $e'$ and $m'$ are constrained, the harder the problem becomes. If $e'$ and $m'$ are fixed, then the problem seems as hard as breaking RSA. At which point the problem reaches the "infeasibility threshold" is not known.

See this article for a longer treatment of this subject. Bottom-line: digital signatures yield guarantees about a message for a given public key, not the other way round.


What is a "lattice" in cryptography? There are some questions here concerning lattice-based cryptography and this kind of cryptography seems to be especially useful if quantum computers are assumed to exist.

When reading such questions I always asked myself: "What is a lattice?"

And now I'm asking here:

How is a lattice defined?
What's the most common operation performed on / with a lattice? (like doubling and adding in ECC)

If you need assumptions on what knowledge is available:
Solid knowledge on most non-quantum resistant cryptography, like teached in the HAC.

How is a lattice defined?

A lattice $\mathcal L(B)$ is the set of all integer combinations of the basis $B = \{b_1, ..., b_n\}$ of $n$ linearly independent vectors. That is, lattice $\mathcal L(B)$ is defined as:
\begin{equation}
\mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\}
\end{equation}

In cryptography, we are interested on integer lattices, i.e., those where $B \in \mathbb Z^{n\times n}$, and, specially, on $q$-ary lattices, which are the modular version of integer lattices.

  What's the most common operation performed on / with a lattice? (like
  doubling and adding in ECC)

As you see, elements in a lattice are simply vectors in the space where the matrix is defined. In the case of integer lattices, the space is $\mathbb Z^{n\times n}$, so elements of the lattice are just integers vectors. For this reason, lattice-based schemes usually operate with vectors and matrices, so the basic operations are the usual: vector/matrix addition, inner product, etc.

For the sake of illustration, the following is the main step during the encryption function of the CCA1-secure cryptosystem from Micciancio and Peikert [1]:
\begin{equation}
b^t = 2(s^t A_u \mod q) + e^t + (0, \operatorname{encode}(m))^t \mod 2q
\end{equation}

where $b$ is the ciphertext, $s$ and $e$ are random vectors and $A_u$ is the public key (or more accurately, derived from the public key). You can see that everything is very simple from the point of view of the actual operations that are performed: $b, s$, and $e$ are vectors, and $A_u$ is a matrix, and the operations performed are additions and multiplications. The only "special" part here is the encoding of the message from a bit-string to a lattice point.

[1] Micciancio, D., & Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology–EUROCRYPT 2012 (pp. 700-718). Springer Berlin Heidelberg (PDF).


Computing Logarithm using homomorphic encryption Let's say we have $Enc_{pub}(a)$, the encryption of an integer $a \in \mathbb{Z}^*$ under the public key pub with a Homomorphic encryption scheme that supports both addition and multiplication.

Is there an efficient way to compute $Enc_{pub}(log(a))$?

I tried with Taylor Series approximation, but this one won't work unless we have the Taylor  series of $log(x)$ about a point $b$ that is very close to $a$, which we cannot afford given that we don't know the value of $a$.

This answer is a bit messy, but it should work...

If we have access to a fully homomorphic encryption scheme $E(x)$ then we know that $E(x) + E(y) = E(x+y)$ and $E(x) \cdot E(y) = E(x \cdot y)$.

In addition we know that there exists an efficient Boolean circuit, $BC$, such that $BC(x_1,x_2,...,x_n) = y_1, y_2,...y_n$ where $x_i$ and $y_i$ are the bits of the binary string $x$ and $y$ respectively both of length $n$ and that $x = b^y$ for some base $b$.  Thus this is the circuit for $\log_b(x) = y$.

Now instead of being given $E(x)$ we can just as easily be given $E(x_1), E(x_2), ..., E(x_n)$.  When you want to encode a $0$ you map it to a random even number, $b$, then you encrypt that number, $E(b)$.  Likewise for $1$, except you map it to an even number.  Now all we do is evaluate the circuit and when we encounter an xor gate we do $E(I_1 \oplus I_2) = E(I_1) + E(I_2)$ and likewise for and gates $E(I_1 \wedge I_2) = E(I_1) \cdot E(I_2)$ where $I_1$ and $I_2$ are the inputs to the gate.  For all other gates convert them into $and$ and $xor$ gates.  At the end we will be left with $E(y_1), E(y_2),...,E(y_n)$ which is an encryption of the $\log_b(x)$.

One interesting benefit is that $x$ and $y$ could be represented in any way, not just a n-bit integer.  You would just need to use the correct circuit for the representation.  For example if $n = 64$ you could let $x_1,x_2,...,x_n$ be the IEEE 754 double-precision binary floating-point format representation of $x$ and with the correct circuit $y_1, y_2,...y_n$ would be a double-precision floating-point so you can do more precise calculations if you wanted.

See What does "circuits" mean in Cryptography? for more details on the Boolean circuit only using addition and multiplication.

Edit:

Since the question originally asked how to get from $E(x)$ to $E(log(x))$ and my answer only works if you have the bits and returns bits, I asked another question Fully Homomorphic Encryption: Going from an integer to bits to try to help.

They suggested using a Bit Extraction Circuit to go from $E(x)$ to $E(x_1), E(x_2), ..., E(x_n)$.  Then compute the above.  Now you have $E(y_1), E(y_2),...,E(y_n)$ which you can easily put back together by computing (assuming $y_1$ is the least significant bit) $E(log(x)) = E(y_1) + 2\cdot E(y_2) + 2^2\cdot E(y_3)+\dots+2^{n-1}\cdot E(y_n)$


RSA Digital Signature vs Elgamal Digital Signature What are the advantages of RSA signatures against ElGamal signatures?
Is there a situation in which it would be better e.g. to use RSA signatures?

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work.

The main technical advantage of RSA is speed.
With RSA you only need to do a small-exponent exponentation to verify a signature, where as with plain ElGamal signatures you'd have to do three full-sized exponentiations to verify a single signature. And if you read this, also think about embedded processors who have a public key hardcoded and have to verify the integrity of security-critical firmware updates and other things sent from a central server.
Another domain where RSA is faster, is key generation. If you do ElGamal naively, you'll generate your own field and generator, which is really slow, especially if you consider that "ElGamal primes" $p$ need the special property that $(p-1)/2$ is also prime. Compare that to RSA where you'd only need to find two (random) half-sized primes without any special property and take into consideration that the workload grows superlinear in bitsize.
Of course, if you use standardized fields and generators, ElGamal key generation becomes much faster as it simply is one exponentation and selecting a random integer.

The next domain where RSA is superior to ElGamal is signature with message recovery.
RSA allows you to sign messages which you don't have to encode outside the signature itself which allows very short messages (less than 1700 bits or so) to be directly embedded in the signature, greatly reducing bandwidth requirements in embedded devices and smartcards.
ElGamal signatures on the other hand require you to hash the message and thus you have to append the message to the signature as there's no way to recover it from the hash 100% of the time.

The third point why RSA is superior to many people is standardization.
RSA is greatly defined and standardized in PKCS#1 allowing any developer to just grab the specification and produce an interoperable implementation without any doubt, as every single step is documented. How to encode the hash? Documented. How to convert integers to byte sequences? Documented. How to transfer public keys? Documented.
ElGamal signatures on the other hand completely lack such a specification and the best you can find are some "ad-hoc" implementations following the original mathematical description. Not exactly ideal for interoperability.
It should be noted however, that the related DSA (which is a variant of ElGamal signatures) does have excellent specifications in the form of FIPS-186 (PDF) or your national equivalent.

One of the less technical but still important points to be noted is understandability.
When it comes to RSA, it's super-easy to understand. You take 5-15 minutes with a developer and you can explain him how they work and he can imagine why they are secure. Signature and verification are straight-forward operations and there isn't an awful lot to be done wrong.
ElGamal signatures on the other hand are more difficult to understand. For example in ElGamal your verification is at best an "consistency check" at a first look and the overall description is much much more complex to read and understand, especially compared to RSA. After all, there's a reason why RSA is taught in (some) schools and not ElGamal.

The final and probably one of the more important reasons is lobbying.
Back in the day when RSA was invented, Rivest, Shamir and Adleman sat together and also founded the RSA company. This company sold the RSA cryptosystem to companies and lobbyied a lot for it's use and ensured it ended up in a lot of standards for data authentication (for example at the IEEE).
ElGamal signatures had no comparable economical interest behind them that supported them. It must be said however that DSA did had a similar interest behind it, as the US government established it specifically to avoid RSA (and the related patent cost) and mandated it for quite some time for official products.


Prove that H(s) = G(!s) is a CPRNG if G(s) is one Given a cryptographic pseudo-random number generator $G$, prove that $H$ with $H(s) = G(!s)$ is also a cryptographic pseudo-random number generator. Here $s$ is a binary string; $!s$ is its complement.

For this we have to prove the two properties of a cryptographic pseudo-random number generator: the expansion and the pseudo-randomness.

The expansion is trivial to prove, because that's the same for $H$ and $G$. How can we prove that it is also cryptographically pseudo-random?

A proof by contradiction seems most appropriate here.

Assume that $H$ is not cryptographically secure. This means it fails to provide at least one of the properties of a CSPRNG as defined in your class, textbook, whatever. Then you must show how you can use an attack on $H$ to attack the cryptographic security of $G$. To do this, note that $H(!s)=G(!!s)=G(s)$. Since $G$ is cryptographically secure, your assumption must be incorrect. Therefore, you can conclude that $H$ is in fact cryptographically secure.


Validating a shared secret between two parties, one bit at a time What is the following protocol known as?
Is it considered secure? Would it work?

Background

Alice and Bob each have a secret.

They wish to determine if they both know the same secret.

If they do share the same secret, they are happy for each other to know this. If they don't share the same secret, they don't want to disclose that secret to the other person.

There is no trusted third party.

They communicate over a secure channel.

Protocol

Alice tells Bob the first bit of the secret.
Bob compares this bit to his own secret, if it matches, Bob shares the second bit of his secret with Alice, if it doesn't match, Bob shares a random bit with Alice.
Alice compares this bit to her own secret, if it matches, Alice shares the third bit of her secret with Bob, if it doesn't match, Alice shares a random bit with Bob.

They each continue step 2 and 3. If at any point, their bits don't match, all subsequent bits they share are random.

If they reach the end and every bit has matched, they know they share the same secret, if at any point a bit didn't match, they know they didn't share the same secret, and keep the rest of the secret safe.

Of course this depends on randomness, so there is a small chance you don't share the same secret, but will come to the conclusion that you do, it's dependent mostly based on the length of the secret, the longer the less likely you run into coincidence that those random bits just happen to match up.

To protect against leaking the start of the message too easily, Alice and Bob could pre-pad their true secret with a shared random pre-secret key.

Assuming that you can run this protocol multiple times, it is completely insecure. Say we are an attacker trying to deduce Alice's secret and that the secret has length $n$.
We can then extract Alice's secret using at most $(n+n^2)/2$ times. Let's call the secret as $s$ and let $s_i$ denote the $i$th bit of $s$.

Our attack hinges on two key observations:
 1. For odd $i$, Alice will just send us $s_i$, if we know the prefix $s_1\|\dots\|s_{i-1}$ and execute the protocol honestly using an $s'$ with the same prefix.
 2. For even $i$, Bob needs to send the bit. If Bob sends the correct bit, Alice's answer will always be $s_{i+1}$ and therefore identical for multiple executions. If Bob sends the wrong bit, Alice's answer is random and thus will differ between two executions with probability $1/2$.

So for $1\le i \le n$ our attack proceeds as follows:

If $i$ is odd, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i-1} = s_1\|\dots\|s_{i-1}$ and perform the protocol honestly.
Note that by the correctness of the protocol  Alice's message in round $i$ of this execution will be $s_i$. Thus at the end of this execution we have learned $s_{i}$ with probability $1$.
If $i$ is even, choose a random secret $s'$ such that $s'_1\|\dots\|s'_{i} = s_1\|\dots\|s_{i-1}\|0$. Using this $s'$ run at most $n$ executions of the protocol. Let $\bar{s}_j$ denote the bit sent by Alice in round $i+1$ of the $j$th execution. If there are ever $j,j' \in \{1,\dots,n\}$ such that $\bar{s}_j \neq \bar{s}_{j'}$ we can abort and deduce that $s_i=1$. Otherwise, if $\bar{s}_j = \bar{s}_{j'}$ for all $j,j' \in \{1,\dots,n\}$, then we can deduce with probability $1-2^{-n}$ that $s_i=0$ and $s_{i+1}=\bar{s}_j$. So overall, we have learned at least $s_{i}$ with probability at least $1-2^{-n}$.

After at most $(n + n^2)/2$ executions we have thus revealed $s$ with probability at least $(1-2^{-n})^{n/2} > 1-2^{-n/2}$.


Why is WOTS-type signature schemes OTS? I'm sure I've missed something super trivial, but why are WOTS-type schemes one-time? I've been looking into hash-based schemes, and I feel like I understand WOTS quite well (specifically I have looked at WOTS+), but I cannot figure out why WOTS would not be safe to use just a few times as an FTS such as HORS(T) for example?

I'll only talk about things on a very high level here, probably much higher than what you already know and will use Matthew Green's blog post as the primary reference. Nevertheless the idea should come across.

So in that post, WOTS is described as a smart way to have more than two (0 and 1) lists of of secret key values to publish as the signature. Now what you do is that for each symbol (eg byte), you publish one entry from these lists (in a smart way). But if you do this twice for different message which differ in at least 2 bytes, you can take one byte from the one and one byte from the other signature to forge a new signature! Also note that (as far as I can tell), it's usually not assumed for this kind of signature scheme to mandate hashing the input and only passing the hash to the signature primitive.


Are derived hashes weakening the root? Given a root hash

root = H(plaintext)

and two (or more) derived hashes

h1 = H(salt1 + root)
h2 = H(salt2 + root)

would the knowledge of h1 and h2 alone increase the chances of finding the root hash or even the plaintext?
I'm using SHA256.

To the best of our knowledge, SHA256 does not leak any additional information from related hashes.

On the other hand, the state of "our knowledge" might not be that comprehensive; this security property of SHA256 cannot be derived from the base security assumptions of a hash function (preimage resistance, second preimage resistance and collision resistance), and as far as I know, no one has studied it.  While it may be (and likely is) secure, no one has really studied it, and so there there might be a semiobvious leakage that no one happened to find yet.

Now, there is an obvious variation on this which has been studied: HMAC.  HMAC is a Message Authentication Code, that is, it has a security assumption that if you give someone (who doesn't know the key) a large number of MAC outputs based on known texts, they still cannot derive the key, or any information about MAC outputs for texts they haven't seen.  That is precisely the security assumption that you are looking for; and so HMAC has been analyzed against the exact problem you're looking for.  HMAC uses a hash function (for example, SHA256) as an underlying primitive, and it does have a small additional cost over the underlying hash; if you can do some precomputation, this additional cost is just one more hash compression evaluation.

As for how you would use HMAC; well, HMAC has two inputs, a "key" and a "message".  You would make your "root" the key and the "salt" the message, and use the output of the MAC as your derived hash.


Do low-entropy fingerprints actually make any sense? I'm thinking of ZRTP and OTR in particular here. From my understanding, after a Diffie-Hellman session is initiated, the shared secret is then hashed into a 4-digit number, which the two parties can then check out-of-band (or in ZRTP in-band, assuming that people can recognize each others' voices).

How is this possibly secure? The only articles I've read about the protocols say something like "there's only a 1/10000 chance that it's a man in the middle if the numbers match", but can't the man-in-the-middle pick his own private keys (by brute force) such that the numbers match? That is, with a setup like

Alice <- ss_am -> Mallory <- ss_mb -> Bob

could Mallory not use a brute-force search to find private keys such that ss_am and ss_mb hash to the same 4 numbers?

Or am I fundamentally misunderstanding something about ZRTP and OTR?

A related question would be the SSH public-key randomart thing. It has not a lot of bits of entropy, so couldn't an impersonator simply brute-force a private key such that the public key has the same randomart as the real public key?

This question probably also applies to ideas like generating gravatars from public keys so that impersonators look different, or the common practice of referring to PGP keys by their first few bits.

How can low-entropy fingerprints be useful?

Short key fingerprints are indeed vulnerable. But those are different from the short-authentication-string (SAS) used by ZRTP.

A simple SAS based protocol using one-time keys could look like this:

Alice sends a (collision resistant) hash of her public key to Bob.
Bob sends his public key to Alice
Alice sends her public key to Bob

The short authentication string is computed as hash of both public keys.

Bob can't deliberately influence the SAS because he doesn't know Alice's public key yet. Alice can't deliberately influence the SAS in Step 3, because she already committed to her public key, by publishing its hash in Step 1 before she learned about Bob's key.

Alice could abort the connection after step 2 or Bob after step 3, but that should display an error to the user and can't be pulled off too often.