Are there any other applications of machine learning to cryptography?

While your question is somewhat opinion-based and it depends on how far we stretch cryptography, my answer (having some experience in both fields) would be no, there are no applications of Machine Learning in cryptography.

Why?

Well, for starters, machine learning is made to find some regularities in input data and to produce output data from it. This requires a lot of inputs and well defined function that will define if we are doing good or bad. And they operate on floating-point numbers (they might lose some accuracy with result).

Cryptography and cryptographic functions are designed to be very random-looking and to be very complex. They are designed so that there are no visible structures in output data. They are nearly always defined on integers.

So cryptographic data can't be easily mapped onto machine learning data, because for machine learning 1.0 and 1.5 are close, but in cryptographic sense they aren't close, they are just numbers. And for machine learning representing data in meaningful way is very important to get meaningful results. This is nearly impossible with inputs and outputs from most cryptosystems.

I will ignore your first point, as this probably deserves investigation into it on it's own (but I think most of us fail to believe that those results are correct - it might be worth asking question about that paper specifi).

  Side-channel attacks. This looks more promising, especially power analysis attacks, there are some very interesting articles where ML is used on power signal.

Now depends if we call that cryptography. I'd say that Machine Learning in this case is used to extract data. We can represent power-consumption as floats, and we can represent results as confidence in key bit. However, I do not agree that this is strictly cryptography, as this isn't really meaningful way to connect Machine Learning to cryptosystem. This is barely used as way to analyze data. For me it's like saying that medicine and cryptography are related fields, because cryptosystems are used to secure medical records.

  Machine learning on encrypted data. This one needs homomorphic encryption, as I see it, there is a bunch of articles too.

This is something I don't understand. Homomorphic encryption allows us to modify encrypted data to some extent and Machine Learning allows us to find regularities in data. Just because both were used, I won't say that both are related.

Summary

Cryptosystems are used as means to operate on data (including encryption and verifying). This is merely usage of cryptography. Cryptography is art of designing and verifying security of such systems.
Machine Learning is used to analyze data and produce some action based on data. This is again just usage of Machine Learning, not "machine learning in cryptography".
So to clarify: Machine Learning is applicable when we have input which we can efficiently map into ML and we want to act upon input. This applies to any data which we can efficiently map into ML. Cryptographic functions can't be efficiently mapped into Machine Learning input, so Machine Learning is of no special use in cryptography (but it can analyze some non-cryptographic data even when evaluating cryptographic designs).

So I guess answer can also be: There are infinitely many applications of machine learning in cryptography, just as any other field.


What is the forward cipher function of AES-XTS?

With OpenSSL the forward cipher for EVP_aes_265_xts is AES 256. The key being 512 bits, internally split into two 256 bit keys for each of the AES 256 ciphers used within the XTS mode of operation.


The construction is trivially neither collision resistant nor second preimage resistant, since XOR is commutative. I.e. for any $a,b$ it holds that $a\oplus b = b \oplus a$.
Consequently, given $M_1,M_2$ as a first preimage, we can trivially find $M_2,M_1$ as a second preimage. To break collision resistance, simply choose $M_1,M_2$ arbitrarily.


Matsui's paper on linear cryptanalysis - unexplained formula in Lemma 2

This is a type of "Gaussian approximation", assuming the wrong key randomization hypothesis, and given the bias $|p-1/2|$, the success probability depends on the order statistics of the "sample bias" of the various subkey bit guesses.

Let $T_i$ be the number of times the linear approximation is satisfied by subkey guess $k_i,$ and $$Y_i=|(T_i/N)-1/2|,$$ is the sample bias corresponding to this subkey guess ($N$ is the number of plaintext/ciphertext-pairs). Let $k_0$ be the right key guess and let there be $2^m$ subkey values possible, say from $0$ to $2^m-1$.

Then linear cryptanalysis is successful if and only if
$$Y_0>Y_i,\quad 1\leq i\leq 2^m-1.$$

This probability is then estimated via a gaussian approximation.

The paper "On Probability of Success in Linear and Differential Cryptanalysis", from the Journal of Cryptology, by A. A. Selcuk available here goes over this in detail.


Truncating ciphertexts on ring-LWE schemes

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again.

This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ciphertext as a bitstring, and then discarding the $i$ least significant $w$-words of each bitstring. It also explains why $w^i c'$ is equal to c with the $i$ least significant $w$-words of $c$ being set to $0$, as the authors say in the next sentence of Section 5.4.

By the way, $w$ does not represent the number of bits in each word. Instead, $w$ describes the size of each word, and so the number of bits in each word is actually $log_2(w)$.

If you're interested in other examples of where the technique of discarding the lower-order bits is used, see works on the Learning with Rounding problem. (The paragraph in the middle of page 2 gives an equivalent explanation of this notation.)


What does "sequential memory-hard" mean?

The Scrypt paper here defines memory-hard and sequential memory hard, and accordingly explains why one was used over the other.

Definition 1. A memory-hard algorithm on a Random Access Machine is an algorithm which uses $S(n)$ space and $T(n)$ operations, where $S(n) \in \Omega (T(n)^{1-\epsilon})$

Definition 2. A sequential memory-hard function is a function which  (a) can be computed by a memory-hard algorithm on a Random Access Machine
in $T(n)$ operations; and  (b) cannot be computed on a Parallel Random Access Machine with $S∗(n)$ processors and $S
∗(n)$ space in expected time $T∗(n)$ where $S∗(n)T∗(n) =\mathcal{O}(T(n)^{2-x})$ for any $x > 0$.

Put another way, a sequential memory-hard function is one where not only the
fastest sequential algorithm is memory-hard, but additionally where it is impossible
for a parallel algorithm to asymptotically achieve a significantly lower cost. Since
memory-hard algorithms asymptotically come close to using the most space possible given their running time, and memory is the computationally usable resource
general-purpose computers have which is most expensive to reproduce in hardware
, we believe that, for any given running time on a sequential general-purpose computer, functions which are sequential memory-hard come close to being the most
expensive possible functions to compute in hardware.


No, use SHA256.

If you look at https://bench.cr.yp.to/results-hash.html it seems that SHA256 would probably be the better choice concerning speed as well. Therefore I don't see a good reason to go with SHA-1.


Mechanism to get 10 pseudo-random positive numbers up to maximum from a seed (32-byte hash)?

The best way to do this would probably be through an iterative hash, where you use that seed as an input, and from each iteration you extract a certain amount of bits for conversion to a number. A 32-bit extraction allows numbers up to around 4 billion.

I would do it as follows:

A = Hash(Seed)
Extract1 = lower 32-bits of A
Number1 = Extract1 mod (MaxVal)
B = Hash(A)
Extract2 = lower 32-bits of B
Number2 = Extract2 mod (MaxVal)
... and so on

This will prevent the numbers from having any special relationship with eachother, other than the fact they use the same seed, your suggested example means that the next number directly depends on half the previous number plus an additional 8-bits of unknown information. For a lottery that would be bad. This method means the output depends pseudorandomly on an additional 224-bits of information (assuming the hash is 256-bits).

The iterative sequence is deterministic and will always produce the same values from a given seed, and can generate both enormous numbers as well as enormous quantities of numbers, if needed.

If you want to be able to publish proof of the seed PRIOR to the lottery draw, you can post a digital signature of the seed, that way players would be assured you are not going to manipulate the seed after players are selected in order to generate winning values for a specific player. Just makes sure the signature uses a different hash function.


RSA: Detecting period of unconcealed messages

Convention states that $P > Q$.
At best, there are 9 unconcealed messages. I'll refer to these as $U_0$ through $U_8$.
Here are some relationships between these.

\begin{align*}
U_0&=0\\
U_1&=1\\
U_2&=kP, &&\text{where $k=1$ to $Q/2$. Test if unconcealed. Stop once you find one.} \\
U_3&=kQ, &&\text{where $k=1$ to $P/2$ (try $U_2\pm1$ before trying multiples of $Q$).} \\
U_4&=U_2+U_3 \bmod N \\
U_5&=N-U_4 &&\text{(also, $U_6+U_7 \bmod N$)} \\
U_6&=N-U_3 \\
U_7&=N-U_2 \\
U_8&=N-U_1 \\
\end{align*}

Looking at this example, there is no period for unconcealed messages. Also note $e$, $\phi$, and Carmichael values are not needed.

$P=47, Q=23, N=1081$, where $e$ results in 9 unconcealed messages.

\begin{align*}
U_0&=0 \\
U_1&=1, &U_8&=1080, &U_1+U_8&=N \\
U_2&=46, &U_7&=1035, &U_2+U_7&=N \\
U_3&=47, &U_6&=1034, &U_3+U_6&=N \\
U_4&=93,  &U_5&=988, &U_4+U_5&=N \\
\end{align*}

The most you'll need to test is $(P+Q)/2$ and will often be far less. This reduces the number-space you need to search.

For clarity:

$$U_0=N \bmod N, \quad \text{or $0$}$$

The first pair is $U_1=N+1 \bmod N$ and $U_8=N-1 \bmod N$. Their sum equals $N$.

The second pair, $U_2$ and $U_7$ are a multiple of either $P$ or $Q$ and sum $N$. If the is a multiple of $P$, then you only need to search to $Q/2$ as these mirror each other. Once you go beyond $Q/2$ you are testing the same values against the other half of the pair.

Similarly, the third pair, $U_3$ and $U_6$, will be a multiple of the other factor with the same consideration (sum $N$ and test to $P/2$ assuming this is a multiple of $Q$). This would be $Q$ if the second pair were a multiple of $P$, and $P$ if the second pair were a multiple of $Q$. The small numbers which I've tested, $U_3$ is $U_2\pm1$. Which means $U_6$ is also $U_7\pm1$. I don't know why this is, or if this holds for larger numbers. I have yet to code this and test.

The fourth pair, $U_4$ and $U_5$, also sum $N$. This pair is calculated from pair two and three. $U_4=U_2+U_3$, you can append '$\bmod N$' for consistency, but since both are $\mathit{factor}/2$, these will always sum less than $N$. Conversely, $U_5$ is the sum of $U_6$ and $U_7$, both on the high side of $\mathit{factor}/2$ due to their relation of $U_2$ and $U_3$, therefore will sum greater than $N$ and will require '$\bmod N$'.

