The key is obtained by taking the encryption steps in reverse.
For example, let's encrypt the word "United" with that 4 3 1 6 2 5 key.
The first step is to take the 4th letter, a "t" and make it the first.
In the decryption, this first ciphertext letter must go to the 4th place again.
So the fourth step in the decryption, must be to look at what is in the first position - a "t" - and put that back in the fourth place again. Indeed we see in the decryption key that "1" is the value its fourth member.
By continuing these steps, you can derive the inverse key.

Here is a little code snippet that does the calculation.

static int[] inverse_key( int[] key )
{
    int[] inverse_key = new int[ key.length ];
    for ( int i = 0; i < key.length; i++ )
    {
        inverse_key[ key[ i ] - 1 ] = i + 1;
    }
    return inverse_key;
}

The "-1" and "+1" in the code are because arrays in most programming languages are 0-based; they do not relate to the actual algorithm.


Why is CBC-MAC with length appended not secure?

I'll give you a hint, and you can work out the details yourself.

Take any $m_1,m_2,m_3$ of length $n$ (where $n$ is the block length), with $m_1\neq m_2$. Query the oracle with $m_1$, then query the oracle with $m_2$, and finally query the oracle with $m_1\|n\|m_3$.

Work through this, and you can find a message and its forgery.


What is the role played by cache misses in memory-hard password hashing?

I understand, using large memory (1GB or greater) prevent parallelism, because of the cost. I would like to support mobile and older browsers, so I use 16MB or 32MB memory maximum.

This is true, but 32mb memory is fairly safely OK for most applications.

  Is it because my benchmarks wrong or is not generate a lot cache misses I thought or cache misses not affects like the processing?

Problem of password cracking isn't mere 16 threads that a CPU can pull off. CPU is fairly complex thing and even if it can't cache whatever you throw at it, it has multiple channels of high-speed ram with capacities reaching into terabytes for powerful servers.

Problem starts when everyone has thousands of processors in their computer. This is case right now with GPUs. GPUs make use of massive parallelism. This makes some tradeoffs, for example every thread has tiny amount of memory and no cache. Common GPU programming technique require that data to be accessed next is fetched earlier and saved in that reduced space. This obviously can't happen with 32mb table, which is further limited by huge performance cost of accessing global GPU memory (and you have thousands on threads all accessing some random informations). And you don't even have enough memory in GPU to run 1000 threads at once.

Argon also tries to combat all kind of premade chips to break it quickly by using a lot of memory quickly: your can't just invest into a lot of quickly-hashing chips because they will need megabytes or more per one chip.

So if you were running your benchmarks with CPUs this is expected that it will run this algorithm fairly well. After all argon2 was made so that it runs efficiently on multiprocessor CPU, but not on GPU or ASIC.


AES - MixColumn transformation using the identity matrix

If you eliminate the MixColumn (or equivalently, replace it with an identity Matrix), then the resulting cipher will effectively be 4 independent 32 bit block ciphers.  This happens because what happens in one 32 bit row no longer has any propagation to any of the other 3 32 bit rows.

This results in a much weaker cipher; not only would that bring up possible chosen plaintext/ciphertext attacks (where you modify one of the 32 bit blocks, but leave the other 3 the same), you would also have ciphertext only attacks with a birthday bound of circa 256k...


AES vs RSA - Which is stronger given two scenarios?

It is also assumed that an attacker doesn't know anything about the secret key used as input to the AES algorithm.

Now lets assume that for either algorithm a mode of operation is used that sufficiently protects the ciphertext (say AES-CTR and RSA-OAEP). Then it comes down to analysing the security of the cipher itself given the key size.

Neither AES nor RSA has been broken in the sense that it is much less secure than the strength it was designed for. The key size is therefore easy: AES-256 has close to 256 bits of security while RSA only offers about 112 bits of security. In that respect AES-256 has RSA-2048 completely beat.

As for the algorithm, AES-256 is considered secure against analysis with quantum computers. RSA is definitely not, given a large enough quantum computer. The only disadvantage of AES is that there is no security proof of the algorithm itself. We suppose it is secure, but we're not certain. RSA probably has a slightly better mathematical problem behind it.

Operationally speaking: it is much more likely that AES is implemented / executed correctly rather than RSA.

All in all I'd strongly recommend AES given your question.

But in the end recommending one over the other is futile; an asymmetric cipher has different properties and should be used in different scenarios than a symmetric cipher.

Say for instance that the system that performs the encryption is not as secure as the system that does the decryption. In that case RSA is a much better fit than AES as RSA encryption only requires the public key to be present.

Distributing a public key is of course also a completely different fish than sharing an AES secret key. With a public key you can distribute freely as long as the receiver can trust the public key. With AES you need a secure channel in advance.


Discrete Gaussian Sampling role in Lattice-Based Crypto?

A Gaussian distribution satisfies the following desirable properties:

It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, then $(x_1,x_2,\ldots,x_n)$ is sampled from a multivariable Gaussian distribution.
It approximates a uniform error distribution modulo a lattice exponentially well, regardless of what the lattice is.

The first property makes implementation easy, and the second property makes security proofs easy, since many security proofs in lattice-based crypto involve switching around the lattice lots of times until you get what you want.

To show what I mean by the second property, let's consider a one-dimensional lattice $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\} \subset \mathbb{R}^1$. Take a normal distribution with standard deviation $1/2$. In other words, just your average normal distribution:

Suppose that I sample real numbers from this distribution and take the fractional part of the resulting real numbers. (Taking fractional parts correpsonds to taking error vectors with respect to the lattice $\mathbb{Z}$.) The resulting distribution amounts to taking the original normal distribution, chopping it up into unit intervals $\ldots, [-2,-1], [-1,0], [0,1], [1,2], \ldots$, and adding them up. When we do that, we get something quite magical:

Notice how close this distribution is to uniform! The "radius" or standard deviation of this distribution is only $1/2$, which is not much larger than the size of the unit interval; in fact it's smaller. Even with such a small radius, we get a ridiculously good approximation to the uniform distribution. You can prove (and you should prove, as an exercise) that the quality of the approximation is independent of the choice of where the original normal distribution is centered.

Suppose we take a slightly larger normal distribution, say with standard deviation $2/3$:

If we graph the fractional part of this distribution, we get:

That's really really good! You can't even tell that it deviates from uniform. In mathematical terms, we say that the distribution is exponentially close to uniform. Even a small increase in the width of the distribution (from $1/2$ to $2/3$) improves the quality of the approximation dramatically.

You might say, what's the big deal? We can easily get a uniform distribution on any interval. But that's not the point. In lattice-based cryptography, you often don't know what the lattice is. (It's part of someone's secret key.) Suppose as an exercise that we didn't know what this lattice is, and we tried to sample error vectors by taking them uniformly from an interval $[0,n]$ for some $n$. We can't just take the perfect choice of $n=1$. That's cheating, since we're assuming we don't know what the lattice is. In this case, any choice of a small number $n$ will cause the distribution to be horribly wrong; for example, if we chose $n=2/3$ in this scenario, then all of our error vectors would lie in $[0,2/3]$, which is far from uniform in $[0,1]$. Even a slightly larger $n$ is no good; for example if $n=3/2$ then random real numbers sampled uniformly from $[0,3/2]$ will be much more likely to have fractional part (i.e. error vector) lying in $[0,1/2]$ than in $[1/2,1]$. Of course, a very large $n$ (say $n \approx 10^9$) would do the job, but that's exactly the problem: since our distribution on $[0,n]$ doesn't converge to the uniform distribution on $[0,1]$ exponentially fast (unless we cheat by taking $n \in \mathbb{Z}$, which is not allowed), we end up needing to take very large values of $n$, which is not only hard to implement, but a nightmare in security proofs where theoretical analysis is required.

What you need is a way to approximate uniform error vectors exponentially well, without relying on prior knowledge of what the lattice is. Gaussian distributions do that job.


Is there a way to use Shamir Secret Sharing with updatable data?

I think there's a better way to do this, and I'm not sure the existing answers check all your boxes. I suggest using secret splitting together with asymmetric keys so that:

Nobody but you can write data.
Shareholders can come together to read data.
Each shareholder can individually verify, but not read data.
You can read and write data at any time.

Here's how I'd do it:

Create asymmetric (e.g. RSA) key pair "A".
Split the private half of A into $s$ shares, where $s=nx+t$.
Keep $t$ shares for yourself.
Create asymmetric key pair "B".
Give $x$ shares in A and the public half of B to each trusted person.
Secure the public half of A and the private half of B and keep them to yourself.
Create your data, encrypt it using the public half of A, then sign it using the private half of B. Distribute the signed, encrypted data.

Each shareholder can use the public half of B to verify the encrypted data; they may do this alone and at any time. Shareholders may combine their shares to recover the private half of A, which can then decrypt the data.

You, may at any time, use your shares to recover the private half of A and read the data. Also at any time, and as often as you wish, you may create new and/or additional data, encrypt and sign it, and distribute to your trusted people.


Are commutative digital signature possible?

Let a signed message consist of a bit string $m$ and a set of signatures $\Sigma$.  A ‘signed message’ of a bit string $m$ with no signatures is $(m, \{\})$.  When the $i^{\mathit{th}}$ user signs $(m, \Sigma)$, they return $(m, \Sigma \cup \{\sigma\})$ where $\sigma = \operatorname{Sign}_{S^i}(m)$.  The verifier confirms that there are signatures by all the signers they care about on the message.

This works with any base signature scheme, like Ed25519.  If a signature appendix in the base signature scheme adds $s$ bytes, and there are $n$ signatures, a signature appendix in this composite signature scheme adds $s\cdot n$ bytes, and the cost of verification is at most $s$ times the cost of verification of the base signature scheme.

If this doesn't satisfy your goals, you'll need to be more specific about what they are!


Recommended Books for Cryptography : Theory and Implementation

Theory and practice: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno

Design and some implementation tips are in Cryptography Engineering too. Code writing is highly dependant on the library you're using, so you should read its documentation first.

Development is covered, again, by Schneier's book. As for future possibilities: you'd need to subscribe to cryptography journals.

The older books (Practical Cryptography and Applied Cryptography) are good too, but don't cover the newest algorithms (AES, SHA-2, elliptic cryptography).


Does IKEv2 have some mechanism by which it negotiates those fields to the "highest common denominator"?

Well, IKEv2 allows the initiator to list what DH Groups, Encryption algorithms and Authentication algorithms (among others), and in what combinations; the responder then selects from that list what will be used.  It's actually pretty flexible (except for DH group; that's a bit kludgy, as the initiator has to select a 'main one', and if the responder doesn't like it, it needs to list what DH group it really wants, and we take another round trip with that group).

