Using AES-CTR to generate AES subkeys from a master key and nonce

If I understand correctly:

You have a 256-bit master key $K0$
Generate a random 128-bit value $N0$ and set the last bit to 0
Generate a 256-bit keystream $K1$ using $E_{K0}(N0)$ || $E_{K0}(N0 \oplus 1)$
Generate a random 96-bit value $N1$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $N0$ as associated data
Include $N0$ with the ciphertext

As you suggested, this should give a 127-bit effective nonce size for generation of the key $K1$, plus a 96-bit nonce size for the actual nonce, resulting in 16 byte ciphertext expansion, and minimal extra computation, but now with a $2^{-111.5}$ probability of a key/nonce pair reuse.

Because there are only $2^{127}$ possible keys, you may want to consider additional ciphertext expansion, and instead generate a 256-bit nonce $N0$, encrypting the whole thing with ECB or CBC to get $K1$.

Be aware, security proofs may include keeping the nonce $N0$ (effective state) of the PRNG secret, and here you are providing it as part of the ciphertext. I would do it like this:

You have a 256-bit master key $K0$
Generate a random 256-bit value $N0$
Generate 256-bit key $K1$ by hashing $N0$ with something like SHA-384
Generate a random 96-bit value $N1$ (optional)
Generate $S$ = $E_{K0}(N0)$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $S$ as associated data
Include $S$ with the ciphertext

Encryption only requires a single hash iteration beyond the initial scheme, in addition to the ciphertext expansion from $S$. Decryption of the message requires decryption of $S$ followed by hashing to recover $K1$. In this scenario a GCM nonce $N1$ is not required to be generated, since you are using a new 256-bit key with each message you can use a fixed nonce. You could also get $N1$ from the unused remainder of the hash output. The GCM key is also protected by encrypting the state of the PRNG, which is now a random input to a hash function.

It is probably not insecure to do it your way, I just do not feel good about exposing $N0$ directly. If the system RNG has some problem, exposure of $N0$ (or even $N1$) could give an attacker information they could use against you in some way. Dual-EC is a good example.


How does RSA public and private key structure look like?

Probably the most widely used standard for this is defined in PKCS#1 (available as RFC8017 as well as PDF from RSA Labs).

In apppendix A, the ASN.1 syntax for the keys is defined to be

RSAPublicKey ::= SEQUENCE {
             modulus           INTEGER,  -- n
             publicExponent    INTEGER   -- e
         }

for public keys. Usually DER is used as the ASN.1 encoding rule. And of course, implementing ASN.1 in all its generality is not particularly easy, but implementing this subfunctionality shouldn't be too hard.


Reducing the rounds to 8 would give you Salsa20/8, which is not just a fast PRNG operating at 1.88 cycles per byte on Core2Duo, but is still quite cryptographically secure with the best attack requiring approximately 2244 operations. Removing the final addition step would not be good though, as without that, it would be trivial to reverse the function and discover the key and counter given just a single block of known plaintext. You will not get all zero outputs by keeping the addition, so you should keep it.

You could cut the algorithm down to four rounds in order to roughly double the speed while completely sacrificing cryptographic security. Less than four rounds results in incomplete diffusion, leading to biased and non-uniform output. However, it will still be roughly twice as slow as the fastest dedicated non-cryptographic PRNG, XorShift128+ (an LFSR-based PRNG at 0.48 cycles per byte on Kaby Lake).


Background

Terminology

Injective : one-to-one
Surjective : onto
Bijective : one-to-one and onto.

Pigeonhole-Principle
The pigeonhole principle goes back to 1624. We can state it as; if there are $m$ pigeons and $n$ holes with $m>n$ then when the pigeons are placed into the holes, there is at least one box that has more than one pigeon.
We can look at the traditional example; 101 pigeons and 100 holes. Place each hole one pigeon, and you will get 1 pigeon not placed into a hole so one must put this pigeon into a hole that has already one pigeon. Therefore there is one hole more than one pigeon.
The pigeonhole principle doesn't state that each hole must be filled. It is possible that 101 pigeons are places into one hole (a big one). This still applies to the pigeonhole principle.
With a small note: although the pigeonhole principle is a very simple argument it forms the basis of the combinatorics.

Cryptographic Hash Functions (CHF): CHF maps arbitrary data into a small fixed hash space $$H:\{0,1\}^*\to \{0,1\}^\ell$$ where $\ell$ is the fixed output size and it is 256 for SHA256 and $\space{}^*$ is the kleene star and in short here it forms a set that includes empty string and all finite binary strings.
There are XOF hash functions (e.g. SHAKE of SHA3 series) that the output size is determined during the digest request. In any case, one can see that the input space is larger in practice!
There are 5 main properties we want from CHF's

Deterministic: the same message always results in the same hash value.
Effective: It must be quick to compute the hash value for any given message
Irreversible: it must be infeasible to find a message that produces the given hash value.
No easy collision:  finding two different messages with the same hash value must be it is infeasible.
Avalance: Any small change to a message should change the hash value randomly so that the new hash value appears uncorrelated with the old hash value.

The 3. and 4. have formal definitions that we consider on the security and the below definitions comes from Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance by P. Rogaway and T. Shrimpton.

preimage-resistance — for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $x$ such that $h(x') = y$ when given any $y$ for which a corresponding input is not known.
2nd-preimage resistance, weak-collision — it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given $x$, to find a 2nd-preimage $x' \neq x$ such that $h(x) = h(x')$.
collision resistance, strong-collision — it is computationally infeasible to find any two distinct inputs $x$, $x'$ which hash to the same output, i.e., such that $h(x) = h(x')$.

Collisions
With the pigeonhole principle there exist at least two input  $m_1$ and $m_2$, $m_1 \neq m_2$ such that $\operatorname{SHA256}(m_1) = \operatorname{SHA256}(m_2)$. This implies that collisions are inevitable!
The collision security is bounded by the birthday paradox and roughly for a hash function with $\ell$-bit output, it has $\mathcal{O}(2^{\ell/2})$ cost with 50% probability.
No Injective
Once you have a collision this implies that a function (SHA256 here) cannot be a bijective function, since is not injective. Therefore we cannot talk about an inverse.
Surjective?
Even we don't know that SHA256 is surjective. To see that SHA256 is surjective, one has to find or show that the $2^{256}$ outputs occur.
Finding out this is impossible, since, one at least must try $2^{256}$ distinct inputs and this is infeasible.
On the other hand, showing SHA256 is surjective is problematic since it will indicate that SHA256 is not secure!
If we model SHA256 as pseudo-random function as Meir Moar did and limit the input space equal to output space then a hash value doesn't occur with probability $(1-1/n)^n$ and that is $1/e$ when $n \to \infty$. This is also the portion of the output hash value is not occurs. For the modeled SHA256 this makes $~2^{254.56}$ has values empty.
However, the input space is not limited to 256-bit. In this case, the probability of being empty becomes smaller and smaller $(1/e)^\frac{input-space}{output-space}$. And for both cases, we are still don't know until we look for all values.
If reversible
Assume that SHA256 is reversible then this means that it doesn't have the pre-image security at all. Given the has value one can find the pre-image using the reversible. This is not simple news, you would have heard that immediately.
There is no proof that SHA256 has 256-bit preimage security, however, any attack that has less than 256-bit search will still require substantial work to achieve to break the pre-image resistance. All of the current attacks are on the reduced rounds.
A good example from history is this; MD5 has imminent collisions, however, it has still pre-image resistance ( the best non-brute-force pre-image attack is still slower than brute-force in practice). So, even any collision attack better than the generic collision attack ( the birthday attack), we don't expect that the pre-image resistance will be broken.

The cost of MD5 pre-image attack by 2009 by Yu Sasaki and Kazumaro Aoki.

This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5. The memory complexity of the attack is $2^{45} \cdot 11$ words.


If the plaintext contains the key used to encrypt the ciphertext, is the ciphertext easier to decrypt?

There aren't any known generic attacks against this setup to work on arbitrary ciphers. On the other hand, the standard notion of IND-CPA security does not imply security when encrypting your own key.

I don't know of any commonly used block or stream cipher which has trouble with this setup, but one could be created and might even exist.


Getting the same two hash values for carved files I found

It is quite practical to deliberately generate two different files with the same MD5 hash; if you were handed these files by someone else, it is possible that they did this.

However, MD5 will collide only if someone deliberately crafts the files to do so; if you modified the files somehow, then this is unlikely to happen.  Instead, it would be a strong indication that the two files are bitwise identical.


Why does the NIST CTR DRBG apparently output the internal state when no additional input is given?

Still, the new internal state starts with

  $E(K,V+1) || E(K,V+2) || ... $.

There is where you are incorrect; the CTR_DRBG_GENERATE function updates $V$ while it runs, and hence the new internal state is actually>

$E(K,V+n+1) || E(K,V+n+2) || ... $

(where the $V$ value is initial value of $V$ when generate is called, not when the update is called).

