Does collision resistance stay when extending a hash function to a set domain?

If the hash outputs 160-bit integers, and the product operation is integer multiplication, then this is probably not secure, for reasons fgrieu outlines.  For instance, about $1/2^{19}$ of all 160-bit integers are $B$-smooth, if we take $B$ to be the $2^{20}$th prime.  Consequently, after hashing $2^{45}$ different candidate messages, we expect to find about $2^{26}$ smooth hash digests, which I suspect is enough to find a collision; and this computation seems likely to be feasible today.

On the other hand, if you work in a multiplicative group where the discrete log problem is hard, such as $\mathbb{Z}_p^*$, and if the hash function outputs random elements of this multiplicative group, then your scheme is secure.  For instance, if you pick a 2048-bit prime $p$, arrange for your hash function to output numbers that are uniformly distributed between $1$ and $p-1$, and interpret the product as "multiplication modulo $p$", then your scheme should be secure.  However, it might be a bit slow.  See the following papers for technical details and security analysis:

Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking.  Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh.  Asiacrypt 2003.  See the scheme they call MSet-Mu-Hash.
A new paradigm for collision-free hashing: Incrementality at reduced cost. Mihir Bellare, Daniele Micciancio.  Eurocrypt 1997.  See the scheme they call MuHash.


Typically, the notation || means concatenation, which is to say Hello||World is equivalent to HelloWorld.

Is that equivalent to Hash(Hello) +  Hash(World) or Hash(HelloWorld)?

So Hash(Hello||World) is equivalent to Hash(HelloWorld).

Is there any difference between Hash(Hello||World) and Hash(Hello,World)?

This depends entirely on what Hello,World is defined to mean.

Notation does not have absolutely defined meaning - what a symbol means in one context can be different from what that symbol means in another context.

The only way to know for sure is to check the definitions of the notation from wherever you found this.

If there are no such definitions, then it is safe to assume the most common/obvious meaning for the notation. However, if the notation is non-standard, then there may not be a common and obvious meaning for it.


Key Size for Symmetric Homomorphic Encryption Over the Integers

The paper says that the parameters are $r ≈ 2^{\sqrt \eta}$ and $q ≈ 2^{\eta^3}$. Note that these values are expressed as functions of $\eta$,  not $N$.

With regard to the parameters, it is common practice to describe them using the asymptotic notation. $\omega(\cdot), \Theta(\cdot)$ and $\tilde O(\cdot)$ are instances of this notation. $\omega(g(n))$ denotes a function that dominates $g(n)$ asymptotically; that is, $f(n) = \omega(g(n))$ means that $f(n)$ is asymptotically greater than $g(n)$. For example, a linear function (e.g., $f(n) = n$) dominates a logarithmic function (e.g., $g(n) = \log n$), since, asymptotically, it grows much faster; thus, $n = \omega (\log n)$. $\Theta(g(n))$ denotes a function that, also asymptotically, can be "sandwiched" between $k_0 \cdot g(n)$ and $k_1 \cdot g(n)$, for some real values $k_0, k_1 > 0$. Finally, $\tilde O(n)$ is like the traditional Big-O notation but ignoring any logarithmic factors.

Therefore, these parameters are actually functions of the parameter $\lambda$, since they vary when $\lambda$ varies, although they are not expressed as functions. The expressions given are only a way of specifying how to choose them according to $\lambda$.

Also note that these expressions are somewhat "abusing the notation", since these asymptotic "functions" are actually sets of functions. Therefore, when you see something like $\rho = \omega(\log \lambda)$, it actually means $\rho(\lambda) \in \omega(\log \lambda)$. Anyway, this is a fairly common convention that simplifies the reading.

Knowing this, you can deduce your own example values for the parameters. For example:

$$\rho = \omega(\log \lambda) \to \rho =  \lambda$$
$$\eta \geq \rho \cdot \Theta(\lambda\log^2 \lambda) \to \eta = \lambda \cdot (\lambda\log^2 \lambda) = \lambda^2\log^2 \lambda $$
$$\gamma = \omega(\eta^2\log \lambda) \to \gamma = \eta^2\lambda = (\lambda^2\log^2 \lambda)^2\lambda = \lambda^5\log^4 \lambda$$
$$\tau \geq \gamma + \omega(\log \lambda) \to \tau = \gamma + \lambda = \lambda^5\log^4 \lambda +\lambda $$
$$\rho' = \rho + \omega(\log \lambda) \to \rho' = \rho + \lambda = 2\lambda$$

As you can see, this gives a result that is consistent with the part that says:

  A convenient parameter set to keep in mind is $ρ = λ$, $ρ′ = 2λ$, $η = \tilde O(λ^2)$, $γ = \tilde O(λ^5)$ and $τ = γ + λ$. (This setting results in a scheme
  with complexity $\tilde O(λ^{10})$.)

When it says that the scheme has complexity $O(\lambda^{10})$, I guess it means the time complexity.


How can two UProve token holders prove to a 3rd party that they aren't the same user?

The U-Prove Technology Overview V1.1 shows that this can be done. The issuer knows who the individual is but can't correlate that with verifier or prover use.

Upon setup the issuer can have extra attributes available that upon request of authorization from the prover the verifier can have access to. The verifier could use such an attribute and only successfully verify if it hasn't seen that attribute before.


Why does TLS 1.2 use GCM with additional SHA hash?

Those ciphersuites do use GCM for both encryption and authentication. The hash function mentioned at the end is not used for integrity, but in the pseudorandom function. The TLS PRF is used to derive valid keys for the ciphersuite from the shared secret generated in the key exchange.


Choice of authenticated encryption mode for whole messages

GCM

Personally, I would go for GCM (Galois Counter Mode) since it is efficient – meaning: it handles pretty much everything you’ld expect from it, while other modes sometimes tend to lack a specific feature here and there (see image below for a comparison that shows what I’m hinting at). Also, GCM has a pretty good performance (assuming non-flawed implementation). As you most probably already know, it provides Galois mode of authentication with the well-known CTR mode encryption. The CTR aspect practically means that it doesn’t need any padding (which avoids related attack potential) and it means that you keep a bit of flexibility when it comes to message/package lengths (something CCM for example doesn’t offer, since it uses a fixed block length). Also, the Galois field multiplication used for authentication can be computed in parallel, which enables higher speed/throughput than those authentication algorithms that use chaining modes (like CBC etc). Btw: in case you decide to check on GCM, you might find it handy to know that NIST Special Publication 800-38D includes recommendations for IV selection etc.

The rest…

An alternative at the top of my list would have been EAX mode, which also provides several desirable attributes. But: EAX is a “two-pass scheme”… making it slower than well designed one-pass schemes that are based on the same primitives. Since your designing a messaging/storage protocol, you probably will want to get your hands on all the speed you can get. Two-pass seems not to be an option in that case, pushing EAX down on the list.

Now, you also mentioned CCM. That mode is only defined for block ciphers with a block length of 128 bits, which might be a bit restrictive in size for messaging et al. Which is why I would like to remind you of GCM’s counter mode again…

Last on the list of things you’ve mentioned is OCB. I’m a bit uncomfortable when thinking about OCB, because Ferguson found collision attacks on OCB. The attack limits the data that can safely be encrypted with OCB to around and about 64GB per key.  That’s about the same 64 GB limit that GCM has (GCM limits plaintext size to $2^{39} − 256$ bits for any given key and IV combination), but we have to remember that GCM’s limit is “by design”… in the case of OCB, it’s “the result of a collision attack”. From a security perspective, I would therefore tend to avoid OCB. We all know attacks can only get better.

There are a few other things that might or might not make a bit of sense, depending on the individual setting… but in the end, I personally would advise to use GCM for a messaging and storage protocol.

Comparing some of the options…

To compare, you might also want to check out the nice comparison table on slide 7 of this PPT file by David Wagner. I’ll quote it as a graphic here for reading convenience (as you’ll notice GCM is a winner):

EDIT

Sometimes, my brain seems to be a bit slow when it comes to remembering papers I’ve once been reading.

Anyway, I’m pretty confident you’ll enjoy reading “Basic comparison of Modes for Authenticated-Encryption (IAPM, XCBC, OCB, CCM, EAX, CWC, GCM, PCFB, CS)” (PDF) which compares a truckload of modes in terms of attributes, speed, implementation, memory usage, tables showing things like the number of the underlying block cipher invocations for each mode, etc.

After reading that, you’ll have ample info at hand to decide for yourself what makes most sense.


Supplying ECDSA with deterministic input doesn't make for a one-time signature—RFC 6979 chooses the per-signature secret as a deterministic but secret function of the message.  However, there is a variant of ECDSA—or EdDSA—that could probably work.

