Using same key and nonce for different field of the same document

I will assume you're asking about NaCl crypto_secretbox, although the same considerations apply everywhere ‘nonce’ appears in the NaCl API.

  Is it bad if I encrypt every field with the same key and nonce?

Yes, it is very bad.  If you reuse a key/nonce pair for two different messages, you violate the security contract of NaCl.  It is so bad that an adversary who knows the plaintext/ciphertext of one field can decrypt all the other fields, and forge arbitrarily many more fields.

Here are a couple of things you can do instead:

If you never modify a field, and you can uniquely name each field—e.g., name each field by (table name, column name, rowid), as long as you never reuse a rowid—then you could derive a key by a pseudorandom function of the field name: Given a master key $k$ and a field name $f$, use $k_f = \operatorname{HMAC-SHA256}_k(f)$ as the key to encrypt the field, with an all-zero nonce.

However, if you ever modify a field, even this is no good in case an adversary ever sees two versions of the same field, which would again violate the security contract.  If you additionally have a version number so that (table name, column name, rowid, version) is unique, you could use that instead (or use the version number as the nonce).
If you are willing to allow an adversary to see when a field value is repeated in multiple places or at multiple times, you can use a deterministic authenticated cipher.  NaCl doesn't have one built-in, but here's a relatively simple one you can make out of parts available in NaCl, which is designed to make a security reduction theorem easy to prove:

Parameters: 512-bit master key $(k_1, k_2)$, field name $f$ encoded so that no field name is a prefix of another field name.

(The field name need not be unique, but if you repeat a field name then the adversary will be able to tell when the field value is repeated.  Typical prefix-free encodings might be either (a) making sure every field name is exactly the same length, or (b) NUL-terminated field names if field names can't have embedded NULs, or (c) length-delimited field names with a prefix-free encoding of the field name's length followed by the field name.)
To store a field value $m$:

Compute the authentication tag $t = \operatorname{HMAC-SHA256/192}_{k_1}(f \mathbin\| m)$.  Here HMAC-SHA256/192 is first 192 bits of HMAC-SHA256.  (You can compute HMAC-SHA256 with crypto_auth_hmacsha256 in NaCl.)
Compute the unauthenticated ciphertext $c = \operatorname{XSalsa20}_{k_2}(t) \oplus m$, using $t$ as the nonce for XSalsa20.  (You can compute XSalsa20 encryption with crypto_stream_xsalsa20_xor.)
Store the concatenation $t \mathbin\| c$.

To load an encrypted field value $\hat t \mathbin\| \hat c$ (which may or may not be the same as what you previously stored, $t \mathbin\| c$):

Compute the putative plaintext $\hat m = \operatorname{XSalsa20}_{k_2}(\hat t) \oplus \hat c$.  (The forward and backward directions of XSalsa20 encryption are the same, so also use crypto_stream_xsalsa20_xor here.)
Check whether $\hat t \stackrel?= \operatorname{HMAC-SHA256/192}_{k_1}(f \mathbin\| \hat m)$; if not, immediately erase $\hat m$ and either drop the field on the floor or raise an alarm.  (Make sure to do this check in constant time.  NaCl provides crypto_verify_16 and crypto_verify_32 for constant-time comparison; you can use crypto_verify_32 for this if you just zero-pad the 24-byte tags up to 32 bytes.)
Otherwise, if verification succeeded, return $\hat m$ as the value of the field.

There are other deterministic authenticated ciphers on the market too, like AES-SIV and AES-GCM-SIV, but they have much smaller safe data volume limits than the one I just described, and they essentially require hardware support to avoid timing side channel attacks.


Is the CONF key sharing Problem equivalent to discrete log problem?

No.  There's no known proof that CONF is equivalent to the discrete log, in general.  When $q$ is prime, CONF is equivalent to the Diffie-Hellman problem.  And it's a long-standing problem whether the Diffie-Hellman problem is equivalent than the discrete log; see, e.g., Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?.

Proof of equivalence:

Note that if we can solve the Diffie-Hellman problem, we can solve CONF.  In particular, suppose $DH$ is a Diffie-Hellman oracle (so $DH(g,g^x,g^y)=g^{xy}$).  Then given $g,g^a$, you can compute $g^{a^k}$ for any power $k$: you can add in the exponent using the identity $g^{x+y}=g^x g^y$, and you can multiply in the exponent using the DH-oracle $g^{xy}=DH(g,g^x,g^y)$, so you can do the square-and-multiply algorithm "in the exponent" to compute $g^{a^k}$ from $g^a$.  Now setting $k=q-2$, we see that you can compute $g^{a^{q-2}}=g^{a^{-1}}$.  Finally, $DH(g,g^{a^{-1}},g^{ab}) = g^b$, so with one more application of the DH-oracle, we can compute $g^b$, solving the CONF problem.  Thus, CONF is no harder than the Diffie-Hellman problem.

Also, if we can solve CONF, then we can solve the Diffie-Hellman problem. Suppose $CONF$ is an oracle for the CONF problem, i.e., $CONF(g,g^a,g^{ab})=g^b$.  Then

$$CONF(g^x,g,g^y)= CONF(g^x,(g^x)^{x^{-1}},(g^x)^{x^{-1}y}) = (g^x)^{y} = g^{xy},$$

so an efficient solution to the CONF problem lets us solve the Diffie-Hellman problem.


TL;DR: Bit values of passwords are "weirdly" distributed and hash functions (and thus HMAC) are generally believed to deal better with them.

Why is HMAC?

Presumably originally the idea was to improve on previous designs which were all very hash-focused. People wanted to use hash functions in some way to process passwords. But the designers of PBKDF2 probably considered it wise to use a PRF (thereby reducing assumptions on the underlying function) and HMAC is the standard way of turning a hash into a PRF. Also they probably liked the idea of not having to jump through hoops to define ways to process arbitrary-length passwords.

Can I use other pseudorandom functions?

So, if your password was a uniformly random bit sequence, then yes absolutely you could use other PRFs and get a PRF out of PBKDF2. However, passwords generally don't stay to that model. In that case one usually turns to hash functions to map a high-entropy non-uniform value to a high-entropy uniform value.
Of course the above argument raises the question "what about KMAC and other hash-based PRFs"? They should work similarly well as they tend to inherit the security advantages of their underlying hash functions. Note however that some such constructions (not KMAC) have weaknesses with regards to variable-length keys. For those fix the length of your salt.
As for actually using KMAC (and this Keccak / SHA-3), this is a difficult situation. In principle it works. However you usually want to use functions for password derivation where the optimal ASIC to brute-force it would essentially be the hasher's normal CPU (or only marginally better). However until we get specialized Keccak extensions dedicated Keccak circuitry will likely be much faster than software implementations making PBKDF2-KMAC a much inferior choice to e.g. Argon2.


What are the qualities of a good block cipher? Beginner, Intermediate, Advanced, Expert

I don't think we can really separate things into skill levels as such, but there plenty of targets to aim for in terms of security goals. You'll want resistance to:

Differential cryptanalysis

Truncated differential cryptanalysis
Integral cryptanalysis
Impossible differential cryptanalysis
Higher order differential cryptnalysis
Boomerang attacks

Linear cryptanalysis

Differential-Linear attack

Rotational cryptanalysis
Slide attacks
Meet in the middle attacks

Biclique_attacks

Brute force search
Side Channel attacks

Timing attacks

Algebraic attacks
Partitioning cryptanalysis
Attacks that don't exist yet (at least, publicly)

Some resistance can be achieved via:

Large enough keysize

Mandatory for simple brute force search

Large enough blocksize

A large enough size can preclude the conditions for a slide attack to be applicable

Avoiding using secret information in ways that leak timing information

No lookup tables
No shuffling of arrays according to secret information
No secret dependent rotations

High levels of diffusion that cause the avalanche effect quickly

Some other desirable traits:

Software efficiency on a wide variety of platforms (i.e. 8 bit, 32 bit, 64 bit)
Key agility

Ideally the key schedule is invertible
Ideally the actual keys used each round are extracted from the invertible key schedule in a weakly one way manner (first preimage resistant)

Don't forget to obey Kerckhoffs Principle

After you've done all that, you might like to make your construction tweakable

Some of the mathematical concepts related to cipher design are:

Information theory

Information Entropy

Finite Fields
MDS matrix

Matrix
Coding theory

Boolean functions

S-box (meaning NxM mapping, not a lookup table)
Bent functions


plain textbook RSA signature with a fixed format input

That signature system is insecure assuming that the adversary

can obtain a few signatures for <user-id> and <device-id> which s/he can choose (with perhaps <user-id> constrained, e.g. in a list),
is deemed to succeed if creating a valid signature for some <user-id> for which s/he was not given signature (perhaps with some constraint) and <device-id> s/he can choose,
knows the public key $(N,e)$.

In a simple form of the attack, the adversary restricts to suitably smooth values of $m_i=$<user-id>0000f000<device-id>, and finds a set of these $m_i$ and associated $k_i\in\mathbb Z$ (with $k_0=1$, $k_i\ne0$) such that
$$1=\prod m_i^{k_i}$$
which, when there are enough smooth $m_i$, essentially reduces to solving a system of linear equations (obtained by considering the multiplicity of each prime factor of each smooth $m_i$). It is then easy to compute the signature $s_0$ for $m_0$ from the signatures $s_i$ for other $m_i$, as
$$s_0=\prod_{i>0}s_i^{-k_i}\bmod N$$

Improvements replace the constraint $k_0=1$ with $\gcd(k_0,e)=1$, and exploit very low $e$ like $e=3$, by noticing that a signature can still be forged if the linear equations on multiplicities are satisfied modulo $e$.

How hard the attack is depends primarily on the width of the $m_i$ (here modest with at most 96 bits, perhaps 65 or 48 with enough freedom <user-id>) and on the maximum number of signatures that can be obtained; on the freedom there is on the choice of <user-id>; and to some degree on $e$. Critically, the size of $N$ is immaterial.

The attack is often designated the Desmedt and Odlyzko attack, with reference  to Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985. A modern re-exposition is in section 3 of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (in proceedings of Crypto 2009
then Journal of Cryptology, 2016).

Exhibiting actual values of <user-id> and <device-id> allowing the attack is an interesting exercise.


How does CCM handle variable-length messages?

Q1: Since CBC-MAC is insecure for variable-length messages if nothing is done to handle them, I'm wondering how it can be used with variable-length messages.

CCM simply uses a packet format which simply includes the message size in the first block of data, see SP 80038C, to be precise section A.2.1: Formatting of the Control Information and the Nonce.

