Can the attacker guess secret such that they would end up with a valid prefix?
Can the attacker use that guessed, validated secret and compute prefix values for different publics?

You don't need a collision attack here. You need the pre-image attack that given a hash value $h$ one needs to find an $x$ such that $h = \operatorname{SHA-256}(x)$. Note that the attacker doesn't need to find the original value, any value that has the required has value will be a success for the pre-image attack and there can be more than one value or none in the range $[0..2^{256}]$. We expect that some will have none due to the collisions.
The 16 bytes hex string makes 128-bit and that is beyond the search for anyone. Therefore looking for the original value will be beyond any attacker since there is no known successful pre-image attack better than searching for SHA-256.
Since you trimmed the result, the pre-image resistance now requires around the 32-bit search to find one. The attacker will look for a candidate secret so that
$$\operatorname{SHA-256}(\operatorname{SHA-256}(\text{candidate secret}) \mathbin\|\text{-} \mathbin\| \text{public})$$ will produce valid output.
Once a successful candidate is found, unlikely to be the original since it was the output of SHA-256, the system will accept this a valid input. The attacker only needs to look for the first 32-bit of a 224-bit where they can set the rest bits to zero.
$$\text{candidate secret} = \overbrace{\texttt{0x00000000 to 0xFFFFFFFF}}^{32 \;bits}\;\overbrace{\texttt{0x00000...0}}^{224 \;bits}$$
That search is quite double if you consider some of the top machines

Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year.
Titan can reach $\approx 2^{63}$ SHA-1 hashes around two hours, $\approx 2^{71}$ hashes in one year.
Bitcoin miners reached $\approx 2^{92}$ SHA-256 hashes per year in 06 Agust 2019.

The advice: keep the result at least 16 bytes if you don't fear a possible future quantum attack. Otherwise one needs to double size for Grover's attack and triple size for Brassard et.al's attack. Of course, it is not clear how one can prepare the sequential evaluation without a magnificent delay that can cause an invisibility.


FCD 18033-2
Encryption algorithms — Part 2:
Asymmetric ciphers - the final committee draft (FCD) of ISO/IEC 18033 - by Victor Shoup is publicly available from his website and specifies (in section 6.2) that KDF1 is

For an octet string $x$ and a non-negative integer $l$, $\operatorname{KDF1(x,l)}$ is defined to be the first $l$ octets of
$$\operatorname{Hash.eval}(x || \operatorname{I2OSP}(0, 4)) || ··· || \operatorname{Hash.eval}(x || \operatorname{I2OSP}(k − 1, 4)),$$
where $$k = \lceil l/\text{Hash.len} \rceil $$

The binary counter representation should translate to 4 bytes in big endian.
KDF2 is identical but starts counting from 1 instead of 0.


The algorithm would work fine without the restriction, although it's debatable whether NIST owns the name DSA and you would have to call it something else, the way non-RSA-licensed implementations of RC4 were for a long time called ARCFOUR (alleged RC4) or similar. How about Schnorr Patent Evading Digital Signature SPEDS?
Why did NIST do it (originally, see next)? AFAICT 'everyone knows' they wanted to reduce the amount of testing needed to ensure that multiple, different implementations would provably meet the standard and (as a result) interoperate with each other reliably, while still allowing designers and possibly users to choose tradeoffs of cost vs security. I don't think I've seen that rationale officially documented anywhere, but they certainly have done essentially the same thing with other algorithms and standards, most notably AES (which supports only 3 key sizes and 1 block size, though the underlying algorithm Rijndael supports quite a few more).
Also note the originally permitted sizes 512 to 1024 by 64 -- which still survive in a good deal of software that hasn't been updated -- have officially been obsolete for a long time. Change Notice 1 to FIPS186-2 in Oct. 2001 restricted p to only 1024 (with q still 160); after a long delay FIPS186-3 in June 2009 added p 2048 or 3072 (with q 224 or 256 in the former case and 256 in the latter) -- while 1024 2048 3072 are multiples of 64, they are not all the multiples of 64 in that range, and do not provide nearly the 'fine tuning' that the old list did.
Although in contrast RSA and DH were defined and usually are implemented for any bit size (sufficiently large to provide the desired security) in practice people almost always use powers of two or 'halfway between' sizes: 512 768 1024 1536 2048 3072 4096 -- and FIPS186-3 specifies key generation for RSA signatures (for US govt use) that only allows n sizes 1024 2048 3072.


Difference between a secure PRG and semantically secure encryption

I consider the SU Cryptography course on Coursera really good, up to certain level is very comprehensive. You should discuss these topics on the Coursera forum, IMHO you will be guided more precisely.

You have two questions here and you should know the DEFINITIONS of the secure PRNG and semantically secure encryption. Security of the message differs between two with what needs to be secure. For PRNG it's the output, for encryption it's the plaintext message.

  I have a question why append 0 in G(k) i.e., G'(k) = G(k) || 0 is
  considered as not secure PRG as 0 in message is copied with out
  encryption.

