You don't need fully homomorphic encryption for this.  In particular, you don't need to use Gentry's scheme.  Any standard scheme for additively homomorphic encryption will be fine.  For instance, Paillier should work fine, as should exponential El Gamal.

Search this site and you can find lots of information on additively homomorphic encryption.    See, e.g., Can Elgamal be made additively homomorphic and how could it be used for E-voting? and https://crypto.stackexchange.com/a/9003/351 and https://crypto.stackexchange.com/a/12704/351 and https://crypto.stackexchange.com/a/9139/351.  Also, search the literature for work on "encrypted counters" and you should find additional stuff that might be helpful.

This is not the site to ask how to implement crypto in F#; ask on StackOverflow for coding questions.  Your questions about padding make no sense to me.  The real question is what algorithm to use.  Once you know what algorithm to use, just implement it (that's just a  straightforward matter of programming).


Are encryption algorithms with fixed-point free permutations inherently flawed?

Are all encryption algorithms with fixed-point free permutations inherently flawed?

Yes - when fixed points, or the lack of them, is knowable and detectable.

This is a violation of multiple modern semantic security definitions. For example, this means that plaintexts with repeating symbols are distinguishable with high probability from plaintexts that has none. It means you with a high probability can determine what a plaintext does not include, especially if you can observe multiple communications.

This violates security notions like chosen plaintext attacks, indistinguishability from random, and more.

  Can it be mathematically proven that all fixed-point free permutation algorithms can be broken with a "faster-than-brute-force" attack?

It always makes it easier to guess the plaintext (as according to the answer of question 1), but it does not necessarily make it easier to derive the original key (what bruteforce normally refers to). You can often not say with certainty what the original plaintext is without the key, but often you can settle for an educated guess.


What are some design considerations for S-Boxes?

The main consideration is to ensure no strong differential or affine properties.

Random S-Boxes are actually not bad in this regard though not necessarily optimal.

However Most would not trust "Random" S-boxes and prefer a Nothing-Up-My-Sleeve choice. For fear the designer may have cleverly selected the values to enable some unknown attack. We want some plausible explanation for why the specific values were chosen.

The AES S-boxes are such, they were selected based on a simple mathematical formula, and yet can be shown to be fairly resilient to differential and linear cryptanalysis.


How is the session key more secure than the public key?

From my understanding, if an attacker is able to decrypt a session key which was encrypted through a public key, then the attacker practically has the corresponding private key pair.

Effectively yes, however only for that single message. Note that session keys are chosen independently and so leaking one doesn't allow you to guess any others. The public key encryption is also independently randomized preventing efficient recovery from the known plaintext. Then, as soon as you consider more than one message, leaking a strict subset of session keys is not as powerful as leaking the private key once.

If you're looking for a scenario where recovery of the session key is sometimes possible but recovery of the private key is not consider the following:
Suppose you run on an old copy of Debian with a weak RNG. Further suppose that you want to send a message to somebody else running a modern copy of Debian who also generated their private key on that modern copy. Now because of the RNG bug, you accidentally pick a weak session key and encrypt it. You then send a message which gets observed by an adversary knowing you run old Debian and brute-forces the session key exploiting the bad RNG output. Now your message has leaked, but no messages from other parties using good RNGs leaked.
If this is "too far-fetched" replace the Debian RNG bug in the above explanation with say a Spectre side-channel leaking the session key.


