Generating Encryption Keys from Biometric Fingerprint Templates

There is a pretty good introductory book that strongly relates to the topic area: Security with Noisy Data that I would recommend you take a look at. The book has constructions for how you would do this (turn fingerprint readings into keys), information on different adversary models you might consider, and information on related topic areas.

I am not familiar with either of the SDKs you mention, or the formats. So, for the sake of simplicity, I'll assume that each time you read the fingerprint, you get back a binary string. Since the scanners are not perfect, each time you read from it, you will get back a slightly different binary string. Let $\rho$ be the maximum error rate you see between binary strings which come from scanning the same fingerprint. One chapter in the book (which is freely available here) gives constructions for how you can generate and publish some helper data which can be stored in plaintext. This helper data allows you to recover the original key so that you can, for example, decrypt.

Let $C$ be an $[n, k, 2t+1]$ linear error  correction code defined over some finite field $\mathcal{F}$. $t$ is the number of errors that can be corrected, so we need  $t$ to be large enough to  correct $n\rho$ errors. The syndrome construction for secure sketches works as follows.

We have 2 phases (enrollment and reconstruction or GEN and REP). GEN: Let $H$ be the parity check metric of $C$. We take a sample from the reader to get the binary string representing the fingerprint, call it $w$. The length of $w$ is $n$. Let $H$ be the parity check matrix of $C$, we compute the syndrome of $w$ as $wH=s$. We then run $w$ through an extractor (e.g., a hash function) to get the key. We publish $s$ publicly as the helper data.

REP: At some later point in time, we want to reconstruct the key (do do a decryption or further encryption). This time we take another sample using the reader and get $w'$. We decode $w'$ using $s$ to get back $w$, and rerun $w$ through the extractor to get the key. As long as the hamming distance between $w$ and $w'$ is less than or equal to $t$ we are guaranteed to get the same key. For more information on coding, and some source code, see here.

In practice there can be issues. The helper data $s$ leaks information. So, to get 80 bits of security, $w$ is going to have to be larger than 80 bits long. Using the syndrome construction, we can quantify the amount of information leaked by $s$. It is $n-k$ which happens to also be the length of $s$. I am not sure what the error rate is for fingerprint scans or the entropy rate. It could very well be that by the time we have published $s$ there is no usable entropy left. Recent work tries to deal with this case. But, if the error rate is too high, and the number bits in a single fingerprint is too low, we could be in a case where there is just not enough entropy to get a strong key. Therefore, you really need to analyze and think about if this will work. Theoretical constructions are there, but physical limitations might make it impossible.


Constant size commitment to a bivariate polynomial

I think the main issue for the bivariate polynomials is the coefficients of the polynomial $f(x,y)$. Since $\tau$ is a secret value then to calculate $g^{\alpha f(\tau)}$ we can use the public parameters. As you know, the users can obtain the coefficients based on a standard basis and then solve a multiplication.
$$g^{\alpha f(\tau)}=\prod_{i=0}^{n}{(g^{ \alpha \tau^i })}^{f_i}$$
For a univariate polynomial, the coefficients of $f_i$ are constant while if we consider bivariate polynomials then it is necessary to evaluate a second polynomial on the $\tau$. Precisely, the standard basis $(1,X,X^2,...,X^d)$ forms the univariate polynomials and the coefficients for a bivariate polynomial are changing by the second variable.


How to find the value of a vector modulo a basis in lattice-based cryptography

Examining the definition provided by A. Sakzad, I now have the intuition for what this means which I'll explain through an example.

In the diagram below, the red dots are a lattice, and the two red arrows represent a basis, $B$, for this lattice. We have a green vector, $ψ'$ = [2, 2]. We might ask which point on the lattice $ψ'$ is closest to. If we are just looking at this in the grid reference frame, $ψ'$ is equidistant from [3, 1] and [3, 3]. But within the reference frame of basis $B$, which is shown by the red parallelograms, $ψ'$ is closest to (3, 3). The value of $B⋅⌈B^{−1}ψ′⌋$ is the point in the lattice to which $ψ'$ is closest in the reference frame of $B$. $ψ=ψ′(\mod B)=ψ′−B⋅⌈B^{−1}ψ′⌋$ is the vector from $B⋅⌈B^{−1}ψ′⌋$ to the original vector. It could be viewed as the error or remainder when $ψ′$ is approximated by a point on the lattice. In the diagram below, $ψ$ is the blue arrow.

Since the basis vectors are [3, 1] and [0, 2] the basis matrix is:
$$
B = \left( \begin{array}{ccc}
3 & 0\\
1 & 2 \end{array} \right) $$
Doing the math we find that (3, 3) is indeed the value of $B⋅⌈B^{−1}ψ′⌋$:
$$
B⋅⌈B^{−1}ψ′⌋
=B⋅⌈1/6 \left( \begin{array}{ccc}
2 & 0\\
-1 & 3 \end{array} \right)
\left( \begin{array}{ccc}
2\\
2 \end{array} \right)⌋ $$
$$
= B⋅⌈\left( \begin{array}{ccc}
2/3\\
2/3 \end{array} \right)⌋
= \left( \begin{array}{ccc}
3 & 0\\
1 & 2 \end{array} \right)
\left( \begin{array}{ccc}
1\\
1\end{array} \right)
= \left( \begin{array} {ccc}
3\\
3\end{array} \right)
$$
Therefore the remainder of $ψ′$ modulo the basis is:
$$ ψ=ψ′(modB)=ψ′−B⋅⌈B^{−1}ψ′⌋ = \left( \begin{array} {ccc}
-1 \\
-1 \end{array} \right)
$$


We have the three cipher texts $m^3\equiv c_1\equiv 4\pmod{6}$, $m^3\equiv c_2\equiv 20\pmod{35}$ and $m^3\equiv c_3\equiv 142\pmod{143}$. An application of the Chinese remainder theorem tells us that $m^3\equiv 1000\pmod{30030}$, but because $m$ is less than $\root 3\of{30030}$ we know $m^3=1000$. A regular cube root now recovers $m=10$.


Is hashing large files CPU or I/O bound?

Clearly this depends a lot on your setup.

Looking at some numbers:

According to Wikipedia SHA-3 requires 12.5 cbp (cycles per byte) on a Core 2. Let's also assume this Core 2 has 2.4 GHz.
So we get 2.4 GHz / 12.5 cbp = 192 MB/s for the hash calculation.

Let's say you have an SSD with 500 MB/s access speed which is plausible according to the Wikipedia article on SSD and this benchmarking website.

That means the SSD is faster and hashing is CPU constrained.

Additionally, there are faster SSDs and benchmarks usually don't consider only consecutive reads so that could widen the gap.


Might I suggest the "DES cipher internals in Excel" page by Nayuki? Because everything's in Excel, all the internal values are openly displayed.


SHA512withRSA - Looking for details about the Signature Algorithm

References

Related to your reference request: SHA512withRSA points to the RSA Signature Scheme with Appendix based on PKCS #1 v1.5 with SHA-512 hash function.

This means you’re looking for reference documentation describing RSA PKCS1 v1.5 (see: RFC2313) signatures with SHA512 (see: RFC6234) hash and X.509 encoding format.

Removing “overhead” from code

As for the part of your question on how to achieve the removal of overhead in your code: diving into that could quickly become off-topic for Crypto.SE and it would probably be more suitable for StackOverflow anyway. Nevertheless – since your question indicates you’re new to the reference documentations and RFCs describing SHA2, RSA, etc. – I would like to add my two cents to your code-modification idea…

Cryptographic implementations rarely contain or produce (what you call) “overhead”. Therefore, I would like to strongly discourage you from stripping or modifying any part of code that represents, interacts, or relates to cryptographical algorithms or schemes. Doing so has a high probability of introducing issues – which might range from simple software bugs, up to a dangerous situation where the removal of code is equal to the voiding (= removal) of cryptographic security. You surely don’t want the later to happen. Instead of fiddling with the code, you should simply rely a tested and well-vetted implementation. There are many of them out there, available in almost every programming language you could wish for.


Showing the decrypted sum of encrypted values

There is a recent line of work that does exactly this; it is called functional encryption for inner-product. It allows to encrypt a vector of integers (from some exponent space $\mathbb{Z}_p$) so that one can generate secret keys that do only allow to decrypt a given inner product between the components of any such encrypted vector.

There is a simple construction under DDH, and under LWE. The construction from the Paillier cryptosysem is way more involved and was presented at the CRYPTO conference in august this year.

For the DDH-based variant, the intuition is simple: encrypt your vector with different keys, but the same random coin each time (id est: $E((m_1, \cdots, m_n);r) = (g^r, h^r_1g^{m_1}, \cdots, h^r_ng^{m_n})$, where $g$ is a generator of some group where DDH is hard, and each $h_i$ is $g^{s_i}$ for some secret key $s_i$). The secret key to decrypt an inner product with $a_1, \cdots, a_n$ is just $\sum_i s_i a_i$.

Here is the original article: http://eprint.iacr.org/2015/017. If you want to look into the more advanced constructions, I suggest looking the papers that cite this one.

EDIT: I forgot to mention, the DDH-based instantiation has the same drawback that the additive variant of ElGamal it relies on, which is that a discrete logarithm must be performed on $g^{\sum_i a_i m_i}$ at the end, so it works only when $\sum_i a_im_i$ remains small (say, less than $2^{30}$). If the messages can be large, then the LWE-based or the Paillier-based instantiations must be used.


Is this problem still as hard as discrete logarithm (modified ElGamal)?

Yes, the system is easily breakable.  We have:

$$(g^r)^{k+s} / g^{rs} = g^{rk}$$

You don't list $g^r$ in your problem statement, however it is in the ciphertext, and so we can assume the attacker knows it.


Why are the random exponents so much bigger in the Socialist Millionaire protocol versus Diffie-Hellman key exchange?

For Diffie-Hellman, adequate security is achieved provided that:

we work modulo a prime $p$ big enough to resist discrete logarithm (1536 bits are sufficient);
the order of the subgroup generated by $g$ is a multiple of a big-enough prime integer $q$ ($q$ should have length $2n$ bits to achieve $2^n$ security);
the private exponents are randomly chosen in a big enough range ($2n$-bit exponents to reach $2^n$ security).

