Is it possible to generate backdoored DH parameters?

A trapdoor in a discrete log group was first suggested in 1992 by Daniel M. Gordon[1] in response to the recently proposal by NIST for the Digital Signature Standard (among hundreds of other responses[2] including an objection to the now-infamous random generation of the per-signature secret).  Though the computational cost was too high for an academic researcher to demonstrate it at the time, Gordon did suggest alleviating the concerns by using what we would today call a semi-rigid procedure for choosing the primes.

Fast-forward to 2016, when Fried, Gaudry, Heninger, and Thomé dusted off Gordon's algorithm and applied it in practice[3] to spend:

12 core-hours choose a 1024-bit DSA prime $p$, with a 160-bit prime factor $q$ of $p - 1$, with an SNFS polynomial $f$ admitting…
a few hundred core years (spread across a few thousand cores for a couple of months on an academic cluster) of precomputation in order to enable…
a handful of core-days to compute each discrete log.

The paper [3] is worth reading for more technical details and historical background.  There are some caveats:

The experiment produced a group for DSA, a Schnorr group with a 160-bit prime subgroup, not a safe prime for DH to avoid Lim–Lee active small-subgroup attacks[4] which are not relevant in signature applications.  It's not immediately clear to me whether the technique would work to find a safe prime with a trapdoor: if nothing else, the arithmetic modulo a (say) 2047-bit $q$ would cost a dozen times what the arithmetic modulo a 160-bit $q$.

Counterpoint:  But there have been Schnorr groups inexplicably documented for use with DH, in RFC 5114.  The paper [3] reports systems in the wild using primes with an obvious SNFS polynomial, like $2^{1024} - 1093337$.  For years socat used a composite modulus[5].  And maybe a more careful reading of the costs than I have done would show that searching for a safe prime is not all that much costlier than a Schnorr group as demonstrated.
Obviously, a 1024-bit modulus is too small by today's standards: it has been considered plausible for some years now that well-funded governments or corporations could mount a GNFS discrete log computation in a group with a 1024-bit modulus.

Counterpoint: But it shouldn't be within the reach of an academic cluster!  If the trapdoor for this 1024-bit modulus is within the reach of an academic cluster today, is a trapdoor for a 2048-bit modulus within the reach of a major government or corporation?

So, while it is likely outside your budget to generate a 2048-bit safe prime with a hidden SNFS back door in the privacy of your own living room, you should definitely raise a lot of eyebrows at anyone suggesting to use DH primes other than the semi-rigid RFC 3526 ones.

Or just use elliptic curve DH, particularly X25519.


Using ePassport with Active/Chip Authentication to sign documents

Active Authentication (AA henceforth) relies on RSA or ECDSA and allows you to sign data. However, as our is not meant to sign data you should not use it for that purpose.

First of all,  the only PKI that verifies the public key is that used for passive authentication of the passport - so you probably have to set up a separate PKI for it to be useful. Passive authentication simply embeds the public key in a "data group" which is then authenticated by a signature set by a country's signing certificate. However, the public key used is not in a certificate itself.

Second, the signing is used for passport authentication only and therefore does not require user confirmation / commitment such as  entering a PIN. Hence any reader with access to the contents of the passport is allowed access to the signing procedure, so having a signature does not prove user consent in any way.

The old AA algorithm uses the ISO/IEC 9796-2 signature scheme 1 giving message recovery. I've never been able to find out why (and I was directly involved), probably it was copied from some banking standard. Newer ones may use PSS as well. If 9796 is used then you might not be able to find too many parties that are able to verify the generated signature. AA is performed using the INTERNAL AUTHENTICATE command and is performed over RND.IFD which is specified for 8 bytes only, severely limiting input data.

If the passport still uses AA then you might also have a problem with the size of the keys. If you want to sign something for non-repudiation then you may want to have an RSA key size of 3072 bits or above. There aren't many smart cards that have the hardware for such large key sizes (at least not if you want to fit the other tens of pages of protocol spec in there as well).

In principle AA may use ECDSA, but it makes more sense for the country to use CA if that's the case. Finally, there may also be passports that use PACE-CAM, where the CA internal authentication is embedded in the initial authentication procedure.

For Chip Authentication (CA) the signature generation was considered a threat to the privacy of the user. A country could for instance use it to sign time and coordinates to create tracking.  That's why CA is based on Diffie-Hellman key agreement rather than a signature generation function. Unfortunately, that also makes it unavailable for signature generation.

Conclusion: it is next to impossible to use AA and CA for digital signatures  used for non-repudiation; AA was not designed to support such use case and CA was deliberately designed to avoid the use case. AA could be used to sign 8 bytes without user consent, but that's about it.

Besides the technological barriers, I'd certainly consider using AA or CA for anything other than (national) border control morally wrong. It should not be used even with consent, as any advantage that is gained can also be used to pressure people into using a passport for what it is not designed to do.


How fast would a polynomial time factoring algorithm compute?

I know an algorithm that runs in polynomial time would be able to break an RSA key pair "quickly". But how quickly is "quickly"?

No way to say, it might be microseconds, and it might be large multiplies of the age of the universe.

When we say that an algorithm runs in polynomial time, we're not saying anything about how fast the algorithm runs given any particular input.  Instead, what we're saying that, as we give the algorithm increasingly large inputs, the time it takes doesn't increase that quickly.

How polynomial time is generally expressed is that there are values $c, e$ such that, given a problem of size $N$ (and in the factorization case, $N$ would be the number of bits in the RSA key), the algorithm takes time less than $cN^e$.  Now, there are no limits on how big $c$ and $e$ might be, and so this doesn't give any limits on how much time a specific instance might take.

On the other hand, for all known factorization algorithms, this is not true -- no matter how large values we select for $c$ and $e$, we can find problem sizes $N$ large enough that the algorithm takes more than $cN^e$ time; hence saying that an algorithm is "polytime" does say something -- it just doesn't say what you're hoping it did.


blinding a hash vs. sending the hash directly

You are wrong.  The purpose is to prevent linking the signing operation with the verification operation.

For instance, suppose that I have to identify myself when I ask B to sign the thing (maybe B charges me to create a signature; for instance, when blind signatures are used for e-cash, B is the bank, and B charges money to sign anything, since validly-signed coins are money).  Now suppose I want to be able to present the signature later so someone else can verify that the signature is valid.  The security goal for blind signatures is that I don't want the verifier to be able to collaborate with B to identify me.

If it is possible to link the signature (presented during verification stage) with the value presented during the signing step, then that defeats the security goal.

If you ask B to sign an unblinded hash, then security falls apart.  The verifier (who sees the signature) can pull the hash out of the signature, then collude with B to match that up to the person who originally presented the hash for signing.  In that way, the verifier could identify you -- something that's no longer possible if you use blind signatures and only send the blinded hash to B.  In particular, given a signature, it is very easy to recover the hash of the message that is being signed: part of the signature verification step involves computing this hash.

So, just sending the unblinded hash isn't good enough.  You need to blind the hash before sending it to B for B to sign, in the applications where blind signatures are sued.


Multiple passwords per key with any allowing decryption

You can do this by generating a (random) encryption key for the data and then encrypting that key separately with each of the passwords, using some password-based encryption.

To decrypt the user can use any of the passwords to decrypt the encryption key, then use that to decrypt the actual data. If the password-based encryption used is authenticated encryption, the decrypter can decrypt each of the encrypted keys and use the one where the authentication checks out.


SHA-256 Hash over multiple SHA-256 Hashes

Yes, this is fine for verifying that the file contents match the original. You are basically using a hash list. As long as SHA-256 is collision resistant, there is no way to find a hash that would be ambiguous and refer to two or more known file sets.

In addition to the potential issues mentioned in the comments, storing just the aggregate hash value leaves you with no way to figure out which file failed to match. That is why it is common to store the intermediate hashes as well to see which file would have to be e.g. downloaded again.


In cryptography, strong primes have been used (with various definitions of that) for RSA, in order to defeat the factorization of the public modulus by Pollard's p-1 and p+1 algorithms, and various other attacks. For this reason, there is no list of standard large strong primes, for that would defeat the purpose in RSA, where the prime factors of the public modulus must be secret.

The Diffie-Hellman key exchange often uses safe primes, which is a prime $p$ such that $\displaystyle q=\frac{p−1}2$ is also a prime. The answer linked to in the question accidentally misuses the word strong prime where safe prime is meant, as noted in comment.

Standard safe primes for use in DH are in RFC 3526. These intentionally use the generator $g=2$ for the subgroup of prime order $\displaystyle q=\frac{p−1}2$. Except perhaps for the 1536-bit one, they are considered large enough to be safe for use right now.

  With (safe prime $p$), can I use any number between $2$ and $p−2$ and be guaranteed to have an order of either $p−1$ or $\displaystyle\frac{p−1}2$ ?

Yes. Argument: the order of a subgroup always divides the order of the group, which is $p-1$ for prime $p$. When further $p$ is a safe prime, the order of the group is $2\,q$ with $q$ prime, thus the order of any $g$ is one of $1$, $2$, $q$ or $2q$. Only $1$ has order $1$ and only $p-1$ has order $2$.

But as noted in comment, there is no good reason not to use the generator coming with the prime.


What is more efficient, pairing based cryptography or non pairing based cryptography?

If you can express your operation well using plain groups, go with normal elliptic curves. But the pairing adds additional mathematical structure, which enables new algorithms.

Some examples:

BLS signatures

They're verifiably deterministic and small, 2x security level, instead of 3 to 4 times, with DSA/Schnorr/ElGamal signatures.

These  use the pairing as a decisional Diffie-Hellman oracle.
Identity based encryption using the Boneh–Franklin scheme.


What is the purpose of implementing cryptographic algorithms in a token?

In practice, “secrets do not leave the token” is not beneficial.

Ouch, I think I would rather like to know where my keys are. This is about the same as saying that you don't care if your house keys got copied or not.

For example, a banking application. This program is not able to execute on a token since tokens have insufficient UI. Hence this program will execute on a UI device to which the token is attached.

In PKCS#11 you can still have key specific PIN or passwords. This is especially important for transactions which is what you are referring to here.
Sometimes additional security measures such as counters are also present. If those are not depleted they can at least be used to check if the key was used unexpectedly. In software the attacker could just reset the counter at will. Cars also have odometer's that are deliberately hard to compromise.
That all said, yes, if an attacker has full access to the keys within the token over extended periods of time then the token is virtually useless.