Now, the initiator lists things in preference order (e.g. the encryption algorithm it would prefer is listed first), and the responder is supposed to respect that order.  There's no built in logic within the IKE protocol itself that says, for example, AES-GCM is better (or worse) then ChaCha20; that's something for the initiator to decide.

  When IKEv2 "mode" is selected, the UI disables the DH Group, Encryption, and Authentication fields, and I can't find what values are used, anywhere in the documentation.

This is definitely something that ought to be both changeable and documented; if would appear unlikely that you could come up with a single policy that would make everyone happy.


The scheme you propose certainly leaks plaintext repetitions to an attacker since the same plaintext is always encrypted to the same ciphertext. You typically don't want this and it can be disastrous if the attacker knows some of the messages.

If you are absolutely sure that leaking repetitions is no problem in your case, you can use an authenticated encryption scheme with nonce-misuse resistance. Note that not all authenticated encryption schemes have this property. If you use a scheme with nonce-misuse resistance, you can even use the same nonce (say $0...0$) for all messages, so you don't need the hashing trick. If it is not, a hash function that is not collision resistant does not make it secure because an attacker can find different messages that hash to the same value, so you will end up using the same nonce for different messages. I don't know whether ChaCha20 Poly1305 together with a cryptographic hash function provides nonce-misuse resistance, but unless this is proven somewhere (or at least some other evidence is provided), you should not assume it.


BGV for three multiplication level/depth

Actually It depends on which library you use. If you use Palisade, you can set numberoftowers (L level) to 3.


The key is 4 characters long, therefore it must be in a 2 × 2 matrix. The numbers in this matrix must be the inverse of the encryption key matrix, and there are various methods to work this out (see this link). Once the matrix inversion has been calculated, you multiple it through each part of the cipher text in their respective 2 × 1 matrices


(Non-) Perfect Secrecy of Vernam Cipher Using $E(m) = m \oplus k \oplus \operatorname{rev}(k)$

While the other answer is correct, there are multiple ways to disprove a theorem.

In your case you want to disprove $$\Pr[\mathcal M=m|\mathcal C=c]=\Pr[\mathcal M=m]$$ holds for $$c=m\oplus k \oplus \operatorname{rev}(k)$$.

The first one is to argue using the probabilities and show that the above equation doesn't hold for this scheme.
The second (formally correct) approach is to find a counter-example. Note that counter-examples alway disprove theorems while they can never be used to prove them (this is how sciences like physics work).

Now consider the following message space $\mathcal M=\{(0,1),(1,1)\}$ with $\Pr[\mathcal M=m]=\frac{1}{2}$ (i.e. both messages are equally possible). For the next step observe that $$c_0\oplus c_1 = m_0\oplus k_0 \oplus \operatorname{rev}(k)\oplus m_1\oplus k_1 \oplus \operatorname{rev}(k)= m_0\oplus k_0 \oplus k_1 \oplus m_1\oplus k_1 \oplus k_0=m_0\oplus m_1$$ as was noted by Maarten in the comments. $m_0,m_1$ here denote the first and second bit of the message space and $c_0,c_1,k_0,k_1$ the respective cipher text and key bits.

Now observe that the first message always yields a $1$ when applying the above $\oplus$ and that the second one always yields $0$ when applying it. So you know that $$\Pr[\mathcal M=m|\mathcal C=c]\neq \frac{1}{2}=\Pr[\mathcal M=m]$$ and thus the scheme isn't perfectly secure. The first probability follows trivially from the fact that you can you know exactly which message was encrypted given a particular cipher text.


Why no swapping block in the last round of DES?

In "Applied Cryptography" — Chapter 12, , Bruce Schneier writes:

The final permutation is the inverse of the initial permutation and is described in Table 12.8. Note that the left and right halves are not exchanged after the last round of DES; instead the concatenated block $R$16$L$16 is used as the input to the final permutation. There’s nothing going on here; exchanging the halves and shifting around the permutation would yield exactly the same result.
This is so that the algorithm can be used to both encrypt and decrypt.


Homomorphic mapping between elliptic curve point and Zq

I think that you can use a bilinear pairing map for the function $F$. This map is defined from $G_1 \times G_2$ to $\mu_n$. This means that $F(x)=e(x,T)$ that $T \in G_2$.
The feature of this map is as:
$e(g^a,T^b)=e(g,T)^{ab}$
$e(g^bh^r,T)=e(g^b,T).e(h^r,T)=F(g^b).F(h^r)$
The amount of $\mu_n$  is in $F_{q^k}^*$. There is a map from $F_{q^k}$ to $F_q$ that is called Trace map. You can find more information about this map at "Pairing for beginners" book or http://www.m-hikari.com/ija/ija-2011/ija-21-24-2011/yadavIJA21-24-2011.pdf


What is total key space in transposition algorithms

Measuring the size of the key space in transposition algorithms is not important, because their security is far less than the size of the key space would suggest.  Therefore, any measure of effective key length will be misleading and will not give an accurate picture of the true security of the scheme.

In general the standard way to compute the effective key length of a cryptographic algorithm is as follows: we let $K$ denote the set of all possible keys for that algorithm; then the effective key length is $\lg |K|$, where $|K|$ denotes the size of the set $K$ and $\lg$ denotes the logarithm to base 2.


AES Algorithm processing time in Arduino vs Raspberry Pi

In principle, it is theoretically possible to calculate the time it takes a machine to run some known algorithm.
It used to be fairly commonplace, but there are apparently very few people who have ever done it -- the sorts of things that used to require isochronous code are now-a-days generally done in other ways.

In practice, it's generally simpler and takes less human effort to write the code and run it on the target machine and measure the time.
According to people on the Internet, some implementations of AES-256 that run directly on the 16 MHz Arduino can encrypt approximately 1 block per millisecond, roughly 32 000 bytes/sec.
(a) (b) (c) (d) (e) (f)

I hear that AES implementations are available on many other 8-bit processors.
AN953 "Data Encryption Routines for the PIC18" describes two AES implementations for a 10 MHz PIC. The "C" implementation decodes 3 400 bytes/sec; the assembly implementation decodes about 14 000 bytes/sec.
 (g) (h) (j)

I also hear that many people connect Arduinos to some other devices that does the AES encryption for them, such as some ZigBee and XBee radios with the "Enable AES 128 encryption" command.

Have you heard that Carl is doing AES+CTR+HMAC Encryption and Authentication on an Arduino ?


Is OCSP multi stapling supported by OpenSSL?

Still unsupported.
I think it still is not supported.
From openssl/blob/master/ssl/statem/extensions_srvr.c:
if (s->tlsext_status_type != TLSEXT_STATUSTYPE_ocsp) {
    /*
     * We don't know what to do with any other type so ignore it.
     */
    s->tlsext_status_type = TLSEXT_STATUSTYPE_nothing;
    return 1;
}

And from openssl/blob/master/doc/man3/SSL_CTX_set_tlsext_status_cb.pod

A client application may request that a server send back an OCSP status response (also known as OCSP stapling). ... Currently the only supported type is TLSEXT_STATUSTYPE_ocsp.


Why is Blakley secret sharing in finite space?

So why does Blakley use a finite space?

There are multiple reasons:

It is really inconvenient to use and represent infinite sets with computers, because the representation takes a potencially infinite amount of storage.
If you use floats or doubles for representation, then you also have to fight the problem of rounding errors, which are especially notorious in linear algebra when you are solving linear systems of equations, potentially preventing you from learning the accurate secret even if you have all the shares.
There is very few practical downsides to using finite spaces, especially as you can use finite fields of arbitrary size with exact precision rather easily.

However, I think that for theoretical / mathematical purposes the restriction to finite spaces is not needed though I haven't checked whether this fact is used in the security proof for perfect security somewhere.


How insecure is AES-128-CTR to encrypt any kind of data using the Ethereum keystore file format?