Quoth Messrs. Rivest, Shamir, and Adleman in 1978:

  To find a prime number $p$ such that $(p - 1)$ has a large prime factor, generate a large random prime number $u$, then let $p$ be the first prime in the sequence $i \cdot u + 1$, for $i = 2, 4, 6, \dots$.  (This shouldn't take too long).  Additional security is provided by ensuring that $(u - 1)$ also has a large prime factor.

  A high-speed computer can determine in several seconds whether a 100-digit number is prime, and can find the first prime after a given point in a minute or two.

Quoth Messrs. Rivest and Silverman two decades later in 1999:

  We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem.  That is, by using strong primes one gains a negligible increase in security over what is obtained merely by using ‘random’ primes of the same size.

The latter reference also contains a handful of citations on methods for generating strong primes and their expected performance—admittedly, for numbers of somewhat smaller magnitudes, but the paper should explain why everyone may have been sapped of the motivation for more recent studies on the subject.  Specifically, citing John Gordon in 1984 (whose primitive typography renders the original paper nigh illegible), they summarize:

  The naive algorithm for finding a $k$-bit prime by testing random $k$-bit numbers for primality thus requires time $\Theta(k\,T(k))$.  Gordon's algorithm requires finding one $k$-bit prime after finding three $k/2$-bit primes, taking a total time of $$k\,T(k) + 3(k/2)\,T(k/2) = 1.1875 (k\,T(k)).$$  This justifies Gordon's claim that finding strong primes requires only 19% more work than the naive algorithm for finding strong primes.

Gordon's analysis assumes there is nothing remarkable about the distribution of strong primes among all primes.  While that's not a priori clear, any interesting properties of that distribution would likely be a remarkable result worthy of publication in a mathematics journal, at least, even if cryptographers don't care any more.

How to weigh the lack of interest of practical cryptographers against the excitement of pure mathematicians about completely useless but difficult trivia in number theory in the fine tradition of G.H. Hardy is a question I leave to the sociologists.


When do I need to renew keys for Salsa20 or HMAC?

Salsa20 has essentially no limits on its own for data volume: it can be used for up to $2^{64}$ messages of up to $2^{70}$ bytes apiece.  You could use it in a nonstandard way for, say, more messages if they're each smaller, by carving up the input to the PRF differently, as long as the total volume of data is below $2^{134}$ bytes.  You certainly can't exhaust this volume or even this many messages in a few hours.  There's no reason to complicate a protocol with key rotation just to limit the number of bytes or messages encrypted under a Salsa20 key.

But you may want to deliberately erase a conversation.  For that to be effective, you must be able to erase the key that can decrypt a transcript of the ciphertext over the network.  How often you do that depends on your protocol: for example, with modern messengers, key erasure happens after every message, while with TLS, it typically happens after a TLS session completes (though there have been a raft of historical mistakes in the design and implementation of TLS session resumption failing to erase keys).


Is there a way of sharing a key without anyone knowing what the key is initially?

You can use MPC in order to generate a key that is distributed amongst a set of users, without anyone knowing the key itself. This is a very standard MPC problem, and many different protocols can be used. For example, if you want to generate a key for ECIES encryption, then you can basically have each party $P_i$ choose a random $x_i\in\mathbb{Z}_q$ and send a commitment to $Q_i = x_i\cdot G$ along with a zero knowledge proof of knowledge of $x_i$. Then, after all commitments are received, all parties decommit and ZK proofs are verified. Finally, you define the public key to be $Q=\sum_{i=1}^n Q_i$. This will give you a plain additive sharing. You can use a similar idea to get a Shamir sharing as well.


This is called the diffusion property, and hash functions are explicitly designed to have this property. The reason you want this property is because it makes it harder to find patterns between similar plaintexts and their hashes.

Something like SHA-1 is based on a block cipher. This essentially means that hashing involves iterating some operations over a block of data many times. Each iteration, the bits get scrambled and effect the subsequent iterations. This way, one small change at the beginning makes a large difference 80 iterations later (SHA-1 does 80 iterations)


Creating a PKCS#12 file where public key doesn't match the private key

You could try portecle. Import your keystore.p12 store, using the correct password of course or it will (silently) fail. Delete the certificate entry, and import a new "trusted" certificate entry.

Now it could be that some PKCS#12 defined attributes are different (e.g. friendlyName, which is visible as alias in portecle. Normally the key and certificate are linked through the modulus value however, so this should not make a difference for anybody trying to use the private key and certificate. It's probably best to copy the alias of the certificate just to be sure.

Portecle is written to use the Java KeyStore class, which supports PKCS#12 out of the box. The Java keytool utility uses the same class, but it seems to automatically delete certificates and keys together so it is not much use here.


That depends on the protocol being used, but most pairing-based protocols assume that the Bilinear Diffie-Hellman (BDH) problem is hard: given $P, aP, bP, cP$ for group element $P$ and integers $a, b, c$ it is hard to compute $e(P, P)^{abc}$ for a given pairing $e$.

There are many related problems that, if broken, could be used to break the BDH: the discrete logarithm, the Computational Diffie-Hellman (given $P, aP, bP$ compute $abP$), etc.


Should I bother implementing DH + AES, or leave it to a library like Crypto++

Rather risk vulnerabilities of third party library than implement your own.
If you feel novice on this field, only implement cryptography yourself as an learning exercise.

Why:

Mistakes, lack of know-how and maintenance.

It is very easy to make novice mistakes in custom implementation of
cryptography. Even battle scarred veterans of the field do mistakes
now and then. The amount of software quality assurance (including
testing, reviews, ...) needed to ensure quality of cryptographic
library is very significant.
When vulnerabilities are found third party cryptographic libraries are (often) updated. The user of the software may be able to update the library to newer version and (assuming API compatibility) fix the issue. If cryptographic functionality is built inside the program, all vulnerabilities always require fixes to the program itself.
Cryptographic libraries have to protect them against attacks almost no other software needs to (like timing attacks, and pretty recently, sound). New attacks are found now and then.
Even when no new attacks are not found, the cryptographic practices develop (towards safer). For instance, NIST considers 1024 bit RSA modulus fairly safe to use now, but in 1.1.2014, the minimum NIST accepts will be 2048 bit. Similarly, other parties "upgrade" minimum key length requirements from time to time.


Assume that we use a 256-bit entropy to shuffle $\{0,1\}^8\rightarrow\{0,1\}^8$. Then is the fact true that the permutation can have at max 256-bits of entropy?

There's a semantic problem: in cryptography, unless otherwise stated, we consider Shannon entropy, and that's defined for a symbol-generating process, not for a symbol. A permutation can be a symbol, not a process. Hence "permutation … have … bits of entropy" is not something defined. That's true including if we consider Permutation Entropy (a different breed of entropy, discussed in the second section of the present answer).
What we can define is the entropy at the output of a deterministic process/algorithm generating permutations. And then yes, if there is 256-bit entropy (per symbol) at the input of this process (for example, if the input consists of 256-bit bitstrings chosen uniformly at random, uniquely defining one output permutation in a deterministic manner), then there can be at most 256 bits of entropy (per symbol produced, that is permutation) at the output. Argument: applying any deterministic function $f$ to a source of symbols $s$ can not increase it's Shannon entropy, defined as
$$\sum_{s\text{ with }\Pr[s]>0}\Pr[s]\,\log_2\left(\frac1{\Pr[s]}\right)$$
because $f$ can only change that sum when $f(s)=f(s')$ with $s\ne s'$, $\Pr[s]>0$ and $\Pr[s']>0$, and then that change is the negative
$$\Pr[s]\,\log_2\left(\frac{\Pr[s]}{\Pr[s]+\Pr[s']}\right)\,+\,\Pr[s']\,\log_2\left(\frac{\Pr[s']}{\Pr[s]+\Pr[s']}\right)$$
What's more, that threshold of 256-bit output entropy is exactly achievable: there are $(2^8)!=2^{1683.996\ldots}$ shuffles of $\{0,1\}^8$, and that's (way) more than $2^{256}$. Depending on how we use Fisher-Yates shuffling and the form of the entropy at the input, that threshold will be reached, or not.
One way to reach this 256-bit output entropy threshold, if the 256-bit input entropy is in the form of a 256-bit uniformly random bitstring, goes: the first 64 times the Fisher-Yates algorithm requires a random integer $j$ in range $[0,i]$ with $i\ge15$, we pick an integer $j$ in $[0,15]$ based on 4 bits of the input (that we assemble into an integer per big-endian convention, then discard). And any other time the algorithm requires a random integer, we pick the integer $j=0$. That method will generate one of $2^{256}$ distinct permutations with probability $2^{-256}$ for each, and probability $0$ for the $(2^8)!-2^{256}$ other possible permutations. That's exactly 256-bit Shannon entropy per permutation output by this process.
As noted by Maeher, the above must not be used to generate a pseudo-random permutation from a 256-bit uniformly random bitstring in a cryptographic context! If that's needed, one option is to seed a Cryptographically Secure Pseudo Random Number Generator (CSPRNG) and use it to generate the $j$ in $[0,i]$ during Fisher-Yates. The output entropy will still be near 256-bit per permutation, but it will be computationally impossible to distinguish the output permutations from permutations generated at random (that is, with $1683.996\ldots$ bits of entropy per permutation).

Answering the title of the question

What Permutation Entropy really is?

Permutation Entropy, and the "paper" linked in the question (which I won't discuss or seriously consider), have no relation with the entropy of a permutation generator. Permutation Entropy is an alternate entropy defined by Christoph Band and Bernd Pompe's Permutation entropy: a natural complexity measure for time series in  Physical Review Letters, 2002 (paywalled).
Given a source of values, it's Permutation Entropy of order $2$ is the Shannon entropy of a modification of the source, where we replace a symbol by $0$ if it's lower than the next, by $1$ otherwise.
This generalizes to Permutation Entropy of order $n>2$: we replace each symbol by an integer $k$ in $[0,n!)$ characteristic of the order of $n$ symbols starting from there.
A property of Permutation Entropy is that it's invariant when the source goes thru any strictly monotonous transformation. Perhaps that's interesting in physics, but I do not see that this property, or Permutation Entropy in general, is much useful in cryptography.


To be precise, different affine transformations following the Galois field inversion should give the same Walsh spectrum up to a $\pm$ sign, in terms of how many times each value occurs. Since an affine transformation is a linear transformation plus a constant vector addition, this is not surprising.

Don't forget linear cryptanalysis measures distance to the unbiased case (prob. 1/2) so signs of Hadamard coefficients switching between positive and negative is allowed. This is how come we can ignore the sum of the non targeted key bits modulo 2 during Linear cryptanalysis, since all they would do is switch the sign of the relevant coefficient.

Let
$$L_{a,b} := \sum_{x \in V_n} (-1)^{a \cdot x \oplus b \cdot S(x)}$$

where $V_n$ is the n dimensional binary vector space. Let $A x+c$ be an affine map where the linear part $x\mapsto Ax$ is full rank and thus invertible. It is then a simple matter of algebra to prove the result:
$$L_{a,b}' := \sum_{x \in V_n} (-1)^{a \cdot x
\oplus b \cdot (A \cdot S(x)\oplus c)}$$
by a change of basis.

Even better, in "The Design of Rijndael" by Daemen and Rijmen, (See  here, Appendix A.1 onwards, provided for personal research use only) there is a coordinate free approach using trace functions on the finite field to show this.

Similar comments apply for the correlation spectrum.


The author does not define hybrid PKE schemes. What is their
  definition?

A hybrid public-key encryption scheme is a scheme that uses public-key encryption along with symmetric encryption to gain speed advantages for long messages.

The usual instantiation is to simply encrypt a key for the symmetric scheme and prepend the resulting cipher text. The more modern approach is to choose a random element from the PKE scheme's message space and encrypt it. Then use the hash of said element as the key for the symmetric scheme. This is called the KEM/DEM approach and allows for easier usage of elliptic curves (see ECIES) and code-based crypto (see McBits by Bernstein et al).

  Why is it that XOR alone cannot perfectly hide challenge bit to the CCA2 adversary in hybrid PKE schemes?

This means that the following scheme isn't CCA2 secure. Encrypt by choosing a random key from the PKE's message space use this key as one-time-pad, prepend the random key - encrypted with the PKE. Decrypt by decrypting the random key with the PKE and then use the result to decrypt the data with the OTP. Note: The OTP could be replaced by a stream cipher and the key may also be the result of a key-derivation function.

You see what is missing here? The message is not authenticated.

Say you're given a cipher text $c$ for an unknown message $m$ to be decrypted (if you can you win the CCA2 experiment). Suppose further that $c=(E_{PK}(k),H(k)\oplus m)$ which is standard construction for this. Note that $H(k)=k$ is allowed. Now randomly choose a $r$ of length $||m||$ and compute $c'=(E_{PK}(k),H(k)\oplus m\oplus r)$. Note that $c\neq c'$. Now query the decryption oracle for $c'$ and obtain $m'=m\oplus r$. Now finally reconstruct the message $m=m'\oplus r$ and you have "won" the CCA2 experiment.


how to prove that given cryptosystem is not IND-CCA secure?

Given two plaintexts x1; x2 and a ciphertext (y1; y2) where y1 = f(r) and y2 = G(r) xor xi
for a random i(1,2) a CCA can query the decryption of (y1; ~y) where ~y != y2. Upon
receiving the answer x, the attacker can recover G(r) = ~y xor x. Then the attacker can
compute xi = G(r) xor y2 and find i.


Calculation of time needed to crack DES with my CPU

I can't provide you with good numbers without actually benchmarking on your system.

All I can provide you with are estimates, based on the fact that Serpent is roughly as fast as DES. Of course the figures I can give you aren't actually brute-force figures but rather how much data can be encrypted per time, but this should give a solid estimate of the required time.

The general approach is to measure how many keys per second you can try and then divide $2^{56}$ by this number which will result in the number of seconds you'll need.

So let's estimate for Serpent with 56 bits. Serpent can get up to 0.16 GB/s on your machine as this is mainly computation bound. 0.16 GB is roughly $2^{24}$ blocks for DES, meaning you can roughly try $2^{24}$ keys per second. This means you need $2^{56}/2^{24}=2^{32}$ seconds for this which is equal to 136 years.

I'm sorry but I doubt this is feasible for you.
Note that even the brand-new Intel Core i7 6700K can only do 0.47 GB / s meaning an i7 6700K would also still require roughly 45 years. And to get even more crazy: the Intel Core i7 5960X is the best consumer CPU as of now can only do 0.63 GB / s resulting in 34 years. Now finally consider the currently strongest possible server mainboard running 8x Intel Xeon E7-8890v3 with 18 cores. There's no measured benchmark out there but I assume the performance to scale linearly with the number of cores (75 MB/s per core) and the frequency (62.5 MB/s with E7's freq). This would mean that this board could do 9GB / s of Serpent meaning $2^{30}$ blocks and thereby $2^{26}$ seconds being equivalent to 2.12 years (however this board would roughly cost $56k in 2015).


Elliptic curves with field sizes that not byte-aligned

There are some good answers in the comments, let me summarize and add a comment at the end.
Binary fields
For fields of the form $\mathbb{F}_{2^m}$, so field with $2^m$ elements, there are attacks which use the fact that $m$ is a composite number. So in practice you would want $m$ to be prime, and in particular not a multiple of 8. Therefore in this case you're out of luck, you can't have a "byte-aligned" field. This is what poncho mentions.
Prime fields
For fields of the form $\mathbb{F}_p$, you would want to choose a prime such that you can efficiently do field arithmetic. In other words, you want to give the prime some structure such that the modular reduction becomes easy. Examples are:

Mersenne primes, i.e. primes of the form $2^n-1$. This makes the modular reduction extremely fast. Unfortunately there don't exist many, and the smallest one which achieves a $256$-bit security level is $2^{521}-1$. This is what SEJPM remarks.
Since there are not many Mersenne prime, you want to choose something a little different. In the NIST documents, they use so-called Solinas primes. An example is the prime for P-256, which is $p=2^{256}-2^{224}+2^{192}+2^{96}-1$.
Any other structure. A commonly used one is $2^{255}-19$.

What is important, is that being "byte-aligned" is not necessarily useful. In fact, there are many implementation tricks which use the fact that it is not. Take for example $p=2^{127}-1$. Any integer mod $p$ fits in four 32-bit registers, but only needs 127 bits. There is one extra bit which is "free", and there are circumstances where you can use this bit to speed things up. This is usually what is referred to as using a "redundant representation".
A note: this is kind of an ongoing discussion, but there are arguments why primes with any kind of structure are less preferred. The reason is that the structure of the prime will in some sense be carried over the elliptic curve group. This can have downsides, for example it makes "additive scalar blinding" harder, which results in a slow-down. I'm not saying one way or the other is better, but be aware that there are different opinions on this.


Blowfish Encryptions in Bcrypt hashing algorithm

It is not really clear what you propose instead of the original algorithm - using ExpandKey(state, salt, key) instead of ExpandKey(state, 0, key)? What about the second call ExpandKey(state, 0, salt)?.

You are right, each ExpandKey(state, 0, xxx) contains one XOR-ing of xxx into the P-array, and then Blowfish-encrypting multiple 64-bit blocks of zeros – in CBC-mode, if I read the description right - thus actually we are not encrypting zero, but the ciphertext of the last block – but each block is encrypted with a different cipher state (as the result of each encryption replaces some of the P- or S-boxes).

Using salt as input instead of 0 would not be very more difficult, but (if I understand the argumentation on your linked page right) it might need some registers more to store the salt, and thus might slow down the execution on processors which are low on register count. Also, with zero salt, this is identical to the standard ExpandKey of Blowfish, so an existing (maybe optimized) implementation can be reused here, and all analysis of Blowfish can be applied, too.


Can a CSPRNG, seeded with a key, be used to generate a byte sequence as long as the plaintext to XOR it with that?

Yes it would.

As CodesinChaos reminded us in his comment:

  We call that a (synchronous) stream cipher.

Look up RC4 and A5/1, two of the most statistically popular ciphers in the universe.  Also compare to a correctly generated one time pad.  Not a lot else to say at this point.


Key exchange without an underlying semigroup

Can this always be turned into an underlying semigroup? I am thinking that it should be possible to glue the different operations and domains/codomains into a semigroup action somehow.

It wouldn't appear so, as there's no reason to expect to be able to perform any operations other than the ones listed in the protocol; in particular, one wouldn't expect to be able to concatenate operations as would be expected in a semigroup.

For example, here's a simple way to turn a public key encryption method (e.g. RSA) into a key exchange method:

Alice generates a public/private key pair $pub_A, priv_A$, and also selects a random nonce $n_A$; she sends $pub_A$ and $n_A$ to Bob
Bob selects a random nonce $n_B$; he encrypts it with $pub_A$, and sends $Enc_{pub_A}(n_B)$ to Alice
Alice uses $priv_A$ to decrypt the ciphertext to recover $n_B$
Then, both Alice and Bob compute $h( n_A, n_B )$ to obtain the shared secret.

In this case, the private values are $priv_A$ and $n_B$; the messages that are exchanged are the values $pub_A, n_A$, and $Enc_{Pub_A}(n_B)$.  It is not at all clear how someone could define an operator that would take an unrelated message/private value pair (e.g. $priv_A$ and $Enc_{Pub_C}(n_D)$, you can consider all four possible pairs), and combine them into a meaningful value.


Why is xor'ing plaintext blocks and encrypting the resulting checksum not a secure MAC using CTR mode?

Bit flipping
Flip the bit in the position $x$ on ciphertext block $C_i$ then on the block $C_j$ where $i \neq j$ and similarly for the plaintext $P_i$ and $P_j$. The the new MAC result
$$T = (P_0 \oplus P_1 \oplus \cdots \oplus \bar{P_i} \oplus \cdots \oplus \bar{P_j} \oplus \cdots \oplus P_{n-1}) \oplus E_k(nonce||n)$$ will be the same for the plaintext $Q = (P_0\mathbin\| P_1 \mathbin| \cdots \mathbin\|\bar{P_i}\mathbin\|\cdots \mathbin\|\bar{P_j}\mathbin\|\cdots \mathbin\|P_{n-1})$
Now, send $(Q,T)$ as the message and the tag to the target and they will accept it as a valid tag. This flipping is not related to a single position. The attacker can choose more than one position as longs as the resulting x-or is the same.
Details
Flip is $\bar{x} := x \oplus 1 $ then
\begin{align}
\bar{C_i} &= \bar{P_i} \oplus E_k(nonce\mathbin\|i-1)\\
C_i \oplus 1 &= P_i \oplus 1 \oplus E_k(nonce\mathbin\|i-1)\\
C_i  &= P_i \oplus E_k(nonce\mathbin\||1)\\
\end{align}
So $\bar{C_i}$ and $\bar{P_i}$ work as an attack on the ciphertext. The tag calculates on the messages, therefore one-bit change will be not enough. We need to modify even pairs exactly at the same positions.


When is data origin authentication necessary but non-repudiation not?

Can anyone suggest an example of an application where we need to know who sent the data but it doesn't really matter if they later deny that they sent it?

I would argue that most situations where you need authentication are like this. You very rarely need to be able to prove anything to third parties.

For example, if you have a TLS connection to a server, you need to know that the data is coming from the server and not a man-in-the-middle attacker, but there is usually no need to later prove that the server sent you the piece of data it did.

Note that non-repudiation does not mean you cannot "prove to yourself" who sent the data. If you use symmetric authentication and know only two parties have the key, then you know that any MAC you did not create was created by the other party. However, since you could have created the same, you cannot prove it to anyone else.


Hash based stream cipher where the input is a constant, key, nonce and counter

Sure, you can do this. Officially the output of a hash function is not directly designed for this, but the output of SHA-256 is no doubt randomized enough to be used as a base for a stream cipher. And actually, ChaCha & Salsa use what is basically the same approach, but with a different PRF (compared with a PRP when a block cipher is used).

Of course, the devil is in the details. The nonce (96 bits) and counter (32 bits) are rather on the short side. Besides that, they don't follow the convention of having the more static nonce first and the counter next. Having a nonce for domain separation is nice, but as the key should be fully randomized, I guess it is not strictly required for this scheme.

As for the applicability: you haven't specified any padding scheme, and you do seem to be using the full 512 bit block size. That means you should have access to the low level block-based SHA-256 functionality to implement the scheme. Otherwise you would have two full blocks of SHA-256 to perform for one 256 bit output and one block with the padding and length encoding. The output is then the output of the last block operation (which also depends on the first one as the state is maintained). So in that case you would have a 4 x drawback compared with using a normal stream cipher at the minimum when using the full SHA-256.

If you are using the block size then you could define separate SHA-256 constants for the starting state instead of trying to shoe-horn them into the input block.

Generally the hash functions don't use table lookups and should be relatively safe against side channel attacks. Of course, side channel attacks are implementation dependent, so this detail is not a final verdict for any system.

A minor note: although logical, the output is not entirely related to the input block size for generic hash functions. So specifying $n / 2$ as output size feels a bit strange to me.


PBKDF2 when dkLen and hLen have the same size

The output length of the F step of PBKDF, i.e. the T_i each are of the size of your hash function's (or actually: your PRF's) output.

So yes, when the desired output size is as large (or smaller) as the hash function output, we have l = 1 and thus only one call to F(P, S, c, 1).

I suppose this is also the most common way to use PBKDF-2, the extension to longer generated key sizes is only included to make the scheme more generally usable.


I'm not aware of any attacks on SHA-512 this way. I would create a small function to validate that the input size to SHA-512 is indeed identical to the seed size though, just in case. Even without that the function should be secure. Kind of related is my question about KDF1 and KDF2.

Note that implementation of HKDF-expand from a hash should be pretty easy, especially if a HMAC construction is already available. KDF1 or KDF2 would be even easier, it would probably be trickier to find test vectors for those KDF's though. So you might ask yourself why not to use HKDF-expand.

Generating a 256 bit key using a KDF over a 128 bit means that the security margin would remain at 128 bit. Basically it's fine as long as you don't claim a security margin of 256 bit. Just claiming AES-256 bit encryption would probably mean the same thing to most people.


More than likely the wrong words were used in class, 'not reversible' was probably supposed to be tied to the understanding of Feistel type ciphers, where simply reversing the order of operations of the block cipher leads to decryption. We are talking about the block cipher here, not modes.
In AES, reversing the order does NOT lead to decryption, since not all the operations are their own 'self inverse' like they are in say, DES.
In AES, which uses a combination of MDS matrix multiplication, s-box lookups, and XOR, needs the inverse MDS matrix and s-box to decrypt when reversing the order of operations, in this case the subkey XOR does not change.
AES also offers something called Equivalent Inverse Decryption, which still needs using the decrypt matrix and s-box, but allows the order of operations to be the same as encryption. This works by changing some of the subkeys using the decryption operations. If you look at this from the start without a good understanding of the regular encryption and decryption functions and their component operations, it looks like witchcraft.
I recommend reading the original submission paper, which explains everything pretty well.


Use HKDF to generate your random data with inputs of your private key, the message being signed, and whatever entropy you do have available (such as a real-time clock value or other time stamp).

This way all random values you produce will be completely unpredictable to anyone without your private key, and will change with each message even if you have zero effective bits of additional entropy available.

Also, move away from SHA-1 if you can; it provides <70 bits of effective security when used in signatures, and you'll have interoperability issues in the near future without SHA-256 if you're also using any standardized protocols such as TLS.


RFC 5958 and RFC5959
seems to be the latest standard for storing encrypted private keys.
It obsoletes RFC 5208, also known as PKCS#8.
My understanding is that AES is one of the many encryption algorithms supported by RFC 5958.

The GNU Keyring File Format is a another standard for a file format that stores private keys using AES-128.

The Gnome Keyring implementation stores private keys using (among other things) AES-128 encryption.
Alas, it doesn't seem to follow any published standard, but perhaps it can be seen as a de-facto standard.
The Gnome Keyring FAQ briefly mentions that sometime in the future (after 2010) it will transition to "a standard way of encrypting the keyring" (PBKDF2) which apparently requires "A new file format" (perhaps one of the above formats?).


What is the cryptography job market like these days?

There is a no single variety of "cryptography job". iacr.jobs is very small representation

If you have an academic degree (like PhD in Crypto/Maths/TOC) then
very much your area of thesis might help finding a PostDoc/Asst Proff
types job for this you need to search for Universities that do work
in similar area.
You may get general faculty types position too in
their Security group if one exists usually in a Univ below your
Graduating Univ's ranking. This could be both theoretical
cryptography work or practical (systems level security) types work
depending upon your thesis etc.
Few industry associated research labs to hire crypto & security scientists they need academic qualifications like PhD too.
If you have industrial experience working on cryptographic libraries (open
source or proprietary) then you may get typical software engineering roles in C, CPP, Java with expertise in cryptography like projects that involve key management, PKI, Kerberos, SSL, Hashing, AES, protocol implementations etc.
There might be some jobs which are not explicitly advertised as cryptography jobs but may be part of larger projects that has security elements in it and you may get to work at API level calls to cryptography.
You could also be independent researcher/consultant types but you need street credentials there too like rockstar status those who found heartbleed type bugs, given blackhat/defcon type talks etc. Modern Ransomware research too needs good understanding of cryptography in order to breakupon those malware and provide decryption tools.

Note : By large it depends on what qualifications and work experience you have. Without both entry level jobs are almost rare in this niche field.


Termonology help: What is using AEAD without encrypting data called?

The tag is to best I can tell, a tag. It's not really a signature, it's not a hash, it's pretty close to a mac. Is tag in this case colloquially synonymous with anything else?

It is not just close to a MAC—it is a MAC.  Various synonyms:

message authentication code / MAC
MAC tag
authenticator
authenticator tag
authentication tag

  Is it right to say ChaCha20 in AEAD-mode? I know GCM has GHASH and GMAC, but I think those are the Galois part. Would be it be fair-enough to say I'm using ChaCha20 in HMAC mode? What would be the right way to phrase this?

ChaCha/Poly1305, as used in, e.g., is a specific authenticated cipher (or AEAD).  So is AES-GCM.  You shouldn't worry about the method by which they are constructed—what is important is the security contract of the whole thing.  You should generally forget the archaic ‘mode of operation’ way of thinking that requires a user to choose a block cipher and a mode of operation from two different cauldrons of unintelligible acronym soup and then mix them.

If you use ChaCha/Poly1305 with an empty ciphertext, there's no specific name for it, but it would be like AES-GMAC, which is AES-GCM with an empty ciphertext.  You could say you are using ChaCha/Poly1305 as a (nonce-based) message authentication code, I guess.

If you're really interested in the acronym soup (which is not useful in isolation outside the cryptography literature):

GHASH is a universal hash family based on polynomial evaluation in $\operatorname{GF}(2^{128})$.  Cheap in hardware, slow and often leaky through side channels in software.
GCM is a method of constructing a nonce-based authenticated cipher out of a 128-bit block cipher and GHASH.
GMAC is GCM with an empty ciphertext (but usually nonempty additional data) which serves as a nonce-based message authentication code.

None of these are ever used much if at all outside AES-GCM.  And:

HMAC is a method of constructing a pseudorandom function family out of a fixed hash function like SHA-256.  It is not related to GMAC, GCM, GHASH, Poly1305, ChaCha, or AES, except insofar as (a) it can also be used as a message authentication code like AES-GMAC or ChaCha/Poly1305 with empty ciphertext, and (b) it can also be used as a PRF, including as a stream cipher, like ChaCha.


Security proof. Adversary source of random coins.

It certainly wouldn't make sense for the challenger to provide the coins. If you are working with non-uniform adversaries, then you can assume that the adversary is deterministic. This is due to the fact that $BPP \subset P/poly$. Intuitively, a non-uniform adversary can receive as "advice" the best random coins that maximize its probability of winning the game. However, if you are working with uniform adversaries, then you cannot assume that the adversary is deterministic.

Note, that as part of the proof, if you need to somehow simulate something for the adversary, then you can always fix its random tape to a uniformly chosen string and then work with an effectively deterministic adversary. However, this is different to having the "challenger" in the game provide the coins; that would make no sense.


Inconsistency with PKCS#11 v2.40 CKM_AES_KEY_WRAP_PAD

The PKCS#11 technical committee is currently working on standard version 3.0. You can find the latest working draft here: https://www.oasis-open.org/committees/download.php/64968/pkcs11-curr-v3.0-wd09.docx

In fact, reworked section "AES Key Wrap" (now 2.16) solves your problems:

It allows all mechanisms to be used with Encrypt&Decrypt and Wrap&Unwrap.
It clarifies that CKM_AES_KEY_WRAP and CKM_AES_KEY_WRAP_PAD actually refer to NIST SP800-38F section 6.2 ("KW"), which in fact require an 8 byte IV.
It introduces new CKM_AES_KEY_WRAP_KWP, which is algorithm KWP of NIST SP800-38F section 6.3 you are looking for.

Header files for the working draft can be found here: https://github.com/oasis-tcs/pkcs11/tree/master/working/3-00-wd-01


More rounds after AES related key attack?

My question is how many more rounds would they have to use to keep this security margin on AES (other then adding a hash to AES 256 key schedule)?

When AES was standardized, the best known attack (pdf, page 19) in terms of rounds broken was a related key attack that broke 9/14 rounds of AES-256. The best attack on AES-128 broke 7/10 rounds.

Currently, the best attacks (pdf, paywall) are actually on full round variants. It's just that those attacks are only very slightly better than brute force. If you assume those attacks do not apply to increased-round variants, you would get the same security margin of unbroken rounds by defining AES-128 with 13 rounds and AES-256 with 19 – or maybe 14 and 20 for nicer numbers and in case an extra round can be broken with current attacks.

However, "rounds broken" is a rather crude measure. The best practical attack (in terms of computational cost) at the time of standardization was on six rounds for all variants. Now there are at least related-key attacks of practical complexity on 10/14 rounds of AES-256.

Either way, something like 14/20 rounds for AES-128/256 might be a reasonable number if the standard was revised, but attacks are still far from practical.

  And would NIST actually change the standard again to something more secure such as Serpent?

I doubt they would just change it to another existing cipher. Serpent may have more of a security margin, but it has also seen less cryptanalysis at this point. More likely would be another competition for "AES-2", like the one for SHA-3. Existing ciphers might be submitted, of course, but new ciphers would also be considered.


What does it mean that $BW_N$ is a permutation over the squares mod N?

"$BW_N$ is a permutation over the squares $\mod N$". Does someone know what that means?

You define your map $BW_N:\mathbb{QR}_N\rightarrow \mathbb{QR}_N$. Note that $$\mathbb{QR}_N:=\{r\in Z_N: r\equiv y^2 \pmod{N}, y\in Z_N\}$$ and a permutation is a one-to-one mapping (bijection) from a set into the same set.

Basically, this map is a permutation if under $BW_N$ for every $x\in \mathbb{QR}_N$ there is a unique $y\in \mathbb{QR}_N$ (and clearly the same for its inverse $BW_N^{-1}$).

Now, since you have $N=pq$ being the product of two Blum integers $p$ and $q$, you have that for every of the four possible square roots of $r\in\mathbb{QR}_N$, which are of the form $(\pm\alpha,\pm\beta)$, exactly one of those is also a quardratic residue modulo $N$, i.e., an element of $\mathbb{QR}_N$ (this is not hard to prove).

Consequently, $BW_N$ gives a bijection from $\mathbb{QR}_N$ to $\mathbb{QR}_N$ and this is what is meant by "$BW_N$ is a permutation over the squares mod $N$".

  Does that mean its a trapdoor permutation? Or what might it mean?

The factorization of $N$, i.e., the knowledge of $p$ and $q$, is the trapdoor of this permutation and is required to efficiently compute the inverse.


($\hspace{.02 in}$packet $\approx$ chunk)

They put a packet number into the plaintexts, and mac-then-encrypt the packets separately.


Correct method to encrypt data so that it can be decrypted only by Alice and Bob

The traditional way to go about this would be to generate a symmetric key and use AES to encrypt the transaction using that symmetric key. You would then encrypt that symmetric key with Alice's public key and publish that. Then encrypt the symmetric key with Bob's public key and publish that. You also publish the AES encrypted version of the transaction.

I say that is the traditional way is you could, theoretically encrypt the transaction directly with RSA (though it is typically not recommended). The transaction would have to fit size constraints (see my comment).

Now, there is one additonal requirement that you might not be aware of. I'm assuming that you wouldn't want anyone to be able to modify any of these messages that will be uploaded to a server without being detected (think a hacker breaking into the server). Therefore, you will have to digitally sign the copies of the encrypted symmetric keys and compute a MAC on the AES encrypted transaction. The MAC could be a traditional HMAC or by using an authenticated encryption mode such as GCM.


Is it possible and safe to use SAKKE for signing/verification, rather than for encryption?

In general, encryption schemes are not suitable for signatures. The misconception may stem from the symmetricity of operations in RSA encryption and decryption, which allows the core scheme to be easily used for signing as well.

That being said, all identity-based encryption schemes (IBE) can be used as general signature schemes, see e.g. Boneh & Franklin's original paper (https://crypto.stanford.edu/~dabo/papers/bfibe.pdf), last para of Ch.6. You will lose the "identity-based" in that setting though, so there may be not much point in using an IBE-scheme as a general signature scheme. In this sense, it is safe to use SAKKE as signature scheme, but this is probably not what you are looking for.

What I gather from your problem description, the problem is to detach the personal identity from the signature identity. This is not necessarily a cryptographic problem, as one might as well obtain "usual" PKI certificates using a pseudonym instead of the real name, or generate and publish personal PGP certificates with pseudonyms.

In a more restricted setting, it may be desirable to be able to sign anonymously, but still as a part of certain group. This falls under the category of group- and ring signatures. In the former, the anonymity can be revoked in special cases and in the latter not.

In the identity-based setting the concept is called Identity-Based Signature (IBS, e.g. Hess IBS, implemented in the PBC-library). In IBS, the verification can be performed using system-wide parameters and the identity only. Even in this case, the anonymity needs to be based on using pseudonyms. The advantages over conventional PKI include:

The ability to announce a space of pseudonyms even before creating any private keys
Depending on the administration of the master key, simpler and faster production of pseudo-identities with a corresponding private key.

Most likely the first advantage might suite your needs, as Alice could simply announce a space of identities (e.g. 0xA11CE000...0xA11CEFFF, 0x12345678...0x1234FFFF) and then use them up as needed, without having to bother creating private keys until actually required.

There is, however, a catch: if the system parameters (including the master key) are managed by a third party, this party would likely be able to associate the identities with Alice. If Alice manages her own master key, obtaining and publishing this public key is comparable to the effort of publishing a PKI public key. This will diminish the value of choosing the identity-based paradigm anyway.


"Classical hardness" is demonstrated in the very same way, namely, we find a problem that is believed to be hard then we reduce the task of breaking the security of the scheme to the task of solving that problem.

So, it is kind of the same situation, because maybe there exist classical polynomial-time solutions to the problem used and those solutions simply were not discovered yet.

The main difference is that, in general, we are far more used to classical computers than to quantum ones and maybe saying that a problem is believed to be classical hard is more meaningful than the quantum analogous because we have really studied those problems a lot in the classical setting...


Yes, the protocol in RFC6628 (and SRP) is vulnerable to brute force password search in the event of server compromise.
As Thomas Pornin puts it: for all password-based authentication protocols, what the server knows must allow for offline dictionary attacks, since an attacker who could get a complete snapshot of the server could simulate a client and a server on his own machines, and see when the simulated server accepts the password provided by the simulated client. This is rather unavoidable; thus, it is not a vulnerability of RFC6628/SRP specifically, but rather a vulnerability of authenticating clients with passwords.

That fact is acknowledged by a creative definition of resistance to server compromise:

  An augmented PAKE protocol is said to provide resistance to server compromise in the sense that the attacker cannot impersonate the user without performing off-line dictionary attacks on the password verifier.

The only thing I can think of to improve on that is replacing the password on the server side by a conventional entropy-stretched (purposely slow) hash (such as scrypt) of the password, with salt set to username and serverid, computed on client side at each use. So we have that entropy-stretching hash as the last line of defense in case of server compromise. That would require trusted and reasonably efficient code implemented on the client side, which is hard to get with the current browser architecture.

Update: There's room to add such entropy-stretching in RFC6628. As an option, RFC6628 allows for use of a so-called effective password which is $w'=H'(\text{0x00}\|U\|S\|w)$ (where $H'$ is a hash function; $U$ is the user's identity; $S$ is the server's identity; $w$ is the password remembered by the user, after normalization per RFC4013), then used to compute $W=g^{w'}\bmod p$. So if we use that effective password option, and use an entropy-stretching hash for $H'$ (that is: a slow one, at least for input starting in $\text{0x00}$), we have some serious protection. A brute force password search would require one evaluation of $H'$ per $U\|S\|w$ tested, and some extra work involving modular arithmetic to test against $W$.

Without the effective password option, the amount of work to test a password in an off-line password search attack following server compromise can be down to near one modular multiplication: we can express most passwords $w_j$ that we want to test as $w_i+\delta$ with $\delta$ in a small set, implying that $W_j=W_i\cdot\Delta\bmod p$, with $\Delta=g^\delta\bmod p$ precomputed.


Practical implementations of Multiparty computations

There is the Might Be Evil framework and FairplayMP. The hcrypt project also has a secure function evaluation library.

UPDATE:

Also, VIFF and SCAPI (though as of writing this, the SCAPI framework is not fully released).

March 2016:

I just came across FRESCO.


Explaining weakness of Dual EC DRBG to wider audience?

I wouldn't try to explain the mathematics of the backdoor.  Just explain that the NSA hid a secret backdoor in there.

Instead, I would suggest focusing on the history and the context.  For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers.  You could explain how random number generators are a classic weak point in cryptography, because of the RNG has been backdoored, whoever knows the backdoor can recover all your keys.  You could also explain how this is very hard to detect: since RNGs are supposed to output random-looking bits, if it's actually pseudorandom bits that the NSA can predict but no one else can (if the bits are actually coming from a PRNG that the NSA knows the seed to, but no one else does), this is very difficult to detect through black-box testing or through inspection of the supposedly  random bits.

If you wanted, you could explain that back in 2006, cryptographers discovered the mathematical structure that would allow a backdoor but shied away from making any accusations, because, hey, surely the NSA wouldn't do that -- that would be so egregious a breach, that it seemed hard to imagine it actually contained a backdoor.  And now things are changed: it appears that what seemed unimaginable, is in fact reality.  So, you could explain how this is an eye-opener for the cryptographic community and how it will change the way we think about government standards and system design for the future.

You could then explain the impact.  You could explain how the impact is believed to be relatively minor, because most people heeded Bruce Schneier's warning from 2007 and didn't use Dual_EC_DRBG.  However, you could explain that at least one major crypto library (RSA's BSAFE) does use it, for reasons that are unclear, so this might have an unknown impact on an unknown number of deployed products.  You could explain how this backdoor is likely to only allow the NSA to decrypt traffic, not anyone else.  And finally, you could explain what the biggest impact is: the potential for loss of trust in cryptographic standards and in American companies.  I'm not sure that we've seen the general public lose trust yet -- I think people still trust Google and Apple and Amazon to have their back -- but if that ever happened, that might be hard to recover from.

I see that you want to explain the mathematics.  OK, here is an explanation.  I'm going to attack a simplified version of Dual_EC_DRBG, but the simplification doesn't change any of the essence of the attack.

The algorithm specification specifies an elliptic curve, which is basically just a finite cyclic (and thus Abelian) group $G$.  The algorithm also specifies two group elements $P,Q$.  It doesn't say how they were chosen; all we know is that they were chosen by an employee of the NSA.  In the simplified algorithm, the state of the PRNG at time $t$ is some integer $s$.  To run the PRNG forward one step, we do the following:

We compute $sP$ (recall we use additive group notation; this is the same as $P^s$, if you prefer multiplicative notation), convert this to an integer, and call it $r$.
We compute $rP$, convert it to an integer, and call it $s'$ (this will become the new state in the next step).
We compute $rQ$ and output it as this step's output from the PRNG.  (OK, technically, we convert it to a bitstring in a particular way, but you can ignore that.)

Now here's the observation: we're pretty much guaranteed that $P=eQ$ for some integer $e$.  We don't know what $e$ is, and it's hard for us to find it (that requires solving the discrete log problem on an elliptic curve, so this is presumably hard).  However, since the NSA chose the values $P,Q$, it could have chosen them by picking $Q$ randomly, picking $e$ randomly, and setting $P=eQ$.  In particular, the NSA could have chosen them so that they know $e$.

And here the number $e$ is a backdoor that lets you break the PRNG.  Suppose the NSA can observe one output from the PRNG, namely, $rQ$.  They can multiply this by $e$, to get $erQ$.  Now notice that $erQ = r(eQ) = rP = s'$.  So, they can infer what the next state of the PRNG will be.  This means they learn the state of your PRNG!  That's really bad -- after observing just one output from the PRNG, they can predict all future outputs from the PRNG with almost no work.  This is just about as bad a break of the PRNG as could possibly happen.

Of course, only people who know $e$ can break the PRNG.  So this is a special kind of backdoor: the NSA presumably knows how to break Dual_EC_DRBG, but it's very unlikely that anyone else knows how to break it.  Even though we know now the backdoor exists, it's very hard to recover the secret backdoor $e$, because that requires solving a discrete log problem.

Hmm.  Maybe that's still too complicated, because it requires understanding additive groups and a little bit about elliptic curves and... ugh.  OK.  So, let me share with you an analogous: a PRNG that is just like Dual_EC_PRNG, except that it uses integers, instead of elliptic curves.  In particular, everything will be conceptually basically the same -- the backdoor will be the same, the PRNG will be the same -- this will just be easier to understand without any background in elliptic curve cryptography.  Hopefully this will give the intuition better.

The PRNG. The algorithm specifies a prime number $p$, and two integers $g,h$ that are both less than $p$.  The algorithm tells you that the state of the PRNG at each point in time is some number $s$ that satisfies $1\le s < p$.  To step the PRNG forward by one iteration, you set $r = g^s \bmod p$, $s' = g^r \bmod p$, update the state to $s'$, and output $t = h^r \bmod p$.
The backdoor. The backdoor is a secret number $e$ such that $g=h^e \bmod p$.  The NSA, who created the algorithm specification, chose $g,h$ by picking $h$ randomly, picking $e$ randomly, setting $g=h^e \bmod p$, and then publishing $g,h,p$ (but keeping $e$ secret, since $e$ is the backdoor).
Breaking the PRNG. Here's how the NSA can break this PRNG.  Suppose they observe one output $t$ from the PRNG.  They compute $t^e \bmod p$.  Notice that

$$t^e = (h^r)^e = h^{re} = (h^e)^r = g^r = s' \pmod p.$$

This means they were able to compute $s'$, the next state of the PRNG.  So, after observing just one output from the PRNG, they can infer the next state of the PRNG and thereby predict what all future outputs from the PRNG will be.

For instance, suppose you generate a random IV using this generator (and send it in the clear), then generate a session key using this generator, then encrypt stuff under that session key.  The NSA (who is eavesdropping on your communication and thus can see the IV) knows that the IV was output from this PRNG and can use their backdoor to infer the state of the PRNG and predict its future outputs -- and thus they can predict your session key and decrypt all your subsequent traffic.  You've been owned!

I hope this gives the intuition.  The problem with Dual_EC_DRBG is exactly the same as the problem with this hypothetical PRNG that I just described.  Hopefully this is simple enough to follow: if you understand how Diffie-Hellman works, you can understand why this is broken.


Is there a way to produce a decrypted output with the same size as the input message?

Yes, CTR mode should work for that. You must have a broken implementation as there is no padding required for CTR mode. You could simply use the leftmost bytes of the ciphertext though. If decryption fails because of that then you could simply pad the ciphertext with zero's, decrypt, and remove the number of (now random) padded bytes so your plaintext length matches the ciphertext length.

Note that often an IV is send as well. The IV needs to be unique for CTR mode (in such a way that the counter is always unique). This is even more troublesome for 8 byte block ciphers such as Blowfish than for 16 byte block ciphers such as AES. You would need to use a counter IV or establish the IV otherwise to make the ciphertext the same length as the plaintext.

  A way to calculate the length of zero-padding at the end (so that I can cut them off in the end).

For plaintext ASCII text you can simply remove all zero bytes at the end; zero is a control character called NUL which should not appear in printable text.

Note that there are two forms of zero-padding: one that always pads and one that doesn't always pad (which is more often used). You could encrypt a 8 byte block of plaintext to see which one you got.

Note that for binary messages that may contain a zero byte at the end that zero-padding is not deterministic, meaning that you cannot determine the exact amount of padding. You would need to implement a padding mode such as PKCS#5/PKCS#7 padding yourself if you require that.

Do not use Blowfish, use a 16 byte block cipher, preferably AES in an authenticated mode such as GCM (which does add the authentication tag as overhead though). Even Bruce Schneier - the inventor - doesn't recommend Blowfish anymore.

An 8 byte block cipher is especially harmful for CTR mode. You'd better use CFB or OFB mode if you have to stick to Blowfish. Those are also modes that turn the block cipher into a stream cipher, so they do not require padding.


Is it okay to use a hash of a timestamp as the IV for AES?

It depends on the chaining mode. With recent modes like EAX and GCM, the IV just needs to be non-repeating, so a timestamp is OK (as long as you take care never to issue two messages with the same timestamp: this can be a problem if you emit two messages in, say, the same millisecond, or if the sender clock is somehow reset through manual action or NTP; notably, consider that the NTP protocol is rarely protected at all, so an active attacker may play tricks on your clock).

With CBC, the IV must be uniformly random, and, depending on the situation, should be unpredictable by the attacker. For instance, if the attacker can trigger the encryption of some messages of his own choosing, he may use a predictable IV to obtain precise block encryptions which he could then use to alter some other messages in a controlled way. A timestamp is highly predictable. A tempting design would be to compute the IV with HMAC over the timestamp, using a shared secret key for that; on a general basis, use a Key Derivation Function to extend your encryption key into two keys, one for HMAC and one for the actual AES encryption (make it three keys: one for the HMAC-for-IV, one for encryption, and one for the MAC which you of course add to the message to thwart active attackers). However, making your own designs is known to be dangerous, and modes like EAX and GCM already do that job better.

To sum up: using a timestamp is a bit tricky since it is only mostly unrepeating. And it will not work well with all chaining modes.


Message length limit induced by block counter size

From the RFC you can see that a ChaCha20 block is constructed as follows:

state = constants | key | counter | nonce

Which is then processed in a number of rounds. So lets keep that in mind for the following Q/As.

1. Is it being implied that that using the same block counter repeatedly is a risk?

Yes. If you use a 32 bit counter then it is presumed to be used in modular fashion, using modulo $2^{32}$ calculations. That means $\operatorname{inc}(2^{32} - 1) = 0 \mod 2^{32}$. I.e. it overflows and resets to the initial counter 0.

That would mean that the state would get the same value (none of the other components changes for the same nonce), which means that the key stream starts to repeat itself. The processing of the state is otherwise deterministic, so you would get the same key stream block.

2. How is that risk calculated? What is the formula for the risk?

In the calculations below $P_x$ is a block of the plaintext message, $S_x$ is a block of the key stream generated by processing the state with the ChaCha20 rounds and $C_x$ are the blocks of the ciphertext (where the last block may be a partial block depending on the size of the message). $x$ is the position of the block within the plaintext / key stream / ciphertext.

This is basically a so called many-time-pad. If you have two blocks of the message $P_0$ and $P_{2^{32}}$ then you would have $C_0 = P_0 \oplus S_0$ and $C_{2^{32}} = P_{2^{32}} \oplus S_{2^{32}}$. But because $S_0 = S_{2^{32}}$ you can see rewrite that to $C_{2^{32}} = P_{2^{32}} \oplus (C_0 \oplus P_0)$ or, after a bit of rearrangement $P_0 \oplus P_{2^{32}} = C_0 \oplus C_{2^{32}}$, i.e. you leak the XOR of two plaintext blocks of the message by XORing the ciphertext at the same position.

This risk is 100%. How much information is leaked depends on the contents of the blocks of the message. Note that much more information becomes available if the same limit is crossed multiple times, as you can now XOR multiple blocks together in a pairwise fashion.

3. If it is a question of repeating blocks counters, then shouldn't the block size be the same as the nonce? 96 bits = 12 bytes?

That would not fit in the state; ChaCha20 is specified with a specific state size where state consists of sixteen 32 bit words, or 512 bits.

4. If it is not repeating block counters that is the source of risk, then is the risk just based on the total length of encoded data?  What is the formula for that risk?

This is about repeating counters, so this question is not applicable.

Note that a correct implementation should fail rather than overflow. Unfortunately for online implementations, where the size of the plaintext message is not known in advance, that would be after encrypting $2^{32}$ blocks.


Why would Diffie-Hellman Group 21 be 521 bits rather than 512?

"Group 21" was originally used by IKE to refer to a specific elliptic curve group, which happens to use $2^{521}-1$ as the prime modulus.

Your question is "why did they use $2^{521}-1$ is their prime, rather than a prime closer to $2^{512}$?

Well, it turns out that using $2^{521}-1$ is more efficient than a slightly smaller prime.  Most of the time implementing elliptic curve operations turns out to be performing modular multiplications, that is, given $a$ and $b$, compute $a \times b \bmod p$.  There are some tricks we can use for $p = 2^{521} - 1$ that aren't available for $p \approx 2^{512}$ (specifically because of the special form of $p^{521}-1$ as a Mersenne prime); and so they just took advantage of it.

There are no similar Mersenne prime circa $2^{256}$ or $2^{384}$, and so a similar trick was not available for the smaller Elliptic Curve groups.


Can Shor's algorithm factor multi-prime numbers?

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$.  (Otherwise, repeat with another $a$.)  If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

The cost is dominated by $(\lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.

Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:

If a prime factor is bounded by $y$, then $\gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$—e.g., trial division, Pollard's $\rho$, ECM, etc.  If $n = p q r$ and you find $u$ so that $\gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

Grover's algorithm finds a preimage of 0 under $u \mapsto [\gcd(n, f(n, u)) = 1]$ in the time for about $\sqrt{y}$ quantum evaluations of $f$.  For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{\sqrt{\log y \log \log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.

Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.


Is part of an output of secure PRNG also cryptographically secure?

Yes. Although the bit values are not identical per se (even given the same seed) you should use any of the 192 bits to form a 128 bit key - as long as you don't reuse any bits of course.

If the 128 bits are not secure, then the 192 bits should also not be secure. AES keys consist of bits that are entirely random and thus unrelated, so generating a 192 bit key and then using the leftmost 128 bits should be OK.


How does a Hashing algorithm always result in a digest in a fixed size?

Basic Building Blocks of a Hash Function

The part of a hash function that leads to the digest always being the same size regardless of input length is called the compression function. The compression function is then linked whmacith a domain extender which extends the compression function to allow it to map across any length of input.

Construction From Block Ciphers

I am going to use the construction of the WHIRLPOOL hash function as an example of how a compression function and domain extender works.

Setup

It is very simple to construct a hash function from a block cipher. The first step in a block cipher algorithm would be to split the data to be hashed into blocks the same number of bits as the input to the block cipher being used. If needed padding is added to the input to make it a multiple of the key size. No difference here from normal block cipher operation.

Compression Function with Domain Extension

There is a lot of variation between different designs here but basically what they all perform though is some means of feeding each block into the chosen cipher and some combination of XOR or some other operation on the previous rounds output, the current rounds output, the input, or all of the above. For example the following is the compression function of WHIRLPOOL.

For the following let:
$$
\begin{align}
    m_i\:&=\:\mbox{Message or Input}\\
    H_i\:&=\:\mbox{Output}\\
    W\:&=\:\mbox{Block Cipher}\\
    g\:&=\:\mbox{Bit Mapping Function}
\end{align}
$$

To construct a new hash function it would be possible to simply plug a new block cipher into $W$ and the size of input and output would change with the input and output new cipher. There are many other forms of compression function structures with different properties also, and they mainly consist of changing when, what, and in what order things are combined. I would put a link here but reputation limit, so wikipidia's compression functions article has more on this.

The domain extension which allows it to operate over any amount of data is simply how the output feeds back into the cipher as the key as each subsequent block is encrypted replacing the key schedule. It will only output the result after all blocks have been fed through the block cipher effectively limiting output to the size of the ciphers output no matter the input size.

Other Constructions

There are also hash functions that are based on mathematical problems that are hard to solve and also stream ciphers. This is really a topic that an entire book could be dedicated to but they all use the basic structure of a compression function and domain extender. More info on the general construction of hash functions, compression functions, and domain extenders can be found here: https://eprint.iacr.org/2012/322.pdf


How can I create pre-determined encrypted results?

What's asked is not possible if we add three constraints:

There exists a decryption method that given only the encryption results and the passphrase, outputs the original text.
The encryption/decryption method is not highly specific to a particular input (a particular menu to a local pizza place) or desired output (the lyrics to Star Spangled Banner).
In "I want my encryption results to be the lyrics to Star Spangled Banner", what's meant is that the full encryption results is exactly equal to prescribed data rendering as the lyrics to Star Spangled Banner.

Proof: suppose what's asked is possible with these three constraints. Using the same passphrase, encipher a variant of the menu to that local pizza place, in the same hypothetical method that gives the prescribed data rendering as the lyrics to Star Spangled Banner. The deciphering program of 1 has no way to decide which of the two menus it should output.

If we remove any of these constraints, what's asked is easy.

Argument for 1: Consider a decryption program that uses the help of an online server to retrieve the original text stored there, using the desired output as key.

Argument for 2: Consider a program that outputs the lyrics to Star Spangled Banner whenever the original text is a specific menu to a local pizza place, and otherwise performs as a normal encryption program; add a few easy technicalities.

Argument for 3: Consider an encryption program that accepts as additional input a text file with the desired output; and outputs a PDF or JPEG file that shows the text of that desired output, but contains in a comment field (not rendered by a PDF or JPEG viewer) the result of the encryption of the original text under the passphrase, per some standard encryption method. The decryption program will first extract the comment field, then use the standard decryption method. We can perfect the illusion by replacing the passphrase with the SHA-256 hash of the passphrase followed by the PDF or JPEG output file less its comment field.

There are countless ways to work around requirement 3; some even use a standard method modified in a detail. For example, with AES-CBC, it is easy to specially chose an IV such that a given 16-byte plaintext block enciphers to a given 16-byte ciphertext block under a given key, with no change to the decryption program. That's apparently how the idea illustrated in Angecryption started.

An entropy argument gives us a limit to how far we can go while meeting requirements 1 and 2: regardless of how clever we are in working around 3, the ciphertext is bound to be at least as big as we can losslessly compress the combination of the input and desired output, minus the entropy in the passphrase.


Is there an oblivious decryption scheme?

Yes.

The easiest way is if $K$ is an RSA private key, and Bob has the public key.

Then, here's how it works; we'll call the ciphertext that Bob has $C$:

Bob selects a random number $r$, and computes both $C \cdot r^e \bmod N$ and $r^{-1} \bmod N$ (where $e$ and $N$ are the public exponent and the modulus from the public key)
Bob sends $C \cdot r^e \bmod N$ to Alice
Alice uses her private key to compute $(C \cdot r^e)^d = C^d \cdot r \pmod{n}$, and sends that back to Bob
Bob then computes $(C^d \cdot r) \cdot r^{-1} = C^d \pmod{n}$; that is the decrypted message (and Bob can then remove the RSA padding).

Alice learns nothing, because since $r$ is a random number, so is $r^e$, and so the value she sees is uncorrelated to the original message.  Bob learns the decryption, but he doesn't learn anything else.

Now, it is possible to do this with any encryption algorithm (using secure circuits), however it is a lot more work.


Why do we encrypt-then mac but sign-then-encrypt?

Okay. So first up, let's eliminate encrypt-then-sign. Why is this a problem? The idea behind a signature is to prove that a message came from me even in the presence of malicious actors. If a malicious actor changes the ciphertext under the signature, clearly this invalidates the signature as per expectations, however, that is only one possible attack scenario. The other is that the attacker could claim ownership of a message simply by stripping off the existing signature and adding their own - this is trivial, since the ciphertext (not the plaintext) is signed.
So relying on the signature to identify the recipient in this case could be fatal. D.W. gives an example of this in his/her answer.
The alternative approach to this is sign then encrypt. Clearly a malicious adversary cannot modify this in flight, but again the purpose of the signatures is to indisputedly identify the sender. A malicious recipient could forward the signed plaintext encrypted and it would appear to come from the original sender, defeating the goal of signatures.
D.W. gives one approach for resolving the issue. Others are sign-encrypt-sign, encrypt-sign-encrypt etc.
In the MAC case, our goal is different. We want to know whether or not the ciphertext has been modified on the wire or not, and whether or not we should decrypt it (to prevent the creation of an oracle, for example) or reject it as corrupted. We are not attempting to identify who the plaintext came from, simply that it has not been modified in flight.
So you might ask, okay, what happens if an attacker strip off a MAC block from a ciphertext and replace it with their own? Since we have exchanged MAC keys and we assume these keys are still secure, the recipient will identify an invalid ciphertext and reject it.
It is also worth reviewing Thomas' answer for some additional items. Specifically, not all cryptographers agree that encrypt-then-mac is the most ideal approach.
Secondly, Thomas highlights that MACs provide automatic protection against chosen ciphertext attacks. D.W. has recommended in his/her answer that an IND-CCA2 cipher should be used - that is, one provably secure under adaptive chosen ciphertext attacks.
Although it is not entirely accurate, I would say that the requirement for MACs and IND-CCA2 to defeat chosen ciphertext attacks is a closer parallel than comparing MACs and Signatures, although at first glance it looks like MACs and signatures are doing the same thing.


how many blocks are encrypted at a time in DES Algorithm?

This is in fact a question about modes of operation, as mentioned in a comment.

The basic operation of DES itself only defines the block cipher, and the encryption of a block.  The encryption of multiple blocks with a single key is managed by the further application of a mode of operation.

Some modes of operation, like ECB, or CTR, are parallelizable.  In this modes, the encryption of multiple blocks can be done independently, and so the blocks can be split apart and encrypted simultaneously.

Other modes of operation, like CBC, are sequential.  In the case of CBC, each successive block requires the previous block to have been encrypted before encryption of the next block can begin.

There is a further consideration of implementation.  Even a paralleizable mode, like ECB does not need to be implemented in a parallelizable way.  Indeed, the simplest implementation is to continue to simply encrypt a single block at a time, so even a mode that may theoretically support encrypting multiple block simultaneously may very likely only encrypt a single block at a time in practice.

So, mode and implementation will determine how many blocks can be encrypted in parallel, not DES itself.  In the real world, you're relatively unlikely to come across actual implementations that encrypt more than a single block at a time.


Can we attack a hash function if we only have the input x such that y = h(x)

a) You can't reverse the hash function, but you can try to hash a lot of different x', and see if h(x') = y. Assuming you have second pre-image resistance, you should then have x'= x. This is possible only because you know that Peter's salary is in a small range (e.g. [0,10000]), so you can compute every hash.

b) Well, we didn't reverse the hash, we simply use a forward search attack... There is nothing more to say.

c) You suppose that you can't use a key, so I don't see how you can prevent the attack... Maybe concatenate x with a constant length secret value, if using a secret value without encrypting x allowed.

However, if you assume that Peter has a secret key he can use, one way of preventing this type of attack would be to use a secure way to compute the tag of x. You can take a look at HMAC, which is described in the link I provide.


How are isogeny graphs made and how are they helpful to crypto?

Let an elliptic curve $E(F_p)$ have the Frobenius discriminant $D_\pi$, and $\left(\frac{D_\pi}{l}\right)$ be a Kronecker symbol for some $l$-degree isogeny. If $\left(\frac{D_\pi}{l}\right)=-1$, then there are no
$l$-degree isogenies; if $\left(\frac{D_\pi}{l}\right)=1$, then two
$l$-degree isogenies exist; if $\left(\frac{D_\pi}{l}\right)=0$, then $1$ or $l+1$ $l$-degree isogenies exist.

  Therefore, if $\left(\frac{D_\pi}{l}\right)=1$. then $l$-degree isogenies of elliptic curves form branchless cycles, and changing
  direction in a cycle means switching to dual isogenies.

This is a Theorem2 of "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES", by Alexander Rostovtsev and Anton Stolbunov.
With this theorem, you can determine the shape of isogeny graphs.


Do I need to use a CSPRNG when creating salts for user accounts?

Answering your question

If an attacker have access to a copy of my users database table containing each salt and the related salted password, I can't understand how a CSPRNG would be more secure than a SHA12 hashed UUID. Can someone elaborate?

I’m not sure if you only have read the question “Cryptographically Secure Pseudo-Random Number Generator in Qt/C++ (Cross platform)” at StackOverflow, or if you also noticed the accepted answer. The answer practically answers your question here, just like it answered the question at StackOverflow.
Quoting the accepted answer:

If you think you need a cryptographically secure PRNG for generating salts then I must tell you that you do not understand what the salt is and how and why it works and against which kinds of attacks it is useful.
The simple fact that the salt must be stored in plaintext alongside the hash of the salted password should have given away that you do not really need a cryptographically secure PRNG for salt - or any PRNG for that matter. Frankly, you could have a simple 64-bit number, which you increase by one every time you need a new salt and it would be just as secure as a salt generated by a cryptographically secure PRNG.

Even though that answer was posted back in 2012, things haven’t changed and it is still valid.
That is why CodesInChaos already commented correctly…
Quote:

Salts only need uniqueness, so a UUID is fine. A CSPRNG is just the simplest way to generate a salt, not the only one.

and Quote:

If you prefer a UUID that's perfectly fine, though I don't know why you'd want to implement password hashing on the database side instead of the application. In general I recommend using higher level APIs which take care of hashing and salting at the same time. e.g. php's password_hash/password_verify functions.

In the unlikely case you’re still unsure about salts and what exactly the reason for their existence is, I would like to point you to the question “Can you help me understand what a cryptographic “salt” is?“ and its accepted answer, which explains things using different wording. Quoting part of the accepted answer which seems to be the most relevant to your request for elaboration:

A salt is simply added to make a common password uncommon. A salt value is generated at random and can be fairly small, the only purpose is to lower the probability that the hash-value will be found in any pre-calculated table. A common way to combine the salt and the password is to simply concatenate them, i.e. the stored hash value is Hash(salt||password). The common password password1 now magically becomes, e.g., 6$dK,3password1 and is very unlikely to be found in a table.
The salt can be stored completely in the clear in the database, next to the hashed value. Once the attacker has the database and wants to find the passwords, he needs to generate the pre-calculated table for each salt individually, a costly operation.

Besides that Q&A, you might want to search Crypto.SE for Q&As related to “salt” which might help you to fully grasp things related to salts. One of many examples: “Why not encrypt salt?”
Diving into your comments

I'm asking because I disagree it is the simplest. MySQL, for example, doesn't have a native CSPRNG.

Then you could use a simple incrementing integer, or anything else that would produce a UNIQUE salt. (Please note the word “unique” has been capitalized as a hint, not to represent frowned-upon “online shouting”.)

There are several reasons. First, database servers are way more secure than web servers. They are, most of the time, only accessible through the application.

First off, I have to disagree with your database servers are way more secure than web servers because that is not really the case. But let’s assume that to be correct (as it is not relevant to your question anyway).
You have to remember that your salt only needs to be unique, not secret. It isn’t there as “a secret to secure data”. A salt is merely used to make things like passwords unique – slowing attackers down in situations where they might want to use things like hash-tables.

Second, if your application is stolen, having the salt logic on it gives the attacker an edge.

That argument isn’t really relevant in your scenario as the attacker would still have to “guess” the passwords – which are the real secrets (in contrast to the salts, better: the salting function within your application). That edge you see is rather minimal… and if you use a separate database server anyway, your attacker would be looking at a function within your application that can produce salts… but he/she would still have no copy of the database(s) to do anything useful with his/her ability to replicate the salts your application uses. For that, they would need to also steal the database.

Third, I use salt in the database and pepper in the application, this way the attacker needs to stole both the application and the database.

Great. Now all you need to do is to understand that a salt is not a secret. If an attacker knows the salt because – for example – he/she stole a copy of your database and can look it up quick and easy, that attacker would still need to brute-force the hashed passwords. Only when using a hash that is known to be cryptographically insecure, you would have given the attacker some kind of edge. But if you used something sane and cryptographically secure (like – for example – SHA256, HMAC256, or bcrypt), such an attacker will still be facing a loooong and painful brute-forcing attempt.
Knowing how to recreate salts will not magically make brute-forcing password hashes easy. That is, unless you use a cryptographically insecure password hashing method (like plain MD2 or MD5). Therefore, I tend to recommend that – instead of trying to secure non-secrets like salts – you rather focus on how you hash the real secrets… the passwords. See, I mentioned SHA256 above as a cryptographically secure hashing function, but it’s not the most optimal way to hash secrets like passwords. In fact, things like SHA256, HMAC256, or SHA512 (which you mentioned in relation to creating salts) are not meant to be used as password hashing functions and should - as a logic consequence - not be used for that purpose (not saying you should avoid them when creating unique salts). That‘s why I also mentioned bcrypt – which is one of many dedicated password hashing functions out there and definitely more recommendable when it comes to hashing passwords. Other good password hashing functions besides bcrypt would be scrypt, PBKDF2, or Argon2. No salt and/or pepper on this planet will save you when you mess up the password hashing part, but even the worst salt won’t be able to cause much damage if you implement the rest of your password hashing correct.
TL;DR
Salts are not secrets. They do not have to remain secret; they only need to be unique.
Non-secrets like salts (and peppers) can be stored “in the open”; in your case: as plaintext, integer value, or binary blob in your database. Both your application as well as your database can contain the functionality for creating unique salts.
Instead of trying to “secure” salts, it’s more important to focus on how you hash the passwords. Use a dedicated password hashing function to do so.


For the purpose of key diversification (that is, assigning a unique key per device), a true master_key is customary; that is, one with plenty of entropy (like, 128 bits or more random bits). Edit: that's now stated in the question.

With that caveat, yes, PBKDF2(password=master_key, salt=serial_number, rounds=1000, dkLen=16)is appropriate to generate one 128-bit key; it's even overkill, especially as parameterized: rounds could be 1, since the only purpose of rounds is to stretch the password input, which is not needed if that input is a true key. Reducing rounds will speed up production, and use by a master server, with no cryptographic drawback.

And yes, AES(key=master_key, data=serial_number) is appropriate, and usual. As a benefit, that allows to just state: each card has a different key, something that has a (minuscule, and non-exploitable) chance not to hold with PBKDF2.

Edit: For the purpose of having strong diversified keys, the salt (typically, the serial number) needs not be high entropy. It is enough that it is different from one device to the other [one drawback occurs in case of temporary compromise of a resource capable of doing the diversification, without compromise of the list of salts/serial numbers of existing devices: it becomes possible to compute the diversified keys of all the devices if the serial numbers are sequential; PBKDF2 with rounds=1000, or whatever slow KDF, is not an adequate way to mitigate that risk; a delay is much better].

Also, ask yourself one question: is there potential for a side channel attack on the device(s) doing diversification? If yes, is PBKDF2, which is hash-based, really appropriate from that implementation standpoint? I have yet to see a hash implementation evaluated against DPA, contrary to AES implementations, where this risk of DPA attacks is at least assessed.

Side note: if key stretching was needed (it is not), rounds=1000 in PBKDF2 is clearly obsolete; that was a suggested minimum over 12 years ago, and IMHO was not enough even at that time. Moore's law and friends (in the form of the democratization of GPU and FPGA accelerators) have made it necessary to use at least rounds=100000 for equivalent security. Further, PBKDF2 is obsolete as a key stretcher, except perhaps if you have a hardware-accelerated hash and positively no memory; scrypt is the new state of the art.


The title of the protocol and explanation of the steps required

This protocol is known as Kerberos, at least, as originally implemented (I believe the protocol has been extended significantly since).
Within Kerberos, the tuple $[s_2, s_A]$ is protected by $k_2$ (which both R and B know); hence no one else can modify it.
This tuple essentially tells B "A wants to talk to you, and use key $k$ to do so".  A third party could forward this tuple directly to B, but it doesn't give him an advantage; after all, A really does want to talk to B.  This third party could prevent A from receiving his message from R (and so A doesn't learn $k$), however the third party doesn't learn $k$ either, so B gets a key that will never be used.
It may be that, in the original protocol, the tuple R sends to A was encrypted by $k_1$; this would obviously prevent this attack - it's been a while, and so I forget the details.  Even if it doesn't, this attack doesn't doesn't achieve anything, other than preventing A from talking to B, and an adversary that can arbitrarily modify or delete messages can trivially do that.


Collision resistance of composed hash functions

Suppose you have found a collision for $H^2$, ie a pair $(x_1,x_2), x_1\neq x_2$ such that $H^2(x_1)=H=H^2(x_2)$.

Now let $F$ be a deterministic function (like $H^1$?). Does
$$(F\circ H^2)(x_1)=F(H^2(x_1))=F(H)=F(H^2(x_2))=(F\circ H^2)(x_2)$$
yield anything interesting?


Why does $p$ need to be a prime number?

That's necessary for arithmetic modulo $p$ to be a field. For non-prime modulo, we only get a ring.

That's important because we want to compute modular multiplicative inverses, and need a field for that to work consistently.

More specifically: if $q$ is such that $0<q<p$ and $\gcd(p,q)\ne1$ (which is possible when $p$ is not prime), then there exists no $r$ with $q\,r\equiv1\pmod p$, that is $q$ has no multiplicative inverse. This would invalidate formulas with the term $(x_P-x_Q)^{-1}\bmod p$ when $\gcd(p,x_P-x_Q)\ne1$, as used when performing point addition. With $p$ prime, that can only occur for $x_P\equiv x_Q\pmod p$, which can be handled as a special case in point addition.

  you can only have modular inverses of prime numbers

Uh, no. Counterexamples abound. Say $1$, which is not prime, and is its own modular inverse; and $4$, which is not prime, and has modular inverse $7$ modulo $9$, since $4\times7=3\times9+1$.

Correct formulation: reliable modular inversion requires prime modulus.

More precisely: all integers from $1$ to one less than the modulus have a multiplicative modular inverse if and only if the modulus is prime.

Note: for different (security) reasons, the number $n$ of points on the curve (including the neutral, also known as the point at infinity) needs to be a prime too (as it is in ECDSA), or at least to have a large prime factor.


Given a ciphertext in RSA which is not comprime with our N, can we get the secret key?

Let $N=p\cdot q\quad,p,q\in\mathbb P$ be a semi-prime (as in RSA). Further let $a$ be any number for now. $$\gcd(a,N)$$ can now take exactly 4 values:

$\gcd(a,N)=1$
$\gcd(a,N)=p$
$\gcd(a,N)=q$
$\gcd(a,N)=N$

because there are no other factors of $N$ which could be the greatest common divisor.
Now let's take $c$ (your cipher text) instead of $a$. We can exclude case 1 because we know $c$ and $N$ are not co-prime (remember how co-prime is defined as $\gcd(a,b)=1$?). We can exclude case 4, because $c$ is an RSA ciphertext and thus was reduced $\bmod N$ before and this automatically ensures that $c<N$. Furthermore $c$ is supposed to be a ciphertext for which the case $m=0$ probably happens with negligible probability and the only encryption that can yield $m=0$ is one of multiple (including 0) of the modulus, i.e. only 0, if we assume $m<N$ as usual (which excludes the case where $m=0$ which would yield $\gcd(c,N)=N$)(thanks poncho and fgrieu). Also note that you don't need to bother with the key at all if $c=0$ because you directly know that $m=0$.

Now we're left with only two possible options: $p$ and $q$. So the $\gcd$ has to be one of that. And if we know one of the factors of $N$, everything else follows trivially.

Also note that "a and b are co-prime" is equivalent to $\gcd(a,b)> 1$ and that this doesn't have to imply $a=k\cdot b$ for some k, because it may also be that $a=pq$ and $b=mp$ which would yield $\gcd(a,b)=p$. For a concrete example consider $a=10$ and $b=15$.


Blum primes [x=3(mod 4)] zero knowledge proof?

I believe a zero knowledge proof that $-1$ is a quadratric nonresidue would accomplish that.

If we know that $n$ has two prime factors, and that $n \equiv 1 \pmod{4}$, then $n$ is either a product of two primes both $1 \bmod 4$, or two primes both $3 \bmod 4$.

If it were the former, then $-1$ is a QR modulo $p$, and $-1$ is a QR modulo $q$, and hence $-1$ is a QR modulo $pq$.

On the other hand, if $p \equiv 3 \bmod 4$, and $-1$ is a QNR modulo $p$, and hence a QNR modulo $pq$.

As for how to implement a zero knowledge proof that $-1$ is a QNR, see this paper


Efficient pen-and-paper calculation of the Galois Field multiplication?


Is it possible to deduce the IV from CBC ciphered data, without knowing the key?

For CBC mode, the IV must be

Never used twice with the same key
Unpredictable

So, in your example (filename$\oplus$key), if you ever encrypt two files that have the same filename with the same key, you will violate #1.

Now, you may be tempted to say "but I always generate a new key for every file that I encrypt, so that example doesn't apply". Fine, it doesn't. There are probably some use cases where filename$\oplus$key is fine. But, there are a lot of use cases where this will have big problems. In crypto, we typically try to develop our systems so that they are secure no matter how they are used. This is often not entirely possible, but that is what we aim for. So instead, we would generate a random IV and publish it with the ciphertext.

To give you an example of where filename$\oplus$key could have issues, consider the following. What if you publish your IV (which is a very, very common practice). Then all I have to do is brute force the file name and I have the key.


That's SHA-1; TLS uses either SHA-1, or on occasion a SHA-2 hash (and those would be listed as SHA256 or SHA384).  I've have never heard of anyone actually using SHA-0 (the hash algorithm originally proposed by NIST).


Do data-dependent rotations have any advantage over fixed rotations?

Compared to fixed rotations, data-dependent rotations improve resistance to differential and linear cryptanalysis. A fixed rotation has no effect (beyond helping with diffusion) in the probability of a (xor-)differential characteristic, whereas a data-dependent rotation also introduces differences in the rotation amounts, which brings probabilities down. There's a 2000 paper by Scott Contini that quantifies this advantage.

Successful attacks against ciphers using data-dependent rotation have focused on trying to avoid differences in the rotation amounts, or to fix them to some value; this was the case for RC5. Later designs like RC6 and MARS made this harder by using more complex functions as the input to the rotations. This is an interesting paper studying the effect of varying that complex function in RC6, and how it affects the overall security of the cipher.

That said, the disadvantages you listed outweigh the potential advantages, and data-dependent rotations are generally not employed in new designs.


Is multiple hashings of a cryptographic hash function an acceptable way to increase complexity?

Iterating a hash function such as SHA-256 does raise the cost of brute-force preimage attacks to recover passwords from password hashes, and in fact this technique appears in most password hash functions, usually with some variation in the input to the hash function in each iteration.  See, for example, PBKDF2 for a widely used password hash function that does only this.

However, it does not exponentially increase the cost of a brute force preimage attack.  It only linearly increases the cost, because if you iterate SHA-256 2x instead of 1x, the attacker must do 2x as many SHA-256 evaluations.

The cost here is measured in the area*time product of an attack, not how long an attack takes in wall clock time: an attacker with $2n$ CPU cores can compute an attack on 2x-iterated SHA-256 in the same time an attacker with $n$ CPU cores can compute an attack on 1x-iterated SHA-256.  To attack your iterated SHA-256, a smart attacker will buy computers with many CPU cores on a die to attack hashes in parallel, e.g. with GPUs or custom ASICs.  This is essentially what Bitcoin miners do.

The cost factor you can impose on the attacker by this method is bounded by the time you're willing to wait for your CPU to compute the password hash function once.  But there's another way you can impose cost on the attacker, which is by making the password hash require a lot of memory as well as time.  Area on the die dedicated to memory can't be used to attack multiple passwords in parallel like area on the die dedicated to extra CPU cores can.

Sequential memory-hard password hashes were introduced in scrypt to force attackers to spend either a linear amount of memory or (say) a quadratic amount of time to compute the same function you compute.  Since on your laptop or phone you typically have gigabytes of memory available, you can easily spend a lot of it to evaluate a single password hash in a tolerably short time.  This is how modern password hashes such as scrypt and argon2 work to raise the cost for an attacker without hurting legitimate users.