What is wrong with AES-CTR-HMAC-SHA256 - or why is it not in TLS?

Short answer:

There would be nothing (that isn't already wrong with TLS) necessarily wrong with a CTR + HMAC cipher suite, but the technical merits are only one factor in a technical feature getting to RFC status in the TLS working group.

Without being discourteous to the TLS Working Group (WG) participants or process, other reasons can be: political (including national/standards body alignment); personal/corporate preference/motivation; historical timing; resistance to change (modifying implementations is an often-cited cost); fear/uncertainty/doubt/apathy/debating skills etc.
TLS standardization happens very much in a real world implementation + real humans interacting environment, where the isolated technical merits of an idea are by no means the only measure of, or contributing factor to, success.

Why the draft-ietf-tls-ctr in particular never made it to RFC status (as part of TLS 1.2 or separately) is a little murkier, but my best guess is that a combination of:

timing and politics: probably most importantly, AEAD modes such as GCM, many based on CTR mode, and in the case of GCM favoured by a NIST standardisation process, came along early in the TLS 1.2 process and probably supplanted CTR in the thinking of the WG editors/participants.
uncertainty: CTR in 2006 was relatively less known and trusted compared to CBC.
doubt: there were some concerns stated in the TLS WG discussions about its use in DTLS and with explicit vs implicit IVs
Eric Rescorla was both an author for draft-ietf-tls-ctr and co-editor of the TLS 1.2 draft, so I suspect once GCM became a preference for the WG he stopped editing and pushing the CTR mode.

Longer timeline:

Nov 2005

First mentions of draft-ietf-tls-ctr at Oct 2005 TLS WG meeting, at this stage not a chartered WG item.
Feb 2006

draft-ietf-tls-ctr 00 begins life as a companion draft to the TLS 1.2 draft 00.
March 2006

draft-ietf-tls-ctr is listed on the March 2006 TLS WG meeting agenda
The TLS WG charter at that time explicitly discusses counter mode cipher suites as being a goal of TLS 1.2.

The March 2006 TLS WG meeting minutes refer to draft-ietf-tls-ctr as being a chartered item and ready for review.

At this point the First draft of TLS 1.2 specification, including CTR mode cipher suites milestone is marked as Done but CTR modes are clearly not in draft 1.2 specification at that time (or any other).
July 2006

At the July 2006 TLS WG meeting draft-ietf-tls-ctr is described as ready for last call in the minutes.

No last call for draft-ietf-tls-ctr eventuates on the TLS WG mailing list.
October 2006

TLS 1.2 draft 02 is published, and AEAD/GCM modes are included for the first time.
November 2006

At the Nov 2006 TLS WG meeting draft-ietf-tls-ctr is still on the agenda, and the minutes show discussion centered around the counter and IV structure.  A GCM mode draft is mentioned as being imminent.
December 2006

Some concerns about counter mode, in particular counter/IV structures, are discussed on TLS WG mailing list.
January 2007

Discussion of CTR mode on the TLS WG mailing list has dried up apart from some discussion about potential issues with DTLS, and GCM mode is being actively discussed.
March 2007

draft-ietf-tls-ctr is still mentioned in the TLS 1.2 charter, but no longer on the March 2007 TLS WG meeting agenda, and all discussion in the minutes is about GCM.

From this point on draft-ietf-tls-ctr is not mentioned again, and no CTR modes end up in TLS 1.2. GCM modes go on to be published in RFC 5288 about the same time as TLS 1.2 is finalised in RFC 5246.


ECC keys vulnerable to brute force attack?

Yes a brute force key-guessing attack would be faster, but:

It would be ridiculously slow for either. E.g. see this for 256-bit keys.
There are faster attacks on both and those attacks break larger RSA sizes than ECC sizes.

Related: Why can ECC key sizes be smaller than RSA keys for similar security?


Is there a SHA-256 value which hashes to itself?

This question here gives the probability of such a value, called a "fixed point" existing as 63% (based on assuming a "random" property of SHA256):

Cryptographic hash where the hashing function input is similar to the result

There is at least one such "fixed point" of the compression function that the SHA256 algorithm uses. An example is here:

Fixed point of the SHA-256 compression function

As explained in that answer, "[e]asy to find fixed-points are a known property of this construction", therefore this isn't a problem.


In very short:

Assume you have an NP problem, stated as some condition to be met. Since it is a NP condition, the computational complexity to find a satisfying input (called the witness for the language) grows quite fast.

The setup of such an encryption scheme is based on a multilinear map (a generalization of a bilinear map, but with arbitrary many inputs). And then you only need to know the NP statement to encrypt something, but you need a witness of the according length to decrypt the ciphertext again.

The actual construction is really complex, and I don't think you can explain that in easy terms. But it is based on multilinear maps, and look at DrLecters answer in "What are Cryptographic Multi-linear Maps?" for more information on that. Current constructions build on fully homomorphic encryption.


Can PBKDF2 be used to create an XOR cipher key to encrypt random plaintext?

I would use an encryption method designed for the purpose, such as AES Key Wrap.

That said, PBKDF2 uses a PRF internally, so if you specify an iteration count of 1, your suggestion would effectively amount to using a PRF in CTR mode. Since you put the question that way, then, yes, it would be good enough, in the sense that the weakest link would probably be the password and not the encryption scheme.

Edit: Using the PBKDF derived key as a key stream, rather than as a key for a proper symmetric cipher, would obviously require you to treat the Salt value as a nonce (i.e. it has to be different each time you perform the encryption operation). This is not strictly necessary if you use AES in a secure mode of operation - in such case you would get away with leaving the Salt unchanged, but you would OTOH, depending on which mode of operation you use, might have to set the initial state of the mode of operation to a Nonce value. If you use AES Key Wrap, the initial state is a default constant, but for e.g. CTR mode it would be essential to set the initial counter to a nonce.


Finally, the decryption is: $m = C_2 \cdot C_1^{-1} \cdot C_1^{-d}$


Multiplication in elliptical curve cryptography

I understand that $16\cdot 7\equiv 10 \bmod 17$, but where does the $7$ come from? Also, why is $5^{−1}\equiv 7 \bmod 17$ shouldn't that equal zero..?

When working with modular arithmetic, $a^{-1}$ (if it exists) is a number $b$ such that $a\cdot b\equiv 1$. So, because $5\cdot7\equiv 1\bmod{17}$, we say that $5^{-1}\equiv 7\bmod{17}$. Not sure where $0$ came from in your mind as $0$ times anything is $0$.

In step 5, where you are multiplying by $\frac{7}{7}$, the reason they are doing this is to cancel out the bottom since $5\cdot 7\equiv 1$. This step is not necessary, but it does make things simpler, I guess. You can play around with this modular arithmetic calculator to verify that $\frac{16}{5} = 16\cdot 7\equiv 10\bmod{17}$.


There are more recent papers that cite Joux and Lucks.  Example: "Preimage Attacks against PKC98-Hash and HAS-V", Sasaki et al., uses the Joux-Lucks algorithm to attack two hash functions.

Have you looked at newer papers that cite Joux and Lucks?  Have you done a literature search, to find newer papers that cite their Asiacrypt 2009 paper?  Google Scholar, Citeseer, and Microsoft Academic Search can help you here.  That'd be a good start.  If someone uses the Joux-Lucks algorithm in their work, they'll probably cite the Joux and Lucks paper.


Is it safe to derive secret from alice's private key and alice's public key?

Yes, recovering the computed secret is as hard as doing it for conventional Diffie-Hellman and thus infeasible for any secure groups.

This is known as Square-Diffie-Hellman problem, the reduction to the computational Diffie-Hellman problem (CDH) can be found in this Q&A.


I think
Johannes Buchmann, Introduction To Cryptography, Springer, 2nd Ed, 2004
is very nice and pitched squarely at undergraduates. You can see a preview here
https://books.google.com.au/books/about/Introduction_to_Cryptography.html?id=BuQlBQAAQBAJ&printsec=frontcover&source=kp_read_button&redir_esc=y#v=onepage&q&f=false
Its contents are:
Integers
Congruences and Residue Class Rings
Encryption
Probability and Perfect Secrecy
DES
AES
Prime Number Generation
Public Key Encryption
Factoring
Discrete Logarithms
Cryptographic Hash Functions
Digital Signatures
Other Systems
Identification
Secret Sharing
Public Key Infrastructures
It is broad, as opposed to very deep, but really well written.


IOTA doesn't use proof of work.
IOTA is a tangle, and the consensus is reach based on the information propagation in the network. You can find more information about it here:
https://forum.iota.org/t/iota-consensus-masterclass/1193


You're somewhat on the right track.  A standard way to do this would be using an RSA sign/verify scheme.

On the server, user-specific and license-specific data is concatenated into a string and signed with the private key.

In the software, the signature is verified with the public key.  The public key can not be used to create valid signatures, it can only verify them (this is the beauty of asymmetric cryptography).

Of course, as pointed out by Thomas, there's nothing to stop someone decompiling your software and modifying the source code, but that can't be avoided.

If you're going to use RSA, be sure to use a secure padding scheme like RSA-PSS.


Is there a studied notion of "party independent transfer"?

You can get active security in cryptographic setting, but it seems that you also need broadcast.

Bob and Charlie both create an asymmetric key.
Bob commits to his public key a broadcasts the commitment.
Bob sends its public key to Charlie and opens the commitment to him. If these do not match, Charlie complains.
Charlie broadcasts both keys (in random order). If Bob's isn't one of them, he complains by opening the commitment.
Alice picks one key at random, encrypts the message, and broadcasts the result. Only one of them is able to decrypt, and Alice doesn't know who.

Note that the message space should be large, otherwise Bob can just try to encrypt all possible messages with Charlie's key and see which one was broadcast. To remedy this, apply some random padding to the message.

Also note that in step 3, the accusation does not lead to identification of the culprit.


Is it possible to apply hill-climbing algorithm to Diffie–Hellman?

NO, we can't apply an hill-climbing algorithm to Diffie–Hellman.

In order to break Diffie-Hellman key exchange, it is enough for Eve to reverse exponentiation modulo the public prime $p$; that is, given $g^x\bmod p$, find $x$. That's the Discrete Logarithm Problem.

We do not know that hill-climbing can help for that (or the slightly less general DH problem). One reason is that in the DLP, we have no known way to estimate if a guess of $x$ is close or far from the solution (contrary to what happens for the continuous logarithm problem). Hill-climbing is nice when it works; but in crypto, it tends to work only against weak/broken systems.


How is the plaintext to ciphertext expansion ratio on AES cipher?

AES as a block cipher

AES is a block cipher. Since it is invertible, there must be a one-to-one mapping between plaintext and ciphertext blocks. So when talking about a single block, the ratio of ciphertext to plaintext is indeed $1$.

Ciphers and modes of operation

However, a block cipher is not a complete cipher. In order to encrypt quantities of information greater than the block size and/or to encrypt the same plaintext while maintaining indistinguishability, you have to use a mode of operation.

A mode of operation requires an initialization vector, which will add a constant amount of size overhead to the size of the cryptogram. Different use cases and modes of operation can support/require varying minimum IV sizes. IV sizes of 96 to 256 bits are common.

A proper mode of operation includes authentication and integrity of the ciphertext, as well as associated data. The authentication tag will also contribute to the size overhead. Tags can vary in size depending on the application. Very constrained environments may use tags for short lived data that would be unacceptably short in other environments, while less constrained environments may use tags that would be unacceptably large in other contexts. A tag size of 64 to 256 bits is a reasonable range.

Conclusion

In the worst case scenario, for AES which has a 128-bit block size, encrypting a single block with an 128-bit IV will double the size of the cryptogram compared to the size of the plaintext, giving a ratio of $2:1$ ciphertext to plaintext size.*

When you include authentication, assuming a 256-bit tag for a single block, then you have a ratio of $4 : 1$.

In the best case scenario, encrypting a very very long message with any sized initialization vector and authentication tag will cause a negligible increase in the size of the cryptogram compared to the size of the plaintext. The ratio of ciphertext to plaintext size will approach $1$ as the size of the plaintext becomes larger.

* It is arguable that encrypting a single bit is the worst case scenario, but this answer concerns itself with a minimum unit of 1 block size.


Are there drawbacks to encrypting data locally before being encrypted in cloud backup (multiple encryption)?

Apart from the performance hit of encrypting / decrypting twice, and the inconvenience of having two keys to not lose, this should work fine. In fact I wish more people had your approach to data privacy and encrypted things before sending them over the internet!

About Altdrive in particular, a good question to ask yourself about their upload service / upload webpage is: is the data being encrypted on your computer and then uploaded, or uploaded and then encrypted? If their uploader encrypts on your end with a key you never give them, then double-encryption probably isn't adding anything, but if it's sent to them in the clear, then your EncFS idea is good. A good test would be to upload a secret.txt file, then log in to the site from a different computer that doesn't have the encryption key and see if you can download and decrypt the file. If you're not able to decrypt it, then their service is probably trustworthy.

That bit from Altdrive about losing your key is a standard warning in the encryption world: backing up your key protects you from losing it, but means there are more copies of your key for someone to steal. You have to decide which you're more worried about: losing your key, or having it stolen? I can tell you that there are many large corporations and governments who back up decryption keys, and many who don't. You have to decide for yourself.

I've never used EncFS, but from a quick google it looks like it encrypts each file individually, so you should be able to pull down files one-at-a-time rather than having to download the whole block. BUT it looks like it encrypts the filenames by default, so you'll have no idea which file you're grabbing. Does EncFS have a setting to turn off filename encryption?

Again, from a quick google of EncFS:

  Files are encrypted using a volume key, which is stored encrypted in the source directory. A password is used to decrypt this key. wikipedia

You probably want to not upload that volume key file since that would mean that cracking your password gives an attacker your decryption key (and it's ALWAYS easier to crack a password than a full key).


Is it ever OK to to sign RSA messages with padding random bytes?

The correctness of the padding should be verifiable from the hash of the message - that is, given the hash of the message, the same padding should be reproducible. Otherwise, "existential forgery" would be possible.
So what is "existential forgery"?
Basically, you just produce a random string of bytes as your signature. When it's interpreted as an integer and raised to e'th power mod n, the lower 256/384/512 bits will be as valid a hash value as any other, so even though we don't know what message produces such hash value, we've found one that exists, hence "existential forgery".
To actually make the attack work requires some extra effort, including but not limited to:

mounting collision attack on the hash function against the verification exponent with many random messages.

for small modulus, GNFS may yield results with part of lower-order bits matching the candidate message digests.

As noted by @fgrieu in the comment, the question asks a hypothetical situation that cannot be universally applied, thereby making it a false proposition.


What is the key size currently used by RSA and Diffie-Hellman for secure communication over Internet?

Currently (as of 2017-05-11) 2048-bit keys are most popular for use with RSA, and 2048 bit keys should also be used with classic Diffie-Hellman. These offer about the same security as a symmetric encryption algorithm with 112 bits of security.

Also in common use as of this date are 256 bit Elliptic Curve keys (mostly NIST P-256 and Curve25519) for ECDH/ECDSA/EdDSA which offer the same security as a 128-bit symmetric algorithm.

A good primer on the reasons for these key size differences can be found here.


What is a wide block cipher and why does it avoid birthday bound problems?

I don't think the term "wide block cipher" has a hard definition beyond

  has a larger block size than the current standard algorithm(s)

which right now in most cases would equal to

  has a block size larger than 128 bit

because AES is our current reference standard.

Now the thing with block ciphers is that they are are pseudo-random permutations and as such you can distinguish them from pseudo-random functions because you will see a collision with the latter at the birthday where you won't find that with PRPs. This can be important in scenarios where you need to generate a lot of random numbers mostly and even then I don't think the different characteristic would be exploitable in most cases.

To see how PRPs can be distinguished, assume as an example that you run CTR-mode with a PRF and a PRP, both with $n$-bit output length. You will now find that a collision in the CTR keystream occurs with the PRF at about $2^{n/2}$ invocations whereas this won't happen until after you wrap-around with the PRP.

Another application of wide block ciphers is in full-disk encryption where you can encrypt larger blocks implying that single bit-flips will destroy larger regions of plaintext thus being (hopefully) more notice-able.

The last somewhat popular application of wide block ciphers is as part of hashing functions. Imagine your average block cipher $E:\{0,1\}^k\times \{0,1\}^n\to\{0,1\}^n$, note that you can put more into the function than you take out of it. Now you expect collisions after $2^{n/2}$ invokations, ie you have $n/2$-bit collision resistance which makes non-wide block ciphers (such as AES) unsuitable for usage as a core compression function in hash functions (because $2^{64}$ operations is feasible and a similar amount of work was done for the SHA-1 collision).


Kudos for the question's critical thinking. Keep on with that attitude!

Eve wants to find $\log_g(g^x)$ which gives her $x$. Why is it a problem? She knows $g$ and she knows what the number $g^x$ is.

The problem as stated in this quote and with $g$ in the set $\mathbb Z$ (the integers) is the logarithm problem restricted to integers, and indeed is easy. Just by looking at the size of $g^x$ (the number of digits in decimal), it's easy to get an idea of how large $x$ is. For example if $g$ is $11$, $g^x$ will have a little over $x$ decimal digits. More generaly, $x$ is $\log(g^x)/\log(g)$, computed over the reals with the logarithm in any base.
In the discrete logarithm problem, $g^x$ is not computed by regular integer multiplications. It's computed in a finite set with group structure. $g^x$ is constrained to be in the same finite set as $g$ is, no matter how large $x$. That makes a huge difference, because Eve always gets a small value, thus techniques based on the size of $g^x$ will no longer work.
The simplest group usable is the multiplicative group modulo a safe prime $p$. In this group, $u*v$ is defined as the remainder of the Euclidean division of $u\cdot v$ by $p$, where $u\cdot v$ is the ordinary product. $g^x$ is defined as usual:$$g^x=\underbrace{g*g\ldots g*g}_{x\text{ terms}}$$
where each $*$ is an operation in the finite set. Note that $g^x$ can be computed with $\approx1.5\log_2(x)$ modular multiplications, rather than the obvious $x-1$.
To convince you things are hard, try with $p=31469$ (small enough that $u\cdot v$ fits 9 decimal digits), $g=3$, $g^x=11292$. How do you get $x$?
One simple method is to try all $x$ sequentially, that has cost $\Theta(p)$ (note that we can move to the next power of $g$ with a single modular multiplication). A better method is baby-step/giant-step, that has cost $\Theta(\sqrt p)$ in work and memory. Yet a better (probabilistic) method is Pollard's rho, which also requires $\Theta(\sqrt p)$ work but reduces memory requirements to $\Theta(1)$, and can largely be parallelized.
Because we use a particularly simple group, there are even better methods. However, with e.g. Elliptic Curve groups, we don't know a much better method that works on computers as we know them. Thus if we use a suitable group with enough elements (e.g. in the order of $2^{256}$), the best way we know to get $x$ requires in the order of $2^{128}$ group operations on computers as we know them.


For private key operations you need at least $n$ (the modulus) and $d$ (the private exponent). The primes $p$ and $q$ let you calculate those – or use some shortcuts for quicker computation – so they also suffice.

In practice RSA keys often include all of those values, to avoid having to compute them as needed and to allow for optimized and unoptimized implementations.

  In 2 - (d)

This would not be enough on its own, but the page actually says that the private key includes the modulus.


First of all, we need to review what they mean by "parity of a permutation"; they don't mean whether the input block had a even number of 1's.

Instead, they view the $n$ bit cipher (with a specific key) as a permutation on $2^n$ objects; that is, it can be review as a way of rearranging that set of $2^n$ objects onto itself.

Now, permutations on a finite set of objects has a "parity"; that is, any specific permutation can be generated by a series of exchanges between the objects; there are a large (actually, infinite) number of ways of expressing any specific permutation as a series of exchanges, however if an permutation can be expressed as an even number of exchanges, any other set of exchanges that express that same permutation will also be even; we then say that this is an "even" permutation.  Similarly, if a permutation can be expressed with an odd number of exchanges, we say that this is an odd permutation.

Now, if we perform an even permutation on a set of objects, and then do a second even permutation, the resulting permutation will also be even.  Because block ciphers are commonly expressed as concatenations of round functions (where you first do one round function, then the second, etc), that means that if each round function is even, then the overall block cipher will be even.

Now, what does this have to do with small operations?  Well, most of the obvious ways to use a 32 bit operation within a 128 bit block cipher will result in an even permutation.  For example:

If you use the 32 bit operation on 32 bits of the block in an invertible way, and don't touch the other 96 bits, this will always be even.  AES can be modeled in this way.
If you take a function of some of the block cipher bits (and possibly key bits), and exclusive-or that into the other block cipher bits (Feistal network), this will always be even, as long as you're excluseive-or'ing into at least two bits.  Hence, virtually most Feistal-based ciphers will be even.

Now, just because most operations will be even, it doesn't mean that all operations are.  Here is one that can be odd: if we split the 128 bit block into 4 32-bit tracks $A$, $B$, $C$, $D$, then this operation can be an odd permutation:

A += F(B, C, D, Key)

(where the addition is performed modulo $2^{32}$).  Obviously, that can be a part of an unbalanced Feistel design.

So, if it is possible that we can construct a block cipher with an odd permutation, why don't we?  Well, as far as I can tell, because no one cares.  If the attacker knows that a block cipher is an even permutation, all that means is that if he obtains $2^n-2$ entries in the code book, he can deduce the last two.  Given that he can't really deduce anything more than that, people are content to leave that on the table.


In storing passwords in a database should I use a per-application salt in addition to a per-secret salt?

There is an advantage.

Cracking a password from its hash without knowing the salt is extremely difficult, as you're essentially increasing the password length by the length of the salt.

If you're storing the hash in such a way that it isn't obvious that it's been salted by the application, the attacker likely won't go looking for it. If the application itself isn't plain text (ie; compiled in some way), even if they do go searching for it, it is non-trivial to find.


Q1.

Here's an algorithm to test irreducibility of a univariate non-constant monic polynomial over a finite field $\mathbb F_q$. (I learnt this from von zur Gathen and Gerhard's Modern Computer Algebra.)

Let $q=p^e$ be a prime power. A generalization of Fermat's little theorem states that for all $d\geq1$,
$$
x^{q^d}-x \;=\;\prod \{\,f\in\mathbb F_q[x]\text{ monic and irreducible with }\deg f\mid d\,\}
\text.
$$

Therefore, a monic polynomial $f\in\mathbb F_q[x]$ is irreducible if and only if $\gcd(x^{q^d}-x,f)=1$ for all $d\in\{1,\dots,n-1\}$.
This immediately yields an algorithm for testing irreducibility; it requires $\mathcal O(n^3\log(nq))$ elementary arithmetic operations when implemented correctly.

5.
If you are interested in a high-level description of Schoof's algorithm, have a look at this post of mine. (In particular, note that it is not exactly trivial to implement.)

Q4.

Suppose you have a prime factorization of the curve $E$'s group order (perhaps obtained using Schoof's algorithm followed by a factoring algorithm), say
$$n=\lvert E\rvert=\prod_{i=1}^k p_i^{e_i} \text.$$
Note that in any finite group, an element's order divides the group order. Hence you can easily check whether a point $P\in E$ is a generator by computing the powers $[n/p_i]P$: If
one of them is the identity, then $P$ is not a generator (since its order must then be a divisor of $n/p_i<n$), otherwise it is.
Now one can show (using the classification of finite abelian groups) that a randomly chosen group element is a generator with probability at least
$$
\prod_{i=1}^k\left(1-\frac1{p_i}\right)^{e_i}
\text,
$$
which should be "large enough" for practical purposes (when $n$ has few small prime divisors), hence you can find a generator by randomly picking points on the curve until you get one.


