Sites to find crypto intermediate values

Normally, test vectors, in particular test vectors for intermediate values, are to be found with whatever is the "official specification" for that algorithm. MARS has not been blessed with a standard (few algorithms are), so the "official specification" is what IBM distributes, in particular the MARS package (compressed archive).

This package contains the specification itself as a PDF file (in MARS/Algorithm/mars.pdf), sample implementations, and test vectors (in the MARS/Test_Values/ directory). In particular, have a look at the ecb_ivt.txt file, which contains some "intermediate values".

As a more generic rule, when faced with low-quality or inexistent test vectors ("low-quality" meaning, e.g., that there are some hexadecimal bytes but without clear endianness rules), the usual method is to find a "reference implementation" and sprinkle printf() statements throught its code, so as to get the intermediate values. I recommend using the Java code, which, in practice, will run you into much less trouble than any C code (that's the benefit of the strictness of the Java platform).

The NESSIE project was a big effort at analyzing many cryptographic algorithms, and it produced a large amount of test vectors for all those algorithms. This is a good source (but MARS was not submitted as "NESSIE candidate" so no luck there, in the case of MARS).

If all else fails, you can always send an email to the function author. Most function authors are researchers who will gladly help you out.

On the question of endianness, in particular in C, I strongly recommend against trying to play games with the memory representation, such as using a union between a sequence of bytes and an integer type. Such games limit portability and, more importantly, tend to break in awful ways in the presence of an optimizing compiler (because of strict type aliasing analysis). Instead, use generic encoding and decoding "functions", which you can later on optimize with inline functions and macros, and possibly inline assembly, if you detect a machine and compiler on which you know a smarter and cheaper implementation is possible. As an illustration, have a look at sphlib, which is a library implementing many hash functions in C and Java. In the C code, all the endianness "smartness" is concentrated in the sph_types.h file, which defines uniform names for the integer types and encoding/decoding functions (e.g. sph_dec32be() for 32-bit big-endian decoding).


Not as secure as a one time pad. A key concept with one time pads is that no part of them is ever reused. It is a common pitfall of people attempting to implement cryptography to assume that an obscure relationship is necessarily a secure one: it is not. You are create a chain of SHA hashes that can be observed, and potentially decoded.

Therefore what you have described is not an effective one time pad. The one time pad depends on the idea of a pre-compiled book of codes that have no relationship to one another, and that are used exactly once. If any sort of iteration is observed between the ciphertexts, this ruins the pad.

From the outside this seems like a hard code to cryptoanalyze, but I don't think it is massively difficult. Differences between your ciphertext will be analyzed, and when is found that you are not using a standard encryption scheme, the various pitfalls of self implemented crypto will be explored.

The security of your entire system can be no better than the original secret in that case, and the additional secrets generated from original secret actually worsen the security of the system, because they give some clue as to the original secret, however obscure that clue might be. To be as secure as a one time pide, the keys should bear absolutely no observable relationship to one another.

If I were to cryptoanalyze your system, I would first figure out the nature of the cipher text, and the nature of the keys. If I had access to a single key (say by brute forcing, or a flaw in the encryption) then I would be able to detect fairly quickly via automated methods that the key was a SHA hash.

At that point, I would try to guess the plaintext of the hash. If I had access to multiple keys I would notice that key size might correlate to message size in some way. From there it would be obvious that key was related to the message somehow. I will admit that brute forcing an entire message against a SHA hash is unreasonable, but all it takes is one leaked message to start pulling things apart.

If I ever decoded the plaintext from any one of the hashes it would be game over. System cracked. This was a quick analysis, others might be able to go deeper into the math side of this.


The usual meaning of "secure" for a MAC means that an attacker has no chance to forge a message not originally sent by the sender, without knowing the private key.

So, assume there is a message $ABCDE$ (where each letter corresponds to one $n$-bit block). This will be sent as $rABCDEt$. If an attacker captures this message, she can reorder the blocks to create a second message $rBDCEAt$, and if you look at your formula, the tag for $BDCEA$ is exactly the same as the one for $ABCDE$, thus this mangled message will still validate as authentic.

Thus, in the formal sense this proposed MAC scheme is not secure. Whether it is a problem in practice depends on what kind of data you are sending. If each block is a sub-message which makes sense of it own independent on the order of the blocks, then it might still be enough.

But as there are better MAC schemes which actually take the order of the blocks into account, use these instead.


What is the correct value for "certainty" in RSA key pair generation?

Certainty of $x$ bits means that the probability that something (in this case $p$ being prime) not being true is smaller than $2^{-x}$. This is the same probability as guessing a random $x$-bit value correctly on the first try, hence the name.

How to select $x$? We want the probability of $p$ (and $q$) not being prime to be small enough that a failure probability in this point is not larger than other ways the system could be broken - like guessing a symmetric key, factoring the modulus etc.

So here a correspondence table of symmetric and asymmetric key sizes should help. Pick the same prime certainty as you would pick an symmetric key size accompanying your public key usage.


Is it possible to make sense of an unknown language by means of cryptanalysis?

If you've got many examples of a language then you can probably perform frequency analysis to distinguish correct plaintext from invalid plaintext. This would make it easier to find out if you have successfully broken a cipher.

Understanding the language itself is of course off topic here - language studies / linguistics different from cryptanalysis. But if you have a newspaper then you can put it next to another newspaper with a language you know. You'd certainly find many articles that would have the same content, so you can use these newspapers as a Rosetta stone and "decipher" (most of) the language.

AFTER THE EDIT: Yes, you could certainly perform - for instance - frequency analysis to establish which language constructs are used often and where. This can help deciphering the language. But I presume that it will only result in statistical knowledge of the text.

Finding - for instance - the meaning of nouns will not be helped too much with this kind of analysis, you need to place the language structures in context for that.


What's the principle to design the functionality under UC framework?

What's the principle to design the functionality, if it aims to a new scene that Canetti hasn't treated? Are the ability to corrupt parties (by some unknown methods) required to be written into the functionality? What else (except the normal functions) should be written into it?

Basically, you can design the ideal functionality as you wish. The functionality does not consider corruption, because it is the ideal version. In order to make it more clear, you can consider the functionality as a trusted third party, which takes all the necessary input from all parties, computes the result and outputs it to those parties who should receive it.

  It is required that the simulator must successfully deal with any adversary. So how to 'predict' the behavior of adversaries if there are some abilities of adversaries which are not listed in the functionality?

UC is one of the strongest framework to proof security, because it does not give the adversary explicitly any power. In fact, in UC proofs the real world adversary is mostly just a dummy adversary, who just forwards any message it receives to the environment.

What happens is that you give the simulator some advantage (otherwise it would never work) e.g being able to choose the CRS, extract witnesses, etc.. And then you have to proof that the environment can't distinguish between real and ideal.

  What will happen if I write an only seem-to-be-right functionality?

Well, you prove that the protocol is a secure zealization of your functionality. If the functionality is "wrong" (not what you intended actually), then you have nothing.

  Why do real protocols mostly ignore the message type field (as new-session, test-password, ...) used in functionalities?

An example for that would be great, as it is not really clear what you mean. Sometimes, session IDs, etc. are omitted because they just blow up the length of the descriptions/proofs, making it unnecessary complex to follow.

  Does the environment gives some inputs to the simulator? Does the simulator need to simulate any non-corrupted parties? What information can be got by simulator?

Simulators replace corrupted parties. If the environment can give some input to a normal party and it is corrupted, the simulator has to do exactly the same in the ideal world. The difference is: In the ideal world, all parties and the simulator can only communicate with the functionality and the environment.

  In the real world, who controls the non-corrupted parties?

What does "control" mean? Parties are just independent Turing machines, which process some input and then have some output. Therefore, they don't have any input on their own, and they are activated by the environment, usually after the environment gave them some correct input.

  In the hybrid worlds, who controls the non-corrupted parties? Are they the worlds that exist both simulators and adversaries? Who else exists in those worlds?

Not really. A hybrid argument is, that you have some other functionality $F_{other}$, which is realized by $\Pi_{other}$ (in the UC framework). And then you actually use $\Pi_{other}$ in the real world, while using $F_{other}$ in the ideal world (both where they belong). Since they are already proven indistinguishable for the environment, you can use them for your own proof in their respective worlds. Basically, this is just the composability  of the UC framework.

For some further reading:
The UC approach: an application view


What are the "natural language input messages" that were used to derive Streebog's constants?

If you reverse the bytes, and you decode in cp1251, you get a series of Cyrillic names.

$C_1$: Гребнев
$C_2$: Сергей Владимирович
$C_3$: Дмух
$C_4$: Андрей Александрович
$C_5$: Дыгин
$C_6$: Денис Михайлович
$C_7$: Матюхин
$C_8$: Дмитрий Викторович
$C_9$: Рудской
$C_{10}$: Владимир Игоревич
$C_{11}$: Шишкин
$C_{12}$: Василий Алексеевич

I leave it as an exercise for the reader to find who all these people might be.  Hint: Рудской transliterates to Rudskoy.


I'm a little confused because I thought all 3 keys had to be independent for it to be backward-compatible with DES, unless by backward-compatible they were referring to something else?

No, all three keys have to be identical for the EDE (encrypt-decrypt-encrypt) scheme to be backwards compatible with DES. This is called single key triple DES.

What they may be referring to is the DES weak keys. There are keys $k_1$ and $k_2$ for DES where $E_{k_1}(E_{k_2}(X)) = X$. So if you'd use triple encryption $E_{k_1}(E_{k_2}(E_{k_1}(X)))$ then you would get $E_{k_1}(X)$ if you'd use weak keys.

Alternatively, they may just mean that you currently have to use triple-DES and that you achieve backwards compatibility in case $k_1 = k_2$.


Using HMAC is more principled and flexible here, because HMAC with a random secret key is a pseudorandom function, while sha256(secret + nonsecret) isn't.

In your case where the non-secret is a random value there might not be a security difference. But I mentioned also flexibility, because this sort of authentication scheme—when implemented with a proper pseudorandom function like HMAC—doesn't need a random value.  A counter or wall clock time will do.  In fact, if you've seen those two-factor authentication tokens or apps that display a six-digit code that changes every minute, those are based on the TOTP algorithm, which is basically hmac(secret, current_time / refresh_interval).


Is RSASSA-PKCS1-v1_5 a good signature scheme for new systems?

PSS is harder to implement because it uses randomness -- randomness is hard on many embedded systems like smart cards.

The most proclaimed advantage of PSS is that it has a "security proof" with, apparently, a rather tight reduction (see this page for some references). Security proofs are not an easy subject; the proof for OAEP (the encryption padding which is like the "sister protocol" to PSS) was found out to be wrong by Shoup and then repaired again by Fujisaki, Okamoto, Pointcheval and Stern, albeit with some casualties on the tightness front. I do not know how much all of this extends to PSS, but it shows that security proofs, however cool they may be, also need the "peer scrutiny" on which cryptographic security is traditionally built.

On the other hand, v1.5 signatures have been exposed "in the wild" for twice as long as PSS, and remain unbroken. In my opinion, this is very good and I quite trust that kind of security.

On a practical point of view, using a signature algorithm implies using a key storage device which knows that algorithm (smart card, HSM, software implementation...). The choice is not necessarily up to the application which requests the signature.


Is there a generic attack on encrypted CRC32 when used as a MAC?

Well, 32 bits is somewhat short, so one could just try ciphertexts.

However, there is a much better attack.

Choose M0 arbitrarily, let P be the CBC padding for Headers || CRC || M0,

and choose M1 so that CRC( M0 || P || M1 )  =  CRC(M0).

Submit M0 || P || M1 to be encrypted, truncate the ciphertext to the length of

encryptions of M0, and then output the result. $\:$ That will be a valid encryption of M0.

Even without chosen plaintext, one should be able to change the headers.

Let H be the headers and let CL be the first 16 bits of CRC and let  L be the (bit-)length of Data.

Choose 48 bits X which are not all zero so that the CRC of [X combined with L zero bits

however the protocol does that] ends with the same 16 bits as the CRC of 48+L zero bits.

Xor the IV with [X concatenated with [the xor of the first 16 bits of the two just-mentioned CRCs.

By the affineness of CRC, the result will be a valid ciphertext

with the same Data and header H xor X.


How to decide whether to use digital signature (RSA) or HMAC

HMAC (and any other MAC) are totally different from Digital Signatures (RSA, DSA, ECDSA, EdDSA).

MACs require a shared secret key that both the communicating parties have. The same secret is used to create the MAC as is used to verify it. Anyone with the shared secret key can create a MAC, and anyone with the shared secret key can verify a MAC.

Digital Signatures don't use a shared secret: Each entity has two keys, one public and one private. Only they can sign messages (only they have the private key) but anyone can verify those signatures. There's no need to exchange a shared secret.

MACs are generally much faster than Signatures.

That said, the fact that you are asking this question indicates that you have some fundamental learning to do before even starting to design an SSO mechanism. Have you considered using OAuth? There are many libraries for various languages that support it, it's secure, and it avoids many of the hidden pitfalls you won't have thought of.


Perfect Secrecy -> One Time Semantic Security -> Secure PRG

First, on the difference between perfect security and semantic security. Both definitions concern confidentiality, so let us first define what confidentiality means.

Note first that an adversary as some a priori knowledge of the message. We can capture that by e.g. having the adversary choose two messages and then flipping a fair coin to decide which one to encrypt.

Next, note that the adversary wants to learn something from the ciphertext, his a posteriori knowledge of the message. We capture that by having the adversary guess which message was encrypted.

If the adversary cannot guess correctly which message was encrypted with probability significantly different from $1/2$, then we have confidentiality.

That was the definition of confidentiality.

(More complex definitions are possible using a probability space and a function from the message space to 0 and 1, but we ignore that since it isn't important for the present discussion.)

Perfect security is about confidentiality against arbitrary adversaries. Now we can prove many theorems about perfect security, and one of them talks about the number of keys taking a given message to a given ciphertext (as you describe).

Semantic security is about confidentiality against computationally bounded adversaries. Unlike for perfect security, there aren't so many theorems we can prove about semantic security, which means that we know less about what is required to achieve semantic security.

So the difference between perfect and semantic security is just about which adversaries we consider, nothing else. The two notions are often presented in a superficially different way, however, making it look like they are different in other respects.

Regarding computationally bounded adversaries. The traditional approach (based on computational complexity theory) is to speak about families of cryptosystems with increasing key lengths, and let the adversary's effort be bounded by some polynomial in the key length. The concrete security approach says that we have a concrete cryptosystem with a fixed key length, and let the adversary's effort be bounded by a fixed number of computational steps (probably relative to some fixed universal Turing machine or something, there are some foundational problems here).

Second, on pseudo-random generators. A pseudo-random generator is a function that "expands" a short string into a long string. As above, we define first a security goal similar to confidentiality, and then we can consider different adversaries against that goal.

A short string is sampled and expanded into a long string. A second long string is sampled. The adversary gets either the first or the second long string, decided by a fair coin flip.

If the adversary cannot guess correctly which of the two strings he got with probability significantly different from $1/2$, then we have security.

(This is equivalent to Boneh's notion of indistinguishable probability distributions.)

Perfect security considers arbitrary adversaries. Using the arguments you outline in your question, it is fairly easy to show that perfect security for a pseudo-random generator is impossible.

Computational security considers computationally bounded adversaries. Obviously, here there's no proof of impossibility. Instead, we have good reason to believe that this is possible to achieve for useful values of "computationally bounded".

Since perfect security is impossible, there's no point in going on about "computational" all the time, so we usually ignore it and talk about "secure pseudo-random generators". Since pseudo-random generators are used in many fields of science, we often add "cryptographically" in front to say clearly that we are talking about cryptography here, and not (say) statistics.

A pseudo-random generator is a function $G$ from the set of short strings to the set of long strings. If you can invert the function (or find preimages if it is not injective), then the generator is obviously not secure, as you observe.

Third, on unpredictability. It is clear that if I sample a long string and show you a prefix, then you cannot say anything about the remainder of the string, specifically not about the next symbol.

Suppose that if you are given a prefix of a pseudo-random generator's output, you can predict the next symbol of the output. In the setting described above, where you either get the generator's output or a random string, you can recognize the output of the pseudo-random generator.

Here's how you recognize the output: You get a long string. Momentarily, you forget all but a prefix of the string and pretend that it is a prefix of something output by the generator (which it may be). Now you use your ability to predict the next symbol. Then you remember the entire long string, specifically the next symbol. If you predicted it correctly, then probably the long string was output by the generator. If your prediction was incorrect, then probably the long string was random.

Since you can recognize the generator's output, the generator is not secure. It follows that if you have a secure generator, it is unpredictable. Which is nice.

(The other direction is more complicated. Basically, the idea is that if given a prefix, you cannot say anything about what the next symbol will be, then you cannot distinguish the generator's output from the generator's output with the final symbol randomized. But you cannot distinguish the latter from the generator's output with the final two symbols randomized. Etc. Since indistinguishability is transitive, it follows that you cannot distinguish the generator's output from random strings.)


Convert m-Sequence into a de Bruijn Sequence

A de Bruijn Sequence, as defined in N.G. de Bruijn's A combinatorial problem, Proc. K. Ned. Akad. Wet., vol. 49, pp 758-764, 1946 (with attribution to Ir. K. Posthumus) is

  an ordered cycle of $2^n$ digits 0 or 1, such that the $2^n$ possible ordered sets of $n$ consecutive digits of that cycle are all different.

The example given for $n=3$ is the sequence 00010111, yielding sets 000, 001, 010, 101, 011, 111, 110, 100.

Given that, a de Bruijn Sequence of length $2^n$ is obtained from any m-sequence of length $2^n-1$ (that is, the cyclic output of a LFSR with a primitive polynomial of degree $n$ starting from a non-zero state) by inserting a single 0 in the single subsequence with $n-1$ consecutive 0.

Update per comment: We can implement a circuit that outputs a de Bruijn Sequence of length $2^n$ using $n$ D-type flip-flops connected as for a maximal-length Fibonnaci LFSR with $n$ stages, by adding an additional XOR term equal to the NOR of the outputs of the $n-1$ flip-flops on the feedback's side. In the following drawing (which outputs the example sequence above), the added gates are NOR1 and XOR2.

Note 0: When the number of stages $n$ gets large, the NOR gate with $n-1$ inputs gets annoying; one can trade this for a $\lceil\log_2(n)\rceil$-bit counter with reset, counting the number of consecutive zeroes in the output, giving a $1$ when reaching $n-1$ consecutive zeroes, and that output the additional XOR term.

Note 1: A de Bruijn generator is used in the paper only for the control generator of the ASG, deciding which of the other two are clocked. It would be questionable to also use a de Bruijn generator for any of the other two generators: notice that if the control generator has $c$ bits, a slave generator $x$ bits, and both are de Bruijn, the overall period of the slave's output is $2^{\max(c,x+1)}$, rather than $2^c\cdot(2^x-1)$ when the slave is a maximal-length LFSR.

Note 2: I do not see why the ASG's security would be weakened if the control generator was a maximal-length LFSR rather than a de Bruijn generator, with both slaves maximal-length LFSRs, provided $\gcd(2^{c-1}-1,2^x-1)$ is small [as well as $\gcd(2^x-1,2^y-1)$], where $c$ (resp. $x$, $y$) are the number of bits of the control generator (resp. the slave generator clocked when the control generator outputs $0$, the other slave generator). The original paper hints at another paper (submitted to IEEE Transactions on Information Theory, but I could not locate it) covering the case of maximal-length LFSR as control generator. It also seems to be the case in this article on the ASG, and some of its references.

Late addition: This is also easy in software. Assume $x^\mathtt n+x^\mathtt k+1$ is a primitive trinomial over $GF(2)$ (suitable constants $\mathtt n$ and $\mathtt k$ can be obtained from Jörg Arndt's Complete list of primitive trinomials over GF(2) up to degree 400). If x is an unsigned integer variable at least $\mathtt n$ bits wide, then the C expression
x = ((((x>>k)^x)&1)<<(n-1))|(x>>1);
readily implements a LFSR with period $2^\mathtt n-1$ (when starting from any positive x less than $2^\mathtt n$). We can change this to
x = ((((x>>k)^x^!(x>>1))&1)<<(n-1))|(x>>1);
which implements a NLFSR with period $2^\mathtt n$ (when starting from any non-negative x less than $2^\mathtt n$).


Tree hash and multithreading for parallelism

On multi-threading: Read the code.  As Paulo writes, that's up to the implementation.  Read the source code of your library and see for yourself what it is doing; it shouldn't be too hard to figure it out.


Usually what you call "information theoretic hardness" is denoted as statistical indistinguishability. And it is pretty much black and white only: Two distributions are distinguishable or not.

When you ask "how much harder", you already drift into the area of computational indistinguishability. There are plenty of ressources for that keyword, including most books about introduction into cryptography.

So the actual answer to your question would be "If the distribution of p is distinguishable (which is the case for any $p\neq1/2$), and the distribution of the PRNG is distinguishable, then your construction is distinguishable (from a truly random distribution)"


Plain text of data, including server's public key

Yes, and many other public information, including something identifying the holder of the public key (perhaps in the Common Name field).

  Signature of hashed version of plain text

Yes, except that the correct semantic is: Signature of the plain text. Building and verifying the signature includes hashing plain text.

  What encoding scheme is this?

See RFC 7468 section 5 and what it references, including RFC 1421 section 4.3.2.4 for the translation of binary to text (which in a nutshell is per Base64).

  Does this offer extra layer of security?

From a cryptographic standpoint, no. That's merely a binary-to-text encoding, see this for rationale.

  Shouldn't the main ideas (point 1 and 2) be secure enough?

Yes, they are.

  Is there a way I can break this blob down to visually show that data part and the signature part?

When there's any non-confidential piece of standard text-encoded stuff to decode, it can be thrown at the marvelous https://lapo.it/asn1js/ (with or without the delimiters) and the results are usually pretty good. When in doubt about the confidentiality, use a local copy in an isolated VM.


First of all, if you want to seriously learn cryptography, then do not use any online encryption sites. It seems most if not all are created by enthusiasts that just learned crypto and then wanted to do something interesting with it. Unfortunately that simply means that they are just propagating their very limited and often incorrect understanding of (block) ciphers and cryptography in general. Even if one of the sites was created by a good cryptographer, you would not be able to distinguish it from the rest.

One of the first things to learn before starting to learn cryptography is how - and when - to perform encoding / decoding. Basically there are two forms of encoding that convert byte- and character strings:

character encoding where a character is encoded to binary. Examples are ASCII, UTF-8 and UTF-16(BE/LE).
(binary) encoding where a octet string / byte array is encoded to a string consisting of characters. Examples are hexadecimals, base64, base64url.

For instance, ar635N/LqmY= is a base 64 string which encodes 8 bytes or 64 bits. Those bytes may not themselves represent a string, and assuming that they consist of 8 UTF-16 characters is obviously incorrect, if just because 8 UTF-16 characters take 8 * 16 = 128 bits at a minimum, not 64 bits.

The site you pointed to doesn't decode the base64, it just tries to character-encode the string to binary. For base 64 you could use e.g. this site (random one without ads). Note that humans are bad at reading bytes if they do not represent text, and ciphertext consists of pseudo-random bytes. So the site will return another encoding as well: hexadecimals. From hexadecimals it is easierto see any structure in the returned bytes.

To be able to take a "encryption" site seriously, the site should:

explicitly define which cipher is used (for DES, does it accept 3DES as well?)
show the key sizes that you can use
allow the key to be entered as hexadecimals
if it allows a password (a password is not a key), specify which Password Based Key Derivation Function is used (examples: bcrypt, scrypt, PBKDF2, Argon2)
allow you to input a given IV (and possibly create and display a random IV as an option)
specify the mode of operation that is used for the block cipher
specify the padding mode that is used for the mode of operation (if any)
indicate which configuration options are used (such as the hash of the digital signature, or the length of an authentication tag) instead of relying on unspecified defaults
specify the character encoding of the plaintext message (assuming the message is text instead of hex or base64)
specify the encoding of the ciphertext (directly displaying the random bytes doesn't make sense, some bytes do not translate directly into printable characters)

If any of these are not given it will leave you guessing on what is happening.

Furthermore, the site should:

indicate that the site is for testing only, actual plaintext or keys should not be entered
not make any simple crypto errors such as failing to distinguish between AES and Rijndael or reuse the key to generate an IV (the list is endless)
hopefully indicate that encryption using e.g. CBC is not secure for transport protocols
and finally, return correct results

These two lists will unfortunately rule out 99% if not all of the sites.

You're better off picking up the best crypto API for your favorite language / runtime and use that to explore.

As for your specific key issue: the site will probably add 00 valued bytes up to the key size. Or it could use spaces. Or it could use a cryptographic hash (and take the wrong, rightmost bytes if you're unlucky). All of which are insecure and show exactly how you should not use a block cipher.


Why GCM operation mode with AES-128 is recomended and can we use AES-192 and AES-256 with GCM?

AES can be used with 128,192, and 256-bit key sizes and always with 128-bit block size †.

In NIST 800-38d, GCM is defined for 128-bit block size, since it is operating on block size and doesn't mandate about the key size.

  This Recommendation specifies an algorithm called Galois/Counter Mode (GCM) for
  authenticated encryption with associated data. GCM is constructed from an approved symmetric key block cipher with a block size of 128 bits, such as the Advanced Encryption Standard (AES) algorithm that is specified in Federal Information Processing Standard (FIPS) Pub. 197

In rfc5288 these modes are defined for TLS 1.2

  The following cipher suites use the new authenticated encryption
     modes defined in TLS 1.2 with AES in Galois Counter Mode (GCM)

CipherSuite TLS_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0x9C}
CipherSuite TLS_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0x9D}
CipherSuite TLS_DHE_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0x9E}
CipherSuite TLS_DHE_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0x9F}
CipherSuite TLS_DH_RSA_WITH_AES_128_GCM_SHA256 = {0x00,0xA0}
CipherSuite TLS_DH_RSA_WITH_AES_256_GCM_SHA384 = {0x00,0xA1}
CipherSuite TLS_DHE_DSS_WITH_AES_128_GCM_SHA256 = {0x00,0xA2}
CipherSuite TLS_DHE_DSS_WITH_AES_256_GCM_SHA384 = {0x00,0xA3}
CipherSuite TLS_DH_DSS_WITH_AES_128_GCM_SHA256 = {0x00,0xA4}
CipherSuite TLS_DH_DSS_WITH_AES_256_GCM_SHA384 = {0x00,0xA5}
CipherSuite TLS_DH_anon_WITH_AES_128_GCM_SHA256 = {0x00,0xA6}
CipherSuite TLS_DH_anon_WITH_AES_256_GCM_SHA384 = {0x00,0xA7}

and for TLS 1.3

TLS_AES_256_GCM_SHA384
TLS_CHACHA20_POLY1305_SHA256
TLS_AES_128_GCM_SHA256
TLS_AES_128_CCM_8_SHA256
TLS_AES_128_CCM_SHA256

  Can it be?

Yes, see above.

  although AES-256-GCM is available, it is costly from the computational point of view at this time and should be used with other practices and methods to ensure greater security and privacy.

AES-256 is only 40% slower compared to AES-128. New CPU's from INTEL also includes instructions for GCM mode. If you are targetting post-quantum cryptography or fear of multi-target attacks on any 128-bit key sized block cipher you should use 256 bit key. Otherwise, 128 bit is fine [1],[2].

  Why is this recommendation made?

Anybody can make recommendations. It is up to you to listen to them. Some already migrated to 256.

As commented by Swashbuckler, Department of Homeland Security, in section 5.1 of DHS Sensitive Systems Policy Directive 4300A Version 13.1
July 27, 2017 mandates 256-bit key size for block ciphers.

  Systems requiring encryption comply with the following methods:

  Products using FIPS 197 Advanced Encryption Standard (AES)
  algorithms with at least 256 bit encryption that has been validated
  under FIPS 140-2
  National Security Agency (NSA) Type 2 or Type 1 encryption

If you want to sell a product that contains AES to them you need to use 256-bit.

† Don't confuse AES with the Rijndael. From Wikipedia's footnotes;

Key sizes of 128, 160, 192, 224, and 256 bits are supported by the Rijndael algorithm, but only the 128, 192, and 256-bit key sizes are specified in the AES standard.
Block sizes of 128, 160, 192, 224, and 256 bits are supported by the Rijndael algorithm for each key size, but only the 128-bit block size is specified in the AES standard.


Constructing a mac scheme secure to regular definition but insecure to special case

Using your terminology, if a scheme is secure in the mac-forge game then it is also secure in the mac-forge* game. The formal proof is a bit fussy I can sketch the main idea.
First, without loss of generality, assume that in the mac-forge* game the adversary never queries the verification oracle on $(m,t)$ that was a result of a prior MAC query. This is without loss of generality because we already know what the verification oracle will answer (true) on such an input, so there is no need to query.

Claim: If the MAC scheme is secure in mac-forge then in the mac-forge* game the verification oracle will answer false to all queries.

The proof idea is as follows: Suppose we have an adversary $A$ who breaks security of the mac-forge* game. We will use it to construct a new adversary that breaks the security of the mac-forge game. Suppose $A$'s $i$th query to the verification oracle is the first one that returns true. Construct a new adversary $A^*_i$ which does the following in the mac-forge game:

run $A$
whenever $A$ makes a MAC query, make the same MAC query in the mac-forge game and relay the result back to $A$
when $A$ makes verification queries 1 through $i-1$, give the answer false  to $A$
when $A$ makes the the $i$th verification query $(m,t)$, halt with output $(m,t)$.

So $A^*_i$ plays in the mac-forge game (it never makes verification oracle queries). If $A$'s $i$th verification query really was the first one that returns true, then:

$A^*_i$ provides a view for $A$ that is identical to when $A$ plays the mac-forge* game (identical until we terminate $A$ early)
$A^*_i$ halts with a valid forgery.

So $A^*_i$ breaks the mac-forge security of the scheme.
This is just a sketch, and it somewhat assumes that it is always the $i$th verification query that works. In the real proof, you would choose $i$ uniformly at random and incur a loss in concrete security.


What does CA certs contains? public key of site or CA?

As per definition, digital certificate is a security document that binds public key to some entity. That is, any X.509 certificate at least contains certificate owner's public key and information about the cert owner.

In the case of web site SSL certificate, digital certificate contains web site's public key and information about the site.

For CA certificates, they contain CA's public key and information about that particular CA.

Digital certificate contains other information as well, like information about issuer, validity, key usages and information that could be used to validate each certificate (e.g. build certification path, perform revocation checking, etc.)

For your question: CA certificate contains its own public key. When bank web site's certificate is validated, a certification path is constructed by using issuer information. Then issuer's public key is used to validate web site certificate's signature. That is, when you validate any particular certificate, public key for signature validation is taken from other source (except self-signed certificates, where public key in the cert is used to validate its own signature).

For more details I would recommend to read RFC5280.


A boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ has correlation immunity $k$ if its walsh-hadamard transform coefficients
$$F(a)=\sum_{ x \in \{0,1\}^n} (-1)^{f(x)+a\cdot x}$$
are zero whenever $1\leq w(a)\leq k,$ where $w(a)$ is the hamming weight of $a$.

An sbox  $S:\{0,1\}^n\rightarrow \{0,1\}^n$ has correlation immunity $k$ if the functions $b \cdot S(x)$ all have correlation immunity $k$ whenever $b$ is not the all zero vector.

Operationally this means that all nontrivial output linear combinations of the sbox are uncorrelated with all linear combinations of $\leq k$ of the input bits, raising the complexity of divide and conquer attacks in stream ciphers.

In block ciphers this means that any useful linear characteristic must have output weight at least $k+1$ provided we also require that the walsh-hadamard coefficients are zero when $a$ is zero, i.e., the relevant functions are $k-$resilient.

For you $n=4.$


That's a well-known disadvantage of using OTP. Like in the ancient times, you could e.g. employ a trusted courier for that transfer.


NIST LWC finalists (AEAD) vs ChaCha20-Poly1305

As for every benchmark, it all depends on the computing platform.
As mentionned in comment, you will find benchmarks at bench.cr.yp.to that include NIST LWC finalists and ChaCha-20. However, most of the architectures considered for those benchmarks are rather high-end computing platforms, and they do not necessarily reflect the landscape of constrained devices where lightweight cryptography takes all its sense.
If you are mostly interested in how the NIST LWC finalists compare with ChaCha20-Poly1305, you should take a look at the benchmark by Rhys Weatherley which focuses on embedded devices (8-bit AVR, ARM Cortex-M3 and ESP32 Arduino). As stated on the performance on 32-bit platforms webpage, all the benchmarking results are reported in comparison to ChaCha20-Poly1305:

The approach I take here is "ChaChaPoly Units". The library contains a
reasonably efficient 32-bit non-vectorized implementation of the
ChaChaPoly AEAD scheme from my Arduino cryptography library. This
makes it a known quanitity to compare with other algorithms side by
side.
If an algorithm is measured at 0.8 ChaChaPoly Units on a
specific embedded microprocessor at a specific clock speed, then that
means that it is slower than ChaChaPoly by a factor of 0.8 on that
microprocessor. If the algorithm is instead measured at 2 ChaChaPoly
Units, then it is twice as fast as ChaChaPoly on the same
microprocessor. The higher the number of units, the better the
algorithm.

As you can see, many of the NIST LWC finalists show better performance than ChaCha20-Poly on such platforms. Note that all implementations considered are running in constant-time to ensure a fair comparison.
Another point that matters for the NIST LWC final round is resistance against side-channel attacks. Because ChaCha20 is an ARX-based design, it is does not facilitate the integration of countermeasures against power side-channel attacks such as masking, as highlighted in previous works (e.g. in [1] and [2]). The benefits provided by the NIST LWC finalists over ChaCha20-Poly1305 will likely be of greater interest when considering power side-channels.


ElGamal encryption and signature using same keys

Is there a possibility to obtain private key $x$?

No; here's the proof.

Suppose we had a black box that, given $c = g^k, d = M \cdot y^k, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (and we'll throw in $M$, and $z : y = g^z$), is able to give us $x$.

Then, here's how we can find the private key given an ElGamal signature.

We have $M, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (as that's the ElGamal signature and message being signed).

That also gives us $c$.  To get $d$, we select a random $z$ and compute $d = M \cdot c^z = M \cdot y^k$.

We now have everything the Oracle expects; we pass in everything, and we recover $x$.

As we believe that deriving the ElGamal private key from a signature is infeasible, we believe there cannot be such a black box.


If the original message length $N$ is $2^{64}$ bits or longer, you encode the value $N \bmod 2^{64}$ in the final padding block, rather than just $N$.  Alternatively, you can just always encode $N \bmod 2^{64}$; if $N < 2^{64}$, then they're the same value.

Now, this distinction between $N$ and $N \bmod 2^{64}$ doesn't happen at 64 bits, it's at $2^{64}= 18,446,744,073,709,551,626$ bits, or about 2000000 Terabytes.  No one has ever hashed a message that long with MD5; even if we assume an MD5 compression function can be computed in 1nsec (massively overoptimistic), it'd take over a year to hash a message that large (and parallelism doesn't help).


As fgrieu notes in the comments, the protocol might not even work reliably in the absence of adversaries: if the tag fails to receive the reader's reply of "True", the keys will get out of sync.  (If that happens, the tag will just retry the next exchange with the old key, so this could be fixed by having the reader remember one more "subkey".  But the current protocol, as described, does not have this feature.  Also, note that this would have its own security implications, which would need to be analyzed.)

This protocol also has the inconvenient feature that each tag can only work for one reader, at least unless the readers communicate with each other to synchronize their state, or unless the tag actually holds multiple keysets, and uses some kind of a handshake with the reader to decide which key to send.  (Again, neither of these features are part of the protocol as decribed, and so their security implications cannot be analyzed reliably.)

The fact that the protocol requires the tag to generate random numbers also worries me a bit.  I'm not really familiar with the state of the art in RFID, but generally, securely generating unpredictable random numbers is not a trivial task.  The protocol appears to be designed for tags that have very minimal computing capabilities, so I wouldn't fell comfortable automatically assuming that such a tag has a cryptographically secure RNG.

Also, obviously, 4-bit keys are trivially vulnerable to brute force attacks, but that's easy enough to fix.  In the rest of this answer, I'll assume that the actual key length is at least 128 bits or so.

Even if all the issues mentioned above are addressed, though, the protocol as described has (at least) two obvious and serious security flaws:

An eavesdropper can impersonate the tag after observing four consecutive successful authentications.  The random numbers generated by the tag are transmitted in the clear, and the keys depend only on the last four random numbers, so knowledge of those four numbers automatically lets an attacker compute the key.

When using the key thus obtained, a clever attacker could also perform four consecutive authentications, and recycle the random numbers so that the reader ends up in the same state it was in before.  That way, the holder of the valid tag need not notice anything unusual, as their tag will still be in perfect sync with the reader.

(In fact, since the XORed key is also sent in plain, it's enough to observe the latest transaction and the fourth one before it.  This is not enough to fully determine the state of the tag, but it does suffice for one fake authentication.)
The attacker doesn't even need to get near the reader to carry out this attacks, since it's trivial to impersonate the reader.  The fake reader can just reply "true" to anything the tag sends it.  This allows a number of attacks:

An attacker can impersonate the reader, and (possibly after some delay) relay the tag's key and random number to the real reader.  This will allow the attacker to authenticate as if they had the tag, and any logs will show the tag being used normally.
Alternatively, an attacker with a fake reader can query the tag four times, replaying "true" every time, and thus steal the full state of the tag.  At that point, the real tag will no longer work (until and unless the attacker deliberately sends the same sequence of four random numbers to the real reader to re-sync its state), but the attacker can now authenticate with the reader as many times as they like.

There are ways to address all of these issues, but honestly, by the time you've fixed them all, the result will no longer bear more than a passing resemblance to your original protocol.  So, no, this is not a secure authentication protocol.


"Homomorphic" one way function for public/private key pairs

Sure.  Let (Gen,Sign,Ver) be any signature scheme, and let h be any pseudorandom generator from {0,1}k to {0,1}k+L.  (Since h is a pseudorandom generator, h is one-way.)

Gen' takes k+L random bits as input and outputs [those bits as the private key] and

[the public key resulting from running Gen on the last L of those bits] as the public key.

Sign' outputs the result of running Sign on [the message and

[the private key resulting from running Gen on the last L bits of the (k+L)-bit private key]].

(Gen',Sign',Ver) is a signature scheme such that "we can efficiently calculate

the public key associated with $h(s_k)$" without even needing $s_k$'s public key.

That makes me think you're actually after something stronger.


Difference between "one-way function" and "cryptographic hash function"

It's all a matter of definitions.

Typically, a "cryptographic hash function" $H$ has three properties:

Preimage resistance: Given $H(x)$, it's hard to find $x$
Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

These aren't definitions that are set in stone. This sort of broad definition is not really very nuanced, but it is indeed a common one. Usually, it's not necessary to be any more specific than this.

For a less restricted definition, you might say a hash function $H$ only has two properties:

  a.  Easy to compute: Given $x$, it is easy to compute $H(x)$
  b.  Compresses: $H : \{0,1\}^{*} \to \{0,1\}^n$ (i.e., it maps any bit-length string to a fixed bit-length)

And then from there you can become more nuanced. Now you can say a "one-way" hash function is a hash function (using the less restricted definition) that possesses properties 1 and 2; that is, it is an easy-to-compute compression function that possesses preimage resistance and second-preimage resistance. In other words, the function can only be computed "one way".

Using this sort of definition is sometimes convenient for a detailed study of hash functions. You can also have collision-resistant hash functions, which possess property 3.

In fact, property 3 implies property 2 implies property 1. (In other words, there is a hierarchy of security properties, each one implying the one above it.) So a hash function that is collision-resistant is also second-preimage resistant and preimage resistant. Note that it does not go the other way: MD5 is an example of a hash function that is preimage resistant (very much so) but is very broken when it comes to collision resistance.

Ultimately, it just depends on whose definition you are using. In this case, I'm essentially summarizing the definitions given in the Handbook of Applied Cryptography.


What is the fuss about 'dot blockchain' and music metadata?

Publicity man creates his own fuss.

  claims that this is an answer to the metadata woes of the music/recorded media industry.

There are no such woes. Sure there is piracy but that's not because songs can't be identified using a centralized interface (they can, and more efficiently than watermarking).

  I don't see how it can possibly prevent rewriting the file.

It's a watermarking scheme. You can't just get rid of these watermarks by converting to PCM and re-encoding because the watermark is present in the audio data itself. Consider, for example, shifting the center point (DC offset) of the PCM samples slightly - to either "up" or "down" states each lasting a few tenths of seconds, and using this to embed a repeating 128-bit identifier. No quality loss because DC offset is practically ignored by the end output analog playback system and you only shift it slowly.

Then consider fancier tricks like partially undoing the DC shift by selectively amplifying some of the lobes on the other half of the sample space and you get something that requires very advanced processing to remove without introducing artifacts.

The even meaner thing to do if you run an online store is to embed different identifiers for each user when they download the song ... then when some of these downloaded songs, each unique, appears on a file sharing site you can do "traitor tracing" and send in the FBI.

In terms of the other stuff they talk about, enforcing the rights, well, that's just not doable with today's tech because it will come out in analog at some level. Even assuming a secure encrypted link between a computing device and a set of speakers, at the most basic level you can just capture the analog voltage going to voice coil and process that somehow back into an audio file to drop DRM restrictions.

Note however that a good watermarking scheme will survive a few iterations of this. Applying DRM restrictions automatically based on watermarking sort of works in theory but requires a doomsday trusted computing scenario where users have absolutely no ability to run arbitrary programs on their computing devices (i.e., programs that don't necessarily obey DRM restrictions).

Watermarking is quite an old technology. It appears what they consider to be the main benefit of putting the metadata on the public blockchain is that it cannot be revoked (as in, the publisher who applied the watermark going out of business and lookups to their website/API failing to provide data for audio files). This is a mildly interesting idea for Indie media, etc, but of course big media does not assume they are going to go out of business any time soon so there is no impact on their business model from this technology.


Which Fully Homomorphic Encryption schemes are fastest?

Encryption and decryption are usually the least problematic operations, in terms of performance, in FHE schemes.

The main software library I know for FHE is HElib, which is regularly maintained and been around for a while now.
There are several different papers about various benchmarks of HElib.
The most recent one I could find was HEtest: A Homomorphic Encryption Testing Framework. In Section 6.7 you find their encryption and decryption benchmarks. They state 33 ms for encryption and up to 5 seconds for decryption.

Very recently, there appeared a new library $\Lambda \circ \lambda$ (code can be found here).
In Section E.2.2 they provide some performance results for a Somewhat Homomorphic Encryption (SHE) scheme, which allow you to evaluate circuits of a fixed depth.
If I read the table (Figure 10) correct, then their encryption needs around 371 ms and their decryption 2.3 ms.


The reason to use a large private key (or rather, not to attempt to use a small private exponent) are given in 5. The reasons to use a large public key are in 1, and have nothing to do with exponent size (private or public). There is no known reason to use a larger public exponent than suggested in 2, and that's uncommon.

In RSA:

One should use a large enough size $n$ for the public modulus $N$; that's important because anything that factors $N$ will break the RSA instance using that $N$, and the resistance of $N$ to factorization tends to grow with $n$ (for constant number of factors of size proportional to $n$). The bit size $n$ of $N$, with $2^{n-1}\le N<2^n$, is known as the key size, public key size, or public modulus size. Official security recommendations start at $n=2048$.
The public exponent $e$ can be fixed to $e=2^{16}+1$, which is most common, compatible, and unobjectionable; or $e=3$ which gives a significantly faster public-key operation (see cautionary note). In modern practice, $e$ is typically a small odd prime fixed and chosen before $N$ and its factors. In any case, $e$ must be odd and at least $3$.
The factors of $N$ must be large distinct primes, and not one more than an integer sharing a prime factor with $e$. They must be randomly and secretly generated and combined into their product $N$. Standard practice is to select two primes $p$ and $q$ as about uniformly random primes in range $[2^{(n-1)/2},2^{n/2}]$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$, simplifying to $p\bmod e\ne1$ and $q\bmod e\ne1$ when $e$ is prime; then compute $N=p\,q$.
A private exponent $d$ is most commonly secretly computed from $e$ and factors of $N$. The smallest working positive $d$ is $d=e^{-1}\bmod\lambda(N)$ with $\lambda(N)=\operatorname{LCM}(p-1,q-1)$ when $N=p\,q$. It is also common to use $d=e^{-1}\bmod\varphi(N)$ with $\varphi(N)=(p-1)(q-1)$.
No attempt should be made to significantly shorten $d$ ("small decryption key") by choosing $e$ or the factors $p$ and $q$ of $N$ for that purpose; that's not possible anyway when following advice in 2 and 3 above. It is known that $d$ shorter than $0.292\,n$ is unsafe; see Dan Boneh and Glenn Durfee, Cryptanalysis of RSA with Private Key $d$ Less than $N^{0.292}$, in proceedings of Eurocrypt 1999. It is unclear what a safe minimum would be; and better speedup is achieved by a common implementation of the private-key function uisng the Chinese Remainder Theorem.
The textbook public-key function $x\to x^e\bmod N$ should be used for encryption, and/or the textbook private-key function $x\to x^d\bmod N$ used for signature generation, only when $x$ is

essentially random in some large interval (with bit size of its width close to $n$) and not under the control of an adversary; for example, $x$ can safely be a random bitstring of $n-1$ bits, converted to integer from binary, encrypted as $y=x^e\bmod N$, decrypted as $x=y^d\bmod N$, and then considered a shared secret, used in part as an encryption key for a message encrypted using symmetric cryptography;
or produced by some appropriate padding technique adapted to the usage (encryption or signature); a recommendable encryption padding is RSA-OAEP; a recommendable signature padding is RSASSA-PSS.

Care should be taken that implementations using a private key (decryption, signature generation) or secret data (encryption) can be vulnerable to side-channel or fault attacks.

Cautionary note: many uses of textbook RSA in introductory literature, and even in the industry, violate 6 to some degree. There is anecdotal evidence that when making goofs there, choosing very small $e$ (like $3$, or much smaller than $n$) makes things worse; but there is no evidence that $e=3$ is less safe than $e=2^{16}+1$, or that any low public-exponent attack applies, when abiding to 6.


plaintext distribution ,perfect secrecy cryptosystem

Perfect scheme \Pi defined such that for every distribution over M and every $c\in C$ it holds that:  $Pr[C=c|M=m]=Pr[C=c]$ which means that probability to get a cipher text $c$ is independent of the message been encrypted, thus independent of the distribution over the message space M.


Is sha3 better than sha2 in (m)any aspects?

SHA3 is built on-top of a fundamentally different construction than SHA-2 which has many nice properties. So yes, in many hash-function relevant aspects it is indeed better. As for password-hashing, SHA-3 implementations (without hardware acceleration) also tend to be slower, which is good in this case.

However.

  Is use of sha3 justifiable?

NO. Do not use a fast hashing function for password hashing. Use a dedicated password hashing scheme (PHS) such as Argon2 or bcrypt. These have been heavily reviewed, analyzed and even been built around the idea of being used for password hashing. They do their job really well and give you and your users the best possible security to the standards threats that you have to deal with when handling passwords on standard modern CPUs with fast RAM access.


Pairing Field size as security parameter

Thats a bit outdated as for your choice of setting (with $k=6$) the 170 bit will give you 1020 bit security in the subgroup of $F_{q^6}^*$.
In your case for embedding degree 6 I would at least take 224 bits which would give you 1344 bits in the multiplicative subgroup of $F_{q^6}^*$ or you even go to 256 bits which will give you 1536 bits. Anyways the setting with embedding degree 6 will give you not an optimal efficiency-security tradeoff as you have to take far higher security levels in the curve to achieve acceptable security levels in $G_T$.
The choice of Baretto-Naehrig curves will give you the optimum security-efficiency tradeoff (they have $k=12$) today and they are for instance implemented in the RELIC toolkit.
You may look here what parameters for elliptic curves and multiplicative groups of finite fields are recommended today by different institutions.

Update (2021): As mentioned in the comments, already in 2014 the parameters mentioned above for MNT curves only gave security (far) below 100 bit. For an up to date reference on parameters one can look here: https://members.loria.fr/AGuillevic/pairing-friendly-curves/


Number of words to be outputted from PBKDF2 based on HMAC-SHA512?

PBKDF2's output is defined by the underlying functions which produce 160 bits (20 bytes) at a time. Let me explain using RFC 2898 which defines PBKDF2.
OK, so lets start with the output of PBKDF2 and work backwards:

Concatenate the blocks and extract the first dkLen octets to produce a derived key DK:
DK = T_1 || T_2 ||  ...  || T_l<0..r-1>

Now the values of T_x are defined as output of function F:

F (P, S, c, i) = U_1 \xor U_2 \xor ... \xor U_c

and U_i is again the output of the PRF. The PRF is the HMAC value and the HMAC output size is the same size as the underlying hash function.
OK, so the output size of the of the T_x values is consists of 4 blocks of length hLen (4 times 160 bits for SHA-1, making 640 bits or 80 bytes), the hash length. If there were 3 blocks then the output would be 60 bytes and you'd have 4 bytes too few.
Each hash consists of five 32 bit (4 byte) words, to make 160 bits. The size of a word in this case is determined by SHA-1 which is defined using 32 bit calculations. The same 32 bit word is used for the other calculations such as XOR. So in total the number of words in the output is 80 / 4 = 20.
So what you have there is the value of the output before the leftmost 64 bytes are taken. In general cryptographic functions should convert the output to bytes/octets of the correct size. But that has clearly not happened yet.

There is no problem for PBKDF2 with SHA-512 for the simple reason that you ask for exactly 512 bits, the output size of SHA-512 (i.e. four 64 bit words, as SHA-512 is defined using 64 bit operations).
Note that it could still return eight 32-bit words if the implementation uses 32 bit words instead of 64.


Can randomness protect a list of signatures against forgery attacks?

If $l<k$, then the attack will be detected with a probability 1.

If $l\ge k$, the probability of the attack not being detected is
$$\frac{l}{n}\cdot \frac{l-1}{n-1}\cdots \frac{l-k+1}{n-k+1}\ge (\frac{l-k+1}{n-k+1})^k$$

Whether this is large enough or not depends on $n,k,l$.

If the attacker does not know $k$, the best he can do is to choose $l=n-1$, which gives him the highest probability of not being detected.


If you have two keys of constant length, using HKDF is rather pointless.

You can simply combine them using a hash function like SHA-2:

$$combined\_key = \text{SHA-2}(k_1 || k_2)$$


what is the difference of Pretty Good Privacy and Gnu Privacy Guard

Both PGP and GPG are software implementations of the OpenPGP protocol. Typically when people say "PGP" they refer to the OpenPGP protocol.

OpenPGP itself specifies the formats for messages and keys. Both the PGP software and GPG are implementations which produce OpenPGP messages and keys.


Should we use modulus switching when dealing with ciphertexts encrypted in different rings?

The problem is that operations between such $c_1$ and $c_2$ are not even defined. You have to reduce the coefficients of the resulting polynomial modulus either $q_2$ or $q_4$, so, you have to switch one of them.

Switch $c_2$ into $R_{q_2}$ would work as well, but since it would increase the noise in $c_2$, it is smarter to switch $c_1$ into $R_{q_4}$ (which gives you meaningful operations and also decrease the $c_1$'s noise).

I think the only way to avoid this switching is to treat both the polynomials as elements of $R$ and check if the coefficients of the resultant polynomials are not greater than $q_4$, because this means that no reduction would be done in the coefficients if operations were done in  $R_{q_4}$ and so the resultant polynomial is a valid ciphertext in $R_{q_4}$ and in $R_{q_2}$.

Anyway, the modulus switching operations is not expensive, and it also reduces the noise, so, I don't see advantages in avoiding to do them.


Hermitian curves introductory references

"Algebraic Geometry Codes: Basic Notions" by Tsfasman, Vladut, and Nogin is a textbook that is available as a PDF. Discussion of Hermitian curves begins on page 167.

I haven't read it and no very little about coding theory. It was the reference a friend provided in his dissertation, which included constructing universal hash functions from Hermitian curves.


Cryptopals challenge 2.11: Distinguish ECB and CBC encryption

Hint: Use the plaintext XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX, where the (arbitrarily chosen) byte X is repeated at least 48 = 3 × 16 times (so that, no matter how many random bytes are prepended to this plaintext, it will always cover at least two successive AES blocks).


RSA - PKCS#1 padding - overall correction of algorithm

The case that the (encoded) message may be too long for proper encryption has already been envisioned and mitigated by the designers of the specification of the padding scheme.

First note, that $k$ in fact denotes the length of the modulus $n$ - in bytes. This length is always accurate, so if $k=256$ the modulus has a bitlength somewhere in $[2041;2048]$ or otherwise $k<256$ if the modulus was shorter.

So let's consider what can happen regarding the length issue.
If you choose the length of your message $mLen$ to be larger than the modulus, step one of the specification tells you to output "message too long". Theoretically you could apply the rest of the scheme if your message was three bytes shorter than the modulus, but it allows only for 11 bytes shorter to allow the random string $PS$ to take at least 64-bits length.

And finally let's consider how long $EM$ is. If you convert EM to an integer you'll get $k-1 = EM$ as the first byte is zeroed out. To make things sure even the second most significant byte is nearly completely zeroed out (except for the bit #15 you correctly identified). But as the modulus is guaranteed to be of accurate length, you'll never get this equation not to hold: $$n>2^{8(k-1)}>2^{8k-14}>EM > 2^{8k-15}$$


But what if I use a keyed hash (like Blake2b) with a server key and
  then hash the user ID to generate the user key to avoid the need to
  hold a database of randomly generated keys?

Let's make some assumptions: the user IDs are unique and Blake2b with a keyed input acts like a PRF and you supply a long-enough key, all of which are reasonable. Then for any given (userID,hash) pair you can't learn anything about the other pairs (if you're computationally bounded).

There are a couple of potential issues with this though:

The user can't choose their credentials themselves, users may dislike this.
It is potentially easier to exfiltrate a short secret than a large amount of data (like in a database).
You must ensure that the userID is always given in the exact same encoding to the hash function.
If the credential gets compromised on the user end, the user also has to change the userID or you have to change the master key
Key roll-over gets harder as every client needs to log-in to receive their updated access token

There's an upside to this sort of scheme though: If you want to, you can put the secret inside a HSM and use HMAC-SHA256 instead of Blake2b and mitigate the key exfiltration risk


Is it safe to use signed messages from a private key to send to clients as tokens?

They should be. As long as your signature scheme is resistant to existential or at least selective forgery, [under chosen message attack]. Well, I am not sure if the scheme requires resistance to forgery under chosen message attack unless you set up your application in which your server works as a signing oracle but no worries, most state of the art signature schemes are resistant to existential forgery under chosen message attack. As long as you don't use outdated signature schemes, the ones that hash the message directly using MD5 or SHA1, the signature can be forged by creating hash collisions.
In fact that's what popular JWT tokens are. They are just base64 encoded json objects with some content (like who it is issued to, expiry time etc),which may or may not be encrypted, and appended with a signature of that content produced using server's private key (or alternatively contains a MAC of the object produced using a key secret to the server but this method has a disadvantage in that no one else can verify the authenticity of the token).


What does ChopMD refer to in the default Go ECDSA package?

Let $n$ be the digest length of a hash function $\operatorname{MD}^f:\{0,1\}^*\to\{0,1\}^n$. Now quoting the paper you linked:

  chopMD. For $0\leq s<n$ we define $\operatorname{chop}_s(x)=x_R$ where
  $x=x_L\parallel x_R$ and $\left|x_L\right|=s$. In this paper we fix
  $0<s<n$ and define
  $\operatorname{chopMD}^f(M)=\operatorname{chop}_s(\operatorname{MD}^f(M))$.

So the idea is basically "take the value, run it through the specified hash function and discard ("chop off") the first $s$ bits", which is a pretty intuitive and standard ways to get a small-domain hash function from a large-domain hash function.

So TL;DR: It appears the package runs the given data fields through SHA-512 and then only returns the last 256 bit of the resulting hash.


DROWN - decrypting ServerVerify message is not enough?

No, it's not a mistake. After Bleichenbacher's attack was discovered, the fix throughout SSL/TLS was to prevent the "padding oracle" by decrypting and following this strategy: if the PKCS#1v1.5 padding is correct, then use the PMS obtained; if the PKCS#1v1.5 padding is incorrect, then use a random PMS. This prevents the oracle since an attacker who doesn't know the PMS cannot distinguish these two events (they are also supposed to take the same amount of time). However, in SSLv2, since it takes only $2^{40}$ to brute force the server reply, it's possible to re-establish the oracle. Specifically, the attacker gives the ciphertext twice to the server. If the padding is correct, then the server will reply with the same key both times. If the padding is incorrect, then since the server chooses a random key in this case, it will reply with different keys. This enables the attacker to know if the padding in the RSA encryption was correct or not.


Number of plaintext–ciphertext pairs needed to rule out false keys with a reasonable likelihood in AES

I cannot see why such values are required for AES-192 and AES-256.

That's because you have a correct understanding of the situation, and the answer manual is wrong.
Your analysis in "what I tried" is correct; there's not a whole lot I can add to it...


Directly applying the RSA-function to a message is not secure in real life. The function leaks all kinds of information about the underlying plaintext and is particularly vulnerable to active attacks (where the attacker might be able to learn something about some related message also encrypted under RSA, and use this to learn what the original message was). Unfortunately, some textbooks only present RSA as you have done above and leaves it at that, hence the term textbook-RSA is often used for this raw application of the RSA-function to the message.

However, the good news is that if your message was somehow chosen completely at  random within $\mathbb{Z}_n$ (the full plaintext space), then applying the RSA-function would actually be secure. Unfortunately, in real life, our messages are seldom   completely random, but rather chosen from a very tiny subset within $\mathbb{Z}_n$. The solution is to randomize the message using padding so that our messages takes up a much larger possible subset within the plaintext space. Additionally we make it so that equal messages encrypt to different ciphertexts each time which is important.
In real life we use RSA like this:

Encrypt: $m \mapsto$ randomize message using some padding scheme $\mapsto x$ $\mapsto c = x^e \pmod n$

Decrypt: $x = c^d \pmod n \mapsto$ check whether $x$ has the approptiate padding $\mapsto$ if yes: strip of the padding from $x$ and return $m$; if no: return Fail.

The question then becomes: how should we pad the message $m$? OAEP is one such padding scheme (there are actually many ways how this can be done, but not all of them are secure. RSA-OAEP fortunately is). So how does OAEP-work? You should check out the description on Wikipedia, but this picture goes a long way of explaining it:

$\hskip 2 in$

After the message you pad with some zero's then append a completely random string $r$. Then feed these through a couple of hash functions $G$ and $H$ and some XOR-applications and output the padded message $x \| y$. Then you encrypt this padded output. When you decrypt you basically reverse the whole process and verify that you have the right number of zeroes at the end (before the $r$).


Why generating random consumes an entropy?

For the same reason that to generate true random bits using coin throws, one needs to throw a coin for each bit generated. Any attempt to use less throws is doomed (against a computationally unbounded adversary, or if the technique relies on few simple bit combinations).

  Why generating a random bit causes that entropy to become useless?

Revealing a generated random bit is what makes it useless towards generating further secure random bits.

There's a solution: generate a sufficient number of random bits (like 256 or more) and use these, exclusively, to seed a Cryptographically Secure Pseudo Random Number Generator which will supply an endless stream of bits that have all testable properties of truly random bits. That's part of the strategy of Unix's /dev/urandom


Derive $x$ when given $g,g^x$ and $g^{(1/x)}$?

Any group where you can derive $x$ from $g, g^x, g^{1/x}$ would also have the Discrete Log problem be equivalent to the (computational) Diffie-Hellman problem.  Since this is not known to be true in general, we don't know of any general method for deriving $x$ from those values.

This equivalence is quite simple to demonstrate; if it based on the fact that solving the cDH program allows us to compute $g^{1/x}$ given $g, g^x$.  So, if we assume we can recover $x$ from $g, g^x, g^{1/x}$, then we can solve the Discrete Log problem (given $g, g^x$) by first recovering $g^{1/x}$ (using our cDH Oracle), and then given $g, g^x, g^{1/x}$, recover $x$


Proof of non-membership on a Merkle tree?

If you are not worried about revealing information, then you can commit to the set of data items in one Merkle tree, and to the frontier of that set in another Merkle tree. A frontier is the set of ancestors to all values that are not in the tree (note that this is about the same size as the size of the set itself). Then, in order to prove that a value is inside the set you work with the first tree, and in order to prove that it is not you work with the second tree.

However, I strongly recommend that you read this paper on Zero-Knowledge Sets by Micali, Rabin and Kilian. First, the notion of a frontier mentioned above is defined. Second, they provide a formal definition and analysis. Third, they achieve something much stronger which is that nothing but the fact that the element is in or is not in the set is revealed (not even the size of the set). There was some follow up work on zero-knowledge sets as well, but you can find them easily by Googling.


How to design a cryptographically secure file hosting service

Generate key-pair
Generate random salt, hash password with proper password hash (scrypt or PBKDF2) to derive a master key.
Use HKDF to derive one login key and one encryption key from master key
Encrypt private key with encryption key from previous step
Upload it to server, download only possible by proving possession of login key (either send over SSL, or use SRP)
Encrypt files with random AES key, encrypt AES key to public key of a user


Encryption method that is purposely vulnerable to cracking parts at a time?

Encrypt a short known plaintext ($s$ bits) using truncated keys (to $s$, $2s$, $3s$, etc. bits) and publish them alongside the ciphertext. Then an attacker can break them in order of increasing keylength, until they recover the full key.

There is a quite similar vulnerability when performing a chosen-ciphertext (online) attack against short polynomial MACs. For example consider GCM with a short 32-bit authentication tag (hence you should never use short tags). The attacker submits messages to an oracle and learns if they're accepted or not. After a successful forgery (chance $2^{-32}$) the attacker learns 32-bits of the MAC key. After several successful forgeries they can recover the full MAC key. The decryption key can then be recovered using standard oracle attacks against unauthenticated CTR mode.


No, asymmetric encryption or other known purely cryptographic techniques do not solve the problem stated in the question. When device keys are extracted, any (future, see below) firmware update for that device can be deciphered.
The best we can do in this direction without some trusted hardware:

After deciphering and installing a certain version of a firmware, the device can forget the key used to decipher it, and use a new key (e.g. embedded in the firmware just downloaded, or derived from the earlier key with a ratchet mechanism). This limits exposure of past firmware, with the side effect that firmware downgrade is not possible. Things can be arranged so that some firmware upgrades can be skipped.
We can use security by obscurity, including white box crypto, which aims at making key extraction impossible (in other words making simulation of the actual decryption the best way to decipher). That theoretically fails, but practicaly succeeds to some degree.
Deciphering keys can be device-unique, but then the encrypted/signed firmware is also device-unique.
By making the encryption process dynamic (which makes sense if the update process is online), the key protecting the firmware's confidentiality can be an ephemeral session key, so that extracting the device's long-term key is not enough to decipher the firmware from a line intercept. However such extraction is theoretically enough to impersonate the device, connect to the update server, and get the firmware enciphered under a known session key, thus this is security by obscurity.

Update: the last two bullets do not apply given new comment to the question that all devices are the same and share the same cryptographic keys. Also, it’s not an online protocol.
Update per comment to this answer: indeed, signature works to prevent the creation of valid firmware that installs on genuine devices. That's a strong mechanism, resisting extraction (but not replacement) of device keys, provided no exploitable bug in any firmware allows to take full control of the device and circumvent that signature mechanism. Firmware signature is Independent of firmware encryption, which the rest of this answer is about.
Update: As noted in another comment, asymmetric encryption does not bring value in the situation, thus we want to use symmetric cryptography for the encryption part.


Yo are taking only the one-to-one functions, while there are a lot of other functions, to name a few:

00 00
01 00
10 00
11 00

00 01
01 01
10 01
11 01

00 00
01 00
10 01
11 01

as you already mentioned, each table can be represented with $n*2^n$ bits, i.e. strings from the set: $\{0,1\}^{n*2^n}$, each string from this set defines one function from $Func_n$, so the number of such functions is the size of the above set $=2^{n*2^n}$


A cryptographic hash function will produce an output with pseudorandom properties, therefore when expressed in hexadecimal, a list of hash values will have an almost equal number of each character. Pseudorandom data will not compress, as compression looks for patterns. If you had duplicates, compression could reduce the data size.

If you want to compress the list, take your hexadecimal string of 32 characters, and convert it back to ASCII character values, taking up 16 characters. If you need it to be text readable, that can be encoded using Base64 or a variant, which will take 22 to 24 characters.


Facebook app-scoped identifiers and similar - implementing stateless ID obfuscation

Reversible implies collision-resistant, as you have defined it.  The criteria you have written down are essentially the criteria of deterministic encryption; if you add the criterion that it be hard for anyone without an app's key to forge a masked user id, then deterministic authenticated encryption[1] is exactly what you seem to be looking for.

If a user id is at most 64 bits, you could simply use AES itself as a deterministic authenticated cipher: $$\operatorname{mask}(\mathit{user\_id}, \mathit{app\_id}) := \operatorname{AES}_{k_{\mathit{app\_id}}}(0^{64} \mathbin\| \mathit{user\_id}).$$  The masked user id is 128 bits long.  If, on decryption, you verify that the upper 64 bits are all zero, what you get is a deterministic authenticated cipher with distinguishing and forgery advantage bounded by about $2^{-64}$.


What is the function of the secret key “r” in Poly1305?

$Poly1305_{{r,s}}(m)$ is a one-time authenticator - it can be used to authenticate only a single message with any given key $(r,s)$ without violating the security guarantees (the violation is immediate - only two authenticated messages with the same key are required to create a forgery according to the nacl docs).

There are two 128 bit key values to this function (commonly combined into a single 256 bit key):

$r$ is the basis for the polynomial evaluation (in a specific format with some bits cleared)
$s$ is a key value that is added at the end to the result of the polynomial evaluation

Both of these values are part of the key - the specification requires that the key (including $r$) is unpredictable, and the size of the set $R$ from which $r$ is sampled does factor in the security proofs, so I would presume that exposing $r$ would compromise the security guarantee to some degree. Given the $2^{106}$ bound on that security, I would treat all parts of they key as secret.

$Poly1305{-}AES_{(r,k,n)}(m)$ extends $Poly1305$ into a general purpose MAC function - i.e. it can be used to authenticate many messages with a single key $(r,k)$ as long as the nonce $n$ is not repeated.
The extension is achieved by replacing the $s$ value in the one-time authenticator with the result of $AES_k(n)$, which produces an unpredictable value for each unique nonce.

The $AES$ part of the calculation can be replaced by another secure cipher - e.g. the nacl library uses $xsalsa20$ to encrypt the nonce, but other block ciphers like Serpent/Twofish etc. will work just as well.


Would this program be useful in cryptography?

I can several possible questions in the original post, hopefully I'll manage to answer at least one of them here.

I have calculated a large $N$, with $\log_{10}(N)>600,000$. Is this suitable for RSA?
We have that $\log_{10}(N)>6*10^5>2^{19}$, meaning $\log_2(N)>2^{19}$. Currently, implementations with $\log_2(N)\approx 2^{11}$ are coming into practice, making your choice of $N$ much much larger than those in use today. There's a nice little crypto.SE question here stating that there is no need for $N$ orders of magnitude greater than $2^{2048}$, with good references.

Is my multiplication algorithm good for taking the product of Mersenne Primes? I'm sorry to say the answer is almost certainly no. Multiplying large numbers is something that has been studied in depth over the years, and the odds are your program does not provide a breakthrough. In the particular case you've given (Mersenne primes), there is an efficient way to solve it anyway, so I suspect your implementation isn't as efficient as it could be:

Working in binary notation (as your computer will be), $(2^{756839}-1)$ is the number given by 756839 consecutive 1's. Since $$(2^{756839}-1) * (2^{1257787}-1) = (2^{756839}-1)*2^{1257787} - 2^{756839} + 1$$
the answer will (in binary) have 756838 ones, followed by a single zero,followed by ~50100 ones, followed by 756839 zeros and then finally a 1.
(nb: my counts may be out by $\pm1$, but the idea holds)

Part of this answer is drawn from my comments on the original post.

Is my algorithm good for taking the product of two large integers? I do not know the headline speeds for integer multiplication in general, but I'm pretty sure you should be able to do this a lot more quickly than you have, especially since your multiplication doesn't make use of the binary representation of its operands. You can easily test this by downloading reference code for Big Integer multiplication and timing yours against that. If you have a licence, Magma or Mathematica are both good candidates for a first test.
UPDATE: In the comments below, Reid provides benchmarking figures for Mathematica, demonstrating that your times are well off these, which should themselves be considered lower bounds.


Is there a way to make a black-box function side-channel attack resistant?

If I have no knowledge of the inner workings of a function, (i.e. a black box function) is there a way to make it side-channel attack resistant?

No, not really.  When we make a cryptographical function 'side-channel' resistant, we generally use one of the following strategies:

We modify the cryptographical implementation not to leak anything to that specific side-channel.  For example, for timing and cache side channels, we can make the algorithm run in constant time and constant memory accesses (or, at least, independent of any secret data).
We modify the cryptographical implementation to scatter the internal information so that getting information on only part of the cipher state does not divulge any information about what we're actually doing.  For example, in a "thresholding" implementation, we might convert each bit on the cipher state into three internal bits (where the state of the logical bit is the exclusive or of the three internal bits).  By doing this (and randomizing each individual internal bit), we ensure that the adversary needs to get side-channel information on all three bits simultaneously, rather than any one or two...
We can exploit the mathematical properties of the cryptographical operation, performing the operation on random data, and then converting that into the result we are interested on.  The canonical example of this is RSA ciphertext blocking; when we want to decrypt a ciphertext $C$, we select a random value $R$ and compute $R^eC \bmod N$ (where $e, N$ is the RSA public key); as $R$ is a random value uncorrelated to $C$, this is a random value.  We pass this value to the low-level RSA decryptor, which will return $RC^d \bmod N$.  We then multiply this by $R^{-1} \bmod N$, and that gives us the actual plaintext.

Unfortunately, none of the above actually works in your scenario.  The first two involves modifying the cryptographical implementation, which you can't do,  The last uses mathematical properties of the cryptographical algorithm, which a black box generally will not have.


I think it's OK in this instance: an attacker cannot check the first half of the hash (160 bits) because he cannot use AES-256 yet; the key is incomplete. So he needs to run the second half too. He needs the full key to check the decryption.

The OWASP guide refers to the case where the output of the PBKDF2 function is stored directly as the hash-check in a database. In that case the first 160 bit check is already enough to discard almost all invalid passwords. In the rare case the 160 first bits match, you can do the second half to confirm, and that's no extra work, really.


Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

By definition, a dishonest verifier may be able to completely extract the witness from an honest-verifier ZK proof.

To prove this: take any zero-knowledge proof, and add an initial round where the verifier sends 1 to the prover. The prover then works as follows: if it receives 1 then it runs the original zero-knowledge proof; if it receives 0 then it sends the witness.

The above proof is clearly honest-verifier zero-knowledge, but a dishonest verifier can learn the witness by sending 0.

Typically, the point of an honest-verifier zero-knowledge proof is that it can be "compiled" into a (full) zero-knowledge proof without much difficulty.

Having said the above, some honest-verifier zero-knowledge proofs already have stronger properties like witness indistinguishability. This makes no sense for Schnorr itself since there is only one witness, but I believe that the standard Diffie-Hellman tuple sigma protocol is witness indistinguishable (I would want to write a proof to be 100% sure but I'm nearly sure).


First of all, this attack assumes that we have a decryption Oracle; that is, an Oracle that we can submit any ciphertext to (except for, apparently, the challenge ciphertext), and it will tell us that the padding is bad, or it will give us the decrypted message (minus the padding).

In the attack, we're given the challenge ciphertext $(Pad + M)^e$, and we select a simple rational value $r/s$ near 1, we submit to the Oracle the ciphertext $(r s^{-1})^e (Pad + M)^e$, and if $Pad+M$ happens to be a multiple of $s$ (and the padding looks valid), we get the lower $n$ bytes of $r/s (Pad + M)$

Your question really is: given the lower $n$ bytes of $r/s (Pad + M)$ (which we will call $R$), how can we recover the lower $n$ bytes of $Pad + M$?  That's actually fairly simple; essentially we need to compute $s/r R \bmod 2^{8n}$.  Now, the divide by $r$ is slightly tricky (and computing $r^{-1} \bmod 2^{8n})$ is the wrong approach); however we know that the full value $r/s (Pad + M)$ is a multiple of $r$, and so one way to do is is to find the value $0 \le k < r$ such that $R + ks^{8n}$ is a multiple of $r$, and then divide that by $r$; that'll give the same lower bytes as the original $r/s(Pad + M)$.

Now, going back to looking at this attack in general, we find this attack is less powerful than the Blechenbacker attack, which will allow us to decrypt any message, and makes weaker assumptions on the Oracle (namely it doesn't have to give us the decrypted text on success; only notify us that success did happen).  This attack does have the advantage that, if successful, it requires fewer queries (but it won't always be successful, perhaps $Pad+M$ doesn't happen to have any small divisors), and it is easier to understand.


Security of basic SHA256 MAC in an authenticate-then-encrypt scheme

Unfortunately your question doesn't fully specify the authenticated-encryption mode. In particular, AES is a block cipher, not a mode of operation, and only operates on plaintexts of some fixed length (128 bits for AES). So you need to fix a mode-of-operation for AES, such as CBC mode or CTR mode. (Never use ECB mode.)

Let's assume you used CBC mode. Then the final Authenticate-then-Encrypt mode you outline is indeed more commonly referred to as MAC-then-Encrypt or MAC-Encode-Encrypt. The latter is a bit more accurate, as it captures the fact that often one needs to encode the concatenation of the message and message authentication tag as a plaintext string that is compatible with the encryption mode of operation. For example, CBC mode only accepts plaintexts that are a multiple of the underlying block cipher's block size (for AES this is 128 bits).

In general MAC-Encode-Encrypt is never recommended for use in modern applications. Why? Because it's near impossible to implement correctly. One must first decrypt, then properly decode, and only then can check the MAC. The first two operations are done before checking authenticity and many clever attacks have shown how to confuse decryption implementations. See Lucky 13 for a recent example, and the included references to padding oracle attacks.


All of the arithmetic is done modulo $l$ here.  The notation is slightly confusing—I would have written it as: $$s_j \equiv \alpha - c_j\cdot x_j \pmod l.$$  It may not actually matter whether the integer representative you choose for the scalar is positive or negative; there are many equivalent choices of scalar that will yield the same result when you multiply a curve point by them.  (But the specific algorithm you use to compute scalar multiplication may impose constraints on the integer, like being positive and below a certain size.)


What should be broken to break a cipher with perfect forward secrecy?

If the key exchange (i.e. (EC)DHE) is broken then a passive observer might be able to find out the symmetric key used for encryption which thus would allow the attacker to decrypt the traffic.

If instead only the public key or signature algorithms in the certificate are broken (that's what you probably mean with RSA/EC) then an active attacker might be able to man in the middle the connection but this ability does not help in passive attacks.


IV transmission from Transmitter to Receiver side in CTR mode for every call

If you encrypted your data as $c = \mathrm{CTR}_{IV}(m)$ you can send the value $IV || c$ (where $||$ is concatenation) to the decryption side. That side then parses the value it received into $IV$ and $c$ and computes $m = \mathrm{CTR}_{IV}(c)$. No need to keep the $IV$ secret.


How to define secure pseudorandom functions?

Consider yourself an adversary. You're given access to an oracle $O(\cdot)$. You're trying to determine if $O(\cdot)$ is actually random or $F'_s(\cdot)$ with some randomly sampled $s$.
a. Consider $O(0^n)$ and $O(1^n)$.
b. Consider $O(0^n)$
In each case, consider some special event $E$. If $O(\cdot)$ is truly random, what is the probability $p$ that $E$ occurs? If $O(\cdot) = F'_s(\cdot)$, what is the probability $q$ that $E$ occurs? Your distinguishing advantage is $|p-q|$.


How to prove that permutation and substitution ciphers satisfy H(X) = H(Y) in Shanon Entropy?

For any one to one encryption mapping, which these ciphers are assumed to be, say $E:{\cal M} \rightarrow {\cal C}$ under whatever key, we have:
$$
H(Y) =-\sum_{y \in {\cal C}}p(y)\log p(y)=
-\sum_{y \in {\cal C}} p(E^{-1}(y)) \log p(E^{-1}(y))
$$
which can be rewritten as
$$
H(Y)=-\sum_{x \in {\cal M}} p(\sigma(x)) \log p(\sigma(x))
$$
for some permutation $\sigma$ of the messages.
Note that the decryption mapping exists since $E$ is one to one.


Stripping off message authentication or signature

If attackers can strip off RSA / EC / -DSA digital signature and
  conduct CCA on AES-CTR or CBC payload, why can't they do the same for
  AES-GCM?

The scenario, you're talking about is iMessage or Signal Protocol or other protocols which allow optionally to sign the ciphertext and thereby don't MAC it.

The problem here is a) that you could replace the signature with your own (if it is valid and required) or b) completely strip it off if it is not required, which would be considered a protocol flaw in my eyes.

The situation is different with AES-GCM because the authentication is a mandatory part of the specification. Any non-stupid implementation will return an "invalid ciphertext" if the tag is missing or just the last ciphertext block (i.e. largely unrelated), so this won't allow you to even get to decrypt the CTR stream and thereby exploit its CCA weaknesses.


Does the multiplicative property apply to modern, non-text book RSA?

can this apply to the real world in modern implementations of RSA?

No!

RSA is a trapdoor function and the RSA public encryption/decryption and RSA signatures are derived from them. Contrary to some people, RSA decryption is not a signature.

RSA must never be used without proper padding. It is very dangerous and example attacks can be seen from the paper Twenty Years of Attacks on the RSA Cryptosystem by Dan Boneh.

Apart from the multiplicative property, some of the attacks are;

Common Modulus attack where a group shares the same modulus in which any other user can find the others private key.
Blinding is signature forging where the forger asks a blinded, suspicious, message to sign and then convert this into a valid signature.
Low private exponent ( Wiener's attack) where the private exponent is chosen small to reduce the signature time. The attack can recover the d
Hastad's Broadcast Attack where the sender sends the same message to may. The attack recovers the message.
Bleichenbacher's Attack on PKCS 1 uses the invalid ciphertext error returned from the target and the attacker turns the target into a decryption oracle.

For encryption use

Optimal asymmetric encryption padding (OAEP), or
PKCS#1 v1.5 padding

for security comparison of these two encryption padding see this answer from Cryptograpgy.SE.
For signatures use Probabilistic signature scheme (PSS)

This question What is RSA OAEP & RSA PSS in simple terms gives a simple explanation for both.


Why does anyone use elliptic curves for a CSPRNG?

We, for the most part, don't bother with elliptic curve-based pseudorandom generators. DUAL_EC_DRBG was shoehorned into a NIST standard that also included a block cipher generator, CTR_DRBG, and two hash-based ones—Hash_DRBG and HMAC_DRBG—that are actually used in the field.

Number-theoretic generators, which include Blum-Blum-Shub, DUAL_EC_DRBG, and several others, tend to advertise provable security. What this means is that predicting the next bit reduces to solving a presumably hard problem, like integer factorization or the discrete logarithm problem. While this is appealing to mathematicians and theorists, this kind of generator tends to be very slow and hard to implement correctly, i.e., without leaking state information via a side-channel or buggy arithmetic.

Practitioners highly favor generators based on symmetric primitives that are much faster and easy to implement and reason about and—as a bonus—also happen to resist quantum computers, if those ever get built.


Hypothetical encryption technique, is it secure?

First, I would like to point you to this answer. Copying the TL;DR from there:

  Multiple encryption addresses a problem that mostly doesn't exist.

You are better off using a single well chosen algorithm.

That said, here are answers to some of your questions:

  A longer password adds more layers of encryption in this hypothetical scenario and thus adds more security and thus encourages longer passwords (a double positive trait)?

It is not generally true that more layers equals better encryption (cf.  Cascade Ciphers: The Importance of Being First). In particular, in those cases where it can be proved that it is as strong as even one of the layers it is assumed that the keys are independent. Your keys are clearly not independent.

  That no file (assuming each password is different) will be encrypted the same way twice?

If by "same way" you mean into the same ciphertext, then that is already the case with any secure encryption algorithm (with high probability). If you mean with the same cascade, then probably so, if you have as many techniques as different symbols. I.e. a-zA-Z etc. all give a different algorithm. Otherwise some passwords that differ will still lead to the same cascade.

  The password is the only major vulnerability?

No, the algorithms can also leak information about the password through e.g. implementation mistakes or even weaknesses in the algorithm. And the more algorithms you implement, the higher the chances one of them is buggy. As an example of such a mistake:

  The program progresses through each symbol in the password encrypting the file with a different algorithm at each stage.

This is probably almost impossible to implement without timing attacks, so in any situation where the attacker would be able to observe how long it takes to encrypt/decrypt something, they could learn things about the password, narrowing down a brute force or dictionary attack even if they are unable to recover the whole password.

If you nonetheless wish to use more than one algorithm to guard against breaks, I recommend:

Use just two, always. That is simple enough to limit issues and the chance that both are broken should be small with modern well vetted algorithms.
Use stream ciphers (or block ciphers in CTR mode). Their cascade is provably as strong as the stronger if the keys are independent.
Use independent keys that you derive from the password using a strong password hash.
Add authentication.

For example, you could use AES-GCM(ChaCha20(m)), with keys derived using scrypt.