Perfect shuffle possible with limited raw entropy? I am trying to shuffle a standard 52-card deck in a perfect way (every outcome should be possible at an equal chance). I am not, at this point, concerned with cryptanalysis attacks against it.

I have run into some problems/questions that are probably answered in cryptographic theory:

Most PRNGs run off some sort of internal state. A deck of cards has 52! shuffles, which is a 220+ bit number. Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160-bit internal state? My intuition says no. Even though to shuffle the deck I only need 52 small random integers, a PRNG with internal state size below 52! probably cannot generate all the different 52 number sequences needed. Is this true or am I completely wrong?
In case I am right above, does that mean I cannot generate a true shuffle in most modern programming languages? Java's SecureRandom only has 128bit internal state and even /dev/rand uses a SHA-1 based PRNG on MacOS (160bits), so even using the "golden standard" cryptographic random source it isn't going to be enough. What are my options? What about JavaScript.. what are my options in the browser?
The option I came up with is to use CPU's built-in RDSEED command to get 256 bits of a really random seed, then I would like to use a PRNG with 256 bit internal state to shuffle the cards. Is that a sensible choice? What's the simplest way? Some sort of SHA-256 hash-based PRNG?

Is it possible to generate all shuffles with a PRNG that has 64, 128 or 160 bit internal state?

No, for restriction of "possible .. with" to a deterministic procedure using the Pseudo RNG output as sole input, and:

Bound to output a single shuffled sequence per run. To generate all shuffles, $\lceil\log_2(52!)\rceil=226$ bits of PRNG internal state are required.
Or bound to use strictly less than $\lceil\log_2(52!)\rceil-160=66$ bits of memory between output of shuffles (for appropriate account of memory).

This is proven by counting the possible states of the deterministic system consisting of the PRNG plus device running the shuffling procedure.

  Does that mean I cannot generate a true shuffle in most modern programming languages?

No. It means that a single instance of a built-in PRNG with that 160-bit limitation can't be used, should we require that the shuffle generated could be any of the $52!$ shuffles, say because such claim was made. If we used such PRNG, irrespective of how it was seeded and security, it could be rationally proven such claim is untrue. But, for a secure and properly seeded PRNG and shuffling procedure, such proof can't be by examination of the shuffles produced (even with a 128-bit internal PRNG state). The proof must rely on the design characteristics of the PRNG. That could be the case in a code audit.

The difficult problem is not making a PRNG with a large state (virtually all modern languages allow to build one). The problem is seeding it with enough entropy. This is not always possible, much less built "in" the programming language¹. However, many modern programming languages (most if you weight in how commonly used/taught they are) come with libraries or allow using external libraries/services which often conveniently provide entropy without a size limitation, and at a rate way more than sufficient for the application.

For example, on a Unix system, a language allowing file I/O often can read /dev/random, which promises to provide true randomness and pause towards that goal if necessary. Using that should be OK, but historically, it has not always. There are anecdotes of embedded devices which generate a key on first boot and end up with a guessable key.

  Java's SecureRandom only has 128bit internal state

That's a dubious assertion. Things depend both on how SecureRandom is used², and on the environment.

  even /dev/rand uses a SHA-1 based PRNG on MacOS (160bits)

As long as /dev/random appropriately re-seeds itself using true entropy, being based on a 160-bit hash or even having a 160-bit state does not imply the (theoretical anyway) limitation of being a PRNG with a 160-bit state. This generator promises to reseed with fresh entropy as needed, and wait when it lacks entropy. It is not (or not supposed to be) a PRNG, that is deterministic after seeding. From this standpoint, /dev/random gives a stronger insurance than /dev/urandom.

  Even using the "golden standard" cryptographic random source it isn't going to be enough. What are my options?

When a paranoia damper is needed (e.g. to convince a gambler who does not trust that $2^{128}$ is large enough), or in order to formally fulfill a promise that all $52!$ possible shuffles can be generated with (nearly) equal probability, the recommendable way is to combine using XOR [or using modular addition modulo $n$ for a primitive that generates a random integer in $[0,n)$ ]:

The output of the "golden standard" cryptographic random source
The output of a custom RNG that is in no way influenced by 1.

With a flawless implementation of that, the resulting RNG is at least as good as the best of the two. This architecture minimizes the (still very practically real) probability that trying to improve on 1 leads to a disaster. Additionally, 1 should be carefully checked to be a Cryptographically Secure True RNG, or a Cryptographically Secure Pseudo RNG seeded from a TRNG with enough entropy.

Now comes the problem of making the custom RNG 2. One possibility if to make a CSPRNG with a 512-bit state initialized as the SHA-512 hash of multiple sources:

The CPU's built in RDSEED, if there is such thing available in the programming environment, in which case that's a sensible choice as an extra entropy source. Same for RDRAND.
Current time to the highest accuracy available, perhaps at different moments in the execution. Same for the job's CPU usage.
The output(s) of some instance of the "golden standard" cryptographic random source with said instance discarded after use³.
For code with a user interface, keypresses and mouse movements (value or position, and sampling of the above sources at each change).
Whatever is easily available, tends to vary, and is even mildly hard for an attacker to guess: compilation date/time, address of static variable/local variable/code, process id, output of some system command (on Windows, wmic process).

For the PRNG 2 itself, one possibility is HMAC-SHA-512(seed, counter) truncated to 32 bytes, where the key seed is the above hash, and the message counter is incremented for each 32 bytes. Techniques to turn this into a uniform generator in $[0,n)$ are well-known.

Note: I'm not claiming that this will generate all shuffles with the exact same probability, or even that it it is possible to positively demonstrate that it is close to that.

¹ Many if not most modern programming languages have no RNG. For example, there's no RNG in the Java language specification. If we count the JCL APIs as part of Java, SecureRandom is there. It is explicitly specified to deffer to providers that often are part of the underlying OS.

² JCL's SecureRandom supports plenty of providers and RNGs, typically including a provider with NativePRNGBlocking which promises to output continuously reseeded entropy, straight from or equivalent to /dev/random.

³ There is nothing preventing repeatedly creating a SecureRandom object, using it to generate say 16 bytes, then disposing of this object. There is at least the potential that the multiple chunks obtained are independently seeded.


How can recovered 5-letters plain text help me to recover reused OTP key I have 10 cipher texts ciphered with One Time Pad (OTP) using the same key.

I need to recover the key (or in other words, to recover the 11th cipher text which I assumed would require me to recover the key first).

I followed a technique called "Crib Drag" described in: Taking advantage of one-time pad key reuse?
Simply, by XORing the word " the " (including spaces) with the result of (C1 XOR C2), I could recover 5-letters that make sense to me that it is a plain text.

However, I do not know whether this plain text belongs to P1 or P2.

Can you help me how to know if the plain text belongs to P1 or P2 ?
How can I recover the key bytes if I could recover letters from P1 or P2 ?
How can I check whether they belong to P1 or P2 ?

I tried several attempts but no hope. Please, help me to continue and recover the key using this method.

Assume that $P_1$ contains " the ". In that case you can get the key stream by XOR'ing " the " with $C_1$, lets call this key stream $K^1$. If this key stream is correct then $P_3^1$ should make sense, where $P_3^1 = K^1 \oplus C_3$. If $P_3^1$ doesn't make sense then you can create $K^2$ and $P_3^2$ from $C_2$ in using an identical calculation and check that.

Of course, as you've got 10 ciphertext you might as well check against $C_3$ to $C_{10}$. They all should make sense if you've got the right key stream at the location you are testing. Beware though that some professors find it funny to introduce single "mistakes" in the plaintext, forcing you to perform statistics (or "by eye" verification) instead.


Elliptic curve parameters What's the meaning of "160-bit curve" in an elliptic curve? Or 192, 224, 256, etc. And what is the standard for selecting this number of bits?

Why they don't say "100-bit curve"?

What's the meaning of 160 bit Curve in Elliptic curve?

It's the size of the field, as the other answers explain. It affects the size of keys and signatures (which can be equal to the number or e.g. double it), as well as security and performance.

  Why they don't say 100 bit curve?

100-bit curves are too small.

It's also a convention. Other cryptographic primitives, like hash functions or symmetric ciphers, can have any bit length we want and powers of two are chosen for performance. So we want elliptic curves that match (or are close) to pair with them in a protocol, so we don't waste performance on security beyond the weakest link.

There's also the performance of the elliptic curve algorithm itself. It is useful to have the bit length be a multiple of a large enough power of two, like 64 bits, because computers deal with numbers of 32-bits or 64-bits. This isn't always the case though (e.g. P-521) if there happens to be a very juicy prime ($2^{521}-1$) that is easy to work with.

