Background:

An infinite sequence $c_0,c_1,c_2,\dots$ is generated by a (linear feedback shift register (LFSR) with) polynomial $f(x) = \sum_{i=0}^n f_i x^i$ if for any $j$, $$\sum_{i=0}^n c_{j+i} f_{n-i} = 0 \text.$$

We can consider the sequence as a power series $\sum_{i=0}^{\infty} c_i x^i$. If we multiply this power series with the polynomial $f(x)$, we get
$$f(x) \sum c_i x^i = c_0 f_0 + (c_0 f_1 + c_1 f_0)x + (c_0 f_2 + c_1 f_1 + c_2 f_0)x^2 + \dots $$
We get that the $(j+n)$th coefficient is $\sum_{i=0}^n c_{j+i} f_{n-i}$. Which means that the sequence $c_0,c_1,c_2,\dots$ is generated by $f(x)$ if and only if the product of $\sum c_i x^i$ and $f(x)$ is a polynomial of degree less than $f(x)$.

We denote the set of all sequences generated by $f(x)$ as $\Omega(f(x))$. If we consider $\Omega(f(x))$ as a set of power series, we find that
$$\Omega(f(x)) = \left\{ \sum_{i=0}^{\infty} c_i x^i : \deg\left(f(x) \sum c_i x^i\right) < \deg f(x) \right\} \text.$$

If $f(0) \not= 0$, then $f(x)$ is invertible in the power series ring. This gives us a different characterization of $\Omega(f(x))$:
$$\Omega(f(x)) = \{ f(x)^{-1} r(x) : \deg r(x) < \deg f(x) \}\text.$$
As you observe, it is now easy to prove that if $f(x)$ divides $h(x)$, then $\Omega(f(x)) \subseteq \Omega(h(x))$, since if $h(x) = v(x) f(x)$, then for any $r(x)$ with $\deg r(x) < \deg f(x)$, we have that
$$f(x)^{-1} r(x) = f(x)^{-1} v(x)^{-1} v(x) r(x) = h(x)^{-1} v(x) r(x) \in \Omega(h(x)).$$
The fact that $\Omega(h(x))$ is closed under addition and scalar multiplication then implies that $\Omega(f(x)) + \Omega(g(x)) \subseteq \Omega(\mathrm{lcm}(f(x), g(x)))$.

Direct approach hint:

If you write $f(x)=u(x)w(x)$ and $g(x)=v(x)w(x)$, with $\gcd(u(x),v(x))=1$, then any polynomial $r(x)$ can be written as $s(x)u(x)+t(x)v(x)$ for some $s(x)$,$t(x)$. The trick is to ensure that $s(x)$ and $t(x)$ don't end up with too high degrees, so you can't use the obvious approach.

Indirect approach hint:

You can also consider the dimensions of the (finite!) vector spaces involved, which together with (i) should give you a proof. This approach is probably easier.


What is the prp-advantage of a $2^{80}$-time adversary attacking AES-256?

You misunderstood what Dan Boneh was trying to say. There is no known attack on AES256 that comes even close to this complexity. However, if there was a known attack that came close to this, then it would be very unwise to assume that this is the best attack. When formalizing an assumption, one needs to be conservative relative to what is known. Thus, Dan was giving an example of how one could formulate a conservative assumption about AES, and he was being very conservative (which is a good thing).


If you know the sender's verification key previously: Yes, it does prove the authenticity and integrity of that message. No one else could have created a matching signature - for any message under that public key.

As a side note: hashes of files are in theory a good idea to check that it was not changed. But when you get the hash from the same source as the file itself (e.g. the webserver offering a file for download), then that's utterly worthless. Anyone able to manipulate the file can also just replace the hash (doesn't matter if he has access to the file server or if it's a man-in-the-middle attack).


Preliminary: the present answer assumes an Elliptic Curve group of order $n$ built on a prime field of order $p$, with one of $p$ or $n$ a 160-bit prime of the form in the question (rather $p$, which will give the most computational benefit, and is close to common practice). Choosing "public key $P$ as $p*G$ where $p$ is an Optimal prime" is not proper, and not considered.
Rather yes: ECC cryptography would be dangerously close to being vulnerable to brute force attack.
That's because the order $n$ of the Elliptic Curve group would be at most roughly $2^{160}$ (due to Hasse's bound when the 160-bit prime is $p$), thus vulnerable to a generic Pollard's rho attack with cost about $2^{160/2}=2^{80}$ field operations, e.g. recovering a private key from a public key. Further, that attack is not too difficult to parallelize. That's not entirely out of reach for well funded adversaries.
However, the largest similar attack publicly performed (by Nov. 2020) seems to be against secp112r1, requiring about $2^{56}$ field operations, that is about $2^{25}$ less work than for the above. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, and Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in International Journal of Applied Cryptography, 2012.
Thus for a 160-bit prime, a similar attack would be worth publication in the applied cryptography field. And in the unlikely cases that it it required sizably less than $2^{80}$ field operations, or less than $2^{25}$ more computing power than the secp112r1 attack on any given sufficiently flexible hardware, that would be a major theoretical breakthrough.

Update per comment: I fixed the above to use proper notation for $p$ and $n$. Yes proper ECC on a 160-bit prime field is not publicly broken in practice so far. Yes a 256-bit OPF $p$ would be on par with current practice: common curves such as secp256k1 and Ed25519 use primes of the form $2^{256}-2^{32}-977$ or $2^{255}-19$, which is similar to the question's OPF. Beware however that what matters to security is (half) the number of bits of the highest prime factor of $n$ (that is $n$ if it is prime), which depends on $p$ and other curve parameters. And there are other complex considerations in choosing an ECC curve, that I do not master, see safecurves.


Would the public key of Digital Signature be replaced?

extended and transformed comment into an answer

Digital signatures are not a complete system, they are one mechanism. They assume public keys are known by everyone.

In practice, this is often achieved by some sort of public key infrastructure. In software it's also possible the program has the verification key hard-coded.

  If there is a safe way to send a public key to receiver, why don't just send the message in the same way?

Well, that's pretty much what the chain of certificiates in a PKI do - but the sender might be a different person then.


How long to wait to feed hashing using SHA 256?

You should aggregate bits until you have enough seed bits to start your DRBG using an initial seed. Your seed should contain at least 128 bits of entropy (the amount of uncertainty to an attacker).

Then you could either add the bits as additional seed when you get it or you could first aggregate some entropy. With only an update rate of about 8 bits per second you might as well directly add the entropy to your DRBG.

To create the same pseudorandom bit stream on both sides you should:

make sure you got the same algorithm on both sides;
configure the DRBG identically on both sides;
update your entropy at exactly the same time;
request data from the DRBG using the same methods and parameters.

Note that HKDF is not a pseudo random number generator (PRNG) or deterministic random bit generator (DRBG, same thing). It may be a pseudo random function but that's not the same.

HKDF turns an already secure key into more key material, possibly given additional information. HKDF / HMAC could be used to build a deterministic random bit generator. If you want to do that then you need to create a paper and prove it is correct.

I would recommend having a look at NIST SP 800-90A (revision 1) and pick a DRBG from there.


How does Random Oracle and Standard Model differ?

The random oracle model is a heuristic that assumes the existence of a truly random function to which all parties involved in a protocol, good and bad alike, have access. Since in reality no such function exists, random oracles are instantiated with hash functions and one heuristically assumes that a hash function behaves good enough to be a replacement for random oracles. Random oracles are nice as they allow to prove protocols secure while they are still practically efficient.

Since there are theoretical results showing that there are protocols that are secure in the random oracle model but trivially insecure whenever the random oracle is instantiated with any hash function, standard model constructs, i.e., constructs that do not rely on random oracles, are nicer from a theoretical perspective. Standard model means that the protocols only rely on standard cryptographic assumptions (DDH, CDH...) in their proofs.

No, using hash functions does not mean that you are in the random oracle model - only if you model them as random oracles. If you rely for instance on the collision resistance of a hash function, you can be still in the standard model.


Can I prove my app uses randomness right way?

Nothing you show the user within the app could prove that the numbers were truly generated randomly and that the numbers weren't leaked maliciously or accidentally.

In general, you could make your application (or the module that does the cryptography, assuming it's built into a separate binary like a library or an executable used by the main app) open source and use a reproducible/deterministic build process so that users can compile the source themselves and verify that it matches what they've installed. I'm not sure how feasible or convenient this may be on the iOS ecosystem though. (Users might need a rooted phone to be able to view the app's binary installed from the app store, etc.)


At what stage is DHE and RSA used during the SSL/TLS handshake?

The SSL/TLS handshake consists of a series of messages which do keyexchange and (usually) authentication together. See rfc5246 or its predecessors or Wikipedia for details.
The handshake actually results in one "premaster secret" and one "master secret"
which is then used to derive multiple keys:
an encryption key for each direction (for an algorithm that may be AES or something else), an IV for each direction for suites that need it (which is all CBC suites in protocol versions before TLSv1.1, and some of the AEAD suites in TLSv1.2), and a HMAC key for each direction for suites that need it
(which is everything except the AEAD suites in TLSv1.2).
See How key materials are generated in SSL V3 from master secret
and What is the purpose of four different secrets shared by client and server in SSL/TLS? .

The original, and still a common, keyexchange method is RSA, sometimes emphasized as 'plain' RSA or kRSA. The server sends a certificate containing an RSA (public)key; the client validates
the cert and uses the publickey to RSA encrypt the random premaster secret.
The server proves correct decryption (and is implicitly authenticated) with the Finished message.
The server can optionally request client authentication; if so the client
sends its own cert and uses its matching privatekey to sign a partial transcript, which the server validates and verifies, but this is rarely used. Except possibly the client auth, this is 'pure' RSA.

DHE (DH in ephemeral mode) is used in conjunction with a signing certificate, which can be either RSA or DSA.
The server sends its cert which client validates, and also its DH group and ephemeral publickey signed under its cert; client generates its ephemeral key in the same group
and sends that, plus its cert and signature if client authentication is used.

There is also a method to use DH keyagreement without certificates and authentication, which is in effect ephemeral, but SSL/TLS doesn't call it that, it calls it DH-anon instead. This is usually a bad idea; many people imagine only passive eavesdroppers
and think they only need encryption, but in today's internet active attacks of many kinds are widespread and if you don't use authentication you probably aren't secure.
You could view this as 'pure' DHE even though it isn't called that.

