Why does ROT13 provide no cryptographic security?

I think I understand what you're asking for.  You're trying to learn how we know which algorithm was used, so we know how to attack it.  That's a part of what is known as cryptanalysis, the task of breaking ciphers.

If you are using a standard computer protocol, the encryption algorithm is defined as a part of the protocol.  The computers can't talk unless both know what algorithm is in use.  No attempt is made to keep it secret.

Generally there are plenty of clues will tell you what's going on.  If things are flowing through port 443, the attacker is going to assume it's SSL protocol, look for the header which indicates what algorithms are in use, and begin there.

(If you're reading a joke or a movie plot on-line, ROT-13 has traditionally been used to keep you from accidentally seeing the punchline or spoiler until you're ready.  Thus, ROT-13 is actually a de facto standard.  Note that "standard" does not necessarily mean "secure".)

Even without knowledge of the protocol, though, there are usually other ways to figure out which algorithm was used.  The old school tool is frequency analysis.  The cryptanalyst (the guy whose job is to break the cryptography) might plot out the frequency of characters.  Normal English text follows a distribution such that the letter E appears 12% of the time, T appears 9%, A, O, I, and N appear about 8% each, and so on.  (The nonsense words ETAOIN SHRDLU represent the 12 most common letters in English in descending order.) If the distribution of letters in the ciphertext approximately follows this same distribution, the cryptanalyst can assume a transposition cipher was used to shuffle the plaintext letters.    If a different set of letters follows the same distribution, it's likely that a simple substitution cipher was used.  (ROT-13 follows this pattern, by the way, and can be spotted because the distribution will be RGNBVA FUEQYH.)

If the distribution is flatter, the cryptanalyst might try measuring the distribution for every other letter, or every third letter, or every fourth letter, etc.  If the distribution suddenly follows that same 12,9,8,8,8,8 curve, then the cryptanalyst has discovered that a Vigenere cipher or polyalphabetic cipher might have been used.

Once the algorithm is known, the next task is finding the key.  Frequency analysis can help with the simpler codes, but with the advent of computers a different attack becomes possible.  A computer can quickly try every possible key, which is called a brute-force attack.  The number of keys you would have to try is called the keyspace.  The classical Caesar cipher is a rotation cipher with a key of 3 (shift every letter to the left by 3 places.)  The keyspace of a Caesar cipher is $26^1 - 1$ (there are 26 possible shifts, but cleartext is not considered encrypted), or just 25.  Because these increase exponentially with the number of possible keys, and because brute-forcing is generally done with computers, it's common to refer to these with power of 2 exponent notation. The keysize is generally referred to by the number of bits.  The next power of 2 greater than or equal to 25 is 32, ($32 = 2^5$), so we can say the keysize of a Caesar cipher is 5.

Because the algorithm and key of ROT-13 is known (the algorithm is ROTate, and the key is 13) the keyspace is 1, and the only possible result is to decrypt.  The keysize of ROT13 is $1^{1} = 1$.  The next power of 2 greater than or equal to 1 is $2^0 = 1$.  Therefore the keysize (the exponent) is zero.

Keysize is an upper boundary of cryptographic security for an algorithm, as it represents the number of tries using brute force.  A 40 bit keysize (2^40) is easily brute forced on a home PC.  DES, with a 56 bit key length, was brute forced in the 1990s on a special purpose-built computer (Deep Crack.)  Keysize is an upper boundary only, because if an attacker can figure out a cryptographic weakness in the algorithm, they can use it to reduce the number of brute force attempts.  80 bits is right at the margin of what is considered safe - advances in computer power make brute forcing larger keys more and more possible.

(Please note that this explanation doesn't work the same for RSA keys, where factoring a public key is the method of brute force.  Today, a 1024 bit key is right on the margin of safety, and is not expected to remain safe much longer.)

Cryptanalysis is a fascinating study, and is highly recommended for anyone interested in cryptography.  Being able to break protocols or ciphers is the first step in understanding what is needed to make protocols and ciphers more secure.


Is this ECC based messaging method secure?

You should consider “sign-then-encrypt” instead of “encrypt-then-sign”.

Note that it is very important that the “encrypt” in “sign-then-encrypt” should be authenticated encryption. If you don’t use authenticated** encryption, you should definitely use an athenticating “sign-then-encrypt-then-MAC” approach.

Besides that:, when thinking about all this, you should definitely keep ECIES and ECDSA in mind.


Any standards for canonical ordering of HMAC or additional data in AEAD ciphers?

Imagine I have some serialization (example JSON) that can have 1-100 fields I’ll assemble into data to be get a MAC (my AD in AEAD). The receiving end has no idea which ones are coming, and the ordering of decode is not guaranteed.

If the receiving end really has no idea which fields are coming as you say, then the only way it can possibly determine the authentic AD for a message has to be from information that's transmitted alongside that message.  There's a bit of a subtle point here: the AD for a message in practice can be either (or a mix of):

Unencrypted data that is stored or transmitted along with the encrypted data proper.  Often people will call this a "header."  In this case the receiving end knows the AD because it's right there next to the ciphertext so to speak.
An encoding of information that isn't stored or transmitted along with the ciphertexts, but which the sender and receiver can correctly infer from the context in which each message occurs. For example, if messages are part of some protocol where the participants' interaction is governed by some state machine, an encoding of the current mutually known state can be used as AD.

If your statement that "the receiving end has no idea which [fields] are coming" is true, then, it sounds like you're in a pure example of #1—you have to send the JSON-encoded AD along with the ciphertext for the recipient to know it at all.  In that case the JSON text sounds like it would serve you just fine as AD or an element thereof, as the JSON encoder call that produced that text embodies some injective function of the data elements into a textual representation that can then be uniquely parsed.

JSON-encoded data however can be problematic for case #2 (implicit AD), because although JSON is uniquely parsable, there is more than one textual encoding for any given datum, e.g., whether you use optional whitespace or not, and ordering of named fields as you remark. The problem is that even if both ends mutually know the correct set of key/value mappings, they might encode it to different textual AD strings that would then fail the authenticity checks.  In that case either the two ends would have to agree on how to do the JSON encoding in an identical manner, or use some other encoding that's not prone to this problem. Encoding the fields alphabetically by field name as suggested is one possible tool for this, indeed.


Just how insecure are VeraCrypt containers encrypted with short passwords?

9 lower case letters with standard English alphabet make around 40-bit direct search this is very low password entropy. This is quite achievable even you use high iteration numbers like 200000 iterations for the HMAC-SHA-256. 200000 makes $\approx 2^{18}$ so in total $\approx 2^{58}$

Even public laboratories in the USA, like Oak Ridge Summit,  can achieve this;

The super computer Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year.

Actually there are two recommendations for you

Use diceware based passwords. EFF has a very decent page about this. This is a very good method to generate strong passwords that one can easily remember. With 8 words one can reach the 96 bits password entropy. A small list;

7 words have 80 bits
8 words have 96 bits
9 words have 128 bits password entropy.

Use the hidden volume in VeraCrypt. The hidden volume is created under a VeraCrypt volume that is indistinguishable from the free space of VeraCrypt volume since the free space in VeraCrypt is random, not zero, or FF. Keep in mind that, you must use a different password for this hidden volume.

An important aspect of the hidden volume is the plausible deniability. One can give the key of the outer VeraCrypt volume as honesty and keep the hidden volume key for themself. Since the hidden volume is indistinguishable from the free space it is not noticeable.

Note that as pointed by Mark, a forensic analysis can reveal the hidden volume. It is not perfect yet.


Can we use elliptic curve cryptography in wireless sensors?

Yes, one can use Elliptic Curve Cryptography in wireless sensors.

A typical use of ECC in this domain would be to authenticate the sensor and establish a symmetric session key using a combination of ECDSA and ECDH. That symmetric session key would then protect application data, insuring confidentiality and integrity using AES-GCM. This is hybrid cryptography.

Notice that in this typical use case, there is no mapping of points on elliptic curve to "message characters" representing application data; rather, application data is dealt with by mean of symmetric cryptography.

The main benefit of using ECC rather than RSA or Rabin in resource-constrained devices like wireless sensors is that for equivalent security, ECC needs less RAM, and shorter keys and messages; and also less CPU power when computing a signature, or establishing a session key, or (hybrid) DEcryption. On the other hand, for signature verification or straight Public Key ENcryption, RSA uses less CPU power (and allows shorter signed messages as well for many real-life use cases, including certificates).

As a consequence, ECC has an edge when there needs to be a public method to authenticate the data coming from the sensor (which implies ability to protect confidentiality of a private key in the sensor), or when RAM is extremely constrained, or when the amount of data exchanged during key establishment needs to be reduced to the max.

For other uses, including protecting the sensor from rogue commands and insuring confidentiality of the data sent by the sensor (basically the only goals still achievable when it is impossible to protect long term confidentiality of key material held in the sensor), RSA or Rabin is often a better choice than ECC. More RAM is required, but 1kByte is plenty enough for 2048 bit modulus, and it is used only temporarily during signature verification or PK encryption.


Is using a smart card and password two-factor authentication?

Is this still a two-factor authentication?

Yes, it can be but it depends on how the smartcard is used.

For example your OS could just use the password for authentication and ignore the fact that a smartcard is present in which case there would be no 2FA.

Or your smart card / OS could be configured to use a key on the card that doesn't actually require a correct user input to allow operation (though I'm not sure how many cards support that) and in this case it is imaginable that only the card matters for authentication which is also no 2FA.

However it is most likely that the OS will e.g. decrypt a per-user secret using a private key stored on the card or perform public-key based authentication against a remote server and your card will allow usage of the relevant key if you authenticate first to the card, which indeed is a form of two-factor authentication, as you need the card which holds the key and you need the password to operate the card.


Proof of application of $f(x)$ without disclosing input $x$

Use a zk-SNARK, proving the following statement:

Private data: $x$.
Public data: $y, pk, \sigma$

I know an $x$ such that $f(x) = y \land \textsf{Ver}(pk, x, \sigma)$

