Finding Galois LFSR and its initial configuration

In general, you're missing both the polynomial (taps) and some symbols, so there is no unique solution.

The LFSR is determined by its generating polynomial and thus its degree/length/taps. If the LFSR is 5 bits or more in length you're out of luck, you need 5 equations so 5 bits of information for any hope of solving this.

If it is 4 bits long, and primitive, you're in general out of luck again in the absence of any extra information, since all loadings, and in particular both states
$$(s_1,s_2,s_3,s_4)=(0,s_2,0,0)$$ with $s_2$ arbitrary are possible.

However, if $s_2=0$ this will give a trivial LFSR of all zero output, so if you're not in this setting you can assign $s_2=1$ and proceed, if the LFSR is 4 bits long. Then you might try all possible primitive LFSRs (there are 2 of length 4) and have 2 candidates.

If it is 3 bits or less, again, if the all zero state can be ruled out, you can proceed by trying all primitive LFSRs and in fact now you have 4 bits of info (4 symbols after ruling out all zero state) for a $L=3$ so you should be able to determine the LFSR uniquely if it is primitive (there are 2 here).


Improving security of (authentication) protocol

The original is completely broken and would be regardless of the insecurity of DES.

The ECB encryption of a single block message (with a secure cipher) would be a secure MAC, but XORing the message blocks means that an attacker can modify any block of the message simply by making the same change to another block so that they cancel out.

The modified protocol is better, but not necessarily secure. For example, if the attacker can see two messages whose last blocks are "compatible" so that switching one for the other does not affect the aggregate XOR, the attacker can make that change knowing the MAC will match. I think this scheme effectively reduces to hash-then-encrypt (with an insecure hash, even), which is not secure. Even better attacks may exist.

You would be better off with an actual MAC algorithm. For example CMAC, if it must use a block cipher.

A minimal change would be to rip out all the current MAC code and replace it with just sending M, AES-CBC-MAC(len(M) || M), where len(M) is the length of the message as a 64-bit integer and || is concatenation. This would be secure authentication, but would of course not hide the message.


When would you increment a nonce and when not?

My only idea is that B authenticates himself to A, because if A later decrypts it, A will see whether B was able to decrypt it. But why would you need to increment the nonce?

Correct, that's the idea.

If B didn't need to increment the nonce and just encrypted the same value, the message sent back would be the same that A sent, so an attacker would be able respond correctly without knowing how to decrypt it.

There are other ways to accomplish the same in other protocols that do not use increments. For example, B could encrypt it with another shared key.

  So are these two use-cases for the same purpose? Just to authenticate Bob to Alice? What is the difference between them? When would you apply which of these two and why?

In terms of authentication there is no real difference. They both prove to Alice that Bob has the correct key.

The one with encryption and increment is slightly less efficient, due to requiring both parties to encrypt and decrypt the values. However, it has the advantage of not allowing an attacker to directly ask for encryptions of chosen plaintexts, with which they could attack other uses of the same key. This is not necessarily a problem if the key is only used for authentication, but in the case of Needham–Schroeder the objective is to establish a session key.


Textbook-RSA meet-in-the-middle attack against other RSA based schemes?

I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar).

If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude.

For example, the attack can work if the message were a product of two 64 bit numbers; however this would imply that the message itself was no longer than 128 bits.

This is a credible attack against textbook RSA used to pass 128 bit messages; however any sane public key encryption method (such as ISO 18033-2) would include padding to make the message presented to the RSA primitive much larger; this completely invalidates this attack.


How to check whether the permutation is random or not

There are at most $n \cdot (n - 1)$ permutations of $\mathbb Z/n\mathbb Z$ of the form $x \mapsto ax + b$: if $n$ is prime, there are $n - 1$ choices for $a$ and $n$ choices for $b$ under which this is a permutation.  There are $n!$ permutations of $\mathbb Z/n\mathbb Z$ altogether.  So the probability that a uniform random permutation has this form is negligible if $n$ is even modest in size—the probability is at most $n \cdot (n - 1)/n! = 1/(n - 2)!$, which gets very small very quickly as $n$ grows.  For example, for $n = 64$, this probability is already less than $1/2^{256}$, which, in cryptographic terms, is not-gonna-happen squared.

You can confidently verify whether it has this form given oracle access to the permutation simply by querying it on two different inputs and solving for $a$ and $b$, and then checking it on a third point, and a fourth point, etc., to see if they match.

Exercise: Compute the false alarm rate of this test for a uniform random permutation as a function of the number of confirmation points.  The statistical power of the test under the alternative hypothesis of the form $x \mapsto ax + b$, of course, is the maximum possible: 1.
You can confidently say your friend is not being entirely forthcoming about how they chose the permutation if it has this form (e.g., it's an 8-bit permutation and you can verify all 256 outputs) but they claim they chose it uniformly at random.

For an 8-bit permutation, the probability of falsely accusing your friend in the event they actually did choose the permutation uniformly at random—the false alarm rate, or ‘statistical significance’—is below $1/2^{256}$, the equivalent of ‘$p < .0000…00001$’ (77 zeros).

However, that's only for this particular test, if you devised the test without knowledge of the permutation.  If your friend gives you a permutation and based on the permutation you devise a test that it fails, that may not mean anything—for any particular choice of permutation, there are many tests with low false alarm rates that it will fail.  And if you string many tests together, so that any one of them will raise an alarm, then the false alarm rate rises—a standard consequence of ‘$p$-value hacking’ or the ‘garden of forking paths’.

This question is similar to the issues surrounding the hash function Стрибог (Streebog), from the Russian federal government standard ГОСТ Р 34.11-2012 (also RFC 6986), and the block cipher Кузнечик (Kuznyechik), from ГОСТ Р 34.12-2015 (English; also RFC 7801).

In 2015, Alex Biryukov, Léo Perrin, and Aleksei Udovenko discovered a remarkable structure in the S-box—a permutation of 8-bit strings which the Streebog designers maintain was chosen at random by rejection sampling on uniform random S-boxes (archived).

When Perrin et al. identified the structure, they reasoned that the designers' story is implausible because there are $256! \approx \sqrt{2\pi\,256\,} (256/e)^{256} \approx 2^{1684}$ possible S-boxes, of which only about $2^{82}$ admit a neat concise description with the special structure.

‘But,’ you object, ‘knowing my permutation, you could invent any tiny class of permutations containing my permutation even if I really did choose it uniformly at random.  Then you could use the low probability of your class to claim that I must have chosen my permutation from that class intentionally, rather than guessing it by luck!  That doesn't mean anything!’  (This is essentially the argument made by the designers to claim that they are not lying spooks, according to Léo Perrin, as recently as a couple of weeks ago at an ISO standardization meeting.)

So Perrin put it to codegolf.SE, whose participants came up with various short descriptions of the permutation including a 78-byte, or 624-bit, AMD64 instruction sequence.

A code-golfing exercise is interesting not so much because a program can be invented that is shorter (for example, a 1-bit program for a machine that either computes the S-box if the program is 0, or returns zero if the program is 1), but because the AMD64 instruction set was presumably designed without knowledge of the chosen S-box—and if the Streebog designers really did sample from permutations uniformly at random to choose the S-box, the probability of getting one that admits a 78-byte/624-bit description in the AMD64 instruction set is at most $2^{624}\!/2^{1684} = 1/2^{1060}$.  Of course, the Streebog designers had some criteria for rejection sampling, but even if they went through a quintillion candidates this way (short scale, about $2^{60}$), the probability would remain less than $1/2^{1000}$.

Another way to look at it is:

Imagine writing down a sequence of all ${\approx}2^{1684}$ 8-bit permutations, labeling them $1,$ $2,$ $\dotsc,$ $2^{1684} - \mathit{whatever}$.  It doesn't matter what order you put them in; you can put them in any order you want, as long as you do it without seeing into the future of what I'm about to do.

If I then pick a permutation uniformly at random, there's a 1/2 chance it'll be in the first half of your sequence.  There's a 1/4 chance it'll be in the first half of the first half—that is, the first quarter—of your sequence.  More generally, there's a $1/2^n$ chance it'll be in the first half of the first half of the first half…of the first half ($n$ times)—same odds as flipping a coin $n$ times and having it come up heads every time.  If I wanted to find a permutation in that region by trying them uniformly at random until one works, the expected number of permutations I'd have to try is about $2^n$.
Now imagine writing out all byte strings: (empty), 0x00, 0x01, 0x02, …, 0xff, 0x00 0x00, 0x01 0x00, 0x02 0x00, …, 0x00 0x01, 0x01 0x01, 0x02 0x01, and so on.  Some of these are valid AMD64 instruction sequences.  Some of the valid AMD64 instruction sequences implement permutations (say, permuting the value of AL, ignoring all other architectural state).

You certainly need at least 211 bytes to cover all of the permutations this way, because with only 210 bytes = 1680 bits, there are more 8-bit permutations than there are sequences of 210 bytes.  You almost certainly need more than 211 bytes, too, because most AMD64 instructions sequences do not compute permutations—but you don't need much more than 256 bytes, because you could use a 256-byte table of all inputs and outputs in ROM and then a MOV instruction or two to use it.

So, you have now laid out a sequence of all 8-bit permutations by enumerating AMD64 instruction sequences.  Somehow, by allegedly doing rejection sampling on uniform random choices of 8-bit permutations, the designers found one that lies in the first half of the first half of the first half…of the first half of this sequence, iterated over a thousand times, an event with probability less than $1/2^{1000}$—even if they rejected a quintillion candidates first.

If you wrote out any sequence of a thousand coin toss outcomes—THTTHHHTHT…—and then watched a gambler flip a coin a thousand times coming up with exactly your sequence while looking at it, would you believe that they were doing fair coin tosses, or would you begin to suspect they might be pretty good at flipping coins to come up the way they want?

Of course, in principle, this could still be a fluke: By shopping around to different languages in the garden of forking paths, we could maybe find a language in which this permutation by chance happens to turn up early in the sequence…by shopping through about $2^{990}$ different programming languages to raise the probability of a false alarm from $2^{-1000}$ to a mere one-in-a-thousand $2^{-10}$.  But (a) it is not plausible that codegolf.SE tried out $2^{990}$ different programming languages, and (b) besides AMD64 instructions, there are also now descriptions of the same S-box in many languages that all clock in at well under 200 bytes, including C, C#, JavaScript, Rust, and Python.

There's an alternative hypothesis: Like a gambler who can make a coin come up the way they want (it's actually quite easy!), the Streebog designers may have used a method of generating the S-box that enabled compact, efficient implementation which they just aren't telling anyone about.  The outcome of such a method—even if randomized—would be much more likely to have many short descriptions in existing programming languages.  In a Bayesian analysis, whatever prior odds ratio we assigned to the hypotheses $\text{structured}$ and $\text{uniform random}$ (i.e., the relative plausibility of the two hypotheses a priori), we can write the posterior odds ratio by Bayes' rule in terms of the prior odds ratio and the likelihood ratio as:

