What happens if a nonce is reused in ChaCha20-Poly1305?

If you reuse a nonce, you lose confidentiality for the messages with that nonce. Messages with other nonces retain their confidentiality.

However, the attacker can also attack the MAC part (Poly1305) and generate a third and more messages with the same nonce. See: Why is Poly1305 popular given its 'sudden death' properties?

So unless you have a way to rule out messages with that nonce in the future, for example due to the protocol enforcing a new nonce each time, you cannot trust messages encrypted with that key any more. If you can rule them out, messages with other nonces cannot be forged, because the MAC key is generated from the encryption key and the nonce.


You are correct, Blowfish is a reversible cipher if you know the key. Bcrypt has three parameters it uses to hash a password:

Salt
Password
Cost

It derives a key using the salt, password and cost to encrypt the well known text "OrpheanBeholderScryDoubt" and not the password itself. So verification would be performing the encryption again on this string and see if the ciphertext is the same. The salt prevents scenarios where two users would use the same password to show up as the same ciphertext. So if you don't have the password you can't generate the ciphertext.

The reason why they are using Blowfish instead of twofish or threefish, is that it was published in 1999, whereas Twofish was from 1998 and threefish 2008. Bcrypt was seeking properties offered by Blowfish, namely slown key derivation so there was no reason to not use the already established blowfish (cryptographers are conservative and prefer to use proven solutions rather than cutting edge ones).


People found MARS to be clunky and overly complex, leading to more effort for implementation and optimization, and also a less clear overall security picture.

Assessments of "security" are, in fact, extremely subjective, because they rely on speculations about unknown future cryptanalytic attack, empiric traditions (e.g. "more rounds" = "more security"), and wishful thinking. If we want to remain objective, then out of the 15 AES candidates, 13 were "as secure as one can get" and there is relatively little more that can be said on the subject. The rest is a matter of implementation (for performance and for resistance to side-channel leaks), and the word of the implementers about MARS was, mostly, "please don't".


Is it possible to break AES-128 ECB if you are given a ciphertext and a small portion of the key?

You can't use it to "break the encryption", but you can guess at the remaining 8 bytes of the key. The remaining 8 bytes should be feasible to find, especially if you can run the search in parallel.


Key derivation for AES-Encryption key and HMAC

In both options, if the adversary has a way to check either AES key, then a brute password guessing attack can be attempted, and BCrypt is the main line of defense against that.

For constant effort, option 2 force to halve the cost parameter in BCrypt, and is thus twice more vulnerable to password guessing than option 1 is.

BCrypt's output is described as 31 byte, and likely has 192 bits of entropy excluding cost and salt. If so, this is more entropy than needed for security in the foreseeable future, and acceptable baring a diktat requirement that all keys have some larger size.

Thus option 1 is decidedly the best of the two; however a proper implementation of scrypt would be considerably safer, and as a bonus there is no need for something extra in order to generate the desired amount of key material.


Collision resistant hash function implies one-way function

Collision-resistance implies one-wayness.
Proof by reduction: if you have an algorithm $A$ which is able to invert $H: b^* \rightarrow b^n$,
we can build an algorithm $B$ which is able to find a collision (with almost the same time and probability).
Here $b$ means $\{0,1\}$.

Let's consider only input strings of some length $l\ge n$.
Notice that $H$ splits the set $b^l$ into the following $2^n$classes:
$$
\{C_h = \{x: x\in b^l \land H(x)=h \}\}_{h\in b^n}.
$$
On expectation (if function behaves randomly), each class consists of $k = 2^{l-n}$ elements.
But for our concrete function some of the classes could be empty, while some of them have more elements than others.

Algorithm $B$ behaves as follows:

Picks random $x\in b^l$ and evaluates $h = H(x)$.
Runs $A$ on input $h$: $x' = A(h)$.
If $x \neq x'$, returns a collision $(x, x')$. Goes to step 1 otherwise.