You asked several questions above.  I will address one in specific that stands out to me, and that is your question about XORing the keys together.  Your statement that they might both have the same character at the same location that would yield a null byte is disconcerting: passwords are not normally used directly as encryption keys.

Mathematically, a string of eight zero bits is not going to reduce the strength of AES, as AES does not have any known weak keys.  However, if an attacker knows you will be using ASCII characters directly as key material, his job of attacking just got that much easier, because he understands the limits imposed by such a restriction.

If you use ASCII characters as your key, you would need to tell your clients they must use exactly a 16 character password, which will limit their creativity (greatly reducing the pool of likely passwords they might choose.)  ASCII severely constrains the number of bits that can change in a given byte: there are few people who could enter a character on a keyboard that is outside the range of the common letters, numbers, and symbols.  By limiting key bytes to exclude values in the ranges of 0x00-0x1F and 0x80-0xFF, you've artificially limited your keys to $96^{16}$ instead of $256^{16}$.  This dangerously weakens your implementation.

Consider using a key derivation function to transform the passwords into the cryptographic key.  Such an algorithm combines all the bits of input and produces a key of the desired length.  By using a key derivation function you could require a 64 character minimum password, and combine all that material to produce a much stronger key - $96^{64}$ is significantly stronger than $96^{16}$.


