ECC: application of multiple multiplicative inverses

Your analysis is pretty much on point. The cost of batch inversion is only justified if we have a computation involving a relatively large number of simultaneous point additions. In a project I work on, we set a threshold of 70 additions based on our benchmarks. Our code is here if you're interested.
To generalize your example a bit, a single summation involving $n$ points could be reduced to one involving $\lceil n/2 \rceil$ points by simultaneously adding pairs of points. So we would need a rather large summation (140 terms in our case), or several simultaneous summations, to justify the cost of inversion. Even then, we would eventually fall back to projective formulas after this reduction shrinks the problem size below our threshold.
In practice, the cost of inversion isn't likely to be justified for single multiplication problems, at least assuming ~256 bit scalars. The affine formulas are quite useful in the multi-scalar setting, though. We use a multi-scalar variant of Yao's method, which involves computing a summation of precomputed points for each digit in $1 \dots 2^w - 1$. Not only are these summations potentially large, they are also independent of one another, so the whole first (and most expensive) phase of the algorithm can be viewed as $2^w - 1$ simultaneous summations.


Is it hard to compute $g^{ab}$ when given $(g, g^a, g^b, \frac{a}{b})$?

It is indeed a hard problem - in fact, it is at least as hard as the square Diffie-Hellman problem (SDH), which states that given $(g,g^a)$, it is infeasible to compute $g^{a^2}$. It is a standard and well-studied assumption, and it can be reduced to CDH (correcting a previous version of this answer where I said it does not - I was confusing with the decisional version for which no such reduction is known).
Intuition: intuitively, SDH is exactly a CDH instance together with the constraint $a/b=1$. Hence, it is a particular case of the problem you consider, where $a/b$ is known.
Reduction: given an algorithm $A$ solving your problem, here is how you solve an SDH instance: on input $g,g^a$, pick a random exponent $\lambda$, and compute $g^{\lambda^{-1}a^2} \gets  A(g,g^a,g^{\lambda^{-1}a},\lambda)$. I let you check that the input to $A$ is indeed distributed as a random instance of your problem. Then, compute $(g^{\lambda^{-1}a^2})^{\lambda} = g^{a^2}$.
For the reduction from SDH to CDH, it's a standard one; the trick is to use the identity $(x+y)\cdot (x-y) = x^2-y^2$. Setting $x = (a+b)/2$ and $y = (a-b)/2$ gives $ab = ((a+b)^2-(a-b)^2)/4$, from which the reduction to CDH is straightforward, with two calls to an SDH oracle.


Cryptographic hash function based on logistic map?

A brief description of such functions can be found in chapter 9.3 of the paper “Cryptographic Hash Functions: Recent Design Trends and Security Notions” (eprint.iacr.org/2011/565). The following excerpt is taken from page 29 of the paper:

  Hash functions based on chaos theory use chaotic maps, which are functions that exhibit particular chaotic behaviours; examples of these maps include: logistic map [source #75], tent map [source #120], and cat map [source #42]. Unfortunately, most chaos-based hash functions suffer from poor efficiency due to their inherent complex structure, which makes them unattractive as a practical approach for building hash functions.


While you're a crypto newbie, I hope that you know something about mathematics (because you've stumbled something that needs to be described in mathematical terms).  What you've described here is actually polynomial multiplication (over polynomials in $GF(2)$ (that is, we do our computations modulo 2).