The expression ( G'(k) = G(k) || 0 ) effectively means you're appending zeros to the generated message. It means you can predict there will be 0 at the end of the (otherwise random) message. It is pretty unsecure PRNG.

  Whereas in semantically secure E'(k,m) = 0 || E(k,m) i.e.,
  prepend 0 is considered as semantically secure. Here why appending 0
  does not break semantically secure?

Even you have prepend anything to the ciphertext, it still doesn't reveal anything about the plaintext message.


How is n-bit security calculated with nested encryption?

This solution considers the cipher as AES with 128-bit key and the X-OR is the one-time pad.

A careful investigation will show that 128-bit XOR is not going to help.

$$c = F_{k_1,k_2}(p) = E_{k_1}(p\oplus k_2)$$

The Ciphertext-Only attack;

If you give only one ciphertext then there is no solution. Since the decryption of the given ciphertext with every possible key is a valid plaintext and we cannot distinguish. If we assume that it is in English or another language we can only reduce the key space.

The Known-Plaintext Attack

Now, assume that we have a plaintext-ciphertext pair with $k_1,k_2$. Now we can brute-force but this will be $2^{256}$. $$p = F^{-1}_{k_1,k_2}(c) = D_{k_1}(c) \oplus k_2$$ Since once we
decrypted we cannot determine the $k_2$, we have to search for it.
Now assume that we have more than one plaintext-ciphertext pairs encrypted with the same keys $k_1,k_2$.

Execute the key search only $k_1$ for both cyphertext simultaneously.
$$p_1 = F^{-1}_{k_1,k_2}(c_1) = D_{k_1}(c_1) \oplus k_2$$ $$p_2 = F^{-1}_{k_1,k_2}(c_2) = D_{k_1}(c_2) \oplus k_2$$

For every iteration check the if;
$$ p_1 \oplus  D_{k_1}(c_1) =  p_2 \oplus  D_{k_1}(c_2) $$
then we find the $k_1$ and $k_2$ where the $k_2$ is the $p_1 \oplus  D_{k_1}(c_1)$

The total complexity will be $\mathcal{O}(2 \cdot 2^{128}) = \mathcal{O}( 2^{129})$

The key-space is $2^{256}$ but the provided security is $2^{129}$


Is this an instance of a Diffie-Hellman problem?

As stated the problem is insoluble as zero-knowledge of $k$ is provided (unless we know something about $m$).
To see this, let $x$ be any integer $0\le x\le p-1$ and let $m':= m\cdot v^{-x}$ then we see that $c=m'\cdot g^{(k+x)a}$ and we see that $k+x\pmod p$ is an equally valid output unless we have some reason to choose $m$ over $m'$.


Understanding a variant of Shamir's cryptosystem with authorization levels

I really don't understand what each participant hold and how to recover the secret s in this complicated scenario.

Part of the issue you're running into is that the method to implement the original scheme is not uniquely defined, and so what the various parties hold (and how they would recover the secret) would vary based on things not specified in the question.

The most straight-forward way you would do this is to share the secret two ways:

Once with a $(2,2)$ scheme (and which you would give a share to each of the A parties)
Once with a $(3, 3)$ scheme

For the three shares generated by the latter scheme, you would give them out as:

One would go to each of the A parties (and so both parties would get the exact same share).
One you would secret share with a $(3, n)$ scheme (and each of the B parties would get a share)
One you would secret share with a $(5, n)$ scheme (and each of the C parties would get a share).

In this method, each of the A parties get a "share" which consists of two separate lower level Shamir shares, while each of the B, C parties get a single Shamir share.

If we assume that this is the method used, then it should be straightforward to write out what everyone would hold if the A party leaving were to reveal his share, and how that would allow 3 B parties and 5 C parties to recover the secret.

Note: with these requirements, it is possible to design an alternate scheme where every party holds a single Shamir share; you might find it educational if you were to find that yourself.


How 'safe' is a 12-digit alphanumeric key?

Well, you have $(26+10)^{12}$ choices if the characters are truly random and independent. That's how we commonly judge security in these situations.  So that's $4.7 \times 10^{18}$ alternatives, or 62 bits of security. Hmm, not bad but we commonly refer to at least 128 bits of security on this site. However...

The real security question here is what happens if the wrong key is entered? Consider that a hole-in-the-wall machine only uses 4 digit PINs, but it gets angry when the wrong PIN is entered three times. What does your portal do? It would be really really bad if it just accepted incorrect passwords ad infinitum. Some form of lock out would be in order, or   a  delay (exponential) after each failed attempt.

There are standards/libraries for token generation such as the secrets module in Python with ad hoc security parameters. It's difficult to progress this further in light of the above uncertainty and your minimal revelations about the portal.

And to the counter, any password like your's is almost certainly going to be written down.

And I'm assuming that your records are encrypted in some secure form, rather than directly  using this password without an intermediary key derivation function.


There are attacks on both blockciphers and hash functions that can exploit symmetry in the round functions.  For example, completely identical round functions can permit Slide Attacks on Hash Functions, and rotational symmetries of the round function can permit rotational cryptanalysis.  The round constant addition or 'iota' step of the Keccak Hash Function is designed to break up the self-similarity symmetry of the round function.  Similar tweaks to the 'key schedule' (i.e. round) constant of Threefish/Skein were intended to break up rotational symmetries (see section 9.5.2 of the latest specification for details).

The up shot is that too much symmetry can be very dangerous, even for hash functions, and opens the door to attacks.  Round constants are an easy and cheap way to close that door.


Generate a new public/private key pair for each new message?

In the case of emails your solution is not really practical. The problem is that the sender of an email uses the public key whereas the receiver should have the secret key. This means that whenever somebody wants to send you an email (and therefore generate a new key) you have to be online or you have to provide a set of pre-computed key pairs. If multiple people are sending you emails at the same time. Who is taking which key? Making the key management more complicated doesn't necessarily give you more security.

In the case of communications, like chats, the property you are asking for is called (perfect) forward secrecy. This property, roughly speaking, states that an adversary, who at some point obtains your secret key(s), should not be able to decrypt past conversations.
The following paper should be a good starting point for you:
https://otr.cypherpunks.ca/otr-wpes.pdf


are anonymous credentials a type of zero knowledge proof?

I would rather call them a type of blind signatures. Since signatures stem from non interactive ZKP you can say that they are related.


Is there a cryptographic protocol that let's me prove someone has a large binary?

Like Thomas suggests in the comments, a Merkle tree would help here. As would a simple hash list.

Calculate the hash tree/list over suitably sized blocks of the file and let the recipient know it. As data comes in it can be verified to match. With file size $n$, block size $b$ and SHA-256 as the hash, a hash list takes about $n/b \cdot 256$ bits. So with up to gigabyte files you would want to use at least 2 MB blocks to keep the metadata below 1 MB.

This is similar to how BitTorrent works.

If you need to verify someone has the file you can request they produce a random block. If they have fraction $p$ of the blocks, they will be able to do it with probability $p$, so if that is a problem you can request $m$ blocks for a probability $p^m$.


ECDSA security using same per-message secrets $k$ but different signing keys

For ECDSA the per-message secret $k$ should be generated randomly. In particular you have to ensure that the per-message secrets never repeat, or else the private key $d$ can be recovered. First, let's have a look at an example where the same per-message secret $k$ and the same private key $d$ was used to generate ECDSA signatures $(r, s_1)$ and $(r, s_2)$ on two messages $m_1$ and $m_2$. Then $s_1 \equiv k^{-1}(e_1+dr)$ (mod n) and $s_2 \equiv k^{-1}(e_2+dr)$ (mod n), where $e_1 = H(m_1)$ and $e_2 = H(m_2)$. Then $ks_1 \equiv e_1 + dr$ (mod n) and $ks_2 \equiv e_2 +dr$ (mod n). Subtraction gives $k(s_1-s_2) \equiv e_1 - e_2$ (mod n). If $s_1 \not\equiv s_2$ (mod n), which occurs with overwhelming probability, then

\begin{equation}
k \equiv (s_1 - s_2)^{-1}(e_1 - e_2)\mod{n}.
\end{equation}

From this an adversary can determine $k$, and then use $d=r^{-1}(ks-e)\mod n$ to recover the private key $d$. This implementation failure was used, for example, to extract the signing key used for the PlayStation 3 gaming console or in 2013 to rip users of Android Bitcoin Wallet off their funds.

Now let's have a look at a second example, where the same per-message secret $k$, but different private keys $d_1$ and $d_2$ $(d_1 \neq d_2)$ are used to generate different signatures. In this case the subtraction step from before would lead to $k(s_1-s_2) \equiv e_1-e_2+r(d_1-d_2) \mod n$. From this you are not able to recover the private keys $d_1$ and $d_2$ used to generate the signatures $s_1$ and $s_2$ unless you can efficiently solve the $ECDLP$ (assuming an adequate elliptic curve group was chosen). If you signed the same message, i.e. $m_1=m_2$, then $e_1-e_2$ would cancel out, but this doesn't give the attacker any more advantage as $e_1$ and $e_2$ are supposed to be known anyway.

But be aware that as soon as you’d use the same private-key / message-secret pair to sign another message, this would lead us back to the scenario depicted in the first example. This means that you’d have to be 100 % sure that you only need to sign one single message using the same $k$/$d$-pair. In practice however, you normally don't create a new ECDSA key-pair for every new data you need to sign, as

for every new key-pair you create the verifying party will need to learn the new corresponding public key
you need to keep track of which key to use for every piece of data you signed if you are both the verifying and signing party
using some crypto APIs you sometimes cannot control the per-message secret but only the private key and the signing function will create its own per-message secret making use of the underlying CSRNG


In the proof that weak OWFs imply strong OWFs, why must the position of $y$ be random?

As you write, the proof is via a reduction that transforms any adversary $B$ that inverts $F$ with non-negligible probability $\varepsilon(n)$ into an adversary $A$ that inverts $f$ with probability at least $1-1/p(n) \approx 1$.

Assume for simplicity that $f$ is an injective function. Consider a potential adversary $B$ that internally works as follows: given $Y=(y_1, \ldots, y_t)$, it checks whether $y_1$ belongs to a certain “special” $\varepsilon(n)$-fraction of the image $f(\{0,1\}^n)$. If so, it computes and outputs the preimage $X = F^{-1}(Y)$. Otherwise, it outputs nothing, i.e, it fails to invert this $Y$. Clearly, this $B$ satisfies the above hypothesis, because $y_1$ has an $\varepsilon(n)$ probability of being in the “special” set. (How $B$ checks $y_1$ and inverts $F$ is not important, because the reduction treats $B$ as a “block box.” So we can think of $B$ as using unbounded computation to perform these steps.)

Now, consider a reduction $A$ that works as you propose, by always “plugging in” its external challenge $y=f(x)$ in the first position, letting $y_1=y$, and choosing the rest of $Y$ itself. Clearly, $B$ outputs the preimage $F^{-1}(Y)$ if and only if $y$ belongs to the “special” set, which occurs with probability $\varepsilon(n)$. Therefore, $A$ succeeds in outputting the preimage $f^{-1}(y)$ with the same probability $\varepsilon(n)$. But this is not enough: we need $A$ to succeed with much larger probability $1-1/p(n)$.

If $A$ repeats its procedure many times, always letting $y_1=y$ but changing the other $y_i$, the probability of success would not improve: whether $B$ inverts $Y$ or not depends only on the value of $y_1=y$, and this does not change. (Remember, $A$ gets only one challenge value $y$ and needs to invert on it with high probability.)

The correct reduction and proof circumvents this problem by showing that there must exist some position $i$ for which there is a large $1-1/p(n)$ fraction of $y_i$ such that, if we choose the other $y_j = f(x_j)$ at random as described, then $B$ inverts on that $Y$ with non-negligible probability (over the choice of the $y_j$ alone). By guessing such $i$ at random (or enumerating all of them) and repeating the core procedure many times, we can ensure a high probability that $B$ actually inverts on one of the $Y$ we provide it, thereby telling $A$ a preimage of $y$. (The actual proof does not depend on $f$ being injective.)


Generating unbiased numbers with a biased six sided die?

Each biased die result has >2.52 bits of Shannon entropy. Each unbiased die result has <2.59. So 21 biased rolls have more entropy than 20 unbiased ones.

Alice can concatenate 21 biased results into $r$ and use $r_i = H(s||r||i) \bmod 6$ as the unbiased results, where $H$ is a hash function like SHA-256 and $s$ is a unique salt she decides just before rolling.

(If Alice wants to cheat, she must use >$2^{52}$ work to find an $s$ with biased outputs. If this is insufficient, roll more dice or decide $s$ in a way that does not allow this.)


The general idea is that either one of the inner hashes, or the combining hash must collide, since there is not other place to introduce the collision.

Assume we found a collision for H. This means we have X, Y with $X \neq Y$ such that:

$h(h(X_0)||h(X_1)) = h(h(Y_0)||h(Y_1))$

Now we define: $A = h(X_0)||h(X_1)$ and $B = h(Y_0)||h(Y_1)$

This gives us a new equation h(A) = h(B)

If $A \neq B$, we found a collision, and are done.
If $A=B$ we know that $h(X_0)||h(X_1) = h(Y_0)||h(Y_1)$, which we can split into $h(X_0)=h(Y_0) \land h(X_1)=h(Y_1)$. From $X \neq Y$ follows $X_0 \neq Y_0 \lor X_1 \neq Y_1$. Thus at least one of $h(X_0)=h(Y_0)$ and $h(X_1)=h(Y_1)$ has different inputs on both sides of the equation, and thus represents a collision.


What is the cost of encrypting of long message with public-key cryptography?

The real problem is not the encryption or even the decryption of an encryption scheme with huge values, it is the generation of the key:

For RSA, ElGamal, Paillier, etc. you need one or more large primes, which make up a modulus for your computations. In practice, you can find large primes by using the Miller-Rabin primality test. It has a run time of $O(t \log^3 n)$, and for large numbers it can be improved to $O(t \log^2 n)$ if using FFT-based multiplication. $t$ notes the number of test runs and you have an error rate of $1/4^k$, where the test says prime for a coposite number. While the runtime with multiplication optimazation has the smaller exponent, the Big-O notation does hide constant factors, and I don't know where the break-even is, but let's just assume the current crypto libraries already use the optimzation.

As a reference in this SO answer generating a $2048$ bit RSA key (which is generating two $1024$ bit primes and a tiny amount of its computation time to find $e$ coprime to $\phi(n)$ and calculating $d$) takes around $1$ sec. So $\approx 0.5s$ for a $1024$ bit prime.

If we want to increase the size by a factor $a$, then the Miller-Rabin test takes $a^2$ times longer. However, we also need to test $a$ times as many numbers on average to find an actual prime number. Example: A random $1000$ bit number is prime roughly with probability $1/ln(2^{1000}) = (\log 2)/ 1000$ and we need on average $1000/(\ln 2)$ tests to find a prime, a random $2000$ bit number is prime with probability $(\log 2)/2000$, and on average we need to test $2000/(\ln 2)$ numbers to find a prime. This means, we expect to run the algorithm on $a$ times as many numbers to find a prime.

For example, for a prime with $1 M$ bits for example and an estimate of $0.5$ sec for a $1024$ bit prime, we have a factor of $~976.5$ in size, so the runtime for Miller-Rabin itself is $0.5 \cdot 976.5^2$, and we need to test $976.5$ as many values, resulting in an overall runtime of $\approx 465 M$ seconds, which is around $14.76$ years.

In case you want to use RSA you need two of these primes, so after 30 years you have a RSA modulus with $2,000,000$ bit, which allows you to encrypt $0.25$ MByte of data in one piece. Of course using a large computing center will speed this up, but the real problem is the size, since I guess you didn't have $0.25$ MB of data in mind when you wrote "potentially very large".

Edit:
The encryption and decryption scale much less from the size increase. For RSA, you can still use a small exponent in the encryption, this doesn't have to be much larger than current ones. That means the number of steps in square-and-multiply are roughly the same, just each multiplication and modulo operation takes more time. Decryption then involves a number of length of the modulus, but overall it is still quadratic at worst, and much less than prime generation.


Are there any Implementations of Secure Indexes?

Cryptdb has a search component which implements techniques from this paper this might be helpful to get some insights and get started , cryptdb is open sourced code is available


How can I break a Vigenère cipher with partial plain text?

First guess the key length(Just try every plausible length, there aren't many).

Then for each position where you know both plain- and ciphertext, calculate the key char. If you get a contradiction, the guessed key length was wrong.
If the key length is short enough compared to the number of known pairs this will probably give you a large part of the key.


AES CBC encoding of decomposable OAuth2 tokens

It probably is doing some good, although there's probably

a simple attack, depending on how long your fields are.

You should use a MAC or authenticated encryption, depending on whether or not you

want to keep $\:$ username + start timestamp + end timestamp $\:$ confidential from someone

who gets access to a user's computer while that computer has a token from your site.


Is PKCS7 a signature format or a certificate format?

So is PKCS7 a signature format or a certificate format or both?

Neither. PKCS7 is now Cryptographic Message Syntax(CMS). From the RFC 5652:

  This
     syntax is used to digitally sign, digest, authenticate, or encrypt
     arbitrary message content.

CMS enables interoperability between different products which can operate on the same document without knowing anything about other product (implementation and such other specific info related to the product). CMS achieves this by defining specific message formats for each data type (signed data, enveloped data, authenticated enveloped data). Hence, each product which support CMS format can exchange files or messages defined in the CMS format with no trouble.

The second link you provided also talks about CMS format.

After comments from @Maarten:

It is also worth to mention that PKCS stands for "Public Key Cryptography Standards". These are a set of public key cryptography standards created by RSA Security Inc. Some of these standards handed over to standards organizations and they became industry standards after that.

Also, as @Maarten mentions, using CMS(PKCS7) format enables storing more than one certificate. (Check this answer)


A well-formed XML document is subject to all sorts of constraints.

You can incorporate these constraints into a function that checks a base64 substitution key by looking for invalid syntax, such as improperly nested tags, or a tag name containing control characters, white space, or any of the characters !"#$%&'()*+,/;<=>?@[\]^`{|}~, or that starts with a dot, hyphen or numeral.

Combine this with a backtracking search algorithm, and with a bit of luck you should obtain a solution within a reasonable amount of time.

If it turns out to be too slow, there are other assumptions you could make. For example, most XML documents use only printable ASCII characters in their tag names, and often contain white space after closing tags.


How Secure is gpg Command Using Symmetric AES-256 From Being Cracked

GPG's AES-256 symmetric encryption is believed to be as secure as it is difficult to

guess the passphrase
or compromise the machine used to perform encryption and decryption.

Guessing the passphrase should be harder if one uses

gpg --s2k-mode 3 --s2k-count 65011712 --s2k-digest-algo SHA512 --s2k-cipher-algo AES256

or equivalently puts in the gpg.conf file:

s2k-mode 3
s2k-count 65011712
s2k-digest-algo SHA512
s2k-cipher-algo AES256

These options increase (to about the maximum possible per the OpenPGP format) the amount of processing to transform a passphrase into a key, hence the resistance to brute-force passphrase search. This is not a substitute to using a hard-to-guess passphrase, but does help significantly.

When encrypting to self, it still makes a lot of sense to use asymmetric encryption: that allows to encrypt without a passphrase, limiting its possible leak to decryption. I use this for automated backups in the cloud (with a different asymmetric key to sign the backups). I can confidently say that nothing on the machines doing the backups allows to decipher the backups.


If you are dealing with encryption using user-provided passwords, the resulting ciphertext might be attacked using pre-computations à la "dictionary attack", which is the same kind of attacks we are trying to mitigate when using a salt to store passwords.
When encrypting with user provided passwords, the KDF is used as a mean to compensate for the poor entropy of the user passwords, but because you cannot consider the salt to be a secret and you have to provide it to the decrypting party in some way, if you use a salt you will not necessarily increase the "entropy" of your password, because an attacker could simply use the same salt to try and brute-force your key.
In the same manner, a dictionary attack against encrypted data would still work by simply using the same parameters and salt as you do, since these are supposed public (and is even easier if you have a known plaintext-ciphertext pair).
So in the end, you should still be worried about making a dictionary/brute force attack as costly as possible and this is possible with modern KDF such as Argon2 or Balloon, where you can set the parameters, which can be publicly known, in such a way that the attack will become more and more time consuming and costly for the attacker.
So effectively, I agree with you that the salt is not necessarily useful for your use-case, since having a larger initial, secret entropy is more important to protect your data.
But still notice that having a single hard-coded salt will be detrimental to you in the sense that it allows an attacker to "pre-compute" its tables or dictionary attacks for all of your ciphertext at once. This means that using a fixed salt makes the act of cracking multiple ciphertexts on average less costly.
So your use-case benefits from using a KDF, (not just a hash function), with a large iteration number to increase the cost of an attack, and benefits also from using a different random salt for each encryption in order to avoid "pre-computation" attacks that can target all ciphertexts at once. This effectively means each ciphertext would require its very own precomputations and thus it boils down to a bruteforce in the end.
PS: notice that dictionary attacks are only useful when the adversary is able to tell easily whether she has found the correct key or not. Which is typically the case in known plaintext attacks, but not always true for all use-cases.
PPS: I'm not mentioning the pepper since you're aware of its existence given your other question. But a pepper is typically useful in that kind of use-case. Note that the salt, when considered secret is basically a pepper.


You're close with the idea of using an envelope; the standard answer is to use a commitment scheme; this is a scheme where someone can publish a 'commitment' to a value, and then later revealing what that value was.  The two essential properties of commitments are:

Someone just looking at the commitment cannot tell what the secret was
Someone with the commitment cannot reveal a value other than the value that was committed to.

How this works in this scenario is exactly analogous to your envelope method; Alice selects a random bit, and publishes a commitment to that bit.  Bob then selects a bit (there's no need for a commitment there) and publishes it; Alice then reveals the bit she committed to; the exclusive-or of Alice and Bob's bit is the output.

Now, there are a number of practical commitment schemes known.  The easiest is to use a cryptographically secure hash function; Alice selects a large random value $A$ and publishes the hash value $hash(A)$.  Bob then selects his bit and publishes it; Alice then publishes $A$ (and they use, say, the lsbit of $A$ is Alice's bit).

Looking at $hash(A)$, Bob gets no information on what the lsbit of $A$ was (assuming Alice selected a sufficiently large bit string).  This is not a formal requirement of cryptographically secure hash functions, but is a reasonable assumption with real hashes (especially if Alice chooses an $A$ which is longer than the hash function output).

And, assuming that we're using a cryptographically secure hash function, Alice cannot decide to reveal a different value $A'$; if she could, that would mean that Alice found a hash collision $hash(A) = hash(A')$, and we assume Alice can't do that.


Secret sharing between a very large number of participants

Is there an algorithm that can realistically generate keys for value of k between 1,000 and 1,000,000?

How about Shamir's Secret Sharing method?

For $k = 1000000$, generating a share would take a million field operations (multiplications and addition); this can be done in a few milliseconds per core (depending somewhat on the field you pick; there are CPU friendly ones out there).  Obviously, for the shares to be usable, you'll need to generate at least a million of them; this could be done in circa an hour on a laptop; that doesn't sound unrealistic to me.

If taking an hour to generate a million key shares is too expensive, what are the performance requirements?

Combining $k$ shares to reconstruct the secret takes $O(k)$ field operations; this is obviously quite reasonable; actually loading the shares is going to be the bulk of the work.


Does Runge phenomenon affect Shamir's secret sharing scheme?

No, the Runge phenomenon is known not to affect Shamir's scheme.

Remember, the point of Shamir's scheme is not actually to form an approximation over an interval; instead, it's to encode a secret in a randomly chosen polynomial, and then divide up clues to that polynomial so that, with enough clues (shares), someone can reconstruct the entire polynomial (and hence recover the secret).

(Now, in practice, we don't bother reconstructing the entire polynomial; instead, we just recover the coefficient that is the secret.  However, that's just a detail; we could, if we wanted to, recover the entire polynomial).

So, in terms of accuracy, the question is "do we recover the polynomial with sufficient accuracy so that we can uniquely identify the secret".  And, the answer to that is, yes, we can (because computation in Finite Fields are done precisely, with no rounding errors).


Trouble understanding the correctness of this Zero-Knowledge proof of posession of a discrete log

This is "Protocol 2" shown on page 207 of the paper (pdf) referenced.

Maybe I should start from "Protocol 1" that requires (I believe) $s_i = x e_i^{-1}$, not $xe_k^{-1}$.

With step 5, it was explained at Theorem 4, "Correctness" part (that is actually proving soundness property). It starts with a claim of Peggy unable to always produce an acceptable answer $s_i$ for both cases of $b_i$ at step 4. However, this answer does not depend on $x$ and only depends on $\{r_k\}$ chosen by Peggy herself at step 1.

My view is, a better (I believe) protocol was presented next year by (almost) the same team.
For practical purposes, Schnorr protocol would be my choice for this setup.
This paper remains the first to introduce a proof for DL setup/problem.


Can Winternitz be easily converted to a many-time encryption scheme?

Can it also be used as a one-time encryption scheme?

You cannot build asymmetric encryption from just hash functions. There is an impossibility proof for that. So for asymmetric encryption the answer is no. See Merkle Puzzles are Optimal - Boaz Barak, Mohammad Mahmoody-Ghidary for the proof.

For symmetric encryption, you can simply use the hash function directly to build encryption, no need to bother with Winternitz.

But you could use quantum-key-exchange together with hash based signatures to achieve something similar to asymmetric encryption.

Concerning many-time signatures

It's straight forward to build stateful many-time signatures from one-time signatures. Just create as many one time keys you need, compute a hash tree over their public keys and public its root. The hash tree allows you to efficiently prove what the nths public key is and proceed with the one-time signature form there.

But if you don't want to keep track of which one-time signatures you already used, you need a stateless many-time signature. It is possible to build stateless hash signatures, but it's a bit trickier. SPHINCS is a recent example.


The obvious way to construct such a pseudorandom single-cycle permutation is to take a pseudorandom permutation $P$ (which need not be single-cycle), a simple fixed single-cycle permutation $Inc$ (e.g. just increment the value by 1), and construct:

$$S = P^{-1} \ \circ Inc \ \circ P $$

That is, to evaluate $S(x)$, you first apply the permutation $P$ to $x$, then the permutation $Inc$, and then the permutation $P^{-1}$, which is the inverse of the permutation $P$.

Things that should be obvious:

$S$ is a single cycle permutation
Every single cycle permutation can be expressed this way with an appropriate choice of $P$
(Less obvious) if $P$ is selected uniformly over all permutations, then $S$ is selected uniformly over all single-cycle permutations.


montgomery reduction multiplicative identity

The additive identity is $0$, as usual.

The multiplicative identity is the Montgomery representative for $1$, namely $1\cdot R \bmod N = R \bmod N$, just like the Montgomery representative for any other element $x$ is $x\cdot R \bmod N$.


Proof that a particular algorithm has been used

I’m looking for the existence (or the proof of non-existance) of a
method to prove (with arbitrary certainty) that a particular output is
the result of a particular algorithm applied on a particular input.

If by "a particular algorithm" you mean "any algorithm whatsoever", then definitely no such method exists, because before you could establish if an algorithm gave a particular output for a particular input, you'd first have to establish whether the algorithm even halts on that particular input, and the halting problem is well-known to be undecidable. Note that even removing the restriction on not actually running the algorithm wouldn't let you escape from this.
If by "a particular algorithm" you mean "a specific algorithm that I'm thinking of right now" then in general, as was discussed in the comments, if you have a single input and a single output, an infinite number of different algorithms which produce that specific output from that specific input can be constructed, so it's impossible to distinguish between them solely by inspecting those two values.
If, on the other hand, you just want to test whether a given algorithm would have given a particular output for a given input, regardless of whether some different function might also have given the same output, then there are at least some relevant cases where it's not - or shouldn't be - possible. For example, any block cipher should output ciphertext that doesn't leak any usable information about either the key or the plaintext. Even if you have the key and the plaintext, if you can tell a given ciphertext would be produced by them without actually running the encryption (or decryption) function then that function is broken.
In general, if you have all the inputs, all the outputs, and full knowledge of the algorithm, then it's not clear what "zero knowledge proof" would mean here, since you evidently possess all the knowledge you'd need to run the algorithm yourself. There is the concept of a certificate value which can be a proof of an expensive algorithm - for example, you can prove you solved a given discrete logarithm by simply supplying the right exponent, so anybody can easily verify it without going to the trouble of solving it themselves - but this is completely dependent on the algorithm in question.


As Luis Casillas said in his comment, the spec of Salsa is short and well explained. Namely, if you are interested in the expansion function, you can find a description with two examples (one with a 32-byte key, and one with a 16-byte key).

Short answer: when dealing with a 16-byte key, you only have to change a constant and append the key to itself.

More details bellow.

Salsa keystream generator, noted $Salsa20_k(n)$ for a key $k$ and a nonce $n$, is based on a hash function : $hSalsa20$ (called $Salsa20$ in the spec). This hash function works as follow :
if $x$ is a 64-byte sequence, $hSalsa20(x)$ is a 64-byte sequence.

Now, let's see the role of the key and how it is managed. Whether you're using a 32-byte key or a 16-byte key, there is no real key expansion as you can find in Blowfish. Instead, the key $k$ is divided in two 16-bytes subkeys $k_0$ and $k_1$ (if $k$ is 16 bytes long, $k_1 = k_0$). Then, a 16-byte constant is added to the state, and that's where there is a difference : the value is not the same depending on the key size:

for a 16-byte key, this constant is "expand 16-byte k"
for a 32-byte key, this constant is "expand 32-byte k"

This constant is divided into 4 equal part, let's call them $\sigma_0,\sigma_1,\sigma_2$ and $\sigma_3$, 4-byte each.

The keystream is produced as follow :
$$Salsa20_k(n) = hSalsa20(\sigma_0\ ||\ k_0\ ||\ \sigma_1\ ||\ n\ ||\ \sigma_2\ ||\ k_1 || \sigma_3)$$
 where $||$ denotes the concatenation.

Notice that in both case, the argument of $hSalsa20$ is 64-byte, so 64-byte of keystream is produced. You only have to increment the nonce, and start over to generate more keystream.


What is difference between Cryptographic Transformation, Encryption and Hash?

Usually a cryptographic transformation can mean anything. It is just a cryptographic function whose output is based on the input, $K$ and $R$ in this case. You could have a $MAC(K, R)$ where the transformation is a message authentication code or MAC for instance. A MAC also takes a key and a message, but its purpose is rather different.

So $K\{R\}$ is a specialization of $f$. Often $K\{R\}$ it is written down as $E(K, R)$ which would probably make this more clear (although $E_k(R)$ is also often used).

It could also be that $K\{R\}$ is the keyed encryption function, taking just the input $R$ while $f(K, R)$ is the uninitialized or stateless cipher taking both the key $K$ and the input message $R$. If the math notation is not precisely specified you may have to rely on context.


A confusion on the proof of Yao's theorem (Yao 82)

He's doing a pretty poor job of expressing a very simple idea here, which is that if there exists a distinguisher $D$ for which $Pr\lbrack D(H^{i-1})=1\rbrack$ > $Pr\lbrack D(H^{i})=1\rbrack$ (which means the advantage is negative before taking the absolute value), there also exists a distinguisher $\overline{D}$ for which $Pr\lbrack D(H^{i})=1\rbrack$ > $Pr\lbrack D(H^{i-1})=1\rbrack$ (i.e. the advantage is positive before taking the absolute value) by just defining $\overline{D}(H^*) = 1-D(H^*)$ for $H^* \in \{H^i,H^{i-1}\}$. Informally, this distinguisher runs $D$ on its input and just flips whatever $D$ outputs.

Thus, w.l.o.g. we can assume the distinguisher has a higher probability of outputting a 1 given a sample from $H^i$ than from $H^{i-1}$, which means we don't need the absolute value.


What is the reason of using Pedersen Commitment scheme over HMAC?

In this case, there probably is no difference.

The Pedersen Commitment scheme is often used in cryptographic protocols because:

It allows zero-knowledge proof to prove some properties of the committed value.
It is perfectly hiding, which can be important in proving the security of the protocol.

Hash based commitment schemes do not have the above two properties. However, they may be more efficient and are preferable in certain scenarios.


Strategy to crack a presumed substitution cipher

There are different approaches to crack a substitution cipher.

A human would use a different strategy than a computer. But as the word boundaries are not preserved it will be rather challenging for a human solving this cipher.

The quipqiuq tool mentioned by John is using word lists, but there are other methods as well.

Resources:

http://reflectionsonsecurity.files.wordpress.com/2011/03/fast-reliable-cryptanalysis-of-simple-substitution-ciphers.pdfThis paper proposes to use the genetic algorithm.
http://practicalcryptography.com/cryptanalysis/stochastic-searching/cryptanalysis-simple-substitution-cipher/Describes how to crack a substitution cipher using the hill-climbing algorithm.
http://www.cryptoden.com/programs/Ari_Pat_WW.htmlThis solver is using the hill climbing approach. The good thing is that you can study the Javascript code. I think this tool expects the cipher text in upper cases.
http://www.guballa.de/pages/geocaching/substitution-solver.phpThis solver uses the hill climbing approach as well.

Note: If feeding your cipher text one of the online tools above you will notice that the word "sherlock" was used to generate the cipher alphabet.


Proof that perfect privacy implies that the number of keys is at least the number of messages

Let $K$ be the set of all possible keys (for AES-256, this set has $2^{256}$ elements.)
Let $M$ be the set of all possible messages (for AES, it has $2^{128}$ elements).
Let $C$ be the set of all possible cipher texts (for AES, again $2^{128}$ elements).

I was reading a proof to the statement:

Perfect privacy implies that $|K|=|M|$

Actually this is $|K| \ge |M|$.
Perfect privacy condition is:
that for all $m$ and $m′$, $P_{k \in K}[e(k,m)=c]=P_{k \in K}[e(k,m′).=c]$
the probability that a cipher text $c$ is decrypted as $m$ is the same as being decrypted in $m'$.
Or in other words:
you can't find a difference between $m$ and $m'$.
In order to prove such statement you use reductio ad absurdum. Here you assume $|M| > |K|$.

The first thing that I don't understand is the following notation: $p_{k \in K}[e(k,m)=c]>0$. What exactly does this mean ?

Yes the $p$ is a typo and should be $P$. It means that there exists $k$ and $m$ such as $e(k,m)=c$ (which is trivial because we need a working algorithm...). Therefore the probability that given a $c$, $m$ is the plain text is at least $\frac{1}{|M|}$ (assuming a uniform distribution), hence $> 0$.
About this part:

Therefore $P_{k \in K}[e(k,m′)=c]=0$
Does this mean that the probability that we encrypt $m′$
using $k$ results in the cipher $c$ is equal to $0$ because, as said before in the proof, $m′$ is a message that has no key $k$ that transforms it into $c$? If yes, I am still not 100% convinced.

The first thing you must think of is that the $c$ is fixed. In order to encrypt a message $m$ to this $c$ you need a key $k$. Because $|M|$ is greater than $|K|$ (assume $|M| = 5$ and $|K| = 3$), there exists messages that won't have a mapping to $c$ (in this case $5 - 3 = 2$). Therefore there exists $m'$ such as there is no $k$ so that $e(k,m) = c$. Hence $P_{k \in K}[e(k,m′)=c]=0$
Because the statement of perfect secrecy is for all $m$ and $m'$ you can't have at the same time all probabilities being $> 0$ and $= 0$. Therefore you have a contradiction.


Is there value in performing signature during key exchange?

As for the first question: as long as you create a signature over some or all data that is required and unique in the key establishment protocol then you should get entity authentication for that session. If you sign entire messages then you may be able to avoid some attacks on the message format itself. Some protocols deliberately include the public key into that calculation, others don't. Including the public key is not strictly required of course, you can also sign over a nonce used in the protocol or even over the shared secret (although I would seriously frown on the latter, as you don't want to use the key material for anything other than what it should be used for).

I'd also make sure that the established secret is correct by validating the generated secret (derive a MAC key and use that to create a MAC over some or all data unique to the session); you don't want to be relying on the messages themselves (implicit authentication) to verify the data and shared secret, use explicit authentication instead. It might be a good idea to start hashing the messages immediately and perform the signing / MAC'-ing over the calculated hash for maximum efficiency.

Yes, you can achieve forward secrecy with libsodium, if - as always - you make sure you destroy the keys as soon as they are not needed anymore. Just performing ephemeral-static DH - using whatever scheme - doesn't cut it, as you must make sure that the key material is not available anymore. Fortunately, Daniel is known for trying to make his protocol implementations in such a way that key destruction is easy.


Build set with PKI from reliable broadcast / random beacon

There might be multiple solutions, and this could be one of them.

You can use multiple rounds of Terminating Reliable Broadcast (TRB). Each party in $S_1$ sends a message with their own proposal $pk$ -- this corresponds to one round of TRB.

After $|S_1|$ rounds, you're good to go. Since all honest parties have the same set of individual proposals, they can deterministically compute the result $S_2$.

Naturally, if you assume $f<|S_1|$ nodes can fail (e.g. by crashing, arbitrary), you have to stop the protocol after $|S_1|-f$ rounds.

PS: I might have misunderstood some of the details in your the question, so please correct me if anything's amiss.


Hash Function - Pre-image resistance and Strong collision Resistance

With the definitions that a function $F$ is

(strongly) collision-resistant when a [computationally bounded] adversary can't [with sizable odds] exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$;

neither form of pre-image resistance guarantees (strong) collision resistance. As to why: there's no argument that such guarantee should hold; and we have counterexamples, both practical (e.g. MD5), and theoretical.

Consider an hypothetical random function $H$ from bitstrings to $k$-bit bitstrings; or a good practical cryptographic hash with $k$-bit output (assuming that exists). This $H$ has all three properties, for large enough $k$. Define another function $F$, as
$$F(x)=\begin{cases}H(\mathtt{“b”})&\text{if }x\text{ is the string }\mathtt{“a”}\\H(x)&\text{otherwise}\\\end{cases}$$
$F$ is not collision-resistant since the strings $\mathtt{“a”}$ and $\mathtt{“b”}$ collide; but is preimage-resistant (in both senses) for large enough $k$.

The above counterexample still works if we use quantitative definitions of the three properties, requiring effort $O(2^{k/2})$ to break collision-resistance, and effort $O(2^k)$ to break preimage-resistance.


Can you defeat AES-CTR's birthday boundary with a 2nd AES?

Yes. The number of $n$-bit blocks you can encrypt with this construction is proportional to $2^n$ instead of just $2^{n/2}$. So for AES this shouldn't be a problem because you can't process anything near $2^{128}$ blocks.

A secure stream cipher can be constructed from a PRF using something similar to AES-CTR.

AES is more accurately described as a PRP than a PRF, but this distinction is unimportant if the number of queries an attacker is allowed to make under a given key is much much less than $2^{64}$.

(See PRF switching lemma. If the number of queries the attacker can make is much less than $2^{n/2}$, then it is safe to substitute an $n$-bit PRP for a PRF. This is where AES-CTR's limit comes from.)

However it has been proven that the XOR of two PRPs is a secure PRF instead for up to $\mathcal{O}(2^n)$ queries. 1 2

Readers should note that this isn't the same as saying that you can use up to precisely $2^n$ blocks. For this reason, I strongly discourage using a block cipher algorithm with smaller blocks (like DES, Simon, or Speck) in this kind of construct. (Or any other mode, I suppose.)


Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key?

This is 100% safe, assuming your 128 bits of entropy is generated properly, and assuming your attacker is only trying to attack one key.

If you did use, say, 17 bytes (136 bits) of entropy for your KDF, then the attacker would simply choose to break the ECC using Pollard Rho, instead of breaking the KDF using brute-force, and in this case they would still not need to do any more than $ 2^{128} $ work. (This is the weakest-point principle in action). This means that using more than 128 bits of entropy to generate a 256-bit ECC key is useless, unless your attacker is trying to break multiple keys.

In that case, using 256 bits of entropy to generate the ECC key would be completely justified, since it prevents certain batch attacks. Daniel J. Bernstein has a great blog post about batch attacks.


Are there known any protocols or algorithms with precisely narrowed time estimate above?

Of course not, because it would depend on the details of the system performing the brute forcing / dictionary attacks. Your comment: "Processor cycle count measurement by brute force breaking scheme" basically contains the answer.

  Is it possible to design such brute force breaking scheme it guarantee that it will be successful after t_min but before t_max?

Same answer of course, but you can certainly create a protocol which requires a certain proof-of-work. And that's precisely what the current block chain technology is all about. But proof-of-work relates to the amount of work performed, not the amount of time that it took.

You could of course also use a trusted third party to release information - such as a key - at a certain time. Not all protocols allow for such a third party to exist though.


For $(t,n)$ where $t=n,$ and where the secret is the vector $Z,$ the XOR based scheme is:

Scheme $\cal S:$

distribute $n$ shares, one to each user, as the binary vectors
$$S_1=X_1,S=2X_2,\ldots,S_{n-1}=X_{n-1},S_n=Z\oplus X_1\oplus \cdots\oplus X_{n-1}$$.
reconstruct $Z$ by computing $S_1\oplus\cdots S_n$.

For $t=n-1,$ one way is to create $n$ different $(n-1,n-1)$ schemes for each of the $n$ subsets of size $t=n-1$. So for the users $1,2,\ldots,n-1$ we can use the scheme

Scheme ${\cal S}(1,\ldots,n-1):$

distribute $n-1$ shares, one to each user, as the binary vectors
$$S_1=X_1,S_2=X_2,\ldots,S_{n-2}=X_{n-2},S_{n-1}=Z\oplus X_1\oplus \cdots\oplus X_{n-2}$$.
these users reconstruct $Z$ by computing $S_1\oplus\cdots S_{n-1}$. .

Note that the sums of the different shares  differ by the xor of two random vectors, in the symmetric difference of the two sets of users, and if these are uniformly generated the required intra-subset security property will hold.

Obviously this multiplies storage and communication by a factor of $n.$


Why are collision attacks important when talking about MAC schemes?

The attack outlined by Drlecter is valid for any deterministic MACs (that is: with the MAC a function of message and key) with an iterated structure and an $n$-bit state. It relies on internal state collisions, expected to occur after about $2^{n/2}$ messages (the birthday bound), that can allow forgery once discovered. I'll illustrate this in the case of CBC-MAC with a 64-bit block cipher (e.g. 3DES) operating on fixed-size 3-block messages (24-byte) with 8-byte MAC (the full block cipher width).

The adversary asks for the MAC of $2^{33}$ messages with random first two blocks and the last block fixed. It is expected that a collision occurs, and the adversary then has $(M_0||M_1||M_2)$ and $(M'_0||M'_1||M_2)$ having the same MAC, with $M_0\ne M'_0$. So far, this is not a break. But notice that, with certainty, the collision has occurred after the second block, and continued after the third.

Now, for any last block $M'_2$, $(M_0||M_1||M'_2)$ and $(M'_0||M'_1||M'_2)$ collide with certainty. That allows the adversary to predict the MAC of one of these messages by querying for the MAC of the other, which is a break.

Thus a deterministic MAC with $n$ bit internal state (and output, but in itself truncating the output does not help much), after $q$ queries with the same key, has become unsafe with odds about $q^2/2^{n+1}$, for $1\ll q\ll2^{n/2}$. E.g. after $2^{60}$ queries, HMAC-SHA1 has odds $2^{-41}$ to be vulnerable.

Note: This attack (or any generic attack with similar result that I am aware of) does NOT in general apply to iterated MACs with an $n$-bit output. E.g. HMAC-MD5 or CBC-MAC-AES truncated to $64$-bit are not awfully vulnerable to this attack; after $2^{40}$ queries odds that the attack works are $2^{-49}$.


Why did NIST remove The Lempel-Ziv Compression test from the Statistical Test Suite?

According to the paper On Lempel-Ziv Complexity of Sequences by Doganaksoy and Gologlu,

  A test based on Lempel-Ziv complexity was used in the NIST test suite, to test the randomness of sequences. However the test had some weaknesses. First of all, the test could only be applied to data of a specified length: $10^6$ bits. Moreover, the test used empirical data generated by SHA-1 (under randomness assumptions) for estimating the expected value of Lempel-Ziv complexity of sequences of length $10^6$ bits. Apparently, the data generated by SHA-1 led to not-so-good an estimate, hence, for instance, first $10^6$ bits of the binary expansion of $e$ failed the randomness test. Using asymptotic formulae for an estimate will not work either, since the sequences, as we will see in the forthcoming sections, are distributed tightly around the mean. Recently, apparently because of the spelt out reasons, Lempel-Ziv test had been excluded from the NIST test suite.

The Crypt-XS package, part of the NIST suite, includes the simply named sequence complexity test, which is based on Lempel-Ziv compression.


How is the quality of a password calculated and what does it mean?

How much entropy is enough?

For a password, something around truly 96-bits of entropy is enough. After all password usually go through some slow password hashing which increases the work load for attacks significantly. And even with a super-fast verification function 96-bit should be just out of reach of attackers.

  How much is overkill?

Going above 500-bit is very likely to be overkill, even for an actually imperfect source of entropy. If your entropy is "true" (ie what is reported would actually be the entropy), then there's literally no point in going beyond 256-bit and maybe even 192-bit.

  How does entropy actually apply to the length of time it may take for
  an attacker to guess a password?

Entropy denotes the uncertainity in a string1 and is measured logarithmically in bits. So if you increase the entropy by one, the string is twice as uncertain and thus can take twice as many values which means an attacker has to try twice the amount of passwords. Shortly put: Let $l$ be the actual entropy (in bits), then there are $2^l$ possible different values to be tried.

  How is entropy calculated and how may my addition of a new character
  affect the number of bits?

What I strongly suspect this tool to be doing is to analyze the character set used in your password, looking for common words in a dictionary and then making its guess for the entropy (try this by comparing the entropy of potat with potato, the latter being reported at 12 bits and the former at 20). The upper bound for the entropy is $$\leq{|\Sigma|}^n$$ where $\Sigma$ is the alphabet / group of characters that the tool estimates could appear in your password and $n$ is the length of the password. For example if you use upper-case it's gonna include those as opposed to excluding them if you don't have an upper-case letter.
Note that what the tool reports is an estimate at best and the actual entropy can be significantly lower due to a bad RNG being used, an implementation flaw or you simply having bad luck and hitting a string that's more easily guessed / guessed sooner by an attacker.

  What is the theoretical max?

Theoretically there's none. Practically it's limited by the size of your RAM probably (because the password has to fit in there).

1Actually the uncertainity in a random variable, but that's details here.


Getting the key used for HMAC given the hash and the plaintext?

Is there any way I can extract the key being used by the hmac function knowing the message, the function used to generate keys and the message digest, that does not involve brute-force?

None are known; this remains true even if you have a huge pile of messages that you picked, and their corresponding HMAC-MD5's.

Collision-resistance for MD5 is completely and utterly broken; we can easily find pairs of messages that have the same MD5 hash, and we have a surprising amount of flexibility in choosing most of the contents of these messages.

However, HMAC does not rely on collision resistance of its hash function; as far as we know, HMAC-MD5 is still secure.  Now, we don't suggest people use it, but that's more of us btrying to get people away from anything that uses MD5, not of any specific known weakness.


Why is lcm(n) used now instead of $\varphi(n)$ in RSA?

Defining the public and private exponents as inverses modulo φ(N), as originally done for RSA, provides a sufficient (but not necessary) condition for the decryption rule to recover the plaintext from any ciphertext. Since Carmichael’s lambda function is, by definition, the smallest number m such that $a^m \equiv 1 \pmod N$, for any integer a that is relatively prime to N. Thus, it is sufficient to define the public and private exponents as inverses modulo any multiple of λ(N).


Side channel security of HMAC in software

I am answering on the basis of this paper (pdf) linked in the comments, as well as some of the related papers it cites or is cited by. I am not aware of more realistic attacks on HMAC.

It assumes a DPA side channel that leaks the number of bits flipped when a new value is read into a CPU register (or in another instruction in some of the papers). I.e. it leaks the Hamming distance between the old value and the new. This allows a direct key recovery attack on HMAC, made easier by the fact that HMAC uses inner and outer keys that are conveniently a known distance apart.

If you assume such a side channel, there is not much you can securely do on the computer. In fact, a typical hardware implementation of HMAC would be almost equally likely to be vulnerable, if you still have to load the key from memory to use it.

  Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?

I do not think it is a matter of software vs. hardware or even side channel protection. If such a side channel as described above exists, there is not much you can do securely on the CPU. Certainly most conventional data processing with secret values has to be rethought.

  If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?

Stronger, in the sense that it is a key-recovery attack, unlike e.g. padding oracle attacks that target CBC. But the assumptions are much stronger as well.

  Would it be possible to retrieve the key used to key the HMAC algorithm?

Yes, assuming.

  Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

Not necessarily. For example, with AES-NI instructions you have to load the AES key into XMM registers, which has the potential of allowing a key-recovery attack in the same manner.

If you have a dedicated crypto chipset that also stores the keys then it may be a different matter. Of course, there is no a priori reason to assume it does not have the side channel too. And you need to get the keys into it securely.


Elligator-2 against curves over Fq, q mod 4 = 3

Most probably, the elligator (hiding in here: Elligator: Elliptic-curve points indistinguishable from uniform random strings – PDF) will jump onto the attackers and bite them, so that they will not risk any further attack.

As an additional security, as described in section 5.1 of the paper, the definition of Elligator 2 is parametrized with a non-square element $u\in \mathbb{F}_q$. So if I understand this correctly, an attacker will not know this parameter $u$ and will thus not be able to decode and encode points of the curve. All the attacker can do is observe a uniformly distributed sequence of bits.


OpenPGP supports an approximation to what you seek, albeit with at best weak privacy guarantees: To transmit the message $m$, Alice picks a session key $k$ and sends $$E_{f_1}(k) \mathbin\| E_{f_2}(k) \mathbin\| \cdots E_{f_n}(k) \mathbin\| \operatorname{AES-CFB'}_k(m),$$ more or less.  Here $\operatorname{AES-CFB'}$ is OpenPGP's bespoke variant of CFB mode.  See RFC 4880, §5.1 for details of how public keys are identified or not.

Decrypting such a message to many recipients is slower, of course, because it requires trying to decrypt every session key encapsulation $E_{f_i}(k)$ with every private key known to the user.  Variants of this scheme with long-term DH-style shared secrets could enable recipients to cache the long-term shared secret under which a per-message session key is encrypted to make this more efficient for many messages.

The privacy guarantees are weak because not every public-key encryption or KEM scheme provides the property called key privacy or key anonymity.
For example, it is feasible for an adversary to distinguish a collection of RSAES-PKCS1-v1_5 ciphertexts (or RSAES-OAEP, but OpenPGP uses PKCS#1 v1.5) under a target public key from a collection of ciphertexts under any other public key, by solving the German tank problem.

You could use a nonstandard RSA-KEM encryption procedure as follows: Pick $1 < x < n$ uniformly at random, compute $y = x^3 \bmod n$, reject and start over if $y \geq 2^{\ell - 1}$ where $2^{\ell - 1} < n < 2^\ell$, and otherwise yield $y$ as the encapsulation of $k = H(x)$.  The encapsulation $y$ is uniform random in $\{2,3,4,\ldots,2^{\ell - 1} - 1\}$, so it reveals nothing about which $\ell$-bit modulus is used.*  This variant is slower than standard RSA-KEM, but the expected number of trials to pick $x$ is under 2, and decryption remains the same as standard RSA-KEM.  Bellare et al. suggest a corresponding variant of RSAES-OAEP which they dub RAEP.  The security is essentially the same as RSAES-OAEP.  Probably the same could be done in OpenPGP with RSAES-PKCS1-v1_5 by trying a different session key, but you are limited to a single recipient in that case.

Other cryptosystems may naturally provide key privacy, such as ECIES and variants where the appendix is a uniform random element of a standard group.  But it's not a standard criterion for public-key encryption/KEM schemes, so it takes further scrutiny than standard security advertisements to be confident that any particular cryptosystem you use provides or can be adapted provide key privacy.

* Note that there are many ways to generate RSA keys.  In an attempt to generate a 2048-bit modulus $n$, some methods pick 1024-bit primes $p$ and $q$ uniformly at random, and with nonnegligible probability will yield for $n = p\cdot q$ a 2047-bit modulus instead of a 2048-bit one.  In this case, by rejecting $y \geq 2^{\lfloor\lg n\rfloor}$ you would partition the anonymity set of recipients into two: the 2047-bit moduli and the 2048-bit moduli.  If this concerns you, you could (say) reject $y \geq 2^{2046}$ for any 2047- or 2048-bit moduli.  This will increase the rejection rate, but at worst it will double.


Reverse Shamir's Secret Sharing Algorithm?

Let's first recall the normal construction for Shamir's Secret Sharing:

We work in a finite field $\mathbb{K}$. This will usually be $\mathbb{F}_{256}$ (the binary field with 256 elements), so that the sharing can be conveniently done on a per-byte basis. We want an $m$-out-of-$n$ scheme, so the finite field must have at least $n+1$ elements. For each value to share, a random polynomial $P \in \mathbb{K}[X]$ of degree at most $m-1$: we write $P = \sum_{i=1}^{m-1} p_i X^i$ where the $p_i$ are chosen randomly and uniformly in $\mathbb{K}$, except for $p_0$, which we set to the secret value to share.

Thus, $P(0) = p_0$ is the secret value. The "shares" are $P(v_1)$, $P(v_2)$... $P(v_n)$, where the $v_j$ values are $n$ distinct non-zero elements of $\mathbb{K}$, that are chosen arbitrarily through a fixed, public convention (exactly which convention is used does not matter).

To retrieve the secret out of $m$ shares, we really rebuild the polynomial $P$, using Lagrange's polynomials. Let $N_i \in \mathbb{K}[X]$ be the following polynomial:
$$ N_i = \left(\prod_{1\leq j\leq n, j\neq i} (X - v_j) \right) $$
It is easily seen that $N_i(v_j) = 0$ for any $j \neq i$, but $N_i(v_i) \neq 0$. We thus define the Lagrange polynomial $L_i = N_i / N_i(v_i)$; it has value $1$ on $v_i$, and $0$ on all other $v_j$.

Then, $P$ is reconstructed as a linear combination of the Lagrange polynomials. If we have shares $P(v_1)$, $P(v_2)$,... $P(v_m)$, then we can write:
$$ P = \sum_{i=1}^{m} P(v_i) L_i $$
Therefore, the secret is:
$$p_0 = P(0) = \sum_{i=1}^{m} P(v_i) L_i(0)$$

In a practical implementation, the coefficients $L_i(0)$ will be precomputed, and the reconstruction needs not bother with actually rebuilding the polynomial $P$; it just recomputes the secret $p_0$ as a linear combination of the shares $p_i$.

Now, let's examine the problem at hand: you have $k$ predefined "shares" and want to use them in a secret sharing. To do that, you simply apply the reconstruction above, and use fresh random values when needed. In other words, you first declare that the polynomial $P$ really exists, and that the $k$ predefined shares are $P(v_1)$, $P(v_2)$,... $P(v_k)$. You then generate randomly and uniformly $m-k-1$ extra shares, which you call $P(v_{k+1})$, $P(v_{k+2})$,... $P(v_{m-1})$. Finally, you define that your secret value is $P(0)$. At that point, you have the evaluation of $P$ on exactly $m$ values ($0$, and the non-zero elements $v_1$ to $v_{m-1}$). You then define new Lagrange polynomials for a set of values that include $0$:
\begin{eqnarray*}
N'_0 &=& \prod_{1\leq j\leq m-1} (X - v_j) \\
N'_i &=& X \prod_{1\leq j\leq m-1, j\neq i} (X - v_j) \\
L'_0 &=& N'_0 / N'_0(0) \\
L'_i &=& N'_i / N'_i(0) \\
\end{eqnarray*}
At that point, you can find $P$:
$$ P = P(0) L'_0 + \sum_{i=1}^{m-1} P(v_i) L'_i $$

What happened here is that you rebuilt a polynomial $P$ that matches your predefined shares and the target secret value; you also generated new random shares in order to have enough value to make a unique candidate for $P$. Now that you have the polynomial $P$, you can compute as many extra shares $P(v_i)$ (for $i\geq m$) as you need.

Some extra notes:

If $k < m$, you can still choose the secret value, as shown above. It does not need to be "something random". If you do not want to choose the shared secret, you can simply create $m-k$ extra shares (instead of $m-k-1$) and use the normal Lagrange interpolation to get $P$, at which point you can obtain $P(0)$ as the shared secret. The computations always work, for all input values (that's how the scheme is secure, indeed). This would also be the situation if you started from exactly $m$ predefined shares: if you want a threshold of $m$ and already have $m$ shares, then there is no room for choice of the secret.
In all of the above, I used $P(0)$ for the secret, but that's purely conventional. $0$ is not special here. The gist of Lagrange interpolation is that, for any set of values $P(v_i)$ on $m$ different field elements $v_i$, there is a unique matching polynomial $P$ of degree less than $m$ (i.e. a polynomial that can be represented as $m$ coefficients).


First let's write the original relation that they are deriving this one from:

$$
W_i = A_{i+1} - (A_i \lll 5) - f(A_{i-1}, A_{i-2} \ggg 2, A_{i-3} \ggg 2) - (A_{i-4} \ggg 2) - K_i
$$

So, if everything in the state bits are fixed except the ones in position $j+2$, all the operations on the fixed bits could be gathered together and we can simplify the relation to the variable ones. Now, let's derive the new relation.

For now, let's put the $c_i^j$ aside and write the term related to $f$. Then the variables in $A_{i-2}$ and $A_{i-3}$ (which are $a_{i-2}^{j+2}$ and $a_{i-3}^{j+2}$) are mixing with the fixed value of $A_{i-1}$ (which is $a_{i-1}^j$), and the rest is fixed. Thus the term $f(a_{i-1}^j, a_{i-2}^{j+2}, a_{i-3}^{j+2})$, and the result is in position $j$, so the $\ll j$ is added. We can add the term $(a_{i-4}^{j+2} \ll j)$ (corresponding to the last term in original relation).

The remaining terms can be collected in the $C_i^{j..0}$. Although both of the $A_{i+1}$ and $A_i$ have variable bits at position $j+2$, they do not contribute to the value of bit positions $j..0$ of $W$. The only way they get involved is that by left rotation of ($A_i \lll 5$), the variable bit gets rotated and falls in $j..0$. It happens if $(j+2) + 5 > 31$, but they restrict the $j$ to $0\le j \lt 25$, so it doesn't happen.

And about the $E_i$ relations. Your relation is not quite right.
We know that:
$$
W_{i+16} = (W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i) \lll s
$$
Therefore:
$$
W_{i+16} \ggg s = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i
$$
and in other words:
$$
W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s) = 0
$$
if there is no error in calculating $W_i$s.
So they define the error bit vectors as:
$$
E_i = W_{i+13} \oplus W_{i+8} \oplus W_{i+2} \oplus W_i \oplus (W_{i+16} \ggg s)
$$
with the goal of making all $E_i$ equal to zero.


Length of ElGamal signature compared to RSA signature

Mistakes happen.

The author's scheme adds a signature about twice as large as $p$, when RSA signature (of the textbook variety of the reference) adds a signature about as large as $n$. It is clearly assumed that the public prime modulus $p$ is about the size of the RSA public composite moduli $n$.It follows that the size of the signature in the proposed scheme is twice that in RSA.


New to cryptology, studying Message Authentication Codes

First, terms: A MAC is a generic term for a class of cryptographic primitives. It's in the same category as "hash" or "PRNG." HMAC is a particular construction that, combined with a suitable cryptographic hash, gives a secure MAC function (it can also be used to generically refer to any HMAC algorithm, since HMAC is secure with pretty much any standard hash, even MD5). A similar term in symmetric encryption is "CBC mode;" it's a way to take a certain kind of primitive (hashes for HMAC, block ciphers for CBC) that does one thing and get it to do something else. MIC is a term used rarely, but basically means is a synonym for MAC; MIC is what some standards (like WPA) call their MAC, because the term "MAC" already has a meaning in those contexts (in WPA's case, this is MAC addresses). "Integrity" implies "authentication" in security-land; MICs need keys as well.

To your first question: MACs verify that the message did come from a specific source (someone with the MAC key). What they don't verify is that it hasn't been intercepted and passively eavesdropped. They're meant to protect integrity, not confidentiality; you use encryption to protect confidentiality. In general, you have to keep your MACs confidential; a MAC can leak information about what was MACed. Privacy-protecting MACs don't themselves leak info about what was MACed, but you still need to encrypt the plaintext.

To your second: It's complicated. Encrypt-then-MAC is generally considered the best (the MAC then can't leak info about the plaintext, and protects against tampering of the ciphertext; all an attacker can do is mess with the ciphertext, they can't touch the plaintext directly); however, Encrypt-and-MAC (MAC the plaintext and do not encrypt the MAC when you encrypt the message) and MAC-then-Encrypt (MAC the plaintext, then encrypt everything) can work.

You also have to think about how the MAC algorithm works with the encryption algorithm, and here be dragons. The best practices are to use a different key for your MAC and your encryption (which normally rules out negative interactions between them), or to use a known-secure construction like GCM to provide both. If you're combining a MAC and an encryption scheme, it's common to use a key-based key derivation function to create the MAC and the encryption keys from a single session key; HMAC is also a pretty good KBKDF (it has a lot of nice properties that aren't really needed for a MAC role).


RSA keys are multiplicative inverse in mod phi(n), but also in mod n?

I understand that the RSA keys $pk$ and $sk$ are chosen such that one is the multiplicative inverse of the other, in $\bmod \phi(n)$

Mostly correct.  Actually, they're always multiplicative inverses modulo $\lambda(n) = \phi(n) / \gcd(n)$; selecting them as inverses modulo $\phi(n)$ does work (they will encrypt and decrypt properly), but using the smaller $\lambda(n)$ also works, and yields smaller key values.

  $pk$ and $sk$ must also be multiplicative inverse to each other in $\bmod n$, right?

That is wrong; $pk \cdot sk \bmod n$ need not be any specific value; there's no reason it needs to be 1.  One trivial example is $n = 85, e = 5, d = 13$; in this case, $e$ is not relatively prime to $n$, hence it doesn't have a multiplicative inverse.

After all, when you look at ${m^{pk}}^{sk} \bmod n$, you're not multiplying by $pk$ or $sk$; you're raising $m$ to the power of $pk, sk$; those are different operations.


does SHA* collide more or less than a random function?

If we could prove anything one way or another about this, it would be a remarkable result worthy of publication in a cryptography journal, since—except for length extension issues in MD hashes—we usually expect these collision-resistant hash functions to behave like good little random oracles.

Of course, there are other families of functions which are not collision-resistant but from which random choices of function have bounded collision probability, namely universal hashes like Poly1305 and GHASH.  We can use these as building blocks for fast authenticators or PRFs.  But I don't think you were asking about those.


Developing algorithm for detecting plain text via frequency analysis

As otus suggests in the comments, it's better to first calculate the frequency of each letter in the decrypted message, and then compare the frequency distribution to what would be expected for English text.

For the comparison, you can use chi-squared ($\chi^2$) testing.  (Actually, for just comparing the likelihoods of different decryptions, you don't even need the complete test.)  To do this, start by comparing the actual observed number of occurrences $N_{\rm obs}(c)$ of each character $c$ in the decrypted message with the expected number of occurrences $N_{\rm exp}(c)$ of that character in a piece of English text of the same length (i.e. its expected frequency times the length of the message), and calculate the test statistic $$\chi^2 = \sum_c \frac{\left( N_{\rm obs}(c) - N_{\rm exp}(c) \right)^2}{N_{\rm exp}(c)},$$ i.e. the sum of the squared differences between the observed and the expected frequency, divided by the expected frequency.  The smaller this $\chi^2$ is, the more closely the decrypted message resembles English.*

Here's some basic JS code to calculate $\chi^2$ for English ASCII text:

// http://en.algoritmy.net/article/40379/Letter-frequency-English
var english_freq = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,  // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,  // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,  // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074                     // V-Z
];

function getChi2 (str) {
    var count = [], ignored = 0;
    for (var i = 0; i < 26; i++) count[i] = 0;

    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if (c >= 65 && c <= 90) count[c - 65]++;        // uppercase A-Z
        else if (c >= 97 && c <= 122) count[c - 97]++;  // lowercase a-z
        else if (c >= 32 && c <= 126) ignored++;        // numbers and punct.
        else if (c == 9 || c == 10 || c == 13) ignored++;  // TAB, CR, LF
        else return Infinity;  // not printable ASCII = impossible(?)
    }

    var chi2 = 0, len = str.length - ignored;
    for (var i = 0; i < 26; i++) {
        var observed = count[i], expected = len * english_freq[i];
        var difference = observed - expected;
        chi2 += difference*difference / expected;
    }
    return chi2;
}

If you're only interested in finding the most likely decryption(s), that's all you need to do.  Just sort the decryptions (and corresponding candidate keys) by $\chi^2$ in increasing order, and print out the first few entries.

If you also wish to estimate the actual likelihood of the message being English (or, rather, the likelihood that picking random letters with frequencies matching English text could yield such a message), you'll also need to determine the number of degrees of freedom $k$ for the model (which, for a simple model like this, is simply the size of the plaintext alphabet minus one**) and then integrate the chi-squared distribution for $k$ degrees of freedom up to $\chi^2$ (or just compare it to a precalculated table).  But just for comparing the likelihood of different decryptions, the raw $\chi^2$ value is enough.

*) You have to calculate this sum over all the letters in the alphabet, including those that don't actually occur in the message, for which $N_{\rm obs}(c)$ simply equals $0$.  Conversely, any characters that don't occur in your frequency table would, in principle, have $N_{\rm exp}(c) = 0$, and thus yield $\chi^2 = \infty$ if they occur in the message.  In practice, to avoid such infinite results, you may wish to either ignore such characters or assign them some more or less arbitrary small frequency.  One reasonable choice, if you're compiling your own frequency tables from a corpus of text, is to use additive smoothing by incrementing the observed count of each character in the corpus by one.

**) The one degree of freedom is lost because the sum of the character counts must obviously equal the length of the message, which is fixed a priori.  Thus, we're not completely free to choose how many times each character occurs in the message; having chosen all but one of the counts, the last count is unique determined by the others.


Finding RSA private exponent with a chosen ciphertext attack?

Is there any way, using some form of CCA or whatever the sort, to recover the primes/private exponent of the RSA key?

TLDR: No, save for a breakthrough or a leak.

Whether $N$ can be factored (in time polynomial to $\ln N$ with non-vanishing probability) given $(N,e)$ and an RSA decryption blackbox (assumed free of side-channel leakage) is one of the most thought at open problem in cryptography, and to a lesser degree in number theory.

Proving either yes or no would make the news, even if restricted to an heuristic algorithm, plausible mathematical hypothesis, a polynomial of degree so high that the method is impractical, and a particular choice of $e$. I'm thinking of $e=3$, or $e=N$ (the Clifford Cock's cryptosystem, which predates RSA), or on the contrary random odd $e\in[0,N])$.

A proven fact is that extracting any working private exponent $d$ of size upper-bounded by a polynomial in $\ln N$ allows to extract a factor of $N$, at least heuristically and in heuristic polynomial time, and in practice allows to factor $N$.

Another experimental fact is that if we probe a physical implementation  of such a black box, that has a public design, long enough, with sensitive-enough sensors, and pour enough brainpower and a little CPU power on the thing, we manage to extract $N$. This is one of several understandable reasons why such black boxes are not made of public design.

BTW: experimental cryptanalysis with quantum sensors is the one unobstructed way for experimental cryptanalysis to go quantum.


Security of a signature scheme based on both factoring and discrete logarithms

Although I can't see any immediate weaknesses, I also don't see how it adds significant value over DSA (while being significantly slower).

It claims to be based on two hard problems, discrete log and factoring. However, it doesn't give any particular proof that if you could forge signatures, you can solve both problems.  It also doesn't look particularly likely; if you can solve the problem of finding a value $K$ where $K^K = x \bmod p$ (for a fixed $x$), you can forge (by selecting a random $\nu$, computing $x = g^{\nu^e}y^{h(M)^2}$ and then solving for $K$), and it would appear unlikely that this problem would be reducible to the discrete log or the factorization problem.

In addition, while it is true that discrete log and factoring are different problems, they are related.  The paper claims that "it is very unlikely that factoring and discrete logarithms can be efficiently solved simultaneously", however it is not actually that implausible that an advance would solve both.  For example, a dramatic speedup of the Number Field Sieve may solve both (as that algorithm can be modified to work against both problems).  Alternatively, if someone builds a Quantum Computer, well, both problems are then solved.

In addition, their algorithm doesn't appear to run nearly as quickly as DSA (which is not a particularly efficient signature algorithm).  Here's why: their algorithm can be viewed as a DSA variant, except that they work in a composite subgroup (rather than the prime subgroup that DSA works in).  Here's the rub: their subgroup must necessarily be large (as it must be hard to factor their subgroup; otherwise one of the problems they're relying on is easy).  So, instead of having a 256 bit subgroup (which we may work with DSA), they need to work in a 2048 bit subgroup.  Because the time taken to compute, say, $K^K$ is proportional to the size of the subgroup, their scheme would take 8 times longer than DSA.

Also, at points their algorithm description is a bit goofy.  Take their signature generation algorithm; it would appear that the three steps they have listed could be summarized as $\nu = (Kr - xh(M)^2)^d$.  This alternative formulation would better than halve the time (as you don't have to compute a modular square root, and we do one modular exponentiation step; they do it twice); and you don't have to worry what to do if $Kr$ happens not to be a quadratic residue.  The only reason I can think of to use their formulation would be to add some sort of side channel resistance; however if you're concerned with that, well, there's got to be a cheaper way.


If the attacker does not know the value of $secretkey$, he cannot predict in advance the value of $MD5( attackercontrolled + secretkey)$.  However, what he can to is create two different messages $M$, $M'$ such that:

$MD5( M + secretkey) = MD5( M' + secretkey) $

He cannot predict this common value in advance; however, if he is able to submit $M$ and observe the generated tag, he immediately knows the tag for $M'$

This is a violation of the security properties that message authentication codes are supposed to provide.


Pohlig Hellman and small subgroup attacks

The Pohlig-Hellman algorithm reduces the discrete logarithm from a group of composite order to subgroups of prime order. For instance, with an elliptic curve and a point $P$ whose order is a composite integer $q = p_1 \cdot p_2$, and we want to find $k$ such that $Q = [k]P$ for a given point $Q$. Then, since $[p_2]P$ is a point of order $p_1$. Let
$$
Q_2 = [p_2] Q,\quad \text{and} \quad P_2 = [p_2]P,
$$
and now we have $Q_2 = [k\bmod p_1] P_2$. Generic discrete logarithm algorithms can then be used to get to obtain $k\bmod p_1$.
With $Q_1 = [p_1]Q$ and $P_1 = [p_1]P$, we obtain $k\bmod p_2$ and the Chinese Remainder Theorem can be used to get $k$. Then, the security depends mainly on the largest prime in the decomposition of $q$. That's why points whose order $q$ is a large prime is chosen.
In the small subgroup attack, the idea is to make the computation happens with a point of small order instead of a point whose order is a large prime. Typically, standardized curves in cryptography have order $q\cdot h$ where $q$ is a large prime and $h$ is generally small. The principle is the attacker, instead of sending a point of order $q$, sends a point $P$ of order $h$ (for example in a Diffie-Hellman key-exchange). Then the computation with a secret value $k$ will be $Q = [k]P$, but since $P$ has order $h$, there is at most $h$ possible values for $Q$.
In a Diffie-Hellman key-exchange, it works like this: the attacker sends $P$ of small order to Alice instead of its valid public point. Alice computes $Q = [k]P$ thinking that the point $Q$ is the shared secret, from which she derives a symmetric key to encrypt the communication. Since there is only a few possible values for $Q$, there are only a few possible keys. The attacker tries them one by one until the decryption is correct. When this is the case, he learns $k \bmod h$.

You can use this attack, when the order of the field of the elliptic curve is not prime ( you can use it with a prime field, too, but it is not useful ). How it works: Be $E$ an elliptic curve over $F_p$. Be $p = f_1 \cdot f_2 \cdot \ldots \cdot f_n$ the factorization.

For clarification, in cryptography an elliptic curve is defined over a finite field, and a finite field has an order that is either a prime $p$ or a power of a prime $p^\ell$. This value is not the order of the curve. The order of the curve is very close to it, but is generally different.


Why use base64 or hexadecimals for ciphertext?

When using standard encryption algorithms like AES-GCM, ciphertext is bytes that are approximately uniformly distributed among the 256 possible byte values. Since ISO/IEC 8859-1 allows like 191-byte values out of 256, it's extremely unlikely that any practical ciphertext will entirely consist of these 191 bytes, as would be the case if some appropriate Binary-to-text encoding was used, including Base64. In the rest, I'll assume it is not used such encoding.

The curious case is that within that file there are two lines in plain text (header and footer) and the rest encrypted.

That does not make it impossible for decryption of such files to works. Many modern file transfer methods, including USB thumb drives, attachments to email or messaging, network shared volumes, cloud storage, UNIX pipes, windows pipes opened in binary mode… will happily transfer any (contiguous and single fork/stream) file with all its data (if not metadata like file name, date and security attributes) unchanged. Thus the problem of allowing decryption boils down to locating the ciphertext in the file.
That can be dealt with with conventions. One possibility is that ciphertext starts after a header of fixed size in bytes that the decryption skips. Another is that it starts after the first occurrence of a fixed text sequence, e.g. <-- ciphertext on next line --> followed by a single LF character. The end of ciphertext can be dealt with by embedding the ciphertext length at the start of ciphertext. That can work if the file is correctly prepared, e.g. by a correctly written program; or by manually concatenating a header file, the ciphertext, and the footer file using bash on a Unix system; or using copy /b of cmd.exe on Windows.
Things that go wrong when that's attempted include: the file is opened and mistakenly saved with a text editor (perhaps to remove the header), and that particular text editor ruins the ciphertext (many do); the sender used CR LF as end-of-line and the decryption is unaware of that; the file is piped to a console display emulating some glass terminal (e.g. a VT100 itself emulating an ASR-33), which emits silly noises, locks, or act strangely because it entered an obscure mode.


Well, as others have said, you would not be able to do with a standard salted hash function.

However, if you were use a specially designed hash function (that allows this specific comparison), then it would be possible.

Here is a proof-of-concept idea, to show that it is possible:

Suppose $N$ was a large composite number of unknown factorization
Let our hash function be $h( C, Salt ) = hash(C) ^ {2hash(Salt)} \bmod N$ (where $hash$ is a function that converts strings into large integers, in a way where hashes of different strings don't have obvious relationships).  The factor 2 is there to prevent the Jacobi symbol of $h(C, Salt)$ from leaking any information.

This hash function is one-way, because reversing it is the RSA problem, and that's hard if we don't know the factorization of $N$.

And, we can compare hashes $h_1, h_2$ with salts $Salt_1, Salt_2$, we just check if $h_1 ^ {Salt_2} = h_2 ^ {Salt_1} \bmod N$.

And, if you're wondering "how do we get a value $N$ which we know is hard to factor, well, we can just grab an RSA-challenge number of the appropriate size.

Now, I'm not really advocating this method (the "hashes" are quite lengthy); however it does show that it is possible in principle.


Problem with Fiat-shamir on poly-round interactive protocol?

Yes, there are examples of non-constant round interactive protocols that are unsound when the Fiat-Shamir transform is applied even in the random-oracle model. Note that for constant-round protocols soundness in the random oracle model was proved by Pointcheval and Stern [PS00] -- that is, any constant round interactive protocol (that has negligible soundness error) is also sound when the Fiat-Shamir transform is applied to it given the hash function is modelled as a random oracle.

One simple counter-example is to consider the sequential composition, say $n$ times, of a constant-round protocol that has constant soundness error. By amplification theorem, the resultant protocol has negligible soundness error --- inverse-exponential in $n$ to be precise ---  but the Fiat-Shamir transformed protocol is totally insecure as argued next. Since the soundness error is constant a malicious prover can basically sample (in constant-many attempts in expectation) "favourable" messages for each round and with high probability come up with a cheating proof: see this lecture (around 11 minutes) by Ron Rothblum for more details.

[PS00] Pointcheval and Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.


Why do all hash functions use big-endian data?

Probably you just looked at the SHA-family of cryptographic hash functions as others (like MD5 and the RIPEMD-family use little endian (see for example this table for the compression functions).

The emphasis on a certain byte ordering is purely functional and not relevant for security (see my 2nd comment to your question).


Are Lagrange Multipliers necessary for Shamir's secret sharing?

I will answer you by an example, assuming Shamir sharing algorithm with $d=2$ (minimum shares). So, by definition we need a $d-1$ degree polynomial as:

$Poly(x)$ = $ A_1 \cdot X^1 + S$ = $10x +20 $ where $S=20$ is the secret. The dealer will calculate the shares as (two shares for simplicity, where 2 is needed to reconstruct the polynomial):

$(1) [x_1, Poly(x_1) ]$ = $[ 5, Poly(5)]$ =$[5,70]$ , and

$(2) [x_2, Poly(x_2) ]$ = $[ 10, Poly(10)]$ =$[10,120]$.

Now, without using Lagrange interpolation: the verifier needs to reconstruct the polynomial equation (i.e., line equation) to find $S$ as:

$(1) Poly(5)=A_1 \cdot 5 +S =70$ and

$(2) Poly(10)= A_1 \cdot 10 + S =120$

So, you will need to solve the two equations. This is a simple one because it has only two equations. However, for larger  $d$ minimum shares it will be intricate process to solve lets say 10 equations.

Second, by using Lagrange interpolation it will be much easier because we are only interested by $Poly(0) \equiv S $.

In conclusion, both have the same security but Lagrange interpolation is much faster way.


Why does RFC8032#8.7 state that the IUF hash API should not be used for Ed25519?

What implications does it have?

That's because, as designed, Ed25519 does two passes over the message that is being signed:

It first hashes the message (and secret data) to construct the internal value $r$ (which is used to compute the public value $R$)
It then hashes the message (and the public value $R$) to construct the public value $S$.

Because of the ordering of the hashes in the second pass, the first pass must be completed before starting the second pass [1]

Now, the verifier cannot check that $r$ was constructed correctly, and so you could (say) select a random value in its place, which would allow you to create a signature with a single pass.  However, if you did that, and got it wrong (say, using the same $r$ to sign two different messages), you just leaked the private key; Ed25519 was designed to avoid such possibilities.

[1]: Random musing: if you modify Ed25519 by changing the ordering of the hashes $H(R, A, M)$ to, say, $H(A, M, R)$, you could perform it in a single pass (performing both hashes in parallel).  Of course, the verifier would need to know about the modified hash ordering.  I speculate Dan did it the way he did because that change would require a stronger security assumption on the hash function; as it is, Ed25519 assumes second preimage resistance, rather than collision resistance.


what are the most common stream ciphers algorithms?

By far, RC4 is the most popular stream cipher that's been around for 10+ years.  ChaCha20 has just turned 10, and is now becoming popular, but was essentially unheard of 10 years ago.


What information to include is the 'info' input for HKDF?

No, the info is not a salt. The input key material for a KBKDF (key based key derivation function) should already be pseudo-random, and should therefore contain enough entropy to not need a salt.

If the user already has a unique 16+ pseudo-random bytes key then there is little reason to use the email address as part of the info. The email address could be used to make the derived key specific to the user, but that is already the case (in your example).

The main reason for a KBKDF is to create more keys or longer keys. You would need to use the algorithm name as part of the info when the algorithms would otherwise use the same key material.

The info is the key derivation data. You use identical input key materials to create multiple derived keys. The info makes the distinction between the keys. The KBKDF makes sure that the keys are indistinguishable from pseudo random numbers (and thus independent of each other).

Example uses: create a encryption and mac key from the same input key material (info is ASCII encoding of "ENC" and "MAC" or a counter value 1 or 2).

Another example: encrypt files with the same key without using an IV: input of the info part is the UTF-8 encoding of the file name.


How were the best AES whiteboxes in the CHES 2017 CTF challenge built and broken?

Junwei Wang gave a talk on how the winning entry (#777 by cryptolux) was designed and how team cryptoexperts broke it. Slides, video.

The overvew of the design (slide 9) is:

Multi-layer protection

Inner: encoded Boolean circuit with error detection
Middle: bitslicing
Outer:   virtualization, randomly naming, duplications, dummy
operations

Code size: ~28 MB
Code lines: ∼2.3k
12 global variables including:

computation state (2.1 MB)
program bytecode (15.3 MB)

And the overview of their approach to reversing it:

Reverse engineering ⇒ a Boolean circuit
Single static assignment (SSA) transformation
Circuit minimization
Data dependency analysis
Key recovery with algebraic analysis