There are elliptic-curve variants ECDHE (ephemeral, RSA or ECDSA signing} and ECDH-anon.
The handshake sequence, and security properties, are the same, only
the actual crypto computations are different. These are technically optional
but in fact nowadays widely implemented and becoming more popular to use.

And there are 'static' methods (DH and ECDH, no E or anon) which use
long-term [EC]DH keys instead of ephemeral ones. This requires certs for
the static keys (and preagreement on the group or curve) which is less
convenient, especially for classic (non-elliptic) DH, although TLSv1.3 is planned to add standardized DH groups that might change this, and these methods don't seem to be used at all on the public net.

Finally, there are some methods that don't use publickeys at all, including
Pre-Shared Key (PSK) and Secure Remote Password (SRP). These basically work only in
a private net (or virtual one) and aren't seen on the public net.

AES or other data cipher like 3DES or RC4 is not used in the handshake.
It is used for data after the handshake.

Contrary to @mirabilos for [EC]DHE methods the ephemeral key material IS
signed under the server cert and the client cert if client auth used.
Not for the -anon methods, which are designed not to authenticate.


Will AES-GCM smaller sized tag (mac) be included in larger sized tag

Yes, that's what the standard mandates.

First we need to note that if you fix a key and an IV, then AES-GCM becomes fully deterministic, that is the same input will yield the same exact output.

Then we look into the standard, NIST SP800-38D (PDF), and look at the way the tag is generated.

$$T=\operatorname{MSB}_t(\operatorname{GCTR}_K(J_0,S))$$

which effectively tells us that the $t$ most significant bits of the tag output (which is the same for both invocations) are to be used for the tag.

Then we look up the semantics of the $\operatorname{MSB}_s(X)$ function which are:

  The bit string consisting of the $s$ left-most bits of the bit string $X$.


What form of ECC can we use to make sure our newly invented ECC based crypto-systems are quantum secure?

Traditional Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe.

However there is a true Post Quantum Key Exchange algorithm which uses the mathematics of elliptic curves and is considered secure by experts who have studied it so far. This key exchange is known as Supersingular isogeny key exchange.


Random Oracle to prove an Authenticated DH protocol

Answers to your questions:

1) Random oracle - is a replacement for hash-function. Its input is any bitstring, and output - random string. In some sense - it's an ideal hash-function. But in order to evaluate it, you (attacker) need to explicitly ask the oracle.

2)  "Why would the adversary query g^ab to the random oracle. Is it part of the game?" - no, adversary of course isn't obligated anything for you, and it isn't obligated to ask ROM for $g^{ab}$. But, easy to see, that if the attacker didn't ask oracle for $g^{ab}$, he has only a negligible probability of success.
In the article it's simply expressed as "has no idea on the session key"; it's indeed true - recall that oracle will return some random string for this input, regardless of all previous actions/queries of the attacker.
While it's not a rigorous mathematical statement, it still correctly describes what happens.

