Multiple signatures on one OpenPGP key. How are they combined? Where are they stored in OpenPGP certificate?

OpenPGP keys are formed by a whole bunch of individual OpenPGP packets, for example the public key itself, user IDs, and also certifications. RFC 4880, OpenPGP provides the specification and a list of possible packets together with their explanation (very technical indeed, but you're descending into the inner details of OpenPGP now).

When fetching a newer copy of the key from any source (let it be a local file import, from the key server network, from local files, ...), GnuPG or other implementations of OpenPGP just merge the individual packets together, adding those it didn't know yet. There is no artificial limit on the number of signatures or other packets, but the individual implementations are likely to have some technical ones (32 bit integers, addressable memory, ...).

You can look at a key's structure using gpg --list-packets or pgpdump. An example output for my own key with some explanations added, originally this is one large stream:

gpg --export a4ff2279 | gpg --list-packets | less

The public key:

# off=0 ctb=99 tag=6 hlen=3 plen=1037
:public key packet:
        version 4, algo 1, created 1356475387, expires 0
        pkey[0]: [8192 bits]
        pkey[1]: [17 bits]
        keyid: 4E1F799AA4FF2279

A user ID packet:

# off=1040 ctb=b4 tag=13 hlen=2 plen=49
:user ID packet: "Jens Erat (born 1988-01-19 in Stuttgart, Germany)"

Binding signature connecting key and user ID, and carrying configuration:

# off=1091 ctb=89 tag=2 hlen=3 plen=1083
:signature packet: algo 1, keyid 4E1F799AA4FF2279
        version 4, created 1356516623, md5len 0, sigclass 0x13
        digest algo 2, begin of digest 18 46
        hashed subpkt 27 len 1 (key flags: 03)
        hashed subpkt 11 len 5 (pref-sym-algos: 9 8 7 3 2)
        hashed subpkt 21 len 5 (pref-hash-algos: 8 2 9 10 11)
        hashed subpkt 22 len 3 (pref-zip-algos: 2 3 1)
        hashed subpkt 30 len 1 (features: 01)
        hashed subpkt 23 len 1 (keyserver preferences: 80)
        hashed subpkt 2 len 4 (sig created 2012-12-26)
        hashed subpkt 25 len 1 (primary user ID)
        subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
        data: [8189 bits]

A newer binding signature:

# off=2177 ctb=89 tag=2 hlen=3 plen=1080
:signature packet: algo 1, keyid 4E1F799AA4FF2279
        version 4, created 1356475387, md5len 0, sigclass 0x13
        digest algo 2, begin of digest 44 77
        hashed subpkt 2 len 4 (sig created 2012-12-25)
        hashed subpkt 27 len 1 (key flags: 03)
        hashed subpkt 11 len 5 (pref-sym-algos: 9 8 7 3 2)
        hashed subpkt 21 len 5 (pref-hash-algos: 8 2 9 10 11)
        hashed subpkt 22 len 3 (pref-zip-algos: 2 3 1)
        hashed subpkt 30 len 1 (features: 01)
        hashed subpkt 23 len 1 (keyserver preferences: 80)
        subpkt 16 len 8 (issuer key ID 4E1F799AA4FF2279)
        data: [8192 bits]
# off=3260 ctb=89 tag=2 hlen=3 plen=284

A certification issued by another key:

:signature packet: algo 1, keyid CBC2613CD745722B
        version 4, created 1356529414, md5len 0, sigclass 0x13
        digest algo 2, begin of digest d3 ec
        hashed subpkt 2 len 4 (sig created 2012-12-26)
        subpkt 16 len 8 (issuer key ID CBC2613CD745722B)
        data: [2048 bits]


Are there standards for transport layer security using only symmetric keys?

I know of two standard protocols that support AES encryption without public key cryptography getting involved:

With TLS, we have RFC4279, and in particular, the ciphersuite TLS_PSK_WITH_AES_128_CBC_SHA.  Now, the two sides don't literally have preconfigured AES keys; instead, they have preshared premaster secrets; the AES (and HMAC-SHA1) keys are derived from the premaster secret in the standard way.  No public key cryptography is involved.
With IPSec, we have RFC4301, and in particular, "manual keys" (which are exactly that, preconfigured symmetric keys)

If both work for you, I'd advise you to use the TLS option; it is probably more work (as you'll need to deal with the session setup messages); however, support for TLS is more command, and it does mean that the keys actually change over time (while with IPSec manual keys, the keys are fixed; if they are ever leaked, you are dead).

You could, of course, design your own protocol, however I'd strongly advise you to stick with protocols designed by people who knew what they are doing.


Strictly, is length(key) >= length(message) wrong for one time pads?

Your confusion stems from a misinterpretation of a formal statement about the limitations of perfect secrecy. Let us first recall the definition

Perfect Secrecy.
An encryption scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ with message space $\mathcal{M}$ is perfectly secret if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which $\Pr[C = c] > 0$:
$$Pr[M = m | C = c] = Pr[M = m].$$

Note that there is no mention of bits or bitstrings here and "length of the message" is not really well defined for a general message space.
The statement that is often informally paraphrased as

  The key must be at least as long as the message.

therefore doesn't really make any sense here. This is where you seem to be confused. The formal statement that can be proven about perfectly secret encryption schemes is the following:

Limitation of Perfect Secrecy.
If $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})$ is a perfectly secret encryption scheme with message space $\mathcal{M}$ and key space $\mathcal{K}$, then $|\mathcal{K}| \ge |\mathcal{M}|$.

Note that this is only a statement about the size of the key space! It makes no mention of any length.
Now, the most well known perfectly secret encryption scheme is the one-time pad, which is most commonly defined over bitstrings¹ with a message space $\mathcal{M}=\{0,1\}^n$ for some message length $n$ as well as a keyspace $\mathcal{M}=\{0,1\}^\ell$ for some key length $\ell$. In this specific case case $|\mathcal{K}| \ge |\mathcal{M}|$ indeed implies that $\ell \ge n$.

In your specific case however you used a different message space, in particular you defined $\mathcal{M}$ to be the set of "messages in the English language" which is something we would need to define more formally. We can define this for example as "any concatenation of words in the English language with total length at most $\ell$ characters".

In this case, clearly $|\mathcal{M}| < 2^{8\ell}$ and therefore obviously you do not need $|\mathcal{K}|\geq 2^{8\ell}$ but the definition never claimed otherwise. What you are defining here is simply not the one-time-pad, but a different encryption scheme with a different message space. And the same condition on the key space still holds. It is just that this does not necessarily correspond to an immediate lower bound on the length of the keys when encoded as bitstrings.

¹Technically the one-time pad can be defined over strings over any finite alphabet $\Sigma$ as long as we can define an order over $\Sigma$.


More efficient and just as secure to sign message hash using Ed25519?

Peter Schwabe, one of the authors of Ed25519, directed me to a recent paper titled "EdDSA for more curves".  The section "Security notes on prehashing", page 5, says that the Ed25519 algorithm without prehashing the message is resistant to collisions in the hash function, while using the algorithm with prehashing is not.  Of course the hash function is not supposed to have collisions, but if it does, not prehashing gives added protection.


Ed25519 PKCS8 private key example from IETF draft seems malformed

That example private key is not encoded with PKCS#8, but with the format described in RFC 5958, which is supposed to replace PKCS#8 (at least, in IETF parlance, RFC 5958 "obsoletes" RFC 5208, which is a copy of PKCS#8 v1.2). The ASN.1 type if called OneAsymmetricKey:

 OneAsymmetricKey ::= SEQUENCE {
   version                   Version,
   privateKeyAlgorithm       PrivateKeyAlgorithmIdentifier,
   privateKey                PrivateKey,
   attributes            [0] Attributes OPTIONAL,
   ...,
   [[2: publicKey        [1] PublicKey OPTIONAL ]],
   ...
 }

The structure is similar to that of PrivateKeyInfo in PKCS#8, but with the extra publicKey field (optional) at the end. Also note that the version field, which is an INTEGER, has value 0 for PKCS#8, but value 1 for OneAsymmetricKey; this is meant to allow some level of backward compatibility, in the sense that a decoder for OneSymmetricKey can accept an encoded PrivateKeyInfo, and will use the version field to apply the proper semantics (i.e. to decode the contents of the private key blob).

I must say that I have, so far, never encountered a OneSymmetricKey structure in the wild. The openssl command-line tool encodes keys in PKCS#8, and applications tend to expect that. RFC 5958 has status "proposed standard", but sometimes you cannot enforce acceptance.


Why is MixColumns omitted from the last round of AES?

Having taken The Design of Rijndael from the library just yesterday, I had a look on this problem, too. Fixee wrote in a comment:

  However, my question is not so much about security implications, but rather
  "how does omissions of MixColumns make the inverse cipher similar to the cipher?"
  and "how does this help in implementing the cipher?"

The encryption has these steps in each round (List 3.2, page 34), with an additional AddRoundKey at the beginning and a shorter round at the end:

Round(State, ExpandedKey[i]) {
    SubBytes(State);
    ShiftRows(State);
    MixColumns(State);
    AddRoundKey(State, ExpandedKey[i]);
}

The decryption looks this way, when done in a straightforward way (List 3.5, page 47) (with a shorter initial round):

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

As mentioned in a comment, without the omission of the one MixColumns step all 10 rounds would be identical (like the ones above), and we could do the total encryption and decryption as

AddRoundKey(ExpandedKey[0])
for i = 1 .. 10:
    Round(State, ExpandedKey[i])

for i = 10 .. 1:
    InvRound(State, ExpandedKey[i])
AddRoundKey(ExpandedKey[0])

If we move the AddRoundKey to the end of the inverse function, it would look like this:

InvRound'(State, ExpandedKey[i]) {
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
    AddRoundKey(State, ExpandedKey[i]);
}

AddRoundKey(ExpandedKey[10])
for i = 9 .. 0:
    InvRound'(State, ExpandedKey[i])

In this form, we would have a similar global structure of the encryption and function, but the round functions for encryption and decryption are still structurally different. We (as hypothetical re-inventors of Rijndael) can do better.

Back to our (naive) inverse round function:

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

By swapping InvMixColumns and AddRoundKey with a modified ExpandedKey) and also swapping InvShiftRows and InvSubBytes (as one of them works on each byte individually, and the other one just transposes whole bytes), we see this is  equivalent to this one:

InvRound(State, ExpandedKey[i]) {
    InvMixColumns(State);
    AddRoundKey(State, InvMixColumns(ExpandedKey[i]));
    InvSubBytes(State);
    InvShiftRows(State);
}

(We still have a shorter group at the beginning, and a final AddRoundKey at the end.)

