If you want, one can define a "general SIS problem", with parameters $(n,m,q, \beta)$, as follows: I give you a matrix $A\in\mathbb{Z}_q^{n\times m}$, and you must find a nonzero vector $\vec x \in \mathbb{Z}_q^m$ such that $||\vec x|| \leq \beta$ and $A\cdot \vec x = \vec 0$.

The matrix $A$ specifies an instance of this general SIS problem. You get different variants of the problem by defining how the instance $A$ is chosen. What average-case hardness of SIS means is just that it is assumed to be hard to find (with good probability) a solution to the problem above when the instance is chosen randomly from some distribution of instances. This is in contrast to worst-case hardness, which would be the (much weaker) assumption that the problem is hard to solve for some instance $A$.

Now, when we talk about the SIS problem, by default this refers to the conjectured average-case hardness of the problem I described above, where the distribution over instances is the uniform distribution over $\mathbb{Z}_q^{n\times m}$. You can view this if you like as a special case of a more general family of SIS-problems, where one could consider both average-case hardness for different distributions over instances, or worst-case hardness.

However, the terminology "average-case" has nothing to do with the fact that SIS can be seen as a special case of a more general problem where one attempts to find a small-norm matrix $B$ such that $AB=C$ instead of a small-norm vector $\vec x$ such that $A\vec x = 0$. Note that the first one is also well known (it asks about solving several instances of the inhomogenous SIS problem) and indeed more general if we define $k$ and $C$ to be parameters of the system. But this has nothing to do with the terminology average-case - in fact, you could equivalently discuss average-case hardness and worst-case hardness for the more general problem which you consider as well. And the same goes for BDD and LWE.


Gaussian integers are numbers of the form $a+bi$, where $i$ is such that $i^2=-1$. If you consider them modulo a prime integer $p$, then:

If $p=4k+1$, then $i$ exists in $GF(p)$ and so Gaussian integers simply reduce to $GF(p)$ when working modulo $p$, with the size of the multiplicative group equal to $p-1$.
If $p=4k+3$, then $i$ does not exist in $GF(p)$ but does exist in $GF(p^2)$ (that's actually a common way to construct $GF(p^2)$ - to introduce such $i$), so Gaussian integers reduce to $GF(p^2)$ when working modulo $p$. The size of the multiplicative group is $p^2-1$.

Note that $p-1|p^2-1$ so using $p^2-1$ in the first case (as a multiple of the group order) also works for RSA. Although, for the scheme it probably matters to use primes of the form $p=4k+3$ to avoid degeneration to the basic RSA.


Why aren't Diffie Hellman public keys used for authentication?

This is called static DH. It can be done directly by using OpenSSL, but not many clients will support it. There is no mathematical vulnerability to using DH in this way, but it never really took off. Infrastructure for RSA signatures were already in place, so there was no need to switch to another algorithm.


How to calculate bit strength of Integer Factorization Cryptography (IFC) such as RSA using Python

(From comment so question can be closed properly)

log2 is log base 2. $log(exp(x))$ would cancel, but $log2(exp(x))$ is x times 1.44270 approximately, which gives the expected results


Encrypting a 64-bit binary number to a text containing upper- and lowercase, and digits

You can use Key Derivation functions (KDF) to generate secret keys, e.g., from passwords. In 2013 a Password Hashing Competition was organized and the winner is Argon2 KDF. Argon now very popular and it has a new version named argon2i.

From Wikipedia;

  In cryptography, a key derivation function (KDF) derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES.

Once a key is generated, you can stip the key into the desired size.

In the end, if you want to human readable generated keys apply Base64 encoding for the derived key. Base64 encoding uses 6-bit to encode data From $A–Z, a–z,0–9$, and $+,/$.


How does AES-GCM produce different ciphertexts, and how can the algorithm decrypt the values if they're random?

If you will look at Probabilistic encryption in Wikipedia, that will explain shortly.

GCM mode internally uses CTR mode and therefore let's concentrate on CTR mode. CTR mode converts a block cipher into a stream cipher. In CTR mode, one encrypts the $(nonce\mathbin|counter)$ then x-or the plaintext then increments the counter like

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$

If you select a random $nonce$ (IV) for each message, then even if you encrypt the same message you will get different ciphertext.

$$C'_i = P_i \oplus E(k, nonce'\mathbin|counter+i)$$ where $C'\neq C$.

In CTR mode, and therefore in GCM, the nonce must not be reused. It can have catastrophic results from leaking the messages to leaking the authentication key in GCM.

$$C_i = P_i \oplus E(k, nonce\mathbin|counter+i)$$
$$C''_i = P''_i \oplus E(k, nonce\mathbin|counter+i)$$
x-or both sides and use two-time pad attack as in One-Time Pad.

To prevent the random collision due to the birthday paradox (we expect a nonce collision with 50% probability after randomly selecting $2^{bit-of-nonce/2}$ nonces), incremental IV is advised, that is for each message you next nonce value so that you may prevent the IV re-use.

The nonce is not secret and it is usually prepended to the ciphertext. To decrypt, the other side uses this nonce that you send together with the ciphertext to initialize the mode in the same stage.

The other probabilistic encryption modes like CBC, OFB, etc., similarly uses and IV/nonce to randomize the encryption.

Note that to have semantically security the probabilistic encryption is necessary.


What is the error in this collision probability approximation?

Clearly, for $x\in (0,1)$ which is our case,
$$
e^{-x}-(1-x)< x^2/2,
$$
and thus the relative multiplicative error between the estimate and actual answer satisfies
$$
\frac{\widehat{P}_{\neg C}(Q)}{P_{\neg C}(Q)}<\prod_{i=1}^{Q} \frac{(i/M)^2}{2(1-(i/M))}\leq
2^{-Q} M^{-2Q} \frac{Q(Q+1)(2Q+1)}{6}\frac{1}{(M+1-(Q+1)/2))},
$$
by using the sum of first $Q$ squares on the numerator and the arithmetic geometric mean inequality in the denominator. So
$$
\frac{Q^3/3}{ 2^Q M^{2Q}(M-Q/2)}
$$
is a good approximation to the error.


If there's a trusted third party who needs to do the comparison (and you don't care if the trusted third party knows the committed values), then it's actually quite simple.

Take your favorite public key encryption algorithm; remember that a public key encryption algorithm can be represented by $E_{pub}(x, r)$, where $pub$ is the public key, $x$ is the value being encrypted and $r$ is a random value; this random value makes the encryption nondetermanistic.

Now, have the trusted party generate a public/private key pair, and have him publish the public key.

To commit a value $x$, Alice would select a random value $r$, and publish the value $E_{pub}(x, r)$.  Assuming that $E$ is a secure public key encryption system, no one can recover $x$ without the private key (and we assume that only the trusted third party knows that private key).

The open the commitment $E_{pk}(x, r)$, Alice would reveal the values $x$ and $r$; anyone can verify that those values (along with the global public key) generate the commitment.

And, because the trusted third party has the private key, he can examine $E_{pk}(x, r)$, recover $x$, and check if it is a sane value, and check how it compares to another commitment.


Whats the most secure way to encrypt a string without the use of a computer?

A one time pad, the first problem is the key is as big as the message, the second problem is you have to roll some dice a whole bunch of times and do a lot of repetitive math and looking at tables to convert numbers to characters.

The advantage is perfect secrecy. But I think that answers the question as nothing is more secure.


How RSA-OAEP decrypt a Symmetric Key message?

OAEP is Optimal asymmetric encryption padding for RSA and developed by M. Bellare, P. Rogaway, in 1995 and standardized in PKCS#1 v2 and RFC 2437.

Optimal Asymmetric Encryption -- How to encrypt with RSA. Extended abstract in Advances in Cryptology

Your image hiding some internals of the OAEP. Here a better one;

The MFG is Mask Generation Function is expected to be a random oracle. The MFGs are similar to a cryptographic hash function except that while a standard hash function's output is a fixed size, the MGF supports output of a variable-length.
If OAEP is developed after the XOF (Extendable Output Functions) then the proof will be much easier.
Back to your question

How it can retrieve back the key when it's XORed with A Hash (hash1) That it doesn't know. I don't think that the output of Hash2 helps with anything. Right?

We can formalize above as;
\begin{align}
T &= lhash \mathbin\| PS \| \texttt{01} \mathbin\| Message\\
maskedDB &= MFG1(seed) \oplus T \\
maskedSeed &= MFG2(maskedDB) \oplus seed\\
\end{align}
In the PKCS#1 standard, the same MFG is used as the random oracles. I've made a distinction by numbering. $MFG1$ is taken the $seed$ as input.
Now, you got a message that is sent to you by RSA-OAEP. You get the $maskedSeed$ and $maskedDB$
The $seed$ can be calculated by
$$seed = maskedSeed \oplus maskedDB$$ and now we know the $seed$.
Now the $T$ can be computed by
$$ T = MFG1(seed) \oplus maskedDB $$
Now get the encoded $message$ block and check it.
$$T = lhash \mathbin\| PS \| \texttt{01} \mathbin\| Message$$


using Post-quantum asymmetric ciphers instead of RSA

My impression is that there is no production ready post quantum scheme ATM.

NTRU seems to be decent (complete spec,  reasonable parameter-sizes and performance), but I think it's patented. No idea about the licensing terms.

But whatever scheme you choose, don't use it instead of a conventional scheme(RSA, DH, ECDH) but in addition to a conventional scheme. If you use a good construction, your protocol will be as secure as the stronger of the schemes.


Public Key generation for Ed25519 vs X25519

The public key representations are related but not the same. They cannot be used interchangeably without additional processing.

The curves are birationally equivalent; a point on a curve has an equivalent on the other curve.

So, given an EdDSA public and/or private key, you can compute an X25519 equivalent. Libraries such as libsodium provide functions to perform these computations.

Of course, it also works the other way round, even though this is slightly more convoluted due to the fact that the sign is not present in encoded X25519 keys.

There are alternatives. One of them is to use the same curve for both operations. There is nothing wrong with using Ed25519 for DH.

If what you need is store a single secret, you can simply use it for both operations. You will get 2 public keys, but given how small they are, it is rarely an issue.

Speaking of which, is storing a combined 64 byte key instead of a 32 byte key really an issue? For most applications, it rarely is.


Why is only one oracle + challenge-response phase sufficient for IND-CPA security?

EDIT: I realised that I assumed an IND-CPA game where the adversary has pre- and post-challenge access to the encryption oracle and not only pre-challenge access. I'll edit my answer soon.

I'll give the idea and leave the concrete analysis to you. You want to show that single-query IND-CPA implies multi-query IND-CPA or in other words if there is an adversary against multi-query IND-CPA, then there is also one against single-query IND-CPA.

Assume that you have an adversary $\cal A$ that that wins the multi-query IND-CPA experiment with $q$ challenge queries.

