are outputs of sha256 independent when padded with different seed each time, in other words, when inputs can be somewhat related

You are making a domain seperation with a prefix, and that is very common in random oracles (RO) instead of initiating another RO, one can use domain separation to use only one RO. Since the RO are like hash functions the same idea is used in the hash functions, too. That is the correct term and the correct way.
We expect that SHA256 outputs are indistinguishable from uniformly random.
Also, we expect that SHA256 ( like any cryptographic hash functions) has the avalanche effect;

a one-bit change in the input bits flips each output bit with a 50% probability. So some bits flip some bits doesn't.

If hash values with the prefixes are not independent there will be lots of problems for the used hash function. Also, consider that due to the padding, there are already lots of similar parts at the end of each message that didn't cause dependency.
One might note that SHA256 is vulnerable to length extension attack ( not only SHA256 though), but this may also be a problem for your scheme or not. Assume you have $h= \operatorname{SHA256}(12\mathbin\|234)$ then the attacker can use the output hash $h$ as the initial value for $\operatorname{SHA256'}(h,\text{extension})$ where this function controls the initial values of SHA256, then they can extend the message with a different hash value without knowing the prefix or the message. If $h= \operatorname{SHA256}(\text{prefix}\mathbin\|234)$ is used for MAC, although the attacker cannot produce the same output for the extended message, they can inject the extended message to execute a forgery.


Informally, you can think of the embedding degree as the smallest integer $k$ that lets you transform or embed an instance of the elliptic curve discrete logarithm problem (ECDLP) over an elliptic $E(\mathbb{F}_p)$ into an instance of the discrete log problem (DLP) over the field $\mathbb{F}_{p^k}$.

Answering the specific question: we have an elliptic curve over a finite field $E(\mathbb{F}_p)$, where $\log(p) = 512$. There is a subgroup with order $\log(q) = 160$ bits. Finally, there is a transformation from the elliptic curve to $\mathbb{F}_{p^2}$, where $p^2$ has $\log p^2 = 1024$ bits. (The exponent "$2$" here is the embedding degree.)

Recall that the fastest algorithms known for solving the ECDLP are of order $O(\sqrt{p})$ steps for the ECDLP over $E(\mathbb{F}_p)$, whereas the DLP can be solved in subexponential time using, say, the index calculus. This transformation opens up the solution of the ECDLP to techniques from DLP, depending on the curve you choose.

Generally speaking, you want $k$ to be large to resist faster solution via transformation to the DLP.

I'm leaving out heavier details because the OP was new to ECC, but to be more precise, if you have a curve $E(\mathbb{F}_p)$, and one point in $E(\mathbb{F}_p)$ has order $q$ where $q \neq p$ is a prime, then the embedding degree with respect to $q$ is the smallest value $k$ such that $q | p^k - 1$, or $p^k \equiv 1 \bmod q$, assuming $p \not\equiv 1 \bmod q$.

I also left out that the Weil pairing does the embedding, and is used in the MOV algorithm. A similar attack is the Frey-Rück attack carried out using Tate pairings.


public key cryptography and digital signature

This text tries to explain how digital signatures work, but it actually is a bit misguiding.

It explains digital signatures based on public-key encryption schemes, but this is only valid for schemes like RSA. And even here, you don't simply encrypt some message with your private key to sign it, but you apply the "decryption" operation (i.e. exponentiation with the private key) on a hash of a message, suitably padded.

In RSA, you have a key pair consisting of private key $(n, d)$ and public key $(n, e)$, where $n$, $d$ are quite big numbers (the size of $n$ relates to the security of the scheme), $e$ usually a smaller number like $2^{16}+1$.

In the "textbook version" (without any padding/hashing), to sign a message $M \leq n$, you calculate $s := M^d \bmod n$, where $\bmod$ is the integer remainder operator. The pair $(M, s)$ is then the signed message.
To verify the signature, anyone can calculate $M' := s^e \bmod n$ and then check if $M \mathrel{\overset?=} M'$. Here signing looks like RSA-encrypting with the private key and verifying looks like RSA-decrypting with the public key, which is the reason that the article tries to show it as such.

The real RSA-based signature schemes work a bit different: We apply a one-way hash function $H$ and a semi-random padding $P$ on the message before the exponentiation, so the signature is $s := P(H(M))^d \bmod n$, and this can be checked as $P^{-1}(s^e \bmod n) \mathrel{\overset?=} H(M)$ (where $P^{-1}$ also checks if the padding was really correct). This hashing and padding actually makes the scheme secure against forgeries (and it also allows to sign messages longer than $n$).

There are other signature schemes which do not relate directly to an encryption scheme, for example DSA.

To use a digital signature for authentication (or "identity verification", as the article says), you normally don't sign an arbitrary message, but you sign a piece of data which is somehow relevant to the protocol. For example, in the SSH protocol, at the end of a Diffie-Hellman key exchange, the server signs about everything important which was exchanged, to make sure that there was no man-in-the-middle attack which modified the exchanged data.


How does the GCM encryption limit affect TLS connections?

Actually, that limit does not affect TLS.

TLS encrypts each record separately, using a fresh IV for each.  A record is limited to 16kbytes in length, and hence you'll never hit the 64Gbyte limit in TLS.  In other words, you'll use a fresh IV after every 16kbytes (and possibly earlier).


Is this cascading encryption, and is my security weakened as a result?

I would not consider your case to be a cascading encryption. The reason why is the fact you need multiple interventions before getting access to your file.

Here is what I would consider a cascading encryption (let's go crazy) :
$$E(k_1,k_2,k_3,m) = \text{KEYAK}(k_1,\text{NORX}(k_2,\text{AES}(k_3,m)))$$
which you would decipher with :
$$E^{-1}(k_1,k_2,k_3,m) = \text{AES}^{-1}(k_3,\text{NORX}^{-1}(k_2,\text{KEYAK}^{-1}(k_1,m)))$$
All operations are done in a single go. One should not need to enter keys one after the other.

Considering your questions now.

As long as you use AES (supposed in the good mode of operation: i.e. not ECB) and under the assumption (3.) your files should be secure as long as the key is not leaked.

In the case of GPG, I suppose you meant to use it in a asymmetric mode (the symmetric case fall under the previous assumption are it will generally use AES).
For larges files GPG generally generate a random decryption key $K_D$, encrypt the files with AES and this key $K_D$, encrypt $K_D$ with the public key, therefore we are sort of back to point (1.) but with a asymmetric key.
I suppose your file to be already encrypted. If your disk image is encrypted therefore yes it will be more secure as just finding the file : you need to decipher the disk before getting access to the file... However, if your file is encrypted with the same algorithm as the one used to encrypt your file. If the first one is broken, expect the second to be the same (meet-in-the-middle... ).
Same idea as in 2...

However what you should really consider is the fact that nowadays cryptography does not work that way. Assuming that the attacker has only access to the cipher text is assuming a very weak attacker.

Academics assume strong attackers : he has control over the plaintext, ciphertext and can ask for any part to be encrypted / decrypted. The only thing he does not have access is the key. The goal here is to retrieve the key. This is usually illustrated by the lunchtime attack.


Why is low-degree polynomial preferred on Ring-LWE based somewhat homomorphic encryption?

The ciphertexts contains a certain amount of noise for security reasons. The downside is that if this noise is too big, the decryption will fail. When using homomorphic operations, the noise contained in the output ciphertext will be bigger than the one in the input ciphertexts.

Now when adding ciphertexts, the new noise is just the sum of previous noises, but when doing multiplication, the noise grows faster, and ultimately, only knowing the number of multiplication you're doing is a good approximation to know how to set your parameters.

This is why you prefer low degree polynomials to high degree polynomials, to avoid the noise growing too large.

Second question would be why do we do polynomials? Well, basic operations here are just additions and multiplications, which gives only polynomials - but it can represent any function so it's ok!


How is it possible to trust a public key that can confirm a message's signature?

I am not commenting for what purpose your are going to use public key and answer your main question:

  How is it possible to trust a public key ...?

This one of the most important questions in cryptography: key distribution. Here are some possible solutions:

You can for instance meet Alice and exchange keys personally (but it is applicable in rare real cases).
Or you can use some channel that you trust to exchange keys.
Or you use PKI. Namely some certification authority issues a certificate confirming that the public key belongs to a particular person. The advantage is, that you can exchange certificates also via insecure channel. But to use PKI you need of course trust particular certification authority.


Session-specific Symmetric Key Derivation Using SHA256

HMAC: The hmac version is considered slightly more secure than sha-256, assuming it's also based on SHA-256, because the HMAC formulation folds in the key material with 2 rounds of hashing, making it harder to use a chosen plaintext attack on the digest.

SHA-256: SHA-256 should be relatively secure against chosen plaintext attacks, but it's better to be safe than sorry.

You can also achieve a higher level of assurance and forward security provided $K$ is not long-lived, but rather is chained to the immediately previous session.

For some stored value D1:

K2 = HMAC(Nonce,D1)     // session key
D2 = HMAC(Nonce,K2)     // stored material for a future session
authtoken = E(K2,Nonce) // auth token proving client derived K2 correctly

If you want to authenticate the server, you can also pass a token from server to client, thus proving the server knows D1.  Something like,

servtoken = E(K2,authtoken)   // proof server knows D1

Client checks servtoken before sending authtoken.  D1 is discarded and replaced with D2. So you have bidirectional authentication and forward security.


Is there a signature scheme for the Cramer-Shoup cryptosystem?

It is very bad practice to use the same private key for two different schemes. In some cases this is secure but you need to explicitly prove it. One example of this can be seen here: http://www.pinkas.net/PAPERS/combined.ps.

My suggestion is to take the Cramer-Shoup group and to define a separate key pair for DSA or Schnorr signatures. You can use the generator g_1 and this will be fine (the group can be the same; it's just the key that has to be different).


Asymmetric password encryption - Viable? Which algorithm?

This seems OK assuming you can trust the authentication servers to leak neither the private key nor the deciphered passwords; and, if you use RSA, assuming you use a standard encryption padding with randomization, e.g. one of the two RSAES schemes in PKCS#1.

Elgamal indeed can give you shorter cryptograms, which might be desirable in the context (an Elgamal cryptogram consists of two group elements; thus when the group is a 256-bit elliptic curve, you get security arguably better than 3048-bit RSA for 17% of the size of each asymmetric cryptogram).

But if ciphertext size is an issue, you can use hybrid encryption which gives you minimal ciphertext expansion, and can reduce the cost of deciphering one more password. That's by enciphering all passwords using a symmetric scheme (e.g. AES GCM, which also gives integrity) using the same random key, itself enciphered with an asymmetric scheme. As an additional (marginal) benefit, each server can have its own private key with minimal ciphertext expansion.
Each server needs to store only a single RSA cryptogram (or whatever asymmetric cryptosystem is used), which holds the symmetric key allowing to decipher any password.

None of this will survive compromise of a server, unless everything sensitive (including RADIUS/CHAP) is in a separate trusted environment, such as an HSM or Smart Card.


If I run this encryption twice with the same message but different $r$ (due to nonce behavior), will I get the same $c$?

No.

Lets split this question into the two elements of $c = (c_1, c_2)$ where $c_1 = P(k,r)$ and $c_2 = G(r) ⊕ m$. Then lets start with $c_2$ where the message is actually "encrypted".

A good PRF will return a stream of bits indistinguishable from random. It should be a different stream each time the seed is different. However, two random streams will still have approximately half the bits identical, purely because of chance.

So lets minimize the size of $m$ to a single bit, and set $m$ to zero. The resulting stream of bits may start with a zero or one for $r=x$ or $r=y$ with $x \neq y$ . Say that they both start with $0$ or $1$ then the result of $c_2 = G(r) ⊕ m$ will be $0$ or $1$ as well.

Of course the chance that $c_2=c_2'$ is reduced by 50% for each bit added to $m$. But $c_2$ can be identical for the right combination of nonces.

The fact that $c$ consists of the permuted nonce as well confuses the matter. The $c_1$ will always be different because $P(k, r)$ will always be different - it is a permutation after all. This has however nothing to do with the message $m$ or the security of the scheme.

However, it does mean that the only answer possible is no given your scheme; if $c_1$ is never the same then $c$ is obviously never the same as well, even though $c_2$ is not affected.

Note that $G(r)$ can only be secure if $r$ behaves as a secret, i.e. has enough entropy. The size of $r$ is maximized by the size of the PRP. Basically this scheme is a stream cipher if and only if $r$ contains enough entropy. In that case $P(k, r)$ will be a form of key wrapping.


So if I want to implement a MAC function Can i just do the first method ?? just pad the message with key and do the hash ?

Yes, $mac = \text{SHA3}(k||m)$ is a secure MAC if $k$ is a fixed-length key. This is an explicit design goal of SHA3.

You can also rely on HMAC or KMAC instantiated with SHA3. These will also give you secure MACs but the added complexity is not necessary.


Solve a system of non linear equations over GF

There have been extensive comments by the OP on this question as well as a related one and its answers and the consensus
don't seem to be converging at all to anything sensible.

  Broadly speaking, the field in which we are operating influences
  the answer to the question of whether a system of equations has
  solutions or not to some extent, but not in the ways that the OP
  thinks it does. Whether we are operating in a prime field or an
  extension of a prime field (what the OP calls gf or GF) has relatively
  little to do with the matter. In particular, for linear equations,
  the general theory of linear equations over a field
  usually has more to say about the matter than the identity of the
  field.

As Henrick Hellström has pointed out in a comment on the question,
the first set of equations in the OP's question can be converted
into a pair of linear equations in the unknowns $x_0$ and $y_0$,
say
$$\begin{align} a_{11}x_0 + a_{12}y_0 &= b_1\\
a_{21}x_0 + a_{22}y_0 &= b_2\end{align}$$
where the $a_{ij}$ and the $b_k$ are functions of
the known quantities $M_1, M_2, x_1, y_1, x_2, y_2$.
I refuse to calculate and state explicitly what the $a_{ij}$
and the $b_k$ are in terms of the known quantities. I will
differ from Henrick slightly, though, in that I do not think
that these equations are solvable for each and every choice of
$M_1, M_2, x_1, y_1, x_2, y_2$. This has nothing to do with
whether these quantities belong to GF$(2^m)$ or GF$(p^m)$ for
$p > 2$ or GF$(p)$ and everything to do with basic linear
equation theory: the matrix might be singular
for some choices of $M_1, M_2, x_1, y_1, x_2, y_2$ in which
case we get multiple solutions rather than a unique solution,
or the matrix might be singular and the equations might be
 inconsistent in which case no solution exists.

All this, however, as well as the OP's questions about other
equations is irrelevant in the context of Shamir's secret
sharing scheme which is referenced in the
other question
but not in this one but which I believe is the reason for
these questions.

If someone chose three distinct $x_0, x_1, x_2$, as well
as $y_0, y_1, y_2$, then computed $M_1$, $M_2$, and finally
revealed $M_1, M_2, x_1, y_1, x_2, y_2$, but not $x_0, y_0$
to us, then we can find $x_0$ and $y_0$ from the given
relationships, and inconsistency is not an issue.  Note the
requirement that $x_0, x_1, x_2$ be distinct which allows
the unnamed someone to avoid the heartbreak of
division by $0$ when computing $M_1$ and $M_2$.

Similar remarks apply to the nonlinear equations in the
OP's question as well.


(added) Disclaimer: in the years since 2011 browsers have closed the holes that allowed sending a fully-chosen first block plus practically all TLS stacks now do 1/n splitting for TLS1.0 CBC providing defense in depth. And many servers no longer allow TLS1.0 at all (particularly those subject to PCI-DSS). So this A and Q are mainly of historical interest.

Actually that example is wrong, because it counts \r and \n each as two bytes instead of the single byte each actually represents. Also it uses DES as the block cipher, which has been broken and obsolete since the late 1990s.

However, if we ignore those minor errors, in the very next paragraphs that article does correctly explain the principle (graphics simplified to what I can do in SX):

  .... On the other hand, if he can inject packets, he can make modifications to the request as well. Lets say he did this:
  GET /ind | ex.jsp H | ... | ession=1 | 2345678
  Here, I've removed one character from the page being requested to the completely innocent-looking index.jsp, but I've also split the victim block across an 8-byte boundary. Now, if I want to find the first digit of the session ID, I only need a maximum of 10 guesses:
  ession=0
  ession=1

Notice the latter is a result of the former; making the URL one character shorter caused a subsequent block to contain known text ession= (we know the server uses cookie name Session and the secret is the value) plus only one unknown character from the beginning of the value, so we only need to try a small number of possible guess blocks.

  ... Now, armed with the first digit, I can alter the request again:
  GET /ind | ex.js HT | ... | ssion=12 | 345678
  And make up to 10 guesses:
  ssion=10
  ssion=11
  ssion=12

Again by changing the URL we caused a block to contain known text ession=1 and a single unknown character (the second), making it easy to guess. Repeat as needed.

If index.js or even index.j causes a server error and attracts attention, as it might, it is easy to choose other URLs that are the correct length (modulo 8 for DES/3DES/IDEA or 16 for AES/Camellia) like query.cgi?search=able query.cgi?search=baker query.cgi?search=chubby

poncho's answer in the question you link says the same thing, except he calls it 'maneuver[ing] the cookie' into the desired position just before a block boundary and then 'remaneuver[ing]'.


Idea for secure password hash-likes, is this feasible/usable/workable?

I don't see anything horribly wrong with your proposal.  On the other hand, the obvious question would be "what advantage would this approach have over, say, PBKDF2 with a good salt"?

In your proposal, it is infeasible to recover the password from the hash (short of brute-force); that's also true of PBKDF2.
In your proposal, the hash is randomized (and so the same password doesn't always result in the same hash); that's also true of PBKDF2.

In addition, in your proposal, generating a hash is moderately expensive (it isn't cheap to find large random primes); with PBKDF2, it's no more expensive than validating a password.  I can't see any reason why you'd want to make generating a hash an expensive operation.

Given that this proposal doesn't appear to have an advantage over well-accepted techniques, I can't recommend it.


Well, one way to look at this is to notice that, if the feedback polynomial is prime, then the result of starting with state $E$, and then stepping the LFSR forward $N$ steps is the value $2^N \cdot E$, where we do the computation in $GF(2^K)$, using the polynomial representation (with the feedback polynomial being the polynomial).  In addition, I believe that if the feedback polynomial is not prime, then it is possible to factor that polynomial into its primes, solve the equivalent solution modulo each prime factor, and then recombine them.

So, the solving the problem of finding $N$ is equivalent to solving $S = 2^N \cdot E$ in $GF(2^K)$, or in other words, $S/E = 2^N$; that is, this problem can be reduced to solving a discrete log problem in $GF(2^K)$.

What does that rewording of the problem buy us?  Well, it turns out that there are recent results in this area; this paper shows us how this problem can be solved in "quasi-polynomial" time (by which they mean $K^{O(\log K)}$; technically supra-polynomial, but just barely); that paper tells us how to do discrete logs quickly over fields of small characteristic, and a characteristic of 2 is as small as it gets.


How to get a speedup linear in the number of iterations on unsalted iterated password hashing?

The only way I see to justify the claim is that the authors are thinking as follows thus it is not for any $P'\neq P,$ but specific $P'$ in that trail:

Compute $H^i(P),$ for $i=1,2,\ldots,k.$ This gives you the hash for $P,$ call it $H_0.$

Now define the sequence $P'_i=H^i(P),$ for $i\geq 1,2,3,\ldots.$

Evaluate $H^i(H_0)$ to obtain $H(P'_i),$ for $i\geq 1,2,3,\ldots,$ at extra cost of one evaluation each. Of course these $P_i'$ are almost certainly distinct until the trail length is comparable to square root of the hash output space.


AES storing the length within the encrypted data versus storing it outside

First, the advice:

  What are the best-practices to store the message length / strip away padding?

Use standard padding, like PKCS#7 padding. It handles finding the length uniquely for you.
Use encrypt-then-MAC to prevent padding oracle attacks.

(Or better yet, don't use CBC. Use an authenticated encryption mode like GCM, or use CTR+MAC which doesn't require padding.)

  My concern with Option 1 is that you're giving away information for free: is there a way in which a potential attacker might be able to utilize the length of the data in attempting to compromise the message?

Maybe not, since the length in number of blocks is known anyway. However, in some cases it would be a problem, like if the attacker was expecting either 'no' or 'yes' as the message. It depends on your messages. You likely shouldn't rely on it remaining secret, though.

  My concern with Option 2 is that a potential attacker (after determining by decompiling source code that the first 4 bytes indicate length) might try a brute-force approach, only needing to go through a much smaller part of the data for each potential key to determine if the message for that particular key is valid; i.e. that he only has to try one block or only the first 4 bytes of the message until he ends up with a block for which the first 4 bytes are relatively close to the size of the payload (hence effectively reducing the amount of time it would take to determine the message's key)

This one is not a valid concern. AES has 128+ bit keys so a brute force attack is impossible. Whether they have to test one or several blocks for each key does not matter. Even if AES was broken somehow, such a small factor shouldn't matter, and the attacker could likely guess some other details about the message instead to gain a similar advantage (like all-ASCII for a certain part of it).


Does a conditional statement depending on a round number introduce timing attack problems?

Unless the number of rounds is secret, this does indeed not represent a secret-dependent branch.

(If the number of rounds is secret, a chap named Auguste would like to have a word with you.  Hope you speak French or Dutch as they were spoken a century ago.)


AES: Is it safe to encrypt same cleartext with same key but with million diferent IV?

No, for the same reason that you can't crack 1.3 million ciphertexts knowing they use the same key but different plaintext.

As long as the CSPRNG you use to get your IVs is strong, you're safe.

You are correct in that decrypting the first block without the right IV is not possible. If it were, we wouldn't be using CBC. But yeah, if he could somehow guess the right IV and key for a certain block, he'd be able to decrypt all the following.

For situation 2 take a look at this question.


How is asymmetric cryptography safe if one of the keys is public?

How is asymmetric cryptography safe under these conditions?

Well, you sort of outlined (but see kelalaka's corrections) how you would use asymmetric crypto to do authentication; that is, to make sure that the message was actually sent from $A$.

You ask "how does that provide privacy?".  The answer, of course, is "if that's all you do, it doesn't".

If we want to do privacy, that is, generate an encrypted message that only $B$ can read is that $A$ encrypts $m$ with $B$'s public key, that is, $E(m, p_B) = m_A$.  We then send $m_A$ to $B$.  $B$ can then take his private key and compute $D(m_A, k_B) = m$, recovering the original message.  No one else can read the message, because only $B$ knows $k_B$, and that's needed to decrypt the message.

Two notes:

If we need to provide both authentication (only $A$ could have generated the message) and privacy (only $B$ could read the message), we do both; $A$ might generate the ciphertext $E(m, p_B) = m_A$, and then sign it with his private key $Sign( m_A, k_A ) = s_A$ and then send both $m_A$ and $s_A$.  $B$ can then verify the signature (with $A$'s public key), and then decrypt the message (with $B$'s private key).
In practice, if we need to encrypt a long message, what we generally do is pick a random symmetric key (which is short), and use the public key encryption to encrypt the key, and then use the symmetric key to encrypt the message.  Symmetric encryption is far more efficient than public key crypto, and so this is a significant performance gain over using the public key encryption method multiple times to encrypt the message.


Generating nicer diceware passwords without losing entropy

To get "nicer" passwords, whatever that means, the suggestions are typically:

  …

  use a selection method but be aware you lose entropy (e.g. pick $1$ out of $16$ passwords at the cost of $4$ bits of entropy)

What you are doing is effectively ‘a selection method’ (more commonly known in the literature as rejection sampling) with a bound on the number of rejections.  For your method to work, you need (say) a word list 16 times the size of a word list for standard (no-rejection) diceware in order to attain the same entropy while giving the user 16 distinct choices for each word position.

  1 - Am I correct that generating a password in this fashion does not decrease entropy?

Provided each of your 16 word lists has the same number of distinct words, you are correct that this does not decrease entropy vs. doing standard (no-rejection) diceware on one word list.

  2 - What is the impact of overlaps between lists when $N > 2$?

As far as the probabilities are concerned, nothing, provided (a) each word list has the same number of distinct words, and (b) you always accept exactly one of the 16 options presented.  As far as the user is concerned, they may be presented with the same objectionable word twice for one position.

  3 - Why is nobody doing this? This is easy enough to automate. Unless something above is wrong?

How do you decide how to partition the word lists?

If you have a 16x word list, you could just do rejection sampling on that word list and as long as you reject on average fewer than 16 words per position in the pass phrase, you get the same security with less user interface complexity.  For example, you could draw 16 words independently from your 16x word list, and ask the user to pick exactly one of them.

Exercise: Find the probability distribution on what you get by selecting 1 of 16 choices drawn without replacement for each word position.  (Independent samples as in the previous paragraph, in contrast, are ‘with replacement’.)  This avoids partitioning the word list.


Automatic generation of secure passwords with the least inconvenience for a user

The entropy of a random password is given by the formula:

$H = log_2 N^L = L\log_2 N$

where $N$ is the number of possible symbols, and $L$ is the length of the password. Since you want to know the minimum length to achieve a determined level of security, then the answer to your question is $L = \lceil \frac{H}{log_2 N} \rceil$.

In your case, $N=20$, and your desired entropy $H$ depends on the requirements of your system. RFC 4086 gives some guidelines about it. Let us assume you want to have only a one in a million chance of a password being guessed, then you need at least 39 bits of randomnes, so $H = 39$. Then $L = \lceil \frac{H}{log_2 N} \rceil = \lceil 9.02 \rceil = 10 $, so you need at least 10 characters.
Of course, if you want to achieve more bits of randomness, then the length will increase. For instance, for 128 bits, you need at least 30 characters.

Note: All this info comes from Wikipedia


Is it possible to hand-negotiate an SSL/TLS session?

No, this is not possible, even if you copy & paste data to/from another program. The reason is that SSL is a binary protocol, and telnet won't pass through arbitrary binary data. Moreover, upon connection, it does some protocol negotiation, and this is probably the reason for connection reset.

There are programs, like openssl s_client, which set up SSL connection for you and let you type the data by hand. For example, you can use it to connect to a HTTPS server and type the request manually, as you do with HTTP and telnet.


How could you find the preimage of an isogeny function?

Isogenies are always surjective, but there's a nuance. They are surjective over the algebraic closure. The correct statement would be "for every $\mathbb{F}_{17}$-point on the green curve there are three $\bar{\mathbb{F}}_{17}$-points on the blue curve which map to it".

To find the preimages of a point, write down a polynomial system and find its solutions. A computer algebra system (e.g., SageMath) may help. The number of solutions is obviously related to the degree of the polynomial system.


I just tried this tool to no avail

https://www.onlinehashcrack.com/hash-generator.php#res

My best guess is that the program is actually doing more than a simple hash, it may be a number of hash rounds or some other manipulations

You said that changing the plaintext makes the hash change. So you have a program which performs such unknown hash. Decompile it and work out the process behind. The algorithm is not "secret", it's stored in the executable


Any way to prove possession of a RSA 2048 private key using 256 bit?

Is there a way how Alice can proof to Bob that she is in possession of the private key?

Here is one possible way:
Bob selects a random 2048 bit value $m < n$ and computes $m^e \bmod n$ and sends that and $\text{SHA3_256}(m )$ to Alice.
Alice, with the private key, recovers $m$, and verifies that $\text{SHA3_256}(m)$ matches the value she received from Bob.  If so, she computes and sends $\text{SHA3_256}(m || m)$; that's 256 bits.
Bob compares that with the hash of the duplicated value he originally selected; if they match, then either Alice was improbably lucky, or she really does have the private key.
Bob cannot use this protocol as an Oracle to compute the hashes of RSA decryptions, because he would need to already know the hash of the plaintext.


Parallelization of CFB mode encryption and decryption

I've been thinking a little bit about it, and now I think it is possible, but you have to consider the generalization of CFB in ISO 10116 (I don't have access to the ISO 10116 standard, so I will assume that the description by Rogaway is correct).

The generalization of CFB from the ISO standard seems to have two main changes:

The feedback block (FB), of size $r$, can be longer than the input block (IB), of size $n$. The IB is constructed with the left $n$ bits of the FB.
A new parameter $k$ specifies how much the previous feedback block is shifted to the left on each step.

For each new plaintext block, the feedback block (FB) will be made of three parts:

The least significant $r - k$ bits of the previous FB
A sequence of one bits, of size $k - s$
The previous ciphertext bits, of size $s$

We are used to the case where $r = n$ and $k = s$ (e.g., the NIST 800-38A specification), so there is no sequence of one bits. However, when $r\ge n+s $, the input block for the block cipher will only take bits from the previous FB and one-bits, and not from the previous ciphertext bits since it only takes the left $n$ bits from the FB. This way you could partially parallelize the encryption operation.

A very illustrative way to understand why this allows some parallelization is to imagine a very very long feedback block, much greater than the input block. If you append the previous ciphertext to the right of the FB, shift the FB just a little to the left and take the left part of the resulting FB as your new IB, then the ciphertext will not take part of the new IB, at least for some rounds. These rounds are then parallelizable. Adjusting parameters $k$ and $r$ allow to precisely define the parallelization factor.


When using symmetric encryption is it important to compress the data first?

No, not really (unless you're concerned with bandwidth usage).  On the other hand, compressing the message can leak data (for example, how compressible the data is).

  Could it be the case for some ciphers but not for others?

No, or at least, not for any cipher that we would consider secure.  If there is a cipher that is marginal enough for this to matter, we would consider that cipher to be insecure (and ought to be replaced by something where this doesn't matter).

It might be of some marginal help if the key is weak.  For example, if the key is based on a guessable password, compressing the plaintext might make it marginally more difficult (because, to test a trial password, the attacker would need to decrypt slightly more before being able to check to see if the decryption is plausible).  On the other hand, if you were close enough to the margin where this matters, you're in danger anyways.


Wrong Test Vector for HKDF with HMAC-SHA256

This hastily written implementation of HKDF in C# agrees with the RFC test vectors:

    private const int SHA1 = 1;
    private const int SHA256 = 2;

    private static HMAC NewHMAC(int h, byte[] key)
    {
            switch (h) {
            case SHA1:
                    return new HMACSHA1(key);
            case SHA256:
                    return new HMACSHA256(key);
            default:
                    throw new Exception("NYI");
            }
    }

    private static byte[] HKDFExtract(int h,
            byte[] salt, byte[] ikm)
    {
            using (HMAC hm = NewHMAC(h, salt)) {
                    return hm.ComputeHash(ikm);
            }
    }

    private static byte[] HKDFExpand(int h,
            byte[] prk, byte[] info, int len)
    {
            using (HMAC hm = NewHMAC(h, prk)) {
                    MemoryStream ms = new MemoryStream();
                    byte[] T = new byte[0];
                    int j = 0;
                    while (len > 0) {
                            byte[] buf = new byte[T.Length + info.Length + 1];
                            Array.Copy(T, 0, buf, 0, T.Length);
                            Array.Copy(info, 0, buf, T.Length, info.Length);
                            buf[buf.Length - 1] = (byte)(++ j);
                            T = hm.ComputeHash(buf);
                            int clen = Math.Min(T.Length, len);
                            ms.Write(T, 0, clen);
                            len -= clen;
                    }
                    return ms.ToArray();
            }
    }

Feel free to reuse and modify it at will, in order to print intermediate values, to pinpoint the location at which your implementation diverges. Like @Andrey, I find it plausible that your code gets it wrong when applying HMAC with a key larger than the underlying hash function block size (which is 64 bytes for both SHA-1 and SHA-256): in such a case, the key should first be hashed alone, and the hash result (20 or 32 bytes, for SHA-1 and SHA-256, respectively) is then used as the actual HMAC key.

Thus, you may want to compare your HMAC implementation with the test vectors from RFC 4231, especially the last two, which exercise the "key larger than block" situation.


NIST's Recommendations for Protection of CLASSIFIED Data?

Suite B has been revised in the light of development of quantum algorithms. Some modifications to ECC standards was in response to the scandal of an apparent weak elliptic curve in the previous standard.

From the NSA IAD website:

  Commercial National Security Algorithm Suite

  The Commercial National Security Algorithm Suite (CNSA Suite) will
  provide new algorithms for those customers who are looking for
  mitigations to perform, replacing the current Suite B algorithms.

  [..]

  Currently, Suite B cryptographic algorithms are specified by the
  National Institute of Standards and Technology (NIST) and are used by
  NSA's Information Assurance Directorate in solutions approved for
  protecting classified and unclassified National Security Systems
  (NSS). Below, we announce preliminary plans for transitioning to
  quantum resistant algorithms.

  Background

  IAD will initiate a transition to quantum resistant algorithms in the
  not too distant future. Based on experience in deploying Suite B, we
  have determined to start planning and communicating early about the
  upcoming transition to quantum resistant algorithms. Our ultimate goal
  is to provide cost effective security against a potential quantum
  computer.  We are working with partners across the USG, vendors, and
  standards bodies to ensure there is a clear plan for getting a new
  suite of algorithms that are developed in an open and transparent
  manner that will form the foundation of our next Suite of
  cryptographic algorithms.

  Until this new suite is developed and products are available
  implementing the quantum resistant suite, we will rely on current
  algorithms. For those partners and vendors that have not yet made the
  transition to Suite B elliptic curve algorithms, we recommend not
  making a significant expenditure to do so at this point but instead to
  prepare for the upcoming quantum resistant algorithm transition.

  For those vendors and partners that have already transitioned to Suite
  B, we recognize that this took a great deal of effort on your part,
  and we thank you for your efforts. We look forward to your continued
  support as we work together to improve information security for
  National Security customers against the threat of a quantum computer
  being developed. Unfortunately, the growth of elliptic curve use has
  bumped up against the fact of continued progress in the research on
  quantum computing, which has made it clear that elliptic curve
  cryptography is not the long term solution many once hoped it would
  be.  Thus, we have been obligated to update our strategy.

  It is important to note that we aren't asking vendors to stop
  implementing the Suite B algorithms and we aren't asking our national
  security customers to stop using these algorithms.  Rather, we want to
  give more flexibility to vendors and our customers in the present as
  we prepare for a quantum safe future. Where elliptic curve protocols
  are to be used, we prefer Suite B standards be used to the fullest
  extent possible as they have a long history of security evaluation and
  time tested implementation that newer proposals do not yet have.

There are links to documents for implementers and users as well.

https://www.iad.gov/iad/programs/iad-initiatives/cnsa-suite.cfm


Algorithm to factorize $N$ given $N$, $e$, $d$

Algorithm

An RSA modulus $N$ product of large distinct primes can be factored given $(N,e,d)$ per:

Compute $f\gets e\,d-1$, and express $f$ as $2^s\,t$ with $t$ odd
Set $i\gets s$ and $a\gets2$
Compute $b\gets a^t\bmod N$ , and if $b=1$ then

set $a$ to the next prime, and proceed at 3

If $i\ne1$ then

compute $c\gets b^2\bmod N$ , and if $c\ne1$ then

set $b\gets c$, decrease $i$, and proceed at 4

If $b=N-1$ then

set $a$ to the next prime, and proceed at 3

Compute and output $p\gets\gcd(b-1,N)$ , and $q\gets N/p$.

For standard RSA where $N$ has 2 distinct factors, we have fully factored $N$. Otherwise, $p$ or/and $q$ won't be prime, just re-run the algorithm from step 2 replacing $N$ by any still unfactored component, until all the prime factors of $N$ have been pulled out.

Justification

In an RSA context, $N$ has no small prime factor, thus the algorithm's $a$ at step 3 will remain small enough that $\gcd(a,N)=1$ will hold (if it did not, $a$ would be a factor of $N$ found by trial division; a trivial modification of the algorithm additionally handles $N$ with such small factors).

For any valid RSA triple $(N,e,d)$, it holds that $\left(a^e\right)^d\bmod N=a$ for any integer $a$ in $[0,n)$ (because textbook RSA decryption works).

Thus for any $a$ used in the algorithm, $a^{e\,d-1}\bmod N=1$ holds, that is $a^f\bmod N=1$ for the $f$ of step 1.

The $t$ and $s$ of step 1 are uniquely defined, with $s>0$, and $\left(a^t\right)^{\left(2^s\right)}\bmod N=1$.

For most $N$, step 3 will quickly find an $a$ with $a^t\bmod N\ne1$. Argument: Since $N$ is squarefree, by the Chineese Remainder Theorem, an $a$ coprime with $N$ is rejected at step 3 iff $a^t\bmod p=1$ for all primes $p$ dividing $N$. Since $t$ is odd, if $a^t\bmod p=1$ holds for $a$, then $\tilde a^t\bmod p=p-1\ne1$ for $\tilde a=-a\bmod p$. Thus for $a$ coprime with $N$ chosen randomly in some large interval, the probability of $a^t\bmod p=1$ is $\le\frac12$. That is independently for each $p$, thus $a^t\bmod N\ne1$ has probability $\ge1-2^{-m}$ where $m\ge2$ is the number of factors of $N$. Using the consecutive primes $a$ (rather than random $a$) works well in practice for random instances of the problem (I have no proof, and one may require the Extended Riemann Hypothesis).

Before each iteration of step 4, it holds $1<b<N$, with $i\ge1$, and $b^{\left(2^i\right)}\bmod N=1$ ; thus after at most $s-1$ computations in step 4 we reach step 5 with $b\bmod N\ne1$ and $b^2\bmod N=1$.

Step 5 excludes the case $b=N-1$, which is rare in practice (I'm looking for an argument).

Thus at step 6, $\gcd(b-1,N)$ is a non-trivial factor of $N$.

References

A similar algorithm was hinted at in the original RSA paper: Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in CACM 1978; see last two paragraphs of section IX-C. That uses and references the proof of a primality test in Gary L. Miller's Riemann's Hypothesis and tests for primality, in proceedings of STOC 1975.

A more detailed exposition is in Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, CRC Press 1997; see last paragraph of section 8.2.2 (i).

That answer's algorithm differs by using incremental primes $a$ rather than random $a$. That makes the algorithm deterministic (not its runtime), and works well in practice. As a minor aside, the number of modular squares computed in step 4 is minimized by using a test of $i$ rather than an additional last square.

Note: Simpler variations restrict to $b=a^t\bmod N$ or $b=a^{f/2}\bmod N$, but require testing sizably more $a$ when $s$ is large, which occasionally happens. Some justifications assume $d=e^{-1}\bmod\varphi(N)$ or $e\,d\equiv1\pmod{\varphi(N)}$, which does not consistently hold in modern RSA: for FIPS 186-4 that has probability less than $\frac1 3$, because $d=e^{-1}\bmod\operatorname{lcm}(p-1,q-1)$ is required.

For a (different) deterministic polynomial-time algorithm, see Jean-Sebastien Coron and Alexander May's Deterministic Polynomial Time Equivalence of Computing the RSA Secret Key and Factoring, in JoC 2007.


Only remember part and format of BitLocker password

Well, this isn't really on topic for our site, so it will probably be closed.

But you might want to look at something like John the Ripper.

Either that or just grab a dictionary of English words and write a program to put combinations of them together and submit them as password guesses.


Does anyone know of any programmes that can find a function from a known input and output?

Recovering an arbitrary function $f:M \rightarrow N$ from samples $x_i, f(x_i)$ is clearly impossible without additional information unless the given $x_i$ cover $M$ or unless $N$ is of size one, since an arbitrary continuation can be chosen on the remaining inputs. By the same token, it is trivial to find some function that reproduces the input-output behaviour of $f$ (for instance one may just pick a function that takes inputs outside the given values to some constant output in the codomain of the function).

Finding the simplest or most efficient function that reproduces some given input-output behaviour is believed to be difficult in general, even when a full description of the target function is given to the adversary and even when domain and codomain are fairly small. For instance, the paper Partitions in the S-Box of Streebog and Kuznyechik by Leo Perrin basically showed a surprisingly efficient way to implement the S-box of the Russian encryption algorithm Kuznyechik (and the Russian hash function Streebog) as well as the techniques used to obtain this representation and won the best paper award at FSE 2019. The S-box in question is a function that takes an 8-bit value to another 8-bit value and is completely public. Hence, even for functions that small, recovering an efficient function representation from the value table will not be easy in the general case.


How to use cryptography to assure data integrity?

If I want to ask a potentially compromised server to remember a file that I don't have room to store myself, I can pick and remember a 256-bit secret uniformly at random, and compute a short—say, 128-bit—authenticator (or MAC, message authentication code) for the file under the secret key.  I keep the key on my person; I affix the authenticator to the file.

Standard MAC algorithms include Poly1305, which is very fast but can handle only one file per secret key, and HMAC-SHA256, which is much slower but can handle many files per secret key.

If, when I ask the server to retrieve my file, the server tries to fool me into accepting a file that is different from the one I stored, I can recompute the authenticator using the secret key, and compare it to the one that was stored alongside the file.  If they match, then it is almost certainly the file I stored.  If they don't match, then the file was modified.

The technical property that a MAC has is existential unforgeability under chosen-message attack: we conjecture, or prove in the case of one-time authenticators like Poly1305, that an adversary who can learn the authenticator for one or many messages of their choice has only negligible probability of finding the true authenticator themselves for any other message.  That is, we consider a game where the adversary can query you, the bearer of the secret key, for the authenticator for one or many messages of their choice; then the adversary wins if they can find, without asking you, the correct authenticator on any other message.

What if I want someone else to be able to verify integrity, without their being able to forge the messages?  For example, I want to make a promise in a contract, and publish the contract so that anyone can read it, but I don't want to let anyone else alter the contract.  I first share a public key with everyone, and then use the corresponding private key to digitally sign the contract.  Anyone can use the public key to verify the signature.  Only I, with secret knowledge of the private key, can make a signature that will pass verification.  So anyone can verify, but only I can sign.

Standard signature algorithms include RSASSA-PSS, which is based on the mathematical magic of the RSA trapdoor permutation $m \mapsto m^3 \bmod n$ for $n = pq$ a product of large randomly chosen primes, and Ed25519, which is based on arithmetic in the scalar ring of the twisted Edwards elliptic curve $-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$ over the finite field $\mathbb Z/(2^{255} - 19)\mathbb Z$.

The technical property that a digital signature scheme has is also called existential unforgeability under chosen-message attack, but in the public-key setting where the adversary also has access to the public key in addition to being able to query you for the signature on any message of their choice.


Point decompression on an elliptic curve

Let $x\in\mathbb Z/p\mathbb Z$ be the point's first coordinate, and define
$z := x^3+ax+b$. We know that there exists a square root $y\in\mathbb Z/p\mathbb Z$ of $z$, i.e. $y^2=z$.
Let's assume we have already found such an $y$. Since the order of $(\mathbb Z/p\mathbb Z)^\ast$ is $p-1$, Lagrange's theorem implies $y^p=y\text,$ hence
$$\left(z^{(p+1)/4}\right)^2=\left((y^2)^{(p+1)/4}\right)^2=\left(y^{(p+1)/2}\right)^2=y^{p+1}=y^2=z\text,$$
which shows that $z^{(p+1)/4}$ is a square root of $z$. The possible second coordinates for the uncompressed point are thus $z^{(p+1)/4}$ and $-z^{(p+1)/4}$, and you can select the right one using the "sign" bit from the compressed representation.


Why Random Secret Necessary Almost in all digital Signature Algorithms

ElGamal signature, Schnorr signature, DSA and ECDSA are all based on the same core principle. They all use a group where calculating discrete logarithm is infeasible with a generator $g$ (i.e. $k \mapsto g^k$ is a trapdoor function). A key is a group element: the secret key is an index $x$ and the public key is the corresponding group element $y = g^x$. To sign a message:

Choose an element of the group by its index $k$. $k$ must remain secret forever and must not be reused for another signature.
Calculate a value $r$ which is derived from the group element $g^k$. $k$ must remain secret but $r$ will be public.
Calculate a value $s$ that depends on both $r$ and $k$, as well as the secret key $x$ and the message to sign. (Actually Schnorr is structured differently and the message goes into $r$ instead of $s$, but it's still the same core principle.)
The signature is the pair $(r,s)$.

The verifier uses $r$, $s$ and the public key to calculate two group elements. If $s$ was derived from $r$ using the secret key and the secret index $k$ then the secrets cancel out and the two group elements are identical. Without knowledge of the secrets, it's infeasible to make the two calculations produce the same value.

The nonce $k$ must have two properties: it must not be reused for another signature in the same group, and it must remain secret. If the nonce for a signature is revealed, it's trivial to calculate the secret key from the nonce and the signature. If the same value $k$ is used for two signatures with the same key then their use cancels out and this again reveals the secret key. Even partial information about $k$, or reusing $k$ with different signatures, leaks information that can make it easier to find the secret key(s).

It is not necessary for $k$ to be random, however. It needs to be as hard to find as the secret key, and as unique as the secret key and the message. It's ok for $k$ to depend deterministically on the secret key and the message. For (EC)DSA this is standardized and commonly used. Deterministic (EC)DSA uses the secret key and the message to seed a pseudorandom generator which is used to generate $k$.

The other family of popular signature methods is based on RSA. There are two signature schemes based on RSA: PKCS#1v1.5 and PSS. Both use the RSA trapdoor permutation on an input that contains the message to sign. PKCS#1v1.5 is not randomized at all, and PSS is optionally randomized to generate the padding (the part of the input from the trapdoor function that isn't the message). The random padding in PSS is revealed as part of the signature. Using random padding gives a proof of security that relies on fewer assumptions than what you can get without random padding, but this doesn't translate to any known attack on signatures without random padding. PKCS#1v1.5 signature, which is always deterministic, has no known attacks if implemented correctly.

Encryption requires non-determinism so that, at a minimum, encrypting the same message twice doesn't produce same output. For asymmetric encryption, this is vital since anybody can use the public key to encrypt: if a public-key encryption scheme wasn't randomized then any ciphertext could be broken simply by guessing the plaintext and encrypting it. The non-determinism is equivalent to building in a secret part in every ciphertext (which needs to be done right!). In public-key encryption, the random nonce needs to remain secret as long as the message, but (at least with some schemes such as RSAES-PKCS1v1_5 and RSAES-OAEP) it can be revealed when the message is decrypted.

Signatures don't have the same requirements. They don't intrinsically require non-determinism. A popular type of signature scheme uses a secret nonce, but the important property of this nonce is that it's secret, not that it's non-deterministic.

Deterministic and randomized signature scheme each have their own benefits and weaknesses. Randomized versions make fewer assumptions on the cryptographic primitives, which makes them more robust in case of partial breakage. However they introduce a reliance on the system's random generator, which is often a weak point in practical design. This tends to make the deterministic variant of (EC)DSA preferable in practice. For RSA, the random nature padding of PSS is not critical for security, but its presence protects against bugs in verifiers: the main problem with PKCS#1v1.5 signatures is that some verifiers don't do a thorough job (Bleichenbacher attacks against PKCS#1v1.5 signature — not to be confused with his attacs against PKCS#1v1.5 encryption), and PSS is more robust against such errors.

Using a random value also introduces a potential covert channel (a black box that is supposed to do nothing but sign a message can get some information out to a third party). The deterministic variants of logarithm-based schemes don't solve this since it's impossible to tell how the nonce was generated. Covert channels are rarely a concern however.


Reverse in a sense that every step done in encryption needs to be reversed. For Sbox, there is an Inverse Sbox. For MDS, there is an inverse of MDS(invMDS) such the multiplication of MDS and invMDS is an identity Matrix. Since inverse of XOR is xor, so round keys are xored in decryption but in reverse order meaning, round 10 key is xored first, then round 9 and so on.

If you write down all the encrypting steps done between Plaintext and Ciphertext from Top to Bottom, then while decryption, you need to inverse of each step from Bottom to Top (moving from ciphertext to plaintext)


Is there an $n$-bit hash function such that $n$ is equal to the length of input and the collision resistance is close/equal to $2^{n/2}$?

I am not entirely sure I got your question right, so let me rephrase it: you want a function $H$, that takes as inputs strings of bits, and outputs other strings of bits, such that:

There is nothing secret in $H$; it is deterministic, easily computable, and uses no secret key.
If $m$ has length $k$ bits, then $H(m)$ also has length exactly $k$ bits.
It should be computationally hard to find two distinct inputs $m$ and $m'$ (with the same common length $k$ bits) such that $H(m) = H(m')$. The "hardness" here means that the effort to find a collision should be at least in $O(2^{k/2})$.

With these requirements, a very simple solution is to use the identity, i.e. $H(m) = m$ for all strings $m$. The identity can be computed very efficiently: it has cost zero. There are no collisions at all, so the hardness of finding a collision is infinite. However, I suppose that the identity is not appropriate in your use case; i.e. you actually want more than just "resistance to collisions".

So let's add some extra requirements. You want a publicly computable function $H$ that preserves length ($H(m)$ has the same length, in bits, as $m$, for all strings $m$), and that fulfill the three classical notions of security for hash functions:

Resistance to preimages: given output $t$, it should be computationally hard to find input $m$ such that $H(m) = t$.
Resistance to second preimages: given input $m$, it should be computationally hard to find input $m'$ such that $m\neq m'$ but $H(m) = H(m')$.
Resistance to collisions: given a bit length $k$, it should be computationally hard to find inputs $m$ and $m'$ of length $k$ bits, such that $m\neq m'$ but $H(m) = H(m')$.

Note that, in our case, we must use the bit length as parameter. In usual hash function, the input length is arbitrary but the output length is fixed an implicit in the definition of the hash function. For your function $H$, you must add the bit length $k$ as parameter to the security notions. For preimages and second preimages, this is easily obtained as the length of the challenge: when I give you $t$ and challenge you to find $m$ such that $H(m) = t$, then I also necessarily give you the bit length $k$, which is the length of $t$. But for the "collisions" challenge, I must specify the bit length $k$ explicitly, otherwise you could (smugly) solve the problem for a very short length, and show me that collision.

The variable-length property of $H$ makes the problem a bit harder to analyze. With a normal hash function with a fixed output size ($k$ bits), but accepting inputs of arbitrary sizes, it can be shown that the best resistances you can hope for are on the order of $2^k$ for preimages and second preimages, and $2^{k/2}$ for collisions. However, with a length-preserving function, you can get farther some of these limits; indeed, if you use the identity (i.e. $H(m) = m$), then resistance to preimages is nil (simply set $t = m$) but resistance to second preimages and collisions is infinite (there is simply no collision at all).

All of that being said, an easy solution is to use a key derivation function. One standard KDF is HKDF: it can take inputs of arbitrary size, and produce outputs of configurable size, so you can simply use HKDF with an output size equal to the input size. This has some caveats, though:

Maximum output size of HKDF is limited to 255 times the output size of the underlying hash function. If you build HKDF over SHA-256, then you will get an output of at most 8160 bytes (65280 bits).
You will heuristically get your collision resistance target ($2^{k/2}$) but, again, only up to some limit. If the internal hash function is SHA-256, then for $k \gt 256$, you might not get more than $2^{128}$ resistance to collisions. This does not matter in practice, since anything beyond about $2^{100}$ is equivalent to infinite for the foreseeable future.

Another candidate is SHAKE, one of the variants of SHA-3. SHA-3 is based on Keccak, a "sponge function" in which you first accumulate the input into an internal state, then produce output from that state; with "plain" SHA-3 you just get enough bits to reach the defined output size for the hash function, but with SHAKE you let it flow for as long as you want. If you define $H$ to be "SHAKE256, with an output size equal to the input size", then you should get a reasonable solution. Note that SHAKE output size is not practically limited; however, like with HKDF, there is an internal limit which will set a maximum to the collision resistance you can hope for, in a theoretical point of view.

(Having such a limit is mostly necessary for any function that works but first absorbing the data into an internal fixed-size state, then producing output deterministically from that state alone. This should not be a problem in practice, since you can put that limit far away into the land of "cannot do that in practice". If you want to talk theory with adversaries of truly unlimited power, then take care that there is no known proof that secure hash functions can actually exist at all.)


Your second solution seems to be quite close to optimal. You perhaps do not need both nonce and timestamp unless timestamp is part of the payload. Anyway, the structure
$$
N||P,
$$
where $N$ is 48-bit nonce and $P$ is a 32-bit payload seems sufficient for your needs, as you are unlikely to generate more than $2^{48}$ product keys. To ensure authentication (unforgeability) you merely add a 48-bit zero string (analogue of your 'magic') and encrypt it with AES:
$$
KEY = AES_K(N||P||0^{48}).
$$
Forgery is unlikely in this scheme unless an attacker makes more than $2^{47}$ attempts (which I also suppose is a fair assumption).

In this scheme you can vary all these parameters if you have a larger payload but expect fewer keys or forgery attempts.


Dilithium signature scheme and timing attacks – Does the running time actually depend on the secret key?

The running time does not depend on the secret key. All multiplications, additions, and modular reductions can be implemented to be constant-time.

Diving in to the details:

The probability of the goto in line 11 of the signing algorithm is independent of $s_1$, $s_2$ (the probability is in equation (4)).
The goto in line 13 is also independent of $s_1$, $s_2$ because the use of $s_2$ in line 12 can be replaced with an expression that does not use $s_2$ (as in equation (1) ) in which all variables have distributions independent of $s_1$, $s_2$.


In differential cryptanalysis for DES, why is F(0...0) assumed to be always 0...0?

The question arises from a misunderstanding: The attack described in the paper does not work with actual inputs and outputs, but with differences between them. Hence Differential Cryptanalysis.

Given two messages m1 = (l1, r1) and m2 = (l2, r2) with equal right halves r1 = r2, it obviously follows that r1 - r2 = 0...0 and F(r1) - F(r2) = 0...0.


How did you get the key from message & cipher text seems that step is flawed.
The general approach seems correct.

Also most people would write a tiny bit of code in their programming language of choice rather than do this by hand. If you are not comfortable writing code, I strongly urge you to pick up a tutorial. Even classic cryptography is far easier with some basic programming skills.


Can curve25519 keys be used with ed25519 keys?

Trevor Perrin wrote a library doing exactly that. Explanation can be found on in the curves mailing list archives.

To convert a Curve25519 public key $x_C$ into an Ed25519 public key $y_E$, with a Ed25519 sign bit of $0$:
$$y_E = \frac{x_C - 1}{x_C + 1} \mod 2^{255}-19$$
The Ed25519 private key may need to be adjusted to match the sign bit of $0$: if
multiplying the Curve25519 private key by the Ed25519 base point
yields a “negative” Ed25519 x-coordinate, then the private key must be negated modulo the order of the base point: $a_E = q - a_C$.

See Trevor Perrin's email and the ensuing thread  for a security analysis.


Constant time implementations of crypto algorithms

Any function can be made timing attack resistant, and may be more expensive. I.e. AES can be made safe by using a hardware-simulated constant time circuit for lookups (and maybe more magic).

If you need AES: use hardware with a constant time fallback in software. If you don't need AES then prefer it by hardware, then negotiate to a fast software cipher such as chacha20.

I'm yet to investigate (as I don't use these "standard libraries"). Which libraries are we including in standard? OpenSSL? LibreSSL? BoringSSL? Libsodium?
The AES round function is implemented in hardware. This enables the caller to decide the mode I.e. CTR vs CBC vs GCM etc. Last I checked AESNI included sha1 and sha2, but not any ECDSA nor ECDH nor EdDSA nor RSA. Hardware can implement any of these, however, not all functions have a significant speedup in hardware such that using hardware is preferred.


Both ideas are safe if the hash function behaves like a random oracle and has a large enough output (in particular for "idea 1": with a function which outputs n bits at a time, it is expected that the state will enter a cycle of length about 2n/2, after about 2n/2 steps, so if you want "128-bit security", you will need n = 256 or more).

However, we do not have random oracles, but concrete hash functions, which are not as good and have subtle "flaws" which can compromise simple PRNG designs without contradicting the core security properties of the hash function. See this answer for some details. Proposals like yours are not necessarily weak when used with existing hash functions like SHA-256, but it is hard to make sure of it.

The NIST constructions are a bit more complex because they try to be more robust, or at least more convincingly robust. For these reasons, HMAC_DRBG is preferred.

If you want a lot of pseudorandomness with a very high bandwidth, you should look at specialized stream ciphers like these ones (a stream cipher can be turned into a PRNG by making it encrypt a long sequence of zeros). Alternatively, use AES in CTR mode, which will be devilishly fast on recent x86 processors (the ones which have an hardware AES implementation).


Verifying signature owner (without verifying the actual document)

No.

An RSA signature is just a single number, encoded in a certain way. The number represents $x^d$, where $x$ is a padded hash of the document and $d$ the private exponent. If you know a public key $(m,e)$, you can calculate $x = (x^d)^e \mod m$, but without a document (or at least its hash) there is nothing to compare it with to verify anything.

The only thing you can check is whether the signature matches the size of the key (e.g. both 2048 bits). If it doesn't, it clearly isn't from that key, but that's it.


Simulation of Chosen Plaintext Attack on CBC, Predictable IV with OpenSSL

Okay, I solved it.

First of all, I do not need to worry about the padding as I only care for the first block (I know that the message is either Yes or No and therefore never longer than one block) and I can just discard the added block. In reality I probably won't be able to persuade the encryption oracle to use -nopad anyway :)
These are the values that I used

Key:              0011 2233 4455 6677 8899 aabb ccdd eeff

Original Message: Yes || padding
                  5965 730d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d
Original IV:      1212 1212 1212 1212 1212 1212 1212 1212
Message XOR IV:   4b77 611f 1f1f 1f1f 1f1f 1f1f 1f1f 1f1f

Encrypted Message:
                  030a 6eac 2641 e072 bd51 0d84 fb87 08da  -- Actual Message
                  25ff efd9 b2ca 90f9 9c57 7006 0e53 2437  -- this is just padding

Next IV will be:  1212 1212 1212 1212 1212 1212 1212 1213
Message:          5965 730d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0c -- last byte changed!
Message XOR IV:   4b77 611f 1f1f 1f1f 1f1f 1f1f 1f1f 1f1f
                  -- has to be the same as for the original message: check :)

Encrypted Message:
                  030a 6eac 2641 e072 bd51 0d84 fb87 08da -- Message
                  25ff efd9 b2ca 90f9 9c57 7006 0e53 2437 -- this is just padding

We see that the first block of the ciphertexts match (also all following blocks as it is deterministic). Therefore the original message must have been "Yes". We do not need to care about the padding.


Are any block ciphers provably free of equivalent keys?

Yes, some block ciphers provably have no equivalent keys.

For a start, it's very easy to exhibit such a block cipher, by restricting the key and message spaces to something enumerable. Granted, that makes the cipher insecure.

But we can also construct such a block cipher secure under chosen-plaintext attack. Assume a secure block cipher with the same key and block space (e.g. AES-128). Note $E_k(x)$ (resp. $D_k(x)$) for the encryption (resp. decryption) of $x$ under key $k$. And define
$$E'_k(x)=\begin{cases}
0,&\text{if }x=k\\
E_k(k),&\text{if }x\ne k\text{ and }x=D_k(0)\\
E_k(x),&\text{otherwise}
\end{cases}$$
In other words, $E'_k$ is the same function as $E_k$, except possibly for inputs $k$ and $D_k(0)$, which outputs are swapped.

Notice that for any fixed $k$, the function $E'_k$ is well-defined and a permutation of the block space, including in the rare case $E_k(k)=0$, which degenerates in $E'_k=E_k$. Hence $E'$ is a block cipher. And it is demonstrably secure under chosen-plaintext attack if $E$ is, because access to an encryption oracle gives no efficient way to query for $k$ or $D_k(0)$.

The corresponding decryption is
$$D'_k(x)=\begin{cases}
k,&\text{if }x=0\\
D_k(0),&\text{if }x\ne0\text{ and }x=E_k(k)\\
D_k(x),&\text{otherwise}
\end{cases}$$
And since $k=D'_k(0)$, there can't be equivalent keys. For if keys $k_0$ and $k_1$ yielded the same bijections $E′_{k_0}$ and $E′_{k_1}$, then the reverse bijections $D′_{k_0}$ and $D′_{k_1}$ would be the same, hence we would have $D'_{k_0}(0)=D'_{k_1}(0)$, hence $k_0=k_1$; now by contraposition, different keys must yield different bijections, Q.E.D.


Security of hash functions over input extended with a random value

I think so cause $M, R$ can be assumed to be as $X$, so in essence $H(X)$ is being hashed and the birthday attack possibility still exists.

Yes, that's correct.

Note that there is no such function as $H(M, R)$, you'd need some way of combining the values; lets assume concatenation though (so $H(M | R)$).


Why don't we use bcrypt and scrypt together?

Probably because a simple cascade would only be stronger against some attacks, while opening the door to more implementation bugs.

While bcrypt and scrypt are password-hashing functions, much of what is in the answers to this question about combining hash functions applies here. Different constructions give preimage resistance and PRF-ness, and which is desired depends somewhat on the use case. (Password storage is mostly about the former, while the latter also matters if you are deriving an encryption key with scrypt.)

Regarding implementation bugs, if the inner function, which is applied to the raw password, leaks the input through some side channel attack, the outer function may not matter at all. Conversely, if the outer function somehow leaks its output, then using the cascade for encryption keys may be completely broken, and using it for password storage may e.g. allow offline attacks.

With password hashing there's the additional problem of how to divide the time. If you spend the same time on both bcrypt and scrypt, a dedicated attack using ASICs or GPUs could be almost twice as fast as if you spent all that time on scrypt.

All that aside, scrypt is already basically a cascaded algorithm. Internally it uses PBKDF2 to preprocess the input and to produce the final output data. Its preimage resistance should therefore be at least equal to that of a single round of PBKDF2, i.e. HMAC with SHA-256.


Please read the article on HMAC. What you are trying is exactly what is described in the chapter design principle:

  The design of the HMAC specification was motivated by the existence of attacks on more trivial mechanisms for combining a key with a hash function. For example, one might assume the same security that HMAC provides could be achieved with $MAC = H(key ∥ message)$. However, this method suffers from a serious flaw: with most hash functions, it is easy to append data to the message without knowing the key and obtain another valid MAC ("length-extension attack"). ...

There are only two differences to your idea:

Reverse the order of message and key/tag
The idea of having a "tag", where I can only assume it is the usual case as with passwords: Low entropy, unsuitable to be used as a cryptographic key.

So basically you should just use HMAC (if that fits your needs), but put your tag into a password-based key derivation function first, e.g. PBKDF2, scrypt or bcrypt. That key can then be used for HMAC.

Digital signatures on the other hand also offer non-repudiation, and HMACs don't because both the sender and the receiver know the same symmetric key and thus could both have created the HMAC.


Are there any security drawbacks for simply encrypting and MACing my JWS token (JWT)?

[I]f I want the JWS token content to be non-visible, I keep hearing people mention JWE. But is there a security reason why I shouldn't be encrypting them myself?

On the contrary, there is a security reason why you should avoid JWT altogether: software implementing it tends to be riddled with vulnerabilities which are encouraged by a poor design, where the adversary tells you which algorithm to use in the alg field and the software happily obliges.

The standard examples of exploits are specifying the none algorithm to disable verification altogether, or specifying a secret-key authenticator like HMAC-SHA256 when you meant to use a public-key signature like RSA—the adversary knows the public key, and can therefore compute HMAC-SHA256 under that public key that will pass HMAC-SHA256 verification.

Instead, you are much better off just using a single authenticated cipher on a binary blob of data.

  If I take the JWT, encrypt it with AES-256-CBC (I prefer CBC over GCM because I don't want to fall into equal IV attacks), then MAC it with some hashing function like SHA-512 (HMAC-SHA512), convert both the ciphertext and the MAC to base-64, and put them in a printable string. Am I vulnerable to some security attacks if I use the outcome to authenticate users on a web application? Or is just "not nice"?

This just doesn't follow the dogma of JavaScript and JWT cultists.  I would say it is not nice for JWT to inflict misbegotten cryptographic disasters on the world in the name of…overengineering or something.

That said, while AES-CBC/HMAC-SHA256 in encrypt-then-MAC composition using randomly chosen IVs is generally OK, you should be careful composing primitives this way, especially ones with sharp edges like AES and CBC:

Do not touch anything before you have verified the authenticator (in constant time!).  It may be tempting to have one function to decrypt the message, and another function to verify the authenticator, and hope that downstream users will do both—but this is a disaster waiting to happen.  Make one function that either verifies and decrypts, or fails altogether without divulging any plaintext.  Unauthenticated data is pure evil—don't touch it!
Pay close attention to security contracts; note that CBC and GCM are different types of thing.  You are evidently aware of the importance of authentication, which is good—I am emphasizing this just because your parenthesis seemed to compare CBC and GCM directly, which is apples-to-oranges because they have totally different security goals; while encrypt-then-MAC with AES-CBC and HMAC-SHA256 is a more similar type of thing to AES-GCM in that they have the same security goals and differ only in usage requirements (and size of authenticator).
If you're having a sequential conversation, AES-GCM is may be a better option than AES-CBC/HMAC-SHA256 if it is simpler to use: you can safely use the number of messages you have sent so far as the nonce, and have the receiver require that number to be the nonce.  This enables the receiver to quickly drop forgeries on the floor, and which ensures that a large class of insecure implementations will immediately fail to interoperate rather than silently leak secrets.

(When AES-GCM was introduced to TLS in RFC 5288, they made the mistake of allowing arbitrary sender-chosen nonces; TLS 1.3 in RFC 8446 fixed this mistake so that broken implementations will fail fast and noisily.)
If counting is hard because of, say, VM state rollbacks, random IV generation might be hard too for the same reason.  If this is relevant, you may want to use a SIV-type scheme, synthetic IV, like AES-SIV, which chooses the IV as a pseudorandom function of (an optional nonce and) the message; at worst, if you repeat a nonce, the adversary can tell whether the whole message was repeated or not.
Make sure to generate known-answer test vectors for the whole AES-CBC/HMAC-SHA256 composition that you can automatically do self-tests with.
AES invites timing attacks unless you can guarantee all the way down your software stack that you're using hardware support for it like AES-NI.  It can be computed in constant time software, but it's very slow to do so.  Alternatives like  Salsa20 in the the authenticated cipher NaCl crypto_secretbox_xsalsa20poly1305 do not have this flaw.  Of course, I don't know how easy it is to use anything other than AES in your software stack; if the tradeoff may be between using AES here and throwing up your hands and giving up on security, maybe AES is OK.

Side note:

  I understand that signatures make it impossible for the tokens to be modified.

There are two very different things that JWS conflates under the term ‘signature’, which makes for exceptionally bad API design.

Signatures enable anyone who knows a public key to verify a message, but only the owner of the private key can sign messages.

Signatures are verifiable by a third party, and so are useful as an adversarial audit trail—if you claim to an arbitrator that a vendor stole your money, but they can present the check to the arbitrator, the arbitrator can verify it to determine that you're lying.

Signatures are relatively expensive to compute, costing hundreds of thousands of CPU cycles per message.
Authenticators or message authentication codes (MACs) allow anyone who knows a secret key to verify or authenticate messages.

Authenticators are not verifiable by third parties—if Bob shows Charlie a message he claims Alice sent him, the putative authenticator from Alice doesn't mean anything because Bob could have forged it too.

Authenticators like Poly1305 can be some of the cheapest cryptographic primitives ever, costing under one cycle per byte.  (HMAC-SHA256 is nowhere near the fastest authenticator but it is still much faster than public-key signature.)


Multiple Rainbow Tables and their Success Probability

With perfect rainbow tables the math for evaluating is much simpler but the math for how long it takes to the build them becomes complex.

It all has to do with collisions and since we eliminate almost all of them the math is simple.
Let's look at how collisions behave in a classic distinguishing point table.
When adding a new row each value may collide with any previous $m*t$ point and the continuation to the end of the row will obviously collide as well. So any collision costs us the whole row not just the colliding point. When we split into multiple tables this changes.  A collision with within the table is as before but is less likely as we separated our points between tables so each table is much smaller. A collision across table isn't that bad because because only the single point will collide the next point in each chain will be different in each table so this isn't very bad and is in many cases ignored in analysis.

Rainbow tables are similar, each column has a different hash function so a rainbow table column is similar to a separate table. Only $\frac{1}{t}$ collisions are in the same column and will continue to collide till the end of the row. Cross column collisions like cross table collisions don't propagate and aren't expensive.
$t$ distinguishing points tables with $m$ rows and $\sim t$ columns each have similar coverage to a single rainbow table with $m*t$ rows and $t$ columns. The obviously both take $m*t$ space. But the lookup time in the rainbow version is half, because columns near the end are cheaper to check.

As to the math, the first formula is easy, $m_i$ are the number of distinct values in each column and the probability of appearing in each column is independent so the coverage is $1$ minus the probability of missing all columns. The next formula is the tricky one. Each column has fewer distinct values then the previous one. This comes from balls into bins theorum. Throwing $m$ balls into $n$ bins. The expected number of empty bins is $n*(1-\frac{1}{n})^m$ and subtract that from $n$ you get the number of different values. The version with $e$ is an excellent aproximation for large $m,n$.

As to multiple rainbow tables:
The first column of a rainbow table is special we can easily ensure it is unique. Adding columns each column is less effective. If we break into multiple tables we need to look up in each of them independently so splitting into two tables cost us lookup time. but collisions between tables are a non issue. Try punching in some numbers to get a feel for it.
If our search space n is 2^50 and we have a memory budget for 2^30 rows. Let's consider one or two rainbow tables. If we want a probability of 50% in a single table we need 869,000 columns. For two tables each with half the rows we will need each table to have a success rate of $1-sqrt(1-0.5)$ which ~0.292 This will require 790,000 columns. Which is better? The single table, because it's runtime is $869000^2/2$ which is less then $2(790000^2/2)$
But what if we want a high probability for example 95% ? for a single table we will need to go all the way up to 7,300,000 columns. But two tables with half the rows will need only 4,680,000 rows to reach 77% each.  Now we punch in and see the two tables are more then twice as fast then the single table.
If you fix sigma(m) for all tables and p, you can iterate over small table counts for each find the necessary t and pick the optimum.


Is it possible to reverse the birthday attack calculation?

It is possible to reverse the birthday bound calculation. You can get an easily computable approximation using the expected number of collisions:

If you had random $n$-bit salts, after $k$ values you would expect $2^{-n}\binom{k}{2}$ collisions. If the collisions are rare, they are mostly single collisions, so there are approximately $u = k-2^{1-n}\binom{k}{2}$ unique, non-colliding values. So your results $k = 1.8 \cdot 10^7$ and $u \approx 1.7 \cdot 10^7$ could be generated with $n \approx 28.3$. That is, they could be random numbers between zero and 340 million, give or take.

More exact formulas are found in the answers to this question Neil Slater linked in the comments. With your numbers they give an answer of around 27.3. This makes sense, because the approximation above ignored multi-collisions, which leave more unique values than estimated.

However, that does not imply they have 27-28 bits of entropy. They could have considerably less. For example, they could instead be the results of a counter that wraps around after ~17500000 items. There is no way to know with just the data you gave. They very likely do not have more than about 28 bits of entropy each, however.


Coin flipping with limited communication between participants

As fgrieu pointed out, Alice and Bob must have somehow come to some kind of agreement before the random beacon is generated.
Would either of these techniques work for you?

use the random beacon directly

They could agree ahead of time that "Alice wins if the first random bit sent by the NIST Randomness Beacon on 2015-11-02 at 11:59 is a 0, and Bob wins if that bit is a 1."

Randomness beacons allow a person to prove that the random number (or any hash value calculated from it) was generated after some particular time.

use Alice's message with trusted timestamping

There are ways of doing trusted timestamping to prove that Alice knew a message before some particular time.

They could agree ahead of time that "After Alice commits to a single message by including that message in the Bitcoin blockchain as part of a transaction sending a tiny amount of bitcoin from Alice to Bob sometime during the day of 2015-11-01, and then later the NIST Randomness Beacon on 2015-11-02 at 11:59 generates some random data, Alice wins if the first bit of hash(message, beacon) is a 0, and otherwise Bob wins."

(If the message is long, it would be better to store only the hash of that message in the blockchain as a commitment to that message).

There is no direct communication from Alice to Bob or from Bob to Alice before the beacon transmission,
although this particular system requires some two-way communication between Alice and the Bitcoin system before the beacon transmission.

  Alice may generate several messages and timestamp them before the
  random beacon is generated. Then, after the random beacon is
  generated, she can choose the message that yield the result that
  favors her.

With this system, after the beacon transmission, Bob can fairly easily inspect the Bitcoin blockchain for that day and see if Alice tried to cheat by sending small amounts of bitcoins to him over several transactions that day, each transaction with the hash of a different message.
(Bob could inspect that blockchain even before the beacon transmission, although you could argue that would count as a message from Alice to Bob before the beacon transmission).

  How can we prove that the timestamp was generated before the random
  beacon?

That is a hard problem, but that is the problem that Bitcoin was designed to solve.


Creating UID's using hash functions - most appropriate hashing algorithm?

I want to run each of these unique integers through a hash function, with the objective of 1) maintaining the uniqueness, 2) obscuring the underlying integer value and 3) having a hash output with a length of <= 34.

You need to be very clear about what you mean by "obscuring."  The basic problem here is that your values look like they're likely to be subject to brute force guessing attacks—just like passwords are.  This means that if you apply a public, unkeyed hash function to your values, you subject yourself to the same sorts of attacks that are very successful against passwords—particularly attacks against unsalted passwords.

If by "obscure" you really mean that an attacker should not be able to figure out which number corresponds to each hash, then your solution needs to incorporate a secret key, and that key needs to be protected.  This is much, much, much, much more important than whether you use SHA-2 or Blake2.  (PS: Don't use MD5 for anything!  And if you need to incorporate a secret into the computation, don't do it in an ad-hoc manner—use HMAC-SHA2 or Blake2's optional key support).


Can you use a dynamic key and data size for KMAC?

Yes, however it does take a deeper look into the standard.
KMAC128 is defined as:

newX = bytepad(encode_string(K), 168) || X || right_encode(L).
return cSHAKE128(newX, L, “KMAC”, S).

So there seem to be no encoding of the size of the key, which that there could be multiple K, M key message pairs that would result in an identical value of bytepad(encode_string(K), 168) || X (because A || BC = AB || C).
However if we take a look at the encode_string(S) function:

Return left_encode(len(S)) || S.

This means that the (bit) string encoding canonically encodes the key including the size of the key (len(S)). That means that any key with a different size will be encoded in such a way that the division between key K and message X is clear.
The canonical encoding is still present even though the encode_string has a more generic name compared to earlier KMAC drafts where it was called Keypack(K, l)  and took the length as explicit parameter.


Using a static IV isn't simply "poor form" — it introduces crippling weaknesses to the security of your ciphertexts. Likewise, using correctly-generated IVs (the requirements differ from mode-to-mode, but cryptographically random IVs almost always meet those requirements) isn't "better"; it's absolutely necessary.

That said, there is absolutely no requirement of security for IVs. They can be stored safely alongside your ciphertexts.

However, I would strongly caution against using the implementation in the linked post. It uses CBC mode without authenticating the validity of the ciphertext (e.g., with an HMAC), and so will likely (depending on your particular use) make you susceptible to padding oracle attacks.

You should use something like KeyCzar or NaCl if at all possible. As a non-cryptographer, trying to use cryptographic primitives yourself is a bit like trying to build a car engine from parts. You're overwhelmingly likely to miss an important but crucial detail, and have the whole thing blow up in your face.


Attacking historical ciphers methodology

If you don't know the system, you just check one after the other:

frequency analysis of bigrams detects Ceasar and Playfair. Try Caesar first then Playfair.
Auto correlation method for Vigenere (for each x: count the number of occurances, where letter at position i and i+x are equal. For the correct codeword length, it will spike)
If you have a Hill cipher, you lost.


Homomorphic encryption methods that could support logical XOR, AND?

Partial and Fully Homomorphic Encryption
When a homomorphic encryption scheme supports a single operation on the encrypted data like

RSA has a modular multiplicative operation
Elgamal has a modular multiplicative operation
Goldwasser–Micali cryptosystem has x-or operation
Paillier cryptosystem has a modular addition operation

it is called partial homomorphic. When they support two operations they are called Fully Homomorphic Encryption (FHE) in the sense that one can build arbitrary circuits with them constrained to some conditions.
The two operations in the FHE scheme are usually addition and multiplication. In the bit-based case, the addition is XOR $\oplus$ and the multiplication is AND gates $\wedge$. Though neither the XOR nor the AND are universal logic gates, when combined they can construct any gate. And note that the randomization on the encryption requires a different design than the usual circuit design.
Public Key!
All FHE schemes that I know are based on public-key. Therefore if the randomization is removed then an attacker can use the public parameters to determine the encrypted values. If one looks at the Ind-CPA game for public-key encryption, we consider that the encryption oracle is free to the adversary. As a concrete example, consider TextBook RSA encryption (it has no padding, insecure, and it is multiplicative) with single-bit encryption then you can immediately deduce it, even for a byte or a word.
This is dangerous and we left it with the seminal paper of Shafi Goldwasser and Silvio Micali

Probabilistic Encryption, April 1984

You can also get the notion from the famous ECB picture of tux in Wikipedia.
There are many libraries for FHE that you may look at like HeLib, TFHE, Seal. If you like to read how some small circuits are designed, you can read from here Representing a function as FHE circuit and see some of the implementation papers, too.


Can quantum computers break quantum cryptography?

I happened to learn that encryption by quantum cryptography would be impossible to break as it's state changes the instant an eavesdropping event (by non-quantum systems) occurs.

Actually, the QKD system doesn't assume that the eavesdropper is nonquantum; he is allowed to attempt to generate an entangled state with the qubit being transmitted.  However, even the act of generating such an entangled state would alter the received bit (with a probability that is bounded away from zero), hence any such eavesdropper is detectable, even if the eavesdropper is allowed a quantum computer.

[Insert standard skepticism about whether QKD is a practical system, compared to the alternatives]


I think the 10100 is a typo and should be $10^{100}$ as shown here

The period would be something along the lines of how long until the byte stream repeats. For example if the byte stream were "ABCDABCDABCD" and so on, then the period would be 4.

For security you want a large period so that you can encrypt large amounts of data.


Will the ECDSA with SHA-3 implementation be quantum-proof?

No.  Anyone who can compute elliptic-curve discrete logs, such as an adversary with a quantum computer powerful enough to run Shor's algorithm, can immediately recover an ECDSA private key and forge arbitrary signatures of their choice.  It doesn't matter if you use SHA-3 or floss each day.


Is it safe to use single-block AES for mutual authentication?

If we assume that AES is a pseudorandom permutation (which is a standard model for block ciphers), then AES can replace the HMAC in your construction. Be aware, this only works because you have a fixed message length, i.e. the protocol must not accept nonces $> 128$bit.

Besides, I guess you are aware of this but you have a shared secret key among all users. Hence, your protocol does not authenticate a specific user. Instead, the protocol only verifies that the other side is a user that knows the secret key.

The reason is that any user knowing $s$ can compute $k_A = \text{HMAC}(s, i_A)$. Even if $i_A$ is not made public explicitly. Everyone that communicated once with $A$ will know $i_A$. Besides, this would mean that you have to protect $i_A$ while being transmitted and finally this has the problem that the authenticity of $i_A$ must be verifiable. Otherwise, an attacker could use an arbitrary value as $i_A$.

If you only want to get a proof of membership, this protocol works but is overly complicated as you can omit the key derivation step. You can simply use $\text{HMAC}(s,nonce)$...

As you included the identifiers I guess you wanted something stronger than a proof of membership. In this case, you should switch to some standard mechanism like TLS with a PKI. You will not really be able to omit public key crypto in this setting. The only (impractical) solution in the symmetric setting would be the establishment of one key for each pair of users.


Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given an oracle that tells you for any $h\in\mathbb{Z}_{p-1}^\times$ if the discrete logarithm $\log_g(h)$ is $\ge\frac{p}2$ or not, allows you to find $x := \log_g(h_0)$ for fixed $h_0$ with about $\log_2 p$ queries:

The query $\log_g(h_0)\stackrel{?}\ge\frac {p-1}2$ gives you one bit of information $z_0 := \lfloor\frac{2x}{p-1}\rfloor\in\{0, 1\}$, and you know that $h_1 := h_0\cdot g^{-z_0\cdot\frac{p-1}2}$ has a discrete logarithm $\log_g(h_1) \in \{0, 1, \dots, \frac{p-3}2\}$.

So if you multiply $h_1$ with $g^{\lfloor\frac{p-1}4\rfloor}$ you get an element $h_1'$ with discrete logarithm $\log_g(h_1')\in\{\lfloor\frac{p-1}4\rfloor, \dots, \lfloor\frac{3p-7}4\rfloor\}$, and querying $\log_g(h_1')\stackrel{?}\ge\frac {p-1}2$ gives you (roughly) another bit of information by cutting the interval in half.

You can repeat this step of multiplying an adaptively chosen power of $g$ to query the oracle, halving the intervals in every step until you find a single value from which then you can calculate the discrete logarithm $x$.


Blowfish, Sboxes and the digits of PI, and the P_Array

Another unbreakable encryption from Bruce!  His words.

Yes the boxes come from π.  However, it's not the way you think.  It's not a literal base change of the decimal expansion.  You have to calculate π from scratch in hexadecimal.  If you were to use your approach and simply change the base of the decimal expansion, you'd be putting 10 values into 16 bins for each digit. In hex, π is just:-

3.243F6 A8885 A308D 31319 8A2E0 37073 44A40 93822 299F3 1D008 2EFA9 8EC4E 6C894 52821 E638D 01377 BE546 6CF34 E90C6 CC0AC

which are your digits.

You do understand that the P and S boxes don't contain π?  They are initialised with π digits, but then amended in a key related fashion.  The π bit is what's know as nothing up your sleeve numbers (NUMSN), and there are many answers here relating to such initialisation.  In summary, you have to initialise a variable with something or zero. The purpose of NUMSN is to create a dissociation between the numbers you start with and the way the algorithm works so that there cannot be any possible adverse relationship.  There is some expansion here.

On that basis, yes you could initialise with anything.  Even just  zeros.  Although, I've never seen security analysis of an algorithm with and without the NUMSN.

  After all, I saw that sbox values were supposed to be random.

This is a contentious issue.  For a super dooper efficient algorithm, s boxes are very cleverly designed with several security parameters in mind.  There is an s-box tag that will highlight a pile of appropriate questions.  Uber efficiency isn't always necessary.  Brute force can be used instead by increasing the number of rounds.  As Blowfish recalculates it's S and P boxes dynamically, such security pre design clearly isn't used in that case.  I believe that this technique works for both the S and P boxes.


Soft question: What are examples of beautiful proofs in cryptography?

Theorem.  The ECB mode of a block cipher is distinguishable under chosen-plaintext attack with laughably high advantage.

Proof.