If cryptographic algorithms are implemented in the token, the attacker can execute any operation that the user can as long as the token is attached.

Absolutely, and there is a balance between usability and security here, which is hard to maintain. E.g. you can setup a HSM in such a way that a person has to login into each session. Then again, you might have some trouble finding a human in the middle of the night that is able to do this upon a sudden restart of a server. This would be fine for personal tokens and smart cards.
Login procedures can also be protected by additional counter measures such as number of logins or delays between password verification checks.

If cryptographic algorithms are implemented in the UI device, the attacker posesses the user's secrets.

There are things like white box cryptography of course. And then there are certainly levels of access. Even in software you can have a secure system run at a different level than the user process. However, in that case you cannot easily protect against side channel attacks on processor usage. So this actually advocates for a hardware device such as a token.

AFAIK, PKCS #11 does not allow backups. If you store all your secrets in a token, it will be valuable not only to attackers, but to you too.

PKCS#11 is a generic token interface. However, most if not all HSM's have proprietary backup mechanisms and / or extensions of the PKCS#11 interface to deal with backups.
Other tokens such as smart cards basically require you to request a new smart card or token - which is fine for signature generation (authentication, non-repudiation). It is bit more tricky when it comes to decryption for obvious reasons.

Restricted set of cryptographic algorithms. Only algorithms implemented in a token.

Absolutely, and this can be a nuisance. And if you enable FIPS mode then only FIPS algorithms will be available. HSM's can receive (signed) updates though. And generally we don't use tokens for research, we tend to use them for standardized algorithms.
Some HSM's actually allow you to run restricted programs as well - although this may have interesting effects on certification of the hardware.

More complex hardware interface and API.

That's debatable. I think the PKCS#11 interface is well specified and it is about the only standardized, generic crypto API out there. It may not suite your language / runtime model perfectly, but the fact that you can use it from a myriad of languages and runtimes has a lot going for it. Many languages contain wrapper libraries around PKCS#11, which are then wrapped object oriented wrappers where required.


Here are some advantages and disadvantages for each of the three classes of MACs, which I know about:

Based on block cipher

There are constructions where the security of the MAC is proven in terms of the security definition of a block cipher. This means as long as the block cipher is secure, the MAC will be secure.

There are constructions where encryption and MAC can be computed with almost no extra CPU cost compared to only encrypting.

Based on cryptographic hash (HMAC)

Assuming the underlying hash is secure, a HMAC guarantees that even an adversary who knows the key cannot produce two different messages for which the same HMAC value would be valid. Neither could an adversary produce a HMAC value which would be valid with two different keys.

One disadvantage is that security of HMAC cannot be proven based on the usual properties regarding collisions of the underlying hash. There could exist a secure cryptographic hash which would lead to an insecure MAC if used in an HMAC. Put differently, HMAC could be broken without ever finding a collision in the underlying hash.

Based on almost 2-universal classes of hash functions

This kind of MAC is provably secure.

Like a one-time-pad, this kind of MAC consumes key material. You will need some key material, that is used only for a single message.

Unlike a one-time-pad, the number of bits consumed does not grow with the message size. You can authenticate an arbitrarily large message using a constant number of key bits from your pool. (The key material also has a reusable part, that grows logarithmically in message size.)

Public key signatures based on cryptographic hash

It is possible to construct a public key signature using a cryptographic hash as the only underlying primitive. These can be proven secure based on the usual assumptions about the security of the underlying cryptographic hash.

A major drawback is that they are expensive to compute, and the signatures require a huge number of bits compared to other public key algorithms.

This is not really a MAC, because it is using asymmetrical keys. A signature could be used in place of a MAC, if it wasn't so expensive. The CPU time needed and the number of bits in a signature is prohibitive in many of the situations, where a MAC would be used.


What is meant by this notation in the ElGamal key generation process?

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on.

A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, \alpha_A, \alpha_A^2, \alpha_A^3, \ldots, \alpha_A^{p_A-1}\}$ must be the whole set $\{1, 2, 3, \ldots, p-1\}$ of nonzero elements of the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, i.e. any nonzero element of the field can be expressed as a power of $\alpha_A$. Another way of expressing this property is that $\alpha_A$ must have the order $p-1$ (the largest possible order of an element of the field), which means that none of the $\alpha_A^k$ for $1 \le k \le p-2$ are equal to $1$ modulo $p$.


How many unique elements are generated by a variation on the equation in DSA for r?

If $n > p$, then this will yield $q$ distinct results, since $g^x$ takes on exactly $q$ distinct values all below $p < n$ and ‘modulusing’ by $n$ has no effect in that case.  This is the largest number of values it can take on, no matter what $n$ and $p$ are.

Suppose $q = 2$ and $n = g < p$.  Then there are two distinct values of $g^x$, namely 1 and $g$, and two distinct values of $(g^x \bmod p) \bmod n$, namely 1 and 0.  This is the smallest number of distinct values it can take on, no matter what any of the parameters are.

It can also take on intermediate numbers of values.  For example, with $g = 2, p = 17, n = 13$, we have $q = \operatorname{ord}(g) = 8$, and $(g^x \bmod p) \bmod n \in \{0,1,2,3,4,8,9\}$, which has 7 possibilities, which lies between $2$ and $q$.

It's possible there is some nice formula relating $p$, $n$, $q$, and the cardinality of $\{(g^x \bmod p) \bmod n \mathrel| x \in \mathbb Z\}$, but it's not obvious to the tiny brain in this feathery skull—which is spending more brain cycles wondering: Why do you want to know the number of possible values this can take on?  It is not actually the formula for $r$ in DSA, unless $n = q$.

On the other hand, if $n = q$, one might be wondering about the security of DSA.  Curiously, if one follows the references, what appears to be the standard reference for reduction of DSA security to discrete log security has only this to say on the subject:

  Indeed, it is very unlikely that the $“x \mapsto (g^x \bmod p) \bmod q”$ map has $(\log q)$-multi-collision.

(§6.1 ‘DSA–II Variant’, p. 289)

Here ‘$(\log q)$-multi-collision’ means a set of about $\log q$ (exactly which integer near that real number is not clear) elements sharing a common image under that map; the paper demonstrates a reduction of DSA forgery to calculation of discrete logarithms under the model of the message hash function as a random oracle and under the assumption that the map $x \mapsto (g^x \bmod p) \bmod q$ is $(\log q)$-multi-collision-free.  If, indeed, it is $(\log q)$-multi-collision-free, then since there are $q$ possible inputs in the domain and $q$ possible outputs in the codomain, there are at least $q/\log q$ possible values of $(g^x \bmod p) \bmod q$.

Thus, I'm afraid I must leave it as an exercise for the reader to trawl the number theory literature for wisdom on the question of the cardinality of the image of $x \mapsto (g^x \bmod p) \bmod q$, since the field of cryptography seems to lack an answer.


What's the difference between PBKDF and SHA and why use them together?

SHA-512 is a cryptographically secure hash, PBKDF2 is what we call a Password Based Key Derivation Function. If the resulting secret isn't used as key but as hash value it's also called a password hash. Password hashes differ from secure hashes in the sense that they contain a salt and a work factor / iteration count.

Both cryptographic hashes and password hashes are one way functions designed to create a short, fixed sized output from a given input. In the case of the password hash the input would be the password and salt. The size of the salt and the iteration count are commonly considered configuration parameters; both do of course influence the output of the password hash.

Password hashes are generally build on top of Pseudo Random Functions or PRFs. A usual form of PRF is a HMAC or Hash based Message Authentication Code, which in turn uses a hash internally. When hash-based PRFs such as HMAC are used then the type / size of hash used is often configurable. Password hashes however do not need to be build using hashes. Any other PRF, such as ones based on symmetric ciphers, may do. bcrypt for instance is build on top of Blowfish, a block cipher.

Password hashes need a salt so that identical passwords won't map to the same hash. They therefore also prevent rainbow tables (containing precalculated password / hash pairs) from being useful. Furthermore they contain a work factor / iteration count so that an attacker needs to perform more work to calculate the hash of each possible password. This is needed because most passwords are not random enough. Without the work factor the attacker would be able to test vast amounts of possible passwords using brute force or a dictionary attack.


Is encrypting a single 128 bit block with AES ECB "safe"

16 bytes is 128 bits, which matches the block size of AES-256, but not "256 bit block" in the (original) title. Hence the question is ambiguous: was it meant 16, or 32 bytes?

For 16 bytes: ECB reduces to single-block encryption, and yes ECB is safe, for a definition of safe that let one test identity of plaintexts by testing identity of the ciphertexts.

For 32 bytes (e.g. a US SSN encoded in UTF16 or perhaps ASN.1 or XML): no, ECB is unsafe. This extend to any standard block cipher mode of operation modified by fixing IV. Problem is, plaintexts that match in the first block, but not the second, will match in the first block of the ciphertext, but not the second, which leaks information (e.g. in the US SSN format, it allows to cluster plaintexts by identical area number if the block frontier happens to be on the right of that). You need a 256-bit block cipher, such as Rijndael (a superset of AES) instantiated with 256-bit block. There are ways to construct a 256-bit block cipher from AES-256, but I know none with both a sound security argument and either a short statement, or performance close to Rijndael.

Note: Public key encryption can not be used in the context where "encrypted value of the block (is) to be consistent between encryptions" and the plaintext is low-entropy (enumerable, or guessable). Here, there are few enough SSNs that they can all be enciphered by anyone (knowing the public key), and compared with the ciphertext, leaking the plaintext.

Update: it is now clear that the question is about 16 bytes. I wonder if some day, UTFx with x>8 will catch in the US.


Is a Feistel structure based cipher IND-CPA?

If the challenger is using an encryption algorithm only based on Feistel structures, would it be possible to always correctly identify, which of the messages the challenger encrypted?

No, it will not always be possible to have any such distinguisher, even if we assumed that the attacker had infinite computing resources (!); all we need to assume is that the attacker has a bound on the number queries he is allowed to perform.