For our argumentation below, we construct an adversary $\cal B$ that uses only one challenge query where $\cal B$ interacts with an single-query IND-CPA challenger $\cal C$ of a symmetric encryption scheme.

The idea is that $\cal B$ chooses an index $i\in [q]$ and proceeds as follows:

Let $\cal B$ initialize the single-query IND-CPA game with a challenger $\cal C$ and:

For all challenge query $(m_0^j,m_1^j)$ with $j<i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_0^j$ and returns the obtained ciphertext to $\cal A$
For the challenge query $(m_0^j,m_1^j)$ with $j=i$, $\cal B$ queries $(m_0^j,m_1^j)$ to the challenge oracle of $\cal C$ and returns whatever $\cal C$ returns
For any challenge query $(m_0^j,m_1^j)$ with $j>i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_1^j$ and returns the obtained ciphertext to $\cal A$

If $\cal A$ outputs its guess $b'$ to $\cal B$, then $\cal B$ forwards $b'$ to $\cal C$

Now, define the $j$'th hybrid $H_j$ to be the version of the multi-query IND-CPA game where the first $j$'th queries are with respect to $m_0^j$ (and all remaining with respect to $m_1^j$). It is clear that in $H_0$ all queries are with respect to $m_1$ and in $H_q$ all queries are with respect to $m_0$. Consequently, a distinguisher between these two extreme hybrids $H_0$ and $H_q$ clearly yields a mutli-query IND-CPA adversary.

If we now assume that there is such an multi-query IND-CPA adversary $\cal A'$ that has non-negligible advantage, then if we move from $H_0$ to $H_q$, there must be an $i, 0\leq i < q$ such that for the neighboring hybrids $H_i$ and $H_{i+1}$ it must hold that their distance must be non-negligible (as the number of queries $q$ is polynomially bounded). Now, you can argue that any distinguisher between two neighboring hybrids yields a distinguisher for the single-query IND-CPA game, by exactly using the adversary $\cal B$ defined above. Finally, you will get that the advantage for an adversary of winning the multi-query IND-CPA experiment is less or equal then $q$ times the advantage of an adversary winning the single-query IND-CPA experiment, i.e., any multi-query adversary with non-negligible advantage yields a single-query adversary with non-negligible advantage (which proves what you want to show).


There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.


Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC)

If evaluating $f$ uses computer time $t$, a brute force attack takes on average time $Nt/2$. To have this larger than $T=36\cdot10^6$ seconds, with $N\approx10^{12}$, we need $t>72\cdot10^{-6}$, that is some hundred thousands CPU instructions. Artificialy slowing down the implementation of $f$ in the program won't help. $f$ must be inherently slow so that it is slow for the attacker; and controllably slow so that we can tune the compromize between security and speed of the user program.

The example application suggests that $S$ is a haphazard subset of a larger set with $M\approx10^{15}$ elements. We'll take it as $[0,M)$, with $M\ge2N$.

I aim only at a reduced version of the security requirement: Given two random values produced by the RNG, a guess of the number of steps of $f$ to go from one to the other, if made with much less than $T$ seconds of compute time, has low probability to be exact. Towards that:

Choose an integer parameter $\alpha$ (a larger one will slow $f$). Find a prime $p\approx\alpha N$ with $q=(p-1)/2$ prime ($p$ is a safe prime and $q$ a Sophie Germain prime), and also $2^q\bmod p=p-1$ (and perhaps $\log_2p$ unremarkably close to a simple fraction).
Define the function $b$ on the set $[1,p)$ as $x\mapsto b(x)=2x\bmod p$. The function $b$ is a cyclic permutation of $[1,p)$.
Define the function $c$ on the set $[N,2N)$ that iteratively applies $b$ (at least once) until the result is in $[N,2N)$, and returns this result. The function $c$ is a cyclic permutation of $[N,2N)$. See note for implementation.
Build a permutation $g$ of $[0,M)$ using a standard Format-Preserving Encryption technique. $S$ is  the set of integers $v$ in $[0,M)$ with $N\le g^{-1}(v)<2N$.
Define the RNG as drawing $u$ uniformly at random in $[N,2N)$ and returning $g(u)$.
Define function $f$ over the set $S$ as $f(v)=g(c(g^{-1}(v)))$. It cycles over the $N$ elements of $S$ in exactly $N$ steps.

Given random $v$, $v’$ produced by the RNG, it is possible to estimate how many steps of $f$ are necessary to go from $v$ to $v’$: we compute $u=g^{-1}(v)$ and $u’=g^{-1}(v’)$, then $y=u^{-1}\,u’\bmod p$, then solve for $x$ the Discrete Logarithm Problem $2^x\bmod p=y$ (this remains easy, given the order of magnitude of $N$ and $\alpha$). A reasonable guess of how many steps of $f$ are necessary to go from $v$ to $v’$ is $x\,N/p$ rounded to the nearest integer. However that estimate has low probability to be exact for moderate $alpha$ (much less than $N$), and I have some hope that markedly improving it has some sizable cost.

Note: there are time/memory trade-offs possible for evaluation of $c$ faster than the trivial:

uint64_t c(uint64_t x) {
  do {
    x += x;
    if (x>=p)
      x -= p;
  }
  while( x>=2*N || x<N );
return x;
}

and the program should use these, in order to increase $\alpha$ inasmuch as functionally tolerable, maximizing the cost of a brute force attack.


What does "simulatable" mean in security proofs?

That means you can produce a transcript by yourself (with only public knowledge), which has a sequence of values $C_1',\ldots,C_n'$ such that the distribution of $C_1',\ldots,C_n'$ and that of $C_1,\ldots,C_n$ are computationally (since public key encryption) indistinguishable.


NMAC is really just an "education tool" on the way to HMAC and I don't think anyone intended it to be used. The two keys are needed since the first and second hashes have different purposes. The first hash on the message is just needed to get collision resistance, whereas the second hash is supposed to provide a pseudorandom function type property. As such, it actually suffices to have just one key (on the second hash). However, the first key is included as a conservative measure so that even if the hash is broken and collisions can be found, it does not mean that NMAC/HMAC are broken since the attacker has to find a collision where a key is used that it doesn't know. The best way to look at NMAC/HMAC is a specific implementation of "hash and MAC" (analogous to "hash and sign").

The purpose of ipad and opad in HMAC is to get computationally independent keys for the first and second hashes. If we assume that the compression function acts like a pseudorandom generator when used in this special way with ipad and opad, then this follows. (It of course follows immediately in the random oracle model, but this is overkill and not needed.)

Nothing inherently bad happens if the key is longer than the block size, but nothing is gained either.

I'm not sure what you mean by the key being longer than the number of inputs bits of the hash function. I guess that you mean the compression function (since the hash function is practically unlimited). If yes, then the key can be longer, but nothing is gained by it, so you shouldn't do it.


Basic question on hash-based signature scheme

However, if quantum vulnerable schemes such as RSA is used for certificates, it makes such system still vulnerable to quantum computing.

Well, yes, if one used conventional crypto in your certificates, things would be vulnerable.  You'd need to use a certificate that used postquantum signatures.

BTW: generating a certificate for a one-time signature public key, such as W-OTS, would appear to be somewhat pointless, as you'd need to request a new certificate everytime you used your private key.  What you'd want to do (assuming tracking state is not an issue) is to use a scheme that can sign multiple messages, such as XMSS or LMS.


Computers are unable to handle real numbers, especially irrational numbers.

Computers can handle a fraction of the rational numbers (for being limited in size in a binary representation), and without some special tricks it can't handle the entire field $\mathbb{Q}$.

So you're down to integer arithmetic anyway (if you consider floats: rounding and cancellation can really mess things up). However, addition and multiplication over integers are just a ring structure and not a field (multiplicative inverse elements do not exist). So if you need to invert multiplication you need to use the finite structure.


Why does the recommended key size between symmetric and asymmetric encryption differ greatly?

Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs.

In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker would need to perform an attack with complexity $O\left(2^n\right)$ to correctly guess the key.

Asymmetric algorithms, on the other hand, use a different kind of key. For example, an RSA modulus is of the form $m = pq$, where $m$ is the modulus, and $p$ and $q$ are two large, distinct, randomly-chosen prime numbers of roughly equal sizes. The strength of the key is based upon the modulus' resistance to factorization into its prime components. An attacker using a general field number sieve would need to conduct an attack with complexity $O\left(\exp\left(\left(\left(\frac{64}{9} + o\left(1\right)\right) \cdot n\right)^\frac{1}{3}\left(\log n\right)^\frac{2}{3}\right)\right)$ to factor the modulus (and thus break the private key), given a modulus of bit-length $n$.


Actually, there is one way which you can achieve a similar effect: if you have some idle time beforehand, you can perform some of the work even before you know the message you'll encrypt (or possibly even before you know the public key you'll be sending to -- you will need to know the curve).  This doesn't decrease the total amount of work; however it can decrease the amount you work you need to when you get the message (because you did some of that work beforehand).

For example, let us assume you use ECIES; there, you pick a random number $r$, and compute the point $rG$ (where $G$ is the curve generator).  You can do this before you know either the message or the public key you'll be sending to.

Then, when you get the message and the public key $P$, then you compute $rP$, generate the symmetric keys, and encrypt and MAC the message using the symmetric keys; then you package up the values $rG$ and the symmetric ciphertext -- this part is about half the amount of work you'd need to do without precomputation.

Now, this as stated doesn't really address the question (because it doesn't make the work less than the decryption part) -- however, if you also knew the public key $P$ first, you could move the computation of $rP$ into the precomputation step as well, and that would make the remaining part of the encryption (which is just playing around with symmetric ciphers) significantly less than decryption.


You seem to have already calculated it. If you have
15(5) - 2*72 = 1 then  15(5) $\equiv 1$ (mod 72).  Can you see the solution now?


Encrypting and Authenticating The Simplex Communication Between Embedded Devices

For my answer, I'll assume that you have symmetric keys pre-shared between your heater and your sensors. If your devices have enough computational power to support asymmetric cryptography (which will increase workload by a large factor and message length by at least 32 bytes) the answer will be different (and provide stronger guarantees).

AES-128 CCM is a good choice for your use-case because your hardware supports the required primitives, e.g. AES-CTR and AES-CBC.  Authentication in cryptography means ensuring the correct source of information. If information is tampered in transit, the tampering party is the new source. Assuming you pre-share the symmetric keys in advance, AES-CCM will ensure the data actually came from a party holding the key or otherwise return an error upon decryption.
Actually you can do better than that. AES-CCM requires a so-called (12-byte) nonce  for operation for each message. This nonce only needs to be unique to provide the full security guarantees and so you can define the nonce to be a counter whereby the nonce gets incremented by one each message. If a too-small counter (IV) arrives, you can simply reject the message. You only need to ensure that the length field for CCM is long enough to describe your message length (4 bytes would be good).
Sadly no. If you use pre-shared keys, there's no further need for randomization from the cryptographic side of things. If you'd involve asymmetric cryptography, the RNG would actually prove useful (for generating temporary keys and such).
The best solution would be for your nodes to actually digitally sign the data they send, assuming the heater has the public keys in advance, so he can validate the signatures. However, such signatures tend to be computationally expensive and so may not be an option for you.