That is, you can interpret the numbers as specifying a polynomial (where each bit indicates whether the coefficient of the polynomial is either 0 or 1; for example, 1011 would correspond to the polynomial $x^3 + x + 1$, and 1010 would correspond to the polynomial $x^3 + x$.  When you perform your operation, you generate the product polynomial, in this case $(x^3 + x + 1) \times (x^3 + x) = x^6 + 2x^4 + x^3 + x^2 + x = x^6 + x^3 + x^2 + x$ (this last step of dropping $x^4$ happens because we're computing everything in $GF(2)$

With that in mind, the problem of reversing the operation is actually a factorization problem (not factorization over the integers, which is what people generally think about when factorization is brought up, but its analogue over polynomials).

This implies that:

The values $A$ and $B$ need not be unique.  For one, the operation is actually symmetric (even if your algorithm to perform it is not); swapping $A$ and $B$ will always result in the same product, and so another solution in your case is $A = 1010$ and $B = 1011$.
More generally, as yyyyyyy referenced, the factorization process can reduce the product to its prime factors, but there might be multiple ways to reassemble these prime factors (for example, the prime factorization of $1010 = 11 \times 11 \times 10$).  It terms out that $1011$ is prime (and hence if we limit our multiplicands to 4 bits, $1011$ and $1010$ are the only two possible factors), however this won't be the case in general.

And if you're asking whether factorization is a hard problem, it is not.  There are known polynomial time factorization methods over polynomials (this is one way where factorization over the integers differs from factorization over polynomials).  However, those techniques are a bit beyond what a newbie can be expected to understand.


How to obtain 256-bit security from Ed25519?

It is not possible to double security level of Ed25519 any trivial way. Instead, doubling security level requires using another curve that is approximately 512 bit curve.

In systems compliant with RFC 7748, i.e. some of IETF specifications, there is Curve448 curve (Ed448-goldilocks). It is almost twice as strong as Curve25519 (its strength is 224 bits). This is often convenient alternative, because it is already available on some of the systems.

Widely deployed alternatives that are 256-bit security: Of course there are also BrainpoolP512 and NIST P-521 curves, which in theory provide 256 bit security. However, BrainpoolP512 and NIST P-521 are not considered to be as good as Ed25519 in all aspects possible (see e.g. https://safecurves.cr.yp.to/).

M-511 and E-521 are curves similar to Curve25519, which offer around 256-bit security level. However, because it is wide spread to consider security level 128 - 192 sufficiently strong for now, so larger curves are not used often in practice. For instance, NSA suite B site suggests that they consider 192-bit security level (i.e. 384-bit elliptic curves) to be sufficient to protect TOP SECRET materials.

Any optimized curve specific implementation of elliptic curves, such as the implementation of Curve25519 in lib sodium/NaCL is hard to replace efficiently with curve of different size. However, the API level of lib sodium/NaCL allows easy replacement of cryptographic primitives. Therefore, the "right" way to "hack libsodium/NACL" would probably be to provide the necessary curve(s) implementation(s) in API that is compatible with NaCL API. This usually requires use of different implementation rather than tweak of code implementing Curve25519. And some API work to adapt the API, as most Elliptic Curve implementations have APIs somewhat different from API in libsodium/NaCL.


Given enough length, which string of symbols will have the greatest entropy?

As examined by Shannon in his paper "Entropy of printed English", higher order models which allow for dependencies between nearby characters are more accurate models of English. And in general, dependencies reduce but never increase entropy, so @Guut Boy is correct, the first shall have higher entropy. In the extreme case there is essentially zero entropy about the $(n+1)$st character if the $n$th character is q, it is almost always followed by u ("coq au vin" is taken to be French).

Edit To verify this experimentally given the string $(x_1,\ldots,x_n)$ over the alphabet $A$ define the sequence $(y_1,\ldots,y_{n-k+1})$ by
$$y_i=x_i,x_{i +1},\ldots,x_{i+k-1},\quad i =1,\ldots,n-k+1,$$ over $A^k.$

Compute the entropy corresponding to the frequencies of the $y_i$ sequence. Divide by $k$ to obtain entropy per symbol.

Put simply, $k=2$ would give the entropy of bigrams and divided by 2 it should be lower than that given by monogram frequencies.


Given a SHA-256 message block, is it possible to undo the transformation of the internal state?

No, this 'unappend' operation is effectively infeasible for the SHA-256 hash compression operation; there is no known way that is less expensive than brute force.

Such an 'unappend' operation would reduce the time taken to generate preimages from $2^{256}$ to $2^{129}$ hash compression operations (assuming that the unappend operation is as cheap as the forward hash compression operation).  This would be done via a meet-in-the-middle attack, where in the most straight-forward implementation, you generate one list of $2^{128}$ intermediate states (from $2^{128}$ prefixes), and you generate a second list of $2^{128}$ intermediate states (from $2^{128}$ postfixes; starting from the target hash, you use the unappend operation), and search for a common value in the two lists.


What makes a hash function good for password hashing?

For password-hashing, you should not use a normal cryptographic hash, but something made specially to protect passwords, like bcrypt.

See How to safely store a password for details (this article advocates the use of bcrypt).

The important point is that password crackers don't have to bruteforce the hash output space ($2^{160}$ for SHA-1), but only the password space, which is much much smaller (depending on your password rules – and dictionaries often help). Thus we don't want a fast hash function, but a slow one. So your not too computationally expensive requirement is actually not possible to met. Bcrypt and friends* are designed for this.

*Bcrypt and friends: All slow hash functions. There is PBKDF-2 (which basically just iterates a fast hash with salt some configurable large amount of rounds, and thus the brute force can be easily parallelized - but it is mentioned in a NIST standard, which might be important for certain uses), bcrypt (which additionally needs 4 KB of memory, which makes parallelization (of the brute force) on standard GPUs quite slow, but can be still attacked on custom hardware with 4KB cache per processing unit), and scrypt (which takes not only a configurable amount of time, but also a configurable amount of space to execute (with a possible trade-off to time), and thus brute-forcing can not be easily (cheaply) parallelized).

Of course, you always should use a salted hash (a salt is automatically included in bcrypt). A salt is stored together with the hash in the database (e.g. it is not more secret than the hash), and will be hashed together with the password to produce the hash.

A salt alone does not help against a brute-force attack against specifically your password, but it helps against rainbow table attacks (i.e. attacks with precomputed hash lists), which can attack with the same effort all passwords everywhere at the same time, instead of only all passwords with the same salt (which should be about only one).

There is also the concept of a "secret salt" (also known as pepper), which is not stored together with the password, but at some other location not accessible by a possible attacker. (You would then usually use the pepper, as a non-user-specific piece of information, together with a normal salt.)

This does work only for some attack scenarios, where the attacker does have only (reading) access on the database (or maybe some less secured backup copy on it), but not on this pepper data (i.e. we have an attacker who can't yet execute arbitrary code on the server).

Another possibility would be to use some kind of cryptographic hardware (a token) attached on the server with an embedded key, which does some hashing operation on salt, key and password to produce the hash. Make sure to rate-limit this in case it is stolen, and make sure it does not have an interface to retrieve the secret key, otherwise your attacker (if she succeeds to gain execute access on the server) can use this, too.


There has been a huge amount of work on related questions in the past years. As Thomas Prest mention, this problem was considered for memory-hard function, which provably (in some idealized models) require some amount of space to be evaluated.

However, MHF alone are only the weakest primitive of this kind; many primitives have been designed that enhance MHFs with other desirable properties, such as efficient verification. What you are looking for is probably best captured by proofs of transient space, where you provably use a given amount of space during a computation, so that the proof can be verified in a time and space considerably smaller (polylogarithmic) than the space used by the prover.

I recommend going through the introduction of this article, which does address your problem and furthermore points to many interesting references if you want to dig the subject a bit. Most constructions use graphs with specific combinatorials properties (such as expander graphs and depth-robust graphs), which imply lower bounds on the hardness of playing a certain game (the pebbling game) on the graph. These lower bounds then translate into bounds on the memory usage in the random oracle model.


Is the strength of RSA over quadratic or other cyclotomic fields as strong as over the integers?

There are three distinct computational problems related to RSA. They are:

FACTORIZATION: given an RSA modulus $n$, find its prime factors $p$ and $q$;
ORDER: given an RSA modulus $n$, find the order $\lambda$ of the multiplicative group modulo $n$;
RSA Problem: given a ring element $a \in \mathbb{Z}_n$, a public exponent $e$ and an RSA modulus, find an element $b \in \mathbb{Z}_n$ such that $b^e = a \mod n$.

For the integers, the following reductions are known:

Given the factorization of a number $n$, it is easy to find the order: $\lambda = \varphi(n) = \varphi(p) \varphi(q) = (p-1)(q-1)$.
Given the order of the multiplicative group modulo $n$, it is easy to find the inverse exponent (if it exists): $d = e^{-1} \mod \lambda$. Given the inverse exponent, it is easy to solve the RSA problem: $b = a^{d} = b^{ed} = b^1 \mod n$.
Given the order $\lambda$ of the multiplicative group modulo $n$, there exists an efficient way to calculate the prime factors of $n$.
However, no algorithm is known that can turn an RSA problem solver into an algorithm that either finds the order $\lambda$ or factorizes $n$.

We can write these relations concisely as FACTORIZATION $\equiv_p$ ORDER $\geq_p$ RSA Problem.

Note: RSA is secure based on the assumption that the RSA problem is hard. This assumption implies, in turn, that factorization is hard. This assumption is weaker than the assumption that factorization is hard.

You correctly note that it is possible to define an analogue of RSA on other unique factorization domains (UFDs). However, on all the UFDs, factorization is either easy, or equivalent to factorization over the integers.* For example: there is a polynomial-time algorithm for factoring polynomials in one variable (see this survey). Factorization over the Gaussian integers reduces to factorization over the real integers (see this stackexchange answer).

*: I should qualify this statement by saying that not all UFDs are known. Perhaps there does exist a UFD where factorization is harder than it is for the integers. But finding this would be a scientific breakthrough because its applications to cryptography would be great.

Lastly, I should not that quantum computers might not be able to factorize efficiently in just any UFD. Shor's algorithm for factorization first finds the order $\lambda$ of the muliplicative group modulo $n$, and then uses this value to find the prime factors of $n$. The quantum algorithm to find the order will translate to any group. However, the reduction from FACTORIZATION to ORDER might not hold for all UFDs.


Licensing software with asymmetric signed files

keys are stored within the application in a very secure and complicated manner

Secure and complicated are antagonist, except when it comes to security by obscurity. But, the later is the only practical way to implement "software licensing" (the politically correct term for copy protection) on modern computers without using some sort of trusted hardware or enclave (which this answer does not consider).

  you should sign your license file and send it along with the public key so that it could be verified.

That's insecure, as noted in the question: there's noting cryptographic to prevent an attacker from generating a fresh public/private key pair, using that private key to sign an unauthorized license file, and send the signed unauthorized license file with the fresh public key.

The baseline sound way is that the code implementing the license verification, and specifically the signature check, contains (or comes with) the publisher's public key, and it is assumed¹ attackers can not change that public key, no more than they can change the code to bypass all license verification.

There is one significant advantage to thus using signature: it gives strong cryptographic insurance that no amount of reverse-engineering will allow an attacker to generate new license files that will get accepted by unmodified genuine software. That's not possible with symmetric cryptography. It's not a silver bullet, though:

Attackers can and do modify software.
Legit license files could still be accepted in multiple identical virtual machines if they reproduce the authorized machine faithfully enough.

No cryptographic protection from the above two threats is obtained by adding bells and whistles like:

Key identifiers, with multiple public keys in the software, allowing key rotation and independent issuers.
Hierarchy of keys (PKI). With this, the license file could indeed come with a public key, with that key itself signed together with its metadata (the technical term is certified) by the publisher's public key(s), soving the question's security problem.
X.509 certificates
Revocation server

¹  This assumption must rely on some level of code obscurity. Among standard techniques:

Code tries to check that it was not modified, thru OS services (e.g. Authenticode² on Windows as pointed by SEJPM) or/and self-checks.
The public key is stored encrypted, and is deciphered and checked by the security code before use, using symmetric cryptography with a key in the security code. This mitigate attacks that work by altering the public key.
Some of the above keys are hidden among other material with similar redundancy, to foil attacks that locate keys based e.g. on the distribution of the bytes they contain.
If the masters of the executable platforms have no binding rules against it, reverse-engineering is complicated by having the security code

Processed by code obfuscators.
Stored encrypted, and deciphered before execution.
Compiled to pesudo-code for an interpreter, perhaps custom.


Does every language's SHA256 implementation provide different result for the same value

Yes, SHA-256 is defined to give the same output for the same input byte sequence on every platform.  However, by design, even the smallest change in the input will change the output into something completely different.  So the most likely reason for the discrepancy you observed is that the input you used is not actually the same as the original input from the video.

Some possible causes for this discrepancy might include:

An extra null byte at the end of one of the inputs.
An extra newline or space at the end of one of the inputs.
A difference in the encoding of newlines (if the string contains one).
A difference in the capitalization of one of the letters (e.g. hello vs. Hello).
A difference in punctuation (e.g. Hello! vs. Hello. or "Hello!").
A difference in the character encoding used to encode the string as a sequence of bytes (unlikely for a plain ASCII string like Hello!, since most commonly used character encodings today are extensions of ASCII, but possible e.g. if one string was encoded as UTF-16).


TL;DR: The probability of a hash palindrome should be around $1-\frac{1}{e^2} \approx 0.8647.$

I'd like to generalize the question and answer it immediately afterwards.
First of all, let's make the setting more abstract. Say we have a set $M$ of finitely many hash values and denote its cardinality $|M|$ by $m$, usually $M=\{0,1\}^m$.

Then a more general question could be: For any random permutation $H: M \rightarrow M$, how probable is it, that there exists some $x\in M$ such that $\underbrace{H(H(...x))}_{\text{n times}}=x$,
meaning that after $n$ repetitions of $H$ on $x$ the hashed value is equal to the input. We'll have to assume surjectivity of the hash function for now, despite it technically not being accurate. Now that we know what we are looking for let's focus on the case that the $n$-th time is the first time this occurs.

If you are wondering whether $n\geq m$ is possible, there's a section about this at the end of the post, otherwise let's continue with $n < m$.

Case 1:
For simplicty let's look at $n = 1$ first. The question then is equivalent to asking what the probabiliy is, that $H$ has some fixed point or to speak in the language of permutations: $H$ does not produce a derangement of $M$, as there is one value (the fixed point) that is not deranged.

Let's first calculate the probability of a permutation being a derangement.
In general there exist $m!$ many permutations of $M$ and $!m$ of them are in fact derangements, with $!m$ meaning

$$!m=m! \sum_{i=0}^{m} \frac{(-1)^i}{i!}=m!\cdot\left(1-1+\frac12-\frac16+\frac1{24}-\ldots\right)$$.

So we get
$$P(\text{H produces a derangement})=\frac{!m}{m!}$$

Now, as our $m$ get's larger and larger our $n$ does so as well. So I will be assuming that we have large enough values, such as $m=2^{256}$, for both to make the known approximation $\lim_{n\rightarrow \infty} \frac{!m}{m!}=\frac{1}{e}\approx 0.3679$ which results in

\begin{align}
P(\text{H does not produce a derangement})&=\\
1-P(\text{H produces a derangement})&=\\
1-\frac{!m}{m!}&=1-\frac{1}{e} \approx 0.632
\end{align}

So this far, I have not said much more than in Maartens' answer, I just framed it a little bit different.

At this point it's time to let our $n$ increase. I'll reason inductively. We already established, that $n<m$ holds. For notation purposes let's denote the $n$-th repetition of $H$ as $H^{n}$, meaning
$H^{n}(x)=\underbrace{H(H(...x))}_{\text{n times}}$.

Observe, that the first hash not producing a derangement leaves only around $37\%$ of a chance open for the remaining cases to occur. Since those cases are disjoint you can add their corresponding probability.

Case 2:
Now, if the first hash did produce a derangement, what is the probability of the second hash not producing one as well?
As argued before, we get

$P(H^{2}\text{ does not produce a derangement})= P(H \text{ does not produce a derangement})
\\ + P(H \text{ does not produce a derangement})\cdot P(H^{2} \text{ produces a derangement}))=\\(1-\frac{1}{e}) + (1-\frac{1}{e})\cdot \frac{1}{e}= 1-\frac{1}{e^{2}}\approx 0.8647.$

I should mention, that $H^2$ is just another permutation on $M$, meaning that the probability for it to produce a derangement is exactly the same as for $H$.

That much for the start of my inductive reasoning. In the next steps $H^3, H^4 \dots H^{m-1}$ the probablities have to be added in a similar way. This yields the formula

$P(H^{m-1} \text{does not produce a derangement})= \sum_{i=1}^{m-1} \frac{1}{e^{i-1}} - \frac{1}{e^{i}}$. The last telescoping series evaluates to
$1-e^{1-m}$.

The result also mirrors the intuition in the way that not producing any derangement becames less and less likely as we continue to hash our values, thus at some point it is nearly guaranteed to get some hash value back to the input, with the case of $m$ iterations being covered seperately as cycling back guaranteed.

Now, as promised, the argument why $n<m$:
First of all, note that $n$ can't be equal to or greater than $m$. The reason: Let $j$ be any element in $M$. If $\underbrace{H(H(...H(j))}_{m-1 \ times}$ would not have produced a cycle back to any previously hashed value yet, it would have to do so in the next iteration, since all other $m-1$ elements in $M$ were already reached exactly once. This means, that any Hash repeated $m$ times is guaranteed to cycle back to the input.


In RSA, do I calculate d from e or e from d?

Well, as far as the mathematics of RSA are concerned, $d$ and $e$ are symmetric; they are related by the relationship:

$$ e·d \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)}$$

So, from the perspective of making it work, it doesn't matter which you choose first.

Now, it is not sufficient that the RSA encrypts and decrypts properly, it also has to be secure.  From a security perspective, these values are not symmetric; $e$ (the encryption or verifying exponent)  is public and $d$ (the decryption or signing exponent) is private.  This means that $d$ must be a hard to guess value.  On the other hand, we couldn't care less if someone could guess $e$; we're going to tell him that value anyways.

That means that if we choose $e$ (and then compute $d$), we can choose $e$ to be a small value. This has a real advantage; it makes the public operation (public key encryption, signature verification) go much faster, without any loss of security.

In contrast, if we choose $d$ and then compute $e$, we have to select a large value for $d$ (both so that it is not guessable, and to avoid subtler attacks that can factor $n$ given an $e$ that corresponds to a small $d$), and so we end up with $d$ and $e$ both being large.  This slows down the operation without any corresponding advantage.

Because of this, common practice is to select a small $e$ (65537 is the most common value), select primes $p$ and $q$ such that $p\not\equiv 1 \pmod e$ and $q \not\equiv 1 \pmod e$ (so that $d$ exists), and then compute the corresponding $d$ value.


Signing with RSA-SHA256 algorithm using EC keys

tl;dr  - RSA keys and ECDSA keys are not compatible and cannot be used in one anothers signature algorithms

In RSA you have the following:

A public key $(e, N)$ where $e$ and $N$ are integers.
A private key $d$ where $d$ is an integer and $ed \equiv 1 \bmod \phi(N)$, $\phi$ being Euler's totient function.

In ECDSA you have:

A public key $Q$ which is a point on an elliptic curve e.g. $Q = (q_x, q_y)$.
A private key $d$ which is an integer such that $dG = Q$, where $G$ is the base point of the elliptic curve.

Given those facts the question you pose doesn't make sense. Indeed an RSA private key and an ECDSA private key seem similar in that they are both integers, but in RSA $d$ needs to also have a corresponding $N$, which is usually left out since it is a public value (if you want to be pedantic the private key is really $(d, N)$ in RSA).

So say I generate an ECDSA private key $d$ and want to sign a message $m$ with it via RSA-SHA256. RSA-SHA256 would look something like $signature = \mathrm{sha256}(m)^d \bmod{N}$ (actually you would want to apply padding after the hash and before the exponentiation but that's not really important here).

But if only $d$ is generated, as one would do for an ECDSA private key, how does one perform the $\bmod{N}$ operation? You can't because $d$ by itself is an incomplete RSA private key, you also need the $N$ corresponding to the public key.

Let's say you do generate some $N$ after the fact so that you can perform signing. Verification would run into the same problem of keys not being compatible. RSA-256 signature verification for message $m$ and signature $s$ looks something like $\mathrm{sha256}(m) =^? s^e \bmod N$ where $(e, N)$ is the RSA public key. But if one does not have $(e, N)$ and is provided only a point $Q = (q_x, q_y)$ that lies on an elliptic curve, how does one then verify the signature? One of course can't.

SEJPM is probably correct in his comments that the library you're using sees that the signature algorithm doesn't match the key and chooses the correct signature algorithm for signing. If the library isn't raising a warning and quietly acting as though all parameters are valid I would consider switching libraries.


Is it safe to use a key as message in keyed hashing (HMAC)?

Question: Is it safe to apply step 3 in terms of: can the password key be (easily) determined because it is known that it is the message to be hashed?

Yes, this should be fine, although you might as well use a constant as the message input when calculating the HMAC. Theoretically some implementation could be more lax with regard to side channel attacks about the message than the key, though I doubt that is an issue in practice.

Knowing the self-HMAC of the key will allow an attacker to easily verify their guessed passwords, but PBKDF2 will slow them down and anyway the speedup is not significant, compared to attempting to decrypt the data with the derived key.

(There are better alternatives to PBKDF2, like scrypt, argon2, bcrypt.)


Why is the Fiat-Shamir heuristic deemed secure in the ROM?

The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive protocols. However, an easier place to start is the seminal paper of Canetti, Goldreich and Halevi, called The Random Oracle Methodology, Revisited. This paper shows that there exist signature and encryption schemes that are secure in the random oracle model, but fail for every concrete instantiation, for any hash function. They prove this by carefully constructing a scheme that will fail for any hash function instantiation. Their proof does not work in the random-oracle model (as with Goldwasser and Tauman) since the description of the hash function does not exist when it's a random oracle (it's certainly not polynomial size).

It's important to understand what this actually proves. The theorem proven shows that it is impossible to generically replace the random oracle with a hash function. That is, there does not exist any hash function that can be used to replace the random oracle in every construction, in order to get a proof in the standard model. Furthermore, there exist constructions that cannot be proven secure in the standard model at all, for any hash function. Thus, the random oracle model is not "sound" in the sense that it cannot always be a stepping stone to a standard-model proof.

What this does not say is that there are no random-oracle constructions that can be proven secure in the standard model. Since my previous double-negative sentence will surely be confusing, I'll explain. There may exist schemes that are proven secure in the random oracle and can be instantiated with a concrete hash function. These proofs do not state that this is impossible. Thus, it is theoretically possible that a hash function can be found to instantiate RSA-OAEP to be secure in the standard model, and it is theoretically possible that a hash function can be found to instantiate Fiat-Shamir on Schnorr's protocol specifically so that the result is a secure signature scheme in the standard model (I may be wrong, but I don't think that this has been proven to be impossible). To be honest, it is very unlikely that this is the case (at least in my opinion), but this hasn't been ruled out.


RS Erasure Coding and Shamir's Secret Sharing

Shamir's (m,n) secret sharing scheme has a secret $s_0$ which is represented as an element of a finite field $\mathbb F_q$ of $q$ elements.  There are also $m-1$ other "randomly chosen" elements $s_1, s_2, \ldots, s_{m-1}$ that the designer uses.  The scheme creates a
polynomial
$$S(x) = s_0 + s_1x + \cdots + s_{m-1}x^{m-1}$$ and evaluates $S(x)$ at $n$
distinct nonzero
elements $\alpha_1, \alpha_2, \ldots, \alpha_n$.  Note that $n$ must be at least
as large as $m$ and cannot be larger than
$q-1$.  The $n$ pieces of the secret that are handed out to those sharing in the
secret are just these polynomial values $S(\alpha_1), S(\alpha_2), \ldots, S(\alpha_n)$.

Given $m$ of the $n$ shares, the Lagrange interpolation formula gives the unique
polynomial $T(x)$ of degree $m-1$ or less that interpolates through these $m$ points,
that is, for each share $[\alpha_j, S(\alpha_j)]$ that is available to the reconstructor,
$T(\alpha_j)$ equals the share value $S(\alpha_j)$.  Therefore, $T(x)-S(x)$ is a
polynomial of degree $m-1$ or less that has $m$ roots in the field, and by the
Fundamental Theorem of Algebra, must be zero.  Thus, $T(0) = s_0$ is the secret.

  If $m$ shares are available, the secret can be recovered.

If more than $m$ shares are available, any $m$ of them can be used
to reconstruct the secret.  Shamir also showed that if fewer than
$m$ shares are available, then
the secret cannot be recovered; in fact, all possible $q$ values of
the secret are equally likely to be obtained if one interpolates through
fewer than $m$ shares.

The McEliece-Sarwate generalization of this scheme via Reed-Solomon
codes has two aspects.

First, by using the error-correcting properties
of Reed-Solomon codes, it is possible to recover the secret even if
some of the shares are in error.  Here, error means that the
shareholder submits a share value that is different from the value
given to him/her.  Such errors could be due to malice, or could occur
because of accident (e.g. a flash drive holding the
share is forgotten in a pocket and gets washed in a clothes-washer).
In the standard Shamir reconstruction, damaged shares are no different
from valid shares and Lagrange interpolation will almost always
reconstruct a "secret" that is different from the original.  Unless
there is error control built into the secret (e.g. a CRC checksum),
there is no way of knowing that the recovered "secret" is different
from the original.  On the other hand, the properties of Reed-Solomon
codes say that if $m+t$ shares are available of which at most
$\lfloor t/2\rfloor$ are in error, then by using a Reed-Solomon
decoding algorithm, the secret can be successfully recovered.  The
reconstructor does not need to know which shares are in error (if
this were known, the damaged shares could just be ignored!).  The
decoding algorithm also indicates which shares, if any, of the
$m+t$ submitted shares are in error, that is, cheaters (or launderers!)
can be identified, and of course the correct share values can be
computed and given to the innocent share holders on new flash drives.
It is also true that if more than $\lfloor t/2\rfloor$
shares are in error, the Reed-Solomon decoding algorithm will quite likely
refuse to reconstruct a secret, and will reconstruct a "secret"
different from the original only in rare circumstances.  Note that
a failure to reconstruct a secret is not fatal (unless $m+t = n$)
since one can always await the submission of more valid shares so
that the effect of the invalid ones can be overcome.  In this form,
there is no difference between the security of the Shamir scheme and
the Reed-Solomon coding scheme.
The second aspect of Reed-Solomon coding schemes considered
in the McEliece-Sarwate paper is that it is not necessary to
fill up $S(x)$ with $m-1$ randomly chosen symbols.  In fact,
the secret can be all $m$ symbols $s_0,\ldots,s_{m-1}$ instead
of just $s_0$ being the secret.  One advantage is that we can
use a smaller finite field.  If the secret is $1000$ bits, say,
and $m=10$, Shamir's scheme would operate over $\mathbb F_{2^{1000}}$
and each share of the secret would also be $1000$ bits long.
$10$ kilobits ($10$ one-kilobit shares) would be needed to
recover the secret.  On the other hand, a Reed-Solomon coding
scheme could divide the secret into $10$ $100$-bit symbols and
operate over $\mathbb F_{2^{100}}$.  Also each share would
be $100$ bits long, and, as before, only ten such short shares
would be needed to recover the secret.  This reduction in the
field size does come at some cost in security.  If only $9$
shares are available to a cabal and they guess at possible
values of the tenth needed share, they can come up with a
"short list" of only $2^{100}$ values that the $1000$-bit secret might
have.  Shamir's scheme in a similar predicament would have
a list of $2^{1000}$ possible values of the secret, thus
providing perfect security.  The trade-off between reduction
in security and ease of implementation as well as storage of
each share of the secret is something that needs to be evaluated
for each application.  The most secure scheme has shares that
are as long as the secret while the Reed-Solomon scheme can
be used to reduce the share size at the cost of reduced
security.

Edit Another version of secret-sharing gives the $i$-th share
holder the value of $\alpha_i$ as well as the share $S(\alpha_i)$
(this requires twice as much storage).  Thus, $m$ share holders
can reconstruct the secret if they know Lagrange interpolation
and have access to a computer that does the needed finite-field
arithmetic without anyone else knowing about it.  In the standard
scenario, the $i$-th
share holder only has $S(\alpha_i)$ without any knowledge of
$\alpha_i$, and only an official reconstructor knows that Joe
Blow is the $i$-th share holder and looks up $\alpha_i$ when
Joe submits his share for reconstruction purposes.
In this case, secret re-construction
can only be done by the official re-constructor; a cabal
of $m$ rebellious share holders cannot reconstruct the secret
in private and use it to overthrow the Evil Empire.
When share holders actually have $[\alpha_i,S(\alpha_i)]$,
a cheater could alter either quantity or both, and an innocent
error might do likewise.  The solution to this problem is more
difficult.  For what can be done in such
cases, see, for example, here.


How do I attack an RSA setup where e is even?

Unless they did something wrong (either accidentally, or deliberately to make it easy), there is no practical way.

It's well known that, if you're able to compute the squareroot of an arbitrary number modulo a composite, you can efficiently factor that composite.  And, solving $e=4$ is equivalent for solving the RSA problem twice with $e=2$.

Now, it's possible that they somehow made it feasible for you, such as:

Selecting a prime $N$, or one that is easy to factor
Selecting a tiny message (however, you did indicate that they didn't do that)

As for why we generally select $e$ relatively prime to $p-1$ and $q-1$, well, that's not actually to make things more difficult for the attacker.  Instead, it's so that the legitimate decryptor (that is, the guy with the private key) can uniquely determine the original message.

After all, we have $M^4 = (N-M)^4 \bmod N$ for all messages $M$; hence if the decryptor got the value $M^e \bmod N$, he would have not inherent way to determine if $M$ or $N-M$ was the original message.

However, that doesn't help you.


What is the most secure way to let Alice "input" her private key, transfer it to the server and decrypt the message?

What you really want to do is never have any unencrypted data leave the server in the first place. What should be happening is that the server is sending the encrypted message to Alice, who then decrypts it locally.


Finding the Input if Hash Value, Hash Function, and Key are known

First of all, HMAC is not exactly a hash function. The Wikipedia clearly states that;

  In cryptography, an HMAC (sometimes expanded as either keyed-hash message authentication code or hash-based message authentication code) is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key.

In case of HMAC-SHA256, the hash function in the HMAC is SHA256.

Remember that, Cryptographic hash functions are not invertible functions, and we require that they have pre-image, second pre-image, and collision resistance.

There is still an ambiguity in the question; I'll try to answer in two ways.

The input is exactly 15 numbers where first 7 are known.

In this case, the input space is limited, 8 unknown numbers this makes $10^8 \approx 2^{27} $ and this input space can be tested very quickly even with a raspberry pi.

What about finding a $m$ without generating the pattern. Actually, this means that, you are looking for pre-image for HMAC-SHA256. There is no known attack for HMAC. For alone SHA-256 there are pre-image attacks, for example:

Advanced meet-in-the-middle preimage attacks require $2^{248.8}$ complexity with 42 rounds.

This will be infeasible. Note that practical collision attacks for SHA-256/512 is possible with reduced rounds 26/64 and 27/80, respectively.
The input contains 15 numbers where first 7 are known.

In this case, we have a structure as;

    ppp...pppfffffffrrrrrrrrsss...sss

Knowing some part of the input may help with testing each value. Unfortunately, there is no information about the prefix (p) size and suffix (s) size. So, one has to consider cases.

What about finding a $m$ without generating the pattern. The pre-image status is the same as in the first case.


I don't see any obvious way to do this without violating the security of GCM; at least, if you are at all concerned with an evesdropper (and if you're not, why are you encrypting at all?)

Here is a distallation of your requirements: you want to have the sender send the ciphertext (including nonce, ciphertext and tag).  Then, you want the sender to be able to send the edits to the ciphertext; the receiver applies these edits to its copy of the ciphyertext.  Then, the receiver decrypts this editted ciphertext, it gets an editted plaintext (and the editted tag authenticates if nothing was modified by a third party).  In your case, the edits to the plaintext are appending arbitrary texts; that's not important for this analysis.

However, one of the requirements for GCM is that you never allow an attacker access to two different ciphertexts generated with the same nonce/key pair.

So, if the modified ciphertext uses the same nonce (and key), then this is an obvious violation; someone listening into the exchange will gain the original ciphertext, and the editted version; that allows him to deduce the internal 'H' value (and thus allow him to generate his own ciphertexts).

On the other hand, if the modified ciphertext uses a different nonce (or key), the keystream used to encrypt the plaintext changes; the two keystreams are (one hopes) computationally indistinguishable from random, and so any edit will not be more efficient than just producing a new ciphertext to replace the old one.  Obviously, this would not meet the spirit of your requirements.

So, it appears that what you're trying to achieve would not be doable with GCM.

However, it turns out that, if you are not concerned with evesdropper, you could actually incrementally recompute the tag; I won't go into the details (in part because, as I said above, it generally is a bad idea).


Are all stream ciphers algorithms based XOR with the key?

Almost all. The reason is simple; x-or is a cheap operation and  $c = m \oplus k$ then
$$c \oplus k = (m\oplus k) \oplus k = m$$
Therefore if you x-or the message with the keystream then re-xor is equal to the message. This helps to use the same logic as encryption and decryption. This reduces the cost of hardware.
There is another important property of the x-or;

x-or of a random sequence with a non-random sequence is random. Therefore it can hide our non-random messages very well if the produced sequence for the stream cipher has good randomness.

Note that a stream cipher doesn't need to output one bit per cycle/encryption.  AES in CTR mode is a stream cipher that produces 128-bit per AES encryption/counter. The ChaCha20 stream cipher has a 64-byte block size, in other words, it produces 512 bits per counter.
As pointed FGrieu, there is also modular addition/substruction, when the number of the symbols are not power of 2, $c = m + k \bmod n$ for encryption and $m = c - k \bmod n$ is used. The Solitaire manual stream cipher uses this operation.

What happens when the key length is less than the size of the message?

Stream ciphers are designed to produce a very long sequence of bits, so there is no issue here. The real issue is reusing a (key,nonce) pair more than one. This can result in the loss of confidentiality.

Does all algorithms perform the same XOR operation with the key or there are other operations to be performed as is the case with block cipher where multiple rounds and derivate keys are used?

Well, the obvious answer is the x-nor, that is $\neg\oplus$. Can we use other than x-or and x-nor? Exercise:

find a binary operation that doesn't destroy information yet doesn't leak, too!

How can I better understand the stream cipher?

Well, reading a book about stream ciphers and designs? You can start from

The Handbook of applied cryptography chapter 6
Study LFSR-based stream ciphers, they are easy to understand.
Study RC4
Andreas Klein's Book : Stream Ciphers
Next step is eSTREAM: the ECRYPT Stream Cipher Project. Read the eSTREAM candidates/winners and attacks on them.


How is the ciphertext labeled with a set of attributes in Key-Policy Attribute-based Encryption (KP-ABE)

The first Attribute-based Encryption scheme was introduced by Sahai and Waters in 2005: Fuzzy Identity-Based Encryption. It worked by associating a set of attributes with both the ciphertext and the private key of the user.

Take for example the ciphertext which is encrypted with the attribute set $\{A, B, C\}$ and the private key of some user with the attribute set $\{B, C, D\}$. If the system threshold $d$ is chosen as 2 then the user would be able to decrypt the ciphertext with because the cut set of the ciphertext attribute set and the private key attribute set is of size 2 which is greater or equal to the global threshold $d$.

This is of course not very useful, because this only achieves cryptographic access control based on set overlap. One generally wants to use more complicated policies which are more expressive than simple sets. Such expressive policies where later achieved by Goyal et al. in 2006: Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data (KP-ABE).

Instead of using two sets, the private key of the user is generated (associated) from a boolean formula (policy) of attributes and the ciphertext is encrypted with an attribute set. For example, the ciphertext may have been encrypted with the set $\{A, B\}$. Now we have two users with private keys from two different policies. $$SK_1=\text{Keygen}(MSK, ``A\ \text{and}\ (B\ \text{or}\ C)")$$ and $$SK_2=\text{Keygen}(MSK, ``A\ \text{and}\ (C\ \text{or}\ D)").$$

You should see that the user who possesses $SK_1$ can easily decrypt the ciphertext, because ciphertext was encrypted with $B$, the clauses $B\ \text{or}\ C$ is fulfilled as well as the $A$. Since both clauses are fulfilled, the $\texttt{and}$-gate is also fulfilled. This means that the attribute set satisfies the policy in the private key and $SK_1$ can decrypt the ciphertext.

The user who possesses $SK_2$ cannot decrypt the same ciphertext, because the necessary clause $C\ \text{or}\ D$ is not fulfilled by the attributes present in the ciphertext. Therefore the $\texttt{and}$-gate cannot be fulfilled and $SK_2$ cannot decrypt the ciphertext.

There is also CP-ABE by Bethencourt where the roles are reversed, because a policy is used to encrypt the ciphertext and private keys are generated from attribute sets.


How secure is file header encryption for large files?

It depends on the format. The size suggests it is a video. However, video formats seems to be designed to be seekable. That means, the attacker seems to be able to:

Create some header (guessing the resolution and some other information)
If the beginning was damaged, play and seek in the file.


What are the properties that makes this "safer" (less exposed to failure) than just: [simple construction]

Well, there's an easy attack on the simple construction: Pick any message block $P$ and construct a message $M=P\|P$ (so $P$ twice). Now compute the MAC-tag of that message: $\text{MAC}=E_k(\text{IV}\oplus P\oplus P)$ which is just $E_k(\text{IV})$ because $x\oplus x=0$. Now pick any different message $P'$ and $M'=P'\|P'$ and compute the tag for that message: $\text{MAC}'=E_k(\text{IV}\oplus P'\oplus P')$ which again is $E_k(\text{IV})$. So both messages have the same tag. As soon as you see the tag for any of them, you can make somebody accept the other one as well. This is a property that we don't want from MACs.

If it helps your imagination: $P=0^n$ and $P'=1^n$, i.e. they are the message of all-zeroes and all-ones.


Proof for collision resistance on a block-based hash

If I understand you correctly, you are using the Simon key expansion process, so that the input to your block is the 256 bit Simon key, and the output is the 256 bit last round key (and you're ignoring the Simon encryption process entirely).

If so, three nits:

I believe that you can find preimages for your hash function in $O(2^{64})$ compression function evaluations.  This happens because the key expansion process is invertible; that is, given a 256 bit output, you can find the corresponding 256 bit input.  So, what an attacker would do is assume a 2 block message; he would:

Generate $2^{64}$ initial blocks, and compute the intermediate states from them.
Generate $2^{64}$ final states consisting of the target hash and $2^{64}$ different $K_i, K_{i+1}$ words, and compute the inverse key expansion
Look for a collision in the $K_{i+2}, K_{i+3}$ words; if you find one, this implies a preimage

This is easy to fix; make the transform noninvertible.
If you want your hash function to be collision resistant, you'll need to add some collision-free padding mechanism.
This architecture is actually closer to a Sponge hash function than a Davies-Meyer type construction (just in case you're wondering)


How does the attack on MD5 work that allows a file to show its own (full) hash?

TO understand what is going on, you have to consider how MD5 works and how the collision attack works.

MD5 is a Merkle-Damgård hash function: it process the input data by blocks (of 64 bytes each), with a "running state" of 128 bits. So there is an internal function $f$ that takes as inputs the current state $s$ and the next message block $m$, and outputs the new state. The state after processing the last message block is the hash value.

The known collision attacks produce pairs of two-block messages that trigger a collision, with an arbitrary starting state value $s$. That is, given a 128-bit value $s$, the attack produces blocks $m_1$, $m_2$, $m'_1$ and $m'_2$, such that $(m_1,m_2) \neq (m'_1,m'_2)$, and $f(f(s, m_1), m_2) = f(f(s, m'_1) m'_2)$. The important point here is that since $s$ is arbitrary, then one can "chain" collisions: taking as value of state the output $s'$ of the expression above (i.e. what you get after processing $m_1||m_2$ or $m'_1||m'_2$), then you can run the attack again and find a new colliding pair $m_3||m_4$ and $m'_3||m'_4$.

At that point you have a four-way multicollision: the following four messages:

$m_1||m_2||m_3||m_4$
$m_1||m_2||m'_3||m'_4$
$m'_1||m'_2||m_3||m_4$
$m'_1||m'_2||m'_3||m'_4$

all hash to the same value.

Now iterate that process, by running the attack 128 times. You end up with 128 two-block collisions that can be chained, allowing a grand total of $2^{128}$ messages (each consisting of 128 pairs of blocks, i.e. 16384 bytes in length) that all hash to the same value.

Another crucial consequence of the Merkle-Damgård structure is that once you have a collision, then you can add an arbitrary suffix to the colliding messages, and it is still a collision. Similarly, since the attack works with any starting state value, you can also have an arbitrary prefix.

The rest of the attack is non-cryptographic hackery. Basically, you need a document format that is flexible enough to perform a "selection": something that can print out different pictures based on specific bytes somewhere else in the file. Roughly speaking, the file will have this format:

prefix || multicollision || suffix

where the prefix and suffix select the picture to display based on the contents of the "multicollision" part. Then you just have to select the right combination in the "multicollision" part (among the $2^{128}$) such that what is displayed matches the intended output: since this is a multicollision, the choice does not alter the final hash value.

This "image selection" mechanism can be more or less easy based on how flexible the format is. With Turing-equivalent languages (e.g. PostScript), this is trivial(*). With PDF and animated GIF, this is doable. With some formats, this is extremely hard or even impossible (e.g. if the format is "plain ASCII text readable by a human, then there is no "selection" mechanism).

(*) In fact, with a fully Turing-equivalent format, one can use Quine techniques to display the file hash even without leveraging any collision. It would work with unbroken hash functions like SHA-256 as well. But that's quite something else, and is not really a question of cryptography.


Ensuring CSRNG integrity in reduced range

There are two cases to distinguish:

Either the limit (let me call it $\ell$) divides 256. In this case, your method gives indeed random numbers in the appropriate range, but one can do better: simply pick a random byte $b$ and return $b\bmod \ell$.
Either $\ell$ does not divide 256, and you have an issue.

Let me develop a bit on this issue. Your assumption was that using your method, each value would be biased, but with a bias depending of the previous value, which you assumed to be uniform. However, this does not quite work, for two reasons. First, your previous value is not uniform, as your first value is 0, so you cannot assume that the bias will be "uniformly spread". But even more, assume your previous value is uniform; then it does not solve the issue at all. Indeed, what you want from your random-looking sequence is that each value looks random even given the previous values. This is very important, it is fairly trivial to generate a long sequence of integers so that each integer taken independently look random, but the sequence is clearly not a random-looking sequence.

So, by adding the previous value to your byte before reducing modulo $\ell$, you do not solve the problem: there is a bias, which depends on the previous value, which you should assume is available to the adversary.

Let me restate the classical solutions that provably work:

You can take $b$, and if it is lower than $\ell$, keep it, otherwise drop it and take the next byte. This is the rejection sampling.
You can take a sequence of, say, 9 random bytes, parse them as a random 72-bit integer $n$, and compute your output as $n \bmod \ell$. This gives you a distribution statistically close to uniform over $[0, \ell-1]$, with a bias bounded by $2^{-64}$, as $\ell$ is lower than $2^8$.


How to test an encryption against different attacks

Cryptograph Network Security by William Stallings is pretty decent read I had to read in my crypto class. Each encryption method is different, the way you can test its effectiveness as a encryption method is by what they call avalanche effects , where by changing one bit in decryption it changes a lot of other bits throughout the process.

Also I recommend checking out capture the flags online that have cryptography categories to use for real world practice. Just a simple google search will find you free sites online to practice, and you can even see write ups for the challenges to get better ideas how to attack the encrypted flag.

Hope this helps, cryptography just takes some time then you will understand it really easy. Good luck


a possibly stronger type of attack on identity-based encryption

You can probably prove the security against your game from the security in the IND-ID-CCA game of Boneh and Franklin (see http://courses.cs.vt.edu/cs6204/Privacy-Security/Papers/Crypto/IBE-Weil-Pairing.pdf). The idea is to create an adversary $\mathcal{B}$ against IND-ID-CCA from your adversary $\mathcal{A}$. Essentially $\mathcal{B}$ will play man-in-the-middle between the IND-ID-CCA challenger and $\mathcal{A}$.

When $\mathcal{B}$ receives the $2k+1$ identities from $\mathcal{A}$, he chooses one of those at random (let's call it $ID_0$) sends two random values $(x_0,x_0')$ together with $ID_0$ to the challenger and receives an encryption $C_0$ of either $x_0$ or $x'_0$. For each of the other identities $ID_i$, $\mathcal{B}$ encrypts values $x_i$ chosen in such a way that $(x_0,\cdots, x_{2k+1})$ are valid shares for the secret sharing, the ciphertexts are denoted by $C_i$. Then $\mathcal{B}$ returns the ciphertexts to $\mathcal{A}$. [Note that if the challenger has chosen $x_0$ your game is perfectly emulated, otherwise, the shares are invalid]

When $\mathcal{A}$ sends the $k$ identities, if $ID_0$ is in the set $\mathcal{B}$ aborts the communication with $\mathcal{A}$ and returns a random guess to the challenger. Otherwise, $\mathcal{B}$ asks the $k$ keys to the challenger and sends those to $\mathcal{A}$. When $\mathcal{A}$ returns $y$, $\mathcal{B}$ proceeds as follow:
If $y$ is consistent with the share $x_0$, then $\mathcal{B}$ guesses that the challenger returned an encryption of $x_0$, otherwise $\mathcal{B}$ guesses at random.

If $\mathcal{A}$ wins your game with probability $\epsilon$, the advantage of $\mathcal{B}$ is approximately $\epsilon/4$.

Additional information:

The advantage is not $\epsilon/2$ as I wrote initially but $\epsilon/4$, this is due to the fact that there are two possible definitions for the advantage of a distinguisher. Some papers use the absolute value of the difference to $1/2$ and some papers use twice that. For technical reasons, twice the difference is preferable and I did not initialy noticed that Boneh-Franklin don't use this version.
How is the advantage computed ? This needs an additional hypothesis which I did not mention. Take your game with a variable number of shares, say $\ell$, keeping $k$ fixed and denote by $\ell_0$ the smallest value for which there exists an adversary with non-negligible advantage. Clearly, if there exists an adversary for $\ell=2k+1$ then $\ell_0\leq 2k+1$. And, of course, $\ell_0>k$ because with $k$ shares you have no information about $x$.

If $\ell_0=2k+1$ use the above reasoning. in this case, $\mathcal{A}$ cannot return $y=x$ with non-negligible probability when one share contains $x'_0$ because you could then transform $\mathcal{A}$ into an adversary against $\ell_0-1$ shares by just adding a random valued share. If $\ell_0<2k+1$, redo the reasoning with the new $\ell_0$. This changes the advantage to $\frac{(\ell_0-k)\epsilon}{2k}$. The only problem is that in the case $\ell_0=k+1$, the reduction is not tight.

Response to Ricky's comment on the tightness of the reduction:

I don't see how you get a degradation exponential in $k$. Here is a more precise analysis of the full game if you don't assume that the probability of success jumps from negligible for non-negligible but do a more precise analysis.

Let $\epsilon_\ell$ be the best possible advantage for an adversary that wins your game with $\ell$ queries. Note that $\epsilon_\ell$ form an increasing sequence.

Moreover, the advantage in your original game is:
$$
\epsilon=\epsilon_{2k+1}=\sum_{i=k+1}^{2k+1}\epsilon_i-\epsilon_{i-1}.
$$
As a consequence, at least one of the differences is bigger than $\epsilon/(k+1)$.

Run $\mathcal{A}$ for an $\ell_0$ such that $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$ is not too small. The probability that $\mathcal{A}$ wins with $\ell_0$ genuine shares is higher than the probability with a fake share by at least  $\epsilon_{\ell_0}-\epsilon_{\ell_0-1}$, otherwise $\mathcal{A}$ could be used to improve $\epsilon_{\ell_0-1}$.

As a consequence, $\mathcal{B}$ wins with advantage at least $\frac{(\ell_0-k)(\epsilon_{\ell_0}-\epsilon_{\ell_0-1})}{2k}\geq \frac{(\ell_0-k)\epsilon}{2k^2}$.

So the degradation is polynomial in $k$ not exponential.


Additive homomorphic encryption: strict equality - handling congruence

I think this kind of scheme can't even be construct, because the message space is always finite, thus we are always working in some kind of modular structure.

If we say that $\mathcal{M}$ has $n$ elements and that it is closed to the sum, then for all $m \in \mathcal{M}$, adding $m$ to itself generates $\{m, 2m, 3m, ..., nm, (n+1)m\} \subset \mathcal{M}$.

But by the Pigeon hole principle, at least two of those values are equal. So, let's say $pm = qm$ with $q > p$, then $(q - p)m = 0$.

Therefore, there exists this positive number $k := (q - p)$ such that $E((k-1)m) \otimes E(m) = E(0)$.

That said, what was typically done was to chose parameters in a way that the message space is large enough for the application, so that the generated values don't get bigger than the known modulus (then the decrypted value is always equal to the expected one, without being reduced).


Practical use of semi direct product of group in Cryptography

Public key exchange using semidirect productof (semi)groups by Habeeb et al
https://eprint.iacr.org/2013/226.pdf


Programming language for modular arithmetic over large numbers

Yours is a perfectly legitimate question.

I know that C#, F#, Java and Scala have an in-built support to handle arbitrarily large numbers, i.e. as large as your computer’s memory.


The sponge construction does not have a compression function in the sense of traditional hash constructions like Merkle–Damgård.  Instead, it operates using a permutation function $f$ which "mixes" or "absorbs" the input into the state of the algorithm.  Strictly speaking, it does take an input larger than the output it produces, but this function is actually reversible and so is not comparable to one-way compression functions like in MD5 or SHA-1.


The encryption process will use MiniAES which IS same as normal AES with all component reduced while maintaining the same structure and security of normal AES.

MiniAES most certainly does not have the same security as normal AES.  To quote the original paper:
It is meant to be a purely educational cipher and is not considered secure for
actual applications.

Indeed, it has essentially zero security:

It has a 16 bit key.  It is trivial for an attacker to try all 65536 keys to search for the correct one.

It has a 16 bit block size; that means you'd hit he birthday bound after 512 encrypted bytes.

It doesn't reach full change propagation; an output nybble is a function of the key and two of the input nybbles (the other two input nybbles being irrelevent).  Hence, it can be characterized as two 8 bit block ciphers interleaved (hence you hit the birthday bound after encrypting only 32 bytes...)

It's sole reason for existence is to serve as target practice for budding cryptographers.


Does the plaintext have to be at least as long as the key in Polyalphabetic substituion cipher

I'm not aware of any classical polyalphabetic ciphers where the key could not be longer than the message.

For the Vigenère cipher, the key is, effectively, repeated to make it as long as the message.  There is no reason why it could not be repeated less than once, effectively discarding the unnecessary characters at the end of the key.

Similarly, in the autokey cipher, the key is dynamically extended by appending either the plaintext or the ciphertext message to it, ensuring that the extended key never runs out of characters.  If the message is no longer than the key, however, this extension is never needed, and the autokey cipher behaves exactly like the Vigenère cipher.

In fact, if the key for the Vigenère or autokey cipher is:

at least as long as the message,
composed of purely random characters, and
never used to encrypt more than one message,

then the cipher becomes an unconditionally secure one-time pad.  This is the most secure kind of cipher, being provably impossible to decrypt without knowledge of the key.  Alas, the strict requirements on the key — not the least being that it needs to be at least as long as the message being encrypted — make it rather impractical for most purposes.

As for your side question, obviously, if you deliberately choose only keys that consist of a single repeated character, then a Vigenère cipher becomes just a simple shift cipher.  However, if you're using a one-time pad with random keys, there is a (very small) probability that all the random characters will be the same, and that's perfectly fine.

In fact, if you threw out such keys, your key selection process would no longer be perfectly random, and so an attacker could potentially learn some information about the plaintext just by inspecting the ciphertext and knowing that the key cannot be one that has all its characters identical.


Your confusion seems to be between DSA, the discrete signature algorithm and the Elliptic Curve variant ECDSA. The answers to the question you point to already seem to make a distinction between the two, which this answer won't re-iterate.

The key size of 256 bits is considered secure for Koblitz curves such as SECP256K1. So if used correctly the shown code is secure when it comes to the algorithms and key sizes used. Using a bad random number generator for ECDSA signatures is known to lead to catastrophic loss of key material.

Notes:

using a single-person implementation of ECC is not recommended: there is a bigger chance of implementation mistakes or side channel attacks (e.g. during the multiplication to calculate the public key or signature generation);
SECP256K1 provides somewhat less than 128 bits of security, which is currently not feasible to crack (although the bit size is slightly at the low side). But EC(DSA) is vulnerable against attacks from future quantum computers (and so is DSA).


Reverse Java random seed using 81 calls to nextInt with a bound of 4?

The $48$-bit state $s_i$ evolves per a Linear Congruential Random Number Generator, with modulus $n=2^{48}$, multiplier $a=\mathtt{5DEECE66D}_{16}$, and additive constant $b=\mathtt B_{16}$; that is $s_i=(a\cdot s_{i-1}+b)\bmod2^{48}$. We are given the OR $r_i$ of its two upper bits for $i\in[1,81]$, or equivalently the $81$ booleans $s_i\ge2^{46}$. Our goal is to find $s_0$: if the Java default generator was explicitly seeded, $s_0\oplus a$ is the low-order 48 bits of the given long seed.

The $81$ givens yield about $-81\left(\frac14\log_2(\frac14)+\frac34\log_2(\frac34)\right)\approx65.7$ bit of information, which should be typically ample to pinpoint a single $48$-bit seed.

A most brute force solution to the problem enumerates all the $s_0$ in $[0,2^{48})$, and for increasing $i$ computes the $s_i$ and eliminates a candidate $s_0$ as soon as there's a mismatch between a bit $r_i$ and the condition $s_i\ge2^{46}$. That's feasible, and particularly easy to distribute on multiple threads/CPUs/GPUs/FPGAs. The rest of this answer illustrates the NSA saying (popularized by Bruce Schneier): Attacks always get better; they never get worse.

Notice that we can compute for $z\in[-81,81]$ the $48$-bit constants $a_z$ and $b_z$ such that $s_{i+z}=(a_z\cdot s_i+b_z)\bmod2^{48}$. We have
$$\begin {align}
a_0&=1&b_0&=0\\
a_{z+1}&=a\cdot a_z\bmod2^{48}&b_{z+1}&=(a\cdot b_z+b)\bmod2^{48}\\
a_{-1}&=a^{-1}\bmod2^{48}=\mathtt{DFE05BCB1365}_{16}&b_{-1}&=a_{-1}\cdot (-b)\bmod2^{48}\\
a_{z-1}&=a_{-1}\cdot a_z\bmod2^{48}&b_{z-1}&=a_{-1}\cdot (b_z-b)\bmod2^{48}
\end{align}$$
This allows computing directly any $s_j$ from any $s_i$, by taking $z=j-i$. That's put to use in the following optimizations:

Pick an $i$ with $r_i=0$ and reorganize the search by walking $s_i$ in the interval to $[0,2^{46})$, then compute $s_0$ from $s_i$. That's a welcome gain by a factor of $4$.
We most likely¹ can pick the above $i$ such that $r_i=r_{i+1}=0$. The condition $s_{i+1}<2^{46}$ (which must hold) changes rarely when incrementing $s_i$: it holds true for about $2^{46}/a\approx2791$ consecutive values, then is false for an interval about three times longer, that we can skip, giving a speedup by a factor next to $4$.

At that stage of optimization, we explore $2^{44}$ values of $s_i$. I guesstimate² we can run faster than $2^6$ cycles/value tested on a core of a modern x64 desktop CPU. With a single $2^2$-core CPU at $2^{31}$ Hz, that would be $2^{17}$ seconds (1.5 day for the full exploration), and half that on average.

We can do better, but be warned that premature optimization is the root of all evils (Donald Knuth). We most often are able to make good use of the fact that $a_{-67}$ is small: when we can find $i,z$ with $r_i=r_{i+1}+r_{i-67}=0$, that allows getting down to $2^{42}$ values searched at cost of a further sub-division of the search sub-intervals for $s_i$ into sub-sub-intervals of width $2^{46}/a_{-67}\approx394$.

We often are able to further subdivide at least once or even twice, each time gaining another reduction by a factor of $4$ of the number of $a_i$ to test. We want to explore the usefulness of such subdivision for each $s_{i+z}$ with $r_{i+z}=0$. The better choices have the highest width $\approx2^{46}/\min(a_z,2^{48}-a_z)$ for the interval of $a_i$ with $s_{i+z}<2^{46}$. In particular, we might be able to use that $2^{46}/a_{19}\approx60$ or $2^{46}/(2^{48}-a_{-12})\approx60$. But we'll quickly get hit by the law of diminishing returns.

Update: There must be better methods. Something at least quite close was studied by Alan M. Frieze, Johan Hastad, Ravi Kannan, Jeffrey C. Lagarias, and Adi Shamir, Reconstructing Truncated Integer Variables Satisfying Linear Congruences, in SIAM Journal on Computing, 1988.

¹ In the very unlikely case (I'm not even sure it is possible) that there's no $i$ with $r_i=r_{i+1}=0$, the simplest of several possible fallbacks is to pick $i$ and $z$ with $r_i=r_{i+z}=0$ and the smallest $a_z$ possible; that will often be $z=-67$ or $z=19$. The reduction in number of $s_i$ scanned is the same, but we'll more often change sub-intervals.

² When $s_i$ increases in a sub-interval, we want to quickly update at least one $s_j$ that we'll always test. An update of $s_j$ cost one addition of $a_{j-i}$ and a mask³. We'll pick $j$ with $r_j=0$, which will leave only one out of $4$ values of $s_i$ needing more scrutiny. For these, we sequentially compute and test the many other $s_{i+z}$ that we could still have wrong, of course stopping at the first mismatch and first testing $z$ with $r_{i+z}=0$. Each additional $z$ requires a multiplication by $a_z$. If that's too costly, we'll want to maintain one or a few more $s_k$ by addition.

³ A simple micro-optimization maintains $2^{16}s_i$ over a $64$-bit variable, saving the masking. The comparison becomes against $2^{62}$, also implementable as a $62$-bit right shift and a test for zero.


For a hash over a finite space without size reduction, is a public permutation sufficient?

Lamport's signature requires a hash function $H$ that is a one-way function. So your question is whether $H(x) = x \oplus P(x)$ is one-way when $P$ is a public permutation.

I will assume that $P$ is a public random permutation (a.k.a., an ideal permutation). In that case, yes the construction is one-way. It is very closely related to the Matyas-Meyer-Oseas (MMO) construction of a collision-resistant hash function from an ideal block cipher.

To hash a sequence of blocks $m_1 m_2 \cdots$, the MMO construction works by iterating the function $s \gets E(s, m_i) \oplus m_i$, where $s$ is the continuously updating internal state and $E$ is an ideal cipher. If you could find inverses in $H(x) = x \oplus P(x)$, for a public permutation $P$, then you could easily find collisions (even second preimages) in an MMO hash. Since MMO hash is provably secure in the ideal cipher model, this impiles that $H$ is one-way:

Consider a 2-block message $m_1 m_2$ and its hash which is computed as:

$s_1 = E(s_0, m_1) \oplus m_1$
$s_2 = E(s_1, m_2) \oplus m_2$

To find another message that collides with this one, pick $m_1' \ne m_1$ arbitrarily and set:

$s'_2 = E(s_0, m_1') \oplus m'_1$

If you had an $m'_2$ that satisifed

$s_2 = E(s'_1, m_2') \oplus m'_2$

then $m'_1 m'_2$ would be the desired collision. Note that everything in this expression is known except $m'_2$, and so $E(s'_1, \cdot)$ is a public random permutation. So the task reduces to that of finding preimages of a function of the form $x \mapsto P(x) \oplus x$, where $P(x) = E(s'_2,x)$.


How to perfrom modular division while numerator is lesser than the denominator?

I'll assume we are working modulo $p$, which most likely is some large prime. When evaluating $S={P_y-Q_y\over P_x-Q_x}$, one really is finding a representative integer of the residue class of the equivalence relation modulo $p$; that is, the result is defined within addition or subtraction of $p$ any number of times.

The same holds for numerator $P_y-Q_y$ and denominator $P_x-Q_x$: addition or subtraction of $p$ to these quantities, any number of times, is immaterial. That makes comparing numerator and denominator moot; and even ambiguously defined: when working modulo 7, we can't tell which is the smaller of 2 or 6; that's because we could as well be comparing 2 to -1, or 9 to 6.

As long as $P_x-Q_x$ is not a multiple of $p$, one evaluates $S={P_y-Q_y\over P_x-Q_x}$ without considering a comparison of numerator and denominator. The result is, depending on definition

any integer $S$ such that $S\cdot(P_x-Q_x)-(P_y-Q_y)$ is a multiple of $p$;
or perhaps the single non-negative integer $S$ less than $p$ with this property; this would be obtained by "reducing modulo $p$" some $S$ with this property; that is:

if $S$ is negative, change $S$ to $S+p\cdot\lfloor{p-1-S\over p}\rfloor$, where $\lfloor{p-1-S\over p}\rfloor$ is the quotient of the Euclidian division of the positive integer $p-1-S$ by the positive integer $p$, and $\cdot$ stands for ordinary multiplication;
otherwise, change $S$ to $S-p\cdot\lfloor{S\over p}\rfloor$ (or equivalently, change $S$ to the remainder of the Euclidian division of $S$ by $p$).

If we stick to the convention that $S$ and intermediary results are kept as non-negative integers less than $p$ (or, equivalently, as kept reduced modulo $p$), the evaluation of $S={P_y-Q_y\over P_x-Q_x}$ could go:

evaluate the denominator $U=P_x-Q_x$, reducing the result modulo $p$;
abort if that's zero;
compute the modular inverse $I$ of $U$ modulo $p$ using the extended Euclidian algorithm, reducing the result modulo $p$ ($I$ is well defined if $p$ is a prime);
evaluate the numerator $V=P_y-Q_y$, reducing the result modulo $p$;
evaluate $S=I\cdot V$, and reduce the result modulo $p$.

The same applies for $S$ as used in point doubling, except for what numerator and denominator are (the formula to be used will depend on the curve).


Which keys are necessary to decrypt Application data in a SSL connection?

To simply decrypt the data, the keys that were used to encrypt it are all you need.

However without the MAC keys you won't be able to verify the integrity of a message, so you won't be able to tell if the data you have decrypted is the same as what was sent (or even who sent it).

If you're debugging on a trusted local network then that might not be too important.


Explanation of vector in Visual Cryptography

This is string notation: $J_i^0=0^{i-1}10^{k-i}$ means i-1 consecutive 0's followed by a 1 (we don't write $1^1$) which is then followed by k-i consecutive 0's. So $0^{3}10^{4}$ is $00010000$.

As for $S^t[i,x]=\langle J_i^t,x\rangle$, with $t\in \{0,1\}$ this is an inner product of $J_i^t$ with $x=(x_1,\ldots,x_k) \in \{0,1\}^k$ so in general $S^t[i,x]=x_i$ (only the 1 component in $J_i^0$ picks up a nontrivial value. Thus $S^0[2,x]=0\times x_1+1\times x_2+0\times x_3=x_2$ and $S^0[2,101]=0,$ while $S^0[2,010]=1.$ I agree it is quite cumbersome.

Generally, a good idea is to try to find "slides" as opposed to papers, where examples are usually given to make notations clear.


FIPS 140-2 only certifies cryptographic modules, not entire systems. So, to tell if your system is 140-2 compliant, it must be using a 140-2 certified module. NIST publishes a list of all FIPS 140-2 certified cryptographic modules.

It is important to remember, though, that 140-2 certification does not certify that the module is used in a secure manner. From the FIPS 140-2 document:

  Similarly, the use of a validated cryptographic module in a computer or telecommunications system is not sufficient to ensure the security of the overall system.

Looking over the document, I don't see anything on specific key sizes. It discusses key management, including key storage. So you'd have to make sure keys are stored properly. I don't see anything in the document about requirements on the data which is to be encrypted. That makes sense though as you would want your module to be data agnostic.

So, there is no way to look at an encrypted file and tell if it is FIPS 140-2 compliant. You would have to look at the module that did the encrypting.


Is it safe to combine System.Random with cryptographically secure pseudo-random number generators?

Yes, if you XOR any values with a secure random numbers, you end up with secure random numbers.

You can easily see this by assuming the insecure random number is a constant instead. It only changes what the numbers are, it does not affect their relative probabilities.


Can an adversary distinguish a private key from a pseudo-random string of the same length?

Usually choosing a safe password and standard parameter for the PBKDF2 key derivation would be enough protect your cipher. If PBKDF2 is correctly used, the symmetric key you get as output is well generated and attacking the ciphertext is infeasible.

Protecting a private key as you're doing is a standard operation, usually the password is used (in PBKDF2) to generate a symmetric key which is used with a symetric algorithm (let's say AES) to protect your precious private key.
AES is supposed to be secure even if an attacker is given access to a decryption oracle (i.e.: it can get decryption of every ciphertext he wish but yours, the challenge). So modifiing the plaintext (stripping the header) would not improve the security level.

After your edit.
Let's imagine that someone saw almost all your password while you were typing it or know that it is included in a relatively small set.

You said that you would strip the "-----BEGIN RSA PRIVATE KEY-----" string, that means that the key is in PKCS#1 standard, so what you keep is a base64 encoded string corresponding the following DER structure:

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

(source)

So, an attacker could try to check for the value of $e$ (usually a standard value among 2 or 3) or check if $p \times q = n$, or ...
So even if, in theory an RSA key is just a couple of integers, it is usually stored in a well known structure helping the attacker to recognize what he has found.


A more concrete answer for the data observed from OpenSSL:

naive bignum multiplication is $O(n^2)$ and so is modular multiplication (which is what is actually needed here). However OpenSSL (for these sizes) uses Karatsuba multiplication which lowers this to roughly $O(n^{1.6})$ (thanks frgieu) and also Montgomery reduction which is only a constant factor.
for publickey the number of multiplications is fixed (and small) so the total operation is the same big-O as one multiplication.
for privatekey the number of multiplications also scales with $n$ giving a total roughly $O(n^{2.6})$ . OpenSSL also uses CRT which halves the size of the multiplications and doubles their number (plus wrap-up and sanity check), and windowing which reduces the number of multiplications by about 1/3, but those are both constant factors and ignored for big-O.

OpenSSL doesn't 1.1.1 does implement the imprecisely named 'multi-prime' form of PKCS1, which changes the privatekey benefit from CRT, but to get speed results for it you must specify -primes N and a sufficiently large (total) size.


What's different between ground setting and ring set in the Enigma machine?

Terms
As stated on Wikipedia:

Ring settings (Ringstellung) – the position of each alphabet ring relative to its rotor wiring.
Starting position of the rotors (Grundstellung) – chosen by the operator, should be different for each message.

Functions
The ring setting changes the output letter of a rotor. A rotor has a fixed permutation installed (by the wiring) as seen here, i.e. one rotor would encrypt the letter A to the letter G. After one encryption the rotor would turn and the next wiring comes into effect and the new encryption of the letter A would now be encrypted to the letter C.
With the ring setting you could additionally change this fixed permutation of the rotor, i.e. with a ring setting of B (a.k.a. 02) it would change the output of the rotor. It functions like a caesar cipher. Using the example above with the ring setting of B would change the letter A to the letter H (because B is mapped to A (difference of 1) H is mapped to G).


See this explanation. The 0x10 signature (typically belonging to a different individual) is applied to one's master/primary key, not to 0x18 subkey signature packets used for signing, encrypting, and authenticating.
Remember, CA responsibilities are decentralized with the PGP Web of Trust and the one's master/primary key can be used to sign other people's master/primary keys that also act as a reputation. By signing other people's master key(s), those people can revoke and re-issue subkeys as needed (with their reputation) without the involvement of those that have applied 0x10 signatures.
With more recent gpg code, the signing subkey will have a 0x19 backsignature when created.


What is an extremely basic asymmetric cipher that I can present at the pub?

I'm trying to explain the basics of Bitcoin to my parents.

If this is your objective, I would argue that it is not necessary to go in-depth into asymmetric encryption/signing. The basic mechanics of Bitcoin, or blockchain systems in general, are easily, (and probably best) explained on a very abstract level, i.e. it is a decentralised solution to asset transfers and consensus building, and so forth.

As for the signatures, you could say that they serve as transaction authorisation so that only the owner of tokens is able to spend, but everyone can verify the signature.

  What's an extremely simple asymmetric cipher I can use as an example?

If for some reason, your audience is really interested in learning how it works on a more technical level, I would avoid RSA and the effort of doing the transfer from encryption to digital signatures later. In this case, you might simply want to stick to DSA (the classical, non-elliptic curve version), and use small numbers to talk them through step by step.

Not knowing your parents/friends at the pub, I would have my doubts though that they care about the hardness of discrete logarithm problems or finite group operations, and from my experience with similar settings, I advise you to start with the general concepts, and then go into the exact algorithms if required.


Note that encrypting "the message with a private key where the readers decrypt it with my public key"

is usually insecure, although there are signatures with message recovery that are presumably secure.

The canonical short signature scheme is BLS.

The main alternative that I'm aware of is the random-oracle part of this paper,

although that scheme cannot safely sign a large number of messages.


Is it possible to make two files with the same size and the same MD5 and CRC32?

It's straight-forward.

First off, we start with Joux's multicollision attack (PDF) to generate $2^{33}$ different same-sized files with the same MD5.  Here's how that works; the MD5 collision attack works by starting with an internal MD5 state $S$, and finding two different blocks $B_0, B_1$ such that, with the MD5 compression function, $\text{MD5Compress}( S, B_0 ) = \text{MD5Compress}( S, B_1 )$.  Finding such a $B_0, B_1$ is fairly easy.

What Joux's attack is ask us to do that 33 times to succesive states; and so we have $2^{33}$ different sequences (as there are $2^{33}$ different ways of selecting $B_0, B_1$ values) that all hash to the same final value.

Once we have that, we know that there exists a pair of files with the same CRC32 value (and actually, we don't need to search through them all, with CRC32, we can find such a pair with linear algebra)


What is the computational cost of a public key certificate signature verification?

It very much depends on the asymmetric cryptosystem used, and its parameters.

With RSA using small public exponent (which is typical), the cost of verifying a certificate (knowing the signer's public key) is dominated by a few (typically $17$ or $2$) modular multiplications (for $e=2^{16}+1$ or $e=3$) with arguments of the size of the public modulus. With the Rabin cryptosystem, that goes down to a single modular multiplication (or even less with Bernstein's lifting). With the most classical algorithm, one modular multiplication for $n$-bit public modulus costs $\approx 2\cdot(n/w)^2$ multiplication-and-addition with $w$-bit multiplicands and $(2\cdot w)$-bit result. That is often low enough for practical use even on a modest 8-bit CPU  (e.g. about $70.000$ multiply-and-add for RSA with $n=1024$-bit modulus, $e=3$, $w=8$).

Most other asymmetric cryptosystems require significantly more work from the verifier, for equivalent security. They are typically implemented using a 32-bit CPU or/and a cryptographic co-processor.

For example, with DSA as defined in section 4 of FIPS186-3, an $n$-bit modulus, and a $h$-bit hash, the cost of verifying a certificate is dominated by two modular exponentiations with $h$-bit exponents and $n$-bit modulus, each using $\approx 1.5\cdot h$ modular multiplications with $n$-bit public modulus (assuming a common, basic exponentiation algorithm). With $h=160$ and $n=1024$ (the minimum specified), that's over 200 times more work than for 1024-bit RSA with $e=3$ (which security is lower, but in the same ballpark).


Asmuth-Bloom Secret Sharing $m_0$ public?

According to Dragan&Tiplea,On the Asymptotic Idealness of the
Asmuth-Bloom Threshold Secret Sharing Scheme $m_0$ is a public parameter.
The scheme itself does not require $m_0$ to be kept secret. However, by keeping it secret you could eliminiate the possibility to get a probabilistic distribution of secrets as explained here but if $m_0$ for some reason is lost, the secret is not recoverable, which kind of defeats the purpose (or parts of it) of a secret sharing scheme.


Group in the context of elliptic curve crypto

Short answer: the definition you're using (and, in particular, the notation in it) is specific to multiplicative groups modulo $p$.  It makes no sense for elliptic curves, or for most other kinds of groups over which the discrete logarithm problem can be defined.  In particular, for elliptic curves, there is no prime modulus $p$.

(Well, OK, for the elliptic curves used in cryptography, there is a prime modulus involved in the definition of the finite field over which the elliptic curve itself is defined.  The size of this prime depends on the type of finite field used — it can be anything from $2$ up to the size of the field itself — and is only very indirectly relevant to the hardness of the discrete logarithm problem.)

Longer answer: In mathematics, a group is simply any set $G$ equipped with some binary operator $\star$ that satisfies the following properties:

Closure: For every $a, b \in G$, the value $a \star b$ is defined and belongs to $G$.
Associativity: The equation $(a \star b) \star c = a \star (b \star c)$ holds for every $a, b, c \in G$.
Identity: There exists an identity element $\epsilon \in G$ such that $\epsilon \star a = a \star \epsilon = a$ holds for every $a \in G$.
Invertibility: For every $a \in G$ there exists another element $b \in G$ (called the group inverse of $a$) such that $a \star b = b \star a = \epsilon$.

If these properties seem fairly broad and abstract, that's because they are.  Indeed, math is full of things that satisfy the definition of a group.  For a few examples:

The integers $\Bbb Z = \{…, -2, -1, 0, 1, 2, …\}$ equipped with the operation $+$ (i.e. addition) form a group.  The identity element is $0$ and the inverse of $a$ is $-a$.
The positive rational numbers $\Bbb Q^+$ equipped with the operation $·$ (i.e. multiplication) also form a group.  The identity element is $1$, and the inverse of $a$ is $1/a$.
For any set $S$, the set of invertible functions from $S$ to $S$ form a group, with function composition ($\circ$) as the group operator.  This group is known as the symmetric group of $S$.
For any $n > 0$, the numbers $\{0, …, n-1\}$ equipped with the operation $+_n$ defined as $$a +_n b = (a + b) \bmod n = \begin{cases}a + b & \text{if }a + b < n, \\ a + b - n & \text{otherwise} \end{cases}$$ also form a group.  The identity is still $0$, but the inverse of $a \ne 0$ is now $n - a$.  This group is isomorphic to the (additive) group of integers modulo $n$, and indeed is one way to define that group (although a more commonly used definition uses congruence classes instead).
For any prime $p$, the numbers $\{1, …, p-1\}$ equipped with the operation $·_p$ defined as $$a ·_p b = ab \bmod p = ab - kp,$$ where $k$ is the largest integer such that $kp \le ab$, also form a group.  The identity is $1$, and the inverse of any element $a$ can be calculated e.g. using the extended Euclidean algorithm.  This group is isomorphic to (and again, under some definitions, the same as) the multiplicative group of integers modulo $p$.

There are, however, plenty of other ways to form groups as well.  For example, for any elliptic curve, it's possible to define a binary operator that makes the set of points on the curve (including the "point at infinity") into a group.  The definition is somewhat complicated, so I won't attempt to summarize it here, but it can be shown to satisfy all the properties required of a group.

Now, for any group $G$ with the group operation $\star$, we can define an "exponentiation" operator $\uparrow$ that maps a group element $g \in G$ and a non-negative integer $k \in \Bbb N$ into the group element $$g \uparrow k = \underbrace{g \star g \star … \star g}_{k \text{ times}}.$$ (In particular, $g \uparrow 0$ is defined to be the group identity element $\epsilon$.)

For any group element $g \in G$, the set $$g^{\Bbb N} = \{\epsilon, g, g \star g, g \star g \star g, …\} = \{k \in \Bbb N: g \uparrow k\}$$ of powers of $g$ forms a subgroup of $G$.  This is called the subgroup generated by $g$, and also written $\langle g \rangle$.  (For some groups, it's even possible to find a $g \in G$ such that $\langle g \rangle = G$, i.e. $g$ generates the entire group $G$.)

For a given generator $g \in G$ and an arbitrary element $a$ of the subgroup $\langle g \rangle \subset G$ generated by $g$, it's then possible to ask the question: what is the smallest (or even any) number $k \in \Bbb N$ such that $g \uparrow k = a$?  Such a number $k$ is known as the discrete logarithm of $a$ with respect to $g$.

Now, for some groups, computing the discrete logarithm is very easy.  For example, if $G = \Bbb Z$ is the additive group of integers, then $g \uparrow k = kg$, and the discrete logarithm of $a$ with respect to $g \ne 0$ is simply $a \mathbin/ g$.  The additive group of integers modulo $n$ is not much harder: calculating the discrete logarithm of $a$ there just requires solving the modular congruence $a \equiv kg \pmod n$, which can be done using the aforementioned extended Euclidean algorithm.

However, for other groups, no easy or efficient way of calculating discrete logarithms is known.  The multiplicative groups of integers modulo large primes $p$ are one example of a class of such groups; elliptic curves (over a finite field) are another.

For cryptography, the main advantage of choosing elliptic curves over multiplicative groups of integers is that the most efficient known algorithms for finding discrete logarithms over elliptic curves are even less efficient than those for multiplicative groups of integers.  In other words, this means that we can use smaller groups (and thus shorter keys etc.) for the same conjectured level of security.

Of course, technically, we don't know that the discrete logarithm problem is actually hard over either kind of groups, and that there isn't some magic algorithm to solve it efficiently that we just haven't found yet.  But a lot of smart people have studied this problem for both kinds of groups, trying to find such an algorithm, and so far (at least as far as publicly available academic literature goes) they haven't really found one.  And so far, of the two kinds of groups, elliptic curves seem to be the harder nut to crack.


Rounding function used in Saber Key Exchange

If $p$ and $q$ are powers of two, as in Saber, then multiplying and diving by $p$ and $q$ amounts to simple bit shift operations.
In Saber, $p = 2^{10}$ and $q = 2^{13}$. Thus, $p/q = 1/2^3$ and $x/8$ can be computed by a right-shift of 3 bits. Using the $bits$ notation, $\frac{p}{q}x = bits(x, \log(p/q), \log p)$.
But we can do better, and also compute the rounding operation in terms of the bits function. Right-shifting by some bits is equivalent to a floor operation. We can express rounding in terms of flooring, with $\lfloor x \rceil = \lfloor x + 1/2\rfloor$ (where $\lfloor x \rceil$ denotes rounding to the closest integer, and $\lfloor x \rfloor$ is the integer floor of $x$).
The same reasoning can be applied here. We want to add $1/2$ before the flooring operation. Since we are dividing everything by $8$, if we add $4$ to the original value $x$, we obtain $p/q( x + 4) = x/8 + 1/2$, as desired.
Hence, $\left\lfloor \frac{p}{q} x \right\rceil = bits(x + (\log p)/2, \log(p/q), \log p)$.
Note that this works only because $p$ and $q$ are powers of two. If Saber had chosen prime moduli, the scaling and rounding operations would be more involved than a simple addition and bitshift operation.


AES, is this method to say "The password you entered is wrong" secure?

Is it secure to encrypt with AES CFB mode a plaintext for which the first bytes are known (e.g. %PDF-1.5 for a PDF document)

Yes. Known (and even chosen) plaintext is a standard assumption in any moder cipher, including AES-CFB (and CTR, CBC, OFB...). It does not "give too much information to an attacker", and it is not "bad to encrypt documents with known headers with AES".

True, having a known plaintext at start to allow a test of the password makes password search a little simpler. But only a little, and we customarily ignore that little. One reason (stated in the question) is that actual plaintext typically contains recognizable sequences. And when not, it is typically compressible, when the incorrect plaintext obtained for the wrong password is not, which allows automated recognition of having the correct password anyway.

Another problem is that CFB is weak at detecting message alteration. Using a modern, authenticated encryption mode such as AES-GCM would solve that. It turns out this is readily available in PyCryptodome's Crypto.Cipher.

However, there is a different, serious problem with the code !

It has poor security because the Crypto.Hash.SHA256.new(b'password1') part of it builds the AES key from a password using a standard cryptographic hash (SHA-256). That conversion from password to key is fast, and that allows to test passwords at high speed. This makes the system very vulnerable to password crackers (which essentially test plausible passwords at high speed, including short ones, and those from or inspired from a dictionary of common passwords/words).

  I use a random Initialization Vector, so doesn't this help (against the above problem)?

No, because that does not appreciably slow down testing a password.

That issue has plagued password-based encryption since the origin of that, and progress in computing (faster CPUs, GPUs, FPGAs, ASICs..) directly worsen it, to the point that nowadays, very practically, if users can memorize a password, and a standard hash is used to turn it into a key, then the system is very weak (much to the pleasure of Three Letters Agencies and more casual/greedy attackers, which routinely use password crackers, and succeed).

In the 1990 we started to get iterated password-to-key derivation functions, like PBKDF2 of RFC 2898, which essentially slow down conversion from password to key by requiring many hashes. Initially "many" was at least a thousand, but nowadays we'd need hundred thousands just to keep with the progress of technology. Until about 2015, that was the industrial state of the art (what your mobile phone or computer used).

We are slowly moving to memory-intensive (or memory-hard) password-to-key functions. The pioneer was bcrypt (which almost accidentally required sizable memory), then scrypt (theorizing the use of large memory and multiple CPUs when available). The Password Hashing Competition gave us Argon2 (which unfortunately fails to catch AFAIK, perhaps because it's complex and has many options). There is also Balloon (which does not catch either, perhaps because it was not in the PHC).

In any case, it is nowadays inadequate and grossly incompetent to turn a password into an encryption key using anything lesser than an iterated hash with many thousand iterations; and it is highly recommendable to additionally make that process require sizable memory.

  Could you include an example of code with which you would replace AES.new(SHA256.new(b'password1').digest(), AES.MODE_CFB, iv).encrypt(p) to make use of another hash?

Crypto.SE is not for code recommendations; and we need another kind of hash. One variously called entropy-stretching key derivation function, password-based hash, or some mix of that. It must be purposely as slow as possible for the attacker, yet fast enough for the application. Also, it will have a salt input, and it is a good idea to feed that with the IV/nonce, of at least server+user ID (this was missing in an earlier version of this answer).

The good news is that we no longer have to choose between several evils (see earlier version of this answer): PyCryptodome now has entropy-stretching key derivation functions, including scrypt which is memory-hard. This is the obvious choice. Be sure to up the N parameter as much as bearable.

Sample Python code there, illustrating how PyCryptodome's scrypt can turn a password into a key of AES-GCM, with GCM's nounce also scrypt's salt.

Caveat: nothing in this post should be construed as an endorsement of PyCryptodome's security.