In addition, I would try to explain why this ROM model good for modeling hash function. In this proof we essentially use the fact that any attacker will explicitly ask the oracle for hash-values, and we can track all these queries.
While in real life, for real hash function, we can't track attacker actions.
But, if hash-function is good (ideal), to get hash-value everyone needs to honestly calculate it by applying hash-function to some input (e.g.,
you can't derive hash-value of some input from hash-values of other, even somehow related, inputs).
So, if hash function is good enough, any successful attacker at some point should calculate hash from $g^{ab}$, i.e. this attacker should know $g^{ab}$ at some step. So, this attacker is able to solve CDH. This is a meaning of this proof in ROM. It doesn't mean that for any hash-function it's true - it's only true for good hash functions, which are really unpredictable and behave like random oracles.


How to Sample from Frobenius Eigenspace?

The Frobenius eigenspace of $-1$ is, by definition, the kernel of the map $π+1$. Typically, this is further restricted to some torsion group $E[ℓ]$, so we are really talking about $E[ℓ] ∩ E[π+1]$, i.e., those points of $E[ℓ]$ such that $π(P)=-P$.

If the curve is expressed in Weierstrass form $y^2=f(x)$ (or Montgomery, or similar), letting $P=(x,y)$ we have $-P=(x,-y)$. Thus the Frobenius eigenspace is made by those points $(x,y)$ such that $x^p=x$ and $y^p=-y$.  A little theory shows that this is the set of rational points of the twist of $E/_p$.

So, the obvious way to sample the points is to

Choose a random $x\in _p$;
Check that $f(x)$ is not a square, i.e., that $y=\sqrt{f(x)}$ is not in $_p$, i.e., that $y^p=\sqrt{f(x)}f(x)^{(p-1)/2}=-\sqrt{f(x)}=-y$;¹
See $(x,y)$ as a point in $E/_{p^2}$, multiply by an appropriate cofactor to obtain a point in $E[ℓ]$.

¹To see why this works, note that $f(x)$ is not a square in $_p$, thus its Legendre symbol is $-1$. By the way, saying $x$ is in $_p$ and $y$ is not is equivalent to saying that $x$ is the abscissa of a rational point on the twist.

If $\#E(_p)=p+1-t$, where $t$ is the trace of $π$, then the twist has order $p+1+t$, thus the "appropriate cofactor" above is $(p+1+t)/ℓ$. Note that $E[π+1]∩E[π-1]=E[2]$ (because $1=-1\mod 2$), thus for $ℓ=2$ the two ℓ-restricted eigenspaces are indistinguishable, and you would get a random point of order $2$; however for any other prime $ℓ$ there are two distinct eigenspaces, and step 3. will stay in the twist.

Steps 1. and 2. above can be replaced by Elligator 2, which samples simultaneously in both the eigenspace of $+1$ and that of $-1$. The original Elligator 2 was explained as a map to $E[π-1]$, but the generalization to a map to $E[π-1]×E[π+1]$ is easy and has been hinted at in several papers. For an explicit description, see Section 3, and Algorithm 3 in particular, here: https://eprint.iacr.org/2019/837.

All this can be generalized to arbitrary eigenvalues $λ$, not just $±1$. The multiplicative order of $λ$ in $ℤ/ℓℤ$ determines the degree of the extension of $_p$ where the points $E[π-λ]$ are defined.


Basic question on interaction with HSM using PKCS11

No, the operations on the key itself are not standardized and not supported by the PKCS#11 standard. There are some key derivation mechanisms, but even the NIST specified ones have hardly any support (which is kind of ironic, as key management is of course one of the main reasons to buy an HSM in the first place).

These operations are pretty specific to BitCoin and are therefore not standardized. It is of course possible to extend the base functionality of PKCS#11 with custom mechanisms. But in general HSM's will not be created with BitCoin wallets in mind.

Probably easier to create a BitCoin specific hardware module interface with your own software support. Some HSM's do allow custom code to be loaded, so you do likely not have to create your own hardware for that. Smart cards can be programmed as well. Prepare for a steep learning curve though.


HW acceleration for Camellia cipher (x86_64/AES-NI/AVX2)

The obvious answer to your question is "yes". The kernel mode implementation pointed to by otus clearly shows that it can be done.

That it can be done doesn't mean it gets done however. Many Google searches for sourcecode don't show any OpenSSL code that implements this functionality. In general, OpenSSL doesn't rely on the crypto code of the kernel. So, that means the hardware acceleration is not available. In general you should not expect that hardware-crypto availability is automatically reflected in (higher level) API's.

To resolve this you could either implement an engine yourself or ask for a feature request at OpenSSL. Note that Camellia interest seems to be dwindling. Nobody picked up the - relatively new - feature request for Camellia in authenticated ciphers or ciphersuites so they got closed.

It seems that Camellia is seen as a "vanity algorithm" by many; let's not do AES because it is too American, but do something almost identical instead.


"Work factor" and "iteration count" nomenclature in adaptive functions

There is no international committee on which function / term is correct or not.

Work factor seems to be a more generic term, and I'd prefer that when talking about the relative amount of work that needs to be performed. That - at least internally - an iteration count is used together with a hash algorithm is an implementation detail.

The work factor doesn't really have a generic value in itself.  So any password hash / KBKDF that performs key stretching must have a work factor. But how this work factor reflects the amount of work is algorithm specific. It could be using a logarithmic scale and for many algorithms this is the case. However, the iteration count - which is linear - is also a work factor - even if the specific algorithm specification doesn't explicitly use that name for it.

In the end, the best way to compare the time required (CPU time or user time) is to test the values. You can make a pretty good bet if you know the internal details, but in the end small changes - for instance the specific implementation - may make a lot of difference.


Hint: modular inverses are unique, therefore the following holds:

$$2^x \equiv 3 \pmod{p} ~ ~ \iff ~ ~ 2^{-x} \equiv 3^{-1} \pmod{p}$$

Now what is the inverse of $3$ modulo this particular $p$? Can you express it as a power of two modulo $p$? Solve for $x$. If you end up with a negative $x$, use Fermat's little theorem to derive a positive exponent.


Let's break apart the property description:

An active attacker

So an attacker who can both read and create packets on the network

who pretends to be the initiator

In the NK1 handshake, the initiator is anonymous, so it's not really pretending to be the initiator, it is an anonymous initiator like any other NK1 initiator

and records a single protocol run

This just means they remember every message sent and received. You need to do this to analyze the packets later! I'll give the analysis you do below.

can then check candidates for the responder's public key.

You explicitly ask about this part in your question. The responder's public key, whose identity you're trying to hide, is never transmitted in this protocol, so you won't be able to ever see or directly decrypt it. In order to learn the responder's public key, you can only check if a guess you have for the public key is valid. You could enumerate the entire public key space, but it's so infeasibly large you'd never find it. But if you think the responder might use a specific public key (its identity), say because you know a certain service uses that public key, you could check if your guess is right. That's what this part of the identity hiding property is all about.
How would you do this? The crucial bit here is that 2 Diffie-Hellman operations are done here: ee and es. For ee, you are the initiator and the server transmits it's "e", so you can do this DH easily. For es, you supplied the "e", but want to make guesses about "s". The implicit (possibly empty) transport message after the "es" token has a MAC whose key is derived from ee and es; so if you can guess the responder's public key "s", and you use it and it successfully validates the MAC sent, then you know your guess was right.
Finally, this property is last in the list because it was added last; deferred handshakes (like NK1) were added later. It's not the strongest identity hiding level, 8 is.


Can we break RSA with an optical Fourier Transform?

The horsepower underlying this algorithm is the Fourier transform

Not quite; the algorithm is to generate a superposition of states, compute the modular exponentiation of those states (generating the superposition of those results), and then use a Quantum FFT (actually, the inverse FFT[1]) to find a periodicity (and from such a period, you can deduce the factorization).

The issue for you is that this is an inherently quantum operation; the hardware you linked to performs a Discrete (Classical) FFT [2], which doesn't operation on superpositions.  And, if you don't perform the inverse FFT on a superposition, then you can't implement Shor's algorithm.

Hence, your idea using an optical hardware within superposition doesn't solve the problem at all...

  Are such alternatives viable (in a near future) to break RSA?

It doesn't appear that way...

[1] Requiring an inverse FFT isn't the main objection - I believe optics can perform that operation as well...

[2] Actually, it's rather easy to compute FFTs (and inverse FFTs) in software - the linked hardware's just claims it can compute it somewhat faster, but software already is pretty fast...


An adversary can easily win this game with $\epsilon = 0.5$ when the scheme under examination is any block cipher in ECB mode.

Simply set $m_0$ and $m_1$ to the same block value, $q$. This guarantees that you'll get the encryption of $q$ back, which we'll call $r$.

Then you can distinguish between $q$ and some other block value with probability $1$ on subsequent trial by checking whether $r$ is returned or not.


Encrypt challenge instead of storing it on the server

Short version:  No it is probably not safe; it will likely allow for a replay attack.

Longer version:  Defining what "safe" means is always a little tricky and dependent on a lot of other context.  With what you have showing in your sequence diagrams, the approach of sending AES(RndA) and not storing it on the server would allow your untrusted client to reuse that same data in a future transaction.

If the server simply compares the AES(RndA') and AES(RndA) that is receives from the client, there is nothing that ties it to this particular transaction.  Once a malicious client has done a single valid transaction, it can just send back the results for any future transactions.  Because the server doesn't keep the random value, it has no way to tie a given pair of AES(RndA') and AES(RndA) to a particular transaction.

You can add additional data like serial numbers, user ids, timestamps, etc to the encrypted values so that there is some state.  Those will help in some scenarios as supplemental checks, but they will never be as strong as simply keeping the full random value.


Is the linear and differential cryptanalysis only dependent on Sbox?

The question is contradicting with the title.
A random S-Box with a "very good diffusion mechanism" would be perfectly ok, assuming enough rounds.
A random S-Box without a "very good diffusion mechanism" would be worse.
For example, consider the AES with the S-Box replaced by a random S-Box. We can use known bounds on the number of active S-Boxes in AES (even the simple one - 5 active S-Boxes every two rounds), and use the differential uniformity / nonlinearity of the new random S-Box to give a provable bound on the differential/linear cryptanalysis. Possibly, we would need to increase the number of rounds a bit. Though, such proof would refer only to a single-trail cryptanalysis, but this is exactly what was done for AES. For example, truncated or higher-order differential cryptanalysis would not be covered.
Answering your question: security against linear/differential cryptanalysis depends both on the S-Box and the linear layer, though in a different way. Of course, in an edge case like fully linear S-Box, a strong linear layer won't help.


Cracking a hash when you know the result?

TL;DR: Salts are too long to try and brute force them.

In theory
You can create a mask attack using hashcat, specifically a hybrid attack.
Let's assume you know that the salt used is (only) 4 numbers.
-a 7 ?d?d?d?d myKnownKey.txt

myKnownKey.txt contains the key alturkovic.
This setup would then try out these combinations:

0000alturkovic
0001alturkovic
0002alturkovic
$\ldots$
9999alturkovic

This is one example of how to create hybrid attacks using hashcat.

In practice
In practice salts are (as SEJPM commented) of course not only just 4 digits long but they are very long random alphanumerical characters and thus renders any brute force attacks impractical.


Can Differential Privacy be used to show that two distributions are indistinguishable?

These sorts of arguments come up in the theory of randomness extractors where we argue that a random function from a certain family when applied to inputs with a certain minimum entropy ($H_\infty$, the -ve log-maximum probability of an outcome in the Renyi notation) produce outputs that are indistinguishable from uniform up to some $\epsilon$ bound. The differential privacy of the uniform and extractor distributions can be bounded in terms of input size, output size and $H_\infty$ (see for example the Kamp and Zuckerman theorem of the article).
The min-entropy should be the choice of entropy function when using differential privacy as it bounds the worst case scenario of concentration of inputs.


what are DP and DQ in Encryption by RSA in c#

DP is $d\bmod{p-1}$, similarly DQ is $d\bmod{q-1}$. InverseQ is $q^{-1}\bmod{p}$.

These are used in applying the Chinese Remainder Theorem to RSA decryption, which is an optimization technique.


Are SSL/TLS used for maintaining data confidentiality?

The answer to the first question is both.

TLS uses a custom PRF based on HMAC to generate symmetric and MAC keys from a shared secret. The shared secret is created during the asymmetric key exchange between client and server as part of the handshake.

The PRF generates key material of a required length. That length is determined by the key sizes and the key quantity. Those are related to the ciphersuite chosen. If an encryption algorithm provides both confidentiality and integrity (like AES-GCM), only 1 key per party is generated. If HMAC is used to provide integrity, 2 keys are generated. The PRF may also generated initialization vectors.

Different keys are generated for both client and server, so there are 2 keys generated for authenticated encryption algorithms, and 4 keys for algorithms that require a MAC for integrity. The keys used to encrypt the data in transit are used with symmetric algorithms. For data secured by TLS, the hash algorithms are used in the MAC, and not part of the encryption process.


So your idea is that the client does the work in calculating the slow hash $B(P)$, and proves that to the server by using a hash as an encryption key. It is definitely not a standard way to do things, and has some problems.

In particular, any eavesdropped can trivially launch an offline dictionary attack on the password, so it is like your normal password database was constantly compromised (which should normally lead to "change your password" emails being sent). That means any passwords that are simple enough to be attacked are completely unprotected.

Instead, I would second the suggestion of using TLS. Even if you can come up with a strong password authentication system that works in the clear, you need authenticated encryption to prevent eavesdroppers from reading the authenticated content etc.

If TLS is simply out of the question, you could use SRP. It, too lets you offload all the hard work of using e.g. bcrypt to the client, by using as B(P) as the SRP password: the server only uses the verifier, meaning it does not need to do the calculation. Unlike your protocol, it prevents both passive attacks on the authentication (as well as MITM). However, you should use the agreed key to authenticate and encrypt the rest of the session, or an attacker can just jump in at that point, so complexity is not that much less than TLS.

(You mention patent concerns. IANAL, but Stanford has a royalty free patent grant for implementing RFC 2945, and anyway the patent may already have expired.)


Detecting steganography by analysing non-significant data entropy?

You cannot detect the use of steganography without taking into account the inherent variation in the protocol. Of course, you should be able to detect bad steganographic practices that operate outside the normal limits - you don't expect huge swaths of whitespace in HTML - but well applied steganography should be hard to detect by definition. So I agree with your evaluation of (1).

Entropy is not complexity. Pi may be considered complex if you try to estimate the value of subsequent digits (in whatever base) without using the common methods to calculate Pi. A common X.509 certificate is rather complex, but only the modulus (of the public key within the certificate) and signature may contain entropy.

Furthermore, I don't see how complexity of the significant part and non-significant part are necessarily related in any way. Take the certificate: you can easily re-encode it using XML encoding rules. Now generally a converter doesn't add any whitespace. However, a simple XHTML file may contain a lot of whitespace placed almost randomly between tags as it may be human generated.

As there doesn't necessarily seem to be a correlation, it would be impossible to create a generic algorithm that could detect steganography. Of course, heuristics can be used, but given that the amount of variation is unknown it advance, there must be either false positives, false negatives or both given any protocol that allows variation and any steganographic practice.

So I don't agree with your assessment of (2), and in my opinion, no generic algorithm should be possible to exist. Proof: take a protocol that randomly adds a space or tab character, ignored by the receiving party. Replace these by a CPA secure ciphertext, bit by bit. Now both the original data and space/tab encoded ciphertext should be completely random to an adversary.


PKCS#10 why keeping the Subject Public Key in the X.509 Certificate

The certificate is signed with the Certificate Authority's private key, but the purpose of an X.509 Public Key certificate is to associate a public key with a subject-entity.

You generate a public/private pair
You generate a PKCS#10 CSR which contains the SubjectPublicKeyInfo, signed with the private key as proof-of-possession.
You submit the PKCS#10 CSR to a CA.
The CA does whatever validation they do to ensure that you're the subject that you claim to be in the CSR (or whatever subject you claim to be external to the CSR) ... and for whatever extensions you may have requested.
The CA copies the SubjectPublicKeyInfo into a new certificate they create, and they sign it with their private key.
People can now use the trust of the certificate to understand that signatures that come "from you" and verify under the public key within the certificate are actually from you (or used a stolen/cracked version of your private key).

Alternatively: Whose public key do you want them to put in your certificate?  If they just made one up on the fly for you they'd also have had a copy of your private key, which is clearly less secure than only you ever having your private key.


Is it possible to test 15-bit PRNG with the library TestU01?

It can be taken groups of 32 samples of 15 bits, and turned each into 15 samples of 32 bits, either by transposition, or concatenation then splitting.

The best of the two method depends on the nature of the test, and TestU01 has several tests (as test suites do). If in doubt, use both methods. Should any valid test consistently fail more than predicted by its P-value, the generator has been demonstrated broken.

As always: absent any information on the generator tested, passing a statistical test gives zero insurance about its suitability for cryptographic purposes.

  For instance, the generator included in the book The C Programming Language by Brian Kernighan and Dennis Ritchie is a 15-bit generator.

/* rand: return pseudo-random integer in 0..32767 */
int rand(void);

A 15-bit wide output can be cryptographically OK, but this generator's narrow key (an int) makes it a no-no from a cryptographic standpoint, even when we consider only its interface to set the key:

/* srand: set seed for (rand) */
void srand(unsigned int seed);

Further, when we consider the details of the implementation

unsigned long int next = 1;

/* rand: return pseudo-random integer in 0..32767 */
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (unsigned int)(next/65536) % 32768;
}

/* srand: set seed for (rand) */
void srand(unsigned int seed)
{
    next = seed;
}

we note that

Only the low-order 31 bits of next and seed matter to the output, even when intand long are much wider (since next * 1103515245 + 12345 gets truncated to some number of low-order bits of the mathematically accurate result when it overflows; bits of next diffuse on the left only; and those above 31 do not make it to the result of rand).
Among these operative 31 bits of next, 15 are known from one output, making it trivial to perform a brute-force search of the other 16 bits to recover the full state from 3 consecutive output. And there are even simple methods avoiding enumeration, thus scaling the generator from 31-bit to 256-bit would not make it secure.

Thus this particular generator is totally weak from a cryptographic perspective. Yet it still gets a pass from many statistical tests (including Ent applied to a few kilobytes of its output); and a scaled-up version of that generator would pass even more tests for all practical sizes.

Due to the particular structure of this generator, the best way to demonstrate that it is weak from the results of a byte-oriented Chi-squared test like Ent might be to keep the low-order 8 bits of each 15-bit output, and throw away the rest. But that's not a general rule, it depends a lot on the generator, and also on the test.


anonymous signature implementation and usage?

The first google-entry brought up this paper.
To answer your questions:

An anonymous signature is a signature that is unforgeable in the classic sense. But without the message no informations about the signer can be extracted from the signature even if brute-force of all public keys is possible.
If I'm understanding things correctly, a blind signature hides the message from the signer but the signer is still known. So the signer is not anonymous whereas with anonymous signing the signer is anonymous as long as the message is unknown, but the signer knows what he's signing. (I hope that makes sense)
The paper will give you insight in how to actually implement anonymous signature.

You may also wish to read this paper and maybe even some references to get further ideas. In the mentioned paper there's an approach the anonymize the signer by holding back parts of the signature.


why does TTLV encoding in KMIP require padding?

The padding in KMIP is present only when data is converted to TTLV format, which is a binary representation of KMIP data. TTLV padding exists to "provide optimal alignment for both 32-bit and 64-bit processors" according to the kmip specification. It's generally easier for a CPU to load memory when it's aligned to certain byte widths, especially when the CPU is doing work in parallel.

see section 9 in the kmip 1.0 spec:
https://docs.oasis-open.org/kmip/spec/v1.0/os/kmip-spec-1.0-os.html#_Toc262581260

wikipedia describes how "there can be substantial performance advantages from using aligned data" on x86 cpus:
https://en.wikipedia.org/wiki/Data_structure_alignment


How to convert RSA public keys to one key to use for text hashing?

An RSA public key is made of 2 parts, the modulus n and the exponent e.  They are both required, and neither alone can be considered "the key".  Often e will be one of just a few different values, but this is mostly convention and shouldn't be assumed.

RSA does work on integers; if your data is of another form, you have to specify how to convert it.  For instance, if you have text you might encode it to a byte array with UTF-8, then take blocks of bytes such that the number if bits is less than the length of n, and then treat that byte array as one big integer (either little-endian or big-endian).

But you probably don't want to be doing this math yourself, and there are a lot of pitfalls (padding, etc) to trap the unwary.  You should be using a library that someone has already implemented.


How would quantum computers affect password based encryption?

Currently we use slow key derivation functions. If a hypothetical quantom computer could run these as fast as a classical computer (Which is a huge If) grover's algorithm would allow searching over the equivalent of the squared root of the password space.
However even a sizeable quantom computer won't be able to do that. We will be seeing Shor's algorithm being used to attack RSA and DH before we see Grover's used to attack old 128 bit encryption. And that before it will be used against a password based key derivation function.
And I expect none of this soon.


In some applications, a serious limiting factor for the security of 4DES is its 64-bit block size. In common modes of operation, that limits the security to data sizes that are insufficient for many application nowadays. It makes 4DES much less secure than AES-128 is.
For example, assume a VPN in CBC mode using a fixed key. Assume an adversary injects known traffic consisting of a known repeated byte representing 99.9% of the payload for 64 GiB of reference ciphertext, then gets another 64 GiB of actual ciphertext. With good probability there is at least one match between one of the $2^{33}$ blocks (of 8 bytes) of the reference traffic and the $2^{33}$ blocks of the actual traffic. And any such matching block can be deciphered correctly with >99% probability.
If we want residual risk at most $\epsilon$ that this kind of attack succeeds, we need to limit the traffic with the same key to about $2^{36}\,\sqrt\epsilon$ bytes. For a residual risk of one in a million, that's about 64 MiB, not a lot by modern standards.
While DES-CTR with non-overlapping counter is less susceptible to this attack than DES-CBC, such mode is unusual, impractical, and remains vulnerable to a distinguishing attack at similar data size threshold.


Obfuscating functions that are mostly zero

I provide a summary below of what is currently known (to my knowledge) regarding obfuscation of various class of "mostly-zero" functions.

From Indistinguishability Obfuscation

What we can obfuscate: all efficient functions

Which notion of security: indistinguishability obfuscation

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.

You state in your question:

  I also know that there is no generic scheme that can obfuscate all functions -- but perhaps it's possible to find a generic scheme that obfuscates all functions in this class.

However, as far as we know, it is perfectly possible that all efficiently computable functions (hence in particular all functions you are interested about) can be obfuscated with an iO scheme. We have a bunch of concrete candidates, and there has been a large body of work on the underlying assumptions. Providing a complete treatment would be out of scope for this question (I count more than 160 papers on the subject since 2013), but roughly, all known constructions of iO rely on exotic assumptions: either the existence of graded encoding schemes, whose security is poorly understood and with many (many) existing attacks, the latest being this one, or recent assumptions regarding the weak pseudorandomness of some extreme families of low depth pseudorandom generators -- some assumptions made in the three latest results (1, 2, 3) in this area have already been broken. Furthermore, none of the iO schemes we currently know of would be concretely efficient. Still, as a theoretical feasibility result, all functions you care about can be obfuscated (under exotic assumptions), where the obfuscation security notion is that of indistinguishability obfuscation.

From Multilinear Maps

What we can obfuscate: evasive low-degree polynomial modulo a prime

Which notion of security: virtual black box obfuscation (the strongest possible notion)

Underlying assumptions: new, exotic, and relatively poorly understood assumptions.

Is it efficient? Nope.

Barak et al. study in this paper the possibility of achieving even stronger notions of obfuscation (such as virtual grey box obfuscation, or virtual black box obfuscation) for the class of evasive functions. A class of function is evasive if, for any fixed input $x$, a random function from the class evaluates to $0$ on $x$ with overwhelming probability. While their results are mainly negative, Barak et al. also provide an interesting positive result:  under a new perfectly-hiding multilinear encoding assumption, which is the same kind of assumption that is used in constructions of iO schemes (hence suffers from comparable weaknesses and gives comparable (in)efficiency), there exists a virtual black box obfuscator for evasive functions that tests if a low-degree polynomial evaluates to zero modulo some large prime. Virtual black box obfuscation is the ultimate security notion for obfuscation: while iO states that it should be infeasible to distinguish two functionally equivalent obfuscated circuits, VBB states that everything that the adversary sees, given the VBB obfuscation of the function, can be simulated given only black-box access to the function. It is known that VBB is in general impossible to achieve; hence, this work shows that this impossibility does not seem to hold anymore for this restricted class of evasive functions.

From LWE

What we can obfuscate: conjunctions, compute-and-compare functions

Which notion of security: distributional virtual black-box

Underlying assumptions: the well-studied (conjectured quantum-resistant) LWE assumption (or entropic variants of it)

Is it efficient? Not really, but depending on the primitive to obfuscate, it can be doable.

There has been recently a large body of work identifying interesting classes of "mostly-zero" functions, which can be obfuscated under the plain (or variants of) LWE assumption, which is a well-studied assumption.

1) Conjunctions. Several papers have proposed schemes to obfuscate functions of the form

$f : (x_1, \cdots, x_n) \rightarrow \bigwedge_{i \in I} y_i$,

where each $y_i$ is either $x_i$ or $1-x_i$, and $I$ is a subset of $[1, \cdots, n]$. This paper shows how to obfuscate this class of function under an "entropic variant" of the ring-LWE assumption. Obfuscating a 64-bit function takes a few hours, and evaluating the obfuscated program takes a few seconds. The security notion achieved is that of distributional VBB obfuscation, a variant of the notion of VBB obfuscation which also relies on the entropy of the obfuscated function.

2) Compute-and-compare functions. This is a very nice result achieved independently in this paper and in this paper. Assuming only the plain LWE assumption, they show how to compute a very large class of interesting evasive functions: the functions that have two secret values $(\alpha, \beta)$ hardcoded and, on input $x$, evaluate an arbitrary function $f$ on $x$ and output $\alpha$ if and only if $f(x) = \beta$ (and $\bot$ otherwise). This captures as a particular case conjunctions, point functions, but also much more. Their construction also achieves distributional virtual black-box obfuscation.

