What are the problems of IKEv1 aggressive mode (compared to IKEv1 main mode or IKEv2)?

As far as I understood the problem, the difference between IKEv1 Aggressive and Main Mode is how the hashed PSK is sent.

Of course, the PSK itself is never sent to the other side as both sides need to prove to each other that they know the PSK and if one side was sending it to the other one, of course, the other one will now know it. Instead, each side calculates a hash value out of several session related values and the PSK, and sends this hash to other side which is also able to calculate the same hash using the same session values and its own PSK. If the PSK used on both sides was the same, the hashes will match. The way how initiator and responder calculate that hash is slightly different, of course, so one side cannot simply send back the hash it received from the other side as that would also prove nothing. Yet, all values used to calculate the hash must be values that the other side will know just from the data of the current or previous exchanged packets, except for the PSK that each side must simple know.

Main Mode first performs a DH Key Exchange, resulting in secure key on both sides. After that has happened, all communication between both sides is always encrypted and thus not readable by an attacker who is only able to capture traffic between those two sides. The PSK hash is transferred after the key exchange, that means the calculated hash is already encrypted. Also some of the session values required to calculate that hash are sent in the same packet at the hash itself, so these values are also encrypted. An attacker who can just read interchanged traffic will not be able to see the hash, nor will he be able to get all the session related values required to even calculate it. He first had to break encryption or the DH Key Exchange.

Aggressive Mode on the other hand, sends the hashed PSK together with the DH Key Exchange payloads, as well as all the values required to calculate the hash in the very first responder packet and this packet cannot be encrypted because the key exchange has not yet completed. So an attacker, who can just read interchanged traffic, will get the unencrypted hash and also has access to all values that are required to calculate it, except for the PSK itself, of course. Now all that an attacker has to do is brute forcing the PSK, which can be very easy, if it is a poor PSK that is either very short, very simple or cannot stand up to a dictionary attack.

A man-in-the-middle attack is not required for this attack scenario as you are not trying to break the key exchange, you are trying to guess the PSK and you can do so "offline", as you have all the other values required for calculation and a hash that will tell you when you've found the right one. To perform the same attack on a Main Mode connection, you must perform a man-in-the-middle attack which means it's not enough to just see the traffic, you must be able to capture, manipulate and then forward the traffic to break yourself into the DH Key Exchange in realtime. Only then you will get an unencrypted version of the hash and the other values required to calculate it. While also possible, that's a lot harder than just sniffing some outgoing traffic somewhere.

Of course, it all depends on the strength PSK. If your PSK is 64 totally random alphanumeric characters, well, good look brute forcing that. Winning the same lottery ten times in a row is probably more likely than guessing that PSK and trying all possibilities will need more time than our sun is going to exist. The problem is rather that a lot of people don't even understand what a PSK is and consider 1234 secure enough.

Summary: Aggressive Mode is not really less secure than Main Mode. Both can be broken and both can be broken by the same attack. The difference is only, to get the values required for such an attack, it's enough to be able to sniff some traffic in Aggressive Mode (just sniffing two packets is enough), whereas in case of Main Mode you must perform a man-in-the-middle attack on the DH Key Exchange to even get the required values to make the attack possible. Once you have the value, it's equally hard to guess the PSK.


Differences between hashed text and encrypted text

Hash is very short, e.g. 8 bytes, 32 bytes, 64 bytes, no matter how long the original text is. Where as encrypted text is actually unlimited.

If the encrypted text is relatively long, you can calculate some statistical values. Where as hash is short and is no sufficient for any statistics. E.g. how will you speak about some frequency if you only have 32 bytes?

Hash is a one way transformation. In a normal case there is no way to restore the original text. If you had a text of 1000000 bytes and hash of 64 bytes, it is clear that  there is no way to obtain 1000000 bytes from 64 bytes.

To randomness: It is one of the goals of good encryption to make the encrypted message indistinguishable from a random sequence of bytes.


The title says authentication, that is we want only the real firmware to load and run, unmodified. There are fast, practical code signature techniques for that. Most importantly they require no secret in the target device.

The baseline would be that the target contains an RSA 2048-bit public key with $e=3$, and uses that to verify an RSASSA-PKCS1-v1_5 signature with SHA-256 of the firmware. RSASSA-PSS would be nice, at a slight expense in code complexity.

Given that the firmware won't fit in RAM, signature verification must be after writing the firmware in Flash but before running it. That check could be at each startup, if we can afford to save the 256-byte signature in Flash, and some milliseconds of startup delay.

This can be done with 2kB byte of Flash, including public key (256 bytes, can get down to <100 with special generation techniques), and within the stated RAM budget. Using Rabin signature (similar to RSA but with $e=2$) can save some time, RAM, and even code.

This is quite secure against all except attacks that modify what the hardware does (e.g. with a JTAG probe, or power supply glitch). For proper implementation, and if the whole firmware is secure (free from buffer overflows and similar), there is excellent insurance general users can't reproduce the attack on their device.

For secrecy of the code, as in the body of the question, there must be a secret in the target. Serious adversaries will manage to extract that secret, and will be able to decipher the code. My advice: use encryption, but know it's breakable.

I see no reason to use AES, unless it is required in the application AND the loader's AES code is reused by the application. ChaCha seems a better choice.

I won't comment on the proposed solution beyond stating that:

It is inconsistently described: CRC-32 is 4-byte, leaving how that "matches last 16 bytes" a mystery.
It writes the firmware by small 256-byte chunks, therefore it gives no insurance that it leaves the firmware as a whole in a consistent state in case on interrupted download. This is a tried and tested avenue to disaster.

The correct solution to issue 2 is:

Invalidate the current firmware when firmware download is initiated, leaving only the bootloader running at next reset; this insures that download can be started over in case of power loss.
Have the bootloader download the code in Flash.
When download is done, check the signature of the whole firmware just downloaded and written, and if OK re-enable the firmware to run at reset.
Optionally, the signature can be part of what's written in Flash, and the check performed again at each reset.

The bootloader can use the whole device's RAM, thus the technique works down to 1kB RAM total (rather than 8kB here).


Information theoretical security of an inefficient Shamir based access structure

Yes, your scheme is trivially correct and secure.  This follows from the fact that:

Shamir's secret sharing is correct: any group of participants with at least the threshold number of shares can reliably reconstruct the secret; and
Shamir's secret sharing is perfectly secure: no group of participants with less than the threshold number of shares can learn any information about the secret.

Since your subschemes are constructed independently except for having the same secret, the only way in which knowledge learned from one subscheme could help in breaking another subscheme is if this knowledge somehow involved the secret.  But since Shamir's secret sharing, by construction, reveals no information about the secret without access to the threshold number of shares, this is not possible.

