AES-128. Do there exist two different keys for a pair (text, encrypted text)? I have two very close questions.

Question 1

y = AES-128(x, key).
Is it possible that AES-128 will return the same y (encrypted text) for different keys?

I know that each key selects one permutation from the set of (2^128)! possible permutations. We have (2^128) possible keys and it is less than number of possible permutations. But it doesn't mean that there are no two different keys for some pair of text and encrypted text.

Question 2

If we have fixed x,y (both of them have the size of 128 bit) does there exist a key( key size is 128 bit) so that
y = AES-128(x, key) ?

Example.
We have 2 bit message and 2 bit key. There are 4 possible messages: msg1 = {0,0}, msg2={0,1}, msg3 = {1,0}, msg4 = {1,1} and there are 4 possible keys. We have 4! = 24 possible permutations of messages.
I can select the next permutations

| From\key | key1 | key2 | key3
--------------------------------
| msg1     | msg2 | msg3 | msg4
--------------------------------
| msg2     | msg1 | msg4 | msg3
--------------------------------
| msg3     | msg4 | msg1 | msg2
--------------------------------
| msg4     | msg3 | msg2 | msg1
--------------------------------

Here I have a mapping from a message to every message. e.g. I can get msg4 from msg1 using key3. Has the AES-128 the same property for the mentioned x,y?

$\newcommand{\given}{\mathrel{|}}$Answer 1.

Let $\pi_0, \pi_1$ be independent uniform random permutations of $\{0,1\}^{128}$.  What is the probability that for any fixed string $x \in \{0,1\}^{128}$, $\pi_0(x) = \pi_1(x)$?

For any fixed string $x$ and each $i$, the variable $\pi_i(x)$ is a uniform random element of $\{0,1\}^{128}$.  (Only if we consider multiple distinct inputs $x_0 \ne x_1$ does the fact that $\pi_i$ is a uniform random permutation rather than a uniform random function come into play, when we consider whether repeated elements are possible in $\pi_i(x_0), \pi_i(x_1)$.)  Since $\pi_0$ and $\pi_1$ are independent, so are $\pi_0(x)$ and $\pi_1(x)$.

Thus
\begin{align*}
  \Pr[\pi_0(x) = \pi_1(x)]
    &= \sum_y \Pr[\pi_0(x) = y \given \pi_1(x) = y]\cdot\Pr[\pi_1(x) = y] \\
    &= \sum_y \Pr[\pi_0(x) = y]\cdot\Pr[\pi_1(x) = y] \\
    &= \sum_y 2^{-128} \cdot 2^{-128}
     = 2^{128} \cdot 2^{-128} \cdot 2^{-128}
     = 2^{-128}.
\end{align*}

What if instead of uniform random $\pi_i$ we had $\pi_i = \operatorname{AES}_{k_i}$ for uniform random strings $k_i$?  If you could predict how that would affect the distribution nonnegligibly, you could distinguish AES from a uniform random permutation, violating the pseudorandom permutation family property that it is conjectured to exhibit, and there would be lots of cryptographers who would like to have a word with you.

So, for any fixed plaintext $x$, does there exist a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$?  Maybe, but you're not likely to find them—for each plaintext, only $1/2^{128}$ of the $2^{256}$ possible pairs $(k_0, k_1)$ of these keys is likely to work!  (It's not guaranteed that any of them will work, but it would be a remarkable publication if you could say one way or another about that guarantee.)

Does there exist any plaintext $x$ such that there exists a pair of keys $k_0, k_1$ under which $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$?  Note the order of quantifiers: We are not asking about some particular fixed $x$; we are asking whether there is any pair of keys that agrees on any plaintext.  This is a little trickier.  To approximate an answer, let's first try the uniform random function model.  A random function is not restricted to be a permutation, so its values at two distinct points are independent, which makes the analysis a little easier.

In the uniform random function model, what is the probability that there exists a plaintext $x$ on which two random functions $f_0$ and $f_1$ agree, $\Pr[\exists x. f_0(x) = f_1(x)]$?  We can answer this by answering it in the complement: what is the probability that for all plaintexts $x$, two random functions disagree on $x$?

\begin{align*}
  \Pr&[\exists x. f_0(x) = f_1(x)] \\
   &= 1 - \Pr[\neg\exists x. f_0(x) = f_1(x)] \\
   &= 1 - \Pr[\forall x. f_0(x) \ne f_1(x)] \\
   &= 1 - \prod_x \Pr[f_0(x) \ne f_1(x)] \\
   &= 1 - \prod_x \bigl(1 - \Pr[f_0(x) = f_1(x)]\bigr) \\
   &= 1 - \prod_x (1 - 1/2^{128})
    = 1 - (1 - 1/2^{128})^{2^{128}}.
\end{align*}

That may look painful to evaluate, but it's turns out to be approximately $1 - e^{-1} \approx 63\%$, since $(1 + x/n)^n \to e^x$ as $n \to \infty$.  (This is why you should pay attention in calculus, kids!)

That's the probability that there exists an input on which two uniform random functions agree.  Of course, AES isn't even conjectured to be a random function—it's designed to be a random permutation.  How does this answer change if we use random permutations $\pi_i$ instead of random functions $f_i$?  The crux is that $\pi_i(x)$ and $\pi_i(\xi)$ for $x \ne \xi$ are dependent—they cannot be equal—whereas $f_i(x)$ and $f_i(\xi)$ are independent.

So let's consider how that affects the expansion of $\Pr[\forall x. \pi_0(x) \ne \pi_1(x)]$, first by examining the case of two distinct inputs $x \ne \xi$, and expanding with the chain rule:

\begin{align*}
  \Pr&[\pi_0(x) \ne \pi_1(x), \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= \Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)]
      \cdot \Pr[\pi_0(\xi) \ne \pi_1(\xi)].
\end{align*}

For the case of $f_i$, by independence of $f_i(x)$ and $f_i(\xi)$ we reduced this to

\begin{align*}
  \Pr[f_0(x) \ne f_1(x)] \cdot \Pr[f_0(\xi) \ne f_1(\xi)]
  = (1 - 2^{-128}) \cdot (1 - 2^{-128}).
\end{align*}

How do the left-hand factors compare?  We can expand the permutation case by Bayes' rule:

\begin{align*}
  \Pr&[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x)]
        \frac{\Pr[\pi_0(\xi) \ne \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]}
             {\Pr[\pi_0(\xi) \ne \pi_1(\xi)]} \\
   &= 1 - \Pr[\pi_0(x) = \pi_1(x)]
        \frac{1 - \Pr[\pi_0(\xi) = \pi_1(\xi) \given \pi_0(x) = \pi_1(x)]}
             {1 - \Pr[\pi_0(\xi) = \pi_1(\xi)]} \\
   &= 1 - 2^{-128} \frac{1 - 1/(2^{128} - 1)}{1 - 1/2^{128}}.
\end{align*}

The quantity $1/(2^{128} - 1)$ arises because if $\pi_0(x) = \pi_1(x)$, the common value is excluded from the possible values of $\pi_0(\xi)$ and $\pi_1(\xi)$.

Thus, $$\Pr[\pi_0(x) \ne \pi_1(x) \given \pi_0(\xi) \ne \pi_1(\xi)] > \Pr[f_0(x) \ne f_1(x)],$$ from which we can conclude that $$\Pr[\forall x. \pi_0(x) \ne \pi_1(x)] > \Pr[\forall x. f_0(x) \ne f_1(x)].$$ This further means that $$\Pr[\exists x. \pi_0(x) = \pi_1(x)] < \Pr[\exists x. f_0(x) = f_1(x)],$$ so there's less than about a 63% chance that any pair of permutations chosen uniformly at random agree on any plaintext.

Turning back to AES, we might guess that for about 63% of the key pairs $(k_0, k_1)$ there is a plaintext $x$ with $\operatorname{AES}_{k_0}(x) = \operatorname{AES}_{k_1}(x)$.  Not bad odds for existence—but will you find them by flailing around randomly, which is about the only thing you can do until you're ready to publish a novel cryptanalysis of AES?  No—there's too much hay in that stack of $2^{128}$ possible plaintexts.

Answer 2.

Exercise for the reader.  If you followed Answer 1, you should have all the tools you need to answer this yourself.


How feasible is a preimage attack or speedups to brute force a substring of MD5? Beyond the birthday problem analysis how feasible is a preimage attack or speed up brute force on a substring of MD5. For instance let's say from the 128 bits I decide to strip 24 bits, the first four and last 20 of a generated MD5.

How can you attack or fast generate a preimage that will collide on the same substring.

ps.It is known MD5 is broken, some hardware can compute billions of MD5 hashes per second. The intent of the question is theoretical understanding.

Right now, the cheapest known algorithms for (partial) preimage search are generic algorithms, costing ${\sim}2^b/t$ to compute a preimage for any of $t$ target $b$-bit strings in time ${\sim}2^b/t^3$ if parallelized $t^2$ ways—here $b = 128 - 24 - 4 - 20 = 80$.

The Sasaki–Aoki algorithm, while perhaps theoretically interesting, costs about a petabyte of memory, when at much lower cost you could power 32 CPUs (or just MD5 circuits) instead and get an answer faster with a naive generic search in parallel.


AES/DES question about determine a key I have a question. If you receive a DES encrypted message for which you would NOT recognize the plaintext if it were decrypted, is there any way to potentially determine the key if all keys are likely? What about for AES?

No. For any key $k$ your ciphertext $c$ has a corresponding plaintext $p$ (since block ciphers are families of bijections). Hence, since you can't (in)validate plaintexts, you can't discard any possible key.

Or, in other words: If someone claimed the right key was a certain $k$, you had absolutely no way to ever prove them wrong.


How does RIPEMD160 pad the message? For RIPEMD hashing algorithm on hardware
I am not exactly getting how padding works

So as per my understanding padding will work like explained below:

For ripemd 160 message should be multiple of 512 bits. So, along with message to make it 512 bits, after message we pad 1 following zeros. Last 64 bits of 512 block are reserved for length of the message.

Suppose message is a which I have to send it for hashing. So first it will go through padding. So for message a asci value 61 will be send for padding which is nothing but 61 hex.

So after value 61 there will be 1 and followed by zeros and last 64 bits will be length of message. So as per little endian conventions, byte wise representation of a after padding will looks like below right?

512'h08000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008061

(MSB side last byte 08 is nothing but length of message a LSB side 61 is actual message then followed by 1 and zeros) as ripemd is little endian based.

Please correct me if I am wrong. Is my description correct? If not, how does RIPEMD160 pad the message?

RIPEMD-160 uses precisely the same padding and endianess convention as MD5.

Everything is little-endian, with the exception of the order of bits in bytes, which is kept big-endian. If the message is $n$-bit, it is appended a single bit at 1 and $511-((n+64)\bmod512)$ bit(s) at 0 , then the representation of $n$ on 64 bits. The resulting padded message is an integral number of 512-bit blocks, which are each considered 16 words of 32 bits.