The first two conditions are necessary for the discrete logarithm to be hard. But having hard discrete logarithm is not necessarily sufficient for the security of the cryptographic algorithm which uses that group. Diffie-Hellman appears to be reasonably secure with the conditions above. However, other protocols require a bit more. A prime example is DSA. With DSA, you work in a subgroup of size $q$ (a prime integer) generated by a conventional value $g$ modulo a big prime $p$; whenever you sign, you select a random $k$ modulo $q$ (that's a "secret exponent"). $k$ must be chosen uniformly in the $[1...q-1)]$ range; simply choosing a "big enough" $k$ is not sufficient: any bias in the selection of $k$ can be exploited to rebuild the private key from the observation of several signatures (many signatures, if the bias is slight).

So your question is: is SMP more like Diffie-Hellman, i.e. tolerates that private exponents be chosen in a subrange, or more like DSA, for which uniform selection in the whole range is necessary ? Barring any explicit indication to the contrary, it is safer to assume that uniform selection in the whole range should be used. In particular, it seems to me that non-uniform selection may imply exploitable biases in the zero-knowledge proofs which are sent along the SMP values.


Can we always find a key to map a given plaintext block to a given ciphertext block in AES?

The answer is no, such a key need not exist.  Let the given plaintext/ciphertext pair be $P,C$ and let $n=2^{128}.$

How many permutations on $n$ points map $P$ to $C$? Clearly $(n-1)!.$
Thus, if we could uniformly sample all possible permutations, the probability that under a given permutation $P$ would map to $C$ is a tiny
$$
\frac{(n-1)!}{n!}=\frac{1}{n}.
$$

Since the AES keyspace also has size $n,$ the expected number of keys that would have this property is $n\times(1/n)=1,$ provided we assume AES perfectly samples the keyspace with respect to this arbitrary property $P\mapsto C.$  But there are no guarantees that it does so since it uses only 128 bits instead of $\log n!$ bits.


You are correct that using a different salt for each file will slow down encryption and decryption, in proportion to the number of files. But it is not useful to do so. An adversary is not helped if she knows that the salt is common to several files hashed with the same password (under the assumption that she can recognize a correct password with fair probability from one ciphertext, and cost dominated by PBKDF2). Both with common and different salt per file, the hard work for the attacker is finding the password; the cost of recomputing PBKDF2 for other files when salt is different will be comparably negligible.
Thus an option if to have the enciphering program generate the salt at random common to every files, and appropriate IV for each file (e.g. 48-bit file number, and 80-bit zeros; this is enough for $2^{48}$ files of $2^{84}$ bytes each, encrypted using AES-CTR); compute only one key using PBKDF2; and store salt and IV as header of each enciphered file. The deciphering program can cache the key in RAM for reuse when deciphering files with identical salt (it should not assume all files have identical salt, in case files separately enciphered are merged into the same directory).
When using other block-cipher operating modes such as CBC, CFB or OFB for enciphering multiple huge files, you may approach the limit of reasonable usage of one key. For this reason, or just for added peace of mind, you might want to have one key per file. This can be done while still amortizing the derivation of key from password over multiple files, by generating a common "slow" master key from password and master salt (e.g. random) for each encryption session, and a "fast" derived key from master key and secondary salt (e.g. file index) for each file, with both salts in the encrypted file's header. The "fast" derivation could be with PBKDF2 and a minimal iteration count c=1, or just one HMAC.
Also: you might want to consider scrypt instead of PBKDF2 (at least for the master key), for it provides better security for a given time overhead, as summarized in this table from the scrypt paper (2009):

Update (2020): state of the art has evolved. Bitcoin mining has shown that dedicated ASICs performing SHA-256 at high rate (220 TH/s) and efficiency (15 pJ/H) can become commercially available for few thousand US dollars. This makes it untenable to rely on PBKDF2-HMAC run on standard hardware for stretching of user-chosen passwords in high-security applications. Scrypt still stands strong, however the new best practice for password hashing is the winner of the password hashing competition, Argon2.


Question about IND-CPA with block cipher mode with random IV (CTR$ mutation)

It is not CPA secure, because we can exhibit an attack against the CPA security of your construction.
There are two key insights here:

The attacker has (limited) control over the input to the Permutation $E_k$.
$E_k(x) = E_k(x')$ if and only if $x = x'$, since $E_k$ is a deterministic Permutation.

The trick is now to find two messages $m_0,m_1$, such that $m_0$ will result in the same value being fed into $E_k$ twice, while $m_1$ will result in different values being fed into $E_k$.
The attack works as follows: The attacker $\mathcal{A}$ outputs messages¹ $$m_0 = 0^{2\ell-1} \Vert 1 \quad\text{and}\quad m_1 = 0^{2\ell}$$
and receives the challenge ciphertext $c^* = IV\Vert c_1\Vert c_2$. If $c_1=c_2$, $\mathcal{A}$ outputs $0$, otherwise it outputs $1$.
Now we need to analyse the success probability of $\mathcal{A}$. Let $m_b^i$ denote the $i$th block of message $m_b$. As we noted above, it holds that $E_k(x) = E_k(x')$ if and only if $x = x'$. Therefore,
$$c_1=c_2 \iff \langle IV +1\rangle \oplus m_b^1 = \langle IV +2\rangle \oplus m_b^2.$$
For $m_1$, we have that
$$\langle IV +1\rangle \oplus m_1^1 = \langle IV +1\rangle \oplus 0^\ell = \langle IV +1\rangle \neq \langle IV +2\rangle = \langle IV +2\rangle \oplus 0^\ell = \langle IV +2\rangle \oplus m_1^2$$
therefore, when given an encryption of $m_1$, $\mathcal{A}$ will always output $1$.
In the other case, for $m_0$ however, we have
$$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle \quad \text{and}\quad \langle IV +2\rangle \oplus m_0^2=\langle IV +2\rangle \oplus 0^{\ell-1}\Vert 1.$$
Now observe, that if the least significant bit² of $IV$ is $1$, then $IV+1$  and $IV+2$ will differ only in the least significant bit. I.e. $$\langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1.$$
It thus follows that if (and only if) the least significant bit² of $IV$ is $1$, then
$$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1 = \langle IV +2\rangle \oplus m_0^2.$$
Since $IV$ is chosen uniformly at random, the lsb of $IV$ is $1$ with probabilty $1/2$. Therefore, the attacker has an overall success probability of $$\frac{1}{2}\cdot\left(1+\frac{1}{2}\right) = \frac{3}{4},$$
which is clearly non-negligibly greater than $1/2$.

¹Note that I'm using $\ell$ to denote the block-length, since $k$ would be confusing, given that it's also the key.
²Assuming appropriate endianess. If my endianess above seems wrong to you, just flip the bitstring around.


I don't want to store passwords, can I use them as an encryption key for another field?

It kind of makes sense, but there are some hairy details.

To use a password as a key you need a password based key derivation function or PBKDF, not just any KDF. Otherwise the adversary can try and guess the password and try to decrypt anything you encrypted with it. Generally that would take just one additional block decrypt, so that's generally a fast operation. So you need a work factor (or, for specific PBKDF's, iteration count) to make it harder to guess the password. Just like when storing a password hash, for the same reason you will probably also want to a salt. The salt / random may also be required to stop replay attacks.

This does however mean that the user suddenly has to perform the work factor; generally password hashes are calculated server side. This might be an issue if the client has limited computing facilities - or battery life / heat dissipation issues, etc.. More importantly, if the attacker learns the key from your DB, then the attacker can simply skip the calculation altogether.

Generally we don't encrypt known / public data. It may be easy to slightly alter the data by adversaries, which in turn may result in surprising attacks. Generally we use a MAC such as HMAC over the data instead. That way you can verify if the key is correct by simply validating the MAC.

There are many other ways to verify passwords. For instance, you could have a look at PAKE protocols or SRP.

You haven't really indicated why simply storing a password hash is not sufficient either. Currently you are making your life more difficult without making your protocol more secure.


In the standard definition of security for public key encryption schemes there exists only one public key.
Therefore the decryption oracle will always decrypt with the secret key that corresponds to the public key given to the attacker. It does not matter how the $c_1$ in your question is computed, it can be computed using the real public key, a different public key or might even be random garbage. The decryption oracle doesn't care, it simply runs the decryption algorithm with the secret key produced earlier in the security game and the input provided by the attacker.
Whether this results in a valid decryption or not depends on the encryption scheme and is not part of the security definition.


Is it possible to fake any file's SHA256 checksum with Length extension attack? Is SHA256 completely insecure when file size is not also checked?

Bob compares the SHA256 checksum that he generated from fake ISO file to the checksum found on official linux distribution's home page. Because Bob's fake ISO checksum matches the official ISO checksum, Bob doesn't notice that he has downloaded fake ISO

I highlighted the incorrect assumption: the checksums wouldn't match.
What the length extension attack allows someone to do is, given the hash of an unknown message $M$, compute the hash of a message $M | pad | X$ (for a specific string $pad$ which depends on the length of $M$, and an arbitrary string $X$).
However, the hash of $M | pad | X$ will not (in general, that is, barring an extremely improbable coincidence) be the same as the hash of $M$.
If it were, that would count as a hash collision, hence disproving the collision resistance of SHA256.

Is this trivial to do?

It is believed to be infeasible  to make the hashes match.  Yes, the adversary could compute the hash of $Y = M | pad | X$, however because he knows what his image $Y$ is, he could compute its hash without any special properties of the hash function.


What is the purpose of Homomorphic encryption?

In addition to the other answers: A secure secret-key homomorphic encryption scheme can be used to create a public-key encryption scheme.

If we consider encryption to be control of read and write abilities on data, then it's easy to see how this is the case.

With normal secret-key encryption:

only the key holder(s) can create ciphertexts (write permissions)*
only the key holder(s) can decrypt ciphertexts (read permissions)

With normal public-key encryption:

anyone with the public key (which is anyone, as it is public) can create ciphertexts
only the private key holder can decrypt ciphertexts.

With homomorphic secret-key encryption:

the key holder can create ciphertexts
anyone can manipulate ciphertexts (another form of write permission)
only the key holder can decrypt ciphertexts

This overlaps with the above definition for public-key encryption. While someone without the secret key cannot create a ciphertext for a given plaintext directly, they can do so if they are given pre-existing ciphertexts with known plaintext by the key holder.

An example

Assume the existence of a secure, secret-key, partially homomorphic encryption algorithm that supports integer addition on ciphertexts.

For the sake of simplicity, we will also assume that noise levels and resultant corruption of plaintext are not an issue (this is a real issue that many homomorphic encryption schemes suffer from).

A private key is simply a secret key $d$ for the secret-key encryption algorithm.

The nature of which is unspecified in this example, it would depend on the concrete scheme being used whether $d$ is a scalar, vector, etc.

A public key $\mathbf{e}$ of is a vector of encryptions of $1$ of length $n$ created using the private key with the symmetric encryption algorithm.

The public key operation generates a vector $\mathbf{r}$ such that $$m = \sum_{i=0}^{n}r_i$$ (secret splitting of $m$ into $n$ shares) and computes $$c \leftarrow \mathbf{er}$$

The inner product of $\mathbf{e}$ and $\mathbf{r}$.

The private key operation applies the decryption procedure from the secret-key cryptosystem to $c$ to recover $$1 * r_0 + 1 * r_1 + 1 * r_2 + \dots + 1 * r_n$$

Which is of course simply equal to $$m = r_0 + r_1 + r_2 + \dots + r_n$$

There are other possible public-key operations, e.g. based on subset-sum problems and/or LWE.

* Only the user with the secret key can create meaningful ciphertexts; An arbitrary block of bits of correct size is a valid ciphertext, but picking such a block of bits arbitrarily is unlikely to yield a meaningful plaintext with overwhelming probability


Calculating random number in ECDSA based on private key and signature

This is immediate:
$$ k = s^{-1} (z + r \, d_a) \bmod n $$
where $z$ is the hash value of the message being signed.


If $H(X)$ and $H(Y)$ were not evaluated as a part of selecting $X$ and $Y$, then yes; the assumption of a random Oracle is that $H(Z)$ is an independent and uniformly distributed variable for every new (not previously submitted to the Oracle) value $Z$.

If this isn't the case, then this need not hold.  One obvious counterexample is:

$X := 1; Y := 2 \textit{ if H(1) < H(2)}\\ X := 2; Y :=1 \textit{ otherwise}$


Is it safe to generate ECDSA keys from the hash of the previous, over and over again?

This approach will work, but there's another approach I want you to suggest.

As for why it's secure (or better the ways to attack):

Break the elliptic curve discrete logarithm problem. If you can do this you can just grab the first address out of your addresses, solve for the private key and derive all subsequent ones. This is generally considered infeasible.
Brute-force your passphrase. This is impossible as you describe it as "very long and secure".

Now for the alternative approach:

Don't use iterated hashing on your password for the ECDSA key derival. Use HKDF-extract on your password and then derive each indexed key using HKDF-expand which will allow you to supply context-information. You could simply use "1", "2","3",... as context info here. Use the derived values as ECDSA private keys.

The advantages are:

Independent keys. Compromise of one private key doesn't imply compromise of all subsequent private keys, because they are all independent.
Higher speed. If you only want to access your account number 500, you'd have to iterate your hash function 500 times (which may take a moment). With HKDF you get this at a few HMAC calls independently of the index.
More security. If you use HKDF you don't need to store / buffer 499 intermediate private keys on your machine, whereas with iterated hashing you'd have to (although you still have to store the master password).


What is the probability of a SHA-512 hash containing both digits (0-9) and alphabets (a-f) all the time?

A cryptographic hash outputs a string of bits.

Whether or not it appears as digits/alphabet letters is a matter of how the output is encoded and presented to the user.

You could easily ensure that nothing but digits/alphabet letters in what is presented to a user by performing base conversion on the output, from a base-2 system (binary) using the symbols $0$, $1$ to a base-$n$ system using arbitrary symbols.

For example, If you encode the output in the hexadecimal number base, a user will see only hexadecimal values (0-9 + A-F).

If you wanted to operate under the assumption of a given number base, you would do some math to quantify the probability of a given subset of symbols occurring in the output - but you have to pick a specific encoding first before you can do so, as the choice of encoding will drastically chance the probability.

For example, consider an encoding that uses (0-9 + A-Z + !) - The probability of sha512 outputting a string with only the symbols (0-9 + A-Z) is relatively high. While in the opposite case, if the encoding only uses (! + ?), the probability is non-existent.


Asymmetric format preserving encryption?

Yes, in fact there is at least one length-preserving asymmetric encryption scheme. It's deterministic, though, so there are some security tradeoffs that come with it. It's described in the paper "Deterministic and Efficiently Searchable Encryption" by Boldyreva et al. Look for "RSA-DOAEP".


Why is DES secure against differential cryptanalysis

It's mainly due to the use of multiple rounds and the presence of the various permutation and expansion mappings that bring the overall maximal differential probability to a very low level for key recovery.

This then leads to unrealistic requirements for chosen plaintext/ciphertext pairs encrypted under the same key, in ECB mode.

And the presence of different sboxes complicates things a bit further. Under current technology, or even for the last 20 years, a simple brute force key search with a small amount of plaintext ciphertext pairs is much simpler and easier.


Is the simulation-based proof difficult and needed?

The essence of semi-honest security is that "the protocol transcript leaks no more than the function output." How do you propose to formally prove this without a simulator? After you become comfortable with simulators, it becomes obvious that they are the correct way to formalize this idea.

Yes, simulators also do a good job of formalizing properties unique to the malicious setting (particularly input extraction). But that is not an argument against simulators for semi-honest definitions. If anything it reinforces the fact that simulators are the correct paradigm to formalize MPC security in all scenarios!

Yes, security proofs are much harder in the malicious setting. This is to be expected since the adversary has much more power.

Overall, it's not really clear what you are suggesting. First you say that a simulator in semi-honest is "often .. trivial" but then you say "the proof makes paper difficult to read". Simulation-based security is there because it is the most elegant way to formalize the relevant security concepts; it's not there to make things difficult for no reason.


Ways to protect flash player against MITM diffie hellman

The usual solution for the Man-in-the-Middle problem of Diffie-Hellman is to combine it with a public-key authentication solution.

This could either work by including the server's public Diffie-Hellman key (which then must be a long-term key, not a short-term or even session key – this way you lose your forward-security) in the client, or including a signature key (DSA, RSA, ECDSA) with the client, where the server uses the corresponding private key to sign everything what was exchanged. (All those ways of authentication are used in SSL/TLS ciphersuites, by the way.)

Of course, this then poses the problem how the client (i.e. your flash application) comes securely to the browser in the existance of a MitM – so you'll have to also use some authentication solution on the transfer of this, using another public key, maybe certified by some key the users already know (and trust).

By then, you can just use SSL/TLS for the whole communication, both for delivering your flash client as well as to receive the secret data from the server.


The exact details depend on the logic family but basically The difference is that the charge representing those "1" bits need to be discarded somehow. This is done by switching the output to ground, 1^0 is 1 so no charge need to go away but 1^1 is zero meaning at least two gates get discharged to ground slightly raising its voltage due to the non zero resistance in the ground return path.

Though, this really depends on the logic Family, the effect of charging the output gate lowering vcc may be dominant in some like you say. But in most any mos family, some assymetry will be noticed. ECL is notably immune due to steering currents that always flow not charging capacitors.


A "block" is the amount of bits your block cipher operates on (There are other kinds of ciphers, see below.)

Think of a Caesar cipher, it replaces letters in words. For example with key 13 it replaces as follows:

A -> N

and

HELLO ALICE -> URYYB NYVPR

Note that the same letter will always be replaced by the same letter. So it operates on one letter at a time.

A block cipher operates not on individual bits 0/1 but on blocks of them so if your block size was four your cipher might do the following replacement:

0100 -> 1110

(Of course what exactly is replaced with what depends on the key.)

Essentially, a block cipher behaves like a permutation of the blocks. Which permutation exactly, is determined by the key. So it is a bijective map $\{0,1\}^{blocksize} \rightarrow \{0,1\}^{blocksize}$.

It is not strictly required for a cipher to have a block size. A stream cipher for example operates on individual bits.

Note, that since a block cipher is a permutation it will replace the same input-block with the same output-block just like the Caesar cipher always replaces the same input-letter with the same output-letter. Because this makes for bad cryptography block ciphers are used in different modes of operation.


Is the Keccak family of sponge constructions the same as SHA-3?

SHA-3 is defined by FIPS 202.
If you go to the team Keccak website you will read the following.

Keccak is a versatile cryptographic function. Best known as a hash function, it nevertheless can also be used for authentication, (authenticated) encryption and pseudo-random number generation. Its structure is the extremely simple sponge construction and internally it uses the innovative Keccak-f cryptographic permutation.
After its selection as the winner of the SHA-3 competition, Keccak has been standardized in 3GPP TS 35.231 for mobile telephony (TUAK), and in NIST standards FIPS 202 and SP 800-185. Consequently, it has received extensive public scrutiny and third-party cryptanalysis.
[source]

Thus Keccak[1600] is the exact same as NIST standardized in SHA-3.


Then I found out that you always pad at least 1 byte when doing PKCS#7 padding (with byte 01 if length of input is divisible by the desired amount). Is this understanding correct?

Actually, if the input was already a multiple of 16 bytes, the padding would consist of 16 10 (hex) bytes, which you would append to the end of the input.  Then, the padded input will then be a multiple of 16 bytes (which, with this padding method, is always the case, even if the original input was an odd length).

If so, should I divide my input into blocks with size of 15 bytes (with 16th byte being the pad byte)?

No; you need to add padding only to the end of the message - there is no reason (or permission, as far as PKCS#7 is concerned) to add padding to the intermediate blocks.


Prove that function G is not a pseudo-random generator

You can construct a discriminator which applies G' on the first half of the output in question and compares it to the second half. If they match claim it came from G'' otherwise call it random.

This discriminator has no false negatives and a false positive rate of $2^{-n-2}$.

The ability to build an efficient discriminator with non negligible success probability proves G'' is not pseudo random.


The best generic attack against a PRG (i.e. an attack that does not use any internal structure of a construction and hence works for any PRG) is exhaustive search for a seed. I think this was not done yet but it is very likely that the optimality of Grover's algorithm carries over to this setting. This would mean that for $n$ bit seeds, the best attack requires $O(2^{n/2})$ evaluations of the PRG.

For PRGs build from hash functions and block ciphers this should be the case also for specific, non-generic attacks (assuming the used hash / BC is post-quantum). Of course, if you use a number theory based PRG like Blum-Blum-Shub Shor's algorithm kicks in.


What is the translation for "hash" in french?

In French, cryptographic hash function translates to fonction de hachage cryptographique.


What does K stand for in frequency analysis

It probably refers to the Index of coincidence, or more accurately the un-normalized index of coincidence, referred to in the Wikipedia article as "kappa-plaintext".


Affine Cipher Keys that map plaintext to a given ciphertext

Assuming plaintext and ciphertext alphabets are $U=\{0,\ldots,25\}$, taken to be the ring of integers modulo 26, and the keyspace is $U^2$ with $$(a,b)\in U^2,$$ it is clear that for plaintext $x=2t$ corresponding to even numbers,  $(a,b)$ and $(a+13,b)$ give the same $y$ violating the invertibility of the encryption. Moreover, if $b=0$ $a$ can't be zero for the same reason.

So we allow all $b$ but only $12$ nonzero $a$'s and can choose either $a$ or $a+13$ as $a$ ranges over $\{1,2,\ldots,12\}$.


Cipher Block chaining but with encrypting the plain text first then xor with IV

It is a really bad idea to have $$C_i = C_{i-1} \oplus E(P_i).$$ The ciphertext leaks a deterministic function of each plaintext block, as  $$C_i \oplus C_{i-1}  =E(P_i).$$ Now an eavesdropper can easily tell whether $P_i = P_j$ by checking whether $$C_{i-1} \oplus C_i = C_{j-1} \oplus C_j.$$


Is this a better involution S-Box for the Anubis cipher?

Assuming your differential uniformity and non-linearity figures are correct, then yes, your s-box is slightly stronger against basic differential and linear cryptanalysis.  Although Anubis already was essentially immune to basic differential and linear cryptanalysis.  However your s-box would need to be evaluated against other forms of cryptanalysis (e.g. interpolation, invariant subspace, etc) in order to determine if it was "better" in a more general sense.  It may also be less efficient in terms of hardware implementation than the current Anubis s-box (to invoke another, no-less crucial sense of "better").

Note: The AES s-box is affine-equivalent to an involution (as will be obvious if you think about the multiplicative inversion function), and has a higher non-linearity and lower differential uniformity.  Non-linearity and differential uniformity are the same for all affine-equivalent permutations.  So that should help address your question about the maximum non-linearity of an involution.


SHA-1 collisions - what about practical attacks?

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509.

I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised that toolchain), and enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to

$2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
$2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
$2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

Suppose an executable file format consisting of

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8
: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-4096 signature of the SHA-1 hash of 1-2-3-4-5.

The attacker writes or adapts bootstrap code 3 so that the executable is

: 4-byte magic value 0x4D6F4546 (My own Executable Format)
: 4-byte length of bootstrap code, allowing to locate section 4
: bootstrap code with entry point at offset 8

: code that gets the value of $k$ from section 3.4, then jumps to section 3.6 or 3.5 according to if $k^\text{th}$ bit of section 3.3 is 0 or 1
: filler data so that 3.3 is aligned to a 64-byte boundary
: 128-byte data block
: 4-byte $k<1024$ such that the two values of section 3.3 differ in the $k^\text{th}$ bit
: code performing whatever the attacker wants to perform
: code performing whatever the bootstrap is supposed to perform

: 4-byte length of section 5, allowing to locate the signature
: (anything)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3 / 4 / 5.

The adversary needs to

know 1 / 2 / 3.1 / 3.2 when starting the attack
apply enough rounds of SHA-1 to deduce the 160-bit SHA-1 state after hashing 1 / 2 / 3.1 / 3.2, giving the 160-bit initialization value of the SHA-1 variant attacked
perform one of the costly attack at the beginning of this section
having found two 128-byte colliding data blocks, determine a bit index $k$ where they differ, and label the colliding blocks A and B according to if $k^\text{th}$ bit of the block is 0 or 1
construct two version 3A and 3B of the bootstrap code 3, differing only by containing block A or B in section 3.3; notice that 3.5 and 3.6 can be changed without performing the costly attack again;
plant version 3A of the boostrap, which does as it is supposed to perform
let an unsuspecting developer create an application with bootstrap 3A, and getting it signed;
obtain that signed original;
create a forgery by changing section 3.3 to block B, so that version 3B of the bootstrap is in place;
arrange for the forgery to be used on target machines, using the reputation of the application developer.

The forgery pass signature verification because the SHA-1 hash of 1 / 2 / 3 / 4 / 5 is unchanged, but when launched executes the code of section 3.5 performing whatever the attacker wants to perform, when the signed original did not.

Further, it is possible to encipher the code of section 3.5 using the block of section 3.4 as key, making it impossible to analyze the exact behavior of bootstrap 3B from the knowledge of bootstrap 3A. And code of section 3.1 can be of the form decipher-then-execute, so that the intention is less apparent.

Similar tricks can be pulled with some "data" format that are executables in disguise; e.g. that trick has been pulled with postcript and MD5.

Back to certificates in X.509-like format: consider a simplified certificate format with

: identity of the certificate holder, in ASCII on 44 bytes right padded with spaces
: public modulus $N$ of a 2048-bit RSA key, on 256 bytes (big-endian)
: (other certificate data, including public exponent, attributes..)
: PKCS#1v2 RSA-2048 signature using SHA-1 hash of 1 / 2 / 3

and one of two relevant attack models

An attacker legitimately purchases from an honest certification authority a certificate with her identity Alice and a public modulus $N_a$, modify it into a certificate with the identity of Bob and public modulus $N_b$, and holds the private keys $d_a$ and $d_b$ corresponding to $N_a$ and $N_b$ ($d_a$ is necessary to obtain the certificate; $d_b$ allows Alice to impersonate Bob);
A rogue certification authority knowingly supplies to Alice a certificate with the identity of Bob and a public modulus $N$ with factorization known to Alice (and perhaps having relatively easily found prime factors, making it more plausible that the above attack occurred), allowing Alice to impersonate Bob; and if word ever leaks that Alice impersonated Bob using a certificate issued by this authority, pretends that it has fallen to the above attack.

Note: something close to one of the above things has actually occurred with MD5-based X.509 certificates, per the evidence given here. This had been publicly described circa 2009.

In order to actually perform the attack, Alice

searches one SHA-1 collision between two 64-byte data blocks $M_a=I_a\|J_a$ and $M_b=I_b\|J_b$ with the first 44 bytes $I_a$ and $I_b$ corresponding to Alice's and Bob's identity; and 20 other bytes $J_a$ and $J_b$ arbitrary except for having the first bit set

the brute force Parallel Collision Search referenced earlier allows that with expected effort less than $2^{82}$ hashes: the function iterated can map a 160-bit value to a 64-byte block with either Alice's or Bob's identity in $I$ according to one bit; and map the other 159 bits to the unconstrained bits of $J$; when a collision is found, there is a 50% chance that it will be between a 64-byte block with different identities, thus usable;
it is conceivable to adapt some specialized methods exploiting weaknesses in SHA-1's compression function (in particular Marc Steven's publication referenced earlier describes a chosen-prefix collision attacks with expected effort about $2^{77.1}$ hashes);

finds a 236-byte value $K$ so that $N_a=J_a\|K$ and $N_b=J_b\|K$ (big-endian) are 2048-bit integers with known factorization, squarefree, and odd (and if necessary, with $N_a$ passing whatever other test the certification authority may perform, and $N_b$ passing whatever other test the entity to which Alice wants to represent herself as Bob may perform); given our message format, it is even feasible (though not required) to ensure that both $N_a$ and $N_b$ have exactly two large primes factors: we can choose $p_a$ and $p_b$ arbitrary primes about 900 bits, then systematically construct and explore $K$ such that $p_a$ divides $N_a$ and $p_b$ divides $N_b$, until both $N_a/p_a$ and $N_b/p_b$ are primes.
finds a public exponent $e$ acceptable for both $N_a$ and $N_b$ (there's a fair chance that the common $e=2^{16}+1$ will do) and compute private exponents per RSA as defined in PKCS#1, as $d_a=e^{-1}\bmod\lambda(N_a)$ and $d_b=e^{-1}\bmod\lambda(N_b)$, which is easy knowing the factorization of $N_a$ and $N_b$;
legitimately obtain the certificate with identity $I_a$, public modulus $N_a$, public exponent $e$ (which typically requires signing the certification request using $d_a$);
change $I_a$ to $I_b$ and $N_a$ to $N_b$ in the certificate (this will not change the SHA-1 hash, thus the forgery is a certificate that pass the verification procedure);
impersonate Bob using the forged certificate and $d_b$.

A countermeasure would be that certification services enforce the insertion of some unpredictable data in the beginning of certified data.


Does the Paillier system remain secure if it is used to encrypt only binary values, i.e. {0, 1}?

No, there are no security compromises; the Pallier system remains secure.  Both messages are in the supported message space and as Paillier encryption provides IND-CPA security you are safe when doing this.


Derive both MAC and AES keys from same PBKDF2?

From a security point of view, deriving lots of key material using PBKDF2 is ok.

From a practical point of view, deriving lots of key material using PBKDF2 is inefficient (in the sense that to generate $n$ blocks and increase the adversary's work by $t$, you do work $nt$, instead of $n+t$).

A more practical solution uses PBKDF2 to generate a short string and a suitable generator (probably HMAC-based) to produce lots of key material. Typically:
$$k_0 \leftarrow PBKDF2(pw, \dots)$$
$$\text{key material} \leftarrow HMAC(k_0, 1) || HMAC(k_0, 2) || HMAC(k_0, 3) || ...$$


Proving a function is a one way function

The easiest way to construct a probabilistic $A$ is simply, given $z$:

Select a random $w$
Compute $A'(z || f(w))$.
If $A'$ succeeds, then it'll evaluate to an $(x, y)$ pair with $z = f(x)$ and $f(w) = f(x \oplus y)$.
Discard $y$, and return $x$ as $A(z)$.

We select a random $f(w)$, rather than just inserting another copy of $z$, because it is possible that $A'$ would always fail on an input of the form $(z || z)$.  As I have written, if $A'$ succeeds on a nontrivial fraction of its inputs, then $A$ will succeed on the same nontrivial fraction of its inputs.


As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently:

The idea is to produce $n$ key pairs $(X_i,Y_i)$ of a one-time signature scheme and then to take the hash values $g(Y_i)$ of the public keys $Y_i$ (where $g:\{0,1\}^*\rightarrow \{0,1\}^n$ is a cryptographic hash function as described in your reference) and to assign the hash values $g(Y_i)$ to the leaves of a complete binary tree with $n$ leaves.

Then, you recursively compute up the hash tree (by computing hash values of inner nodes as the hash value of the concatenation of the child nodes) and finally as root hash you obtain your "public key" which is then given to a receiver. Let's call this public key $PK$ and observe that this is a "virtual" public key as it is not directly used for signature verification of the one-time signature scheme (I will come back to that soon). The private key is $(X_1,\ldots,X_n)$, i.e., the sequence of signing keys of the one-time signature scheme.

Then, this public key $PK$ allows the verification of $n$ one-time signatures. Each of these one-time signatures is produced using the private signing key $X_i$ of the one-time signature scheme.

Now, the basic idea is that you use signing key $X_i$ for the $i$'th signature and the $i$'th signature for message $m_i$ is composed of:

the signature $\sigma_i$ obtained by signing $m_i$ with the signing algorithm of the chosen one-time signature scheme and signing key $X_i$.
the authentication path $A_i$ in the hash tree for the leave $i$ with label $g(Y_i)$. This path consists of all the siblings on the unique path from the leaf $g(Y_i)$ to the root. This allows you given the public key $Y_i$ required to verify the one-time signature on $m_i$, to recompute the root hash of the hash tree (which is the public key $PK$) and compare it to the public key $PK$ which you received.

A signature $s$ for a message $m_i$ is then $s=(i,\sigma_i,Y_i,A_i)$. Note that when given $(s,m_i)$ and being in possession of $PK$, for verifiying one checks whether:

$\sigma_i$ is a valid one-time signature for $m_i$ under public key $Y_i$
and the recomputation of the hash tree using the hashed public key $g(Y_i)$ (by hasing the public key $Y_i$ from the signature $s$) and the authentication path $A_i$ results in a root hash that is equal to $PK$.

I hope this answers your question and you see that there are no trapdoors involved with $g$ and $Y_i$. Essentially, the hash tree is used to aggregate $n$ public keys of a one-time signature scheme into a single "virtual" public key $PK$. Thus, this public key $PK$ allows to verify $n$ signatures. How the values $X_i$ and $Y_i$ are related depends on the used one-time signature scheme, but has nothing to do with the hash tree.


Is this API for ECDSA signature verification consistent with NIST test vectors?

Public keys in this system are very sparse: for any $x$ value there are at most two possible $y$ values satisfying $y^2 = x^3 + ax + b$ where $a$ and $b$ are the curve parameters, since the equation is quadratic in $y$.  (And $x^3 + ax + b$ has a square root at all only for some values of $x$; by Hasse's theorem, the number of points on the curve can't be very far from the number of elements in the coordinate field, so only about half of the possible $x$ values work.)

The signature API you're using presumably deals only in compressed public keys, which have maybe some formatting metadata and likely a single bit determining $y$ in one byte, together with 32 bytes to determine $x$.  For example, in the ANSI X9.62 format, the first byte is 0x02 for an even $y$ value, or 0x03 for an odd $y$ value; then the remaining 32 bytes encode $x$.


I'm reading the question as:

Prover knows a message (thus its SHA-256 hash, and message length), and position+length of a substring (thus the substring).
Verifier knows the hash, the substring and its position (thus length), and message length.

Prover should demonstrate knowledge of a message with such SHA-256 hash and length and with such substring at such position, without revealing more information about such message.

This is possible: we define a variant of SHA-256 with fixed message length and fixed substring at fixed position. The problem then reduces to demonstrating knowledge of input of that hash to a verifier knowing the hash, which is covered in this question.

I do not know exactly how much info must be exchanged between prover and verifier.

A concrete implementation is described by Irene Giacomelli, Jesper Madsen, Claudio Orlandi, ZKBoo: Faster Zero-Knowledge for Boolean Circuits, in proceedings of SEC'2016.


I don't think there is an existing library that can satisfy your needs.
Homomorphic encryption is powerful and requires lots of computations. However, in your case which allows user-defined keywords, I suggest you to take a look at Searchable Encryption.
Searchable Encryption is the algorithm that should be of interest. It allows cloud server to search 'blindly' on client's encrypted data, based on a 'trapdoor' - a token that contains keywords to be searched for - sent by the client. Of course, client must also encrypt the keywords along the encrypted data before uploading them, which will surely increase the overhead. For 'blindly' it means the cloud server doesn't acquire any unnecessary knowledge about the searched keywords and the encrypted data, during the entire query process.
Some of the searchable encryption algorithms are based on pairing-based cryptography. In that case, you can build your application based on PBC library.


Can you explain to me how permuted congruential generator XSL-RR-RR works?

I have read a bit about C syntax and I seem to understand what this generator does.

count = (int)(x >> 122)

>> is the right bitshift operator, shifting all the bits to the right a specified number. So initial number $x$ is shifted by $122$ bits. It means count is number consist of first $6$ most signifficant bits of $x$. Type of this data is int, because it could be every $0$-bit, $1$-bit, $2$-bit, $4$-bit, $5$-bit, $6$-bit number.

low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)

^ is just XOR operation. After xoring we can get every $128$-bit number, that's why there is introduced type uint64_t. It means we have to cut our result to first $64$ least signifficant bits. Rotr64 rotates the bits $x$ to the right by $n$ places around a $64$-bit boundary, which means we rotate (uint64_t)(x ^ (x >> 64) by count places.

high64 = rotr64((uint64_t)(x >> 64), low64 & 63)

Here we have the same operations like above except & which is the logical AND operator.

return (uint128_t)high64 << 64 | low64

In the end we get $128$-bit number (uint128_t). high64 bits are shifting on most signifficant bits positions and | is the logical OR operator. All $64$ least signifficant bits after << 64 will be equal to $0$. So OR operator just copy all $1$ and $0$ of low64 to $64$ least signifficant bits in our final $128$-bit number.
And $x$ is just number taken from typical linear congruential generator modulo $2^{n}$. Author specified in the documentation two multipliers and increments, which we can use:
$m=2549297995355413924$, $i=4865540595714422341$
and
$m=6364136223846793005$, $i=1442695040888963407$


UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield?

The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the polynomial of your example, $F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − 9x_2x_4 − 2x_3x_4+3x_0x_5+5x_1x_5 + 14x_2x_5 − 11x_3x_5$. Using the vector notation $\mathbf{x}^\mathsf{T} = (x_0, x_1, \ldots, x_5)$ we can write this polynomial as the following product:
$$ F_0(\mathbf{x}) = \mathbf{x}^\mathsf{T} \left( \begin{matrix}
1 & -4 & 8 & -2 & 7 & 3 \\
0 & -4 & 0 & -1 & -11 & 5 \\
0 & 0 & 0 & 9 & -9 & 14 \\
0 & 0 & 0 & 12 & -2 & -11 \\
0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{matrix} \right) \mathbf{x} \enspace .$$
The coefficients in the matrix are the same as in the sum-of-terms representation. Note that in this matrix representation, the bottom-right block consists of zeros; this reflects the fact that oil-times-oil terms have coefficient zero. Also note that this matrix is not unique: whenever $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T} M_{F_i} \mathbf{x}$ then for any skew-symmetric matrix $A$ (i.e. such that $A^\mathsf{T} = -A$) you can also write $F_i(\mathbf{x}) = \mathbf{x}^\mathsf{T}(M_{F_i}+A)\mathbf{x}$. In particular, this means that (assuming odd characteristic) it is always possible to choose the central matrix to be symmetric by computing $\frac{1}{2}(M_{F_i}+M_{F_i}^\mathsf{T})$.

The secret linear transform $\mathcal{T}$ can also be represented in two ways. You give the matrix representation
$$ T = \left( \begin{matrix}
18 & 23 & 14 & 1 & 6 & 21 \\
24 & 3 & 3 & 0 & 2 & 0 \\
17 & 25 & 2 & 16 & 23 & 8 \\
8 & 21 & 16& 5 & 1 & 9 \\
14 & 28 & 8 & 17 & 12 & 12 \\
6 & 24 & 18 & 19 & 3 & 1
\end{matrix} \right) \enspace ,$$
in which case $\mathcal{T}(\mathbf{x}) = T\mathbf{x}$. You could also have chosen the list of polynomials representation, in which case there are 6 polynomials, $\mathcal{T}_0$ throught $\mathcal{T}_5$. For illustration, the first polynomial is given by $\mathcal{T}_0(x_0, x_1, x_2, x_3, x_4, x_5) = 18 x_0 + 23  x_1 + 14 x_2 + 1 x_3 + 6 x_4 + 21 x_5$.

To compute the composition $F \circ \mathcal{T}$ you must first choose a representation. In the polynomial representation we have $F \circ \mathcal{T} (\mathbf{x}) = F(\mathcal{T}(\mathbf{x})) = F(\mathcal{T}_0(\mathbf{x}), \mathcal{T}_1(\mathbf{x}), \ldots, \mathcal{T}_5(\mathbf{x}))$. So you can compute $F \circ \mathcal{T}$ by starting with a copy of $F$ and then substituting every occurrence of $x_i$ with $\mathcal{T}(\mathbf{x}) = \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5)$. But make sure to keep track of which occurrences of $x_i$ appear as a result of the substitution, because they obviously shouldn't be substituted twice.