Unfortunately, including the length in the first block is what destroys most of the online capabilities. Furthermore, the packet construction is rather obnoxious, with a lot of bit fiddling and dependencies between different methods of length encoding, and so forth.

  Q2: Rogaway's critique of CCM indicates that it is not an online mode of operation (the length must be known ahead of time for CCM). So, can it be altered/modified to be online? Like by perhaps appending the length of the message as the last block?

Yes, it can be modified, but this is already done for you: it is called CMAC, usually prefixed by the cipher it was created for: AES-CMAC, particularly because it was designed for a block cipher with a block size of 128 bit:

  The core of AES-CMAC is the basic CBC-MAC.  For a message, M, to be
     authenticated, the CBC-MAC is applied to M.

CMAC consists of CBC-MAC with a pre- and post-processing added to it, particularly to avoid length extension attacks. It is possible to use AES-CBC and perform the pre- and post-processing yourself, which makes it a drop-in replacement for CBC-MAC even if CBC-MAC is accelerated.

There is a proposed AEAD cipher that replaces CCM as well, called EAX mode, which uses AES-CMAC to calculate the authentication tag. It was never standardized by NIST (and probably won't be, if you look at the time it has been a proposed mode) but it is a more flexible replacement of CCM.

Like CCM it only relies on the block cipher as underlying primitive but it is much more flexible and easier to handle as it doesn't require you to create "packets" like CCM mode does. Instead, everything is "online", with the disadvantage that it is - like CMAC - slower because of the pre- and post-processing required.

Both CCM and EAX mode are "two pass" AEAD ciphers, which means that all the data needs to be processed twice by the block cipher. There are modes of operation that can be faster: the single pass - but patented - OCB mode and the so called one-and-a-half pass GCM mode. Especially when accelerated (on newer Intel / AMD processors for instance) GCM mode will be faster than CCM or EAX mode, while only being slightly less flexible/online/foolproof compared to EAX mode.

The AES-CMAC RFC I've linked to is particularly based on XCBC MAC which was created by Philip Rogaway while EAX mode was specified here, which is co-authored by him. So he didn't just criticize fortunately, he did help to improve the situation as well.


Does encrypting both the message and digital signature adds to the integrity of the digital signature?

First of all, the fact that A is Bob and Alice is B is a bit confusing.

In my explanation:

A - Alice (receiver), has keys PRa, PUa
B - Bob (sender), has keys PRb, PUb

The former approach has a couple of substantial drawbacks:

The message is send in a plain text. Any one who has an access to a communication channel can read its content.
The signature of a message hash is separated from the actual message. They are only concatenated together and as the signature has a fixed size it can be easily stripped from a content.

The first drawback allows Max to read a content and decide that he wants to commit a forgery as it makes sense for his agenda.

The second drawback actually allows him to forge the email. He can easily calculate H(M). Assuming Max knows Bob's public key he can strip of the H(M) "verifying" the signature with Bob's public key.

Then Max simply signs the H(M) with his private key (PRm) and substitutes block E(PRa, H(M)) with E(PRm, H(M)).

The result would be that the message looks like sent by Max as it's signed by his private key and nobody can detect that it was originally an idea of Bob.

The later approach with encrypting both content and a signature with Alice's public key guarantees that only Alice would be able to decrypt the whole packet (thus content + signature).

Max won't be able to substitute the signature with his own as he doesn't knows PUa. Neither M, nor H(M) is possible to recover for him.

When Alice would receive the message it would decrypt it with her own private key (PRa) and then verify the signature with Bob's public key (PUb) thus being sure that the message was indeed send by Bob.

This pattern would still lack integrity check but generally it's much better then the former one.


Feasibility of finding public key when private key is known

In practice, no.

Firstly, RSA private keys are typically stored together with the public exponent. The standard definition includes the following information:

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Obviously, if this is the information you got, deriving the public key is just a matter of extracting the fields modulus and publicExponent.

Secondly, the public exponent is typically a small pre-defined value, selected for making the public key operation as efficient as possible. Even if all information you got in the private key is modulus and privateExponent, it would be trivial to test the two most common publicExponent values $3$ and $65537$ and see if they check out. If not, the publicExponent is rarely greater than $2^{32}$, so checking every such odd value would still be feasible.

Checking if a known privateExponent matches a guessed publicExponent, is typically just a matter of performing a RSA encryption of arbitrary data with one key, and test if the resulting cipher text can be decrypted with the other.

Thirdly, should the publicExponent deliberatly be selected as a random value roughly the same size as the modulus, then deriving publicExponent from privateExponent and modulus, would indeed be as hard as deriving privateExponent from publicExponent and modulus. This is however not how RSA is typically used or how RSA keys are typically generated.


What are some disadvantages of homomorphic encryption schemes?

The multiplicatively homomorphic variant of RSA is not semantically secure. This is a major disadvantage. ElGamal is a semantically secure, multiplicativey homomorphic cipher. Paillier is a semantically secure, additively homomorphic cipher.

As described by tylo, all homomorphic ciphers are malleable by definition. Chances are, however, if you are interested in homomorphic ciphers, however, malleability is probably not a concern.

Homomorphic ciphers typically do not, in and of themselves, do not provide verifiable computing. In words, you encrypt your data, send it to the cloud and let the cloud compute on it for you. How do you know the cloud performed the correct computation? To get this sort of guarantee, other machinery is needed.

Performance is often a disadvantage. Ciphertexts in the ciphers you mention are much larger than the plaintexts, so communication requirements typically go up. The computations on these large ciphertexts are typically slower than if you just performed the computation on the plaintext itself. Because of this, in the outsourcing computation model, we typically see a requirement that encrypting inputs and decrypting outputs should be faster than performing the computation itself. In the case of multiple parties with individual inputs this seems to be less of a concern as privacy, not efficiency is the concern.

In the case of multiple, participating parties, guaranteeing fairness (which means everyone who is suppose to get an output, gets it) is often difficult and requires extra machinery (e.g., threshold decryption) and more assumptions (threshold of honest parties, etc). Another concern in the multiple, participating parties model is how the parties privately input their values for the computation. If one party knows the private key, they can decrypt the inputs and violate another party's privacy. So in this case, threshold decryption is often used. This in itself is a disadvantage as generating threshold keys is a non-trivial task.


DH prime size required to force an attack of $2^N$ steps

How do we pick a group size for a 128-bit security level?

Estimate the cost of mounting an attack as a function of the group size.
Find the group size that puts that cost estimate above $2^{128}$.

In this case, for appropriately selected groups, without back doors, like the RFC 3526 groups, the best attack algorithm is the general number field sieve, GNFS.  The usual (single-target) cost estimate for the GNFS is $L^{\sqrt[3]{64/9} + o(1)} \approx L^{1.92999 + o(1)}$ where $L = e^{(\log p)^{1/3} (\log \log p)^{2/3}}$ and $p$ is the modulus.  Where 6800 came from is unclear to me; the usual consensus is that 3072 is plenty for a 128-bit security level, even if the $\sqrt[3]{64/9}$ figure is optimistic.  Of course, you can get much better performance, and much better implementation security, if you use X25519 instead.


Why do the elliptic curves recommended by NIST use 521 bits rather than 512?

I very much suspect it's to related to the fact that $2^{521}-1$ is prime. The previous similar prime is $2^{127}-1$ and the next such is $2^{607}-1$ so they're quite rare. Elliptic curve operations on such a field can be implemented somewhat faster than over another prime field with similar size but without this special form.

I very much doubt that serious thought went into this decision at all. If there are no breakthroughs in elliptic curve logarithm finding then 521-bit coordinate components are complete overkill. If there were a suitable breakthrough then there's no guarantee that 521 bits would be enough.
Elliptic curves tend to be used when the size becomes a factor in the design of a system. It's hard to imagine what sort of constraints would have to operate to make a 521 bit curve order make sense.


Consequence of $p\bmod e=2$ in RSA prime generation

Very large exponents $e$
Assuming that $e > 2^t$ where $t > 514$ we may use Coppersmith's attack to factorize $N$ efficiently. By this answer I only intend to exemplify that for some public exponents $e$ the given condition on the primes makes it significantly easier to factorize the RSA modulus. In particular it is worth noting that public exponents $e$ that conform to the FIPS 186-4 standard are less that $2^{256}$, and are therefore not susceptible to the following.

The following (essentially) appears in [1].
Theorem (Coppersmith)
Let $N$ be an integer of unknown factorization which has a divisor $b \geq N^\beta$, $0 < \beta \leq 1$. Let $0 < \epsilon \leq \frac{1}{7}\beta$. Furthermore, let $f(x)$ be a univariate monic polynomial of degree $\delta$. Then we can find all solutions $x_0$ of the equation $f(x) \equiv 0 \bmod b$ such that
$$|x_0| \leq \frac{1}{2}N^{\beta^2/\delta - \epsilon}$$
using a LLL-reduction on a lattice of dimension $\leq \frac{\beta}{\epsilon} + \frac{1}{\beta}$.
We will apply this theorem for $\beta = 1/2$, $\delta = 1$, $b = p$ where $p$ is the larger of the two prime factors of the public RSA modulus $N = pq$, and $\epsilon = (t - 514)/2046$. To find a suitable polynomial $f$ we note the following.
Note that $p \bmod e = 2$ implies that there is some integer $x$ such that $p = ex + 2$. If we can find this $x$ we can determine $p$. Now, note that
$$ex + 2 = p \Rightarrow e_0 ex + 2e_0 = e_0 p,$$
where $e_0$ is the modular inverse of $e$ modulo $N$ (which is expected to be easy to determine), say $e_0 e = 1 + \ell N$. Furthermore, note that the right hand equation may be rewritten as $x + 2e_0 = e_0 p - \ell N x$ which implies $x + 2e_0 \equiv 0 \bmod{p}$. Hence, we have that any solution $x$ to $p = ex + 2$ must also be a solution to $f(x) \equiv 0 \bmod{p}$ where $f$ is the monic degree 1 polynomial defined as
$$f(x) = x + 2e_0.$$
Now, applying Coppersmith's theorem, with the given parameter values, we get that we find all solutions $x_0$ such that
$$|x_0| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}$$
using a LLL-reduction of a lattice of dimension $\leq \frac{1023}{t-512} + 2$.
Finally, we want to show that the $x$ such that $p = ex + 2$ is among the solutions found above. For this we have to show that such an $x$ must satisfy
$$|x| \leq \frac{1}{2} N^{1/4 - (t-514)/2046}.$$
We can do this by noting that since $p = ex + 2$ we have $x \leq p/e \leq 2^{1024-t}$. Now, $N = pq > 2^{2046}$ and thus
$$2^{1024-t} \leq \frac{1}{2}N^{1/4 - (t-514)/2046},$$
as desired. Hence, one of the solutions $x_0$ found by the LLL-reduction in Coppersmith's theorem is the sought after $x$. To determine which solution is the correct one all we have to do is a trail division of $N$ by each $ex_0 + 2$.

