How does the PRESENT cipher's permutation affect all rounds when it repeats after every three rounds? I heard that the permutation in PRESENT affects all bits after only a few rounds. However, when I looked at it the bits return to their original position after only three rounds. For example, in round-1 bit b1 ---> b16, in round-2 b16 ---> b4, and in round-3 b4 ---> b1; thereafter the cycle repeats. This is the same for all bits, except b0, b21, b42 and b63 which do not move at all.

So my question is: this being the case, how does the permutation cause each bit to affect every other bit?

I am sure I have missed the point, so a simple 'numerical' example would be much appreciated.

Yes, you might think that the bits return to their original positions.  But they don't because those aren't the bits you're looking for.  They've changed.  Specifically, you need to consider the effect of the s-boxes.  If a single bit goes into a s-box, it's very nature means that on average, two bits come out.  Similarly, if three bits go in, two bits still emerge on average.  This is the substitution component of PRESENT.  What you've focused solely on is the permutation component.  To achieve full and proper diffusion of bits throughout a substitution /permutation network (SPN), you need both components to work together.

This repetitive substitution and permutation (what Shannon termed confusion and diffusion) creates an avalanche effect through the internal state.  If such a network happened to have the same number of s-boxes as their width (ie. 8 boxes of 8 bits), you would achieve full avalanche effect in two rounds.  If the ratio is different like PRESENT's 4/16 construction, full avalanche won't occur till more rounds happen.  It's a function of the ratio.  I don't know how many rounds PRESENT needs, but it clearly happens way before the total 31.  These networks tend to have a very generous and conservative round count to help security.

So it's the effect of the s-boxes in conjunction with the permutation that ensures all bits affect all other bits.  The diagram below is for a generic SPN but illustrates a bit's travel through it:-

One bit went in and as expected on average 8 bits come out.  It simply doesn't work if you just consider the permutations on their own.


Calculating private keys in the RSA cryptosystem The number $43733$ was chosen as base for an implementation of the RSA system.
$M=19985$ is the message, that was encrypted with help of a public key $K=53$.

What is the plaintext text?
What is the private key?

So far, my calculations are:

$n=pq$
$n=101*433$
$\phi(43733) = (101 − 1)*(433 − 1) = 43200$.
The public key is $(n = 43733, e = 53)$.
The private key is $(n = 43733, d = 12343)$.

However, I'm not sure if this is right? Where am I going wrong?

The public key is $K = e = 53$, already given. $n$ (the modulus) must also be given, so you could say that $(e, n)$ is the actual key.

The private key is $d$ which must satisfy $d * e = 1 \mod \phi(n)$.
So you're looking for $d$ for which $(53 * d) \mod 43200 == 1$. A quick brute-force search (with such small numbers it's not a problem) reveals that $17117$ satisfies this equation.

Now $N=43733$, and you're guaranteed that $(M^e)^d = (M^d)^e = M \mod n$.

Your message is $M=19985$:

$19985^{53}  \equiv 17195 \mod 43733$
$17195^{17117} \equiv 19985 \mod 43733 $

This shows that you can encrypt using the public key and decrypt using the private key.
The opposite also works (for signing the message):

$19985 ^{17117}  \equiv 125 \mod 43733$
$125 ^{53} \equiv 19985 \mod 43733$

There are better ways to find $d$ from $e$ if you know $\phi(n)$. But if you don't, you're in trouble, because you need to factorise $n$ to do that.


LFSR Tap sequence 15 bit LFSR I have been asked to create an LFSR with a polynomial of x^15 + x + 1 and i am confused where the tap sequence would go.

The examples I was given show a 4 bit tap sequence with two polynomials: x^3 + 1 and x^2 + 1. These were shown having tap at positions 0101 and 0101 respectively, where the bold represents the tap sequence.

I am confused about where the tap sequence would go for x^15 + x + 1, since in the first above example, there is 4 bits but taps are at either ends with the polynomial x^3+1. So how would x^15 be placed on a 15 bit LFSR? surly it would not fit? (x^14 + 1 being taps at either end of the 15 bit LFSR following the examples?)

I have written code for this also and have placed taps 000001111100000, which i think is the correct tap sequence, however this outputs only 14 bits, being way under what i estimated. 0s and 1s being different then mentioned above. This also doesnt match the 4 bit examples i was given which is confusing me very much.

Where am i going wrong, any advice on this would be appreciated, thanks.

Let $[s_0, s_1, \ldots, s_{14}]$ denote the initial contents of the shift register (which holds 15 bits). The output sequence is
$$s_0, s_1, s_2, \ldots, s_{14}, s_{15}, s_{16}, \ldots$$
in that order with $s_{15}$ being the first computed bit that is fed back into the shift register. That is, $s_{15}$ is computed as a linear function (meaning XOR operations) of the initial contents $[s_0, s_1, \ldots, s_{14}]$ of the shift register which then shifts its contents one place leftwards with $s_0$ being sent out into the dark dirty world while $s_{15}$ enters the shift register on the right, thus making the shift register contents $[s_1, s_2, \ldots, s_{14}, s_{15}]$. Thus the change in shift register contents looks like
$$(s_0, \quad s_1, \quad \ldots, \quad s_{13}, \quad s_{14})\\
\downarrow\\
(s_1, \quad s_2, \quad \ldots, \quad s_{14}, \quad s_{15})\\
\downarrow\\(s_2, \quad s_3, \quad \ldots, \quad \quad s_{15}, \quad s_{16})\\
\downarrow\\
\cdots \quad \cdots$$
and more generally as

$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+13}, \quad s_{i+14}\biggr)\\
\downarrow\\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+14}, \quad {\Large{\oplus}}_{j=0}^{14}c_{15-j} s_{i+j}\biggr),$$
where $c_{15}x^{15}+c_{14}x^{14} + \cdots + c_1 x + c_0 = x^{15}+x+1$ is the feedback polynomial. In other words, $$s_{i+15} = c_{15}s_{i}\oplus c_1s_{i+14} = s_i \oplus s_{i+14}$$ and so the taps are on the zero-th and the 14th stage of the shift register.

Just be aware that there is an alternative convention which defines the feedback polynomial as $c_0 x^{15} + c_1x^{14} + cots + c_{14}x + c_{15}$ which would change the tap locations.


How exactly does key whitening manage to increase security? Wikipedia states that key whitening increases security:

In cryptography, key whitening is a technique intended to increase the security of an iterated block cipher. It consists of steps that combine the data with portions of the key.
The most common form of key whitening is xor-encrypt-xor -- using a simple XOR before the first round and after the last round of encryption.

But Wikipedia does not explain in what way exactly key whitening manages to increase security.
Reducing it to a minimum, it seems as if the most used form of key whitening is a triple-encryption using a XOR-cipher + Other-Encryption-Algorithm + XOR-cipher combination. A XOR can be reversed rather easy (which is why XOR-ciphers aren’t all too secure), so how does key whitening manage to increase security using two simple XOR steps like that? Does it really make the cipher stronger in some special way, or is key whitening just an obfuscation-step to give attackers a hard time?

While it may be confusing, that Wikipedia article is actually correct! Let me try to explain it a bit better…

Definition of key whitening

Key whitening is an extremely simple technique to make block ciphers like DES much more resistant against brute-force attacks. Like you’ve already discovered yourself, this is the basic scheme:

Or, defining it a bit more mathematically…

Encryption: $y = e_k,k_1 ,k_2 (x) = e_k (x \oplus k_1 ) \oplus k_2$
Decryption: $x = e_k^{-1},k_1 ,k_2 (x) = e_k^{-1} (y \oplus k_2 ) \oplus k_1$

In addition to the regular cipher key $k$, two whitening keys $k_1$ and $k_2$ are used to $\oplus$ (XOR-mask) the plaintext and ciphertext.

Security added by key whitening

Now, it is important to stress that key whitening does not strengthen block ciphers against most analytical attacks such as linear and differential cryptanalysis.

So, your observation/interpretation is somewhat correct.

Key whitening indeed isn’t a “cure” for inherently weak ciphers or something like that. Its use only makes sense when ciphers are relatively strong against analytical attacks, but possess a too short key space.

Trying to use your wording: key whitening can only increase security by strengthening a cipher where its key space is too short. That’s it. When it comes to increasing security, you won’t gain anything else from a key whitening step.

Ciphers using key whitening

A prime example of such a cipher would be DES. A variant of DES which uses key whitening is DES-X. In the case of DES-X, the $k_2$ is derived from $k$ and $k_1$.

If you take a look around, you will notice that most modern block ciphers already apply key whitening internally by adding a sub-key prior to the first round and after the last round… prime example: AES.

An aside: In case you want to dig in deeper, it might be interesting for you to check out books like “Understanding Cryptography”  by Bart Preneel, Christof Paar, and Jan Pelzl; or “The Block Cipher Companion” by Lars R. Knudsen, and Matthew Robshaw.


Does a high exponent compensate for a low degree of certainty? If a RSA certificate is created with a low degree of certainty, does the value of the exponent compensate for this?

I'm asking because certain implementations of key generation software hide the certainty value from the administrator, and I'd like to find reassurance in any other parameter.

If the exponent doesn't compensate for this, does a longer key length compensate for certainty?

Well, no, having a longer exponent really doesn't compensate for low degree of certainty in the RSA key generation.

As you are well aware, the most common method for generating RSA keys involves finding primes by picking numbers, and using a probabilistic method to verify whether those numbers are prime.  These probabilistic methods have a small probability of claiming that a composite number is prime; the certainty factor that some implementations ask for is an indication of how small this error probability should be.

Now, if the certainty factor is too low, the error that might result is that one of the "primes" that are picked isn't really a prime.  This can cause two errors:

The RSA key might not work (or, at least, not consistently).  For example, if the RSA key is used for public key encryption, the private key might not correctly decrypt something encrypted with the public key.
The RSA key might work; this will happen if the 'prime' that got chosen happens to be a Carmichael number; that is, a composite number $n$ for which $x^n = x \mod n$ holds for all $x$.  Now, Carmichael numbers are rare (far rarer than primes), but they do exist.  The potential problem is that Carmichael number often have small factors; if someone notices that the RSA key has a small factor, they might be able to figure out the other factors of the Carmichael number, and thus factor the RSA key.

In both cases, using a larger public exponent won't help.  A larger RSA key also won't help much for case 1 (other than making it less likely that a nonprime will sneak through).  It might for case 2, but I wouldn't be real confident about it.

Now, if the key generation software doesn't allow you to specify a certainty factor, it means that either:

The software has a preset certainty factor build in; one would hope that it is set fairly conservatively (perhaps about as likely as hardware error), but you can certainly ask
The software doesn't use a probabilistic method.  There are deterministic methods of finding primes (such as the Shawe-Taylor algorithm, see A.1.2.1) that are approximately as efficient as probabilistic methods; perhaps those libraries do that.

On the other hand, if you don't trust some key generation software to do the right thing, perhaps you shouldn't use them.  There are some nasty things that a bugged RSA key generation software can do.