Is a Diffie-Hellman scheme in which parties always use the same public keys vulnerable?

This was actually the original proposal of Whit Diffie and Martin Hellman back in 1976:  Alice puts $g^a$ in the telephone book and keeps $a$ secret, Bob does likewise with $g^b$ and $b$, and whenever Alice and Bob want to have a conversation they use $g^{ab}$ as a shared secret key.

The main trouble is that you expose an oracle for $h \mapsto h^x$, where $x$ is your secret key, to anyone who wants to have a conversation with you.  If the group we're working in has many subgroups of small orders $\ell_1, \ell_2, \dotsc, \ell_n$, then the adversary can feed you points $h_1, h_2, \dotsc, h_n$ of those orders in order to learn $x \bmod \ell_1,$ $x \bmod \ell_2,$ $\dotsc,$ $x \bmod \ell_n$—this is the Lim–Lee active small-subgroup attack.

But if we operate in a group of prime or nearly prime order, that doesn't leak much information—for finite-field DH, for instance, we can use a safe prime $p = 2q + 1$, meaning that $q$ is also prime, so the only possible subgroup orders are $\{1,2,q,2q\}$, and we can choose $x \equiv 0 \pmod 2$ so that the adversary learns nothing from this.

Of course, if an adversary ever breaks into your computer and learns $x$, then they can also decrypt past conversations—the longer you use a secret key for encryption, the more conversations are vulnerable to retroactive decryption.  So you might want to use a long-term secret only for authentication and do a fresh key agreement per conversation, somewhat like Signal does—and pay attention to when you erase keys.  (A protocol that involves erasing keys is sometimes said to have ‘forward secrecy’, but I recommend against using that term because it obscures when you erase keys.)


Affine Cipher - Pair of plain to cipher text

After $3a=-1 \pmod{26}$ note that mod $26$ we have $-1 = 25=51=3\cdot 17$, so $a=17$.

Alternatively, note that $3\cdot9=27=1$ so we can multiply both sides by $3^{-1}=9$ and $-9=17\pmod{26}$.

And then $5\cdot17 +b = 9$, and $5\cdot 17=85=7$ and so $b=9$.

Now substitute $p=3$ in the encryption formula $c=17p+9$ for the final question.


Help to understand the KDM in SP800-56A, and the usage of "FixedInfo"

There is a couple of reasons one would want to do SP800-56A key derivation in real life scenarios.

Computational and communication cost - while it's true that for each usage the two parties could negotiate a fresh Diffie-Hellman shared secret $Z$ and use it to derive a session key, usually this process is computationally expensive and requires communication between the parties. More frugal approach is to do the key exchange once to agree on a shared secret and then do key derivation to derive shared keys for various purposes.
Shared secret is not a cryptographic key - most likely the shared secret the parties agreed upon is not suitable for use as a cryptographic key. Usually, secrets agreed with DH are too long and (when seen as bit strings) not uniformly distributed. For example, the result of a Diffie-Hellman process over $\mathbb{F}_p^\ast$ would be a number with length 4096 bits. One cannot use it directly as e.g. AES key because it's too long and using only a part of it as a key is an extremely bad idea. So we need to do entropy extraction and this boils down to key derivation.
Many derived keys are required - usually, we need more than one key in a system. E.g. we may need symmetric encryption session keys, maybe HMAC key for integrity protection, etc... The good practice is to use a different cryptographic key for each usage.
And in order to get the required number of different cryptographic keys from one "master secret" $Z$ we need key derivation. And here comes the FixedInfo parameter - it allows to parametrize the key derivation process and bind keys to their usages. For example, FixedInfo would contain the information about parties (so that we separate key derivations for different parties), purpose (so that we separate encryption keys from MAC keys), session (so that keys used for different sessions are different).

A drawback of the key derivation approach that is worth noting is that if the "master secret" $Z$ is compromised, all derived keys need to be treated as compromised as well.
On the other hand, compromise of any of the derived keys does not constitute a compromise of other derived keys or the master secret.


What key exchange do OpenSSL and CryptoAPI prefer by default?

Given a SSL-enabled web site, the Qualys SSL tester will tell what ciphersuite would be negotiated by a bunch of different browsers if they connected to that web site.  It will also tell you the list of ciphersuites supported by that server and the list of ciphersuites are supported by each of those major browsers.

For example, here is the output for one web site you mentioned elsewhere: output.  The section labelled "Handshake Simulation" will tell you what cipher suite many different major browsers would negotiate with this server.  For instance:

Chrome 29 (Win 7) would negotiate TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA over TLS 1.2;
IE 8 (Win 7) would negotiate TLS_RSA_WITH_AES_128_CBC_SHA over TLS 1.0 (which does not provide forward secrecy);
Firefox 22 (Win 7) would negotiate TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA over TLS 1.0;

and so on.  This doesn't tell you what elliptic curve they would use or the key size, but it gives you the other information you were looking for.

By testing one representative web site for each possible SSL server, you should be able to get close to the grid you want of the key exchange algorithm negotiated by all (browser, server) pairs.


Finding multiple smaller collisions equal work as finding a bigger collision?

Are problem A and B equivalent?  In other words, do both take $2^{256}$ work?

No; in the first case, you can find the first collision with $2^{128}$ effort and then find the second collision with $2^{128}$ effort, yielding a total effort of $2^{128}+2^{128} = 2^{129}$
Actually, you'd likely start hashing arbitrary values, and stop after both a second preimage of $x$ and a second preimage of $y$ came up; this expected effort is slightly less than $2^{129}$...


How do i generate the shared key from this question?

First note that by basic power laws:

$$(a^b)^c=a^{b\cdot c}$$

and then note that this here is simply an application of that:

$$\left(y_B^{RA}\right)^{XB^{-1}}=\left(\left(g^{XB}\right)^{RA}\right)^{XB^{-1}}=\left(g^{XB\cdot RA}\right)^{XB^{-1}}=g^{XB\cdot RA\cdot XB^{-1}}=g^{RA}$$

where all equalities hold in all multiplicatively written groups (actually in all monoids), such as $\mathbb Z_P^*$ and $XB^{-1}$ is computed modulo the group's order, e.g. $\varphi(P)$ for $\mathbb Z^*_P$

As for your numerical example, with $g=9, RA=6, XB=4, P=23$, first note that the multiplicative order of $g$ is $11$, which means we need to calculcate $XB^{-1}\bmod 11=3$ and then everything just works:

$$g^{RA}=9^6\bmod 23=3=12^3\bmod 23=(y_B^{RA})^{XB^{-1}}$$

And of course you probably also want to note that $$Z_{AB}=g^{RA+RB}=g^{RA}\cdot g^{RB}$$, so you don't actually need to recover $RA$ nor $RB$ but only $g^{RA}$ and $g^{RB}$, one of which either party can compute directly and the other using the above formulas.