Where $\textsf{Ver}$ is the secure signature scheme verifier algorithm, $x$ is the secret input, $y$ is the output of $f$ applied on $x$, $\sigma$ is the signature of $\mathcal{S}$ on $x$, and $pk$ is the public key of $\mathcal{S}$.

As long as your signature scheme does not reveal your message contents within the signature $\sigma$, your scheme will be zero-knowledge. If it does, you can hash it prior to supplying it to the protocol:

Private data: $x, \sigma$.
Public data: $y, pk, \sigma'$

I know an $x$ such that $f(x) = y \land \textsf{Ver}(pk, x, \sigma) \land H(\sigma) = \sigma'$

Where $\sigma'$ is the hash of the signature.


Firstly, convince the verifier that $n$ is not a prime number. (Prime is in P)
Use Zero-Knowledge Proof to make sure that $n$ has no square factor (no $p^2|n$)

See this paper Practical zero-knowledge proofs: Giving hints and using deficiencies for details.
Showing that $n$ has exactly two factors: if not, the number of quadratic residues is roughly less than $1/8*n$. Verifier just randomly chooses a value y and ask prover to prove whether y is quadratic residue.

If the probability is roughly $1/4$, then accept.
Verifier can't cheat since he can only compute the quadratic residue, and let the probability raise, but not decrease below $1/8$.


Equivalence of Secret IV and Secret Prefix MAC

There are a number of assumptions being made here, and I will make them explicit in case this was not what you had in mind.

The first assumption is that we are using a Merkle-Damgard hash. That is, given a compression function $C(h, m)$, we have (assuming a properly padded message)
$$
H_{\text{IV}}(m_0 \| m_1\| \dots \| m_n) = C(C(C(C(\text{IV}, m_0), m_1), \dots), m_n).
$$

The secret-prefix MAC is simply $H_{\text{IV}}(k \| m)$. I also assume that secret-prefix MAC uses the entire first block, that is, the secret key $k$ is the same size as $m_0$ above.

The secret-IV MAC sets the $\text{IV}$ to be the key: $H_{k}(m)$. But notice we can easily convert a secret prefix into a secret IV by setting $k' = C(\text{IV}, k)$. Therefore if you have a key-recovery attack on a secret-IV MAC, the process is exactly the same with secret-prefix, except the output you obtain is $C(\text{IV}, k)$ instead of $k$. Likewise, an attack on secret-prefix MAC is highly likely to target $C(\text{IV}, k)$ and not $k$ directly. To define the IV, you cannot use the standard APIs for hashing (e.g., md4_init(&ctx)), but will likely have to write your own code.

Recovering this secret IV, in either case, will allow you to forge any message and completely destroy the security of the MAC. In the secret-prefix case, however, recovering the IV does not immediately translate to recovering the original key.


The whole idea of a KDF is to use the output of the key material as, well, an unpredictable key to an attacker. So as long as your IKM is secure and preferably your salt is unique, then the output of a KDF should be usable as key.

For HMAC it is best to use the same key size as the output of the hash algorithm used, as per HMAC spec:

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

You're correctly concatenating the nonces already to create the salt. Don't use XOR for that.

Um, yeah, I think there is all that there is to it. If you just need one key you can do with just HKDF-Extract which takes the IKM and, indeed, a salt.


Why is release of unverified plaintext so Bad?

If you don't care about the authenticity of the plaintext, why are you listening for it in the first place?  You could make up plaintext on the spot with your ears plugged up and it would be just as good!

Here's the traditional example:  You are a general.  You receive a message that says, Attack at dawn!.  Since it is late at night already, your cryptographer on staff decided to rush it to you before verifying the authenticator on it.  Alas, it was a forgery.  The secret message actually sent by your fellow general was Attack at dusk!.  That message, encrypted by a one-time pad, was intercepted in transit, and its ciphertext xored with the Attack at dawn! xor Attack at dusk!.

That is:

the original plaintext $P$ was Attack at dusk!;
the modified plaintext $P'$ is Attack at dawn!;
the original ciphertext was $C = P \oplus K$ where $K$ is the one-time pad;
the modified ciphertext is
\begin{align*}
    C' &= P' \oplus K \\
       &= 0 \oplus P' \oplus K \\
       &= P \oplus P \oplus P' \oplus K \\
       &= P \oplus P' \oplus P \oplus K \\
       &= P \oplus P' \oplus C.
  \end{align*}

This may sound contrived and goofy, but mistakes like this still happen today—and much faster, because your cryptographer on staff is actually a computer making millions of decisions every second and leaking the content of your encrypted email to an attacker.

‘But, but,’ you say, ‘you contrived that example to make it really easy for the attacker to modify the message, by using xor.  Surely the well-known mode of operation like CBC thwart this?’  It does not.  In fact the additional unnecessary complexity of CBC enables other attacks.  A one-time pad with a one-time authenticator guarantees secrecy and negligible forgery probabilities; CBC guarantees nothing whatsoever about forgery—every string of blocks is a valid ciphertext in CBC, so the cryptography can do nothing to distinguish valid messages from invalid messages.

To make the one-time pad and authenticator practical, generating the one-time pad and the one-time authenticator key from a short secret by a pseudorandom function like ChaCha or AES-CTR is widely accepted to be a good method that nobody is likely to break.  Better yet, just use NaCl crypto_secretbox_xsalsa20poly1305 when you and your peer share a secret key and you want to exchange secret messages on a potentially compromised channel.  (In a sequential conversation, use message sequence numbers as the nonce; in a nonsequential conversation, pick the nonce uniformly at random and affix it to the message.)

Unauthenticated data is pure evil—don't touch it!


AES (or otherwise): can you decrypt concatenated encrypted messages as one?

Stating "AES" is not enough to specify some encryption. AES is a block cipher, not a cipher. It's used per some operating mode. Among these

ECB without padding has the desired property that one can concatenate ciphertext fragments without decompression artifact, but is unsafe, and works only if the plaintext is an exact multiple of the AES block size (16 bytes).
CBC and CFB with IV prepended as ciphertext (which is usual) would do precisely what's reported: "when I decrypt 20 (concatenated ciphertext fragments) together it sounds like the original but with some clinky noise" because the IV (and perhaps some padding in the previous fragment) is misinterpreted as data, and inserts an error;
CTR or OFB would not recover from the error, and thus only the first 1/20 of the audio would be intelligible.
GCM or other authenticated mode would not output anything.

Is it possible using AES or another method to call my decrypt function on the concatenated 20 messages as one message and get the concatenated decrypted results?

Yes. One needs to take come precautions w.r.t. padding, but if the existing encryption procedure splits the data on some multiple of 16 bytes, there's nothing to change on encryption. Just remove from the output the extra data that corresponds to the inserted IV, and perhaps padding. That's merely 19 memory copy, over 19/20 of the data. It might save time, or not, depending on off-topic considerations.
For padding, the plaintext fragments should be aligned on multiples of 16 bytes (except for the last).
Encryption can be with padding (as most libraries do), but then one should either

Remove the last 16 bytes of each ciphertext fragment except the last before joining the ciphertext fragments; and remove the 16 bytes of IV at each of the 19 fragment frontiers in the output of decryption.
Remove the 16 bytes of data the padding generated (thus removing 32 bytes at each of the 19 fragment frontiers: 16 for padding of the previous fragment, and 16 for IV of the next one).

Alternatively, one can encrypt without padding, and manually pad the last plaintext fragment with zeroes, which for most compressed audio gets removed by the player, and for some uncompressed audio is silence.


ECC - ElGamal with Montgomery or Edwards type curves (curve25519, ed25519) - possible?

ElGamal works for any group. What is badly specified is the glue between the protocols (some network packets) and the exact implementation variants in the math library.

C25519 use arithmetic over Montgomery curves.

Ed25519 use arithmetic over twisted Edwards curves.

Huff curves implementations can be "faster", but there are not in the repository of curves types http://www.hyperelliptic.org/EFD

Implementations over MIST binary curves can be "faster" than integer curves. http://rt.openssl.org/Ticket/Display.html?id=3117 and even immensely faster than many implementations of c25519.

So you have a plethora of curves available to you. they are all equivalently secure related to "modulus size". Speed, constant time, inter-operability, conformance to standards, and bugs, depend on the library choices and implementation details.

Points from one specific curve (e.g. NIST B283) cannot be used directly in the arithmetic a different curve (e.g. Ed25519).

You have to go to DJ Bernstein original paper for the reasons of his choice for these curves. ECDH can benefit of XZ coordinates and montgomery ladder, assuming the protocol would not require that you transfer the Y coordinate between Bob and Alice. If you need Y coordinate, then c25519 and its XZ ladder is not much of an improvement.
EDDSA can benefit of the coordinate system for twisted edwards curves which has a strongly unified point addition which does not requires the implementor to specifically care about P+Q, P+3Q, P-Q, P+P .....

EC encryption, EC decryption, EC-ELGAMAL works with all of these curves. All you need is a standardization of the type of data exchanged between bob and alice. As far as I know, there is nothing approved in the RFCs and NIST standards, where lobbying and who'swho dictates the changes and approvals.


Infinite one time pads using a pseudorandom hash function

This is called a stream cipher.  It is a practical instantiation of the one-time pad model, where we encrypt a message $m$ with a single-use pad $p$ by using the ciphertext $c = m \oplus p$.

When $p$ is generated from a short key $k$ by $p = F(k)$, obviously $c$ and $m$ are not technically independent—we can't say of the probabilities that $P(m \mid c) = P(m)$, because obviously some pads are impossible—but the advantage the adversary has at breaking the cryptography knowing that we used $F(k)$ is limited by their advantage at distinguishing $F(k)$ from a uniform random bit string.

If $k$ is uniform random and $F$ is, e.g., ChaCha or SHA-256, the adversary has no hope of doing this without a breakthrough in cryptanalysis.


What would be a good choice for the hash type?