Cryptography's random number problem? Sophie Chen at Wired Magazine;

  quantum mechanics could solve cryptography's random number problem

Such machine already exist, but it's too huge and not so fast in order to use it all the time.

Anyway, can it solve the problems connected to randomization and security or it will be still vulnerable?

The title of this article is complete hype. Tip: when a journalist says “X could solve Y”, read “X probably won't solve Y”. Much of the content of the article is hype too.

Cryptography has a random number problem, but the problem is not producing random numbers, and the proposal in this article wouldn't be useful to produce random numbers anyway.

Cryptography does need random numbers for many things. The problem of obtaining random numbers can be divided into three parts: generating sufficient entropy for security, generating a sufficient quantity and quality random numbers for the applications, and actually bringing the random data where it's needed. The first problem is solvable, the second is solved, the third one is where the difficulty is.

To generate random numbers, it's necessary to have a source of non-determinism. A deterministic computer, by definition, is incapable of producing anything random. But there is no need for any expensive machine using quantum mechanics. Classical mechanics or cheap applications of quantum mechanics are good enough in practice. Your PC has a random number generator, if it isn't an antique. Your phone probably has one too, if it's a not-too-old smartphone. If your credit card has a chip, it has a hardware random generator. You can find microcontrollers that cost a few cents (I'm talking bulk prices here) that have a built-in RNG. Many devices lack one (your home router might not have one), but at current prices it's a supply chain and requirements problem, not a cost problem. If you can control how a device is designed, there's no excuse not to include a hardware random generator.

A hardware random generator gives you entropy, but it isn't directly usable for cryptography. It usually has limited bandwidth and biases (no measurement apparatus is perfect). Fortunately, turning an entropy source into a cryptography-grade random generator is a solved problem. All you need to do is to use the entropy source to seed a pseudorandom generator. Any cryptography library has one or more PRNG available.

The real problem with random numbers in practice is getting all the software out there to use them correctly. This is a difficult problem to solve because every piece of software needs to get things right: properly relay the data, don't leave a copy lying around. The operating system driver needs to get it right, the system installer needs to get it right, all the layers of software libraries need to get it right, and the application needs to use the libraries properly. Proper use of randomness is near-impossible to test, so bugs are difficult to detect. Common problems include developers using non-cryptographic random generators when they need cryptographic ones (don't use rand anywhere near cryptographic code!), using a cryptographic PRNG that is not seeded properly (always use your OS's randomness source such as /dev/urandom or CryptGenRandom), using non-random inputs to functions where random input was needed, and systems where the entropy source is not configured properly.

So when the article says

  Eventually, it would be great if they shrank the setup to fit on a chip, says Bierhorst: a random number generator in every laptop, so that nobody ever uses those algorithm-based numbers for encryption again.

that's attacking the part of the problem that doesn't need new technology. The reason people use “algorithm-based numbers for encryption” is that either their device lacks a generator which can be built cheaply using current technology, or that there's a problem in the software. This new machine would not help with either part of the problem.

As for the proposed application of a “randomness beacon”, it's a plausible one, but it's of limited use and difficult to put to practice. A randomness beacon, as the article explains, is useless for most cryptographic applications since it wouldn't be secret. It's useful as an impartial arbiter, for example to assign auditors to auditees, but that can be done with any source of randomness. The fact that the machine itself is more difficult to “hack” than a PC with RDRAND is not all that useful, because the hacking could be done in the reporting and logging system.


Can I use the output from a DRBG directly as K for AES, or do I need to use a key generator algorithm? NIST has 3 validated "Recommendation for Random Number Generation Using Deterministic Random Bit Generators" (DRBG's) that are based on NIST SP 800-90A:

Hash_DRBG (based on hash functions)
HMAC_DRBG (Based on Hash-based message authentication code)
CTR_DRBG (based on block ciphers)

If I need a 256-bit key for AES encryption, by using one of the above mentioned DRBGs and getting output from it as K, can I use K for AES encryption directly? or I must use K as an input of other algorithm that is called key generator and the output of key generator will be key?

It you need a deterministically derived key for AES, the DRBG algorithms of NIST SP 800-90A are suitable, and their output is directly usable as an AES key. An example use case is when computing an AES session key from a longer-term master key, and the nonce corresponding to that session.

AES will expand its key (128, 192 or 256-bit) to 128-bit subkeys (one more than there are rounds, thus 11, 13, or 15 subkeys), using an algorithm known as the AES key schedule, but that's considered internal to AES.

Notice that any DRBG needs a seed input, and that must be random and secret, thus best generated by a True RNG.

Update following comment: to my knowledge, NIST has no publication fully describing a particular TRNG (which they designate as nondeterministic random number generator); the closest thing (pointed by Thomas M. DuBuisson) seems to be draft NIST SP 800-90B, which gives general recommendations for (mostly: the conditioning of) entropy sources.

NIST does have publications, in particular FIPS 140-2, on how a TRNG should be tested (both during use and for certification purpose) and used; quoting that (as current in 2003):

  Until such time as an Approved nondeterministic RNG standard exists, nondeterministic RNGs approved for use in classified applications may be used for key generation or to seed Approved deterministic RNGs used in key generation. Commercially available nondeterministic RNGs may be used for the purpose of generating seeds for Approved deterministic RNGs. Nondeterministic RNGs shall comply with all applicable RNG requirements of this standard.

Quoting a 2012 draft of annex of FIPS 140-2 annex C on RNGs

  There are no FIPS Approved nondeterministic random number generators.

NIST maintains a list of cryptographic devices with a certificate made in relation to the aforementioned publications.


Is TripleDES 168bit vulnerable to Differential Cryptanalysis? I was reading this paper. In the table-1 of the paper it says  TripleDES (showing both 128bit and 168bit keysize) is vulnerable to Differential Cryptanalysis. It also says that AES (showing all three keysize) is strong against Differential Cryptanalysis. If AES-128bit is secure against Differential Cryptanalysis then why not TripleDES-168bit as well?

So, is it the paper that the authors haven't made it clear or is it true that TripleDES 168bit keysize is vulnerable to Differential Cryptanalysis attack?

This claim is bogus. DES itself has a 13-round differential with probability around $2^{-47}$, so TripleDES with its 48 rounds is resistant to any sort of differential attack.

The paper authors are not really competent in the subject.


What is Universal Circuit $U_{e}$ I was reading research Paper. In which writer talks about universal circuit. I want to know how is universal circuit $U_{e}$ different from simple circuit. What properties they have. Is they hide structure of simple circuit

A universal circuit is one that can compute any circuit. Specifically, it receives as input the description of another circuit and an input, and it outputs the computation of the given circuit on the given input. In cases where you want to hide the structure of the circuit being computed, a universal circuit can achieve this for you.


Is a 4DES or 5DES system possible? We know that 3DES is created with $E_{K_3}(D_{K_2}(E_{K_1}(m)))$ to extend DES's key length. Is it possible to extend it further by repeating this pattern? Perhaps using $E_{K_5}(D_{K_4}(E_{K_3}(D_{K_2}(E_{K_1}(m)))))$ for a 280 bit key.

There is a very interesting paper that relates to this exact question (but you wouldn't guess it from the title). The paper is titled Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems. In Section 3, the paper considers the multiple encryption problem and gives novel attacks that are better than what you would expect (for a general multiple encryption $r$ times). For example, for 2DES there is an attack taking about $2^{56}$ time and $2^{56}$ space. You would therefore expect that 4DES would give you $2^{112}$ time and $2^{112}$ space. However, they show an attack that takes time $2^{112}$ and only space $2^{56}$.

In any case, in practice there is no good reason to use this. You are far better off using AES. DES's block size is too small, and it is very slow as it is (repeating 4 or 5 times will completely kill you).


A question regarding next-bit predictors Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows.
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}.
\end{equation}
Here, $X_i$ indicates the $i^{\text{th}}$ bit of $X$. Consider that this predictor exists. Intuitively, if I understand correctly, this means that there should be a "gap" between the bit $X_k$ and the bit $\overline{X_k}$ (complement of $X_k$); otherwise the algorithm $A$ should not exist. In other words, I think that the existence of an algorithm $A$ implies
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \geq \frac{1}{\text{poly}(n)},
\end{equation}
or something similar to this, with respect to the statistical property of the $k^{\text{th}}$ bit. I couldn't prove this mathematically.
Is my intuition correct and can it be made mathematically rigorous?

I tried proving my intuition, but I am still stuck. Here is my attempt.
We can show that the fact that $A$ exists and acts as
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} + \frac{1}{\text{poly}(n)}.
\end{equation}
implies
\begin{equation}
\underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}] \geq \frac{1}{\text{poly}(n)}.
\end{equation}
Now, I am trying to show
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ \geq \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}].
\end{equation}
In other words, the proof reduces to proving
\begin{equation}
\underset{X \sim D}{\text{Pr}}[X_k~|~X_1X_2.....X_{k-1}] - \underset{X \sim D}{\text{Pr}}[\overline{X_k}~|~X_1X_2.....X_{k-1}] \\ = \max_{A}\left( \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1}) = X_k] - \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})= \overline{X_k}]\right).
\end{equation}
If I start with the contrapositive of the statement, I end up in the same place. I think I am missing something subtle. In spirit, the statement our proof reduces to is similar to a very similar-looking result relating total variation distance between two distributions with distinguishability bias of the best algorithm (like this answer). But also, it is not quite the same: as we only have one distribution now, not two, and retracing the same steps does not work.

[SEE UPDATE BELOW] This is a very interesting question. Basically what it means is that if there exists a next-bit predictor, then there is a canonical distinguisher $D$ that outputs the $k$th bit and does nothing else. This is a good distinguisher since the $k$th bit equals 1 with probability that is polynomially bounded away from a random bit. I find this intuitively appealing and was first surprised. However, it does make sense.
As a sanity check, let's see what would happen if on the extreme:
$$
Pr_{X\sim D}[X_k=1 \mid X_1X_2\ldots X_{k-1}] = Pr_{X\sim D}[X_k=0 \mid X_1X_2\ldots X_{k-1}].
$$
This would mean that $X_k$ is actually independent of $X_1,\ldots,X_{k-1}$ and is a random bit. In such a case, it is clear that $A$ could only predict the next bit with probability $\frac12$. As a result, I think that this could be proven in the contrapositive.
I won't do all of this here; there is good value in you working it out. In order to get the direction, I propose that you look at the proof of equivalence of next-bit unpredictability and pseudo randomness. One place to see this is Section 7.3.2 of this chapter on Pseudorandomness by Salil Vadhan.
Let me know if it doesn't work out from here.
==================================
I'm leaving the above for the didactic value, but I'm no longer sure that this is correct. The problem is the conditioning. In particular, once we condition on $X_1,\ldots,X_{k-1}$, then we are completely changing the probability space. (General recommendation - it's really easy to get conditioning wrong so stay away if you can. This was a recommendation given to me by my advisor. You can't always avoid it, but you need to be really careful.) In more detail, it could be that for \emph{many} given $X_1,\ldots,X_{k-1}$, the $k$th bit $X_k$ is polynomially biased away from $1/2$. The problem is that you don't know how to recognize the prefixes where this holds. Of course, this means that it can't happen with high probability (or a non-uniform distinguisher could hold some prefixes as advice). I think part of the confusion is what it even means to sample a full $X$ and then condition on $X_1,\ldots,X_{k-1}$. I think what you mean is that: for every $X_1,\ldots,X_{k-1}$, the probability of $X_k=1$ when the sample of $X$ has the given prefix of $X_1,\ldots,X_{k-1}$ is bounded away from $1/2$. I don't think this would be correct. If you mean something else, then it's worth thinking about.
I guess the important question is what you are trying to show and why, or possibly it's just understanding (which is good within itself).


