$\text{modBits}$ is the length of RSA modulus $n$ for example if you have 17 as RSA modulus than it has $\texttt{10001}$ as base two representation and has $\text{modBits} = 5$
If you generate a modulus $n$ which is 2048-bit than the $\text{modBits} = 2048$. Keep in mind that, we say a number $n$ is 2048-bit when it is between $2^{2047} \leq n \leq 2^{2048}-1$

  lets say n = 10 decimal = 1010 binary
  then modBits = 4?

Yes 4.

  in my 2048 RSA key PEM file n uses 257 bytes
  then modBits = 257 *8 ?

The leading 00 is coming from ASN.1 encoding of integers. Therefore you have 256-byte key.

  which one is the value of modBits?

8*256


Key distribution protocols, PKIs, document authentication, general authentication and/or identification protocols, times tamping protocols...


Advantages of a TLS handshake over pre-shared public keys

What are the advantages of a TLS handshake compared to pre-shared
  public keys?

Actually TLS supports raw public keys, so you could actually do what you just described with TLS. Now what it would gain you, for starters, is the fact that you get a protocol which has seen a lot of analysis, which has security reductions, which has some very good implementations and for which  you can somewhat easily / more cheaply buy good security review / consultation on the concrete implementation.

  transfers it, the AES-encrypted data and an AES-encrypted MAC

For example, TLS doesn't do this (in the handshake), because this is known as MAC-then-Encrypt, which is highly discouraged and has lead to attacks on sloppy implementations in the past. Also TLS has eg measures to prevent replay attacks, ie an attacker just sending your device the same handshake and the same record data again as in a previous session.

Beyond that you don't have to use the full flexibility of TLS. You can just turn off and strip away the code for anything but TLS 1.2 and eg ECDHE with RSA and GCM. This will also have the benefit that you can just use a known-good library and don't have to roll your own protocol and thus save dev-time, nerves and benefit from standardization.


Yes, that is sufficient.

I realise this isn't the most helpful of answers, but I'm not quite sure how we're supposed to deal with questions that lend themselves so neatly to one word answers. Certainly it seems wrong that something that has been solved should continue to sit in the 'unanswered questions' column!