\begin{multline*}
  \frac{\Pr[\text{structured} \mid \text{78-byte code golf}]}
       {\Pr[\text{uniform random} \mid \text{78-byte code golf}]} \\
   = \frac{\Pr[\text{structured}]}{\Pr[\text{uniform random}]}
     \cdot
     \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]}
          {\Pr[\text{78-byte code golf} \mid \text{uniform random}]}.
\end{multline*}

It is obviously hard to quantify what $\Pr[\text{78-byte code golf} \mid \text{structured}]$ is without a clearer idea of what structures the Streebog designers might have considered, but let's say that there's about a one-in-a-googol ($10^{100} \approx 2^{332}$) chance that there's a 78-byte code golf solution in a well-known widely-used programming language for the method the Streebog designers used.  In that case, we might measure the magnitude of code golf as evidence for the structured hypothesis over the uniform random hypothesis—the likelihood ratio, which is the ratio of the posterior odds ratio to the prior odds ratio, measured in decibels—as

\begin{multline*}
  10 \log_{10}
    \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]}
         {\Pr[\text{78-byte code golf} \mid \text{uniform random}]} \\
  \leq 10 \log_{10} \frac{2^{-332}}{2^{-1000}}
  = 10 \log_{10} 2^{790}
  \approx 2000\,\mathrm{dB}.
\end{multline*}

