This is an extended but still partial attempt at an explicit solution.

Since $p$ is prime, Fermat's little theorem tells us that:

$\forall z\in\mathbb Z_p, z^p\equiv z\pmod p$.
$\forall z\in\mathbb Z_p^*, z^{p-1}\equiv1\pmod p$.

We settle some easy cases:

If $n=0$ and $a\equiv 0\pmod p$, our equation $x^n\equiv a\pmod p$ is ill-defined.
If $n>0$ and $a\equiv 0\pmod p$, the solution is $x\equiv0\pmod p$.
If $n\equiv0\pmod{p-1}$ and $a\equiv 1\pmod p$, any $x\not\equiv0\pmod p$ is solution.
If $n\equiv0\pmod{p-1}$, $a\not\equiv 0\pmod p$ and $a\not\equiv 1\pmod p$, there is no solution.
If $n\equiv1\pmod{p-1}$, the solution is $x\equiv a\bmod p$.

In all the other cases, $x\equiv0\pmod p$ will not be a solution, and we can reduce $n$ modulo $p-1$ to obtain an equivalent equation. From then on, we will assume $1<n<p-1$, $a\not\equiv0\pmod p$, $x\not\equiv0\pmod p$, and proceed to solve our equation $x^n\equiv a\pmod p$.

As pointed out in the question, things are easy when $\gcd(n,p-1)=1$: the only solution is $x\equiv a^{n^{-1}\bmod(p-1)}\pmod p$. Proof: For the stated $x$, we have $x^n\equiv a^{(n^{-1}\bmod(p-1))·n}\pmod p$; thus $\exists k\in\mathbb N, x^n\equiv a^{1+k·(p-1)}\pmod p$; thus $x^n\equiv a\pmod p$; thus the stated $x$ is a solution of our equation. The function $z\mapsto z^n$ is thus a surjective function over the finite set $\mathbb Z_p^*$, thus a bijection, thus there is no solution other than the stated one.

If $\gcd(n,p-1)\neq 1$, let it be $m$, with both $n/m$ and $(p-1)/m$ integers. We find $b$ such that $b^{n/m}\equiv a\bmod(p-1)$ by the above method; that is: $b=a^{(n/m)^{-1}\bmod(p-1)}\bmod p$. Solving $x^m\equiv b\pmod p$ is equivalent to our original equation.

By raising to the power $(p-1)/m$, we see that $x^m\equiv b\pmod p\implies 1\equiv b^{(p-1)/m}\pmod p$. Thus if $1\not\equiv b^{(p-1)/m}\pmod p$, which we can check, there is no solution.

This test is quite useful; for example when $p=71$, $n=55$, $a=2$, we have $m=5$, $(n/m)^{-1}\bmod(p-1)=51$, $b=3$, $b^{(p-1)/m}\bmod p=54$, thus no solution, and that's the case for most $a$. But for $a=20$ we get $b=45$, $b^{(p-1)/m}\bmod p=1$, and indeed there are $5$ solutions $\{18,19,24,32,49\}\pmod p$.

We can thus restrict to solving $x^n\equiv a\pmod p$ when $n$ divides $p-1$, $n>1$, and $a^{(p-1)/n}\equiv 1\pmod p$ (we have shown that any other $a$ leaves the equation without solution, except $a\equiv 0\pmod p$; and we have an efficient method to reduce to that case for any other $n$).

That equation has exactly $n$ distinct solutions $\pmod p$. Proof: by the fundamental theorem of algebra, any polynomial of degree $n$ in the field $\mathbb Z_p$ has exactly $n$ roots, counted with multiplicity; applying that to $x^n-a$ we see that $x^n\equiv a\pmod p$ has at most $n$ solutions $\pmod p$; similarly there are at most $(p-1)/n$ solutions in $a$ to the equation $a^{(p-1)/n}\equiv 1\pmod p$; thus the function $z\mapsto z^n$ over the finite set $\mathbb Z_p^*$ maps at most $n$ elements to any element, and at most $(p-1)/n$ elements have a preimage; by a counting argument, every element with a preimage thus has exactly $n$ preimages.

It follows that we can not aim at finding all the solutions in time polynomial w.r.t. $\log p$ for arbitrary $n$: there are too many solutions when $n$ is big, e.g. $n=(p-1)/2$. We can still aim at finding one solution, or perhaps the smallest one.

When $(p-1)/n$ is small, there is an efficient and trivial probabilistic algorithm that finds a solution: pick a random $x$, and check if $x^n\equiv a\pmod p$, until a suitable $x$ is found; that is expected to require $(p-1)/n$ steps. By trying $x$ sequentially starting from $2$, we can find the smallest $x$.

If the exponent $n$ is even, we can change the unknown to $y\equiv x^{n/2}\pmod p$ and first solve $y^2=a\pmod p$, which is the well-studied problem of finding a square root modulo a prime. By applying this recursively, we can remove the powers of $2$ from the factorization of $n$. Assuming a polynomial-time algorithm finding a solution for any odd exponent $n$, our resulting algorithm would find a solution and work for any exponent, while remaining polynomial in $\log p$ after reduction of the exponent $n\pmod p$.

This is studied and generalized by Adleman-Manders-Miller, solving the problem in time polynomial w.r.t. $\log p$ for fixed $n$. Their algorithm is (at worse) linear w.r.t. $n$ (not $\log n$), and as an aside requires the factorization of $n$.

This might be improved by Barreto-Voloch, and perhaps these two re-visitations of Adleman-Manders-Miller and Barreto-Voloch.

