Finding a keylength in a repeating key XOR cipher

You'd be trying each possible displacement (offset).

Suppose the ciphertext is CXEKCWCOZKUCAYZEKW.  Here's displacement 1:

CXEKCWCOZKUCAYZEKW
 CXEKCWCOZKUCAYZEKW

At displacement 1, there are no matches (nothing where the a letter in the top line is equal to the letter immediately below it).

Here's displacement 2:

CXEKCWCOZKUCAYZEKW
  CXEKCWCOZKUCAYZEKW
      ^

You can see that, at displacement 2, there is one match.

Here's displacement 3:

CXEKCWCOZKUCAYZEKW
   CXEKCWCOZKUCAYZEKW

At displacement 3, there are no matches.

In this way, you can count the number of matches at each displacement.

The idea is that, if you line up the ciphertext with itself displaced by $k$, where $k$ is the period of the keystream (i.e., the length of the key), then you get a match in the ciphertext (offset by $k$ places) if and only if there is a match in the plaintext (offset by $k$ places).  Now it's a property of English language that the frequency distribution of English letters is not uniform: some are more likely than others.  If you pick two positions at random from an English text, there's about a 6% chance (say) that those two positions have the same letter.  Consequently, when you've guessed $k$ correctly, there's about a 6% chance that any particular ciphertext letter matches the one $k$ positions later.

In contrast, when you line up the ciphertext with itself displaced by something displacement that does not match the key length, the chances of a match at any particular position are much smaller (1/256, if ciphertexts are bytes; 1/26, if ciphertexts are letters).


Is there a difference between PRF and a hash function?

No, the two primitives are definitely not the same.

A pseudorandom function is a keyed function that is (computationally) indistinguishable from a function chosen at random from all functions with matching domain and range as long as the key remains secret.

On the other hand, a cryptographic hash function is a function with either a publicly known key (in theory) or no key at all (in practice) that is compressing and collision resistant. That means, it maps long inputs to outputs of a fixed length and it is hard to find two inputs that map to the same output.


Block Cipher vs Stream Cipher in Web Application

Very few cryptosystems actually use a block cipher directly (i.e. in "ECB mode") to encrypt data — and those that do usually only do so because whoever designed them didn't really understand how a block cipher should be used.

Rather, the main use of block ciphers in cryptography is as versatile building blocks for other cryptographic components, such as stream ciphers, message authentication codes, hash functions, KDFs etc.  In particular, the usual way to use a block cipher to encrypt free-form data is by using a mode of operation such as CBC, CFB, OFB or CTR (or an authenticated mode like EAX, GCM, OCB or SIV) which actually uses the block cipher to construct a kind of stream cipher.

Thus, the actual distinction, insofar as there is one, is not between block ciphers and stream ciphers as such, but between stream ciphers based on block ciphers (like AES-CTR or AES-CBC) and "primitive" stream ciphers not based on block ciphers (of which the most common is probably RC4).

I don't really have any reliable statistics on how much those are respectively used in web applications, but my gut feeling would be that the majority (say, 95%) of (symmetric) encryption schemes used in such systems are probably based on block ciphers (mostly AES, some 3DES, occasionally rarer types like Serpent, Blowfish or old single DES).  Their main competitor is RC4, with a small but non-negligible share (say, 5%), while all other "primitive" stream ciphers (like the eSTREAM ciphers) are probably marginal (< 1%), mostly because few crypto libraries support them.

(The share of RC4 probably goes up a bit if its use in SSL / TLS is included in the total, particularly since many websites switched to it after the BEAST attack exposed weaknesses in the TLS 1.0 implementation of AES-CBC.)


AES - Encrypting multiple blocks of files

If you don't allow changes, renames and overwrites then you could create an IV by hashing (e.g. with SHA-256) the unique location of the file. If you want to allow changes/renames/rewrites you could re-encrypt with an IV that also uses the time of the change, if that is unique and stored reliably. That is, if you want to keep the size of the files to the one stated. If you are OK with slightly larger files, it is better to prefix a random IV.

Once you've got your randomized IV then you can encrypt with any secure mode. CBC would be an option, or CTR mode encryption. If you always use exact file sizes then you may be able to forgo padding - only do this if 1KB is the maximum size, otherwise perform PKCS#7 padding. You may reuse your key as long as the IV remains unique. In response to the question, yes, this would be protected against known plaintext attacks.

If your keys are similar then you've got a big problem. You should use random keys or use a password based key derivation function (PBKDF) to derive keys from passwords. Even then, you would require quite a strong password, as offline attacks seem possible.


A discrete-log-like problem, with matrices: given $A^k x$, find $k$

The answer appears to be similar to one that I asked on cstheory.SE about Discrete log in GL(2,p) (i.e., given $A,B$, find $k$ such that $A^k=B$).  In this question we are given less information, but similar techniques should still apply.

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix.  Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.  This means that $A$ can be expressed as a concatenation of Jordan blocks:
$$A = \begin{pmatrix} J_1 \\&\ddots\\ &&J_n\end{pmatrix}.$$

Each Jordan block gives us an independent system of equations, so let me look at a single Jordan block at a time.  We can break this down into cases, based upon the size of the Jordan block $J$:

A size-1 Jordan block. Suppose $J$ is a $1\times 1$ Jordan block, i.e.,
$$J=\begin{pmatrix} \lambda \end{pmatrix}.$$
Then it is easy to see that the problem is exactly as hard as the discrete log to base $\lambda$ (unless $x=0$ in this component, in which case it is unsolvable for information-theoretic reasons).
A size-2 Jordan block. Suppose $J$ is a $2\times 2$ Jordan block, i.e.,
$$J = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$
where $\lambda \ne 0$.  A simple induction shows that
$$J^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$
Let $x=(x_1, x_2)$ and $y=(y_1, y_2)$.  Then we obtain the linear equations
\begin{align*}
\lambda^k x_1 + k\lambda^{k-1} x_2 &= y_1\\
\lambda^k x_2 &= y_2
\end{align*}
which has the solution
$$k = \lambda (y_1 - x_1 y_2/x_2)/x_2.$$
We see that as long as $x_2 \ne 0$, the problem is easy and we can solve for $k$ with a little bit of arithmetic (no discrete log needed).  If $x_2=0$, I'd conjecture that this case is hard.
A larger Jordan block. If we have a larger Jordan block, say $m \times m$, basically the same thing happens.  The top row of $J^k$ is $(\lambda^k, k \lambda^{k-1}, {k \choose 2} \lambda^{k-2}, \dots)$, and each subsequent row is a right-shift of the one before it.  Then, as long as $(x_2,x_3,\dots,x_m) \ne (0,0,\dots,0)$, we can solve for $k$ easily as in the $2\times 2$ case.

So, each Jordan block gives us a chance to solve for $k$.  If any of the Jordan blocks are easy, we learn $k$.  If all of the Jordan blocks are hard, learning $k$ is hard.

In summary: If the Jordan normal form of $A$ is diagonal, and at least one of the diagonal elements is such that discrete log to that base is hard, then this problem is as hard as the discrete log.  On the other hand, if the Jordan normal form is not diagonal---i.e., if it has at least one Jordan block of size $>1$---then the problem is easy (except in corner cases where the wrong components of $x$ happens to be zero).


Emphemeral key creation from a long term shared secret (without DH)

Let's create a simple scheme that includes authentication and the dependence of the session secret on both the long term secret $K$ as well as random generators of both sides:

generate and store random $R_A$ at A;
send random $R_A$ from A to B;
generate and store random $R_B$ at B;
send $(R_B, MAC(K, R_B \| R_A \| B \| A))$ to A;
let A validate that the MAC authentication tag is correct and that B, therefore, controls key $K$;
send $MAC(K, R_A \| R_B \| A \| B))$ to B;
let B validate that the MAC authentication tag is correct and that A, therefore, controls key $K$;
let both sides calculate $Info = R_A \| R_B$ and $K_S = KDF(K, Info)$

Here $A$ and $B$ are identity strings of the entities A and B respectively.