So, three unconcealed messages are known, $U_0$, $U_1$, and $U_8$. By discovering $U_2$ and $U_3$, the remaining four can be calculated. In the process of discovering $U_2$ and $U_3$, the multiple, $k$, ranges from $1$ to $\mathit{factor}/2$. You can stop once a factor is found because the compliment is calculated. Then test $U_3$ as $U_2\pm1$ before testing multiples of the opposite factor.

When the selection of $e$ results in more than 9 unconcealed messages, these same 9 are always the same, as they are based on $P$ and $Q$.

There are three simple formulas, $U=k*\mathit{factor}+1, U=k*\mathit{factor}, U=k*\mathit{factor}-1$, which demonstrate concisely how and why these 9 relate to each other the way they do. It was an awesome discovery and I'll share in another post.


Can anyone answer me, if I can embed a message when I convert it to ASCII value to points on Elliptic curve $E(Fp)$ , by multiplied the ASCII value with a base point B?

This is probably a rather more extensive answer than what you were looking for; however here it goes:

There are a number of reasons why we might need to convert a 'value' to a curve point, that is, define a function $F(x)$ that takes a value $x$, and maps it to a point on $E(\mathbb{F}_p)$; there are also a number of ways to do so.  Which one is best depends on the requirements that the use case demands.  Some on the requirements to consider:

Does it need to be invertable?  That is, if you're given a point $F(x)$, do you need to be able to recover $x$ (or, do you need that the problem of recovering $x$ to be difficult)?  Some use cases need it to be invertable, others don't care.
Do you need to obscure the relationship between two mapped points?  That is, if someone knows $x, y$, is it a problem if they can deduce the discrete log of $F(y)$ to the base $F(x)$; that is, if that can find the value $n$ s.t. $n \cdot F(y) = F(x)$?  For some use cases, it is critical that this be a hard problem; for others, it isn't important.
How important is side channel resistance?  If someone can listen into the computer evaluating $F(x)$ (e.g. by monitoring the timing), how important is that they not be able to get information on $x$?  Again, for some use cases, this is critical.

Within those three requirements, there are three obvious strategies to implement $F(x)$:

Use simple point multiplication, which is your original idea, define $F(x) = x \cdot G$, for the curve generator point $G$.  This is moderately efficient (using code you probably have lying around anyways) and (depending on your point multiplication routine) potentially side channel resistant; however it obviously makes the discrete log problem fairly easy.  And, it is potentially invertable with some work if the range of possible $x$'s are small - if we know that $0 < x < n$, this we can recover $x$ with $O(\sqrt{n})$ steps.
Use a 'hunt and peck' approach, as suggested by Koblitz.  You map the $x$ value into a potential $x$ coordinate, and then search for near-by values for which is the $x$ coordinate of an actual point (and then pick the $y$ coordinate somehow).  This can obviously be made either invertible or noninvertible as required, and it disguises any relationship between mapped points.  On the other hand, this isn't that efficient, and side channel resistance can be tricky (at least, I've seen people get it wrong).
Use a Hash2Curve algorithm, such as one found here.  These algorithms are quite efficient, and they obscure any relationship between mapped points.  On the downside, these algorithms are noninvertible, and the algorithms that can be used depend on the actual curve (generally, the value of $p$).

One last note: you appear to be asking how to embed messages in points so to use ECElGamal.  In practice, we never use ECElGamal; it is rather more practical to use ECIES, where we use the Elliptic Curve to share a point that only the encryptor and decryptor know, and use that point to derive a symmetric key that encryptions the actual message.  This solves the problem, without any need to map the message to a point.


Security of Shamir secret sharing with regards to the threshold

Absolutely no information about the secret is gained by having fewer than $k$ shares.  This is true regardless of what $k$ is, and for an adversary with unlimited computational power.  The secret is information theoretically hidden.

In at nutshell the reason for this is that, for every possible value of the secret, there exists a polynomial that interpolates it and the all the shares obtained.

Each share is a point on a degree $k-1$ polynomial $f$.  The secret is also a point on the polynomial, typically it is taken to be the point $(0,S)$ (i.e. $f(0)=S$, so the constant term of the polynomial is the secret $S$).

SSS uses the following fact: for every $k$ points, there exists exactly one polynomial of degree $k-1$ that goes through all these points. This can be shown using Legrange interpolation.

Let's say that you knew $k-1$ shares and were trying to figure out if $S'$ was the secret.  You think to your self, well if $S'$ is the secret, then I must have that $f(0)=S'$.  Then, I would have a total of $k$ points on $f$, namely $k-1$ from the shares I know of and I'm assuming you have the point $(0,S')$.  Such an $f$ always exists and could very well have been the polynomial generated by SSS, and so I cannot rule out $S'$ as the secret.

This is true for every value of $S'$, and so I gain no information about $S$.

Edit: a tangent about the case of $k=n$.  You can actually do something much simpler than SSS.  Randomly sample $n-1$ bit strings $s_1,\cdots,s_{n-1}$.  Then let $s_n=S\oplus s_1\oplus\cdots\oplus s_{n-1}$.  Note that the $s_i$ satisfy $S=s_1\oplus\cdots\oplus s_n$.  If any one share is unknown (WLOG, say $s_n$ is unknown), then $s_n$ is functionally a OTP that protects $S$.


Hashing with (some sort of) Public and Private keys/salt/nonce

What you are describing here looks like a thing, indeed. For instance, in the case of passwords, you have human-created password, whose entropy is generally weak and who are often found in dictionaries...

So, suppose you'd like to store the user's password in your database in a way that would prevent an attacker obtaining the database to deduce the actual password used by any given user, the simplest way around it might be to simply hash the passwords and store the hashes, right?

Well, if you just hash the passwords, then an attacker could simply take a dictionary and hash its content and compare it to the hashes he found in your database... So it wouldn't prevent the adversary to possibly find some passwords.

So, the next step is obviously to salt the hashes you are storing, in order to increase the cost of the dictionary attack for your adversary. And you can even use a different salt for each password, thus increasing the cost of a dictionary attack even more.

Note that modern hash functions, such as Blake2, sometimes includes support for salted and even for keyed hashing out of the box.

Modern password hashing algorithm, such as Argon2 are actually very similar to "proof of work", as you noticed, since you want to make your adversary consume as much time and power as possible.

There are also other cases where you'd want something like this (see how HMAC works, for instance.)


The birthday problem is the generic name for such questions. You have $n$ values, selected randomly and uniformly in a space of size $t$; the probability that at least two of these values are identical is roughly equal to $n^2/(2t)$. When $n$ becomes close to $\sqrt{t}$, then the probability raises sharply. In your case, with 5 hexadecimal digits, you have a space of size $t = 16^5$, so you can expect your first collision, on average, when you get about 1000 values or so.

An intuitive way to think about it is that $n$ values make about $n^2/2$ pairs, and, "somehow", each pair has probability $1/t$ of being a collision. (The pairs are not independent of each other, but the intuition still works in that case.)


PostQuantum Lattice-based schemes and Nguyen-Regev like attacks

NTRUSign does not have a security reduction of the type "if one can break the scheme then one can find short vectors in some lattice."  There are several other lattice schemes that do have such a reduction, and are therefore unaffected (as far as we know) by the Nguyen-Regev attack.  If they were affected, then we would have a better algorithm fro finding short vectors in lattices.


How can I do a brute force (ciphertext only) attack on an CBC-encrypted message?

If (you suspect that) the (plaintext of the) encrypted data is ASCII text, you can check if the high bit of each decrypted byte is zero.  As long as you have more than 24 bytes of data to check, the odds of that happening by chance are pretty low (given that you have a 24-bit keyspace).

UTF-8 text is also pretty easy to detect, since all bytes that do have the high bit set can only occur in a very distinctive pattern.