To put this number in perspective, the magnitude of evidence we demand in cryptography before accepting a message in typical message authentication code rather than rejecting it as a forgery is over $300\,\mathrm{dB}$—and remember that decibels are a logarithmic scale.  (For more on measuring weight of evidence between two hypotheses in decibels, see Jaynes's book, particularly chapter 4.)

Of course, this is a very heuristic quantification of the evidence—it should really be taken mainly as an illustration of the Bayesian shape of reasoning.  There may also be other hypotheses which this analysis doesn't consider—for instance, perhaps the Streebog designers just used a particularly bad PRNG when allegedly performing a Fisher–Yates shuffle to generate the permutations, and didn't realize that they were exploring a subspace that has an interesting relation to the AMD64 instruction set.

Exercise: Hypothesize plausible PRNGs that the Streebog designers might have used, and extend this to a many-hypothesis Bayesian analysis.

For more on the background and references, see Léo Perrin's web site and the story so far at ASIACRYPT 2019.


Why XOR and NOT is free in garbled circuit

Regarding the NOT gates in your example. Suppose the wire called $b$ has wire labels $B$ for false and $B \oplus R$ for true. Then you would garble gate "AND1" using these labels as normal, and you would garble gate "OR1" imagining that $B \oplus R$ means false and $B$ means true.

There are two equivalent ways to think about this. One is to consider the output of the NOT gate to be a separate wire (separate from the input to the NOT gate). If the NOT gate input wire has labels $A, A\oplus R$ then the output wire has labels $A \oplus R, A$.

The other way to think about it is to absorb all NOT gates into their neighboring AND/OR gates. In your example we could garble a NAND for gate AND1 and we could garble a gate $(x,y) \mapsto (\lnot x \lor y)$ for OR1. The way to actually do this is the same as above, just let the garbler switch the "meaning" of the two wire labels, locally for this gate.

Regarding free XOR: the main cost that it saves is not in generating random wire labels for output wires. (In fact, advanced GC constructions do not sample wire labels at random except at the inputs.) The savings are: (1) neither garbler nor evaluator have to evaluate a cryptographic primitive to process this gate. Instead they just make one xor computation. (2) Nothing must be included in the garbled circuit, saving bandwidth. So XOR gates are free for communication cost, and are "free" in computational cost of crypto operations (as you point out, not "free" of all computational cost since some minor xor computation is required).


What problems with "random" data would cause this result from Ent?

I've seen this before in the true random number generators I've been working on.  Look at the following test.  I've ent'd two jpegs, one 10 times the size of the other.  A jpg is highly compressed so can't be compressed much further, and incompressibility is one of the definitions of random.  It has however, some non random bytes such as control structures and the golden bytes.  So it's almost random, as is your data.

C:\scratch>ent lada.jpg
Entropy = 7.956933 bits per byte.

Optimum compression would reduce the size
of this 4685491 byte file by 0 percent.

Chi square distribution for 4685491 samples is 319354.77, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 132.0827 (127.5 = random).
Monte Carlo value for Pi is 3.027673947 (error 3.63 percent).
Serial correlation coefficient is 0.000597 (totally uncorrelated = 0.0).

C:\scratch>ent lena.jpg
Entropy = 7.947390 bits per byte.

Optimum compression would reduce the size
of this 408932 byte file by 0 percent.

Chi square distribution for 408932 samples is 33552.83, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 116.3320 (127.5 = random).
Monte Carlo value for Pi is 3.357464603 (error 6.87 percent).
Serial correlation coefficient is 0.020913 (totally uncorrelated = 0.0).

Compressibility stays similarish as a jpeg is a jpeg.  pi improves for the larger lada file somewhat as you have more samples that are randomish.  However, Chi increased exponentially as you have more and more control structures (read non random values) and as Chi uses a squared function in the calculation this error builds rapidly.

In summary, there are some values in your data set that occur at way too wrong a frequency.  A histogram of the data over the full 0-255 range in a spreadsheet /gnuplot might help to show something obvious, but with  chi of only 400 it might be subtle. You're hampering your analysis with the small sample size.  ent is typically run against an 11 MB data set to get a target Chi of about 250.

One methodology I find useful is to draw a picture of the data.  Load your data file into a pixel editor like GIMP as raw data and create a square image.  Subtle patterns will show up if you sit and stare at it for a few minutes.

There are two questions you must consider.  One, have you cocked up your randomness extraction algorithm and it's something you can eventually fix?  Two more worryingly, is are you totally, utterly and willing to stake your puppy's life on it convinced that the original source of your numbers is really random?

Supplemental:

I don't see dips in your histogram.  I see waves.  The black line identifies at least to me, two halves of the histogram.  Eight less strong ones (pink line), then 16 (blue line) and so on in powers of 2.    That kinda corresponds to bit positions.  It seems fairly regular.  Does that mean anything to you?  I think that your seeing a strobe effect between threads and your timer /counter with some jitter overlaid.  I think that the strobe effect is probably totally uniform.  I think the jitter is the source of your randomness, and I think that it's true randomness.  Congratulations.

If you're interested in pursuing the random generator thing, ent is naff at measuring entropy.  Take the file you generated for the histogram, and compress it as hard as you can. I suggest the program fp8, but zipping will be a good start.  The resultant file will be a very good measure of how many truly random bytes you're generated.

See, printing out an image (in whatever form) is useful.

(Help Centre will be angry with us for having this discussion).


Any encryption scheme can be insecure if the key space is small enough.

For example, you could perform encryption with an 8 bit RSA key.  For a key of that size, it's trivial to determine the private key given the public key.


As kodlu previously said, this text is confusing because it uses the name $F$ for two different things.
For clarity, I'll use

$P$ (rather than $F$) for a function that we already know (or assume) is an n-bit pseudorandom function. Typically a pseudorandom function "encrypts" a n-bit plaintext block to a n-bit ciphertext block using a k-bit key.
$M$ (rather than $F$) for any function that we are trying to prove either definitely is or definitely is not a pseudorandom function. As the attacker, you win if you can find any way to distinguish $M$ from a random oracle -- in other words, you win if you can show that candidate $M$ definitely is not a pseudorandom function.
$D$ is a "function of a function" that can be applied to any keyed function $M$. The text leaves unstated a few details that it expects you to fill in, but to be explicit (where + represents xor):
$$D(M, K, K', x, y) = \begin{cases} 1, & \mbox{if } M_{K, K'}(x,x) + M_{K, K'}(x,y) + M_{K, K'}(y,x) + M_{K, K'}(y,y) = 0^n \\ 0, & \mbox{otherwise} \end{cases}$$

We separately apply $D$ to two different things: first we set $M$ to a true random oracle $R$ (or a pseudorandom function $P$, which should give the same results) and calculate D, and then we set $M$ to the function $G$ given in the problem and calculate D.
(When D calls the random oracle with the two keys of length k and the two inputs of length n, we concatenate the keys and we concatenate the inputs to call a random oracle with one key of length 2k and one input of length 2n and we only use the first n bits of the output of the oracle).

  what happens if the key is the same as message such as $F_x(x)$.

In this particular problem and solution, we set the message independently of the key, so they are almost certainly not the same.
Even if they were the same, nothing special happens.
A few (old and deprecated) password hash functions set the key the same as the message: "HMACs that have the same key and message" , "HMAC SHA1 using the same value for key and message", etc.


What conditions does a provable secure cryptosystem satisfy?

Provably secure doesn't actually mean secure. Plenty of provably secure cryptosystems were broken and not because the proof had a flaw. When something is provably secure, it just meant some statement regarding it's security has been proven. There are any number of such statements.

A proof always starts off with some assumptions, such as the hardness of some underlying problem, or security property of some building block. A statement about something else can then be build on top of those assumptions. But when that statement is formalized, it is never as broad as: "$X$ is secure".  Instead the statement would be a more specific statement such as: "If you can invert $F$ you can also invert $G$, but $G$ is believed to be hard to invert. In this protocol under such and such assumption an attacker learns nothing more then he knew initially."

WPA is provably secure. They went all out on this proof. It was not just proven that the specification was secure in that no key material could leak. The implementation was proven to match the specification and the compiler was proven to work correctly.

And yet WPA was horribly broken. The proof didn't say anything about an attacker being able to coerce an all zero key. The attacker learned nothing, the security proof was not violated.

Provably secure does not imply Secure. It implies only whichever claims were actually proven.


How can I calculate the time complexity of modular arithmetic?

I'm turning earlier discussion into a partial answer. I apologize if the whole thing can be considered off-topic (we are discussing computer science, with specialization to Java, and only potential application to cryptography).

In order to discuss time complexity, we must specify the algorithm used, and that's not done in the question. However, in Java, an easy and customary way to perform integer arithmetic on numbers of 256 bits is to use the java.math.BigInteger package. Its source code is supplied with the public JCDK, in src.zip, allowing analysis. The algorithms used by this package to compute $a⋅b$, then $a⋅b\bmod n$, are essentially the so-called classical algorithms taught in primary school with base 10, only adapted to base $2^{32}$; see e.g. multiplyToLen in BigInteger.java where the actual computation of $a⋅b$ occurs.

Assuming that implementation is used, and $a$, $b$ and $n$ are of the same order of magnitude, the asymptotic cost of computing $a⋅b\bmod n$ is going to be $O(\log(n)^2)$. More precisely, I expect the number of long multiplications to be $o(2⋅(\log_2(n)/32)^2)$, and that goal is reachable by a good Java implementation of the classical algorithms, which java.math.BigInteger seems to be.

Unless something clever is done, computing $m=a^{-1}·b\bmod n$ will be by first computing $i=a^{-1}\bmod n$ (perhaps using modInverse in BigInteger.java), then $m=i·b\bmod n$. Assuming that, the asymptotic cost is going to be at least that of the second part, which was discussed above. I suspect $i=a^{-1}\bmod n$ might cost appreciably more than $m=i·b\bmod n$, even asymptotically, but my time is missing right now for a detailed analysis; I stopped after determining that the core of the computation is by mutableModInverse in MutableBigInteger.java, and this is not quite a straightforward Extended Euclidian algorithm.

Caveat: Given that a 256-bit integer uses only eight 32-bit words/digits/limbs, asymptotic cost, be in in $O()$ or $o()$ notation, likely is a poor predictor of the actual runtime; that might be dominated by non-computational overhead, especially in Java.

Edit: As references, I suggest the HAC (esp. chapter 14), and Modern Computer Arithmetic.


In the context of encryption schemes, the key is whatever piece of information the legitimate recipient of an encrypted message possesses, which allows him to decrypt the ciphertext efficiently. Hence, the key must be kept hidden from an attacker, since otherwise the attacker could decrypt efficiently just as the legitimate recipent does.


Trying to understand the use of ECC in TLS certificates

ECC is indeed used by CloudFlare's website but only for the session key agreement. The authentication is performed using an RSA 2048 bit private key. The corresponding RSA public key is in the certificate. In other words, although ECC is being used, it is not used for authentication and therefore not part of the certificate.

The ciphersuite is:

TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256

Which means TLS with ECDHE (ephemeral Elliptic Curve Diffie-Hellman) key agreement, RSA based authentication (and thus certificates). The ephemeral part means that no static private ECDH key is used on the server and no public ECDH key is therefore present in the certificate.

Or, as specified by RFC 4492 section 2.4:

  2.4 ECDHE_RSA

  This key exchange algorithm is the same as ECDHE_ECDSA except that
     the server's certificate MUST contain an RSA public key authorized
     for signing, and that the signature in the ServerKeyExchange message
     must be computed with the corresponding RSA private key.  The server
     certificate MUST be signed with RSA.

To state that the CloudFlare website is using ECC certificates (not certification, that term means something else) is therefore incorrect. It uses a cipher suite that performs ECDH key agreement.

The used explicit or named parameters are determined during the handshake. The client has the ability to include a list of supported curves, ordered to preference RFC 4492 section 5.1.1. The point format - uncompressed (default) or compressed - can also be indicated. As the EC points themselves are ephemeral (short-lived) you can only retrieve them by analyzing the handshake.

For completeness the rest of the ciphersuite: AES-128 bit encryption using GCM authenticated (AEAD) mode encryption. The final SHA-256 is used as definition of the keyed hash (HMAC) used for key generation (or key derivation) and validation.


What is the definition of dummy password?

It appears this term is only used in the proof. In this context "dummy password" is to be understood as
"some value that syntactically fits the requirements of a regular password including matching the length of the replaced password but is not actually the password to be used in this exchange".
The point here is that an adversary cannot distinguish between the actual password being contained in a value and some other "fake password" being contained in a value which then allows one to argue that an adversary learns nothing about the password given that they can't even tell whether the real one is used thus helping in proving that the exchange leaks nothing about the value of the password.


Isn't fully homomorphic encryption trivial with a complex enough decryption function?

No, this is not considered homomorphic encryption.  This is excluded by requiring that the ciphertext size and running time of the decryption operation be bounded by the security parameter, independent of the circuit size.  Your pathological example is given as the first footnote in Craig Gentry's seminal paper on a realization of FHE.


Cryptanalysis in the middle ages -- publications

Holden's "The Mathematics of Secrets" has nearly comprehensive explanations with rough algorithms to follow for each of the steps. It is meticulously filled with citation and rife with references to materials for additional study. It is an excellent resource for this inquiry. A good companion for it is Singh's "The Code Book".


Should I use self generated or predefined RFC 7919 DH groups?

Well, it's one less thing for the server to get wrong; I'll be giving my answer in the context of TLS 1.2 (as that was the context Mozilla assumed); remember, in TLS 1.2, it is the server that proposes the group, and Mozilla makes clients.

A "randomly generated group"; there are a number of ways of generating such a group, and they vary both in complexity, and (less obviously) the security.  Depending on the algorithm, you could generate a random prime, a "DSA prime"[1], a "Lim-Lee prime" [2], or a safe prime [3]; I have arranged the types of primes in order of both increasing security and increasing cost to generate.

The group includes the generator - how is that selected?  Ideally, we want to select a generator with a large prime suborder; does the server do that?

When you use the group, will you ever reuse the private exponent?  If you do, well, DSA primes can be weak in that scenario.

So, depending on the algorithm the server uses, the group has variable security characteristics; worse yet, the TLS 1.2 protocol does not give the client enough information to vet the proposed group (it can determine whether the server proposed a safe-prime, but since TLS 1.2 doesn't mandate safe-primes, there's little it can do with that information); in particular, it cannot determine the order of the proposed generator.
Hence, if Mozzila supported  server-generated groups, they'd be trusting that random servers did this rather subtle process correctly (without any way for them to verify it).  In contrast, the 7919 groups are known to be correctly generated, so that's one less  thing they need to depend on.
And, if you're worried about someone computing a factor base, well, I recommend you switch to ECC groups.
Also, I should list things which were likely not a part of the Mozilla decision:

The possibility that the server could accidentally select an SNFS-friendly group, that is, a group where the Special Number Field Sieve algorithm was applicable (which would allow computation of discrete logs considerably faster than the standard GNFS (aka NFS) algorithm can).  However, the probability that a SNFS-friendly group is selected is sufficiently tiny that, in practice, we don't need to worry about it.

The possibility that a malicious server could generate an "easy to solve" group.  However, there are lots of other ways a malicious server could foil security (for example, by selecting the private exponent in a guessable way, or just publishing the symmetric encryption keys); we need to assume that the server is honest (and so we need to protect only against accidental errors).

[1]: DSA prime is my terminology of a prime of the form $kq+1$, for $q$ a prime of perhaps 256 bits (and $k$ being an arbitrary even integer of the appropriate size).  The point of this is that it generates a group with a subgroup of a known size, and are essentially as cheap to generate as a random prime.
[2]: A Lim-Lee prime is a prime of the form $2qr+1$, for $q, r$ both primes about the size of half of the full prime.  The point of this is that it gives you most of the security advantages of safe primes, and are much cheaper to generate.
[3]: A safe prime is a prime of the form $2q+1$, for prime $q$.  This is standard and common terminology (compared to the other two); since I did define the other two, I thought I'd define this as well.


How to generate successive stream-cipher keys?

I can see a number of problems with your suggestion to let the session key $sk_{n,c}$ for node $n$ and client $c$ be $sk_{n,c} = h^{n+1}(masterkey_c)$, where $masterkey_c$ is what you refer to as "token":

You should use different keys for encryption and integrity, and different keys for the client -> node direction and the node -> client direction, making four keys total for each node and client combination.
The keys are not independent. If an adversary is able to compromise a node $n$ and get the session keys of that node, then the sessions of each node $n+k$ with $k > 0$ will also be trivially compromised.
There is no easy way to negotiate a new $sk_{n,c}$ if the connection between client $c$ and node $n$ is dropped. The client will have to negotiate a new $masterkey_c$.

I presume you have already figured out a way to securely distribute $masterkey_c$ from the login server to the nodes. The question is exactly which security features you need. I presume the communication between the client and the node is two-way, and that your application is such that you both need protection from replay attacks and the ability to easily renegotiate the session key of any client and node pair without having to renegotiate the master key for the client.
To begin with, you need a key derivation function $KDF(keymaterial,label,nonce)$. If the only cryptographic primitives you have are the stream cipher and the hash, you will firstly have to implement HMAC since it will be used for the protocol later. Secondly, you could then construct the KDF as follows:
$KDF(keymaterial,label,nonce) = HMAC(keymaterial,label|nonce)$
where $|$ denotes concatenation.
Thirdly, you need an unpredictable pseudo random bit generator. Since the client is performing a Diffie-Hellman handshake with the login server, it must have one already. If the nodes don't have access to the same functions the login server has, they could get a random $seed$ sent to them by the login server and use the following:
$DRBG(seed,ctr) = KDF(seed,"drbg",I2OS(ctr)), ctr = ctr + 1$
client/node master key
Server side, the login server performs the following calculation and sends the result to the corresponding node. The client might perform the calculation immediately before connecting to a node. The keymaterial $masterkey_c$ is the output from the Diffie-Hellman handshake:
$masterkey_{c,n} = KDF(masterkey_c,"mast",I2OS(n))$
client/node handshake
Input: $masterkey_{c,n}$
Output: message counter c->n $Ctr_{c,n}$ message counter n->c $Ctr_{n,c}$, session keys $ek_{c,n}$, $ek_{n,c}$, $ak_{c,n}$, $ak_{n,c}$.
Note: For simplicity, I assume you are using a stateful stream cipher, and that the encryption keys $ek_{c,n}$ and $ek_{n,c}$ can be regarded as stream cipher states that get updated by each call to the encryption function $E(keystate,text)$.

Both the client and the node set both message counters to $0$.
The client generates a random nonce $nonce_c$ and sends it to the node.
The node generates a random nonce $nonce_n$ and sends it to the client.
Both calculate $ek_{c,n} = KDF(masterkey_{c,n},"ekcn",h(nonce_c)|h(nonce_n))$, $ek_{n,c} = KDF(masterkey_{c,n},"eknc",h(nonce_c)|h(nonce_n))$, $ak_{c,n} = KDF(masterkey_{c,n},"akcn",h(nonce_c)|h(nonce_n))$, $ak_{n,c} = KDF(masterkey_{c,n},"aknc",h(nonce_c)|h(nonce_n))$.
The client calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|E(ek_{c,n},"verify")), Ctr_{c,n} = Ctr_{c,n} + 1$ and sends it to the node. The node disconnects if it fails.
The node calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|E(ek_{n,c},"verify")), Ctr_{n,c} = Ctr_{n,c} + 1$ and sends it to the node. The client disconnects if it fails.

There should probably be some safety mechanism in the handshake protocol that prevents the client and the node to repeat it indefinitely in case of failure. For instance, they could attempt to complete it three times, before they give up and the client either marks that specific node as unreachable, or returns to the login server to negotiate a new $masterkey_c$. The client should only do the latter if it fails to complete the handshake with several nodes.
Bulk data transfer
Input: $pt$
Output: $ct|mac$
Client to node:

$ct = E(ek_{c,n},pt)$
$mac = HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$
$Ctr_{c,n} = Ctr_{c,n} + 1$

The client sends $ct|mac$ to the node, the node calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{c,n}$ and decrypts $ct$ otherwise.
Node to client:

$ct = E(ek_{n,c},pt)$
$mac = HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$
$Ctr_{n,c} = Ctr_{n,c} + 1$

The node sends $ct|mac$ to the client, the client calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{n,c}$ and decrypts $ct$ otherwise.
Hope this helps