Your scheme is indeed an instance of output feedback mode (OFB), using
$$(\mathit{key},\mathit{pad}) \mapsto H(\mathit{key}\oplus\mathit{pad})\text,$$
where $\mathit{key}$ corresponds to keyhash and $\mathit{pad}$ to hash, as the "block cipher". (It is very likely not really a block cipher due to lack of bijectivity, but that's not needed for output feedback mode.) When $H$ is a cryptographically  secure hash function, the construction should have the same security properties as OFB using a "real" block cipher; however, since hash functions are usually slower than block ciphers, one generally prefers to use the latter.


What role does RSA play in DHE_RSA cipher suite?

Ephemeral Diffie-Hellman (DHE or ECDHE) uses two ephemeral key pairs that should be discarded after use. However, to establish a secure connection it is required that you know the entity that you establish the connection with. If that isn't the case then an impersonation or man-in-the-middle attack is possible.

So RSA in this case points to the key pair of the server, the public key of which is in the server certificate. This certificate is used to establish a chain to a trusted (root) certificate in the certificate store, e.g. the one in your browser or system store. This chain is verified and validated so that the public key of the server can be trusted to a certain degree (the level of trust established by trusting all of the CA's in the certificate store is an ongoing debate).

Now that you've established trust in the public key the private key of the server can be used for two related goals:

entity authentication of the server and
making sure that the ephemeral public keys and parameters have indeed been generated by the client and server.

The RSA algorithm is used for the private key calculation at the server to sign the messages used to perform the key agreement to agree on the master secret. This master secret in turn is used to derive the session keys used to encrypt the data streams. The client uses the RSA algorithm for the verification of the public keys, parameters and to make sure that the server controls the private key used for the signature generation (server entity authentication).

The advantage of directly encrypting the master secret (in the old RSA_ cipher suites) is that it establishes the master secret and performs the entity authentication in one single operation. Fortunately DH and certainly ECDH is relatively fast compared to RSA private key operations.

Notes:

obviously the certificate needs to have an RSA public key, so ECDSA certificates cannot be used by the server;
the client is not authenticated by default - to authenticate the client it is required for the server to explicitly request client authentication, this is why you need to login on most websites (or authenticate yourself when paying, of course);
the certificates themselves may be signed by a different algorithm than RSA, and if client certificates are used then they may use a different algorithm as well.


Is there an algorithm to derive a 1-of-N shared secret from a set of N private keys?

I'll start this thread off with a not-very-satisfying solution. If we let $D$ be as long as all the $k_i$ put together (i.e. $|D|=N |k_1|$), then we can solve this using Shamir's Secret Sharing (SSS).

First, choose any $S$ we want. (As you can see, this problem is now under-constrained.)

Use $1$-of-$N$ SSS to derive keys $r_1,\ldots,r_N$, any one of which is sufficient to recover $S$.

Then define $$d_i := r_i - k_i$$ (that is, the difference between the $i$-th SSS key and our $i$-th input key).

Finally, let $$D := d_1 \| \cdots \| d_N$$

Now we can use any single $k_i$, together with $D$, to recover one of the $1$-of-$N$ SSS keys, which gets us $S$.

So I've established an upper bound on the length of $D$. Can anyone do better?


How to actually compute the statistical distance?

Prove your method correct.
Factor your code into a nondeterministic uniform bit sampler and deterministic logic.

You can use the full suite of standard software testing techniques for to test deterministic part.
You can use automated formal verification tools to prove the deterministic part is correctly implemented.
You can use well-studied cryptography—also with deterministic known-answer test vectors—seeded by observations from well-studied unpredictable physical models for the uniform bit sampler.

‘OK,’ you say, ‘but Shirley, you should be able to also use empirical hypothesis tests of random samples—after all, the goal is to test that a random sampler for a distribution is correct, so why not run it and apply a standard empirical hypothesis test of distribution to the samples?  Specifically, we can consider the null hypothesis that the software correctly samples from the intended distribution, and apply a hypothesis test with a specified statistical significance level for that null hypothesis!’

This is not wrong.  But there are several issues with it.

Empirical hypothesis tests of distributions are qualitatively different from the normal kinds of automatic tests you might be familiar with in software engineering, because they necessarily have false alarms:

A test for deterministic software properties rejects certain samples, because correct software cannot yield them—thus it is a bug if you encounter them.
A random test for the distribution of a null hypothesis rejects certain samples, even though correct software can yield them—the conceit, of course, is that buggy software will yield these rejected samples with much higher probability than correct software.

What do you do, then, when your test suite rejects the null hypothesis and raises an alarm?  Well, it might be a bug, or it might just be a fluke!  Better run it repeatedly to make sure that the rate of alarms is exactly what the significance level was set to—so maybe we should run a hypothesis test for the null hypothesis of iid Bernoulli trials weighted by the significance level, but what do you do if that test fails?  Well, it might be a bug, or it might just be a fluke…
For these empirical tests to be useful, they need high statistical power to detect the bugs that might be in your program.  So you need to hypothesize plausible bugs, and confirm that the tests have high statistical power to detect those bugs.

You could hypothesize specific bugs that occurred during development, and relatively easily make tests for them.

But, you could also just test those in the deterministic part of your program.
You could hypothesize bounds on statistical distances: null hypothesis, $D(P \mathbin\| Q) \leq \varepsilon$; alternative hypothesis, $D(P \mathbin\| Q) \geq \varepsilon + \delta$.  Then you can choose hypothesis tests that are guaranteed to have certain false alarm rates and statistical power for those alternative hypotheses.  You could even choose the two bounds to use different statistical distances, e.g. the null hypothesis might be bounded KL divergence while the alternative hypothesis is a bug of excess Hellinger distance.

But, the numbers of samples required for these tests to attain prescribed false alarm rates and statistical power are usually superlinear in $1/\varepsilon$ and $1/\delta$—if they exist at all with such guarantees, which for some statistical distances $D$ they do not!
You could just apply standard hypothesis tests and blindly hope they'll catch bugs.  Actually in practice this works quite well during development to catch obvious bugs early on.

But, it doesn't get you very far.

As your system gets bigger, you will be tempted to expand the tests you do.

With deterministic property tests, adding a test case to a test suite just means each run of the test suite takes a little more time.
With $n$ random hypothesis tests, if each test case has a false alarm rate $\alpha$, the test suite has a false alarm rate $1 - (1 - \alpha)^n$ which rapidly approaches $1$—i.e., false alarms nearly all the time—as $n$ increases.  What can you do when you add a new test?

Leave the false alarm rate of the test cases alone.

But, then if you had calibrated the test cases so that the test suite has a prescribed false alarm rate, that rate will go up as you add more tests—even if the software is working perfectly!
Whenever you add a test case, recalibate all the test cases to have false alarm rate $\alpha' < \alpha$ so that $1 - (1 - \alpha)^n = 1 - (1 - \alpha')^{n + 1}$, i.e. choose $\alpha' = 1 - (1 - \alpha)^{n/(n + 1)}$.

But, the number of samples needed in each test case to maintain the same statistical power at lower false alarm rates tends to grow rapidly with $n$.
Give up on a notion of ‘tests passing’, and instead record a detailed history of test case runs on which you can do meta-analyses later.

But, software people don't like it when the answer from a test suite isn't just PASSED or FAILED, and none of the standard tools like Jenkins are designed to cope with such nonbinary fluidity of notions of test results, as is typical for the white cismale culture in Silicon Valley that dominates software engineering tooling.

My name is Squeamish, not Shirley.
If we're talking about cryptography, the statistical distances are generally going to be so small you don't have a snowball's chance in a Manhattan trash can on a summer day of detecting them anyway.  So go back to step 1: prove your method correct.

Of course, all of this depends on more details about what you're doing.  Maybe, for your application and your distribution and your sampler and your type of statistical distance and your bound $\varepsilon$ on magnitude of statistical distance and your tolerance $\delta$ on magnitude of statistical distance and your development process and your toolchain, you can actually address all these concerns, in which case, great!  Go for it!


How did the power measurements translate to AES Key?

I am not familiar with your side channel attack "here", but it looks like what I have read about before in those that monitor the processor to determine calculations.  "The trick is based on the fact that the “ground” electrical potential in many computers fluctuates according to the computation that is being performed by its processor—including the computations that take place when cryptographic software operates to decrypt data using a secret key."  Researchers using signals from grounding the computer through touch.[1]

"Traditional power analysis would measure power consumption at a frequency comparable to the CPU's clockrate (a few GHz), and is foiled by dampening emanations at these frequencies. Our attack extracts the key using much lower bandwidth (a few kHz to a few MHz, depending on settings and duration). Our attack is also more resilient to filtering and noise." [2]  Look at "Q14: How do you extract the secret key bits?" in this article.  They find the secret key bits one by one sequentially by teasing out processor signals and what they represent.  They go through some technical steps to get their timing correct, not like they walked by a computer in a coffee shop and happened to crack it.

[1]http://www.technologyreview.com/news/530251/how-to-break-cryptography-with-your-bare-hands/
[2]http://www.cs.tau.ac.il/~tromer/handsoff/


To understand a fact related to padding in MD5

Let's say our message is b bits long. When we're done padding it, it should look like this:

P = [  Message   |     Padding     |  Message length ]
    |<- b  bits->|<-- ??? bits --->|<--- 64 bits --->|

Where the message length is just b encoded as a 64-bit integer, and the middle padding section looks like this:

Padding = 1 0 0 0 0 ... 0 0 0 0 0

(Those are actual 1 and 0 bits).

So how many zero bits do we include in the padding? Enough to make P a multiple of 512 bits long (so 512 bits, 1024 bits, 1536 bits, etc.). This allows us to break P up into a complete number of 512-bit chunks for the next step.

For example, let's say the message is 128 bits long (16 bytes). We need 64 bits for the message length. That brings us to 192 bits. In order to get to a multiple of 512 bits, we'll need to add 512 - 192 = 320 bits of padding: a single one followed by 319 zeroes:

P = [  Message   |     Padding     |  Message length ]
    |<-128 bits->|<-- 320 bits --->|<--- 64 bits --->|

Note that the first two sections take up 128 + 320 = 448 bits. In general, once we break the message up into 512-bit blocks, the last block will contain 64 bits for the message length and 512 - 64 = 448 bits for the end of the message and the padding combined. This is where the 448 number in the RFC comes from.


Using only pseudorandom function to drive many deterministic keys

Yes, what you suggest is essentially "KDF in Counter Mode" as defined in section 5.1 of SP 800-108 (pdf). That shows how to derive a long block of "derived key material" using a PRF in counter mode as you do. It includes some inputs for differentiating the context and length of the derived key for domain separation. You could use those, but if you only use this one key derivation procedure you can skip them.

Section 7.3 of the same document states that you can divide the derived material for keys as you like, as long as they do not overlap:

  In the absence of limitations that may be imposed by relying applications, any segment of the derived keying material having the required length can be specified for use as a key, subject to the
  following restriction: When multiple keys (or any other types of secret parameters, e.g. secret initialization vectors) are obtained from the derived keying material, they shall be selected from disjoint (i.e., non-overlapping) segments of the KDF output.

I cannot think of a protocol that does this off the top of my head. E.g. TLS uses a more complex key derivation function, until 1.3 which is supposed to use HKDF.

Speaking of, you might want to use HKDF just because it is more standard, but what you are doing is fine too.


Exercise: recognizing Hawaiian plaintext

Let's assume that the incorrectly decrypted messages look like random sequences of letters.  That assumption might not be exactly correct, but for most modern ciphers it should be pretty close.  In any case, the mention of "random noise" in the assignment suggests that this is indeed the assumption that we're supposed to make.

According to the given rules of Hawaiian morphology, no word may contain two consonants in a row or end in a consonant.  This implies that the correct plaintext can never contain two consonants in a row.

In an incorrect plaintext, the probability of each letter being a consonant is 7 out of 12.  From this, you should be able to calculate (or at least approximate) the probability of two consonants appearing adjacent to each other in the incorrect plaintext as a function of its length.

Given this probability, you can then calculate the probability of all the $2^{50}-1$ incorrect plaintexts having at least one pair of adjacent consonants.  Then pick some reasonably high target probability (say, 0.9999) and calculate the minimum plaintext length needed to meet it.  (Of course, you really should give the full formula for the plaintext length needed to reject all the incorrect plaintexts with a given probability, so that the person reading your answer can choose a higher or lower target probability if they want.)


ECDSA: Why is SigningKey shorter than VerifyingKey

The secret $s$ in ECDSA is a value in the range 1 and the order of the group (exclusive). Some parameters are chosen in such a way that you can simply generate any value within the amount of bits as the chance that you're outside of the range or choose 0 is very small indeed. The public key is a point on the curve, calculated by performing $w = s \cdot G$ - using (modular) point multiplication as $G$ is the base point of the curve.

Generally the value $s$ is just encoded as an unsigned statically sized, big endian integer of the same size as it takes to encode the order of the group in bytes. The public point $w$ however can be encoded in different ways. You've shown a simple concatenation of two unsigned statically sized big endian x,y coordinates. That means of course that it is two times the size of the secret $s$. To get the values of x and y you first have to split the public point encoding exactly in half and then decode the separated values of x and y.

Usually this "flat" encoding (i.e. without structure) is preceded by a byte with value 04 to indicate that it is an uncompressed point. It is however possible to create a compressed point, which is just a single bit larger than the x value. Unfortunately that bit is not available in the encoding of x, so generally the point x is prefixed by a byte with either value 02 or 03 (depending on the value of x and y). Then the value of y can be retrieved by uncompressing the point. So yes, you can "shrink" the public key.

Bitcoin is even sneakier and allows you to recreate the public key out of the signature. That's probably worth a separate question though.

Note that you must first trust the public key before you can use it to verify any signature. If you don't know who's public key you're using, then you do not know who's signature you're verifying either.


Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics?

This depends on what kind of hash function you mean and what kind of security you want.

Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, has forgery probability for messages of $L$ bytes bounded by $8\lceil L/16\rceil/2^{106}$.  This means that an adversary, given $(m, a)$ where $a = \operatorname{Poly1305}_k(m)$ for a uniform random choice of $k$ unknown to the adversary, has probability at most $8\lceil L/16\rceil/2^{106}$ of forging a pair $(m', a')$ where $m \ne m'$.

This forgery probability is independent of any bounds on the attacker's computational costs, so a quantum adversary has no advantage over a classical adversary to forge universal hash authenticators without knowing the key.  However, while the collision probability of Poly1305 as a universal hash family is negligible, an adversary who knows the key can trivially find collisions: Poly1305 is not collision-resistant—more on the distinction between collision probability and collision resistance.
SHA-256 is conjectured to be collision-resistant.  This means, loosely, that it is hard to find a pair of distinct messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$.  There is actually no formalization of this concept, only of keyed collision-resistant hash families because, by a simple technique of counting pigeons and holes, we know that collisions exist in SHA-256, so any trivial algorithm that is hard-coded to print one will succeed with essentially zero cost.  We just don't know those algorithms, so the best we can do is generic collision search.

The state of the art in classical generic collision search, the van Oorschot–Wiener algorithm, is actually cheaper than any of the proposed quantum algorithms for generic collision search.  There may be breakthroughs in generic quantum collision search algorithms, or someone may find specialized cryptanalysis of SHA-256 that works only on quantum computers (e.g., see below about exotic constructions).  But in the current state of the public literature, classical collision searches already appear cheaper than any known quantum collision searches would be even in the unbelievable scenario that qubit operations became as cheap as bit operations.
HMAC-SHA256 is conjectured to be a pseudorandom function family, sometimes loosely called a ‘keyed hash’.  You might use these to make bearer tokens that passed as HTTP cookies in a web application, e.g. $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ where $m$ is the message ‘the bearer of this token is allowed to write cat pictures to the database between 2018-05-18 and 2018-05-25’ and $k$ is a uniform random secret key known only to the application server.

For an adversary to forge bearer tokens, their best known strategy given current cryptanalysis of HMAC-SHA256 is to recover $k$ by a generic preimage search on the function $k \mapsto \operatorname{HMAC-SHA256}_k(m)$ for a known message $m$.  Actually the adversary might have $t_0 = \operatorname{HMAC-SHA256}_{k_0}(m)$, $t_1 = \operatorname{HMAC-SHA256}_{k_1}(m)$, etc., for many different services handing out bearer tokens, and is happy to recover one of the uniform random secret keys $k_i$.

The same applies to, e.g., ciphertexts with one-time pads generated by the Salsa20 hash function (which is emphatically not collision-resistant), or AES ciphertexts with the function $k \mapsto \operatorname{AES256}_k(0)$; although AES is a pseudorandom permutation family, the best generic attack is essentially the same.

The state of the art in classical generic preimage search to find any one of $n$ keys among $2^b$ possibilities with probability $p$ is Oechslin's rainbow tables on a parallel machine, with the computational cost of about $p\cdot 2^b/n$ evaluations of the hash if parallelized at least $q \geq n^2$ ways in the time for $p \cdot 2^b/nq \leq p \cdot 2^b/n^3$  evaluations of the hash.

The state of the art in quantum generic preimage search is Grover's algorithm, which for a single-target attack can find one key among $2^b$ possibilities with high probability $p$ with the computational cost of about $2^{b/2}\sqrt{p}$ evaluations of the hash in quantum superposition on a quantum computer.  This would be a stunning improvement if qubit operations were ever made as cheap as bit operations.

Grover's algorithm can be parallelized by running many quantum computers on different parts of the search space, but the time advantage of parallelizing Grover's is modest: parallelized $k$ ways, it runs in the time of about $2^{b/2} \sqrt{p/k}$ evaluations of the hash in quantum superposition on a single quantum computer: an array of $k$ quantum computers gives only a factor of $\sqrt{k}$ time improvement over than a single quantum computer.  The parallel Grover machine can also be modified to find a preimage for any one of $n \ll k$ targets in the time of $2^{b/2} \sqrt{p/n^{1/2}k}$ quantum evaluations of the hash, at the total cost of $2^{b/2} \sqrt{p/n^{1/2}}$ including communication costs—only a very modest factor of $n^{1/4}$ improvement in cost over a single target.

The bounds on single-target parallel Grover are proven to be optimal for a generic quantum algorithm, so unless something about the structure of HMAC-SHA256 lends itself to better specialized quantum cryptanalysis, in our current model of quantum computers these costs will not get better (but see below about exotic constructions).  It seems unlikely that multi-target parallel Grover variants can cost much less than $2^{b/2} \sqrt{p/n}$, if the $2^{b/2} \sqrt{p/n^{1/2}}$ figure including communication costs is not already optimal.
SHA-256 is conjectured to be preimage-resistant.  There is actually, again, no formalization of fixed preimage-resistant hash functions, only keyed preimage-resistant hash families (our own potato's summary), but the intuitive idea is that if you're challenged with a hash $h$, it should be hard for you to find a message $m$ such that $m = \operatorname{SHA256}(m)$.

If $h$ is 8a798890fe93817163b10b5f7bd2ca4d25d84c52739a645a889c173eee7d9d3d, and you know that $m$ was drawn from one of the strings ‘yes’ or ‘no’, then it is easy to find $m$.  This is a generic preimage search too, but it is worth mentioning as qualitatively different from the case of HMAC-SHA256 with a uniform random key because the input space is small and highly structured.

Still, the adversary's best known strategy for finding a message $m$ given a hash $h$ is essentially the same as the adversary's best known strategy for finding a key $k$ given a bearer token $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ and a known message $m$: generic preimage search with parallel rainbow tables or Grover's algorithm.  Just remember that highly structured messages or messages drawn from nonuniform distributions—especially, e.g., human-chosen passwords—may make the adversary's job substantially easier.
Exotic constructions with specialized cryptanalysis.  These applications of Grover's algorithm and generic search strategies apply to any hash function without knowledge of its structure beyond how to evaluate it.  Nobody has found anything in the structures of SHA-256, Salsa20, BLAKE2, etc., that would admit faster quantum cryptanalysis.  Universal hash families like Poly1305 and GHASH have forgery and collision probabilities that are independent of the attacker's computational budget, so neither a thousand suns nor a real live quantum computer would change them.  But here are some examples of constructions that do have quantum-vulnerable structure:

Collision search.  If $n$ is a public 2048-bit product of two uniform random 1024-bit primes $p$ and $q$, then for uniform random $y \in (\mathbb Z/n\mathbb Z)^\times$ the function $H\colon x \mapsto y^x \bmod n$ of 2048-bit integers to 2048-bit integers is collision-resistant as long as the RSA problem is hard.  But on a quantum computer, Shor's algorithm can find the order $k$ of $y$ modulo $n$ at modest cost in qubit operations, and then trivially compute the collisions $y^0 \equiv y^k \pmod n$, $y^1 \equiv y^{k + 1} \pmod n$, etc.  Similar considerations apply to other factoring-based collision-resistant hash families like VSH.

(Shor's algorithm can also factor $n$ at modest cost in qubit operations, at which point it is trivial to find collisions because the order $k$ always divides $\operatorname{lcm}(p - 1, q - 1)$.)
Preimage search.  If $p$ is the 2048-bit prime modulus of RFC 3526 Group #14 and $g$ is any primitive root modulo $p$, the function $H\colon x \mapsto g^x \bmod p$ is preimage-resistant as long as the finite-field discrete log problem problem in $\mathbb Z/p\mathbb Z$ is hard: finding a preimage is exactly solving the finite-field discrete log problem in a group where it is conjectured to be hard.  But given $h = g^x$, if we can find a period $(\delta, \gamma)$ of the function $f\colon (a, b) \mapsto g^a h^{-b} = g^{a - b x}$ then we have $$g^{a - b x} = g^{a + \delta - (b + \gamma) x}$$ for all $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma x \pmod q$ and thus $x \equiv \delta \gamma^{-1} \pmod q$ where $q$ is the order of $g$.  Again, on a quantum computer Shor's algorithm can find such a period and thereby compute the discrete log $x$ of $y$ with base $g$.

These constructions are of only theoretical interest because they are costlier for legitimate users, they provide no additional security against classical adversaries with current knowledge of cryptanalysis, and they would be much cheaper for quantum adversaries to attack.


Is the One Time Pad secure in additive Rings?

The classical xor-based one-time pad can be generalized to finite groups.

Let $(G,*)$ be such group with order $p$ and $*$ is the group operation(like the xor).
The message, the pad and the ciphertext are elements of $G$.

Now to encrypt a message $m \in G$, choose $k \in G$ uniformly at random and set $c = m * k$. One of the security proofs of the one-time pad consists of showing that $c$ does not give any information on $m$(i.e to find $m$ we might as well pick a $c'$ at random and ignore $c$ completely).

More precisely, if $M$ is a random variable for messages distributed somehow, $K$ is a uniform random variable for the keys, and $C = M*K$ the random variables for the ciphertexts.

What we need to show is that $C = M*K$ is independent of $M$. i.e $C$ does not give any information on $M$.

Proof: We want to show that $P_{C|M}[c|m] = P_C[c]$. First, It's easy to see that $C$ defined as above is uniform(i.e $P_C[c] = \frac{1}{|G|}$). Next observe that $P_{C|M}[c|m] = P_{K|M}[c*(m)^{-1}| m] = P_K[c*(m)^{-1}] = \frac{1}{|G|}$. This follows form the fact that $K$ and $M$ are independent.

Therefore we showed the 'perfect secrecy' property of this constriction.


Deriving a key from a pseudo-random string

The problem with this scheme is that $k_1$ can be calculated from $k_0$. That may not be a huge issue, but it can easily be avoided.

You can make sure that $k_0$ and $k_1$ are derived from the original master $k$ which is derived from the password. So you would have k = PBKDF2(password, mail, iteration_count) and k0 = KDF(k, "Enc") and k0 = KDF(k, "Auth").

If you've just PBKDF2 with SHA-256 you could define the second KDF(k, label) as PBKDF2(password: k, salt: label, alg: 'sha256', iteration: 1).

Other options are given in my other answer on the followup question.


Distributed Asymmetric Key Decryption with threshold

I assume you say on the threshold encryption scheme, in which a dealer generates $(PK,SK_1,\dots,SK_n)$ and distributes the secret keys to users indexed by $1,\dots,n$, and if a combiner obtains $t$ partially-decrypted ciphertexts, it can retrieve a plaintext.

Dodis and Katz showed a generic construction of CCA-secure threshold encryption scheme from a secret sharing scheme and a CCA-secure labeled PKE scheme.
See the paper, Dodis and Katz: Chosen-Ciphertext Security of Multiple Encryption (TCC 2005).
DDH-based constructions (in ROM) are proposed by Gennaro and Shoup: Securing threshold cryptosystems against chosen ciphertext attack (EUROCRYPT 1998, JoC 2002).
You can also find a pairing-based construction in Boneh, Boyen and Halevi: Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles (CT-RSA 2006).


In other words, how hard is it to decrypt a given ciphertext without knowing the details of BLOCK.

Pretty easy; all you'd need to do is ask for:

ENC(0x000..0001)
ENC(0x000..0002)
ENC(0x000..0004)
ENC(0x000..0008)
ENC(0x000..0010)
...
ENC(0x400..0000)
ENC(0x800..0000)

For an $n$-bit block cipher, that's $n$ queries.

Then, you find the linear combination of the above values that gives you the known value ENC(BLOCK) (for example, by Gaussian Elimination); by the homomorphic property you listed, that immediately gives you the value of BLOCK

This same strategy can be devised as a known ciphertext attack, using $n+\epsilon$ random known plaintexts, that'll allow you to decrypt any ciphertext with high probability.


Why does the padding in Merkle–Damgård hash functions like MD5 contain the message length?

MD5, like other hash functions, uses the Merkle-Damgard construction. You take the message and break it up into fixed-size blocks. You start with an intialization vector (IV), which you feed into a compression function along with the first block. Take the output (it will be the same length as the IV), and feed it into the compression function along with the second message block, and so on.

Call the compression function $c$ and the "raw" (unpadded) hash function $h$, we have $$ \begin{align*} h(ZABCD) &= c(h(ZABC), D) \\&= c(c(h(ZAB), C), D) \\&= c(c(c(h(ZA), B), C), D) \\&= c(c(c(c(h(Z), A), B), C), D) \\&= c(c(c(c(c(I,Z), A), B), C), D)\end{align*}$$ with a fixed initialization vector $I$ (each letter represents a block).

Different hash functions use different compression functions. The goal is to prove that we can find a collision in the hash function only if we can find a collision in the compression function (the next step would be to argue that finding a collision in the compression function is extremely difficult).

How would this argument work? We could restate our goal as follows:

If you give me two messages that cause a collision in the hash function, I can find two pairs of inputs for the compression function that cause a collision.

Here's how I do meet this goal: I take the two messages you give me, and split them into blocks. Then I find the right-most block that the two messages don't have in common. For example, if the first message (after padding) has blocks $ZABCD$ and the second has blocks $XKCD$, then third block from the right is different ($B$ vs. $K$).

Since $h(ZABCD) = h(XKCD)$, I check to see if $h(ZABC) = h(XKC)$. If not, I have my collision:

$$ h(ZABCD) = c(h(ZABC), D) = c(h(XKC), D) = h(XKCD). $$

On the other hand, if $h(ZABC) = h(XKC)$, this isn't really a collision for $c$, since the input values are the same. So I go back a block and see if $h(ZAB) = h(XK)$, and do the same thing. If they are not equal, I have a collision: $c(h(ZAB), C) = c(h(XK), C)$. If they are equal, I go back another block.

But now that $B \neq K$, I don't need to worry about whether or not $h(ZA) = h(X)$. I know that $c(h(ZA), B) = c(h(X), K)$ (because $h(ZAB) = h(XK))$, and since $B$ and $K$ are distinct, this is a collision – different inputs, same output.

I can go through this processes for any pair of inputs that generate a hash function collision in order to find a pair of inputs that cause a compression function collision. QED, right?

But wait!
What if when I go from right-to-left, I run out of blocks before I find two that are different? Then the argument breaks. So for the argument to work, I need my padding scheme to ensure that one (padded) message is never the tail end of another.


Technically these two strings have the same entropy I believe:

We cannot tell how much entropy is in a string by looking at it, as it depends on how it is generated and if the values cannot be predicted by other means. For instance, you just posted these strings on this site, so they would not contain (almost) no entropy when used as keys.

Your strings just represents a bit string, possibly of the same size - as you presume, depending on the actual encoding (I don't know the encoding used for the first string, and I can only assume binary digits for the second string). And those bits may contain entropy.

  My question is, does character encoding affect entropy?

No, it doesn't as the character encoding is just about the representation of the bits, not the actual value of the bits. The entropy is present in the value of the bits.

  If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

Yes, assuming that the alphabet is not larger than expected.

  If 256bits is good as an AES key, it's also good as a password right?

No, because normal humans cannot remember such large strings. You could store them in a password manager though, and then 256 bits of entropy is plenty, if not overkill. Generally we don't need password sizes or keys over 128 bits - as long as quantum computers don't come of age anyway.

  I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

No, now the value of the bits of the input string contain less entropy, so this isn't comparable at all. The entropy is not expanded by the password hashing algorithm, so the earlier hash contains less entropy than the latter hash.

  If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

No, because a dictionary attack would almost immediately find the first hash.

  I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

That depends. Let's assume that all the security is in the password or key. In that case we work with Kerckhoffs principle, and we assume that we know how the password is encoded. In that case there is no difference.

Of course, a real world attacker may not work that way. You may use your password for a generic store, and an attacker may not try your particular encoding.

Most humans are terribly bad at remembering 256 ones and zeros. There may be other technical difficulties in entering such a long string of characters as well (screen space, remembering where you are in the string, stealing clipboard contents etc. etc.).


bob hashes his message and encrypt it with alice public key

No, Bob would sign it with his own private key.  For some signature methods, this is roughly similar to "encrypting with the private key", however for other signature methods, it's not; hence it is safer to keep a strong distinction between 'signing' and 'encrypting'

alice receives the original message and the signature she decrypts the signature with her private key and she compares the original message with the signature

No, Alice would validate the signature with Bob's public key.  How Alice gets a verified copy of Bob's public key is an important part of this process, however that is generally considered something to be solved by the whatever mechanism is using the signature method.

Why did we call it digital signature if an attacker can pretend to be bob?

If the attacker does not have Bob's private key (and so he cannot generate sigantures that would verify with Bob's public key), and he can't fool Alice into using the attack's public key, the attacker cannot pretend to be Bob.


If you want to do it with hand calculator, you can use exponentiation by squaring, and compute the remainder after each multiplication. (instead of first computing huge powers and only then taking the remainder)


How to compute result in last step of Socialist millionaires problem?

The answer is that Bob and Alice each calculate $(Q_a Q_b^{-1})^{\alpha \beta}$. Alice computes the quantity $Q_a$, Bob computes $Q_b$, Alice computes $(Q_a Q_b^{-1})^\alpha$ and sends that to Bob, who can compute $c = (Q_a Q_b^{-1})^{\alpha \beta}$.

Let's step through the protocol, keeping in mind the OTR reference (assuming that you do the tests, which I'm leaving out because it clutters things more):

$\text{Alice} \rightarrow \text{Bob}$: Alice picks random $a$ and $\alpha$, sends $g_{2a} = h^{a}$ and $g_{3a} = h^{\alpha}$ to Bob.

$\text{Bob} \rightarrow \text{Alice}$: Bob picks random $b$ and $\beta$, computes $g \equiv g_{2a}^{b}$ and $\gamma \equiv g_{3a}^{\beta}$, picks random $s$, sends $P_b \equiv \gamma^s$, $Q_b = h^s g^y$, $g_{2b} = h^b$, and $g_{3b} = h^\beta$ back to Alice. note: At this point, Bob has computed the secure $g$ and $\gamma$.

$\text{Alice} \rightarrow \text{Bob}$: Alice also computes $g = g_{2b}^{a}$ and $\gamma = g_{3b}^{\alpha}$, computes $P_a \equiv \gamma^r$, $Q_a \equiv h^r g^x$, and $R_a = (Q_a Q_b^{-1})^{\alpha}$, sends $P_a, Q_a, R_a$.

$\text{Bob} \rightarrow \text{Alice}$: Bob computes $R_b \equiv (Q_a Q_b^{-1})^{\beta}$, compute $c = R_{ab} = R_a^{\beta}$, check whether $c = P_a  P_b^{-1}$, send $R_b$.

$\text{Alice} \rightarrow \text{Bob}$: compute $c = R_{ab} = R_b^{\alpha}$, also check $c = P_a P_b^{-1}$.

Bob can compute $c$ in the fourth step, because Bob computed $Q_b$ in step 2, and received $R_a$ from Alice in step 3.


You claim that $k$, $k'$ are chosen independently and uniformly. Assuming these keys are used nowhere else except as PRF keys in this way, and that the length of the PRF keys are at least the security parameter, then you can apply the security of the PRF. Collision resistance doesn't seem relevant to me if the key portion of the PRF input is guaranteed to be chosen randomly. The answer to your question is negligibly close to the answer to:

what is the probability $R(r_1) = R'(r_2)$ where $R$ and $R'$ are independent random functions?

Here it is clear that the distribution over $r_1$ and $r_2$ is irrelevant. The outputs $R(r_1)$ and $R'(r_2)$ are distributed uniformly/independently. So they are equal with probability $1/2^m$.

So the answer to your question seems to be ``negligibly close to $1/2^m$'' where the negligible amount is the security loss of your PRF. If $m$ is large then it is possible the PRF security loss may overwhelm the $1/2^m$ term. If $m$ is small (e.g., constant), then the security loss probably dwarfs the $1/2^m$ term.


How to encrypt and decrypt a transposition cipher?

For Decryption Process, use the reverse of encryption process.
I think you are using a wrong table format. The table should be 4*3 instead of 3*4. Now, Write your encrypted text column by column(4 rows and 3 cols). It will be like this.

e h l

o l _

h t e

e r x

Now, Apply the decryption key of key 2 1 3. The decryption key will be the same.

2 1 3

| | |

2 1 3

Now, arrange the message in columns from above by making necessary transformations. The table will become,

h e l

l o _

t h e

r e x

Now, Read row by row. Your Message will be

hello there

Remember, For decryption, apply the same process for encryption in reverse order.
Hope that helps. :)


Have there been efforts to prevent length extension attacks of hashing algorithms that are based on the Merkle–Damgård construction?

Yes. In this paper, Coron and al. showed that a plain MD construction is secure when it's inputs are prefix-free. They actually proved the indifferentiability of the construction. In other words messages need to be encoded in a prefix-free manner.

Quoting the paper:

  A prefix-free code over the alphabet $\{0, 1\}^κ$is an efficiently computable injective function $g: \{0, 1\}^∗ \to (\{0, 1\}^κ)^∗$such that for all $x \neq y$, $g(x)$ is not a
  prefix of $g(y)$.

One such encoding is given in the paper

  Function g1(m): let $N$ be the message length of $m$ in bits.
  write $m$ as $(m_1, \ldots , m_l)$ where for all $i$, $|m_i| = k$.
  and with the last block $m_l$ padded with $10^r$.
  let $g1(m) = (\langle N \rangle, m_1, \ldots , m_l)$ where $\langle N \rangle$ is a $κ$-bit binary encoding of $N$.


How can k3d3/ed25519-java's performance be improved?

PLEASE NOTE: The code I link to below has not yet been reviewed by anyone with professional cryptography experience. I expect that it contains bugs, and it is definitely not production-ready. I am still learning about the JCA; there are parts of the code I have not finished, and there are parts that I will most likely go back and redo. That said, the tests on example data are passing, so I think it is functional enough for testing.

I have been working on exactly this problem (I want to have a fast Ed25519 Java implementation for use in I2P). In our measurements, the original code was taking about 4 s s+v (one sign operation + one verify operation), which is much too slow for a router. I was able to speed up this implementation by a factor of twenty:

The implementation is a direct port of the slow Python implementation, which had its own expmod method. Using BigInteger.modPow() instead sped the code up by a factor of ten to 457 ms s+v.
I2P has a NativeBigInteger which provides access to libgmp's native modPow() implementation. Using NativeBigInteger.modPow() increased the speed to 289 ms s+v.

Neither of these changes have the constant-time property of the reference implementation of Ed25519 (I think - I am new to this), but then neither did the original.

After these changes, I decided to port DJB's ref10 C implementation from SUPERCOP to Java, to try and gain additional speed increases. (I also rewrote the entire thing to leverage the Java Cryptography Architecture.) The primary change here was in using extended coordinates for the twisted Edwards curve, which decreases the number of required operations.

The code in my branch takes about 20-22 ms s+v, which is about 190x faster than the original. There is no noticeable increase in speed when using NativeBigInteger; my hypothesis is that the use of extended coordinates has greatly decreased the number of modPow() calls, and the code is primarily limited by the speed of scalar multiplication.

I want to make the code even faster (to around 1-2 ms s+v). But I am not sure if there is much more that can be done to speed the code up without moving to a radix-2^51 representation of FieldElements and using tables precomputed from the base (as is done in ref10). I will test using libgmp for multiply() calls, and see if that helps. Another avenue would be to find a better algorithm for scalar multiplication.

(On a side note, I am also unsure if it is possible to use BigIntegers for constant-time operations on secrets. Then again, the only reason I stayed with BigIntegers was because I2P already packages native code in NativeBigInteger, and I would rather have a pure-Java implementation that could leverage libgmp than have to compile more native code for different platforms. If NativeBigInteger provides no speedup, then there is nothing stopping a move to something that does allow for constant-time operations on secrets.)

UPDATE (2014-04-28): I have now ported across the scalarmult and doublescalarmult methods from ref10 (including pre-computation), and it now takes ~2.1ms to run the signing code, and ~3ms to run the verifying code (on my laptop's 64-bit Core i7-U 1.9GHz; this falls directly between the sign and verify speeds for ECDSA_SHA384_P384 and ECDSA_SHA512_P521). But the results aren't correct yet, and I suspect the cause is hidden somewhere in my conversion from C's unsigned and signed bytes into Java's signed bytes and ints. I'm still working to understand the optimizations in ref10, and in particular which optimizations are necessary (like how ref10 uses bit arithmetic to execute cmov - I don't know Java or C intimately enough to know whether this is a) necessary over a switch() statement, and b) potentially where Java's lack of unsigned bytes could be causing bugs).

UPDATE (2014-05-05): The ported code was in fact correct, it was just being passed inputs that weren't correct. Additionally, I discovered two things:

My timing code was still including the creation of a PrivateKey from a seed. The actual signing time was half what I thought (both key extraction and signing are limited by the time to run scalarMultiply()).
The constant-time FieldElement.cmov() implementation (using XOR and AND) was taking 285ns to run, and scalarMultiply() calls it 1728 times. A huge speed increase is seen by changing GroupElement.cmov() to instead use return (b == 0) ? this : other.

Current timings:

1.0934 each sign, 3.0052 each verify, 4.0986 s+v (with constant-time cmov)
0.6006 each sign, 2.9454 each verify, 3.546 s+v (with simple cmov)

For us, this is excellent signing speed. Int comparison on 32-bit architecture is constant-time, so the only unknown here is whether boolean ? val : val is constant-time or not. Then again, much of the rest of the code is not constant-time yet...


First some definitions:

A safe prime is a prime $p$ of the form $p = 2q + 1$ where $q$ is also prime. This is important as the Pohlig-Hellman algorithm runs faster as the largest factor of $p - 1$ becomes smaller. A safe prime is optimal in this sense as $p - 1 = 2q$ and $q$ is therefore the largest possible factor of $p - 1$.

Strong primes are defined here:
https://en.wikipedia.org/wiki/Strong_prime#Definition_in_cryptography

Notice that depending on your definition of "large prime factors" either all strong primes are safe, or they are distinct but similar class of primes.

The fastest algorithms for breaking Diffie-Hellman in the generic case of a group of order $p$ (i.e. those that also work in elliptic curve groups) are $\mathcal{O}(\sqrt{q})$ where $q$ is the largest prime factor of $p$. Hence it is important that $q$ be as large as possible. Ensuring $p$ is a safe prime is a good way of enforcing this.

In specific cases, when groups are represented as $\mathbb{Z}_{p}^{\ast}$, since the fastest algorithms (Index Calculus and Function Field Sieve) are sub-exponential and do not depend on the prime factors of $p$, it is less crucial in these settings.


How to represent a 32-byte SHA2 hash in the shortest possible string?

There are 94 printable ascii characters. Not all of which are valid for file names, however. There should be $64=2^6$ that are valid for file names, so read $6$ bits at a time and map those to one of the $64$ characters that are valid for file names. That would give you $256/6\approx 43$ characters. It will be hard to get much smaller than that.

That process is pretty much base64 anyways, so I'd stick with base64.

Truncation could work depending on your adversary model. What kind of collisions are you worried about? If you are only worried about random collisions, truncation would be fine. If you truncate to $128$ bit outputs, you would expect to see a collision after about $2^{64}$ files. If you are worried about malicious collisions, best to stick with the $\approx 43$ characters of base64.


If the RSA keys were generated randomly, then it is inconceivable that two different devices would happen to pick the same key.

Taking 2048 bit RSA keys as an example, there are approximately $2^{1014}$ 1024 bit primes; if we consider them pairwise (and realise that about half the pairs yield a 2047 bit number), that means there are about $2^{2026}$ RSA modulii possible.

This is an incredibly huge number.  Even if we take into account the fact that the probability for generating each modulii isn't precisely the same (depending on the actual algorithm used), it'd be far more likely that you'd win the lottery 100 times in a row than two devices happen to pick the same RSA key.

On the other hand, examples of devices having the same RSA key have been seen.  In this case, the problem wasn't that someone won the lottery 100 times; instead, they got the random part wrong.

An essential part of the above argument is that we pick them randomly; that is, we start with a 'random' value, and we use that value to select two primes.  If two different devices start with the same 'random' value, and use the same algorithm to select the primes, they'll end up with the same RSA key.

So, to answer your question: whether you can assume that two different devices always have different keys, well, that depends on whether whoever did generate the keys had proper amounts of randomness (entropy) when doing so.  If they did, you can certainly assume it; if they're broken, any such assumption is suspect.


Simulation-based proofs and universal composability proofs

What does this mean, exactly?

The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things are going on in the world during the protocol execution." For instance, the adversary could be running instances of other protocols (or the same protocol), against the honest parties, who could be using related inputs, etc.

There are several flavors of standalone security definitions, not all equivalent. But for the purposes of this question, think of standalone security as exactly the same as UC security, except that but the adversary is not allowed to talk to the environment during the protocol execution. They can talk only before and after the execution. In this model we cannot use the environment to capture an adversary who is doing "other things" during the execution of our protocol. We can model adversaries who run other protocols with honest parties on related inputs after or before our execution, but not during.

A protocol supports sequential composition if it is secure when many instances are executed sequentially, possibly on related inputs. It's easy to express this in both standalone and UC model. You can capture sequential composition by just having the adversary pass along its state between executions. Pre/post-execution communication with the environment is enough to do this, so it's fine in the standalone model.

A protocol supports concurrent composition if it is secure when many instances are executed concurrently, possibly on related inputs. It is not possible to express this in standalone -- only in UC. So standalone security does not guarantee this property, and there are indeed counterexamples of standalone-secure protocols that are insecure when run concurrently.

This restriction of standalone security (i.e., not talking to the environment during the protocol execution) is actually used in security proofs in the standalone model. A common technique for the simulator is to "rewind" the adversary, meaning to revert his internal state back to a previous time in the protocol. This is safe in the standalone model, because the adversary is detached from the environment. But it's not valid in the UC model because if you're trying to rewind the adversary back to round $r$ of the protocol, the adversary might have already spoken to the environment at round $r+1$. The environment cannot be rewound, so this would cause the environment to notice the difference between real & simulated --- this technique cannot be used in a UC security proof.

  A UC proof works if you show that the environment can not tell if it is interacting with the real adversary and the real protocol, or the simulator/ideal adversary and ideal functionality.

Yes.

  To this end, for the proof one must define, for each real adversary, a simulator.

Yes, but there is a shortcut. Take any environment and adversary that you wish to consider, and imagine logically moving the adversary into the environment so that all that is left as a syntactic "dummy adversary". The dummy adversary just says whatever the logical adversary (living inside the environment) tells it, and also reports back all the messages it sees as they are received. This doesn't change the interaction, it only repackages the parts. So every UC interaction can be expressed in terms of an equivalent interaction where the adversary is such a dummy adversary. Since UC security quantifies over all environments, it just suffices to prove security with respect to a dummy adversary.

  My (other) question is, how do we define this simulator? In proofs, I only ever see the simulator being defined by how it behaves when it receives a message from the ideal functionality and how it behaves when it receives a message from the adversary? But why is it never described by how it behaves when it receives a message from the environment? The environment wants a two-way interaction with the real adversary/simulator right? So do we have to define the simulator so it knows how to respond and interact with the environment?

Perhaps this question is cleared up with the understanding of dummy adversaries. When you imagine an interaction with a dummy adversary, you lose the distinction between the environment and the logical adversary embedded in the environment. So the receiving a message from the [logical] adversary / receiving a message from the environment really refer to the same thing. We just know without loss of generality that all communication with the environment will be of the dummy-adversary form: environment says "here is a message to send in the protocol", dummy adversary / simulator has to report back all [simulated] protocol messages that are seen.

  Also, I would be most grateful if you should show me example proofs in the UC framework. The shorter/easier the better, just so I can get my head around it.

Nothing comes immediately to mind. You might want to search for "UC security" + "lecture notes". Also you may be interested in the following recent paper that presents a simplified model of UC that nevertheless is sufficient for 99% of use cases:

Ran Canetti and Asaf Cohen and Yehuda Lindell: A Simpler Variant of Universally Composable Security for Standard Multiparty Computation, CRYPTO 2015.


Is there a time-space tradeoff attack for breaking symmetrical cryptos?

The idea you have is: lets say we have a known plaintext/ciphertext pair; can we use a precomputed table to speed up the recovery of the key?

Well, the main problem with that precomputed tables don't actually speed up the search time, if you count the time taken to generate the precomputed table.  What the table precomputation does is (for example) generate lots of key/ciphertext pairs (for a given plaintext), and store those in a table (in a clever way that makes the table much smaller than just storing each set individually.  That's the real meaning of the phrase "time/memory trade-off"; it doesn't reduce the amount of time taken by using memory, it reduces the amount of memory (in terms of table space) by making the table lookup harder.

Then, when given a plaintext/ciphertext pair, it checks the table to see that if that ciphertext appeared in a key/ciphertext pair; if so, you have a solid guess of the key.

Now, if the key/ciphertext pair never occurred during the precomputation phase, you won't find it in the table; hence to generate a table where a lookup has a $2^{-32}$ probability of finding a 128-bit AES key, you need to spend at least $2^{96}$ time; that's no better than brute force; and we already believe brute force is too hard.

So, you say, why then do we use rainbow tables?  Because we can spend the time to compute those tables once, and then use the same table multiple times.  So, if we have $2^{32}$ different crypto texts with $2^{32}$ different keys, with each crypto text containing the encryption of the same plaintext block (and that same plaintext block would result in $2^{32}$ different ciphertexts), we could (with the above $2^{96}$ precomputation) have a decent chance at recovering the key to one of those sessions.

Isn't that some benefit?  Well, in theory it might, but in practice, not so much.  Remember, we generally run ciphers such as AES within a mode, and the mode may not give us consistent access to the same plaintext across sessions.  For example, for CBC mode, the plaintext we present to the AES block cipher is effectively randomized; that means that you are quite unlikely to get the same plaintext used by even two different sessions, and so rainbow tables are not a win here; brute force is actually more efficient.


Leighton-Micali Hash-Based Signature key sizes

Yes, each LMS parameter sets can be used with any OTS parameter set.
In the final NIST Recommendation for Stateful Hash-Based Signature Schemes there are even more parameters defined.

Those calculations are correct but we do not need to store the entire LMS tree in memory. The solution is to store the seed for the RNG in the private key and calculate the tree on demand. Requires more work but requires much less memory.

Calculations
LMOTS private key:
Size = 4 byte LMOTS typecode + 16 byte identifier + 4 byte q + n byte seed
Example: LMOTS_SHA256_N32_W8 = 4 + 16 + 4 + 32 = 56 byte

LMS private key:
Size = 4 byte LMOTS typecode + 4 byte LMS typecode + 4 byte q + 16 byte identifier + 2^h LMOTS private key size
Examples:
LMS_SHA256_M32_H5 & LMOTS_SHA256_N32_W8: 4 + 4 + 4 + 16 + 2^5 * 56 = 1 820 byte
LMS_SHA256_M32_H25 & LMOTS_SHA256_N32_W1: 4 + 4 + 4 + 16 + 2^25 * 56 = 1 879 048 220 byte ~ 1.9 GB


If you care about security, and don't care much about performance, you might consider a Format Preserving Encryption mode such as FF1; this is a mode of operation that uses a 128-bit block cipher to form an arbitrary sized block cipher; this arbitrary size includes a size of 32 bits.

It is believed (I don't think we have a proof in hand) that, if instantiated with AES, it is as strong as AES (with the caveat inherent with having a block size of 32 bits); hence you have at least 128 bits of security.

Performance isn't great (performing an encryption or decryption of a single block involves 10 AES operations), however depending on what your use case is, it may be quite acceptable.


Deciphering “easy” ciphers without hints

I had a look at classic transpositioning and substitution methods which lead me to encryptions like Vigenére, Autokey, Beaufort and so on. However, those are designed to work with non-numeric alphabets as far as my understanding goes.

While most classical ciphers are applied to the usual alphabet (without different cases), they are not limited to that. It's perfectly fine to have exactly that alphabet you mentioned. In your cryptanalysis you will most likely use number representations of characters anyway (to use addition and modulo), then it just comes down to ordering the alphabet.

  About the cipher: The Cipher contains [a-zA-Z0123456+] without whitespaces, while some patterns are recurring (same characters are repeating in the same order a few times in the cipher).

If there is structure like this, it's very likely to be Vigenere or something similar, operating in fixed "blocks". The distances from the repeating patterns will indicate the block size, as they are multiples of the blocksize.

  I tried a frequency analysis to see if it's just substituted monoalphabetically sign for sign - without success (many results staying at ~8%, no one above 10%)

If you have the symbols a - z, A - Z, 0 - 6, how can  58 symbols have "many at 8%"? Still, it looks like Vigenere fits.

A few things to consider:

Having different cases can imply, they have an alphabet of 2 * 26 (and then add the numbers), or they just use the case of the plaintext, but that should be quite obvious (the distribution is more even in the first case). Alternatively they could just have used a single alphabet and randomly used upper or lower case.
Focus on finding out the block size first. You mentioned index of coincidence, but I guess you meant the "Friedman test". And you have to keep in mind, that your alphabet might be different than the standard one. Use the actual index of coincidence to find out the block size. As an algorithm, you can also calculate the autocorrelation directly (for shift $i=1,2,\dots$, count the positions where the text and the shifted text have the same symbol). The correct block size (and its multiples) will be a outlier(s) from what you would get from a uniform distributed alphabet (for all the wrong block sizes).

From there on, it's just frequency analysis for each position in the block.


Storing passphrase and encrypted private key

The problem is that I'm pretty sure that storing together, the salt, the digest of the passphrase - which is at the end the symmetric key used to encrypt the private key - and the private key itself, encrypted with the digest of the passphrase, is a naive solution.

Storing the digest of course negates both the PKBDF function and the encryption. Storing the salt and wrapped key is of course not a good idea.

  But if I don't save the digest of passphrase together with the encrypted private key, how can I be sure, when decrypting the private key with an inserted passphrase, that the passphrase and the obtained private key are the correct ones?

The easiest way to do this is to use the key for authenticated encryption such as GCM or SIV. If the authentication succeeds then you know that the key was encrypted with the key derived from the passphrase.

So you'd store:

salt | authenticated_ciphertext

where the tag is the authentication tag calculated by the authenticated encryption.

You'd calculate the salt by using a secure random number generator, the ciphertext as:

key = PKBDF2(password, salt, iteration_count, key_size)
authenticated_ciphertext = SIV_AES(key, encoded_rsa_key, [])

Now decryption will fail as SIV_AES includes an IV that doubles as an authentication tag. [] is the additional authenticated data (AAD) which is the empty array, i.e. it is not present.

A disadvantage of this scheme is that you don't know on failure if you have the wrong passphrase or the wrong ciphertext. The simplest way to deal with this is to include a specific ID with the ciphertext and treat it as Additional Authenticated Data in your authenticated encryption. Furthermore, you might want to indicate the protocol version:

protocol | id | salt | authenticated_ciphertext

and the calculations:

key = PKBDF2(password, salt, iteration_count, key_size)
authenticated_ciphertext = SIV_AES(key, encoded_rsa_key, protocol | id)

so now you've got a protocol and id which are also protected by the authentication tag.

Notes:

in above scheme the iteration_count and key_size are considered configuration parameters (i.e. stored separately from the ciphertext), possibly derived from the protocol in the later version;
the above scheme has the disadvantage that the authentication tag can only be verified after decrypting; this is both a disadvantage with regards to security as well as the legit user having to wait a long time for large plaintext - I won't go into the details of these weaknesses here;
note that if active attacks are possible that the stored data may be altered; in that case you should consider that any part of the data (including the protocol, id or just the authentication tag) may have been altered - relying on any specific error condition is in that case not possible anymore.
don't forget to zero your sensitive data in memory after you've concluded your private key calculations or if you've encountered an error condition;

If you're starting to see the full scale of what you're attempting, you might want to use an existing scheme instead.


What is a method for hiding RSA prime values from .exe De-Compiling?

You can't. If the user can run the software, they can extract the key from it. There is research on how to make it difficult to extract the key (white box cryptography), but it's not very successful.

You need to think about what do you want to accomplish. Does the user encrypt the files to themselves, so that they can decrypt it later? Then you could derive a symmetric key from a user's password. Does the user want to encrypt the file to someone else? Then each user should generate a private key (the primes) for themselves, and send their public keys to one another.

(In each scenario there are a lot of details you should take care of, so you're just scratching the surface of the problem)


How to determine r' in pederson commitment?

Assuming that someone knows $log_g(h)$ so that he can calculate any message $m'$ for commitment $c$, how to determine $r'$ in?

First, we assume that he already knows the 'true' value of the commitment $c = g^m h^r$ (as this is the prover who is cheating).  Then, assuming he knows the value $x$ s.t. $g^x = h$, then he sets $r' = r + x^{-1}(m - m')$; then, the pair $m', r'$ is a valid opening of the commitment, as $g^{m'}h^{r'} = g^m g^{m'-m}h^{r + x^{-1}(m - m')} = g^m g^{m'-m}h^r g^{(m'-m)} = g^m h^r = c$