Easy to see that probability of success on step 3 is $1 - \frac{1}{k}$ (which is quite a lot, and you can increase $k$ or just make several rounds of algorithm to achieve any probability you want).
The explanation is: when you're picking $x$ on first step, you're picking one of ${C_h}$ with probability proportional to a number of elements in the class: $Pr[C_h] = \frac{|C_h|}{2^l}$.
Then, on the step 3, probability of failure, i.e. $x = x'$, is $1/|C_h|$,
taking into account uniformly random choosing of $x$ and the fact that $A$ "doesn't know" which element $x$ from the class $C_h$ you selected (you've given him just $h$).
So, the common probability of failure is calculated as:
$$
Pr[\texttt{"failure"}] =
\sum_{h\in b^n} {Pr[C_h] \cdot Pr[\texttt{"failure on C_h}"]} =
\sum_{h\in b^n} {\frac{|C_h|}{2^l} \cdot \frac{1}{|C_h|}} = 2^n\cdot \frac{1}{2^l}.
$$

Remark that we do not require any random properties of $A$ nor $H$.
We achieve this probability estimate just using randomness of $B$ (uniformly random choosing of $x$ on step 1).


Why work in a subgroup for Naor and Pinkas oblivious transfer?

The protocol's security comes from the DDH assumption, which is only secure when operating in groups of prime order [1]. The more typical groups, e.g. $\mathbb{Z}_p^*$ is not of prime order, but of order $p - 1$. Fortunately, a subgroup of $\mathbb{Z}_p^*$, namely the set of quadratic residues modulo $p$ doesn't have this problem. This answers the first question.

To answer the second question, the public values such as $x, y$ and so on are in the subgroup. The private values are selected uniformly at random from $\mathbb{Z}_q$, where $q$ is the order of the subgroup (and the generator $g$).

Finally, the set of quadratic residues is one of the simpler subgroups to understand, but others are also possible as long as DDH is hard. Some alternatives are outlined in [2].

[1] Katz and Lindell, Introduction to modern cryptography, Chapter 7.3.3

[2] Dan Boneh, The decision diffie-hellman problem, Section 1.1, http://crypto.stanford.edu/~dabo/pubs/papers/DDH.pdf


Why do we need special key-wrap algorithms?

The paper you cite (Deterministic Authenticated-Encryption...) gives quite a bit of useful information (but I'm assuming you already knew that). It looks like a pretty good read (I'll let you know if that assumption holds after I finish it).

For why simpler constructions (CBC/CTR with a MAC or even AEX mode) don't satisfy (emphasis added):

  A key-wrap scheme is a kind of shared-key encryption scheme. It aims to provide “privacy and integrity protection for specialized data such as cryptographic keys, . . . without the use of nonces” (meaning counters or random bits). So key-wrap’s raison d’etre is to remove AE’s reliance on a nonce or random bits.

The reason for removing the nonce/IV/random bits, at least according to the paper, is to make the protocol "more resilient to IV misuse."

I also found the following paragraph useful (emphasis added):

  That said, in many contexts where one would think to use key wrap, one can use a conventional AE scheme, instead. This does not make studying the key-wrap problem pointless. First, it clariﬁes the relationship between key wrap and conventional AE. Second, DAE leads to misuse-resistant AE, and methods that achieve this aim make practical alternatives to conventional (not misuse-resistant) two-pass AE methods. Finally, practitioners have already “voted” for key-wrap by way of protocol-design and standardization efforts, and it is simply not productive to say “use a conventional AE scheme” after this option has been rejected.

Another potential reason for key-wrap algorithms is their analyzability. I'm not completely sure about this, but it could be that under the key-wrap algorithms, security is provable, but that might not be possible under a more simplistic approach.

On a side note, when reading through the intro to that paper, it made me wonder how the notion of Entropic Security plays into key-wrap algorithms. In the paper, they briefly mention it as a related work, but that is all.


Is it secure to use Diffie-Hellman key agreement to generate a nonce?

This algorithm is vulnerable to a Man in the middle. From Wikipedia:

In the original description, the Diffie–Hellman exchange by itself does not provide authentication of the communicating parties and is thus vulnerable to a man-in-the-middle attack. Mallory may establish two distinct key exchanges, one with Alice and the other with Bob, effectively masquerading as Alice to Bob, and vice versa, allowing her to decrypt, then re-encrypt, the messages passed between them. Note that Mallory must continue to be in the middle, transferring messages every time Alice and Bob communicate. If she is ever absent, her previous presence is then revealed to Alice and Bob. They will know that all of their private conversations had been intercepted and decoded by someone in the channel.
A method to authenticate the communicating parties to each other is generally needed to prevent this type of attack. Variants of Diffie–Hellman, such as STS protocol, may be used instead to avoid these types of attacks.


Block cipher mode with diffusion on ciphertext

Yes, there are modes of operation that achieve the property that you are describing. For example, the Propagating Cipher Block Chaining (PCBC) mode of operation:

This mode is similar to CBC but the output for each block is propagated to the input of the next one, so a small error will propagate indefinitely, both for encryption and decryption.

There may exist other less known modes of operation that also share this property.

Depending if you consider also corruption of the Initialization Vector (IV), then other common modes of operation will do. For instance, the Counter (CTR) mode and the Output Feedback (OFB) mode will irremissibly corrupt all the plaintext blocks during decryption if the IV is changed.


Attacking a hardware AES implementation if it leaks the intermediate round states

If you can read the intermediate states of the encryption algorithm you could recover, one by one all the round keys.
Given a AES round, all the operation between the two AddRoundKey (at the beginning and the ond of the round) are invertible.

Take for example round 1:
you get the internal state before AddRoundKey (of round 2), you get back at the beginning of round 1, and you get the plaintext XORed with the first round key.

Finally, recovering all round keys is equivalent to recover the master key.


How does Clifford Cocks 'Non-Secret Encryption' work?

The two last equations don't directly give you the value of $C_i$, they are telling you the values of the remainder of Ci when divided by $P$ and $Q$. You then use the Chinese Remainder Theorem with this information to produce the value of $C_i$ (modulo $N$) that you are looking for.

See en.wikipedia.org/wiki/Chinese_remainder_theorem (there is an algorithm for solving it for the case of two equations)


Yes. See also en.wikipedia.org/wiki/Advanced_Encryption_Standard. There is a pseudo-code in NIST's AES standard document which is very helpful for implementors. I have a Python code that very closely follows that pseudo-code in s13.zetaboards.com/Crypto/7385224/1/. For details of the design of AES, see J. Daemen, V. Rijmen, The Design of Rijndael. (Springer-Verlag, 2002)


There are 256! possible 8x8 S-boxes (i.e., bijective functions from $\{0,1\}^8$  to $\{0,1\}^8$).  This is an absolutely enormous number.  You couldn't possibly enumerate all of them within the lifetime of the universe.  So, yes, this is one reason why it is not straightforward to determine whether there exists such a S-box with differential uniformity 2.


Use of q-ary lattices in developing cryptosystems

The main advantage of using $q$-ary lattices is that it allows a cryptosystem designer to rely on the standard Short Integer Solution (SIS) and Learning With Errors (LWE) problems, which are known to be at least as hard as worst-case lattice problems.  So the SIS/LWE problems abstract away the connection to lattices, and give the designer a strong hardness guarantee "for free."  By contrast, if one were to work "directly" with lattices, one would have to explicitly describe a distribution over lattices and their secret "trapdoors," show (or assume) that lattices generated in this way are hard, etc. etc.

Another reason is that the SIS/LWE problems are very easy to work with, and admit a lot of versatility; it's less obvious how to obtain comparable properties when working with general lattices.  For example, one can perform arithmetic on parity-check/generator matrices $\mathbf{A}$, which can yield many interesting properties and applications (e.g., trapdoor manipulations, homomorphisms, etc.).  Most of these arithmetic operations do have interpretations in terms of general lattices, but they've been much easier to discover and exploit when working with $q$-ary lattices and their parity-check/generator matrices.

Regarding your question about $\Lambda(\mathbf{A}^t)$, this is a lattice and hence it has an infinite number of points.  However, modulo $q$, it has at most $q^n$ distinct points, at most one per value of $\mathbf{s}$.  It has exactly $q^n$ points if and only if no two distinct values of $\mathbf{s}$ yield the same value of $\mathbf{A}^t \mathbf{s} \pmod{q}$, which holds if and only if the right-nullspace (mod $q$) of $\mathbf{A}^t$ is simply $\{ \mathbf{0} \}$.


Explanation and proof of a well-know probabilistic lemma

This is based on an averaging argument (which is also used in the proof of the Goldreich-Levin hardcore bit).

First, I assume that when writing $\operatorname{Pr}[A(x,y)=1] \geq \epsilon$, then the probability is taken over a random choice of both $x$ and $y$. Now, the claim is that there exists a subset of $x$ values of a "large enough size" so that for every $x$ in this set, the probability of the event is at least $\epsilon/2$ when taking a random $y$ only.

This can be proven as follows: Let $\Omega$ be the set of all values $a\in X$ for which $\operatorname{Pr}_y[A(a,y)=1]\geq \epsilon/2$. (Note that for any $a\in X\setminus \Omega$ it therefore holds that $\operatorname{Pr}_y[A(a,y)=1] < \epsilon/2$.)

Our aim is to prove that $\Omega$ is of size at least $\epsilon/2 \cdot |X|$, since this will show what we need.

\begin{eqnarray}
\epsilon \:\leq\:\operatorname{Pr}_{x,y}[A(x,y)=1] & = & \frac{1}{|X|} \cdot \sum_{a\in X} \operatorname{Pr}_y[A(a,y)=1]\\
& = & \frac{1}{|X|} \cdot \sum_{a\in\Omega} \operatorname{Pr}_y[A(a,y)=1] + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\
& \leq & \frac{1}{|X|} \cdot \sum_{a\in\Omega} 1 + \frac{1}{|X|} \cdot \sum_{a\notin\Omega} \operatorname{Pr}_y[A(a,y)=1]\\
& < & \frac{|\Omega|}{|X|} + \frac{\epsilon}{2},
\end{eqnarray}
We therefore have that $\epsilon \cdot |X| < |\Omega| + \epsilon/2 \cdot |X|$ and so $|\Omega| > (\epsilon - \epsilon/2) \cdot |X| = \epsilon/2 \cdot |X|$, as required.

I hope that this is clear.


Does splitting random data reduce its security?

One way to think about this is that you are defining an encoding, and that this is just a change in representation. You are representing a 32-bit value as 3 words, and importantly this is a reversible process. Since it's a bijective mapping, there's as much entropy in the output as there is in the input.

Really, what you're doing is not fundamentally different from representing the 32-bit value in 9 base 10 digits. It's true that there is notable bias in the leading digit, but the important thing is that the full range is covered and it's invertible.


Is it possible to do partial message authentication?

My guess is that you want to prove that the message you sent is a part of a bigger message without showing the entirety of the bigger message to prove so.
A solution that comes to mind is to make the authentication hash is the hash of the hashes of the other messages. That way you can confirm that this message is a part of the bigger message you sent without revealing the actual bigger message.


RSA is not done over field. When using RSA, you rely on the fact that the adversary does not know the order of the multiplicative group, i.e. he does not known the value of Euler's totient function and he is unable to compute it.

Over field, computing it is trivial.


Encryption algorithm multiple threads/cores for higher throughput

Typically, it is thought that an encryption algorithm is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.

This is only true for "heavy-handed" operations like CBC-MAC (and its variants), HMAC and CBC. For most of modern cryptography as implemented, parallelizability is both a feature an a necessity for high performance implementations.
Before jumping to the schemes that are relevant to you in this context, let me clarify why parallelism is actually a necessity. You might have heard of the AES-NI. These are instructions that perform one AES round per instruction. However, the instructions don't have a latency of 1 CPU cycle but of 3-7 CPU cycles even though they have a throughput of at least 1 instruction per cycle. Latency in this context means that if instruction B depends on the result of instruction A, B must wait for the full latency of A. So, what you need to do to optimally use your hardware is to have 8 data-independent AES operations be run in parallel which is quite tricky with request-level parallelism. So instead what schemes do, is they use a parallelizable scheme and don't compute one block of AES data at a time, but rather 8 or however many is optimal for the implementation.
But how can this be done, you surely ask yourself:

If you want CPA-secure encryption, CTR-mode transforms a block cipher into a stream cipher by encrypting a counter.
If you want a nonce-based MAC, GMAC can be parallelized - which is commonly exploited to reduce the number of reductions to compute.
If you want a full-blown parallel PRF, PMAC is the way to go, though it is not seen as often in practice due to the prominence of HMAC or single-block AES where needed.
If you want a parallel hash algorithm, you can use tree-hashing.
If you want authenticated encryption, AES-GCM can be parallelized - as it is essentially composed of GMAC and CTR.
If you want nonce-misuse-resistant authenticated encryption, the generic SIV transform and AES-GCM-SIV both require two passes but each pass can be parallelized - at least for the encryption, the decryption is natively parallel.


As suggested, here is a hopefully entry-level precis of the paper linked in the comment above.
A Discrete Logarithm based asymmetric key system lacks a true trapdoor function - you can't compute a pre-image for an arbitrary image. Instead, a Schnorr signature relies on a slightly weaker condition. A generalized Schnorr signature can be considered to have two parts:

a function $O_{K}(i, s)$ taking public key, $K$, an input $i$ and a signature $s$. In ECC, the main component of $O_K(i,s)$ is a bit representation of $s\cdot G+i\cdot K$, where $G$ is the canonical generator for the ECC group and $x\cdot h$ is multiplication of the curve point $h$ by the scalar $x$. Other data may be appended to this bit representation, such as the message to be signed and the list of candidate keys in the ring signature. Generally, it must contain enough information to precisely specify the claim the signature is intended to prove, so that the signature can't be replayed in any other context.
a hash function $H(o, m)$ which takes $o$, any output of $O$, and $m$, the message to be authenticated.

$O$ has the additional property that, knowing the secret key corresponding to $K$, it is possible to construct arbitrarily many $o'$ where it is possible to find $s$ for any given $i$ s.t. $o' = O(i, s)$. i.e. there are specific outputs where we can solve for the signature given any input. Call this a preimageable output.
In a standard Schnorr signature we...

construct such a preimageable output $o'$ and pass to $H$
take $i = H(o', m)$ and solve for $s$.
Our signature is $(i, s)$

We verify by checking $i = H( O_{K}(i, s), m )$, i.e. that the input to $O$ is equal to the output of $H$.
Assuming we know the secret key for $K_{1}$ in a set of $K_{1 ... n}$ public keys, we can construct a ring signature as follows:

Construct $o'_{1}$, a preimageable output of $O_{K_{1}}$
Calculate $i_{1} = H(o'_{1}, m)$
Calculate each $i_{j+1} = H( O_{K_{j}}(i_{j}, s_{j}), m )$ for a randomly chosen $s_{j}$
Finally, with $i_{1} = i_{n+1}$ solve $o' = O_{K_{1}}(i_{1}, s_{1})$ for $s_{1}$

The ring signature is the sequence of $(i_{j}, s_{j})$ and is verified by checking that for a chosen $i_{j}$ a round-trip of the ring gives the starting value.
The actual construction is a little more complex. The hash includes the complete set of public keys, for example. But this should give the idea of how it works.


can half of an encrypted photo be decrypted with the key?

OK, for clarity I'll quickly summarize your scenario:

You have the key and know the encryption algorithm.
You have 60% of the cipher text of an image encrypted under above key and algorithm.
You seek to decrypt the cipher text and reconstruct the full image.

There are two possible answers to this:

It's pretty much impossible. If the 60% are highly fragmented and you only got a bit of ciphertext every now and then, you may either suffer from desynchronization (if you don't know how large the gaps are) or you'll lose potentially even more information because you can't decrypt all the bits (highly dependent on the mode of operation in use)
You're lucky and have about 60% of the picture as a continuous block. This means that chances likely are that you can fully decrypt those 60% of the cipher text and start reconstruction of the image. How much of the image you can recover from 60%, I don't know. I suspect it depends on the details of the format and how interrelated the pixels for it are.


Are HMACs based on hashes with larger bit-lengths also more secure?

HMAC-SHA-256 is sufficient for up to 256 bit security. Confer e.g. NIST SP 800-107. This recommendation is based on the premise that collision attacks are infeasible against common uses of HMAC, and that you consequently only have to worry about primary pre-image attacks that attempt to recover the secret key (and use this for forging subsequent messages).

SHA-256 has 256 bit security against primary pre-image attacks. This is sufficient for all practical purposes.


Is clientside encryption to hide data from server safe when using SSL?

Client-side encryption can prevent a passive eavesdropper on the server's memory—like Heartbleed—from seeing the client's secrets.  But, if you might be concerned about any more serious compromise of the server, who delivers to the client the JavaScript code that performs encryption?


You can find the folowing information in the book Katz, Lindell "Introduction to modern cryptography".

  PROPOSITION 13.6 Let $N=p q$ , where $p, q$ are distinct odd primes of
  equal length. Then:

  $\operatorname{gcd}(N, \phi(N))=1.$
  For any integer $a \geq 0,$ we have $(1+N)^{a}=(1+a N) \bmod N^{2}.$

  As a consequence, the order of $(1+N)$ in $\mathbb{Z}_{N^{2}}^{*}$ is $N .$ That is, $(1+N)^{N}=1 \bmod N^{2}$ and $(1+N)^{a} \neq 1 \bmod N^{2}$ for any $1 \leq a<N .$

  $\mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*}$ is isomorphic to $\mathbb{Z}_{N^{2}}^{*},$ with isomorphism $f : \mathbb{Z}_{N} \times \mathbb{Z}_{N}^{*} \rightarrow \mathbb{Z}_{N^{2}}^{*}$
  given by
  $$
f(a, b)=\left[(1+N)^{a} \cdot b^{N} \bmod N^{2}\right]
$$

It means that $n$ divides the order of $g=f(a,b)$ iff $L(g^\lambda \bmod n^2)=a\cdot \phi(N)\in \mathbb{Z}_{N}^{*}.
$


Avoiding overflow when encrypting with RSA

Actually, the fundamental mathematical operation is not
$$
\begin{align}
  \mathbb{N} &\to \mathbb{N} \\
  m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\), divide by \(n\) and take the remainder)} \\
