Why isn't data encrypted with mutiple ciphers?

Why isn't data encrypted with multiple uncompromised (so far) ciphers?

Since about 1980, when modern widely deployed symmetric encryption actually fails on the field, that's not due to a theoretical break of the cipher, because the art/science of making ciphers has matured¹,². Successful attacks are on compromised or leaking implementations, key management/generation, short keys (perhaps deliberately³), operating mode, and human factors, which are issues that multiple ciphers do not solve. Hence multiple ciphers would only guard against a risk that now fails to materialize.
Before about 1990-2000, strong crypto was illegal for civilians or discouraged, including in many western countries. Thus multiple cascaded ciphers could not be widely⁴ used in commercial products when they where most useful: before the knowledge to make good crypto became commonplace.
Multiple ciphers add complication, and complex systems fail more.
Multiple ciphers increase the computational cost of encryption, and the cost of hardware when hardware is used (as is increasingly the case for AES, the de-facto standard for built-in-CPU cipher nowadays).
If multiple cascaded ciphers use the same key, the security can become that of the weakest cipher, especially against side-channel attacks, which are among the ones that do happen. Therefore we need multiple keys for multiple ciphers, which goes against usability, or/and introduces more complexity.

¹ The closest thing to an exception is RC4, but most actual attacks against systems using RC4 are due to poor key management/operating mode. Also, RC4 was initially used for applications with 40-bit security.

² Asymmetric encryption, signature, and hashes matured later, say 2000.

³ That's why DES has a 56-bit keys, see this. Another example is GSM's A5/1, which is breakable mostly because it uses a small state, presumably because authorities wanted to be able to break it (though I lack a clear reference proving that assertion).

⁴ There are a few examples of cascaded encryption used in disk encryption products where it is an option to damp paranoia / an accessory for security theater. It's an option in  TrueCrypt/VeraCrypt, and the successful attacks against this product work irrespective of use of this option.


For the LTV-FHE scheme, after how many additions should modulus switching be used?

First of all, I want to clarify that there is no relinearization involved in ciphertext multiplication.

Second, as discussed in the BGV paper, its not the ratio of noise to modulus size that matters but the absolute magnitude of noise is important and we should bring down the noise magnitude after each multiplication.

And finally comparing homomorphic addition to multiplication, the noise growth in multiplication is exponential whereas the noise growth in addition is atmost a single bit. Therefore we can perform multiple additions but not multiplications. Theoretically, you can compute a bound for maximum number of additions or multiplication before the noise wraps around the modulus, rendering the decryption unsuccessful.

I hope this helps you.


Impact of a non-uniform distribution in a secret sharing scheme

Just to add to the other answers, you may also want to take a look at leakage resistance secret sharing, for example this work.
The idea is to study the following question:

  What is leaked about the underlying secret when the adversary gets some leakage from the shares?

This turns out to be a very interesting question, and in some sense, changing the distribution can be seen as "leaking" information since some shares may become more likely than others.

Interestingly, in some cases, even a 1-bit leakage can completely break security.
For example, if you use Shamir's secret sharing over $GF(2^n)$, then leaking the first bit of a large enough amount of shares will leak the first bit of the secret! So if you have a distribution that generates shares for which it is more likely that the first bit is, say, $1$, then you will know something about the secret.


Understanding the impact of partitioning oracle attacks on stream ciphers

In short, we can call this a speed-up password search on non-committing AEAD schemes like  AES-GCM and ChaCha20-Poly1305 with low oracle calls. If your password has good strength then you are safe.

