Efficient hardware implementation of real-time asymmetric video encryption

Would you recommend the video stream being compressed before being
  encrypted?

This is an excellent question in itself. What compression does, it recognizes redundancies in the data and removes those. So it changes the length of the data as a function of its value. Now cryptography doesn't promise to hide the length of the transmitted data, because that would be an impossible goal to achieve. So an outside attacker, could now go ahead and deduce some information about the plaintext, through the encryption, simply by looking at the length and frequency of packet transmissions. This in fact has been a famous attack, called CRIME, and has lead to TLS abandoning compression at the security protocol level. So you have to evaluate yourself whether the trade-off of leakage versus size gains is worth it to you.

Of course, with video being nicely encode-able with lossy methods, you can get a constant bit-rate encoding, where each unit of time of video material is encoded to the same unit of bit-output. As indicated in the other answers and the comments, this should leak very little to no information.

Now for your actual question:
(Hybrid) McEliece

McEliece is an old code-based signature scheme. It encrypts data by running it (as a vector) through a matrix-vector multiplication and then adds a limited amount of noise to the result. The decryption is more involved and essentially works off of error correction codes being applied to remove these errors. So let's go through things to figure out why it would be a good pick:

It is insanely fast. As you read above, it's simply a binary matrix-vector multiplication and a binary vector addition with some carefully generated noise. As such it is essentially, naturally, a lagre bunch of AND and XOR gates along with the output of a HW RNG, which can be built to be quite fast somewhat easily.
It is post-quantum resistant. McEliece (well, variants of it) are currently considered for the NIST post-quantum competition and McEliece has stood the test of time against quantum algorithms for a few decades now.
It has a large public key. Given that you don't actually seem to want to transmit the public key, this shouldn't be a problem in your case and even then, you mostly transmit video data, an extra Megabyte for the public key won't end the world.
Decryption is somewhat complicated. But this doesn't seem to be much of an issue for you, as far as I can tell.
It is rather badly supported. That is, it is used very sparsely. Given that you roll your own ASIC, you seem to be able to set your own standard here, but make sure to run things through proper cryptographers and don't just take the word of a random internet potato!
It lacks a lot of standardisation. When you use it "raw", that is not for some hybrid encryption as would be usual these days, you need to look around a bit to find a padding scheme that makes McEliece IND-CCA2 secure, which is really a security notion you want, but again, consult a proper cryptographer on this!

Now for your actual problem: The slow speed of asymmetric cryptogaphy. Well, there the solution of hybrid encryption. That is you take your favourite encryption scheme (such as McEliece), encrypt a lot of random bytes with it, prepend the ciphertext to the message and use the hash of the bytes as the key for authenticated symmetric encryption. This has the advantage that you can now keep the key for a (short) period of time in volatile registers and use the fast symmetric crypto to do the bulk of the work. Of course you can also pair hybrid encryption with slow asymmetric crypto such as RSA and just continuesly run the RSA encryption in a loop, generating a new session key once a second or so. The advantage of the hybrid encryption is that you need to spend less area on the asymmetric crypto (because you need less parallel instances / less area-time-trade-offs) and more on your actual logic and of course the fact, that you should have no problem finding pre-made IP for such symmetric encryption modules.


What if OT breaks in Yao's garbled circuit?

The problem is because sender has provided the receiver with a garbled circuit in which the sender's inputs are hard coded (or has provided keys for those inputs, which is morally the same).  If the receiver has both keys for each input wire then it is trivial to narrow down the possible values of the sender's input.

Consider a concrete example, the millioniar's problem.  In this problem the sender constructs a circuit that returns $1$ if the resulting value is less than or equal to the sender's wealth.  If the receiver has the circuit and all input keys then it effectively has a function $f : Z_n \rightarrow Z_2$.  Through trial and error we can find the sender's wealth, $X \in Z_n$ where $f(X) = 1 \wedge f(X+1) = 0$.


Why does BCRYPT_RNG_DUAL_EC_ALGORITHM get removed from CNG API on Windows 10?

The Government's elliptic curve backdoor is real, isn't it?

We don't know for sure, but there are indicators into that direction. More importantly though,

yes, you can backdoor the RNG, as was pointed out shortly after its publication (PDF)
yes, the parameters have been replaced in-the-wild by attackers to break VPN appliances using this RNG.

  Does this imply that Elliptic Curve PRNG is considered unsecure
  already?

As you saw above, using Dual-EC can be a real exploitable risk. There are however additional reasons why Dual-EC isn't the greatest random number generator and why people wouldn't want to use it:

It's no longer in the list of NIST specified RNGs and was removed from SP 800-90A rev.1.
It's very slow compared to all the other "approved" RNGs (like three orders of magnitude slower).
It doesn't even have a security proof, which is the only reason why you would want to use such a slow RNG in the first place and more specifically...
It's output is actually distinguishable from random (which is like the bare minimum of a security guarantee no RNG should violate)!

So TL;DR: Yes, the Dual-EC is backdoorable and slow and not even properly random and was probably dropped because of that.

Additional reading: Matthew Green's blog post on the subject (which is also a source for this answer) as well as Bernstein's, Lange's and Niederhagen's "Dual EC: A Standardized Back Door".


Factoring two RSA modulus with known $|p_1 - p_2| < \ell $

Outline of a elementary attack:

if $\mid p_i-q_i \leq 2^s$, we can write for each $p_i=a.2^s+\tau_i$, with  $\tau_i \leq 2^s$, and we can imagine that if we determine the integer a, we can factor $N_i$ by a brute force attack.
We know that $p_i$ have exactly the same bit size and if $N_i$ have exactly the same bit size (n=1024, 2048, ... s=64), the sizes of $q_i$ could differ by at most one.

Let $r=\frac{a.2^s+\tau_1}{a.2^s+\tau_2} \approx 1 + \frac{1}{a} \pm \epsilon$.
And $\rho=\frac{N_1}{N_2} \approx (1 + \frac{1}{a} \pm f(\epsilon))\times \frac{q_1}{q_2}$ is a rational number which can be determined with a infinite precision.

Then by the examination of the bit of this ratio we can get information on the unknow number a, and hope to success in the factorisation Pb, in complexity less than the general know attacks.

Probably with the help of LLL algo we can enhance the attack.


Can a message and one time pad each encrypted with separate ciphers be weaker than the stronger of either cipher?

No, it can cannot be less secure. The proof is simple: if P is ever found out then the security of the strong cipher still protects $P \oplus M$ and thus $M$.

However if the one-time-pad $P$ ever leaks then it can be used to break the weak cipher, and in that case the result is just as secure as the strong cipher. It is generally not a good idea to rely on data to be kept secret forever. And it is certainly not a good idea to rely on security that may or may not be present.

Outside of theoretical security, the weak cipher may also have issues with e.g. padding oracle attacks that could leak $P$, in which case only the strong cipher will be left.

All in all, without additional details, I would rate this about as secure as the strong cipher, so the one time pad doesn't seem to have much benefit (certainly compared to, for instance, frequently using fresh keys).


Computational Diffie-Hellman problem over the group of quadratic residues

That depends entirely on the size of $p$ and $q$.

Given a factorization of $N = pq$, an attacker can compute $g^u \bmod p$ and $g^v \bmod p$, and then attempt to solve the CDH problem modulo $p$, giving him $g^{uv} \bmod p$.

Then, he can then compute $g^u \bmod q$ and $g^v \bmod q$, and then attempt to solve the CDH problem modulo $q$, giving him $g^{uv} \bmod q$.

Then, he can combine them to form $g^{uv} \bmod pq$.