To decrypt with this system, the decryptor first computes $g^{ab}$ (which he can do because he knows one of the two private exponents); then, he computes the modular inverse of $g^{ab}$; that is written as $(g^{ab})^{-1}$.

The modular inverse is defined the same way that the regular multiplicative inverse is defined in the reals (although there it is commonly referred to as the reciprocal): $b  = a^{-1}$ is true iff $a\times b = 1$.

So, $(g^{ab})^{-1}$ is that value $x$ where $x \times g^{ab} \equiv 1 \bmod n$.

Modular inverses can be computed using the Extended Euclidean method; another method (which is usually more expensive, but not drastically so) that works if $n$ is prime is using the identity (for $n$ prime and $a \neq 0$):

$$a^{-1} \equiv a^{n-2} \bmod n$$

Once you have that, then the decryption can then be computed by a single modular multiplication:

$$m = y \times (g^{ab})^{-1} \bmod n$$

In addition: When using DH for encryption using the method you are using, it is more normally called ElGamal (after the person who first invented it); you might want to use that as the search term to look up more information on it.

In addition, there is a distinct (but generally better) alternative method for using the DH primitive to perform encryption; that is known as the Integrated Encryption Scheme; you might want to study that as well.  One advantage that has is that it doesn't require a modular inverse to decrypt.


