How to find which padding method is used in block cipher (AES) encyption?

In general, you cannot, because padding makes sure the plaintext can always be recovered, so any valid padding method produces equally valid plaintext. For instance, suppose the last (decrypted) block is, in hexadecimal notation:

01:02:03:04:05:06:07:08:09:0A:0B:0C:0D:FF:00:00

The "natural" interpretation is that the padding method here might be "add an FF byte, then pad the rest with zeroes". But it could equally well have been "put the message at the end, insert an FF byte before, then pad with random non-FF bytes at the beginning", so that the message is in fact 00:00. Or it could have been "append a 05 byte, then pad with non-05 bytes", giving the message 01:02:03:04. You would rightly argue that the last two padding methods are unusual, but they are admissible.

In short, if you know absolutely nothing about the plaintext and do not make assumptions about possible padding methods, then you simply cannot know for sure which padding method was used. In other words, you cannot decrypt your message reliably without knowing the padding method. You can come up with a padding method that will literally produce any message you want (an easy way is to add a constant xor operation beforehand, though this is stretching the definition of "padding method").

However, in practice, there are only a handful of block cipher padding methods used in the real world, and they are easy to recognize - bit padding, which consists of adding a "1" bit (usually, a 0x80 byte for byte-oriented implementations) and padding with zero bits, PKCS #7, which adds N bytes of value N where N is the number of padding bytes required (from 1 to a whole block's worth, up to a maximum of 255 bytes), X.923 byte padding, and a few variants.

If you know features of your plaintext, it gets even easier, as you might be able to work out the end of the plaintext without needing to consult the padding. For instance, the plaintext could have a length record at the start indicating how long it is, in which case you can just read that and skip the padding entirely (assuming it is a standard padding method, of course). It might include a terminating character or symbol, the last block might not matter (if it carries redundancy data), etc, etc...

Or you can just try each one and see if what you get makes sense. That works, too.

This is assuming you only have the ciphertext, the ability to decrypt it (but not strip off the padding), and no metadata. Usually implementations will either hardcode the padding method used in their software (meaning if you know where your ciphertext comes from, you can look up the padding method there) or output it along with the ciphertext and IV in order to allow the receiver to actually decrypt the message properly, in which case it is given to you.

And, of course, if you have only the ciphertext and not even the IV or decryption key, then the answer is, of course, that you cannot know. Because if you could, then it would mean that features of the plaintext are not properly hidden by the encryption scheme used, meaning that scheme is (very) broken.


Which public key encryption scheme is re-randomizable? How can I re-randomize an encryption scheme?

I will start with an example and then comment on a natural general way to achieve re-randomization:

ElGamal: Let’s say we have a multiplicative written group $G$ (suitable for ElGamal) with public key $h=g^x$ and $g$ generates $G$ (or some prime order subgroup of $G$).
Any library that implements ElGamal encryption can do the following, although there may be no explicit function to do this: Take some ciphertext $(g^r,mh^r)$ for some message $m$ under public key $h$ and (since ElGamal is multplicatively homomorphic) do a component-wise multiplication with an encryption of the identity $1$ in $G$, say $(g^k,h^k$), with $k$ chosen uniformly at random. This gives you $(g^rg^k,mh^rh^k)=(g^{r+k},mh^{r+k})$, which is a re-randomized ciphertext to the original message $m$ under the public key $h$.

Generically, any public key encryption scheme that is probabilistic and homomorphic will let you re-randomize a given ciphertext by using the homomorphic property with a ciphertext to the identity of the respective group.

To generate the ciphertext of the identity element you obviously need access to the respective public key, i.e., you have to know under which public key the respective ciphertext has been produced. This can be avoided by extending the regular ciphertext with an encryption of the identity, as e.g. done in universal re-encryption.


Timestamps, as mentioned by user93353, are one possible answer.  The drawback is that they require synchronized clocks, which can't always be assumed.