Currently only one session key is calculated, but it is easy to add e.g. a label and identity to the $Info$ structure to calculate specific keys (so to create a message authentication key for A, you could create $Info = R_A \| R_B \| \text{"Auth"} \| A$ where $\text{"Auth"}$ is the label and $A$ is the identity of A, for instance, a serial number. Using separate session keys for specific uses and entities is highly recommended.

The above mixes a challenge / response protocol with session key establishment. There are many variations for such schemes.

You can just swap randoms, calculate and create session keys as above, and use one of them to authenticate the parties, instead of relying on $K$ for authentication.

You can, of course, skip the authentication of the parties entirely. But then you would not know that you're communicating with a legit party. You would be sure of the authenticity of the entity when you'd receive the first authenticated message protected by the newly established session key. However, I would strongly advise against mixing entity and message authentication - if just for the error handling if the authentication does not succeed (but there are more issues than just that).

Yet another variation would be to rely on a random value generated by a single party. This is more efficient and could remove one handshake message from the protocol. However, the resulting session key now only depends on the correctness of one random number generator.

Note that these purely symmetric schemes do not provide forward security. That means that the security - especially the confidentiality - of the messages depends fully on the confidentiality of the key $K$. If it ever gets known then an adversary can simply decrypt stored sessions. Don't forget to destroy your keys when they are not needed anymore.

There are of course standards for these kind of schemes, but I'll quote Andrew S (Andy) Tanenbaum on standards: "The nice thing about standards is that you have so many to choose from..."

I noted ratchets as well in the comments; I didn't go into that as I think it is more targeting creating the next long term key rather than an ephemeral session key.


Serpent block cipher : S0 to S7 functions unclear

The reason it is taking 4 32-bit integers into the round function is because it IS a bitsliced implementation.

It bitsclices 32 4-bit sboxes into 4 32-bit inputs and uses standard logical operations on the words to get the job done.
The sbox you posted was not generated by Osvik, but he generated a set of optimized blitsliced sboxes for 32-bit implementations of Serpent. His sboxes use only 5 registers, and are faster even though they use more logical operations because data does not need to be moved out of cache. I would suggest using his sboxes, unless better ones are now available. Osvik's sboxes are generally 25% faster on modern processors, and much faster on older ones.

Non bitsliced mode will be extremely slow in software, unless it is on something like a 8-bit cpu.


Why does NTRUEncrypt lack a formal security proof?

NTRU, as it was originally introduced, is based on what people now call the "NTRU assumption", which really just assumes that it is difficult to break NTRU.  Annoyingly circular, but that's how it is.  Similar to how breaking RSA is not provably as hard as factoring (technically it is based on the "RSA assumption"), but people still think it is hard, NTRU was conjectured to be secure based on the fact that it is hard to find the shortest vector in a lattice (which is the private key).  The SVP problem is actually NP-complete.  However, you can't really make a secure cryptosystem based on an NP-complete problem.  You need some related problem with good average-case hardness to work with.  This was in 1996.

The paper you reference by Stehlé and Steinfeld does modify NTRU to be provably reducible to some standard lattice problems.  However, the problem they use (Ring Learning with Errors) was not formalized or studied until 2005.  So the answer really is that there was a lot of work on the complexity of lattice problems that still needed to be done when NTRU was published, and the authors didn't have the tools necessary to prove it secure at the time.


Any side effects of switching from Rijndael to AES in a .net application?

are there any side effects to switching to AES that aren't readily apparent?

Key sizes: AES is only defined for 128, 192, and 256 bit keys. Rijndael supports other key sizes. There is not much benefit to using the key sizes in between these two, but if you use AES they will not be available anymore.
Block size: Rijndael allows a wider range block sizes than AES
Performance: Using AES could lead to (notable) performance increases. Modern CPUs support a hardware instruction for evaluating AES that will be significantly faster than a software implementation. This will be dependent on the machine that is executing the code, as well as the implementation.

  Or does the encryption method not matter as long as the inputs and outputs are the same?

The encryption method very much does matter. Different ciphers are not compatible with each other.

AES and Rijndael are not different ciphers per se. AES is the title given to the standardized variants of Rijndael.


Given enough RSA ciphertext, is it possible to determine which key was used?

Yes, it is possible to determine with some certainty which public key in some known set was used to produce RSA ciphertexts made with the same key in this set, given enough ciphertexts, and if neither the public moduli nor the random padding are made with intend to hide which public key was used.

Assume that the set of $k$ public keys have public moduli $N_i$, ordered in increasing order, and we initially have no clue about which might be the one used. If we chose random padding as in any of the two PKCS#1 encryption paddings (randomly and independently of the RSA key), any of $r$ ciphertexts is essentially uniform on the interval $[0,N_j-1]$ where $N_j$ is the public modulus actually used to produce the ciphertexts. The obvious strategy to guess the public key used is to determine the largest of the ciphertexts $C$; the most likely public key in the set is the one with the $N_i$ immediately superior to $C$, and $i\le j$ holds.

Odds that our guess $N_i$ of the public modulus is right are $1/\sum_{j\ge i}(N_i/N_j)^r$, which depends only on where $C$ falls in-between the public moduli, and the values of these (justification: only $j\ge i$ can hold; for any of these $j$, the odds to get a $C$ not higher than what we actually got were $p(C,N_j)=(C/N_j)^r$ before we knew $C$; all these $j$ were then assumed equally likely; therefore the odd of $i=j$ are the ratio of $p(C,N_i)$ over the sum of the $p(C,N_j)$ for $j\ge i$, which simplifies to the expression given).

Note: it is easy to defeat this guessing; for example, when using 2048-bit $N$, encrypt a given plaintext until the result is 2047-bit or less, before sending it.


How to hash a structure that needs to include that hash's outcome?

First, a hash does not provide integrity. You would need a MAC (like HMAC) or a digital signature to ensure the message hasn't changed in transit.

You'll have to put some standard value (say all zeros) into the field which holds the MAC, compute the MAC, then insert the value. Otherwise you have a chicken and egg problem. You need the MAC value to compute the MAC value. So which comes first the MAC or the header you want to compute the MAC over. See the issue?

To verify the MAC, the receiver would pull out the MAC tag, replace it with all zeros (or whatever you used), compute what the MAC should be, compare with the extracted tag.

If you are not restricted to the header as defined, placing the buffer for the MAC at the end of the header would be the best. That way you can just MAC the data before the MAC slot.


Difference between Pure EdDSA (ed25519) and HashEdDSA (ed25519ph)

This is just a preventive measure. Without this separation, an attacker knowing ed25519ph(m) would also learn ed25519(h(m)).

I'm not aware of any real-world protocol using both simultaneously and where that would be an issue, but it's not far-fetched to think that it could be the case.

Domain separation is good hygiene and has become very common in new designs.

The choice of dom2() being a blank string when using ed25519 was only made to remain compatible with existing implementations.


If you really can use all 95 printable ASCII characters, you're better off encoding everything in binary (however you want) into 64 bits, then encrypting that with your secret key (using a cipher with a 64-bit block size, such as 3DES), then turn the result of that into 10 characters using an encoding from binary into base-95.  You can actually encode 64 bits into 10 characters using only 85 characters, so you could omit some that might be a problem (e.g. SPACE).  Since you're encrypting only one block, and they're guaranteed to be unique, you can simply use it in ECB mode (no IV, no chaining modes).

Then just turn it into a 10 digit base-85 number (the same way you'd convert binary to base 10), then map each of the 85 possible values for a digit (0-84) into an ASCII character (either with a lookup table or something as simple as adding 0x21).

You'll want to make the data as well-structured as you can so that you can detect any tampering, including perhaps a (small) checksum of some sort, and verify all 64 bits as being valid/well-formed.


Key construction in the Full Cramer-Shoup cryptosystem

Yes, if you allow to introduce other primitives into the PKE scheme.
The Kurosawa-Desmedt scheme is an example whose secret key consists of four exponents in $\mathbb{Z}_q$.

Let us fix a group $\mathbb{G}$ of prime order $q$. Let $H$ be a secure hash function (TCR security).

Cramer and Shoup

Let us review the Cramer-Shoup scheme. As you wrote, the scheme is summarized as follows:

$\mathrm{pk} = (c,d,h) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2},g_1^{z_1} g_2^{z_2}) \in \mathbb{G}^3$
$\mathrm{sk} = (x_1,x_2,y_1,y_2,z_1,z_2) \in \mathbb{Z}_q^6$
$\mathrm{ct} = (u_1, u_2, e, v)$,
where $u_1 = g_1^r$, $u_2 = g_2^r$, $K = h^r$,
$e = E_K(m)$, $\alpha = H(u_1,u_2,e) \in \mathbb{Z}_q$,
and $v = c^r d^{r\alpha}$.

I omit the decryption algorithm. The scheme is IND-CCA2 secure if the DDH assumption holds and the SKE scheme ($E_K$) is one-time secure.

Kurosawa and Desmedt (CRYPTO 2004)

Kurosawa and Desmedt proposed a new PKE scheme with more compact secret key, as you wanted.
The scheme is summarized as follows:

$\mathrm{pk} = (c,d) = (g_1^{x_1} g_2^{x_2}, g_1^{y_1} g_2^{y_2}) \in \mathbb{G}^2$
$\mathrm{sk} = (x_1,x_2,y_1,y_2) \in \mathbb{Z}_q^4$
$\mathrm{CT} = (u_1, u_2, e, t)$,
where $u_1 = g_1^r$, $u_2 = g_2^r$, $\alpha = H(u_1, u_2) \in \mathbb{Z}_q$,
$v = c^r d^{r\alpha}$, $(k, K) = KDF(v)$, $e = E_K(m)$, and $t = MAC_k(e)$.

The scheme is IND-CCA2 secure if the DDH assumption holds, the SKE scheme ($E_K$) is one-time secure, and the MAC scheme ($MAC_k$) is secure.
In this scheme, $v$ is used to extract keys for SKE and MAC,
 while in the CS scheme, $v$ is used to serve integrity of $u_1,u_2,e$.
By this change, they successfully removed $h$ from the public key and $z_1,z_2$ from the secret key.

Others

There are tons of PKE/KEM schemes improving the Cramer--Shoup PKE/KEM scheme;
efficient ones based on slightly stronger assumptions, say, GDH, HDH, and GHDH assumptions, and less efficient ones based on weaker assumption. Some researchers try to make schemes compact by employing the random oracles. You can find them by search engines, say, Google Scholar.


elliptic curve infinity point implementation returns exception

So to understand why the code doesn't work, we need a bit of background on IEEE 754 floating point representation of which BigDecimal is essentially an arbitrary precision extension. Most notably it defines special values to indicate a computation yielded "infinity" (which is the Double.POSITIVE_INFINITY you are using) and for computations that yielded an invalid result (such as log(0) or 1/0), this is called "NotANumber" (NaN). So what BigDecimal does, is that it is essentially a double with higher precision, but using similar values for these special cases.

Now BigInteger on the other hand, is an extension of the usual int to arbitrary precision, taking up as many bits as needed to represent the number at hand. As it is an extension of int, this also means that it doesn't support special values such as "infinity" or "NaN", but rather only actually representable integers.

When you do new BigDecimal(Double.POSITIVE_INFINITY).toBigInteger(), you create a new BigDecimal with the special "infinity" value / flag and try to convert this to an "ordinary" integer. But as you can't represent infinity with an integer, as this would need an infinite amount of storage, an exception is thrown instead.

Now, how can you fix this? Well, this is actually a non-trivial question and depends on what you want to do with the points. If you want to do elliptic curve cryptography using affine coordinates (which is terribly inefficient), then the usual approach is to give your Point a flag which essentially indicates "infinity" and test for the flag when you implement doubling and addition. When you use a more modern curve which has a complete addition law (that is it works for all points), then there are specific, concrete coordinates defined for the point at infinity. Of course the best solution would be to use projective coordinates, which can represent the point at infinity perfectly easy using a Z coordinate of 0.


In fact both assumptions you state are often implicitly made in the literature (I am, however, not aware of any explicit use of the latter). For instance various variants of the bilinear Diffie-Hellman problem in Type-3 groups imply the hardness of the assumptions you state, e.g., $\sf BDH\text{-}3$ [1; Definition 2] which we will recall below.

For the following explanations, let $\sf BGGen$ be an algorithm which, on input of a security parameter $\kappa$, outputs a bilinear group description ${\sf BG} := (\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, p, P, \hat P, e)$. Here $\mathbb{G}_1$, $\mathbb{G}_2$, and $\mathbb{G}_T$ are three groups of common prime order $p$, where $p$ is of bitlength $\kappa$. $P$ and $\hat P$ are generators of $\mathbb{G}_1$ and $\mathbb{G}_2$, respectively, and $e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ is a bilinear pairing. Finally, we let ${\bf g} := e(P, \hat P)$. The $\sf BDH\text{-}3$ assumption states that for every PPT adversary $\mathcal{A}$ there exists a negligible function $\varepsilon(\cdot)$ so that it holds that
$$
\Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b,c \stackrel{R}{\gets} \mathbb{Z}_p,~ {\bf g}^{abc} \gets {\cal A}({\sf BG}, aP,bP,cP,b\hat P, c\hat P) \right] \leq \varepsilon(\kappa).
$$

Now, it is not hard to show that any solver for one of the assumptions you stated implies a solver for $\sf BDH\text{-}3$. We will present an explicit reduction ${\cal R}$ for the second assumption (the reduction to the first one is left as an exercise). Before we do so we restate the assumption in our notation (wich we henceforth call ${\sf A}_1$).