In the matrix representation, we have $F_i \circ \mathcal{T} (\mathbf{x}) = \mathcal{T}(\mathbf{x})^\mathsf{T} M_{F_i} \mathcal{T}(\mathbf{x}) = (T\mathbf{x})^\mathsf{T} M_{F_i} (T \mathbf{x}) = \mathbf{x}^\mathsf{T} (T^\mathsf{T} M_{F_i} T) \mathbf{x}$. So a matrix representation $M_{F_i \circ \mathcal{T}}$ of the composition can be computed just by sandwiching $M_{F_i}$ between $T^\mathsf{T}$ and $T$, i.e., $M_{F_i \circ \mathcal{T}} = T^\mathsf{T} M_{F_i} T$.

To complete the example you started, let's assume we're working modulo 31 (because otherwise the numbers get quite large). Then we have
$$ M_{F_0 \circ \mathcal{T}} \cong T^\mathsf{T} M_{F_i} T = \left( \begin{matrix}
6 & 25 & 19 & 19 & 3 & 26 \\
22 & 29 & 3 & 29 & 28 & 2 \\
8 & 15 & 12 & 18 & 6 & 7 \\
28 & 1 & 24 & 17 & 4 & 1 \\
6 & 21 & 18 & 5 & 30 & 23 \\
11 & 23 & 8 & 15 & 5 & 5
\end{matrix}\right) \cong \left( \begin{matrix}
6 & 8 & 29 & 8 & 20 & 3 \\
8 & 29 & 9 & 15 & 9 & 28 \\
29 & 19 & 12 & 21 & 12 & 23 \\
8 & 15 & 21 & 17 & 20 & 8 \\
20 & 9 & 12 & 20 & 30 & 14 \\
3 & 28 & 23 & 8 & 14 & 5
\end{matrix}\right) \cong \left( \begin{matrix}
6 & 16 & 27 & 16 & 9 & 6 \\
0 & 29 & 18 & 30 & 18 & 25 \\
0 & 0 & 12 & 11 & 24 & 15 \\
0 & 0 & 0 & 17 & 9 & 16 \\
0 & 0 & 0 & 0 & 30 & 28 \\
0 & 0 & 0 & 0 & 0 & 5
\end{matrix}\right) \enspace .$$
Here the congruence sign ($\cong$) indicates that the matrices represent the same quadratic form, i.e., up to addition of skew-symmetric matrices. In other words, after sandwiching them between $\mathbf{x}^\mathsf{T}$ and $\mathbf{x}$ they will result in the same polynomial. From the last upper triangular matrix we can read out the representation of the polynomial as a sum of terms, namely
$$ F_0 \circ \mathcal{T}(x_0, x_1, x_2, x_3, x_4, x_5) = 6x_0^2 + 16x_0x_1 + 27x_0x_2 + 16x_0x_3 + 9x_0x_4 + 6x_0x_5 + 29x_1^2 + 18x_1x_2 + 30x_1x_3 + 18 x_1x_4 + 25x_1x_5 + 12x_2^2 + 11x_2x_3 + 24x_2x_4 + 15x_2x_5 + 17x_3^2 + 9x_3x_4 + 16x_3x_5 + 30x_4^2 + 28x_4x_5 + 5x_5^2 \enspace .$$
This should be the same result as obtained through the substitution method applied to the polynomial representations.

