Ballot box with multiple parties. All can read it, or none can read it

See malleability and commitment schemes.

You are apparently looking for a collusion-preserving implementation of simultaneous broadcast.

By letting each processor control at least one player and directing each processor to choose a random bit for each of its players and outputting the xor of all players' random bits, the resulting coin-flipping protocol is as fair as the system. $\:$ Thus, one smacks straight into this paper's impossibility result.

The ways I know of to get around that impossibility result are:

$\;$ time-lock puzzles, with which the amount of work needed for cooperating players

$\;$ to read the messages is "not too much more" than the amount of work needed for

$\;$ adversarial players to read the messages, and in both cases; the relevant work only

$\;$ needs a small amount of memory and is not (known to be feasibly) parallelizable

$\;$ partial fairness, so that when more than 1/3 of the players are cooperating

$\;$ (in particular, when there are only 2 players) and the number of possible messages is small,

$\;$ cooperating players get "not much less" information than adversarial players get

$\;$ having lots of moderators that only need to be contacted if a player stops participating

$\;$ before or during a reveal phase, each of whom is assigned a small positive integer weight

$\;$ (presumably less than the threshold I'll mention later in this text-block, otherwise there's no point

$\;$ in using more than one moderator), so that if [the sum of the weights assigned to adversarial

$\;$ moderators] is less than [the threshold chosen before the reveal phase begins] is less than or

$\;$ equal to [the sum of the weights assigned to the moderators who appear to be cooperating]]

$\;$ then the "All can read it, or none can read it" property holds

.
(A moderator that merely cannot be contacted or has lost its private key

is neither adversarial nor one who appears to be cooperating.)

To emphasize, even if all moderators are adversarial, the only thing they can do is let players

who stop participating violate the desired "All can read it, or none can read it" property.

In particular, each message must still be chosen independently of the other messages.

It may be that there are other ways around that impossibility result; in particular,

I don't see a reason why the 1/3 threshold should be critical for partial fairness.

Even if there aren't, it appears to me that one could combine the "partial fairness" option with the

"lots of moderators" option in a way that is at least as good as the latter but also provides partial fairness when the latter's inequalities are not too far off and the number of possible messages is small.

Note that I have no idea which of the three options I

described are compatible with being collusion-preserving.


Both schemes are presented as Leveled Homomorphic Encryption schemes, which means that for each $L$, there is at least a set of parameters ($\lambda$, $q$, etc) that allows us to homomorphically evaluate circuits of multiplicative depth up to $L$ (and the reciprocal also holds, i.e. for each set of parameters, there is a limit $L$ on the multiplicative depth of the circuits that can be evaluated).

In those basic forms, they are not really fully homomorphic, because once you set the parameters, you can't evaluate any circuit.

However, there are bootstrapping methods for both schemes, and once you implement the bootstrapping to refresh the ciphertexts after each operation, they become fully homomorphic.

For the FV scheme, the bootstrapping is presented in the own paper, in section 5.

For the HEANN scheme (which you called CKKS in your question), the bootstrapping method only appeared in that subsequent paper and it was improved in this paper that was published this year in Eurocrypt.


Simple question about the branch number of the matrix

Yes. This a degenerate matrix that provides no mixing and has minimal branch number.


You are actually doing the right thing, however you do not include the "_" as part of the characterset. Assuming the alphabet consists of 27 letters (A-Z and "_"), and using the appended JavaScript script (you can simply paste it into the console), returns one sentence which actually does make sense:

THE_FAILURE_MAY_BE_BOTH_DELIBERATE_AND_CLANDESTINE

var ciphertext = "OC_VAWDGPM_VHWTVX_VXJOCVZ_GDX_MWO_VWIZVYGWIZ_NODI_";

var alphabet = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","_"];

var rotation = 1;

var cleartext = "";

while (rotation < 27) {
for (var i=0,l=ciphertext.length;i<l;i++) {

  var character = ciphertext[i];

  var index = 0;

  // get the number in the alphabet
  for (var j=0;j<27;j++) {
    if (alphabet[j] === character) {
      index = j;
      break;
    }
  }

  // rotate

  cleartext += alphabet[(index + rotation) % 27];
}

console.log(cleartext);
rotation++;
cleartext = "";
}

EDIT: There is one thing I wanted to add regarding the script above. We are doing $index + rotation \bmod 27$ here because we are trying every possibility. In a strict sense this is another encryption of the ciphertext, only that one rotation must of course result in the cleartext. If $rotation$ is already known and you want to decrypt the cipher using this exact value, you would of course have to calculate $(index - rotation + 27) \bmod 27 $.


Where can I learn basic cryptography to know more about passwords and Bitcoin?

At the core of your question is a concept called entropy, which is the amount of uncertainty or unpredictability in a set of data.

In cryptography, entropy is related to probabilities, expressed in terms of powers of 2 (bits.)  For example, a fair coin flip has one bit of entropy: it can be either heads (1) or tails (0).  Flipping four coins gives you one of 16 possible outcomes, so it gives you four bits of entropy.  Rolling one six sided die gives you 2.6 bits of entropy ( $2^{2.6} = 6$ ), and so on.  Each Diceware word generated with 5 dice gives you $2^{(2.6 * 5)} = 2^{13}$, or 13 bits of entropy. Ultimately, the number of bits of entropy represents the number of tries required to test every possible input (also known as a brute force attack.)

Be careful not to confuse a password with a hash of a password.  A SHA-1 hash is 160 bits of data that looks very random, so it might appear to have 160 bits of entropy.  If I were to tell my computer to guess every possible value for a SHA-1 hash ( $2^{160}$ ), it would take longer than forever.  However, a hash algorithm is just a math operation, and produces no entropy on its own; a hash digest value contains no more entropy than the amount of entropy that went into its input.  If I know that a hash value is the result of running a user's password through a SHA-1 algorithm, as an attacker I don't have to try all $2^{160}$ possible values.  I just have to figure out all the values the user might have chosen for a password, and run them through the hash algorithm myself.

Because users are humans, the passwords they choose are frequently based in their native language.  If you're guessing the password of an English speaker, it's common to start with a list of frequently chosen English passwords, such as "god", "admin", "root", "password", "abc123", etc, and then move on to testing all the rest of the words in an English dictionary.  If a dictionary has 200,000 possible words in it, the entropy is only 18 bits; it takes only a few milliseconds for a computer to compute the hashes of 200,000 words and test each to see if it matches a given hash value.

Note that password restrictions can severely reduce the number of words I would have to test.  If a password policy says "passwords must be 6 letters long", then I would first test all six letter dictionary words, which is faster than testing all 200,000 dictionary words.  One thing we assume in all cryptosystems is that the attacker knows everything about the system in use, just not the values of the secrets involved.

Check out the wiki page I linked above for a fairly readable introduction to the concepts of entropy.


Paillier can add and multiply, why is it only partially homomorphic?

It can not do multiplication in the plaintext domain using two ciphertexts. In other words, given $E(m_1)$ and $E(m_2)$, you can not get $E(m_1\cdot m_2)$. You can only get $E(m_1+m_2)$.

Given $E(m_1)$ and $m_2$, you can get $E(m_1\cdot m_2)$ however. But notice that $m_2$ in this case was not encrypted. On the site you reference, $C$ is not encrypted. It is using this feature that I just described.


How can I create a block cipher of a reduced size given a fixed length block cipher?

If I understand your problem, I think the best way would be to pad the plaintext bits to 128 bits (8 bytes) with zeros and then use a strong block cipher like AES (Rijndael). Of course, then your ciphertext will be 128 bits instead of the 54 (or whatever) you started with. You can trim these trailing zeros after decryption.  If you want the ciphertext to be the same length, you'll have to use a stream method, but which will not be as strong.


Encrypt and decrypt data accessible by multiple users within a team

One potential risk is your AES key length. Using a key length of 64 bits or less is not advisable as it can be relatively easy to brute force these days. Recommend that you use at least 128 bits.

As for your problem when a user is removed, you may like to try something similar to PGP. Each time you commit a file to the server, you encrypt it with a randomly generated symmetric key and encrypt the key with the public keys of all other legitimate users. In this way, a removed user would no longer be able to access newer files.

But I dunno if that will be secure enough, its two cents worth.


openssl_get_cipher_methods: which one to choose?

IDEA is a block cipher with a 128 bit key size and a 64 bit block size. AES-256 is a more modern block cipher with a key size of 256 bits and a block size of 128 bits. For large files AES certainly has the advantage.

As for the modes of operation: CBC, CFB and CFB1 are all non-authenticated modes of operation. CFB1 is an older format that is mainly useful for its error propagation properties. That's not often considered an important factor anymore. So lets focus on CBC and CFB. CFB is probably the more secure choice. It's a streaming mode of operation which doesn't require a randomized IV (just a unique IV). Because it is a streaming mode it also doesn't require a padding mode.

So AES-CFB is probably the best of the choices above. It certainly can be secure when correctly used within a protocol. But in the end the cipher and mode of operation cannot protect a broken security system. So how safe depends on the details of your protocol.


The seed of a pseudorandom number generator — whether cryptographically secure of not — is the initial input that defines the pseudorandom sequence of outputs generated from it.
It's not really a term that's specific to cryptography, except insofar as there's a considerable amount of overlap between pseudorandom number generation and cryptography, which might be why you haven't been able to find a good definition of it in crypto literature.
That said, such definitions do exist.  For example, NIST SP 800-90A rev. 1 provides the following, admittedly perhaps not the most easily digestible one:

Seed
Noun : A string of bits that is used as input to a DRBG mechanism. The seed will determine a portion of the internal state of the DRBG, and its entropy must be sufficient to support the security strength of the DRBG.
Verb : To acquire bits with sufficient entropy for the desired security strength. These bits will be used as input to a DRBG mechanism to determine a portion of the initial internal state.
Also see reseed.

(Note: "DRBG" stands for "Deterministic Random Bit Generator", which is essentially the NIST term for a pseudorandom number generator.)
SP 800-90A also includes a more detailed description of seeds in section 8.6 (appropriately titled "Seeds"), which I would strongly recommend taking a look at if you're interested in PRNG seeding in a cryptographic context.  It may, however, be a good idea to start reading a few pages up from section 7 ("Functional Model of a DRBG") to familiarize yourself with the concepts and terminology first.


It sounds like a basic Vigenere cipher. From what you wrote, you even have some knowledge about the plaintext, but don't know the position.

You only tried out the first position, maybe just try this with shifting the worst to another position? Or just break the Vigenere cipher as if you knew only the keylength.


Adding identical homomorphically encrypted inputs