The worst purely cryptographic weakness is the password (1). The worst (and much worse) practical weaknesses are likely to be in the implementation (6) (7), and those (4) (5) that cryptographers dismiss as out of scope of encryption (the question's only stated objective).

Candidates for weaknesses, from cryptographic (but still to consider) to implementation:

The password: it is hard to remember a password with over about 48 bits of entropy (that's about equivalent to a 16-digit number, like 3141592653589793 or 2718281828459045, and more than envisioned by the obligatory XKCD). Using N=262144=218, r=1, p=8=23, buys at the very least 18+3+1=22 bits (see this) compared to a straight SHA-256 hash followed by AES-128, I guess about 32 bits stronger, thus the key might be about 80-bit good, which is not entirely unbreakable by brute force but still quite secure.
AES-128: this has a 128-bit key, no known purely cryptanalytic attack better than brute force, and is thus much better than the password.
CTR mode: with AES's 128-bit block, the only way key-stream reuse could kick in would be a bad random number generator for the IV (see 6)
The size of the plaintext can be effortlessly deduced from the size of the ciphertext. This is explicitly not a theoretical weakness of encryption, since length is excluded from what a cipher is supposed to hide about plaintext. However, that can be a practical weakness. Say analysis of ciphertext concludes that it is 17267095423 octets; and there exists, somewhere in the prosecution's exhibits a file with exactly that size, demonstrably predating search and seizure of the ciphertext, and which mere detention is illegal.
Lack of detection of (intentional or accidental) ciphertext alterations, corresponding to predictable alteration in the plaintext: again this is explicitly not a theoretical weakness of encryption, but can allow some attacks if the adversary can alter the ciphertext (example: if the plaintext is an executable or PDF with a known fraction, that can allow changing what the executable does to about anything, or make the PDF display as about anything). Authenticated encryption (AES-GCM..) solves that.
Random number generator: if this is bad, or worse gets more or less stuck (obligatory XKCD and Dilbert which turn to reality all too often), that would enable recovering plaintext in many scenarios, including repeatedly enciphering different English text or email addresses with the same password.
A side channel, that is broadly speaking unforeseen or unmitigated leak of information in the implementation or usage context. There are so many:

Password recovery from the password holder by exploiting a procedural goof (password on a postit note, master password list), rubber-hose cryptanalysis (obligatory XKCD), legal variants (involving use of expressions on the tune of contempt of court), bribery, chemical impregnation..
Password recovery by shoulder surfing, key logger (software or hardware), camera, microphone (a good audio capture of the sound of keys when entering a password leaks a lot of info about the password, especially when correlated with known keyboard entry by same operator under same conditions)..
Straight compromise of plaintext as shown on screen (with TEMPEST variants of that), printed, while transmitted to a printer or remotely accessed by a network, or just "temporarily" stored..
Straight compromise of the OS of the machine doing encryption or decryption (getting temporary root access is enough, means in 7.7 are game to the attacker).
Cryptanalytic side channel at a distance, including DPA and electromagnetic variant DEMA, and hypothetically timing if the machine doing the encryption/decryption is accessed by a network and does not use AES instructions.
Cryptanalytic side channel from a process running on the same hardware (including another VM), including cache-based targeting for AES when not using AES instructions, or more general ones (Meltdown, Spectre) which are all the rage these days.
Exploitation of various software bugs; that's huge.


Why can't I use ECB with some obfuscation for transient RAM?

The concept of encrypting blocks independently but based on the address is sound. It's commonly used in disk encryption.

In the simplest case you could use a tweakable blockcipher in an ECB like mode using the block index as tweak.

But let's say you want to use an existing block cipher, like AES. In that case you want to turn that block cipher into a tweakable block cipher. There are standard modes for doing this, in particular XTS. But they're more complex than your suggestion, applying a non trivial transformation both before and after encrypting with the block cipher. These transformations are keyed and necessary to eliminate patterns in the plaintext.

Simply xor-ing the address into the plaintext, like you suggest is not secure. If an attacker observes two identical ciphertext blocks, they learn that the xor of the corresponding plaintext blocks is equal to the xor of the address. Since they know the xor of the addresses, they learn the xor of the plaintext. In practice this could occur if two consecutive blocks of plaintext differ only by a single bit.


How long should a HMAC cryptographic key be?

Hashes and therefore HMAC do not take alphanumeric characters as input. You'd first have to convert the textual "key" into bits. I've put "key" in quotes because keys for HMAC should consist of bits in the first place.

The recommendation for HMAC is (indeed) that the key size is identical to the output size (and the intermediate state for Merkle–Damgård based hashes). Now lets presume that the characters in the key are completely random and that a large enough alphabet is used, say base 64. In that case you'd have 32 * 6 = 192 bits of randomness. That's larger than the required 160 bits of randomness.

If we'd use a single byte per character encoding such as ASCII or Windows-1252 then you'd get 32 bytes. This is much smaller than the ipad or opad used in HMAC. This means that additional hashing is not required before XOR'ing the key with ipad or opad. You would even be able to use UTF-16 as long as you don't use characters that require more than 2 bytes to encode. Anything longer than 64 bytes will require an additional hash calculation.

Below the security requirements for the key, taken from section 3 of RFC 2104:  HMAC: Keyed-Hashing for Message Authentication:

  The key for HMAC can be of any length (keys longer than B bytes are
     first hashed using H).  However, less than L bytes is strongly
     discouraged as it would decrease the security strength of the
     function.  Keys longer than L bytes are acceptable but the extra
     length would not significantly increase the function strength. (A
     longer key may be advisable if the randomness of the key is
     considered weak.)

  Keys need to be chosen at random (or using a cryptographically strong
     pseudo-random generator seeded with a random seed), and periodically
     refreshed.  (Current attacks do not indicate a specific recommended
     frequency for key changes as these attacks are practically
     infeasible.  However, periodic key refreshment is a fundamental
     security practice that helps against potential weaknesses of the
     function and keys, and limits the damage of an exposed key.)

Where H is of course the hash function, B the block size (64 bytes for SHA-1) and L the intermediate/output size (160 bits or 20 bytes).

Notes:

HMAC doesn't break in any terrible way if your key has somewhat less entropy; anything above 128 bits is probably OK.
Switching to SHA-256 is a good idea, even though it is not required to replace SHA-1 from a theoretical standpoint.


Proving Sigma Protocol on a Schnorr Protocol Variant

This Sigma protocol is basically a variant of the Schnorr knowledge of exponent protocol but with respect to two different generators. Therefore, also the proof is really similar to the classic one:

Completeness

This is kind of straightforward: $$g_1^{z_1}g_2^{z_2}=g_1^{r_1+ew_1}g_2^{r_2+ew_2}=g_1^{r_1}g_2^{r_2}g_1^{ew_1}g_2^{ew_2}=g_1^{r_1}g_2^{r_2}(g_1^{w_1}g_2^{w_2})^e =ah^e \mod q $$

Special soundness

Let's assume we have two accepting transcripts $(a,e,(z_1,z_2))$ and $(a,e^{'},(z^{'}_1,z^{'}_2))$. A knowledge extractor could extract the witness in the following way. We have that:

$$g_1^{z_1}g_2^{z_2} = ah^e$$ and $$g_1^{z_1^{'}}g_2^{z_2^{'}} = ah^{e^{'}}$$
Let's divide the two equations and we will get: $g_1^{z_1-z_1^{'}}g_2^{z_2-z_2^{'}} = h^{e-e^{'}}$, which yields: $$g_1^{\frac{z_1-z_1^{'}}{e-e^{'}}}g_2^{\frac{z_2-z_2^{'}}{e-e^{'}}} = h=g_1^{w_1}g_2^{w_2}$$.
Therefore the extractor has that $w_1=\frac{z_1-z_1^{'}}{e-e^{'}} \mod q$ and $w_2=\frac{z_2-z_2^{'}}{e-e^{'}} \mod q$ .

Honest-Verifier zero-knowledge (HVZK)

Let's build the simulator given a random $(z_1,z_2)$ and $e$. The first message message $a$ can be obtained by $a=h^{-e}g_1^{z_1}g_2^{z_2} \mod q$.
Clearly, $(a,e,(z_1,z_2))$ have the same distribution as in a real run. Namely, random values
satisfying $g_1^{z_1}g_2^{z_2} = ah^e$.


Yes, signing the ciphertext does provide extra security, and yes, that would be integrity and authenticity of the message.

Encrypting with a public key does not provide integrity / authenticity against active attacks. That's kind of obvious: an adversary can simply encrypt another message with the public key - it is public after all.

The scheme however uses asymmetric encrypt-then-sign. This is dangerous as an adversary could strip off the signature to replace it with its own. That way it looks like the adversary has signed / send the message. However, this is only possible if the public key of the adversary is trusted within the system. More details are (indeed) here.

It will also be impossible to verify the message afterwards (unless you keep the ciphertext message as well, and make sure that the plaintext message and ciphertext message are irreversibly linked).

So when used correctly this kind of scheme provides integrity / authenticity. But it also has known limitations; that is: known to the cryptographic community, not the authors.

These kind of papers are used by the writers to get their degrees or progress within their studies. They provide zero insight and contain clear issues:

no mode of operation is defined for the symmetric cipher, no IV handling is performed;
the padding modes of RSA are not specified, not for encryption nor for signature generation ... there is only a limited description of the textbook RSA operation;
the hashing is not thought of to be part of the signature generation function;
the use of SHA-1 and the references to MD5 and blowfish, years and years after SHA-2 has been standardized.

And quite obviously there is no security analysis at all, which makes the entire paper a waste of bits and - worse - time.

The given "protocol" (and the quotes are needed here) could easily be extended with a message nonce and sender/recipient, making it more secure.


How does hash speed vary based on string length?

Contrary to the other answer, I'll be assuming the hash function is of the password-oriented kind; and my answer will be: input size has almost no influence on speed in good practice, even for much longer input than in the question.

Password-oriented (or entropy-stretching, key-stretching) hash functions are, for example, suitable to transform a (password, salt) pair into a hash, with (salt, hash) then stored in a database, allowing later checking a (password, salt) pair by recomputing hash and comparing it against the one found in the database along salt, without allowing to directly extract password from a (salt, hash) pair.

Such hashes actually have three inputs: password, salt, and a workfactor which controls the effort required to compute the hash output. Said effort is parameterized to make testing a list of (say) the 10 million most common choices of password somewhat costly. For example, with a workfactor such that computing one hash requires 0.1s on the CPU normally used, the 10 million passwords are tested in 12 days with that CPU, hours with a server having many CPUs, perhaps a fraction of hour for a well-equipped adversary using ASICs or FPGAs (example publicly for sale). Choice of workfactor is a compromise between effort for legitimate use (translating into delay and power spent at each password use, capital investment for more powerful hardware); and security: the lower the effort to compute a hash, the cheaper it will be to find a common password from a leaked (salt, hash) pair.

An example of password-oriented hash is PBKDF2 with PRF an HMAC with (e.g.) SHA-256 as the hash, as standardized by NIST Special Publication 800-132. A safer one is Bcrypt. An arguably even safer one is Scrypt with HMAC−SHA-256, which can leverage multiple CPUs and ample RAM on the legitimate user's machine as a mean to dramatically raise the investment cost necessary for a parallel attack in a reasonable timeframe. The recent state of the art is captured by the results of the Password Hashing Competition.

For all these functions, a choice of the workfactor giving even minimal security, and password and salt inputs even orders of magnitude larger than in the question, the execution time overwhelmingly depends on workfactor; somewhat on code quality and CPU used; and very marginally on the size of password and salt (up to a limit of perhaps 1MB for each second of the execution time as controlled by workfactor). In a nutshell, that's because the password and salt inputs, when long (typically: more than about 64 bytes) are only processed once and reduced to something of fixed small size (using a hash such as SHA-1 or SHA-256), which is then repeatedly processed, with the repetition count controlled by workfactor.

Update: Maarten Bodewes pointed in comment that things might be different for the common PBKDF2 using HMAC-SHA-256 as the PRF. My analysis (below) is that timing dependency w.r.t. the size of the password won't happen for software implementations offering good security, but only for those sub-optimal from a security standpoint by a factor of about 2 or more.

The bulk of the execution time for PBKDF2 using HMAC-SHA-256 as the PRF is spent iterating $m_j=\operatorname{HMAC}(P,m_{j-1})$, where $P$ is the password input, and (with $H=\operatorname{SHA-256}$):
$$\operatorname{HMAC}(P,m)=\begin{cases}
H((P\oplus\text{opad})\|H((P\oplus\text{ipad})\|m))&\text{if }|P|\le64\text{ octets}\\
\operatorname{HMAC}(H(P),m)&\text{otherwise}
\end{cases}$$
where the $x\text{pad}$ are 64-octet constants, and the $P\oplus x\text{pad}$ are with $P$ right-padded with zeroes to 64 octets. When $|P|\le64$ and $|m|=32$, computing $\operatorname{HMAC}(P,m)$ involves 2 invocations of SHA-256 each with 96 octets of data, thus a total of 4 invocations of the round function of SHA-256.

A good implementation of PBKDF2 should maximize the security obtained for a given execution delay, thus should be speed-optimized. Therefore, a good implementation of PBKDF2 using HMAC-SHA-256 as the PRF should

replace $P$ with $\operatorname{SHA-256}(P)$ if $P$ is more than 64 octets;
pad $P$ to 64 octets by appending zeroes to the right and pre-compute $P\oplus\text{ipad}$ and $P\oplus\text{opad}$
apply the round function $R$ of $\operatorname{SHA-256}$ to these, obtaining the 32-octet $h_\text{in}=R(\text{IV},P\oplus\text{ipad})$ and $h_\text{out}=R(\text{IV},P\oplus\text{opad})$
in the core loop dominating the execution time, compute $m_j=R(h_\text{out},R(h_\text{in},\operatorname{pad}(m_{j-1})))$ using 2 invocations of $R$, and combine that $m_j$ by XOR into a separate 32-octet value.