Remark: We can at least do some small improvemets to the above, e.g. by noting that $x$ has to be odd so really we may start with an equation of the form $p = 2ey + e + 2$ instead.
[1] May A. (2009) Using LLL-Reduction for Solving RSA and Factorization Problems. In: Nguyen P., Vallée B. (eds) The LLL Algorithm. Information Security and Cryptography. Springer, Berlin, Heidelberg


For Diffie-Hellman, why is a g value of p−1 not a suitable choice?

If $g=p-1$ then $g\equiv -1\pmod p$ that is $g$ is effectively the same as $-1$ which has the obvious drawback that $g^x$ can only ever be $+1$ or $p-1$ which is easily brute-forcable.

Here's a short proof sketch of the above exponentiation statement:

\begin{align}
 (p-1)^2\bmod p  &= (p^2-2p+1)\bmod p \\
  &=(p^2\bmod p)-(2p\bmod p)+(1\bmod p)\\
  &= 0-0+1\\
\end{align}

So when you have $(p-1)^x\bmod p$ this is the same as $(p-1)^{2y}\cdot(p-1)^{z}\bmod p$ for $x=2y+z$ and $z\in \{0,1\}$ which is $((p-1)^2)^y\cdot (p-1)^{z}\bmod p=1^y\cdot (p-1)^{z}$ which is either $p-1$ or $1$.


No, in the end the private exponent $d$ is just a number within $0..N$ where $N$ is the modulus. It depends on $N$ what the chance is that the first bit is one, but in more likely to be valued $0$ than $1$ (given that it is well distributed, you would expect it to be $0$ around $\frac23$ of the time). If you generate enough private keys you'll even see private exponents that start with a few leading bytes that are completely zero'ed out (!). That's not a problem cryptographically speaking, it just shows that the entire key space is utilized.

So the private exponent $d$ doesn't always start with a $1$ when you consider the most significant bit of the modulus. The fact that the modulus is strictly less than $2^{keylength}$ does matter ever so slightly though. But as RSA requires exponential sized keys to achieve a certain security level, that should not worry you overly much (1 partial bit out of 1024 for the absolute minimum key size is completely negligible). Even if the private exponent would always have a 1 at the most significant position then the same logic applies; it would not have any significant impact on security.

I'm assuming a calculation with a preset/precalculated RSA public exponent, which is most often used in practice. If PKCS#1 conformant calculations are used then the most significant bit of $d$ is always $0$.

As I'm not that good in statistics, my computer has calculated that the first bit is probably 0 about 69 percent of the time and the first byte is zero 0.54 percent of the time, slightly higher than you would probably expect. And yes, I did generate 21171 keys starting with at least two zero bytes.


@fgrieu is right.  I concur with the recommendation to use CMAC.  That is a simpler, more general solution.  Also, if space is at a premium, you can probably truncate the output of CMAC to 8 or 10 bytes, while still receiving adequate security.

One remaining vulnerability is that this scheme does not prevent an attacker from replaying, re-ordering, or deleting messages.  If you send messages A,B,C,D, the attacker can arrange for the recipient to receive D,B,C,B,B (for instance).  If you want to defend against that, you could use a sequence number (or possibly a timestamp).

Another vulnerability arises if you use this key for multiple connections.  For instance, let's suppose Alice, Bob, and Carol share a single CMAC key.  Then if Alice sends message M to Bob, the attacker can arrange to redirect the message to Carol and make Carol think that Alice sent M to her.  One defense is to never reuse the same CMAC key (make it unique to a pair of endpoints and a direction).  A different defense is to include the identity of the sender and the recipient in the input to CMAC, i.e., you compute T = CMAC(K, sender || recipient || message) and use T as the authentication tag.  This solution does not increase the size of the packet, so it is essentially free.


Your intuition that $G'$ is insecure is correct, but your approach is a bit off. In the PRG security game, the adversary is not allowed to influence the choice of seed, which is always chosen uniformly at random.

To attack $G'$, notice that given just $G'(s)$, you can reconstruct $s$ from $\bar{s}$. Therefore a distinguisher, when given a challenge output $w$, can compute $G'(\bar{w}[2n+1] \cdots \bar{w}[3n])$ and check whether this gives $w$.


What happens if no final subtraction is done in Montgomery multiplication?

Theorem 2 in [Dussé et al. 1991] states that, if we skip the final subtraction, then, for $N < R / 4$ and $0 \leq A, B < 2 N$, we have $0 \leq C = \text{MonMul}(A B) < 2 N$, while keeping $C \equiv A B R^{-1} \pmod N$. I think the condition $N < R / 4$ inherently holds in your case e.g. you are using larger $R$ value acutually.


Zero-knowledge proof that a group element is a quadratic residue?

First let's develop a zero knowledge interactive proof. The verifier doesn't know $p,q$ as otherwise he could just take the roots. Let $a$ be the putative residue, and have $P$ know a square root $t$. So P will take a random number $r$ and send $r^2$ to V. V will send a bit, either $0$ or $1$. If $0$ P sends $r$ to V. If $1$ P sends $rt$ to V. This is zero-knowledge by a standard simulated transcript argument. It is a proof of knowledge because P must assure that $r^2a$ is a quadratic residue, and it is enforced that he must send a square.


(I am one of the authors of the paper you're asking about.  The isomorphism $\varphi$ you wrote is the intended one.)

The key observation is that a Gaussian $D_r$ of parameter $r$ over $\mathbb{C}$ is "spherical," i.e., it is the sum of independent Gaussians (both of parameter $r$) for the real and imaginary components, and so is invariant under rotations of the complex plane.  Therefore, $x \cdot D_r$ equals $D_{|x| \cdot r}$ for any $x \in \mathbb{C}$.

The claim then follows by the fact that multiplication in $K$ corresponds to coordinate-wise multiplication in the real/complex components of $\sigma$.  That is, the distribution of $x \cdot D_{(r_1,\ldots,r_n)}$ for $x \in K$ is just $D_{(|\sigma_1(x)| \cdot r_1, \ldots, |\sigma_n(x)| \cdot r_n)}$.  (Note that the conjugate symmetry of the pairs of complex embeddings is preserved, as needed.)


How to break AES CBC with PKCS#5 padding?

You may take the following approaches:

You can check if the key generation or storage has any weaknesses;
You can check if padding oracle attacks apply;
You can check if (part of) the ciphertext has been generated previously (using the same IV).

Neither of these methods work when AES CBC has been correctly applied. AES does provide adequate confidentiality, even for many ciphertext&plaintext pairs.


Authentication in Lattice PQC candidates

As I understand, GCM will also be broken by quantum computing

The idea that GCM would be broken is, at best, questionable; it is broken only in the scenario where you allow the attacker to make entangled queries, and is returned entangled answers.  That is, for this to be an applicable attack, the implementation under attack must also be a Quantum implementation; that is, it must receive the entangled state from the adversary, it must maintain it throughout the encryption/decryption process, and then return the entangled result back to the adversary.
This is in contrast to RSA/DH/ECC - there, you can take the public key, load it into your Quantum Computer, run Shor's, and directly obtain the private key - the only cooperation you need from the device under attack is the public key (which we generally assume is public).
In a white-box scenario, this attack against GCM is plausible (because the adversary would be able to install the entire implementation-under-attack within his Quantum Computer and make entangled queries at will).  Outside of that, this would seem (to me) to assume an extraordinary amount of cooperation from the device under attack.  In some ways, this could be considered a side channel attack; only much easier to defend against than most side channel attacks (just don't implement GCM in a way that preserves Quantum entanglement - given that we currently don't know how to preserve entanglement over that many operations even if we wanted to, this sounds quite easy).
No one thinks GCM is broken because DPA probing can, given a sufficient number of queries, generally recover the key - it's not clear to me why this easier-to-defend against attack is more of a concern.


Deniability and Prekey Security in X3DH Key Agreement Protocol

Deniability

Let's say that Eve notices that Alice and Bob are having a secure communication. Later on, Eve shows up to Alice's home and demands that Alice turn over all of her private keys so that Eve can expose their conversation. Alice and Bob want to ensure that their previous communications remain private.

If Alice encrypted a message $m_1$ into ciphertext $c = E(m_1,r)$, where $r$ is some random input (perhaps a shared secret), then Alice may want to deny she sent $m_1$ and instead claim that she encrypted another message $m_2$ such that $c = E(m_2,r')$, where $r'$ is some other random input. If $E$ has this property, it's called deniable. Unless Eve has telepathic superpowers, she can't trust Alice at all, since she could've turned over $m_2$ and $r'$ instead of $m_1$ and $r$. In fact, this protects Alice's data from even herself in the future! (How could Eve trust anything Alice decrypted?)

(Of course, if Alice for some reason has to hand over $m_1$ and $r$, there is no hope. I took the example from this paper.)

X3DH doesn't allow Alice and Bob to prove that they had a particular conversation; their messages are deniable. But: if Eve forces Alice and Bob to hand over private keys, Eve can generate conversations that appear to have come from Alice and Bob.

Compromise of Prekeys

Recall the formulas used to derive the secret key from the prekeys:

DH1 = DH(IK_A, SPK_B)
DH2 = DH(EK_A, IK_B)
DH3 = DH(EK_A, SPK_B)
SK = KDF(DH1 || DH2 || DH3)

If I have access to the prekeys, I can try to calculate DH1,DH2, and DH3 (although I think this is hard without the ephemeral and identity keys) and carry out key-compromise impersonation attacks; see this informal overview. Basically, I can compute the shared secret if I have a secret key SK and impersonate someone in a conversation. This is why the protocol suggests periodically uploading prekeys to the server, since these attacks are invalidated (the secret key depends on the prekey).


Security equivalent to Diffie–Hellman problem?

It is equivalent to the computational Diffie-Hellman problem; if you can one of the two problems, you can solve the other (with a polynomial number of queries to the oracle which solves the other).

If you can solve the Diffie-Hellman problem, you can solve your problem: this can be seen by first noting that, with a Diffie-Hellman solver, given $g^b$, you can compute $g^{b^{-1}}$; this is done by computing $g^{b^k}$ (which can be done with $O(\log k)$ queries to the DH oracle) with $k=q-1$ (where $q$ is the order of the group).  Once you have that, you can do another query with $g^{b^{-1}}$ and $g^a$ to obtain $g^{ab^{-1}}$, and once you have that, you can then compute $g^{acb^{-1}}$ directly (as you know the value of $c$).

If you can solve your problem, then you can solve the computational Diffie-Hellman problem with two queries; given $g^a$ and $g^b$, you can first do a query with $g^1$, $g^b$ and $c=1$ (to compute $g^{b^{-1}}$), and then with $g^a$ and $g^{b^{-1}}$ and $c=1$ to compute $g^{ab}$


Handshake differs greatly between SSLv2 and SSLv3. All versions of TLS (1.0, 1.1, 1.2) use the SSLv3 format and although they add some new options and features they don't alter the basic flow relevant to DROWN. Although formatted differently, the security content of SSLv2 ClientMasterKey is the same as SSLv3/TLS ClientKeyExchange when using RSA keyexchange, in that both contain an RSA (specifically PKCS1v1.5) encryption of the only secret information needed to determine the keys, which is exactly why DROWN works.

The critical difference is SSLv2 ServerVerify. Quoting from the DROWN paper:

  2.2 SSL and TLS ...
  The SSLv2 handshake protocol. ...
    The server responds with a ServerVerify message
  consisting of the challenge $r_c$ encrypted with
  the server_write_key. ...
    Our attack exploits the fact the server always decrypts
  an RSA-PKCS#1 v1.5 ciphertext, computes the
  server_write_key, and immediately responds with a
  ServerVerify message. The SSLv2 standard implies
  this message ordering, but does not make it explicit. However,
  we observed this behavior in every implementation
  we examined.

  The TLS handshake protocol. ... or SSLv3, ...
  The two main details relevant to our attacks are: ...
  * After receiving the ClientKeyExchange message,
  the server waits for the ClientFinished message,
  in order to authenticate the client.

This is why SSLv2 provides the Bleichenbacher-style oracle but SSLv3 or TLS does not, so DROWN can use the SSLv2 oracle to break SSLv3 or TLS sessions.


No, $F'$ is not a secure PRF. There exists an efficient distinguisher $D$, which can distuingish between $F'$ and $f$ with overwhelming probability.

Imagine D asks her two oracles for the value of $F'(k,x'\mathbin\Vert x')$ and $f(x' \mathbin\Vert x')$.

$D$ additionally asks the following queries from her oracle:
$$F'(k,x\mathbin\Vert x')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')  $$
$$F'(k,x\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')  $$
$$F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')  $$