Maybe you are looking for something like MPC, where parties want to compute a shared result, but need to keep their data private. Well, as you observed, the result of the computation can reveal more or less information depending on the security model and the number of parties involved. However, you can achieve secure multi-party computation using homomorphic encryption, as indicated in this paper On-the-fly Multiparty Computation on the Cloud via Multipkey Homomorphic Encryption. Unfortunately, the scheme described in the paper is no longer secure for practical computation as recent work by Ducas et.al proved.


Authenticated encryption with forged verification key

Suppose we had a 384-bit block cipher $B_k$.  (Making this practical with a 512-bit block cipher like Threefish-512 is left as an easy exercise for the reader.)

For $k_0, k_1, m \in \operatorname{GF}(2^{128})$, define $H_{k_0,k_1}(m) = k_0 m + k_1$, a standard secure polynomial evaluation one-time MAC for a one-block message.

For nonce $n \in \operatorname{GF}(2^{384})$, plaintext $p \in \operatorname{GF}(2^{128})$, and key $k$, define $$F_{k,n}(p) = (p + k_2, H_{k_0,k_1}(p + k_2)),$$ where $$k_0 \mathbin\Vert k_1 \mathbin\Vert k_2 = B_k(n).$$

Under standard assumptions, $F_{k,n}$ should be a secure authenticated encryption scheme, on a limited message space, built roughly as an encrypt-then-MAC composition.  Decryption is the obvious $F_{k,n}^{-1}(c, t) = c + k_2$, to be done only if $t = H_{k_0,k_1}(c)$.

Note that we can also phrase this as

\begin{align*}
  F_{k,n}(p) &= (c, t), \quad\text{where} \\
  c &= p + k_2, \\
  t &= k_0 p + k_0 k_2 + k_1.
\end{align*}

Our task as an adversary, given legitimate ciphertext $c$ and tag $t$ (authenticated, say, by a signature), and forged plaintext $p'$, is to find $k'$ and $n'$ so that $F_{k',n'}(p') = (c, t)$.  We obviously must have $k_2' = p' + c$; then

\begin{align*}
  t &= k_0' p' + k_0' k_2' + k_1' \\
    &= k_0' p' + k_0' p' + k_0' c + k_1' \\
    &= k_0' c + k_1',
\end{align*}