If you want to carry out these computations with realistic numbers yourself, you normally use the little Fermat or the EEA for finding the multiplicative inverses, using also e.g. repeated-square-and-multiply. Finding the order of $g$ can be a bit tricky at times, because you only know that it must divide the group order (by Lagrange's theorem), so you could just pick a safe prime and use a $g$ that has order $q$ for $p=2q+1$ with $p,q$ prime. Finding such an element is quite straightforward in that you check increasing candidate values until you get one that matches the following three conditions:
\begin{align}
g^1\neq 1\\
g^2\neq 1\\
g^q=1
\end{align}


Pairings in Identity-based encryption vs. Attribute-based encryption

There really isn't a difference. It is just author preference in notation. Some authors prefer to write the pairing operations multiplicatively $e(P^a, Q^b)=e(P,Q)^{ab}$ while others prefer to write it additively $e(aP,bQ)=e(P,Q)^{ab}$.

This comes from the fact that in $e : \mathbb{G}_1\times \mathbb{G}_2\to\mathbb{G}_T$, $\mathbb{G}_1$ and $\mathbb{G}_2$ are (typically) elliptic curve groups, in which the group operation is additive, while $\mathbb{G}_T$ is a multiplicative group. Thus some authors might prefer to make the additive notation of the elliptic curve groups more explicit while other others prefer to make the notation more consistent.


Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used?

If you are the one to pick $x$ and $N$, finding collisions and second preimages is feasible (and it would appear to be possible while not jeopardizing the security of the system).

Here is one possible approach:

Search for a set of $n$ preimages $s_0, s_1, ..., s_{n-1}$ such that:

$\prod h(s_i) -1 = k r$, for a prime $r$ between, say, 256 and 512 bits.  This can be done by selecting a set such that the product is about the right size, and checking if the value is a large prime times a smooth number.
Then, select $p = k'r + 1$ and $q = k''r + 1$, both primes of the appropriate size (at least 1024 bits each), and set $N = pq$
Then, select $x$ such that the order of $x$ mod $p$ is $r$ and the order mod $q$ is $r$

Publish $N$ and $x$ as the system parameters.

Then, when someone has an accumulation of the set $t_0, t_1, …, t_m$, you can display a second accumulation $t_0, t_1, …, t_m, s_0, s_1, …, s_{n-1}$, which hashes to the same value.

That's because $h(s_0)h(s_1)...h(s_{n-1}) \equiv 1 \pmod r$, and $r$ is the order of $x$, and hence $x^{h(s_0)h(s_1)...h(s_{n-1})} \equiv 1 \pmod N$

Furthermore, I believe that:

The knowledge of the special form of $N$ (not counting the exact value of $r$) and the knowledge of $x$ does not make $N$ easier to factor
It appears infeasible, given $N$ and $x$, to determine whether this is being done.


Shamir Secret Sharing Scheme - leak of information

Since all the operations are with respect to the field defined by $p$, for a threshold of $t$ shares required for reconstructing the secret, any set of $t-1$ shares reveals no information about the secret, even in a probabilistic sense. This is the claim given in the original presentation of Shamir's scheme, and is in fact true due to the properties of finite groups and polynomial interpolation within them.

For a brief but illustrative example, consider the polynomial $4x^2+3x+1\in\mathbb{Z}_5$ to keep things reasonably small for a manual example. If we have three parties involved in the scheme, given two of their shares we should not be able to gain any information with respect to the secret, 1. If it is known that the shares of $P_1$ and $P_2$ are both $3$, for example, what information has been gained about the secret? Since the polynomial is of degree 2, 3 points are minimally required for using interpolation to identify the unique polynomial fitting the points. In this example it is easy to see that if the share of $P_3$ is 0 the secret revealed will be 4, and every other domain value results in a different secret value being revealed all solely dependent on the share of player three when shares for players 1 and 2 are known and fixed. Explicitly and exhaustively, given a list of potential share values for $P_3$ $[0,1,2,3,4]$ across the whole domain of possibilities, the resulting secrets revealed using this combination are $[4,0,1,2,3]$ respectively, and with equal probability since the share of $P_3$ is uniformly random. This is, once again the whole domain of possibilities and all are equally likely.

Therefore the scheme is information theoretically secure, because the property demonstrated in this brief and small example holds with respect to every combination of every proper subset of shares less than the threshold and every field of prime order, assuming of course that the scheme was set up correctly with appropriate parameters.


What's the difference between RSA and Diffie-Hellman?

Diffie-Hellman Key Exchange

Problem: We have a symmetric encryption scheme and want to communicate. We don't want anybody else to have the key, so we can't say it out loud (or over a wire).

Solution/Mechanics:

We each pick a number, usually large, and keep it a secret, even from each other. I'll pick $x$, and you'll pick $y$.
We agree on two more numbers, both prime, which anybody can know. We'll call them $g$ and $n$.
I'll calculate $g^x\bmod n$ and tell you my answer. You'll calculate $g^y\bmod n$ and tell me your answer.
Our shared key is $g^{xy}\bmod n = (g^y\bmod n)^x\bmod n = (g^x\bmod n)^y\bmod n$.

RSA Asymmetric Encryption

Problem: I want anybody to be able to encrypt a message, but I'm the only one who can decrypt it. I don't want to share decryption keys with anybody.

Solution/Mechanics:

I choose two large primes, $p$ and $q$.
I calculate $n$ such that $pq = n$.
I calculate $t$ such that $(p-1)(q-1) = t$.
I choose an integer $e$ that is both less than $t$ and coprime with $t$.
I find $d$ such that $d$ is the multiplicative inverse of $e$ modulo $t$.
I release $(e, n)$ as my public key, and retain $(d, n)$ as my private key.
When you communicate with me, you treat your message as a large number $m$. The ciphertext $c$ is given by $c = m^e\bmod n$, and decrypted by $m = c^d\bmod n$.


Does anyone know some good way to create such a certificate?

As you need to put the private key on the server anyways, you could just copy it of and use that for demonstration purposes.

Alternatively you could use software versions from the time when such keylength restrictions were not in place.

In particular you might want to take a look at FREAK, in particular this website (need to scroll down a bit) has a list of vulnerable server and client software that you should be able to retrieve from release archives for demonstration purposes.


Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme

There is no reason in Shamir's scheme for the finite field $\mathbb F$
to have a prime number $p$ of elements; the field can have $p^m$ elements for
suitable prime $p$ and integer $m \geq 1$.
So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right.
However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$
can be done using the
standard arithmetic unit included in microprocessors and the like (followed
by integer divisions for doing the mod $p$ operations) whereas using
$\mathbb F_{p^m}$ requires having a library already available (or developing
one) or building a processor for arithmetic in the field.

Given that you have the capability of doing arithmetic in $\mathbb F_{2^8}$,
you can use this field if you like. But, (as you say) in Shamir's
scheme, the secret is just one element of the field (one $8$-bit byte),
and so, if the Secret to be shared is several bytes long, you will
need to process each byte separately into its (one-byte) shares, and
concatenate the $i$-th share bytes into the $i$-th Share of the Secret.
Keep in mind that each byte  can be divided into at most $255$ shares
(the point $q(0)$ on $q(x)$ cannot be used for obvious reasons),
and so if you need to have more than $255$ shares to distribute, you
will have to use a different field. Finally, to maintain cryptographic
security, as the shares corresponding to each byte of the Secret are
being computed, you should do exactly what you say you are doing
in your comment:
use a different set of "randomly chosen coefficients" for $q(x)$,
rather than re-use the same set over
and over again for finding the shares of all the bytes.


Practical quantum attacks on SHA256 MAC and HMAC

There are two points. First the MAC you are using is not HMAC and the way you construct it (first message than key as input without any padding) is only ok if you assume that a) the SHA2 compression function is a random oracle and that b) verifiers check that messages are no longer than 32 bytes. Otherwise one can forge messages at the cost of an intermediate inner state collision without learning key. Hence, it might be a safer choice to put key first, an even safer choice to additionally pad key to the block length (64 byte), and the safest choice to use HMAC from the start.

Second, quantum attacks: Of course you can run grover against this: Just collect, say three (message, tag)-pairs and build an oracle out of it that for a key $k$ outputs 1 if it maps all three messages to the respective tags. This function is a boolean function as needed by Grover. Hence, you can break this in $\mathcal{O}(2^{128})$ queries to SHA2. How long this actually takes is a different story and depends on the size of the quantum circuit to implement the boolean function.

Note that the rate limitation does not help in any way here as we only need sufficiently many pairs that there exists only one solution $k$ with sufficiently high probability.

Add-on:
What is the probability that a key that works for two message tag pairs works for a third?

If we model $SHA2-256(m \| k) = t$ as a random function and assume we obtained pairs $(m_1,t_1), (m_2,t_2)$ which were computed using some key $k$ then the probability that a given key $k' \neq k$ maps $m_1$ to $t_1$ is $2^{-256}$. The probability that $k'$ maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is $2^{-(2*256)}$ and so on. (Here the 256 comes from the output length).

The probability that $k'$ does not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})$. The probability that all possible $2^{256}-1$ keys $k'\neq k$ do not map $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$(1-2^{-(2*256)})^{2^{256}-1}$ (here the outer 256 exponent comes from the size of the key space). So, the probability that there exists a key $k'$ that maps $m_1$ to $t_1$ AND $m_2$ to $t_2$ is
$$1-(1-2^{-(2\cdot 256)})^{2^{256}-1} \approx \frac{2^{256}-1}{2^{2\cdot 256}}\approx 2^{-256}.$$


The difference is how the plaintext-ciphertext pairs that the attacker has access to are generated.

In a chosen plaintext attack, the attacker chooses some plaintext and is handed the corresponding ciphertext.
In other words, the attacker may encrypt arbitrary messages.
In a chosen ciphertext attack, the attacker can additionally (a chosen ciphertext attack is usually understood to subsume a chosen plaintext attack) choose some ciphertext and is handed the corresponding plaintext.
In other words, the attacker may encrypt and decrypt arbitrary messages.

(Note: usually, additional restrictions on the permitted messages are posed in a particular security game to make it "fair", since some notions of security are vacuous if the attacker can query really arbitrary messages.)


what is the current actual budget - as of 2015 - needed to build a DES breaker machine?

Re-using their design might be no good idea - there are cheaper designs for sure. This new DES cracker would just need to try every possible key - like the one of the EFF already did.

DES was a big standard for encryption, so some people did build such machines, right? Of course did they: COPACOBANA is able to break DES in under 9 days and costs under 10,000 US $ - That was 2006. You could even run a few of them parallel and crack algorithms like DES even faster - or you just use RIVYERA and crack DES in 1 day. You can use more than one machine of them, too.

More informations about the DES cracker and the mechanic behind it can be found in this document.

I'm pretty sure there are even better methods as of 2015.


The Meet-in-the-Middle attack was (first?) exposed publicly in the context of DES by Whitfield Diffie and Martin E. Hellman, in Exhaustive Cryptanalysis of the NBS Data Encryption Standard (published in IEEE Computer magazine, 1977). In this attack, if we count only the time spent doing DES computations (thus discount the time and cost of memory and memory accesses), then we can find the 112-bit key of 2DES from a few known plaintext/ciphertext pairs using only a little more than twice the time it takes to find the key in DES. The factor is actually closer to 17/8 for worst-case time; and closer to 3 for average time.

That's a strong indication that 2DES is over twice as safe against key search as DES is, given a few plaintext/ciphertext pairs. That's (slightly over, but most importantly only) 1 useful extra key bit out of 56 (or over 55 under CPA due to the complementation property), when examination of the key space would (wrongly) conclude 56 extra key bits.

But the question can be understood as asking to confirm that 2DES can be broken with about twice the time it takes for DES. That's a broader statement, and very wrong in practice. Fact is, cost of memory and cost and time of memory accesses make a straight MitM attack impractical.

There are practical alternatives to straight MitM, but the increase in time is much larger than a factor 2. As far as I know, the best reference on that is section 5.3 in Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Application (1996), published in Journal of Cryptology, 1999. They state that 2DES offers "only 17 more bits of security" than DES does (that would still be over a hundred thousand times more).

Additionally: key search is far from being the only cryptanalytic attack. Sometime the 64-bit block size is the weak spot, and 2DES is just as weak as DES from that standpoint (see Sweet32 attack pointed by Lery in comment). Also, a DES key can sometime be found other than by key search, e.g. by compromise of a device holding the key (in which case the duration of the attack is often essentially independent of the number of chained DES), or Differential Power Analysys (in which case 2DES or 3DES often are only marginally more secure that DES).


modified substitution permutation networks

Your construction is completely insecure: a single known plaintext / ciphertext block pair is sufficient to decrypt all blocks encrypted with the same key.

Specifically, let me write your block encryption function $E_K$ as $$c = E_K(p) = P^{(n)}(S^{(n)}(p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n)),$$ where $p$ is the plaintext block, $c$ is the corresponding ciphertext block, $S^{(n)}$ and $P^{(n)}$ denote the $n$ times iterated substitution and permutation steps respectively, $K_1$ to $K_n$ are the $n$ subkeys derived from the encryption key $K$ by the key schedule, and $\oplus$ denotes the linear subkey mixing operation (i.e. normally bitwise XOR).

Since the substitution and permutation phases are invertible and independent of the key, I can just apply their known inverses $P^{(-n)}$ and $S^{(-n)}$ to the known ciphertext block $c$ to obtain the intermediate value $$x = S^{(-n)}(P^{(-n)}(c)) = p \oplus K_1 \oplus K_2 \oplus \dots \oplus K_n.$$  XORing this with the known plaintext $p$ then gives me the bitwise XOR of the subkeys $$\tilde K = p \oplus x = K_1 \oplus K_2 \oplus \dots \oplus K_n.$$  Clearly, given $\tilde K$, I can now decrypt any ciphertext block $c'$ to the corresponding plaintext block $p'$ as $$p' = S^{(-n)}(P^{(-n)}(c')) \oplus \tilde K.$$

The same attack works with trivial modifications also if the key is mixed with the plaintext e.g. using modular addition instead of bitwise XOR.  Indeed, all it really needs is for the operation $\oplus$ to be associative and invertible.