Whatever works best for you. As long as the hash is considered secure, the difference comes down to performance.  SHA-256 and SHA-512 are both traditional and safe choices recommended e.g. by NIST.  You can't really go wrong with either of those.  Which one is faster depends on your hardware.  (SHA-384 is basically just tweaked and truncated SHA-512; there's little point in using it unless you're implementing some standard that requires it.)

  What is a sufficient length for K0?

The master key needs to be long enough to resist brute force guessing attacks.  128 bits is probably enough; 256 bits certainly is.

  What is a sufficient length for Rn?

You should use Rn as the salt in HKDF-Extract, to detive a distinct PRK for each node.  For that purpose it just needs to be (almost certainly) unique for each node.

If you can assign the values deterministically, even 10 bits would be just enough for 1000 nodes.l, and 16 bits wouldbe plenty.  If every node chooses a random ID, you'll want something like 2×16 + 32 = 64 bits to guarantee a $< 2^{-33}$ (i.e. less than one in eight billion) chance of a collision for up to $2^{16}$ nodes.  (But be careful to seed your RNGs well!)

Also, if your nodes already have some unique ID each, you can just use those, however long they might be.

  What is the purpose / benefit / need of the optional Salt?  Is it okay to omit assuming it can't be sent in the clear or pre-shared?

The purpose of the salt is key diversification.  In your case, as noted above, you should use Rn as the salt to ensure that each node gets its own PRK.

The purpose of the info parameter to HKDF-Extract is to let you derive multiple (pseudo-)independent keys from the same PRK.  If you only need one key per node, you may omit it.


Is an invulnerable code possible (including brute force attack)?

No, If we assume that the mythical computer can brute force the multiple AES encryptions and there are many ciphertexts available which are encrypted under the same key and their corresponding plaintext are not random.

The brute-force code can keep track of the meaningful plaintexts for each ciphertext and finally can perform an intersection of possible key candidates to find the key.

Yes, If the plaintexts don't contain any meaningful information to distinguish them from random then there will be no possibility. So at least a distinguisher is required.


Is there an asymmetric encryption algorithm where the public key cannot be derived from the private key

RSA could do what you want: just put only the private exponent and the modulus in the private key, and not the prime factors of the modulus. Since the factors are not needed to decrypt, this will not hurt functionality.

This assumes, of course, that the party generating the keys has a reliable way to destroy the factors when they are not needed, but this seems to be implicit in what you are asking: since the key generation algorithm outputs both keys, if no reliable way to destroy data exists and the generating party is compromised, the attacker can both encrypt and decrypt.


Dimension of Encryption of a linearly dependent set of plaintexts

If $E$ was a random function from $\{0,1\}^N$ to $\{0,1\}^M$, then encrypting $n = |M_0|$ distinct messages with $E$ would be equivalent to picking $n$ independent random elements from $\{0,1\}^M$.  If $n \ll M$, these random elements are with very high probability linearly independent, and thus span a subspace of dimension $n$; conversely, if $n \gg M$, with high probability they'll span the entire $M$-dimensional space.

In any case, of course, $\dim(E(M_0)) \le \min(n,M)$.  If $n \approx M$, there's a non-negligible probability that the inequality is strict, but it decreases exponentially in either direction.  (In particular, the probability that $\dim(E(M_0)) < n$ equals $1 - \prod_{i=0}^{n-1}( 1-2^{i-M} ) \le \sum_{i=0}^{n-1} 2^{i-M} < 2^{n-M}$.)

Now, determining the dimension of the subspace spanned by $E(M_0)$ is computationally fairly easy (at least unless both $M$ and $n$ are really huge), so any non-negligible difference in it between the actual encryption scheme $E$ and a random function would allow a distinguishing attack on $E$.  Secure encryption schemes are not supposed to be distinguishable from random functions (without knowledge of the key), so if $E$ is secure, there shouldn't be any detectable statistical difference between the dimension of $E(M_0)$ and that predicted for a random function.


Where in the FIPS documents is it stated that SHA-1 is not secure?

Much of what NIST publishes about cryptographic algorithms is in Special Publications. In this case it is SP 800-131 (pdf) where they describe transitioning away from old algorithms and key sizes.
Pages 14-15 have the hash function specific information:

SHA-1 for digital signature generation:
     SHA-1 may only be used for digital signature generation where specifically allowed by NIST protocol-specific guidance. For all other applications, SHA-1 shall not be used for digital signature generation.
SHA-1 for digital signature verification:
     For digital signature verification, SHA-1 is allowed for legacy-use.
SHA-1 for non-digital signature applications:
     For all other hash function applications, the use of SHA-1 is acceptable. The other applications include HMAC, Key Derivation Functions (KDFs), Random Bit Generation, and hash-only applications (e.g., hashing passwords and using SHA-1 to compute a checksum, such as the approved integrity technique specified in Section 4.6.1 of [FIPS 140]).

FIPS 140, being the document you linked in the question, points to this document for guidance.


ABC Conjecture's Impact on RSA Encryption

There are no known implications of the ABC Conjecture to RSA.  The ABC problem doesn't have even a superficial resemblance to the security of RSA.

(The only point of connection is the fact that they both relate to prime numbers, but that is extremely thin.  Much of number theory can say it is somehow related to prime numbers.  It'd be like assuming that recent improvements in building fast sailboats for the America's Cup has implications for the possible future availability of a flying car, since they both involve fluids.)


What's asked is possible, both for public-key encryption and signature schemes.

One option can be a concatenation of the keys, with delimiters allowing separation of concatenated keys (by the same function for public and private keys), with

for encryption, cascaded encryption in order of the public keys
for decryption, cascaded decryption in reverse order of the private keys
for signature (with appendix), concatenation of the signatures in the order of the private keys, with delimiters allowing separation of the signatures
for signature verification, verification of all the signatures in the order of the public keys (and success iff all the signatures check).

More in details, restricting to public-key encryption: we start from some hybrid public-key encryption scheme, easily implemented with wrapper scripts on top of GPG. Encryption accepts any plaintext file and a public key (as a text file starting with -----BEGIN PGP PUBLIC KEY BLOCK----- restricted to a single such block), and outputs a ciphertext file. Decryption accepts a ciphertext file and the matching private key (as a text file starting with -----BEGIN PGP PRIVATE KEY BLOCK----- restricted to a single such block), and outputs the original plaintext.

We define the question's functions building new keys to both be concatenation: the "fourth secret key" is the file obtained by concatenation of the first three secret keys (with some EOLs as separator), same for the public keys.

We modify the encryption script to parse its public key input and, for each public key found in that, encrypt the plaintext (for the first key) or the previous encryption result (for the next ones, if any). It outputs the final ciphertext obtained.

We modify the decryption script in the same way, except that it processes multiple private keys starting from the last one in the private key input file.

The modified encryption and decryption scripts still works just as the original when fed a single public or private key. And when using the fourth public and private keys as obtained by the concatenation functions, they are able to encrypt and decrypt.

It can be proven that if GPG is secure, then the new scheme obtained is.


SPDZ- How to do secure less-than comparison

The way this is currently done within SPDZ is using a primitive which allows to truncate a secret shared value $[s]$ by a publicly known power of $2$.

You can see the code here.

In SPDZ, $k$ bit integers are in range $(-2^{k-1},2^{k-1})$. They are represented as $x \mapsto x$ mod $p$. So every number $x \in [2^{k-1},2^{k})$ is considered a negative number.

From a high level overview if we have the truncation, we can compute $[a] < [b]$ as a secret value:

Assign $s \leftarrow ([a - b])$ locally to see $[s < 0]$.
Denote $k$ as the bit length of $s$. Take $r \leftarrow [s/2^{k-1}]$ which has output either $[0]$ or $[1]$ depending on
the sign of $s$. Due to some technicalities of sign preserving, the output is in practice $[0]$ or $[-1]$.
To normalize the result, output $0 - [r]$. This is done locally again.

The expensive part here is step $2$ since parties have to communicate to achieve the truncation.

If you want to check the details you can find the specific protocols ($3.2$, $3.3$) on page $7$ here.


Can one detect if two pairs of elements in Zp have the same exponential relation?

This is another way of expressing the decisional Diffie-Hellman problem.  This problem is more typically written as 'given $g,\  g^a, g^b, g^c$, does $g^{ab} = g^c$?'.

As for the difficulty of this problem, it is believed to be difficult as long as you stay within a large prime subgroup; in this case (because you specify a strong prime), you means that you want to make sure that both $x1$ and $x2$ are quadratic residues.

Here's what can go wrong if you don't; an attacker can determine which subgroup any particular element belongs to; if he (for example) determines that $x1$, $x2$ and $y1$ are quadratic nonresidues, and that $y2$ is a quadratic residue, he knows that $r1 \neq r2$.  Staying within a prime subgroup prevents this possible information leakage.


Why does Birthday attack work only with random messages and not with chosen messages?

Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired. I can prepare $2^{n/2}$ letters of the first kind and $2^{n/2}$ letters of the second kind, and then we expect there to be a collision between a message of the first kind with a message of the second kind. Note also that it's not hard to prepare such letters. All you need is a number of ways of replace enough words. For example, consider "[Mr. | Dr. | Prof.] [Yehuda | Y.] Lindell was employed as a [security | cryptography] consultant in our [company | organization]." This sentence can be written 3 x 2 x 2 x 2 =24 different ways (and this is just one short sentence).

I would also like to note that it's even possible to carry out a low memory birthday attack on meaningful messages. But, I'll leave working that out to you as an exercise.


Does anyone know an easily creatable asymmetric cryptosystem for usage in VDF?

The issue of having to factor a large number in ElGamal appears only if you set the group order to be an arbitrary prime $p$. In this case, to find all subgroups of $\mathbb{G}$, you need the factorization of $p-1$.

However, this issue entirely disappears if you take $p$ to be a safe prime, i.e., a prime number of the form $p = 2q+1$, where $q$ is also a prime. Finding such primes is not so hard, and testing primality does not require to compute any expensive factorization.