In ECDSA, a public key is a point $A$ on a curve with standard base point $G$, and a signature on a message $m$ is a pair of integers $(r, s)$ such that $$r = f\bigl(x([H(m) s^{-1}] G + [r s^{-1}] A)\bigr),$$ where $f$ maps a coordinate to a scalar.  For any particular $r$, there are only approximately two $s$ values that work—$s \equiv \pm [H(m) k^{-1} + r k^{-1} a] \pmod n$, where $k$ is the per-signature secret, $a$ is the secret scalar such that $A = [a]G$, and $n$ is the order of the group.  (There may be a few other $s$ values because of the weird $f$, but there aren't many.)

Instead of choosing $r$ at signing time, you could choose $r$ at key generation time: then a public key is a pair $(A, r)$ and a signature is an integer $s$ satisfying the same equation.  Then publishing two different signatures, that is two different $s$ values for a single $r$ value and therefore for a single per-signature secret $k$, would leak the private key to anyone who can solve a trivial linear equation.
Similarly, in EdDSA, a signature is a pair $(R, s)$ of a point $R$ on the curve and an integer $s$ such that $$[8 s]G = [8]R + [8 H(R, A, m)] A.$$  Again, you could make $R$ part of the public key $(A, R)$, leaving only $s$ in the signature.

This doesn't really enable any simplifications—where previously you could have (say) 32-byte public keys and 64-byte signatures, now you have 64-byte public-keys and 32-byte signatures, and the cost of signing and verifying is exactly the same.  But it does guarantee one-time signatures on threat of leaking the private key.


Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem

If one knows $\gamma_1,\cdots,\gamma_n$ and $g(x)$ then for any $n$-long binary vector $V$ one can form the polynomial
$$v(x):=\prod_{i:V\cdot e_i} (x-\gamma_i)$$
and the syndrome polynomial $s(x)=v'(x)/v(x)\pmod{g(x)}$. This is all the information required by Paterson's decoding algorithm, independent of the basis used for the generator matrix and/or parity check matrix.
Section 3.1 should be read as an argument of the importance of keeping $M$ and $P$ secret as they are essentially the private key. It should be a very unreasonable assumption that the attacker can obtain these as this would break the system.
The recovery of $g(x)$ starts off as pretty much as you describe. For $V$ any codeword, compute the corresponding $v'(x)$ which we know is a multiple of $g(x)$. If we do this for two codewords, we can take the GCD which must also be a multiple of $g(x)$. After a handful of GCDs we have almost certainly recovered $g(x)$.
Note that that there is a equivalence between Goppa codes where columns are relabelled according to a linear function and $g(x)$ undergoes the corresponding linear change of variable. Recovering the columns labels of any equivalent code would also allow decoding.


Sane implementations of Bitcoin cryptography routines w.r.t. side-channel attacks

Is there a "sane" implementation of the algorithms used by bitcoin? e.g. are there high-quality implementations available that incorporate defenses against side channel attacks?

libsecp256k1

  Does OpenSSL already protects against side-channel attacks?

haha*

  How can I train myself to evaluate whether an existing implementation is vulnerable to certain types of attacks?

Review the claims.  If it doesn't even claim side channel resistance, worry.
Review the track record.  If it's been subjected to side channel attacks repeatedly and it doesn't claim to have taken a serious comprehensive approach to fixing them, worry.
Identify the physical observables of interest.  If you're talking over the internet, you probably don't need to worry about power analysis.  But if you're making a smart card that a hapless luser will put into a malicious ATM, you may need to worry about it.
For timing side channels:

Identify a set of primitive computations that you take as constant-time.  Typical set: copying data, $w$-bit addition and subtraction, bitwise operations, constant shifts and rotates.  Multiplication can be questionable.
Follow the data flow of secrets.  If you can find any primitive computations that depend on the values of secrets, like the conditions of branches or the addresses of memory references, *bzzzzzrt*.  If you can prove they flow only into the safe operations, you might be OK.

Try not to handle individual bits at a time, and keep up with the state of the art because technology moves fast.
Pay attention to tools like gfverif.

  Are there good resources that explain how to implement those algorithms myself? I do not intend to use my own implementation for the app, but I am interested in understanding how the stuff works I'm using. Entry-bar seems quite high. Can the "Guide to Elliptic Curve Cryptography" book be recommended?

Our friendly neighborhood bear has some good references.  Reading existing implementations is indispensible, and the abysmal code quality of a lot of otherwise good cryptographers can provide good motivation to get into implementation yourself.  For references on elliptic curve cryptography, we have lots on this site!

* In fairness to the modern OpenSSL team, they inherited a gigantic legacy code base and they are doing their best to clean it up and plug side channels without severely damaging performance.  Unfortunately, these goals—maintain legacy code base, preserve performance of bad cryptosystems—often come into conflict with side channel security.


I think what you're missing here is that a cryptographic hash by itself is not actually sufficient to verify the integrity of a message.  Consider this:

I want to send a message over the Internet (on an insecure connection, e.g. UDP), but have it be protected from tampering.  I take the message and attach at the end a cryptographic hash of the message (e.g. SHA256(message)).  When my friend receives the message, she verifies that the hash at the end matches SHA256(message).

Now, despite the fact that she has "verified" the message using a cryptographic hash, it turns out that this is not sufficient to prevent tampering.  If an attacker is able to intercept and modify the message before it reaches my friend, they can remove the old hash, SHA256(message), and add a new hash, SHA256(tamperedMessage).  When my friend receives the tampered message, she won't notice anything is wrong, because the message she receives still ends with a matching SHA256 hash.

Hashes do not (by themselves) provide integrity protection (in other words, prevent tampering).  Hashes provide a convenient way of identifying the content of a message.

We can use hashes to build schemes that do provide integrity protection.  Consider the earlier example.  Let's say I again transmit a message to my friend over the Internet, this time without a hash.  She receives the message, but knows that she can not yet trust that it has not been tampered with.  If I meet up with her in person, I can provide her with the hash, say, diligently scrawled on a sheet of paper.  If she checks this hash against the message she received over the Internet, she will know that it has not been tampered with.  Why?  Because (1) the hash uniquely identifies the original, legitimate message and (2) the hash was provided over a secure channel (i.e. in person).

This is why having a hash that "verifies itself" does not prevent tampering.  You could attach to a hash, a hash of that hash, then attach to that hash, a hash of that hash, but your scheme would still not provide any integrity protection unless the hashes are provided over a secure channel.  Hashes identify, and further identifying the identifier does not actually improve security.

Note (in anticipation of nitpicks): I used the term "uniquely identifies".  Hashes aren't actually unique from a theoretical perspective, but they are in practice.


AES-CBC with zero IV and a unique first block

If the IV is all zeroes, then you basically have ECB for the first block.  Basically you're proposing to use this first block's encryption as the IV for the second block.  You're implying that the first block will always be unique, but low entropy, which sounds like a counter or time stamp.  There are attacks when the IV is predictable, and while this is a step away from that, it may still be useful information for an attacker.


Can A PRNG Be Used To Generate Multiple Private Keys for ECDSA?

The most important property of cryptographic PRNGs is that it's indistinguishable from true random numbers, unless you know the seed, or you have huge computational resources. Two important consequences of this requirement are:

You can't find the seed from observing the output
You can't predict more outputs from observing some of them.

An attacker who can do either of those, either has broken the cryptography used in the PRNG, or he has computational resources exceeding the security level of the PRNG. For typical security levels of at least 128 bits, nobody on earth has the required resources.


The opponent possesses a string of ciphertext and has access to the encryption machinery as black box. What is the name of this attack?

Actually, this specific attack against RSA is known as a 'cycling attack'; it works because RSA defines a permutation, and so by doing repeated encryptions a sufficient number of times, you'll always get back to where to started with eventually.

However, people have analyzed this attack, and shown that (with extremely high probability) the amount of work required by this attack (for a randomly chosen RSA modulus) takes more work than the known factorization methods.


Yes, if (and this is important) the keys for $E$ and $S$ are selected independently.

Consider that we had two encryption methods $E$, $S$ for which their composition $E(S(x))$ is not CPA secure; that is, we have some distinguisher $D$ that had some advantage in distinguishing that from a random function.  Then, we can build a distinguisher for $E$ (by selecting a random key for $S$, then then use the distinguisher $D$, and when it made a query, we'd take the plaintext it selected, encrypt it with $S$ with our random key, and then gave that ciphertext to the object we're distinguishing (either $E$ or the random function).

Similar logic can be used to show that we can use the distinguisher to distinguish the inner function (by selecting a random key for the outer function).

Hence, if $E$ and $S$ are indistinguishable, so is their composition (in the CPA model).  In fact, we can make a stronger statement; if either are indistinguishable, so is the composition.

On the other hand, if the keys aren't independent, then all bets are off.  Not only do these simulation arguments don't work (as the simulator is unable to select the appropriate key), but the possible insecurity of the system can be seen by considering the case where $E$ and $S$ are inverses of each other.


How to prove that a rainbow table is complete?

Rainbow tables are not complete. But some have good coverage. We estimate how many distinct hashes are covered by a rainbow tables using statistical tools.

We can build perfect rainbow tables where we throw out colliding chains. This reduces redundancy in the final table. But even in a "perfect" rainbow a certain hash can appear twice(but not in the same column) so we still need to estimate the coverage.

As we approach full coverage it becomes more and more expensive. Because with a table with high coverage nearly anything we add would already be covered.


Why a Blockchain cannot confirm "Membership Proof" as can a Merkle Tree?

Nevermind, I just realised that the statement says

  a concise proof of membership

Indicating that the Blockchain has indeed proof of membership, just one not as efficient.


How much would this AES modification improve security?

It would not improve security at all.

For AES-CTR mode, encryption and decryption use the same algorithm: generate the key stream using the counter and then XOR the plaintext with it. Because of that, step 1 and 3 would completely cancel each other out, and you would be left with the "decryption" in step 2.

If you'd just use the first two steps then you would actually two independent keystreams. However, as they both rely on the AES algorithm then if the algorithm is broken, your scheme may still be broken as well. This is why usually that kind of construction is created with two algorithms that are rather distinct from each other.

You keep trying to "improve" a cryptographic primitive that is already considered secure. Why not try to improve one of the many problematic schemes? Preferably you would try and first understand the scheme before trying to improve it, like you tried to do for AES-CTR.


Yes, you could use the HKDF-expand function to expand the bits of the key to a certain size and then use HKDF-extract to derive a key from it again. Note that the resulting key is not identical to the key you've started with. You can use the HKDF-expand again to derive one or more multiple keys with any size from the extracted key material.

HKDF internally uses a hash function (it's a Hash based Key Derivation Function). So it should be fine as long you use SHA-256 or above for 256 bit of input material. The entropy in the output material should be (close to) 256 bits.

Just like a normal hash, you would need all the input data to calculate the correct output, so if only part of the enlarged key gets known you might be still secure, as long as the amount of unknown material is large enough (so brute force attacks are unlikely to succeed).

You can leave the other arguments to HKDF-extract / expand empty if you don't know what to do with them. Using an empty salt seems fine for this kind of purpose.


Attacking AES-128 with Grover's algorithm

Grover's algorithm is a brute-force quantum algorithm with complexity $\mathcal{O}(\sqrt{N})$ with asymptotically optimal on unstructured data. There is also "Quantum Computing and Hidden Variables" in  $\mathcal{O}(\sqrt[3]{N})$ by Aaronson.

Ensuring uniqueness of the solution

Requires ECB mode;

Let $n$ denotes the block size.

Let $r$ be the number of different plaintext-ciphertext pairs.

Let $r$ denotes the number of the simultaneous plaintext-ciphertext pairs  encrypted under two secret keys $k_1 \neq k_2$.

Then the expected result of having a different result if the $r$ plaintext are different;

$$ 1- \frac{1}{2^{rn}}$$

A good estimate on $r$ is given as;

$$r > \lceil 2^k/n \rceil$$

For AES-128

$n=128, k=128 \Rightarrow r=3$

For AES-192

$n=128, k=192 \Rightarrow r=4$

For AES-256

$n=128, k=256 \Rightarrow r=5$

for more details, see "Applying Grover’s algorithm to AES:
quantum resource estimates"  at #3.1


Unconditionally secure block cipher for a finite number of blocks

The PEANUT and WALNUT ciphers are an example of this (see also Vaudenay's decorrelation theory for the theory behind these ciphers). The idea is simple: take a provably secure construction, like the Luby-Rackoff scheme, and instantiate it with random functions that are identical to random up to $h$ invocations.
For example, if your block cipher works on $n=128$-bit blocks, it is easy to come up with a $64$-bit random function that is indistinguishable from random up to $h$ evaluations: a random polynomial of degree $h-1$ over $\mathbb{F}_{2^{64}}$. It takes $hn/2$ bits to represent such a polynomial. You cannot do better than this and remain information-theoretically secure.
Since with Luby-Rackoff you need $4$ rounds with an independent random function each, you need $4$ random polynomials as above to obtain a cipher that has an unconditional attack advantage bound
$$
\mathbf{Adv}^{\mathrm{sprp}}_E(q) \le \frac{q^2}{2^{64}} + \frac{q^2}{2^{128}}\,,
$$
provided the number of queries $q$ stays under the maximum $h$. Security completely breaks down after $h+1$ queries.
With some extra complications you can reduce this to a single random degree-$4h$ polynomial and $4$ Luby-Rackoff rounds.


Is there any such thing as "proof of location"?

A clear cut answer to your question is NO for now. In the literature there is no an accurate and reliable scheme that can determine geolocation of the data. They are basically timing-based schemes and the problem with timing (in this case) is that many factors can affect it. Also they usually assume that there are some reliable landmarks around the world that can help determining data location.

I think some internet infrastructures are needed to be improved to support such capability. See below for some paper in this area.

However, securing outsourced data might be a solution in hand rather than finding its location (I entourage you to think/read about why data location may matter).

1-GeoProof: Proofs of Geographic Location for Cloud
Computing Environment:http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6258199

2-Do You Know Where Your Cloud Files Are? :
http://dl.acm.org/citation.cfm?id=2046677

3-Geolocation of Data in the Cloud:
http://znjp.com/papers/gondree-codaspy13.pdf


Difference between one-level and two-level E0 encryption

I seem to have found the answers myself:

Two-level E0 uses one instance of the cipher with the master key to generate the internal state for a second instance of the cipher which is then used to encrypt a single frame. I found this out from a slide presentation and a paper describing attacks against two-level E0.
Bluetooth 2.1 does still use two-level E0. HMAC-SHA-256 is only used in combination with P-192 key exchange to derive the master key. Attacks against two-level E0 do apply to 2.1, however the best known attacks require more frames encrypted under a single key than is supported by the protocol. This was made clear in a Security SE answer.


Explanation of correlated randomness for garbled circuits

Correlated randomness and garbled circuits are two different approaches to achieve secure multiparty computation. They have nothing to do directly with each other.

Highly multi-party protocols like SPDZ, TinyOT, etc., which are secure against a dishonest majority, are based on correlated randomness. Protocols in this paradigm have two phases.

In the first phase, the parties do a specialized MPC for the following task: it takes no inputs, but samples $(r_1, \ldots, r_n)$ from some agreed-upon distribution, and outputs $r_i$ to party $P_i$. The outputs of this phase are called the correlated randomness. Since this phase doesn't use any specific inputs of the parties, it can be done well beforehand.
In the second phase, the parties consume their correlated randomness to perform MPC of a desired function $f$, on their chosen inputs for $f$. This phase is often information-theoretically secure (assuming the security of the first phase).

The absolute simplest correlated randomness is a multiplication triple (proposed by Beaver in 1991). Let $[s]$ denote a situation where the parties have a secret-sharing of $s$. The details of the secret sharing are not too important -- you can imagine simple additive secret sharing or Shamir secret sharing. The only important property is additive homomorphism: from $[s],[t]$ it is possible to compute $[s+t]$ (cheaply, usually without interaction).

The correlated randomness consists of $[a],[b],[c]$ where $a,b$ are random field elements and $c=ab$. These values are called a multiplication triple. I won't elaborate on the parties generate a multiplication triple, I just want to focus on how random values like this can be used for MPC.
Later suppose the parties have secret shares $[x]$ and $[y]$ and they want to multiply them to learn $xy$. This is a multiplication of chosen inputs. How can they use the multiplication triple, which uses random values that are unrelated to the multiplication they really care about?

Parties compute $[x+a]$ and $[y+b]$ (using additive homomorphic properties of the secret sharing) and publicly open them as $d=x+a$ and $e=y+b$. Since $a$, $b$ are random and unknown to any party, opening $d$ and $e$ reveals nothing about $x,y$ (but this "one-time pad" means that this particular multiplication triple can be used only once in this way).
Note that $xy = (d-a)(e-b) = de - ae - da + ab$. But parties know $e,d$ in the clear and they have secret shares of $a, b,$ and $ab$. So they can use the homomorphic properties of the sharing scheme to compute $de - e[a] - d[b]
+ [c]$ and open it. The result is the $xy$ they care about.

This (and other tricks) are roughly how correlated randomness is used for MPC. For a very good overview of this protocol paradigm, I highly recommend Claudio Orlandi's excellent tutorial video about the topic.


Padding password before SHA-512 hashing to avoid info leak via timing

In general password hashing (algorithms such as bcrypt, PBKDF2) should contain a specific work factor. It might well be that repeating the hash multiple times will already obfuscate the hash time enough to make the padding redundant.

If you consider password hashing a requirement then reducing the number of rounds on the underlying compression function (e.g. the hash) doesn't make much sense as you would reduce the work load for both the regular user and an attacker.

For now assume that your passwords contain lots and lots of entropy so you may skip the issue of the work factor. In that case your scheme might be of some use.

You should however take really good care to avoid memory allocation issues.

Say an attacker could influence memory allocation. In that case asking for e.g. a block of memory of $c - l(p)$ bytes could be problematic (with $c$ being the total length of the input to the hash function and $l(p)$ being the password). In that case an attacker could guess a length $n$, and make sure only $n$ bytes are available within the memory page / cache block / whatever. Now the padding of $p$ would either allocate within the current page or it wouldn't. Page allocation / cache misses take a lot of time, so they can be relatively easily be detected. So the attacker has a method of checking if the password has a certain length.

You could work around this by copying the password into a preallocated block of memory. You then copy the required amount of pre-generated padding bytes after it.

  (Of course, with the padding being a function of the password, one could dispense with the password and simply hash the padding instead. That seems risky, though; entropy might somehow be lost in the process.)

Heh, no, the size of the password is rather less important than the content of the password. Unless you assume the padding to contain the entire password, but in that case you forgot to define your protocol well.

  and adding precompiled libraries is problematic.

So use the source code. I don't get it, is there an invisible man throwing up these invisible walls somewhere?


After 20 years of AES, what are the retrospective changes that should have been made?

Nobody seems to need a 192 bit version, we can do fine with just AES-128 and AES-256. Having a key that's 1.5 times the block size is a nuisance (or 0.75 times the block size if the block size is doubled).
The key schedules of AES-192 and AES-256 are vulnerable to attack; we could do with a better key schedule where even these attacks are avoided. They don't have much influence when the cipher is used for confidentiality, but we could do without those attacks regardless.
And while we're expanding the block size and fixing vulnerabilities to the key schedule anyway, we might as well make it suitable as underlying cipher for a cryptographic hash function and make it a tweakable block cipher.


Difference between UF-CMA and UF-CMVA security

Why if the tag $\varphi$ is unique the two Games are identical?

If your Tag algorithm is deterministic, then verifying a tag-message-pair is actually just re-computing the tag for the message and checking if the provided and the re-computed tags match. So in this case $\operatorname{Vrfy}_k(m,\tau):=\operatorname{Tag}_k(m)\stackrel?=\tau$. So I hope now you see how step 3 is identitical in both games if $\operatorname{Tag}$ is deterministic.

  But I can't understand why they are different?

Because there are MAC algorithms for which $\operatorname{Tag}$ works non-deterministically, that is with large probability two tags for the same message will differ. Now you can no longer check whether a tag-message-pair is valid as above, you need a more complex verification algorithm.

As a contrived example consider the scheme $M$ which is HMAC with the following modification for the tag-generation: First you generate a random 128-bit string and prepend it to the message, then you run the modified message through the HMAC and return the concatenation of the random string and the HMAC-tag. Verification now works by taking the prepended random string and prepending it to the message before feeding it into the HMAC oracle.


Is there a secret sharing scheme which allows delegation/re-sharing without reconstructing the original secret?

Suppose we have a $(k, n)$ threshold scheme meaning that there are $n$ shares of a secret distributed to different parties, and any $k$ shares can be used to re-create the secret.  A new person joins the club and wants to have a share of the secret too.  I contend that the secret must be available to a trusted party who can create the extra share.  Because if someone with little knowledge of the secret (or even as much
knowledge as a cabal of $k-1$ shareholders trying to break the scheme) could
create a new share of the secret, then this someone could repeat the process many times until $k$ shares are available, and thus recover the secret via the standard reconstruction
technique.  Now, it is possible to have a mathematical algorithm or computer program
that will take $k$ (or more shares) and create new shares without the secret being
explicitly reconstructed, that is, none of the quantities used internally or stored
anywhere (register or memory cell or disk or tape drive) will actually be the secret itself and so the new share creation process is safe from the casual eavesdropper.
However, a savvy opponent  who can view the process or get a core dump from the
processor  will be able to recreate the secret.


Any known cases of lucky collisions resulting in security breaches?

There have been similar "security breaches" where someone did indeed gather a lot of public RSA keys and successfully factored some of them using Euclid's algorithm.

I believe the weakness was that a lot of implementations didn't use "random enough" RSA key generators (by using a cryptographically secure random number generator) and this resulted in some common factors of said public keys.

Here's the paper with more information if you're interested.


Does zero-padding the secret in Shamir's sharing scheme increase security?

As you note, Shamir's threshold secret sharing is perfectly secure (or information theoretically secure), yet does leak some information about the size of the secret (same thing with one-time pad).

If you are worried about leaking some information about the size of the secret, then padding could be used to lower the information leakage (instead of knowing that say the secret is 32 bits, the attacker would now know that the secret is no larger than say 1024 bits, something along those lines). If leaking the size of the secret is a problem, then this indeed increases the security of the scheme.

Padding with random bits vs zero-padding would make no difference in security. The secret is already perfectly secure (except for the size of it). Zero-padding hides the length just as well as random padding.

So, what if the secret starts with a zero bit? One thing to do (and this works with random padding too) would be to prepend the length of the padding to the secret. Other techniques would work too.


What is the meaning for a vector mod a matrix in a lattice?

A vector u mod a matrix B is  u ± Bv .    We are modding an element of the vector space's

additive group by the range of the restriction of B to vectors whose entries are all integers.

The parallelepiped given by B's columns is a fundamental domain for the range of that restriction.

⌊⃗c×B−1⌉ is probably rounding each entry of c×B−1 to the nearest integer.  If that's correct, then they are using the lattice representation, which corresponds to using [the translation of the parallelepiped I mentioned which sends its center to the origin] as the fundamental domain.


mapping a 256 bit random number to a 3 bit number

Method 1 - Big Integer Math

Convert the 256 bit random_result to an unsigned big-integer. Divide by 6 and take the remainder. Your die roll result is the remainder plus one.

$6$ does not evenly divide $2^{256}$. It divides about $1.93\times10^{74}$ times with an exact remainder of $4$. That means values $1$-$4$ are over represented but by a negligible amount, since they're only represented once more than $5$ and $6$ over a gigantic range.

The bias towards low die rolls is much much much much less than $2^{-128}$, modern cryptography's slightly arbitrary threshold for the maximum detectable amount of bias in probability.

Method 2 - "Small" Integer Math

Let $M = 6 \times floor(2^{32} \div 6) = 4294967292$, ie. the largest multiple of 6 that fits into a 32-bit unsigned integer.

Split the 256 bits into 8 32-bit unsigned numbers. Find the first value one of those values less than $M$ and return one plus the remainder of its value divided by 6. This returns value has a value a range of values $[1, 6]$.

The reason for using values in the range $[0,M-1]$ instead of $[0, 2^{32}-1]$ is because the latter is not evenly divided by 6. Random numbers in the former range lead to a perfectly uniform distribution.

The probability of one 32-bit value being rejected is $p = (2^{32} - M) \div 2^{32} \approx 9.32 \times 10^{-10}$. All 8 are rejected with $p^8 \approx 5.66 \times 10^{-73}$ probability which is very unlikely. The exact probabilities happen to be $p = 2^{-30}$ and $p^{8} = 2^{240}$. Again, this is less than $2^{-128}$, so you shouldn't expect it to happen.

If it does fail 8 times you can derive more 256 bit numbers by hashing random_result concatenated with a counter. Or you can just use the final 32 bit value if the first 7 fail. The probability of that happening is small and the resulting bias is smaller.

The reason why I specify 32 bit numbers is for ease of implementation and for optimization reasons. There isn't any cryptographic relevance. 64-bit numbers and 64-bit division works as well, but it might not be available in some scripting languages and 32-bit division may be faster than 64 bit division on 32-bit and 64-bit architectures.

You could use 3 bit chunks. Then you could eliminate division entirely because 6 only divides 8 once. Rejecting an individual chunk happens with $1/4$ chance. Rejecting 85 times is less than $6.7 \times 10^{-52}$ or $2^{-170}$.

Method 3 - Seed a PRNG

This would be a really easy if CS-PRNGs were implemented in standard language libraries or popular add-on libraries with a similar API to those for non-secure PRNGs. Using standard PRNGs doesn't work for every application either because of statistical artifacts, small state space, predictability, or lack of a good seeding algorithm.

Edit: Avoid this method. I don't have a single example I can cite. There are too many ways it could go wrong.

No method has significant bias and therefore the entropy of the die roll has very close to $\log_2 6$ bits of entropy. (Assuming reasonably high entropy seed, like 128 bits of entropy. It doesn't need to have 256 bits of entropy.)

I don't think you want an answer based on entropy. I don't know what you mean by "botching the entropy" and I assume you don't know either.

For each method you can estimate entropy of the result by treating the entropy of the hash output about equal to $min(256, \text{seed-entropy})$ and calculating the probability of each outcome 1 through 6 by computing how many hash outputs map to that die-roll-value.

Since we already know the bias to be incredibly small we know that the die-roll result is about uniform. Since it is about uniform we know it has about the maximum entropy you can get out of 6 element discrete uniform distribution, $\log_2 6$.


Encrypting and obscuring data between site/user without SSL

There is no easy way to do this in a secure manner. Simply obscuring the content will give you no additional security. I'll give you an overview of the possible ways to realise such a system, and then I'll conclude by telling you why they don't work well enough, unfortunately.

Key-Exchange protocols and encryption

The basic idea of these protocols is to securely exchange a secret (the shared secret) and use it to encrypt communication.

First approach (flawed, as we'll see)

Have both parties participate in a Diffie-Hellman key exchange

Both agree on $G$ and $P$ (see RFC 3526)
Both generate a random value $X$.
Both exchange public value $Y = G^X \mod P$
With each other's $Y$, they generate secret key: $K = Y^X \mod P$

Now that both parties share a secret, use AES encryption (for instance) to encrypt the data being transmitted, using the shared secret to derive an AES encryption key.

This is easily implemented in JavaScript.

The great problem with this approach is that it's susceptible to a Man-in-the-middle attack. Unless you add some form of authentication, for instance using a pre-shared key, an attacker would simply intercept and relay the comunication: Alice ←→ Eve ←→ Bob. The Communication between Alice and Eve, and between Eve and Bob is now secure, the communication between Alice and Bob isn't.

Possible fix:

If there is a shared secret, one that is either transmitted securely through some other means or shared beforehand, you can authenticate messages using a Message authentication code.

This "solution" however isn't very good. It basically means:

  In order to exchange a secret, first exchange a secret.

Which in practice means this approach will typically lead to an insecure crypto-system. This also happens to be the main problem with One-Time Pads.

You could use asymmetric keys for this, and build a Public Key Infrastructure to overcome this limitation, but then you'd basically implement almost all of SSL. It's worth mentioning again that 99% of security flaws are caused by mistakes in the implementation, rather than insecure protocols.

Second approach (totally doable, reasonably complicated)

We saw that the basic problems comes down to exchanging a secret. In order to authenticate both parties to each other (this is important, authenticating the client isn't enough!), we can use a password. This way, we can exchange a secret and know that we exchange it with the right person.

An example of a protocol designed for this purpose is the Secure Remote Password protocol (SRP). I'll not explain the protocol here, wikipedia does a far better job doing that.

Third approach, just implementing SSL

You could also basically implement SSL using your server-side language and JavaScript on the client. Now, SSL is quite complicated. The probability of a programming error leading to an insecure cryptosystem is very high.

It also requires you to have your own public key infrastructure. Meaning your clients have to get the right keys in order to communicate with your server.

In practice

This kind of thing is almost never done in practice. There are systems like Kerberos which, using a special key server, implement this kind of approach for client-server communication in closed networks, but I've never encountered anything like it on the world wide web.

If you just want to avoid being detected by Deep packet inspection, merely obfuscating the data will be enough. But you have to obfuscate at the TCP level, which normally means re-implementing whole protocols.
If you have to safeguard against decryption or de-obfuscation of your data after the fact, you need to use proper encryption that provides a few properties:

Authentication (you know exactly who you're talking to, both client and server)
Encryption (your communication is secret)
Perfect forward-secrecy (compromise of the long-term keys [like RSA keys] does not lead to a compromise of the short-lived encryption keys, i.e. does not compromise your past communications [this is the huge problem with PGP encrypted instant messaging])
Malleability (adversaries can easily fake the transcript of your messages after the fact, so that your scheme now provides deniability).

One protocol which provides all of these is Off-The-Record Messaging (OTR). This is a fantastic protocol, it's used for Instant Messaging however, not for web-pages.

Conclusion

I think I've taken more than enough of your time to demonstrate: there isn't an accepted or appropriate way to do it. But you can fiddle about until you find something that fits your (watered down) attack scenario. The Secure Remote Password protocol is the best way of doing this.

It will be much easier, and well worth your time and effort, to just change the rest of the system so that you can implement real SSL. That's the right way to do it.


Such an operation is possible.

The ways of calculating that appear to be different for each curve.


If you encrypt an image (AES), is it still an image and can you view it?

If you aim to show the effect of the encryption, meaning a scrabled image you have to encrypt only the "image data" and keep the file structure unchaned. A simple tutorial can be found here: https://blog.filippo.io/the-ecb-penguin/.
Author uses ppm files, but you can easily adapt to your file format.

# First convert the Tux to PPM with Gimp
# Then take the header apart
head -n 4 Tux.ppm > header.txt
tail -n +5 Tux.ppm > body.bin
# Then encrypt with ECB (experiment with some different keys)
openssl enc -aes-128-ecb -nosalt -pass pass:"ANNA" -in body.bin -out body.ecb.bin
# And finally put the result together and convert to some better format with Gimp
cat header.txt body.ecb.bin > Tux.ecb.ppm

Here’s an example (using the key “ECB”):

You actually can. You actually can do even more: encrypt a file format into an other. You need to play with key and IV to get that the message input is "well" transformed by the encryption. If you control the key and the IV and the initial and final file you ave enough freedom to achieve your aim.
Ange Albertini made a proof of concept.
Ablog post explaining the idea is available here: http://blog.fortinet.com/post/angecryption-at-insomni-hack

Roughly you want that the encryption of the file header (with the magic number, identifying the file type) is encrypted into a valid file header. Then you can play with data chunks and segment to get one image or the other.

The video explanation: https://www.youtube.com/watch?v=wbHkVZfCNuE

An example: https://code.google.com/p/corkami/source/detail?r=1906

Some slides: https://www.blackhat.com/docs/eu-14/materials/eu-14-Apvrille-Hide-Android-Applications-In-Images.pdf (not the same as the op asked but the idea is the very same)


Is $(a,g^{ab})$ computationally indistinguishable from $(a, g^c)$?

Their statistical distance is less than $\: (q\hspace{-0.04 in}-$$\phi$$(q))\hspace{.02 in}/q\:$, $\:$ since

$\:$ if $a$ is relatively prime to $q$ then $(\hspace{.02 in}g^a)^b$ and $g^c$ are

$\:$ each uniformly distributed and independent of $a$
$\;\;\;\;$ and
$\:$ even if $a$ isn't relatively prime to $q$, $(\hspace{.02 in}g^a)^b$ and $g^c$ each

$\:$ have a positive probability of being the identity element

.
Therefore, if $q$ has no small factors then they are in fact statistically indistinguishable.


Is the composition of collision resistant hash with non collision resistant hash a collision resistant hash?

Will they always be collision resistant? No

For example, let $h_2(x)=0$. Then, $h(x)=h_2(h_1(x))=0$, which certainly isn't collision resistant.

Can it be collision resistant? Yes

For example, suppose we define $h_1(x)=\mathrm{SHA256}(x)$ and

$$
h_2(x)=\begin{cases}
   0 & |x|=1
\\ \mathrm{SHA256}(x) & \mathrm{else}
\end{cases}
$$

Then, since the output of $|h_1(x)|=256$, the composition will leave:
$$h(x)=\mathrm{SHA256}(\mathrm{SHA256}(x))$$
Which is believed to be collision resistant from the collision resistance of Sha256.

But what if $h_2$ is uniformly distributed across a 'sensible' codomain? As before

I add the requirement that it must be uniformly distributed across a sensible codomain since I assume this clarification wishes to prohibit hash functions for which the target space is too small to possibly be secure)

We can trivially create two examples that demonstrate the above properties. Let $W=\{0,1\}^{256}$. Then, as before let $h_1$ be a cryptographically secure hash function, with $h_1 \colon \{0,1\}^* \to W$ (eg SHA256 as above).
Define $h_2(x) = h_1(\mathrm{MSB_{256}}(x))$.

Then $h_2$ is not collision resistant (since for any $x\in W$ and $y\in\{0,1\}^*$ we have $h_2(x)=h_2(x||y)$), but as before $h(x)=h_1(h_1((x))$.

Defining $h_2(x) = h_1(\mathrm{LSB_{256}}(\mathrm{MSB}_{512}(x))$ (ie we extract bits 256->511) we get the composition $h(x)=0$ which is not collision resistant.

A slight issue here might be justifying $h_2$ is uniformly distributed, but this comes down to how you attach a distribution to the set of all random strings - ie the distribution taken by $\{0,1\}^*$


Differential or Truncated Differential Attack On Small Cipher

How differential attack can be mounted with effort less than brute force.

Was the homework specifically to use a differential attack against this cipher?

Well, part of the problem you're having is that the cipher is, in some sense, too simple to use differential cryptanalysis against; the standard approach of "use DC to find a distinguisher in $N-1$ rounds, and then use that distinguisher to recover the subkey for the last round" doesn't apply.

The other issue is that you're still learning how to use differential cryptanalysis, and it certainly doesn't help that the standard approaches to use DC against this cipher doesn't work.

If you have to use DC, the first thing to do is look for high-probability differentials through the sbox; that is, values $\delta_i, \delta_o$ such that $sbox(x) \oplus sbox(x \oplus \delta_i) = \delta_o$ happen for lots of different values $x$; eyeballing the sbox, it would appear you can find such values which this happens far more often than a well-chosen sbox.

On the other hand, if you don't have to use DC, well, there's an easier approach to attack this cipher.  To start, we note that MDS matrices are bit-wise linear, and bit-wise linear functions have this property:

$$MDS(x \oplus y) = MDS(x) \oplus MDS(y)$$

for all values $x, y$.

Hint: how can you use this relation against the cipher?  How will this drastically reduce the work involved with attacking it?


Why are the first few bytes of a gpg encryption always the same?

The first few bytes are the PGP header. They encode the format information, encryption algorithms and the recipient(s) key id. The recipient must know which key to use and how GPG/PGP has encrypted the session key and payload and how the MAC was generated. Like TLS/SSL the OpenPGP standard has a couple of cipher suites and hash algorithms.

The format is defined in RFC 4880 (http://www.ietf.org/rfc/rfc4880.txt). You can inspect the data with the tool pgpdump

$ gpg -a -e test.txt

$ pgpdump -g test.txt.asc
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
        New version(3)
        Key ID - 0x59C8FAE9A25222C6
        Pub alg - RSA Encrypt or Sign(pub 1)
        RSA m^e mod n(4095 bits) - ...
                -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
New: Symmetrically Encrypted and MDC Packet(tag 18)(110 bytes)
        Ver 1
        Encrypted data [sym alg is specified in pub-key encrypted session key]
                (plain text + MDC SHA1(20 bytes))


The question is from Problem 2 in Assignment 6 given here. It looks much like a straight instance of the RSA problem: we want to find $x\in\mathbb N$ such that $x^e=E\bmod R$ and $x<R$, given $R$, $E$, $e=7$, with $E$ expected to be the product of two unknown primes $p,q$ such that $e$ is coprime with $(p-1)\cdot(q-1)$.

It is correct that knowing none of $d$, $\varphi(R)$ or $\lambda(R)$, nor the factorization of $R$, we can't solve the problem by massaging $e\cdot d\equiv1\pmod{\varphi(R)}$ or $e\cdot d\equiv1\pmod{\lambda(R)}$ with $e$ small.

The fact that $e$ is small would help if it turned out that $E$ (or $i\cdot R+E$ for some small $i$) was an exact power of $e$; for this would allow to find $x$ by extracting an $e$-th root. For random parameters, this happens with odds about ${R^{1/e-1}}$, thus decreasing with $e$. But $R$ is so big that theses odds are vanishingly low for $e\ge2$. In fact, any small odd $e>2$ is believed a safe choice in RSA when $x$ is random or properly padded.

The most classic avenue to solve an RSA problem is to factor the public modulus $R$. This is how Part 1 of Assignment 2 was done, for $R$ of 276 bits. In the present problem, $R$ is 367-bit, therefore brute force factorization is feasible (it was feasible in 1995 by means available to academics; see this answer). However it would require a significant effort, and I do not know that Maple's built-in factorization primitive would factor a properly chosen 367-bit RSA modulus in reasonable time.

We should not rule out factorization though: in this course, Alice (which, we are told, has $R,e$ as public key) has in Assignment 4 made unconventional and rather poor choice of key; so there is a chance that $R$ was not properly chosen and can be factored with little effort, using some of the factorization methods likely alluded to in the course.

Hint 1: The problem can be solved with practically any big-number calculator offering modular exponentiation, without even writing an iterative program.

Hint 2: (Hover mouse to see it)

   Alice may have put too much emphasis on being ultra-resistant to trial division for a given magnitude of $R$.


Is there a risk when publishing multiple signature for the same message ?

As long as the keys are independently generated, there's no risk. This simply follows from the fact that every forgery on the composite scheme - the message signed with $n$ different keys / signature schemes - immediately implies a forgery against at least one of underlying signature schemes. But because we assume these underlying ones to all be secure, the composite scheme is secure as well. And yes, RSA-PKCSv1.5 is also secure.

  What risks are there if the signatures are made with the same key?

If you re-use keys with different signature schemes, e.g. use the same key for RSA-PKCS and RSA-PSS, all bets are off by default in standard cryptographic security models and careful analysis is required to regain security statements. Examples of this include the standalones-secure CBC-MAC (a PRF for inputs which are not prefixes of each other) and OCB2 which used two related primitives with the same key in an insecure way. Without naming concrete schemes to be paired, a general statement is impossible - if they can even reuse the keys which is e.g. impossible for ECDSA and RSA-PSS as one uses a point on a curve as the public key and the other a ring with an exponent.

  However, providing two signatures lets say PKCS1/[SHA]256 and another PKCS1/SHA512 using the same private key, that would not be advisable. Right ?

This would be fine if PKCS1v1.5 signatures were secure for plaintexts without hashing, so a plain signature of 0x05 instead of hashing first would be secure. But this is not the case for PKCS1v1.5. So by default it's indeed not advisable to do this. If you really have to do it though, it could be fine on the grounds that random functions (SHA256 / SHA512) are practically unrelated in their I/O behavior.


As an analogy to asymmetric key encryption, does the following work? If not why not?

(Disclaimer: I am not qualified to speak authoritatively on cryptography - I didn't even take any undergraduate classes on cryptography as a student either)

The first part (the analogy for public-key encryption) is valid (analogising a public-key as a padlock works, but disregards the fact that a public-key (padlock) can be used to decrypt data encrypted with the private-key (the key) - which is counter-intuitive to a layperson).

As for the second part:

  Bob wants to be sure the box came from Alice: (Bob gets Alice's signature)

  Bob sends box to Alice locked with her padlock
  Alice unlocks it, then puts Bob's padlock on instead, and sends it back to Bob
  Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

Key-exchange - or any subsequent interaction between Alice and Bob - is not necessary to prove message authenticity:

In PKI, a digital-signature is basically a message-digest (i.e. a hash like SHA-256) that has been encrypted with a private-key (rather than a public-key) - so that anyone with the public-key can decrypt the encrypted hash (and then recompute the hash and if it matches then that's proof that the message came from the holder of the private-key for the corresponding public-key), like so:

Alice sends Bob a private message.

The message is encrypted with Bob's public-key, so only Bob can decrypt it.

(Assuming Bob's private-key hasn't been leaked or discovered, of course).

While the message is encrypted with Bob's public-key, that has absolutely no bearing on the originator or attestor of the message - because anyone can encrypt anything with someone's public-key.

So Alice also adds her signature to the message, which does two things:

It means that Bob can trust that Alice is responsible for the message (that she either authored or she's attesting to it) - again, assuming Alice's key isn't leaked or discovered.
It proves that the message from Alice to Bob has not been modified (otherwise the recomputed hash wouldn't match).

Alice adds her signature by computing a hash of the message, then encrypting the hash with her private-key, so anyone with her public-key can decrypt it and see her hash.

Bob then receives the message:

The message is encrypted with Bob's public-key, so only Bob can decrypt it with his private-key.
The message has Alice's signature attached to it, so Bob can verify the authenticity and integrity of the message:

Bob has Alice's public-key and decrypts Alice's signature, revealing Alice's computed hash of the message.
Bob then computes his own hash of the message.
Bob sees that his hash - and Alice's hash match - therefore the signature is valid and Alice sent the message.

Regarding Step 3 in the scenario you've posted:

  Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

This is not guaranteed and must not be assumed: Alice could have sent the exact same message to other people, and those other people could have encrypted the message with Bob's public-key and then forwarded it to Bob - if Bob receives one of those messages then there is absolutely no indication it actually came from Alice or that he was the original intended recipient.

This is why, for example, S/MIME for e-mail requires the entire message body and headers to be included in the message hash (in S/MIME this is actually done by copying certain headers like To:, Subject:, From:, etc into the message and then hashing and encrypting that) - so while the adage that anyone can encrypt anything with someone's public-key, so long as the message is also signed by the sender then at least this approach preserves information about the intended recipient in addition to the actual sender.

Example scenarios:

Alice wants to send a non-secret newsletter that can be redistributed by anyone:

Alice would sign her newsletter content with her private-key.
Anyone is able to redistribute (copy, forward, etc) this newsletter, and provided they keep the signature attached to the newsletter then anyone who receives it can be sure it originated with Alice.
Because anyone could simply remove Alice's signature and replace it with their own, Alice can prove she originated the message by getting a signed timestamp signature, as anyone else who subsequently signs the same message (after removing Alice's signature) would have a higher timestamp.

Note that this requires the use of a widely-trusted source of time information. Without a trusted source of timestamps the only solution in a zero-trust distributed system is by using a distributed ledger (aka blockchain) - which is another topic in itself.

Alice wants to send a secret message to a single individual recipient (Bob):

Alice would encrypt her message using Bob's public-key.
Alice should also sign the message to allow Bob to know the message came from her and to ensure the message isn't tampered with in-transit.
Note that nothing stops Bob from redistributing the message after decrypting it - encryption still relies on trust: encryption can't protect data if you can't trust the intended recipient of a secret message to actually keep it secret.

Note that there is little point to encrypting a message using PKI without also signing it because (strictly speaking) encryption doesn't ensure message integrity (i.e. changing random bytes in an encrypted message in most crypto-systems will result in changed output (usually garbled output though, but some crypto-schemes like ECB mode can be successfully attacked without knowing any of the secret keys).


An "encryption scheme" defines the encryption/decryption of data.

A "message transmission scheme" is about securing transmission and defines both "privacy" and "authenticity" between a sender and a receiver.

Since you haven't asked about the definition of CCA-secure (encryption) schemes and since you've been given this as an exercise, I won't mention anything about CCA-secure schemes because that would quickly provide an answer which would almost solve your exercise for you (and you wouldn't learn from that). But, when you keep in mind what I wrote above, you should be able to quickly come up with an encryption scheme that is CCA-secure while not being a secure transmission scheme.

Hint:

Your CCA-secure scheme will be missing something a "message transmission scheme" provides… look closely at what I wrote, ask yourself what a "CCA-secure scheme" defines at a minimum, and then start thinking. You should be able to wrap your brain around it easily if you look at what each scheme defines.


What is the "purpose" byte in Crypto++ PBKDF2?

This seems to only be used in the PKCS12_PBKDF<T>::DeriveKey implementation.
According to the PKCS12 specification,

  The following procedure can be used to produce pseudo-random bits for a particular “purpose” which is identified by a byte, ID. The meaning of this ID byte will be discussed later.

The spec actually declares three values this ID byte can take, depending on the actual purpose of the key derivation.

It's not used for PBKDF2, and seems to only be present in its signature to have the DeriveKey method of PasswordBasedKeyDerivationFunction be usable for all subclasses here.


Making both the IV and salt public for PBE with AES-CFB

In cryptography an Initialisation Vector or IV is an input of fixed size required to randomize the output of a cryptographic primitive. It is not meant to be secret, so there is not problem in make it available to the attacker after the encryption. The crucial point about the IV is its uniqueness and, for some mode of operation, its unpredictability. So, if your implementation correctly generates the IV using the right random number generator there is no problem in making it public, after the encryption.
Quoting poncho:

  What this means that if you keep the IV secret, it doesn't really
  hinder any particular attack in any way. One way to see that is to
  assume the contrary; let us assume that, if we expose the IV to the
  attacker, that he can exploit some weakness. If we assume that, then
  the attacker can use that weakness to attack a CFB mode encrypted text
  without the IV; what he does is take the ciphertext (without the IV),
  and treat the initial ciphertext block as the IV, and the rest of the
  ciphertext as the "real" ciphertext; the plaintext this corresponds to
  is the normal plaintext with the initial block omitted.

  Because of this, if exposing the IV with CFB mode lead to a weakness,
  CFB mode in general is weak. Now, written this way, this might not
  sound very comforting; however athat statement is logically equivalent
  to "if CFB mode is strong, then CFB mode with the IV mode exposed is
  strong", which is really what we want to show.

A salt is a random value added as additional input to an hash function, or to a key derivation function to protect the construction from dictionary attacks, an attacker should create a dictionary per salt. As in the IV case, the crucial property is the uniqueness. You don't want all password share the same salt (otherwise an attacker may build a dictionary to attack many password at the same time).

In both cases you should authenticate the values.

So the answer to your question is "no, it does not compromise security". You should really pay more attention to the algorithm used to generate IVs and salts (and probably salt size). And add a mode to check the integrity of the ciphertext (+ the IV) before decrypt it.


Well, not exactly.

The hash function that your MD internally uses a compression function $f:\{0,1\}^{256} \to \{0,1\}^{128}$

MD construction uses an IV, in your case 128-bit feed into the first call $f$.

The first input and output of $f$ is $h_1 = f(IV\mathbin\|m_1)$. From these, you can deduce that you must divide your message $m$ into 128-bit blocks. 1093 rounds that make 1093*128 = 139904 that is 96-bit less than a full block.

Therefore you need padding and also protection against length extension attacks.

Assume that we simply use the last 64-bit as the big-endian length encoding and padding is 1000000...000Length_in_64_bit. In the end, we require that the size after the padding is a minimum multiple of 128. In your case, your message becomes

$$m =\texttt{M}\mathbin\|\texttt{100...0}\mathbin\|\ell$$ where $\ell$ is the encoding of your length. 96 bits don't leave space for a 1 and encoded length. Therefore you need 1095 round that is 140160 bits.

Now you can divide your message into 128-bit blocks say; $m_1,\ldots,m_{1095}$

\begin{align}
  h_0 &= f(IV\mathbin\|m_1)\\
  h_i &= f(h_{i-1}\mathbin\|m_u), \quad 1<i\leq 1095\\
  H(M) &= h_{1095}
\end{align}

Note that, MD can also apply a finalization with $g$ in the end. In this case $$H(m) = g(h_{1095})$$


Convert plain text as numbers to encrypt using RSA

Is there any (open) standard for converting text to numbers before encrypting?

Well, yes and no.

There is the Unicode standard which converts each character as a single code point. But that's not what you are after, you want to encode a complete text into a number.

To do this the standard way to operate is to use two conversions:

convert the text to bytes using a character-encoding;
convert the bytes to a (large) number.

Now RSA certainly operates on numbers, but the RSA PKCS#1 standard is defined to take bytes as input. So step 2 is an integral part of PKCS#1 called OS2IP. OS2IP means Octet String (bytes) to (two) Integer Primitive. OS2IP simply interprets the bytes as an unsigned, big endian number.

OS2IP however happens after padding, which is performed on the input bytes. Padding is required to make RSA secure.

So that leaves us with the first step: converting the text to bytes. Text is stored inside computers as a string of characters. Character encoding is what is used to convert a set of characters (an alphabet) to bytes. The most logical character encoding is no doubt UTF-8, which encodes most of the most common Unicode characters to a single byte, ASCII compatible representation.

Unicode with UTF-8 is definitely as close as you can get to a commonly accepted standard.

If you want to experiment with raw/textbook/unpadded RSA, you could first encode using ASCII or UTF-8, and convert the resulting bytes to a number using OS2IP - but keep in mind that this is insecure.


How to configure a client browser cert to be authenticated by a server?

You have to use the certificate (which will have your public key) which you had generated, to configure your browser. This certificate can be used by your browser to authenticate itself with server.


Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

We are given some $b^t = s^t A + e^t$ for $A$ of the above form and short $e$, and wish to recover $s$ (which will immediately give us $e$ as well). If $e$ is short enough, then $\hat{b}^t = (s^t H) G + \hat{e}$ for some sufficiently short $\hat{e}$. (This is where we use the bound on the expansion, or top singular value, of $R$.) Therefore, the LWE inverter for $G$ will recover $s^t H$ (and $\hat{e}$), from which the original $s$ can be recovered via $H^{-1}$.
It’s very important that $e$ is short enough to ensure that $\hat{e}$ is short enough. If the latter is too long, then the LWE inverter for $G$ might return the wrong answer for $s^t H$, leading to a wrong $s$ and thereby a wrong, probably very long $e$.


Is there a theoretical maximum useful keysize given the block-size?

If you are asking about a truly theoretical limit for a theoretical block cipher (as opposed to a practically usable one, like AES), you could calculate the number of possible keys like this:

A block cipher, together with a key $k$ ($|k|$ = $M$), describes one of many possible random permutations: For every plaintext block, there is exactly one ciphertext block. The number of possible blocks is simply $2^M$, where $M$ is the length of a block in bits.

The number of permutations of $n$ different objects is $n!$, so for our (very unpractical) block cipher, there can be at most $2^M!$ keys. Many of those will be unusable in practice (for some, plaintext and ciphertext will differ for only a single block), but they all satisfy your condition that they differ in at least one plaintext-ciphertext-pair from all other permutations.

Now, specifying one of all possible permutations without any optimization would take an insane number of bits to transfer (the number of plaintext-ciphertext-pairs in the permutation, times the number of permutations: $2^M\cdot2^M!$

To be able to actually transmit the key with fewer bits than any conceivable message, we limit our keyspace to mere $N$ bits, or $2^N$ possible permutations.

If you insert the actual numbers, we get $2^{256}$ possible keys for AES-256, which seems like a lot (and for practical purposes, it is), but the theoretical limit for 128-bit blocks is much, much higher: $2^{128}\cdot2^{128}!$.

Update:
Avijit has pointed out in the comments that there is an easy optimization which allows enumerating all possible permutations with "only" $\lceil log_2 2^M!\rceil$ bits (which allows for $2^M!$ keys). This is a lot more compact, but still much larger than any practical key size.


Encrypt entire payload or only confidential parts of payload?

Pros of encrypting entire payload:

That's simplest to code.
Encrypting data may have the side-effect of improving the chances to detect an alteration during transfer of the cryptogram (hence enciphering the whole payload may extend that beneficial side-effect to the whole payload); however that is not the function of encryption, and it must not be assumed that encryption ensures integrity, especially facing malicious changes; see second section.

Cons of encrypting entire payload:

The whole payload becomes unintelligible, possibly hindering functionality; e.g. we could loose access to the identifier of the destination of the data (possibly needed for routing to the appropriate location), when it was produced (forcing transmission of obsolete data), or the index/identifier of the key used for encryption (making decryption a guesswork).
Because of the above, some essential data might need to be duplicated in clear, increasing the size of the data transmitted, thus transmission time and cost.
Encryption time has a component proportional to the amount of data enciphered, thus there is more encryption and decryption work to do.
The attacker has potentially more known plaintext/ciphertext pairs; that is a non-issue with modern ciphers, but used to be a way to attack pre-1970 cryptosystems.
It is much easier to get approval for free circulation across borders of a system using secure encryption that enciphers only specific fields of an application-specific message, than for a secure system designed to encipher arbitrary data; this reality often entirely negates the first stated advantage of enciphering the whole payload.

In many practical cases, a sound security analysis would conclude that the right option is to ensure the integrity of the whole payload, and the confidentiality of part of it. Some modern operating modes, like AES-GCM, have provision for that; the computational savings obtained by not enciphering what needs not are significant (at least when AES is in software).


Plaintext with 'T' and 'E' alphabets missing and encrypted with Vigenere Cipher

frequency analysis works just fine even without a few common letters. In fact you don't even need to know the frequency in the underlying alphabet it is sufficient that it is far from uniform. You can rotate the columns so as to make the frequencies in each match.
Alternatively using an English bi-gram frequency table you can break this quickly even without two letters.

Do you know if the letters were removed from plain text in preprocessing or is this a clever text without these? it makes no difference for first method but some if you bring in external frequency tables.


Private Information Retrieval--Is it still theoretical?

Not a real answer, but some hints:

Single DB PIR schemes (ones that don't need several non-colluding DB) have had serious efficiency problems for a long time. See paper 'on the computational practicality of private information retrieval' by Sion and Carbunar arguing that all schemes at that time (2007) were less efficient than downloading the whole DB (most simple PIR technique).

However the same year, Trostle and Parrish published a PIR scheme that does not have this problem. If someone uses PIR he's probably using this one.

We use it in my team but it's research, and I am not aware of use cases in the industry.

EDIT

As mentionned by DrLecter, Trostle and Parrish single-database cPIR has been broken (http://eprint.iacr.org/2015/012).

Good news are that PIR has evolved since then and a French team built a PIR framework to prove that PIR is now practical: XPIRe: Private Information Retrieval for Everyone

The PIR they use does more or less the same thing as Trostle and Parrish, i.e encryption of a zero for cells you don't want, encryption of 1 for cell(s) you want, but they use a stronger underlying homomorphic encryption scheme so that it's not broken. The obtained throughput and latency they obtain is insane (1080p streaming over NetFlix-like DB !!!).


What if in AES-128 CBC, IV is very related to KEY?

This implementation is horribly broken, since the IV is (most likely) sent in the clear. An eavesdropper who knows the implementation will immediately be able to deduce the key and decrypt all data.

The IV will also be the same for repeated uses of the key. This opens up several weakness. For one, it leaks information on when multiple plaintexts begin with the same data, and for approximately how long. IV reuse is also vulnerable to chosen plaintext attacks. See this answer for more details.


Hash function for a small, enumerable set of elements

To the best of my understanding, you're trying to make phone->ID an irreversible transformation. For long inputs, hashing would suffice, but there are so few possible inputs (phones) that enumeration is feasible and even a slow PBKDF won't make mapping prohibitively difficult.

Strong security is impossible in this scenario. The best you can do is slow down the data gathering process. To do that, you have to be the only one able to perform the transformation; that requires keeping a secret. It's not a salt then, but a key. The transformation can be hash(phone+key) or just encryption of the phone with the key - if the key is leaked, the security is broken either way.

Preferably, I'd suggest that you consider alternative approaches. If it's a way to find "friends", do you have to reveal the ID right away? For instance, when one enters a phone number, you only send a friend request to that number's corresponding ID if it exists, without confirming whether it does. Only upon request confirmation do you reveal the ID. Can be combined with a friends-of-friends system to limit random requests.

Don't count on this for much. But, combined with limits on accounts and friend requests, and some monitoring for suspicious activity, it could make mapping the users take more effort than it's worth. If and only if that mapping actually isn't worth much.


How to produce large list of BigInteger prime numbers (RSA) in fast and efficient way

We will actually need to have a list of prime numbers

That's dangerous, since that list must be kept secret, and primes that have been used removed to avoid reuse. There's almost always a better way, like generating the primes on demand. But let's ignore that.

  My current approach here is to actually skip all the even numbers and increment the BigInteger by 2 through looping to select and filter out the possible prime numbers

If two large primes $p$ and $q$ thus obtained are used to form RSA moduli $N=p\,q$ , then that modulus $N$ will be factorable in a millisecond: compute $u=\left\lceil\sqrt N\,\right\rceil$, $v=\sqrt{u^2-N}$ (which critically will be a small integer), the factors are $u-v$ and $u+v$. That's a special case of Fermat's factorization method. This works because the two primes will be overly close¹, and illustrates a more general fact: we must generate two primes forming an RSA moduli in a way such that they bear no relationship known to an attacker².

Also, in most applications, we want that revealing the factorization of a number of $N_i$ does not help factoring any other $N_j$. For this reason, it's simplest/common/best to generate the primes independently. It remains important to generate them fast.

There are several ways to generate primes in a reasonable time. A simple one improves on the method above by avoiding not only the multiples of two, but the multiples of more small primes, so that fewer candidates will be tested before a prime is found. For example, when generating a prime with $b$ bits, we would expect to test about $b\ln(2)/2$ odd integers (that's $\approx355$ for $b=1024$), per the Prime Number Theorem. But if we manage to avoid those with no divisor among the first $127$ primes (that is, the primes to $709$), we improve this by a pleasant factor of $\displaystyle\prod_{3\le s\le709\\\,s\text{ prime}}\frac s{s-1}\ \approx5.9$.

The most usual methods towards that are

First testing a candidate odd prime $r$ with $\gcd(r,m)=1$, where $m$ is the product of a number of small odd primes; e.g. first up to $23$, or $29$ such that $m=3234846615$ barely fits 32-bit. In one swift test, that reduces the number of prime candidates by a factor of $\approx3.17$. But if the method to test primes already does something equivalent or better, this added filtering will actually harm!
Sieving, essentially building a sieve of Eratosthenes localized to an interval sieved. It's effective, and often practiced. But it's a tad difficult to code and optimize³; and the basic algorithm exhibits detectable bias⁴.

There are other techniques which generate provable primes, and I'm told they are competitive from a performance standpoint. See e.g. FIPS 186-4 B.3.2 for one.

I now describe an alternative to sieving, that also avoids testing candidates $r$ with a small prime factor $s$ (though to an appreciably lower bound than possible with sieving, as noted by poncho), without an explicit sieve array, and (discounting precomputations) with less work on modular reduction of a large value modulo a small prime $s$, which sometime gives a speed advantage.

In a nutshell, we'll use the Chinese Remainder Theorem to generate candidate primes $r$ with $r\bmod e$ drawn in $[2,e)$ and $r\bmod s$ drawn in $[1,s_i)$ for other small primes $s_i$.

Inputs:

We want to generate random primes in $r\in[r_\min,r_\max)$ for use as RSA modulus. We restrict to $2^{(2^6)}\le r_\min<1.01\,r_\min\le r_\max\le2^{(2^{20})}$. For $b$-bit primes intended for $2\,b$-bit RSA moduli with two factors, the customary interval is $\left[\left\lceil 2^{b-1/2}\right\rceil,2^b\right)$, which insures that the product of any two primes generated will be $2\,b$-bit.
We want to use some public exponent $e$, and thus need $\gcd(r-1,e)=1$. We restrict to $e$ an odd prime. Popular choices for $e$ are the five known Fermat primes, and 37.

One-time precomputations:

$m\gets2\,e$.
$r\gets\left\lfloor(r_\max-r_\min)/(2^{40}\,m)\right\rfloor$.
$i=0$.
$s\gets 3$.
While $s<r$ (it's possible to abort earlier, e.g. when $s$ or $i$ is above some bound):

if $s\ne e$:

$s_i\gets s$ (these are primes saved for later use).
$c_i\gets(-m)^{-1}\bmod s$ (these are CRT coefficients for later use).
$m\gets m\,s$.
$r\gets\left\lfloor r/s\right\rfloor$.
$i\gets i+1$.
$s\gets$ the prime following $s$.

Slightly restrict the search interval for $r$ to $[k_\min\,m,k_\max\,m)\,\subset\,[r_\min,r_\max)$ with $k_\max-k_\min$ a prime $t\ne e$, as:

$k_\max\gets\left\lfloor r_\max/m\right\rfloor$.
$t\gets\left\lfloor(k_\max\,m-r_\min)/m\right\rfloor$.
if $t$ is even: $t\gets t-1$.
while $t$ is not prime or $t=e$:

$t\gets t-2$.
$k_\max\gets k_\max-1$ (optional, keeps the interval centered on $[r_\min,r_\max)$ ).

$k_\min\gets k_\max-t$.

For each prime $r$ to generate:

Pick a uniformly random secret $v$ in $[0,e-2)$.
$r\gets ((v+1)\bmod 2)\,e+v+2$; this leaves $r$ odd with $(r\bmod e)\in[2,e)$.
$m\gets2\,e$ ; it now holds $r\in[0,m)$.
For $j$ from $0$ to $i-1$:

Pick a uniformly random secret $v$ in $[0,s_j-1)$.
$r\gets r+m\,((r+v+1)\,c_j\bmod s_j)$ ;
this leaves $r\bmod m$ unchanged and $(r\bmod s_j)\in[1,s_j)$.
$m\gets m\,s_j$ ; it now holds $r\in[0,m)$.

Pick a uniformly random secret $v$ in $[0,t)$, determining the first $r$ tested.
$r\gets r+(k_\min+v)\,m$.
Pick a uniformly random secret $v$ in $[0,t-1)$, determining how $r$ is stepped.
$v\gets v+1$.
$r_0=v\,m$ (increment for $r$)
$r_1=(t-v)\,m$ (decrement for $r$)
$r_2=(k_\max-v)\,m$ (threshold for an increment of $r$).
Repeat⁵:

If $2^{(r-1)/2}\bmod r$ is $1$ or $r-1$ (that is, $r$ pass the Euler test to base $2$):

Test if $r$ is prime⁶, using e.g. a small number of strong pseudoprime⁷ tests to random base, and if so:

Output $r$ and stop.

If $r<r_2$: $r\gets r+r_0$; else: $r\gets r-r_1$.

Caution: It is critical to use an unpredictable randomness source, and that all quantities manipulated remain secret.

¹ The primes will be close if they have been chosen incrementally.

² Other kinds of harmful relations between primes could be: they are generated by testing integers of the form $2\,k\,a+b$ for public $a$ and random secret $b$. That could extend to random secret $a$, if there are several $N_i$.

³ Competing computational bottlenecks are the final primality test (the more small primes are sieved, the less such tests there are), and computing the offset in the sieve (which requires computing the remainder of a large value modulo each of the small primes).

⁴ If we select the smallest prime in the sieved region, it will have a gap with the previous prime larger than expected for a random prime. Selecting a uniformly random prime in the sieved region mostly fixes that, but still the selected prime will tend to have less neighboring primes than expected for a random prime. These biases are detectable when examining the primes generated, but are not a security concern in RSA.

⁵ With $(r\bmod e)\in[2,e)$, $(r\bmod2)=1$, and $(r\bmod s_j)\in[1,s_j)$ for $0\le j<i$. The product of these distinct coprime moduli is $m$. Prime candidate $r\in[k_\min\,m,k_\max\,m)$ changes by multiples of $m$, among $t$ possible candidates. $t>2^{39.9}$, which makes it beyond reasonable doubt that there's a prime among the candidates, given the upper bound for $r_\max$. The order in which we scan them is random and secret among $>2^{39.9}$ possibilities, conjecturally defeating statistical tests of non uniformity.

⁶ This is very likely, to the point of making the contrary hard to test.

⁷ In an RSA context, it is considered acceptable to restrict to primes $r\equiv3\pmod 4$. This simplifies the strong pseudoprime test to an Euler test (or otherwise said, makes the straightforward Euler test more robust). This can be obtained by $r\gets ((1-v)\,e\bmod4)\,e+v+2$ rather than $r\gets ((v+1)\bmod 2)\,e+v+2$, and $m\gets4\,e$ rather than $m\gets2\,e$ (the later occurs in two steps).


Any concrete examples of the use of NIST Special Publication 800-90B?

What is the purpose of NIST SP 800-90B?
I think you are misunderstanding what NIST SP 800-90B is for. It is not a document explaining how to estimate the quality of a hardware noise source, but rather is meant for validation of a noise source. This means that you will not see it used to return a number of bits per byte. Instead, it will return pass or fail, depending on the quality of the randomness. A source that passes the test will be able to proclaim that it is 800-90B compliant and will be one step closer to being fully FIPS compliant. See section 3 in that paper for more information on that validation process.
To put it simply, there are two steps. The first is a test done in an accredited lab environment where the raw noise source is subject to tests, and the second involves an online test that actively runs as the noise is being collected, prior to conditioning or whitening. The first tests are extensive and are used to check whether or not the noise source lives up to the IID claims made by the manufacturers. The second test is an online test which is constantly run. The online test is part of the implementation and is designed to detect transient failure of the RNG. FIPS requires it shut itself down and refuse to output anything if the test ever fails. The online tests are much simpler than the initial tests as they are run constantly, making performance an issue.
You can run these tests yourself on any raw noise source you have. Post-processing using a simple algorithm is permitted if the source is biased but IID. Only three algorithms are permitted: Von Neuman debiasing, linear filtering, and run length counting. After that, you are free to condition the output using a cryptographic whitener, such as those specified in 800-90A.
A simple overview on one of the drafts for this document is available here.
Who is compliant with 800-90B?
Almost every single product listed on Wikipedia's Comparison of HWRNGs is either directly 800-90B compliant, or is compliant by extension of being FIPS 140-2 compliant. Others are compliant to similar standards such as STS or AIS 31 (which both specify a battery of statistical entropy tests run on pre-whitened, raw hardware noise sources). Some of these have open designs, meaning everything, including the noise source, is public. Others keep that as a trade secret, but publish detailed whitepapers and patents. Perhaps you should look at them.
It is a standard and necessary for FIPS 140-2 compliance, so many TRNGs will be using it. If you have something with a hardware noise source that needs to be FIPS certified, you will see a use of NIST SP 800-90B. At this point, the question becomes Are there any examples of FIPS-certified implementations in which case the answer is yes, many. Microsoft, Intel, Atmel, and even Western Digital have products that are FIPS 140-2 compliant, and thus also NIST SP 800-90B compliant.
If you are looking for a research publication, there are various academic papers that discuss improvements and critiques of the various entropy testing techniques used. For an actual publication going down to the silicon itself, you will probably be out of luck. Those things tend to be considered trade secrets and the most you will see is various whitepapers. In these cases, what you want to look for is whether or not their datasheet or whitepaper claims compliance.
While it is not an academic research paper, here is one concrete example, the TRNG-IP-76:

Another example may be the ATAES132A, an encrypted EEPROM chip with its own FIPS-certified RNG. Other examples would be the main microcontroller for any number of Opal-certified storage devices, TCG-certified TPMs, various smart cards, or even your CPU itself.


Is it safe to store initial counter value for AES-CTR alongside with ciphertext?

It is an IV and it is safe to transmit with the ciphertext (if it wasn't, we would call it a key).


Why OpenSSH prefers ECDSA nistp256 keys over -384 and -521, and those over Ed25519, for host key verification?

If I remember correctly, it is simply an issue of performance. Remember, HostKeyAlgorithms determines the method used to authenticate the server to the client, it does not generate session keys.
The ECDSA algorithm is faster than RSA, and small key sizes are faster than large key sizes, when the default was changed in 5.7, the changelog specially referenced performance reasons, See the first feature item.
NIST keys are probably preferred over ED25519 for compatibility reasons, I have had to generate NIST keys after Curve25519 based keys after finding the server did not support them, so that makes total sense. Curve25519 based keys are probably more secure, unless you are asking NIST, then they say the are equally secure.
Since these are just default options, you are of course free to change them or force a specific algorithm, I have forced 3072-bit RSA for my default host key method. Remember, this is a selection option, if a key type on the list does not exist, it will not be used. If you only have RSA keys in your configuration, all the EC options will be skipped, you can delete them at will.
If you are using SSH for transport and you have control over the app and server, you can just generate the 1 host key you want and be done with it, and ignore the configuration options, since they will not matter.


functional encryption over homomorphic encryption

The main difference between FE and HE is that:
In HE, for the decryption you need to interact with the owner of the secret-key, but in FE everybody who has access to the ciphertext and functional key can decrypt the massage.
While HE can efficiently support different kinds of computation over encrypted data, FE supports limited class of functionality (in theory it still can support general functionality).
This limited class includes: inner-product (which might be what you called weighted sum) and quadratic functionality.
Recently there has been a European Project called FENTEC, they are trying to implement the existing FE schemes.


what are the plaintext's for the RC4 stream cipher test vectors in RFC6229?

RC4 is some kind of pseudo random number generator. You input a key (seed) and now can get a stream of pseudo random numbers. The values here are this numbers, always a byte at a time.

Unlike a block cipher, you don't have a plaintext. You use this key stream to add it to the plaintext to get the ciphertext. "Adding" can be done with XOR, because that's pretty easy and the most common way.

Yes, DEC means the offset. The first 16 values are the 16 output bytes of RC4 with the mentioned key. The next 16 values are the output bytes after the first 16. The third line has the output bytes after the first 240 bytes.

We could say that the plaintext was all zero bits. This would lead to the ciphertext being the key stream.

This online tools allows to encrypt / decrypt something with RC4. Switch the input and the key to hex numbers, write only zeros as input text and then copy the key into the key field (without the 0x at the start). Now you can see exactly the mentioned numbers as output of the function.


Can the confusion/diffusion of a hash algorithm be quantified?

It depends a lot of why you want to do this and for what types of hashes and input data but I would think that for some purposes it may be sufficient to do so through sampling, though you would certainly want to be careful about how much you trust this sort of analysis depending on how you're using the hash values.

For example, if you know that the data you're hashing often has a certain format or is always a certain length you could generate a set of test inputs of manageable lengths. For the purposes of this answer let's say 4 bytes but in practice you'd probably want to pick an assortment of lengths that apply to your use-case.

You should include some simple values (e.g. 0x00000000, 0xFFFFFFFF), some patterned values (e.g. 0x40404040, 0x1ACEECA1), and some completely random values.  Then take each one and hash it to get a baseline, $H$, of length $N$ bits (i.e. 32).

For diffusion you could then, for each bit of the input:

Flip the bit, $i$
Hash the altered value, $H_i$ (i.e. the hash with bit $i$ flipped)
Count the number of bits that differ between the new hash and the baseline hash, $d_i$
Calculate $1 - \frac{| d_i - N/2 |}{N/2}$ to get a rating $r_i$ between 0 to 1 (with 1 being ideal diffusion).

For confusion you could do something similar, checking that across $H_0$ to $H_{N-1}$ each bit is flipped relative to the baseline due to changes in as many input bits as possible, creating a score for each output bit.

Using these diffusion and confusion scores, you could then compare hashes depending on whatever criteria you're most looking for in your use-case.

All of that said, this is a somewhat brute-force method that could very easily miss issues in a hashing algorithm that could be important from a security perspective.  So again, I would only consider using a method like this if you're considering the properties of the hash relative to a specific use-case that isn't security-critical.  Making this kind of statistical argument when you don't already have some idea what types of inputs you might be seeing reducing the likelihood that it will tell you anything useful effectively to zero.


How to compare two datasets „anonymously”?

That sort of thing is known as multi-party computation, and you

should use a Socialist Millionaire Protocol for your particular instance.


What is the difference between perfoming Correlation Power Analysis (CPA) in the first AES round and doing it in the last round?

When you perform CPA against AES, you'll attack either the first or the last round depending on the data you've got at hand. Both attacks are of the same complexity, roughly.

If you know the plaintext $p$, then you'll exploit the very first AddRoundKey and attack the first SubBytes routine, which will allow you to recover directly the master key, by doing CPA on assumptions about the value of $k_0\oplus p$ as input to the operation SubBytes.

Now, if you know only the ciphertext, you'll want to attack the last SubBytes routine of the whole AES process, to recover the last round key through the last AddRoundKey operation, and once you have a round key, you can recover the master key since the key schedule is invertible.

In the last round the operations done by AES are:
SubBytes, ShiftRows, AddRoundKey.

So you will want to do CPA on the SubBytes operation, just like you did in the first round case, except that you'll have to deal with the ShiftRows operation, which is hopefully invertible.
You will have assumptions on the input value of your SubBytes method, which is $\mathtt{SubBytes}^{-1}[\mathtt{ShiftRows}^{-1}[k_{10}\oplus c]]$, for $c$ a known ciphertext. Those are all reversible operation, thus it is possible to compute the assumed input.

Thus the differences with the first round case are:

you are using a known ciphertext instead of a known plaintext,
you will end up with the last round key $k_{10}$ instead of the actual key $k_0$ ,
you'll have to deal with the ShiftRows operation.

Maybe you can read this, although it's not going really into the practical implementation steps.

You can also read this question and its answer to get why why want to target the SubBytes routine, as well as that one.


elliptic curve multiplication with negative factor

If you know the order of the curve (we'll call it $q$), then it's easy.

In that case, we have the identity $xP = (x + q)P$ for any $x$.  Using that identity, we can express $(-n)P$ as $(q - n)P$; by the above identity, these are the same.  If $q > n$, this gives you your answer.

The more general answer (which works for any $n$) is $(-n \bmod q)P$, using the convention that $a \bmod b$ is that integer which is between 0 and $b-1$, and which is congruent to $a$ modulo $b$.

This is exactly analogous to the $\mathbb{G}^*$ case; in that case, the size of the group is $\phi(q)$; in this Elliptic curve case, the size of the group is $q$.