Another possible approach to prove liveness (that is, that this isn't a replay) is for the receiver to select a random value (a "nonce"), send that to the server, and have the server sign the command concatenated with the nonce.  This also foils a replay; replays cannot work unless the receiver repeats the nonce.


If the adversary gets a signature on $m_1$, then it's true that the adversary could claim the signature is a signature on both $m_1$ and $m_2$, if $h(m_1) = h(m_2)$ (i.e., there is a collision). The adversary does not need the private key to make this claim, anyone holding the public key should be able to verify the signature.

The reason the adversary can successfully make this claim is that the signature does not actually sign the message, it signs the hash. So since $h(m_1) = h(m_2)$ the resulting signature is in fact both a signature of $m_1$ and $m_2$.

The reason why this is not usually a problem is that the hash function $h$ will be chosen as a cryptographic secure hash function meaning that it should be (practically) impossible for the adversary to find such a collision.


Securely start a client server connection without ssl/tls

if you want to use a password, SRP is probably a good choice.
alternatively, you could use ECDHE with ECDSA or RSA keys.
you should also use a MAC of some sort if you're using CBC (and encrypt then MAC). GCM or OCB would be much better choices.


Secret sharing over reals - Difficulty with Computer implementation

Recall the definition of a $(k,n)$-threshold secret sharing scheme is that any group of at least $k$ players (out of $n$ total players) can recover the secret given their shares.  The naive method for constructing a threshold scheme out of a non-threshold scheme (which was recommended in your previous question's answer) is giving every possible $k$-combination of the $n$ players a fresh $(k,k)$ sharing of the secret.  (I'll note that this is only practical for small values of $n$.)

It seems that you are stuck on the question of how to enumerate all of the possible combinations.  A good reference is this comprehensive answer on Stack Overflow, which mentions several algorithms.

Here is a quick Python script that will calculate all of the combinations for $k=3, n=5$:

import itertools

players = {1, 2, 3, 4, 5}
k = 3
for subset in itertools.combinations(players, k):
    print(subset)

With the resultant subsets:

(1, 2, 3)
(1, 2, 4)
(1, 2, 5)
(1, 3, 4)
(1, 3, 5)
(1, 4, 5)
(2, 3, 4)
(2, 3, 5)
(2, 4, 5)
(3, 4, 5)

This is of course a general algorithm that will work for any values of $k$ and any set of players.


Proving HMAC collision probability bounds?

The following is a method of calculating the probability using the random Oracle model, where the random Oracle is substituted for the HMAC function:

$\mathcal{A}^{\mathcal{O}}$ works as follows:

Generate $m_1$ and $m_2$ in whatever way

set: $tag = \mathcal{O}(m_1)$

output: $[m_2,tag]$

and observe that $\mathcal{A}^{\mathcal{O}}$ has trivial runtime and makes only one query to the oracle. $\:$

This leads to:

$\operatorname{Prob}(m_1 ≠ m_2 \text{ and } \operatorname{HMAC}(k,m_1) = \operatorname{HMAC}(k,m_2))= \operatorname{Prob}(\mathcal{A}^{\text{HMAC}(k,\cdot)} \: \text{succeeds})$


Is RSA secure enough to protect bitcoin private keys?

2048 bit RSA is currently and for the foreseeable future secure.
512 bit is currently not considered useful.
1024 bit RSA though not currently known to be cracked doesn't have enough security margins for comfort. Definitely not for securing $1B USD. Several years ago the cost of a machine which could break 1024 bit RSA in a year was a few million. Cost presumably went down. And it is likely certain 3 letter organizations have such machines.
The best way to attack RSA is by factorizing the composite $n$ using Number Field Sieve. and though $1B is a lot of money I don't believe there is a known design which will break 2048 bit RSA for that budget.
However, there are other attacks to think of. Starting with how you share your public key. How does your friend know your public key is indeed yours.
Then there are various side channel attacks on RSA, if the attacker has timing or power or noise measurements of you computing stuff with the private key that can help.
Then of course to protect a $1B secret there better be plenty of physical security around your key.
Should large quantum computers become available RSA may be broken also for significant key sizes. Personally I don't expect this any time soon but plenty of smart people disagree.


Invalidate a hash of a sequence of values given only the first N elements of a sequence?

Ok, here's how to generate a commitment to a sequence of values, where it is easy to open the commitment to any initial subsequence.
Here's how it works; suppose the values you are committing to are $M_1, M_2, ..., M_n$.  Then, the committer picks a random value $R$, and with a preimage-resistent hash function, recursively computes the sequence:
$$I_{n} = R$$
$$I_{k} =  \text{Hash}( I_{k+1}, M_{k+1}) \text{ for $k \in \{0, ..., n-1\}$}$$
Then, the commiter publishes the value $I_0$.
Then, when the verifier gets the values $M_1, M_2, ..., M_N$, the committer can prove those are the first $N$ values of the commitment by publishing the vlaue $I_N$.  The verifier can then compute the series of hash functions to verify that the end hash is the same as the commitment.

I see there is something called a Merkle Tree which seems to be able to prove set membership but it is not clear to me if this can prove order as well.

A Merkle tree can verify it; the above suggestion can be viewed as a Merkle tree (just a rather oddly shaped one), optimized for proving the initial sequence.  If you need to prove more general subsets (e.g. the values $M_N$ through $M_N'$), a balanced Merkle tree would be more flexible (but with higher complexity)

Also this seems to be potentially leaky if there is only a limited set of values.

Nope; because $R$ is selected randomly, the verifier cannot test a potential sequence of $M_i$ values based on the commitment.


While McEliece could be used like a block cipher, in practice it would much must slower than the standard hybrid approach.  McEliece might be relatively fast compared to other public key primitives, it is still quite slow compared to a symmetric cipher.

On the Ecrypt performance page, they list the performance of McEliece on various hardware platforms; the fastest median time they list to encrypt a block of data is 48937 cycles, and to decrypt is 827864 cycles.

Now, I can't find where they list the value of $k$ they used (which the size of the message being encrypted in bits); if we assume a $k$ of 2048 (which is somewhat larger than the current recommendations), a block of data would be 256 bytes, so we're encrypting at 191 cycles per byte, and decrypting at 3233 cycles per bytes.

Obviously, a symmetric algorithm can do considerably better.

In addition, as for the block cipher mode, well, it's not as straightforward as you might have hoped; McEliece isn't a block cipher; it's nondetermanistic and it has a larger ciphertext size than plaintext size.  Straightforward ECB may sound attractive with McEliece's randomization property, however encryptions of the same text still resemble each other, and so ECB would still have problems with repeated plaintext blocks.  As for CBC, well, you probably could truncate the previous ciphertext to make it match the plaintext size when doing the exclusive-or.  You might be able to define a variant of OCB modified to work with the differing plaintext/ciphertext block sizes.  That other standard modes look pretty hopeless; CTR, CFB, OFB all have both sides run the block cipher in encrypt; this won't work both because we would lose the public key characteristic of McEliece, and in any case, they rather assume that encryption is determanistic.

In addition, McEliece has the property of expanding the ciphertext (making it perhaps 30% larger than the plaintext).  While this is not unusual for a public key algorithm (indeed, most public key algorithms expand the ciphertext rather more), for a long message this would be considerably more expansion than with a standard symmetric cipher (which generally adds a fixed amount of data for IVs, padding, and MAC tags).

As for your question about random errors, well, that's not actually a problem.  Yes, random errors are inserted during encryption, but they are removed during the decryption phase.  Hence, the decryptor gets exactly the same message that the encryptor sent, and so there's nothing prohibiting you from using some type of block cipher mode (assuming you use one that can live with McEliece's not-particularly-like-a-block-cipher characteristics).


what could you do to make your custom algorithm as safe as possible

Try to re-use existing algorithms and research to the extent possible.

For instance, suppose you are designing a block cipher (for some reason), and you need some source of non-linearity. Some researchers have already gone to the trouble of finding s-boxes with optimal cryptanalytic stats and minimal implementation costs. There are analogous results for linear layers as well. If you incorporate the results of these works into your design, you can rest assured that they will probably not be the weakest links in your design.

At a higher level, you could also simply re-purpose an existing primitive such as ChaCha and make a hash function out of it (like BLAKE). Or you could re-purpose an existing hash function into a (inefficient) stream cipher, like many others have done/tried to do already.

You (or someone with the same question) might say:

  "But wait, if I do those things then I'm not really coming up with something of my own!"

I think it is safe to say: Symmetric cryptography is pretty much a solved problem by this point.*

You can play around with it if you want, but don't expect to come up with anything (good) that hasn't been done already.

A note about "security"

You need to define your threat model before you can conclude what is/is not good enough in regards to security.

If your only goal is to keep your messages confidential from your grandparents, then you can probably get away with a pretty low quality design (unless your grandpa happens to be Adi Shamir or someone similar of course).

If your goal is to keep your messages safe from nation-state level actors with billions of dollars for their budget and hundreds (or thousands) of cryptographers and mathematicians at their disposal, as well as good old fashioned thugs, then you should probably think twice about the expectations of your design.

If this is your threat model, this is where you need to really stick to pre-existing and battle-hardened constructions. An "oops" in your design could cost you or one of your friends/users dearly.

Note

A secure design and a secure implementation are not the same thing. Coming up with a design that is not broken is only half the battle - you also need a way to implement the design in a way that can't be exploited, and this is a non-trivial subject. Just knowing how to program does not mean that you can create a secure implementation of an algorithm.

Finally

If you read all of that and are still interested in doing it, please remember one thing:

Don't advertise your construction for others to use (outside of your friends who you have of course already informed that it is your own home-rolled construction and could break at a moments notice with no warning... right?).

If you set up a website preaching the virtues of your algorithm, the only people who would use your construction are people who don't know any better. This would be taking advantage of peoples ignorance at the expense of their safety for no good reason. If you did something like that in real life as opposed to cyber space, you would probably go to jail.

Advertising your design will probably just put you on a list of snake oil salesman and destroy your own reputation.

*Take my word for what it's worth, I'm just someone that likes cryptography.


On a lower bound for the birthday problem

The question's $\displaystyle C(q,N) \ge \frac{(q-1)^2}{2N}$ bound is wrong. That's incompatible with the well-known fact that for $N=q^2$ and large, $C(q,N)\approx1-e^{-1/2}\approx39.3\%$.

A correct bound is $\displaystyle C(q,N) \le \frac{(q-1)\,q}{2N}$, valid for all $q$ and $N\ge1$, and tight when $q\ll\sqrt N$.

Another correct bound is $\displaystyle C(q,N) \ge \frac{(q-1)^2}{4N}$ when $1\le q\le\sqrt{2N}$, which follows from the question's lemma.

See this answer for some derivations, but beware that the notation there is $(n,k)$ and $p_n$ where the question has $(q,N)$ and $C(q,N)$.


Protection Against Rainbow tables

First of all, design a log-in system so that users cannot set bad passwords and have protection against rainbow tables. One nice solution is using salt as in bcrypt.

Protection of Public Keys

Generate public-private pair for each user. Then, encrypt users private keys with their passwords and prefer Password Key Derivation Functions PKDF, so that you can prevent the guess and brute-force attacks on the user's passwords. You can use their password to encrypt and decrypt the key-encryption key.

Session Keys

When you want to send a message to a user, generate a session key and encrypt the message with AES crypto algorithm with an appropriate scheme, CBC, CTR or GCM, and secure the session key by the user public key with appropriate padding scheme.

Later on, when a user log-in the system, you can use their passwords to decrypt their private key and open the messages, if any, by extracting the session keys for each message. Hope this clear.


Can Alice prove that she *did not* send an unsigned message to Bob?

There is no way to prove that the message is fake without some trusted authority (such as GMail's DKIM) that automatically provides some level of non-repudiation without Alice being able to influence it (Alice can't send a message with DKIM disabled if she's using GMail).
Alternatively, Alice can habitually sign every message and ensure that those who are receiving those messages know that any unsigned message is not to be trusted. This only works if her audience is technically-minded and not easily swayed by emotive language and unfounded claims. Since you say that the community trusts Bob more than Alice, this is really a no-go.
From a cryptographic point of view, there is no way to prove that a message is not authentic as long as the message and signature can be separated in any way whatsoever.


Do any cryptography algorithms work on numbers besides primes?

Yes, very large primes, and I know my question is quite broad. I guess this is equivalent to asking if there are other very hard one-way math functions besides those based on primes. that don't rely on the fact that composites of two large primes are easy to create but hard to factor.

I don't think you should call them one way math functions. If RSA was one way then it wouldn't be possible to create RSA (only) encryption. More information here. RSA relies on a trapdoor function and traveling back without "a stair" is expected to be a hard problem. ECC also relies on primes to be secure, so it would also be affected.

Factoring and the RSA trapdoor function is already threatened by quantum cryptography. So generally you can simply look at post-quantum cryptography. So yes, there are problems that don't rely on primes for their security. Lattice based crypto is one of the most promising theories. Within this problem space a promising algorithm seems to be Ring-LWE. This is an algorithm based on the idea that . You can read a story about lattice based crypto here; as a writer you'll love the way it is written. So with regards to scientific research the impact would probably be minimal. A host of new students should be thought harder to learn primitives, but otherwise we already have replacement algorithms and protocols.

Being able to factor numbers won't affect most common symmetric primitives. So stream ciphers, block ciphers and hash functions would not be affected. Neither would any algorithms build from those such as message authentication codes (MAC), deterministic random bit generators and the like.

So what would be affected? Basically signature schemes used for authentication and non-repudiation. Asymmetric encryption (including hybrid encryption) and key agreement would be affected as well. That means that without RSA and ECC the whole PKI infrastructure would break down until an alternative such as lattice based crypto could be introduced.

So impact on the security landscape would be huge. Smart cards contain keys build on RSA and ECC. In general many quantum resistant algorithms have large memory requirements as well, so it may not be a simple task of replacing cards with new cards. SSL/TLS uses PKI for authentication, so the whole PKI eco-system would have to be renewed. A lot of hardware security modules (HSM's, devices used by e.g. banks and certificate authorities used to keep their keys secure) do not have any asymmetric primitives other than RSA or ECC. Embedded systems would need to be upgraded.

Basically if you currently would introduce an algorithm that would allow us to factor some numbers, the effect would be that the large institutions would try and migrate to other numbers still thought to be secure. There would certainly be a panic and a lot of speculation if those numbers would actually be secure. It would probably take some 3-5 years before we could completely migrate away from our current infrastructure to something that would not rely on prime numbers. The reluctance to move away from SHA-1 should be considered a strong warning about the resistance to change by the security industry.

This is one reason why NIST is already moving away from ECC crypto, even though quantum computing is still in its infancy.

Anyway, enough information to write a story about, although that story would be more a story about mayhem in the security world than a story about some genius coming up with a new algorithm to try and avoid it. That's what I would speculate to happen anyway.


Are modes of operation algorithms practical?

I know that some of them are pretty hard to crack, but since they are so commonly known is it even practical to consider using something like that as an encryption method considering the algorithms for encryption and decryption are commonly known (from a security perspective)?

In fact, this is exactly what we want.

Schneier's law

  Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

That is why it is crucial that the algorithms be made public. If the only information I keep secret from you is a relatively short key (128-bits isn't much), and you still cannot break the cipher, then one could argue that the cipher is stronger than one where you have to keep a few megabytes (the source code) protected.


"Kernel attack" on MinRank -- why do we guess $\left\lceil \frac k n \right\rceil$ vectors?

So we have $k+1$ matrices $M_0, M_1, \ldots, M_k \in \mathbb{K}^{n\times{}n}$. We are trying to find weights $\mu_1, \dots, \mu_k$ such that the rank of the weighted sum of matrices is smaller than or equal to some target rank: $\mathsf{rank}(-M_0 + \sum_{i=1}^k\mu_iM_i) \leq r$.

The Courtois and Goubin strategy is to select $m$ random vectors $\mathbf{x}^{(i)} \in \mathbb{K}^n$ (for $i$ from $1$ to $m$) and hope they all lie in the kernel of some combination of the matrices. If these vectors do lie in the kernel of suck a weighted sum, we can then easily find those weights by solving for $\mu = (\mu_1,\ldots,\mu_k)$ the linear system
$ \left\{ (-M_0 + \sum_{j=1}^k\mu_jM_j)\mathbf{x}^{(i)} = \mathbf{0} \right\} $
for all
$ i \in \{1, \ldots, m\}$.

This linear system consists of $mn$ equations and $k$ variables. If $k = mn$, then we expect there to be one solution. If $k < mn$, then the system might well be over-determined and might not admit any solutions, whereas if $k > mn$ then we might find several solutions rather than a single one. We are aiming for the case in which the system has one solution, so we must choose $m$ so that $k \approx mn$ holds as well as possible. Further constraints on $m$ are that it is an integer -- so we must round up or down -- and that it is different from zero -- because otherwise we have no equations. So the natural choice is $m = \lceil {k \over n} \rceil$.


How to show that this modification of CBC-MAC is insecure?

Consider the following chosen-plaintext attack on the modified CBC-MAC function:

Send $m_1$, $m_2$, $m_3$, receive $t_1$, $t_2$, $t_3$.

Send $m_1$, $m'_2$, $m'_3$, receive $t'_1$, $t'_2$, $t'_3$.

Send $t'_2 \oplus m''_3$, $m''_2$, $m''_3$, receive $E_k(t'_2 \oplus m''_3)$, $t''_2$, $t''_3$.

Then you know the following (message, tag) pair will verify:

Send $m_1$, $m'_2$, $m''_3$: the tag will be the concatenation of values you have previously queried for: $t_1$, $t'_2$, $E_k(t'_2 \oplus m''_3)$. Therefore you can generate a valid (message, tag) pair that has not yet been sent through the modified CBC-MAC algorithm. This can be generalized for any number of blocks.


I agree with e-sushi that PoW does work, however, the primitives used by HashCash are too friendly for adversaries. As the OP pointed out we need contextually bound challenge and response that cannot be reused or precomputed.

We cannot prevent the work from being delegated; but we can make the PoW much more expensive than an ASIC friendly hash function. The argon2 KDF family is well suited for this, specifically argon2d which was designed for PoW; whereas argon2i was designed for secret passwords.

The memory and cpu parameters may be tuned individually such that no real users are too inconvenienced and the server is not overwhelmed when under load.

Instead of requiring the PoW be computed 100% of the time, you might only require it while the server is under load. This may not apply to your use case.

  Whats the advantages and disadvantages of using plain hash and KDFs when used in POW?

Advantages:

Increase adversary costs

Disadvantages:

Inconvenience users (less than a captcha)
More code running on the user's client, inconveniencing users who opt to disable JavaScript
Drain the power of user's mobile devices
Adds additional computational costs, increasing power consumption for minimal benefit

  Besides replay, pre-computation, what are the other attacks that must be considered in designing a secure proof-of-work system?

Remote delegation to unsuspecting users (like recently cryptominers on government sites)
Deniable of service. The adversary may produce fake solutions without trying. The server still performs the computational costs.

Alternatives:

Enable the user to send money as a micropayment. This scale will require a high performance ledger, or better many ledgers. On the other hand, an adversary may have enough money to burn, possibly stolen.


Isn't the use of public key encryption a redundant step in Encrypting File System, which doesn't improve the security of the File Encryption Key?

[Or] I'm missing a point?

Actually there are at least two reasons why you would want to involve public:

First using public key allows you to rather precisely map permissions into keys. So suppose you create a file, how do you get the new file key to everyone who should have access to it? Public key encryption solves this readily. Or suppose you remove access to a file for somebody, you obviously need to pick a new file encryption key, so that that person doesn't have access anymore even if they accessed in the past. How do you communicate the new key? Public key encryption.

Second reason is mostly historic. EFS was mostly designed for corporations and governmental use. They already had smart cards deployed or saw the obvious usefulness of smart cards. But these smart cards typically don't support symmetric key encryption, but only public key encryption, so if you wanted to integrate smart card based authentication into the process, you'd have to involve public key encryption at some point.


Why is $h(H, m) = E(m, H) \oplus m$ insecure?

Well, the problem with $h(H,m) = E_m(H) \oplus m$ is that it makes the preimage attack easier than we'd expect; with a 128 bit hash, we'd hope that it'd take around $2^{128}$ attempts to find a preimage; with this compression function, we can find a preimage with only around $2^{64}$ effort.

This happens because this compression function is reversible; with a fixed m and a target value J, as one can efficiently find the H with $h(H,m)=J$, namely, $H = D_m(J \oplus m)$ (where $D_m$ is the decryption operation using $m$ as a key).

Here is how we use this property to find a message that hashes to $J$:

We select $2^{64}$ distinct initial blocks $m_1, m_2, ..., m_{2^{64}}$, and compute the $2^{64}$ values $h(H_0, m_i)$, where $H_0$ is the fixed IV of this hash function
We select $2^{64}$ distinct final blocks $n_1, n_2, ..., n_{2^{64}}$ and compute the $2^{64}$ values $h^{-1}(J, n_i)$, where $h^{-1}$ is the compression function run backwards.

Search the two lists for a common value; assuming a 128 bit hash, a collision is likely.  If we find a pair with $h(H_0, m_i) = h^{-1}(J, n_j)$, when we have found a message $m_i || n_j$ which hashes to $J$.


Implementing Secure multi-party computation for online website

What exactly constitutes the "private key"?

If the key is the private part of an asymmetric encryption key pair, such as for RSA, and you'd hence also like all three parties to know the public key, then what you're looking for is called distributed key generation. You can then also use threshold cryptography and let the parties compute private key operations – decryption and signatures – without any single party needing to have access to the full key.

If the key is any random string of bits (e.g. the key for a symmetric block cipher), and you want a secret sharing of this random value, what you want is called correlated randomness (see e.g. this paper by Ishai et al. from 2013 for its uses in multiparty computation). In this 2-out-of-3 case, you can simply let each party $i \in \{1, 2, 3\}$ generate a random $k$-bit string $r_i$ and send their value to the "next" party (i.e. party $i$ sends $r_i$ to party $i+1 \bmod3$). Define $r = r_1 \oplus r_2 \oplus r_3$ to be your random key. Then any single party has only two of the values $r_i$, and hence does not obtain any information about $r$, but any two parties can reconstruct $r$.


Security of very simple XOR with random?

Your cipher is a synchronous stream cipher build on a random number generator.

For cryptographically secure random number generators (CSRNG), this is a secure stream cipher.

The problem is, that your random seed is way too small for any security. Trying all possible seeds and seeing if the decryption result makes some sense (assuming the plaintext makes sense) is possible in some seconds, I guess, even with non-specialized hardware.

Also, the random number generator used by your program is quite likely not a CSRNG (otherwise it would not have a 32-bit seed), so there might even be other ways to attack it.

Also, as you don't have any initialization vector, you have the usual stream cipher problem: As soon as you reuse a key twice, you have the same keystream twice. Then the attacker can XOR both ciphertexts and get $c_1 \oplus c_2 = (p_1 \oplus k) \oplus (p_2 \oplus k) = p_1 \oplus p_2$ – and from this we often can extract parts of the plaintexts, especially if these are longer messages.


What operation does $\|$ denote in ANSI X9.63 KDF?

It means concatenation. Z, Counter, and SharedInfo are three bitstrings which are to be concatenated before hashing. The [ ] around SharedInfo means it may be absent in which case you would use an empty string instead. (Since concatenating an empty string to the end yields the same result as not concatenating anything.)


What are linear and non-linear elements in cryptography?

A mathematical function $f$ is linear if it is of the form $f(t) = c + g(t)$ where $c$ is a constant and $g$ has the property that $g(a + b) = g(a) + g(b)$.  (Strictly speaking, in math one usually considers only $g$ to be linear and $f$ to be merely affine, but we don't make that distinction here.)  We also say that a function $\phi(s, t)$ of two arguments is bilinear, or again just linear, if for each $s_0$ and $t_0$, the functions $t \mapsto \phi(s_0, t)$ and $s \mapsto \phi(s, t_0)$ are linear.

  Exercise. Prove that the function $(s, t) \mapsto s + t$ is bilinear.

If we're talking about real numbers, like 0, −3, 1/48, $\pi$, etc., linear functions are of the form $f(x) = mx + b$ for constants $m$ and $b$, which you may recognize as the equation of a (nonvertical) line.  But we don't have to talk about real numbers; we can consider integers too, or even the remainders of integers after dividing by 2 (‘modulo 2’), where $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, and $1 + 1 = 0$.  The linear functions in this case are still of the form $f(x) = mx + b$, but the only two possible values for $m$ and $b$ are 0 and 1, so there are only four such linear functions.

We can also do addition and multiplication of polynomials, or of matrices of higher dimensions.  Each space has its own notion of linear functions, defined in terms of that space's notion of addition.  Linear functions are easy to compute—and easy to invert, or at least partially invert: in spaces where we have a notion of division (like rational numbers), we can recover $x$ from $f(x)$ by $x = (f(x) - b)/m$; in other spaces, like matrices, we have easy algorithms like Gaussian elimination to solve linear systems.

Suppose you have a string of bits, say 10110 or 00111.  One way to interpret the bits is an integer, in this case 22 or 7 (in decimal).  Another way is to interpret the bits as a polynomial with coefficients modulo 2, in this case $x^4 + x^2 + x$ or $x^2 + x + 1$.  If we add these in their respective spaces and convert back to a string of bits, we get different answers:

\begin{gather}
  22 +_\mathbb Z 7 = 29 \longrightarrow \mathtt{11101} \\
  (x^4 + x^2 + x) +_2 (x^2 + x + 1) = x^4 + x + 1 \longrightarrow \mathtt{10011}.
\end{gather}

  Exercise. Why did the $x^2$ term disappear?

Here I have labeled the integer addition operation as $+_\mathbb Z$ and the polynomial modulo 2 addition operation as $+_2$.  We could also write both sides of the equation as a string of bits; when we use $+_\mathbb Z$ and $+_2$, we may get different answers, as strings of bits:

\begin{align}
  \mathtt{10110} +_\mathbb Z \mathtt{00111} &= \mathtt{11101} \\
  \mathtt{10110} +_2 \mathtt{00111} &= \mathtt{10001}.
\end{align}

  Exercise. Is there another name for $+_2$?

  Exercise. Find two bit strings $s$ and $t$ such that $s +_\mathbb Z t = s +_2 t$.

Although $+_\mathbb Z$ is linear (or, more precisely, bilinear) in integer addition, it is not linear in polynomial modulo 2 addition—in other words, although, e.g., $t \mapsto s_0 +_\mathbb Z t$ is linear over $+_\mathbb Z$ meaning it is of the form $t \mapsto c +_\mathbb Z g(t)$, specifically with $c = s_0$ and $g(t) = t$, this function is not of the form $c +_2 g(t)$ for any $c$ or $g$.  Conversely, $+_2$ is linear in polynomial modulo 2 addition but not in integer addition.

In other words, xor is linear in polynomial modulo 2 addition, but not in integer addition; conversely, integer $+$ is linear in integer addition, but not in polynomial modulo 2 addition.  When you combine the two—e.g., consider the function $(u, v, w) \mapsto (u +_\mathbb Z v) +_2 w$—the result is a function that is nonlinear in both spaces, which means it does not admit any neat algebraic simplification or inversion like $(f(x) - b)/m$ or Gaussian elimination.  This in turn means that cryptanalysis can't take advantage of neat algebraic simplification or inversion, and so may be much harder.


Is it safe to convert a 256-bit nonce into a 192-bit nonce by SHA-256ing and then truncating it?

XChaCha20 requires a 192-bit nonce size. As a rule of Stream ciphers, the nonce should not be repeated under the same key.
Note that; Daniel J. Bernstein is pointed in the XSalsa20 article for Salsa20 which has 64-bit nonces.

There is a standard argument that a 64-bit nonce is long enough. Nonce
security does not mean unpredictability; it means uniqueness. Applications can
generate a nonce as a monotonic timestamp or simply a counter 1,2,3,...

and

There is also a standard counterargument. Counters might sound simple but
are sometimes mismanaged by applications, destroying security. Rather than
blaming the application for this failure, we can append random bits to the nonce,
adding protection that is likely to succeed even if the counter fails.

For Salsa20 using random nonce is not secure since the birthday bound on the collisions. One expects at least collision after $2^{32}$ random generation with 50% probability.
For XChaCha20 using random nonce is secure since the collision probability becomes nonnegligible (50%) if you can encrypt $2^{96}$ messages under the same key. Since it is not possible, you will change, you should, way earlier than that.

I'd expect a 196-bit nonce derived from a 256-bit nonce by computing the SHA-256 hash and then truncating it to 24 bytes to behave like an approximately uniformly randomly generated 196-bit nonce and hence be good enough for using it e.g. as a nonce for XChaCha20-Poly1305 encryption.

If the input to the SHA256 is a good random source then we expect the usual collision probability. Except it doesn't guarantee that there is no repeat, however, that is negligible.

(This was in the comments by OP) In the extreme case the input is just a counter.

Your proposition is similar to building a CTR mode encryption from hash function. As long as the hash function has pseudo randomness properties the construction will work (most modern hash functions have this property). It will work, too.
You have the same problem as mentioned by Bernstein, the mismanagement of the counter that usually occurs system failures. The system may start from a previously used counter that will regenerate the same SHA256 values and that is insecurity may be more than one nonce.
Generate the nonce like $$nonce = random \mathbin\| counter$$ is a better and safe way. Now, the mismanagement of the only counter is handled.
Or, generate the nonce like $$nonce = random \mathbin\| \operatorname{SHA256}(counter).$$


Possible combinations of 8 digits, 6 upper case letters, 2 distinct numbers

Close.

It's $26^6 \times 90 \times 8 \times 7 / 2$; the $/2$ is there because having the digits appear in locations 1 and 3 is exactly the same as having the digits appear in locations 3 and 1, and hence there are only 45, not 90 distinct locations where the digits may appear.


A core component of Bulletproof is a "range proof". Since Bulletproofs are designed to be used in the blockchain setting, it is important for the range proof to be non-interactive. The one used in Bulletproof is obtained by taking an interactive range proof and then compiling it into a non-interactive one using the Fiat-Shamir transform. The random oracle is used to establish the soundness of this transformed protocol. In practice one would instantiate this random oracle with a concrete hash function (say SHA-$3$).

Now, to answer your question whether a random oracle is necessary, it is not clear and is an active line of research. It has been shown that in some cases it is possible to instantiate the Fiat-Shamir transform with concrete hash functions (e.g., the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19]).

[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


RSA Key Differences (OpenSSL CLI vs. OpenSSL/ssl.h C function)

They're both in ASN.1 (DER) format, however they have different contents.

The OpenSSL version has an outer formatting that effectively states "this is an RSA public key", following by the actual raw public key key (which is listed as a 'bitstring' in the ASN.1 parse).  If you were to parse the bitstring as ASN.1, you'd see the public key, expressed as a sequence of two integers.

In contrast, the C program just has the ASN.1 raw public keyl that is, it's just a sequence of two integers, the values for $n$ and $d$.

The additional outer formatting included in the OpenSSL version accounts for the additional 25 bytes.


Figure out chosen-plaintext-attack in Zerologon attack

So just to be clear, these are not properties of the CFB8 scheme itself - rather, they exist specifically in the context of this attack due to this issue with how windows uses (..or used) the scheme:

The ComputeNetlogonCredential function, however, defines that this IV is fixed and should always consist of 16 zero bytes. This violates the requirements for using AES-CFB8 securely: its security properties only hold when IVs are random.

Regarding proof of the first claim, this excerpt explains it a bit more clearly:

Because AES is a high-quality cipher with no known statistical biases, you can put in any input and encrypt it with any key, and the chance of each individual bit in the output being zero (or one) is 50%.
Every output bit’s value is like a digital coin toss.
So the chance of the first output byte being zero is the same as the chance that the first 8 output bits are all zero, which is 50% × 50% × 50% … eight times over (50% is just another way of writing 0.50, which is the same as 1/2).
50%8 is 2-8, or 1/256.

The second claim is an extrapolation from the first and I'm afraid my math skills don't reach that far.


Is there necessarily an infinite number of inputs to any given output in a crypto hash function?

For any given output, obviously there are multiple inputs.

This is not true. Namely, for any is not true. There are outputs such that multiple inputs produce them - this is consequence of pigeonhole principle. But we cannot claim that this holds for any output for any hash function. This can be true for some specific hash function only.

  ... proof that there exists no crypto hash function ...

There is no proof because this statement is simply false. Here is a simple example of a hash function that has many hashes that have finite number of preimages.

function hash(x){
    if (x.length <= 64) {
        return
            '1' ||
            '0000000000000000000000000000000000000000000000000000000000000000' ||
            sha3(x);
    } else {
        return
            '0' ||
            sha3(x) ||
            '0000000000000000000000000000000000000000000000000000000000000000';
    }
}

The number of inputs that produce hashes starting with '1' is finite.


Why are obfuscators generally defined to be probabilistic algorithms, rather than deterministic ones?

Let's consider the notion of IO (indistinguishability obfuscation). Informally, the definition states that for every two circuits $C_1$ and $C_2$ such that $C_1(x)=C_2(x)$ for every $x$, it holds that $IO(C_1)$ is computationally indistinguishable from $IO(C_2)$. That is, a distinguisher knowing $C_1$ and $C_2$ and given an obfuscation of one of them cannot guess which with probability greater than $1/2$.

Now, assume for a moment that $IO$ is a deterministic algorithm. In addition, assume that $IO$ does not map all equivalent $C_1,C_2$ to the same concrete output (if it could do this, then we would have an efficient way of determining that circuits compute the same function, which is co-NP complete). Then, the distinguisher could simply compute $IO(C_1)$ and $IO(C_2)$ and compare to the obfuscated program that it received. With this strategy it knows which circuit was obfuscated with probability 1. Thus, $IO$ cannot be deterministic.


Does using a snapshot of running PID on Linux provide enough entropy?

No, it doesn't; not unless you want to have $2^{15}$ bits of non-cryptographically secure random token - the output of the $RANDOM function of bash.

How PID's are created depends on the operating system. The only other information is the starting time really. Neither of those can be seen as random and is easy to guess and even to influence.

There have been some proposed patches to make PID's more random in Linux but they were rejected by the kernel maintainers. They are kind of chicken-egg anyway; to create random ID's the kernel would need to have a good random number generator which you could employ yourself.


persisting sensitive binary data encrypted (+integrity)

There are at least two ways to do this:

Using asymmetric encryption. This may be advantegeous if you want to use hardware-enforced keys or something like that. However, such keys tend to be "weak" for long-term storage (in a theoretical sense).
Using symmetric encryption. This may be advantegeous as you can easily use a password or a hardware-enforced AES key to do this. However such devices are much rarer than those supporting e.g. RSA.

Now classically you would do the following:

Encapsulate the data's symmetric key using asymmetric and / or symmetric encryption and / or key derivation methods.
Encrypt each block using said data key and an authenticated encryption mode (e.g. AES-CCM, AES-GCM or AES-EAX), using the index as the nonce.
If you use asymmetric encryption: Compute a signature over the complete ciphertext and store it for later verification (because an attacker could use the public key to just replace the data).

Now the data is immune to re-ordering attacks (because the authenticated nonces would miss-match).


The main problem here is that signature is malleable. Given signatures on $m_1$ and $m_2$ allows you to construct a valid signature on $m_1m_2$ by multiplying the signatures. Therefore, the answer is no. When you hash you don't have $H(m_1m_2)=H(m_1)H(m_2)$, so hashing destroys this algebraic structure that connects messages and signatures.

EDIT: I'm assuming the question is whether you can sign without hashing when the messages to be signed are already intergers modulo $n$, i.e. you don't need to hash your messages to make them elements of this group.


Crypto that takes n days to solve depending on how many bytes are missing?

You can try 20 billion DES keys per second on a single Nvidia Geforce GTX 1080.

Assuming (roughly) that another algorithm (with much higher keylength than 56-bit) is equally as fast, the bitlength you want for the key is:

$$\log_2(\text{NumberOfSeconds})+\log_2(\text{NumberOfGPUs})+34$$

where $2^{34}\approx 16 \text{ billion}\approx 20\text{ billion}$.

If you want some example numbers, let's do the math:
If we want to wait approximately 3 days (that's $24\times 60^2\times 3$ seconds) and can get hands on maybe the equivalent of 5000 such GPUs using a botnet, that yields about $64$ bits which sounds very reasonable.

What you could do with this is to take AES-128 und give 8 bytes using (8?) puzzles and let them brute-force the remaining 8 bytes. Every unknown byte will increase the brute-force workload by 256.

So TL;DR: Brute-force of 8 bytes (give or take a few bits) sounds like what you're aiming for.


How should one create an ephemeral Diffie-Hellman private key?

It would be nice to just get a bunch of random bytes and make those
  into a big integer than to have to uniformly pick a big integer within
  a specific range.

If you pick a uniformly random value from a bigger set and throw away everything that is not in your range until you find something you will get a uniformly random value in that range.

If however you do something like taking a random big integer and reducing it modulo $q-2$ to put it into your range you will skew the distribution and you will lose some security.


SHA-256 : Finding two strings that the first n bits of hash value are same

If you use the same size input, there may no be a collision at all. It is better to increase the input size like double of $n$. Note that the input is padded so that the input to $\operatorname{SHA256}$ it is multiple of 512-bit.

  Keep generating two random string

You need to store all the hashes to see that there is a collision. If you don't store you may miss it. Since you are not storing, you can use an LFSR to generate uniquely, if you want.

Actually you should use Rho Method for this one, which is a low memory collision search.

Pick a random hash value $h_1=h_1'$
and compute $h_2 =\operatorname{SHA256}(h_1)$ and $h_2' = \operatorname{SHA256}(\operatorname{SHA256}(h_1'))$.
Continue to iterate $h_{i} = \operatorname{SHA256}(h_{i-1})$ and $h_{i}' = \operatorname{SHA256}(\operatorname{SHA256}(h_{i-1}'))$

These two sequences will eventually enter into a cycle, and there will be a tail (rho-shape $\rho$). The cycle start is the collision point.

Note: this algorithm is also known as Robert W. Floyd's Tortoise and Hare which is used for cycle detection.

  Hash the two random string and store in a dictionary

This can be better since hash tables can effectively search, up to amortized $\mathcal{O}(1)$-time Generate the hashes and look upon the hash table - if exist you have found, not exist then insert the new hash.

The performance is really depending on the value of $n$. If the value of $n$ is too big, you may choose the Rho method. Since when the needed memory becomes larger than your system memory, you will be slowed.

  Loop the dictionary to check if there is two hash value share the same first n bits and return the two strings as a result

In this case, you already store the data in the Python dictionary. Python dictionary is already implemented by hash tables. Therefore, you only need to use Python's existing dictionary functionalities.

If you want to use a double dimensional array (or similar structure) to store the value and hash you  You first calculate all of the hashes up to a predetermined amount $n$, then sort the array with an $\mathcal{O}(n \log n)$-time sorting algorithm. After the sort, all you need to iterate and see that are there any adjacent elements is the same. This can be done in $\mathcal{O}(n)$-time


Does the Richard Sorge cipher still provide good security?

Short Answer: No
But it depends on what you mean by good. If pretty lousy by modern standards is your idea of good enough, and you want to use it on your little brother, then this cipher may exceed expectations. Sorge's cipher was powerful in its day.  However, it is not a one-time pad; that is, it never offered perfect security. The Sorge cipher is not a modern cipher, and almost no one would ever use it because it depends on the obfuscation of the key, and security by obfuscation is anathema to modern cryptography.
What is the Sorge Cipher?
In The Codebreakers (Macmillan, 1967, p. 650), David Kahn points out that the Sorge cipher was regarded as unbreakable, a triumph of cryptography.  It was a mainstay of Soviet espionage during their days of stunning successes.  Richard Sorge has been described as the best spy who ever lived, his work impeccable.
No one that we know of ever broke it while it was being used.  Kahn says, "it remained hermetically sealed against cryptanalysis."

It brought the old Nihilist substitution to a peak of perfection. It
merged the straddling checkerboard with the one-time key.

A Straddling Checkerboard

The innovation of the Sorge cipher was to assign the highest-frequency letters of the English alphabet (yes, communications were in English) to single numerals in the straddling checkerboard.  The phrase "a sin to er(r)" gives us the seven most commonly used English letters: A, E, I, N, O, R, S.  Matching these to single digits helped flatten the distribution of letters and shorten the messages, which made radio transmission faster and thus safer.
The Sorge cipher's straddling checkerboard was not partly alphabetical, as seen in the example above.  It was made with a keyword in such a way as to muddle the order of the letters.

Clausen [Sorge's radio operator] used SUBWAY. The encipherer wrote
this out, followed by the rest of the alphabet in rows beneath it,
with a full stop and a letter-number switch sign at the end. Then the
digits 0 to 7 were assigned to ASINTOER as they occurred vertically
in columns from left to right. Finally the two-digit groups from 80 to
99 were assigned to the remaining letters and symbols, also
vertically:

Which results in this checkerboard (Kahn, p. 651):

Which gives this fractionation to the plaintext (Where is 106 Division):

Now for encryption with a one-time numerical key from a book
The key was chosen "randomly" in Moscow from a book about railroad construction in Luxembourg in 1931. Where one started in the tables of statistics had already been agreed upon. Non-carrying addition produced the ciphertext.
There are many obscure books.  Every book on our planet has not been scanned yet.  Would such a key provide "good" security?  Probably not, and its strength is certainly nowhere near perfect or anything resembling the strength of modern encryption.  This cipher method depends on obscurity, which is a critical mistake.


Improve security of transposition ciphers

First determine the permutation domain. If $L_2 > L_1$, then the cipher is broken by $\lceil  log_2 (L_2) \rceil$ pairs of plaintext/ciphertect. The security improvement is small, as the attacker only needs to use $\lceil  log_2 (L_2) \rceil - \lceil  log_2 (L_1) \rceil$ additional pairs to find the key.


Multiple-prime RSA; how many primes can I use, for a 2048-bit modulus?

If we consider an RSA modulus $N$ of $n$ bits ($n=2048$ in the question) product of $k$ primes of about $n/k$ bits, how high can be $k$ without loosing security? That's a problem studied even before Multiprime-RSA was named, with no definitive answer other than: we can't err on the unsafe side with $k=2$.

Why would we want $k>2$?

For classical multiplication algorithms implemented in software or hardware with fixed word size (which covers all hardware and many software implementations I know), using the standard method described here, there's a potential effort saving of the RSA private-key function by a factor up to about $k^2/4$ compared to $k=2$, and a lot of that speedup is achieved in practice; plus it allows simple and efficient parallelization on $k$ cores.
When there is hardware to perform modular multiplication that enforces a maximum modulus width, increasing $k$ is the only way to increase $n$ (thus security against factoring) while making any use of this hardware resource.
The algorithms [GNFS and previously (MP)QS] that hold factoring records for $k=2$ have run time dependent of $n$ with no influence of $k$; thus the security against factorization attacks using these algorithms remains unchanged when $k$ grows with constant $n$.
Given a public-key and its certificate, and (side-channel-free) access to a black box implementing the RSA private-key function $x\mapsto x^d\bmod N$, the best known way to tell if $k=2$ involves factoring $N$; thus we can increase $k$ without fear of interoperability with devices concerned only with the public-key.

Why would we want to summarily stick to $k=2$?

That's mandated by US standard FIPS 186-4 ever since it includes RSA, and by reference for compliance to some or all of FIPS 140; by French official RGS recommendations; and by pretty much every security authority making recommendations on key size as listed by this reference website, last time I checked; and then some.
In countless cases $k=2$ is the only thing compatible with what's around. One example out of many, in the field of Smart Cards: the Java Card 3 Classic API.
While PKCS#1 standardizes Multi-Prime RSA and even a private-key exchange format for that, there are devices, including some claiming PKCS#11 compatibility, that do not support it. If you want to move the private-key to a different device, or even make a backup of a key generated on-board in a future-proof format, beware!
Some modular exponentiation hardware or software wants prime factors $p$ which exact bit size is multiple of something (usually a power of two, e.g. 64); that's another interoperability hurdle (and in the context of $n=2048$, $k=3$, being a multiple of 64 would force one prime to be 640-bit, rather than 683-bit). Note: it can be worked around by reducing modulo an appropriate multiple of the prime during modular exponentiation, then doing a final reduction.
There has been patents (now expired) delivered at least in USA and Europe (US 5,848,159, US 7,231,040, EP0950302) that created fear, uncertainty and doubt as to whether using Multiprime-RSA cames with a legal risk.

What other things are to be considered when pondering $k>2?$

Main one, by far: the effort (by any measure) of factorization attacks using ECM increases (faster than polynomially) with $n/k$, thus tremendously decreases with $k$ for constant $n$. And the adversary (which, we must assume, knows $k$) has the choice of the factorization method, and will choose ECM if advantageous. All the literature I know (listed below) on deciding $k$ thus aims at choosing it as high as possible so that the expected effort (or runtime, cost..) of ECM is no lower than that of GNFS, sometime with a projection of these expected efforts in the future; the $k$ of the crossover is of course rounded down.
ECM is easy to distribute on many commodity computers that need almost no communication with each others, when as far as we know the matrix step in GNFS requires a heavily connected supercomputer with enormous amounts of memory (or perhaps, spending some binary orders of magnitude more computing power in the sieving step that dominates the computing effort for current parameterizations). That somewhat invalidates comparisons between GNFS and ECM that consider computing work, effort or runtime, rather than some attempted measure of cost [Comparatively minor related aside: ECM reportedly can take advantage of GPU; but that might not be much of an argument, since GNFS could in the future benefit from GPU, by way of using ECM internally].
Since the advent of computers, and even in this century, we have not had a precise crystal ball when it comes to future runtime (much less cost) of published factorization algorithms (and that can only be worse for their relative cost, or if we consider unpublished improvements or algorithms). Whatever comparison we make between ECM and GNFS, the more in the future we want security, the more margin we should take on the ground of these uncertainties, and shift the balance towards lower $k$ (before rounding).
AFAIK, no implementation of Multiprime-RSA has been checked for side-channel attacks by a certification lab. That's not a mere certification issue: it is not unreasonable to fear that either the smaller primes, or the final CRT step (necessary to get any speed benefit) makes an implementation more vulnerable to side-channel leakage. That's a potential issue at least in HSMs operated in non-trusted environments, and Smart Cards.
When using ECM, odds that the factorization will be found after a fraction $\epsilon$ of the expected work are about $\epsilon$ (for $2^{-20}\le\epsilon\le0.3$ and common ECM parameters). That's in contrast with GNFS and QS, where we simply can't get the factorization until the last few percents of the expected work. If we want residual risk $\epsilon$ that an adversary succeeds with a certain work, we should aim for at least that work for GNFS, and at least $1/\epsilon$ times that work for ECM; that shifts the crossover towards lower $k$ (before rounding). In security, there is no consensus on acceptable residual risk to known attacks, and I have seen such $\epsilon$ entirely ignored, or set from 5% (for an overall system) to $2^{-40}$ (for symmetric cryptography where admittedly there is no strong incentive to tune that).
When we want to generate $m$ keys, and the adversary would be content to factor any single one (as is often the case when the keys are used for authentication or signature in a machine-to-machine application), we should pay some attention to two other factorization algorithms: Pollard's p-1 and Williams' p+1. Problem is: with primes of size $n/k$ chosen randomly, these algorithms (especially the first) substantially surpass ECM on the standpoint of the ratio $\text{odds to factor}\over\text{runtime}$ for small $\text{odds to factor}$. Thus an adversary will get a benefit by trying Pollard's p-1, then Williams' p+1, on the $m$ moduli available, before using ECM; and can do so with benefit on a fraction of the expected work proportional to $m$. To confirm this: GMP-ECM practitioners use that strategy, with significant success for p-1, and to a lesser extend for p+1. Rather than assessing this risk, we can generate the primes $p$ in a way such that $p-1$ and $p+1$ have a known high prime factor, which makes these algorithms useless (that's feasible efficiently if not simply, e.g. as explained in FIPS 186-4 appendix B.3, which for $k=2$ mandates that for primes of 512 bits, but not 1024 bits).
It should also be taken into account in the balance that ECM is expected to require near $k$ times less work to factor a Multiprime-RSA $N$ than a random $N$ of comparable size with lower prime factor of size $n/k$.

References

Restricting to the current century, I know only 4 references that deal with finding a balance for $k$:

Arjen K. Lenstra: Unbelievable Security: Matching AES security using public key systems, Asiacrypt 2001 (alternate link).
Dan Boneh, Hovav Shacham: Fast variants of RSA, with abridged version in CryptoBytes, Vol. 5, No. 1, 2002.
M. Jason Hinek: On the Security of Multi-prime RSA, Technical Reports of the Centre for Applied Cryptographic Research (CACR) at the University of Waterloo, 2006 (alternate link).
Jean-Sébastien Coron, Aline Gouget, Pascal Paillier, Karine Villegas: SPAKE: A Single-Party Public-Key Authenticated Key Exchange Protocol for Contact-Less Applications (Financial Cryptography 2010 Workshops, pay-walled with free extract)

A recent answer!

The later reference briefly touches the nearly identical problem of the size of $p$ in unbalanced RSA (1. differs in the rounding to get $k$, 4. may differ w.r.t. final CRT step, 7. does not apply). The authors conclude that $n=2048$, $p=560$ gives a good balance; from which it would follow that $k=3$ is fine, but $k=4$ is not. This is based on an analysis of ECM and GNFS (taking into account only 1. as far as I can tell) with reference to:

Paul Zimmermann, Bruce Dodson: 20 Years of ECM, In Proceedings of the 7th Algorithmic Number Theory Symposium, 2006 (alternate pay-walled link).
Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, Paul Zimmermann: Factorization of a 768-bit RSA modulus, in the proceedings of Crypto 2010.

A recent data point about ECM: in late 2013, Ryan Propper reported using GMP-ECM 6.4.3 + GMP 5.1.0 to find a 274-bit factor from the 787-bit composite $(7^{337}+1)/8/101020140256422276570987002251440602782290400709$ product of two unknown primes, on a commodity CPU using less than 6GB of RAM. He further reports that was a 10-day effort on Stanford's University cluster, and the factorization was found after 5000 curves. By extrapolating the log I get a runtime of 16 hours/curve and an expected $2^{21}$ curves (about $2^{12}$ core.years), and if that's any close to correct, an average of more than 300 cores have been used, and odds of finding that factorization so fast where 1/400; "this was quite the lucky find" is an understatement. The second largest of the ECM records is also quite a lucky one; which, if one considers 5. above, is to be expected!


How to calculate the number of Linearly active Sbox

I highly recommend reading Howard Heys's Tutorial on Linear and Differential Cryptanalysis available online (google is your friend) for a detailed explanation for the SPN case.

In brief, if a linear expression $a\cdot x+ b\cdot S(x)$ is used then all the output wires that correspond to 1 bit in the vector $b$ turn on the Sboxes they are connected to in the next round. It's best to start with one active Sbox in the initial round to turn on as few Sboxes as possible in the next round (by choosing $a$ and $b$ so that $b$ has a minimum Hamming weight but at he linear expression has a large bias).

See also the answers to this question and this one.

AES turns on the maximum number of Sboxes in a different way, since there are no bit permutations but a diffusion matrix. See a nice explanation in this answer.


What's happens if we use the weakest S-BOX for AES?

See: How can one construct the weakest S-box ever?
and How do I choose the best 3*3 s-boxes?

I believe that user Hend's question is not "how to design the worst possible S-box" but about "having generated an S-box randomly how do we know it is bad, how is that measured?".

A construction of S-boxes that was a trifle, insignificant, a minimis non curat would simply encode during half the rounds and decode during the other half, producing output equal to the input. If the number of rounds were odd the algorithm could leave the output in a state that was equivalent to a single round.

Obviously such poor design is trivial to discover. Where the problem lies is "when presented with an S-box construction that appears complex how do we disprove that". That is the question that I touch upon with this answer.

There are different cryptanalysis techniques and different ways to measure security. Some are published and some are secret. It's not particularly useful to measure an algorithm's security by a published method if a secret method exists for easily cracking the code.

For example: If it were though that there were only 10 ways to approach the cryptanalysis, the first 9 taking a little over a month each to execute but without any certainty of success and the 10th method providing absolute certainty of success but taking a year to produce the result, it makes sense to try the first 9 methods; you don't know which one will be successful but the worst case is it would take as long as simply applying only the 10th algorithm alone.

Similarly, if there were an 11th method, unknown to almost all cryptanalysists, one can not say that any S-box construction is opaque; that it does not reveal itself, and most importantly the original input. This answer can not speculate on what we don't know and will be limited to published measurements of complexity.

Some of the measurements are resistance to:

Algebraic attacks (RAA) (e.g., XL attack, XSL attack and Gröbner basis attack)

"Cryptanalysis of block ciphers with overdefined systems of equations" by Nicolas T. Courtois and Josef Pieprzyk.
Differential cryptanalysis
Linear cryptanalysis
Distance to the Strict Avalanche Criterion (DSAC)

In "An improved AES S-box and its performance analysis" by Jie Cui, Hong Zhong, Wei Yang they provide the formula for calculating the above metrics, and offer a list of papers they referenced; unfortunately the first four that I searched for are paywall only. The referenced papers are probably not necessary to understand their paper or this answer.

  "The cryptanalysis of the cryptographic strength of Rijndael has not stopped after the announcement and official publication of the AES $[11-16,19]$. Biryukov et al. $[10]$ proposed a distinguisher and related-key attack on the full AES-256. Wang $[5]$ noted that AES S-box affine transformation period is 4, and it does not achieve the most 16. Wang et al. $[6,17,18]$ studied AES S-box structure and pointed out that the iterative period of AES S-box has short-period phenomenon, and all the periods are less than 88. Murphy and Robshaw $[3]$ analyzed AES S-box algebraic expression and indicated that the algebraic expression of AES S-box is very simple and only 9 terms are involved. Much work has concentrated on AES S-box, such as the latest significant progress $[7]$ which illustrated the reason why AES S-box algebraic expression is so simple and proposed an improved S-box, and the algebraic expression of the S-box involves 255 terms, so the complexity of the S-box has been increased. However, the algebraic expression of the inverse S-box becomes very simple and only 9 terms are involved.

  In view of the shortcomings of AES S-box and the S-box $[7]$, in this paper, the cryptographic properties of AES S-box are analyzed, and an improved scheme to increase the complexity and security of AES S-box is proposed. Simulation results show that the improved AES S-box is better than AES S-box and S-box $[7]$ in cryptographic properties.

In their paper they offer this table on page 2301:

$[3]$ "Essential algebraic structure within the AES" by S. Murphy and M. J. B. Robshaw, Proc. of the 22nd Annual International Cryptology Conference on Advances in Cryptology, London, pp.1-16, 2002.

$[5]$ "Property of affine transformation in S-box of AES" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.4, no.2, pp.5-9, 2002.

$[6]$ "Analysis of structure of AES and its S-box" by Y. B. Wang, Journal of PLA University: Science and Technology, vol.3, no.3, pp.13-17, 2002.

$[7]$ "An AES S-box to increase complexity and cryptographic analysis" by J. M. Liu, B. D. Wei and X. M. Wang, Journal of Systems Engineering and Electronics, vol.18, no.2, pp.427-433, 2007

$[10]$ A. Biryukov, D. Khovratovich and I. Nikoli´c, "Distinguisher and related-key attack on the full AES-256", Fast Software Encryption, Advances in Cryptology – CRYPTO 2009, pp.231-249, 2009.

$[11]$ W. Phan, "Impossible differential cryptanalysis of 7-round advanced encryption standard (AES)", Information Processing Letters, vol.91, no.1, pp.33-38, 2004.

$[12]$ E. Biham, O. Dunkelman and N. Keller, "Related-key boomerang and rectangle attacks", EURO-CRYPT ’05, LNCS, vol.3494, pp.507-525, 2005.

$[13]$ J. Kim, S. Hong and B. Preneel, "Related-key rectangle attacks on reduced AES-192 and AES-256", FSE 2007, LNCS, vol.4593, pp.225-241, 2007.

$[14]$ W. Zhang, W. Wun, L. Zhang and D. Feng, "Improved related-key impossible differential attacks on reduced round AES-192", SAC 2006, LNCS, vol.4356, pp.15-27, 2007.

$[15]$ S. Galice and M. Minier, "Improving integral attacks against rijndael-256 up to 9 rounds", LNCS, vol.5023, no.3, pp.1-15, 2008.

$[16]$ C.-C. Chang, Y.-W. Lai and J.-H. Yang, "An efficient authenticated encryption scheme based on elliptic curve cryptosystem for broadcast environments", ICIC Express Letters, vol.4, no.1, pp.95-100, 2010.

$[17]$ J. Liu, B. Wei and X. Wang, "Affine transformation observation on rijndael S-box", Journal of Xidian University, vol.32, no.1, pp.94-97, 2005.

$[18]$ L.-G. Cui, "A new S-box structure named affine-power-affine", International Journal of Innovative Computing, Information and Control, vol.3, no.3, pp.751-759, 2007.

$[19]$ Y.-S. Yeh, C.-Y. Lee, T.-Y. Huang and C.-H. Lin, "A transpositional advanced encryption standard (AES) resists 3-round square attack", International Journal of Innovative Computing, Information and Control, vol.5, no.5, pp.1253-1264, 2009.

As you can see the weakest, even stronger S-boxes, are suspicious. Belief that no one anywhere has a means to break the algorithm is probably misplaced. Some S-boxes would be more susceptible to one kind of an attack over another, so there's not one particularly strong or weak one without improvements to the original algorithm. The authors offer an improved version and their analysis of that, in addition to the original.

In the thesis "The Design of S-boxes" (direct .PDF link) (2010), by Jennifer Miuling Cheung and the paper "The Structured Design of Cryptographically Good S-Boxes" (1990) by Carlisle M. Adams and Stafford E Tavares, J. Cryptology. 3. 27-41. 10.1007/BF00203967 and "Modification in Designing of Substitution Technique Using 4x32 S-Box in Data Encryption Standard" (direct .PDF link, or 2nd source), (2018), by Sumit Chaudhary, N. K. Joshi, and Foram Suthar - the general consensus has improved over the years but is currently:

Five design factors that must be meet for Boolean functions to construct a cryptographically good S-box:

  Bijection: If the S-box is of ‘n x n’ bit then from input vectors a one-to-one and onto mapping to output vectors will be there. This can be explained later that how we can achieve this criterion when the S-box will
  be n x m bits.
  Strict avalanche criteria: Here, there will be the change in output bit with the probability of one-half only if a strict avalanche criterion of one input bit has changed. In Strict avalanche criteria, output vector will
  be significantly changed with a small/slight amount of change in the input vector. So, a function is needed that has a 50% dependency on each of its n input bits inorder to achieve this effect.
  Bit independence criterion or correlation-immunity: Here, there is a requirement that output bits should have different statistical patterns or no statistical dependencies compare to the output vectors.
  Nonlinearity: The cryptosystem is susceptible to various attacks so nonlinearity requires S-box which should not be a linear mapping from input to output. If the nonlinearity gives a bad result by linear functions
  and makes a cryptosystem more complex to crack so S-box will be constructed by using maximally nonlinear Boolean functions.
  Balance: if each Boolean vector has the S-box with an equal number of 0’s and 1’s then it is known as balance. This should meet most of the standards set by the NIST. Sometimes, it can be impossible to achieve
  all criteria to their full potential. Sometimes criteria can be compromised due to their conflicting nature. For example, maximum nonlinearity also conflicts with balance as well as correlation immunity conflicts with
  high nonlinearity.

The newest criteria is balance, essentially a test of the output compared to a true random number.

Possibly of interest: "Small Scale Variants of the AES (SR) Polynomial System Generator".


Does brute force attack use the program that created the ciphertext?

Brute force attacks are usually implemented in custom hardware or software for maximum performance.

Obviously the method of encryption must be determined before the attack can be implemented. The encryption method can be determined in several ways:

It's publicly available e.g. open source code, or open specification
It's secret and gets leaked by someone with access to insider information
It's reverse-engineered e.g by diassembling the application


Counter mode with $\operatorname{AES}_k(m)$ vs $\operatorname{AES}_m(k)$

I understand that it would be quite inefficient as the key schedule would need to be re-calculated for every block, but would it make cryptanalysis easier?

It would make cryptanalysis trivial.

If the attacker knows that

$$P_i \oplus C_i = E_{n \mathbin\| i}(k)$$

and he knows $n, i, C_i$ and has a guess for $P_i$, he can recover $k$, and use that to decrypt everything else.

This works because, with AES, $E_k$ has an inverse $E^{-1}_k$ that's efficiently computable, assuming you know $k$.  There's no corresponding "inverse" corresponding to the message block, and so the "message block" and the "key" inputs to AES are not interchangable from a security standpoint.


Understanding Feldman's VSS with a simple example

It has to do with which modulus you use.  You did all your arithmetic modulo 11.  However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot).  In your example, you shouldn't do all arithmetic modulo 11.  Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ in this case).  If you do that, everything will work out.

In general, you need to pick primes $p,q$ such that $q | p-1$.  Then, some arithmetic is done modulo $p$, and some arithmetic is done modulo $q$.  In particular:

The polynomial $f(x)$ is treated modulo $q$, so when you compute the shares, you need do arithmetic modulo $q$.
The commitments and all computations with the commitments are treated modulo $p$, so when you verify that you got the correct share, you work modulo $p$.

The reason we do it this way is that when doing a computation like $3^{15}$ (modulo $11$), we can reduce the base modulo 11, but we have to reduce the exponent modulo 10.  Roughly speaking, commitments are in the base, whereas the value of the polynomial (the shares; the coefficient of the polynomial) are in the exponent -- so you gotta use different moduli for these two different kinds of values.

We can modify your example to take this into account. We could take $p=11$, $q=5$, and generator $g=3$ of the subgroup of order $q$ of $(\mathbb{Z}/p\mathbb{Z})^*$.  However, you can no longer have the polynomial $f(x)=5+3x+8x^2$: the polynomial is interpreted modulo $q$, so all coefficients have to be in the range $0..4$.  This means we'll need to change things a little bit.

So, here's a corrected example.  You could use the polynomial $f(x)=0+3x+3x^2$.  Since $f(1)=1$, you'll get the share $s_1=1$.  The commitments are $3^0=1$, $3^3=5$, and $3^3=5$.

For verification of the correctness of the share, we first compute $3^{s_1}=3^1=3$.  Next, we compute the check value $1 \times 5^1 \times 5^{1^2} = 3$.  You can see that $3^{s_1}$ is equal to the check value, so everything verifies, and the share is correct.


Security proof of schnorr identification scheme

I believe this is the 'Rewinding Lemma' part of Schoor identification security proof, and very well explained in the Boneh and Shoup book "A Graduate Course in Applied Cryptography", pgs 727-728.
An important aspect here is that we have to consider another adversary B, who emulates (grab a digital compiled version of A) and plays/interacts with A. (we can think of B as whoever wants to break the scheme, and presupposes the existence of A):

first, B plays the role of the verifier, and expect A (playing the prover role) send w;
B send r1, and wait for the A's answer;
B rewinds A, so that A’s internal state is exactly the same as it was at the end of step 1;
B sends a random and independent r2; waits for the A answer.

So B may be ignorant about how A works, but s/he is who sets A independent challenges/answers, and takes advantage of it.


Solve a problem, thought it was hash length extension, hours later, am I wrong?

Length extension attacks exploit the pattern that it's possible to use H(k || m1) to compute H(k || m1 || m2) without knowing the value of k, but it is restricted to messages m2 of a particular form.  Which is, they have to begin with the padding p that the hash algorithm applies to expand to a multiple of the block size.  This is critical, because it's what allows the attack to infer the internal state of the hash when it starts to process the non-padding part of m2.  Without the padding, the hash algorithm never gets to the state represented by the original output.

In your example, "IamSecret:YouKnowMe" and "IamSecret:YouKnowMe:1" don't follow that pattern - the second message does not have the padding before the new data.  Therefore you can't know the internal state when it starts consuming the nonce, and so you can't predict the output.

The authentication protocol in your application is not strong, you probably want to use HMAC or similar.  It's not clear to me if it's vulnerable to a length-extension attack; I don't quite understand which of the inputs are under control of the attacker (presumably known_value) and what the hash is used for.

See also Understanding the length extension attack for an accessible write-up.


Is there a specification for the "BEGIN RSA PRIVATE KEY" format?

I'm here, because, I'm asking myself the same question as the OP.

PKCS#1 (RFC 3447) defines the ASN.1 structure: RSAPrivateKey, permitting the
expression of an RSA private key only.

PKCS#8 (RFC 5208) defines the ASN.1 structure: PrivateKeyInfo, permitting the
expression of any private key. (For an RSA private key, PrivateKeyInfo is some
packaging information, and a reuse of RSAPrivateKey from PKCS#1).

PEM (Privacy Enhanced Mail), is a defunct method for secure email. But, its
container format was borrowed for packaging cryptographic items.

RFC 7468 (Introduction): "For reasons that basically boil down to non-coordination or inattention, many
PKIX, PKCS, and CMS libraries implement a textbased encoding that is similar to
-- but not identical with -- PEM encoding."

Which reads as: Um, folk have decided to use bits of PEM to package thier
crypto files. Here we have a jolly good effort to try and formalise that...

Alas, RFC 7468 clarifies the PKCS#8/PrivateKeyInfo packaging as "BEGIN PRIVATE
KEY". But not the packaging of PKCS#1/RSAPrivateKey as "BEGIN RSA
PRIVATE KEY".

The "BEGIN RSA PRIVATE KEY" packaging is sometimes called: "SSLeay format" or
"traditional format" for private key. Which, as least, gives us a name for this
format, but, like yourself, I cannot find, and would welcome, something that
approaches a formal description of this format. I suspect this does not exist.


Protocol for proof of knowledge of $l$-th root

The immediately obvious solution would be this simple cut-and-choose protocol:

Prover: selects a random value $v$ and sends the value $y = v^\ell$
Verifier: selects and sends a random bit $b$
Prover: if $b=0$, sends the value $t_0=v$.  If $b=1$, sends the value $t_1=vu$
Verifier: if $b=0$, then verify that $t_0^\ell = y$.  If $b=1$, then verify that $t_1^\ell = y w$

The standard zero knowledge logic works - if the prover knows a $y$ value for which he knows both correct responses $t_0$ and $t_1$, then (assuming that inverses are also easy to compute) he can recover the value $u$ (hence, if he succeeds with this protocol a number of times, then the probability of success without him knowing $u$ is minimal).  And, only one of the answers does not give any information to the verifier.


Finding Elliptical curve points and encoding text using them

What standard curves could I use? I know curves like p192 etc exists, am I allowed to use these?

Yes, of course you may use those, for more curves - including safer ones - check the safecurves website.

  How can I find valid points to use for messages and generator on these huge curves? So far I've done it using brute force on smaller curves with a small prime. I can't find any using my previous brute force approach since the numbers are too large.

This is part of key generation procedure. For Elliptic Curve the private key is a vector (usually of order N) and the public key is calculated for this particular vector. So this is basically asking how EC key generation takes place (for which there are tutorials available online, I won't completely explain it here).

  Whats a good way for encoding/decoding text using ECC? Should I simply map each valid character to a point on the curve and perform encryption/decryption once for each character and translate between the character and point using a lookup table?

No, you shouldn't directly encrypt anything with EC crypto, try and look up ECIES instead, it is basically ECDH key agreement coupled with symmetric cryptography on the derived key. Start with ECDH and then implement ECIES. Progress on with ECDSA if you want to have signatures.

EC is different than RSA in this regard, you cannot just alter the padding scheme (as there is no padding scheme).


Why does SHA-2 call for doing 10* padding in addition to appending the message length?

As rightly pointed in the question, 0*+length padding would work just as well as 10*+length padding, with the benefit of simplicity and requiring one less block in some cases, like SHA-256 for a message of 56 bytes.

I guess SHA-2 does this because SHA-1 did, and before that SHA, MD5, and Ronald Rivest's MD4 (1990), which is the earliest reference that I can point, and already had:

  Step 1. Append padding bits

     The message is "padded" (extended) so that its length (in bits)
     is congruent to 448, modulo 512.  That is, the message is
     extended so that it is just 64 bits shy of being a multiple of
     512 bits long.  Padding is always performed, even if the length
     of the message is already congruent to 448, modulo 512 (in
     which case 512 bits of padding are added).

     Padding is performed as follows: a single "1" bit is appended
     to the message, and then enough zero bits are appended so that
     the length in bits of the padded message becomes congruent to
     448, modulo 512.

  Step 2. Append length

     A 64-bit representation of b (the length of the message before
     the padding bits were added) is appended to the result of the
     previous step.  In the unlikely event that b is greater than
     2^64, then only the low-order 64 bits of b are used.  (These
     bits are appended as two 32-bit words and appended low-order
     word first in accordance with the previous conventions.)

Perhaps earlier block-cipher based MACs used 10* padding without length strengthening, where 10* prevents some trivial attacks 0* allows. In particular, 10* padding was used for variants of the so-called "CBC-MAC", which became ISO/IEC 9797-1 MAC Algorithm 1 padding method 2 (approved 1999). It would then be plausible that the 10* padding was kept, and length-strengthening as suggested by Merkle added, because 10* padding alone would not be as safe.

Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, in section 9, mentions both padding with 0* (algorithm 9.29) and 10* (algorithm 9.30) and note:

  The padding method of Algorithms 9.29 and 9.30 originated from ISO/IEC 10118-4 “Information technology – Security techniques – Hash-functions – Part 4: Hash-functions using modular arithmetic”, draft (CD), 1996.

but I doubt this is the true origin.


why $e(g,g)^N=1$ in bilinear pairings holds?

If $N$ is the order of the group $\mathbb{G}_T$, then for any element $x \in \mathbb{G}_T$ we have that $x^N = 1$. This follows from the Lagrange theorem. Since $e(g,g) \in \mathbb{G}_T$, the same applies to it.


Re-using information from the first factor for the second factor

As originally described, the system of having the two factors be [password, H(username || password)] is no more secure than the password alone.

The intent of Two-Factor Authentication is that you are improving security by requiring two independent factors for authentication. In the proposed model your second factor is fundamentally the same as the first. Assuming the hash function is publicly known as part of the protocol, then once your password is compromised then both factors are compromised.

Adding a key to the hash (i.e. a keyed hash) could potentially improve security depending on how that key was generated/shared. You would need to describe the whole system of course.

Nevertheless, There are a number of rigorously analyzed 2FA methods. Something like a TOTP token or U2F hardware key does add significant independent security to a password. You would be well served to investigate existing constructions and analysis.


Difference in one time key and one time pad and many time key

A one-time key is when the encryption scheme is set up such that only one message may be encrypted with a key. A many-time key is when multiple messages may be encrypted with a key. (A one-time-pad is a special case of a one-time key.)

The semantic security definitions for one-time and many-time keys for block ciphers may help. In both, an adversary $A$ submits two plaintext messages $m_1$ and $m_2$ to a black box that internally chooses one of $m_1$ and $m_2$ at random (namely, $m_i$ with $i \in \{0,1\}$ at random), encrypts $m_i$ with a randomly chosen key $k$, and outputs the ciphertext $C = E_k(m_i)$. Adversary $A$ wins if they can find a way of successfully guessing which of $m_1$ or $m_2$ were encrypted and output as $C$.

For the one-time key security model, the attacker gets to submit only one pair of messages. He must then launch his attack having only one input/output to observe. For the many-time key security model, the attacker gets to submit and observe a nearly unlimited number of message input/output pairs. (The choices of $i$ and $k$ remain fixed across each submission for the many-key model.)

To be secure in the many-time key model, the encryption scheme $E$ used above must be randomized. If it is not, then $A$ will break semantic security easily. $A$ will make three random messages and submit $m_1$ and $m_2$ in the first round and get back $c_1$, then $m_1$ and $m_3$ in the second round and get back $c_2$. If $c_1 = c_2$ then the ciphertexts are equal which means the encrypted plaintexts were equal, so the blackbox is encrypting the first message (which was the same in both submissions). If the ciphertexts are different, then the blackbox is encrypting the second message (which was different between the submissions). (Note that security for $E$ does not have to be randomized in the one-time key model.)

Example: CTR mode with a fixed IV is secure in the one-time key model, but insecure in the many-time key model. CTR with a nonce is secure in both models.


On what basis is padding chosen in OpenSSL?

Q: I am using CAPI Engine in OpenSSL and I did some test. When I use TLS 1.0 or 1.1, during handshake and RSA signing, PKCS padding is chosen. When I use TLS 1.2, RSA signing uses PSS padding.

Funny, a quick lookup of TLS 1.2 contains the following:

Note that there are certificates that use algorithms and/or algorithm
combinations that cannot be currently used with TLS.  For example, a
certificate with RSASSA-PSS signature key (id-RSASSA-PSS OID in
SubjectPublicKeyInfo) cannot be used because TLS defines no
corresponding signature algorithm.

As I didn't find any RFC's that counteract this, it seems impossible that TLS 1.2 uses PSS for authentication at all.
Now, on the other hand TLS 1.3 specifies that you should use PSS, which is not that surprising as TLS 1.3 very deliberately uses up to date cryptography at the cost of backwards compatibility. The TLS 1.3 specification does specify in section 4.2.3 that a 1.3-capable implementation negotiating 1.2 must support PSS signatures. If the peer supports 1.3, there should be no good reason not to negotiate 1.3 though, and if it only supports 1.2 it should not allow PSS, as there is no way to indicate that padding format1.
1 Choosing the padding algorithm can be performed by guessing the signature format, but PKCS#1 explicitly requires you to define the configuration beforehand, rather than looking into the signature format itself, as that may leave you prone to downgrading attacks on the signature algorithm itself.

For TLS 1.0 a very specific structure with both SHA-1 and MD5 is used. This standard predates SHA-2 and therefore it uses a more secure construct using two hashes that are separately pretty insecure. It also may use RSA encryption using PKCS#1 v1.5 padding as PKCS#1 v2.0 hadn't been introduced either. I don't see any changes for TLS 1.1 for RSA signing / encryption. Note that TLS 1.1 and 1.2 were mainly incremental updates of TLS 1.0 rather than the significant rewrite that TLS 1.3 is.
So basically, the use of RSA padding in TLS is directly tied to the standard itself. OpenSSL will try and follow that standard.

It might be that if you have a certificate that identifies the public key algorithm as PSS, see here. In that case an implementation may decide to go with that single choice, even though it is prohibited by the TLS 1.2 standard - I guess the correct response would be to throw an error unless the connection is downgraded from TLS 1.3.


For a hashing function like MD5, how similar can two plaintext strings be and still generate the same hash?

This answer is based on the work by AleksanderRas, although my conclusion is different.

First, to lay out a definition, a hash is a function that takes an arbitrary length input to a fixed length output. For example, MD5 takes any input and produces a 128 bit output.

A cryptographic hash is a hash function which has certain additional security properties.

Because a hash function takes an arbitrary length input and produces a fixed length output, it is guaranteed that there are some inputs which produce the same outputs. These are collisions.

Finally, the Hamming distance is the number of bits by which two inputs of the same length differ.

For any hash function, whether or not it is a cryptographic hash function, there are inputs with a Hamming distance of 2 which collide. This can also be shown by the pigeonhole principle:

Suppose that the hash function returns an n bit output.
There are 2n possible outputs.
Consider a string B which is 2n + 1 bits long.
Consider then the set of all strings which differ from B in exactly one bit. There are 2n + 1 such strings.
The Hamming distance between any two different strings in this set is 2: a 1 bit change to get back to B and a second 1 bit change to get to the other string in the set.
Because there are more strings in this set than there are possible output hashes, at least two strings must share a hash.
Therefore the hash function has a 2 bit difference collision.

It is possible to construct a hash function which does not have any collisions between strings with Hamming distance of 1. This can be shown as follows:

Consider a string B
Consider a string C which has Hamming distance of 1 from B.
The parity of B must be different from the parity of C. That is, if there are an odd number of bits set in B, there must be an even number in C and vice versa.
Therefore any hash function which directly encodes the parity of the input, such as regular MD5 with the parity bit appended, will have a minimum Hamming distance of 2.

There are less trivial hash functions than the parity one which have a minimum collision hamming distance of 2. For example, CBC-MAC is a family of algorithms which encrypts a bitstring with a fixed key under CBC mode, and returns the last block. This meets the definition of a hash function: it takes an arbitrary length input and returns an output fixed at the size of the block. Although (like all hash functions) CBC-MAC is vulnerable to collisions, it cannot have a collision if all changes occur within a single block. (This property comes from the fact that it is an encryption function and therefore a permutation, but further elaboration would be off topic) Since a hamming distance of 1 corresponds to a single bit change, and that single bit change is necessarily in just one block, it cannot cause a collision.

This should not be taken to mean that the smallest Hamming distance between collision inputs for every hash function is 2. There are functions with a minimum Hamming distance of 1: for example, the trivial hash function truncate. That is, given an n bit hash function which simply drops all but the first n bits, varying bit n+1 will (because it is ignored by the algorithm) give a collision.

So, when it comes to particular hash functions, the answer could be 1 or 2.

Others have argued that for MD5 and other standard cryptographic hash functions it will probably be 1. This is a purely probabilistic argument, but in the absence of evidence to the contrary it is a reasonable to use probability with hash functions which are designed to behave randomly.