Finally if she xor's all three of these values she can obtain $F'(k,x'\mathbin\Vert x')$:
$$F'(k,x\mathbin\Vert x')\oplus F'(k,x\mathbin\Vert x'')\oplus F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')\oplus F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')\oplus F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x')=F'(k,x'\mathbin\Vert x').$$

Therefore she can distinguish between $F'$ and $f$ with overwhelming probability. $D$ is trivially efficient (runs in polynomial time), as it only uses $3$ oracle queries.


What are the differences between ephemeral-static ECDH and static-static ECDH?

Static static Diffie-Hellman isn't that commonplace. It uses two static key pairs (where both the public and private keys are static, not just the public key) to establish the secret. Generally those keys are trusted keys: the public keys are commonly embedded in signed certificates. That way static-static Diffie-Hellman can be not just used to derive a secret (session) key, but also to authenticate both parties.

Note that it is required to use a nonce generated by (at least) one of the parties for static-static Diffie-Hellman: without this nonce the derived secret would always be the same, as there is no fresh data within the Diffie-Hellman calculation itself.

Static-static Diffie-Hellman is not provide forward secrecy: if either one of the private keys is found by an adversary then the shared secret can be calculated (using the public key of the other party) and all security is lost.

With ephemeral-static Diffie-Helman one party generates a new key pair for each key agreement.

Only the party with the static key pair can be authenticated by the key agreement itself. The other party with the ephemeral (transient or fleeting) key pair can authenticate itself after the key agreement. As it knows now that the session is to a trusted party, that authentication could be anything from signature generation to simple password validation over a secure channel.

Ephemeral-static Diffie-Hellman is does not provide forward secrecy. If the static private key is found by an adversary then the shared secret can still be calculated for this and every other connection that was created by it.

Generally ephemeral-ephemeral Diffie-Hellman is used. This provides forward secrecy: the other sessions are still secure even if one or both of the private keys is found. Both key pairs are regenerated for each key agreement. Fortunately, DH key pair generation is nowhere as slow as RSA key pair generation. RSA or ECDSA can be used to authenticate one or both the parties.

All of the above goes for both Diffie-Hellman using a multiplicative group (just DH) as well as ECDH. More info can be found in the document NIST Special Publication 800-56A, Revision 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Take a look at the C(0e, 2s) for the static-static and C(1e, 1s) for the ephemeral-static scheme.


This is a simple 128-bit block cipher, reversibly changing a 32-bit word of the state at each of 4 steps shown. It is very similar to an unbalanced Feistel cipher, except that the change of state is with += rather than the conventional ^=. In the context that deviation has three consequences, with the first rather desirable:

It creates alternation of ^ and + in the diffusion pattern.
Decryption is less similar to encryption than in a Feistel cipher (I guess the decryption code use uses -= ).
Hardware implementation would be slightly bigger/more power hungry, perhaps even slightly slower; but 1 more than compensates, and that's a non-issue in software.

To hope for security, there must of course be MUCH more rounds than shown. We have not even reached full diffusion (nothing in B or C influenced the outcome of A ). As a crude reference, AES-128 modifies its full state 10 times (discounting the initial XOR with a subkey); and Speck-128-128 modifies it 16 times. Security will depend a lot on the number of rounds, on a sensible choice of table P, and on the key schedule (producing the array k of subkeys from the actual key).

Note: Implementation in software is likely to suffer from data cache timing dependencies and other cache-related side channels, due to indexing in P at data-dependent indexes.

Note: as pointed by Poncho (correcting my mistakes), this cipher generates an even permutation; but that's not a weakness, since that reveals 1 bit of information only after $2^{128}-2$ input-output pairs are collected.


For a real-world example of precisely the same ECB weakness leading to a massive password compromise, see the Adobe password database leak, as memorably illustrated in the xkcd web comic:
$\hspace{83px}$
(source: xkcd.com)
While there were several issues contributing to the scale of the compromise, one of them was that Adobe, instead of properly hashing the passwords, encrypted them using ECB mode instead.  Even though the attackers apparently did not get the encryption key (or, if they did, they chose not to disclose it), this still exposed several weaknesses that made the passwords much easier to guess:

The length of the encrypted data revealed the length of the password, rounded up to the next 8 bytes.  (This weakness is actually not specific to ECB mode, but I'm including it for completeness.)

Identical passwords produced identical ciphertexts, making it easy to locate frequently reused (and thus presumbaly weak) passwords, and also allowing multiple hints for the same passwords to be correlated as shown in the cartoon above.  (This is a weakness of ECB mode; it would not have happened if the encryption had been done using a semantically secure mode with a proper IV.)

Passwords with the same 8-character prefix yielded ciphertexts with the same first block, making it easier to guess the prefix by comparing hints.  Similarly, any multi-block passwords differing only in some of the blocks would yield partly matching ciphertexts, and any password that happened to contain repeating 8-character blocks (say, "passwordpassword" or "aaaaaaaaaaaaaaaa") would produce a repetitive ciphertext, just like in the Tux image example.


Preventing attack in RSA modified version

Tldr: Your notes are nonsense.

First, normal RSA: There are some big, random, secret (pseudo)-primes p and q, and a nonsecret N with N=p*q. RSA is secure (well, other than the known problems) because an attacker can't extract p and q from N (factorization).

Your version of RSA does not require that q is prime, just big and random. If the random number happens to be a prime, everything is ok.
If, on the other hand, it is something like 2^1024 or anything else with lots of small prime factors, it's trivial to factorize N => broken. In real RSA, the requirement for primes is important.

  We can show that the decryption problem is equivalent to find the
  factor p of n.

Yes, like in normal RSA. If p is found, q=N/p, broken.
But again, if I can factorize N easily, there's no challenge.
Let's take the 2^n - example from above: I do N=N/2 until I have a prime number (or any uneven number), and that's p. ... Other numbers than 2^n are not much harder.

  In the previous the deduction we actually chose a convenient message
  to show that solving decryption problem implies factoring n but in
  reality we won't get a chosen message m but random ones

The content of the message m does not matter at all. Factoring N => broken, that's all.

  One can add some redundancy in the message before encryption, and
  check the redundancy after decryption before disclosing the result.

That's something to detect tampering (ie. the attacker changes the encrypted data to something else, without knowing the plain content), but it does not prevent factorization.


Sequential public key generation with secret private keys?

Yes, this is indeed possible.

A scheme with such properties is e. g. used in Bitcoin's HD (hierarchical deterministic) wallets. The scheme was introduced in BIP32 (Bitcoin Improvement Protocol) and is explained in detail here: https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

Regarding your example scenario: That is also possible with the system Bitcoin uses. However the key derivation path and the order in which the private keys are released is important in order to not leak future private keys in advance.


Using states of a double pendulum as a one-way function

It's an interesting idea, but I don't think it offers any advantages over current one-way function candidates and may be worse. For one thing, specifying the initial data of the simulation specifies a lot of properties of the dynamical system that will remain invariant (conservation of energy, horizontal component of momentum, et cetera). There are also constraints on the phase space of the coupled pendulums that never change over time either. I'd want the scheme to not have lots of internal constraints and symmetries for an adversary to exploit.

With a dynamical system like this, assuming the adversary can just look at the pendulums, she could just "look at the internals" of your scheme at any time, set up her own Lagrangian or Hamiltonian. By just observing the motion, the state of your one-way function is "leaked".

Also, since floating-point numbers are involved in the numerical solution of the system of equations, if you and I use slightly different numerical integrators, even for the same initial state, we may get different final states / "public keys" due to rounding or Runge-Kutta methods. In fact, you will have to specify the initial position and momentum extremely well, since any small changes in this data will cause wildly different subsequent states: chaos in a nutshell.


I would say that all of them are valid options, with the security differences they might have negligible. So I focused on other properties of the approaches:
Option 1: XOR
I think the most interesting property here is the malleability that gives us the XOR function. If I'm a keyholder under this chema, I could give n keys which XOR to my half to my n children, and their keys combined will be as good as mine.
Similarly, it the requisites went from 2-people to 3-people (such as including a new partner in the business), they could each provide a random half-key to combine with their now-new-half.
It also has the property of being commutative. This is silly from a cryptographic and technological point of view, but if you are giving two keys to two people, one might think to be more important to have the "first" key, or feel hurted on their big ego for only being given the "second" key. Here, both keys are equal rank, their order doesn't matter at all.
Option 2: KDF
This woud be similar to the above, but not allowing you such malleability (which you may consider good or bad).
You may want to combine them in lexicographical order, so that it doesn't matter the order in which they are provided. For the reasons provided above and less user errors by not being possible to provide them in an order it doesn't work.
Option 3: Encrypt twice
This option would be slower, although just doing two layers of encryption would not be a noticeable hit. You should perhaps be careful to do both things "at once" or with pipes, not using intermediate temporary files that might end up recovered. Although you would still have the same concern with the final decrypted item.
This solution would be subject to a Meet-in-the-middle attack. I don't think this would actually be a realistic concern, since you would still need to break AES.
A new keyholder could be added by encrypting the existing ciphertext with the new key.
Same comment as above about setting an order would be applicable.
Option 4: Split the key in two
Just for completeness, I'm adding the trivial solution of, instead of giving 128 or 256 bit keys to each of them, directly providing half the key (64/128 bit keys) to each one. This means each key is half the size, with no benefit over the other solutions, so I wouldn't recommend it.


In OAEP we pad the message with $k_1$ zero bits and $k_2$ random bits. It's the zero bits which give you verification. The all or nothing gurantee means if you change anything you will flip all bits with probability 0.5 and the chances of getting $k_1$ zero bits by chance is 1 over $2^{k_1}$


Using DH when both sides have static public keys (always send the same message when running the DH protocol) doesn't make DLP easier. It does increase the value of the secret key.

There are some things to worry about. If the DH shared secret or one of the secret keys is compromised, the compromise is complete. This is mitigated if the static public keys are replaced often.

In ordinary DH, the shared secret is a one-time secret. With static public keys, you have a multiple-use secret. You need to be very careful when using this key.

You should also be aware that DH where only one side has a static public key is essentially equivalent to ElGamal encryption...


What makes adaptive memory attack difficult for the adversary?

The game is not trivial for the adversary to win because the author is suppressing $ENC\hspace{.02 in}$'s randomness, which makes it so for most PKE systems it will be the case that $\; \operatorname{Prob}\left(ENC_{PK}(m) = ENC_{PK}(m)\right)$

is exponentially small, in which case the probability that either $ENC_{PK}(m_{\hspace{.02 in}0})$

or $ENC_{PK}(m_1)$ matches the challenge ciphertext is also exponentially small.

"state" is the contents of $A$'s memory locations during step 3,
when there's just an $A$ rather than an $A1$ and an $A2$.


How to prove that the concatenation of two secure PRG is secure?

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints:

You're on a good direction.  If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy.  Keep at it.
Your particular distinguisher $A$ is not an effective distinguisher against $G$.  Hint: What is the running time to compute $A(x)$?
You can probably fix up your distinguisher (to get the runtime down to something reasonable), but that's working harder than you need to.  Instead, you might want to read on....
Have you heard of the notion of a "hybrid argument"?  If yes, can you see any way that it might be relevant?  If no, go read up on "hybrid arguments"; they are a fundamental and important proof techniques for proving indistinguishability/distinguishability.


Is it safe to derive two different keys with the same password and key derivation function using two different salts?

With a KDF meeting its objectives, the only way the leak of the persisted key compromises the confidentiality of the other is correctly identified in the question: a password guess can be checked at the cost of one evaluation of the KDF based on the leaked key and its corresponding salt (and assuming the password's entropy is significantly less than the leaked key's width, it's unlikely there's a false positive); so when and if the password is found based on that, the second key is trivially found.

All KDFs have the objective that knowing the output with one salt, it's impossible to find (or otherwise obtain information about) the output for another salt with significantly less cost than testing the passwords (or more generally: than testing values fed to the key input of the KDF, for those KDFs that are not purposely slow in order to stretch a password's limited entropy). PBKDF2, bcrypt and scrypt convincingly meet that objective.

So the answers to the questions in the last paragraph are no, and no for a good KDF. For the question in the title, I'd answer yes, for a good KDF, and within the fact that the common password can be brute-forced with enough effort.


How do you perform the invert operation of Pm = kP on elliptic curve?

How to you perform the invert operation ?

Actually, we hope that is a hard problem.  After all, if someone has an efficient way, given $G$ and $xG$, to recover $x$, almost all crypto based on elliptic curves is broken (exception: isogeny-based crypto).

So, what do we do?  Well, we arrange things so that we don't need to solve this hard problem to decrypt.

One way is the change how we do things.  Instead of trying to encode the message as a point, we can use ECIES:

We have a private key $k$ and a public key $kG$
To encrypt with the public key, we pick a random value $r$, and compute both $rG$ and $r(kG)$.  Then, we transform $r(kG)$ into a symmetric key, and use that to symmetrically encrypt the message.  Then, the ciphertext consists of both $rG$ and the encrypted message.
To decrypt with the private key, we compute $k(rG) = r(kG)$, and use the exact same transforming to turn that into the same symmetric key, and then use that to decrypt the message, revealing the original plaintext.

This works quite well, and avoids any awkwardness about converting a message into a elliptic curve point in a reversible fashion...


You could use the turtle block cipher with CMAC, maybe.

The turtle block cipher claims a cipher design that is based on "an NP-Complete Subproblem".

Block ciphers can be used to produce authentication tags via algorithms such as CMAC.

I'm not sure if this combination necessarily qualifies the authentication as being based on an NP-Complete subproblem too.


What is the difference between "securely realizes" and "securely implements"?

Realizes vs Implements
Given the context of the cited papers, they mean the same thing. That said, I would prefer realizes. Implements has a connotation of a source code implementation. There could be implementation flaws (buffer overflow, etc) that impact security. The protocol design is secure, but the implementation is not. That, to me, is the primary reason to prefer realizes over implements.
Simulate vs emulate
The difference in the wording on the Wiki stems from the difference between the two. I found this description of the general difference between the two to be good.

Emulation is the process of mimicking the outwardly observable behavior to match an existing target. The internal state of the emulation mechanism does not have to accurately reflect the internal state of the target which it is emulating.
Simulation, on the other hand, involves modeling the underlying state of the target. The end result of a good simulation is that the simulation model will emulate the target which it is simulating.

So, the wiki article says that "the protocol may simulate the other protocol", but it doesn't have to simulate it (in terms of modeling the underlying state of the target). All it really has to do is emulate, or mimick the outwardly observable behavior. So, internally, we may be simulating the protocol, or we may be doing something else, as long as as long as the outside observable behavior matches.
Note that in Universal Composability, there is a simulator $S$, that is not called a simulator because it simulates the real functionality, it is called a simulator because

We often call the adversary $S$ a simulator. This is due to the fact that in typical proofs of security the constructed $S$ operates by simulating an execution of $\mathcal{A}$.


It's certainly possible, although it will be very slow.

TweetNacl includes all the required field arithmetic operations. The main thing you will have to implement is the Chi function.

If you don't understand the internals and how these functions work, I would recommend using libsodium instead. It has a compatible API, and supports hash-to-point using Elligator.


Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$

There are concerns on curves defined over an extension field. In particular for those of a small extension degree.

For a curve with a subgroup of prime order $r$, generally the best algorithm to solve the discrete logarithm problem has a complexity $O(r^{1/2})$. But there are attacks that use the structure of the extension field to get an algorithm with a smaller complexity.

Weil descent. The finite field $\mathbf F_{q^n}$ can be viewed as a $\mathbf F_q$ vectorial space of dimension $n$: a polynomial equation defined over $\mathbf F_{q^n}$ can be viewed as $n$ polynomial equations defined over $\mathbf F_q$.
It is possible to construct, under some conditions, a homomorphism from an elliptic curve $E$ defined over $\mathbf F_{q^n}$ to the jacobian a hyperellipti curve $H$ (the group associated to the curve, in the case of elliptic curve it is the curve itself) over the smaller field $\mathbf F_q$.
$$
\varphi : E(\mathbf F_{q^n}) \to \mathrm{Jac}(H)(\mathbf F_q)
$$
When this can be achieved, we can use better algorithms to solve the discrete logarithm on $\mathrm{Jac}(H)(\mathbf F_q)$.
There are some limitations: for most curves $E$, the hyperelliptic curve produced has a high genus that makes algorithms much slower than on the elliptic curve.
Algebraic approach. Index calculs method brought a better than square-root complexity for the discrete logarithm on the multiplicative group of a finite field. The idea is to decomposed random elements over a factor basis, and with enough relations and linear algebra, the discrete logarithme is solved. For elliptic curves over an extension field $\mathbf F_{q^n}$, the factor basis can be defined as:
$$
\mathcal F = \{ P \in E(\mathbf F_{q^n}) \mid x(P)\in \mathbf F_q\}.
$$
Suppose $n=2$ and you want to decompose a point $R=(x_R, y_R)$ into two points of $\mathcal F$. There exist a polynomial $S_3$ such that if $S_3(x_1, x_2, x_3) = 0$, then there exists $P_1, P_2, P_3$ with $P_1 + P_2 + P_3 = \infty$. It can be used to solve the system
$$
\begin{array}{l}
S_3(x_1,x_2,x_R) = 0 \\
x_1, x_2 \in \mathcal F
\end{array}
$$
And $S_3$ can be viewed as $2$ polynomial equations over $\mathbf F_q$ and since $x_1$ and $x_2$ are already in the subfield, we have a polynomial system (non-linear, unfortunately) of $2$ equations and $2$ variables that can be solved by computing a Groebner basis. This can be generalized for bigger $n$.
This approach has lead to an algorithm of heuristic complexity $\tilde{O}(q^{2-2/n})$ which is faster than the square-root algorithm when $n\geq 3$. One drawback is that there is a constant $n!$ on the complexity.

You can find a survey from 2015, Recent progress on the elliptic curve discrete logarithmproblem that talks about the above and more.
Attemps have been made to apply the algebraic approach for curves over a prime field $\mathbf F_p$ but have failed (a factor basis that can be translated algebraically is harder to find without having a polynomial of high degree, which makes is very difficult to solve non-linear polynomial system).