Assumption ${\sf A}_1$ states that for every PPT adversary $\cal A$ there exists a negligible function $\varepsilon(\cdot)$ such that
$$
\Pr\left[{\sf BG} \gets {\sf BGGen}(1^\kappa),~ a,b \stackrel{R}{\gets} \mathbb{Z}_p,~ ab\hat P \gets {\cal A}({\sf BG}, aP, a \hat P, b \hat P)\right] \leq \varepsilon(\kappa).
$$
It is easy to verify that ${\sf A}_1$ indeed resembles the second assumption from the question (let $\hat P := Q$ and $H := bQ$).

Reduction ${\cal R}$ is implemented as follows:

Firstly, it obtains a $\sf BDH\text{-}3$ instance $({\sf BG}, aP,bP,cP,b\hat P, c\hat P)$ from a $\sf BDH\text{-}3$ challenger.
Secondly, it starts the adversary against ${\sf A}_1$ on $({\sf BG}, bP, b\hat P, c\hat P)$ to obtain $bc \hat P$.
Finally, it outputs $e(aP, bc\hat P) = e(P, \hat P)^{abc}$ as a $\sf BDH\text{-}3$ solution.

To sum up, the existence of $\cal R$ and the assumed hardness of $\sf BDH\text{-}3$ contradict the existence of an efficient adversary against ${\sf A}_1$.

Sidenote 1: The assumptions you state are quite natural assumptions in the Type-3 bilinear group setting.

Sidenote 2: The plausibility of the assumptions can also easily be confirmed in the Uber assumption framework [2].

References:

[1] https://eprint.iacr.org/2009/480.pdf

[2] Xavier Boyen: The Uber-Assumption Family. Pairing 2008: 39-56


Is it hypocritical to use AES-256 and RSA 2048 in the same application?

Using AES-256 instead of, say, AES-128 is not merely ‘future-proofing’: AES-128 provides a security level far below the standard of 128 bits today.  If your application has four billion users, the expected cost of breaking one of them by the best generic brute-force attack is about $2^{96}$ evaluations of AES-128, which can be parallelized.  This might not break your toy application, but it is well within the realm of human feasibility.  Not so for AES-192 and AES-256: even up to a whopping sixteen quintillion users, the expected cost of the same attack on AES-192 is an unimaginable $2^{128}$ evaluations of AES-192.

So if you want AES—which invites timing side channel attacks on software implementations, unlike, say, ChaCha—then you should pick AES-192 or AES-256 without further thought.  This saves you the effort of thinking about whether AES-128 provides adequate security for your application.  AES-192 and AES-256 are marginally costlier than AES-128, so if you have an overwhelming performance concern then we can discuss the finer details when you present a budget measured in joules or nanoseconds or cycles per unit of processing in your application, and not until then.

The story is more complicated for RSA, and depends on what you're doing with it:

If you're using it for signatures, you will presumably have some way to rotate signatures—unlike confidentiality, authentication generally need not last for decades.
The number of RSA keys is likely to be considerably smaller than the number of AES keys, if for no other reason than that generating an AES key costs a few dozen CPU cycles while generating an RSA key involves a search through complicated primality tests.
RSA computations are substantially costlier than AES computations at any reasonable key size, so your budget for time might actually be measured in milliseconds rather than nanoseconds, like human response times.
RSA key sizes are substantially larger than AES key sizes, so your budget for time might actually be measured in kilobytes rather than bytes.

All these considerations might figure into your application: it would not be hypocritical to pick AES-256 and then spend your time worrying about RSA, if RSA-4096 is too costly.  Heuristically, we might infer that RSA-2048 is safe for the time being because the current factorization record is RSA-768, and while we're overdue for an RSA-1024 factorization, there's a big gap from there to RSA-2048.  But it is also true that a 2048-bit RSA modulus certainly doesn't attain a 128-bit security level either.  The best cost estimate I'm aware of gives an area-time cost per key of about $2^{103}$ if we conservatively read $o(1)$ as zero, rather than the cost $2^{112}$ advertised by keylength.com, NIST, etc.

That said: Can I interest you in Ed25519 or X25519, which confidently provide a 128-bit security level—meaning the best attack has expected cost $2^{128}$ curve additions no matter how many users there are—with 32-byte keys and 64-byte signatures, and at much lower cost to generating a key or making a signature or decrypting a message than RSA will ever attain?  Then, unless your bottleneck is verifying signatures or encrypting messages, you don't have to spend time thinking about whether RSA-2048 is secure enough as you use it in your application.  (See also this earlier answer to a similar question about AES-128 and X25519.)


Hypothetical unknown cipher - security in obscurity?

An unknown block-cipher with an $n$-bit block length can just be viewed as an arbitrary permutation of size $2^n$. Assuming you have the means to verify a correct decryption, you can just try each of every $2^n!$ possible permutations.

Naturally, if your ciphertext consists of fewer than $2^n$ distinct block values then you can omit permutations which result in previously-tried plaintexts.

An extreme example of this would be a ciphertext consisting of one block of $n$ bits which would need only a maximum of $2^n-1$ decryptions to be tested. This is of course significantly less than $2^n!$


Is XOR adequate for encrypting truly random data?

By two-time pad I assume you mean using a one time pad key to encrypt two messages. Lets say $K$ is the key and $m_1, m_2$ are your messages. Then from the ciphertexts $c_1 = m_1 \oplus K$ and $c_2 = m_2 \oplus K$ an adversary could trivially learn information such as $x = c_1 \oplus c_2 = m_1 \oplus m_2$. Whether or not this information is "exploitable" may be application specific (in general it is very hard to say what "exploitable" should mean). However, the fact is that you are leaking information on your secret messages and you should be very careful.

Take the following example of how this could go very wrong: Say I want to send two random 128 bit strings $m_1$ and $m_2$ to a friend who should then use $x = m_1 \oplus m_2$ as an AES key. If I send $m_1$ and $m_2$ using regular OTP then there is no problem. Using the two-time pad, as described above, the AES key is revealed.


For the first part of your question: Yes, if Mallory manages to publish his own public key under Alice's name, then there is really nothing to stop him.
This problem is addressed with public key infrastuctures and public key certificates.

That is, for Bob to believe that the public key is Alice's key, Mallory would need to have a trusted third party attest, that that's the case. As the third party is assumed to be trusted, she obviously wont attest to that false statement.

Once we've got that problem out of the way, then no, as long as you use a secure signature scheme, it is not possible for Mallory to forge a signature on any message not already signed by Alice herself.

The usual security requirement for a signature scheme is existential unforgeability under chosen message attacks.
That means, Mallory can ask Alice to sign any number of messages of his choosing and he still wont be able to produce a single message signature pair, where the message has not already been signed by Alice herself.

What Mallory would need is an even stronger forgery, namely a selective forgery, because he chose the message to forge a signature for, before he even started the attack.


Most secure but feasible encryption running on WWII technology

It depends on what you mean by widespread (military) use.  The Russian VIC cipher, which used a lagged Fibonacci generator, classified as a "straddling bipartite monoalphabetic substitution superenciphered by modified double transposition," as identified by the FBI in 1953, could have been applied to widespread military intelligence use, especially for HUMINT. After all, it was not broken until 1957--with the aid of a defector. It was used in World War II, and it clearly worked.

But for moving armies that use radio communications, a one-time-pad system that actually worked in practice would have been an excellent idea.  The German one-time pad GEE system was considered unbreakable, and had been in use for quite a while prior to its initial interception in 1934--used for diplomatic traffic from 1925--and continued to be heavily used in 1943, according to this declassified NSA document, but it suffered from weak key generation, according to this declassified NSA technical report. Its additive generator of wheels and switches had weaknesses which were brilliantly exploited by American analysts: the phases, cycles, potential overlaps, and limits of the keys became clear after exhaustive analysis of captured GEE one-time pads. So, the GEE system with a good TRNG, responsible cryptographic clerks, and cautious leaders, would have done the trick.

The other solution would have been to fix the weaknesses in Enigma, especially in its rotors and settings, modernize it-- see this paper by Ross Anderson-- and to improve the training of its operators, change key settings frequently, reduce predictable formatting, and not regard Enigma as an unbreakable magic box.  Weaknesses in how the settings were shared over the radio were pivotal to Enigma's downfall. Or we could continue with the Rasterschlüssel 44 (RS44), a grid-based, broken double transposition that was better, in practice, than Enigma. Even so, we could tweak the RS44 and make some improvements.

Implementation is very important, as your question suggests. Procedures such as message formatting need to be emphasized.  Again, weaknesses in the training of cryptographic clerks helped speed the exploitation and downfall of both GEE and Enigma--as did overconfidence, even hubris, among the leadership.

Perhaps even more important was a failure to understand some of the underlying principles of information security, the work that would soon be done by Claude Shannon.

One could implement everything according to the principles of information theory that we now know.

Edit:  We should also include the Schlüsselgerät 41 (SG41), which was a rotor cipher machine similar to the Enigma--but better.  It had six rotors that could move irregularly--forwards and backwards--and it was intended to replace the Enigma.

Traffic from the SG41 was almost never broken by Bletchley Park.  But due to its weight (about 30 lbs; see one here) from a lack of light metal building materials, relatively few were made and then put into service (about 1500 were created in total).  From the viewpoint of the frontline soldier, heavy is bad.

Both the Germans (SG41) and the Allies (SIGABA) had rotor-based encryption that worked well when used properly.  Some of that equipment could have been improved for service--it was definitely good enough for the time.


What is perfect collision-resistence in probability terms?