Difference between Hash function and Random Oracle

The random oracle model is a way to analyze schemes that need a hash function; essentially, you replace the hash function with some black box (the random oracle) which evaluates a function selected uniformly at random from all functions from its input domain to its output domain. Equivalently, it takes input and gives output like this:

If you give it an input it hasn't seen yet, it gives you an output selected uniformly at random from its possible outputs. It then saves that output for later use.
If you give it an input it has seen before, it gives you the output it saved previously.

No actual hash function is a random oracle. Hash functions are deterministic; for a given hash function, $H(x)$ in one problem is equal to $H(x)$ in some other problem. With a random oracle, this is not the case: the function used is random. Random oracles are often used to approximate hash functions in security proofs, but no actual hash function can be a random oracle because anything used in a real, sensible security scheme must be a deterministic algorithm.

Random oracles aren't used when analyzing hash functions, they're used when analyzing other things. Unfortunately, for any real, deterministic hash function $H$, you can come up with schemes which are secure when used with a random oracle but not when used with $H$. Essentially, you construct a signature scheme that hashes a bunch of stuff and checks if the hash of $x$ is $H(x)$ for all the $x$ it tested; if not, it outputs a normal signature, if so, it outputs a normal signature and then sticks the private key on the end. With a random oracle, it's extremely unlikely that the hashes represent any pre-specified function (as they're completely random), but if you use $H$ they will obviously always fit the relationship. So, random oracles are an imperfect model, and we generally prefer security proofs not relying on them.


The fact that block ciphers can be run in stream like modes diminishes the need for stream ciphers. Add to this the fact that a number of processors today are being built with instructions to speed up AES, and even the performance advantages of stream ciphers is less.

RC4 is still used today, but has shown significant weaknesses and is therefore not recommended in newer designs. The eStream project was put forth to develop new stream ciphers and the ciphers picked for the final portfolio have been well analyzed. They are still probably too new for general acceptability, but I have started to see some of the being used in the wild, especially Salsa20.

Personally, if I were designing a new system and needed a stream cipher, I'd use AES in GCM or CCM. That way you get the streaming capabilities of CTR mode, with authentication.


Do reversible black box obfuscators exist?

By "reversible program" I assume you mean an injective function.

The answer to your question is no, there is no black-box obfuscator for the set of injective functions.

The idea is to make an unobfuscatable function invertible using the Feistel trick. More formally, if $g: \{0,1\}^n \to \{0,1\}^n$ define $Feistel_g : \{0,1\}^{2n} \to \{0,1\}^{2n}$ as

$$Feistel_g(x,y) = (x, g(x) \oplus y).$$

$Feistel_g$ is invertible regardless of $g$ (and a similar thing works when the input/output lengths of $g$ are different).

Let $\mathcal{G}$ be the unobfuscatable function family from the Barak et al paper. Then define

$$Feistel_\mathcal{G} = \{ Feistel_g \mid g \in \mathcal{G} \}$$

Then this family consists of only invertible functions. Furthermore it is black-box unobfuscatable because black-box access to $g$ can be simulated given black-box access to $Feistel_g$ (and vice-versa). And oracle access to  $(Feistel_g)^{-1}$ is redundant since $Feistel_g$ is its own inverse.


(There are to date no attacks that compromise the pseudorandomness of the compression functions of MD5 or SHA-1.)

  Has this changed since then?

Not as far as I know.

  It seems to me that in practice hash functions are usually considered to be PRFs. Is this valid and are commonly used compression functions all PRFs?

Note that there are two ways to define the PRFness of a hash function. A compression function is a function $f(x_1, x_2)$, where $x_1$ is the state input (either the IV or the previous block output) and $x_2$ is the current data block. You can take either $g_k(x) = f(k, x)$ of $g'_k(x) = f(x, k)$ when you consider whether it is PRF.

For SHA-1 and SHA-2 $f(x, k)$ is relied on when using the SHACAL ciphers. (Or actually, SHACAL relies on them being pseudorandom permutations, PRP.) However, for HMAC the opposite, $f(k, x)$, matters (as well, see comments).

E.g. since there are no known attacks on full SHACAL-2, you could assume that SHA-256 is PRF up to around $2^{128}$ calls (birthday bound for distinguishing PRP from PRF). However, that would not necessarily apply to the way it is used in HMAC... but there is no known attack on that either.

SHA-3 has more explicit security claims regarding its pseudorandomness, but it does not use a compression function in the normal sense, but a sponge function instead.

TL;DR: the compression function of the currently secure hash functions, like SHA-256, seems likely to be PRF, though it is not a property that the designers claimed. The compression function of the weak MD5 or SHA-1 might still be PRF, but I would not rely on it if I did not have to, since their use is deprecated. And if you want something with security claims regarding this, you could look into SHA-3 instead.


How can I (generally) calculate a stream cipher computation cost?

For any typical stream cipher (including block ciphers in streaming modes like CBC / CFB / OFB / CTR), the time needed to encrypt a message consists of two parts:

the time needed to set up the cipher, which is approximately constant, and
the time needed to encrypt a chunk of the message (also approximately constant), multiplied by the number of chunks in the message (rounded up).

Most ciphers will process the message (or at least generate the keystream) in chunks of more than one bit at a time.  For block ciphers in streaming modes, the chunk size will typically equal the block size of the underlying block cipher.  For dedicated stream ciphers, the chunk size may vary, even between different implementations of the same cipher.  For some examples, RC4 generates its keystream in chunks of 8 bits, whereas Trivium can generate anything from 1 to 64 bits at a time, depending on how strongly the implementation is parallelized.

In any case, the typical runtime will be of the form $a + b \lceil n / c \rceil$, where $a$ is the setup (+ teardown) time, $b$ is the time per chunk, $c$ is the chunk length and $n$ is the message length (in appropriate units, typically bits or bytes).  Asymptotically, this will be ${\rm O}(n)$.

One peculiar corner case is that, for ciphers that require the message to be unambiguously padded to a multiple of the chunk size (such as block ciphers in CBC mode), messages that already happen to be a whole number of chunks long will typically need to have an extra chunk appended, so that the time cost becomes of the form $a + b \lceil (n + 1) / c \rceil$.

