How to build an electro-mechanical public key cipher machine?

Since this is an historical question, I am going to digress and make some historical corrections. In science, we give credit for important inventions to the people who published. If it turns out that someone else invented it earlier and didn't publish, they don't get credit. Obviously, they should be mentioned in passing or a footnote in the interests of complete information, but credit for inventing something goes not to the person who keep it secret, but to the people who publish.

Thus, I must take issue your saying that GCHQ invented it. As smart and forward-thinking Ellis, Cocks, and Williamson were, they didn't publish, so they don't get credit for inventing it. (Also, they were at CESG, not GCHQ. Some may find this a difference without distinction, but Ellis himself makes that point in his notes on their work.

Secondarily, public key encryption is generally credited to some combination of Merkle, Hellman, and Diffie, who were at some combination of Stanford (where it was understood) and Berkeley (where it was misunderstood). Diffie's article, "The First Ten Years of Public-Key Cryptography" is a great account of this. You can also find Merkle's rejected 1974 Berkeley project for what was an early form of public-key cryptography on his Computer History Museum bio.

Thank you for your forbearance on the above. Now let me answer your question.

The basic idea in public-key cryptography is that there are problems that are easy to do in one direction and hard to do in another. At it's easiest, this is intuitive. Anyone who has struggled through learning long division knows that there's a very real sense in which dividing is harder than multiplying. But more more importantly, the structure of public-key (or non-secret) encryption is that there's one key to encrypt and one key to decrypt and you can't derive the decrypt-key from the encrypt-key. That's why the encrypt-key is either public or non-secret.

In construction, the Merkle-Hellman-Diffie ideas played around with "trapdoor" functions that had a secret that made the problem very easy to solve. The basis for discrete-log public key cryptography is that exponentiion -- $g^x$ in a finite field with a public $g$ and a secret $x$ is easy to solve for the person who knows $x$, but hard without knowing the trap door of $x$.

Similarly, RSA is built on the difficulty of factoring, and the trap door is that if you know the two primes you've multiplied together, it's easy to undo an RSA calculation. Rabin is based on the hardness of square roots (think of it being a special case of RSA where the public exponent $e=2$), and so on. Just as it's easy to intuit that division is harder than multiplication, taking a logarithm or a square root or factoring is intuitively a lot harder.

So how does this apply to electro-mechanical systems? Well, you could probably construct an electromechanical machine that did Diffie-Hellman. Konrad Zuse's Z3 computer was Turing-complete and program-controlled. It's entirely possible you could do it there. I have a mild raised eyebrow as the Z3 didn't have conditionals, but if you knew about Diffie-Hellman or RSA, I'm sure you could build a machine to do it. Of course, you'd have very short keys, but who cares, as everyone else only has electro-mechanical machines, too.

Could you do it with rotor machines? I don't know. My intuition is to say no. Remember that what we want to have with public key machines is a separate encrypt and decrypt key, and fast decryption aided by some trap door. Enigma was in many ways a mechanical puzzle in which electricity was bounced around, whereas the Lorenz machine is pretty recognizable as a modern stream cipher. I don't see a good way to turn those into public key systems.

For quite some time, we cryptographers have considered the possibility of symmetric ciphers that had some sort of back door in them. Some number of years ago, someone proved that if you have a symmetric cipher with a back door, then that is a trap-door function that can be used make an effective public key cryptosystem where the backdoor and its parameters are the secret key. (I'm sorry that I don't remember whose theorem that is.) Interestingly, this would be a public-key system that runs at the speeds of a symmetric cipher and very likely with a key that is small (compared to other public-key systems).

All our usable public-key cryptosystems are much, much slower than symmetric systems. They're often four or five orders of magnitude (or more) slower than symmetric systems of comparable strengths. So if you managed to find one of these, why would you waste it by releasing it as a symmetric cipher with a back door?

If you're an academic, you've invented something of mindblowing newness. It's an invention at least as powerful as the existing public key systems, and really much, much more interesting because it runs at symmetric speeds.

If you're in an intelligence service (like the CESG guys), you still have something amazingly powerful. Would you waste it? I say waste, because if you release this new cipher as a symmetric cipher, someone's going to figure out the back door eventually, even if that happens by a leak. Someone else will figure out that it's actually a usable public key cryptosystem and they will get the credit for it, not you. If and when it comes out that you knew it all along, then the way history will remember you is for this, and history is unlikely to be kind.

Moreover, this suggests that at the very least, making either a fast public key system or cipher with a backdoor is very hard. We've been trying for ages to get effective, new, usable public key cryptosystems and they're hard to do.

This means that if there is a way to make a rotor or electromechanical system that has a new public-key cryptosystem (one that isn't simply one of the ones we know now), we very likely don't know it. That suggests that they really couldn't have done it then. It's more likely tha they'd have done something like invent Diffie-Hellman or one of Merkle's puzzles or knapsacks and then implement that on electro-mechanical hardware.

So I would say that no, probably not. People in WWII probably could not have come up with something cool that isn't one of the systems we know about now.

Jon


Is power of non-negligible function non-negligible?

No and yes, depending on what do you mean by $n$.

Take $f(x)=1/2$ for example. It is a non-negligible function, but $g(x)=(f(x))^x=(1/2)^{x}$ is negligible, i.e. for every positive integer $c$, there exists an integer $N_c$ such that for all $x > N_c$,

$$|g(x)|<{\frac {1}{x^{c}}}.$$

If you mean a constant $n$, then $g(x)=(f(x))^n=(1/2)^n$ is non-negligible.


mutual authentication with pre-shared key

Typically, a preshared key itself is already mutually authenticated, i.e., you can simply use that key to encrypt and decrypt messages. The AUTH messages are not necessary and actually useless. However, here the mutual authentication does not imply that the public identities of both parties are explicitly authenticated, but depends on the authentication guarantees provided by the previous session that generated the pre-shared key. That is, direct use of a preshared key just guarantees the same two parties communicated before resume their session. More authentication procedures are required (e.g., each party signs a challenge message) to ensure explicit identity authentication, if it has not been guaranteed by the previous session.


Check out the videos from Art of Problem  there are some amazing videos on cryptography. Short and good visual ones they nail the point, am sure you would love them.


Different implementations of SHA1, which one is correct?

The echo command will include a newline at the end. So when you use echo 'Rosetta Code' | sha1sum you are actually hashing the string Rosetta Code\n.

Do the test using echo -n, the -n flag prevents the trailing newline character. Doing echo -n 'Rosetta Code' | sha1sum gives the same 48c98f7e5a6e736d790ab740dfc3f51a61abe2b5 hash that you were seeing elsewhere.


How to calculate the complexity of a meet-in-the-middle attack in terms of the key size k (Use big-O notation)

The meet-in-the-middle attack means that two successive encryptions using two different k bit keys do not give the security against a brute-force attack that you would expect from a 2k bit key.

Consider the case where you take your plaintext, encrypt it once with a $k$-bit key, and then encrypt it a second time with a second $k$-bit key.

You used a total of $2k$ bits of key; however this can be attacked with less effort than by simply trying all possible combinations of the $2k$ bits of key.

Blocks (a) and (b) try to talk about the complexity of how it is done; however they assume that you know the basic technique.  If you don't, well, that's probably what's confusing you (and block (a) talking about AES at one point and DES at another may well add to the confusion).

The basic attack is fairly simple; go through all possible values of the first $k$-bit key, and generate all possible first stage encryptions; go through all possible values of the second $k$-bit key, and decrypt the known ciphertext with that key, generating what had to be input to the second stage.  For the correct guess, the output of the first encryption had to be the input to the second, and so look for a match.  This is known as the 'meet-in-the-middle' attack; where you attack the cipher from both sides (and meet in the middle).


Yes, a ciphertext of a bulk encryption algorithm normally should not be compressible to less than the plaintext size¹ (at least, if the compression function does not know the encryption key), other than in some corner cases which will occur only with negligible probability (like you hitting the one plaintext which will encrypt to the all-zero-string).

¹Of course, if the encryption algorithm applies some encoding after encrypting which makes the ciphertext larger, like PGP's ASCII-armor, Base64 or Hexadecimal encoding, you can compress this resulting encoded ciphertext, but not to less than the original plaintext size. Similar things could occur with some asymmetrical encryption algorithms, which have slightly biased output, when (mis)used for bulk encryption - don't do this.

If the compressor knows the algorithm and key, it can simply decrypt the ciphertext and then compress the plaintext, of course.

With bad modes of operation, such as ECB mode, some repetitions in the plain text will also show through in the cipher text (see this famous example in Wikipeda), which then might show by compressibility of the ciphertext (the ECB image is bigger than the plain"text" one, but still smaller than the CBC one).

On the other hand, non-compressibility of ciphertext with generic compression algorithms is given by every not totally trivial encryption algorithm, even if they have to be categorized as broken by every aspect.


ECDSA signing and verification between Python and JS

It seems that the python library is actually re-hashing the hash you're passing it, since you are using the verify method of a VerifyingKey object, which is performing a hash computation on the data you're passing to it.
You might want to try passing the hash's pre-image to Python, or try hashing that hash again for JS, to have them interoperate...

You can also read this part about OpenSSL compatibility for Python's ecdsa lib.

I'm not really sure what secp256k1 library you are using for JS, but my answer assumes that the library is directly signing the data you're passing it, without hashing it first, or that the hash used by default by both library is not the same.


How to use RCON In Key Expansion of 128 Bit Advanced Encryption Standard

The Rijndael/AES key schedule uses (for every some steps, depending on the key size) a non-linear function (I called it $f_i$ in my schematic image in a related answer) on a 32-bit column:

This function $f_i$ (note that $i$ starts with $1$ here) does the following steps:

substitute each byte, using the AES S-box.
rotate the whole column by one byte "down" (these two steps can be swapped around without effect)
XOR in the round constant $RCON[i] = [x^{i-1}, \mathtt{00}, \mathtt{00}, \mathtt{00} ]$. The values $x^{i-1}$ are to be computed in the same representation of $GF(2^8)$ as used in all other operations in AES (see at the end on how to do this), but you can also take them from a table in the Wikipedia article, or from the examples in Appendix A of the AES standard.

As you see, $RCON[i]$ consists mainly of zeros, the only effective part is in the first byte. This means, this step only modifies the first byte of the column, the others are unaffected.

So, in your example, you have this column 3 of the original key:

[09]
[cf]
[4f]
[3c]

Now we rotate this by one:

[cf]
[4f]
[3c]
[09]

Now we put this through the AES S-box (component wise):

[8a]
[84]
[eb]
[01]

And now the round step: This is round 1, thus we need $RCON[1] = [\mathtt{01}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$:

[8a ⊕ 01]   [8b]
[84 ⊕ 00] = [84]
[eb ⊕ 00]   [eb]
[01 ⊕ 00]   [01]

This was $f_1$, and we'll now XOR this result with column 0 of the original key to obtain column 4 of the expanded key:

[8b ⊕ 2b]   [a0]
[84 ⊕ 7e] = [fa]
[eb ⊕ 15]   [fe]
[01 ⊕ 16]   [17]

After three more simple XOR steps to get column 5-7 we would then apply $f_2$ (which uses $RCON[ 2] = [\mathtt{02},\mathtt{00}, \mathtt{00}, \mathtt{00}]$) on column 7 and XOR the result with column 4 to get column 8, and so on.

The Rcon-array on Wikipedia contains the precomputed constants $x^{i-1}$ for $i$ from $0$ to $255$, so you would put $RCON[i] = [\mathtt{Rcon[i]}, \mathtt{00}, \mathtt{00}, \mathtt{00}]$. For AES-128, you only need the RCONs from $1$ to $10$ (as you need 44 columns of round key material), and here are these as a table (in hexadecimal form, as all constants in code font here):

   i        1     2     3     4     5     6     7     8     9    10
--------------------------------------------------------------------
          [01]  [02]  [04]  [08]  [10]  [20]  [40]  [80]  [1b]  [36]
RCON[i]   [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]
          [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]  [00]

For AES-192 and AES-256 you need even less of these round constants, so putting all 255 of them in Wikipedia is a bit superfluous. Even for Rijndael-256-128 (i.e. 256-bit blocks and 128-bit keys) we would need only $(14+1)·8/4-1 = 29$ of these.

As mentioned by fgrieu in a comment, you can also calculate the $\mathtt{Rcon[i]}$ on the fly, as each of them is obtained from the previous by an doubling in $GF(2^8)$, which in the representation used in Rijndael is just a left-shift followed with a conditional XOR with a constant. In C-like syntax (using a twos-complement representation like every usual computer nowadays) this looks like this:

rcon = (rcon<<1) ^ (0x11b & -(rcon>>7));

An explanation: (rcon<<1) is the pure doubling (multiplication by $x$ in $\mathbb{Z}_2[x]$). rcon >> 7 is the first bit of rcon, i.e. either $\mathtt{0}$ or $\mathtt{1}$. -(rcon>>7) then is $\mathtt{0}$ or -1 (= $\mathtt{f...ff}$, i.e. all bits set). Thus (0x11b & -(rcon>>7)) is either $\mathtt{0}$ or $\mathtt{11b}$, and XORing with this just is reduction modulo the Rijndael polynomial $x^8 + x^4 + x^3 + x + 1$.

The same doubling operation is used in the MixColumns-step of the actual encryption operation, so you need to implement it anyways.


Using an RSA private key simultanously as an AES encryption key to generate random numbers?

On a general and administrative basis, reusing the same private key for distinct usages is bad.

For this specific case, this should be fine (although you should use SHA-256 instead of SHA-1, if only for reasons of public relations: SHA-1 has bad press and any use of SHA-1 for a new design will be questioned), subject to the important caveat below.

The current date is a monotonous scale. However, your device does not have direct access to that physical value; it only has a clock which provides a discrete (it works by small increments, e.g. 1 second each) approximation of the current date. If you try to generate your AES key twice in the same second, and the "current date" changes only once per second, then you get the same seed, hence the same output, which can be bad. Also, more importantly, if the user (or attacker) can set the clock, then he can potentially enforce a seed reuse, leading to a PRNG sequence repeat. "Setting the clock" must be thought in a wide sense: an attacker who have the device in his hands may try to freeze or cook it, because quartz are sensitive to temperature. He may also play with the power input, e.g. adding a high frequency signal into it, on the hope that it would interact with the quartz and change its oscillating frequency. Possibilities are quite endless; the bottom line is that it is very hard for an embedded device to have an accurate, secure notion of the current time. Even getting a value which an attacker cannot force to repeat can be quite a challenge.

A more robust version would use a counter, which you increase every time you need a new AES key. Make sure that the counter is large enough that it cannot overflow (e.g. use a 64-bit counter). The counter must have permanent storage and never be reset throughout the lifetime of the device; you must also update the counter storage before using the counter value in the PRNG.

By the way, using the RSA private key as PRNG seed will not help you when it comes to actually generating the RSA private key itself. So either you generate the RSA private key externally and import it into the device (e.g. as part of factory initialization), or you have a problem. This might lead to another problem, depending on your exact situation: if a user can force the value of the RSA private key, then he can predict the PRNG output. You do not give information on your security model to know whether this can be an issue for you.


How to perform a parallel hash over a large file without changing the sequential hash result?

If you want to produce a hash compatible with an existing sequential hash, like SHA-2, you're out of luck. But when you choose a parallel mode, you can always compute the same output using a single thread.

The two most important parallel constructions are:

Interleaved

You initialize a fixed number of sequential hashes. Then you feed them one block in turn. At the end of the file you take the outputs of the individual hashes and hash it down into a single hash.

The biggest downside of this approach is that you need to choose the maximal parallelism at design time and changing it breaks compatibility. It still needs to process the file start to finish, it can only take advantage of multi-core CPUs but can't parallelize IO by hashing different parts of the file at the same time.
A (deep) Merkle-Tree.

For example the Tiger-Tree-Hash splits the file into 1 KiB and computes an unlimited depth binary hash tree over it. (Don't forget tagging leaves and inner nodes differently, or an equivalent mechanism to avoid ambiguities)

This has slightly higher CPU (a few percent) and memory (a few KB) overhead. It can only parallelize hashing files larger than the leaf size.

In exchange you can hash pieces independently in any order and the maximal parallelism grows with the file size.

Personally I prefer the tree approach due to its flexibility.

If you can use a key, you can use a PRF/MAC instead of a collision resistant hash. For example GHash (the MAC part of GCM) is very flexible in how it allows you to partition and parallelize the computation. It's also much cheaper to compute than collision resistant hashes.


Interesting problem. One should distinguish between two distinct cases, according as whether $p_1=p_2$ or not.

The case $p_1=p_2$ (let's call this common prime $p$) is easy. You can just subtract the two equations and get:
$$(a_1-a_2)x + (b_1-b_2) \equiv 0 \pmod p $$
which gives either a unique choice for $x$ (if $a_1\neq a_2$) or none at all (if $a_1=a_2$ but the $b_i$'s are distinct). In the former case, you can easily check whether that coordinate $x$ corresponds to an actual point on the elliptic curves; for randomly chosen curves, the chance of this happening is about 1/2. Note however that standard curve parameters often mandate that $a=-3$, in which case you are always in the latter case, and intersections simply don't occur for curves over the same base field.

The case $p_1\neq p_2$ is more subtle, because it isn't obvious how to interpret the question anymore. Mathematically speaking, the problem doesn't really make sense, because the fields $\mathbb{F}_{p_1}$ and $\mathbb{F}_{p_2}$ are distinct, unrelated objects.

One can look, however, for points $(x,y)$ with integer coefficients (or even, in some sense, rational coefficients), with the property that when reduced modulo $p_1$ we get a point on the first curve, and when reduced modulo $p_2$ we get a point on the second curve. Constructing such points is straightforward: take any point $P_1$ on the first curve, any point $P_2$ on the second curve, and apply the Chinese remainder theorem to their coefficients to get what you want. But this may not be the problem you are actually interested in, because if you do that, the bit size of the coefficients of the resulting point $(x,y)$ will be as large as the sum of the bit sizes of $p_1$ and $p_2$ in general.

One could also ask for such integer solutions $(x,y)$ with the additional requirement that, for example, $x$ and $y$ should be at most $\min(p_1,p_2)$ in absolute value (or perhaps $\max(p_1,p_2)$ depending on the application). This amounts to looking for points with small coefficients on the lifted curve
$$y^2 \equiv x^3 + \hat{a}x + \hat{b} \pmod {p_1p_2}$$
where $\hat{a},\hat{b}$ are obtained by Chinese remaindering. Heuristically, if $p_1$ and $p_2$ are roughly of the same size, say $m$ bits, such a point should exist with good probability (there are about $2^m$ possible $x$ coordinates of the right size, and at least one of the corresponding $y$ coordinates fall in the right interval with probability around $2^{-m}$; one can make this rough estimate more precise if necessary). It is not completely obvious how to find such a point, however. The usual technique to find small solutions of algebraic equations is to use some variant of Coppersmith's theorem, but depending on the precise version of the problem you are interested in, the bounds offered by Coppersmith are likely to be insufficient.

If you can say more about your precise application, one could have a closer look. It might even be worth writing a paper about it.


Using the same RSA keypair to sign and encrypt

The short answer is no. This is a general piece of wisdom in cryptography: never use the same key for more than one thing. A “thing” means a specific scheme where all the parameters are fixed apart from the key itself and the message size. Don't use the same key to encrypt and sign; don't use the same key with both PKCS#1v1.5 and PSS; don't use the same key with different hash functions.

If you use the raw RSA operation ($M^d \bmod n$ or $M^e \bmod n$), then no, it is unsafe to use the same key, because an attacker could trick the private key holder into signing a message $M$ (i.e. generating $M^d$) which is actually an encrypted message ($M = P^e$), thus allowing the attacker to recover the original plaintext ($(P^e)^d = P$). (The dual attack leads to a forgery.) However, the raw RSA operation has a whole range of other flaws that make it unsafe as an encryption or signature scheme.

Encryption and signature schemes based on RSA use padding modes. The standard padding modes include discriminants so that an encryption payload does not look like a signature payload. Therefore, it is technically safe, cryptographically speaking, to use the same RSA key pair for signature and encryption, provided that the key pair is used safely for signature and used safely for encryption. Here, I mean safe in a narrow sense, assuming a “perfect” world where everything that should stay secret, remains secret.

The thing is, the world is not perfect. Implementations of RSA can leak partial information through side channels. Keys get compromised. Protocols using RSA sometimes use it in ways that are very brittle.

Using the same key for both encryption and signature can exacerbates weaknesses. RSA has a history of weaknesses, not in the mathematical algorithm itself (once you use proper padding), but in the way it's implemented. Decryption, especially, requires a lot of care, because some inputs are invalid, and the mere act of revealing whether an input is valid or not can allow oracle attacks, the best known of which is due to Bleichenbacher. The way RSA decryption is used in TLS¹ exacerbates this because it creates a second reason for invalidity: a ciphertext can be invalid for the decryption operation, or can be valid for decryption but decrypt to something invalid. This has led to a long series of practical attacks against TLS cipher suites that use RSA decryption. Using the same key for both encryption and signature has two downsides. Most obviously, if a vulnerability in decryption allows the attacker to recover the key, then anything that relies on a signature is also broken. Less obviously, even if the attacker can't recover the key, but can get some partial information about the decryption of invalid ciphertexts, they may be able to forge signatures. This is the case, for example, with the CAT variant of Bleichenbacher's attack, so that even clients that do not accept RSA decryption ciphersuites are still at risk if the server uses the same key for RSA signature ciphersuites.

Another reason is key management. Signature keys and encryption keys have different requirements in terms of backups, access control, repudiation, etc. The fallback for a signature key in case of a catastrophic event is to destroy it to avoid future forgeries, so a signature key does not need to be backed up extensively. Conversely, the fallback for an encryption key is to keep it around to decrypt existing documents, so it needs to be backed up reliably. In case of a leak of a signature key, pre-existing documents are not affected; it is only newly produced signatures that must be repudiated. Conversely, in case of a leak of an encryption key, the confidentiality of all pre-existing documents is at risk, whereas new documents simply need to be encrypted with different keys. The constraints push in different directions, so the keys need to be managed differently, they need to be different.

¹  That is, ciphersuites whose name starts with TLS_RSA_. Ciphersuites whose name starts with TLS_(EC)DH(E)_RSA use RSA signature, not RSA decryption, and are a lot more robust.


The size we speak of with regard to elliptic curves is the size of the field over which the elliptic curve is defined. This is not necessarily exactly the size of the private key.

For example: Curve25519 is a 255-bit elliptic curve and has, effectively, 252-bit private keys, though they are usually encoded as 256-bit values with four fixed bits. Public keys are 256-bit values, but only contain 255 bits of information since the last bit is always 0.


They measure it.

Once upon a time, CPUs were simple enough that you really code compute the amount of time for a stretch of code by looking up the clocks per instruction in the manual, add them all together, and that'd be the total time.

However, CPU manufacturers have added more and more optimizations and parallelism; this makes the CPUs run faster (for example; using memory caches, executing instructions in a pipeline, executing instructions out of order), however it becomes increasingly difficult for someone to look at some code and generate an estimate.

So, instead of trying to deal with the complexity, we just measure it.


What are the different uses of MAC and Digital Signature?

A MAC is a form of symmetric or secret key cryptography. It uses the same key for signing and verification. It's fast and produces a small signature. Almost all algorithms are post-quantum secure.

A digital signature is a form of asymmetric or public key cryptography. It uses the private key for signing and the public key for verification. It's slow and produces a slightly larger signature. The popular algorithms get broken by quantum-computers and the replacements all have significant downsides like large signatures.


Why is the tweak length 64bit in BPS FPE algorithm?

From the paper:

  We denote by $f$ the number of output bits of the internal function $F$

and

  We first divide the 64-bit tweak $T$ into two 32-bit sub-tweaks $T_L$ and $T_R$

plus

  We denote by $L_i$ (resp. $R_i$) the left (resp. right) branch value after application of round $i$.

with the note

  Note that because of our restriction on the number of input $s$-integers, we always ensure that each branch can be coded on a $(f − 32)$-bit word.

Right, so now look at part of the definition of the cipher:

  ...

  $L_{i+1} = L_i \boxplus F_K ((T_R \oplus i) \times 2^{f −32} + R_i) \mod s^l;$

  ...

although multiplication is represented by a dot instead of $\times$. Similarly for the calculation of the state $R_{i+1}$ of course.

Basically, this shifts the tweak to the most significant 32 bits, leaving the rest for the state. Now $F$ can be AES, HMAC-SHA-2 or TDES. TDES has a block size of 64 bit. If the tweak size was 128 bit then there would not be any space left for $R$ or $L$ that make up the internal state.

So the tweak size is such that repetition of the tweak is unlikely and it can still be used efficiently when the encryption uses a 64 bit block cipher. If the tweak would be larger the construction would become less efficient, up to the point that the scheme would not work at all.


Rationale for NORX/Ketje/Keyak not being chosen for the CAESAR final portfolio

This is an interesting question ,  here are some main points to identify major differences between Caesar winners and above-mentioned algorithm

Background

Norx is LRX- Duplex based authenticated encryption scheme designed
for lightweight and high-performance use cases.
Ketje is Keccak-f-Duplex based authenticated encryption  scheme  designed for lightweight (except Ketje Major for high performance)
Keyak is Keccak-f-Duplex based authenticated encryption  scheme  designed for high-performance (except River Keyak for lightweight)
The winners of Lightweight use case are Ascon (SPN-duplex based authenticated encryption cipher and Acorn (stream based authenticated encryption).
The winners of high-performance case are AEGIS (AES-Block cipher authenticated encryption), OCB (AES-XEX authenticated encryption)  and  MORUS (LRX-stream cipher )

Performance

A hardware benchmark on Virtex6 , Virtex-7 and Straix-IV shows the Acorn and Ascon have the lowest Area/$A_{GCM}$ compared to Norx , Ketje and Keyak (0.16 and 0.4 on average).
The hardware performance in term of throughput/ Area and throughtput/AES-GCM throughput for AEGIS and MORUS across Virtex6 , Virtex-7 and Straix-IV are very high compared to OCB , Ketje , Norx and Keyak.
The software performance in this chart shows the , AEGIS, OCB and MORUS have lower cycles per bytes (higher performance ) compared to Ketje , Norx and Keyak.

Security

A paper presented in FSE 17 (cryptanalysis of NORX2) concluded Almost practical forgery and key recovery attack on NORX v2.0.

Further Details

ATHENa project is hardware benchmark of Caesar candidates
eBACS: ECRYPT Benchmarking of Cryptographic Systems

PS:Iam happy to see if someone provide more selection rationals.


Definition of perfect secrecy using ciphertext

I think they are similar but not equivalent.

The first condition says that for any ciphertext $c$ all messages $m$ have equal probability to encrypt to $c$. The second says that for any message $m$ all ciphertexts $c$ have equally probability of encrypting $m$.

So I think you can demonstrate non-equivalence as follows:

Imagine a (somewhat contrived) scheme satisfying the first condition but not the second: The scheme has two disjointed sets of ciphertexts $C_0$ and $C_1$. Concretely, consider one-time-pad where keys and ciphertext contain one extra bit, simply indicating if we are in $C_0$ or $C_1$. Now, assume we pick the extra bit to be 0 with probability 1/3 and 1 with probability 2/3.

Now if $c \in C_0$ and $c' \in C_1$ it is clearly not the case that
$$
Pr_{k \leftarrow Gen}[Enc_k(m) = c] = Pr_{k \leftarrow Gen}[Enc_k(m) = c']
$$
because the probability that $Enc_k(m) \in C_1$ is twice as big as $Enc_k(m) \in C_0$.

Alternatively, I think you can show that condition two implies condition one. I.e. condition one is more general than condition two.


Does EAX use the same keys for encryption and authentication?

The same key is indeed used in EAX to key both the CTR mode and the underlying OMAC (which is actually used in 3 distinct phases: randomising the CTR nonce, authenticating the Additional Authenticated Data, and authenticating the Ciphertext). This is explicitly acknowledged in the security proof.

Where EAX differs from a naive reuse of the key is that it initialises each use of OMAC with a distinct parameter, and initialises the CTR mode cipher with one of the OMAC outputs, effectively randomising that as well. The security proof of this single key approach is (to quote the authors) "novel and involved" and "surprisingly complex", but seems to have stood up to peer review.

It's worth noting that in the EAX paper, 3 modes are actually defined:

EAX2 is a general composition method for combining a cipher and a MAC to produce an authenticated cipher using two keys Key1 != Key2.
EAX1 is a composition of EAX2 with one Key == Key1 == Key2
EAX is a composition of EAX1 with CTR and OMAC

The security proofs in the EAX paper are provided for EAX2 and EAX, but not EAX1 (the proof of EAX relies on the properties of OMAC, and so doesn't extend to general use of EAX1).

The lengths of the Ciphertext and AAD are not explicitly handled in EAX, which allows EAX to operate as an online mode (processing data as it arrives without buffering more than one block).
The authentication in EAX is simply processing the entire sequence of AAD and Ciphertext with OMAC, and the security proof for that (and any other secure MAC) naturally excludes any message extension attacks - any message extension resulting in the same MAC would be a forgery, and instantly invalidate the scheme as a secure MAC.

CTR mode has to handle incrementation of the nonce/counter value in any implementation - the starting value of the counter is arbitrary (and in the case of EAX pseudo-random). This isn't difficult (BouncyCastle for example does it in one line of code).


Is it possible to construct a $3*3$ MDS matrix in $GF(2^4)$?

A matrix $M$ of order $n$ is an MDS (Maximum Distance Separable) matrix if and only if every sub-matrix of $M$ is non-singular. Therefore, if you have an $n\times n$ MDS matrix $M$, constructing the $(n-1)\times (n-1)$ MDS matrix $M'$ is so easy. $M'$ can be constructed by choosing an arbitrary $(n-1)\times (n-1)$ sub-matrix of $M$. Here you can find some information about constructing the MDS matrices over $GF(2^q)$.


ElGamal Signature Scheme: Recovering the key when reusing randomness

That looks about right.  Assume we have two messages $m_1$ and $m_2$ and the corresponding signatures $(r,s_1)$ and $(r,s_2)$ generated using the same $k$ (where $r=g^k$ is thus the same for both signatures).

If we could assume that $s_1 - s_2$ and $r$ were invertible modulo $p-1$, we could simply compute

$$ k \equiv (m_1 - m_2)(s_1 - s_2)^{-1} \mod p-1 $$

and then

$$ x \equiv (m_1 - ks_1)r^{-1} \mod p-1. $$

Of course, that's not necessarily the case, but we can still first solve the congruence

$$ k(s_1 - s_2) \equiv (m_1 - m_2) \mod p-1 $$

for $k$, check which of the $\gcd(s_1-s_2,p-1)$ solutions yields the correct $r = g^k$, and then solve

$$ xr \equiv (m_1 - ks_1) \mod p-1 $$

for $x$ and check which of the $\gcd(r,p-1)$ solutions gives the correct $y = g^x$.

Note that, in the ElGamal signature scheme, the only operations done modulo $p$ are the exponentiations (and the final multiplication $y^r \cdot r^s$ in the verification step); everything else is done modulo $p-1$.

This makes sense when you realize that we're really working in two distinct $(p-1)$-element algebraic structures: the ring of integers modulo $p-1$ and the multiplicative group of integers modulo $p$.

We may usefully view the latter of these as a module over the former, with exponentiation as the "scalar multiplication".  Also, since the two structures have the same number of elements, we can identify the canonical (i.e. least non-negative) representations of their elements simply by identifying 0 with $p-1$; this is what we do implicitly during signature generation, when we first calculate $r = g^k \pmod p$ and then use it to calculate $s$ modulo $p-1$.

(Actually, the case $r = p-1$ is impossible anyway, since it would imply that $r^2 \equiv 1 \pmod p$, and thus that $2k \equiv 0\pmod{p-1}$, and so $\gcd(k,p-1) \ne 1$.  The case $r=1$ can be similarly ruled out, so we always have $1 < r < p-1$.)


What is the relation between hash chaining and chosen prefix attack

Hash chaining does not itself prevent hash collisions.  It sounds like you might have walked away with the wrong lesson from your reading.  You might want to read about the Merkle-Damgaard construction, which takes a collision-resistant compression function (for fixed-length inputs) and shows how to extend it to a hash function (for variable-length inputs).  Note: to prevent collisions, you need the compression function to be collision-resistant, and you need to use a proper chaining scheme.

Most modern hash functions, including MD5, use Merkle-Damgaard or some other chaining scheme.  Obviously, in the case of MD5, it doesn't prevent the chosen-prefix attack on MD5.


Selection of rotation constants in ARX design

Leaving besides that the designers (NSA) of Simon and Speck did not provide an initial design rational for their ciphers/parameter choices, they added some notes later after pressure from the cryptographic community/ISO. There they mention that they selected the round constants to be

  ... optimal with respect to resistance against 8-round differential and linear attacks...

and

  ...many of these led to poor performance on software devices (especially
  8-bit microcontrollers) and so were rejected...

There are some other ARX ciphers like for example Chaskey and MergeMAC who argument the choice of the round constants with

  ... our choice of constants, implementation on 8- and 16-bit
  microcontrollers will be more efficient than had these constants been
  chosen at random ...

and

  The rotation constants in our permutation are chosen to be optimal for
  microcontrollers which often only allows efficient rotations/shifts by
  one or two bits, and byte-permutations by 8-bits.

So one of the reasons for the choice of rotation parameters is that they are optimal for implementations.

Another point for choosing the rotation parameters comes from a security point of view regarding differential/linear attacks. The non-linearity of ARX ciphers only comes from the modular addition. If we look closer into modular addition, we can see that the non-linearity actually just stems from the carry propagation (more details i.e. here), as the sum is simply just an XOR (which is linear).
In general, for ARX ciphers the best rotation constants would shift a
difference to a position where it reaches the msb last (as a difference
in the msb is not counted in the calculation for the probability).
Therefore, one can ensure that the differences quickly build up and are
not canceled out.

Moreover, regarding the rotation constants for Speck, the designers of the block cipher Sparx mention in their paper

  While it is possible to choose the rotations used in Speckey in such a
  way as to slightly decrease the differential and linear bounds, such
  rotations are more expensive on small microcontrollers which only have
  instructions implementing rotations by 1 and by 8 (in both directions)

and they also provide the different rotation constants that actually would improve the differential/linear bounds of Speck (for the cost of less efficiency):

  Both can be lowered by a factor of 2 if we choose rotations
  (9,2),(9,5),(11,7) or (7,11) instead of (7,2).

The size of the plaintext influences the choice of round constants indirectly, as one would have to choose a constant such that it is obviously between 1 and the wordsize = plaintext size/number of branches. This is because a rotation of 0 won't change anything and a rotation large then the wordsize would just be the same as a rotation modulo the wordsize.


Bounding security of password authentication given entropy

Optimizing attacker's success probability constrained by $H$ and number of passwords

Let's tweak the notation a little bit to make it less cumbersome: the passwords the adversary tries have probability $p_i$ for $0 \leq i < n$, and the passwords the adversary doesn't try have probability $q_j$ for $0 \leq j < m$.  The adversary succeeds with probability $\sum_i p_i$.

We seek an extreme point of $f = \sum_i p_i$ among the zeros of $g$ and $h$ where
\begin{align*}
  g &= H + \sum_i p_i \log p_i + \sum_j q_j \log q_j,
    &&\text{entropy constraint;} \\
  h &= 1 - \sum_i p_i - \sum_j q_j,
    &&\text{total probability constraint.}
\end{align*}
These extreme points are zeros of $$d(f - \lambda g - \mu h) = df - g\,d\lambda - \lambda\,dg - h\,d\mu - \mu\,dh$$ for Lagrange multipliers $\lambda$ and $\mu$.  Since $$d(x\log x) = \log x\,dx + x\cdot(1/x)\,dx = (1 + \log x)\,dx,$$ we have
\begin{align*}
  df &= \sum_i dp_i, \\
  \lambda\,dg &= \lambda\,dH + \sum_i \lambda (1 + \log p_i)\,dp_i + \sum_j \lambda (1 + \log q_j)\,dq_j, \\
  \mu\,dh &= -\sum_i \mu\,dp_i - \sum_j \mu\,dq_j.
\end{align*}
Thus if $dH = 0$ while $dp_i$ and $dq_j$ are nonzero (we hold $H$ fixed but allow the probabilities to vary), we obtain from $0 = d(f - \lambda g - \mu h)$ the system of equations
\begin{align*}
  0 &= 1 - \lambda (1 + \log p_i) + \mu, \\
  0 &= -\lambda (1 + \log q_j) + \mu,
\end{align*}
and from $g\,d\lambda = 0$ and $h\,d\mu = 0$ we get the entropy and total probability constraints as before.  Since $\log$ is injective, this system implies that the $p_i$ are all equal, and the $q_j$ are all equal; call the common values $p/n$ and $q/m$, respectively.  From the total probability constraint, we have $p = 1 - q$.  The entropy constraint reduces to $$H = -p \log (p/n) - (1 - p) \log [(1 - p)/m].$$  The adversary's success probability $p$ must be optimized by minimum/maximum uniform probability mass distributed to the first $n$ passwords consistent with this entropy constraint.  There are two solutions, because $H$ is increasing for $p < n/(n + m)$ and decreasing for $p > n/(n + m)$, corresponding to the attacker's minimum and maximum success probability.

Inverting $H$ is tricky, but we can approximate it in this case without too much trouble.  Let $n = 1000$ and $m = 2^{48} - 1000$ as in the question.  For the minimum value of $p < n/(n + m) = 1000/2^{48}$, we might use the approximation that $\log (1 - p) \approx 0$, so that
\begin{align*}
  H &= -p \log (p/n) - (1 - p) \log [(1 - p)/m] \\
    &\approx -p \log (p/n) + (1 - p) \log m \\
    &= \log m - p \log (p/n) - p \log m \\
    &= \log m - p \log (p m/n).
\end{align*}
To solve this, let $W(x e^x) = x$ be Lambert's W function.  Suppose $y = x \log (a x)$; then $e^y = e^{x \log (a x)} = a x e^x$, so that $e^y/a = x e^x$, from which $x = W(x e^x) = W(e^y/a)$.  Thus, since $\log m - H \approx p \log (p m/n)$, we can recover $p \approx W(e^{\log m - H}/(m/n)) = W(e^{-H} n)$.  For $H = 20 \log 2$ so that $e^{-H} = 2^{-20}$, we get $$p \approx W(2^{-20} \cdot 1000) \approx 0.000952766 > 2^{-11}.$$  For the maximum value of $p > n/(n + m)$, we can use bisection on the decreasing function $H$ (on a range much more amenable to naive numerical computation) to find $$p \approx 0.757204 < 4/5.$$  Thus, $$2^{-11} < p < 4/5.$$

Multi-user setting

Suppose Alice, Bob, etc., all use the same distribution on passwords.  If there are $u$ users, the adversary's probability of success at breaking at least one of the $u$ users with the $i^{\mathit{th}}$ password is given by $\hat p_i = 1 - (1 - p_i)^u$.  This is the complement of the probability that every user picked a password other than $P_i$.  The adversary's probability of success after trying the first $n$ passwords is $\hat p = 1 - (1 - \sum_i p_i)^u$.  To optimize this, we simply replace the objective $f$ in the above procedure by $f' = 1 - (1 - \sum_i p_i)^u$.  We obtain the modified system of equations
\begin{align*}
  0 &= u \bigl(1 - \sum\nolimits_\iota p_\iota\bigr)^{u-1} - \lambda (1 + \log p_i) + \mu, \\
  0 &= -\lambda (1 + \log q_j) + \mu,
\end{align*}
which as far as I can tell doesn't change the extreme points, only the value of the adversary's success probability at those points.  Suppose $u = 2^{10}$; then since $2^{-11} < p < 4/5$,
\begin{gather*}
  1 - (1 - 1/2^{11})^{2^{11}} \approx 1 - e^{-1} \approx 0.63212 \\
  1 - (1 - 4/5)^u = 1 - (1/5)^{2^{10}} \approx 1,
\end{gather*}
so we have $$1/2 < \hat p < 1.$$
That is, the adversary's probability of success in a multi-target attack guessing a thousand passwords out of $2^{48}$ possibilities with 20 bits of entropy for any of a thousand users is guaranteed to be better than a fair coin toss coming up heads, and may be essentially 1.  Note that this multi-target attack still costs $n\cdot u$ queries, just like the single-target attack costs $n$ queries (unless the password database is amazingly badly designed).  In this case, it costs $2^{20} \approx 10^6$ queries.

Addendum: If number of passwords is unbounded then entropy is unbounded for any success probability no matter how close to 1

Fix $0 < \varepsilon < 1$.  Let $p_0 = 1 - \varepsilon$ and $p_i = \varepsilon/m$ for $i = 1, 2, \ldots, m$.  The Shannon entropy of this distribution is
\begin{align*}
  H &= -(1 - \varepsilon)\log(1 - \varepsilon) - \sum_{i=1}^m (\varepsilon/m) \log(\varepsilon/m) \\
    &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log (\varepsilon/m) \\
    &= -(1 - \varepsilon)\log(1 - \varepsilon) - \varepsilon \log \varepsilon + \varepsilon \log m.
\end{align*}
If $\log m$ is unbounded above, so is $H$.

The adversary's chance of success at a single guess, trying the first password with probability $p_0$, is $1 - \varepsilon$, which can be made arbitrarily close to 1, while the Shannon entropy of the whole distribution is made arbitrarily high, by adding more equiprobable passwords other than the first one.

What this counterexample demonstrates is that for any Shannon entropy, the probability of success after the first trial can be made arbitrarily close to 1.  On the other hand, the min-entropy of this distribution is $-\log (1 - \varepsilon)$, no matter how many other choices there are.

In general, if the min-entropy of the distribution on passwords is $H_\infty$, then the best chance of success at a single guess is $e^{-H_\infty}$.  If the min-entropy of the distribution on passwords given that it is not the first one is $H'_\infty$, the best chance of success at a single guess after the first one is $e^{-H'_\infty}$, so the best probability of success after two trials is $$\Pr[T_0] + \Pr[T_1 \mathrel| \neg T_0] \Pr[\neg T_0] = e^{-H_\infty} + e^{-H'_\infty} (1 - e^{H_\infty})$$ and so on, where $T_0$ means success after the first trial, $T_1$ means success after the second, etc.  In the uniform case, this reduces to a hypergeometric distribution as one might expect.


I give an answer summarizing and precising the comments you provided.

  Being invertible in $\mathbb{Z}_{n }$ is equivalent to having some power equal to 1.

If $b$ is invertible there exist $b^{-1}$ and as we are working in finite groups in the sequence $1,b,b^2,...,b^n$ there must be repetitions, let's say $b^i = b^j$. Then using the existence of $b^{-1}$ we have that (assume $i > j$) $b^{i-j} = 1$ so for power $i-j$ we have 1 modulo n.

If we have some power that is equal to one, say $b^x$ then we can take $b^{-1} = b^{x-1}$

Now, in Fermat's test we pick $b$ in $\{1,\cdots,n-1\}$ and going wrong means that in fact $b^{n-1} = 1$ so that $b$ must be invertible. Therefore, the total number or wrongs $W$ must be bounded by $\phi(n)$. The probability of going wrong in k attempts is therefore $\big(\frac{W}{n-1}\big)^k \le \big(\frac{\phi(n)}{n-1} \big)^k$ assuming independence.

As fgrieu pointed out this is only an upper bound which is an equality if number $n$ has the particularity that every invertible $b$ verifies $b^{n-1} = 1$ so that $W =  \phi(n)$. These funny numbers are Carmichael numbers.


Injecting salt into PyCrypto KDF - useful?

Identical passwords will still get unique PBKDF2 hashes given a unique salt, regardless of which mechanism you use.

I don't think explicitly adding the salt improves the security of this scheme. The designer PBKDF2 have already considered and solved this problem. There is no need for you to try to duplicate their efforts.

I think it's safer to use the well tested and well understood construction of PBKDF2:

dv = PBKDF2(password, salt)


Finding an x such that xP = (11,44) on an elliptic curve

As mentioned by Thekwasti, what you want here is compute a discrete logarithm, but while it is true that in general computing discrete logarithms is "hard" (which is why they are used in cryptography), in your case the group is small enough to make even a brute force search completely feasible. So the goal of the exercise is probably to make you implement at least one of the following algorithms:

Brute force search
Shanks's "baby step, giant step"
Pollard's rho

You will normally find that they are in increasing order of efficiency (although here the group is so small that the difference might not be noticeable).


Multi-prime RSA is simply using more than 2 prime numbers in generating RSA public key - The public modulus would have more than 2 factors.

We use it because it has more efficient key-generation and decryption/signing operation, which is the benefit of it.

The downside being it might be easier to factor a multi-prime RSA public key than a dual-prime one.

It's neither recommended or recommended against, it's simply an possible option without any endorsement.


Are parts of a pseudorandom string also a pseudorandom string?

If you have a stream, $s$, of $n$ bits that is computationally indistinguishable from random, then any truncation of that $n$ bit string must also be indistinguishable from random.

The proof of this is straightforward. If $s$ was computationally indistinguishable from random, but some truncation of $s$ was not then we could distinguish the larger sequence from random by enumerating all possible truncations of $s$ and testing them against the distinguisher.

If the distinguisher identifies that any truncation is not random, then this demonstrates $s$ is not random. It acts as a distinguisher on $s$. Obviously, that is a contradiction.


How to choose constants in a cryptographic function?

There are some approaches.

In many algorithms it for the security doesn't really matter what constant is used, as long as it is not too simple, like initialization vectors for hash functions. (And of course, we need to use always the same number.) Then mathematical constants like binary expansions of irrational numbers like $\sqrt{2}$ (or roots of other numbers), $e$, $\pi$ can be used, to show that one didn't select the numbers to create a back door. This is known as a nothing up my sleeve number, the linked Wikipedia article contains some more examples.
The padding constants for HMAC, 0x36 for ipad and 0x5C for opad, are repeated (for the hash function's block size) and XORed with the key to generate the prefixes for the two hashing steps. 0x36 = 0b00110110 and 0x5C = 0b01011100 - these two values are about "as different as possible", to avoid any attacks which rely on a similar hash state after the key block for inner and outer hash. This is mainly a heuristic, as far as I understand.
In the DES S-boxes, the constants were randomly generated and then tested for resistance against differential cryptanalysis. As differential cryptanalysis was not yet known officially, and NSA didn't explain what they did (one only could see that they gave it back with other S-boxes), there was quite some suspicion that they put in a backdoor, while they actually made the algorithm harder to break.
In AES, the S-boxes are an implementation of a simple mathematical function (inversion in $\mathbb F_{2^8}$, followed by a linear transformation). One wouldn't need an S-box here, it just helps to efficiently implement it.
In the hash function Skein (one of the SHA-3 candidates), the initialization vector (initial state of the iteration) is not a fixed arbitrary number, but is gained by hashing a "configuration vector" (where we use 0 as init state). If one uses Skein only in common uses (e.g. a simple hash), i.e. always with the same configuration, one can hardcode the resulting hash state into the implementation instead of re-running it each time.


AES - CCM, why not use CMAC inside instead of CBC-MAC?

So in their original suggestion of the mode for 802.11i (for WPA2) the only reason given by Whiting, Housley and Fergueson is:

  A combination of counter mode  encryption  and  CBC-MAC authentication is proposed here. These modes have been used and studied for a long  time,  with  well-understood  cryptographic  properties,  and  no  known  patent  encumbrances.  They  provide  for  good security and performance, whether implemented in hardware or software.

So they probably were mostly looking for a mode that satisfied their specific needs at the time (no patents, reasonably fast and cheap, with security proof) and so they came up with this relatively simple construction.

Furthermore, "CMAC" is actually OMAC1 (first definition (PDF) from 2003) which is based upon OMAC(2) (from december 2002) which is based upon XCBC (from 2000, PDF) which is based upon CBC-MAC.
So as the CCM specification is from January 2002, it obviously couldn't make use of OMAC / CMAC. Furthermore XCBC was known at the time, but had the problem of requiring 3 keys which would have bumped the key size for CCM from 128 bit for AES-128 to at least 384 bit, probably an undesirable result.

  But if CMAC is more robust, why not just use this one?

So I looked through the specification and CMAC actually isn't more robust. CBC-MAC by itself is a prefix-free PRF (and thereby a MAC). So if you don't allow sequences of message blocks to be prefixes of each other you get a secure MAC.

The way this weakness is overcome in CCM is that the length of the message is encoded into the first input block to CBC-MAC so no two messages of different length can be prefixes to each other because the initial block will always differ.
The way CMAC overcomes this is by XORing a constant secret into the last input block, so that an adversary doesn't actually know the complete input to CMAC and thereby can't find any prefixes without guessing the secret key-dependent constant.

So as you can see, security-wise both CCM's CBC-MAC and CMAC are rather equivalent in their properties. The only downside is that with CCM you need to know the message length in advance which sometimes is inconvenient.

Bonus: I actually think the prepending of the message length is unncessary for CCM. This is because CCM already needs a nonce-respecting adversary for security (or else the CTR component breaks horribly), so it's guaranteed that the first block is different for each CBC-MAC invocation and thereby no two inputs can be prefixes of each other.

Also note that the more popular GCM breaks at least as badly as this CCM variant since it leaks the secret authentication key in that case...


What do you call one time pad where pseudo-random numbers are used?

Synchronous stream cipher, or just stream cipher.

  In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, and then combined with the plaintext (to encrypt) or the ciphertext (to decrypt). In the most common form, binary digits are used (bits), and the keystream is combined with the plaintext using the exclusive or operation (XOR). This is termed a binary additive stream cipher."

http://en.wikipedia.org/wiki/Stream_cipher#Synchronous_stream_ciphers


Fast Symmetric Encryption Algorithms: My Options

AES-GCM can be used as it provide Authenticated Encryption, no need to separately calculate MAC as the same same algorithm does that in parallel.This is hardware efficient.

For software you can use ChaCha(which is a Salsa variant stream cipher) along with Poly1305 , this combination also provide AEAD.


How does the probabilty for universal hashing work out?

Actualy chance of 2 dice throws to have the same value is 1\6, not 1\36. And definition also compares 2 values.
What you are asking is called https://en.wikipedia.org/wiki/Birthday_problem and it is still present even with universal hashing. Or dice throws. If more than 2 are compared.


Does pseudorandom secret sharing require a central dealer?

In secret sharing, one person typically wants to share a secret. Only that one person knows that secret, so they are the dealer.

In MPC, which VIFF implements protocols for, you actually have multiple parties, each with a secret input(s). So, each of these parties is the dealer for their individual secret input(s). In this sense, there is no central dealer for the entire computation.


In 2020, SHA-1 practically broken in chosen-prefix collision (CP-collision). Can double SHA-1 hashing prevent CP-collision?

a. No such double hashing doesn't do a bit of good. Anything which collides after a single hash will definetly collide after a double hash. It preserves all collisions and adds new ones.

We might consider other constructions which may provide some strength e.g $H(H(m) || m)$ however:

b. We have no need for any such double hashing of SHA1 as we have newer better hash functions. Most notably we have SHA3 which is by all accounts far from being broken


Why would this method of discrete logarithm finding not work?

The flaw in your reasoning lies in your assumption that finding the discrete log of $f$ is any easier than finding the discrete log of $g$.  It just isn't.  That assumption is not correct.  And if you try to recurse and apply your procedure to $f$, you'll recurse for a very long time, and your algorithm will take exponentially long.

Let me summarize your algorithm: to find the discrete log of $g$, you suggest we  pick some specific power of $b$, say $e \equiv b^3 \pmod p$, then compute $f \equiv g/e \equiv g b^{-3} \pmod p$, then somehow magically find the discrete log of $f$.  The problem with this algorithm is that "magic" doesn't exist.  If you want to find the discrete log of $f$, that's every bit as hard as finding the discrete log of $g$.  So the "factoring" hasn't helped you one bit.

I imagine you're going to be tempted to respond "but I just recurse, and apply my method recursively to $f$!", so let me proactively explain why that ain't gonna work: first, you have not identified any base case, so your recursion never terminates; and second, if you identify a reasonable base case (e.g., if $g$ is a perfect power of $b$, stop immediately), you'll find that you will need to recurse an exponential number of times, so the running time of your algorithm will be worse than brute-force search.

There is no known reduction that proves that the discrete log is as easy as factoring.  Lots of people have tried to find one, and failed.


how to validate cert when signed cert has authority key id but signing cert doesn't?

The subject key identifier is not used for validation, it is merely used to help in path building.

Please see RFC 5280 section 4.2.1.2 for more details.

Edit: Use of key identifiers in certificate path building is detailed in RFC 4158 section 3.5.12


Can TweetNaCl box sender's private key be set to "1" without privacy loss?

It is possible to decrypt the message using either the receiver's private key together with the sender's public key or using the sender's private key together with the receiver's public key. This means that if either private key is public, you end up with a completely broken system.

What you should do instead, is generating an ephemeral key-pair for the sender and sending the public part of it alongside the message. This essentially turns crypto_box into ECIES.

Using the same keypair for both sender and receiver is possible in principle, but silly, because then you end up with symmetric authenticated encryption and you should use the cheaper crypto_secretbox function instead.

Note that you need to know the shared key to verify, which at the same time allows forgeries. So this is typically only a workable solution if you have at most two parties. When you need a party who can verify but not sign, you should use a signature scheme instead. NaCl includes Ed25519.


Is signing a hash instead of the full data considered secure?

This is secure, and a lot of systems actually do signatures this way (for example, PGP). One reason to do this for performance. Signing a hash is much faster than signing your whole message. It is also non-trivial to hash large messages since signature functions usually operate on a bounded size input.

An attacker will have just as much difficulty forging a signature on the hash as they would forging the signature on the message itself.


Is order of Correlation Immunity of AES S_box Zero?

The Siegenthaler result is for boolean functions, i.e., $f:F_2^n\rightarrow F_2$, while you are considering vectorial boolean functions $$f:F_2^n\rightarrow F_2^n$$ so you can't apply it. The results in this area are quite technical. Some overview:

You could certainly compute resilience (hence correlation immmunity for AES Sbox) by using the definition that the resilience of a vectorial boolean function $$S:F_2^n\rightarrow F_2^n$$ is the minimum resilience of the boolean functions as $b$ ranges over the nonzero vectors in $F_2^n.$ So $$\min\{ \rho(b\cdot S(x)): b \in {F_2^n},b\neq \mathbf{0}\},$$ where $\rho(\cdot)$ denotes resilience of a boolean function. So you need to check $255$ boolean functions, since $n=8.$
There are some constructions in this area, I suggest you look at the draft of a chapter by Claude Carlet on vectorial boolean functions (especially the last section) available at his homepage. You may also find his chapter on boolean functions interesting, in terms of more basic definitions.

Edit: To clarify 1, let the output bits be $S_i(x)$ for $i=1,\ldots,8.$ Compute the correlation immunity of each nonzero bitwise linear combination of these functions, such as those of weight 1: $$S_1(x),S_2(x),\ldots,S_8(x),$$ weight 2:
$$S_1(x)+S_2(x),S_1(x)+S_3(x),\ldots,S_7(x)+S_8(x),$$
up to weight 8. This will give you 255 functions. The minimum correlation immunity of this collection of 255 functions is the correlation immunity of the AES Sbox.

Finally the correlation immunity of a boolean function is equal to the largest hamming weight $w$ for which all hadamard coefficients $\hat{f}(\lambda)$ for $\lambda$ with weight $1,2,\ldots,w$ are all zero.


I don't think an algorithm like that would exist. For PoW to facilitate a random slot leader for block generation, it has to be necessary that the PoW puzzle is really hard to solve by anyone and that no deterministic polynomial time algorithms exist which promise a solution to that puzzle, because if they would then I think that a person with a faster rig and a faster processor would solve the PoW puzzle the fastest and become the slot leader every time.
Since I have already stated that there shouldn't exist any deterministic algorithm to solve the puzzle in polynomial time, this means that the best that anyone contending for becoming the slot leader can do is to try the probabilistic approach and wish that their random nonce solves the puzzle faster than anyone else. It is just because of this randomized (probabilistic) nature of the solution to the puzzle that the very slot leader elected is random in nature.
If you know about complexity classes of P and NP, then you will realize that if PoW is linearly solvable then it lies in P, whereas it should lie in NP i.e. given an oracle which takes all the correct steps and makes all the correct choices (meaning that selects the random nonce correctly every time) every time, then the problem is polynomial time. This means that given a solution, you can verify that the nonce is correct in polynomial time but you cannot solve the puzzle in polynomial time.


Short answer: Use bcrypt.

Long answer:

First, "hashing a password with the password" is an undefined statement. Regardless, you are well into "inventing your own crypto" territory. Assuming you mean something along the lines of SHA-256(password + password), this is a phenomenally bad password digesting scheme. Being unsalted, your approach is vulnerable to rainbow attacks. Not using key stretching, your approach is vulnerable to brute forcing with GPGPUs.

BCrypt is vulnerable to none of these. It uses cryptographically random salts, ensuring that duplicate passwords do not hash to the same value. And it requires a significant amount of work to be performed by an attacker in order to generate each hash, requiring tens to hundreds of thousands of times more computation per password attempt.

Edit: In the comments, it was clarified that the meaning was something along the lines of SHA-256(password + SHA-256(password)). This is susceptible to precisely the same attacks: identical passwords hash to identical values, which is a serious flaw. And again, hashing is fast. Fast enough to brute force a huge number of your passwords, if given your password database. Real key derivation functions significantly increase the cost of brute forcing past the point where it's no longer a practical attack vector.


When is it appropriate to use HMAC? If I'm encrypting files on my local computer? If I'm encrypting and syncing files to a server? If I'm sending messages to Bob? When is it not needed?

I think the best answer here is that you're mixing levels of abstraction.  Since you've been reading Ferguson et al's book, I would refer you to their material on the concept of the secure channel—an API that provides concepts at a level more appropriate to scenarios that you are describing here (even though the one they show may not ideal for all of them).  Indeed, in their book HMAC is applied in the context of how to implement a secure channel so that clients that need secure communications don't have to think about HMAC (or nonce reuse or anything of the sort).

The second point is that two of the big, hard-learned lessons of the past 20 years are:

The importance of authenticated encryption;
How easy it is to get it wrong!

So another answer to your question is that, by default, you should be using authentication everywhere unless you can prove that you don't need to.  That doesn't mean use HMAC specifically (again, you're mixing levels of abstraction!), but it does mean that nearly all encryption really ought to be authenticated encryption, and that it should not be ad hoc—it should be a well-studied construction, from a well-audited library function.

Some good reading:

http://blog.cryptographyengineering.com/2012/05/how-to-choose-authenticated-encryption.html
Why should I use Authenticated Encryption instead of just encryption?


Given a particular $1600$-bit output $Y$, is it feasible to find a $1600$-bit input $X$ such that $\text{Keccak-}f[1600](X) = Y$?

Keccak-f is a permutation composed of trivially/efficiently invertible building blocks and is therefore itself trivially/efficiently invertible.

If you have the full state you can go backwards. In fact given a message of say, a MAC and the full state at the end you can go backwards and recover the secret key! So you may want to zero out part of the state after pushing your secret key through it in order to make going backwards intractable.

Using Keccak as a CSPRNG has a similar problem, need to periodically zero out a part of the state to defend against state compromise compromising past outputs, especially if there is no reseeding being done.

You can find the inverse operations here: https://github.com/CamMacFarlane/SHA3


Key material is the “mathematical” key, as opposed to metadata about the key such as the key type, its name in a database, its usage policy, etc.

In the context of key management, and in particular of programming interfaces that manipulate cryptographic keys, the term key can mean multiple things. It can refer to the actual bytes or numbers that are used in cryptographic computations: this is key material. It can also refer to the name (or label, identifier, index, …) of a cryptographic key in a key storage database. It can refer to an object in a system which supports requests such as “encrypt” and “decrypt”, and which may have associated metadata such as the key type (“this is an AES key”) and usage policies (“this key may only be used for AES-GCM, only on Tuesdays and only by users with the Grand Vizir privilege”).

In the context of information security, key material is the aspect of a key that requires especially confidential storage. Typically, the metadata about a key has low sensitivity and can be stored, manipulated and displayed with ordinary precautions. Key material (except for public keys) is more sensitive and requires additional precautions: avoid storing copies in a cache, require additional authentication before viewing or extracting, refuse copying to unencrypted storage, etc.

For example, the top Google hit for “key material” for me right now is “Importing key material in AWS Key Management Service”.

  An AWS KMS customer master key (CMK) is a logical representation of a master key. In addition to the CMK identifiers and other metadata, a CMK contains the key material used to encrypt and decrypt data.

When you create a CMK in AWS, you have a choice of letting AWS generate the key material randomly, or importing your own key material. In either case, you pass metadata such as identifiers as parameters to the key creation request.

Another example: PKCS#11 does not consistently use the term “key material”, but it uses it (without a formal definition) in the context of key objects. For an RSA private key, the key material consists of the (RSA-specific) attributes modulus, public exponent, private exponent, etc. For a secret key, the key material is a single byte array which PKCS#11 calls “key value”. Other key attributes, such as the key type, start and end date, usage policies “derive”, “encrypt”, “verify”, etc. are key metadata, not key material.

If you have a smartcard containing a decryption key, and you know the PIN that allows you to use the smartcard, then you have access to the key, in the sense that you can use the key for its intended purpose. But unless the smartcard is configured to allow extracting the key, you don't have access to the key material itself: only the smartcard has the key material.


Can we reduce Diffie-Hellman problem to "Discrete-log inversion" problem?

The answer is yes; see Chapter 21 of Galbraith's book. Suppose we have your Fixed-Inverse-DH oracle $O(\cdot)$, and given $g^a$ and $g^b$ we want to find $g^{ab}$. We do this in two steps. First, we use $O$ to compute $g^{a^2}$ from $g^{a}$—this is a related problem called the Square-DH problem. Then we use the quarter-squares identity to compute $g^{ab}$.

To compute $g^{a^2}$ from $g^a$ using $O$, we perform:

$$
\begin{align}
x &= O(g g^a) = g^{1/(1+a) \bmod n} \\
y &= O(g / g^a) = g^{1/(1-a) \bmod n} \\
z &= O((xy)^{1/2 \bmod n}) = g^{1 - a^2} \\
w &= g / z = g^{a^2}.
\end{align}
$$

Let's call the above procedure $S(\cdot)$. Now, we use the quarter-squares identity

$$
(x + y)^2 - (x - y)^2 = 4xy,
$$

to compute $S(g^{a}g^{b}) / S(g^{a}/g^{b}) = S(g^{a+b}) / S(g^{a - b}) = g^{(a+b)^2 - (a-b)^2} = g^{4ab}$. Exponentiate to ${1/4 \bmod n}$ and obtain $g^{ab}$.


Is this safe? Am I doing something dumb?

Well, I don't think it's actually safe; however why it's not safe would depend on the details of what your library has implemented within the Poly1305 function.

Straight Poly1305 isn't a MAC; it's actually a universal hash.  That is, it takes a message and a key and produces a value; however (unlike a MAC) it's sole guarrantee is that, for two different messages $M, M'$, we'll have $\text{Poly1305}_K(M) = \text{Poly1305}_K(M')$ for only a tiny fraction of the keys (and so if the key $K$ is selected randomly, this is quite improbable.

What this doesn't guarantee is that someone looking at $\text{Poly1305}_K(M)$ values for various $M$'s would have any difficulty whatsoever about recovering $K$, and for the Poly1305 function itself, recovering $K$ is easy.  Hence, if your Poly1305 function implements only the universal hash function itself, well, it's broken that way.

Now, this use of Poly1305 doesn't actually use a nonce, and so I'm not sure if you're using it straight.

To use Poly1305 as a MAC, what we do is compute the Poly1305 of the message, and then encrypt the tag with the nonce, using some cipher (AES or ChaCha, most typically).  This is safe; the Poly1305 prevents someone from producing two messages that will have the same MAC (because with an unknown Poly1305 key, that's unlikely), and the AES/ChaCha cipher will prevent someone from seeing the Poly1305 output directly (and so recovering things that way).

However, we do this encryption by taking the nonce, sending that through the cipher, and then adding that to the Poly1305 output; if we use the same nonce repeatedly, that means that we'll be adding a constant value to the Poly1305, and the attacker can adjust to that.

On the other hand, things doing this generally call out the cipher being used, say, as Poly1305-AES or Poly1305-ChaCha

So, I'm not sure why what you're doing isn't safe; but it doesn't look good.

  Is there a better way?

If you find it inconvenient to use a different nonce for every token, might I suggest using HMAC (based on some reasonable hash function, say SHA256)?  That doesn't need a nonce, and hence you're secure (or, at least, as long as you can keep the key secret).  It's not as fast as Poly1305; it wouldn't appear you care about that.


Is one big file as secure as X small files with the same password?

It depends on the possible attack vectors.

Generally password reuse is very dangerous. For instance, you could have less important files in one volume - say that the photos are less important. An attacker could ask you to show him a photo or two. You enter the password and the attacker performs classic shoulder surfing to get to know the password. Now the password is known for the important text files as well. Possibly you would not have entered the password if both sets of files were in one volume. This is one of the many reasons why you should not share passwords of internet sites either.

At the very least you'll have to enter the password twice to unlock all the files, it seems to me. So having two times the same password is less secure than having one whatever you do.

If you want to use one password: use a password manager, preferably on an unconnected device and unlock two highly complex and different passwords with the one used to unlock the database file.


First, you should specify:

what you need to be able to do in your database to get your job done;
what capabilities an adversary may have; and
what you want to ensure the adversary can't do.

Here's some generic guesses, but you should fill these in with specialized knowledge of your application's needs.

For (1): If all you need to do is search by a known SSN, as in SELECT * FROM users WHERE ssn = '123-45-6789' if there were no cryptography—in particular, if you never need to SELECT ssn FROM users WHERE ... and get back an SSN—then it is sufficient to hash the SSN irreversibly; there is no need for reversible encryption.

For (2): The standard threat model here is database disclosure.  But you might have a separate application server and database server, which have different attack surfaces and different risk of compromise, so you might consider compromise of the application server separately from compromise of the database server.

For (3): Obviously, one might hope that if your database is compromised, then the adversary nevertheless can't the SSN of anyone indexed by other information in the database.  But beware here: there's a lot that can be learned from the structure of databases even if individual records or identifiers are concealed.

Once you've read about leakage from databases even if encrypted, let's suppose for the moment that you just want to search by SSN, not look up SSN.  Here are some approaches.

You could store $\operatorname{SHA-256}(\mathit{ssn})$.

However, anyone who can read the database and find a hash $h$ in it can quickly enumerate all SSNs to find which one $h$ corresponds to by testing whether $h = \operatorname{SHA-256}(\text{000-00-0000})$, $h = \operatorname{SHA-256}(\text{000-00-0001})$, etc.  The problem here is that SHA-256 is a public function that anyone can evaluate, including the adversary, to test a guess, and the space of SSNs is very small.
You could store $\operatorname{Argon2}(\mathit{salt}, \mathit{ssn})$, with a per-row unique salt, and the largest time and space parameters for Argon2 that fit in your budget.

This raises the adversary's cost of testing a guess.  However, Argon2 is still a public function, so an adversary can still just test guesses—in parallel to get answers sooner, at the same total cost—and using Argon2, or any other sequential memory-hard hash, increases the cost for you to run your application too.
If there is a meaningful separation between the application server and the database server, so that an adversary could plausibly compromise one without the other, then you could store a secret key $k$ on the application server, and store $\operatorname{HMAC-SHA256}_k(\mathit{ssn})$.

Then, if only the database server is compromised, the adversary learns essentially nothing about the SSNs themselves: since they don't know $k$, they can't evaluate the secret function $\operatorname{HMAC-SHA256}_k$ to even test a guess.  Of course, once they break into the application server and recover $k$, the security is essentially as if you had used SHA-256.

The specific criterion here is that HMAC-SHA256 is a pseudorandom function family, or PRF.  Other PRFs would work too: keyed BLAKE2, SHA-3 KMAC, AES-CMAC, etc.

If you do need to store and retrieve the SSNs, you should use a deterministic authenticated cipher, such as a nonce-misuse-resistant authenticated cipher like AES-SIV or AES-GCM-SIV with a fixed nonce.  As it happens, authenticated ciphers like these also serve as pseudorandom function families, so you get essentially the same security as HMAC-SHA256 as long as the key $k$ is not compromised.  Be careful to check on the scaling limits of AES-SIV or AES-GCM-SIV in comparison to the potential volume of your database.


Is Blowfish strong enough for VPN encryption?

Thomas mentioned some "theoretical weaknesses" that can happen with $2^{32}$ blocks of data with CBC mode and an 8 byte block cipher; I will explore more about what that weakness is, and its practical relevance.

In CBC mode, we effectively send randomized data through the block cipher.  However, there is a chance that it happens to encrypt the exact same data twice with the same key; this results in the exact same ciphertext block appearing in the encrypted output twice.  If an attacker finds this, then he can deduce the exclusive or of the corresponding plaintext blocks.

How likely is this to happen?  Well, after about $2^{32}$ blocks of data ($2^{35} = 34$ Gigabytes of data), the expected number of times for it to happen is about 1 (it might not happen at all, or it might happen 2 or 3 times); if you encrypt more data, it's expected to happen more often; if you encrypt less, it can still happen (but with a reduced probability of happening).

How much effort will an attacker have to go through to find those colliding pairs?  Well, not very much; the biggest difficulty that the attacker would have is just dealing with the multigigabytes of data, and that's quite feasible for a determined attacker.

How much is this information leakage a security concern?  Well, that depends entirely on the nature of the plaintext.  The attacker will see the exclusive or of pairs of 8 byte segments, however he has no control over where they might appear.  8 bytes might be enough for him to guess the underlying plaintexts (and then, it might not), and even if he did, we might not care if he can deduce 16 bytes of data out of 34 Gigabytes.  On the other hand, maybe we do care -- that's really up to the application.

Now, block ciphers with 16 byte blocks (such as AES and Twofish) don't have these concerns (this same weakness can be expected to take place after $2^{68}$ bytes of encrypted data; we will never need to encrypt that much data with a single key).  This is one of the reasons we advise people to use more modern ciphers; this observation might not be a concern for a particular user, but with a modern cipher, we know it's not a concern for anyone.


Can I build a secure tweakable block cipher from a normal one by adding key and tweak?

Well, whether it is a secure tweakable block cipher depends on how resistant (E,D) are to related key attacks; that's not a standard assumption for block ciphers.

For example, this would not be a secure tweakable block cipher with 3DES; because every 8th bit is ignored, the attacker can effectively test the value of the 7 adjacent bits (except for the 7 MSBits) by a choosen tweak attack.  For example, if he can find a value t with (for an arbitrary block x):

E'(k,t,x) = E'(k,t+256,x)
E'(k,t+2,x) != E'(k,t+258,x)

then he can deduce that the addition of k and t+258 was just enough to propagate a carry past bit 8 (which doesn't affect the operation of 3DES) into bit 9 (which does).  This allows him to immediate deduce the lowest 7 used bits of the key.

Repeating this observation for the rest of the key bits allows us to recover all but 7 bits of the key with about 400 adaptively chosen tweaks; the last 7 is easy to brute force.


Such a weak key schedule was chosen since the key schedule "theory" was not well developed by that time. Designers just modified the key schedule of DES a bit. Remember that these key schedules had to be optimized for hardware, and any extra operation would cost something in terms of area.


For this cipher, I suggest finding all possible linear approximations by simply enumerating them.  If $S$ is the S-box, the bias of the linear approximation $\alpha \cdot x = \beta \cdot S(x)$ is given by

$$b(\alpha,\beta) = |2 \Pr[\alpha \cdot x = \beta \cdot S(x)] - 1|.$$

Notice that you can compute $b(\alpha,\beta)$ for a single value of $\alpha,\beta$ with $2^8$ evaluations of the S-box.  Also, there are only $2^{16}$ values of $\alpha,\beta$, so it is easy to enumerate all of them and compute $b(\alpha,\beta)$ for all of them.  This should help you find high-quality approximations for the S-box.

Your next step will be to piece these together into one-round characteristics and then multi-round characteristics.  You can do that by hand, but for your cipher, you might want to look at Matsui's algorithm, which is designed to find the highest-bias linear characteristic for multiple rounds, given the biases for approximations of the S-box.

As a starting point, it may be helpful to be familiar with the notion of active S-box.  A S-box is considered active in a particular linear characteristic if it is being approximated by some linear approximation other
than the trivial approximation $\alpha=\beta=0$.  The linear diffusion layer places some constraints on the set of active S-boxes in round $r+1$ as a function of the set of active S-boxes in round $r$.  Generally speaking, the more active S-boxes, the lower the bias.  (Non-active S-boxes are free: the approximation holds with probability 1 for them, i.e., with bias 1.)

Serge Vaudenay has suggested the following approach for finding high-bias linear approximations: summarize a one-round linear characteristic by a vector $a \in \{0,1\}^8$, where $a_i=1$ if the $i$th S-box is active in that round.  Now we can look at pairs $(a,a')$ where $a$ is the summary for a linear characteristic in one round and $a'$ is the summary for a linear characteristic in the next round.  Not all pairs $(a,a')$ will be feasible, but some will be.  In this way, we can build a graph where the vertices are elements of $\{0,1\}^8$ and there is an edge $a \to a'$ whenever the pair $(a,a')$ is feasible.  Now we can look for a path of length 8 in this graph that minimizes the total Hamming weight of the vertices visited along this path; this will correspond to looking for an 8-round linear characteristic with the smallest possible number of total active S-boxes.  More precisely, it gives us an upper-bound on the bias of any such 8-round linear characteristic; if the number of active S-boxes in the path is small, there might be a good 8-round linear characteristic with high bias; but if the number of active S-boxes is too large, there's no hope for a good 8-round linear characteristic.

We can even push this idea a bit further.  We can annotate each edge $a \to a'$ with the log of the maximum bias of any 2-round approximation where $a$ represents the S-boxes active in the first round of that characteristic and $a'$ the S-boxes active in the second round.  Then, we can look for a path of length 8, where we try to minimize the sum of the labels on the edges in the path.  This corresponds to a all-pairs shortest-paths path problem in a graph with 256 vertices, and can be solved efficiently using the Floyd-Warshall algorithm.

To test whether the edge $a \to a'$ is feasible, here is a technique that might be helpful.  Let $\alpha,\alpha' \in \{0,1\}^{64}$ denote the linear approximation for the first round that we are considering, i.e., $\alpha \cdot x = \alpha' \cdot R_k(x)$ where $R$ is the round function.  Note that $a$ is a deterministic function of $\alpha$; i.e., $a_i=0$ if and only if $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$.  Now we can break $R_k$ into three pieces: the key xor, the S-box application, and a linear function, i.e., $R_k(x)=L(S(x\oplus k))$ where $S(\cdot)$ denotes parallel application of 8 S-boxes.  Now both the key xor and the S-box preserve the set of active S-boxes, so we really want to look at the set of feasible linear approximations $\alpha,\alpha'$ for $L$, i.e., $\alpha \cdot x = \alpha' \cdot L(x)$.  Given $a,a'$ it is easy to determine whether there exists $\alpha,\alpha'$ that are consistent with $a,a'$ and such that the approximation $\alpha \cdot x = \alpha' \cdot L(x)$ has non-zero bias.   You can solve this using Gaussian elimination: for each $i$ such that $a_i=0$, add linear constraints $\alpha_{8i}=\alpha_{8i+1}=\dots=\alpha_{8i+7}=0$, and similarly for $a',\alpha'$; now treat the remaining bits of $\alpha,\alpha'$ as unknowns.  Now notice that $\alpha \cdot x = \alpha' \cdot L(x)$ has bias 1 if $\alpha = L(\alpha')$, and bias 0 otherwise.  This gives additional linear constraints on the unknowns.  Now use Gaussian elimination to check whether there exists a non-zero solution to this set of linear equations.

Or, you can look for multi-round characteristics by hand.  That works, too.

I am assuming you have read some basic tutorials on linear cryptanalysis, e.g.,

A Tutorial on Linear and Differential Cryptanalysis.  Howard M. Heys.

You can also read some advanced literature that establishes the theoretical foundations underlying linear cryptanalysis, e.g.,

How far can we go beyond linear cryptanalysis? Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.
Statistical Cryptanalysis of Block Ciphers.  Pascal Junod, PhD thesis, École Polytechnique Fédérale de Lausanne, Switzerland, 2004.

The following paper introduces Matsui's algorithm for finding linear characteristics for DES:

On correlation between the order of S-boxes and the strength of DES.  Mitsuru Matsui.  EUROCRYPT '94.


How many hashes for high probability of finding a collision (specific case)?

Let's assume that there are no prior collisions (two different messages that generate an identical hash) for the first $2^{64}$ messages.

If you want to find a message for one hash then you would have to try all these $2^{64}$ messages to reach the probability of 1 (100%). Since you mentioned good probability we can say that we would have to try half of that for a probability of 0.5 (50%). That means that we would have to try $2^{64} / \space 2$ possibilities which would be $2^{63}$.

Now you also already have a list of 220 hashes. That means that you can reduce it because we previously only calculated it for one hash, so the solution is:

$$\frac{2^{63}}{220} \approx 4.2 \times 10^{16}$$ for a probability of $0.5$ to find a message that hashes to one hash in your list.


Performance metrices of cryptographic algorithms

Criteria for evaluation of Cryptography Algorithms:

Having public specification (the only secret is the key).
Patent status.
What it aims at: block cipher (DES, AES..), cipher, message digest, MAC, proof of origin, signature, key establishment, TRNG, PRNG.
Requirements for and limitations of the algorithm itself.

Randomness requirements;
Requirements to validate the input parameters (e.g. public key for ECDH).

Being symmetric (block ciphers, SHA) or asymmetric (RSA, ECDSA, ECDH).
Security under some threat model:

Resistance to key recovery (bounded at least by key size);
Block size (for block ciphers);
Resistance to pure cryptanalytic attacks;
Resistance to side-channel leakage (with many subdivisions);
Resistance to fault injection.

Complexity and familiarity / learning curve to use the algorithm.
Parameter sizes:

Output size (overhead / expansion ratio);
Encoded (public) key size;
Accepted input sizes;

Speed (often very platform-dependent):

Cycles/byte averages for large messages or multiple uses with the same key;
Time to setup a new key;
Time versus size.

Memory footprint:

Code;
RAM per running instance.

Availability of a version with suitable characteristics as above on a given platform.
Acceptance by security authorities.

Note: fell free to restructure / add to the list, this is a community wiki.


Is CAST5 still a secure algorithm to use?

CAST5 seems to be a solid 64-bit block cipher with 128-bit key. As far as I can tell after a short literature search, it's definition is sound and unbroken, despite nearly two decades of exposure (more for the round function).

CAST5 is also known as CAST-128, defined in RFC 2144 (1997), and endorsed by ISO/IEC 18033-3:2010 (current). It is a 16-round Feistel cipher, with each round using 4 (among a total of 8) S-boxes with 8-bit input and 32-bit output; and 32-bit operations (XORs, addition/subtraction), and key-dependent rotations.

CAST5 most (but still mildly) serious weakness is its small block size (64-bit) by modern standards (the trend is 128-bit, e.g. AES). This could be an issue when enciphering large amount of data with the same key using some common modes, including CFB used in OpenPGP and GnuPG, because collisions among random blocks occur with increasing odds (about 0.8% for 4GiB, 40% for 32GiB). For example, it can be disproved with some level of credibility a false claim that a dozen of ≈20GiB files known to have been GnuPG-enciphered using CAST5 correspond to all-zero data encrypted as a computer benchmark, simply by checking if there is any file with colliding blocks (the claimed origin of the encrypted files makes it unlikely, when several collisions are expected for "real" data, like video).

Another inherent limitation is the 128-bit key. There are much worst fears to have in a GnuPG context (how can I trust that BIOS? Hard disk firmware? Keyboard?).

CAST5's implementation may be vulnerable to timing attack related to cache or data-dependent operations. That could be a relatively credible attack vector if hostile software was running on the same CPU with only the isolation provided by an OS or VM. It seems to be a relatively low residual risk.

CAST5 does not seem particularly vulnerable (or resistant) to fault attack, or related-key attack. These types of attacks are not much to fear in the context of GnuPG.

Note: the paper by John Kelsey, Bruce Schneier, and David Wagner: Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA (ICICS 1997), is for an earlier version of CAST with only 8 rounds. The paper is made available in Postscript by the last author, and may be viewable online here.


Linear Feedback Shift Registers analysis

First of all, LFSR's are not secure when they are used alone. They have good statistical properties and one can calculate their period given the feedback polynomial. The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. In this case, it visit all states except the all-zero state if it started with a non-zero sate.

To find the taps and internal of an LFSR, you can go in two ways;

Give variable names for the internal and tap point then you can generate a linear equation of the system then solve it with Gaussian elimination.
Use the Berlekamp-Massey algorithm, this is faster than Gaussian elimination and only requires the double of the LFSR's size. i.e. an LFSR with length $L$ can be constructed with $2L$ sequential output regardless of the number of the taps. It is an interactive algorithm that updates the taps according to a currently given output bit.

Actually, Berlakamp-Massey algorithm produces the shortest LFSR with taps that produce the given sequence. The algorithm may reach the result before consuming all $2L$ bits, however, an attacker needs to use all $2L$ bits to be sure. If the determining polynomial of the LFSR is no primitive, then there can be more than one LFSR that produces the sequence with different lengths. Berlakamp-Massey algorithm, however, always will find out the shortest LFSR.

The LFSR based archaic stream ciphers are;

Combining LFSRs with non-linear combiner broken by the novel attack of Siegenthaler
Irregular clocking as Alternating step generator
Shrinking Generator is broken if the taps are known; Gil et. al,  2009 New Attack Strategy for the Shrinking Generator
if not known then the attacks are not better than brute-force.
Filtering the LFSR
Self Shrinking Generator (SSG). Attack on SSG;

2001 Zenner et. al; Improved Cryptanalysis of the Self-Shrinking Generator require less than 70% of the brute-force, for example for 120-bit the attack requires $\mathcal{O}(2^{83})$-time.
2011  Amparo and Sabater; Cryptanalytic Attack on the Self-Shrinking Sequence Generator requires $\mathcal{O}(2^{L/2})$ for time complexity, $\mathcal{O}(2^{L/4})$ for the amount of intercepted sequence and $\mathcal{O}(L^2)$. Note This work may not be correct, see comments
2006 Zhang and Fang; New Guess-and-Determine Attack on the Self-Shrinking Generator. Depending on the $L$ the length of the LFSR their attacks has;

$L \geq 100$ then $\mathcal{O}(2^{0.556L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.161L})$-bit keystream
$L < 100$ then $\mathcal{O}(2^{0.571L})$-time complexity, $\mathcal{O}(2^L)$-memory complexcity, and $\mathcal{O}(2^{0.184L})$-bit keystream

And all the above is broken, at least, theoretically.

Also, some well-knowns due to GSM and Bluetooth.

A5/1 and A5/2 used in GSM phones, E0 used in Bluetooth. They are broken, see the links. According to this source NSA can break A5/1.


How to encrypt data with the Threefish cipher

As far as I know there isn't any Threefish-specific encryption standard specified. I actually asked Bruce Schneier back in the day (when I created my "SkeinFromSpec" implementation). Threefish is a tweakable block cipher with a large block size. I asked for instance if you should keep to the high amount of rounds (80 for Skein) and what mode I should use, but I never got a concrete answer. At that time the Skein team was of course mainly busy with the SHA-3 contest.

In principle you could use any mode of operation that is also available for normal block ciphers, as long as it allows for the larger block size. You are of course better off using an (authenticated) mode of operation for tweakable block ciphers. There are a few papers on that, but as you've indicated, they are usually theoretical in nature.

Things may have been different if Skein was the winner of the SHA-3 contest. There are a few proposed modes that use the Keccak sponge - the winner of the SHA-3 contest - which you could use, Keyak for instance.


Multi Message security in Random Oracle Model

The random oracle model is needed, if you work with hash-functions and want to prove security with them. The reason is, that collision resistance often does not satisfy all condition you want for a proof.
For proofs under the ROM you need a cryptosystem that uses a Hash-function. One example is the RSA Full Domain Hash Signature. I think you learned about the reduction proof. When you build the reduction you have to simulate the RO. So if you assume an adversary for the reduction, you have to simulate the communication between the adversary and the RO. This is mainly just rewriting the definition of RO, but you can also make use of some tricks: The reduction knows the communication and the reduction can "program" the result of the RO. In Katz & Lindell's textbook (2nd edition) on page 448ff you can find such a proof for the RSA Full Domain Hash Signature.
I couldn't find a proof for EAV-Mult security under ROM. But it should be pretty similar to EVA-Mult in general, expect simulating the RO.


As commented by Maarten Bodewes, derived secrects are not session keys. In TLS 1.3, a "derived secret" and a label are further fed into the HKDF.Expand function to generate the desired session/traffic key, secret nonce/IV, resumption key, etc. I think such an intermediate HKDF.Expand step makes a better key separation for security purpose, e.g., corrupting a traffic key intuitively leaks no information about a resumption key because they are not generated from the same "derived secret".

Btw, HKDF.Extract essentially converts a high-entropy input (not sampled from a uniform distribution), e.g., a DH result, to a fixed-length pseudorandom key, while HKDF.Expand takes a pseudorandom key and a label to generate a random string (which for example could be either a derived secret or a session key).