[To be continued. Feel free to improve this community wiki, e.g. by including a description of Adleman-Manders-Miller; I'll have no time to do that in the following week.]

An instance of the original problem with random exponent has a fair chance of being solvable with the above techniques. I have the feeling do not know if this is easier than discrete logarithm modulo $p$ even in the harder cases, like $n\cdot k=(p-1)$ with $k\approx\sqrt{p-1}$, and $p$,$k$,$n$ are primes.


The affine transformation works similar to MixColumns, but operates on an array of 8 bits instead of 4 bytes. Confusion in various descriptions of the affine transform in AES comes from where the LSB of the input byte is located. Some show it at the top of the column, others show it at the bottom. I will be using the version shown in the Rijndael paper, with the LSB at the top of the column.

The matrix used in AES is a rotational matrix based on the value 0x1F, which is 00011111 in binary. The multiplication is performed in the field GF(2), as is the addition of the final vector 0x63. Addition in GF(2) is the same as xor.

The bit indexes for the matrix are 76543210, with 0 being the least significant bit and 7 being the most significant. Each column is the previous column rotated to the left by a single bit, as shown here:

0  7  6  5  4  3  2  1
1  0  7  6  5  4  3  2
2  1  0  7  6  5  4  3
3  2  1  0  7  6  5  4
4  3  2  1  0  7  6  5
5  4  3  2  1  0  7  6
6  5  4  3  2  1  0  7
7  6  5  4  3  2  1  0

For the AES 0x1F affine matrix, the bits are arranged in the following way:

1  0  0  0  1  1  1  1
1  1  0  0  0  1  1  1
1  1  1  0  0  0  1  1
1  1  1  1  0  0  0  1
1  1  1  1  1  0  0  0
0  1  1  1  1  1  0  0
0  0  1  1  1  1  1  0
0  0  0  1  1  1  1  1

For an input of 0x53 in AES, we first find its inverse, which is 0xCA, represented in binary as 11001010

The affine transformation is as follows. The input bits are multiplied against the bits of a given row, with the first bit the LSB of the input. Input bit 0 is only multiplied by row bit 0, and so on. Only when both values are one (logical AND) is the result one. Finally, all bits are XORd against eachother within that row to generate the transformed bit for that row.

Input = 0  1  0  1  0  0  1  1 (LSB First)
Row 0 = 1  0  0  0  1  1  1  1
Bit 0 = 0  0  0  0  0  0  1  1 = 0

Row 1 = 1  1  0  0  0  1  1  1
Bit 1 = 0  1  0  0  0  0  1  1 = 1

Row 2 = 1  1  1  0  0  0  1  1
Bit 2 = 0  1  0  0  0  0  1  1 = 1

Row 3 = 1  1  1  1  0  0  0  1
Bit 3 = 0  1  0  1  0  0  0  1 = 1

Row 4 = 1  1  1  1  1  0  0  0
Bit 4 = 0  1  0  1  0  0  0  0 = 0

Row 5 = 0  1  1  1  1  1  0  0
Bit 5 = 0  1  0  1  0  0  0  0 = 0

Row 6 = 0  0  1  1  1  1  1  0
Bit 6 = 0  0  0  1  0  0  1  0 = 0

Row 7 = 0  0  0  1  1  1  1  1
Bit 7 = 0  0  0  1  0  0  1  1 = 1

The final result LSB first is 01110001 or MSB first is 10001110 = 0x8E. This value is then added (XOR) to the final vector 0x63, giving an output of 0xED


Find collision in Ajtai's hash function using short vector

It depends on the exact domain of the hash function and the quality of the SIS solution, i.e., its norm (and the choice of norm itself).

Suppose the hash domain is $\{-d, \ldots, d\}^m$, i.e., vectors of $\ell_\infty$ norm at most $d$. Then any nonzero vector in Ajtai's lattice having Euclidean norm at most $d$ collides with the all-zeros input. (Actually, $\ell_\infty$ norm at most $d$ suffices.) Thus, finding short enough lattice vectors yields collisions.

But now suppose $d=1$, say. (This is a typical choice.) For standard parameters, the shortest (in Euclidean norm) nonzero vectors in Ajtai's lattice have norm about $\sqrt{n \log q} \gg d = 1$.  Thus, short vectors in Euclidean norm (which is what typical lattice-basis reduction algorithms deliver) may not be sufficient to yield a collision.  Instead, finding a collision requires finding a shortest nonzero vector in the $\ell_\infty$ norm. But little is known about lattice-basis reduction algorithms for this setting.

More details on these issues can be found, e.g., in the paper "SWIFFT: A Modest Proposal for FFT Hashing" (I am a coauthor).


Self-expiring symmetric keys, or: cryptography in absence of secure deletion

I don't believe there is any way to achieve what you want, within your constraints.

You stated as a requirement that a user must be able to get all of their data from the server, without storing anything other than their private key.  If an attacker learns the private key, the attacker then knows everything that the user does, so of course the attacker can decrypt too.

A random beacon (a continuous, public stream of random numbers) doesn't seem to help, since an attacker can record a copy of that entire stream.  Also, it would rely upon on some external trusted party to generate the stream; if you are willing to trust a third party, there are simpler solutions.  An example of such a solution: store $H$ on the trusted third party and return it only upon request to users who prove knowledge of the private key, and only if the expiration date has not yet passed.

A different solution is to have the user change their private key every so often.  To ease this, they can generate a long-lived keypair which is used only for signing, and then generate short-lived keypairs every so often.  The long-lived key is used to sign each short-lived public key and publish this certificate.  To send a message to this user, you look up the current short-lived public key, check its corresponding cert, then encrypt to the short-lived public key.  The user can then securely delete their short-lived keypair when it expires. (I think you might also be able to build sophisticated schemes that eliminate the need for a lookup, but I'm not 100% certain about that.)


Software Security Impossible in Non-Trusted Hardware?

Recently, ECRYPT CSA organized a white-box challenge where you can publish your white-box implementation for AES-128 without exposing your design and the chosen key.

As a result, all the submitted challenges have been broken in less than one month, which further proves that "obscurity" is never sufficient to protect your assets.

To the best of my knowledge, there are no formal methods to measure the obscurity strength achieved in a software.


I recommend to read book "Algebraic Cryptanalysis Book by Gregory Bard". it has a simple example of XL algorithm chapter 12 page 213 (12.4 The XL Algorithm).

after that you can develop sage/magma code for capturing the concept very well.


Deciding on an AES cipher mode for chunked data

I was wondering which of AES-GCM and AES-CBC would be best to use?

If these two are your option, then it is essentially a no-brainer. Always use AES-GCM unless you really know what you are doing.

  Ideally I'd like to choose a solution that is "encrypt-then-mac", but
  I'm unsure which of those fit the bill here?

That's what AES-GCM does internally. It encrypts the data with AES-CTR and then uses a fast, specialized MAC to authenticate the ciphertext.

  Once the encrypted chunks had been written to storage, they could be
  consolidated into a single file, which would have to be split into
  chunks again for decryption.

One thing to look out for when doing streamed decryption is that the resulting plaintext must not be used until the decryption has finished. The reason being that until you have processed everything (including the authentication tag at the end), you can't be sure that the data hasn't been tampered with. There are workarounds to this, that allow you to chunk the data and authenticate it individually using incrementing nonces to prevent re-ordering attacks, but even then there may still be problems with substitution attacks (ie where old versions of chunks are used to substitute current chunks).


Encryption technique performance evaluation

Looking at encrypted pictures is not a good test. I mean, if you can visually see non-random looking parts in an encrypted picture or text, then this implies that the encryption system is abysmally bad. But seeing nothing from a visual inspection does not prove that the system is secure; it just suggests that it will not be easily broken by a chimpanzee.

The same can be said, to some degree, about statistical tests like the Diehard suite. Successfully passing the tests is no proof of security, only proof that you did not make a mistake so obvious that even a brainless generic statistical test would detect it.

To know whether a given encryption system is secure, cryptographers use the following recipe:

They publish the system: complete algorithm description and sample implementation with test vectors (the code is not the description; the description should make no assumption on the involved programming language, and yet be sufficient to reimplement it perfectly in any language).
They lure other cryptographers into gnawing at it and try to break it. The "luring" is about making the algorithm interesting, either through a some kind of mathematical novelty in the structure (e.g. a reduction proof with regards to a well-known hard problem) or impressive performance (see below).
After enough time and work, if the cryptographers found nothing bad to say about the algorithm, we can begin to say that it may be worthwhile to consider in future protocol designs.

Let me stress that "enough time" means "at least five years and one hundred cryptographers". Yes, it is very expensive unless you can convince cryptographers to work for free. NIST did it quite well back in 1998, for the AES competition: they just promised glory (but not a single dollar !) to the winner, and they all came. But the real source of AES strength is not the three years of competition, it is the ten years of subsequent widespread usage and thorough continuous investigation. We have come up with a few interesting attack ways, not on the algorithm itself but on its implementations (side channel attacks); the existence of some results on AES shows that research on AES has kept on, and found nothing fatal. That's the good thing: whatever weakness AES may have is certainly not obvious and we can begin to build trust on that.

Note that there are guaranteed ways to ensure that a given algorithm will not be studied, and thus may never be declared "safe enough":

do not publish the algorithm;
publish the algorithm only as code (especially in an ill-suited language such as any dialect of Basic);
patent the algorithm;
make it considerably slower than the AES.

If you do any of the following, you totally forfeit your chances of seeing your algorithm being independently investigated, and therefore it will never be considered "secure".

Performance is quite easier to evaluate than security. For a symmetric encryption system, the following characteristics are absolute requirements for the system to be considered a non-joke, performance-wise:

The input data shall be any arbitrary sequence of bytes (no restriction like "printable characters only").
For an input message of size $n$ bytes, the encrypted message should have length at most $n+r$ bytes where $r$ is a small overhead, no more than twenty bytes or so, independently of $n$. Proportional size increase, even by a small amount (such as encrypting 1 GB of data into 1.01 GB), is a total no-go.
The encryption process shall use only small amounts of RAM and code; apart from the data itself, the code and RAM for state and constants shall fit in the level 1 caches of the CPU. On a modern, "big" CPU like the one in a desktop PC, there is typically 32 kB of level 1 cache for code, and about as much for data. Some smaller architectures have smaller caches (e.g. 8 kB for code and 8 kB for data on a MiPS-based home routeur). The encryption shall be amenable to streaming, i.e. encrypting gigabytes by small successive chunks, while keeping only a few hundreds of bytes of state in RAM.
The processing time to encrypt $n$ bytes shall be, asymptotically, proportional to $n$ (time to encrypt 2 gigabytes shall be twice the time to encrypt 1 gigabyte).

Given these characteristics, you can define encryption performance with the following formula:

$$ T = k*n + i + f$$

where:

$T$ is the encryption time;
$n$ is the input data size, in bytes;
$i$ is the processing time needed to begin the processing (initialization which can be done before seeing the first byte of data; the "key schedule" fits there);
$f$ is the processing time needed for finalization (after all data bytes have been seen, the time needed to close up things appropriately and output the last encrypted byte);
$k$ is the asymptotic encryption speed.

If you express all these values in "clock cycles", then $k$ is the encryption speed in "clocks per byte". The smaller the better. To measure $k$, have your code repeatedly encrypt an 8 kB data buffer so that the total processing time takes at least a few second (see this answer for a more detailed treatment).

With OpenSSL on a basic desktop machine, I get AES speed close to 17 cycles per byte (the processor is an Intel i7; it can do much better, below 2 cycles per byte, using the special AES opcodes, but OpenSSL does not use them). Some stream ciphers achieve much better performance (e.g. less than 4 cycles per byte with Sosemanuk). That's your competition.

Bottom-line: If your system cannot go below 20 cycles per byte on a PC, don't even bother with publishing it: it will not be "interesting enough". Harsh but true: symmetric encryption has gone quite far and is considered to be a "mostly solved" problem. It takes quite a lot of effort to design something which has the slightest chance of being an improvement over already known algorithms.


Isn't the deterministic property of (EC)DSA a security problem?

We are talking about signatures here, not encryption. The two activities are quite different. In the case of signatures, there is nothing secret except the private key, whereas in the case of encryption, both the private key and the message to encrypt should remain confidential (you encrypt the data precisely because you want to keep it confidential).

Asymmetric encryption requires some randomization because if it was deterministic, then an attacker could make an exhaustive search on the data itself. In the case of signatures, there is no confidential data on which the attacker may want to run such a brute force attack (indeed, no confidential data at all), so this specific issue does not apply.

Indeed, the "old" padding for RSA signatures (EMSA-PKCS1-v1_5, more usually known as "PKCS#1 v1.5") is deterministic, and, as yet, unbroken. The newer version (EMSA-PSS) is randomized, but, as PKCS#1 puts it:

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.  The salt value enhances the security
     of the scheme by affording a "tighter" security proof than
     deterministic alternatives such as Full Domain Hashing (FDH); see [4]
     for discussion.  However, the randomness is not critical to security.
     In situations where random generation is not possible, a fixed value
     or a sequence number could be employed instead, with the resulting
     provable security similar to that of FDH [12].

(Emphasis is mine.)

In the case of (EC)DSA, the $k$ value has some specific requirements which do not have a counterpart in RSA; namely, from the point of view of any attacker, $k$ should be as if it was generated randomly and uniformly in the $1..q-1$ range, where $q$ is the order of the subgroup in which the algorithm is applied, with one optimization: it is permitted to reuse the same $k$ value as a previous signature, provided that all the inputs are the same (same private key, same input message). We can see that this "optimization" is safe if we consider the following attack model:

The attacker is given access to a black box which computes the signature on messages that the attacker chooses, using a private key $x$ that the attacker does not know.
The attacker may submit $n$ signature requests to the box ($n$ messages $m_i$), thus resulting in $n$ corresponding signatures ($s_i$).
The attacker's goal is to make a forgery: a new message $m$, distinct from all the $m_i$, and a corresponding signature $s$.

The "optimization" is then modelled as a filter/cache on the box, which remembers past requests from the attacker; if a request is made for a message which was already seen ($m_j = m_i$ for $j \gt i$), then the filter blocks the request, and returns the previous signature instead of making the box work again (i.e. it forces $s_j = s_i$). In the model above, this is a restriction on the attacker, so this can only strengthen the algorithm, not weaken it.

This model actually explains why, in all generality, derandomization is safe for signature algorithms: any random value used in the course of the algorithm can be replaced with a deterministically generated value, provided that the generation system takes as input both the message and the private key, and acts as a random oracle. This is exactly what RFC 6979 does. (Of course, random oracles are more easily talked about than incarnated; e.g. see this. RFC 6979 uses HMAC-DRBG as a "practical random oracle".)


Yes, field operations may involve numbers that are larger than the order. Public key point coordinates may exceed the order.
Parts of the protocol that handle scalars work modulo the curve order, while the parts that handle elliptic curve points work modulo the prime modulus.
Sometimes, as you noted, some information "crosses" between these domains: the main case being inside the ECDSA protocol, in the r value which is obtained from a X coordinate and reduced modulo the order to enter in the computation of s.


What is the current time limit of Keccak inversion?

But for this reason I would argue it’s the most valuable sub-function to study if we are to determine the theoretical time limit of Keccak inversion.

That is incorrect as you don't need a time limit to compute $\theta^{-1}$.

You are not using the correct representation. As follows are some intuitions of how to efficiently invert $\theta$.

I. Quick Reminder of $\theta$

II. Inverting the $\theta$-effect

Instead of seeing the parity  $\mathscr{P}$ of the state $S$ as $5 \times w$ bit-array. You can see it as  a $5w$-bit vector $W$. i.e. you have a unique mapping $\sigma$  between $x,z$ and $i^{th}$ the coordinate in that $5w$-bit vector $W$ : $i = x \times w + z$.
$$\varphi(\mathscr{P}) = W$$

The $\theta$-effect can be seen as the result of a matrix multiplication:
$$W' = W \cdot T$$
which gives us:
$$E = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi$$
and the inverse:
$$E^{-1} = \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi$$
Note: this assumes that $T^{-1}$ exists.

Proof:
\begin{array}{rl}
E^{-1} \circ E &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ \varphi \circ \varphi^{-1}\circ (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T^{-1}) \circ  (\lambda x \mapsto x\cdot T) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x\cdot T \cdot T^{-1}) \circ \varphi\\
 &= \varphi^{-1}\circ (\lambda x \mapsto x) \circ \varphi\\
 &= \varphi^{-1}\circ \varphi\\
 &= id
\end{array}

As an example as follow is computed $T$ for $w = 4$:

i =  0 : 0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1
i =  1 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0
i =  2 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0
i =  3 : 0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0

i =  4 : 0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0   0 0 0 0
i =  5 : 1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 0 0
i =  6 : 0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 0
i =  7 : 0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0   0 0 0 0

i =  8 : 0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0   0 0 0 0
i =  9 : 0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 10 : 0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0   0 0 0 0
i = 11 : 0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1   0 0 0 0

i = 12 : 0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0   1 0 0 0
i = 13 : 0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0   0 1 0 0
i = 14 : 0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0   0 0 1 0
i = 15 : 0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0   0 0 0 1

i = 16 : 1 0 0 0   0 0 0 0   0 0 0 0   0 0 0 1   0 0 0 0
i = 17 : 0 1 0 0   0 0 0 0   0 0 0 0   1 0 0 0   0 0 0 0
i = 18 : 0 0 1 0   0 0 0 0   0 0 0 0   0 1 0 0   0 0 0 0
i = 19 : 0 0 0 1   0 0 0 0   0 0 0 0   0 0 1 0   0 0 0 0

If we take point at coordinates $(x = 0, z = 3)$ or $i = 0\times 4 + 3 = 3$ (thus the fourth column).

The $\theta$-effect gives us:

$(x-1, z) + (x+1,z+1) = (4,3) + (1,0)$ as we are with $w = 4$.

In other words we need:

$i = 4 \times 4 + 3 = 19$ and $i = 1 \times 4 + 0 = 4$.

You can check that these coordinates are set in the $4^{th}$ column.

Fun fact, $T$ is not invertible.

For $T$ to be invertible, the determinant should not be null. Using sage we notice that $det(T) = 0$, proving that $T$ is not invertible.

III. Going back to $\theta$

Sadly inverting the (non-invertible) $\theta$-effect does not gives us the inverse of $\theta$ as it is added back to the state. However we can notice multiple things.

   +---+       +---+
  /   /|      /   /|
 /   / +     /   / +
+---+ /     +---+ /
| S |/ ---> | S'|/
+---+       +---+
  |           ^
  v           |
  P  ------> E(P)

Notice that:

$\bigoplus_{y=0}^4 S[x,y,z] = \mathscr{P}$
$\bigoplus_{y=0}^4 S'[x,y,z] = \mathscr{P} + 5 \times E(\mathscr{P}) = P + E(\mathscr{P})$

In the same way as in [II], $P + E(\mathscr{P})$ can be seen as a matrix transformation (i.e. a multiplication by $(id + T)$).

Thus if we inverse this $(id + T)$ matrix, we will be able to find the initial parity $\mathscr{P}$ of the state, compute the $\theta$-effect and add it back to $S'$, canceling the itself ($\forall s, s \oplus \theta\text{-effect} \oplus \theta\text {-effect} = s$). And in such way, computing the inverse of $\theta$.

   +---+                              +---+
  /   /|                             /   /|
 /   / +                            /   / +
+---+ /        theta^-1            +---+ /
| S'|/ --------------------------> | S |/
+---+                              +---+
  |                                  ^
  v                                  |
P + E(P) ---------------> P ----- > E(P)
          *(id + T)^-1        *T

Going back to our $w= 4$ example we have:

id + T =
[1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]
[0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0]
[0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0]
[0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1]
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0]
[0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1]