Which categories of cipher are semantically secure under a chosen-plaintext attack?

Encryption using a block cypher such as AES by passing plaintext blocks directly to the encryption function is known as Electronic Code Book mode (ECB) and is not CPA secure as (as you say in your question) it is entirely deterministic and two identical plaintext blocks will result in two identical ciphertext blocks.

To prevent this an initialisation vector or nonce can be used in  combination with a cryptographic mode such as cipher block chaining or randomised counter mode which will prevent the encryption from being deterministic and allowing the comparison of ciphertexts.


How would I convert committed coordinates $x$ and $y$ to a commitment of the EC point without revealing the point (in Zero Knowledge) or vice versa?

It's quite useful that you included yuor actual goal in the question, to avoid the XY problem.

  My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash.

If we assume that pulic parameters are known by everyone, you only give the verifier a single piece of information: The hash-value of the public key. And here it is quite irrelevant what kind of public key is used - you need a ZK proof for a preimage under the according hash function.

I am not sure what you mean with "all associated functions like the Bitcoin Hash". But the goal here seems to be keeping the identity of the Bitcoin account secret, so I guess that additional information does not reveal the public key either.

  This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key.

Actually, this is probably wrong. The reason for this is, that knowledge of a preimage under a hash function does not guarantee that the preimage is actually a valid Bitcoin account. For that you would need a different ZK proof, in which the verifier actually needs the according public key.

In the setting of Bitcoins, I think your agoal is not achievable. What you actually would need is a proof for membership of a group, e.g. the group of owners of valid accounts, and I can imagine that being possible - if the system is designed that way. This would be similar to group signatures, etc. But without an according setup, I don't see any way to achieve your goal.

Regarding your idea with the commitments and the EC public key:

You have two Pedersen commitments $a = g^xh^{r_1}, b = g^yh^{r_2}$ and then $c = G^nH^{r_3}$, which is like a Pedersen commitment but not in a prime order group but an elliptic curve.

Now, regardless of what $x$ and $y$ actually are, $a$ and $b$ could potentially be any element of the group, because the Pedersen commitments are perfectly hiding. So maybe you can generate $G^nH^{r_3}$ somehow from $a$ and $b$, but that will definately reveal $n$ itself and it has actually no relation to $x$ or $y$.


Will varying plaintext compensate for a fixed initialisation vector?

I recommend that you prepend a random 16-byte prefix.  Prepending a random 16-byte prefix, before encrypting with your CFB mode, will be just as good as using a random IV. The argument is pretty similar to Using CBC with a fixed IV and a random first plaintext block.

If we use CFB with an all-zeros IV and a random 16-byte value prefixed to the message before encryption, as you suggested, we get a scheme that looks like this:

$C_0 = 0$

$C_1 = E_K(C_0) \oplus IV$

$C_2 = E_K(C_1) \oplus PAN$

where $E_K(0)$ is a constant and $IV$ is your random 16 byte value. Since a constant xor-ed with a random value is itself random, the above has the same properties as:

$C_1 = IV$

$C_2 = E_K(C_1) \oplus PAN$

which is the standard CFB construction (with a random IV) with different indices.

Strictly speaking, the 16-byte prefixes don't need to be random.  The above approach is probably secure as long as the 16-byte prefixes are all unique. If you pull 16 random bytes from a well-seeded crypto PRNG, they should all be unique. But I don't trust your other schemes to produce unique values.  Therefore, I don't recommend using any of your other approaches.

Note that while this technique of prepending a random prefix works for some modes, such as CBC or CFB, other modes, such as OFB or CTR are totally broken in such a scenario.


How do I demonstrate that a PRNG not designed for cryptography is not suitable for generating passwords?

There are two key things that a secure PRG should have that you probably won't have with Random in this case. A secure PRG should not allow someone with access to some of the output to learn more about any of the other output, and it should be securely seeded.

On the first point: If you're generating passwords that are supposed to be independently secure, you have to assume that the other passwords are going to be known to a malicious adversary at some point. (Perhaps the attacker is actually a user of your program and thus given these passwords directly.) If an attacker somehow learns a large number of passwords, it raises concern that he could derive (fully or partially) other passwords he should not know. I don't know much about Random's PRG in specific, but this is why an attack like one mentioned by Ilmari would be important.

On the second point: The seed space is pretty much guaranteed to be insecure. The default constructor for Random says:

  "The default seed value is derived from the system clock [...] different Random objects that are created in close succession by a call to the default constructor will have identical default seed values".

This implies that the seed is determined purely based on the timestamp.

However: Any PRG seeded only by a timestamp is insecure. There is a temptation to think that it's hard for an attacker to guess exactly what time a timestamp was generated, but this is not true. If the attacker has any idea about the time frame when the timestamp seed was created, it limits the range of seeds they need to attack (because they will only need to test timestamps from the interval of time that the seed was generated from). But modern timestamps on personal computers do not have a small enough resolution to provide a total space that is large enough to resist brute-force attacks.

For example, assume you can get a timestamp accurate to one microsecond (a thousandths of a millisecond). That's better than any modern PC (that I am aware of) will provide. That provides 1,000,000 possible timestamps per second, which yields 86,400,000,000 timestamps per day, which is roughly 37 bits of total space. This is not cryptographically secure and easily brute-forcible if the attacker knows a 24-hour time frame the seed was generated. Over the course of an entire year, the timestamp space is still only about 45 bits, which also not cryptographically secure. If the attacker merely knows the year the seed was generated for the PRG, they can still brute-force it.