Given $n=pq$ and $\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \pmod {\lambda(n)}$?

Well, the most straightforward approach is first to show that we must have both:

$$ed \equiv 1 \pmod{p-1}$$

$$ed \equiv 1 \pmod{q-1}$$

We can combine these equivalancies into one, using the Chinese Remainder Theorem; however as $p-1$ and $q-1$ are not relatively prime, we get:

$$ed \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$

This turns out to be a necessary and sufficient condition.  Sometimes, we denote $\lambda(pq) = \text{lcm}(p-1, q-1)$; you'll sometimes see this formulation.


why are non singular curves used in elliptic curve cryptography?

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography.

Why not use singular curves? It turns out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm problem is not harder than of that in a finite field, so there is little reason to use the curve in the first place.

The discriminant characterizes all curves which are non-singular. In other words, the curves that are non-singular are exactly those for which the discriminant $\Delta$ is non-zero.


Is it possible to exactly reverse engineer an unknown cipher inside a black box?

Judging by your comments, you are imagining a box that accepts inputs of arbitrary length. Hence it is a function $f:\{0,1\}^*\to\{0,1\}^*$. There are uncountably many such functions but only countably many programs you could propose as the "reverse engineered" result. This makes your problem fundamentally impossible.


Can someone explain the "three-for-two" trick used by the DGHV scheme authors to squash the decryption circuit?