Which happens to be invertible:

(id+T)^-1=
[1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 1 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1]

Because of the associativity of the matrix group. You can just compute: $(id + T)^{-1} \cdot T$ giving you a slightly faster computation of the $\theta$-effect from $S'$ (as opposed to do the 2 matrix multiplications):

(id + T)^-1 * T =
[0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0]
[0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1]
[1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1]
[1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0]
[0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1]
[0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1]
[1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0]
[1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 1]
[1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1]
[1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 0 1 1]
[1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1]
[0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 1 1 0]
[0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 0]
[1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0]
[1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 0 0 0 0]
[1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0]
[0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0]
[0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1 1]
[0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 1]
[0 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0]


How do TLS 1.1 and 1.2 generate IVs (initialization vectors) for each record?

An implementation should generate the IV from any cryptographically secure PRNG. TLS 1.1 further details the possible ways to do that:

The IV can be obtained from a PRNG.
A random string $r$ can be generated from a PRNG, and added to the plaintext to encrypt where the IV should go; then the whole lot is encrypted with either a fixed IV, or even the last block of the previous record as IV. This method is easier to map on existing implementations of CBC encryption, because the IV is treated like plaintext. It is safe because $E(r \oplus iv)$, for a given $iv$ (e.g. the last block from the previous record) and encryption function $E$, is as uniformly random as $r$ itself.
The same method, but with $r$ being a fixed string.

It is unclear whether the third method is safe or not. It relies on the encryption $E$ to "act as a PRNG". The TLS 1.1 specification includes this:

 The following alternative procedure MAY be used; however, it has
  not been demonstrated to be as cryptographically strong as the
  above procedures.  The sender prepends a fixed block F to the
  plaintext (or, alternatively, a block generated with a weak PRNG).
  He then encrypts as in (2), above, using the CBC residue from the
  previous block as the mask for the prepended block.  Note that in
  this case the mask for the first record transmitted by the
  application (the Finished) MUST be generated using a
  cryptographically strong PRNG.

Since the specification gives it as a "MAY", one must assume that some implementers may have used this third method. Its advantage is that it does not require a PRNG invocation for every record, only for the first record, so a relatively slow PRNG can be tolerated.

Interestingly, all these detailed paragraphs have been removed from TLS 1.2, which merely states the generic "The Initialization Vector (IV) SHOULD be chosen at random, and MUST be unpredictable".


Why computation of $u*v^3*(u*v^7)^{(p-5)/8}$ is suggested instead of $(u/v)^{(p+3)/8}$

Note that
$$\frac{7(p-5)}8+3=\frac{7p-11}8\equiv \frac{7p-11}8-p-1\equiv -\frac{(p+3)}8\pmod{p-1}.$$
Similarly
$$\frac{p-5}8+1=\frac{p+3}8$$
And so $v^3(v^7)^{\frac{p-5}8}\equiv v^{-\frac{(p+3)}8}\pmod p$.
Likewise $u(u)^{\frac{p-5}8}\equiv u^{\frac{p+3}8}$ as required.
The reason is to save a modular division which is quite a pricey operation.


Encryption of numeric value using playfair

use letters to represent digits

"a captured German revealed under interrogation that Enigma operators had been instructed to encode numbers by spelling them out ...  Alan Turing reviewed decrypted messages and determined that the number "eins" ("one") was the most common string in the plaintext."
-- Wikipedia: known-plaintext_attack

"The Enigma machine didn't encode spaces (nor punctuation characters), so either leave out the spaces in your message or replace them with X's. ... If you wish to encode numbers in your message, you must spell them out."
-- Madlab: Enigma

"The German Army, Air Force and Police used the Double Playfair system as a medium-grade cipher in WWII, ... numbers were spelled out. As the German numbers 1 (eins) to twelve (zwölf) contain all but eight of the letters in the Double Playfair squares, pro forma traffic was relatively easy to break"
-- Wikipedia: Playfair cipher

"each digit was represented by 2 letters"
-- "Enigma Uhr"

use some other cipher that can handle letters and digits directly

"... we proposed a 6 X 6 Playfair cipher ... 6 X 6
Playfair cipher supports all 26 alphabets (A-Z) and 10 digits (0-
9)"
-- "6 X 6 Playfair Cipher using LFSR"

"This extended play fair algorithm is based on the use of a 6 X 6
matrix of letters ... and digits..."
-- "An Extension to Traditional Playfair Cryptographic Method"


Proof of membership and non-membership in Merkle tree (Hash-tree)

If you don't use a merkle tree then checking membership is an O(n) operation, as opposed to O(log n) with a merkle tree. Instead of going through each item in the set, you walk up one branch of the merkle tree which has O(log n) depth.
Though, without sorting, proving non-membership still requires O(n) steps. Sorting makes it possible to prove non-membership by only looking at the leaf nodes that would be adjacent to the non-element.
I found this short summary here that's really useful.


Understanding ransomware – What makes plain-text-attacks or brute-forcing so hard?

Does the length of the public key imply the length of the private key, or can they be unrelated?

Yes.

The sizes of public and private keys depend on the cryptosystem. Usually they are related somehow, but not necessarily. For example, you can store a short value as a private key, which is then used as a PRNG seed to generate the private key used in the actual algorithms.

In RSA a private key file typically includes a lot more information than a public key - in addition to those modulus and public exponent that the public key contains, it includes the private exponent, as well as usually the original primes and some CRT values.

However, raw RSA keys only need to contain the modulus and the private or public exponent, so they can be the same size.

  Also, wouldn't more plaintext information provide a brute-force program a starting point to speed the process?

No, typically not. An encryption algorithm where this is true (at least for values smaller than other attacks) is considered broken. Because of the below.

  I don't understand why, given that all the files would be decrypted using the same key, we can't deduce said key by comparing encrypted files to unencrypted ones.

If you could do that, then the public key system would not be very useful would it? Anyone who has the public key can encrypt any number of files they want. Thus, they have any number of plaintext-ciphertext pairs they could want. If this made the algorithm weak, it would be completely useless (except maybe as a replacement for a symmetric, i.e. secret key algorithm).

You might find questions such as this helpful: Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?


Proof that $gcd(e, \lambda(N)) = 1 \hspace{1mm} \Longleftrightarrow \hspace{1mm} gcd(e, \varphi(N)) = 1$

An outline of the proof is:

$gcd(a,b)=1$ is equivalent to the claim that $\not\exists p_\text{ prime}: p|a \land p|b$ (that is, there does not exist a prime $p$ that is a factor of both $a$ and $b$)