The only parts that might not be straightforward is the CDH problem modulo $p$ and $q$ -- if one if the two primes is large enough to make this infeasible, then he cannot do that (and conversely, if he cannot solve the CDH problem modulo $p$, he obviously cannot solve it modulo $pq$.


Generate an insecure public / private key pair

I am not sure to fully understand your question, but what you can do is the following: take $r=2^{512}$, and compute $p=r+\delta$ and $q=r-\delta^\prime$ such that $p$ and $q$ are prime numbers, and $0\leq \delta, \delta^\prime < 2^{32}$. Then you have an RSA key at you disposal that can be broken by a brute force search on $\delta$, which should take strictly less than $2^{32}$ trials.


AES-128 (cbc mode), is it possible to deduce the IV if the plaintext, ciphertext and key are known?

By the formal modern definition of a cipher, the ciphertext and key should be all that's necessary to decipher, thus the IV of CBC should be in the ciphertext (often it is in the first block of ciphertext).

However the original description of CBC disagree and treat IV as a separate.

For the later situation, and assuming IV is not available (which suggests an exercise rather than a real situation), hint: write down the relation between IV, plaintext, ciphertext, and key by the definition of CBC; apply to the first block of plaintext; and use properties of bitwise exclusive-OR (commutativity, associativity, each element is its own inverse), and the defining property of a block cipher like AES-128 (that for fixed key, it is an easily reversible bijection of the block space).


Does the Shappening mean HTTPS can be broken?

SHA1 certificate is getting weaker because computing power grows to Moore's Law. According to Jesse Walker, who made a back of the envelope calculation of the cost of SHA1 collision attack:

  the cost of the attack will be approximately:

  \$2.77M in 2012
  \$700K by 2015
  \$173K by 2018
  \$43K by 2021

  A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021.

To your question:

  What are the practical 'something bad's?

The practical "something bad" is that sometime this year, all major browser vendors (Google, Firefox, Microsoft) would distrust sha1 certificate. This means that your site/servers will be blocked with a big security warning, it might actually be more sensible to not use HTTPS at all than to use SHA1 certificate at that point. Some browsers now already no longer shows the secure lock icon on sites with SHA1 certificate.

  Once an attacker has the capability to create a SHA-1 collision, what then can they do?

Certificate signature is made by taking a hash of the public key and attached data (owner identity and Common Name/SAN) and then the CA signing that hash with the CA's private key.

If you generate two keypairs with the same SHA1 signature, you can convince a CA to sign one of the public key and that signature will also be valid for the other key. From there on, it's a simple matter to implant the CA's signature on the second certificate. That second certificate could be for a different domain that you don't actually control.


zero knowledge framework for c programs - how to prove correct C program execution with private inputs

pepper project does not lack private input functionality. It does support that with exo_compute method. Probably it didn't when you asked the question, but now it does.

Check here for more details about exo_compute. Also, I have implemented in a pull-request the scenario you mentioned where a prover knows the pre-image of a hash function and he/she does not disclose it to the verifier. See here for the source code and here for more details about the PR.


Many consecutive hashes to slow down brute force attack?

Instead of that home-grown scheme, I would use PBKDF2 instead if you simply are sold on the idea of iterated hash schemes. It uses an such a scheme, although not exactly the one you have described, and is well-studied and considered secure.

However, PBKDF2 doesn't offer many advantages over bcrypt, as PBKDF2 is still vulnerable to GPU and FPGA/ASIC brute-force attacks. bcrypt resists GPU brute-forcing because of the 4K table used in the algorithm, which forces contention for the global memory bus in GPUs. But bcrypt is still potentially vulnerable to FPGA/ASIC attacks, although most people don't have to worry about that.

A newer KDF, scrypt, is also tunable for the amount of memory it uses, so it is more resistant (when properly tuned) to FPGA/ASIC attacks than bcrypt. However, scrypt is relatively new (2009) when compared to bcrypt (1999), so that may make you somewhat nervous.

Essentially, to store passwords, you should be probably using bcrypt, since it seems to hit a sweet spot of being GPU resistant as well as being sufficiently mature. But PBKDF2 and scrypt are still good; using any one of the three is really fine.

For more information, I would recommend looking at the following question which has an (excellent) top answer by Thomas Pornin: Do any security experts recommend bcrypt for password storage? He is infinitely more credentialed than I am, so if you don't believe me, hopefully his testimony will be compelling.


What impact does the hash function have on the randomness of the resulting pseudorandom number?

None.  A good cryptographic hash function like the ones you mention will  produce output that is uniformly distributed random.  Given a long stream of output, you will not be able to identify what hash function was used.  The actual stream of numbers will however totally change if you change the hash, but they'll all be just as random.  It should still be impossible to distinguish a good PRNG's output from true randomness, no matter how much effort you use.

  For example, SHA1 suffers from proven hash collisions. Does that impact the pseudorandom number?

That's a highly contrived example in a very particular situation.  We're not at the stage yet where we can immediately invert a SHA-1 output to determine the input.  And actually, collisions in a PRNG output are nothing to be feared.  You would expect these to occur naturally (but infrequently) as you produce the output.  Random numbers repeat sometimes.  What's important is that again given a  long sequence of output, we can't at the moment discover the input sequence and therefore the generator's internal state.

  Would SHA2 be considered more secure or is the impact of the hash function not that crucial on the randomness?

At this stage, it doesn't make a difference.  /dev/random and Java's SecureRandom still use SHA-1 mixing functions and they're considered unbroken.  If you specifically focus on the randomness, that's not a direct product of cryptographic security and invert ability.  It's a  function of the avalanche effect.  Any hash function that exhibits the avalanche effect will generate perfect random output.  For  example a simple algorithm based on a substitution permutation network or matrix multiplication will produce perfectly random output.  You'll just be able to invert it and therefore those wouldn't be suitable as cryptographic PRNGs.


Attack XOR encryption of binary data compressed by zlib with known key length (very short key)

If you have known plaintext, namely one input file that is known in its entirety, this is trivial to break.  So I'll explore methods that might lead to a break, if you don't know what's in the input file that was compressed.

I suggest that you start by analyzing the DEFLATE stream format carefully (see also these handy notes).  This will probably help you derive some consistent relationships that the first handful of bits of the DEFLATE stream must satisfy.

On first glance, it looks to me like the beginning of the DEFLATE stream has the following structure:

As Stephen Tousot explains, in normal operation the first 3 bits of the DEFLATE stream are likely to be 110.  (You may want to double-check this with the compression program you are using.)
The next three fields are HLIT (5 bits), HDIST (5 bits), and HCLEN (4 bits).  I suggest that you take a bunch of sample inputs that would be typical for your application, compress them with the compression implementation you're using, and look at the typical range of values for HLIT, HDIST, and HCLEN in the resulting DEFLATE stream.  I suspect you may find that not all values are equally likely.
After the aforementioned 17 bits is a chunk of 3*(HCLEN+4) bits, which is interpreted as a sequence of 3-bit values.  If I understand the DEFLATE algorithm correctly (and I might not), if you permute these appropriately using a fixed permutation found in the DEFLATE specification and ignore all 000-values, then the remaining 3-bit values should be in sorted order.  This provides an additional constraint on possible values for those bits.
Then there's some more stuff that I'm ignoring right now.

For example, if HCLEN=15, then the first three items above account for the first 74 bits of the DEFLATE stream.  And, if I understand correctly, above structure imposes some consistency relationships on the bits: not all possible 74-bit sequences are possible (and not all possible ones are equally likely).

Now, I think you could use the following procedure to try to recover the key $K$.

For each candidate value of the 64-bit key $K$, xor it against the first 64 bits of ciphertext to obtain $Y = C\oplus K$, a guess at the 64 bits of the DEFLATE stream.  Check to see if $Y$ is consistent with the above-mentioned constraints.  If it is not consistent, continue on to the next candidate for $K$.
If it is consistent, then do a trial decryption of the entire ciphertext using $K$ (i.e., xor a repeated version of $K$ against the ciphertext, then decompress).  See if the resulting plaintext looks like a plausible input.  If yes, you may have found the key $K$.  If not, continue on to the next candidate.

As described, this method would take $2^{64}$ iterations of the loop.  However, I suspect you might be able to speed it up if you are a bit clever about how you check keys $K$.  Rather than iterating over all possible 64-bit values one-by-one, I think you can use a tree-like iterative-deepening method.  The idea is, roughly, if you reject a (say) 17-bit prefix of $K$ as impossible, then there is no need to try any of the keys that start with that prefix.  So, an optimized algorithm might first check all candidate values for the first 17 bits of $K$ (say) to see which ones look consistent, then for each 17-bit prefix that survives, you look to find all plausible ways to extend it by 3 bits, and so on, repeating at each step.

I don't know what the running time of this more sophisticated algorithm will be, but if you study the DEFLATE format carefully and are able to identify enough consistency checks on the first 64 bits of the DEFLATE stream, you might be able to make this attack run efficiently enough to be practical.

I realize I haven't worked out all the details for you -- I've left something for you to do on your own.  But hopefully this gets you started and gives you some ideas for a direction that might lead to a practical attack.


Does RSA operate over a Finite Field (Galois Field)?

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are invertible, as their representants are coprime to $n=pq$).


Example of product cipher more secure than its components

For

a $1$-bit message $m$
a randomly generated, fixed prime $k$ (the key)
per-ciphertext randomly generated $r$ and/or $e$

C1, C2

$$C_1 : (k * r) + m$$
$$C_2 : (2 * e) + m$$

A1, A2

$$\begin{align}A_1(c_0, c_1) : c' = c_0 - m_0\\c'' = c_1 - m_1\\k = \operatorname{gcd}(c', c'') = \operatorname{gcd}(k*r_0, k*r_1)\end{align}$$
$$\begin{align}A_2(c_0) : m = c_0 \bmod 2\end{align}$$

C12

$$C_{(12)} : (k * r) + (2 * e) + m$$
$$A_{(12)} : \text{Solve the AGCD problem}$$

Notes

Attacks assume the known-plaintext attack scenario
$C_2$ by itself might be considered a pathological example by itself, but as you can see above, when combined with some $C_1$ it contributes immensely to security.
$A_1$ might require multiple applications if $k$ is not prime


How do I generate a challenge for elliptic curve signing using NIST standards?

I believe you're misunderstanding how ECDSA works.

When you sign a message with RSA, you pad out the message somehow; some padding methods are determanistic, and some are randomized.  However, once you get this padded message, you present it to the underlying RSA private operation, which is entirely determanistic.

However, ECDSA isn't like that.  Instead, the ECDSA private operation selects a value k; this value k is not the message being signed, instead it's a random value (and there are known attacks that can occur if it's biased; that's why FIPS 186 goes into such detail about exactly how you do it - if you ignore their advice without knowing what you're doing, well, there be dragons here).

Now, once you have the value k, you can take the message (actually, the hash of the message), and then present that to the ECDSA signature operation to generate the signature.

So, with ECDSA, there is a hash involved; however it's the message that is hashed, not k.


If the output domain is large enough so that the probability of getting a collision in the PRF is negligible, then the output of a PRP and PRF are indistinguishable. Thus, in principle, the answer is yes - you can interchange these freely (under the above condition).

Having said that, it's unclear to me why you would want a non-invertible PRP rather than a PRF. Typically, a PRF is better for cryptographic constructions, being easier to analyze and giving better bounds, and the only time we use a PRP is when we want to invert. Maybe there is an example of a use of a PRP specifically when inversion is not needed, but I don't think I've ever seen one (and can't really think of where it would be helpful).


In CPA, how does one-message security implies multi-message security?

For the CPA game, we play the following experiment