Furthermore, even if the subkeys were somehow combined with the plaintext in some weird way that was not trivially invertible, we could still use the approach outlined above of first inverting the unkeyed substitution and permutation steps, leaving only the key mixing steps, and then focusing our cryptanalysis efforts on that.  So, in effect, the substitution and permutation steps in your construction provide no cryptanalytic strength whatsoever beyond that provided by the key mixing step alone (which for normal key mixing methods, like bitwise XOR or modular addition, is essentially zero).

In fact, this is why normal substitution–permutation ciphers like AES both begin and end the encryption process with a key mixing step: any unkeyed substitution or permutation steps before the first key mixing step or after the last one would contribute no additional security to the cipher, since an attacker could just invert them even without any knowledge of the key.


Attack on stream cipher that XOR's the output of two LFSRs

There is another method named algebraic attack.

Name each of the keys initial keys by $l_{1i}$ and $l_{2i}$.
Since the LFSRs are linear and the combining function, x-or, is also linear compute algebraic equations
Solve them. They construct a linear system of solutions.

Since only 38 bits are keys, you will only need 38-bit output if the if the equations are linearly independent.

if you use the Gaussian elimination method it will have $40^3$ operations.


Efficient algorithm for finding Sophie Germain primes

I don't know of any industry standards, however it's obvious that your code is fairly suboptimal.

The initial randomPrime() will effectively pick a candidate number $q$, and then spend a lot of time ensuring that number is prime.  Now, half the time it'll pick a $q \equiv 1 \pmod 3$; if so, p will be a multiple of 3, and so you've just wasted all that time testing if $q$ is prime.

Now, what all random prime routines I've seen do is first ensure that their candidate number doesn't have any small factors (so we don't need to run our expensive primality tests on those values); this can be done either by computing $q \bmod s$ for small primes $s$, or by creating a sieve (a bitmap where each bit $i$ corresponds a value $a + bi$; the bit gets marked if $a + bi$ has a small factor).

Both methods can be extended to check either $q$ or $p = 2q+1$ has a small factor:

For the explicit $q \bmod s$ computation, we skip it if that is either 0 or $(s-1)/2$
For the sieve case, we mark bits where $a + bi \bmod s$ is either 0 or $(s-1)/2$

Doing this will significantly reduce the number of iterations you'll need to perform.

Now, if your randomPrime() logic is in a library you can't touch, this advice doesn't help you.  However, if you can do it, this will be of help.


Is there a proxy re-encryption algorithm for Elliptic Curve ECIES?

In ECIES, the ciphertext is a pair:

$$rG, \text{Encrypt}_{h(raG)}(Message)$$

here:

G is the block generator point
aG is the public key that this is encrypted to (in this case, Alice's)
r is a random value
Encrypt is some symmetric cipher (the details aren't important)

What the proxy encryptor needs to do is convert this into:

$$r'G, \text{Encrypt}_{h(r'bG)}(Message)$$

Where $bG$ is Bob's public key, and $r'$ is a possibly different random value.

Surprisingly enough, this is possible, if the proxy encryptor knows the value $ab^{-1}$ (where $a, b$ are Alice's and Bob's private keys).  Note that just knowing the value $ab^{-1}$, without knowing either $a$ or $b$, does not reveal either key.

What the proxy encryptor would do is replace the ciphertext with:

$$ab^{-1}(rG), \text{Encrypt}_{h(raG)}(Message)$$

(that is, multiplies the point by $ab^{-1}$ and leaves the symmetric portion alone).

If we denote $r' = ab^{-1}r$, then we note that this is the same as:

$$r'G, \text{Encrypt}_{h(r'bG)}(Message)$$

And so is a valid ciphertext encrypted with Bob's public key.


Would the rotors in Enigma machines always advance by one position? Or was there a way to set this?

No, there was no way on the Enigma machine to change the behavior of the rotor rotation.

Rotation on the Enigma was a fixed mechanical property of the rotors like the gears in a clock. However, other cryptographers noted this vulnerability in the Enigma and improved it in follow on rotor machines particularly the British Typex and the American SIGABA aka ECM Mark II aka M-134.

The Typex had five non-reflecting rotors (watch this video for why reflecting rotors were a flaw in the Enigma), but the first two were stationary. They could be set and acted like the Enigma's plugboard but did not have the flaw of being reciprocal, a key means of defeating the Enigma's plugboard (watch this video for why).

Typex type 22 or 23 with two plugboards

The other three rotated, but Typex rotors came in two pieces. An wiring insert which scrambled the letter, and a sleeve which determined when it rotated. Each sleeve had different numbers of notches in different locations making it difficult to work out when the rotors would rotate. They could even be reversed giving yet more variation.

SIGABA also had varying rotation but electric signals rather than mechanical notches.  The original used a paper tape with holes in it to allow or block an electrical signal. Each keypress read and advanced the tape which could contain many holes. Each keypress could turn any and all (or none) of the rotors.

SIGABA rotor unit

The next version did away with the paper tape and instead used yet more rotors (control and index rotors) to generate a 5 bit signal, each bit indicated which scrambling rotor (code wheels in the illustration below) to turn.  This eliminated the paper tape and instead rotation was determined by setting the rotation rotors according to daily code.

This provided SIGABA with very good pseudo-random behavior for the time and it is not known to have been defeated during its service lifetime.


Database sharing in Private Information Retrieval (PIR)

Information theoretic PIR protocols that have communication complexity less than the size of the database require multiple, non-cooperating servers [1]. In a computational setting, this is not required. So if you do not want to have to share your database with multiple servers, you should probably use a computational PIR protocol.

1. https://en.wikipedia.org/wiki/Private_information_retrieval#Advances_in_information_theoretic_PIR


Is there a way to find $a$ and $b$ keywords in an affine cipher when only ciphertext but no plaintext is known?

There are several ways to break an affine cipher without any known plaintext.

First of all, for the common case of $n = 26$, there are only $12$ possible values of $a$ (since $a$ and $n$ must be coprime) and $26$ possible values of $b$, for a total of $312$ possible keys.  That's small enough that you can easily test all the keys and simply inspect the results to find the most plausible plaintext.

Even if the alphabet size is larger (say, $n = 256$) you can let a computer try all possible keys and use statistical frequency analysis to sort them by plausibility.  Manual inspection should then let you pick out the correct plaintext from among the few dozen ones rated most likely by the statistical test.  Of course, to set up the frequency model, you'll need to have some idea of what the plaintext might be (e.g. English text, executable binary code, base64-encoded data, etc.) and it must not be too random-looking.

More generally, an affine cipher is a type of monoalphabetic substitution cipher, and so any techniques that can break general monoalphabetic substitution ciphers (such as manual step-by-step frequency analysis) can certainly also break an affine cipher.  Also, many techniques that work on simple Caesar shift ciphers can also be adapted for affine ciphers.  For example, you could try:

Simple frequency analysis: Find the two most common ciphertext symbols, and guess that they correspond to the two most common letters in English (E and T).  That should give you a system of linear equations that you can solve for $a$ and $b$.  If the results don't make sense, try switching the letters around; if that doesn't help, try the next few most common ciphertext symbols and/or the next most common English letters (A, I and N).
Crib dragging: Guess a word of two or more letters that likely appears in the plaintext, and try matching it with different parts of the ciphertext.  Common words like "the" are particularly useful here: if the plaintext is supposed to be English, and there's a particular sequence of three symbols that occurs often in the ciphertext, there's a pretty good chance that it decrypts to "the".  Conveniently, since "the" has three letters, you get a system of three equations and two unknowns, so you can check it for consistency before even attempting actual decryption.


Establishing a shared secret over a unsecure channel

No if strictly they have no prior knowledge and no secondary secure channel to exchange information. Man in the middle attack will always be possible in this case because the two parties cannot authenticate each other. If they cannot authenticate, then even if they have a value at the end, the value may not be secret nor shared with the right party.


One way to do this is to construct two pairing-friendly curves such that the scalar field of the "outer" curve efficiently supports arithmetic for the "inner" curve. Then you can define a circuit for a zk-SNARK over the outer curve, that can verify proofs of a zk-SNARK over the inner curve. This can be done by constructing the outer curve using the Cocks-Pinch method, as in Zexe. In this case you would use an efficient zk-SNARK proving system such as Groth16, to reduce the cost of verifying the inner proofs.