Because these are encryptions of blocks that are distinct from the blocks used to generate the random output, there is minimal leakage of the new state (well, someone looking at the random output could deduce what the new state is not; however that's not of much help to an attacker)


What does the probability subscript mean in Shannon's secrecy definition?

This is standard notation in information theory but it is redundant as given here, usually it is used as below.

For example
$P_M(m)$ would be used instead of $P_M(M=m)$ both of which refer to the random variable $M$ and the probability that it equals $m$.

$P_{M,X}(M=m,X=x)=P_{M,X}(m,x)$ would refer to a joint distribution in the same way.


Composing and Inverting Symmetric Encryption Keys

As block ciphers are invertible, and since XOR is too - the main operation on the key stream for many stream ciphers - the resulting encryption/decryption modes of operation are often invertible. For stream ciphers that create a key stream that is XOR'ed with the plaintext, it is even true that $E = E^{-1}$.

Some block cipher modes of operation however require padding. If padding is included in $E$ then then you cannot perform $E^{-1}(M)$, because the padding would likely fail or result in a wrongly sized plaintext.

ECB mode is invertible, but requires padding
CBC mode is invertible, but requires padding
CFB, OFB and CTR modes generate a key stream are therefore invertible, they do not require padding

Any authenticated cipher is of course not invertible as $E$ would include creation of the authentication tag, (and $E^{-1}$ includes the verification of an authentication tag that isn't there).

Usually a (block) cipher has the same security for $E$ as for $E^{-1}$. It would however be advisable to use the cipher as intended, or verify (somehow) that the security conditions hold.

As for the keys, that's an entirely different question. If you have two (possibly identical) encryption functions $E_1$ and $E_2$ then you could create an encryption function $E_3(K_3, M) = E_2(K_2, E_1(K_1, M))$ that uses the $K_3 = K_1 | K_2$ as key. I don't see why you couldn't combine that with the previous approach.

Obviously such a construction is not safe by definition; if $E_2 = E_1^{-1}$ and $K_2 = K_1$ then you would have created the identity function. The identity function is not secure. You should also know about meet-in-the-middle attacks. You may want to study the multiple ways that DES can be - and has been - combined in this regard.


The protocol you are trying to reinvent is called SRP.

Unless you have a compelling reason to believe that your protocol is secure, it should by default be assumed completely broken. Given that your protocol has seemingly no benefits over SRP, you should seriously consider going with something that has been designed and analyzed by cryptographers, has existing software implementations, and has been around for over a decade.

  We are working on a cloud based encrypted file system...

Then you really should have somebody on staff who deeply understands cryptography. Your authentication protocol has a few sign that it was designed by novices. I don't mean to be rude or offensive, but cryptography is incredibly hard to get right. Thomas Ptacek said it best: if you think the dangerous stuff is in the primitives like the AES core, and if you just stick to the glue you'll be safe, you're gonna have a bad time.

  4. s1 and k0 are appended to produce b0
  5. SHA512Managed uses b0 to produce the hash (h0)

Why is this not an HMAC?

  If all is good k0 is used to actually encrypt/decrypt the file system locally using AES-256.

What is the point of the authentication protocol, if a malicious client can simply opt not to bother sending $h_0$ to the server and attempt decryption anyway? If the sole purpose is to prevent accidental decryption with an incorrect key, then this is trivially solved by simply using an authenticated encryption mode. Which, really, you should be using anyway.

You've also walled yourself into a design that doesn't allow password changes without decrypting and re-encrypting everything. Instead, you could use a protocol where the client sends a password-protected secret key to the server. After authentication over something like SRP, the server sends a copy of the encrypted key back to the user. If they wish to change their password, they can simply re-encrypt and re-send the secret key.

Note: the above description is the general approach that I would try and look for in an existing protocol, and not a description of an existing, vetted protocol for this type of exchange.


Which symmetric cipher is best for studying?

First, it is important to learn the basics behind all symmetric ciphers. You can get this from Handbook of Applied Cryptography, see Chapter 7, especially 7.1, 7.2, 7.3. If you understand those three sections, you will be off on the right foot.

From there, I would suggest just diving right into AES. It isn't that terribly difficult (yes, there are easier ciphers, but the "market penetration" of AES is so great that it is worth the added effort). There should be some good videos online, plus look at this question, the comments, and answer.

From there, I recommend the book "The Design of Rijndael". It was written by the inventors of Rijndael and has some very useful information on why they designed pieces the way they did.

Finally, I recommend using this site as much as possible to help clarify things. If there is something you don't understand as you are learning all this, search on here to see if it has already been answered. Then, if not, ask a specific question on this site.


Oh boy. Snakeoil at its finest.

This question is about the encryption scheme "Blobby" presented on their site and the security claims surrounding it.

Inventing and selling completely new symmetric encryption? One of the best indicators for snakeoil.

The first notation they use is $10^{yM}$ which I didn't get, but just below is an example $10^{41485806}$, which seems obscene with the unit to of the previous number being "operations", which can be inferred from them stating a relative strength of $10^{38}$ for AES-128 which is roughly $2^{128}$.

It seems they use big numbers for the sake of using big numbers and impressing people. For all practical purposes nothing beyond 256-bit security matters unless you want to invest the entire energy of the sun for most of its lifespan into breaking it. Double that number if you want to go "sure" against quantum computers thanks to Grovers provenly optimal search algorithm.

If their claim is solid, would this be quantum resistant?

It could be that their scheme is quantum-resistant. Symmetric crypto is rather easy to get quantum-resistant. But we don't know until they actually publish a description and even then we might not know because people won't care enough to analyze this scheme.

I'd like to ask if you think it's even possible.

Yes, you can build multi-factor encryption and you can build it nicely out of standard cryptographic primitives.
Now for the actual question you are probably having: "Ok, this is all snakeoil they're trying to sell me and you're saying that we don't need this, so how would you do it in practice?"
Well turns out people already did look at this problem, i.e. how to combine something that you know (like a password) with something that you have (i.e. a pre-generated key, a key-file or a security token).
My favourite three examples for this are the softwares VeraCrypt, BestCrypt and KeePass, which all handle this in a different way.

VeraCrypt will essentially mix your keyfile(s) with your password using their funky custom hash function and then run this through standard password-based key derivation. A random salt from the ciphertext will still be used.
BestCrypt will hash each of your keyfiles individually and then sort the hashes and prepend the hashes to the salt before key derivation.
KeePass will hash your keyfile and concatenate it with your password before feeding that into the password-based key derivation. A random salt from the ciphertext will still be used.

Obviously you need both inputs in all three cases to mount a brute-force / dictionary attack. Also note that any attack that would allow you to recover the password-based key derivation input without actually doing the forward iteration would be considered a major publication-worthy break. And yes there are publications that show that for standard password-based encryptions the optimal strategy is to search the password space or guess a secret symmetric key, the best one of which is probably by Bellare, Ristenpart and Tessaro (Theorem 3.4).


Public Key Encryption for Message Confidentiality

The question's formula $\text{Dec}(k_i,\text{Enc}(K_i,p))=p$ is for both encryption and decryption.
Encryption is $p\mapsto\text{Enc}(K_i,p)=c$.
Decryption is $c\mapsto\text{Dec}(k_i,c)=p$.
Note that $\text{Dec}$ can be a true function, but $\text{Enc}$ likely has a hidden random argument. Otherwise encryption would be deterministic, and deterministic encryption is vulnerable to chosen-message attack, especially public key encryption. If a name on the public class roll is encrypted with deterministic public-key encryption (such as textbook RSA encryption), anyone can find the name from the ciphertext, simply by enciphering all names on the class roll and comparing with the ciphertext.

In a textbook RSA context, $\text{Enc}(K_i,\text{Dec}(k_i,c))=c$ would be equivalent to textbook RSA signature of message $c$ followed by textbook RSA signature verification. But it is using a confusing notation, that won't work in most other signature contexts (e.g. Schnorr signature, DSA, ECDSA, EdDSA).


Are multi move proof protocols still "sigma protocols"?

There is no technical reason while it couldn't - but the term $\Sigma$-protocol was specifically invented to mean three-round public-coin honest-verifier zero-knowledge proof system. Note that the very choice of the greek letter $\Sigma$ was made because it (kind of) picturally represents the interaction pattern in a three-move protocol (arguably, one could also kind of see a four move protocol in it :p).

Note that interaction is a big deal in cryptography: more rounds introduce more latency, and this is very often the main efficiency bottleneck in protocols (think of a protocol between London and Sao Paulo: a 30-round protocol would take 3 seconds counting solely the latency, and is doomed to take at least one full second unless the parties can send messages faster than light - this means that 1 second is here a strict physical efficiency lower bound, unlike communication and computation which we can always improve with more bandwidth or more processors). Hence it makes sense to distinguish, through a specific name, protocols which enjoy the very desirable feature of having only three rounds (which is the minimum we can hope for in the plain model, at least if we want honest-verifier zero-knowledge - of course, in the common reference string model or in the ROM, we can have non-interactive proofs, which are also a big deal in crypto).

For many-round generalizations of $\Sigma$-protocol, I'd recommend calling them by their natural name, public-coin HVZK proofs. Note that the form "commitment - challenge - response" is characteristic of public-coin proofs in general, not only of $\Sigma$-protocols.


Exploiting XOR one-time-pads with alphabet size that isn't a power of 2

Don't think about xor over an alphabet. Only think of it over a binary encoding of an alphabet. I see what you are saying, and what you are hinting at is why Vigenere Cipher is a bad idea in general (one time pad of length $\ell$ that you use over a message of length $k$ for $\ell < k$. However, there is no "meaningful" way of implementing xor with an alphabet that is not a power of 2 as it is defined in terms of bits. Therefore, if there is no binary encoding of your alphabet, then you cannot perform xor.

As for the unrelated question, we try to avoid modular addition because 1) it is slower and 2) it makes side channel attacks possible


It is security on a 0-10 scale that goes to 11.

The cost of cryptanalysis to break a cryptosystem with a 128-bit security level, like Ed25519, is out of reach for humanity already.  A higher security level like Ed448's doesn't have any actual meaning with current understanding of cryptanalytic attacks.  The only purpose it serves is to hedge against potential modest future advances in cryptanalysis—a radical advance like a cheap quantum computer would devastate Ed25519 and Ed448 alike, of course.

P.S.  I see you tagged this jwt and jwe.  JWT and JWE, and JOSE generally, provide a different sense of ‘spinal-tap grade’ security, which is that they are a parody of security.


How to calculate an IV when I have a shared private key?

Well, to start off with, IVs have different security properties than keys.  With keys (as you are well aware), you need to hide them from anyone in the middle; if someone did learn your keys, then he could read all your traffic.

IVs are not like this; instead, we don't mind if someone in the middle learns what the IV is; as long as he doesn't know the key, he still can't do anything with the encrypted traffic.  Because of this, one common practice is to have the encryptor select the IV, and then include it along in the encrypted message (generally immediately before the ciphertext).  This eliminates half your problem (how does the decryptor know which IV to use; he gets it out of the message); the attacker can see the IV as well, but (as above) we don't care about that.

So, the question comes down to "how does the encryptor select the IV"?  Well, the answer to depend comes down somewhat as to the mode you're using; the requirements for IVs differ depending on whether you're using CBC or CTR mode.