For any fixed data set, you can spend computation up front on the data set to construct a perfect hash $h_{\mathcal D}\colon \mathcal D \to \{0,1,2,\dots,|\mathcal D| - 1\}$ which has no collisions, implemented by software such as gperf.
In cryptography, we are seldom worried about random data—we can control keys and choose them randomly and keep them secret, but we usually assume that the adversary has arbitrary control over the data and can choose the most evil, awful, worst-case data imaginable.  So there's not much in cryptography to help you with finding a cheaply computed fixed hash function $h$ such that $\Pr[h(d_1) = h(d_2)]$ is bounded for some distribution on $d_1$ and $d_2$.  There's arbitrarily much heuristic empirical literature on the subject of finding ‘good’ hash functions on particular distributions like English text, like Bob Jenkins' compendium, but that's largely outside the domain of cryptography.
A ‘cryptographic hash function’ like SHA3-256 can be treated as if it were a uniform random function that everybody can evaluate.  That may sound like exactly what the doctor ordered for a hash table, and you can use it as a hash for a hash table, and in applications like a distributed hash table or content-addressed storage system open to anyone in the world it may even be essentially the only reasonable kind of choice—but if you take only (say) the low 12 bits as the index into your bucket array or open-addressing array, an adversary can work offline to find lots of 12-bit collisions quite cheaply even if they don't have any shortcuts beyond evaluating SHA3-256.  These functions are also not very fast, because there seems to be a high cost to pay for preventing any shortcuts to finding collisions in the whole function, as we discovered the hard way with MD5 and SHA-1.
How can you set a bound on collisions in a secret hash function, e.g. in an application server that has a private in-memory cache, where the hash function need not be shared with the general public?
If you allow $h$ to vary randomly, then for any fixed $d_1 \ne d_2$, you can have $\Pr[h(d_1) = h(d_2)] \leq 1/2^n$; in this case we call $h$ a universal hash family, or an $\varepsilon$-almost universal hash family if $\Pr[h(d_1) = h(d_2)] \leq \varepsilon$, and there are various standard efficiently computed examples (paywall-free: (a), (b)).  A typical example in cryptography, for message authentication, is to choose two elements $r, s$ at random from a field of about $2^{128}$ elements, e.g. $\operatorname{GF(2^{128})}$ in GHASH or $\mathbb Z/(2^{130} - 5)\mathbb Z$ in Poly1305; interpret 128-bit chunks of a message $m$ as coefficients a polynomial in the field; and compute $h(m) = m(r) + s$.
You might consider using a universal hash family for a hash table.  For a non-adaptive adversary who sends you all input before you operate on it, a universal hash family is a good way to cheaply compute hashes with low probability of collisions.  But if the adversary can adaptively submit inputs based on the timing of your past operations, they may be able to discern whether a collision happened and exploit it to make more collisions in a denial of service attack.  In applications with an adaptive adversary, you really want a pseudorandom function family like SipHash.  More details on universal hash families vs. pseudorandom function families.
Further reading on collision-related metrics in cryptography.


Explanation of $z^{-1}$ and $T_{1,2}$ within E0 Bluetooth encryption algorithm

This article  Cryptanalysis of the Bluetooth Stream Cipher by Canniere et al. explains in details;

\begin{align}
T_1 : \mathbb Z^2_2 &\mapsto \mathbb Z^2_2\\
(x_1, x_0) &\to (x_1, x_0)\\
\end{align}

\begin{align}
T_2 : \mathbb  Z^2_2 &\mapsto \mathbb  Z^2_2\\
(x_1, x_0) &\to (x_1, x_1 \oplus x_0)\\
\end{align}

$Z^{-1}$ are 2-bit digital delay lines. $Z^{-1}$ is delay one sample and $Z^{-N}$ is delay by $N$ sample. This can be implemented by circular buffer in electronics and with arrays in software.

Why $T_1$ and $T_2$ are bijections? $T_1$ is bijection since it is just swapping the values. To prove that $T_2$ is a bijection; first, notice that it is surjective. To see it is an injective notice that we can find the inverse of every element on the range.

Extra:

To understand $\mathbb Z_2^2$ we need to construct it: We can also represent $\mathbb Z_2^2 $ as $\operatorname{GF}(2^2)$. It is the second-degree extension of $\operatorname{GF}(2)$ by the roots of the polynomial $x^2 + x + 1$. Let $\alpha$ is one root then the second root is $\beta  = 1 + \alpha$.

By using $1 + 1 = 0$ and $\alpha^2 = \alpha + 1$ we can build the addition and multiplication tables.

Addition:
$$
\begin{array}{c|cccc}
+  & 0&   1&   \alpha &  \beta  \\
\hline
    0&   0 &  1 &  \alpha &  \beta \\
1 &  1 &  0 &  \beta &  \alpha  \\
\alpha &  \alpha &  \beta &  0 &  1  \\
\beta &  \beta &  \alpha &  1 &  0  \end{array}
$$

Multiplication:
$$\begin{array}{c|cccc}
\cdot &   0 &  1 &  \alpha &  \beta  \\
\hline
0 &  0 &  0 &  0 &  0  \\
1 &  0 &  1 &  \alpha &  \beta  \\
\alpha &  0 &  \alpha &  \beta &  1  \\
\beta &  0 &  \beta &  1 &  \alpha
  \end{array}$$


Is symmetric encryption vulnerable to plain-text-attacks?

If the encryption is any good, no.  What you're describing is a known-plaintext (or possibly chosen-plaintext) key recovery attack, and any encryption system that was even suspected of being vulnerable to such attacks would be considered hopelessly broken by modern standards.

The "gold standard" that modern encryption methods aim for is generally taken to be "IND-CCA2" security, or ciphertext indistinguishability under an adaptive chosen-ciphertext attack.  Loosely speaking, this security property means that an attacker who gets to choose two plaintexts (of equal length) to be encrypted and sent back to them, and may also request the encryption or decryption of any number of other messages, will not be able to tell which ciphertext corresponds to which plaintext.


Choice of finite fields for use in elliptic curves

First, the size: the best attacks for breaking elliptic curve cryptography are algorithms that break the discrete log (given a point $P = kG$, find the integer $k$; which in ECC translates to: given the public key, find the private key).
These attacks have complexity of $O(2^{n/2})$, where $n$ is the size of the field. So, in a 256-bit field (i.e. with a 256-bit $p$), the best attacks can break the algorithm with $2^{128}$ steps, which is similar to what is needed to break a single instance of a 128-bit key symmetric algorithm by brute force. This is usually called "128-bit level of security". In short: the field size must be the double of the desired security level. (I've omitted some details about cofactors, but they don't change the picture that much for commonly used curves)

Now, the particular primes chosen: the computationally expensive part of ECC is field multiplication, which is composed of integer multiplication followed by reduction modulo $p$. Depending on the structure of $p$ this reduction can be computed faster. One example are primes having the form $2^k-c$ for small $c$ (Crandall primes), which is the case of secp256k1 and curve25519. The best case is a Mersenne prime, $2^k-1$, which is used by the NIST curve P-521 ($2^{521}-1$). Other common case is when the prime is composed of powers of multiples of a word size, such as P-256 ($2^{256}-2^{224}+2^{192}+2^{96}-1$), which are all multiple of 32. The reason why these lead to a faster implementation would probably required another question on the site, though; but for example, when $p = 2^k-1$, then $2^k \equiv 1 \pmod p$. If you write the result of the integer multiplication as $H + 2^kL$, then the reduction modulo $p$ will be simply $H + L \bmod p$.


Can we say that if $P=NP$ there is no CPA secure public key encryption?

There is no direct inference from $P = NP$ or $P \neq NP$ to security or insecurity of any particular encryption algorithm. As far as practical consequences are concerned, the "$P = NP$" problem is severely overhyped.

If $P = NP$ then any problem for which a solution can be verified in polynomial time can also be solved in polynomial time. "Polynomial time" does not automatically mean fast, for two reasons:

Complexity classes like $P$ and $NP$ are about asymptotic behaviour: they give us values for sufficiently large instances of the problem. Nothing tells us that a specific instance is large enough for the asymptotic behaviour to be an accurate description of the computational cost of solving that instance. For instance, asymptotically speaking, GNFS is a faster integer factorization algorithm than Quadratic Sieve; but, in practice, QS is faster than GNFS for integers of less than 300 bits. Proving $P = NP$ would imply that there exists a polynomial algorithm to solve integer factorization (or discrete logarithm), but it would not follow that this algorithm is indeed efficient for a 1024-bit integer.
"Polynomial" means "with cost proportional to $n^x$ for a problem of size $n$ and some constant integer $x$". Nothing guarantees that $x$ is small. A $O(n^{20})$ algorithm is completely polynomial, and completely out of reach of our technology for a size $n \geq 32$ bits...


Help me describe/identify this challenge-response protocol/algorithm?

The intend appears to be that vector is secret and the main key; and version (that, we are told, is secret) is an extension of that key (or variant selector).

1) I could say that ResetCode is a MAC of quote with key vector and version.

2) Never met this particular one. Anyone with common sense should laugh at it as snake oil if it pretends to be military-grade cryptography.

3a) When seen as a MAC, an obvious algorithmic flaw is that adding 1 (mod 256) to version and subtracting 11111 from any quote which has each of its digits non-zero leaves the ResetCode unchanged; this can be classified as a related-key weakness. That observation can make a usable paper tabulation of the function over twice less bulky (only entries with quote including a 0 need to be tabulated). Adding 10 (mod 256) to version also has special properties.

3a') Update: there's much worse! For constant version and vector, changing a particular digit in quote into another digit causes a difference (mod 10) in any particular digit of ResetCode that is independent of the 4 other digits of quote. With this observation, from the ResetCode for a small set of quote values, we can compute the ResetCode for any quote value, without knowing vector or version. The set of 46 quote values having at most one non-zero digit is convenient for hand calculation, but even random quote from a significantly smaller set often allows trivial linear algebra to pull that trick. In fact that MAC is so linear and with poor mixing that it could be broken from examples alone, without knowledge of the algorithm or reverse engineering the code or extracting vector!

3b) In the usage context, after vector has become public (e.g. if it is common to all alarms of the type), most often a single intercept of (ResetCode, quote) is enough to find version, leading to total break. Even a theoretically perfect cryptographic MAC is expected to have this property, given the ridiculously small size of what remains of the key (version), and the larger size of ResetCode. Any theoretical weaknesses of the algorithm seen as a MAC is moot compared to this system weakness of a small version when an adversary can obtain all key material beside version, or has access to a black box computing ResetCode for any chosen input (quote, version).


Determining the primitive root $g$ of $p$, given $B=g^b \pmod p$

If $\gcd(b,p-1)=1$ you have  $u\cdot b + y\cdot (p-1) = 1$ where $u=b^{-1} \bmod {(p-1)}$. With Euler's theorem $B^{p-1} \equiv 1\bmod p$ you get
$$g \equiv B^u \bmod p.$$

Right you are with your comment, I have included the changes. Euler's theorem is used at the penultimate step:
This is the 'easy case' on page 4 of the reference given by SEJPM
$$g^u \equiv (B^u)^b \equiv B^{ub} \equiv B^{1-y(p-1)}
\equiv B \cdot (B^{p-1})^{-y}\equiv B \cdot 1^{-y}\equiv B \bmod p$$
Example: $p=11, b=7, B=4$.  Compute:
$$u \equiv 7^{-1} \equiv  3 \bmod {10}$$
$$g \equiv 4^3  \equiv 9 \bmod {11}$$
and check:
$$9^7 \equiv 4 \bmod 11$$


Background

When defining protocol compliant with NIST SP 800-108, you just need to pick suitable options, which work well with your protocol.

If there is a need to be compatible with a specific pre-existing protocol, you may want to take a look at NIST SP 800-135Rev1, which defines application specific key derivation functions. It is notable to recognize that some of the NIST SP 800-135Rev1 key derivation functions are valid NIST SP 800-108, with specific options selected.