From Group-Based Assumptions

What we can obfuscate: conjunctions, pattern matching, hyperplanes membership

Which notion of security: distributional VBB

Underlying assumptions: from entropic DDH to the generic group model

Is it efficient? It can be reasonably efficient

Many constructions have also been designed under various assumptions in standard discrete-log-hard abelian groups. Most notably:

1) Conjunctions can also be obfuscated in the generic group model, and achieve distributional VBB, as shown by this very nice recent paper.

2) Pattern Matching. Two recent works have considered the task of obfuscating functions that test whether a given input string contains a pattern, with "wildcards" (i.e., the pattern can contain wildcards * that correspond to "any value there"), and achieve distributional VBB for patterns having some entropy. These are very nice results, and are in addition relatively efficient compared to everything that I've discussed so far. The first of these paper achieves security in the generic group model, while the second achieves security in the standard model, under a knowledge-of-exponent style assumption (i.e., something plausible, but far from being the most well understood assumptions).

3) Hyperplane Membership Testing. Eventually, this paper shows how to obfuscate hyperplane membership testing (i.e., checking whether an input vector belongs to a secret obfuscated hyperplane), which generalize point functions to a much larger class. The obfuscation is relatively efficient and is proven secure under a strong variant of the DDH assumption.

Note: there exists also DDH-based obfuscation scheme for re-encryption functions, but those do not fit into your notion of mostly-zero functions.