The numbers are more bleak with a more realistic timestamp resolution of only 1,000 timestamps per second. (Ilmari's answer suggests C# may only be as accurate as a millisecond.) That yields a timestamp space of only about 35 bits per year. (For reference, I think my old laptop can attack that in less than two weeks.)

It gets worse: The constructor for Random that takes a user argument as the seed only takes a 32-bit integer. This prevents you from possibly generating your own superior seed and using that, because you can only provide 32 bits of a seed. It also implies that the internal seed is limited to 32 bits for the default constructor case. 32 bits is not cryptographically secure, and would allow the attacker to brute-force the seed regardless of whether he knows the original time it came from.

In contrast, the secure PRG provided by C# should resist attacks using known output and should consult a good entropy source (it may be a wrapper to the same source as CryptGenRandom) for the seed.

So ignoring the cryptographic strength of the actual PRG implemented in class Random, I would say that it is insecure based on it's seeding alone. The default seed is too predictable and is not large enough.


with RSA encryption, how do I find the md5sum of the private key from the public key?

You cannot get a hash over the entire private key if you've just got $n$ and $e$. You can however create a hash over the modulus $n$. This is sometimes used as identifier for keys within a key pair, e.g. in PKCS#11. Usually SHA-1 is used however, not MD5.

The modulus is unique for RSA key pairs and links the public key and private key together.

md5sum is a GNU utility that performs MD5, it's not an algorithm in itself.


Server authentication in TLS 1.2 with static DH

Yes -- which is the same as RSA, because there the server proves it was able to decrypt the premaster secret (with the private key) only by getting the correct master secret, and working keys, and thus Finished. (All of these are the same for 1.1 and 1.0, and SSL3.)


Interpretation of (NIST) Non Overlapping Template Matching Test

First, Fisher's method is a way to combine several independent statistical tests with known distributions under the null hypothesis into a single statistical test with a known distribution under the null hypothesis.  If you would have raised an alarm for certain outcomes of the individual statistical tests with a known false alarm rate, then you can use the same criteria to raise an alarm for the composite test with a known false alarm rate.

Another way to look at this is: Fisher's method is a way to combine several independent d20 rolls into a single d20 roll, so that if you're given a black box that prints d20 outcomes, you can't tell whether a gremlin inside is doing several statistical tests and applying Fisher's method to them and rounding the result, or just rolling a d20.

If you would have raised an alarm when one of the statistical d20 tests rolled a 1 for the standard false alarm rate of 0.05, then you can raise an alarm when the Fisher composite statistical d20 rolls a 1 for the standard false alarm rate of 0.05.
Another way to look at this is:

With one statistical test, you lay out the possible test outcomes ($p$-values) uniformly on a line segment from $[0,1]$ and raise an alarm for any data that gives a $p$-value in $[0, 0.05]$.
With two statistical tests, you have a grid of outcomes on the unit square $[0,1] \times [0,1]$.  On what subspace of the unit square do you raise an alarm?

Fisher's method is a particular choice of which subspace of the unit square raises alarms.  There's some good illustrations of this—and comparisons to an alternative method of combining $p$-values—in the answers to a question about Fisher's method on stats.se.

There are other methods too for combining a collection of $n$ values $\{p_i\}_{i=1}^n$ into a single test statistic with a known distribution:

The arithmetic mean $\sum_i p_i/n$, as discussed in the stats.se answers, and known as Edgington's method.
The root-mean-square, $\sqrt{\sum_i p_i^2/n}$.
The geometric mean $\prod_i {p_i}^{1/n}$, which turns out to be tantamount to Fisher's method—just take the log.
Pearson's complementary geometric mean, $1 - \prod_i (1 - p_i)^{1/n}$.
The minimum $\min_i p_i$.
$p_1$, ignoring $p_2, p_3, \dots, p_n$ altogether.

Why should you prefer one of these over the others?  They all give rise to statistical tests that have any prescribed false alarm rate you want, so they must all be good, right?  Well, there's an elephant in the room.

Why raise an alarm when you roll a 1, rather than, say, a 7, on your d20—i.e., why do we care about $p < 0.05$?  What's really interesting is the alternative hypotheses.  The null hypothesis is that the device is working correctly as intended (and perhaps that working correctly means a perfect uniform distribution).  But the test is valuable insofar as it raises alarms at a substantially higher rate for plausible deviations from the null hypothesis—for instance, a significantly higher number of one bits than zero bits, which can happen in samples under the null hypothesis but only with low probability.  What plausible deviations might there be?

Study the physics or engineering of the system—don't just discard them as waste byproducts of the process that led you to a good NIST test result.

What do you know about the physics that might let you predict the result better than flipping a coin?
What manufacturing flaws and failure modes could the engineered system have that might change the distribution?

Many of these deviations or failure modes will not be detected by generic statistical tests.  As an extreme case, if your device chooses $k$ uniformly at random and produces $\operatorname{AES}_k(0) \mathbin\| \operatorname{AES}_k(1) \mathbin\| \operatorname{AES}_k(2) \mathbin\| \cdots$, except when it's broken and always chooses $k = 0$, generic statistical tests will never detect that broken case.

What matters for security is showing that the smartest, best-funded physicists in the world can't do better than a certain advantage at predicting what the outcome is, and that if the device fails in some way then you will detect that failure and stop relying on it.

The $p$-values of NIST statistical tests on samples you took during development?  These are more like the waste byproducts of a process that led you to a good hardware RNG.


Parity alone is a hard-core predicate of a oneway function, with this example given in the wiki:

With $f$ a oneway function, define $g(x,r) = (f(x),r)$ with $|x|=|r|$. Clearly $g$ is oneway, too, and it's trivial to build an adversary for $f$ from an adversary for $g$ and vice versa. However, $g$ has a hard-core predicate:

$$b(x,r) := <x,r> = \bigoplus_j x_j r_j$$

If we fix $r$ as the all-$1$ input, we get exactly the parity function.

In a similar context in this question the answer of Thomas Pornin has an example where the parity of the input to a oneway trapdoor function is is used as a hardcore predicate.

Now, the difference here is that you have a PRG, with a different definition than oneway functions, but my intuition would be that this is actually a secure PRG (regardless of the input parity) - since one of the standard way to construct a PRG is based on using hardcore predicates. And in the input domain you just fix one bit of the input by calculating the last bit as parity of the others, that should not break the PRG definition.

Edit, here's a sketch for the security proof:

Let's assume you have a distinguisher for $G'$, and we want to build a distinguisher for $G$. We get a challenge $x$ of length $l(n)$, which is either $G(s)$ or a randomly chosen number (from the uniform distribution). Now, we run the distinguisher for $G'$ on the $x|1$ and on $x|0$. Running a poly time algorithm twice is still a poly time algorithm. Loosely speaking, a distinguisher guesses, whether a challenge is in the image of the PRG or not and then returns this guess - but of course any value in the image could also have been the randomly chosen number.

So if at least one of our distinguishers returns "this was generated by the PRG", then we also answer this - if $x|0$ is in the range of the function $G'$, then $x|1$ could be in the range as well or it might not be. For an actual proof you would want to estimate the actual advantages.


How does the TLS Client Hello message choose the TLS version?

TLS 1.3 record layer is shown because the ClientHello contains TLS 1.3 as supported version. This can be seen at the bottom of the following image. See also TLS record layer and Handshake protocol at ask.wireshark.org.


Is it safe to reuse the same random session number r in the Guillou-Quisquarter protocol?

Is this safe?

No, it is not.  Here is how it would be easy to recover $A$:

The prover generates $r$ and publishes $T$, and the verifier selects an arbitrary challenge $d$.  The prover responds with $T = A^d \cdot r$
The prover generates the same $r$ and publishes the same $T$.  The verifier selects the next $d' = d+1$ as his challenge, and the prover responds with $T' = A^{d'} \cdot r$

The verifier can then compute $T' \cdot T^{-1} = (A^{d+1} \cdot r) / (A^d \cdot r) = A$, thus recovering the secret.

  I was not able to find indications in the literature about it and r is never defined as a nonce but I am afraid this could leak the provers secret key A.

Actually, it's not a nonce; calling something a nonce implies that the only requirement it has is that values never repeat,  In this case, you can devise ways to exploit related $r$'s as well; for example, if it's a simple incrementing pattern, that is, $r' = r+1$, then the attacker just selects $d = d' = 1$.  There might be nonrandom update patterns that are safe, but why risk it?

In general, using nonrandom challenges (either repeating or related) within a zero knowledge protocol does leak the secret.


How does one verify a GPG/PGP key revocation?

How does one verify a key revocation?

As Jon Callas already stated: you simply don’t.

In case a different wording helps, here’s a quote related to the exact same question… https://lists.gnupg.org/pipermail/gnupg-users/2014-February/049100.html

  …

    I revoked my key and on the public key server it says: "* KEY REVOKED * [not verified]" Why does it say that revocation is not verified?

  That probably refers to the point that the keyservers don't do crypto checks. It means: There is a packet which looks like a key revocation but it could be forged. If an OpenPGP application  downloads the key from the server then it does a signature check.

  …


Is the security of an HMAC equally important as the security of the cipher itself?

Based on your comment:

  Correct... But it looks like many HMAC systems basically end up including a hash of the plaintext+key alongside the ciphertext. So it seems like cracking that hash would effectively compromise the entire encryption, no?

you may have a misunderstanding of how HMAC is used as part of a cryptosystem, which is reinforced by the opening line of the question.

The HMAC input is not the plaintext+key, but rather just the ciphertext, or just the plaintext. A separate key is used as part of the HMAC process to change the initial value of the hash function to a secret. The input is then hashed with the secret IV, and then the output is hashed again with a different secret IV. That key that generates the secret IVs is not the same as the key used by the cipher.

Current best practice is to MAC the ciphertext, and not even attempt decryption if the authentication fails. If the plaintext is MAC'd, decryption is required first. When HMAC is used, if the plaintext was MAC'd, an attacker can corrupt the MAC or ciphertext and resend multiple times, forcing the recipient to decrypt the message every time. If the cipher was vulnerable to a timing attack, this method could be used to recover cipher key material. The same security against timing attacks must be provided to the hash function, since a ciphertext MAC failure would not even touch the encryption key, but could allow recovery of the MAC key. In this respect, the security of HMAC is as important as the security of the cipher. This is also one of the reasons the MAC key and cipher key are different, so recovery of one would not compromise the other.

One of the other reasons to MAC the ciphertext when using HMAC, is that processing an identical plaintext results in an identical MAC, whereas the same plaintext results in a different ciphertext when encrypted correctly with most modes, which is an important required property for many applications.

Because of the way HMAC uses the hash, it is more robust than the hash used. The offline attack that would compromise HMAC is a preimage attack, which would recover the original message, specifically the part that generates the secret IVs. Because HMAC hashes twice, this is extremely difficult even with a broken hash like MD5.

Alex's answer also brings up an important point. Even after key rotation, a broken HMAC (key recovery) does not recover the message, and only allows forging a MAC using that key, which is now no longer used. The MAC key must be secure for the life of that key, which is generally short enough that a brute force attack to recover it is all but infeasible. The key should also be large enough for the same reason.


Comparison among algorithm based on key length

Usually we only consider those keys, we can actually use. There is no restriction about the bits in a symmetric key, you can use all of them. For asymmetric encryption schemes, both keys need to fulfill some constraints to actually work. For example:

In RSA, $e$ has to be chosen coprime to $\phi(n)$, and you need $ed=1 $ mod $\phi(n)$0. What does it mean? Yes, there are certain values of $e$ (and $d$) which do not work.

edit: Even numbers never work, because $\phi(n)= (p-1)(q-1)$ is always divisible by 4. Other than that, the fastest way is to pick a random odd number for $e$, and check if it is coprime to $\phi(n)$.

What the reason is, that we can not blindly compare bit sizes of keys, is that attacks on symmetric and asymmetric encryption schemes are fundamentally different. It is a bit like comparing apples and oranges. So a 200 bit symmetric key is just something different than a 200 bit asymmetric key.

However, there are heuristics (not proven) to compare the strengths of these keys. For example NIST provides information about that here.

A very good read is Universal security; from bits and mips to pools, lakes -- and beyond, which tries to accommodate the the irritating scale of bits in a humorous way.


eavesdropping on sha 256 consist of two entries one is public is secure

It is proposed to use $\operatorname{SHA-256}(\mathsf{horodate}\|\mathsf{password})$ as a key of AES or/and Initial Value (the lack of unique IV is stated as the motivating context).

That's a very poor idea. If the password is worth its name and is low-entropy (as most passwords are, and increasingly so since the bar for low-entropy is raising per some variant of Moore's law), then indeed the attacker can retrieve the original value of the password from the hash and time-stamp.

A general problem is ignoring the

First rule of modern crypto: don't roll your own

Ignoring that rule is a tried and tested recipe for disaster (and making a question rejected as off-topic on CSE, but I won't raise that further).

More specifically, it is ignored the

First rule of passwords: they must undergo entropy streching

Not knowing why entropy stretching is needed when turning password into key, that irreversible entropy stretching (going under the name of Password-Based Key Derivation Function) is needed for password storage, and that the first hit for PBKDF is outdated, is a sure indication that one should either learn, or leave the problem at hand to someone more knowledgeable, including for applying the first rule of crypto (commercial products that get the first rule of passwords wrong are legion, and recognizing the good from the ugly requires understanding of the issues and the products).

Even more specifically, if it is performed as planned, it will be easy to mount a password search. Yes, that thing in the movies, except one can find characters one after the other only in the most strikingly incompetent implementations of the first rule of passwords (like those vulnerable to timing attack).

Here, the regular breed of brute force password search will be needed: plausible passwords are tried (roughly from most probable to least, possibly in parallel), and for each

the disastrous substitute of a PBKDF $\operatorname{SHA-256}(\mathsf{horodate}\|\mathsf{password})$ is applied ($\mathsf{horodate}$ is assumed known, and since regular decryption needs it, that's reasonable);
decryption of some ciphertext(s) is attempted with that; if a direct error occurs (like incorrect padding), that password is rejected;
the resulting plaintext is submitted to more plausibility test(s); the most commons are:

starting with a magic number appropriate to the context;
being sharply rejected as uniformly random octets by a chi-squared test.

That will tell when the attack has reached the right password, which will then allow decryption of all ciphertext encrypted under that password (and perhaps access to unrelated online accounts of the person using that password).

There are other lesser issues in the proposed solution:

Usually, the IVs are in clear at start of ciphertext; that alleviates the need for steps 2 and 3 in brute force password search.
If AES-256 is used, SHA-256 is not wide enough to derive key and IV; using a fixed IV with a message-unique key dents the theoretical security.
There is no mentioned effort to insure message integrity, which often is more important than confidentiality; see first rule of modern crypto.

Note: this answer applies to the original question, without its new flavor of Certificate-Less Authenticated Encryption.


This sounds like the scenario of identity-based encryption, or IBE.

In IBE, the ‘root CA’, called the private key generator or PKG in this scenario, doesn't handle encrypting or decrypting messages directly, but does have to furnish Bob and Carol with their respective private keys.  As long as Alice knows the names Bob and Carol, and the long-term master public key of the PKG, Alice can send encrypted messages to Bob and Carol—even offline, without contact with the PKG.  Then whoever can convince the PKG that they are named Bob or Carol will get a private key to decrypt those messages.

Of course, the PKG is a central point of failure: anyone who can compromise the PKG can decrypt all messages.


The "openssl genrsa" command only generates a private key?

How can the second command generate a public key, given ONLY the
  private key?

It will probably use the public key encoded in the private key datastructure. As per RFC 3447 / PKCS1 (v2.1) the RSAPrivateKey should contain:

RSAPrivateKey ::= SEQUENCE {
          version           Version,
          modulus           INTEGER,  -- n
          publicExponent    INTEGER,  -- e
          privateExponent   INTEGER,  -- d
          prime1            INTEGER,  -- p
          prime2            INTEGER,  -- q
          exponent1         INTEGER,  -- d mod (p-1)
          exponent2         INTEGER,  -- d mod (q-1)
          coefficient       INTEGER,  -- (inverse of q) mod p
          otherPrimeInfos   OtherPrimeInfos OPTIONAL
      }

which contains a public key $(n,e)$ as well as the private key $(n,d)$ and some other useful information.

  Isn't the whole value of cryptography depends on the impossibility of
  generating one key from another in a key pair?

No. Generating the public key from the private key is fine. Generating the private key from the public key is not. And in fact with RSA, it can be hard to recover the public key from the private key, if you only store the private exponent $d$ and the public modulus $n$ (which is the bare minimum needed for private-key operations) and if you pick the public exponent $e$ not to be the standard $65537=2^{16}+1$ but some random large integer.

On the other hand, for DSA and ECDSA, the private key is only an integer $d$ and the public key is $g^d$ for some fixed $g$ which is needed for private key operations. So recovering the public key from the private key is always and inevitably possible with (EC)DSA.


PRF that can be distinguished after $k$ queries?

A $k$-wise independent hash family has the property that the joint distribution of $h(x_1), h(x_2), \ldots, h(x_k)$ is uniform when $h$ is chosen uniformly from the family (and $x_i$'s are distinct). Such families exist unconditionally (for fixed $k$), are efficient, and satisfy the condition you give.

The simplest example of a 1-universal function is $F(k,x) = x \oplus k$. Clearly the output of $F$ on one point is uniform (it's a one-time pad) but with two queries $F$ can be easily distinguished from a random function.


Tell where messages begin and end in a series of ciphertext blocks?

With block ciphers, I understand that the plaintext is first broken down into the right-sized blocks, padded, and then encrypted into the same number of cipher blocks.

Actually, it's a bit more complex than that.  There are some block cipher modes (for example, CTR, CFB) that don't require any padding.  On the other hand, even if the encryption mode doesn't require padding, we usually do want to provide some integrity protection to the ciphertext (so that if someone modifies the ciphertext, we can determine that); we usually do this by dividing the message up, and generating a Message Authenticated Code for each segment (or using a Authenticating Encryption Cipher, which effectively does the same thing); this would also cause us to treat the messsage as something other than a continuous stream (even if, to the application, it might be).

  does this mean that (after decryption) the receiver would have to parse each block looking for the padding

Actually, the receiver wouldn't be able to determine if a particular block is the last block in a message.  That's because we generally allow all blocks but the last to take on any value (so that we can encrypt 128 bits per block with AES); this means that the decrypted plaintext block might take on any value; there's no way that the decryptor would be able to distinguish 'padded last block' vs 'just more data'.

Instead, we generally rely on a noncryptographic higher-level protocol to divide distinct messages.  The use of a higher level protocol means that an attacker can deduce the size of the messages (and the timing); however the cryptographical piece ensures that that's the only thing that an attacker can learn).

One example which might be illuminating is TLS; that breaks up the stream of plaintext into 'records', and individually encrypts each record.  Before each record, it includes (in plaintext) the length of the encrypted record.  Hence, the decryptor knows up front where the last encrypted block is.

This isn't the only way to mark where the start of the next record is; another way is the IPsec approach.  With IPsec, each ciphertext is placed in its own packet; hence where the ciphertext ends is easy (it's at the end of the packet).


How to specify last $t$ bits are only sent when a signature is sent?

In general, this depends entirely on the signature scheme in question; usually however, the answer is that truncation is generally not possible.

For very short signatures, depending on your risk appetite for other kinds of somewhat novel public-key cryptography, you may find success with pairing-based BLS signatures or multivariate cryptography (GeMSS comes to mind).

For Schnorr signatures in particular, you generally either send:

the result of applying the group operation with the nonce $r$, $x = \alpha^r$ (or $[r]G$ in the elliptic curve case) and the scalar $y$, or
the tuple of the hash value $e=h(\overline{x}, m)$ and the scalar $y$.

EdDSA, a relative of Schnorr signatures, sends $([r]G, y)$ and thus doesn't lend itself to shortening unless you change your implementation to send $(e, y)$ instead.

If you send $(e, y)$, you can essentially truncate $e$ to an arbitrary extent in your scheme, but the security of the scheme also sinks by that much. Schnorr's original paper proposed using a $t$-bit hash for a $2t$-bit group order. The academic community still isn't sure whether this is a good idea, however, see e. g. Jeremiah Blocki and Seunghoon Lee. On the Multi-User Security of Short Schnorr Signatures, 2019 and Daniel R. L. Brown. Short Schnorr signatures require a hash function with more than just random-prefix resistance, 2015 and their references.


A 3 minute running time on my laptop (running Java) already gave me a bit string where 99 bits are identical. It might be that you're overthinking this.

This sounds like a classical proof of work that you're supposed to do. As it is unlikely that there are any shortcuts I guess you'll have to break it brute-force. And as is it a gaming site, the faster GPU probably wins.

MD5 still has pre-image resistance of over $2^{123}$, with the specific attack mentioned here. You won't get far with just finding collisions as the pre-image seems to be (unknown) and given.

Just computing on a laptop gives, comparing with a hash of all zero's:

100 : 00000000000000000000000625b4aa69 -> 0740a0a42a0074920018000008308212

only just over 26,000,000,000 (16 billion for the US, 16 milliard for the rest of us) hashes required; the hexadecimal representation of the value as 16 byte integer is used as input.

Took some time but nothing major, unoptimized, single threaded Java code, running on a downclocked i7 laptop. On a fast machine with semi-optimized, multi-threaded code expect a 16 times improvement minimum.


Possible problems in using a hash algorithm to construct a stream cipher

It would be good to define what you require for the cipher to be secure before trying to determine it's security properties. Take the example of CPA security - Katz and Lindell (Introduction to Modern Cryptography 2nd ed.) state that a symmetric scheme has indistinguishable multiple encryptions under chosen plaintext attack (i.e. the scheme is CPA secure for multi-encryptions) if the following relation holds in the so called "Left - Right Oracle" Game:

$ \textbf{Pr}[\textbf{PrivK}_{\mathcal{A},\pi}^{LR-cpa}(n) = 1] \leq 1/2 +  \textbf{negl(n)}$

where $\textbf{K}$ is an encryption key of length $n$ and $\textbf{negl}(n)$ is a "negligible'' function in $n$ (this relation is a re-statement of definition 3.23 in the above text by Katz and Lindell)

Given the above definition of CPA security, it can be shown that CTR modes are CPA secure so long as the underlying "block cipher" is a pseudo-random function and you are dealing with a "q-query" adversary, i.e., you are limiting the number of oracle queries by the adversary to $q$ such that $q^{2}<< 2^{n}$ where $n$ is the size of the block (cf. so called "CTR Mode Theorem" over here:
http://spark-university.s3.amazonaws.com/stanford-crypto/slides/04.5-using-block-annotated.pdf)

If your underlying "block" is a PRF and you have constructed a proper randomized counter mode, then your scheme would be "CPA secure" by the results stated above.

If you require CCA security, on the other hand, your scheme would need to be non-malleable in the manner of authenticated encryption schemes. So the answer to your question on security depends partly on what you require or what you wish to achieve from a security definition standpoint.


Check if two ed25519 points are equivalent

Short answer:

The affine coordinates are (X/Z, Y/Z).

So, check that Y1*(1/Z1) ≡ Y2*(1/Z2) and that the signs of X1*Z1 and X2*Z2 are the same.

Z being 0 represents the point at infinity.

Slightly longer answer:

Think about (X, Y, Z) as a fraction representation of (X', Y') with X' = X/Z and Y' = Y/Z. T is just X*Y and is not relevant here.

What you mean by "unproject" is going from a fraction to a scalar. Once this is done, you get something equivalent, but the denominator is lost.

You can go back to a fraction representation by setting the denominator to 1. This is what happens when you go from an affine representation to a projective or extended one.

(X, Y, Z) may look different after a round trip, but this is the same set of affine coordinates, just with a different denominator Z.


EDIT: I think what I do is provide a little more than a hint so don't read further if that is an issue.

   This problem is very much like the NSL protocol in that it allows an intermediary due to neither party declaring their own identity:

That is:

   A -> E : { <[A, {K}pk(E)]> }pk(E) }  E -> B : { <[A, {K}pk(B)]> }pk(B) }  B -> E : { <[B, {K}pk(A)]> }pk(A) }  E -> A the above

Resulting in:

   Now B believes it has a shared channel with A but E is involved.  You can even simplify and omit A entirely since its existence was never proven to party B:

Alternatively:

   E -> B : { <[A, {K}pk(B)]> }pk(B) } B -> anyone : { <[B, {K}pk(A)]>}pk(A) }