One more thing: it is a good idea to avoid mixing homogeneous quadratic polynomials (i.e., without linear or constant terms) with affine transforms (i.e., with constant terms) -- or vice versa. In other words, whenever your secret polynomials are homogeneous, your secret transforms should be linear; whenever they are inhomogeneous, they should be affine. This guarantees that the public polynomials are (in)homogeneous whenever the secret ones are.


Backdoor Designer Key Recovery in LowMC-M

This would be done by a last round attack. The attacker would collect a crib of known pairs of inputs that differ by the plaintext difference (01010001101011 in your example). They would then run through $2^{16}$ guesses for the last round key, for each guess they would be able calculate the difference between each pair in round $r-1$ (by running just one round of the decryption process) and look for instances of the target difference (0111101010100100 in your case). In cases where they had guessed incorrectly, the target difference would not show up (or perhaps once); in the case of a correct guess the target would show up repeatedly.
Once the last round key is known, this drastically cuts down the number of main keys that could have produced it and (depending on key schedule) the main keys that are possible can then be exhausted.


Is there a standard method to compare hardware-implemented ciphers?

Because of how many ways there are to implement a hardware design there is not a specific comparison protocol that I am aware of. The main comparison points are power, area, and throughput, and comparisons are generally done on the same process, 32nm GF SOI for example. With a given process, area can be measured in GE or mm$^2$.