Another way to show this is to assume that a group already has, for each subscheme, access to just one less share than the threshold number for that subscheme.  (We can do this without loss of generality, since giving an attacker access to more shares never hurts their chances of recovering the secret.)  Then show that, for any possible secret value, there exists a unique assignment of the missing shares for each subscheme that will reconstruct that secret.  (This is basically the standard proof for the security of basic Shamir's secret sharing, just with multiple sets of shares and polynomials.)

Also note that, since your subschemes are always $(n,n)$ schemes (i.e. they always require all shares to reconstruct the secret), you don't actually need the full power of Shamir's scheme.  In particular, trivial secret sharing, e.g. based on XOR or modular addition, would work just as well.


How can process algebra help to design security protocols?

More specifically, can I use it for proving the security of protocols?

Sort-of.
Using process algebras you can model or describe your protocol using a language that has a formally defined syntax and semantic (= meaning) just like you can describe a protocol using code or text. The advantage of process algebras is that the formal syntax and semantics can be used by tools to do one of the following:

Find a counter-example to a claimed property.
Prove that the protocol satisfies a claimed property (not always possible).
Reduce the proof of the complete protocol to some more easily manually achieved proofs.


Hashing user password without database to store salt

BTW, rainbow tables are more thing of the past. They were time / space tradeoffs and currently rainbow tables of most plausible sizes can be generated in seconds by serious crackers - that is, they are not useful. Salt is still recommended to hide the fact when two people have the same password - but you are not using hashing for password storage, so unless you store the generated key hash somewhere, salt is not helping (you only have the encrypted database, not a hash of the password). One would need a rainbow table for all possible passwords in some set and all possible databases (within some constraints). Storage requirements would be insane. I wouldn't be worrying for rainbow tables if I understand the setup correctly.


Is the product of two primes only factorisable by those two primes?

Yes, that is true (unless you count the trivial factors of 391, namely 1 and 391).  The fundamental theorem of arithmetic states that any postive integer is a product of a unique multiset of primes, and that no other multiset will multiply together to form that integer.

And so, since $391$'s multiset of primes is $(17, 23)$ (because both $17$ and $23$ are prime, and $17 \times 23 = 391$), that implies that no other prime can possibly divide $391$.  If there were such a prime $p$, then we'd have an alternative multiset that consisted of $p$ and a multiset that was the factorization of $391/p$; that would be a different multiset (because, by assumption, $p$ is neither $17$ nor $23$) with the same product, and we know that can't happen.


Discrete logarithm over prime modulo: small input, large exponent, larger prime

Since attacker does not know $m$, he can't directly apply discrete logarithm methods. On the other hand, small message space allows to run discrete log algorithm on each possible $m$.

There are subexponential algorithms for dlog, but I am not sure if they are directly applicable here. But the general BSGS algorithm will find $e$ in $sqrt(e)$ operations, so for each $m$ candidate we need $~2^{80}$ operations to find some possible $e$ (total $~2^96$ complexity). Notably, most of the wrong candidated for $m$ will not yield any $e$ so this can also be used to "unhash" your "hash". Though complexity is quite high, there are high chances that more effective discrete logarithm can be applied.

Another note: assuming you use odd $e$, this "hash" leaks some information about the message: Legendre symbol (e.g. if the message is quadratic residue mod p or not).

PS: It's not completely clear how you are going to use it and why your attack model assumes only knowledge of $h$, not $m$ (since even then finding $e$ is hard). But this confuses as it may seem that you want also to hide information about $m$, which is really a bad idea here.


Is it possible to convert a selective secure broadcast encryption scheme to an adaptive secure broadcast encryption scheme?

There is a generic reduction from breaking selective security of a protocol $\mathsf{P}$ to breaking its adaptive security: the adaptive reduction for $\mathsf{P}$ simply guesses (at random) the information $w$ (in your case, the recipient set) that the adversary commits to in the selective experiment. Therefore, if $w$ comes from a universe $\mathcal{W}$ (which in your case is the set of recipient sets) and if $\mathsf{P}$ is at least $\epsilon$-secure then $\mathsf{P}$ is also at least $\epsilon\cdot|\mathcal{W}|$-secure. Since the universe $\mathcal{W}$ in the case of private linear broadcast is only of polynomial size, the adaptive security of $\mathsf{P}$ follows.$^*$
I think this idea is folklore, but the earliest formal statement I found goes back to [BB] (Theorem 7.1); you can read more about it in [J+]
[BB] Boneh and Boyen, Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles, Eurocrypt 2004
[J+] Jafargholi et al.,  Be Adaptive, Avoid Overcommitting, Crypto 2017
$^*$ In most cases the universe is of exponential size and this lead to an exponential loss in security. But there are examples where this is the best we know!


Calculating RSA private exponent when given public exponent and the modulus factors using extended euclid

The extended Euclidean algorithm is essentially the Euclidean algorithm (for GCD's) ran backwards.

Your goal is to find $d$ such that $ed \equiv 1 \pmod{\varphi{(n)}}$.

Recall the EED calculates $x$ and $y$ such that $ax + by = \gcd{(a, b)}$. Now let $a = e$, $b = \varphi{(n)}$, and thus $\gcd{(e, \varphi{(n)})} = 1$ by definition (they need to be coprime for the inverse to exist). Then you have:

$$ex + \varphi{(n)} y = 1$$

Take this modulo $\varphi{(n)}$, and you get:

$$ex \equiv 1 \pmod{\varphi{(n)}}$$

And it's easy to see that in this case, $x = d$. The value of $y$ does not actually matter, since it will get eliminated modulo $\varphi{(n)}$ regardless of its value. The EED will give you that value, but you can safely discard it.

Now, we have $e = 17$ and $\varphi{(n)} = 40$. Write our main equation:

$$17x + 40y = 1$$

We need to solve this for $x$. So apply the ordinary Euclidean algorithm:

$$40 = 2 \times 17 + 6$$

$$17 = 2 \times 6 + 5$$

$$6 = 1 \times 5 + 1$$

Write that last one as:

$$6 - 1 \times 5 = 1$$

Now substitute the second equation into $5$:

$$6 - 1 \times (17 - 2 \times 6) = 1$$

Now substitute the first equation into $6$:

$$(40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1$$

Note this is a linear combination of $17$ and $40$, after simplifying you get:

$$ (-7) \times 17 + 3 \times 40 = 1$$

We conclude $d = -7$, which is in fact $33$ modulo $40$ (since $-7 + 40 = 33$).

As you can see, the basic idea is to use the successive remainders of the GCD calculation to substitute the initial integers back into the final equation (the one which equals $1$) which gives the desired linear combination.

As for your error, it seems you just made a calculation error here:

3(40 - 2(17)) - 1(17)

which incorrectly became:

3(40) - 3(17)

It seems you forgot the factor of 3 for the left 17, the correct result would be:

3(40 - 2(17)) - 1(17) = 3 * 40 - 3 * 2 * 17 - 1 * 17 = 3 * 40 + (-7) * 17

Which is the -7 expected.


A problem about Gaussian distribution in paper GPV08

The Gaussian function $\rho(x)=\exp(-\pi \| x \|^2)$ satisfies the property that if $x,y$ are orthogonal vectors, then $\rho(x+y)=\rho(x) \cdot \rho(y)$. This follows directly from the definition and the Pythagorean theorem. So, we can cancel out the contribution due to $c-c’$, which is orthogonal to every element in $\Lambda$, from both the numerator and the denominator.


Is pairing based cryptography ready for productive use?

Type-1 (symmetric pairings) are dead for curves over fields of small characteristic. Over prime fields of large prime characteristic they are not really dead, but as they only offer small embedding degrees ($k=2$), they are not really attractive from a performance point of view. You have to choose very large curves (which makes the curve arithmetic slow) such that you have a reasonable security in the multiplicative target group.

Type-3 pairings are most attractive (from the perspective of a performance and security tradeoff) as when they are used with Barreto-Naehrig (BN) curves, they have nice embedding degree of 12 (meaning that for 256 bit curve $G_1$ will give you 3072 bit in $G_T$ and this choice is ideal at the 128bit security level w.r.t. the comparable strengths proposed by NIST at the moment). Furthermore, most Type-2 protocols can be ported to the Type-3 setting by non-crucial modifications.

Type-4 are rarely used as they only are required if one requires secure hashing (in the sense that one does not know the discrete logarithm of the result to some fixed point) to $G_2$ (and that is only required rarely by protocols). As it turned out, they are also quite dangerous to use.

The different types of pairing functions $e$ (ate, optimal-ate, etc.) are basically all instantiations of the miller algorithm (aka miller loop) with different optimizations (use of distortion maps, use of Forbenius, etc. in the algorithm) and are typically restricted by the type of paring you are using.

Benn Lynn actually provides Type-3 pairings (dn - MNT curves, f - BN curves) and I have no idea why it seems that he has a preference towards Type-4 (maybe because he required them in his proposed protocols?).

I think whether they are ready for productive use is opinion-based, but AFAIK Voltage sells pairing-based crypto for years, and there are also draft standards for IEEE P1363 and I guess they will propose the use of BN curves. Also there is a draft RFC on the Optimal Ate pairing over BN curves.

Udate:
Since there has been a recent progress in the discrete logarithm problem in extensions of fields of large prime characteristic (see here for a nice overview), it is not really clear at the moment how exactly this would influence BN curve choices to adjust the BN curve parameters for a given security parameter. It is thus possible that for instance KSS curves (with an embedding degree of $k=18$) get more attractive than BN curvres. So this will not really push standardization at the moment till this is clear.


Is a signature scheme using a hash considered a hybrid cryptosystem?

What I didn't directly see is that a hybrid cryptosystem is not the same thing as hybrid cryptography. A cryptosystem is commonly targeting encryption: it exists of a key generation function $\operatorname{Gen}$, an encryption function $\operatorname{Enc}$ of course a decryption function $\operatorname{Dec}$.

So although signature generation could probably be called hybrid cryptography, it commonly isn't a hybrid cryptosystem because it lacks the $\operatorname{Enc}$ and $\operatorname{Dec}$ function.


Is it possible to derive an Ed25519-public-key from an Ed25519-signature?

From Wikipedia, an EdDSA signature is a pair $(R, s)$ of a point $R \in E(k)$ and scalar $s \in \mathbb Z$ satisfying the verification equation $$[2^c s] B = [2^c] R + [2^c H(R, A, M)] A,$$ where $E/k$ is the underlying curve over a field $k$, $B \in E(k)$ is the standard $k$-rational base point of large prime order and cofactor $2^c$, and $A \in E(k)$ is the public key.

It is tempting to say that if you had $h = H(R, A, M)$, then you could simply compute an inverse $k$ of $h$ modulo $\ell$ and compute $A = [k] ([s] B - R)$, and hope that complications with the the covfefe $2^c$ won't eat your lunch.  But, by design, the only way to compute $h$ is in fact to know $A$ a priori to feed it into $H$.  And unless you break the preimage resistance of $H(R, A, M)$, which is SHA-512 in the case of Ed25519, you won't get very far doing this.

However, that only answers the question you asked literally: Can I derive $A$ from an Ed25519 signature?  You also mentioned anonymity, which is a slightly different kettle of fish.  The question for anonymity should be the key privacy property: Given two signatures $(R, s)$ and $(R', s')$, can I tell with nonnegligible probability whether they were made by the same key pair or not?

In the case of most RSA-based signature schemes, the answer is yes (to both questions), thanks to a problem of counting German tanks well-known in the anglophone empirical inference literature—that is, most RSA-based signature schemes do not provide key-privacy.  What about Ed25519?

The answer may be a little trickier, because we don't demand recovery of the public key as the standard approach to breaking RSA-based key privacy works.  The literature does not seem to be rife with references about key privacy for signature schemes, but there is a simpler sufficient criterion for key privacy of encryption schemes which could likely be adapted to signature schemes.

I leave it as an exercise for the reader to adapt this into a sufficient criterion for key privacy of signature schemes, demonstrate that Ed25519 satisfies the criterion, and publish it all to fame and glory in the cryptology literature.


What are some of the best prime factorization algorithms and their effecitvity

Is it really that simple?

If it weren't we would have to abandon RSA.
Here's why: To be able to run RSA somewhat decently fast, it needs to run in polynomial time in some parameter, let's call it $\lambda$. RSA is basically the same as modular exponentiation and thus runs in time $\mathcal O(\lambda^3)$ when $2^\lambda\approx n$. Now the best known generic factorization method, the GNFS runs in time $L_n\left[\frac13,\sqrt[3]{\frac{64}9}\right]=\exp\left(\left(\sqrt[3]{\frac{64}9}+o(1)\right)\cdot\sqrt[3]{\ln{2^\lambda}}\cdot\sqrt[3]{\ln{\ln{2^\lambda}}}^2\right)$, which is sub-exponential in $\lambda$. So if we double the key length (that is $\lambda$), we may 8-fold our workload, but we also take the attacker's workload to the power of at least $\sqrt[3]2$, which turns an $2^{80}$ attack into an $>2^{110}$ attack, thus increasing the attack complexity by at least a billion.

Now assume we could factor in time $\mathcal O(\lambda^n)$ for some somewhat small $n$. Now if we double the key length, we (the legitimate user) take 8-times the time, but the attacker now only takes $2^n$ times the time, so if he has $2^{n-3}$ as many cores or as good cores, he could recover the new key in the same time as before. So we'd have to repeat the increase in key length a few times (assuming $n\leq 20$) so that we, the user, get an edge of the attacker, but at this point key length become so large that RSA will be too slow to be good choice, especially if you consider low-power embedded systems.


Finding product of two unknown numbers each raised to a known power

To say more about this, you need more assumptions on $(x_0, y_0),\dots, (x_2, y_2)$.
For example, if you write
$$B = \begin{pmatrix}x_0 & x_1 & x_2 \\ y_0 & y_1 & y_2\end{pmatrix}$$
to be the $2\times 3$ matrix of your known constants, and let:
$$\mathsf{span}_{\mathbb{Z}}(B) = \{(x', y')\in\mathbb{Z}^2 \mid \exists \vec{\alpha}\in\mathbb{Z}^3\text{ s.t. }(x', y') = B\vec{\alpha}\}$$
be the span of all of their integer linear combinations, then you can efficiently compute $a^{x'}b^{y'}$ for any $(x', y')\in\mathsf{span}_{\mathbb{Z}}(B)$ by writing:
\begin{align*}
\prod_{i\in[3]}c_i^{\vec{\alpha}_i} &= \prod_{i\in[3]}(a^{x_i}b^{y_i})^{\vec{\alpha}_i}\\
&=\prod_{i\in[3]}a^{\vec{\alpha}_i x_i}b^{\vec{\alpha}_i y_i}\\
&=a^{x'}b^{y'},\quad (x', y') = B\vec{\alpha}
\end{align*}
The above technically uses the assumption that $G$ is abelian (commutative), but this is likely intended.
So if $\mathsf{span}_{\mathbb{Z}}(B) = \mathbb{Z}^2$ (which is definitely possible), you can compute your desired function for any pair of $(x', y')$. But if the span of $B$ is not all of $\mathbb{Z}^2$, it is not clear how to compute your desired function for $(x', y') \in \mathbb{Z}^2\setminus\mathbb{span}_{\mathbb{Z}}(B)$ (at least the prior technique no longer works).


From RFC 4880 - Open PGP Message Format (emphasis added)

  OpenPGP implementations SHOULD compress the message after applying
     the signature but before encryption.

As the signature provides authentication, and you specifically ask about authentication, I think that quote from the RFC should answer your question. Compression does not affect authentication of the message at all as the authentication step (signing) is applied before compression. See the question archie linked for other issues with compression.


Is this ECC encryption key sharing method okay?

To start things: Don't roll your own crypto.

What you're proposing is using standard static Diffie-Hellman for key-exchange, which by itself is a bad idea, as it will always result in the same key for each communcication between Alice and Bob. The key by itself should be safe, but as soon as it's broken all messages are as well. So if either the sender's public key is broken or the derived DH key is learned all communications are broken, whereas ECIES will still be safe (if the DH secret is learned one message is broken, if the public key is broken all messages to that person are broken and not all messages).

Next, ECIES provides authenticity and secrecy, meaning that if the message is altered in transit ECIES will output an error on decryption, using plain CTR + random IV doesn't provide this property.

So it's for these reasons (don't roll your own crypto, avoid static keys, think of authentication) that ECIES is the better choice.


I'm implementing an encryption algorithm that requires me to use a random number to mix up the values. However I'm caught in between if I should use quasi-random or pseudorandom.

It may sound counterintuitive, but what works best within an encryption algorithm does in fact depend on the details of that algorithm.  It may be that, for your encryption algorithm, a uniform random distribution has a nonnegligible probability of creating a weak transform, and a tailored nonuniform ("quasirandom") distribution is better.

I assume you have spent a lot of time exhaustively cryptanalyzing your encryption algorithm; what does that analysis say?

And, by the way:

  And because it is less uniform compared to quasi-random it presents a certain bias towards a certain group of numbers.

Actually, that's not accurate; the definition of a uniform distribution (which is the name of the distribution that an unbiased random number generator generates) is that it doesn't have a bias.  For example, consider the probability that a generator proceduces two consecutive outputs $7, 7$.  If the generator was uniform, the probability of those two outputs is precisely the same as the probability of producing any other two specified outputs.  However, if the generator is quasirandom, the probability may be significantly smaller (even 0), if the quasirandom generator was biased away from repeating outputs.


Is the Couvreur et al. polynomial time attack on McEliece practical?

My understanding is that the attack only works against McEliece with algebraic geometry codes. The paper by Bernstein, Lange and Peters recommends parameters for McEliece with binary Goppa codes, so the attack does not apply against those parameters.


Mapping a value $g^x \bmod p$ to a small interval $[1...H]$

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage.

Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under the mapping $a \in \mathbb{Z}^*_p \mapsto (a \bmod H)$. So the probability of hitting your target $h$, when you choose a random $a \in \mathbb{Z}_p^*$, is $\lfloor \frac{p-1}{H} \rfloor/(p-1)$ for some $h$'s and $\lceil \frac{p-1}{H} \rceil/(p-1)$ for others. But if $p$ is exponentially large (as I suspect it is here since you're talking about discrete logs), then this probability is negligibly close to $1/H$.


Question about discrete log - why can one attacker not solve for g but two colluders can?

The idea is that someone who just knows $g^d \bmod N$ and $d$, they cannot compute $g$ (because they don't know the factorization of $N$; hence this is the RSA problem); however, if they know $g^d \bmod N$ and $d$ and $g^e \bmod N$ and $e$, then (assuming $gcd(d, e) = 1$), they can (and once they have $g$, they can compute $g^{abc} \bmod N$).

That's because, since they know $d$ and $e$, they can compute two integers $s$ and $t$ such that $sd + te = 1$ (that's where the assumption that $gcd(d, e) = 1$ comes in; if that's not true, then no such $s$, $t$ will exist).  Once that have those two integers, they can compute $(g^d)^s \times (g^e)^t = g^{sd + te} = g^1 = g$, recovering $g$.  One of $s$ and $t$ will be negative; that's not an issue, as we can compute inverses modulo a number of unknown factorization.


Shake 128/256 Output Length Restrictions

There is no standard limit on the output of SHAKE256.  No matter what output size you use, SHAKE256 advertises collision, preimage, and second-preimage resistance up to a 256-bit security level against a classical adversary, and up to a 128-bit security level against a quantum adversary, limited by the size of the output for small outputs (see Table 4 in Appendix A of the SHA-3 standard for details).

In particular, you are not limited to a 1600-bit output.  SHAKE256-$d$ does not simply reveal up to $d$ bits of the state and stop at 1600.  Rather, it reveals up to 1088 bits of the 1600-bit state, then permutes the state, and repeats until it has produced $d$ bits.  In spongy lexicon, it repeatedly squeezes up to 1088 bits at a time out of the sponge after absorbing the input.  It leaves 512 bits of the state secret at each iteration, far more than an adversary could ever hope to find even with a quantum computer.


Using a hash with a constant key to create easily verifiable codes

I will keep my answer short.

Yes it is trivial, in order to verify the code you need the parameters AND the key, thus there is no easy way to keep the key secure except through a hardware security module.

The correct way would be to use a digital signature:

Sign(SHA256(parameters),secret_key)

The signature can be verified by anyone with the public key, and the secret key is not required or exposed.


AES multiple devices to server communication

Will the presence of this "secret" (presuming it is the same in every message coming from that device, and in the same location within the message) cause repeating patterns in the ciphertext making some form of attack possible?

As long as the AES mode uses an IV and the IV is different for each message, there will be no patterns in the ciphertext.

However, there may be other attacks.

  As this is sent unencrypted, I think this is somewhat insufficient to identify the device so I placed a device specific "secret" in the bit of the message that is encrypted which, if absent or incorrect will lead to the server discarding the message.

A better way to do that would be to use authenticated encryption. Either AES in GCM mode or AES CTR + HMAC would work, for example. That will also prevent changes to messages, which may currently allow an attacker to change the device status in a message.

Even then, replay attacks may be possible. To prevent those you could verify the IV is never reused, for example by using a counter as the IV (in CTR or GCM modes) and storing the last value on both server and device, or by having the server send a random session number the device needs to include in its message.


We think that the player will not be able to get this key by extracting it from the memory or somehow else.

Forgive me, but I'm skeptical. If you really have figured out a way to do this --- and plenty of well-funded, intelligent people have tried and failed --- I'd recommend slapping a patent on it and making millions off of licensing fees.

  How safe is this implementation?

Regardless of what you end up doing, the key will probably be the weak link. Or perhaps an attacker will try to read the decrypted packets from memory instead of the key.

I'm assuming that when you say "A fast hash function with a key will be used for authentication" what you mean is that you'll be using HMAC for authentication. If you mean something else, please clarify.

Using HMAC and CTR is a sound approach. Just make sure to authenticate the ciphertext ("encrypt-then-MAC"), rather than the plaintext ("MAC-then-encrypt" or "MAC and encrypt").

The real devil is in the details, though. You've given a broad overview of your approach, not a specific algorithm/protocol, and not an implementation. Each of these two transitions has the potential to go awry. For example, will your protocol prevent replay attacks? Will your implementation generate CTR nonces securely?

  4-6 bytes (not 16) will be used for the tag.

I wouldn't use a tag this short to protect financial data, but for a game, it's probably fine.

  Which hash function is better to use?

This depends on your definition of "better". SHA-2 will probably be the most secure. SHA-1 will probably be secure enough. HMAC-MD5 hasn't been broken, but using it is generally not recommended since MD5 has been broken. On the other hand, if your definition of "better" includes performance, than using MD5 may be worth the security risk (considering the relatively low stakes of the information you're protecting).

  Can we use the same key for both the hash function and AES?

Do not do this. This may not lead directly to any obvious attacks, but key reuse in general will anger Crypto Gods because it violates a key assumption (heh) that cryptographers make when designing these algorithms. It's the crypto equivalent of not doing any bounds checking on your buffers. (And if you later switch to using something like CBC-MAC for authentication, key resuse will be come a definite problem.)

If transmitting two keys is problematic for whatever reason, you can securely derive keys from a master key by doing something like this:

encryption_key = HMAC-SHA1(master_key, "Encryption key")
authentication_key = HMAC-SHA1(master_key, "Authentication key")

A couple suggestions.

This wasn't part of your questions, but I'd recommend using a dedicated authenticated encryption scheme such as GCM (galois counter mode) instead of separate MAC and encryption algorithms (such as HMAC-SHA1 and CTR-AES). Doing so will prevent some common implementation errors while quite possibly increasing performance.
Regardless of whether you use HMAC or GCM, look into using "associated data" (sometimes called "additional authenticated data"). The idea here is that if there's data that doesn't need to be encrypted (i.e., kept secret from the players) but still needs to be authenticated (i.e., the players shouldn't be allowed to tamper with it), there's no need to eat the performance cost of encrypting it. A crypto library that offers GCM will likely take an optional argument containing a string of associated data.


(1) Am I missing something? What is the real security provided by tokens in this case?

Suppose you shop at Home Despot and IKING and they store payment information.  Suppose Home Despot is breached and evil Freedonian hackers steal all the stored payment information.  What can we do?

If Home Despot was storing your long-term credit card information, then you have to get a new credit card.  Worse, so do the eight million other people who used it.  And until you get a new credit card, you can't buy a new longcouch at IKING—but until the breach is discovered, the pirates who breached Home Despot can!
If Home Despot was merely storing a per-site pseudorandom function of your payment information, then:

only Home Despot has to get a new thing (in their case, a new security department)—you and the eight million other schmucks who shopped there can keep your credit cards
presumably the Home Despot tokens work only at Home Despot, so the pirates are unable to refurnish their living quarters with new longcouches from IKING on your shilling

  (2) Are tokens generated by PRFs? If a PRP is considered "secure" (so it cannot be distinguised from a "secure" PRF and its outputs look like random strings) can PRPs be used to create PRFs to generate tokens? For example, a cipher block with random keys used to generate tokens.

As long as you see well under $2^{b/2}$ input/output pairs for a PRP, a PRP is a good PRF.  Of course, if the key gets leaked, all bets are off.  For a keyed hash like HMAC-SHA256, which has PRF security and a little more, at least if a key gets leaked an adversary is limited to brute force search to find the input (like a credit card number) that might have gone into it to yield an output they found stored in a database.  So, while a PRP is a pretty good PRF, there are qualitative differences that might lead you to want to choose something with stronger security like HMAC-SHA256 or keyed BLAKE2 or KMAC128 instead.

  (3) Additionally, tokens that are 128 bits long and are never changed will operate correctly (in probability) up to $2^{64}$ generated tokens, after which we can expect the system to fail? (due to collisions)

It's unclear to me exactly how the tokens are used and I'm too lazy to read beyond the page you linked.  But suppose it works as follows—a scheme I just pulled out of my cloaca on the spot:

Home Despot is assigned a secret key $k$ known only to Squipe, Silicon Valley's hottest new payment processor.
When Evelyn T. Shopster enters her credit card information at Home Despot's web site using Squipe's gooey webplet, Squipe stores Evelyn's name and credit card number, and computes for Home Despot the token $t = \operatorname{HMAC-SHA256/128}_k(m)$ where $m$ is the message: The bearer of this token is authorized to charge the credit card of Evelyn T. Shopster.  (Here $\operatorname{HMAC-SHA256/128}$ is the 128-bit truncation of HMAC-SHA256.)
When Home Despot wants to charge the card, it sends the charge amount, Evelyn's name, and $t$ to Squipe.
On receipt of a charge request with token $t$ and name name, Squipe computes $\operatorname{HMAC-SHA256/128}_k(m')$ on the message $m'$ computed by The bearer of this token is authorized to charge the credit card of ${name}., and checks (in constant time!) whether the result is the same as $t$.

In this protocol, it doesn't matter if there is a collision between tokens, because one token cannot be used for another user; for any particular user you might try to abuse a token for, there's still only about a $1/2^{128}$ chance that it will work.

On the other hand, there are cases in which collisions could matter—for example, $2^{64}$ queries to an oracle for HMAC-MD5 under a secret key can lead to forgery with high probability.  (This isn't because MD5 is broken—only MD5's collision resistance is broken; the same attack applies to HMAC with any 128-bit hash.)


Prevent double-spending with decentralized digital currencies without all transactions being public?

For such a scheme to work, if I have some currency, I have to be able to give it to Abel and I have to be able to give it to Beth, but I have to be unable to give it to both Abel and Beth. This means that giving the currency to Abel has to somehow make me unable to give the currency to Beth even though I previously could do that.

There are three mechanisms by which this can be accomplished:

There can be a central authority. To give the coins to Abel, I must tell the central authority that I have done so. The central authority would then prohibit me from giving the coins to Beth. This means giving coins requires both approval from the central authority and reporting to the central authority.
There can be a distributed secure device. To give the coins to Abel, I must tell the instance of the secure device that holds the coins. The device will then prohibit me from giving the coins to Beth once it has given them to Abel. This means coins must be held in a physically-secure device. In practice, it also requires a central authority to load the devices and issue keys to them. (I need to prove a secure device was involved in the transaction, which requires the device to have a certificate, which requires some authority to issue such certificates.)
At least some aspect of all transactions can be public. Thus, if I give the coins to Abel, there will be a record Beth can easily find. Beth will know the coins are not mine to give.

Bitcoin chooses the third approach. This seems the best approach for cryptographic decentralized currencies. There is no fourth approach known.

Now, the only information about the transaction that needs to be public is enough information to prove I have the coins and prove that I didn't transfer them elsewhere. As it happens, the Bitcoin protocol leaks much more information than this (for example, the account I transferred the coins to). The protocol could have been designed to make less information public if that was desired.

The coins need be traceable back to their origin. But whether or not you can track the particular accounts they passed through is an implementation decision.

For example, a hypothetical coin could use the following mechanism: Alice wants to send some coins to Bob. She knows Bob's public key. She generates a random private key just for this transaction and encrypts it with Bob's public key. She then publishes a transaction transferring coins to the public corresponding to the random private key she generated along with the encrypted version of that same key that she encrypted with Bob's public key.

Now, Bob will see a transaction that his private key is able to claim. Nobody else will know the transaction was to Bob because neither Bob's public key nor any analog of it appear in the block chain. Bob will have no idea the coins came from Alice and nobody else will have any idea the coins went to Bob.

This method still leaves the coins fully traceable. But no traceable accounts ever appear in the block chain.

This solves two 'problems' with Bitcoin. If I publish a bitcoin address somewhere, anyone can see how many Bitcoins that account got. If someone wants to transfer me bitcoins that cannot be traced, he must obtain a one-time use account from me, which he cannot easily do if he wishes to give me the coins anonymously.

You can still generate and use one-time accounts with Bitcoin, but you cannot broadcast them or they cease to be one-time accounts. And there is no easy way for someone to anonymously request one from you.

You might think this means every account must be tested to claim every transaction, resulting in an inefficient scheme and making things like web-based mass wallets computationally impractical. However, I've discovered a truly marvelous solution to this problem, but this answer is already too long.


What do these notations mean in the definition of Perfect Secrecy, if we read those in English?

Imagine the following three scenarios. In each, you intercept an encrypted message and you know from context:

the message is a randomly chosen key in $\{0,1\}^n$ for some other cryptosystem
the message is either "It's a boy!_" or "It's a girl!", both are equally likely
the message is a vote from someone in a referendum; it's either "yes" or "no_", and the probability of it being "yes" (based on your knowledge of that person's preferences) is around 9/10.

Each of these scenarios describes a different context and prior knowledge you may have about the message (formally: a probability distribution on messages). An encryption scheme that's any good won't reveal anything more about the encrypted message than you already know in any of these scenarios. Even in the last case where you can make a pretty good guess at the message without breaking any encryption, the ciphertext shouldn't tell you anything more than you already know.

The last line of that definition translates to "what you know about $m$ after seeing $c$ is the same as what you would know about $m$ without seeing $c$" (for any kind of knowledge about $m$ that you may have).


Why is writing your own encryption discouraged?

Your question, MikeAzo's comment, and your reply practically could not be a better example of Schneier's Law in practice. Schneier stated:

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

To answer your reply

How can you break it if I send you this "QTCPIGXKUXTGG" ciphertext encrypted by a merely a simple algorithm which you have no idea about how it was encrypted?

Because even though we might not know exactly what your secret algorithm is, the first thing an attacker is going to reach for are common tools to attack substitution ciphers or polyalphabetic ciphers. Given even a few sentences of ciphertext is likely enough to fully recover every plaintext.
The fact that you don't know how to break it is irrelevant. It's trivial to create a cipher that you yourself can't break, but it's another thing entirely to create a cipher that others can't break. And the odds that you are capable of doing it when you're not aware of even the most basic attacks against ciphers hundreds of years old — not to mention modern concepts like indistinguishability under different attack models — puts you at an insurmountable disadvantage compared to ciphers designed by researchers with decades of experience in the field who are building off of modern notions of security and the discarded remains of thousands of failed ciphers that came before.
As an example, even if your cipher is somehow secure against a ciphertext-only attack (it's not), is it secure if I can trick you into encrypting a message of my choosing? What if I can trick you into decrypting a message of my choosing? What if I know part of or all of the plaintext for a particular encrypted message you've sent? What if you encrypt multiple messages with the same key? What if I can do any or all of these things hundreds or even millions of times in a row? These are all situations that are extremely common in the real world, and under which modern ciphers remain completely secure.
I'll leave you with another Schneier classic, Memo to the Amateur Cipher Designer:

A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.

So here's your first envelope: given a paragraph or two of ciphertext, your cipher will fail to language-based frequency analysis.
Let me know when you've figured out the other two attacks.
Edit: The comment about indistinguishability under different attack models is one reason why most "decipher this message crypto challenges" are completely bunk. They often simply give an attacker some ciphertext, ask them to decipher it, and declare victory when nobody produces the plaintext after some amount of time. Unfortunately that's not how crypto works in the real world; attackers have many more tricks up their sleeve in practice. They can trick computers into encrypting data of their choosing, they can trick computers into decrypting data of their choosing, and they can usually even do these things thousands, millions, or billions of times. Moxie's post shows how even the most terrible, horribly-designed, and obviously insecure ciphers can be effectively impervious when you restrict an attacker to a single ciphertext-only attack, which aren't representative of attackers' capabilities against ciphers as they're actually deployed in practice.


Is PBKDF2/RFC 2898 broken because SHA1 is broken?

That particular usage of SHA-1 uses HMAC, and then iterates that as part of PBKDF2 (which is actually defined for any PRF, not just HMAC-SHA1).

As of this date (2017-05-18) HMAC-SHA1 is unbroken in terms of collisions and other attacks, so PBKDF2-HMAC-SHA1 is still considered safe. The HMAC construction, along with the many iterations in PBKDF2, protects against the Google collision attack on SHA1.

However, new applications should move to at least SHA2-256 or SHA3-256 as a hashing primitive and not implement anything using SHA1 at all unless strictly necessary for compatibility with other systems.

In your case, you need compatibility with older systems, so go ahead, but build in code and make a transition plan to use newer hash function in the near future. Adding simple version field alongside the password hash will suffice in most cases.


Secure implementation of public key cryptography

Libsodium is written/implementable in C++, C and Python. It implements lots of crypto systems, such as public key cryptography. Here is the intro in the docs: https://libsodium.gitbook.io/doc/


First off, the maximum size of a message you can use is determined by the desired length of the padding (in my case, I am using RSA-2048 so I wanted a final padded length of 256 bytes) and the hash function you are using.

The formula is messageLength = desiredLength - 2 * hashOutputSize - 1 (in my case, I wanted to use SHA-256 so hashOutputSize would be 32 bytes).

The number of zeroes padded is desiredLength - messageLength - 2 * hashOutputSize - 1. This can be 0 sometimes. There are not always padded zeroes…!

After reading “PKCS #1: RSA Cryptography Specifications Version 2.0”, I realize that this question isn't important/doesn't make a lot of sense.
Yes. The specification only calls for 1 hash function as a parameter, not two different ones.
Bonus Question

MGF1 is what I used for generating masks (i.e. "expanding and shrinking data using hash functions").

And if anyone is reading this in the future and needs more resources to understand OAEP, I translated it to Java code (this is OAEP, not RSA-OAEP). Also, not strictly related to the forum, but if you can program this might make things easier to follow along:

public class OAEP {
    public static void main(String[] args) throws Exception {
        byte[] myMessage = "I wonder if this will work".getBytes("UTF-8");
        byte[] padded = pad(myMessage, "SHA-256 MGF1", myMessage.length + 32 + 32 + 1);
        StringBuilder sb = new StringBuilder();
        for (byte b : padded) {
            sb.append(String.format("%02X", b));
        }
        System.out.println(sb.toString());
        byte[] unpadded = unpad(padded, "SHA-256 MGF1");
        System.out.println(new String(unpadded, "UTF-8"));
    }
    public static final SecureRandom random = new SecureRandom(); // Uhh you may want to replace this though
    public static byte[] SHA256(byte[] input) throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-256");
        return digest.digest(input);
    }
    public static byte[] MGF1(byte[] seed, int seedOffset, int seedLength, int desiredLength) throws NoSuchAlgorithmException {
        int hLen = 32;
        int offset = 0;
        int i = 0;
        byte[] mask = new byte[desiredLength];
        byte[] temp = new byte[seedLength + 4];
        System.arraycopy(seed, seedOffset, temp, 4, seedLength);
        while (offset < desiredLength) {
            temp[0] = (byte) (i >>> 24);
            temp[1] = (byte) (i >>> 16);
            temp[2] = (byte) (i >>> 8);
            temp[3] = (byte) i;
            int remaining = desiredLength - offset;
            System.arraycopy(SHA256(temp), 0, mask, offset, remaining < hLen ? remaining : hLen);
            offset = offset + hLen;
            i = i + 1;
        }
        return mask;
    }
    public static byte[] unpad(byte[] message, String params) throws Exception {
        String[] tokens = params.split(" ");
        if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
            return null;
        }
        int mLen = message.length;
        int hLen = 32;
        if (mLen < (hLen << 1) + 1) {
            return null;
        }
        byte[] copy = new byte[mLen];
        System.arraycopy(message, 0, copy, 0, mLen);
        byte[] seedMask = MGF1(copy, hLen, mLen - hLen, hLen);
        for (int i = 0; i < hLen; i++) {
            copy[i] ^= seedMask[i];
        }
        byte[] paramsHash = SHA256(params.getBytes("UTF-8"));
        byte[] dataBlockMask = MGF1(copy, 0, hLen, mLen - hLen);
        int index = -1;
        for (int i = hLen; i < mLen; i++) {
            copy[i] ^= dataBlockMask[i - hLen];
            if (i < (hLen << 1)) {
                if (copy[i] != paramsHash[i - hLen]) {
                    return null;
                }
            } else if (index == -1) {
                if (copy[i] == 1) {
                    index = i + 1;
                }
            }
        }
        if (index == -1 || index == mLen) {
            return null;
        }
        byte[] unpadded = new byte[mLen - index];
        System.arraycopy(copy, index, unpadded, 0, mLen - index);
        return unpadded;
    }
    public static byte[] pad(byte[] message, String params, int length) throws Exception {
        String[] tokens = params.split(" ");
        if (tokens.length != 2 || !tokens[0].equals("SHA-256") || !tokens[1].equals("MGF1")) {
            return null;
        }
        int mLen = message.length;
        int hLen = 32;
        if (mLen > length - (hLen << 1) - 1) {
            return null;
        }
        int zeroPad = length - mLen - (hLen << 1) - 1;
        byte[] dataBlock = new byte[length - hLen];
        System.arraycopy(SHA256(params.getBytes("UTF-8")), 0, dataBlock, 0, hLen);
        System.arraycopy(message, 0, dataBlock, hLen + zeroPad + 1, mLen);
        dataBlock[hLen + zeroPad] = 1;
        byte[] seed = new byte[hLen];
        random.nextBytes(seed);
        byte[] dataBlockMask = MGF1(seed, 0, hLen, length - hLen);
        for (int i = 0; i < length - hLen; i++) {
            dataBlock[i] ^= dataBlockMask[i];
        }
        byte[] seedMask = MGF1(dataBlock, 0, length - hLen, hLen);
        for (int i = 0; i < hLen; i++) {
            seed[i] ^= seedMask[i];
        }
        byte[] padded = new byte[length];
        System.arraycopy(seed, 0, padded, 0, hLen);
        System.arraycopy(dataBlock, 0, padded, hLen, length - hLen);
        return padded;
    }
}


Nothing. The Riemann hypothesis would have some implications about the distribution of prime numbers. No cryptosystem uses the distribution of prime numbers for security, so there would be no effects on any current cryptosystem.

One cryptosystem in particular, RSA, uses prime numbers. But it doesn't use the distribution of prime numbers in any way, just the difficulty of factoring composite numbers which are the product of two large primes.

As a (strained) analog it would be like thinking that finding some information about the relation of total roadway length to population in countries and wondering how it would change mapping. Sure, maps draw roads, and countries, but the statistical information isn't relevant.


One time pad: why is it useless in practice?

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport.

After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the guy (Bob) you're sending the message to, and you need to send it in a way that's secure.

That's the real reason OTP's aren't used that often; OTP's would require meeting with the other side directly, or alternatively using a trusted courier; we rarely want to put up with the expense with either, especially since there are cheaper alternatives available.


Using a non-secure random generator for IV or salt generation

Let's take AES-CBC for example—a typical cryptosystem that requires a randomized IV.  Suppose I can predict the IV in advance.  Then I can start by asking for the encryption of $\mathit{iv}_0$, which is $\operatorname{AES}_k(\mathit{iv}_0 \oplus \mathit{iv}_0) = \operatorname{AES}_k(0)$, and proceed by asking to be challenged on the messages $m_0 = \mathit{iv}_1$ and $m_1 = \mathit{iv}_1 \oplus 1$ (or any message distinct from $\mathit{iv}_1$).  If I get back $\operatorname{AES}_k(0)$ as the ciphertext for $m_b$ for unknown $b$, then $b$ must have been 0; otherwise 1.  Hence if the IV is predictable in advance, AES-CBC is an insecure cipher—specifically, it fails the standard of IND-CPA.

On the other hand, most things called ‘salts’, like what you sprinkle on password hashes, need only be distinct between users to thwart multi-target attacks in the multi-user setting.  It's convenient to choose them at random from a large space so there is negligible chance of collision and no need for state, but that's not necessary in principle—a unique per-application identifier and a counter of hashes within that application would suffice.  (Without the per-application identifier, a multi-target attack could save effort attacking (say) the 7th user in each of a set of many applications.)

Similarly, if we take a nonce-based cryptosystem, like AES-GCM or crypto_secretbox_xsalsa20poly1305, and turn it into a randomized cryptosystem by choosing the nonce at random, the danger is, again, not in predictability of the nonces but in collisions of nonces—though in contrast to AES-CBC and password hashes, the consequences may be more catastrophic than merely revealing ciphertext equality or admitting multi-target attacks.


Blockcipher: key space define permutations of blocks

I do not think that collisions are dangeous.  If they would, most real world ciphers would not be secure. Here is the argument:

Even if the block size is 2 times the key size, you will get  lots of collisions due to the birthday paradox.
A good cipher behaves for each fixed message like a random mapping on the key space.
Let's assume |key space|= $2^{64}$ and |message space| = $2^{128}$.
For each message $x_0$, the birthday paradox says that for $\sqrt {2^{128}}  = 2^{64}$ randomly chosen values you get a collision probability above 0.5. This means that on average at least half of the messages lead to a collision.
As you have $2^{128}$ different $x_0$, at least (on average) $2^{127}$ messages will give you such a collision.


How to find modulus from a RSA public key?

I wanted to help break down exactly what you're seeing.

If you take your base64 string:

  MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCqGKukO1De7zhZj6+H0qtjTkVxwTCpvKe4eCZ0FPqri0cb2JZfXJ/DgYSF6vUpwmJG8wVQZKjeGcjDOL5UlsuusFncCzWBQ7RKNUSesmQRMSGkVb1/3j+skZ6UtW+5u09lHNsj6tQ51s1SPrCBkedbNf0Tp0GbMJDyR4e9T04ZZwIDAQAB

You then decode it into hex:

30 81 9F 30 0D 06 09 2A  86 48 86 F7 0D 01 01 01
05 00 03 81 8D 00 30 81  89 02 81 81 00 AA 18 AB
A4 3B 50 DE EF 38 59 8F  AF 87 D2 AB 63 4E 45 71
C1 30 A9 BC A7 B8 78 26  74 14 FA AB 8B 47 1B D8
96 5F 5C 9F C3 81 84 85  EA F5 29 C2 62 46 F3 05
50 64 A8 DE 19 C8 C3 38  BE 54 96 CB AE B0 59 DC
0B 35 81 43 B4 4A 35 44  9E B2 64 11 31 21 A4 55
BD 7F DE 3F AC 91 9E 94  B5 6F B9 BB 4F 65 1C DB
23 EA D4 39 D6 CD 52 3E  B0 81 91 E7 5B 35 FD 13
A7 41 9B 30 90 F2 47 87  BD 4F 4E 19 67 02 03 01
00 01

So the question is: what is this? Well it's actually the DER variant of ASN.1 encoding. ASN.1 is a horrible monstrosity, but you can use the web-based ASN.1 decoder to find that the values are actually this:

30 81 9F             ;30=SEQUENCE (0x9F = 159 bytes)
|  30 0D             ;30=SEQUENCE (0x0D = 13 bytes)
|  |  06 09          ;06=OBJECT_IDENTIFIER (0x09 = 9 bytes)
|  |  2A 86 48 86    ;Hex encoding of 1.2.840.113549.1.1
|  |  F7 0D 01 01 01
|  |  05 00          ;05=NULL (0 bytes)
|  03 81 8D 00       ;03=BIT STRING (0x8d = 141 bytes)
|  |  30 81 89       ;30=SEQUENCE (0x89 = 137 bytes)
|  |  |  02 81 81    ;02=INTEGER (0x81 = 129 bytes) the modulus
|  |  |  00          ;leading zero of INTEGER
|  |  |  AA 18 AB A4 3B 50 DE EF  38 59 8F AF 87 D2 AB 63
|  |  |  4E 45 71 C1 30 A9 BC A7  B8 78 26 74 14 FA AB 8B
|  |  |  47 1B D8 96 5F 5C 9F C3  81 84 85 EA F5 29 C2 62
|  |  |  46 F3 05 50 64 A8 DE 19  C8 C3 38 BE 54 96 CB AE
|  |  |  B0 59 DC 0B 35 81 43 B4  4A 35 44 9E B2 64 11 31
|  |  |  21 A4 55 BD 7F DE 3F AC  91 9E 94 B5 6F B9 BB 4F
|  |  |  65 1C DB 23 EA D4 39 D6  CD 52 3E B0 81 91 E7 5B
|  |  |  35 FD 13 A7 41 9B 30 90  F2 47 87 BD 4F 4E 19 67
|  |  02 03          ;02=INTEGER (0x03 = 3 bytes) - the exponent
|  |  |  01 00 01    ;hex for 65537

So encoded in there are the two important numbers in hex:

Exponent: 65537 (Nearly everyone universally uses 65,537 as their prime exponent)
Modulus: 00 AA 18 AB A4 3B 50 DE EF 38 59 8F AF 87 D2 AB 63 4E 45 71 C1 30 A9 BC A7 B8 78 26 74 14 FA AB 8B 47 1B D8 96 5F 5C 9F C3 81 84 85 EA F5 29 C2 62 46 F3 05 50 64 A8 DE 19 C8 C3 38 BE 54 96 CB AE B0 59 DC 0B 35 81 43 B4  4A 35 44 9E B2 64 11 31 21 A4 55 BD 7F DE 3F AC 91 9E 94 B5 6F B9 BB 4F 65 1C DB 23 EA D4 39 D6 CD 52 3E B0 81 91 E7 5B 35 FD 13 A7 41 9B 30 90 F2 47 87 BD 4F 4E 19 67

Or, in decimal, your modulus is:

  119,445,732,379,544,598,056,145,200,053,932,732,877,863,846,799,652,384,989,588,303,737,527,328,743,970,559,883,211,146,487,286,317,168,142,202,446,955,508,902,936,035,124,709,397,221,178,664,495,721,428,029,984,726,868,375,359,168,203,283,442,617,134,197,706,515,425,366,188,396,513,684,446,494,070,223,079,865,755,643,116,690,165,578,452,542,158,755,074,958,452,695,530,623,055,205,290,232,290,667,934,914,919

No need for OpenSSL and it's voodoo commands.


What is the purpose of Pseudorandom Function Families (PRFs)?

By definition, a family of functions (with a given domain and codomain) is a PRF if no efficient algorithm can (with non-negligible advantage) distinguish a randomly chosen member of the function family from a function chosen at random from the entire set of functions with the same domain and codomain.

Obviously, if the family contained just one function, distinguishing it from a random function would be trivial: just feed a couple of values into the function, and check if the outputs match those from the function you're trying to distinguish from random.

For example, let's say that we have an unknown hash function $f$ with a 256-bit output, and we're trying to decide whether it is a) SHA-256, or b) a randomly chosen hash function with a 256-bit output.  We can just feed the ASCII string Hello to the function, and check if the output in hexadecimal equals 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969.  If it doesn't, the function definitely isn't SHA-256; if it does, it almost certainly is.