and

   Now 'B' presumably believes key $K$ is shared with party $A$ when in fact party $E$ holds a copy.


Why does encrypting the Diffie-Hellman value with the other side’s public key prevent man-in-the middle?

It's because, Eve (attacker) can't break the encrypted data since Eve doesn't have other side's private key. Only by using other side's private key, the encrypted data can be decrypted.

And yes, this is general technique for preventing Man-In-the-Middle attack using asymmetric keys. Diffie-Hellman is Symmetric Key Exchange Protocol, not encryption mechanism.

First two numbers are generated g and p where p is prime.

One side:

$R_1 = g^x \bmod p$ where $x$ is randomly chosen

Send $R_1$ to other side, Receive $R_2$

Calculate key as $K = {R_2}^x \bmod p$

Other side:

$R_2 = g^y \bmod p$ where $y$ is randomly chosen

Send $R_2$ to other side, Receive $R_1$

Calculate key as $K = {R_1}^y \bmod p$

Also, Diffie-Hellman doesn't prevent Man-In-The-Middle; it's one of Diffie-Hellman's weakness and it's vulnerable to it.


What is the exact definition of $x^u\bmod k$?

In RSA and most cryptographic contexts, $x^u\bmod k$ is written with:

$k$ in the set $\Bbb N^*$ of strictly positive integers. $k$ is the modulus (plural moduli)
$u$ in the set $\Bbb Z$ of signed integers. $u$ is the exponent.
$x$ in the set $\Bbb Z$ of signed integers, or in the set $\Bbb Z_k$ of integers modulo $k$. The later is a special case of the former, since we'll assimilate $\Bbb Z_k$ to the non-negative integers less than $k$.

$x^u\bmod k$ can be spoken « $x$ raised to the power $u$ [small pause] modulo $k$ », and becomes « $x$ to the $u$ mod $k$ », or « $x$ to $u$ » under time constraints.
For the full definition, skip to $\eqref{fgr4}$. For a gentle introduction, we'll first study the
definition with exponent $u>0$
When $u>0$, the notation $x^u\bmod k$ just stands for $\left(x^u\right)\bmod k$, where $x^u=z$ and $z\bmod k=y$ have their usual definition:

$x^u$ is $\underbrace{x\cdot x\cdots x\cdot x}_{u\text{ term(s)}}\,$ where $\cdot$ is integer multiplication. More formally
$$x^u\,\underset{\text{def}}=\begin{cases}
x&\text{if}\,u=1\\
x\cdot\left(x^{\left(u-1\right)}\right)&\text{if}\,u>1
\end{cases}\tag1\label{fgr1}$$
Note: the parentheses would usually be omitted¹.
$z\bmod k$ is defined to be $y$ such that $0\le y<k$ and $z-y$ is a multiple of $k$. Equivalently:

$z\bmod k$ is obtained from $z$ by subtracting or adding $k$ as many times as necessary for the result to be in range $[0,k)$. More formally:
$$z\bmod k\,\underset{\text{def}}=\begin{cases}
z&\text{if}\,0\le z<k\\
\left(z-k\right)\bmod k&\text{if}\,z\ge k\\
\left(z+k\right)\bmod k&\text{if}\,z<0
\end{cases}\tag2\label{fgr2}$$
If $z\ge 0$, then $z\bmod k$ is the remainder in the Euclidean division of $z$ by $k$;
otherwise, $z\bmod k$ is $k-1-\left(\left(-z-1\right)\bmod k\right)$.
More formally, noting $\ell$ for the quotient (with $\ell=\left\lfloor z/k\right\rfloor$ per the mathematical definition of that):
$$z\bmod k\,\underset{\text{def}}=y\in\Bbb Z_k\,\text{ such that }\,\exists\ell\in\Bbb Z\,\text{ such that }\,y=z-\ell\cdot k\tag3\label{fgr3}$$

Example: We compute $3^5\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=5$, $k=35$. We compute $x^u=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the Euclidean division of $z=243$ by $k=35$, yielding quotient $\ell=6$ and remainder $y=243-6\cdot35=33$. Thus $3^5\bmod35=33$.
In Python, the above is obtained as (3**5)%35 or pow(3,5)%35 or pow(3,5,35). The three forms internally use exponentiation by squaring, but only the later uses modular reduction of intermediary results. Using both techniques is essential for even mildly efficient modular exponentiation in RSA, e.g. encryption per $C=M^e\bmod N$ with common parameters like 2048-bit $N$ and $e=65537$.
Starting with Python 3.8, pow also handles all the following.

Extensions to any integer exponent $u$
The full² definition of $x^u\bmod k$ in cryptography is:
$$\begin{array}{l}
x^u\bmod k\underset{\text{def}}=\\\\
\begin{cases}
y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y=x^u-\ell\cdot k&\text{if }u>0\\
y\in\Bbb Z_k,\;\exists\ell\in\Bbb Z,\;y\cdot x^{-u}+\ell\cdot k=1&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)=1\\
\text{undefined}&\text{if }u<0,\;k>1\text{ and }\gcd(x,k)\ne1\\
1&\text{if }u=0,\;k>1\\
0&\text{if }k=1\\
\end{cases}\end{array}\tag4\label{fgr4}$$
In this, $\Bbb Z_k$ stands for the non-negative integers less than $k$, or equivalently the integers modulo $k$. “$\text{such that}$” is replaced by “$,\;$” which is common practice (suppressing it is also accepted).
This definition extends $\eqref{fgr3}$ to the multiplicative group of integers modulo $k$, that is the subset $\Bbb Z_k^*$ of $\Bbb Z_k$ that forms a group under multiplication modulo $k$. For negative $u$, the notation $x^{-u}\bmod k$ is now defined as the multiplicative inverse of $x^u$ in $\Bbb Z_k^*$.
Definition $\eqref{fgr4}$ maximizes the domain where it holds the property:
$$\begin{array}{l}
\text{if }\,x^u\bmod k\,\text{ and }\,x^v\bmod k\,\text{ are both defined, then}\\
\quad\bigl(\left(x^u\bmod k\right)\cdot\left(x^v\bmod k\right)\bigr)\bmod k\;=\;x^{u+v}\bmod k
\end{array}\tag5\label{fgr5}$$
When $u<0$ and $k>1$, the equation $y\cdot x^{-u}+\ell\cdot k=1$ follows from extending definition $\eqref{fgr3}$ with $y=x^u\bmod k$ constrained to be an integer, while insuring property $\eqref{fgr5}$. With $x^{-u}$ replaced by $z$, that becomes a Bézout identity $y\cdot z+\ell\cdot k=1$. The requirement $\gcd(x,k)=1$ pops up, as well that $y$ and $\ell$ can³ be computed per the extended Euclidean algorithm (that can yield $y<0$; we need to bring it back to positive by reducing it modulo $k$, or equivalently adding $k$).
Example: We compute $3^{-5}\bmod35$ directly from this definition. That's $x^u\bmod k$ with $x=3$, $u=-5$, $k=35$. We compute $x^{-u}=3^5=3\cdot3\cdot3\cdot3\cdot3=243$. We perform the extended Euclidean algorithm to solve for $y$ (and $\ell$ that we don't need) the Bézout identity $y\cdot 243+\ell\cdot 35=1$. Using the pseudocode of this Try It Online!, the steps are
$$\begin{array}{rrrrrrr|rrr}
r&r'&s&s'&t&t'&q&z\cdot s+k\cdot t&=&r\\
\hline
243&35&1&0&0&1&6&243\cdot1+35\cdot0&=&243\\
35&33&0&1&1&-6&1&243\cdot0+35\cdot1&=&35\\
33&2&1&-1&-6&7&16&243\cdot1+35\cdot(-6)&=&33\\
2&1&-1&17&7&-118&2&243\cdot(-1)+35\cdot7&=&2\\
1&0&17&-35&-118&243&&243\cdot17+35\cdot(-118)&=&1
\end{array}$$
and that yields $y=17$, $\ell=-118$. Thus $3^{-5}\bmod35=17$.
The definition $\eqref{fgr4}$ is such that
$$\begin{array}{l}
\text{if any two among the three $\;x^u\bmod k$, $\;\;x^v\bmod k$, $\;\;x^{u\cdot v}\bmod k$}\\
\text{are defined, then all three quantities are defined, and}\\
\quad\left(x^u\bmod k\right)^v\bmod k\;=\;x^{u\cdot v}\bmod k\;=\;\left(x^v\bmod k\right)^u\bmod k
\end{array}\tag6\label{fgr6}$$
Applied for a negative $w$ with positive $u=-w$ and $v=-1$, $\eqref{fgr6}$ allows computing $x^w\bmod k$ using modular exponentiation with a positive exponent, and (after or before that) a modular inversion, thus avoiding monstrously large input to the extended Euclidean algorithm, and using alternative algorithms.

The meaning of $\bmod$ [reference to Monty-Python intentional]
In some contexts including the definition of RSA, we need to distinguish two kinds of $\bmod$

An operator, yielding e.g. the remainder of Euclidean division when applied to two strictly positive integers. It is to be typeset using \bmod k in $\LaTeX$ / MathJax (see this, or this for more). In this case, that operator's result, when and if defined, is always a non-negative integer less than the modulus. And, depending on context, that operator has

two arguments like in $7\bmod5$, or in $7\bmod5\,=\,2$, or in $2\,=\,7\bmod5$. The first is the integer $2$, the later two are two true statements.
three arguments like in $3^{-1}\bmod5$, or in $3^{-1}\bmod5\,=\,2$, or in $2\,=\,3^{-1}\bmod5$. The first is the integer $2$, the later two are two true statements.

The indication of modular equivalence (class) in what stands on its left. That is best typeset:

As \pmod k in $\LaTeX$ / MathJax, which shows as “$\pmod k$” with an opening parenthesis “$($” immediately before $\bmod$ and a closing parenthesis “$)$” after the modulus.
And⁴ with the sign $\equiv$ rather than $=$ anywhere on its left.
And with only the closing parenthesis on the right of the modulus.

Example of typographically and mathematically correct usages of modular equivalence:

Definition: $r\equiv s\bmod m\;\underset{\text{def}}\iff\;\exists\ell\in\Bbb Z,\,r=s+\ell\cdot m$
In any valid RSA public/private key, $e\cdot d\equiv1\pmod{\lambda(N)}$
It holds $7\equiv2 \pmod 5$ thus $2\equiv7 \pmod 5$
It holds $3^5\equiv243\equiv33 \pmod{35}$ thus $33\equiv3^5 \pmod{35}$
$\lambda(35)=12$ and $-5=7 \pmod{12}$, thus $3^{-5}\equiv3^7\equiv2187\equiv17 \pmod{35}$.
$7\pmod 5$ can be seen as the infinite set $\{\ldots,-8,-3,2,7,12,\ldots\}$.

Sometime a statement is false with the operator from, that would be true as a modular equivalence: $7=7\bmod5$ stands for $7\,=\,(7\bmod5)$ thus is false, when $7\equiv7 \pmod 5$ is true.
The distinction matters in RSA encryption, with ciphertext $C$ specified by $C=M^e\bmod N$ where $M$ represents the message. In this, $\bmod$ is an operator, thus implies $0\le C<N$, which is important. An encryption system only specified to output $C$ such that $C\equiv M^e\pmod N$ could output $C=M^e$ and be totally insecure, or leak some sensitive information by selectively producing $C=(M^e\bmod N)+N$.

What is the difference between $x^u=y\bmod k$ and $x^u\equiv y\bmod k$ ?

The cardinal way to read the correct $x^u=y\bmod k$ is as $x^u=(y\bmod k)$ with $\bmod$ an operator. Unambiguously, that implies $x^u\equiv y\pmod k$, that is $y-x^u$ is a multiple of $k$. Formally, $x^u=(y\bmod k)$ also implies $0\le x^u<k$. But it is not often that $0\le x^u<k$ is meant, thus I try to not use $x^u=y\bmod k$, and would use $x^u=(y\bmod k)$ only if $0\le x^u<k$ was intended.
I'm reading $x^u\equiv y\bmod k$ (using \bmod) as a slight $\TeX$po™ of $x^u \equiv y\mod k$ (using \mod, which adds spacing on the left to indicate that it is not an operator) or $x^u\equiv y\pmod k$ (using \pmod, which adds parentheses to more clearly indicate the same thing). Thus here $\bmod$ stands for modular equivalence. I avoid \mod when \pmod rather than \bmod is meant, because except in contexts like tex-SE or a JOC paper, 90% of the audience will not interpret the slight extra space correctly.

¹ Raising to a power is performed before multiplication (thus before addition), tough after any operation in the exponent. The exponent is on the right, and is typographically distinguishable by being higher and in smaller characters. If that's not feasible, it is often used ** or ^^ (or ^ when confusion with eXlusive-OR operator $\oplus$ is impossible), and parentheses.
² Sometime $x^u\bmod 1$ and/or $x^0\bmod k$ with $\gcd(x,k)\ne1$ are left undefined or unspecified, for simplicity and because they are seldom practically useful.
³ Since we do not need $\ell$, we can simplify the extended Euclidean algorithm by removing the two variables $t$ and $t'$. When performing the algorithm by hand, that has the drawback we can't check intermediary results. But we can still check $y\cdot z\bmod k=1$ in the end.
⁴ Sometime, this $\equiv$ becomes $=$, or the $($ immediately on the left of $\bmod$ vanishes [together owith the matching $)$ after the modulus]. But absent at least one of these indications, the meaning changes: we are back to the $\bmod$ operator.


Enhance security by combining bits of 4 different hashes