The algorithm itself will usually be the limiting factor when it comes to clock speed, and this may not be an issue if the throughput is still good. Unrolling loops uses more area but can increase throughput dramatically. Constants like those in SHA2 use a large amount of area, wheras those in SHA-3 use very little.

An implementation can be tuned to be better at a specific trait, such as power usage or speed, or tuned to have a good combination of two of them at the expense of another. Throughput/area or throughput/watt then become the usual target for a given implementation.

    Area          Power         Throughput
A   1mm^2         10mw          1.00Mb/s
B   1mm^2         30mw          2.45Mb/s

C   3mm^2         10mw          2.45Mb/s
D   3mm^2         30mw          6.00Mb/s
E   3mm^2         90mw          14.7Mb/s

F   6mm^2         90mw          44.1Mb/s

Each implementation has an advantage and a cost. D has a 100% increase in throughput/area and throughput/watt over A, but at triple the area. B and C have the same throughput, but one uses less area and the other less power. For a given area, triple the power budget gives a 2.45X increase in throughput. Because the 3mm area implementation is able to radiate more heat thanks to increased surface area, it can be pushed beyond the power limits of the 1mm area implementation. Despite using 1/3 the area and 1/9 the power, A is only 14.7 times slower than E. F is 3X faster than E at the same power, with only double the area used.

