Can I safely replace XOR with ADD in a stream cipher?

On software platforms, bytewise adding will not be faster than bitwise XORing. It may be a bit slower, though, also this will be negligible with regards to the process which generated the stream (and, for that matter, will probably also be negligible with regards to the memory bandwidth).

On hardware platforms (FPGA, dedicated ASIC), addition is slower than XOR because of the need to propagate carries. A XOR is a simple layer of XOR gates, so it has minimal depth and minimal area; an addition requires more gates (so more area) and carry propagation over $n$-bit words requires a circuit of depth at least $\log n$, so the addition will induce more latency as well. The overhead will be probably limited for mere bytes, but it will never be as efficient as a XOR.

The only kind of architecture where adding would be somewhat faster than XORing would be an architecture which offers addition/subtraction primitives, but not XOR, or not as efficiently. This may be the case for some DSP, or possibly for some Javascript interpreters (in Javascript, numbers are thinly-disguised IEEE 754 floating-point values, and bitwise operations entail conversions to and from integer types). I still think that for most platforms (including recent JIT-able Javascript interpreters), the XOR will not be slower than bytewise addition.

As for security, bytewise addition is as good as XOR. Indeed, XOR is bitwise addition (XOR is the addition in $\mathbb{Z}_2$).


Difference between secure function evaluation and private function evaluation?

You will find similar terminology interchanged a lot in this field. So, secure multiparty computation can take the acronym MPC, SFE, SMC and so on. In general, you should look at each paper closely to see what they mean in their definition. However, pretty much secure function evaluation is just another term for secure computation. In contrast private function evaluation can refer to the case where the function itself is private and is not revealed. Note that these are completely orthogonal to the number of parties involved.


Efficiency of McEliece cryptography (ciphertext expansion)

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?

Not really; or at least, that's not an inefficiency we care about.

A length of 1024 means, in this context, 1024 bits (or 128 bytes).  This compares favorably to RSA (for which a key with a 1024 bit ciphertext has questionable security).  More importantly, a ciphertext of 1024 bits is fairly cheap to transport; it fits extremely easy in an IP packet (if we're communicating over IP); over wireless (which we tend to be sensitive to message length due to power reasons), it's still not too bad.

The reason we don't use McEliece now is the "expense"; that is, those parts of the cipher that make it costly to implement.  And, the expensive part of McEliece is the public key (which is circa 200kbytes); we could fit it into a certificate, or pass it as an authenticated part of the key negotiation protocol, but it would be painful.  Most everything else about McEliece (the ciphertext size, the computational effort) are things we can easily live with (with the possible exception of the private key; we don't have to worry about transporting that around, but we still need to store it securely).


You cannot, at least not if that's the only encrypted image. ECB leaks information because repeated plaintext blocks lead to repeated ciphertext blocks. But it doesn't leak the information within those blocks directly.

So you could find the original size by finding another encrypted picture with the same header of which you already know the size. In that case the encrypted header should be identical.

Otherwise, smart guessing might be the best way forward. If you look at the vertical lines then there should be a high amount of repetition between one horizontal line and the next. Just shifting the image and selecting the one with the most vertical repetition should do the trick.


TLS handshake with client later on acting as a server

Is it possible that a client which gets the Digital certificate of the Server during the TLS handshake then acts as a server? Because a server only needs to have a valid digital certificate which it already possesses.

Are you asking whether a client can take the certificate it receives from the server, and later pose as that server?  No, it cannot - in addition to the certificate, it would also need the private key that corresponds to the public key that's in the certificate.  That is, later on in the TLS protocol, the server is required to perform some operation that depends on the private key (which might be decrypting a value encrypted with the public key, or it might be signing some data - which it is depends on the ciphersuite and TLS version).

That private key is not sent through the TLS handshake, and so the client would not be able to perform either of these actions.  Hence, just the information that the client learns via the TLS connection is insufficient.


How blockchain system manages it's memory limit for nodes?

Right, most cryptocurrencies store all transaction data in the blockchain, which must be available to every node. You're right that this is a big problem for scalability.