The main question about this topic is: Guarding against cryptanalytic breakthroughs: combining multiple hash functions. There you will find some better combiners for multiple hash functions. I would generally recommend against the extra complexity - a single good hash ought to be enough.

Now, regarding your way of combining them:

  Does this make sense? If yes, do I loose security (in general) by truncating each hash to 128 bit?

By truncating a hash to 128 bits you make brute force attacks against the hash easier and may also make other attacks easier. A 128-bit hash alone would not be secure, since a $2^{64}$ collision attack is within plausible estimates of strong attackers' (e.g. national security agencies') capabilities.

Some hash functions, e.g. SHA-2, explicitly state that you can truncate them and assume the lower resistance implied by the shorter output size. Others do not.

By concatenating four 128-bit hashes you are back to "secure against collision attacks" if at least two of them are 64-bit secure. (Preimage attacks are another matter. It depends on which notion of preimage resistance you consider, but if one of the hashes somehow leaked some bits of the input you could lose preimage resistance.)


As there is some minimal attempt in solving I will answer at least in part.

No 128! would be the number of permutations. But that is not what we are doing, we 128 is already the number of possibilities to combine 7 bits $2^7$ if you have 8 of these then you get: $128^8$ or alternatively bitwise $2^{56}$

yes

no, 26 letters. need $\log_2(26)$ bits or just over 4.7 bits per letter. Assuming compact representation and after rounding it 8 independent letters need 38 bits.

I'll leave something for you still.


Why do cryptographic hashing and symmetric encryption use different functions?

You are correct: The 'workhorses' or primitives of cryptography, hash functions and block ciphers, can be used in such a way that they accomplish each others tasks:  A hash function can be used to generate a key stream just as a stream cipher or block cipher in CTR mode (see e.g. Salsa20).  And a block cipher can be transformed into a hash function (e.g. a Davies–Meyer compression function inside the Merkle–Damgård construction).

So why use different functions?  Well, hash functions are not as versatile as block ciphers for the purpose of encryption - you can't do CBC mode with a hash function, for example.  And block ciphers are generally not as well suited to the task of hashing as a purpose built compression function - they tend to have smaller blocks and relatively slow key schedules (or key schedules which are not secure when the attacker can control all the inputs).  For efficiency's sake, it is easier to design a really strong and fast block cipher and a separate really strong and fast hash function than it is to design a single function which is really strong and fast in both capacities.

P.S. The hash function constructed from a block cipher you describe in your question is not cryptographically secure - you can find a collision merely by re-ordering the blocks of the message.


Is more ECDHE or RSA currently recommended?

It is not fully clear what you are talking about - "many websites warn us" is a bit too short on detail. But usually this topic comes up when talking about TLS (as used in HTTPS) and here comparing RSA and ECDHE  means to compare the different methods of key exchange offered by TLS. Note that key exchange is not encryption  - it is instead the method to determine the common key which is later used for encryption.

And yes, ECDHE is clearly the preferred key exchange since it provides forward secrecy which can greatly limit the impact of a successful attack. With forward secrecy an attacker cannot decrypt previously sniffed traffic while without forward secrecy this might be possible. For more details see What guarantees does perfect forward secrecy make with respect to compromise of a private key? and Wikipedia:Forward secrecy.


Symmetric versus asymmetric self encryption

called asymmetric self encryption

No, not really, you just made up that term.

  might seem an unusual choice in situations where a key exchange is not required

No it doesn't, although commonly a hybrid cryptography is used, especially for EC based cryptography.

  an attacker apparently needs both to have the public key and brute-force the passphrase to decrypt the data.

Of course not, the attacker requires the encrypted private key and a password to unwrap that key using password based encryption (PBE).

  Considering attacks on the asymmetric encryption, does hiding the public key increase the entropy required for a brute force attack? What information does the public key provide to the attacker?

Possibly, but the scheme should of course be secure even if the public key is known to the attacker. Generally the public key is not considered a secret, and that means schemes, but also the implementations of the public key operations are not protected against leaking the public key.

  The standard algorithms for symmetric and asymmetric encryption are AES-256, 4098-bit RSA. The answer to the above question helps compare the security level of these algorithms.

No, it really doesn't. In some situations asymmetric cryptography may be more secure, even though the key strength of the symmetric encryption is larger than the key strength of asymmetric encryption. However, it is impossible to quantify that advantage, so you cannot talk about a "level".


Do you use a salt when encrypting a password or just when hashing a password?

Salt ( a.k.a $CaCl_2$) is added before hashing to prevent rainbow attacks. So each password will be appended to a unique salt before hashing and if the server is hacked and the hashes are leaked, a hacker will have hard time un-hashing with rainbow tables.
Salting has no use in encryption/decryption because it serves no purpose.


Calculating CP-ABE random secret $s$ initialized by the data owner

Extracting $s$ in this case would seem to be equivalent for the discrete log problem in the bilinear group $\mathbb{G}_0$, using the Bethencourt CP-ABE paper notation.

To see this, first consider that if you can solve DLP in $\mathbb{G}_0$, then obviously you can solve $s$ from the ciphertext component $C=h^s$, as $h$ is already known (part of the public key).

The other direction follows from that if we assume an algorithm $\mathcal A$ capable of extracting $s$, given the global public key $PK$, ciphertext $CT$, and a secret key $SK$ capable of decrypting $CT$ according to the scheme, we can also use this algorithm to compute a discrete logarithm in $\mathbb{G}_0$.

We can use $\mathcal A$ as follows:

First assume that we know, which message, attribute-set and policy-formula $\mathcal A$ is able to "break". Call these $M,S$ and $\mathcal{T}$, respectively.
Assume $\mathcal A$ takes as input a set $\{PK, CT, SK\}$, and outputs $s \in \mathbb{Z}_P$
Now, given $g, g^s \in \mathbb{G}_0$, where $s$ is unknown, and $g$ is a generator of $\mathbb{G}_0$, we can construct $PK=\{g,g^\beta, g^{1/\beta}, e(g,g)^\alpha \}$ simply by passing $g$ as such and selecting $\alpha, \beta \in \mathbb{Z}_P$ randomly, as stated by the scheme. We can also construct $SK=\{g^{(\alpha+r)\beta},\{g^rH(j)^{r_j},g^{r_j}\}_{j \in S}\}$ similarly, as we have already selected $\alpha, \beta$. We also select randomly $r$ and $r_j$ to match $S$.
Constructing $CT$ is trickier, since it involves handling $s$, which is unknown to us, but needs to be conformant to the scheme in the eyes of $\mathcal A$. First part of $CT$ is $\mathcal{T}$, which we simply replace from what we know of $\mathcal A$. The second part is $C^o=Me(g,g)^{\alpha s}$, which we can construct, since we know $g,\alpha, g^s$ and $e(g^\alpha,g^s)=e(g,g)^{\alpha s}$. The third part is $C=h^s = (g^s)^\beta$, again elements we know or have created. The fourth part, $\{C_y,C'_y\}_{j \in S}$ (leaf-node shares in the exponents of both $g$ and the attribute hashes) requires knowing the (secret) shares for $s$. Constructing this depends on the realization that the shares and their polynomials per each node are created randomly, independently of $s$. They are only tied to $s$ by making, for example, $q_{x_1}(0)=q_R(1)$, where $q_R()$ is the polynomial of the root node (and $q_R(0)=s$) and $q_{x_1}()$ is the polynomial for the root's child $x_1$. We can then freely select other polynomial interpolation points randomly and calculate the required $C_y=g^{q_y(0)}$ and $C'_y=H(att(y))^{q_y(0)}$. It doesn't matter that we don't know $s$, as $\mathcal A$ is responsible for the possible decryption, and the interpolation points are selected independently of $s$, even though they are later connected to $s$.


Birthday attack on AES-CCM with 32-bit Authentication Tag

Please note: This answer is entirely based on the theorem the OP stated.

Notation:

$\tau$: length of the tag, in bits, this is 32 in your case
$\sigma$: the number of encrypted / decrypted blocks
$n$: the block size of the cipher, in bits, this is 128 for AES
$q_{dec}$: the allowed number of decryption queries
$\text{Adv}$: the probability that an attacker wins "the game" and thus breaks the associated security definition

Formula: $$\text{Adv}<\frac{q_{dec}}{2^\tau}+\frac{\sigma^2}{2^n}$$

First, for $q_{dec}$: You should really set this value as low as you can tolerate it to be without giving (too many) false positives, ideally this would be $1$.

The next step is to chose the upper probability you're willing to tolerate for an attacker breaking your scheme. Ideally, you'd want to set this as low as possible, for example FIPS 140-2 specifies that no random attempt should have a chance better than $\frac{1}{10^6}$ of succeeding (at wrongly authenticating the user) and it also specifies that an attacker may not have a chance greater than $\frac{1}{10^5}$ of succeeding within one minute when being alone with a cryptographic module. Also note that the chance of an attacker succeeding at least once after $k$ tries with probability $\text{Adv}$ is $1-(1-\text{Adv})^k$, so you may want to do the math and keep the value reasonably low for a given time-period and try-count an adversary has.

Now, after you figured out how much advantage you're willing to give to the attacker and how many decryption queries you're willing to accept, you can finally go ahead and use the above equation to find the maximal number of block cipher calls allowed for the scheme. This should be $$\sigma<2^{48}\cdot\sqrt{2^{32}\cdot\text{Adv} - q_{dec}}$$


Fully understanding bitcoin transcation verifying and secp256k1

G is a point on the curve, but multiplication on elliptic curves is not the same as just multiplying the x and y value by the number.
Have a look here https://en.m.wikipedia.org/wiki/Elliptic_curve_point_multiplication to see how you multiply a Point (G) with a natural number.
Because the elliptic curve, you are talking about, is not over the real numbers, but over a residual field (natural numbers mod N), the division is just another way to write the multiplication by the inverse (mod N) https://en.m.wikipedia.org/wiki/Modular_multiplicative_inverse


Is there much difference in a RSA-4096 over RSA-3072 for support/speed and security?

See here, they mention that there is not particularly good software support for RSA-3072.


How can a non-crypto-expert implement crypto libraries in a programming language?

The best option is to avoid doing so as much as possible. Ideally, your language of choice will offer a wrapper around a battle tested library such as libsodium (or maybe bearssl one day).

Additionally, in a perfect world, the interface that the library/wrapper provides should be designed to make it difficult if not impossible for you as the developer to shoot yourself in the foot. For example, if generation of the nonce for some kind of CTR-like mode is left up to you and not handled by the libraries you're using, you probably want to use a different library.


RSA without proper padding using randomness (plain old RSA) is not to be used in practice, and the attacks on small exponents assume plain old RSA, or a means of getting past the padding, such as the so-called million message attack.

The original attack on plain old RSA using such small exponents was due to Wiener. There has been further work showing that an even larger $d$ than $d>N^{1/4}$ is required, such as work by Maitra and Sarkar.

In addition, please see the extensive discussion in the question RSA with small exponents.