(As an aside, we do sometimes approximate something as e.g. 100-bit security if we don't care about the exact number but only a minimum. For example, a 256-bit elliptic curve that has a prime smaller than $2^{256}$ – e.g. P-256 – has only approximately 128-bit security so might as well call it 100-bit. Especially after you add a signature algorithm that also relies on a hash function, perhaps losing another bit of security to collisions.)


What is ε in differential privacy? In ε-differential privacy, what does the ε refer to?

Is it privacy value or the notation used?

Can anyone provide an example of differential privacy?

In ε-differential privacy, ε represents the privacy parameter.

You might want to try to enhance your research efforts because related papers and publications mention that more than frequently.

Even websites like Wikipedia would have quickly provided you with an answer to your question. Quoting Wikipedia > Differential privacy > ε-differential privacy > Trade-off between utility and privacy:

  A trade-off between the accuracy of the statistics estimated in a privacy-preserving manner, and the privacy parameter ε.

(emphasis mine)

Beyond that, you could also take a good look at these Google scholar search results. The truckloads of related papers and publications presented there explain ε-differential privacy and tend to contain examples. Honestly, “simply” writing down an example would quickly become too broad since you‘ve obviously not yet invested any time to read about ε-differential privacy and I surely don’t want to write a book explaining everything (incl. notations) from scratch. But the pointers (links) I have provided should definitely help you get started on your quest for knowledge.


Yao's Garbled circuit: Does Bob ever see the circuit? I asked a question about whether the circuit structure for Yao's garbled circuit needs to be rearranged. I understand from Yehuda Lindell's response that the circuit structure itself does not need to be changed or garbled, only the gate ciphertexts need to be garbled.

New question: does this mean it is safe for Bob to be able to know the structure of the circuit? He should not be able to know the values on the wire, but is it fine for him to know for example which gates are AND gates?

It seems to me that this would not be safe. Here is my reasoning:

Let us say gate $g_s$ is an AND gate in the circuit with input wires $w_i$ and $w_j$ and output wire $w_k$. Based on this summary if $g_s$ is an AND gate, Alice has computed the following values:

$$X_s^{0,0} = K_i^0 \oplus K_j^0 \oplus K_k^0$$
$$X_s^{0,1} = K_i^0 \oplus K_j^1 \oplus K_k^0$$
$$X_s^{1,0} = K_i^1 \oplus K_j^0 \oplus K_k^0$$
$$X_s^{1,1} = K_i^1 \oplus K_j^1 \oplus K_k^1$$

She has shuffled and renamed these values $X_s^1,X_s^2,X_s^3,X_s^4$ and sent them to Bob. $K_i^0$ is the key for $w_i$ when it's value is 0 and so on.

Bob also has access to hashes of the two keys for each wire, though he does not know which key represents that wire being 0 and which represents 1.

Say Bob has $K_i^{v_i}$ and $K_j^{v_j}$ where $v_i,v_j\in\{0,1\}$ are the values of the wires $w_i,w_j$.

Say Bob calculates $K_j^{v_j}\oplus X_s^{0,0}\oplus X_s^{0,1}=K_j^{v_j}\oplus K_j^0\oplus K_j^1 = K_j^{1-v_j}$

He will still not know whether key $K_j^{1-v_j}$ is $K_j^0$ or $K_j^1$, but he will then have both keys for wire $w_j$.

Now, he may not know which two $X_s$ values are $X_s^{0,0}$ and $X_s^{0,1}$. But he can try all 6 combinations. Since Alice has given him $AUTH(K_j^{1-v_j})$ (where AUTH is a trapdoor function) Bob can apply this function to all 6 values and see which one matches the value that Alice gave him.

In the same way Bob could find the key of $K_i^{1-v_i}$.

Bob still does not know which keys represent 0s and which represent 1s. But he does know it is an AND gate, so if he calculates the value of the output wire key value for all 4 combinations of the input wire key values. For three of these, the output key will be $K_k^0$ and one of these will be $K_k^1$. So Bob will know which key represents 0 and which represents 1.

As far as I understand, Bob has also not deviated from the algorithm, since he can still compute what he is meant to compute and send Alice the output. So Bob is still honest-but-curious.

So it seems that if an honest-but-curious Bob knows what types of gates the circuit has he could discover which keys represent 0 and which represent 1.

Is there a flaw in this reasoning?

Thanks in advance.

That summary, on which you are basing your understanding, seems bogus to me. Clearly the same $K_i^b$ values are being used as one-time pad keys, but are being used more than once. This is a major red flag.

Here's an even simpler attack: if you XOR together all 4 ciphertexts $X_s^{i,j}$ you will get $\Delta = K_k^0 \oplus K_k^1$. Since the functionality of the construction ensures that Bob will learn at least one of the values $K_k^v$, he can learn the other via $K_k^{1-v} = \Delta \oplus K_k^v$. As you point out, learning both wire labels is a violation of the privacy property.

While it is possible to use something like one-time pad for garbled circuits (see for example this paper of Kolesnikov), it requires much more care, and is not typically used in practice.

Better to think of a garbled gate as a random permutation of the following 4 ciphertexts:

$ \qquad \textsf{Enc}_{A_0,B_0}(C_0), \quad \textsf{Enc}_{A_0,B_1}(C_0), \quad \textsf{Enc}_{A_1,B_0}(C_0), \quad \textsf{Enc}_{A_1,B_1}(C_1)$

where $\textsf{Enc}$ is a legitimate encryption scheme.
(I like to use $A_0,A_1$ as wire labels on the left input wire, $B_0,B_1$ for wire labels on the right input wire, and $C_0,C_1$ for output wire labels)
In particular, knowing $Y$ and $\textsf{Enc}_K(Y)$ shouldn't allow you to solve for $K$ as it does in one-time pad.

To answer your bigger question about hiding the circuit. It is not required that the circuit be hidden from Bob. The standard setting of two-party computation has the parties first agreeing on a function to compute. The inputs to the function are to be hidden, but not the function itself. Furthermore, most practical garbled circuit constructions use the "Free XOR" optimization, and this requires Bob to behave differently for XOR gates vs AND gates (hence he must know the type of each gate).


Why is the seed masked in OAEP In the OAEP padding/armoring scheme for RSA encryption, the seed used is masked  (with the masked data block) in the end. Why is that necessary, since the seed is random anyway?

The point is that you will only be able to reconstruct the seed if you know every single bit of maskedSeed and maskedDB and you will be able to decode the message only if you know every single bit of the seed and maskedDB.

If an attacker gets only a single bit of maskedDB wrong, feeding it to the MGF will yield a totally different result and will not allow him to reconstruct the seed.

If only a single bit of maskedSeed is incorrect, the reconstructed seed will also contain a single incorrect bit and again, feeding it to the MGF will lead to a totally different value and it will not be possible to reconstruct the original message.


hashing points of elliptic curves Can I create a secure hash function $h: E(\mathbb{F}_p) \rightarrow \mathbb{Z}_q$ (for some $q$) where $E(\mathbb{F}_p)$ is an elliptic curve on the finite field of $p$ elements?
By secure hash function I mean: one way, strongly collision free.

With the current requirements, it seems like any member of $H(C(P)) \bmod q$ should work.

Where:

$H$ is the set of secure hash functions, e.g. SHA-512;
$C$ is the set of canonical encoding schemes of the points, e.g. a compressed point representation (02+X or 03+X depending if Y is odd or not);
$P$ a the set of possible points on the curve;
$q$ is the order of the curve (already specified).

This is certainly one way and collision free, as long as the used curve and hash function outputs are large enough. But note that it is not well distributed over $\mathbb{Z}_q$ (especially if the hash is shorter than $q$ of course, when viewed as an unsigned number).


I think you should probably specify more details about the current curve, or give more insight about the parameters you are choosing, eg: is this a curve over $GF(p)$ or is this a curve over $GF(2^m)$. What is your $r$ value? Without such detail I can't give a very accurate answer but the order of the subgroup generated by a given point $P$, $<P>$ can be calculated from a combination of bruteforcing and checking the divisors of the number of elements inside the original curve (Since these are cyclic groups you really only need to apply lagrange theorem and check if the current divisor $d$ of $n$ satisfies $P^d = O$). There are polynomial time algorithms to retrieve the order of the original curve group (check Schoof's algorithm).


Is $f(x) = -1.5$ a negligible function? Is $f(x) = -1.5$ a negligible function? Since it satisfies the condition for a negligible function?

You could probably have answered your own question with a quick look at the Wikipedia definition: a function $\mu(\cdot)$ is negligible if for every positive $c$, there is an integer $N_c$ such that for all integers $x > N_c$, $|\mu(x)| < 1/x^c$. The function $f : x \mapsto -1.5$ is clearly non-negligible according to this definition.

Moreover, even without looking at the exact definition, if you think of the (cryptographic) purpose of a negligible function (bounding the probability that an adversary does something he should not be able to do), it would have made no sense to define it so that any negative function is negligible. One can therefore guess that cryptographers try to use definitions that make sense :)


How can we reduce indistinguishability-from-random to other security notions? In probabilistic encryption schemes, different notions of security exists.  I'm interested in the relationship between two notions.  One is the indistinguishability-from-random notion of security and the other is the right-or-left notion of security.  In crypto literature, it's often asserted that the former is stronger than the latter.  But is there a crisp proof of that?

In Difference left-or-right CPA security, IND-CPA security, the answer seems to indicate that Left-or-Right CPA security and Real-or-Random CPA security are equivalent.  However, I have found in other papers like Rogaway's paper on Modes that Real-or-Random is a stronger notion.  On page 19, he defines the Real-or-Random security notion. On page 20, he defines the Left-or-Right notion among others.  Then he concludes: "In fact, the indistinguishability-from-random-bits notion is properly stronger than all four of the alternative notions sketched above."

Is there a proof for his claim or is this not settled in the crypto community?

Let $E_k$ be a cipher with a uniform random key $k$ unknown to the adversary.  Actually this can be any pseudorandom function family; its invertibility is not relevant in the chosen-plaintext attack model.  It might keep state, or it might be randomized; filling in the details of state and/or randomization is left as an exercise for the reader.  There are a few different ways to quantify attacks against $E_k$, usually phrased in terms of a random decision algorithm $A(\mathcal O)$ defined on an oracle $\mathcal O$ that may involve $E_k$.

Left-or-right indistinguishability.  We define the oracle $\operatorname{LOR}(P_0, P_1) := E_k(P_b)$ where $b$ is a secret fair coin toss unknown to $A$, and the adversary wins if $A(\operatorname{LOR})$ returns $b$.

That is, the adversary will submit a series of message pairs $(P_0, P_1)$, and our oracle always returns the encryption $E_k(P_0)$ of the left message, or the encryption $E_k(P_1)$ of the right message, and the adversary has to figure out which way it is.  The left-or-right advantage is $$\operatorname{Adv}^{\operatorname{LOR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{LOR}) = b] - 1/2\bigr\rvert.$$  We measure the distance from $1/2$ because any answer given by $A$ that is independent of the oracle, and therefore of $b$, will always succeed with probability $1/2$; what's interesting is how much better $A$ can do by taking advantage of the oracle.
Real-or-random indistinguishability.  We define oracles $\operatorname{Real}(P) := E_k(P)$ and $\operatorname{Rand}(P) := E_k(\tilde P)$, where $\tilde P$ is an independent uniform random message of the same length as $P$, and we will quantify how well the adversary can tell them apart.

That is, the adversary will submit a series of messages $P$ to the oracle, and the oracle might return the ciphertext $E_k(P)$ for each message, or might return the ciphertext $E_k(\tilde P)$ of random gibberish $\tilde P$ of the same length as each message instead.  The real-or-random advantage is a measure of how well the adversary can distinguish these two oracles: $$\operatorname{Adv}^{\operatorname{ROR}}_E(A) := \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(\operatorname{Rand})]\bigr\rvert.$$

These two security notions are essentially equivalent, since the best advantage against one is at most double the best advantage against the other, as shown in Bellare–Desai–Jokipii–Rogaway 1997.  There are other slightly weaker notions of security, like find-then-guess, which I usually just call IND-CPA, and semantic security, which is equivalent to find-then-guess but usually more of a pain to prove theorems about.

Note that in the left-or-right and real-or-random settings, the adversary is always given real ciphertexts of partially unknown messages.  LOR/ROR indistinguishability implies nothing about the shape of ciphertexts—ciphertexts could be written in pig-Latin encoded in KOI8-R, or in Navajo binary, as long as the adversary can't tell two ciphertexts apart.

We can instead consider the difficulty of distinguishing ciphertexts from uniform random bit strings as in Rogaway's CRYPTREC evaluation:

Indistinguishable from uniform random.  We define the oracle $F(P) := \tilde C$ where $\tilde C$ is an independent uniform random bit string of the same length as the ciphertext for $P$, and we will quantify how well the adversary can tell $E_k$ apart from $F$.