Note: It follows that the padding bit at 1 corresponds to a byte mask with value $2^{7-(n\bmod 8)}$. The $n\bmod 8$ last message bit(s) are in the high-order bit(s) of that byte, which $7-(n\bmod 8)$ low-order bit(s) are 0.

Suppose the message is the one-character string "a", and that is coded in ASCII as the single byte 61h = 01100001b = 97.

That's the bitstring 01100001. $n=8$, thus the padding is 1 followed by 439 0 (with the first eight bits of that padding 10000000 corresponding to byte 80h), followed by the length $n=8$ represented as the bitstring 00001000 00000000 00000000 00000000 0000000 00000000 00000000 0000000 (with the first eight bits 00001000 corresponding to the byte 08h).

Showing this as a string of 64 bytes with bytes and 32-bit boundaries shown (and individual bytes shown in big-endian hexadecimal), the padded block is

61 80 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   00 00 00 00   00 00 00 00
00 00 00 00   00 00 00 00   08 00 00 00   00 00 00 00

Packing that into 32-bit words using little-endian convention (and individual 32-bit words shown in big-endian hexadecimal), we get

00008061      00000000      00000000      00000000
00000000      00000000      00000000      00000000
00000000      00000000      00000000      00000000
00000000      00000000      00000008      00000000

or in decimal { 32865, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0 }.

Note: a former version of this answer did not take into account the exception to little-endianness in the conversion of bytes to/from bits, and used uppercase ASCII code in the example. I'm confident about the present revised version.

Simple demonstration and example output for the reference code rmd160

// Demonstration of rmd160 - public domain
// note: on machines with more than 32-bit unsigned long, rmd160.h requires a simple change
#include "rmd160.h" // at http://homes.esat.kuleuven.be/~bosselae/ripemd160/ps/AB-9601/rmd160.h
#define SIZEOFHASH  20      // size of the hash in bytes
#define SIZEOFBLOCK 64      // size of a block in bytes

// including the code simplifies compilation+linking into a tool
#include "rmd160.c" // at http://homes.esat.kuleuven.be/~bosselae/ripemd160/ps/AB-9601/rmd160.c

// hash a byte buffer in memory
void hashmd160(
    const byte  *iData,             // input
    size_t      iDataLength,        // size of input in bytes
    byte        oHash[SIZEOFHASH]   // result (must be allocated by caller)
    )
    {
    dword       vHash32[SIZEOFHASH%4==0 ? SIZEOFHASH/4 : -1 ];      // the hash, as 32-bit words
    dword       vBlock32[SIZEOFBLOCK%4==0 ? SIZEOFBLOCK/4 : -1 ];   // a block, as 32-bit words
    size_t      vb;
    int         vj;
    // start hashing
    MDinit(vHash32);
    // hash full blocks; needed only when iDataLength>=SIZEOFBLOCK
    for (vb = iDataLength/SIZEOFBLOCK; vb!=0; --vb)
        { // make a little-endian copy of SIZEOFBLOCK bytes from iData to vBlock32
        for (vj = 0; vj<SIZEOFBLOCK/4; ++vj, iData += 4)
            vBlock32[vj] = iData[0] | iData[1]<<8 | (dword)(iData[2] | iData[3]<<8)<<16;
        compress(vHash32,vBlock32);
        }
    // hash remaining bytes
    MDfinish(vHash32, (byte *)iData, iDataLength, iDataLength>>16>>16);
    // make a little-endian copy of SIZEOFHASH bytes from vHash32 to oHash
    for (vj = 0; vj<SIZEOFHASH; ++vj)
        oHash[vj] = (byte)(vHash32[vj>>2]>>((vj&3)<<3));
    }

// hash each argument, print its hash and the (quoted) argument
int main(int argc, char *argv[])
    {
    byte    vHash[SIZEOFHASH];
    int     vj,va;
    for(va=1; va<argc; ++va) {
        hashmd160((const byte *)(argv[va]),strlen(argv[va]),vHash);
        for (vj = 0; vj<SIZEOFHASH; ++vj)
            printf("%02x",vHash[vj]);
        printf(" \"%s\"\n",argv[va]);
        }
    return EXIT_SUCCESS;
    }

/* Example output
9c1185a5c5e9fc54612808977ee8f548b2258d31 ""
0bdc9d2d256b3ee9daae347be6f4dc835a467ffe "a"
8eb208f7e05d987a9b044a8e98c6b087f15a0bfc "abc"
5d0689ef49d2fae572b881b123a85ffa21595f36 "message digest"
f71c27109c692c1b56bbdceb5b9d2865b3708dbc "abcdefghijklmnopqrstuvwxyz"
12a053384a9c0c88e405a06c27dcf49ada62eb2b "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"
b0e20b6e3116640286ed3a87a5713079b21f5189 "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"
9b752e45573d4b39f4dbd3323cab82bf63326bfb "12345678901234567890123456789012345678901234567890123456789012345678901234567890"
*/


How can we tell if there is a Zero-Knowledge Proof for a given problem? I remember my cryptography instructor saying that in math, we can use logic to find out what we can prove and what we can't prove. Assuming this, how would we use logic to find out if a given problem has a ZKP or if it does not? On a similar note, is there a ZKP to show that a file (that one wants for someone else to download) is not malicious? Not sure if that applies to ZKP's well, though. Still curious on what you guys have to say about it. Thanks.

Assuming this, how would we use logic to find out if a given problem has a ZKP or if it does not?

From a theoretical standpoint, this has a rather simple answer: If the language you are trying to prove lies in IP or PSPACE then there is an (efficient) ZKP for it.

So, from a formal standpoint, a ZKP looks as follows:
There's a prover and a verifier. The prover is (in principle) computationally unbounded, the verifier is a probabilistic polynomial-time Turing-Machine. Now both sides know the specification of the language and the potential element (the "word") of the language. An interactive proof is now that the prover tries to convince the verifier that the word is in the language and has at least a 2/3 chance to succeed if it is (this is called "completeness"). On the other hand if the word is not in the language, any prover should at most have a 1/3 chance to succeed to convince the verifier that the word is in the language (this is called "soundness").

Every such interactive proof can be turned into a zero-knowledge proof.
Additionally if a language is in PSPACE there is an interactive proof for it (which can be turned into a zero knowledge proof).
Though one may want to note that neither construction is "efficient" in a practical sense.

A zero-knowledge proof has the same completeness and soundness properties as an interactive proof but additionally for each verifier there must be a simulator that when given an input word must be able to output a communication transcript that is indistinguishable from that that the given verifier would have with a real prover for every word in the language. That means that one could also have come up witht the transcript on their own and thus it doesn't leak anything only the prover could know.

Note for our local pedants: The above talks about computational zero-knowledge proofs.

  On a similar note, is there a ZKP to show that a file (that one wants for someone else to download) is not malicious?

Well, if you can come up with a protocol that would prove that to said person, you could convert it into a zero-knowledge proof. But I suppose the tricky part here is defining what "not malicious" means in a formal sense that satisfies soundness (i.e. a prover shouldn't be able to convince somebody that a file is "not malicious" even though it is).


How much work is required to find multiple collisions for a hash function? Assume an ideal hash function of output size n bits, finding one collision requires approximately 2^(n/2) evaluations of the hash function using a birthday attack.

However, how many evaluations are required to produce two or more collisions?

Note I am talking about distinct collisions i.e. $H(A)=H(B)$, $H(C)=H(D)$, etc.

The expected effort to find $k$ distinct collisions on an ideal hash function of output size  $n$ is about $\sqrt{2k} \cdot 2^{n/2} = \sqrt{k2^{n+1}}$ (for $k << 2^{n/2}$).

One way to see this is to look at the probability of the outputs of two distinct inputs colliding, which is $2^{-n}$; if we generate outputs for $\sqrt{2k} \cdot 2^{n/2}$ distinct inputs, there are $(\sqrt{2k} \cdot 2^{n/2} \cdot (\sqrt{2k} \cdot 2^{n/2}-1))/2 \approx 2^nk $ pairs of outputs; if the collision probabilities are independent (which they approximately are if we stay $k << 2^{n/2}$), then the expected number of collisions we get in the set of outputs is $2^{-n} \cdot 2^nk = k$

Note that for $k=1$, we get about $\sqrt{2}\cdot 2^{n/2}$ expected outputs for a single collision.  That's not a contradiction to the $2^{n/2}$ rule of thumb; $\sqrt{2}\cdot 2^{n/2}$ is a slightly more precise value.


RSA encryption with multiple publickeys Suppose Bob wishes to send an encrypted message $M$ to 4 people $P_1,P_2,P_3,P_4.$ Each one has their own RSA key $(N_1;e_1),(N_2;e_2),(N_3;e_3),(N_4;e_4)$.

The encrypted messages are $C_i=M^{e_i}\bmod{N_i}.$

The $e_i$ are pairwise distinct (per comment).

How to decipher the original message $M$ ?

Eureka: this looks like a variant of Håstad's broadcast attack after all. We workaround the different $e_i$ by using the Least Common Multiple of an adequate subset of the $e_i$, and can still succeed if the bit size of $M$ is low enough.

Among the 11 subsets of $\{1,2,3,4\}$ with more than 1 element, find which minimizes the quantity $\operatorname{lcm}(e_i)/\displaystyle\sum\log_2(N_i)$ where the Least Common Multiple and the sum are computed for $i$ in the subset. In the rest of this section, $i$ varies in this subset.

Compute $e=\operatorname{lcm}(e_i)$. Compute $D_i\gets C_i^{(e/e_i)}\bmod N_i$. It holds that $D_i=M^e\bmod N_i$. That allows to compute $y=M^e\bmod\left(\displaystyle\prod N_i\right)$ using the Chinese Remainder Theorem.

If we are lucky enough that $m<\left\lfloor\sqrt[e]{\displaystyle\prod N_i}\right\rfloor$ (roughly, $m$ of bit size less than $1/e$ of the sum of the sizes of the moduli in the set), then $y$ will be exactly the $e^\text{th}$ power of some integer $x$, we can get that $x$, and it will be $M$.

If not, we can try, for incremental $j$, if any if the $y_j=y+j\displaystyle\prod N_i$ is exactly an $e^\text{th}$ power; that slightly extends the attack.

If that does not work, we are left with generic attacks that do not take advantage of the operational goof of using the same $M$ for multiple recipients:

Common prime: We can compute $\gcd(N_i,N_j)$ for the 6 $(i,j)$ with $i<j$, and if any of these is not $1$, we have factored $N_i$ and $N_j$ (for two-primes RSA). With a full factorization, we can decipher the normal way. This attack has occasionally succeeded on deployed cryptosystems, an example is related there.
The $e^\text{th}$ root attack: perhaps $M$ is small enough that $M^{e_i}<N_i$ for some $i$. We can chose the $i$ with the smallest $e_i\log_2(N_i)$ and try if $\sqrt[e_i]{C_i}$ is an integer, in which case that integer is $M$. We can similarly try $\sqrt[e_i]{k\,N_i+C_i}$ for small $k$.
Search of $M$: If there's context about $M$ (like, it's a credit card number in ASCII, or a password), it might be possible to find it by enumeration. We can check a guess of $M$ with the $(C_i,N_i,e_i)$ allowing the fasted test of $C_i=M^{e_i}\bmod{N_i}$.
Meet-in-the-middle search of $M$: it is reasonably likely that $M=X\,Y$ for sizable integers $X$ and $Y$, $X<Y$, in which case there is an attack of cost $O(Y)$ with $O(X)$ memory. For the appropriate $i$ as in 3, it tabulates candidates $X^{-e_i}\,C_i\bmod{N_i}$, then searches among these candidates $Y^{e_i}\bmod{N_i}$. A match reveals $X$ and $Y$, thus $M$.
Factoring an $N_i$: if any recipient uses a key generator with a flaw, including too small an $N_i$, it might be possible to factor that $N_i$, then decipher normally.