However, if we're instead trying to tell whether $f$ is HMAC-SHA-256, we can't do this unless we know the HMAC key.  In this case, the set of all possible HMAC-SHA-256 functions forms a pseudorandom function family, where each function in the family is defined by a different HMAC key.


Indistinguishability Obfuscation : What are it's consequences on crypto?

Indistinguishability Obfuscation (iO) is a quite powerful tool, but its implications alone are really hard to tackle - as so often, the combination of different primitives enables us to do new and exciting things.

But before going into details, I am not sure if this is clear to you:

If you can use an algorithm $A$ (in your question that would be compact functional encryption) to get some interesting property $P$ (this would be the construction of iO), then this has no consequences for $A$ itself besides the obvious - that you can use $A$ to get property $B$.
Even if $P=NP$ is true, then iO would still exist. But it is also known, that public key cryptography and oneway functions would not exist. Generally speaking, $P=NP$ would be a nightmare for cryptography, because we would loose almost all of our building blocks. However, any construction/property from iO alone would still have to hold in a world where $P=NP$ - and the meaning of "security" is severely restricted there (or phrased differently: a lot of our current definitions would be invalid).

Regarding the general construction of IO in general, I suggest reading Survey on Cryptographic Obfuscation (2015, Horváth), which gives a decent overview. But here is a problem with iO:

The elephant in the room - Multilinear Maps:

The first construction by Garg et.al.in 2013 based ona primitive called multilinear maps - with a nice definition of their security. From that they build iO, but there was a problem: Multilinear maps in the way they defined them did not exist - and as far as a I know we only have constructions for limited versions of multilinear maps. So while their construction of iO is actually secure, we don't know if their assumptions actually hold for any construction.

In Obfuscation without the Vulnerabilities of Multilinear Maps (2016, Garg et.al.) this issue is adressed quite elaborately and proposes iO with multilinear maps without the known vulnerabilities. There are also other constructions of iO out there, but there are still open questions.

As for the current state of research: The topic is still relatively new and it is not fully explored. With iO we can achieve interesting constructions, for example deniable encryption, functional encryption, non-interactive zero knowledge arguments, etc. But all of those require some other assumption (which would be invalid in a world with $P=NP$) and build upon constructions with those. And as far as I know we don't have a construction which just uses standard assumptions.

The only way to get to know all the current research is by reading all related publications on the major conferences, I don't think there is any shortcut.


I have looked at some attacks on RC4 and be curious if some of them can be applied to Spritz as well. Does anybody else has analysed Spritz so far? Or is it far too early for results against Spritz?

No third party analysis. Probably way too early. (Even the paper you linked is unpublished.) The answer may of course change any time.

  From the performance viewpoint Spritz is really slow (compared to other related ciphers e.g. Keccak or Salsa20, SHA-256). Why didn't they go for performance? Nobody will use it if its that slow.