Generate a key $k$ with the security parameter $n$
The adversary $\mathcal{A}$ is given the $n$, Oracle access to the encryption oracle $Enc_k(\cdot)$
$\mathcal{A}$ outputs two messages $m_1$ and $m_2$ of the same length ( here, there is no restriction about $m_0 \neq m_1$)
A random bit is chosen $b \overset{R}\leftarrow \{0,1\}$ the the ciphertext $c = Enc_k(m_b)$ is computed and trasnmitted to $\mathcal{A}$. This is called the challange ciphertext.
$\mathcal{A}$ access to the encryption oracle $Enc_k(\cdot)$ ( even before  submitting)
And, finally, $\mathcal{A}$ submits $b'$ as their candidate
The output of the experiment is defined to be $1$ if $b' = b$ and $0$ otherwise. If the output is $1$, we also say that $\mathcal{A}$ succeeds.

Then we can make the definition of $Ind\text{-}CPA$ as;
An encryption scheme is  $Ind\text{-}CPA$ if for all probabilistic polynomial-time adversaries  $\mathcal{A}$ the advantage is negligible $negl(n)$
Notes:

The negligible is depends on the security parameter $n$
There is no restriction for submitting the same messages. The adversary must find the correct $b$.
If you send two identical messages there is no advantage since the adversary will not learn anything.
CPA security requires randomized encryption. Deterministic encryption like ECB mode cannot have CPA security.
The experiment also requires a good random number generator.
In public-key cryptography, the encryption oracle  $Enc_k(\cdot)$ is free. One can access all the time they have, consider encrypting with RSA's public key.
The key is fixed during the experiment (Step 1)

However, if A sends two identical messages, say 'm', to C, A would definitely know the encrypted 'm' by the returned text of C. Then, for the second time, A can send a 'm' and any other message to C, then, if the returned text of C is the same as that of the returned text when inputting 'm', the message chosen by C is 'm', otherwise is that any other message. And this enables A to have a probability of 1 to guess the chosen message of C.

You know the $m$ but which $b'$ will you submit to win the game?
For the second time the encryption of the $m$ will change since the CPA game requires randomized encryption, in other terms any CPA-secure encryption scheme must be probabilistic. In which, random coins tossed in order to ensure that two encryption of the same message is different.


You are probably looking for what is called "anonymous credentials".

An anonymous credentials system relates three types of parties: authorities, users, and verifiers. An authority (Alice) can issue a credential to a user (Bob), that certifies that the user satisfies some property (in your case, that would be "is trusted"). Credentials are unforgeable. Then, that user (Bob) can prove to a verifier (Peter) that it possesses the credential, without revealing anything about himself other than the possession of the credential (anonymity), even if the verifier colludes with other verifiers and/or the authority.

The way anonymous credentials systems are typically implemented is that a user has a single private key sk, and multiple corresponding public keys pk, pk', etc. (pseudonyms) that can be generated on the fly as randomized commitments on sk. Then, the credential issuing protocol is a special kind of signature scheme that produces a signature on the value inside the commitment; in that way, Bob can obtain a credential from Alice via his pseudonym Bob-Work, and prove possession of it under his pseudonym Bob-Friends, in such a way that the two pseudonyms cannot be linked to each other.

A good general introduction to anonymous credentials is Anna Lysanskaya's Ph.D. thesis, especially chapter 3.

Since 2002, there has been quite a bit of research and progress on anonymous credentials, so we have efficient instantiations supporting additional features like revocation or delegation.


Zero Knowledge Proof AND Diffie Helmann?

From my research, I think what everything says is that the result of a zero knowledge proof (ZKP) is that the participants end up with a shared secret
  …
  If I just got a secure key from the ZKP - why do I need DH? Why don't I just expand the ZKP result and go from there?

You obviously misunderstood ZKP at its core.

Zero knowledge proofs are interactive or non-interactive protocols or schemes for proving membership of a common input in a formal language (or the analogous thing for promise problems).

In the basic ZKP setting, there are only two parties, in which case something that is unknown to one party is simply not a shared secret. For proofs (or for arguments), the verifier is only necessarily convinced that a valid secret exists, not that the prover has one. Also see proofs of knowledge.


What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

Looking at appendix A of the eprint I'd say that the authors call a polynomial of algebraic degree at most $2$ bi-affine, if it contains some terms of algebraic degree $1$, and fully quadratic, if there are no such terms.

(Working over fields of characteristic $2$ the map $x\mapsto x^2$ is linear over the field with two elements and of algebraic degree $1$.)


Disk encryption using AES-CBC: is reliance on previous block data a downside?

As you know, it makes reading and writing the disk very slow if all the data in the drive is chained together. If so, writing to a drive of size $n$ at position $p$ will require $\Theta (n-p)$ time. One solution is the drive being divided into sectors, and each sector being chained. The IV of each sector can be attained using ESSIV. it generates IVs from a combination of the sector number with the hash of the key. This method is used in dm-crypt, OpenBSD's swap encryption, and FreeOTFE.


The MAC under attack is built from a hash $h$ (assumed to process a hashed message by splitting it in blocks processed only once, as most hashes do), with a key split into $K_1$ and $K_2$ of equal size. It computes the MAC of a message $x$ as $$\operatorname{MAC}_{K_1\mathbin\|K_2}(x)=h(K_1\mathbin\|x\mathbin\|K_2)$$

The attack in the paper recovers $K_1$ and $K_2$ from an oracle accepting to compute the MAC, in 3 steps