The best way to identify the KDF is to actually list all the applicable options from NIST SP 800-108 KBKDF. (What of three functions to use (CTR, FB, Pipeline); order of components, what is the content of label, and if the label is terminated by zero etc.) It is likely best to illustrate the protocol specification with clear examples which show the correspondence of NIST SP 800-108 functions (or alternative show invocations of underlying MAC function) as used in key derivation.

Testing NIST SP 800-108 implementation

The recommended way to test is via CAVP (Cryptographic Algorithm Validation Program). Testing takes a long time and will be performed by a CST (Certified testing Laboratory), which costs money. But you get to choose pretty specifically what to test (from reasonably large option space) and if you pass the testing, you will get a algorithm validation certificate.

For most common options, less expensive and quicker way could be to test against pre-existing unofficial test vectors from NIST/CAVP.

If the implementation needs not only to be FIPS compliant, but also is required to have US government certification (FIPS 140-2), then algorithm certificates for the applicable algorithms are needed.

If you need a set of test vectors for your KBKDF "instantiation", one way to do it is to first ensure correctness of implementation using one of the above mechanisms, and the use that "appears to be correct" implementation to generate the official test vectors, and attach the test vectors with the protocol specification.

The way to determine order, sizes of elements etc. used in the test vectors is explained in KBKDFVS (KBKDF Validation System).

The parameters KBKDFVS uses for Feedback Mode are (extracted from KBKDFVS):

Pseudo-Random Function supported by the IUT

List CMAC AES 128, 192, 256
CMAC TDES 2, 3
HMAC SHA1, SHA224, SHA256, SHA384, SHA512

L-length of the derived keying material K0 in bytes – Enter all that apply:

A minimum and maximum value for full block lengths supported
A minimum and maximum value for partial block lengths supported

Method(s) supported to generate K:

SP800-56A
SP800-56B
SP800-90A
an Approved RNG
N/A – Out of the scope of the algorithm implementation

Does the IUT support the counter being used as an input? If yes, what is the length of the binary representation of the counter i.

8 bits.
16 bits.
24 bits.
32 bits.

Does the IUT support the counter coming before and/or after the iteration variable and/or after the fixed input data?

The information for other modes (i.e.) counter and double pipeline is similar.
This information is not sufficient to encode all that can be known about the KDF function, but is already a good start.

Finally addressing your questions

Identify the KDF by specifying options from NIST SP 800-108. You should also have examples (and possibly test vectors), which allow correct implementation.
The name is of NIST SP 800-108 and the name (or section) of the mode used.
I'm also not aware of OID/ASN.1 applicable. (But maybe somebody has defined something for their implementations of NIST SP 800-108. There are no OID/ASN.1 which covers all the possible options of NIST SP 800-108.)
If you need OID or ASN.1 module for your protocol, it is likely easiest for now to define your own.
Implementations of SP 800-108 likely can be tested using CAVP or unofficial CAVP test vectors.
KBKDFVS can be good example to see how NIST specifies the parameters in context of test vectors. Maybe you can use similar approach and terminology for the protocol?

HKDF

Side Note: Depending on how you use HKDF, you are often using either NIST SP 800-108 or NIST SP 800-56C: HKDF "expand only" can be considered to be a variant of NIST SP 800-108 KBKDF. NIST SP 800-56C is basically attempt to define full HKDF in NIST terminology (and add AES-CMAC).


Is CPU timing jitter a usable entropy source?

The problem with CPU jitter is that it is difficult to pin down an accurate physical model of it that would allow you to calculate the entropy involved. Therefore entropy estimates have to largely be grounded on statistical testing, as in the document I linked in the comments.

As you may know, statistical testing alone can only ever give you an upper bound for entropy. What you need for secure random number generation is a lower bound, and that requires making more assumptions.

However, since you only need enough entropy to seed a PRNG, the answer to your question is almost certainly that it does have enough entropy. You can always collect timings for a very long time and feed it all as seed material to the RNG, and unless the jitter contains no entropy at all you will eventually have 256 bits' worth. How long is the question, with no single answer.

If you use a recent Linux kernel, you should be able to get entropy with all that figured out (or guessed...) for you, just by accessing /dev/random or /dev/urandom. In practice it is also often possible to get a small seed into the VM from outside, so you do not necessarily have to rely on the VM being able to generate entropy.


How to create the ciphertext that generates a desired plaintext in CBC (previous cipher- and plaintext are known)

CBC-R
To better understand the attack on the paper, It is better to look at the original CBC-R attack to understand the above attack.

Practical Padding Oracle Attacks, Juliano Rizzo and Thai Duong. USENIX 2010

This work shows how to turn the padding oracle into an encryption oracle. With padding oracle, we can get decryption of any ciphertext.
Choose a random ciphertext $C_i$, actually, any ciphertext will work. Request decryption with the padding oracle $$P_i = Dec(C_i) \oplus C_{i-1}.$$ By controlling the $C_{i-1}$ we can turn $P_i$ to any value we want. The the target is $P_x$ than we can set $$C_{i-1} = P_x \oplus Dec(C_i).$$
As we know this will make the decryption of $C_{i-1}$ as a garbage block ( random block). But we started with a random block, too. Similarly, as the first step, request decryption then adjust the previous block;
$$C_{i-2} = P_{i-1} \oplus D(C_{i-1})$$ Here note that we request the decryption of $C_{i-1}$ with arbitrarily chosen $C_{i-2}$ then we adjust the $C_{i-2}$ so that the decryption is $P_{x-1}$. This is easy since it is just an x-or difference.
In this way, we repeat to the beginning where the last adjusted value is the nonce of the CBC mode.
This encryption oracle is very slow since it needs a padding oracle for the decryption of a block. The attack on the FPGA ( next title) is used directly by the decryption oracle and therefore it is very fast.
The Unpatchable Silicon: A Full Break of the Bitstream Encryption of Xilinx 7-Series FPGAs
When a malicious action occurs the system halts, and the WBSTAR register is left intact, then after reboot, they read the WBSTAR register that stores what was decrypted and leaks 32-bits. Repeat to reveal all. This turns this bug into a decryption oracle on the FPGA.
HMAC key can also be decrypted using the above technique using the FPGA as a decryption oracle.
The aim is to turn the decryption oracle into an encryption oracle!

Why does it say in equation (2) say that we can generate the desired ciphertext of the previous block this way?

Actually, it is the goal and they show it in the next steps. Therefore, you need to understand the next steps.

Also shouldn't the equation (3) formula be: P′i−1=... instead of Pi−1=...

Yes it should be $P'_{i-1}$

Note that  for arbitrary selected $C_i$ and $C_{i-1}$ using the decryption oracle one can find out $P_i$.
Now you want a value $P'_i$ in the FPGA and for this, you need the encryption of it $C'_i$.
$$P_i = dec_{KAES}(C_i) \oplus C_{i-1} \label{1}\tag{1}$$
If you set
$$C'_{i-1} = P_i \oplus C_{i-1} \oplus P'_i \label{2}\tag{2}$$
Then put values into equation \ref{1}
$$P_i = dec_{KAES}(C_i) \oplus P_i \oplus C'_{i-1} \oplus P'_i$$ leaves;
$$P'_i = dec_{KAES}(C_i)  \oplus C'_{i-1}  $$
CBC has the chaining so they need to modify to the beginning.
$$P'_{i-1} = dec_{KAES}(C'_{i-1})  \oplus C_{i-2}  \label{3}\tag{3}$$

I don't really get equation (4) and why is it different to equation (2)?

This is also a typo, since
$$C'_{i-2} = P_{i-1} \oplus C'_{i-2} \oplus P'_{i-1} \label{4}\tag{4}$$ leads
$$ P_{i-1} =  P'_{i-1}$$
It should be
$$C'_{i-2} = P_{i-1} \oplus \color{red}{C_{i-2}} \oplus P'_{i-1}$$

Results of the article

This turns the decryption oracle into an encryption oracle. And using this a valid HMAC can be created, to.

So, a simple bug leads to a loss of confidentiality and integrity and authentication.