They say in the paper that they were using "a simple and unoptimized implementation of Spritz". With the possible exception of Keccak, the implementations of those other algorithms may have seen years of optimization work.

Looking at the actual numbers, Spritz generates keystream at ~95 MB/s compared to 150+ for AES and 290+ for Salsa20 and RC4. So it's slower, but not by orders of magnitude. That sort of gap could realistically be closed with optimization work, if the implementation truly is poor. It also isn't necessarily that big a deal in many applications. Further, hardware performance might look completely different, although I don't see anything to suggest that it must.

The same question could be posed of AES: why are we using AES CTR if stream ciphers like Salsa20 have twice the performance? AES of course has the advantage of being an older design that has seen its share of cryptanalysis, but versatility may also play a role. As a block cipher, AES can be used for a variety of things, from MACs to disk encryption, whereas a stream cipher is basically only for encryption and requires a MAC to prevent malleability.

Similarly, due to being a sponge function, Spritz, like Keccak, could be seen as a more versatile primitive, offering not only encryption, but also a hash function and a MAC. This would allow you to rely on fewer moving parts, hopefully avoiding bugs and security weaknesses, possibly gaining back some performance too. Having a simple algorithm also helps.

However, the hash function performance of Spritz is more than an order of magnitude slower, so I'm not sure you'd really want to choose it over Keccak...