Now by using a grouping that uses both InvMixColums and AddRoundKey at the end of the round, we will swap the positions of InvSubBytes with InvShiftRows and swap the positions of InvMixColumns with AddRoundKey to get this equivalent description instead (List 3.8, page 49), with again a shorter last round, and an initial AddRoundKey:

EqRound (State, EqExpandedKey[i]) {
    InvSubBytes(State);
    InvShiftRows(State);
    InvMixColumns(State);
    AddRoundKey(State, EqExpandedKey[i]);
}

But as it stands, this round structure, combined with the initial AddRoundKey, is not the inverse of the encryption. The last MixColumns of encryption has no corresponding InvMixColumns, and the last InvMixColumns of decryption has no corresponding MixColumns. We will solve this by omitting the MixColumns step from the last encryption round and the InvMixColums step from the last decryption round. With that change, since both encryption and decryption omit of the MixColumns / InvMixColumns step of the last round, their round structure remains the same and decryption is the inverse of encryption.

This combination of substitution, row-shifting and column-mixing (in this order) looks quite similar to the operation sequence for encrypting, and is now assumed to be more efficiently implemented than the inverse sequence used in the straightforward inversion.

Also, we can share some of the code (for software implementations) or chip area (for hardware implementations) for encryption and decryption.

Of course, we now need a tweak to the key schedule for decryption: apply InvMixColumns on each round key, other than the first and last. As the key schedule is only done once for many blocks, this is not a big overhead.

On 32-bit (or larger) processors with some fast cache (or ROM), one can implement this sequence of substitution, row-shifting and column-mixing (which is independent of any key) for each 32-bit column by looking up four 32-bit values (depending on different bytes in the old state) in four 1kB lookup tables and XORing these together. By using different rotations after the lookup, we can use just one of those tables (1 kB). (Details are in section 4.2, pages 58/59 in the book.)  A part of this table can be used for the final round, too (where there is no column mixing).

