How confident can we be that nobody will crack a 128-bit key?

This question seems to be asking us how fast will computers grow. No cryptanalytic breakthrough and no quantum computing essentially means no attack faster than brute force.

So will humanity at some point in the future with significant resources be able to brute force 128 bit key?
I would answer, maybe. 256 bit key Almost definetly not.

Obviously predicting is hard especially the future but assuming humanity will not self destruct it will continue to progress and it is not unreasonable to assume it will come close to the limits of what is possible.

The main discussion on theoretical limits of brute force is in minim energy requirements. I suspect we may be short on physicists on crypto stack exchange so I will try.

Brute forcing a key requires enumerating the keys. And that requires changing bits. Each bit change erases some information and there is a minimal amount of energy required for that. Lauder's limit
https://en.m.wikipedia.org/wiki/Landauer%27s_principle

For brute forcing a 128 bit at room temperature this comes out 262.7 Twh(the annual electricity consumption of Spain) that is a lot But not something humanity can't achieve.  By lowering the temperature we can improve on this. And some say we could build another type of computer which doesn't erase information and this limit won't apply to it. Though such a computer might go against the spirit of the question which excluded quantom computers.

So we don't actually have any good theoretical limits to prevent humanity from brute forcing a 128 bit key eventually. Which leads to my answer. Maybe.

For 256 bits the same energy limit would put brute forcing well outside the realm of the possible.


If $p = 2q+1$ where $q$ is prime, and then we can efficiently solve for $x_0 \in \{0, 1\}$ for $g^{2x+x_0} = h \pmod p$, if $g$ is a generator.

This is true; this is a special case of the observation "if $g$ has order $a \times b$ with $b$ small, then if $g^y = h$, then we can find $y \bmod b$ quickly (specifically, in $O(\sqrt{b})$ time).

As $g$ is a generator for the entire group, it has order $2q$, and so we can find $y \bmod 2$ quickly (or, as you put it, find $x_0$ where $y = 2x + x_0$)

  Suppose $g^2 = r$, then why cannot I reduce the problem to $r^x = hg^{-x_0} \pmod p$

Well, I suppose you could, but solving that would be as difficult as the DLog problem (actually, that's provable; given an Oracle to do that, you can solve the entire DLog problem).  The previous observation doesn't help you solve this problem; $r$ has order $q$, which is a prime; it doesn't provide any magic ways to compute $x \bmod 2$; the best it can do is find $x \bmod q$ in $O(\sqrt{q})$ time, and we have more efficient ways than that.

  Suppose I know $x_0$ in $g^{3x+x_0} = h \pmod p$, which $x \in \{ 0, 1, 2 \}$, would that help.

Yes, if you had an Oracle that could find $y \bmod 3$, then you could efficiently solve the DLog problem.  That said, we don't know any way to do that efficiently (assuming that the order of the group wasn't a multiple of 3).


Security of AES CTR with multiple messages containing the same known plain text

This is a type of chosen-plaintext attack, where the adversary gets partial choice of plaintexts — they can cause the same substring to be encrypted multiple times.

AES-CTR, if used properly, is resistant to chosen-plaintext attacks.

Used properly, for CTR mode, means that the same counter value must not be reused for different messages. For example, if one message is 48 bytes (3 blocks) long and is encrypted with the starting counter value 12, this uses up counter values {12, 13, 14}. Other messages must never use those counter values; for example, another 3-block message may use {9, 10, 11}, but not {14, 15, 16}.

CTR encryption calculates $N_i \oplus P_i$ where $N_i$ is the counter value for the $i$th block of the message and $P_i$ is the plaintext. If a counter value is repeated ($N_i = N_j$ with $i \ne j$, whether within the same message or in different messages encrypted with the same key), the xor of the two ciphertexts is $(N_i \oplus P_i) \oplus (N_j \oplus P_j) = P_i \oplus P_j$; if the plaintext for one of the blocks is known or guessed then so is the plaintext for the other block.


Cryptographic equivalent of family coat of arms

You can put almost any information in an X.509 certificate, and then pass the private key for the matching certificate along. People can of course claim that the certificate is theirs, but when holding the private key, you can prove it belongs to you.

Of course, you might need a central authority for the certificate to be trusted, but you can send a certificate request to many CA's. Of course, if there is sufficiently weird info in there to be notified you may need to explain the applicability (and most likely, pay up, but I guess that comes with the domain). If you start to dislike the CA you can always switch to another one.

Probably easiest is to include an URL to a website with e.g. an actual coat of arms.

Digital information is usually not used to show off. If you require something more physical then you could get e.g. a gold leafed ePassport. For that you would probably need a high up person in the government (and be a complete and utter - well you can fill that one in yourself).


I think this is a very good question, and an interesting one. Not sure if my answer will go in the direction you meant.

Generally when first discussing the DLP for groups, you'd want to find an attack which uses only the most basic properties of a group. That is, you think of having a black box into which you can feed any two group elements, and it will compute the group operation on them. You see the result, but have no idea how it was computed.

Now suppose we have such a black box group, and assume that it is cyclic of prime order $r$. Then this paper proves that you need on average at least $O(\sqrt{r})$ calls to the black box to solve the DLP. For those groups we are sure that the DLP is hard, for some definition of "sure" and "hard".

This may be somewhat counterintuitive. Note that for a prime $p$, $\mathbb{Z}/p\mathbb{Z}$ with addition is a prime order group for which the DLP is trivial. Also for every black box group $G$ such that $|G|=p$ there exist an isomorphism $\phi:G\cong \mathbb{Z}/p\mathbb{Z}$. The problem is that we cannot reduce the problem from the black box group $G$ to $\mathbb{Z}/p\mathbb{Z}$, since we cannot compute the isomorphism $\phi$ efficiently.


mixing round functions and key schedules

Assuming the 2 algorithms play well together you would end up with a composite of the cryptographic properties of both algorithms - the key schedule would have the properties of X's key schedule and the round function would have the properties of Y's round function. Taking them out of context of their original algorithm won't (usually) change their cryptographic properties.
Many encryption algorithms have been built like this, and the scheme tends to work. That said, you still need to make sure they play well together but that's easier than reviewing an entirely new algorithm.
Update
A list of algorithms using components from other cryptosystems is as follows:

TwoFish

Twofish's distinctive features are the use of pre-computed key-dependent S-boxes, and a relatively complex key schedule. One half of an n-bit key is used as the actual encryption key and the other half of the n-bit key is used to modify the encryption algorithm (key-dependent S-boxes). Twofish borrows some elements from other designs; for example, the pseudo-Hadamard transform[3] (PHT) from the SAFER family of ciphers. Twofish has a Feistel structure like DES. Twofish also employs a Maximum Distance Separable matrix.

SAFER

In cryptography, SAFER (Secure And Fast Encryption Routine) is the name of a family of block ciphers designed primarily by James Massey (one of the designers of IDEA) on behalf of Cylink Corporation. The early SAFER K and SAFER SK designs share the same encryption function, but differ in the number of rounds and the key schedule. More recent versions — SAFER+ and SAFER++ — were submitted as candidates to the AES process and the NESSIE project respectively. All of the algorithms in the SAFER family are unpatented and available for unrestricted use.

RC6

In cryptography, RC6 (Rivest cipher 6) is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard (AES) competition. The algorithm was one of the five finalists, and also was submitted to the NESSIE and CRYPTREC projects. It was a proprietary algorithm, patented by RSA Security.

DEAL

DEAL is a Feistel network which uses DES as the round function. It has a 128-bit block size and a variable key size of either 128, 192, or 256 bits. For key sizes of 128 and 192 bits, the cipher uses 6 rounds, increasing to 8 for the 256-bits size. The scheme has a comparable performance to Triple DES, and was relatively slow compared to many other AES candidates.

CAST-256

CAST-256 uses the same elements as CAST-128, including S-boxes, but is adapted for a block size of 128 bits – twice the size of its 64-bit predecessor. (A similar construction occurred in the evolution of RC5 into RC6). Acceptable key sizes are 128, 160, 192, 224 or 256 bits. CAST-256 is composed of 48 rounds, sometimes described as 12 "quad-rounds", arranged in a generalized Feistel network.

Camellia

Like other AES candidates, E2 operates on blocks of 128 bits, using a key of 128, 192, or 256 bits. It uses a 12-round Feistel network. E2 has an input transformation and output transformation that both use modular multiplication, but the round function itself consists only of XORs and S-box lookups. The single 8×8-bit S-box is constructed from the composition of an affine transformation with the discrete exponentiation x127 over the finite field GF(28). NTT adopted many of E2's special characteristics in Camellia, which has essentially replaced E2.


Testing the frequency of bytes produced by an ideal (uniform) random generator per question's method with $1200$ samples or more gives a $\chi^2$ that varies typically by few dozens around the average, $255$. It should be below $254.334$ for 50% of experiments, and the most likely values those closest to $253$.

For a good uniform random sequence of bytes, and "enough" samples, the distribution of $\chi^2$ computed as in the question has a well-studied distribution: the $\chi^2$ distribution with $2^8-1=255$ degrees of freedom, with this Probability Density Function:

The mean is $255$ (that's what you obtain by averaging the $\chi^2$ of many experiments). The median is $\approx254.334$ (the $\chi^2$ is less than this for 50% of experiments). The mode is $253$ (that's the most likely value, maximizing the PDF).

The standard deviation is $\sigma=\sqrt{510}\approx22.58$. Because the PDF is close to a normal, the 68–95–99.7 rule applies: that gives the probability (in percent) to be one, two and three $\sigma$ from the mean. Again that's with "enough" samples. A rule of thumb tells that about $5$ samples per expected value (thus like $1200$ samples) starts to be enough when reasoning at up to $2\sigma$. More sample usually help (I wish I knew how to more rigorously choose the minimum number of samples).

The Cumulative Density Function $\displaystyle\operatorname{CDF}(x)=\int_0^x\operatorname{PDF}(u)\ du$ is:

That tells the expected proportion of experiments (for a uniform random sequence) where the computed $\chi^2$ is less than a certain value.

We have a 0.05% chance that the $\chi^2$ is less than $187.171$, and 0.05% chance that it is above $335.917$. Thus in only about one experiment out of 1000 will the $\chi^2$ will be out of that range, for a truly uniform random sequence, and "enough" samples.

In particular, a generator that consistently gives low $\chi^2$ is not random!

When we generalize to different tests with a random variable taking one out of $n\ge2$ different outcomes with expected frequencies $e_i$ and $\displaystyle1=\sum e_i$, and the number of samples is at least about $5/\min(e_i)$ (enough for a minimum of $5$ expected samples for each value), then the distribution of $\chi^2$ is the $\chi^2$ distribution with $k=n-1$ degree(s) of liberty.