Yes, this stems from elementary school arithmetic:
If you multiply two numbers ending in 1 the resulting least decimal digit or result will always be 1. Primality not required.
This does not however mean that if the resulting decimal digit is 1 both original primes end in one: e.g 7*3 or any primes ending in 7 and 3 respectively.
The best way to break RSA (excluding rubber hose cryptography) is to factorize the composite n. This is typically done using: https://en.wikipedia.org/wiki/General_number_field_sieve
Your observational on the behavior of the least significant digits though correct, does not obviously lead to any superior attack.
I use 2048 bit RSA and feel secure, and sometimes 4096 bits for extra safety margin. I expect this to remain this way for many years to come.


Disadvantages:

Message length: In Cryptography, usually, the message length is not considered secret. There are approaches that you can add random values to the end or beginning or both if this is really an information leak for you. The random approach depends on your actual data case. It is also possible that a pre-determined fixed size can be used as the e-mail can be limited to 512 characters. In the end, at least the upper bound is revealed in all of the cases.

The (IV, key) pair reuse is a real problem that can eliminate the confidentiality with the crib-dragging technique. This doesn't reveal the encryption key.

Lack of authentication Like all unauthenticated encryption modes, the bare CTR mode lacks integrity and authentication. A single bit of flipping can have catastrophic results due to the malleability of the CTR mode.
The AES-GCM mode that uses the CTR mode of operation provides you all-in-once, however, it has the same  (IV, key) pair reuse problem. There is a Synthetic Initialization Vector (SIV) mode as nonce-misuse resistance ( paper, rfc8452 ) that eliminates this. SIV mode can still leak that the same message is sent under the same key, so an observer can distinguish this.

Long message distinguisher:  The CTR mode is designed with a Pseudo-Random-Function (PRF). When using AES in CTR mode, we use it with Pseudo Random Permutation (PRP); $$E_k\colon \{0,1\}^n \to \{0,1\}^n.$$ Whit PRP as long as the message blocks are not repeated the sequence $E_k(0), E_k(1), \dots, E_k(\ell - 1)$ with $\ell < 2^n$ is not repeated. If the message with length $\ell$-block has no repeated block this is no problem. If we approach the message as uniform random block then we expect a collision $\ell \approx \sqrt{2^n} = 2^{n/2}$ by the birthday paradox/attack.
When used with AES-128 for long messages check for the repeat. The repeat enables the attacker to distinguish this from uniform random with non-negligible probability.
In short, a duplicate ciphertext in any position leaks that the messages are different.

Message size per key: although NIST say 64 nonce and 64 bit counter, one should stop using a key well before $2^{64}$ block. This is due to using a PRP (AES) instead of PRF in CTR mode.

Other advantages:

No need for the decryption: CTR mode doesn't require decryption of the block cipher, it always uses them for encryption. This is very helpful in constraint environments. Simplifies the software and hardware code, too.

No need PRP: Doesn't need a block cipher (PRP) at all. A hash function can be used like in the ChaCha series.

Prepocessing: the keystream generated by the CTR mode can be prepared before. This can help to use buffers.

CTR mode has CPA security.

A little history of CTR
CTR mode was introduced by Whitfield Diffie and Martin Hellman in 1979

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

A concrete Security of Treatment of Symmetric Encryption, Bellare et. al, 97 provides the security bounds.

See also; Comments to NIST concerning AES Modes of Operations: CTR-Mode Encryption, by Lipmaa et al. for other details of advantages and disadvantages.


What you are looking for could be in the Data Sheet (be sure to read 5.5) for the hardware layer, or/and the TCG PC Client Platform TPM Profile (PTP) Specification for SPI frame format.

You'll also need to find out what commands to send. The specs are there, and it is rumored that some have rewired their brain to actually use it (I'm not in). More.


How can convert affine to Jacobian coordinates?

When you go from Affine to Jacobian, $X$ and $Y$ stay the same, and $Z$ is equal to $1$