Only attack 1 is specific to multiple keys. The others simply select the most vulnerable key.

All attacks in this answer fails for RSA as correctly practiced. 1 and 5 fail for proper key generator. Other attacks fail when what's raised to the power $e$ modulo $N$ is a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.


Adding and multiplication in jacobian coordinates How can I derive formulas for adding 2 points and multiplication by a scalar in Jacobian coordinates $(x,y) = (\frac{X}{Z^2},\frac{Y}{Z^3})$ over an elliptic curve?

Well, you can start with affine coordinate addition formulas, and simplify things as you go along. Here's an example for point doubling:

$$
\begin{eqnarray*}
\lambda &=& \frac{3(X/Z^2)^2 + A}{2(Y/Z^3)} \\
&=& \frac{3X^2 + AZ^4}{2YZ} \\
X_3 &=& \lambda^2 - 2X = \frac{9X^4 + 6AX^2Z^4 - 8XY^2Z^2 + A^2Z^8 }{4Y^2Z^2} \\
Y_3 &=& \lambda(X - X_3) - Y \\ &=& \frac{-27X^6 - 27AX^4Z^4 +36X^3Y^2Z^2 -9A^2X^2Z^8 +12AXY^2Z^6-8Y^4Z^3- A^3Z^{12}}{8Y^3Z^3} \\
Z_3 &=& 2YZ
\end{eqnarray*}
$$

Notice that $4Y^2Z^2 = (2YZ)^2$, and $8Y^3Z^3 = (2YZ)^3$, thus $Z_3 = 2YZ$. There are a lot of common terms here, so it's a relatively short computation once you combine those. The EFD website has spared us all much trouble by maintaining a record of most of the popular coordinates and worked out formulas.


CBC with a fixed or random IV I have three questions related to the use of IV within CBC mode of operation:

Why, exactly, is it so bad to have a fixed (or predictable) IV in CBC mode? An example would be great!
Given 1., why is a random IV better? And if the IV is "random", how are Alice and Bob boh supposed to know it? Isn't the IV part of the key in that case?
Why not only use the IV once (as in, keep on the CBC process forever and ever, without ever "starting again with a new IV")?

For question (1):

This page gives some hints on IVs and CBC: https://defuse.ca/cbcmodeiv.htm

I copy-paste the part about IVs "predictability"

  Chosen-Plaintext Attacks

  Randomness is not enough, though. IVs have to be unpredictable,
  too[2].

  Suppose there is a CBC-mode encryption system that selects a random
  IV, publishes it, asks the user for a one-block plaintext to encrypt,
  encrypts it with that IV, then gives the ciphertext to the user.
  Suppose Alice uses the system to encrypt two distinct messages A, and
  B, to get ciphertexts C and D. Alice gives Mallory the plaintexts and
  the ciphertexts and offers Mallory \$1000 if he can tell her which of
  the two ciphertexts is the encryption of plaintext A. If he can't, he
  has to give Alice \$1000.

  If Mallory made a random guess, he would be right with 50%
  probability, because either C corresponds to A, or D corresponds to A.
  If the system is secure, Mallory shouldn't be able to do any better
  than this.

  Mallory doesn't have to guess, though, because he can use a
  chosen-plaintext attack on the CBC-mode encryption system to figure
  out if C corresponds to A, or D corresponds to A. Mallory knows that
  the IV Alice used to encrypt A was IVA, and he knows that the input to
  the block cipher was A XOR IVA. Mallory just needs to know whether the
  block cipher encryption of A XOR IVA is C or D. Mallory asks the
  encryption system for the next IV, IVN, and sends it the plaintext A
  XOR IVA XOR IVN to encrypt. The system follows CBC mode, XORing
  Mallory's plaintext with IVN and passing the result to the block
  cipher. IVN XOR IVN is 0, so the system passes A XOR IVA to the block
  cipher, and gives Mallory the ciphertext. What Mallory gets back is
  either C or D, whichever one corresponds to plaintext A. In this case,
  Mallory gets back C, tells Alice that C corresponds to A, and wins
  $1000 with 100% probability.

  Mallory would not have been able to do this if he could not predict
  the IV, since the plaintext he sends to the system depends on the next
  IV.

For (2):

Although the IV must be unpredictable (for each key), it doesn't need to be kept safe once the ciphertext was generated. Generally it is send (prefixed) to the ciphertext. It's certainly not part of the key.

For (3):

If there are separate encryptions, then see 1. If there is just one long stream then you only need one IV.


RSA: If n=35, show that e will equal d Show that if $n = 35$ is used as an RSA modulus then the encryption exponent $e$
always equals the decryption exponent $d$?

What I have so far:

$n = 35$

Therefore $p = 5$ and $q = 7$ or vice versa, which means Euler's phi function is

$\varphi  = (5-1) \cdot (7-1) = 24$

Then to find $e$ we need the fact that $\gcd(e,\varphi) = 1$

$\gcd(e, 24) = 1$

Therefore the possible values of $e$ are only prime. $e = 5, 7, 11, 13, 17, 19, 23$

Then $d$ must follow the equation $d \equiv e^{-1} \mod \varphi$ or $(d\cdot e) \equiv 1 \mod 24$

Then I've tried for all those values which solve that equation. Why is that true? How can I explain this?

The number 24 has the curious property that, for any prime $p > 3$, $p^2 - 1$ is divisible by 24.  (In fact, this holds for any odd number $p$ not divisible by 3.)

This follows simply from the fact that $p^2 - 1 = (p-1)(p+1)$; since $p$ is not divisible by either 2 or 3,

the factors $p-1$ and $p+1$ must both be even,
one of them must be divisible by 4, and
one of them must be divisible by 3.

Thus, their product must be divisible by $2\cdot4\cdot3 = 24$.


Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG? Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?

A hash function is a "public" function. If some bad guy knows what the input might be then they are able to evaluating the hash function themselves and get the same output the good guys do. The only way that won't be a problem is if the input has really high entropy.