Since I first wrote this answer, another approach has become available using $2$-cycles of non-pairing-friendly curves, as in Halo. (I'm a codesigner of Halo, with Sean Bowe and Jack Grigg.)

The #zcash-wizards channel of the Zcash community chat is a good place to ask about such things.

(This answer previously included a suggestion to use a nested pair of curves with the inner curve as BLS12 and the outer curve as BN. In fact there's no known method of matching up the base field of the BLS12 curve with the scalar field of the BN curve, and there are good reasons to believe that it is not possible to do so.)

Note that any of these approaches will only pay off if the number of proofs being aggregated is large.


DES has a total of 8 s-boxes which takes 6-bit input (say $b_1b_2 ... b_6$) and produces 4-bit output. The s-boxes are the 2-dimensional array of size 4x16.
The bits $b_1b_6$ determine the row of the s-box and bits $b_2b_3b_4b_5$ determine the column. The value of 6-bit input is substituted with the value at cell $S_i[b_1b_6][b_2b_3b_4b_5]$.

In your given question the output of 1st s-box will be the value of $S_1[3][15]$

For reference, you can Cryptography: Theory and Practice, Third Edition (Discrete Mathematics and Its Applications) page 97.


Best way to attack a small e and small m RSA problem?

In the case where one has a small $e$ AND a small $m$, would it be correct to say that if $m<N^{1/e}$ then we can attack by calculating the $e$-th square of $m^{e}$?

Yes, in a textbook RSA context, where ciphertext $c$ for the small $m$ is computed as $c=m^e\bmod N$, that is $c=m^e$ if $m<N^{1/e}$. But in RSA as practiced, either $m$ is large and mostly random (RSA-KEM), or a padding step is used (RSAES-OAEP or RSAES-PKCS1-v1_5), so that won't work.

  best way to approach such an attack practically?

We want to determine if the $e$-th root of $c$ is an integer, and in the affirmative calculate it, which will be $m$.

It is needed a tool that can compute exactly with large integers. Python, GP/Pari, Mathematica, GMP… have appropriate built-in types, Java comes with a BigInteger package, and it is possible to create one in any Turing-complete language. Some tools have built-in functions to check/compute exact $e^\text{th}$ root. For others an option is to obtain an approximation using floating point, then Newton-Raphson or the less efficient dichotomic search.


RSA - Compare two values for encryption exponent, both are relatively prime and $e < λ(n)$

Hint: compute $d$ for the alternate value of $e$ considered. Isn't something rather remarkable? What is the probability that it occurs by chance?

While that is totally immaterial given that $p$ and $q$ are billions-n'-billions times too small to prevent factorization (gross understatement), what if we scaled things?  Why would it matter (caution: there are several levels of answer to that later one)?

Facts relevant to this (and many other sensible RSA questions) can be found by combing Dan Boneh's classic Twenty Years of Attacks on the RSA Cryptosystem (in Notices of the AMS, Vol. 46, No. 2, pp. 203-213, 1999).
I might have properly cited that followup attempt if it had acknowledged what inspired it.


What are good combinations of public key algorithms or primitives for long term security?

For the signatures, hash-based signatures provide a nice solution to your problem: You can use so called hash combiners to instantiate the signature. These are functions that construct a hash function given two or more hash functions and preserve certain properties as long as at least one of the hash function has this property. For example the concatenation combiner:
$C_{H_1,H_2}^{\|}(M) = (H_1(M)\|H_2(M))$

preserves collision resistance and second preimage resistance.

If you use hash functions based on different design principles, e.g. SWIFFT as one that has certain security guarantees steaming from the hardness of lattice problems and one classically constructed one like SHA-3, you can achieve good redundancy.

The big advantage is, that you do not have to implement two different schemes but only one: You would have to implement two different hash functions for message compression anyway but in addition you would also have to implement two "fixed length" signature schemes for multiple signatures.


Random unique key per message, safe to use key as IV?

Is it safe to use the key as the IV of the CBC?

CodesInChaos has answered this sufficiently in the Q&A he linked (AES key equal to IV (CBC mode)) and the TL;DR is: It's risky, but not directly exploitable.

  Do I still need to do any random padding on the IM itself?

Hybrid encryption modes generally don't need random message padding as the randomness is already encapsulated in the key.

Now for some other issues with your scheme:

You're using concatenation and hashing as the MAC. More precisely your MAC construction is $\tau=H(H(M)\parallel K)$ is potentially broken.
You're using CBC. Using CBC in newly deployed system is highly discouraged, especially due to padding oracle attacks and the likes which are only an issue in block-based encryption modes.
You're not using AEAD. Rolling your own mode of encryption and authentication is dangerous without proper knowledge and formal security reductions. Using a proper mode like GCM, OCB or EAX is really recommended and will ease implementation and use proven-secure constructions.
Your RSA encryption is probably risky to say the least. If I'm reading your question right you may be using straight, textbook RSA encryption of the 128-bit secret. However this is highly susceptible to brute-force attacks which can recover this secret in roughly $2^{64}$ steps.


Well, I think OpenSSL has documented this pretty well:

  If an alternative RAND_METHOD implementation is being used (either set
  directly or as provided by an ENGINE module), then it is entirely
  responsible for the generation and management of a cryptographically
  secure PRNG stream. The mechanisms described below relate solely to
  the software PRNG implementation built in to OpenSSL and used by
  default.

  These functions implement a cryptographically secure pseudo-random
  number generator (PRNG). It is used by other library functions for
  example to generate random keys, and applications can use it when they
  need randomness.

  ...

  The RAND_SSLeay() method implements a PRNG based on a cryptographic hash function.

  ...

  hash function; currently SHA-1

So that is certainly not Dual_EC_DRBG. You can switch RNG method by using RAND_set_rand_method but setting a different ENGINE should be preferred for newer applications.

Note that it would not hurt to check this in the source of the openssl implementation you are using. I don't believe it has changed yet, but openssl documentation is not known for its, eh, "up to dateness".


Are MACs vulnerable to birthday attacks?

Are Message Authentication Codes (MAC) are vulnerable to birthday attacks...

Like most things in life, it depends.

Certainly, if you have an $n$-bit MAC, then after about $O(2^{n/2})$ MAC'ed messages, there's a decent probability that you see two different messages $M_1, M_2$ for which $\text{MAC}_k( M_1 ) = \text{MAC}_k( M_2 )$

However, that begs the question: is this observation actually an attack?  After all, the security property of a MAC is "it's hard to generate the MAC of a message you haven't seen"; in the above attack scenario, you've seen the MAC's for both $M_1$ and $M_2$, and so neither would qualify under the "you haven't seen" part.

The pertinent question is "does having two message evaluating to the same MAC actually allow us to deduce the MAC of a message we haven't seen".  For most MACs, it doesn't; there's no obvious way to do this for HMAC, and for nonce-based MACs, the fact that each message was MAC'ed with a different nonce would appear to block any such obvious approach.

However, there is a common MAC where it would appear to be an issue: CMAC.  That is, if we can find two messages $M_1, M_2$ (both a multiple of 16 bytes in length; it is easy to extend this observation to non-multiples of 16 bytes) with $\text{CMAC}_k(M_1) = \text{CMAC}_k(M_2)$, then we know that, for any string $N$, we have $\text{CMAC}_k(M_1 | N) = \text{CMAC}_k(M_2 | N)$.  Hence, if we find such a collision, we can ask for the MAC of $M_1 | N$, and then we immediately know the MAC for $M_2 | N$; this counts as a valid attack.

However, CMAC is the only MAC I can think of with this potential vulnerability.


How does DES decryption work? Is it the same as encryption or the reverse?

DES is based on a Feistel construction - while the one-way function used is.. well.. one-way, you don't need to reverse it at all to "decrypt" (otherwise you are correct we would have a problem). Look at this diagram, specifically the decryption one:

As you can see, even though one half of the ciphertext is passed through the one-way function, there's always a copy of it remaining. In this case, $L_{n + 1}$ goes through the one-way function to mask $R_{n + 1}$, but still becomes one half of the ciphertext, which lets you use it again during decryption to undo the XOR operation you used to mask the other half of the ciphertext.

Then you keep doing that for each round (using the round keys in reverse) and you end up with the plaintext. No information is lost during the encryption process, the one-way function is simply used to mask each half in turn in an interleaved fashion (which can be done again during decryption in the opposite direction, but only if you have the key).

Ultimately decryption is very similar to encryption, a common feature of Feistel ciphers in general. In fact with some arrangements the only difference is the order of the subkeys, which is (or at least was) a big advantage as it makes implementation easier on limited devices, as you can mostly reuse the encryption code for decryption.


What does that mean, that A5/1 is clocked?

The clock term comes from electronic engineering; in each clock, the cells of LFSRs ( flip-flops) are clocked and the data moves. In the shift registers, the data moves from one to another in one direction. As we can see from the below, each flip-flop has a clock input where each has the same clock.

In the LFSRs ( Linear Feedback Shift Register) there is also the feedback that is calculated from the selected tap point is fed the beginning.
Normally LFSR's are clocked for each clock so that new feedback is calculated and the LFSR is shifted so that new output is formed. If you don't clock, then no new feedback is calculated and no shifting occurs, too. The old output is still active. To achieve this in electronics the clock is also controlled by logic. In programing that is way easier (see bottom).
Consider the first LFSR ( index names are free to choose and it is reflected)

When clocked it will become;

See that the data of the cells are shifted to the right and the new value to the left is feedback values calculated from the active taps.
A5/1, which is terribly broken, has three LFSR where each of them has clocking bits, (8,10,10) shown orange on Wikipedia's image. At each clock, the majority is formed from those values.
The majority of the $n$ binary variable means the most occurring value. For three bits, just count the number of ones $c$ if $c > 1$ then the majority is *one ( i.e. number of ones > number of zeros) and the majority bit is $1$, otherwise the majority bit is $0$.

If the majority bit matches the LFSR's clocking bit, then the LFSR is clocked otherwise not clocked.
A simple code can be described for each LFSR as
majority = (L1[8] AND L2[10]) xor (L1[8] AND L3[10]) XOR (L2[10] AND L3[10])

def clockLFSR1(majority):
    if L[8] == majority:
        self.applyClock()

def clockLFSR2(majority):
    if L[10] == majority:
        self.applyClock()

def clockLFSR3(majority):
    if L[10] == majority:
        self.applyClock()


How can I calculate the avalanche effect in symmetric algorithms?

You appear to be under the impression that AES should score better than DES, because AES is stronger than DES.

The issue is that your test is extremely crude; any decent block cipher will pass the test.

If I were to go to an analogy, it's as if you have devised a test for automobiles, which the sole check being 'is there an engine?'.  You run your test on a Yugo, and it passes, you run your test on a high-end Porsche, and it passes; and you ask, the Porsche is a much better car than the Yugo; why isn't it scoring better?

As for the differences between AES and DES, the important ones are:

AES has a much larger key than DES.  The DES key is small enough that it can be (and has been) brute forced (that is, checking each key individually) by adversaries with a reasonable amount of resources; the AES key space is so much larger that, even with the "small" setting of 128 bits, it's infeasible to do so.
The AES block size is larger than DES; with DES (and CBC mode), you'll start to leak contents of the plaintext after encrypting a few Gigabytes; the same will happen with AES, but only after a truly huge amount of data has been encrypted (e.g. the amount of data that travels over the entire internet in a week)
There's also some known ways to apply linear cryptanalysis to DES; however (again) only after a large amount of data has been encrypted.

Your tests won't pick up on any of these differences, and so (as far as your test is concerned), DES and AES look equally good.


Are more complex algorithms easier to break with timing attacks?

Timing attacks rely on operations which do not always take the same time to execute, depending on the processed data. For instance, on a typical software platform (say, a PC) implementing SHA-256, all operations are 32-bit additions or rotations or bitwise combinations which take a constant time to execute, regardless of the actual operand values. SHA-256 is thus largely immune to timing attacks, because processing time, down to the nanosecond, depends only on the length of the input message, not on the values of the bits constituting the message. An attacker observing from the outside a SHA-256 computation would learn nothing about the hashed message, except possibly an estimate of the message length. On the other hand, a simple RSA implementation will leak information because the modular exponentiation incurs data-dependent and key-dependent costs (in a programmer's point of view, the code if full of "if" which operate on values computed from the input data and key).

"Complexity" of the algorithm is mostly irrelevant for that question. You can make a very complex algorithm out of operations which have no timing-related issue. Complexity is, in itself, a bad thing, since it makes analysis more complex (it is much harder to know whether the result is secure or not) and implies a higher implementation cost (in development time, and, often, in code size and execution speed).


RSA - How to change the encrypted numerical result into text?

You don't encode the encrypted result of an RSA encryption to text; it's just a sequence of bytes. It makes no sense as "text". In network traffic such bytes can often just be sent as is, but if you're in a text based protocol (mail , HTTP etc.) one could encode the RSA-bytes from the encryption as base64 encoded data, and this is sometimes done. In either case it's not meant for "human consumption", but used in a program. RSA is not a hand cipher...


The use of linear cryptanalysis for unkeyed hash functions seems to data back to the article (available here) below

Handschuh H, Knudsen LR, and Robshaw MJ, Analysis
of SHA-1 in encryption mode, published in the Cryptographers' Track-RSA Conference, Naccache, D. (Ed.), LNCS 2020, Springer-Verlag, Berlin, pp.70-83, 2001

The authors state:

  SHA was never defined to be used for encryption. However, the compression
  function can be used for encryption. Each of the 80 steps of SHA-1 (divided into
  four rounds, each of 20 steps) are invertible in the five A, B, C, D, and E variables
  used for compression. Therefore, if one inserts a secret key in the message and a
  plaintext as the initial value, one gets an invertible function from the compression function by simply skipping the last forward addition with the input.
  This is the encryption mode of SHA considered in this report. The resulting block cipher is named SHACAL and has been submitted to NESSIE by Naccache and the first
  author.


Difference between Pseudorandom Function vs randomly chosen function

Random function -- function $F$, that is selected randomly from the set $Func$ of all possible functions (with given domain and range).

Pseudo-random function --- family $\{F_k\}$ of functions, that is indexed by the parameter $k$ (which serves as a number). It is pseudo-random, because if someone picks $k$ secretly and lets you interact with $F_k$, it should look like you are working with a random function, whereas in fact it is chosen from a much smaller set, not from the set of all possible functions.


I am simplifying greatly, maybe someone else can provide a
more formal answer.

  I see that homomorphic encryption works with only numeric data.

There are many ways to encode strings into integers,
you can encode a string into bytes and then translate these bytes to an integer.

  I have read that homomorphic has scalability issues as it creates a 100x increase in encrypted data.

Homomorphic encryption indeed comes at a price both in size of the ciphertexts and efficiency of the computations.

  Which one to use for which use-cases?

ZK-SNARKS

ZK-Snark is a zero-knowledge proof-of-knowledge: One party, the Prover, knows a secret and wants to convince another party, the Verifier, that a statement involving the secret is true, without revealing the secret.

Example: A user knows a password $x$ and a server knows a hash of the password $h$, the user needs to prove the statement:

I know a value $x$ such that $H(x)=h$

Homomorphic encryption

Homomorphic encryption is type of an encryption scheme: A value $x$ is transformed into a ciphertext $c=Enc_k(x)$ using a secret key $k$, such that $c$ doesn't reveal anything about $x$ without the key.

We say that such a scheme is homomorphic for a specific operation (I will design it by $\cdot$) if given $Enc_k(x_1)$ and $Enc_k(x_2)$, one can compute
$Enc_k(x_1\cdot x_2)$ without decrypting the ciphertexts.

We say it is fully homomorphic, if given encrypted inputs
$Enc_k(x_1), \dots Enc_k(x_n)$, one can compute for any arbitrary function $f$, the value $Enc_k(f(x_1,\dots, x_n))$ without decrypting the ciphertexts.

Use case: We know some secret value $x$, and want the value $f(x)$. Since $f$ is too computationally intensive, we need to delegate it to a worker (e.g. a cloud server) with more resources.
To avoid revealing $x$ to the worker, we can send $Enc_k(x)$ to the worker, which computes $f$ via homomorphic computations, and sends back $Enc_k(f(x))$. We can then decrypt $f(x) := Dec_k(Enc_k(f(x)))$.

Comparison

Zk-snarks are usually used when the computation is realized by the party holding the secret, which is trusted to protect the secrets, but is not trusted to correctly execute the computation.

Homomorphic encryption is usually used when the computation is realized by a party that doesn't know the secrets, and is not trusted to protect these secrets, but is trusted to correctly execute the computation.

These two constructions could be combined if you want to make sure that the worker sends back $Enc_k(f(x))$ and not some other value $Enc_k(g(x'))$. Then we could require the worker
to send back a proof that the computation was done correctly.
But then we wouldn't need the zero-knowledge property, since the worker doesn't know any secret.


No it's not. It is really bad.

Basically, this is a stream cipher, where your keystream is $key | key| key|key....$. This is really bad, similar to the level of "using OTP twice". As If you take a block of size keylength, and XOR two such blocks, then you get the XOR of the plaintexts. Depending on the nature of the plaintext, this can be really easy to guess.

If you want an easy encryption scheme, like XOR the plaintext with a keystream, use a stream cipher or a block cipher in OFB mode of operation. If you want a construction with SHA512, that is also possible, see e.g.

Is it feasible to build a stream cipher from a cryptographic hash function?
Can I use HMAC-SHA1 in counter mode to make a stream cipher?

However, since hash functions have different security properties than stream ciphers, it might be better to use a construction which is actually intended to be used this way. In a similar context, Bruce Schneier wrote (about ciphers based on hash functions):

  While these constructions can be secure, they depend on the choice of the underlying one-way hash function. A good one-way hash function does not necessarily make a secure encryption algorithm. Cryptographic requirements are different. For example, linear cryptanalysis is not a viable attack against one-way hash functions, but works against encryption algorithms. A one-way hash function such as SHA could have linear characteristics which, while not affecting its security as a one-way hash function, could make it insecure in an encryption algorithm such as MDC. I know of no cryptanalytic analysis of particular one-way hash functions as block ciphers; wait for such analysis before you trust any of them.


Factoring RSA-129 with a personal computer today

From what I can gather it took about 2.5 months to factor a 512 bit RSA key on a personal computer from 2009 with a dual-core athlon64.

https://www.cemetech.net/projects/uti/viewtopic.php?t=8888

A typical desktop of today has about twice as many cores and twice the clockspeed. So that would cut it down to about two and a half weeks.

Furthermore modern processors have better IPC and your key is less than 512 bits.

So clearly doable but probablly not instant.


Using $key^{th}$ multiple of $\pi$ as a one-time pad

That is not practical since either you keep a sequence of the bits of the $\pi$ or regenerate them every time. You may need to store 64GB sequence if you want to encrypt such files.
Then you need to multiply it with the 128-bit number. That is not practical, consider multiplication of 64GB number with a random 128-bit number.

OTP needs true random bit sequences like flipping coins, $\pi$ is not since the sequence is there! It is known to everybody.

In modern Cryptography, we use the 128-bit random key with a PRF to produce a long enough secure key-stream to encrypt the message like ChaCha. This is the way we encrypt messages. They are very fast like 3GB/s with AES-NI.
No need to store or heavy calculation like you proposed.

It is not KPA secure yet CPA!. Given message and ciphertext, we can find the 128-bit key by dividing.

How the 128-bit key is transferred is not clear. The better way to use DHKE than a KDF than encrypt with xChaCha20-Poly1305 with this you will get forward secrecy - if you DELETE the key after decryption - integrity, authentication, and integrity where your scheme only may provide confidentiality.


Security of somewhat homomorphic encryption via LSB encoding?

As hinted by @kelalaka in the comments, note that $q$ is odd, and $\gcd(2,q)=1.$

Therefore within $Z_q$ we have that $2e\neq 0,$ if and only if $e \neq 0,$ so the noise is never masked.


Please punch holes in this authentication scheme

The protocol's description includes "Alice then encrypts $R_B$ with her private key". This has no standard meaning. Comments have clarified it is used an "RSA encryption scheme with proper padding" and I am taking as granted that encryption of $R_B$ using the private key half of $K_A$, denoted $K_A^-(R_B)$, is obtained by padding $R_B$ as in encryption, then applying the RSA private key exponentiation of $K_A$. This can be a valid form of signature (while RSA signature and encryption usually use different padding, it is possible to define a secure padding that works for both encryption and signature).

The protocol does nothing to prevent a MitM attack. In the usual definition of that, Charlie's goals are:

impersonate as Alice to Bob, or/and to Bob as Alice;
be able to understand all that Alice says to Bob, or/and Bob says Alice;
be able to make Alice believe that something Charlie decides comes from Bob, or/and make Bob believe that something Charlie decides comes from Alice.

In order to achieve every single of these goals, Charlie:

receives "I'm Alice" from Alice, relays that to Bob;
receives "I'm Bob" from Bob, relays that to Alice;
receives $K_A^+(R_B)$ from Bob, relays that to Alice; (I'm using the first drawing as reference, where's that before the next step)
receives $K_B^+(R_A)$ from Alice, relays that to Bob;
receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
receives $K_B^-(R_A)$ from Bob, relays that to Alice, and also applies Bob's public key to that and removes any padding, thus getting $R_A$.

From then on, Charlie acts with respect to Alice using the (unspecified) protocol defined for Bob, including deciphering Alice's messages, and forwarding anything Charlie decides to Alice, which has no way to tell that it comes from Charlie rather than Bob; and similarly acts with respect to Bob using the (unspecified) protocol defined for Alice.

Charlie reached all his goals. The only thing that Charlie does not know is the padding used in $K_A^+(R_B)$ and $K_B^+(R_A)$ if that's random padding, but there is no indication that some use is made of it.

Further, if for some reason Charlie wants to choose his own nonce $R_C$ as in the second drawing, rather than use $R_A$ or $R_B$ (perhaps because the protocol is extended with "After authentication, perform the action defined in the low 20 bytes of the $R$ that I sent"), Charlie can still achieve that. In order to impersonate Alice w.r.t. Bob using an $R_C$ of Charlie's choice instead of $R_A$ chosen by Alice, Charlie

receives "I'm Alice" from Alice, relays that to Bob;
receives "I'm Bob" from Bob, relays that to Alice;
receives $K_A^+(R_B)$ from Bob, relays that to Alice;
receives $K_B^+(R_A)$ from Alice, discards this, computes $K_B^+(R_C)$ and sends that to Bob;
receives $K_A^-(R_B)$ from Alice, relays that to Bob, and also applies Alice's public key to that and removes any padding, thus getting $R_B$;
kills the session with Alice;
receives $K_B^-(R_A)$ from Bob, discards it.

From then on, Charlie acts with respect to Bob using the (unspecified) protocol defined for Alice, including deciphering Bob's messages, and forwarding anything Charlie decides to Bob, which has no way to tell that it comes from Charlie rather than Alice.
Kudos to mikeazo for finding a mistake, hopefully fixed.

In a comment to the present answer, the protocol is extended by adding:

  Alice sends Bob a pre-master secret encrypted in Bobs public key; then
  both of them use this premaster to calculate master secret.. and
  communicate using that key"

That extended protocol is still vulnerable to an attack where Charlie impersonate Alice with respect to Bob. Charlie performs as in the first attack, then

kills the session with Alice;
pretending to be Alice, sends Bob a pre-master secret of Charlie's choice encrypted in Bobs public key;
then Bob and Charlie use this premaster to calculate the master secret.

In fact, no addition after the protocol can protect against a MitM attack, unless it uses another public key of the participants, or another padding scheme with the existing key.

That's because Alice's behavior allows using her as a decryption oracle: by participating in the beginning of whatever extension of the protocol, Alice accepts doing steps that can be abused into the equivalent of decrypting anything with her private key, and since no other use is defined for her private key, making a fake connection attempt with Alice is as good as having Alice's private key.

The protocol can be strengthened, and the unclear "encrypt with private key" removed, as follows.

We consider an asymmetric encryption scheme with encryption $E_{Pub}(P)\mapsto C$ and decryption $D_{Priv}(C)\mapsto P$. We assume an infrastructure to verify the validity of public keys.

A participating entity $A$, when communicating with (alleged) entity $B$

sends I'm $A$, and receives I'm $B$;
checks that $B\ne A$;
obtains the authentic public key $Pub_B$ of $B$ (how is not part of this protocol; a common technique is that $Pub_B$ is sent together with I'm $B$ as part of a certificate, which is verified according to a master public key);
draws a secret random $R_A=R_{A0}||R_{A1}||R_{A2}$ where each $R_{Aj}$ is 256-bit;
enciphers $R_A$ using $Pub_B$, yielding $C_A=E_{Pub_B}(R_A)$, sends it, and receives an alleged $C_B$;
deciphers $C_B$ using $Priv_A$, yielding $R_B=D_{Priv_A}(C_B)$ (or an error, which aborts the protocol);
breaks $R_B=R_{B0}||R_{B1}||R_{B2}$ into $R_{B0}$, $R_{B1}$, $R_{B2}$;
sends $R_{B0}$ and receives an alleged $\widehat{R_{A0}}$;
compares $R_{A0}$ and $\widehat{R_{A0}}$ (an inequality aborts the protocol);
uses $R_{A1}\oplus R_{B2}$ as an AES-GCM key for communication from $A$ to $B$, and uses $R_{A2}\oplus R_{B1}$ as an AES-GCM key for communication from $B$ to $A$.

Messages are exchanged at steps 1, 5, 8, and 10 only. The order in which messages are sent and received in these steps is left unspecified, so that $A$ and $B$ can proceed without waiting for the other side between steps involving message exchange. Step 2. is necessary, otherwise an adversary reflecting what Alice sends will successfully make Alice accept whatever information she sends at step 10.

This protocol is better than the original. At least, a passive eavesdroper can not decode the information exchanged at step 10, as would have been possible in the original protocol. However this scheme is still NOT secure against a MitM attack assuming only that $E_{Pub}(P)\mapsto C$ perfectly preserves confidentiality. In particular, an attack is possible when $E_{Pub}$ encrypts each bit of the plaintext $P$ separately; finding this attack is left as an absolutely necessary exercise to any reader diving into protocol design.

When $E_{Pub}(P)\mapsto C$ is one of the RSA encryption scheme in PKCS#1, or when we remove steps 7. and 8. (making $R_{A0}$ and $R_{B0}$ pointless), I can not think of any mean for a MitM to intercept or alter any part of the plaintext exchanged at step 10, provided $A$ and $B$ act according to the protocol, and in particular never disclose or use any of $R_A$, $R_B$, $R_{A1}\oplus R_{B2}$, $R_{A2}\oplus R_{B1}$ other than as instructed.


Hashing/encrypting an integer to produce an unique integer in the same range

You indeed need Format-Preserving Encryption. It is a pretty easy concept, and this paper by Black and Rogaway should be readable for non-specialists. The simplest method you should be satisfied with is to use a cycle-walking cipher. Suppose :

Take $I'\leftarrow E_K(I)$;
Repeat until $I'\in [0\ldots M-1]$,

where $E_K$ is a conventional cipher with key $K$. However, the block size $n$ of $E$ should only slightly exceed $\log M$, otherwise the procedure would take too long.

If a cipher with such block length is not available, the following construction, known as Swap-or-not cipher, should help:

$E_K(X):$

for $i\leftarrow 1$ to $8 \log M$

$K_i \leftarrow AES_K(i) \pmod{M}$;
$X' \leftarrow K_i-X \pmod{M}$;
$X'' \leftarrow \max(X,X')$;
if ($F_i(K,X'')=1$) then $X \leftarrow X'$.

Here $F_i$ is some key-dependent predicate of $X''$. It must have algebraic degree or higher. For instance, it can be a polynomial of degree 2 over $F_2$, whose coefficients are encryptions of some constants by AES on the key $K$ (similarly to $K_i$).


Which gives better deterministic encryption SIV or Plain ECB mode?

Both:

Secure deterministic encryption for one-block messages.

ECB:

No expansion for block-sized messages.
Faster.

SIV:

Authentication.
Works for messages of any size.


a bit late, if I had been pinged on this, I could have answered earlier.

$x \vee z$ was chosen for the following reason:

$a \wedge b$ is biased towards 0. As a result if we only used $\wedge$ the linear weight of the equation would have a strong bias towards 0.
As $a \vee b$ is biased towards 1, this aims to compensate.

The $z ≪ 1$ instead of just $z$ in the equation is necessary to ensure that this is a permutation, otherwise the equations do not have an inverse and we really wanted a permutation and not a transformation.

As for the why $⊕⊕((∧)≪3)$, if you remove the $x \leftrightarrow z$ swap, you realize that the shape of the expression is:
$x \leftarrow x \oplus z' \oplus EXPR$
$y \leftarrow y \oplus x \oplus EXPR$
$z \leftarrow z \oplus y \oplus EXPR$
We already discussed why $z'$ is $z ≪ 1$, now if you look at $EXPR$ you notice that in all cases, the destination is not included in the non-linear binary expression, as a result, this increase the complexity of linear trails as you have to track more variables.


Choosing good parameter for Lenstra's elliptic curve factorization

It becomes clear once you understand what $p-1$ and ECM are doing. I'll start with $p-1$, since it is simpler.

Suppose the number you want to factor, $n$, is the product of two primes: $p$ and $q$. If we knew $p-1$, we could get $p$ from $n$ by doing

$$
\gcd(a^{p-1} - 1 \bmod n, n) = p.
$$

This works because by working modulo $n$, we're working "in parallel" modulo $p$ and modulo $q$. And modulo $p$, we get $a^{p-1} - 1 = 0 \bmod p$ (for nonzero $a$) by Fermat's little theorem. So $a^{p-1} - 1 \bmod n$ is going to be 0 modulo $p$, but not modulo $q$, and the $\gcd$ gives us a factorization of $n$.

However, we don't really know $p-1$ — if we did, we wouldn't be looking for $p$ — and that puts a dent in our plans. There is an alternative route, however: if we can find a multiple of $p-1$, that works too:
$$
a^{k(p-1)} - 1 \bmod p \equiv (a^{p-1})^k - 1 \bmod p \equiv 1^k - 1 \bmod p = 0 \bmod p.
$$

So what Pollard's $p-1$ does is select an exponent that is likely to contain every single factor of $p-1$. An easy way to do this, that works as long as $p-1$ only has small-ish factors, is simply to make the exponent the product of all primes: $2\cdot3\cdot5\cdot7\ldots\cdot B_1$, where $B_1$ is our upper bound. This, however, misses power-of-prime factors, such as $2^2$ or $3^5$. So another exponent that catches everything is the factorial of $B_1$: that one is certain to catch every possible factor up to $B_1$!

Some observations about $p-1$ leads us to ECM. $p-1$ is the order of the group formed by the integers modulo $p$, denoted by $\mathbb{F}_p$. Further, if the order of $\mathbb{F}_p$ only has small factors, we can find $p$ by the aforementioned exponentiation. It turns out this generalizes to other mathematical groups. In particular, the group of points in an elliptic curve modulo $p$ is parameterized by two additional numbers $a$ and $b$:

$$
E_{a,b} = \{ (x, y) : y^2 = x^3 + a x + b \pmod{p} \}
$$

Each curve (parameterized by a and b) modulo $p$ has an order ($\#E$, analogous to $p-1$ above) in the range
$$
p + 1 - 2\sqrt{p} < \#E < p + 1 + 2\sqrt{p}.
$$
Further, for each order in that interval, there is an $(a,b)$ tuple that yields it.

Suppose we pick a random elliptic curve $E_{a,b}$, and run it modulo $n$ (again, "in parallel" in both $p$ and $q$). Picking a random point in the curve, $P$, and multiplying it by $\#E$ results in the point at infinity (the elliptic curve analogous of 0):

$$
\#E\cdot P = \infty
$$

This special point, usually represented as $(0,1)$, triggers divisions by $0 \bmod p$ but not $\bmod~q$, and that nets us a factor. The logic for picking the exponent is the same as $p-1$: every prime and prime power up to $B_1$, and hope for a hit.

Besides the factorial, another good way to pick the exponent is the lowest common multiple of every integer up to $B_1$; this yields every prime power lower than $B_1$, and is much smaller than the factorial of $B_1$.


Help to understand the chameleon hash function?

Edit: Sorry, I know this is bad form, but I'm replacing my entire answer :).

The proof takes place in the so-called CKS-light model, which allows the adversary only two "register honest" queries, i.e. the ability to register two identities of his choice and receive their generated public keys. In the end, he must distinguish the shared secret of these keys from random.

In the proof, the fact that the public key involves a degree-two polynomial in $t$ is used to generate a uniformly random pair of keys satisfying $p(t) = a_0 + a_1t + a_2t^2 = 0$ for the same polynomial $p$, and these $t$-values are used to satisfy the adversary's two honest-key queries. This strongly suggests that the 2 in "degree-2 polynomial in $t$" and the 2 in "adversary only gets 2 honest queries" are one and the same.

One way to test this intuition is to adjust the security game so that the adversary gets 3 honest queries and see if this lets you break it. Another way is to drop the polynomial in $t$ to degree 1 and see if you can break it under the same security model. I think either one will give you some intuition as to why $t$ is used the way that it is.

(My original answer suggested that if the polynomial in $t$ had only degree 1, and the adversary was able to register two identities with the same secret key $x$, this would give him undue power. This is true but irrelevant, since the security game does not let the attacker do this.)

Edit2: As for problems in the proof in the appendix: I'm pretty sure that we need $u_i = g^{b_i}$ for $i = 0, 1, 2$; but I don't see this written anywhere. Also the line
$$ X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i2^{3k}}}$$
is wrong; it should be
$$ X_i = D^{\alpha_{3-i}b(t_i)} = (u_0u_1^tu_2^{t^2})^{\frac1{\alpha_i}}$$
which sets the secret key $x = 1/(\alpha_i 2^{3k})$ as claimed.


Are there any hand ciphers not obsoleted by computer cryptanalysis?

One time pad is definitely both easy to do and has perfect secrecy, but key management is a pain and can compromise security. Basically a Vigenère cipher with a key as long as the the message should be secure, because different keys can create ALL possible messages with equal probabilities.

Again, it's a one time pad, so no KPA, CPA, or CCA security. Actually I don't think any pen & paper cipher system has such security.


Yes. $\:$ "simply XORing" is obviously malleable, which may allow related-key attacks.

"When storing a short key, e.g. a 256-bit ECC private key," the "good reason to use AES" is

that "the XOR with a single PBKDF2 (or other KDF) output block" is not necessarily sufficient,

since an adversary might also have changed the stored public key.