From One-Way Functions

What we can obfuscate: point functions

Which notion of security: distributional VBB

Underlying assumptions: exponentially strong one-way functions, one-way permutations, or deterministic encryption

Is it efficient? Yes

To conclude this overview, the weakest of all these "mostly-zero" functions that you want to obfuscate are point functions, which are equal to zero everywhere, except on a specific point. Such functions can be obfuscated, depending on the exact notion of obfuscation achieved, assuming the existence of exponentially strong one-way functions (here) or one-way permutation (here), or deterministic encryption (here) all being highly plausible assumptions (the second one being even a fundamental assumption of cryptography). Obfuscation of point functions has been studied in depth and has many applications in cryptography. Note that to achieve stronger notions of obfuscation for point functions (e.g. to achieve composability, or non-malleability), one typically rely on stronger DDH-like assumptions (e.g. here and here).


What is the new attack on OCB2 and how does it work?

How does the attack work (on a high level)?

It's an unfortunate consequence of how the pad of the last encryption block is computed. The pad can essentially be used to both eliminate the block cipher operation for a chosen ciphertext's decryption (allowing the attacker to determine the plaintext) and the pad can be used as the tag in this attack. It's quite incredible.

The attack crafts a special initial plaintext, sends it to an encryption oracle, receives a ciphertext and tag, modifies both of those, and then sends them to a decryption oracle which accepts the modified tag for the modified ciphertext (hence, a successful forgery).

The modified ciphertext (which is submitted to the decryption oracle) will have it's block cipher operations cancelled out in decryption. See the paper for details on how this works. The gist of the idea is that the pad used for the last (and only block) has the same block cipher operation in it as the ciphertext block. Said another way, the pad and the ciphertext are both the results of data xored with the block cipher called on the same input. Since the pad is xor-ed with the ciphertext block, we essentially eliminate the only operation requiring knowledge of the secret key, so we now know what the plaintext will be.

The correct tag for the modified ciphertext turns out to be the pad from the original encryption oracle call. This pad is simply the last block of the initial plaintext, which was sent to the encryption oracle, xor-ed with the last block of ciphertext that the oracle outputs. So a forgery takes exactly one encryption oracle call.

I highly recommend reading the paper for details, I've tried to keep all the math out of this since you asked for high level, but the magic is really in how the plaintext is crafted and how the ciphertext is modified in a way that the corresponding tag can be deduced by the attacker.

  Why did the proof by security reduction fail?

The security reduction failed because of a subtlety in how XEX (xor encrypt xor) and XE (xor encrypt) were combined into XEX* for OCB2 mode. The issue is that, even if the encryption function (e.g. the block cipher) is information theoretically secure (think a uniform random permutation), XEX* is not.

There is an issue with what the adversary is, by definition, allowed to do in the security proof of OCB2. The adversary is assumed to be tag-respecting, i.e. it can only query the encryption and decryption oracle with certain parameters to XEX*, but the construction of OCB2 actually violates this tag-respecting property in a very subtle way. I again will refer you to the paper for details, the proof is a bit complex and there's no good way to thoroughly give it without re-rewriting it.

The solution to enforcing this tag-respecting property is rather simple, which is to use XEX to generate the padding used in the last block, rather than XE.

  What are the implications?

This break is very specific to OCB2, down to how it uses XEX*. OCB1 and OCB3 are not affected. Use of the ISO spec of OCB2 should be discontinued. For deployments using OCB2 that need to path a quick fix, the solution mentioned above of using XEX rather than XE for the padding of the last block should suffice. The authors call this modification OCB2f and assert that the security bounds claimed for OCB2 are in fact now correct.

I've tried to answer in readable fashion without getting into all of the technical details (which would amount to re-writing the paper), but the best way to really understand the attack and its impact is to read the paper and grok the math behind how the attack works, and how it violates the assumptions that were made in the original security proof.


Maximum security strength in bits of ISAAC cipher?

ISAAC's internal state is a 256-element array of 32-bit words, so the maximum key size is 8192 bits. In theory, this means ISAAC has a maximum keyspace of 28192. It's important to remember, though, that attacks are known that can result from weak states, meaning not all keys are created equal. While this may not be an issue in practice, there are two primary reasons why you shouldn't use it:

It's not particularly well-researched, so more serious attacks may be lurking.

The entire 8192-bit keyspace is utterly unnecessary. 256 is more than enough.

Just stick with 256-bit AES if you need a block cipher, and ChaCha20 if you need a stream cipher.


Encryption scheme for social-network-like data sharing data via untrusted server?

Yes, it's trivial. You encrypt each item with its own random key. You then need only encrypt the key to each album for Bob and Carol.

A typical way to do this is to publish an encrypted per-user keyring -- one for Bob and one for Carol. Bob and Carol can each decrypt their keyrings to get the keys to all the objects they are supposed to access.

The reverse way of doing this is to attach to each group of objects with common permissions a per-group keyring. This is usually used in conjunction with a public key for each user. The key to the group of objects is encrypted with the public keys of every user authorized to access it and those encrypted keys are stored with the group of objects.


How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem?

Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$.

Here's the proof; suppose that there was an efficient way to recover $k$ given a $n$ different $b_i^k = g_i$ equations.

Then, we can efficiently solve the simple equation $b^k = g$ by doing the following:

We select $n$ random values $r_1, ..., r_n$
We compute:

$$b_i = b^{r_i}$$

$$g_i = g^{r_i}$$

We have our $n$ equations, as $b_i^k = (b^{r_i})^k = (b^k)^{r_i} = g^{r_i} = g_i$, so we use the efficient way to recover $k$ given $n$ equations.

We then know the solution $k$ to the original equation, and the only extra time we took was to the time select $n$ random values and to compute $2n$ modular exponentiations.


Combining a keystream generator with a block cipher

Under your scheme, the keystream generated by the stream cipher will be the same for each message enciphered with the same key. While your scheme does not encrypt identical blocks of plaintext in the same message to the same value, it does encrypt identical blocks of plaintext in different messages to the same value, meaning that XORing two ciphertexts together will give clues to the structure of the plaintext inside. This can quickly become relevant when used, for example, in a network protocol, because the sorts of structured data computers like to exchange with each other frequently include significant repeated or predetermined segments.

Completely beside the issue of whether your scheme provides confidentiality, it can't replace using "complicated" block cipher modes of operation, because its performance would be abysmal. It's not obvious from the definition of a block cipher, but there is a reason that all the popular block cipher modes of operation vary what they do with the plaintext or what they do with the ciphertext but never get inventive with what they do with the key. In block ciphers, a significant amount of computation is put into expanding the key into a "key schedule," or list of the subkeys that will be used in each round of the cipher. Once the key schedule has been calculated, subsequent blocks can re-use the same data if the key hasn't changed, meaning that encrypting 1,000 blocks with a single key is much, much faster than encrypting them to different keys. If you wanted to change the key for each block, you'd have to re-do the key schedule operation each time, and that would suck.