First, you should start by guessing which symbols in the ciphertext are actually enciphered, and which are simply written in plain.  (Don't worry if you guess wrong, you can always make several guesses.)  For a Vigenère cipher, one also needs to guess whether any non-encrypted characters should advance the key position or not (usually they do not).

For your example ciphertext, it seems likely that spaces, and probably also periods, commas and apostrophes are written in plain — they occur at places where they would in natural English text.  On the other hand, the letters are certainly in cipher, and so are most likely the numbers and the plus signs and slashes too, since they seem to be scattered randomly among the words.

(A curious feature to note at this point is that the lowercase letters in the ciphertext seem to occur at places where an uppercase letter would be plausible in plain English text.  This suggests that letter case may simply be trivially flipped.)

The next step I'd suggest, after initially guessing the cipher alphabet, is to compute the index of coincidence for various key lengths.  In particular, if you do that for various choices of ciphertext alphabet, you'll notice that, for the alphabet consisting of letters (ignoring case), numbers, + and /, the plot of IoC (scaled here for an assumed plaintext alphabet of 26 letters) as a function of key length looks pretty striking:

 1: 0.826  ################
 2: 0.816  ################
 3: 0.825  ################
 4: 0.781  ###############
 5: 0.867  #################
 6: 0.847  ################
 7: 1.822  ####################################
 8: 0.778  ###############
 9: 0.771  ###############
10: 0.860  #################
11: 0.816  ################
12: 0.743  ##############
13: 0.786  ###############
14: 1.812  ####################################
15: 0.791  ###############
16: 0.640  ############
17: 0.803  ################
18: 0.693  #############
19: 0.734  ##############
20: 0.671  #############
21: 1.985  #######################################
22: 0.745  ##############
23: 0.840  ################
24: 0.766  ###############
25: 0.688  #############
26: 0.672  #############
27: 0.567  ###########
28: 1.669  #################################
29: 0.786  ###############
30: 0.777  ###############

Notice the sharp peaks at multiples of 7, strongly suggesting that the key is seven characters long.  In particular, the IoC for those values is close to 1.7, which is considered a typical value for English text.

So let's see what happens if we assume that the key is seven characters long. We'll write down the ciphertext in seven-character blocks (omitting spaces and punctuation) and print out the character histogram of each column:

Column 1:                                 Column 2:
        |
        |
        |            |                     |
        |      |     |                     |                 |
|       |    | |   |||                     |             |   |     |   ||
|   | |||    | |   |||                     |             | | |   |||  |||
|   | |||    |||   |||  |                  |          |||| |||   |||  ||| || |
3   2 227    314   335  1                  5          1113 214   223  233 11 1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 3:                                 Column 4:

          |                                                     |
  |   |   |  ||                                             | | |             |
  |   |   | |||                                             | | |   |    ||   ||
  | | |   | |||  | |                                        | | |   |    ||  |||
  | ||| ||| ||| |||| |                                |     | ||| | |  ||||  |||
  4 214 115 344 1212 1                                1     4 415 1 3  1133  243
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 5:                                 Column 6:
                                     |
                                     |                |
                          |          |                |
                  |       |          |                |  |     |    |
                  |   |   |    |     |              | |  |     ||   |
                  |   | |||    |   | |       |      | |  |     ||   ||
            |     ||| |||||  ||||  | |    || |      ||| |||  | ||  |||
            1     411 31225  1131  2 7    11 2      316 141  1 43  142
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ    +/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

Column 7:
        |
    |   |
    |   |
    |   |  |
    |   |  |          |
    ||  |  | |||      |
|   ||  || | ||||| | ||           |
1   62  71 4 22211 1 13           1
+/0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ

The first remarkable feature to note is that, even though the cipher alphabet has 26 + 10 + 2 = 38 characters, none of the columns features even half that many character.  This is quite plausible, assuming that the plaintext mostly consists of letters, and keeping in mind that the English letter frequency distribution is quite skewed.

Also, the numbers seem to mostly appear in the columns whose letters are mostly from the beginning of the alphabet, suggesting that they may indeed be sorted before the letters in the cipher alphabet.  (It's not so clear where the + and / characters should belong, but we can try to figure that out later.)

Finally, looking at the letter frequencies within each column, we may note some distinctive peaks.  For example, in column 5 (which, conveniently, has only letters), the most common characters are G, K, O, T and Z.  Shift those six places back in the alphabet, and you get A, E, I, N and T — five of the most common letters in English (only O is missing from the top six).  This gives us a pretty good guess for one key value out of seven already.

Can you finish the decoding from here?

(Ps. I haven't, so my apologies if it turns out I've led you down a false trail.  But I'm pretty sure I haven't.)

Pps. I did eventually solve this puzzle, and it turns out that one of the early assumptions I made above was wrong.  However, you can still decode most of the text despite the wrong assumption, and, once you do, it's not hard to figure out what the mistake is.

Specifically, I was wrong about letter case being simply flipped.  Instead, the correct cipher alphabet has 64 characters: A–Z, a–z, 0–9, + and /, in this order.  (This is, in fact, the same alphabet as used for base64 encoding.)  It just happens that, with this particular alphabet and key, most lowercase letters are encrypted to uppercase ones, and vice versa.


Is this problem same as discrete logarithm?

This is exactly the Computational Diffie-Hellman (CDH) problem. Rename $h=g^z$ and $g'=g^y$ in what you wrote, then the problem becomes:

  Given $g$, $g^z$, and $g^y$, compute $g^{yz}$.

See this discussion to address your question about the relationship between CDH and discrete log.

edit:

  Q1: If we know $(g′)^z$ and $g^z$ then is it easier to find $z$?

No, it is just as hard as discrete log. If you are given just $g$ and $g^z$ then you can generate other pairs with the same discrete log relationship yourself, via $g' = g^r$ and $(g')^z = (g^z)^r$. So having extra such pairs doesn't add any new information.


Same format means they are numbers. So you have to try the combinations to match. In other words, you are performing an attack on limited message space. Produce combinations of numbers.

ONEONEONEONE...
ONEONEONETWO..
...
NINENINENINE

Before this applying Kasiski test to determine the key length may be helpfull to reduce the string lengths.

Good luck!


Dividing a point by a specific number in elliptic curve

Find an integer $k$ such that $65537k \equiv 1 \pmod q$; such a $k$ exists because $q$ is prime.

If $65537\cdot P = H$, then clearly $P = k\cdot H$ (keeping in mind that $q\cdot P = \mathcal{O}$ for all points $P$), and conversely $(k\cdot H)\cdot 65537 = H$.


I doubt you will find a fast implementation of Salsa20 in Java (having spent much time attempting to achieve just this).

Salsa20 mutates a 512 bit state made up of 16 x 32 bit integers, which means that implementations that don't take advantage of SIMD (on Java or otherwise) will probably not perform well - there are too many independent state parts to keep them all in general purpose registers on any common architecture, so you inevitably incur load/store overhead, which kills your throughput.

Java (Hotspot at least) does a reasonable job of optimising all the basic operations (e.g. inlining, single instruction rotate etc.) but it doesn't have the smarts to dynamically do small scale SIMD optimisations.

I've tried various approaches to get around this: simulated SIMD by packing 32 bit integers into 64 bit longs (too many additional instructions); triggering hotspot vectorisation optimisations (too much array munging overhead), and didn't find anything that worked.

By comparison: Threefish 512, despite having the same state size uses 8 x 64 bit words, so on 64 bit Java the entire state can be held in registers, and the performance is ~150% the speed of AES.

The BouncyCastle Salsa20 implementation can be pushed a bit (by registerising the state as much as possible) to get it just faster than AES, but it's still woefully slow compared to implementations on SIMD capable platforms.

XSalsa20 and ChaCha will have the same issues, as they have the same basic structure.


This is a basic length extension attack. For hash functions like SHA-1 and SHA-2 the final state of hashing $h(K \| M)$ block by block is the output. If you hash $h(K \| M \| X)$ then you simply continue hashing from the given state (i.e. the last output).

In practice though the final block must contain a valid padding and length, which is added to $K \| M$. So basically you can create a valid hash for $K \| M \| P \| LE \| X$ where $P$ is the padding and $LE$ is the length encoding. You cannot just create any message that starts with $M$.


Can prepending "junk" be equivalent to an IV when encrypting using CBC?

If you know that the integer is fixed in size (always in the range 1-1000), then the second approach is fine.  Effectively, you still have a random nonce (what you are calling the "junk"); you concatenate the nonce and the integer, then encrypt the result with AES-ECB.  This works.

Do make sure that you choose a large enough random nonce.  I recommend making it as large as possible, i.e., filling the full remaining width of the block.  For instance, if your value is always in the range 1-1000, then it will fit in 10 bits.  So dedicate 10 bits to hold the value, and use the other 118 bits for the random nonce (i.e., to encrypt, you generate a random 118-bit nonce, concatenate it with the value, and then encrypt using AES-ECB).  At a minimum, you probably want your nonce to be at least 80 bits long, and a bit longer might be a bit better.

Also, make sure that you use a cryptographic-strength PRNG to generate the random nonce.


How many bits should a token have to be unguessable (given some computational resources)?

Well whilst AES can take 256 bit keys, it still only accepts a 128 bit IV. And the width of the AES block is considered secure in 2017. So that would be a good guide.

Also, there are type 4 UUIDs that use 122 bits of uncertainty and are currently in widespread use.  There's not a lot more to say other than to extract this from my reference:-

  Thus, for there to be a one in a billion chance of duplication, 103 trillion version 4 UUIDs must be generated.

Increasing the size to 128 bits would require 8e14 tokens for the same 1 in a billion risk of collision. Should be okay.


Is braid-based cryptography proven insecure when looking towards post-quantum cryptography?

I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7).  I am not sure if this completely ends braid cryptography, however, since there are other difficult problems in braid groups that have not been studied extensively.


The original question states that we are given $e,m_1,{m_1}^e,{m_1}^d,\dots,{m_x}^e,{m_x}^d$, but not $N$; and asks for $d$ or a factorization of $N$.

I suspect some gremlin crept in this statement, because if any of the ${m_j}$ is such that ${m_j}>1$, it is trivial to obtain $d$ from ${m_j}$ and ${m_j}^d$, as $d=\log({m_j}^d)/\log(m_j)$.

So I guess we are given $e, m_1, {m_1}^e\bmod N,{m_1}^d\bmod N,\dots,{m_x},{m_x}^e\bmod N,{m_x}^d\bmod N$. If we are not given $N$, and for non-trivial choice of messages, we can find $N$ with overwhelming probability as $N=\gcd_{j=1}^x(({m_j}^e)-({m_j}^e\bmod N))$. With $N$ known, the givens ${m_1}^e\bmod N$ can be eliminated, for we can recompute them.

Thus the problems likely boils down to: given $N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N$, can we find $d$ or a factorization of $N$?

If the givens (beside $N$) allowed to efficiently factor $N$, that would solve Open Problem 1 in Dan Boneh's survey given as the question's second reference, which is nearly that problem (in addition, there is freedom to choose the $m_j$).

Thus no, we do not know how the givens (beside $N$, or the givens that let us find $N$) help in factoring $N$, but we do not know how to prove that they do not help significantly. That's an open problem!

We however can state one provable fact: if the $m_j$ are chosen at random, then knowledge of the ${m_j}^d\bmod N$ can not help. Proof sketch: any efficient algorithm factoring $N$ from $(N,e,m_1,{m_1}^d\bmod N,\dots,m_x,{m_x}^d\bmod N)$ with the $m_j$ chosen at random could be turned into an efficient algorithm that factors $N$ from $(N,e)$ alone, by choosing some $c_1,\dots,c_x$ at random and computing the $m_j={c_j}^e\bmod N$.

Some triva:

If we knew $d$, or any working private exponent $d'$, then we could factor $N$ using an efficient probabilistic algorithm.

If we knew the factorization of $N$, we could find the smallest working private exponent $d_0=e^{-1}\bmod\lambda(N)$, such that $d\equiv d_0\pmod{\lambda(n)}$. And if we further knew that $d=e^{-1}\bmod\phi(N)$ (rather than just some working private exponent), we could find $d$.


Asymmetric key derivation – Who derives the new pub key can't know the new private key?

I am afraid this answer is long overdue, but what you are asking for is actually possible. It is even easy if you use public key cryptography relying on the discrete logarithm problem to secure the private key, such as ECDSA (for signature) & ECIES (for encryption) for example. And it might probably be possible for other schemes as well, but not as easily (at least, not in a way that seems as straightforward as for the discrete logarithm).

You can go around your problem using something like the derivation of the "shared encryption key" in ECIES.