So how do you compare them? Which one is the best? The high area implementation obviously has the best throughput, and the best throughput/watt, but you may not have the area to spare, or the power. Would one consider A more efficient than E or the other way around? E has 63% better throughput/watt than A, but at the same wattage A has 22% better throughput/area.

In the end the a good comparison can only be made by keeping the process a constant, then deciding which implementation is better or more efficient based on the requirements of the final product.


Questions about future and session key generation in DUKPT process

I don't know where you're seeing session keys. DUKPT is designed to do transactions, not sessions, hence the name. If some application is using them for sessions that is probably a bad idea. (added for edit) Okay, that website is amazing: I think every sentence of the text has an error or ambiguity, yet the code is correct -- at least for the simpler 'host' algorithm; it doesn't implement the device-side future-key algorithm. DUKPT is not intended to and should not be used for session keys.

For the device-side algorithm, the 21 so-called Future Keys are used in a hierarchical fashion controlled by a 21-bit counter (which is the low bits of the KSN) to derive a sequence of keys; they are not directly used as the key sequence. Because high Hamming weights are skipped, the key sequence for a device (starting from an Initial KSN and corresponding Initial Device or TRSM Key, Device or TRSM Injection Key, or various other names) is $2^{20}-1$ or 1048575 keys -- slightly over a million.