The shape of the Probability Density Function vary with $k$.

The mean is $k$, the median is about $k(1-2/9k)^3$, the mode is $\max(0, k-2)$.The variance is $\sigma=\sqrt{2k}$, but for low $k$ computations or tables (rather than estimations based on $\sigma$ and a normal approximation) are necessary.

The shape of the Cumulative Density Function vary with $k$:


If you define one round of your Even-Mansour cipher as: $$c \leftarrow P(\operatorname{Salsa20}(k, f(\text{nonce}, \text{round})) + m)$$

Where $P$ is your public fixed permutation, $f$ is some function that ensures the combination of nonce and round number don't lead to repeating nonces, and $\operatorname{Salsa20}$ is the Salsa20 stream cipher.

And assume that:

Salsa20 is a secure stream cipher
The Even-Mansour cipher uses one round
The permutation is the identity permutation

Then the proposed Even-Mansour cipher is secure. To see this, simply drop the permutation and round counter altogether and get $$c \leftarrow \operatorname{Salsa20}(k, nonce) + m$$

If $\operatorname{Salsa20}$ is assumed to be secure, then the above is secure.

The latter two assumptions of a single round with the identity permutation are the worst case scenario. More rounds and an alternative permutation should not make the design weaker.

However

This also demonstrates that there is little benefit to using more than one round and an additional permutation.

Note also that with more than one round, the $f$ function needs to be designed to ensure that the combination of nonce and round counter never leads to the generation of repeated key streams. It is conceivable that failure to do so could lead to an Even-Mansour cipher that is trivially broken despite Salsa20 being secure, e.g. a 2 round variant where rounds 1 and 2 result in the same key stream being generated, leaving the plaintext message unaltered.

If Salsa20 is secure, then there is no real benefit from embedding it inside of another encryption algorithm. The extra complexity could lead to something that is broken, despite Salsa20 being secure.


How should I read these three-dimensional (pseudo)random-generated numbers representations?

One of the key properties we want out of PRNGs is that they produce results that follow a desired probability distribution.  Nearly all of the time we want our PRNGs to produce data with uniform distribution—all of the possible output values should have equal probability.

So let's assume that we are given a seq sequence whose values are samples drawn from a uniform distribution.  We can now ask: what should be the distribution of the x, y and z sequences?  Well, since they're defined as sums of values drawn from a uniform distribution, this is the same sort of distribution we get from throwing a pair of dice and adding their results, where a 7 is six times more likely than a 2.  So the distribution we should ideally see in that page's data is:

A cube with a hard boundary (just like we can't roll a 1 or a 13 from the dice);
Centered around (0, 0, 0) (because the expected value of the subtractions is zero);
Denser toward the middle and sparser toward the boundary (just like throwing a seven is more likely than a two).

The Windows NT SP3 graph very obviously deviates from that pattern:

  I would expect to be the Windows NT4 the less easy to attack because in its distribution the points seems to be better distributed respect to the "cube" of Windows 2000 distribution.

What you should be thinking of is how closely does the distribution resemble the "ideal" one for the scenario in question.  This is the approach that I took above:

I picked uniform distribution as the ideal for sequence numbers;
And from that it follows that I must pick the "dice roll" distribution as the ideal for x, y and z.

Then, any significant deviation from the ideal distribution should be seen as a potential flaw.  Why?  Because non-ideal distribution means that some values are more likely than they ought to be, and thus that the attacker will succeed faster than they ought to by trying such values first.

  But, given this, I can not understand how points plotted are related: for example, what I should think about two near (respectively: far) points? are sequence numbers with low differences or high differences?

The magnitude of the distances between points isn't important.  What's important is whether those distances are predictable at a higher-than-chance success rate.  And this gets to the heart of the attacks they're analyzing here.  By looking at the distributions of the differences they are able to build models that predict the ISNs for various operating systems with better-than-chance success rates.

Finally, look at your definition of seq and notice that the differences in question are between the elements of consecutive quadruples of the ISN sequence.  If these differences are highly predictable, what it tells you is that you can easily guess the next sequence number just from knowing the previous ones, by guessing the next differences and adding them to the recently observed ISNs.


Is the last step of an iterated cryptographic hash still as resistant to preimage attacks as the original hash?

If the hash function is any good, then it should behave as a "random function" (i.e. a function chosen randomly and uniformly among all possible functions). For a random function with output size $n$ bits, it is expected that nested application will follow a "rho" pattern: the sequence of successive values ultimately enters a cycle with an expected size of $2^{n/2}$; and the length of the "queue" (the values before entering the cycle) should also be close to $2^{n/2}$.

So, theoretically, recursive application weakens the function with regards to preimage resistance, but the weakening is low-bounded by $2^{n/2}$, a boundary which requires an awfully big number of invocations to be reached.

Moreover, when we select a hash function, we want to have decent resistance to collisions, and collisions can be found with effort $2^{n/2}$. So we already choose hash functions such that $2^{n/2}$ is unreachable (e.g. we use SHA-256, because $2^{128}$ is far beyond what can be realistically achieved with Earth-bound technology; see this answer for a discussion on the subject). In short words, the weakening through recursive application has no practical consequence (while the time taken to compute all the hashes improves things greatly with regards to dictionary attacks).


Chosen plain-text Attack on DES-X with roughly $2^{64}$ DES operations

I'll take the question as: with all plaintext/ciphertext pairs $(p,c=\operatorname{DESX}(p))$ at hand, how do we efficiently find the DESX key $(K_1,K_2,K_3)$?

The main idea is to observe that (independently of the DES complementation property), for any fixed $\delta\ne0$, $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus \delta)$ matches $\text{DES}_{K_2}(0)\oplus\text{DES}_{K_2}(\delta)$ when $p=K_1$, but few if any other values. We can compute the second quantity as a function of a candidate $K_2$, and search which $p=K_1$ matches in the plaintext/ciphertext pairs (there's in the order of one), then check if that guess is right.

The DES complementation property states that $\operatorname{DES}_{\overline K}(\overline p)=\overline{\operatorname{DES}_K(p)}$. This suggests using preferentially $\delta=\overline0$, which helps since $\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)=\operatorname{DES}_\overline{K_2}(0)\oplus\operatorname{DES}_\overline{K_2}(\overline 0)$.

The attack will thus go:

Compute¹ all $\Delta(p)=\operatorname{DESX}(p)\oplus\text{DESX}(\overline p)$ for $p$ having its high-order bit clear, and keep track of them in a data structure allowing efficient search of which $p$ yields a given $\Delta(p)$. There's on average $1$ such 64-bit $p$ for each 64-bit $\Delta$, and always an even number since $\Delta(p)=\Delta(\overline p)$.
For $K_2$ with the high-order bit clear and the other $55$ significant bits varying sequentially:

Compute² $\Delta=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(\overline 0)$.
If a $p$ matches $\Delta$ (which has probability $\approx1-e^{-1/2}\approx39\%$ ):

Compute² $\Delta_1=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(1)$.
For each candidate $p$ with $\Delta(p)=\Delta$ (our data structure lists those with the high-order bit clear, and we complement to get them all):

Test¹ if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus1)=\Delta_1$. When that holds (which is extremely rare):

Test¹,² if $\operatorname{DESX}(p)\oplus\text{DESX}(p\oplus2)=\operatorname{DES}_{K_2}(0)\oplus\operatorname{DES}_{K_2}(2)$. When that holds, we almost certainly have³ the right $K_2$ and $K_1=p$. The matching $K_3$ is $\operatorname{DESX}(p)\oplus\operatorname{DES}_{K_2}(0)$.

Expected computational cost is $\approx(3-e^{-1/2})\,2^{54}\approx0.6\times2^{56}$ DES operations, ignoring memory and memory accesses (which in practice would likely dominate). The DES complementation property has halved the work by allowing to restrict to $K_2$ with high-order bit clear.

¹ Using our $(p,c)$ pairs.

² Using a DES engine.

³ Within polarity, which we can't find, because the DES complementation property implies that DESX key $(\overline{K_1},\overline{K_2},\overline{K_3})$ is equivalent to $(K_1,K_2,K_3)$.


I believe the answer can be found in section 5.2.4, "Computing Signatures".  According to that section, what you actually need to hash is the concatenation of:

the key packet (with an old-style packet header with a two-byte length — but your sample key packet has that header type already),
for the first (certification) signature, the constant byte 0xB4, a four-byte number giving the length of the user ID packet body, and the user ID packet body itself,
for the second (subkey binding) signature, the subkey packet (using the same type of header as for the key packet above),
a "trailer" consisting of the beginning of the signature packet body, from the version number field to the end of the hashed subpacket data, and
a final six-byte trailer consisting of the bytes 0x04 and 0xFF, and a four-byte big-endian number giving the length of the "trailer" string from the previous string.

I haven't checked if that will actually produce the correct hashes for your packet, but I believe it should.

Note that I've simplified the description somewhat; you should actually read section 5.2.4 of the RFC carefully to figure out just what goes into the hash under various circumstances, since it appears to depend on many things.