We can take advantage of the well-known fact that Feistel structures can implement any even permutation (possibly with a truly huge number of rounds; however the question didn't introduce a bound on the number of rounds); hence it would be possible for a well-chosen set of Feistel structures to produce any even permutation with equal probability.

And, given an attacker that is bounded to no more than $2^N-2$ queries, it is impossible to distinguish a random even permutation from a random permutation.


Does this mean unless you have tested the choice of irreducible polynomial $p$ throughly, you cannot use it for key exchange as proposed by Diffie-Hellman but you can use it for Elliptic Curves?

Skipping the part about Galois fields (where you can easily map between different representations, and so the choice isn't important for security), for Diffie-Hellman, one thing that is important (if not sufficient) is the size of the subgroup that is generated by the generator.

If we pick a size that has a small factor $a$, the attacker can easily derive the values of our DH private keys modulo $a$ (with $O(\sqrt{a})$ work), and so we are leaking $\log_2 a$ bits.

Instead of targeting a generator that generates the entire group, we typically select a generator that generates a large prime subgroup of the group (in some happy cases, this prime subgroup will just happen to be the entire group; that's not the case here, unless we pick $GF(2^x)$ where $2^x-1$ is a Mersenne prime).

For $GF(2^8)$, the size of the multiplicative group is $255 = 17 \times 5 \times 3$; obviously, the largest prime-sized subgroup is 17 (and there will be 16 generators for that subgroup).  This is obvious far too small to be secure, but selecting a generator of a subgroup that size would be more typical of how we use Diffie-Hellman.


What are some restrictions when converting Montgomery Curves into Weierstrass Curves?

My comment already gave you the answer; I'm submitting an official answer to give you something to upvote :-)

An elliptic curve is defined within a field; in the case of curve25519, it is defined within the field $GF(2^{255}-19)$; this is a prime field, because $2^{255}-19$ is prime.

So, when we get to the conversion formulas such as $\frac{3 - A^2}{3\cdot B^2}$, this formula is done within the field the curve is defined in.

Because this is a prime field, addition and multiplication can be implemented by addition and multiplication modulo $2^{255}-19$.  However, division is trickier; it's typically done by computing the modular inverse of the divisor.

As for your question:

  Are there restrictions on which Montgomery curves can be converted to Weierstrass curves?

No, there are no restrictions; all Elliptic curves are isomorphic to some curve in Weierstrass form.  The Wikipedia page you gave gives an explicit mapping from a Montogomery curve into Weierstrauss form.

The one glitch is converting the Curve25519 generator, which is defined as $x=9$; they omit the y-coordinate, and hence corresponds to two elliptic curve points (as there are two different solutions on the curve equation with $x=9$).  This translates into two different points on the Weierstrass curve (which share the $x$ coordinate as well); you can either say that the conversion is that translated $x$ coordinate, or arbitrarily pick one of the valid $y$ coordinates.


Let $[s_0, s_1, \ldots, s_{14}]$ denote the initial contents of the shift register (which holds 15 bits). The output sequence is
$$s_0, s_1, s_2, \ldots, s_{14}, s_{15}, s_{16}, \ldots$$
in that order with $s_{15}$ being the first computed bit that is fed back into the shift register. That is, $s_{15}$ is computed as a linear function (meaning XOR operations) of the initial contents $[s_0, s_1, \ldots, s_{14}]$ of the shift register which then shifts its contents one place leftwards with $s_0$ being sent out into the dark dirty world while $s_{15}$ enters the shift register on the right, thus making the shift register contents $[s_1, s_2, \ldots, s_{14}, s_{15}]$. Thus the change in shift register contents looks like
$$(s_0, \quad s_1, \quad \ldots, \quad s_{13}, \quad s_{14})\\
\downarrow\\
(s_1, \quad s_2, \quad \ldots, \quad s_{14}, \quad s_{15})\\
\downarrow\\(s_2, \quad s_3, \quad \ldots, \quad \quad s_{15}, \quad s_{16})\\
\downarrow\\
\cdots \quad \cdots$$
and more generally as

$$\biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+13}, \quad s_{i+14}\biggr)\\
\downarrow\\
\biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+14}, \quad {\Large{\oplus}}_{j=0}^{14}c_{15-j} s_{i+j}\biggr),$$
where $c_{15}x^{15}+c_{14}x^{14} + \cdots + c_1 x + c_0 = x^{15}+x+1$ is the feedback polynomial. In other words, $$s_{i+15} = c_{15}s_{i}\oplus c_1s_{i+14} = s_i \oplus s_{i+14}$$ and so the taps are on the zero-th and the 14th stage of the shift register.

Just be aware that there is an alternative convention which defines the feedback polynomial as $c_0 x^{15} + c_1x^{14} + cots + c_{14}x + c_{15}$ which would change the tap locations.


secure multiparty computation for multiplication

Well, I am unaware of any published work on this precise problem, however I believe I do have a solution.

First of all, I would note that your problem is equivalent to the problem "if each party has a bit $b_i$, can they securely compute a value $k$ with either $k = \sum b_i$ or $k = N - \sum b_i$ (without giving any further information, including which of those values it might be)".  So, we can use a secure sum as part of the solution, as long as we're careful not to give any information about which sum it is.

Here is how my protocol works; it takes 4 rounds and $4N$ messages between party members.  In each round, the party members arrange themselves in a cycle; each party member takes a value from the previous party member (or the data from the start of the cycle for the first party member), does some computation on the values, and then passes it along to the next party member.  I also do not assume that the message between party members are private.

In an initialization phase, the party members agree on a group where the Diffie-Hellman problem is hard, and two group members $A$ and $B$ such that $A \neq 2^k \cdot B$ and $B \neq 2^k \cdot A$ for any value of $0 \leq k \leq N$ (note: I'm using additive notation for the group, if you're using a multiplicative group, that would normally be written $A \neq B ^ {2^k}$ and $B \neq A ^ {2^k}$)

Now, round 1: we start with the data consisting of the pair $(A, B)$.  Each party member takes the pair that they get $(X, Y)$, selects an integer $c_i$, randomly selects either $(c_i \cdot X, c_i \cdot Y)$ or $(c_i \cdot Y, c_i \cdot X)$, and sends that pair to the next party member.

The point of this round is that the output from the final party will be either $(c \cdot A, c \cdot B)$ or $(c \cdot B, c \cdot A)$ (for some blinding factor $c$) without anyone being able to determine which.

Now, round 2: we start with the data from the last round.  Each party takes the pair they get $(X, Y)$, selects another integer $d_i$, and then if their bit $b_i$ is zero, computes $(2 \cdot d_i \cdot X, d_i \cdot Y)$, and if their bit $b_i$ is one, computes $(d_i \cdot X, 2 \cdot d_i \cdot Y)$, and sends that pair to the next party member

The point of this round is to gather the votes; the first of the pair collects the zero vots, and second of the pair collects the one votes (again, with a blinding factor so no one can see what someone else voted).