A committing encryption scheme is a scheme that computationally intractable to find a pair of keys and a ciphertext that decrypts under both keys.
The defined  targeted multi-key collision resistance
(TMKCR) security by the following game in which for a given target key set $\mathbb{K} \in \mathcal{K}$ for a randomized adversary $\mathcal{A}$ must produce a nonce $N^*$, associated data $AD^*$, and a ciphertext $C^*$ such that $\text{AuthDec}_K(N^*,AD^*,C^*) \neq \perp$ for all $K \in \mathcal{K}$. And the advantage is defined as
$$\textbf{Adv}_{\text{AEAD},\mathbb{K}}^{tmk-cr} = \Pr \left[ \textsf{TMKCR}_{\text{AEAD},\mathbb{K}}^\mathcal{A} \right] \implies \textsf{true}$$
As one can see, if the attacker somehow partitions the keyspace then they can reduce the oracle queries this means the attack has less online interaction to be detected.
For example, consider AES-GCM which is not committing, and select two keys and an arbitrary ciphertext then the adversary will look for creating a valid tag so that when during decryption the tag is valid [1]( note; AES-GCM doesn't require decryption to validate the authentication tag, however, separating decryption and tag validation requires to pass on the data, and usually this is not preferred for performance reasons)
The aim is the recovery of a password $pw$. Consider that you want to test the membership of two passwords $S_1^* = \{pw_1,pw_2\}$. Create two keys $K_1 = PBKDF(salt,pw_1)$ and $K_2 = PBKDF(salt,pw_2)$ (the salt can be found by sniffing!), now use Dodis et, al's approach  [1], construct a ciphertext $C'$ with a tag such that it decrypt correctly under the keys $K_1$ and $K_2$. Now send the splitting value $\hat{V}$ to the server. If the server indicates the decryption is successful then $pw \in S_1^*$. With iterating this procedure the attacker can find the password in $|\mathcal{D}|/2 +1$ queries while the default brute-force requires $|\mathcal{D}|$ queries. This attack has degree 2, if $k$ degree is possible then this will decrease the query amount substantially.
With SageMath code they were able to find $k=2^{16}$ colliding ciphertext very quickly. They simulate their adaptive partitioning oracle attack that constructs splitting ciphertexts of size $k$ iteratively for different sets of keys until the oracle returns valid. At this point, the adversary performs a binary search in $\log k$ queries to find the secret.

On the left, on the above picture, their success rate, and on the right is the time to generate the $k$-way collisions.
It turns out that multi-key collision attack on the Poly1305 is harder than GCM due to the appended 0x01. They are only able to generate at most 10, compare to GCM that reaches 18 degrees.  this still gives a factor-
of-ten speedup in partitioning oracle attacks
Misuse-resistant schemes like AES-GCM-SIV also applicable to this attack.
Attack on protocols

Shadowsocks
OPAQUE

Countermeasures

Limiting the length of the ciphertext
Entropy requirements on shared secrets
Use committing AEAD scheme, there is non in any standards, yet!.
Use single key Encrypt-then-HMAC ( long live HMAC ) or KMAC.

Questions

These multiple key things seem crazy, I always understood symmetric ciphers like ChaCha20-256 required searching a $2^{256}$ bit keyspace for a single correct key. I read that you can actually calculate using linear equations approx 200,000 valid keys for decryption. Is this really true, if so we shouldn't consider the bit-strength $2^{256}$ even for ECDH agreed on keys should we?

First, a small correction. If the keys are uniformly generated then on average it is not $2^{256}$, one bit less. let $k$ be the target key that the adversary search with a way to test the correctness of the key. Since each key has $\Pr[k_i = k] = 1/2^{256}$ to be correct then the expected number of guess is;
$$\sum_{i=1}^{2^{256}} i \cdot \Pr[k_i = k] = \sum_{i=1}^{2^{256}} i \cdot \frac{1}{2^{256}} = \frac{2^{256} (2^{256} - 1)/2}{2^{256}} = 2^{255} - {\textstyle\frac12}.$$
Of course, during the search, there will be many false positive keys to be eliminated, which doesn't add much to the search time.
As we talked about above, they search for a possible password space $\mathcal{D}$ where $|\mathcal{D}|= 800000$. The committedness of the scheme enables the attacker to reduce the oracle calls substantially.
If you are using a strong password or generating them with ECDHKE plus KDF call then you will be safe. The point is that humans tend to use bad passwords including cryptographers.

In an example local application where one uses say, libsodium's secret box (Xsalsa20+Poly1305) and Argon2 to derive a password and encrypt some file, if this file is stored on a system with no other API or info, is this vulnerable to this attack? (e.g. by calling libsodium and watching if the MAC primitive is successfully verified) or are "offline/stored" files like this safe? i.e. like a padding oracle attack, does this whole thing require that the server knows the correct key, and as such can give away information?

This attack requires an oracle that returns a value like the padding oracle attacks. If there is no return, then there is not a test even for a normal online password guessing attack $k=1$. They have looked at the libraries the use OPAQUE and AEAD schemes and saw that some of them are not applicable. See the emits error column. The attack on Shadowsocks was interesting since the attacker had a side channel to test.

Is this only an issue with password-based keys? Doesn't this attack also mean one can reduce the keyspace for ECDHE agreed keys to $2^{256}/200k$, when destined for use with ChaCha/Salsa?

If the keys are uniform randomly generated then the attack will not work. It is a password search.


Random permutation of bit strings of length $n$, where $n$ can be any positive integer?

Format Preserving Encryption is the name for a standard way of doing what you are asking.  It does a keyed mapping from a (potentially small) domain to itself.  It does more than you are asking (it tries to be secure; you specified that you didn't need that), however there should not be an issue with this.

You have already found it yourself, however if you were to ask me which FPE primitive to use, I would have suggested FF1.

(I'm putting this as an answer so you can accept it)


What is the "unknown attack" the reviewer is referring to?

The reviewer did not say "the unknown attack", but "in front of unknown attacks". That refers to no attack in particular. Much like a reviewer of a math paper could tell, without thinking of a particular $y$: "the argument that $p$ is prime is unconvincing, for it fails to show $\gcd(p,y)=1$ for hypothetical $y\in\left[2,\left\lfloor\sqrt n\right\rfloor\right]$ with $y\not\in\mathbb S$" (where $\mathbb S$ is a set defined in the paper).
I read the reviewer's argument as equivalent to: the existing analysis gives no proof that the claimed IND-CPA security follows from the difficulty of some assumed-hard problem.
That's what so-called security proofs are when it comes to encryption. Since about the last decade of the 20th century, such proof is considered necessary for proposing a new cryptosystem or protocol in a serious peer-reviewed crypto journal or conference, with few exceptions. These exceptions include block ciphers, hashes, or similar low-level primitives: for these, we still examine known attacks, and prove they do not apply, preferably with some quantitative assessment.
For all other cryptosystems, modern arguments against unknown attacks are on the tune of: Assume a PPT algorithm $\mathcal A$ that breaks IND-CPA security of the proposed system. (..) Hence PPT algorithm $\mathcal B$, using $\mathcal A$ as a subroutine, is able to solve the well-studied smurf problem with non-vanishing probability. Perhaps that smurf problem is: attack of AES with random key under IND-CPA.
If such security reduction is missing entirely from a paper, adding it will be a major rework; or sometime, impossible.
Up to the early 1990s, practice allowed to claim security without proof, or even without a clear definition. It was common the claim was disproved. For example, El Gmamal encryption in $\mathbb Z_p^*$ turned out to leak one bit about the plaintext. Countless attacks where found on RSA encryption and signature schemes. Crypto was then proverbial for it's break and fix cycles, much like bridge design used to be. Fortunately, these times are over when it come to crypto designs in IACR publications. That's still the norm for implementation, some standards, and less than recommendable publications.

My favorite example of why we should not trust security claims based on repelling existing attacks is the ISO/IEC 9796:1991 signature scheme, withdrawn 2000. It was AFAIK the first official standard for RSA signature, and carefully justified by Louis Claude Guillou, Jean-Jacques Quisquater¹, Mike Walker, Peter Landrock, Caroline Shaer Precautions taken against various potential attacks in ISO/IEC DIS 9796 “Digital signature scheme giving message recovery”, in proceedings of Eurocrypt 1990. And then, in 1999, that scheme was broken by Don Coppersmith, Shai Halevi, and Charanjit S. Jutla extending an almost working attack by Jean-Sébastien Coron, David Naccache, and Julien Stern; and independently by me using a technique a child could apply: all there is to do is find two different paths across this maze and collect the node values.

¹ I thank JJQ for having taught me multiprime RSA (then uncommon and perhaps unpublished) and using the Chineese Remainder Theorem for that.


No you can't prove that C sent something.
The only thing you can reliably prove to somebody is that somebody at some point had a HTTPS connection to C, by presenting the key exchange.

You can't prove that C send something because the record layer is symmetrical, meaning everything C sent, could be forged by B as he has to have the neccessary keys.

To understand, let's quickly recap how TLS (the security layer behind HTTPS) works:
The server and the client negotiate a shared secret using the key-exchange which also proves to the client that he is communicating with the correct server. Both parties derive four keys (2x authentication and 2x encryption). The data you consider is symmetrically encrypted and then symmetrically authenticated meaning the receiving party can as well construct this exact message using the symmetric methods (by encrypting and authenticating the message with the appropriate keys). If the user presents you with a full transcript of his side of the key-exchange and communication you can't be sure if he forged the claimed message or if the server sent it legitimately as he must have the keys for that or he couldn't have received the message in the first place.


Construct Schnorr Protocol can only verify by designated verifier

I try to add a trap door commitment to a non-interactive schnoor protocol. Trap door protocol provide a back door for selected verifier by public key.

Cryptography setup

$y=g^x$ where $r$ is the secret to prove
$y'=g^{x'}$ where $y$ is the public key of the verifier and $x'$ is the private key of the verifier

Construct the proof

Pick $w$, $r$, $d$ randomly in $Z_q$
$c=g^wy'^r$
$t=g^d$
$h=hash_q(c, t)$
$s=d + (h + w)x$
$(w, r, t, s)$ is the proof and send to verifier

Verification

$c=g^w y'^r$
$h = hash_q(c, t)$
verify $g^s = ty^{h+w}$

Simulating Transcript

Pick $\alpha$, $\beta$ randomly in $Z_q$
$c=g^\alpha$
$t=g^sy^{-\beta}$
$h=hash_q(c ,t)$
$r = (\alpha - w)(-x')$
$w = \beta - h$
$(w, r, t, s)$ is the transcript

Because of the trap door commitment, designated verifier ($y'$) can create a valid proof.
But only the designated verifier know the proof is come from himself or prover. For others, they can't tell the proof is come from designated verifier or prover. Only designated verifier or prover know the proof is created by who. So only designated verifier can be convinced in this protocol.

So this protocol, can convince designated verifier knowledge of r in Schnorr Protocol. The verifier can't transfer the proof to others and he is the only one can be convinced.


How hard is it to generate a simultaneous MD5 and SHA1 collision?

Surprisingly enough, it would appear that generating a simultaneous collision wouldn't be that much more expensive than generating a single collision for SHA-1.

The basic idea is to form a $2^{64}$ wide multicollision on SHA-1; that is, $2^{64}$ distinct messages that all SHA-1 hash to the same value.  We can do this by using Joux's idea of forming finding 64 different colliding blocks $B_{i, 0}, B_{i, i}$ such that all sequences $B_{0, a}, B_{1, b}, B_{2, c}, ..., B_{63, z}$ all share the same SHA-1 hash; this can be done by finding 64 successive SHA-1 collisions.  The best estimate on finding a single SHA-1 collision is $2^{61}$ SHA-1 compression function calls (Stevens); hence the effort to find 64 such collisions is $2^{67}$ compression function calls.

Once we have such a $2^{64}$ wide multicollision, we just do an MD5 hash of each, and look for an MD5 collision; this takes $2^{65}$ MD5 compression function calls, and yields a collision with good probability.

This yields a simultaneous SHA-1 and MD5 collision with an expected $2^{67}$ computational effort.


Why does a perfect secrecy can be achieved when decryption correctness is not totally required?

I'll further explain the comment of @CodesInChaos and then give a simple example:

Explanation

When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the message that effectively is encrypted is not $m$ but rather just part of it of length $|\ell|<|m|$ and thus the key doesn't have to be of length at least $|m|$ but rather be of length at least $|\ell|$.

Example

The most basic example is an encryption using the One-Time-Pad Scheme, in a model where the correctness requirement from the scheme is weakened to: $Pr[Dec_k(Enc_k(m))=m]=\frac{1}{2}$. Take a message $m$ of length $|m|$ and a random key $k\in\{0,1\}^{|m|-1}$; the encryption method take the first $|m|-1$ bits of $m$, call it $m'$ and output the cipher $c=m'\oplus k$. Then, given $c$ and $k$, we can decipher (or decrypt) the cipher correctly with probability of exactly $\frac{1}{2}$ by computing $m'=c\oplus k$ and then randomly guessing the $|m|^{th}$ bit of $m$; since we get the correct bit with probability $\frac{1}{2}$ we satisfy the correctness requirement.

About the bound

We can say the when the correctness requirement is $Pr[Dec_k(Enc_k(m))=m]\geq\frac{1}{2^t}$ the key space must be of length no less then $|m|-t$. If the key in the example above is of length $|m|-t$ then the decryption algorithm can guess the omitted $t$ bits of the message with probability $\frac{1}{2^t}$ as required.


Is it safe to use a secret salted hash of a public id for client to prove ownership of id to a server that knows salt but does not store ids?

You could do something fairly simple, such as

$UserSecret = Random()$
$UserID = HMAC(ServerSecret, UserSecret)$

Send the user the two values.  When he reconnects, he sends the two values back.  If re-calculating $UserID$ with the user's $UserSecret$ gives the same $UserID$ then that proves (to a high degree of certainty) that it's the same person that was given that ID before (assuming the $ServerSecret$ is still secret and the same value as it was originally).

The size of the ID value will need to be sufficiently large that the same ID is unlikely to be handed out to more than one person, since you're not keeping track of which ones have been used previously.

Using HMAC-SHA256 would give large enough values.  See the wikipedia entry for HMAC for an explanation of how it works.

You could also use an SRP-style verifier, which could then be used to do an authenticated key exchange as well.

User generates a random value $x$, and sends the server

$Verifier = g^x mod N$

(see SRP for more details on $g$ and $N$)

Establish a secure session using SRP with $x$ and $Verifier$ to generate a key. The server then calculates $UserID = HMAC(ServerSecret, Verifier)$ and sends that to the user.  The user saves the $UserID$ and $x$.

Later connections, do the same thing using the saved $x$, but server sends a hash (e.g. SHA256) of $UserID$ to the user.  The user verifies that the hash is correct (which authenticates the server), then sends $UserID$ (that it originally got) back to the server to prove it also knows it.


Interesting implementation practices in popular crypto library

This appears to be a simple case of Loop Unrolling, which is a generic software optimization. Implementations of crypto algorithms are often times "unrolled", which means taking the statements that normally go in a loop and hardcoding them in the order they would have happened. This is a performance optimization: The loop counter requires cycles to increment and compare, as well as register space to do either (which may imply additional MOV instructions as well).

So the answer is speed, not security — optimizations such as loop unrolling do not change the output of the algorithm, they are an implementation choice.

Chances are, if you describe an algorithm to 10 different people and ask them to implement it, you will receive 10 different variations of the same program - that all still produce the same output, albeit at varying speeds and implementation complexities. Especially at the C level, performance often times comes at the cost of code clarity.

Theoretically speaking, which means disregarding side channel attacks, the implementation should influence only the performance of the algorithm, not the security. In practice however, due to the potential for side channels, the implementation may influence security, though loop unrolling will most likely not be the culprit. If this was the case, the lack of security would not be visible in the output of the algorithm - side channels exploit information that is only present when the actual algorithm is physically implemented in practice, and the information is extracted via other means.

  Why is this not left to compiler optimizations

We do not necessarily like to let the compiler aggressively optimize our crypto code. - it can do things that are less than desirable. Cipher algorithms are usually relatively small and very simple in their implementation (if not conceptually so), and sometimes are implemented directly in Assembly to maximize performance or minimize code size.

Loop unrolling is used in hardware implementations as well.

  Why is this done in the official implementations

The official implementations are the ones actually being used by the largest numbers of people, and so obviously should be the most efficient ones available. This is just a common courtesy really, as CPU cycles cost dollars as well as time. This is not particular to cryptography, but is most likely true of software in general.

The "unofficial" implementations you have seen were probably written by somewhere learning the algorithm, for which clarity is a priority, rather then efficiency.


I do not know if the result is true, since I did not check it, but note that this algorithm is not in the standard model of quantum computation. As the author himself put it:

  The Deutsch model of quantum computation is extended to allow for thermodynamically irreversible operations by allowing the system of interest to interact with an outside reservoir. A set of irreversible logical error correction superoperators are constructed which allow the rapid concentration of probability from an exponentially large search space into a small number of logically defined states. These capabilities are used to construct a linear time solution algorithm for the NP complete problem 3SAT.

Therefore, this result, if true, simply says that in an appropriate extended model of quantum computation, there exists an algorithm that solves 3SAT in linear time. This does not prove BQP = NP (which would be a major breakthrough), nor is it clear whether this model has any concrete value - put otherwise, it is not an algorithm that a quantum computer, if it is ever build and runs as quantum computation experts expect it should run, could ever run.

A few additional notes: algorithms that solve NP-complete problems in extended models of computation are well-known, people have long investigated closed timelike curves, post-selection in quantum computation, and other appropriate modifications of the standard model of quantum computation. More often than not, these modifications make the model much more powerful, able to evaluate much more complex functions (indeed, studying how specific variations of the model deeply change its computational power is one of the ways some researchers use, e.g. Scott Aaronson to name only one, to understand the exact boundaries of BQP). Note also that the paper you link was added to ArXiv in 2015 and, as far as I can see, was never published anywhere - so it does not seem unlikely that it either contains a mistake, or the alternative model investigated there was not judged realistic, useful or interesting by the reviewers.


Disjunction of several instances of sigma protocol

There is a truly elegant solution to this problem by Cramer, Damgard and Schoenmakers from CRYPTO'94. You can also read about it in Section 4 of the survey on $\Sigma$ protocols by Damgard.


Non-iterative cryptographic hash functions

Per my comment, I'd like to suggest a definition for "non-iterative hash function", and propose some constructions that fit the definition. I will also suggest an alternate name (though it may not help much with searching for papers on the topic).

Let $\mathcal{M}$ be the message space of a hash function, e.g. $\mathcal{M}=\{0,1\}^{*<\ell}$, the set of all binary strings of length less than $\ell$ for some $\ell \in \mathbb{N}$.  Let $\mathcal{D}$ be the 'digest space' (codomain) of a hash function, e.g. $\{0,1\}^b$ for some constant $b$.  I will use subscripts to denote which hash function is associated with a given message space or digest space.  Also, let $subseq_y(x)$ be a function that takes binary strings of arbitrary length and outputs a fixed subsequence of the string of length $y$ (e.g. truncation of the string to its first $y$ bits, or outputting only every third bit up to bit $3y$, etc).

A hash function $H(x)$ with digests of length $b$ is "non-iterative" or "uncompressible" if and only if there exists another function $G(x)$ such that:

$\mathcal{M}_{H(x)}\subseteq\mathcal{M}_{G(x)}$,
$|\mathcal{M}_{G(x)}| \le |\mathcal{D}_{G(x)}|$,
$G(x)$ is injective - no two distinct messages in $\mathcal{M}_{G(x)}$ map to the same digest in $\mathcal{D}_{G(x)}$, and
For any message $m \in \mathcal{M}_{H(x)}$, $H(m) = subseq_b(G(m))$.

Note that a hash function need not be cryptographically secure to be non-iterative by this definition.

The construction in the question meets this definition:  In that case, the function $G(x)$ is simply $SPRP(IV||m||padding)$, without truncation.

As described in my comment, another construction is to truncate an injective Random Oracle.  Unlike the permutation-based construction, this doesn't have a fixed limit on the message space size (or digest size) defined by the blocklength of the underlying $SPRP$, and yet is just as "non-iterative" or "uncompressible".

As a concrete instantiation of a "non-iterative" or "uncompressible" hash function with no limit on the message or digest lengths, I propose an 'expanding sponge' function.  This is just like an ordinary sponge function, but with two differences: 1) instead of using a fixed size permutation it uses a (keyless or fixed key) variable-length blockcipher (like the BEAR blockcipher), and 2) at each step during the absorption phase, instead of xoring the message blocks into the state, it concatenates the next message block with the state; i.e. $S_n$, the state at step $n$ is equal to $\mathcal{E}(S_{n-1}||m_n)$, where $\mathcal{E}(x)$ is encryption with the variable-length blockcipher.

Edit to clarify: For this expanding sponge function, the injective function $G(x)$ that makes this construction "uncompressible" has the same absorbing stage as $H(x)$, but during the squeezing stage $G(x)$ outputs the entire state at each step instead of only part of the state.  The output digest of $H(x)$ is thus a subsequence of the output digest of $G(x)$.  $G(x)$ is of course trivially insecure, in the sense that one can easily invert the function to find the preimage of any digest.

Note that this construction is in a sense 'iterative', in that it breaks messages up into blocks (with padding at the end if necessary) and absorbs each message block in turn one at a time using repeated iterations of the same variable-length blockcipher.  But, there is no possibility of collisions in the internal state (any two distinct messages will generate distinct internal states).  Of course, the internal state will balloon to the size of the message once it is done absorbing.  But that is the price of collisionless internal states.  For this reason, I propose "uncompressible" rather than "non-iterative".


Do per connection random keys solve the stream cipher key repetition issue?

I'll answer per related question:

It seems like you are trying to describe a scheme that relies on a One Time Pad (OTP). To use an OTP it is required that your scheme complies to the security requirements of a one time pad. If it does, it will be provably secure (except for the leaking of time and length related data).
Now you are trying to create a slow, untested stream cipher out of your OTP scheme, because you do not comply to the OTP requirements. You are better off choosing a well known, fast stream cipher instead.

So choose a fast stream cipher and try and create a good key management scheme around it; you haven't described how you distribute your session keys.


Research for video game: Novice cryptography concepts

Depending on your video game design you maybe can utilise a many-time pad. Many-time pad is many plaintexts encrypted by XORing them with a common string.

One-time pad cannot be broken but many-time pad can, especially if the players can make an educated guess about what the plaintext message might contain.

You can also try encrypting numbers with RSA but with small modulo n so that players can easily factor it.


Why isn't CTR mode (counter mode) used more often?

There are probably quite a few good reasons for this, although I don't expect that a scientific answer can be composed (as you would need to use a survey, and I've never heard of such a thing for modes of operation).

Let me list a few possible reasons:

Developers don't know about CTR mode of operation; most questions on StackOverflow are about ECB and CBC (I really hope that SO doesn't reflect corporate practices everywhere);
Even today it is possible that CTR mode is not available for some runtimes (only ECB and CBC mode are practically guaranteed on most lower level libraries);
(Older) protocols may simply specify other modes of operation.