We make online queries to the oracle until we find $x$ and $x'$ with the same MAC, and such that this occurs due to a hash state collision before $K_2$ is hashed. The later condition is testable by a few extra queries to the oracle. It is chosen $x=x_1\mathbin\|x_2$ with a hash block frontier between $x_1$ and $x_2$, with $x_1$ large enough to find a collision, and $x_2$ used to test for a hash collision before the frontier, per the criteria that if $h(K_1\mathbin\|x_1\mathbin\|x_2\mathbin\|K_2)=h(K_1\mathbin\|x_1'\mathbin\|x_2\mathbin\|K_2)$ for a few distinct values of $x_2$, then most likely there was a hash state collision before the frontier.
We find $K_1$ by offline exhaustive search, with the selection criteria that $h(K_1\mathbin\|x)=h(K_1\mathbin\|x')$ (changing $x_2$ and/or using a second collision similar to that in 1 to weed out false positives).
We find $K_2$ by offline exhaustive search, with the selection criteria of computing the correct MAC for a few examples kept from step 1.

For a hash with $s$ bits of internal state at block boundaries and a key of $k$ bits, step 1 costs $\mathcal O(2^{s/2})$ oracle queries, and steps 2/3 costs $\mathcal O(2^{k/2})$ hash computations. Truncating the MAC width to a fraction of $s$ increases the attack cost, but does not change these asymptotics.

The attack is practical if $s=64$, $k=128$, and it can be made $2^{32}$ oracle queries.


what benefits quantum offer over classical parallelism

1. What is the benefits of quantum computing vs parallel processing using classical computer?

The answer is in terms of Cryptography;

Quantum Computing (QC)

Key search on Block ciphers;  Grover's algorithm is a brute-force quantum algorithm with complexity $\mathcal{O}(\sqrt{N})$ with asymptotically optimal on unstructured data.
Public key algorithms;

RSA factorization problem; Shor's algorithm can efficiently factor integer $n$ in $\mathcal{O}((\log n)^2(\log \log n)(\log \log \log n)$
Discrete logarithm problem; Shor's algorithm can efficiently solve.

Therefore, RSA, Diffie–Hellman, and Elliptic Curve Diffie–Hellman could be broken easily.

Parallelization

Parallel computing in keys searches only help linear time whereas using single QC already gives quadratic speed up. Examples are Distributed.net, DES Cracker, COPACOBANA hashcat
Parallel computing is used in factorization algorithms where the help again is linear with complexity;

General Number Field Sieve with superpolynomial scaling: $$\mathcal{O}(exp [ c (\ln n)^{1/3} (\ln \ln n)^{2/3}])$$

  2. Can classical parallel processors outperform quantum computing?

Firstly, quantum give new complexity classes;

  The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time".7

  BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP.

Some $NP$ problems can be solved efficiently.

A Turing machine can simulate a QC and QC can simulate A Trung machine too,. So, once A QC is built, you can outperform a QC only by money.

Cost2

An important subject is also the cost of running the algoriths.

Daniel J. Bernstein asked the question in "Cost analysis of hash collisions: Will quantum computers make SHARCS1 obsolete". Some results if a QC is built;

Factorization; QC much more scalable and much more cost effective

The number-field sieve factors b-bit RSA moduli in time $2^{b^{1/3+\mathcal{o}(1)}}$
If a QC can be built for $b^{\mathcal{\Theta}(1)}$ Euros can factor b-bit integer in $b^{\mathcal{\Theta}(1)}$ seconds.

Pre-Image Search;

Traditional hardware can find in $2^bh$ operations
Quantum; much more cost effective

Grover $2^{b/2}h$ operations on $\mathcal{\Theta}(h)$ qubits.
Shor’s speedup from $2^{b^{1/3+\mathcal{o}(1)}}$ to $b^{\mathcal{\Theta}(1)}$

Collision search; He claims that all quantum algorithms upto his paper are less cost-effective than the traditional.
Parallelization
A size-$M$ machine finds collisions in time roughly $2^b/M^{3/2}$. if size $2^{b/3}$ than collision time is $2^{b/2}$ with $\epsilon$ time with $\epsilon$ probability.
a size-M QC after $2^{b/2}h\epsilon$ quantum operations each unit has $\epsilon^2$ success probability. After $2^{b/2}h/M^{1/2}$ total quantum operations the size-M machine has $M\epsilon^2$ success probability. If the size a quantum computer is $2^{b/3}$ then the time for finding collisions is approximately $2^{b/3}$. Compare to classical.

and he added;

  Anyone afraid of quantum hash-collision algorithms already has much more
   to fear from non-quantum hash-collision algorithms.

1 Special-Purpose Hardware for Attacking Cryptographic
Systems

2 Special Thanks to Ella-Rose for the article.


While SHA2 (SHA-256, SHA-512) original design goals are limited to collision-resistance and (first and second) preimage resistance, it is not known that its computationally distinguishable from a random oracle for messages of fixed length¹. Thus $\text{SHA2}(\text{seed}+n)$ for incremental $n$ is a CSPRNG as far as we know, for a wide-enough random secret seed. If we generate $2^k$ outputs, and $+$ is addition², we need $b+k$ bits of $\text{seed}$ for $b$-bit security.
For added insurance, one could use $\text{HMAC-SHA2}(\text{key}\gets \text{seed},\text{message}\gets n)$, which requires very little extra code. Mihir Bellare's New Proofs for NMAC and HMAC: Security Without Collision-Resistance gives an argument of security³ for weaker assumption on the compression function. Main drawback is that HMAC requires more evaluations of the compression function for each output (four for a simple implementation, possibly down to two with precomputation).
I would use HMAC, with SHA-512 rather than SHA-256 for $b>120$ bit security, or/and truncate the output or XOR its two halves (which can only help security), just to err on the safe side.

Any of the above constructions has the drawback that earlier output can be found at little cost if the state of the generator is recovered.
Beware that an adversary having access to the embedded system could try to extract the random secret seed (using a JTAG port, probing, side-channel attack…), or replace it with a known value (e.g. erase that area of remanent storage).
Also, I emphasize that it is difficult to make a robust incremental $n$ facing adversaries that can cut the power at any time of their choice.
Any of the above three paragraphs might be enough to justify the complications of a TRNG with cryptographic strengthening (CSTRNG).

¹ This restriction is necessary due to the length-extension property.
² Concatenation is more usually noted $\mathbin\|$. In that case, we only need a $b$-bit seed.
³ With security level half the hash width, or the width of $\text{seed}$, whichever is lowest.


Implementing PKCS#7 Padding on a Stream of Unknown Length?

Bit padding, PKCS#5 padding and PKCS#7 padding are always applied, and they are always applied to the end of the plaintext. The last block of ciphertext will always contain the padding. The padding is always 1 to [blocksize] bytes, which in case of AES is 1 to 16 bytes.

For PKCS#5 padding and PKCS#7 padding - which are basically identical - the value of the padding bytes is equal to the length of the padding. So you would get values 10, 0F, 0E to 01 (in hexadecimals) for ciphertext lengths Z*16 + 0, 1, 2 to 15 respectively.

To unpad quickly simply read the last byte of the decrypted ciphertext, and remove that number of bytes (not characters) from the end of the plain text.

Notes:

It is possible to verify the other padding bytes, as long as the padding bytes themselves are not used to verify the correctness of the data;
It is only possible to unpad at the end of the ciphertext but it is not possible to use the padding bytes to detect the end of the ciphertext (unless the padding is clearly distinct from the plain text);
Please know of and beware of padding oracle attacks.


How to calculate the order of the subgroup?

Run Schoof's algorithm on the curve parameters to find $qh$, and divide by $h$.

The size $p$ of the coordinate field is only required, by Hasse's theorem, to be near $qh$, within a factor of a square root: $|qh - (p + 1)| \leq 2 \sqrt p$.  Consequently, $p/h$ may be near $q$ but is not equal to $q$ except in anomalous curves in which ECDLP is easily solved by additive transfers as described by Smart (preprint), Araki–Satoh, and Semaev (the ‘Smart-ASS’ attack).

For example, Curve25519's coordinate field is $\operatorname{GF}(2^{255} - 19)$, and its order $2^{255} + 221938542218978828286815502327069187944 = qh$ where $q = 2^{252} + 27742317777372353535851937790883648493$ and $h = 8$.


How is Diffie Helman secure when the exchanged number is a power of the generator less than the modulo

If $g^a<p$, then the discrete logarithm mod $p$ becomes plain logarithm, even for a 2048-bit $p$. So, you are right that in this case $a$ can be easily computed from $g^a$. However, this is not bad because there are only at most $\log_2 p$ such $a$s (that satisfy $g^a<p$). Compared to $p$, $\log_2 p$ is a negligible number. In other words, since $a$ is chosen uniformly at random from $p-1$ values, the probability that it falls into the first $\log_2 p$ values is negligible (in $\log_2 p$, the bit length of $p$).


Birthday-attack calculation in planning password salting strategy

Yes! I'd recommend at least 64 bits, but that's only because powers of two are convenient and space is cheap. Furthermore, usually a salt of the block size of the hash you're using is usually best, because salting at all will almost always involve an extra block, so why not fill it up given that there will be no performance impact?

But once again, yes, you're correct in your analysis of the Birthday Problem.


Is this a good way extracting randomness from some physical process?

If hash collisions of f don't exist then information is neither created nor destroyed by f and $f(Q_{n-1}\oplus p_n)$ has as much entropy as $Q_{n-1}\oplus p_n$ which has as much entropy as $p_n$. If (for example) $p_n$ only introduced one bit of entropy then someone with $Q_{n-1}$ and access to the same randomness source can deduce the only two possible values for the next hash.

By "extract randomness" I think what you mean is that all blocks of P should have as much entropy as there are bits in P? A good hardware random number generator should already do that. If it doesn't then bits must be destroyed to turn them into entropy. Either $P_n$ gets mapped onto a space of fewer bits or you take multiple instances of $P_n$ and compress them into one. For example you could use the central limit theorem to take several samples from your unknown distribution and generate a normal distribution. Then you can turn the normal distribution into a uniform one.


Setting protocol parameters to achieve concrete security

Concrete units.
Nothing can be said in general until you replace $\Theta(|n|^2)$ by a concrete estimate for the actual computational costs, by filling in the constant factors with units like seconds, bits, and joules.  Obviously you should be a little conservative in cost estimates, although if there are multiple different attacks with different costs—e.g., for discrete logs, NFS cost scales with size of modulus while Pollard's $\rho$ cost scales with size of group order—you should try not to be too conservative with any one of them in order to avoid unbalanced costs to defend against unreasonably pessimistic models of attacks that cause you to make foolish compromises.

Cost metric.
You should take care of the actual cost model.  Time is not the only cost, and many attacks are parallelizable.  For example, although a sequential machine might take an expected $2^{n/2}$ operations to find a collision in an $n$-bit hash function using a gigantic table, it also costs $2^{n/2}$ space to store the table—but you can do better with with a $\rho$-type collision search in constant space, and with van Oorschot and Wiener's parallel collision search machine you can use a machine of size $2^{n/4}$ to get an answer in the time for $2^{n/4}$ sequential evaluations of the hash.

Largely the best metric seems to be the area*time cost: the two-dimensional size of the machine multiplied by the amount of time you have to run it, which is usually a good proxy for the cost in rials or joules.  In this metric, the van Oorschot–Wiener collision search still costs $2^{n/2}$.  Other metrics include RAM metric and NAND metric.  One often-ignored part of the cost is communication between large memories and the parallel computational machines.

Precomputation?
There is a foundational issue about quantifying human ignorance in the concrete, nonuniform setting.

We don't know messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$, but we know such a message pair exists.  So there obviously exists a random algorithm $A()$ that finds SHA-256 collisions very efficiently—specifically, the trivial algorithm that returns $(m, m')$.  We just haven't found that algorithm yet.
Similarly, there almost certainly exists a string $s$ such that the first bit of $\operatorname{MD5}(s \mathbin\| F(0))$ is zero significantly more often when $F = \operatorname{AES}_k$ for a uniform random key $k$ than when $F$ is a uniform random function, which means there exists a high-advantage, low-cost distinguisher for AES—we just don't know what $s$ is, nor do we have any idea how to find it at reasonable cost.

These foundational issues are discussed by Bernstein and Lange in their nonuniform cracks in the concrete paper, which is worth reading if you're interested in the theory—there are more issues, and potential remedies, and compounded issues introduced by the remedies, than I can hope to address in a single crypto.se answer.

So, how do you decide what parameters to use?  It's easy as 1-2-3!

Solve a gigantic open problem in the foundations of cryptology of quantifying human ignorance and precomputation in the concrete nonuniform setting and rewrite the entire literature to address your solution.
Write down a concrete formula giving a cost estimate for the best attack on the system, based on attack costs on primitives and derived attack costs of reductions.
Choose the parameters optimizing your concrete costs, subject to a lower bound on the budget needed to break the parameters above what you assume the adversary has.

That is to say, find the best parameters for your budget that are beyond the reach of your adversary given an assumption about their budget.