As far as I understand, the "three-for-two" tricks rely on the fact that one does not need to immediately propagate the carries along the whole adder circuit. You may have heard of the "carry-save-adder" method which consists in postponing the carry propagation to reduce circuit latency. For instance, when adding $a=0, b=1$ and $c=1$ (1 bit-integers), one will split the result into two new integers x and y : carry and output. Thus, one can compute $a+b+c$ as $(x << 1)+y = 2 \times x+y$. In this case, $x = 1$ and $y = 0$. While this example is given with 1-bit integers, we can extend the method to n-bit integers.

Given $a=(1001)_2$, $b=(0101)_2$ and $c=(1010)_2$ (where $(.)_2$ stands for binary notation), one can find that $x=(1001)_2$ and $y=(0110)_2$. Computing both $x,y$ requires $\mathcal{O}(1)$ circuit depth as it does not depend on $(a,b,c)$ bit-length. However, notice that computing $(x \times 2+y)=(10010)_2+(00110)_2=(11000)_2$ will require $n$ depth circuits if based on a basic "carry-ripple adder" (where $n$ is the bit length of given integers). Note there exists logarithmic adder.

About the $d<2^{\lceil\log_{3/2}(k)\rceil+2}$ property, it is related to the fact that one can apply the "three-for-two" trick as many times as necessary. For instance, given integers $(a_0, a_1, a_2, a_3)$, one will apply the trick to the first triple $(a_0,a_1,a_2)$ to obtain $(b_0, b_1)$. Thus it remains to compute the sum $(b_0, b_1, a_3)$ (first step). Using the trick one last time, one will obtain $(b_2, b_3)$.