Affine -> Jacobian:

$(X',Y',Z') = (X,Y,1)$

Jacobian -> Affine:

$(X',Y') = (\frac{X}{Z^2}, \frac{Y}{Z^3} )$


Why does ed25519 seem to accept and use 96-byte / 384-bit signatures?

This is likely an artifact of the API used in the specific piece of code you're using. This piece of code follows the NaCl API, which verifies the input as the concatenation of signature and message (sm) and copies the message out of sm into the message buffer m. The NaCl paper explicitly states on p. 5 et seq. that this is an intentional design choice. The reason why it "will include extra bytes at the end of the signature" is because these seemingly extra bytes are actually the message that was signed.

Thus they're not actually 96-byte signatures, but rather 64+$L$-byte signatures, where $L$ is the length of the signed message in bytes, and 64 is the length of the actual signature.

Note that it is theoretically possible to have 96-byte signatures specifically, by skipping point compression, as noted on the original Ed25519 paper, p. 15, but this isn't the case in the code you're linking as an example.


Why does dragonfly key exchange need hunting and pecking?

Where is the mistake in that reasoning?

The problem is that would allow an attacker to test multiple passwords with the same exchange, hence losing the PAKE properties that we were trying to achieve.
With dragonfly, the honest side selects a secret values $p, m$, and outputs the values $s = p+m$ and $P = -m \cdot SKE$, where $SKE$ is the 'secret key element', that is, the one that you suggest to be derived $SKE = [password]G$ (I'm writing it in additive notation because hunt-and-peck comes into play in Dragonfly only if you're using elliptic curves).
Then, the honest party receives values $s'$ and $P'$ from the other side (the adversary), and then computes the secret key:
$$H( p( P' + s' \cdot SKE ))$$
and then sends an encrypted message based on that key (that is, if the adversary somehow obtains a guess to the same key, he can decrypt the message, and thus validate the key).
With your proposal, the attacker will know the discrete log of any SKE, that is, the value $x$ s.t. $xG = SKE$.  So, what the attacker can do (after receiving the honest peers's $s, P$ values) is select arbitrary $s', P'$ values (for which he knows the discrete log of $P' = p'G$) and send those, and then receive the encrypted password based on the value the honest party computed.
Then, for every password in his dictionary, computes the corresponding $SKE$ and $xG = SKE$ and then computes:
$$H( (p'+s'x)(sG + x^{-1}P))$$
If the guess for SKE was correct, this is the same secret key that the honest party computed, and that can be validated.
This can be seen to be the same because, if the SKE is the value the honest party used, then $pG = sG + x^{-1}P$ and $p' + s'x$ is the discrete log of $P' + s' \cdot SKE$
The attacker can perform all this computation for every password in his dictionary, hence he can test every password as the result of a single exchange.
Now, DragonFly doesn't have to use hunt-and-peck; there are other known hash-to-curve transforms that convert a password to an EC point in a way that you can't compute the discrete log.  However, DragonFly needs to use some such method...


What you are doing is the following:

Choose a random number $r$ in $[1,2^n-1]$.
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.
Check if $(\frac{r}{p})=(\frac{r}{q})=1$($(\frac{a}{n})$ denotes the jacobi symbol), if not go to 1.

So in order to speed this algorithm up, one needs to understand what the step #3 does.
"It calculates some Jacobi / Legendre Symbols" is too easy.
This step makes sure that $r$ is a square $\bmod p$ and $\bmod q$. Hence it makes sure that $r$ is a square $\bmod n$, because if r is a square $\bmod$ $p$ and $q$ than it's also a square $\bmod pq$. The calculations are split ub and not performed like $(\frac{r}{n})$ because $(\frac{r}{n})=(\frac{r}{p})*(\frac{r}{q})$ and if $(\frac{r}{p})=(\frac{r}{q})=-1$ then $(\frac{r}{n})=1$. So this doesn't work for optimzation.

But there's another way.
Step #3 makes sure we actually do have a square $\bmod n$, so why don't we construct $r$ to be a square $\bmod n$? Thus the "new" algorithm would look like this (sorry, I forgot the proper functions for Crypto++, post them in the comments please)

Integer r, rInv;
ModularArithmetic modn(m_n);

do {
    // Do this in a loop for people using small numbers for testing
    r.Randomize(rng, Integer::One() /*min*/, m_n - Integer::One() /*max*/);
    r = r*r%n; // square it, there was a better function for this IIRC
    rInv = modn.MultiplicativeInverse(r);
} while (rInv.IsZero()); // we don't need the symbols because r is always a square

So what are the security implications with this?
I don't know for sure, you should contact the author of the paper in either case and make sure this solution works.
The squaring of $r$ shouldn't harm the randomness / unpredictability as if $r$ is random, $r^2\bmod n$ should be random / unpredictable as well.
Timing attacks? Shouldn't be a concern I think because an attacker may only observe one squaring and after this a related squaring making it really hard to use this. (if it's not impossible)

What else to say?
You even can store the "old" $r$ if you need the square root of the "new" $r$ in a later step.
The new algorithm looks like this:

Choose a random number $r$ in $[1,2^n-1]$.
Set $r \gets r^2 \bmod n$
Check if $r$ is invertible $\bmod n$ (should be with probability $\approx1-2^{-1000}$, because by random luck you'd have to hit $p$ or $q$), if not go to 1.


The general question is, "what is the probability that $T$ is significantly far from its mean?" This is a question about the "tail" of a distribution.

Your random variable $T$ can be written as a sum of indicator variables, $T = \sum_{i=1}^q T_i$, where $T_i=1$ if the $i$th query begins with 8 zeroes. Hence, $T$ follows a binomial distribution $B(q,1/256)$ in the ideal world and $B(q,1/128)$ in the real world.

The standard way to estimate tail probabilities for binomial distributions is through the Chernoff bound. For example, in the ideal world, $T$ has mean $q/256$:
\begin{align*}
\Pr[ T > 3q/512 ] &= \Pr[ T > (1+0.5) q/256]
\end{align*}
So you can use the multiplicative Chernoff bound with $\delta=0.5$ to get:
\begin{align*}
\Pr[ T > 3q/512 ] &\le \left( \frac{ e^{0.5} }{ 1.5^{1.5} } \right)^{q/256} \approx (0.999577)^q
\end{align*}

You can do a similar computation to get a bound on $\Pr[ T < 3q/512 ]$ in the real world, and from that get a lower bound on the advantage.


Why is stateful CTR slightly better than stateless CTR? Does the adversary know the value of counter in CTR mode of operation?

For stateful CTR, what do we assume is predictable - the nonce or the counter?

Both. In general, the majority of implementations work as follows:

The input to the block cipher is the combination of IV/Nonce (96-bits) and Counter (32-bits). For each message, the Nonce increments by 1. For each block of a message, the counter increments by 1.

The state kept by communicating parties consists of the key, the last nonce used, and the last counter used. Importantly, keeping track of these ensures that the combination of all 3 is only ever used once, as repetition can allow plaintext recovery if an attacker knows one of the plaintext blocks used with that triplicate.

That predictability is also important for optimization, as both sender and receiver can precompute blocks of a message in parallel while waiting for the message to be received, or in multiple threads to increase throughput.


Yes one can, this is, for example, in Stinson's book "Cryptography and Security", 1st edition, from which I quote.

  We now display the resulting key schedule. As mentioned above, each round uses a 48-bit key comprised of 48 of the bits in K. The entries in the tables below refer to the bits in K that are used in the various rounds.

Round 1

  10
  51
  34
  60
  49
  17
  33
  57
  2
  9
  19
  42
  3
  35
  26
  25
  44
  58
  59
  1
  36
  27
  18
  41
  22
  28
  39
  54
  37
  4
  47
  30
  5
  53
  23
  29
  61
  21
  38
  63
  15
  20
  45
  14
  13
  62
  55
  31

Thus the round 1 subkey uses bits 10,51,...,31 in that order.


Is encryption with the Web Cryptography API resistant against side channel attacks?

The safe academic thing is to assume that no, something using the Web Cryptoraphy API can not be assumed resistant to side-channel attacks.

The Web Cryptography API is, as the acronym states, an Application Programming Interface. What it does is platform-dependent. For example, in a browser environment, the code that implements that API is browser-dependent (including version), and what it interfaces to can be OS-dependent (including version). User-settings may matter, compilation options of the native code often do. Plus, the feasibility of side channel attacks turns out to be CPU-dependent, microcode-of-the-CPU-dependent, setting-of-the-BIOS-or-virtualization-environment-if-any-dependent...

However, the worst is not certain! Actual feasibility of side channel attacks is extremely attacker-capabilities-dependent, and quite often it is pointless to assume that the attacker has a foot in the client machine (for in this case the attacker has options beyond side-channel attacks). And once there is the constraint to be platform-independent, perhaps the Web Cryptoraphy API is the best thing to use: rolling one's own side-channel-resistant implementation in JS is bound to be much less efficient than a native implementation, hard to the point of being next to infeasible, potentially ruined by the execution environment, and rightly recommended against by every expert.


Burmester Desmedt Key agreement. Is the division a floating point one or an integer one

Thus I wonder whether the division $k_{i+1}/k_{i-1}$ should result an integer of a floating point number.

An integer.

Specifically, this computation is done modulo $p$; that is, the result of this division is the value $d$ such that $d \cdot k_{i-1} \equiv k_{i+1} \pmod p$.

One way to find this $d$ is to compute the multiplicative inverse of $k_{i-1}$ modulo $p$ (for example, using the Extended Euclidean algorithm, and then multiply that inverse with $k_{i+1}$ (again, modulo $p$)


I'll be answering the question as in its body, which does not match the title (double encryption implicitly refers to using the same block cipher for each encryption, when the question is explicitly about two block ciphers).

With only the hypothesis that $A$ and $B$ are secure block ciphers sharing block size and key size, we can't conclude that the compound block cipher $G$ defined by $c=G_k(m)=A_k(B_k(m))$ is secure. An extreme example is that $G$ could be the identity function (e.g. $B$ could be AES-256 encryption, and $A$ AES-256 decryption).

And we can't make a rigorous exception for that case: $A$ and $B$ can interact badly in many ways to that $G$ is weak when $A$ and $B$ are secure (e.g. $B$ could be AES-256 encryption except for a modified S-box in the first SubBytes, and $A$ straight AES-256 decryption, so that $G_k$ is a transformation with no diffusion between bytes of a block, and quite a weak transformation of each byte).

On the other hand, there are (overwhelmingly many) cases where $G$ is more resistant to attack than either $A$ or $B$ is (e.g. $B$ could be AES-256 encryption reduced to the initial AddRoundKey and first 7 rounds, and $A$ AES-256 encryption reduced to the last 7 rounds, so that $G$ is the full AES-256). Thus we can't hope for general attacks working against $G$.

Thus, sorry to say, but what's explored with the question's body appears to be a dead end.


How is the following different than RSA Signing of a document?

Two scenarios:

Alice sends a document to Bob that she has signed using her private key. Bob verifies the signature.
Alice sends a document to Bob. Bob encrypts a random message for Alice's public key. Alice decrypts it and sends it back to Bob. Bob verifies it's the same.

Both will only be possible if Alice has access to the private key, so you might think they are similar. However, the latter does not make any connection between the document and the authentication attempt. In fact, it allows a man-in-the-middle attack:

Eve intercepts a document meant for Bob, so Alice expects an encrypted message for decryption.
Eve sends another document to Bob, claiming to be Alice.
Bob encrypts a random message using Alice's public key and sends it to Eve.
Eve forwards it to Alice, who decrypts it and sends it back to Eve.
Eve can now send the decrypted message to Bob, convincing him she is Alice and that the document came from Alice.

In comparison, with signatures the document itself is signed. The signature cannot be transferred to a different document, or it will no longer verify. Moving it would require either breaking the asymmetric system to find the key or finding a hash collision.


Segmenting encryption to get the same results with the same key

Yes this would work as stated by you.

Explanation:

If you're using a library supporting ECB (which you are actually using in this example) you can input the whole 32 bytes of plaintext and will receive the corresponding 32 bytes of ciphertext. Splitting the operation into two calls doesn't make any difference for libraries as internally they do nothing else than simply calling the encryption function for each block and concatenating the ciphertext to get the output.

Standard note:

Do not use the encryption mode proposed by you (ECB) in the "real world".  Rather use GCM or an other authenticated encryption mode as you also have to check if your data was altered and came from the correct source.


How does the time complexity of block cipher change with increase in key length?

Usually we want a block cipher to be resistant to an exhaustive search attack on the key, if the key space $\mathcal K$ is the set of all binary strings of length $n$ then for a particular $k$ the attacker would have to search against $2^n$ possible keys, so the key length is chosen to make the mentioned attack infeasible.

Even if the cipher is proved to be computationally secure there is another (sometimes underestimated) security issue related to the cipher block size.

When we encrypt a message of arbitrary length it gets broken in chunks and the cipher is used within a particular mode of operation (ECB, CBC, etc) and because of the birthday paradox if the block size is not large enough the cipher could be vulnerable to a birthday attack which shows that after $2^{m/2}$ message blocks, where $m$ is the block size, we already have a 50% probability of having a ciphertext block collision and therefore leaking information about the original plaintext blocks.

For example 3DES works with key of length 168, which makes theoretically the exhaustive search attack unfeasible$^*$, but it's designed to accept blocks of 64 bits which means that after we collect $2^{32}$ encrypted blocks ($\sim$32GB of data) we expect to have a collision with 50% probability.

$^*$there is a known attack that runs in time $2^{112}$ instead of $2^{168}$


Parity checking on DES key if using ASCII chars

a key like "aaaaaaac" (ASCII encoding) is invalid, since "c" (0x63) has even parity

Right. Notice that restricting to ASCII ($2^7$ values per byte, of which $2^6$ with odd parity) severely reduces the already small keyspace of DES, from $2^{56}$ to $2^{48}$ keys ($<2^{45.5}$ if one restricts to printable ASCII). For this reason, DES keys are usually expressed in hexadecimal.

  how commercial / publicly - available packages treat this

A very common practice is to exclude parity checking of DES keys from the functionality offered, and simply ignore the low-order bit, treating a key byte of 0x63 (ASCII c) just as 0x62 (ASCII b).

Another practice is to reject a key as invalid if any of its byte has even parity. With 64-bit x and side-channel protection aside, that could be implemented on the tune of

x = (x>>4) ^ x;
x = (x>>2) ^ x;
if (( (~((x>>1) ^ x)) & 0x0101010101010101) != 0) // error

For why DES keys have parity, see Purpose of DES parity bits.


What problems might you encounter if you use a block size much greater than AES?

It may be very tricky to have a good distribution / diffusion of the input bits for each round. That would mean that you would either require a very intricate design for each round, or a lot of rounds to make up for it.

Furthermore it will also mean that you need to perform an operation of at least 1000 bits to perform any kind of calculation. This is not a desirable property in most circumstances. For some modes of operation such as CBC, it will mean that the minimum message size would be 1000 bits - and the IV would take up another 1000 bits. For counter (CTR) mode your message will not grow as only part of the output can be used. However, that still means doing 1000 bit calculations for possibly much smaller messages.

Most modes of operation function quite well for block sizes of 128 bits, although 256 bits would be beneficial for modes such as CTR (because the IV is split between a nonce and the counter).

Although a large block size is desirable for use in the design of hash functions, the avalanche effect does require a good diffusion of bits. Threefish - the block cipher used for Skein, one of the SHA-3 finalists - however does support a block size of 1024 bits, so ~1000 bits is certainly not unheard of (quite often the internal hash state is at least double the intermediate / output size). Skein 512 however requires 80 (!) rounds of Threefish1024 so it certainly wasn't the fastest algorithm out there.

A relatively fast large block cipher may also be beneficial for some format preserving encryption, by the way. In principle a single block encrypt of a unique value is secure, so having a large block size may be helpful avoid repetition of blocks. You could build a cipher with a larger block size from a block cipher with a small block size, but those kind of constructs are generally not all that efficient.


Comparing the first 50 bits of a hash Vs. the last 50 bits of hash

If I had a hash function outputting a 256 bit hash, would there be any discernible difference comparing the last 50 bits of 2 hashes versus comparing the first 50 bits?

No, not for a correctly constructed cryptographic hash function.

  My gut says it shouldn't be any different because theoretically a hash should use all possibilities of hash values with equal randomness.

That is correct.

  I guess what I am trying to say is can you have 2 hashes that finish with the same 50 bits yet have the first 206 bits different? (Assuming we are using Merkle-Damgård setup)

Yes, absolutely. There is always a possibility of two hashes matching by pure chance, but by checking only 50 bits instead of the full hash, you are increasing that probability significantly.

Checking only 50 bits of a 256-bit hash is essentially the same as checking all of a 50-bit hash (whichever 50 bits you choose). And as SEJPM is stating in their comment, the probability of two hashes of this size matching by chance is about one in $2^{25}$ (i.e. much higher than one in $2^{50}$) because of the birthday paradox. As user Meir Maor rightly pointed out, the birthday paradox does not apply here.

This answer to the similar question "Should I use the first or last bits from a SHA-256 hash?" might be of interest to you.


Is there an increased risk of nonce reuse when using GCM with a nonce more than 96 bits?

If you insist on random nonces, 128 bit random nonces are safer than 96 bit random nonces (but not as good as 96 bit counter-based nonces - I presume that is infeasible in your scenario).

The 128 bit random nonce is transformed (via GHash) into what is effectively a 96 bit nonce and a 32 bit counter; in the 96 bit case, the 96 bit nonce is used directly, and we use a fixed 32 bit counter value value $1$.  If this (96, 32) bit value is $(X, Y)$, then an encryption of an $N$ block message uses the values $(X, Y)$ through $(X, Y+N+1)$ (and the addition is done modulo $2^{32}$)

Now, GCM runs into trouble if either a used range contains the value $(0, 0)$ (which can't happen with 96 bit nonces), or two separate encryptions (with their nonces) use a value in common.

As for the first possible case (using a value $(0, 0)$ somewhere in the range), that happens with probability $2^{-128}(N+2)$ for an $N$ block message - obviously, 96 bit nonces are better there.

As for the second possible case (using two ranges that interest), 128 bit nonces are clearly better.  After all, for two ranges to interest, they must share the same $X$ component; for 96 bit nonces, that is sufficient; for 128 bit nonces, the $Y$ components also need to intersect, and unless $N$ is near the maximum, that has a probability less than 1.

If we model the prohibition on the $(0, 0)$ value as a single message that just happens to use that single value, then that falls in line with the 'no two messages can use intersecting ranges'.  Then, it is easy to see that encrypting $M$ messages with 128 bit random nonces must be at least as secure as encryption $M+1$ messages with 96 bit random nonces, and actually, because of the observation that two 128 bit nonces that happen to map to the same 96 bit space will generally not intersect, it is actually considerably better.

In addition, you claimed that GHASH was not collision resistant, and Woodstock claimed that GHASH output was likely not uniform.  Actually, if $H \ne 0$, then with 128 bit inputs, GHASH is a permutation, hence it is collision resistant, and the output is uniform.


How much entropy is lost via hashing when you add known or low entropy data?

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible outputs.

When $s$ is smaller than $n/2$, then it is expected that the hash function will produce $2^s$ distinct values, and all your $s$ bits of entropy are preserved. When $s$ reaches $n/2$, collisions begin to appear, and each collision means a tiny fraction lost entropy. You still preserve most of it, though. When $s$ reaches $n$ (e.g. you hash an input with 256 bits of entropy, with SHA-256), then it is expected that you get about $0.6·2^s$ distinct output (you lost one third of the inputs to collisions), so the resulting entropy will be a bit more than $n - 1$ bits. When $s$ is higher than $n$, the output entropy will still rise, but never exceed $2^n$: you cannot have more than $2^n$ distinct outputs of $n$ bits...

To sum up, when hashing your input, you preserve almost all your input entropy, up to at most the output size of the hash function. To make things simple: when you hash with SHA-256 an input of entropy $s$ bits, then you get an output entropy at least equal to the lower of $s-1$ and 255 bits.


They are there to check if the key was indeed correctly retrieved. It could for instance be that the key is a result of key decryption or key agreement. In that case, or simply during transmission, wrong keys are used. According to NIST FIPS 46-3:

  The 8 error detecting bits..."

Or even better, Wikipedia states ANSI INCITS 92-1981), section 3.5:

  One bit in each 8-bit byte of the KEY may be utilized for error detection in key generation, distribution, and storage. Bits 8, 16,..., 64 are for use in ensuring that each byte is of odd parity.

So you see, they're there to protect against errors reinstating/recreating the key.

Nowadays transmission errors are usually taken care of at the transport layer. As e.g. TCP/IP (and most other network protocols) already deliver a reliable transport mechanism the need for the parity bits has been strongly reduced. Things like parity checking are not seen as part of a cipher definition. Nowadays it is seen as an unnecessary nuisance, complexity where it isn't required.

In the unlikely event that you'd ever need to perform parity or CRC checking it is of course easy to add the necessary bits; as long as you strip them away again before using the key.