Only steps (1) and (2) can have a timing dependency w.r.t. to $|P|$. All steps of PBKDF2 conceivably movable in the core loop 4 are shown.

If the implementation uses SHA-256 as a black box, but still performs (1) and (2) out of the core loop, it is bound to have 4 invocations of $R$ in the core loop, rather than 2. This is not best practice at least in software, because it lowers the protection against password search by a factor of about 2; but it does not introduce any dependency of the execution time of the core loop w.r.t. to $|P|$.

If the implementation moves (2) in the core loop, but not (1), it is likely that it will have some time dependency w.r.t. $|P|$ in the core loop (about linear, with some slope likely positive up to and including $64$ octets; then stable at the value obtained for $|P|=32$ afterwards). There will however be a fixed 4 invocations $R$ per core loop, and in any half-decent software implementation using a compiled language that will dominate the execution time, making the time dependency w.r.t. $|P|$ small.

If the implementation fails to perform (1) out of the core loop, then likely its core loop will exhibit a time dependency w.r.t. $|P|$, with a stiff steps at $|P|=65$ octets corresponding to going from 4 to 6 $R$, then steps about half as stiff at $|P|=120+k\cdot64$ octets for each additional $R$. That's a strong time dependency w.r.t. $|P|$, but only for implementations seriously inadequate from a security standpoint for the range of $|P|$ considered.

Hashes optimized for speed (like MD5, SHA-1, or SHA-256) should not be used alone for password storage and validation, because their very speed is a devastating weakness; worse, that weakness increases as time passes, for even nowadays Moore's law significantly speeds-up tasks which run well on parallel engines.


Why is H(message||secret_key) not vulnerable to length-extension attack?

How does the length extension attack against $H(k||m)$ work?

For Merkle-Damgård hashes, if you know $H(x)$ but not $x$ you can still choose an $e$ and then compute $H(x||p||e)$. With $x=k||m$ you can compute $H((k||m||p)||e)=H(k||(m||p||e))$ which is a valid authentication tag for $m||p||e$.

Why doesn't it work against $H(m||k)$?

With a length extension an attacker chooses the extension. The only non trivial way to make $H(m||k||e)$ a valid tag is if $e$ ends with $k$. Since the attacker doesn't know the secret key they can't put the key at the end of $e$ and thus can't produce a valid tag.

What should I be using?

Either use H(k||m) with a hash that's not vulnerable to length extension attacks, such SHA3. Or use HMAC with  an older hashfunction, such as SHA2. $H(m||k)$ is not ideal because it can be attacked by finding collisions of $H$. Collisions are one of the easier attacks crypto-analytically and require a hashfunction twice the width of the target security level. e.g. SHA-256 for a 128 bit security level.


No.
This doesn't work like this.
While, yes you can split a 64-bit key up into 8 8-bit blocks, you cannot confirm your sub-block individually. So you can only confirm the entire 64-bit key at once and only get a "yes" or "no" answer.

From this it follows that the maximal time to cracka 64-bit key is indeed $2^{64}$, where you first try all your guesss for the first byte, then all your guesses for the second byte for all your guesses for the first one and so on...


Even if we make RSASSA-PSS deterministic by fixing its seed, it remains with a security proof in the Random Oracle Model per Full Domain Hashing (Jean-Sébastien Coron, On the Exact Security of Full Domain Hashing, in proceedings of Crypto 2000). We can't say the same for RSASSA-PKCS1-v1_5, because a lot of the message representative is fixed.

In practice, a better argument to use deterministic RSASSA-PSS rather than RSASSA-PKCS1-v1_5 is that vulnerable implementations of verification of RSASSA-PKCS1-v1_5 abound, when I know no vulnerable implementation of RSASSA-PSS verification (regardless of randomization), and this is less likely to happen accidentally.

However a practical argument against RSASSA-PSS is that it requires careful specification of the hash and the mask generation function: even if the later is almost universally MGF1, that could be with another hash (e.g. stuck to SHA-1) depending on implementations.


Does limiting the sales market to U.S. only, releive my application of Export Admin Regs?

First, Crypto.SE is not a forum of attorneys, and is definitely not your attorney, and cannot provide legal advice.  So don't make your business decisions on the basis of queer pseudonymous feathery strangers on the internet!

That said, the Bureau of Industry and Security's current web site (archived 2017-11-03 because it changes all the time) claims that ‘open source encryption source code available for free online’ is not subject to the Export Administration Regulations once you send email to crypt@bis.doc.gov and enc@nsa.gov notifying them that you have published it per 15 C.F.R. §742.15(b)(2).

You should always publish your source code, and provide ways for users to verify that it is being used (e.g., let users build it from source, and if you provide a binary distribution, also provide the tools for reproducible builds), because sensible users will reject secret proprietary crypto algorithms and implementations that they cannot study and audit or ask their friends to study and audit.