Now, round 3: we start with the data from the last round.    Each party member takes the pair that they get $(X, Y)$, selects an integer $e_i$, randomly selects either $(e_i \cdot X, e_i \cdot Y)$ or $(e_i \cdot Y, e_i \cdot X)$, and sends that pair to the next party member (except the last party member; they random select either $(e_N \cdot X)$ or $(e_N \cdot Y)$ and sends that

The point of this round is to disguise which of the pair was the '0' vote, and which was the '1' vote; the last member returns one of them, but no one knows which one it has.

Now, round 4: we start with the data from the last round.    Each party member takes the value that they get $(X)$ and removes the blinding factors they applied; that is, computes $((c_i \cdot d_i \cdot e_i) ^ {-1} \cdot X)$, and passes that to the next part member.

The result of the last party member will be either $2^k \cdot A$ or $2^k \cdot B$; we can recover the value $k$ in $\sqrt N$ time, and that is our result.

Note that:

It will be $2^k \cdot A$ if an even number of party members decided to swap during round 1, and $2^k \cdot B$ if an odd number decided to swap.  Because each party member selected this randomly and independently of anything else, tthis is unbiased, and uncorrelated to anything.
The computed $k$ will be $\sum b_i$ if an odd number of party members decided to swap during round 3, and $N - \sum b_i$ if an even number decided to swap (and for the last party member, we count him as swapping if he selected $(e_N \cdot Y)$.  Again, because each party member selected this randomly and independently of anything else, this is unbiased, and uncorrelated to anything.


Secure multi-party computation for digital signature

Here's a fairly straight-forward method, using RSA:

Set-up phase (assuming a trusted dealer that participates only with the setup phase; such a setup without a dealer can be done, but is considerably more complicated):

The dealer selects a random RSA public/private keypair $(n,e)$ and $(d)$
The dealer then selects $N$ values $d_1, d_2, …, d_N$ with the constraint that $d_1 + d_2 + … + d_N \equiv d \pmod{ \lambda(n) }$
The dealer privately sends $d_i$ to party $i$, and publishes the public key $(n, e)$

Signature generation phase:

Each party gets a copy of the value to be signed $S$
Each party $i$ deterministically pads $S$ (perhaps using PKCS #1.5 signature padding, perhaps using PSS using randomness seeded by $S$), and then raises that to the power of $d_i$ modulo $n$; that is, it computes $sig_i = \text{Pad}(S)^{d_i} \bmod n$
Each party sends $sig_i$ to a collector, which computes $sig = sig_1 \cdot sig_2 \cdot … \cdot s_n \bmod n$, and broadcasts it
Everyone checks if $sig$ is a valid signature to the value $s$; if not, then a malicious party is detected

Lets go through the requirements:

No party can recover secret key $d$ without other $N-1$ parties data

Met; without all the $d_i$ values, you cannot reconstruct the $d$ value.

5.Parties should be able to encrypt $S$ (actually hash of $S$, I need digital signature) with secret key $d$, but without revealing any useful information about $d$ to malicious adversary

Met; each party acts as an Oracle that'll compute $f(x) = x^{d_i} \pmod n$, however if the Discrete Log problem is hard, you can't recover $d_i$ from that.

Now, a malicious party could perform a Denial of Service attack (by not computing his $sig_i$ value properly.  On the other hand, I believe that this will always be true if you require that $N-1$ parties be unable to recover the key (or otherwise generate arbitrary signatures, which is effectively the same as recovering the key), and so I would claim that this meets your requirement.


HMAC_DRBG Generate Process: requesting N bytes at once different from requesting N bytes in total?

Yes, you are reading this right. The requests for random value from NIST 800-90 drbgs perturbed the state.  If this is a problem you can add a layer that optionally buffers values and always makes constant size requests.


Did you try Wikipedia?

DES consists of 16 rounds of the form:

$$L_{i+1} = R_{i}, \quad R_{i+1} = L_i \oplus F(R_i, K_i),$$

which are identical except for the round subkeys $K_i$.  (The last round is slightly different, in that the half-blocks $L$ and $R$ are not swapped as they are after all other rounds, but that makes no cryptanalytic difference.)

The subkeys $K_i$ are derived from the encryption key $K$ using the DES key schedule, which takes the form:

$$K_L \,\|\, K_R = P_1(K)$$
$$K_i = P_2(K_L \lll n_i, K_R \lll n_i)$$

where $K_L$ and $K_R$ are the left and right halves of the permuted key $P_1(K)$, the functions $P_1$ and $P_2$ are fixed maps that basically just shuffle the bits around, and $\lll n_i$ denotes bit rotation by the fixed number of positions $n_i$, where

$$(n_0, n_1, \dotsc, n_{15}) = (1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28).$$

The important thing to note here is that, if $K_L$ and $K_R$ each consist of all zero or all one bits, then rotating them has no effect, and so all the subkeys $K_i$ will be equal, which in turn implies that all 16 rounds of DES encryption using these keys will be identical.  Since there are two choices (all ones or all zeros) for each of $K_L$ and $K_R$, this gives us a total of four weak keys.

In particular, because DES is a Feistel cipher, and therefore each DES round is its own inverse (except for the swapping of the half-blocks), the fact that all the rounds are identical also makes the full DES function self-inverse: that is, for weak keys, DES encryption is the same as decryption.

Ps. DES also has six pairs of "semi-weak keys", for which encryption with one of the keys in the pair is equivalent to decryption with the other (and vice versa).  Basically, these are the keys for which the bit patterns of $K_L$ and $K_R$ repeat with a period of 2, i.e. $$K_L, K_R \in \{000000{\dotsc}00,\, 010101{\dotsc}01,\, 101010{\dotsc}10,\, 111111{\dotsc}11\}$$ (excluding the four weak keys described above).  Because the bit patters have repeat with period 2, the round subkeys $K_i$ for these keys can only take two possible values, depending on whether the rotation constant $n_i$ is odd or even.

In particular, reversing the bits of each of $K_L$ and $K_R$ (or, equivalently, rotating them by one bit) for any of these semi-weak keys gives another "complementary" semi-weak key that generates the same two round subkeys, but switched around.  If you look at the DES rotation constants listed above, you'll notice that $n_i$ is odd if and only if $n_{16-i}$ is even, and thus this swapping of the round subkeys is equivalent to reversing the key schedule.  Since DES decryption is the same as encryption with the key schedule reversed, this means that encryption using a semi-weak key is equivalent to decryption using its complementary pair.

There are also 48 "possibly weak keys" for which the bit patterns of $K_L$ and $K_R$ have a period of 4, and which thus generate only four distinct round subkeys.  These keys don't have such obvious encryption/decryption symmetry properties as the weak and semi-weak keys, but they nonetheless produce a much simpler key schedule than usual, which might conceivably be exploited somehow.

Of course, in practice, all these types of weak keys are pretty much irrelevant: if your keys are chosen randomly (or by a good KDF), the chance of picking a weak (or semi-weak or possibly weak) key is negligibly small ($1/2^{50}$).  And if you did suspect that a system was, for some reason, more likely to use weak keys than one would expect by chance, a much more efficient way to exploit this knowledge would be to just test all these 64 keys and see if any of them indeed happened to be the correct one.  Not to mention that any (single) DES key is "weak" nowadays, simply because the 56-bit keyspace is too small to resist brute force attacks (although triple DES, which doubles the keyspace, does also have the same kind of weak keys as single DES).

Pps. Showing that there are no other similarly weak keys in DES would require a somewhat more detailed analysis. In particular, there's the quirk that the DES PC-2 function ($P_2$ above) ignores some of the bits of the rotated subkeys (specifically, it only selects 48 bits out of 56), so it's possible that $K_i = K_j$ even if $(K_L \lll n_i \,\|\, K_R \lll n_i) \ne (K_L \lll n_i \,\|\, K_R \lll n_i)$.

However, while I haven't actually worked out all the details, I do expect that, even if occasional subkey collisions are certainly possible, the self-inverse properties of weak and semi-weak keys should not occur for any other keys, since they require the whole subkey schedule to be (anti-)symmetric.


What is the difference between known-plaintext attack and chosen-plaintext attack?

It's the difference between an active and a passive attacker:

Known plaintext attack: The attacker knows at least one sample of both the plaintext and the ciphertext. In most cases, this is recorded real communication. If the XOR cipher is used for example, this will reveal the key as plaintext xor ciphertext.
Chosen plaintext attack: The attacker can specify his own plaintext and encrypt or sign it. He can carefully craft it to learn characteristics about the algorithm. For example he can provide an empty text, a text which consists of one "a", two "aa", ... For example: if the Vigenère cipher is used, it is very easy to extract the key length and recover the key by repeating one letter.

So the second type of attack is a lot more powerful.


Secure entropy extractor for thermal noise collected from camera input?

The question asks for an entropy extractor suitable for a particular camera, that is information-theoretically secure, but rejects hash on the rationale that hash functions are not perfectly secure. I'm afraid that for the same definition of secure in these statements, there's nothing on the book; perhaps nothing possible.

A method considered in the question seems to be: XOR the low-order bit of the readings of the three color channels, and feed the result to a Von Neumann extractor. Even assuming that the experimental data in the question holds, it is not information-theoretically possible to prove this will give a result indistinguishable from random, or even just unbiased. Rather, it could be demonstrated that for some model of the input, the output is biased; and more surprising things have occurred in similar attempts in practice. That's because:

There is reason to believe that the channels of the same pixel are heavily correlated; combining several of them is some arbitrary way not taking their nature into account can theoretically leave us with less entropy than in any channel alone, even if the combiner is information-theoretically secure under the assumption that its inputs are not uncorrelated.
The Von Neumann extractor is guaranteed to yield unbiased output if it is fed with mutually independent bits; but here there are reasons to fear that consecutive readings are mutually related (like: the analog route taken by pixels in the same scanning row is the same, hence the capacity of that line creates correlation).
Keeping only the low-order bit of a reading with known entropy is guaranteed to lower the entropy to at most 1 bit per sample, but there's no theoretical minimum, no matter how high the entropy before truncation is, unless some detailed hypothesis is made on the initial samples (in particular: it is quite conceivable that an ADC has its low-order bit constant while it recovers from a large input change).

Cryptographic entropy extractors, based on a hash or similar primitive, are the best thing around with a sound security rationale that does not require knowing some model of the physics and hardware in the entropy source. They are robust: a sound cryptographic entropy extractor convincingly gives output computationally indistinguishable from random for any mishap in its input, except for loss of entropy in the input ever since initialization, or leak of the extractor's internal state thru side channels.

By contrast, simple extractors relying on a some model of the source at their input tend to fail because the model is inaccurate, perhaps even briefly (for example: ADC saturation caused by a power supply transient, internal recalibration after some time or a temperature change).

If one insists on something extremely simple (not secure in a cryptographic sense), with a level of theoretical justification that it is unlikely to be catastrophic for a natural entropy source of unknown model, one could use

a multiplicative scrambler with a large $n$-bit state (detailed below); that's a simple entropy accumulator, of easily tuned capacity; it's output is provably perfectly random if its input is, and it smoothly degrades to a simple PRNG otherwise;
fed with all the bits output by the sensor's channels;
with sub-sampling  of its output keeping every $s$th bit, with sub-sampling factor $s$ coprime with $n$ and such that the residual bit rate is comfortably below the entropy rate on input estimated by the empirical data at hand (say, by a safety/fudge factor of 8, or 2 if the next step is taken); thus here, if we feed 24 bits per pixel and have an estimated 2.1 bit entropy per pixel (which the second figure on the right column justifies), we want $s$ at least 8*24/2.1 or 2*24/2.1; rounding up to the next prime number in order to widen our choice of $n$, that's $s=97$, or $s=29$ with the next step;
optionally followed by a Von Neumann extractor, which will divide the average bit rate by 4 (and make it irregular, which might be unwelcome); it is likely to remove a residual bias that could be present for low $n$ even if everything else goes as planned; it makes cryptanalytic attacks trying to distinguish the output from random more involved;
taking care to discard the early output until the number of discarded bits is several times $n$;
with precautions that nothing in the above can have any feedback to the entropy source (which would invalidate the hypothesis that the model of the source has nothing to do with the scrambler).

A multiplicative scrambler is built around a LFSR, based on a binary polynomial of degree $n\ge1$. The polynomial must have the constant term set (ensuring it does not lose entropy), and is often chosen primitive (which avoids a number of poor choices; and maximizes the expected period for input stuck at 0, though that's not essential here). For example, with $x^{23}+x^{18}+1$, the schematic of a scrambler used in telecoms goes

In telecoms, $n$ must be small (for quick resynchronization of the descrambler in case of error). We rather want something with a larger state, like $x^{256}+x^{187 }+x^{125}+x^{60}+1$, taken from eq-primpoly-w5.txt of Jörg Arndt's Tables of mathematical data, quoting Janusz Rajski, Jerzy Tyszer: Primitive Polynomials Over GF(2) of Degree up to 660 with Uniformly Distributed Coefficients, in Journal of Electronic Testing: Theory and Applications, vol.19, pp.645-657, 2003. A software implementation can use an array $b$ of 256 bits, and an 8-bit index $i$ (all operations on index being truncated to 8 bits)

for each input bit $x$

$i\gets i+1$
$x\gets x\oplus b_i\oplus b_{i+60}\oplus b_{i+125}\oplus b_{i+187}$
$b_i\gets x$
output $x$


How to solve polynomial modular equation to create a correct decryption algorithm

We can write $m$ as

$$m = (c -3 + 4k) \cdot 5^{-1} \pmod n$$

There is a problem here that the 5 may not has an inverse for every $n$. For example, it doesn't have an inverse in $\mathbb{Z}_{10}$.

It has an inverse in $\mathbb{Z}_{n}$ if $\gcd(5,n) =1$.

If it has the inverse one can find it by the Extended Euclidean Algorithm to form the Bézout's identity $5 x + n y = 1$ then take $\bmod n $ to achive the inverse as $5 x = 1 \bmod n$

As pointed by poncho, for finding the inverse of $5$ there is a better method $$(n+1)/5, (2n+1)/5, (3n+1)/5, (4n+1)/5$$ if the inverse exist. To see the inverse exist, one first needs to see that the $\gcd(5,n)=1$.

In the general case, after some threshold, this approach may not be helpful, since testing all $$(n+1)/x, (2n+1)/x, \ldots, ((x-1)n+1)/x$$ will pass the calculation of the Bézout's identity.


Cracking a hash which descends to a single value after repeated hashes

This specific hash function is weak; it appears that what this hash function does is pad out the string to be hashed into a 32 byte string, and then take the 8 4-byte substrings, and maps each substring individually into an individual byte.

This immediately makes it trivial to find a preimage; start with a random 31 byte preimage (there appears to be a bug in the code if it is presented with a 32 byte input), hash it, and for every byte of output that is wrong, modify the corresponding 4-byte substring in the preimage, and repeat until the hash is the expected value.

However, to answer the general question of whether a hash function with the specific property that is necessarily weak, well, I believe that we can produce an example of such a hash function that is not.  One such example would be:

Given the empty string, outputs the empty string
Given a string $S$ of length $L$, generates the first $L-1$ bits of $SHAKE256(S)$

This function would appear to be strong given a long input (because we believe that SHAKE256 is a strong hash function), but repeated application of this hash function eventually will cycle at the empty string.


Authorities on password hashing best practice

The best place to start is the password hashing competition. It was run by and had many entries by competent researchers. You don't make a mistake going with their recommendation.

If you are interested in ongoing discussion I suggest their mailing list.


Encryption that purposefully take hours to decrypt

Time-lock puzzles appear to be what you want (see for example this).
A basic construction is via "Repeated Squaring in the RSA group".

Let $p,q$ be large primes, and let $N = pq$.
The goal is, for fixed $t>0$, to compute $2^{2^t}\bmod N$.
There are two "obvious" ways to do this, depending on whether you know the factorization of $N$ or don't.

If you do know the factorization of $N$, you can first compute $2^t\bmod \varphi(N) = 2^t\bmod (p-1)(q-1)$, and then compute $2^{2^t\bmod \varphi(N)}$ via Repeated Squaring. The complexity of this is at most $O(\log N)$ multiplications within $(\mathbb{Z}/N\mathbb{Z})$.

If you don't know the factorization of $N$, then there are some conjectures [1] that computing $2^{2^t}\bmod N$ must be done "directly" (and that it cannot really be parallelized).
One can do this by repeated squaring to give a complexity of $2t$ multiplications within $(\mathbb{Z}/N\mathbb{Z})$.
Here $t\in\mathbb{N}$ is an arbitrarily large number, allowing you to make this as "difficult" as you want.

Note that someone could always factor $N$ if they want to ignore this (so it's not "arbitrarily hard"), but if you make factoring $N$ appropriately hard it gives you fine-grained control over the difficulty of computing $2^{2^t}\bmod N$ (which is the "easier option" in comparison).
One can then use $2^{2^t}\bmod N$ as the basis of any symmetric-key crypto scheme (or hash it into any suitable domain first).
Your algorithm could then look as follows:

To encrypt something, generate an RSA instance, compute $2^{2^t}\bmod N$, use this value (or its hash) to encrypt something, then only store $(N, t)$.
To decrypt, start by recomputing $2^{2^t}\bmod N$, then decrypt using whatever "base scheme" you encrypted with.

This has the benefit of allowing you freedom to "tune" the parameter $t$ to take however long you want to decrypt.

[1] For more information I'd suggest looking into Verifiable Delay Functions, but I'm not too familiar with the area admittedly.


Problems understanding the applications of pseudo random number generators

In most cases your runtime uses a DRBG rather than a PRNG. A DRBG is a Deterministic Random Bit Generator, so it delivers bits to the user rather than random numbers in a specific range. Generally it is possible to request bytes and then use - for instance - the lowest 4 bits. If the 8 bits of a byte are random then the lower 4 bits must be random as well after all. In most programming languages you can get to the lower 4 bits (4 bits is called a nibble) by MASKing: nibble = byte & 0x0F.

If you have a PRNG that delivers numbers in a range $0$ (inclusive) to $n$ (exclusive) then you can request a number in the range $0$ to $16$ because $2^4=16$. The number requested will have the lowest order bits set to the random values.

Generally the conversion to nibbles should be covered by existing tests. However, if you still want to perform a test then you could try and generate about 500 billion nibbles (yes, you are reading that correctly) and use that to create a 250 GB file. That file can then be used to test against the Dieharder testing framework. Testing for randomness requires a lot of samples if you want to be cryptographically secure.

Beware that most DRBG's are actually (re-)seeeded using an operating system. You must make sure that the DRBGs/PRNGs actually delivers the type of pseudo-random stream you're after.


What is the entropy of a Mersenne Twister (MT)?

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

The subsequent distribution is not, in fact, independently uniform.

Given 624 32-bit outputs $$V = V_1 \mathbin\| V_2 \mathbin\| \cdots \mathbin\| V_{624},$$ I can deterministically recover the Mersenne twister state by $$S(V) = \tau^{-1}(V_1) \mathbin\| \tau^{-1}(V_2) \mathbin\| \cdots \mathbin\| \tau^{-1}(V_{624}),$$ where $\tau$ is the tempering transform, and then compute the next output by deterministically running the generator $G$ on the recovered state $S(V)$.  If the $V_i$ were independently uniformly distributed, we would have $$\Pr[V_{625} = G(S(V))] = 1/2^{32},$$ but if the $V_i$ are instead generated by the Mersenne twister with uniform random initial state, we have $$\Pr[V_{625} = G(S(V))] = 1.$$

This test—evaluate whether $V_{625} = G(S(V))$—will distinguish the Mersenne twister under a uniform random initial state from a uniform random string with high success rate.

Does this nonuniformity matter for the Monte Carlo physics simulation you're doing?  Perhaps not: your physics model is unlikely to, by happenstance, interact with the Mersenne twister output generation function $G$ in a way that would be a problem, because physics itself is usually not adversarially trying to screw you up personally, no matter how much the years of pain in grad school might make it seem.

On the other hand, if there is an intelligent adversary, as we assume in cryptography, that intelligent adversary will exploit this relation to decipher your messages, steal your money by forging signatures, etc.

In other words, the Mersenne twister is designed to appear uniform to stupid algorithms that don't even know it's the Mersenne twister they're trying to distinguish, but falls flat on its face when it trips on an adversary who knows it's the Mersenne twister but just doesn't know the initial state.


If $e$ is not too large, then it is easy.
The relation $q = e^{-1} \mod p$ can be rearranged to $qe = 1 + kp$ for some integer $k$; or in other words, $p/q \approx e / k$; that is, $p/q$ is extremely close to a simple rational, and that makes factorization easy.


TLDR: Can't do.

16-bit is simply not enough for digital signature, which requires many times more bits¹, and can't be checked if truncated (becoming useless).

One may want to consider a Message Authentication Code, such as HMAC with SHA-256. At least, that's cryptographically better than an encrypted CRC². But there must be a shared secret between sender and receiver(s), thus that's not usable in the question's stated context.

If one absolutely needs public-key verification, the only option that I see is signing a group of earlier packets in a special signature packet (or group of signature packets), as the question proposes for "critical information". Problem is that losing a single packet prevents verification of the signature.

¹ To attain even mild security (80-bit), the most compact signature schemes around require about 224 bits (or 160 for a BLS scheme once used but now thought quite vulnerable), for something that is added to data renaming in clear; or down to 64 bits if you accept that about 1200 bits of the payload remains scrambled until cryptographic verification (even though only the public key is involved for the unscrambling, it's very debatable that the later meets the requirement of non-encryption in amateur radio).

² It is trivial to alter a message without changing the CRC, thus the encrypted CRC.


Why do we use encrypt-decrypt-encrypt (EDE) in 3DES, rather than encrypting three times?

Well, the standard answer is to preserve compatibility with DES; a hardware circuit that implemented 3DES (with EDE) could also be used to do DES as well (by, say, making all three subkeys the same).

Now, there is one slight problem with this straightforward argument; 3DES (EEE, that is, with three encrypt operations) would have this property as well; if we select the first two subkeys to be the same weak key, the second encrypt with the weak key would exactly undo the first, and the plaintext block will be operated on by the third subkey (which is the DES operation we really want).

However, it's not the case that whoever designed 3DES missed this point.  Instead, they were also considering a third option as well, 2 key 3DES (which is normal 3DES except that the first and the third subkeys are the same).

Now, if we had a 3DES EEE implementation with three independent subkeys, we could support DES (using the weak key trick), 2 key 3DES (EEE), and 3 key 3DES (EEE).  However, that wasn't the only situation they had in mind; they also considered the case where someone implemented 2 key 3DES in hardware (which the first and last subkeys were constrained to be the same).  That's one thing EEE mode can't do; we can't use the weak subkey trick with 2 key 3DES (if we make two of the adjacent subkeys the same weak key, then all three subkeys are the same weak key).  However, the EDE trick still works.

Hence, the full answer is so that one hardware circuit can support both DES and 2 key 3DES (where the hardware circuitry insists on using the same subkeys for both the first and third subkeys), and also one hardware circuit can support DES, 2 key 3DES, and 3 key 3DES.


Given only what you've said, and assuming the keys are created and stored in a strong manner, using a different key to encrypt database entries mitigates the problem of ECB mode. Namely that identical plaintext, when encrypted with the same key, always outputs the same ciphertext. No security is gained by switching to CBC mode (assuming you can easily store all the keys securely, but see what @Thomas Pornin had to say about that). The practical gain by switching to CBC mode is that you only have to store one key securely. The IV's don't typically need to be protected.

In the second scenario where the exact same key is used for all entries in ECB mode, the advantage the attacker gains is that if he knows a plaintext/ciphertext pair, he now knows everywhere that plaintext appears in the entire database.

For example, lets say the attacker's own info happens to be in the database. He can look up the encrypted version of his gender. He now knows the gender of everyone else in the database (if the ciphertext is the same as his, he knows the entry is for a male, otherwise it is for a female). This same idea can be extended to other fields (age, first name, last name, etc). The key to this advantage is though that the attacker must have plaintext/ciphertext pairs.


Can AES ans SHA-2 algorithms be implemented in parallel?

They can be computed in parallel.

But what would still make AES-GCM faster than AES-SHA2 is GCM itself.

GCM is a universal hash function: it can be very fast, especially on CPUs supporting carry-less multiplications.
But it doesn't satisfy the same properties as a hash function such as SHA2. In particular, not encrypting its output would have catastrophic implications. It's fast because it is a simple and specialized function.

Even with Intel and ARM SHA extensions, I doubt it would be faster than GCM.

With AESNI and CLMUL, AES-GCM is about 0.65 cpb. SHA256 alone using Intel extension is about 3.8 cpb.


First of all, let us look at what AAD is; it is a string that must be presented both at encryption and decryption; if the decryptor presents the wrong string, the decryption fails.
Why is this useful?  Because AAD can be understood as "encryption context".  We typically use the same keys to encrypt several messages.  What AAD prevents is the attacker taking one of the valid ciphertexts, and replacing another of the ciphertexts (encrypted with the same key) with it; if the decryptor uses different AADs for the two separate contexts, then the decryption will fail (and the attack is thwarted; if the attacker just wanted the decryption to fail, he could just replace the ciphertext with random gibberish).
An alternative approach would be to just use a separate key each time; that'd work, however AAD generally solves the problem with less complexity.
So, to answer your question:

What is an example problem/scenario that AEAD solves?

You asked for one; I'll give you two:

Consider TLS, where individual records are encrypted with the same key.  TLS uses an AAD that includes the record sequence number (which increments with each record); this prevents an attacker from replaying a previously sent record.

Consider database encryption, where we are encrypted individual fields within a database, for example, a database that gives the employee names [1] (unencrypted) and the salary (encrypted).  If the attacker could (say) take Alice's salary, and write that into Bob's row, well, that'd be bad.  By using the employee name as the AAD, the attacker can't do that undetected.

How does AEAD solve this problem? (not the algorithm details but higher level big picture)

What GCM does is stir in the AAD into the tag; if the AAD isn't correct, the tag would not verify (and you're supposed to reject the decryption in that case).

If AEAD is not used what are attackers able to do?

Replace one ciphertext with another

As a developer should I always use AEAD for everything?

Well, if you're using the same key for multiple purposes, you probably should use a distinct AAD for each encryption.  On the other hand, if you're using the key to encrypt only one message (e.g. as the symmetric portion within IES), there is no need

Is AEAD only required for block ciphers but not required for stream ciphers?  Is AEAD required when using a public key crypto such as RSA?

Generally, the replay problem needs to be addressed, however stream ciphers and public key methods generally use different approaches.
With stream ciphers, we often generate a single long string, and use distinct portions to encrypt individual messages - this prevents replay attacks.  Other times (when we need to be able to decrypt messages out of order), we include a nonce as an input to the stream cipher, and have a higher level protocol ensure that a nonce is not reused.
With public key encryption, it's generally handled at a higher level, possibly with a nonce...

[1]: A real database will be more likely to have some sequence number rather than the name; I'll ignore that for this example.


Is there a property comparable to IND-CPA for hash functions taking a random value?

Not only is your idea of using $H(x|| r)$ sufficient, it will even in general provide unconditional security, if $H$ satisfies some regularity property, which is (roughly) that the size of the preimage of $H$ with a given prefix $x$ is always approximately of the same size.

To reformulate your question, you are asking whether $H(x || r)$ leads to a hiding commitment scheme, i.e., a scheme com for which it is infeasible to distinguish com$(x_0)$ from com$(x_1)$ given $x_0$ and $x_1$.

If you use any standard hash function which maps long strings to shorter string, observe that there will be in general many preimages to any given output of the hash functions. This means that given a hash value $h$ and strings $x_0$ and $x_1$, there will almost always exist values $r_0,r_1$ such that $H(x_0|| r_0) = H(x_1||r_1) = h$ (and the number of such values should be essentially the same for $x_0$ and $x_1$). This means that it is impossible to find out whether $h$ was obtained by hashing $x_0$ or $x_1$, even if the adversary is computationally unbounded.

If you want more formal details, an improved variant of this scheme was studied in this paper (where they show that their scheme is also binding - i.e., you cannot change your mind about $x$ if you later reveal the input you've fed to the hash function - and obtain a perfectly hiding commitment scheme without even having to assume that $H$ is regular).


Chrome TLS 1.3 no TLS resumption with not secure connections

This is a typical behavior of Chrome if the certificate is not trusted but the user has just skipped the warning. Skipping warnings is a bad idea anyway so you better import the certificate explicitly as trusted.


Does gpg's symmetric encryption keep information about the filename?

Yes, gpg -c file.zip does encode the input file name in the encrypted packet.
The gpg man page documents a few relevant options:

--set-filename string
Use string as the name of file which is stored in messages.

This  overrides the default, which is to use the actual filename of the file being encrypted.

--use-embedded-filename
Try to create a file with a name as embedded in the data. This can be a dangerous option as it allows to overwrite files.

This defaults to no.


Yes, it's broken.  Here is the approach I see:

$$p = \text{gcd}( n, r^e - r \bmod n)$$

with quite high probability, for random $r$.

This happens because $e \equiv 1 \bmod p-1$, and hence $r^e \equiv r \pmod p$ (for any $r$).  It is unlikely that $r^e \equiv r \pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.


How does randomized hashing defeat collision attack?

In randomized hashing for Merkle-Damgard based hash function (like MD5, SHA1, SHA2) the input preprocessed with a salt before hashing applied. This process doesn't modify the underlying hash function uses it as a black box, It is proposed by Shai Halevi and Hugo Krawczyk in 2007;

Strengthening Digital Signatures via Randomized Hashing

For MD based hash functions. They defined the Target Collision Resistant (TCR) as;

a family of hash functions $\{H_r\}_r\in R$ (for some set $R$) is target collision-resistant if no efficient attacker $A$ can win the following game, except with insignificant probability:

A chooses a first message $M$, then receives a random value $r \in_R R$, and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.

and they also defined the Enhanced Target Collision Resistant (eTCR) since signature schemes like DSA don't support to sign the salt $r$. To support this they use relaxing the conditions to strengthen the mode of operation. This scheme is

sufficiently strong to ensure the security of the resultant signatures even if we only apply the underlying signature to $H_r(M )$ and do not sign the salt $r$.

The game is played as;

A chooses a first message $M$, then receives a random value $r \in_R R$, the salt r, the attacker can supply a second message $M'$ and a second salt $r'$, and it is considered successful if $(r, M ) \neq (r', M' )$ but $H_r (M ) = H_{r'} (M')$.

and it needs to find a second message $M' \neq M$ such that $H_r(M_0) = H_r(M)$. The value $r$ is called a hashing key, or a salt.
They define two methods as;

$$H_r^c(m_1, \ldots , m_L) \overset{def}{=} H^c(m_1 \oplus r,\ldots, m_L\oplus r).$$ This scheme is TCR under second-preimage resisantce (SPR)
*. This suit RSA signature since we can extend the modulus so that the $r$ can be signed, too.

And the below scheme is eCTR under SPR, too *, This is useful for DSA like algorithms in which signing additional data, $r$, is not easy.
$$\tilde{H_r^c}(M)\overset{def}{=} H_r^c(0|M)  = H^c(r, m_1 \oplus r,\ldots, m_L\oplus r).$$

They designed their scheme so that the security of the resultant signature scheme does not depend on the resistance of the hash function to off-line collision attacks. In short, they related the security of their scheme to the second-preimage resistance of the compression functions.

* Actually, the proofs rely on two properties that related to SPR. e-SPR is the real hardness of collision resistance of $H_r$ and $\tilde{H_r}$. And, c-SPR, which is related to the hierarchy of collision resistance.
Note 1: There is a web page that shows how this and similar method can be easily applied to NSS Library and Firefox.
Note 2: The extended version of the paper is here ( and it is not https!)


Can Secp 256 K1 curves "map" to a value on FIPS 186-3 or P-256?

If what you want is some kind of algorithm that takes a public key $Q = aP$ on one curve and converts it into $Q' = a P'$ on the other curve, then the answer is almost certainly no. There are no "interesting" maps between curves with different group structures.

If you just want to use the same secret key for both curves, so $Q = aP$ on one curve and $Q' = aP'$ on another, $P,P',Q,Q'$ public, that isn't obviously a bad idea. It seems plausible that the obvious DDH-like problem is hard. However, doing this does introduce a bunch of technical problems, e.g. how do you prove that your public keys correspond to the "same" private key (which can be solved, but is tricky when the group orders are different).


Does this computation lead to solving DL?

No.
Assuming that uniformly random sampling for $x,b$ is applied, this (let's call it E-CDH) is actually equivalent (in terms of hardness) to the Computational Diffie-Hellman Problem (CDH). Which states: Given a finite group $G$, sample $a,b\in G$ uniformly at random and provide $g^a,g^b$. The problem is solved if you can find $g^{ab}$.

Proof:

CDH is at most as hard as E-CDH ($\Rightarrow$). Suppose we have an oracle $\mathcal O(g^b,a,g^x)$ that returns $g^{(a+x)b}$ (i.e. an oracle that solves E-CDH). We can now solve any given CDH instance $g^a,g^b$ as the result of $\mathcal O(g^a,0,g^b)=g^{(a+0)b}=g^{ab}$.

E-CDH is at most as hard as CDH ($\Leftarrow$). Suppose we have an oracle $\mathcal O(g^a,g^b)$that returns $g^{ab}$, ie solves the CDH problem. Now suppose we are given the instance $g^x,a,g^b$, we now compute $g^a$ and $g^x\cdot g^a=g^{x+a}$. Finally we return $\mathcal O(g^{x+a},g^b)=g^{(x+a)b}$ and thus solve the instance.

Small assumption: We need to actually know $g$ and the relevant group.


Key sizes for discrete logarithm based methods

The best known estimates are still the two that can be found in RFC 3526. Both estimates (with regard to the modulus size) are based on the estimated number of operations required to compute discrete logarithms using number field sieve based methods. The reason the estimates differ, is because of the second estimate does not account for memory/time trade offs that would require arguably unrealistic amounts of storage space.

   +--------+----------+---------------------+---------------------+
   | Group  | Modulus  | Strength Estimate 1 | Strength Estimate 2 |
   |        |          +----------+----------+----------+----------+
   |        |          |          | exponent |          | exponent |
   |        |          | in bits  | size     | in bits  | size     |
   +--------+----------+----------+----------+----------+----------+
   |   5    | 1536-bit |       90 |     180- |      120 |     240- |
   |  14    | 2048-bit |      110 |     220- |      160 |     320- |
   |  15    | 3072-bit |      130 |     260- |      210 |     420- |
   |  16    | 4096-bit |      150 |     300- |      240 |     480- |
   |  17    | 6144-bit |      170 |     340- |      270 |     540- |
   |  18    | 8192-bit |      190 |     380- |      310 |     620- |
   +--------+----------+---------------------+---------------------+

These estimates do not account for post-quantum cryptography. Arguably, it is not entirely improbable that we will see major break-troughs in quantum cryptography, rendering these estimates moot, long before the difference between estimated 128 bit strength and 256 bit strength will become relevant for most practical purposes. Then again, there might of course be applications that generate a lot of traffic and has to bump the estimated security strength, to guarantee that the advantage of an attacker stays well below $2^{-128}$ even in a shorter term.


There are several uses of cryptographic algorithms in the protocol.

Accounts/Transactions

To move money from one account to another, you need to collect some data (the previous transaction(s) which got you the money, the target account, the amount you want to transfer) and sign them, using the private key which belongs to your account.

For this signature Bitcoin uses the ECDSA algorithm.

If I can fake your signature, I can also steal your money.

The (public) addresses of the accounts are given as address = version || hash || checksum, where version = 0 (one byte), hash = RIPEMD-160(SHA-256(public-key)) and checksum = first 4 bytes of SHA-256(SHA-256(version || hash)). (The checksum mainly protects against transmission errors.)

If I can somehow generate a private key whose corresponding public key has the same SHA-256 hash as your one, it will have the same address, and I can steal your money. If I can create a fitting private key for your public key, this is also possible.

For now, there is no known attack at the ECDSA algorithm (and I think even with second-preimage attacks at SHA-2 to find a second public key with same hash, you would need an attack at ECDSA to get a useful private key).

It is much easier for now to use a trojan or such to steal the actual private key of the owner. (But this would be off-topic here.)

The Block chain

For a transaction to be deemed valid, it has to be included in the block chain, e.g. in one of the blocks consisting this chain.

To create this block, a miner uses a Merkle tree of hashes, which refer the individual transactions included in this block, the previous block, and some other data. This tree uses SHA-256, too.

A block is considered valid (e.g. other peers will accept it, and build their own blocks on it) if the hash of the header is lower than some number (the "target"). This can be reached by manipulating one part of the block, the nonce value, calculating the hash, and repeating until one is lucky hitting the right nonce to make this block valid.

If there are several valid blocks running around (which are not descendants of each other), "good" miners will usually build on the one with the longest chain.

So, how could we cheat here?

If we can break SHA-2, e.g. by finding a faster way to get the right nonce than trying many of them, we can generate the blocks faster than everyone else. This would mean that we will get all of the mined coins, at first. Having a monopole, we can also effectively decide which transactions to include and which ones not (this could be a denial-of-service for competitors who want to transmit money).

I'm not sure if we could in fact include bogus transactions this way (or by other SHA-2 breaks means) in our Merkle tree - I think the receivers of a blocks should still check if its transactions have actually a valid signature.

For now, no such break of SHA-2 is known.


Safety of encrypting a plaintext with its hash as the key

No, there are no security risk beyond "(with) an approximation or part of the plain text, brute force attack complexity will be reduced considerably", understood to cover the fact that an exact (or near complete) guess of the plaintext can be verified with near certainty by one not holding the key. That is under the plausible assumptions that the hash is secure in the random oracle model, and the cipher's design is independent of the hash (the later condition takes care of a cipher purposely made insecure specifically when the key is equal to the hash of the plaintext).

Decryption works just as usual: under the standard assumption that the ciphertext is public, revealing the key allows decryption. The only functionality issues that I can think of are that encryption requires more work, including two passes on the plaintext, and on-the-fly encryption is impossible.

So-called Convergent Encryption goes one step further: it uses a hash of the plaintext as key, and deterministic encryption (the hash is typically stored conventionally encrypted along the ciphertext, possibly using asymmetric cryptography). The same plaintext is therefore always enciphered to the same ciphertext (except for the conventionally encrypted hash). That is nice for de-duplicating encrypted data, but gives up a little more on security: it becomes slightly easier to recognize a known piece of data from its enciphered form.


Can I create a fixed length output from a fixed length input?

See “format-preserving encryption” at WikiPedia.

Depending on the size of the message space, one can get such a scheme by:

sorting pseudorandom values, see section 4.1 of “Format preserving encryption”,
or
using this arbitrary-size scheme described in “Perfect Block Ciphers With Small Blocks”,
or
using swap-or-not as described in “An Enciphering Scheme Based on a Card Shuffle”.

Nota bene: we also have a format-preserving tag that points to related questions and answers.


Need help finding keysize for Vigenere cipher

For the explanation to why this approach works I found an excellent answer here: repeating-key xor and hamming distance
And I managed to finally find the correct keysize using the following pseudocode:
dictionary = () // dict or hashmap which stores <Keysize, Score> as <K,V> pair
for keysize in 2..max_keysize:
    n = 0, score = 0
    while True:
         if 2*keysize >= bytes.len():
             break
         a = bytes[:keysize]
         b = bytes[keysize:2*keysize]
         score += (hamming_distance(a,b) / (8*keysize))
         n += 1
    averaged_score = score / n
    dictionary.add(keysize, averaged_score)

And finally you select keyisze with lowest averaged_score


AES vs Blowfish taking key-length into account

Blowfish has a 64-bit block size whereas AES has a 128-bit block size, so you are sort of comparing apples and oranges (there are some things you can do in AES which would be unwise in Blowfish, in particular Blowfish in CTR mode can be distinguished from a random stream after only a few dozen gigabytes of output - see fgrieu's answer here, replacing 128 by 64 in the calculations).

As for strict brute force complexity, I think you've pretty much answered your own question, if we assume that 256-bit keys are sufficiently resistant to brute-forcing then using a longer key makes no sense. It's like trying to decide what's best between "infeasible" and "infeasible". But theoretically speaking, Blowfish uses all 448 bits of the key, so a brute-force attack would take on average $2^{447}$ guesses at the key, whereas AES would take $2^{255}$ guesses on average (AES-256, that is).

Now if you want to take cryptanalytic advances into account, AES-256 has a much lower margin of security (break complexity / brute-force complexity) than Blowfish, though both remain secure today. That said, it should be kept in mind that since AES is the Advanced Encryption Standard, it has received considerably more attention from cryptographers than Blowfish!


Cryptographic hasing functions init-update-final

Many libraries, like Java and OpenSSL, provide an Init-Update-Final model for transformations. It's used to minimize memory requirements.

Let's suppose all you have is a single shot SHA-1 function which requires the input to be available.

Then, for example, with a 1GB RAM system, how would you hash a file of 2 GB ?

You simply cannot as the SHA-1 function will require to have the whole input in RAM and you simply can't do it.

What you can do, instead, is to call SHA_Init, read 1MB of the file into RAM, SHA_Update that 1MB, read the next 1MB of the file (overwriting the previous one), call SHA_Update on that 1MB, repeat 1998 more times and then call SHA_Final.

This requires only 1MB RAM to hash a 2GB file.


What is the "Random Oracle Model" and why is it controversial?

A random oracle is described by the following model:

There is a black box. In the box lives a gnome, with a big book and some dice.
We can input some data into the box (an arbitrary sequence of bits).
Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message $m$, until we actually try $m$. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really "random" oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Indeed, see SHA-256 (or SHA-512 if you wish). It suffers from something called the "length extension attack". This is an artefact from the Merkle–Damgård construction: to hash a message $m$, the message is first split into fixed-size blocks (64 bytes for SHA-256), the last block being padded with some bits which include the length of $m$, and some ones and zeros such that we end up with a full block. Each block is then processed over a running state, the hash output being the last block value.

So suppose that there is a message $m$, that I do not know, but I know the length of $m$ and its hash $h(m)$. With that information, I can rebuild the padding bits which were added (let's call them $\pi$). Then, I can envision the message $m'$:
$$ m' = m || \pi || x $$
for some value $x$ that I choose arbitrarily. I then know that the computation of $h(m')$ will begin by splitting $m || \pi$ into blocks and processing them, and after having processed the last bit of $\pi$, the current "running state" will be exactly $h(m)$. So, if I know $h(m)$, I can finish the computation of $h(m')$ by taking it from there, and I can do that without knowing $m$. In particular, I end up with $h(m')$ while not having presented $m'$ to the gnome.

This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function.

It has actually been shown (by Canetti, Goldreich and Halevi) that random oracles cannot exist "in all generality" in the following sense: it is possible to build pathological signature and asymmetric encryption schemes, which are secure when they internally use a random oracle, but which are insecure whenever an actual computable function is used instead of the mythical gnome-in-the-box.

Summary: proofs in the random oracle model are fine, but are never complete enough to cover a practical implementation: we know that any function we will use in lieu of the random oracle will not be a random oracle; so security relies on the fervent hope that the parts where the actual function is not a random oracle do not impact security. This justifies a bit of mistrust. Still, a proof in the random oracle model is much better than no proof at all.


Could we share a secret key using the Birthday problem?

You are right that if it costs Alice & Bob effort $N$ to agree on a key in this way, then it costs Eve only effort $N^2$ to find it. So the protocol is not secure in the standard sense, and probably not very useful. (Maybe in some highly constrained situation with very short-lived keys?)

More generally, this purports to be a key agreement protocol whose only ingredient is a hash function / one-way function used in a black-box way. It is known that such a thing is impossible:

  R Impagliazzo, S Rudich, Limits on the Provable Consequences of One-Way Permutations, CRYPTO 1988.


How to use Botan to verify a web3 wallet/password?

Ah, the misunderstanding was that the spec says SHA-3 (Keccak-256), which I had assumed was SHA-3-256, but is actually Keccak-1600(256), which is part of the SHA-3 standard. Fixed.


How can I get the message which was encrypted before (when decrypting a product cipher) ?

You don't need 14. You need the inverse of 7 which is 15.

$$14 a  = 4 \mod 26$$

$$7 a = 2 \mod 26 $$

$$a = 2 * 15 \mod 26$$

$$a = 4$$


Is there a 1:1 mapping between private and public EC keys?

Points on secp256k1 fulfill the equation:

$$ y^2=x^3+7 \pmod p$$

Your 257 bit compressed point consists of the sign* of $y$ and the value of $x$. You probably want to restrict $x$ to $0 \leq x < p$ as a canonical representation.

Since $y^2$ is obviously a square,  we need to look at $x^3+7$ to see if it's a square as well:

If $x^3+7$ is a square, then there are two points for that $x$ which only differ by the sign of $y$, which is why the compressed point contains the sign of $y$.
If $x^3+7$ is zero, there is only one solution, since $y=-y$.
If $x^3+7$ is a non-square, then there are no solutions.

Not counting $0$, exactly half the elements of the finite field are square and the other half is non-square. $x^3+7$ complicates matters a bit, so approximately half of the possible $x$ values are square. Hasse's theorem on elliptic curves quantifies this approximation.

You can efficiently check if a field element is square, and thus verify if it is a valid $x$ value of a point on the curve.

* field-elements don't actually have a sign. But since the least significant bit of non-zero values differs between $+y$ and $-y$, we can use it as sign. See Determine if a public key point y is negative or positive, odd or even? for a longer explanation.


Why is the subhash key (H) of AES-GCM defined as such?

In GCM, GHASH doesn't use K directly in order to ensure that if GHASH's key is compromised, the master key K remains secret.

Actually, there's not why GCM was designed the way it was (it may be an effect, but not the reason).  Instead, the reasons were:

To allow provable security (based on the assumption that the block cipher was a secure keyed random permutation).  If we used $k$ as both the block cipher key, and used as an input to compute the tag, we need to make additional assumptions on the block cipher.
Because of the size mismatch; $h$ is 128 bits, $k$ is (at least, for AES) is either 128, 192 or 256 bits.  Yes, one could select an arbitrary section of $k$ as your $h$, however, that seems a bit, well, arbitrary...

In any case, to answer the question you did ask:

  If the mapping is universally constant wouldn't it be the case that this could be pre-computed and available somewhere?

Not really, the effort of pre-computing such a table would be at least $O(2^{128})$ operations; we believe that is infeasible for anyone, even as a one-time effort.  And, generating a rainbow table doesn't decrease this effort any; it just makes the generated table smaller...


When $n$ is prime, solving for $e$-th roots modulo $n$ is easy, since it suffices to compute $d = e^{-1} \pmod {n-1}$ and then $s = m^d \pmod n$. If $n$ is not prime, but is instead a RSA modulus (a composite integer that is the product of two big primes), then the problem becomes apparently hard (in the sense that we don't have a clue how to do it efficiently) and is known as, indeed, the RSA problem.

The most efficient known methods to break the RSA problem, for non-special values of $m$ (e.g. the values which result from the padding step in standard RSA encryption and signatures), rely on integer factorization. If you can factor $n$ into its prime factors, then the RSA problem can be solved efficiently. Note the important point: we do not know if the RSA problem is equivalent to factorization; the RSA problem cannot be harder than factorization, but it might be easier. It is just that, right now, we do not know any RSA-breaking algorithm which is more efficient than factorizing the modulus.

The most efficient known method for integer factorization is GNFS, whose complexity is expressed as a barbaric-looking equation which you will find on the Wikipedia page. This is asymptotic complexity, so it does not given readily applicable results for two reasons:

The expression is valid for a big enough modulus; it does not tell whether a specific modulus length (say, 1024 bits) is sufficient for the expression to be at least approximately correct.
In practical terms, we want to express attack complexity in terms of dollars, not operations. In particular, the mathematical expression speaks only on CPU cost, not on memory cost, and says nothing about parallelization.

For big cracking jobs, a key to efficiency is how well we can split the problem into individual units which can run in parallel of each other, and how much data they have to exchange with each other. Heavy clusters achieve a lot of raw power through a lot of parallelization, which works wonders for, say, meteorological simulations, but not so much for integer factorization.

Roughly speaking, GNFS consists in two main phases, the sieve and then the linear reduction. The sieve is amenable to some rather high level of parallelization. For big integers (say, 1024-bit), the linear reduction appears to be the bottleneck. It is very hard to parallelize, and our best method so far is to find a big computer with an awful lot of very fast RAM. Existing "supercomputers" are ill-suited for such jobs. In fact, baring some non-trivial algorithmic enhancement for this phase, breaking a 1024-bit RSA modulus will require special-purpose hardware which exists only theoretically (we have plans, but turning plans into silicon takes money, time, and a lot of extra thinking).

Some people have tried to estimate how much this would all cost, and compared that to the cost of breaking a symmetric key through brute force (there again with dedicated special-purpose hardware). The result depends on a lot of parameters, including how much developers are paid (academics tend to think in terms of "developer = PhD student = free") and how many keys you try to break (hardware can be reused). Depending on who does the estimate, a 1024-bit RSA modulus will be deemed "as robust" as a symmetric key in the 75 to 85 range, meaning that it would cost the same to break it (note that this range hides a 1000-times factor !).

This site is the usual reference for pointers to the relevant papers.


Is RSA signature as strong as the RSA encryption?

Breaking RSAES-OAEP encryption for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization.  (Likewise RSA-KEM, which is much simpler.)

Forging RSASSA-PSS signatures for generic hash functions can't be much easier than computing odd roots modulo a large composite of unknown large prime factorization.  (Likewise RSA-FDH, which is much simpler.)

(Forging Rabin-Williams signatures—which involves square roots, not odd roots—for generic hash functions is as difficult as factoring a large composite of unknown large prime factorization.)

This is the story for the individual cryptosystems RSAES-OAEP under a key independent of RSASSA-PSS under another key.  The security of a composite cryptosystem (RSAES-OAEP, RSASSA-PSS) under the same key, in which the adversary can witness decryptions and signatures of arbitrary messages, requires its own analysis: security of RSAES-OAEP and RSASSA-PSS individually does not imply security of the composite scheme.

The standard pathological example, in the scheme I like to call do you even RSA, bro‽, is that if I want to decrypt a ciphertext $c \equiv m^e \pmod n$, and if I can ask you to sign the message $c$, then your signature is $s \equiv c^d \equiv m^{ed} \equiv m \pmod n$, so you just unwittingly decrypted $c$ for me.

Are there attacks on (RSAES-OAEP, RSASSA-PSS) under a single key?  Unlikely, but I don't have a handy citation for a reduction of security to the RSA problem.


Key length is the length of the key. It's a term whose meaning has evolved over time; these days, it typically means length in bits. With digital symmetric ciphers, it's fairly simple, because those tend to have a key that's just a string of some number of bits, and any string of that length is a valid key. With RSA, it's more complicated - the key has a bunch of elements, and can be written in various formats or with more or less info. With algorithms like that, there's generally some standard thing whose length is the key length (with RSA, it's the modulus).

The key space is the set of all possible keys. With symmetric ciphers, where any string of $n$ bits is a valid key, the key space has $2^n$ elements. With asymmetric ciphers, it's more complicated.

With monoalphabetic substitution ciphers, you have $26!$ keys, but key length depends on how you're expressing the key. If you compress the key as much as possible, you can fit it in 89 bits ($2^{88}<26!<2^{89}$), so if you want to directly compare key length with other symmetric algorithms (to talk about brute-forcing) you'd say it has an 89-bit key. Expressed another way, it has a 26-letter key, but not all 26-letter keys are valid keys (AA...AA isn't, for instance). But letters are not bits; if each letter is encoded in 5 bits, this is a 130-bit key, but very few of the 130-bit keys are valid. That's why you'd look at the smallest you could possibly make the key, which is 89 bits.

This is actually reasonably long; it's weak by modern standards, but in the 1980s and 1990s would have been fine. The issue is that you don't attack it by brute-force, but by cryptanalysis; that means key length is a bit beside the point.


How vulnerable is the C rand() in public cryptography protocols?

In the example you linked, the current time (specifically, a value representing the number of seconds elapsed since Jan 1, 1970 UTC) is used as the seed. If an attacker knows which year you generated your key, then that leaves only about 2^25 possible values for the seed --- and therefore only about 2^25 possible values for your key. At this point, he can guess your key pretty easily simply through brute force.

But let's say you find a better way to choose a seed, what then? Well, rand() will try to use this seed to generate a stream of random bits. But those bits won't be truly random, since they're based off a single seed value. So will they be close enough to random for cryptographic purposes? Probably not. Most PRNGs that aren't specifically designed to be cryptographically secure won't be good enough. They're designed for use in simulations and the like, not for times when there are smart and resourceful Bad Guys trying to do Bad Things.

OpenSSL seeds its PRNG using /dev/urandom (I'm not sure what it does on systems where this isn't available), and then uses its own PRNG to generate the random numbers. You can read a somewhat vague description here. (This is the first time I've looked up what OpenSSL is doing, and frankly, I find it a bit frightening --- it looks like someone is trying a roll-your-own-crypto, hash-functions-are-random-oracles approach. But I digress.)


Without the secret key, the signer can only be simulated through creative use of the random oracle (which is the only thing meaningfully in control of the simulator). Traditional signature proofs involve the simulator responding to random oracle queries in a way that will necessarily make their signatures validate, which they can do because they have control over the random oracle's input and can program it to have the right value specifically on the query needed for a particular signature.

If they program the wrong value, the simulation will produce an invalid signature (proof fails), and if they program the right value on the wrong query, they're also out of luck since the right query needs to have an independently random output from the attacker's view, so the simulator is forced to use the wrong value on the right query.

However in a blind signature the simulator doesn't get to query the random oracle for signatures, it has to sign the attacker's challenge. In effect, the attacker gets to behave as the random oracle. For common signatures which are also proof-of-knowledge of the secret key (at least when the public key is fixed in advance), this necessarily forces the simulator to have knowledge of the secret key.