so if we pick $k_0'$ arbitrarily we must have $k_1' = t + k_0' c$.  If we further pick $k'$ arbitrarily, we then find that $n' = B_{k'}^{-1}(k_0' \mathbin\Vert k_1' \mathbin\Vert k_2') = B_{k'}^{-1}\bigl(k_0' \mathbin\Vert (t + k_0' c) \mathbin\Vert (p' + c)\bigr)$ will give the ciphertext and tag we desired.

If you were watching carefully, which you presumably were because you're not new to this game, you probably noticed that I granted myself the latitude to pick the nonce freely.  Is that cheating?  I don't know—it's not clear what the context of your question is, how it fits into a protocol.  Certainly it would be foolish not to sign the nonce too, but maybe the nonce is implied as a message sequence number here, and the designer figured that it would be space- and bandwidth-efficient to omit it from the message on the wire and consequently also omitted it from the inputs to the signature.


What information does $g^x$ reveal about $x$?

You state

  One way to formalise this question would be: Let $A \subset \mathbb{Z}_P^*$. If Player 2 is honest, we have
  $$
\mathbb{P}[x \in A] = \frac{|A|}{p-1}.
$$
  Can Player 2 increase this probability using the above strategy?

  (Naturally, $A$ can be defined by "the set of all numbers $x$ in $\mathbb{Z}_p$ such that $g^x$ has a '1' in the last digit" and then Player 2 can easily make this probability equal 1, so this formalisation is not very good. Suggestions?)

One way to address this issue, let's call it the encoding of $A$ issue is to hide the obvious properties of $A.$ Thus the players can interact with a randomized encoding of $A.$ Specifically, for your case, we can define $A$ as the set of all numbers $x$ in the integers modulo $n$ such that $H(x)$ has a certain bit pattern $(a_1,a_2,\cdots, a_t)$ in its leading $t$ bits, where $H$ is a secure hash function.

So the game can be played on the hashed image of the relevant quantities.


Affine cipher and plaintext attacks, how to find the base modulo?

Well, to start off with, we have:

$$k_1 m_1 + k_2 - n_1 p = c_1$$
$$k_1 m_2 + k_2 - n_2 p = c_2$$
$$k_1 m_3 + k_2 - n_3 p = c_3$$

Where we know $m_1, c_1, m_2, c_2, m_3, c_3$, and we don't know $k_1, k_2, p, n_1, n_2, n_3$.  I chose to use explicit unknown integers $n_1, n_2, n_3$, rather than modulo an unknown $p$, as it makes it easier to justify the operations we'll do.

The first step is to cancel out the $k_2$ unknown; if we take the first equation, and subtract the second equation, this gives us:

$$(k_1 m_1 + k_2 - n_1 p) - (k_1 m_2 + k_2 - n_2 p) = (c_1) - (c_2)$$

or

$$k_1(m_1 - m_2) - (n_1 - n_2)p = c_1 - c_2$$

Subtracting the second and the third equation gives us:

$$k_1(m_2 - m_3) - (n_2 - n_3)p = c_2 - c_3$$

The next step is to cancel out the $k_1$ unknown; to do this, we multiply the first equation by $(m_2 - m_3)$, multiply the second equation by $(m_1 - m_2)$, and then subtract the two.  Doing this (and performing algebraic simplification) results in:

$$((m_2 - m_3)(n_1 - n_2) - (m_1 - m_2)(n_2 - n_3))p =\\ (m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$$

Or, in other words, $p$ is a factor of $(m_2 - m_3)(c_1 - c_2) - (m_1 - m_2)(c_2 - c_3)$, which is composed entirely of known values (that is, we can compute it).

Hence, the solution is to compute that value, and if it nonzero, factor it, and go through the factors to search for plausible values of $p$.


TLS Key Block calculation - What is a PRF?

Yes, you're misinterpreting the PRF.

It's not just a hash function (and when you hit the end of the function, start back at the beginning).

Instead, it is a function that generates a rather long (actually, infinite) output; we use the first $N$ bits of that output to populate the various key values.

See section 5 of RFC5246; we have:

  TLS's PRF is created by applying P_hash to the secret as:

 PRF(secret, label, seed) = P_<hash>(secret, label + seed)

where

P_hash(secret, seed) = HMAC_hash(secret, A(1) + seed) +
                        HMAC_hash(secret, A(2) + seed) +
                        HMAC_hash(secret, A(3) + seed) + ...

and A() is defined as:

 A(0) = seed
 A(i) = HMAC_hash(secret, A(i-1))

As you can see, until you hit a loop within the internal A function (which is quite unlikely to happen for a while), the PRF output will not repeat itself.

And, to answer your question "does both sides compute the same value", the answer is "this process creates a long output, but deterministically; both sides do generate the same PRF output"


In practice Cross Certification is rare, instead, certificate consumers trust multiple CAs. For example, Mozilla includes 154 different trusted CAs by default with their browser.

As to the process of cross-certification, it involves a CA signing other CA's public key. It can be one-way or cross-certified.


Simple multiplication as an encryption method

As Ricky Demer comments above, an obvious weakness of this scheme is that if you know (or can guess) the plaintext $M$ corresponding to any ciphertext $C$, then you can immediately recover the key by calculating $K = C/M$.  Modern ciphers are generally expected to resist such known-plaintext attacks, making your cipher insecure by any current standards.

In fact, even if we don't know any plaintexts, there are still ways to attack your cipher.  For example, let's say that we've intercepted $k$ ciphertexts $C_1, C_2, \dots, C_k$, and we wish to decrypt them.  The obvious attack is based on the fact that, by definition, each of the ciphertexts is divisible by $K$.  More specifically, $$\gcd(C_1, C_2, \dots, C_k) = K \cdot \gcd(M_1, M_2, \dots, M_k),$$ where $\gcd(\dots)$ denotes the greatest common divisor of the ciphertexts and the plaintexts respectively.  Assuming that the plaintexts are not specifically chosen to all share a common divisor (in which case we might as well regard this deliberate common divisor as part of the key), as the number of intercepted messages $k$ grows, the probability that $\gcd(M_1, M_2, \dots, M_k) = 1$ approaches 100%.

Thus, having intercepted enough ciphertexts, we may calculate $K' = \gcd(C_1, C_2, \dots, C_k)$, which can be done efficiently e.g. using Euclid's algorithm, and be reasonably confident that $K' = K$, possibly times a small factor coincidentally shared by all the plaintext messages.  Thus, we can try decrypting the ciphertexts using $K'$ and see if the results look like plausible messages; if they do not, we can either intercept more ciphertexts, or simply try multiplying the decrypted plaintexts with small factors of $K'$ and see if this yields more plausible-looking results.  Either way, it should not take too many ciphertexts to recover the key and intercept all the messages.

Of course, the attacks above are only practical if the same key $K$ is used to encrypt multiple messages.  If the key for each message is (somehow) chosen independently at random, they do not yield any useful information to the attacker.

However, even in this case, your scheme still leaks some information to the attacker.  As a basic observation, we may note that, if $C$ is not divisible by some number $X$, then $M$ also cannot be divisible by $X$.  This observation alone is enough to show that your cipher lacks semantic security, which, again, makes it insecure by modern standards.

For a more concrete attack, let us assume that you regularly send messages consisting of the same plaintext $M$ (say, "nothing to report"), with different keys $K_1, K_2, \dots, K_n$.  With sufficiently many message, it's very unlikely that all the keys would just happen to share any common factor (unless this is done deliberately, in which case we're just back at the fixed-key case), so I can simply compute $M' = \gcd(C_1, C_2, \dots, C_n)$ and be reasonably confident that $M' = M$.

(Of course, for a more advanced attack, I can look for factors that are shared by most of the ciphertexts you send, which most likely correspond to either repeated plaintexts or repeated keys.  Then, observing any ciphertext that doesn't share one of these factors would be a strong indication that something unusual is going on.)


Chosen plaintext attack on textbook RSA decryption

You seem to have some misconception here. Obviously, you are investigating chosen ciphertext attacks (CCAs) on textbook RSA instead of chosen plaintext attacks (CPAs). To help you with your understanding I am discussing CPA on textbook RSA first. To analyse all these kinds of attacks we formally model the attack as a game between an adversary (trying to break the property) played with a so called challenger.

CPA for textbook RSA

In a CPA game, an adversary can compute arbitrary encryptions of plaintexts of its choice as it is given the public key by the challenger and at some point submits two distinct plaintexts $m_0$ and $m_1$ to the challenger. The challenger then flips a coin to determine a bit $b$ and provides an encryption of $m_b$ (the challenge ciphertext $c^*$) to the attacker and the attacker has to output a guess $b^*$. The adversary wins if the probability that $Pr[b=b^*] -1/2$ is non negligible (in the security parameter). This means that the adversary needs to succeed significantly better than just guessing the bit.

Clearly, textbook RSA does not provide IND-CPA security, since it is deterministic. When the adversary receives the challenge ciphertext $c^*$, he simply encrypts e.g. $m_0$ and if the so obtained ciphertext matches $c^*$, then we have $b^*=0$ and $b^*=1$ otherwise. Note that the probability of winning this game for textbook RSA is 1.

CCA for textbook RSA

This notion is stronger than CPA and this is modelled by giving the adversary additional access to a decryption black-box (oracle) throughout the game, i.e., the adversary is allowed to submit ciphertexts and gets back the respective message, but does not get to hold the decryption key directly.

The only restriction is that the adversary is not allowed to ask the decryption oracle to decrypt the challenge ciphertext $c^*$.

Now lets look at your given procedure. What you describe is a strategy for winning the CCA game for textbook RSA. Note that if the adversary receives the challenge ciphertext $c^*$, he is not allowed to send $c^*$ to the decryption oracle directly. But what the adversary can do is to "blind" the challenge ciphertext with a "blinding value" $r\in \mathbb{Z}_n^*\setminus \{1\}$, i.e., it submits $c'=c^*r^e \pmod n$ to the decryption oracle (note that this is allowed as $c'\neq c^*$). Then the adversary gets back $m'$ from the decryption oracle which has performed a decryption to obtain $m'=(c^*r^e)^d=m_br \bmod n$. Now if the adversary has chosen $r$ as above, i.e., such that it is invertible in $\mathbb{Z}_n$ (which is the case iff $r$ is relatively prime to $n$, i.e., $gcd(r,n)=1$), then the adversary can compute $r^{-1}$ and compute $m_b=m'r^{-1}$ and wins the CCA game with probability 1.

There are subtle differences between IND-CCA1 and IND-CCA2 security, but this explanation should be sufficient here.

Note that when employing a proper padding scheme to textbook RSA such as OAEP, the decryption oracle will only return a decryption if the decryption works correctly, i.e., the decryption oracle checks if the padding of the message is proper. For a "good" padding scheme the probability of ciphertext $c'=c^*r^e \pmod n$ yields a proper decryption is negligible and thus RSA-OAEP provides IND-CCA security as the above discussed attack does not work (with overwhelming probability).


The entire point of a key-derivation function like Argon2 is to increase the time (difficulty) it takes to create a key, and as a side effect, increase the resources required to attack the key.

The problem with other key functions like PBKDF2 is that you can only set the total iterations required, while this is fine for many applications, it isn't ideal for password hashing. PBKDF2 can be easily hashed quicker by using specific equipment. A graphics card is designed to be able to perform repetitive actions relatively fast. This makes hashing an easy task to allow a GPU to quickly power through. However, while GPUs have access to many logical processors, they are quite limited on access to fast memory.

Argon2 is designed with this in mind, allowing three different parameters for it to be enabled best with your hardware. As such it comes with three different adjustable factors (called cost):

Iterations: A total time cost, requiring Argon2 to run a certain amount of time before the output is received, allowing you to adjust how long it takes for an output to generate.
Memory: A system resource cost. Memory is specified as a set amount required for each running instance of the hash function. Unlike iterations, memory is not something that can be optimised for, it's a physical limit that needs a certain sum of physical memory (often RAM) available, and free for hashing. Unless a high-speed storage density revolution occurs in the future, this is going to be one of your hardest hitting costs
Parallelism: The total sum of threads which will run at once in order to generate an output. If you have a large quantity of logical processors available, increasing this cost requires an attacker to either process less congruent attacks at a time, or purchase more expensive equipment.

(It is also important to note that there are several different inputs other than those listed, but those are mostly for low-level API usage of the Argon2lib and can be found here)

A quick guide for configuring Argon2 costs:

Set your Memory cost as high as you can comfortably support. If you at most expect to have 10 users log in at the same time on a dedicated server and have a total of 20 GBs of memory available, issue a total of 1.5 GBs per function run. Also, always remember to be scaling friendly: if you have 20Gbs of memory, and only 10 users login at any given time currently, but you expect to have over a hundred at a time in the future, set your parameters to support such an event.
Set your parallelism in accordance to what your hardware can support. I have a 4 core computer, as such, I set KeePass's parallelism to 4 threads, your needs will vary depending on total logins per second and what your hardware can do.
Set your iterations to a reasonable time, depending on your application. Start with a low value like 10, run your function, and see how long it takes to receive your output, if it feels too fast, increase your iterations. Continue to repeat this process until well-tuned. You will want to set your iterations dependent on your application's needs. If you are performing password hashes for clients on your web service, you may want to aim for around 0.2 seconds per hash. However, if you are doing client-side hashing for local storage encryption, you may want to aim for a couple of seconds as you will likely only ever expect to run one function at a time and run it very few times a day.

Hope this helps and I explained things well for you!


What are the implications of a non “constant time” implementations on trusted systems in a non-network scenario?

"Constant-time" is about not leaking information through timing-based side-channels. If you assume that there is no side-channel, then, in particular, there is no side-channel attack. It is nevertheless a rather bold assumption.

There is a large variety of possible side-channels, and lab demonstrations of attacks have been done exploiting, among others, power usage (especially through differential power analysis), electromagnetic emissions, sound,... Most, though, require the attacker to be in the physical vicinity of the target systems (the actual operating distance may vary, e.g. up to a few dozen meters for sound-based attacks). Timing attacks are special in that respect, since, thanks to the magic of the Internet, they may be exploitable from very remote attackers.

If there is no network, then attacks will be geographically constrained, and thus physical protection measures (isolated building with guards) should be effective. So, in effect, your question really hinges on whether the target system is really "compartmented". As illustrations, consider the following:

Some of the demonstrations of timing attacks have been across virtual machines: the attacker and the victim run in two different VM that merely happens to be cohosted on the same hardware. From an abstract point of view, the isolation contract of the VM is fulfilled; and still, the keys flow.
Not leaving physical tracks is incredibly difficult. For instance, it is possibly to listen on conversations held in a room from a large distance, with a laser microphone: a reflective surface (e.g. a window) vibrates in response to the sound waves, and such vibrations are picked up with interferometry. Theoretically, this kind of listening should work with acoustic attacks.
Electrical activity may leak over power lines. A nominally non-networked system may still send considerable information, unwittingly, over its power cable. This can be fixed with isolation transformers, but ascertaining that such transformers are in place where they should can be quite difficult.
Ultimately, systems are never completely isolated: at some point, some result should exit and have a physically observable effect; otherwise, whatever the system does becomes irrelevant, from a philosophical point of view. Therefore, the overall processing time is available. Then it is a matter of quantifying the precision of the measure.

Thus, in practice, having a non-constant-time AES implementation can be guaranteed not to be an issue only in usage contexts where true physical compartmentation can be shown to be applied, and, in particular, where the ultimate "networking" happens in human-compatible time (i.e. in a matter of days, not microseconds). This tends to be the kind of context where performance is not an issue, thereby removing the most common excuse for using non-constant-time implementations.


With ECDSA is there a way for the verifier to calculate any properties of $k$?

There are no relation we are currently aware of.
The reason is as follows. The map
$$k \mapsto (k G).x$$ is assumed to be a good pseudo random number generator.
(The NSA infiltration of the Dual EC drgb has nothing to do with that fact).
This basically says that k and r can be seen as independant random variables.


Determining strength of a crypto algorithm - clarification with the salsa paper

One can reasonably conjecture, for example, that every function that encrypts data in 0.5 Core-2 cycles/byte is breakable.

This is wrong. OTP is below 0.5 cycles/byte, and as we know it's very secure. Now, the author probably meant proper encryption, like functions that actually take key that doesn't have to be longer or equal to message length.

  Also, does 0.5 Core-2 cycles/byte mean that the algorithm take 2 cycles to encrypt a byte using 0.5 core?

There isn't such thing as 0.5core. Core 2 Duo is architecture of Intel processors, and this means that on such processor, you can encrypt 2 bytes of ciphertext per processor cycle (but keep in mind that operations on ciphertext are usually done on 16-byte blocks, so this means that you do 8 operations on ciphertext).

  Is there a table or some paper that talks about the timings of algorithms in Core-Cycles/byte? I am guessing this is implementation dependent as well, though the algorithm design also sets lower bound on this.

It is implementation dependent, but authors usually give performance they were able to get using optimized implementation, and usually only include time it takes to execute some core function, without padding, key setup etc. Cycles/byte are usually calculated by measuring time it takes to execute algorithm, because for many years now, there isn't set time in which CPU operation finishes.

  Again, its not obvious to me. Can someone explain these two sentences to me?

Well, to achieve avalanche effect, you have to mix data. And author assumed that you cannot do this in 5cycles/byte. But actually Chacha20, variant of Salsa optimized for modern CPU's instructions, seems to be able to get to about 3-4cycles/byte. See here


Short version: It is quite likely that a large proportion of the keys have fixed points, but I don't have any idea on how to find them.
Long version: A stochastic argument
There are $2^{128}!$ permuations of 128-bit blocks, and of these, $!2^{128}$ (this is the subfactorial) are fixpoint-free. It is known that
$\lim_{N\to\infty}\frac{!N}{N!} = \frac 1e \approx 0.3679$ (and this limit is approached quite quickly), i.e. slightly more than one third of all permutations are fixpoint-free.
AES-128 selects $2^{128}$ from these $2^{128}!$ permutations. Assuming this selection behaves like a random one, about 63% of all keys have at least one fixed point.
(This argument is valid for any block cipher with sufficiently large blocks, nothing AES-specific here.)
But ...
Of course, AES (and any block cipher usable in practice) is not a random selection of permutations – for example, all permutations selected by AES are even (AES is composed of operations which each leave some bits unchanged, these are even, and compositions of even permutations are even), thus the available space is halved.
There might be some similar property which makes fixpoint-less permutations less or more likely than a random selection, or even make each key (or no key) have fixed points (both the number of fixed-point-free and non-fixed-point-free permutations are much much larger than the number of available AES keys). I don't know anything here (and as Thomas points out, knowing more might indicate a weakness in AES).
Also, this heuristic gives no way of finding these fixed points (other than brute force).


Difference between Hardware implemented algorithm and software implemented one?

There are typically four different settings where you want to run your crypto.

The Central Processing Unit (CPU). This may be a classic desktop or laptop CPU or the one of your embedded device. Its characteristic is that it usually has rather few computation cores ( < 20), but it can use the ones it has very fast and can execute arbitrary instructions (in mostly arbitrary order) from its assembler language. Crypto algorithms that run on CPUs are most likely software-implemented because the algorithms (i.e. the instructions) are merely information given to the CPU for execution. CPUs are best at running complex, linear algorithms.
The Graphics Processing Unit (GPU). This may be your desktops or laptops graphics processor or it may be your supercomputing computation accelerator. Its characteristic is the high number of cores, the low speed of each core and the limited instruction set. GPUs are made to run simple algorithms massively parallel.  Much like CPUs they accept their algorithms as pieces of information, so it's the software that implements the algorithm.
The Field Programmable Gate Array (FPGA). The FPGA is typically found in small embedded devices and is running specialized algorithms. Its hardware can be configured post shipping, at the expense of lower speeds of operation than with ASICs. With FPGAs you change the hardware layout of your integrated circuit to run your algorithm. Hence algorithms run by FPGAs are said to be hardware implemented, because in its current state, the hardware can run only this exact algorithm, nothing else.
The Application Specific Integrated Circuit (ASIC). This is an integrated circuit that is manufactured to run exactly one algorithm, nothing else. ASICs provide high speed for this algorithm usually and are used when speed matters. An example application are Hardware Security Modules (HSMs) which commonly use ASICs to accelerate the execution of cryptographic operations (like AES encryption). Crypto processors commonly are simple processors with additional crypto-specific ASICs.

As for the security of each platform, the tendency is that if you go down this list, the security will increase. CPUs are usually occupied by many different processes (including the OS), allowing somewhat "easy" side-channel attacks, GPUs are usually not used for crypto (besides hash-cracking), FPGAs should provide more security than CPUs if done right because there less "noise" of other operations on the chip and ASICs have the same benefit, but a bit more extreme.

The speed increases similarly if you go down the list. CPUs must be capable to do many different things and so can't be too much optimized in one direction, some goes for GPUs although they have much more computation power if needed. FPGAs are faster because you can more optimizations and ASICs are king because you can do whatever you want with them and optimize the heck out of them.

The price has a similar order. CPUs are easy to obtain, cheap to program and you can get your program running quickly. GPUs are also quite easy to obtain, a bit more expensive to effectively program and can be get to run your code somewhat fast. FPGAs are more expensive by theirselves and require you to design your algorithm using the hardware language of your FPGA, requiring a lot of time and expertise and thus money. ASICs need to be planned before they are built, have long design cycles, but once you've got the design, you can manufacture them "easily" and for a "low price".

The last two points could already be observed in natura when looking at the development of Bitcoin mining. It started with CPUs on PCs, went on with GPUs, then with FPGAs and is now dominated by ASICs. Note that Bitcoin mining is equivalent to "doing many double-SHA-256 hashes".


Embedding a secret private key in a homomorphic encryption system

"Is there a way to create a homomorphic encryption function F such that given an input

it would produce an output and also cryptographically sign the input and output?"

Sure.  Just let signing key and verification key be part of the homomorphing information.

"Anyone can verify the signature according to the public key,

but no one knows the private key"

Change the signature scheme so that the signing key includes a random part,

which neither the signing algorithm nor the verification algorithm use,

and leave that part out of the homomorphing information.

", and therefore"

The part just after that quote does not follow from what's before that quote.

"no one can generate the signature without running F."

gets into parallelism-resistance without the

"generating a puzzle should take less time than solving it." condition,

and/or quantitative things that mainly apply to password-hashing.

Your stated idea would have complexity-theoretic consequences;

namely, showing that non-uniform MATIME is unexpectedly powerful.

It seems like you'd be interested in publicly-verifiable SNARGs.

(Note that they are arguments, not proofs.)


Are there any differences in operation between existing Diffie-Hellman specifications?

PKCS#3 is an older standard which only defines the DH primitive itself. It contains the following information: parameter generation, the Diffie Hellman key agreement algorithm, integer/octet string conversions (as in PKCS#1, RSA) and the specification of an ASN.1 structure for the parameters. The ASN.1 structure is very limited, containing only the necessary $p$ and $g$ parameters and an optional privateValueLength parameter.

ANS X9.42 is a much larger specification, which contains a great number of derivative algorithms, including the MQV2 and MQV1 authenticated Diffie-Hellman schemes. With regard to the Diffie-Hellman calculations itself, it contains a method to validate the parameters as well as the public key of the other party. It contains two Key Derivation Functions (KDFs) that are slightly different from each other: one octet string concatenation while the other uses ASN.1 encoding. Both use hashing to derive keys from the generated secret value. Finally the ASN.1 definitions are much more extensive than PKCS#3. The domain parameter structure has a required $q$ parameter, which makes the domain parameter structure incompatible with that of PKCS#3. The base calculation and integer to octet string functions used for the secret value are however identical to PKCS#3. ANS X9.42 also helpfully provides calculation examples.

RFC 2631 is a strict subset of ANS X9.42. It only defines Diffie-Hellman algorithms without authentication. It limits Diffie-Hellman to the ephemeral-ephemeral, ephemeral-static and static-static schemes also present in X9.42. It defines only the ASN.1 based KDF with a specific hash function: SHA-1. The data in this ASN.1 structure is limited as well, but it has not been made static. It contains all the domain parameter and public key parameter validation algorithms. It does however not define any ASN.1 structures for the domain parameters nor the public key. Note that RFC 2631 may not use the same names and identifiers specified in X9.42; it for instance uses "ephemeral-static Diffie-Hellman" for the "dhOneFlow" scheme in X9.42. It also introduces the term KEK for the key generated by the KDF.

Finally NIST Special Publication 800-58A is a document that is based on ANS X9.42. It shows key agreement based on Finite Field Cryptography (what most persons call DH) as well as key agreement based on Elliptic Curve Cryptography. It defines MQV authenticated schemes, but only for ECC. An additional test has been defined for the shared secret value: if $Z$ has the value 1 then an error should be returned. It also contains a slightly different KDF, where the counter is removed from the OtherInfo. It also contains references to NIST Special Publication 800-58C for using a KDF that uses extract-then-expand. Instead of just algorithms a lot of this standard provides indications on how to properly implement the standard. This document seems to be most up to date and provides clearly more information than the other documents.

This answer is based on PKCS#3 Version 1.4, ANS X9.42–2003, RFC 2631 of June 1999 and NIST SP 800 56A: Revision 2, May 2013. Note that ANS X9.42 is not publicly available.


RC4 encryption -> AES encryption = more or less secure than RC4 or AES alone?

What type of attack are you trying to prevent?

If it's a brute-force attack, AES-128 is more than sufficient. In the best case scenario, combining RC4 and AES gains you negligible additional security due to a meet-in-the-middle attack.

Are you trying to hedge against a "break" of either RC4 or AES? If so, in the real world, this is extremely unlikely to happen. If either one is weakened by a cryptanalytic result, you will have plenty of time to migrate away from the affected cipher — and you should do this regardless of if you're encrypting only with this cipher, or encrypting with two separate ciphers.

So, practically speaking, there's very little upside. On the downside, you're now heavily increasing the likelihood that you implement the cryptography incorrectly. It's infinitely more likely that you will, as an amateur cryptographer, generate keys insecurely, store keys insecurely, generate two keys that are not independent of one another, use an insecure mode of encryption (e.g., ECB), use static IVs, generate IVs that don't satisfy the requirements of the cryptographic mode for which they're used, fail to use authenticated encryption (e.g., GCM / EAX modes), introduce timing attacks when creating your own authenticated mode (e.g., CTR + HMAC), and so on. There is a near infinite number of ways in which even experienced cryptographers can fail when working directly with ciphers, and well-intentioned amateur cryptographers have practically no hope of implementing it correctly.

The general advice here is to use a high-level cryptographic library like NaCl or KeyCzar that handles the details for you. If you're typing the letters A-E-S into your code, you're doing it wrong.


How to use separate keys for signing and encryption

In TLS 1.2 the Client proposes a list of suites of primitives they are willing to use for TLS. This takes place in clear in the ClientHello message.
You could examine that list and decide one of three things:

The list has a nice modern Forward Secret Diffie-Hellman-style key agreement method you're comfortable using with RSA signatures. You present Certificate #1 for RSA Key #1 and you use the corresponding Private Key to sign stuff in TLS. Certificate #1 says this RSA key is suitable for this purpose (specifically it should set the Key Usage bit 0 digitalSignature).

The list says the client is willing to do RSA key agreement. You present Certificate #2 for RSA key #2 and you use the corresponding Private Key to decrypt the key agreement message from the client. Certificate #2 says this RSA key is suitable for this purpose but not for signing things (probably setting bit 2 of Key Usage aka keyEncipherment -- it should definitely not set bit 0 digitalSignature).

OR 3. You can't accept any of these methods and give up.
Having chosen to behave this way you can now also do TLS 1.3, you should always use Certificate #1 (and the corresponding key) because in TLS 1.3 there is no RSA key agreement mechanism since it is considered dangerous. Because you are using separate keys, a client which is careful about validating Key Usage information can discern that it should not trust Certificate #2 in TLS 1.3 (or doing DH key agreement in TLS 1.2) and so if an attack on your decryption in scenario #2 above is successful those clients are protected and only clients willing to undergo scenario #2 themselves are affected.


No, you are not leaking any information except how to MAC those specific values with the specific key you are using. Using a short message is exactly as secure as using a long message.

For the following, remember the definition HMAC (K,m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)). There are two hashes here, an outer hash and an inner hash nested inside the outer one. The message is inside the inner hash.