(Say what you will about the insanity of US crypto export controls, the BIS rules provide additional incentive to do the right thing about publishing crypto source code by giving you mountains of bureaucratic paperwork if you don't.)


Crypto USB Devices - where is the PIN/Password stored?

It's impossible to say what the device really does; there are so many possible ways.

If you don't find any technical specification describing it, I would be wary of the actual security of the device.

If the device is FIPS 140 approved at any level, you can find back the FIPS certificate and the relevant security policy on this NIST web page.


Why does a non-prime DH modulus creates a "NOBUS" backdoor

[In the non-prime case] For the backdoor to work, the discrete log should be do-able in $p_i^{k_i-1}(p_i - 1)$

Actually, that's not quite correct, and that's relevant for the answer.

If the factorization of $p_i^{k_i-1}(p_i - 1)$ is $p_i^{k_i-1} q_1^a q_2^b ... q_n^z$, then for NOBUS to work, someone else shouldn't be able to find the factors $q_i$.

Here's why this distinction is important: in the prime case, everyone knows the size of the group $p-1$, and anyone can hand off that value to a factoring method that's good at finding small factors, such as Elliptic Curve Method.  That is an astoundingly good way for find small factors, and for ECM, small can be 128 bits...

So, if $p-1$ consists of factors that are small enough for us to use, ECM can find them without much difficulty.

However, if we use a composite modulus, the size of the group is now secret. In other words, we've shifted the problem to finding the $q_i$ values.  Here, ECM doesn't help us much; unlike the prime case, there isn't a convenient $p-1$ value we can hand to ECM.  And, by making the $p_1, p_2$ values comparatively large, ECM just doesn't work the modulus directly.

What would work (to some extent) is the $p-1$ factoring method.  There, we keep making guesses as to the various primes that make up $q_i$; if we guess all of them on one side (and there's no penalty, apart from wasting time, for incorrect guesses), then we factor.  So, if we have a 64 bit $q_i$ value (and assuming the attacker knows that), he can guess all 64 bit primes; however there's about $2^{58}$ of them, so it'll take a while...


Public key encryption algorithm for short messages

Using RSA with short keys is a bad idea since it would make the encryption less secure.

The standard way to use asymmetric encryption is to only use the asymmetric encryption algorithm to encrypt a symmetric encryption key and then use that key to do the actual communication. In this case you only get the message overhead of the asymmetric encryption scheme once which can then be amortized over many small messages.

Is there any reason you can not use this approach in your application?


Does data authenticity always, implicitly, provide data integrity?

There are varying definitions of authenticity and integrity, but generally speaking, no.

In a cryptographic sense, authenticity indicates that a message was endorsed by a particular principal. This principal may endorse multiple messages, and the same authentication tag can validate distinct messages. For example, having a (secure) MAC guarantees the authenticity of the message, but does not guarantee its integrity (see Why have hashes when you have MACs?). HMAC guarantees authenticity and integrity, but other MACs typically only guarantee authenticity: the authenticating party can forge other messages with the same MAC value.

In a data flow sense, authenticity guarantees the provenance of a message, but it does not distinguish between different messages from the same principal. A mere authenticity check does not protect against replay attacks: a message that was authentic in a previous run of the protocol is still authentic now, but integrity demands that the message that is received is the message that was sent as part of the same run. There are situations where integrity is harder to achieve than authenticity. For example, suppose I back up a file to a remote storage service. When I download the file, I can check that I am getting back a properly signed file, and if I include the file's name, I know that I am truly getting back a version of the file that I uploaded: the file is authentic. If I upload multiple versions of the file under the same name, integrity would guarantee that I download back the latest version; with a mere guarantee of authenticity, all I know is that I downloaded some version of that file.


Questions about length key of RSA 2048 bit

The binary base 64 encoded blob contains a modulus which is 257 bytes in size:

00D74A6BCF9FC5BC75FB731E5AA30885F9E3BCB90B8A4D8494D2B034C79C8D3C3E724C8D071A61014E78626B888E84ECF083405EBCE651D520A50690914D9562CA6D99FA88401ADEB9996ABED8B2E145FDCC36970CE93B66F085C5C5189547D8802E4F5C3EC5EEEB3CF8C7B453F6F646EEB135F8A6DE7929F581A72909EB9DB046020CEAE07A71FBF2135708B71CE9374A3969C194049FF1CA23FD3D5CCD45BBF12F6D72ABBB6C5AD1ECDEB17E3F4CD1DF1EF28C813AA62B86FDEE1662F1BD5436CB166B27420B8407FC2A1ADF957E92CAD3B9B3F2B9CD359192387083CDD5F10B37D0B59DEFDC4982969411269615E4B5EF1EA28ADF2E12332D3EA0469EA2EBCB

The first byte is set to 00 to indicate that it is a positive number. 256 bytes equals 2048 bits, which is the size of the modulus. The modulus in turn defines the key size of RSA.


What is the "standard model" for block ciphers?

In the standard model, the block cipher is modeled as a pseudorandom permutation (when using a random key). The adversary has oracle access to either the block cipher instantiated with a random key or a truly random permutation, and has to try to distinguish between them. In the ideal model, the block cipher is modeled as a family of truly random permutations; a different independent one for every different key. This is similar to the random oracle model, but even stronger (in some sense).

In what sense is it stronger? Well, it's stronger in the sense that there are functions that are random oracles but certainly not ideal ciphers. For one, a random oracle need not have the same domain and range. In addition, it can have collisions. In addition, they don't have two separate inputs (key and input). However, as an \emph{assumption} they are actually equivalent in that you can build an ideal cipher from a random oracle. This was proven (incorrectly initially, and then fixed). See the paper Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited for this.


Has a Two Key TDES encryption ever been successfully attacked?

If we talk about key search attacks (rather than key compromise or/and side-channel attacks), the answer must be no, for the best known method is impractical.

On the other hand there has been numerous successful key-recovery attacks against devices using TDES, including on some that try hard to avoid it. One example here, another there.


Digital signature for an expiring password

So, let's see if we can build something from the ideas in the question and the ones collected in the comments.
While the plain keys for asymmetric signature schemes need to be quite long (longer than normal humans can memorize), creating an asymmetric key pair from a password is doable [as pointed out by fgrieu in a comment]. Here is what Alice (or some program in her control) would do when first signing up:

Alice feeds the password and some other data, like her user ID (what Alice uses to login), system ID (an identifier for the server/system/...), system parameters, maybe some random salt from the user database, etc. as input to a key derivation function like PBKDF-2, bcrypt or scrypt, with suitable work factor so this takes as long as Alice is normally ready to wait whenever giving out a new authorization (this might be 10 seconds, for example), and obtain a 256-bit number $s$.

Alice uses this number $s$ as the seed to some (deterministic) cryptographically secure random number generator.

Alice uses the generator to generate a key pair. The exact procedure will depend on the algorithm in use - for RSA, Alice would generate two numbers $p$ and $q$, and check them for primeness (using more random numbers from the same generator) - if one of them turns out not to be prime, repeat. Then Alice creates their key pair from these in the normal way. (There are known standards for this, this is just a sketch.) For (EC)DSA or ElGamal, she just takes some random number $x$ from the generator, and calculates the public key $y = g^x$ in the group in use - nothing more to do.

She now gives the public key from this key pair to Bob (Bob is the "resource administrator" here.)
The private key will not be stored anywhere - whenever Alice needs it (e.g. to create a token), she will do this whole procedure again.

As all inputs are fixed and everything is deterministic, the key pair will only depend on the password (and Alice's user ID, so other users will have other key pairs).
How to create the token:
To generate a token, Alice takes all the necessary data together:

Alice's user ID
the ID $X$ of the resource which is to be accessed
Some form of the validity time (could be the current date in the simplest form)

Hash these together, and sign it with the private key (recreated from the password as above).
Now encode enough of the information mentioned before (the user ID could be enough) together with the signature in a token, and hand this token to Charles.
Charles takes the token, and shows it to Bob to access some resource $X$.
How to check the token:
Bob gets the token (and the resource ID $X$), extracts the user ID, and looks up the Alice's public key (and checks if she is actually permitted to access the resource, and to authorize such access to others).
Then Bob hashes together the user ID, the resource ID $X$ and the current date. Then he checks (with Alice's public key) if the signature is a valid signature for this message, and only then allows Charles access to $X$.
This scheme is extensible to other validity time spans - either encode the validity date into the token, too, or let Bob check the last some days as input.


Why NaCL does not provide anonymous public key cryptography?

As I now understand the question: why doesn't NaCL provide a primitive for unauthenticated encryption, making ciphertext blobs that are only decrypt-able by a receiver identified by their public key?  Note libsodium provides crypto_box_seal which does exactly this and NaCL claims to (try to) provide all necessary crypto primitives.

In answer, notice crypto_box_seal can be built using other primitives.  Sodium says of crypto_box_seal:

ephemeral_pk ‖ box( m, recipient_pk, ephemeral_sk
                  , nonce=blake2b(ephemeral_pk ‖ recipient_pk))

So what we have in terms of NaCL prims are (pseudo-code):

sk = random();
ephemeral_pk = crypto_box_keypair(sk);
nonce = sha512(ephemeral_pk || recipient_pk); // NaCL uses SHA512 not Blake2b.
ct = ephemeral_pk || crypto_box(m, recipient_pk, sk, nonce);

This can be considered anonymous because the ephemeral key pairs used are not associated with any identity - the secret key should be destroyed immediately after computing the ciphertext message, ct.


If you wanted to compute secp256k1 discrete logs, you would use Pollard's rho, except of course the cost is far beyond your budget so it won't do you any good anyway.

The number field sieve is applicable to finite fields and to elliptic curves that admit embeddings into relatively small finite fields.  Such elliptic curves are called pairing-friendly, and are not normally used for ordinary ECDH key agreement or ECDSA or EdDSA signatures like Bitcoin—secp256k1, for instance, does not admit such an embedding, so the NFS is inapplicable.
Pohlig–Hellman is used for groups of composite order: it speeds up the computation by doing it separately modulo each factor; you can then reassemble an answer with the Chinese remainder theorem.  Although some elliptic curve groups used for discrete-log-type key agreement or signatures like edwards25519 have composite order, they typically have one large >250-bit prime factor and a very small cofactor like 4 or 8.  Secp256k1 has prime order, so Pohlig–Hellman is inapplicable.
BSGS and Pollard's rho both cost $O(\sqrt n)$ operations where $n$ is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc.  However, BSGS also has $O(\sqrt n)$ memory cost, so the area*time cost—which is a proxy for euro or joule cost—is $O(n)$ even if we unrealistically assume $O(1)$ random access to memory.  In contrast, Pollard's rho costs $O(\sqrt n)$ time on a machine of constant space and thus $O(\sqrt n)$ area*time.  Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost.  There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains $O(\sqrt n)$.
If you knew the secret scalar were in a restricted range $[a,b]$, you could use Pollard's kangaroo, which costs $O(\sqrt{b - a})$ time on a machine of constant size.  The kangaroo method too can be parallelized without increasing overall cost.  If, say, $b - a \approx 2^{100}$ for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible.  But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.


Do I need to prepare plain text before encryption?

If you are using a modern, secure cipher, there is no reason whatsoever to perform such manipulations of the plaintext.

I'm not sure how to elaborate much more on the topic than that. The entire purpose of a cipher is to perform the exact types of confusion and diffusion you describe. Only, the approach that it will use has been designed, peer-reviewed, and cryptanalyzed by professional cryptographers. Your hypothetical algorithm has not.

At best case, it will do nothing to improve the security of your ciphertexts. At worst case, you can introduce bugs that unintentionally cause plaintexts to be unrecoverable from the ciphertext, or ones that accidentally reveal information about the plaintext (for instance, via a leak of timing information).


CPA-security of a pseudorandom permutation encryption scheme

You're close. As Mikero noted in the comments, this scheme is CCA-secure as proven in his book.

The proof strategy that seems easiest here is to do game-hops and with the IND$-CPA definition:

Start with the real case where $c=F_K(r\mathbin\|m)$ is returned
Swap out $F_K(\cdot)$ for a random permutation $\pi$, so $c=\pi(r\mathbin\|m)$ is returned, you "lose" the PRP advantage on your bound here
Swap out $\pi$ for a random function $f$ using the PRP-PRF-switching lemma, so $c=f(r\mathbin\|m)$ is returned, you lose the PRP-PRF bound here (additively)
Swap out $f$ for the function that instead drops its input and instead returns a fresh random value, you additively lose the probability you named because only if $r$'s (and $m$'s) repeat there's a chance that you can distinguish this from the previous game, $c\gets \{0,1\}^n$
Now you always return a random value as the ciphertext, independent of the input message, therefore it cannot convey any information about it, you're done

  Is that correct?

The basic idea is there, it just needs to be spelled out a bit more explicitly.


It sounds like a nice codebreaking puzzle, but little more than that.

If the encryption algorithm is known to the attacker, they can map each 5x5 binary grid to an arbitrarily chosen symbol (say, the number of distinct 5x5 grids seen in the message so far) and then solve it as a simple monoalphabetic substitution cipher e.g. using frequency analysis.
Note that this attack does not depend on the choice of the 5x5 pixel grid patterns in any way.  In practice, if the patterns are not chosen at random, the pattern chosen to represent each plaintext character might provide additional clues to the attacker.  But the generic attack described above works even if they don't.
(Using multiple grids per character and choosing between them at random would turn your scheme into a homophonic substitution cipher, which can be somewhat harder to break than simple substitution especially if the amount of available ciphertext is low.  But even homophonic substitution can be broken via statistical analysis if enough ciphertext is available, and even more easily if the attacker has access to at least some known plaintext.)

If the encryption method is not known to the attacker, it may take them some time and effort to figure out that the ciphertext should be converted to binary, laid out on (a multiple of) five lines and then each 5x5 grid of bits should be treated as one character.
However, assuming that the ciphertext is long enough to contain at least some repeated grids, the method you describe will leave statistical patterns that will be very obvious if the ciphertext is analyzed in binary (e.g. an unexpectedly low number of distinct groups and an unexpectedly high serial autocorrelation when the ciphertext is divided into 5-bit groups) and still apparent to some extent even if it's analyzed e.g. as 8-bit bytes (since e.g. the number of distinct 5-byte / 40-bit groups will still be lower than expected of a random byte sequence).
Also, assuming that the attacker doesn't know the encryption algorithm violates Kerckhoffs' principle, and is considered an unsafe assumption in modern cryptography, as it's hard to prevent such secrets from leaking (you've just leaked your algorithm by posting it here!) and even harder to restore the security of a system after a leak (since a completely new and unrelated algorithm would have to be devised, analyzed and communicated to all parties).  Instead, secure encryption schemes in the modern sense all feature a key of some kind, such that the system remains secure even if the attacker knows everything about it except the key, and such that the key can be easily changed if it's compromised.
While your scheme does have a "key" of sorts, in the choice of 5x5 bit grids to represent each character, this key does not offer much security since, as noted above, there are efficient generic attacks on monoalphabetic substitution ciphers (which yours effectively is, once the obfuscation layers are removed) that an attacker can use to find the key.  Thus, any additional security your cipher offers beyond that of a simple substitution cipher is based entirely on its non-keyed obfuscation elements, and would thus be considered worthless in a modern security analysis.


I don't have my copy of Katz & Lindell in front of me, but using the term "simulator" in the context of, say, an IND-CPA definition, is not exactly in line with standard usage in current literature. (But still an ok choice of words which is excusable for a textbook.)

Here's the breakdown of "game-based" vs. "simulation-based" definitions:

Both styles involve a fixed game played with an adversary.

Game-based:

Typically the game is specified as a 2-player interaction. I prefer using the names "adversary" and "challenger" as the names of the players. The game explicitly specifies a goal condition that the adversary is trying to achieve (like correctly guessing a particular piece of hidden information).

In this style of definition, we define security via a statement of the form: for all adversaries, the probability of the condition happening does not exceed some fixed threshold.

Simulation-based:

This style of definition is often called the "real-ideal paradigm," and it has its roots in the work of Goldreich-Micali-Wigderson's 1987 paper on secure multiparty computation.

In this style of definition, the adversary's goal is not explicitly defined. Instead, we define an additional, "idealized" game which often doesn't involve any cryptography. As an example, for a task such as encryption, the "real game" might involve honest parties sending encrypted messages (and the adversary gets to see the ciphertexts), while in the "ideal game" the honest parties might have a secure physical channel, where the adversary is told only that a message was sent (and so sees no ciphertext).

Then we define security via a statement of the form: for all adversaries, there exists a simulator, so that the "adversary in the real game" and "simulator in the ideal game" achieve the same effect. Achieving the same effect typically means that the joint distribution of adversary/simulator's outputs and the honest parties' outputs are indistinguishable.

The term "simulator" is reserved for "an adversary who attacks the idealized game." It's difficult to grasp at first, but think of it this way: (1) Any attack that can be done against the real game can also be done against the ideal game. (2) But the ideal game is really simple, often defined in terms of physical security assumptions in a way that makes it obvious you'd be happy with such a world.

So the main differences are: extra quantifier for the existence of a simulator, and no explicit goal defined for the adversary. The latter condition is important in contexts like secure computation, where there is a wide variety of ways of attacking a protocol, and it's hard to enumerate game-based conditions for each kind of thing that can go wrong. Or at least, it's hard to be sure you haven't missed any subtle thing that can go wrong.


EC Schnorr signature: multiple standard?

Adding to other answers, I note that both schemes are related to (but clearly different from) those standardized in ISO/IEC 14888-3:2016 (non-functional preview):

The BSI's EC-Schnorr original specification was similar to ISO/IEC 14888-3's EC-SDSA-opt, standing for Elliptic Curve Schnorr Digital Signature Algorithm optimized version, except that EC-Schnorr outputs $H(M\mathbin\|Q_x)$ but EC-SDSA-opt outputs $H(Q_x\mathbin\|M)$.
ISO/IEC 14888-3 also defines EC-SDSA which outputs $H(Q_x\mathbin\|Q_y\mathbin\|M)$.
The BSI's current specification now matches the definition of EC-SDSA in ISO/IEC 14888-3.
The question's libsecp256k1 (possibly matching this source) is similar to ISO/IEC 14888-3's EC-FSDSA (where the F stands for full), except that libsecp256k1 outputs (and later hashes) $Q_x$ where EC-FSDSA uses $Q_x\mathbin\|Q_y$. It follows that EC-FSDSA has a significantly larger signature than libsecp256k1 does (for $b$-bit security it is $6b$-bit, rather than $4b$-bit).

There are more variants related to libsecp256k1. A comment links to BIP-Schnorr.

Summary of the schemes discussed:
$$
\begin{array}{l|rllr}
\text{scheme}&\text{public}&\,\,\,\text{ first}&\,\,\text{ second}&\text{sign. }\,\\
&\text{key }\,\,&\text{component}&\text{component}&\text{size }\,\,\,\\
\hline
\text{[Sc91]}&-d\,G&H(Q,M)&k+d\;h&b+2b\\
\text{EC-SDSA}&-d\,G&H(Q_x\mathbin\|Q_y\mathbin\|M)&k+d\;h&2b+2b\\
\text{EC-SDSA-opt}&-d\,G&H(Q_x\mathbin\|M)&k+d\;h&2b+2b\\
\text{EC-FSDSA}&-d\,G&Q_x\mathbin\|Q_y&k+d\;H(Q_x\mathbin\|Q_y\mathbin\|M)&4b+2b\\
\text{EC-Schnorr old}&d\,G&H(M\mathbin\|Q_x)&k-d\;h&2b+2b\\
\text{libsecp256k1}&d\,G&Q_x&k-d\;H(Q_x\mathbin\|M)&2b+2b\\
\text{BIP-Schnorr}&d\,G&Q_x&k+d\;H(Q_x\mathbin\|\text{Pub}\mathbin\|M)&2b+2b\\
\end{array}
$$

$M$ is the message to be signed.
$G$ is the group generator.
$k$ is the secret drawn by the signer (randomly or pseudo-randomly) at each signature.
$Q=k\,G=\underbrace{G+\ldots+G}_{k\text{ terms}}$.
$Q_x$ (resp. $Q_y$) is the $x$ (resp. $y$) component of $Q$ as a bytestring.
$b$ is the intended security in bits; the group size $n$, $Q_x$ and $Q_y$ are about $2b$-bit.
$H$ is the hash function, and $h$ is the result of the hash, often also the signature's first component. For $\text{[Sc91]}$, $h$ is $b$-bit wide, and the input of $H$ combines an unspecified fraction of $Q$ with $M$. In other schemes, $h$ is  $2b$-bit wide.
$\text{Pub}$ is the public key. Including it in the hashed data simplifies (perhaps strengthens) security reduction in a multi-users configuration.
An implicit $\bmod n$ is omitted for the signature's second component.
Conversion between integer and bistring is omitted (though essential for interoperability).

$\text{[Sc91]}$ is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991; refer to this for an exposition and more bibliography.

In $\text{EC-Schnorr}$, the signature's first component is an ASN.1 integer rather than a bytestring.

$\text{EC-Schnorr}$ (resp. $\text{EC-SDSA}$, $\text{EC-SDSA-opt}$, $\text{EC-FSDSA}$ ) have registered Object IDentifier 0.4.0.127.0.7.1.1.4.3 (resp. 1.0.14888.3.0.11, 1.0.14888.3.0.13, 1.0.14888.3.0.12).

These 7 schemes are incompatible; Andrew S. Tanenbaum's "The nice thing about standards is that you have so many to choose from" is an understatement!

ETSI's Electronic Signatures and Infrastructures (ESI); Cryptographic Suites TS 119 312 V1.2.1 (2017-05) states:

  For interoperability reasons only one version (EC-SDSA-opt) from the EC-XDSA Schnorr variants defined in ISO/IEC 14888-3 is selected by the present document. EC-SDSA in the optimized version has the small advantage
  of minimal data transfer for smart cards.

but that rationale works only against EC-FSDSA as far as I can tell. If the Smart Card itself computes or verifies the signature, as it should, what's transferred is the signature, which is $4b$-bit in both EC-SDSA-opt and EC-SDSA.

Hashing $M$ first is a specificity of EC-Schnorr; my guess is that it was designed for constrained environments like Smart Cards, where it allows offloading the bulk of the hashing of $M$ externally (also, on a multicore CPU, that allows hashing $M$ in a separate thread). As long as the hash is secure, it should not make any difference in security.


How do two parties put together the AUTH data in the SKEME protocol?

how does $A$ know $g^y$ to include in the formula above?

Actually, what they mean here is, in fact, $g^y \bmod p$; that is, the value that $A$ received.  It wouldn't work to insert the literal values $g^x$ and $g^y$; apart from the fact that $A$ doesn't know the second one, there's also the practical difficulty that since $x$ and $y$ are (perhaps) 256 bit random values, the bit representation of $g^x$ and $g^y$ may consist of circa $2^{256}$ bits in length; rather too long to process.

In general, when the group we're working in is understood, we often write $g^y$, with the fact that we're talking about operations in the group, and not as an integer, being implied.


The first construction is a well-known PRF in the random oracle model, with security from DDH. I can't find a good reference right now where this construction is explicitly framed as a PRF, but I will update if I find it.

Edit: this is the PRF that is implicit in private set intersection protocols dating back to:
Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986
Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

The second construction is insecure. If I know $f_s(x)$, then I can raise this value to the $H_2(y)/H_2(x)$ power (inversion is mod $Q$) and this tells me $f_s(y)$. So I can easily distinguish $f_s(y)$ from random.
BTW, in the random oracle model, $f_s(x) = H(s,x)$ is a PRF, as is $f_s(x) = g^{H(s,x)}$.


There's nothing wrong with using CTR mode to encrypt files, or anything else, as long as you make sure to use every nonce value only once. (And add authentication, if malleability would be a problem.) You could, for example, rewrite the whole file encrypting it with a new random nonce every time it's modified.

Since you are assuming nonce reuse, an attack that used different versions of the file would indeed be simple. How feasible it is depends on how easy those previous versions are to get to, which depends on what sort of threats you envision. An attacker who does see multiple versions does not need NSA-level powers.

Example attacks:

An attacker who can read the encrypted file e.g. daily would be able to just wait until you modify it.
If there are backups or a versioning filesystem, an attacker could find previous versions there.
Access to the raw HDD image might make an attacker able to read previous versions from currently unused parts of the filesystem.

Etc. None of these is really that difficult, if the attacker has proper access.


Client side encryption / hashing of "person ID's" with password?

Because of the requirement that the secret be decryptable, it has to be encrypted, rather than simply hashed. Because of the requirement that a record be retrievable by the secret, it should be encrypted deterministically, so it can be reproduced. Finally, no keys or salts can be stored by the client, complicating the matter.

This suggests that the client should encrypt the secret person ID using e.g. AES-SIV, which requires no IV. The encryption key can be derived from a password and a constant salt (per client, rather than per record) which does not need to be secret or random (but can be for some extra protection against the server).

Possible key derivation functions include e.g. PBKDF2, bcrypt, scrypt or argon2. I would prefer the later ones, but any of them are acceptable if the password is good.

(Note that AES SIV used without a nonce, like any deterministic encryption, leaks the equality of person IDs (by design), so they should all be unique for this to work.)


As long as the key is secret, your list of MACs is safe and the numbers are not guessable.

You probably can truncate your MACs to 80 bits in order to save space, as collisions are highly unlikely for $2^{23}$ entries or so.

If your numbers do not repeat and fit into 128 bits, the simple Electronic Codebook (ECB) mode with AES should also do a good job, you just store the ciphertexts encrypted on the same key.


CCA-Security Proof of a particular scheme


DSA stands for "Digital Signature Algorithm" - and is specifically designed to produce digital signatures, not perform encryption.

The requirement for public/private keys in this system is for a slightly different purpose - whereas in RSA, a key is needed so anyone can encrypt, in DSA a key is needed so anyone can verify. In RSA, the private key allows decryption; in DSA, the private key allows signature creation.

The fact that RSA also can be used for signatures is a result of the textbook algorithm being a trapdoor permutation - in simple terms, this means the ciphertext and the plaintext are part of the same set space. It is not a requirement of a public key algorithm for this to be the case - public key algorithms just require trapdoor functions.


Serpent cipher : Osvik S-Boxes confusion and test vectors

To answer your questions in order:

You won't find test vectors for the s-boxes in the submission - the
s-box functions are implementation specific optimisations,
especially the bit-sliced s-box functions like the Osvik and Gladman/Simpson, which actually compute multiple s-box lookups in parallel.
If you need to test your s-box implementations, I would take the s-box functions from the implementation you're trying to replicate and generate test vectors yourself in isolation.
The difference in the s-boxes between the paper and the C source file is explained on the homepage of those two resources: "...Since then I have made further algorithm improvements, and results optimized for 3-way parallel execution are used in my implementation...".
It looks like Osvik did further searching and testing and came up with better (for x86/x64 architecture probably) s-box functions after publishing the initial functions.
I can't see anything obviously wrong with your approach, but I would recommend picking one of the implementations to compare to and generate some test vectors directly from the s-box functions to be certain.
This is the approach I was planning to use to integrate the Osvik s-box functions into a library that currently uses the Gladman/Simpson ones - I'm glad you pointed out the inconsistency in the paper/source.


Are really, really long passwords any more secure than short ones?

There is no AES-512; AES takes keys of 128, 192 or 256 bits.

When encrypting with a password, there are two steps: first the password is converted into a key for the symmetric encryption, then the encryption is applied. Brute force can be applied either on the password (enumerating all possible passwords until a match is found) or on the key itself (enumerating all possible keys until a match is found).

A 128-bit key is large enough to defeat brute force for long period of times. You can use a larger key for display purposes (larger figures impress managers, and some people apparently believe that key length correlates with manhood -- in the same way as big cars).

The same applies to a password with 128 bits of entropy -- which is a way of saying that there are 2128 possible passwords, and you chose one at random among them. You can lower the entropy requirements on the password by using a slow hashing process; roughly speaking, if the function which converts the password into a key has the cost of 220 elementary encryption operations (that's about one million, and will be done in a fraction of a second with a basic PC) then you can be content with 108 bits of password entropy.

If your passwords are random sequences of alphanumeric characters (uppercase letters, lowercase letters, digits), then 19 characters are enough (because you use 62 distinct signs, and 6219 is greater than 2108). More characters are useless. Note that "random" is an important word: I am certainly not talking about choosing the password with your head ! Human brains are definitely bad at randomness. Use a coin, dice, or a computer with /dev/urandom.

All of the above is about making sure that the message will not be decrypted within the next 10 years. A much harder problem is to also ensure that the message will be more or less easily decrypted in year 2022, but not before. I suggest entrusting the key to a notary, with instructions to reveal it at a specific future date.


What was the first MD5 collision ever constructed?

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required.

On the other hand, the most famous is probably described by Xiaoyun Wang and Hongbo Yu in their paper called "How to Break MD5 and Other Hash Functions" (PDF) (Advances in Cryptology – Lecture Notes in Computer Science 3494. pp. 19–35.) which was published somewhere around 2004/2005 and the spear-head of dozens of alike papers which successively described optimized and related collision-attacks.

When you check their paper, you’ll quickly notice (page 1) that they also reference Dobbertin, which is why I think he should at least be mentioned in this context. His contribution provided the base.

From the paper by Wang and Yu:


Prove that H(s) = G(!s) is a CPRNG if G(s) is one

A proof by contradiction seems most appropriate here.

Assume that $H$ is not cryptographically secure. This means it fails to provide at least one of the properties of a CSPRNG as defined in your class, textbook, whatever. Then you must show how you can use an attack on $H$ to attack the cryptographic security of $G$. To do this, note that $H(!s)=G(!!s)=G(s)$. Since $G$ is cryptographically secure, your assumption must be incorrect. Therefore, you can conclude that $H$ is in fact cryptographically secure.


How is a lattice defined?

A lattice $\mathcal L(B)$ is the set of all integer combinations of the basis $B = \{b_1, ..., b_n\}$ of $n$ linearly independent vectors. That is, lattice $\mathcal L(B)$ is defined as:
\begin{equation}
\mathcal L(B) = \{ B \cdot z \;: \; z \in \mathbb Z^n\}
\end{equation}

In cryptography, we are interested on integer lattices, i.e., those where $B \in \mathbb Z^{n\times n}$, and, specially, on $q$-ary lattices, which are the modular version of integer lattices.

  What's the most common operation performed on / with a lattice? (like
  doubling and adding in ECC)

As you see, elements in a lattice are simply vectors in the space where the matrix is defined. In the case of integer lattices, the space is $\mathbb Z^{n\times n}$, so elements of the lattice are just integers vectors. For this reason, lattice-based schemes usually operate with vectors and matrices, so the basic operations are the usual: vector/matrix addition, inner product, etc.

For the sake of illustration, the following is the main step during the encryption function of the CCA1-secure cryptosystem from Micciancio and Peikert [1]:
\begin{equation}
b^t = 2(s^t A_u \mod q) + e^t + (0, \operatorname{encode}(m))^t \mod 2q
\end{equation}

where $b$ is the ciphertext, $s$ and $e$ are random vectors and $A_u$ is the public key (or more accurately, derived from the public key). You can see that everything is very simple from the point of view of the actual operations that are performed: $b, s$, and $e$ are vectors, and $A_u$ is a matrix, and the operations performed are additions and multiplications. The only "special" part here is the encoding of the message from a bit-string to a lattice point.

[1] Micciancio, D., & Peikert, C. (2012). Trapdoors for lattices: Simpler, tighter, faster, smaller. In Advances in Cryptology–EUROCRYPT 2012 (pp. 700-718). Springer Berlin Heidelberg (PDF).


Well, that transform can be viewed as an unkeyed transform of the plaintext, followed by exclusive-or'ing the key.  It would also appear to have the same limitations as the usual key exclusive-or; how it works out depends on the details of the key:

If the key is as long as the plaintext, and is chosen at random, this is effectively a One Time Pad, with a same protections and drawbacks; it is perfectly secure such if you use a key once; however, if you ever use it again to encrypt a different message, it is possible (and usually: likely) that someone can recover both messages.
If the key is shorter than the plaintext, and when you run out of key, you start back at the beginning; well, you've got a variation on the Vigenère cipher, and it can be attacked in a similar manner.  The extra unkeyed transform you put on the plaintext may complicate a ciphertext-only attack a bit, but I wouldn't count on that slowing down a knowledgable attacker a great deal.
If you generate the key dynamically via a key stream generator, then you've effectively got a Stream Cipher; if the key stream is indistinguishable from random, then you're good; if not, well, there may be weaknesses.


Computational feasible to reverse MD5SUM?

Actually, to the best of our knowledge, it's computationally infeasible.

By the terminology what we use when we discuss cryptographical hash functions, you're not asking for a hash collision (which is "find two different messages that hash to the same value"), but instead you're asking for a hash preimage (which is "for this hash value, find a message that hashes to it").

While MD5 is known to be woefully inadequate when it comes to resistance to hash collisions, there is no known way to find hash preimages that is faster than brute force (that is, hash different message until you stumble across one that happens to hash to the target value).  This brute force approach with MD5 will take $O(2^{128})$ expected operations, and so it is computationally impractical.


Generating password from high entropy file

If I'm correct it would take an attacker ~10 years to go through the whole keyspace with a brute force attack. Would this be correct or am I missing something here

No

First let's consider simple fact: The more power you have the shorter attack will take. There is no such thing as "it would take attacker 10 years". Also, 10 years is very, very short compared to proper key, which is very far from measurement in life-times.

Also, you seem to imply that fact that attacker will have to try multiple files will make it hard. Imagine that I have botnet with 40 000 machines. I can assign one machine for each of your files. So it will just take me as long as it took you to decrypt it (if not better). I can then try most common choices of A and B which would me take maybe day if i'm unlucky (considering that your decryption takes you minute, which is massive amount of time for password-based encryption).

While when you had used password with just 6 characters, I would have somewhat harder time recovering those.

If you assume that attacker knows your file, your whole process is basically useless. There simply isn't enough entropy in A, B and file selection. If you assume attacker doesn't know your file then all you do is still useless, because you would be just as secure in getting first 256-bytes of that file (since you assume that this file is high-entropy, if it isn't consistently high-entropy then you simply hash that file and end in same thing).

Also, one advantage of using passwords is that user himself choose how secure he is. If he uses 4-character password, it will be broken. If he uses 20-character password then there is good chance it will never be broken. With your scheme everyone who doesn't have 20TB worth of storage for keys is limited to 4 characters of security (and with 20TB you won't be much better).

TL;DR: Use established best practices. With your scheme you are arguably worse than with md5.

Also speaking of your scheme, it seems to come from world of "security by obscurity". There is no point in using crc-16 to shorten your key. Scrypt returns high-entropy mixed key, which you can simply cut. But your scheme doesn't spread entropy trough your returned key (which is terrible - you can know part of key with part of file). Also, you use scrypt to convert key to key, which is something pointless, since your key generation will take longer with longer file. So long in fact that user will get bored. Just imagine 60bytes file with A=0, B=1. It will take one minute to get key. You would be far better with just scrypting hash of whole file (you would still be able to configure scrypt time to something reasonable).


Yes. This problem is roughly equivalent to LWE.

If you have an oracle to solve $LWE_{n, q, m, \sigma}$, then you can solve an instance $(A, b := As + e)$ of your problem just by sampling a Gaussian $e_1$ and add it to $b_1$, that is, defining $b' := b + (e_1, 0, 0, ..., 0)$.

Of course, $(A, b')$ is a legitimate instance of $LWE_{n, q, m, \sigma}$ and can be solved with the oracle.

On the other hand, if you have an oracle to your problem, then given an instance $(A, b := As + e)$ of $LWE_{n, q, m, \sigma}$, you can try values to $e_1$ in order to produce a new error vectors with a zero in the first entry.

For typical LWE instances, $q$ is polynomially big in $n$ and the Gaussian parameter $\sigma$ is $\alpha \cdot q$ for some $\alpha$ between zero and one. Therefore, the errors values are also polynomially big in $n$ (they are bounded by $k \cdot \sigma$ for some very small constant $k$ with probability exponentially close to 1).

If you do a loop through those possible values of $e_1$, always defining $b' := b - (e_1, 0, 0, ..., 0)$, at some point, you will subtract the correct value and produce a legitimate instance of your problem, which the oracle will then be able to solve.


IND-CPA security of mode of operation using triple AES with plaintext || IV+counter

Seems to me that if you just look at the first layer that uses K1 that you can already show that it is CPA secure. After all, if the IV is always unique then $M_n \| IV + n - 1$ is always unique in this scheme. So then the input to the $\text{AES}_{K_1}$ block cipher is also unique. This makes the scheme have the same properties as the key stream of Counter Mode, with $IV + n - 1$ is the counter.

So unless $K_1$ is reused within the scheme, the scheme must be secure - regardless of any other encryption operations.

Now one thing to notice with the above reasoning is that I've proved it to be secure given key $K_1$. If you expect it to have a security of the 3 keys together (e.g. 128 x 3 = 384 bits for AES-128) then you may need to read up on meet in the middle attacks. At most the security will be 256 bits - that is if we don't put any constraints on memory usage. That's a separate security issue than IND-CPA though.

Of course, when it comes to practicality, this is one of the worst schemes you can think of. The number of key bits and operations is tripled to achieve additional security of about two times specified. More importantly, you'd also need more encryption operations as the IV takes away message space from each message block. The ciphertext also expands with the same factor.


Ed25519 and hierarchical deterministic wallet

Small-subgroup attacks are not relevant to Ed25519: You never reveal $[n]P$ for attacker-controlled $P$ where $n$ is your secret scalar.  Clearing and setting high bits of the secret scalar to put the highest set bit in a fixed position is not relevant to Ed25519: It is important only for easy implementations of the Montgomery ladder in $x$-restricted scalar multiplication, which Ed25519 does not use.

The only reason to use the same secret scalar clamping as X25519 is to allow the use of the same secret key material and software both for X25519 and Ed25519, e.g. in XEdDSA, and generally for compatibility with existing software.

Of course, you can only clamp the original scalars, not the derived scalar, since standard clamping is not a homomorphism of the scalar ring $\mathbb Z/h\ell\mathbb Z$, where $\ell$ is the large prime order of the standard base point and $h$ is the small cofactor: if your master secret scalar is $s \in \mathbb Z/h\ell\mathbb Z$, and you have random function $H\colon \{0,1\}^T \to \mathbb Z/h\ell\mathbb Z$ mapping tweaks to scalars, there is no way for the holder of the public key $[\operatorname{clamp}(s)]P$ to compute $[\operatorname{clamp}(s\cdot H(t))]P$, while they can compute $[\operatorname{clamp}(s)\cdot\operatorname{clamp}(H(t))]P$.

If you're not restricted to compatibility with existing software, but you still want to make sure low-order base points can't cause trouble, you can use a nonstandard clamping scheme suggested by Ian Goldberg, George Kandianakis, Isis Lovecruft, and Henry de Valence.  Let $\alpha$ solve the CRT system
\begin{align*}
  \alpha &\equiv 1 \pmod \ell, \\
  \alpha &\equiv 0 \pmod h.
\end{align*}
Then for any scalar $s$, the action of $\alpha s$ on a point in the order-$\ell$ subgroup generated by the standard base point is the same as the action of $s$ since $\alpha s \equiv s \pmod \ell$, but $\alpha s$ annihilates any $h$-torsion points since $\alpha s \equiv 0 \pmod h$.  Since multiplication by $\alpha$ is a homomorphism of $\mathbb Z/h\ell\mathbb Z$ and fixes the action of $\mathbb Z/h\ell\mathbb Z$ on the subgroup generated by the standard base point, it doesn't matter whether you do it to the original scalars, the derived scalars, or both.  This technique does not put put the highest set bit in a fixed position, however, so it requires more careful handling in a scalar multiplication ladder.


passive corruption ?= Byzantine corruption in the UC framework?

Is passive corruption actually equivalent to Byzantine corruption?

The answer is clearly no, otherwise cryptographers wouldn't spend so much time on developing protocols for active security.

Let me add an example to assist explanation.
Consider that I can passively corrupt the webserver of CVS. I can steal their TLS/SSL certificate private keys in the CVS webserver's internal state.
Then, I make a man-in-the-middle attack to a specific client, and if I also control the network, I can mimic CVS website to this client and display wrong pharmacy records.

The man-in-the-middle attack you specify is an active attack. Yes, in real-life, an attacker that has the internal state of the webserver can get their TLS/SSL private key and then could cause all sort of trouble. But, the whole point of the passive model is that we assume that the attacker does not do this. The only thing they do is record plaintext messages/internal state of the parties they have corrupted.
Why do we make this assumption? To make our lives easier, of course. We have to start somewhere, so we start with a fairly simple adversary model. It does not assume a completely trusted third party, yet we can still develop secure protocols. That is a win. Whether that win translates into the real world is another question. There have been papers (I'm looking, I'll update when found) that use passively secure protocols and argue that this is okay since, because of the application, there are other mechanisms in place that will force parties to be honest.
So, if you are worried about active attackers you should use protocols that are secure against active attackers. Passively secure protocols will break royally if the adversary is actually active.


What is the correct test/s to do in asymmetric algorithms to test their security?

If you're looking to test the parameters for an RSA or ElGamal implementation, well, that's fairly straightforward (assuming you can look at the innards of the implementation, and ask "are these primes drawn from a random distribution, do you get the RSA padding right, are you secure against the relevant side channel attacks, etc).  You really do need to know your crypto, but it's not that hard.

On the other hand, if you've devised your own public key cryptosystem, well, that's much harder.  Actually, symmetric cryptosystems aren't that much easier; the 'avalanche' test that you alluded to is a very weak test; a cipher can easily pass that with flying colors, and still be very weak.

In both cases, the real test is 'can a clever individual who has access to the ciphertext, possibly some plaintext, and (in the case of public key cryptosystems) the public key find an attack'.  That's not an easy question to answer (or so you hope, if there is an easy answer, it's be 'yes, here's this attack').

With public key cryptosytems, the obvious place to start is the 'hard problem' they're based on; why precisely do we think it's hard.  For RSA, well, it's the "RSA problem" (typically, people say factoring, however that's not proven to be true); for ElGamal, it's the Diffie-Hellman problem.  In your case, you need to consider what problem makes it easy (with a public key) to perform in one direction, and hard (with a public key, but not the private) to perform in the other direction.

Issues with the hard problem aren't the only possible way a system can fail (consider RSA with no padding; the RSA problem remains hard, but we can find ways to break the system by taking advantage of the homomorphic properties of raw RSA); however it's the obvious place to start.


In GnuPG, what's the difference between --s2k-cipher-algo and --cipher-algo?

(1,2) You could use:

gpg2 --s2k-mode 3 --s2k-count 65011712 --s2k-digest-algo SHA512 --s2k-cipher-algo AES256 --symmetric /*file path*

According to The GNU Privacy Guard Manual, p. 71, we use --s2k-cipher-algo name when we want to apply symmetric encryption with a passphrase if --cipher-algo name or --personal-cipher-preferences string have not been set.  The default is AES128 for GnuPG 2.1 and higher.  The setup above is the strongest one available in the OpenPGP Proposed Standard (RFC 4880).

The result will look like this (but the salt will surely be different):

gpg2 --list-packets /*file path*
 gpg: AES256 encrypted data
 gpg: encrypted with 1 passphrase
 off=0 ctb=8c tag=3 hlen=2 plen=13
 :symkey enc packet: version 4, cipher 9, s2k 3, hash 10
    salt 406974B08EF1428B, count 65011712 (255)

(3)

Yes, there were two errors:  one hyphen was left out in front of symmetric.  It should be:

--symmetric

Secondly, after  --s2k-count 65011712 one should put the path to the file.  Those usually look something like this:

/home/me/Documents/myfile

Keep in mind what your goals are.  Perhaps you should focus on using a very strong passphrase:  long, truly random, using all possible characters.

So, in short, those pairs of commands you listed do the same things, but the s2k specifiers only apply to symmetric encryption with a passphrase (note that s2k specifiers have another function: in the encryption of the secret part of private keys in the private keyring).


What are the uses of arbitrary length output hashes (other than OAEP)?

Uses for SHAKE/XOF functions
Community wiki answer, please add and edit:

key derivation of any type

such as turning a 128-256 bit secret key into an ECC or RSA public/private key pair

deterministic secure uniform random number generation starting from a small seed

this might be used in fuzzing tools, simulations, etc. where you want a lot of random data for your experiment but you want it to be repeatable

stream ciphers

absorb the key and IV then output the key stream

authenticated encryption

such as the duplex construction

length-preserving data obfuscation or anonymization

One might hash all customer data from a production environment when being copied into a development environment. An XOF can presereve the data cardinality distribution as well as the data size distribution of the "real" production data for accurate testing and performance comparisons in non-production environments.

digital signatures

digital signatures such as EdDSA employ hash functions whose output must be a specific size, some of them "awkward" (e.g. Ed448 requires a 912-bit hash function). This can be easily accomplished with a XOF. (In fact, Ed448 uses SHAKE256.)


The problem 'given a group and the elements $g, g^x, g^y$, find $g^{xy}$' is known as the Diffie-Hellman problem (or, more precisely, the computational Diffie-Hellman problem).

As for how difficult it is, well, we typically work with groups where this is difficult (by design; we often need to assume that the DH problem is hard).

As for how it might be solved, well, in a finite field multiplicative group, the best way of solving it is to solve the discrete log problem; this is, given $g, g^x$, recover $x$ (and from there, you can compute $(g^y)^x = g^{xy}$.  If you are in a group where recovering $x$ (or $y$) directly is infeasible, then solving the DH problem (to the best of our knowledge) is also infeasible.


zero-knowledge proof of disjunctive statements (OR proofs)

You can use the CDS94-technique for that. Suppose you have two zero-knowledge proof systems $\sigma_1$ and $\sigma_2$, both of which consist of three messages: a commitment $com$, a (public-coin) challenge $ch$, and a response $r$. And suppose you want to prove the OR of both claims, meaning that you can generate a valid proof for (wlog.) $\sigma_1$ for any challenge even after generating the commitment, but in order to generate a valid proof for $\sigma_2$ you must get the challenge first and compute the commitment from there. So you have essentially one degree of freedom in the choice of $(ch_1, ch_2)$, i.e., one is fixed beforehand but you want to hide which one. The clue is to get a new challenge $ch'$ from the verifier and guarantee that $(ch_1, ch_2, ch')$ satisfies a suitable relation, for instance sum-to-zero. So the proof system for $\sigma_1$-OR-$\sigma_2$ looks like this:

preprocessing by the prover: compute $com_2, ch_2, rsp_2$ for a random $ch_2$
prover sends commitment: $com_1, com_2$
verifier sends challenge: $ch'$
prover computes $ch_1 \leftarrow ch' - ch_2$ and uses this to complete $\sigma_1$
prover sends response: $(ch_1, rsp_1), (ch_2, rsp_2)$
verifier verifies that $(com_1, ch_1, rsp_1)$ is valid, that $(com_2, ch_2, rsp_2)$ is valid, and that $ch_1 + ch_2 + ch' = 0$

You can use $\sum_i ch_i = ch'$ for OR-proofs consisting of any number of claims. However, in some cases you want to prove more specific facts such as "$t$ out of these $n$ claims are true". In this case, you want to use Shamir's secret sharing and exchange the sum-to-zero relation for a polynomial of degree $n+1-t$: this guarantees that all $n-t$ degrees of freedom for choosing $ch_i$ must be used up by the false claims.
The CDS-94 technique applies to any zero-knowledge proof system that follows this three-pass public coin structure. Schnorr's protocol for proving discrete logarithm knowledge is just one particular case of that structure.
CDS94: Cramer, Ronald, Ivan Damgård, and Berry Schoenmakers. "Proofs of partial knowledge and simplified design of witness hiding protocols." CRYPTO 1994.