Let's ignore space costs and communication costs and constant factors for the moment, and pretend the precomputation issue didn't exist.  If the adversary can break your protocol in time $T = 30\,\text{sec}$ with probability $\epsilon$, then they can factor $n$ in expected time $\frac{T L m}{\epsilon} + \tau |n|^2$, where $\tau$ is the constant to make the units work out.  What choices of $|n|$ (and $|p|$ and $|q|$) and $L$ optimize your costs, subject to the constraint that $|n|$ be out of reach for the NFS (or ECM, or Pollard's $\rho$, or whatever gives the best concrete factoring costs for $|n|$) to factor with a budget of $\frac{T L m}{\epsilon} + \tau |n|^2$?

For this to work, you need to be armed with:

an estimate of your costs, e.g. from https://bench.cr.yp.to or from your own measurements or from your own analysis
an estimate of NFS and ECM costs per key, which can be complicated

Of course, if you're not generating a fresh $n$ in each instance of the protocol, you also need to constrain the optimization so that $|n|$ is out of reach of the NFS/ECM with a budget of $2^{80}$ operations offline as you posited.

I'd give a concrete example but I'm too dizzy from reading about NFS costs and I need to sit still for a while.

Some caveats to beware of:

One type of attack cost is number of queries to an oracle.  This represents your application's maximum bandwidth; you might hazard a guess about limits on bandwidth of normal usage, but an adversary will saturate all remaining possible bandwidth to maximize the efficacy of an attack.
While you often care about the latency of a single operation, the adversary often cares instead about the bandwidth of many simultaneous attacks.
There are often batch advantages to attacks and opportunities for parallelism; brute force does not just mean trying every key sequentially.
Reduction theorems sometimes give wildly unreasonable bounds.  If there's a concrete attack actually attaining the bound, then this should worry you; if not, you are stuck in a limbo of wondering whether you really need a 100000-bit RSA modulus or you just didn't work hard enough to prove a better bound.


Discrete Logarithm (512 bits numbers) - Find exponent parameter


As it turns out, this is just a beginner question and I think I managed to figure it out. Since $E(m,r) = g^mh^r \pmod n$, I can just split it in two: $E(m,r) = (g^m \pmod n) (h^r\pmod n)$ and then apply the CRT trick on both sides, after which I can multiply the results together to get back the original:

$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$R_{h}(r) = (h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$E(m,r) = E_{nonrand}(m,r)R_{h}(r) \pmod n$

Can anyone think of any reasons why I should not skip the (mod n) reductions for $E_{nonrand}(m,r)$ and $R_{h}(r)$? It looks to me like they are redundant...


In the NIST Special Publication 800-38D page #8 the maximum inputs lengths are defined in the standards as;

  The bit lengths of the input strings to the authenticated encryption function shall meet the
  following requirements:

$len(P) \leq 2^{39}-256$

and in section 8.3 the number of invocations requirements for all implementations:

  The total number of invocations of the authenticated encryption function shall not exceed
  $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with
  the given key.

As a result, the recommendation doesn't advice the overflow of the counter.

We can find the maximum as:

$2^{32}$ invocation, per invocation you can encrypt 128-bit ($2^7$-bit) with AES, thus

$2^{32} \cdot 2^{7} = 2^{39}\text{-bit} \approx 68.7\text{GB}$ is the maximum data that one can encrypt with AES-GCM under the NIST recomendation.


What is the non-programmable random oracle model?

The main difference (from a cryptographic point of view) is whether the simulator is capable of choosing the answers to the oracle queries or not. In more detail, to prove the simulation-based security of a cryptographic construction in the random oracle model, the simulator is assumed to be able to choose answers for the queries that parties make to the random oracle. This property is referred to as programmability of the random oracle. In the context of non-interactive zero-knowledge (NIZK) proofs, for example, this makes the simulator able to create a convincing but fake proof. On the other hand, the non-programmable random oracle (NPRO) model restricts the simulator such that it can no longer choose the answers for the queries. Instead, the simulator is empowered by seeing all the query/answer pairs, made by the parties during the protocol. This restriction on the simulator (or more generally, the security reduction) makes the underlying proofs preferable, as they rely on fewer properties of the random oracle and so can be considered as a step toward getting rid of it.


How to calculate Public Key exponent if I have p, q, Dp, Dq, QInv?

Your public key contains two numbers. First it is a number n, which is called the Modulus and are computed through $p \cdot q = n$.
The second number is e, which is the public exponent and are used to encrypt your message m. The number e is choosen that it have the following properties:

\begin{equation}
1 < e < \phi(n) = (p-1)(q-1)
\end{equation}
\begin{equation}
gcd(e, (p-1)(q-1)) = 1
\end{equation}

$\phi$ is the euler's totient function.

The private key contains the numbers p,q and d. The number d is your private exponent and p,q are your prime numbers, which helps you do calculate n and the private and public exponent.

The private exponent have the following properties:

\begin{equation}
1 < d < (p-1)(q-1)
\end{equation}
\begin{equation}
d = e^{-1} mod~(p-1)(q-1)
\end{equation}

I am not sure, what are Dp, Dq and QInv in your configuration is, but if you have d you are able to compute e with:

\begin{equation}
e = d^{-1} mod~(p-1)(q-1)
\end{equation}

I hope it will help you. If that doesn't help may specifiy what are Dp, Dq and QInv are.

EDIT:
I think you are using the PKCS#1, which are mentioned in the comments below of this answer.

In the PKCS#1 you are also able to have a quintuple as a private key, which are p, q, Dp, Dq and QInv.

Dp and Dq satisfy the following equations:

\begin{equation}
e \cdot Dp \equiv 1~mod~(p-1) \Leftrightarrow e = Dp^{-1} ~mod ~(p-1) \\
e \cdot Dq \equiv 1~mod~(q-1) \Leftrightarrow e = Dq^{-1} ~mod ~(q-1)
\end{equation}

and the number e have a little bit different property.
The property of e is:

\begin{equation}
gcd(e, \lambda(n)) = 1~and~\lambda(n) = LCM(p,q)
\end{equation}

Additionally your d is satisfying this equation instead of that from above:

\begin{equation}
ed \equiv 1 ~mod ~\lambda(n) \Leftrightarrow e = d^{-1} ~mod ~\lambda(n)
\end{equation}

This equation should give you the right e from your giving d and $e = d^{-1}~mod~\lambda(n)$ means compute the modular inverse from d with the modulus $LCM(p,q)$.

I hope this will help you.


Breaking hashless variant of the Rabin Signature system with chosen message attack

Here's how the attack works:

Select a random value $y$
Compute $a = y^2 \bmod n$
Ask for the signature of $a$, that is $x$ with $x^2 = a$
If $x \ne y$ and $x + y \ne n$, then $\gcd(n, x+y)$ is a proper factor of $n$

The last step will succeed with probability $\approx 0.5$.  You can make it probability 1 if you select a $y$ with Jacobi symbol -1.


Is there a practical upper limit for password rehashing?

When using PBKDF2, is there a practical upper limit to the iteration count above which we lose security?

No.

There is a limit above which you gain no security, but it isn't practical. It's on the order of $2^{128}$ iterations for PBKDF2-HMAC-SHA-2, or $2^{80}$ if you use SHA-1 as the HMAC hash. For an explanation, see the questions mikeazo linked in the comments.

However, due to the structure of PBKDF2 those collisions in the iterated hash likely don't undo the previous iterations, they only add to them (XOR). So the fact that you get collisions in the iterated function does put a limit on how much security you can gain from a high iteration count, since an attacker could stop iterating if they notice a collision. Nevertheless, they need to get that far and the ultimate hash is probably still different from all the other passwords, so that doesn't mean those extra iterations make it weaker.

Cycles, which you would notice about the same time, can technically "undo" previous iterations, but the unique iterations before the cycle begins are still strong, and the expected number of those is also close to $2^{128}$ for a 256-bit hash.


Moni Noar One Way Function: What does input is partioned mean?

I am having trouble understanding what "$m$ is partioned into a sequence $\langle m_1, ..., m_k\rangle$ of elements in $\textbf{Z}_R$ means.

This is essentially what you said. Consider $n$ such that $\{0,1\}^n$, seen as integers, is a subset of $\textbf{Z}_R$ (e.g. $n = \lfloor\log_2R\rfloor$). Then regard $m$ as a long string $m = m_1\|\cdots\|m_N$ where each $m_i$ is in $\{0,1\}^n$ (if $n$ does not divide the bit-length of $m$ then apply a "good" padding to $m$, i.e. one that is prefix-free).

Just take into account that, as noticed by @poncho in the comments, this is not a PRF. This is a 2-universal hash function, and as shown in the post you cite, it is an ingredient for the construction of an actual PRF.


Expanding truly random key into printable password for successive hashing

Q1.
 Each printable ASCII character gives you $\log_2 M$ bits of security where $M$ is the number of printable characters, assuming uniformity and independence between the characters [the second assumption does not hold in natural language].

For ASCII $M=106,$ which gives approximately $6.74$ bits/character, but this is likely to be a massive overestimate of security unless a good randomness source is used to
generate the passwords.

Q2. If you want to use limited entropy to generate astronger password you should consider generating a key using a KDF (Key Derivation Function). Have a look at this question and other linked questions from there. Some such schemes are used to derive different passwords/keys for different sites, where the sitename seems to correspond to the message in your case [i.e., it is variable].


Can I securely refill a one time pad over the same connection?

No, using a one-time-pad to encrypt another key stream is futile, as the original key stream must be at least the same size as the message you're trying to encrypt. So the amount of bits used from the current key stream will at least equal the amount of bits transmitted. For a one-time-pad the key stream must be at least the same size as the plaintext message to achieve information theoretical security. XOR is not the only operation that encrypts the message using the key stream, but no other operation will allow a key stream smaller than the message by definition.

The more clever way is to use a stream cipher. A stream cipher generates the key stream from a statically sized key. This key can be any size, but sizes of 128 bits to 256 bits give the required key strength against brute force attacks. A stream cipher doesn't provide perfect security but it does give you practical security - even against quantum computing based analysis, given a large enough key size.

For transport security you also want to protect against leaking information by message size, plaintext oracles and side channel attacks - particularly time based side channels (presuming that the processor itself is in a secure location).

Furthermore you probably want to protect your message integrity and authenticity by using an authentication tag (using a MAC or AEAD scheme). A one-time-pad - by itself - does not provide integrity or message authentication.


How to prove identity without revealing identity

She can generate a key-pair and include the public key in the book. Having the private counterpart she can at any time proove that she wrote the book by signing an arbitrary statament.


When using a salted, key-stretching KDF, like PBKDF2 or scrypt, you are in effect stretching both the salt and the password.  That is to say, what you're calculating is

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

where changing either of $\rm password$ or $\rm salt$ requires the slow $\rm KDF$ function to be entirely recomputed.

In fact, if changing the salt did not require repeating the entire key derivation process, this would significantly reduce the effectiveness of the salt: instead of requiring $t \times n \times m \times k$ time to test $n$ passwords against $m$ hashes with a KDF iteration count of $k$ (with one iteration taking about $t$ time), the ability to easily change the salt would allow an attacker to carry the same attack out using only about $t \times n \times (m + k)$ time.

In particular, contrast this with extract-then-expand style KDFs like HKDF, used for deriving multiple keys from a single original key or password, which have the general form:

$$\begin{aligned}
\rm PRK &= \rm KDF_{extract}(password, salt) \\
\rm key_{\it i} &= \rm KDF_{expand}(PRK, info_{\it i}) \\
\end{aligned}$$

where ${\rm info}_i$ is a unique string identifying the purpose for which ${\rm key}_i$ is being derived.
One of the advantages of this kind of KDF is that, whereas $\rm KDF_{extract}$ needs to be slow if used with password inputs*, the $\rm KDF_{expand}$ function can be fast, allowing many keys to be efficiently derived from one password.

The important thing to note here is that, as a consequence, the salt and info strings play very different roles: the salt can and should be varied to reduce the effectiveness of parallel brute force attacks on multiple passwords, whereas varying the info strings offers no such protection, since changing the info string does not require recomputation of the slow extract phase.

(*: Note that the extract function defined in the HKDF standard is not slow, and should not be used for password-based key derivation.  However, the standard does include a provision for effectively replacing the extract function with any other source of uniformly distributed pseudorandom keys, such as PBKDF2.)


Crypto lib that use files instead of passphrase

Note: I won't recommend a specific library for these, because this would be off-topic and the risk would be there that this gets outdated sooner than later (especially as soon as CAESAR finishes).

This is a very standard solution to the authentication problem although usually one does do both (e.g. passphrase and keyfile).

On the conceptual level any library exposing some sort of KBKDF or PBKDF and a decent encryption mechanism is sufficient.

What you do is simple and clear: You look at your chunk of data and extract derivation paramters from it (they are associated data), then you ask the user for the file name and completely parse it into your PBKDF / KBKDF of choice. From this you derive an encryption key and a nonce / IV and you're good to go to apply authenticated encryption on your data

You should use a password based key derivation function (PBKDF such as Argon2, scrypt or bcrypt) if you suspect the file to be low entropy (less than $2^{128}$ plausible possibilities) and use a key based key derivation function (KBKDF such as HKDF or KDF2) in all the other cases. For the actual encryption AES-EAX is your mode of choice for files that get larger than 60GB and AES-GCM for anything smaller.


How exactly works the quantum communication done by China?

I watched the video with the sound off, but the giveaway are the lasers. It's simply(!) the extension of quantum bit transmission to orbiting satellites, rather than via fibre optics.  All the same principles apply, although it's hard to keep a physical lock on the satellite.  Clearly this becomes impossible when the satellite disappears beneath the horizon.

There is a rule of thumb that says general media + tech = 0.  The general press are hopeless in trying to convey a technological story.  What the Chinese will have done is to transmit entangled photons to the satellite.  They may have then send another set of entangled photons back to the earth station.  This allows transmission of data via statistic analysis, and the BB84 protocol is a common technique for this. The Chinese may not have got as far as this protocol.  It would be sufficient to prove entanglement between the earth station and the satellite. This would be the real advancement in this item.

This answer details how a quantum network works.  In summary, keys are generated via quantum RNGs and transmitted via photons.  Transmission is akin to a one time pad (OTP), but a bit cleverer as there is a great deal of noise within the transmission.  That's why the key exchange is unbreakable.  Those keys are then used for conventional encryption over conventional wiring.  With a  satellite, that conventional encrypted transmission could be achieved via lasers, just minus the glass fibrery bit.

  If not smaller what's the point of using the quantum channel and not just sending all the message in the conventional channel?

That's a good question.  Currently the key exchange is done via OTPs.  It's low baud, so a conventional channel is used in an office setting for the Gigabit throughput.  ID Quantique only manage about 10 KBits /s currently.  It is conceivable that when this technology is miniaturised to portable size, military battlefield communication could all be performed via pure BB84, without bothering with the conventional encryption. And it would all be unbreakable, whilst currently the conventional encryption might be broken one day.

But it might be jamable and susceptible to MITM attacks.  Another almost coincident laser directed at the satellite receiver could swamp it.  This is speculation at this stage, but someone's working on it, I'm sure.


Is a random string good for an AES-256 instance

The Following Code Is Now Using The Password Derive Bytes Function, All Values Will Be Changed Accordingly
    string Password = "Example";
    byte[] IV = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    byte[] Salt = Encoding.ASCII.getBytes("Salt Example");
    PasswordDeriveBytes pdb = new PasswordDerivedBytes(Password,Salt);
    Aes Alg = Aes.Create();
    Alg.Key = pdb.CryptDeriveKey("Aes","SHA256",256,IV);
    Alg.IV = IV;

The Code Above Is C#


Do any stream ciphers with aperiodic keystreams exist?

Well, it's easy to show that any generated with a bound on the amount of internal state must eventually become periodic.  It's also easy, once we allow a generator whose internal state grows arbitrary large over time, to design a generator that never repeats (and the state growth required is actually quite reasonable).

That said, I don't know of any proposed stream ciphers that attempts to be completely aperiodic.  I suspect that it's mostly because aperiodicity is not a realistic requirement (as opposed to the nicety of being implementable within a bounded memory space).  After all, it is easy to have, even with a bounded state generator, such a large period (e.g. a period of $>10^{100}$) that we never have to worry about it.  After all, if we never generate that much output, does it really matter if it would repeat if we did?


Why does NaCl's crypto_auth have twice the security level of crypto_onetimeauth?

There are two things to consider.

First is that the security models differ: crypto_onetimeauth only has to be secure for one message, while crypto_auth needs to be secure for any (practical) number of messages. The reason crypto_secretbox gets away with using the Poly1305 authenticator internally is that it generates message-specific authentication keys based on the nonce.

Second is the size of the authenticator. There is no very secure 128-bit hash function – using MD5 would be iffy even if it is not known to be broken in HMAC. You could still truncate HMAC-SHA256 and get a 128-bit authentication tag, but that would require assuming more than just the security of SHA-256.


Alternative block cipher design paradigms to SP-networks and Feistel-like ones?

Are ARX block ciphers considered there own class of block cipher separate from SPNs and Feistel-like ones?

Generally speaking, yes. ARX ciphers typically only use simple CPU instructions (Addition, Rotation, and Xor) and are typically designed to ensure constant time execution as well as to facilitate efficient SIMD implementations.

The s-boxes and split state that are so prevalent among SPN and Feistel Networks generally aren't present in ARX designs. I'm sure if you wanted you could come up with/find an example of an ARX Feistel network or build an SP network from ARX instructions, but I'm not sure what advantages it would offer.

Are there other schemes out there besides Feistel-like designs, SPNs, and ARX? Or is there really nothing new under the sun?

Typically, the ARX/SPN/Feistel part of the algorithm is used to create a "pseudorandom permutation", and the pseudorandom permutation is then used as part of a cipher construction to provide encryption.

The basic cipher construction is the iterated key or Even-Mansour construction. AES can be modeled like this, as an interleaved application of a key addition layer with the pseudorandom permutation.

A more recent cipher construction that can be built from an arbitrary pseudorandom permutation is the sponge construction. Technically the duplex
construction is a stream cipher, rather then a block cipher. I think that this is actually a key point: The presumption that a block cipher is the best way to encrypt is not necessarily true.

Permutation based

Permutation based constructions are usually more versatile, and often times offer an all-in-one solution (authenticated encryption, hashing, MACs); While you could construct all of the above via a block cipher, it is much more straightforward from an implementation perspective to use a permutation based construction like the sponge construction.

Homomorphic Ciphers

There exist "linear" secret key ciphers, like this one from Fully Homomorphic Encryption Over The Integers. Typically these sorts of ciphers are designed to facilitate homomorphic encryption and/or to instantiate public key cryptosystems. They are often times built from number-theoretic perspectives, and clearly do not resemble any of the other cipher categories (and you would not use them for the same reasons).


Cryptocurrency for quantum computers that is physically impossible to double-spend?

I'm not sure how developed the idea is, but it sounds like you are describing the idea of quantum money.

Also, as it would be a new cryptocurrency, it would not be Bitcoin; Bitcoin is a particular cryptocurrency, and not all cryptocurrencies are Bitcoin in the same way that not all normal currency is US dollars.


Padding on RSA signature and RSA encryption

TL;DR: The security definitions ask for different properties.

The usual security definition for public key encryption, asks you, the attacker, to distinguish which message (out of two) was encrypted and you're seeing the ciphertext of. Obviously you can't succeed at defending in this if you don't randomize, because otherwise an attacker could just encrypt the messages himself and compare the results. Also see our canonical answer for the details.

For signature schemes on the other hand, the usual security definition asks you (the attacker) to find a $(m,s)$-pair (where $m$ is a message and $s$ is its corresponding signature) that you haven't seen before or that you haven't received from the oracle (ie any ressources you're allowed to use). As you can see, there's nothing that would require for randomness in this definition and as such there are fully deterministic schemes with "provable" security, such as RSA-FDH.


Encryption algorithms larger than 256 Bit for “big data” encryption?

There is no need to go beyond 256 bits if the cypher is strong (can only be attacked by brute force).

This is because there are fundamental physical limits on the energy required to perform a computation. The Landauer limit is one: to switch one bit takes $kT\ln2$, where $k$ is the Boltzmann constant ($1.68\times10^{-23}$), $T$ is the temperature in Kelvin, and $ln2$ is the natural log of 2. On average brute forcing a 256-bit key will take $2^{255}$ operations (half of $2^{KeyLength}$).

Assume a computer exists which operates at this limit, is at the temperature of the cosmic microwave background (about 3K), and only needs to do one operation to test a key. It will then take $2^{255}\times 1.68\times 10^{-23}\times 3 \times \ln 2$ Joules, which comes out to about $2.02\times 10^{54}J$.

For comparison, the if the entire mass of the Earth were converted to energy it would only release $5.4\times 10^{41}J$. So you'd be annihilating 10,000,000,000,000 earth-sized planets just to brute force one key. Or building a Dyson sphere and capturing the total energy output of the Sun for 10,000,000,000,000,000,000 years.

In short, there are so many possibilities that the key length is sufficient, presuming you want your secrets to outlive the Sun.


How to verify the integrity of RSA encrypted messages?

With pure asymmetric encryption there is no way to ensure integrity and authenticity, since anyone who knows your public key can encrypt any message for you. For that you would need either a symmetric key to use for a MAC (in which case you could use it/derivatives for symmetric encryption too) or a signature from the sender. And in the latter case the advice is to sign-then-encrypt, which doesn't help with any padding concerns.

There's no simple way to avoid leaking information through a padding attack, like with encrypt-then-MAC for symmetric encryption, if the padding algorithm is vulnerable to one. Instead, your implementation should not leak information about whether the padding is correct. OAEP is more resistant than older padding algorithms, but even it must be correctly implemented.

However, since you are using a high level cryptographic library, the low level details are not something you should have to worry about. The writers of that library should have taken care of those. Just choose the correct algorithm, i.e. OAEP. (I don't know details about any Java libraries' security record, though.)


Guidelines for cryptographic key generation

As for the randomness it is simply sufficient to have a cryptographically secure PRNG to generate the HMAC key and RSA key pair. You should make sure that the PRNG is a well known algorithm and well seeded, and you should perform self tests during startup. Having a malfunctioning or incorrectly seeded PRNG is one of the most common reason for vulnerable keys.

The HMAC key simply consists of random bits. You can directly use the output of your random number generator.
The RSA key pair generator requires a random input to find the random primes of half the key size. This generator will likely use a high number of random bits.

With regards to key lengths take a look at keylength.com.

Make sure your hash algorithm used within the HMAC construction is of the same size as the key size.
It is strongly recommended to only choose 8-bit multiples for the RSA key size in order to reduce compatibility issues.

RSA-specific notes:

It is best to choose a public exponent in advance, 0x010001 (65537), the fourth prime of Fermat is a popular - and often the default - choice.
Key sizes of the form $2^x$ or possibly $2^x + 2^{x-1}$ are highly recommended (e.g. 2.048, 3.072, 4.096, 8.192, 16.384 bit keys).
There is technically no need to go for ANSI X9.31 key generation (now practically replaced by FIPS 186-4 with appendix B.3); however, if a private key must run on yet unspecified hardware (as long-term root keys should), it is prudent to use primes with $2^{(n-1)/2}<p<2^{n/2}$ where $n$ is the public modulus size (one of the requirements of these standards).
RSA private keys should contain CRT parameters so as to make it straightforward to speed up RSA private key operations.
Beware that an RSA private exponent may be smaller in size - even in bytes - compared to the modulus, this is no reason to worry (unless it is much smaller).
Beware that RSA key generation can take a long time compared to other cryptosystems, including asymmetric; and this time varies widely and without firm upper bound from one key to another. This is a classic issue for mass production of devices with internal key generation, or when defining a maximum delay for supervising software.

For optimum assurance you should use a FIPS or Common Criteria validated software and hardware component (HSM, smart card) for key generation, key storage and key usage. Beware that computer memory may not always be secure. Key generation is the easy part, correct key management is much harder.


So my question is that if an attacker has gained access to this secret, would he not be able to generate the OTP just as easily as the client software on my system because HOTP(key,counter) will remain the same for all?

Yes, if an attacker learns your shared secret, he can calculate OTPs whenever she wants. But this is very unlikely, since every secret is unique (no reuse, like with a password) and never transmitted (apart from the initial agreement) a direct hack of the server or the client's token is the only possibility of obtaining it.

  So to ensure TOTP is helpful, I have to make sure that the secret key with the client is safe?

Correct.

  Let's say I'm making a software that is to be used by the public which
  uses TOTP based authentication. So will I be attaching a different
  secret to each of the clients and maintaining a database on the server
  end to match the secret server side?

Yes. Every user has a different key on your service. If you store it in a database or obtain via some deterministic calculation from a master secret is up to your implementation.


Is RSA encryption without padding secure with NIST Key Establishment schemes?

Yes, RSA encryption without padding as used by RSASVE in NIST SP800-56B is secure.

The RSASVE Generate Operation in NIST SP800-56B §7.2.1.2

is given on input an RSA public key $(n,e)$;
generates a random secret bitstring $Z$ uniformly distributed on range $[2,n-2]$;
computes $C=Z^e\bmod n$ (as in textbook RSA encryption);
outputs the secret $Z$ and the public $C$ (as bitstrings).

and the RSASVE Recovery Operation

is given as input $C$ and the private key $(n,d)$ (or some equivalent);
computes $Z=C^d\bmod n$  (as in textbook RSA decryption);
outputs the secret $Z$.

It is used to generate a secret bitstring $Z$, then share it with the legitimate holder of the private key $(n,d)$.

This is safe (in the sense that an adversary intercepting $C$ gains no knowledge about $Z$ chosen in RSASVE Generate), despite the lack of padding, because what's passed to textbook RSA is random. Breaking RSASVE is, quite precisely, the RSA problem, defined as gaining information about random plaintext randomly chosen on $[2,n-2]$ (give or take $0$, $1$, $n-1$) and encrypted using textbook RSA encryption. Padding is unnecessary here. One way to see that is that the aim of RSA padding is to transform plaintext (or message to sign) into something close enough to random that the RSA problem is safe, and here we have something assumed random in the first place.

Update: as rightly pointed by SEJPM in comments, the above is not enough to show that the uses of RSASVE in NIST SP800-56B are safe. According to a cursory review, that's indeed the case, for I only see that $Z$ is

optionally, first concatenated with another similarly shared secret, to form a wider one;
used as the input of some KDF, where it is subject to $H(\text{counter}\|Z\|\text{OtherInfo})$

and this prevents any exploitation of the homomorphic property of RSA.

We can safely use RSA encryption without padding when

The plaintext enciphered is guaranteed to be about uniformly random (from the adversary's standpoint) over $[0,n-1]$ (or a large-enough subset of that, say with more than $n^{2/3}$ elements); this is enough to insure that the adversary can not gain knowledge of what's enciphered.
And it does not matter that the alleged plaintext obtained by deciphering unauthenticated ciphertext can have special relations to some true plaintext.

Two common applications of that are

Encryption of a freshly generated secret, for secret sharing, when that secret is then hashed (as in NIST SP800-56B) or otherwise used in a manner matching 2.
Encryption of a freshly generated RSA signature, when the modulus used for encryption is different form the one used for signature (and not with much more bits); in this application, deciphered plaintext is then naturally submitted to signature verification using a different modulus than in encryption, which insures 2 is met. In the common case of moduli of the same bit size, there is a standard trick to shorten the signature by one bit so that it is always less than the encryption modulus: replacing signature $S$ by $\min(S,n_s-S)$ where $n_s$ is the signature modulus. Enciphering a signature is useful to insure confidentiality of some of what's signed.

Note: I have silently assimilated bitstrings to integers using big-endian convention.


Understanding definition of secure pseudo random number generator

You'd do well to review your readings to see if they stipulate somewhere earlier that when they say "random" they mean uniform random (equiprobable).
But even without such a stipulation that I'd say the definition as you've loosely formulated it and are interpreting it seems to imply equiprobability.  If we follow your logic strictly, then we have to conclude that your proposed attack on the normally-distributed output of $G$ would imply that $G$ is not in fact a secure PRNG by your definition and application thereof.  And in fact you should be able to conclude that your definition and interpretation implies that the output of a secure PRNG must be uniform.
But the definitions used in theoretical cryptography are much more precise than this.  For example in Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where thre first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

I'll repeat this bit that I boldfaced at the end:

the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$

If your reading materials are leaving you with questions like these, maybe have a look at something more rigorous.


In real word RSA modules are so large that probability for finding $c_1$ which is not coprime with $n$ is approximately zero.

  Also if you founded such number then $p=gcd(c_1,n)\neq1$ so $p$ is a factor of $n$ and in this case attack is not necessary because $n$ is factored.

$gcd(296,1073)=37\neq 1$ so $p=37,q=\frac{1073}{37}=29$ and $\phi(n)=1008$

Now you can easily compute private key $d_2$:

$e_2\cdot d_2=1 \pmod{ \phi(n)}$ so $d_2=275$.

  $$m={c_2}^{d2}\pmod n={555}^{275}\pmod{1073}=999$$


The reason we, at the end of the compression function, add the input to the compression function, well, that's because otherwise the compression function would be invertible, and that would be bad.

Without that final step, the compression function would be invertible in this sense: given a desired compression function output and a message block, we would be able to find the compression function input.  We would be able to do this because the MD5 compression function is made of 64 steps, and each step is itself easily invertible.  Adding in the compression input at the very end breaks up this invertibility, because the analyst is unable to invert that final step (because he doesn't know the compression function input yet).  He could guess the input at that stage, and then run the rest of the compression function backwards; this turns out to be no more efficient that just guessing the compression function input, and running it forwards.

This invertibility would be bad, because it allows an attacker to do tricks we'd prefer him not to.  For example, we'd want a preimage attack (that is, given a hash value, give me a message that hashes to that) to take (with a 128 bit hash like MD5) roughly $2^{128}$ steps; that is, there is no method that is drastically more efficient that trying random messages and hashing them until you stumble across one with the correct hash.  However, if the compression function is invertible, here is what that attacker can do, given a $Target$ hash value:

Generate $2^{64}$ message prefixes, and generate the partial hashes to that point
Generate $2^{64}$ message suffixes.  When these, he would start with the $Target$ hash value, and compute the hash backwards until he gets the inverse partial hash (having first applied the MD5 final padding).
Given those two lists of 128 bit items, he then looks for a match (and, by the birthday paradox, there's a good chance of being one.

And, if the partial hash of $P_i$ is the same as the inverse partial hash of $S_j$, then he knows that $Hash( P_i || S_j ) = Target$.  This is because, when we evaluate the hash, we first run the compression function on the blocks from $P_i$; at the end of this evaluation, he would come up with the common partial hash value.  Then, he would run the compression function on the blocks from $S_j$ after padding; he knows that, starting at this common value, that results in $Target$.

So, because of this, an attack we had hoped would take $2^{128}$ steps could be done with roughly $2^{64}$ steps.  Making the compression function noninvertible (which the real MD5 does) prevents this line of attack.


FHE over the Integers - reduction to approximate gcd problem

Before my answer, I would like to review the original binary GCD algorithm @wikipedia. Roughly speaking, this algorithm replaces division with binary shifts and subtraction.

For two positive integers $u$ and $v$, the following identities hold:

$\gcd(0,v) = v$ and $\gcd(u,0) = u$.
$\gcd(u,v) = \gcd(v,u)$.
If $u,v \in 2\mathbb{Z}+1$ and $u \geq v$, then $\gcd(u,v) = \gcd((u-v)/2,v)$.
If $u,v \in 2\mathbb{Z}$, then $\gcd(u,v) = 2 \cdot \gcd(u/2,v/2)$.
If $u \in 2\mathbb{Z}$ and $v \in 2\mathbb{Z}+1$, then $\gcd(u, v) = \gcd(a/2,b)$.

By using those identities, the binary GCD algorithm $\mathsf{BGCD}(u,v)$ is defined as follows:

If $v > u$, then swap them.

If $v=0$, then output $u$.

Let $b_1$ be the parity bit of $u$ and let $b_2$ be the parity bit of $v$.
If both $u$ and $v$ are odd, then $u \gets u-v$ and $b_1 \gets 0$.
If $b_1=0$, then $u \gets u/2$. If $b_2=0$, then $v \gets v/2$.
(Recursion) If $b_1=0$ and $b_2=0$, then output $2 \cdot \mathsf{BGCD}(u,v)$. Otherwise, output $\mathsf{BGCD}(u,v)$.

Answer 1

  What exactly do the authors mean by $q_p(z_1')$ being the odd part of the gcd? (last line of step 3)

Let us consider two positive integers $a$ and $b$, and its GCD.
Then, there is an unique integer $k$ and odd integer $c$ satisfying $\gcd(a,b) = 2^{k} c$.
The authors call this $c$ the odd part of $\gcd(a,b)$.

The reduction algorithm, say $\mathsf{Alg3}(z_1,z_2)$, in Step 3 is defined as follows:

If $z_2 > z_1$, then swap them.

If $z_2 = 0$, then output $z_1$ and $z_2$.

Let $b_i$ be the parity bit of $q_p(z_i)$, that is, $b_i = [q_p(z_i)]_2$.
(Call the LSB oracle implemented by $\mathcal{A}$.)
If both $q_p(z_i)$ are odd, then $z_1 \gets z_1 - z_2$ and $b_1 \gets 0$.
For each $i = 1,2$, if $b_i = 0$, then $z_i \gets (z_i - \mathsf{parity}(z_i))/2$.
(Recursion) Output $\mathsf{Alg3}(z_1,z_2)$.

As the authors wrote, this algorithm (approximately) performs the binary GCD algorithm over quotients on input $q_p(z_1)$ and $q_p(z_2)$.
Since we are interested only in the case $\gcd(q_p(z_1),q_p(z_2)) = 1$,
 the algorithm removes "If" from the step 5 in $\mathsf{BGCD}$.
In addition, the doubling in "If" will introduce another noise.
By this removal, $\mathsf{Alg3}$ (approximately) outputs $z_1'$ whose quotient $q_p(z_1')$ is the odd part of $\gcd(q_p(z_1),q_p(z_2))$, when the current $z_2'$ in Step 1 is $0$.

Answer 2

  In step 4 (recovering p): Where does the $\pi^2/6$ come from? I'm guessing it has something to do with prime distributions, but I couldn't find anything on google. Also, $\pi^2/6 \approx 1.6 $  and not $0.6$, so is the formula wrong?

  Thanks @Thomas, found it on wikipedia: The probability that two random numbers are relatively prime is $1/\zeta(2) = 6/\pi^2 \approx 0.6$, so the paper just has nominator and denominator switched.

As @Thomas wrote, the probability is that two random numbers are relatively prime.
If so, $\gcd(q_p(z_1^*), q_p(z_2^*))$ is $1$ and the odd part of it is also $1$.

Answer 3

  Also in step 4: Am I correct that $\tilde{z} = z_1'$, i.e. the non-zero output of the first round of the binary gcd algorithm?

Yes.


Why does TLS 1.3 support two CCM variants?

The rationale goes this way:

On a "big" system like a PC or a smartphone, ChaCha20+Poly1305 or AES/GCM are very efficient; the latter is fast because the hardware provides dedicated opcodes that implement both AES itself (aesenc, aesenclast on x86 CPU) and the GHASH part of GCM, which is used for the integrity check (pclmulqdq opcode on x86 CPU).
On much smaller systems (embedded microcontrollers), things are not that easy. Pure software implementations of AES/GCM are quite slow; ChaCha20+Poly1305 may fare somewhat better, but not necessarily as fast as can be hoped for. Note that "speed" can mean "maximum bandwidth", but also battery life: when processing small messages, the cost for encrypting can be expressed in terms of a duration during which the CPU must be powered at its high frequency.

On that kind of system, you may have an hardware AES implementation, but usually not a an hardware helper for GHASH (because of size constraints on the CPU die, mostly). Thus, CCM works better than GCM on such microcontrollers. This explains the request for supporting some CCM-based cipher suites.
Constrained systems are usually constrained for everything; computing stuff drains the battery, but so does sending data. Reducing the amount of bytes to send can help, and every byte counts. The normal authentication tag of CCM is 16 bytes. The "CCM_8" cipher suites use tags reduced to 8 bytes, thus saving 8 bytes of overhead, at the expense of a higher probability of forgery.

This is how TLS 1.3 ends up with CCM_8 cipher suites. It's all about performance issues on small embedded systems. Note that MAC can tolerate a relatively high forgery probability because of their "online" nature: when an attacker tries to forge a MAC value, he still have to try it out on an honest receiver for every forgery attempt; if the attacker is talking with small embedded systems, he won't be able to do that many times per second (and each failed attempt implies an error on the receiving system). This contrasts with encryption, where a brute force attack is "offline" (the attacker tries potential decryption keys on his own computers, and can thus do that at a high rate, and quietly).

It is worth pointing out that AES/GCM has a bit of trouble with truncated tags. An authentication tag of $n$ bits cannot have a probability of forgery less than $2^{-n}$, but with GCM, when $n < 128$, it tends to be higher (specifically, successful forgeries leak extra information, making subsequent forgeries easier). As such, tag truncation on GCM is not recommended. CCM, for all its design issues, does not suffer in the same way.


Smallest possible certificate for IoT device

What is the minimum, secure enough, certificate that you can build? How could I generate it using OpenSSL?

Generally you'd need to flatten certificates if you want to go below 256 bytes. X.509 version 3 certificates have a certain overhead due to the ASN.1 tree structure. So those are not as efficient as they could be.
For smart card systems generally so called "card verifiable" certificates are used. CVCertificates are proprietary structures that are generally also specified using ASN.1. However, they try and use a minimum of bytes, generally a SEQUENCE of OCTET STRINGs with possibly a few INTEGER's and OID's thrown into the mix. They would also use flattened public keys and signatures where a minimum of overhead is used.
For instance, if Elliptic Curves are used (ECDSA) there could be a dedicated named curve used, or a single byte indication of the curve used. Then the (compressed) public key would just be a single OCTET STRING containing just X for compressed or X and Y for uncompressed as statically sized unsigned integers. Similarly the signature would not be DER encoded but consist of simply a concatenation of R and S.
Generally you'd avoid RSA. RSA can be used in such a way that part of the signature actually contains the data of the certificate itself. For this "digital signature schemes giving message recovery" are used. These schemes are however rather uncommon. More importantly, a 2048 bit RSA key only allows about 88 bits of security (compared to a AES key, for instance), and already takes 256 bytes for the signature, with the public key taking another 256 bytes for just the modulus. So generally a 64 byte ECC signatures and 33 / 65 byte public keys are preferred (e.g. P-256 or ed25519 offering about 128 bits of security).
OpenSSL command line won't support CVCertificates. Generally CVCertificates are build for a specific purpose. The OpenSSL library can of course be used for both the ASN.1 / DER functionality and the cryptographic functionality. The Java / Bouncy Castle library has some CVCertificate functionality build in that is probably just compatible with the ePassport specifications (where it is used to gain access to the biometrics on the smart card chip - or at least it could be used for that).
Currently EJBCA (an open source Java EE Certifcate Authority) offers CVCertificate support compatible with the ePassport standards. Beware that the software is relatively tricky to use and setup. As it is Open Source you could probably tweak the certificate format for it to meet your needs. But whatever you do, you are entering a rather specialized territory (... welcome!)