Now, for all primes $p$, $p | \phi(N)$ iff $p | \lambda(N)$ (that is, for all primes $p$, either they are a factor of both $\phi(N)$ and $\lambda(N)$, or they are a factor of neither).  This can be seen by examing the relation $\phi(N) = (p-1)(q-1)$ and $\lambda(N) = (p-1)(q-1)/gcd(p-1,q-1)$, and observing that if $gcd(p-1,q-1)$ had a prime power factor $r^n$, then both $p-1$ and $q-1$ were multiples of $r^n$, and hence $(p-1)(q-1)$ had $r^{2n}$ as a factor, and so $(p-1)(q-1)/gcd(p-1,q-1)$ has $r^n$ (and hence $r$) as a factor.

So, if $gcd(e, \lambda(N))=1$, then:

For any prime factor $p$ of $e$, $p$ is not a factor of $\lambda(N)$
Hence, For any prime factor $p$ of $e$, $p$ is not a factor of $\phi(N)$
Hence, $gcd(e, \phi(N))=1$

And versa-visa, showing the equivalence.


The open source version of CyaSSL contains code that calls into the commercial NTRU library -- the library itself is missing of course. You might be able to make CyaSSL work with the open source NTRU implementation at https://github.com/tbuktu/libntru ; it's alpha level software though.


Hashing entropy with only 128 bits of internal state

Use SHA-256. Truncating the hash does reduce its collision resistance, but you can't "lose entropy" if you're only keeping 128 bits in each pool anyway.


As explained in the link posted by bkjvbx, the short keys and signatures offer the same security level as ~3000-bit RSA.

Regarding the implementation, TweetNaCL's code has been written by experts, has been carefully reviewed and is something you can trust. The only catch is that it is very slow.


How does Kerckhoffs's principle apply to Adversarial Neural Cryptography?

If I'm interpreting section 2.2 correctly, the "optimal Eve" $O_E(\theta_A) = argmin_{\theta_E}(L_E(\theta_A, \theta_E))$ is actually allowed to see Alice's parameters $\theta_A$.  The training of Alice and Bob is, in plainer (and rougher!) terms, trying to solve this question: what are the best choices of $\theta_A$ and $\theta_B$ such that if:

We reveal $\theta_A$ and $C = A(\theta_A, P, K)$ to Eve but neither $P$ nor $K$;
We reveal $\theta_B$, $C$ and $K$ to Bob, but not $P$;

...then Eve's ability to infer information about $P$ is minimized but Bob's is maximized?

So I don't think there's a Kerkhoff's principle problem here.  My concern, actually, isn't that Eve knows too little about Alice and Bob, but rather whether Alice and Bob might know too much about their adversary Eve.  If we unwind the definition of the "optimal Alice and Bob" $(O_A, O_B) = argmin_{(\theta_A, \theta_B)}(L_{AB}(\theta_A, \theta_B))$ we find that it refers, indirectly through the definition of $L_{AB}$, to the definition of the "optimal Eve" $O_E(\theta_A)$.  If we chase this down in turn, we find that this definition indirectly refers to the function $E(\theta_E, C)$—the function that, given a choice of parameters $\theta_E$ for Eve, produces her guess $P_{Eve}$ of the plaintext that corresponds to the ciphertext $C$.

So Alice and Bob are allowed to know what function $E$ is.  I think cryptographers would want $E$ to be a universal Turing machine and allow $\theta_E$ to be any polynomial-time program, but it sure sounds like the paper's Eve only considers a subset of that, and that Alice and Bob know which subset that is.  So, in simpler language, I fear that Alice and Bob may know too much about "how Eve thinks" (the membership of the narrow set of functions that Eve can compute).


can i find the algorithim of a prng by entering previous sequence

If the PRNG is a cryptographically secure PRNG, then no. A basic property of CSPRNG is that if you know all the bits of a sequence of outputs except one, then your probability of guessing that one bit is no better than pure chance.

A deterministic CSPRNG operates by having a secret state. Without finding out the secret state, there's no way to guess outputs.

If the PRNG is not cryptographically secure, then it might be possible to reconstruct some outputs knowing others. In fact that possibility is basically the definition of not being cryptographically secure. Realistically, unless the PRNG is extremely bad, it's rather difficult to find the algorithm given only a few outputs, but it might be very easy to find if you manage to guess the algorithm. Maybe it's a common one?


How to find generator $g$ in a cyclic group?

Mike gave you the answer for the specific question you asked.  I'll try to give you an answer to the question you should have asked:

  For Diffie-Hellman, what criteria should I use to select a secure $p$ and $g$?

This question is important, because not every large cyclic group is actually secure.  It turns out that, for the group $\mathbb{Z}_p^*$, the factorization of $p-1$ is critical.

If $p-1$ has a factor $q$, and $g^{(p-1)/q} \ne 1$, then given $g$ and $g^x \bmod p$, we can determine $x \bmod q$ in $O(\sqrt{q})$ time.

What does this mean?  Well, if we pick a $p$ where $p-1$ has a bunch of small factors $q_1, q_2, q_3$, and we give $g$ to be a primitive element (so $g^{(p-1)/q} \ne 1$ for any $q > 1$), then we transmit $g^x \bmod p$ as a part of the DH exchange, the attacker can efficiently derive $x \bmod q_1q_2q_3$; we're effectively giving him $\log_2 q_1q_2q_3$ bits of our secret exponent.  This means that, with a random prime $p$ and either a random $g$, or a primitive $g$, we have a good possibility of leaking quite a bit of information.

So, what do we do?  Well, first of all, we make sure that $p-1$ has a large prime factor $q$ that we know.  There are two common practices:

Select a prime $p$ with $(p-1)/2$ prime as well (often called a safe prime).  If we do that, then $q = (p-1)/2$ is certainly large enough (assuming $p$ is large enough).
Select a prime value $q$ (perhaps 256 to 512 bits), and then search for a large prime $p = kq + 1$ (perhaps 1024 to 2048 bits).  This is called a Schnorr prime

Once we have our values $p$ and $q$, we then select a generator $g$ that is within the subgroup of size $q$.  Members of this subgroup have the property that $g^{(p-1)/r} = 1$ for any factors $r$ of $p-1$ other than $q$ (and $p-1$ itself), hence the above observation does not apply.

One easy way of selecting a random generator is to select a random value $h$ between 2 and $p-1$, and compute $h^{(p-1)/q} \bmod p$; if that value is not 1 (and with high probability, it won't be), then $h^{(p-1)/q} \bmod p$ is your random generator.

An alternative method of finding a generator $g$: if you selected a safe prime, and if your safe prime also satisfied the condition $p = 7 \bmod 8$, then the value $g=2$ will always be a generator for the group of size $q$.  It won't obviously be a random generator, however, we can also show that, with a safe prime, if you can solve the computational Diffie-Hellman problem with $g=2$, you can solve it with any $g$ (with a polynomial number of queries), hence $g=2$ cannot be weak.


W-OTS+ is stronger, as it makes weaker assumptions on the hash function.

Let us take a rather extreme example, let us consider W-OTS and W-OTS+ based on the MD5 hash function.

Now, the proof for W-OTS is quite invalid; it assumes that the hash function is collision resistant, and we know how to generate collisions with MD5.

On the other hand, W-OTS+ based on MD5 would appear to be secure; despite MD5 being "broken", we do not know how to create second preimages to MD5.

BTW: this appears to be more about the proof technique used to prove W-OTS, rather than the actual security; we can create MD5 collisions (invalidating the proof), however we don't know how to use those collisions to actually attack W-OTS-MD5; hence it would appear to be secure (but we can't prove it).

Also, one note: those aren't the only versions of Winternitz signatures in the published literature...


Ciphers in CBC mode reveal place of change in plaintext

Your problem is that if you encrypt two messages which start the same (and change at some point later on) the beginning of the ciphertext will be the same in CBC mode when using the same IV.

Normally you should change the IV every time you encrypt a new message. This is precisely what the IV is meant for - achieving IND-CPA (semantic) security which prevents an attacker from detecting where the the message was changed. Once you do this, your concerns go away, since even two similar messages (say, an old document, and a newer, slightly revised one) will be encrypted with completely different IV's, and hence their ciphertext will be unrelated. And you don't need a two-pass scheme anymore!


Is it feasible to build a stream cipher from a cryptographic hash function?

With the corrected system (which actually uses the key), I see these weaknesses:

If the attacker can guess some plaintext_n, he can derive pad_n from ciphertext_n and from this all the following pad_i - which means that he can read the rest of the message.
The ciphertext starts with a H(plaintext), which means that an attacker which can guess the plaintext has a means to verify this guess. To avoid this, the plaintext should at least be randomly padded. (But then you could simply use these random bytes as the initialization vector instead of the hash of the plaintext).
The entropy of your actual key stream (the pad) is reduced to h bits, even if the key itself had bigger entropy. This might be better if you input the key again to the hash function for creating the higher-order pad_n.
As already said by Jack, the need to hash the plaintext before you can start to encrypt it means that you need two passes over the plaintext, which means that the encrypting algorithm is not an online-algorithm (the decryption is).

Other than this, your algorithm is similar to the Output feedback mode of operation for Block ciphers, with the initialization vector derived from the message, and without new key input for the following steps.

Here is a variant which would not have these weaknesses (and hopefully no others):

initvec = random
pad_0 = H(key + initvec)
pad_n = H(key + pad_(n-1))

ciphertext = initvec + cipherpart_0 + ... + cipherpart_max

(The rest as in your example.)

This does not do integrity-protection ... for this you would append some keyed MAC at the end (so it can be an online algorithm).

Then we have actually the OFB mode of a strange "encryption only" block cipher derived from the hash function. The only problem would be that it would be quite slower than a normal block cipher, as Jack already mentioned.

Disclaimer:

Note that while this construction is secure in the random-oracle model (see this blog entry for a proof of a similar construction, using a counter instead of previous hash), the proof uses properties which are not implied by the collision-resistance and preimage-resistance properties of a hash function (which is what hash functions are constructed for).

So while this might work, it does not have to work with real-world hash functions.


AES GCM : is it acceptable to return the wrong plaintext if the tag is incorrect?

There is an article* that answers the question in the negative for GCM and CCM. The article introduces the first formalization of the Releasing Unverified Plaintext (RUP) setting. The related security notion is the Ind-RUP.
The security question is can an adversary forge messages with unverified messages? In this game, confidentiality is not relevant, since in the game the adversary is accessing the plaintext of the chosen messages. AES-GCM fails to satisfies this.

How to Securely Release Unverified Plaintext in Authenticated Encryption by Elena Andreeva and Andrey Bogdanov and Atul Luykx and Bart Mennink and Nicky Mouha and Kan Yasuda

AE schemes such as GCM [34] and CCM [49] reduce to CTR mode in the RUP setting. This is because the adversary does not need to forge a ciphertext in order to obtain information about the corresponding (unverified) plaintext.