Finally, a note on IVs. An external source of entropy, in the form of an IV, is required for probabilistic encryption schemes. Probabilistic encryption guarantees that the same message encrypted twice will not produce the same ciphertext, and that property is needed to assure semantic security. However, semantic security is a very strong requirement, and while using deterministic encryption (for example, by calculating an IV deterministically as I suggest in the comments on Maarten's answer) means you won't have semantic security, for many applications it's good enough. Consider implementing strong encryption on a microcontroller, where entropy is scarce and available sources are easily tampered with: deterministic encryption will leak that you've encrypted the same thing twice, but that's usually much more acceptable than courting the spectre of a full-blown break if someone somehow manages to poison your PRNG.


How does a backdoor in the RNG enable an attacker to break encryption protocols?

There are three ways a RNG can fail

Insufficient randomness in the input
Losing randomness as a result of the random transformation
Leaking bits through an intentional or unintentional side channel

Each fail weakens things. A backdoor in a random number generator is like actively implementing such a fail, introducing possible ways to lower the security of the random number generator since it becomes less random.

It it's not as if a backdoor in a random number generator always directly breaks things like SSL, but they can have the ability to. The real problem is that a well constructed backdoor is near to undetectable, while allowing an attacker to take security shortcuts that wouldn't be available normally. And that would happen without the person using the RNG for security purposes noticing the backdoor.

Imagine using such a backdoor to seed something... it would look perfectly random to you, but the one who implemented the backdoor might be able to recover the whole state of the RNG by just looking at - let's say - 32 bits. That would mean you're in big-big trouble. Now imagine you feel good, safe and secure because you aren't aware of a backdoor lurking behind the screens... get a creepy feeling? Good!

Practically describing it all would be too broad, and giving you a walk-trough would be too long and too technically detailed... but if you want to learn a bit more generally why a backdoor in an RNG might be a real security issue, you could read a bit about it in "The Many Flaws of Dual_EC_DRBG " which talks about a prominent, recent backdoor in an RNG and shows what practical impacts it would have had on cryptographic implementations:

  If I use the Dual-EC PRG to generate the "Client Random" nonce transmitted in the beginning of an SSL connection, then the NSA will be able to predict the "Pre-Master" secret that I'm going to generate during the RSA handshake. Given this information the connection is now a cleartext read. This is not good.


(Why) should I avoid using a randomized IV for CTR mode?

You say that a random IV "would also be unique", but really that is the crux of the problem.  The problem with counter mode is that it is secure unless the same counter is used twice; if it is, it is likely that an attacker will be able to recover both plaintext messages.  This contrasts with CBC mode, which if you repeat an IV, it has the relatively benign failure mode of allowing an attacker to detect whether or not the initial blocks of the messages are the same.

So, with random IVs, is the probability of a repeat sufficiently negligible that we can live with the possibility?  Well, that depends on the size of the IV, the total number of messages we're talking about (and our tolerance to risk; how small is negligible).  With 8 byte IVs, well, we're likely to see repeats (because of the Birthday Paradox) after a few billion messages (and have nontrivial probability of repeats before then); I would consider that too high of a risk to live with.  With 12 byte IVs, it's unlikely we'll see a repeat before a few trillion messages, but for very long-lived keys, perhaps this is unacceptable.  With 16 byte IVs, it is unlikely to ever see a true repeat, however now we'll need to worry about partial overlaps (where two different IVs generate the same block cipher input after combining with the counter for different parts of the messages).

In contrast, with CBC mode, we don't have to worry about any of this.  Once we make sure that the IVs are generated unpredictably (and we check the integrity of the encrypted text, a requirement of CTR mode as well), we're golden.  I believe Ferguson et al recommend CBC mode specifically because it is more foolproof and less fragile.


Requirement for the length of a HMAC tag?

Short answer, no.

The 112-bit value is actually the security parameter, and not necessarily the key length. For all NIST hash functions, the security provided is half the output bit of the hash function, therefore SHA-224 or better is required for 112-bit security. The security parameter we are considering is collision resistance.

However, there are other considerations for a MAC, such as how long the attacker will have to forge the code, which in some applications can be shorter than a second, and you can get away with a shorter code, such as 96-bits, which provides only 48-bits of security. A threat analysis of your application can determine if this is acceptable. 96 and 128-bit MACs are common lengths for short lived messages, with 128-bits becoming standard for new algorithms. How MAC failures are handled is also very important.


Proving that a scheme is not IND-CPA-secure

Seems like you're getting confused between two different notations. Generally, in the experiment, adversary $A$ will output a bit $b'$. So, we have the following notations which refer to the bit $b'$ output by $A$:
$$Pr[A(n)=1]$$
and
$$Pr[A(n)=0]$$

Now, $A$ is said to have won the experiment if $b'=b$ and that is captured by the following notation. Here, we are interested in the outcome of the experiment.
$$Pr[Game_A^{CPA}(n)=1]$$

The $=1$ in the above should not be confused with $A$'s output. Rather $1$ means $A$ wins (i.e. $b'=b$) and $0$ means $A$ loses (i.e. $b' \neq b$)


Are CFB and OFB really meant for streaming?

CFB does require padding unless you use a segment size of 1 bit (or 8 bits if your message is byte oriented). Check Section 5.2 in NIST 800-38A:

For the CFB mode, the total number of bits in the plaintext must
be a multiple of a parameter, denoted s, that does not exceed the
block size

OFB indeed does not require any padding.

There are no other limitations on the plaintext (but read very well the requirements about Initialization Vectors!).


Is there a secret sharing scheme which allows sharing of a secret (one-out-of-n)

Just tell the whole secret to each person.


Any practical uses of machine learning for cryptography?

I would personally be very surprised if machine learning was of any use in a known plaintext attack.

We design our ciphers to look a lot like random functions; you give the black box an input, and an output spits out.  You give it a second input (possibly the same input in the case of nondetermanistic encryption), and a second output spits out.  What we try to achieve is that no one can determine whether the black box was our cipher (with an unknown key), or whether it's just spitting out random outputs.

Now, we assume that the attacker has the complete design of our input (apart from the 'key'); in a successful cipher, he still cannot determine it.  In fact, we design things so that the attacker can submit inputs of his own choosing; he still cannot determine whether he's giving inputs to the cipher or a random function.

Now, what machine learning would be trying to do is essentially this, except that you would be ignoring the design (because there's no way to give the design to the machine learning process), and you are limited to a known plaintext attack (because your machine learner has no way to generate the chosen inputs).  In addition, your machine learner would also not have the best asset a cryptanalyst has (which is his cleverness; programs aren't good at 'clever').

Now, I don't know enough about machine learning to say that it can't be used elsewhere (or that a clever cryptanalysis couldn't use a machine learning program to help with his cryptanalysis); however it certainly sounds to me that machine learning would not be enough to do the entire cryptanalysis job.


Yes, you can do this.  In fact, implementing other cipher modes is precisely what ECB mode is good for (and, indeed, just about all it is good for).

To implement AES-CTR, simply fill an array of 128-bit blocks with increasing counter values, encrypt it with AES-ECB and XOR the resulting keystream with the plaintext (for encryption) or ciphertext (for decryption).


How is an IV used in a Merkle-Damgard construction- Explicit example

If the function takes two inputs of 4-bits each, then yes, 4 of the bits would come from the IV.The output of the function would be used as the IV (although it is no longer initial) of the next iteration of the function with the next 4-bits of the message.

Since the function outputs 4-bits, the final digest would also output as a 4-bit digest.


Diffie Hellman unsafe prime vulnerability

For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible.

Actually, it's straightforward to compute $A^{\frac{p-1}{r}} \bmod p$; one straightforward way is to use the binary exponentiation algorithm.

If $\frac{p-1}{r} < 2^n$, then this will take no more than $2n$ modular multiplications (and so, in your example, fewer than 8184 modular multiplications); one could do somewhat better, but this is good enough to show that it is practical.

Note: you use those same algorithms to make the computations within DH (computing $g^x \bmod p$ for large $x$) feasible.

Note on the notation (which might be what is confusing you): sometimes, we leave off the $\bmod p$; at those times, we assume that the reader will understand that we are not working in $\mathbb{Z}$, but instead in the field $\mathbb{Z}/p$, and hence the $\bmod p$ operations are implicit.  This is similar to how, in other branches of math, you are assumed to know whether we're working in $\mathbb{Z}$ or $\mathbb{R}$ or $\mathbb{C}$...


Can someone clarify two things about the HKDF by Krawczyk?

For example, there are no current attacks to HMAC-MD5, although MD5 is broken for several years. Hash functions have very strong requirements (e.g., collision resistance, preimage resistance, etc.), and some hash functions have been shown to fail some of these requirements (e.g., MD5 is not collision resistant). Hash-based KDFs may be affected by the problems of these hash functions, since they directly use their output, normally a concatenation of iterated inputs. On the contrary, HKDF only requires that the compression function behaves like a PRF, which is a much weaker assumption.

See these other questions for more details:

Is HMAC-MD5 considered secure for authenticating encrypted data?

Security of KDF1 and KDF2 (hash based KDF's)


Password in first line of file for AES-256 encryption

Yes it's secure if:

the password contains (i.e. is chosen using) sufficient entropy to resist attack. In practice this means it must be generated by a physical process (like rolling fair dice or flipping fair coins) or a good computer program (usually not the C library rand() function for example) not chosen by a human. Humans are very bad at choosing "randomly" and even when we think something "looks really random" it isn't; see also https://security.stackexchange.com/questions/79275/are-humans-a-strong-or-weak-rng . Note that PBKDFs are usually designed to be artificially
costly and thereby 'stretch' a human-chosen password, but openssl enc uses only ONE iteration of MD5 and adds no strength; even in the 1990s this was not good practice.
the pw file, and all stored and/or (edit) transmitted copies of it, are never available to an attacker but conversely the password data in the file is never lost (unless all the data encrypted using it is also discarded or lost so it is no longer needed)


RSA signature send signature with encrypted message?

The archetypal mistake would be to send in clear the signature of (the hash of) the message itself, for it would allow to check a guess of the message.

This leaves us with (at least) two general safe sketches (the first having advantages including allowing earlier elimination of bogus messages on the receiver side)

encrypt, then sign the whole encrypted message;
sign, then encrypt the whole signed message.

In both cases

encrypt can be: draw a random key, then apply encryption padding, then apply the RSA exponentiation with a receiver's trusted public key, then append to that cryptogram the encryption of the input with a symmetric cryptosystem using said random key;
sign can be: hash he input, then apply a signature padding, then apply the RSA exponentiation with a sender's private key, then append that signature to the input.


Why are finite groups used in cryptography?

Can someone explain why is that the case?

Cryptosystems based on finite sets have two very nice properties:

There is an upper bound to the size of all involved mathematical objects. This also allows one to predict things like memory usage rather well. This also means that the precision / memory you need can't grow arbitrarily / infinitely.
You can actually draw numbers at random according to some distribution. You can't draw a number uniformly at random from the natural numbers because you'd have probability $0$ of drawing any single specific one. Also in theory if you wanted to sample a normal distribution, you could get $10^{10^{100}}$ drawn (even though that's unlikely) which also brings back the first point.


Elliptic curve point addition clarification

What happens if you naively plug those numbers into the addition formula?  Anything obviously untoward?

This may be an exercise in the impact of invalid-curve attacks.


Regarding the feasibility of MPC protocols

Are any theoretical results regarding the feasibility of MPC protocols? To be more specific, are there any functions that are infeasible to compute in an MPC?

Yes, there are hundreds of paper on MPC feasibility. The answer always depends on the adversarial model. Here are a few of the more well-known/standard results:

$n$ parties can compute any function of their inputs, in the presence of a passive (semi-honest), computationally unbounded adversary that corrupts strictly less than $n/2$ parties.
There are functions that can't be computed in the presence of a passive adversary that corrupts $\lceil n/2 \rceil$ parties.
$n$ parties can compute any function of their inputs, in the presence of an active (malicious), computationally unbounded adversary that corrupts strictly less than $n/3$ parties.
There are functions that can't be computed in the presence of a malicious adversary that corrupts $\lceil n/3 \rceil$ parties.
$n$ parties can compute any function in the presence of a passive computationally-bounded adversary that corrupts any number of parties.
Most functions can't be computed against an active adversary in a way that provides universal composability, if there is no setup (like a common reference string).

I have taken all of these examples from a survey chapter that I co-wrote on the topic. You can find the original references there.

  Even more specific, are there any 2-party computations that are impractical to run (assuming that both parties are honest), yet are practical to run by a single party that held both inputs?

This is a harder question to answer because it is more about concrete efficiency than feasibility. There are theoretical results about how you can compute everything securely with "constant overhead" relative to the plaintext computation, but none of these results are what you would consider practical.

Using a more colloquial interpretation of what's "practical", pretty much everything falls into your category of "impractical" under secure computation. As @SEJPM points out in the other answer, unless you know that your problem has a lot of structure, the only known way to do 2-party secure computation would be to translate it to a boolean/arithmetic circuit and securely evaluate that circuit. This is many orders of magnitude slower than just computing something on raw data.

I know very few examples where the secure computation is reasonably close in efficiency to the plaintext computation. One such example is private set intersection, which is only ~ 6-8x slower than insecurely computing the intersection.


You probably don't want to encrypt data with a key derived from a password directly with a KDF. This makes changing the password require rencrypting everything. You can instead encrypt data with a strong random key. And encrypt the key with a password derived key. This encrypted key is what you keep.
You can also encrypt this key with other keys. Including a random key the user downloads and keeps wherever, possibly on paper. Or you can possibly split a key into multiple shares to be kept separately.

Obviously if you have multiple ways to decrypt your key, it is only as secure as the weakest method.


On Program Verification Through zk-SNARKs

I think the simplest and the best example for a system which uses zk-SNARKs to verify execution of a computation (program) is the Pinocchio system, developed by Microsoft and IBM research groups. You can get access to their source paper, which has some examples, in this URL.

With regard to your questions; the meaning of verifying an execution is that you check that the computation of your target program or circuit has been done correctly. E.g. assume you have a program $P(.)$ and you need to run this program with some inputs, e.g. $x$. Due to some reasons (e.g. low power device, save money) you outsource the computation and ask some cloud computing services (e.g. Amazon service, Google, Microsoft) to execute this program with this input for you and return the result. The cloud executes the program with your input $x$ and returns $y=P(x)$ to you. But if you do not trust the server, you are not convinced that $y$ is the correct answer for $P(x)$. To deal with this issue, the cloud (service provider) needs to give a formal proof that the execution of $P(x)$ is done correctly.

Note that outsourcing computation makes sense only if checking the proof generated by service provider is easier (lighter) than recomputing $P(x)$ by verifier himself.

zk-SNARKs such as Pinocchio uses pairing-based cryptography which makes the proof size very short (less than 1KB) and proof verification very efficient for verifier (client), verification time is around 0.1 second on current smartphones or laptops.

To get a clear view about how zk-SNARKs are used to prove that an execution of a circuit is done correctly, I strongly recommend to look at Pinocchio system. For a quick overview check the following Slides. At a very high level, the following figure shows what steps Pinocchio system (that uses zk-SNARKs) takes to give a proof for a computation.


Security strength for encryption and authentication (wrapping) of cryptographic keys

There is a non-academic kind of answer, that states that there is no better security than "cannot break it", and 128-bit keys are already quite far into that zone, leading to the following recommendation: 128 bits for everything, and be done with it.

A dual version, often encountered in marketing and compliance circles, is that larger keys are always better, and more apt at wooing auditors or customers; thus, you need 256-bit keys everywhere. If you could paint keys, you would make them red, or decorated with shark teeth drawings.

Of course, this cannot please everybody. There are some rational objections related to multi-target attacks: if you want "128-bit security" but you have a set of $2^{30}$ keys to try to attack, and finding any one of them is enough for the attacker to "win", then you need 158-bit keys to reach your specific level.

For that kind of analysis, context matters a lot. For instance, if you have one wrapping key $M$, used to protect $2^{30}$ keys $K$, and you want 128-bit security, then $M$ must live in a space of size at least $2^{158}$. Conversely, if you have a single key $K$ but it has been wrapped with $2^{30}$ distinct keys $M$, then the attacker only has to break on of the wrapping keys to obtain $K$; in that situation, $M$ should have length 158 bits or more, while $K$ may remain at 128 bits.

Therefore, there is no fully defined clearcut context-free answer.

The authentication tag is not about confidentiality, but integrity. Integrity matters, notably because in most contexts where attackers can observe confidential data, then can also change it. For instance, over the Internet as it is practiced today, to eavesdrop on a link, you must be physically connected to that link, or arrange to make the link pass through hardware you control (e.g. you run your own WiFi access point, or you poison the DNS to make target names resolve to the IP address of your own server).

There again, context matters a lot, as well as application conditions. Suppose, for instance, that wrapping uses AES/GCM with a 256-bit wrapping key $M$. An attacker could try to find the key through exhaustive search, which is going to be expensive ($2^{255}$ tries on average). On the other hand, the attacker may "just" want to make a forgery (feeding the recipient with a fake encrypted key); with a 128-bit authentication tag, the attacker has probability $2^{-128}$ of succeeding at each attempt. In that sense, the authentication tag offers only 128-bit security.

But the situation is quite different! In the exhaustive search on the key, each "try" correspond to the spending of some computational power by the attacker on his own machines. This attack is not limited by anything else than the attacker's budget. On the other hand, each "try" on a forgery attempt implies talking to the recipient, to see if the altered wrapped key will still be accepted. That attack is then running on the defender's budget, which is usually a lot less than the attacker's. Moreover, it's much less discreet: after a few billions of failed attempts, the defender may catch up that something's running afoul.

Thus, it would be wrong to equate "128-bit symmetric key security" with "128-bit authentication tag security". They don't really live in the same world.


Can high-entropy data be reconstructed from plaintext XORs in CTR nonce reuse?

A block cipher in CTR mode is just a stream cipher.  You have a stream of bits that are indistinguishable from random (assuming good things about the block cipher) and you xor that stream with your plaintext.

What happens when you reuse the stream?  It allows an attack to take their knowledge of one plaintext and use that knowledge to expose information about the other plaintext.  If you encrypt all-zeros as the plaintext (or any message entirely known by the attacker) then the attacker knows the stream and can perfectly decrypt the second message, no matter what that message is.  If, for the re-used portion of the stream, you encrypt two different perfectly random and secret bitstrings then the attacker will learn the relation between the bitstrings, $M_1 \oplus M_2$ but nothing more.


Shor algorithm and schnorr signature in ed25519

Shor's algorithm can compute discrete logs in elliptic curves and thereby recover the secret scalar from a public Ed25519 key, which you can use to forge signatures of your choice.

So, yes, it affects Ed25519—it completely breaks Ed25519, or it would if you could engineer a quantum computer capable of executing it.

It can also compute discrete logs in finite fields, which you can use to forge traditional finite-field Schnorr signatures.


Why did replicated secret sharing use correlated randomness?

The multiplication is indeed correct without adding the randomness, but it is no longer private (i.e., it leaks information). By adding the correlated randomness, it ensures that what any single party sees during the computation is just uniformly distributed and reveals nothing.


Are there any authenticated stream ciphers that use the same PRF for MAC and cipher?

The Duplex constructions of Keccak (now standardized as SHA-3) work this way.

See:
http://sponge.noekeon.org/SpongeDuplex.pdf

And

http://keccak.noekeon.org/KeccakDIAC2012.pdf

I believe some variant of this is in the process of standardization by NIST, but I haven't seen a draft yet. See:

http://csrc.nist.gov/groups/ST/hash/sha-3/Aug2014/documents/sonmez-turan_sha3_2014_workshop.pdf


Private Set Intersection

How about a private set intersection protocol?

The banks input is a set of all of their account numbers, the user's input is their account number (a single member set). The output could be given to the user, or the bank, or both, depending on your needs.

You would need a way to protect against guessing account numbers. For example, I could just keep submitting account numbers to one of the banks until I find a valid account at that bank. Or, the bank could put tons, and tons of accounts in their set that they don't actually own with the hopes that your account number will be in there and they can figure out your account.

Both would be fairly easy to protect against if the account numbers are fairly large (say 256 bits) and randomly generated. The probability of success would be greatly limited. You could further limit the bank from submitting overly large sets as I think the size of the set is probably not kept hidden.

Another possibility

Another possibility would be to develop a multiparty set intersection protocol using multiparty computation. Use the paper I linked to as a basis (it only supports 2 parties). That way all parties participate in the protocol at the same time. An MPC framework such as VIFF will be helpful.

The idea is that all banks would input their account databases, the user would input their account number, and you find which set contains the account number and return to the user the ID of that bank. If 2 banks are found to have that account, someone likely falsifying accounts and return $\bot$.


Is it necessary to use Fermat's Little Theorem to prove the 'correctness' of the RSA Encryption method?

The proposition following «show that» in the question's first paragraph requires $p\ne q$ to become true. Problems are that when $p=q$, the expression $\phi(n)=(p-1)(q-1)$ no longer holds, and even fixing it to $\phi(n)=(p-1)\,p$ does not make the proposition true for quite all $M$ and $e$, when $p\ne2$. For example the proposition fails for $p=q=M=3$, $n=9$, $e=d=5$, for both the correct $\phi(n)=6$ and the incorrect $\phi(n)=4$.

This proof of that propostion does without the full Chinese Remainder Theorem. Rather, following a suggestion in comment, it uses the more basic fact that if $p$ and $q$ both divide $Z$ and are coprime (including: are distinct primes), then $p\,q$ divides $Z$.
In a nutshell, this is applied to the quantity $Z\underset{\text{def}}=(M^e)^d-M$, leading to the desired conclusion. To show that $p$ divide that $Z$, we distinguish the easy case $M\equiv0\pmod p$, from the other where that follows from $e\,d \equiv 1 \pmod{\phi(n)}$ rewritten as $\exists k,\ e\,d=k\,(p-1)(q-1)+1$, and Fermat's Little Theorem. We could further integrate one of the proofs of the FLT in the demonstration.

In conclusion, we can rigorously prove that RSA works without explicitly using either the FLT or CRT, by using or proving slightly less general statements along the way. I see no reason to thus circumvent the use of FLT, because it is so useful. For CRT, that makes sense.
From a pedagogical perspective, if the audience can't stand the FLT, it's not ready for a proof anyway, and we can as well proceed by affirmation and example. At least, let's try to affirm only true propositions.

A former version of the question used slightly incorrect notation. It is best as it stands now, with $(M^e)^d \equiv M \pmod{n}$ and $e\,d \equiv 1 \pmod{\phi(n)}$. The opening parenthesis immediately on the left of $\bmod$ is to denote modular equivalence, rather than an operator with restriction of the output range to non-negative integers less than the modulus. That notation is obtained with \pmod in $\LaTeX$. Alternatively, we could write $(M^e)^d\bmod{n}=M$ if we add $0\le M<n$. And we could write $d = e^{-1}\bmod{\phi(n)}$.


Coordinates of points on the curves in SIDH are in a finite field $\mathbf F_{p^2}$.

First, $\mathbf F_p$ are integers mod $p$. Some polynomials on this field does not have roots, and what we can do about it is extend the field so it has a root. The same way $X^2 + 1$ does not have a root in real numbers, so we introduce $i$.

On this case, let's say we have an irreducible (it has no roots) polynomial of degree $2$ in $\mathbf F_p$, so we introduce a root $w$ and that's how we can create $\mathbf F_{p^2}$. Then, any element $z$ in this new field can be written $z = a + bw$ for $a$ and $b$ in $\mathbf F_p$.

Again, think of the complex numbers: anyone of them can be written $a + bi$ for $a$ and $b$ two real numbers.


How are public keys securely and reliably obtained across the internet?

In a public-key infrastructure, there are two ways a public key can be trusted: either because it's signed by a certificate authority that you trust, or because you already have it in a list of trusted public keys. That's where the chain of signatures ends: in a list of pre-trusted public keys.

These pre-trusted public keys are usually called “root CAs” or “trust store”. They come with the operating system, with the application, or in a configuration.

Sometimes the OS/application/configuration might have its own special-purpose set of root CAs which are obtained via a different PKI provided by the operating system where the OS/application/configuration is installed. This might not be the same system where the application that relies on the PKI will run. For example, if you download firmware for an embedded device on your PC, then the PKI that your browser uses guarantees the authenticity of the firmware image. You trust the root CAs for PKI on the embedded device because they came as part of that firmware image that you trust.

But ultimately, it comes down to a public key that you trust, not because it has a digital signature made by a certificate authority, but because you obtained it from someone you trust by means that you trust. Usually it's the same entity that also provides the code that performs signature verification, and you have to trust that anyway: if the code to verify signatures might accept invalid signatures then it doesn't matter who didn't actually make these signatures. And often it's the same entity that also provides the hardware, and again if the hardware isn't executing the signature verification correctly then it doesn't matter whether the code and data are good.

For example, if you buy a computer with an operating system preinstalled that includes a web browser with HTTPS support, the reason you trust it to verify keys has nothing to do with cryptography. Cryptography is how that browser verifies the authenticity of connections, not why you trust it to do so.

That's in fact a general thing with cryptography: cryptography doesn't actually create security properties from scratch. Cryptography is a mathematical means to extend security properties to cover more ground. For example, encryption alone can't make data confidential: all encryption does is to extend the confidentiality of the key into the confidentiality of the data. A digital signature extends the confidentiality of the private key into the authenticity of the data. Likewise, a hash doesn't guarantee the integrity of data of its own, but extends the integrity of the hash into the integrity of the data. At the root, there has to be some non-cryptographic means of securing the key or hash.

I didn't find a duplicate question on this site, but this has been covered several times on Security Stack Exchange, in particular:

SSL Certificate framework 101: How does the browser actually verify the validity of a given server certificate?
How can we trust PKI, for example, Verisign?
How are public key certificates updated securely?
Where does the list of trusted content authorities come from when using a web browser?
How are Chrome and Firefox validating SSL Certificates?
SSL certificate chain verification


Encryption algorithms that require more work to decrypt versus encrypt?

Since the encryption key is public knowledge, one simple method is to encrypt using a standard symmetric algorithm (such as AES), but randomize a portion of the encryption key.
For example, if you use AES-256, and the encryption key is published, but each individual encrypted file has 12 bits of the key overwritten with a random value (which is never saved or stored anywhere), so decrypting the file will require the decrypting device to brute-force the final 12 bits of the key.
The number of bits randomized, can be adjusted based on how quickly people are able to crack it, to hit whatever sweet-spot of required work you are looking for.
IMPORTANT:
It should be noted, as A. Hersean pointed out in the comments, that this method may have significant negative side effects:

... proof-of-work is a bad idea: motivated people will have enough work power, while normal users will be negatively impacted. It will most likely not solve your problem and just make your system use so much power that nobody would want to use it.


How does Blowfish avoid successful cryptanalysis?

The same way other ciphers, basically, only it does it better than some. From the Blowfish paper these were the relevant building blocks "demonstrated to produce strong ciphers" in previous designs:

"Large S-boxes. Larger S-boxes are more resistant to differential cryptanalysis."
"Key-dependent S-boxes. While fixed S-boxes must be designed to be resistant to differential and linear cryptanalysis, key-dependent S-boxes are much more resistant to these attacks."
"Combining operations from different algebraic groups." (Blowfish uses XOR and  addition modulo $2^{32}$.)
"Key-dependent permutations. The fixed initial and final permutations of DES have been long regarded as cryptographically worthless."

The basic structure is a Feistel network, which has also been shown to produce secure ciphers provided the round function is good.

Of course, it's not a perfect cipher. For one, its 64-bit block size puts some restrictions on how we can use it securely. Its key setup is rather slow. There's also a class of weak keys for up to 14/16 rounds, which is quite close even if it allows no attacks. Schneier himself has been quoted as recommending people move to e.g. Twofish instead.


When do we need composite order groups for bilinear maps and when prime order?

A composite order group is like having a 2-dimensional vector space, because of the Chinese Remainder Theorem. More concretely in the context of a bilinear map, if $g$ is a generator with order $N=pq$, then $g_p = g^q$ generates an order-$p$ subgroup, and $g_q = g^p$ generates an order-$q$, and $e(g_p, g_q) = 1$. They cancel each other out, and so you can think of $\{g_q, g_p\}$ as an orthogonal basis for the a 2-dimensional vector space.

The way this is typically used is that the bilinear "functionality" of a scheme is carried out in one dimension (e.g., in the exponent of $g_p$) while the other dimension (e.g., the exponent of $g_q$) is used for "blinding". Orthogonality ensures that the blinding factors just disappear after the bilinear map.

Recently, Okamoto & Takashima have developed a framework for cryptographic constructions using prime-order bilinear groups (called dual-pairing vector spaces, DPVS). It is a nice abstraction that allows you to build (from prime-order groups) $n$-dimensional orthogonal vector spaces that have a suitable pairing. It's like having the above effect, but now even with of a product of $n$ primes! I think most people in the field believe that prime-order constructions can be "ported" to prime-order groups, using these DPVS techniques.


It depends completely on the algorithm if it would matter that the result would be divisible. If it was a cryptographic error I don't think it would have a specific name. Possibly a side effect or unexpected property.


How is key length of feistel cipher calculated?

You have some confusion here: The formula N * (2 ** N) for key size is for ideal block ciphers that select one of (2 ** N)! permutations. Shortly after that formula, your book starts to go into the Feistel construction (emphasis is mine):

The Feistel Cipher
Feistel proposed [FEIS73] that we can approximate the ideal block cipher by utilizing
the concept of a product cipher, which is the execution of two or more simple ciphers
in sequence in such a way that the final result or product is cryptographically stronger
than any of the component ciphers. The essence of the approach is to develop a block
cipher with a key length of k bits and a block length of n bits, allowing a total of 2 ^ K possible transformations, rather than the 2 ^ N! transformations available with the ideal
block cipher

So the idea is to compromise on the huge key length and sacrifice the ability of picking one of all possible permutations, to utilize a smaller key that can select one of enough possible permutations. A cipher will typically use a key length that is equal to it's target block size, to simplify the key addition layer.


Minkowski's theorem in lattice-based cryptography

Try to draw a "hypercube" in $\mathbb{R}^2$ (i.e. a square) and in $\mathbb{R}^3$ (i.e. a regular cube), both centered at the origin and having side length equal to $\frac{2r}{\sqrt n}$...

Since they are centered at the origin, each side goes from $-\frac{r}{\sqrt n}$ to $\frac{r}{\sqrt n}$ (in its axis).

Now, the farthest points from the origin that belong to the hypercube are exactly the points of the corners and all the corners are at same distance from the origin. Since a sphere is symmetric, if one corner belongs to a sphere, all the corners belong to the sphere and, consequently, the whole hypercube is contained in the sphere.

The distance between the origin and the corner $c := \left(\frac{r}{\sqrt n }, \frac{r}{\sqrt n }, \cdots, \frac{r}{\sqrt n}\right) \in \mathbb{R}^n$ is given by

$$||c|| = \sqrt{\left(\frac{r}{\sqrt n}\right)^2 + \cdots + \left(\frac{r}{\sqrt n}\right)^2} = \sqrt{n \cdot \left(\frac{r}{\sqrt n}\right)^2} = r$$

Now, notice, by definition, the hypersphere $B(0, r)$ contains all points within distance $r$ to the origin, therefore, it contains the corners and then, the entire $n$-dimensional hypercube.

Since this hypercube is contained in $B(0, r)$, its volume cannot be greater than the volume of $B(0, r)$, and we know that the volume of a hypercube is the product of its sides' length, in this case,  $\prod_{i=1}^n \frac{2r}{\sqrt n} = \left( \frac{2r}{\sqrt n} \right) ^n$.

So, finally, $Vol(B(0, r)) \ge  \left( \frac{2r}{\sqrt n} \right)^n$.

To the corollary 2, you just have to use $r = \lambda_1$ in the above formula. Then, we get

$$\left( \frac{2\lambda_1}{\sqrt n} \right)^n \le Vol(B(0, \lambda_1))$$

and since $B(0, \lambda_1)$ has no nonzero lattice point (by the definition of $\lambda_1$), its volume can't be greater than $2^n \det(\Lambda)$ (by the contrapositive of theorem 9), then we get

$$Vol(B(0, \lambda_1)) \le  2^n \det(\Lambda)$$

  In this section we will talk about why the cube's side length is of $\frac{2r}{\sqrt{n}}$ in n-dimension

We first explain the 3-dimensional case and later extend things to n-dimensions.
Let us take the cube of side length $a$ inscribed in a ball of radius $r$ as shown below:

Now, the length of main diagonal of cube is $\sqrt{3}a$.
The length of the main diagonal of cube is the diameter of the Ball of radius r
$\Rightarrow \sqrt{3}a=2r$.
So, $a=\frac{2r}{\sqrt{3}}$ which is of the form $\frac{2r}{\sqrt{n}}$ for $n=3$

So, the result holds for $n=3$. Now, for the n-dimensional case see this question on Math.SE.

From the above post:

The length of the main diagonal of a cube is $\sqrt{n}a$ where $a$ is the length of each side of the cube.
Again, the length of main diagonal of cube is the diameter of the ball of radius $r$
$\Rightarrow \sqrt{n}a= 2r$
so, $a=\frac{2r}{\sqrt{n}}$  which is the value given by theorem.


The OMAC version used by EAX is OMAC1, which is equivalnent to CMAC. The zero you're talking about is probably the zero in $\operatorname{OMAC}^0_k$. This does however not distinguish different algorithms but it displays the tweak value. The tweak itself is simply prepended to the message before OMAC1 is applied.

This is explained in figure 1:

  Algorithm $\operatorname{OMAC}^t_K(M)$
  (50) return $\operatorname{OMAC}_K([t]_n | M)$

so t is encoded in $n$ bits before being put in the OMAC function.