Regular MACs vs Carter-Wegman MAC Carter-Wegman MAC variants (VMAC, UMAC etc) are known to be very fast and efficient when compared to MAC algorithms that are based on block ciphers and compression functions (like HMAC, CMAC etc).

However, Carter-Wegman MAC variants are not very popular on the internet like HMAC. Why is this so? Do Carter-Wegman MAC variants have some disadvantage that prevents them from being widespread?

A lot has changed recently in this area. Now the only ciphersuites Chrome considers non-obsolete (those that use AES-GCM or ChaCha+Poly1305), do use Carter-Wegman MACs.

So, I would say that there is no disadvantage and that any low popularity has been just an artifact of historical decisions in standardization. Secure hashes were the first to be openly standardized and exportable, so they were used for MACs as well.


AES-GCM for Securing Bluetooth Low Energy Application I have a task at hand on designing security on Bluetooth Low Energy application layer. The system is created so that only smartphones with symmetric key (long term) could communicate and control my BLE device. The symmetric key will be stored securely on cloud server and programmed on BLE device with JTAG read protection. The mechanism to distribute this symmetric key to intended smartphone is outside the scope of this thread.

I use AES-GCM on my embedded processor and phone app. It can be summarized like this:

Smartphone request connection to BLE device
Smartphone read a characteristic which will respond with a challenge $C$:
$C = \operatorname{AES}(K, S, N)$
$K$ is the symmetric long term key
$S$ is 1-byte of secret generated randomly by BLE device
$N$ is nonce/IV controlled by BLE device and starts from $0$
Smartphone prepares the legitimate command $I$ by encrypt and authenticate with incrementing the nonce received by $1$:
$I = \operatorname{AES}(K, D_{0} \mathbin\Vert S, N+1)$
$D_{0}$ is the opcode for specific operation for BLE device
BLE device then increments its nonce to $N+2$ for future smartphone connect and read the challenge, and so on...

At first I though it would be secure but later I found that it might break if someone impersonate BLE device (MAC address clone) and replay the previous legitimate response such as:

Smartphone request connection to impersonate device
Smartphone read a characteristic and impersonate device replies previous challenge:
$C = \operatorname{AES}(K, S, N)$
Smartphone does not know about previous challenge and proceed with:
$I = \operatorname{AES}(K, D_{0} \mathbin\Vert S, N+1)$
I think this would not be a problem if the data is the same $D_{0}$. However if the data is different, lets say the phone would send $D_{1}$ then:
$I = \operatorname{AES}(K, D_{1} \mathbin\Vert S, N+1)$

It leads into condition where different data is encrypted and authenticated with same nonce. I am worry that adversaries could recover the long term key.

My problem seems similar with these:

Establish a secure connection between a Bluetooth Low Energy device and an Android App using ECDH
Encrypting small packets with low data rate

But it uses ECDH while my system does not use public key cryptography

My questions are about:

If I use a mechanism to produce symmetric session key before proceeding with above flow. Is it one of solution to mitigate the above problem?
What is the good mechanism to securely generate session key when both parties have that same long term symmetric key?

I have a true random number generator on my BLE hardware and for apps I can use secure random number generator library but my knowledge is limited on key exchange technique.

Using GCM with a long term fixed key is dangerous; if you repeat the nonce, you can leak the authentication piece.

Instead, what I would suggest is that you use AES-SIV instead.  It doesn't have the problems with repeating a nonce.  It is more complex, and slower, however it is far better suited if you have to use a long term key.


Calculating $s$ in ECDSA over $GF(2^m)$ I am implementing ECDSA over $GF(2^n)$. I am following RFC 6979 and compare my results with the example in Appendix A (which uses curve SECT163K1).
My calculation of $r$ is correct, but I am struggling with $s$.
A few parameters determine $s$ and I am not sure which one I got right and which wrong.

$s=k^{-1} * (m + r * d_A) \mod q$

$q$ is the order of the curve's generator (in other sources refered to as $n$). $r$ is correct/was given and $d_A$ was given, which leaves $k^{-1}$ and $m$.

m

The hash of the message is h1 = AF2B DBE1 AA9B 6EC1 E2AD E1D6 94F4 1FC7 1A83 1D02 68E9 8915 6211 3D8A 62AD D1BF, which is shortened with bits2int(h1, 163). I presume it to be correct.
m = 5795 edf0 d54d b760f 156f 0eb4 a7a0 fe38 d418 e813

$k^{-1}$

The value of $k$ was given in the example with 2 3AF4 074C 90A0 2B3F E61D 286D 5C87 F425 E6BD D81B. I calculated $k^{2^{162}-2} \mod q$  to get. I checked it with $k^{-1}*k = 1$. The algorithm also works with other curves and $k$'s. I also checked the results against the Python package BitVector, which also implements a modular inversion in $GF(2^n)$.
k^-1 = 3 759d 2532 cdd0 d539 5f03 eaed b650 3045 d218 9bad

I implemented all operations in "binary" (i.e. addition as xor, mod as polynomial division, ...).
Other intermediate results:
$r * d_A$: 14d1 14fe1 04b4 a34f 3bf6 fd30 02aa f767 3ed8 c786
$m + r * d_A$: 4 344f 90ec 506f d540 2e99 f384 a50a 095f eac0 2f95
$s$: b957 16f7 2680 def2 d19f d596 6a2e 93fe 8c0c fea9

Question

What goes wrong, where is the error?

I can also post my (Python) code, but I would have to clean it up first.

Since you're calculating a scalar multiplication value, and the base point has order $q$, you should calculate $s$ in the field $\mathbb{Z}/q\mathbb{Z}$, not in $GF(2^m)$. In particular, this means that you can't use xor or polynomial division to implement addition and modular reduction, but should use regular addition and division instead.

For example, this should give you the value for $k^{-1}$ as:

$$k^{-1} \equiv 2315871241563531210130617073628712209517930583176 \pmod q$$

which is 1 95A7 4210 396D 0D19 E522 8C83 6815 E728 EFD7 9488 in hexadecimal notation.

Since $q$ is prime, the order of $\mathbb{Z}/q\mathbb{Z}$ is $q-1$, so you can easily calculate the inverse of $k$, and then calculate $s$. This gives the correct output:

>>> q = int('4000000000000000000020108A2E0CC0D99F8A5EF', 16)
>>> x = int('09A4D6792295A7F730FC3F2B49CBC0F62E862272F', 16)
>>> k = int('23AF4074C90A02B3FE61D286D5C87F425E6BDD81B', 16)
>>> m = int('5795edf0d54db760f156f0eb4a7a0fe38d418e813', 16)
>>> r = int('113A63990598A3828C407C0F4D2438D990DF99A7F', 16)
>>> k_inverse = pow(k, q-2, q)
>>> s = (k_inverse * (m + r * x)) % q
>>> '%X' % s
'1313A2E03F5412DDB296A22E2C455335545672D9F'


It's safe to store a known value (for checking) next to the actually encrypted values The high level details of the encryption I'm using is:

AndroidKeyStore create/store RSA key
AES key is created and wrapped with RSA/ECB/PKCS1Padding
Encrypted AES is saved to disk.
Data is encrypted with AES/GCM/NoPadding and saved to disk.
Every encryption operation generates a new initialization vector from the platform secure random. Those are also saved to disk with their data.

The algorithm/transformation used are limited by the platform.

There are known issues on the AndroidKeyStore forgetting keys and I would like to save a known "lorem ipsum" data encrypted on first run. This known data would later be used during initialization to check the consistency of the keys and provide proper status for the system.

So my question: is it safe to store this known hard-coded value next to the real values, or with that I'm leaking everything and making it easy for someone to decrypt the real values?

Yes, it is secure to do this. Any cipher should be secure against known plaintext attacks after all.

However, if you're using RSA then the RSA decryption routine will already throw an exception during the PKCS#1 v1.5 unpadding, so storing the 'lorem ipsum" data is not necessary: the padding already acts as the "lorem ipsum" data.

If you still somehow require "lorem ipsum" for the symmetric encryption (in case Android loses track of the AES key as well) then you might as well use the "lorem ipsum" as Additional Data for the GCM algorithm. This data is included in the authentication tag but not in the ciphertext. If it is constant then you do not have to include it at all.

Note that you may want to use RSA-OAEP or RSA-KEM rather than PKCS#1 to avoid padding related attacks (RSA-OAEP should be directly available in Java / Android and is therefore recommended, but please do check with the KeyStore implementation and the targetted runtimes to be sure).


Generate random numbers whose sum is equal to a constant value modulo n I want to generate $n$ random numbers $u_i \in [ 0, 2^{\kappa + 1})$ such that $\sum u_i = c$ $mod$ $2^{\kappa + 1} $, where c is a constant.
Also, taking $n - 1$ random numbers and subtracting their sum from $b \cdotp 2^{\kappa + 1} + c$, where $b \cdotp 2^{\kappa + 1}$ is the closest multiple of $\;2^{\kappa + 1}$ that is greater than sum of the $n - 1$ random numbers, to get the $n^{th}$ random number a good solution?

P.S. I want to know if there's a solution to this problem that'll ensure good statistical properties.

For $i=1, \dots, n-1$, generate $n-1$ random numbers $u_i \in [0,2^{κ+1})$ and define $u_n = \left(c - \sum_{i=1}^{n-1} u_i\right) \bmod 2^{κ+1}$.


Why is it that most messages seem to be expanded? Whenever I have seen a more secure version of a message, the message seems to be expanded by some factor. One example is RSA encryption, but whenever a message does not appear to be expanded it is very easy to crack. Such as the Caesar Shift Cipher, or a Substitution Cipher, or even the Vingere Cipher. Is there a reason that expanded messages are much more difficult to crack?

Is there a reason that expanded messages are much more difficult to crack?

When looking purely at encryption, message expansion does not really tell you anything about the difficulty to crack it.

Message expansion is often a feature of asymmetric cryptosystems. Those are not inherently more difficult to crack than symmetric systems. Block ciphers also expand the length slightly in some modes, but other equally secure modes do not expand the message length.

Weak classical ciphers often act on single symbols, so they will not expand the message, but e.g. stream ciphers can likewise act on single symbols and remain secure.

However, there are a couple of caveats:

Semantically secure encryption requires some kind of an IV if you reuse the key for multiple messages. This can expand the message if it is added as part of the ciphertext, but it does not need to be - many protocols handle the IV implicitly.
Authenticated encryption must expand the ciphertext at least somewhat. And authentication is usually necessary to prevent attacks that would be possible even with otherwise secure encryption. So in that sense message expansion is often necessary.


Are hash trees an alternative, quantum-resistant signature scheme which can replace RSA? Can hash trees provide quantum resistant signatures to replace RSA for signing securely? What is the key size and how many times can we use same key?

Hash trees alone wont do that. But hash trees in combination with one time signatures (this is called the Merkle signature scheme).

If you use hash based one time signatures such as Lamport-Diffie, then yes.

Basically, the hash tree is used to "aggregate" $k$ public keys by representing the hash values of the public keys as leaves of the hash tree and recursively computing the hash values of inner nodes of the tree as hash of the concatenation of its children till you obtain the "root public key hash". Then every leave public key can be used for a single time with a one time signature scheme and allows you to produce $k$ signatures in total.

Therefore, you compute a signature with public key $i$ and you have to add the "root public key hash" and the authentication path of public key $i$, i.e. the hash values of all siblings of public key $i$ on the unique path to the root of the tree (this is required to check if public key $i$ is "contained" in the tree by recomputing the root). Latter contains $\log n$ hash values for a tree of height $n$.

The key and signature sizes depend on the used one time signature scheme and in turn on the hash function.


Should Bob trust a certificate issued by delegated party? Consider this scenario:

Alice sends a message signed under her public key to Bob.
Bob has never exchanged a keys with Alice.
Alice's key is signed by a certain X.
X's key is signed by Y, an entity that Bob trusts.

Is Alice's key valid or not for Bob?

This very much depends on what you mean by

  Bob trusts Y.

If Y is a root CA and Bob "trusts" them to do their job properly, then yes he would trust Alice's key. This is because the job of a root CA is exactly discerning whether a subordinate CA (in this case X) should be trusted to in turn do their job: I.e., check people's identity and sign their public keys if and only if they can be certain beyond reasonable doubt that the person presenting the public key is in possession of the corresponding secret key and that they are the entity they claim to be.

If on the other hand Y is just some random friend ob Bob, whom he trusts in the sense that they are sure that the key they is theirs and they probably genuinely believe whatever it is they signed with that key, then no, this is no basis to trust Alice's key. In fact in general Bob has no way of telling in what context and why Y ever signed X's key.

Which means that we lack the necessary information to answer the question, because the statement "Bob trusts Y." is underspecified.


Is hybrid encryption required to use Attribute based Encryption to encrypt messages? Does the mechanism behind Attribute Based Encryption require us to first encrypt the message by using a symmetric cipher, e.g. AES, and then encrypt the AES key by using Attribute Based Encryption?

Or if I encrypt the message directly using Attribute Based Encryption, would the message still be considered encrypted and the plaintext hidden?

No, this is not required by Attribute Based Encryption (ABE) itself.

However it is a common practice to use so-called "hybrid encryption" when you want to encrypt data using public-key encryption, for multiple reasons:

it sometimes avoids the need for padding of the message: if your ABE scheme works on messages that are of size 256 bits, for instance, then using a AES key of 256 bits fits naturally in that message space. (Although in practice you often have some rejection sampling to do because the whole 256-bit space is not necessarily the universe of the messages.)
it allows to ignore the limits of the public-key encryption scheme you are using, that is the converse of the previous point: if you can only work with 256 bits messages but want to encrypt more than 256 bits, then you have a problem, whereas AES (with a good mode of operation) (or the underlying stream cipher of your choice) is not limited in the size of the data you can encrypt.
probably one of the most important reasons: the performance! ABE (and more generally public-key cryptography) schemes are super slow in practice, while AES is super fast, so in order to have decent performance it makes sense to use as little public-key cryptography as possible.

So in the end, most practical instantiations of ABE (not that I'm aware of any) would be probably better off using ABE as a way to broadcast keys to access symmetrically encrypted data, à la Attribute Based Broadcast, rather than encrypted messages directly, excepted if the messages are really short!

As it wouldn't better to use hybrid encryption on message of the same size as the keys of the underlying symmetric cipher.

But to sum it up, in the end, there is nothing that restricts you and says you have to use hybrid encryption when using ABE.
As long as the ABE scheme you are using is okay encrypting messages of the size you need to encrypt, then you could use ABE directly on the messages and it would not reduce the security of the ABE scheme when compared to a construct where you'd use hybrid encryption to first encrypt the message with a symmetric cipher with a randomly generated key, say AES, and then use your ABE scheme to encrypt the random symmetric key for the set of attributes that are allowed to access that message.

And yet you should use it in practice!

Hybrid encryption schemes are actually a good thing in practice, because they have many nice features.
Firstly, notice that when doing hybrid encryption, we have two main components:

a Key Encapsulation Mechanism to protect the key, in this case the ABE scheme
a Data Encapsulation Mechanism to protect the data, in this case AES

And the encryption works by generating at random a key $\mathcal{K}$ that is used to encrypt the data $M$ using the DEM algorithm $DEM_\mathcal{K}(M)$, and then that key $\mathcal{K}$  is encrypted using the KEM algorithm for the public key $P_k$ of your choice  $KEM_{P_k}(\mathcal{K})$, and the resulting ciphertext is the tuple $\left(KEM_{P_k}\left(\mathcal{K}\right), DEM_\mathcal{K}\left(M\right)\right)$.

A really nice property of the KEM-DEM construct is that if the DEM and the KEM are both "CCA2-secure" (secure against adaptative chosen ciphertext attacks), then the resulting hybrid encryption scheme is also CCA2-secure.

Whereas, for instance, if you were to encrypt a longer message than what your public-key algorithm allows, and decided to do so by "chunking" the message into "blocks" of the right size, and then encrypt using ABE each block of your message and send all the blocks together as you ciphertext, your scheme would trivially not pass the "CCA game" as we commonly use it, whereas if you were to use a CCA2 ABE scheme as a KEM and AES-GCM (or any other IND-CCA2 stream cipher) as a DEM, then you would still pass it.

For more details, including a proof of the former, I refer you to this paper by Cramer & Shoup, section 7.3.

It is also interesting to see what are the necessary conditions on the security of your DEM and KEM in order to have secure scheme. This online paper by Herranz et al. (or the published one) has a good coverage of the question.

The other good thing with a KEM-DEM scheme is the fact that such schemes are significantly more efficient than pure public-key schemes, as soon as the message would require more than one public key operation invocation.


What does well-typed mean? I am currently studying Cryptography and I don't really understand what does 'well-typed' mean when talking about secure cryptographic protocols. I can't find any reasonable explanation on the internet either.

It would be great if someone could give definition and maybe example.

For example quote from “prosecco.gforge.inria.fr”:

  The basic soundness theorem for the type system states that well-typed process do not reveal their secrets." So what is 'well-typed'?

“Well-typed” relates to a type system. This is a general concept in computer science, the usage here is an example of the general concept and is not specific to cryptography. “Well-typed” does not refer to a cryptographic protocol, but to a theory (model) in which a protocol is described.

A type system is a way to assign properties (called types) to components of programs. For example, a type system might make stipulations like the following:

The program fragment int x; declares a variable called x whose type is “integer”.
Integer literals such as 3 and 42 are expressions of the type “integer”.
String literals such as "hello" and "42" are expressions of the type “string”.
If x is a variable with the type “integer”, then x is an expression of the type “integer”.
If E_1 and E_2 are expressions of the type “integer”, then E_1 + E_2 is an expression of the type “integer”.
If x is a variable which has the type “integer” and E is an expression of the type “integer”, then x := E is a valid (well-typed) program. If E does not have the type “integer”, then x := E is an invalid (ill-typed) program.

The ultimate goal of most type systems is to declare that certain programs are well-typed, i.e. that they're correct (with respect to this type system). They achieve this by assigning types to program fragments, to variables, to functions, etc. and detecting conflicts (e.g. trying to assign a string value to an integer variable, trying to apply a function to an argument which is not of a type that it can handle). Most programming languages have a type system, such that ill-typed programs are rejected, either at run time (dynamic typing) or at compile time (static typing).

Type systems can encompass a wide variety of properties. The most common class of property has to do with the structure of data, such as:

“this is an integer“
“this is an integer modulo $2^{32}$ using the smallest nonnegative representative”
“this is a list of integers”
“this is a function that takes an integer as argument and returns an integer”

But type systems can describe arbitrarily complex properties. That makes it harder to decide whether a program has a correct type, but makes the type system provide more useful information. Here are some example properties that a sufficiently sophisticated type system might model:

“this is a prime integer”
“this is a list of integers whose length is the value of the expression x + y”
“this is a terminating function that takes an integer as argument and returns an integer”
“this function $f$ takes two arguments $(p,s)$ and returns two values $(p',s')$, such that the value of $p'$ depends only on $p$ and not on $s$”

In that last example, you can see a security property emerging: if we think of $p$ and $p'$ as public values and $s$ and $s'$ as secret values, the property states that public values do not depend on secret values. In other words, the function $f$ preserves the confidentiality of secret values.

Soundness relates a type system with execution rules (an execution semantics) for the programming language. It is a formal property that states that if a program is well-typed, then all runtime states of the program (as modeled in the semantics) are also well-typed. Most type systems are designed to be sound for the usual semantics of the language. This way, information given by the type system about the program translates into information about the program's execution.

The paper that you're reading defines a type system for processes (describing communication protocols) that classifies messages according to which principals know their content. The execution rules describe the propagation of messages. The soundness of the type system means that the initial classification of who knows what is preserved during the execution of the protocol. This holds for well-typed processes, i.e. processes for which the classification (typing) rules give a result. Thus processes that are classified as valid by the type system will not reveal secret data during their execution.


Generating ElGamal parameters in a mix net I am reading this paper regarding re-encryption mix nets. I want to implement my own for educational purposes and I am stuck at the initial steps of how I should generate the keys and distribute them. The paper for this step says that

"Key generation: all decryption servers jointly generate
the parameters (q, g, x, y) of an ElGamal cryptosystem
in a group G of order q generated by g, using for
example the threshold key generation protocol of Pedersen
"

This whole step though seems to be more complex than I initially thought and I have failed to find any other implementations out there to study from. Can someone explain in simple steps the process of how the mix servers jointly generate the public and private parameters of an ElGamal cryptosystem?

The generation is actually quite straightforward.

I'm just paraphrasing the beginning of section 3.1 of A Threshold Cryptosystem without a Trusted Party by Pedersen.

Every participant $P_i$ (for $i=0\ldots n$) picks a secret key $sk_i$ and computes the public key part $pk_i = g^{sk_i}$. $P_i$ then publishes a commitment to $pk_i$.
When all commitments have been broadcast all the $pk_i$ are revealed and the commitments checked.
The global public key is $pk = \prod_{i=1}^n pk_i$


Diffe-Helman Exchange result is always 1 I watched a video on Khan Academy explaining the Diffe-Hellman exchange. When I try to do an example problem, I get 1 all the time. Does the generator and prime modulus (or base on Wikipedia) have to somehow be related for the key exchange to work?

Here is my example:

Generator: 47
Prime modulus: 23
Alice's private number: 6
Bob's private number: 19

Alice's public number: 47^6 mod23 = 1
Bob's public number: 47^19 mod23 = 1

Shared number: 1^6 mod23 = 1
Shared number: 1^19 mod23 = 1

For a given prime $p$, there are many choices for the generator $g$, but $g$ cannot be completely arbitrary. As the name hints, $g$ is supposed to be a generator of the multiplicative group $(\mathbb{Z}/p\mathbb{Z})^*$ (or at least a large subgroup, more on this later), that is, it must have the property that the set of its powers modulo $p$ $\{g^1 \bmod p, g^2 \bmod p, g^3 \bmod p, \ldots, g^{p-1} \bmod p\}$ is equal to the set of elements $\{1,2,\ldots,p-1\}$.

You happened to pick $g = 47 = 2 \times 23 + 1$, thus $g \equiv 1 \pmod{p}$. The set of powers of $1$ is just $\{1\}$, so it's about as far from a generator as it gets (the only way this could be “worse” would be a number like $46 \equiv 0 \pmod{p}$ which is not in the multiplicative group at all).

With large prime numbers, there's no efficient way to find a primitive root directly, but it's easy to test whether a candidate $g$ is a generator if the factorization of $p-1$ is known. This is because if $g$ is not a generator, its order (the smallest number $k \ge 1$ such that $g^k=1$) will be a multiple of one of the prime factors of $p-1$. The Wikipedia article on primitive roots modulo (“primitive root modulo $n$” is another way to say “generator of $(\mathbb{Z}/p\mathbb{Z})^*$”) and some results on the proportion of candidates that are generators.

In fact, the $g$ parameter in Diffie-Hellman does not have to be a generator of the whole group in order for the protocol to work, in the sense that Alice and Bob end up with the same shared key. In fact, even in your example with $g=1$, the protocol “works”, but it has no security. For security, what matters is that $g$ generates a “large” enough subgroup of $(\mathbb{Z}/p\mathbb{Z})^*$, where “large” means that the order of $g$ (i.e. the smallest $k \ge 1$ such that $g^k \equiv 1 \pmod{p}$) is a multiple of a large prime.

There are several techniques for generating Diffie-Hellman parameters. Typically $p$ is chosen in such a way that a good generator can be chosen easily. A small generator is prefered for a minor performance improvement. There are bad values of $g$ that can lead to practical attacks but it is easy to avoid them. An additional subtlety is that if the order of $g$ has a small prime factor (which is the case if $g$ generates the whole of $(\mathbb{Z}/p\mathbb{Z})^*$, since its order $p-1$ is then a multiple of $2$), there is a practical attack to find one bit of the shared secret, so choosing $g$ such that its order is a large prime is recommended.

Usually, $p$ and $g$ are chosen long in advance; many protocols or applications use built-in constants for $p$ and $g$, or have just a few of them to span different key sizes. There's no need to vary $p$ or $g$ for security, they can be reused.


Wrong Proof of Secure PRF Disclaimer, this is not homework; I found the question statement here: Security of this PRF

To restate the question:

  Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as
  $F'(k,x\mathbin\|x') = F(k, 0\mathbin\|x)\oplus F(k, 1\mathbin\|x')$
  with $x$ and $x'$ of $\lambda-1$ bits.
  Is $F'$ a secure PRF?

The given answer is no and it's clear that the PRF $F'$ is not secure. But I tried to provide a false proof that $F'$ is secure (but it's not) and cannot see what step the proof goes wrong.