Your questions:

It is very dangerous. AES-GCM internally uses CTR mode and bit flipping is very easy in the CTR mode. An attacker can easily change the ciphertext bit on their advantage. This is catastrophic if the structure of the message is known.
One must never ignore the tag invalid!
It is not about the leak of the key, CTR mode is IND-CPA secure. It is about changing the messages. This is why CTR mode can't have IND-CCA. GCM provides integrity and authentication and authenticated encryption > IND-CCAs

For the second part you may benefit from is Q/A which provides a solution for the limited chunks for the GCM;

How to securely encrypt/decrypt data with a maximum chunk size?

Also for general guide

What are the rules for using AES-GCM correctly?, and
Deep into bounds Does GCM (or GHASH) only provide 64-bit security against forgeries?

*Thanks to Squeamish Ossifrage for pointing the article.


Security of Diffie-Hellman with multiplication for secret derivation?

This problem (in the computational sense) is equivalent to the CDH problem [1].
This problem can be summarized as "given $g, A, A^y, B, B^x$, compute $g^x \cdot g^y$
Given a CDH oracle, we can solve this with two queries; we get the inputs $g, A, A^y, B, B^x$, and we give the CDH oracle the values $B, B^x, g$, and it'll give us the value $g^x$; we do the same to get $g^y$, and a simple multiplication gives us $g^x \cdot g^y$
Conversely, given an oracle that solves this problem, we can solve the CDH problem; we get the inputs $C, C^x, D$, we select an arbitrary $E, y$ values, and give the oracle the tuple $D, E, E^y, C, C^x$; it'll return the value $D^x \cdot D^y$.  We then multiply that by $D^{-y}$, and that gives us the answer to the CDH problem $D^x$

Now, addressing the decisional problem would appear to be trickier; it's easy enough to show how to solve the DDH problem with an oracle that solves the decisional version of this problem; however, I don't see an obvious way to use a DDH oracle to solve this problem.

[1]: Note: for the CDH problem, I won't be using the usual formulation "given $g, g^x, g^y$, return $g^{xy}$, instead, I'll be using the equivalent "given $g, g^x, h$ return $h^x$.  That formulation would appear to be make the proof a bit cleaner...


Decrypt AES-encrypted data with another key

Usually you require a mode of operation for a block cipher such as CBC or CTR to encrypt data. CBC or CTR is then configured with the given block cipher & key. The mode takes an IV or nonce as additional parameter, but I'll leave the IV out of my answer as the IV value is inconsequential if the wrong key is used.

A block cipher such as AES will simply encrypt or decrypt a full block of bytes. For each possible plaintext block there will be precisely one ciphertext block, given a specific key. The result of a bad key will have the same size, but it will be indistinguishable from random otherwise.

A block cipher itself however is not secure and can only encrypt precisely one block - you need the mode of operation too. In that case it depends on the mode. If the mode does not apply padding - e.g. CTR - then the result will be indistinguishable from random, and you won't get an error. If you use CBC (and a padding algorithm instead of ciphertext stealing) then you will probably get a padding error (about 255 in 256 times).

If you always want to receive an error instead of garbled ciphertext or a padding error you need to integrity protect your ciphertext. You can do this by using an authenticated mode of operation such a GCM or by applying a (H)MAC over the ciphertext.


Verifying Diffie–Hellman parameters someone else generated

There are several possible ways to generate a weak DH group:

The attacker can generate a $g$ with a small order; this would make deriving the shared secret from the public values easy.
The attacker can generate a $g$ with a smooth order; that is, the order is large, but is composed of small prime factors; this would make deriving the shared secret from the public values easy.
The attacker can generate a $g$ with a large order, but one with a number of small factors; if the implementation also doesn't use large secret exponents, this would also make deriving the shared secret easy
The attacker can select a prime $p$ that is easy to attack with the Special Number Sieve algorithm; this makes deriving the shared secret easier (but no picnic; I believe that attacking a 2048 bit modulus with SNFS may be in the range of the NSA at the moment).
The attacker may select a composite $p$.  While this also makes it easier on the attacker, what this chiefly does is allow the attacker to disguise whether they're doing the above tricks.

With this in mind, the first thing I would do is check if $p$ is prime; if it is not, then either the implementer picked a random odd value for $p$ (which implies he's a bit clueless when it comes to cryptography), or he has something to hide -- neither of those sound good.

Assuming that $p$ is prime, then the next step would be to attempt to factor $p-1$ (or at least, search for any small factors, where 'small' means, perhaps, 128 bits or less); a tool that implements the Elliptic Curve Method to find small factors would be useful here.  You'll get $p-1 = 2 \times p_1 \times p_2 \times ... \times p_n \times q$, where $p_1, p_2, ..., p_n$ are small primes, and $q$ is a large number with no small prime factors (and $q$ may be either prime or composite).

The ideal case is that there are no $p_1, p_2, ..., p_n$ and $q$ is prime; that means that we have a 'safe prime'; any $g$ (other than 1 and $p-1$) is good, and and the implementor is clueful; other than SNFS, we're good.

The other extreme is that there are no large factors; you managed to completely factor $p-1$ into small factors; this means that the DH problem is easy here; fail.

However, if it is somewhere in the middle, we then need to determine the order of $g$.  First thing to check is if $g^{2\times p_1 \times p_2 \times ... \times p_n} = 1$; if so, then someone generated $g$ with a smooth order; fail.

The next step is to compute $g^q$; and find the minimal $r$ which is a divisor of $2 \times p_1 \times p_2 \times ... \times p_n$ with $(g^q)^r = 1$.  Here, the ideal case is $g^q=1$ (as $r=1$).  What this matters is that the attacker can compute the secret exponents modulo $r$.  If $r$ is large, and if the secret exponents aren't, this can significantly reduce the strength of those secret exponents.

The last step is to check if the SNFS discrete log algorithm can be applied; I'm sorry, but I can't help you with that.  On the other hand, SNFS isn't as large of a concern as these above issues.


How a chosen prefix collision is more useful than a standard collision concerning hashing functions?

In a chosen-prefixes collision attack, the adversary is able to freely choose two distinct prefixes $P$ and $P'$ of arbitrary content, and is able to find suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P'\mathbin\|S')$.Note: It is common to write chosen-prefix when that logically should be chosen-prefixes.

In other types of collision attack the adversary freely chooses only one prefix $P$ (possibly empty) and is able to find distinct suffixes $S$ and $S'$ with $H(P\mathbin\|S)=H(P\mathbin\|S')$.

That makes a critical difference: only chosen-prefixes attacks allow the attacker to freely choose different meaningful content where the colliding messages differ.

Chosen-prefixes attack thus are much more flexible for the attacker. For example, in a pure text document, the prefixes could be the meaningful part of the text at start, with the suffix in the end after a few hundred space characters so that it never shows. That allows the attacker to prepare documents with vastly different contents of his choice (except for the end which does not show), and so that the signature of one will be valid for the other.

By contrast, in other types of collision attack, the attacker typically is unable to make similar forgeries for pure text files, and more generally data formats where insignificant data can only be at the end. Attacks can only target more flexible data formats (like Portable Document Format, Postscript, some compressed image formats, some executable file formats..) such that it is possible to turn the alteration in the suffix into an operationally meaningful difference. This is often hard or infeasible (depending heavily on details of the data format and attack context).

In particular, a chosen-prefixes attack is a near necessity to attack certificate issuance (but this is mostly theoretical: certification authorities could foil all such attacks by using an unpredictable Certificate Serial Number at start of the certificate; and powerful adversaries obtain practically working certificates under any identity they desire without any cryptographic attack, by using complacent certification authorities).

Addition: in practice a trailer can easily be added, so that $H(P\mathbin\|S\mathbin\|T)=H(P'\mathbin\|S'\mathbin\|T)$. The attacker is able to freely choose $P,P',T$, with the constraint $P=P'$ for non-chosen-prefixes collision attacks.


Struggling to understand CFB mode (with DES)

and so $E_k((IV << 8) | C_1 | C_2')$ gives an incorrect encryption

That's your issue; CFB isn't designed to correct for errors in the plaintext - after all, if the ciphertext is not modified, then the decryptor will get precisely what the encryptor encrypted and so if the original plaintext had an error, and then was correct, what the decryptor will get will have that exact same error, and then be correct.

Instead, what CFB is concerned about is if the ciphertext is modified.  As long as $C_3'$ remains in the shift register, yes, the decryptor will get gibberish.  However, after 16 shifts (8 bytes), $C_3'$ will fall out of the shift register.  Then, the 8 bytes will be precisely what the encryptor had intended, and so it will start to decrypt properly (and it will stay so as long as long as no further errors in the ciphertext occur).

Of course, CFB's claim to fame is not that it can adjust to bit flips in the ciphertext (after all, CBC has that same property, and OFB is even better); what CFB does in addition is handle it if segments aren't received at all.  For example, suppose if $C_3$ wasn't received in error, but not received at all; that is, the decryptor received $C_1, C_2, C_4, C_5, C_6,...$.  With CFB, the next 8 bytes will be decrypted incorrectly, however after that, the shift register will resync, and everything later will be decrypted normally.  This is in contrast to CBC, where if a 4 bit chunk was dropped, it would never resync (because everything is processed in 64 bit chunks, and those chunks wouldn't line up anymore).

If you're wondering what could cause such an error, well, way back in the day, there really were communication channels (RS-232, for example) where you could add or drop individual bytes.  Doing CFB over such a line would give a usable encrypted channel, even when that happened.

Of course, nowadays, we're not concerned about recovering about such add/drop errors, and considerably more concerned about attackers who can intentionally cause such errors (and try to gain an advantage for doing so); hence the fashion today is to place sequences of plaintext bytes into records, and perform an authenticated encryption of those records.  Hence, the advantages of CFB aren't seen as an advantage today...


You don't need to adress Shamir's, that is just needed for $k<n$. What you do here is along the lines of the proof that OTP is perfectly secure - actually OTP is one example for this (it is not the general case you are given).

Also see Wikipedia the section "trivial secret sharing", which does list elementwise-XOR with a truly random value for the $2,2$ case (also works for $n,n$. There you just choose $n-1$ shares randomly, and calculate the last one).


Equality check in homomorphic encryption

Depends on what you mean "returns 1 if there are equal".

If you mean "returns an encrypted 1 if there are equal, and 0 if there are not", then here's one straight-forward way; to compare the values $A$ and $B$, you just compute the encrypted value $1 - (A - B)^{p-1}$; that is an encrypted 1 if $A = B$ (because $A - B = 0$), and an encrypted 0 if $A \ne B$ (Fermat's Little Theorem). This takes $O(\log p)$ homomorphic multiplications, and two homomorphic subtractions.