With regards to the parallelism provided:

AES is already pretty fast, doubly so if AES instructions are present within the chip - for instance AES-NI within Intel/AMD CPU's - so the parallelism provided by CTR mode are not often required;
Many problems that require fast crypto are embarrassingly parallelizable by themselves (e.g. multiple file encryption and TLS sessions to a server);
Multi-threading is hard to get right, and may be hard to use (for instance, you may not want all your cores to be just encrypting data);

You think in CPU terms. Loads of people however don't use C/C++ but use higher level languages. These may have a totally different level of operation and may not have good support for modes of operation, let alone multi-threading support for these modes of operation.

If you want to create a protocol that is supported on lots of devices you may need to standardize on CBC as highest common denominator. C/C++ may be fast, but software created in those languages is also notoriously hard to secure, leaving you exposed to all kinds of attack. Speed is nice, but it is useless if you lose your data because of a buffer overflow.

In the cryptographic community CTR is probably the hottest mode in town. It is for instance used in GCM, CCM and EAX (authenticated modes of operation) as underlying mode to provide confidentiality. It has one particular cryptographic property that is not nice: nonce (IV) reuse is catastrophic to the confidentiality of messages send with CTR. The IV in CBC mode is harder to get right, but it doesn't fail as badly if you don't.

In the end, CTR mode is often simply not required. But with the advance of AEAD modes that use it for encryption / message confidentiality, it may be that it makes a stealthy comeback; many developers will be using it without even knowing that it is there.


How to decrypt RSA if ciphertext is less than the modulus and e=3?

"How can I decrypt RSA provided I only have public key and ciphertext?"

You break e=3 RSA.  (See pages 393 to 396.)


AES-128 uses the full set $\{0, 1\}^{128}$ as keyspace, and for each key the blockcipher is defined for each input block in $\{0, 1\}^{128}$. The same goes for AES-256, but it uses a 256-bit keyspace (but still a 128-bit block).

So the answer to 1 is yes.

For 2, we have this equation:

$$AES_K(AES_K^{-1}(x)) = x$$

We can decrypt both sides:

$$AES_K^{-1}(AES_K(AES_K^{-1}(x))) = AES_K^{-1}(x)$$

Because we know that $AES_K^{-1}(AES_K(a)) = a\:$ by the definition of the inverse we can cancel out an encryption/decryption cycle on the left hand side:

$$AES_K^{-1}(x) = AES_K^{-1}(x)$$

So it's true.


What is the discrete logarithm assumption and why it is not easy with Shank's baby-step/giant-step

When I read about the DLP, it seems that the assumption is that it is not generally possible to solve it in polynomial time.

Actually, whether or not we assume that it is hard depends on the group; there are certainly groups where it is quite easy (for example, in $\mathbb{Z}_q^*$ where $q-1$ is smooth).

  But I also read that there are several algorithms in O(sqrt(n)) for instance the big-step/baby-step so there must be some misunderstanding by me.

That is what you are misunderstanding; when we say "polynomial time", we mean "polynomial in $\log(n)$"; $\sqrt{n}$ is not polynomial in $\log(n)$ (actually, it is exponential), and so that is not a contradiction.

  The problem is: Given an element $x$ of the group, find the number $a$ so that the generator $g$ will generate $x$ by $x = g^a \bmod q$.

Actually, there are a number of generalizations, and they're all sometimes called DLP:

Perhaps we don't require $g$ to be the generator of the entire group; we still insist that $x$ be a member of the subgroup that $g$ generates (there won't be an $a$ otherwise).  This is actually more common than your meaning; where $g$ might generate a prime-sized subgroup.
Perhaps we don't restrict ourselves to groups of the form $\mathbb{Z}_q^*$, but instead have $g$ and $x$ be members of a different group (for example, an elliptic curve group).  Sometimes this is called the ECDLog problem; sometimes, we aren't as specific.

  I read about deterministic algorithms such as Shank's which solve the problem in O(sqrt(|G|) which is quite fast isn't it?

Not if $|G| > 2^{256}$, it's not (and yes, that's the size of the groups we use in practice)


I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or you may be able to reuse a lot of the intermediate claims of the proof of the original scheme. However, you must prove!


Cryptographic Systems Involving Modular Exponentiation

Can someone please clarify the last line for me (in italics)?

Ok, here is a very simple example of what can go wrong.
For a very simple example, let us consider $p=11$ (smaller than what they specify, however it'll act the same, and it'll keep the computations simpler), and $k=3$.
Suppose we want to encrypt the message $m=2$; what we'll do to encrypt is compute $m^k \bmod p$, in this case, $2^3 \bmod 11 = 8 \bmod 11 = 8$.  And, later on in the text, they'll explain how to decrypt.
However, to answer your question, suppose we were to try to encrypt the message $m=13$.  In this case, we'd compute $13^3 \bmod 11 = 2197 \bmod 11 = 8$.  That is, we got the exact same ciphertext that we did for $m=2$; that means that if we get the ciphertext $8$, we wouldn't be able to tell whether the original $m$ was $2$ or $13$ (and by default, we assume that it is less than $p$, namely, $m=2$).
It turns out that this encryption method always handles any $m$ the exact same way as $m+p$; hence if we get a message larger than $p$, there will always be a smaller message that encrypts the same way.
As a side note, when I computed $m^k \bmod p$, I wrote it out as $m^k$ and then applied the $\bmod p$ operation.  This works on these small toy examples, but on realistic cases, we convert the $m^k$ into a series of modular multiplications and squarings, and apply the modulo operation after each multiplication/squaring.  This is not related to your question - I'm just trying to anticipate a possible future source of confusion.


