Problem with Hash-DRBG's seedlen values (and others)

440 and 888 are the maximal values of seed length, that, when concatenated with 1 octet, yields a input to SHA256 and SHA512 respectively, requiring only 1 invocation of the compression function.

These values are fixed in such way that, it precludes the use of other hash functions, even ones approved as SHA3.

However, if one wants, the above rule can be used to derive seedlen for other hash functions, although, this would have no official document backing it.

For example, the minimal padding length in all SHA3 functions (when used in byte-oriented environment), is 1 byte, so seedlen for SHA3 functions is

$$ 1600-\mathit{capacity}-16 $$

Also, there's problem with Hash-DRBG that's missed in the publication.

The document states that the hash function used should be "one-way", but in reality, to obtain secure DRBG instances, the underlaying primitive have to behave random, or else, distinguish attacks will be possible.


It's simply not secure.  Sure, it "works", in the sense that you can generate shares and reconstruct the secret from a sufficient number of them, but the essential security property of Shamir's secret sharing — namely, that knowing less than the required threshold number of shares reveals no information about the secret — does not hold.

Since it's easier to understand why this is the case if you actually see it happen, let me give an example.  To keep the example simple, let's assume that you're sharing the secret $S \in \mathbb R$ among two people, and want to require both of those two shares to reconstruct it.

So, since the reconstruction threshold is two, you need to choose one random number $a_1 \in \mathbb R$ and evaluate the polynomial $p(x) = S + r x$ at two non-zero points $x_1, x_2 \in \mathbb R \setminus \{0\}$.  The shares are then $y_1 = p(x_1) = S + rx_1$ and $y_2 = p(x_2) = S + rx_2$, and the secret can be reconstructed from them by linearly interpolating between the points $(x_1,y_1)$ and $(x_2,y_2)$ and taking the constant term of the resulting interpolation polynomial.

Now, so far so good.  But let's say that I know $y_1$ but not $y_2$.  Then, if I guess a value for the secret $S$, I can calculate the unique random value $r = (y_1-S)/x_1$ that gives me the share $y_1$, assuming that $S$ has the value I guessed.

Now, let's say (again for simplicity) that I'm sure that either $S = S_1$ or $S = S_2$ for some specific values $S_1$ and $S_2$.  Thus, I know that $r$ equals either $r_1 = (y_1-S_1)/x_1$ or $r_2 = (y_1-S_2)/x_1$.

Furthermore, let's say that, a priori, I believe that $S = S_1$ with probability $\mathrm{Pr}[S = S_1] = p_0$, and thus $S = S_2$ with probability $1-p_0$.
Now, using Bayes' rule, I can calculate the conditional probability $p^*$ that $S = S_1$ given that I have the share $y_1$ as:

$$\begin{aligned}
p^*
&= \mathrm{Pr}[S = S_1 \mid y_1]
= \frac{\mathrm{Pr}[y_1 \mid S = S_1]}{\mathrm{Pr}[y_1]} \mathrm{Pr}[S = S_1] \\
&= \frac{\mathrm{Pr}[r = r_1]}{\mathrm{Pr}[y_1]} p_0
= \frac{\pi(r_1)}{\mathrm{Pr}[y_1]} p_0\\
\end{aligned}$$

where $\pi(r)$ denotes the probability that you picked the random number $r$, and the denominator $\mathrm{Pr}[y_1] =$ $\pi(r_1)\, p_0 +$ $\pi(r_2)\, (1-p_0)$ is just a normalization constant that ensures that the conditional probabilities $\mathrm{Pr}[S = S_1 \mid y_1]$ and $\mathrm{Pr}[S = S_2 \mid y_1]$ sum to one.

Now, in general, $p^* = p_0$ if and only if the probability distribution $\pi$ is uniform, i.e. if every random number $r$ is equally likely to be picked.  In this case, knowing $y_1$ gives me no additional information about $S$.  When Shamir's secret sharing is implemented over a finite field, this is (or should be, if the implementation is correct) the case.

Conversely, if the probability distribution $\pi$ is not uniform (i.e. if some values of $r$ are more likely to be picked than others), then I can learn some information about $S$ just by knowing my own share $y_1$.  In particular, if $\pi$ is not uniform, then there will always be some pairs of possible secrets $S_1$ and $S_2$ such that $\pi(r_1) \ne \pi(r_2)$, and so $p^* \ne p_0$.

OK, you say, so just make $\pi$ uniform, then.  The problem, however, is that there is no uniform distribution over the real numbers, so any choice of random numbers necessarily leaks some information about the secret.

That issue — the need to pick uniform random numbers over the field we're working in — is the real reason why Shamir's secret sharing requires a finite field.


Decrypt affine cipher given encryption key

Your formulas are wrong. If $$c \equiv 7p + 11 \mod{27}$$ then by applying the modular arithmetic function $$c - 11 \equiv 7 p  \mod{27}$$ and then $$(c - 11) \times 7^{-1} \equiv p  \mod{27}$$.

Therefore, the decryption function is:
$$p \equiv (c - 11) \times 7^{-1} \mod{27}$$

For this we need to compute de multiplicative inverse of 7 modulo 27. Since they are coprime number, this inverse exists. And we can compute it using the Euler totient method like this:

$$7 ^{-1} \equiv 7 ^{\phi(27) -1}  \mod{27}$$

$$\phi(27) = 27 \times (1 - \frac{1}{3}) = 18$$
then
$$ 7^{-1} \equiv 7^{17} \equiv 4  \mod{27}$$

Finally the decode function is :

$$p \equiv (c - 11) \times 4$$

For your example:

$$(18 - 11) \times 4 \equiv 7 \times 4 \equiv 28 \equiv 1  \mod{27}$$


Difference between MAC and Authenticated Encryption?

A mac is basically applied after encryption is totally complete, where "authenticated encryption" usually refers to something like a mode of operation that builds an authentication tag as the process of encryption moves along. The goal of the "authenticated encryption" is basically doing the same job as a mac in less passes/applications of crypto primitives.

Examples of "authenticated encryption" include GCM mode and the duplex mode offered by the sponge construction. Using either of these will produce an authentication tag with the ciphertext. If data was encrypted using either of these, then application of HMAC after encryption is not necessary.

Suppose a mode of operation like CBC was used instead. It does not produce an authentication tag, and in order to assure integrity and authentication we would require the application of HMAC. This must wait until after encryption was complete. Because this is essentially two totally separate operations, it is relatively slow compared to GCM mode.


We have $d = e^{-1} \pmod{ \phi(N) }$, this implies that $m = c ^ d \pmod{N}$


Is there a cryptographic scheme that allows joint encryption using a shared secret?

The common procedure for what's asked is to draw a random key $S$, use it to encipher the plaintext using a symmetric cipher such as AES-CTR, then split the key into so-called key shares per a threshold scheme, so that $k=2$ shares out of $n=3$ are required to reconstruct the key. A generic $(k,n)$ threshold scheme is Shamir Secret Sharing.

Here is a very simple $(2,3)$ threshold scheme: each bit $x$ of the key is splits into three shares values $a$, $b$, $c$. Share value $a$ is chosen uniformly at random among $\{0,1,2\}$, then the other two are determined as $b=(a+x)\bmod3$, $c=(b+x)\bmod3$ (where $\bmod3$ designates subtracting $3$ from the result if it is $3$ or more). For decoding, if any two share values among $a$, $b$, $c$ are equal, then the corresponding key bit $x$ was $0$; otherwise it was $1$. Demonstrably, a single share gives no clue about the key. See this question for schemes still workable by hand and giving a slightly more compact encoding.

As pointed in comment, this has the drawback that who/whatever draws, uses and/or splits $S$ could be dishonest, keep $S$, and decipher the plaintext.


A secret-sharing scheme allows you to distribute a secret message among multiple parties. However, a fundamental question is how this message is represented. In many SS schemes, this message is an integer between $0$ and some maximum value $M-1$ (for unsigned values), and whenever you add secret-shared values, the addition happens modulo $M$.
Addition modulo a number is not very useful in applications, so one typically considers secret to be much smaller than the modulus in the scheme so that wrap-arounds do not occur. This is what happens in your example when you propose a large prime modulus and a much smaller size for the actual data.
However, what you have to understand here is that this difference in the sizes of the data and the modulus exists only to enable some applications, but the actual MPC protocol doesn't care about the sizes of the underlying data: It just assumes it is smaller than the modulus. This is very similar to programming: If you use data types that are 64-bits long, any wrap-around modulo $2^{64}$ when adding variables is the programmer's fault, since the program doesn't really care about this.
Given this, and to answer your concrete question, protocols usually consider the computation to be defined over certain domain, like integers modulo a prime $p$, and they don't really care about what data is fed to them. In particular, whenever you see something like "sample a random value", it typically means random in the whole domain, that is, random between $0$ and $p-1$ (for unsigned, although this is irrelevant). For the case of triples, this has to be the case, since these random values are used to mask the inputs to the multiplication gates, so they have to be chosen uniformly at random in the whole domain so that the reconstructed value leaks nothing about the sensitive inputs.


Is rubberhose cryptanalysis a sidechannel - formally?

Yes. A human surely is a physical component of the cryptosystem. Even if we ignore the "physical" aspect, we have

  implementation of a cryptosystem, other than brute force or theoretical weaknesses in the algorithms.

If a key is not secure (ie. in the mind of a human who can be persuaded to divulge it), acquiring this password and bypassing the crypto would be a side-channel attack IMO.


How can Alice prove that a message has not been tampered with?

There are two parts here, and not just one message to Bob.  Alice's authorization should be viewed as a packet within a packet.  This is often referred to as a token.  The message from Alice to Bob may be email, but the token is a cryptographic value.  Bob can't decrypt the token and play with it, because Bob doesn't have the keys needed.

The permissions Alice is granting are not intended to go to Bob as the final recipient.  She isn't telling Bob "you have read access to the database."  She is telling an authorizing system "Alice is granting Bob read access to the database."  So Alice needs to securely communicate her intent to the authorizing service.  In your scenario you describe Bob as seeking Alice's approval, and she replies to him with a message.  But Bob is responsible only for receiving the token from Alice and delivering the token to someone else.  He might forward it on to the authorizing system, or he might pass it along to the database (who would pass it to the authorizer.)

Think of Bob not as the recipient of the token, but as Eve (the eavesdropper) or Mallory (the malicious attacker) standing between Alice and the authorization system.  The token has to be secured against Bob's tampering.  When done right, it doesn't matter if those messages are seen by Bob as they flow through his hands.

See Kerberos for an example of a security system that behaves as you describe.


Are there historical examples of Occam's Razor being useful to cryptography research?

The definition you cite says that "among competing hypotheses, the one with the fewest assumptions should be selected". If you take this literally and don't understand fewer assumptions as simpler, this principle is widely accepted in cryptographic research: Having a provably secure scheme means that it can be shown to satisfy some security definition under certain assumptions. If you propose a new scheme and prove its security under weaker (or less) assumptions than what was needed for previous schemes, this is considered to be a substantial contribution.