On the other hand, if you mean "returns the value 1", and so allows someone without the private key whether two values are the same, we hope that's not possible.  That would be a violation of the security of the system; it would allow an adversary to determine the value of encrypted plaintexts, and so if it were possible, the homomorphic system would be insecure.


Are those two distributions indistinguishable?

I see no reason to expect $x-1+x^N \bmod N^2$ to be indistinguishable from $r$, at least not based upon the assumption you give.  The map $f(x)= x^N \bmod N^2$ is a very different map from the map $g(x) = x-1+x^N \bmod N^2$.  The range of $f$ is a subgroup of size $\varphi(N)$; that's not true of $g$ (for instance, the range of $g$ can potentially be the entire group of integers modulo $N^2$).  The map $f$ is a $N$-regular map; I don't see any reason to expect $g$ to be $N$-regular in general, and maybe not even regular.  As a third difference, $f(x+kN) = f(x)$, but $g(x+kN) = g(x)+kN$.  For these reasons, I don't expect to find a simple reduction between these two indistinguishability statements.


Why does Diffie-Hellman need be a cyclic group?

Diffie-Hellman operates in a cyclic group by definition: the elements $g, g^a, g^b, g^{ab}$ are in the cyclic group generated by $g$. Technically, a monoid is sufficient, but since cryptography mostly operates in finite structures, you get a group anyway.

In your example, you operate in the cyclic group $c\mathbf{Z}$, and as you were told in the comments, Diffie-Hellman is not secure in this group because an attacker knows $c$ and $ac$, and can thus obtain $a$, and from $a$ and $bc$ can obtain the secret $abc$.


It is an important feature to be able to see if encryption/decryption failed. Sure, padding oracles are a problem, but so is a protocol that doesn't perform intrinsic verification of the performed operation.

If you have a key agreement protocol then you need some kind of method of validating that the decryption of the symmetric key succeeded. Now you could do this by adding a separate authentication tag over some constant value calculated by the generated/decrypted key. That would however leak this information to an attacker. So you probably need to perform the MAC calculation over some challenge, which you would also need to include in the message. You could also create an additional key using the decrypted value as seed, and use that to verify the result, but again: additional operations are required and there is still an authentication tag to be sent. Note that MAC tags can also be vulnerable to (time based) oracle attacks.

What you really don't want is implicit verification, i.e. using the resulting keys and see if you get verification errors over the actual data. I'm using a protocol that does this and it makes for horrific implementation choices. In an update of the protocol explicit authentication with a third key (used to HMAC the handshake) is being utilized.

So currently there is intrinsic verification of the result, in your scheme there isn't. That said, your scheme is probably secure. RSA KEM is even more secure so if you like your scheme you should probably go for RSA KEM and send an authentication tag within the same message containing the encapsulated key.


What is wrong with simple concatenation in salted password hashes?

One difference is that with simple concatenation two different salt-password pairs could lead to the same hash input. For example: H('abcd'||'example@example.com') = H('abcde'||xample@example.com). This cannot happen between your password hashes if you use a constant width salt, but could still happen between your password hashes and those of some other service using the same hash.

With HMAC or another construction that handles the password and salt differently you avoid such collisions. Collisions still exist, of course, if the number of possible passwords and salts is long enough, but they never happen in practice.

If you generate a long enough random salt you avoid the issue even with simple concatenation, and that is usually a good idea in any case, so the practical effect may not be significant in many applications.

In practice the issue should not crop up other than in algorithm design. The best practice is always to use a real password-hashing function, such as bcrypt, scrypt or argon2, and those expose an iterface where you input the salt and password separately.


If my server utilises an RSA based certificate, why does firefox think I am using Diffie Hellman?

There are two different ways a RSA certificate can be used by a SSL/TLS server.

In the "classical" RSA ciphersuites the client randomly picks a secret value, encrypts it with the public key from the server certificate and sends it to the server. The server uses the private key to decrypt it. So the client and server now have a shared secret.

The downside of this approach is that it does not provide "forward secrecy", if the server's private key is later stolen then all previous sessions can be decrypted.

To solve this problem the "ephemeral" cipher suites were introduced where the keys used for the key exchange are generated for a given session and then thrown away. In principle an epheral RSA ciphersuite is possible, but no modern ciphersuite uses that technique for performance reasons (generating RSA keys is computationally intensive).

So in modern "ephemeral" cipersuites the clients agree a shared secret using an epheral DH or ECDH exchange. The RSA (or DSA or ECDSA) key in the certificate is used to sign the key exchange so that the client knows it is communicating with the correct server. These ciphersuites have names like TLS_DHE_RSA_(something) or TLS_ECDHE_RSA_(something) .

The strength of the DH or ECDH keys used in the key exchange itself is independent of the strength of the RSA key used to verify the key exchange. Some older servers default to 1024 bit or worse 768 bit DH parameters.

The preffered option is to set up your server to use 2048 bit or stronger DH parameters. If for some reason that is not possible you should disable the DHE ciphersuites, though be aware that this may cause you to lose forward-secrecy with some clients.


Privately Sum Values without Dealers, MPC

I believe the basic idea is the following:

Choose $m$ so that $\: \sum p_i \:$ can be efficiently recovered from $\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \:\:$.