Suppose I am an attacker who has your message and MAC result, and I want to derive your key. In order to get your key, I will need to do a brute-force guess. I already know the function H, I know the constants ipad and opad, and I know your message m. I need to try building lots of hashes using different key values until I come up with the right HMAC. The hardness of this task is dependent entirely on the length of K; the length of m is not a factor.

Note, however, that if you are not using a temporary key, then any message/HMAC pairs you give out will be valid for your key, so an attacker could impersonate you in a replay attack for any messages she has seen from you.


Reusing one-time-pad with random plaintext

This question is not really well defined. If by "Would this actually work?" you mean "Will this be as good as using a one time pad of length y" then the short answer is No. Anything susceptible to a brute force attack is not as secure as a one time pad.

What are you trying to achieve? If you already agreed on a key of 512 bits and assume this is the difficulty of brute forcing your algorithm, why not use any common symmetrical encryption algorithm such as AES? It seems you are attempting to design a symmetrical encryption algorithm. This is a great exercise to do, and there are many considerations to be made. For an introduction to some of these considerations, but without too much delving into the theory, I highly recommend the book Cryptography Engineering.

To go into specifics, I'll address a few issues:

Step 1:
A one time pad is agreed upon by physically giving 2 or more parties the same key (or by using leveraging quantum key distribution (QKD), but we'll leave this aside for the moment). Any other type of key exchange is only as secure as the key exchange protocol itself.

Step 2:
By random generator, you must mean pseudo-random generator (PRNG), for two reasons:

If two generators generate the same string, they are definitely not random (again, excluding QKD).
If you have a truly random generator, there is no need for this scheme, as you can already generate a one time pad of arbitrary length.

So we have now established that the security of the bits in step 2 is at most that of the pseudo random generator. The word security can have different definitions, and is commonly expressed in number of bits, a system with 128 bits of security is as secure as a 128 bit random key, i.e. to brute force it you would need to do on the order of 2^128 computational steps.

Step 3:
This would not be necessary. If step 2 gave you a truly random array, this would be no more secure. If step 2 gave a pseudo-random array, this would only add a little more security to the randomness by mangling it with x. But as x is reused (because it is shorter) it could be brute forced.

Step 4:
This again is only as secure as the PRNG used (hash functions and AES are not truly random)


One-time pad mistake in the transmission?

Assuming that you have not used the one-time pad bits $k_2, ..., k_{N+1}$ to encrypt another message, then the answer is no, the attacker cannot determine the message.

This can be seen by using the normal proof of One Time Pad's security; the bits $k_2, ..., k_{N+1}$ are random and uncorrelated to any other bits the attacker has access to; hence the attacker gets no information on the values of $a_1, ..., a_N$ from the sequence $a_1+k_2, ..., a_N+k_{N+1}$.  That those random uncorrelated bits are not the precise ones that you intended to use is irrelevant.

On the other hand, if the sender realized his mistake, and then sent $a_1+k_1, a_2+k_2, ..., a_N+k_N$, at that point, the attacker could deduce information about the message.  This violates the restriction that "bits from the one time pad are used only once", and this actually allow the attacker to deduce the original message (or its complement).


How to make a message into a polynomial on NTRU encryption?

According to Wikipedia:

  Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation.

So, lets say you have a message encoded in base 2 as 101101, you'd set the polynomial to $1+0x+1x^2+1x^3+0x^4+1x^5=1+x^2+x^3+x^5$. That then is your message to encrypt. Technically you could encode a message in ternary and do the same thing. Then you'd have coefficients in $\{-1,0,1\}$. There is no reduction in security by encoding in binary, however, and only having coefficients in $\{0,1\}$.

Now, moving that to your string. First encode your string in base 2 (you can do this how you want), then construct your polynomial. If you have more bits than the degree of the NTRU polynomial, you'll have to split up the message into blocks. I'm sure you know about the standard warnings with using public key encryption for large messages. Unless you have a really, really good reason you shouldn't do it. Encrypt a random key with the public key cipher and encrypt the plaintext with the random key.


How to handle the GCD(V,P) != 1 case when doing point addition or point doubling in elliptic curve cryptography

First of all, I would like to note that the statements you make up front are not universally true -- sometimes we use Elliptic Curves with different equations, and with a bit of cleverness, we can do a long series of point additions/doubles and compute a single multiplicative inverse at the end.  These cavaets don't really change the answers; they do indicate that what you're learning right now isn't everything there are to elliptic curves.

However, you have to start learning somewhere, and where you are isn't a bad place to start.

Now, to address your questions:

  Is $P$ a primary number for all the standard Curves Nist,Secp...

The answer is effectively "yes".  Now, here is why I say "effectively": there are some curves, called "even characteristic", where the number of values $x$ and $y$ can take on is $2^k$, for some integer $k$; however the multiplication operation is not "modulo $2^k$", and what I say below about inverses is still true.

  If the $GCD(X_1 - X_2, P) \neq 1$ then there is no solution for the inverse.  Can this actually happen?

Yes, it can, even though $P$ is prime.  $(X_1-X_2)^{-1}$ will always exist, no matter what $X_1-X_2$ is...., unless it happens to be 0.  That is, if $X_1-X_2=0$, or equivalently, if $X_1 = X_2$, then that inverse won't exist.

Can this happen in practice?  Well, yes, there are two different ways this can happen:

$Y_1 = Y_2$ as well; in that case, you're adding a point to itself.  In other words, you're doing a point doubling; with the standard Weierstrauss elliptic curve equations, there's a distinct algorithm to do that.
$Y_1 = -Y_2$; in that case, you're adding a point to its additive inverse; in that case, the result really will be "the point at infinity".

  I just want to use this standard curves do I need to test the GCD?

Well, you need to compare $X_1$ and $X_2$ to see if you fall into either of the above conditions.  If $X_1 \neq X_2$, then you'll always have $GCD = 1$.

And, if you're asking why the library you're looking at explicitly tests the GCD, well, I have no idea -- I didn't write that library.  However, one possibility is that they are using the Extended Euclidean Algorithm to compute the inverse -- that algorithm does the same logic that's used to compute the GCD (and keeping track of some extra information that is used to compute the inverse).

Finally,

  I decide to use this point at infinity and I encounter a GCD≠1, will the public key resulting be a weaker one?

Depends; if you're doing a long chain of point additions/doubles, and an intermediate point happens to be the point-at-infinity, that's not actually a problem -- that point works algebraically like any other point.

However, if the final point (that is, your "public key") is the point-at-infinity, well, that would be bad.


Encrypt-then-authenticate variant used in IPsec

This is standard Encrypt-then-Authenticate. The only difference is that when doing EtA, it actually isn't necessary to encrypt everything. This strategy makes sense when there is some part of the message that needs integrity and not privacy. In IPSec, the ICV (which is a counter to prevent replay) does not need privacy. Furthermore, by not encrypting it, it is possible to not have to decrypt in order to check if a packet is being replayed (rather, it suffices to check the MAC).

It is important to note that it is possible to use IPSec incorrectly, and do MAC-then-encrypt. This is achieved by computing the IPSec authentication header, and then encrypting. Despite being recommended by some experts, this is BROKEN! So, if you want privacy and integrity, then it should all be done inside the ESP, as is described here.

The fact that AtE is broken in IPSec is not theoretical. See, for example, the paper On the (In)Security of IPsec in MAC-then-Encrypt Configurations by Degabriele and Paterson.


Is Ed25519 really constant-time as widely implemented?

For instance, when implemented in C, what are the chances that the compiler deobfuscate this into a branch?

At first glance, it sounds unlikely.  For example, if you're worried about the compiler translating this as:

 if (b) {
    for(i=0;i<32;i++) r->v[i] = x->v[i];
 }

well, that would be a valid transformation only if the optimizer could deduce that b could only be 0 or 1; depending on how the caller is written, that could be difficult.

Now, there are additional steps that the quoted code could take, such as:

volatile crypto_uint32 *dest = r->v[ix];
volatile crypto_uint32 *src = x->v[ix];
for(i=0;i<32;i++) dest[i] ^= mask & (dest[i] ^ src[i]);

(the volatile attributes would specifically prohibit the optimizer from eliding the memory accesses).

However, ultimately, we can't be certain that the optimizer doesn't insert unexpected branches (or other side channel issues) into our code; for example, the  optimizer could insert logic at the beginning some code of the form:

 if (b) a_do_nothing_call();

We generally assume that the optimizer won't do that sort of thing without a good reason.

  For an assembly implementation, what is the chance that XOR by a mask depends on the number of 1s set in the mask?

The answer to that would depend on the side channels you are concerned about.  We assume that, with an assembler, the instructions you write are pretty much the instructions the CPU will execute, and we generally assume that the XOR instruction on the CPU doesn't access memory conditionally, or change the amount of time taken based on the data.  However, if we're concerned about DPA style attacks (by which I mean an attack that depends on the actions of the gates that make up the CPU), there is some leakage - not typically a large amount, but some.  The techniques we've been discussing wouldn't necessarily be sufficient, and we would need to use additional techniques (in this case, probably some sort of blinding).


Is it possible for this tweakable block cipher scheme to be secure for more than $2^\frac{n}{2}$ blocks? $2^{n}$ blocks?

Abstractly, there is no $2^{l_X/2}$ limit on the security of a block cipher. The security claim is that the block cipher is indistinguishable from a random permutation which it may remain even after the adversary has seen all its inputs and outputs (for a particular key). Similarly, there is no reason a tweakable block cipher needs to become insecure after a certain number of blocks are encrypted.

In practice the security of a block cipher depends on the mode of operation you use and most of those break down one way or another after $2^{l_X/2}$ blocks.

Practical ciphers also do not claim perfect security. AES-128 security claim is only "128-bit security". If you construct a tweakable block cipher from AES-128 the security bound is even lower. E.g. XEX/XTS security proof adds a term that is proportional to the square of the number of encryptions. So you should not use it more than AES itself, but in fact a small factor fewer times.

If you have a tweakable block cipher that is not constructed from another block cipher, its security claim may or may not depend on its block size. So using it like you describe may or may not be secure for more than $2^{l_X/2}$ blocks.


Security implications of using constant string to verify AES key?

It likely depends on the encryption algorithm you use, but the answer is likely NO, this method does not ensure the integrity of ciphertexts.

For example, suppose you're using CBC mode encryption. The value you get for the first plaintext block when decrypting depends only on the first ciphertext block and the IV. Hence, I could intercept a message and change the ciphertext in any way I wanted as long as I kept these two values the same. The resulting, tampered-with ciphertext would pass your proposed integrity check.

However, if you really are only trying to make sure the key is correct (so a user can be informed if they entered a password incorrectly, for example), rather than trying to provide a secure MAC, then this method should work. Just be aware that it's not secure in the MAC sense.

Your scheme will not adversely affect the privacy of the encryption algorithm, as long as the encryption algorithm is secure against chosen-plaintext attacks. All standard encryption algorithms, such as CBC, meet this requirement (as long as they're used with a secure blockcipher, such as AES).

In summary, your scheme (1) will not alert you if a third party tampers with a ciphertext (whereas CBC-MAC would); (2) will almost certainly succeed in letting users know if they're using the correct key; (3) will not compromise the security of the encryption algorithm.


Identity-Based Encryption consist of four algorithms. Extract phase is one of them and it is done by PKG or receiver?

The Extract phase is performed by the Private Key Generator (PKG). Note that in IBE it is not necessary a Public Key Generator, since public keys are just arbitrary bit strings or "identities". So, to sum up:

Setup, executed by the PKG. This algorithm creates, among other things, a master key for the PKG.
Extract, executed by the PKG. This algorithm enables the creation of the corresponding private key for an arbitrary identity. The PKG needs the master key for doing this.
Encrypt, executed by the sender, who only needs to specify the receivers' identity.
Decrypt, executed by the receiver, who is in possession of a private key that must be generated by the Extract algorithm.

This is much better explained in the Wikipedia.


When seeing clearly through all the cube "magic", one recognizes the following: All the cube operations are just key-dependent bit permutations. Therefore, the whole cipher is a sequence of key-dependent permutations and XORs with key bits.

This admits an algebraic description: For all keys, there is a permutation matrix $A\in\mathbb F_2^{512\times512}$ and a vector $b\in\mathbb F_2^{512}$ such that
$$\mathit{cipher} = A\cdot \mathit{plain}+b\text,$$
where $\mathit{plain}$ and $\mathit{cipher}$ are interpreted as vectors over $\mathbb F_2$ of length $512$. Therefore, the cipher is an affine map over $\mathbb F_2$. This is about the most undesirable property a block cipher can exhibit. An attacker has of course no direct access to $A$ and $b$, but there are lots of weaknesses: For example, in a chosen-plaintext scenario, an attacker can

encrypt $\mathit{plain}=0$, thus obtaining $\mathit{cipher}=b$; and subsequently
encrypt $\mathit{plain}=\mathrm e_i$, the $i$th unit vector, for all $i$. He can then subtract $b$ from the resulting ciphertext, yielding $A\cdot\mathit{plain}$, and check which entry of this vector is $1$ — this is the target of the $i$th entry of $\mathit{plain}$ under the permutation $A$.

A chosen-plaintext attacker is therefore capable of obtaining (information equivalent to) the encryption key using a very simple procedure, hence making the cipher, to put it mildly, rather unsatisfactory (which is a synonym for "absolutely broken beyond any hope" in cryptography).


Parameters for comparison of Salsa, HC-128 and SOSEMANUK

HC-128 and SOSEMANUK are two stream ciphers that were studied by the "eSTREAM" project. A bunch of candidates were evaluated, and the "best" (in some way) were kept in the final portfolio.

From the eSTREAM project page, you will find a lot of information on these algorithms, including full specification, reference code, test vectors, and design descriptions. There are also links to benchmarks.

The point of making you write a table that compares parameters for these algorithms is, indeed, to have you read these documents and understand what parameters are relevant. Ideally, you would go beyond what is already documented to take into account some newer research (e.g. while SOSEMANUK is really fast in software, the natural implementation will use a lookup table with state-dependent addresses, which is a bad thing with regards to side-channel attacks; a fair assessment of the algorithms should discuss such things).


Probability that rank of a square matrix, whose each element is uniformly random from a ring of integers modulo prime p, is not full

I'll try to show the probability that the matrix has rank equal to $n$. Two important facts, since $\mathbb{Z}_p$ is a field and not just a ring:

Each column of the matrix can be considered as a random vector drawn from a set of an $n$-dimensional vector space over $\mathbb{Z}_p$, which has $p^n$ vectors.
The number of vectors in a $k$-dimensional subspace will be $p^k$.

So, model the construction of the matrix as drawing $n$ vectors independently at random. For the matrix to have full rank, after the $i$th draw, we need all $i$ vectors to be linearly independent. Assuming the previous $i-1$ vectors are linearly independent, they span a space of dimension $i-1$, so the $i$th vector must be outside of this space. A space of dimension $i-1$ has size $p^{i-1}$, so the probability that a random vector is in that space is $p^{i-1}/p^n$, and we want the opposite to happen, so the probability is:
$$1-\frac{p^{i-1}}{p^n}=1-p^{i-1-n}$$
This even holds for the first vector, which will have rank 1 as long as it is not the all-zero vector.

Thus, the total chance of being full-rank will be

$$\left(1-p^{-n}\right)\left(1-p^{-n+1}\right)\dots\left(1-p^{-1}\right)$$

This is less than $1-1/p$, which means its converse (that the matrix's rank does not equal $n$) must be at least $1/p$. Are you sure the paper didn't mention a lower bound?

Alternatively, since $(1-p^{-i})\geq 1-1/p$ for $i\geq i$, we can argue that the probability of a full-rank matrix is lower-bounded by
$$\left(1-\frac{1}{p}\right)^{n} \geq 1-\frac{n}{p}$$

and thus $\frac{n}{p}$ an upper bound on the probability that $Rank(A)\neq n$.


Does Paillier Homomorphic Encryption Work only with numbers?

Shot answer:

It can work over a set $\mathcal{M}$ of non-numeric data, but you have to find a map from elements of $\mathcal{M}$ to $\mathbb{Z}_n$ in a way that the operations between elements of those two sets are related.

In details:

The message space of Paillier cryptosystem is the ring $\mathbb{Z}_n$ and it guarantees some homomorphic properties over this ring.

Thus, if you want to work homomorphically over any other message space $\mathcal{M}$, you have to model $\mathcal{M}$ as a ring and find an isomorphism, say $\varphi$, between $\mathcal{M}$ and $\mathbb{Z}_n$.

Given two messages $x_0$ and $x_1$ of $\mathcal{M}$, you would apply the isomorphism $\varphi$ to get  $m_0 = \varphi(x_0)$ and $m_1 = \varphi(x_1)$, then, encrypt those messages, getting $c_0 = Enc(m_0)$ and $c_1 = Enc(m_1)$. Now, if you add them, you get $c$ that decrypts to  $ m = m_0 + m_1$. Therefore, after decryption, you would just need to use the isomorphism:

$$\varphi^{-1}(m) = \varphi^{-1}(m_0 + m_1) = \varphi^{-1}(m_0) + \varphi^{-1}(m_1) = x_0 + x_1$$

as expected.

About the the particular case you pointed out: using concatenation as addition will never yield a ring isomorphic to $\mathbb{Z}_n$, because addition in $\mathbb{Z}_n$ is commutative, while concatenation is not (e.g., "hi" + "hello" is different from "hello" + "hi").


Question about lower bound and upper bound key collision

Remember that the bounds are defined for every key. This means, there will be a first set of keys that contains at least $\kappa'$ and at most $\kappa$ keys that all map $x$ to the same $y$. Now, every key not in this set has to be in another set with the same size bounds that maps within which every key maps $x$ to the same $y$ which is different from all the $y_i$ the other sets map to. And so on.

Hence, there are at least $\frac{2^n}{\kappa}$ such sets of keys. All keys in such a set map $x$ to the same $y$ which is different form the $y_i$'s the other sets map to. Consequently, there are at least $\frac{2^n}{\kappa}$ different $y_i$.

Similarly, there are at most $\frac{2^n}{\kappa'}$ such sets of keys and accordingly no more than $\frac{2^n}{\kappa'}$ different values $y_i$.


Theoretical concern.
The standard security reduction of RSA-KEM to the RSA problem relies on the ability of the decryption oracle to handle most of the input space.  If you don't feed all the bits into the KDF, or if you treat some inputs equivalently, you may shoot yourself in the foot, like failure to verify lHash in OAEP.

Practical concern.
If you don't generate all of the bits of the element $x \in \mathbb Z/n\mathbb Z$ from which you derive a key $k = H(x)$, even if you spread them out so that the standard real number cube root attack doesn't work on exponent $e = 3$, you may nevertheless be walking headfirst into the Franklin–Reiter related-message attack, which applies even to exponent $e = 65537$ that everyone quietly accepts without the PTSD over $e = 3$ left from the dark ages of cryptography engineering in the '90s.

Performance concern.
It costs at best about 20k cycles on a modern AMD CPU to compute $x^3 \bmod n$ for 2048-bit $n$—the faster half of RSA with the fastest exponent; any other exponent is slower (except perhaps in Rabin territory), and decryption is much slower.  It costs at worst about 1k cycles to generate 2048 bits with Salsa20 using naive C code, and that's about the easiest option, not the cheapest option.

OAEP also needs to generate about $\lg n$ bits of data, but usually with a much more expensive PRNG (‘MGF’), such as SHA-256.  Under what circumstances could the generation of $x$ be a bottleneck, but not the MGF computation of OAEP?


It is very easy to do this with openssl.

Say foo.crt is your crt file. Then,

$ openssl x509 -in foo.crt -text -noout

will print all the necessary information (issuer, pkey : modulus rsa and exponent, signature algorithm etc) in text format.

If you  give

$ openssl x509 -in foo.crt -text -noout > foo.txt

you will save the previous information to foo.txt file.

To answer your question

  Can you tell me how can I extract from this file public key ready for
  use in hexadecimal (byte) format?

one way to do this is first export the public key and then convert it to  hex form

  $ openssl x509 -in foo.crt  -noout -pubkey > foo-public
  $ openssl rsa -noout -text  -in foo-public -pubin > foo-public-hex

Now foo-public-hex contains your pkey in hex format.

Then you wrote

  I know that in this file is p, q and rest but I want final public key
  ready to use.

I am not sure I follow you...
the private key is not in the .crt file but in .key file and server wont sent it to the client.

If foo.key is you private key  then giving

$openssl rsa -noout -text  -in foo.key

you will see the private exponent and the primes p,q in hex form.


Why is c25519 in the GPG “expert” options?

The risk mainly resides in compatibility.
See, not all GPG users/systems are updated to the latest version. If you look at the GPG changelogs, you'll notice ECC was first introduced to GPG with version 2.1 in 2015:

Support for Elliptic Curve Cryptography (ECC) is now available. ⇒more

None of the pre v2.1 versions of GPG support ECC, which is something that can and most probably will cause several annoyances and interoperability issues — hence the "expert" toggle which can be interpreted as "herewith I confirm that I know what I'm doing and that I'm aware of related compatibility problems that may come within it".
Note that this is only an annoyance for the time being; things will surely brighten up while time goes by and more users/systems adopt newer GPG versions by updating
Also note the related dependencies and — last but not least — the OpenPGP specification "draft" status, which additionally influence adoption speed:

Encryption ECDH — RFC7748: Curve25519
OpenPGP specification: RFC4880bis draft
Dependencies:

libgcrypt >= 1.7.0

Gnuk >= 1.2.0

(Source: https://wiki.gnupg.org/ECC)


Better security than SHA1 for signature?

Is using /dev/urandom a good idea on OS X?

Yes. /dev/urandom is the preferred way to get random values on all modern unixes. Arguments that /dev/random are more secure is a complete myth.

  Are there any other problems here? (I will probably generate a 4096-bit or larger key instead of the 2048-bit one.)

2048 bits is considered secure and likely will be until ~2030. 4096 bits is overkill — the next logical step is 3072 bits, which is roughly equivalent to a 128-bit symmetric key.

  Would changing it to [SHA-256] be enough to avoid the weakness in SHA1?

Probably. But SHA-1 collisions are only just now starting to become computationally feasible. It's worth trying to get upstream to migrate onto a more resistant hash function.


AES-CBC streaming configuration IV usage

This is broken.  If you send two packets with the same block twice, an eavesdropper on the network can tell that they are the same.  An adversary who can influence your traffic—for example, by causing your web browser to submit HTTP requests with some predictable formatting nearby a secret cookie—can exploit this to recover secrets from your conversation.

If you are having a sequential conversation, though, where each message has a unique number (maybe choose even numbers for one side of the conversation, and odd for the other side), then you don't need to transmit the IV each time: You could use $\operatorname{AES}_k(n)$ as the IV for the $n^{\mathit{th}}$ packet[1].  However, this only provides IND-CPA—that is, security against passive eavesdroppers on the network, not against forgers on the network.

Even better, you could use crypto_secretbox_xsalsa20poly1305 (or AES-GCM, if you insist on the notoriously side-channel-leaky AES) and use the message number as the nonce—then you have authenticated encryption which does defend against forgers, and you don't have to rely on a feathery pseudonymous carrion fowl on the internet for security analysis.


Here's an overview of a strong [1], append-only accumulator with your desired properties. This accumulator was originally introduced by Reyzin and Yakoubov in [3]:

Supports provable batch additions.
Is publicly updatable.
The information to update all witnesses is sublinear in the number of elements added.

I'll describe this scheme by example, since formalization would be tedious and is not likely to enlighten.

First, take a look at the figure below.

It consists of a forest of Merkle trees. There's an old accumulator $F_7$ (orange nodes) and a new accumulator $F_{18}$ (orange & green nodes), which "includes" $F_7$. In fact, there's  an append-only proof of this consisting of the filled-in nodes (e.g., nodes 000, 0010, 00110, 00111, 01, 1000).

The prover stores all the leafs and the internal nodes (which include root nodes), while the verifier stores a digest of size $O(\log{n})$ consisting of all the root nodes, where $n$ is the number of accumulated elements.

For example, if you look at just $F_7$ (i.e., ignore all the green stuff), its digest $d_7$ consists of $\{h_{000}, h_{0010}, h_{00110}\}$ where $h_w$ denotes the hash of node $w$. Similarly, the digest $d_{18}$ of $F_{18}$ consists of $\{h_0, h_{1000}\}$.

Key ideas

The scheme is just a small tweak to Crosby and Wallach's history tree [2].

Adding elements

To add an element to the accumulator, the prover appends a leaf to the forest and merges nodes only when necessary so that all tree sizes are a power of two.

I think it's best to try out an example on paper to see when you would merge nodes to maintain this invariant. Formally, let $w = v|b$ denote a node with prefix $v$ concatenated with $b\in\{0,1\}$ and let $v|\bar{b}$ denote its sibling, where $\bar{b} = 1-b$. The idea is to only merge nodes that are siblings (i.e., we only merge $v|0$ with $v|1$ only if they are both in the forest).

For example, node 1000 has no (right) sibling so it cannot be merged with anything. In contrast, node 01 and node 00 are siblings so they were merged, resulting in a parent node 0. This process can continue recursively. For example, consider what happened when node 00111 was added: the first merge of 00111 with 00110 triggered two other merges, eventually creating node 00.

Membership proofs

The proof for an element $x$ being in a digest $d$ is just a Merkle path from $x$ to one of the roots in $d$. For example, the image below shows proofs for two different elements $x$ and $y$ w.r.t. digest $d = h_0$. The proof for $x$ consists of the filled-in nodes (i.e., $\pi_x = \{h_{00000}, h_{0001}, h_{001}, h_{01}\}$), while the proof for $y$ consists of the bold-circled nodes (i.e., $\pi_y = \{h_{00101},h_{0011}, h_{000}, h_{01}\}$). (It so happened that the proofs share a common node $h_{01}$ which I highlighted differently.)

Append-only proofs

If you look again at the overview picture, the append-only proof between $F_7$ and $F_{18}$ consists of "deduplicated" Merkle sibling paths (i.e., the filled-in nodes from the figure) from the old roots of $F_7$ to the new roots in $F_{18}$. Specifically, the nodes with $\times$ on them are "deduplicated": they are computed by hashing up the filled-in nodes.

The proof also consists of extra roots like $h_{1000}$ (also filled-in in the figure). This proof is very similar to the append-only proof in history trees [2] (except it's called a consistency proof in that paper).

Importantly, the size of an append-only proof between $d_m$ and $d_n, m<n$ is $O(\log{n})$.

Updating membership proofs (after an append-only proof)

After a batch addition in the old accumulator with digest $d$, the verifier receives an append-only proof from the prover and ensures nothing has been maliciously removed from $d$ or modified. As you indicated in your question, the verifier has some old membership proofs w.r.t. the old digest $d$ that he wants updated so they can verify w.r.t. the new digest $d'$.

First, note that the old membership proofs are sibling paths to the old root.s
Second, note that append-only proof between $d$ and $d'$ are sibling paths from the old roots to the new roots.
Third, recall that the append-only proof is $O(\log{n})$-sized, where $n$ is the size of the new accumulator.

By now, you might notice that one can easily "compose" the old membership proofs with the append-only proof to obtain new membership proofs w.r.t. the new digest $d'$. This necessarily involves linear computation in the number of old membership proofs, since the verifier needs to update them all. However, the bandwidth required to update the old membership proofs is sublinear since it's just the $O(\log{n})$-sized append-only proof.

For example, the old proof for $y$ w.r.t. to $d$ was $\pi_y = \{h_{00101}\}$ and the new proof is $\pi_y' = \{h_{00101},h_{0011},h_{000}, h_{01}\}$. Note that the verifier needs to compute $h_{0011}$ from its two children: an old root from $F_7$ and the 8th leaf in $F_18$. The verifier can easily do that because it has all the necessary information: the 8th leaf is part of the append-only proof.

In general, one can argue this will work for any element $x$ in any digest $d$ with updated digest $d'$. Again, the intuition is that the append-only proof consists of "deduplicated" Merkle sibling paths from old roots to new roots (e.g., no point in including $h_{0011}$ because it can be recomputed from its children which are included).

Conclusion

A strong, publicly-updatable accumulator with "batch addition" that can update old membership proofs with sublinear bandwidth exists. A slight tweak to Crosby and Wallach's elegant history tree [2] construction gives exactly that.

Hope this make sense and helps!

References

[1] "Strong Accumulators from Collision-Resistant Hashing", by Philippe Camacho, Alejandro Hevia, Marcos Kiwi, and Roberto Opazo

[2] "Efficient Data Structures for Tamper-Evident Logging", by Scott A. Crosby, and Dan S. Wallach

[3] "Efficient Asynchronous Accumulators for Distributed PKI", Leonid Reyzin, and Sophia Yakoubov


Why concatenate the key a second time in HMAC?

As pointed in the question, with common Merkle–Damgård hashes like SHA-256, $H(key\ \Vert\ message)$ is vulnerable to a length extension attack, where $H(key\ \Vert\ message\ \Vert\ pad\ \Vert\ extension)$ can be computed knowing $H(key\ \Vert\ message)$ and the length of $key\ \Vert\ message$ (with $pad$ trivially determined from that), for any known $extension$. Indeed, $H( H(key\ \Vert\ message))$ is enough to block that simple attack.

One good reason to NOT use $H( H(key\ \Vert\ message))$ as a MAC is that we do not have a security proof for that construction, when we have one for HMAC since the origin. Even better, the modern security proof of HMAC gives an argument that HMAC is secure even if the compression function in the underlying hash has properties insufficient to make the hash collision-resistant. In particular, HMAC-MD5 still seems quite strong, even though collision-resistance of MD5 is badly broken.

Both of these security proofs require two hashes each starting with (different variants of) the key. Intuitively: there's a similarity to adding rounds in a block cipher, which makes recovering the key or otherwise breaking the cipher much harder; the outer hash sorts of re-enciphers the result of the previous one.


Is there any relation between two strings with the same MD5 hash?

In general, no: two bitstrings with the same MD5 need not be related by a simple relation (other than the obvious  have the same MD5). Argument: take $2^{128}+1$ distinct random $1024$-bit bitstrings; by the pigeonhole principle, at least two are bound to have the same MD5; since less than $2^{257}$ pairs of distinct bitstrings can be picked among $2^{128}+1$, and our colliding bitstrings where generated with $1024$ bits of entropy each, they must be unrelated in the sense that at least $1024-257=767$ bits from one can't be deduced from the other.

However, some of the efficient methods we have to generate two bitstrings with the same MD5, and all efficient methods that work for 512-bit bitstrings as in the question, produce bitstrings of the same length, and differing only by very few bits within each 512-bit block. The question's example matches that given by Tao Xie and Dengguo Feng in Construct MD5 Collisions Using Just A Single Block Of Message, 2010. That seems to be the first 512-bit MD5 colliding pair published, tough without disclosure of the method. For public method and code, see Marc Stevens, Single-block collision for MD5, 2012; (alternate link to the paper). The location of the bit differences are characteristic of the method, and the differential path it uses.

Further, for some of the first methods discovered to efficiently generate MD5 collisions, bit differences are bound to occur in two adjacent pairs of 512-bit blocks; see in particular Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, in proceedings of Eurocrypt 2005.

To generate very different bitstrings with the same MD5 (including: starting with different chosen strings, and/or of different length), the best first known method required in the order of $2^{65}$ evaluations of the MD5 round function; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website). This would be feasible, was attempted over 11 years ago, but remains a little hard, and never was publicly done AFAIK.

Update: as pointed by otus, we now have more efficient methods allowing to generate colliding bitstrings with any chosen prefix using approximately $2^{16}$ less work (with the restriction that the bitstrings must have the same length, and be nearly identical in their last block). See Marc Stevens, Arjen Lenstra, Benne de Weger: Chosen-prefix collisions for MD5 and applications, in International Journal of Applied Cryptography, Volume 2 Issue 4, July 2012, Pages 322-359; the HashClash page on Chosen-prefix Collisions; this striking application to images.


Can messages be recovered from signatures if the private key is known?

In generally it will not be possible: the signature generation generally includes hashing the message, and secure hashes are one-way functions.

Often the hash can be retrieved during verification with the public key. This is for instance the case for RSA. If you have the hash you can try all possible messages until you find one that calculates to that same hash. This will of course only work if the message space is restricted; the higher the number of valid messages, the lower the chance to find the right one. With a secure hash with any kind of secure output you can however be certain that if a matching message is found that it is the right one.

If the signature verification requires a hash as input, e.g. for ECDSA you may be required to perform the whole verification, which will take longer, so searching may take more time.

There are signature schemes that provide (partial) message recovery (see ISO/IEC 9796-2). In that case the public key verification operation will return (part of) the message. This is useful for data constrained devices such as smart cards.

For verification the private key is not needed, so the answer is no. Having the private key doesn't bring you any benefit over using the public key.


The short answer is that such an encoding would not help with encrypting the content.

A good, modern encryption scheme should at least be secure if the attacker can choose the plaintext, let alone know what the plaintext is. Moreover, most of them are secure if the attacker can even ask for the decryption of ciphertexts of his choice (other than the actual challenge message they're trying to decrypt).

It is worth reading up on known-plaintext-attack, chosen-plaintext-attack and chosen-ciphertext-attacks.


You say they produce 'the exact same output' but are different; I assume you mean the same ciphertext but different MAC aka MIC which is also output. Note Sun/Oracle Java, or more exactly the set of cryptoproviders in Sun/Oracle Java, does not (yet?) support CCM at all, and AIUI neither does OpenJDK. However the optional third-party provider from BouncyCastle does. Android Java on the other hand uses spongycastle which I understand to be a clone of BouncyCastle, but I don't know which version(s).

BouncyCastle 1.50 up provider implementation of AES CCM accepts via Cipher.init(key,param) parameter type javax.crypto.spec.GCMParameterSpec which exists only in Java 7 up, to specify the MAC aka tag size (in bits) as well as the IV aka nonce. Yes, GCMParameterSpec for a CCM cipher. If what you have in Android is equivalent to BC >=1.50 on Java >=7 try that.

Otherwise I think your only choice is to implement CTR + CBCMAC yourself, which wouldn't be all that hard.


How to compute a challenge c using Fiat Shamir?

The challenge is generated by hashing the public parameteres in order of their usage in the proof generation. Consider a hypothetical ZKP proof generation that takes 7 steps.
$ P \to V: x$ means prover sent $x$ to verifier.
$P \leftarrow V: y$ means verifier sent $y$ to prover.

$P \to V: P_1$
$P \leftarrow V: c_1$
$P \to V: P_2$
$P \leftarrow V: c_2$
$P \to V: P_3$
$P \leftarrow V: c_3$
$P \to V: \text{Proof}$

The prover sends $P_1$ to verifier in step 1 and verifier replies with challenge $c_1$ in step 2. Then the prover sends $P_2$ and verifier sends another challenge $c_2$ and then prover sends $P_3$ and verifier sends another challenge $c_3$. The prover finally sends the proof in step 7. Here $P_1$, $P_2$ and $P_3$ are commitments to some data. The list of exchanged messages between prover and verifier is called the transcript. $[P_1, c_1, P_2, c_2, P_3, c_3, \text{Proof}]$ is transcript of the protocol.
Now if the prover wanted to make it non-interactive, he could generate challenge by hashing the transcript till that moment. Thus challenges are generated as

$c_1 = \operatorname{hash}(\text{any public data}+P_1)$
$c_2 = \operatorname{hash}(\text{any public data}+P_1+P_2)$
$c_3 = \operatorname{hash}(\text{any public data}+P_1+P_2+P_3)$


It depends on the access structure.
It is perfect for the structure on $\{P_1, P_2\}$.
However no subsets of players from $Q=\{P_3,..,P_6\}$ have any information on the secret since they only now one part of the sum.


What is the possibility of collision of trailing 160 bits of Keccak_256, for any two differing public-keys as pre-images?

There are about $2^{256}$ distinct inputs, secp256k1 private keys, and about $2^{160}$ distinct outputs, Ethereum addresses.

By the pigeonhole principle, there is at least one address which is shared by many private keys.  In principle, there could be $2^{160} - 1$ addresses each with exactly one private key, and another address with $2^{256} - (2^{160} - 1)$ different private keys.  But that is essentially guaranteed not to be the case in practice.

The map from secp256k1 private keys to Ethereum addresses can reasonably be modeled as a uniform random function.  In this model, the expected number of secp256k1 private keys shared by a single hash is about $2^{96} = 2^{256}\!/2^{160}$.

What can you do with this apparently staggering number of colliding private keys?

Suppose the world has generated $n$ private keys and published their addresses.  The probability that there is a pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$ is about $n^2\!/2^{160}$ by the birthday paradox[1].

If the world has generated a trillion keys, or about $2^{40}$, this probability is below $1/2^{80}$.  In other words, you are essentially guaranteed it hasn't happened.
Suppose you want to find some pair of private keys $k \ne k'$ sharing a common address $H(k) = H(k')$.  The cheapest known method is the van Oorschot–Wiener parallel collision search machine[2], whose expected cost is $\sqrt{2^{160}} = 2^{80}$; of course, if parallelized $p$ ways, it runs in time $2^{80}\!/p$.

This cost is spent by the Bitcoin network in about a day.  But what would you do with this pair of keys?  You could give one of the keys to someone and do something nefarious with the other key, but…if you can already choose someone's key, it's hard to imagine what nefarious things you could do with a colliding key that you couldn't already do with the original in the first place.
Suppose you have a specific address $h = H(k)$ for a key $k$ that you don't know, and you want to find a key $k'$ that matches $h$.  You are essentially guaranteed that $k' \ne k$, but that doesn't matter—$k$ can spend the money of $k'$ and vice versa.  Perhaps you actually have $t$ different addresses, $h_1 = H(k_1)$, $h_2 = H(k_2)$, …, $h_t = H(k_t)$, and you will be happy if you find one matching $k'_i$.  The cheapest known method is an adaptation of Oechslin's rainbow tables[3] to a $p$-way parallel machine[4], which costs $2^{160}\!/t$ as long as $t < p^2$, and runs in time $2^{160}\!/pt$.

Even if you had a quadrillion target keys (about $2^{50}$), which you don't, and you had a $2^{100}$-way parallel computer, which you don't, it would still cost $2^{110}$ to power that computer to find the first matching private key, which you won't.

P.S.  Public keys may be encoded with 512 bits but there are only about $2^{256}$ of them—specifically, there are exactly as many distinct public keys as there are distinct private keys.


What's the difference between word-oriented and byte-oriented ciphers?

To my understanding the only difference between word oriented and byte oriented is that word length depends on the processor used, so maybe 32 bits or 64 bits long, for example.

The idea of a word oriented cipher is that it uses native operations to hardware, processing words instead of bits, making for higher speeds, but clearly that makes designs technology dependent which may not always be the best way to go. Mixing addition mod $2^{16}$ with $GF(2)^{16}$ and multiplication mod $2^{16}+1$
can be complex to analyze. Thus word oriented operations have a complex algebraic representation which may be considered a plus for the designer, but then reliable analysis of such operations also hampers the designer.


Initialization

Key hash function hashstring

Configuration: E is Rijndael with a block size and key size of 256 bits
Input: keystring
Output: hash

The keystring is padded up with bytes valued zero and split up in blocks of 256 bits $S_0$ to $S_n$;
The key blocks $K_0$ to $K_n$ are generated, where $K_0$ consist of $S_0$. The following blocks - if any, most passwords are shorter than 32 bytes - are defined as follows: $K_i = r(K_{i-1})\oplus S_i$ where $r$ is the full subkey derivation of Rijndael-256/256;
A hash block of 256 bits is initialized to zero:
A hash block of 256 bits is initialized to all zero's, lets call this $H_{zero}$, then $H_0 = E(K_0, H_{zero})$, $H_i = E(K_i, E(K_{i-1}))$ for $i > 0$. In other words, the hash block is repeatedly encrypted with itself using the generated key stream $k_i$;
The output is $H_n$.

An answer by Peter Selinger - the creator and current maintainer - showed that the subkey derivation in step 2 is included on purpose. The source code from which this description has been derived does not show any comment or indication that this is the case. To replicate the functionality in another language it may be required to alter an existing Rijndael implementation as the result of the subkey derivation may not be returned to the caller.

Key derivation from the password

Key derivation simply consists of applying hashstring to the password. The password simply consists of a null terminated string of C char. Lets call this key $R$.

Nonce derivation

The nonce derivation consists of the performing the hashstring method over an ASCII string consisting of the following:

gethostname(host, 256);   /* ignore failures */
host[255] = 0;
gettimeofday(&tv, NULL);  /* ignore failures */
sprintf(acc, "%s,%ld,%ld,%ld,%d", host, (long)tv.tv_sec, (long)tv.tv_usec,
   (long)getpid(), count++);

in other words the input of haststring consists of a comma separated ASCII string of the hostname (255 characters max), the seconds in time-of-day, the microseconds in the time-of-day, the process ID and a static / process-wide counter.

Lets call the result $N$.

Creation of IV

The first 4 bytes/characters of the nonce are replaced by the following magic: c051, lets call this $N'$. Then the resulting value is encrypted using key $R$: ${IV} = E(R, N')$

Encryption

Encryption consists of a simple CFB mode using key $R$ and initialization vector $IV$, where the IV is prefixed to the ciphertext.

Decryption

The IV is first decrypted using key $R$ to validate if the if the magic is included in the nonce. The magic therefore acts as a key check value. After that the ciphertext is simply decrypted in CFB mode.


Why routers don't just use Diffie-Hellman protocol?

Even if you were doing that you would only ensure that the communication between you and "some" router is secure. It's still possible to MITM using arpspoof for instance such that in:

[you] <--- A ---> [hacker] <--- B ---> [router]

Communications A & B are encrypted, yet you're not talking to the real router.


Yes, it means ‘a statement that he has received this message from Alice’.

WARNING: Applied Cryptography is archaic and bad, and these days is useful only for historical research, not for learning how to use, choose, or think about cryptography.  Consider the later Cryptography Engineering by the same author instead.


Ok, back to my initial answer (which I edited to the last version, thinking that you did not choose an appropriate generator):

I now think that you may calculate the inverses wrongly:

I tried it with $k=2$ and get:

$r=9,k^{-1}=6, s=10, w=10, u_1=3, u_2=2$ which works out.

Just as an additional comment:

Choosing a generator

Since the order $11$ is prime, you can simply choose an arbitrary element of $Z_{23}^*$, say $h$, and then compute your $g$ as $g=h^{22/11} \pmod{23}$, i.e., every element that lies in this subgroup is a generator of this subgroup.

Take for instance $h=2$ and compute $g=h^{2}\pmod{23}=4$ (in your case, $3$ is also fine).

General case: For the general case $Z_p^*$ with $p$ being prime, an element $g$ is a generator if it holds that all for all prime divisors of the order $p-1$ the following holds:

$g^{(p-1)/q_i}\neq 1 \pmod{p}$.

Typically, you construct $p$ as a safe prime, i.e. choosing prime $q$ and set $p=2q+1$ as, then you know the prime divisors $2$ and $q$ by construction.


I am aware of reduced variants of Salsa20 (Salsa20/12 and Salsa20/8). These are variants of Salsa20 using reduced number of hashing rounds (12 and 8 instead of standard 20).

This is the same idea as reducing number of rounds of a block cipher - you get better performance by undermining security.


The function $e$ takes two values: $x$ and $H$, and then merges them in a specific way. Your "way" is just XORing them. That's insecure, as you can see. Normally you use a block cipher for the function, like AES-128 for an input of 128 bit.

Example: $$ H_i = H_{i-1} \oplus AES_{xi}(H_{i-1}) $$