Every single time one sees a "triplet", one can transform it into a couple. At every step, one can reduce the total amount of elements from $k$ to $k \times \frac{2}{3}$. Since then, it requires at most $\lceil \log_{3/2}(K) \rceil+2$ steps to reduce a list of $K$ integers to 2 integers. To illustrate this point, if $K=9$ and if one applies the trick once, one will obtain a 6-item list. If one apply it one more time, one obtains a 4-item list. It requires a last "trick" to obtain 2 elements that one can finally sum up using a regular adder.

Let $x_i$ be the i-th bit of $x = x_0+x_1 \times 2 + x_2 \times 2^2 +... x_{n-1} \times 2^{n-1}$. The $x_i$ computing part of the "three-for-two" circuit requires at least one multiplication (at least one AND gate / Multiplication gate). As the "trick" is chained, multiplications involved in $x_i$ will stack, doubling (that explains the power of two in the  $d<2^{\lceil\log_{3/2}(k)\rceil+2}$ inequality) the "noise" of the homomorphic encrypted text for every layer of the "chain". That is why the multiplicative depth is at most $d<2^{\lceil\log_{3/2}(k)\rceil+2}$.


How to require two keyholders to decrypt a document?

Splitting a key does not reduce the key strength at all. Simply generate two random 128-bit strings and give one to each party. Encrypt the data with the exclusive OR of the two random strings.