EDIT: While simplifying, I accidentally left out some pretty major parts. :(  I've added them in now, hopefully this time I've got everything that's needed.  Alas, I can't really check it now either, and probably won't have much chance of participating here during this week.

(Oh, and yes, I agree, that all looks like an awful mess.  I assume there are reasons for all the quirks, and that it probably looks easier to read in source code form, but that doesn't make it any less messy.)

Ps. As for "hash context", other places where the term is used, particularly section 3.7.1.1, suggest that it basically means an object or data structure that contains the internal state of the hash function and supports methods for providing further input and for finalizing the hash and returning the output. (Most cryptographic hash implementations provide such an API.)

In particular, in various parts of the RFC, it is recommended that several hashes be computed in parallel by maintaining multiple hash contexts (i.e. hash object instances).


For CFB, if the IV is corrupted, can the system re-synchronise?

Depends on the type of corruption (mangled vs. lost data) and what the segment size is.

If you use a segment size equal to the block size, which is most efficient from a computational point of view, you can recover from corruption that changes data. However, you cannot recover from dropped bytes unless you happen to fall on the same block boundary – i.e. the dropped data is a multiple of the block size.

Recovery is based on the fact that to decrypt a block of data you only need that block's ciphertext and the previous block's. This is similar to CBC. The "advantage" (see below) CFB has is that you can use a segment size of a single byte and recover from any number of dropped bytes. In that case to decrypt a byte you only need the ciphertext of a sliding window up to that byte and its alignment does not matter. You could even do that with bits if you wanted to.

However, in practice such error recovery is not very useful. Indeed, we usually want to use authentication and discard any message that has changed in transit. Otherwise an attacker could be able to change the message, even if only in random ways.


Does omitting the first two lines of RC4's pseudo-random generation algorithm weaken the cipher?

Yes, that omission weakens the cipher: the output  $\mathtt K$ has a short cycle (at most 65280 bytes) for a sizable class of keys (one in 65536). The following details why.

Because earlier code leaves $\mathtt i=256$ and the first execution of i := (i + 1) mod 256 makes that equivalent to $\mathtt i=0$, not initializing $\mathtt i$ makes no difference in subsequent code; and hence has no security implication whatsoever.

But earlier code leaves $\mathtt j$ to a key-dependent value, thus the lack of initialization of $\mathtt j$ has an effect. In particular, if at the end of key scheduling $\mathtt j=1$ and $\mathtt S[1]=1$, then (by induction) during the whole of the stream generation we have $\mathtt j=(\mathtt i+1)\bmod 256$ and $\mathtt S[\mathtt j]=1$; thus the output generated has a short cycle of (at most) $256\cdot 255$ bytes.
This never occurs in real RC4 (as observed in 1994 by Hal Finney, in An RC4 cycle that can't happen, summarized on the RC4 page), but occurs for $2^{-16}$ of the keys in the modified cipher.


How to apply IV and tag to protect messages encrypted using AES-GCM?

1.The IV should be unique for each 128 bit text or for each massage?

Per message.  Using an IV of 0 for the first message, 1 for the second, etc is just fine (no matter how long each message is), and is actually fairly common.

  2.Is adding the IV in auth data makes it less secure?

No, it doesn't.  It also doesn't make it any more secure; however if it makes you feel better, feel free.

  3.Is sending the computed tag by pepending/appending to the ciphertext, creates any vulnerability?

No, it doesn't create any problems; as long as the decryptor can unambigiously derive the computed tag, IV and raw ciphertext, any method of transport is fine.  In fact:

  4.What is the standard way to share the IV & computed Tag?

The most common way is the prepend the IV, and append the computed tag to the ciphertext, and send that as a unit; as above, we don't mind revealing the IV and the tag to an evesdropper; and we'll detect any modification to the IV and the computed tag by an active attacker (except for the possibility that he rolls back the entire message to a previously sent one; GCM can't detect that).

The most common variation I've seen to that is not to send the entire IV, but only a portion (64 bits), and have the other 32 bits shared between the sender and the receiver; this reduces the bandwidth used a tad, and we still can send $2^{64}$ messages per key, which is plenty.  Of course, this is an implementation trade-off, with no security implications; you don't need to follow this example.

Also, unrelated to your question, but the Arduino API is not very well thought out.  For one, in the decryption phase, the application is supposed to ask for a decryption, and then separately ask for the tag validation.  That means that it's up to the application to maintain cryptographic safety; if the application forgets to ask for the validation, then everyone looks like it's working, but you're not actually secure.  This is the sort of 'rake-in-the-grass' behavior that we like to stay away from; if they got this wrong, one can only wonder what other things the crypto library authors messed up on...


Why is encryption slower than decryption in elliptic curve cryptography (ECC)?

It appears that the public-key anonymous encryption scheme in question is ECIES.  ECIES encryption requires generating a single-use key pair and doing a DH key agreement with it, while ECIES decryption only requires doing a DH key agreement and so should cost considerably less than encryption.

Specifically, the sender knows the recipient's public key, $A$, a point on an elliptic curve.  The sender picks an ephemeral secret scalar $t$ and computes $T := [t]G$, where $G$ is the standard base point on the curve; then the sender computes $k := H([t]A)$ and uses $k$ as the key for a symmetric authenticated cipher.  Finally, the sender sends $T$ alongside the authenticated ciphertext.  This operation requires computing two scalar multiplications: $[t]G$ and $[t]A$.

The recipient knows the secret scalar $a$ such that $A = [a]G$, and can recover $$H([a]T) = H([a][t]G) = H([a\cdot t]G) = H([t\cdot a]G) = H([t][a]G) = H([t]A) = k,$$ with which they can then decrypt the authenticated ciphertext.  This operation requires computing only one scalar multiplication: $[a]T$.

So it is to be expected that the encryption operation would cost more than the decryption operation.  In a naive implementation—and I would not be surprised if libgcrypt, as the software you cited uses, is naive—encryption will cost approximately twice as much as decryption.  It could be made faster in a less naive implementation by using a precomputed table for the fixed-base $t \mapsto [t]G$ computation, but encryption will still be slower than decryption.

The signature scheme in this library is probably ECDSA.  Making a signature with ECDSA costs one fixed-base scalar multiplication, while verifying a signature costs one double-base scalar multiplication, so verification should cost a little less than twice what signing costs.

Specifically, the verification equation for a signature $(r, s)$ on a message $m$ under a public key $A$ is $$r \equiv x\bigl([H(m) \cdot s^{-1}] G + [r \cdot s^{-1}] A\bigr) \pmod n,$$ which requires computing $s^{-1}$, the scalars $H(m) \cdot s^{-1}$ and $r \cdot s^{-1}$, and the double-base scalar multiplication $[\alpha] G + [\beta] A$ where $G$ is the standard base point of order $n$.

The signer, who knows the secret $a$ such that $A = [a]G$, picks a scalar $k$ uniformly at random, computes $r = x([k]G)$, and then solves $k \equiv H(m) \cdot s^{-1} + r \cdot s^{-1}$ for $s$ with one inversion and two multiplications modulo $n$.

That said, ECDSA is about the stupidest elliptic curve signature scheme around—it was designed as it was in order to deliberately avoid patents that have long since expired on more sensible schemes.  You should use Ed25519 instead.


Can you break an RSA modulus if you know $k \cdot \phi(n)$ where $k$ is a large prime?

Yes we can factor an RSA modulus $n$ given $n$ and $k \cdot \phi(n)$, including where $k$ is a (reasonably) large prime. We just use $f\gets k \cdot \phi(n)$ instead of $f\gets e\,d-1$ in the algorithm of this answer.
The algorithm is heuristic, and I do not claim a rigorous proof of the distribution of the runtime. Also, a larger $k$ tends to make it more costly. But in practice it works fine for $k$ of size comparable to $n$.


There should be no limits to the exponent size if you're using power_mod.
"Too big" errors in a multiple-precision-capable library likely mean that you're trying to exponentiate-then-modulo; this creates huge numbers. If you use power_mod (cf. Python's pow), it keeps the number pruned within $\{0,\dots,n-1\}$ through the process so it never has to handle "exponentially large" numbers.


Is the Blum Blum Shub PRNG suitable to create initialization vectors?

The choice or PRNG doesn't really matter much, as long as it's a decent one. I wouldn't use BBS because it's slow, and the security proof isn't too useful.

The interesting question is rather, how to seed the PRNG with sufficient entropy. You need a sufficient amount of data that an attacker can't predict. I strongly recommend not doing this yourself, but to leave the job to the OS. Any major platform or OS offers a built secure PRNG which is supposed to be well seeded(/dev/urandom on linux, CryptGenRandom on windows, RNGCryptoServiceProvider on .net, etc.) . There are some issues on embedded systems and virtual machines, but for normal desktop computers the built in mechanism should be sufficient.


From the manufacturer's website:

  Quantis uses Quantum Physics to create truly random numbers

  Existing randomness sources can be grouped in two classes: software
  solutions, which can only generate pseudo-random bit streams, and
  physical (hardware) sources. Software solutions are not capable of
  providing true randomness as they are based on deterministic computer
  programs. Instead, they rely on external entropy sources to build up
  randomness, but these are slow and inefficient, and the quality of the
  randomness may be difficult to verify.  In the latter – hardware RNGs
  – most random number generators still rely on classical physics to
  produce what looks like a random stream of bits. However, in reality,
  determinism is hidden behind complexity for such RNGs without real
  quantum random properties.

They claim that hardware random number generators which do not use quantum properties are actually deterministic but this determinism is hidden.
This is complete nonsense.

There is no evidence that this is true and no theoretical model supporting it.

Even if the universe was completely deterministic as long as the process generating the output is hidden (as they claim) the output will still appear random for all intents and purposes. Randomness is not necessarily a fact about the universe but about the lack of knowledge of an adversary.

Saying that the universe is completely deterministic but that their quantum random number generator works would require the universe to receive no feedback from quantum effects. If this was true we could also not measure them.


In layman's terms, how does Shor's algorithm work?

The question to answer is "Is N the product of P*Q?" I believe that the easiest way to understand Shor is to imagine two sine waves, one length P and one length Q. Assuming that P and Q are co-prime, then the question above can also be answered "At what point does the harmony of P overlapped with Q repeat itself?" And the answer can be determined quickly, based upon the simple observation that we can figure out the phase of each wave at any given point on the number line. (The phase, remember, is "how far along the pattern is this point?" and is often measured in degrees; 90 degrees = 1/4 rotation)

If we look at the point N then the phase of P and Q must be 0 if they are factors of N (or else there would be a remainder of the division N/Q or N/P). Shor just tests whether the phase of P == the phase of Q == 0 at point N. It turns out that phase estimation is pretty easy for quantum computers, so it's a good tool to build into a factoring machine. See http://www.wikipedia.org/wiki/Quantum_phase_estimation_algorithm for more information.


Implementing secret reconstruction in Shamir's Secret Sharing

Suppose $s_0, s_1, s_2, \ldots, s_{k-1}$ are
elements from the finite field you are working in, where $s_0$ is the secret
to be shared, and the $s_i, i > 0$ are randomly chosen nonzero elements of
the field. Then, the polynomial used to construct the shares is
$$S(x) = s_0 + s_1x + s_2x^2+ \cdots + s_{k-1}x^{k-1}$$ and the shares
themselves are $y_i = S(x_i), 1 \leq i \leq n$ where the $x_i$ are
$n$ distinct nonzero elements of the field. Note that $n$ must be at least as
large as $k$, and that the polynomial $S(z)$ can be recovered
from any $k$ of these $n$ shares. This is commonly done using
Lagrange interpolation as has been already pointed out in the other
answers.  Assuming without loss of generality that $y_1, y_2, \ldots, y_k$
are the shares available for reconstruction, $S(x)$ is a weighted
sum (or linear combination) of $k$ different
polynomials $g_i(x)$.  We have
$$\begin{align}
S(x) &= \sum_{i=1}^k y_i \cdot g_i(x)\\
&=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{x-x_j}{x_i-x_j}\\
&= y_1 \frac{(x-x_2)(x-x_3)\cdots(x-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)}
+ y_2 \frac{(x-x_1)(x-x_3)\cdots(x-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\
&\qquad
+y_3 \frac{(x-x_1)(x-x_2)(x-x_4)\cdots(x-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)}
+\cdots\\
&\qquad
+y_k \frac{(x-x_1)(x-x_2)\cdots(x-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})}
\end{align}$$
Notice that each $y_i$ is being multiplied by the polynomial
$$g_i(x) = \frac{1}{c_i}(x-x_1)(x-x_2)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_k)$$
which has as factors all terms of the form $(x-x_j)$ except $(x-x_i)$, and
the constant $c_i$ is given by
$$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k).
\tag{1}$$
In other words, $g_i(x_i)=1$ and $g_i(x_j)=0$ for all $j \neq i$.

So there is a lot of calculation required, and care must be exercised
when writing the computer program that carries out these calculations.
But note that we really don't need to compute the entire polynomial
$S(z)$  since all we want to find is the secret $s_0 = S(0)$. This
saves us a fair amount of work because we have
$$\begin{align}
S(0) &= \sum_{i=1}^k y_i \cdot g_i(0)\\
&=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{-x_j}{x_i-x_j}\\
&= y_1 \frac{(-x_2)(-x_3)\cdots(-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)}
+ y_2 \frac{(-x_1)(-x_3)\cdots(-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\
&\qquad
+y_3 \frac{(-x_1)(x-x_2)(-x_4)\cdots(-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)}
+\cdots\\
&\qquad
+y_k \frac{(-x_1)(-x_2)\cdots(-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})}\\
&=  \sum_{i=1}^k y_i \cdot (-1)^k\frac{x_1x_2x_3\cdots x_k}{x_i\cdot c_i}\\
s_0 &= (-1)^k (x_1x_2x_3\cdots x_k) \sum_{i=1}^k \frac{y_i}{x_i\cdot c_i}
\end{align}$$
So now the task seems a little easier. We need to
compute $x_1x_2x_3\cdots x_k$ only once using $k-1$ multiplications,
each $c_i$ has to be calculated separately and needs $k-1$ subtractions
and $k-2$ multiplications. We multiply $c_i$ by $x_i$ and then
do the division $y_i/(x_i\cdot c_i)$.  The hard part in all this is thus writing
the code for computing each $c_i$.  And of course we must remember that
all this is using finite-field arithmetic so that we must use operations
or subroutine calls as described in the answer by Ilmari Karonen.


A fair peer-based coin-flipping protocol?

Yes, your basic idea is feasible.  What you are describing is a distributed coin flip protocol based on a commitment scheme.

However, you protocol as described is vulnerable to replay attacks: after one peer receives the other's hash, they can send back the same hash, wait for the other peer to reveal their random bit and salt, and send back those as well.  That way, they can force the outcome of the XOR operation to always be 0.

There are a number of ways to modify this protocol so that this attack won't work:

include a unique peer ID in the hash input,
abort (or restart) the protocol if two peers produce the same hash value, or
require the peer who revealed their hash last to be the first one to reveal their inputs.

Any one of these modifications would be enough to prevent this attack.

Edit: I thought this seemed familiar.  Here's my earlier answer to essentially the same question.


Is it safe to AES-CBC and AES-CMAC both using the same key?

The answer is simple.
The recommandations of all experts in this case is to dissociate Keys used for Encryption from Keys used for MAC-ing.
Then you have to use two different Keys.


Is it true for Java that the transformation mode and padding is ignored when using RSA?

ECB, CBC and such cipher modes are something that relate to symmetric cryptography.
In context of RSA, it is important to study from documentation of the product what they mean as they do not ordinarily apply.

Based on the articles you provide, this statement is correct:

  The mode, ECB in this case, is ignored for RSA.Use PKCSPadding. The max amount of data you can encrypt is the size of the modulus in bytes minus 11.

PKCS#1 standard defines many padding schemes. The more elaborate and less ambiguous name for this scheme and padding is RSAES-PKCS1-v1_5. You just need to ensure that the data you intent to encrypt is at most 245 bytes.

It is common to warn against using textbook RSA. This warning practically means "do not use RSA without using a padding scheme". Thus, RSA with any padding from PKCS#1 is not textbook RSA.

Secure?

In most protocols, what is encrypted with RSA with PKCS#1 padding is a secret key.    Encrypting username and password is significantly less common occurrence. Using RSAES-PKCS1-v1_5 securely needs some care in the application. Long story short, it is possible that this padding scheme would not meet the needs of this use. However, as I don't know the context and other algorithms applied, I cannot know if this is secure or not in this context.

The intent of RSA encryption is to ensure that decryption is only performed by party that has access to the private key. RSA encryption does not authenticate the sender, anybody may send a message which appears correct as far as RSA and the padding scheme is concerned.

If sender authentication is needed (quite common), it is necessary to use a digital signature scheme, such as RSASSA-PKCS1-v1_5 in conjuction with the encryption algorithm.

There is a newer padding scheme (Optimal Asymmetric Encryption Padding), which addresses some of the outcomings of RSAES-PKCS1-v1_5. However, as a general advice, I would recommend trying to find a security protocol, which'll implement the entire security use case you have. Implementing any practical security protocol from small blocks like this RSA/ECB/PKCS1Padding is tedious and unfortunately error prone.


"Impossible" might be appropriate.  And "Not really a cryptography issue." Summing up Artjom's and Geoffroy's comments, nothing can stop you pointing a camera at the screen. Or perhaps taking a screen grab. There is the notion of an Analogue Hole, which means that ultimately if you can see it, you can record it.

But that's not really necessary.  Virtually all mainstream content transmission protocols have been cracked directly via interception software or accessing a master key.  You can easily record directly from the BBC, PornHub and YouTube as simple examples.  These services have huge incentive to prevent unauthorised copying and can't, so it's unlikely a school can succeed where major global players can't. This all becomes much easier on Linux powered devices where you have total control over the kernel. Linux also comes by default with the ability to record anything playing on the sound card, so audio protection is non existent on that platform. And text can be spoken by   a screen reader, which can then be recorded via the sound card feature above. Then speech recognition $ \rightarrow $ text and so on and on.

Clearly you can release encrypted content, then either repost the plain text or the key to allow users to decrypt.  But then you've lost all control of the data.  It's out.  Re-encrypting will just create a copy of the files you already had before decryption.  The decrypted content may have been copied off machine.  USB stick perhaps.  The whole of the political European Union wants content to be able to be deleted for ever, but they haven't achieved it yet.  Perhaps  General Data Protection Regulation might work, but I doubt it.  And a server restore can bring it all back, and this has   happened as you   hear it in the news occasionally.

Another comment provides us with a fine example of irony - Google's attempt at self destructing emails.  I'm assuming that this is exactly the kind of copy protection that you're looking for. The irony is found in the mere existence of the following screen grab of   such a test email featuring a clear expiry date. Assume it expired yesterday:-

So what? Not only has it been screen grabbed and made immutable, I've just reposted it here. So the irony is further exacerbated in that whilst the email might disappear off the Gmail system in a puff of smoke, Googlebot has already indexed this answer and made it available on the Google search engine!  And as the email text is a nice clear modern machine font, OCR techniques allow for it to be extracted automatically from image format to text. This is a perfect measure of the size of the Analogue Hole and how even a billion dollar company cannot fill it in.

There's my answer here to "Can a device prove the identity of its own code?"   which really asks if a voting machine can be hacked, even with specialist hardware protection.  You're asking almost the same question, regarding a computer displaying some content. Yes it can be.


Any speed up methods for finding the index of a random value produced by the Inversive congruential generator?

(too long for a comment)

You can calculate $x_n$ directly by your formulas, if you know, how to calculate in a quadratic extension field of a prime field $\mathbb{F}_p$.

Here is the code in python:

# global parameters
p = 65537
t = (p+1)/2
r = 313
s = 997

# from https://stackoverflow.com/a/9758173/99978
# modular inverse based on extended Euclidean algorithm
def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)
def modinv(a, m):
  g, x, y = egcd(a, m)
  if g != 1:
    raise Exception('modular inverse does not exist')
  else:
    return x % m
# for generating sequence x_n
def succ(x):
  return (r*modinv(x, p)+s) % p

# check that 4*r+s^2 does not have any root mod p
for i in range(t):
  if (i*i) % p == (4*r+s*s) % p:
    raise Exception('not irreducible')

# conjugate in field
def conj(x):
  a, b = x
  return [a, -b]
# subtraction in field
def minus(x, y):
  a, b = x
  c, d = y
  return [(a-c)%p, (b-d)%p]
# multiplication of a+bX with c+dX in field F_p/[X^2+4*r+s^2]
def mult(x, y):
  a, b = x
  c, d = y
  return [(a*c+b*d*(4*r+s*s)) % p, (a*d+b*c) % p]
# exponentiation in field
def exp(x, n):
  y = [1, 0]
  while n > 0:
    if n % 2 == 1:
      y = mult(y, x)
    x = mult(x, x)
    n = n/2
  return y
# inverse in field (same as exp(x, p*p-2))
def inv(x):
  a, b = mult(x, conj(x))
  if b != 0:
    raise Exception('error in inverse')
  return mult([modinv(a, p), 0], conj(x))
# your formula for q_n
def qn(n):
  x, y = mult(mult(minus(exp([s, 1], n), exp([s, -1], n)), exp([t, 0], n)), inv([0, 1]))
  return x
# your formula for x_n given q_n
def xn(x0, n):
  return ((qn(n+1)*x0+r*qn(n))*modinv(qn(n)*x0+r*qn(n-1), p)) % p

# a short test
x = 97
for i in range(500):
  x = succ(x)
  if xn(97, i+1) != x:
    raise Exception('wrong result')

Extending a prime field $\mathbb{F}_p$ ("prime fields" are the minimal fields, the finite ones are the fields of order $p$, the infinite one is $\mathbb{Q}$) by the square root of an element $z\in\mathbb{F}_p$ that does not have a root $\bmod p$ works the same way as extending the real numbers $\mathbb{R}$ to the complex numbers $\mathbb{C}$: Just invent an element $X$ whose square is $z$ (for $\mathbb{C}$ this is usually called $i$), and calculate with numbers of shape $a+bX$ using $X^2 = z$.

Formally correct this can be done by calculation in the polynomial ring $\mathbb{F_p}[X]$ modulo the polynomial $X^2-z$ or in code like you see it above.

You can slightly optimize the code by using the fact that conjugation (replacing $X$  by $-X$) is commutes with addition/multiplication/exponentiation in the field, but I doubt that you will be able to invert the function $n\mapsto x_n$.


What makes a hash like SHA1 resistant to collisions?

Collisions will always happen because of the infinite sized input space and finite sized output space (the pigeonhole principle). So the goal is that collisions can not be found in any less time then simply trying random inputs until a collision is found - it's not possible to have a compressing hash function where collisions do not exist, they must exist and so we have to settle for making them hard to find instead.

  What makes a hash algorithm resistant to collisions?

The first thing is actually the padding of the message. If this is not done, collisions are usually trivial to produce.

The output of the function for any input should be unpredictable. Any degree of predictability in the output can be used to search for collisions faster then brute force.

In the worst case, the hash is completely linear and collisions can be computed from a simple expression.

In the best case, the value of any particular bit in the hash output cannot be guessed with probability better then 50%.

The exact, specific, best way to produce a hash function that produces unpredictable outputs doesn't really have an exact answer. There are a variety of ways to attempt to predict the output of the function, such as linear and differential cryptanalysis for example. Hash functions are designed with these kinds of attacks in mind.

Ideally the authors of the function would determine what the best possible attack is, then simply configure the function parameters to be large enough to where the attack does not apply anymore. While it is hard to know what the best possible attack is, with the right design strategy you can ensure a high level of resistance against the known classes of attacks.

  What is the best way to find a hash collision

This depends on the particular hash function in question.

If it is a non-cryptographic hash, there may exist a simple expression that will allow you to calculate collisions outright with no search effort required.
If it is SHA1 you are curious about, then you would want to read about the recent attacks on SHA1
If it is some other hash function, then you would need to locate some pre-existing research that analyzes it (or perform such analysis yourself if it is a construction of your own).

  If we find 1 collision because it has to be caused by a particular input, cant we just discount that SHA result as a possible candidate for a problematic hash and assume most other results will be fine?

It's not really clear what you are asking: It sounds like you are testing some other hash function and wondering if, despite finding a collision, it's safe to "assume" it's not broken somehow and other collisions can't be found.

If that is the case, then no, it is not safe (or reasonable) to make that assumption. If the hash is padded correctly and has an sufficiently large output size, then you should never witness a collision for it. If you do, then other collisions will probably follow eventually (attacks get better, not worse).


Are "deterrent" algorithms like NFS and Coppersmith's algorithm actually used in practice?

Technically, yes.

The number field sieve was used to break a 768-bit RSA challenge.

What is probably the current best effort (unclear whether it's still ongoing) to break a 130-bit elliptic curve challenge uses Pollard's rho algorithm.

Wikipedia lists many more references.

I say ‘technically’, of course, because these aren't ‘attacks’ on real systems; they are attacks on challenges to demonstrate the cost of the attack by academics who get to win grant funding in exchange for performing it, which we hope is a good proxy for the cost to real attackers.  It is exceedingly unlikely that these academics would intentionally attack real systems, too, because the ethical issues are more obvious than the back door in Dual_EC_DRBG, and nobody else who might carry them out is motivated to disclose their cryptanalytic capabilities.

I would guess that well-funded intelligence agencies such as the NSA devote some resources to NFS, Pollard's rho, etc., for stupidly small parameter choices made by people who don't know any better, or by people who should have known better but were under the influence of the selfsame state intelligence agencies, or in historical systems—such as major internet protocols that were designed when US crypto export controls were in effect.

But mostly they probably spend effort on working around the crypto rather than breaking it, since on a scale from one to ten of sturdiness, modern cryptography rates somewhere around a nine and most modern so-called software ‘engineering’ rates somewhere negative.


How is the SHA-1 collision detector so fast?

One trick used by the collision detector you mention is to check for "unavoidable conditions", described in the paper here: http://oai.cwi.nl/oai/asset/23932/23932A.pdf

Essentially, the unavoidable conditions are a faster check, but may have false positives. If a given block meets these conditions, the detector then runs the full check. Per the paper above, the total cost of doing this is only 1.96 times the regular SHA-1 runtime.


Why are cube and square roots of primes used as SHA constants?

This is more of a humanist rather than mathematical answer, but the design of a cryptographic primitive cannot be abstracted away from the human condition.

Knowing some research methodology, there will be a great deal of one up manship taking place.  There is a powerful motivation to produce something innovative that acts as a differentiator (marketing wise not cryptographic wise) for your particular work.  The underlying idea of the 'nothing up my sleeve' number is to form a (proven) dissociation between the value of the constant for cryptography and the source of the numbers.  E.g. It is unlikely that the sine wave can have any effect on the behaviour of a hash function**.  Similarly prime numbers are unlikely to have any deleterious effect on mixing rounds.

Clearly a string of zeros might be counter productive, but pi digits are proven as random.  Cube roots of primes are just bravado.  You could just as well use the ASCII values of the names of the planets.  That would    be at least noteworthy and hopefully more inventive than the next designer's constants.  The Million Dollar elliptic curve is probably the most blatant form of such showmanship.

**Note.  It would be interesting as to how close to the 'knuckle' this could be taken.  What if IVs or constants were somehow derived very tightly from powers of two for example?


Cryptographic algorithms compromised and alternatives?

Should you pick AES, Twofish, AES(Twofish) or Twofish(AES)?

You should pick AES.

  Also if you should choose Twofish, is it post-quantum computer
  algorithm proof?

There's no current publicly known attack that breaks Twofish any faster than Grover's algorithm (using quantum computers), so it is as secure as AES in that regard. However it is likely much more difficult to securely implement Twofish than it is to securely implement AES (due to the large secret S-Boxes) and the last meaningful cryptanalysis result against Twofish is more than one and a half decades old because research focused on AES.


If its possible to derive the public key from a private key, why can't we go in reverse?

Concerning your notation problem, yes that is kind of an issue. First, elliptic curves in cryptography are usually noted in additive notation. That's why the function call is called "multiply" and is not just a "simple multiplication" but in practice it uses the same principle as exponentiation for "normal numbers" (implemented mostly as "square and multiply", or in additive notation "double and add").

In the basic finite fields, however, people use mostly multiplicative notation to imply, that the DLOG problem is hard, because the equivalent problem based on the addition of numbers is quite easy (given numbers $a$ and $b$, everyone can calculate $a\cdot b$).

To answer your problem with the understanding: In elliptic curves, the "division" operation is not possible (well, computationally hard). This is based on the fact, that in elliptic curves we have only one group structure and we have to work with only this. Finite fields, however, offer us two group structures and they are linked by the distributive property, which in return makes the Diffie-Hellman problem easy for the additive group structure.


ChaCha with 64bit integers as a PRNG with streams

The BLAKE and BLAKE2 cryptographic hash functions use a modified version of the ChaCha quarter round in a HAIFA construction. The modified round function uses a 64-bit word size and has adjusted rotation constants (32, 25, 16, and 11 for BLAKE, and 32, 24, 16, and 63 for BLAKE2.). It's likely that all you'd need to do is use that primitive to construct a 64-bit version of the stream cipher, increasing the number of rounds as necessary to allow for sufficient diffusion. Of course, this construction could easily be fatally broken, and you should never roll your own crypto. However, it appears that this would be sufficient for a non-cryptographic PRNG if it meets all your randomness requirements.

If all you need is a non-cryptographic PRNG, you'd likely be better off using a dedicated high-speed PRNG that is capable of performing well on 64-bit architectures, assuming that is the primary reason you wish to operate on those word sizes. Various versions of XorShift should fit the bill. A large seed state can be compressed using a hash function, so there is no need to modify the algorithm.


What is the maximum number of messages that can be encrypted using the same key for CTR mode?

You should generally keep the total volume of data encrypted well below $2^{64}$ blocks per key with AES-CTR (or any use of AES)—for example, a petabyte ($2^{50}$) per key is a reasonable limit.  This is because AES is slightly defective as a pseudorandom function, which is what ‘CTR mode’ is designed for—it is really a pseudorandom permutation masquerading as a pseudorandom function, with a corresponding minor loss in security proportional to $q^2\!/2^{128}$ after $q$ messages.

AES-CTR specifically entails using $\operatorname{AES}_k(n \mathbin\| c)$ as a block of a one-time pad, where $n$ is a per-message nonce and $c$ is a block counter within the message, so that the concatenation $n \mathbin\| c$ is 128 bits long.  Just like the security of a one-time pad goes up in smoke if it's a two-time pad, the security of AES-CTR goes up in smoke if you repeat $n \mathbin\| c$.  The size of the nonce $n$ determines a hard limit on the number of messages, and the size of the counter $c$ determines a hard limit on the length of any individual messages.

Different systems use different sizes for $n$ and $c$, but a common reasonable choice, as used in, e.g., AES-GCM, is 96-bit $n$ and 32-bit $c$, which limits messages to $2^{32} - 2$ blocks, or $2^{36} - 32$ bytes, or $2^{39} - 256$ bits.  (The extra two blocks are used inside AES-GCM to choose the GHASH key for authentication.)  It is generally a bad idea to use very large messages anyway—the largest message size you accept is the largest amount of memory an adversary can waste in a denial of service attack before you can reject a forgery.

(There are also CTR variants that involve the sum $n + c$, where $n$ is chosen pseudorandomly rather than sequentially, instead of the concatenation $n \mathbin\| c$; for example, AES-GCM-SIV does this.  But the security story for that is a little more complicated and getting a bit afield from the question.)


Does simulation extractability require that the protocol have a backdoor in it?

Extractability inherently requires that the party who holds the extraction trapdoor can extract the witness. Therefore, it is important that the common reference string (CRS) is set up by a trusted party in the real protocol. However, this requirement for setting up the CRS in a trusted way is not only specific to extractability but also required by other notions such as soundness or zero-knowledge (see, e.g., [1] where the fact that the CRS is not set up by a trusted party is used to attack a protocol). Ultimately, you may observe that this trusted setup requirement is not only specific to zero-knowledge protocols, but applies to every protocol which relies on a CRS.

Regarding the UC-secure NIZK part of the question: Roughly speaking, realising a UC compatible zero-knowledge protocol requires to achieve simulation extractability. Therefore, one also has to take care that the CRS is set up by a trusted party in real instances of the protocol.

References

[1] http://stevengoldfeder.com/papers/ZKCSP.pdf


Use AES-128, the instruction set in most CPU's (AES-NI) speeds up the encryption and does not put to much load on your CPU. I would use CBC but there might be better mode operations for encrypting files. Also don't forget to use a MAC.

Using a one time pad (OTP) is nice but what you're doing is not an OTP it's more a Vigenère cipher. If you were to use OTP the key should be as long as the file which requires you to store a (approximately) 200MB key.

Thanks @CodesInChaos I missed the "I have an embedded device", but than it's not a CPU it's a MCU (most likely) even than, AES is designed to be fast on any platform so i would still give it a try, just see how much it takes i think you'll be surprised as to it's efficiency.

Take a look at the list of validated AES implementations, see if there's something which resembles your embedded device.


What is certainty in a real world zero knowledge proof?

There is obviously no definite answer to that. The general principle, however, is not at all a problem of cryptography: it is a question with a long history in probability and economics. It is referred to as Cournot's principle in this answer of Bjørn Kjos-Hanssen on cstheory.stackexchange.

As detailed by the document which I linked to, the question has long bothered people, especially when it comes to law. When can magistrates declare moral certainty? If there is a 99.99% chance that a guy is the killer, can we safely condemn him? The general consensus is what is known as Cournot's principle, which connects mathematical probabilities with the empirical "real world":

  rare events simply don't happen

Or, as put by Kolmogorov: if $P(E)$ is very small and we make a single trial, we can be practically certain that $E$ will not happen.

Of course, none of this really "answers the question". In reality, finding out which probability you will associate to certainty is essentially a matter of three things:

How many trials could a cheater have?
How strong is the incentive to cheat?
How disastrous would be the rare event?

If the attacker has a single trial, and a mistake would not be the end of the world, go for $1/{2^{20}}$ and you'll be fine. If your life depends on the outcome, or an attacker could repeat trials as often as he wants until he succeeds, you want to take a large margin, and you can go for $1/{2^{128}}$.

Note: items 1 and 3 in my list above are, in fact, closely related. Indeed, extremely rare events appear all the time: take a deck of cards, shuffle it, pick ten cards. What was the probability that you would get exactly those ten cards? It's obviously extremely low. Most things are just not so important, so the situation where an unlikely event happens is in fact very common, as there are virtually many "trials" of "unimportant events". This justifies restricting our attention, not to any event, but to "situations with potentially disastrous outcomes": there are very few such situations, hence we get less trials to get a disastrous event.

Note 2: if you want more "actual numbers" for which some famous guy randomly decided that they indicate that an event is unlikely, look at Borel's choice in page 17 of the same pdf I linked to before: he mentions $10^{-6}$ as "uncertainty on the human scale", $10^{-15}$ as "uncertainty on the terrestrial scale", and $10^{-50}$ as "uncertainty on the cosmic scale". Which is, again, an attempted answer at the following question: how many trials does a human / the earth / the universe gets at producing an event with an important outcome?


Calculate share for a specific value of $x$ in Shamir's Secret Sharing scheme

In exercise 11.8, you have written a program that recovers the shared secret, that is, given $n$ pairs $x_i, y_i$ with $y_i = P(x_i)$ where $P$ is an unknown $n-1$ degree polynomial, evaluates $P(0)$.
Now, exercise 11.8b asks you to find the share with $x=10000$, that is, $y = P(10000)$ for the unknown polynomial $P$ that you have $n$ shares with already.
Here is one approach; define $P'(x) = P(x + 10000)$, and then trick your program into evaluating $P'(0)$.  The question then is "how do you find the $n$ pairs $x'_i, y'_i$ that satisifies $y'_i = P'(x'_i)$, using the $x_i, y_i$ pairs you have?".
I hope that is a enough of a hint...


Are there any applications of Lie algebras or Lie groups in cryptography?

My knowledge of Lie algebras and groups is limited, so I hope I get at least some things right.

  Are Lie algebras or groups used in cryptography?

No. Except perhaps by some daredevils, unable to communicate with the rest of us.

  Are there any, for example, cryptographic algorithms which use Lie algebras?

No. Except perhaps some super exotic ones which nobody uses.

Let's focus on the more interesting question.

  How could Lie algebras or groups be used in a cryptographic algorithm?

I'd say the two main use cases of asymmetric crypto are key exchange and signatures. Given any group, we can build both. For key exchange we use Diffie-Hellman, and for signatures we can use for example Schnorr signatures.

A Lie group has a group structure. By the above, we can use them for key exchange and signatures. The answer to the following question is crucial: how hard is the discrete logarithm problem in a Lie group? Once that is answered, the following question is crucial: what is the size of the representation of private and public keys to obtain a 128-bit security level?
Once that is answered, the following question is crucial: are we more attractive than elliptic-curve groups or multiplicative groups of finite fields?

If the answer to the last question is no, then you probably don't want to use Lie groups. My 2-cents: they seem unlikely to be useful. For the discrete logarithm problem to be hard, we'd want our group to have as little extra structure as possible. By the definition of a Lie group, we require a lot of geometric structure which has no use for our protocols. This may make the dlog problem easier, and hence parameters larger.

For Lie algebras there is no direct use-case. When I googled this, I ended up here. So apparently someone has been able to Diffie-Hellman using some Lie algebra structure. Again, ask the questions from above. If you do worse than what's already out there, what is your use-case?

Of course, perhaps there are other ways to build protocols using the Lie algebra/group structure. It could be interesting, but it may be too little too late.


Decrypting an already sent encrypted file in PGP

When encrypting with PGP, it's common for the sender to add themselves as a recipient. When they do that, they are able to decrypt their own messages at a later time.

If the sender doesn't do that, they simply won't be able to decrypt their previously sent messages.


My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$?

Doesn't really matter - the results come out the same either way.

We know that the order of $C1$ is $q$, and so we have $x C1 = (x+q)C1$ for any $x$.  Hence, we have $b_js_j C1 = (b_js_j \bmod q) C1$

In practice, we generally want to reduce $b_js_j$ mod $q$ for performance reasons (or because our point multiplication routines might not handle multipliers significantly larger than $q$); however the math works out the same in either case.


RSA keys finding when messages are known

I confirm that "encrypt with the private key" in an asymmetric encryption scheme generally does not make sense. It seems that the only reasonable interpretation of "encrypting with the sender's private key" in your setting is that the sender actually signs the message.

Now the attack scenario you describe is not "chosen plaintext attack" but rather known plaintext attack: the attacker knows that the message is one out of n possible, known, messages. For a deterministic encryption, this would allow the attacker to find out what the message actually was, provided the list of n messages is not too big (since the encryption function is public, one can encrypt each of the n messages exhaustively and see which ciphertext matches). However, this is not possible with a standardised version of RSA such as RSAES-OAEP in PKCS #1 where the encryption is made probabilist by the use of an appropriate padding.

Using a standard implementation of RSA would not allow an attacker to recover the keys.
The ElGamal scheme is also probabilistic so the same applies.


You can solve this using mixnets.

Sample protocol:

The parties jointly choose a public/private keypair, such that the random key is shared among all $n$ parties.  (This is threshold crypto, and there are standard protocols for this.)
Each party $P_i$ encrypts his/her value $v_i$ under the public key chosen in step 1.  He/she broadcasts this ciphertext $E(v_i)$.  Now everyone knows $E(v_1),\dots,E(v_n)$.
Party $P_1$ uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts.  Party $P_1$ uses a zero-knowledge proof to prove that he/she did this step honestly (i.e., the shuffled ciphertexts decrypt to the same set of values as the original ciphertexts did).  He/she broadcasts the results and the zero-knowledge proof.  (There are standard protocols for this.)
Party $P_2$ does the same thing: he/she uses a re-encryption mixnet to shuffle and re-randomize the $n$ ciphertexts that resulted from step 3.
And so on.  Each party in turn performs their own re-encryption mix on the results from the previous party.  At the end of this, party $P_n$ has broadcast a set of ciphertexts $C_1,\dots,C_n$ that are a shuffled and re-randomized version of $E(v_1),\dots,E(v_n)$.
Now all the $n$ parties use the threshold decryption protocol to jointly decrypt the ciphertexts $C_1,\dots,C_n$ and broadcast the result.  As a result, everyone learns the values $v_1,\dots,v_n$, but in a shuffled/permuted order that cannot be linked to the originator of each value.

This should satisfy your goals.  I think it provides about as much security as one could hope for: if a party is honest, she can verify the integrity of the result of the protocol; and if $k$ parties are honest and $n-k$ parties are dishonest, then the dishonest parties learn the set of $k$ values that were contributed by the $k$ honest parties, but cannot associate which of those $k$ values came from which honest party.


Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity

I haven't read your full question, but the answer to:

Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?

and (implicitly)

Can the noise scale better than $O(d)$ for $d$-dimensional output?

Then the answer is yes.
The following should be able to be easily adapated for essentially any mechanism $\mathcal{M}$, but I'll focus on the case that the mechanism is adding independent mean-zero Gaussian noise, as this is your case.
Moreover, this argument should work provided that the sensitivity is "homogenous" in a certain sense --- in particular, any sensitivity defined with respect to a norm should work, so any $\ell_p$ sensitivity (for $p\geq 1$ I think).
Throughout this, I will write $\vec{\Delta} = (\Delta_1,\dots, \Delta_d)$ to be a vector of the per-coordinate sensitivities of $f(x)$.
I will write the $i$th coordinate of $f(x)$ as $f(x)_i$.
I will also write $\mathsf{diag}(\vec{\Delta})$ to denote the $d\times d$ diagonal matrix with $(i, i)$ entry $\Delta_i$.
The idea here is to transform $f(x)$ as follows:
$$g(x) = \mathsf{diag}(\vec{\Delta})^{-1}f(x)$$
If you compute the $\ell_2$sensitivity of $g(x)$, you get that:
\begin{align*}
\Delta_2(g) &= \max_{x, y} \lVert g(x) - g(y)\rVert\\
&= \max_{x, y}\lVert \mathsf{diag}(\vec{\Delta})^{-1} (f(x)- f(y))\rVert\\
&= \max_{x, y}\sqrt{\sum_{i\in[d]} \left(\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\
&\leq \sqrt{\sum_{i\in[d]} \left(\max_{x, y}\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\
&\leq \sqrt{\sum_{i\in[d]} \left(\frac{\Delta_i}{\Delta_i}\right)^2}\\
& = \sqrt{d}
\end{align*}
So, we have that $\Delta_2(g)\leq \sqrt{d}$.
I'm pretty sure this should extend in a straightforward way to give you that $\Delta_p(g) \leq \sqrt[p]{d}$, which would explain why you can only get the upper bound of $O(d)$ for the $\ell_1$ sensitivity.
Anyway, now we can just apply (essentially any) differentially private mechanism to $g(x)$.
In particular, the Gaussian mechanism states that:
$$h(x) = g(x) + \mathcal{N}^d(0, 2\ln(1.25/\delta)n/\epsilon^2)$$
Is $(\epsilon, \delta)$ differentially private.
For what follows, recall that differential privacy is closed under post-processing, so "we're done" on the topic of privacy.
$h(x)$ has the undesirable property that $\mathbb{E}[h(x)] = \mathbb{E}[g(x)] + 0 = \mathbb{E}[\mathsf{diag}(\vec{\Delta})^{-1}f(x)] \neq f(x)$, so we have (potentially significantly) biased the output of your function.
Fortunately, we can fix this by having our output be $\mathsf{diag}(\vec{\Delta})h(x)$ (which you can quickly check leads to an unbiased output).
In total, the mechanism which outputs:
$$f(x) + \mathcal{N}\left(0, \frac{2\ln(1.25/\delta)n}{\epsilon^2}\mathsf{diag}(\vec{\Delta})^2\right)$$
Is therefore $(\epsilon, \delta)$ differentially private.
This is what you would expect --- if you have sensitivities which are different in each coordinate, then instead of "spherical" Gaussian noise, one should use ellipsoidal Gaussian noise "matched" to each coordinate, which is precisely what the mechanism does when you write it all out.
Note that the gaussian noise is no longer the product of $d$ i.i.d. gaussians (but still has quite simple covariance structure).


$\mathbb Z_n^*$ is the subset of $\mathbb Z_n$ with elements relatively prime to $n$ (or equivalently: with an inverse under multiplication modulo $n$). That's a group under multiplication modulo $n$. It has $\varphi(n)$ elements, where $\varphi$ is the Euler totient.

It follows that $7\not\in\mathbb Z_{21}^*$; that's what's missed in the question.


Where can I find source code for ideal world simulation?

There is no source code to simulate this. It is a theoretic construct used in security proofs. Cryptography is often about the very limits of what could be calculated. This is quite far from actual programming source code.

For example, quite often something is called "efficient" in cryptography, if the algorithm runs in polynomial time (for some parameter). However, if the source code of a program actually requires $n^{1000}$ seconds then it still runs in polynomial time, but it is not possible to calculate it for $n=2$ (over $10^{293}$ years).

The adversary can not be represented by a specific algorithm, but the adversary is the union of all polynomial time algorithms (or said differently: He is limited to poly-time algorithms, but not specified which algorithms).


ElGamal scheme signature: if private key a mod p is equal to private sig. key k mod p-1, can an attacker notice and determine the value of a?

No, it doesn't provide extra information on the private key.

Note that there is no restriction on the private key value, you just have to ensure that $gcd(k, p-1) = 1$ and that $k$ is only used ONCE. Otherwise the private key can be easily found: see this link which explains how it fails for DSA (this is the same reasoning for the ElGamal scheme).


Why are the Davies-Meyer and Miyaguchi-Preneel constructions secure?

The detailed technical analysis is given in the following research paper:

Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV.   John Black, Philip Rogaway, Tom Shrimpton.  CRYPTO 2002.

They show that Davies-Meyer and Miyaguchi-Preneel are secure, assuming the block ciphers can be modelled as "ideal ciphers" (that have no regularities or patterns beyond that implicit in the very definition of a block cipher).

In a nutshell, an ideal cipher assumes that, for each key $k$, the function $E_k(\cdot)$ can be treated as a totally random permutation on the set of all $2^n$ possible texts, and these permutations for different keys $k$ are independent.

In other words, you can think of an "ideal cipher" as a black box where you send it a key $k$ and a plaintext $x$ and it responds with a ciphertext $c$.  It behaves in a very special way.  When you feed it a key $k$ and plaintext $x$, it picks a totally random ciphertext $c$ uniformly at random and gives you $c$, subject only to the following two consistency restrictions:

if you've previously queried the black box on the same key $k$ and the same plaintext $x$, then it will respond the same way it previously did, and
if you've previously queried the black box on the same key $k$ and a different plaintext $x'$ (where $x'\ne x$) and got back the response $y'$, then this time the black box won't respond with $y'$ again (it'll respond with some $y$ such that $y \ne y'$)--in short, it'll never give the same response to two different queries with the same key but different plaintexts.

That gives the flavor of the model, but it's not quite sufficient, because it only models encryption, but not decryption.  In actuality, we model this with two black boxes: one that emulates $E_k(\cdot)$, and one that emulates $E_k^{-1}(\cdot)$.  It's a bit tricky to describe how they work, but it goes like this:

If you query $E_k(x)$ and you've previously queried the $E_\cdot(\cdot)$ black box with the same key $k$ and the same input $x$, then it  will respond with the same value it previously did;
If you query $E_k^{-1}(x)$ and you've previously queried the $E_\cdot^{-1}(\cdot)$ black box with the same key $k$ and the same input $x$, then it  will respond with the same value it previously did;
If you query $E_k(x)$ and there was some prior query to the $E_\cdot^{-1}(\cdot)$ black box with key $k$ and some input $y$ and it responded with the output $x$, then this query will respond with $y$;
If you query $E_k^{-1}(x)$ and there was some prior query to the $E_\cdot(\cdot)$ black box with key $k$ and some input $x$ and it responded with the output $y$, then this query will respond with $x$;
If you query $E_k(x)$ and none of the above conditions hold, then the box will randomly pick a value $y$ that is different from the responses from all prior responses to queries of the form $E_k(x')$ (i.e., same key but different input) and that is different from all the inputs $y$ that were submitted to the $E_\cdot^{-1}(\cdot)$ box with key $k$.
If you query $E_k^{-1}(y)$ and none of the above conditions hold, then do something similar.

That's the definition of an ideal cipher.  It turns out that this is equivalent to picking $2^{n'}$ different, independent random permutations on $2^n$ texts (one permutation per key).

It is possible to use various mathematical techniques to prove that if you apply the Davies-Meyer or Miyaguchi-Preneel construction to an ideal cipher, the result will be a secure compression function.  Therefore, if our block cipher acts like an ideal cipher, then we can expect that Davies-Meyer and Miyaguchi-Preneel ought to be secure.

That's the basic idea.  You'll need to read the research literature to get the full details.


Message expansion in NTRU: why is it $\log_p(q)$-to-$1$?

I guess you are taking this information from this document.

In Section 2.1 you can see a table with different sizes. In particular, a plaintext block (that is, an encoded message) has size $(n-k) \log_2 p$ bits, while a ciphertext has size $n \log_2 q$ bits. The explanation is simple: ciphertexts are actually polynomials of $n$ terms (since degree is $n-1$), where each coefficient can be represented with $\log_2 q$ bits, while encoded messages are polynomials of $n-k$ terms (since degree is $n-k-1$),  where each coefficient can be represented with $\log_2 p$ bits.

Now, the "message expansion" (also known as "ciphertext expansion") is simply the ratio between the ciphertext size and the plaintext size. In other words, it is an indication of how much a ciphertext increases with respect to the original message. Ideally, you don't want it to expand too much for obvious reasons, although it can be shown that some expansion must exist for the encryption to be semantically secure (in the case of public-key schemes, like NTRU). In this case, it is $\frac{n \log_2 q}{(n-k) \log_2 p}$. Finally, by the properties of logarithms we have that $\frac{\log_2 q}{\log_2 p} = \log_p q$, so the final message expansion is $\frac{n}{n-k}\log_p q$.


This problem seem to be equivalent to a particular instance of the $k$-Strong Discrete Logarithm Problem.

Let $\mathbb G$ be a cyclic group of order $q$. The $k$-Strong Discrete Logarithm Problem ($k$-DLP) is, given $h, h^x, h^{x^2}, .., h^{x^k} \in \mathbb G$, to compute $x \in \mathbb Z_q $. Taking a simple change of variable ($h^x = g$), one obtains an equivalent version of the problem, which is as follows:

  Given $g^{x^{-1}\bmod q}, g, g^x, ..., g^{x^{k-1}} \in \mathbb G$, compute $x \in \mathbb Z_q $

It can be seen then that the problem in the question is the case of $k=2$.

The $k$-Strong Discrete Logarithm Problem is discussed in Correlated-Input Secure Hash Functions by Goyal, O'Neill, and Rao, for instance.


What is a safe maximum message size limit when encrypting files to disk with AES-GCM before the need to re-generate the key or NONCE

Security analysis of AES-GCM for maximum key use

Note: I am not a cryptographer. As such there are probably mistakes in my analysis. Please help me fix my mistakes and built on top of this answer so we can collectively arrive at the correct conclusion.

AES-GCM Setup

Key: 256 bit
IV 96 bit (deterministic construction)
Tag: 128 bit

Analysis

The internal implementation of GCM is using CTR mode of operation with a 32 bit integer for a counter which sets a hard limit on the number of invocations of the encryption operation to 232 blocks. The first two counter values are reserved so this gives us 232 - 2 number of invocations. This corresponds to the first limit set by the NIST standard to 239 - 256 maximum bits that can be processed with a single key/IV pair.

The IV is recommended to be 96 bits and as such I’ll use this in my analysis. In the general deterministic construction the IV is made of a 64 bit (invocation field) counter and a fixed 32 bit field. The 32 bit field is not important in our discussion. Wrapping 64 bit counter will take 264 operations which far exceeds the actual maximum of the underlying CTR mode of operation: 232 - 2. Therefore the minimum of the two is the allowed usage of the GCM mode: 232 - 2.

The final security parameter for the GCM mode is the authentication tag length. I assume a 128 bit tag length as it is the recommended by most. Theoretically, all secure hash functions have at least one weakness defined from the Birthday Paradox. It states that in order to get 50% chance of collision you need to do half the hash output length number of operations. For our 128 bit hash this gives us a security of 264 for a 50% chance of collision. This is in contradiction to our desired security of 2128, but it is what we have to deal with. Since the number of hash operations is still limited by the actual internal CTR mode of operation to 232 - 2, the authentication security is 296 - 2 which is quite high for the 128 bit tag. This is outside of the reach of any attacker at the moment.

Niels Ferguson's message-forgery attack on GCM provides further limits on the authentication tag. It is primarily targeted to the truncated version of the tag, but we’ll look at the full 128 bit tag. The attack uses about 2t (n-bit) blocks to succeed where t is the tag length. Here is the explanation of the attack from Rogaway

  The adversary asks for the MAC of a single message having 2(t / 2 + 1) blocks and then forges after about 2(t / 2) expected tries, on messages again of 2(t / 2 + 1) blocks. Focusing on the case of 32-bit tags, for example, the attack begins by asking for the MAC of a single message of 217 blocks. After that, it needs about 216 verification messages, again of 217 blocks each, until the first forgery is expected.

This is not a concern for 128 bit authentication tag, because in order to succeed you need the tag of a message of size 2(128 / 2) 128 bit blocks to begin with. This is impossible to craft as the internal CTR limit is 232 - 2, 128 bit blocks.

However, the theoretical investigation of hashes deviates from the practical realization of the underlying GHASH algorithm. It has problems that have been identified which generally reduce its security somewhat. As such we are well advised to stay away of the theoretical birthday bound of 264 operations for the same key H. But since we have an upper limit of only 232 operations from the underlying CTR construct, this raises our security parameter from 264 to  128 - 32 = 96 or 296 for the same key H.

Conclusion

After considering all of the above, it appears that the limiting security factor is the internal CTR mode of operation for AES-CTR which is processing at most 232 - 2 blocks. If we process that number of blocks we should still achieve high security margins and no further data chunking should be necessary. Therefore it is safe to utilize the full range of AES-GCM encryption and process 239 - 256 bits of plaintext data with the same key when using a 128 bit tag and a 96 bit IV.

Update

I have summarized my research on how to use AES-GCM correctly in a blog post.


In what sense addition modulo $n$ ($n>2$) isn't linear in the field $\mathbb{F}_2$?

Sicne your question is refering to an answer on this site, I will not quote the entire answer here. But the crucial point is there in the last paragraph:

  If none of that made any sense to you, that's OK. You just need to read up about Abstract Algebra, and Fields, Rings and Groups. It's a fascinating and beautiful area of mathematics, and much of cryptography will make no sense without at least some understanding of it.

I can only suggest you do the same and carefully read the answer again, because $\mathbb{F}_2$ was not mentioned in the answer at all. It contained statements about (finite) fields of Characteristic 2, which are $\mathbb{F}_{2^k}$ for any integer $k$.

If you carefully read the statements again, you will see that $\mathbb{F}_2$ actually meets both criteria, being a finite field of characteristic 2 and being a ring of the form $\mathbb{Z}_n$. In fact, XOR and modular addition are the very same group operation. It is quite obvious in this example, but could easily be checked by writing down the operator tables.

Considering your real question about linearity in finite fields, let's look at $\mathbb{F}_4$, which has characteristic 2, and is also described in the according Wiki article.
So we got $\mathbb{F}_4 = {0,1,a,1+a}$, where addition is just the normal addition of polynomials, coefficients are reduced modulo 2, and multiplicaion is the regular multiplication of polynomials modulo $X^2+X+1$.

Unfortunately, the answer in question has a few points, which only make sense under a certain point of view. Basically, if you consider a number in a binary format, and then interpret each bit as a coefficient in $\mathbb{F}_{2^k}$ (see above construction for $\mathbb{F}_4$, with 2 coefficients before $a$ and a constant $1$), then XOR-ing numbers can be interpreted as the actual addition of polynomials in that finite field. However, you can't express XOR in $\mathbb{Z}_4$ as a linear equation - which has a quite different meaning than linear function in algebra. Analog, you can't express addition modulo 4 (in  $\mathbb{Z}_4$) as linear equation in the field $\mathbb{F}_4$.

As a final note I can only say: Notation and details matter a lot in algebra. Especially if you don't understand the exact statement, this becomes even more important to avoid confusion  - or even worse, that you learn something that is just false.


SSTP MSCHAP-V2 Authentication before SSL or after SSL Session

So the question I have is on a SSTP Connection is the MSChapv2 handshake encrypted pre SSL setup or post.

Post is the answer. Specifically, SSTP is basically SSL, with special body specific to a tunnelling protocol. You can read the full spec here, but it's a little dry. Essentially, your options are these:

Authenticate through SSL/TLS certificates as you would for any SSL-certificate authenticated site, then establish the wrapped tunnel protocol, authenticating as you go.
Go through the standard key negotiation with SSL, then authenticate over your choice of P2P tunnelling protocol, e.g. with MSCHAPv2. Doing this, your tunnel is already encrypted via the HTTPS part.

From the standard:

  Because SSTP runs by means of an HTTPS connection, SSTP relies entirely on HTTPS for the reliable
  delivery of its messages. The SSTP client MUST authenticate the SSTP server by using HTTPS
  authentication. The SSTP server MAY<1> authenticate the SSTP client by using HTTPS client
  authentication. The SSTP server SHOULD authenticate the SSTP client by using PPP authentication.
  Therefore, PPP authentication is required even when the SSTP server authenticates the SSTP client
  by using HTTPS authentication. For more information about PPP authentication, see [RFC1661]

The essential difference between SSTP and PPTP is the requirement to route TCP over TCP, needed to make this an SSL connection. This has a performance impact, since TCP packets are much less efficient to send and receive than UDP packets or GRE datagrams, the latter being how you'd typically set up a PPTP tunnel.


Is there a key exchange protocol that requires only one message?

For forward secrecy without a synchronous handshake, you want something like the "ratcheting" protocol that Signal uses. It's a quite clever system, really:

Each party generates an asymmetric key pair, and gives the public key to anybody who wants it.
Each party generates and stores some number of [EC]DH parameters - one set for everybody you expect to need to talk to soon - then signs the public part of the parameters with the private key and makes the signed part publicly available too.

In Signal's case, the keys and signed public parameters are sent to the central server. Assuming you want to start a secure communication and either trust the server, have some way to verify the public key, or don't care about authentication, you can then do the following steps:

Download the recipients's key and their next, not-yet-used public key exchange parameters (the server and the recipient both track which parameters have been used).
Optionally, authenticate the key and verify the signature on the parameters.
Generate your own ephemeral set of key exchange parameters, and sign the public portion with your private key.
Use the private portion from your parameters and the public portion from the recipient's parameters to derive a symmetric key.
Optionally, encrypt a message with that key.
Send your public key, both sides' signed public key parameters, and the message all to the recipient.
Delete the ephemeral key parameters.

The recipient:

Looks up the pre-signed key exchange parameters, and verifies that the one of theirs just received had never been used before.
Optionally, verifies the sender's public key and the signature on their public key exchange parameter.
Retrieves their corresponding private portion of the key exchange parameters, and uses it plus the sender's public portion to re-derive the symmetric key.
Deletes the now-used private portion of the key exchange parameters, to ensure forward secrecy.
Decrypts the message, and/or encrypts one to send back, using the exchanged key.

For your scenario, if you can't have the central server, you'd need to retrieve the public key exchange parameter (and optionally public key to verify it) beforehand. However, you'd then be able to complete the key exchange and initiate secure communication, asynchronously, with one message... and (at least as soon as the recipient gets the message and completes the key exchange) it would be forward-secret.


Cryptographic properties of field multiplication

You're asking about the multiplication operation over $GF(2^{128})$; it turns out that, if we exclude the element 0, then the multiplication operation over that modified set of $2^{128}-1$ elements is a group operation; for example, inverses exist.
And, for any group operation $\odot$, we have:

For any element $Y$, if we multiply it by a random (and independent) element $X$, the result $X \odot Y$ is random (and revealing it does not reveal anything about $Y$).

This answers your question one (with your question being modified by having $X$ exclude the 0 element only, not the 1 element)
.  Remember, 0 is not a member of the group (even though it is a member of the field; we deliberately excluded it when defining the group); in contrast, 1 is a member of the group, and avoiding it would leak some information, in particular, the value that $Y$ is not (because $Y \ne X \odot Y$
)

If both $X$ and $Y$ are unknown, then revealing $X \odot Y$ does not reveal any information about $Y$

This answers your question two.

Revealing $X_i \odot Y$ for a large number of random $X_i$ values also does not reveal any information about $Y$.

This answers your question three.

If the above problems are hard to solve, probably finite field multiplication can be used as a method for masking countermeasure for side channel (at least theoretically).

Possibly, but it wouldn't be ideal.  For one, we had to deliberately exclude the 0 value; a real implementation that does masking can't ignore such a possible value; in particular, if you had a $Y=0$ value, masking wouldn't work in that case.  On a more practical note, masking would usually involve computing inverses, and while computing multiplicative inverses over $GF(2^{128})$ isn't that hard, it isn't exceptionally trivial either.


Are there any known inverse hash lookups for the zero string?

The 2-pass Snefru hash of the one-block message

79F6A75E 0397C368 F60C88DE 3133A55E 6D00251C 8ED3567B
CA49F82B A32E5DC4 8F86E479 DD3FF4D6 14DD88C1 A2322E00

is all zeros[1].

However, no other major hash function (and it's debatable whether 2-pass Snefru counts as major) with advertised collision and preimage resistance has ever had its preimage resistance broken[2] (archived), not even MD5[3].  If anyone found a preimage of zero under MD5, SHA-1, SHA-2, SHA-3, BLAKE2, etc., it would be quite astonishing.


RSA Key generation: How is multiplicative inverse computed?

Modular inverse can be computed with Extended Euclidian Algorithm, as other answers suggest.

I will answer your second question - why an attacker can't get private key? The problem here is that the private exponent is the modular inverse of the public one, but modulo $\phi(n)$, not $n$:

$d \equiv e^{-1} \pmod{\phi(n)}$

Attacker does not know $\phi(n) = (p-1)(q-1)$ here and there's no known way to compute it without factorizing $n=pq$.

You can notice that these numbers differ only by $p + q - 1$ but this fact itself does not help much because $p+q=O(\sqrt{n})$ and the simplest trial division algorithm for factorization works with the same complexity (it is far from feasible). Of course there are much more advanced factorization methods but they are also far from factorizing large RSA modulus.


How does reusing IV for OFB mode breaks the scheme

OFB converts a block cipher to a stream cipher (As does CTR mode). The plain text or any derivitive from it never enters the block cipher. The key stream is unrelated to what is being encrypted. The final ciphertext is just a xor of the plain text with the key stream and the key stream depends only on secret key and IV. reuse both and you get the same key stream. It is the same as reusing a one time pad. It's bad even without knowing a cipher text plain text pair. If you do, it becomes trivial to decrypt any message reusing the same key+IV.


Do I need to worry about timing attacks in Base64 encoding/decoding of private keys?

Yes, kind of. The encoding does depend on the individual bits so there could very well be timing differences. Note that the differences would be pretty small; encoding a byte is likely much faster than e.g. modular exponentiation. But as even block ciphers are vulnerable it may very well be possible, especially since table lookup may be implemented.

The solution however is also very standard: before storing the keys you first wrap the keys with a symmetric cipher. The key can be derived from a strong passphrase. Most of the time when private keys are stored in PEM format (which is just the ASCII armor) they are encoded in PKCS#12. As the encoding after the wrapping and the decoding before, you should be secure against timing attacks against base 64. Obviously the block cipher is much more likely to be protected against timing attacks (but don't forget to verify that).

In principle PKCS#8 could also describe an encrypted private key, but that doesn't seem to be used much. PKCS#12 can be used to encrypt the private key and store the certificate (chain) for the public / private key pair.

If you directly store them in PKCS#1 or PKCS#8 format (without encryption) you should make sure the system itself is secure - especially with regards to file access.


It is computationally infeasible to find $R$ (or any other short matrix that satisfies the relation) because solving $A R = V \pmod{q}$ for uniformly random $A, V$ is the SIS problem (in its inhomogeneous version).  SIS is provably as hard as solving worst-case approximation problems on lattices.

(Also, for the parameters considered in the paper, $[\bar{A} \mid -\bar{A}R]$ is very close to uniform, so finding a valid trapdoor given $A$ really is equivalent to the SIS problem.)


A quick list from Wikipedia;

ECB : doesn't use IV and don't use ECB which is insecure, see the penguin from Wikipedia.
CBC : uses IV
PCB : uses IV
CFB : uses IV
CTR : uses IV
OFB : uses IV
GCM : uses IV
CCM : uses IV
....

In short, all secure modes need an IV. To achieve semantical security the Probabilistic encryption is required.