(expanded in detail since I can't seem to convey that the 21 future key registers are not 'used up' by 21 transactions; revised to more accurate 'derive' instead of 'generate')

AN EXAMPLE OF THE FUTURE-KEY ALGORITHM

In either host or device (future-key) mode the Initial Key (two 64-bit halves) for a device is created by twokey-3DES encrypting the high 8 bytes of the device's IKSN with the BDK for the left, and with the BDK with each half XORed with C0C0C0C0_00000000 hex for the right.

At device injection this Initial Key is used to derive the keys for each KSN whose counter value is a power of two, and store them in the future-key registers: the key for IKSN+$2^0$=IKSN+1 in FK21, for IKSN+$2^1$=IKSN+2 in FK20, for IKSN+$2^2$=IKSN+4 in FK19 and so on to IKSN+$2^{20}$=IKSN+1048576 in FK1. Since all keys derived by a device are for KSNs beginning with the device's IKSN, I will omit that part from now on and just say the counter value.

For transaction 1, the device (TRSM) finds the lowest 'on' bit in the counter which is $2^0$=1 and uses the key in the corresponding FK register (FK21) which was set above to contain the key for counter 1. Actually the key is first modified to a 'variant' key with two octets complemented depending on the type of crypto done in the transaction. After use FK21 is logically erased.

For transaction 2, the lowest 'on' bit is $2^1$=2 so it uses FK20 similarly and erases it, but first uses it to derive the key for counter 3 and store that in FK21.

For transaction 3, the lowest 'on' bit is $2^0$=1 so it uses FK21 similarly which now contains the key for counter 3 as set above, and erases it.

For transaction 4, the lowest 'on' bit is $2^2=4$ so it uses FK19 which contains the key for counter 4, and erases it but first derives the keys for counter 4+2^1=6 in FK20 and 4+2^0=5 in FK21.

For transaction 5, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 5 as above, and erases it.

For transaction 6, the lowest 'on' bit is $2^1=2$ so it uses FK20 which contains the key for counter 6 as above, and erases it after generating the key for counter 7 in FK21.

For transaction 7, the lowest 'on' bit is $2^0=1$ so it uses FK21 which contains the key for counter 7 as above, and erases it.

Txn 8 bit $2^3$ uses key 8 from FK18 and derives key 12 in FK19, 10 in FK20 and 9 in FK21.

Txn 9 bit $2^0$ uses key 9 from FK21.

Txn 10 bit $2^1$ uses key 10 from FK20 and derives key 11 in FK21.

Txn 11 bit $2^0$ uses key 11 from FK21.

Txn 12 bit $2^2$ uses key 12 from FK19 and derives key 14 in FK20 and 13 in FK21.

Txn 13 bit $2^0$ uses key 13 from FK21.

Txn 14 bit $2^1$ uses key 14 from FK20 and derives key 15 in FK21.

Txn 15 bit $2^0$ uses key 15 from FK21.

Txn 16 bit $2^4$ uses key 16 from FK17 and derives key 24 in FK18, 20 in FK19, 18 in FK20, 17 in FK21.

Txn 17 bit $2^0$ uses key 17 from FK21.

Txn 18 bit $2^1$ uses key 18 from FK20 and derives key 19 in FK21.

Txn 19 bit $2^0$ uses key 19 from FK21.

Txn 20 bit $2^2$ uses key 20 from FK19 and derives key 22 in FK20 and 19 in FK21.

Txn 21 bit $2^0$ uses key 21 from FK21.

Txn 22 bit $2^1$ uses key 22 from FK20 and derives key 23 in FK21.

Txn 23 bit $2^0$ uses key 23 from FK21.

Txn 24 bit $2^3$ uses key 24 from FK18 and derives key 28 in FK19, 26 in FK20, 25 in FK21.

Txn 25 bit $2^0$ uses key 25 from FK21.

Txn 26 bit $2^1$ uses key 26 from FK20 and derives key 27 in FK21.

Txn 27 bit $2^0$ uses key 27 from FK21.

Txn 28 bit $2^2$ uses key 28 from FK19 and derives key 30 in FK20 and 29 in FK21.

Txn 29 bit $2^0$ uses key 29 from FK21.

Txn 30 bit $2^1$ uses key 30 from FK20 and derives key 31 in FK21.

Txn 31 bit $2^0$ uses key 31 from FK21.

We have now generated 31 transaction keys and have not come anywhere near 'using up' the future key registers -- in fact we've only used five of them, not even touching FK1-16 at all.

If you continue this process for a long time you will see it derives a key for every 21-bit binary value other than zero, of which there are 2097151; but DUKPT prescribes that counter values with more than 10 bits set are skipped, so only 1048575 of these values, and their corresponding keys, are used -- and as I said in the summary above, that's the number of keys and transactions for one DUKPT device, without rekeying.

The original intent was that a device, or (much more likely in the technology of the 1980s and 1990s) the secure module within a device, would be replaced after this cycle. In recent years as DUKPT has been applied to higher-volume but lower-value and lower-security applications, there is more desire for rekeying. See What is transaction capacity of a POS using 3DES DUKPT? for some (differing) perspectives on this.

(further expanded for completeness although this part is correct at the link)

Each derivation step occurs between the key for one KSN and a subsequent KSN which has exactly one bit set that was cleared before, i.e. adds a power of two. For the (trusted) host algorithm, all these steps are performed in a loop, from the highest-order bit set in the desired counter to the lowest-order; for the future-key algorithm they are spread out in time with each bit effectively done at the beginning of the range of counter values which have that bit set, as laid out above; either way the cumulative result for each key actually used is the same.

Each one-bit derivation step uses two single-DES encryptions (but not triple-DES) and is expressed by the standard in a rather complicated form that boils down to:

Input: curkey = key for 'before' KSN, with Left and Right halves accessible separately;
ksn = low 8 bytes of updated KSN (with new bit added) corresponding to new key

Temporary: modkey = curkey with each half XORed with C0C0C0C0_00000000

Output: newkey = key for updated KSN, similarly with Left and Right halves

newkeyR = DES_encrypt(key=curkeyL, data= ksn XOR curkeyR) XOR curkeyR

newkeyL = DES_encrypt(key=modkeyL, data= ksn XOR modkeyR) XOR modkeyR

The website you linked expresses this more concisely in pseudocode as

GenerateKey(key, ksn) { # where ksn is already updated by the caller, and the return is used to update key
    return EncryptRegister(key ^ KeyMask, ksn) << 64
         | EncryptRegister(key, ksn)
}
EncryptRegister(key, reg) {
    return (key & FFFFFFFFFFFFFFFF) ^ DesEncrypt((key & FFFFFFFFFFFFFFFF0000000000000000) >> 64,
                                                  key & FFFFFFFFFFFFFFFF ^ reg)
}

The main benefit of the future-key algorithm is that if a device is compromised, the data currently in the FK registers cannot be used to construct any previous keys for the same device, or any keys at all for another device. Thus assuming the compromise is detected and all new keys from this device are blacklisted, the compromise results in no loss of security. DUKPT was originally intended for use in bank ATMs and it was expected (correctly) that some ATMs would be stolen or attacked because, as Willie Sutton famously observed, that's where the money is. The simpler host-side algorithm is capable of creating the key for every txn for every device on demand, but was assumed to be implemented only in a well protected environment, typically a dual-locked vault inside a fortified data center with reinforced walls, fences, and round-the-clock armed guards. And possibly, though an ABA committee would never say so, sharks with frickin lasers :}


Is the 'Padding Oracle attack' deterministic?

These should both be valid paddings:

... ... ... 68 02 02
... ... ... 68 02 01

But if this ambiguity comes up, we can distinguish between the two by  modifying the second-to-last byte in some way. After flipping, say, the highest four bits:

... ... ... 68 f2 02
... ... ... 68 f2 01

Only the second one is a valid padding.


Crypto scheme to map data to users in a way that is anonymous to database server

I'm not sure this threat model is realistic, since I would expect an adversary to want to shutdown the entire site, instead of just censoring specific "contributors" :-).
To protect from this (and from the users becoming de-anonymized) one would likely use an anonymity network such as Tor.

The website should not be able to see that data content in clear text. - this problem is fixable by implementing database encryption with key derived from user password and kept in session, and dumped at the end.

The problem with this, is that the data will be unencrypted at the server's location for some time - worse, the server has the key.
Lets assume, that the server is compromised, and malicious:
Then it could easily obtain a copy of every new document, and of old documents by storing the password, when the respective user logs in again.
A solution to this problem would be to have contributors encrypt data using the public key of the recipient.
However, if you use asymmetric cryptography on the client side, someone has to perform the encryption.
You don't want the website to do this for several reasons:

JavaScript (which would likely be required) is a large attack surface - if the server is compromised, and users of the website are required to enable JS, they are exposed to more risk.

If the server is compromised, it could swap the encryption for nothing, without the users noticing.

Therefore, you would likely need an external program, such as gpg or age.
Unfortunately, by now, we have achieved usability levels close to that of encrypted email :-(.

What I need is a hint in order to implement multiple cryptographic functions in a system that will allow a website to map data to an account anonymously.

As I already said, I don't think this is a realistic requirement.
Additionally, I'm not aware of any protocols that solve this problem.
However, ring-signatures could maybe be used to authenticate users. Using ring-signatures, a user could prove that they are part of a larger user-group. Then, the server can't determine which specific user they are, but could allow them to submit documents for upload.
I'm not sure on the specifics, and there are many ways the protocol design of this could go wrong. A first step would be, to determine the exact requirements.


Proof of correctness of an ElGamal encryption given a specific public key

As you suggested, the most natural approach would be to use a zero-knowledge proof - namely, we can let Alice prove to Bob that she knows the plaintext encrypted in the ciphertext she sent, with respect to the public key $h$. However, this has an immediate issue: what prevent Alice from honestly encrypting some garbage, unrelated to the actual (say) ASCII character she knows? She can intuitively always do that - she could even always encrypt another valid-looking ciphertext, like, another ASCII character.

So, what exactly is your security model? Who should Alice and Bob prove something to (clearly, Bob is not the one Alice wants to sent a proof to: he has the secret key, so he can check by himself whether he got garbage or a valid-looking plaintext)? Do you assume some kind of authority that Alice and Bob interact with, to whom we can either ask Alice to prove that she encrypted the right value (is this right value known to the authority?), or ask Bob to prove that he could decrypt the ciphertext to a valid-looking value?

In all situations, an appropriate zero-knowledge proof should do the trick. Which one exactly depends on the exact scenario and variant of ElGamal: for example, using exponential ElGamal, Alice should not only prove that the knows $(v,r)$ such that the ciphertext is of the form $(g^r, g^vh^r)$: to prove that this can be decrypted, she must further prove that $v$ is "small" (smaller than some bound $B$ which is a parameter of the system). But without knowing your exact scenario, it is not possible to give a more precise answer for now. As a general principle: do not ask "how can Alice and Bob to this" when you think that this is what they should do in your scenario - instead, explain exactly what your scenario is, and what security property you wish to achieve exactly. Then we can figure out a solution.


Asmuth-Bloom's threshold secret sharing scheme

I don't believe that, in the example you gave, you can reconstruct the secret using two shares.

$d + \alpha m_0$ is in the range $[0, 2431)$; using the two shares $1 \bmod 11$ and $3 \bmod 19$, you can determine that it is one of $155, 364, 573, 782, 991, 1200, 1409, 1618, 1827, 2036, 2245$, however you have no further information about which it might be.  Since these include values consistent with all possible values of $d$ (which must be between 0 and $m_0-1$), we can conclude that the attacker cannot determine the value of $d$, or even eliminate any potential value of $d$.

On the other hand, if the attacker knows the probability distribution $\alpha$ was chosen from, he can obtain some probabilistic information about $d$.  In the case in question, we see that there are four possible values of $\alpha$ that is consistent with $d=1$ and $d=2$, while there are only three possible values that is consistent with $d=0$.  If the attacker knows that $\alpha$ was chosen uniformly, he may conclude that while $d=0$ is possible, it is somewhat less probable to be the shared secret than either of the other two.

In contrast, Shamir's Secret Sharing doesn't leak any such probabilistic information for any number of shares less than the threshold.


How many bytes of the last keystream block are used to XOR the final block of partial plaintext in CFB, OFB & CTR modes?

Suppose a block is $b$ bits long, say $b = 128$, and the message is $\ell$ bits long, say $\ell = 187$.  Then the final plaintext block is $n = \ell - \lfloor\ell/b\rfloor \cdot b$ bits long.  So use $n$ bits of the final keystream block; in this example, $n = 59$.


At least, doing the goof of reusing the OTP makes one vulnerable to disclosure of any of the key, which trivially reveals all the others.

For the rest, the consequences depends heavilly on what the keys are intended for. If the keys are intended for a block cipher that is secure including under related-key attack (as AES almost is), then there is not consequence beyond the aforementioned.

But in other cases the goof can be damaging, even disastrous. Simple example of the worse: the two random keys enciphered under two-times Pad are really random half-keys, intended to be held separately and combined by XOR to form a full key when needed (which is a simple and most common form of secret sharing with 2-out-of-2 parameterization); with the goof, the full key is the XOR of the ciphertexts for the two half-keys, thus is compromised, even though the individual half-keys remain confidential.

There is a spectrum in-between if the keys are for ciphers with poor security, especially under related-key attacks. In particular, if there are many keys enciphered under many-times pad, the goof allows the attacker to effortlessly pinpoint a key pair with much lower Hamming distance than average, and that pair might become the basis of a cryptanalysis (e.g. from ciphertexts for known plaintexts enciphered under both keys).


Can we retrieve his private key using his public key in ECC?

On ECC, the private key is a value $k$ in the range $[0,q-1]$ where $q$ is the order of the group generated by a point $G$, with $q$ a prime number, and $Q = kG$ is the public key.

The best known algorithm to solve this is Pollard's rho algorithm which runs asymptotically in $O(\sqrt{q})$.

In your situation, part of $k$ is known, except the $72$ least significant bits. Writing $k = k_12^{72} + k0$ with $0 \leq k_0 < 2^{72}$, then $k_1$ represent the known bits and $k_0$ the unknown part you are looking for.

We have
\begin{array}{rcl}
Q & = & kG \\
& = & (k_12^{72} + k_0) G \\
& = & k_12^{72}G + k_0 G
\end{array}
So $k_0G = Q'$ where $Q'= Q - k_12^{72}G$ is known. Now, instead of looking for $k$ in the range $[0, q-1]$, you are looking for $k$ in the range $[0, 2^{72} - 1]$ which has a much much smaller size.

For that, you can look at Pollard's kangaroo algorithm which can search for the discrete logarithm in the subset $[0, 2^{72} - 1]$ in an asymptotically complexity $O(\sqrt{2^{72}})$ which is $O(2^{36})$ and is feasible.


Should we run PBKDF2 for every plaintext to be protected or should we run PBKDF2 only once?

Assume you have an IND-CCA secure cryptosystem $E$ that runs a password through a slow KDF and implicitly handles salts and random IVs, a human-chosen password $p$, and messages $m_1$ through $m_n$ to encrypt. Is $E_p(m_1+m_2+\cdots+m_n)$ or $E_p(m_1)+E_p(m_2)+\cdots+E_p(m_n)$ better for this? Each invocation of $E$ is slow due to it running a KDF on $p$, but an attacker only needs to guess $p$ once. This means that both techniques are equally secure against an attacker assuming $E$ takes a constant amount of time, but the former is significantly faster for honest parties, so the former is better.

The purpose of a slow KDF is to make brute force of a weak, human-generated password difficult. You need to run it each time a password is input. Assuming only one password is being input, then it only has to be run through a KDF once. The output key can be used to protect as many secrets as you wish.

The reason is simple. If an attacker manages to guess the original password, they'll be able to use it again and again to decrypt all the data, whether or not the data was encrypted all at once or encrypted piece by piece by running the password through a KDF multiple times to generate multiple keys.


RSA-OAEP
Recall that RSA-OAEP is defined as follows (with $m$ being the message to encrypt, $G$ and $H$ being random oracles and $(e, N)$ being a standard RSA public key):
$Encode$:

Select a random $k$-bit integer $r$.
Pad out $m$ with $0$s to length $l = |N| - k$.
Compute $X = G(r) \oplus m_{padded}$
Compute $Y = r \oplus H(X)$
Return $X || Y$

$Decode$

Compute $r = Y \oplus H(X)$
Compute $m_{padded} = X \oplus G(r)$
Strip off the $0$s from $m_{padded}$ to recover $m$

IND-CPA Game
The IND-CPA game in this case is as follows:

The adversary selects two messages $m_0, m_1$ and submits them to the an encryption oracle.
The encryption oracle samples $b \in \{0, 1\}$ and computes $c = \text{RSA-OAEP}(m_b)$.
The adversary is free to perform more encryptions. To conclude, the adversary must guess $b$ corresponding to the message that was encrypted.

If the adversary can guess $b$ with non-negligible advantage the scheme is not IND-CPA.
Sketch of proof that RSA-OAEP is IND-CPA
The basic idea of the proof is that in order to recover $m_b$ from $c$ the adversary must be able to recover the entirety of $X$ and $Y$ from $c$ (recall that $c = \text{RSA-OAEP}(m_b) = \text{RSA}(X||Y)$). This is because to recover $m$ we must be able to compute $r = Y \oplus H(X)$. If we are missing even one bit of $X$ then $H(X)$ will give us a uniform random value (remember $H$ is a random oracle), and our $r$ value will be totally wrong (i.e. we learn nothing of the true value of $r$). The same is true of $Y$, if we fail to recover even one bit of $Y$ we will compute $r$ incorrectly, and as $G$ is also a random oracle  $m_{padded} = X \oplus G(r)$ will again give us a uniform random value, revealing nothing about the actual value of $m$. Therefore adversary must be able to recover all of $X||Y$ to learn anything about $m$ which under the assumed hardness of the RSA Problem is not considered computationally feasible. Thus the adversary has no better chance than guessing $b$ and has negligible advantage, making the scheme IND-CPA.


Crypto-shredding a file by erasing the IV instead of erasing the Key

No, just erasing the AES-CTR IV is not enough to reliably render the file undecryptable.

To see why, consider what happens if the AES key is later compromised, and the attacker also happens to know at least one AES block (i.e. 16 bytes) of the "shredded" file's plaintext content.  They can then XOR this known plaintext with the corresponding part of the ciphertext to obtain a block of the AES-CTR keystream.

Running this block through the AES block decryption function, using the compromised key, will then reveal the input block (i.e. nonce and counter) used to generate this block of keystream.  Incrementing and/or decrementing the counter will then let the attacker decrypt all other blocks of the file.

Ps. Similar attacks are also possible on all the other classical block cipher modes of operation (CBC, CFB, OFB, CTR).  I'll leave figuring out the exact steps needed as an exercise.  (The diagrams on the Wikipedia page I linked to should be helpful.)  With CBC and CFB modes, the first block of the file cannot be decrypted without knowing the IV, but on the other hand, those modes allow all the rest of the file to be decrypted even without knowing any of the plaintext in advance.

Modern AE modes aren't generally any more resistant to such attacks, either, especially as most of them simply combine one of the classical modes (usually CTR) with some message authentication scheme, and can thus be attacker just like the underlying classical mode.

The take-home message from all this is that the IV is not a secret, and hiding it is not sufficient to protect the message from decryption by anyone who has the key.  More generally, modern encryption schemes are generally designed with the assumption that the only secret parameter of the system is the key, and with the goal of remaining unbreakable as long as the attacker does not know they key.  The flip side of the coin is that, if the attacker does know the key, these schemes generally offer no security guarantees whatsoever.


How to prove that two EC public keys created with two different generators share the same secret key?

Is it safe to simply provide a Schnorr signature

Actually, a single Schnorr signature is insufficient.  For your proposal, someone could pick an arbitrary $A$ and compute $B = x(G+H)-A$ (for some $x$ he picks), and he could generate the signature.

I will also assume that the order of the subgroup that $G, H$ generate is prime (which is usually the case)

Instead, you can use three signatures:

One is sig.c = Hs(A || kG), sig.r = k - x * sig.c; this shows that we know a solution $x$ to $A = xG$
Next is sig.c' = Hs(B || k'H), sig.r' = k' - x * sig.c'; this shows that we know a solution $y$ to $B = yH$
Third is sig.c" = Hs((A+B) || k"(G+H)), sig.r" = k" - x * sig.c"; this shows that we know a solution $z$ to $A+B = z(G+H)$