\end{align}
$$
but
$$
\begin{align}
  \mathbb{Z}/n\mathbb{Z} &\to \mathbb{Z}/n\mathbb{Z} \\
  m &\mapsto (m^e) \bmod n & \text{(elevate to the power of \(e\))}\hphantom{\text{, divide by \(n\) and take the remainder}} \\
\end{align}
$$
It is an operation in modulo arithmetic.

In computations, the elements of $\mathbb{Z}/n\mathbb{Z}$ are almost always represented by the representative in the range $[0,n-1]$. Each elementary operation is performed in $\mathbb{N}$, then the result is truncated modulo $n$. For example, if $n$ fits in $k$ machine words, then a multiplication of two elements of $\mathbb{Z}/n\mathbb{Z}$ can be performed by computing the product, which fits in $2k$ machine words, then taking the remainder modulo $n$, yielding a representation of the element of $\mathbb{Z}/n\mathbb{Z}$ that is again in the range $[0,n-1]$ and in particular fits in $k$ words. Taking the exponential of a number involves a series of multiplication, each of which is truncated to $[0,n-1]$ in this way so as to obtain the smallest representative of the element of $\mathbb{Z}/n\mathbb{Z}$.

Even multiplication of two $k$-word numbers can be performed with intermediate values fitting in $k$ words. The naive method is wasteful both in the amount of memory and in that it builds a large number only to divide it afterwards. Methods such as Montgomery multiplication avoid computing a double-size number by reducing the size of the result after each intermediate step in the multiplication.


Is it feasible to design a crypto scheme for centralised reporting of anonymized data?

Ok, here's what I got:

Someone selects two large primes $p$ and $q$ such that $n = 2pq + 1$ is prime, and $pq$ is large enough to make factorization infeasible; they select a value $g$ with order $p$ in $Z^*_n$ and a value $h$ with order $q$ in $Z^*_n$ (e.g. select a random $s$ in the range $[2, n-2]$ and set $g = s^{2q} \bmod n$ and $h = s^{2p} \bmod n$ and verify that neither $g$ nor $h$ are 1).  Someone (and it need not be the same someone) also selects a symmetric encryption key $k$.
The authority gets the values $q, n$ (and optionally the values $g, h, p$; the authority doesn't need them, but it wouldn't hurt security), the authority does not get $k$. Each "reporting party" gets the values $g, h, n, k$.
For a reporting party to convert original information $i$ into derived information, he first deterministically encrypts $i$ with the key $k$ (forming $E_k(i)$), selects a random value $r$, and computes $d = g^{E_k(i)}h^r \bmod n$, which is the derived information, which he can send to the authority.
For the authority to compare two derived information $d_1, d_2$ to see if they correspond to the same original one, he computes $(d_1 d_2^{-1})^q \bmod n$, if that is 1, then the original information is the same.

This works because $d_1 = g^{E_k(i_1)}h^{r_1}$ and $d_2 = g^{E_k(i_2)}h^{r_2}$, hence $(d_1 d_2^{-1})^q = (g^{E_k(i_1)}h^{r_1} \cdot g^{-E_k(i_2)}h^{-r_2})^q = (g^q)^{E_k(i_1) - E_k(i_2)}$, which is 1 if $E_k(i_1) = E_k(i_2)$, that is, if $i_1 = i_2$

As for your requirements:

1) The authority does not directly receive original information

2) The authority can compare two different derived information; it cannot otherwise reconstruct the original information; that is because of the symmetric key $k$; given $g^{E_k(i)}$, the attacker might be able to recover $E_k(i)$ (actually, he couldn't, however if the $E$ function was public without a secret $k$, he could, given the short range of possible $i$ values), however because he doesn't know $k$, that's as far as he could go.

3) Reporting parties are dynamic; all reporting parties are given the same information, and so adding more is not an issue; they cannot determine if other parties have contributed the same information; because they don't know the orders of $g$ and $h$, they cannot determine this.

4) Two or more parties cannot collaborate to subvert the system; because all reporting parties get the same information, two parties don't have any more power than one.

Now, a reporting party and the authority could collaborate to recover another reporting party's original information; this is actually inherent in the problem, and so is not an issue (at least as far as I'm concerned; you may consider it a deal-breaker, in which case you need to rethink the problem).  You could make it somewhat more difficult by replacing an invertible encryption function $E$ with a keyed hash $H$ (and assume that two different inputs just don't collide); however given the small range of the original information, it won't help that much...


Entropy after shuffling result of /dev/urandom

I can understand paranoia.  They're probably recording everything I type.

There's good paranoia of the sort that gets the adrenaline pumping, sharpens the reflexes and gives you the energy to turn that sabre tooth tiger into dinner and moccasins.  Unfortunately, I think that you might be suffering from the bad type of paranoia.  This has led you to think irrationally (sorry).

Let's assume that your urandom seed is generated magically and is cryptographicly safe, and uniformly distributed.  It's about as good as its going to get without a true random number generator.  You then transmit it and the bad people read it.  Is this your compromised? So security = 0.

You then start manipulating it by slice and dice.  This is a speculative calculation, but I would suggest that the only security you add is the decision where to chop the seed.  So if you chopped and swapped a 32 byte (256 bit) seed  at some random place, you add log2(32) bits of entropy.  That's 5 bits. Perhaps you add another 5 if you chop and swap again.  Ultimately though, you can only generate an absolute maximum of 32! byte permutations /combinations.  It will be less in reality as some bytes might be equal (and I can't do the maths). That's a maximum of 118 bits, which is less than  half of your original entropy. And you have to realise that a human is very poor at thinking of random things in his head.  The 5 bits might actually only be 4 or even less. (Have scientific studies been done of human generated entropy?)

You can see where bad paranoia can take you?  Taking of other solutions, urandom isn't magic.  It's a CSPRNG (SHA1 or ChaCha) which you either have on your client computer, or can implement using one of the many kosher algorithms. You might even have access to a Windows version of /dev/urandom if that's your bent.

In summary, it all falls apart when you believe THEY read your SSH traffic.


How to prove a pseudo-random function has certain expansion factor

The concatenation operator $||$ in e definition $F$ ensures an expansion $n \rightarrow 2n$ since both $F_0$ and $F_1$ map $n$ bits to $n$ bits.

The argument for $F'$ is similar since repeated application of two $n$ bit to $n$ bit functions gives an $n$ bit to $n$ bit function, and four of those are concatenated in $F'$.


What does Maj and Ch mean in SHA-256 algorithm?

The definitions given in FIPS 180-4 are
$$\begin{align}
\operatorname{Maj}(x,y,z)&=(x\wedge y)\oplus(x\wedge z)\oplus(y\wedge z)\\
\operatorname{Ch}(x,y,z)&=(x\wedge y)\oplus(\neg x\wedge z)
\end{align}$$
where $\wedge$ is bitwise AND, $\oplus$ is bitwise exclusive-OR, and $\neg $ is bitwise negation. The functions are defined for bit vectors (of 32 bits in case fo SHA-256).

$\operatorname{Maj}$ stands for majority: for each bit index, that result bit is according to the majority of the 3 inputs bits for $x$ $y$ and $z$ at this index.

$\operatorname{Ch}$ stands for choose (source: poncho) or choice, as the $x$ input chooses if the output is from $y$ or from $z$. More precisely, for each bit index, that result bit is according to the bit from $y$ (or respectively $z$ ) at this index, depending on if the bit from $x$ at this index is 1 (or respectively 0).


What is the relevance of "physical layer security" to cryptography?

Driven by the saying "secure by design", scientist start thinking about how they gonna secure the network while they are designing it. Cryptography is happening in the network layer. Scientists wishing that, by adding some security features in the physical layer, this will improve the security of the information in the upper layer and overall. In the future, millions of devices will be connected together and crossing each other… securing them by cryptography alone is a scary idea.


Same 64-bit preimage resistance security for SipHash and SHA-512/64?

SipHash doesn't claim to be a secure hash function. Only a secure MAC. So if you try to use it as a hash function, with a constant, public key, you are on your own.

SHA-512/64 should be a "secure" 64-bit hash, which is of course not enough for a truly secure hash, since it only has 32-bit collision resistance. However, since you only desire preimage resistance, it may have its uses.

  How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?

That depends on the attacker's computational power, of course. With a typical desktop CPU you can calculate around $2^{20}$ to $2^{25}$ SHA-512 hashes per second. So a brute force preimage search would take maybe $2^{40}$ seconds, or tens of thousands of years. GPUs could reduce that by a large factor, but it would still likely be centuries.

However, the whole bitcoin userbase is currently (as of early 2016) hashing over $2^{60}$ hashes per second, and even taking into account a small additional factor from SHA-512 vs. SHA-256, you'd be inverting the hash in less than a minute at that rate.

If you want something that takes longer to invert, you should use a password-hashing function, like scrypt with sufficiently large parameters.


Is there a format preserving cryptographically secure hash?

Cryptographically secure hashes usually work on bitstrings of arbitrary length and output a fixed length bitstring. The secure part is being collision resistant and preimage resistant, so that you have a practical oneway function, and those are the properties you want for "scrambling".

As fgrieu psted in the comments, one easy way to do this is to utilize an encryption scheme, and use the plaintext for the key as well. That means, in order to decrypt the ciphertext you would need the plaintext. Formally:

$$F(p):= E_p(p)$$
with $E_k(p)$ denoting an encryption method with key $p$. If you want to utilize format preserving encryption, you might have to make adaptions how the plaintext actually is used for the "key input".

One more remark: Usually the key should be generated uniform randomly, and depending on your format, this might not be true. Therefore, if you use a normal hash function on the input $p$, then you should get a uniformly distributed hash value, and if you use this as key, you should be fine. Theoretic remark: In the random oracle model this should work just fine. So, we can adapt this to:

$$F(p):= \hat{E}_{H(p)}(p)$$

with a format preserving encryption function $\hat{E}_k(p)$ and a cryptographically secure hash function $H(p)$, where the key length $|k|$ is equal or less than the length of the output of the hash function $|H(p)|$.


Side Channel Analysis (CorrPA), comparison between HW-results and measured power traces

