Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor.

Not all binary fields are affected equally, however. Both Göloğlu et al and Joux's approaches descend from the medium-prime function field sieve, and require the field $\mathbb{F}_{2^N}$ to be representable as (among others):

$\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k' \cdot d_1}$, $d_1, k'$ constant  (Göloğlu et al);
$\mathbb{F}_{q^n}$, where $q = 2^l$ and $n = 2^{l/k'} - 1$, $k'$ constant  (Göloğlu et al);
$\mathbb{F}_{q^{2n}}$, where $q = 2^{l}$ and $n \le q + \delta,\, \delta \ll q$ (Joux).

When the exponent of the binary field is smooth, we get many choices to try and represent the field in the forms above. Example: $1778 = 7 \cdot (2 \cdot 127)$; $6120 = 24 \cdot (2^{24/3} - 1)$; $6168 = 257\cdot (2\cdot 12)$; etc. When the exponent is prime, however, we have no such luck.

Instead, as Joux suggested, one may embed the target field within a larger field that does: $\mathbb{F}_{q^{2N}}$, where $q = 2^{\lceil \log_2 N \rceil}$. While this solution may be asymptotically satisfactory, the blow up in size increases the bitlength where Joux's algorithm is faster than the regular function field sieve. It is currently unknown what this size may be, but it is likely that is is higher than current common key sizes (1024-4096 bits).

As for actual uses of binary fields, I do not know of any real-world usage of schemes based on the DLP over binary fields (beyond pairings). We have long been avoiding composite degree binary fields for elliptic curves due to their increased susceptibility to index-calculus; it seems that finite fields are now forced to do the same.


Is HMAC necessary if the AES ciphertext of a message includes the CRC of the message?

In crypto, we like designs that are secure in (most) all use cases. There is a use case of your proposal that is trivially insecure.

Consider the AES cipher run in a stream-like mode (e.g., CTR). Due to linearity of CRC (i.e., $CRC(X\oplus Y\oplus Z)=CRC(X)\oplus CRC(Y)\oplus CRC(Z)$ and the malleability property of stream ciphers, it is very easy to modify the plaintext and then change the CRC so that it will still be correct.

I don't know if non-stream-like modes (e.g., CBC) have issues with your proposed design, but the fact that some modes do should steer people away from it.

So where we are is, the proposal is shown to be trivially insecure for a number of modes. I don't know if it is secure for certain other modes or constructions. So, yes, HMAC (or some other MAC) is necessary even though a CRC of the data is encrypted. In other words, CRC (even though it is encrypted) is not a good MAC.

P.S. you may find this question interesting.


KRACK - Is all-zero key installed by the acces point?

No, only one side installs the all-zero key. Which side depends on the mode being attacked (the client in standard 4WHS, the server in FT). Generally, the KRACK attack allows the adversary to replay, decrypt, or forge packets in a specific communication direction.

Let's focus on the standard 4WHS here, as that corresponds to the case of your question.
Here, the client will install the all-zero key, while the AP will install the correct (and unknown to the adversary) encryption key derived from the 4WHS.
Thus, the adversary will be able to decrypt messages going from the client to the AP, but not the other way around. It will also be able to replay and forge messages towards the client (but not the AP).


Symmetric key pair on app and low power device

It seems you are mistaking the block cipher AES to be a secure transport protocol.

To provide transport security a secure transport protocol is required. In those protocols the session keys are usually distributed using either encryption with the help of a (trusted) asymmetric key pair or by a key agreement primitives. Together with symmetric message encryption this makes up a hybrid cryptosystem.

For embedded devices usually ECDSA and ephemeral ECDH are used as underlying primtives. Note that in general transport security also requires message authentication.

If you are just looking for a method of securely sharing symmetric keys then you can secure one master key at the server and distribute derived keys to the clients. The master can always perform KDF(master_key, client_id) to derive the keys again. HKDF is probably the best known key based KDF right now.

I'd recommend a careful study of TLS and DTLS before proceeding.


This is something I tend to disagree somewhat with Colin Percival on.

You should use Encrypt-then-HMAC if and only if you can get it right. The biggest pitfall is using a short-circuiting string comparison versus a constant-time string comparison. Given the former, people can use timing attacks to forge valid HMACs for arbitrary ciphertexts. With an encryption mode like CBC, this could be used to read the contents of encrypted messages. Other pitfalls include accidentally implementing Encrypt-and-MAC or MAC-then-encrypt, which have historically had vulnerabilities related to their construction.

On the other hand, EAX and GCM modes provide this feature transparently. There are some concerns about potential side-channel attacks against dedicated AEAD modes, and there is also the conceptual issue of potentially passing unauthenticated packets to your decryption algorithm. You, of course, have to get details like unique IVs correct, but you also have this requirement for Encrypt-then-MAC.

That said, potential flaws in EAX and GCM implementations can be fixed for many people at once with patches to the relevant libraries. Flaws where non-cryptographers naïvely compare HMACs are epidemic, and even high-profile projects like Google's KeyCzar have made this simple mistake. If you absolutely know what you're doing, Encrypt-then-HMAC is a provably secure construct. If you don't know what you're doing, something like EAX or GCM may be found to have weaknesses, but they are assuredly better than implementing something yourself.

Edit: I may have made Encrypt-then-HMAC sound easier than it actually is. One other major pitfall of Encrypt-then-HMAC is not HMACing enough information, or not HMACing the information correctly. The HMAC must include the ciphertext, the additional authentication data, and the initialization vector. It probably must also (perhaps someone else can confirm or deny this) include a descriptor to identify the encryption algorithm used. To pass these fields into the HMAC, you must use a format that unambiguously delineates fields. The easiest way to do this is to prepend a 4-byte big-endian length before any variable-length field (usually just authentication data and ciphertext), but doing this for all fields is probably a good idea. If you don't HMAC all this information, an attacker can modify any of the data not included. If you don't HMAC them unambiguously, an attacker can manipulate message boundaries, which could allow him to conduct an exploit.

Edit 2: Another detail of Encrypt-then-HMAC I've forgotten. Hopefully you can see how hard this is to get right. Ideally, you should never reuse the same key across security contexts. I'm unaware of any attacks that would result from using your encryption key as the key for the HMAC, but best practice is to use a different key for encryption and authentication. One simple approach (assuming a 256-bit encryption algorithm and 256-bit HMAC) is to use a "virtual" 512-bit key. Use the first half for encryption and the last half for authentication. Another approach is to use a 256-bit key, but pass it through HKDF with a 512-bit output; use this as before: split it into two parts, use one for encryption and one for authentication.

Edit 3: I asked a highly relevant question on the security StackExchange a few months ago. Thomas Pornin's detailed answer may be helpful.


From the main page;

Ristretto is a technique for constructing prime order elliptic curve groups with non-malleable encodings. It extends Mike Hamburg's Decaf approach to cofactor elimination to support cofactor-8 curves such as Curve25519.

The cofactor can cause some problems in some protocols, MQV, HMQV, MVQ and HMVQ
The main idea is the coset definition, only Edwards here;
Edward Curve ( twisted Edward Curve if $a\neq 1$ and untwisted Edward Curve if $a=1$)
$$\mathcal{E}_{a,d} := \{(x, y) \in \mathbb{P}^2 (\mathbb{F}) : a \cdot x^2 + y^2 = 1 + d \cdot x^2 \cdot y^2\}$$
has a cofactor of 4. A complete ( if $d$ and $ad$ are nonsquare in $\mathbb{F}$) Edward curve $\mathcal{E}_{a,d}$ has a $4$-torsion group ( elements of order $4$) and it turns out that it has exactly has 4 elements. Then the below coset is defined w.r.t. $P=(x,y)$
$$\mathcal{E}[4] + P = \{(x, y); (y/ \sqrt a, −x \sqrt a); (−x, −y); (−y/ \sqrt a, x \sqrt a)\}$$
Now, this coset eliminates the co-factor problem. Similar definitions for Jacobi with isogenies are given. Also for the compatibility of the Montgomery curves.

In The Ristretto Group, do all points sampled with Elligator have the same order?

This coset operation makes sure that the order (number of elements) of the coset curve is prime. Since the order of the group is prime then by the Lagrange theorem all elements have prime order ( order of elements must divide the order of the group).
In short, now, the hash-to-group with Elligator maps the hash into elements where each has prime order, except the identity.

Does any basepoint create a weakness?
The answer is no!. Consider that an attacker chooses the base $G$ deliberately that they can solve it easily. There is a simple approach for them to solve for any basis $G'$;

Solve DLog $G'$ to base $G$ to obtain $G' = [k]G$.
Now given $[x]G'$ solve it in the base $G$ to obtain $r$ such that $[x]G'=[r]G$
To get the $x$ just compute $x = r\cdot k^{-1} \pmod n$ where $n$ is the group order.


Use AES-256 Or AES-CTR-256 For One Block?

Like said in the comments, a 256-bit message is two blocks of AES, no matter the keysize.

The main issue with ECB mode (i.e. using AES directly on 128-bit blocks) is that you leak whether two blocks are equal. When encrypting perfectly random data, that means there's a $2^{-128}$ chance the two parts of the key are equal, and the attacker knows that. The probability you see a collision between halves of any two keys becomes significant once you reach about $2^{63}$ keys, but that probably doesn't help the attacker much unless he knows one of the keys already.

In contrast, with CTR mode the chance that you get two equal ciphertext blocks is the same, but that only leaks the fact that the two halves are not equal, which helps the attacker a minuscule amount – and is always leaked by ECB. So CTR is obviously better. (Assuming you can ensure unique nonces.)

However, lets get realistic. In CBC mode, with random and unequal IVs, the attacker could instead learn the XOR of two key blocks with the same probabilities as above. Knowing that helps an attacker about as much as knowing an equality. Yet, we consider CBC a secure enough mode to use.

So I wouldn't really worry about it, but if you can easily use CTR it only costs you the IV storage. Even 128-bit keys would be secure, though.

Note: The above is only the case when you encrypt purely random data. With non-random data ECB is almost always broken. The above also assumes the attacker can't get a chosen plaintext encrypted or anything similar.


Does a different exponent and base but same key help to resolve discrete logarithm?

Does the attacker help this knowledge about $k$ (in case (1.) or (2.)?

No; suppose you had an Oracle that could recover $a$ given $N, P, k, b, M$, then you could recover $a$ just given $N, P, k$ (that is, solve the Discrete Log problem).  Because we believe that the Discrete Log problem (given appropriate choices for $N, P$) is hard, we can conclude that constructing such an Oracle is also hard.

Here is how we would use such an Oracle; we already have been given $N, P, k$, and so all we need to do is construct $b, M$.  This can be done by selecting a $b$ relatively prime to $P-1$ and random otherwise; we can then compute $M = k^{b^{-1} \bmod P-1} \bmod P$; such a $b, M$ pair satisfies $k = M^b \mod P$, and so satisfies the Oracle's preconditions.  We then supply $N, P, k, b, M$ to the Oracle, and recover $a$

A similar method can be constructed for your question (3)


Are there any Secp256k1 ECDSA test examples available?

Here are five test vectors for secp256k1, which I just generated with my own code. My code is a generic implementation of elliptic curves; it has been tested for many curves for which test vectors were available (in particular the NIST curves) so I tend to believe that it is correct. Each test vector is a value $m$ (chosen randomly modulo the curve order $n$) and the coordinates $(X, Y)$ of the point $mG$, where $G$ is the conventional generator defined in section 2.7.1 of SEC 2.

m = AA5E28D6A97A2479A65527F7290311A3624D4CC0FA1578598EE3C2613BF99522
X = 34F9460F0E4F08393D192B3C5133A6BA099AA0AD9FD54EBCCFACDFA239FF49C6
Y = 0B71EA9BD730FD8923F6D25A7A91E7DD7728A960686CB5A901BB419E0F2CA232

m = 7E2B897B8CEBC6361663AD410835639826D590F393D90A9538881735256DFAE3
X = D74BF844B0862475103D96A611CF2D898447E288D34B360BC885CB8CE7C00575
Y = 131C670D414C4546B88AC3FF664611B1C38CEB1C21D76369D7A7A0969D61D97D

m = 6461E6DF0FE7DFD05329F41BF771B86578143D4DD1F7866FB4CA7E97C5FA945D
X = E8AECC370AEDD953483719A116711963CE201AC3EB21D3F3257BB48668C6A72F
Y = C25CAF2F0EBA1DDB2F0F3F47866299EF907867B7D27E95B3873BF98397B24EE1

m = 376A3A2CDCD12581EFFF13EE4AD44C4044B8A0524C42422A7E1E181E4DEECCEC
X = 14890E61FCD4B0BD92E5B36C81372CA6FED471EF3AA60A3E415EE4FE987DABA1
Y = 297B858D9F752AB42D3BCA67EE0EB6DCD1C2B7B0DBE23397E66ADC272263F982

m = 1B22644A7BE026548810C378D0B2994EEFA6D2B9881803CB02CEFF865287D1B9
X = F73C65EAD01C5126F28F442D087689BFA08E12763E0CEC1D35B01751FD735ED3
Y = F449A8376906482A84ED01479BD18882B919C140D638307F0C0934BA12590BDE

For self-testing an elliptic curve implementation, I suggest first verifying that multiplying $G$ by $n$ (the expected curve order) indeed yields the point at infinity. Then, do the following many times:

Choose two random integers modulo $n$; call them $a$ and $b$.
Compute $c = a + b$.
Compute points $P = aG$, $Q = bG$ and $R = cG$.
Verify that $P + Q = Q + P = R$.

If you go through this a few dozen times with no errors then chances are that your implementation is at least mostly correct.

A must-have reference on elliptic curve implementation is the Guide to Elliptic Curve Cryptography. It is not free, but worth its price. Good university libraries will let you read it without spending a dime on it.


Possible to split a secret to generate a re-encryption key (PRE)?

Something similar to what you ask, although not exactly, is the PRE scheme called Umbral. It has a reference implementation called pyUmbral. (Disclaimer: I'm the author of Umbral).

Umbral is a threshold PRE scheme, which means that re-encryption is divided among several proxies and at least certain threshold of them has to cooperate. With Umbral, the delegator can generate M-out-of-N re-encryption keys, in a way similar to Shamir's Secret Sharing.

I think you probably can reuse some of the techniques used in Umbral to split the delegator's private key and generate re-encryption key shares from the shares of this private key, rather than Umbral's approach which consists in generating directly re-encryption key shares. Anyway, both approaches should be very similar from the perspective of the application of Shamir's Secret Sharing.

I also think these techniques can be easily adapted to pairing-based PRE schemes, such as AFGH and others.


Is there a way to encrypt multiple sets of data into one result, with separate keys decrypting each set of data

It is possible that you have some additional implicit constraints that invalidate the following solution.
But as the question currently stands the following might give you what you are looking for:

Assume we have a authenticated symmetric encryption scheme. (Say encrypt-then-mac with a blockcipher in a suitable mode.)

We get our two messages $m_0,m_1$ and two keys $k_0,k_1$.
To make things simpler, we assume that the messages have the same length and that our encryption scheme will output ciphertexts of the same length for inputs of the same length.

We encrypt $c_0 \leftarrow \mathsf{Enc}(k_0,m_0)$ and $c_1 \leftarrow \mathsf{Enc}(k_1,m_1)$.
We then choose a random bit $b \in \{0,1\}$ and output the ciphertext $c=c_b\Vert c_{1-b}$.

To decrypt, given a key $k$ and a ciphertext $c$, we split $c$ into two halves, and try to decrypt each half.
As the encryption scheme is authenticated, decryption will only be successful for the half actually encrypted under $k$ except with negligible probability. We then simply output this message.

The CPA security of this scheme easily reduces the the CPA security of the authenticated encryption scheme.
If we need CCA security, it should be enough to add an additional MAC over the complete ciphertext with a third key, and include that third key as part of what you call AP and BP, i.e. the two keys.

The Security of the encryption scheme ensures that given one of the keys you can decrypt only exactly one of the messages.
Furthermore, because the order of the ciphertexts is random, you cannot learn whether your key/message is the first or second one.


How convert Point on Curve into AES key?

Most symmetric cryptographic algorithms requires a key that is indistinguishable from random. This means that the process used to generate the key must have a uniform, independent distribution over all bit-strings of the appropriate length. Using a non-uniformly-random key not only reduces the brute force needed to guess it, but may also open the door to related-key attacks.
The expressions “key agreement” and “key exchange” are often used to mean a mechanism like (elliptic curve) Diffie-Hellman, but (EC)DH itself does not produce a key, it only produces a shared secret. This secret is in some numerical range that depends on the curve: not all $2^n$-bit values are possible. Even within this range, it is not uniformly distributed (it can't be since there isn't the same number of private points and public coordinates).
To go from the shared secret to a key, you need to use a key derivation function. A KDF takes a secret which has a cryptographically high number of possible values but may not be uniformly distributed, and has output that is indistinguishable from random to anyone who doesn't know the secret.
In a pinch, if you only need one symmetric key from the key exchange, hashing the shared secret with a cryptographic hash such as SHA-256 or SHA-512 is fine. If you need more key material than one hash's length, or if you prefer to use a standard construction that may be more robust in case a partial weakness is discovered in a hash function, there are (too) many standardized key derivation functions, for example HKDF (robust and popular), the TLS 1.2 PRF (a variant of HKDF which is specific to TLS), the NIST SP 800-56C key derivation functions (some hash-based like HKDF, some AES-based), etc.


Layman's description of the padding oracle attack

Quoting the answer here:

Padding Oracle attacks are mainly a problem in cases, where e.g. an encrypted message is modified and send to a target. These attacks try to measure the difference when decrypting and validating the message.
The steps are:

decrypting the message
checking the padding > error if wrong
checking or processing the data > error if wrong or format corruption detected

The padding oracle attacks try to measure timing differences between step (2) and (3) or utilizes different error messages.

So the information leakage that enables the attack comes in the form of either timing differences or is present in the error messages that the server returns as a response to the malicious query.


Do standalone Oblivious Transfer (OT) Protocols exist?

The term "stand alone" in secure computation typically refers to the case of a protocol being run once, and not to assumptions. In any case, what I assume you are really asking is what assumptions are needed for OT. You are indeed correct that OT is built from asymmetric assumptions, and this is actually inherent for black-box constructions. This was studied in The Relationship Between Public Key Encryption and Oblivious Transfer.


Generic group model: use of polynomials in the proof of the master theorem

The problem can be simplified to the following problem, since the standard argument doesn't really take into account that you can't generate all the polynomials of the given maximum degree :

Assume that we have sampled a random point $\vec{x}\in \mathbb{F}_p^n$. We let an adversary adaptively choose polynomials of degree at most $d$ and after each choice we tell whether $\vec{x}$ is a root of the chosen polynomial. Then after $q$ queries, the probability that the attacker has found a polynomial for which $\vec{x}$ is a root is bounded above by
$$\frac{qd}{p}.$$

What we know is that the probability that a random element in $\mathbb{F}_p^n$ is a root of some polynomial of degree $d$ is bounded above by $d/p$. Therefore, the attacker is essentially choosing subsets of size at most $d/p\cdot p^n$, since we only care about roots, not the actual polynomials. Thus, the problem is equivalent to the following:

Assume that we have chosen a random point $x$ in a set $S$ of size
$p$. We let an an attacker adaptively choose $d$ points at each round
and then tell the attacker whether or not $x$ is among the $d$ points.
Then the probability that after $q$ queries we have chosen a set of points containing $x$ is bounded above by $qd/p$.

We prove by induction that the upper bound is given by $qd/p$. This clearly holds for one query, since on the first attempt we're just picking a set of size $d$ and the probability of $x$ being in this set is $d/p$. Now assume by induction that the winning probability on $q$ queries is $qd/p$. Now with $q+1$ queries, we either win during the first $q$ queries or we don't and win on the $q+1$st. It follows that we get
$$\frac{qd}{p}+\frac{d}{p-dq}\left(1-\frac{qd}{p}\right)=\frac{(q+1)d}{p}$$
It's correct, however, that none of the existing proofs in the literature discuss the point that the adversary chooses polynomials adaptively. All the proofs just say that at the end we have $(s+q)^2$ possible polynomials and the chance of a random element being a root of one is $(s+q)^2d/p$, which is not really a valid argument in this case, although you get the same bound.


Implications of reversing CBC encryption

If I understand you correctly, you want to use the decryption process of CBC to encrypt, i.e.,

This would not be CPA secure. The problem is, as you already noted, that the IV has no influence on any block but the first one.

I.e. a CPA attacker works as follows:
Choose two random messages of length 2 blocks $(m_0^0,m_0^1)$ and $(m_1^0,m_1^1)$ and output them as the challenge messages. Receive back the challenge ciphertext $(c^0,c^1)$. Now, ask $(m_0^0,m_0^1)$ to the encryption oracle and receive the encryption $(c_0^0,c_0^1)$. If $c^1 = c_0^1$ then output $0$, otherwise output $1$.


Is AES ECB mode with salt and frame counter still comparatively weak?

The point of producing different ciphertexts for the same plaintext is so that an attacker, given two identical ciphertexts, could not conclude that the plaintexts must be the same. This is indeed a weakness, but is not the main problem of ECB, which is that each block is encrypted completely independently, leaking huge amounts of information about the plaintext to even a passive observer.
Your strategy does not help with that, as the attacker could simply ignore all the ECB blocks belonging to the counter and salt and simply pick out blocks belonging to the messages, and we're back to standard ECB.


This sort of combination is vulnerable to a meet-in-the-middle attack.  Let's start from one of your equations:

$$
C = P \oplus f_1(K_1) \oplus f_2(K_2)
$$

If we XOR $f_1(K_1)$ to both sides, we get:

$$
C \oplus f_1(K_1) = P \oplus f_2(K_2)
$$

Now if I have one known plaintext/ciphertext pair $P, C$, to attack the cipher, I can carry out the meet-in-the-middle attack:

I build a table of the values of $C \oplus f_1(K_1), K_1$ for all possible values of $K_1$.  This takes time and memory proportional to $2^{|K_1|}$.
For each possible value of $K_2$ I compute the corresponding $P \oplus f_2(K_2)$, and look it up in the table from step #1.  If I find a match I record that $K_1, K_2$ combination as a candidate key.

Now the key must be one of the candidate keys, and it only took me $2^{|K_1|} + 2^{|K_2|}$ time to find this out, not $2^{|K_1| + |K_2|}$—the combined cipher is much weaker than a cipher with the sum of the key lengths.

(Note that there can be more than one candidate key.  Any $K'_1, K'_2$ such that:

$$
f_1(K'_1) \oplus f_2(K'_2) = f_1(K_1) \oplus f_2(K_2)
$$

...is a candidate key as well.  But you can bet the number of candidate keys will be much, much smaller than the number of keys.)


In cryptography, an elliptic curve is a group which has a given size $n$. We normally work in a subgroup of prime order $r$, where $r$ divides $n$. The "cofactor" is $h = n/r$.

For every point $P$ on the curve, the point $hP$ is either the "point at infinity", or it has order $r$; i.e., when taking a point, multiplying it by the cofactor necessarily yields a point in the subgroup of prime order $r$.

The cofactor matters inasmuch as it is not equal to $1$:

When the cofactor is $1$, then the subgroup is the whole curve. Any non-zero point is a generator. Any incoming point $(x,y)$ that fulfills the curve equation is part of the subgroup. Everything is fine.
When the cofactor is not $1$, then the subgroup of prime order is a strict subset of the curve. When considering a point, verifying that the curve coordinates match the curve equation is not sufficient to guarantee that the point is on the appropriate subgroup. Moreover, there will be points whose order is not a multiple of $r$. This is what happens, for instance, with Curve25519, which has a cofactor of $8$. Such curves require some extra care in the protocol that uses them. For instance, when doing a Diffie-Hellman key exchange over Curve25519, the Diffie-Hellman private keys must be chosen as multiples of 8 (which is expressed as: "set the three least significant bits to zero"); this ensures that the points will be in the proper subgroup.


Boolean circuit: can the output wire of a gate be used by many different gates in the next layer?

However, I failed to find any explicit comment whether an output wire of a gate can be used simultaneously by several gates in the next layer.

Of course you can do that.
In fact there are examples in the very repository you linked to, e.g. wire 3488 of the AES-128 implementation is used twice.


Is there an escrow-like mechanism that doesn't involve a trusted 3rd party?

Yes they can!

This can be done through a public blockchain like bitcoin for instance.

Other blockchains such as Ehtereum provide more functionnalities like Smart Contracts. These would enable both parties to send their goods (cryptocurrency/ digital property of some good etc.) to a decentralized application - DApp - running on the blockchain (basically, a piece of logic code that would be cowritten by the two parties so it would wait to receive the expected goods from the expected parties until realeasing it to one another, effectively acting as a decentralised, no TTP, automated, bot-escrow).


Do any one-key-of-many cryptographic schemes exist?

Yes, absolutely.  Here is the standard construction to address this problem.  Let $pk_1,\dots,pk_n$ be the public keys of the $n$ recipients.  We pick a random symmetric key $k$, encrypt the message $m$ (using authenticated encryption) under key $k$ to get $c=AE_k(m)$, and then encrypt $k$ under each of the public keys. Finally, we form the whole ciphertext as

$$E_{pk_1}(k),E_{pk_2}(k),\dots,E_{pk_n}(k),c.$$

That's what we treat as our ciphertext.  Now any of the $n$ recipients can decrypt (they can recover $k$ using their private key, and then use that to decrypt $c$), but no one else can.

The same method works in the shared-key (symmetric-key) setting as well.

This standard construction is standardized in more detail in "RFC 4880: OpenPGP Message Format" and in PKCS#7 (enveloped-data).  (Thanks, David Cary and DrLecter!)

You might also enjoy looking into broadcast encryption, which solves a related problem.  It basically allows you to transmit a message to millions of receives, without having a huge blowup in the size of the ciphertext (so it achieves much shorter ciphertexts than the simple scheme above), though there are some details and a little bit of additional coordination required.

For digital signatures, you might enjoy looking at ring signatures and group signatures.


Digicipher and other proprietary systems?

Don't think you've missed something.

  How do they keep these systems from being broken by someone just looking at the information in the smartcard that houses the key?

Those systems have indeed been (and frequently are) broken via Hardware reverse-engineering. Therefore I would chime in with your "not secure". OTOH: decrypting AV signals isn't like trying to break national security or anything. Multiple black-markets exist where you could (but legally shouldn't!) get rebuild decoder-cards for almost any system and channel(s).

As indicated, the law is the strongest protection for Pay-TV providers. The signal is merely "crippled" to keep the masses from intercepting and decoding them without additional hardware and (illegal) efforts.


How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier?

The security goal behind SRP is that an attacker that could either pretend to be a client (and attempt to log into a server that knows the key), pretend to be a server (and allow clients that know the key to attempt to log in), or actively monitor (and modify) the communications between a valid client and a valid server, would learn nothing from an exchange, except possibly whether a single password is valid or not.  This last bit cannot be helped with a password-based authentication method, as the attacker could always take his guess at the password, and then proceed with the protocol with a valid server or client, and see if it succeeds.  The point of SRP is that the attacker can't do any better than that.

Now, in the protocol, the value v is never sent over the wire, and so the attacker does not see it, and so a dictionary attack against that value is impossible (unless the attacker can rederive that value somehow, which is not believed to be possible).

On the other hand, the note you highlighted assumes that the attacker can do more than just work with the protocol; it assumes that he is also able to access the password files on the server.  If he can do that, well, yes, he knows enough to impersonate a server, and he can also perform a dictionary attack on the password; namely for each password P' in his dictionary, he computes:

x' = H(s, P')
v' = g^x'

and check if v == v' (note: it is quite unlikely that you could stumble on a different password that also passes this check)

Note that this is not specific to SRP; for any password-based authentication method, if the attacker can learn everything the server knows, then he can impersonate the server, and in addition, he can perform an undetectable dictionary attack (for example, by simulating a client logging in with various passwords; this is undetectable because since this occurs entirely on the attackers equipment, you aren't informed that someone that someone is trying to log into the system with a long series of passwords).

As for why this is better than a shared secret protocol, well, an attacker can run a dictionary attack even if he didn't have direct access to the server's password files; with SRP, that sort of access is needed.


Chosen Plaintext Attack and Chosen Multiple-Plaintext Attack

If a public-key encryption scheme is CPA-secure is it also secure in this revised version of CPA game?

Yes, because this is essentially a trimmed down version of Left-or-Right-CPA security (PDF) which is provably equivalent to the first definition you mentioned which is also known as Find-Then-Guess-CPA security.

If your scheme is LoR-CPA secure then you can query all message pairs from the two sets to the LoR oracle and answer any remaining queries $x$ by querying $(x,x)$.

The inverse direction (that the new definition implies LoR) probably requires a Hybrid Argument as indicated in the comments to "extend" the size of the set to all queries. This should go analogous to proving that FtG-CPA security implies LoR-CPA security.


RSA never was intended as a symmetric/secret key cryptosystem, or extensively used as such. Public/Private key pairs have been used for RSA from day one.

A very close cousin of RSA, also using Public/Private key pairs, was known (but not published) at the GCHQ significantly before RSA was published. See Clifford Cocks's declassified A Note on 'Non-secret Encryption' (1973). Public-key cryptography was theorized at the GCHQ even before, see James Ellis's declassified The Possibility of Secure Non-Secret Encryption (1969), and his account in the declassified The history of Non-Secret Encryption (1987). See this question for more references on these early works.

As kindly reminded by poncho: the Pohlig-Hellman exponentiation cipher is a symmetric analog of textbook RSA. It uses as public parameters a large public prime $p$ with $(p-1)/2$ also prime, and two random odd secret exponents $e$ and $d$ with the relation $e\cdot d\equiv1\pmod{(p-1)}$; encryption of $m$ with $1<m<p$ is $c\gets m^e\bmod p$, decryption is $m\gets c^e\bmod p$. By incorporating the computation of $d$ from the encryption key $e$ into the decryption, and using cycle walking to coerce down the message space to bitstrings and remove a few fixed points, it becomes a full-blown block cipher by the modern definition of that. Security is related to the discrete logarithm problem in $\mathbb Z_p^*$ . An algorithm for solving that is the main subject of the article, and what Pohlig-Hellman now designates. The encryption algorithm has little practical interest, because it is very slow for a symmetric-only algorithm. It never caught in practice, and I believe never was intended to do so.

I found no earlier reference than: Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithm over $GF(p)$ and Its Cryptographic Significance published in IEEE Transactions on Information Theory, Volume 24 Issue 1, January 1978.

RSA was clearly known to the authors when they submitted this correspondence. They make explicit reference to:

Ronald L. Rivest, Adi Shamir, and Leonard Adleman, On Digital Signatures and Public-Key Cryptosystems, Technical Memo MIT/LCS/TM-82, dated April 1977 (received by the Defense Documentation Center on May 3, 1977; publication date unknown).
Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems published in Communications of the ACM, Volume 21 Issue 2, February 1978 (received April 4, 1977; revised September 1, 1977).

Note: I discovered (1.) only because it is referenced by Pohlig and Hellman; it has a number of rough edges fixed in (2.), including a byzantine and unnecessary complication in the handling of messages not coprime with the public modulus, that are telling of the novelty.

I refer to poncho's account on chronology.


Looking for cipher that uses one ciphertext

There are several systems that sound vaguely similar to your description.
Would either one (or both) of the following systems work for you?
If not, what exactly about systems is unsuitable for your application?

deniable encryption

You give a unique key to each of a bunch of people.

You think up a unique plaintext message intended for one and only one person.

Later, you publicly publish some huge encrypted file (one ciphertext).

Each person uses their own unique key to extract their own unique plaintext message from that file.

It's not possible for any one person (as long as everyone keeps their own key secret), or even several of the intended recipients working together, to find out if there are any other messages in the huge encrypted file, much less exactly how many messages there are or what exactly the other plaintext messages say.

deniable encryption

File intended for several recipients

Each person has a unique key.
(Typically each person has their own private key, generates a public key from it, and each person publishes the public key or gives you their public key some other way).

You think up a plaintext message you want to send to some, but not all, of those people.

You make up a completely new one-time symmetric key that no one else could possibly know.
You encrypt the plaintext message with this new key, making one large file.
You encrypt and re-encrypt the one-time key multiple times, each time with the key (typically the public key) of one of the intended recipients.
You end up with lots of short files, one for each intended recipient,
and one large file that is the same for everyone.
The standard OpenPGP system archives that large file and all the corresponding short files together into one slightly larger file.

Then you publish that slightly larger file (one ciphertext).

Each person uses their own unique key to extract the one-time symmetric key, and then uses that key to decode the large file.

Then every one of the intended recipients knows there is one and only one message in the large encrypted file, and they all know they are all reading exactly the same message as all the other intended recipients.

It's pretty obvious how many intended recipients there are for a file in OpenPGP format, even to people who are not a intended recipient.
But there are work-arounds to camouflage exactly how many (other) recipients there are, even to someone that is a intended recipient and can decode the file into readable plaintext.

" Hash decrypts key, key decrypts cipher... why? "

" https://security.stackexchange.com/questions/8245/gpg-file-size-with-multiple-recipients "

Information leakage from the ecryptfs filesystem

" How can two different passphrases unlock the same content? "


How to use the Extended Euclidean algorithm to invert a finite field element?

To answer this question, we need to understand what is meant by:

  the field $\operatorname{GF}(2^8)$ generated by the irreducible polynomial $m(x) = (\mathtt{0x11B})$.

and I'll try a gentle, progressive introduction to that.

One simple way to see this field is that as the set of the 256 octets $\{\mathtt{0x00},\mathtt{0x01},\dots,\mathtt{0xFF}\}$; with additive law bitwise XOR $\oplus\;$; and multiplicative law the commutative operation $*$ defined in either one of the following ways:

By having $\mathtt{0x01}$ as the neutral element, $\mathtt{0x02}*\mathtt{0x80}=\mathtt{0x1B}\;$ (that's the given $\mathtt{0x11B}$ truncated to its low-order 8 bits), and the more intuitive $\mathtt{0x02}*\mathtt{0x02}=\mathtt{0x04}\;$, $\mathtt{0x02}*\mathtt{0x04}=\mathtt{0x08}\;$, $\mathtt{0x02}*\mathtt{0x08}=\mathtt{0x10}\;$, $\mathtt{0x02}*\mathtt{0x10}=\mathtt{0x20}\;$, $\mathtt{0x02}*\mathtt{0x20}=\mathtt{0x40}\;$, $\mathtt{0x02}*\mathtt{0x40}=\mathtt{0x80}\;$. These and the properties of $*$ (commutativity, associativity, distributivity with respect to $\oplus\;$) are enough to fully define $*$. The constant $\mathtt{0x1B}$ is such that every element except $\mathtt{0x00}$ (the neutral element of $\oplus\;$) has a multiplicative inverse, which can be found by inspection of the multiplication table (building this table, and deriving an algorithm which computes the product of two arbitrary elements without this table and at most 8 iterations, is left as a recommended exercise to the reader). This gives the result asked in the question, but not by the method thought, and is impractical by hand.
Alternatively, we can define a commutative ring $(\mathbb N,\oplus,\otimes)$ where $\oplus$ is bitwise XOR, and $\otimes$ (sometime called carry-less multiplication) is the same as common multiplication when either argument is a power of two, and the associativity of $\otimes$ with respect to $\oplus$ is used to define the other cases. For example $\mathtt{0xDB}\otimes\mathtt{0x42}$ $=\mathtt{0xDB}\otimes(\mathtt{0x40}\oplus\mathtt{0x02})$ $=(\mathtt{0xDB}\otimes\mathtt{0x40})\oplus(\mathtt{0xDB}\otimes\mathtt{0x02})$ $=\mathtt{0x36C0}\oplus\mathtt{0x1B6}$ $=\mathtt{0x3776}$. We can define an analog to Euclidean division in $(\mathbb N,\oplus,\otimes)$, giving quotient $q$ and rest $r$ from dividend $d$ and non-zero divisor $n$, such that $d=(q\otimes n)\oplus r$, and the bit size of $r$ is less than the bit size of $n$. That allows us to define an analog in $(\mathbb N,\oplus,\otimes)$ of modular reduction in the ring $(\mathbb Z,+,\times)$. Our operation $*$ in $\operatorname{GF}(2^8)$ is $\otimes$, followed by reduction modulo $m=\mathtt{0x11B}$. That constant is such that $(\operatorname{GF}(2^8),\oplus,*)$ is a field, much like $(\mathbb Z_n,+,\times)$ is a field when $n$ is prime. Now we can apply the Extended Euclidean algorithm and answer the question by the method asked. We do as for computing an inverse modulo a positive integer, but use $\oplus$ instead of addition and subtraction, $\otimes$ instead of multiplication, and the analog of Euclidean division in $(\mathbb N,\oplus,\otimes)$.

An equivalent way to see the field $\operatorname{GF}(2^8)$ is as the set of the 256 polynomials with one variable, of degree less than 8, having bit coefficients per Boolean algebra; additive law the addition of polynomials; and multiplicative law the multiplication of polynomials followed by modular polynomial reduction of the product by the polynomial $m(x)=x^8+x^4+x^3+x+1$ (corresponding to bits in $\mathtt{0x11B}\;$). A necessary and sufficient condition for every element except zero being invertible, is that $m(x)$ is irreducible, which holds. Now we can apply the Extended Euclidean algorithm and answer the question by the method asked. We do as for computing an inverse modulo a positive integer, but use $m(x)$ as the modulus, and division of polynomials with bit coefficients instead of Euclidean division.


I am attempting to decrypt a 90 GB file that is encrypted using 256
  AES. [...] How long should this take to complete?

If the AES implementation and the program doing the decryption are any good this is only bound by the speed of your drive, if your processor is newer than from about 2012. So for an SSD, you should be able to hit 200MB/s and with an HDD 50MB/s with little problems, if the program doesn't have some horrendous overhead and utilizes a sane implementation and with an older / weaker processor, you should still be able to saturate the HDD and run the SSD at about half speed.

Note however that certain platforms, e.g. standard python don't actually compile to machine code and thus are extremely slow, ie in a measurement I did recently I hit about 1MB/s with the interpreter. But even then it should "only" take you 25 hours. So chances are the program you are using is extremely poorly implemented and you should strongly consider using an alternative if you can.


Is LibreSSL affected? - Downgrade Attack on TLS 1.3


Two suggestions:

Does it simplify the problem for you if you omit n? (or only consider the n=1 case)
Suppose F(x⊕1n) would not be a pseudorandom function, what does that tell you about the pseudorandomness of the original function F?


What is the difference between Paillier additive homomorphic property and addition of two paillier ciphers

In standard Paillier encryption

Property 1 really is:
$m_1=D(c_1)\text{ and }m_2=D(c_2)\implies D(c_1\cdot c_2\bmod n^2) = m_1+m_2\bmod n$.
Property 2 does not hold (but see final off-topic note).

As a consequence of property 1, for all $k$ in $\mathbb Z$, it holds $D({c_1}^k\bmod n^2)\ =\ m_1\cdot k\bmod n$. Proof for positive $k$ can be by induction, proof for negative $k$ follows from group properties of multiplication in $\mathbb Z_{n^2}^*$ and $\mathbb Z_n^*$.
Note: For integers $u$, $v$ and $w$, by definition of $u\bmod v=w$, that means $u-w$ is a multiple of $v$ and $0\le w<v$. The operator $\bmod$ has priority less than $+$ (thus less than $\cdot$) but more than $=$. Contrast with operator % in computer languages, which typically has priority more than +.

Once this party has received some EncryptedNumber instances (e.g. see Serialisation), it can perform basic mathematical operations supported by the Paillier encryption:

Addition of an EncryptedNumber to a scalar
Addition of two EncryptedNumber instances
Multiplication of an EncryptedNumber by a scalar

That's correct if we take addition and multiplication modulo $n$. Given $c_1$ and $c_2$ such that $m_1=D(c_1)$ and $m_2=D(c_2)$, and a scalar $k$ in $\mathbb Z$, any party knowing the public key $(n,g)$ can

Compute $c$ such that $D(c)=m_1+k\bmod n$, by encrypting $k$ and applying property 1. That is $c\gets c_1\cdot g^k\cdot r^n\bmod n^2$ for some $r$ coprime with $n$ (possibly $r=1$ if hiding $k$ and that $c$ derives from $c_1$ are pointless in the application).

Compute $c$ such that $D(c)=m_1+m_2\bmod n$, by application of property 1.

Compute $c$ such that $D(c)=m_1\cdot k\bmod n$, by application of the consequence of property 1.

The doc linked in the question is for a library that adds a wrapper on Paillier encryption. This is the part of the source doing the crypto. The library handles negatives and floating point numbers, as explained there, by

Restricting it's plaintext integers to range $\left[\,-\left\lfloor n/3\right\rfloor,\left\lfloor n/3\right\rfloor\,\right]$, with negatives mapped to $\left[\,n-\left\lfloor n/3\right\rfloor,n-1\,\right]$ of standard Paillier encryption.
Separating mantissa (encrypted with sign as above) and exponent (which remains in clear).

Off-topic: Python allows operator + to perform anything the programmer wants when applied to objects defined by the programmer. Both in the above library and the simpler code linked in comment, + for two ciphertexts has been coerced overloaded to call an internal function that makes use of property 1, thus performs a multiplication modulo $n^2$. Similarly, * has been overloaded to call an internal function that makes use of the consequence of property 1, thus performs an exponentiation modulo $n^2$.


Are there any known security issues when doing the following chaining of BCrypt Hashes: 'bcryt(bcrypt(user-pw, work-factor1), work-factor2)'

First there are a few technical hurdles to deal with. Nominally, bcrypt takes three inputs: the password itself, a work factor, and a salt. To hash or to verify a password, you need the salt. Usual bcrypt implementations generate the salt randomly when first processing a password, and encode the salt along with actual function output into an aggregate string. If you use the whole string from the first bcrypt as input to the second bcrypt, then the final output will not contain the first salt, and you will never be able to recompute that hash for password verification.

Also, bcrypt works over "passwords" that it uses as sequences of up to 72 bytes. However, since passwords are normally text, some (most) implementations will accept a character string. In the C language, a character string stops at the first character of value zero. If the first bcrypt output, in binary, happens to contain a byte of value zero at the start, then in fine you will get the bcrypt hash of an empty string, and the hashed password will match one in 256 input passwords, which is bad. This is the kind of mistake that destroys your security but has a high chance of not being detected in unit tests.

You could avoid the "byte zero" effect by encoding the bcrypt output into a character string, e.g. with Base64 or hexadecimal. This enlarges the output, and can bring you dangerously close to the input size limitations for the second bcrypt. Compounding the effect, some bcrypt implementations have lower limits (56, 55 and even 51 bytes maximum size have been spotted in the wild) and may silently truncate the input.

All of that being said, yes, you could expand a bcrypt instance by cascading a second one, assuming that you take care to manage salts externally (it's unclear whether using the same salt for both bcrypt would be safe, so you might have to manage a longer aggregate salt).

However, it's better to start with a password hashing function that already includes work factor increases as a design feature. In the password hashing competition, at least Makwa had that feature (Makwa is not "the" winner of PHC, but it got a "special recognition" and, like many other candidates, was not broken).


RSA Key generation Public exponent too big

The $2^{16} + 1$ exponent is really meant for use in real life systems, in which public keys are expected to be considerably larger than that. I guess CrypTool assumes this is the case, as you would expect, really.

That said, if $\gcd{(e, \varphi{(n)})} = 1$, then $gcd{(e ~ \mathrm{mod} ~ \varphi{(n)}, \varphi{(n)})} = 1$ by definition, so such an $e$ will still work regardless, as noted by fgrieu in the comments.


Is there a TLS extension for generating unique IVs for AES GCM?

You can check this answer which mentions how does the IV generated for GCM ciphers in TLS 1.2

  ... is an AEAD Cipher, so it is in the form of GenericAEADCipher:

struct {
     opaque nonce_explicit[SecurityParameters.record_iv_length];
     aead-ciphered struct {
         opaque content[TLSCompressed.length];
     };
  } GenericAEADCipher;

  Here, the nonce_explicit contains 8 byte nonce, and you combine this
  with the 'fixed IV' from key derivation (4 bytes) then you get 12 byte
  IV for AES-GCM mode encryption. (Note that you only sent the
  last 8 bytes of
  the IV).

Also, from the RFC 5288 (AES Galois Counter Mode (GCM) Cipher Suites for TLS)

  6.1.  Counter Reuse

  AES-GCM security requires that the counter is never reused.  The IV
  construction in Section 3 is designed to prevent counter reuse.

From Section 3 of the RFC 5288:

  The "nonce" SHALL be 12 bytes long consisting    of two parts as
  follows: (this is an example of a "partially    explicit" nonce; see
  Section 3.2.1 in [RFC5116]).

struct {
     opaque salt[4];
     opaque nonce_explicit[8];
} GCMNonce;

  The salt is the "implicit" part of the nonce and is not sent in the
  packet. Instead, the salt is generated as part of the handshake
  process: it is either the client_write_IV (when the client is sending)
  or the server_write_IV (when the server is sending).  The salt length
  (SecurityParameters.fixed_iv_length) is 4 octets.

  The nonce_explicit is the "explicit" part of the nonce. It is
  chosen by the sender and is carried in each TLS record in the
  GenericAEADCipher.nonce_explicit field. The nonce_explicit length
  (SecurityParameters.record_iv_length) is 8 octets.

  Each value of the nonce_explicit MUST be distinct for each distinct
  invocation of the GCM encrypt function for any fixed key. Failure to
  meet this uniqueness requirement can significantly degrade security.
  The nonce_explicit MAY be the 64-bit sequence number.

So, reusing the same IV in GCM ciphersuites in TLS is prevented in this way.


Can one use a reversible hash algorithm as a compression function?

Strictly speaking, all hash functions are compressing since the output can be smaller than the input, but I imagine you're asking about compressing data that can later be losslessly decompressed.
This is impossible due to the pigeonhole principle. The fact that the fixed output space of a hash algorithm is smaller than the input space means that there will always be multiple possible inputs for the same output. Even if you could find a preimage (i.e. "reverse" the hash), you would not know if it is the original preimage or just a preimage. If the input size was sufficiently small (smaller than the hash) then it may be possible since you can discard larger preimages and only keep the very finite number of small ones that make sense (e.g. only valid ASCII strings), but then it's not compression.
As an extreme example, imagine a "hash function" with a trivial preimage attack: a 1-bit CRC with the polynomial x + 1 (i.e. an even parity bit). If I give you the output of this function and the output is 1, you will have absolutely no idea what the input was. You can compute an input, but you can't find the input. For a 1-bit hash, half of all possible inputs in the input space map to that same output!

This impossibility is the basis of the popular joke from Schneier Facts:

For Bruce Schneier, SHA-1 is merely a compression algorithm.


Proof Dlog is hard in generic group model

The lower bound for the generic group model is proved by Victor Shoup,

He showed in Lower bounds and Discrete Logarithm and Related Problems

  Lower bounds on the complexity of these problems are proved that match the known upper bound: any generic algorithm must perform $\Omega(p^{1/2})$ group operations, where $p$ is the largest prime dividing the order of the group.

Generic Group model;

To process with a group we must present them with bit strings. This must be a bijection, 1-1 and onto. A generic algorithm works independently from the representation of the group. They are not allowed to work with efficient representation as field and rings instead they are working with an oracle with the random representation $\sigma$ of the group. The oracle executes the group operation $$\text{add}(\sigma(a),\sigma(b)) = \sigma(a+b)$$ and $$\text{inv}(\sigma(x)) = \sigma(-x) $$ The running time is measured by the number of oracle calls.

The importance of this model is providing an answer to the question

What is the fastest generic algorithm for breaking a cryptographic hardness assumption?

The lower bound for the generic group model is proved by Victor Shoup. It is proven that any algorithm with constant success probability has at least $\mathcal{O}(\sqrt{q})$-time where $q$ is the largest factor of the group size $n$. The generic algorithms are

Baby-step Giant-step needs an upper bound knowledge of the group size and has running time $\mathcal{O}(\sqrt{n} \log n)$.
The Pohlig-Hellman algorithm needs the prime factorization of $n$ and has $\mathcal{O}(\sqrt{q} \log q)$ complexity.

Generic Group model has the same problem as the Random Oracle model - Real model vs Ideal model. It can be shown that Cryptographic schemes can be secure under the generic group model but trivially broken if instantiated 1,2


Based on your description, you will not be able to recover the original encrypted file.

Since you specify that you used a password and do not indicate the use of an IV, my assumption is that you did, in fact, use a passphrase rather than a secret key. When you encrypt a file with a passphrase, OpenSSL assumes that it is a low-entropy string unsuitable for use as a cryptographic key (which is assumed, for AES, to be a random 128-bit or 256-bit string). To turn the passphrase into a suitable key, it performs key stretching: a random salt is generated, and it is hashed together with the key a large number of times in order to increase the amount of effort needed for an attacker to guess the original input. The result is then used as the key.

Unfortunately, it is this random salt which prevents you from reencrypting back to the same file. If you had used a fixed key and IV (initialization vector), it would in general be possible for you to simply reencrypt the data with the two inputs you had mistakenly used, and recover the original encrypted file. However, since a random salt is used in the process to produce a key from a passphrase, and that random salt is stored in the file you decrypted, there will be no way to guess what that value was and therefore ensure you reencrypt with the same key and IV inputs.


How does ECDH arrive on a shared secret?

Let's assume that everyone agreed on some elliptic curve and a public base point $g$ somewhere on the curve.
When two parties Alice and Bob want to agree on a shared secret, they proceed as follows:

Alice chooses some random number $a$ and applies the curve operation to $g$, the public base point, $a$ times. She obtains some result $A=g^a=\underbrace{g\cdot g\cdots g}_{\text{$a$ times}}$ and shares this point across the wire with Bob.
Likewise, Bob chooses a random number $b$ and publishes $B=g^b$.
Alice takes Bob's point $B$ and applies the curve operation $a$ times to it to obtain a point $S$. That is, $S=B^a=\underbrace{B\cdot B\cdots B}_{\text{$a$ times}}$.
Bob takes Alice's point $A$ and proceeds accordingly to obtain $S'=A^b$.

At this point, the important thing to notice is that applying some operation $a$ times $b$ times is the same thing as applying some operation $b$ times $a$ times. To keep abusing the billiards metaphor: Hitting a ball $3$ times and repeating this process $5$ times is exactly the same thing as hitting a ball $5$ times and repeating this process $3$ times. In both cases, the ball gets hit $15$ times. Therefore, $S=S'$ is a shared secret!

We have yet to make plausible why $S$ is secret: An attacker only sees $A$ and $B$ and wants to find out what point would result in "mixing" the operations performed by Alice and Bob. Mathematically speaking (this is known as the Diffie-Hellman problem): Given $g^a$ and $g^b$, what is $g^{ab}$? The obvious (but perhaps not the only) way to solve this problem is to compute $a$ and $b$ and simply evaluate the desired expression (remember, hitting the ball is easy!). But computing $a$ or $b$ (solving the discrete logarithm problem) is hopefully — this is in fact an open problem — hard when they are sufficiently large, as described in the text you cited. Therefore, an attacker has (for all we know) a very hard time obtaining the shared secret $S$, and Alice and Bob can live their lives happily ever after.

As to the ephemeral "variants": There are none. The difference lies exclusively in the way the above procedure is used: "ephemeral" simply means that the private keys $a$ and $b$ are generated only for one single session and thrown away afterwards, providing forward secrecy.

Edit. As Stephen pointed out in the comments, it is actually not that easy: If Alice just naïvely applied the curve operation $a$ times, an attacker might obviously also have the computing power to conduct a brute-force search for $a$. In fact, the repeated application of the operation is performed using exponentiation by squaring, effectively obtaining the result in time $\mathcal O(\log a)$ instead of $\mathcal O(a)$. It is based on the observation that, when $a=2a_h+a_\ell$ with $a_\ell\in\{0,1\}$, then
$$g^a = (g^2)^{a_h}\cdot g^{a_\ell}\text.$$
Recursively applying this identity to compute $(g^2)^{a_h}$ until $a_h$ is zero requires a number of steps proportional to the bit length of $a$. When $a=\sum_{i=0}^ra_i2^i$ with all $a_i\in\{0,1\}$ is the binary representation of $a$, this yields the formula
$$g^a=g^{\sum_{i=0}^ra_i2^i}=\prod_{i=0}^rg^{a_i2^i}\text.$$
(Without using formulae, this means: For each $i$ where the $i$th least significant bit of $a$ is set, take $g$ and square it $i$ times. That is, set $t:=g$ and repeat the assignment $t:=t^2$, i.e. apply the curve operation to $t$ and $t$ and call the result $t$ again, $i$ times. Do this for all $i$ and combine the resulting $t$s using the curve operation.)


Is there a way to use a one-way hash function for both sides to "ratchet" an asymmetric keypair?

Is there any way to derive a series of asymmetric keys, such as using a one-way hashing function, where both sides can predict the next in the sequence?

Here is one way, based on elliptic curves (or finite field based on discrete logs); one such public key encryption method is the Integrated Encyption Scheme.  Now, it does have the drawback that if the attacker learns a prior public key, he can then (with knowledge of the current private key), he can learn the prior private key.  However, this limitation may still be acceptable to you.
In such a scheme, there is a private key (which is an integer $p$ in the range $[0, q)$), and the public key is a point $P = p \cdot G$ (where $\cdot$ is point multiplication if you're using elliptic curves, and exponentiation, more commonly written as $G^p$ if you're using a finite field group).
To ratchet the key forward, the two sides would compute:

Private key: $p' = hash(P) \times p \bmod q$
Public key: $P' = hash(P) \cdot P$

(where $hash$ is a cryptographic hash function).
This works, in that the relationship between the new public key $P'$ and new private key $p'$ still holds; $p' \cdot G = hash(P) \times p \cdot G = hash(P) \cdot P = P'$.
In addition, it is ratcheting; given $p'$, you cannot recover $p$ without knowing the hash of $P$ (and we assumed that he doesn't know that)


I'll assume that you a prefix-free encoding (or fixed-length messages) to solve that problem of CBC-MAC. It's actually very possible that this would be secure since the proof of CBC-MAC pretty much works by showing that the input to each block is random. Thus, it's conceivable that it will be secure when using the result as a key (since it's also random). However, I say just "conceivable" because you would have to formally prove this.

I'll just note that in practice this would be a terrible idea since it would require a new key schedule for every block. That would be really inefficient (e.g., for AES).


What does it mean for a random number generator to be cryptographically secure?

What are the criteria that make an RNG cryptographically secure?

In short, a DRBG [deterministic random bit generator] is formally considered computationally secure if a computationally-limited attacker has no advantage in distinguishing it from a truly random source.

What does this mean? Given a DRBG F and a truly random oracle G, let A be a probabilistic "attacker" that accepts F or G and outputs 1 or 0 after making queries to the function it was given. We define the attacker's advantage Adv to be |Pr[A(F)=1] - Pr[A(G)=1]|. If Adv is non-negligibly more than zero, the DRBG is considered broken. In this definition, note that it doesn't matter what returning 1 or 0 "means", just that we care only if A has a different probability of returning one or the other when given F and G.

In English, if there exists a computable function that can reliably tell the difference between a black-box DRBG and a black-box truly random function, then we consider it a break of the DRBG.

  Why must your RNG be cryptographically secure? I.e., what are the consequences if it is not?

This is probably far too broad a scope for a question like this. In some cases it doesn't have to be. In some cases even a slight weakness can cause a near-total loss of confidentiality or authenticity. The implications of a weak RNG are completely dependent upon the system and context in which it is used.

  Examples of secure and insecure RNG's

There are multiple kinds of DRBGs, intended for different purposes.

Yarrow and, later, Fortuna are algorithms that accept as input entropy sources of unknown quality, mix them, and produce entropy streams with strong guarantees as output. They have self-healing properties that resist injection attacks; even if an attacker controls almost all of the inputs, after a finite amount of time, the outputs will become indistinguishable to the attacker.

This is an extremely useful property for system RNGs such as those used by operating system kernels and provided to userspace through /dev/urandom, getentropy(2), and CryptGenRandom() (note: these interfaces may or may not actually use Yarrow or Fortuna, they are just examples of the types of system RNGs those algorithms were designed for).

Stream ciphers like ChaCha20 or block ciphers in streaming modes like CTR are really just cryptographically-seeded DRBGs. These algorithms aren't designed or intended to defend against an attacker injecting predictable inputs as the aforementioned algorithms were, but they produce nearly-infinite streams of randomness at very high speed given only a small initial random key and IV. These streams can then be XORed against a plaintext to produce a cryptographically-strong ciphertext. Even better, these algorithms are typically seekable; given a key, IV, and long ciphertext, you can generally seek far into the ciphertext and decrypt individual bits without needing to compute the entire stream.

I won't list insecure DRBGs here. There are simply too many to list, and the general assumption should be that a DRBG is not secure unless demonstrated otherwise.

  Would a non-psuedorandom generator be cryptographically secure? E.g. one based on radioactive decay of a particle

Non-pseudorandom generators are the only generators that are even capable of being information-theoretically secure, which is a significantly stronger metric than computational security. With a computationally-secure DRBG, a small seed of n bits is expanded into a larger cryptographic stream; that larger stream still is only one selection of at most 2^n possible streams.

Quantum sources of randomness such as radioactive decay and thermal noise are by physical definition truly random.


Can authenticated encryption reduce bandwidth overhead of per-packet encryption?

GCM supports multiple authentication tag sizes.  To the extent that overhead outweighs security in your application, you perhaps could use GCM with reduced tag size.  You'd be settling for a lower security level, so that needs to be thought through very carefully.

The common requirements on the use of IVs are the following:

The sender and recipient must agree on what the IV is for each encryption/decryption pair.  Even better, they should authenticate the IV.
Other additional requirements that the cipher imposes on IVs.  The two typical ones:

Some ciphers require the IVs to be a nonce—that two encryptions with the same key never reuse the same IV, or otherwise the cipher may fail catastrophically.  CTR and GCM are like this.
Other ciphers require the IVs to be random.  CBC is like this.

Requirement #1 is often achieved by sending the IV along with the ciphertext, but this is just one way of achieving the goal.  The alternative would be to have some protocol where the parties can locally generate the correct IV for each encryption/decryption pair without having to individually transmit them. Many solutions are possible here.  One very simple scheme, suitable for nonce-based ciphers, is to treat the IV as a counter.  The documentation for the NaCl library has an example trick worth quoting:

  Distinct messages between the same {sender, receiver} set are required to have distinct nonces. For example, the lexicographically smaller public key can use nonce 1 for its first message to the other key, nonce 3 for its second message, nonce 5 for its third message, etc., while the lexicographically larger public key uses nonce 2 for its first message to the other key, nonce 4 for its second message, nonce 6 for its third message, etc.

This does require that recipient be able reconstruct the order in which the sender used encrypted the messages.  But there are other ideas that can help if that's a problem:

If your messages carry some plaintext metadata that contains values that offer some uniqueness guarantee, you might be able to use that metadata as an input to compute a unique or pseudorandom nonce.
You could put a variable-length encoding of the counter into the datagrams along with the ciphertexts, and have the recipient expand the counter values to the full IV size for decryption.

Note that these implicit IV techniques stress the importance of authenticating the IV as well as the ciphertext, otherwise active attackers may be able to fool you by reordering, deleting or adulterating packets. (Authenticated encryption modes like GCM implicitly authenticate the IV already, however.)


Advantages of Pallier vs Goldwasser-Micali

They're both additively homomorphic, but over different groups.

With Goldwasser-Micali, you can, given $E(x)$ and $E(y)$, compute $E(x \oplus y)$ (where $\oplus$ is exclusive or)

With Pallier, you can, given $E(x)$ and $E(y)$, compute $E(x + y \bmod n)$, where $n$ is a large integer; this implies that, given $E(x)$ and $k$, you can compute $E(kx \bmod n)$

Which is appropriate depends on what operation you need to perform on the encrypted data.

In my experience, we almost always want the operations that Pallier provides.


Does ChaCha20 counter actually increment through iterations?

You seem a bit confused about how the various parts of the ChaCha20 cipher actually fit together, so let me start from the top down and see if I can clarify things.

At the highest level, the ChaCha20 encryption algorithm is a synchronous stream cipher: given a secret key and a (possibly) public nonce, it generates a pseudorandom keystream which is bitwise XORed with the message to be encrypted.  Repeating this process (i.e. XORing the encrypted message with the same pseudorandom bitstream again) then lets the receiver reveal the original message again.

(The purpose of the secret key is to ensure that no-one else can generate the same keystream, and thus decrypt the messages.  The purpose of the nonce is to ensure that we never use the same keystream for encrypting two different messages, since that would allow an attacker to cancel out the keystream by XORing the encrypted messages together, leaving them with the bitwise XOR of the original plaintext messages.  So, no, the nonce doesn't need to be secret — all it needs to be is unique.)

The keystream is generated by concatenating a sequence of 512-bit blocks, each of which is generated by applying the ChaCha20 block function to an initial 512-bit input block consisting of the key, the nonce, a block counter and a fixed 128-bit constant.  The reason why the block counter is needed is because the ChaCha20 block function is deterministic, and would thus always produce the same output block if given the same input.  We don't want the keystream to consist of just the same 512-bit block repeated over and over, so we include a counter in the input block to make sure that every input to the ChaCha20 block function is different.

(This is essentially the same as the CTR mode construction for making a synchronous stream cipher out of a block cipher, except with the ChaCha20 block function used in place of the block cipher.)

Finally, going one level deeper yet, the ChaCha20 block function scrambles its input by iteratively applying 10 "column rounds" and 10 "diagonal rounds" to it, in alternating order (and then finally XORing the scrambled result with the original input to make the whole thing non-reversible).  Each of these column rounds and diagonal rounds, in turn, consist of four (possibly) parallel applications of the ChaCha20 quarter round  function, which takes a 128-bit slice of the full 512-bit block and scrambles it in a particular way, as described in the linked RFC.

All that iterated scrambling ensures that even tiny changes to the input block (like, say, incrementing the block counter by one) will cause the output of the block function to look completely different.  Thus, even though the successive inputs to the block function for any given message are all the same except for the counter, the keystream obtained by concatenating the scrambled output blocks is effectively indistinguishable from random, unless one knows all the inputs that went into generating it (including, in particular, the secret key).

Of course, to deterministically generate the keystream from a given key and a nonce, we need to decide how to choose the initial counter value for the first block, and how to increment it for the later blocks.  (If we don't do it consistently when encrypting and decrypting, the keystreams will be different and we won't get the original message back!)  The obvious choice would be to number the blocks consecutively as 0, 1, 2, 3, 4, …, but in principle other methods could work just as well.

Indeed, the RFC you linked to describes the ChaCha20 encryption algorithm as taking the initial counter value as an input, in addition to the key, the nonce and the message to be encrypted (or decrypted), and describes it as follows:

  A 32-bit initial counter.  This can be set to any number, but will
    usually be zero or one.  It makes sense to use one if we use the
    zero block for something else, such as generating a one-time
    authenticator key as part of an AEAD algorithm.

Note that this is the initial counter value, used to generate the first 512-bit block of keystream, and incremented by one for every subsequent block.  So if the initial counter value is set to 0, the blocks will be numbered as 0, 1, 2, 3, 4, …, whereas if it's set to 1, the blocks will be numbered 1, 2, 3, 4, 5, … instead.

So why would you choose to set the initial counter value to something other than 0?  Well, probably because you want to start the keystream at some later block number, e.g. because you already used block 0 for something else.

In particular, the AEAD_CHACHA20_POLY1305 authenticated encryption scheme works by using block 0 of the ChaCha20 keystream to generate the one-time Poly1305 key for protecting the integrity of the encrypted message, and then using the rest of the keystream starting from block 1 to actually encrypt the message as described above.


I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).

One typical approach is that the parties will treat the CRS as the public key of an encryption scheme, and encrypt their inputs under this key. They can prove things about this ciphertext in zero-knowledge for the rest of the protocol. This overall approach is useful because the simulator can generate the CRS to be a public key for which it knows the corresponding secret key, and therefore decrypt the parties' encryptions of their inputs. An example of this approach is in Canetti et al.

Beyond this, CRS is a fundamental part of the syntax for non-interactive ZK (NIZK). If the simulator generates the CRS with a trapdoor, they can generate proofs of false statements. But without the trapdoor, only proofs of true statements can be generated.

Another cute and totally different approach for a CRS is from Peikert et al. They construct oblivious transfer protocols in the CRS model. The CRS can be of two different flavors. If the CRS is of one flavor (think of a Diffie-Hellman triple $g^a, g^b, g^{ab}$) then the protocol can be proven information-theoretically secure against the receiver. If the CRS is of the other flavor (think of a random triple $g^a, g^b, g^c$) then the protocol can be proven information-theoretically secure against the sender. The fact that the two CRS flavors are indistinguishable means that the protocol actually gives (computational) security against both parties.

  I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.

If you have authentic channels, then you can get secure channels using standard public-key encryption. So it is standard to just assume secure point-to-point channels. The bigger challenges are: (1) how to get broadcast from point-to-point channels; (2) what happens when you don't assume even authentic channels?

(1) is relatively standard. There is very little work on (2), but one paper I know of is Barak et al. Basically, without authentication it is inevitable that the adversary can partition the honest parties into disjoint and isolated groups, that each perform their own separate computation.

  If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?

You can bootstrap privacy from nothing (using key agreement), but you can't bootstrap authenticity from nothing. PKI is the root of trust for authenticity.


Who assigns algorithm OIDs for cryptographic algorithms?

No, there isn't a single one that takes care of the algorithms. Many algorithms do not have an OID, and many proprietary ones have OID's that aren't known.

The OID's are strictly hierarchical. The first digit is either 0, 1 or 2 indicating ITU-T, ISO or both. ITU-T and ISO are both international standards organizations that are then responsible for the next digits. This may include internal associations, but they may also be other organizations. Those organizations are then responsible for their part of the tree.

Of course, if anything is standardized by e.g. ISO then it will probably get an identifier somewhere in the tree of ISO. It could however be that the algorithm is already registered somewhere else, and in that case it may not get a new one. Or it could and you would have two ones identifying the same thing. It is up to the protocols to choose which ones you should use.

As there isn't one global registration authority for the insurmountable amount of algorithms, there isn't a single location in the tree either. And there doesn't need to be: an ID doesn't need to be ordered.

Commercial entities

It is perfectly possible for a commercial organization to get their own space in the OID tree:

{iso(1) member-body(2) nl(528) nederlandse-organisatie(1) enschede-sdu(1006)}

This space seems empty but the organization no doubt build their own tree internally. In this case I have very little doubt, in fact.

Examples

{joint-iso-itu-t(2) country(16) us(840) organization(1) gov(101) csor(3) nistAlgorithm(4) aes(1) aes128-CBC(2)}

So here the joint ISO / ITU-T has created a space for countries, and those countries can decide how to create their trees. Here CSOR is part of NIST, which has created a subspace for AES and then CBC mode.

 {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsassa-pss(10)}

Here ISO identified the US, who has identified the RSA digital signature algorithm, PKCS#1 / PSS version.

{iso(1) member-body(2) us(840) ansi-x962(10045) signatures(4) ecdsa-with-SHA2(3) ecdsa-with-SHA384(3)}

Same thing, but now a national standardization institute: ANSI has created a standard with associated OID's.

Configuration

Important note: there are generally two ways of handling algorithms and OID's in data structures such as ASN.1, shown in the following X.509 (certificate) specification:

 AlgorithmIdentifier  ::=  SEQUENCE  {
      algorithm               OBJECT IDENTIFIER,
      parameters              ANY DEFINED BY algorithm OPTIONAL  }

every algorithm is fully identified, including any configuration option and the parameters are not present or NUL
the algorithm is specified, but it requires additional parameters to be specified.

You can see this in the above examples where the ECDSA algorithm is defined with the hash, while RSA PSS requires additional configuration parameters.

Structure?

For some fun, please see the following quote in the OID database here:

  To the question "Are the OIW OIDs still in common use?", Peter Gutmann replied on June 23, 2004: "Some of the crypto ones still in use, this would include the DES-modes OIDs and some of the weird (obsolete) Secure Hash Algorithm (SHA) and Digital Signature Algorithm (DSA) ones that were (incorrectly) copied into Java Cryptography Extension (JCE) implementations. Examples of obsolete OIDs: {iso(1) identified-organization(3) oiw(14) secsig(3) algorithms(2) sha-1WithRSAEncryption(29)}; an obsolete DSA one that ended up in Common Data Security Architecture (CDSA) (so presumably "OS X crypto" will use it) and the German Public Key Infrastructure (PKI) work; and a variety of other odd bits and pieces. In general you need a many-to-one mapping where on write you emit the most appropriate OID and on read you allow any one of a number of OIDs, including incorrect ones (the Java Development Kit (JDK) one is actually dsaWithSHA0, but it's used as if it was dsaWithSHA1)."

Please do not expect all that much structure in the OID tree.


Padding methods for block ciphers - PKCS7 vs ANSI X.923

This site is a reference for padding:

http://www.di-mgt.com.au/cryptopad.html

Method 3 refers to the ANSI X.923 and method 1 refers to PKCS7.

The main advantage listed is that PKCS7 allows you to double check the number of padding bytes


I do not think this is a practical possibility. In order to get the 4-5 most significant bits, the bits of lower significance must be known. This is due to the manner in which numbers are multiplied. The most significant bits of the product do not depend solely on the most significant bits of the factors. Bits of lower significance may have an effect too due to the propagation of carry bits up the product as partial products are summed. Even with some look-ahead optimizations the bits of lower significance would still need to be known. The best I could see would be a probabilistic scheme in which k>5 bits would would be attempted to be solved and the result would be probabilistically correct with some chance as a function of k.


what does 64-bit representation stand for?

It's the length (in bits) of the hashed message, expressed as a 64 bit binary value (in little endian order).  If you hash a 1 character message, $b=8$ (as 1 byte == 8 bits); this would be represented as the 8 bytes 08 00 00 00 00 00 00 00 (the 08 is first, because in little-endian order, you place the least-significant part first)

  what does lower-order bits mean?

The length of the the $b$ field within the padding is 8 bytes long; if you were to hash an extremely long message (one $2^{61}$ bytes or longer), it might be the case that $b$ wouldn't fit in an 8 byte field.  In that case, what you place into the field is the lowest 8 bytes into the field; another way to express this is that you place the value $b \bmod 2^{64}$ into the padding field.

On the other hand, $2^{61}$ bytes is an enormous amount of data; it is approximately the amount of data that flows over the internet globally in a day.  It is quite unlikely that you (or anyone else) will ever compute an MD5 hash on that much data; you can in practice ignore this sentence.


Does MAC provide origin authentication? Why not just use symmetric encryption?

Non-authenticated symmetric encryption schemes are generally malleable, meaning that an attacker who intercepts a message may be able to modify it even without knowing the key, e.g. by flipping arbitrary bits in it.  A MAC prevents such attacks by detecting any modifications made to the ciphertext.

Also, there are various chosen-ciphertext attacks that work by having the attacker feed bogus ciphertexts to a recipient with the key and observing the responses (such as whether the ciphertext decoded to a valid message or not).  A properly used MAC also prevents such attacks, since the attacker will not be able to generate messages that would pass the MAC check.

Finally, a MAC is also useful for detecting modifications to message metadata, which might otherwise allow replay attacks to be carried out.

Instead of combining a traditional symmetric encryption scheme with a MAC, it's also possible to use a purpose-built authenticated encryption scheme to achieve the same goals, sometimes more efficiently.  That said, many authenticated encryption schemes actually consist of a traditional scheme combined with a MAC, although the combination may be done in specific ways that offer some speed, convenience or misuse-resistance advantages over the generic encrypt-then-MAC construction.

Ps. If you want to be able to prove that a given message was sent by Alice to Bob and not, say, forged by Bob himself, you need a digital signature instead of a MAC.

However, note that, for some applications, the inability to verify a MAC without knowing the shared key can actually be considered a feature, since it provides a measure of deniability — if you're Alice, and your supposedly private conversation with Bob is somehow leaked, a MAC cannot be used to prove that you actually wrote the leaked messages, since anyone who can verify the MAC could also forge it.  In particular, the OTR messaging protocol uses MACs instead of signatures precisely for this reason.


Does the Message Integrity Check in WPA(2) standard solve the problem of non-repudiation?

No it doesn't.

Message Authentication Codes (MACs, which in networking some may call MIC in order to differenciate from Media Access Control) are symmetric-key primitives that only provides authenticity and integrity of the message exchange. Non-repudiation requires public-key cryptography.


What's a good strategy for the game "spyfall"?

I think the following protocol works:

Let's take a group where discrete logarithm is hard (say, a classic elliptic curve); I'll note the curve law with additions. Let $q$ be the group order (prime). Let $G$ be a conventional generator for that group. Let $H$ be a hash function whose output is a group element (the value $H(x)$ for an input $x$ should be such that nobody has any clue as to the discrete logarithm of $H(x)$ in base $G$). Let $h$ be another hash function that produces bytes (like SHA-256).

Each player $i$ generates a random value $x_i$ modulo $q$, and publishes (i.e. announces) $P_i = x_iG+H(loc)$ (where $loc$ is the secret location).

Once all $P_i$ have been broadcasted, each player $i$ then computes, for all other players $j$, the values $s_{i,j} = x_i(P_j-H(loc)) = x_ix_jG$. The important point here is that $s_{i,j} = s_{j,i}$ for all pairs $(i,j)$.

Then, each player $i$ publishes the list of values $t_{i,j} = h(i||j||s_{i,j})$ for all $j\neq i$. Each value $t_{i,j}$ can be computed by the player $i$ and the player $j$.

Each player $i$ recomputes all the $t_{j,i}$ and compares them with the received values. If all players follow the protocol, then they should all match, except the one from the spy (if the spy did not guess the location correctly when computing his own point $P$). The player $i$ can then detect the spy, and, in that situation, all other honest players have also detected the spy, so they all agree when he is accused.

On the other hand, if the spy did guess the location properly, then he will notice that all the received $t_{j,i}$ match his own recomputed $t_{j,i}$, confirming his guess, and he can proceed to winning the round. I don't think this case can really be avoided, on a general basis: the spy can always get lucky with his initial guess, in which case he cannot be uncovered by any protocol, and thus he can infer the correctness of his guess by his own survival.

The protocol above is an extension of the Encrypted Key Exchange, the first PAKE protocol to be published, by Bellovin and Merritt in 1992.

It's clear that the $P_i$ points reveal no information on the secret location. If $h$ behaves like a random oracle, then the spy may extract information from any published $t_{i,j}$ value only by guessing exactly the value $s_{i,j}$, i.e. by breaking the EKE between $i$ and $j$.


What is the purpose of calculating the N modulus in the encryption phase of asymmetric cryptography?

What am I missing?

Not much; you've just come across one of the reasons why we never use "raw RSA".  Instead, whenever we use RSA (say, for encryption), we always pad out the message so that, after padding, it's not much smaller than $N$.  This prevents the message from being less than $N^{1/e}$ (which, as you point out, would be completely insecure), and it also prevents subtler attacks based on the homomorphic properties of raw RSA (namely, $RSA(x)RSA(y) = RSA(xy)$


do koblitz curves over $\mathbb{F}_{P}$ as generalized in SEC2 always have $a$ as 0?

Neal Koblitz is an actual person who did more than one thing in his life. Notably, he proposed several types of curves, which are all "Koblitz curves", but not necessarily all following the same rules.

Generally speaking, the "Koblitz curves" we are talking about have a common property which is that they have an efficiently computable non-trivial endomorphism. An endomorphism $\phi$ maps a curve point to another curve point, with the property that for any two curve points $P$ and $Q$, then $\phi(P+Q) = \phi(P) + \phi(Q)$. When working over a curve of prime order $n$ (or a subgroup of the curve, of prime order $n$), then an efficient endomorphism $\phi$ is necessarily equivalent to multiplying by a given scalar $k$. The endomorphism is said to be "efficient" if it can be computed faster than usual multiplication of a point by a scalar.

On binary fields $\mathbb{F}_{2^m}$, Koblitz proposed curves that are actually defined over $\mathbb{F}_2$. In $\mathbb{F}_2$, there are only two values, $0$ and $1$. Thus, the curve equation $y^2 + xy = x^3 + ax^2 + b$ must be such that both $a$ and $b$ are in $\mathbb{F}_2$, i.e. are $0$ or $1$. Then, that curve equation is used over the field $\mathbb{F}_{2^m}$, which is an extension of degree $m$ over $\mathbb{F}_2$ (we usually use a prime $m$). Such a curve has some interesting property:

Its order is easy to compute. No Schoof/SEA shenanigans, just some plain additions and multiplications.
Since $\mathbb{F}_2 \subset \mathbb{F}_{2^m}$, the curve on $\mathbb{F}_2$ is a subgroup of the curve on $\mathbb{F}_{2^m}$. Hence, the order of the latter must be a multiple of the order of the former. This prevents the full curve from having prime order. If $m$ is prime, though, then it is possible to have the full curve order be the product of a big prime with either $2$ or $4$, which is considered good enough for cryptography. Indeed, the order of the curve over $\mathbb{F}_2$ is $2$ if $a = b$, $4$ if $a \neq b$.
If $b = 0$ then the curve is singular and various problems occur (and it's not good for cryptography). So we can assume that $b = 1$.
The efficiently computable endomorphism is $\phi(x,y) = (x^2,y^2)$. This is known as the Frobenius endomorphism. In a binary field, squaring is an automorphism (notably, $(u+v)^2 = u^2 + v^2$, for all values $u$ and $v$), which makes that operation "compatible" with the curve equation, as long as $a^2 = a$ and $b^2 = b$, which is the case since we chose both values to be $0$ or $1$.
Applying the Frobenius endomorphism $m$ times brings you back to the original point. This, in fact, defines $m$ endomorphisms. A consequence is that it reduces difficulty of discrete logarithm by $(\log m)/2$ bits, which is not a big deal (it means with with $m = 283$, you do not get "141-bit security" but closer to "136-bit security").

The endomorphism can be used for an efficient point multiplication in which point doubling is replaced with application of the Frobenius endomorphism.

On prime order fields $\mathbb{F}_p$, with $p = 1 \bmod 3$ a prime number, Koblitz proposed equation $y^2 = x^3 + b$ (i.e. $a = 0$ in the usual short Weierstraß equation):

Since $p = 1 \bmod 3$, then there are three distinct cubic roots of $1$ in the field. One of them is $1$. Let's call $u$ another cubic root of $1$; the third cubic root is then $u^2$. The roots are linked with the relation $1 + u + u^2 = 0$.
The efficient endomorphism is $\phi(x, y) = (ux, y)$. You can trivially verify that for any point $P$, $\phi(P)$ is indeed a curve point. Less trivially (you have to work it through the addition formulas), this is indeed an endomorphism.
The endomorphism can be used for speed up point multiplications, but not as much as the Frobenius endomorphism in the binary case. The reason is that applying $\phi$ only three times brings you back to the start point. In that sense, it is "less powerful" than the point doubling operation, and cannot be used to replace all doublings in a multiplication. It can still help avoiding half of the doublings; this is known as a GLV curve. This optimization is not often implemented because it has a few hidden costs and is hard to do with pure constant-time code.
If we use the same equation with a prime $p$ such that $p = 2 \bmod 3$ then we get a supersingular curve, with exactly $p+1$ points. Such a curve allows for efficient pairing computations with a very small embedding degree (only $2$, since $p^2-1$ is a multiple of $p+1$). In other words, you need a much larger $p$ to achieve decent security, and that kills performance; this is done only if you want a pairing for advanced things such as identity-based encryption. Even for that, there are better pairing-friendly curves (e.g. Barreto-Naehrig).

Both types of curves are "Koblitz curves", but certainly not the same kind of curve.

In practice, curves on binary fields are being abandoned, because it turned out that we don't have a good intuition about what happens on binary fields, and cryptographers got afraid and panicked. They may be back, much later on, when the current generation has died away. The other type of Koblitz curves, on prime fields, is well alive and kicking; for instance, the main curve in Bitcoin is secp256k1, with equation $y^2 = x^3 + 7$.


Why does the one-time pad not imply $P \not= NP$?

A one time pad is secure regardless of complexity. When you have a ciphertext all plaintexts are equally likely and you have no way to verify a guess. Even an attacker which enumerates all possible keys will not learn anything he didn't know already. Thus it doesn't have anything to do with complexity.

A one way function on the other hand implies $P \ne NP$. Any function which is easy to compute in one direction but hard to find a pre image. Since finding a preimage of a polynomial time function is in $NP$.

Note it is possible that no one way functions exist and and still $P$ does not equal $NP$.

A one time pad is not a one way function. It is trivial to find a preimage We can find as many preimages as we want we can't tell them apart.


Is there a standard or recommended format for encrypted data, with algorithmic agility?

The layout of the format doesn't matter much.  I would recommend combining all the parameters into a single cipher suite name so that you're not tempted to make nonsensical combinations: just use NaCl crypto_secretbox_xsalsa20poly1305 (or AES-GCM if you must use AES, with the caveat that it subjects your users to side channel attacks on software AES implementations), not your own composition of AES256-CTR with HMAC-SHA256.

What matters much more is:

How many cryptographic decisions are imposed upon users who are not competent to answer questions on this site?  Correct answer: none.

For example, although the scrypt file format has some options, there are no cipher fields—just a format version number.  There are cost parameters for the password-based key derivation function, but when creating files, even those are automatically calibrated by the scrypt utility by default, with the option to specify them manually.
How are the parties in the system to behave when fed instances of the format?  Be careful to specify protocol, not just data.  How do you use the key and act on the file?

If you are using a key for a particular purpose, say an RSASSA-PSS public verification key, do not let the format dictate another purpose.  The implementation ecosystem of JavaScript Web Tokens, JWT, is a disaster because it was designed as a lofty view of data, abstracted from the reality of protocols.

JWT implementations often expose a generic verify(token, key) function which uses key however the attacker-controlled token prescribes.  Even if you meant for key to be an RSASSA-PSS public verification key, token might say ‘hey, JavaScript chump, please use HMAC-SHA256!’, and you, the chump who used JWT, will happily use the ‘RSASSA-PSS public verification key’ in the place of an HMAC-SHA256 key which enables trivial forgery since RSASSA-PSS public verification keys are, well, often public.


What is the link, if any, between Zero Knowledge Proof (ZKP) and Homomorphic encryption?

There are many.

Homomorphic encryption implies ZK proofs for NP. This is simply because homomorphic encryption implies one-way functions, which imply ZKP for NP.
Homomorphic encryption allows to compile any public-coin zero-knowledge proof into a designated-verifier non-interactive zero-knowledge proof; this was shown in the paper Non-interactive Zero-Knowledge from
Homomorphic Encryption.
Zero-knowledge proofs are not known to imply anything regarding the existence of homomorphic encryption. In fact, only very strong forms of zero-knowledge proofs were very recently shown to imply public-key encryption.
Fully homomorphic encryption can be used to minimize the size of a non-interactive zero-knowledge proof, and reduce it to witness size + polynomial in the security parameter, see this paper.

This is just a sample of the many interplays between the two notions; if you had more specific relations in mind, please clarify.


Is it possible to create a Bilinear Function with Already Assigned "Multiplicative" Input Groups?

If you can find such an efficiently computable function (other than the trivial solution $\hat{e}( x, y ) = 1\ \ $ for all $x$, $y$), then you have shown that the decisional Diffie-Hellman problem is easy.  That is, given $g$, $g^a$, $g^b$, $g^c$, you can check whether

$$ab = c$$

simply by testing:

$$\hat{e}( g^a, g^b ) = \hat{e}( g, g^c)$$

The decisional Diffie-Hellman problem is believed to be hard in appropriately sized Multiplicative Cyclic groups, hence we believe that there is no such efficiently computable $\hat{e}$