Each party $i$ chooses $\:n\hspace{-0.03 in}-\hspace{-0.04 in}1\:$ elements $\:q_{i,\hspace{.03 in}j}\:$ of $\:\{0,\hspace{-0.04 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...,m\hspace{-0.03 in}-\hspace{-0.04 in}2\hspace{.02 in},m\hspace{-0.03 in}-\hspace{-0.04 in}1\hspace{-0.02 in}\}$

independently and almost uniformly, where $j$ ranges over the other parties,
and then sends each to the corresponding other party over a confidential channel.

Each party $i$ lets $S$ be the set of other parties, and then lets $q_{i,i}$ be $\;\; \operatorname{mod}\hspace{.02 in}\left(\left(\hspace{.02 in}p_i-\left(\hspace{.02 in}\displaystyle\sum_{j\hspace{.02 in}\in \hspace{.02 in}S} q_{i,\hspace{.03 in}j}\right)\right),\hspace{.03 in}m\right) \;\;\;$.

Each party $i$ lets $q_i$ be $\; \operatorname{mod}\hspace{.02 in}\left(\left(\displaystyle\sum_j q_{j,i}\right),\hspace{.03 in}m\right) \:\:$,$\:\:$ and the broadcasts $\:q_i\:$.

Now, $\;\; \operatorname{mod}\left(\sum p_i\hspace{.03 in},m\right) \: = \: \operatorname{mod}\left(\sum q_i\hspace{.03 in},m\right) \;\;\;$.

The simplest thing to address is the use of the confidential channel. $\:$ First, if there is any way to

do this against a pure eavesdropper, then key agreement is possible, by letting Alice run one party

with a random $p_i$ from a large range, letting Bob run the others, one of which also has a random

$p_i$ from a large range and the others of which have a $p_i$ of zero, and letting the key be least

significant bits of Alice's $p_i$. $\:$ If secure erasure is allowed, then secure key agreement means

that one can lift from authentic channels to confidential channels. $\:$ If secure erasure is not

allowed, then non-committing key agreement would still suffice for that. $\:$ On the other hand,

if authentic channels are not available, then one must proceed as described in this paper.

The more complicated thing to address is the issue of parties lying about their $\:q_i\:$.

For each ordered pair of parties $\:\langle i\hspace{.01 in},j\hspace{.02 in}\rangle\:$,$\:$ there need to be equivocal commitments to $q_{i,\hspace{.03 in}j}$ such

that no secrets are needed to verify openings and the commitments and the committed values are computationally independent of the other $q_{i,\hspace{.03 in}j}$ values. $\;\;\;$ (For the first part, when $i$ and $j$ are different, just have either of them make the commitments and then send the decommit information to the other

of them over a confidential channel. $\:$ The computational independence part is easier than it would normally be because all relevant parties are in communication with each other.) $\:$ Finally, after the parties broadcast the $q_i$ values, the parties must give simultaneous computational zero knowledge arguments of knowledge of how to decommit the $q_{j,i}$ values in a way that is compatible with $q_i$.


This question both describes the SRP-Z variant and mentions that the patent should expire in three years.
I think the patent in question is this one, but I'm not sure: US 6539479. If it is, it seems to actually have expired earlier this year due to non-payment of fees. Looking it up on the USPTO PAIR says:

Status:   Patent Expired Due to NonPayment of Maintenance Fees Under 37 CFR 1.362
Status Date:  04-20-2015

It is still possible it could be revived after such expiry, but IANAL, etc.


Does a hash function in chaining mode or in counter mode make a better pseudo-random number generator?

In cryptography, the standard we use when evaluating a cryptographically secure random number generator is "how much effort does it take to distinguish this generator from a truly random source".

By this criteria, we find that, as specified, your $f_2$ is considerably better than your $f_1$.

With $f_1$, we can distinguish the generator from random (and predict future outputs) by selecting a $r_i$, iterating through the possible values of $l_i$, and find if there is a $l_i$ value that successfully predicts the $r_{i+1}, r_{i+2}, \ldots$ values.  There are $2^{80}$ possible $l_i$ values, and hence this rng can be distinguished with approximately $2^{80}$ SHA-1 evaluations.

In contrast, with $f_2$, where is no known weakness in SHA1 where, given a long series of hashes of related equal-length plaintexts, we can deduce anything about the plaintexts (or, indeed, whether the hashes were from related plaintexts).  Hence, the best approach would be to iterate through the possible $s$ values, and try to find one that correctly predicts the outputs.  There are $2^{160}$ possible $s$ values, hence this approach would take approximately $2^{160}$ SHA-1 evaluations.

In addition, I would notice a practical advantage to $f_2$; it performs one SHA-1 evaluation for every 160 bits of output, while $f_1$ performs one SHA-1 evaluation for every 80 bits of output.  This means that, practically speaking, $f_2$ is likely to be twice as efficient.

On the other hand, while $f_2$ is distinctly better, I couldn't really recommend either; I would suggest you look at the NIST 800-90 random number generators, and in particular, the CTR_DRBG - this would be rather more efficient then either of your approaches.


ChaCha20 has Ind-CPA security and beyond this ( Ind-CCAx.. [1]), you need integrity and authentication. And note that Authenticated Encryption > Ind-CCA.
ChaCha20 is already teamed with Poly1305 authenticator to provide confidentiality, integrity and authentication. It exists in TLS standards and one of the five cipher suites in TLS 1.3 as ChaCha20_Poly1305.
If you are going to use ChaCha20 it is better to use XChaCha20-Poly1305 since it has larger nonce sizes (192-bit) so that randomly generated nonces are safe against the collisions, you need $2^{96}$ random nonces to hit another one with 50% probability and that is almost impossible.


What is the importance of Rcon in Rjindael's key expansion from a security prespective?

According to Section 3.8 of "The Design of Rijndael", authored by the cipher's creators, the purpose is to eliminate symmetries in the key schedule:

  The non-linear function is realized by means of the application of $\mathrm S_\mathrm{RD}$ to the four bytes of the column, an additional cyclic rotation of the bytes within the column and the addition of a round constant (for elimination of symmetry). The round constants are independent of $\mathrm N_\mathrm k$, and defined by a recursion rule in $\operatorname{GF}(2^8)$:

(Emphasis mine.)

Section 5.8 elaborates a bit more on this:

  For the key schedule in Rijndael the criteria are less ambitious. Basically, the key schedule is there for three purposes.

  The first one is the introduction of asymmetry. Asymmetry in the key schedule prevents symmetry in the round transformation and between the rounds leading to weaknesses or allows attacks. Examples of such weaknesses are the complementation property of the DES or weak keys such as in the DES [28]. Examples of attacks that exploit symmetry are slide attacks.

(Emphasis mine.)

To summarize: Adding the round constants $\mathrm{Rcon}$ is a very cheap way (it's not that many cycles) to make each step of the key schedule slightly different, avoiding a variety of attacks that have become apparent in the past.


RSA - is it possible to find the modulus from both the private and public exponents?

It turns out that recovering $N$ from $e, d$ is a hard problem; in particular, if you can, you can factor values that are currently believed to be intractable (!).

To start with, a necessary and sufficient condition on $e, d$ being valid RSA exponents to a square-free modulus $N$ is that, for every prime factor $p$ of $N$, we have:

$$ed - 1 = k(p-1)$$

for some integer $k$.

Now, let us assume that we have an Oracle that, given $e, d$, will recover a value $N$ for which $e, d$ are valid RSA exponents (assuming there is such an $N$); we further assume that it gives a reasonably large value $N$, specifically, one in the range $\ell \sqrt{eq} < N < 5ed$ (for a modest constant $\ell$).

Now, suppose that we have a value $N = pq$, where $p, q$ are both unknown Sophie-Germain primes (that is, $2p+1$ and $2q+1$ are also prime), and are approximately the same size; that is $q < p < 2q$.  We will also assume that the value $2pq+1$ and $4pq+1$ both happen to be composite (which it will be for a majority of the possible $p, q$ pairs).

Assuming $N$ is sufficiently large, there is no known way to factor it.

We note that $p \equiv q \equiv 2 \pmod 3$, and hence $2N + 1$ is a multiple of 3.  So, we set $e = 3$ and $d = (2N + 1)/e$; and give $d, e$ to our Oracle.

What the Oracle will do is return a value $N' = p_1' p_2' … p_n' $ (where $p_1', p_2', …, p_n'$ is the prime factorization of $N'$.  Such an $N'$ will always exist, as $N' = (2p+1)(2q+1)$ is such a valid modulus (hence the Oracle must return some value, if not necessarily $(2p+1)(2q+1)$

Because of the condition on RSA exponents, we have $ed - 1 = 2pq = k_i(p_i' - 1)$ for every prime $p_i'$.

Because of the range limitation on $N'$ (that is, $\ell \sqrt{eq} < N'$), we must have $p$ as one of the factors of $p_i' - 1$ (for some $i$), and similarly have $q$ as a factor of $p_j'-1$ (for some different $j$; it must be different, otherwise this prime factor would be $2kpq+1$; we assumed that $k=1$ and $k=2$ didn't yield a prime, and $k>2$ have a value outside the $5ed$ range we assumed).

Hence, we have $N' = k''(k'''p + 1)(k''''q + 1)$, for modest $k'', k''', k''''$.  Given that, and $N = pq$, it's easy to factor $N$.

This is much more of a sketch than I originally intended; there are a number of missing details.  However it should not be hard to fill in the details...


The one metric that generically matters in cryptography for a physical entropy source is the min-entropy: the exponent of the most probable outcome, in bits.  This depends on the physics of the entropy source.  As long as it exceeds 256, you can feed a sample through a typical preimage-resistant hash function such as SHAKE256, a conditioner, and you will have what is effectively a uniform random string fit for use as cryptographic key material.

(Sometimes the physical device is called a TRNG; sometimes the composition of the physical device and the conditioner like SHAKE256 is called a TRNG.)

If your device can't produce a sample with that much min-entropy at once, but it can produce a sequence of IID samples, then you can concatenate them.  The result may be much longer than 256 bits—even if it is very far from uniform in whatever is your favorite measure of statistical distance, what matters for cryptography is only that its min-entropy be at least 256 bits.

The NIST tests hypothesize various families of probabilistic models for the entropy source, fit parameters based on a sample, and then print the entropy of the models with the fitted parameters.  These models are very simple-minded and were designed without knowledge of your device, so they are at best a way to spot-check particularly obvious predictable distributions—so obvious an engineer thought of them without even knowing what your device is.  (More details on how ‘entropy tests’ work.)

Generic measures computed on samples from your device, designed without reference to any model of the physics of your device, have very little value in studying the security of the system.  The min-entropy you advertise must be computed from a specific probabilistic model of the physics of the system to give any meaningful confidence in it.


Does the block size of a symmetric cipher impact the security of the cipher itself?

Yes, absolutely. A small block size limits the amount of data that can be encrypted with a given key, and some block modes are more badly affected by this than others. Additionally, some cryptographic attacks against weak ciphers can be made more practical against a block cipher with a small block size, such as the slide attack, which becomes very difficult to implement when the block sizes are large.

The classical issues with small block sizes are well documented, and other questions on this site on that topic have been answered. Generally, a small block size opens up a can of cryptographic worms regardless of whether or not your adversary is quantum-capable. A 32-bit block size is silly. A 64-bit block size is worrying and can be insecure in certain situations. A 128-bit block size is okay. A 256-bit block size is better. A 512-bit block size is generally excessive. This holds true, quantum or not.

  Will a 128 bit block have some security implication in post-quantum cryptography?

No, a small block size will not generally be affected by quantum computers. The quantum algorithm that would be responsible is Grover's algorithm, which is a search algorithm. All the attacks against block ciphers that rely on a small block size are limited by the amount of ciphertext the attacker has, not by the number of operations an attacker is able to perform. Sweet32, slide attacks, etc. depend on nothing more than being able to collect a lot of ciphertext that has been encrypted under a single key. Once sufficient data has been collected, the number of computations required to break the guarantees of the cipher are not great enough to benefit substantially from Grover's algorithm.

It's important to note, however, that a block cipher used for authentication, e.g. with CBC-MAC, is more vulnerable against a cryptanalytic quantum computer. The reason for this is that a small block size results in a small authentication tag size, and Grover's algorithm can be used to brute force the small tag with more ease. The same is true if the block cipher is used as the core of a hash function, which would result in smaller digests that are easier for a quantum computer to attack.


(Responding to Squeamish Ossifrage) Threshold signatures do not require any single member to reconstruct the whole secret. Ideally each party produces a partial signature and only when they are all combined is the signature valid.

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

This enables a pre-determined group to share a single schnorr identity without changing the verification side of the protocol. Any subset of $k$ members may collaborate to sign a common message. The secret sharing is verified and the dealer cannot cheat. The co-signers cannot be tricked by their peers.

MuSig: n-of-n threshold schnorr via aggregation

MuSig also doesn't change the verification side. A group is derived from the list of all public keys required to sign the common message. With only two-rounds of communication, the group produces the signature.

Crypto conditions: off-chain contracts resolving to minimal proofs of execution

Crypto-conditions are a form of multi-sig contract that doesn't attempt to aggregate any identities. Instead it uses hash commitments to commit to some boolean circuit. I.e. A contract may require "either Alice, or both Bob and Carol", or any arbitrary logic. The contract is a single hash. The proof of execution reveals only the relevant branches. The contract is valid if all leaves are valid and all intermediate steps have appropriate thresholds.

ANY-k is implemented as k-of-n. OR/ANY as 1-of-n. AND/ALL as n-of-n. A fullfillment may be either a hash-lock that is just a revealed symmetric secret key, or a signing public key whose corresponding secret signs the transaction that it approves.

Any irrelevant (or dead/unresolved) branches are truncated to a single hash commitment; enabling an arbitrarily large contract to resolve to a minimal proof.

Conclusion

I believe it would be worth implementing all of these. Notably $(t,n)$ enables a group to divide their signing right such that no single, or fewer-than-t subset may impersonate the group. N-of-N MuSig enables opportunistic groups to compress the crypto-condition contracts, which can describe any boolean circuits - not just subsets or all.

bonus: BLS is signature scheme that supports aggregation of many distinct-signatures. But this is not schnorr-friendly and does not work with any curves not explicitly designed to be pairing-friendly.


Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?

As a general rule, you should not use SHA1; instead, go with one of the hash functions from the SHA-2 family.

As far as truncating a hash goes, that's fine. It's explicitly endorsed by the NIST, and there are hash functions in the SHA-2 family that are simple truncated variants of their full brethren: SHA-256/224, SHA-512/224, SHA-512/256, and SHA-512/384, where SHA-$x$/$y$ denotes a full-length SHA-$x$ truncated to $y$ bits. (Technically the starting algorithm constant is different for the truncated versions, as pointed out by Henno Brandsma, but this is somewhat orthogonal to the point I'm trying to make.)

  Are there any security implications for hashing and storing sensitive data like this?

As far as determining the sensitive material from the digest itself, you're safe. All secure modern-day cryptographic hashes have what is called preimage resistance, which essentially means that it is computationally infeasible to "reverse" the hash, if you will. So, your sensitive data's confidentiality won't be compromised by storing the digest. (Note: See Gordon Davisson's comment below about this; there are possible security implications in some scenarios.)

Now, the real question is: why are you wanting to store the hash in the first place? Hopefully you are not using it to detect if the data is maliciously modified; that generally is the purview of a MAC, such as HMAC or CBC-MAC.

  Is it more or less secure than using the full SHA1 hash?

Much more secure, actually, if you care about collision resistance. There is an attack on SHA1 that finds collisions in 260 time, whereas truncating SHA-512 to 160 bits requires 280 time to find collisions (see the birthday attack). So, truncating one of the SHA-2 functions to 160 bits is around 220 times stronger when it comes to collision resistance. (Plus, finding collisions is now within the realm of possibility for SHA1. So, if you are reading this, and you are building a new system, you should choose SHA-2 or SHA-3.)

  Is there an increased risk of hash collision when using the truncated version?

Increased risk over SHA1? No. Increased risk over using the full SHA-512 output? Yes.

Truncating the output of a hash function always decreases its (theoretical) collision-resistance. In practice, it usually doesn't matter too much; for instance, 280 time is still pretty big. Still, if you used the full output of SHA-256, the same birthday attack would take 2128 time, which is totally out of reach.

  by truncating it a potential hacker wouldn't know which algorithm was used in the first place

Always assume the attacker knows everything about your algorithm/cryptosystem except for the secret keys. This is known as Kerckhoffs's principle. Why this is important is well-covered, so you should follow it.

  My understanding was that SHA1 would always produce a unique value, whereas there is a chance that the first 40 characters of a SHA512 output could appear many times.

SHA1 doesn't produce unique values. There are infinitely-many possible inputs to SHA1 (it takes a bitstring of any length), yet there are only 160 bits of output. By the pigeonhole principle, there have to be infinitely-many values that map to the same 160 bits of output. In February 2017, a SHA-1 collision was published. However, there have not been any published SHA-256 collisions to date, despite that the pigeonhole principle guarantees they exist.

I should note, if you are going to use the full output of SHA1, SHA-256, or SHA-512, you should be aware of length extension attacks.


Is my identity exposed when publishing my public key or encrypting with PGP?

Yes, your public key includes your UIDs. It may be possible to delete all before exporting though - for sure you could copy the key, add an "anonymous" UID and delete all others.
As long as you're not signing the message, nobody will know who sent the message (but have a look at the mail or other headers!).


Big block cipher as memory-hard function

I've been toying around with your function, and I've come to the conclusion it's not memory hard. The amount of required memory can be reduced to at maximum digestsize * 3 * rounds.

The first problem is that the entropy does not avalanche throughout the state, but stays localized. For example, after 1 round the state of the 2nd block only depends on the state of the 3rd block. After 2 rounds it (indirectly) only depends on the initial state of the 3rd and the 4th block. This means that an attacker could precompute 1024 rounds on a large portion of the constant and not need per-password memory for that.

A possible improvement would be to turn around the mixing to state[i mod size] = state[i mod size] ⊕ F(state[i - 1 mod size]) so that each block depends on the previous instead of the next, but the fact that you're generating & hashing in the same order will always make tradeoffs possible. Changing that order, preferably in a data-indepent way (e.g. by reversing the order of the blocks after each round), would make that way more difficult.

To illustrate my point, here are 2 codes: 1 with, and 1 without a memory tradeoff on your function:

#!/usr/bin/env python3
from hashlib import sha512

blocks = 1000
rounds = 100
# pseudorandom constants created by hashing the literals "0", "1", ... "1000"
constants = [sha512(str(i).encode()).digest() for i in range(0, blocks)]

def mix(a, b):
    global operations
    operations += 1  # statistics
    b = sha512(b).digest()
    return bytearray(a ^ b for (a, b) in zip(a, b))

def more_memory(constant):
    state = list(constant)

    for i in range(0, rounds * blocks):
        state[i % blocks] = mix(state[i % blocks], state[(i + 1) % blocks])

    # Make a checksum for the entire state
    state_hash = sha512()
    for s in state:
        state_hash.update(s)

    return state_hash.hexdigest()[:32]

def less_memory(constant):
    def perform_round(sequence):
        first = None
        cur = next(sequence)

        try:
            while True:
                after = next(sequence)
                result = mix(cur, after)
                yield result
                if not first:
                    first = result
                cur = after
        except StopIteration:
            pass

        yield mix(cur, first)

    current = (s for s in constant)
    for _ in range(0, rounds):
        current = perform_round(current)

    # Make a checksum for the entire state
    state_hash = sha512()
    for s in current:
        state_hash.update(s)

    return state_hash.hexdigest()[:32]

operations = 0
print('Using a lot of memory: {} ({} mixing-operations)'.format(more_memory(constants), operations))
operations = 0
print('Using little memory: {} ({} mixing-operations)'.format(less_memory(constants), operations))

# Prints:
# Using a lot of memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)
# Using little memory: e58f5665a2c388fc1420d4d1667f83df (100000 mixing-operations)


Is the following aggregation scheme private?

Well, it has the obvious problem that if the UA has both $d_1H(r)^{k_1}$ (from the party) and $H(r)^{S-k_1}$ (from the UA), it can compute $d_1$ directly.


CBC related TLS cipher suites to be disabled in the server side

Based on the useful comments above, some of the resources I found to provide an insight into the matter is as follows:

TLS Support tells us which browser versions support which TLS versions. Since (as puzzlepalace mentioned) GCM was introduced in TLSv1.2, we get an idea as to what browser versions we'll miss out by supporting only GCM
Qualys (as forest mentioned) shows some of the best SSL configured website and the cipher suites used. This also shows the cipher suites used by your browser. The best practices for TLS deployment and the recommended list of cipher suites are listed here. Finally, this table lists which browser versions support what.

In summary, all major browsers support TLS 1.2 since Oct, 2013 and therefore GCM.

Forward secrecy (ECDHE) is available from even before.


Is the logic for how the enigma machine worked documented somewhere?

Yes!

If you're really interested in "diving in deeper" (pun intented), I would like to advise you to check out:

"The Cryptographic Mathematics of Enigma"
Dr. A. Ray Miller
NSA. Center for Cryptologic History. USA. 1996. 3rd edition 2002
"Funkpeilung als alliierte Waffe gegen Deutsche U-Boote 1939-1945."
Arthur Bauer
ISBN: 3-00-002142-6. The Netherlands, 1997. German. p. 33.


Standard or guidance for entropy collection

As far as I can tell, NIST has only one official document about entropy collection. SP-800-90B.

  The purpose of NIST Special Publication (SP) 800-90B is to
  specify the design and testing requirements for entropy sources that can be validated as approved entropy sources by NIST‘s CAVP and CMVP.

It essentially defines a bunch of statistical tests to check the strength of a particular entropy source. Seeking entropy methods that meets the requirements is a good first step especially if you need "official" certification by NIST.


Will adding space to the Vigenère block make it truly unbreakable?

I believe you need a few clarifications to answer this question yourself.

The first is the one time pad (OTP). This is the only truly unbreakable system if it's used correctly.

Using correctly means that for every symbol of the message there is exactly one truly random symbol in the key. Specifically, this means that there is no chosen symbol of the key that is used twice (of course a symbol can occur twice in the key; I mean that for every symbol of the message there is a new symbol chosen for the key with its own randomness). The message includes spaces, so spaces need to be encrypted as well! This is what your thought was when you said to extend the table with a space.

The Vigenère cipher has a repeating key in its original definition. If you choose the key to be exactly as long as the message (and encrypting every symbol of the message, not just the letters) and you chose this key randomly, then the Vigenère cipher becomes the One Time Pad and is thus, as you correctly said, unbreakable.

If your message has more than 27 symbols (for instance capital letters, punctuation etc.) then your key must be extended, as well.


How is the initial permutation of DES created?

The Inital Permutation is defined in the DES specification. This spec numbers bits from 1 to 64 in big-endian reading order. The table gives the bit numbers in the 64-bit block input, to be selected to build the L and R registers:
58  50  42  34  26  18  10   2      L, bits  1 to  8
60  52  44  36  28  20  12   4      L, bits  9 to 16
62  54  46  38  30  22  14   6      L, bits 17 to 24
64  56  48  40  32  24  16   8      L, bits 25 to 32
57  49  41  33  25  17   9   1      R, bits  1 to  8
59  51  43  35  27  19  11   3      R, bits  9 to 16
61  53  45  37  29  21  13   5      R, bits 17 to 24
63  55  47  39  31  23  15   7      R, bits 25 to 32

This table is extremely regular: each value is 8 more than the value on its right, if any. More: the transformation is a near transposition, and becomes one if we make a left/right mirror, and bring the lines with octets of R before the corresponding lines for L.
That regularity comes from the initial implementation of DES in hardware: the plaintext was loaded sequentially as 8 octets, with at each of 8 loads each of the 8 bits of an octet entering an 8-bit shift register, 4 of which for L, 4 of which for R, with these 8 shift registers clocked simultaneously. A natural software implementations can mimic that (among other possibilities).
For the highest performance in software, see Richard Outerbridge's implementation. That uses a general technique to implement transpose using wordwide operations, tunes it to the slightly irregular transpose that IP is, and (in some variants) performs a 32-bit rotate by 1 bit of L and R than can speed-up the rest of DES.
Other than easing hardware implementation, the initial and final permutation have no know design purpose. They do not increase (or decrease) security of DES. They slow software implementation a little, but there is no indication that's explicitly among the design goals (which broadly are to make DES fast, and secure from all attacks except brute force, see this).


Keyfobs that do a handshake are actually quite common, see the HiTag2 key transponder specifics for how its handshake works.

Even without a handshake, the code can still identify the key if it is long enough, and cars can be programmed to accept multiple keys, but almost certainly there is a handshake involved.

I believe your key probably uses a Ford type transponder chip, probably transmitting at 315MHz for long range commands like door unlock, and a lower freq for engine start (123-134KHz). For engine start, the car tells the key it wants to start and adds a challenge code, then sends to the key. The key encrypts the challenge, resulting in an 80-bit code, then truncates to 40-bits and transits back with its serial number and a checksum. The car then verifies the code, and starts if it is correct.

I am not sure if the high frequency commands use the same cipher, but they are a 1-way transmission. Similar to how a garage door opener can use 2 remotes, the car can use 2 keys to unlock doors without a handshake, as internally the car will see that the code matches a programmed key.


Is it safe to send HMAC and plaintext in the same message?

If a certain protocol sends plaintext and its corresponding HMAC then is such a protocol prone to key extraction attacks?

No, a HMAC uses a cryptographically secure, one-way hash underneath. That means that it should be impossible to find the input as long as the input cannot be brute forced. If you use a key of the right size (identical to the hash output size) and with enough entropy then the key cannot be found, even if the plaintext is available to an attacker.

  Intuitively , HMAC is ciphertext generated from plaintext, (although not an encryption of plaintext), so the only secret being key.

An authentication tag is not the same thing as ciphertext. But even with known plaintext & authentication tag (or ciphertext) the key should not be found.

Of course, an attacker should also not be able to create a new plaintext / authentication tag pair even if the attacker knows multiple other such pairs. Therefore HMAC also protect against e.g. length extension attacks, for which knowledge of the key is not required.

  Will sending both of them together weaken the protocol?

It is nowadays common to HMAC the ciphertext (encrypt-then-MAC), for instance to avoid padding oracle attacks on CBC mode encryption. So for the HMAC, the ciphertext is the plaintext in such a scheme. If knowing the plaintext / authentication tag is a vulnerability then many protocols are broken.

Commonly cryptographic schemes should even be secure if the attacker chooses the plaintext (CPA secure).