Brute-force attack given small search-space and hash prefix

If you have an $m-$bit output decent hash function (such as SHA1) and you're hashing $k-$bit values, and your list $L$ of candidates is not tiny ($2^{56}$ which is the size of possible candidates, isn't) the function will behave like a random mapping on any substring of its' output.

If your prefix consists of 8 4-bit characters, then you'll
be filtering roughly one out of every $2^{32}$ candidates during precomputation.

Thus, at the end of precomputation, you'll have $2^{24}$ candidates left.

In a large enough list is expected that whatever the correct input is, it has shown up as part of an unknown subset of roughly $2^{32}$ inputs in your filtered candidate list. Since you only have $2^{24}$ candidates left, it's likely that most of them are actually the unique candidate.


Elliptic Curve Integrated Encryption Scheme (ECIES) is a type of Integrated Encryption Scheme (IES) that uses Elliptic-Curve Diffie-Hellman (ECDH) key agreement to establish an ephemeral data key (rather than a session key) which is then used to encrypt data using a symmetric scheme. It uses an ephemeral key during the creation of the ciphertext, for which the public key is stored with the ciphertext. Usually, the receiver / decrypting entity has got a static key pair for which the public key needs to be trusted by the sender / encrypting entity.
ECIES can of course be used for authentication of the receiver: you could encrypt an ephemeral key using the data key, send it over, and if the other party is able to decrypt then you have authenticated the receiver. Of course, the receiver must still show that it now has the authentication key to e.g. create a MAC over a message known by both parties. In the case of TLS you would basically be replacing RSA_ ciphersuites that perform RSA encryption with ECIES_ ciphersuites that perform Elliptic Curve encryption.
That sounds great, but hold on: both parties now first have to establish an ephemeral data key, to encrypt an ephemeral authentication key. It would be much easier to simply use the data key for authentication. If you'd do that then you're back to Diffie-Hellman key agreement. So basically it would only be useful if normal DH key agreement can - for some reason or other - not be directly integrated in the protocol.
This is an explanation by example that differs from an earlier, more concise one given here. That one focuses on the session key derivation, this one is more about the possible entity authentication.