Each string alone gives no information whatsoever about the final key, assuming your random number generator is sound. No party has any advantage.


What encryption schemes to hide the plaintext length exist besides padding?

There are two basic ways to hide the length of a message. And one probably bad way.

Expand (pad with non-message bytes) the message to a constant length. Or multiple of a large constant.
Shrink the length of a message to a constant or multiple of a large constant.
(Bad) Pad all messages with a random number of bits.

Fgrieu is definitely talking about padding on a block cipher level. CBC mode leaks the length of a message accurate to within one multiple of the block size (say 128 bits). CTR mode leaks the length accurate to within one byte (normally) or (potentially) one bit. 128 bits is too accurate a level to hide the plaintext length well.

There are a lot of parts to the conversation. What you're thinking of is probably what I listed as method one. That's a different type of padding. Over a low bandwidth channel this method is likely unusable. With unconstrained bandwidth or for data at rest this type of padding works fine. There are just the obvious problems of wasted bytes and what to do if you go over a constant length.

Method 2 seems impossible. You can't shrink a message that's uncompressible. If you can compress data, though, and then you use method 1 to pad the compressed data, then this doesn't leak any more information about the message than not compressing/padding does. Uncompressed unpadded messages leak the length of a message's encoding in bytes and puts an upper bound on what the entropy of the message is. Using compression and padding leaks only an upper bound on the entropy of the message.

Where he notes that compression can be dangerous he's referring to things like VOIP that do not use constant bit rate compression. If you use variable bit rate  with real time audio then you leak how compressible the audio data is. Silence is highly compressible so a passive observer would notice short packets and conclude that the person is probably silent. (Or if the packets are frequent and shorter the silence between words/syllables.) And it's possible that harder entropy/packet-length analysis could reveal something more valuable. It's probably harder to do a distinguishing attack on someone saying spoken digits. One might be able to steal ID numbers or credit card information sent through the channel that way.