First, to restate the counterexample:

  More specifically, for sake of simplicity let $F'_k$ be a keyed PRF
  $F'$ with key $k$ from the family of unkeyed PRFs $\{F' : \{0,
 1\}^{2(\lambda - 1)} \times \{0, 1\}^{2(\lambda - 1)} \to \{0,
 1\}^{\lambda - 1} \} $ and consider the following  $\mathsf{PPT}$
  adversary $\mathcal{A}$. $\mathcal{A}$ asks for the evaluation of the
  oracle $\mathcal{O}$ on $x_0 \mathbin\| x_1$, $x_0 \mathbin\| x_2$, $x_1 \mathbin\| x_2$, and
  $x_1 \mathbin\| x_1$. Then $\mathcal{A}$ computes the XOR of the first three
  oracle outputs and checks if the XOR is equal to the fourth oracle
  output. Observe that if $\mathcal{A}$ is given oracle access to
  $F'_k$, then $\mathcal{A}$ receives \begin{align*} F'_k (x_0 \mathbin\| x_1)
 &= F_k (0 \mathbin\| x_0) \oplus F_k (1 \mathbin\| x_1)\\ F'_k (x_0 \mathbin\| x_2) &= F_k (0
 \mathbin\| x_0) \oplus F_k (1 \mathbin\| x_2)\\ F'_k (x_1 \mathbin\| x_2) &= F_k (0 \mathbin\| x_1)
 \oplus F_k (1 \mathbin\| x_2)\\ F'_k (x_1 \mathbin\| x_1) &= F_k (0 \mathbin\| x_1) \oplus F_k
 (1 \mathbin\| x_1) \end{align*}
  and the XOR of the first three is exactly
  equal to the fourth and $\mathcal{A}$ guesses correctly with
  probability 1 given this case of the oracle. In the random case,
  $\mathcal{O}$ is equal to some truly random function $U$ and receives
  $U(x_0 \mathbin\| x_1) \oplus U (x_0 \mathbin\| x_2) \oplus U (x_1 \mathbin\| x_2)$ is
  unlikely to be equal to $U (x_1 \mathbin\| x_1)$, namely the probability is
  negligible. Hence $\mathcal{A}$ is a distinguisher.

Here is my "false proof" in an attempt at proving the statement "$F'$ is a secure PRF" and I'd really appreciate clarification on what step is incorrect.