[Don't forget to use three different $k$ values for the three signatures]

It is easy to show that if we know solutions to the above three with $x \ne y$, then we can rederive the discrete log of $H$ wrt $G$.  We assumed that we don't know that, and hence we have $x=y$ (which is what we are trying to prove)


curious DHE implementation for key exchange

I haven't checked, is $p$ a safe prime and/or is 4 a generator over $p$?

Server has random secret $S$, known $p$ and $g$ a generator.  I'm substituting in $V$ for your $g$, with $g = 4$.

$V = g^S \mod p$

$V$ is a verifier of the server, as in SRP.

$V$ is your $g$, so known by the client.  Anyone knowing $V$ can establish communications with the server.

You calculate for random $X$

$A = V^X \mod p$
$B = g^X \mod p$

So, when you send $B$, server calculates

$A = B^S = g^{XS} = V^X \mod p$

This is one-way authentication, of the server only.  You could do the same thing with the client, and have a mutually authenticated DH key exchange (each client would need a secret as well, and the server would have to know the corresponding verifier).

What's curious is why bother sending back anything, why not just use $A$ directly (or a hash of it, for example)?  If the 20-byte value isn't checked against anything else, it seems sort of useless.  It could be used as a proof, e.g. hash of $A$, but you don't indicate that it's used for anything except to XOR it with $A$.  Since it's being sent in the clear, it doesn't really add anything to the security.


Should the secret key of Shamir's secret-sharing algorithm be interpreted byte by byte?

Shamir's secret sharing scheme provides only confidentiality against shareholders who want to try to learn the secret.  It does not prevent denial-of-service attacks (or attacks on integrity), where a malicious shareholder submits a bogus share to try to cause the reconstruction of the shares to fail.

If you want security against that sort of attack, don't use Shamir's secret-sharing scheme; there are other schemes that can accomplish that.  Verifiable secret sharing schemes do exactly that: they protect against malicious shareholders who submit bogus shares.  There are many constructions of verifiable secret sharing schemes in the literature.  They do exactly what you want.

Depending upon your application, you may also find threshold cryptography  relevant.


Using the floor of sines of integers is to show that there is nothing sinister, like a backdoor in the choice of the constants.

The answers to the following
question shows how the choices for the shifts help with diffusion, I.e., a fast avalanche effect.


$g$, $p$, and $y$ are of length 308 (decimal digits). How can I compute $x$ accurately from the equation?

Computations with integers this size (for example, verifying a guess of an integer $x$) are possible with Python's pow in its three-arguments form, Java's BigInteger modPow, GP/Pari, Sage, Mathematica…

  I tried finding $x$ by taking log on both sides

That method can give you a real $x$, but here we want an integer. Given 1024-bit prime $p$, generator $g$, and $y=g^x\bmod p$, there is no general and easy way to find an integer $x$. That may be possible if the order of $g$ is appropriately smooth, but nothing in the context suggests that. That also may be possible if $x$ was generated by a weak RNG, but since the nature of the weakness is untold, it is hard to tell how to proceed.

  Random Number as well

Perhaps that mysterious given helps to determine the nature of the RNG weakness. Or/and perhaps this given is somewhat related to the random number generated during the encryption, which knowledge would trivially allow to decipher without the private key $x$.


Continuous stream of strong randomness from limited entropy?

As noted in the comments, simply using your initial entropy to seed a deterministic random bitstream generator, such as those specified in NIST SP 800-90A Rev.1, or as a key to any secure stream cipher or a block cipher in OFB / CTR mode, should be enough to generate a bitstream practically indistinguishable from random.

Actually, 1024 bits of seed entropy is overkill for that.  Even a 256-bit keyspace cannot be enumerated using known physics (yes, even quantum computing) and resources available to mankind, so the only way to break (i.e. distinguish from true randomness, without prior knowledge of the key) a DRBG with a 256-bit seed length is through cryptanalytic attacks that exploit some flaw in the generator — and adding more seed entropy generally doesn't help against attacks like that.  This is fortunate, since most standard DRBGs / ciphers don't actually accept a seed / key longer than 256 bits, or, if they do, they'll internally hash it down to a shorter internal state.

That said, if your chosen DRBG does not directly accept long keys, and if you're not 100% sure that your 1024-bit seed really has 1024 bits of entropy, you may still want to hash it down to 256 bits (using a secure cryptographic hash function), instead of simply truncating it, before feeding it to the DRBG.  Alternatively, you can simply use a hash-based DRBG (such as the Hash_DRBG or HMAC_DRBG constructions from SP 800-90A.1, or the SHAKE functions from SHA-3 / FIPS 202) that directly accepts an arbitrarily long seed, and automatically hashes it down to its internal state size.

In any case, without a better entropy source than system time, I would not bother with attempting to merge additional entropy into the PRNG state — or at least, not the way you're proposing to do it.  Specifically, your proposed method has a couple of serious weaknesses:

If the initial entropy is ever leaked, an attacker can fairly easily predict future outputs just by observing a block of output and guessing when the next output will be generated.  (The precise level of difficulty will depend on the precision of the clock input, and on the predictability of the usage patterns, but even in the best case it's unlikely to deter a serious attacker.)
In particular, by observing two output blocks separated by one unknown block, an attacker can both guess the middle block and verify their guess quite efficiently (most especially so if they can observe the two blocks within a short period of time).
Conversely, if the initial entropy is not leaked, mixing in the system time doesn't really provide any added value.  It does, however, destroy the determinism of the generator, which might be considered a drawback.
Also, if the seed entropy is leaked, and an attacker can observe two or more previously generated successive outputs of the generator, they may be able to learn when those outputs were generated, which could be information one might not wish to reveal.

If you do wish to incorporate additional entropy from the system time (or other low-density entropy sources), I'd suggest using a proper entropy pool design such as Fortuna, which is designed to recover from state compromises by accumulating entropy into multiple internal pools that are only used to reseed to PRNG once they've accumulated enough entropy to resist brute force guessing.


Are chosen-prefix collisions for SHA-1 a major threat?

This is the same issue as with MD5, so you can search for attacks on that scheme.

An attacker can create executables that can do one thing during testing and another during deployment by replacing one file by another. As the signature doesn't change, the files in the repository would still validate. If you have a changed file then it is pretty easy to execute an entirely different code path when an application is run.

You would have to analyze the entire (sub-)system to see the impact of such a vulnerability on the system itself. I'd say that a well maintained Git repository isn't as vulnerable as e.g. GPG. It's probably not that easy to simply replace files that are already within a Git repository (but you'd better ask a Git expert instead).

In general signature generation and validation through message digest values are most vulnerable to attacks on the hash functions.


Does AAD make GCM encryption more secure?

In general the AAD itself is not required or won't change the security of the GCM mode of operation itself.

It may however directly influence the security of the protocol in which GCM is deployed. For instance, you may have specific configurable parameters outside the ciphertext itself.

These parameters may very well include:

version number of the protocol
message specific nonces
addresses of recipient(s)

If you don't include these in the AAD or ciphertext then those parameters won't be validated by verification of the authentication tag. This means that attackers can simply change them. For instance, an attacker may try and switch to a previous, less secure protocol number.

You don't need to include the GCM nonce (the IV) itself in the AAD by the way; the nonce is already included in the calculation of the authentication tag.

Obviously if you allow the parameters to directly influence the GCM mode of operation itself then validating the authentication tag may be too late; you're better off to verify or set them beforehand for maximum security.