That is, the adversary will submit a series of messages $P$ and get either the corresponding ciphertext $C = E_k(P)$ each time, or get an independent uniform random bit string each time.  The indistinguishability-from-uniform-random advantage is: $$\operatorname{Adv}^{\operatorname{PRF}}_E(A) := \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert.$$  (Called ‘PRF’ here because this is essentially the same notion as for pseudorandom function families.  In Rogaway's manuscript, it's called ‘ind\$’ because cryptographers apparently like to mark randomness with \$ signs.)

It is very easy to concoct a cipher that has left-or-right/real-or-random indistinguishability but is trivially distinguishable from uniform random: if $E'_k$ has LOR/ROR indistinguishability, define $E_k(x) = E'_k(x) \mathbin\| 0$ and you get a trivial distinguisher of the ciphertexts from uniform random bit strings, even though $E_k$ obviously still has LOR/ROR indistinguishability.  So clearly left-or-right/real-or-random indistinguishability does not imply indistinguishability from uniform random.

How do we show that indistinguishability from uniform random implies left-or-right and real-or-random indistinguishability?  Since left-or-right indistinguishability is equivalent to real-or-random indistinguishability, proving the result for ROR implies the result for LOR.  We will show that the real-or-random advantage of an adversary to distinguish true ciphertexts from ciphertexts of uniform random plaintexts is at most the sum of

the adversary's advantage at distinguishing the true ciphertexts from uniform random bit strings, and
a related adversary's advantage at distinguishing the ciphertexts of uniform random plaintexts from uniform random bit strings.

Let $A$ be a putative real-or-random distinguisher.

Note that the oracle for a real-or-random distinguisher is syntactically like the oracle for a uniform random distinguisher: it takes a plaintext, and it returns a ciphertext-length bit string.  So we can just as meaningfully evaluate $A(\operatorname{Real})$ and $A(\operatorname{Rand})$ as in the real-or-random setting, and $A(E_k)$ and $A(F)$ as in the uniform random setting.
By definition, $\operatorname{Real} = E_k$, so $A(\operatorname{Real}) = A(E_k)$.
Note that if $A(\operatorname{Rand})$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $E_k(\tilde P_1), \dots, E_k(\tilde P_n)$ where the $\tilde P_i$ are independent uniform random plaintext bit strings.  So running $A(\operatorname{Rand})$ is equivalent to running $A'(E_k)$ where $A'(\mathcal O)$ works exactly like $A$ but queries $\mathcal O(\tilde P_1), \dots, \mathcal O(\tilde P_n)$ where $A$ would query $\mathcal O(P_1), \dots, \mathcal O(P_n)$.  That is, $A(\operatorname{Rand}) = A'(E_k)$.
Similarly, if $A(F)$ submits the plaintexts $P_1, \dots, P_n$ to its oracle, what it gets back are the ciphertexts $\tilde C_1, \dots, \tilde C_n$ where the $\tilde C_i$ are independent uniform random ciphertext-length bit strings.  It could just as well have submitted $\tilde P_1, \dots, \tilde P_n$ to its oracle, as $A'(F)$ would do, since $F$ ignores the input.  That is, $A(F) = A'(F)$.

We can combine these facts with the triangle inequality to set the desired bound:

\begin{align*}
  \operatorname{Adv}^{\operatorname{ROR}}_E(A)
    &= \bigl\lvert\Pr[A(\operatorname{Real})] -
         \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &= \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]
       + \Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &\leq \bigl\lvert\Pr[A(\operatorname{Real})] - \Pr[A(F)]\bigr\rvert
       + \bigl\lvert\Pr[A(F)] - \Pr[A(\operatorname{Rand})]\bigr\rvert \\
    &= \bigl\lvert\Pr[A(E_k)] - \Pr[A(F)]\bigr\rvert
       + \bigl\lvert\Pr[A'(F)] - \Pr[A'(E_k)]\bigr\rvert \\
    &= \operatorname{Adv}^{\operatorname{PRF}}_E(A)
       + \operatorname{Adv}^{\operatorname{PRF}}_E(A').  \tag*{$\square$}
\end{align*}


Luby-Rackoff on Feistel ciphers On page 46 of these lecture notes, it seems to say that if we have a Feistel cipher, and plaintexts $(L_0, R_0)$ and $(L_0^*, R_0^*)$ with corresponding encryptions, then we can determine the key? But isn't this not the case by Luby-Rackoff? I'm not entirely sure what the slides are even saying. They say that we can compute $R_3 \oplus R_3^*$, but so what? How does this help determine the key?

Xor can help find bits not yet known, whether most significant or least significant; and help the adversary find more information about both ciphertext and plaintext, especially if a table of potential plain texts or even keys is stored in conjunction with bitwise Xor.

Some reading:

http://www.researchgate.net/publication/2633994_Luby-Rackoff_Ciphers_over_Finite_Algebraic_Structures_or_Why_XOR_is_not_so_Exclusive

Although this has minor typos, the notes on Feistel networks and Xor is excellent:

https://github.com/FredericJacobs/Cryptography-Stanford-Notes/blob/master/crypto-notes.md

Luby-Rackoff, as you may already know, is a key component of the Feistel network and it is not secure in 1,2, or 3 layers. Luby-Rackoff must have a 4 independent layered Feistel network structure from independent seeds to be considered a strong pseudo-random permutation. No less than 3 independent rounds must be used to even be considered a pseudo-random permutation though it is much weaker. Some consider a 3 round Feistel to be a secure pseudo-random function, but 4 rounds proves to be more secure.

No more than 8 corresponding outputs from the 32 pairs of inputs of the Xor should exist.

I suggest learning more about Xor and differential cryptanalysis.

Please focus most on pages 4-7 and 11-16, but the whole article is interesting if you have time:  http://cs.ucsb.edu/~koc/ccs130h/notes/dc1.pdf

It covers the tables and Xor technique in much better detail.


How will Cryptography be changed by Quantum Computing? I realise this isn't a 'yes or no' question, and I apologise for asking something that could be seen as a discussion thread, but I had to ask.

I'm currently doing an EPQ in CS (specifically how QC will change Cryptography). I'm trying to gather up topics to cover, and so far I've scribbled down -

Effects -

National security, classical cryptographic methods (RSA, DSA, AES-256). Including Shor's algorithm.
Communications
Online services, e.g. BitCoin.

How would we counter this (not sure how better to phrase this) -

Lattice-based
Multivariate
Hash-based signatures
Code-based cryptography

Is there anything else you'd recommend me including (as well as the above), or anything in the above you don't think I should include?

Honestly, the list above is a rough, first draft the main bulk of it... so don't it as gospel.

Best regards,

Cameron.

Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical algorithms, but the best known quantum attack against AES is effectively "try all the keys." In a quantum computer, the time taken to solve a general search problem (such as "find the AES key that gives a reasonable message") scales slower than for a classical computer; this would effectively turn an n-bit key into an n/2-bit key. Fortunately, that would leave AES-256 with an effectively 128-bit key against a quantum attacker, which is still believed unfeasible to crack. Similar considerations apply to hashes. You'd want to increase key lengths and the like, but you could fairly reasonably do that.

The main issue is actually asymmetric cryptography. Unlike symmetric crypto and hashes, asymmetric algorithms have extreme levels of mathematical structure -- they're based on the difficulty of a single hard problem. The two main problems used for this can be solved extremely quickly on a quantum computer; if you tried to increase key lengths to make it take a long time there, it'd take an infeasibly long amount of time for the legitimate user on a classical computer to use the long keys. However, this is something of a historical accident: there's no reason asymmetric crypto has to be easily breakable by a quantum computer, it's just that the most commonly used ones happen to be easily breakable by one. Others may not be; post-quantum cryptography is an active research area, and people are working on algorithms that rely on problems not believed to be efficiently solvable by quantum computers.


How exactly was the finalist chosen in the NIST AES competition? I was just reading the Stick Figure Guide to AES and came across an interesting table explaining how the winner was chosen:

Unfortunately the NIST site is down so I can't gain further information about the approval process so I was hoping someone here would know in more detail.

Who or what decided on the numbers in this table which ranks each
algorithm? I.e. can the exact analysis process be described?
Who created that process? People in NIST or an equally divided group of government, industry and public cryptographers?
What is included in "Design Features"? I.e. What were those features that were important?
"Performance" analysis could have been done with benchmarks but "Implementation Difficulty" sounds subjective. How was that quantified?
Could the numbers in that table been tweaked to skew the results in favor of a particular algorithm?

Those questions aside and assuming the magic numbers above were arrived at a fair and equitable process without bias or hidden agendas, it seems to me this table or ranking system is still missing a "weighting" criteria. All categories seem to be weighted with the same importance. That is "Smart Card Performance" is equally important as "General Security". That seems incorrect. I would argue that security is of the utmost importance so that should have a higher weighting relative to the other criteria which would be secondary concerns. A good quote would be:

  Security at the expense of usability, comes at the expense of security.

I wondered what would happen if I applied a high weighting factor to security and left the other points as they are. For example:

Now Serpent is first equal with Rijndael with Twofish coming in a close second. Interesting.

What about if I am developing a software product, I don't care about about hardware performance or smart card performance so I can rule those two out completely in my decision. The table might look like this:

Now Twofish is the winner and Rijndael is second equal with Serpent and MARS. MARS might even be more attractive with its variable key size up to 448 bits.

My overall point is that Rijndael, Serpent, Twofish and MARS all appear to be within the same ballpark quality range as far as block ciphers go and this rating criteria. There might be a more accurate mathematical way to apply a weighting factor. If I was revamping the security on a project and concerned about NSA involvement in weakening encryption standards then I could re-weight some of the criteria and priorities to suit my project's specific goals. I might decide on a different algorithm from Rijndael. Back in 2000 Rijndael might have suited the US government's purposes and planned surveillance agendas but not my project's. I would compare it to selecting an algorithm just like TrueCrypt gives you the option of choosing between 3 different algorithms. Would that be a reasonable call?

At the time of the competition (I can talk about it, I was there), there was a lot of discussion and various people showed arguments. However, there was never an official, publicly known "board of scores" with totals and definite rules, as the pictures you show seem to purport. It is possible that the NIST people did make something similar internally, but they certainly did not publish it. From the outside, the choice has been made by NIST in "some way" and they then provided qualitative reasons, not really quantitative. NIST never bound itself into following strict rules; they wanted to remain in control of the whole proceedings.

The picture still conveys the main reasons why Rijndael was chosen:

Its performance is nowhere bad. It was not the highest performer on every platform, but there was no platform where it would be abysmally slow, in contrast to almost any other candidate.
The "implementation difficulty" relates to features which, on some platforms, imply quite some work. For instance, RC6 requires a multiplier, which is hard on ASIC / FPGA (which translates to: it uses a lot of silicon space). MARS is very complex (many kinds of transforms piled up together) and implementers have reported that it took them quite some time to come up with working implementations, let alone optimized implementations. Twofish uses key-dependent S-boxes, which need RAM (bad for smart cards, bad for ASIC/FPGA). Rijndael was rather simple to implement (in retrospect, Serpent was better for that, especially if you want to implement the algorithm without lookup tables).

During the round conferences, where cryptographers who meet to talk about the AES candidates, some informal surveys were conducted, where people could give "scores" to candidates. While Rijndael did not necessarily elicit the best marks from everybody, nobody really hated it, so it looked fine as a future standard.

All of this, of course, depends on quite arbitrary assumptions on the usage context. NIST wanted an all-purpose block cipher, suitable to a large range of hardware platforms. If you target a specific system (e.g. for disk encryption on your PC), then this may point at another algorithm; for instance, RC6 is faster than Rijndael on a PC (except if the said PC offers the AES-NI instructions, of course).

The really good thing about the AES competition is not that it came up with a good, strong algorithm; what matters is that almost all candidates turned out to be good and strong. Among the 15 candidates, only two were "broken", and then only in an academic way. The trust we can have in AES comes from that: the AES competition proved that we apparently knew how to design algorithms that nobody else knows how to break (that's about as good as you can get with symmetric cryptography).


Is multiplicative blinding less secure than additive? It's easy to see that additive blinding (e.g., $x+r$ for secret x and random r) is perfectly secure in a finite field (this is a one-time-pad) and statistically secure for $r$ uniformly distributed in a domain sufficiently larger than $x$.

What I'm confused about is multiplicative blinding (i.e., $x \cdot r$) - in some places, I read that it's being used and is as secure as additive blinding, while in others it's stated that it is much less secure (e.g., multiplicative blinding less secure). Assuming, of course, both $x \neq 0$ and $r \neq 0$, is multiplicative blinding as good as additive (ignoring side channel attacks), and if not - what's the explanation?

In a finite field $\mathbb{F}_q$, both maskings are perfectly secure, provided that $x \neq 0$ for the multiplicative masking.

This is easy to see.  The finite field $\mathbb{F}_q$ defines two groups: the additive group $\mathbb{F}_p^+$ (i.e., $\mathbb{F}_q$ equipped with addition) and the multiplicative group $\mathbb{F}_q^*$ (i.e., $\mathbb{F}_q \setminus \{0\}$ equipped with multiplication).

Proposition  Let $\mathbb{G}$ be a group and let $\star$ denote the group law in $\mathbb{G}$.  Given $x \in \mathbb{G}$, if $r$ is a uniformly random element in $\mathbb{G}$ then so is $y:=x \star r$.

Let $x \in \mathbb{F}_q$.  We have:

If $r$ is drawn uniformly at random in $\mathbb{F}_q^+$ then $x+r$ (where $+$ denotes the addition in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^+$;
If $r$ is drawn uniformly at random in $\mathbb{F}_q^*$ then $x*r$ (where $*$ denotes the multiplication in $\mathbb{F}_q$) is uniformly random in $\mathbb{F}_q^*$, provided that $x \neq 0$ (that is, $x \in \mathbb{F}_q^*$).


Use Smart Card to decrypt files So I'm trying to figure out the feasibility of using a Smart Card to decrypt files in an offline scenario.

I wish to sync encrypted files to a mobile phone with a Smart Card reader case. The files should only be readable when the Smart Card is in the card slot. If the user looses the phone the files will be stored in a encrypted format on disk only.

Assume that I will not be able to write any actual Smart Card apps myself and that the Smart Card is a US CAC or equivalent.

My thinking goes something like this:

Send the Smart Card certificate (containing the Public Key) to backend server
Backend server generates files and encrypts those by using the client Public key and Signs the file with backend private key
Client receives files, verifies backend signature and then decrypts the file with the Smart Card private key

For number 3 I wonder if this is available and would it be performant for text only files?

If it is available, how does it work. Will the Smart Card take a stream of encrypted bytes and then spit out a stream of unencrypted bytes?

Any references to similar examples, code etc appreciated.

Edit: By performant I mean decryption measures with bytes/s. I saw in a talks that the cards have accelerated encryption chips but I don't really know what that implies.

Also, found some sample code from a course homepage at Radboud University. So it is possible to achieve with a custom Java Applet. I'm still wondering if there are any "standard" ways of doing this, either as a part of APDU or GlobalPlatform commands.

Crypto Applet
https://www.cs.ru.nl/E.Poll/hw/samples/CryptoApplet.java

Usage from Java
https://www.cs.ru.nl/E.Poll/hw/samples/CryptoTerminalSmartCardIO.java

Edit 2: So I figured out that the card supports PKCS#11 and that is probably what I should use.

I've downloaded the pkcs11-tool which works well for browsing/viewing things. I can list certificates etc. But when I try to sign something I get that the operation is unsupported (PKCS11 function C_SignFinal failed: rv = CKR_FUNCTION_NOT_SUPPORTED (0x54)).

The documentation I've found on this tool is not very good (no examples just man page) so if anyone knows how to do this properly please tell:

pkcs11-tool --module $OPENSC_LIB --sign --slot 0x2 --input-file message.txt --login --pin XXXXXX --mechanism SHA1-RSA-PKCS

By the looks of it I would also be able to use PKCS#11 to decrypt a message. Didn't get that far yet.

If it is available, how does it work. Will the Smart Card take a stream of encrypted bytes and then spit out a stream of unencrypted bytes?

No, that's generally not what happens. In general smart card simply supply an RSA operation that performs raw RSA, RSA PKCS#1 or RSA OAEP decryption. The result of this operation is a relatively small amount of bytes; e.g. in the case of RSA PKCS#1 about 11 bytes less then the key size (which is the size of the modulus for RSA). If a raw RSA operation is provided then the unpadding should be performed by the off card entity.

So what is used is a hybrid cryptosystem. Such a system uses a random, symmetric data key to encrypt the plaintext. This random data key - usually an AES key - is then encrypted by the RSA public key. The encrypted data key is stored together with the ciphertext using a container format such as CMS or Open PGP.

Upon decryption the AES data key is first decrypted with the private key on the smart card. This for instance requires a PIN code to be entered to gain access to the private key. Once the data key is decrypted it can be used to decrypt the rest of the data. Using authenticated encryption (such as GCM) should of course be preferred.

So the smart card only "accelerates" the private key operation. I put that between quotes as in general a mainstream CPU will be much faster than the speed of the cryptographic co-processor and the communication overhead provided by the card. The AES operations are performed off-card, and they bear the brunt of the work for any files above, say, a few KiB.


Message expansion in NTRU: why is it $\log_p(q)$-to-$1$? Suppose that we are working with the original version of NTRU with parameters $(N,p,q,k,d_f,d_g,d_\phi)$.

In this case we are working with the original NTRU with the digital envelope and the parameter $k$ is described below.

Suppose that we encrypt a message $m$ that is in $\frac{\mathbb{Z}[X]}{\langle X^N-1 \rangle}$.

Recall that $m$ has coeffcients between $-\frac{1}{2}(p-1)$ and $-\frac{1}{2}(p-1)$ and has degree at most $n-k-1$.

The ciphertext is then $e=p\phi \circledast h + m$.

It is said that the message expansion is equal to $\frac{n}{n-k}\log_p(q)$-to-$1$.

Can someone help me explaining why do we have this equalty? I don't quite understand what is said to be "message expansion" in this context...

Thanks in advance.

I guess you are taking this information from this document.

In Section 2.1 you can see a table with different sizes. In particular, a plaintext block (that is, an encoded message) has size $(n-k) \log_2 p$ bits, while a ciphertext has size $n \log_2 q$ bits. The explanation is simple: ciphertexts are actually polynomials of $n$ terms (since degree is $n-1$), where each coefficient can be represented with $\log_2 q$ bits, while encoded messages are polynomials of $n-k$ terms (since degree is $n-k-1$),  where each coefficient can be represented with $\log_2 p$ bits.

Now, the "message expansion" (also known as "ciphertext expansion") is simply the ratio between the ciphertext size and the plaintext size. In other words, it is an indication of how much a ciphertext increases with respect to the original message. Ideally, you don't want it to expand too much for obvious reasons, although it can be shown that some expansion must exist for the encryption to be semantically secure (in the case of public-key schemes, like NTRU). In this case, it is $\frac{n \log_2 q}{(n-k) \log_2 p}$. Finally, by the properties of logarithms we have that $\frac{\log_2 q}{\log_2 p} = \log_p q$, so the final message expansion is $\frac{n}{n-k}\log_p q$.


Why is a known-plaintext attack considered a complete break? I read somewhere that if a cipher has a known-plaintext attack, then it is considered completely broken.

Say there is a cipher that someone uses where the algorithm is understood and a known-plaintext attack is trivial to perform, however a ciphertext only attack is as impractical as brute force. The XOR-Cipher with the key length equal to message length, for example.

If the user changes the key for every message sent, then what use is a known-plaintext attack?

It's always been my understanding that if one finds the key to a message they already know but to nothing else, then that is just as useless as not being able to perform a known-plaintext attack at all.

So what use is a known-plaintext attack in a world where a key is never used more than once (effectively a one-pad pad)? How is that "a complete break"?

if a cipher has a known-plaintext attack, then it is considered completely broken.

Yes, pretty much...

  [Paraphrased] But can't we come up with a case where this isn't true, such as a One Time Pad?

Yes, we can come up with cases like that; however the requirements of such a case (key as long as the plaintext, no key reuse) make such a cipher impractical.

Instead, when we talk about such a cipher:

We generally use the same key to encrypt multiple messages (for example, consider TLS, where the the symmetric key is used to encrypt all records going in the same direction)
And, even when we use a key to encrypt only one message, the attacker might be able to guess parts of it; if he can use those guessed parts as known plaintexts, and recover the parts he didn't know (or even to verify if his guess is accurate), well, the cipher didn't do its job.

"Known plaintexts implies total break" is an excellent rule-of-thumb, even if you can come up with cases where it is not true.


Is it safe to send IV in plain text for every request? Currently, I am creating a project with an IoT device. This is an offline device which shows a QR code which can be scanned by a mobile device, which sends this code to a server. The server handles data but does not send anything back.

The plaintext data part of the QR code needs to be encrypted and should not be changed, nor intercepted, so I made the following protocol:

The IoT device generates a new EC keypair at every boot;
The server has a permanent EC keypair. The server public key is stored in the firmware of the IoT device;
When creating a QR-code, the IoT device calculates a DH agreement with the server's public key and the private key of the IoT device;
The IoT device creates an IV from an incremented nonce (8 bytes array);
The data gets encrypted using chacha20 with the calculated agreement;

The QR code is then generated using the following format: (IoT public key) + (iv) + (ciphertext).

The server is then able to decrypt the ciphertext by using the IoT public key, which can be used for calculating the agreement and the IV for decrypting the ciphertext.

Now I have several concerns since I am new to crypto and I am almost sure that my protocol is not safe enough.

Is it safe to embed and send the IV in plain text in every QR-code?
When using the same nonce, decryption will still work, what is the purpose or misuse of the nonce here?
Should I use chacha20 at all? Or is there a much better encryption/decryption method to use here?
I need to keep my server's public key secret and only in the firmware of the IoT device, to prevent 'fake devices' generating valid but fake QR codes, which sounds bad.

Is it safe to send the IV in plain text in every QR code request?

IV is not secret and never meant to be, it can be sent as it is. See the CBC mode from the Wikipedia.

  When using the same nonce, decryption will still work, what is the purpose or misuse of the nonce here?

Nonce (in Cryptography) means number used once. The IV in the CBC mode cannot be nonce. The aim of IV is randomizing the encryptions. Using the same IV again turns the CBC mode into the ECB mode. This has catastrophic results, see the penguin from Wikipedia in or look at frequency attack.

For the difference of IV and Nonce please see Difference between a nonce and IV

  Should I use chacha20 at all? Or is there a much more better encryption/decryption method to use here?

You need authenticated encryption which simultaneously give authenticity and integrity. You may choose ChaCha20Poly1305 or AES-GCM.

  I need to keep my server's public key secret and only in the firmware of the IoT device, to prevent 'fake devices' generating valid but fake QR codes, which sounds bad.

Public keys are not created to be kept secret. The more important is the ID of the IoT that should be sent during the data transmission so that the server can accept the result. Therefore the server must store the ID's beforehand. In the current design, the server is going to accept any message.

Note: You will also need to authenticate the mobile device, otherwise any mobile device can be used to attack.

Note 2: IV should not be predictable.

Note 3: You don't need to generate if from a nonce. A good random source should be enough. See  Best way to generate a IV for AES-CBC when encrypting files?


Encrypting between nodes that have RSA keys: Diffie-Hellman or random secret key? I have two peers with RSA keys; they want to encrypt a non-trivially sized message between them, so I want a random AES symmetric secret key, which is encrypted with Bob's public RSA key, and sent along with the AES ciphertext.

I believe this idea is pretty standard. The question is: do I generate the AES key using Java's SecureRandom.getInstanceStrong(), or do I implement Diffie-Hellman between the two nodes?

I assume the main advantage of DH is forward secrecy. Are there any other considerations? How difficult is it to implement DH securely?

If you're using RSA as a key encapsulation mechanism, then there is no need to use Diffie-Hellman to generate the shared secret.
Diffie-Hellman provides key agreement: Both Bob and Alice will end up with the same shared secret. No party a priori selects what that secret will be, it is determined by whatever $({g^a})^b \equiv ({g^b})^a$ happens to be.
If you did use Diffie-Hellman to generate the shared secret, then both Alice and Bob will already have the shared secret. Having Alice then encapsulate that and send it to Bob via RSA does not accomplish much.

How difficult is it to implement DH securely?

It's difficult - you are not expected to do so, and you should not need to do so. Perfectly good, free libraries that have already solved this problem exist.
Note
If it is at all possible, consider using an existing protocol and library such as TLS or libsodium instead of re-inventing this particular wheel.
If your current crypto library forces you to make these types of decisions, it's not a library you want to use.
A good crypto library will offer high level constructions that solve specific problems, rather then requiring you to combine low level constructs into a solution that you think/hope might work.

I believe this idea is pretty standard.

Quoth the bear, Nevermore
Actually, using RSA for this is not that great of an idea and is being phased out in general.

RSA-based key agreement (or transport, or exchange) with PKCS#1 v1.5 is vulnerable to Bleichenbacher attacks. OAEP (from PKCS#1 v2.0) is better, though it requires implementation to not leak partial information on failure causes, otherwise Manger's attack applies (which is like Bleichenbacher's, but more efficient). That's the first reason RSA key exchange is being discouraged.
The second reason is that RSA key generation is expensive (and hard to make constant-time)(there is a constant-time RSA keygen in BearSSL), so you don't want to make a new RSA key pair for each incoming connection. Reusing encryption keys goes contrary to forward secrecy, and forward secrecy has become a selling point (though it's a bit overhyped, in my opinion).
The third reason is basically performance, or at least performance perceived through the filter of microbenchmarks. An RSA private key operation is an order of magnitude more expensive than some ECDH.

Source: the Bear says so (excerpt from a private conversation)


Generating Encryption Keys from Biometric Fingerprint Templates How would one go about generating Encryption Keys from Biometric Fingerprint Templates extracted from a fingerprint using either Griaule SDK or DigitalPersona SDK or any other SDK that will return the fingerprint template in either ISO or ANSI fingerprint templates format? Is there a way one would do that using Fuzzy Extractors, Secure Sketch, Bio Hashing or any other approach? I will appreciate if anyone can show me how to go about this in any programming language? I intend to use the obtained Encryption Keys in encryption and decryption of data.

There is a pretty good introductory book that strongly relates to the topic area: Security with Noisy Data that I would recommend you take a look at. The book has constructions for how you would do this (turn fingerprint readings into keys), information on different adversary models you might consider, and information on related topic areas.

I am not familiar with either of the SDKs you mention, or the formats. So, for the sake of simplicity, I'll assume that each time you read the fingerprint, you get back a binary string. Since the scanners are not perfect, each time you read from it, you will get back a slightly different binary string. Let $\rho$ be the maximum error rate you see between binary strings which come from scanning the same fingerprint. One chapter in the book (which is freely available here) gives constructions for how you can generate and publish some helper data which can be stored in plaintext. This helper data allows you to recover the original key so that you can, for example, decrypt.

Let $C$ be an $[n, k, 2t+1]$ linear error  correction code defined over some finite field $\mathcal{F}$. $t$ is the number of errors that can be corrected, so we need  $t$ to be large enough to  correct $n\rho$ errors. The syndrome construction for secure sketches works as follows.

We have 2 phases (enrollment and reconstruction or GEN and REP). GEN: Let $H$ be the parity check metric of $C$. We take a sample from the reader to get the binary string representing the fingerprint, call it $w$. The length of $w$ is $n$. Let $H$ be the parity check matrix of $C$, we compute the syndrome of $w$ as $wH=s$. We then run $w$ through an extractor (e.g., a hash function) to get the key. We publish $s$ publicly as the helper data.

REP: At some later point in time, we want to reconstruct the key (do do a decryption or further encryption). This time we take another sample using the reader and get $w'$. We decode $w'$ using $s$ to get back $w$, and rerun $w$ through the extractor to get the key. As long as the hamming distance between $w$ and $w'$ is less than or equal to $t$ we are guaranteed to get the same key. For more information on coding, and some source code, see here.

In practice there can be issues. The helper data $s$ leaks information. So, to get 80 bits of security, $w$ is going to have to be larger than 80 bits long. Using the syndrome construction, we can quantify the amount of information leaked by $s$. It is $n-k$ which happens to also be the length of $s$. I am not sure what the error rate is for fingerprint scans or the entropy rate. It could very well be that by the time we have published $s$ there is no usable entropy left. Recent work tries to deal with this case. But, if the error rate is too high, and the number bits in a single fingerprint is too low, we could be in a case where there is just not enough entropy to get a strong key. Therefore, you really need to analyze and think about if this will work. Theoretical constructions are there, but physical limitations might make it impossible.


How can Hashed Value be same in length extension attack? Let's say we had the following information:

Secret = "Hello"
Message = "Attack at Dawn"
H(s,m) = ABC

Alice is sending a message to Bob but there is a person in the middle, Mallory who intercepts the message.
A ------(s,m)= v ----> Mallory ------ (s',m') = v' ---------> Bob

In order to make sure that the message is untampered v=v'. Here is my question: how can Mallory append to the end of the hashed value yet still have the same hash?
How is it that $H(\text{ABC||"jk don't attack"}) = ABC$? Doesn't the extra char in the string change the entire hashed output?

It is not about having the same hash value. It was about forging a message.
It was first executed on Flicker API where the signature was;
$$tag = \operatorname{MD5}(\text{secret_key}\mathbin\|\text{known_data}),$$ the $tag$ and $\text{known_data}$ send to server, and the server can verify it with the $\text{secret_key}$.
The attacker can extend this message this into
$$tag_2 = \operatorname{MD5}(\text{secret_key}\mathbin\|\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data})$$
Now you can send the server $tag_2$ and extended message $$\text{known_data}\mathbin\| \text{pad1}\mathbin\|
 \text{appended_data}$$
The server will accept it since it was assumed that the key used in the signature will protect against the forgeries, but not. It was known way before the attack.
It can similarly be applied to SHA-1 if it is used as $$tag_x = \operatorname{SHA-1}(\text{secret_key}\mathbin\|\text{known_data})$$
or any hash function that has no resistance to length extension attacks.
To mitigate one either need HMAC or KMAC of SHA3.
If you ask about finding collisions, it is possible in theory, but not in practice.


Append data to authenticated ciphertext encrypted using a stream cipher Say we have xSalsa20 authenticated using Poly1305. If $ X $ is the ciphertext, $N$ is the nonce value, and $H$ is the authentication tag such that the final ciphertext is $ N || X || H $, then given the key $K$, is it possible to extend $ X $ with more data, without decrypting it, updating $N$ and $Y$ as needed? (I'm not sure if $N$ would need to be changed.)

To be clearer, say $ X_m $ is the original authenticated ciphertext. I want to append plaintext data $ A $ to it. I'm looking for a scheme to implement $ X_n = Append(X_m, A, K) $ such that $ Decrypt(X_n, K) = Decrypt(X_m, K) \| A $.

Salsa20 is a stream cipher so it produces a CSPR key-stream, $ S $, and then then ciphertext becomes $ X = S \oplus P $, where $P$ is the plaintext. So I intuitively feel as though this should be a lot easier to do than with a block cipher. Perhaps by generating the same key-stream up until the size of the ciphertext and encrypting the new data with the part of the key-stream past that point. If the authentication tag is generated from the ciphertext then decryption wouldn't be necessary for that either. Also the nonce would not really be reused in a scheme like this as far as I can see.

How well would this translate to other stream ciphers like XChaCha20-Poly1305?

Well, no you can't (without rescanning the entire ciphertext), and you probably shouldn't anyways.

The xSalsa20 is the easy half - it is effectively in counter mode, and so it'd be easy to generate a few more bits out of the xSalsa20 to use to encrypt the additional data you're appending (and those additional bits wouldn't change to previous ciphertext bits).

The problem is with the Poly1305 half; it treats the ciphertext as polynomial coefficients (over $GF(2^{130}-5)$) and then evaluates that polynomial for a secret value of $x$ (and then adds a secret nonce-dependent factor) - if that's all it did, then it would be fairly easy to adjust the polynomial result to account for the additional bits (by subtracting out the secret constant term, multiplying by a power of $x$ if necessary, and then adding in the new bits and adding back the secret constant term).  However, it does one further step; it takes the output of the polynomial (which is a value between $0$ and $2^{130}-6$), and takes it mod $2^{128}$.  That means that, for (almost) any tag value, there are 4 possible values that the polynomial would evaluate to, which implies 4 possible tags that the extended polynomial would need to be (because those two higher bits modify the lower bits once we multiply it by $x$), and you have no idea which one it might be (without recomputing the polynomial from scratch.

Now, one could modify the initial Poly1305 implementation to save those two upper bits that the $\bmod 2^{128}$ operation scraps away (and leaking those would not give any advantage to an attacker); this would allow an efficient incremental update.  On the other hand, doing so might not be a great idea - if an adversary sees both ciphertexts (that is, the original and the extended version, both of which uses the same nonce), he can compute an explicit polynomial which has the secret value $x$ as a root - this allows him to recover a good guess of the value of $x$, and that would allow him to modify ciphertexts at will without being detected.

Because of this threat, I believe you really do want to change the nonce whenever you modify the ciphertext; that involves a full decryption and reencryption.


Why does OAEP have 2 rounds with 2 random oracles? I strive into understanding why OAEP has two rounds of computations and not just one. I.e: Wouldn't it be safe to hash the random number r and XOR it with the original message?What security risks if any that padding scheme violates?

This variant of OAEP would be malleable if the underlying trapdoor permutation is malleable, and hence would not be chosen-ciphertext secure.  This is a major theoretical weakness, as I explain below, and one that may lead to attacks in practice.

In more detail, suppose $G$ is the (lone) hash function and $f$ is trapdoor permutation used, so the formula for the encryption algorithm of this variant of OAEP is
$$f(m\oplus G(r)\|r).$$
Suppose you have are given the output of the encryption algorithm (call it $y$) for some unknown message $m$.  If $f$ is malleable, it may be feasible to come up with $y'$ that is an encryption of $m$ with a bit flipped, meaning $$y' = f(m'\oplus G(r)\|r)$$ for $m'$ equal to $m$ with a bit flipped.  If one obtains a decryption of $y'$ (as is allowed in a chosen-ciphertext attack) then one learns $m'$ and hence $m$.

The extra round of OAEP is to ensure that such ciphertexts decrypt to unrelated messages that do not help an attacker.  You may want to look at SAEP and SAEP+ [1] for some more results on one-round variants of OAEP that are secure.

[1] D. Boneh.  Simplified OAEP for the RSA and Rabin functions. In proceedings of Crypto '2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp. 275-291, 2001


What are the chances of an RSA signature collision? My understanding is: fundamentally it should be hard to produce a different message with the same signature. Therefore chance of collision should be low. But what exactly is the probability of a collision, taking into account stuff like the birthday paradox?

As a consequence, in a system with many signed messages, is it safe to use the (sha-2 or sha-3 hash of the) signature as a unique identifier?

So what you are asking is if we could create $\operatorname{Sign}_S(M_1) = \operatorname{Sign}_S(M_2)$ where $S$ is the private (and secret) key. Obviously, this cannot be the case. If you could then an adversary could claim you signed $M_2$ even though you actually only signed $M_1$. That would also mean that the signature would be repudiable; a signer could simply claim to have signed a different message. Non-repudiability is arguably the most important aspect of a digital signature in the first place (authentication can also be performed using other primitives, e.g. using a static DH key, after all). To round it up: if signatures would collide for separate messages and the same key (and the same configuration parameters) then the algorithm would be fundamentally broken.

Note that many signature generation algorithms are non-deterministic. In other words, they take the input of a random number generator as input, and will therefore generate a different signature each time the signature is generated. The often used RSA-PKCS#1.5 scheme is however deterministic and RSA-PSS can be configured to be deterministic by configuring the salt size to an empty octet string / byte array. Mind you, runtimes may decide not to make the salt size of RSA-PSS configurable, in which case RSA-PSS remains non-deterministic per default.

So yes, you can use a hash to subtract or condense the signature into an identifier, as long as your signature is deterministic (and presuming you want to regenerate the identifier later on). If your hash is too large then you can simply use the leftmost bytes or use a smaller hash function. There are also multiple ways of expanding the result - although that's unlikely required for your use case. Nowadays you would probably use a XOF such as one of the SHAKE functions (part of SHA-3 specs) for expansion. An KDF that supports expansion such as HKDF-expand would also be an option.

Note that most if not all modern signatures already include hashing of the data - if just to make sure that the requested property holds. It would be a good idea for the hash functions to have about the same security strength. Of course you need to use a secure hash function (e.g. SHA-2 / SHA-3 and not MD5 or SHA-1) for the hash function.

The smaller the final identifier, the bigger the chance of collisions, of course. Note that you would need $2 \cdot s$ bits to reach a strength of $s$ bits due to the birthday problem. Don't make your identifier too small, especially if you're planning of using many identifiers. Using the full hash output should of course be preferred.


How can I make sure message m ∈ Zp I am implementing ORUTA and using JPBC library for it.
In one of the algorithms, for hashing a message, it is specified that for message m:

$m \in \mathbb Z_p$ , for some large prime $p$.

I have a message text, so how can I make sure that the above equation holds true?
(If possible someone please reply with example code or any predefined funtion able to do this).

It depends on what exactly you want to achieve. I don't know ORUTA.

But in general:
You have to convert your message to a numerical representation somehow. Then the message has to be short enough to be in Zp.

e.g. in Java:

    BigInteger p = [your p value]
    String message = "test message";
    BigInteger m = new BigInteger(1,message.getBytes(StandardCharsets.UTF_8));
    if(m.compareTo(p)>0) {
        not good, your message is too big!
    }

Usually in signature schemes, you use the hash value of the message instead of the message, because a hash function has a fixed output size and for a suitable p you can be certain it is always < p.

This is also quite simple, but if you say you want to compute a hash, it is probably not what you want to do?


Is it secure to ECDSA-sign a public key without hashing it first? I am trying to sign an ECDH public key with ECDSA. However, my hardware does not allow me to implement a hash algorithm, considering I am running out of memory already.

Therefore, I am currently just passing the ECDH public key as the message to be signed to the sign function without any hashing beforehand, which is usually advised in any algorithm explanation (see chapter 6.4, http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf).

I have yet to find any evidence or analysis about possible security implications of skipping the hashing step. My intuition would say, that hashing the message serves as a way to blur the original message, essentially avoiding any retracing if the algorithm was somehow compromised.

If this is the case, would it be applicable to simply leave out the hash in this case, considering I am sending the ECDH public key in plain text over the wire anyways?

From FIPS 186-4, section 6.4

  An approved hash function, as specified in FIPS 180, shall be used during the generation of digital signatures.

Thus if the hashing step was removed, then this is no longer ECDSA. Let's call the resulting Modified signature scheme MECDSA.

MECDSA has a potential weakness: it is easily exhibited a valid MECDSA signature for message(s) $m\equiv0\pmod n$: signature $(r,s)$ with $r=s=x_A\bmod n$, where $x_A$ is the $x$ coordinate of the signer's public key $Q_A$; at verification we get $z=0$, $u_1=0$, $u_2=1$, $u_1\times G+u_2\times Q_A\,=\,Q_A$, hence $r\equiv x_1\bmod n$ and the signature verifies. With true ECDSA, it is computationally infeasible to exhibit a message hashing to $0\pmod n$, making this a non-issue.

Update: things get much worse: we can efficiently exhibit an arbitrary number of (message, signature) pairs passing verification (but there's no control on the message); see this answer.

It is not quite clear if MECDSA signs an integer $m$ or a bitstring; and the maximum $m$, or the maximum size of the bitstring:

If $m$ was an unbounded integer, the signature for $m$ would also be valid for $m+n$, where $n$ is the order of the group ($n\approx 2^{256}-2^{224}$ for curve P-256). To solve this, we'd need to restrict to $0<m<n$.
If $m$ was a bitstring of exactly as many bits as $n$, then we would also have a number of bitstrings with interchangeable signatures (about $2^{224}$ such 256-bit bitstring pairs for curve P-256).

In either case, we are slightly in trouble if the public key to sign is using the same curve as used for the ECDSA signature: the usual ("uncompressed") form of a public key is twice as wide as $n$ is; and even with point compression (which is not all that usual, and is not considered by FIPS 186-4), a public key is one bit more than $n$ is. In order to solve this, we'd need to restrict the allowable public keys (e.g. with sign bit clear, and the $x$ coordinate less than $n$, thus removing very slightly more than half of the valid public keys).

An important other issue is that signatures of public keys, also known as public key certificates, typically need attributes, like who they belong to. We could spare a few more bits for a serial number at the cost of further restrictions in the public key, but each bit spared doubles the difficulty of generating a public/private key pair. Thus in the end we might need to sign two messages instead of one, with something to link the two signed messages. That's feasible, but hairy!

With such restriction to signing messages $m$ with $0<m<n$, and non-standard form of public key or/and certificate content, carefully enforced/compensated at verification, MECDSA could be used to sign a public key. But it is clumsy, and is it safe? I'm not entirely sure. That's not a well-studied problem. I would never prescribe it, and would feel very uncomfortable endorsing or doing it, for lack of positive security argument, and because of the usability issues. Hashing is cheap (it can be done in less than 1 kByte of code), and signing hashed message is the way to go.

Addition: here is a tiny (1.2 kiB) implementation of SHA-256

// tinysha256 - a public domain, compact implementation of sha256
// input is limited to 0 to 0xffffffff octets(s) in memory
// gcc 5.3.0 for x386 with -Os compiles this to 1280 bytes
#include <stdint.h>

// hash len bytes in memory pointed by ibuf
void tinysha256(
    uint8_t         hash[32],           // result
    const uint8_t * data,               // input
    uint32_t        size                // input size
    )
    {
    uint32_t s[8] = {                   // init state
        0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19};
    uint32_t w[16];                     // data buffer
    uint32_t x;                         // warning about unitialized x can be safely ignored
    const uint8_t *e = data+size;       // end of data
    int n = 0;
    for(;;) {
        while (data!=e) {               // while there is data..
            x = (x<<8)+ *data++;        // accumulate it in x, big-endian
            if ((3&~n)==0) {            // a full 32-bit chunk
                w[n>>2] = x;
                if (n==63) {
                    n = 0;
                    goto c;             // compression
                    }
                }
            ++n;
            }
        switch(n) {                     // handle padding
        case 64:
            n = x = 0;
            break;
        case 65:
            n = 31;
            do
                hash[n] = s[n>>2]>>((3&~n)<<3);
            while(--n>=0);
            return;
        default:
            x = ((x<<8)|0x80)<<((3&~n)<<3);
            }
        w[n >>= 2] = x;
        while (++n!=14) {
            if (n==16) {                // extra compression needed
                n = 64;
                goto c;
                }
            w[n] = 0;
            }
        w[14] = (uint32_t)(size>>29);   // length padding
        w[15] = (uint32_t)(size<< 3);
        n = 65;
c:          {                           // compression
            static const uint32_t k[64] = {
                0x428a2f98,0x71374491,0xb5c0fbcf,0xe9b5dba5,0x3956c25b,0x59f111f1,0x923f82a4,0xab1c5ed5,
                0xd807aa98,0x12835b01,0x243185be,0x550c7dc3,0x72be5d74,0x80deb1fe,0x9bdc06a7,0xc19bf174,
                0xe49b69c1,0xefbe4786,0x0fc19dc6,0x240ca1cc,0x2de92c6f,0x4a7484aa,0x5cb0a9dc,0x76f988da,
                0x983e5152,0xa831c66d,0xb00327c8,0xbf597fc7,0xc6e00bf3,0xd5a79147,0x06ca6351,0x14292967,
                0x27b70a85,0x2e1b2138,0x4d2c6dfc,0x53380d13,0x650a7354,0x766a0abb,0x81c2c92e,0x92722c85,
                0xa2bfe8a1,0xa81a664b,0xc24b8b70,0xc76c51a3,0xd192e819,0xd6990624,0xf40e3585,0x106aa070,
                0x19a4c116,0x1e376c08,0x2748774c,0x34b0bcb5,0x391c0cb3,0x4ed8aa4a,0x5b9cca4f,0x682e6ff3,
                0x748f82ee,0x78a5636f,0x84c87814,0x8cc70208,0x90befffa,0xa4506ceb,0xbef9a3f7,0xc67178f2
                };
            uint32_t r[8];
            int j = 7;
            do
                r[j] = s[j];
            while (--j>=0);
            j = 0;
            do
                {
#define RL(value, bits) (((value) << (bits)) | ((value) >> (32 - (bits))))
#define S0(x)   (RL((x),30)^RL((x),19)^RL((x),10))
#define S1(x)   (RL((x),26)^RL((x),21)^RL((x),7))
#define S2(x)   (RL((x),25)^RL((x),14)^((x)>>3))
#define S3(x)   (RL((x),15)^RL((x),13)^((x)>>10))
#define S4(x,y,z) ((z)^((x)&((y)^(z))))
#define S5(x,y,z) (((x)&(y))^((z)&((x)^(y))))
                uint32_t t = r[7] + S1(r[4]) + S4(r[4], r[5], r[6]) + k[j] + w[j&15];
                r[7] = r[6]; r[6] = r[5]; r[5] = r[4]; r[4] = r[3] + t;
                r[3] = r[2]; r[2] = r[1]; r[1] = r[0]; r[0] = t + S0(r[1]) + S5(r[1], r[2], r[3]);
                w[j&15] += S3(w[(j+14)&15]) + w[(j+9)&15] + S2(w[(j+1)&15]);
                }
            while(++j!=64);
            j = 7;
            do
                s[j] += r[j];
            while (--j>=0);
            }
        }
    }


Check device authenticity by HASH Hello I'm working in a school project and I'm trying to resolve an issue.
I have a server, a BLE device and a computer.
The BLE device is constantly advertising data, I'm using 7bytes of the data leaving 17 bytes left and I want to use the rest of the bytes to check the authenticity of the BLE device.

So, when a computer is capturing the packages, I need to confirm that that package is really from an authentic device. My idea is:

The BLE device will sign the data (7bytes) with his private key (RSA method).
As the signature is much more than the 18bytes, it will generate a Hash of the signature.
The payload broadcast will result in the data (7bytes) + the hash (16/18bytes)
The computer will catch the broadcast message
The computer will send to the server the entire payload.
The server will have the BLE device private key and will sign the data (7bytes)
The server will generate the hash and will compare it
If it matches the server will send a successful code otherwise an error code.

My concern is it is possible to get the private key by getting the hash of a signed message? I think it is, but I'm not sure, maybe the hash can help in the guess of the private key, I don’t know.

And, this is a good and secure solution? If not do you guys know one better? Thank you.

If an RSA signature is sizably truncated, as is the case here, it can not be verified with the public key. Hence here (necessarily: deterministic) RSA signature is used as a secret-key MAC, and could (and IMHO should) be replaced by HMAC.

That said, no, there is no risk of leak of the private key, or even the lesser risk of the ability to sign. If there was, that would demonstrably be a break of the RSA signature scheme used.

More generally, given access to a black box that performs the textbook RSA private key operation $x\mapsto x^d\bmod n$, there is no known way that $d$ (or an equivalent) leaks, unless the black box has a side-channel leak.


Is TLS 1.2 compression methods in client_hello a mandatory field? As stated int he question, is compression methods list in the client_hello in TLS 1.2 a mandatory field (it is clear that it is mandatory in session_resumption, but not clear to me whether it is mandatory in the new session case)?

Reference to the standard TLS 1.2, RFC 6246, chapter 7.4.1.2 (formatted):

  compression_methods

  This is a list of the compression methods supported by the client,
        sorted by client preference.  If the session_id field is not empty
        (implying a session resumption request), it MUST include the
        compression_method from that session.  This vector MUST contain,
        and all implementations MUST support, CompressionMethod.null.
        Thus, a client and server will always be able to agree on a
        compression method.

Well, it is specified in the ClientHello struct here, and the description reads:

  The ClientHello includes a list of compression algorithms supported
     by the client, ordered according to the client's preference.

And since the client hello is the first message that needs to be send to the server, yes, new sessions should contain this struct, even if the internal value just points to the zero-compression.


Do Quantum Key Distribution and Physical Unclonable Functions combine, and how? I see there's a project to combine Quantum Key Distribution, Physical Unclonable Functions, and classical crypto, in order to secure a high speed (100Gb/s) optical link.

While there does not seem to be a direct combination of QKD and PUF in that particular project, I wonder if that combination could be used to solve one of the problems of QKD: it is by itself not secure against a Man-in-the-Middle attack. Perhaps a PUF could solve that by some synergy with QKD (the issue seem to be: make it impossible for a MitM to appear holding the legitimate PUF, when he really is using the legitimate one remotely).

Are the QKD and PUF combined for that purpose? It yes, how, and how is it superior to the combination of classical crypto (which can solve MitM) and PUF (which should prevent cloning of the credentials), without QKD?

Reformulation: One problem with proof of ownership of a PUF (especially of the silicon memory kind envisioned in my first reference) is that they can be relayed, so that the verifier may believe he is interacting directly with the PUF, when in reality he is interacting with the PUF through some hostile proxy/MitM. My question is about using a quantum protocol to solve that, which hypothetically could make sense with some PUFs, e.g. optical. Perhaps this should be migrated to the physics site (but I have not the foggiest idea how).

It seems difficult to combine the two. PUFs can provide authentication but they are based on the sender having first built up a small number of challenge/response pairs before handing the PUF over. So if Alice gives the PUF to Bob, Alice can authenticate Bob with the response. However if the protocol is two-phased, where Alice authenticates Bob and then they do QKD, the MITM will just jump in at the second phase. So the idea is that PUF-based authentication needs to be binded to the key generated during QKD.

For example, Alice and Bob could perform QKD but treat the output as a challenge, and the response from the PUF is their shared secret key. Unfortunately, the number of possible outputs is too large for building up a set of challenge/response pairs. Without jumping into using classical cryptography, I don't see a way that the addition of a PUF could be useful.


Toy encryption system that provides "hints" I'm looking for a toy encryption system that has a specific property that when decrypting it with a key that is close enough to the key used in the encryption, it will produce some of the original plain text.

The idea is to use it as a game/teaching system where kids can try to break a cyphertext but instead of using cryptanalisys on the cyphertext, I want them to try different keys and then the decrypted text would provide feedback as of how close the key really is, for example:

I encrypt

attack at dawn with key 1234

and let's say the cyphertext is

ABCDEFGHIKLMN

now, if I try to decrypt the cyphertext with key, for example, 1288, it should display some of the plaintext, in order to hint the breaker that the key is somewhat close to the real one

think of it as an encryption system a la Mastermind

A simple substitution cipher kind of does the trick, but I'm wondering if there are other ciphers that behave that way (preferrable with smaller key space)

You can try NSA's CryptoKids page (archived here). It's been around for some years and the ciphers have varying difficulty so you might at least get some ideas.

Alternatively you can use plain XOR encryption with a twist: Encrypt multiple consecutive letters with the same character. For example, if $|m|=n$ then $|k|=n/4$ and do $c_i,...c_{i+4}=k_i \oplus m_i,...,m_{i+4}$. That should give good feedback with every correct guess.


How would one crack a weak but unknown encryption protocol? I asked a question on security.stackexchange, but was told it would be a better fit here:

https://security.stackexchange.com/questions/32779/how-would-one-crack-a-weak-but-unknown-encryption-protocol

My question is: Assume I'm an attacker trying to break a weak-but-unknown encryption algorithm. i.e., someone not too bright made a home-brew encryption algorithm, and I'm trying to break it.

BIG FAT DISCLAIMER: Using home-brew security algorithms is very bad for many reasons. Everybody in the security community agrees about it. It's very hard to keep algorithms secret. Please don't answer this question explaining why it's a bad idea to use a home-brew algorithm. I know it's bad. Assume the algorithm is completely unknown.

Okay, now back to my question.

How would you approach a completely mysterious ciphertext when you have no idea what algorithm was used to make it? For me it would look like a meaningless stream of hex, but I'm very curious to know if there's a method to analyze such data and try to break the code.

Here's an example of such a ciphertext.

Is there a way to break it using a single ciphertext? If that's very difficult, I'll be happy to learn how to do it from multiple ciphertexts. I can create more ciphertexts using the same home-brew algorithm, if someone here thinks he can use that to figure out the algorithm.

It depends on what information you have. If all you have is that one ciphertext and no way of acquiring more, there's not much you can do.

If you have multiple ciphertexts, you can try to observe any patterns in them. If you have the corresponding plaintexts, you can really start to make some useful observations. If you have some plaintext, ciphertext pairs, you can try to find patterns in the data.

An even stronger attack would having access to the encryption oracle. That is, being able to encrypt plaintexts of your choosing. Here you could try special encryption strings to see if they leak any information about the algorithm. You can try things like "a", "aaaaaaa", or string of null bytes and see what information you can extract about the algorithm.

If the encryption algorithm is insecure, your goal should be to figure out what the algorithm does. Once you know how the algorithm works, you can presumably figure out a way to break ciphertexts or get the key.


What happens when a root CA loses its private key? Certificate Authorities normally keep their private keys inside dedicated Hardware Security Modules (HSMs).

What happens when such a device is lost (fire, electronic fault, stolen, etc)?

How would that affect a big, established CA such as Comodo?

EDIT: I have seen the question about the key being compromised (see comments below), but my question is about the key becoming inaccessible.

What happens when such a device is lost (fire, electronic fault,
  stolen, etc)?

Assuming the HSM is stolen: The CA will likely inform the police so they can hunt the thief down, then they will ensure that the thief has actually only stolen a brick (that is, they can't do anything useful with the HSM) and finally they will just continue business as usual and maybe inform the CA/B mailing list about this incident.

Assuming the HSM is no longer available to other reasons: The CA will ensure that the key material inside the HSM is no longer retrievable and then give it into the trash.

In either case: The CA will likely acquire a new HSM (or a new set of HSMs) and restore the key material from the other HSMs they have and import it into the new HSM(s). That's the big difference between HSMs and smart cards: With smart cards you usually can't get the key out at all. With HSMs you can get encrypted copies out of the HSM that can be read and used by other HSMs of the same type, given that they have been initialized in the same way. Also decent CAs will have their root keys at at least 2 different physical locations, exactly to deal with this type of scenario.


Is it Possible to Generate a Duplicate DH Session Key from 2 Pairs of DH Keys? This might sound pointless at first, but I want to know if it's computationally feasible to generate the same resulting session key in 2 different DH key exchanges.  The purpose would be for a man-in-the-middle attack where both of the unsuspecting target users check to make sure they're using the same session key.

The way I am thinking it would work is that Eve establishes a normal DH key exchange with Alice.  She then does a key exchange with Bob where she uses specially-crafted responses to end up with the same session key she generated with Alice.

Is it possible, and how would this work in practice?  I'm guessing it would either be impossible or extremely time-consuming with large primes, etc., but that's just a quick assessment.  Thanks!

If you're doing Diffie–Hellman in a group $G$ written multiplicatively with identity element $e$, say $G = (\mathbb Z/p\mathbb Z)^\times$ for some standard large safe prime $p$ and $e = 1$, then Eve/Mallory can simply supply $e$ as their public key to both Alice and Bob.  Then the shared secret group element is $e^a = e = e^b$.

There is a way for Alice and Bob to thwart this, by simply checking whether the peer's public key is the identity element.  But it's usually pointless because Alice and Bob will normally authenticate the entire transcript of the session—this thwarts the attack anyway because they will authenticate $g^a$ and $g^b$ as their public keys, not $e$.


Using Diffie–Hellman without a key derivation function In an answer to another question, it was suggested that the shared secret derived from Diffie–Hellman key exchange could then be used directly as a one-time pad to encrypt a message (by XORing the message with the shared secret after writing everything in binary). This forms a simple hybrid cryptosystem.

User fgrieu writes in the comments that this has a flaw, saying:

  "you may use its resulting shared secret as a one-time-pad": but this
  less than satisfactorily secure! If one simply XORs the message with
  the shared key and sends the whole result, then it is possible to
  recognize which of two messages was sent with probability sizeably
  better than random. There is a similar issue with ElGamal encryption.
  Problem is: in $\mathbb Z ^*_p$, Diffie–Hellman leaks the Legendre symbol of the
  shared key. That's one reason we stick a key derivation function on
  top of DH.

Recall that the Legendre symbol determines whether an element of a group is a quadratic residue.

Could we fix this by choosing an element $g$ that generates a large subgroup, all of whose elements are quadratic residues? Concretely, we could take $p= 2q + 1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.

Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order bit of the shared secret. So I could just remove this bit and use all the higher order bits as the one-time pad, and no information about the shared secret leaks.

Is this scheme secure, assuming an eavesdropper can't break Diffie–Hellman? Even if the particular flaw fgrieu points out is fixed by this scheme, are there other compelling reasons to combine Diffie–Hellman with a key derivation function?

The Wikipedia page for Diffie–Hellman notes that IKEv2 chooses the public group element this way. However, they do not say whether a further key derivation function is applied.

Could we fix this by choosing an element $g$ that generates a large subgroup (of $\Bbb Z_p^*\ $), all of whose elements are quadratic residues? Concretely, we could take $p=2q+1$ for a large prime $p$ and then find an element which generates the order $q$ subgroup.Now, if Diffie–Hellman is done with this group element, any eavesdropper knows the lowest order bit of the shared secret. So I could just remove this bit and use all the higher order bits as the one-time pad, and no information about the shared secret leaks.

That's not safe. Problems:

What the adversary learns is not the low-order bit of the Diffie-Hellman shared secret $a$ as stated. Rather, what leaks is the Legendre symbol $\bigl(\frac ap\bigr)=a^q\bmod p$, which is always $+1$. Therefore, even if we remove the low-order bit, the adversary still learns something about the shared secret, and that's an advantage.
E.g. with $p=23$, $q=11$, $g=3=7^2\bmod p$, the adversary knows that $a$ is among the powers of $g$ modulo $p$, that is $a\in\{3,9,4,12,13,16,2,6,18,8,1\}$ (which low-order bits are rather haphazard). Thus for example if the ciphertext is $101_2$, the adversary can tell that the plaintext can not be $000_2$, because that would imply that $\lfloor a/2\rfloor=000_2\oplus101_2=101_2=5$ thus that $a\in\{10,11\}$, which can't be since $\bigl(\frac{10}p\bigr)=10^q\bmod p\ne+1$ and $\bigl(\frac{11}p\bigr)=11^q\bmod p\ne+1$.
That attack also works for large $p$ and in practical scenarios. E.g. if a name on the class roll was enciphered, then at the cost of two Legendre symbol computations per name on the class roll (one for each of the two possible DH shared secrets), an adversary likely could rule out with certainty about a quarter of the names (those with two negative results), and find another quarter (those with two positive results) among which the actual name is more likely to be than for the remaining of the class roll.
The high-order bit of $a$ expressed as a fixed-length bitstring of $\lceil\log_2(p)\rceil$ bits is not well distributed.
If $q$ has moderate prime factors, then I can't rule out that much more than one bit of information about the shared secret could leak due to the Pohlig-Hellman algorithm.

I conjecture that this variant is safe (ind-CPA):

Pick $p$ a safe prime (that is $p=2q+1$ with $q$ prime), $p$ large (e.g. $4096$-bit), and not of the special form $r^e\pm s$ for small $r$ and $s$.
Chose $g\in[2,p-2]$ such that $g^q\bmod p=1$, implying that $g$ is a generator of the subgroup of the quadratic residues of $\Bbb Z_p^*$, which has prime order $q$.
Perform DH as usual, yielding shared secret $a$.
Truncate $a$ to its e.g. $\lceil\log_2(p)\rceil-k$ low-order bits yielding $a'$, where $k$ is a security parameter (e.g. $k=128$, giving a $496$-byte $a'$).
Use $a'$ for XOR-encryption of a plaintext at most as large as $a'$ (or best, devote some of $a'$ to provide integrity of the message using universal hashing à la Carter-Wegman).

Argument: DH's security hypothesis tells that $a$ is computationally indistinguishable from a uniformly random quadratic residue in $\Bbb Z_p^*$, since that has prime order. I conjecture that these quadratic residues are well-enough distributed on $\Bbb Z_p^*$ that $a'$ is computationally indistinguishable from uniformly random, with the advantage vanishing as $\mathcal O(2^{-k})$.

This is possibly the simplest academically correct way to perform ind-CPA public-key cryptography on a link spied by a passive adversary. But caution: this not commonly used. The accepted practice is to feed the DH shared secret $a$ thru a Key Derivation Function, or Pseudo Random Function / hash such as SHA-256, and use the outcome as a key for an authenticated symmetric cipher such as AEAD_AES_256_GCM_SIV of RFC 8452.


Using same encryption key in different schemes Is it safe to encrypt possibly same plaintexts with 2 different algorithms using same secret encryption key? This question is similar to this question except they use 2 keys. More formally:

$E_k(m) = E_{1,k}(m)||E_{2,k}(m)$

I understand that this could be easily made secure by producing few more keys out of the one key that is provided by, for example, using a stream cipher over predefined plaintexts or by hashing the key with predefined prefixes. I am wondering if there are any non-obvious problems with mixing schemes. I suspect there may be, since both ciphertexts together provide more information to an attacker than each ciphertext alone.

Consider this. Both schemes use 512 bit keys. First encryption outputs a ciphertext that is a function of message and first half of the key, concatenated with second half of the key in the clear. This scheme is secure in itself, because the key bits essential to security are kept secret. Remaining bits are considered junk. Second encryption does the opposite where first half is outputed in the clear. Together, entire key is revealed.

On side note, I am aware that same RSA keys should not be used for encryption and authentication. GPG uses separate keys. Feels like a similar issue.

I understand that this could be easily made secure by producing few more keys out of the one key that is provided by, for example, using a stream cipher over predefined plaintexts or by hashing the key with predefined prefixes.

This would be the task of a Key Based Key Derivation Function or KBKDF for short. HKDF is such a KBKDF that quickly has made inroads. It is possible to construct keys using other methods as well, but basically you'd be creating simplified KDFs.

So usually it is better to use a KDF to derive each separate key.

  I am wondering if there are any non-obvious problems with mixing schemes. I suspect there may be, since both ciphertexts together provide more information to an attacker than each ciphertext alone.

As you already found out, it is very easy to create a set of two theoretical ciphers where reusing the key is insecure. You could however take a set of normal ciphers that are very different. In that case you have to find an equation where one cipher leaks information about the other, or you have to retrieve the key from one of the ciphers (i.e. breaking it). Nobody here is going to take two of the final AES candidates and break this scheme.

  On side note, I am aware that same RSA keys should not be used for encryption and authentication. GPG uses separate keys. Feels like a similar issue.

Now you're getting into dangerous waters. Unlike the AES candidates keys for asymmetric ciphers generally have a specific structure that is tied to the algorithm (e.g. RSA). So you can probably only use them for algorithms that are directly related. In that case it might very well be that you leak information and possibly even the key.

The same indeed goes for cipher modes that simply split the key into multiple parts such as SIV of course. You would not want any key reuse for those kind of modes of operation.

Note that besides theoretical issues there may be practical issues as well. Many API's won't allow you to use a key of one specific type as another. Imagine you've got an RSA or AES key in a HSM. You cannot just use that for any other algorithm.