In both ECIES and ECDSA, the private key $k$ is a large integer, while the public key $P_{k}$ is a point on the elliptic curve $\mathrm{E}$ derived from $k$ by computing $P_k=k\cdot G$, for $G$ a generator of the curve with large prime order $n$ (which is generally standardized along with the curve you're using).

This means that you can actually derive another public key $k\cdot G$ just like what you are asking for by:

Alice picks a random secret integer $r$
She computes the point $R=r\cdot G$ on the curve $\mathrm{E}$
She can then compute the derived public key $P_{kr}$ by adding the public key point $P_k$ and the point $R$ together: $P_{kr}=P_k+R$

And now, the corresponding private key $k'$ is simply $k'=k+r$, because of the definition of the scalar multiplication, which make it distributive over the group law $+$, which means that $P_k+R = k\cdot G + r\cdot G = (k+r)\cdot G$.

So Alice can simply send $r$ to Bob, and Alice would still not be able to sign anything (in the ECDSA case) for this child public key $P_{kr}$.

Knowledge of $r$ merely allows to discover the "main" public key $P_k$. (So you might want to keep it secret, depending on your needs.)

If you want to adapt the scheme to something else than elliptic curves, you might, but you'll have to rely on the discrete logarithm problem to use the same trick. For instance, this specific method wouldn't work with RSA keys.

PS: I am also aware of a more intricate scheme used in certain Bitcoin wallets, but I haven't had time to study it yet and the scheme presented above is way simpler. But just in case, you might also want to check what's done in BIP32.


How to encrypt incomplete block with RSA as a block cipher?

With such a small block size there is no way to employ RSA padding modes such as PKCS#1 v1.5 padding or OAEP. You could however see the encryption as ECB mode encryption. In that case you could apply padding mechanisms that have been constructed for symmetric block ciphers.

Those padding modes however have been defined for bytes rather than characters. That's no problem - let's just assume ASCII text so we can convert the text to bytes without issue. Within many programming environments you may not even have to perform the conversion explicitly (e.g. C has char*).

OK, so after the conversion you have multiple options (values are in hexadecimals):

PKCS#5 padding: a padding where each added byte has the value of the size of the padding in bytes (i.e. 01, 0202 or 030303 in your case).
Bit-padding: just add a single 1 bit and then zero's up to the end (i.e. 80 8000 or 800000 in your case).
Zero-padding: just add zero bytes until the next boundary, i.e. $\varnothing$ (nothing), 00 or 0000. This one is probably used most for textbook RSA.

Zero padding is non-deterministic as it may strip off 00 valued bytes at the end of the plaintext after decryption. It has however the advantage that you don't have to pad when the plaintext is already correctly sized.

Furthermore, at least for ASCII (and UTF-8) you won't find any zero bytes in printable text. Zero byte value is often seen as end-of-string marker - especially in the C language. Don't forget that your string may need to end with a 00 in those kind of environments (so make your buffer one byte larger and set the rightmost byte to 00 before or after decryption).

If the zero's are not stripped off automatically by the runtime then you usually have right-trim function such as rtrim(plaintext, '\0') available to you.

After conversion you need to convert the 3 byte sequences into unsigned integer before you can feed them into your function that performs modular exponentiation with the public key. PKCS#1 defines a method on how to do that called OS2IP (and I2OSP to convert back).

Make sure that the resulting integer is always smaller than the modulus (ASCII is 7 bit, so a 24 bit modulus should be sufficient).


I can see some weaknesses in your protocol. For example, it allows any attacker to request the encrypted private key and thus mount an offline dictionary or brute force attack on the password. (An incorrect password doesn't give you a properly formatted OpenSSH key.)

Thus this is a good idea:

  I'd rather use something proven.

As mentioned in the comments SRP does exactly what you want. Here is description of the version 6(a) protocol.

To protect against compromised servers (like normal with password authentication), you'll want to incorporate your idea of using PBKDF2 (or another password hashing function). If you don't want the server to have to compute a slow password hash on each login attempt, you can use a normal hash as $H$ except when deriving $x$, which only the client needs to do. Or if you use an SRP library (as you should if possible) and it doesn't support this, you could calculate the $p$ you feed into SRP using PBKDF2 from the actual password.


Use of nonces in Kerberos and Needham–Schroeder protocols

For Needham-Schroeder, $N_A$ is used to prevent a replay attack. Look at the message from $S\to A$. Without a nonce, a malicious server could replay an old but valid response. The message would still decrypt, etc. Furthermore, the key $K_{AB}$ would be the same as a previously used key which could open up the system to more attacks.

It is the same for Kerberos.

You are correct with $N_B$. The only way Alice could return $N_B-1$ is if she knows $K_{AB}$. Thus it is to prove knowledge of the key.

The nonce $N_B'$ in Needham-Schroeder is used to prevent a replay attack with someone spoofing Alice to Bob.

  How does the use of the nonces provide more security to the protocol?

It ties messages to specific sessions of the protocol. This ensures that all messages are "fresh" which prevents replay attacks.


Multiple users getting access to same (secret) encryption key on a single computer?

It is a no-no to use SHA-512 alone as entropy-stretching key derivation function protecting a password: that would leave dangerously vulnerable to brute force password search, even if salt is mixed. Other than that, the principle outlined in the question is sound, though slightly more complex than needed; also, I'd replace PBKDF2 by a better substitute like bcrypt, scrypt, or Argon2.

Sharing the main database key among many users each having a login/password can be achieved with a single level of a PDKDF2 (or better) rather than two, and nothing more complex than comparison and XOR (the later being used as the currently unspecified encryption method for the main database key).

Recall that an entropy-stretching key derivation function like PBKDF2 produces a bytestring of desired size, from

key (the password)
salt (typically at least concatenation of an application-specific constant and user id)
desired output size (not available for stock bcrypt, see note)
difficulty parameter(s), including at least an iteration count (set as high as tolerable), and for modern entropy-stretching key derivation functions (scrypt and later) maximum CPU count, and size of memory to use.

We can make the output size parameter say 48 bytes: 16 bytes for password verification purpose, and 32 bytes for the main database key. What's stored in the password database for each user includes its user id (the search entry, as plaintext), and the 48-byte output of the password entropy stretching key derivation function, with the 32-byte portion combined using XOR with the 32-byte database key. The user's record can additionally contain security parameters currently used for the entry, extra random salt, and other details like when the password was last changed.

On login we fetch the (alleged) user's record from the login/password database, compute the entropy-stretching key derivation function with the given password, and combine the result with the above 48-byte user record using XOR. We allow login only if the 16-byte subfield is all-zero, and then only use the rest as the database key, without need for further verification.

Finding the database key is as hard as finding any user's password (the stated security goal). Changing a user's password only involves changing the corresponding entry in the login/password database.

This leaves unspecified the cryptography used to protect the database by way of its key; that one is a complex issue.

Note per comment: bcrypt has fixed output size 24 bytes. It would be tolerable to halve the fields used for password check and data base key; or we could change bcrypt's OrpheanBeholderScryDoubt string constant to something twice as long, taking care that no 8 byte segment repeats (but then that's no longer bcrypt).


Why do public keys for RSASSA-PKCS1-v1_5 follow a normal distribution?

It's not perfectly clear what your graph is actually displaying.

However, if you expect that $k$-bit RSA keys are equidistributed between $2^{k-1}$ and $2^k$, well, that's not likely (unless the key generator goes out of its way to try to ensure that).

Remember, an RSA key is (usually) produced by independently selecting two primes from a range of $[c2^{k/2}, 2^{k/2}]$ (where common values of $c$ are $0.75$ and $\sqrt{1/2} \approx 0.7071$; it varies between implementations; I don't know what Chrome uses).

Each prime might be approximately equidistributed, but the product of two such primes will be somewhat closer to a normal distribution, with intermediate values being of higher probability; however note that it won't really be that close to normal.


Are there any classical proven secure cryptographic algorithms other than OTP?

A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time.
Is my understanding of provable security correct?

It doesn't appear to be accurate. It appears to be mixing up "provably secure" and "information-theoretically secure".
You can have a system that is provably secure as some problem X, and it could easily be the case that X is easily solved. "Provably secure as X" does not mean "it's unbreakable". It's a relation, not an absolute statement.

And if so, are there any other classical algorithms that are provable secure?

So this question should probably read:

are there any other classical algorithms that are information-theoretically secure?

The standard goals of information security are confidentiality, integrity, and availability.
One Time Pads are for the goal of confidentiality.
One Time Macs are the analogous algorithm that provide information-theoretically secure integrity.
I don't believe there is any such algorithm for availability. It's not clear what information-theoretically secure would even mean in such a context.
For the One Time Pad, I think there is a proof that any encryption algorithm that is information-theoretically secure is equivalent to a One Time Pad, but I can't think of a paper/answer to point to off hand. I think the proof I am thinking of is that any information-theoretically secure encryption algorithm requires a key that is at least as large as the plaintext.


Yes, the best attack still seems to be on 7 rounds. Namely, "Improved Key Recovery Attacks on Reduced-Round Salsa20 and ChaCha" shows a $2^{246.5}$ time attack on the 7-round variant.

So even the 12-round variant has a decent security margin – better than AES-256 had when standardized, much less currently.


Quantum vs. regular computing time to break ECC?

It's hard to answer given that there is no quantum computer to perform benchmark on. However, let us assume a quantum computer which would perform quantum operations as efficiently as our current standard computer can perform classical operations (this might be a bit unrealistic but it's hard to come out with realistic assumptions regarding quantum computing given the state of advancement of this research field). The complexity of Shor's algorithm being $O(\log^2 n \log \log n \log \log \log n)$ according to Wikipedia, one can observe that this is better than the complexity of the best known classical algorithms for performing the multiplication of two $\log n \times \log n$ matrices. A quick search over some papers such as this one indicates that an optimized implementation of matrix multiplication of size $1024\times 1024$ can take less than a second, hence it does not seem unreasonable to assume that if a quantum computer was executing an optimized implementation of Shor's algorithm, factorization of a 2048 bit integer would take very little time - say, less than a few minuts.

For a regular computer performing a discrete logarithm over an elliptic curve is not done with brute force as you suggest, but using the Rho-Pollard algorithm, whose complexity is $O(\sqrt{p})$, where $p$ is the order of the curve. Still, executing this algorithm on well-chosen curves of size higher than $256$ bits is completely impractical.


Can I find two specific words with the same md5 hash?

What you want is called a chosen prefix collision. Given p1, p2 you want to find m1, m2 such that hash(p1 || m1) = hash(p2 || m2).

Generic attack

The generic attack to find this, is creating messages starting with p1 and just as many starting with p2. Thanks to the birthday problem you'll find a match after around 2n/2 messages.

For a 128 bit hash like MD5, this means you need about 264 operations. This is feasible in principle, but exceeds your budget. I guess it costs 200'000\$ if you use GPUs and 5'000\$ if you already have developed appropriate ASICs.

Exploiting MD5's weaknesses

MD5 is a broken hash function. Finding normal collisions is very cheap, but that doesn't help you. Luckily(for you) there is also a chosen prefix attack against MD5.

According to a paper from 2009 this costs around 251 compressions. Which corresponds to to about 18 GPU days on a GPU that cost 200\$ in 2009.

So I estimate that the attack costs 10-20\$.

There are two caveats:

The random characters are no printable ASCII characters, but rather random bytes.

It might be possible to modify the scheme to only emit printable ASCII, but I didn't investigate that.
There will be more random characters than your example has, probably somewhere between 70 and 130.


Using xor encryption in the following use case

It sounds like you're looking to implement something very similar to what was asked about here, with the addition of a signature of the ephemeral public key.  But as poncho's answer points out, the potential malleability of the XORed key and the ciphertext could potentially pose some problems.  The way the shared secret is derived may also introduce the possibility for issues here, though following the ECIES method with a KDF should help.
For the sake of differentiating this question from Maarten Bodewes's question, I'll assume you're more interested in replacing your existing scheme than implementing exactly what you've described.  One potential option to consider to using standard ECIES (using an ephemeral key and KDF to generate a new symmetric key) to encrypt the symmetric key of your original data.  This would certainly have both some computational and size overhead, but should achieve your goal.
Here you could still sign the ECIES output (or probably just the ephemeral public key) if that authentication is important to your system.  But if you can afford the overhead that might be a safer/less experimental approach.


When does the SIS (Short Integer Solution) Lattice-problem start becoming easy (According to the parameters size)?

The problem becomes easy (as in `solvable in polynomial time') if $$\beta \geq \min_{k=1 \dots m} C^k \cdot q^{n/k}$$ for some constant $C$. This follows from:

volume $q^{n}$ for the $q$-ary kernel lattice
a Hermite approximation factor of $C^k$ for lattice reduction algorithms (LLL/BKZ) over a lattice of dimension $k$
noting that one can `ignore columns' to work with a lattice of dimension $k \leq m$

Some more details in Section 3 of

https://homepages.cwi.nl/~dadush/teaching/lattices-2018/notes/lecture-9.pdf

(where $C=\gamma_2$ because we just consider what is provable with LLL, but all other smaller fixed constants $C>1$ are also reachable in polynomial time)


Supersingular isogeny Diffie–Hellman key exchange (SIDH) Library Support AES-256?

Neither implementation actually incorporates or uses AES of any keysize, rather the primes used provide a security about 1/6 of their bit size, resulting in a security level of 83 bits for SIDH/SIKEp503 and 125 bits for SIDH/SIKEp751 against quantum attacks, and 126 bits and 188 bits against classical attacks, respectively.

Because of this, you are not limited to the recommended cipher bit size, or even to AES. You can use any secure block cipher with an appropriate security level and mode.

Since AES provides a post-quantum security of half its key size, AES-256 is actually better matched to SIDH/SIKEp751. Against classical attacks, this results in 188 bits of security, and against quantum attacks, 125 bits.


Why does decryption fail after modification of the ciphertext for RSA with OAEP padding

Let's look at the decryption part of RFC 8017 for OAEP. Let's only look at step 3, as step 1 is called length checking, and step 2 is the step to perform modular exponentiation and integer to octet string conversion (or, rather interpretation). Step 1 can fail but is out of scope for this as it acts on the ciphertext itself, step 2 cannot fail, even though the result may not make sense.

So here is step 3. Note that EM is the message after modular exponentiation with the private exponent, i.e. the input that should be generated after step 3 in the encryption phase.

3.  EME-OAEP decoding:

    a.  If the label L is not provided, let L be the empty string.
        Let lHash = Hash(L), an octet string of length hLen (see
        the note in Section 7.1.1).

Label L is a configuration option and therefore doesn't have to do with error checking. So we can know lHash regardless of any calculations performed during decryption.

    b.  Separate the encoded message EM into a single octet Y, an
        octet string maskedSeed of length hLen, and an octet
        string maskedDB of length k - hLen - 1 as

           EM = Y || maskedSeed || maskedDB.

This just splits the message EM without regard of the value of the octets.

    c.  Let seedMask = MGF(maskedDB, hLen).

Some function to calculate the seedMask, will finish without regard of the input...

    d.  Let seed = maskedSeed \xor seedMask.

Some function to calculate the seed, will finish without regard of the input...

    e.  Let dbMask = MGF(seed, k - hLen - 1).

Some function to calculate the dbMask, will finish without regard of the input...

    f.  Let DB = maskedDB \xor dbMask.

Some function to calculate the DB, will finish without regard of the input...

Now this is interesting, since we now have seed, dbMask but more importantly DB, which all have been defined in the encryption function as well. In other words, this whole process so far reversed the calculations in the padding process. If the input is garbage, then DB won't match the DB during encryption, but the above calculations will conclude in some result.

    g.  Separate DB into an octet string lHash' of length hLen, a
        (possibly empty) padding string PS consisting of octets
        with hexadecimal value 0x00, and a message M as

           DB = lHash' || PS || 0x01 || M.

Splitting DB of course is still performed without evaluating the values in the octets.

        If there is no octet with hexadecimal value 0x01 to
        separate PS from M, if lHash does not equal lHash', or if
        Y is nonzero, output "decryption error" and stop.  (See
        the note below.)

Finally, after all these calculations, we do some validation, before actually outputting M, which is the encrypted plaintext message. This is deliberately placed as final check, because we could have checked Y back at step 3b where it was the direct result of the modular exponentiation. To know why, see the section below.

So first we have to check the initial octet is 00 (although we may want to postpone that, see the section below).

Then most importantly we check if lHash' matches the hash over the label l, which is a configuration option so known beforehand. Generally, this label l cannot even be configured in implementations of RSA-OAEP so we can usually assume that lHash is simply the hash over an empty (zero octet) message, i.e. a constant specific to the configured hash function.

This is the most important step because it will check a full hash output size (in your case 16 octets for MD5) for correctness. And these 16 octets depend on all the other octets due to the masking process. Well, all other octets apart from Y that was already validated anyway. So there is negligible chance that the bits of this constant value are correct if any bits of EM have been altered.

Then we go over PS, expecting only 00 octets until the next octet which should have value 01 (if you look at it like that you don't have to check the 00 octets, just check if the first non-zero octet is 01). Finally we have M which can be anything so there is no possibility to check.

The chance that octet Y is correct and / or that the PS padding (which may be 0 bytes) and 01 byte is correct if incorrect ciphertext or key is used is around 1 in 192 * 256, depending somewhat on the modulus value. Although that chance is not very high, it is far from being negligibly small. So comparing the lHash and lHash' values is the comparison that matters.

Now for completeness, the note:

Note: Care must be taken to ensure that an opponent cannot
distinguish the different error conditions in Step 3.g, whether by
error message or timing, and, more generally, that an opponent
cannot learn partial information about the encoded message EM.
Otherwise, an opponent may be able to obtain useful information
about the decryption of the ciphertext C, leading to a chosen-
ciphertext attack such as the one observed by Manger [MANGER].

OK, so that's just about avoiding side channel attacks on the final validation.

It can probably be implemented very easily by validating lHash in a time-constant manner first. If that step hash negligible chance of completing if EM has an incorrect value, then obviously the Y must have value 00 and the separator be present and correct if it does complete.

If you want to know even more about OAEP padding validation and why it is secure then you probably have to consult the security proofs that have been presented for RSA-OAEP.


Are there post-quantum cryptosystems with a gap between classical and quantum security?

Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other:
Inverting a cryptographic group action such as CSIDH.

Let $G$ be a (finite) commutative group $G$ acting on a set $X$, i.e., we consider a map
$$ \ast\colon\; G\times X\to X$$
that is compatible with the group structure of $G$ in the sense that $1\ast x=x$ and $(g\cdot h)\ast x=g\ast(h\ast x)$.

The problem to be solved is analogous to the discrete-logarithm problem:

  Given two elements $x,y\in X$, find $g\in G$ with $g\ast x=y$, assuming it exists.

Classically, the best known attack is a meet-in-the-middle approach à la baby-step giant-step, where the group $G$ is split into two subsets $U,V\subseteq G$ such that $G=U\cdot V$, and one looks for a collision between the two sets $U\ast x$ and $V^{-1}\ast y$. Indeed, when $u\ast x=v^{-1}\ast y$, then $(u\cdot v)\ast x=y$. This takes time and space $O(\!\sqrt{\lvert G\rvert})$, which is exponential in $\log{\lvert G\rvert}$.
(In reality, there are better time-space tradeoffs than this simplistic approach.)

Quantumly however, this problem can be attacked using Kuperberg's algorithm [1,2] for the abelian hidden shift problem, and this takes subexponential (but superpolynomial) time in the group size. More concretely, the asymptotic cost is
$$ {\exp}\Big(\!\sqrt{\log{\lvert G\rvert}}+o(1)\Big) \text, $$
which can be roughly summarized as "taking a square root in the exponent".
(For comparison, the number field sieve for integer factorization is also subexponential, but with a cube root.)


How can I edit or build an app to encrypt data, and build a decryption key?

Generally speaking, it is not up to you to design and implement your own encryption algorithm. The time period where you could do that and maybe get away with it has long since past. Nowadays, we have standardized cipher algorithms such as AES, which are efficient on modern CPUs and believed to be secure against all currently known attacks.

So basically, your question is/should be, "how do I select an algorithm and generate a key for using it?".

My answer is, unless you can cite a specific reason to not use AES, then AES is probably what you should be using. So now that the algorithm has been selected, you need to find an implementation. This is a language dependent issue and you will have to find an appropriate library for the language your program will be in.

Do not just implement AES yourself (for production use; it's fine for fun). There are some "extra" implementation details that can influence the security of the implementation, and these things may be non obvious to those who don't know what to look for.

Key generation is simple: to generate a key, use the key generation function provided by the library that implements AES, or use the OS urandom/CryptGenRandom functions (for UNIX/Windows). A good library should disallow you from using inappropriate key sizes; For AES, 128, 196, and 256 bits are appropriate key lengths.

If you're on multiple platforms, you may want to find a cross platform crypto library to ease the implementation. An easier implementation can lead to less bugs, which can influence security.

Regarding "I imagine encryption via altering the pixels of the image for cool effects, but that may not be logically efficient" - you're going to want to forget about this idea. After successful encryption, any file data will look like noise/scrambled data - if it does not look this way, then you have a problem.

Lastly, unrelated to the crypto: adding a button to the native camera apps on your phone may be more complicated then writing say, a python script to encrypt the contents of the folder where the images are saved. The latter would not require modification of multiple, different, already compiled apps.

Alternative Ciphers

There do exist alternative designs that are both efficient and believed to be secure. If you really do want a different algorithm, this article might be interesting to you. Assuming the alternatives that are suggested are equally secure for practical use, you might implement each and measure which is most efficient for your specific application and platform.


Is this EAX extension weakening the (provable) security of EAX?

So you want to use EAX with a block cipher with a 56-bit key. Presumably, this is for a good reason.

Your idea is to include a (long!) fixed string in the OMAC to slow down nonce creation. Since the attacker must know the nonce to test if a key is correct, this should also slow down a brute force attack.

Instead of modifying EAX, you could use EAX in a slightly different way: Always prefix the EAX nonce by S, and always prefix the associated data by S. This seems to be equivalent in operation to your proposed modification. I don't think the EAX security proof covers this specific case, but I wouldn't be surprised if it could be adapted to this case. (Probably, you could argue that a random-looking function remains random-looking even when its inputs are restricted.) Which means that this should be ok.

You should note that including S in the associated data doesn't hinder the attacker, only the users of the system. So probably, S should only be included with the EAX nonce.

PS. You need a really good reason to use a 56-bit block cipher today.