To prevent the above attacks, it is recommanded to have a finite field of prime degree which is the case for most of binary standardized curves ($\mathbf F_{2^n}$ with $n$ prime), but not all, or use a curve defined over a prime field.


Soft question: Examples where lack of mathematical rigour cause security breaches?

The SSH protocol has a complicated record format with an encrypted message length, variable padding, encrypt-and-MAC, etc.  This complicated system, which was designed without any formal analysis relating the security of the system to the security of the building blocks, turned out to be vulnerable to an attack (paywall-free) exploiting the MAC verification as an oracle for information about the plaintext, leading to plaintext recovery attacks on SSH in popular implementations like OpenSSH.
The SSL/TLS protocols have a long and sordid history of informal design, leading to a multitude of attacks:

The Bleichenbacher RSAES-PKCS1-v1_5 padding oracle attack, which breaks an RSA-based encryption scheme designed without formal analysis, broke SSLv3 with RSA key agreement in 1998, and then broke it again in 2014 with the POODLE attack because of security-destroying protocol compatibility fallbacks, and then broke it again in 2018 with the ROBOT attack.
The BEAST attack, which had been noted by Phil Rogaway in 2002 and documented in theory for SSL/TLS in 2004, exploited the failure of SSL/TLS to follow the security contract of CBC which requires the IV to be unpredictable in advance for each message—the protocol had deployed CBC without formal analysis of how the IV is chosen.
The Lucky 13 attack (web site) recovers plaintext by using timing of padding verification as a CBC padding oracle, which arose from a CBC padding mechanism designed without even a simple-minded formal analysis of its timing characteristics.
The TLS renegotiation attack exploited a complicated state machine in the TLS protocol involving key renegotiation and authentication, which was never formally analyzed for its security properties, to forge messages sent to a TLS peer without its notice.

The OpenPGP protocol was designed by the ad hoc '90s-style composition of generic and poorly-understood public-key encryption and signature building blocks with no formal treatment for how they fit together.

The original promise of ‘Pretty Good Privacy’ was to keep email private.  But the method for combining fancy math primitives like RSA and standard symmetric cryptography like AES to encrypt long messages in OpenPGP was designed without formal analysis relating them to the security of the building blocks.

And it turned out this method was exploitable in practice in real email clients in an attack dubbed EFAIL that can leak message content (my answer on it).  It took a decade and a half after the problem was first reported in theory in 2002 for the OpenPGP world to catch up when an attack was published in practice in 2018.
A secondary promise of PGP was to prevent forgery in private email.
But there is no formal concept of a message from Alice to Bob—only of an encrypted message to Bob, and a signed message from Alice, nested however you please*…and usually nested in a way that Charlie can take a message Alice sent to him and make it look to Bob like Alice had sent it to Bob instead.  Alice can, of course, take the extra step to name the recipient in the message, and Bob can take the extra step to check for his name.  The software could also do this.  The OpenPGP designers could have tried to formalize the human-relevant interactions and analyzed their security properties—and could have designed the cryptography to support human use.

But, when confronted with the problem, instead the OpenPGP designers abdicated that responsibility by asserting that cryptography cannot solve the problem of appropriate use of technology.  To this day the OpenPGP protocol doesn't have a formal concept of a message from Alice to Bob—which could be implemented by standard well-understood public-key authenticated encryption—even though it is nominally intended for private email.
The public-key encryption and signature schemes chosen in OpenPGP were themselves designed without any formal analysis relating them to well-studied hard problems like the RSA problem or the discrete log problem, and it turned out that both the particular Elgamal signature scheme and RSA encryption scheme used by OpenPGP were problematic.

It is unclear to me whether these led to practical exploits on OpenPGP—except perhaps for the implementation error in GnuPG of using the same per-message secret for Elgamal signature and encryption, which illustrates the danger of proving a protocol secure without proving the code implements the protocol correctly.

These attacks are all on protocols that were designed by ad hoc engineering without formal analysis guaranteeing the security of the protocol relative to the security of its building blocks.  But the primitive building blocks—like $x^3 \bmod{pq}$, cubing modulo a product of secret primes; like $g^x \bmod p$, exponentiation of a standard base modulo a safe prime; like the AES-256 permutation family; like the Keccak permutation—don't have formal analysis guaranteeing their security relative to anything.  What gives?

The formal analysis or provable security for protocols, which consists of theorems relating security of a protocol to security of its building blocks, is only one part of a global sociological system for getting confidence in security of cryptography:

The reason we suspect the RSA problem is hard is that some of the smartest cryptanalysts on the planet have had strong motivation to study it for decades, and they have left a track record of decades of failure to find any way to break (say) RSA-2048 at cost less than $2^{100}$ per key.  The same goes for discrete logs in certain groups, for AES-256, etc.
The formal analysis of a protocol using RSA and AES enables the cryptanalysts to focus their effort so they don't have to waste time studying SSH, studying OpenPGP, studying SSLv3, studying TLS, studying WPA, etc., to find whether there's some way to break those protocols.  If the formal analysis is done well enough, the cryptanalysts can spend their effort on a small number of primitives, and the more effort they spend failing to break those primitives, the more confidence we have in the primitives and everything built on them.

Protocols like SSH, OpenPGP, SSL/TLS, etc., without formal analysis, are a colossal waste by society of the world's supply of cryptanalysts.  Formal analysis enables much more efficient use of the world's resources—and it would have paid off, because nearly all of the above attacks could have been caught just by studying the security properties of the protocols involved and the security contracts of the building blocks: CBC in TLS with predictable IVs, public-key encryption in PGP failing the IND-CCA standard, RSA-based encryption schemes in PGP and TLS without a reduction to RSA security, representing one's error responses in SSH and TLS as oracles for a chosen-ciphertext adversary.

Not all protocols are easy to formally analyze once designed—like the trainwreck that was TLS renegotiation—but protocols can be designed out of well-understood composable parts with clear security contracts to facilitate formal analysis, instead of ad hoc agglomerations of crypto gadgets like the '90s, and today there are tools like the Noise protocol framework with the Noise explorer to compose protocols with built-in formal analysis.

* Sometimes infinitely nested!