For CBC mode, the statement you list is mostly accurate (although I would write it as "You SHOULD use unique IV's everytime you encrypt, and they MUST be unpredictable"; there are known attacks against predictable IVs; I don't know if they apply to your scenario, but it's generally safer if we don't have to worry about them at all).  There are several ways do to this; a cryptographically secure PRNG (with good seeding) works.  Another thing that I've seen is you take a counter (say 0 for the first message, 1 for the second, etc), encrypt that (in ECB mode) with the same key you'll be encrypting the message in, and use that ciphertext as the IV.  This works because the ECB encryption of a counter is unpredictable to anyone who doesn't know the key.  Of course, if both ends of a bidirectional channel use this method, they need to either use different keys or make sure that their counter values won't overlap (e.g. one end could use only even values and the other only odd ones).
For CTR mode, the statement is less accurate; it would be more properly "You MUST always use unique IV's every time you encrypt; predictability is not a concern".   Because of this, it is common to use a counter as the IV; we get uniqueness (counters obviously never repeat within the lifetime of the key), and while it is predictable, we don't care about that here.  Now, there is one note: the uniqueness requirement doesn't just apply to the IV's, it also applies to the values you present to the block cipher.  Because of this, one common approach for CTR mode is to take the 16 byte AES plaintext block, and divide that up into (say) a 12 byte IV field and a 4 byte message index field; during the encryption of a single message, the IV field is always the IV value we are using to encrypt/decrypt the message, and the message index field increments for every block we encrypt; say, 0 for the first block, 1 for the second, etc.

Lastly, while you haven't specifically asked about this, I believe a heads-up is required; usually, when we encrypt a message, we generally need to use an integrity check as well (to make sure that the message received was the message sent); even if you don't particularly care about message integrity, there are several clever ways for an attacker to find things about about the encryption by modifying the cipher text, and seeing how the receiver reacts.  The short answer is that you should include some integrity transform (be it HMAC, CMAC, or replace the entire encryption operation with a primitive that does both privacy and integrity, say, GCM or OCB).  However, to fully discuss this requires more space than I should take up in the answer to a different question.


Can error correction and detection be done without adding extra bits?

In general, no. Let us say you have a data vector $x$ of $k$ bits and one bit is flipped by an error. There is no way of detecting, let alone correcting this, unless the errored data vector $x'$ is not another valid data vector.

If the errored vector $x'$ is not a valid data vector and you can do detection, then all $k$ bits cannot be used as arbitrary data bits, thus your data rate is less than $k$ bits, implying you are using parity in some sense.

More simply, if there are no parity bits, all $2^k$ data vectors are valid, and thus all errors result in another valid data vector, making all errors undetectable.

Since correction is harder than detection, the same argument rules out correction as well.You can't correct if you can't detect.


Acceptable condition for dictionary search

In a chosen plaintext attack, the expected ciphertext length required to conclude that a decryption is correct was derived by Claude Shannon and is called the unicity distance. It depends on the distributions of the plaintext and the key and is infinite for the one time pad.

So if $K$ is the random variable describing the key with a known distribution, and the message has $N$ symbols, say $(M_1,\ldots,M_N)$ with the message distribution known, let the encryption map be $$(C_1,\ldots,C_N)=E(M_1,\ldots,M_N;K).$$

Then the unicity distance is defined as
$$D:=\min\{ N: H(K|(C_1,\ldots,C_N))=0\},$$
where $H(\cdot|\cdot)$ is the conditional Shannon entropy.

See, e.g., wikipedia or van der Lubbe's Information Theory text.


Can a Message Authenticaty Code recover original data from corrupted data?

let's say that someone has used an XOR gate with one of the inputs as some random noise, the original data would get altered to some other data set. Is such a case possible if the authentication system is poorly designed?

If you change the message $m$ than the MAC will have a different value. Let see HMAC, fips-198-1;

$$MAC(m) = HMAC(K, m) = H((K_0 \oplus opad )|| H((K_0 \oplus ipad) || m))$$

Let say you modified even a single bit of $m$, now we have $m'$

Concentrate on this part; $H((K_0 \oplus ipad) || m'))$, and the $H$ is an approved Hash function, means that finding a collision is negligible. We assume that you have access to the keys$.

In any case, when you modify the message $m$ to $m'$ with x-oring, you have to find a collision, i.e;
$$H((K_0 \oplus ipad) || m'))=H((K_0 \oplus ipad) || m))$$

Finding collision is very hard, and if you find you will be very famous as in SHA-1, that still require $2^{63}$ calculations.

  And if it is possible, how would the system get back the original data?

If a message is changed and there is no a MAC failure, there is no way to turn back to old value, except file history etc in your operating system.

Even there is a MAC failure, you cannot turn back to the original data. MAC's are not Error Correction Codes.

In a better short wording from Maarten's Comment;

a MAC is there to make the message tamper evident rather than tamper proof


Why can't hashes be reversed with toffoli gates?

The question errs precisely at the point when it writes: $$\text{and so }H(x')=y.$$

Problem is: that holds for $x'$ matching some garbage $z'$, including $z'=z$, and perhaps other garbage $z'$, but we do not know which garbage (or $z$ unless we know $x$), and I see no reason that it holds for $x'$ obtained from any garbage $z'$ except for trivial $H$; and in the question $z'$ is random.

The only constructive process (as opposed to search) that I can think of to exhibit garbage $z'$ such that $H(x')=y$ is clause resolution or some improvement of that, well known to be exponential, as well as its sequential alternative.

Or otherwise said, my understanding of Toffoli-gate equivalent circuits (still limited, but improved in the process of making the present answer) is that they really are of the form $T(x,z)\mapsto(y,z)$ where it is easy to deduce $z$ from $x$ such that $H(x)=y$ holds, but not to deduce $z$ from $y$ such that $H(x)=y$ holds. Or, if we insist on the $T(x)\mapsto(y,z)$ notation, that is use $z$ built from inputs taken from $x$, we need $x$ to exhibit $z$.


Can a nested block cipher avoid the meet in the middle attack by using a secret initialization vector for the inner encryption?

Eli Biham examined this, along with a long series of other "internal chaining" modes in the paper "Cryptanalysis of Multiple Modes of Operation" in AsiaCrypt 1994.

His conclusion was that there were ways of attacking such modes that were strictly easier than the standard "external chaining" mode that is now commonly used; his paper is the chief reason that we stick to what we do use.

For example, in the case that you have CBC mode (with secret IV, as you suggested), followed by an independently keyed ECB mode, one way to attack this is to do a chosen ciphertext attack; ask for the decryption of the message (A B B) (where A and B are distinct blocks); if the plaintext message is (P1 P2 P3), then it turns out that $D_{k2}(A) \oplus D_{k2}(B) = P2 \oplus P3$; this makes brute forcing $k2$ straightforward (and once that is recovered, $k1$ can then be brute forced).

Other modes (I believe CBC mode followed by CBC mode would be one example) don't have such easy tricks; for them, you need to find an internal collision and exploit it.  One possible way to do it (for CBC mode followed by CBC mode) is as for the repeated decryptions of plaintexts of the form (A A A) (for various block-sizes values of A); if two different values A, B satisfy $A \oplus D_{k2}(A) = B \oplus D_{k2}(B)$, then the third word of the corresponding plaintexts will be the same.  Hence, if we ask for $2^{32}$ (assuming DES) such plaintexts, we can scan the plaintexts for collisions in the third word; once we find such collisions, we can do a brute force search to verify that the collision was caused at the $k2$ level, and if so, recover $k2$.

Now, it may be that these attacks are of mostly theoretical interest; they are often chosen ciphertext attacks, and chosen ciphertext attacks can be thwarted by a simple Message Authentication Code.  However, given that the standard modes don't have these theoretical weaknesses, people have found it safer just to stick with the now standard modes.


How does the McEliece asymmetric encryption work?

The intuition is really quite simple here. Assume you have a message of $k$ bits. You then use a specific mathematical operation to create a larger intermediate value of $n$ bits with $n>k$ such that it is not immediately obvious what the original message was and such that you can recover up to $t$ bit-errors using a specific algorithm. You then actually introduce $t$ random bit errors into your message to get your ciphertext.

Decryption is essentially reversing the above knowing the special values used to "obfuscate" the original message and the algorithm to remove the errors.

The idea behind the security of this scheme is that you cannot be sure for every bit that you are seeing whether it has been changed or not and through the "obfuscation" a wrong guess will yield essentially unrelated values when trying to invert the "obfuscation".

  why its quantum safe?

The entire reason is that we don't know how to (efficiently) break it if we had a quantum computer even though we have thought about this for more than 20 years.


AES: Guess Password using the unencrypted text?

Any good software should use PBKDF (a password based key derivation function) that uses a random salt. This salt is stored with the ciphertext and should be different for each ciphertext. As long as this is the case they key will be different for each ciphertext.

The best way an attacker can then attack your ciphertext (when stored on disk) is to iterate over the most likely passwords and perform the PBKDF. So the password and PBKDF together will provide the barrier that the attacker has to take. That is, if there are no other vulnerabilities to the crypto system, this is about the general case.

If you don't want to type a (different) password for each encrypt and if you want to use the same password each time, you might be better off using PGP encryption/decryption with a public / private key pair. PGP directly uses a public key for encryption and will request the same password each time to decrypt the private key, which decrypts the session key, which decrypts the data.


What would happen to AES if we replaced MixColumns with ShiftColumns?

If MixColumns is omitted, the following happens:

The cipher essentially becomes a group of 8-bit block ciphers, that work only by subkey addition and s-box transformation. After every 3 rounds, the original bytes will shift back to their original locations, in the following pattern:

Original state
a b c d
e f g h
i j l k
m n o p

After round 1
a g i o
f k n d
l m c e
p b h j

After round 2
a n l h
k e b o
c p i f
j g d m

After round 3
a b c d
e f g h
i j k l
m n o p

With AES-128, 10 rounds would equal a single round shift, and with AES-256, 14 rounds would equal a double round shift. An optimized version of the cipher would exist where only the final byte repositioning occurs, and the subkeys themselves get the shifts during the key schedule.

The entire cipher can then be re-described as 16 8-bit block ciphers, all with different key schedules that do not use every bit of key material for each round, and a final position change. The 8-bit ciphers will not be secure. Only a maximum of 16 times the data should be required to attack it compared to an 8-bit cipher, which recovers the entire code page for that key.

Key recovery is substantially more likely with a chosen plaintext attack due to the way the key schedule is broken up across each 8-bit group than would be with a pure 8-bit cipher, and the fact that you have 16 of them to work with.


How can I protect against the failure of a block or symmetric cipher?

Unintentional programming errors can be defeated by extensively checking your code against test vectors before releasing it (or better yet, create a self-test routine). Note that this doesn't protect against a malicious attacker circumventing your self-test and inserting his backdoor at runtime, obviously.

Of course, there aren't any test vectors for cipher combos, but you can always create your own by running reference code (presumably, by the cipher designers or some authority like NIST).

As for malicious crypto implementations, there really is no way to know without sifting through the implementation line by line and verifying that nothing that shouldn't be there is, like a socket call to some random IP in a crypto library would probably raise a few eyebrows.

And as for crypto hardware, I think this has come up before a few times - if you can't trust your hardware cryptographic provider, it's game over already. Of course, if you're into that kind of stuff, you could recover the firmware and study it and check it for malicious code, but in general it's more or less a black box that you have to trust.

Your question seems to relate more to the correctness of the implementation (i.e. "getting the right answer") than of how to detect backdoors in crypto code.

  Are some combination of ciphers better or worse than others?

When it comes to ensuring your code doesn't screw up and works fine, it doesn't matter, because of the all-or-nothing property of cryptographic primitives. It doesn't matter if your code screws up a single bit at the beginning, at the end, or at the middle - the result will be garbage in any case (or most of the time - if you are using keystream encryption this may not be true if your key schedule is correct).


Key material leak from initialized cipher?

Or in other words, is keeping initialized cipher in memory basically equal to keeping key in memory?

In the case of AES, yes, every time you encrypt (or decrypt) another block of data you need the key (or equivalent information, like the round keys), so the cipher instance must have it somewhere.

Other ciphers (like Keccak's AE mode) may allow encrypting more and more material without needing the actual key anymore. Even then knowing the cipher state would allow an attacker to at least decrypt later parts of the ciphertext, but not necessarily earlier parts.

  If so, what can be done to avoid this kind of leak?

If there is some kind of key store and encryption facility in the OS or hardware, that could make the attacker's life more difficult, as they might need root access rather than just a view of the process memory.

However, access to the running application could allow the attacker to call into that secure facility anyway, allowing them to break the encryption even if they do not get the key. So better if the attacker does not have access in the first place. I.e. avoid security bugs that would allow memory dumps or code execution. Easier said than done, of course.


AES S-Box Affine Mapping - how to do it?

Yes it is a normal matrix multiplication but within Galois finite field. We have to use Galois defined operations of  $+$ and $\cdot$. Example might clarify everything. Let's say we have the $b'$ vector, and it's value is $170 = 10101010b$ Just remember tat $b'_0$ is the least significant bit of that value.

$b_0 = (1 \wedge b'_0) \oplus (0 \wedge b'_1) \oplus (0 \wedge b'_2) \oplus (0 \wedge b'_3) \oplus (1 \wedge b'_4) \oplus (1 \wedge b'_5) \oplus (1 \wedge b'_6) \oplus (1 \wedge b'_7) \oplus (1) = (1 \wedge 0) \oplus (0 \wedge 1) \oplus (0 \wedge 0) \oplus (0 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1) = 0 \oplus 0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus (1) = 1 \oplus 1 \oplus (1) = 1$

$b_1 = (1 \wedge b'_0) \oplus (1 \wedge b'_1) \oplus (0 \wedge b'_2) \oplus (0 \wedge b'_3) \oplus (0 \wedge b'_4) \oplus (1 \wedge b'_5) \oplus (1 \wedge b'_6) \oplus (1 \wedge b'_7) \oplus (1) = (1 \wedge 0) \oplus (1 \wedge 1) \oplus (0 \wedge 0) \oplus (0 \wedge 1) \oplus (0 \wedge 0) \oplus (1 \wedge 1) \oplus (1 \wedge 0) \oplus (1 \wedge 1) \oplus (1) = 0 \oplus 1 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 0 \oplus 1 \oplus (1) = 1 \oplus 1 \oplus 1 \oplus (1) = 0$

$\vdots$

Just remember that here also $b_0$ is the least significant bit of the result.

Here's a little python from my experimental implementation for You:

result = 0;

inverse = RijndaelHelper.Inverse(value)

for i in range(8):
    row = (0xF1 << i | 0xF1 >> (8 - i))

    t = row & inverse;

    sum = 0;
    for j in range(8):
        sum ^= (t >> j) & 0x1;

    result |= sum << i;

result ^= 0x63;


How to encrypt a vector $e\in Z^{m}$ using LWE

I think you will not find any scheme that works over $Z$.

But, if you want to work over $Z_t$, you just have to choose a LWE-based encryption scheme that encrypts non-binary messages, and there is a lot of them!

For example, the paper ML Confidential uses one scheme  like that (non-binary messages) to perform classification algorithms over cipher texts.

The same occurs with this one: Using Homomorphic Encryption for Large Scale Statistical Analysis.

In general, the LWE schemes are presented considering only binary messages because the authors want to extend them to some Fully Homomorphic Encryption (FHE). Since the FHE is able to process functions described as boolean circuits, these schemes just worry about encrypt bits.

But usually, it's easy to change the schemes to work over $Z_t$ if you don't need a FHE, I mean, you don't need to do arbitrary sequences of multiplications and additions.

To do so, you just have to adjust the modules used by the schemes and be aware that you possibly will be able to do less operations than specified on the papers to the same set of parameters.


Require x of y possible passwords to decrypt

This is a well studied problem in cryptography; what you're looking for is known as a Secret Sharing Scheme.  This is a scheme where we take a master secret, and from that generate $N$ shares, and with any collection of $T$ shares, we can reconstruct the master secret (and we can't with $T-1$ of them).  We can make $N$ and $T$ as large as we like, and so it works in the "any 218 out of 435" case.

See this article for more details, as well as pointers to practical ways to implement it.


Are cryptographic hash functions quantum secure?

It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.

The point of a reduction is to gather the cryptanalytic effort on a smaller number of hypothesis. The fact that RSA-OAEP is CCA secure under the RSA assumption is not a proof that it is secure, simply an indication that to study its security, it suffices to study the security of the RSA problem. As many other cryptographic primitives can be reduced to the RSA assumption, it saves a considerable cryptanalytic effort.

Now, such reductions usually rely on some nice algebraic properties of mathematical hypothesis, exploiting group structure, self-randomizability, and so on. These properties are common in asymmetric cryptography, because such additional structure is already necessary in the primitives it involves. But in symmetric crypto, on the other hand, such structure is typically avoided. A consequence of that is that you need way smaller primitives (in terms of bit size) and much less computationally expensive operations to achieve a (conjectured) given security level, but you loose the possibility of reducing many symmetric primitives to a small number of hypothesis.

Still, for the most widely deployed block ciphers and hash functions, the cryptanalytic effort that has been invested on studying their security easily matches the effort invested on "generic hypothesis" such as the discrete logarithm or the factorisation, because they are widely used in practice. Therefore, there is no reason to believe that, due to the lack of reductions, inverting SHA256 should be any easier than breaking RSA. In fact, because RSA has so much structure, most experts would probably be way more surprised by an attack that inverts SHA256 than by an attack that breaks RSA. Therefore, the fact that ElGamal and the kind enjoy "reductions" does absolutely not make them more secure - it only establishes links between hardness of different primitives.

That being said, quantum computers are not magical. We cannot say anything for sure about what we can or what we cannot break with them - for all we know, it could be that $P=NP$, and that all of cryptography can be broken using a classical computer. But our current knowledge gives us some intuition on the additional power they give over classical computers. And this intuition can be summed up as follow: it seems to give some additional power, but to still fall short on solving very hard problems (say, NP-complete problems) in reasonable time.

Some problems with a special structure (factorization, discrete log) typically fall in the category of problem for which quantum computers would give a very strong speedup, because they can be reduced to the task of finding the period of some function, which seems hard to do with a classical computer, but not with a quantum one. For unstructured problems, quantum computers seem to provide some non-trivial quadratic speedup, via the use of the Grover algorithm. But a quadratic speedup does not give an attack, it simply indicates that the size of the keys should be increased by a factor two to compensate for this speedup.

Hash functions are rather unstructured, so we currently do not see how to get more than a quadratic speedup over a classical computer to attack one. Therefore, we currently conjecture that a hash function with 256 bits of classical security would still have 128 bits of quantum security. For collision resistance, quantum computers provide an even less impressive speedup: the birthday attack gives a $O(\sqrt{n})$ attack, and it's quantum version seems only to make this attack $O(n^{1/3})$.


Why does TLS do Authenticate-then-Encrypt instead of Encrypt-then-Authenticate?

SSL was designed long ago when encrypt-then-MAC wasn't that popular yet. Even TLS 1.2, published in 2008, is pretty old by now, and while encrypt-then-MAC was preferred by then, the practical risks were underestimated for a long time. Padding oracles attacks became well known after several high profile attacks in 2010.

With stream ciphers, MAC-then-encrypt is safe and easy to implement correctly. With CBC it's trickier, but technically the way it's used in TLS is provably secure if you ensure that the attacker doesn't learn anything about the cause of a detected manipulation (invalid padding vs incorrect MAC etc).

The choice of MAC-then-encrypt has lead to several weaknesses over the history of SSL and TLS, including POODLE and Lucky 13.

Lucky 13 was a timing attack, which gave an attacker information about why decryption failed, invalidating the proof.
POODLE was an attack against SSL 3.0 (and some careless TLS  implementations) which didn't have as strict padding validation requirements as newer versions of TLS.

In response to these attacks TLS implementations were carefully written to avoid side channel attacks, working around these weaknesses.

There is a draft TLS extension (Encrypt-then-MAC for TLS and DTLS
               draft-gutmann-tls-encrypt-then-mac) to use encrypt-then-MAC, but it didn't gain much traction and still hasn't been finalized.

TLS 1.3 will only support AEAD suites, where each suite is responsible for ensuring both confidentiality and authenticity, instead of combining MAC and encryption at the protocol level. So in TLS 1.3 this problem will finally be fixed.


SHA-1, SHA-224 and SHA-256 append  the  bit  “1”  to  the  end  of  the message, followed by k zero bits, where k is the smallest, non-negative solution to the equation l+1+k ≡ 448 mod 512, where l - message length. In second step they use 32-bit words.

SHA-384, SHA-512, SHA-512/224 and SHA-512/256 use different equation: l+1+k ≡ 896 mod 1024 and in 2. step use 64-bit words.

If you want to learn more, you should read Fips-180-4.


Is it secure to use order preserving encryption in practice?

Timely question, since attacks on the order preserving encryption in CryptDB were recently in the news. Quoting the research paper (pdf), there are two attacks they use on OPE:

sorting attack: is an attack that decrypts OPE-encrypted
columns. This folklore attack is very simple but, as we
show, very powerful in practice. It is applicable to columns
that are “dense”in the sense that every element of the message
space appears in the encrypted column. While this
may seem like a relatively strong assumption, we show
that it holds for many real-world datasets.
cumulative attack: is a new attack we introduce that decrypts
OPE-encrypted columns. This attack is applicable
even to low-density columns and also makes use of combinatorial
optimization techniques.

In practice they were able to decrypt fields with a relatively small range possible values with very high confidence.
The response from the developers was that:

OPE encryption should be used for “high-entropy values” where the order does not reveal much

I would not think there are many circumstances where that would be the case and yet both privacy and ordering (rather than e.g. deterministic encryption only) is needed, but there are probably some. E.g. some very exact timestamp might fit the bill in some circumstances, if finding the approximate value would not be a problem but the exact value would.
So practical applications where it is secure may be limited but they probably exist.


Append text to file without decrypting & encrypting again

There may be a relatively straightforward answer, depending on your requirements: could you use a multipart MIME message with separate MIME sections, one for each user's encrypted contents?

If you're looking instead for an asymmetric cryptosystem that supports appends, then maybe you can update your question to make that clear.


In EC with key chaining, is it possible to verify signature made by root private key using public key of derived keypair?

I think you're asking about what are called hierarchical signature schemes or blinded signature schemes.  There's a root private key $a$ and public key $A$, and for any tweak $t$, there is a derived private key $a_t = f(a, t)$, and a derived public key $A_t = F(A, t)$, such that signatures made with $a_t$ can be verified by $A_t$, but the set $\{A_t\}_t$ is supposed to be indistinguishable from $\{A'_t\}_t$ for any other $A'$ to anyone who doesn't know $A$.  See an earlier answer for some references.

I think you're further asking about whether there is an easy way to compute $A$ given $A_t$ and $t$, although you didn't mention $t$ so maybe there is only one possible derived key pair.  Whether you can do this depends on the specific signature scheme, so let's pick one for illustration:

Signatures.
$\newcommand{\Z}{\mathbb Z}\newcommand{\concat}{\mathop{\Vert}}$Let $k$ be the field $\Z/(2^{255} - 19)\Z$, and let $E/k$ be the twisted Edwards curve $$E/k\colon -x^2 + y^2 = 1 - (121665/121666) x^2 y^2,$$ whose group $E(k)$ of $k$-rational points has order $h\ell$ for large prime $\ell$ and cofactor $h = 8$.  A public key is a point $A \in E(k)$, and a signature on a message $m$ is an encoded pair $(R, s)$ of $R \in E(k)$ and a 253-bit integer $s$ satisfying the verification equation $$[h s] B = [h] R + [h H(R\concat A\concat m)]\,A,$$ where $B$ is the standard base point and $H$ is the standard hash function mapping long messages to 512-bit integers.

A signer chooses a secret 256-bit scalar $a$ (usually with $a \equiv 0 \pmod h$ and $2^{254} < a < 2^{255}$ so that it is compatible with X25519 secrets, but this is irrelevant to signature security) and a secret 256-bit string $\kappa$ as their private key, and publishes $A = [a]B$ as their public key.  To sign message $m$, they compute $r = H(\kappa\concat m)$, $R = [r]B$, and $$s \equiv r + H(R\concat A\concat m)\,a \pmod \ell.$$

Hierarchical signatures.
So far this is just standard Ed25519.  For a tweak $t$, we can let
\begin{align*}
  a_t &\equiv a H(A\concat t) \pmod \ell, \\
  A_t &= [H(A\concat t)] A.
\end{align*}
Note that $$A_t = [H(A\concat t)]([a]B) = [a H(A\concat t)]B = [a_t]B,$$ so that $A_t$ is the ordinary Ed25519 public key for the private key $a_t$.

Question.
In this hierarchical signature scheme, given $A_t$ and $t$ but not $A$, and given a signature $(R, s)$ on a message $m$ under key $A$, can we verify the signature?

Suppose $H(A\concat t)$ is coprime with $\ell$; then it has a multiplicative inverse, say $\xi$, modulo $\ell$, so that $$\xi H(A\concat t) \equiv 1 \pmod \ell.$$  If $A_t$ is a scalar multiple of the order-$\ell$ point $B$, then $$[\xi]A_t = [\xi]([H(A\concat t)]A) = [\xi H(A\concat t)]A = A.$$
Thus we can recover $A$ from $A_t$ and $t$, and use that to verify the signature $(R, s)$ on $m$.

Under uniform random choice of $H$, then probability that $\ell$ divides $H(A\concat t)$ is negligible; under the standard $H$ based on SHA-512, the overwhelming majority of outputs are not multiples of $\ell$.  If this bothers you on aesthetic grounds (the probability is so small it is inconsequential for security), you could use $H(A\concat t) \bmod 2^{252}$ instead of $H(A\concat t)$ in the above protocol.

Adapting this to other hierarchical signature schemes and other curves is left as an exercise for the reader.


Schnorr Ring Signatures - wrong hash results

If $g^a$ in the modular version translates to $aG$ or $a*G$ in the elliptic curve version, then $y_i^{-H(m, R_i)}$ should translate to
$$\begin{align*}
(-H(m, R_i))*Y_i&=-(H(m, R_i)*Y_i)&\text{(1)}&\text{ or equivalently}\\
&=H(m, R_i)*(-Y_i)&\text{(2)}&\text{ or equivalently}\\
&=((-H(m, R_i))\bmod n)*Y_i&\text{(3)}&\\
\end{align*}$$

The form (1) leads to an expression requiring one point subtraction or inversion:
$$R_s=a*G-\sum_{i\neq s}(H(m,R_i)*Y_i)$$

The form (3) leads to an expression that requires none:
$$R_s=a*G+\sum_{i\neq s}(((-H(m,R_i))\bmod n)*Y_i)$$

Note: By definition, $u\bmod n$ is the uniquely defined $v$ with $0\le v<n$ and $u-v$ a multiple of $n$. When $u\ge0$, $(-u)\bmod n$ can be computed as $n-1-r$, where $r$ is the remainder of the division of $(n-1+u)$ by $n$.


The way you should think of it is not as $(g^k \bmod p) \bmod q$ but as computing exponentiation by the integer $k$ of the order-$q$ element $g$ of the group $G = (\mathbb Z/p\mathbb Z)^\times$—which happens to be the multiplicative group of units modulo $p$ and to correspond to reducing the integer $g^k$ modulo $p$—and then randomly projecting that onto $\mathbb Z/q\mathbb Z$.  But for security it is sufficient to work with some more or less evenly distributed function from $G$ into the group $\mathbb Z/q\mathbb Z$ of exponents of $g$ (recall $g$ has order $q$), and the map $h \mapsto h \bmod q$ seems to work well enough as such a function.

In more detail:
The general form of (EC)DSA is the following structure:

Parameters:

Group $G$ in which discrete logs are hard.
Element $g \in G$ of large prime order $q$.
Random function $H\colon \{0,1\}^* \to \mathbb Z/q\mathbb Z$.
More or less evenly distributed function $F\colon G \to \mathbb Z/q\mathbb Z$.

Public key: Element $y \in G$.
Verification: A signature on a message $m$ is a pair of exponents $r, s \in \mathbb Z/q\mathbb Z$ satisfying the equation $$r = F(g^{H(m) \cdot s^{-1}} y^{r s^{-1}}).$$
Key generation: Pick uniform random $x \in \mathbb Z/q\mathbb Z$; public key is $y = g^x$.
Signing: Pick $k \in \mathbb Z/q\mathbb Z$ uniformly at random (reject $0$ and $1$ if you're a stick in the mud); compute $r = F(g^k)$ (reject $0$ if you're a stick in the mud) and $s = k^{-1} (H(m) + x r)$.

For DSA, we have $G = (\mathbb Z/p\mathbb Z)^\times$ and $F\colon h \mapsto h \bmod q$ (taking $h$ to be its least nonnegative residue modulo $p$).  For ECDSA, we replace the exponentiation $g^x$ for integer $g$ by the scalar multiplication $[x]B$ for curve point $B$, so we have $G = E(k)$, the $k$-rational points of some curve $E$ over a field $k$, and $F\colon P \mapsto x(P) \bmod q$.  And, as an additional tweak, in the signature for ECDSA we encode $x(P)$ instead of $F(P) = x(P) \bmod q$, because by Hasse's theorem $\#k \approx q$ (as long as the cofactor is small; for the curves typically used in ECDSA, it's usually 1), so unlike in finite-field DSA the additional reduction modulo $q$ for encoding the signature doesn't save much space.

If the choice of $F$ feels like it's all very arbitrary, you would be right.  (EC)DSA was a wacky bizarro design motivated mainly by a desire to avoid a patent-wielding Claus Schnorr in the early '90s, and nobody would care about this nonsense any more except (EC)DSA has now been carved into the stone of bureaucratic United States federal government standards standards that nobody in the Western world ever got fired for following.


How to securely encrypt/decrypt data with a maximum chunk size?

I have a solution that may satisfy you
Splitting the file into parts and chaining is a solution for you. To prevent the truncation we will use the associated data, that same for the first and last.
Assume that you divide the file into $n$ parts each around 16KB ( need adjustments). Encrypt each of them with $\operatorname{AES-GCM}$ with the following additions. Prefix each part before encryption as follows;
tag_0 = ''
borderFlag = random
for i from 1 to n
  if i == 1 or i == n
     #Third parameter is the Associated Data
     (C_i, tag_i) = AES-GCM(key, i:n || tag_i-1 || P_i, borderFlag)
  else
     (C_i, tag_i) = AES-GCM(key, i:n || tag_i-1 || P_i)

prefix each part with the part number as i:n
prefix each part except the first one with the authentication tag of the previous part.

With these, you have now a chain that can be controlled after decryption. You can detect, additions, deletions, and in the final part the truncation. The order is under your control, you can send even without the order. However, you need to check the prefix.
You can also

add the part size, and
add the time of encryption, too if you fear from the replay attack.


What is the purpose of adding secondary error to calculated key in BCNS and NewHope protocols

If $e''$ isn't there, then $v=bs'$ in both protocols, which means it would be easy to recover $s'$ given $v$ and $b$. Since $b$ is sent in the clear over the channel, and a (randomized) function of $v$ appears in the clear as $c$ (or $r$), without using $e''$ to hide $s'$, information about $s'$ would likely be leaked both to Alice and to any eavesdropper of the channel. Even if it wouldn't immediately leak all of $s'$, any leakage is clearly bad.

Somewhat related to this is the history of lattice signatures, which initially leaked "just a little bit" about the secret key, after which full breaks of these schemes were found. These schemes were only truly fixed once a way was found to make the output distribution completely independent of the secret key, so that nothing is leaked. In this case $e''$ is used to make sure that $v = bs' + e''$ is indistinguishable from random, i.e. the distribution of $v$ is independent of $s'$, assuming R-LWE is hard. See also the security proof in the BCNS paper, where Game 1 and Game 2 are assumed to be indistinguishable under the R-LWE assumption.


BIP 39: If I mix my 24 seed phrase with another 24 words, will the checksum property allow an attacker to retrieve the original seed phrase?

The proposed method requires 24 additional random BIP-39 words. The additional words together with the real 24-word passphrase are permutated in a word manner. The result has $2\cdot 10^{37}$ combinations that have $\approx 2^{124}$ bits of security. 8-word passphrase are already had more security than this $\approx 2^{139}$[1]
If a random permutation is used to scramble the words there is another problem with the bit size of the permutation that one has to store. If we consider that each of the 48 words can be represented with 8 bits then one needs $48\cdot 6 = 288$ bits to store. This is already larger than the bits size of the AES-256 that we hard to memorize it so we use BIP-39 or DiceWire to keep our keys secure depending on the length of the key 128 or 256.

I want to find a way to memorize a 24 word passphrase with the least effort possible and without using any encryption. So my suggestion was to just store 48 words in which the passphrase is hidden in a way I can remember. For example, I could just permute the words such that all the even positions recover my passphrase. For an attacker who doesn't know my system this would look like a random permutation. Can this attacker derive from these 48 words my passphrase?

Your least effort possible way to memorize is not unique to you. Actually, this means that you are using less entropy for your permutation. The attackers, by knowing or with a clever thought, will first try this least effort permutations as done in the least effort passwords like 1234.
I will not consider your example even possible position or others, the above paragraph should be enough ( how do you recover the order of the even permutations).
Your idea

Has less entropy than the 24-word passphrase 256 vs 124
An attacker can recover your weak permutations if you are the target and they know your system and you!
Humans are bad at random number generation [2] and you are shifting a secure system to your randomness that already shows the weakness.

If you already consider storing them consider using password managers so that you only need to store one really good BIP-39 or Dicewire and the rest of the passwords can be generated uniform randomly
.


This is off-topic, but arbitrary binary data can be read as image data using for example the Netpbm family of file formats. For example, here's how to read 10000 bytes of random data as a 100x100 grayscale image:

$ cat > image.pgm
    P2
    100 100 255
    ^C
    $ dd if=/dev/urandom of=image.raw bs=10000 count=1
1+0 records in
1+0 records out
10000 bytes transferred in 0.001229 secs (8136380 bytes/sec)
$ od -A n -t u1 image.raw >> image.pgm

You can then open image.pgm for example in Gimp.


Why does the SRP-6 calculation of B include a multiplier k = 3?

The purpose is to prevent a two-for-one guessing attack, where an active adversary, impersonating the server, can test two password guesses per attempt. The attack and why the multiplier prevents it is described in Section 2 of the SRP-6 paper (ps). (According to MacKenzie, it was discovered by Bleichenbacher.)

In brief, the attack goes like this:

Instead of $B = v + g^b = g^x + g^b$ with a random $b$, the attacker calculates $B = g^{x_1} + g^{x_2}$ with two password guesses.
The client uses the value $B - g^x$, meaning if $x=x_1$ they get $g^{x_2}$ and if $x=x_2$ they get $g^{x_1}$.
The attacker calculates two session keys, based on $x=x_1, b=x_2$ and $x=x_2, b=x_1$. If either of these matches with the $M_1$ sent by the client, they have found the password.

If the attacker does not know the discrete logarithm of $k$, i.e. the number $l$ for which $g^l = k$, they cannot try two guesses at once with the version 6 protocol where $v$ is multiplied by $k$.

The paper shows why $k=3$ is a safe choice for generic $g$ and $N$.

(The hashed $k$ fixes it for maliciously chosen $g$ and $N$ as well.)


Bit commitment with 1-out-of-2 oblivious transfer

It turned out that the protocol I designed was good.

Bob can't cheat because its impossible for him to discover $b$ because at every $\binom{1}{2}-OT$ iterations, Bob can only discover $b_i$ or $b_{i+1}$ for $i\geq1$ and $i=2k-1$ such that $1\leq k\leq\frac{n}{2}$ ($i$ is uneven).

Alice has an exponentially small chance to cheat without getting caught because if she would like to do so, Alice would have to lie on the reveal phase for every row for one of the $b_i$ or $b_{i+1}$, hoping that Bob discovered the other one. (She doesn't know which one Bob discovered). If Bob finds out that one of the bit isn't the one he discovered during the oblivious transfer or that one row doesn't equal the others, Bob rejects.


Can MFA codes be predicted if you know what their values were at a previous time?

[Is] it possible over time for the attacker to use this history of codes, along with the time they were used, to derive the original QR code I was given when I set up the MFA in the first place?

To answer this one needs to understand how TOTP (the standard in question works). Namely it essentially takes the current time 1 and the pre-shared secret from registration and feeds them into HMAC (usually HMAC-SHA1, but other hash algorithms are also supported) and then takes the returned byte string, converts it into an integer and essentially reduces it $\bmod 10^6+1$ (or however many digits you configured).

Now note that the weakest attacker goal is to predict whether you are generating these numbers at random for each time interval or are using TOTP (e.g. recovering the secret lets you do that). This is called PRF-security in cryptographic terms and luckily has been studied intensively for HMAC. The current best know security estimate for this is found in this paper. It states that one can only distinguish HMAC from a random function (Theorem 1) with probability $\varepsilon'=(2q+1)\varepsilon+q^2/2^c$ when doing $q$ queries (i.e. seeing $q$ different outputs) for a $c$-bit output. The $\varepsilon$ here is the security of the underlying compression function used by the hash function, which is usually assumed to satisfy PRF-security as well. Heuristically it can be assumed that $\varepsilon=q/2^c$ for a good hash function - which includes SHA1 and MD5 even to this day. Plugging things together we get $\varepsilon'\approx q^2/2^c$ and $c$ being 512 for SHA-1 this value is negligible for more than a human lifetime. Now this means that the intermediate TOTP output is indistinguishable from a random string for distinct outputs which means in turn that the codes are indistinguishable from random codes. This is what we wanted to show.

So you might be wondering what the hell all of the above means:

Distinguishing the MFA codes from a randomly chosen code is essentially impossible while the shared secret is unknown to an adversary (even knowing the input time).
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict any future or past unseen codes.
Because of the preceeding an adversary only seeing the codes (and knowing the time generating them) cannot predict the shared secret obtained through the QR code.

  Essentially, do I need to occasionally rotate my MFA accounts?

As explained above, no you don't.

1:Actually it takes the current time minus the unix epoch divided by the base interval duration, e.g. 30s.


Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?

The Berlekamp-Massey algorithm is an iterative method for finding the shortest LFSR that can generate
a given sequence of bits. The given sequence might or might not be generated by
an LFSR: the Berlekamp-Massey algorithm does not care. It just finds the shortest
LFSR that can generate the given sequence, and if the sequence has been generated
by an LFSR of length $n$, then the Berlekamp-Massey algorithm is guaranteed to find
this LFSR after examining no more than $2n$ bits of the sequence.  A simplistic
description of what happens is as follows.
After the algorithm has found the shortest LFSR that generates the first $k$ bits of the sequence, it examines the $(k+1)$-th bit of the
sequence. If this $(k+1)$-th bit of the
sequence matches the $(k+1)$-th bit of the output of the current LFSR, the
LFSR is accepted as the one that generates the first $k+1$ bits. If not, the LFSR is
updated so that the new, typically longer, LFSR generates the first $k+1$ bits.
As stated earlier, if
the sequence in question was in fact generated by an LFSR of length $n$, then
the Berlekamp-Massey algorithm is guaranteed to find this LFSR  by the time
it has examined $2n$ bits of the sequence.  How does the algorithm know that it
is done? Well, it doesn't, but after the correct LFSR has been found, the $(2n+1)$-th,
the $(2n+2)$-th, the $(2n+3)$-th, $\ldots$ bits of the given sequence match the
corresponding outputs of the LFSR and so the Berlekamp-Massey algorithm does
not update the $n$-bit LFSR it has found.

What does all this have to do with the question asked?  Well, the
(bit-by-bit XOR) sum of the
outputs of the various LFSRs is a sequence that is generated
by a longer LFSR (typically, the length of the longer LFSR is the sum of
the lengths of the LFSRs whose outputs were summed). So, the cryptographic
security is not significantly larger. What is needed is some way of
combining the constituent LFSR outputs so that the resulting sequence
has linear complexity much larger that the sum of the LFSR lengths.
The linear complexity of a sequence is defined as the length of the
shortest LFSR that can generate the sequence.
What we want is a sequence that has high linear complexity
but which can be generated easily
as a nonlinear function of the outputs of short LFSRs. The
legitimate users of the system can encipher and decipher
easily, but a cryptanalyst attempting to break the system
via a known plaintext attack has to either figure out
the nonlinear function (and the constituent LFSRs) which is
not easy to do or
attempt a Berlekamp-Massey algorithm attack which may fail
because not enough bits of the sequence can be determined
via a known plaintext attack to
find the shortest LFSR that generates the sequence.


Is suppose you choose to not consider online payment, credit card payment with euros, pounds, yens, etc(which include cryptography in their algorithms)...

In the 90's, there was a company called Digi-cash funded by David Chaum:
https://en.wikipedia.org/wiki/DigiCash
The goal was to provide anonymous transactions to users and was based on his previous academic work about e-cash
 The company doesn't exist any more, but it's the best example of "cryptocurrency" not based on the "blockchain protocol".


Secure password-authenticated key exchange that allows for passwords to be stored as hashes, but does not make the hashes password-equivalent

Are there any secure password-authenticated key exchange that allows
  for passwords to be stored as hashes, but does not make the hashes
  password-equivalent?

Yes, they are called augmented or asymmetric password-authenticated key exchanges (aPAKE). They generally build on the scenario that the user knows a password and the server may only store a "verifier" that should at most admit off-line brute-force search of the password and the key exchange should only succeed if the right password is match with the right verifier.

There are extensions to this approach which also consider cases where the user has a second device (e.g. a smart card or a phone) and a connection between his primary and secondary device, for an overview of the protocols, see here.

The most notable standard aPAKE is currently OPAQUE, which has already been announced to soon get an IRTF / CFRG draft and hopefully someday become an RFC, see this email thread.

The basic idea of OPAQUE goes as follows:

Upon registration the server generates a random key $k$ and two DH key-pairs and stores one of the private key as well as the random key and the two public keys in clear and computes $H(pw,H'(pw)^k)$ with the random key to get an encryption key which is used to perform an authenticated encryption over the complete second DH key and its own DH public key.
Upon a login request the client chooses its own DH public key as well as a random key which is used to exponentiate the inner hash of the of the password, ie $H(pw)$.
The server then retrieves the data stored on registration, generates a fresh DH keypair, exponentiates the received exponentiated hash with the stored $k$ and computes a key-exchange (HMQV is recommended) over its long-term secret DH key, its short-term DH secret key, the received short-term DH public key and the stored long-term DH public key.
The client undoes the exponentiation from 2. and evaluates $H(pw,X)$ on the result. This can e.g. be a memory-hard hash function taking the second input as the salt. It uses the resulting key to decrypt the stored ciphertext  and itself computes the key-exchange.


Is it possible to recover an AES encrypted file that was decrypted with incorrect key/password?

Note: This is answer version 2. I hastily answered the question incorrectly before.

It's not possible without brute forcing the IV. While encryption is reversible, encryption is generally one-to-many operation and decryption a many-to-one operation. This is because using the same key pair IV accross multiple messages can compromise security. For example if you send the same message twice then a one-to-one deterministic algorithm would leak the fact that you said the same thing twice. The part of the IV in any encryption algorithm that cannot be reused is called a "nonce" for number-used-only-once.

One way to generate distinct nonce values is to start with zero and increment by one every time you encrypt. If at some point you forget the counter you have to rekey. You could recover data in this case.

A random nonce is a memoryless way to prevent reuse. It needs to have enough entropy to prevent the same random value being generated twice. (Large enough to prevent birthday collisions.) This means a random IV is too long to brute force if you lose it.

However if you knew the IV and key, you could reverse CBC encryption. If it's deleted and unpredictable you cannot. CBC mode is deterministic and invertible for a given/known key/IV pair. It has the property $E_{K,IV}^{-1}(E_{K,IV}(M))$ = M (normal operation). Where $E$ is encryption and $E^{-1}$ is decryption. Additionally $E_{K,IV}(E_{K,IV}^{-1}(M)) = M$. It's not something you would normally do, but you could do it to recover the ciphertext file.

I assume you encrypted plaintext, deleted the original file, then wrote the ciphertext to disk. Then in the decryption process you encrypted with the wrong key, deleted the ciphertext (that included your IV), then wrote the wrong plaintext to disk. That process would mean you lost the IV because the random IV is only stored in the ciphertext file.

When you use encryption you should also use message authentication. You check if the MAC tag attached to a message is correct before trying to use decrypted data. Using authentication would have prevented your mistake.


On the fly key generation for cloud storage objects

Instead can't we generate object specific keys "on the fly" using HKDF using a master key and object id as inputs, so that we dont have overhead of storing and managing keys each time?

Sure you can. I've got an even easier method. Just use the same key for everything. No key derivation or key management needed. Or even better, don't encrypt anything. No keys, no management, much simpler.

My point is, there are no solutions, only tradeoffs. Your proposal has its benefits, but also has its disadvantages (assuming object ids are public, an attacker need only steal one small piece of information, the master key, and all objects are compromised as pointed out by Ricky).


You can turn any public-key encryption or signature system into an authentication protocol, and that includes both ElGamal encryption and the ElGamal signature scheme.

Protocols for this can be found in most textbooks. E.g. 10.3.3 in Handbook of Applied Cryptography.


What does Shor's algorithm tell us about the complexity class of RSA and the DLP?

That tells us those problems are in BQP.
This answer
describes a way of reducing factoring to SAT.
More elaborate approaches will give reductions from  RSA or ECC  to SAT.
On the other hand, if there is a polynomial-time reduction

from an NP-hard problem to  RSA or ECC   then    BQP ∩ UP ∩ coUP  =  NP  .


How can we authenticate a public key with limited secure side channel?

PGP supports a so-called fingerprint of the public key, which really is a 20-byte hash expressed in hexadecimal as 10 groups of 4 characters. The recommendation is to read it over the phone. That's doable, but seldom done.

In the context, we only need second-preimage resistance, thus 20 bytes are a bit overkill. With a slow password hash (scrypt, argon2) we can safely get this down to 5 groups of 5 characters in a 25-character alphabet 0123456789CFGHJKMPRTVWXZ+, for $5\cdot5\log_2(25)>116$ bit.
Note: that alphabet is likely to produce reasonably safe-to-spell-at-work codes, and is easily keyable if the software remaps Sto 5, Bto 8, ODQto 0, IJLto 1, UYto V, and so on)

With a challenge-response we can reduce this further. We can use a slow password hash using the (hash of) the public key as password and the challenge as salt.

please enter CK9Z 5H7C what do you get ?
got 01W8 RR4G

A substitution has probability $<2^{-37.1}$ (one in 150 thousand millions) of going undetected, which is perfectly fine in practice.


Assume the length is $n$. If the cipher text is $c_0, c_1, c_2, \ldots, c_N$ then consider the sub-text consisting of the characters $c_0, c_n, c_{2n},\ldots$. These have all been encrypted with the same Caesar, and you can break it by frequency analysis (the shifted 'e' should be the most common in standard English texts, or else maybe the 't' etc.). Suppose the shift you find is $s_0$. Then try the shifts $s_0 + 1, \ldots s_0 + (n-1)$ for the next sub-texts and see if you have a result. If not, try another $n$. This way you only brute force over $n$, essentially.

You could also determine the length $n$ by a statistical method (index of coincidence) or Kasiski (finding long repeats) as well. These will work for any Viginère cipher. But the above might be simpler if you already know that the shifts will be cyclic and consecutive.


How does the I2OSP primitive in RSA work?

Basically I2OSP is nothing more than a fixed size big endian representation of the integer, using a given number of bytes (or octets, same thing). The way that this is described in PKCS#1 is very technical, but this is what it comes down to. Big endian (or network order, same thing) numbers need to be left padded with zero bytes in case they are too small.

For RSA, the length given to I2OSP is nothing more than the modulus size in bytes. Usually this is just the modulus divided by 8 as most RSA key sizes can are multiples of 8. The standard however does define that the minimum number of bytes required for the unsigned representation of the number is to be used.

Obviously I2OSP would have to report an error if the integer doesn't fit. However, given that RSA calculations are performed modulus $n$, this can never happen.

Usually runtimes already have methods to encode a number (usually called a bignum or BigInteger or something similar) into big endian encoding. If only little endian is available you'll have to reverse the bytes in the array yourself before proceding.

After you're retrieved the big endian encoding you simply have to left-pad with zero's, and that's it.

You may have to strip a single zero byte from the output in case you only have a signed encoding available within your runtime.

What you do not want to do is perform the mathematical calculations yourself. What is described is nothing more than a binary representation of the number, and this binary representation is already present in one form or other in the memory of your runtime.


Block cipher not resistant to collisions

First since E is an encryption algorithm, it has a Decryption counterpart, lets name it D.

From the correcntess equation we get that $E(x,D(x,c)) = c$ for every $x$. Then we can easily see that if

$$y= x \oplus D(x,c)$$
then
$$f_2(x,y) = E(x, y \oplus x) = E(x, x \oplus D(x,c) \oplus x) = E(x,D(x,c)) = c$$

Again this holds for every $x$. So we have just shown that a collision exists for all pairs of the form $\langle x, x \oplus D(x,c) \rangle$


Apparently one can make the signature much shorter, by hashing the above again. Boneh and Shoup define Winternitz signatures in this way

No, Bohen and Shoup do not; their Winternitz signature is a concatination of the hashes.  This can be seen as the output of their $S(sk, m)$ algorithm on page 591 of version 0.5 of their book - the signature they generate is $(\sigma_1, ..., \sigma_n)$, that is, the concatination of the intermediate hashes $\sigma_1, ..., \sigma_n$
If you do generate a signature which is the hash of the intermediate hashes, it is not clear how the verification process is supposed to work.  The procedure that Boneh and Shoup propose (which is what LM-OTS does) starts with the intermediate hashes $\sigma_1, ..., \sigma_n$, and follow the hash chains upwards to the tops of the Winternitz chains $y_1, ..., y_n$.  It is not clear how one can rederive $y_1, ..., y_n$ given only $H(\sigma_1, ..., \sigma_n)$
Now, the public key they use is, in fact, the hash of all the tops of the chains $H( y_1, ..., y_n)$, and hence the public key is short.  LM-OTS also follows this.


How are blockchain keypair private keys hidden from miners, and how are they generated in the first place?

In blockchain systems, there are no clients and servers, just peer-to-peer nodes. They connect to each other using a TCP/IP connection, but are otherwise equal. Each node does not share its private or public keys with each other. These are kept locally in every node. The node can use their keys for two purposes, both of which are performed locally:

To sign a new transaction in order to make a payment. This signature is computed locally and then broadcast to the network. This does not reveal the private key, only the public key.
To check if a transaction it receives pertains to it. To do this, it checks to see if it matches its public key.

There is no further authentication taking place in the protocol. There are no user accounts, passwords, or any other form of "login".


Digital signature algorithms within the European Union

Except if you are picky with updates of references, there is such standard. DSA, RSA, ECDSA-$F_p$, ECDSA-$F_{2^n}$, are approved by ETSI TS 102 176-1 V2.1.1 (2011-07) (Electronic Signatures and Infrastructures (ESI); Algorithms and Parameters for Secure Electronic Signatures; Part 1: Hash functions and asymmetric algorithms), which essentially is an update of ETSI SR 002 176 V1.1.1 (2003-03) (Algorithms and Parameters for Secure Electronic Signatures), which is referenced by CWA 14169:2004 (Secure signature-creation devices “EAL 4+”), which (in an earlier edition that it supersedes) is referenced by Commission decision 2003/511/EC (on the publication of reference numbers of generally recognised standards for electronic signature products in accordance with Directive 1999/93/EC of the European Parliament and of the Council).

However, updates of both CWA 14169 and ETSI SR 002 176 have broken the formal chain of approval, with no official repairs that I am aware of. The state of things is that Member States have their own rules, AFAIK. For France, that is currently RGS 2.0 and its annex B.1 (both in french).


Weak and Strong Collision Resistance, again

There are many situations where collision resistance is exactly the property that you need. For example, assume that I want to get a certificate from a CA with the URL www.google.com so that I can play a fishing attack against Google. Assume that I manage to find two certificates with the same hash; one has URL that is www.google.com and the other has something else (e.g., www.yehudalindell.com). Then, the CA will happily sign on the certificate for the latter URL, and due to the collision I will now have a valid certificate for google. Another example is code signing: if I can construct two pieces of code where one is malicious and the other is perfectly valid but both have the same hash, then I can get my valid code accepted to Apple Store or something like that, but then get people to download my malicious code.

It is really important to understand that birthday attacks on hash functions are just the generic way of finding collisions when nothing better is known. However, advanced cryptanalysis can do amazing things and find really valid collisions. For example, using advanced techniques and MD5 collisions, a rogue certificate signing certificate was obtained. The Flame virus also propagated by using an MD5 collision. So, this is not there, but reality!

Weak collision resistance, or more exactly, target resistance or 2nd-preimage resistance is important when a collision must be found with a given hash. But this is often not the case.


Why does l'Ecuyer reject p-values close to 1?

So, what's wrong with a p-value close to 1?

Because random sequences don't look 'perfectly random' (or, rather, they have a low probability of doing so).  We're checking if this sequence quacks [1] like a perfectly random sequence; acting 'too uniform' is evidence that it is not.

[1]: from the proverb "if it acts like a duck, and it quacks like a duck, then it is a duck".  Fairly common where I am; however you never know how regional sayings like this are..


Can you distinguish encryption methods from the output?

Well, with standard protocols (TLS, SSH, IPsec), there really is a blatant unencrypted "I need to login from scratch, please!" message.  That's because when they first come up, they don't share keying material with the peer, and so they can't encrypt any messages.  Instead, they perform some sort of key exchange process using nonencrypted messages, and those messages are easily distinguishable.

Now, I suppose it would be possible to define a protocol where this initial message would be indistinguishable from an encrypted message.  However, the details would appear to be rather finicky (you'd have to worry about message timing and message length), and probably end up being expensive.  In addition, reboots are not actually instantaneous, and when you are rebooting, you obviously can't send out any messages.  I can't think of any scenario where the effort would be worth the cost.


How can one encrypt with RSA (or ElGamal) without revealing whom the ciphertext is intended for?

Your aim is to have a number $y' = y + rn$ that gives an uniform distribution over any valid key modulus $n'$, so that no keys can be ruled out. For that, you need $y'$ to be uniformly distributed modulo a larger number. How large is the question.

If you have uniform samples from $[0, 2^l-1]$, according to this (pdf, page 20 talking about key generation, but should apply here) they are uniform (enough) modulo $n < 2^k$ if $l = k + 64$. Hence, to have your $y'$ be uniform for keys up to $L$ bits you should draw $y'$ from $[0, 2^{L+64}-1]$.

Your approach gives even larger numbers ($2^{L+lg(n)} > 2^{L-lg(n)+64}$ with a realistic $n$), so that part's covered, but it may leak the minimum size of $n$, since if $r = 2^L$, no key with $n'<n$ could result in so high a number $y'$.

You should instead draw $r$ from $[0, 2^{L-lg(n)+64}-1]$, rounding the exponent so that $y'$ can reach $2^{L+64}-1$, then throw away those $r$ values that give you $y' > 2^{L+64}-1$.

(You could find a better upper bound for that random number generation, but generating uniform random numbers that aren't modulo a power of two is itself tricky. At worst you'll be throwing away half the $r$ values, so that should be easy enough.)


What is difference between an identification scheme and a digital signature scheme?

Huh, I was just reading about this.
Quoting [1]:

Identification schemes: A can prove to B that he is A, but B cannot
prove to someone
Signature schemes: A can prove to B that he is A, but
B cannot prove even to himself
The distinction between identification and signature schemes is
subtle, and manifests itself mainly when the proof is interactive and
the verifier later wants to prove its existence to a judge: In
identification schemes B can create a credible transcript of an
imaginary communication by carefully choosing both the questions and
the answers in the dialog, while in signature schemes only real
communication with A could generate a credible transcript. However, in
many commercial and military applications the main problem is to
detect forgeries in real time and to deny the service, access or
response that the forger wants. In these cases the transcript and
judge are irrelevant, and the two types of schemes can be used
interchangeably.

[1]: Fiat, A., & Shamir, A. (1986, August). How to prove yourself: Practical solutions to identification and signature problems. In Conference on the Theory and Application of Cryptographic Techniques (pp. 186-194). Springer, Berlin, Heidelberg.


difference between the math of RSA problem and DH problem

If you could take discrete logarithms modulo a composite number of unknown factorization, you could recover the decryption exponent.

Compute $c = m^e \bmod N$ for some $m < N$. We know that $c^d \equiv m \bmod N$.

You have $m, c, N$, and knowledge that $c^d \equiv m \bmod N$. Recovery of $d$ is the discrete logarithm problem.

The factorization of $N$ being unknown will probably work against you when attempting to compute the discrete logarithm. Depending on the hypothetical algorithm that you employ to compute discrete logarithms, knowledge of the factors of $N$ may be required, which implies that you still have to factor $N$ to compute the discrete log, which means breaking RSA would still be as hard as factoring.

Diffie-Hellman usually works with a prime modulus, so the factors of the modulus (which are just $1, P$) are public information.


Is Threefish the only cipher with 1024 bits of security?

If we are talking about symmetric encryption, the PAGES block cipher based on Speck support key size 1024 bits and PAGES+/PAGES— variants support key sizes up to 2048 bits. However, I have not seen any independent cryptanalysis of these, so I can't recommend them. If we talk about the ciphers which have some cryptanalysis available, the Kalyna block cipher supports up to 512-bit keys.


When the signal goes back through the rotors after the reflector, the permutation for each rotor is inverted. That's what you're missing.

In a way, this is kind of obvious: if going through the rotor one way would map, say, A to E, then going through it the other way has to map E to A, and so on.

(The permutation applied by the reflector itself is always, by design, its own inverse; it just swaps distinct pairs of letters.)


There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

   You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F_k'(0^n)$?

   Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F_k'(0^n)$?

From your last comment, I guess this isn't clear yet: The distinguisher can query the function for any kind of $x$, as often as he wants - with the limitation of being a polynomial time algorithm. And he has to find out whether the results he gets back are from a truly random function or from $F_k'(.)$, with just $k$ being drawn randomly. So the distinguisher can only do one thing: Choose $x$ in a clever way, so that some structure appears within one result or over several results, if it is $F_k'$ - and the random function does not have that.


How can I handle the situation if key size is less than 64 bits in DES?

A DES key is, by definition, a (pseudo)randomly chosen sequence of 8 × 7 = 56 key bits, plus 8 parity bits,* for a total of 64 bits.  If what you have isn't 64 bits long (with the appropriate parity bits), then it's not a DES key, but something else (e.g. a passphrase).

To turn that "something else" into a DES key, you need a key derivation function (KDF).  There are several standard and commonly used ones, most of them based on cryptographic hash functions.

If the "something else" you have might contain less than 56 bits of entropy (which is likely, if it's e.g. a user-chosen password), then you will most likely want a key stretching KDF such as PBKDF2.  Such KDFs are deliberately slow (and their slowness is adjustable) to make brute force guessing attacks harder.

Also, please note that the 56-bit key size of plain DES is itself too short to resist brute force attacks using modern hardware, making DES insecure.  If you can't use a more modern cipher like AES, you should at least use Triple DES, which doubles the effective key size of DES to 112 bits (at the cost of also tripling the work needed for encryption).

(Ps. Of course, the "something else" could also be a corrupted DES key.  In that case, you should just reject it, and report the error to the user who supplied the key.)

*) The standard way of storing a DES key is as a sequence of eight bytes, each consisting of 7 key bits and one redundant parity bit.  Thus, the standard form of the key has 64 bits, even though only 56 of them are actually used for cryptographic purposes.  This is a peculiarity of DES, not shared by most later block ciphers.


How do I know if a given curve requires a FpCurve F2mCurve or ECCCurve?

The EC objects implement general elliptic curve properties, whereas the other 2 operate on specific fields. Since secp256k1 is a prime field curve, you want the Fp objects. For binary field curves, you would use the F2m objects.

Note that NIST "K" curves are binary field curves, wheras secp256k1 is a "K" curve but over a prime field. Koblitz curves allow efficient mathematical operations.


The difference seems to be that cmacs are using a symmetric encryption additional to the hash-function while hmacs process the key within the hash-function itself. Is that correct?

There is no "normal" collision-resistant hash involved with CMAC. See below for details. For HMAC, the internals of the hash function are exploited to process the key, however it can use the hash function as a black box.

HMAC was standardized in RFC 2104 and NIST FIPS 198-1. The idea of HMAC is to exploit the common Merkle-Damgård structure of hash functions. This is done by first invoking the compression function with the pre-processed key, then using that state to process the message normally. Finally, the output of the previous step is used as a message again in the same manner as the original message was in the previous step, though this time with a different derived step.

CMAC is defined in NIST SP 800-38B which has a nice figure explaining the mode:

Where the $\oplus$ denote XOR, CIPH is a block cipher, the MSB operation is truncation, $K,K1,K2$ are keys derived from the main input key via doubling in a polynomial field.
The message is divided in blocks of at most CIPH's block size.

Are there some situations when a cmac shall rather be used than a hmac?

Yes, the typical recommendation is that if you either have hardware acceleration for a cipher or if you want to minimize code size and provide other functionality relying on a block cipher in your code.


Do I need to use AE/AEAD in my particular scenario? Or is it redundant?

In general signature creation contains the hashing part within the algorithm. A signature algorithm may also contain a padding mechanism such as PKCS#1 v1.5 or PSS for RSA. Finally it contains a one-way trap door function (modular exponentiation within RSA). Encryption has other requirements, and uses a different padding mechanism.

Basically you are encrypting a plaintext, and signing all the data including IV within the message. I don't see the need for either a MAC or an authenticated cipher; the signature is perfectly fine as authentication tag. That does not mean that your current scheme does not have weaknesses:

it does not provide forward secrecy (i.e. if your secret key is compromised, all the messages can be decrypted)
you have to keep both a private key and share a secret key
asymmetric operations are expensive (with regards to CPU) and you need a private and public key operation per message
no signer anonymity (eavesdroppers can prove that messages were sent by a specific sender)
as others have pointed out, encrypt-then-sign may have vulnerabilities you should be aware of in your protocol

Those drawbacks may be resolved by a careful choice of a TLS cipher suite (if you just require transport security).

Finally you may want to think about how you are going to setup key management.