Here we can use the same code with different (sets of) tables for both decryption and encryption. (These tables don't change with different keys, so we put them in ROM, or calculate them when first needed.)

(These lookup tables open the way to timing attacks if they don't fit completely in the processor cache, and/or are removed from the cache by other programs running concurrently.)


ElGamal signature without calculating the inverse

Try switching $\alpha$ and $\gamma$ during the verify.

Fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then  $(\gamma, \delta)$  where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv kx-a\gamma \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \alpha^\delta \equiv \gamma^x \pmod{p}$$

Correctness:
$$\beta^\gamma \alpha^d = \alpha^{a\gamma+d} \text{ but } \gamma^x = \alpha^{kx} \text{ and } d = kx-a\gamma$$

Security: Seems a little iffy to move the known exponent onto an unknown generator, but forging a signature ($\delta$) for a given $\gamma$ still seems like a discrete log problem with base $\alpha$.  I don't know if there is a better way to choose $\gamma$ to make forging signatures easier though.

The definition of $\delta$ does not use $k$ (beyond $\gamma$) to mask the secret key $a$.  I think just using $\gamma$ is a bad idea, so I think this system is insecure, but I forget the attack.


Implementation of a decryption mixnet, and problems with the size of the key

With RSA and ECC you generally don't encrypt the actual message. When signing, you sign a hash of the message; and when encrypting you encrypt a symmetric-key that can be used to decrypt the message. The message itself is encrypted using either a block cipher, or a stream cipher, depending on what was chosen in the design. As such, with a block cipher, once the message is padded once it's already as long as it's gonna get, and with a stream cipher no padding is needed at all.
Also, it should be noted that ECC-based public-key algorithms operate a lot more like a block cipher than RSA does. With RSA you would need padding at every layer, but with ECC you only need to pad once.


Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0

You have shown a distinguisher for $F^1$ with high advantage that does not involve a distinguisher for $F$, so you can conclude there must be an error in your argument that that any distinguisher for $F^1$ implies a nearly-as-good distinguisher for $F$.

In particular, in equation $(*)$, you have confounded a uniform random function with the codomain of $F$ and a uniform random function with the codomain of $F^1$ by calling them both $f(\cdot)$.  It may be helpful to label the codomain sizes, or at least to call it $f$ vs. $f^1$, and clearly write out the distinction between the two and how your distinguisher acts on $f(x)\mathbin\| 0$, $f^1(x)$, and $F^1_k(x)$.


What is degree of randomness in individual bits of MD5 hash?

MD5 was designed with the goal that any change in the input uniformly affects all the bits of the output. It's not perfect, but it's pretty good. If you're choosing the input "randomly enough" (e.g., by appending random bits before hashing) then your question approaches this one:

  Given two randomly generated 8-bit strings, what is the probability
  that they match?

This is $\frac{1}{2^{8}}$.

References:

RFC 1321, Rivest's original description of the MD5 algorithm
How to Break MD5 and Other Hash Functions, by Wang and Yu
The same question
Again
Slightly differently
Yet again
And again


Solving the discrete logarithm problem for a weak group

The question is about making wonky DH parameters for which discrete logarithm is super-easy to solve. Thus, somebody suggests the following:

Let the modulus $p$ be the product of all small primes from $3$ to some value such that $p$ is adequately large. In this case, we consider the product of all primes from $3$ to $1471$; there are $232$ such primes, and their product is a $2046$-bit integer.

We now have a $y = g^x \bmod p$, for known values $y$ and $g$, and unknown $x$. The task at hand is to find $x$, or at least one value $x$ that matches the equation. There may be several (this is the common case; the algorithm below will usually find a much smaller solution than the original $x$). Crucially, we assume that there is a solution, i.e. that $y$ was obtained by choosing a (random) value $x$ and then computing the modular exponentiation.

Let's called $p_i$ the small primes. Let's define:
\begin{eqnarray}
  g_i &=& g \bmod p_i \\
  y_i &=& y \bmod p_i \\
\end{eqnarray}

The Chinese Remainder Theorem basically tells us that whatever happens modulo $p$ also happens modulo each of the small primes $p_i$, and back; said otherwise, if we can find a $x$ such that $g_i^x = y_i \bmod p_i$ for all $232$ values of $i$, then $x$ is a solution. Note that it is about using the same value $x$ modulo each prime $p_i$.

We now consider each small equation $g_i^x = y_i \bmod p_i$. There are two sub-cases:

$g_i = 0 \bmod p_i$. In that case, $y_i$ must be 0 \bmod $p_i$ (otherwise there would be no solution, and by definition we assume there is at least one); and any value $x$ works here.
$g_i$ is invertible modulo $p_i$ and has a definite multiplicative order $n_i$ which is a divisor of $\phi(p_i) = p_i - 1$. There again, since we assumed the existence of a solution, $y_i$ must be part of the group generated by $g_i$ modulo $p_i$. There is then exactly one value $x_i$ modulo $n_i$ that matches the equation. Since $p_i$ is small (our largest small prime $p_i$), the value $x_i$ can be obtained with the dumbest of brute force, i.e. trying values $0$, $1$, $2$... until $g_i^{x_i} = y_i \bmod p$ is satisfied.

Thus, we end up with a number of values $x_i$. We know that $x = x_i \bmod n_i$ (for all $i$ that match sub-case 2). By the magic of the CRT, this works both ways: if we find a value $x$ such that $x = x_i \bmod n_i$, then it will be a solution to $g^x = y \bmod p$.

Now, each $n_i$ is itself a product of small primes, which can easily be found (the largest $n_i$ is not greater than $1470$ since $n_i$ divides $\phi(p_i) = p_i - 1$). In general, we can write:
$$ n_i = \prod p_j^{a_{i,j}} $$
i.e. $n_i$ is a product of powers of small prime powers.

Let's look at these small primes. For each $p_j$, there will be one of the $n_i$ which maximizes $a_{i,j}$. In other words, we define:
$$ b_j = \max\{ a_{i,j} \} $$
We can then extract some information from the corresponding equation, i.e. we can define $d_j = x_i \bmod p_j^{b_j}$ for the value $x_i$ such that $n_i$ is a multiple of $p_j^{b_j}$ (there may be multiple matching $n_i$, but, by the assumption that there is a solution, they must all agree).

We now have a bunch of prime powers $p_j^{b_j}$, for distinct small primes $p_j$, and equations $x = d_j \bmod p_j^{b_j}$. Since we took care to maximize the $b_j$, the equations are sufficient: any $x$ that matches all of them will be a solution to the original DL problem. And since all the $p_j^{b_j}$ are prime to each other, the CRT applies without any further issue.

The tricky part in this description is that we have two distinct domains in which we use the CRT: one is modulo the small primes $p_i$, the other is in the exponents, which work modulo each order $n_i$. Note that the $n_i$ are not necessarily prime to each other, which is why we have to factorize them all and find the largest prime powers.

Less talk, more code! I wrote a C# implementation of the algorithm above. Main file is EasyDL.cs, that follows the steps above. It uses a generic big-integer implementation that I wrote previously, ZInt.cs. This is easily compiled on a Linux machine with Mono (install package mono-devel on a Ubuntu system):

mono-csc EasyDL.cs ZInt.cs

This produces EasyDL.exe, which can be executed with Mono:

mono EasyDL.exe

On a Windows machine, use the command-line compiler csc.exe, which is typically in C:\Windows\Microsoft.NET\Framework64\v4.0.30319\ (assuming a Windows 8+ machine in 64-bit mode; the code should work also with older .NET versions such as 3.5).

When executed, the program:

rebuilds the modulus $p$ as a product of small primes;
generates random $g$ and $x$, and computes $y = g^x \bmod p$;
applies the algorithm above to recompute a solution $s$ such that $y = g^s \bmod p$.

Values are printed out in hexadecimal.


Asymmetric Encryption - How is the Public Key Being Shared?

The key is shared via email, via scp/rsync/ssh-copy-id (remote copy), or by editing the settings of your account on a website. If you look in a web application that supports PKI, there will be an option under settings where you can upload your public key. Running an agent on your trusted OS machine (which has your private key) allows automatic verification via custom client software. It will understand you have an agent, then verify your local private key against the server's known public key.

The metaphor used is that of an empty box. You give a friend a padlock, but you keep the key. They put valuables in the box, and close the padlock you gave them on the box.  Now only you can open the box and get the valuables. The public key is the padlock. The private key is the key. Imagine that anyone can have the same padlock all over the world, but only you can open whatever they send you.


How to use a stream cipher to sign a message?

Many caveats: I'm not qualified to write this answer, but hopefully other folks can correct my mistakes. Outside of NaCl's crypto_box and crypto_secretbox constructions, there are a lot of ways to misuse a polynomial MAC. That might be why Thomas Ptacek specifically recommends against them. The standard way to sign a message using a symmetric key is HMAC, and this question seems like kind of an "assuming I'm forced to used a stream cipher instead of a hash for some reason" thought experiment.

That said.

Poly1305 is the authenticator in NaCl, and it's built with a stream cipher. First it feeds your message into a big polynomial, to give a checksum. The coefficients of the polynomial are derived from the bytes of your message, and the value of x in the polynomial comes from half of your secret key. Then it encrypts that checksum, using the other half of your secret key along with a nonce. The cipher for encrypting the checksum can be anything; it was AES in the original paper and it's XSalsa20 in the NaCl implementation. You need the cipher because the checksum by itself can leak the x that generated it.

One important difference between a polynomial MAC and a hash, is that it's easy to find collisions in the polynomial. If you know x you can find its multiplicative inverse, and then you can mix that into a message to control the exact checksum you end up with. A polynomial MAC doesn't uniquely determine its input like a good cryptographic hash does.

Another important difference is that the polynomial MAC relies on a unique nonce (for the cipher) to keep its key secret, which means nonce reuse is extra specially terrible.


Paillier Homomoprhic addition overflows after a certain value

The plaintext space for Paillier is integers modulo $n$. You are seeing "overflow" at the modulus, which makes sense. You should choose larger primes for both security reasons and to make it so that you can support larger numbers without the "overflow".


Why are inputs to boolean functions usually modelled as random variables?

A bit of clarity is needed here...
the Cook–Levin theorem
says that it is possible to translate each program into a boolean formula, so it is clear that the input of a program is almost never random.

I believe your question refers to binary satisfiability problems.
The formers are extremely important decision problems which are studied in the field of Theoretical Computer Science.
Example of such a problem:

Given an instance $\sigma$ of 3SAT (boolean formula in CNF with exactly 3 literals per clause) is there a distribution of variables such that $\sigma = 1$ ?
This decision problem is known to be NP-complete.

Why are they so important? well, for so many reasons that it is impossible to list all of them but the main ones are two:

circuit design/algorithm design:
Each Boolean formula corresponds to a circuit and to a Turing Machine (algorithm), so it is useful to know which formulas produce results and which ones are blind alleys (contradictions).
NP-completeness: KSAT (with $K \geq 3$) is known to be NP-complete,
which means that every other problem in the complexity class NP (nondeterministic polynomial time) can be reduced to an instance of SAT, therefore it is useful to have efficient algorithms for it.
Unfortunately, an efficient (polynomial time) algorithm is not yet known. Finding it would prove that P = NP and would guarantee the discoverer a million dollar.

Regarding cryptography, someone has proposed cryptographic methods based on sat
but, perhaps taken by enthusiasm, they had not thought that creating a public key based on an instance of SAT could be as expensive and intractable as validating the instance itself.


Diffie-Hellman key exchange using addition instead of multiplication?

Why can't we use $(Z_p,+)$?

In the DH key Exchange Alice and Bob agree on a common generator g which allow to share a common key. In fact in $(Z_p,+)$ every non zero element is a generator.

If a common generator g is preallably chosen, when Alice chose a secret a, transmitting A=g.a, the secret a will be immediatly disclosed by any one in the public channel by simply Computing $a=\frac{A}{g}$ and key exchange will be violated which isn't the case in $(Z_p,*)$, as the inversion by the discret logarithm, is considered hard.


What is the minimum message length to obtain the full potential of a hash?

First of all, the output sizes of SHA2 are 224, 256, 384 or 512-bit and of SHA3  are 224,256, 384, 512-bit.

Normally, hash functions are accepting arbitrary length inputs and producing fixed-length outputs. Hence, collisions are inevitable by the pigeonhole principle. We want them to have collision resistant in a way that even mathematically they exist, it must be hard to find one.

There are no known collisions for SHA2 and SHA3 series (but SHA-1 is shuttered).

If we limit the input size shorter than the output size, it is unlikely that we will find a collision. Consider 128-bit input size, the total inputs are $2^{128}$ and even for today technology, it is far to reach for search. The SHAs will map these $2^{128}$ different inputs into a much larger space as 224, or to 521-bit. Since we don't know how the values are distributed by these hash functions, we cannot prove it but we can say that it very likely that the values are distinct.

We can say similar arguments if the input size equal to output size.


Guarding against cryptanalytic breakthroughs: combining multiple hash functions

Combining is what SSL/TLS does with MD5 and SHA-1, in its definition of its internal "PRF" (which is actually a Key Derivation Function). For a given hash function, TLS defines a KDF which relies on HMAC which relies on the hash function. Then the KDF is invoked twice, once with MD5 and once with SHA-1, and the results are XORed together. The idea was to resist cryptanalytic breaks in either MD5 or SHA-1. Note that XORing the outputs of two hash functions relies on subtle assumptions. For instance, if I define $\mathrm{SHB-}256(m) = \mathrm{SHA-}256(m) \oplus C$, for a fixed constant $C$, then SHB-256 is as good a hash function as SHA-256; but the XOR of both always yields $C$, which is not good at all for hashing purposes. Hence, the construction in TLS in not really sanctioned by the authority of science (it just happens not to have been broken). TLS-1.2 does not use that combination anymore; it relies on the KDF with a single, configurable hash function, often SHA-256 (which is, in 2011, a smart choice).

As @PulpSpy points out, concatenation is not a good generic way of building hash functions. This was published by Joux in 2004 and then generalized by Hoch and Shamir in 2006, for a large class of construction involving iterations and concatenations. But mind the fine print: this is not really about surviving weaknesses in hash functions, but about getting your money worth. Namely, if you take a hash function with a 128-bit output and another with a 160-bit output, and concatenate the results, then collision resistance will be no worse than the strongest of the two; what Joux showed is that it will not be much better either. With $128+160 = 288$ bits of output, you could aim at $2^{144}$ resistance, but Joux's result implies that you will not go beyond about $2^{87}$.

So the question becomes: is there a way, if possible an efficient way, to combine two hash functions such that the result is as collision-resistant as the strongest of the two, but without incurring the output enlargement of concatenation ? In 2006, Boneh and Boyen have published a result which simply states that the answer is no, subject to the condition of evaluating each hash function only once.

Edit: Pietrzak lifted the latter condition in 2007 (i.e. invoking each hash function several times does not help).


Can I store the initialisation vector (IV) in the filename?

Yes, you can store the IV any way you want.  Putting it in the file name is no different from putting it in the file contents.

(Actually, there's nothing specific to cryptography here.  You could take any file you want and decide to move, say, the first $n$ bytes of its content into the file name.  It's all just data.)

That said, as SEJPM notes in the comments, to protect your data from tampering you really should use some form of authenticated encryption (either with a bespoke AE mode, or using the generic Encrypt-then-MAC construction), and you do need to include the IV in the authenticated data, no matter where it's stored.

The risk here is that, depending on the cipher mode used, tampering with the IV could allow an attacker to modify the plaintext in more or less predictable ways.  Even if decrypting with the wrong IV just produces gibberish, an attacker may be able to combine this with other attacks to learn something about the plaintext, especially if your code leaks information about the "gibberish" on decryption failure.  Using authenticated encryption protects you from this.

Also, a practical risk with storing data in the file name is that people are much more likely to rename files than to randomly tamper with their contents (especially if the contents just looks like random binary data).  Thus, using the file name to store critical data like the IV could lead to an increased risk of accidental data loss or corruption.


The assumption about gcd tell you that $2\alpha +1$ cannot belong to an ideal of $\mathbb{Z}/q\mathbb{Z}$. For example,  $2\alpha +1$ could divide $q$ and then $(2\alpha+1)t$ is never going to look like a uniformly random vector in $\mathbb{Z}_q^n$. If you want to fix ideas, assume $3$ divides $q$ and $\alpha =1$: then $(2\alpha+1)t$ always has its entries a multiple of $3$, which is absolutely not what a uniform vector would look like. The added contribution of $Ar$ may not be enough to "blur" the entries to a more uniformly random vector: it is likely that you could observe too many instances where $(2\alpha+1)t+Ar$ has entries a multiple of $3$.

In general, having this assumption make the proof easier (it might even not be possible to have a general proof without it) and relax the care on $\alpha$. It is also not very restrictive.


What does the running transcript hash in RFC-8446: TLS 1.3 do?

What's keeping a running transcript hash value ?

It means keeping the internal state of the hash in-between processing pieces of the message hashed. Virtually all hashes are designed to make this easy, for the benefit of devices with limited RAM. They can hash large messages piece by piece, with a three-function interface Start/Hash/Finalize allowing to repeat the Hash step as needed, passing a piece of the message at each call.
Such implementations of SHA-256 keep a state that comprises:

the hash so far (32 bytes)
the input buffer (64 bytes) holding 0 to 511 bits of input data not hashed yet
the length so far (8 bytes), which also encodes how much data was hashed (multiple of 512 bit) plus how much data is in the input buffer.

is it possible to calculate first a HMAC of first half of the message, delete the fist half of the message and calculate the final HMAC from the first HMAC and the remaining half of the message ?

Essentially yes, except that what's calculated first is not "a HMAC of first half of the message". Computing $\operatorname{HMAC}(K,(M_0\mathbin\|M_1),\ell)$ with $\operatorname{SHA-256}$ when $M_0$ and $M_1$ are available sequentially can go:

Check $0\le\ell\le64$ (the output length, here assumed in bytes)
if $K$ is more than 64 bytes, then $B\gets\operatorname{SHA-256}(K)$, else $B\gets K$
expand $B$ to 64 bytes by appending zeroes
$B\gets B\oplus\mathsf{3636\ldots3636_h}$ (the ipad constant, over 64 bytes)
Perform the first hash

Start
Hash $B$
Hash $M_0$
Hash $M_1$
Finalize the hash, yielding $H_1$

$B\gets B\oplus\mathsf{6A6A\ldots6A6A_h}$ (the XOR of the ipad and opad constants, over 64 bytes)
Perform the second hash

Start
Hash $B$
Hash $H_1$
Finalize the hash, yielding $H_2$

Truncate $H_2$ to length $\ell$ as needed to obtain the final result.

Between steps 3 and 4 of the first hash, it is needed a state of only about 168 bytes of data, including 104 bytes for the the hash state, and 64 bytes for $B$.
For SHA-512, we need to change the 64 to 128, and the RAM needed doubles.


What is Post-Compromise security exactly?

Post-compromise security secures future messages if the key for present messages is compromised. It repairs itself by using key update process. Key update process derives new key for future messages by using assymetric key exchange like DHE and chain of key derivation function.
If your present key is compromised by external sources, anytime when next DHE will happen, it will derive new key from that point. So the compromised key cannot be used to decrypt future messages. Whereas in key derivation chain, if it outputs separate key for each message, compromising one key will not compromise future keys but with a condition that the key that goes into the chain as input shouldn't be compromised because it acts as seed.
Based on how frequently DHE happens during the session, the attacker can compromise only subset of messages. But as DHE can itself be compromised by MITM, it only works in a condition if the attacker is passively listening the communication and relies on external sources to compromise keys.
Signal protocol does that by exchanging new key using DHE with every incoming message and derives new key for each message from symmetric ratchet.


Why are elliptic curves constructed using prime fields and not composite fields?

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{GF}(p^n)$, but they are constructed differently. For $n\ge2$, they are commonly called extension fields (as opposed to prime fields for $n=1$), as they can be viewed as extensions of $\mathbb{F}_p$.

There are examples of elliptic curves over extension fields. For example, every cryptographically secure curve in characteristic two is defined over a field of the form $\mathbb{F}_{2^m}$, i.e. a field with $2^m$ elements. There is also the Four$\mathbb{Q}$ curve, which is defined over $\mathbb{F}_{p^2}$ where $p=2^{127}-1$.

Doing things over extension fields can get a bit more tricky. There are attacks which can exploit the fact that $n\ge2$, which lead to faster algorithms for the discrete logarithm problem, on which elliptic-curve crypto is built. This gets complex pretty quickly, but some of it is explained in Galbraith's book (see $\S15.7$ and $\S15.8$). These attacks do not apply to every curve over an extension field, but show that you'll have to be more careful.


Instead of plain matrix, a matrix similar this (but bigger):

+a -h -g -f -e -d -c -b
+b +a -h -g -f -e -d -c
+c +b +a -h -g -f -e -d
+d +c +b +a -h -g -f -e
+e +d +c +b +a -h -g -f
+f +e +d +c +b +a -h -g
+g +f +e +d +c +b +a -h
+h +g +f +e +d +c +b +a

which one can deduce it's equivalant in addition and multiplication to a polynomial reduced by $X^8+1$. And here, the polynomial is the "Ring".

And instead of plain matrix of $n$ x $m$, we use a $1$ x $2$ matrix of polynomials.

Note: the arithmetical difference between matrix-represented polynomial rings and plain matrices, is that the former is commutative in multiplication, while the latter is not.


If Bob steals Alice's private key, how exactly would he read her encrypted documents?

GPG's (or OpenPGP's) public-key file encryption uses multiple steps:

Generate a random session key
encrypt the file using this random session key
encrypt the random session key using the public key of the receiver (or using multiple keys in parallel, if the file is meant to be decrypted by multiple receivers).
store the encrypted file together with the encrypted session key.

To decrypt it, the receiver (or attacker) needs the private key corresponding to (one of) the used public key(s).

Now, Alice should have protected her private keys with a passphrase - this way, Bob would get not the private key itself, only an encrypted version of it. If so, Bob's only way for decrypting the key (and thus the file) would be to guess the encryption passphrase (which can be possible if the passphrase is not that long/complicated).

If Alice didn't protect her private keys, Bob would get the private key, and could directly use it to decrypt the session key, and thus decrypt the file.


Is there any area where AES-CBC cannot be used ? If so, why?

CBC does not perform authentication

This property makes it less suitable for places where authentication is required, basically any transport protocol. TLS uses CBC, but by default performs authentication over the plain text instead of the ciphertext, which opened up a host of attacks. CBC can be used here, but it is error prone and may require an additional key for calculating a (H)MAC.

CBC is more error prone than other modes of encryption to error oracles, even if padding oracles (see below) are not feasible. See the paper "Error Oracle Attacks on CBC Mode" by Chris J. Mitchell for more information.

CBC doesn't let you pre-calculate a key stream

Pre-calculated key streams let you XOR plaintext with the pre-calculated stream to provide encryption. For instance AES-CTR makes it possible to let you use very low latency encryption for protocols.

CBC doesn't allow you to perform parallel encryption

As each block is depending on the previous block, all the way up to the last block, it is impossible to perform AES using multiple threads at the same time. This is a performance bottleneck which may invalidate AES-CBC on many systems where performance is required (and that do not have implicit parallelism).

CBC doesn't allow you to skip bytes

As each block is depending on the previous block, it is not possible to start encryption in the middle of a stream (decryption is possible though). This means that CBC is less suitable for re-encrypting parts of a file. Nor does this allow you to easily skip frames in e.g. video or audio play back.

CBC requires padding or ciphertext stealing (CTS)

Padding has many issues: it requires additional block encrypts and will require additional space. If CTS is available (it isn't usually) it requires at least one block, although the IV may be used as well if that is send to the other side. Regardless, CBC may have issues where a minimum number of bytes need to be send, or when a minimum number of block encrypts is required.

Besides that, CBC with padding applied may be vulnerable to padding oracle attacks. These may even be present on applications that are protected with a MAC if decryption is performed before authentication is established. This includes all transport protocols.

CBC requires an IV that is unpredictable to an attacker

This may be an issue where no fast random number generator is available and/or where additional block encrypt (to create an encrypted IV) is not feasible or wanted. This may be an issue on embedded platforms. As it is not directly possible to use a counter, CBC cannot be directly used on places where the IV can be derived from some identifier present in the protocol. It is also tricky to use an IV that is smaller than the block size.

CBC ciphertext errors do not propagate much forward nor do they travel backwards

This is not a feature that is requested a lot, but where it is, CBC does not provide it. Instead a mode such as bi-IGE (bi-directional Infinite Garble Extension) must be used.

Single bit errors in the ciphertext may affect up to 129 bits of plaintext

On the other hand, a single bit error in the ciphertext will garble the a complete block + a bit in the next block. This means that CBC is less suitable in places where error correction is calculated over the plaintext. CTR would be more suitable in such situations.

CBC may fail harder if you use a key too long

If you use a key for close to $2^{n/2}$ blocks, you expect a collision which leaks a block's worth of data. In contrast, CTR-based modes fail more gracefully: as long as you don't reuse a counter value, they only lose indistinguishability at that point.


How to prove that a SKE scheme is IND-CPA secure

A CPA on the second scheme is exactly the same thing as a CPA on the first one, provided that the attacker never calls the encryption oracle on a message which equals the key. But the latter can happen only with negligible probability, otherwise the first scheme would not be CPA-secure since it has the same key generation algorithm.

Thus, for any CPA attack against the second scheme, the exact same CPA attack will succeed with almost the same probability on the first scheme after accounting for the negligible possibility that the attack calls the encryption oracle on a message quich equals the key.


Why is a common reference string needed in zero knowledge proofs?

To complement a bit the answer of Occams_Trimmer: a CRS matters strongly for obtaining zero-knowledge proofs with a small number of rounds and for a large class of languages.

Without a CRS and without restriction on the number of rounds, as Occams_Trigger mentioned, we get the class CZK. This is a very large class: under the minimal assumption that one-way functions exist, it is actually equal to the huge class PSPACE. If we limit our attentions to zero-knowledge proofs with an efficient (polynomial time) prover, then it becomes equivalent to NP (i.e., essentially the class of all languages we care about).

However, without a CRS, it is much harder to get a small number of rounds: assuming only one-way functions, we need a superconstant number of rounds to get zero-knowledge proofs for NP. Assuming further the existence of collision-resistant hash functions, we can build five rounds zero-knowledge proofs for NP. This is essentially the best we can hope for: under black-box simulation, a 4-round zero-knowledge proof for NP would collapse the polynomial hierarchy (but there exists some candidate constructions based on exotic assumptions, such as knowledge-of-exponent assumptions or keyless multi-collision resistant hash functions, with non-black-box simulation). Even with non-black-box simulation, a 3-round ZK proof for NP would break indistinguishability obfuscation. Furthermore, 2-round ZK proofs can simply not exist for languages outside BPP.

In contrast, with a CRS, every language in NP has a non-interactive (1-round) zero-knowledge proof, under standard assumptions (e.g. factorization).


What is the general justification for the hardness of finding preimages for cryptographic hash functions?

The general justification is several years of cryptographic research in trying to "break" hash functions. As far as I know there is no "proof" that finding pre-images of a hash are hard. It is just assumed to be hard based on the history of effort trying to invert it.
A hash function considered secure today may well turn out to be weak tomorrow.

This paper (ONE-WAY FUNCTIONS AND CIRCUIT COMPLEXITY) might be of help in understanding the relationship between circuit complexity and one-way functions.


How can a Vigenère cipher be broken if the message is short?

If the message is shorter than the key, then the Vigenere cipher is essentially the one-time pad, which is unbreakable for a random key. If the key is not random, then you may get some information on the plaintext.


Annex E of X9.62-2005 says:

  Annex E provides the syntax for elliptic curve cryptography, including domain parameters, keys and signatures, according to Abstract Syntax Notation One (ASN.1). Although it is not required that elliptic curve domain parameters, keys, and signatures, be represented with ASN.1 syntax, if they are so represented, then their syntax shall be as defined here. Though it is likely that these ASN.1 definitions will be encoded using the Distinguished Encoding Rules (DER), other encoding rules may also be used.

RFC 3279, section 2.2.3 mandates use of ASN.1 to represent signatures, but, surprisingly, says nothing about encoding rules (whereas it explicitly requires DER for public keys).

Some cryptographic libraries insist on strict DER. Project Wycheproof contains some test vectors that check that (the reason which is given is: "to limit signature malleability"). OpenSSL is one such library: after decoding the incoming signature, it reencodes it with strict DER rules and checks that it obtains the exact same sequence of bytes. Apparently, this is due to a "vulnerability" known as CVE-2014-8275, where some systems implement blacklist on certificates by fingerprint, i.e. hash of the whole certificate (and not just the internal to-be-signed). In my opinion, blacklist systems do not offer good security and it was pretty daft to use the fingerprints for that, but apparently the OpenSSL developers thought that they needed to enforce strict DER encoding of both (EC)DSA signatures, and the outer layer of the certificate itself.

Other libraries accept variants. For instance, BearSSL requires the lengths to be explicit, but not necessarily minimal (i.e. some extra leading bytes of value 0x00 are accepted for the two INTEGER values).

From these data points, it seems that non-strict-DER encodings of signatures are nominally acceptable, as per the relevant standards, but they won't be accepted everywhere. Thus, in practice, any ECDSA library should ensure that the signatures it produces follow strict DER rules.


Understanding the linear cipher decryption process

First note the $\pmod{27}$ at the end, which tells us that all these equations are to be taken modulo $27$.

Also note that $4^{-1}$ literally means "the number $x$ such that $x\cdot4=1\pmod{27}$" (much like with the real numbers where $4^{-1}=\frac14$ with $4^{-1}\cdot 4=\frac14\cdot 4=1$).

Finally observe that $7\cdot 4=28\bmod 27=1$ and it follows that $7=4^{-1}\pmod{27}$.


How many bits to flip in an RSA public key to do signature forgery?

If Eve can find an $n'$ that is prime (and $n'-1$ is relatively prime to $e$),then she can easily sign any message with that $n', e$ pair.

So, the question is: what is the probability that there exists a prime $n'$ such that there is only one bit difference between $n$ and $n'$, and $n' \not\equiv 1 \pmod {e}$ ?  The answer is that it is quite good if $e > 3$, and decent even if $e = 3$. We'll assume $e$ is prime; in practice, it almost always is.

There are $log_2 n$ integers that have one bit difference from $n$ (we'll assume that Eve cannot flip bits that increase the size of $n$); flipping bit 0 will obviously yield a composite; flipping any other bit will yield an odd integer.  A "random" odd integer of size circa $n$ has a circa $2/{\log_e n}$ probability of prime; if we model each of the odd integers as "random", then we would expect around $(\log_2 n - 1) 2/{\log_e n} \approx. 2.89$ primes to be about one bit flip away from $n$; alternatively, there would a probability approximately $(1 - 2/{\log_e n}) ^ {\log_2 n - 1} \approx. 0.044$ that none of the values 1 bit away from $n$ happen to be prime.  When we include the condition with $e$, we know $n$ always satisifies the condition, and so a value with a bit flipped would have probability $1/(e-1)$ of satisfying it; from that, we can see that with $e=3$, we have an expected $1.44$ values satisfying it (hence we have a better than average chance); for $e>3$, the probability is even higher.

And, once we consider $n'$ values that aren't prime, but are easily factored (they're a large prime times a smooth number), the probability becomes much higher)


Secure Multiparty Sum in malicious model using threshold encryption

You are on the right track. However, as Ricky Demer points out in the comments, your suggestion would not work because the input is encrypted with different public keys. To fix this you need to use the properties of the threshold-encryption scheme.

In a threshold-encryption scheme the players run a key-generation protocol in order to generate a common public key $pk$, and a secret sharing of the secret key $sk$. This means that while all players hold $pk$ no single player holds $sk$. I.e., all players can encrypt but no one can decrypt without the help of the other players. In order to decrypt the players run a special decryption protocol.

So in other words your suggestion is almost correct, only the players do not hold different public encryption keys. To fix it you need to add an other step before step 1 where the players collaborate to generate keys. And in step 3 the players do not decrypt on their own. Instead they run a decryption protocol among each other.

This works because you only want to compute a sum (i.e., you are only doing additions). However, in general you could compute any arithmetic function. The only problem is that since you are using a additively homomorphic encryption scheme, doing multiplication is not as simple as addition. This is solved by running a special multiplication protocol among the players for every multiplication.

These days of course you could use a fully homomorphic threshold encryption scheme instead of a additively homomorphic one. In that case you would no longer need a special multiplication protocol. The reason why the authors of the paper you are linking to do not use a fully homomorphic scheme is simply that those were not invented when the paper was written.

This is just a rough description of course. For more detail I recommend you read the paper you linked to.


Lagrange Coefficients & Polynomial in KP-ABE

Short refresher on KP-ABE:

The Master Secret Key (MSK) and the Public Parameters (PP) are created during Setup and both enable the attribute authority to create Secret Keys (SK) for users using the Keygen algorithm.

Some user who possesses PP can Encrypt some data with a set of attributes $\gamma$. The encryption works by generating a new random secret $s$ and using that secret on all attributes in set $\gamma$.

$${E_i=T_i^s}_\gamma$$

The Keygen algorithm takes a policy (access tree) and MSK to create SK. The $y$ element from MSK is shared by using the policy into shares that represent the leaves of the access tree $q_x(0)$. This is very similar to Shamir's Secret Sharing. Those shares are used as

$$D_x=g^{\frac{q_x(0)}{t_i}}$$

where $q_x(0)$ and $t_i$ are both not easy to calculate due to the difficulty of discrete logarithm. Since the Lagrange interpolation is done in the exponent, as the polynomial interpolation on page 9 shows, it cannot reveal $y$. In the end we get $e(g,g)^{ys}$ where $y$ is still not easily computable due to discrete logarithm.

  I am assuming that the attributes are used to share the master secret key and only a user with the right attributes for a particular access tree is able to reconstruct the master secret key.

If the user would be able to reconstruct MSK from its own SK and the received CT, then it could create SKs for any attribute set and decrypt any CT with any policy. Of course, this is not the point of ABE. The MSK is the master secret key, because you can create any SK from it, so it must be kept secret at all cost by the attribute authority. This is also the main problem of ABE, because this is basically a key escrow service that, if broken into, undermines the complete security of the system.


The web of trust is no longer active. It was removed in GPG version 2.2.17.

The way it worked was that people would meet in person and sign each other's keys, then upload those keys and signatures to a network of "keyservers". Or maybe they'd just verify that email could be delivered to the other person. Or sign whatever they were asked to with no verification. In theory you could likely find some path of signatures back to a signature by someone you trust, thereby letting you establish a chain of authentication to believe that a key belonged to a given person, as long as everyone in the chain always actually did verification of all the keys they signed. In practice that was rarely done, people just trusted keys identity on first use.

Then in June 2016 the keyserver network was attacked in a way that fundamentally broke the whole thing. Anyone can add a signature attesting that a key in the keyserver is valid for the name it claims to be for. Anyone can add 150,000 such signatures. GPG breaks horribly whenever a key with more than about 150,000 signatures is used, or is anywhere in the chain of trust needed to verify another key. Someone signed a couple of popularly-used keys 150,000 times each, thus breaking GPG for everyone who was actually trying to use the Web of Trust.

So the Web of Trust was removed, the keyserver network is useless, and nobody really cares because no one really relied on it anyway.

And this is all without mentioning all the other massive vulnerabilities in the design and implementation of PGP/GPG, like its default to 1024-bit DSA keys with SHA-1 hashes (both broken), its common doomed attempts to encrypt email, lack of forward secrecy, use of RSA for encrypting, extremely complicated interface, long-lived identity keys, ease of creating colliding key fingerprints, etc, etc. It's a long, long list and not entirely on-topic to this answer.


Here is one possible way, that assumes:

C doesn't mind modifying how it signs data
C knows up front what part of the data is the hidden part
We don't mind if it isn't precisely zero knowledge, as long as we're at least as strong as the signature algorithm.

Then, here is how it works:

We'll assume ECDSA (or EdDSA); this assumption is mostly so we can reuse the same hard problem in our padding as in the signature, to make sure we're at least as strong as the signature.
We'll assume a hash function $F(m)$ which takes a message $m$, and converts it into an elliptic curve point; this function $F$ has the property that, for any two $m \ne m'$, the discrete log problem $nF(m) = F(m')$ is hard.
We'll assume another hash function $g(m)$ which takes a message $m$, and converts it into an integer between $1$ and $q-1$, where $q$ is the order of the Elliptic Curve.

To sign the message $(x, y)$ (where $x$ is the public part, and $y$ is the secret part, $C$ computes the elliptic curve point $(g(y))F( x )$, converts that into a bit string, and signs that.

For $A$ to prove that it knows $(x, y)$ that $sign( (g(y))F( x ) )$ is a signature to, it publishes:

$sign( (g(y))F( x ) )$
$(g(y))F( x )$
$x$
A zero knowledge proof that $A$ knows a solution to the discrete log problem $zF(x) = (g(y))F( x )$

$B$ then verifies that the signature is a valid signature to $(g(y))F( x )$; he then computes $F(x)$, and verifies that $A$ knows the value $z = g(y)$; he then concludes (because $F$ makes the discrete log problem hard) that $g(y)$ must be the value that $C$ originally used to sign, and hence $A$ must know $y$.


Is a PRG concatenation using the same input still a PRG?

Refering to THIS post

If we call $U_k$ the random variable uniformly distributed over bit strings of length $k$, then a function $g: \{0,1\}^k \to \{0,1\}^m$ is called pseudo-random generator if no feasible(poly-time if you want) algorithm can distinguish $g(U_k)$ and $U_m$ with non-negligible probability.

More formally let $U'_m = g(U_k)$ then the distinguishing advantage of any distinguisher efficient $D$ that we denote as $\Delta^D(U'_m, U_m) = \Pr^{DU_m}[Z = 1] - \Pr^{DU'_m}[Z = 1]$ is negligible.

Here $Z$ is the output of the distinguisher, and negligible is any suitable notion of "really small"; same for efficient.

Now my ability to distinguish between $U_k$ from your PRNG $g: \{0,1\}^k \to \{0,1\}^m \mathbin\| \{0,1\}^m$ is obviously more than negligible. Because any OUTPUT from your generator has symmetry and if I see this symmetry the generator being used is most probably your generator.


What is the correct way to choose the start parameters for NIST tests?

Yes, the NIST tests are a little opaque.  You'll find that the input file size should be (no. bitstreams) * (no. bits for testing).   That means the input file will be automatically partitioned into (no. bitstreams) fragments, and the test suite run that times.  Yo don't have to do anything.  That creates the output histogram and the final P value assessments. It's typical to pick 10 streams.

So an input file should be at least 1MB in size.  A good rule of thumb is 1 Byte * (no of bits for testing).  But you won't get any meaningful P values for RandomExcursions and RandomExcursionsVariant until you go to a 10MB input as in ./assess 1000000.  However, these two excursion tests don't generate P values until the input is >100MB.

Note1.  The above input sizes are for binary files as I find them easier to manipulate.  You can modify accordingly for ASCII representations. The tests work the same way.

Note2.  Given that you're being Pythonic, the generator is the Mersenne Twister.  It will pass with flying colours, even though academically it has some weaknesses in the very higher dimensions. If it doesn't, it's a code problem.


Why is Min-entropy significant in cryptography?

In most cases, cryptography requires values to be uniformly random (in which case discussions of min-entropy are moot) or unpredictable (in which case min-entropy isn't sufficient --- though "conditional" min-entropy might be --- since in these contexts an adversary typically has multiple guesses).

The context where I see min-entropy play the greatest role is in randomness extraction. Since physical sources of randomness rarely produce uniformly random bits, we need a way to transform the output of some physical system (presumably containing some amount of entropy, however measured) into a uniformly random bit string. At that point, we can start to do cryptography.

The Leftover Hash Lemma tells us how to take an input $X$ and transform it into a value $f_S(X) \in \{0, 1\}^n$ that is "close" to uniform. In particular, it tells us how to construct $f$ such that $n \leq H_{\infty}(X) - 2 \log(1/\epsilon)$, where $\epsilon$ is the statistical distance between the uniform distribution and $f_S(X)$ (technically, the distance between $(S, f_S(X))$ and $(S, U)$, where $U$ and $S$ are uniform and $S$ is implicitly a fixed, public value).

We're not making any assumptions on $X$ except for it's min-entropy. This quite nice because in practice we can't precisely characterize the distributions used to provide inputs to RNGs (which vary from device to device in the case of HW RNGs, and are not known a priori in the case of, e.g., /dev/urandom). Of course, estimating $H_{\infty}(X)$ is its own bag of worms...


Is AES S-Box resistant to side-channel attacks?

I assume the question is 'suppose you had an AES implementation that uses a precomputed SBOX table (and no other tables); can we do a key recovery attack using a timing or cache side channel?'
The answer to that question is "yes (at least potentially; we have to make some assumptions on the CPU hardware; at the very least, if it actually does have a cache)"
Here is a simple (and plausible) scenario where it is easy to recover some of the key bits (actually, we can recover them all, however that'd require more explanation)
Assume that we are on a CPU with 16-byte cache lines (that is, the cache stores things in 16 byte chunks; if the CPU reads in a location, the memory controller reads in all 16 bytes of that chunk).  We also assume that the sbox happens to be aligned at a 16-byte boundary (and so it occupies 16 cache lines) - actually, it'd be easier to exploit if it were misaligned; however for now, we'll assume aligned.
And, for our cached-based side channel, we can flush the cache, present a plaintext block, ask AES to encrypt it, and then check the cache to see which cache lines of the sbox were read in.  I'll cover the timing-based version of the attack below.
Here is how the attack would work: we flush the cache, and present a random plaintext, run it, and see which cache lines the sbox occupied.  The AES processing performs 160 sbox references (assuming AES-128); if we model each reference as random, then we have about a 1 in 2000 chance that there is some sbox cache line that is not referenced by any of the 160 reads.  Now, if (say) the cache line that corresponded to the 5X entries (that is, the sbox indicies with a high nybble of 5), then we can deduce that it was never refenced in the initial round; that is, for each byte $B_i$ of the plaintext and each key byte $K_i$, we have $B_i \oplus K_i \ne 5X$; that is, we can deduce what the high nibble of each key byte is not.
We can repeat this process until we've eliminated all possibilities for the high nybble of each key byte except for the correct one - this gives us half the key.  And, this would take maybe 30,000 or 50,000 probes (depending somewhat on whether we get to pick the plaintexts or have someone else generate random ones).  And, it's easy enough to recover the lower nybble as well (say, by relying on the second round sbox references); that would take more explanation.
As for how you would convert this into a timing attack (using the same base assumptions, except that the attacker cannot determine which cache lines are in the cache after the AES operation, but can measure the time), we can perform the same base attack, however before the AES operation, we set the cache so that 15 cache lines within the sbox are in the cache and 1 line is not, and then perform the AES operation.  If the 1 line is referenced, the CPU will read that line into the cache (which is an expensive operation; there's a reason CPU manufactures include a cache), and that would measurably increase the time.  By measuring the time, we can deduce whether that cache line was referenced, and hence we can proceed with the same attack (albeit with rather more probes required; we're getting data on whether a specific cache line was read, not data on all 16).


The RSA operation always produces an answer modulo the modulus.

Normally, we are careful to have a 'plaintext' which is smaller than the modulus, and hence the end result is the same.  After all, the fundamental identity for RSA is:

$$(M^d \bmod N)^ e \bmod N = M \bmod N$$

If $M < N$, then the right hand side simplifies to $M$

However, in this case, you have an initial input FEDCBA9876543210 which is actually larger than the modulus BE1EE24B5ACD9DE5.  When you do this, you end up with an end result which is FEDCBA9876543210 mod BE1EE24B5ACD9DE5 = 40BDD84D1B86942B

That answers the immediate question you asked; however as you dig further into RSA, you should be aware of the following:

When we use RSA, we (almost) never apply the RSA operation directly to the value given by the application (hash result, plaintext); instead, we apply a 'padding' operation first, to avoid potential attacks that exploit the homomorphic properties (and determinism in the case of encryption) that the raw RSA operation has
During the signature operation, we really can't call the RSA operation 'decryption' (as we're not actually decrypting something that has been previously encrypted).  Normally, it is called a 'signing' or 'signature generation'.


Here is one possibility, which answers the scenario you asked about, but feels too fragile for real use.

We'll have a trusted dealer, which selects an RSA modulus N (with secret factorization), a large exponent $e$, and two decryption exponents $d_1 = e^{-1} \bmod \lambda(N) + k_1 \lambda(N)$ and $d_2 = e^{-1} \bmod \lambda(N) + k_2 \lambda(N)$, for distinct integers $k_1, k_2$ (and $\lambda(N) = \text{lcm}(p-1, q-1)$)

Then, he encrypts the secret using RSA and exponent $e$; he then hands $d_1$ and $N$ to Alice, and $d_2$ and $N$ to Bob; they can both use these to decrypt the secret using RSA.

Just given $d_1$ or $d_2$ (and $N$), neither of them can recover the other; hence you have the traitor-tracing properties you're looking for.

Of course, if anyone learns two of $e, d_1, d_2$, they can factor (and so can derive their own $d$ values), hence the fragility of the system I mentioned.


Entropy of a random message chosen by an adversary from a subdomain

You did not define what the probability that $s_i = s^\prime$ for each $i$. Therefore entropy is undefined.

The definition of (Shannon) entropy is:

$$H = - \sum_{i} p_i \log_2 p_i$$

When you determine every non-zero probability $p_i$ then come back and enter those numbers into the formula.

Knowledge of $|S|$, the elements of $S$, or $\lambda$ is insufficient for calculation purposes. In different contexts (even if $S$ and $\lambda$ are the same), the probability of each message can follow a different distribution. The entropy depends only on what that distribution is. Therefore, the entropy of $s^\prime$ can be different depending on context.

Examples of the different contexts:

We care about the adversary's ability to guess $s^\prime$. This is trivial. The adversary picked the number. The adversary is certain what that number is. Certainty means one outcome has a probability of exactly one. The only non-zero $p$ is one. Entropy is zero because the log of one is zero.
A first party ("us") sends the set $S$ to a second party. The second party picks an element of that set. The first party wants to guess it before the adversary reveals it. The entropy can be at least zero bits and at most $\log_2 {|S|}$ bits. Exactly what value that entropy is depends on what the probability distribution is that describes which element the adversary picks.
The above scenario, except the first party tries to guess the number after the the second party reveals it to them. The entropy is zero. The first party is certain what that value is. $p = 1$
The first party chooses a set. A second party chooses an element of that set. A third party is supposed to guess what element was chosen with no knowledge of what choices the first or second party made. The entropy, $H$ satisfies, $0 \leq H \leq \log_2{|S|} \leq \log_2 (2^\lambda)$ The exact value depends both on the distribution of possible $S$ values the first party may choose and the distribution describing which element the second party may choose from any given set. See "joint entropy".


Wolfram alpha can do this:

http://www.wolframalpha.com/input/?i=multiplicative+inverse+of+65537+mod+265291078722948385056973898354378582740

yields

d = 240894030773496778838526583320400223673

The alternative is to write a small C program using gmp or using python, e.g.


What is the Knowledge Of Secret Key Assumption (KOSK)

According to the paper you link to in the comments:

  The security model makes the knowledge of
  secret key (KOSK) assumption. There is no dedicated key
  generation, but, when the adversary, mounting a rogue-key
  attack, provides a public key of its choice for a group member, it is required, in the model, to provide also a matching
  secret key. Of course “real” adversaries would not do any
  such thing, so what does this mean? It is explained by the
  authors as modeling the assumption that a user provides
  the certification authority (CA) with a proof of knowledge
  of its secret key before the CA certifies the corresponding
  public key.

What the above says is that the KOSK is not really an assumption in the cryptographic sense (like RSA, or discrete logarithm), but more like an hypothesis that is made about a specific security model. That is, KOSK is simply the hypothesis that when the adversary will mount an attack on the system, which is done by submitting some public key, he will also provide the matching secret key.

Now, let's explains why it matters here. Intuitively, there are situations in cryptography, such as this one, where we can prove that an attacker cannot break the security property of our scheme if he knows some specific piece of information, such as the secret key associated to the public key he submits. This might look strange at first, but it makes sense if you look at it the other way around: if the adversary is only allowed to submit public keys for which he knows the corresponding secret key, he is severely restricted in the type of attacks he can mount (e.g. he cannot provide a public key that he has stolen to some honest party, in an attempt to impersonate him).

Of course, there is a problem: in real life, no user will not provide the secret key together with the public key, that would completely break the system for them. The trick instead is to ask them to perform a zero-knowledge proof of knowledge (ZKPoK) of the secret key, which demonstrates that they know the secret key associated to the submitted public key, without leaking any further information.

Then, Bellare and Neuven go on with identifying the following problem: in real implementations of the protocol, this proof of knowledge is replaced by a signature, using the secret key as the signing key. Of course, intuitively being able to sign a document with the secret key shows that you know it. But it does not prove it, and that's all the issue. What does it mean to prove that an algorithm $A$ knows something? In cryptography, it means something very precise: it means that, given the code of $A$, it is possible to extract this value in polynomial time. This is possible by definition with a ZKPoK, but not with a signature. In the security analysis of the scheme, this extraction procedure is in general crucial: to show that the system is secure under some assumption, the security reduction will make use of the existence of an extractor that recovers this secret key, and use the extracted secret key in order to derive a contradiction to some security assumption from a successful adversary. If no such efficient extraction procedure exists, the security analysis breaks down.

Is this only a theoretical issue? This was probably the hope of the people who implemented the design. Arguably, it should be hard to mount an attack on a real-world system that uses signatures instead of ZKPoK, because a successful attack would require, at least, that the adversary somehow manages to find signatures on some documents without knowing the secret key. But can't he? Maybe the adversary can trick the real owner of the secret key into signing the document for him, mounting a man-in-the-middle attack. Or perhaps there is some more complex attack: I could easily design myself a (contrived) system which is provably secure using a ZKPoK, but which becomes completely insecure as soon as one replaces the ZKPoK bs a signature. The point is that without a security reduction, there is no way to be 100% sure that no such complete break exists.


A situation where security by obscurity might be the best solution - or am I wrong?

In summary: the premise "there is so little space in the bootloader that no cryptographically secure decryption algorithm can be implemented there" is likely wrong; thus security-by-obscurity is not the way to go.

The method described in the question attempts to "prevent theft from the publicly released update"; but it fails to do that if an adversary manage to extract the bootloader and include it verbatim in a clone of the hardware: the clone and bootloader will happily load the software updates, no matter what clever and effective security-by-obscurity is performed.

Thus, something secret is needed in the bootloader, else this (or any) technique is doomed to allowing clones of the hardware to run the software updates. Once you assume that, even only 10 bytes of secret data, you no longer need security-by-obscurity: you can use that secret data as a key to a block cipher in e.g. CBC mode, and release the software updates encrypted with that, and perhaps signed integrity-protected with a MAC. Complete decryption with an appropriate block cipher, such as TEA (which is designed to be compact and reasonably efficient), can be implemented within less than 200 bytes on about any micro-controller.

Unfortunately, it is hard to keep something secret in a standard micro-controller: all data, including secret keys, tends to be readable using widely available tools, such as a JTAG port. And when that won't do, side-channel attacks will typically succeed. The premise "the internal flash which is protected against reading" might be true, but protected does not imply safe.

For this reason, in the integrity-protection part (if desired), it is best to use a public-key signature scheme, which does not need a secret (but will only marginally help towards the goal in the question: it will not prevent use of the software on unauthorized hardware, only prevent use of modified software on authorized hardware or exact clone thereof). An RSA signature with public exponent $e=3$ together with a proper padding scheme based on a hash can be implemented in say 800 bytes including 2048-bit public key (which will use less than 128 bytes; that's not a typo), and run at acceptable speed (run time is typically dominated by the hashing).

You are unlikely to get support for security-by-obscurity here: we officially believe in Kerckhoffs's principles. I would only condone security-by-obscurity as a second line of defense.


How does ECDSA signature verify work in EOS and ETH/BTC, compare to standard (on text book I mean)

The two questions are somehow related. The answer to your question (2) is no. In BTC/ETH, signature verification is like the first method you mentioned: the verifier extracts the public key from the signature, hash it, and compare the results to the address where the coin comes. If so, the signature is valid.

The main reason why this is used instead of the normal ECDSA verification is that when you verify a signature, you don't have the public key, but only an address that is the hash of the public key. Therefore you cannot verify using the normal procedure. The key recovery procedure is another way to verify signatures without much security loss.

Edit to add: The signature is generated using the normal ECDSA signature algorithm. Recovering the public key from a signature is a well-known trick. For example, it is documented in Section 4.1.6 of SEC 1. See also one of the answers for this question for a better explanation. Note it is possible to recover two candidate public keys from a signature, but as I said, this is not going to result in much security loss. See the discussion here.

Now for the "check authorization" part, a transaction in EOS may require authorization from one or more accounts. So the system verifies that the transaction has been signed by all of the necessary signatures to grant the specified authorization.

Then for the block signature verification, in EOS, there are only 21 producers that can generate blocks. Each producer has a producer key. This is the key for signing blocks and identifying themselves. This key cannot sign transactions on EOS, it can only sign blocks. Therefore it cannot transfer or claim EOS. The producer public key is known by parties who verify blocks, thus the normal ECDSA verification is used.


Can I use a deterministic NONCE for AES-GCM file encryption if I generate "fresh" keys for each encrypted file

Yes, you can set the IV to zero if you use a different key each time. You speak about a random key, but is the key truly random, even in time? What happens if a file is changed, what attack vectors would surface in such a case?

Using a 32 bit random "fixed" integer is not a good idea. You'd quickly produce collisions even for a relatively small amount of files stored with the same key. So whatever you try to fix with that, it won't be fixed enough to be called secure in a cryptographic sense.

If you worry about the keys not being random, I'd add some startup tests for the random number generator instead. Because without a trusted random number generator a lot of operations are not going to be secure.


What does the term “nontrivial rotation” mean?

A trivial rotation is one where the input to the rotation is equal to the output (hence the rotation is equal to the identity function). Rotating by a multiple of $n$ is a trivial rotation for all $n$ bit values. Note that for certain values other trivial rotations may exist. See below for the values of the (right) rotations of 0x9e3779b9 ($n = 32$) and the amount of different bits for each:

0:  0x9e3779b9 (0  bits different)
1:  0xcf1bbcdc (14 bits different)
2:  0x678dde6e (22 bits different)
3:  0x33c6ef37 (18 bits different)
4:  0x99e3779b (12 bits different)
5:  0xccf1bbcd (14 bits different)
6:  0xe678dde6 (18 bits different)
7:  0x733c6ef3 (16 bits different)
8:  0xb99e3779 (14 bits different)
9:  0xdccf1bbc (12 bits different)
10: 0x6e678dde (16 bits different)
11: 0x3733c6ef (16 bits different)
12: 0x9b99e377 (16 bits different)
13: 0xcdccf1bb (14 bits different)
14: 0xe6e678dd (12 bits different)
15: 0xf3733c6e (16 bits different)
16: 0x79b99e37 (20 bits different)
17: 0xbcdccf1b (16 bits different)
18: 0xde6e678d (12 bits different)
19: 0xef3733c6 (14 bits different)
20: 0x779b99e3 (16 bits different)
21: 0xbbcdccf1 (16 bits different)
22: 0xdde6e678 (16 bits different)
23: 0x6ef3733c (12 bits different)
24: 0x3779b99e (14 bits different)
25: 0x1bbcdccf (16 bits different)
26: 0x8dde6e67 (18 bits different)
27: 0xc6ef3733 (14 bits different)
28: 0xe3779b99 (12 bits different)
29: 0xf1bbcdcc (18 bits different)
30: 0x78dde6e6 (22 bits different)
31: 0x3c6ef373 (14 bits different)


Can you help me understand pairing $e:G \times G \to G_T$ and ( Decision) BDH assumption?

An attack against the signature scheme over some group where DDH is easy, can be turned into a solver for the CDH problem over the same group, as is shown in Section 2.3 in the Asiacrypt paper you refer to.

So what you are really asking is: In what groups where DDH is easy is CDH still hard?

I would not use elliptic curves over extension fields of low characteristic. Using ordinary elliptic curves over prime fields with a relatively small embedding degree seems ok.


Zero knowledge proof for Paillier addition under multiple keys

As far as I know, with the same public key $(g,n)$
I would change the problem to prove that if
$e_0 = E(m_1,r_1)\cdot E(m_2,r_2)$
then $m_0 = D(e_0) = m_1 + m_2 \bmod n$ where $D(e_0)$ is the result of decrypting ciphertext $e_0$. Thanks Geoffroy for your helpful comment and LaTeX conversion regarding my incorrect guess on the use of html here. .


Williams' $p+1$ in tandem with Pollard's $p-1$?

These attacks are not relevant today because ECM, QS, and NFS are more cost-effective at modulus sizes providing serious security, which these days must be well above 1024 bits, preferably at least 2048 bits.

See past questions [1], [2] for more background on these criteria in historical RSA key generation recommendations, which these days are obsolete since the development of ECM, QS, and NFS.


How to exchange a secret through untrusted server in two steps?

Without changing an assumption somewhere, it does not look possible.

Here is what your ideal protocol would look like:

Alice sends the invitation to the server (to pass along to Bob), along with a message that is encrypted somehow, but not bound to Bob (as Alice doesn't have anything from Bob to distinguish him from anyone else)
Bob gets the invitation, and the encrypted message, and somehow (without any further interaction from Alice) decrypts the message

The problem is with step two; if Bob can decrypt the message, why can't anyone else (in particular, why can't the server)?  The server knows everything that Alice knows about Bob, and so the server can perform the decryption operation just as well as Bob can.

Now, a similar problem lies in the original protocol; when Alice downloads Bob's public key, the server could provide his own (and when Alice uploads the encrypted message, the server decrypts it, and reencrypts it with Bob's public key).  You did say that the 'untrusted' server can be trusted not to do this.

Obvious ways to address this:

Change the trust assumption; you already trust the server to be honest about public keys; also trust the server not to be malicious about reading intermediate mail (and with this assumption; Alice can encrypt the message with the server's public key, and have the server reencrypt it with Bob's when he downloads it).
Give Alice something from Bob (even a symmetric key) that the server doesn't know.


Is CRC32 birthday attack independent of input?

The purpose of the checksum is to detect a change of the configuration (e.g. change of serial number by constant device type). In the case of the serial number only single bits can change.

Actually, the birthday problem does not really apply to CRC; CRC doesn't act like a random function.

For your purposes, it acts better than a random function.  CRC-32 has the property that, if a change you make is limited to 4 consecutive bytes, the resulting CRC will always change.

Hence, if the only change in the configuration is a change to a single 4 byte serial number (and everything else is the same), then CRC-32 will always detect the change (and this remains true even if you change more than one bit of the serial number).

Of course, if additional things change within the configuration (e.g. if two serial numbers are changed), then this need not be true.


Chance of finding the right key by exhaustively searching on half of the key space

Schneier is talking about distinguishing a block cipher from an ideal cipher - or in other words, about formal definitions for security.  Think of a game, where the attacker is given a ciphertext encrypted either with a block cipher or with an ideal cipher (with equal probability), and has to guess which cipher encrypted the message.

Let's say this attacker tries 50% of the block cipher key-space, and if any key correctly decrypts the message then it guesses that the cipher that encrypted the message was the block cipher.  But if no key correctly decrypts the message then the attacker guesses that the ideal cipher was used.

There's a 50% chance that the cipher used was in fact the ideal cipher.  In that scenario, the attacker will always correctly guess that the ideal cipher was used - so it has a 50% chance of being correct along that branch of the probability tree.

There's also a 50% chance that the cipher was in fact the block cipher, and in that scenario there are two possible outcomes - either the key was among those that the attacker tried (in which case it will correctly guess that the block cipher was used), or the key was not among those that the attacker tried (in which case the attacker will incorrectly guess that the ideal cipher was used).  Since the attacker tries half the key-space, that means the attacker has a 50% chance of guessing correctly (given that the block cipher was used).  So the total contribution of this branch of the probability tree is 50% (odds that block cipher is used) * 50% (odds that key is among those tested) = 25%.

So the total probability of the attacker making a correct guess is 50% + (50%*50%) = 75%.


What's the difference between perfect security and unconditional security?

According to the references, both perfect security and unconditional security consider adversaries that have unlimited computational power, i.e., information-theoretic security. I think the only difference is that unconditional security allows for negligible failure while perfect security requires zero failure.


Can you explain what an NP statement is when they refer to it in Zero knowledge proofs?

Intuitively, an NP problem is one
 that if you have a solution it is computationally easy to verify it, but it is not known if it is also computationally easy to find. Of course there exist formal definitions, based on deterministic and non deterministic Turing machines. Any standard complexity textbook will have these definitions.

Their connection with zero knowledge proofs comes from the 1987, Goldreich, Micali and Wigderson paper that proves that all NP problems have zero knowledge proofs (assuming secure bit commitment).
An excellent tutorial on how this is done can be found in Matthew Green's blog.
All this were written for classical zero knowledge systems, but they apply to zkSnarks as well.


If attacker knows salt and hash, how is salt effective?

The resume of that other answer could be:

When you have a password hashed, it's hard (very hard) to find out what was the original password: you have to try all combinations, until you find the hash. That's brute-force.

Someone can speed up a bit this process, by pre-computing many passwords: he'll store all those passwords / hashes, and will try to find it when he needs.

Someone can also see that two hashes are the same, and then he'll know that both passwords are the same.

To avoid these weakness, you use salt: it's a not-secret value, unique to each login/password pair. That way, the 1st problem (pre-computed hashes) won't work anymore, because he should have generated those pre-computed tables (called rainbow tables) including the salt.

The 2nd problem is also addressed: since each login will have it's salt, even if the same password was used, the hash will be different, since (salt1 + password) is different from (salt2 + password).

And there is also some marginal benefit: the password ends up being longer, since it'll have the salt + password. Of course, it's not any help if you think that the salt isn't secret and the password will be brute-forced. The attacker will simply compute all the combinations appending the salt. But it's a benefit if you think that the salt, alone, has 8 characters (for example): then any pre-computed table with 8 or less characters is useless, because (salt + password) will be longer than 8 characters.


Can I decrypt the message having it encrypted with different keys?

If the keys are at least as long as the data (which is confirmed in the comments), and the keys are chosen randomly and independent of each other, no there is no way to get the data. Even if you had infinitely many encryptions.

This is because this type of encryption, called the one time pad, is perfectly secure.


Ephemeral Diffie-Hellman generator selection

I'm not aware of any attack made much easier by using a small generator in EDH, like $g=3$ or $g=5$, even $g=2$ (but I'm not accustomed to GNFS or index calculus), as long as there is a single $g$ used for a given instance of other parameter(s). These generators are common, and (especially $g=2$) allow a modest but sizable performance improvement.

I would give a reference to the desired library, if I knew one. However it is not rocket science to implement for straight EDH, when the desired criteria is known. If we want a random huge $p$ and a generator $g$ among a small list of small $g>1$ such that $g$ is a generator of the group $\mathbb Z_p^*$ where the Discrete Log is hard, one possibility is to generate a random prime $p$ of the desired size until $(p-1)/2$ is also prime, and for one of the desired $g$ we have $g^{(p-1)/2}\bmod p\ne1$ (notice that $g^{p-1}\bmod p=1$ holds since $p$ is prime, and $g^2\bmod p\ne1$ holds since $g\ll\sqrt p$).

There a many other criteria in use, such as those set by RFC 2412, used by IKE as defined by RFC 2409, where in addition to $p$ and $(p-1)/2$ prime, it is wanted:

$g=2$ and $g^{(p-1)/2}\bmod p=1$ (rather than $\ne1$), for reasons explained by poncho;
a number of top and bottom bits of $p$ are forced to 1, in order to simplify modular reduction both by classical and Montgomery arithmetic;
the random-looking center bits of $p$ are traceable to a nothing up my sleeves number.

Another common set of criteria it that for DSA, as specified by FIPS 186-4, appendix A (also good for the Finite Field Cryptography scheme of NIST SP 800-56Ar2 and ancestors, which use DSA public key certificates in order to resist MITM). That requires more complex parameter selection; in particular, a subgroup of prime order $q$ much smaller than $p$. While still not rocket science, that parameters generation process is more involved, and constrained by the standards.


Equivalent RSA modulus for NIST P-192 and P-521 elliptic curves

Security strength of RSA in relation with the modulus size outlines the formula that is used for the strength of an RSA key (as a function of the size of the modulus).

For ECC it's a simpler "the prime field size / 2".

So ECC-192 => 96 bits of security.  $\sqrt[0.43]{96 / 4}$ = $\sqrt[0.43]{24}$ = $1621$, with $1624$ being the next highest number divisible by 8.

ECC-521 => 260.5 bits of security.  $\sqrt[0.43]{260.5 / 4}$ = $\sqrt[0.43]{65.125}$ = $16520.3$, making $16528$ the equivalent, which is beyond most systems' maximum of 16384.


Additive ElGamal cryptosystem using a finite field

As far as I can tell from your description, the modulus is $p$. To multiply two group elements, you compute $xy \mod p$; because the generator $g$ you choose has period $q$ it'll all work out fine.
No, $p$, $q$, and $g$ can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete logarithms rather than factoring.
Yes.
and 5. The Ecrypt report on algorithms and key sizes http://www.ecrypt.eu.org/documents.html is a good place to look. It's not an easy question because it depends on how hard you think it is (and will be in the future) to solve discrete logarithms.

There's an existing, open-source implementation of additive ElGamal (in Python) used in the Helios voting system (http://heliosvoting.org) that you might want to look at.


Diffie-Hellman using a different modulus on both sides

I see you use the same generator on both sides (this need not work for any $n_1, n_2$ of course...). But even if this holds (trying a small example):

Let 1 use $n_1 = 11, M=2$, and 2 uses $n_2 = 13, M= 2$. Check that $2$ is a generator for both of the multiplicative groups.

If $d_1 = 7, d_2 = 9$, then $A = 2^7 \bmod 11 = 7$, while $B = 2^9 \bmod 13 = 5$.

But $5^7 \bmod 11 = 3$ which does not equal $7^9 \bmod 13 = 8$.


ECDH, x25519 and limitations for securing client-certificates on the server

For x25519, can multiple PK's resolve to a single SK, or is there ever only one unique PK-SK pair?

If I wasn't mistaken, there can be atmost 2 PK corresponding to 1 SK in x25519, depending on whether the implicit y-coordinate is internally positive or negative. As for ECDH on the other hand, the mapping is 1:1.

  I'm wondering whether it's rational to think of x25519 public-keys as holding an "almost" equal share in securing information? By "almost" equal, I mean that I can always derive the PK from the SK.

From the way you explain your question, I assume you mean whether the PK and SK are equally essential: yes, the only thing to be noted is that their role is different.

(In the previous form of the question, answerers may confuse your question as asking whether the PK of both parties are equally important).

  If I didn't have the PK or the SK, would I be able to produce a message that matched an SK at better probability than a brute-force guess across (half?) the x25519 key-space?

Do you mean forging a ciphertext that can be decrypted with an SK without knowing its corresponding PK? This type of attack is known as existential forgery - a term usually applied to digital signatures and message authentication codes.

In existential forgery, the attacker produces a message that can be correctly verified (in your case, successfully decrypted) with a key that's possibly unknown. See What do the signature security abbreviations like EUF-CMA mean? and Easy explanation of "IND-" security notions? for further explanation.

  .. is there a greater probability that I can encrypt a message for an unknown SK, than I would otherwise have being able to determine the SK from the PK (if I had the PK).

For elliptic curve key exchange and encryptions, this isn't likely, as the key-recovery complexity and forgery complexity are essentially equal.


What are the minimum constraints on RSA parameters and why?

One does not need  e < n .

One does not need $\;\; e\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \: \equiv \: 1 \;\; \pmod{\phi(n)} \;\;\;\;\;$;

one just needs that congruence modulo λ(n).

(Being coprime with $\phi$(n) is equivalent to being coprime with λ(n).)

Neither the plaintext nor the ciphertext need to be coprime with n.

gcd(m,n) must be coprime with n/(gcd(m,n)).

That last condition will be automatic when n is square-free, since it's equivalent to

"If m≠0 then for every prime factor p of n, p's multiplicity as a

factor of m is either 0 or equal to p's multiplicity as a factor n.".

When the quote holds, for each maximal-prime-power factor q of n,

m's remainder mod q will be either 0 or a coprime to q.

When the former case applies, it will continue applying to all positive powers of m.

When the latter case applies:

By Fermat's Little Theorem, $\;\;\; m^{\hspace{.02 in}\phi(q)} \equiv 1 \: \pmod{q} \:\:\:\:$.

For all non-negative integers k,

$m^{(k\cdot \phi(q))\hspace{.02 in}+1} \: \equiv \: m^{\hspace{.02 in}k\cdot \phi(q)} \cdot m^1 \: = \: m^{\hspace{.02 in}\phi(q) \cdot k} \cdot m \: =$

$\left(\hspace{-0.03 in}m^{\hspace{.02 in}\phi(q)}\hspace{-0.06 in}\right)^k \cdot m \: \equiv \: 1^k \cdot m \: = \: 1\cdot m \: = \: m \;\;\; \pmod{q} \;\;\;\;\;\;\;\;$.

λ(n) is a positive integers multiple of $\phi$(q), so for all

non-negative integers $k$, $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q} \:\:\:\:$.

Thus, when the quote holds, one will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{q}$

for each maximal-prime-power factor q of n and each non-negative integer k.

Therefore, by the Chinese Remainder Theorem, when the quote holds one

will have $\;\;\; m^{(k\cdot \lambda(n))\hspace{.02 in}+1} \equiv m \: \pmod{n} \;\;\;$ for all non-negative integers k.


That's actually a typo, you'd use your private key, not your public key, to establish the secret used for ECIES. File a bug report on the documentation!


HMAC is sometimes called a keyed hash. The key is not part of the input of a secure hash (as CodesInChaos already indicated in the comments). HMAC is a relatively simple construct to allow a key to be used as input to the underlying secure hash. It specifically is constructed to disallow length extension attacks - although those are not likely an issue in PBKDF2.

You could use If you'd use SHA-256 directly you would have to make sure you're not vulnerable against those kind of attacks. You would basically be without the security proofs of HMAC.

KDF1 and KDF2 are KDFs/PRFs that simply concatenate elements in a certain way before entering the result into the hash. SHA-3/KMAC will (largely) be a concatenation of key and message before hashing. So it certainly can be done that way.

You should however reverse your question: Why wouldn't you use a secure PRF instead of directly using a hash?.

HMAC is relatively efficient. Inn PBKDF2 (which requires a work factor / iteration count) the small inefficiencies may actually be a benefit (a good implementation should however store the intermediate hash value of the password, otherwise an attacker may have an advantage).

Furthermore, HMAC is still considered secure, even if the underlying hash is vulnerable to certain kind of attacks (such as those against MD5 and SHA-1).

For the SHA-1 and SHA-2 algorithms I'd advice you to keep to HMAC unless you've got very strong (performance related?) reasons not to.