Also, it should be noted that these are all theoretical timings.  In the real world, if you graph the time needed to encrypt messages of varying size on a real CPU, you're likely to see all sorts of weird jags, kinks and noise due to things like cache misses, branch prediction, microcode optimizations, interrupts, concurrent threads, etc.  On a large enough scale, though, the overall pattern will still generally look approximately linear in the message length.


The output of hash functions is commonly indistinguishable from random (randomness of the output is not a direct requirement for secure hash functions); this is certainly the case for SHA-256. So trying to find any correlation between inputs should be impossible - if there is some kind of pattern on different inputs it was created by chance.

If you would find such a correlation then the hash function would be considered broken. Deep learning should therefore be considered another way of attacking the hash using machine learning, as the comment from SAI Peregrinus indicates.

An important note in this case is that Merkle Damgard constructions such as SHA-256 are susceptible to length extension attacks, which means that SHA-256 is not a random oracle. That won't help you finding a pattern in separate input messages so I don't think it should influence this answer.


If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy?

A deterministic function $f(X)$ of a random variable $X$ never has greater entropy than the original random variable $X$.

(Side note: If you're not familiar with the technical terms random variable and expectation, or the definition of entropy in terms of them, I recommend you read up on some elementary probability theory first—the rest of this post will not make sense without these keywords!  In the sequel, ‘entropy’ can be taken to mean Shannon entropy or min-entropy—both work, and coincide on uniform distributions, but cryptography works primarily in min-entropy.  See this answer for a brief discussion of what entropy means from a crypto perspective.)

At best, if $X$ is a random $k$-bit string with uniform distribution and thus $k$ bits of entropy, the maximum possible, and if $f\colon \{0,1\}^k \to \{0,1\}^k$ is a permutation (a.k.a. bijection), then $f(X)$ also has $k$ bits of entropy.  If $f$ is not a permutation, then $f(X)$ has strictly less than $k$ bits of entropy—although perhaps not much less.

In this case, $f$ is SHA-256, which we might model by a uniform random choice of map $F\colon \{0,1\}^k \to \{0,1\}^k$.  There are almost certainly fewer than $2^k$ distinct outputs, because very few such possible values of $F$ are permutations.  Specifically, fix an output $y \in \{0,1\}^k$; for each input $x \in \{0,1\}^k$, we have $\Pr[F(x) = y] = 1/2^k$, and $F(x)$ is an independent random variable for every $x$, so
\begin{align*}
  \Pr&[\exists x. F(x) = y]
     = 1 - \Pr[\forall x. F(x) \ne y] \\
    &= 1 - \Pr[F(0) \ne y]\,\Pr[F(1) \ne y]\cdots\Pr[F(2^k - 1) \ne y] \\
    &= 1 - (1 - 1/2^k)^{2^k}.
\end{align*}
which, by linearity of expectations, is also the expected fraction of distinct outputs.  As $k \to \infty$, this converges to $1 - e^{-1} \approx 0.632$.

Thus, over a uniform random choice of $F$, the expected entropy of $F(X)$, or $\mathbb E_F\bigl[H[F(X)]\bigr]$, is about one bit less than the entropy of $X$, or $H[X]$, where $H$ is the entropy operator.

What about iterating SHA-256?  Do we lose a bit of entropy every time, so that $\operatorname{SHA-256}^{256}$ has zero entropy?  No.  If we independently chose another function $G\colon \{0,1\}^k \to \{0,1\}^k$, then over a uniform random choice of $F$ and $G$, the expected entropy of $F(G(X))$ might be about two bits less than the entropy of $X$.  But that's a bad model for iterating SHA-256, because we are restricted to the case $F = G$, in which case $F$ and $G$ are as far from independent as possible.

Rather, there's a good chance that for any fixed function $F$, there are many cycles on which $F$ is a permutation, and restricted to which $F$ thus preserves entropy.  There's usually one main big cycle, which lends itself to a drawing of a giant hairy rho: $\rho$.  In the limit as $\ell \to \infty$, $F^\ell(X)$ maps $X$ to an independent uniform random point on one of the cycles, the choice of cycle being weighted by the number of points on and leading to that cycle.

But in practical terms for cryptography engineering?  Usually we treat $\operatorname{SHA-256}(X)$ as a uniform random variable independent of everything else in the system (except where length extension attacks might be relevant) with entropy equal to that of $X$, or 256, whichever is smaller.


Identifying identical files without reading them completely

It will never be secure to hash just part of a file. It will always be trivial to generate two distinct files which produce the same hash. (Just look for which parts of the file the lazy hash doesn't touch and modify those sections.)

If you don't need security, then you might be able to come up with some scheme that works most of the time for "natural" (not maliciously crafted) files.

One could hash the first $n$ kilobytes, prefixed with the file size, to generate a PRNG seed. Then you can use the chunk-reading strategy using the RNG to choose random starting positions for each chunk. The chunk size doesn't matter, other than for performance.

Just like how there is no one ultimate file compression algorithm which works for any kind of file, there isn't going to be one universal algorithm for the type of application you describe.

(Any compression algorithm will work well with some file contents and poorly, inflating the file size even, for other files. You get the best results by choosing an algorithm you know will be well suited to the type of data you're trying to compress.)

If you knew your target file formats, then you could design a lazy hash meant to specifically work for that format. For example, you could start reading from a position other than zero if you knew all files shared a common header or that files tended to start with the same boilerplate text.

Actually, store multiple hashes. One of the first 10kb of a file, one of the last 10kb, and one of a random sample of chunks. Check the start and end of the file for differences first so you can bail early by detecting files that contain different beginnings/ends. Fallback on the slower one if they both match. (Or just use one or two partial checksums along with a fallback to a strong hash of the full file, as I assume most software like this does.)

If you're interested in deduplicated file backups, look into Tarsnap.

Files are stored as a sequence of chunk hashes instead of as a sequence of bytes. Chunks values are also stored, but the hashes are used are used as keys in a lookup table to index those chunks. This adds overhead for random data, but allows one to store only one copy of each unique chunk even if it is part of multiple files or appears more than once in the same file.

If you want to use such a system, then just use Tarsnap or something like it. It's a big wheel to reinvent, so you're probably safer using a mature open source project. (I don't use it personally, though. And it's been a long time since I read about it.)


What algorithm could/should be used to encrypt files for storage on untrusted servers?

The question still lacks detail, so this answer will be equally vague and hand-waving.

Any modern cipher exceeds consumer disk/network IO speeds by a significant margin, you can pair any modern block cipher (AES is probably the best choice here) with a streaming mode of operation such that the file size is left intact, such as CTR or CFB. However, you still need integrity on top, so you also want a fast and strong hash function to use as a HMAC (or use AES in an authentication-capable mode, but such modes are not very widespread yet). A good hash function would be SHA256 (reasonably fast).

There is no "best" algorithm, there are only those that meet your needs and those that don't. Your needs are security and speed - choose accordingly. I gave some fairly generic suggestions above.

Of course, the better choice would still be to use something that's already production-ready, such as OpenSSL. This way you don't need to implement it yourself and just have to learn the API and make a few function calls at either end of your network sockets, and you don't have to worry about security problems (or at least, not as much).

Again, you should not be implementing cryptography if you don't know what you are doing, so your comments such as "I wish I could know that by my self" are worrying to say the least...


AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.

Related key attacks could happen when AES is used within a construction such as a hash function, where the output of one round is used as a key for the next round.

As far as we know now, quantum computing won't have as much as an impact on most symmetric algorithms as it does on asymmetric cryptography (that usually relies on specific mathematical problems that can be solved using quantum computers).

As mentioned, the best generic attack on symmetric ciphers, Grover's attack, about halves the key strength. But you need a lot of qbits to create the attack. Of course, there may be new attacks found that are particular to a specific block cipher, but as far as we can see now, most constructs seems pretty secure against quantum computers. That means that a 256 bit key will still deliver 128 bits of security against analysis using quantum crypt-analysis.

That means that there seems little reason to double the 256 bit key strength, as 128 bits of security are considered plenty against any attack that require such kind of order of operations.

If you require 256 bits security with quantum computers (why?) you could consider Threefish-512 - an algorithm actually designed to deliver that kind of security.


Proof that no DES key makes encryption identity

To throw something, here are simple proofs for 2-4 rounds, applicable to almost any Feistel Network. Some notation: $F_i$ denotes $i$-th Feistel round without swaps, $f_i$ denotes the Feistel function at $i$-th round, $S$ denotes the swap.
Since the initial permutation IP and the final permutation FP are inverses of each other, we can strip them away: for any bijection $P$:
$$P^{-1} \circ G \circ P = Id ~~~\Leftrightarrow~~~ G = Id.$$
We will use this trick later.
(2 rounds)

Consider a 2-round Feistel network (like in DES, with no swaps in the beginning and in the end), denote it by $G$. We want to check if it holds that
$$\forall a,b \in \mathbb{F}_{32} ~~~ G(a,b) = a,b.$$
The right output half is equal to $a \oplus f_1(b)$. This can not always equal $b$ for any $a$ (consider two distinct $a$).
(3 rounds)

Consider a 3-round Feistel network. The right half in the middle is equal to $a \oplus f_1(b)$ (from the input) and to $a \oplus f_3(b)$ (from the output). It follows that $f_1(b) = f_3(b)$ for all $b$. We can now use the trick again and remove symmetrically the first and the last round and the two middle swaps. We end up with $F_2(a,b) := (a \oplus f(b), b)$. Due to the nonlinearity of $f$ in DES, there exist no keys such that $f_2$ (and so $F_2$) is an identity (the key is only xored at the input of $f$).
(4 rounds)

Note that $(S\circ F_1)(a, b) = (b, *)$, and $(S \circ F_4^{-1})(a, b) = (b, *)$, where $*$ denotes a wildcard. So it sufficient to show that there are no 2-round FN that for all $b,x\in \mathbb{F}_{2^{32}}$ always map $(b, x)$ to $(b, y)$ for some $y \in \mathbb{F}_{2^{32}}$. For the two middle rounds we get 2 equations:
$$
b \oplus f_2(x) = y,
$$
$$
b \oplus f_3(y) = x.
$$
If in the input we change $b$ to $b\oplus \delta$ and don't change $x$, then $y$ has to change to $y \oplus \delta$ (from the first equation). From the second equation, we must have
$$b \oplus \delta \oplus f_3(y\oplus \delta) = x,$$
and so
$$f_3(y \oplus \delta) \oplus f_3(y) = \delta.$$
Since this must hold for all $y$, we obtain that $f_3$ must be a XOR with a constant, which obviously does not hold for DES rounds.


What happens if the first input block is identical to the key in DES?

DES encrypts the block, or decrypts it if it is used in the other direction.

DES is a block cipher and therefore a keyed permutation. The key is used to choose the permutation. In this permutation every value of the input is mapped to a pseudo-random output value of the same size. However, how the permutation is chosen is quite different from performing the permutation. Because of that it is unlikely that there are any mathematical properties exposed when encrypting the same data as the key.

From the practical side: before the DES key is used the 56 (not 64) bits undergo a subkey derivation to derive a separate (but related) key for each round. Already at this stage the key won't be equal to the input bits anyway. If DES had weaknesses in such a way that this kind of input would expose the key then it would be considered broken - and despite the key size and existence of other weak keys, it isn't.

That all said, encrypting the key is not considered very useful. Sure you can encrypt it, but you'd need to know the key to decrypt it again. If you already know the information then there is little need to do so. You could possibly use it to confirm a good key guess, but in that case CBC-MAC over a random block of data would arguably be better. It would also scale to other key sizes than the block size, for one. Moreover, it would not treat the key as plaintext data.


Quantum Cryptography Algorithms Implementations

The Post Quantum Cryptography is a type of cryptography that lies on physics properties instead of mathematics , it has many algorithms and implementations like NTRU , McEliece , SIDH ... etc. But there is a difference between Post Quantum Cryptography and Quantum Cryptography

Let's try to classify this:

Quantum Privacy Amplification, which is the honest name of the better known Quantum Key Distribution. It was formerly the meat of Quantum Cryptography, and has become a sub-field of that. It matches “(re)lies on physics properties instead of mathematics” well. More precisely, the aim is establishing a trusted shared secret key between parties, with security relying on:

a Quantum physics model of the devices used;
mathematical facts (contrast with other cryptography, which additionally relies on a few mathematical conjectures);
a shorter trusted shared secret¹ key (hence Privacy Amplification).

Quantum Computing, which aims at performing useful² computing tasks that today's ordinary computers can't do. It uses physical devices directly relying on Quantum physics effects, without the abstraction/limitation of Boolean logic as today's computers do. There are many burgeoning and hopefully cross-fertilizing sub-fields, in which I vaguely distinguish three levels:

Experimental+theoretical³ physics to get these things going at the atomic scale and avoid the accumulation of errors; this subdivides according to technology and level of abstraction.
Study and even development of quantum algorithms to run on hypothesized quantum computers, with a subfield Quantum Cryptanalysis aiming at attack of cryptographic algorithms (not to be confused with attack of cryptographic hardware using quantum sensors)
Development of classical software tools running on classical computers to support development and simulation of quantum algorithms.

Post-Quantum cryptography, which develops cryptographic algorithms that run on ordinary computers and hopefully would resist Quantum Cryptanalysis. This field has “many algorithms and implementations like NTRU, McEliece, SIDH…”.

Sticking to the three disjoint things on-topic for crypto.SE, there is a lot of software involved in Quantum Privacy Amplification, Quantum Cryptanalysis, and Post-Quantum Cryptography. Some is on Github or similar. But as a matter of policy we generally do not recommend software.

¹ In some KPA/KQD setups, that initial key would only need to be kept secret until first used by the first party doing so, and could be public in the part of the plot where some old-fashioned courier then carries it to the second party by a process insuring its integrity. However, because couriers are slow, practice is to send the initial key in advance. In that case it must be secret while the courier moves it, else we loose security reducible to having a valid quantum model of the devices used.

² There are recent well-substantiated claims that we can do things with today's bleeding edge quantum computers that today's classical computers struggle at. However these things are not, yet, the kind of things ordinary heavy users of computing want to do. In particular, these things are as far as can be from cryptanalysis and “big data”. To caricature, today's bleeding edge quantum computers excel in the study of quantum phenomenons, by implementing them.

³ The two are hard to distinguish these days. Before 2020, “wear protective gear” did quite well, for guys in experimental mode need to protect themselves from liquefied gaz, laser, acid and other toxics… and protect their work and tools from the contamination their body generates.


How should I calculate the entropy of a password?

Entropy is a measure of what the password could have been so it does not really relate to the password itself, but to the selection process.

We define the entropy as the value $S$ such the best guessing attack will require, on average, $S/2$ guesses. "Average" here is an important word. We assume that the "best attacker" knows all about what passwords are more probable to be chosen than others, and will do his guessing attack by beginning with the most probable passwords. The model is the following: we suppose that the password is generated with a program on a computer; the program is purely deterministic and uses a cryptographically strong PRNG as source of alea (e.g. /dev/urandom on a Linux system, or CryptGenRandom() on Windows). The attacker has a copy of the source code of the program; what the attacker does not have is a copy of the random bits that the PRNG actually produced.

Entropy is easy to compute if the random parts of the selection process are uniform (e.g. with dice or a computer with a good PRNG -- as opposed to a human being making a "random" chance in his head). For instance, if you have a list of 2000 words and choose one among them (uniformly), then the entropy is $S = 2000$. Entropy is often expressed in bits: an entropy of $n$ bits is what you get out of a sequence of $n$ bits which have been selected uniformly and independently of each other (e.g. by flipping a coin for each bit); it is a simple logarithmic scale: "$n$ bits of entropy" means "entropy is $S = 2^n$" (and the attack cost is then $2^{n-1}$ on average).

If you think of a password as two halves chosen independently of each other, then the total entropy is the product of the entropies of each half; when expressed with bits, this becomes a sum, because that's what logarithms do: they transform multiplications into sums. So if you take two words, randomly and independently (i.e. never ruling out any combination, even if the two words turn out to be the same), out of a list of 2000, then the total entropy is $2000\cdot2000 = 4000000$. Expressed in bits, each word implies an entropy of about 11 bits (because $2^{11}$ is close to $2000$), and the total entropy is close to 22 bits (and, indeed, $2^{22}$ is close to $4000000$).

This answers your question about digits: a decimal digit has entropy 10, as long as it is chosen randomly and uniformly and independently from all other random parts of the password. Since $10 = 2^{3.321928...}$ then each digit adds about 3.32 extra bits to the entropy.

If a human being is involved in the selection process then calculating the entropy becomes much more difficult. For instance, if a human chooses two digits and the first digit is '4', then the probability that the second digit is '2' is quite higher than $\frac1{10}$. It could be argued that it is also difficult for the attacker: he will also have more work to do to sort the potential passwords so that he begins with the most probable. But this becomes a psychological problem, where the attacker tries to model the thinking process of the user, and we try to model the thinking process of the attacker: it will be hard to quantify things with any decent precision.


Can OTP be made practical by using stretched hash algorithms?

You are creating a key stream using a hash function. This is often called a stream mode of operation (although it doesn't seem to be a well defined term). This is a known method of creating a key stream.

An OTP requires the key stream to be completely random. This is because it would otherwise be possible to brute force the key. If you can brute force the key then the scheme obviously does not provide perfect secrecy; meaning the scheme is not an OTP.

Problem is that it is extremely unlikely that there are two passwords that would provide a stream for which the resulting plaintext makes sense. So if you find the password you're pretty certain that you've hit gold. The longer the decrypted plaintext is, the more sure you are that the password is correct.

  It should be impossible to verify that a given password is correct though as all passwords create an OTP with a different outcome producing possible legit words.

Seems contradictory to the last paragraph. It's not correct.

  The amount of computing power is also an advantage as the creation of such a big key can take a lot of time and is memory expensive.

Perfect secrecy is the notion that the scheme cannot be broken regardless of the amount of resources.

Instead of using a hash function we normally use a block cipher such as AES. If you combine that with a counter then you have AES-CTR. CTR is an extremely common way of building a stream cipher.


Don't roll your own. (AKA: The first rule of cryptography.)

Do not create your own cipher, do not implement a cipher.

  Is there a link wherein i can find implementation of AES using standard C library ?

You can find a C implementation of AES in The Design of Rijndael, Section E, page 221. Test vectors are also provided in Section D. However, it is not recommended to use this implementation because it is vulnerable to
cache timing attacks:

Cache-timing attacks on AES.: Dan J. Bernstein
Cache Attacks and Countermeasures: the Case of AES, Dag Arne Osvik, Adi Shamir and Eran Tromer
Faster and Timing-Attack Resistant AES-GCM: Emilia Kasper and Peter Schwabe

  Do i have to use some hashing scheme along with AES ? If yes, which one ?

You need a hashing scheme only if you want to provide authenticity/integrity (see MAC schemes, for more reading about this see here).
Thus having a hashing scheme along is completely independent to having your AES implementation. You might however want to have a look at AES with GCM, EAX or CCM  to provide authentication.

For hashing function, if you go by the standards, it is advised to use at least SHA-256 or even better SHA3-256 (as specified in FIPS 202 by the NIST).

  Is it a good idea to validate my AES C code with the NIST test vectors

It is more than a good idea. It is required. However, making your implementation work and produce the same results as the test vectors does not guarantees you that your implementation is correct (it does still provide you a strong confidence that your code might be correct). You have to check that every parts of your implementation matches the specifications of the algorithm.

  Do you recommend using a encryption library instead ? If so where can i find it ?

Using a encryption library is highly recommended. It will prevent you from suffering from cache timing attacks and other nasty things. It also guarantees that the code is correctly implemented. As for which library to use, at the time of the post (October 2016), you can have a look at OpenSSL, Libsodium or NaCl.


What are the subsequent inputs to the DES key schedule after round 1?

As you already correctly observed, to get $k_1$, you rotate $C_0$ and $D_0$ left to obtain $C_1$ and $D_1$ and apply PC-2 to $C_1$ and $D_1$.

To get $k_2$, you simply rotate $C_1$ and $D_1$ left to obtain $C_2$ and $D_2$ and apply PC-2. To get $k_3$, you rotate $C_2$ and $D_2$ left to obtain $C_3$ and $D_3$ and apply PC-2. This continues until $k_{16}$. Also see Figure 3 in the Wikipedia article on DES for a graphical illustration. The round keys $k_1, \dots, k_{16}$ are then used in the round function of the respective round.


Argon2 or scrypt instead of PBKDF2 with AES

Such quantom attacks are entirely theoretical, we are nowhere near having quantom computers brute force passwords. It is thus difficult to compare.
Argon2 might be harder to implement on quantom computers but also the others are so far from being practical it seems pointless to try and compare how these would fair against a mythical adversary. In general quantom computers can break passwords in a square root of the effort and that is true for all the mentioned algorithms.

However there are far more practical attacks to consider, mainly using GPUs and dedicated hardware. That is where the advantages of argon2 over bcrypt or PBKDF2-SHA1 for instance come into play. Argon2 requires not only CPU but also RAM, while the others hardly use memory. This deminishes the attacker advantage of dedicated hardware or GPUs.

I stillb consider bcrypt a safe option, but assuming you have available RAM you will get a better slowdown factor against a sophisticated adversary by using argon2.


I know that theoretically, the security of the setup when used correctly is at least as secure as the most secure.

That's true if they use independent keys.  If they use the same key, the security of the cascaded cipher may be much worse.  Consider the case where cipher B happens to be the exact inverse of cipher A with the same key.
However, that doesn't answer the question you asked (as in the above example, the key is perfectly secure; the plaintext not-so-much):

Can a broken cipher ever reveal the key directly?

Obvious yes.  In the most trivial case, consider the 'cipher' the appends the key to the plaintext, and outputs that.
Even if we disallow such obvious egregious examples, we could have a cipher B that encrypts securely, but appends a 'tag' which is a function of the ciphertext and the key (which is common with combined mode ciphers) - if the computation of the tag was weak enough, you could recover the key just with the ciphertext and the tag, even if the plaintext given to cipher B was perfectly secure.


Is it possible to securely combine multiple hashes without hashing them?

What you're looking for is called a Merkle tree. BLAKE2b, a modern hash and an evolution of one of the SHA-3 finalists (BLAKE), supports tree hashing natively.

Edit: This may or may not actually be what you're looking for. Initially hashing the tree will take more work ($\mathcal{O}(n\log(n))$ operations) than just hashing the set of hashes, but subsequent partial updates will take less work ($\mathcal{O}(\log(n))$ operations). If you're ever updating the list, a Merkle tree is probably more efficient.


How to pad messages with large amount of padding

As you note, PKCS7 padding isn't designed to do exactly what you want; it's really designed to allow you to pad up to the next multiple of the block size, that is, to the next multiple of 8 or 16.  That it does rather well; however, it's not designed to do what you want with it.

I would note that for block ciphers, as long as you also include a good Message Authentication Code or some other way of ensuring integrity, that the actual padding method isn't critical to security; the AES encryption itself will ensure that there is no information leakage other than message length, and the MAC will ensure that, if the attacker tries to play games with modifying the message, well, that'll always result in a MAC failure, and so that attacker won't learn anything).  This is true even if you try to design a padding scheme specifically to leak information (assuming, of course, that your padding method doesn't use the key).

Hence, the only real constraints on your padding scheme is:

Not to leak any information do to the message length (that's the one thing AES does not disguise)
Be able to remove the padding to obtain the original message without ambiguity

As long as you follow those two constraints, you're golden.  One obvious way to meet both goals is to pad the message out to a fixed length; and then add a 2 (or 4) byte 'original message length' at either the beginning or the end of the message.

I'm assuming that you aren't concerned about interoperability with existing systems; if you are, then you'll need to live within whatever system they are using.

And, the above answer "the padding method is not critical" applies only to block ciphers along with some MAC); when you consider other cryptographical primitives (say, RSA), the padding method does become important in those cases.


How to use CPA on AES128-CBC with constant Key and IV to leak info?

The strategy you need to apply here, is basically the same as with most other oracle attacks:

You construct a message such that you can verify your guess for a single byte, then you adapt to guess the next byte until you are done.

In this specific case you would pick the user-controlled message length such that one byte of the cookie is in the same block as the tail of your message, encrypt that. Then you make your input one byte longer and try all possible values for the cookie byte until the corresponding block is equal to the encryption of the cookie byte.

Now you repeat this process for the second byte and so on.


How is ElGamal not secure under chosen ciphertext attack, but semantically secure in some cases?

Finding the corresponding $m'$ using $c'$ is a chosen cipher text attack. It's possible for a scheme to be semantically secure under certain types of attacks (perhaps something weaker like chosen-plaintext attack), but be broken under heavier attacks (like the chosen ciphertext attack you talk about).


How to hash similar strings to the same hash value?

As pointed out by poncho, a hash function $H(.)$ that would consistently map two close strings $s_1$ and $s_2$ to the same value, would have to map all the strings to the same value. (Since you could go from one string to the next and it would always have to map to the same value.) So this does not make any sense.

I think, like you also suggest, that an error correction code might be what you want. Such a code is defined by a set of codewords $\{c_1,...,c_n\}$ that are at a certain (Hamming) distance from each other, and around each codeword $c_i$ there is a Hamming sphere $S_i$ that contains those words that are closer to $c_i$ than to any other codeword. A perfect decoder will map any word to the closest codeword, so that it will map any word in $S_i$ to $c_i$. So if you have two words in the same Hamming sphere $S_i$, your decoder will decode them to the same codeword $c_i$. (You can easily generate such words by taking $c_i$ and randomly flipping a number of bits.)

This is not exactly the hash function you wanted, but I think this is as good as it gets if you want to map two words at a small Hamming distance from each other to the same value.


In some cases (such as XML or JSON files), the bytes being encrypted have very specific semantic requirements, such that a random byte sequence will be rejected with very high probability.

In the case of XML or JSON, I don't believe that's actually the case.

For example (example was the first JSON example I googled, simplified):

{
    "glossary": {
        "title": "example glossary",
        "GlossDiv": {
            "GlossList": {
                "GlossEntry": {
                    "GlossTerm": "Standard Generalized Markup Language",
                 }
            }
        }
    }
}

}

If the modification was, say, to 16 bytes in the string "Standard Generalized Markup Language" (or "example glossary"), changing that to a random 16 byte string (which is the appropriate modification model for XTS), with nontrivial probability all the bytes will be within the JSON string alphabet (and not "), and hence that change would not be detected, as the modified string would still be valid JSON.


Factor the modulus, $n$ which was given as 33, to yield $p = 3$ and $q = 11$.

The totient, $\phi$ is $(p - 1)(q - 1) = 20$.

The public exponent, $e$ is given as $13$.

Now compute the private exponent $d$ as the multiplicative inverse of $e \mod \phi$, so
$e^{-1}\mod \phi \equiv 17$.

The cipher text, $c$ is given as 8.

Finally compute the message, $M$ as $c^d \mod n \equiv 2$.

No algorithm has been published for factoring large numbers quickly, so the first step is what makes breaking RSA "computationally infeasible." Fast algorithms are known for all of the other operations.


Is there a downside to encrypting too much data with the same key?

Yes, but the answer is more or less embedded in the question here; you can only say that you encrypt too much data in case the secret key and / or plaintext becomes vulnerable.

Most modes of operation define how much data can be encrypted. This could mean real limits to the amount of data (approx. $2^{36}$ bytes or 64 GiB for AES-GCM) or it may be completely impossible to ever reach the limit (e.g. $2^{128}$ bytes or blocks of data).

When it comes to wasting resources: that's more a question of encrypting the wrong data rather than too much data.

And yes, failing to protect sensitive data is a sin as well. But that's a generic statement that also comes down to categorizing the data correctly.

First categorize the data, then find the right method to encrypt the amount of data that needs confidentiality. Encryption itself is not the goal.


Can one group the SHA-256 outputs depending on partial inputs?

Somewhat simplified, if that were possible, you would have found a vulnerability in SHA-256. The kind of attack you're talking about is called a preimage attack, ie figuring out information on the original message from the hash. There have been some attacks of that kind against a weakened version of SHA-256 but no successful ones against the standard algorithm.

Of course your MD5 only adds 128 bits of entropy and your other data one (either all a or all b), but a brute force attack against 129 bits isn't what you're looking for either.


LFSRs are very useful as building blocks of ciphers, with some nonlinearity introduced. For example Trivium is a very strong and fast cipher, which includes a little amount of quadratic nonlinearity in 3 coupled LFSRs.

An example of bad use of LFSRs--and by no means the only one--is the A5 series of ciphers, of GSM fame, where majority clocking does not include enough nonlinearity/unpredictability.


Security issues with computing parallel hashes?

Are there security problems with such a design that wouldn't exist with a normal hash algorithm?

At least not for collision resistance.

Suppose you could come up with a collision for the composite construction $H_p$ based on the hash function $H$. Then you'd have two inputs $x\neq x'$ such that $H_p(x)=H_p(x')$. Then either there is a collision on the final hash invocation and we can reconstruct the relevant inputs following the description of $H_p$. Alternatively all the inputs to the final invocation are equal between $x,x'$ and then the slices that differ produced a collision in $H$ which we can reconstruct.

So every collision for $H_p$ implies a collision for $H$, but because we assume $H$ to be collision-resistant there is no efficiently findable collision for $H_p$.


The other answers provide very good lists of reasons not to use Twitter as an entropy source.  What follows is the flip side of your question:-

Why would you want to?

Tweets are typically read on tablets, PCs and phones. All of those have access to hardware entropy sources that can produce oodles of truly random bits for seeding anything. The zeitgeist is that you aim for 128 or 256 bits of entropy and then seed a cryptographically secure pseudo random number generator. That will meet all of your common random number needs.

You have seeding sources such as:-

The RdRand instruction built into  most modern CPUs.
/dev/*random as part of the various favours of *nix.
Microsoft's Cryptography API.
The cameras built into phones and tablets.

There's not a lot of merit in pursuing Tweety entropy, other than for academic purposes.


WOTS+: Why does it XOR before running data through the hash function?

It allows the security of the construction to be reduced to second-preimage-resistance, rather than collision-resistance. This is a significant distinction, since brute force against collision-resistance is $2^{n/2}$ while brute force against second-preimage-resistance is $2^n$. In short, this XOR trick allows signatures/keys in the scheme to be half as long for the same level of security.

It is hard to express why the XOR trick helps the proof, without getting into the weeds. But here is a sketch of how to prove security of a Winternitz-like scheme.

The security reduction $\mathcal{S}$ plays the role of an adversary trying to break second-preimage resistance. It has to provide public keys and signatures to an adversary $\mathcal{A}$ trying to break unforgeability. In the event that $\mathcal{A}$ produces a signature forgery, $\mathcal{S}$ should break second-preimage resistance.

In plain Winternitz, we imagine a hash chain starting at $x_0$ and with $x_i = f(x_{i-1})$. The public key is $x_n$. The reduction $\mathcal{S}$ will guess an index $i^*$ such that $\mathcal{A}$ will ask for a signature value later than $i^*$ in the chain, but will generate a forgery consisting of a value at or before $i^*$ in the chain. If the guess is correct, then we want $\mathcal{S}$ to break second-preimage-resistance of $f$ somehow.

$\mathcal{S}$ is itself trying to break second-preimage-resistance. It will request a first-preimage $a$ and try to find a second preimage with $a' \ne a$ and $f(a) = f(a')$. It needs to incorporate $a$ into the hash chain somehow --- ideally, set $x_{i^*} = a$, so that if the adversary computes a preimage of $x_{i^*+1}$, it will be a second-preimage of $a$.

But if $x_{i^*}=a$, then what are $x_0, \ldots, x_{i^*-1}$ such that $x_i = f(x_{i-1})$? The reduction $\mathcal{S}$ can't make a consistent chain. It receives $a$ externally and would need to compute a preimage of $a$.

However, if we augment the scheme in the style of W-OTS+, we have additional $r_i$ values and $x_i = f(x_{i-1} \oplus r_{i-1})$. These $r_i$ values allow the reduction to "patch things together."

The reduction $\mathcal{S}$ chooses $x_0$ and computes a forward chain until $x_{i^*}$, as usual. Then it receives $a$ externally, and chooses $r_{i^*}$ so that $r_{i^*} \oplus x_{i^*} = a$. This means that the input into the next $f$ is $a$. This means that to make a forgery, $\mathcal{A}$ would have to find a preimage to go with $a$. From this point, the rest of the chain is computed normally.

So, the extra XOR just gives the reduction extra flexibility to insert a "trap" into the hash chain --- ensuring that a particular $a$ is used as input to $f$ in the chain, even when the reduction algorithm $\mathcal{S}$ didn't itself choose $a$. And this is exactly what's needed to reduce the signature security to second-preimage resistance.


The Decisional Diffie-Hellman assumption, on which the key-exchange would be based on does not hold in $\mathbb{Z}_q^*$. The reason is that the Jacobi symbol "leaks" information about the shared key. Therefore one, instead, works with the subgroup of $\mathbb{Z}_q^*$ of order $p$, which is intuitively obtained by "quotienting out" this information. (This group is sometimes called the Schnorr group.) You can read the details on why DDH doesn't hold here (Exercise 2).


What type of encryption is this homebrew "encyption algorithm"? ${}$

What type of algorithm is this?

The best capturing for this algorithm that I can see would be as "mode of operation for a tweakable block cipher" with the tweakable block cipher being the one that has keyspace size $(64!)^{64}\approx 2^{18943}$ and in its current representation uses (at least) $64^2\cdot 6=24576$ bits for key representation. The tweak size is 64 as is the message and ciphertext space. Key decoding then works by partitioning the key into 64 equal-sized strings and then using each string to identify one permutation over 64 elements. Encryption works by selecting the permutation indicated in the tweak and applying it.

Using the notation $E^{\text{Tweak}}_{\text{Key}}(\text{PlaintextLetter})$ the mode is then $$C_0=E_K^0(P_0)\quad C_i=E^{C_{i-1}}_K(P_i)$$ for a given plaintext sequence $P_i$ and the corresponding ciphertext sequence $C_i$ and the key $K$.

  How weak is it against modern day cryptanalysis and what methods would be used to break it?

This construction has four main problems for modern cryptography:

Ridiculous keysize (for symmetric cryptography). It takes 2.3kB to represent the key, normally our keys use 32 bytes which is plenty (because you can't search $2^{256}$ fully).
Small block size. This is a problem in and of itself as an attacker can just build a dictionary of the input-output pairs by making a sufficient number of block cipher queries (this is part of the reason why modern block ciphers use 128 instead of 6 bit blocks).
Deterministic Encryption. The given encryption scheme cannot be CPA secure, because it is deterministic. That is an attacker can recognize whether two encryptions yield the same value. Even worse, this scheme has the same issue as CBC (the best one could hope for in online deterministic encryption), namely it leaks prefixes. If I encrypt abcde and then encrypt abcgh under the same key, the attacker can see that the messages were equal up to abc.
Lack of authentication. In theory one could think about fixing the previous point by forcing $P_0$ to be a random value (that's what CBC does). In this case this construction might be secure against CPA attackers. But of course it still isn't secure against the most standard adversary model in modern cryptography: CCA secure, that is attackers who also get to ask for decryptions (with one exception input). To break CCA security when given a challenge ciphertext of one of two possible plaintexts an attacker would simply change the last ciphertext letter and ask for the decryption and use the first few letters to determine what plaintext was encrypted.

Also if you don't understand something in this answer, please just ask (in the comments) and don't be frightened if you think "it should be obvious" or something like that.


Key-Bijective Secure Symmetric Encryption Methods

You are asking for a function $h(m, k)$ such that for fixed $m$, $k \mapsto h(m, k)$ is a permutation, and for fixed $k$, $m \mapsto h(m, k)$ is a permutation.  Obviously $m$, $k$, and the output of $h$ must be in the same space.  Suppose they live in a group $G$ (written additively), e.g. they're bit strings interpreted in $\operatorname{GF}(2^n)$.  For any fixed permutations $\pi$ and $\sigma$, $(m, k) \mapsto \pi(m) + \sigma(k)$ satisfies this.  (It seems likely that this is the only shape $h$ can have, but I haven't ruled others out.)

However, you presumably have some security goals in mind.  For example, you probably want to require that $\pi$ and $\sigma$ be difficult to invert; otherwise, a known-plaintext attack would lead to key recovery from the ciphertext $c = h(m, k)$ by $(m, c) \mapsto \sigma^{-1}(c - \pi(m))$.  One option would be $x \mapsto (g^x - 1) \bmod p$ where $p$ is a large prime and $g$ is a generator of $(\mathbb Z/p\mathbb Z)^\times$; this is a permutation of $\{0, 1, 2, \dots, p - 2\}$, inverting which is tantamount to computing discrete logs.  (One could also use $x \mapsto x^3 \bmod pq$ for large secret primes $p$ and $q$, if one wanted a permutation with a back door.)

It might help to know what you wanted to use this for!


How to determine which type of transposition cipher I have?

However how do I determine which transposition cipher I would need to use? Am I right to assume this is definitely a transposition cipher also?

As you found out that the ciphertext has a similar frequency to the English letter frequency. This can lead to lots of possibilities

It can be a shift cipher, that is the generalization of the Caesar cipher $$c = m + k \bmod 26.$$ In the Caesar cipher, the $k=3$ is fixed. There are at most 26 candidates to test, not so far.

It can be a permutation cipher, that is there is a permutation $\pi$ on the alphabet that permutes the letters. The 1000 years old frequency attack work on this. You need to swap the top three letters and try to reveal some other. Since you have a long message this should be working very well. Actually, the substitution cipher is also a permutation cipher.

It can be any of the transposition ciphers since they are keeping the letter frequency, too.

Rail fence cipher
Try some possible rail lengths. It is a very weak cipher. The below is the Rail Fence histogram with rail size 3. This is exactly the same as Moby Dick's frequency since the letters are not permuted, just the positions changed. The same applies other transposition ciphers since they just transpose.

Scytale
The cylinder size cannot be too long. try some possible sizes.

Route cipher
Row size and route to read the letters are required. Don't expect the road to be too complex. Set a row size and test for well-known routes. spiral inwards.outwards, clockwise/anticlockwise, starting from the top right/top left, bottom right/ bottom left, etc.

Columnar transposition

 Guess the column size and look for digrams to determines the permutation on the columns.

Double transposition
This is hard to attack, it takes the result of the column transposition and applies another transposition. Still, we have computers, and once can test all values up to some limit and check for the string in the decrypted text. Linux's strings command can be helpful to distinguish those.

Myszkowski transposition
Just a modification of the Columnar transposition that deals with the reoccurrence of a letter in the key. Increases the key space a little bit.

Disrupted transposition

Grilles
This is one of the hardest ones in this series since the attacker needs to form the grille. Gaines book's chapter is advised. It has some variants.

We don't expect combinations since the combinations can hide the frequency.

Vigenère cipher
It is not expected to be Vigenère cipher, however, the Kasiski test can be used to test.

Online Tools

Crypto Tools 2
dCode.xyz
boxentriq

I also did;

The light gray is from the Moby Dick text, the medium grey is your text.
In a bar, a light grey on the top means that moby dick has a higher frequency, a medium grey on the top means that your text higher frequency, a sample Python code, and Moby Dick is here.
From here we can simply say that it cannot be Caesar or Shift Cipher since the frequency is very close to the real English frequency!.


What are the values of $w$ such that the corresponding $\text{Keccak-}f[25w]$ function is invertible (bijective)?

$\operatorname{Keccak-}\!f[25w]$ is defined, by the Keccak specification, only when $w = 2^\ell$ for some $\ell$, and in all such cases it is a permutation.  The choices 1, 2, and 4 for $w$ are not multiples of 8.  No multiple of 5 is a power of 2 and consequently $w$ is never a multiple of 5.


So my question is: is there a significant strength difference between the following?

From a theoretical perspective, yes.
Namely the first one requires us to assume that the SHA-256 compression function behaves like a dual-input PRF whereas the last two add the assumption of circular security on-top.
While assuming circular security is not entirely unheard of, it's one of those "non-standard" assumptions (PDF) - because you can't achieve it using only simple one-way functions - and should thus be avoided if it doesn't bring significant gains.

HMAC256(K,m) - Assuming that the SHA-256 compression function is a dual-input PRF (which is very reasonable as this even applies to the MD5 compression function), HMAC-SHA256 is a PRF and therefore when keyed with a uniformly random key any unique (per-key) message will output a value that is indistinguishable from a random string. Relevant papers are these three here.
HMAC256(K,m||K) - This likely has the same security properties as above but you'll also have to assume that HMAC offers circular security (which is not entirely unreasonable but gains you nothing over the first construction).
HMAC256(K,K) - This requires circular security again and because the message is not involved is more likely prone to repeat keys where repetition is unecessary thus potentially allowing easier higher-level attacks.


Existence of a map $\phi:\mathbb{Z}_{N^2}^* \mapsto \mathbb{F} $

So if you want a homomorphism from $\mathbb{Z}_{N^2}^*$ into the multiplicative group of a field, you have to adjust the number of elements in the field. With $p=2a+1$ and $q=2b+1$ (with $a,b$ prime), you have
$$|\mathbb{Z}_{N^2}^*| = 4pqab$$
The multiplicative subgroup of a field $F_{x^y}$ with prime $x$ and exponent $y$ has $x^y-1$ elements. At this point you could choose a specific $N$, that the according cardinalities match ($4abpq=x^y-1$), but if you have to apply this to arbitrary $N$, it won't work this way. Then all you can do is try to find $x^y$, s.t. $(x^y-1)$ is a factor of $4abpq$. If you use e.g. $\mathbb{F}_p^*$ or $\mathbb{F}_q^*$, this will work. But I can't think of any other fields which have this property from these given values.

As an example for an homomorphism you can use $f(x) = x^{pq(q-1)}$ to get a subgroup of order $p-1$, which you might be able to find an isomorphism into the multiplicative group of $\mathbb{F}_p$.

However, a bijective function (isomorphism) is quite unlikely to exist.


This is outside the goal of tweakable block ciphers.  For a counterexample, the following is an example of a secure (if inefficient) tweakable block cipher in the paper introducing tweakable block ciphers as Theorem 1 (p. 35): $$\widetilde E_K(T, M) = E_K(T \oplus E_K(M)),$$ where $E_K(M)$ is a block cipher.  If you know $K$, $M$, and $C = \widetilde E_K(T, M)$, then it is trivial to compute $$T = E_K(M) \oplus {E_K}^{-1}(C).$$

The intentional nonsecrecy of the tweak is made clear in the introduction to the paper: all the uncertainty from the attacker's perspective is contained in the key; the tweak is just an index into a family of independent secret permutations.

It's unlikely that any tweakable block cipher is designed to keep the tweak secret.  You may as well just use a longer key if you're going to choose it unpredictably.  But maybe if you gave more details about your intended application, it might become clearer what you need?


What does "message schedule" mean in SHA-256?

What this does is expand the 16-word (512-bit) input message block (to the compression function, i.e. one "chunk" of the complete message) into an 64-word array W[t]. The definition of this array is recursive. What it tells you is that the first 16 words of this 64-word array are just the words of the input chunk:

W[t] = M[t]   for 0 <= t <= 15

In other words, for t between 0 and 15, W[t] is equal to M[t].

Then, for 16 <= t <= 63 (the remaining 48 words) the following recurrence is used:

W[t] = MIX(W[t - 2], W[t - 7], W[t - 15],  W[t - 16])   for 16 <= t <= 63

Such that W[t] depends on W[t - 2], W[t - 7], W[t - 15] and W[t - 16] and MIX is the message schedule function (composed of exclusive-or and bit shifts/rotations). Note that words are guaranteed to have been defined previously as the first 16 words have already been initialized, and the remaining values are then successively calculated.

Here W[t] is just a temporary variable just like any other and is used to improve the compression function's quality, and is called the "message schedule" since it preprocesses the message block.

EDIT: I changed the description to SHA256 as @Henno noted you were actually describing SHA1 (though as he correctly observes, the overall structure remains the same for the two hash functions)


Question on the Quadratic Residuosity Assumption

I would put it as "it is conjectured" rather than "it is assumed", but otherwise, yeah...


Running Crypto on hardware -- e.g., AES in hardware

The difference between "software-based" and "hardware-based" lies in economics.

From a formal, mathematical point of view, there is no qualitative difference: the algorithm takes some inputs (including a source of random bits, for randomized algorithms), and produces some output which is fully determined from the inputs. How exactly the output is produced from the input has no consequence at that level.

In practical terms, though, a new factor must be introduced, and it is of paramount importance: money. Whenever some application (here I am talking generically, not only of cryptography) is to be incarnated as a tangible system, this is done at some cost, both in building (chips, wiring, casing...) and in operating (power consumption, weight, size...). The builder will try to minimize the costs for a given performance target. Among the structural choices that can be made, a very fundamental one is to go either "software" or "hardware":

The software path is about using some general purpose chips, usually known as "CPU", that can implement a variety of behaviours through programmability: the CPU is a fixed circuit, but it can interpret instructions obtained from some memory storage. The CPU includes circuitry to perform a number of elementary, general purpose operations such as "adding two 32-bit integers".
The hardware path means building dedicated circuits for the task at hand, directly from transistors or elementary logical gates. The dedicated circuit will become an ASIC or an FPGA (the FPGA is like an ASIC that can be wiped and drawn again, which is nifty but increases power consumption and chip cost, while lowering the maximum operating frequency).

What is good in the software path is that general purpose CPU are a commodity produced in huge series, which makes individual prices quite low; making millions of the CPU also justifies, economically speaking, the use of finer engraving technologies, which again promote performance (higher operating frequency, lower power consumption). Moreover, the inherent versatility of a CPU allows reduction of the number of hardware pieces needed in a system, since a single CPU can perform a high number of functions.

What is bad in software is that the CPU is basically an interpreter for the operations to perform, and that is expensive. Compared to an equivalent circuit, for the same algorithm to implement, a CPU will mobilize orders of magnitude more transistors and/or clock cycles. Using a dedicated circuit may save a lot in that respect, or allow a substantial performance boost, or both, but at the cost of a much lowered versatility. Dedicated hardware also forfeits the economical benefits of huge production series; FPGA try to regain some of these benefits, but lose a bit on performance compared to ASIC.

So, for any given application, whether software or hardware is to be used depends on what the system is supposed to do. Normally, CPU are cheaper, except for very specialized applications where versatility is not really needed, and raw performance must be achieved (e.g. detectors in high-energy particle accelerators, that must process gigazillions of data each second; bitcoin miners, that need to compute SHA-256 all day long, and only SHA-256; pacemakers, that must reliably regulate the heart beat of a patient with as small energy consumption as possible).

This is the landscape. What does it mean for cryptographic algorithms? Cryptographers, when they design algorithms, do so generically, that is, without a specific application in mind. Well, really, they do have applications in mind, but they try to make their algorithms good for many applications. They recognize that the computing industry at large operates over the two main models, so they try to define algorithms that will be "performant" (fast, light, economical...) in either or both.

For a software-based algorithm, this means using the operations that are natively offered by CPU. An example of a software-based algorithm is the hash function SHA-256, which uses a lot of 32-bit integer additions.

An hardware-based algorithm will rather concentrate on operations that yield better dedicated circuits. The new SHA-3 function (aka "Keccak") is of that kind: it is built around bitwise logical combinations. For a CPU, a 32-bit ADD and a 32-bit XOR have the same cost: both are elementary operations that will be executed in the same time, with the same CPU resources. But when you go hardware, the two operations are quite different: the ADD requires many more transistors (because of the carry propagation) with a deeper circuit (again because of the carry propagation), so the XOR is cheaper (less transistors, so less silicon area), lighter in energy consumption, and faster (because of the shallower circuit). The consequence is that Keccak tends to be a hog in software but a screamer in hardware.

Of course, the full situation is complicated. There are many types of CPU, some of them (the GPU) being optimized for tasks that general-purpose CPU are traditionally bad at (in particular heavy parallelism). Some modern CPU now include circuits dedicated to some specific cryptographic algorithms (e.g. for AES encryption). Also, FPGA have some, let's say, inclinations toward CPU, in that they are reprogrammable, and some include CPU-like features (RAM blocks, or even embedded DSP/microcontrollers). This blurs the limits.

In fact, the notion of an algorithm being "for software" or "for hardware" must be understood as a broad design categorisation that describes more the initial intent of the cryptographer who produced the algorithm, than a cleanly defined, mathematical property. There are extreme cases, e.g. the former AES candidate RC6, which is purely software (it uses an integer multiplication, a very expensive operation in hardware, that just happens to be part of the panoply of most CPU because it is a very useful operation in many cases), and the old GSM phone encryption algorithm A5/1, which is extraordinarily efficient in hardware (can be done in less than 500 gates) and remarkably slow and cumbersome in software.

Most modern cryptographic designs try to be versatile, and while they are usually meant to be more software-friendly or more hardware-friendly, it is considered a good thing if they do not yield abysmal performance in either case. This is one of the reasons, maybe perhaps the main one, that made Rijndael the winner of the AES competition: while not extraordinarily performant on, say, a big PC, it was still decent on all envisioned software platforms and in dedicated hardware; ultimately, this allowed the inclusion of such dedicated hardware in modern lines of CPU.

An exception is password hashing functions, that purposely aim at being most efficient on the defender's platform (supposed to be a general-purpose PC, i.e. the epitome of software), and as slow and expensive as possible on dedicated hardware. The recent Password Hashing Competition revealed a number of candidates that try to achieve this goal either with extensive usage of RAM (a traditionally sore point in FPGA), or with heavy usage of multiplication (as in Makwa).


How message digest hash is used in RSA digital certificate verification

Lets fix that description of the signature generation. Please read the PKCS#1 v2.2 specifications to get the full detail.

Canonical binary plaintext gets run through a hashing mechanism to make a message digest (IBM's terminology, there appear to be plenty of other terms for the hashed data).
Message digest is used as input for the configured padding mechanism.
Binary padded message digest is converted to a number.
Number is raised to the power of the private exponent modulo the modulus, either directly or using the Chinese Remainder Theorem.
The number is converted back to binary with the same byte size as the modulus, giving the signature.
Both the plaintext and generated signature are sent to recipient.

As you can see I had to rewrite most of it. The modular exponentiation is commonly seen as the "encryption with private key part", but that's a contradiction in itself; it is just a similar operation and PKCS#1 v2 goes out of the way to explain that. For more information, see my Q/A here.

  What I can't figure out is how this process is specifically applied in RSA verification of a digital certificate. I can't find the plaintext!

The certificate contains a to be signed (TBS) part. This can be found in the X.509v3 standard. This is the plaintext in above signature generation scheme:

The signatureValue field contains a digital signature computed upon
the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
tbsCertificate is used as the input to the signature function.  This
signature value is encoded as a BIT STRING and included in the
signature field.

  If it's generated at random for each request, then what's the point of having a digital signature from the assigning CA in the certificate? If it isn't, then where does whoever is verifying the certificate get the plaintext to compare the signature to? I don't see that it's part of the certificate.

It's just data, there are no pointers as in: here is the plaintext within the binary or textual description.

  So, first, do I understand the general signature verification process as it applies to digital certificate verification? And if I do, can someone solve the "mystery of the missing plaintext" for me?

Sure see above. But most of this is best found out by reading the standard documents. If you had done that then the mystery would not have existed.