As an example, consider RSA. A necessary assumption for RSA to be secure is that factoring is hard. However, nobody has succeeded so far in proving that under that assumption, RSA is actually secure. There exist security proofs for (variants of) RSA, but they require additional assumptions. At Eurocrypt 2009, a paper [1] received the best paper award for proposing an encryption scheme that is provably secure assuming only that factoring is hard. That scheme is not simpler than RSA, but the hypothesis that it is secure can be based on fewer assumptions.

[1] Dennis Hofheinz, Eike Kiltz: Practical Chosen Ciphertext Secure Encryption from Factoring. EUROCRYPT 2009.


Attack on a key-exchange,symmetric-key cryptography protocol

I'm not sure but in my point of view.

Since $k_{AB}$ is used to authenticate both side.
Mapped $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pair on one side can be used on both side.
Thus we can gather $nounce_x:E_{k_{AB}}$$(nonce_x∥k_x)$ pairs from $B$ since $B$ will happily echo $E_{k_{AB}}$$(nonce_x∥k_x)$ for every $nounce_x$ I asked.

This doesn't form practical MITM attack but I can make $A$ agree on $randomK_1⊕k_2$ as $k_s$ while on the other side $B$ will accept $k_1⊕k_2$ as $k_s$. In another word we can make $A$ and $B$ agree on different values at probability equivalent to (or more than because we can query it ourself) birthday attack.

This might make some cryptanalysis possible but I don't know the details.

As you suggested in chat:
$nonce$ collision is unnecessary we rather change the scheme to something like:
After received $nonce_A$ we send it to $B$ twice but only sent the first response to $A$


Are EC public key values evenly distributed?

Yes, the coordinates are more or less evenly distributed, between 0 and the order of the curve (exclusive). The Certicom curves such as secp256r1 generally have an order very near the maximum of the bit size, e.g. the secp256r1 curve has the following order $n$:

FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551

So that means that there is about one in 256 chances that the first byte is completely zero for each coordinate.

This is slightly different for e.g. Brainpool curves as the order is randomly chosen (for the correct bit size, of course) and thus lower, brainpoolP256r1 has for instance the following prime order $q$ (same thing, different name):

A9FB57DB A1EEA9BC 3E660A90 9D838D71 8C397AA3 B561A6F7 901E0E82 974856A7

so the chances are slightly higher for brainpool curves that the first byte is fully zero (slightly lower than one in A9 of course, so about 1 in 169).

It gets even more "funny", as I've seen implementations fix this by making sure that the leftmost byte is set to 00 if it is missing, in case constant size X and Y coordinates are required. Of course, that fails if the first two bytes are set to zero, with a much smaller but non-negligible chance. The chance of it starting with 16 bytes of zero are of course negligible, but otherwise you'd better make sure.

A donkey doesn't stumble over the same stone twice, as we say in the Netherlands (A fox is not caught twice in the same snare.)

You can have the same fun with EC private keys or RSA private keys, by the way. The RSA specification lists how to create constant size, unsigned, big endian values that you require in the definition of the I2OSP (Integer to Octet String Primitive) definition.

Note that that definition is a rather mathematical way of saying that you need to prefix enough zero bytes. I've seen a crypto professor implement it using big integer arithmetic. This is definitely not required. It is just a formal description how it commonly looks in computer memory if you encode the value correctly. For more info, see my answers here on crypto and the implemention on SO for Java (shameless plugs, sorry 'bout that).

P.S. The chance of either coordinate starting with a zero byte is about $1 - {({255 \over 256})^2}$. That's ever so slightly lower than $1 \over 128$, but $1 \over 128$ is a good ballpark figure I guess.


why do we asume that in the registration process communication is over the secure channel?

Registration phase/process it is always assumed that communication is
  over the secure/private channel, whereas, all of the phases
  communication is happening over the public/open channel. What is the
  reason for this?

Well, the point of the registration phase is to register the client to the server, so that they can reach mutual authentication afterwards using the exchanged information and with minimal / no assumptions on the underlying channel.

If you assume the channel to be insecure for this process, what an attacker can do, is wait for you to enter the registration phase with the legitimate server, intercept the request, act like they are the legitimate server and at the same time register themselves to the real server.

Now if you connect after the registration stage, the attacker can perfectly fine be authenticated as "the real server" and intercept your entire traffic (and potentially forward it to the real server).


Minimum distance between polynomials in ring-LWE

I'm assuming $n$ is a power of $2$ and that $q$ is an odd prime larger than $n$. I'm discarding the trivial case $s_1 = s_2$.

If you consider everything $\mod q$, then it is most likely over the choice of $a$ that there exists $s_1 \neq s_2$ such that $\|a s_1 - a s_2\| = \sqrt{n}$. Indeed, $a$ is invertible in $R_q$ with probability about $1 - n/q$. Take $s_2 = s_1 - a^{-1}$, then you have $a s_1 - a s_2 = 1 \mod q$ and the embedding norm of $1$ is $\sqrt{n}$.

If you do not consider this $\mod q$, i.e. you work in $R=\mathbb Z[x]/⟨f(x)⟩$, then you are precisely asking for the minimal distance $\lambda_1(\mathfrak I)$ of the ideal lattice $\mathfrak I$ generated by $a$. For such an ideal lattice, we can estimate rather precisely this minimal distance. A simple lower bound is
$\lambda_1(\mathfrak I) \geq \Delta_K^{1/2n} \cdot N(a)^{1/n}$, where $N$ denotes the algebraic norm of $a$ (that is, the product of all its embeddings), and $\Delta_K$ is the discriminant of field $K = \mathbb Q(x)/(x^n+1)$. The reason is that the minimal vector $x$ must generate a subideal of $\mathfrak I$, so $N(x) \geq N(a)$, and $\|x\|^n \geq \Delta_K^{1/2} N(x)$. An upper bound is also given by Minkowski's theorem.


Is there a technique to confirm that a given large integer value is a product of two primes?

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes.

About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate to us that there are only two prime factors (and not reveal anything else).  However, that does not appear what you're asking for.


This is not padding, nor is it related to the concept.

The output from the bcrypt library you're using is in a format inspired by Linux crypt(3) format. Dollar signs are field separators. 2a is the algorithm identifier. The full list is:

ID  | Method
─────────────────────────────────────────────────────────
1   | MD5
2a  | Blowfish (not in mainline glibc; added in some
    | Linux distributions)
5   | SHA-256 (since glibc 2.7)
6   | SHA-512 (since glibc 2.7)

The second field, 10, is the strength factor; I believe this corresponds to $2^{10}$ iterations of the algorithm. The salt and hash are stored concatenated with one-another — they are both fixed widths (128 bits for the salt, 184 bits for the hash), so it is easy to extract them.


How does AES bit security increase by round?

A few data points for AES-128. In 2018 Bar-On, Dunkelman, Keller, Ronan and Shamir described a 32-bit attack on 5 round AES (attack complexity here is the maximum of data, memory and computation requirements) and claimed a 99-bit attack on 7 round AES. The 2011 biclique cryptanalysis paper of Bogdanov, Khovratovich and Rechberger claims a 125.4-bit attack on 8 rounds and a 126.18-bit attack on 10 rounds. I'll claim a 128-bit attack against 11 rounds :-)
Based on our current knowledge then, perhaps it looks like an S-curve? Of course cryptanalytic effort has focussed strongly on larger numbers of rounds and I'd be hesitant to hypothesise any security vs. rounds function based on this.
ETA: The quoted figures for 8 and 10 rounds were for a related key biclique attack. The current best generic attack for 10 rounds is $2^{126.01}$


Best choice out of these six TLS cipher suites

Ideally, you should not use any of them. At all.
Here's why.

RC4, MD5 and DES should not be used anymore. Old crypto. Toss it.
CBC mode in AES sometimes suffers from implementation problems (cf. Padding Oracles). Thus, CBC should be avoided.
SHA1 is considered insecure and is not be accepted as a certificate signing hash since January 2017 by major browsers.

So, if you absolutely have to stick with one of these ciphers, I agree with @otus here, and would recommend TLS_DHE_DSS_WITH_AES_128_CBC_SHA.

IF ever you have a chance to add other ciphers to your embedded platform, know this :
Symetric ciphers :

AES and ChaCha20 are the best symmetric ciphers to use, as of the
beginning of the 21st century. The difference between them is, simply
put, being a block and stream cipher, therefore being different in
speed.
AES often takes advantage of AES-NI, a hardware acceleration, found on many processors in current laptops and servers.
ChaCha20 is to be preferred on mobile and embedded platforms, where
AES hardware acceleration is rare, because it is really faster.
Poly1305 is de facto the best buddy for ChaCha20, so they go in pair.
For AES, consider AEAD compatible modes, like GCM.
Chose a hash algorithm like SHA2 or above (SHA384, SHA512,...). The higher, the more secure. But this is overkill, will take more time and is heavier in terms of size. So stick with SHA256.

Asymmetric ciphers (for key exchange) :

Today's trend and best use is Diffie-Hellman. Even better, Ephemeral Elliptic-Curve Diffie-Hellman (ECDHE), because it is smaller, faster (you can generate 384bit parameters in a couple of milliseconds, corresponding to 7680 non-EC bits that would take hours to generate on your embedded device).

Certificate Signing :

Nobody uses DH.

RSA was good. To be avoided from now on. is still good.
It's even really faster for validation than DSA - take a look with
openssl speed (up to you to determine whether this matters for your use).

Best use : ECDSA. DSA is new, and coupled with Elliptic curves, it is smaller and really faster than RSA - take another look at openssl speed. Considered more secure. Just a shame that Edwards curves are not supported in OpenSSL as for now.

(Sorry if I missed details or am not being clear, wrote this on lunch break.)
EDIT : Added clarification on choice between ECDSA and RSA. Thanks @Dreadlockyx and @otus for having me have a second look !


Evaluate the time of Paillier decryption

You need to know

The size $s$ of the public modulus $n$ in bits.
The number $c$ of cryptograms.
If the code uses the CRT, or not; and in the affirmative, the number $k$ of prime factors in $n$ (usually $k=2$ for $n=p\,q$, with $p$ and $q$ distinct primes).
And of course, some benchmark of the code and hardware!

Each cryptogram is $2s$-bit, thus for 4kbyte ciphertext (at most 2kbyte plaintext) $c\,s\le2^{14}$. The largest range/safer/slower for 4kbyte ciphertext is $c=1$, $s=2^{14}$ (that is 16384-bit $n$, which is rather large).
As a rough approximation, using the same computation means and $k=2$, Pailler decryption with CRT for $s$-bit public modulus $n$ ($2s$-bit cryptogram) is about as fast as RSA decryption with CRT for $2s$-bit modulus. Not using CRT in Pailler causes a moderate slowdown (at most a factor of $2$), less than in RSA. Time is proportional to $c$, and often normalized for $c=1$ in RSA benchmarks.
Extremely roughly, Pailler decryption for $c=1$ is like 5 times slower than RSA decryption at equal size of $n$ and other stuff.
Large savings are possible by increasing $k$, like in multiprime-RSA.