Suppose $F_k'$ is not a PRF. Then there exists a $\mathsf{PPT}$ distinguisher $\mathcal{A}'$ and a constant $c$ and natural number $n \in \mathbb{N}$ such that $\mathcal{A}'$ distinguishes $F_k'$ from a truly random function with distinguishing advantage $\geq \frac{1}{n^c}$.
We now construct a distinguisher $\mathcal{A}$ (an oracle machine with access to $\mathcal{O}$ which is either from PRF family $\{F\}$ or truly random function $\{U\}$) for $F$ as follows.
$\mathcal{A}$ runs $\mathcal{A}'$. $\mathcal{A}'$ asks for queries of the form $x_0 \mathbin\| x_1$ as described above and $\mathcal{A}$ then queries the oracle $\mathcal{O}$ with $0 \mathbin\| x_0$ and $1 \mathbin\| x_1$, computes the XOR $\mathcal{O}(0 \mathbin\| x_0) \oplus \mathcal{O}(1 \mathbin\| x_1)$, and sends that to $\mathcal{A}'$.
$\mathcal{A}'$ will query polynomially many times in $\mathcal{A}'$'s input length so $\mathcal{A}$ will have to make twice as many, namely $O((2(\lambda-1))^l)$ queries for some constant $l$, which is still polynomial in $\lambda$.
Finally, $\mathcal{A}$ will output whatever $\mathcal{A}'$ outputs.
Note then $\Pr[\mathcal{A}^{\{F\}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}'^{\{F'\}}(1^{2(\lambda -1)}) = 1]$ by construction since $\mathcal{A}$ effectively simulates oracle access to $\{F'\}$ when $\mathcal{O} = F_k$ for some $k$.
If $\mathcal{O} = \{U\}$ for truly random functions $U$, then $\Pr[\mathcal{A}^{\{U\}}(1^{\lambda}) = 1] = \Pr[\mathcal{A}'^{\{U\}}(1^{2(\lambda -1)}) = 1]$ because $U(0 \mathbin\| x_0) \oplus U(1 \mathbin\| x_1)$ is still truly random.
Then the distinguishing advantage of the new adversary $\mathcal{A}$ is also non-negligible and hence $F$ is not a secure PRF.

Again, where did I go wrong in this "false proof"?

The problem is in the last equation:
$$
Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]
$$

It does not hold because $\mathcal{A}^{\{U\}}$ is the result of $\mathcal{A}'$ using $U$ instead of $F_k$. This is actually equivalent to $F'$ and will be distinguished by $\mathcal{A}'$, so we get
$$
Pr[\mathcal{A}^{\{U\}}(1^{\lambda})=1]=Pr[\mathcal{A'}^{\{F'(U)\}}(1^{\lambda})=1]\neq Pr[\mathcal{A'}^{\{U\}}(1^{\lambda})=1]
$$


Is there any non-interactive zero knowledge proof for Diffie-Hellman tuples I'm aware that Zero-Knowledge for Diffie-Hellman Tuples requires 4 rounds. I wondered if there is any non-interactive version of it.

Usually, non-interactive ZK proofs are achieved by using a technique to transform an interactive proof into a non-interactive. For example you can use a common reference string or the Fiat-Shamir heuristic. If you assume pairings, then you can also use the techniques used in Groth-Sahai proofs, but I guess that doesn't apply to Diffie-Hellman tuples.


Stream Ciphers -- Need clarification on their benefits in practice Compared to a block cipher which encrypts 16 bytes at a time, stream ciphers can encrypt a byte at a time. I am curious about which applications would immensely benefit from the ability to encrypt a byte at a time.

Realtime applications such as chatting or voip always have several bytes at a time to send -- which means only a little bit of padding would be needed every now and then if a block cipher is used. Leaves me curious where the ability to encrypt a byte at a time comes off as a big PLUS for stream ciphers.

Stream ciphers not necessarily encrypt one byte at a time; they encrypt/decrypt by generating keystream and xorring it with plaintext/ciphertext. Old stream ciphers like RC4 generate keystream byte by byte, modern stream ciphers like Salsa20 generate keystream by blocks (Salsa20 by 64-byte blocks). Block ciphers can be converted into stream ciphers using CTR mode of operation, and then they generate keystream by blocks too.

The ability to generate keystream one byte at a time is sure useful for some applications, but generally one need to implement it yourself. Modern ciphers (at least most of them) do not provide it "out of the box".


Generating Diffie-Hellman parameters I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a generator g?

Restricted by the multiprecision library that I have to use, only a few basic operations (+, *, -, /, pow, modExp, modMult, mod, gcd, isProbablyPrime, genRandomBits, and a few more) are available.

I read that in a cyclic finite group $Z_q$ where $q$ is a safe prime, every element is a generator of that group. So I assume I should start by generating a safe prime $q$ first:

Pseudocode:

 // find a safe prime q
 WHILE NOT isProbablyPrime(q)
     WHILE NOT isProbablyPrime(p)
        p = genRandomBits(1024)
     q = 2*p+1

But how do I now find a generator for $Z_q$?

Just stick to the standard algorithm, also remember that you are working in $\mathbb{Z}_p^*$.

Select $q$ with at least $2k$ bits, that means you are targeting $k$ bits security. In the RFC at least 160 bits is recommended for $q$. In addition select a prime $p$ with at least 1024-bit.

Regarding the generator, we know that every generator will generate the subgroup of order $2q$ or $q$. The reason that $g=2$ is chosen is that is desirable for faster computations of modular exponentiation.

You will find all the information regarded to Diffie-Hellman implementation in RFC. Also there's a method for generating $p$,$q$ and alternatively $g$, if desired.


Optimal way to bind two hashes Currently I have:

H1 = SHA256

H2 = SHA1

Both H1 and H2 have fixed length. What's the most efficient way to bind H1 and H2 together into H3? The goal is to maximize protection in case when one of them leaks.

For example:

H3 = H1+H2
H3 = SHA512(H1+H2)
H3 = ???

Length preserving is not needed. This should be calculated instantly so no KDF.

Thanks for your help.

EDIT: I plan to use it as password creation scheme. H1 and H2 should not be changed.

If H1 becomes known then the first part of H3 becomes known if you just concatenate, so that's not a good option.

A simple XOR could work as long as H2 remains secret to an attacker. However, if info about H3 can be retrieved by an attacker and H1 can be changed then the attacker can force H3 to a certain value. But XOR doesn't expand the hash value as you seem to require.

If H1 and H2 are hashed together, e.g. with a larger output hash then all the attacker can do is to try and change H1 until some kind of structure appears in H3. This is the best thing to do if you just rely on hash functions.

You state that you don't require a KDF because you're not dealing with passwords. This is however not a good argument; there are also KBKDF's that derive output key material from input key material (and do not deal with passwords).

HKDF is a KDF that does this: it takes input key material, extracts the entropy from H1 and H2 into a certain intermediate key material, and finally expands the key material to the requested size. So the most fireproof way of creating H3 is: H3 = HKDF(enc(H1, H2), "H3", outsize). Optionally you can also supply a salt or change the label ("H3") to create different output values. enc is an encoding of the values H1 and H2, it can be just concatenation if the size of H1 and H2 can never change.

HKDF just relies on HMAC, and HMAC just relies on a secure hash function. So it can generally be implemented even if it is not directly available.

But just SHA-512 will also work.


Is there a number of tries after which Hashcash is guaranted to be solved? Hashcash is a proof-of-work system in which the Sender needs to find $Y$ such as the first (let's say 20) bits of $H(X+Y)$ are zeros where $H$ is a one-way hash function, $X$ is a fixed value and $+$ means concatenation.

The Sender starts with an initial random number $Y$. It then computes the hash of $X+Y$. If the first 20 bits of the hash are zeros, then $Y$ is an acceptable number. If not, then the sender increments the random number and tries again. Since about $1$ in $2^{20}$ headers will have $20$ zeros as the beginning of the hash, the sender will on average have to try $2^{20}$ random numbers to find a valid number.

My question is: The average number of tries is $2^{20}$ but is there a number of tries after which Hashcash is guaranted to be solved?

The probability of finding an acceptable number is
$$Pr(\mbox{accept})=2^{-20}.$$
Thus the probability not to find an acceptable number is
$$Pr(\mbox{reject})=1-Pr(\mbox{accept})=1-2^{-20}.$$
Assuming independent events, the probability not to find an acceptable number in $k$ attempts is given by
$$Pr(\mbox{$k$ rejects})=(1-2^{-20})^k.$$
Thus, the probability to find at least one acceptable number in $k$ attempts is given by
$$Pr(\mbox{not $k$ rejects})=1-Pr(\mbox{$k$ rejects})=1-(1-2^{-20})^k.$$

This means that if you want to find an acceptable number with a probability $P$, you chose $k$ such that
$$1-(1-2^{-20})^k>P$$

$$\Leftrightarrow k>\frac{\log (1-P)}{\log(1-2^{-20})}.$$

Example

To find an acceptable number with a probability of P=99%, you have to make
$$k>\frac{\log (1-P)}{\log(1-2^{-20})}=\frac{\log (0.01)}{\log(0.9999990463256836)}\approx 4828869$$
attempts.


How long must be the key of a stream cipher? I am watching Lecture 3 (Stream cipher, random numbers and one time pad) by Christof Paar and perhaps its something that will be explained in another lecture but:
When he explains how XOR works, in the example he gives, plaintext X3.X2.X1 is encrypted with key S3.S2.S1 and becomes ciphertext Y3.Y2.Y1.
So if the plaintext is N-bits long...the key has to also be N-bits long?
If the answer is no and it can be an arbitrary number...wouldn't that be a block cipher?
If the answer is yes, does the sending and receiver end have to agree on the quantity of bits to be transmitted beforehand?
If this is random (ie. unknown beforehand), how can they know what key to use to encrypt and unencrypt if it has to be as long as the plaintext?

So if the plaintext is N-bits long...the key has to also be N-bits long?

Let's explain this point-by-point:

The key stream has to be N-bits long for a stream cipher;
For an OTP the key is basically the key stream;
For a stream cipher or block cipher (in stream mode such as counter mode) the key is generally between 128 and 256 bits to be considered secure;
For these ciphers the key is used to generate the key stream.

I've skipped "plaintext aware" stream ciphers as they don't use XOR (directly) to calculate the ciphertext from the key and plaintext.

If the answer is no and it can be an arbitrary number...wouldn't that be a block cipher?

A block cipher is a cipher that permutes one  block of plaintext to a block of ciphertext (and vice versa) - using the key to select the permutation. You can have block ciphers and stream ciphers with about any size of key. The key size doesn't define if something is a stream cipher or block cipher.

If the answer is yes, does the sending and receiver end have to agree on the quantity of bits to be transmitted beforehand?

The answer is no, so that makes this question invalid. Nevertheless: for an OTP you'd have to make sure that you know the location within the key stream and of course that you have shared enough key bits. For a stream or block cipher you don't need to know the quantity of bits to be transmitted beforehand. However, you should be using a unique IV or nonce for each message.

If this is random (ie. unknown beforehand), how can they know what key to use to encrypt and unencrypt if it has to be as long as the plaintext?

They use a complex technique called "keeping count" :) And yes, it is a problem if the index gets out of sync, e.g. because of lost messages.


Is it possible to perform a meet-in-the-middle within a block cipher? Standard meet-in-the-middle explanations show that you can perform a meet-in-the-middle attack on a repeated block cipher such as double-DES (performing DES twice in a row).

However, block ciphers themselves commonly consist of a number of rounds internally. Would it be possible to use a meet-in-the-middle attack on a single block encrypt?

In other words, will encryption / decryption meet a common middle state that allows us to see $\newcommand{\E}{\text{E}} \newcommand{\D}{\text{D}}$ $C = \E_k(M) = \E_{k''}(\E_{k'}(M))$ and $M = \D_k(C) = \D'_{k'}(\D''_{k''}(C))$ so that $S = \E'_{k'}(M) = \D''_{k''}(C)$ where $S$ is a middle state?

Related question: Understanding Meet-in-the-Middle attack on block ciphers.
Related Wikipedia page: Meet-in-the-middle attack with additional references to Multi-Dimensional Meet-in-the-Middle attacks on e.g. GOST.

Meet-in-the-middle attacks can indeed be used for block cipher (but also hash function) cryptanalysis. As mentioned in the question, this goes back to Diffie and Hellman's analysis of DES. However, when applied to primitives, one typically uses more sophisticated techniques. Since the literature around this topic is very extensive, I won't go into the details of all techniques but I'll instead try to provide the main references.

The first four sections of this answer discuss variants of the classical MITM attack. These attacks are the most similar to the attack on 2DES that you refer to.
Probably the most interesting aspect of classical MITM attacks is their low data complexity, which makes them attractive from a practical point of view. There are some exceptions to this, though (bicliques being the most notable).

The last section, however, argues that the general MITM idea is even more widespread in cryptanalysis. That is, many statistical attacks are supplemented with a phase that can reasonably be called a MITM step. A good example of this is the Demirici-Selçuk attack.
Here, the data requirements are usually larger.

Basic MITM attack

The classical MITM attack is easy: one splits the cipher in two parts with independent keys, say $K_1$ and $K_2$. For each guess of $K_1$, compute the intermediate state by evaluating in the forward direction. Similarly, the intermediate states are computed for each guess of $K_2$ by evaluating in the backward direction. The candidate keys are those for which the intermediate states match.

The main issue with this simple approach is that, after a few rounds, it is likely that too many key bits must be guessed in order to obtain the intermediate state. (Leading to a blow up of time and memory requirements.) Of course, the key schedule plays an important role here. For example, MITM is typically useful in block ciphers with a small block size but a larger key size.

The basic MITM attack has been applied to DES itself (so not just 2DES), and several improvements have been introduced since. For example, you can take a look at Improved Meet-in-the-Middle Attacks on Reduced-Round DES by Dunkelman, Sekar and Preneel (INDOCRYPT 2007). Some dedicated tricks are used there; more advanced and generic variants are discussed below.

3-subset MITM

A common improvement over the basic attack was introduced by Bogdanov and Rechberger at SAC 2010.
In these attacks, one splits the cipher into three parts. For each guess of the key bits that are involved in the second and third part, one matches the forward and backward guesses but this is done based on only part of the state (partial matching). This makes it possible to cover additional rounds in the middle part. The downside is that partial matching leads to more false-positives, so you end up with a larger list of key candidates.

The recent attacks on GIFT by Sasaki that I mentioned in the comments are based on this 3-subset technique. In addition, he uses the "splice-and-cut" and "initial structure" techniques that originated in preimage attacks on hash functions (see next section). That work uses MILP modelling to optimize such MITM attacks on GIFT. The reason I mention it is because the simple structure of GIFT makes it a good introduction to such attacks.

Influences from hash function cryptanalysis

The use of MITM techniques to find preimages of hash functions goes back a long time, at least since Lai and Massey (EUROCRYPT 1992) (and probably earlier). For example, this technique is used in Leurent's preimage attack on MD4 from FSE 2008.

Soon after, a number of improvements were proposed by Aoki and Sasaki. In particular:

The splice-and-cut technique, introduced at SAC
2008,
with applications to MD4 and MD5.
Initial structures (as a generalization of local collisions) at EUROCRYPT 2009.

They also applied these techniques to reduced SHA-0 and SHA-1 at CRYPTO 2009. There are also several follow up works here, such as the additional improvements of Guo et al. with applications to SHA-2.

Generally speaking, this so called "splice-and-cut framework" led to major improvements in preimage attacks on hash functions. Of course, these attacks are about message recovery as opposed to key recovery. Nevertheless, the same principles can be applied to block ciphers.

The biclique, due to Khovratovich, Rechberger and Savelieva, is another tool that was initially introduced for preimage attacks. In these attacks, bicliques replace initial structures.
Bicliques were also (famously) used for key-recovery attacks on full-round AES, see the ASIACRYPT paper by Bogdanov, Khovratovich and Rechberger.

Other variants

Other variants that are worth mentioning are multidimensional MITM attacks (as mentioned in the question, some information can be found on Wikipedia), all subkeys recovery and sieve-in-the-middle attacks.

The all subkeys recovery attack is a way to deal with more complex key schedules. This is due to Isobe and Shibutani.

A sieve-in-the-middle attack is a generic improvement due to Canteaut, Naya-Plasencia and Vayssière, CRYPTO 2013. The idea is to replace (partial) matching by a sieving process which discards invalid transitions for a middle S-box. The middle S-box can be a superbox, so you can gain e.g. 2 rounds in many ciphers.

MITM as a general idea (including Demirici-Selçuk)

The first/last round trick as used in linear and differential cryptanalysis is basically a kind of MITM attack. At least in some cases, the number of rounds for which partial subkeys are guessed can be quite large, so that one essentially divides the cipher in three parts and performs matching in the middle using e.g. a linear approximation. Of course, here, there are again a bunch of specialized techniques.

Usually, the most significant part in such attacks is finding the right statistical properties as opposed to the key guessing part. This sets them apart from the MITM attacks described above and hence they are not usually referred to as MITM attacks.

A good example of an attack that is universally referred to as a MITM attack, but which doesn't belong to one of the MITM attacks described in the above sections, is the Demirici-Selçuk attack.

The basic DS-MITM is an attack on the AES based a 5 round distinguisher. Note that this distinguisher is not really a (simple) square attack. Rather, it's an extension of a 4 round distinguisher due to Gilbert and Minier which in turn extends the classical integral/square distinguisher for 3 rounds of the AES. The 5 round distinguisher is extended to 7 or 8 rounds by partial key guessing. I won't go into the details (this should probably be a different question).

Just to give a glance of the importance of this attack, here's a brief chronological overview of follow-up research on this topic:

Some improvements are given by Demirici et al. in Improved
Meet-in-the-Middle Attacks on AES at INDOCRYPT 2009.
Dunkelman, Keller and Shamir presented improvements in Improved Single-Key Attacks on 8-round AES at ASIACRYPT 2010. They introduce multiset tabulation, differential enumeration (main improvements) and key bridging.
Derbez, Fouque and Jean gave further improvements at EUROCRYPT 2013 in Improved key recovery attacks on reduced-round AES in the single-key setting.
Other imrovements by Derbez and Fouque at FSE 2013 in Exhausting  Demirci-Selcuk Meet-in-the-middle Attacks Against Reduced-round AES.
Li, Jia and Wang (FSE 2014) use use key-dependent sieving to obtain a better 5 round distinguisher (leading to improvements in the 9 round attack).
The latest (from 2016) improvement that I'm aware of is due to Li and Lin and extends to 10 rounds (note: this is for AES-256).

The DS-MITM attack also applies to other ciphers. For instance, this paper from ASIACRYPT 2018 uses constraint programming to automate the process with applications to several lightweight ciphers. Not all of the extensions (in particular differential enumeration) are automated though.


RS Erasure Coding and Shamir's Secret Sharing So I was trying to understand the basic difference between erasure coding and secret sharing, and I found this paper (that you can find here or here).
For what I understand, it states that Shamir's Secret Sharing is basically a particular instance of a Reed-Solomon Code;
However I cannot really understand the difference between any RS code and a SS coding from a security standpoint.

Imagine that I have an RS code (m,n) and a data chunk to encode. After encoding the data I will have n chunks, and if I want to reconstruct the data, I will need at least m shares of the data, right?

How this is different to an instance of Shamir's Secret Sharing (m,n), where I need m shares out of n to reconstruct the secret? Are they perfectly equivalent, or SS is some way more secure?

I admit to be really ignorant about the detailed technical/math aspects of how the two work, and I am more interested in the practical point of view.

Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements.  There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses.  The scheme creates a
polynomial
$$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$
distinct nonzero
elements $\alpha_1, \alpha_2, \ldots, \alpha_n$.  Note that $n$ must be at least
as large as $m$ and cannot be larger than
$q-1$.  The $n$ pieces of the secret that are handed out to those sharing in the
secret are just these polynomial values $S(\alpha_1), S(\alpha_2), \ldots, S(\alpha_n)$.

Given $m$ of the $n$ shares, the Lagrange interpolation formula gives the unique
polynomial $T(x)$ of degree $m-1$ or less that interpolates through these $m$ points,
that is, for each share $[\alpha_j, S(\alpha_j)]$ that is available to the reconstructor,
$T(\alpha_j)$ equals the share value $S(\alpha_j)$.  Therefore, $T(x)-S(x)$ is a
polynomial of degree $m-1$ or less that has $m$ roots in the field, and by the
Fundamental Theorem of Algebra, must be zero.  Thus, $T(0) = s_0$ is the secret.

  If $m$ shares are available, the secret can be recovered.

If more than $m$ shares are available, any $m$ of them can be used
to reconstruct the secret.  Shamir also showed that if fewer than
$m$ shares are available, then
the secret cannot be recovered; in fact, all possible $q$ values of
the secret are equally likely to be obtained if one interpolates through
fewer than $m$ shares.

The McEliece-Sarwate generalization of this scheme via Reed-Solomon
codes has two aspects.

First, by using the error-correcting properties
of Reed-Solomon codes, it is possible to recover the secret even if
some of the shares are in error.  Here, error means that the
shareholder submits a share value that is different from the value
given to him/her.  Such errors could be due to malice, or could occur
because of accident (e.g. a flash drive holding the
share is forgotten in a pocket and gets washed in a clothes-washer).
In the standard Shamir reconstruction, damaged shares are no different
from valid shares and Lagrange interpolation will almost always
reconstruct a "secret" that is different from the original.  Unless
there is error control built into the secret (e.g. a CRC checksum),
there is no way of knowing that the recovered "secret" is different
from the original.  On the other hand, the properties of Reed-Solomon
codes say that if $m+t$ shares are available of which at most
$\lfloor t/2\rfloor$ are in error, then by using a Reed-Solomon
decoding algorithm, the secret can be successfully recovered.  The
reconstructor does not need to know which shares are in error (if
this were known, the damaged shares could just be ignored!).  The
decoding algorithm also indicates which shares, if any, of the
$m+t$ submitted shares are in error, that is, cheaters (or launderers!)
can be identified, and of course the correct share values can be
computed and given to the innocent share holders on new flash drives.
It is also true that if more than $\lfloor t/2\rfloor$
shares are in error, the Reed-Solomon decoding algorithm will quite likely
refuse to reconstruct a secret, and will reconstruct a "secret"
different from the original only in rare circumstances.  Note that
a failure to reconstruct a secret is not fatal (unless $m+t = n$)
since one can always await the submission of more valid shares so
that the effect of the invalid ones can be overcome.  In this form,
there is no difference between the security of the Shamir scheme and
the Reed-Solomon coding scheme.
The second aspect of Reed-Solomon coding schemes considered
in the McEliece-Sarwate paper is that it is not necessary to
fill up $S(x)$ with $m-1$ randomly chosen symbols.  In fact,
the secret can be all $m$ symbols $s_0,\ldots,s_{m-1}$ instead
of just $s_0$ being the secret.  One advantage is that we can
use a smaller finite field.  If the secret is $1000$ bits, say,
and $m=10$, Shamir's scheme would operate over $\mathbb F_{2^{1000}}$
and each share of the secret would also be $1000$ bits long.
$10$ kilobits ($10$ one-kilobit shares) would be needed to
recover the secret.  On the other hand, a Reed-Solomon coding
scheme could divide the secret into $10$ $100$-bit symbols and
operate over $\mathbb F_{2^{100}}$.  Also each share would
be $100$ bits long, and, as before, only ten such short shares
would be needed to recover the secret.  This reduction in the
field size does come at some cost in security.  If only $9$
shares are available to a cabal and they guess at possible
values of the tenth needed share, they can come up with a
"short list" of only $2^{100}$ values that the $1000$-bit secret might
have.  Shamir's scheme in a similar predicament would have
a list of $2^{1000}$ possible values of the secret, thus
providing perfect security.  The trade-off between reduction
in security and ease of implementation as well as storage of
each share of the secret is something that needs to be evaluated
for each application.  The most secure scheme has shares that
are as long as the secret while the Reed-Solomon scheme can
be used to reduce the share size at the cost of reduced
security.

Edit Another version of secret-sharing gives the $i$-th share
holder the value of $\alpha_i$ as well as the share $S(\alpha_i)$
(this requires twice as much storage).  Thus, $m$ share holders
can reconstruct the secret if they know Lagrange interpolation
and have access to a computer that does the needed finite-field
arithmetic without anyone else knowing about it.  In the standard
scenario, the $i$-th
share holder only has $S(\alpha_i)$ without any knowledge of
$\alpha_i$, and only an official reconstructor knows that Joe
Blow is the $i$-th share holder and looks up $\alpha_i$ when
Joe submits his share for reconstruction purposes.
In this case, secret re-construction
can only be done by the official re-constructor; a cabal
of $m$ rebellious share holders cannot reconstruct the secret
in private and use it to overthrow the Evil Empire.
When share holders actually have $[\alpha_i,S(\alpha_i)]$,
a cheater could alter either quantity or both, and an innocent
error might do likewise.  The solution to this problem is more
difficult.  For what can be done in such
cases, see, for example, here.


GPG and PAR2 error correction data from the plain archive, will it compromise security? I have the following scenario:

Archives compressed with 7z, hundreds of MiB in size
GPG to encrypt the archives (binary, without ASCII armor)
PAR2 to create error correction data

Question

1. Encrypted archive + plain archive error correction data

If I encrypt the archive, will it compromise the security of the GPG-encrypted data if the error correction data created before the encryption will be stored along with the encrypted archive?

2. Encrypted archive + encrypted archive error correction data

As an alternative, would it be better to calculate the error correction data from the encrypted data after encryption and would this in any way affect security (common sense tells me no, but you never know).

Why?

Rationale

I need to archive the data in question and want to make sure it can be restored even if it gets damaged in some way. But all of that of course without compromising security.

You could GPG-encrypt both the .7z archive and the PAR2 error-correction data.  That will take care of the security issues.

Alternatively, you could compute the PAR2 error-correction data on the results of the GPG encryption, for the reasons Ricky Demer explains.  That would be secure too.

Either one works.


What are the implications of a birthday attack on a HMAC? After collecting approximately $2^{n/2}$ message-tag pairs a collision can be observed. So two different messages (m1 and m2) will have the same tag.

This paper states:

  Then, for any string x, (m1,x) and (m2,x) have the same tags (with high probability in the case of HMAC, and with certainty in the case of CMAC). The attacker can then request for the tag of (m1,x), thereby also obtaining the tag if (m2,x).

Does this mean that it is possible to attach any string x on m1 and the tag of it will be the same as the tag for x attached to m2?

If my assumption is true could this be considered as a length extension attack?

This is like stating that $H(C_1|m_1|x|C_2) = H(C_1|m_2|x|C_2)$ if $H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ for HMAC.

That is probably correct if $H$ is a hash function based on Merkle–Damgård construction (such as SHA-1 and SHA-2) and if $m_1$ and $m_2$ end on block boundaries.

$H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ implies that the state after hashing $C_1$ and $m_1$ is identical to hashing $C_1$ and $m_2$. So adding any data to either one will result in the same hash.

If however $m$ doesn't end on a block boundary then changing the data coming after $m$ will still alter the state after the block has been hashed; it is extremely unlikely that the result will be the same for $m_1$ and $m_2$ (if $m_1$ and $m_2$ differ for the last block of course). If $m_1$ and $m_2$ can be chosen freely then this situation can be avoided.

The situation for CMAC (and CBC-MAC) will be more or less identical. CBC is however explicit while Merkle–Damgård isn't. So this seems indeed more true for CMAC.

  If my assumption is true could this be considered as a length extension attack?

You could call this a length extension attack, it's at least pretty similar to one. With additional data coming after it it's more a kind of insertion attack, but the principles are the same.

Note that this is only applicable to the insertion of $x$, not the rest of the attack.


Bob has an EC key pair. How can he receive a small integer in the least compute intensive way? Alice wishes to send Bob a number $n$ between 0 and 255.

Bob has a private, public EC key pair $(b, B)$ where $B = bG$ and $G$ is an already agreed upon base point on the ed25519 curve.

Alice could roll a random number $r$ and perform a Diffie Hellman exchange to compute the shared secret $rB$. Alice could then use the shared secret $rB$ as a symmetric key to encrypt $n$, resulting in an encrypted payload $p$. Alice can then send Bob $R$ and $p$ where $R=rG$.

Bob would compute the shared secret as $bR$ and then use this as a symmetric key to decrypt the payload $p$ to discover $n$.

This requires Bob to perform some considerable computation, particularly the EC multiplication required to calculate $bR$.

What alternative method can Alice use to send $n$ to Bob, making use of Bob's EC key pair $(b, B)$, which would require the least taxing computation by Bob?

We are not too concerned with how taxing the computation is for Alice. It's only Bob's computation time that we wish to minimize.

Assume that observers of the communication are aware that some number $n$ between 0 and 255 is being transmitted. It is important that only Bob can discover Alice's choice of $n$, and important that an observer cannot detect when Alice sends the same value of $n$ to Bob twice. Observers are aware of Bob's public key $B$.

Given that many different people will want to send Bob a number $n$, it is perhaps likely that a good solution may involve Bob using a pre-computed lookup table of some sort.

The transmission to Bob cannot be interactive.

Suppose there are many different Alices: Alice 0, Alice 1, Alice 2, etc.  Suppose each Alice sends Bob not just one number, but a lot of numbers.

Bob has a secret Diffie–Hellman key $b$ and a corresponding public key $B$.  The $i^{\mathit{th}}$ Alice has a secret key $a_i$ and a corresponding public key $A_i$.  For some subset of Alices, Bob additionally stores a cache mapping $A_i$ to the shared secret $k_i = \operatorname{DH}(b, A_i)$.

For the $i^{\mathit{th}}$ Alice to transmit a number $m$, she generates a nonce $n$ uniformly at random and sends $A_i \mathbin\Vert n \mathbin\Vert c$, where $c$ is the authenticated encryption under key $k_i = \operatorname{DH}(a_i, B)$ of $m$.  When Bob receives $A_i \mathbin\Vert n \mathbin\Vert c$, he consults his cache to find $k_i$ from $A_i$, or computes $k_i = \operatorname{DH}(b, A_i)$ if it's not cached, and caches the result, with some cache eviction policy if you want to limit the cache size.

This way, if there are $\ell$ different Alices, Bob is required to compute only $\ell$ different DH computations—no matter how many numbers he may be receiving.  Depending on the cache eviction policy, he may need to recompute some of them from time to time.  With a good cache eviction policy, if the number of numbers received is much greater than $\ell$, you can save a lot of computation.

The NaCl crypto_box API enables this by separating the per-peer DH computation, crypto_box_beforenm, from the per-message authentication and decryption, crypto_box_afternm.  The control flow looks something like:

unsigned char k[crypto_box_BEFORENMBYTES];
unsigned char m[...];

if (!probe_cache(theirpub, k)) {
  crypto_box_beforenm(k, theirpub, mypriv);
  store_cache(theirpub, k);
}
if (crypto_box_afternm(m, c, clen, n, k) == -1) {
  bad();
}

You may have to be careful transferring key material intended for Ed25519 to the X25519 computations in NaCl crypto_box—figuring out how to do that safely, like XEdDSA does the other way around—is left as an exercise for the reader.


Common Modulus Attack not reproducible I want to calculate a simple example of the RSA common modulus attack. However, the result is not correct and I do not find my mistake.

p=$29,
q=37,
n=p*q = 1073,
\phi(n) = 1008,
e1 = 5,
e2 = 11$

Let $m = 999$.

$c_1 = m^{e_1} \pmod n = 296$,
$c_2 = m^{e_2} \pmod n = 555$

The extended Euclidean algorithm gives me $y_1$ and $y_2$: $y_1 \cdot e_1 + y_2 \cdot e_2 = 1$

$y_1 = -2, y_2 = 1$ (edited)

$m = c_1^{y_1} * c_2^{y_2} = 296^{-2} \cdot 555^1 \pmod {1073}$

How do I calculate $296^{-2}$? I tried to get the inverse of $296 \pmod {1073}$ and then square it, but $296$ has no inverse. What am I doing wrong?

In real word RSA modules are so large that probability for finding $c_1$ which is not coprime with $n$ is approximately zero.

  Also if you founded such number then $p=gcd(c_1,n)\neq1$ so $p$ is a factor of $n$ and in this case attack is not necessary because $n$ is factored.

$gcd(296,1073)=37\neq 1$ so $p=37,q=\frac{1073}{37}=29$ and $\phi(n)=1008$

Now you can easily compute private key $d_2$:

$e_2\cdot d_2=1 \pmod{ \phi(n)}$ so $d_2=275$.

  $$m={c_2}^{d2}\pmod n={555}^{275}\pmod{1073}=999$$


Encode ASN.1 PKCS#8 Private Key with Public Key and attributes I'm trying to encode an Ed25519 private key as a PEM file based on this document https://tools.ietf.org/html/rfc8410#page-7 .
I'm using an ASN.1 encoder written in Dart, and I can encode the private key without its public key and attributes as in this example:
-----BEGIN PRIVATE KEY-----
MC4CAQAwBQYDK2VwBCIEINTuctv5E1hK1bbY8fdp+K06/nwoy/HU++CXqI9EdVhC
-----END PRIVATE KEY-----

But I can't make sense of the specification on how to encode the public key and attributes like this one:
-----BEGIN PRIVATE KEY-----
MHICAQEwBQYDK2VwBCIEINTuctv5E1hK1bbY8fdp+K06/nwoy/HU++CXqI9EdVhC
oB8wHQYKKoZIhvcNAQkJFDEPDA1DdXJkbGUgQ2hhaXJzgSEAGb9ECWmEzf6FQbrB
Z9w7lshQhqowtrbLDFw4rXAxZuE=
-----END PRIVATE KEY------

Using the lapo.it ASN.1 decoder you can see the optional fields, but I can't recreate it. What does the 0 and 1 mean? And why it doesn't have the annotated type?

This is more about representation and manipulation of data in a computer program than cryptography. Questions about Dart or the use of libraries in Dart, are better asked on Stackoverflow.
The [0] and [1] are context-specific tags; more exactly they are tags that are not universal (because then the number-type mapping would be fixed and known) with a class that is not specified and thus defaults to context-specific.
Because they are IMPLICIT, the top-level ASN.1 type of their contents is not encoded, and cannot be shown by a generic decoder like the one you link -- see a page earlier, above the table of universal types.
[0] is Attributes which in rfc5958 (and many other places) is SET OF Attribute (with infoset constraint) where CMS-style Attribute is SEQUENCE { attrType OBJECT IDENTIFIER, attrValue SET OF ANY --DEFINED BY type-- } in the old ASN.1 notation, or with attrValue defined by an infoset in the new notation. Thus the decode of [0] shows the one SEQUENCE of OID plus SET containing UTF8STRING.
On the other hand, [1] is PublicKey ::= BIT STRING which has no internal structure, so it is shown as raw data -- including the prefixed value octet for unused_bits = 00, so the real value of the publickey is the remaining 32 octets.


Why isn’t SHA-3 in wider use? SHA-3 was released by NIST just over 4 years ago this week. In my experience it does not seem to be as widely used as I might have expected. I see SHA-2 and even SHA-1 more often. What are your opinions on why this is the case?:

First, you're taking the question backwards. Inertia is the default position. You shouldn't be looking for reasons not to switch, but for reasons to switch. If there are no strong reasons to switch, nobody will switch.

Security is not a reason. Between SHA-2 and SHA3, there is no reason to believe that one is more secure than the other. It isn't like when switching from MD5 to SHA-1 or from SHA-1 to SHA-2, where in each case the older function has structural weaknesses that did lead to attacks, and had a smaller output size that was starting to raise concerns over brute-force attacks. SHA-2 and SHA3 have the same sizes and no known structual weaknesses.

Performance is not a reason for most applications. Indeed, performance is a reason not to switch. SHA3 is slower than SHA-2 on a general-purpose processor. It was one of the slowest finalists of the SHA3 competition across various processors. This is not a big reason not to switch, because hashes are pretty much never a bottleneck, but it's certainly not an incentive to switch.

SHA3 does have a performance benefit, which is that it's cheap to implement in specialized hardware. It's very fast on a dedicated circuit. This is especially important for low-power devices: SHA3 costs fewer Joules per byte than SHA-2 (or any other SHA3 finalist) when implemented in hardware. So IoT may drive the adoption of SHA3. However, hardware design takes time, and hardware designers are conservative (you can't fix bugs in hardware), so this won't happen any time soon. Furthermore, a hardware implementation of SHA3 uses more gates than SHA-2, so it costs more to build a SHA3 device, even if it costs less to use afterwards, therefore there isn't a clear cost incentive to switch even when a low power requirement is critical.

SHA3 also has a versatility benefit. The same core primitive (the Keccak sponge) can not only be used as a hash, but also as a MAC (KMAC, at lower cost than HMAC), as a key derivation function (SHAKE with a partially-secret input, at a lower cost than constructions such as HKDF), etc. It's not that SHA3 can do things that nobody else can do, but it can do things that otherwise require more complex combinations of primitives. That's an incentive to switch, but only in circumstances where 1. you need those extra things and 2. it is a problem to combine more code. Again, IoT (which wants low-cost, low-power devices) may look towards SHA3, but only once protocols that use more than SHA3's hash functionality are defined and start being deployed.

Coming back to security, a benefit of SHA3 is that it's very different from SHA-2. Indeed this is one of the main reasons it was chosen over other SHA3 proposals: since its construction is different, if a new class of attacks breaks SHA-2, it's unlikely to apply to SHA3, and vice versa. The security benefit would not be in switching to SHA3, but in deploying software and protocols that support both, so that if a weakness is found in SHA-2, the world can quickly and cheaply transition to SHA3.