While the way that Robert showed can work if $e$ is small (and if $e \cdot d \equiv 1 \pmod{\phi(n)}$ (which is not necessarily true), there is a slightly more complicated method which will work in any case.

What we do is compute $\lambda = (e \cdot d - 1)/ 2^k$ odd (and $k$ is the integer that makes $\lambda$ odd.  The special property that $\lambda$ has is that $(m^\lambda)^{2^k} \equiv 1 \pmod{n}$ for any $m$ relatively prime to $n$.

Here's how we use it; we pick a random $m$, and compute $m^\lambda \mod n$.  If it is 1 or $n-1$, we go back and select another $m$.

If it is not, we repeatedly square the value ($\mod n$), and check if the value becomes 1 or $n-1$ (and because of $\lambda$'s property, it'll turn into one of the two in at most $k$ squarings, unless we happened to pick an $m$ which wasn't relatively prime to $n$); if the value became $n-1$, we go back, and pick another $m$.  However, if it became 1, that means that the immediately previous value $z$ had the property $z^2 \bmod n = 1$, that means that $gcd(n,z-1)$ and $gcd(n,z+1)$ are the factors of $n$.

And, at least 1/2 of the possible $m$ values will result in a factorization, hence this method is practical.


What does TLS_ECDHE_ECDSA_with_AES_128_CCM means collectively. What is the signature algorithm and keys used here?

TLS_ECDHE_ECDSA_with_AES_128_CCM

ECDHE: Key exchange with Ephemeral Elliptic Curve Diffie-Hellman
ECDSA: Signature with Elliptic Curve Digital Signature Algorithm
AES_128 : 128-bit Encryption with Advanced Encryption Standard
CCM: Mode of Operation with Counter with CBC-MAC which is an authenticated encryption algorithm designed to provide both authentication and confidentiality.

ECDHKE_ECDSA key exchange is performed as defined as in rfc4492 and the x-coordinate of the shared secret is applied to a KDF to derive the key. The same key both in AES and CCM.
CCM combines CTR mode of operation and CBC-MAC. It has an authenticate-then-encrypt authenticated encryption.  Firstly, the message tag $t$ is calculated on the message by CBC-MAC then the message and the tag are then encrypted using counter mode (CTR). In the above, the encryption is done by AES. CCM only defined for 128-bit block sizes.

The good

this scheme can work on a single key.
The encryption scheme is semantically secure under a chosen-plaintext attack.
The MAC function is unforgeable under a chosen message attack.

The bad:

Like any mode uses CTR internally (e.g. GCM) the (key,IV) pair reuse must not occur.

It is defined in rfc7251 with 4 ECC
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_128_CCM = {0xC0,0xAC}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_256_CCM = {0xC0,0xAD}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_128_CCM_8 = {0xC0,0xAE}
CipherSuite TLS_ECDHE_ECDSA_WITH_AES_256_CCM_8 = {0xC0,0xAF}

And it is mentioned that these cipher suites make use of the AEAD capability in TLS 1.2 RFC5246 in June 2014
The 8 means use eight-octet authentication tags and the default is 16 octets


What is the difference between a one-shot MPC protocol and a unbounded invocation of multiple MPC protocols?

Basically, there a many real-world problems where one might want to compute something on sensitive data several times.  Indeed, later in the paper you cite, the authors give several example, e.g.:

  "Medical Data: One may envision a huge database which contains the medical data of every patient in the US. To compute any global statistic on this data, one would not want to put complete trust in any single database. Instead, it is distributed to $n$ different databases. Each time they need to compute statistics on this data, they engage in an MPC protocol. As in the voting example, since these databases contain very sensitive information, an adversary may try to obtain this information via a leakage attack. Thus, to ensure security, the databases must run an MPC protocol that is secure
  against continual leakage."

The important words above are "each time".  It would not do much good to have a distributed database that was secure only the first time it was queried.


How does AEAD guarantee authenticated encryption and plain AES does not?

However, if data is encoded with a nonce that's clearly visible (one common implementation prepends the ciphertext with a nonce), then it is possible to replace the entire ciphertext with a previously valid ciphertext (since the nonce is known).

This is known as a 'replay attack', and is typically handled at a higher level.

One easy way is the TLS approach; it just keeps a record counter on both sides, and the counter (which increments for each record) is included with the AAD.  If someone were to replay the record, the counter of the original encryptor (which was at some original value) and the counter of the decryptor (which would be at some larger value) would not be the same, and hence the integrity check would fail.

Another approach is the DTLS and IPsec approach; they don't assume a reliable transport (packets sent by one side might not make it to the receiver, or packets might be received out of order), hence counters on the two sides would not necessarily be synced.  Hence, what the do is have the encryptor keep a counter, which is explicitly sent in the packet (and which is included in the AAD).  Then, the receiver checks the counter to see if it's one it has seen before; if so, it rejects the packet.  This protects against replay attacks; if the attacker replays the packet with the original counter value, then the packet will be rejected by the above logic; if it adjusts the counter, then the GCM integrity check will fail.

Of course, there are other possible strategies; these are just two which are used in practice.

  Suppose you have AES-256-CBC encrypted blocks of data, each encrypted with a proper nonce (no collisions). How is it less safe and non-authenticated compared to the same blocks of data, but encrypted with AES-256-GCM?

I just showed you how GCM can protect against replay attacks; there are also message-reordering attacks which the higher level protocol needs to protect against.  GCM itself protects you against other attacks which modify a message to something that the valid encryptor hasn't produced.  On constrast, CBC mode does not; the attacker can do a number of modifications of CBC-encrypted messages without being detected (unless you also include some sort of MAC, which anyone sane would)


Construction of a "simple", nothing-up-my-sleeves, provably KPA resistant symmetric cipher

With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA.

Any scheme that has a message space larger than the key space and is unconditionally provably resistant against known-plaintext attacks while being efficiently computable immediately implies $P\neq NP$. As we don't know for sure whether $P\neq NP$ holds and this having been a famously tricky question to answer it seems like it is really hard to build such a cipher.
However if you're willing to make assumptions, we know provably secure constructions. The issue with that is though that most of these assumptions and constructions lead to ciphers that offer no real security advantage over a heuristically well-designed cipher like AES while being much much slower.

When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation.

While this may look to be the case at first glance, the design of AES was very considerate. If you wish to learn more about this topic I suggest you read the book on why AES looks the way it does: "The Design of Rijndael" by Rijndael and Daemen.


Time complexity to solve Discrete log problem

These days the fastest general method to solve discrete logarithms modulo primes is the number field sieve, which has the asymptotic complexity

$$
e^{(1.92+o(1)) (\log p)^{1/3} (\log\log p)^{2/3}}
$$


That's a bit of a strange question. ECDH is a key agreement protool. ECC does not have a direct form of encryption as RSA has. ECIES is basically ECDH used to derive a symmetric key, which is then used to encrypt the plaintext. You can see it as a delayed form of key agreement.
So your question is if ECIES can be used to encrypt session keys. That would come down to performing ECDH to derive a data key, and then using that data key to encrypt a session key. Yes, it is probably secure, but directly deriving a session key using ECDH is a lot easier. Using ECIES is only useful if - for some reason or other - authenticated DH key establishment cannot be integrated into a protocol.
For more information about using ECIES & ECDH for authentication, please see this other question.


Is a key ratchet effective against replay attacks?

Yes, a ratchet is an effective way of preventing replay attacks.
For example, the Signal Protocol does this (for reasons other than replay protection), and it is stated in a blog post that the replay protection "comes for free".

Since your transport protocol can lose messages, I would assume it also does not guarantee the ordering, so you will have to store some skipped keys. In fact, the Signal Protocol I just mentioned still sends a counter for this bookkeeping reason as you can see in the actual specification. You will have to decide if trying the skipped keys in order is computationally feasible. This issue is related to the first attack scenario described in the first answer of the question you linked: an attacker who can hold back messages and replay them at a later time would still be successful.

If you do not authenticate your messages, this scheme also enables DoS attacks - an attacker simply has to send enough messages to fill up the buffer of stored keys, and you will not be able to decrypt legitimate messages. While this prevents an attacker from using garbage data as keys, he can still use old messages with legitimate keys for this purpose. The result is that you have to keep track of old keys as well, add a counter, or invalidate old authentication tags by e.g. also evolving the key material used for signing.


How to decrypt Rabin message when p=q and you have the roots from Tonelli-Shanks

We are given $n>4$ and ciphertext $c\in(0,n)$ for textbook Rabin encryption. We want to solve for $x\in[0,n)$ the equation $x^2\bmod n=c$.  We found that $n$ is a square, computed $p=\sqrt n$, found that it is prime, solved $y^2\bmod p=c\bmod p$ yielding two roots $y_0\in(0,p/2)$ and $y_1=p-y_0$, and now want the solutions for the original equation.
Every $x\in[0,n)$ can be uniquely written as $x=y+z\,p$ with $y\in[0,p)$ and $z\in[0,p)$.
If $x=y+z\,p$ is a solution of $x^2\equiv c\pmod{p^2}$, then that also yield modulo $p$ since $p$ divides $p^2$, thus $y^2\equiv c\pmod p$, thus our earlier work did yield the possible values of $y$.
Now $(y+z\,p)^2\equiv c\pmod{p^2}$ becomes $y^2+2\,y\,z\,p\equiv c\pmod{p^2}$, that is
$2\,y\,z\,p\equiv c-y^2\pmod{p^2}$, that is
$\exists k\in\mathbb Z,\,2\,y\,z\,p+k\,p^2=c-y^2$, that is
$\exists k\in\mathbb Z,\,2\,y\,z+k\,p=(c-y^2)/p$, that is
$c-y^2$ is divisible by $p$ and $2\,y\,z\equiv(c-y^2)/p\pmod p$, that is
$c-y^2$ is divisible by $p$ and $z\equiv(2\,y)^{-1}\,((c-y^2)/p)\pmod p$
Thus we check that $c-{y_0}^2\bmod p=0$ (which must hold unless we goofed in computing $y_0$),
compute $b_0=(c-{y_0}^2)/p\bmod p$, then $z_0=(2\,y_0)^{-1}\,b_0\bmod p$,
then $x_0=y_0+z_0\,p$, and that's one solution. It can't be zero. The other is $x_1=p^2-x_0$.


Why is a certificate needed at client side

I think you are confusing something in the mbedTLS ssl_client1 example. The example does not specifiy the server certificate, but the CA (Certificate Authority) certificate. The client loads the CA certificate into its CA chain. Later on it still requests the certificate from the server (ssl_handshake step) and uses the public key inside the CA certificate to verify the certificate it received from the server.


Which element produces randomness in symmetric block ciphers encryption

“Random” is a complicated concept and this question does not have a one-word answer.

The ciphertext is not random, in the sense that it's possible to relate it to the plaintext. Just decrypt and compare. The ciphertext is constructed deterministically from the plaintext, the key, the IV and the message.

The ciphertext appears random to someone who doesn't know the key and has plausible computational power. (Someone who has effectively infinite computational power can try all possible keys.) This is a definitional property of encryption schemes.

The block cipher algorithm (e.g. AES or DES), the chaining mode (e.g. CBR or CTR), the key and the IV all contribute to this randomness in their own way.

The key, of course, is where the randomness starts. It's directly extracted from an entropy source. It's the one element that absolutely needs to be random in the sense that an adversary has no knowledge of the key beyond its format (for symmetric encryption, an array of bits of known length).
The block cipher, given a key, makes the encryption of a plaintext block look random. That is, to someone who doesn't know the key, the block cipher acts like a random permutation — it always transforms the same input into the same output, but the outputs for distinct inputs are not related in any visible way. The job of the block cipher is to transform the “raw” randomness of the key into a structured randomness: a random-looking permutation function.
The chaining mode extends this randomness to multiple blocks. The encryption of each block may look random, but when you consider multiple blocks together, the combination is not random if there is correlation between the blocks. The job of the chaining mode is to break any correlation. This is where ECB fails: all blocks undergo exactly the same transformation. CBC and other feedback modes break the correlation by inserting a step of the block cipher between each block. CTR breaks the correlation by using different inputs for each block. In all cases the chaining mode leverages the block cipher's decorrelating action from the block level to the message level.
The IV extends this randomness to multiple messages. The encryption of a single message may look random, but the same transformation of the same plaintext would result in the same ciphertext. The job of the IV is to ensure that there is no correlation between any two uses of the same key. The chaining mode uses the IV to leverage the block cipher's decorrelating action from the message level to the multiple-message level.


What is sent on the initial communication with Kerberos?

If you look at RFC 1510, (an overview and specification of Version 5 of the Kerberos network authentication system), the initial exchange involves the client (Bob) sending its own identity, and the identity of the server (Alice) for which it is requesting credentials in cleartext.  The response contains a ticket for the client to present to the server, and a session key that will be shared by the client and server.  The session key and additional information are encrypted using the client's secret key (which is stored on the Authentication Server).

The request message contains the client's principal name as well as the server's principal name, the time and a nonce to prevent replays.  The reply message contains information which can be used to detect replays, and to associate it with the message to which it replies.

In the normal case, the authentication server does not know whether or not the client is actually the principal named in the request.  It simply sends a reply without knowing or caring whether or not they are the same.  This is acceptable since nobody but the requesting principal (client) will be able to decode the reply.

For further information, have a look at Section 3 - Message Exchange of RFC 1510.


What is the MD5 collision with the smallest input values?

To answer your question, we must first state that for an integer $x$, we define MD5($x$) to be the MD5 hash of the encoding of $x$ as a sequence of bits. Indeed, MD5 expects a sequence of bits as input, not an integer. We should choose a conventional encoding; I select big-endian. Thus, integer $44$ encodes as a sequence of 6 bits: 101100. One may note that by doing so, I miss on half of possible MD5 inputs: indeed, when converting an integer to its minimal-length big-endian unsigned encoding, the first bit is always a '1'.

Though the encoding is not important for the discussion below, it impacts the value of $b$ that you are looking for. Indeed, each encoding will yield another $b$.

Since MD5 has a $128$-bit output, it can have (at most) $2^{128}$ distinct outputs. If I take the integers $0$ to $2^{128}$ (inclusive), then I have $2^{128}+1$: it is thus mathematically guaranteed that at least two of them hash to the same value. In other words, it is proven that there exist integer values $a$ and $b$ such that $0 \leq a < b \leq 2^{128}$ and MD5($a$) = MD5($b$).

The actual minimal value of $b$ is not known. However, it is expected that the minimal $b$ is around $2^{64}$. This comes from the so-called birthday problem: if I take at random $n$ value within a set of size $N$, then I will pick one that I already picked previously when $n$ reached $\sqrt{N}$ or so.

To obtain $b$, one would have to, indeed, generate MD5($x$) for all values of $x$, beginning with $0$, until we get a value that we already had. The expected cost for the MD5 is high: $2^{64}$ is within reach of technology, but not of a home computer. On a quad-core x86, one may expect about $2^{26}$ MD5 evaluations per second; with a good GPU, you could reach $2^{33}$ per second (this guy claims a bit more than $2^{36}$, but that's with 8 GPU). You'd still need about 60 years to reach $2^{64}$. Another issue, which may become quite a problem in the long run, is how to detect that you did obtain twice the same hash output: $2^{64}$ 16-byte results will not fit in RAM... In fact, this search problem is likely to be a bigger issue than just computing all the MD5.

(There are nifty collision-search algorithms which need very little RAM, but I am not sure they could be applied to the exact problem you stated, in which you do not look for just a collision, but for the minimal $b$ value.)


Plaintext for randomness evaluation of cryptographic algorithms?

If I understand you properly, you are going to test some cryptographical primitives by running them on some plaintext, and then taking the resulting ciphertext and giving it to a randomness test suite; your question is "what plaintext should I use?  If I pick a random plaintext, then the test results might reflect the randomness of the plaintext, and no anything the cipher is doing"

In which case, you want to select a maximally nonrandom plaintext.  For example, if you're testing CBC-mode encryption, a plaintext that consists of a long string of 0's would work; if you're testing a hash function (and so need a long series of plaintexts), using plaintexts of the form "0", "1", "2", "3", etc (for some simple encoding of those integers, say, in binary form) would work.

That said, unless the cryptographical algorithms you're testing are severely broken, you're not going to find anything.  An explicit design goal as that an attacker who can submit plaintexts of his choosing is unable to distinguish the output from randomness; it is quite unlikely that something as mindless as the NIST test suite would manage where a clever cryptanalyst cannot.


The aspects regarding IV has already addressed @Maarten - reinstate Monica. There are some more issues.

1) If you store encrypted data in cookies once for all future requests, then it will not work, because many users clean cookies and local storage regularly. Some do that manually, some use add-ons that clean up cookies and local storage on browser exit or every 2-3 hours. Some users cannot even control that, because in serious companies users have no admin permissions and usage of such add-ons is just enforced.

2) If you set encrypted data to cookies each time for login purpose, then cleaning cookies doesn't break your solution. But if an attacker stole the key database, then he can easily decrypt whatever your send him during login.

3) The idea that user should prove he knows the key without sending this key to the server is good. But it is good only if user obtains the key via some channel other than channel used later on for authentication. Where as you want to transfer key via the same channel (same HTTPS connection) as later on authentication/decryption request. Thus you don't have more security. This would be more complexity without any additional security. I would discourage you from doing that.


Lightweight Asymmetric encryption algorithm

When an embedded device needs asymmetric crypto to encrypt, (e.g. measurements it makes) or check authenticity (e.g. of commands or firmware updates it receives), there is no need for a private key or key generation in the device, and nothing beats RSA and Rabin on simplicity and speed (for RSA: with $e=3$, which is safe when used with proper padding); plus RSA and Rabin are well known, and patent-free. In these applications, RSA and Rabin main drawbacks are that cryptograms are at least the size of the private key (e.g. 256 bytes for 2048-bit RSA); however only a fraction of that needs to be overhead not conveying actual data (e.g. 66 bytes for RSA-OAEP with SHA-256).

When and if a device needs a private key (see final note), Elliptic Curve Crypto (e.g. ECDSA, ed25519) has many advantages, including very easy key generation, significantly faster computations for the private-key operation (e.g. signature generation), smaller keys, and smaller minimum size of cryptograms. But there is debate about if some particular implementations are patent-encumbered in some jurisdictions, or not.

On the RSA vs ECC debate: RSA private-key (except perhaps its key generation) can be made fast, using dedicated hardware, as used in many Smart Cards. Dedicated hardware is also used in all modern Common-Criteria security-certified embedded devices using ECC that I am aware of, thus if ECC might allow to do without the burden of dedicated hardware in some contexts, that's uncommon in such security-certified devices.

NTRU can also be considered, but is alleged to be patent-encumbered in some jurisdictions, and is a relatively recent player, thus is of less recognized security, in no FIPS standard, nor endorsed by ANSSI (French) or BSI (German). In particular the signature part of it (NTRUSign) was broken in 2006 (Phong Q. Nguyen and Oded Regev, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, in Journal of Cryptology, 2009; preliminary version in proceedings of Eurocrypt 2006); and the break and fix cycle on NTRUSign has hardly stabilized (Léo Ducas and Phong Q. Nguyen, Learning a Zonotope and More: Cryptanalysis of NTRUSign countermeasures, in proceedings of AsiaCrypt 2012).

Note: having a private key in a device is useful only when some of the other entities that have to authenticate such device, or send it confidential data, can not be trusted to hold and properly use a common secret key. If all such other entities can be trusted, symmetric crypto with device-unique diversified keys (derived from a master key and device serial number) can be made functionally equivalent to full-blown asymmetric crypto everywhere (when combined with asymmetric crypto, restricted to public-key operation on the devices, to authenticate said other entities, and encipher to them); that solution is much simpler and faster on the device side.


Is the IV value in Davies Meyer construction public?

Is that value $H_0$ public?

Well, one property that a hash function has is that anyone can evaluate it.  To evaluate a Davies-Mayer hash, you need the value $H_0$, and so yes, it needs to be public.

  I think that is necessary to complete with zeros until complete 64 bits...

Minor correction there: while Davies-Mayer requires us to pad the message so that it is an even multiple of block sizes long (64 bits in your toy example), we wouldn't want to append zeros.  The reason is that we hope that the hash function is collision-resistant (that is, someone couldn't find two different messages that hash to the same value); with the pad-by-appending-0's method, what someone could do is take a message, and append a 0 bit; as long as the original message wasn't a multiple of 64 bits, then the post-padded versions of the two messages would be identical, and so the hashes would be identical.  What we could do instead is either append a '10000...000' pattern, or append a pattern that includes the original text length.  Actually, common hash functions that are based on Davies-Mayer (SHA-1, SHA-2) do both.

  In this case it is easy to retrieve $m_0$ because the plaintext and the ciphertext are known