How to determine secp256r1 or secp256k1 is used on the web sites

If you look at the all information on the site that provides you can find the answer very fast.

X9.62 ECDSA Signature with SHA-256

X9.62 : Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Standard (ECDSA)"
So, it is the NIST curve and NIST uses the $r$ versions like secp256r1.

A must-read question on our site

Should we trust the NIST-recommended ECC parameters?


The primary secret sharing methods in use for multiparty computation today are Shamir's and additive. I'm going to assume that you understand both.

Additive
No. When you go to reconstruct, you would have (simplified for 2 parties) $a_1b_1+a_2b_2\neq(a_1+a_2)(b_1+b_2)$. To prove it in the general case you would have to extend that analysis to $n$ parties.

Shamir
Yes and no. In Shamir's we say that $a_i=p(i)$ for some polynomial $p$ and $b_i=q(i)$ for some polynomial $q$. Now lets assume that $p$ is used to share $s$ (i.e., $p(0)=s$) and $q$ is used to share $t$. It is the case that $a_ib_i=(p*q)(i)$ and $(p*q)(0)=st$. So, $a_ib_i$ is indeed a valid share from some polynomial which evaluates to $st$ at $0$. There are, however, two problems.

The polynomial $(p*q)$ does not have random coefficients. The coefficients will depend on each other
The degree of the polynomial changes. Lets say that both $p$ and $q$ have degree $r$ (thus it takes $r+1$ shares to reconstruct the secret). The polynomial $(p*q)$ has degree $2r$, so it would take $2r+1$ shares to reconstruct $st$.

For these reasons, MPC protocols which use Shamir have a multiplication protocol which fixes these issues.

Another possibility
I don't even know if this is a secure secret sharing method (I'm hoping someone can comment). But you could use multiplicative secret sharing.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

Let $a_i$ be shares of $s$ such that $s=\displaystyle\prod_i(a_i)$ and similarly $b_i$ are shares of $t$. Then thanks to the commutativity of multiplication $a_ib_i$ would be a multiplicative share of $st$


Probability of false positive key matching two plaintext/ciphertext pairs

Under an ideal cipher model, every key implements a random permutation. A random wrong key that maps $x_1$ to $y_1$ thus maps $x_2\ne x_1$ to a random ciphertext $y_2'$ other than $y_1$. For a $b$-bit block cipher, there are $2^b-1$ such ciphertexts, thus the probability that $y_2'=y_2$ is $1/(2^b-1)$.
The probability that an incorrect key survives two tests is thus $p=1/(2^b\,(2^b-1))$.
A random $k$-bit key has probability $q=2^{-k}$ to be correct. It passes two tests with certainty if correct, with probability $p$ otherwise. Thus a random key has probability $q+(1-q)\,p$ to pass two tests [where the $q$ term is for the correct key, the $(1-q)\,p$ term is for incorrect keys, and obtained as the the probability that a key is incorrect, times the probability that it nevertheless passes the test with $(x_1,y_1)$ and $(x_2,y_2)$ ].
Thus a random key known to pass two tests has probability $q/(q+p\,(1-q))$ to be correct [where the numerator $q$ is the probability for a random key to be correct, and the denominator is the probability that a random key pass two tests]. That simplifies to $1/(1+p\,(1/q-1))$.
The desired probability of a false positive is the complement, that is
$$\begin{align}1-1/(1+p\,(1/q-1))\,&=\,1/(1+1/(p\,(1/q-1)))\\&=\,1/(1+2^b\,(2^b-1)/(2^k-1))\end{align}$$
For $b$ and $k$ at least 7, that's $1/(1+2^{2b-k})$ within 1%. When further $2b-k$ is at least 7, that's $2^{k-2b}$ within 1%, here $2^{-48}$, that is less than one in 280 million million.
More generally, it can be shown that the probability of false positive after testing $n$ distinct plaintext/ciphertext pairs is $1/(1+(2^b)!/((2^b-n+1)!(2^k-1)))$. For common block ciphers like DES and wider, that's very close to $1/(1+2^{n\,b-k})$, and when $n\,b-k$ is at least 7, that's $2^{k-n\,b}$ within 1%.


Encryption algorithm that produces dummy output on incorrect passwords

Yes, this is possible (conditionally). It sounds like you want Format Preserving Encryption. FPE works by encrypting from an arbitrary domain $X$ onto $X$. Consequentially, if plaintext $M \in X$ is encrypted to ciphertext $C \in X$, any decryption of $C$ - even with the wrong key - will yield a decrypted message inside of $X$. Thus an attacker doesn't know anything from a decrypted ciphertext if he only knows the original format of the valid plaintexts. All decrypted ciphertexts look like valid plaintexts to him.

For example, your domain might be "all ASCII strings of length 7", or "a NULL-terminated string of numbers with length less than 10", or some credit-card number format. All plaintexts, ciphertexts, and wrong-key decrypted ciphertexts will be in that domain. From your example, you might have a domain of 9 ASCII numeral digits.

(In case it's not obvious: The way an attack typically works is that the attackers are decrypting a ciphertext onto a plaintext message space $Y$, but they know something about the original plaintext that limits the potential domain to some set $Z$ strictly contained within $Y$ (that is, $Z \subset Y$). On a typical cipher we encrypt $\{0,1\}^n \rightarrow \{0,1\}^m$ (one binary string to another), but it's rare that all plaintexts could actually be any binary value, generally they are only a strict subset of the input domain. So we assume the attacker knows which plaintext formats are valid, and they just check decrypted plaintexts against this smaller domain. FPE addresses that issue by only allowing encryption and decryption from and to domains that are valid plaintexts. The attacker will never be able to look at a decrypted value and conclude that it is an invalid plaintext. Eg, if they are decrypting a credit-card number, they have an idea of what a valid decrypted CC will look like, but with an FPE algorithm all decrypted messages will look like a valid CC.)

Note that this won't mitigate the problem if the attacker knows some part of the original plaintext that does not apply to all valid plaintexts. FPE mitigates attacks where the attacker just knows the original message space for all valid messges, but it's possible they know something about the specific message on hand that doesn't apply to other messages. (For example, they may know that the 3rd digit is an 8 for the plaintext in question, but not necessarily an 8 for all plaintexts.) In this case they would have a smaller domain to check decrypted messages against and their original attack will still help them to some extent.

An FPE algorithm can be implemented from an existing block cipher. There are different schemes for turning a block cipher into an FPE, depending on your domain size and such. Some of the constructions are relatively simple given the block cipher and a function that decides whether a raw block cipher output is inside of the desired domain. The Wikipedia page linked to above contains descriptions of some.

As for your example: I think that it's rare to see FPE applied to very large domains, like image files. It's usually only applied to small domains, things like credit-card numbers in databases. I don't think I've seen it used in a case where the domain was larger than a couple block cipher blocks. (But whether you can use FPE efficiently on very large domains is a different question.)


Is my password entropy calculation correct?

Yes, the computation is correct: the passwords will have an entropy of $\log_2(26^2\cdot10)\approx {12.7}$, which means that they are weaker than a randomly chosen secret key with 13 bits.


XORing a header with SHA512-hash - secure?

Leaving text encryption and padding questions aside and focusing on the header stuff, here's how I'd approach the problem:

FileHeader = {
  BYTE Salt[16]  # Random bytes, K = KDF(Salt, Password)
  BYTE EncHdr[]  # EncHdr = AES-GCM(K, h0...h5)
}