More generally, if you decrypt something with the wrong key, the output will look random, and thus all bytes (and all sequences of n bytes) will appear on average about equally often.  If you get output that deviates significantly from this (where significance can be measured e.g. using Pearson's χ2 test), it will most likely be the correct plaintext.

For small amounts of data, it may be useful to apply this test not only to the full bytes but also to their highest and/or two (and maybe even three) highest bits.  This will detect byte values that cluster together (as e.g. letters and numbers do in ASCII), even if there are not enough bytes in the data to get many exact repeats.  You can also try looking at the differences between two successive byte values (modulo 256) to detect correlations.  All these (and many other variations of them) should be uniformly distributed for random data, whereas many of them will show distinct deviations from uniformity for most kinds of non-random data.


What can a master password also be called?

I think the thing you are looking for is "escrow" as in http://en.wikipedia.org/wiki/Key_escrow.
Be aware though that the security of your system is reduced to the hardness for an attacker to find the master password which might be much easier than breaking the disk encryption scheme


For CBC, the IV must be chosen uniformly at random¹. Furthermore the IV must be independent of the plaintext: if you start sending a message encrypted with CBC, and then an adversary can submit some plaintext that will go in a later part of the message, they may be able to decrypt the whole message.

The output of a cryptographic hash function isn't necessarily uniformly random, but it may be close enough. Your method is very close to encrypting a counter, which is considered safe. But you're still saddled with the downsides of CBC: you must not allow the adversary to inject message content after they've seen the IV, and you must be very careful with padding.

I recommend using CTR instead of CBC. CTR is a lot easier to use correctly. All you need is that the counter does not repeat ever. It doesn't need to be random or unpredictable. Just remember that the counter is incremented with each block, not with each message.

In addition, consider whether you need to authenticate the message. If you don't have a good reason why it isn't necessary, then you definitely need to authenticate the message. To encrypt and authenticate the message, use an authenticated encryption mode such as GCM or CCM. Most authenticated encryption modes use CTR for encryption, but they may have different constraints on the IV due to the way they use it (and the IV for the authenticated encryption mode is not always used directly as the initial counter value for CTR).

¹  Exception: if the key is only ever used once then the IV can be anything.


Variants of Bilinear Diffie-Hellman Assumption

To the best of my knowledge, this hard assumption is introduced by Boneh and Boyen in this paper.

But I don't think so the assumption that you mention being hard, because $c=0$ is a simple solution for it. Then the element $g^{\frac{1}{s}}$ should not publish. Also, this assumption is not bilinear because the challenge is an element in the cyclic group of $\mathbb{G}$ and it is not $e(g,g)^{\frac{1}{\alpha+c}}$.


No, this is not a terrible idea, this is an idea that is often used.

Basically you've described the main use of a symmetric block cipher for exactly the block size of AES. AES is fully deterministic and not reversible without the key.

A block cipher is a Pseudo Random Permutation (PRP) - basically a map - from a set of all possible plaintext to a pseudo-randomly ordered set of all possible ciphertext. The possible plaintext and ciphertext consist of all possible values for the given block size, in this case 128 bits. This maps perfectly with your input and output size.

Beware that:

source ID's will always map to the same target ID's, even in time;
an attacker can see from identical target ID's that the same source ID was used;
if an attacker can change the target ID then it will decrypt to a random source ID;
if an attacker can switch known target ID's the reversed source ID's will be switched as well.

If above can lead to problems depends on your use case / threat model.


This isn't necessarily unexpected. 32-bit platforms vs 64-bit platforms can make a significant difference, as well as the amount of data you're hashing.

$ uname -m
x86_64

$ openssl speed sha256 sha512
The 'numbers' are in 1000s of bytes per second processed.
type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
sha256           29685.74k    79537.52k   148376.58k   186700.77k   196588.36k
sha512           23606.96k    96415.90k   173050.74k   253669.59k   291315.50

As you can see, on my 64-bit machine, SHA-512 beats SHA-256 for hashing anything more than 16 bytes of data at a time. And generally, the more data being hashed at once, the bigger the performance improvement.

Edit: As @MaartenBodewes points out in the comments, there's also SHA-512/256 which does the same computation as normal SHA-512 (with a different initial value) but truncates the output to 256 bits. This is a better option (due to the different IV) than simply truncating the output of SHA-512 to 256 bits by yourself in the case where you need the higher throughput but are limited to 256 bit outputs. Alternatively, if you really need higher throughput, BLAKE2b is an excellent cryptographic hash that is extremely fast and natively supports arbitrarily sized outputs (between 1 and 64 bytes).


How to make cookies tamper-proof and secure by using encryption and hash / MAC

I am going to answer my own question based on the comment from Ricky Demer:
https://crypto.stackexchange.com/a/16431/991

Given the attacker knew what the plaintext should be, for example:

{"userId":1}  --> this is knownText

And with the first approach, which was

aes-ctr((plaintext || sha2-256(plaintext)) || iv

Attacker can simply perform

(knownText || sha2-256(knownText)) XOR cipherText

To compute the AES cipher stream. Without having to know the key, the attacker can then compute:

(modifiedText || sha2-256(modifiedText)) XOR [deduced AES cipher stream]

Where modifiedText can be

{"userId":2}  --> I want to pretend to be user 2

and then append the original IV.

This would decrypt fine and also validates fine given the first approach. Hence it is insecure.


What is this problem called and is it hard? given $g^x$ output ($g^y, xy$)

This problem is equivalent to the CDH problem:
Here is how to solve CDH given an Oracle that solves this problem:

Given $g, g^x$, we can compute $g^{x^{-1}}$ (which is equivalent to the CDH problem) by doing the following:

Call the Oracle with $g, g^x$; the Oracle gives us a pair $g^{y}, xy$

We compute $(g^{y})^{(xy)^{-1}} = g^{x^{-1}}$, hence showing one side of the equivalence

And, repeating my comment, here is how to solve this problem given a CDH Oracle:

Given $g, g^x$, we select an arbitrary value $z = xy$, and compute $(g^x)^{z^{-1}} = g^{y^{-1}}$.

We then invoke the CDH Oracle with $g, g^{y^{-1}}$ to recover the value $g^y$

We then return the values $g^y, z$, which shows the other side of the equivalence.


Can we reverse a hash when we know part of the input?

It depends of course on the hash function you're dealing with. Assuming it is a cryptographically secure hash function, you're still looking at brute forcing the output: in other words, trying every possible input, computing the hash and then comparing with the output. Finding two inputs with the same output is a hash collision. Consider the MD5 hash function, which is no longer considered secure, the known collision attacks end up flipping more bits across the whole input, so depending on exactly which parts of the input you know, you might be closer to a collision.

However, most hash functions besides MD5 have only theoretical collision attacks, with no known working examples. If you aren't extremely lucky, then you will have to search for exactly as long as for what you know is different from the real input.

Knowing part of the input does reduce the search space of your brute force attempts, especially if you know the total size of the input. Most hash cryptographic functions can be used a checksums, which means they can function on inputs of arbitrary length. So in other words, if you don't know the total size of the input, then you may be searching literally forever.

If you know the input class to the hash function is fairly straightforward (for example, it's an English dictionary word, or a series of words), then you can potentially employ a rainbow table. If the input is sufficiently noisy, the rainbow table becomes prohibitively large, which is why salt is an effective countermeasure.


Length-regular: if $x$ and $y$ have the same length, then $f(x)$ and $f(y)$ have the same length.
Length-preserving: $x$ and $f(x)$ have the same length.
Examples:

$f(x) = \overline{x}$ (flip every bit in $x$): length-preserving.
$f(x) = x \|x$ (concatenate $x$ with itself): length-regular but not length-preserving.


What is the difference between a dual cipher and a tweak?

For distinct tweaks $t \ne \tau$, the ciphers $E_{k,t}$ and $E_{k,\tau}$ should appear to be independent uniform random permutations for uniform random $k$.  For example, you could think of it like having a single-bit tweakable block cipher where $E_{k,0} = \operatorname{AES256}_{k_0}$ and $E_{k,1} = \operatorname{Serpent256}_{k_1}$, where $k_0$ and $k_1$ are like magic independent uniform random bit strings somehow both deterministically derived from $k$.

For dual ciphers $E \ne E'$, $E_k$ and $E'_k$ are very much not independent—there is a deterministic relation between them for every $k$, namely $f(E_k(p)) = E'_{g(k)}(h(p))$ for some deterministic functions $f$, $g$, and $h$.


There is actually no difference between what you are describing. One of the issues with writing proofs, is that a separate reduction must be proven for every element of the construction (you cannot reduce security to a hash function and DDH in one shot). In order to facilitate this, one writes hybrid games and then proves each hybrid via a reduction. In some cases, you only need to reduce to one thing (e.g., DDH), in which case there is no need for any hybrids. However, even in these cases, some people prefer writing very clear hybrid games. The question of how to know what is best is really just experience and more experience. I refer you to Victor Shoup's tutorial on game-based proofs. I also have a tutorial on simulation-based proofs. These can help.


How SPHINCS+ Hash Signature ADRS structure define

Well, the ADRS structure is an 32 byte structure, organized as 8 4-byte words.  It looks like:
  +--------------------+
  |   Layer address    |
  +--------------------+
  |    Tree address    |
  |      (3 words)     |
  |                    |
  +--------------------+
  |        Type        |
  +--------------------+
  |  Keypair address   |
  +--------------------+
  | Chain/Tree Height  |
  +--------------------+
  | Hash addr/Tree Idx |
  +--------------------+

The idea behind the ADRS structure is that every single hash computation within Sphincs+ gets a separate ADRS structure.  Because the ADRS structure is an input to the hash, someone brute-forcing the hash computation would need to select the ADRS structure, which means that their brute-force search cannot take advantage of any multitarget attacks.
As for what the various fields within the ADR structure designate:
Layer address - Which Merkle tree level we are working on (0 is the lowest); also 0 if we're working within the FORS tree
Tree address - Which Merkle tree (counting from the left) in this level we are working on.  This is used for FORS, WOTS and Merkle tree hashes.
Type - An indication of why we are doing this hash in the first place; this ensures that, say a hash we do for the FORS does not collide with a hash we're doing for the WOTS
Keypair address - Which WOTS leaf are we working on (counting from the left of the Merkle tree).  Not used during a Merkle tree hash.
Chain/Tree Height - During WOTS, which Winternitz chain we are working on.  During FORS, what height we are in the FORS tree (1 being the bottom).  Unused during a Merkle tree hash.
Hash addr/Tree Idx - During WOTS, where in the Winternitz chain are we (with 0 being the first node in the chain).  During FORS, the horizontal position of the node we're computing (counting all the FORS trees under the current WOTS leaf); the later includes both "where in the FORS tree we are hortizontally", as well as "which FORS tree this is".  Unused during a Merkle tree hash.


What differences between Menezes–Vanstone ECC and ElGamal ECC?

The essential difference between these two encryption schemes is that for standard ElGamal encryption on elliptic curves the plaintext space is the set of points in your elliptic curve group while in Menezes-Vanstone (which can be considered as a variant of ElGamal) the plaintext space is $F_p^*\times F_p^*$ where $F_p$ is the field over which your curve is defined. So what does this mean?

This means that when using ElGamal over elliptic curves you have to map the message to an elliptic curve point before encryption, while when using Menezes-Vanstone you can take your message string, split it up into to halves and interpret these two strings as elements of $F_p$ each.

Alternatively, you can use other "encoding free" variants of ElGamal such as "hashed ElGamal" that avoid the task of mapping
messages to points on the curve. In standard ElGamal on elliptic curves you would compute
the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the message $m$
mapped to a point on the curve, $Y$ the public key and $P$ the generator point.

In hashed ElGamal, the ciphertext is $(C_1,C_2)=(kP,m\oplus H(kY))$ where $H:G\rightarrow \{0,1\}^n$
is a hash function that maps points on the curve to $n$ bit strings. Consequently, you can encrypt $n$ bit
messages, for instance 256 bit if you use SHA-256 for $H$. For the input to $H$ you need to encode the points of the curve in a suitable way.

Regarding performance, standard ElGamal on elliptic curves costs two scalar multiplications and one point addition, where Menezes-Vanstone costs you two scalar multiplication and two multiplications in $F_p$. So Menezes-Vanstone will be cheaper from a computational point of view.

Regarding ciphertext expansion, to encrypt a message (mapped to a point on the curve) with ElGamal, the ciphertext will contain 2 elements of the curve group (which in affine coordinates will be four elements of $F_p$ - and you can bring it down to ~ 2 elements of $F_p$ when using point compression). In Menezes-Vanstone to encrypt a message (which fits into two elements of $F_p$) the ciphertext will contain one element of the curve group (2 elements of $F_p$) and another two elements of $F_p$ (so you have four elements of $F_p$ and using point compression you  come down to ~ 3 elements of $F_p$).

When using ElGamal on elliptic curves you can prove that it provides indistinguishability under chosen plaintext attacks (IND-CPA security), where Menezes-Vanstone does not provide IND-CPA security (this paper shows that it is not a probabilistic encryption scheme and thus not IND-CPA secure). So you should definitely not use the Menezes-Vanstone scheme.

Alternatively, a standardized scheme for public key encryption on elliptic curves is ECIES, which provides stronger security guarantees (IND-CCA security) than ElGamal does (there are ElGamal variants such as Cramer-Shoup wich are IND-CCA secure, but not that efficient as ECIES).


How is the generator used in Feldman's Verifiable Secret Sharing scheme determined?

The multiplicative group $\mathbf{Z}_p^*$ of non-zero integers modulo $p$ is cyclic of order $p-1$, so it has exactly one subgroup of order $k$ for each divisor $k$ of $p-1$.To obtain an element $g$ of $G$, take any element $a$ of $\mathbf{Z}_p^*$ and let $g = a^{(p-1)/q} \bmod p$. Then $g$ is an element of $G$ because
$$g^q = \left(a^{(p-1)/q}\right)^q = a^{p-1} = 1 \pmod p.$$

The order of $g$ is a divisor of the order of $G$, so it is a divisor of $q$, and since $q$ is prime, it equals either $1$ or $q$.


Is XORing a SHA256 better than truncating it?

As pointed out in an answer to an older question, SHA-224 is more or less just using the first bits of the output of SHA-256. That is just about the most official construction anyone can find.

The XOR approach is however not entirely unprecedented, for example Linux uses that approach on SHA1 in order to generate random bits.

There is real security to be gained by not using either approach, but instead use a cryptographic hash to reduce the 256 bits down to 128 bits. This would provide protection against length extension attacks.

Also worth noting is that on 64 bit architectures SHA-384 and SHA-512 are both faster than SHA-256. So you may in fact get a faster and more secure result by computing SHA-512 and then reducing that output down to 128 bits using another hash.

I do however not know which hash could be recommended for reducing the output from 256/512 bits to 128 bits.


Can we modify any hash function like SHA-1 or MD5 to perform multiple iterations at once to gain calculation speed?

If you would find something like this, it would probably even point to a weakness in the hash function.

Impossiblity in the random oracle model. Hash functions are often assumed to behave like random oracles (i.e., for every new query they return a uniformly random value, while answering consistently for repeated queries). For a random oracle, the output is not defined before querying the random oracle at the input - so in this model it should be relatively easy to argue that it is impossible to find what you are asking for.


decrypt numbers multiplied by a certain floating point number

There is a line between encryption and obfuscation, I would say this is on the latter side.

If someone knows the method, and is able to correctly guess even 1 of the original values, simple math will reveal all the original values. Additionally, depending on the type of data in the field, guessing the floating point number may only take seconds even with no 'plaintext' guess, and you have thousands of values to test it on.

Most encryption is based on some kind of permutation and is reversible, floating point values have a maximum level of precision, and can cause the original value to be lost in some cases. Rounding may be able to recover them, but if the original values also have a certain level of precision, there may be no way to recover them, assuming you are not recovering from a backup, but rather trying to decode in Excel.

Examples
Here is an example of an information disclosure that recovers the key.

Say 2 of the encoded values are $388874698.219672$ and $293536403.581274$. If a strong assumption can be made by the table format or header names that these are relatively small integers, say dollar values, you can multiply the ratio by successive values until you find another value with the same relative rounding error. Lets assume they are prices under $1000:

$R = 388874698.219672/ 293536403.581274$

$R = 1.32479206488609$

Multiply $R$ by an incrementing integer counter and round to 6 decimal places till we get an integer. We can even implement the attack in Excel and visually compare, say on the victim's laptop. Extend the following down 100000 rows:

A1 = ROUND(ROW(A1)*1.32479206488609,6)

Then page down till you see an integer. We run into one at row 19357, with a value of 25644. It can be reasonably assumed these translate to 193.57 and 256.44. A little bit of math recovers the 'key' used hide them, which will probably have rounding errors. Testing this against more values and averaging out some more guesses will narrow down which digits of the key are significant and verify if it is correct. An automated attack will take a fraction of a second, even with much larger values.

Since the ratio of values is preserved when using multiplication, guesses can be made about the nature of the data, and information can be exposed even without knowing the real value. mikeazo's example regarding salary information will expose if someone makes more or less, and by what percentage that difference is.


Is there a reason that the N value in scrypt is limited to powers of two?

The operation:

X[16] & (N-1)

is really, mathematically speaking:
$$ X[16] \mathrm{\ mod\ } N $$
With a generic $N$, this operation must be done with an actual division, which is expensive; some CPU types don't provide it, and for CPU which do provide it (e.g. x86), it is quite slow (for instance, for 32-bit operands on an Intel Core2, division latency is 40 cycles). This would raise the computational cost by a non-negligible amount; correspondingly, it would decrease the memory hardness of scrypt (since, for a given CPU budget, it would be able to do less memory accesses).

However, when $N$ is a power of 2, the modulo can be done with a simple bitwise "AND", which is a matter of a single clock cycle.


Give a CPA-attack on Elgamal when used with $\mathbb{Z}_p^*$

HINT

You already have a hint given in the problem statement:

  $g^{ab}$ is a square with probability $3/4$ with an argument based on the parity of $a,b$.

You should start by making sure you understand why is this the case. Then, once you do that, think about what it means to break DDH: it means distinguishing things that look like $g^c$ for a random $c$ from things of the form $g^{ab}$ for random $a,b$. Given the hint above, can you find a feature that differs between these two?


Can I save space for short messages by using encryption with private key instead of a signature?

In general, no.

First, with an arbitrary public key scheme, the public and private keys might have quite different formats, and there might be no such thing like "encryption with a private key".

For example, with (generic) ElGamal, the public key is a member of the group, the private key is a natural number used as exponent.

With RSA, the public and private keys both consist of the same modulus, and additionally a public or private exponent. (The public exponent is usually something small like $3$ or $2^{16}+1$, while the private exponent is of the same order as the modulus.) The core of an encryption or decryption operation is a modular exponentiation with the (public or private) exponent, and yes, this part is easily swapped around, so you can use a private exponent for something which resembles encryption (and you then can use the decryption operation with the public key to undo it). And as is known, the core of the RSA signature operation is just this exponentiation with the private exponent, while verification uses the exponentiation with the public exponent.

Note that this is not a secure use of encryption, i.e. does not provide confidentiality. Does it provide integrity and authentication?

Real live RSA is not only the core exponentiation operation, but additionally a padding operation, to destroy homomorphic properties. There are several padding schemes, both randomized and deterministic, but these padding schemes are different for signature and encryption, for a reason.

Note also that usually public-key encryption is used in a hybrid scheme: encrypt a random symmetric key using the public key algorithm, then encrypt the actual message using the symmetric key. The resulting message thus will have this format:

[ encrypted key ][ encrypted message ]

The encrypted key has (for RSA) a size same as the modulus (which is the same as a signature), the message itself will have about the size of the plaintext message (maybe also including some padding, and hopefully a MAC). This means you will not save anything compared to the standard signature scheme.

What you actually need is a signature with message recovery, i.e. a signature from which (the unknown part of) the signed message can be extracted.
But this only works (or saves space) for a message which is small enough to fit in the signature (and often a bit smaller due to overhead), so for your 1 KB message you would need an RSA key of similar size. I suppose these schemes are only useful for small messages, like in implicit certificates, where the message is the public key to be certified.


Differential privacy of "randomized responses"

I found the answer in this book  https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf at page 30

  Fix a respondent. A case analysis shows that
  $$Pr[Response = Yes|Truth = Yes] = 3/4$$
  Specifically, when the truth is “Yes” the
  outcome will be “Yes” if the first coin comes up tails (probability
  1/2) or the first and second come up heads (probability 1/4),
  while $$Pr[Response = Yes|Truth = No] = 1/4$$ (first comes up heads and
  second comes up tails; probability 1/4). Applying similar reasoning to
  the case of a “No” answer, we obtain:
  $$
\frac{Pr[Response = Yes|Truth = Yes]}{Pr[Response = Yes|Truth = No]}=
\frac{3/4}{1/4}= \frac{Pr[Response = No|Truth = No]}{ Pr[Response = No|Truth = Yes]} = 3$$


The differences between the attackers in the definitions of IND-ATK and NM-ATK

You say:

  Actually, $A_2$ and $B_2$ are both used to decide which one of two
  messages are encrypted for the challenge.

However, this is not true. The definition of the IND and NM games are different. This difference is summarized in this paragraph from the very same paper [Section 2.3]:

  The goal of the adversary, given a ciphertext y, is not (as with
  indistinguishability) to learn something about its plaintext $x$, but
  only to output a vector $\mathbf y$ of ciphertexts whose decryption $\mathbf x$ is
  “meaningfully related” to $x$, meaning that $R(\mathbf x, x)$ holds for some
  relation $R$.


Does the problem of noise growth exist in the Paillier homomorphic scheme ?

No, it does not.  Unlike Lattice-based schemes, you can do as many homomorphic additions as you want in Paillier (without doing anything like a "reboot"), and it's never a problem.


What is definition of "adversary"? And what do they do?

Formally, an adversary is simply a (probabilistic) algorithm, which we usually assume to run in polynomial time in $n$, the security parameter.
From a more intuitive point of view, an adversary is the model of an attacker on the real life, since every attacker follows an strategy that boils down to an algorithm.

Now, at a high level, a passive attack is an attack where the adversary simply "sees" the information (encrypted data, signatures, etc.) and try to find the secret data from the information gathered. By contrast, in an active attack, the adversary has the ability to "interact" somehow (for instance, by encrypting messages of his choice or even decrypting messages of his choice).

Of course, each one of these notions has its formalization (e.g. Computational indistinguishability, CPA-security, CCA-security).


MOV attack when $E(\mathbb{F}_q)$ is cyclic

For the purposes of the MOV attack you choose $T$ to be a point in $E(\mathbb{F}_{q^k})$.


Well the idea of a cryptographically secure hash function (and often functions within them), is to mimic the Random Oracle model as closely as we can. Now, short of a little gremlin (perhaps?), some perfectly unbiased dice, a magical orb and a magic way to store all the possible outcomes from each input, we need these functions. I'm going to assume you know this and what you're asking is why do we need, "magic"?

Some points worth bearing on the Random Oracle:

The Oracle, would need infinite memory to memorise every query it
ever received (as well as the truly-random reply).
The Oracle is truly random, this is enough of a challenge already.
The Oracle would not only need the infinite memory, previously referenced but eventually infinite power, both ideas, violate some physical constants.
The Oracle ... is already debunked. (it's a useful model but it is magic)

So the next best thing to see is Crypto-Secure-DRBGs. - They and the hash functions based around are at the heart of everything the RO attempts to recreate... apart from we should note, with a computer algorithm anyone with access to the algorithm, can query "the oracle" (this isn't really a problem, though and to expect differently is ludicrous).

  (hash functions are deterministic functions whereas RO is a random
  one, is this the most significant factor?)

Basically, no: the most significant is the first one you mentioned, you can't memorise the outcome of every input, this is a physics issue or a maths issue, either-way, I don't think it needs dragging out.


Determine if encryption is safe against CPA

With multiple blocks the scheme is definitely not CPA as the same plaintext blocks encrypt to the same ciphertext. Using the security game given here as a framework for proving this, begin by letting $m_0 = 0^n0^n1^n$ and $m_1 = 0^n1^n0^n$. Given back a ciphertext $c = Enc_{k1, k2}(m_i)$ (where $i \in \{0, 1\}$) we can look at blocks two and three of $c$ to determine $i$. If the second block of $c$ is equal to the first block then $i = 0$. If the third block of $c$ is equal to the first block then $i = 1$. So the adversary can always correctly determine which plaintext was encrypted.

My thought on one block is that the scheme is CPA, though I don't quite know how to prove it. Assuming that $F$ is a strong PRP we can say that $F(.) \approx U_n$ ($U_n$ being uniform randomness). Given this, we can say that $c \approx k_1 \oplus U_n \approx U_n$. This intuitively indicates to me that encrypting only one block is CPA secure.

I'm not sure how to recover the keys efficiently, given that (if I remember correctly) by definition the probability of efficiently inverting a strong PRP is $< \epsilon(n)$ (aka negligible). That means getting anything back out of $F$ should not be feasible.


Yes, there are several ways in which Mallory could pretend to be Amy.

One obvious way, which doesn't even involve Amy herself in any way, would be for Mallory to perform steps 1 and 2 of the protocol normally, as if he were Amy.  Then, given Betty's nonce $n_b$, Mallory can start a second, parallel instance of the protocol, again pretending to be Amy, and submit $n_b$ as Amy's nonce.  The response from Betty then contains $E(k, n_b)$, which Mallory can send back to Betty to complete the original authentication protocol:

M(A) → B: $n_a$ (= arbitrary nonce chosen by Mallory, pretending to be Amy)
B → M(A): $n_b \;\|\; E(k, n_a)$
Second, parallel session:
1'. M(A) → B: $n_b$
2'. B → M(A): $n_b' \;\|\; E(k, n_b)$
M(A) → B: $E(k, n_b)$

Of course, if Amy is also willing to respond to authentication attempts initiated by Betty (or by Mallory pretending to be her), then Mallory can perform the parallel steps 1' and 2' with Amy instead of Betty.  Thus, even if Betty's smart enough to check whether the nonce she receives in step 1' matches her own earlier nonce (or even if she simply refuses to participate in more than one authentication exchange at a time), she will not be able to detect this version of the attack.

As owlstead suggests, the way to defeat this attack is to disambiguate the encrypted values sent in step 2 and 3, so that the value from step 2 cannot be used by Mallory in step 3.  Some possible ways to do this would be to:

Include a step number in the encrypted strings, e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, 2 \;\|\; n_a)$
A → B: $E(k, 3 \;\|\; n_b)$

Include both nonces in each encrypted strings (in different order), e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, n_a \;\|\; n_b)$
A → B: $E(k, n_b \;\|\; n_a)$

Include the (assumed) identities of the sending and receiving parties in the encrypted strings (NOTE: does not protect against the modified attack where Mallory contacts Amy instead of Betty for steps 1' and 2'), e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, id_b \;\|\; id_a \;\|\; n_a)$
A → B: $E(k, id_a \;\|\; id_b \;\|\; n_b)$

All of the above, e.g.:

A → B: $n_a$
B → A: $n_b \;\|\; E(k, 2 \;\|\; id_a \;\|\; n_a \;\|\; id_b \;\|\; n_b)$
A → B: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$

Personally, I would recommend the last option, if only because it makes the encrypted strings self-documenting: $E(k, 3 \;\|\; id_b \;\|\; n_b \;\|\; id_a \;\|\; n_a)$ can be read as "Amy ($id_a$) authenticating with nonce $n_a$ to Betty ($id_b$) with nonce $n_b$ in step 3", which is exactly what the message is supposed to communicate.

Also, obviously, the encryption method $E$ needs to be non-malleable, and the combining operation $\|$ should not introduce any ambiguity.  In fact, calling $E$ "encryption" is somewhat misleading here: the protocol works fine even if $E(k,m)$ is just a MAC, but has obvious attacks if $E$ is a malleable (but still semantically secure) encryption scheme like CTR mode encryption, as Mallory can simply take $E(k, n_a)$ and turn it into $E(k, n_b)$ by flipping the appropriate bits.

The protocol as described also has other potential issues, depending on how it's used.  For example, if Mallory can insert himself as a middle-man between Amy and Betty, then he can simply relay any messages he receives from Amy to Betty, and vice versa, thereby trivially convincing both that they're talking directly to each other, even though both are actually talking to Mallory.
Fundamentally, without some extra out-of-band information, there's no way to prevent this attack from within the authentication stage of the protocol: as long as Amy and Betty just receive messages from some unspecified network, there's no way for them to tell whose hands they've passed through.

The only solution is for Amy and Betty to encrypt their subsequent communications using the shared key $k$ (or, better yet, an ephemeral session key derived from $k$ and the nonces $n_a$ and $n_b$, and preferably also the identities $id_a$ and $id_b$) with a secure, non-malleable encryption scheme to ensure that, even if Mallory can intercept their messages, he will not be able to decrypt or alter them.  (Of course, the messages should also carry sequence numbers / timestamps and sender / receiver IDs to prevent replay attacks.)


How to test if a number is a primitive root?

For all $m$, if $m$ is a positive integer then

$g$ is a primitive root mod $m$ $\;$ if and only if

$0\leq g< m$ $\:$ and $\:$ $\operatorname{gcd}(\hspace{.015 in}g,\hspace{-0.01 in}m) = 1$ $\:$ and $\;\;$ for all prime factors $q$ of $\phi$$(m)$, $\: g^{(\phi(m))/q} \not\equiv 1 \pmod m$.


It is very likely that in practice this doesn't make much of a difference. I haven't seen any implementations in hardware devices of the more intricate modes (check the FIPS certification pages for info on this). Mostly the CTR mode is used, then the feedback mode. Many HSM's only implement one of the three, making all HSM's nicely incompatible to each other (thanks NIST for not indicating a default, even after being pointed out the problem!).

As indicated in the comments, these KDF's are build upon primitives which should already be protected against side channels. If unsure which primitive to choose, it would make sense to choose the one where the primitive is most resistant. In principle even a copy of bytes to another memory location (write!) can be vulnerable to side channel attacks. However generally speaking the KDF is secure if the underlying primitive is secure. It could be wise to go for a hash function if no hardware acceleration is available for a block cipher, as most hashes seem less vulnerable to side channels in software. On the other hand, the cipher may receive more attention to protect against them - without a specific system there is no strong recommendation can be made.

KDF's build from a PRF (instead of a hash) are relative strong constructions. So it may be that the double pipeline KDF is stronger than the other two, but basically the constructions are strong enough for any purpose anyway, so it makes some sense to choose the one that is easiest to implement. More complexity / a higher learning curve generally leads to a less secure system, after all.

Finally, as indicated, not every system implements all of the KDF's. It might be a good idea to look at the entire domain to see which implementations are available / secure / can be agreed upon with any other participants. Many systems won't have them at all, which again promotes simplicity over complexity. It's better to spend the time testing.


Yes, you can have a key of any length of that range (as long as it is an integral number of bytes), but really, why?  There is absolutely no reason to.

If the key is uniformly distributed, anything over 256 bits is total overkill and completely pointless.
If the key is not uniformly distributed (maybe it's a passphrase or something), you should not be using it directly as the RC4 key.  Instead, you should hash it first (preferably using a slow hash like PBKDF2) and use the result as the RC4 key; and the output of the hash will be something like 128 bits or 256 bits, so again, the range doesn't matter.

Bottom line: If you need to ask about the exact range of key lengths, you're probably using RC4 incorrectly.  Instead, stick to a key that is 128-256 bits long and is uniformly distributed and generated using a cryptographic-quality pseudorandom number generator or using a suitable hash/KDF function.

Update: apparently RC2 does allow arbitrary bit lengths for its keys, per a comment from Henno Brandsma (thanks!).  However, that doesn't change the bottom line.  I would not recommend using unusual length keys.  Stick to ordinary lengths, like 128 bits or 256 bits.


commonly used and proven CPRNG implementation in C

An alternative would be knocking off Microsoft's CryptGenRandom.  That's the old CSPRNG build into the WinNT family of OSes.  Essentially it's SHA1(RC4) and has FIPS certification so should be okay for you.  There's enough detail in On the (in)security of the random number generators of Linux and Windows and Cryptanalysis of the Windows Random Number Generator for you to be able to reconstruct it. SHA1 and RC4 details are everywhere. Do not be alarmed at the bias issues with RC4.  Those occur natively before the hash function is applied.

You will note a valid forward security attack on CryptGenRandom. It only requires $ 2^{32} $ work effort which is quite low and therefore serious.
 However that requires knowledge of the internal state. Whether an attacker can know the internal state of anything is a huge can of worms, and only you can decide if this is a likely scenario.

Whopping great caveat: You need entropy to initialise (and perhaps reseed) your RNG. To be honest this is the hardest part.  Generating cryptographically secure numbers is easy if you just use a library implementation of a CSPRNG. Similarly, a bit of ChaCha is easy, but you still require an initial seeded state.  Seeding is the problem. Since we don't know your electronic environment, my advice can't be specific at this time. Have a look through the two links, try to identify any similarities (particularly related to the state)  and come back with any further questions.


Client authentication on limited hardware

I'd suggest that you clearly define which kind of Bluetooth device you are using, more specifically what its capabilities are with respect to processing power, etc. Another question, can you enter a number on a bluetooth device (e.g., for a PIN-based authentication, for example)? From what you're writing, I'd assume that RSA won't be a plausible solution, since the smallest key length the constrained bluetooth device will have to deal with is 1024 bit (2048 is actually recommended). ECC is likely to prove unsuitable as well, since despite the fact that the key length is much smaller, the device has to be able to deal with ECC algorithm which may be quite inefficient without the proper hardware support of even not supported by the device at all. In my experience, using ECC instead of RSA on Android platform does not necessarily entail a performance gain, see the discussion here.
Another important conceptual question is: what are the security goals/requirements in your specific case and against which attacker the system has to be secure (the so-called attacker model)?
Taking into account what you've written in your question, I would assume that authentication using one-time PIN may be a better option than using full-fledged certificate-based authentication based on RSA (or on ECC).


Do I need to keep a 64-bit version number secret?

For most purposes, you probably don't need to provide confidentiality protection for the version field.

There may be some settings where the version field allow traffic analysis, and to analyze that, we'd need to know so much detailed information about your particular protocol that the question would probably become too localized to be a good fit for this site -- but for most circumstances, you don't need to worry about confidentiality protection.

I do recommend you do apply integrity protection (e.g., the MAC, as shown in your question).  The word "protect", in cryptography, is ambiguous, and it's important to understand that confidentiality protection is not the same as integrity protection.


Are there encryption systems that are both homomorphic and commutative?

$\newcommand{\Enc}{\operatorname{Enc}}$
Actually, Pohlig-Hellman exhibits a homomorphism and commutativity.

For the commutativity, see poncho's answer on your other question.

The homomorphism goes as follows
(it is really just plain multiplication, not unlike what is possible with textbook RSA):
$$\Enc(m_1)\cdot\Enc(m_2)=m_1^a\cdot m_2^a=(m_1m_2)^a=\Enc(m_1m_2)\pmod p$$


Conditional probability with Vigenere Cipher given specific plaintexts and key sizes

The answer to this (thanks to help from fkraiem) was literally included in the first sentence of the question.

I went wrong by assuming that the probability of the occurrence of a 1 or 2 character key didn't weigh into the calculation. My (rather questionable) reasoning was that since the key did in fact have to be either 1 character or 2 characters (i.e. it couldn't be 0 or 3 or more characters), that the 50% probability didn't weigh into it. Yes, that reasoning is in fact both as silly and as incorrect as it sounds.

So, the corrected components of the calculations above are:

  Therefore:

  Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 x 0.5 + 1/(26^2) x 0.5] x 0.2
  Pr[C=ff | M=de] x Pr[M=de] = [0 x 0.5 + 1/(26^2) x 0.5] x 0.8

  Ergo:

  Pr[C=ff] = [1/26 + 1/(26^2)] x 0.5 x 0.2 + [0 + 1/(26^2)] x 0.5 x 0.8
  Pr[C=ff] = 0.004585799


I think guessing key bits and checking if the plaintext is valid in both words is the way to go (much like a binary puzzle).

For instance, it is clear that at least one of the words starts with an A because if you take the first 4 bits they are all different except for the last one. That rules out BB, BC, CB or CC as combinations of the first letter, because they don't differ by 3 bits where the final bit is 1. Similarly you should be able to rule out two other combinations, leaving only one combination - unfortunately you don't know yet if it is AX or XA. Similarly, you expect an AA and B combination at the final bits as the bits must be each other complements.

I would implement this using left to right guessing of key bits with backtracking in case the pattern becomes impossible for either W1 or W2. You may even start at each end, but I don't think that is needed. You should be able to do this by hand, but programming it may be fun as well.

In the end I see 13 bits set to 0 and 13 bits set to 1, and I had to backtrack 18 times to find a solution (assuming bits set to 0 before possibly back tracking, simply working from left to right), which is entirely doable for a mere human. Of course giving the key, the pattern of W1 or W2 gives away the entire result, so I won't do that.

The complement of the found key is also a solution in this particular case.

High level design:

create a tree for the key;
create code to perform a breath first search of the key bits;
create a method to check if a given (partial key) could be valid;

create a method that creates a tree of patterns;
check for W1 and W2 - up to the key size - if the key produces a tree up  to a leaf node;
to do this you can search the tree using depth first search;

create checks to see:

if the key is complete;
if there can be a partial match at the end;

Beware to check the end conditions correctly, or you may have to do some manual restructuring at the end.

This is not an easy task to program. Basically you need to create a tree for both the key as well as the resulting plaintext to perform the pattern matching.


Can you help me understand this exam answer related to “breaking discrete logarithm over P256”?

I hope I interpreted this correctly, as both the question here and the pdf are not completely clear to me. As the question seems to do, I will everywhere assume that the chosen walks are completely random.

The idea is that we are going to run the ${\tt Dlog}$ function, and we want to know the expected value of the number of times we have to iterate its loop. Suppose we start a loop, and we have chosen points $P_0,\ldots,P_{\ell-1}$. Three things can happen:

We have seen the point $P_{\ell-1}$ before.
We have not seen the point $P_{\ell-1}$ before, and the point is distinguished.
We have not seen the point $P_{\ell-1}$ before, and it is not distinguished.

This is an exhaustive list of options. Now let's suppose that if we are in 3, that we choose $P_{\ell}$ and continue the loop. Then after a while we are going to end up either in 1 or 2. This shows that every loop either ends up on a point which we have seen before (let's call this event $X$), or ends up on a point which we have not seen before, and the point is distinguished (let's call this event $Y$).

Estimating some probabilities:

Let's call $\mathcal{P}(X)=x$ and $\mathcal{P}(Y)=y$. Since these two options are exhaustive, we have $$x+y=1.$$
Since by assumption we visited at least $k\frac{n}{t}$ points, we have
$$x\geq \frac{1}{n}\cdot k\frac{n}{t}=k\frac{1}{t}.$$
Moreover, suppose we visited $v$ points, then
$$y=\frac{n-v}{n}\frac{1}{t}\leq\frac{1}{t}.$$
Combining the last two equalities, we conclude that $x\geq k\frac{1}{t}\geq ky$. Writing $x=1-y$, from this it follows that $1-y\geq ky$, and therefore that $y\leq\frac{1}{k+1}$. Thus $-y\geq\frac{-1}{k+1}$. From this we we have that
$$x=1-y\geq1-\frac{1}{k+1}=\frac{k}{k+1}.$$
Finally we conclude that $$\frac{1}{x}\leq \frac{k+1}{k}=1+\frac{1}{k}.$$

The final argument:

So why did we do all of this. Well, we have defined a "successful" event, namely $X$, and an "unsuccessful" event, namely $Y$. How many times do we have to repeat before we end up in $X$? This is a standard geometric distribution with probability $x$. It has expected value
$$\sum_{i=1}^{\infty}\left(i\cdot xy^{i-1}\right),$$
which is known to equal $\frac{1}{x}$. As $\frac{1}{x}\leq 1+\frac{1}{k}$, we are done.


Frequency Analysis on DES, AES, 3DES using Cryptool2

My question is - when performing frequency analysis on such ciphers, do I input the hex ciphertext or do I need to transform it into text? How can I comment on that (based on letter frequency or bit occurrence)?

First of all, what you are looking at is a hexadecimal representation of the ciphertext. The ciphertext itself does not consist of hexadecimals, it is binary. Converting it to text makes very little sense; if any analysis has to be done it has to be performed over the binary data without any conversion to text.
We know that DES and AES are permutations over block sizes of 8 or 16 bytes. What you are showing is a DES or AES using mode of operation. Analysis should only be performed on the combination of the two. And you can actually find e.g. duplicate blocks when DES or AES is used in ECB mode. In any correctly used secure cipher mode they should of course be secure, and indistinguishable from random (IND-CCA/IND-CPA).
It doesn't make much sense to use the general frequency analysis over the cipher as the output does not even consist of characters. Generally analysis should not be performed willy-nilly; it is performed while keeping the characteristics of the cipher under investigation in mind. And this kind of leads to the answer...


CTR mode was previously considered a relatively brittle scheme, and in a sense it is. Repeating the nonce will repeat the counter, and repeating the counter will repeat the key stream. This means that the security of the plaintext is broken rather spectacularly on nonce reuse.

However, using CTR has many advantages over CBC:

You can use a nonce instead of a randomized IV (deterministic vs random);
You don't need to bother with padding or ciphertext stealing (no expansion of ciphertext above plaintext size);
Because of above it is not vulnerable against padding oracle attacks (decryption before verification is not vulnerable);
You only need to use the block cipher in one direction (simplification of the encryption scheme, less hardware required);
Online encryption/decryption is perfectly possible (immediate encryption / decryption without caching);
Ciphertext streams may be cached for efficient, byte oriented encryption / decryption (low latency);
As the counter values can be generated in advance, pipelined AES implementations may offer (much) higher performance - see the comment from Yehuda for a description (speed).

So nowadays about every AEAD cipher uses CTR mode underneath. And that's fine, as long as you do indeed provide it with a nonce.

The fact that you can also search within the ciphertext (skip to a specific offset) is of little interest for AEAD ciphers as you would generally not use the data without first verifying the authentication tag. So although it is an advantage of CTR mode, it doesn't make much of a difference within an AEAD cipher such as CCM.

One problem with CTR is that the construction of the counter itself isn't well specified (location of the IV, additional data, etc.). But within an AEAD cipher this is not an issue as the AEAD algorithm itself will specify the precise construction of the counter.

The question is more why the archaic CBC mode is still used that much. It's not as brittle as CTR mode when it comes to the IV, but that comes at a very high price, including additional requirements for that same IV.

Also note that the use of a CBC mode together with a CBC based MAC may not be such a good idea if the same key is used for both; it is easy to introduce conflicts between the two, threatening the security of a scheme providing both confidentiality and integrity of messages.


Can padding length, and thus plaintext length, be considered public information when using aes-cbc?

For AES CBC i would suggest you stick to the standards.

The PKCS7 padding scheme is pretty easy to implement and has been tested extensively now that its been out in the public for a while. I had implemented PKCS7 padding for my AES CBC cipher a few weeks ago and you can see the code here if it helps.

Note that hashing by itself does not provide you with authentication, you will need a MAC (Message Authentication Code) for that. If you like using the SHA family, you can use something like HMAC-SHA256.

Is there any particular reason why you wish to use hashed data as a pad? If you are looking for authenticated encryption, you should stick to the standards like GCM for AES.


Why does the authenticated cipher CCM encrypt the MAC too?

Let $M_k$ be CBC-MAC under the key $k$: for blocks $b_1, b_2, \dots, b_\ell$, $$M_k(b_1 \mathbin\| b_2 \mathbin\| \cdots \mathbin\| b_\ell) = E_k(\cdots E_k(E_k(b_1) \oplus b_2) \cdots \oplus b_\ell).$$

The message $m = m_1 \mathbin\| m_2$ collides with the message $m' = M_k(m_1) \oplus m_2$ under $M_k$, since

\begin{align}
  M_k(m_1) &= E_k(m_1), \\
  M_k(m_1 \mathbin\| m_2) &= E_k(E_k(m_1) \oplus m_2), \\
  M_k(M_k(m_1) \oplus m_2)
   &= M_k(E_k(m_1) \oplus m_2)
    = E_k(E_k(m_1) \oplus m_2).
\end{align}

If the CCM ciphertext for $m_1$ revealed $M_k(m_1)$, then an adversary could use that and the CCM ciphertext for $m$ to forge the CCM ciphertext for $m'$ since the CTR encryption preserves $\oplus$.  To thwart this, CCM encrypts the authentication tag too, with an additional block in the one-time pad generated by CTR.


Verifying EdDSA signatures using xedDSA verify function.

From your link:

  XEd25519 signatures are valid Ed25519 signatures and vice versa, provided the public keys are converted with the birational map.

Unfortunately, the vice-versa is wrong.

XEd25519 works by requiring the private key to be positive in the sense that it will produce a positive edwards public key.
This is obtained by negating the private key if it produces a public key with negative $x$. (negative and positive in the sense of LSB as in ed25519)

This is assumed to hold in verification but it doesn't if the signature was generated with ed25519.

More specifically, in ed25519 you can have both positive and negative public keys $A$. Then your signature is computed as: $R = rB, s = r + ha$
Note that in ed25519 you have that $A = aB$.
Verification is done by verifying that $R = sB - hA$.

In ed25519 this works because $R = rB = (r + ha)B - h(aB)$.

However, when using XEd25519 things changes as the public key are implicitly assumed to be positive (curve25519 lacks the sign information so some assumption should be made), so you would have end up with a sign bit flip in the verification equation: $rB \neq (r + ha)B - h*(-A)$.

So you could verify in this way only signatures made by an ed25519 key pair with a positive public key.

Fixes:
I think that you could probably be ok in testing $R = (r + ha)B \pm hA$ which will hold in one of two cases if the signature is valid, but I guess that would be a problem when your implementation uses a double base scalar multiplication which is pretty common for signature verification.
A better idea would be to replace XEd25519 with qDSA which is a more natural way to do signatures over Montgomery curves


How does the energy consumption of the SHA-3 finalists compare?

I found the answer in the paper "Comparison of the Power Consumption of the 2nd Round SHA-3 Candidates" (PDF version) by Benedikt Westermann, Danilo Gligoroski, and Svein Knapskog, published at the ICT Innovations 2010 Conference.


How can I accomplish Key Derivation in JavaScript?

Okay, for key derivation in the browser you will be using third party libs.

If you want to be the absolute top of the line then scrypt (potential lib to consider) is your best bet with a medium to high work factor based on what your users are going to be using. Bcrypt works but is not memory hard so take that into consideration. (Even 5MB of memory usage could severely impede the usage of custom hardware to attack your keys)

A salt can be derived from the crypto.getRandomValues which takes a typed array and returns it filled with trustworthy random data.


Is key derivation of a token shared secret necessary for usage of token in TOTP as specified by RF6238?

No, you do not have to do any key derivation. The shared secret is just an arbitrary byte string which is used to key the HMAC function.


how to use AES block cypher when there are only 47 byte space?

This is what a block cipher mode of operation is for:

  ...  A block cipher by itself is only suitable for the secure cryptographic transformation (encryption or decryption) of one fixed-length group of bits called a block.2 A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.[3][4][5]

You might consider:

Using an authenticated mode of operation such as GCM
Offload all the work to an existing library for whatever your purpose is (PGP for data at rest or TLS for data in transit), which will handle all of these details for you.


As @mikeazo correctly states, I don't think there is any formal or precise definition for the term "scheme".  It is probably used loosely in a way that might well mean a "protocol", "mode of operation", "cryptosystem", "cryptographic algorithm", or even something else entirely.


Format Preserving Encryption after compression algorithm?

I have been reading about format preserving encryption and would like to use it.

There are many good reasons for using FPE, but this is certainly not one of them.

It's OK to get excited about a solution but you should not apply that solution regardless if it fits the problem.

This reminds me of a developer I knew that wanted to use each and every pattern he encountered. Pattern driven development: "we have this programming pattern, now which problem do we need fixing?"

  I would like to know if its a good idea to use FPE after compression or would that even make sense.

No, it doesn't make sense. Compression generally compressed to bytes, and bytes can be encrypted fine. FPE is mainly used where there is no easy byte or bit conversion possible, e.g. when the output needs to be a number or a specific range or characters. The most common example is the format of credit card numbers.

Besides that, FPE may add quite a bit of overhead; you certainly don't want to process 100s of GB of data with it.


Is there a theorem to determine the elliptic curve parameters based on the group order?

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, cryptographers do not like special cases and prefer the immunity of the herd by relying on random values in big sets (unless there is a performance advantage to be had with the special structure, in which case to Hell with it, let's milk the precious clock cycles -- that's how modern curves tend to be defined in fields of prime order $2^m-c$ with a very small $c$).

CM has been used to define pairing-friendly curves (curves that have a demonstrated special structure which is on the verge of being a weakness, but also enables nifty three-way protocols).


Given only RSA public key parameters, what security issues might I be able to detect?

The tests you can do depend on how much time you want to spend for checking each certificate and the "stupidity" you assume for the given key-owner.

You already mentioned the basic checks:

Modulus is too small, only interesting if it's smaller than 1024 bits
Exponent is unusual, not exactly a vulnerability in most cases

The following attacks may take more or less time but applying each of them will give you high assurances that the parameters are indeed not vulnerable. This can be read as a list of techniques for factoring given moduli.

The following techniques are rather fast and may be applied to each modulus.

Check for GCD > 1 with a given database. For example get a database of many certificates and apply the GCD algorithm to each pair, if the GCD is larger than 1 you've found a non-trivial factor.
Check for the Debian RNG vulnerability. Although the vulnerability is quite old you might get "lucky" and find a vulnerable key.
Check if the modulus is a perfect power. This is highly unlikely but can be verified extremely fast, as proposed by Ricky Demer in the comments.
Check if the modulus is a prime, for example using the Miller-Rabin test. If it is a prime it's obviously an invalid modulus, making it possible although unlikely.
Check if $|p-q|$ is small. If so the Fermat factoring (or more advanced version) will quickly factor the modulus. This is highly unlikely as well.

The last few techniques are rather slow and may not be applicable in the given setting due to time constraints.

If you suspect the modulus to contain a few large (128-bit) primes you can try and apply the elliptic curve method. This is rather unusual for RSA moduli.
If you suspect that the modulus isn't composed of safe primes you may want to give Pollard's p-1 and Williams p+1 algorithm a try.
If you suspect the private exponent to be small you can try to apply Wiener's attack.


Standard symbol / notation for "x knows y", or the inverse

The notation is "", i.e., the empty string. $\;\;$ Since $k$ is not an input of $f$, $f$ has no knowledge of $k$.


Reproducing RSA GCD attack (common factor) - real world certificates

There are multiple steps you'll need to reproduce the attack done by different teams in 2012:

Firstly, you effectively need to grab the data you'll need consecutively. You might take the X.509 certs proposed by third parties, such as scans.io or the SSL Observatory; or grab it yourself directly as explained by Pedro (although I guess it might be easier to use specialized fingerprinting tools to pull them quickly instead of a script relying on OpenSSL).
Secondly, you need to extract the interesting data out of the certificate, this shouldn't be too hard, just make sure you can link the data back to where it came from. What you need to find is just the modulus used in each certificate and collect those in a big database.
Finally you need to perform batch GCD on the huge list of modulus you've extracted from those certs... That is probably the hardest part, I don't know if there exists distributed algorithms to perform it easily without having tons of RAM under the hand...

Now since you seem especially interested by how you could perform 1., you might also want to pull out all of the SSH keys you can find on the web, since most of them will also be RSA keys, as well as PGP keys (which was also done in one of the papers).
I've also once read a blog about doing this on Github's user SSH keys as well, but this would take months to perform, since Github has strict rules regarding its API and requests' rate.

Finally another team has built a key analyzer using the same methods to test your key against millions of other keys (and allowing them to build a bigger database at the same time, obviously): https://keytester.cryptosense.com/


What is the difference between Poly-LWE and Ring-LWE?

One main difference is that in Ring-LWE, the ring $R$ is the full ring of integers $\mathcal{O}_K$ of a number field $K$, whereas in Poly-LWE it is of the form $R=\mathbb{Z}[x]/f(x)$ for some irreducible $f(x)$; this ring is (isomorphic to) an order of the number field $K=\mathbb{Q}(x)/f(x)$, but may not be the full ring of integers.
Another important difference is that in Ring-LWE, the (non-noisy) products $a_i \cdot s \in R^\vee_q$ belong to the dual (fractional) ideal $R^\vee$ of the ring (modulo $q$), whereas in Poly-LWE, all of $a_i, s, a_i \cdot s$ belong to $R_q$. While the latter is technically simpler, there are several advantages that come with using the dual form.
A third important difference is that in Ring-LWE we usually consider error distributions which are essentially spherical in the canonical embedding, whereas in Poly-LWE we usually consider error polynomials whose coefficients are independent small values (e.g., Gaussians)—such error polynomials may be quite “skewed” in the canonical embedding. Again, the latter choice looks technically simpler at first, but in crypto applications there are advantages to the former (especially in conjunction with the “dual” form of Ring-LWE), relating to more tightly controlling the errors as they accumulate.
The two problems can be formally related, up to some blowup and distortion in the error distribution. See https://eprint.iacr.org/2019/878 for the latest information.


Thanks to Richie Frame pointing out this is basically a duplicate of question
Bouncy jdk 1.51 Serpent KAT tests vs Nessie vectors
I discovered the NESSIE writes their key, plaintext, and ciphertext test vectors for Serpent in reversed byte-order (but it's not little endian inside the bytes).  So, on Biham's site,
https://www.cs.technion.ac.il/~biham/Reports/Serpent/Serpent-256-128.verified.test-vectors
, the first test vector,

key=8000000000000000000000000000000000000000000000000000000000000000
plain=00000000000000000000000000000000
cipher=A223AA1288463C0E2BE38EBD825616C0

only works if I use my implementation in reverse byte order; that is, I have to input the key:0000000000000000000000000000000000000000000000000000000000000080,
and I get the above ciphertext in reverse byte order:
cipher:  c0165682bd8ee32b0e3c468812aa23a2
Verifying this with set 3, vector 130:
key= 8282828282828282828282828282828282828282828282828282828282828282
plaintext = 82828282828282828282828282828282
ciphertext= AAA92B00896FE228BDF5AA3BA534CA44
Since the key and plaintext are reversible by byte order, I can put this key and plaintext in and expect the ciphertext in reverse byte order.  My implementation yields:
44ca34a53baaf5bd28e26f89002ba9aa.
This checks out!


Finding Private key in RSA with public key, cipher text and plain text

No, there is no known efficient method to find an RSA private key from public key, ciphertext and plaintext, including when no padding is used and $e=3$. The best known method is factoring the public modulus, which then trivially allows to find a working private key. Factoring is considered brute force, or tantamount to that. The best known factoring method for a public modulus of cryptographic interest in RSA is GNFS.

We can prove the assertion in the first two sentences, modified by adding that the ciphertext was not chosen by an adversary, and that the hypothetical method works including for small public exponents $e$. The idea is that any such method could be turned into a factorization algorithm for any $N$ suitable as RSA key: we chose a small odd $e$, which with fair odds is coprime with $\varphi(N)$; we choose some plaintext, and compute ciphertext by whatever method is normaly used in the RSA variant considered; we can now apply our hypothetical efficient method that finds a private exponent $d$; we compute $f=d\cdot e$, which is such that $f\bmod(p-1)=1$ for any prime $p$ dividing $N$, and that's enough to efficiently factor $N$ (see this answer).


How many bits of entropy does an elliptic curve key of length n provide?

Bits of entropy

The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy.  If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy.  This is the same for all types of cryptographic systems.  It is also why in cases where the key is derived from a password while it may be impossible to brute force the key it is possible to brute force the significantly weaker password.

Bit strength

An ECC key has a bit strength equal to half the key length.  To understand why we need to take a step back and look at what makes ECC strong.  By strong we mean that it is computationally difficult to derive the private key from the public key.  Why is that difficult?  Well the short version is that to go from public key to private key would require solving a discrete logarithm and no efficient solution is known.  This is a mathematical assumption on which ECC is based.

So why is the bit strength equal to half the key length?  It is because all of the fastest solutions for solving a discrete logarithm problem are on the order of $O(2^{n/2})$.  So for a 256 bit key we are talking about $2^{128}$ operations which is the same as an exhaustive search on a 128 bit symmetric key thus it is 128 bit strength.

Key length does not equal bit strength

The ratio between key length and bit strength will vary by algorithm.  For unbroken symmetric algorithms there is no solution short of an exhaustive search of possible keys to find the proper key thus a 128 bit AES key has 128 bit strength.  However for asymmetric encryption there are faster solutions and as a result it takes a larger key to achieve a similar level of security but that ratio will depend on the algorithm used and the fastest known solution.

$$\begin{array} {r r r}
AES\ 128\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
ECC\ 256\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
RSA\ 2,048\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
\end{array}$$

$$\begin{array} {r r r}
AES\ 256\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
ECC\ 512\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
RSA\ 15,360\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
\end{array}$$

Now if tomorrow someone found a faster solution to solve the discrete logarithm problem, let say $O(2^{n/4})$ then a 512 bit ECC key would no longer be 256 bit security it would be 128 bit security.  I think that is unlikely but I use it as an example to illustrate why keys of different algorithms have different lengths for the same level of security.


RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$?

Both questions can be answered using the same kind of argument.

First, observe that in both cases we are really only interested in the number of $e$th roots of unity in $\mathbb Z/n$: Any $e$th root of unity can be multiplied to some $M$ without changing the value of $M^e\bmod n$, and two different $M$ with equal $M^e\bmod n$ differ by an $e$th root of unity. Thus we restrict our attention to the case $M=1$.

For succinctness, I will sometimes write only root for "$e$th root of unity".

The Chinese remainder theorem gives an isomorphism of rings
$$
  \pi\colon\; \mathbb Z/n \cong \mathbb Z/p \times \mathbb Z/q
  \text.
$$

The image of $x^e\bmod n$ under $\varphi$ is $(x^e\bmod p,x^e\bmod q)$.
Some element $x\in\mathbb Z/n$ is a root if and only if both components of $\varphi(x)$ are roots in $\mathbb Z/p$ and $\mathbb Z/q$.
In other words: Each root in $\mathbb Z/n$ "consists" of roots in $\mathbb Z/p$ and $\mathbb Z/q$, and vice-versa.
Thus, if $\mathbb Z/p$ has $a$ roots and $\mathbb Z/q$ has $b$, the ring $\mathbb Z/n$ has $ab$ roots.

Now note that the order of the cyclic group $(\mathbb Z/p)^\ast$ is $p-1$, thus if $e$ divides $p-1$, there must be an element $r$ of multiplicative order $e$ in $\mathbb Z/p$. Its powers $r^1,r^2,\dots,r^{e-1}$ are nontrivial $e$th roots of unity in $\mathbb Z/p$, thus (including $1$) there are $e$ roots in $\mathbb Z/p$.
There cannot be more than $e$ roots since $\mathbb Z/p$ is a field.
Of course, the same holds for $q$.

Armed with that knowledge, let's tackle question 1: If $e$ divides both $p-1$ and $q-1$, there must exist $e$ different roots in both $\mathbb Z/p$ and $\mathbb Z/q$. Thus, by the above, there are $e^2$ different $e$th roots of unity in $\mathbb Z/n$.

As to question 2: Since $(\mathbb Z/q)^\ast$ has order $q-1$ and $\gcd(e,q-1)=1$, the map $x\mapsto x^e\bmod q$ is a permutation on $\mathbb Z/q$. In particular, there are no nontrivial $e$th roots of unity in $\mathbb Z/q$.
Concerning $\mathbb Z/p$, note that the map $x\mapsto x^{e/a}\bmod p$ is a permutation since $e/a$ is coprime to $p-1$. Thus, $1=x^e=(x^a)^{e/a}$ in $\mathbb Z/p$ if and only if $x^a=1$. As $a\mid p-1$, we can apply the above results (with $a$ in place of $e$) to conclude that $\mathbb Z/p$ has $a$ roots, thus $\mathbb Z/n$ has $a\cdot 1=a$.


No, there are expressions relating input values which demonstrate extremely strong correlations between output bits. The output bits of of MD5 are not independent, particularly if the party supplying the input to MD5 chooses for them not to be.

These correlations are sufficiently powerful to enable the generation of completely identical output values rapidly on ordinary desktop systems. This would otherwise require a challenging amount of work (2^64), were MD5 an ideal random function.

Consider this visualization of an MD5 collision. Observe that even towards the end of the computation, near the output, the differences (red and green colors) have been largely confined to long vertical columns (which correspond directly to the output bits). Even after just one input block, a change to 3 input bits results in no change at all in 125/128 output bits rather than the 64/128 that would be expected by chance alone.


I ... was wondering if it was necessary to sign the ciphertext

No, there is no need to sign the ciphertext. The secret key is already derived by the key agreement protocol, and that is secure because you verified the parameters (which, I presume, includes the ephemeral public key of each party).

At this point you just have to verify that each party does indeed have the same shared secret. One way to do this is to verify a GCM encrypted message.

The problems with that are that:

you need to send a message (which could take some time after you've agreed upon a key) and
you're now mixing up entity authentication and message authentication.

Part 2 is a major pain in the back for developers and maintainers as they will have to mix concepts. For instance, what will you log if the first message fails? Was it data corruption for the - often much larger - authenticated message or was it a failure to establish the session in the first place?

So you're probably better off sending a MAC specific to entity authentication to the other party as soon as the shared secret is established, preferably using a different derived authentication key. You can use a KDF to e.g. establish an authentication key and message encryption key for that purpose.

The first MAC can be send with the ephemeral public key that is exchanged last; at that point one party already has the other party's public key and can establish the shared secret after all. Unfortunately it may cost you an additional message if the other party needs to be authenticated quickly. Of course there are solutions to that as well, but yeah...

  How can I introduce forward secrecy?

If you used ephemeral (EC)DH key pairs for both parties to establish the session keys then you already have obtained forward secrecy. Of course this assumes that you destroy the ephemeral private keys asap after establishing the session keys.

Note that sessions are not immune to attack where the private keys are found e.g. by quantum computers in the future. Forward secrecy is not a panacea (which is why I generally stick with "forward secrecy" rather than "perfect forward secrecy" even though the "perfect" part isn't related to breaking the key agreement algorithm).


Can private key be specified on key pair creation?

You can use Elliptic Curve cryptography. Here the private key is a vector $d$ ($s$ is also used sometimes) and the public key $w$ is calculated using $(x_w, y_w) = d \cdot G$ where $G$ is the base point (part of the domain parameters) of the elliptic curve.

To generate the key from the master secret you can just use $K_O = \operatorname{KDF}(K_I, C, L) \mod N$ where the input keying material $K_I$ is set to the masterkey and the Context or OtherInfo $C$ is set to the pair ID. Finally $L$ is the output size in bits, it should just be set to the number of bits in the curve so that the output key material $K_O$ will have the correct size. HKDF-expand would be a KDF that is a good fit for performing the key derivation.

The one thing missing is that you should convert the output to a value between $0$ and $N$ with $N$ the order of the curve. There is a description on how to do this in NIST SP-800-90 Arev1, appendix A 5.3 (the simple modular method). For most curves simply performing $d = K_O \bmod N$ should also return a private key that is random enough (what I would call the simplest modular method) but beware of attacks against certain schemes, sometimes it is worth to go the extra mile.

Note that there is a drawback to creating key pairs this way: the $\operatorname{Gen}$ function is often designed to use a random number generator, not a static value. The generation of private keys may also change between implementations (e.g. big / little endian machines, functions to test the random number generator etc.). So you need low level access to the private and public key generation functions (or just to the point multiplication function, of course).

It would not be too hard to extend this answer to include e.g. keys for schemes based on the Discrete Logarithm problem (i.e. Diffie-Hellman). RSA has a complex key generation function that you probably do not want to use for this.