Once you have $p$, sets $\mathbb{G}$ to be the sugroup of quadratic residues (i.e., squares modulo $p$) of order $q$ in the field of order $p$. Note that every quadratic residue (except $1$, of course) generates the full group of quadratic residues, and testing whether a number is a quadratic residue can be done efficiently. Therefore, there is no possibility that some ElGamal key in this group is invalid: any quadratic residue $h$ not equal to 1 is uniquely associated to a secret ElGamal key $s$, which is the unique $s$ such that $g^s = h$ ($g$ is some fixed generator of the group). Even though brute force to find the key is not efficient (that's the whole point of it, in fact), it is guaranteed to succeed (in exponential time) in finding the unique ElGamal key.

Therefore, it seems to me that a properly instantiated ElGamal scheme should suit all your needs.


One neat trick for the AES Sbox is to use logarithm. In that specific field, the value 3 (0x03) is a multiplicative generator for the non-zero elements. Thus, if you have a "multiplication by 0x03" function, you can compute a mapping $n \mapsto \mathrm{\texttt{03}}^n$ for all $0 \le n \le 254$; this would be an "exponentiation table". From that table, you can make the inverse mapping as another table, which would be a "logarithm tables". By going to logarithms, you transform multiplications into additions modulo 255, and divisions into subtractions modulo 255. In particular, inversion becomes negation.

In Java code, this may look like this:

    /*
     * Make tmp[n] = pow(0x03, n) in the field.
     */
    int[] tmp = new int[255];
    for (int i = 0, x = 1; i < 255; i ++) {
            tmp[i] = x;

            /*
             * Multiply x by 0x03 in the field.
             */
            int x2 = x << 1;
            x2 ^= -(x2 >> 8) & 0x11B;
            x ^= x2;
    }

    /*
     * Make Sbox[] as the inverse table. We use the fact that
     * 1/pow(0x03,n) = pow(0x03,255-n) in the field (since 0x03 is
     * a generator of the multiplicative subgroup of size 255).
     */
    Sbox = new int[256];
    Sbox[0] = 0; Sbox[1] = 1;
    for (int i = 1; i < 255; i ++) {
            Sbox[tmp[i]] = tmp[255 - i];
    }

    /*
     * At that point, SBox[i] contains the inverse of i.
     * Now we apply the affine transform in GF(2).
     */
    for (int i = 0; i < 256; i ++) {
            int x = Sbox[i];
            x |= x << 8;
            x ^= (x >> 4) ^ (x >> 5) ^ (x >> 6) ^ (x >> 7);
            Sbox[i] = (x ^ 0x63) & 0xFF;
    }

This kind of code can be convenient to recompute the S-box and related tables during an initialization process (assuming that you prefer the extra startup cost over the size cost of embedding the tables in the code).

(Of course, table-based AES implementations are not constant-time, you should not do that in practice, etc.)


Using a nonce as a salt for key derivation

I derive the secret key with argon2id from a password, but this needs a salt. So I was wondering whether it would be dangerous to use parts of the nonce as the salt, so I only have to transmit the nonce.

Yes, the salt is used to eliminate the rainbow tables. Keep in mind that the rainbow tables can be build up to some degree. If we consider that the Bitcoin miners agree to build a rainbow table instead of mining, they can build a table the can most cover $\approx 2^{92.8}$ passwords in a year. This is not considered the case that the slowness of the password-based key derivation functions, like PBKDF2, scrypt, Argon2. If we consider that they are parametrized to slow like $2^{20}$ then the coverage is reduced to $\approx 2^{72.8}$.
Within the Kerckhoffs's_principles - that is all but the key is known to the attackers - the attackers will always choose the shortest path to achieve their target whenever they see that. If you use the nonce and send it in public, they will try to find it. If the password is not good, they will find it! However, if the passwords have good entropy like diceware or bip39 is used to generate one,  there is no problem. Keep it above 128-bit entropy then your password is safe and the derived the key. Keep in mind that, the users tend to have bad passwords. Either you should educate them about using better passwords like generated by the diceware method or enforce them on some stupid rules that cause hard to remember passwords xkcd:936. In your case, you should generate a good one beforehand. You should also put an expire date-usage for the password, too. Or better, use a randomly generated key!.

Or is there a better approach?

Use Diffie-Hellman Key Exchange(DHKE) to exchange (establish better) the keys. One should prefer the Elliptic version of that ECDH. After the key is established then use HKDF to derive the key of the required length. Remember to use all of the exchanged keys. DHKE/ECDH That will provide you the forward secrecy as long as you and your friend deleted the keys after using them.
Actually, there is already a solution in the library; Crypto_box.


Advantages/disadvantages of different message numbering schemes

If the receiver can wait for all the packets before decrypting:

This case is simple, since your final goal is to ensure that the plaintext you decrypt was the exact same plaintext you encrypted. (Trivially, this includes rejecting re-ordered plaintext.) Use an Authenticated Encryption (AE) scheme (eg, CCM, GCM, etc) across all the packets, treating the packet contents as concatenated parts of the same message. The receiver waits for all packets to arrive then authenticates and decrypts them. If the authentication fails, the message is different in some way, possibly because the contents are re-ordered, possibly something else.

If the receiver must decrypt packets as they arrive:

Encrypt each packet individually. Use an AE scheme that supports additional authenticated data, such as CCM or GCM. Such schemes are designed to encrypt a secret payload and authenticate the same secret payload alongside plaintext data, which is often times metadata relevant to the ciphertext. If the authentication passes, the receiver can be sure that the secret payload corresponds with the plaintext metadata and that both are unaltered.

This allows you to encrypt your plaintext $M$ as $C=E(M)$, authenticate the ciphertext $C$ along with a plaintext packet number/counter $ctr$, then send $(C,ctr)$ to the receiver. The receiver verifies that $(C,ctr)$ properly authenticates, meaning that $ctr$ belongs to that package.

Presumably the packet number isn't a secret since an attacker can probably watch the wire and count packets anyway. Nonetheless, the packet number $ctr$ can be omitted from the data the sender transmits and the receiver can just substitute the $ctr$ value that they are expecting when they receive the packet and perform the authenticate.

The Proposed Schemes

This assumes you're using CBC for encryption and HMAC for authentication.

This is a good option. In concept, you've created a very simple self-contained protocol for your data that encapsulates ordering of the packets. Then the packets are simply encrypted and authenticated. It's the simplest scheme, and the least likely to be screwed up.
This is essentially building an AE scheme for ciphertext and additional associated data (message-number is the associated data). Likely encrypted-message is variable length, but message-number is presumably fixed length. If it is fixed length this should work, if it's variable length this would require modification.
This is potentially risky. The IV for a CBC-encrypted message should be unpredictable and you're working in discrete packets. If the attacker can control what data is in a packet and has seen the previous packet, they will know the IV for the packet they are about to generate and can use that to launch attacks. There was a popular TLS/SSL attack that exploited this type of CBC IV chaining.
This option is actually kind of pointless. It requires that the original random IV be sent along with the derived (aka, "actual") IV, both MAC'd alongside the ciphertext. Verifying message-number would consist of re-deriving the real IV using the random IV and the expected message-number. It's essentially option (2): they both have an IV, message-number-based value, and the ciphertext.

(To see why both IVs must be sent: If just the original random IV is sent, we can't validate that the derived IV is correct. The HMAC covers only the ciphertext and random IV, so after that the HMAC does the check the packet receiver will derive the real IV and have nothing to check it against. If message-number is wrong then the derived IV is wrong, and the first block of plaintext is trashed, but a trashed first block of plaintext is not always detectable.

If just the derived IV is sent, the recipient can't validate what message-number the derived IV is for. The HMAC will validate the derived IV and the ciphertext, but the receiver will just decrypt using the IV, knowing nothing about what message-number should have been used to generate it.)
This would work, but it is pretty much the same as option (1) if you send the "actual" IV, since the receiver needs to check the message-number by decrypting the IV (option (1) would require decrypting the plaintext).

Of those listed, option (1) is probably the best. It isn't the cryptography itself enforcing the message ordering, rather the "protocol" encapsulated within the packets. Option (2) seems perfectly reasonable as well.


What is the difference between a permutation and a shuffle (transposition cipher)

A shuffle (or transposition function) re-arranges elements of the input. A permutation re-arranges the entire output domain.
For example, compare the following transposition function and pseudorandom permutation:
The transposition takes in a 4-digit number, and re-arranges the digits. 1234 might become 4213, but never 1692.
A pseudorandom permutation has a shuffled list of all possible 4-digit numbers, and an unshuffled list of all possible 4-digit numbers. It looks up the input number in the unshuffled list, finds the corresponding number in the shuffled list, and outputs that. 1234 might become 1692.


Can a LFSR has more than one repeat cycle?

There is a very nice recent paper available here by Chang, Ezermann, Ling and Wang, which has addressed this problem for arbitrary alphabet $\mathbb{F}_q$ and arbitrary characteristic polynomials, including those with divisors that are powers of irreducible polynomials.

Let $\Omega(f)$ be the set of sequences satisfying $f$ as their characteristic polynomial.

This paper determines the cycle structure of $\Omega(f)$ fully for an arbitrary $f$ and gives a method to identify a state from each distinct cycle in $\Omega(f)$, a longstanding open problem.


How is the SPI determined/negotiated in phase 2 of IKE (v1)?

Is the above description actually how it takes place?

No; it works as you suspect.  Each side chooses the SPI to use for the incoming SA; that is, how the other side marks encrypted packets that are encrypted with this SA; in the initial quickmode message, the initiator specifies the SPI that will be used for encrypted packets going to the initiator, in the response packet, the responder specifies the SPI that will be used for encrypted packets going to the responder.  This is done specifically so that, in either case, the decryptor can select SPI values that are convenient to look up; for example, it may chose to place an index into a 'decryption table' into the lower 16 bits, say (and yes, there are implementations that do that).

  If yes, what happens in case the responder receiving the SPI from the initiator finds out that the SPI value is already in use?

While (as above) the assumption behind this question is wrong, there is a nontrivial answer here, and so I'll answer that.

As above, the initiator selects its SPI first (that is, the SPI for its incoming packets), and the responder then selects its SPI.

Because of how IKEv1 derives keys, if the responder selects the same SPI as the initiator, the keys for the two SAs (going in the opposite directions) will be the same; depending on what transforms are negotiated, this can be disastrous.  I don't believe there's any requirements, but I know of at least one implementation that will, as a responder, always select a different SPI then the initiator, and as an initiator, if it sees the responder selected the same SPI, automatically close the connection without encrypting anything.


what is the difference between proofs and arguments of knowledge?

Yes, you are right. In a proof, the soundness holds against a computationally unbounded prover and in an argument, the soundness only holds against a polynomially bounded prover. Arguments are thus often called "computationally sound proofs".


How can I use the whole potential of DES?

Programming your own DES is usually a bad idea (unless as an exercise to understand the algorithm better), but OK. By definition the algorithm works with blocks of data that consist of 8 bytes (i.e. integers in the range 0..255), and the key is 7 of those bytes (or 8 with unused parity bits).

What the data means (text or binary files like Office documents or zip files) etc. is irrelevant. I don't see what you mean by "full potential". You can just use it for ASCII text. It doesn't really matter what range the bytes are in. The encoding of the data is up to you (you can pack lower ASCII data into 7 bit characters, that overflow into the next byte, as SMS does, e.g.), and not a part of DES or any crypto-algorithm. Bytes are bytes. DES handles bytes.


Assuming by "digit" you mean "base-10 number"...

There are $10^4$ different combinations.

$\log_2(10^4) \approx 13$

It would require no more than $2^{13}$ guesses to guess every single possible seed. This assumes that the seed is uniformly random.

Even using python on relatively modest hardware, it takes .001 seconds to iterate over all the possible seeds.

So yes, it is easily guessable.

You would require at least $2^{64}$ cost to become merely inconvenient rather than trivially guessed.

The minimum size for it to be considered secure is 128 bits. That would correspond to roughly 39 uniformly random base-10 digits.


Plain AES is a block cipher, which can only encrypt 128-bit blocks (i.e. 16 bytes at once).

To encrypt longer pieces of data, one would normally create a stream cipher from the block cipher, by using one of several modes of operation. The simplest (and most insecure) one is the electronic code book mode (ECB), which (for the same key) always produces the same ciphertext for the same plaintext block. Normally one thus would use one of the other modes (like CBC, CTR, ...), each having different advantages.

If you need only sequential access to the whole file, any of these modes will do, as you can always decrypt the file sequentially.

If you need some kind of random access to specific parts of the file, you would break it down into parts which each could be accessed individually. Each of them would then be encrypted as essentially a separate stream, i.e. starting with the initialization vector, and including (if necessary) the padding to fill the last 128-block.

You would also want an index to the parts, so you know which part to access.

Alternatively, you could use CTR mode, which essentially allows random access to the file, only knowing the nonce and the block index, without the need to read or decrypt the blocks before or after the desired block.


Computing the cardinality of the co-domain of specific modular exponentiations

One way to approach this problem is to first look at the simpler problem of that cardinality of $x^e \bmod p$ where $p$ is prime, and $gcd(p-1, e)$ might not be 1.

In that case, we have two cases: $x \equiv 0 \pmod{p}$, which makes it obvious that 0 will always be a possible postimage, and $x \in \mathbb{Z}^*/p$; in this second case, that group is isomorphic to the simpler group $\mathbb{Z}/{p-1}$; considering that simpler group, it should be obvious that there are $\frac{p-1}{gcd( p-1, e)}$ possible postimages.  Combining the two gives us $1 + \frac{p-1}{gcd( p-1, e)}$ total postimages.

Now, going back to your original question, $p$ and $q$ are relatively prime, and so by the Chinese Remainder Theorem, any pair of inputs $x \bmod p$ and $x \bmod q$ are possible.  In addition, a postimage $x^e \bmod n$ is possible iff the corresponding postimages $x^e \bmod p$ and $x^e \bmod q$ are both possible.

The upshot of this is that the total number of possible postimages is the product of the number of postimages mod p times the number of postimages mod q.  Or, in other words,

$$|Y| = \lgroup 1 + \frac{p-1}{gcd( p-1, e)}\rgroup \cdot \lgroup 1 + \frac{q-1}{gcd( q-1, e)} \rgroup$$

We see that if $\gcd( \phi(p), e) = 1$, then $gcd(p-1,e)=1$ and $gcd(q-1,e)=1$, and this formula simplifies to $|Y| = pq = n$

I know that you asked for a function depending on $n$ and $e$, however since it is believed to be computationally infeasible to compute $gcd( \phi(n), e )$, coming up with even a formula to estimate $|Y|$ looks impractical.


Can passwords be stored securely so that a similarity comparison can be made?

Storing passwords in such a way as to allow comparison against portions of the hashed password is by definition less secure than traditional cryptographic hashing. As a rule, this is simply never done.

On the other hand, you could safely make comparisons of portions of your new password (for which you necessarily have the plain text) against the entirety of an old hash, and such comparisons are done today by some existing software.

To address your original point, to the best of my knowledge, cPanel does not do what you suggest. It has the option of storing certain kinds of passwords reversably encrypted for use with digest authentication, but this is not the default. All other password storage is done through the underlying product's default hashing mechanism (be it MySQL's hashing, shadow file, etc).

The discussion may have confused cPanel with Plesk, which until very recently stored all passwords in plain text in a MySQL database. Yes, really.


Security of RSA for padding $\texttt{0x00|message|random_bytes}$

Your message format is;

$$\texttt{padded_message} =\texttt{|0x00|message|random_bytes|}$$

You did not specify what will happen if the message is short. If we assume that it is filled with zero then a short message is;

$$\texttt{|0x00|0x00...0x00|short message|random_bytes|}$$

Now there is an active attack. Since the attacker knows the public key $(n,e)$ then the attacker can modify your ciphertext $$c = E_{k_{pub}}(\texttt{padded_message})$$ by multiplying with the encryption of $2$ $$c_2 =  E_{k_{pub}}(2)$$ and the result is;

$$D_{k_{prv}}(c \cdot c_2) = \texttt{|0x00|0x00...0x00|short message|r|random_bytes|0} $$

where your plaintext (short message) is shifted by one and a random bit value is assigned from MSB of the $\texttt{random_bytes}$.

The BT in The PKCS#1 v1.5 padding can prevent this attack. For a general answer, please see;

How does PKCS 1.5 solve the insecureness of Textbook RSA?


How is a public key actually used to encrypt something?

Rick Demer already wrote the answer in the very first comment, but without explanation: Hybrid encryption.

But since you asked for a real practical example to encrypt your word document, this is how: Your file is on your disc, and it is 100,000 byte large. You can then do:

First, you start up a random number generator. Preferably you should either have true randomness or at least a cryptographically secure RNG.
Let the RNG generate a random 256 bit number.
Start up your AES 256 engine/program/hardware module, and choose the appropriate mode of operation like CBC. Use the random number as key.
Use AES to encrypt the entire content of the file.
Get your public key or generate private/public key, depending on what you want to do.
Encrypt the random number (used as symmetric key) with your asymmetric encryption scheme. In the case of RSA, do not just use the textbook variant but RSA-OAEP or a similar padding scheme.
Create a new file: Put relevant information in the file header (whatever you want to be accessible without decryption). In the data of the file, write down the encrypted random number (it was encrypted with the public key), and then you just add the entire encrypted file-content (encrypted with AES).
Optional: You can add delimeters inside your file to make it easier to see where the key ends and where the ciphertext starts. If you want you can also note down which algorithms you actually used to encrypt this specific file.

AES can obviously be replaced with any other symmetric cipher, you can also pick a different mode of operation or use a specific asymmetic encryption scheme to encrypt the random key. If you do so, putting it into the file might help if you ever forget which file was encrypted with which algorithm.

Note on using asymmetric encryption directly

It is also possible to use for instance RSA directly on your $100,000$ byte document. If your RSA key is $1240$ bit long, then you can split your document into $800$ blocks with each block having $1000$ bit (or e.g. $650$ blocks of $\approx 1231$ bits, whatever suits you). Then you can apply RSA directly to each block and be done with it. The problem is that this is extremely slow. The ratio of processed bits per second is magnitudes lower for asymmetric encryption than for symmetric encryption. And then you have the problem, that RSA shouldn't be used in the textbook variant and RSA-OAEP increases the length.


The way I picture it, a pseudorandom number generator (PRNG) has a box of bytes called "internal state".

Seeding the PRNG sets that box of bytes to some deterministic function of the seed.

Every time you ask the PRNG for another number,
the PRNG "stirs the pot" to some new state -- using a deterministic function of the previous state.
The PRNG also generates an output integer that is some function of one or more bytes in the box of internal state.

I'm not sure where you are getting the "n" in your question -- every PRNG I've ever encountered will continue to produce numbers indefinitely, no matter how many numbers it has already generated since you seeded the PRNG.

The size of the box, the specific deterministic functions used by some PRNG, etc. are generally spelled out in detail in the description of that PRNG.

You may be interested in CipherSaber, Salsa20, Fortuna, etc.


How many required known plaintexts for an attack are considered insecure?

Firstly, is this a correct threshold for considering a cipher secure?

Not exactly. Security is a spectrum, so what is secure for some applications may not be secure for others. Is a $2^{-64}$ probability of attack success too much? For some it is far too high. For others, even $2^{-32}$ is fine. In the case of known plaintext attacks, an attacker is usually assumed to have as much known plaintext as they want. In such cases, the bounds are placed on the amount of plaintexts that can be reasonably stored and processed. That is, a petabyte of known plaintext may be assumed (high-speed hardware that behaves as an encryption oracle may allow this), but $10^{90}$ exabytes? Usually not.

As stated, your question doesn't have an objective answer. You would need to append "when performing a specific number of encryptions" to get a real answer, in which case you consult the effects of block size on certain modes of operation. For example, Blowfish is a 64-bit block cipher and is considered secure when encrypting, say, one gigabyte of data under a given key. You can calculate the precise requirements for an attack under those conditions and show that the attack is not practical. If, on the other hand, you encrypt a hundred gigabytes, things will get nasty when using that block size.

A known plaintext attack for a given cipher is usually considered not to be a problem if either:

The specifications make it such that it is impossible to obtain enough known plaintext, or
The amount of known plaintext required would be so vast that no one could encrypt that much.

An example of the first reason for not worrying about known plaintext attacks is in two-level E0, as used in some older versions of Bluetooth. The E0 stream cipher is extremely vulnerable to known plaintext attacks. Rather than vastly modifying the Bluetooth specifications, an easier mitigation was to require rekeying before enough data is transmitted to provide enough known plaintexts to perform an attack.

It turns out that the best attack against E0 requires a bit of known plaintext from only $2^{23.8}$ frames, but the Blutooth protocol allows up to $2^{26}$ frames to be encrypted under a single key, rendering E0 more insecure than implied above.

An example of the second reason would be a 128-bit block cipher in CTR mode. The amount of data required to perform an attack on it is staggeringly huge. An online cost of $2^{64}$ is really quite massive.

  And secondly, does this mean that all 32-bit block ciphers are inherently insecure?

For the vast majority of uses, yes. For those asking if a 32-bit block size is too small, also yes. However there are a few edge cases when that block size is acceptable. This is only the case if truly minuscule amounts of data are being encrypted under a single key. Encrypting small session tags is one example.

The cipher Speck32/64, for example, is considered to be secure despite having a 32-bit block size and a 64-bit key size. It provides 64 bits of security under the constraints that only a trivial amount of data can be encrypted with it. But that doesn't mean you should be encrypting your hard drive with Speck32/64. That is because those parameters make it vulnerable to generic attacks under realistic conditions.

A generic attack is one that applies even to an ideal, perfect block cipher and is utterly independent of its internal workings. Brute force of the key and issues caused by the birthday bound when used with certain block modes are both kinds of generic attacks. A block cipher is not considered inherently insecure in the cryptographic sense just because a generic attack may apply to it, but it may be considered insecure by practitioners. After all, an attacker doesn't care that they broke something with a generic attack because you used a small key or a small block size instead of using some fancy and complex cryptanalysis.

Generally, you should assume the following statements about block sizes to be true:

256 bits is always safe from the limitations imposed by the birthday bound.
128 bits is safe for the vast majority of use cases with realistic amounts of data.
64 bits is worryingly small, but is acceptable if used carefully and not for a lot of data.
32 bits is only safe in extremely rare circumstances. For others, it is horribly insecure.


What does CMS standard mean by "initial input to the message digest"

Consider the two cases.

without signedAttrs: first we hash the content, then we sign that hash. The first thing we do is hash the content.

with signedAttrs: first we hash the content, call it hash1; then we construct signedAttrs which includes hash1 in the message-digest attribute; then we hash signedAttrs, call it hash2; then we sign hash2. Only hash2 is used in the digital signature operation, but to compute hash2 we must previously have the value of signedAtttrs, and to have the value of signedAttrs we must previously have hash1, which is the hash of the content, so the first thing we do is hash the content.

Either way the first thing we do is hash the content which uses the content at input. Since this is the first thing we do, the initial input is the content. And in particular the value octets, not the tag and length, which is the actual point being specified in that paragraph.


If $q$ is prime (which is a common additional constraint) then the possible orders for a random $F_p$ between $2$ and $p-2$ inclusive is either $q$ or $2q$ so you can avoid having to check the order by picking one at random, squaring it and using the result.


The difference in size between ECDSA output and hash size

First to explain you, why you get 512-bit outputs from a 256-bit curve:
The output is basically a point (x-coordinate is enough) and a message-dependant value, with the x-coordinate being expressed as integer. You can verify the signature by checking for a specific relationship between the point and the message-dependant value and the public key point. In order for this relationship to be build the private key is required.

Second, to answer your question why SHA-256 is used and not SHA-512. Consider how the hash function is actually used in ECDSA. You always take the $n$ leftmost bits of it, with $n$ being the curve order bitlength. So if you use SHA-512 you're "wasting" 256 bits, whereas with SHA-256 you "waste" nothing.And from a key-length point it also makes sense to settle on the 128-bit security level (which is defined through your choice of secp256) and it would make no sense to choose a hash-function with 256-bit security level to be used with a curve providing 128-bits.


What is meant by encrypting/decrypting a known plaintext/ciphertext with every possible key in meet-in-the-middle?

Your question has given to you only 20-bit key space so, you can achieve it. As mentioned earlier, even storing one full table is not an easy job and accessing $2^{56}$,too, although we know that Titan can reach $2^{62}$ around one hour, it is a supercomputer. Your task simply says that your key will be in the format in binary case as:

xxxxxxxpxxxxxxxpxxxxxx0p0000000p0000000p0000000p0000000p0000000p

so you have to iterate for x's from

0000000p0000000p0000000p0000000p0000000p0000000p0000000p0000000p

to

1111111p1111111p1111110p0000000p0000000p0000000p0000000p0000000p

and store them in a table T1 ( or hash map). (There are 64-bit over there). The p represents the parity bits.

From Wikipedia:

  Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 (PC-1)—the remaining eight bits are either discarded or used as parity check bits

In the next step, use the same iteration for the decryption and look for the result in T1.


The triple DES (3DES) block cipher works by essentially running the block through DES three times. Triple DES is also known as "DES EDE" (encrypt-decrypt-encrypt) and under the name given by the standard document: "TDEA". The TDEA algorithm is described in FIPS NIST Special Publication 800-67
 Revision 1 where paragraph 3.2 describes the TDEA Keying Options.

In triple DES you take the block and then:

Send it through DES once with a DES key $k_1$
Send the result of that through DES a second time with a DES key $k_2$ (for this second time we generally run DES backwards; in decrypt rather than encrypt mode, however, that's not important for this question)
Send the result of that through DES a third time with DES key $k_3$.

The result of that is the result of the 3DES block operation.

Now, 3DES comes in two main flavors:

The "2 key" version; in this version, the 3DES key consists of two DES keys; $k_1$ and $k_2$, and we implicitly assume that $k_1 = k_3$.  DES keys are typically represented in 64 bits, and so this version of 3DES has 128 bit keys.
The "3 key" version; in this version, the 3DES key consists of three DES keys; $k_1$, $k_2$ and $k_3$.  Because all three 3 DES keys are explicitly represented, this version of 3DES has 192 bit keys.

The keys are sometimes also referred to as key A, B and C. The key for the 2 key version is then referred to as an ABA key and for the 3 key version as ABC key.

Those are the only standard versions of 3DES; you might have an API which allows 64 bit keys (which likely emulates DES in that case); if it allows 256 bit keys, I have no idea what it would do with them.

In case you're wondering whether DES keys are 56 bits or 64 bits, well, they are considered 56 bits of cryptographic strength (because we can run through all possible DES encryption operations by trying $2^{56}$ different values); however when we represent a key, we typically express it as 8 bytes (or 64 bits).  In that case we essentially ignore the least significant bit of each byte (originally, they were "parity bits" for each byte, however since no one manually enters DES keys anymore, most implementations end up ignoring them instead). That's the way the DES designers did things; most everyone follows tradition.

So sometimes the (triple) DES key lengths are referred to as 56 bit, 112 bit or 168 bits instead of 64, 128 or 192 bits respectively. Usually cryptographic API's still require you to enter 8, 16 or 24 bytes despite of this. AES fortunately does away with all this.


Question about SHA-2 (and potentially similar hashing algorithms)

Would it not be better to use a set of less predictable values?

Actually, there aren't any "unpredictable values".

SHA-2 is a hash function (actually, it's a family of 6 hash functions; we'll ignore that point for now); a hash function is designed so that anyone can compute it.

One use of a hash function is during signature generation and verification; typically, the signer takes the message, and hashes it, and then applies the signature operation to the hash.  Then, the verifier takes the message, hashes it, and then verifies the hash against the signature.  If the verifier could not compute this hash, he could not verify that the signature corresponded to this message.

Because of this, the entire specification of SHA-2 must be made public, so that the verifier (and anyone else) can compute it.  That is, any internal table values must also be public, because they are needed to compute the hash function.

Because we're going to tell everyone what the values are, they aren't, in any sense, unpredictable.


Keys for AES are not numbers; they are defined as bits / octets (or bytes). They therefore do not have a "least significant octet", they just consist of octets. So the same order from lowest index (left) to highest index (right) is being used.
As common the bits are indexed from right to left though; this is probably due to humans having some trouble converting hexadecimal digits otherwise. It just shows that humans are terrible at thinking in little endian.
The exact ordering is specified in the AES specification as mentioned by fgrieu int he comments.


TLS1.2 AES 128 CBC Encrypted Data size is not a multiple of block size

The default mode of TLS use MAC-then-Encrypt, it compute the tag, append it to the message, and then padd it to have a length multiple of the block size (16 in our case).
However, you can change the default mode to use Encrypt-then-MAC (which eliminates risks of padding attacks over AES-CBC). In this case, the message is padded and encrypted, and only then you compute the tag and add it at the end.

In your case,  TLS_RSA_WITH_AES_128_CBC_SHA use SHA1, which produce a 20 bytes long tag :
$$116-20=96=16\times 6$$

That's the only way I have to explain it, but both the server and the client have to implement the option Encrypt-then-MAC.


How to choose the linear approximations to build a path through a SPN in Linear cryptanalysis?

I think this is what you are asking. You have to respect the permutation layer, otherwise canot apply the piling up lemma.
The approximations must be "joined together" between rounds by respecting the P-box mapping, so that they can be "added together with cancellation" to get multiround linear characteristics.
Say you apply an approximation $$a\cdot x\oplus b\cdot S(x)$$ to Sbox $S_{1,1}$ [round 1, 1st sbox] whose output constant $b$ is [1,0,0,1]. If you follow the wires at the output of this Sbox, you can see that you need to apply some linear approximation $$a'\cdot x \oplus b \cdot S(x)$$
where $a'=[1,0,0,0]$ to Sboxes $S_{2,1},$ and $S_{2,4}$. Then you use the fact that the key bits cancel and apply the piling up lemma to get a 2 round approximation involving Sboxes $S_{1,1},S_{2,1},S_{2,4}$.
Where is the optimization? You need to stick to relatively low hamming weight $b$ vectors to avoid turning on too many S-boxes since the piling up lemma is multiplicative and each new active S-box reduces the overall bias. You also want to find the highest individual bias characteristics.
In general, this needs to be checked exhaustively.
The following answer gives more general details about linear approximations:
Help with linear cryptanalysis


How can a digital signature algorithm incorporate a random data if it is to be authenticated on a separate system

RSASSA-PKCS1-v1_5 does not use random padding, the scheme is deterministic.

  RSASSA-PSS is different from other RSA-based signature schemes in
     that it is probabilistic rather than deterministic, incorporating a
     randomly generated salt value.

The signature is verified using a hash over the message hash and the salt. So the verifier does not need to know how the random is generated, it will just verify the hash over it. Check steps 9 to 14 of the PSS signature verification of RFC 3447 paragraph 9.1.2.


What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices?

Usually, the FHE schemes are proved to be CPA secure, therefore, the game is similar to the IND-CPA game, with the caveat that the attacker also hold a evaluation key (generally necessary to perform the homomorphic operations). Note that the evaluation key is public anyway, therefore it could just be considered as a part of the public key so that the game would be the same (this is done, for example, in the proof of security of BGV).

If there is some type of circular assumption (which is normally the case), then, you suppose that the evaluation key depends on the private key. However, this does not change the game.

Thus, the game would be more or less like this:

Parameters are set, keys are generated and the adversary receives the public and the evaluation keys.
The adversary can encrypt messages and compute over the ciphertexts freely.
The adversary sends two messages $m_0$ and $m_1$ to the challenger and receive a ciphertext $c_b$ corresponding to $m_b$ (for a random $b$).
The adversary can again encrypt and perform other computations.
The adversary outputs a bit $b'$.

Side note:

As noted by @Maeher in the comments, we have to be careful when talking about CCA security and homomorphic encryption. It is already known that homomorphic encryption schemes cannot be CCA2 secure, thus, in your model, the best you could do to prove CCA security would be to use a game for IND-CCA1 security, as it is done, for instance, on this article (although they are dealing with Somewhat Homomorphic Encryption instead of FHE).


In W-OTS, is it trivial to forge smaller N values?

W-OTS has a checksum that ensures that kind of attack doesn't work.

In essence, the checksum is the sum of the value of every other component subtracted, so that if you hash one component one more time, you need to find a pre-image of a component of the checksum.

Basically, it looks a bit like this:

[ - | - | - | down | checksum up ]

Related: https://crypto.stackexchange.com/a/63903/36960


Can compression + encryption sometimes be beneficial?

Regarding your comment about the CRIME attack, I think I can write an answer:

TLS is one of the common ways for encrypted communication, which gave the CRIME attack a lot of attention. However, I think you drew the wrong conclusions there:

First and foremost, not the encryption scheme was broken. The attack broke the protocol. That is a massive difference.
It only affected those TLS versions, which used a different algorithm: DEFLATE. And the attack works only with that, not a general compression algorithm.

And now I have to say, that your conclusion is probably going into the wrong direction. It is the wrong conclusion to say that coupling compression and encryption is bad in general.   Here are some conclusions I would draw from this:

It's very important to design protocols properly. Someone will find the most unlikely weakness.
Think of all possibilities - especially when it comes to user input and third-party libraries and programs. When it comes to security, better expect the worst than missing something crucial.
The functionality of DEFLATE is quite horrible when you have to consider that linking backwards with short tokens is actually bad. We can only speculate, that it might have been an oversight when it was permitted as compression algorithm.

Regarding the VoIP weakness: Again, that has nothing to do with the security of the encryption schemes itself. It does not break the encryption, but the conidentiality of the communication.

And the reason for that is the combination of timing, the length and number of each individual message etc. All those criteria are not hidden by encrypting the individual messages, and the error here is from the designers, who might not have considered that it's a bad idea if the flow of the messages (length and density of messages over time) actually reflects the content of the messages.

However, that's a sidechannel in this specific scenario. It is not a weakness in general for compression algorithms, but a very specific situation and the information used is actually outside the scope of the encryption (the meta-data).

  I considered this known problems... I didn't know there was anything controversial about it.

The examples are not controversial - but the generalization of them is IMO unreasonable. Also, those incidents actually are not an ideal fit for this site but security-SE would be much more fitting.


Why do SignTool/Authenticode Message Digests not match the direct hash of the file?

You are expecting that the hash that is produced is always over the complete file. This is not correct. Authenticode uses the Cryptographic Message Syntax - a container format - to embed the content and the signature. This ensures that the Authenticode signature is using the hash of the original data (+ other signed attributes). The Authenticode format is specified here.

To quote:

  A PKCS#7 SignedDatastructure contains the PE file's hash value, a signature created by the software publisher’s private key, and the X.509 v3 certificates that bind the software publisher’s signing key to a legal entity. A PKCS#7 SignedDatastructure can optionally contain:

  A description of the software publisher.
  The software publisher's URL.
  An Authenticode timestamp.

Note that Microsoft keeps interchanging the name of the standard with the name of the structure that it defines: PKCS#7 is the standard that defines the Cryptographic Message Syntax.

Unfortunately, going through all the steps of "Calculating the PE Image Hash" is a bit too much for this answer; if you plan to do this programmatically you could ask questions about it on StackOverflow.


RSA finding p and q integer with condition

The question's attempt at resolution is headed in the wrong direction for two related reasons

It informs the math tool that 44*p = 17*q when the problem statement has $44\,p\approx 17\,q$. If we had $44\,p=17\,q$, then $p$ and $q$ could not be primes, as stated in the problem.
It is not informing the math tool that $p$ and $q$ are integers. I can't help about how to do that for Mapple, and it is off-topic anyway.

$N$ is way too small to be useful as an RSA modulus, and could be easily factored without the hint that $44\,p\approx 17\,q$. Anything below 100 decimal digits has long been factorable by a single PC in minutes (see this); the lowest considered reasonable by Y2K was 1024 bits ≈ 309 digits; current is double that, moving to triple or away from RSA in the long run.

This is an application of Fermat's factoring method. This method is very efficient to factor integers of the form $C=A\,B$ with $A\approx B$. The hint $44\,p\approx17\,q$ tells that $C=44\cdot17\,N$ must be of this form, with $\{A,B\}=\{44\,p,17\,q\}$. Once we have factored $44\cdot17\,N$ using Fermat's factoring method, we can easily get at $p$ and $q$.

Don't fall into the trap of thinking that we must specifically guard against Fermat's factoring method and extensions when choosing an RSA key. The likelihood that the product of random primes $p$ and $q$ of practical size can be factored in this way is infinitesimal.

Update: there must be some typo in the value given for $N$, since (as commented by kelalaka) the integer given has 4 prime factors.


If k is even

Choose a string m
Choose any block of m other than the last
Flip the most signficant bit of that block.

They collide because you effictively shift all bits of that block one place to the left. If $x \equiv y \mod 2^{n-1}$ then $2x \equiv 2y \mod 2^n$.

Additionally if $k$ is even all strings with their last $n$ blocks equal collide. This is because the previous blocks have a coefficient congruent to 0 mod $2^n$. (They're multiplied by a multiple of $2^n$.)


Consider ANSI X.923 padding for example, how would the decryptor know that the sequence 00 00 00 04 is not some special data but padding?

Because padding is always used. Thus if the file before padding was 41 42 43 44 00 00 00 04, it would be padded 41 42 43 44 00 00 00 04 00 00 00 00 00 00 00 08 then encrypted.

This rule, or similar ones differing on how the padding octets other than the last are generated, are common and fine when padding octet strings.

For the most general problem of padding arbitrary bit strings, one of the simplest and most general is bit padding, which appends a single 1 bit, then zero to b-1 0 bit(s) as necessary to reach a multiple of the blocksize $b$ (in bits). That can be designated as ISO/IEC 9797-1 padding method 1, but this standard does not prescribe un-padding. This should fail is there's not at least one block; removes final 0 bit(s) in the last block, and fail if that exhausts the last block; finally, remove the final 1 in that last block.

When restricted to octets in big-endian convention, bit padding becomes appending a 80 octet, then zero to b/8-1 00 octets as necessary to reach a multiple of the blocksize.

Use a simple padding rule, and always apply it; complexity and exceptions are the enemy of practical security. Whatever the method, beware of padding oracle attacks on decryption, and off-by-one coding errors in implementations.


How do we find the last two correspondences in an otherwise known even permutation?

All permutations have a cycle decomposition from which you may immediately read off your $P(n-2)$ and $P(n-1)$.  There are trivial algorithms for doing this that run in either $O(n)$ time and $O(n)$ space (invert the permutation), or $O(n^2)$ time and $O(1)$ space (walk backwards by querying everybody repeatedly).

You could adapt that invert the permutation algorithm to use only 1 bit per element, but that's still $O(n)$ space.  Alternatively, if you have an efficient representation for a sparse permutation, then you may replace $n$ by the number of elements actually moved.

In general, inverting a permutation is [exactly] as hard as unordered search.


How to test distribution of a hash function?

Well, for one, SHA-2 (either SHA-256 or SHA-512) doesn't have a 'keyspace'; that's because it doesn't have a key.  SHA-2 takes an arbitrary bitstring is input, and generates an output; while there are limits on how long the bitstring can be, those limits are so huge ($2^{64}-1$ bits for SHA-256, $2^{128}-1$ bits for SHA-512), those limits can in practice be ignored.

With that nit aside, your question is 'given arbitrary inputs (that is, inputs that are not specifically selected with the SHA-2 hash in mind), does the SHA-2 hash functions really generate outputs that are evenly distributed?

To test that, you can use any input distribution that strikes your fancy (as long as inputs aren't repeated; that would bias the statistics, and as long as you're not selecting inputs specifically because of what their SHA-2 hashes are).  You can certainly consider random 512 bit (or whatever size) bit strings, or random 64 character strings.  I would personally advise you to look at "related inputs", that is, inputs that are similar (for example, a 512 bit counter that increments for every hash) -- similar inputs are more likely to stress the SHA-2 function.

Now, one final comment: while you can verify a weakness in SHA-2 with this procedure (although it's extremely unlikely you'll find anything); you cannot verify that SHA-2 is actually well-distributed.  Just because the tests you run cannot find anything doesn't mean that a different set of tests wouldn't.


Can non-assembly crypto libraries truly be secure against timing attacks?

So how secure can non-assembly code truly ever be against timing attacks?

First of all, let me state that this is a tricky subject.

The simplest method is of course to do away with the lookup tables or and other components that are vulnerable to timing attacks. So when a cipher designed, it should require a minimum of vulnerable components. And during execution a minimum of vulnerable constructs should be used to be absolutely secure. For instance AES can be implemented in various ways - some are more secure than others when it comes to side channel attacks. This is all stated by DJB in the paper as well.

It is extremely hard for a native library to control cache timings too. Generally libraries are generally not constructed for a specific CPU. It may be almost impossible to control and measure how the cache handling is performed - or even how much cache is present. So in that sense machine code is (almost) as vulnerable as non-native code.

One way to conquer such complexity is to have a CPU instruction, co-routine or co-processor perform AES. Such an instruction can be designed from the ground up to be invulnerable to timing attacks. If designed well it is completely independent from cache and memory and thus from side channel attacks that rely on them.

The fact that non-native code cannot directly control the instructions and memory addresses doesn't mean it cannot control it at all. Often you can still analyze what happens at a lower level. For instance, an array in Java is not stored in reverse. You know from the specifications that it will be a single, sequential block of data somewhere in memory.

If you are stuck with things like tables then you have various options. You can for instance make sure that an attacker simply does not have enough access to perform an attack. It may be hard for an attacker to put a table on two different pages in memory, for instance.

It may also be hard for an attacker to gain enough timing information. Almost any timing information may be extracted using statistics. But just like brute forcing, it may be that the amount of data required is too high for a practical attack.

Unfortunately this page is not large enough to discuss all measures that can be taken against side channel analysis, and then validate if they are secure for machine code and high level languages. Yes, there are constructs that are valid for both (RSA blinding is probably the most well known one). Is RSA blinding enough to show that code is secure against timing attacks? Probably not.

Note that pretty often the answer to the question is: we haven't tested the code against side channel attacks and hope our algorithms and protocols are secure enough.

One way to battle this in an organization is to buy a HSM (or TLS offloader or other secure system) which should be secure against side channel attacks, basically side stepping the issue completely. These things can be very expensive, but if you require the highest protection against side channel analysis you may have a lot to lose as well.


How difficult is inverting a non-square matrix?

As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses over the complex or real field is that they minimize some second moment error functional, since there is no unique inverse defined.

However, and I may regret this, but there is a recent 2015 conference paper from the Springer Lecture Notes in Electrical Engineering book series (LNEE, volume 339)[behind paywall] which claims to construct such a beast, subject to some strong conditions, but there is no proof of any error minimizing properties for such an inverse, and I'd be really surprised if it results in a meaningful definition of pseudoinverse for lattice based cryptosystems, though it might be worth looking into. A quick look at the paper titles show that this is a very generic and broad conference, not really focused on cryptography, but that may well not be important.


Can any part of AES encrypted blocks be used as PRFed value?

Is it secure if I remove the top-bit of the one block to make it 127-bit?

Yes truncating the output of a PRF produces a new PRF, which can be easily seen by a simple reduction. Assume you had an adversary that could break the truncated PRF, then you would forward all queries to the untruncated PRF and truncate the result (which is a perfect simulation) and output whatever your truncated adversary outputs. This constructed adversary wins whenever the truncated adversary wins.

  AES with 128-bit security is producing 2 AES blocks

This is the tricky part. To compose two PRFs - and AES is assumed to be a PRP which can be used as a PRF if you do less than ~$2^{64}$ invocations - you'll need to ensure that for all possible queries the inputs to both calls are unique. Standard ways to achieve this are to use two different, independent keys for the sub-PRFs or to prepend a unique value, e.g. a single fixed bit which is always 0 for the left and always 1 for the right one.


Answering point 3, no.  Rounding a floating point number just leads to a floating point number.  It just has less significant digits.  So they're still represented as a significand and exponent.  This is a widely accepted format these days.  An integer is a totally different storage method that does not lead to accumulated errors.  They're 100% precise.  The uniform distribution problem is exacerbated by the gargantuan 24 orders of magnitude variance in precision of floating point numbers as:-

Further arithmetic operations on a rounded floating point number will still accrue rounding errors in difficult to predict ways.  And different languages have different types of numbers.  For example Java has different types of numbers compared to  Perl, and those are different to C /C++.  This contributes to the difficulty of  native random floating point number generators.

It's typical to cast a number from one kind to another if you want to change type.


Why ``adversary'' and ``challenger'' and what are typical roles of those?

Suppose you are a member of a mailing list or of an anonymous cryptographic site. Now suppose there is some "new guy" who just joined and makes bold claims about having broken some cryptosystem. Now of course because you don't know anything about the "new guy" you don't believe them. Naturally they're really insistent, so you agree to challenge their claim that the cryptosystem is broken. This makes you, the skeptical person, the challenger.

Of course because the other is trying to break the cryptosystem they're the adversary against which the cryptosystem tries to hold up. Now of course you, the challenger, know that a total and complete break of any cryptosystem (e.g. ciphertext-only attack) is an unrealistic capture of the reality, so you agree to provide the adversary with some ressources, e.g. answering requests for encryptions.

So in a sense security games are protocols that allow adversaries to convince challengers that they broke a security property in the most reproducible and convincing way (e.g. because the adversary clearly at no point has access to the key).


With AES CTR mode, using the same key and nonce to encrypt multiple blocks of data is a huge security breach:

Ciphertext1 = Plaintext1 XOR Key
Ciphertext2 = Plaintext2 XOR Key

XORing the ciphertexts:

Ciphertext1 XOR Ciphertext2 = Plaintext1 XOR Key XOR Plaintext2 XOR Key

This simplifies to

Plaintext1 XOR Plaintext2

This means that if you knew that the first message of the day (plaintext1) was going to be "weather report" then you could work out what the first 14 bytes of ciphertext2 is, because you could XOR "weather report" with the first 14 bytes of ciphertext1, get the first 14 bytes of the key, and them use this to decrypt the first 14 bytes of ciphertext2, and get the first 14 bytes of plaintext2. Other techniques such as what kelalaka suggested can be used to work out the whole message.

The solution: either encrypt the whole lot of data with the key and nonce, or change the nonce per block of data encrypted - maybe use a counter, because the nonce does not have to be unpredictable, but must be unique.


If you are afraid that somebody can get access to your private keys or passwords, disconnect your machine from network and never connect it again; transfer public keys that you want to publish via USB stick; when you need to encrypt or decrypt something, use USB stick, put there the needed files, attach it to your offline machine, encrypt or decrypt on this machine, put result back to USB stick.

Depending on how important are purposes you use openssl for, you may want to put your machine in some room with proper electromagnetic and sound isolation :) And first of all, make sure nobody gets physical access to this machine :)


Windows 8/Server 2012: Passes FIPS-140-2 despite failing AES-GCM for IV != 96 bits long?

The answer is, yes, you can get FIPS certification even if you don't implement every approved cryptographical primitive, or if you don't implement every possible option of those primitives.

When you undergo FIPS testing, they ask you to fill out an "information form" that asks for the details of what cryptography you claim to implement.  These includes questions about which primitives you implement (e.g. whether you do GCM or not).  If you do claim to support GCM, you then have to claim what portions of GCM you implement.  For example, you can claim to support GCM encryption but not decryption, or support 128 bit and 256 bit keys, but not 192 bits (for example).  As for the IV, you can claim support for 96 bits, or you can claim support for a range of IV sizes (anywhere between 0 and 1024 bits, multiples of 8 please).

Hence, when Microsoft applied for FIPS validation of their component, they claimed support for only 96 bit IVs.

However, that's not immediately obvious from the summary that NIST lists in the certificate listing (which is copied directly from the Information Form, and lists exactly what restrictions the certified implementation has).  For this implementation, they list under GCM:

  IV Lengths Tested: ( 8 , 1024 )

which would, to a naive reader, appear to state that Microsoft claimed support for IV's of length in the range 8 to 1024, and that NIST tested them, however, that's not the case.  NIST has a separate flag 'OtherIVLen_Supported'; unless that is claimed, you really get support only for 96 bits.  That flag is not mentioned under the Microsoft entry, hence Microsoft doesn't claim to support those IV lengths.

Exactly how NIST expects you to know this (if you're not familiar with the internals of the NIST information form), I have no idea.  The OtherIVLen_Supported flag is not even mentioned in the 'Legend for Description Field' header.


Are there any crypography schemes which rely on Graph Isomorphism not being in P?

There is an elegant example of zero knowledge proof for graph isomorphism. The prover sends a randomly relabled graph and the verifier requests mapping to one of the originals. It is a very simple to understand and prove zero knowledge proof. However I don't believe anyone ever used this for authentication or such.
Obviously we now know graph isomorphism isn't hard after all making all these not very useful.


How can an all-zero encryption key result in plaintext ?

If the key and nonce are identical then it is possible to recreate the counter mode key stream. WPA2 is using CCM, which uses counter (CTR) mode underneath. This basically generates a key stream which is XOR'ed with the plaintext message. If you have more messages then it becomes easy to retrieve messages by XOR'ing multiple streams together.

If the key is an all zero key then all the adversary has to do is to decrypt the ciphertext of course. Once you have the key then all the security is lost. However, the ciphertext will still not be the same as the plaintext, so what Wireshark is showing in the video must be the decrypted ciphertext.

In other words, the explanation is slightly over-simplified in my opinion.