First, a minor correction: the concern is not that we keep the message secret, but instead that it should be infeasible to find preimages; that is, given a hash value, it should be infeasible to find a message that hashes to that hash value (and it doesn't matter if the message that the attacker finds is the same message that was originally hashed).

In any case, no, it is not easy to find a value $m_0$, if we assume that $E$ is a strong block cipher.  With strong block ciphers, we make the assumption that, given a plaintext/ciphertext pair, we cannot recover the key.  This implies that there isn't a direct way to immediately recover $m_0$.

Of course, with the parameters that you give (32 bit block size), what an attacker could do is try $2^{32}$ different $m_0$ candidates; if he hashes all those values, he is likely to find one that hashes to the $H_1$ value.  Because of this, Davies-Mayer requires us to use block ciphers with much larger block sizes.


Is using a predictable IV with CFB mode safe or not?

Thomas is correct; there's no attack on CFB mode if you can predict the IV; NIST is just being cautious.

With CBC, the value of the first encrypted block $C_0 = E_k( IV \oplus P_0)$, where $IV$ is the IV used for that packet, $P_0$ is the value of the first plaintext block, and $E_k$ is the evaluation of the block cipher.

If an attacker can predict the value of the $IV$ in advance, and can influence the value $P_0$, then he can get the value $E_k(Q)$, for any value $Q$.  Here is how; he learns the value of $IV$, and then injects a message whose first plaintext value $P_0 = IV \oplus Q$.  The encryptor will generate an encrypted message whose first block is $C_o = E_k( IV \oplus P_0 ) = E_k( Q )$.

Using this encryption oracle, the attacker can verify guesses on the possible decryption of previous messages.

In contrast, with CFB mode, the first encrypted block is $C_0 = E_k(IV) \oplus P_0$.  While this looks similar, there is no similar opportunity to an attacker to select the block that is presented to the block cipher.  If the attacker knows the IV in advance, all he knows the value of the first block that will be presented to the block cipher; he cannot influence it by selecting any specific value for the first plaintext block.  Now, if the attacker can control the value of the IV, then yes, he can use that directly to create an encryption oracle; he generally don't allow the attacker to do that.

In addition, if we use the same IV repeatedly, then there is also a weakness (beyond the rather obvious leaking of the first block); the second ciphertext block is $C_1 = E_k( E_k(IV) \oplus P_0 ) \oplus P_1$; if $IV$ is constant, so is $E_k(IV)$, and so the attacker can select messages with $P_0 = E_k(IV) \oplus Q$, also creating an encryption oracle.

The bottom line: predictable IVs are safe in CFB mode, as long as they don't repeat, and you don't allow the attacker to pick them.


It's actually fairly easy to factor $n$ given $e$ and $d$.  Here's the standard way to do this:

Compute $f = ed - 1$.  What's interesting about $f$ is that $x^f \equiv 1\  (\bmod n)$ for (almost) any $x$.
Write $f$ as $2^s g$ for an odd value $g$.
Select a random value $a$, and compute $b = a^g \bmod n$.
If $b = 1 $ or $-1$, then go back and select another random value of $a$
Repeatedly (in practice, up to $s$ times):

compute $c = b^2 \bmod n$.
If $c = 1$ then the factors for $n$ are $gcd(n, b-1)$ and $gcd(n, b+1)$
If $c = -1$, then go back and select another random value of $a$
Otherwise, set $b = c$, and go through another iteration of the loop.

If you are familiar with the Miller-Rabin primality test, this will look familiar; the logic is the same (except that we use $ed-1$ rather than $n-1$ as the startign place for the exponent)


How can we implement a PRF with 1bit input space and 1024bit output space using AES securely?

It is secure. There would be an issue if that you generalize the idea to ridiculously long outputs. Any time you use two distinct inputs with a PRP using the same key, the outputs will necessarily be different. But for an ideal PRF there is a tiny chance that different 128-bit blocks could share the same value.

Because you only have 8 blocks, though, you wouldn't actually see duplicate blocks from an ideal black box PRF in practice. As a rule of thumb, you would not expect to see any duplicates until you look at around $2^{64}$ blocks. (See the "birthday paradox" and switching lemma.)

I'd discourage someone from doing anything more complicated with AES to mask that potential artifact. ECB encrypting the blocks with values 0 through 7, if the input is 0, or the values 8-15, if the input is 1, would be sufficient.

A variable nonce isn't actually needed. You can just use a constant, such as zero.

Alternatively you could replace AES with a (non-block-cipher) PRF. HMAC or ChaCha20, for example.