Insecure PRNGs only appear random to the human eye, but their output might follow enough of a pattern to make brute-force guessing of hash input possible. (Their output definitely has low entropy if their state space is low or if they're seeded with a 32 or 64-bit number.)

You can address the fact that hash functions are public by using a PRF (pseudo-random function) instead. PRFs can be built from hash functions. See the HMAC and SHAKE (SHA-3) algorithms. If the input to your PRF is non-repeating and your secret-key is not predictable then this is a secure PRNG based on the definition of a PRF.

If you do something like outputBlock = PRF(secretKey, rng.getRandom32Bits()) then the construction is not secure. Even if rng allowed you to sample from an ideal uniform random variable, this method would start repeating outputBlock(s) after around $2^{16}$ samples. (Due to the birthday problem, but even if that weren't a problem you would get repeats within $2^{32}$ blocks.

The improbable occurrence of repeated long outputBlock(s) would be a problem for meeting the requirements of a secure RNG. It might also be possible to perform a stronger attack (full state recovery) with knowledge of the insecure RNG's patterns by observing the pattern of repetitions.

However it is really easy to avoid the problem of repetition. Just use a $n$-bit counter for input and use less than $2^n$ blocks of output. A PRF, by definition, must produce output (on non-repeating input) indistinguishable from random (Even if input doesn't look random!) and, by definition, doesn't permit key recovery attacks no matter what the input is.

That gets you a secure RNG (potentially using just hash functions). But you then don't need the weak RNG.

Of course there are many faster secure PRNG algorithms out there. (Like using ChaCha20 key-stream output or the output produced by repeatedly encrypting a counter with a block cipher.) If you can use a hash and a few extra bytes of executable is acceptable then I don't see why you wouldn't want to base an RNG off of ChaCha. Hash functions implemented in software (compared to a dedicated CSPRNG algorithm) are going to be slow, require a large executable size, or both.

Large executable size meaning large for embedded systems. On a PC with GB of RAM it's neglible.


Shortcuts / practicality of brute forcing block cipher (AES) + ECB with known plaintext I know the plaintext (26 bytes long) and cryptotext of block cipher (suspected to be AES) in ECB mode. I can generate hundreds or thousands of such samples, but the samples are not arbitrary. What are my chances of recovering the crypto key using brute force methods or using brute-force + some crypto analysis?

Is there any good guidance to pull off padding oracle?

For a key recovery attack, you'd basically need to break AES itself.  There are no known practical key recovery attacks on AES (and if there were, it would not be considered safe to use), so your pretty much only hope would be to find some kind of side-channel attack on the AES implementation, or on the overall crypto framework it is part of.

Alternatively, if you suspect that the keyspace is small enough (e.g. if the key is derived from a passphrase which might not have enough entropy), you might be able to find it with a brute force attack.  The chance of such an attack succeeding depends entirely on two things: the size of the keyspace you need to test, and the speed at which you can try the keys.  The latter, in turn, depends on the computing hardware you have available (and, of course, your skill in utilizing it) and on the complexity of the key derivation process.

Padding oracle attacks, in any case, are specific to CBC mode, and do not allow key recovery.  ECB mode, while insecure in other ways, does not suffer from them.


A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function? I came up with this question while I was reading this paper: Pilaram, Hossein, and Taraneh Eghlidos. "An efficient lattice based multi-stage secret sharing scheme." IEEE Transactions on Dependable and Secure Computing 14.1 (2015): 2-8.
The theorem 1 in section 4, the author says this:
Therefore, on input $Ex$, the algorithm $\mathcal{B}$ outputs the first part of $x$, i.e. $x_1$, which contradicts with one-wayness of Ajtai's function.
I wonder if this is a correct way to prove a function satisfies one-wayness. I am a noob in cryptography, and English is not my first language. Deeply sorry for the trouble. Thanks for your time :P

If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?

That remains possible.
Simplifying the definition of a One-Way Function in Katz and Lindel's Introduction to Modern Cryptography, it's an efficiently computable function $f$ such that no algorithm $\mathcal A$ exists that, given as input $y=f(x)$ for a random $x$, outputs $x'$ with $f(x')=y$ with non-vanishing probability.
That definition is compatible with existence of an algorithm $\mathcal B$ that, given as input $y=f(x)$ for a random $x$, always outputs some segment of $x$ (e.g. it's first bit).
Illustration: assume a function $h$ that's indistinguishable from a random oracle (SHA-3 aspires to that). It's demonstrably a OWF. Construct a function $f$ with $f(x)$ the first bit of $x$ followed by $h(x)$. An algorithm $\mathcal B$ always producing the first bit of $x$ from $f(x)$ is trivial, yet an algorithm $\mathcal A$ breaking the one-wayness of $f$ can be turned into an algorithm  $\mathcal A'$ breaking the one-wayness of $h$, with at least half the success probability of $\mathcal A$.

The question's quote is in this online document. I'm ready to follow the OP that the proof made is locally wrong, but I do not exclude this can be repaired by some simple argument, on the tune of: if we can find a component $x_1$, by symmetry, we can find any $x_i$. Lattice based crypto is just too far from my comfort zone, and the time I spent on the paper too low, that I can have a useful opinion.
Note: the question mentions "14.1 (2015): 2-8", but that's incompatible with this and this stating "Volume: 14, Issue: 1, Jan.-Feb. 1 2017". Said online document is dated May 20, 2015, as well as another online version bearing "Content may change prior to final publication", thus I can't exclude the document was later revised.


Are stream ciphers no longer considered by NIST? While reading NIST SP 800-90A, "Recommendation for Random Number
Generation Using Deterministic
Random Bit Generators", I noted that no stream cipher was included among the various specified solutions.

I also noted that, at least as far as I could tell from the list of other NIST SP 800 series publications, no stream ciphers seem to be currently approved or recommended by NIST.

On the other hand, a set of stream ciphers (MUGI, SNOW 2.0, Rabbit, Decimv2, K2) appear to be currently standardized in ISO/IEC 18033-4:2011.

So my question is:

What could be the reasons for NIST to apparently ignore stream ciphers?
Is it due to the past failure of any stream ciphers to pass the NESSIE project validation, or is it simply due to reduced interest in dedicated stream ciphers, as compared to stream cipher constructions based on block ciphers (CTR / OFB mode)?

I don't know, but block-cipher based modes of operation have seen a lot more scrutiny.  AES in CTR mode has been vetted much more thoroughly than any of those stream ciphers you mention.  Moreover, those stream ciphers do not offer compelling benefits over AES-CTR mode.  Therefore, it seems to me it would be entirely reasonable to focus on block-cipher based modes of operation.


ZK proof of "element in subgroup" protocol Consider the following protocol for $P$ and $V$ :

Note: The multiplicative group is $Z_p^*$ and $p$ is prime.

Note: The protocol is for proving that $x \in \langle \alpha \rangle$.

Input to $P$ and $V$ : a prime $p$ and $\alpha, x \in Z_p^∗, k = \log_2(p)$.

Input to $P$ : $y$, so that $\alpha^y = x \bmod p$.

Protocol:

$V$ checks that $\gcd(x, p) = \gcd(\alpha, p) = 1$ and rejects if this is not the case.

$P$ chooses $r$ at random in $[0, p - 2]$, and sends $a = \alpha^r \bmod p$ to $V$.

$V$ chooses $b$ at random in $\{0, 1\}$ and sends $b$ to $P$.

$P$ sends $z = (r + by) \bmod (p-1)$ to $V$.

$V$ checks that $\alpha^z = ax^b \bmod p$. If OK, then accept, otherwise reject.

Problem:

I've already proven completeness and soundness of the protocol. However, I need to prove that it is zero-knowledge.

To do this, I consider a simulator playing the role of $P$.

I know, I could use the Rewinding Lemma, so I consider a perfect honest-verifier simulator.

I try to follow the ZK proof of the graph isomorphism protocol, however, I'm stuck.

I don't know how to respond if $b=1$, since I cannot assume the simulator knows $y$. The $b=0$ case is easy.

Can someone help me out?

The simulator does not know $y$, but he does know $x$, and knows in advance which $b$ the verifier will pick. You already know the simulation when $b=0$. In the other case, when the simulator knows that the verifier will ask $b=1$, the simulator chooses $r$ at random and sends $a = \alpha^r/x$ instead of $\alpha^r$ to the verifier. Then, the simulator sends $z = r$. You can easily see that the check will pass: $\alpha^z = \alpha^r = (\alpha^r/x)\cdot x = ax = ax^b$.

EDIT: to complete a bit, the protocol you gave is honest-verifier zero-knowledge, which means that it is zero-knowledge as long as the verifier does not deviate from the specification. In this case, as the simulator is given the random tape of the verifier as input, he knows which $b$ the verifier will choose in advance.

If you want to handle a malicious verifier, to get a fully zero-knowledge protocol, the protocol must be modified, e.g. by asking the verifier to commit to his challenge before the start of the protocol (if you want more details on this point, feel free to ask).


Hash algorithm for user accounts passwords in macOS 10.12, 10.13, 10.14 I study this article: How to Hack a Mac Password Without Changing It
and get interested in what hash algorithm is used for hashing user accounts passwords in macOS 10.12+?

My hypothesis is that it is PBKDF-SHA512.

As @kelalaka said, the answer is still valid as described in this question, so a PBKDF2-SHA512 hash with a large salt and iteration count in the 100000's, usually.


Necessity of changing $p$ and $q$ when your private key is exposed? Suppose your private key $d_1$ has been exposed. Instead of changing $p$ and $q$, instead you just choose a new public and private key (say $e_2$ and $d_2$) and use these instead. What kinds of attacks could someone perform knowing $N,e_1,e_2,d_1$ (where $e_1$ is the first public key)?

If you know even a single key pair $(e,d)$, then you can factor $N$, so that's pretty much the ultimate attack — efficient, total key recovery. For a short, digestible proof of this, see the last fact on page three of Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem.


Can a one-way accumulator be used in place of a digital signature? Could a one-way accumulator be used in a manner to replace a digital signature? Can it provide a way to:

verify that the data has not been tampered with, and
verify that the message is in fact sent/signed by the one who claims to have?

This paper discusses it, but can it safely and effectively replace DS?

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

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

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

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

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

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


Speck32 with low-entropy messages I'm using Speck 32 to encode a very low-entroy set of bits (so that the messages stay very short)

It encodes two numbers:

w: 16 bits: but in most circumstances the message is one of only 10-100 possibilities (~3-7 bits)
v: 8 bits, but in most circumstances the message is only about 4 bits

In my current scheme, I use random (throw-away) content for the last 8 bits. My questions are as follows, assuming a message set in the low thousands (I.e. an attacker would have access to ~4000 encrypted messages):

Even with the low entropy, are the messages individually secure (i.e. the compromise of some doesn't undermine the security of the others)?
Can successful guessing/statistics across a large enough set of messages compromise the key?
There's a temptation to use the last 8 bits for a MAC and/or CRC, but I fear that would make statistical attacks even better. Is that fear warranted?

If I hear you correctly, you are trying to solve the problem of securely transporting $w$ and $v$ values, under the constraint of minimizing the ciphertext size.

So, what you're doing is taking the $w$ and $v$ values, selecting a random $r$ value, concatinating them into a 32 bit block, and then sending that block through Speck32 (with some key with unspecified derivation), and that's you're ciphertext.

With that procedure, I see these possible attacks:

Someone brute forces the key; Speck32 has a 64 bit key.  While brute-forcing the key would be beyond the capability of a random hacker, it would be within the capabilities of a determined large organization.  If your threat model requires you to be secure against such large adversaries, it's not good enough.
Someone recovers the key in another way.  You don't say how you keys are exchanges, but if (for example) you have a global key that everyone uses, then if someone breaks in one device, and grabs the key, then he has everyone's keys.
Looking for repeated values.  If someone sees the same ciphertext twice, then he knows the $w$ and $v$ values are repeated (and $r$, but he doesn't care about that).  Assuming that $r$ is generated randomly, then you are likely to see a repeat after perhaps 16 repeats of $w, v$ values.
Modifying the ciphertext block; if the attacker is able to modify the ciphertext, he can modify it to a value to a value he hasn't seen (which would cause the decrypted $w, v$ values to be effectively random).  Alternatively, he could modify it to be a ciphertext he has seen before (in which case, the decrypted $w, v$ values will be what we sent before.

So, to answer your questions:

  Even with the low entropy, are the messages individually secure (i.e. the compromise of some doesn't undermine the security of the others)?

Well, assuming that the attacker can't do a key recovery attack, then the best he can do is look for repeated values.  If he does see a repeat, and he knows the value in one case, he obviously knows the value in the other.  This doesn't tell him anything about any other ciphertext.

  Can successful guessing/statistics across a large enough set of messages compromise the key?

No, it doesn't help the attacker.  If he has the resources, he can perform the brute force attack on a handful of messages (assuming he can recognize plausible $w, v$ values); more ciphertexts doesn't help him.

  There's a temptation to use the last 8 bits for a MAC and/or CRC, but I fear that would make statistical attacks even better. Is that fear warranted?

Well, if you have a fixed value there (dependent on $w, v$), that increases the probability of a repeated ciphertext.  Also, if you go with using $r$ as the authentication, I wouldn't bother doing a CRC or a MAC on $w, v$; those are already stirred into the ciphertext.  What I would do is either use fixed bits (say, 0; those are easy to generate/verify, and is no less secure than a function of $w, v$), or if you want to add some protection against copy/paste attacks, make $r$ a function of the ciphertext context (e.g. a function of the message sequence number), and have the decryptor check it.  Now, it's not great (a random change would still have a 1/256 chance of being accepted), but it's better than nothing).

Some final comments:

One thing you need to worry about is key distribution; that's quite often the Achilles heel of crypto systems.  The best crypto system doesn't help if you make it easy for the attacker to learn the keys
Might I suggest you consider using Speck48?  Not only does it allow larger keys (making brute force attacks considerably harder), but it allows the $r$ value to be 16 bits larger; if you select $r$ randomly, this means that practically speaking repeated ciphertexts won't happen; if you select $r$ as a function of the message context, that means that a change will have a very good probability of being detected.  Of course, that means that you'll have 16 more bits to transmit; you'll need to decide whether that's a viable option.


What is the exact meaning of the public key cryptosystem properties in New Directions In Cryptography by Diffie and Hellman I'm quite new to cryptography and don't have much mathematical knowledge. I'm studying cryptography, especially public key algorithms. I have some basic knowledge of public key algorithms so I know how the RSA algorithm works. But I found lots of things I don't understand while reading New Directions In Cryptography by Diffie and Hellman.
In section III. PUBLIC KEY CRYPTOGRAPHY in the paper, they defined four properties of a public key cryptosystem which are as follows.

A public key cryptosystem is a pair of families {EK}K∈{K} and {DK}K∈{K} algorithms representing invertible transformations,
EK:{M} → {M}
DK:{M} → {M}
on a finite message space {M}, such that

for every K ∈ {K}, EK is the inverse of DK,
for every K ∈ {K} and M ∈ {M}, the algorithms EK and DK are easy to compute,
for almost every K ∈ {K}, each easily computed algorithm equivalent to DK is computationally infeasible to derive from EK,
for every K ∈ {K}, it is feasible to compute inverse pairs EK and DK from K.

What I understood is as follows.

EK is a public key and DK is a private key,
therefore EK is the inverse of DK.

EK and DK are easy to compute, so they can be computed in polynomial time.

DK should be computationally infeasible to derive from EK, such that it is not possible to derive DK(a private key) from EK(a public key) in polynomial time.

It is easy to compute pairs of a public key and a private key from K.

Here is what I don't understand.

What is the K? From what I understand, the K is like p and q in RSA? Because we choose prime numbers p and q first, and then we choose a public key e and derive a corresponding private key d from e using (p-1)(q-1) with the euclidean algorithm.

Why is that in property 3, for 'almost' every K, it is computationally infeasible to derive DK from EK? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive DK from EK?

Well, it's good that you're trying to learn.  However, learning from the original seminal papers does have some issues that you need to be aware of.
For one, sometimes the original authors did not anticipate some issues that later contributions found (and for which common practice adjusted for).
For example, it is now recognized that public key encryption needs to be randomized; that is, it isn't in general secure to have a deterministic function $\text{Encrypt}(E_k, M)$.  After all, if an adversary obtains $\text{Encrypt}(E_k, M)$ and has a guess of the message $M'$, he can determine whether $M = M'$ by computing $\text{Encrypt}(E_k, M')$ (and seeing if that matches the ciphertext he has seen).  Because of this, we always use a randomized encryption function $\text{Encrypt}(E_k, M, r)$ (where $r$ is a random input), with the property that $\text{Decrypt}(D_k, \text{Encrypt}(E_k, M, r)) = M$, for (almost) all $M, r$ (the "almost" is there because we've found some methods that do have a small probability of decryption failure).
The other thing that feels like it needs to be called out (even though it has little to do with your actual question) is signatures - Diffie and Hellman mention signatures in the context of trap door one way functions.  It turns that that we have a variety of public key signature methods which are not based on trap door one way functions.
BTW: I'm not criticizing either Diffie or Hellman for not anticipating all possible issues - their work was truly groundbreaking.  However, quite a lot of thought has been put into extending this work; it is not surprising that some people found things that were originally missed.
That being said, here are answers to your questions:

What is the K? From what I understand, the K is like p and q in RSA? Because we choose prime numbers p and q first, and then we choose a public key e and derive a corresponding private key d from e using (p-1)(q-1) with the euclidean algorithm.

Well, no.  For any public key cryptosystem, there is a randomized process which generates the public key and the private key.  This randomized process can be modeled as being based on some 'seed' or 'random coin flips' (more modern terminology is, in fact, 'random coins').  The value K is this seed.
Diffie and Hellman reference this process when they write:
     In practice, the cryptoequipment must contain a true random number generator
     (e.g., a noisy diode) for generating K, together with an algorithm for generating
     the EK ~- n, pair from its outputs.

Later works have the cryptosystems specifically call out this algorithm as the 'key generation' (Gen) algorithm as one of the algorithms that define the cryptosystem, and assume that the true random number generator output is something generated outside the cryptosystem as an explicit input to the Gen algorithm.
For RSA, what we typically do is take this seed K, and use it to select the random primes p and q (and possibly e; the details depend on the exact algorithm used). The p and q values are really part of the private key and not the original seed.

Why is that in property 3, for 'almost' every K, it is computationally infeasible to derive DK from EK? What is the exact meaning of for 'almost' every K? There could be an exception where it is feasible to derive DK from EK?

Well, one issue that cannot be avoided is if the attacker took a guess to the original seed value K', and then fed that into the key generation process (which is public).  If his guess is correct, then that'd generate the exact same public key value $E_k$, and so he'd know his guess was correct (and he'd also get the private key value $D_k$, allowing him to decrypt.  This cannot be avoided, and so they need to put in this cavaet about this unavoidable attack (and possibly similar ones as well).  Actually, for most public key cryptosystems (no exception comes immediately to mind), there are better attacks than just guessing K; however that attack is still present.


Defence against timing attacks I know this is a difficult subject but would a good defense against timing attacks be not sending a message if the decryption or authentication fails? So if the attacker provides a wrong HMAC for example and this is compared and found to be false you simply return nothing to the attacker (this is considering a network environment though i do not want to limit it to a network environment)

Are there other ways to defend against timing attacks? I've found papers like this and this the 2nd one seems to be a proposal to change AES to help it prevent feasibility of timing attacks, I don't think i should just go ahead and implement it my self.

All these papers are great but they are such a long read and to be honest sometimes they just loose me. So are there any real life implementation examples against timing attacks? I'd prefer these examples to work on any cipher but cipher specific would be good as well.

I should note I've found some answers on this topic: like this one aes-timing-attacks but again the answer (as it is everywhere) is: take the worst possible time and make it last that long. this, for implementations, just isn't a feasible way to go is it?

TL;DR

is simply not returning a message when something failed to decrypt or authenticate a viable option?
are there other good implementations against timing attacks.

No, because timing attacks don't really have anything to do with errors. A timing attack means analyzing the time it takes a cryptographic operation to complete leaks secret information. That actually has nothing to do with error messages; it's just as much a timing attack to look at how long it takes the server to decrypt something in a CTR mode (where the AES primitive is run on publicly known plaintext with a secret key) by measuring delay between messages, to get information about the key. On the flipside, there are very good reasons to return an error if something goes wrong -- it means the message needs to be re-sent, because you don't know if it was corrupted in transit or if there was a problem with the message itself.

Now, there are attacks that have to do with being able to learn that there was an error in the message; the POODLE attack against TLS was one such attack, where learning that the padding was bad told the attacker valuable information about the plaintext. That may be what you're thinking about in terms of error messages, and one part of a remedy may be to not send detailed error messages (the real remedy is to use a message integrity mechanism to protect the plaintext, so an attacker can't pull a chosen-ciphertext attack). But timing attacks have little to do with this.

The way to defend against timing attacks is to make sure the time taken to execute cryptographic operations does not depend on any secret information. It can depend on key length or message length, because that's not generally considered secret; it must not depend on the actual value of the key, or the contents of the message. This is more complicated than just doing constant-time compares and the like; you also need to worry about other factors (like caching) that you don't directly control but nevertheless affect the time to run the operation (this is one of the advantages of direct hardware implementation of crypto: it's easier to control timing when you have the total control over execution that only Intel or AMD engineers have).


Python hash code returns wrong result? For a school project, I'm trying to demonstrate a hash collision using Python.
This is the little piece of code that I'm trying to use (based on this answer):

from hashlib import md5
from binascii import hexlify

s1 = b'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70'

h1 = md5(hexlify(s1))
print(h1.hexdigest())

This, however returns a completely wrong md5 hash of 9fe9cb63decce991b7783d9b783ee73f (expected: 79054025255fb1a26e4bc422aef54eb4).

My question is, what causes this error and how can I solve this?

It was (like @mikeazo) said an encoding issue.
See the answer linked in the OP for an updated answer from @mikeazo.

This is what the code became:

from hashlib import md5

s1 = 'd131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70'

h1 = md5(bytes.fromhex(s1))
print(h1.hexdigest())


How does Permutation and Substitution work? I'm a little confused on how permutation and substitution works, I've been reading about S-DES and how it goes through P-Boxes and S-Boxes but what goes on inside P or S in the algorithm?

Are these p and B boxes generated from the key?

If for example I have some plaintext of 11010011011110100001 and want to permute or substitute it, what process would I follow? - Preferably by hand so I can understand it...

The concepts here are diffusion and confusion, the goal of diffusion is to spread the influence of one bit over all bits. The job of confusion is to obscure the relationship between input and output.

S-boxes confuse (transform series of bits into different bits), P-boxes diffuse (shuffle bits around).

S-boxes need to have certain properties to be secure, they need to be non-linear to a degree where they can't even be linearly approximated. Given any two possible inputs into the box the difference in input must not correlate with difference in output.

Consider some input going into some number of S-boxes, it has changed drastically. But now consider that input being mixed (XOR) with the key before going to the box, it now changed in a very different way. If all you do is shuffle your entire function is linear and you can just build a matrix to represent it, then it's broken trivially.

In practice you apply shuffling and S-boxes multiple times (rounds) with multiple keys (derived from a master key).


Collusion Attack CP-ABE Suppose that there are Alice with attributes $A$ and $C$ and Bob with  attributes $B$ and $D$. I have a ciphertext with this policy: $A\ \operatorname{AND}\ B$.

Why don't users collude ? If Alice sends the attribute $A$ to Bob, he could regenerate private key and decrypt the document. Why is this not possible ? I don't understand this concept (I'm reading Security intuition in Ciphertext-Policy Attribute-Based Encryption).

Collusions are not possible here since each user's private keys are randomized. As you can see in the Key Generation function, for each user a random value $r$ is generated and embedded into all his private keys. Therefore, if you try to use private keys from different users, you will not be using the same random $r$ during the decryption process, so it will fail.


Why does Fortuna RNG use double SHA-256? In the paper for Fortuna the authors say that you can use any good digest algorithm (obviously as long as its output is 256 bit) and then they recommend double SHA-256.

Why? What's the benefit? What happens if I use single SHA-256 or RIPEMD-256, for example?

Ferguson and Schneier define SHAd-256 in their book Practical Cryptography in Chapter 6.3.1 Length Extensions.

  For any hash function SHA-X, where X is 1, 256, 384 or 512 we define SHAd-X as the function that maps m to SHA-X(SHA-X(m)). In particular, SHAd-256 is just the function m ↦ SHA-256(SHA-256(m)).

They clearly defined SHAd-256 to prevent length extension attacks.

I don't know why Ferguson and Schneier also used SHAd-256 when they designed Fortuna, but I assume that they preferred a hash function invulnerable to length extensions over a vulnerable one even if it might not matter for a particular use.


In practice, how many algorithms depend on the totient function? I am somewhat familiar with the RSA algorithm, and I know that the security comes from the fact that the totient $\phi(m)$ is difficult to compute when $m$ is large and of unknown factorisation. I have more or less assumed that something like this lies at the base for most modern public-key encryption, but how widespread in the real world are public key encryption schemes (including RSA) for which "finding $\phi(m)$ from $m$" is the main bottleneck for a brute-force attack?

I'm not asking how many such schemes there are out there that people have invented (although I actually only know of RSA, so if someone were to, say, drop the names of one or three others, that would be cool), but rather, in a sense, what qualification can I use when I say "_____ of modern public key encryption hinges on the fact that $\phi(m)$ is hard to compute" to laypeople, for instance in a high school math class where we take a day off from the usual curriculum. Can I say "Almost all of modern encryption", or "Most" or do I have to moderate it to "A lot", or even just "Some"?

I know that the security comes from the fact that the totient $\phi(n)$ is difficult to compute

Actually, we don't know that.  We know that if we can recover $\phi(n)$, we can decrypt an RSA encrypted message (given the public key), but we don't know how to go the other way; given a way to decrypt RSA encrypted message (given the ciphertext and the public key), how we might recover $\phi(n)$.  Decrypting RSA messages might be easier than recovering $\phi(n)$.

However, to address your question "what public key algorithms assume that recovering $\phi(n)$ is hard", well, recovering $\phi(n)$ is equivalent to factoring $n$ (in the sense that if you can solve one of them, you can immediately solve the other".  Hence, what you're looking for are public encryption methods that assume that factorization is difficult; I believe that list would be RSA, Rabin and Paillier (which is a public key encryption scheme with some additional homomorphic properties that can be useful at time).


Hill cipher: How to find an unknown key of unknown size How would you tackle the problem of finding the key (you don't know the length) to a Hill cipher when knowing only one 12-letter word of plaintext and its corresponding ciphertext?

CONVERSATION has been encoded as SQZHUSSUDYKP with standard alphabet (A=0, Z=25). The key, as I said, is unknown with unknown size.

I am not asking for a solution, but for tips and guidance. Any help will be much appreciated.

Assuming that $2\times2$ matrix is used, and the encryption starts from the first letter of the plaintext, the key can be found by just calculating the "encryption" with size of $4$ plain- and cryptotext block.

For example, for CONV $\rightarrow$ SQZH, it would go as follows:
$$\begin{pmatrix}
2 & 14 \\
13 & 21
\end{pmatrix}\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}=
\begin{pmatrix}
18 & 16 \\
25 & 7
\end{pmatrix}\pmod{26}$$

Then solving for $a,b,c,d$, the key $K$ is found.
As here the plaintext matrix is invertible, one can compute

$$\begin{pmatrix}
a & b \\
c & d
\end{pmatrix}=\begin{pmatrix}
2 & 14 \\
13 & 21
\end{pmatrix}^{-1}
\begin{pmatrix}
18 & 16 \\
25 & 7
\end{pmatrix}\pmod{26}$$


Why is $e=0$ allowed in Schnorr signatures? In a Schnorr signature (Wikipedia style), we have:

$R = kG$, where $0<k<n$ is a nonce and $G$ is the generator point.
$e = H(R \| M) \bmod n$, where $H()$ is a hashing function and $M$ is the message.
Finally $s = k - xe \bmod n$, where $x$ is the private key. The signature is then either $(R,s)$ or $(e,s)$ depending on convention.
Verifiers check that $R = sG + eP$, where $P = xG$ is the public key.

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed?

The only answer I can find to this is that breaking the hash function to obtain $e=0$ should generally have twice the security level (in bits) of that required to directly break the public key. And, it is most convenient to skip the extra steps of checking zero-ness of $e$, so for practical reasons the case of $e=0$ is glossed over.

Strangely, if $e=0$ then no knowledge of $x$ is proven, as all steps can be carried out by someone who knows only $M$. So, why is $e=0$ not disallowed?

Because $e = 0$ is not unique in this regard. Every single $e$ is equally "insecure", i.e. you may as well ban $e = 23$ with the same reasoning.

To exemplify, assume $e = 23$ arbitrarily (holds for any value of $e$ with the same reasoning). For that $e$, I can easily compute a signature by choosing a random scalar $0 \leq s < n$ and computing $R = sG+eP$. By definition, $(R,s)$ is a valid signature.
For $e = 0$, this is probably the attack you had in mind.

Of course, in reality this attack is not going to be successful because if I try to choose $R$ "cleverly" for a specific $e$, with overwhelming probability this is not going to be the $e$ with $e = H(R||M)$ (assuming the hash function is good). The trick here is that $e$ is only fixed after $R$ is already chosen, which makes it secure.

There is a deeper reason behind all this linked to the security proof, which does not at all care about any $e$. I'm not doing the proof justice with the following sketch, but very, very, very roughly, the reduction runs the attacker twice: once with $e$ and once with some other hash value $e'\neq e$ (modeling $H$ as a random oracle). The reduction only requires $e - e' \neq 0$ (which is the actual "weak spot 0", but it only occurs in the security proof) to compute the signature's secret key given a successful attacker. If you are interested, I recommend a look into Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures.


Deriving HMAC key and cipher key from passphrase? I'm encrypting a file with AES-256 in CBC mode. I needed to add an HMAC for authentication and validation of the file contents and passphrase, so I used a SHA-256 HMAC over chunks of my file cumulatively.

My main question is how to derive both an HMAC key and my AES key from an input passphrase. I'm currently taking the SHA-512 hash of the input passphrase, passing that to bcrypt/PBKDF2 with a salt and high rounds, and then using the SHA-256 hash to supply my AES cipher password. For deriving an HMAC key in addition to my cipher key, I was thinking of doing one of the following things:

SHA-512 the output from the strong hash method and split the result in half, using the first half as the cipher passphrase and the second half as the HMAC passphrase.
Store an additional salt in my header, and after generating the passphrase using SHA-256 after the strong hash, run the result through SHA-256 again with the salt for the HMAC passphrase.
Same as #2, but without a salt.

Which of these ways is the best way to generate a HMAC password in addition to my cipher password from the same input passphrase?

If you are doing authenticated encryption with an AES and HMAC combination, the security of your scheme depends on the key for encryption and the key for message authentication being independent. The general idea is that you might generate two independent keys from a single master key, by proper usage of a $PRF$. The most performance effective solution is therefore to modify your first suggestion in either of two ways:

Let $K$ be the output from the PBKDF2.

Alt 1. Derive the encryption key $K_e$ and authentication key $K_a$ using one call each to
$K_n = PRF_K(label_n)$. The input $label_n$ might e.g. be the single char "e" and "a" respectively.
Alt 2. Derive $K' = K_e||K_a$ using a single call to $PRF_K$ to generate a 512 bit derived key.

Please note SHA-512 is not a pseudo random function, but might be used to create one. For instance, you could use HMAC-SHA-512 as your PRF.


LWE: does using only a small subspace of the plaintext space influence the security of the encryption scheme? Regarding LWE schemes where the encryption is performed this way:

for $m \in \mathbb{Z}_t$, compute $c = LWE_{\mathbf{s}}^{t/q}(m) = \{ \mathbf{a}, \mathbf{a \cdot s} + m\cdot q/t + e\} \in \mathbb{Z}_{q}^{n}$

(where $\mathbf{s}$ is the secret vector of length $n$, $\mathbf{a}$ is a random vector and $e$ is some noise generated by a discrete Gaussian sampler)

What happens if for a given plaintext modulus $t$, we use only a small subspace of $Z_t$ for our messages? Does it have any influence on the overall security of the scheme?

No, as long as your plaintext space is a subset of $Z_t$, then there is not any negative impact on security.

However, if you use a smaller message space $Z_x\subset Z_t$, you should consider setting the plaintext space to $Z_x$ directly as this could improve the efficiency.


Elliptic Curves and Finite Abelian Groups One can note that, given an elliptic curve mod $p$, that the set of points together with the usual addition law gives a finite Abelian group.
Now by the fundamental theorem of finite abelian groups, $$E\cong\mathbb{Z}/p_1^{a_1}\mathbb{Z}\otimes\dots\otimes\mathbb{Z}/p_k^{a_k}\mathbb{Z},$$ where $$E=\{(x,y)\in\mathbb{Z}/p\mathbb{Z} \times \mathbb{Z}/p\mathbb{Z}:y^2\equiv x^3+ax+b\}\cup\{O\}$$ and $n=p_1^{a_1}\dots p_k^{a_k}$.
Are there any cryptographic attacks on elliptic curve cryptography that utilize this decomposition? $n$ can be obtained easily enough by Schoof's algorithm.

Let $E$ be an elliptic curve over a finite field $K$ with an order $n$ such that $n =p_1^{a_1}\dots p_k^{a_k}$. The order is the number of rational points of the curve.
There are various point for a curve to be secure;

Discrete logarithm
The basic security of ECC is the Dlog that is given a base point $G$ and another point $P$ with $P= [x]G$
There are many Dlog algorithms, however, two of them are important here

Pollards' Rho and this defines the bound; that is a curve with $n$ elements the cost of Pollard's $\rho$ is $\mathcal{O}(\sqrt{n})$, therefore a curve with $n$ point cannot be secure than this.

Pohlig-Hellman is applicable if $n$ is a smooth integer. It has  $$\mathcal O\left(\sum_i {a_i(\log n+\sqrt {p_i})}\right)$$ time complexity where $\prod_i p_i^{a_i}$ is the prime factorization of group order $n$.

To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time. Or the order must have at least one large factor where DLog is hard.
If you are looking an example then this curve $E(F_p) : y^2 = x^3 + 7x + 1$ with $p = 9254331510119 $ is a concrete case for Pohlig-Hellman.

Co-factor
Co-factor $h$ is defined as $h = \#E(K)/n$. We want the cofactor small or equal to 1. If not, then;
The attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the $n$ has many small factors. Then, the attackers can use CRT to combine the results.
For each query the attacker can reveal by $[a]P$ is at most $\lceil log_2 h\rceil$ bits. To mitigate this a curve with co-factor is small or 1 or a strict point validation is required.

The above are the obvious security issues when the order is of the form $\prod_i p_i^{a_i}$ for some distinct primes $p_i$ and $a_i \in \mathbb{Z}^+$. The list, however, is not complete;

The twist security
From the factorization, one can say that our curve's one of the primes is large enough to be secure against DLog. If the attacker sends a point on the twist with low order, then can use Lim-Lee's attack to combine the results. To mitigate, a curve with a large prime factor of the twisted order is required as in Curve25519 and point validation!

And, more see in safecurves


Is a PRF applied to a secure MAC also a secure MAC? Suppose I apply a PRF to a secure MAC.  Do I still have a secure MAC?

Yes.

A secure PRF is a secure MAC. A secure MAC of a secure MAC is a secure MAC. Therefore, applying a PRF to a MAC still gives you a MAC.

Depending on the length of the inner MAC and the PRF you may lose security bits, but if they are long enough it works.


Randomizable zero-knowledge proofs? I was wondering whether there exists randomizable zero-knowledge proofs. What I mean by randomizable is that assume I have a zero-knowledge proof of knowledge $\pi$, stating that I know $x \in \mathbb{Z}_q$ for a prime $q$, such that $Q = g^x$, and I randomize $Q$ as $Q' = Q^r$ for a random $r \in \mathbb{Z}_q$. Then, I wish to prove that $Q'$ is a randomized version of $Q$. So, is it possible to somehow also randomize the proof $\pi$ into $\pi'$ for this?

Yes there are. I guess you're looking into non-interactive zero-knowledge (NIZK) proofs, since you're assuming that you have at hand a proof $\pi$. A common approach for building NIZKs in crypto is to rely on the Groth-Sahai methodology, which produces highly structured NIZKs using elliptic curves equipped with a bilinear maps. It was first observed in this paper that Groth-Sahai proofs can be randomized - i.e.,  you can randomize a statement together with its proof so that the randomized proof is indistinguishable from an honest proof computed on the randomized statement. This was used to build anonymous credentials with strong properties, and had many other applications in subsequent works.


Second challenge in Fiat-Shamir for 5-round schemes I'm not sure how to compute the second challenge when applying FS to a 5-round protocol. I've seen TWO different formulas (with and without including the first challenge) and don't know which one is correct.

Suppose we have 5-round interactive protocol for some statement $st$:

$P$ → $V$: $x$ means prover sent $x$ to verifier.

$P$ ← $V$: $y$ means verifier sent $y$ to prover.

$P$ → $V$: $\alpha_1$ // 1st commitment
$P$ ← $V$: $ch_1$  // 1st challenge
$P$ → $V$: $\alpha_2$  // 1st answer
$P$ ← $V$: $ch_2$ // 2nd challenge
$P$ → $V$: $\alpha_3$ // 2nd answer

Now we can apply Fiat-Shamir transform to get a non-interactive proof.

Question: how we compute $ch_2$?:

a) $ch_2 = Hash(st|\alpha_1|\alpha_2|aux)$

b) $ch_2 = Hash(st|\alpha_1|\alpha_2|ch_1| aux)$ ← includes $ch_1$

On the one hand, $ch_2$ should be independent of $ch_1$, right? An original article of Pointcheval and Stern[2], article by Kiltz et. al[1], plus some answers here use formula a.

On the other hand, there are articles [3],[4] where the formula b is used.

UPD: Will the fact of whether $ch1$ included or not matter for the Forking Lemma?

[1] Tightly-Secure Signatures from Five-Move Identification Protocols by Eike Kiltz, Julian Loss, and Jiaxin Pan https://eprint.iacr.org/2017/870.pdf

[2] Security Arguments for Digital Signatures and Blind Signatures by David Pointcheval and Jacques Stern https://www.di.ens.fr/david.pointcheval/Documents/Papers/2000_joc.pdf

[3] From 5-pass MQ-based identification to MQ-based signatures by Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe https://eprint.iacr.org/2016/708.pdf

[4] Extended Security Arguments for Signature Schemes by Sidi Mohamed El Yousfi Alaoui, Özgür Dagdelen, Pascal Véron, DavidGalindo, Pierre-Louis Cayrel https://hal.inria.fr/hal-00684486/document

These are equivalent. Given that the first challenge is a deterministic function of the statement and $\alpha_1$, it makes no difference. What is crucial is just to include the statement, and the entire transcript to that point. (Note that anything that is deterministically dependent on other things doesn't have to be included in the transcript.)


Calculate number of chips to solve bit commitment using hash function I have a problem that I don't know how to solve

Assume that H is a cryptographic hash function with output size 80 bits. Assume that ABC123 is a specifically designed line of hardware chips for computing H. where ABC123  can create 10000 hash values a second. This product line is the best, fastest and affordable, in the market, priced at 1000$. Consider the following Bit-Commitment protocol which is used for applications in betting in football matches.

A create R1 and R2 as 2 random binary strings with length 48 bits and 40 bits, respectively
A send host B: M = H(R1 || R2 || b) || R1
To announce bit b, A send host B: (R2, b) (b is a bit, 0 or 1, that A choose indicate that a football team win or lose, for simplify)
B check validity by re-hashing H(R1 || R2 || b) and comparing with the value received from step 2

Question: how much money the host B has to invest in order to correctly guess b in 5 minutes?

Thank you very much. Any help is appreciated!

$M = H(R_1 || R_2 || b) || R_1$

You already know $R_1$ and you need to find $R_2$ and $b$.

$R_2$ is 40 bits long and $b$ is 1 bit, so you need on average $2^{41}$ guesses to find $R_2$ and $b$ which will give the hash you want.

You know that each chip can do 10,000 hashes per second, so you need to find out how many chips you'll need to do $2^{41}$ hashes in 5 minutes.

$\dfrac{2^{41}}{300seconds} = 7,330,077,518.51 hashes/second$

Since each chip can peform 10,000 hashes per second, we need

$\dfrac{7,330,077,518.51}{10000} = 733,008$ chips (rounded up)

At \$1000 per chip, that is \$733,008,000


Is the AES-GCM encryption using the SHA256 hash of the plaintext as IV secure? I want to encrypt a list of unique values and I want the property of when I encrypt the same value I get the same ciphertext (determinism). The adversary only observes the ciphertexts of a unique set of plaintext values. In this context would the following encryption algorithm be secure:

I generate the sha256 hash of the plaintext value
I use the hash as the IV to AES-GCM to encrypt the plaintext value

Is the resulting ciphertext which includes the hash of the plaintext value secure?

No, because in order to decrypt it you must pass along the SHA-256 hash too, and now you have leaked a public function of the original message, which an adversary can use to efficiently test a guess offline about what the original message was.

If you want a deterministic authenticated cipher, you might consider an existing construction like SIV that has been studied already.


Are convergently-encrypted ciphertexts safe from collision attacks? Convergent encryption uses a message digest of the plaintext as the key to encrypt the plaintext to produce the ciphertext.

This is useful for automatic content sharing because it produces a deterministic ciphertext between unrelated parties who encrypt it without revealing contents to parties who never encrypted it. Weaknesses exist, but it can be a useful thing for automatic content sharing in storage systems.

e.g.

compute SHA256 of plaintext -> KEY1

Use KEY1 to encrypt plaintext using AES256 with CBC -> ciphertext

compute SHA256 of cyphertext -> ID1

When sharing, it would be nice to avoid malicious collisions (e.g. widely distributing the funny graphic in email, identified by ID1, and converting it to something obscene in automatically-shared storage that also happens to have ID1).

The straightforward way is to make sure the hash algorithm is secure. SHA256 is reasonably secure even against collision attacks, which is a greater vulnerability than the preimage attacks.

But let's say you want to store your blocks in a medium that identifies objects by a weaker hash, such as MD5, which is vulnerable to collision attacks. In the above example, this means that ID1 is computed or verified using MD5 instead of SHA256, because it is done by the system when storing the ciphertext. Specifically AWS S3 supports MD5 on objects, specifically not
intended for security but it is there. KEY1 is still computed using SHA256 since that is not part of the object identification/verification process.

The question is, does the process of convergent encryption protect adequately against collision attacks to make them infeasible like preimage attacks of MD5?

It seems like on the one hand, producing a plaintext that after encryption with a known key collides might not be difficult because you can decrypt anything with a symmetric key.

But convergent encryption means that as you mutate your cyphertext looking for a collision changing the plaintext, the key changes as well. Colliding cyphertexts can be produced, but finding cyphertexts that can be mapped back to a plaintext whose MD used as a key produces the cyphertext during encryption seems difficult.

Is it likely that there is a practical way to compute collisions, or did the convergent encryption preprocessing make the weaker MD5 of the storage medium no longer vulnerable to collisions of content that originated as plaintext?

All I have to go on is that it boggles my mind how this collision could be computed, but this sort of instinct can be wrong, so I was wondering whether anyone else had thoughts on whether it might be achieved.

The answer should be "No. A convergently-encrypted ciphertext is not safe from collision attacks."

Just because it is encrypted convergently does not mean it is not subject to collision attacks. MD5 has 128 bits, therefore, I could expect to have to generate at worst around 2^64 attempts to crack it.

Each collision attempt is more complex to generate because of the need to generate a new key via SHA256, reencrypt, and recompute MD5. There is no need to re-SHA256 the entire plaintext each time for the key, and it is also not obvious whether or not there might be a way to exploit known weaknesses of the MD5 hash to crack it in less than 2^64 attempts, but the question as stated was whether it was safe from a collision attack, and the simple answer has to be "No".

The 2^64 worst case seems to be similar to that of the Google SHAttered SHA1 collision demonstration even if generating each attempt requires more computation for convergent encryption. "Safe" might be a relative term that I did not define. I will try to be more concise in the future. But using MD5 to guarantee non-colliding convergently-encrypted content should not pass a security review. This would be why in the SHA2 specification there is no hash with less than 224 bits, which is 96 rounds greater than MD5, a factor of 2^48 difference for collision attacks.


Tips on conceiving safe software messaging platform I have a personal project in mind in which I plan to use cryptography in order to let the users be confident in the fact that, even if all data get's stolen, it would be virtually impossible to crack in the next few decades.

I would like some advice on the way I planned it until now:

All data resides in two key/value stores:

Store 1 - contains messages:

key   : msg_id (numerical)
value : AES encrypted message with random key K1.

Store 2 - links users to messages:

key   : hash H1 of (user identification + password + X)
value : AES encrypted data containing the msg_id and key K1, encrypted with key K2 (identification + password + salt/padding)

( X increments from 1 to N, per message linked to user. I use this to create more noise, should there be an attack, and to differentiate the hash H1 with key K2).

Without any regard to the way it should work (which is quite specific): is the data contained in the two stores safe even if an attacker knows their architecture and has access to the application's source code ? They may know some user id's, but not their password.

BTW: I'm quite new to cryptography. I'm reading through the basic materials (applied cryptography by Bruce Schneier, for one), so please be indulgent.

First, as a bit of general advice: Designing a secure cryptographic system is hard. Experts with decades of experience still make mistakes. Depending on your intended audience, you may be better served by looking for an established system that meets your needs rather than trying to design an implement something from scratch.

To answer your specific question above, I would suggest that the keys of store 2 are one weak point. With a list of these keys, and one or more user IDs known, it's straightforward to implement a dictionary attack to try and discover the associated passwords. (X does nothing to help protect the passwords, because it is not random.)

Passwords are notoriously a weak point of most systems in use today, thus you might contend that this is unavoidable, but you should still strive to avoid making it easy to do an offline dictionary attack.


Reverse engineering secret key in RSA encryption with the help of signature Consider the following:

$i$th message, $m_i$, in its original state.
$i$th message, $M_i$, encrypted message $m_i$ using public key.
Public key, $p$, in a $b$-bit RSA encryption setup. We can access it at all times.
Secret key, $s$.
Signature, signed by $s$. We will denote it as $sg$.

The scenario is such that we are presented with an encrypted message $M$, the public key with which it was encrypted, and the message $m$, which has been decrypted using the secret key and returned to its original state.
We also have a signature, signed as $sg$.

I understand that given simply $m_i$, $M_i$, and $p$, it is not possible to work backwards to obtain $s$. However, would it be possible to work backwards and obtain the secret key $s$ given enough instances of corresponding messages?
Suppose we are given pairs of messages, $(m_1, M_1), (m_2, M_2), \ldots (m_n, M_n)$, then would we get anywhere nearer towards obtaining the secret key (or maybe even increase our chances for a bruteforce search) as we approach a certain $n$? In that case how high an $n$ are we talking about?

Now consider we can vary $n$ to as much as we want. $n \rightarrow \infty$ Essentially, we have been given a frontend for the RSA implementation such that we can give it a message and it will return the encrypted message to us, as many times as we want but will not reveal $s$ (obviously). In this case, will we be able to reverse engineer $s$?

I have recently got to know about asymmetric encryption and these questions are a part of understanding it better, so I would appreciate it if anyone can offer some valuable insights!

In RSA, assuming knowledge of the public key but not the private key, analyzing any number of triplets of matching message, encrypted message, and signature $(m,M,sg)$, does not help (as far as we know) towards recovering the private key $s$ (nor an equivalent). That's regardless of the sensible padding or RSA variant used (as long as neither the padding nor choice of $m$, $M$, or $sg$ directly leak information about the private key, e.g. in some supposedly truly random padding field that really is not).

In fact, the stronger hypothesis that one with knowledge of the public key also temporarily can use a black box containing the private key $s=(N,d)$ that freely allows computing the raw RSA private key function $x\to x^d\bmod N$ for any $x$ (which in turn allows decrypting or signing any message), does not (as far as we know) help in any way towards finding a private key, nor factorizing $N$, nor otherwise building a black box independent of the original one computing the raw RSA private key function $x\to x^d\bmod N$ for random $x$ with sizable odds.

There is no proof of that; proving (or disproving) it is an open research problem.

Note: as pointed in another answer, access to a "frontend for the RSA implementation such that we can give it a message and it will return the encrypted message" demonstrably does not help, for it is possible to perform the same using the public key, with cost growing slower than $O(b^3)$. However, the question mentions that we are also given some signature, and we lack a proof that this does not help.

All the attacks on RSA that we know:

decipher or sign messages without finding a private key (only if improper use of RSA is made, e.g. poor encryption or signature padding);
or find a private key from the public key (typically, by computing a private exponent from the public exponent and the factors of the public modulus $N$, recovered by factorization, because $N$ was too small or its factors improperly chosen);
or extract the/a private key using some information leak.


How do we know a single differential/linear trail dominates the others? I have read the proof of AES's resistance against differential cryptanalysis. In the proof the authors show that there is no single differential trail with prop ratio higher than $2^{-300}$ over 8 rounds. I understand that part but it does not prove that there is no differential with prop ratio higher than $2^{1-n} = 2^{-127}$ because we could end up with the same differential using many different trails. I have read in Jon Daemen's dissertation that in a well constructed cipher a single trail should dominate all the other trails. Is it proven for AES that, in fact, no different differential trails combine to give a significantly higher prop ratio of a differential? If yes, how do they prove that? If no, why is AES assumed to be proven resistant against linear and differential cryptanalysis?
Links:
The proof - https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf.
The dissertation- https://cs.ru.nl/~joan/papers/JDA_Thesis_1995.pdf

The short answer is that we don't. There are several block ciphers (most famously PRESENT) where multiple linear trails combine to form a stronger distinguisher. The collection of trails is called a linear hull. The concept has been extended to differential-linear cryptanalysis, but I don't have any reference for a "difference hull". These multiple trail effects seem to be more pronounced in lightweight designs.
The analytic approach seems to be to assume that hulls don't contribute significantly unless they can be demonstrated to do so. If the term "resistant" is used rather than "immune", then this assumption does not feel too unreasonable.


Can the confusion/diffusion of a hash algorithm be quantified? I am wondering whether the confusion and diffusion are quantified in any way when we examine hashing algorithms and, if so, how they are quantified and what units (if any) are used to represent them.

It depends a lot of why you want to do this and for what types of hashes and input data but I would think that for some purposes it may be sufficient to do so through sampling, though you would certainly want to be careful about how much you trust this sort of analysis depending on how you're using the hash values.

For example, if you know that the data you're hashing often has a certain format or is always a certain length you could generate a set of test inputs of manageable lengths. For the purposes of this answer let's say 4 bytes but in practice you'd probably want to pick an assortment of lengths that apply to your use-case.

You should include some simple values (e.g. 0x00000000, 0xFFFFFFFF), some patterned values (e.g. 0x40404040, 0x1ACEECA1), and some completely random values.  Then take each one and hash it to get a baseline, $H$, of length $N$ bits (i.e. 32).

For diffusion you could then, for each bit of the input:

Flip the bit, $i$
Hash the altered value, $H_i$ (i.e. the hash with bit $i$ flipped)
Count the number of bits that differ between the new hash and the baseline hash, $d_i$
Calculate $1 - \frac{| d_i - N/2 |}{N/2}$ to get a rating $r_i$ between 0 to 1 (with 1 being ideal diffusion).

For confusion you could do something similar, checking that across $H_0$ to $H_{N-1}$ each bit is flipped relative to the baseline due to changes in as many input bits as possible, creating a score for each output bit.

Using these diffusion and confusion scores, you could then compare hashes depending on whatever criteria you're most looking for in your use-case.

All of that said, this is a somewhat brute-force method that could very easily miss issues in a hashing algorithm that could be important from a security perspective.  So again, I would only consider using a method like this if you're considering the properties of the hash relative to a specific use-case that isn't security-critical.  Making this kind of statistical argument when you don't already have some idea what types of inputs you might be seeing reducing the likelihood that it will tell you anything useful effectively to zero.


A simple attack on DESX in time $2^{120}$ Let $\mathcal{M}$ be our message space and $\mathcal{K}$ our key space. Now, let $\mathrm{E} : \mathcal{K} \times \mathcal{M} \to \mathcal{M}$ be a block cipher. Define the block cipher $\mathrm{EX}((k_1, k_2, k_3), m) := k_1 \oplus \mathrm{E}(k_2, m \oplus k_3)$, where $m \in \mathcal{M}$, $k_2 \in \mathcal{K}$, and $k_1$ and $k_3$ are of the same length as the message (I suppose I could write $k_1, k_3 \in \mathcal{M}$).

In the case of DES, we get DESX, giving us a total key size of $64 + 56 + 64 = 184$ bits.

At the end of this lecture (as well as what can be inferred from the Wikipedia entry), prof. Dan Boneh mentions that there is a simple attack on all block ciphers of the form $\mathrm{EX}$ in time $|\mathcal{K}| \cdot |\mathcal{M}|$, meaning a simple attack on DESX in time $2^{120}$.

I finished the course during this summer and generally had no problems, but could not figure this attack out for DESX / the general case. Can anyone explain to me what it is?

It is vulnerable to a sort of meet-in-the-middle attack since you don't really have to brute force $k_1$.  Given a plaintext-ciphertext pair, $P$ and $C$, you can calculate $C' = E(k_2', P \oplus k_3')$ for candidate values $k_2'$ and $k_3'$.  Then, you can determine $k_1' = C' \oplus C$.  So, you only need to brute force the two keys $k_2$ and $k_3$, making the complexity $2^{|\mathcal{K}\cdot\mathcal{M}|}$.

Equivalently, you could attack it from the other side by trying all possible values for $k_1$ and $k_2$, decrypting $C$, and using XOR with the plaintext to determine $k_3$.


RLWE decision to search: probability that oracle work on all automorphic images After watching this talk https://www.youtube.com/watch?v=Eg_pyyeT_Qc&feature=plcp, I tried to formalize the presented search-to-decision reduction for Ring LWE, but got stuck at one point.

I understand how we can construct an algorithm that finds the k-th coefficient of the secret (in "Chinese remainder representation", so really $s(\zeta^k)$ with a root of unity $\zeta^k$) for a given k. To do that, we use an oracle that can distinguish between real RLWE samples and uniform ones. As far as I know, this "distinguishing" means that $Pr[O(f, fs + e)] - Pr[O(f, U)]$ is non-negligible, where $f, U, s$ are uniformly distributed random variables on $R_q$. But this would mean, that the oracle and therefore our algorithm* is only guaranteed to find $s(\zeta^k)$ for a non-negligible fraction of all inputs. Using the average-to-worst case reduction, we can make it work for all $s$, but not necessarily for all $f$, so our algorithm may only work on samples $(f, fs + e)$ where $f$ is in some not-too-small set $S$.

My question is now: Is my understanding so far correct, and if it is, how can the automorphism idea (to find the other coefficients) work? If $\sigma$ is a field automorphism that can preserves the error distribution, we know that $(\sigma(f), \sigma(fs + e))$ is also a valid RLWE sample, but it is not guaranteed that the algorithm will work correctly on this sample (it only has to work on a non-negligible fraction of all $f$s). Since $(\sigma(f), \sigma(fs + e))$ and $(f, fs + e)$ are not independent either, the algorithm does not have to work with relatively high probability.

In other words: Why is it impossible, that the assumed oracle distinguishes real RLWE samples $(f, fs+e)$ and uniform samples perfectly for half the $f$ and accepts with probability $0.5$ in the other cases* in such a way that for every $f$ there are automorphisms $\sigma$ (preserving the error distribution) so that the oracle does not work on $(\sigma(f), \sigma(fs + e))$?

I also had a look at this paper (I think the proof has been published there originally) http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.400.7900&rep=rep1&type=pdf, but I did not find details on this question.

(*of course, the oracle is not invoked on $(f, fs + e)$ but rather on $(f + v, fs + e + vk)$, but this should not fundamentally change things)

If my problem is unclear or not formal enough, please tell me. I did not include my complete current proof part as this question is already quite long.

(The full version of the paper is at https://eprint.iacr.org/2012/230, and my answer below refers to it.)

The answer to your question is that a different part of the reduction ensures that the oracle has advantage very close to 1 over the random samples $(a_i, a_i s + e_i + r_i)$, i.e., the oracle outputs the correct answer for almost all choices of $s, a_i, e_i, r_i$. With this guarantee, Lemmas 5.5 and 5.9 give a reduction that solves the search problem using the automorphisms and the "guess and check" technique.

The other part of reduction to which I refer is described in Section 5.2, on "worst-case to average-case decision" (Lemma 5.12). This uses a pretty standard "amplification" technique to improve the oracle's distinguishing advantage, by repeatedly invoking it on independent samples and measuring how often it accepts.