There are several versions of the DH key agreement that allow authentication. Most possible schemes are documented in NIST SP 800-56A Revision 3: "Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography", chapter 6.
Basically you need a static DH key to perform authentication which then can be performed by validating a MAC created using the derived key. So the "1S" scheme (S for Static) is able to authenticate one entity, and 2S schemes are able to authenticate both entities (I'll skip over multi-entity key agreement, for now, keeping it at a single pair).


Sigma protocol ZK-proof of a pair of pedersen commitments

The important thing to understand is that if the prover knows such a $z$, then the commitment is not binding. In particular, for any $Y$ and any $x_1'$ it can find $x_2'$ such that $Y=g_1^{x_1'}\cdot g_2^{x_2'}$. Thus, it can open the commitment to any $x_1'$ it likes. As such, it can also prove knowledge of any $x'_1,x'_2$ it wishes. This does not break soundness, since it indeed knows such an $x'_1,x'_2$ and so everything is true.

If $z$ is known to the verifier, then this actually makes no difference, because Pedersen is a perfectly hiding commitment.

In general, you should study more about Pedersen commitments, and then understand the $\Sigma$ protocol issue.


Combining secure hashes with insecure hashes?

I can tell that using new hash function is a bad idea since no one has
  yet to research and attack it, aside from the fact that more bits is
  less efficient. Apart from this explanation, I don't see other reason
  to disqualify this answer.

That one is largely correct, although more bits doesn't have to mean "less-efficient" as for example Skein-512 turned out to be faster than Skein-256 during the designer's tests.

  MD5 is broken and collisions can be made quite easy, so two different
  inputs to this function can collide and have the same input to the
  SHA-1 function, which will result in collision between the final
  outputs.

This one sounds good.

  I have no clue how to disqualify this one. The intuition says 'xoring
  with bad hash functions is not a good idea', but I can't really
  justify my answer. I also think the padding doesn't actually affect
  anything, becuase if SHA-1 result is secure then padding 0s to it
  won't make it collide with other inputs suddenly.

This one is actually quite interesting. The property in question here is pseudorandomness of the output. If you zero-pad, the shorter hash functions don't have an effect on the higher bits, so MD5 will only enhance the first 128-bit, SHA-1 and $h_{ib}$ will only enhance the first 160 bits and the remaining 506 bits are up to $h_{666}$. Now if $h_{666}$ isn't pseudo-random, neither will this construction (likely) be, because you can distinguish the output from a random value using only the 500 high bits, which is obviously bad, as we already established that $h_{666}$ isn't exactly trust-worthy.


What is the purpose of four different secrets shared by client and server in SSL/TLS?

In TLS (that's the standard name for SSL; TLS 1.2 is like "SSL version 3.3"), client and server ends up with a shared secret (the "master secret", a 48-byte sequence; when using RSA key exchange, the master secret is derived from the "premaster secret" which is the 48-byte string that the client encrypts with the server public key). That shared secret is then "extended" into six values:

the "client write key";
the "client write IV";
the "client write MAC key";
three similar values for the server.

The "extension" uses the PRF described in section 5; it can be thought of as a hash function with a flexible output length.

TLS main purpose is to keep data confidential; however, it also aims at maintaining data integrity: if someone or something, willingly or not, alters data in transit, then the receiver must be able to reliably detect it. Detecting alterations is important in many protocols; moreover, if an attacker can modify data, he can often handcraft precise alteration which, when sent to the peer in lieu of the correct data, may result in reactions which leak information about the encrypted data. Therefore, we not only want to detect alterations for the own sake of integrity, but also because unconstrained alteration may result in a confidentiality breach.

So we need encryption (for confidentiality) and integrity control (to support confidentiality, and because integrity is also needed by itself). This calls for several algorithms, typically AES for the symmetric encryption part, and HMAC for the integrity control. HMAC is a Message Authentication Code algorithm, which is a kind of "hash function with a key" (HMAC is built over a true hash function, like SHA-256, with a key inserted "the right way"). The HMAC value is computed by the client with its "client write MAC key" and appended to the record data; the server will recompute the HMAC value and see if it matches the one which was sent.

The encryption part requires a key (and an IV for symmetric encryption algorithms which use CBC mode, and this is subject to a few subtleties which depend on the SSL protocol version, so I will not detail these here). The MAC also needs a key. Using the same key for two distinct algorithms is, as a general rule, not recommended at all: there may be unwanted interactions between the two algorithms, an improbable but not impossible event which has not been thoroughly studied. So, to be on the safe side, we generated two keys, one for encryption and one for the MAC. The two keys come from the master secret, but the derivation mechanism is like a hash function, so it supposedly makes it impossible to guess the MAC key even if you know the encryption key, and vice versa.

Since TLS has a key derivation function (the "PRF") which can produce outputs of arbitrary length, it was easy to mandate production of encryption and MAC keys distinct for both directions (the key used by the client to encrypt data -- and that the server uses to decrypt received data -- is distinct from the key used by the server to encrypt data it sends to the client). Using distinct keys avoids problems with attackers who could otherwise get a copy of an encrypted record sent by the client, and feed it back to the client as if it was sent from the server. With distinct keys, the client will reject the attempt, because the HMAC value will not match what the client expects (it will be a HMAC computed with the client write MAC key, not with the server write MAC key).

There are newer symmetric encryption modes which do the encryption and the MAC with the same key in a controlled way, e.g. GCM -- and AES-with-GCM can be used with TLS although you may have a hard time finding compatible implementations (this is rather new).


How does the user get the private/public key with HMAC based request signing?

Each site, users and the server, generate their public and private keys and announce them, by sending the public keys. This can be executed during the registration process. The server should not generate the keys for the users, otherwise, the servers must be totally trusted and you have to securely send the private key, somehow.

You can use the  Diffie-Hellman Key exchange protocol or the Elliptic-curve Diffie–Hellman to generate the keys to use in HMAC or any other process.

Due to the man in the middle attack, you may need  to apply the improved version; Station-to-Station protocol


How to show that a one-way function proves that P ≠ NP?

It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:

Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness  (up to minor formal details; see this question too) we can use to verify the pair in only polynomial time—recall that a one-way function can be computed in poly-time.

But we have $P = \mathit{NP}$, and we can use a decider $D$ for $L$ to "invert" $y$. Receiving the input $(y, 1^n)$ ($n$ being the safety parameter), start with the pair $(\varepsilon, y)$, i.e. with the empty word as a prefix, and use $D$ to incrementally add bits to the prefix part until you obtain $(x,y)$ with $f(x) = y$. Such an algorithm runs in poly time because it is guaranteed there exists an inverse image to $y$ of length at most $n$. It follows that $f$ is not one-way, and we have a contradiction.

Regarding your question about the relation between decision problems and computational ones: the whole point of the $P = \mathit{NP}$ dilemma is answering whether computing a solution is as hard as simply verifying it or not. This is because non-determinism virtually allows us to "cheat" and circumvent wasting any time in computing the answer; we only need to guess it and check whether our guess was correct or not.

An interesting consequence of the statement above is that the assumption of one-way functions is actually stronger than $P \neq \mathit{NP}$. This is in line with the famous hierarchy of cryptographical assumptions known as Impagliazzo's five worlds.


Can ECB be turned into a secure algorithm by adding obfuscation of the plaintext patterns?

Let's say for instance

  each block of plaintext is XOR'd with

  a randomly generated key
  that is stored with the block

  and then encrypted along with it, effectively hiding any observable pattern.

For 1. you need as much entropy as the amount of information in the message.

For 2. you need double the storage for ciphertext.

The clever audience may have observed by this point, that it's just a convoluted way to make one-time-pad insecure against unbounded adversary.


DES Bruteforce attack and false positive keys

My question is, how can DES exhibit such behaviour if the key space is about $2^{56}$ and block space is $2^{64}$

Let us assume that the attacker has a single plaintext/ciphertext pair, that is, two eight byte values $P, C$ with $C = \text{DES}_k(P)$, where $k$ is the correct unknown key.

Then, let us consider the values $\text{DES}_{k'}(P)$; there $k'$ ranges over the $2^{56}-1$ possible incorrect keys.  If we model DES with the incorrect key as a random permutation, then what we get is a list of $2^{56}-1$ random 8 byte values, each one of which has a $2^{-64}$ probability of just happening to be $C$.

Hence, the expected number of times the value $C$ appears on that list is $(2^{56}-1)2^{-64} \approx 2^{-8}$ (and the probability that the value $C$ appears at least once on the list is a tad smaller).

Hence, there does indeed exist a nontrivial probability that a brute force search would find two keys; the correct key $k$, and another key $k'$ that just happens to map $P$ to $C$.

Of course, in practice, we never really get only one plaintext block and one ciphertext block; we generally get additional ciphertext blocks that, at the very least, attempt to decrypt, and see if they make sense; that'll allow us to distinguish the correct key from any incorrect ones.


Help understanding syntax used in security proof

A simple way to understand it is to consider that the best algorithm we know to break CDH in $\mathbb{G}$ has advantage (id est: probability to win) is $\mathbf{Adv}^{\text{cdh}}_{\mathbb{G}}$.

You can suppose that this parameter is very small (exponentially small).

The goal of this theorem is to prove that if an adversary could break ake of SPAKE, $\mathcal{D}$, then this advantage (probability to win) is smaller of the right expression.

By looking the right expression, you deduce it's small (because $\mathbf{Adv}^{\text{cdh}}_\mathbb{G}$ is exponentially small)


what's the reason of the notational difference between statistical and computational indistinguishabilities?

You can define statistical security directly in terms of the statistical properties of different distributions. For example, you could define two distributions to be statistically close if their statistical distance is very small.
On the other hand, computational security is not precisely a statistical property of the given distributions.
As such, the two distributions under consideration may not be similar at all, in fact, they may be super different! but what matters for this notion of security is that it is not efficient to distinguish between the two.
To formalize this idea, you need to talk about distinguishers, which are algorithms that receive an input from one of the two distributions and try to guess which distribution it comes from.
This would the algorithm $A$ in your definition.
The intuition of the definition is that such algorithm will output some fixed value ($1$, in this case) with almost the same probability, independently from which of the two distributions the input is sampled from.


Is AES (or DES) provably secure? What is the hardness assumption underlying these cryptosystems?

No, there is no reduction from AES to any well-known hardness assumption; in other words, the hypothesis that AES is secure is an assumption by itself.

In fact, this is the case for every practical symmetric cipher that you can think off; provable constructions from a one-way function would be completely impractical.


AES + CBC encryption for a stream of UDP packets

At a high level, the major flaw is that you are rolling your own crypto protocol. You should strongly consider using a standardized protocol like DTLS.

Some specific problems:

Symmetric key distribution is left unspecified. Keys must be changed occasionally to thwart distinguishers.
No way to recover from symmetric key compromise.
Your message authentication code follows no existing standards and therefore is likely not secure.
If the attacker can get the IV, which is fixed, so likely not too hard, and can influence the first block of plaintext (which wouldn't be too hard since you are using timestamps), they can do some nasty things.
The fixed IVs add complexity that is unnecessary. For example, you have to trust the endpoints to not get the IVs mixed up.

There are probably a lot more issues that I haven't thought of in the short time I've been thinking about it. To solve this, use something standardized.


What's the name of this cipher? And how can it be broken?

This would appear to be CFB mode, only using a hash function (with a secret key as part of the input), rather than a block cipher.

As such, assuming that the hash function with the partially secret input acts as a random Oracle, this provides privacy.  However, it doesn't provide integrity (that is, the attacker can modify the ciphertext, and the resulting ciphertext will decrypt, and in fact produce semipredictable changes to the plaintext), and will probably end up being slower than a more conventional encryption method.


In a standard linear feedback shift register (LFSR), the succession of states
(generally taken to mean the shift register contents) is
predetermined; there is nothing random about the state transitions. Given
any state and the feedback polynomial, the next state can be readily computed.
Indeed, the states recur in periodic cycles.

In contrast, in a Markov chain, the next state cannot be determined from
knowledge of the current state; all we know are the (conditional)
probabilities that the next state is $S_j$ given that the current state is
$S_i$.  Think of it this way: the transition matrix of a $N$-state Markov
chain is a $N\times N$ matrix of transition probabilities. In contrast,
an LFSR with $N$ bits/symbols has $2^N$ (more generally, $q^N$) different
states, but its transition matrix is only an $N\times N$ matrix.  If you
were to write down the transition matrix in Markov-chain style, it would
be a $2^N\times 2^N$ matrix and all the transition probabilities (entries
in the matrix) would be either $0$ or $1$ and there would be exactly
one $1$ in each row and in each column, that is, it would be a permutation
matrix.


The problem is not broadcast, but secure broadcast. Secure broadcast guarantees that every recipient ends up with the same message.

If you just sign the message and send it separately to each recipient, a malicious sender could send different messages to different recipients.

A simple solution is that each recipient counter-signs the message and re-sends it to the other recipients. Once everyone has everyone's signature on the message, they accept.

There are better solutions, but all of them have an associated cost.


Simulating a joint distribution of an *almost* deterministic function

Lets first state the definitions. Consider a two party computation, where $i\in(1,2)$
Definition 1 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a probabilistic polynomial time algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:
$$[\mathcal{S}_i(x, f_i(x,y)), f(x,y)]\overset{c}\equiv [\text{view}_i(x,y), \text{output}(\pi)]$$
Definition 2 Let $f$ be a functionality, and $f_i$ be it's view from Party $P_i$. Let $\mathcal{S}_i$ be a simulator executing a deterministic algorithm for Party $P_i$. We say that $\pi$ securely realizes $f$ if there exist some $\mathcal{S}$ exists that satisfies the following property:
$$\mathcal{S}_i(x, f_i(x,y))\overset{c}\equiv \text{view}_i(x,y)$$
Definition 3 Probability distributions A(x,n) and B(x, n) are said to be Computational indistinguishably, denoted by $A\overset{c}\equiv B$ if $\exists$ a distinguisher D and negligible function $negl(.)$ s.t
$$\text{Pr}(D(A(x,n)) - Pr(D(B(x,n))) \leq negl(n)$$

Now notice the difference in the above definitions. The first definition talks about a probabilistic algorithm, while the second talks about a deterministic one. We're not talking about the $negl(n)$ difference in the output of the distinguisher, since that is already taken care of by the definition of Computational Indistinguishablity.
A functionality that has randomness is modeled by a probabilistic algorithm. In such a case, the functionality would present different output to both the parties.
So, the security definition for such a protocol would have to ensure that the joint distribution of simulator output and the functionality output are indistinguishable from the real world. If it was not indistinguishable, the simulator would be able to tell you the output for other party. Which would eventually mean that your protocol is insecure.
If the functionality presents the same outputs for the parties, the wouldn't be truly random. We call this functionality a deterministic functionality and we use Definition 2 to prove the security of the protocol that realizes it. Functionality $f(x,y)$  produces the same output for both the parties, so we don't need to care for whether it's joint distribution with the output of the simulator is indistinguishable from the real world.
Coming back to your question,you can certainly apply Definition 1 in your case (where the functionality is deterministic) since definition 1 is stronger notion than definition 2. However, you should go for Definition 2 since the presence of $negl(n)$ does not make your functionality probabalistic.
You can also refer to $\S$4.2 of https://eprint.iacr.org/2016/046.pdf by Lindell


Is there any ECDSA Attack if I have millions of signatures?

In the question's particular context, and ignoring the preamble, yes, the private key can be found (assuming the public key is known, which is a standard assumption). I see two ways, the first using no signature at all, the second likely requiring only a few ones.

Mere knowledge of the public key allows to find the private key for the curve secp112r1, using moderate brute force and 2009 technology. See Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery's Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, in IJACT 2012.
As an artifact of the code shown in the question, we get in the database the result of BigInteger e = new BigInteger(112, rand).Mod(n); where rand is an instance of the basic, non cryptographically-secure Random. With a little digging (left a an exercise to the reader) in the source code of this BigInteger constructor (likely equivalent to this) and of Random, it should be possible to mount an attack recovering the state of rand, and the rest is easy.

In real life, it is possible we would not be so lucky as to have the second avenue. Yet, if the non-cryptographically secure Random was used, we might be able to attack its seed, or multiple signatures could be sharing the same $k$ due to poor seeding (but in the question, repeated $k$ is unlikely).


Should I use NaCl or libsodium for my application?

(I don't have an opinion on NaCl as I've never used it. My understanding is that Libsodium uses NaCl in parts, and/ or re-implements it in others.)

As far as security goes, they should both be as equally secure. As far as I know they are both opinionated in that they don't provide you with an option to use less-secure techniques. In virtually every cryptographic primitive you seek, you will only find one or two more recent and more secure (ie. best-practice). This link elaborates on some of the design decisions:

https://libsodium.gitbook.io/doc/internals#security-first

Here is a good resource on Libsodium from Paragon - if you're using PHP you'll no doubt wind up here as the standard doco is a whole bunch of 'todo':

https://paragonie.com/book/pecl-libsodium

You don't specify a language, however, I have used Libsodium successfully across numerous Linux kernels, in PHP, Python (pysodium), Javascript, Windows 8.1+, and Android 7+ (via Termux). I have also interchanged certain primitives from pysodium with another Python library called cryptography.io (which relies upon OpenSSL).

One thing I like is the way the library provides two interfaces in many circumstances: a 'generically named' function, and an explicitly named one. For example, you can call crypto_aead_xchacha20poly1305_ietf_encrypt which explicitly defines the cipher in use, or, you can call crypto_secretbox and allow your cryptography to be 'upgraded' in the future if a newer version emerges that modifies default behaviour.

One shortcoming I have discovered so far, at least for pysodium's use of this library, is that the api exposure for Argon2id doesn't support associated data, whereas the actual algorithm code-base in the library does:

https://github.com/jedisct1/libsodium/blob/927dfe8e2eaa86160d3ba12a7e3258fbc322909c/src/libsodium/crypto_pwhash/argon2/pwhash_argon2id.c#L136
https://github.com/jedisct1/libsodium/blob/a97ab7085fcda73f4fc7dead1a499025ceda9ecc/src/libsodium/crypto_pwhash/argon2/argon2-core.c#L470

In practice, this wasn't an issue, as I just hashed the associated data with the password - however, this might be a problem in some implementations, especially if you're producing a PBKDF in parallel with another library's so you can exchange data (in an end-to-end protocol for example). If you're using Python, you can use the argon2-cffi implementation in most circumstances.

The lack of AES-ECB and AES-CBC ciphers has prevented me from using Libsodium exclusively on one MySQL-integration project, however, it was no drama to use cryptography.io as a bridge in that circumstance. That is how I started looking at compatibility between Libsodium and OpenSSL (via pysodium and cryptography.io).


Note that in the definition you gave, it says that in order for $\Pi$ to be an indistinguishable scheme, then the above inequality must hold for all PPT adversaries.

  So it seems that if $\Pi$ holds the indistinguishability, then there
  should not exist any adversary A that
  $\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] < 1/2 + \mathsf{negl}(\lambda)$, for it also means an A' that
  $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$.

If there is an adversary $A'$ such that $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] > 1/2 +\mathsf{negl}(\lambda)$, then $\Pi$ cannot be indistinguishable, by definition.

Another way to see it is that the only way $\Pi$ can be indistinguishable is that all adversaries $A$ have probability $1/2 + \epsilon$, at most, of guessing correctly, where $\epsilon \leq \mathsf{negl}(\lambda)$. Then, following your reasoning if you define an adversary $A'$ that simply outputs the opposite than $A$, its probability will be $1 - (1/2 + \epsilon) = 1/2 - \epsilon$, so the scheme is still indistinguishable.

  Hence my question is, why we don't define the indistinguishability
  directly via the conditional $\Pr[\mathsf{Exp}_{A',\Pi}(\lambda) = 1] = 1/2 + \mathsf{negl}(\lambda)$?

That definition would not be right, as the term $\mathsf{negl}(\lambda)$ is not actually a value, but an undetermined bounded function.

As mentioned in another answer, I personally don't like that definition either, although it is used in some places (see, for example, definition 7.2 in the Lecture Notes on Cryptography, by Goldwasser and Bellare). I also prefer definitions given in terms of the advantage of the adversaries, which is defined as $\mathsf{Adv}_{A,\Pi}(\lambda) = |\Pr[\mathsf{Exp}_{A,\Pi}(\lambda) = 1] - 1/2|$. In this case, the definition would be something similar to this:

  If for all PPT adversary A, there exists a negligible function $\mathsf{negl}$ that satisfies $ \mathsf{Adv}_{A,\Pi}(\lambda) \leq \mathsf{negl}(\lambda)$, then we say $\Pi$ is a indistinguishable scheme...


How to generate a certificate/PEM from specific plain text keys?

Yes, of course this is possible.

Generally you are required to first create a certificate (signing) request or CSR - a specific structure sometimes also called PKCS#10 after the standard that defines it. The certificate request contains the public key inside of it. This certificate request needs to be signed with the pre-established private key for the certificate. This certificate request can processed by a local or remote certificate authority, which returns the certificate. Commonly the certificate or certificate chain and the private key then need to be stored together into a (PKCS#12) key store.

Alternatively you should also be able to directly to create a self-signed certificate. Again, the public key is contained in the certificate. And again, the private key is required to perform the signing.

Note that the public key is commonly also contained in the (PKCS#1 or PKCS#8) structure of the private key. This means that you may not have to explicitly include it in any commands for creating the certificate request or self-signed certificate.

I found some answers on this page on how to do this with OpenSSL:

Generate a CSR from an Existing Private Key

openssl req \
       -key domain.key \
       -new -out domain.csr

Generate a Self-Signed Certificate from an Existing Private Key

openssl req \
       -key domain.key \
       -new \
       -x509 -days 365 -out domain.crt

here the domain.key is the OpenSSL PEM encoded private key.

I've tested both methods successfully after copying the private key to a file called domain.key. If this goes wrong, it's likely because of copying or system issues.


Maximum number of possible keys for a fixed-length password?

A password space with $n$ lower case letters, 1 upper case letters and one digit in any order is of size: $26^{n+1}*10*(n+2)*(n+1)$

The choice of the letters the times the choice of the digit times location of digit times location of the uppercase letter.


What are alternatives to number theory based crypto?

Code based cryptography like McEliece cryptosystem, is based on the hard problem of decoding linear codes. But i think it lies to the group of quantum based crypto since as far as we know it is still immune to quantum attacks


Can we decrypt in this order when the message is encrypted twice?

What you are asking appears to be 'is AES commutative'?
The short answer to which is no: encrypting with AES with key 1 then key 2 will not (generally) give the same output as encrypting with key 2 then key 1, which is what would be required for naive implementation.

However, there are modes in which AES can be used which would be commutative.
For example, if you run AES in counter mode, then after encrypting with key1 and key2 through counter mode, we would have that the final cipher text $c_i$ was:
$$c_i = m_i \oplus E_{k_1}(i) \oplus E_{k_2}(i)$$

Since XOR is commutative, we can write this as either

$$c_i = [m_i \oplus E_{k_1}(i)] \oplus E_{k_2}(i) = [m_i \oplus E_{k_2}(i)] \oplus E_{k_1}(i)$$

That is, whichever order you encrypt (and thus whichever order you decrypt) with respect to the two keys, you will reach the same ciphertext (and thus the same plaintext).

I haven't looked at it in detail, but I think the following article might be of use to you:
"Is there two key symetric commutative encryption function?".

Edit: Just to point out, if one was to use counter mode in this way, you would have to either make sure the counters are initialised at different values, or that the keys are different - otherwise your 'encryption' would become
$$c_i = m_i \oplus E_{k_1}(i) \oplus E_{k_1}(i) = m_i$$
Which is probably not a good thing...


How many different keystreams can I produce with AES in Counter Mode?

The number of different key streams depends on the keysize used and the number of bits in the nonce. Say you are using an $n$ bit key and $k$ bits for your nonce. Then the theoretical maximum number of keystreams is $2^n\cdot 2^k=2^{n+k}$ since each combination of nonce and key should result in a different keystream.

If you limit the length of your keystreams, however, this changes. Say you only want $128$-bit keystreams, but you use a $256$-bit key and a $64$-bit nonce. There will only be $2^{128}$ different key streams.

So, if your keystreams are $s$ bits long, you use an $n$ bit key, and a $k$ bit nonce, then really, the number of possible key streams is $\min(2^{s}, 2^{n+k})=2^{\min(s,n+k)}$.

Update
Based on the comment that the key is fixed, this changes the analysis. Since there is only one key it becomes $\min(2^{s}, 2^{k})=2^{\min(s,k)}$. The above analysis if for a randomly chosen key.


Using negative values / unsigned integers to implement SHA-2

The 32-bit values in SHA-256 are unsigned integers, which means the only values they are allowed to have are between 0 and 4,294,967,295, there are no negative values allowed.

If you look at the 4th initial value (0xa54ff53a), that has an integer value of 2,773,480,762. Implementing SHA-256 in programming languages that do not have the a 32-bit unsigned integer, but rather a signed integer, results in that value being interpreted as -1,521,486,534, but the bits of the value are still the same.

For modular addition that is not an issue, (see two's complement), but can be an issue for the shifting and rotations, which need to be performed across all 32-bits, and not just the lower 31. XOR also does not care if the numbers are signed are not, and since SHA-2 only uses addition, XOR, and shifting (and thus rotation), implementing SHA-256 in a programming language that only supports unsigned integers is possible, just maybe a little slower if you have to deal with rotation through shifting of a signed integer, like in Visual Basic 6.


RC4, finding key if we know plain text and ciphertext

The correct answer depends on whether you want to recover the key or the keystream. Let's first review how RC4 works:
RC4 Recap
RC4 takes a key as input and generates a cryptographically secure stream of pseudo random numbers:
$KS= RC4(k)$
To encrypt a plaintext message M, we simply XOR it with the keystream KS:
$KS= RC4(k)$
$C= M \oplus KS$
To decrypt the ciphertext, we have to reproduce the keystream by providing the same shared key as input to RC4:
$M= C \oplus KS$
Now, it is cruical that the same keystream is never used twice for encryptoin, since an attacker could learn the XOR of the two messages:
$C1= M1 \oplus KS$
$C2= M2 \oplus KS$
$C1 \oplus C2= M1 \oplus KS \oplus M2 \oplus KS= M1 \oplus M2$
Known-plaintext attacks against RC4
RC4 keystream recovery: This is a trivial thing to do once you are in possession of the plaintext:
$KS= C \oplus M$
This is normally not a problem since no one that has basic understanding of cryptography uses the same keystream to encrypt multiple messages. However, if I understand the description correctly, you have the following scenario:
$B= A \oplus RC4(K)$
$D= C \oplus RC4(K)$
If an attacker is in possession of A,B and D, it is trivial to extract the keystream generated by RC4(K) and decrypt the message C (at least up to the same length as A):
$C= D \oplus B \oplus A$
Example:
Let's say RC4 produces the following keystream:
KS= 11010110 00011010 01101011 10001110 11001101 11011111 01001010

With message A="hello" and C="secret!", you get the following ciphertexts:
A = 01101000 01100101 01101100 01101100 01101111
C = 01110011 01100101 01100011 01110010 01100101 01110100 00100001

B = 10111110 01111111 00000111 11100010 10100010
D = 10100101 01111111 00001000 11111100 10101000 10101011 01101011

By computing $A \oplus B$, you get the first 5 bytes of the keystream, which allows you to decrypt the first 5 bytes of C. Without the knowledge of the secret key or a longer plaintext-ciphertext pair you will not be able to decrypt the rest of C!
Note: You can already see in this example why it is a bad idea to re-use a keystream: the second byte of the ciphertexts of B and D are identical since they both encrypt the same character ("e").
RC4 key recovery: Recovering the secret key K is a much more difficult. There exist large classes of keys for which a small part of the secret key determines a large number of bits of the keystream. This is why it was recommended to throw away the first 256 bytes of the keystream (nowadays the recommendation is to not use RC4 at all). Observing enough plaintext/ciphertext pairs generated under a key can eventually be leveraged by attacks like the one by Fluhrer et al., leading to the recovery of the key by an attacker.


Implementing AES encryption for firmware distribution system

Yes, the IV (not "IV vector" because IV = "initialization vector" :p) is public and is only used to introduce randomness in the encryption process to prevent it being fully deterministic, while still preserving entropy in the key material.
You normally send the IV along with the ciphertext (yes, it is safe if you do it right), and how it is generated depends on the mode of operation (some, such as CBC, require unpredictable IV's, while others like CTR require only uniqueness). If you have no entropy source on the encryption machine, you can keep a permanent 64-bit counter and use that with CTR, but this has a lot of gotchas and is prone to error in general, randomness is usually the safest thing to do.
No, only pure block modes such as ECB or CBC "require" the plaintext to be a multiple of 128 bits long, but this can be fixed through padding (adding some extra bytes to complete the final block, adding enough information in it so that the decrypting machine can remove the extra padding without confusion) - note this isn't completely safe either and can lead to ingenious attacks.

Other modes of operation don't actually work on the plaintext directly, but generate a bitstream of any length from the key (there is a limit but with modern ciphers it is essentially infinite) and exclusive-or it with the plaintext - this way the plaintext can be any length you want. E.g. if you wanted to encrypt a 300-bit message in AES128 with CTR mode, this is how it would go:

choose your 128-bit IV
encrypt the IV with AES128 with the key
XOR this 128-bit block with the first 128 bits of plaintext
increase the IV (before you encrypted it) by one and encrypt it again
XOR this 128-bit block with the next 128 bits of plaintext
increase the IV by one and encrypt again
you only have 44 bits of plaintext left, so XOR the first 44 bits of the 128-bit block with the remaining plaintext bits and throw away the rest

Does it make sense?


They are used to encrypt symmetric keys.  No.


Why not put MAC in fixed position and cover padding for MAC-then-encrypt?

You scheme, let's call it pad-MAC-encrypt, would indeed fix any padding oracle attacks against MAC-pad-encrypt.

The reason it isn't used is probably that padding oracle attacks weren't known when CBC schemes were initially defined and now that they are known, there doesn't seem to be a convincing use case for CBC. Other modes have advantages over CBC anyway (no requirement for unpredictable IV, easier parallelizability). If you do need CBC for some reason (like backwards compatibility), you can just use encrypt-then-MAC which is simple and well understood.

I.e. rather than asking why it is not used, you should be asking what the advantage is over other safe schemes.


$$\texttt{NO}$$

In short;

$$\text{We are living in a world where that is ruled by Kerckhoffs's principles}$$

The above may not be totally clear as indicated by Maarten in the comments. The We is the Modern Cryptographers, the World is used for the Cryptography,... In other words, and better;

$$\text{Modern Cryptography keeps to Kerckhoff's principles}$$

Decoding lost languages is not related to cryptography, though some techniques may be related like frequency analyzing. That is people tend to give names to some common objects like the sun, earth, man, women, child, etc.

  Does that mean that you can better protect data by making your own language than by encrypting an existing one?

Go on build one, then;

On day one, one will sell the decoding. Then you need to change your language and then you have to teach it, everybody. In Kerckhoffs's principle, the system relies on the secrecy of the key, not the system. If the key is sold or compromised, we can change the key, not the system. Of course, we assuming that the encryption system is designed to stay against cryptography attacks like AES that stands for almost 20 years and expected to stand more.
The more you talk the more information you will give to decode. You can get the notion from the researcher who goes into amazon forest to communicate with people who had no contact with other humans in centuries.
Actually, you build a large permutation cipher, that is breakable.

  Or are all human languages really just different mappings of symbols to the same or similar ideas meaning that decryption and translation are the same things?

That is not exactly. For example; some languages don't have a name for the color pink or other. Some missing other words for describing things/actions etc where it exists in some languages. Culture, living area affects the language. This is out of the Cryptography context.

  Would creating a custom human language be stronger protection than encrypting a known human language?

NO

Let finish with the Kerckhoffs's principles

The system must be practically, if not mathematically, indecipherable;
It should not require secrecy, and it should not be a problem if it falls into enemy hands;
It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will;
It must be applicable to telegraph communications;
It must be portable, and should not require several persons to handle or operate;
Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules.


DGK Cryptosystem Key Generation and Decryption Issues

Just in case someone else is trying to implement this cryptosystem, I wish to share the implementation that I am currently using. Someone helped me pick another approach for generating $ h $ and $ g $, and, intuitively, it seems secure.

In order to generate $ h $ and $ g $, I now apply certain algorithms described in the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone

Specifically, I use Algorithm 4.83, Chapter 4: Selecting an element of maximum order in $ \mathbb{Z}_n^* $, where $ n = p q $:

INPUT: two distinct odd primes, $ p $, $ q $, and the factorizations of $ p - 1 $ and $ q - 1 $.

OUTPUT: an element $ \alpha $ of maximum order $ lcm(p - 1; q - 1) $ in $ \mathbb{Z}_n^* $, where $ n = p q $.

Use Algorithm 4.80 with $ G = \mathbb{Z}_p^* $ and $ n = p - 1 $ to find a generator $ a $ of $ \mathbb{Z}_p^* $.
Use Algorithm 4.80 with $ G = \mathbb{Z}_q^* $ and $ n = q - 1 $ to find a generator $ b $ of $ \mathbb{Z}_q^* $.
Use Gauss's algorithm (Algorithm 2.121) to find an integer $ \alpha $, $ 1 \leq \alpha \leq n - 1 $, satisfying $ \alpha \equiv a \pmod p $ and $ \alpha \equiv b \pmod q $.
Return $ \alpha $.

For completeness, here are the two algorithms referenced above in Algorithm 4.83:

Algorithm 4.80, Chapter 4 : Finding a generator of a cyclic group:

INPUT: a cyclic group $ G $ of order $ n $, and the prime factorization $ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} $

OUTPUT: a generator $ \alpha $ of $ G $

Choose a random element $ \alpha $ in $ G $
For $ i $ from $ 1 $ to $ k $ do the following:

Compute $ b \gets a^{n/p_i} $ (N.B. $ \pmod n $)
If $ b = 1 $ then go to step 1.

Return $ \alpha $.

Algorithm 2.121, Chapter 2 (Gauss's algorithm):
The solution $ x $ to the simultaneous congruences in the Chinese Remainder Theorem (Fact 2.120) may be computed as $ \sum_{i = 1}^{k}{a_i N_i M_i \pmod n} $, where $ N_i = n / n_i $ and $ M_i = N_i^{-1} \pmod {n_i} $. These computations can be performed in $ O((\lg n)^2) $ bit operations.

Fact 2.120, Chapter 2: (Chinese remainder theorem, CRT) If the integers $ n_1 $, $ n_2 $, ..., $ n_k $ are pairwise relatively prime, then the system of simultaneous congruences

$ x \equiv a_1 \pmod {n_1} $

$ x \equiv a_2 \pmod {n_2} $

$ \vdots $

$ x \equiv a_k \pmod {n_k} $

has a unique solution modulo $ n = n_1 n_2 \cdots n_k $.

In order to apply Algorithm 4.83, we require the factorizations of $ p - 1 $ and $ q - 1 $. The standard approach would be to just factor the random ~200 bit factors $ p_r $ and $ q_r $. On the other hand, assuming that we don't break the security assumptions, we can use $ p_r = 2 p_r' $ and $ q_r = 2 q_r' $, where $ p_r' $ and $ q_r' $ are random primes of the required size. After ensuring that $ p = 2 p_r' v_p u + 1 $ and $ q = 2 q_r' v_q u + 1 $ are also primes, we may compute $ h $ and $ g $ with the above algorithms:

First, we compute $ h_r $ and $ g_r $ of order $ LCM(p - 1, q - 1) = (p - 1)(q - 1) / GCD(p - 1, q - 1) = 2 u p_r' v_p q_r' v_q $ in $ \mathbb{Z}_n^* $ with Algorithm 4.83
$ h $ must have order $ v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ h = h_r^{2 u p_r' q_r'} \pmod n $
$ g $ must have order $ u v_p v_q $ in $ \mathbb{Z}_n^* $, so we set $ g = g_r^{2 p_r' q_r'} \pmod n $

And that about wraps it up. Please feel free to add comments if more explanations are needed.

PS: The factor $ 2 $ is required for $ p - 1 = 2 p_r' v_p u $ and for $ q - 1 = 2 q_r' v_q u $ because the product of three odd primes is odd, and, thus, by adding one, we get an even number larger than 2, which can't be prime, but both $ p $ and $ q $ need to be prime numbers.


Cipher Text generated is different if nonce is greater than 12 bytes

Forget the other websites for comparison, you can fall into traps of inconsistent codes. Either use the OpenSSL as a comparison or better use the NIST test vectors;
GCM Test Vectors (SP 800-38D)


SNFS: Quantifying the "small" parameters?

We summarize the discussion of parameters to express numbers suitable to be factored::

$$ N = C_1 r^t + C_2 s^u $$

by the Special Number Field Sieve (SNFS) from the paper "An Implementation of the Number Field Sieve" by Marije Elkenbracht-Huizing (1996).

She describes the Number Field Sieve this way:

  Let $n$ be the odd number to be factored.  It is easy to check whether $n$ is a prime number or a prime power ,and we assume that it is neither. Like [Multiple Polynomial Quadratic Sieve], the NFS tries to find a solution of the equation $v^2=w^2 \bmod{n}.$ For at least half of the pairs $(v \bmod n, w \bmod n)$ with $v^2\neq w^2 \bmod n$ and $v$ and $w$ relatively prime to $n$, the greatest common divisor of $n$ and $v-w$
  gives a nontrivial factor of $n$.

  To construct $v$ and $w$ we first choose two polynomials $$ f_1(x) = c_{1,d_1}x^{d_1} + c_{1,d_1-1}x^{d_1-1} + \ldots + c_{1,0} $$ $$ f_2(x) = c_{2,d_2}x^{d_2} + c_{2,d_2-1}x^{d_2-1} + \ldots + c_{2,0} $$ over $\mathbb{Z}$, with $f_1 \neq \pm f_2$, both irreducible over $\mathbb{Z}$ and having content $\text{cont }f_i := \gcd(c_{i,d_i},\ldots,c_{i,0})$ equal to $1$; we also choose an integer $m$ that is a common root modulo $n$ of $f_1$ and $f_2$.  In our implementation this is the only step in which the SNFS and the GNFS differ: in the SNFS we use the special form of $n$ to pick these polynomials by hand.  One
  polynomial will have very small coefficients compared to the coefficients of the polynomials we will use with the GNFS, where we search for a pair of polynomials with help of the computer.  This makes SNFS faster than GNFS.

Tying what makes "SNFS faster than GNFS" to a manual process of picking a pair of (integer) polynomials (so that "one polynomial will have very small coefficients" compared to the polynomials "where we search... with help of the computer") makes the distinction contingent on the (advancing) state of the art in computer search for polynomials.  Potentially the algorithms for polynomial selection will improve so far as to practically erase the distinction.

Analysis of what effect small coefficients have on the algorithm (in particular on the speed of the sieving phase) is beyond the limits of the present post.  However useful perspective comes from examining the cases set out by Elkenbracht-Huizing's paper.  Here are simplified tables of various factoring successes listed there:

Table 1: SNFS Example Polynomials and Timings
$$ \begin{array}{|l|c|c|c|}
\hline
n \text{ factor of } N & f_1(x) & f_2(x) &
\begin{array}{c} \text{sieve} \\ \text{hours} \end{array}
\\
\hline
\begin{array}{c} \text{C98 from } \\ 7^{128} + 6^{128} \end{array} &
x^4 + 1 & 6^{32}x - 7^{32} & 450
\\
\hline
\begin{array}{c} \text{C106 from } \\ 2^{543} + 1
\end{array} &
\begin{array}{c} 4x^4 \\+2x^2 + 1 \end{array} & x - 2^{90} & 250
\\
\hline
\begin{array}{c} \text{C119 from } \\ 3^{319} - 1
\end{array} &
\begin{array}{c} x^5 + x^4 \\ - 4x^3 -3x^2 \\+3x + 1\end{array} &
\begin{array}{c} 3^{29}x \\- (3^{58} +1) \end{array} & 800
\\
\hline
\begin{array}{c} \text{C123 from } \\ 2^{511} - 1 \end{array} &
\begin{array}{c} x^6 -10x^4 \\+24x^2 -8\end{array} &
\begin{array}{c} 2^{36}x \\- (2^{73} +1) \end{array} & 700
\\
\hline
\begin{array}{c} \text{C135 from } \\ 73^{73} - 1 \end{array} & x^5 + 73^2 & x - 73^{15} & 2150
\\
\hline
\begin{array}{c} \text{C165 from } \\ 12^{151} -1 \end{array} & 12x^5 - 1 & x - 12^{30} & \lt 1680
\\
\hline
\end{array} $$

Table 2: GNFS Example Polynomials and Timings
$$ \begin{array}{|l|c|c|c|}
\hline
n \text{ factor of } N & f_1(x) & f_2(x) &
\begin{array}{c} \text{sieve} \\ \text{hours} \end{array}
\\
\hline
\begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} &
\begin{array}{c} 1.5E20x^2 \\ - 1.4E21x \\- 8.3E21 \end{array} & \begin{array}{c} 1.0E21x^2 \\ + 7.0E21x  \\- 7.4E22\end{array} & 2100
\\
\hline
\begin{array}{c} \text{C87 from } \\ 72^{99} + 1 \end{array} &
\begin{array}{c} 7.3E8x^2 \\ + 2.0E20x \\- 7.8E33\end{array} & \begin{array}{c} 2.2E9x^2 \\ - 7.9E21x  \\- 2.3E34\end{array} & 1500
\\
\hline
\begin{array}{c} \text{C97 from } \\ 12^{441} + 1 \end{array} &
\begin{array}{c} -3.0E10x^2 \\+ 4.4E23x \\+ 3.6E36 \end{array} &
\begin{array}{c} -5.4E11x^2 \\ - 4.8E24x  \\+ 6.3E37 \end{array} & 3500
\\
\hline
\begin{array}{c} \text{C105 from } \\ 3^{367} - 1 \end{array} &
\begin{array}{c} 3.4E11x^2 \\ + 8.7E25x \\+ 5.4E38\end{array} &
\begin{array}{c} 1.2E12x^2 \\ - 9.1E26x  \\+ 1.3E41 \end{array} & \lt 7680
\\
\hline
\begin{array}{c} \text{C106 from } \\ 12^{157} + 1 \end{array} &
\begin{array}{c} 1.9E11x^2 \\ - 1.0E26x \\- 3.2E40\end{array} &
\begin{array}{c} -7.9E11x^2 \\ - 4.0E26x  \\+ 1.6E41 \end{array} & 11900
\\
\hline
\begin{array}{c} \text{C107 from } \\ 6^{223} + 1 \end{array} &
\begin{array}{c} -5.4E11x^2 \\ - 4.3E26x \\- 4.7E40\end{array} &
\begin{array}{c} -2.4E11x^2 \\ + 7.6E26x  \\- 3.1E41 \end{array} & 11200
\\
\hline
\end{array} $$

I'll append some additional remarks, but the first columns describe the number of digits of a composite factor of an expression, the second and third columns give the pair of polynomials used (in "scientific notation" for the large integer coefficients of the GNFS; see paper for exact values), and the last column gives a rough timing for the sieving (of relations) step.


Security of (cryptographic) padding compared to other methods for blockcompletion for block ciphers

The security of these schemes is all comparable, as far as I am aware.  In all cases, you need to use authentication (e.g., Encrypt-then-MAC).  Padding attacks are just one way that security can fail if you omit the authentication, but all of these schemes will have serious security problems if you omit the authentication.  So, don't forget the authentication.

Bottom line: I don't know of any compelling security reason to choose one of these methods over any other, assuming that you are using the crypto correctly.  You can choose on other grounds, e.g., interoperability, performance, ease of implementation, etc.


Which method to generate one time password?

Yes, your best choice is indeed to use a key derivation function.
However you should consider using the TLS-PSK set of cipher suites for your needs. If you use the variant with DHE / ECDHE key exchange (recommended) included you don't have to rely on your passphrase being strong for security, both the password and the discrete logarithm have to be disclosed in order to recover the message.
In both cases (with and without additional key exchange) the TLS nonces will be used to aid master secret derivation, meaning you get unique master secrets even if re-use the static passphrase without additional key-exchange.

As for the cipher suites something like TLS_DHE_PSK_WITH_AES_128_GCM_SHA256 seems like the best choice at the moment or TLS_PSK_WITH_AES_128_GCM_SHA256 if you want to solely rely on your passphrase. As for what to input as PSK, either a hash of the passphrase directly (high entropy case) or a master secret like constructed in the next paragraph(s) is fine (in the low entropy case).

If you're only relying on your passphrase for confidentiality and your passphrase may have low entropy, you should use a password-based key derivation function (PBKDF), for which you can negotiate a key as follows:

$$A\rightarrow B: R_A$$
$$A\leftarrow B: R_B,C_B$$
$$A\rightarrow B: C_A$$

with $R_A,R_B$ being random 128 bit strings and $C_A,C_B$ being key-confirmation values. The 128/256-bit master secret $MS$ is calculated via $MS=PBKDF(PW,R_A||R_B)$ with the second input being the salt. From this you can derive as many keys as you want via HKDF-Expand and you can calculate the $C_A=HMAC_{MS}(R_A||R_B),C_B=HMAC_{MS}(R_B||R_A)$, note that the order matters or replay attacks apply.

As for the algorithmic choices for this and the following approach you should use SHA-256 or SHA-3-256 as your hash functions and Argon2 as your PBKDF.

If you're only relying on your passphrase for confidentiality and your passphrase has high entropy, you should use a key-based key derivation function (KBKDF). More concretely you want to use HKDF with a salt that you exchanged just-in-time via the above protocol with HKDF-Extract replacing the PBKDF.

TL;DR: Use TLS-PSK with strong cipher suites and / or apply a strong PBKDF (like Argon2) using a negotiated salt for key derivation.


Determine Encryption Used by Examining File Headers?

That depends. A file cannot be directly encrypted by a block cipher. You need at least a mode of operation for that block cipher and an IV. I guess you should first determine the correct encryption format that was used.

If your file is directly encrypted you could try and decrypt using one of the two methods. If the result looks like a file then the right mode must have been chosen. You can e.g. test this by using the file command on Posix systems after decrypting the first kilo byte of the file (into a separate, partial file).

Alternatively you could perform a simple randomness test on the result. If that fails, then it is likely a correct file and the correct algorithm. This may however lead to more false positives than the method used above. You may want to test which of the partially decrypted files is least random and chose that algorithm.


This is what Elligator was designed for.
Specifically, the Elligator 2 is suitable for Curve25519 which maps a 32 bytes integer to a point on the curve.
As for implementations of this map:

libsodium: the implemented function maps a $32$ bytes vector to a point that belongs on the prime order subgroup on the Edwards form of Curve25519, by multiplying by the curve cofactor; but not the inverse map;
Monocypher implements the map and its inverse, but the points seem to be on the Montgomery form so it might be needed to convert the points to the Edwards form if necessary, and additional code in Python is present for Edwards form of Curve25519;
C implementation of elligator 2: words for Curve25519.

For information, there is a version made for prime order curves in Weierstrass form called Elligator squared.
Thanks to xorhash for additional links.


The attacker model of the Lucky13 attack in TLS

The Lucky13 article on Our Results;

... attacks can be mounted by a standard man-in-the-middle (MITM) attacker who sees only ciphertext and can inject ciphertexts of his own composition into the network.

Definition of passive and active MTIM from sll.com

Passive MITM: In a passive MITM attack attackers ‘tap’ the communication, capturing information in transit without changing it.
Active MITM: If attackers attempt to modify or tamper with the information itself they are committing an active MITM attack. A very common way to launch a MITM attack is by creating a fake node on a publicly-available computer network, such as a coffee shop's WiFi network.

Injection is an attempt to modify therefore it is an active MITM attack.
on the discussion;

We reiterate that the attacks are ciphertext-only, and so can be carried out by the standard MITM attacker, without a chosen-plaintext capability.

Chosen plaintext attack means; the attacker obtains encryption of plaintexts of his choice. So, in Luck13, the attacker only used ciphertext that they can obtain and injected them into the network.


The ideal cipher model is a way of modeling of block cipher (i.e. a keyed permutation family) which is very close to the modelization of a hash function by a random oracle. In fact, these two models are even equivalent (see http://arxiv.org/abs/1011.1264).

Recall that a random oracle is a "magic box" with for any new input outputs a purely random value (for repeated inputs, the oracle just repeats itself). A ideal cipher behave similarly given a new input pair (K,x), the ideal cipher outputs a random value y, with a small caveat: instead of being chosen at random for a fixed set, y is chosen among the values which have not yet been used for the key K.

Ideal ciphers can appear in security proofs to show that a mode of operation is secure with a "perfect" blockcipher. In particular, when working in the ideal cipher model, you implicitely assume that your blockcipher is secure against related-key attacks.

However, as with the random oracle model, it is possible to construct cryptographic primitives (albeit artificial ones), which are secure in the ideal cipher model and insecure when instantiated with any real blockcipher. For this reason, proofs in the regular security model (where the blockcipher keyed with a random key is indistinguishable from a random permutation) are considered to be much more representative of real-life security.

If you are interested by proofs in the ideal models (RO or ideal cipher), look for papers about indifferentiability.


Can I retrieve a re-hashed (hash) value, for instance by additional hashing?

Short answer; Almost NO!

Can I have it by keep hashing the second one?

There were great answers for the question; Cycles in SHA256
In short, if we model SHA256 as a uniform random function then the probability of element being on the cycle is
$$\frac{1}{\sqrt{\hspace{.03 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}\pi} \cdot 2^{127}}$$
The average cycle length with expected value for SHA256 is $$2^{127} \sqrt{2\pi}$$
Simply consider the first hash $\operatorname{SHA256}(m)$ as the starting point;

As one can see that being on a cycle has a very low probability and you almost find none in a cycle since the probability is $\frac{1}{\sqrt{2\cdot \pi} \cdot 2^{127}}$.
Even it is on a cycle, you almost certainly can not calculate the cycle to find the pre-image since the average cycle length is $2^{127} \sqrt{2\pi}$.

These are from the result of Bernard Harris's magnificent work; Probability Distributions Related to Random Mappings in 1960.

Also, this exists in the Handbook of Applied Cryptography - Fact 2.37

tail lenght = $\sqrt{\pi n /8}$
cycle lenght = $\sqrt{\pi n /8}$
rho-lenght = $\sqrt{\pi n /2}$