You should use the value you found (in watt). Try to have a look at this  file, it's really well explained in my opinion. If you look for page 21 for instance, you'll see that the plaintext produces a certain waveform; then, after the hypotesis and the S-Box output, the correlation is clearly done with the power model obtained and the value of the traces (page 23)


What you are looking for is explicitly specified in the IEEE Standard 1363.1 [1], which covers NTRU. In particular, encoding a bit string into a polynomial is done in the following manner: Once you have processed the input message, you divide it into blocks of 3 bits, and transform each block in a pair of coefficients of a ternary polynomial according to a predefined table (described in 9.2.2.h of [1]):

{0, 0, 0} is converted to {0, 0}
{0, 0, 1} is converted to {0, 1}
{0, 1, 0} is converted to {0, –1}
{0, 1, 1} is converted to {1, 0}
{1, 0, 0} is converted to {1, 1}
{1, 0, 1} is converted to {1, –1}
{1, 1, 0} is converted to {–1, 0}
{1, 1, 1} is converted to {–1, 1}

Note that the input bit string needs some processing before transforming it into the polynomial (also described in section 9.2.2).

Also note that we assume the original message is a bit string, so it doesn't matter which was the codification of the original text string (ASCII, UTF-8 or whatever); that should be a problem of your application, not of the encryption algorithm.

References:

[1] IEEE Std 1363.1 - IEEE Standard Specification for Public Key Cryptographic Techniques Based on Hard Problems over Lattices. 2008.


What will happen if I use RSA encryption for plaintext larger than RSA bit size?

If you have an RSA public key $(e, N)$ (in the case of RSA2048 $N$ will be 2048 bits) and private key $d$ then you can only encrypt messages $m$ whose integer representation is less than $N$.

Recall that in RSA encryption is defined as $c = m^e \text{ mod } N$ where $c$ is the resulting ciphertext, and decryption is defined as $m = c^d \text{ mod } N$. The key insight is that decryption cannot produce an $m \ge N$ because of the modulo $N$ operation (the remainder of division by $N$ must be less than $N$). Thus if we encrypt an $m \ge N$ decryption will not produce the correct value.

To get around this it is possible to break $m$ up into chunks that are smaller than $N$, encrypt the chunks, and then recombine the chunks after decrypting to form $m$. For example ($||$ denotes concatenation):

$$m = m_1 || m_2$$ $$c1, c2 = Enc(m_1), Enc(m2)$$ $$m = Dec(c_1) || Dec(c_2)$$

More things to consider beyond this are space that padding will take (unpadded RSA is not secure), and whether you should be using a symmetric cipher like AES which is more suited for encrypting large amounts of data (RSA is much slower than symmetric ciphers and was not designed to encrypt large amounts of data).

Edit: If we do encrypt a message $m \ge N$ the ciphertext $c$ resulting from encrypting $m$ will not decrypt back to $m$. Example using some small parameters:

$$p =17, q = 19, N = p*q = 323, e = 5, d = 173$$
$$m = 400$$
$$Enc(m) = c = 400^5 \text{ mod } 323 = 229$$
$$Dec(c) = m' = 229^{173} \text{ mod } 323 = 77$$

Note that $m \ne m'$ and thus for values $m \ge N$ RSA does not decrypt properly. In fact, for any value $m \ge N$ encrypted via RSA the ensuing decryption will produce $m \text{ mod }N$ instead of $m$ (as is the case in the example: $77 = 400 \text{ mod } 323$).


As Paŭlo Ebermann already mentioned in his comments, SHA3 can indeed be used as a pseudo-random number generator.

The paper "Sponge-based pseudo-random number generators" talks about just that and it also describes a clean and efficient way to construct a re-seedable PRNG with a (Keccak) sponge function. What you'll get is a PRNG based on a cryptographic hash function… with the usual security implications.