Salt is a sequence of random bytes (it's there to prevent Rainbow table attacks)
EncHdr is the encrypted version of your current header containing magic bytes and length (you can store other information in there, too)
KDF is any key-derivation function, such as PBKDF2, crypt, scrypt, etc.

Now, if you don't want to use proper encryption and KDF, you can try this:

FileHeader = {
  BYTE Salt[16]  # K = HMAC-SHA512(Password, Salt), split K into (K1, K2)
  BYTE EncHdr[]  # EncHdr = Encrypt(K1, Header)
  BYTE MacHdr[]  # MacHdr = HMAC(K2, EncHdr)
}

So, instead of computing K = SHA-512(Password) you compute K = HMAC-SHA512(Password, Salt) and then split resulting 64-byte K into two 32-byte subkeys K1 and K2 (e.g. K1 is first 32 bytes of K and K2 is the last 32 bytes of K).

You then use K1 to encrypt header payload (magic and length) similarly to as you did before. After that you use K2 to authenticate encrypted data by computing HMAC.

Compared to your scheme, this one is (a) resistant to Rainbow tables (because salt is used to derive key in addition to password) and (b) protects from unauthorised modifications of encrypted header data by authenticating it.


Padding size with a CBC Block cipher in TLS

In RFC2246, if you need 12 bytes of padding total, that means that you have 11 padding bytes, followed by a padding length field.  So, each padding byte has a value of 11 (0x0b), as well as the padding length field.  This is implied by the requirement that the total TLSCiphertext.length must be a multiple of the block size, and this TLSCiphertext.length includes the padding length field itself.


Nonlinearity of a Boolean function with odd number of input bits

This is a famous open problem in coding theory, the covering radius of the first order Reed-Muller code, when the number of variables is odd.
As far as I know the best general upper bound on nonlinearity which in this paper is denoted N (=covering radius R) for $n=2k+1$ is still the one below:


Is authentication more computationally expensive than encryption?

SHA-256 is designed to be collision-resistant, which is much costlier than pseudorandomness or unforgeability.  It should come as no surprise that it is slower.  The difference between SHA-256 and HMAC-SHA256 for bulk data is negligible: a call to HMAC-SHA256 on a long input costs the same as one call to SHA-256 on a long input plus one call to SHA-256 on a short input.  The same goes for SHA-512, BLAKE2, SHA-3, etc.  You can use HMAC-SHA256 as a MAC for unforgeability, but you're paying a huge tax for unnecessary collision resistance.

In contrast, polynomial evaluation message authentication codes such as Poly1305 are some of the fastest crypto primitives available.  These are essentially chains of 128-bit additions and multiplications, with considerable flexibility in the order of operations to maximize vector unit utilization by virtue of working in a convenient prime field.  For MACs, collision resistance is not relevant.  Of course, you can't use Poly1305 for applications where collision resistance is necessary.

In chacha20+poly1305, the Poly1305 computation is easily the fastest part.  The speed of Poly1305 is a large part of why chacha20+poly1305 is much generally faster than, e.g., AES-CBC with HMAC-SHA256.  Another part is that software AES is slow, and software AES without timing side channels is horrifically slow—and worse for AES-CBC, which must work on arbitrary inputs, than for AES-CTR with highly structured inputs.

Similarly, for AES-GCM, there is a catch that most CPUs don't easily support fast binary field multiplication in software, whereas most CPUs do easily support fast prime field multiplication in software, so AES-GCM is also much slower than chacha20+poly1305 without dedicated hardware support—and horrifyingly slow without timing side channels.

As for whether AEAD gives you confidentiality: Yes, AEAD means authenticated encryption with associated data.  If you skip the authenticated part, then often you don't get confidentiality in the scenario of active attacks.  You should generally always use authenticated encryption; forget about unauthenticated encryption schemes as anything more than an implementation detail for authenticated encryption.


HKDF vs TLS PRF. Which of the one is better?

It is unclear if you wanted to compare TLS 1.1 PRF or TLS 1.2 PRF. Different TLS versions have different PRFs. Assuming you meant TLS 1.1 PRF although you linked TLS 1.2 RFC.

TLS 1.1 PRF

Short: HKDF is commonly a better choice than TLS 1.1 PRF, but not always.

Consider these aspects:

HKDF is a generic construct.
HKDF is extract and expand.
TLS1.1 PRF is just extract or expand.
TLS1.1 PRF is intended for TLS protocol.
HKDF can be used with hash functions chosen by the user.
TLS1.1 PRF uses MD5 and SHA-1 hashes. Thus, it does not allow using stronger hash functions.
TLS1.1 PRF uses two hash functions which causes extra complexity and complicates security analysis.
TLS1.2 defined new PRF function to use. (So for purposes of TLS, TLS1.1 PRF has gotten deprecated).

TLS1.1 PRF has been analyzed in Hash function combiners in TLS and SSL.
Based on this analysis, HKDF, when used with a strong hash function is likely stronger than TLS1.1 PRF.

TLS1.2 PRF

Comparing HKDF with TLS 1.2's PRF.

NIST SP 800-108 Recommendation for Key Derivation Functions defines various ways to construct Key Derivation Function:
- Counter Mode
- Feedback Mode
- Double-Pipeline Iteration Mode

For NIST, all these approaches are equally acceptable. The Feedback Mode matches HKDF's Expand phase. The Double-Pipeline Iteration Mode matches TLS 1.2 PRF. Thus we could assume, that TLS 1.2 PRF could be considered to be similar to HKDF's Expand phase if used with the same hash function underlying the hmac.

Purpose of HKDF's extract phase is quoted from RFC 5869:

In many applications, the input keying material is not necessarily
distributed uniformly, and the attacker may have some partial
knowledge about it (for example, a Diffie-Hellman value computed by a
key exchange protocol) or even partial control of it (as in some
entropy-gathering applications).  Thus, the goal of the "extract"
stage is to "concentrate" the possibly dispersed entropy of the input
keying material into a short, but cryptographically strong,
pseudorandom key.  In some applications, the input may already be a
good pseudorandom key; in these cases, the "extract" stage is not
necessary, and the "expand" part can be used alone.

For applications where extract phase is beneficial (distribution of input keying material is not uniform), HKDF is certainly the way to go.

For other uses, where expand phase is used alone, any one of these two (or in some cases counter mode) from NIST SP 800-108 could be used. (Note: If you use TLS 1.2 PRF outside context of TLS protocol, maybe better define the function in terms of NIST SP 800-108, instead of TLS 1.2 PRF from the RFC).

Short summary:

If you need extract use HKDF.
If you need expand only, use functions from NIST SP 800-108.
Generally you should not use TLS 1.1 PRF except for compatibility with TLS protocol.


Are there any papers explaining how to port textbook RSA to realworld RSA?

Vanilla textbook RSA does not include "padding and stuff", the term "textbook RSA" generally refers to simply encoding a plaintext message as an integer and raising it to an exponent. Implementing this is pretty easy, just follow the steps outlined on Wikipedia. You can easily translate those steps into some given programming language.

Based on the rest of your statement, it sounds like you want to implement a real-world encryption/signing scheme using RSA, but not some higher protocol that uses it. If so, I would suggest looking at PKCS #1 v2. It's an authoritative specification for several such RSA padding schemes. (RSA-OAEP is probably the most recommended padding scheme for encryption if that's what you want.)


Anonymity of Paillier cryptosystem in e-voting system

You've discovered some of the challenges of secure electronic voting. As you can see, merely having a cipher that allows you to confidentially tally numbers is not sufficient to conduct a secure election.

  Now if each vote is not signed (or identifiable in some way) how can I exclude that Trudy has not forged a huge amount of fake votes? For that reason I suppose that each vote has to be identifiable when still encrypted.

This is the issue of ensuring that each voter only gets one vote.

  What I can't understand is what prevent the election official to decrypt that votes one by one and see who vote for what.

This is an issue of vote privacy, the inability for even the officials who run the election to know who voted for what.

There are lots of different schemes that  use different techniques and make tradeoffs regarding the goals and efficiency.

E-voting is a subject unto itself. This paper provides a gentle introduction.


Comparing n-multiple amount of merkle trees?

While I originally looked into what would require the use of some Tree Topology or use of Bloom Filters, I asked a friend on this problem.
He gave me a more practical solution:

Sort each Tree by Leaves Seperately
Then you put each result in heaps - sort of like a merge step of the quick sort algorithm.
You then take the First Heap from the first tree and compare it with the first heaps from the other trees.

If all heaps match, pop all the heaps and you have a leaf present in all of the trees
If the first heap is larger than any given heap, pop it - it doesn't match all the trees. Continue popping from that heap until you find a matching heap, or...
If the first heap is smaller than any given heap, pop all of the previously checked heaps - all of them contain a leaf that is not present in all of the trees
Repeat until one of the heaps is empty

This solution has a linear complexity - you will compare each leaf about 1 time.


It's harder for the designer to make a hash function collision-resistant than second-preimage-resistant, because it's harder for the adversary to find a second preimage than to find a collision.


What kind of data is appended to the message encrypted in AES128-CBC?

So my question is : what is the nature of the appended data, padding, or info about the length of the message, or both ?

With this ciphersuite, the encrypted data consists of the plaintext data, and the HMAC of the plaintext (and header and sequence number); this HMAC is 20 bytes long.

Hence, if you encrypt 1 byte, then you'll end up encrypting 21 bytes; with CBC mode, this gets padded up to 32 bytes; exactly what you see.  And, a 16 byte message becomes 36 bytes with the HMAC, hence 48 bytes after padding; and a 32 byte message becomes 52 bytes, which is 64 byes after padding.

One correction to a statement you made:

  even though padding is not necessary (I'm using messages of the block size).

Actually, even if the 20 byte HMAC wasn't added, you always have to add at least one byte of padding; if the prepadded message was a multiple of 16 bytes long, that means that you'll need to add a full 16 bytes of padding.  If you encrypt a 12 byte message (so it becomes 32 bytes after the HMAC), that becomes 48 bytes after padding; if padding was not added, then on decryption, there'd be no way to distinguish between "this decrypted message was precisely 32 bytes long", vs "this decrypted message was shorter than 32 bytes, and had padding added"


Is it safe to send IV in plain text for every request?

Is it safe to send the IV in plain text in every QR code request?

IV is not secret and never meant to be, it can be sent as it is. See the CBC mode from the Wikipedia.

  When using the same nonce, decryption will still work, what is the purpose or misuse of the nonce here?

Nonce (in Cryptography) means number used once. The IV in the CBC mode cannot be nonce. The aim of IV is randomizing the encryptions. Using the same IV again turns the CBC mode into the ECB mode. This has catastrophic results, see the penguin from Wikipedia in or look at frequency attack.

For the difference of IV and Nonce please see Difference between a nonce and IV

  Should I use chacha20 at all? Or is there a much more better encryption/decryption method to use here?

You need authenticated encryption which simultaneously give authenticity and integrity. You may choose ChaCha20Poly1305 or AES-GCM.

  I need to keep my server's public key secret and only in the firmware of the IoT device, to prevent 'fake devices' generating valid but fake QR codes, which sounds bad.

Public keys are not created to be kept secret. The more important is the ID of the IoT that should be sent during the data transmission so that the server can accept the result. Therefore the server must store the ID's beforehand. In the current design, the server is going to accept any message.

Note: You will also need to authenticate the mobile device, otherwise any mobile device can be used to attack.

Note 2: IV should not be predictable.

Note 3: You don't need to generate if from a nonce. A good random source should be enough. See  Best way to generate a IV for AES-CBC when encrypting files?


Trying to Understand Ring Learning With Error Encryption

convert $v-u \cdot s$ to centered representation as described here seems to work


Do 2DES and 3DES2 have the same effective key length?

Definitely a mistake. The text clearly contradicts itself.

  ... 2DES has an effective key length of 57.

And later...

  There does not
  appear to be a meet-in-the-middle attack on 3DES2 however, so that its key length of 112 is also
  its effective key length.

which clearly contradicts

  2DES, although having the same effective key length as 3DES2 and offering what appears
  to be the same or at least adequate security, is not popular in practice.

As a bit of an aside, 3DES2 is considered by NIST to have an effective key length of at least 80 bits, but definitely not the full 112 bits, due to its vulnerability to known-plaintext attacks with $2^{40}$ blocks.


How can the identity $\textbf{Pr}[\textbf{y}=y|\textbf{x}=x] = \sum_{\lbrace K:x=d_K(y)\rbrace}\textbf{Pr}[\textbf{K}=K]$ be verified to hold?

The operation of the function is completely described by $P(X,Y,K)$ which factorizes as $P(Y|X,K)P(X)P(K)$ under the assumption that $X$ and $K$ are independent and leads to

$$P(Y) = \sum_X\sum_K P(Y|X,K)P(X)P(K)$$

If you restrict $X$ to only the particular one that $K$ maps onto $Y$ (by writing $X = D_k(y)$) then $P(Y|X,K) = 1$ under the assumption that the function is a bijection, then you end up with

$$P(Y=y) = \sum_K P(K=k)P(X=D_k(y))$$

Using the same approach you can prove the conditional statement:

$$P(Y|X) = \sum_K P(Y|X,K)P(K) = \sum_K P(K)$$


Can any hash function based on the sponge construction work as extendable output function?

Yes.

Pick any permutation $\pi\colon \{0,1\}^n \to \{0,1\}^n$, and capacity $c < n$.  For example, you could pick Keccak-p[1600, 24] like SHA-3 uses, with state size $n = 1600$ and capacity $c = 2\lambda$ for a $\lambda$-bit security level—that is, SHAKE128 uses $c = 256$ for 128-bit collision resistance (provided, of course, the output is at least 256 bits).  Let $r = n - c$ be the rate.

Start with the initial state $x_0 = 0^n$, i.e. a string of $n$ zero bits.  Break the padded input message $m$ into $r$-bit blocks $m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$.
Absorb.  For each block $m_i$, update the state $x_i = \pi(x_{i-1} \oplus (m_i \mathbin\| 0^c))$; that is, pad the $r$-bit block $m_i$ with $c = n - r$ zeros, xor it into the state, and permute the state.
Squeeze.  Reveal the first $r$ bits of $x_\ell$, the first $r$ bits of $\pi(x_\ell)$, the first $r$ bits of $\pi^2(x_\ell)$, the first $r$ bits of $\pi^3(x_\ell)$, and so on, until you've produced the number of output bits you want.

  Is there any lightweight XOF for hardware or software implementation?

There are many permutation-based designs these days.

Keccak comes in many sizes: SHA-3 uses Keccak-p[1600, 24] with parameters that were overdesigned partly out of paranoia and partly for political reasons, but KangarooTwelve uses Keccak-p[1600, 12], i.e. half the number of rounds of SHA-3, and higher rates $r$, and still has a good security margin against the best collision attacks.  You could possibly even tune the Keccak parameters to be even smaller if collision resistance isn't important for your application, and there are other options for smaller word sizes.

NORX, a 512- or 1024-bit permutation, was designed like an ARX network but with the approximation $a + b \approx a \oplus b \oplus ((a \wedge b) \mathbin\ll 1)$ to make hardware designs a little cheaper, since integer addition has a high cost for carry propagation; Gimli is a newer design with a 384-bit permutation that improves on NORX.  The CAESAR winner Ascon uses another 320-bit permutation.


Does AES with whitening mode have the following property?

No. The AES permutation is not distributive over the XOR operation.

If it were true, this would violate the basic security construction of AES in the Chosen Plaintext Attack model (which is a good model we like to use when evaluating the security of a PRP): An adversary $A$ queries a black box with his own plaintext, trying to decide if the black box is outputting AES permutation of the input or a random one. Successfully guessing which one (AES or a real random permutation) the black box is performing is victory for $A$. So $A$ could issue a request to the AES encryption blackbox for X, Y, and X $\mathbin{\oplus}$ Y, and get back AES(k, X), AES(k, Y), and AES(k, X $\mathbin{\oplus}$ Y). Then he would check that AES(k, X $\mathbin{\oplus}$ Y) = AES(k, X) $\mathbin{\oplus}$ AES(k, Y). If it did, he would know (with negligible error) that he was working with AES and not a random permutation because a random permutation would certainly not have that property. Thus he would break AES under the CPA model with just 3 chosen messages.


It is the authentication - which uses Poly-1305 that needs the padding; the padding does not expand the ciphertext. The Poly-1305 operates on blocks of 128 bits. The padding is applied so that Poly-1305 can always process full blocks of input. Afterwards the the padding is discarded - it is not kept with the ciphertext.

During verification the padding is reapplied, otherwise the calculated authentication tag would not be identical with the one that was kept with / is part of the ciphertext.

In the case of Poly1305 it seems that the additional authenticated data (AAD or just AD) is padded separately, instead of concatenating the two and padding the combination of the two. This makes it possible to calculate the AAD component independently of the ciphertext component of the authentication tag, as DannyNiu's answer indicates.

Note that in practice a single block input buffer will be used within the implementation of the Poly-1305 function. Implementations will pad the buffer instead of the actual input. Discarding consists of clearing the buffer - if it is cleared at all, it can also ignore the data in it.


Did NIST verify “post-quantum” claims in the SHA3 proposal papers?

With any $n$ bit hash it is possible to:

Find preimages with work $2^n$ on classical computers and $2^{n/2}$ using quantum computers
Find collisions with work $2^{n/2}$ on classical computers and $2^{n/3}$ using quantum computers

I want to emphasize that these are generic attacks that always work, no matter which concrete hashfunction is used. Grover's algorithm is the quantum mechanical equivalent of classical brute-force.

For sponges (including keccak and cubehash) if $c$ is smaller than $2n$ there are other generic attacks:

Find preimages with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers
Find collisions with work $2^{c/2}$ on classical computers and $2^{c/3}$ using quantum computers

Now several authors of SHA-3 candidates simply wrote "preimages with work $2^n$" and "collisions with work $2^{n/2}$" without explicitly stating that these claims only apply to classical computers. The intention of these claims was clearly "no faster than brute-force attacks", but they only spelled it out explicitly for classical computers.

Some authors (like DJB himself) carefully specified the above limits separately for classical computers and quantum computers, and some simply wrote that the "usual security levels apply".

Now DJB argues that since the security level against quantum computers violate the security claims, they're an attack against those hashes. The same attacks apply to cubehash as well, except that they don't violate its security claims.

The paper is the simple observation that some papers didn't mention the generic quantum computer attacks and didn't clearly restrict their claims to classical computers. It's about a really minor sloppiness in those papers, I'd expect every cryptographer to know that these claims don't apply to quantum computers.

The paper does not contain any new attacks or findings, only nitpicks.


AES vs AES-CMAC for session key derivation

The question is: is there any difference between choosing a simple AES primitive and the more complex AES-CMAC as KDF?

If you use AES as "KDF" in this way, it is equivalent to sending an AES-ECB encrypted key that the recipient decrypts. It's just that you have swapped the direction of encryption and decryption for AES. (AES-ECB is secure with random one-block messages.)

Using CMAC is slower if you take into account the key derivation, but not much different otherwise.

Note that neither version of the protocol has any protection against replay attacks. An attacker can send an R value that has already been used and make the other party reuse a key. Depending on what that session key is actually used for, that can be really bad. (E.g. CTR mode with constant starting nonce.)

A proper protocol would likely let both parties affect the session key. Using e.g. ephemeral Diffie–Hellman with the master key for authentication would be one way to accomplish that while also getting forward secrecy.


Compare two approaches for cracking RSA key

For part(a.ii), I am presuming that "enumerating candidate prime factors" means that we have a precomputed list of all 1536-bit primes, which we can simply test one at a time.

To determine average running time we can use the prime number theorem, which states that the number of primes less that $N$ is approximately given by

$\pi(x) \sim \frac{N}{\ln N}$.

As such, there are approximately

$\frac{2^{1536}}{\ln 2^{1536}} = 2.24 \times 10^{459}$

candidate primes to test. In reality, division of numbers this large is not an elementary operation, but even assuming it were to be one, on average we'd need half that number's worth. I think it's safe to say that (a.i) is the better choice.

As for part(b), I'm may be getting confused, but what I believe this is stating is that our key is generated by taking an input password $p$ and using it to seed a PRNG. We then generate an output stream of 1536 bits, and then select the next prime greater than our output as the first prime? And I presume this implies that we have access to said password?

If so then on average we'll have to look at

$\frac{1}{2} \cdot \ln 2^{1536} \approx 533$

different numbers before we find a prime. We'll have to do this twice though, so that's a little over a thousand primality tests on average. So the speed is then dependent on the number of elementary operations in our testing algorithm and PRNG, but assuming modern constructs (say, ISAAC and Miller-Rabin) the candidate approach should work better.

Sorry if I understand the question incorrectly. It's not the best written.


Homomorphic Modular Reduction for Secure Storage

Your modulo operation does not require a real division, because you are not far from your modulus.

Represent your numbers with 2's complement by using TFHE, or HELib libraries. In this case, your numbers use bit arithmetic in FHE, i.e. you will have a cyphertext $\{c_0,c_1,\ldots,c_{k-1}\}$ for $k$-bit numbers.

What operation do you need?

$Add(A,B)$ : homomorphic addition
$Sub(A,B) = Add(A,-B)$ : homomorphic substraction by using $Add$.
$MSB(A)$ : return the most significant bit of the ciphertext
Comparison $Comp(A,B) = MSB(Sub(A,B)) = MSN(Add(A,-B)) $
If : for singe if else case with single encrypted bit $S$, $$I = S \cdot A + S' \cdot B$$ where $\cdot$ is the $\text{AND}$ operation. According to value of $S$, $I$ is either $A$ or $B$.

More details on these operations can be found in a previous answer about common circuits in FHE.

Let $A = Enc_{pk}(A)$, $B=Enc_{pk}(b)$, and $N = Enc_{pk}(n)$ be encryption of plaintexs $a,b,\text{and } n$ under a semantically secure Fully homomoerphic Encryption with public key $pk$, where $n$ is the modulus.

$S = Sub(A,B) = Add(A,-B)$
$C = MSB(S)\quad\quad\quad\;$          //one bit comparison the result.
$F = S + N\quad\quad\quad\quad\;$      // adding modulus if needed
$R = C * F + C' * S\quad$  // If condition on $C$ selects either $F$ or $S$.
Return $R$

The circuit is not complete because the answer can still be negative. In this case, compare with encryption of zero $E_0 =Enc_{pk}(0)$and add $N$ again.


As far as I know, the "random oracle game" doesn't exist. What your are speaking (I think) is about pseudo-random functions. And when the challenger (not the oracle) is in the "RANDOM" mode, he could keep in memory the pair input/output, according to previous queries. Then it doesn't need to output "error", he could return the same output as in the previous query.

references:

en.wikipedia.org/wiki/Pseudorandom_function_family

https://crypto.stanford.edu/pbc/notes/crypto/prf.html


ChaCha20: is this a potentially safe way of using nonce derived from private key if the key/nonce pair is never reused, for a given plaintext?

I realize in ChaCha20 the nonce should be random and unique each time…

Nope!

For the ChaCha stream cipher, it is not safe to choose the nonce at random.  At 64 bits long, the ChaCha nonce is too short to be chosen at random.  In general, you should use a sequential message number under any single key as the nonce.

For the XChaCha variant, like the XSalsa20 variant of Salsa20, it is safe to choose the nonce at random because the extended nonce is 192 bits long so the collision probability becomes nonnegligible only after an unimaginable $2^{96}$ messages.  But your question was about ChaCha without an extended nonce.

  Could the nonce be entirely deterministic and derived from the key so long as the key is only used exclusively once for a distinct plaintext (akin to the one-time-pad). I realize this is risky if the key/nonce pair is re-used on a different plaintext, but wouldn't it be as safe as the one-time-pad if the pair is never reused on a different plaintext message?

If the key is chosen independently and uniformly at random for each message, then you can safely use the fixed nonce zero.  Don't mess with hare-brained schemes like copying bits of the key around into other places.

  plaintext: 68656c6c6f

  resulting chacha20 ciphertext: 702da4b13e682d4b840b19cde305583b415765f936

Something is wrong with your use of ChaCha because your ciphertext length is not exactly the same as your plaintext length.  [Update: This is because the question is actually about the ChaCha/Poly1305 authenticated cipher of RFC 7539, not about the ChaCha stream cipher originally described by Dan Bernstein with a different nonce size.]

Also: Write down what your protocol is and how it fits into your application so that a reviewer can confirm you're following the rules of ChaCha.

Also: Don't just use ChaCha and leave it at that.  Use an authenticated cipher (or AEAD, authenticated encryption with associated data) like crypto_secretbox_xsalsa20poly1305.


Attack MD5 with limited input and partial information

Let's begin with what is MD5;

MD5 has a 128-bit digest size, 512-bit block size Merkle–Damgård construction based hash function created by Ronald Rivest in 1992.
From a secure hash function we want, 128-bit pre-image and secondary pre-image resistance, and 64-bit collision resistance. MD5 collision resistance is broken, and finding collision can be done in minutes.
There is an attack on the pre-image resistance of MD5 that has $2^{123.4}$-cost however, due to the memory cost, you would not go in this way instead you will run full brute force or better build the parallel machine.

Pre-image attacks

Today's largest known collective computer power is the bitcoin miners that can reach $\approx 2^{92}$ SHA2d calculations per year. This means that even they need 35-years to find one.

The current best practical attack on the pre-images is when there are multiple targets ( we can always have if one still uses MD5 without salts, etc.). Build the parallel brute force machine and use Oechslin's rainbow table;
for $t$ targets built $t^2$ parallel machine with $p$ success probability for finding the first target, you need $2^{128}p/t$ area*time cost. This is much better than the brute force of a single target. See more here.

There is also Grover's unstructured quantum search algorithm to be considered that reduces the search time into the square root of it. If built, then (ignoring running cost) the search time will be around $2^{64}$.

It can also be parallelized; however, building $k^2$ machine will provide $k$ speed-up.

based on the md5 output is there any way to find out information about input? like which character was in the beginning or input mostly consists of which character?

No, what you are describing is actually destructive to pre-image resistance.
If you can find the first character (byte) then the pre-image resistance is fall to $c \cdot 2^{120}$ where the $c$ is the cost of determining the first character. The next question will be what is preventing the attacker to determine the next byte, then next? Hash functions are designed to have an avalanche effect that it changing one-bit of the input should have affect all the output bits randomly, i.e. all of the output bits flip with 50%.
If you can figure out the character space by looking at the hash ( let assume that there is an oracle that tells us this), like 5 numbers, then the pre-image search is crippled if you look into 128-bit information, $5^{16} \approx 2^{38}$. This doesn't mean that the pre-image has to be found in this 128-bit space. Still, we can look at the string length 32 and the search time will be $2^{76}$-time
Or, actually, you are asking something like that;

If the input space is low as 16 characters from $[1,2,3,4,5]$ then this is the short input space problem on the hash functions. Since the calculation of the hash is free, one can easily search these values. $2^{38}$ search space can be easily reached by today's ordinary CPUs.
To mitigate this you can use a keyed hash function like $\operatorname{HMAC-MD5}(k,m)$. As long as the key is kept secret, then you are fine. Note that, if there is no restriction to use MD4, prefer $\operatorname{HMAC-SHA-256}(k,m)$

actual problem is I have a SHA-256 string as input(64 characters and hex) and I want to show MD5 of this input to my users and it's important that they can't find any information based on the MD5 output. I want to know if its a short input space or not

A hex is 4 bits that you will have $4^{64}$ input space to search; that is $2^{128}$-bit. This is too high for a single target. However;

If the $t$ users can come together and can build the parallel machine using the rainbow tables then they can find the first target on  $2^{128}p/t$ area*time cost. So, you can tune your number with this information.


Can a homomorphic encryption scheme be made CCA2 Secure?

The best you can get for homomorphic encryption schemes is non-adaptive chosen ciphertext security (IND-CCA1 security), see e.g. here for a quite up to date characterization.

As you rightly observe homomorphic encryption schemes are malleable by definition and cannot provide adaptive security against chosen ciphertext attacks (be IND-CCA2 secure).

Since in the IND-CCA2 security game the adversary knows the relationship between both messages for the challenge ciphertext, the adversary can obtain another ciphertext to a chosen plaintext and operate on the challenge ciphertext and the newly obtained ciphertext and then submitting the resulting ciphertext to the decryption oracle. This does not violate the conditions of the IND-CCA2 game (the adversary is only restricted to not submit the challenge ciphertext directly to the decryption oracle). Consequently, the adversary can determine which plaintext is hidden in the challenge ciphertext.

The reason why IND-CCA1 security can however still be achieved for homomorphic encryption schemes is that in the IND-CCA1 game the adversary after having obtained the challenge ciphertext no longer has access to a decryption oracle (and thus eliminating the aforementioned strategy).

Concluding, every compiler/transform (like Fujisaki-Okamoto or Naor-Yung double encryption) that takes a less secure scheme (IND-CPA) and converts it into an IND-CCA2 secure scheme destroys the homomorphic property of the original scheme.


Design question for a service that signs messages on behalf of a user

Store the key encrypted. Send the encrypted key to the user and have them decrypt it and sign the message. Whatever your objections are to this scheme, they are most likely either misguided or can be addressed by the implementation of the scheme.


How do I check if the output of my CFB TEA encryption algorithm is correct?

No, there are of course other methods of verifying your implementation.

Note that there are a few separate steps that can be distinguished:

the TEA block cipher;
the CFB mode (using the right number of bits to forward);
The encoding of the message and ciphertext.

First, test your block cipher (without CFB mode of operation) against any available test vectors. There seem to be a few available.

Second, test your CFB mode of encryption with a well known block cipher, e.g. DES, Triple-DES or blowfish (all come with 64 bit block size, just like TEA). You will need to establish key, IV and number of bits that are forwarded within CFB mode encryption (CFB-8 or CFB-64?).

Thirdly, test your encoding / decoding. You should treat the output of TEA as binary, not as text. For the input message you need a well described, canonical way of creating a message using numbers. Of course this encoding / decoding must be reversible. The codec should be tested separately first.

Finally, try and see if the combination of all three works as expected. If you cannot find text vectors directly then try and use a different implementation (and test that against text vectors first).

You could also use a third party implementation to create intermediate values, so you can verify the correctness of your implementation.

Here's a test vector created using Bouncy Castle (Java, v1.57) and, of course, hexadecimals to represent the bytes:

TEA in CFB-8 mode
K : 2c1003d83c3c3707a92a10f45a3bd72f
IV: 681574192889be9d
M : 3132333435363738
C : d2751754c6699453

This is the kind of representation you need to test. Note that the input message M consists of the ASCII encoding of the string "12345678". The 128 bit key and full 64 bit IV have been randomized.


How to choose the integer m in the general number field sieve (GNFS)?

For anyones who's interested - From this paper

http://scholar.lib.vt.edu/theses/public/etd-32298-93111/materials/etd.pdf

I found that it's best to find the degree of the polynomial you're going to be using based on the number of bits in $N$. Let k = $log_2N$ Briggs gives experimental bounds

$d= 5$ for $k \geq 110$

$d= 4$ for $80 > k > 110$

$d= 3$ for $50 > k \geq 80$

And doesn't say for $k \leq 50$, probably because GNFS is not the fastest for numbers that small.

Then you pick a $m$ such that $m^d$ is close to $N$. Then you find the base $m$ expansion of $N$ and obtain $f$ from that. This guarantees that $f(m) \equiv 0$ mod $N$


Here's the basic idea. Encryption ideally hides all information about the encrypted data. But in practice, that isn't completely true: encryption reveals the size of the encrypted data, at least within a few bytes. For example, suppose that you know that the answer is “yes” or “no”, and you see the following message encrypted with AES-CTR:

82a801950ca7aaeea0685afc86b44b70 15c0

You know it's a two-byte message (plus 16-byte IV) so it's “no”.

Now suppose that you have a fixed-size message (or more generally a message where the attacker knows the approximate size anyway, because it's given by the protocol), but it's compressed before encrypted. Compression exploits redundancy in the message. So if the encrypted message is a lot smaller than the expected size of the plaintext, that means a highly redundant message; if the encrypted message is about as large as the expected size of the plaintext, that means a message with low dedundancy.

Low/high repetition, on its own, is typically not meaningful to an attacker. But what if the attacker can inject some text into the message? Then the size of the encrypted compressed message reveals redundancy between the part that's injected by the attacker and the confidential part. Now there's room for a damaging attack.

In cryptography, and more generally in the study of computation, an oracle is a black box which receives inputs and produces outputs. The oracle's outputs may not be possible to obtain without the oracle. In cryptography, a common kind of oracle is one that knows a secret key that the attacker doesn't have, but the oracle will only respond in certain specific ways, it won't just reveal the key. For example, a basic encryption oracle is willing to encrypt any plaintext but won't decrypt anything, allowing attempts to perform chosen-plaintext attack.

In this challenge, you're asked to study a particular kind of encryption oracle which combines the submitted plaintext with some fixed confidential text, and compresses the whole message. By submitting a lot of different partial plaintexts, and measuring how the length of the whole message varies depending on the submitted plaintext, the attacker gains information about the fixed confidential part. For example, submit aaaaaaaa, bbbbbbbb, cccccccc, etc. and see how the compressed length varies to get a rough ideas of how many a's, b's, c's, etc. there are in the confidential part. Repeat with digrams, trigrams, etc. If the confidential text is some kind of password $P$, that can turn an exponential attack (try all possible passwords of the known length) into a linear attack (figure out the first character because it's the character $c$ for which $c^n P$ gives the best compression, then repeat for each subsequent character).

The basic principle has been well-known for a long time. It's mentioned in John Kelsey's 2002 paper “Compression and Information Leakage of Plaintext”. But few people thought about the concrete applications until it was widely publicized as the CRIME attack on TLS. CRIME exploits compressed TLS streams which contain both a fixed confidential part (cookie for a web page) and a varying attacker-chosen part (e.g. an injected ad that makes callbacks). If you look around CRIME, you'll find a lot of literature on the topic, including Thomas Pornin's detailed write-up before the attack was published.


AES-GCM uses single block cipher operation and can be processed in parallel, therefore it should be faster.
CTR+HMAC requires block cipher and hash function, which usually can't be processed in parallel. Also it requires 2 keys. It is often miss-implemented (MAC-then-encrypt or MAC-and-encrypt, using single key).
Cipher-text length is the same for same security level. However CTR+HMAC usually has a longer tag, because hash functions have bigger output than block ciphers, but you can truncate tags to the same length.
If implemented correctly and the block cipher / hash function is secure, both are secure. However, because CTR+HMAC has 2 keys compromising one part won't compromise the other part.


Summary: an ounce of math wins over computers, quantum or not.

For most natural distributions of A (including samplings from a physical process like diode noise, not too much affected by conversion to digital or feedback from the state of the generator) and common rounding methods, we are able to predict future output given enough samples. A stream of zeroes is all it takes. With good likelihood that will start to match the generator's output, and keep on that way from there on, before $2^{32}$ steps, or just $2^6$ if A is rounded to integer before multiplication.

This follows from the fact that once and if $V_j$ reaches zero, it remains stuck there. And that if A is rounded to integer (either to nearest, lower, or higher) before multiplication, an iteration removes from $V_j$ as many bits of entropy as there are low-order bits at zero in the integer multiplicand that turns out to be used. This problem does not touch the original RANDU, because its multiplier is always odd.

Hereafter I consider using $V_{j+1}=65539\cdot(V_j+1)\bmod2^{31}$, which at least may avoid that issue.

Now the generator can be be fully predicted from future output, or not, depending on characteristics of A that are not explicitly stated in the question. It is entirely possible to have A such that after rounding it is always in a small set of integer values equal modulo $2^{31}$, and then A will have no influence on output.

However, for distributions of A arising from sampling a quantum phenomena similar to diode noise and not too much affected by conversion to digital or feedback from the state of the generator, the output will indeed be significantly influenced by A. Output will not be fully predictable from past output, because the multiplier is likely to vary unpredictably (for reasons explained in that other answer, for diode noise). I do not believe (or see anyone believing) that a quantum computer without a direct physical link to the particular source used for A is able to change that; at best it could improve to some degree on the advantage obtainable by a classical computer, or turn something almost predictable to totally predictable.

With the hypothesis in the previous paragraph, the generator will remain utterly distinguishable from random; but if we believe in the hypothesis of quantum physics to any degree (as overwhelmingly most physicians and engineers do), there will be some exploitable entropy in its output, so that seeding enough of that into a sound and generously dimensioned CSPRNG will yield a RNG computationally indistinguishable from random, including by the quantum computer in the question.


Is a using salt important when creating a hash data validator?

The answer to that depends on the details of your system, and specifically whether someone other than you can modify the hash.

If you store the hash in your database, and retrieve the expected hash value from your own database to compare it with the actual hash (when checking to make sure that those certain values have not been altered), there's no point in using the salt.  The only thing someone could try to do to fool you is to find a modification to the object in such a way that leaves the hash result the same; if you use a collision-resistant hash function, he won't be able to do that.

On the other hand, if you return the hash along with the set of objects, and at the end of processing, the hash will be sent back to your system along with the objects, well, one thing someone might do is modify the objects, and then modify the hash to reflect that change; because the hash function can be evaluated publicly, they can do that.

In this second case, introducing an unknown salt value certainly is one way to attempt to prevent this attack, but it's probably not the best.  What you really need in this case is a Messsage Authentication Code (MAC) instead of a hash; I would recommend using HMAC based on the hash function you're already using; it's only a constant amount slower than the hash function, and was designed specifically to be strong in this attack model.


If you're comfortable with the reasons for  alternative pipe construction I won't reiterate them.

Yes you're missing something, but it's not cryptographic.  It's just that informative artwork and graphic design is not the usual cryptographer's skill set.  So they bodge it as best they can.  So single lines can represent many things.  Sometimes they can mean a standard MD width of interim hash passing through, and sometimes they represent  twice the width.  The feature that gives it away is the finalisation function /output compression function.  If one of these exists, it suggests (graphically) that the interim hash width exceeds the input /output block widths and has to be reduced.

I understand your confusion.  Figure 3 of your The Wide-Pipe Hash: A Modified MD Hash seems to show yet another alternative type of wide pipe that you might call staggered.  This is my nomenclature for it as it's not specifically named, but I wouldn't call it standard wide pipe.  It seems to show iterated compression functions of input width IV + message and IV width output.  It's almost the fast wide pipe compression function mirrored.

The designers randomly try all sorts of weird stuff in order to improve the security of the total hash.  It's called incremental development and that's how things evolve.  So some of your examples are slightly different in form.  They just sometimes draw /explain it very badly but then they're not graphical artists.  Your wiki example doesn't name the wide pipe hash, so we don't know what the compression function is.  It is entirely possible that it keeps IV compression and message block compression entirely separate until finalisation.  But it's a clip art style image and not very detailed.  Between subtle variations on which bit is wider than the output block width and bad drawing, it's hard to figure it out.


It can be done using any method you have at your disposal. Obviously, the more efficient method you use, the more efficient your algorithm will be, but even using trial division will yield a significantly more efficient algorithm than if you used trial division for the entire factorisation. Algorithms based on elliptic curves are also commonly used since they are especially good at identifying small prime factors.

By the way, this is not directly related to cryptography so you may get better answers on Math.SE.


What is the best way to store sensitive information on the client?

What you want is basically impossible in this way. The crux of the matter is that if you want your application to access the encrypted data, your application needs to have the key in some shape or form.

Due to the limitations you mentioned, this key needs to be on the client machine, in the application's code or data files.

There are several ways to hide a key in the application's data.  But that is really "security through obscurity", e.g. no security at all. Because it won't protect the key against a persistent attacker who could e.g. single-step through your application's assembly code in a debugger to see how it is accessing the database.

To keep out casual snoopers, you could just compress the database before writing it to disk. To make snooper's lives more difficult, you could chop off the identifying header that most compression programs employ.

BTW, the existence of virtual machines makes snooping on an application easier and harder to detect than ever before. There are some tricks to detect wether your program is running under a debugger, in which case you could abort the program. But if that machine is virtual, the attacker could stop the VM at any time and trawl through that VM's memory at his leisure without your program being any the wiser.

Another thing to keep in mind is authentication. How does the client authenticate to the server when it wants to retrieve a database update? In other words, what is stopping an attacker from impersonating your application and requesting a complete copy of the database?


Does DES support different keys that lead to the same result?

The DES operation (both encryption and decryption) ignores the lsbit of each byte of the key. That is, if you flip any of the lsbits within the key, the operation remains the same.  That's what is happening in the keys you tried: the ASCII code for space is 0x20, while the ASCII code for ! is 0x21; they differ only in the lsbit.  So, if the key has a byte with the ASCII code for a space, you could replace it with a !, and it'll still be able to decrypt.  Similarly, the ASCII code for * is 0x2a, while the ASCII code for + is 0x2b; also differs only in the lsbit.

In the original DES standard, the lsbit was supposed to be used as a parity check bit (with each byte always having odd parity).  It was supposed to be a weak error check for manually entered keys.  Nowadays, no one does this parity check, and so the lsbit gets ignored.


How to calculate initial RC5 encryption parameters?

First: you should use addition, not XOR. Next, if you're doing this calculation with a computer, make sure you're processing the bytes as little-endian, and that you pad your key to the 16 bytes you mentioned:

4B726970 746F6772 61666900 00000000

Now, you have basically answered the question yourself of why you aren't getting the correct value:

  The S Data is the result of 3rd phase key expanding on RC5.

The formula A = A + S[0] is correct, but as you note there are multiple phases of mixing the $L$ and $S$ arrays. During the first phase, $A$ and $B$ look like:

i=1 A= **0xbf0a8b1d** B= **0x5ee7fad**
i=2 A= 0xd88eaf30 B= 0x2a1c93ca
i=3 A= 0xb7dc3e7f B= 0xc47155c4
...

These are the values on the right-hand side of the image you posted. The value 0xbf0a8b1d in particular is the one you've been trying to add. What you should be using are values from the 3rd phase:

i=1 A= **0x8ef5328b** B= **0x600e18b6**
i=2 A= 0x64aa69d0 B= 0x384a0d6
i=3 A= 0x7a471ae8 B= 0xd5a140fa
...

So now, take your plaintext word 0x4b726970 and add it to 0x8ef5328b, and you get the desired value of 0xda679b7b:

i=1 A= **0xda679bfb** B= 0xd9198a23 # before the loop even starts
i=2 A= 0x9637a9a8 B= 0x7e949194
i=3 A= 0x4ec0dda1 B= 0x299ed426
...

I followed Rivest's paper on RC5 and double-checked my values against a Python implementation. We don't do implementation details here, but that should answer why you haven't been able to match up to that example.


AES alternate equation for the S-Box affine transformation

That alternate form, I think, makes things even more confusing than the standard form.

Since the matrix involved is circulant, the affine part of the AES S-box can be represented as
$$
b_o = b_i \oplus (b_i \lll 1) \oplus (b_i \lll 2) \oplus (b_i \lll 3) \oplus (b_i \lll 4) \oplus 99\,,
$$
where $\oplus$ is xor and $\lll$ is bit left rotation. So far so good. But mathematically, it is awkward to describe rotation as "moving bits".

So instead, we can treat a byte as a polynomial with coefficients modulo 2, that is, $\mathbb{F}_{2}[x]$, and a byte is $x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0$, where the $c_i$ coefficients are the bits of the byte. What happens when we multiply by $x$? This is simply a left shift operation:
$$
x(x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0) = x^8\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0\,.
$$
Now, if we reduce this polynomial by $x^8 + 1$, which means that we replace $x^8$ by $1$ wherever available, we get
$$
1\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0 = x^7 \cdot c_6 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + c_7 \,,
$$
which is precisely a rotation left by $1$. You can verify that the same principle works for any rotation value: multiplying by $x^k$ and reducing by $x^8 + 1$ rotates the polynomial by $k$ positions.

Therefore, we can understand the affine transformation of the AES S-box as a multiplication in the ring $\mathbb{F}_{2}[x]/(x^8 + 1)$:
$$
b_o = b_i \cdot (1 + x + x^2 + x^3 + x^4) + 99 \in \mathbb{F}_{2}[x]/(x^8 + 1)\,.
$$
In other words, this modulus only exists to describe bit rotation cleanly, in an algebraic way.

Converted to decimal, this becomes $b_o = b_i \cdot 31 \bmod 257 \oplus 99 $, but that form, to me, loses all its descriptive value.


Firstly:

RSA is computationally complex algorithm and should not be used to encrypt large data. RSA keys can be created with trusted third party. But is the system is in house then you can generate few keys through following technique shown here.

However, it is not recommended to use static set of keys for RSA (as there are security trade offs for reusing the keys).

Secondly:

You can use nested algorithms to get work done as shown below:

say $data = packet$;

$$E = AES_{ENC}(K, data) \\
K' = RSA_{ENC}(PubK, K)$$

and then share the encrypted key publicly.

You can use AES with some popular working modes like CBC-MAC, CTR, CCM etc. to achieve decent security with less computational complexity (now you can encrypt more data in less time)

And RSA will make sure the public key(of underlying AES) is secure.

On the other end:

$$K = RSA_{DEC}(PubK, K') \\
packet = AES_{DEC}(K, data)$$

Finally, Implementing it efficiently in NS2.35 is out of scope for this forum.


Do the inverse over the field first, then the affine transform on that.

You must first invert $1010 = x^3 + x$ in $\textrm{GF}(16)$, with prime polynomial $x^4 + x + 1$; use the extended Euclidean algorithm for that, and see that $1100 = x^3+x^2$ is the inverse (you can verify this by computing their product and replacing all $x^4$ by $1+x$ an ditto for higher powers $x^5 = x^2+x$, $x^6 = x^3+x^2$ etc.; we are left with $1$, using $x+x=0$ etc.)

You can also make a log table based on the generator $x$:

$$
\begin{matrix}
0 & x^0 & 1 & 0001\\
1 & x^1 & x & 0010\\
2 & x^2  & x^2 & 0100\\
3 & x^3 & x^3 & 1000\\
4 & x^4 & 1+x & 0011\\
5 & x^5 & x^2+x & 0110\\
6 & x^6 & x^3 + x^2 & 1100\\
7 &  x^7 & x^3 + x + 1 & 1011\\
8 & x^8 & x^2 +1 & 0101\\
9 & x^9 & x^3+x & 1010\\
10 & x^{10} & x^2+x+1 & 0111\\
11 & x^{11} & x^3 + x^2 +x & 1110\\
12 & x^{12} & x^3 + x^2 +x + 1 & 1111\\
13 & x^{13} & x^3 + x^2 +1 & 1101\\
14 & x^{14} & x^3 + 1 & 1001\\
15 & x^{15} & 1 & 0001
\end{matrix}
$$
And note that $1010 = x^9$ so its inverse is $x^6 = 1100$ (as $x^{15} = 1$).

We then apply the affine transform over $F_2$ to $1100$, we get for the matrix multiplication as the sum of the first two columns with result $\begin{bmatrix}1\\1\\1\\0 \end{bmatrix}+ \begin{bmatrix}0\\1\\1\\1 \end{bmatrix}= \begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$

and adding the constant vector $\begin{bmatrix}1\\0\\0\\1 \end{bmatrix}$ to that we get $0000$, as required.

As an aside: $0000$ has no inverse, so we use the convention  that its "inverse" is $0000$ and into the affine transform this yields the constant vector $1001$, as the table says. The point of the affine tarnsform is to ensure the $S$-box defined by the (very nonlinear) inverse mapping does not have $0000$ as a fix point. The element $0001$ has $0001$ as its inverse, and then the matrix multiplication gives $1101$ (the last column) and so adding $1001$ gives $0100$ etc.


Confused about terminology in the many flavors of security

To explain, I'll exercise these models on an example, namely that of LoR-CPA-security.

The LoR-CPA game $\operatorname{Priv}^{\text{cpa}}_{\mathcal A,\Pi}(n)$ for a cipher $\Pi=(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$ and a security parameter $n$ against a probabilistic Oracle-Turing-Machine adversary $\mathcal A$ goes as follows:

$k\gets \operatorname{Gen}(1^n)$
Uniformly at random generate a bit $b\stackrel\$\gets\{0,1\}$
Define $\mathcal E(m_0,m_1)=\operatorname{Enc}_k(m_b)$
Run the adversary with encryption oracle access to $\mathcal E$: $b'\gets \mathcal A^{\mathcal E(\cdot,\cdot)}(1^n)$
Output 1 if $b=b'$ and else output $b$

Then we define the advantage $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,q,t,s)=2\cdot \Pr[\operatorname{Priv}^{\text{cpa}}_{\mathcal A,\Pi}(n)]-1$ where $\mathcal A$ must run in $t$ steps, only use $s$ cells of space and make at most $q$ queries to its oracle.

Now for the definitions:

Symbolic model: From what I gather from the linked paper (PDF) this would take the above definition and remove all occurences of the security parameter and runtime / space restrictions from all algorithms, which should be equivalent to the notion that the only thing you know / can learn is the correctness property.
Perfect Security / Information-theoretic security: They are the same and ask for a scheme that for all $n$: $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,\infty,\infty,\infty)=0$ holds. This is not always achievable.
Asymptotic Security: This one asks that there exists a negligible function $\varepsilon$ such that $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,\operatorname{poly}(n),\operatorname{poly}(n),\operatorname{poly}(n))\leq \varepsilon(n)$ for all $n$ larger than some $n_0$ and some polynomial $\operatorname{poly}$.
Concrete Security: This one demands a concrete relation / statement for the security of the scheme, i.e. there must exist some function $f$ such that $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,q,t,s)\leq f(n,q,t,s)$ and it is up to the user to judge whether $f$ is small enough for a given parameter set to be considered secure for their application. This is the preferred notion for non-complexity-theoretical results.

The computational model is then an umbrella term for the last three bullet points from above.
Computational security is usually an umbrella term for the last two bullet points from above.
Even though I used CPA-security as the example, the above applies to all security notions that define an advantage, except for the algebraic inference in the symbolic model.


What is the point of digital signatures if confidentiality is violated?

Digital signatures are not designed for confidentiality. For the simplest counterexample to the implicit conclusion that there is no point to digital signatures without confidentiality, consider the use of PGP signatures. People may sign a message that they send to a public mailing list, allowing others to verify that they indeed said that and not an imposter pretending to be them.
Also, you seem to be misunderstanding how digital signatures work. It is not encryption that you decrypt to verify. A digital signature is a mathematical operation on a hash of the message that you verify is valid for the message. You don't recover the message itself from the signature.


Is this password-cracking challenge possible?

Coming back to answer this since I see someone is wondering if I was able to do it.
The professor, seemingly realizing that this assignment wasn't possible in the time given, gave another hint that made this doable.

The plaintext is 8 characters long
The first character and last two characters are lowercase
There are two digits, and the rest of the password consists of only uppercase and lowercase letters (no symbols).
The second character is a digit

Using these criteria, there are only 12 possible arrangements for the remaining characters (characters three, four, five, and six, which contain a digit, two uppercase letters, and a lowercase letter.)
I made a list of the following masks in an .hcmask file, ran it through hashcat, and the crack now only took roughly eight hours.
?l?d?d?l?u?u?l?l
?l?d?d?u?l?u?l?l
?l?d?d?u?u?l?l?l

?l?d?l?d?u?u?l?l
?l?d?u?d?l?u?l?l
?l?d?u?d?u?l?l?l

?l?d?l?u?d?u?l?l
?l?d?u?l?d?u?l?l
?l?d?u?u?d?l?l?l

?l?d?l?u?u?d?l?l
?l?d?u?l?u?d?l?l
?l?d?u?u?l?d?l?l

The password ended up being cracked successfully: e3IDq9wv


Severity of Cooking NIST P Curve Constants

These are "red flags".  No one knows of a specific exploit, only some possible reasons to be concerned that one might exist.  Since no one knows of a specific attack, we can't possibly know how much speedup such a hypothetical attack might allow.  Basically, you're asking for speculation where there is not enough information to allow meaningful speculation, so there's no useful answer to your question.  Of course, if the curves are cooked, the sky is the limit: it could be arbitrarily bad.  So at this point, there's not a lot of hard data to make a risk management decision.


Is it possible to derive the encryption method from encrypted text?

If the encryption system is any good, then no. The output of a (symmetric) encryption algorithm is supposed to be indistinguishable from pure random. If you can distinguish encryption output from pure random with probability greater than 1/2 (i.e. you are given two strings of bits, and you can tell which one comes from an encryption system with better success on average than pure luck), then the encryption algorithm is said to be "broken". An example of such an algorithm is RC4 (not that being broken does not mean that decryption without the key is easy; RC4-protected SSL connections still appear to be mostly safe).

However, the used encryption algorithm is not generally supposed to be secret information. That algorithm exists as code or specific hardware somewhere; it is amenable to reverse engineering. It is very difficult to know how much algorithm secrecy may resist an attacker, and that's a problem since a good security policy should aim at quantifying things. Secrecy of a symmetric key can be quantified: a 128-bit key is secret up to 2127 (on average) trials. Since such a precise measure cannot be achieved for the algorithm itself, it is usually assumed that the name of the algorithm is known by everybody. Correspondingly, encrypted message formats often begin with an additional header which plainly states which algorithm is used (such a header avoids many maintenance headaches, especially when several distinct algorithms are in use).


What are methods of hash classification by finding patterns?

For your example, sure there is:

Precalculate the SHA hash of every number less than $2^{40}$.  Store those hashes in a database.
To check if a hash belong to a number less than $2^{40}$, look it up in the database.  If you find it, the answer is yes, otherwise no.

Sure, that'll take a bunch of precalculation and a rather large database, but it's quite possible to do with modern hardware.

You could optimize the database size a little, e.g. down to 80 bits per entry by only storing the first 40 bits of the hash and the 40-bit number that produced it, letting you verify the match by hashing the number.  Or you could even store just, say, the first 32 bits of each hash and a list of the all the (256 or so) numbers that produced it, getting down to only slightly over 40 bits per entry at the cost of 256 hash computations per lookup on average.  If you don't mind some occasional false positives, even more impressive space savings are possible e.g. using a Bloom filter.

In the general case, though, assuming that:

the groups you wish to distinguish are large enough that precalculating the hashes of all (or even most) elements of either of them is not practical, and
the definitions of the groups don't have anything to do with the hash function used (i.e. you may not choose "strings whose hash begins with a zero" as one of the groups),

then it is generally not feasible to determine which group a string belongs to just from its hash.

Note that resistance to this kind of "generalized preimage attack" does not follow from the standard preimage and collision resistance properties that a secure cryptographic hash is expected to satisfy.  Still, if anyone were to find an efficient distinguisher like that for a widely used hash, that would certainly be considered by most cryptographers a notable attack on the hash function.


Post-quantum alternative to ElGamal? (public key verifiability)

There is nothing quite meeting your requirements, especially if you require the ability to generate random valid public keys without knowing the corresponding private key. CSIDH (not a NIST candidate) comes closest, in that you can at least generate random private keys and easily publish the corresponding public keys verifiably.


In the Paillier cryptosystem, is there a method to judge whether an encrypted number is less than 0 (without the private key)

In Paillier, if it were possible to determine whether an encrypted number is less than 0 (that is, is equivalent modulo N to a value $x$ where $N/2 < x < N$), then it would be possible to decrypt arbitrary encrypted values with only the public key.  That is, if someone found such a method, they will have broken Paillier as a public key system.

The details are fairly straight-forward; to compare an encrypted value $E(x)$ against a known value $y$, you compute $E(y)$, use the homomorphic property to compute the value $E(x+y)$, and then use your blockbox to determine from this value whether $x+y<0$

Hence, you can use binary searching, using the above method as the comparison method, to recover the value $x$ given $E(x)$, using $O(\log N)$ probes.


Why ssh-gen makes difference between PEM and PKCS8?

Oh, I have found an answer. PEM here is PKCS#1 (RSA) key. Not sure why ssh-keygen used this terminology.  And PKCS#8 could be used for Public keys as well since RFC-5958 which obsoletes RFC-5208. A very good article is https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem and this question is also good: https://stackoverflow.com/questions/20065304/what-is-the-differences-between-begin-rsa-private-key-and-begin-private-key

Here is PKCS#1(RSA):

[foo@bar ~]$ ssh-keygen -f .ssh/authorized_keys -e -m PEM
-----BEGIN RSA PUBLIC KEY-----
MIIBCgKCAQEApPGAMzobORnBJdPD0VvBif0cBkRC1KgTi4rDmscp+4F8Ke6nE/jE
.....
rf/DnkvPoJPiRLBnyjmyWsQ0dWHnRbSZSwIDAQAB
-----END RSA PUBLIC KEY-----

And here is PKCS#8

[foo@bar ~]$ ssh-keygen -f .ssh/authorized_keys -e -m PKCS8
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEApPGAMzobORnBJdPD0VvB
...
yk/avnG/lceGqChXgjxcHEKQRJYZRTnqrf/DnkvPoJPiRLBnyjmyWsQ0dWHnRbSZ
SwIDAQAB
-----END PUBLIC KEY-----