A constant bit rate encrypted protocol can either use no compression (and use more bandwidth) or use lossy compression that keeps only a constant amount of information. Constant bit rate compression will discard information if a signal contains more information than can fit in a constant signal-bandwidth (meaning a symphony would not sound right) and it transmits more data than necessary when a signal is less complex. (For good bit rates you won't notice a difference in quality between no compression, lossless compression, and constant bit rate compression of voice audio data.)

Note fgrieu also says "duration of encryption/decryption will leak some indication about the nature of plaintext". This is another problem. If your constant bit rate compression algorithm isn't also a constant time algorithm, then data related to message entropy is leaked via packet timing unless you transmit infrequently enough to transfer at fixed intervals.

If you're transmitting say HTTP data instead of a signal you can reduce to constant bandwidth, then compression can be dangerous. BREACH and CRIME are examples. Both are active attacks that exploit partial known plaintext data and partial chosen plaintext data. You could steal cookies if the attacks work.

Those types of attacks are a good reason to disable compression on the protocol level. Not all compression is bad. If you're a website serving static constant and send no cookies to steal, then it doesn't make a difference whether you serve compressed data or not. (It's still probably safer to recommend compressing at a file level.) For a public, crawlable, static websites that don't perform message length padding (specifically to defeat message length leaks) it's simple for a passive observer of a network to eliminate the secrecy you expect from encryption. Such an attacker can crawl every page of the static website, build a database that relates paths on a website to the length of the pages returned by a query for that path. If there is one file on the website that is about 25.33 megabytes and you see the server send about 25.33 megabytes to the client over a short period of time, this will give them a big clue concerning what specific content you are viewing on the website. This type of attack works whether you're sending an uncompressed file, an uncompressed file compressed at the protocol level, or a pre-compressed gzip file; as long as the stream lengths are fairly distinct.

There are two more, more advanced, methods you could use that are a combination of methods 1 and 2. If you don't want to leak metadata such as when you're communicating with other computers, the length of the message you want to send, or the messages entropy, then you can build a communications channel that sends fixed size packets at fixed intervals regardless of how the channel is being used. You put message data into a first in first out queue. When its time to send a packet, then take out as much as you can up to the packet length minus say a byte, set the first byte of a packet to the number of message bytes, set the remaining packet bytes to zero, and encrypt the entire packet, including the length field and the zero padding. This scheme pads when you're transmitting less data than there is available bandwidth and chops messages into smaller constant size segments when you're transmitting faster than bandwidth allows. This is analogous to the purpose number stations probably serve.

The second advanced scheme I can think of is to get together a group of friends you trust and agree to send your message data all at the same time from the same computer. Each sender uses their own personal secret key but the entire aggregate of encrypted messages gets sent to every recipient. The recipients try decrypting every message addressed to them and throw out data they can't decrypt. If Alice and Bob trust each other not to leak their personal message length and they're addressing two recipients they trust not to leak their message length, then instead of leaking $|M_A|$ and $|M_B|$ only the value $|M_A| + |M_B|$ leaks. The RetroShare and ZCash projects may do something with a similar philosophy, but for anonymity purposes instead. I'm not sure about them.


I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure.

For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size n.

Take a random input and output pair. If each has $\frac{n}{2}$ 1s and 0s on average, you get to know $\frac{n}{2}$ matrix evements from each row – those where the input is different from the output must be 0. So you get about half the matrix elements.

After two random pairs of plaintext and ciphertext you know on average about $\frac{3}{4}$ of the matrix. Then $\frac{7}{8}$, etc. You need on the order of $log_2(n)$ pairs to find the whole matrix. (With non-random plaintext it may take slightly more pairs than with random.)

Even before leaking the whole permutation, you will leak all sorts of information about the plaintext – for example, the number of 1 and 0 bits will be the same in the ciphertext. Two plaintexts that differ in $k$ bits will have ciphertexts differing in $k$ bits, etc.

Old answer based on using a block cipher:

  Is it possible to reveal the used permutation?

Not if the keyspace is large enough. There are $2^n!$ different $n$-bit permutations, but a block cipher typically has only a 128-bit or 256-bit keyspace, so not all permutations are possible. Unless the cipher is broken, the only way to narrow it down is a brute force search of the keyspace, which is intractable for 128+ bits.

As an aside, you would be using the block cipher directly on plaintexts. Unless the plaintexts are random (or known unique) bitstrings of length $\le n$ bits, that is not a secure mode of operation, it is ECB and is not semantically secure.


Proving the existence of a pseudorandom function

Though this is an 4-year old topic, it seems the following should work:

We can construct a function $F_k(x)$ with output length $l_{out}(n)=l_{key}(n)/2^{l_{in}(n)}=n/2^{O(\log n)}$.

Didivde the key $k$ into $2^{O(\log n)}$ blocks with equal length, denoted by $k_i$ with $i=1,2,\dots, 2^{O(\log n)}$. Because $k$ is uniformly distributed in $\{0,1\}^n$, so is $k_i$.

$F_k(x)= k_x$ is the pseudorandom function.


Double spending on a given Blind Signature over ECC protocol

There's no such problem because, even if you find other $(F,s)$ pair, you still have signature for the same message $m$. So if your message contains anything like transaction id or serial number, it doesn't matter if you have more than one signature for it.

Second thing is that, even there are two pairs for single $m$, given one of them it's hard to find the other. Proof:

Given point $F$ with coordinates $(x,y)$, coordinates $(x,-y)$ correspond to point $-F$. So to have valid $s$ you have to calculate $c'$ that satisfies:

  $-F=b^{-1}R+ab^{-1}G+c'G$

After transformation:

  $c'G=-F-b^{-1}R-ab^{-1}G$

Let's set

  $C=-F-b^{-1}R-ab^{-1}G$.

Then we get:

  $c'G=C$

and this is exactly discrete logarithm problem.


Is cryptanalysis of CTB-Locker really impossible?

No. One of the most important principles of cryptography is that knowing the encryption scheme cannot help someone attempting to decrypt the material without the key. The encryption used seems to be a reasonably well-written implementation of several standard algorithms, for which no practical attacks are known. Finding a way to crack these would be a major undertaking, one which many skilled cryptographers have already failed at.


Doubts regarding implementing AES-128 bit algorithm in my IOT system

What should I set my IV to be ?

For any decent mode of operation, like AES-EAX or AES-CCM you want to not re-use a key-IV pair. That is different keys with the same IV is fine as is the same key with different IVs and different keys with different IVs. Beyond that if you can enforce the above restriction with a counter (or domain-separated counters, e.g. $2^{32}$ unique prefixes for the devices which independently count from $0$ up with their prefix) that is fine, if you can't then you probably want to just generate the IVs at random if possible.

You may want to note that CBC is not a decent mode of operation, forcing you to use unpredictable IVs.

  What should be the key value ?

Keys should ideally be generated such that they are indistinguishable from random strings of the same length. This may involve a key-exchange (using symmetric or asymmetric cryptography) or other methods of key-derivation (e.g. using a password or key-based key deriviation function like Argon2 or HKDF).

In your specific scenario one idea would be let the master have a secret key $K$ and each device having a unique serial number. Then on deployment you use HKDF to derive two keys for each device using its serial number and the data flow direction and store the keys on the device. Then when you get a packet, you can simply re-derive and / or cache the specific keys on your master device.

One final warning: You really don't want to implement AES (or maybe even the mode) yourself because that's quite hard to do securely and with good performance. You really want to use a library for that instead, e.g. BearSSL or mbedTLS.

Oh and if you are doing transport encryption you probably want to consider using TLS (for TCP-like transport guarantees) or DTLS (for UDP-like transport guarantees) with pre-shared keys which handles all the encryption and authentication and IV management for you if you just supply it the shared key (only one this time, it will derive its own for each traffic direction).


Signing different types of messages with the same asymmetric key

As long as the prefixes type1 type2 etc.. are distinct, of equal size, and consistently inserted before everything signed, what's proposed is perfectly fine, and common practice.

That prefixes are distinct and of equal size is a simple and foolproof (thus good) way to implement the necessary and sufficient requirement: no prefix shall be the start of another prefix.

If for some reason prefixes must be of different size, possible conventions insuring that this requirement is met include:

The size in byte of the prefix is before the prefix, on 1 byte (Pascal string convention).
A special terminating byte is at the end of all prefixes, and not used elsewhere in a prefix. Common choices include the byte 0x00 (C string convention) or a separator like :
Using the hash (SHA-512/256) of distinct string prefixes, as proposed in comment. Since that's constant-size, the requirement boils down to using string prefixes that do not collide, and we do not even know how to make otherwise.

At the upper end of the complexity spectrum: everything signed could be per an appropriate ASN.1 grammar. Watch out for the complexity degenerating into interoperability issues, or even exploitable flaws.


How to encode messages in $\Bbb Z_p^*$ to be encrypted with ElGamal scheme?

ElGamal encryption

Given a prime $p$, a quadratic residue (implicitly: modulo $p$) is defined as an $a\in\Bbb Z_p^*$ such that $\exists b\in\Bbb Z_p^*, a\equiv b^2\pmod p$. Quadratic residuosity is efficiently testable using Euler's criterion $a^{(p-1)/2}\equiv1\pmod p$.

Select a $g\in\Bbb Z_p^*$ that is a generator of the subgroup of quadratic residues, of order $q=(p-1)/2$. That is, $g^q\equiv1\pmod p$; and $g^{q/r}\not\equiv1\pmod p$ for all prime(s) $r$ dividing $q$.

The private key is $x\in\Bbb Z_q$, a secret drawn uniformly randomly.

The public key is $h\in\Bbb Z_p^*$ computed as $h=g^x\bmod p$.

Define encryption of $m\in\Bbb Z_p^*$ as $E(m)=(c_1,c_2)=(g^y\bmod p,h^y\,m\bmod p)$ with $y\in\Bbb Z_q$ drawn uniformly randomly for each encryption, then discarded. And define the matching decryption $D(c_1,c_2)={c_1}^{q-x}\,c_2\bmod p$. It holds $D(E(m))=m$.

The encryption system is multiplicatively homomorphic: multiplying any number of ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair which decrypts to the product of the plaintexts in $\Bbb Z_p^*$.

For strong medium-term security, $p$ should be an at-least 2000-bit prime not generated to have $p=t^k\pm s$ for small $s$ and $t$, and $q=(p-1)/2$ should have an at-least 250-bit prime factor.

When restricting to $m$ that are quadratic residues, ElGamal encryption is then believed to have IND-CPA security. A problem otherwise is that $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_2$.

Note: other descriptions of ElGamal encryption make $g$ a generator of the full $\Bbb Z_p^*$, of order $q=p-1$. Similarly, $E(m)$ leaks whether $m$ is a quadratic residue, as the residuosity of $c_1\,c_2\bmod p$.

Fixing the residuosity leak while keeping homomorphicity

Find the smallest $u>1$ that is not a quadratic residue. Check that $u^4<p$, which will hold for overwhelmingly most large $p$.

Define encryption
$$\begin{align}E'(m)&=((c_1,c_2),(c'_1,c'_2))\\
&=\begin{cases}
(E(m),E(1))&\text{when }m\text{ is a quadratic residue}\\
(E(m\,u\bmod p),E(u^2))&\text{otherwise}\\
\end{cases}\end{align}$$
and define $D'((c_1,c_2),(c'_1,c'_2))=D(c_1,c_2)\,\left(\sqrt{D(c'_1,c'_2)}\right)^{-1}\bmod p$, failing if the argument to the square root is not the square of an integer.

For any $m\in\Bbb Z_p^*$ it holds $D'(E'(m))=m$.

The encryption system is multiplicatively homomorphic within a limit: multiplying up to $l=\lfloor\log(p)/2\log(u)\rfloor\ge2$ ciphertexts componentwize in $\Bbb Z_p^*$ yields a pair of pairs which decrypts to the product of the plaintexts in $\Bbb Z_p^*$. If $u=2$ is not a quadratic residue, we can multiply at least 1023 ciphertexts for 2048-bit $p$.

That encryption is CPA-secure, because ElGamal encryption $E$ is only used on messages that are quadratic residues.

Notes:

The detection of decryption failure, if leaked by the decrypter, can be abused into a decryption oracle. Don't allow that!
In homomorphic use, the decrypter (with the private key) can compute how many plaintexts that are not quadratic residues have been multiplicatively combined, as $\log({D(c'_1,c'_2)})/2\log(u)$.

Extensions:

If the later property is undesirable, what the decrypter learns beside the deciphered product can be limited to learning a crude approximation of how many plaintexts that are not quadratic residues have been multiplicatively combined: change $(E(m\,u\bmod p),E(u^2))$ to $(E(m\,u^{-1}\bmod p),E(u^{-2}\bmod p))$ with probability 50%, and adjusts decryption to deal with $D(c'_1,c'_2)^{-1}\bmod p$ being a square (also, the order of $u$ must be large enough). Further, by changing $(E(m),E(1))$ to $(E(m\,u^2\bmod p),E(u^4))$ or $(E(m\,u^{-2}\bmod p),E(u^{-4}\bmod p))$ with probability 25% for each of the alternatives, the proportion of quadratic residues is masked (but $l$ is halved).
It is possible to massively increase $l$ by having the decrypter solve $D(c'_1,c'_2)\equiv(u^2)^x\pmod p$ for small $x$ or $|x|$ (e.g. using Baby Step / Giant Step), then compute $D(c_1,c_2)\,u^{-x}\bmod p$ (also, the order of $u$ must be large enough). Still, homomorphically computing sizable powers (e.g. using square and multiply) is out of reach.
If use of another cryptosystem and key pair is game, we can replace $(c'_1,c'_2)$ with a Paillier ciphertext for plaintext 0 or 1 according to if $m$ is a quadratic residue or not. That simplifies decryption while keeping a multiplicative homomorphic property (with a different modulus for the Paillier component), and $l$ skyrockets. A variant of Paillier accepting negative plaintext can be used to mask from the decrypter the proportion (and to some degree the number) of plaintexts that are not quadratic residues.


Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:

Manoj Prabhakaran & Mike Rosulek: Reconciling Non-malleability with Homomorphic Encryption.
Dan Boneh and Gil Segev and Brent Waters: Targeted Malleability: Homomorphic Encryption for Restricted Computations.

Both papers present encryption schemes (and security definitions) that allow malleability $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.

As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $\textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $\textsf{Enc}(m)$ into any $m' \ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.

The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.

The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.


SPDZ- How to do secure equality comparison

One way of doing this is to subtract the non-secret value from the secret value (in the secure computation) and to test that the result is 0. There are a number of ways of testing 0; generically, you can generate a shared unknown random value, multiply it with the value you want to test and then open. If the opened value is 0 then you know that you started with 0. Otherwise, it's a random value and reveals nothing (since the shared random value is unknown to all parties and so masks the original value).