For example: the paper explicitly states that you should reseed regularly with sufficient entropy to prevent an attacker from going backwards on the period of the PRNG (which is probably what you've been hearing about).

Related to proof of security of such a sponge-based PRNG construction, the paper states that the presented PRNG has the property of indifferentiability (which practically claims it is indifferent to an ideal PRNG), a resistance against state recovery (which is a result of it's indifferentiability), and that it passed the statistical tests proposed by NIST. This is the result of the fact that the sponge-based PRNG construction inherits the provable security properties of the sponge construction itself.

I would like to advise you to check on the paper yourself to grasp all the details; like learning how and when to re-seed the PRNG to prevent some potential attacks. It answers your question with ample detail.


What is the hard problem for this algebraic encryption construct?

I want to get a good characterization of the construct so that I may describe it accurately.

I would characterize it as "insecure".

If someone has a ciphertext, and manages to guess the plaintext it corresponds to, then they can compute:

$$\text{gcd}(E_I(M) - M, N)$$

and they'll give then the factor $p$.


Entropy of two concatenated random values

Even in context, much of what is written in the blog post makes no sense. E.g., it says:

  While it can be argued that the DRNG is in reality just splitting a 128-bit value into two pieces and handing them to you one piece at a time, from a theoretical viewpoint this does not matter. While the original value had 128 bits of entropy, the end result is that you are handed two 64-bit numbers one at a time, each of which only has 64 bits of entropy. Because they come from a pseudorandom number generator, the entropy is additive when the values are concatenated, and the resulting 128-bit number has only 65 bits of entropy.

This is just wrong. If you have a 128-bit string that's truly uniform (i.e., has 128 bits of entropy) and split it in half then concatenate the halves, you clearly still have the original string and thus 128 bits of entropy.  The rest of the post is a similar muddle, so I wouldn't give it much credence.

Entropy of independent random strings is indeed additive, but not in the way the post says. Concatenating independent strings having entropy $n$, $m$ yields a string of entropy $n+m$, full stop.

Note however that the strings need to be truly independent to reach this conclusion. Strings generated as outputs of a deterministic RNG algorithm will not be truly independent, and in fact their concatenation will not have any more true entropy than that of the seed provided to the RNG (and may even have less).

I don't know whether the outputs of these Intel instructions can be considered independent or not, but either way this aspect of the blog post is incorrect.


complexity of iterative squaring in relation to factorization

Let $m = pq$.  Computing $A := a^{2^t} \pmod m$ requires $t$ $2n$-bit modular multiplications.

Now if you know the factorization of $m$ (i.e., $p$ and $q$) then you can evaluate $A = a^{2^t} \pmod m$ from  $A_p := a^{2^t} \pmod p$ and $A_q := a^{2^t} \pmod q$ using Chinese remaindering:
$$
A = A_p + p\bigl[i_p (A_q-A_p) \bmod q\bigr]\quad\text{where $i_p = p^{-1} \bmod q$}
$$

The computation of $A_p$ (resp. of $A_q$) requires $t$ $n$-bit modular multiplications.  Assuming that $i_p$ is pre-computed, the computation of $A$ thus requires $(2t+1)$ $n$-bit modular multiplications.


Limiting password length to "prevent hash function splitting into multiple hashes"?

The infamous "LANMAN hash" used in older Windows versions had a problem where it split passwords into 7 byte chunks and computed a hash for each separately. This, together with lack of salt, and other poor design decisions meant that a password of "keyboard42" and a password of "KeyBoarMint" store the same first value, making it uniquely vulnerable to a time-space tradeoff called "Rainbow tables" in which an adversary pre-calculates lots of data and then needs very little work to reverse an password hash.

Not only are the modern schemes you've mentioned proof against such attacks, even in the 1970s a competently designed password hash was not vulnerable to Rainbow tables. The advice you were given is very poor.


How can I generate reasonably short temporary unlock codes?

Use hash based cryptography.
First, define a one way function F. It takes as input a small (10-16 byte) string and uses a secure hash function (EG:SHA2) to produce another string of the same size.
We number each day from (Jan 1 2000) to (Jan 1 2100) with a number n (n=0 ... 36500)
Each day is assigned a code. If the user has the code for a particular day, they are allowed to use the software for all days leading up to and including that day. If we supply the code for day x we don't care if the user can find the code for day x-1 since the code for day x allows them to use the software on that day too. With that in mind, we do the following:
code(x)=f(code(x+1))
The codes form a chain. For each installation, you pick a random code for day 36500 then hash it repeatedly until you get the code for day 0. You then sign a message telling the application the day 0 code.
At that point, give out the code for a particular day to unlock the software up to that date.
Anyone can apply F to a code to get the code for the previous day. But they can't reverse F to get the code for the next day. Since you picked the code at the beginning of the chain you have all of them. This is the asymmetry that makes this system secure. Yes, asymetry ... this is public key cryptography.
To verify a code, the application applies F repeatedly until it reaches the day 0 code. If this does not happen within whatever the set length of the chain, the code isn't valid. Keep a counter during this process to get the code number. Enforcing this limit is not necessary for security it just times out the verification process if the user makes a mistake when entering the code.
Implementation
F can be truncated SHA2. The number of bits kept determines the security level. 80 bits is plenty.
You'd need a binary to text encoding to make this something humans can read and enter into your application.
My current machine can do ~1e6 SHA2 ops per second. That's 3000 years worth of unlock codes. Traversing the chain for generating codes on the server and verifying them on the client won't take much time.
Trusting the Clock
This relies on the application having access to the right time. Users can always change the system time so that's not something a license enforcement system can fix. If the application does something time sensitive (Like recording timestamped records) users might not want to run the software with the wrong time. I'd recommend keeping an internal saved time value which increases while the software is in use and can never run backwards. That's the best you can do. The user is always free to make a system image and restore from backup as many times as they like.
Some things you should already be doing.
I'm assuming you already have a per install ID saved somewhere. That's kind of a requirement for this. Each installed copy of the software has to have a unique ID, a code(0), and a stored signature of the (ID,code(0)) pair for this to work. This prevents the client from deploying lots of identical images of the same installation and using the same code for all of them. This is another thing that can't really be helped.
If you give the client software that gets installed on a machine and will run, the client can make a full system backup. As I mentioned before, they can restore from backup and turn back the clock as many times as they want. But they can also re-image another machine from that same backup. Handling both of these cases is a cat and mouse game of them trying to spoof the environment your application runs in and you trying to make sure they're not doing that.
Deriving an ID from hardware Is one simple option. This prevents the same license data from working on another machine ... but IDs can be spoofed. In this cat and mouse game you try to get legitimate unspoofed HW ids and the client tries to feed your application spoofed values. There isn't anything that can be done about this short of special hardware like TPMs.


Iterated ciphers need variability between rounds to resist so callad Slide attacks. One common way to thwart this attack is with a key schedule generating different round keys for each round.

Slide attacks exploit the repeating rounds of the cipher by finding a collision between one input plaintext and the intermediate value after one round of encryption of some other plaintext. This collision gives a "slid pair" and gives the attacker two known input/output pairs of the round function which in many cases is enough to recover at least parts of the key.

In the question we have a balanced Feistel cipher where every round uses the same round function and key. Due to the birthday paradox we expect to find a slid pair with on the order of $2^{n/4}$ chosen plaintexts or $2^{n/2}$ known plaintexts, breaking the cipher.


Create self signed certificate from modulus, private and public exponents of RSA

Yes, it is possible to generate a self signed certificate. If you've got a private key that can sign with it using the required signature algorithm then that should always be possible. Tool usage (such as openssl, which can be used to generate self signed certificates) is off topic here, but basically you just create the To Be Signed (TBS) part of the certificate and then, well, you sign it.

Yes, you can get the factors from this answer which is about calculating the CRT parameters, but those include the $p$ and $q$ values.


Does anyone have a reliable source for this?

Well, you are asking about the definition of a CSPRNG, and whether this second criteria is a necessary part.

Well, it comes down the to exact definition of the term 'CSPRNG'.

If we define a CSPRNG as something that generates output which is indistinguishable from random (your first criteria), then a CSPRNG need not meet the second criteria.  This can be seen by the observation that this definition relies only on the output, while the second criteria is also defined in terms of the internal state.  It would be easy to take a CSPRNG (which meets the first criteria), and add internal state that would allow someone to reconstruct previous outputs; this modified generator would continue to meet the first criteria (we haven't changed the output), but it would prevent it from meeting the second criteria.

On the other hand, if the term 'CSPRNG' includes the second criteria, well, that's obviously a necessary part.

When I use the term 'CSPRNG', I personally mean something that meets the first criteria (and if I also need the second criteria, I use an additional term such as 'backtracking resistance' to describe it).

The wikipedia article appears to use this as its source.  I would point out that in its list of standardized CSPRNGs, it includes the X9.31 generator, whose obvious implementation does not meet their criteria (if the attacker recovers the internal key, and has a good guess about previous timestamps).

  Is this condition even sensible?

Of course it is; it is useful if you're in a scenario where there is a danger that, at some point, the internal state may actually be exposed.

  If you consider something like RC4; this means that RC4 does not satisfy Wikipedia's second condition for being a CSPRNG?

Well, RC4 is known not to meet the first criteria, and so it's not the best example.  However, ignoring that point, it is certainly true that the obvious implementation of RC4 would certainly not meet the second criteria; it is conceivable (that is, I don't know of a disproof) that there is an alternate implementation of RC4 that generates the same output, and would meet the second criteria.


Can a Cramer-Shoup public key have two different private keys?

Yes, this is possible.

One possible argument is of algebraic nature, using the fact that there is some $a\in\{0,\dots,q-1\}$ with $g_2=g_1^a$ and rewriting the public key's defining equations using this relation.

However, there's a much simpler justification: A Cramer-Shoup public key consists of five elements $g_1,g_2,c,d,h$ of a group of order $q$, hence there are at most $q^5$ possible public keys. However, a private key consists of two freely chosen elements $g_1,g_2$ and five freely chosen integers $x_1,x_2,y_1,y_2,z$ between $0$ and $q-1$, yielding $q^7$ possible private keys. Therefore, there exist (on average) at least $q^2$ private keys mapping to a single public key.

(In fact, the algebraic argument mentioned above shows that there are exactly $q^5$ public keys, each of which corresponds to exactly $q^2$ private keys.)


concerning collision-resistant hash function

When given the question "here's a hash function $H''$ based on a collision resistant hash functions $H, H'$; is $H''$ also necessarily collision resistant?', there are two general ways to answer the question:

We can show how, given a collision in $H''$, we can deduce a collision in either $H$ of $H'$.  That is, if we were given two values $x \ne y$ with $H''(x) = H''(y)$, could we then immediately give two values $z \ne w$ with $H(z) = H(w)$ or $H'(z) = H'(w)$?  If we can, then we can conclude that $H''$ is collision resistant (because if it weren't, that is, if we could find a collision, we'd also find a collision in $H$ or $H'$, and we assumed we weren't able to do that.
We can demonstrate a pair of collision resistant functions $H, H'$ (possibly quite artificial ones, but you won't need that here) that, with the construction, make finding a collision in $H''$ easy.  This would show that $H''$ needn't necessarily be collision resistant.

It turns out that, for all four examples you gave, demonstrating either 1 (for an answer "yes") or 2 (for an answer "no") is quite straight-forward.

Your homework is to figure out the details...


Unpacking the definition of negligible & non-negligible

As @SEJPEM mentioned in the comment: intuitively, for every positive
polynomial $p(n)$ ($n\in\mathbb{N}$) that you take, consider the function $q(n)=\frac{1}{p(n)}$, then we say that the function $\epsilon(n)$ is negligible if from some point $N\in\mathbb{N}$ it follows that $\epsilon(n)<q(n)$. This means that $\epsilon(n)$ reaches 0 very fast because it doesn't matter whether you take $p_1(n)=n$ or $p_2(n)=n^{100000}$, by the definition there would be $N_1$ from which $\epsilon(n)<\frac{1}{n}$ and $N_2$ from which $\epsilon(n)<\frac{1}{n^{100000}}$.

Now, to interpret the definition that you copied: $\lambda_d\in\mathbb{N}$ refers to $N$ in my explanation above, then the definition of negligible function requires that for every $\lambda\in\mathbb{N}$ such that $\lambda>\lambda_d$ (in my explanation above: for all $n$ that is bigger than this $N$) it follows that $\epsilon(\lambda)<q_d(\lambda)=\frac{1}{p_d(\lambda)}=\lambda^d$.

In order to show that $\epsilon(\lambda)=\frac{1}{2^\lambda}$ is negligible you need to show that for every polynomial $p(\lambda)$ it follows that $\epsilon(\lambda)=\frac{1}{2^\lambda}<q(\lambda)=\frac{1}{p(\lambda)}$ from some point $N\in\mathbb{N}$ (this point could be different for different $p(\lambda)$-s. Now take some arbitrary $p(\lambda)$, we can discover this $N$ from which $\epsilon(\lambda)<\frac{1}{p(\lambda)}$ as follows: let $p(\lambda)=\lambda^k$ then we want to find $\lambda$ such that $\frac{1}{2^\lambda}<\frac{1}{\lambda^k}$, thus, we want to find $\lambda$ such that $\lambda^k<2^\lambda$, or in other words, we want to prove that from some $\lambda$ the term $2^\lambda$ is bigger than $\lambda^k$, and this can be proven using the definition of a limit (see this proof).

Now take $\epsilon(\lambda)=\frac{1}{\lambda^{1000}}$, in order to show that it is not negligible you need to show that there exists some polynomial $p(\lambda)$ that violates the definition. Take the polynomial $p(\lambda)=\lambda^{2000}$, there exist no $\lambda_{2000}$ (or $N$) from which $\epsilon(\lambda)=\frac{1}{\lambda^{1000}} < q(\lambda)=\frac{1}{p(\lambda)}=\frac{1}{\lambda^{2000}}$ (i.e. for every $\lambda\in\mathbb{N}$ that you take, it follows that $\epsilon(\lambda)>\frac{1}{p(\lambda)}$.

I hope that it helps.


First of all I'll have to disagree with fkraiem that there are many possibilities. In fact there are exactly four. I'm going to assume that $A$, $B$, $C$, and $D$ are bits. (Or equivalently I'm assuming that they are bit-strings and the operation we are looking for a is a bitwise boolean operation.)
Then I'll make my life a bit easier and define $E=A\oplus B$, since it does not matter what $E$ actually is.

Now, there are exactly 16 possible binary boolean operations. Not all of those actually have their own name, but they technically do exist and we could come up with a symbol for them. Assuming that we are supposed to find an operation and a description of $C$ in terms of $D$ and $E$ such that the equation is satisfied for all possible values of $E$ and $D$.

Then this leaves us with exactly 4 possibilities.

Namely

XOR as the operator and $C=E\oplus D$.
XNOR as the operator and $C= \neg(E\oplus D)$.
The operator that always evaluates to the second value and $C=D$.
The operator that always evaluates to the negation of the second value and $C=\neg D$.

The reason for this can be seen in the following table. For an operation to be viable, we need that it allows us to force any value of $D$ irrespective the value of $E$. This means we require that in the following table the operation has both a $0$ and a $1$ in each pair of columns in the following table. Otherwise there is always at least one combination of values for $E$ and $D$ that makes the equation unsatisfiable. It is easy to see that there are only 4 viable operations.


If so, could using the twisted curve representation of the curve have any performance benefits over the regular representation?

Yes, at least in some cases. To quote Twisted Edwards Curves (section 7):

  One can choose $a$ to be very small, making twisted Edwards curves essentially
  as fast as Edwards curves and thus bringing the speed of the Edwards addition
  law to a wider variety of elliptic curves.

  Even when an elliptic curve can be expressed in Edwards form, expressing
  the same curve in twisted Edwards form often saves time in arithmetic.

  Or is the twisted curve representation only used for the security analysis of the curve?

In addition to the above, twists can also be used to make ciphertexts indistinguishable from random data like in A Public-Key Encryption Scheme with Pseudo-Random Ciphertexts (pdf).


Encryption with 2 symmetric keys and decryption with one key

One solution I was thinking of is to encrypt the data with 2 keys (key1 AND key2) and decrypt it with any of the keys (key1 OR key2). Is is possible?

The immediately obvious way is, when you want to encrypt a record $M$, you select a random key $r$, and generate $Encr_{key1}(r), Encr_{key2}(r), Encr_r(M)$

The decryption process is obvious, using the $key_i$ you have, you recover $r$, and then use that key to decrypt the actual record.

Is there any reason this scheme doesn't solve your problem?


Best practices for saving encrypted user data without a database

This answer proposes a solution based on local storage and local encryption.

The data of the forms that the user enters:

Can be locally encrypted whenever the user wants to save...
The encrypted file(s) can be stored locally, if you want to store it to, you can transfer a copy to your server
The encrypted file(s) can be decrypted locally and restored into forms by JScript. You can use NodeJS.
If the user lost their file(s) then if you saved in your server, you can transfer back to the user to resume.

The methods;

From a password to an encryption key, you can use PBKDF2. Ask the user to a good password to increase against the brute-force attacks.
For encryption of the data, you can use AES-CBC with randomly generated IV. If you want to authentication for the encrypted data, you should, you can use AES-GCM.

Don't forget to ask the user to write the password at somewhere.


Why does a Galois field have to have an order of $p^n$ where $p$ is prime?

Fix a finite field $k$ of $q$ elements, with additive identity $0_k$ and multiplicative identity $1_k$.

For any integer $n$, let $[n]$ be the $n$-fold sum of $1_k$.  Clearly $[a + b] = [a] + [b]$ and $[a\cdot b] = [a] \cdot [b]$.  Since $k$ is finite, for any $n$, in the sequence $[a]$, $[a + 1]$, $[a + 2]$, etc., there must be a repeat; let $p$ be the smallest integer so that $[a] = [a + p] = [a] + [p]$.  Then $[p] = 0_k$, and in the sequence $[1], [2], [3], \ldots, [p]$, the element $[p]$ is the first zero element.
$p$ is called the characteristic of the field.  Suppose $p$ were composite, with factors $1 < a \leq b < p$ so that $p = a\cdot b$.  Then $0_k = [p] = [a\cdot b] = [a] \cdot [b]$, but $[a]$ and $[b]$ are nonzero because $[p]$ was the first zero element in the sequence $[1], [2], [3], \ldots, [p]$.  This is impossible in a field, so $p$ must be prime.
The set $\{[0],[1],[2],\ldots,[p-1]\}$ forms a subfield $k_p$ of $k$, since it is by construction closed under addition and multiplication.  Thus the extension field $k$ forms a vector space over the subfield $k_p$.  Being finite, this vector space is necessarily finite-dimensional, of dimension $n$, and thus has exactly $p^n$ elements.  Hence $q = p^n$ for some $n$.


So here's what you're doing:
$$E_{K_1,IV}(F)||H_{K_2}(F)$$

where E denotes encryption with AES-CBC and H denotes HMAC. This is also known as "Encrypt and MAC".

This scheme potentially has a few issues.

It's (formally) not IND-CPA secure, because an attacker can query the encryption oracle for the challenge ciphertexts and compare the resulting MACs.
The scheme puts higher-than-normal contraints on the MAC, because normally MACs aren't assumed to guarantee not to leak anything about their inputs. With HMAC this isn't a problem though.
The scheme could potentially be vulnerable to POODLE-style attacks if you don't validate your CBC padding properly.

As a secure alternative I highly recommend using AES-GCM if you encrypt less than a few GB per key or AES-EAX if you do. Preferably use some well-known and reviewed implmentation of them because getting AES-GCM right isn't exactly easy. As EAX and GCM are authenticated encryption modes they only expect a unique IV from you and the key and will encrypt and authenticate the message properly.


Why do look up tables speed things up compared to brute force?

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.

Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $k\gets F(k)$. This will take $\mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $\mathcal O(1)$ the entire calculation takes $\mathcal O(2^n)$.

Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $\mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.


What's the difference between symmetric and asymmetic multilinear map?

Symmetric means that the source group and all the intermediate groups are the same, i.e. $\mathbb{G}_1 = \mathbb{G}_2 = ... = \mathbb{G}_{n-1}$ using the notation of the paper you linked, while asymmetric means that they can be different.

Check, for instance, remark 1 on the original paper about multilinear maps.

And about the vectors as indices, the aim is just to identify the levels more clearly. Since you have $2^n$ levels, you could use numbers from $0$ to $2^n-1$ to identify them, but then, increasing the levels with the multiplication would not have this nice interpretation of adding the entries of the vectors (or, equivalently, doing a union of the sets that represent the levels).

In several papers, for the symmetric scenario, we have a ring $R$ and an invertible element $z \in R$. Then, the map goes from $(z^{-1}R)^n$ to $z^{-n}R$. But, since the schemes are actually graded, you can apply the map partially and get elements in $z^{-k}R$ for $k < n$. Then, this $k$ is the level.

So, basically, we have elements of the form $r_i / z$ and you can multiply $n$ of them to get $(\prod_{i=1}^nr_i) / z^n \in z^{-n}R$.

In the asymmetric scenario, instead of a single $z$, we have $z_1$, .., $z_n$. Then, the map goes from $z_1^{-1}R \times ... \times z_n^{-1}R$ to $(z_1^{-1}\cdots z_n^{-1})R$.

So, you have elements $r_j / z_i$ and you can multiply them. But now, you can get any product of $z_i$'s in the denominator, so, it is easier to represent the levels by the exponents of each $z_i$, or, equivalently, with an $n$-dimensional integer vector.

For example, considering $n = 4$, an element $r / (z_1 z_3)$ is in level $(1, 0, 1, 0)$, and an element $r' / z_4$ is in level $(0, 0, 0, 1)$. Therefore, combining them (applying the map partially), gives us $r r' / (z_1 z_3 z_4)$ that is in level $(1, 0, 1, 1)$.

Thus, the vectors used to represent the levels tell us which groups were already used in evaluation of the map.


Let's assume your actual input/output has entropy (which it doesn't for a given string or output hash value).

  If I rehash 606ec6e9bd8a8ff2ad14e5fade3f264471e82251 10x times with the same SHA1 algorithm, would the entropy keep on decreasing?

Yes, but by ever so tiny amount. Hashes are designed so that every bit is dependent on all the bits of the input. Hashes do get into so called cycles after iterating quite a few times, showing that entropy can and does decrease. It is however unlikely to influence practical situations.

The initial hash will of course extract the entropy into a maximum of slightly less than 160 bits.

  If so, would it ever reach a dangerous level to a point where AAA could be recovered?

That's of course nonsense statement; the amount of entropy doesn't influence the one-way-function property of a cryptographic hash function at all.

Let's take an extreme and assume that, after a while, all many messages will generate the same hash (a next to impossible situation in itself). Then the (Shannon) entropy will be lowered. So in this situation it becomes more likely to generate this iterated hash by trying out different messages.

However, if you try and revert it you will find many messages instead of one, and it is impossible to detect which one is the original input message. So if anything, you've just made the function harder to reverse.

As example: I've "hashed" all bits of a fully random message into a single bit by XOR-ing them together. Entropy is hugely decreased to a single bit worth of it. Which message did I use to create this one bit of entropy, even if you (get to) know it is 0 or 1?


libsodium has an API dedicated to stream encryption: crypto_secretstream, which is fully documented here: https://download.libsodium.org/doc/secret-key_cryptography/secretstream.html

Using simply crypto_stream_* or OpenSSL aes-256-cfb would be completely insecure. Without any authentication tags, the stream can be tampered with, without any ways to detect that it happened.

crypto_secretstream lets you encrypt and decrypt a sequence of variable-length messages, and prevents tampering, reordering and truncation.

However, if 50 bytes, then 20 bytes are encrypted, you must decrypt 50 bytes, then 20 bytes as well, in this order.

If you are reading data from a TCP connection, you can accumulate it into a fixed-size buffer, and once that buffer is full or you have reached the end of the stream, encrypt or decrypt its content. This will also improve performance and minimize the overhead of authentication tags over encrypting the outcome of ever single read() call.

If the session is interactive, your options are:

Pad messages to the chunk size (sodium_pad(), sodium_unpad()) before encrypting them. This uses more bandwidth, but improves security by revealing less information about the message sizes.
Prefix each ciphertext with its size, so you know how much data has to be read before being decrypted.


That predicate is basically telling you that the resulting ciphertext does not leak any information about the plaintext that has been encrypted.

Assume that there exists some predicate $\Phi'$ such that $Pr[\Phi'(E(k,m_0)] \neq Pr[\Phi'(E(k,m_1)]$, for some $m_0,m_1$ pair. Then, if you are given a ciphertext that corresponds to some of those two messages, computing that predicate you can tell whether $m_0$ or $m_1$ was encrypted, which means that your cipher does not provide perfect secrecy.

For a more precise enunciation, you can check Lemma 2.4 of Katz & Lindell's "Introduction to Modern Cryptography" and its proof, where the predicate used there is $\Phi(c)$ := "$E(k,m)=c$", for $k\in K,m\in M$. And then, you have $Pr[E(k,m_0)=c] = Pr[E(k,m_1)=c]$.

You can try to think of any other predicate. The important thing is that no such predicate must exist.


Is there a good reason not to mention that ECC is weaker than RSA on a quantum computer?

I mainly see two reasons against comparing the quantum attack cost of RSA and ECC:

If your threat model includes (large) quantum computers, you should neither promote RSA nor ECC : they both scale badly against them, and any argument about which is stronger or weaker is marginal.
Since quantum computers large enough to be useful do not exist as of today (2017), it is to soon to compare precisely the two schemes, since the quantum computer’s architecture (as in “Von Neuman architecture”, not x86 vs PowerPC) is far from settled. Many different theoretical models exists (circuit model, measurement based quantum computers, Clifford computation with magic states, etc.), different universal sets of gates and fault-tolerant architectures are proposed, and work on quantum compilers is only starting. For a theoretician, this in “not really important because all these models are polynomially equivalent”, put this might easily reduce (or increase) the gap between ECC and RSA.


perfectly secret with key chosen uniformly

What now follows "My attempt" (added by kelalaka from here) is IMHO a good refutation of the proposition.
The king of proofs is a well-justified counterexample.


How does the length of the plaintext affect the cipher strength?

I'm still a little unsure what your question is, but I'll try and answer what I think you're asking. If it isn't, please clarify your question or comment below.

Let us assume that $E_k$ is an ideal block cipher$^{[1]}$, and so acts like a random permutation of $2^{64}$ elements.

  Given $(m,c)\in M\times C$ find $k\in K$ such that $E(m,k)=c$. How long will this take?

In total there are $2^{64}!$ permutations of $2^{64}$ elements, but we are only interested in the ones that map $m$ to $c$. As such, we are actually looking at how many ways there are to permute the remaining elements, so there are $(2^{64}-1)!$ permutations.
 So, of the $2^{64}!$ permutations we expect $(2^{64}-1)!$ will map $m\to c$, meaning we expect that
$\frac{(2^{64}-1)!}{2^{64}!}=2^{-64}$ of keys will be suitable. So, it should take around $2^{64}$ key guesses.

  Given $(m,c)\in M\times C$, how many $k\in K$ are there such that $E(m,k)=c$

Since there are $2^{256}$ keys, and we expect to find a suitable $k$ with probability $2^{-64}$ trials, we expect there to be $2^{256-64}=2^{192}$ possible keys.

  So, how many trials should it take to find the correct key?

The important thing to notice here is that, no matter how many trials you run, with just one plaintext-ciphertext pair there will still be lots of false positives, and you will have no way of knowing which is correct. The obvious solution to this is to take more $(m,c)$ pairs, but how many? Suppose we have $n$ distinct $(m,c)$-pairs. Then, a false-positive key must fix these $n$ points, leaving it a permutation of $|M|-n$ points. Following the same logic as above, that means the probability of hitting a false-positive key is
$$P = \frac{(2^{64}-m)!}{2^{64}!}
    = \frac{1}{2^{64}\times (2^{64}-1)\times\cdots\times(2^{64}-m+1)}
$$
We want $P\ll2^{256}$, since at this point we can reasonably assume that even in all $2^{256}$ keys there isn't a false positive. As such, $5$ pairs would be sufficient.

I leave it to the reader to consider how long such an attack would take$^{[2]}$.

The assumption on $E_k$ is an ideal cipher is important. For example, the function given below certainly cannot be modelled as a random permutation, but finding a preimage pair $(m,k)$ is trivial for any $c$.
$$E(m,k)=\begin{cases}
  m & k=0
\\0 & k\neq0
\end{cases}$$
Hint: If $E(m_1,k)\neq c_1$, then we do not need to calculate $E(m_2,k)\stackrel{?}{=}c_2$. So, how many times do we calculate $E(m_2,k)$? How about $E(m_3,k)\ \dots$


The challenge c in Sigma protocol (using Fiat Shamir)

No. Since 0x1234, 0x4321 is public and thus known ahead of the execution, the prover knows the challenge c before sending t. This violet the requirement of the sigma protocol: c is sent to P after t is received.


How to split up $GF(2^{128})$ into smaller fields?

When you have a finite field $\mathbb{K}$ of cardinal $q$ (necessarily, $q = p^m$ for some prime $p$ and integer $m$), then a finite field $\mathbb{K}'$ of cardinal $q^k$ can be defined for any integer $k$, in the following way. You consider $\mathbb{K}[X]$, which is the ring of polynomials whose coefficients are in $\mathbb{K}$. Polynomials can be added and multiplied together, and you can defined an euclidian division on polynomials. Then, choose some polynomial $P \in \mathbb{K}[X]$ of degree $k$. You can then consider polynomials of $\mathbb{K}[X]$ modulo $P$: these are all polynomials of degree up to $k-1$, and when you multiply two of them together, you do a division by $P$ and keep only the remainder.

These polynomials taken modulo $P$ form a ring of cardinal $q^k$. If you chose $P$ to be irreducible (i.e. there is no polynomial $R$ of degree strictly more than $1$ and strictly less than $k$ that divides $P$ exactly), then the ring you got is actually a finite field: that's your $\mathbb{K}'$. This is called a field extension because the elements of $\mathbb{K}$ naturally map to the polynomials of degree $0$ of $\mathbb{K}[X]$, so $\mathbb{K}$ can be said to be a subfield of $\mathbb{K}'$.

It may help to think of this construction as the same thing as the construction of complex numbers $\mathbb{C}$ over the reals $\mathbb{R}$: in $\mathbb{R}$, the polynomial $X^2+1$ is irreducible (there is no real whose square is $-1$); so we define complex numbers as $a+bX$, and then $(a+bX)(c+dX) = ac + (ad+bc)X + bdX^2$, that you take modulo $X^2+1$, i.e. by considering that $X^2=-1$. You then get $(a+bX)(c+dX) = (ac-bd) + (ad+bc)X$. Traditionally, you call that $X$ "$i$", and there you go: you have the complex numbers. With finite fields, you can do the same, with some extra possibilities because you can find irreducible polynomials of any degree (with real numbers, irreducible polynomials cannot have degree more than $2$).

For example, to define $GF(2^{128})$, you can start from $GF(2)$ (the field with two elements) and use an irreducible polynomial of degree $128$. However, you could also start with $GF(4)$ and use an irreducible polynomial of degree $64$: you will also end up with a finite field of cardinal $2^{64}$.

Of course, the field you start with, and the polynomial you choose, will matter for the field you actually get: if your values are represented as sequences of bits, and you compute things with them, the bit sequences you obtain depend on these parameters. However, and that is the "magic" thing, it so happens that when two finite fields have the same cardinal, then they are isomorphic to each other. In that sense, there is only one field of cardinal $2^{128}$, and all concrete fields that you can build are just different representations of that mathematical structure. This is why you can talk of "the" field $GF(2^{128})$.

Computing the isomorphism, i.e. mapping from one representation of $GF(2^{128})$ to another (e.g. to a representation as an extension of $GF(4)$ of degree $64$) can be a bit cumbersome, but, ultimately, it is "just linear" and similar to a change of basis with matrices.

To get some extended information on these matters, go read this book.


How do Käsper and Schwabe's Bitsliced AES Mixcolumns work?

Slide #8 in the presentation you linked to describes the way Käsper and Schwabe pack the bits of the AES data blocks into CPU registers.

According to the slide, what they're doing is processing eight 128-bit AES blocks in parallel, using eight 128-bit XMM registers to store them.  They're not doing basic "naïve bitslicing", which would involve using 128 $n$-bit registers to process $n$ different 128-bit AES blocks in parallel, but rather exploiting the structure of AES to effectively do "byte-level bitslicing".

Conceptually, each AES block consists of a 4×4 matrix of 8-bit bytes, for a total of 4 × 4 × 8 = 128 bits.  The standard packing order of these bits in AES input / output looks like this:

| Block 0:
|-------------------------------+-------------------------------+
|           Column 0            |           Column 1            |
|-------+-------+-------+-------|-------+-------+-------+-------|
| Row 0 | Row 1 | Row 2 | Row 3 | Row 0 | Row 1 | Row 2 | Row 3 | ...
|-------|-------|-------|-------|-------|-------|-------|-------|
| bits  | bits  | bits  | bits  | bits  | bits  | bits  | bits  |
| 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 |

That is, the bits of each input / output byte are stored consecutively, and the bytes within each block are sorted first by column and then by row.

Note that, even though standard non-bitsliced AES only processes one block of data at a time, I've included a block number at the top row of the diagram.  This becomes relevant when comparing this standard packing order with the internal order used by Käsper and Schwabe, since their bitsliced AES implementation processes 8 blocks at the same time.

Specifically, whereas the canonical AES bit packing order illustrated above can be compactly summarized as "block > column > row > bit", the internal packing order used by Käsper and Schwabe is "bit > row > column > block":

| Register 0 (stores bit 0 of each byte):
|-------------------------------+-------------------------------+
|             Row 0             |             Row 1             |
|-------+-------+-------+-------|-------+-------+-------+-------|
| Col 0 | Col 1 | Col 2 | Col 3 | Col 0 | Col 1 | Col 2 | Col 3 | ...
|-------|-------|-------|-------|-------|-------|-------|-------|
| block | block | block | block | block | block | block | block |
| 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 | 0 - 7 |

Since they're processing 8 independent input blocks at a time, the bits from different input blocks never influence each other.  In particular, this implies that, using the "reversed" representation above, the bits in each byte never influence each other, and so the entire AES encryption can be implemented using only byte shuffling and bitwise logic operations at byte (or larger) granularity.

Specifically, looking at slide #11 of the presentation, Käsper and Schwabe note that, in their AES implementation:

ShiftRows is reduced to byte shuffling, for which the Intel SSSE3 instruction set they're using has a dedicated instruction (pshufb); and
MixColumns can be implemented using a combination of byte shuffling and XOR.

I have not actually looked at Käsper and Schwabe's AES implementation code (and, in any case, I suck at reading Intel assembly code), but a basic naïve implementation of AES MixColumns using their bit packing would look something like this pseudo-C code:

// rotate each 32-bit block of state by 8 bits
void rotateColumns (uint128_t state[8]) {
    for (int i = 0; i < 8; i++) {
        uint128_t temp = state[i];
        state[i] = ((temp & 0x00FFFFFF00FFFFFF00FFFFFF00FFFFFF) << 8)
                 | ((temp & 0xFF000000FF000000FF000000FF000000) >> 24);
    }
}

// multiply each AES byte (spread across the 8 state registers)
// by 0x02 = x modulo the AES polynomial x^8 + x^4 + x^3 + x + 1
void doubleBytes (uint128_t state[8]) {
    uint128_t temp = state[7];
    for (int i = 0; i < 7; i++) state[i+1] = state[i];
    state[0] = temp;
    state[1] ^= temp;
    state[3] ^= temp;
    state[4] ^= temp;
}

void bitslicedMixColumns (uint128_t state[8]) {
    uint128_t oldstate[8];
    for (int i = 0; i < 8; i++) oldstate[i] = state[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    doubleBytes(state);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
    rotateColumns(oldstate);
    for (int i = 0; i < 8; i++) state[i] ^= oldstate[i];
}

A less naïve implementation would of course inline the helper functions, unroll the loops, use registers instead of arrays, and replace the klugy byte rotation in rotateColumns e.g. with a pshufb instruction and the trivial shift loop in doubleBytes with register renaming.


With a secure hash function what you are describing is entirely impossible. MD5 is considered totally broken and yet I am unaware of a method of accomplishing this feat even with known multi collision attacks.
SEJPM gave a relevant link to what can be done with multi collision attacks on MD5 but placing the resulting hash in plain text is harder and I don't believe has been done. Definitely didn't happen as a matter of fact implementation detail. Should someone do this even with MD5 it would be a significant cryptography feat.
In order to demonstrate that with a turing complete format it is easy to have a file produce its own hash with no need for cryptanalysis: I created a proof of concept and wrote a Scala program which prints its own SHA-256 hash. This technique can work with any hash function, and any turing complete language, including postscript
https://gist.githubusercontent.com/meirmaor/3d858568d5da35f568fe96687ed7dbaf/raw/c26d3bdd298567e76e92c6c37ab96e353a3d8cdf/QuineHash.scala

scalac QuineHash.scala
scala QuineHash
6bae798a607d1f74630734435cc93d17c9b92a6705f7663c6fd47f7439c69669
sha256sum QuineHash.scala
6bae798a607d1f74630734435cc93d17c9b92a6705f7663c6fd47f7439c69669 QuineHash.scala


OK, so you have come up with your own key-authorization and transport encryption scheme.

The key authorization scheme is fine and and quite a standard solution. A similar approach is used on the web to ensure the user doesn't forge certain cookies.

The per-client key derivation and key management also looks good, but for the encryption there's a better solution than "plain" encryption:
TLS-PSK. (Transport Layer Security with Pre-Shared Keys)
In this case the client can claim an identity during the handshake and confirm it by owning and using the assigned pre-shared key. As a bonus the TLS implementation will take care of all the replay-protection and authentication issues and you will only leak the absolut minimal information during the handshake: the client's name. As an additional bonus you can combine PSK with ephemeral Diffie-Hellman ([EC]DHE) to gain forward secrecy and don't get your sessions' secrecy compromised just because the MASTER_KEY has been leaked at a later point in time.


Rijndael follows (like all decent cryptographic algorithms, to my knowledge) the principles of confusion and diffusion, formulated by Claude Shannon. Confusion means the ciphertext depends on the plaintext and the key in a highly nonlinear way, i.e. the function that calculates a specific output bit from the input (plaintext, key) is not a polynomial of low degree in the finite field $\text{GF}(2)$. Diffusion means that every bit of the input affects every bit of the output. Also, the computations that create confusion and diffusions are intertwined so that every information bit is fed into a confusion-creating operation and then spreads over the whole block multiple times, at least 4 or 5 times during the encryption.


Secure hashing when the input comes from a small space

What you want is the below query is possible but the database is secure against; Frequency/Inference attacks
Select * FROM users WHERE 'fav_color' = RED

What we have; small values space for the color names as people's favorite colors. We can consider this is as an example of the small message space like gender, age, weight, scale, the illnesses they have, etc. The more the information is leaked the more to identify a target.

Case: Cryptographic Hash: Hash functions are considered as a candidate for a one-way function. This means that they are hard to invert. In hash terms, they need to have pre-image resistance. Keep in mind that they are deterministic in the sense that one gets the same hash value whenever the same input is hashed again.
Select * FROM users WHERE 'fav_color' = Hash(RED)

Pre-image resistant: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x'$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known.

In a normal pre-image attack, the success of the attack requires around $\mathcal{O}(2^n)$ search to be successful. This can be executed random $2^n$ input search for the hash value. Since the input space is small, once the attacker access the database they can infer the input values very easily. If one assumes that they have all the knowledge of the system, they can prepare a hash table beforehand.
Using slow and memory hard hashing like Scrypt/Argon2id will not much against this attack. It will only make the attack time slower and very small input spaces like color will be still an easy target.
Using salt can kill the hash table/ rainbow tables, however, one cannot execute the query anymore since the same color name will have different values.

Case: Cryptographic Keyed Hash: Keyed hash function like HMAC and KMAC requires a key to operate and the security also relies on the key. They are also deterministic.
Select * FROM users WHERE 'fav_color' = HMAC-SHA256(RED)

In this case, the attacker has no chance of executing a search as in unkeyed hash function since the key prevents it. This is not preventing them to infer data from the tables. The frequency attack is possible as in the case of the CryptDB.

Case Encryption: We can remove the case of stream cipher since the no padding option will leak information about the data as $\color{Blue}{\textbf{Blue}}$  will be longer than $\color{Red}{\textbf{Red}}$. We may assume that with proper padding all the colors have the same plaintext size that result in the same block size.
Select * FROM users WHERE 'fav_color' = ENC(RED)

One can use ECB mode that enables equal queries like in CryptDB since it is not Ind-CPA secure. In this case, the attack same as in the HMAC case, look for the frequency.
Using Ind-CPA secure ciphers modes like CBC and CTR will hide the frequencies, however, that will remove the equality query.

Other options These are slow, however, can hide the frequency on the data at rest since these are using randomized encryptions.

Once can use PIR (private information retrieval) schemes to access the data with the required fav_color. This may need a special design to access all.
FHE (fully homomorphic encryption) base database; we will see.


As pointed out in the comments, your encryption process is linear (mod 2). So this cipher is very weak, all you need is linear algebra.

See, for example, the question answered here


How to compute $m$ value from RSA if $phi(n)$ is not relative prime with the $e$?

Well, if we assume that:

$e$ is prime (65537 is)
Only one of the primes minus one has $e$ as a factor; for example, $p-1$ is divisible by $e$, but $q-1$ is not.  For this discussion, we'll assume that $p$ is the prime with $p-1 \equiv 0 \bmod e$ (which might happen to be the size 1023 factor for you)
$p-1$ is not divisible by $e^2$
That the ciphertext was actually generated by computing $P^e \bmod n$ for some plaintext value $P$.

Then, one way to derive the possible plaintexts is to compute:
$$C^d \cdot L^i \bmod n$$
where:

$C$ is the ciphertext
$d = e^{-1} \bmod \lambda / e$
.  This is well defined, as $\lambda/e$ is an integer which is relatively prime to $e$.
$L = k^{\lambda/e} \bmod n$, where $k$ is an integer such that $L \ne 1$ (and any such value $L$ works); most values of $k$ work
$\lambda = (p-1)(q-1)/\gcd(p-1, q-1)$
$i$ is any integer $0 \le i < e$

Now, if we iterate over the possible values of $i$, this will give $e$ possible values for the plaintext (unless $C$ happens to be a multiple of $p$).  The original plaintext  will be one of these values.  All these values, when raised to the power $e$, will result in the ciphertext, hence we cannot distinguish from the ciphertext which one it is.


Andrew Neff's verifiable shuffle scheme A Verifiable Secret Shuffle and its Application to E-Voting is implemented by the DeDiS Advanced Crypto Library for Go

A working example program that uses the code is the server from the Riffle anonymous communication system.

Here's a "mostly finished" standalone implementation in Go, including a paper explaining the protocol: https://github.com/cjpatton/shuffle.git


how many iterations of SHA3 (keccak256) hashing would be required to provide reasonable protection for the following data structure?

Since H is essentially a password, I would say... none.

Why? Because SHA-3 is not good for passwords, relative to alternatives, see my answer here why: Replacing the PRF in PBKDF2 with Keccak

Now, if you used a different hash function that is a different story, but you are also performing 3 hash steps, that require different security parameters. You want the outermost hash to be the most difficult to reverse, and you want the secret to be the most difficult to brute force.

Since A+B+C are small, your outer most hash must have a high iteration count. Since H is  a secret, the final hash containing it must have a high iteration count. Therefore your inner hashes can be a single iteration as long as the outer one is many. You can probably also just use PBKDF2-SHA256 with H as the password, and ((A , B , C) , (D , E , F, G)) as the salt. As for the logic behind this, it is best to look at H as the seed for your final output. A through G is now a 58.5-bit number used to derive the output from a secret.

Relative to H, your iteration count should be enough to slow the hash function down to more than 1ms, so at LEAST a million based on your calculation. Since this is a single threaded process, if you have a highly threaded system running the hash, your concurrent hash rate can be high, or you can increase the iteration count.


Clarification needed in TLS 1.2 key derivation process

There are a few things off in your description.

First, you use the term "hkdf". There is such a thing as HKDF, which is a key derivation function that internally uses HMAC; however, HKDF is not used in TLS. TLS defines its own key derivation function, which it consistently calls "PRF". It is described in section 5 of the standard. That function is also based on HMAC, but with a different structure. The PRF has three input parameters:

the "secret";
the "seed";
the "label".

Exactly what goes into each of these parameters depends on the context. Normally, the "label" is a constant string that qualifies the usage point (e.g. "client finished" when computing the client's Finished message). The "seed" is made of elements from the handshake, that are normally observable, i.e. non secret. The "secret" input is where goes any actually secret data. The PRF will mix all these values together with a fair dosage of HMAC invocations, into a sequence of bytes of arbitrary length.

In TLS, a key exchange mechanism is used, that results in a "pre-master secret". When RSA key exchange is used, the "pre-master" is generated randomly by the client and encrypted with the server's RSA public key. When using Diffie-Hellman key exchange, the "pre-master" is the encoding of the integer that results from DH ($g^{ab} \pmod p$). When using ECDH (Diffie-Hellman over an elliptic curve), the pre-master secret is the $X$ coordinate of the computed DH point ($abG$). Note that there is no question of hashing at this point: the pre-master secret is a sequence of bytes whose length and contents depend on the used key exchange method.

The master secret is computed from the pre-master secret using the PRF. This is described in section 8. The label is "master secret" and the seed is the concatenation of the client random and server random (these two values are 32-byte each, generated randomly for each handshake, and exchanged in the ClientHello and ServerHello messages). The master secret has length 48 bytes, exactly.

From the master secret are derived the keys and IV needed for symmetric encryption. This is the "key block" that you show. Note that the sizes for the various keys in the key block depend on the negotiated cipher suite. For instance, if the cipher suite uses AES/GCM (e.g. TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256), then there is no MAC key (or, equivalently, the MAC key length is 0), since GCM mode ensures both encryption and integrity check with the same key. Key block computation uses the PRF, with this time the master secret as "secret" input; the "seed" is the concatenation of the server and client randoms. Mind the order! This time, the server random comes first.

The Finished messages have contents which are computed with, again, the PRF. The contents of the Finished message are 12 bytes obtained by invoking the PRF with, as "secret" input, the master secret; the "seed" is the hash of all previous handshake messages. The "label" differs depending on who, between the client and the server, sends that specific Finished message. Since the Finished messages are sent after the ChangeCipherSpec, they are encrypted and MACed, using the algorithms and keys which have just been negotiated. In that sense, the keys and nonces (the client and server randoms) are involved multiple times.

Thus, in your description, use of "hkdf" terminology is spurious, as well as the MAC usage, in particular with regards to the Finished messages.

A nice summary of the SSL handshake is this diagram, which is part of the TLS 1.2 standard:

  Client                                               Server

  ClientHello                  -------->
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               <--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     -------->
                                           [ChangeCipherSpec]
                               <--------             Finished
  Application Data             <------->     Application Data

         Figure 1.  Message flow for a full handshake

Note that after the ClientKeyExchange message from the client, and before the ChangeCipherSpec, there may be a CertificateVerify message (this is sent by the client when the server requests a client certificate, and the client sends one, and this is not full-static DH or ECDH).

The "hash of all previous handshake messages" that is used as an input to the PRF for the computation of the Finished messages really includes all previous messages for this handshake, starting with the ClientHello. Notably, when the server responds with its own Finished message, the hash used in that second Finished message will include the contents of the first Finished message. Also note that the ChangeCipherSpec message is not formally a handshake message (though it may occur only at very specific times within the handshake) so its contents are not used for these hashes.

The complete TLS handshake is quite complicated, mostly for historical reasons. If you want to formalize its use of cryptographic algorithms, you have little choice but to invest a few hours of reading time to get through all the details. I suggest starting with this answer.


Can sending the same plaintext twice, each encrypted with different key and IV, weaken the encryption?

No, it would not compromise the strength of the encryption (assuming that you didn't use a key that the attacker could guess).

We can take it much further; you could give the attacker a billion encrypted messages, all being encryptions of the same plaintext.  It wouldn't matter if you told the attacker what IVs you used (or AADs, should you decide to use them), or if you used the same keys or different ones.  As long as:

You didn't pick a key that the attacker could guess; for example, you picked the keys randomly
You didn't reuse a (key, IV) pair (which in this specific case would matter if the two messages had different AADs, but it's always a good thing to remember when you're using GCM)

Then the security of the system is not weakened; the attacker would have no information (other than length) of the encrypted message, nor could he generate (with nontrivial probability) another encrypted message that would be accepted by the decryption process.


How are the PC-1 & PC-2 calculated for the DES block cipher?

These are not calculated, but as with the particulars of S-boxes, suggested and reviewed as part of the design.

These fixed values/configurations are intended to add certain qualities to the particular step of each round, essentially obscuring the final output as much as possible, in a non predictable way. As you can read on Wikipedia, there is some controversy involved in the development of the S-boxes.

  There was some criticism from various parties, including from
  public-key cryptography pioneers Martin Hellman and Whitfield
  Diffie,[1] citing a shortened key length and the mysterious "S-boxes"
  as evidence of improper interference from the NSA.