There are several different kinds of strategies being developed to further improve cryptocurrency scaling. These strategies generally either involve sharding the blockchain into multiple related blockchains, so each node only needs to have some subset of the full blockchain (see Ethereum's Sharding FAQ), or moving transactions off-chain (Bitcoin's Lightning Network, state channels, Ethereum's Raiden, etc). Off-chain transaction systems build off of the idea that if two people are sending money back and forth between themselves, they can architect some smart contracts so they can send the transactions privately and instantly between themselves off-chain, and make an on-chain transaction containing all of the private transactions to safely reclaim their money if either defect, and a network can be formed between pairs of users like this to allow instant off-chain transactions between any two people in the network.


Let's say you are party $I$, and your friend is party $J$, secret values are $a$ and $b$. The result of the multiplication would look like:

$$
a.b = (a_i \oplus a_j) . (b_i\oplus b_j) = (a_ib_i) \oplus (a_ib_j) \oplus (a_jb_i) \oplus (a_jb_j)
$$
$I$ and $J$ already have these shares and need no communication for $a_ib_i$ or $a_jb_j$. But for $(a_ib_j)$ and $(a_jb_i)$, they do need other's input. $I$ selects a random value r and creates a table with four entries depending on the values of $I$'s and possible values of $J$ with entries $e$ like $r \oplus a_ib_j \oplus a_jb_i$.

$$
\begin{align}
a_j = 0,b_j &= 0: e = r \\
a_j = 0,b_j &= 1: e = r \oplus a_i \\
a_j = 1,b_j &= 0: e = r \oplus b_i \\
a_j = 1,b_j &= 1: e = r \oplus a_i \oplus b_i \\
\end{align}
$$

Although these entries look confusing, note that $J$ already knows $a_j$ and $b_j$ values. And any if these entries are $0$, then look at the equation $r \oplus a_ib_j \oplus a_jb_i$. This would have one or two entries evaluate to $0$. That is why the table was constructed that way. Clearly, if $I$ and $J$ engages in a 1-out-of-4 Oblivious Transfer protocol now, then $J$ can only retrieve one entry from the table. So $I$ would be having the random number $r$ and $J$ would be having the computed value xor'ed with $r$. Meaning they share the multiplication result but not the result itself.


In SRP, is the client protected from server impersonation?

Yes (and it is an explicit goal of SRP; perhaps not as advertised as such)

The only attack that SRP allows is for the faux server to take a guess at the password, and then attempt to allow the client to login based on that guess (and if the client thinks he succeeds, the guess was correct).

Given that we assume that the password was strong enough to make that unlikely, you're safe.


Question about CTR_DRBG Instantiation specification

I believe the comment is explaining the next line:

seed_material = df(seed_material, seedlen)


Break RSA when modulus is of the form $N = pq$ with $|q^2 - p|$ small

You can find the factor $q$ just by taking the cube root of $N$ and rounding to the nearest integer!

If $N = pq$ where $p = q^2 + \delta$, then: $$\sqrt[3]N = \sqrt[3]{q(q^2 + \delta)} = \sqrt[3]{q^3 \left( 1+\frac{\delta}{q^2}\right)} = q \cdot \sqrt[3]{1+\frac{\delta}{q^2}}.$$

Thus, as long as $2|\delta| < q$ then, given that $|1-x| \le |1-x^3|$ for all $x \ge 0$: $$\left|q - \sqrt[3]N\right| = q\left|1 - \sqrt[3]{1 + \tfrac{\delta}{q^2}}\right| \le q\left|1 - \left(1 + \tfrac{\delta}{q^2}\right)\right| = \tfrac{|\delta|}{q} < \tfrac12,$$ and so $\sqrt[3]N$ rounds to $q$.

(A more precise calculation, using the fact that $q \ge 2$ and that $|1-\sqrt[3]{1+x}| \le \frac{|x|}2$ for all $|x| \le \frac12$, shows that this actually works even up to $|\delta| < q$.)

More generally, even if $|\delta|$ could be several times as large as $q$, you could still solve the problem efficiently by starting with the approximate solution $\tilde q = \sqrt[3]N$ and testing nearby integers $q \approx \tilde q$ until you find one that evenly divides $N$.


Why is it claimed that ElGamal is worse than RSA?

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including

public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
decryption speed (ElGamal as usually practiced wins),
combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...

As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.


In general an affine subspace is not a subspace, it's just a translate (coset) of a subspace. This is because normally we expect $0$ to be in a subspace $V$, since due to closure $x-x \in V.$

If $a+V$ is an affine subspace for $a\neq 0,$ and $V$ a subspace then automatically $a$ is required to be not in $V.$ Otherwise $a+V=V.$


Modular exponentiation with Chinese Remainder Theorem

First, you got the last line wrong, it's
$$M^e \bmod{pq} = C_q+q(q^{−1}(C_p−C_q) \bmod p)$$

The basic idea of the CRT is that if $a$ and $b$ are relatively prime, working modulo $ab$ is the same as working modulo $a$ and modulo $b$ separately. In the case of modular exponentiation, exponentiating an element modulo $a$ and then modulo $b$ is much cheaper than modulo $ab$, because you can work with smaller exponents.

About that last step, it's standard CRT computation, you have
$$\left\{\begin{array}{l}
M^e \equiv C_p \pmod p \\
M^e \equiv C_q \pmod q
\end{array}\right.$$

The second line gives $M^e = C_q+kq$. Plugging that into the first gives $C_q+kq \equiv C_p \pmod p$, so $kq \equiv C_p-C_q \pmod p$. Since $p$ and $q$ are relatively prime we can take $q^{-1} \bmod p$, so $k \equiv q^{-1}(C_p-C_q) \pmod{p}$, so $k = q^{-1}(C_p-C_q) + k'p$. Plugging that into $M^e = C_q+kq$ gives the desired expression.


Use of the master key in Delerablée's Identity-based Broadcast Encryption

That value can be computed with the data you have in the public key. You just need to use the fact: $$ h^{\gamma} \times h^{H(ID)} = h^{\gamma + H(ID)}. $$

Note that in the public key you have all the $h^{\gamma^i}$ you need for the computation.

The notation used in the paper is there to keep the notation easy and clear.

If you want to compute the correct value you could compute the product:
$$\pi = \prod_{i=1}^s (\gamma + H(ID_i))$$ considering $\gamma$ as unknown and later compute $h^\pi$ making the needed substitutions.


What is the (classical) algorithm of choice for finding discrete logarithms in composite-moduli groups?

Suppose you had a discrete log oracle giving $\mathcal O(n, g, g^x) \equiv x \pmod{\phi(n)}$ with high probability for random $g$ and $x$.  Pick a uniform random $g$ and a large random prime $k$; let $m = \mathcal O(n, g^k, g)$, so that $$(g^k)^m \equiv g \pmod n,$$ or $$g^{k m - 1} \equiv 1 \pmod n;$$ then the order of $g$ modulo $n$ divides $k m - 1$.  This gives an oracle to find the order of a random element (or some multiple of it).  As you observed, this is enough to factor $n$ with modest additional effort.

Hence any algorithm you can use to compute discrete logs modulo a composite $n$ can't be much cheaper than an algorithm to factor $n$: there can't be much to be gained by attacking discrete logs directly.  So it's not surprising that the state of the art for both is some variant of the GNFS.


Public key decryption mathematical analogy

Ok, here's a toy example (which really doesn't work) of a simple signature scheme, which you can use as an analogy of a real system:

Suppose the signer Alice picks three integers $b, c, p$, and computes $a = b \times c \bmod p$.  She then publishes $a, b, p$ as her public key, and keeps $c, p$ as her private key.

Then, when Alice wants to sign a message $M$, she computes $S = c \times M \bmod p$, and publishes $S$ as the signature.

So, when verifier Bob gets the message $M$, the signature $S$, and Alice's public key, he verifies whether $a \times M \bmod p$ and $b \times S \bmod p$ are the same; if the signature is valid, then $a \times M \bmod p = (b \times c) \times M \bmod p = b \times (c \times M) \bmod p= b \times S \bmod p\ $, and so equality would hold.

The points I am hoping to make in this analogy:

The signature is not necessarily an 'encoding' of the message
Instead, the signature and the message satisfy some relationship (in concert with the public key)
It's not obvious how to create a signature for a given message with only the public key (actually, my example falls down a bit here)
The private key contains the 'secret sauce' that makes generating such signatures easy

Now, this doesn't work as an actual signature scheme, even with large numbers, because we know how to compute $a \times b^{-1} \bmod p$, which is $c$, however the method isn't immediately obvious to someone new to the field.


What does it mean that a protocol realizes "strong mutual authentication"?

Strong with regards to cryptographic protocol usually means that the protocol is secure if the underlying primitives can be proved cryptographically strong. In your case, that could be because authentication is performed using a symmetric cipher and a key that is only distributed for 2 participants.

But as indicated in the comments, "strong" depends on context, you won't get any assurances from it by itself.


Purpose of repeating a 16-byte key for Salsa20

If we fix the second half of the key to all zeros we have at least 2 potential issues:

The zero-bits offer no additional diffusion effect, whereas repeating the key increases the diffusion effect.
Normally the adversary would know $1/2$ of the input and control $1/4$, but with $16$ more static known bytes, the adversary now knows $3/4$ of the input. This might give the adversary enough control to mount more attacks that may have not yet been analyzed; though likely only with a reduced round chacha.

Without doing the expensive analysis, I can only conjecture that the static zero bytes would only weaken chacha. I do not know by how much, but I do doubt it'll be enough to break the full 20-round chacha.


ECB vs CBC for encrypting high entropy data

ECB is fine for encrypting random data. The point of ECB is that it is secure as long as the input of the blocks isn't repeated. It's often used as a key wrapping method which seems to be your use case.

Note that ECB mode is often used incorrectly even for key wrapping. For instance because the key is embedded in a structure (e.g. PKCS#1 encoded RSA keys). In that case ECB mode may leak data not just about the structure but also about the key.

You can still get into trouble even when wrapping AES keys as neither ECB nor CBC is an authenticated cipher. So if an attacker is able to change the encrypted value you're in trouble. Padding oracles may also apply - so don't unpad an AES-192 bit key (which uses 1.5 blocks!).

Basically you could be OK with any option you mention - but it depends on the system as a whole. I would still choose CBC with a random IV, if just to be on the safe side. That is, if the above are the only options you have, there are better alternatives (e.g. key wrapping mode - first mentioned by Louis Casillas - or SIV mode).


Is it safe to use the CBC-MAC as a Initial Vector and Key Check Value in deterministic encryption?

Am I thinking correctly and will an malicious user (which has access to encryption keys) not (or very hard) be able to generate a collision in my IV-ciphertext combination so that the server is grouping unequal messages together?

If the server checks all the bytes in the IV-ciphertext (and declares a collision only every byte for two encrypted messages are identical), and if you can decrypt it (and a decryption of an encrypted message will always output the original message), then it is obviously impossible to generate for two distinct messages to be declared as colliding (and you don't have to worry about the details of the encryption method except for these two facts).
Consider two distinct plaintext messages $M \ne M'$, they will be encrypted into ciphertext messages(which includes the IVs) $C = E(M)$ and $C' = E(M')$.  Now, the decryption process is a function of the ciphertext and the keys (and nothing else; that's why I counted the IVs as part of the ciphertext).  If we had $C = C'$, then what would this common ciphertext decrypt to?  If it is $M$, then we have a message $M'$ that, after encryption, could not be decrypted properly (hence violating the assumption that decryption of an encrypted value always gave back the original plaintext).
Hence, a malicious user cannot generate a message that the server would confuse with another message.


Which cryptography technique does not increase the size of the plain data?

The standard answer to this question is format-preserving encryption (FPE). FPE is a class of techniques that allow you to encrypt data while preserving some of its format (which can include its length).

In terms of security, most FPE schemes are deterministic, which means they do not achieve the standard IND-CPA notion of security. However, for high-entropy message distributions this is probably not an issue (ymmv). If your ciphertext can't be even one bit longer than the input plaintext, you don't have space to include a random IV or tweak, so randomization is out of the question unless you get tricky with your protocol.

FPE schemes usually do achieve a security notion called "strong indistinguishability from a random permutation", or SPRP.

For an example of FPE being used in a network protocol, see this paper on network protocol obfuscation.


There's no particular computation you have to do.

Since all other tables could be computed just by rotations of Te0 what you need is just to perform rotations, xors and table lookups.

Here's what usually done when you have only Te0.

You read the state column-wise, keeping in one 32 bit variable/register the value of one column. (As convention hereafter, the most significant byte of the 32 bit variable encodes the top byte of the column in the 4x4 AES state matrix).

Now what you want to perform are ShiftRows, SubBytes and MixColumns is:

uint32_t a[4]; //This contains the state
uint32_t b[4]; //This will contain the state after ShiftRows
                         //SuuBytes and MixColumns

b[0] = Te0[FIRST_BYTE(a[0])]  ^
       rotateL8 (Te0[SECOND_BYTE(a[1])]) ^
       rotateL16(Te0[THIRD_BYTE (a[2])]) ^
       rotateL24(Te0[FOURTH_BYTE(a[3])]);

Where the X_BYTE are macros returning the X most significant byte of the uint32_t, and the rotateLX macros perform left rotations of X bits.

The explanation is as follows:
As input it is taking first byte of first column, second byte of second columns, etc.
This is made to perform ShiftRows. In fact, the input will be the first column after ShiftRows operation.
The table lookups by Te0 will return a word, containg: 2*Sbox(input), Sbox(input), Sbox(input), 3*Sbox(input)

Note that this corresponds to the first column of the formulas below, which is used to calculate MixColumns as shown in the wikipedia MixColumns page

$b_0 = 2a_0 + 3a_1 + 1a_2 + 1a_3$

$b_1 = 1a_0 + 2a_1 + 3a_2 + 1a_3$

$b_2 = 1a_0 + 1a_1 + 2a_2 + 3a_3$

$b_3 = 3a_0 + 1a_1 + 1a_2 + 2a_3$

Note that the addition in the above formulas are additions in $GF(2^8)$ and corresponds to the xors used in the C code.

Therefore when you do the second table lookup you need to rotate the result left by one byte, in order to match the second column in the formula above, and so on for third and fourth table lookups.

To evaluate a full round you need to evaluate the other 3 columns, the code is the same, you just need to rotate the indexes of a. So a full rounds can be obtained by:

for (int32_t i=0; i < 4; i++)
{
   b[i] = Te0[FIRST_BYTE(a[i])]  ^
          rotateL8 (Te0[SECOND_BYTE(a[(i+1) % 4])]) ^
          rotateL16(Te0[THIRD_BYTE (a[(i+2) % 4])]) ^
          rotateL24(Te0[FOURTH_BYTE(a[(i+3) % 4])]) ^ round_key[i];
}

Where the addition of $round_key[i]$ performs the AddRoundKey operation.

Please note that the final round requires special treatment since no MixColumns is performed. You will need to do the table lookup and just keep the second or third bytes (which corresponds to the Sbox of the input) discarding the rest. Something like:

for (int32_t i=0; i < 4; i++)
{
    b[i] = (SECOND_BYTE(Te0(FIST_BYTE(a[1]))) << 24) ^
           (SECOND_BYTE(Te0(SECOND_BYTE(a[(i+1) % 4]))) << 16) ^
           (SECOND_BYTE(Te0(THIRD_BYTE (a[(i+2) % 4]))) << 8 ) ^
           (SECOND_BYTE(Te0(FOURTH_BYTE(a[(i+3) % 4]))) ^ round_key[i];
}


There is no why it is identical. The input form of the data does not influence what the output of a secure hash function should look like. The input of a hash should be unrelated to the output except for the mapping performed in the hash function itself. There should be no method of calculating the output other than to execute the hash function.

The best way to find another hash with the same property is to brute force it; go through a lot of numbers, convert them to bytes, calculate the hash and compare against the hexadecimal representation of the output. As each hexadecimal digit represents 4 bits, you would have to perform $2^{44}$ calculations (as I don't see how the birthday paradox would help you here). Note that, as CodesInChaos mentioned in a comment, that rainbow tables could speed up searches for cases where the input has properties that are reflected in the output.

If you get the wrong hash output, then it is likely that your conversion from the given number to bytes is failing. You may want to try another encoding.


Stateless proof-of-work system with 0-roundtrip time

Is the requirement to prevent replaying identical requests? If not, it seems trivial to use a partial inverse hash of the request body.

If you are concerned about replaying identical requests, one possibility might be to use the proof-of-work nonce for your load-balancing algorithm. For example, use the least significant 3 bits to distribute across 8 servers. The long run average should distribute fairly between workers but a replayed request will always end up going to the same worker. SO you can check for duplicates locally without needing access to a global state.


How to recover secret $x$ from Elgamal signatures with repeated $k$?

Given two ElGamal signatures $(r_1, s_1), (r_2, s_2)$ that used the same $k$ when signing will have the same $r$ value since $r \equiv g^k \pmod{p}$ and $g, k, p$ are all fixed. Now, given that $s \equiv (H(m) - xr)k^{-1} \pmod{p-1}$ we observe the following:

$$s_1 - s_2 = ((H(m_1) - xr_1) - (H(m_2) - xr_2))k^{-1} \pmod{p-1}$$

But $r_1$ = $r_2$ so we can reduce this futher:

$$s_1 - s_2 = (H(m_1) - H(m_2))k^{-1} \pmod{p-1}$$
$$k = (H(m_1) - H(m_2)) * (s_1 - s_2)^{-1} \pmod{p-1}$$

Once we have $k$ we can use it to recover $x$ by rewriting the formula with which $s$ was initially computed:

$$x = (-r^{-1})(sk - H(m)) \pmod{p-1}$$

We know $r, s, k, H(m)$ so we just plug them in and solve for $x$.


Authenticated encryption using asymmetric keys

You will always need at least to blocks (=512 bytes in your case) if you want to encrypt and sign some data.
Any RSA signature block, be it armored with PKCS#1 v1.5 or PSS (or even textbook RSA) will have the size of the modulus (256 byte), since it is the output of a RSA operation. So if you want to add some plain text data to that, you will automatically need to start a new block.

All said is under the assumption of using two keys of equal size (2048 bit), as you suggested. You could get away with one block if your signature key has a smaller bitsize (e.g. 2048) then the encryption key (e.g. 4096).


Is Public key used directly to encrypt a message or it is used to derive other keys?

A public key is used to encrypt a message.

Example:

If Alice wants to send a message to Bob she would take Bob's public key and encrypt the message and send the encrypted message to Bob.

A key to derive other keys is done with a Key derivation function and this key is commonly called a "master key", so it has nothing to do with public-private-key-encryption.

  Can we decrypt a message with same public key using which it was encrypted?

No, you can only decrypt the encrypted message with it's corresponding private key (you always create a private & public key pair together).


Trying to implement the algorithm in Wikipedia regarding key exchange

There have been several rLWE key exchange protocols proposed; what you're looking at is the protocol proposed by Professor Ding here.

In this protocol, the errors are assumed to be small even values; on the Wikipedia page, you can see that they always add the error vector in the form of $2e_i$.  Your test fixture is generating relatively large errors without any regard to whether they're even or odd.  Unless you fix that up, yes, the reconcilliation process will generate random values.  It still won't work great unless you make sure that the errors are actually small (you appear to be trying it with large errors); but you appear to be testing that deliberately.


A lot of companies use BSAFE: for a long time, BSAFE was the most successful supported cryptographic toolkits: it predates the success of open source software, it predates the availability of crypto APIs in operating systems, and it predates the expiration of patents on RSA and public-key cryptography in general. And it's always been a reliable, well-tested, well-documented, portable library from a company that ported it everywhere there was a customer and provided support. So, it garnered a lot of customers. The number of developers using BSAFE has presumably declined as the patents expired, export restrictions relaxed, allowing OS crypto APIs, and open source ate the market, but I'm sure there's still a very large number of products that incorporate BSAFE.


Compute euclidian distance on encrypted data

No, not in the system as described.

One sufficient reason: in any scheme matching the standard goals of public-key encryption, including homomorphic, nothing about information encrypted with a public key can be determined from the cryptogram without the matching private key. Thus $p$, encrypted under A's public key, can't be used by others (not knowing A's private key) to determine the distance of A to another point.

The normal thing would be that A signs her position (and date/time) with her private key, encrypts the outcome using other user's public keys, and trusts them not to collude to find her location. Such scheme allows the users to determine their respective distance to A, and protects them from third parties trying to misinform them about A's position.

The non-collusion hypothesis is necessary for geometrical reasons even if the devices used to determine the distance to A are designed not to leak her location. That's because multilateration¹ allows three users B, C, D at known locations and knowing their distance to A, to determine A's position, defeating the purpose of encryption.

That's a hard limit. Fully homomorphic encryption could allow a third party to compute the encrypted distances from the locations encrypted with the same public key, without knowing the locations or distances; but getting at the result requires the private key. That's about all I can imagine towards the question's goal.

¹ Essentially, assuming A,B,C,D are on a plan, A sits at the intersection of 3 circles of centers B, C, and D, of radius their respective distances to A. Two users are often enough to narrow A's position to just two locations, and perhaps one of them is unlikely. If the angles BAC, CAD, DAB are not overly acute, the third user's info narrows to one location, and tends to make the estimation of A's location precise, with an incertitude on that only a few times the incertitude on the positions of A B C D. The technique also works on a sphere of known radius, or in three dimensions with one extra point.


Are there simpler FHE methods than Craig Gentry's original paper?

As you point out, there is the DHGV 2010 scheme over the integers based on the approximate GCD problem but asymptotics are not great with this scheme, for eg. one of the parameters for DHGV is around $2^{\mathcal{O}(\theta^{5})}$ where $\theta$ is the security parameter.

Of the so called second generation schemes, I would say that BGV has been pretty well benchmarked from a performance standpoint (https://people.csail.mit.edu/vinodv/6892-Fall2013/BGV.pdf) - BGV is based on hardness of lattice SVP (Gentry's original scheme, on the other hand was based on two hardness assumptions - the ideal coset and the sparse subset sum problems - additionally, it required some machinations around "squashing" the scheme's decryption circuit in order to make it boostrappable).

BGV is both "leveled" and bootstrappable and there is variant that utilizes Ring-LWE encryption with an "aggregate" plaintext space that consists of integer subrings of cyclotomic number fields $\mathbb{Z}[X]/\langle \Phi_m(X),p \rangle$ where $m$ is a power of 2. The Ring-LWE BGV variant also utilizes Smart and Vercauteren's application of "double" Chinese Remaindering as a structure theorem for it's aggregate plaintext space, thereby allowing for SIMD operations on the data - what this means is that the scheme allows one to encode multiple messages within "slots" in the aggregate plaintext space, and then perform parallel homomorphic Add and Multiply operations on the messages (https://eprint.iacr.org/2011/133). Also, since we're talking about encoding messages as polynomials, FFT can be utilized for fast multiplcation of ciphertext polynomials. Last but not least, BGV leverages automorphisms associated with the plaintext's cyclotomic number field to "permute" slots or elements without having to unpack the ciphertext - so the upshot of all of this is that BGV allows for pretty efficient homomorphic evaluation - a fact that is evidenced by this study on homomorphic evaluation of the AES circuit - https://eprint.iacr.org/2012/099.pdf. In summary, this paper demonstrates amortized time of 2 seconds for homomorphic evaluation of AES encryption per block at lattice dimension 46080 on a commodity laptop - the implementation leverages the so called "Gentry Halevi Smart optimizations" that are outlined here - https://eprint.iacr.org/2011/566.
Halevi and Shoup's HElib provides a BGV backend with all of the features described above. Leo Ducas land Daniele Micciancio have another HE library available here https://github.com/lducas/FHEW, however I am not familiar with this scheme. I should also mention there is the multi key scheme by Lopez, Tromer and Vaikuntanathan based on the NTRU problem and a benchmark of homomorphic evaluation of AES based on this scheme over here - https://eprint.iacr.org/2014/039.pdf


Is there a way to generate sound one-time pads out of public information?

Very short answer: No
Quite Short answer: No, because a scheme can only be a One-Time-Pad if the entire pad is perfectly random and secret.
Concise answer: It sounds like you're trying to build a stream cipher. The security of it really comes down to how much of the scheme you think can be kept secret. If I listen in to your wifi and hear you requesting a certain resource, then I can work out what your data-source was, calculate the pad myself and decrypt your data. This tends to be bad!

Full answer:
Any scheme 'like' the One-Time-Pad (OTP) breaks down into two sections: first we form a pad and second we combine the pad with the plaintext. The second of these tends to be through the xor operation (denoted $\oplus$), but this doesn't really matter for this question.

So, the first section: generating a pad. For the OTP, we assume the pad is perfectly random and secret. If so, then the scheme is perfectly secure. However, this means we somehow have to transmit a large amount of secret information to the other person before we can send them the message, which in most cases just means we pass the difficult problem of key distribution upstream.

So, how do we get around this problem? We take a small key that can be more easily distributed, and expand it with a method that everyone involved knows to form a stream cipher. This is a function that tries to expand a small key into a suitably large key stream to pad the message with, and we have some pretty tough requirements of it. In particular, we demand that the key stream appears random. That is, someone seeing even a large amount of the keystream should not be able to differentiate it from truly random data (within 'reasonable' computation effort).  If they cannot differentiate it from random data, we decide that the output ciphertext is sufficiently secure.

Before I try and pull things together, I'd like to point you to Kerckhoffs's principle.
 Basically, for any real level of security in the modern world, we require that a cryptographic algorithm should be secure even when the attacker knows everything about it except for the key. Note that 'the key' is a vague notion - one can draw the algorithm-key boundary pretty well wherever they like - but good practise says the key should be as small as possible (eg algorithm=RandomAccessMachineSimulator; key=MyCryptoAlgorithm) without compromising the security of the algorithm.

So, how does your situation work? Well, turning a large amount of not-very-random data into a small about of 'quite random' data is a question of [extracting the entropy][Note 5]. A naive way of doing it would be to simply pump all your input data through a key derivation function like PBKDF2, but I won't go into this in much detail chiefly because there's a bigger problem: What do you keep secret?
 - Keeping the entire algorithm secret: If you want to keep everything secret from an attacker, then how do you tell the person you're messaging how to decrypt it? Somehow you must privately give your ally all the required details. At this point though, why not just give them an AES key that you can then use to communicate securely?
 - The data-source is secret: This makes a bit more sense. All the 'fiddly' computer bits (eg the entropy extraction) can be exchanged insecurely (eg email), then you send them the data-source (URL?) in secret. However, (assuming that for some reason this time we can't just send a key instead) anyone listening to your HTTP requests will hear all URLs loaded, and by testing each one of them will find your key very efficiently.

[Note 5] - Is there already a good description of this somewhere?


The probability of finding a limited set of collisions for HMACSHA256

I think most would agree that 2^128 is not plausible without UFO space alien technology (i.e., wildly successful quantum computers).

There is no currently known way to find collisions over SHA-2-256 in any plausible amount of time, with any plausible number of inputs.

As long as the key is secret, there is no known way to someone to find a username or randomID that produces a target HMAC value, or to predict the HMAC value for one username+randomID given the value for another (length extension attack).

However, another thing to be concerned about is timing leaks if you ever compare an expected HMAC value and a value received by a potential attacker. If you use a naive strcmp(), timing will tell the attacker how many initial bytes he got right and he can use that to work out the value he needs to send without even knowing the key, username, or randomID.


Current day memory capabilities for cryptanalysis?

The answer depends a lot on the latency you may tolerate.

In 2011, Oracle/Sun/StorageTek announced a new storage system with exabyte capability (roughly $2^{60}$ bytes, but that's assuming a 2x compression rate; for crypto purposes, this is closer to $2^{59}$ bytes). Note that this was already seven years ago. Latency for random accesses could be up to a few minutes: the system uses a robotic arm that shuffles through thousands of magnetic tapes in a silo.

In a TMTO with the use of distinguished points (in particular Oechslin's "rainbow tables"), there is a "compression factor"; let's call it $t$. Costs for a rainbow table that cover $N$ preimages for a given function will be the following:

Building the table: about $1.7\times N$ evaluations of the function, and a sorting step (mostly $O((N/t)\log N)$ operations, but details vary a lot; merge sort variants are normally used because they can work with high-bandwidth sequential access).
Storage cost: about $(N/t)\log N$ bits.
For each lookup, about $t^2$ evaluations of the function, and $t$ accesses to the stored data (the original TMTO from Hellman would have needed $t^2$ accesses to storage, but the use of "distinguished points" fixes that).

The different variants of rainbow tables all follow these lines, sometimes with a factor somewhere, but always between 0.5 and 2.

For instance, if you have the half-exabyte storage system described previously, and want to find preimages for a 64-bit problem (e.g. an encryption system with a 64-bit key), then you will need $(N/t)\log N = 2^{59}$, hence $t = 2^{11}$. This means that each attack would require a few days (about three days, assuming an access latency of 2 minutes). This can probably be optimized: the $t$ lookups don't really depend on each other, so they could be collected and sorted so as to be performed in a better order that maximizes the robotic arm efficiency.

Some important notes:

The one-time cost of building the table is larger than the cost of exhaustive search. In fact, average cost for brute force is $N/2$ evaluations of the function. The table is worth the effort only if it will be used for at least four attacks.
The attacked function must be known in advance, completely. In the context of attacking a block cipher used in CBC mode with a random IV, then encryption is applied on plaintexts that are, by definition, randomized (that's the point of CBC mode). Thus, a known plaintext/ciphertext pair is not sufficient in that case.
On the other hand, the attacked system may help. For instance, the attacked system may provide enough "known plaintext" that the attacker can afford to wait for a favourable situation. This is the gist of the Biryukov-Shamir-Wagner attack on A5/1, where attackers wait for the algorithm to reach a "special state".

And with hard disks? Instead of using the tape-driven system, which can store a lot of data but with a high latency, you could try to use mechanical hard disks, which store less data for a given cost, but with a much lower access latency. Suppose that you have a budget of a mere million of dollars, that you may spend on "normal hard disks". You can get 4 TB for \$100; thus, we are here speaking about 40 petabytes. Let's round that down to $2^{55}$ bytes. Now you need $t$ to rise up to $t = 2^{25}$ for a 64-bit problem ($N = 2^{64}$). But you have ten thousands of disks, each able to perform about 100 lookups per second, and the lookups will be spread quite uniformly, so they can be made in parallel to a great extent. You can hope for a million lookups per second in total, and the $2^{25}$ will be done in half a minute... On the other hand, the computation cost of $t^2$ evaluations of the function has risen to $2^{50}$, which is prohibitive.

If the storage budget rises to ten millions of dollars, then you can divide $t$ by 10, which divides $t^2$ by 100, making it totally in range of a small cluster of beefy PC. Take care that we are then talking about a hundred thousands of hard disks, which is bound to have some non-negligible operational costs (if only for heat management and replacing failed units). Still, this would fit in a medium-sized server farm.

To sum up, a 64-bit symmetric problem which is amenable to precomputed tables is certainly in range of big organizations; in fact, it can even be done discreetly by medium-sized enterprises, and even spy agencies. On the other hand, such hardware budget would yield much more money by mining bitcoins.


Can you use a "power of 2" gate in the BGW protocol

I don't see why it shouldn't work. If you ran the multiplication protocol using the same polynomial for both inputs, doesn't that work? Each party would square its share and then run degree reduction.


Why don't we use MACs to store passwords?

As K.G. and nightcracker note, the reason we don't recommend this method of password storage is that it becomes insecure if the secret $k$ is compromised.  Given that the whole point of password hashing is to protect the passwords in the event that your server is compromised, it's generally not safe to assume that the compromise won't include the secret key $k$.

That said, obviously the safest thing to do would be to use both a key-stretching KDF (like PBKDF2, bcrypt or scrypt) and a secret key, e.g. as:

$$\rm hash = KDF( MAC( password, key ), salt ) $$

or simply as:

$$\rm hash = KDF( password \,||\, key,salt ) $$

where $\rm key$ is a secret key, $\rm salt$ is a unique per-user salt, and $\rm KDF$ is a slow key-derivation function suitable for password hashing.


Is the only use for the private key of a root certificate signing certificates issued by it?

It could be used to sign a Certificate Revocation List, for instance. Generally it is not used for anything other than certificate related actions, and some private keys belonging to root and intermediate certificates are therefore stored off-line to enhance security of the private key.


Is the Salsa20/ChaCha20 keystream generation one-way?

Nobody should be able to retrieve the key from the IV + key stream. If that would be possible then the stream cipher would be broken. Both the IV and key stream can be considered public knowledge (by performing a known plaintext attack, for instance using all zero's). Retrieving the key from information that may be known to an attacker constitutes the strongest attack possible, so any stream or block cipher should protect against that situation.

Or, as fgrieu already states without making it an answer:

  A keystream generation algorithm which key, assumed unknown and uniformly random, can realistically be found from the output keystream and input other than key, is broken by definition of key per Kerckhoffs's principles, and/or of the security objectives of a keystream generator/CSPRNG.


This looks like a Playfair cipher with MAN as the key.

For characters not in the same row / column, you make a rectangle with the encoded characters at the corners, and the characters in the same row on the opposing sides of the rectangle form the decoded letters. For NP we have -

[N]--B-->C
 F   G   H
 L<--O--[P]

Which yields CL.

So for ET we have -

[E]--F-->G
 K   L   O
 R<--S--[T]

Decoding to GR.

For KO we need a new rule, since K and O are on the same row. For items on the same row we simply shift each letter left one position, wrapping back to the start of the row if needed. This means KO yields

I<--[K] L<--[O]

In other words, KO -> IL.

Finally for KF we have -

 E<--[F]
[K]-->L

Which yields LE

So ET KO KF gives us GRILLE.


While I agree that there exists a largest Lim-Lee prime I think it may be computationally infeasible to construct/find this prime in a provable way.  The set of 256-bit primes is very large and you would need to search through every product of 7 such primes to find the greatest such product that makes the resulting number a prime.

You could add an additional though rather artificial constraint to make the problem tractable.  You could say that you want to look at products of 7 primes chosen from the 20 largest 256-bit prime and choose the largest such product such that when multiplied by 2 times the largest 255-bit prime (2^255 - 19) and added to 1 the result is a prime number.

There are 20 choose 7 or 77520 products of 7 primes to look at. One would expect there to be many primes formed from these products.

Your criteria for the NUMS prime would be:

Pick the size of the prime.  This size is chosen to make the cost of the Number Field Sieve Discrete logarithm prohibitively high
Pick the size of the sub-primes in the Lim-Lee algorithm.  The base 2 log of this size should be twice the desired security strength.  For 128-bits of security one should use 256-bit primes.  For n bits of security one should use primes of 2n bits.
Pick the size (n) of the set of primes to examine. Given the size of the desired prime (a), the size of the sub-primes (b), c = the greatest integer less than (a/b)-1, you choose n such that n choose c is large enough to expect a prime in the set of putative primes that will be generated.
Choose the n largest primes of size b for the set.

You have then described a family of primes that are unique given choices of

a = size of the prime

b = size of the sub-primes

c = size of the pool of primes

With those three constraints you will have a unique result.  For some sets of parameters there will be ZERO primes that satisfy the criteria.
....
Looking back on your question about Lim-Lee primes from several days ago, many people would recommend staying with the original idea of Lim-Lee's algorithm for ephemeral prime generation rather than using fixed NUMS values.  If you were going to use a NUMS value you might consider using a 3072-bit prime to give an extra hedge against rich adversaries.


Pipelined architecture for secret key block ciphers

the number of stages must be a divisor of number of rounds

That applies to pipelined and to iterative implementations where one stage implements $k\ge2$ rounds out of $K$, and we want each of the $K/k$ stages needed for a full block cipher strictly identical. That requirement could be waived by making less rounds in the last stage, or in an iterative implementation using an extra multiplexer extracting the output after $K\bmod k$ rounds in the last of the $\lceil K/k \rceil$ stages. That requirement does not apply at all to implementation with a single round, or less, per pipeline stage.

in AES, since there is 4 operations inside every round then it is possible to make 4 stages?

Yes, with 4 stages per round, thus $4K$ stages per block ($K\in\{10,12,14\}$ depending on key size). That's useful in an iterative implementation (which goal is reduced silicon area at the expense of throughput). One stage still needs to perform 4 identical byte substitutions (since each 16 bytes of a block go through that at each round) in the SubBytes steps, thus a minimum-area implementation might further subdivide that, for a total of $16K$ steps per block.

but what about the last round?

Indeed the last round needs to be special-cased; in a pipeline that's different (simpler) function in the last round, in an iterative implementation that's an extra input to the logic to inhibit MixColumns, held to a different state during the last of the $K$ rounds.


How is NIST's Key Wrap (using AES GCM) different than normal AES GCM Authenticated encryption?

You can find some info in section B.2. "Comparison of Functionality with Other Authentication Methods" in NIST SP 800-38F, where it said:

  2) Many authenticated encryption algorithms ... provide an efficient means of authenticating associated data that is not confidential ...

  3) Digital signatures on ciphertexts or MACs on ciphertext can be verified without decrypting the ciphertext. ...

So obviously, NIST KWs don't allow authentication without decryption or associated header data.

But apart from NIST, you may also be interested in the paper Deterministic Authenticated-Encryption, where it gave a treatment on what does it mean to be a "key-wrapping" mode. To summarize, we can look at the following quote from the introduction section:

  We call the goal deterministic authenticated-encryption (DAE) ... In a DAE scheme, encryption deterministically turns a key, a header, and a message into a ciphertext.

Where as traditional AEAD as treated semi-conanically in RFC5116: An Interface and Algorithms for Authenticated Encryption, a nonce/IV needed to be provided so as to provide so called "semantic security".

As to

  Q: why did we need a separate specification for key wrap in the first place?

Determinism decreases the likelihood that misuse of the schemes happens, as could with non-deterministic schemes running on top of broken RNGs or compromised state.


Bitcoin ASIC miners are specialized hardware, which is capable of computing SHA-256 only. If you change almost any parameter in the Bitcoin proof-of-work, the existing miners will be useless. For instance, you could just change SHA-256 to SHA-1 or SHA-3.

To be more efficient against spammers equipped with GPU, you might want to employ a hash function that requires a certain amount of memory to compute hash. Scrypt is a reasonable choice with hundreds MBytes of RAM as a parameter, and the ongoing Password Hashing Competition will likely to produce better and faster candidates.


Taking half of a X bits hash key as secure as using a X/2 bit hash function?

It is unlikely that a secure X-bit hash function's X/2-bit truncation would not be X/2-bit secure.

For example, suppose you have a faster than $2^{128}$ second preimage attack on the 128-bit truncation of a 256-bit hash. Then you can run that attack $2^{128}$ times and expect to find a second preimage for some value of the full 256-bit hash, so that hash does not have 256-bit second preimage resistance (at least for some definitions of second preimage resistance).

However, the same argument does not apply to collision resistance: even if you can get a collision for the first half you need $2^{X/2}$ such pairs before you expect a collision in the second half. The birthday bound does not apply because you cannot compare different first-half collisions to each other.

(Collision resistance of the whole hash does put a bound on the multicollision resistance of the first half. If you had a $2^{X/4}$-collision in the first half, you would expect a collision among them in the second half.)

So theoretically it could be easy to find a collision for the first half, but no easier than brute force to find a collision for the whole. However, because real world hash functions use the same function to derive the whole hash value, any weakness affecting only the first half would be unlikely.

For Merkle-Damgård hashes in particular, a truncated hash means you actually have a wide-pipe construction, which has some advantages over an untruncated hash of the same length. So you would expect e.g. SHA-512/256 to be at least as strong, if not stronger than SHA-256.


Is this Bleichenbacher '06 style signature forgery possible? (Or more like, why isn't it?)

Now, I'm wondering about the case where an implementation does check that the hash is right-justified, but doesn't check the previous bytes at all.

That case is completely broken for $e=3$

  Assuming that we're still talking about exponent 3, someone could imagine that there might be a way to find a perfect cube that ends with that particular hash, thereby utilizing the more significant digits that are not checked by the code.

That actually pretty easy, with the assumption that the lsbit of the hash is a 1 (or more generally, that the number of 0's at the end of the hash is a multiple of 3); this assumption is necessary, because if it is not true, no perfect cube will exist.  It turns out if this assumption is true, then a cube will always exist.

The most straight-forward approach to find it is to do it iteratively; if we have a value $x^3 = h \pmod{2^n}$, then we can easily find a value $y^3 = h \pmod {2^{n+1}}$, as either $y = x$ or $y = x + 2^n$, and it's easy to check which one it is.  So, we just start with a small $n$, and just repeatedly add bits to $x$ until, when cubed, it generates the entire hash in its $n$ least significant bits.

  Is it possible to sign some message feasibly by somehow utilizing the structure of the particular hash in context of these (hash, perfect cube) pairs?

The above procedure works for more than half of all possible messages (assuming the hash function acts as random), hence the attacker can easily pick a message that he likes.


What happens if five messages are generated in IND-CPA security?

First things first: The adversary doesn't have to randomly pick messages, they can pick any messages they like, including heavily related ones.

Now as for why the adversary has to identify the message under $2$ instead of $n$ options.

Two allows for 1-bit plaintexts. Suppose you had a scheme that is secure for all messages of 2 bits and longer, picking $n>2$ and enforcing same-length and distinctness would mean you have no statement about 1-bit messages.
It's the most natural choice. 2 does the job, why pick a higher number?
Two is perfectly sufficient to express the meaning of the messages. This would be to decide the which message was "picked" with all messages but one (so exactly one for $n=2$) being "not picked".
Two makes the adversary the strongest and thus also our security model. By default the adversary has a 50% chance of getting the answer right, with other numbers this would be $1/n$.


Encrypting with Davies-Meyer hash function scheme

Davies-Meyer is a compression function construction. You need to call a block cipher with your to-be-hashed data as the key and the chaining value as the plaintext. You then XOR the plaintext to the output of the block cipher call to obtain the next chaining value.


One-way hash on encrypted data, result hidden from hasher

If you are not limited to HMAC, blind signatures would meet your requirements.

In RSA, you can do blind signatures as follows:

Let $M$ be the message to be signed (probably the hash of a message) and let $e,N$ be A's public key, $d$ is A's private key.

B computes $M' = M\cdot r^e \bmod{N}$ and sends $M'$ to A.
A computes $S' = M'^d\bmod{N}$ and sends it to B.
B computes $S = S'\cdot r^{-1}\bmod{N} = M^d\bmod{N}$ (i.e., $M$ signed with A's private key).

I am not aware of any libraries that support this scheme out of the box, but it wouldn't be too hard to add the functionality. Also, other cryptosystems would support this idea too.

Homomorphic Encryption
Using fully homomorphic encryption, this would be very possible to do. You would just need to implement a homomorphic version of a hash function and build it up into an HMAC function. Given current public-key homomorphic technology, it would be very slow. Still, though, this technology is too new for deployment.

Garbled Circuits
Another option for implementing HMAC that should meet the requirements you have stated is garbled circuits. Garbled circuits can evaluate AES privately much faster than even the most optimized version of homomorphic AES. Which suggests that a hash function could be practical to compute using a garbled circuit.


Reading the quoted section and then looking at the notes, it seems that this is not well explained in the notes. However, my assumption is that the adversary has compromised s2 before PSS, but then lost access and therefore does not have access to s2'. If the adversary had access to s2', they wouldn't need to do the attack to get s2'.

So, the adversary has s1 and s2 from before PSS and gets s3' (and s1') after PSS. In neither case does the adversary have the required 3 shares. But, because the adversary knows h(x), it is able to compute s2' from s2. Which allows the adversary to recover s.


What is the purpose of the "Explicit Nonce" in TLS for AES-GCM and AES-CCM?

This additional 32 bit nonce acts as a salt, and makes multicollision attacks $2^{32}$ times harder.

In this attack, the attacker collects a huge number of TLS sessions, each with a record encrypted with the same nonce.  He then selects a random key, and generates the counter mode keystream for the key (and the fixed nonce); he then checks if that key stream allows him to decrypt any of the records (and he can do this considerably more efficently than individually checking each one, if we assume that he knows the plaintext for each one, or even if he knows a number of linear equations that holds for each one).  If he finds such a random key that matches, he then has the key for that TLS session, and can decrypt it in its entirety.

If the attacker collects $2^n$ sessions encrypted with AES-128, he needs to check an expected $2^{128-n}$ random keys before being able to decrypt one; this is likely still infeasible for any plausible value of $n$, but still is easier than we'd like.

By setting 32 bits of each nonce randomly, this attack becomes more difficult.  The attacker needs to select not only random AES keys, but also random 32 bits of the nonce settings, and he'll find a valid decryption only if all those bits are correct; this makes the attack require an expected $2^{160-x}$ random keys.  Another way of looking at it; this multicollision attack doesn't make any sense unless an attacker collects at least $2^{32}$ seperate sessions; if he has less, it'd be more efficient for the attacker to select one session, and just brute force that (the 32 bit nonce doesn't make a brute force attack on a single session appreciably more difficult).

Also, it's not really important that the 32 bit nonce is secret; the same sort of logic would work if the nonce was public.  However, there's no reason not to make it secret, and it was more convenient in the protocol.


Elliptic Curve Factorization: Why are elliptic curves suited for this kind of task?

It's probably best to understand Lenstra's Elliptic Curve factorization algorithm by way of contrast with its predecessors, the Pollard's p-1 method, the Williams' p+1 method and the Cyclotomic Polynomial method of Bach and Shallit.

These are all Algebraic-group factorisation algorithms which require you to select a stage 1 bound $B_1$ and stage 2 bound $B_2$ where $B_1<B_2$.

The most common way for Pollard's p-1 method to fail is if none of the primes dividing the composite N to be factored have the order of the group of multiplicative elements (i.e p-1) able to be written as a product of prime powers smaller than $B_1$ and at most one prime between $B_1$ and $B_2$. Numbers having this representation are rare and can be loosely termed "smooth".

This is purely a characteristic of the composite to be factored and without knowledge of the factors you don't know whether the p-1 method is doomed to failure.

The Williams' p+1 method uses the multiplicative group of a quadratic extension of N which (if successfully chosen) has order p+1. So it fails if  none of the $p+1$s are smooth .

The Cyclotomic Polynomial method succeeds if let's say $p^2+p+1$ or more complex expressions are smooth but these numbers are getting larger than $p$ and the chance that they are smooth (unless N has a special structure) is rapidly decreasing.

What would be nice would be to have an effectively unlimited number of different groups with different orders that we can try where there's nothing stopping the group orders being smooth and the group operations are reasonably quick. That's what Lenstra's Elliptic Curve method delivers.

The way it works is that you choose a random $\sigma$ which specifies an elliptic curve where the orders of the multiplicative groups is somewhere in the range $p+1 \pm \sqrt p$. The algorithm will succeed if for one of the curves you try, the order is smooth.

In terms a layman might understand, when Pollard's p-1 algorithm was discovered, we could all of a sudden quickly factorize a whole swathe of numbers where p-1 is smooth but we were still stuck on other numbers. When Williams' p+1 algorithm came along then we could now factorize a whole lot more numbers where p+1 is smooth but we were still stuck on lots of numbers. When Bach and Shallit's Cyclotomic Polynomial method came along, a few more numbers were factorizable but it's clear that the effectiveness of each successive algorithm was diminishing. With elliptic curves, each $\sigma$ value is essentially making available a new algorithm as good as p-1 which works if $p+1-a$ is smooth for some $|a| \lt \sqrt p$. Unlike previous algorithms, we don't know what $a$ will be until the factor has been found. Now we no longer have to worry about the prime factors being small but "hard". The difficulty is purely dependent on their size.


Link between openssl 'req' command and 'unable to get local issuer certificate'?

Your second command generates a new RSA key and writes it in server.key, along with the self-signed certificate in server.crt.


Does RSA key transmit with OAEP insecure?

Q1: The random selection should be $\sqrt[3]{n}<m<n$ due to cube-root attack?

Suppose $n$ is 2048 bits long.  Then $\sqrt[3] n < 2^{700}$.  If $m$ is uniformly distributed in $\{1, 2, \dots, n - 1, n\}$, what is $\Pr[m < \sqrt[3] n]$?  Is this probability large enough that you have to worry about it?

  Now at the end the document it says;

    An attacker who somehow recovers $M$ cannot get the plaintext $m$. With the padding approach, he can.

  Q2: How can the attacker recover the $M$ while there is formal proof of OAEP.

I don't know exactly what the article is getting at here, but what really matters is that even if the adversary has a collection of $(c, H(m))$ pairs where $c = m^e \bmod n$ and $H$ is a random oracle, it doesn't help them to predict $H(m)$ given a $c$ not previously seen before.  Usually the way we use this to encrypt a real message—an arbitrary bit string—is:

Use RSA-KEM to generate $(c, k)$ where $k = \operatorname{KDF}(m)$ and $c = m^e \bmod n$.
Use $k$ as the key for a symmetric authenticated cipher like crypto_secretbox_xsalsa20poly1305 to encrypt the actual plaintext.
Transmit $c$ along with the authenticated ciphertext.

The recipient can recover $m = c^d \bmod n$, and then $k = \operatorname{KDF}(m)$, etc.

This composition of a KEM and a DEM (data encapsulation mechanism; an authenticated cipher serves as a DEM) provides the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack.


RSA generation of private key using public key

It isn't impossible. Otherwise, we wouldn't have to keep increasing key sizes of our RSA keys, see this for the history.

As stated in a comment, it is believed to be computationally hard. Though, even that has never been proven.


Start with the Caesar Cipher.  It is important to know the flaws and important for students to know the history of it.  It would be quite easy to break considering the background of the learners.  You probably want to include the algorithm as well as the cipertext.

From here you can build more advanced problems since they have the basic understanding of what's going on.

LM Hash
Small Keys
WEP

Simple problems, but we must crawl before we can walk.


I would say that DDH does not hold in $Z^*_{p^2}$.

Let's first consider DDH in $Z^*_{p}$. We know DDH is not hard because given a DDH tuple $(g^a,g^b,g^c)$, one can compute the Legendre symbols $(L(g^a),L(g^b),L(g^c))$, and know whether they are quadratic residues or not. If any of $(g^a,g^b)$ is a residue but $g^c$ is not, then we know $c\ne ab$.

It has also shown by Gauss that a number co-prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$. Thus the above can be extended to $Z^*_{p^2}$.


How to test an implementation of a homomorphic scheme?

The best work I know on "How to test an implementation of a fully homomorphic scheme" is the work from Tancrede Lepoint and Michael Naehrig. The article has been published at AFRICACRYPT 2014. Basically, you need to compare the efficiency (in space and time) of the most important operations: KeyGen, Encrypt, Add, Mult, Decrypt.

Links

A Comparison of the Homomorphic Encryption Schemes FV and YASHE.
Slides.
GitHub Poc.


Modified version of a CPA-secure encryption scheme

Ask a CPA-query with a known $m$ and get back $c_0,c_1'$. Compute $c_1'' = c_1' \oplus m$. Then, compute $F^{-1}_r(c_1'')$ and this will be $k$. Now you know the key.

Of course, this attack assumes that you can invert $F$, but nothing in the definition says you cannot (and in practice you often can).


Efficient Robust Private Set Intersection Questions

In general, you might find it more useful to look at the full description of the protocol on page 137 of the paper you cite, rather than the general overview on the preceding pages.

To answer your specific questions:

From page 137, step 8 (which corresponds to step 7 in the general overview):

  "For each $y_j \in Y$, $S$ chooses a random polynomial $P_{0,j}$ of degree $k + k (\lfloor \log n \rfloor + 1)$ with constant coefficient equal to $0$..."

To choose a random polynomial, you just choose every coefficient (except the lowest one, since that's specified to be zero) uniformly at random from the field you're using.
From page 137, step 9:

  "For each $y_j \in Y$, for $1 \le i \le 10k(\lfloor \log n \rfloor + 1)$, using the sharing polynomials obtained in Steps 6, 7, 8, and a random value $r_{i,j}$, $S$ computes: $Out_{i,j} = $..."

See section 2, "Deﬁnitions and Building Block Protocols" on pp. 127–128.  It looks to me like the choice between using a comma or a semicolon to separate the arguments to $\rm ENC$ is merely a stylistic / typographical one: ${\rm ENC}(x,r)$ and ${\rm ENC}(x;r)$ should mean the same thing.
Yes, there presumably is, although I cannot absolutely confirm that for you without actually reading the whole paper.


Generalized Merkle Signatures, SHA-3 and Sakura

In general there is no reason to use tree hash modes for Merkle trees. The reason is that a Merkle tree itself is already some kind of tree hash mode. The important thing about this kind of mode is that it allows to compute the root node given the value of one leaf and one node per tree level.

The possible ambiguity of hashes is not relevant for hash-based signatures as for these the tree height and thereby the number of leaves are predefined.


Here's how it works:

After $r$ signatures, he learns, at most, $rk$ balls (actually, that's a maximum; however that is a conservative estimate).
Hence, the probability that a random ball has been revealed is $rk/t$
Now, he tries to generate a forgery; he picks a message that hasn't been signed, and translates that into $k$ balls.  He can generate a forgery if all these balls have been revealed; the probability that a specific ball is $rk/t$; these balls were selected independently, and so that probability that all of them has been revealed is $(rk/t)^k$

So, if the attacker tries to select random messages until he finds one that works, that'd take an expected $((rk/t)^k)^{-1} = 2^{-\log_2 (rk/t)^k}$ tries.  We express security levels in terms of powers of 2, and so the "security" of this system would be $-\log_2 (rk/t)^k$


Why not use `` or `==` in constant time comparison?

C comparison operators (strictly relational < <= > >= and equality == !=) yield 1 if the condition is satisfied and 0 if not. On some implementations (compilers) depending on the CPU and sometimes options, this may be implemented by code something like:

; int a = ..., b = ...;
; int x = a > b;
  move a, r0
  compare r0, b ; sometimes subtract with value ignored and only flags used
  bgtr lab1
    move 0, r1
    br lab2
lab1:
    move 1, r1
lab2:
  move r1, x

This executes a different sequence of instructions depending on whether the condition is true or false. Depending on the CPU, and if it has branch prediction/speculation as many (not all) do today depending on whether the conditional branch is predicted correctly which in turn depends on lots of other factors that are usually impossible to fully analyze, this may take different amounts of time which may be detectable (although typically damn small).

Some modern CPUs have conditional-move instructions, or even logicize-flag(s) instructions, that avoid this problem, but when writing source to be ported to unknown compiler versions and environments you can't be certain these will be present and (if so) used.

Actually you aren't guaranteed that even bitwise operations are constant time but in practice they're your best bet.

Similarly the logical negation operator ! in your code may be implemented by something like this which is not constant time:

move x, r0
test r0 ; sometimes included in the move
bzer lab1   ; (EDIT)
  move 0, r1
  br lab2
lab1:
  move 1, r1
lab2:
; use r1 as result

No Undefined Behavior:

Shifting by a count greater than or equal the width of the left operand is UB. Even when it comes from an unsigned char as in the code you linked, the left operand of a shift is subject to the Integer Promotions of 6.3.1.1 (though NOT the Usual Arithmetic Conversions of 6.3.1.8) and so the left operand always has a width of at least 16 and they shift by 8 which is okay.

Also left shifting a signed type with a negative value or a value that overflows (i.e. at least one of the high N magnitude bits of the input is nonzero) is UB. They don't shift left.

Right shifting a signed type with a negative value is Implementation Defined: the sign bit may propagate or shift out. They do shift right values that are sometimes negative, but they immediately mask the result so that the bits which could be affected by this IB are not used.


How does one provide a secure and authentic communication channel?

"Authentic" is defined with regards to an identity. A message from Bob is authentic only insofar as Bob is distinct from Charlie. There must be something which, from the outside, makes Bob and Charlie two different entities.

In a computerized world with networks, Alice can "see" other people only through the data they send. Moreover, everybody can buy a computer, so what Bob can compute, so can Charlie. The only remaining way for Bob to be distinct from Charlie is what Bob knows. That's how identities are defined in cryptography: you are what you know.

So Alice can make sure that a given message $M$ comes from Bob (and not Charlie) only if Bob does some computation over the message $M$ which involves some data that Bob knows, but not Charlie.

A basic, traditional setting is when the "secret" known by Bob is a sequence of bytes which Alice knows too. That sequence of bytes can then be used as key in a Message Authentication Code: this is a kind of checksum, which Bob can compute over $M$, and that Alice can recompute over $M$ since she also knows the "secret"; that's how Alice verifies the MAC. But Charlie cannot compute the MAC since he does not know the secret. The shared secret can also be used as key for symmetric encryption, so that the message contents can remain confidential: there again, Alice can decrypt the data encrypted by Bob (since she knows the secret) but Charlie cannot. Combining symmetric encryption and a MAC while using the same secret as key for both can be somewhat perilous; there are subtleties.

The traditional scheme has the drawback of having a shared secret between Alice and Bob: since identities are "what we know", this means that Alice and Bob are really the same entity, "Bobalice". The scheme above is about Bobalice talking to himself/herself. That's not a useless model: that's what happens when you encrypt some data so that you can store it, and decrypt it back later; i.e. you are talking with yourself through time. In practice, for two distinct human beings, this means that Alice can authenticate Bob's message, but cannot prove it, because whatever MAC Bob computes, Alice could have computed as well. Also, setting up a shared secret between two people can be hard in some contexts (they must have met beforehand, or something like that). Finally, in the context of software (which is, by definition, quite dumb), there can be some issues if an attacker tries to send back to Alice one of her own messages: Alice knows that a message $M$ is from Bob because only Alice and Bob know the secret value which is needed to compute the MAC, and (that's the critical point) Alice remembers that she did not send that specific message -- so it must be from Bob. The "remember" bit can be tricky; a simple way is to add the sender name in each message (so that a message from Alice always begins by "From Alice").

To go further, we need public key cryptography. This leads to the following protocol: Bob has a key pair for an asymmetric encryption algorithm (e.g. RSA) or a key exchange algorithm (e.g. Diffie-Hellman). The "public" part of the key is known by everybody (that's what "public" means), including Alice. The "private" part of the key is known by Bob only (it is "private"). Alice choose a random sequence of bytes $K$ and encrypts $K$ with Bob's public key; she sends the result to Bob. Bob uses his private key to decrypt $K$, at which point ALice and Bob have a shared secret ($K$) and they can use it as above, with symmetric encryption and a MAC.

With public key cryptography, Bob is distinct from everybody else, including Alice; he has his very own private key. Bob's identity is defined as "whoever controls the private key corresponding to that public key". This still requires Alice to be able to know, in a reliable way, Bob's public key, where "reliable" means that Alice will not be induced into mistakenly using Charlie's public key. That's where certificates come into play: a certificate is a piece of data which is signed by an authority and says: "this is Bob's public key". It is a way to distribute public keys (and their binding to identities) in a verifiable fashion. There can be other ways.

For instance, in the SSH protocol, a client (which tries to connect to a remote server) knows the server public key by remembering it (the client stores a local copy of the public key). This requires a specific bootstrap procedure, for the first time the client connects to a given server, but afterwards the server key is known to the client, and the client just uses it to authenticate the server.


Key wrapping - encrypting many times with AES-GCM

No.  You're well above the birthday bound for a 128-bit block cipher.  Using AES under a single key for more than about $2^{64}$ blocks of data is asking for trouble.

The largest nonce you can use with standard AES-GCM is 96 bits,* which is safe sequentially, but you're probably not doing this sequentially unless you plan to wait a millennium for your sequential computer to count to $2^{70}$.  You could carve up the input space and assign disjoint subsets to an array of computers in parallel, but now you have much larger operational security and scaling issues that you almost certainly need to address first, and most likely the way you address those will be by using more than one key anyway.

Your best bet here is to give more details about what you're actually trying to accomplish, rather than ask how to use AES-GCM far beyond its advertised limits.

* Technically you can use >96-bit nonces with AES-GCM, but that's foolish because it is effectively the same as using random 96-bit nonces, and so it is worse than using sequential 96-bit nonces.


Is it possible to make use of a pseudo-random permutation to construct a one-way compression function?

This is possible in the ideal cipher model, and is the basis of the Davies-Meyer and other hashes; see https://en.wikipedia.org/wiki/One-way_compression_function. There has been a lot of work looking at this, but I think a good place to start is the paper Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. It is important, however, to be aware that the ideal cipher model is very strong. For example, AES suffers from related-key attacks and so is not a good basis for such constructions. In addition, due to DES weak keys, some of these constructions are completely broken with DES. However, it does explain the rationale behind the SHA256 and other SHA constructions that essentially construct a type of block cipher and apply a Davies-Meyer type transformation.


Generation of N bit prime numbers -> what is the actual range?

In the context of RSA, when we say an "N bit prime", we mean that it's a prime in the range $[2^{n-1}, 2^n)$.

In addition, when we say an RSA key is an "N bit key", we mean that it's in the range $[2^{n-1}, 2^n)$.  What this means that if you pick two random $N/2$ bit primes, and multiply them together, you'll get an $N-1$ bit modulus about half the time.  To avoid this, one common practice is to select the primes from the range $(\sqrt{2}\cdot 2^{n/2-1}, 2^{n/2})$ - that way, when we multiply the two primes together, we'll always get an N-bit key.

If you're worried that restricting the primes to this range will make guessing them easier, well, that's actually not a concern.  If we're generating a 1024 bit key (which by today's standards is cutting it close), there are approximately $10^{151}$ primes in the range $(\sqrt{2}\cdot 2^{511}, 2^{512})$-- it's unlikely anyone will happen to guess either one.


As for your idea to use a hash to create your OTP, please read Hash functions to generate one time pad to avoid the obvious OTP pitfall of getting its definition wrong.

  …

  As a reminder: a one-time pad…

  has to be truly random,
  must be at least as long as the plaintext,
  is never reused in whole or in part, and
  is kept completely secret.

  Only when all four points are met, we´re talking about OTP.
  …

Now, that linked Q&A asks if hashing PRNG output would be good enough to create an OTP stream… but your fixed-files idea is not much different in the end (just less volatile in relation to the data you're hashing, making the file-based solution worse).

You're failing the OTP definition in point 1 because files are not truly random. A hash won't magically make it truly random.
You're failing the OTP definition in point 3 because reuse of even a tiny portion of an OTP is a big problem (key reuse issues which lead to partly recoverable data/plaintext).
You're failing the OTP definition in point 4 because it is not kept completely secret. Obscuring the files used as hash source isn't secret by any means. Which brings us to your “…Fortunately it is possible to make them very obscure.” – This is irrelevant and a flawed assumption in a “governmental adversary” scenario as you describe it. The most obvious scenario (among many) which will be a neck-breaker is simple surveillance. For that reason, “security by obscurity” is not really considdered a safe solution in cryptographic realms. This is one of the reasons RSA & Co. have been developed.

Last but not least: you're also missing authentication which is another security problem related to your idea. Related to that, check Q&As like “Why should I use Authenticated Encryption instead of just encryption?” and maybe the related Wikipedia article about “Authenticated Encryption”.

Wrapping it up

My advise would be to rather rely on well-vetted cryptographic solutions which are publically available: an encryption algo (for example, something like ChaCha20), a MAC (to enable authentication), a KDF (to allow users to create according keys based on one or more common secrets), and potentially something like RSA to allow users to agree on a common secret via public-key encryption.

If you – as your comment describes – want to avoid using dedicated encryption algos and regard hashes to be “less obvious” (which I personally don't agree to), you should know that you can build a steam cipher from a hash (see “Building a stream-cipher out of a hash function?”, you can use a hash to create a MAC (see HMAC), and you can even create a KDF with a hash (see HKDF). If you do this, be sure to rely on a secure hash. MD5 nd SHA-1 are considered broken and should therefore be avoided for these purposes. Yet, SHA-2 and SHA-3 are also available and secure.

And if you really insist on using a “Digital Dead Drop”, you could use that instead of public-key encryption to agree on a common secret. Yet, I would advise against it as “security by obscurity” is generally a bad idea… especially when facing a governmental adversary.

This should be somewhat what you're looking for and cover all issues your scenario descibes.


Possible CPA or CCA attack when using AES-CBC mode under the following situation?

TLDR: Don't invent your own protocol, use an existing one.

Reusing an initialization vector with the same key is always a problem, even if the attacker is read-only. For CBC, you can see whether a beginning part of one message is the same as the beginning part of a different message (and you get to know the length of the common prefix, on block-level).

With a CPA (chosen-plaintext attack) and an IV known before chosing the plaintext, the attacker can (with several tries) decrypt about everything. This was used in the BEAST attack.
With a constant (but unknown) IV, a possible attack I can imagine now is guessing prefixes of the unknown plaintext and encrypting it, to see if they match.

All of these are prevented by using a random IV for each message, chosen after the plaintext of that message (or at least the first plaintext block) is given to the "encryption machine". This IV can be sent with the message itself, commonly before the first ciphertext block.

As far as I can see, a CCA (chosen-ciphertext attack) does not gain much from the fixed IV: you can still do a padding oracle attack by modifying the ciphertext block before the last block of a message and see if the message decrypts properly (assuming a padding scheme like PKCS 7), or can be read by the receiving application.

To prevent most CCAs, use a MAC together with your encryption (in the encrypt-then-mac order, i.e. calculate the MAC from the ciphertext including the IV and maybe other message meta data you might want to protect), and check the MAC before starting to decrypt. You can derive the MAC key from the same secret as you derive the encryption key. This has the side effect that it does not just protect the privacy, but also integrity/authentication.

There might be a lot more weaknesses hidden in your example protocol. Don't invent your own, use an existing one. For example, TLS with a preshared-secret ciphersuite should work for your needs (as much they are outlined in the question).


Upper bound Linear Feedback Shift Register

Between them, K.G. and Dilip Sarwate have pretty much answered your question. That is, you can derive an upper bound using the method described by KG:

  When the LFSR reaches a state it has been in before, what happens to the output sequence? How many possible states are there? Now you have an upper bound

However, working out how tight this bound is can be much more difficult (as per Dilip's comment):

  In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e−1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek.

In particular, this is the cycle generated if you initialize the LFSR with all the entries $0$ except for the last one set to $1$.

For a good LFSR, the period will be close to the maximum possible. Consider the tightness of the bounds described by K.G.: if the feedback polynomial is 'badly' chosen (for example $x^k-1$), the period may be much lower.

Since each time you 'step' the LFSR you are multiplying by $x$ within the appropriate field extension, to calculate the period it doesn't matter where on the cycle you start. It does matter that your initial condition is somewhere on this cycle, as for example initializing with the $0$ state leads to a cycle of only $1$ element. Now, if the period is maximal, then every non-zero element must be part of the 'main' cycle, and so any initialization vector will lead to an LFSR of maximal period. However, if the period is lower than this, we must be careful to ensure that the starting vector is indeed on the main cycle.


Read Toward Sensor-Based Random Number Generation for Mobile and IoT Devices, if it's not too late(!)

In summary, the extracted table below shows their findings.  Those were that the three accelerometers in combination provided a good 24 bits of entropy for randomness extraction.  The good bits are the black boxes in the table as per the note below it.  The team got fairly good random results from their scheme.

I'd add the proviso that they used aggregated data from 37 devices.  The results for a single device might vary...


Is secure lattice based cryptography in future?

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for lattice based systems such as the NTRU is approximately $3slog(s)+1000$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until $2020$. So if we use lattice in future we should increase its dimensions.

For more detail about other cryptographic Schemes complexity you can see "Cryptographic Schemes
Based on Isogenies" and also
"Yearly report on algorithms and key sizes".


Is DES slow in hardware or only in software?

DES is slow in software because it was designed back in the early 70's even before the 8086 processor existed, and uses several bit oriented operations that are just not implemented efficiently in a processor with a word oriented instruction set.

Its intended product was ASIC hardware designs, in which DES runs quickly. DES hardware processors are quite common on older network cards intended for use in servers and workstations (I still have LAN card with wire speed TDES hardware). DES was already considered obsolete by the time the technology would have trickled down into consumer grade hardware.

DES becomes even slower when we compare it from a security standpoint against AES. DES in software is probably half the speed of AES, and it is also half the key space. Therefore TDES is used to increase the key space, but now it is 1/6th the speed of AES. AES is also better designed to resist attacks other than brute force.

Double AES with two 128 bit keys requires about 1.5X the processing of AES with a 256-bit key, and at least from a brute force perspective is not as secure. The reason TDES is used instead of double DES is because it requires 3 operations in order to double the key space.


Which encryption algorithm is used for password protecting a file

This is Traditional PKWARE Encryption as documented in the PKWARE ZIP specification (see Section 6.0). It's an old stream cipher which suffers from a known-plaintext attack (see Biham and Stay publications) and has been replaced with AES in newer ZIP archive utilities.

See a lengthy answer here regarding the possibility of ZIP file password recovery when this cipher is in use.

Various people have implemented the known-plaintext attack and code is available (pkcrack and bkcrack).


Generating PGP key *without* random generator? (using fixed input only)

Yes, this could be done.  It would be easy to implement and use this in a way that would be horribly insecure (e.g. with too short a passphrase, and not enough key stretching), but if used carefully, it could even be secure.

Basically, what you'd do would be:

Generate a secure passphrase, e.g. a sequence of randomly chosen words.  This can be done separately from the other steps.  The passphrase needs to contain enough entropy that it cannot be guessed by brute force using currently available or foreseeable technology.  I'd say that means at least 80 bits (≈ 7 or 8 words at 10 to 12 bits/word), but you might want to go for up to 128 bits or so if you're feeling paranoid.  Double your estimate if you're worried about quantum computers becoming practical.
Use a key stretching KDF to convert the passphrase into a pseudorandom seed (of sufficient length; I'd say at least 256 bits).  The PGP standard already includes such a KDF (RFC 4880 § 3.7.1.3, Iterated and Salted S2K), but something like scrypt would be even better.  You can't use a random salt, because you want deterministic output based on the passphrase only, but you should still be able to get around 20 to 30 bits of effective extra resistance to brute force attacks (letting you use a somewhat shorter passphrase, and/or have a wider security margin) with little noticeable slowdown in normal use.
Use the output of the KDF as the seed to a deterministic PRNG, and use the PRNG as the randomness source for the key generation algorithm.
Optionally, temporarily store the generated key in memory (e.g. through the use of a background agent program) to avoid having to repeatedly retype the passphrase.

Note that all the parameters for steps 2–4 (other than the passphrase) need to be either fixed or specified by the user.  In particular, this includes the KDF and PRNG algorithms and any subcomponents (e.g. hash function) and adjustable parameters (e.g. iteration count) they may use, as well as the method used to generate the key.

Some variation, e.g. in the details of primality testing for RSA key generation, may be tolerable, provided that it has no more than a negligible probability of affecting the output, but other changes (e.g. anything the affects the order in which candidate primes for RSA are generated and tested) are likely to cause the same passphrase to no longer yield the same key.  In particular, this means that it would probably not be a good idea to rely on any third-party PRNGs or key generation code whose internal implementation might change, and that any implementation should be accompanied by a detailed unit test suite to detect any changes in behavior.

I'm not personally aware of any existing programs that would support something like this, but there are open-source PGP implementations (like GnuPG) out there, so if you wanted to write one yourself, at least you wouldn't have to implement the whole PGP standard from scratch.


Is there a security proof for the Triple-DES construction in the ideal cipher model?

Yes.  The following papers should be exactly what you are looking for.

The following paper shows that the answer is "Yes" and provides evidence that 3-key Triple DES is more secure than single DES:

Code-Based Game-Playing Proofs and the Security of Triple Encryption.
Mihir Bellare, Phillip Rogaway.  IACR ePrint 2004/331.  (Full version of a paper published at Eurocrypt 2006.)

They show that, in the ideal cipher model, the adversary must make more than about $2^{78}$ chosen-plaintext/ciphertext queries to have a reasonable chance at distinguishing 3-key Triple DES from a random permutation.  This not too far off from the best known attack on 3-key Triple DES (which requires about $2^{90}$ queries), and shows that 3-key Triple DES is significantly more secure than single DES (again, in the ideal cipher model).

There is prior work by Aiello et al. that analyzes 2-key Triple DES in the ideal cipher; see the related work section of the Bellare et al. paper for a citation and discussion.

There is also subsequent work that re-proves the result on 3-key Triple DES in a simpler form, and analyzes 5DES and longer cascades as well:

Cascade Encryption Revisited.
Peter Gazi, Ueli Maurer.  Asiacrypt 2009.


Is the same message with repeated AES-GCM leaking plain text over time?

If GCM is correctly applied then no, this is not the case.

Ciphertext output is supposed to be indistinguishable from random, so any secure mode of operation behaves in this way. If this was not the case then you could distinguish messages with the same value. That would not be considered secure.

GCM is not secure when (larger) parts of the message are identical. That would point to repetition of the IV / nonce. And as GCM uses CTR underneath it could almost instantly compromise the plaintext.

You would expect about half of the bits to change when comparing larger messages of identical size, as the Hamming distance is about half the message size for randomized messages.


No, it is not possible.

If it were, then RSA would be insecure; the same way to recover $e$ from $m_1, m_1^e \bmod n$ would be able to recover the private key $d$ from $c_1, c_1^d \bmod n$ (as that's the same problem, only using different symbols).


I think that the reason for 31 rounds is in their paper, Section 5.1.
 Bogdanov et al. have approximated a small $2^{−43}$ bias that occurs after 28 rounds of linear analysis.  Therefore they added another 3 rounds to arrive at a slightly unusual odd number of rounds.

This is how ciphers are designed.  There are no specific rules passed down through the generations on how many rounds a cipher should have.  We do know that more rounds improves resistance to analysis.  A very simple primitive can be easily strengthened by the addition of more rounds, and this fact is explicitly stated in the design notes for Skien and Threefish.  And preventing a designer from having 1000 rounds is the need to achieve a speed /performance for their target market. So they compromised at 31.

Singular increases in the round count work for PRESENT.  It's worth adding that sometimes its not possible to increase the round count by any arbitrary value.  The number of rounds has to match the key schedule and sometimes the schedule is designed more inflexibly than the main algorithm.


Is it possible to sign OpenPGP key without consent of a key owner? If yes, can unsolicited signatures be removed from a key?

As each certification is an independent OpenPGP packet, of course it can be deleted -- OpenPGP allows so by opening the gpg --edit-key <key-id> menu and running delsig in there. An alternative would be to use gpgsplit to split up an OpenPGP key file into its individual packets, removing the offending signature and concatenating the files again.

You cannot remove anything from the key server network, though. Most key servers synchronize with each other, and this is done by just merging all unknown packets with no exceptions. Using the common key server software, it is not easily possible to delete a single packet (you'd have to dump everything, find the offending certification, delete it and import the data again). But even if removed, the offending certification will be merged back as soon as the server syncs up to the others again.

You will hardly be able to convince a key server operator to remove a certification for the given reason; and for technical reasons, you'd have to convince all key server operators to do so at the same time (and hope, no other user has a copy of that certification and uploads it at some point in future again).

One of the design principles of the OpenPGP key server network is preventing deletion: by just always collecting all information the servers can get hold of, it is very hard for even powerful attackers being able to control relevant parts of the servers to apply any kind of censorship. The fact that wrong information might be contained is accepted, no content in the key server network is validated at all (apart from some basic, technical verification on the protocol level).


Do Weil, Tate, and Ate pairings exist on all elliptic curves?

Yes. In fact, you can write the Weil and Ate pairings in terms of the Tate pairing.

Let $E$ be a curve over $\mathbb{F}_p$ of embedding degree $k$ and prime order $r$. The Weil pairing is related to the Tate pairing as
$$
e(P,Q)^\frac{p^k - 1}{r} = \frac{t(P, Q)}{t(Q, P)}\,,
$$
where $t(\cdot,\cdot)$ is the Tate pairing. Likewise, we have
$$
a(Q, P)^{kp^{k-1} } = t(P, Q)^\frac{((t-1)^k - 1)}{r}\,,
$$
where $a$ is the Ate pairing, and $t$ is the trace of Frobenius, i.e., $t = p + 1 - \#E$.

So for all common pairing-friendly curves, all of these pairings exist and are well-defined. The optimal Ate pairing is the most common, since it involves the shortest Miller loop and is often the fastest. But this is not necessarily the case, depending on field sizes, available parallelism, etc.