What is the difference between security parameter and $b$-bit security?

What is the difference between security parameter $1^n$ and $b$-bit security?

There's not one, but two:

A security parameter $1^n$ does not precisely specify how the attacker work grows with $n$. Depending on author and context, that can be: unspecified; faster than any polynomial in $n$ (common in asymmetric cryptography); exponential in $n$ (common in theoretical symmetric cryptography); or roughly¹ as $2^n$ (common in applied symmetric cryptography).
By contrast, "$b$-bit security" specifies that the work for attack grows roughly¹ as $2^b$, as it can in symmetric cryptography for attacks aiming at recovery of a $b$-bit key for an ideal cipher. The distinction is paramount in RSA, where $n$ most often is the bit size of the modulus, and $n=2048$ is believed to yield $b\approx112$.

When we consider algorithms running in time at most polynomial to the size of their input, as is customary in theoretical work: passing $1^n$ (meaning a bitstring consisting of $n$ bits at one) as input implies that the run time is polynomial in $n$, when passing $n$ would allow the run time to be a polynomial in $\log(n)$. Usually the former is desired in cryptography.
Whereas "$b$-bit security" says nothing about the run time.

¹ For some definition of roughly. Many, including me, often state that the expected attacker work is $O(2^b)$,. That's improper because that upper-bounds said work. We should at least  write $\Omega(2^b)$ or $\Theta(2^b)$; see this. I corrected that (minor and common) issue in my answer to the "previous question" mentioned.


Which is more secure, using just bcrypt or SRP?

The point of SRP is to remove the need for the SSL/TLS certificates. With SRP integrated into SSL/TLS (as per RFC 5054), you get mutual client/server password-based authentication and can do without any of the dreadful certificate business; and yet the protocol is still resilient to offline dictionary attacks.

If your SSL/TLS still uses a server certificate then there is little point in using SRP; the client already knows that it talks to the right server, and can send the password as cleartext  within the tunnel (or a hash-of-password if you really need that to sleep at night).


Picking a cipher suite for embedded system emails

You can support as many or as few as you like - take a look at RC 5247 for TLS 1.2.  If you are on an embedded system w/o any hardware crypto, you may want to skip the RSA algs that take a long time in favor of the ECDH.  In any case, look for an embedded crypto library that available for your toolchain and cpu vs writing it yourself.  It'll save time as well implementation flaws.

You might try initiating a TLS session with one of these email hosts and see what comes back for the algorithms they support - I suspect it's pretty extensive.  Then you could be sure that the ones you pick will work.

Wireshark is your friend for this.


How to show that Cx is a commitment to a integer of length lm

You want to prove knowledge of an opening $(x,r)$ to a Pedersen commitment, such that $x$ belongs to the range $[0,2^{l_m}]$. Such a proof is called a range proofs, and many methods exist, using bit-decomposition (commit to $x$ bit by bit, prove that the sum of the $x_i\cdot 2^i$ is indeed $x$, and prove that each committed value is a bit) or square decomposition techniques over hidden order groups. I discussed some of these methods in several answers, see here and here. The latest state-of-the-art method for range proofs is Bulletproof, which achieves relatively impressive efficiency guarantees, to the point that it's actually used in several real-world applications (e.g. the cryptocurrencies Monero and Mimblewimble, among others).


Can a SHA3 engine be used to construct a Keccak implementation?

Let first look at  $$\operatorname{KECCAK}[c] (N || suffix, d) \label{1}\tag{1}$$ It calls
$$\operatorname{KECCAK}[c] (N, d) = \operatorname{SPONGE}[\operatorname{KECCAK-p}[1600, 24], pad10*1, 1600 – c] (N, d).$$

$c$ is the capacity
$d$ is the output size
1600 is the base $b$
$pad10*1$ is the multi rate padding.
24 is the number of rounds $n_r$
The sponge in short is the framework for specifying functions on binary data with arbitrary output length.

Let assume that we have a black box SHA3 implementation of any mode

$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M || 01, 224)$
$\operatorname{SHA3-256}(M) = \operatorname{KECCAK}[512] (M || 01, 256)$
$\operatorname{SHA3-384}(M) = \operatorname{KECCAK}[768] (M || 01, 384)$
$\operatorname{SHA3-512}(M) = \operatorname{KECCAK}[1024] (M || 01, 512)$

and black box SHAKEx implementations

$\operatorname{SHAKE128}(M, d) = \operatorname{RawSHAKE128}(M || 11, d)$

$\operatorname{SHAKE256}(M, d) = \operatorname{RawSHAKE256}(M || 11, d)$
where

$\operatorname{RawSHAKE128}(J, d) = \operatorname{KECCAK}[256] (J || 11, d)$
$\operatorname{RawSHAKE256}(J, d) = \operatorname{KECCAK}[512] (J || 11, d)$

Now you want to use the above as black box implementation for cSHAKE
 cSHAKE128(X, L, N, S):
 1. If N = "" and S = "":
    return SHAKE128(X, L);
 2. Else:
     return KECCAK[256](bytepad(encode_string(N) || encode_string(S), 168) || X || 00, L).

The if part is not a problem, since it directly uses the SHAKE128.
The else part is the problematic part. One can externally implement bytepad(encode_string(N) || encode_string(S), 168) and concatenate it with X. The domain separation padding 00 is the real issue. If the block box doesn't allow this as input, then there is no way to this.

If the library somehow extendible one may use the \ref{1} to generate all of the above, otherwise no.
The cSHAKE is the base for KMAC, TupleHash, and ParallelHash. If you are going to need those, you may need to implement yourself.


How does one construct a 27x27 tabula recta for 2-of-3 secret sharing?

We start by coding a secret $k\in\{0,1,2\}$ as three shares $x$, $y$, $z$ by

choosing share $x$ uniformly at random in $\in\{0,1,2\}$
choosing share $y$ as $(x-k)\bmod 3$
choosing share $z$ as $(y-k)\bmod 3$

One share gives no clue about $k$, but we can recover $k$ from any two shares:

from $x$ and $y$ as: $k=(x-y)\bmod 3$
from $y$ and $z$ as: $k=(y-z)\bmod 3$
from $z$ and $x$ as: $k=(z-x)\bmod 3$

Note: per standard notation of modular arithmetic, for $n>0$, the quantity $i\bmod n$ is defined as the $j$ with $0\le j<n$ such that $i-j$ is a multiple of $n$.

The table we need to carry this has $k=(x-y)\bmod 3$ at column $x$ and lines $y$, that is:

    |  0  1  2
----+----------
- 0 |  0  1  2
- 1 |  2  0  1
- 2 |  1  2  0

Now, if the secret consists of two digits each in $\{0,1,2\}$, we can express it as three shares of two  digits each in $\{0,1,2\}$, by using the above method for each digit of the secret, yielding the corresponding digit for each of the three shares.

We can simplify doing that by building the following table, where each digit of the result is obtained by applying the previous table to the corresponding digit of each input:

     |  00  01  02  10  11  12  20  21  22
-----+-------------------------------------
- 00 |  00  01  02  10  11  12  20  21  22
- 01 |  02  00  01  12  10  11  22  20  21
- 02 |  01  02  00  11  12  10  21  22  20
- 10 |  20  21  22  00  01  02  10  11  12
- 11 |  22  20  21  02  00  01  12  10  11
- 12 |  21  22  20  01  02  00  11  12  10
- 20 |  10  11  12  20  21  22  00  01  02
- 21 |  12  10  11  22  20  21  02  00  01
- 22 |  11  12  10  21  22  20  01  02  00

We can then replace two-digit pairs by $3^2=9$ letters A..I (in row and column indexes, and the table itself), and we get:

     |  A   B   C   D   E   F   G   H   I
-----+-------------------------------------
- A  |  A   B   C   D   E   F   G   H   I
- B  |  C   A   B   F   D   E   I   G   H
- C  |  B   C   A   E   F   D   H   I   G
- D  |  G   H   I   A   B   C   D   E   F
- E  |  I   G   H   C   A   B   F   D   E
- F  |  H   I   G   B   C   A   E   F   D
- G  |  D   E   F   G   H   I   A   B   C
- H  |  F   D   E   I   G   H   C   A   B
- I  |  E   F   D   H   I   G   B   C   A

We can do the same thing for secrets consisting of three digits, then replace three-digit triples by $3^3=27$ signs: letters A..Z and . . That's how the table in my answer was constructed.

The mapping of $3^3=27$ three-digit triples to letters is arbitrary. We would obtain a table that works just as well for any mapping. We can additionally reorder lines and columns in a convenient order, e.g. alphabetical. That allows to generate different easy-to-use tables that work just as well.

We can also extend to $3^4=81$ symbols, allowing uppercase and lowercase, digits, and 19 typographical symbols (but if the symbols are ultimately printed, the font must allow recognizing between O and 0, l and 1 ).


Is Pseudo-Random Generator (PRG) in OpenSSL uniformly distributed?

Yes, the Pseudo Random Number Generator (PRNG) in OpenSSL is Cryptographically Secure, which means it passes statistical tests, but as @Maarten Bodewes suggests in his comment, why not go one step further and use that PRNG directly, rather than through OpenSSL?

OpenSSL can use EGD (which stands for Entropy Gathering Daemon). It is a process that taps into configurable entropy sources in a given system to provide cryptographically secure random numbers. EGD is actually modeled after /dev/random in *Nix Operating Systems, so it would not be available in a Windows system, for example, but its function is the same as /dev/random which is to gather entropy for random number generation.

If you are creating an application in a *Nix system (OS X, Linux, etc) chances are that EGD is taking input from /dev/random, so your best bet is to use it. If you are in a different OS, then EGD is probably the way to go.


How can we say there is absolute collision in Baby-Step Giant-Step attack for RSA?

But how can we say there's a absolute collision in these two lists?

Well, we know that $c^d \equiv m$ for some value $d < n$, because of this, we have $d = Nk + j$ for some pair of integers $0 \le j < N$ and $0 \le k < N$.  We see that $c^j$ will appear somewhere in the first list, and $m \cdot c^{-Nk}$ will appear somewhere in the second list.
Since $c^{Nk + j} = m$, rearranging terms, we have $c^j = m \cdot c^{-Nk}$, and so those two terms will be the same.
That said, this is not a practical attack against RSA (and Coron et al never claimed it was).  The attack takes $O(\sqrt n)$ time, making it no more efficient than brute force factoring (and there are plenty of more efficient ways to break RSA than that).


Security exists or not in Modification in schnorr signature

There are quite a few errors in your thoughts:

  k and x are assumed to be secret value of user.
  So, (k,x) value is never changed except e.

As stated in the signing algorithm, $k$ is drawn uniformly random from the set $\mathbb{Z}_q^{\times}$. This means, it is random (and different with overwhelming probability) for every single message. Using the same $k$ might not be secure at all - I am quite sure it won't, but don't have a proof right now.

That means, in every message $k$ has a different value. This ipmplies, that $e$ has a different value (again, with overwhelming probability). And again, $s$ has a different value with overwhelming probability.

This wouldn't work, since a fixed $k$ just does not fit the algorithm's assumptions.

  Unlike Schnorr's signature, e is also kept secret so that only valid users, who knows respective k and x values, can reveal it.

This is a quite pointless in this case. If some information is known to anyone whose role isn't specified in the protocol, you have to assume that the value is publicly known.

  Even though different k,x values, e is selected uniformly randomly from Zq and assumed to be same for all valid users.

This doesn't make sense at all. Every user has his own fixed value of $k$, the protocol clearly describes how $e$ has to be calculated. If you choose $e$ independently, the whole signature does not work any more.

Adn then you write in the comments:

  Instead of signature, just consider for simple, secure delivery of e.

I thought, $e$ is the same for all users? I guess you meant $s$.

But this would mean this: Your value $s$ does not depend on the message any more. $s$ is always the same for every message.

Summary

This isn't a modification, it has nothing to do with the signature scheme any more. If your only modification would be a fixed $k$, chances are quite high that you already have a fatal security flaw in your setup. My guess would be, that two signatures actually reveal the secret value $x$ then.


How can Shor's Algorithm be applied to ECC?

Section 2.2 of the following paper details how to apply Shor's algorithm to ECDLP: https://eprint.iacr.org/2017/598.pdf

The process is similar to DLP, except that we need different circuits to perform our our group operations in elliptic curves (additions and scalar multiplications).


This is easy, just pick $e$ as prime larger than $\max(p,q)$. As $\phi(n) = (p-1)(q-1)$ it has only prime factors smaller than $q$ and $p$.

You can also do trial and error. If $e$ is prime, the GCD test is very fast. But it is technically not necessary to choose $e$ prime. Also note that key generation is not time critical.

However, often one starts with $e \in \{ 3,5,17,257,65537 \}$ which are special primes. Then one choose appropriate $p$ and $q$.
These exponents have computational benefits as they are of the form $2^k+1$. That makes computation of the $e^\text{th}$ power fast. Note that there are attacks for small exponents, especially $e=3$. They are all related to bad implementations, i.e. padding and so on. The RSA-scheme itself is not affected.


Can the encrypt-and-authenticate method result in secure authenticated encryption if the MAC scheme has unique tags（non-deterministic）？

Not necessarily.  Let $M$ be a secure deterministic MAC like HMAC-SHA256.  Define the randomized MAC $M'_{k, \rho}(m) := M_k(m) \mathbin\| \rho$; that is, $M'$ just appends the randomization to the MAC.  Then encrypt-and-authenticate with $M'$ still leaks message equality, even though the MAC is technically randomized.


Is function Deterministic or Probabilistic in the malicious security definition?

No, the semi-honest definition does not have two cases; the correct definition is Definition 2.2.1, which applies to all functionalities. But if the functionality is deterministic, then the simpler definition given later in the book (yes, it is given later in the book; I am not sure why you decided to put it above it in your question) is equivalent, and might therefore be preferred when trying to prove the security of a protocol.

No similar "simplified" definition exists in the malicious model, because even if the functionality is deterministic and the protocol correctly computes it, a malicious adversary can deviate from the protocol and output something completely different from what the protocol says it should.


There are two strategies to do what you want.

The first one being to find the group order $q$ and then compute $i=2^{-1}\bmod q$. When you then multiply your point $P$ by $i$ you get $Q=[i]P$ with $[2]Q=[2i]P=[(2\cdot 2^{-1})\bmod q]P=P$ as desired. This general strategy works for any finite group (as long as $q$ is not even) and was quickly pointed out by fgrieu in the comments.

The second way goes as follows:

Find out the equation for your curve. For secp256k1 this is $y^2=x^3+ax+b$ a.k.a. "Short Weierstrass Form".
Go to the explicit formula database and select the relevant curve.
Take the affine doubling equation and plug it into your favourite tool for solving algebraic equations and tell it to solve for the coordinates on the left side.
You should now receive a result. Because all fields are equal when it comes to the transformations carried out, you can just take the resulting formula and "easily" translate it to work over your finite field.


Diffie-Hellman Parameter Check: when g = 2, must p ≡ 11 (mod 24)?

Actually, there is no major difference between $p \equiv 23\  (\bmod\  24)$ vs $p \equiv 11\  (\bmod\  24)$; any minor difference boils down to "do you prefer the DH shared secret to be limited to half the possible values; or do you prefer to leak a bit of the secret exponents?".  OpenSSL prefers to leak one bit; the RFC 3526 designers decided they preferred to limit the possible values.

To explain exactly why this is true, I need to expound on the structure of $Z_p^*$ when $p$ is a strong prime; that is, if $(p-1)/2$ is also prime.

In that case, there are three types of elements:

The trivial elements 1 and p-1; obviously, you wouldn't want to use those as a base for doing DH; we'll skip those as potential bases from here on out.
Quadratic residues; these are elements $x$ for which there exist a $y$ such that $y \cdot y \equiv x\  (\bmod p)$
Quadratic nonresidues; these are elements $x$ for which there is no such $y$ with $y \cdot y \equiv x\  (\bmod p)$

Here's why the distinction is important:

If $g$ is a quadratic nonresidue, then $g$ is also a generator; that is, for every value $h$, there is an $i$ with $g^i \equiv h$.  In contrast, if $g$ is a quadratic residue, then that is not true; $g^i$ will only take on values that are quadratic residues themselves.

What this means is that if use a $g$ which is a quadratic nonresidue as a base for the Diffie-Hellman operation, then any value $[1, p)$ is possible for the shared secret; if you use a quadratic residue, then half the values are possible (those values which are themselves quadratic residues).

If $g$ is a quadratic nonresidue, then given the values $g^x$, it is computationally feasible to determine $x \bmod 2$; that is, the lsbit of $x$.  The attacker can do this by checking whether $g^x$ is a quadratic residue (for example, by checking whether $(g^x)^{(p-1)/2} = 1$; if it is, then $x \equiv 0 \bmod 2$; if it isn't, then $x \equiv 1 \bmod 2$.

In the Diffie-Hellman protocol, each side picks a secret $x$, and transmits $g^x$; if $g$ is a Quadratic nonresidue, then the attacker can use this observation to recontruct one bit of $x$; if $g$ is a Quadratic residue, this observation does not apply.

Now, what does this have to do with $p \bmod 24$?  Well, it turns out that, if $p \equiv 11 \bmod 24$, then $g=2$ will be a Quadratic nonresidue (and hence Diffie-Hellman can generate any shared secret value, but the attacker can learn the lsbit of the secret exponents).  On the other hand, if $p \equiv 23 \bmod 24$, then $g=2$ will be a Quadratic residue (and hence the Diffie-Hellman will be restricted to the Quadratic residue values, but the attacker isn't give any bits of the secret exponent for free).

And, in case you're wondering, if $p$ is a safe prime > 7, then $p \bmod 24$ will be one of those two values.

So, there really isn't all that much difference between the two; however my personal preference is for $p \equiv 23$; while leaking one bit from a perhaps 256 bit secret exponent isn't all that harmful, I don't see the point in leaking anything at all.


Faster Shuffling for a Simple Application

The obvious way is to use two oblivious transfers.  In case you need reminding: an Oblivious Transfer is a protocol where one party (Alice) has a number of secrets (in this case, two), and the other party (Bob or Charlie) gets to pick which one he gets to learn, but he doesn't learn the other (and Alice doesn't learn which one he picked).  There are several known protocols that implement this.

Here is how it would work:

Bob and Charlie randomly agree on a random bit $b$

Alice takes the two tasks she doesn't want, and randomly labels them $T_0$ and $T_1$

Bob then performs an oblivious transfer with Alice, obtaining the task $T_b$

Charlie then performs an oblivious transform with Alice (but using the bit $1-b$ rather than $b$ in the oblivious transfer), obtaining the task $T_{1-b}$

Because of the guarantees that OT provides, neither Alice, Bob nor Charlie know any of the tasks other than their own.

Now, one obvious issue is that, if Bob or Charlie wanted to cheat, they could use the wrong value of $b$, and learn the task given to the other guy.  However, if they did that, they wouldn't learn their own, and so if we assume that they find that unacceptable, this isn't an issue.  It is possible to insert a zero knowledge proof that would ensure that they're not doing that (the details of which would depend on the OT protocol used); however I don't know if you need to do that.


Comparing the security when using fixed IV for CBC and CTR

If you reuse key&IV(nonce) in CTR mode you have almost no security.
You get a two time pad.
Xoring to messages, will eliminate the key stream and give you the XOR of the plain texts which usually gives you plenty of information.
With multiple such cipher text it gets even easier.
If you reuse IV and key in CBC mode, it isn't good, but it isn't anywhere near as bad. You can't trivially decrypt messages, even if you know parts of the message or you know a lot about the distribution of messages (e.g they are English language).
Having a predictable IV let alone a fixed one, allows you to mount a chosen plain text attack, which can verify guesses about any cipher text block. See:
Why is CBC with predictable IV considered insecure against chosen-plaintext attack?


Friedman Index of Coincidence, pruning multiples of the keylength

I suspect, when the IC was invented, it was typically used together with human judgement, so there might not be any standard rules to address this issue.

Anyway, it seems like there are two plausible solutions:

It might be easy to add a special case for this situation: choose the keylength with the highest IC, except that if it has a divisor whose IC is within 10% of it, choose the divisor.
Another plausible solution would be to try running the rest of your attack on both candidates.

I would imagine either of these might work fine.


Steps 5 and 7 remain very important even when one ignores DoS attacks.

$\;\;\;$ The RSA key-pairs use   e = 3

$\;\;\;$ Server signs $\: \langle \hspace{-0.03 in}$ RSA_modulus , RSA_ciphertext $\rangle \:$ and returns that to Client in step 3

$\;\;\;$ If computation is significantly more of a bottleneck than communication,

$\;\;\;$ then Client computes a sufficiently accurate estimate of its modulus's

$\;\;\;$ reciprocal in step 1 and sends that estimate to server in step 2

$\;\;\;$ In general, if step 6 is used then its estimate may need to go into what gets signed

$\;\;\;$ in step 5. $\:$ However, I believe the most straight-forward way to use estimates from

$\;\;\;$ step 6 would have the property that if an adversary changed it to a bad "estimate",

$\;\;\;$ then Server will either detect that or get the right result anyway.

$\;\;\;$ If step 6 is used and the use of its estimates has that property and the key(s)

$\;\;\;$ is(are) only used as input to a secure MAC scheme and/or a stateless IND-CPA

$\;\;\;$ encryption scheme and those schemes are only used for authentication

$\;\;\;$ and/or (possibly-already-authenticated-)encryption respectively, then the

$\;\;\;$ estimate from step 6 does not need to go into what gets signed in step 5.

$\;\;\;$ (It's fine if the encryption is used in a way that keeps state, but I only see a proof for the

$\;\;\;$ cases in which the underlying encryption scheme is IND-CPA despite not keeping state.)

Explanation of what's going on in #7:
By changing the honest client's estimate to a bad one, the adversary might be able to make

the event "server aborts" depend in a useful(-to-the-adversary) way upon what the resulting

key would otherwise have been and the randomness that would've been used to encrypt it.

The assumptions I gave are enough to guarantee that subsequent

communication remains secure despite such any such dependency.


Compression in key generation of DES algorithm

The PC-2 substitution transforms the 56-bit concatenation of the 28-bit $C$ and $D$ after they have been appropriately rotated, into the 48-bit subkey $K_i$ for round $i$, before that is combined using XOR with the 48-bit output of expansion $E$ and divided into 6-bit entries for each of the 8 S-tables. The table defining PC-2 is correspondingly organized as 8 lines of 6 values in the defining standard.

14  17  11  24   1   5
 3  28  15   6  21  10
23  19  12   4  26   8
16   7  27  20  13   2
41  52  31  37  47  55
30  40  51  45  33  48
44  49  39  56  34  53
46  42  50  36  29  32

The $j^\text{th}$ integer in the table when scanned in reading order is the index of the bit in the input corresponding to the $j^\text{th}$ bit in the output (in DES, the convention is that the bits are numbered from 1 onwards, with 1 being the first or left bit, or the most significant bit in the first or left octet in an octet or quartet string, with octets and quartets expressed in big-endian hexadecimal).

Hence integers 1..28 in the table corresponds to bits from $C$ (and happen to be directed towards the first 4 S-boxes); and the others corresponds to bits from $D$ (going to the other S-boxes).

In other words, we form the first 24 bits of the output by taking the 14th, 17th, 11th .. 13th and 2nd bits of $C$; and the next 24 bits of the output by taking the 13th, 24th, 3rd.. 1st and 4nd bits of $D$ (we subtract 28 from the integers above 28 to get the index in $D$ ).

Integers 9 18 22 25 and 35 38 43 54 are not in the table; they correspond to bits of $C$ and $D$ that are not used in this round (but have or will be in the previous or next round, if any, due to the combination of the shift counts used with PC-2).


How can I verify certificate signature algorithm in TLS 1.3 using PSS?

It depends on what publickey is. An X.509/PKIX cert contains a SubjectPublicKeyInfo structure which contains an AlgorithmIdentifier that specifies what type the key is and in some cases to some extent how it is used, plus the actual publickey value (wrapped in an OCTET STRING type).
See also the links to 3279 and 4055 (which is updated by 5756).
These TLS1.3 SignatureScheme codes (both the RSA_PSS_RSAE set and the RSA_PSS_PSS set) specify that in the cert that contains the publickey usable to verify the PSS signature (often imprecisely called the signing cert) the SPKI AlgorithmIdentifier use a particular OID; they do not constrain the actual publickey value. Is that a constraint on the publickey? You decide.

For the signature_algorithms_cert extension, yes for PSS-signed certificates the two AlgorithmIdentifier's for the signature algorithm in the child cert will use the OID id-RSASSA-PSS and applicable parameters, while the parent cert's SPKI is constrained as above. When the signature_algorithms extension applies to protocol signatures rather than cert signatures, the protocol signatures are not identified by any OID (see 4.4.4) and the leaf cert's SPKI is constrained as above; this is equally mandatory.


This is known in the cryptographic literature as "traitor tracing".  See, e.g., the following seminal paper:

An efficient public key traitor tracing scheme.  Dan Boneh and Matt Franklin.  CRYPTO 1999.

They show a public-key encryption scheme where each  possible recipient has their own private decryption key.  If an authorized recipient discloses their decryption key, it's possible for the authority to figure out whose key it was.  Moreover, they consider a further challenge -- what if a coalition of authorized recipients pool everything they know, and come up with another decryption key that is different from each of theirs but still works, and they leak that new key? -- and they show how to deal with that challenge as well.

There is an entire line of research that proceeds forward from there.

That said, this is often the wrong kind of solution in practice, for most situations.  You are assuming/hoping that the adversary will publish their decryption key.  But what if they don't?  What if they do something else?  There are all sorts of ways the adversary could cause problems without publishing their decryption key:

For instance, the adversary can leak the decrypted data without leaking the decryption key (this is the killer problem with all of these traitor tracing schemes that has rendered them mostly irrelevant in practice).
Alternatively, the adversary could make available an API that provides "decryption as a service".
Or, the adversary might release software for decryption that embeds the key but in an obfuscated form.

Traitor tracing doesn't help with any of those adversarial strategies.  So, beware that your threat analysis might be based on too narrow a view of what an attacker can do.

More fundamentally: this approach has seen no adoption in commercial systems (as far as I am aware), because of the extreme ease of acquiring false identities.  If you're going to sell access to paid content for $20, and you accept credit cards for payment, it's far too easy for someone to get a stolen credit card number, sign up and gain access, and then publish the decryption key (or the decrypted content).  Now what are you gonna do?  Even if you can trace back to the associated credit card number and name provided during signup, that name is surely fake, and the name on the credit card account is someone else.   At that point you realistically have no way to identify the perpetrator and no recourse.  All the fancy crypto in the world won't save you.

That's why these kinds of schemes might not be as useful as they at first appear, except in some special and limited circumstances.


How to calculate key size for Diffie-Hellman key exchange?

With Diffie-Hellman in its most general description, there are three different types of objects involved:

The group
The exponents
The generator

The group
Diffie-Hellman operates in a group. This group may be $\mathbb Z_p^*$ or may be the points on your favorite elliptic curve usually. Usually the group parameters are what needs to be adjusted over time the most due to computational advances and the advances in cryptanalysis of the discrete logarithm problem (DLP). So what you want is a group where the DLP is assumed to be hard and for this you need to adapt the group or change parameters (like the prime or curve parameters).*
The exponents
There isn't much to the exponents with diffie-hellman except that you want to avoid predictable exponents, because then the other party or an adversary could predict your exponent and calculate the shared secret from that.
The generator
The generator of the subgroup of the group is actually fairly irrelevant. You need to make sure it indeed generates a subgroup of appropriate size and that's about it, especially you should avoid the neutral element or other elements with small order.

*This is actually not true as you usually want the computational diffie-hellman (CDH) problem to be hard, but these two are very closely related most of the time such that there's no known way to break CDH without breaking DLP.

As for the "the shared secret is actually easier to brute-force than all other values". While this is true here, this doesn't scale.
Brute-force of the shared secret scales at $\mathcal O(q)$ (because the shared secret is a random element from the group, with $q$ being the order of said group).
The best generic attack on the discrete logarithm problem scales at $\mathcal O(\sqrt q)$ (there are more efficient ones for prime-moduli-groups).
Now chunk in some numbers. If you multiply $q$ by, let's say, 10,000 you get a workload increase of 10,000 for brute-force, but only 100 for the better attack. So brute-forcing the shared secret clearly isn't the way to go for real-life parameters.

If you're seeking for advice on which keylengths to choose and which parameter set corresponds to which security level, you can use Keylength.com for the TL;DR and read the Lenstra-Verheul paper (PDF) for all the details.


Can $r$ and $s$ from an ECDSA signature be negative numbers?

You appear to be testing a DER-encoded integer.

DER-encoded integers are defined so that they can encode both positive and negative values (in cryptography, we don't need to encode negative integers all that often; however ASN.1 isn't specific to cryptography).

DER-encoded integers are defined this way:

Positive values are represented by the minimal number of bytes that can represent the integer (in bigendian byte order), with the msbit of the initial byte being clear.

For example, the value 32768 would be represented by the three bytes 0x00 0x80 0x00.  We are not allowed to use the two octets 0x80 0x00, because 0x80 has the msbit set

Negative values are represented by the minimal number of bytes that can represent the integer (in two's complement notation), with the msbit of the initial byte being set.
Zero is represented as a single 0x00 byte

Hence, testing the msbit of the initial byte will correctly tell you whether the represented integer is nonnegative.


Are EC public/private keys significantly weakened by having a known byte?

By fixing the first byte of both the private and the public key you actually reduce the key space by about 16 bits, because only about one in $2^{16}$ key-pairs has that property – as you notice. (If there is no way to exploit the restriction on both keys at the same time, you may lose less security but I would assume the worst.)

Doing this is fine, unless the elliptic curve system is almost too small anyway. If it was insecure, then one in e.g. $2^{16}$ randomly generated keys would be similarly weak.

So worst case you should have ~112 bits of security since a 256-bit elliptic curve usually has about 128 bits of security, but that should be enough.


Prevent a Man-In-The-Middle attack whilst transmitting a PSK for first time

There is no magic solution. Either both parties are in a direct contact to exchange a PSK, or they use authentication based on PKI. Otherwise there is no guarantee that there is no man in the middle.


Quadratic residue zero knowledge proof - simulator with identical distribution

Zero knowledge simulator (not honest verifier zero knowledge) is required to produce simulated session transcript that must be indistinguishable. Challenge of Verifier $b$ is the part of the transcript. For identical distribution, real Verifier is invoked to produce the challenge. First message of the protocol $y$ is passed to the Verifier. Simulator-chosen challenge $b'$ is here to properly compose first message $y$ so that it would fit the verification relation. Simulator is looping until it would guess the challenge of real Verifier.

Let me repeat it: query Verifier to pick a challenge with otherwise unknown distribution; the rest of algorithm follows.


PBKDF2 defines, that the salt is concatenated with the numbers of iterations (in 32 bit big endian) as 2nd input to the PRF. If you use HMAC as PRF (as suggested in the wiki article), the 2nd argument can be of arbitrary length.

On other SE sites, you can find these questions and answers to cryptographic salts in general:

What is the optimal length for user password salt?
How big should salt be?

The main aspect of salts is that they are unique. So it comes down to how many different keys you want to derive with your KDF. As a rule of thumb, 32 or 64 random bits should be enough and you will most likely never exhaust those numbers. If you just want to derive a couple of keys from the master secret, you can get away with an even shorter salt, e.g. 2 byte. Even if you set the salt length "too short" and want to derive more keys later, you can always use the same salt and a different number of iterations. That will also result in different derived keys, because the number of iterations is embedded in the input of the first iteration of the PRF already.


What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

All three are families of functions.  For example, $f_k(x) = k \oplus x$, where $\oplus$ is xor and $k$ and $x$ are 256-bit strings, is a family of functions; for any 256-bit string $k$, there is a function $f_k$ which given another 256-bit string $x$ returns the xor of $k$ and $x$.  The input and output spaces need not be the same; we could imagine a family of functions $f_k$ from a 512-bit input $x$ to a 128-bit output $f_k(x)$, keyed by a 256-bit string $k$.  Here is a small function family $g_k$ with a 1-bit key, a 2-bit input, and a 3-bit output:

\begin{equation*}
\begin{array}{c|c}
x & g_0(x) \\
\hline
00 & 111 \\
01 & 000 \\
10 & 100 \\
11 & 110
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & g_1(x) \\
\hline
00 & 011 \\
01 & 110 \\
10 & 100 \\
11 & 100
\end{array}
\end{equation*}

A pseudorandom function family is a family of functions—say functions from 512-bit strings to 128-bit strings, indexed by a 256-bit key—which has the following property.

Suppose I flip a coin 256 times to pick $k$—that is, I choose $k$ uniformly at random.
Suppose I also pick a function $F$ from 512-bit strings to 128-bit strings uniformly at random from all $(2^{128})^{2^{512}}$ such functions, by flipping a lot of coins—enough to fill a book with $2^{512}$ pages so that each page has a 128-bit answer on it.

(Each table above has $4 = 2^2$ rows, because the input is 2-bits long, with a total of $3 \cdot 2^2 = 12$ bits of outputs written down, because there are three bits of output for each distinct input and $2^2$ distinct inputs.  For a uniform random 512-bit-to-128-bit function, you need $2^{512}$ rows, and each row has $128$ bits of output, for a total of $128 \cdot 2^{512}$ bits just to write down one of the $(2^{128})^{2^{512}} = 2^{128 \cdot 2^{512}}$ different functions of that shape!)
I will pick one of these functions—$f_k$ or $F$, but you don't know which—and tell you what the value of the function is at any point you ask.

(Actually I don't need to fill the book up front; if I chose $F$, I can fill out the pages of the book lazily as I get queries from you.)

You can't figure out whether I gave you a member of the function family, $f_k$, or a uniform random function, $F$.

In other words, the probability distribution on functions $f_k$, when the key $k$ is chosen uniformly at random, is very close—as far as computationally bounded decision algorithms can discern—to the probability distribution on functions $F$ chosen uniformly at random from all functions.

A pseudorandom permutation family is similar, except $f_k$ and $F$ are restricted to be permutations, i.e. their input and output spaces are the same, say the set of all 256-bit strings, and they map every input to a unique output so that there is also an inverse function.  So there aren't quite as many possibilities for $F$—while there are $(2^{256})^{2^{256}}$ functions of 256-bit strings, there are only $2^{256}! \approx (2^{256}/e)^{2^{256}}$ permutations of 256-bit strings.  A block cipher is just another term for pseudorandom permutation family, for the most part.*

Here's an example of a small permutation family $\pi_k$ for comparison—again the key is 1-bit, and the inputs and outputs are 2-bit strings:

\begin{equation*}
\begin{array}{c|c}
x & \pi_0(x) \\
\hline
00 & 00 \\
01 & 11 \\
10 & 10 \\
11 & 01
\end{array}
\qquad\qquad
\begin{array}{c|c}
x & \pi_1(x) \\
\hline
00 & 01 \\
01 & 00 \\
10 & 10 \\
11 & 11
\end{array}
\end{equation*}

Note that unlike the tables for $g_k$, each output appears exactly once in each table here, so we can flip each table around to get an inverse permutation.

We can interpret the bit strings as integers in (say) big-endian binary, and write this using the alternative notation $\pi_k = (\pi_k(0) \; \pi_k(1) \; \pi_k(2) \; \pi_k(3))$ for permutations, by saying that $\pi_0 = (0 \; 3 \; 2 \; 1)$ and $\pi_1 = (1 \; 0 \; 2 \; 3)$.  Of course, for a pseudorandom permutation family like AES, the number of elements being permuted is not $2^2 = 4$ but $2^{128} = 340282366920938463463374607431768211456$, so we don't quite have enough space here to write AES down exhaustively in either notation even for a single key.

Actually it's not so much that a family of functions is or is not a pseudorandom function family, but rather we quantify your advantage as an adversary in playing that game.  Specifically, we consider a decision algorithm $A(\mathcal O)$ which takes an oracle $\mathcal O$—which might be $f_k$ for uniform random $k$, or might be a uniform random $F$—and returns a decision in $\{0,1\}$, and we consider the distance between the probability that $A(\mathcal O)$ returns $1$ given $f_k$ for uniform random $k$ and the probability that it returns $1$ given uniform random $F$, called the advantage of $A$ as a PRF distinguisher:

\begin{equation*}
  \operatorname{Adv}^{\operatorname{PRF}}_f(A)
  := \lvert\Pr[A(f_k)] - \Pr[A(F)]\rvert.
\end{equation*}

The PRP advantage is similar, but again $f_k$ and $F$ are restricted to be permutations.  If it's very hard to tell whether the oracle is answering for $f_k$ or $F$, then this distance is nearly zero.  Obviously, there is always a distinguisher with nonzero advantage: guess a key $\hat k$ at random and check whether $\mathcal O(x) = f_{\hat k}(x)$, but the advantage is very small, inversely proportional to the size of the key space.  What's more interesting is distinguishers that have much higher advantage.

We conjecture for certain functions like HMAC-SHA256 or KMAC128—based on a long track record of failure by cryptanalysts to find good distinguishers—that this distance is small no matter what the adversary $A$ is, as long as $A$ makes an imaginable number of queries.  (For example, we're not interested in an adversary that makes $2^{256}$ queries to the oracle, because nobody can do that.)

Then, when studying higher-level constructions like CBC-MAC, we set a bound on the forgery probability of the higher-level protocol in terms of a bound on the distinguishing advantage against the underlying PRF.  That way, we can study whether something like CBC-MAC is a good way to build a MAC out of a PRF separately from whether AES is a good PRF.

‘Wait, AES is a good PRF?’, you say, ‘I thought AES was supposed to be a permutation!’  Well, any PRP makes a good PRF up to the birthday bound.  Specifically, there's a theorem, sometimes called the PRF/PRP-switching lemma, that if $f_k$ is a $b$-bit permutation, then for any adversary $A$ making at most $q$ queries to the oracle, $$\operatorname{Adv}^{\operatorname{PRF}}_f(A) \leq \operatorname{Adv}^{\operatorname{PRP}}_f(A) + \binom{q}{2} 2^{-b}.$$  As long as $q \lll \sqrt{2^b} = 2^{b/2}$ so that $\binom{q}{2} = q(q - 1)/2 \lll 2^b$, the term $\binom{q}{2} 2^{-b}$ is very small.  In other words, as long as our application keeps its data volume well below the birthday bound of $2^{b/2}$ blocks, a good pseudorandom permutation family like AES is nearly as good as a pseudorandom function family.  This is, incidentally, the general reason why cryptosystems involving AES are not safe for more than a few petabytes of data under a single key—and for some of them the safe data volume limit is much lower.

* In some security analyses, it may be convenient to model a block cipher with a slightly stronger idealization than pseudorandomness: the ideal cipher model.  Pseudorandomness is a kind of logic quantifier: for uniform random $k$, $f_k$ is hard to distinguish from a uniform random permutation, and it applies to specific function families like HMAC-SHA256.  In the ideal cipher model, we study protocols where the function family itself is randomly chosen: for all distinct $k$, $f_k$ is an independent uniform random permutation.  Like the random oracle model, it is a model for how adversaries are structured, rather than a ‘property’ that a specific computable thing like SHA-256 or HMAC-SHA256 can exhibit.


Paillier encryption: Many private keys for a public key

No, that doesn't work.

If one party chooses primes $p,q$ and sets $n = pq$, then other parties would also have to know $p$ and $q$, because it is the only way to get the same $n$.

But you just left out a part of the public key, which is $g$. This results in a different question:
If you have a trusted party set up $n$ and assign different $g$ values to each party, would that work? No it would not, because in the decryption process you need to calculate $c^{\lambda}$. And knowing $\lambda$ would allow the factorization of $n$. So basically every party would be able to decrypt the messages to every party, as if they were just using one public key.


Formal proof of theorem concerning the Random Oracle Model

As @K.G pointed out in the comments - the proof is obvious.

I'll explain:

We sample the function $h$ from the set of all possible functions that maps from the set $\mathcal{X}$ to the set $\mathcal{Y}$, where the size of the set $\mathcal{Y}$ is $M$. We denote the set of all possible functions from $\mathcal{X}$ to $\mathcal{Y}$ by $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$.
Note that it doesn't matter whether $\mathcal{X}$ is finite or infinite, as far as every function in $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is defined on every value in $\mathcal{X}$ (which is the case, of course, by the definition of $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$). Then, if $|\mathcal{X}|$ is infinite, your question is in place: how can we hold such an $h$ (its size is infinite while our memory is finite)? The answer is that we can determine $h$ on-the-fly, whenever $h$ is being queries on $x$ first check whether $h$ was queried on $x$ beforehand, if so, there is an entry $(x,y)$ in $\mathcal{x}_0$ and we return $y$. Otherwise, if $h$ was not queried on $x$ before then we sample a uniformly random element $y$ from $\mathcal{Y}$ and add $(x,y)$ to $\mathcal{X}_0$.
Also note, that although the author only mentioned that

  $h\in \mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ is chosen
  randomly

he actually meant that $h$ is chosen randomly from a uniform distribution over $\mathcal{F}^{\mathcal{X}\rightarrow \mathcal{Y}}$ (otherwise the theorem is incorrect).
Now, take some $x\notin\mathcal{X}_0$, i.e. $h$ wasn't queried on $x$ before (thus, we don't know its answer to such query yet). Since $h$ was chosen uniformly at random from all possible functions it means that for every query $x\in\mathcal{X}$ $h$ would answer with a uniformly random element from $\mathcal{Y}$ and since $|\mathcal{Y}|=M$ every $y\in\mathcal{Y}$ has the same probability to be chosen as the answer for the query $x$. This probability is simply $Pr[h(x)=y]=1/M$.
Note that the above probability depends only on $M=|\mathcal{Y}|$ and not on $|\mathcal{X}|$ because the result of $h$ when applied to the query $x$ is an element which is chosen randomly from a uniform distribution over $\mathcal{Y}$, thus, every element $y\in\mathcal{Y}$ has the same probability to be chosen.


Decomposing a vector of random bits into constituent XORed vectores

If solutions of more or fewer than $m$ vectors are also admissible, this is easy: XOR of $n$-bit strings can be rephrased as addition in the vector space $(\mathbb Z/2\mathbb Z)^n$. You are looking for a solution to the linear equation
$$ a_1v_1+\dots+a_mv_m=y $$
where $v_1,\dots,v_m\in (\mathbb Z/2\mathbb Z)^n$ are all the public bit vectors, $y\in(\mathbb Z/2\mathbb Z)^n$ is the sum of a subset,
and the coefficients $a_1,\dots, a_m$ must be $0$ or $1$, that is, in $\mathbb Z/2\mathbb Z$.

As over any field, Gaussian elimination can be used to find a solution to such a system.

Here's an example: Suppose given the $4$-bit vectors $1111$, $0100$, $0101$, $0011$ and the result $1110$ of XORing some of them. We write those vectors into the columns of a matrix and perform the elimination (which becomes quite simple in this case as there is only one non-zero field element):
$$
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  1&1&1&0&1\\
  1&0&0&1&1\\
  1&0&1&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&0&1&0\\
  0&0&1&1&1
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&1&1&1\\
  0&0&0&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&1&0&0\\
  0&0&1&0&1\\
  0&0&0&1&0
\end{array}\right)
\leadsto
\left(\begin{array}{cccc|c}
  1&0&0&0&1\\
  0&1&0&0&1\\
  0&0&1&0&1\\
  0&0&0&1&0
\end{array}\right)
$$
The steps performed are:

Add (that is, XOR) the first row to all other rows.
Swap the third and fourth row to obtain a one on the diagonal.
Add the fourth to the third row.
Add the third to the second row.

Now we can read off the result in the rightmost column: The target vector is the XOR of the first three input vectors, that is, $1111\oplus0100\oplus0101$.


How are side-channel attacks executed? What does an attacker need to execute a side channel attack?

Here's a very simple timing side channel attack that you might even see in movies.  Suppose you're trying to log in to a computer with a password, and the victim compares your password byte by byte but stops early if there's a mismatch:

for (i = 0; i < n; i++)
  if (password[i] != input[i])
    return EFAIL;

How do you attack this?

Try a password like aaaaaaa, and use a stopwatch to measure how long it takes; then try baaaaaa, caaaaaa, and so on, and whichever one takes the longest time—say haaaaaa—tells you what the first letter is.

Of course, there may be noise in the timings, so you may have to try each one several times and gather statistics to see the signal through the noise, or carefully arrange that input[i] is in an unmapped or uncached virtual page to amplify the signal of whether the comparison routine reached it.

Then repeat with hbaaaaa, hcaaaaa, etc., until you find huaaaaa; then hunaaaa; then huntaaa; until you've got the password.

How do you defend against such an attack?  Standard countermeasures: rewrite the logic in constant time so that the time it takes is the same for all inputs, and/or judiciously randomize the problem so that any variation in the time is independent of the variation in inputs.

This is only one of many, many types of side channels.  Here are a few other examples and roughly what you need to pull them off:

The CRIME and BREACH exploits take advantage of the compression ratio as a side channel for secret content, namely HTTP cookies.

If the software foolishly passes secrets through compression and reveals the resulting length, what you need is a JavaScript program to run in the user's browser to trigger HTTPS requests for some target site, and an eavesdropper on the network to watch them.

(Most browsers don't do this kind of naive compression any more, because of such attacks!)
Padding oracle attacks like Serge Vaudenay's exploit different types of error messages—padding error vs. authentication failure—as a side channel for secret content of messages.

If the protocol is badly designed (like the original SSL protocol) and the software behaves differently for padding errors and authentication failures (like early SSL implementations), what you need is a MITM on the network who can intercept packets on the wire and modify them to see how the peer behaves.

(Modern TLS no longer uses cryptosystems susceptible to padding mistakes like this, and modern implementations of older versions of TLS/SSL take extra effort to avoid padding oracles—but even the countermeasures sometimes admit other side channel attacks like Lucky Thirteen.)
The Spectre class of attacks exploits side channels arising from timing of speculative execution in CPUs.

If the CPU naively implements speculative execution like essentially all mass-market desktop, laptop, and server CPUs for the past two decades, and if the software doesn't have extensive countermeasures to thwart this class of attacks, what you need is a JavaScript program running in the browser with access to a reasonably high-resolution timer (which, with extra effort, can be simulated using a lower-resolution timer) to set up a Spectre gadget and measure it—and it works even if all the cryptography is safely implemented without side channels of its own like timing attacks below, because it works by using the CPU's speculative execution to reach into memory it shouldn't have access to at all.

(Spectre is baaaaaaaaaaaad news.)
Timing attacks on cryptosystems exploit computations with secret-dependent running times as a side channel for the secrets.  There are many reasons computations might take secret-dependent time, a class of side channels reported in Kocher's seminal paper:

When computing, e.g., the RSA private key operation $x^d \bmod n$ for secret $d$, it is tempting to use a standard square-and-multiply algorithm that checks $(d \mathbin\gg i) \mathbin\& 1$ to decide whether to multiply by $x$ or not at the $i^{\mathit{th}}$ step.  CPUs are bad at keeping branch decisions secret in the first place; skipping a multiplication can changes the time even more substantially, which may reveal which bits of $d$ are set.  What you need to exploit this is an automated system that responds to (say) encrypted queries, and a stopwatch.
When computing, e.g., AES, it is tempting to use secret-dependent table lookups.  CPUs are bad at keeping memory addresses secret—CPU caches are crucial for modern CPU performance, but also exploitable as a side channel.  What you need to exploit this is a JavaScript program in a web browser that can trigger AES operations under the target key, say the power to trigger and measure disk encryption timing as Tromer, Osvik, and Shamir demonstrated (paywall-free).
When checking whether an attacker-supplied message authentication code matches the legitimate message authentication code to verify a message or drop it as a forgery, a naive implementation might check the code byte-by-byte and stop early when it first mismatches: for (i = 0; i < n; i++) if (p[i] != q[i]) return EFAIL;.  If the software does this, what you need is a MITM with a stopwatch to attempt forgeries and guess the correct MAC on a desired forgery byte-by-byte like hackers in movies figure out passwords letter-by-letter.

The EFAIL attack exploits cryptographic flaws in OpenPGP and S/MIME to selectively modify encrypted email messages so that the recipient's mail reader will act on modified messages to just leak the secrets out directly.  What you need to apply this is the dumpster fire of an implementation ecosystem that is OpenPGP and S/MIME.

(That said, most OpenPGP implementations have now fixed the cryptographic flaw that enables this one.)
Computers sometimes sound different depending on what operations they're performing and on what data, leading to acoustic cryptanalysis (paywall-free preprint).  This may sound far-fetched because you need a sensor with physical proximity to the adversary…but people seem inexplicably excited to buy remote surveillance microphones from Apple, Amazon, and Google and put them in their homes!  Alternatively, can you deliver a JavaScript program to a victim that turns on their computer's microphone?

This is not a comprehensive study of side channels.  There are other entire classes of side channels like electromagnetic emissions or power analysis or active fault attacks.  However, these are a little less compelling as a remote exploitation vector—power analysis (whether simple power analysis or differential power analysis) and fault attacks are most relevant to smart cards, for instance, where the adversary has physical access to the device to begin with.

This is not a comprehensive study of what you need in order to exploit side channels either.  There may be countermeasures in place to make them harder.  There may be noise that makes them harder.  You might run out of patience trying to draft a proof of concept.  I drafted a Meltdown exploit but ran out of patience with Spectre, when they were first released, or vice versa, I forget.  It was a fun afternoon toy.  But the side channels that you have the patience to practically exploit are only a tiny subset of the side channels that an adversary—with a market of off-the-shelf exploitation tools—is potentially able to take advantage of.


RSA for key exchange is declining rapidly and is not recommended because it does not provide forward secrecy. Without forward secrecy, if someone breaks into the server and obtains the private key, they will be able to fully retroactively decrypt all recorded traffic encrypted under that key. ECDH does not have that problem because the private and public keys are generated on-the-fly, and discarded after use. This is possible because ECDH (and DH) key generation is light and easy on the CPU, whereas RSA is not. Generating a new RSA key pair for each key exchange would be absolutely prohibitive.

RSA for certificates, on the other hand, is still alive and well, and is still considered industry standard. There are some benefits that ECDSA has, though, such as smaller public key and signature sizes, which equates to reduced network usage, but verification with ECDSA is a little slower than with RSA.


What's the consequence of having a short IV? Is one mode better in that case?

The point of the IV is to prevent the same (key,IV) from ever being used for two different messages in practice. This is an absolute requirement for stream ciphers or block cipher modes such as CTR that are effectively stream ciphers, because re-using the same (key,IV) pair lets an eavesdropper trivially obtain the XOR of two plaintext messages, which means they are effectively decrypted. Other modes behave somewhat differently, but the IV requirements for a mode are generally non-negotiable, and security is broken if they are not followed.

With a smaller IV, the chances of using the same (key,IV) go up dramatically. Hashing a low-bit value as you suggest does not fix this problem at all, as there are only 65k IVs possible with a 16 bit counter.

If your application cannot handle transport of at least 96 extra bits with each message, you should exchange an "IV seed" at the start of your protocol, then each side can use that as the state for a CSPRNG and generate the IV for each packet on its own. Using something like HASH-DRBG is probably simplest, you start with your IV seed, concatenate a counter with value N, hash and use the output as the IV for packet number N.
Making this scheme tolerate packet loss while never ever repeating (key,IV) is left as an exercise for the reader; see the ChaCha TLS draft RFC as an example of how packet sequence numbers are used to generate IVs.
http://tools.ietf.org/html/draft-mavrogiannopoulos-chacha-tls-02


Existence of MAC implies existence of OWF

It is not hard to construct a secure MAC where $f(k) = \textsf{MAC}(k,0)$ is not one-way. Take any secure $\textsf{MAC}$ and define a new one as

$$\textsf{MAC}^*\Bigl( (k_1,k_2), m \Bigr) = \textsf{MAC}(k_1,m) \oplus k_2.$$

It should be relatively clear that $\textsf{MAC}^*$ is also a secure MAC. Now given arbitrary $m$ and $t$, it is easy to find a key under which $\textsf{MAC}^*((k_1,k_2,m)=t$. Just choose arbitrary $k_1$ and then solve for $k_2 = t \oplus \textsf{MAC}(k_1,m)$. This leads to a natural way to invert the $f$ function you propose.

Another way to look at things: The function $f(k) = \textsf{MAC}(k,0)$ can only rely on the fact that the MAC is secure against an attacker who sees just one output. But there are information-theoretic MACs with this property, and you can't expect them to imply a OWF.

To get around this, you should use $f(k) =\textsf{MAC}(k,0) \| \textsf{MAC}(k,1) \| \cdots \| \textsf{MAC}(k,\ell)$ as your OWF candidate, where $\ell$ depends on the key size of this MAC. But even then the argument of one-wayness is not trivial.


Is there a cryptographic solution to provide a “proof of exclusion”?

As shown recently$^1$ in [BBF], this can be carried out using universal accumulators [BdM].
Their construction is in the discrete-log setting in groups of unknown order (e.g., RSA group or class groups) and the size of both proofs of membership and non-membership is independent of the size of the set committed to. The security proof is in the generic group model under an "adaptive root" assumption. The main components of their construction is a hash function $H$ that maps strings to primes and a proof of exponentiation [W]. A long overview can be found in this blog-post. A shorter overview is given below.
Overview of the construction. Let's fix a group $G$ of prime order $p$ with a generator $g$. Loosely speaking, the value of the accumulator for a set $S$ is
$$\pi:=g^{\Pi_{s\in S}H(s)}.$$
To prove membership of an element $s^*$ in $S$, the prover gives out the co-factor, i.e., the product of all elements in $S$ except $s^*$:
$$\pi^*:=g^{\Pi_{s\in S\setminus\{s^*\}}H(s)}.$$
Given $\pi$ and $\pi^*$, the verifier simply checks whether $\pi=(\pi^*)^{H(s)}$.
Proving non-membership of an element $s^*$ in $S$ is trickier and requires an application of Bézout's identity that is due to Shamir [S]. Since $H$ maps elements to primes, with high probability $h^*=H(s^*)$ and $h=\Pi_{s\in S}H(s)$ will be co-prime and therefore there exists two numbers $a,b\in\mathbb{N}$ such that $ah^*+bh=1$. The proof now is $\pi^*:=(g^a,b)$ and the verifier checks whether
$$(g^a)^{h^*}\cdot\pi^b=g.$$
$^1$ The ideas were probably known before, but I couldn't find an earlier reference.
[BBF]: Boneh, Bünz and Fisch, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Crypto 19
[BdM]: Benaloh and de Mare, One-way Accumulators: A Decentralized Alternative to Digital  Signatures, Eurocrypt 93
[S]: Shamir, On the generation of cryptographically strong pseudorandom sequences., TOCS 83
[W]: Wesolowski, Efficient verifiable delay functions, Eurocrypt 19


He needs to add something uniformly random to the second coordinate, to get a distribution that is uniformly random. (The idea is that if he guesses the correct key, his rerandomization turns real instances into real instances. If he guesses the wrong key, his rerandomization should turn real instances into random instances.)

If $p$ is a prime, then multiplication by any non-zero value is a bijection, so a uniformly distributed $l$ maps to a uniformly distributed product $l(k-s_1)$.

If $p$ is composite, then multiplication by a value that isn't relatively prime to $p$ would not be a bijection, so a uniformly distributed $l$ might not map to a uniformly distributed product $l(k-s_1)$.


does publishing a SHA-256 fingerprint of that shared secret reveal any useful info about the derived keys?

No such leakage is known, and it would look quite unlikely.  The SHA-256 and SHA-512 compression functions (which process the hashed messages) differ in a number of significant details (including the size of the words being processed); any such correlation would be quite surprising.

So, your approach looks reasonable.  Of course, if you want to be totally cautious, you can rely on a similar mechanism which has been cryptography studied for this specific security property; you could do:

$EncryptionKey = HMAC( ECDH, \text{'Encryption'} )$

$MacKey = HMAC( ECDH, \text{'Mac'} )$

$Fingerprint = HMAC( ECDH, \text{'Fingerprint'})$

An explicit assumption with HMAC (as a Message Authentication Code) is that if you get the HMAC of one message (say, the string "Fingerprint"), that doesn't help the attacker determine the HMAC of another message (either "Encryption" or "Mac")


AES doesn't require uniformly distributed keys. However, if you have a key with less than 256 bits of entropy, then naturally your keyspace will be smaller than the maximum. Whether or not this is an issue depends on just how few bits you have. The only time a non-random key is bad for AES is when it's chosen very specifically to be harmful, in which case it can be used for a related key attack.

If your input is not uniformly distributed though, the standard technique is to pass it through a hash function like SHA-256 first, which compresses it to 256 uniformly-distributed bits. Or use a KDF.


What are the advantages of neural cryptography over Diffie-Hellman algorithm?

I am not an expert either, but from what I gather the intent is to create a key exchange mechanism that is not based on any number theory problem. The concern is that advances in computing such as quantum computing could make the existing one-way functions such as prime multiplication effectively a two-way function. The authors believe that the neural exchange process will not be as vulnerable to advances in computing.

However the authors also acknowledge that their initial implementation is vulnerable to attacks using probabilistic analysis or genetic algorithms.

So at the moment, there is no advantage. The research is based on creating a future advantage, assuming that they can create a more secure implementation, and that future attacks do in fact become more sophisticated in the way that we expect.


I have been part of several cryptographic competitions (AES, eSTREAM, SHA-3, PHC). In every single one of them, some people worded bitter reproaches and wailed and whined about the unfairness of the selection process. It's just that people are like that, and being very good at cryptography does not prevent smart cryptographers from being basically people.

The mailing-list was hosted on Gmane, which was a free resource maintained by somebody on his spare time. In July 2016 he decided he had had enough of it (he was fed up with recurrent DoS attacks). The PHC mailing-list archives, though, were recovered and put back online by Alexander Peslyak (aka "Solar Designer", who was behind the yescrypt PHC candidate). You can see for instance the winner announcement there.


Can I Implement a Well-Trusted Protocol with Well-Trusted Libraries in JavaScript securely?

If you have to implement or design and implement your own protocol then using well established libraries is generally the way to do it. JavaScript is a large eco-system. For such ecosystems it is not adviced to implement your own (partial) "hazardous materials" library for the low level functionality that you require. It is much more likely that there is something out there that would be more secure.

Of course, if there already is a higher level protocol or protocol implementation out there then you should definitely try and use or improve that. Developing transport security - which is often what is tried with JavaScript - is very hard.  This is why most of the time the best solution is to use TLS underneath.


Difference between Identity-based encryption and multiple key-pairs of public key encryption?

What is the difference between Identity-based encryption and multiple key-pairs of public key encryption scheme?

It's all about the public key.  You state, with your public-key based system:

  … and all the public keys are public (any one can know it).

But if Alice wants to send Bob a message, how does she learn his public key?  After all, any such public key is a long random looking bitstring.  Now, there are possible ways:

The trusted key generator could just send everyone's public key to everyone else (as you stated), but that really has serious scalability problems
Alice could look it up in a public directory of everyone's public keys (but that still has scalability problems, but less bad ones than the previous idea)
Bob could put his public key in a certificate, and so when Alice wants to send Bob an encrypted message, she asks him for his certificate first (but that requires Bob to be able to interact with Alice when she wants to send the encrypted message).

In contrast, with IBE, the public key could be anything; Bob's public key could be, for example, "bob@example.com"; and so if Alice knows Bob's email address (which she may need to send the message anyways, she then knows his public key).


Difference between plain AES CTR and "CCM-style" CTR

The CTR part of CCM is basically the last for loop in the _ctrMode function:

  for (i=0; i<l; i+=4) {
    ctr[3]++;
    enc = prf.encrypt(ctr);
    data[i]   ^= enc[0];
    data[i+1] ^= enc[1];
    data[i+2] ^= enc[2];
    data[i+3] ^= enc[3];
  }

i.e. CTR is simply: encrypt a counter block with a block cipher, xor the encrypted block into the data, increment the counter, repeat...

(For those not used to the SJCL APIs, they tend to operate on 32 bit words rather than bytes).

As CodesInChaos mentions, while a CTR mode has been standardised (in NIST SP800-38A), 'CTR' is used as a component of a lot of other modes (e.g. CCM, GCM, SIV, EAX) and they differ substantially in how the initial counter is constructed (although most will follow the same basic approach once that is done).


What happens if an RSA key pair has identical public and private exponents?

No, the public and private exponents will never be the same for real (that is, not toy) RSA keys.

The public exponent is almost always be deliberately chosen as a small value (with 65537, 3 and 17 being the most popular choices).  In contrast, the private exponent will always be a huge value; always at least $(p-1)/e$ (where $p$ is the larger prime factor of the modulus, and $e$ is the public exponent), and will generally (almost always) be much larger than that.  This implies that if you have a 1024-bit RSA key, and a public exponent of 65537, then the private exponent will be at least 495 bits long.

Even if you (for some unknown reason) select a random large public exponent, then it is still extremely unlikely.  If we look into the conditions that allow $d = e$, we see that both of the following must hold:

$e^2 \bmod (p-1) = 1$

$e^2 \bmod (q-1) = 1$

Having even one of $e^2 \bmod (p-1)$ and $e^2 \bmod (q-1)$ to be 1 is extremely unlikely; having both conditions happen is not something to worry about.


If they pad the key with some fixed value and apply RSA directly to it then it is just a textbook RSA scheme which is vulnerable to meet-in-middle attack: it runs roughly in time $2^{40}$ and requires $2^{32}$ space.


The simulator is just an algorithm. The idea is that for any adversary $A$, you can create an algorithm $S$ that can "simulate" $A$, that is, that has the same output as $A$.
The notation $S^{f}$ means that the algorithm $S$ does not has direct access to $f$, but just oracle access, i.e., every time $S$ wants to evaluate $f$ at an input $x$, it just sends $x$ to the oracle and gets $f(x)$. This formalizes the notion of "$S$ learns nothing about $f$ but pairs of input-output $(x, f(x) )$".
The actual input of $S$ is just the "size of the program". That is why we write $S^f(|f|)$.
On the other side, we have an adversary (also an algorithm) that has as input an obfuscation of the function, i.e., $O(f)$, and can evaluate the obfuscated function by itself, obtaining $O(f)(x) = f(x)$ for any $x$, but more than that, can actually analyze $O(f)$ to try to extract extra information about $f$.
Now, when we say that these two probability distributions are the same (or are indistinguishable), we are saying that both $S^f$ and $A$ behave in the same manner, i.e., the values output by them are the same. In particular, if $A$ can output some information about $f$, then $S^f$ also can. But then that information can be learned from the input-output pairs, since that is all that $S^f$ has, which means that the obfuscation $O(f)$ is not leaking extra information about $f$, as intended.


How does order-preserving encryption work on string?

Paillier cryptosystem has the property that the product of 2 ciphertexts decrypt to the sum of the plaintexts.

Strings are integers. Only that they are usually large. So this algorithm is also available for strings.

This algorithm doesn't allow you to find encrypted string in a ciphertext.

If you want an encryption scheme in which you can do any operation with the ciphertext, see homomorphic encryption.


Does the elliptic curve (EC) cryptosystem outperform RSA and DL cryptosystems?

Simply put, elliptic curves allow you to use smaller fields.

Consider Diffie-Hellman: given $p$, $g$ and $x$, you compute $g^x \mod p$. To ensure security, you must use values of $x$ and $p$ which are large enough to defeat known attacks. In practice, $x$ will need to be at least 160-bit long, while $p$ will be a 1024-bit prime.

Now, the elliptic curve variant: you have a curve $E$ where point coordinates are elements of a field of cardinal $q$, and you compute $xG$ for an integer $x$ and a conventional point $G$. To achieve security, you need $x$ to be a 160-bit long integer, as with the plain DH case; however, it suffices that $q$ is also a 160-bit integer (e.g. a 160-bit prime). Computing $xG$ will require roughly ten times as many field operations than computing $g^x$, but these operations will be performed in a much smaller field, more than 6 times smaller. Since the elementary cost of a field operation is, in practice, quadratic in the field size, you infer that field operations modulo $q$ will be about 40 times faster than field operations modulo $p$. Even if you do ten times as many, you are still 4 times faster with the curve than with plain DH.

The performance ratio increases with higher security levels (e.g. a 224-bit curve will give you roughly the same security than a 2048-bit plain DH key, leading to a factor of more than 8 in favour of the curve).

For storage, elliptic curves are also better: a 224-bit curve point can be represented over 225 bits (and you can often lower that to 224, at least for Diffie-Hellman), whereas a 2048-bit integer uses, well, 2048 bits.

The RSA public operation (raising to the power $e$ modulo $n$, where $e$ is the public exponent) is still a tad faster than public key operations with ECC-powered algorithms, but for private key operations, curves win hands down (if properly implemented, of course).


Are there signatures that don't have subliminal channels?

According to this answer, RSA with the "usual" "padding scheme, described in PKCS#1 as the

'old-style, v1.5' padding," can be made to satisfy that; one would need to specify NULL or omission

and require that the public exponent's prime factors are all easily

findable and sufficiently bigger than the 4th root of the modulus.


Why are different private and public key generated in online brainwallets?

They are the same, bitaddress.org uses an option that you missed; compressed and uncompressed addresses. Turn the compressed address on, then you will get the same values.
They both use base58 while displaying the content when converted to hex
uncompressed
pub  00515da4ade2ea43379043341d158ba1637e695c7b9d942422
priv 8012e29482949d92ef7c159f27065ef7bda744cc0dde8551cc324b312ce6736e24 7af43428

and compressed
pub  00b3f704fd7f30d5868f0e070b7adf75703313775717588aa4
priv 8012e29482949d92ef7c159f27065ef7bda744cc0dde8551cc324b312ce6736e24 01 3445217c

0x08 is always prepended, 0x01 is the indicator for the compression, and the last 4 bytes are trimmed double SHA256 checksum.

Note that generating your private key online is really really a bad idea.


Yes, according to NIST SP 800-56A revision 2, a KDF based on HMAC-SHA-256 is a suitable option.

The basic idea behind using a Key Based Key Derivation Function KBKDF is that the output of the the primitive within the key agreement protocol (DH, ECDH) returns enough entropy for a key to be created. However that entropy may still be distinguishable from random. For instance, the first bit of the secret after a Diffie-Hellman key agreement will certainly be biased. Hence it is required that a KDF extracts the entropy into a key that is indistinguishable from random.

Besides the extraction of the entropy, the KDF may also be used to expand the amount of key material. This key material can be generated by supplying different otherInfo or counter to the KDF (preferred) or by requesting a larger output from the KDF. Note that the entropy within the keys is still bounded by the entropy in the output of the extraction phase or the internal state of the KDF.

The question if the secret can be used as symmetric key directly depends on the key agreement used. I've asked a specific question for Diffie-Hellman here. Note that the KDF calculation should take a small amount of processor time and memory, especially compared to for instance DH or ECDH.


How can SSL secure a two-way communication with only one key-pair?

That's not quite correct.  In SSL, two things happen:

First, a session key is negotiated using something like the Diffie-Hellman method.  That generates a shared session key but never transmits the key between parties.
Second, that session key is used in a normal symmetric encryption for the duration of the connection.

SSL does use public/private in one way, because an X509 certificate is used to identify at least one end of the connection.  Those certs are signed using an asymmetric key pair.


Is it better to maximize memory usage or number of passes with Argon2i 1.3?

As of October 2017, the resource I've found most useful for getting a quick, practical sense of how pick parameters for Argon2 is the (still draft) RFC, in particular section 9, which gives this guidance (in 9.2):

The best attacks on the 1-pass and 2-pass Argon2i is the low-storage attack described in [CBS16], which reduces the time-area product (using the peak memory value) by the factor of 5.  The best attack on 3-pass and more Argon2i is [AB16] with reduction factor being a function of memory size and the number of passes. For 1 gibibyte of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes. The reduction factor grows by about 0.5 with every doubling the memory size. To completely prevent time-space tradeoffs from [AB16], the number of passes must exceed binary logarithm of memory minus 26.

Since $\log_2(128\ \mathrm{MiB}) = 27$, this actually suggests that you should be able to use $t = 3$, $m = 128\ \mathrm{MiB}$ as your first alternative proposes.  (Yes, $27 - 26 = 1$, but you need at least three passes to defeat the [CBS16] attacks.)
It's also worth quoting section 9.3 in full:

9.3. Security for time-bounded defenders
A bottleneck in a system employing the password-hashing function is often the function latency rather than memory costs. A rational defender would then maximize the bruteforce costs for the attacker equipped with a list of hashes, salts, and timing information, for fixed computing time on the defender’s machine. The attack cost estimates from [AB16] imply that for Argon2i, 3 passes is almost optimal for the most of reasonable memory sizes, and that for Argon2d and Argon2id, 1 pass maximizes the attack costs for the constant defender time.

The draft RFC doesn't say which memory sizes they consider reasonable, but they do repeatedly use 1 GiB throughout the draft as a reference figure.  For example the reduction factors given in the first quote are based on 1 GiB, and the quote notes that these increase with more memory—but you're proposing to use less memory than that.

Or, as your question proposes and comments concur, you might consider not using Argon2i.  The draft RFC in fact recommends Argon2id over either 2i or 2d.  Then you just need one pass, because the advantage of tradeoff attacks on 2d and 2id doesn't depend on the number of passes (section 9.2):

The best tradeoff attack on $t$-pass Argon2d is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.
The best attack on Argon2id can be obtained by complementing the best attack on the 1-pass Argon2i with the best attack on a multi-pass Argon2d. Thus The best tradeoff attack on 1-pass Argon2id is the combined low-storage attack (for the first half of the memory) and the ranking attack (for the second half), which bring together the factor of about 2.1. The best tradeoff attack on t-pass Argon2id is the ranking tradeoff attack, which reduces the time-area product by the factor of 1.33.

So for 1 GiB memory size, you need six passes of Argon2i to reduce attacker advantage to a similar level as one-pass Argon2id (2 vs. 2.1), and both are still behind Argon2d (1.33).  This speaks strongly in favor of Argon2id, and is presumably the reason the draft RFC recommends it.


Rotor that divides binary number by mod 3

This is not really a cryptographical question, but rather a (rather simple) question about a finite automata.
This is a state machine; you feed in the bits of the number $n$ you're modding, starting at the msbit (and starting at the state $q0$).  After processing the number, if the state you end up in is $q0$, then $n \equiv 0 \pmod 3$, if you end up in $q1$, then $n \equiv 1 \pmod 3$, and if you end up n $q2$, then $n \equiv 2 \pmod 3$.

Does it only work for determined length of plaintext?

No, it'll work for any size integer.

What algorithm is behind this scheme?

Well, I suspect it's too simple to have a formal name.  The property that always holds is that, after processing an intermediate integer $\hat{n}$ (which has the binary representation of the bits you're processed so far), if $\hat{n} \bmod 3 = i$, then you'll be in state $qi$.
Here's how that property is preserved: assume that property holds at some point.  Then, when you process the next bit $j$ (which means that you will have processed the intermediate integer $2\hat{n} + j$, it will transition to state $q(2i+j \bmod 3)$ (you can verify this by manually going through the state transitions).  And, since $2\hat{n} + j \equiv 2i+j \pmod 3$, this preserves the above invariance.  Since we start with the property holding (that's why it's important we start at state $q0$), it holds no matter how many bits you process.


Would finding a Merkle-Damgård preimage that doesn't change the initial state allow an attacker to prepend it to any hashed message?

Not quite. But it would allow computing ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, {\rm whatever})$, where ${\rm pad}_M$ and ${\rm pad}_m$ are the extra length padding bytes appended to $M$ and $m$ respectively by the MD5 algorithm, as described in RFC 1321 sections 3.1 and 3.2.

To see why, it's worth looking at how the MD5 hash (like other similar hash functions based on the Merkle–Damgård construction) works.  Specifically, MD5 consists of a compression function $f: \{0,1\}^n \times \{0,1\}^b \to \{0,1\}^n$ (where, for MD5, $n = 128$ and $b = 512$), a fixed $n$-bit initial state vector $IV \in \{0,1\}^n$ and a padding scheme for extending an arbitrary input string to a multiple of $b$ bits (and also encoding its length into the padding).

For our purposes, it turns out to be useful to also define the iterated compression function $f^*$ that takes an $n$-bit IV $s_0$ and a sequence of $b$-bit input blocks $(m_1, m_2, m_3, \dots, m_k)$ as input, and returns the $n$-bit output $s_k$, where $s_i = f(s_{i-1}, m_i)$ for $1 \le i \le k$.  Then, for any given input message $m$, we have $${\rm MD5}(m) = f^*(IV, m \,\|\, {\rm pad}_m).$$

In particular, the usual MD5 length extension attack lets us, given $H_m = {\rm MD5}(m)$ and the length of some unknown message $m$, compute ${\rm MD5}(m \,\|\, {\rm pad}_m \,\|\, x)$ for any arbitrary suffix $x$ as $f^*(H_m, x \,\|\, {\rm pad}'_x)$, where the modified padding ${\rm pad}'_x$ is the same as the normal MD5 padding for the message $x$, except that the input length encoded in the padding is increased by the length of the prefix $m \,\|\, {\rm pad}_m$.

Now, in your scenario, we have a special message $M$ such that $${\rm MD5}(M) = f^*(IV, M \,\|\, {\rm pad}_M) = IV.$$  Thus, by the construction of the iterated compression function $f^*$, we also know that $$f^*(IV, M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m) = f^*(IV, m \,\|\, {\rm pad}_m) = {\rm MD5}(m).$$

Thus, given ${\rm MD5}(m)$ and the lengths of $M$ and $m$, we can compute ${\rm MD5}(M \,\|\, {\rm pad}_M \,\|\, m \,\|\, {\rm pad}_m \,\|\, x)$ as $f^*({\rm MD5}(m), x \,\|\, {\rm pad}''_x)$, where the modified padding ${\rm pad}''_x$ now encodes the combined length of $M$, ${\rm pad}_M$, $m$, ${\rm pad}_m$ and $x$.


Using Whirlpool hashing function to encrypt data

Occasionally, for instance in very constrained environment, it can be useful to use only a few cryptographic primitives for all processing. (When you only have a hammer everything looks like a nail.)

In such environments, it may be useful to use key derivation function to derive stream to be used as a stream cipher, or use hash function as cipher and so on.

However, using primitives in non-standard ways risks implementation mistakes and often is "path less traveled", thus risking vulnerabilities that were not thought of.

EncryptedData = Concat(DataBlock XOR Whirlpool(DataBlock + SecretKey))

Have you thought of decrypting data encrypted this way? The DataBlock is supposedly to be kept as a secret, but Whirlpool takes it as input. Thus, to decrypt EncryptedData, it is necessary to know DataBlock.

A pretty well examines way of using hash function based on cipher function as cipher is SHACAL-2. SHACAL(-2) is one of the most well examined "hash-function turned into cipher" constructs. It has been used with SHA-1 and SHA-2 hash functions. It would be possible to use similar construct to turn (some implementations of) Whirlpool into a forward cipher function, and then use that in, in counter mode.

If it is mandatory to use entire Whirlpool function (above "WhirlpoolCAL" construct would not use padding part of hash function), then you could, for instance, use key derivation construct as stream cipher. See NIST SP 800-108 Recommendation for Key Derivation Functions using Pseudorandom Functions. The document shows a few ways that could be used to construct keys stream using a hash function (approved hash functions are SHA family, but here you would use Whirlpool). Note the NIST SP 800-108 requires HMAC construct to build keyed hash function from hash function.

That document also warns against idea of using the function as stream cipher:
"To comply with this Recommendation, the derived keying material shall not be used as a key stream for a stream cipher2.
2 The level of security provided by using the key derivation functions specified in this Recommendation to generate a key stream for stream ciphers has not been investigated."

So summary is, that you "could" do it like this:

EncryptedData = Data XOR KDF(HMAC(Whirlpool))

Where KDF is implemented using the following process (see the above mentioned document SP800-108 for full details).

Process:

n := ⎡L/h⎤.
If n > 2r-1, then indicate an error and stop.
result(0):= ∅.
For i = 1 to n, do
a. K(i) := PRF (KI, [i]2 || Label || 0x00 || Context || [L]2) 12
b. result(i) := result(i-1) || K(i).
Return: KO := the leftmost L bits of result(n).

But: The comment above from Stephen Touset, the SP 800-108 document, and this answer also, are all warning against doing it this way. Use good cipher like AES (or maybe Camellia or ARIA or whatever) in appropriate mode for symmetric encryption and decryption needs and avoid home-baked cryptography.

(AES-CTR if you want to use XOR and no message integrity. AES-GCM is typically even better idea.)


Why this example about pseudorandom generators is performed like that?

Bob sends random number so they can use their shared secret for authentication process many times.


Generating HMAC-SHA256 - is this procedure secure enough?

If you do this like that you won't guarantee the authenticity of your message, only its integrity, as you say you want to... but then if you only need to check integrity, you would be fine with a simpler SHA256.

But FWIW, HMAC is like a wrapper around a secure hash function adding a key, so if you remove the key, you end up with a secure hash function, plus some sequin, if I dare say so.

So, I wouldn't say it is secure per se, unless I knew what problem you are trying to solve, but this way to go will provide you with integrity while using a somewhat more complicated method than usual. (Which is generally not recommended.)

EDIT to address Artegon's comment:
If you really want to use HMAC for your purpose (which is to compare a client value with a value in the server database), you can do so with a challenge-response mechanism, you can use for example the SCRAM one which will use PBKDF2 and HMAC, like you do, but in a way that guarantee that the secret is not leaked and the authenticity of the parties is assured even in case of a MITM.

Otherwise you can devise one which is weak to MITM attack by simply doing the HMAC of the challenge using the secret value as HMAC key... (But you should do so only if you know for sure your channel is secured against MITM attack thanks to public key crypto/a shared secret/etc, otherwise you have to first establish a secure channel, e.g. using your shard secret value to do so... But then you could as well use SCRAM, since it already exists and is good.)


Webapp password storage: Salting a hash vs multiple hashes?

Short summary: Don't do it, use an established password hash function like bcrypt, scrypt or PBKDF2.

Long form:

What you are doing here in effect is this:

Create a combined hash algorithm out of several different hash algorithms (or block ciphers made into hash functions).
Use a salt input to the combined algorithm to decide which of these algorithms to call in which order.
Store the salt and the resulting hash.

There are three ideas hidden here: A salt, repeated hashing, and use of different hash functions.

The reason to use a salt for password storage (or any usage of a password, really) is to avoid that the attacker can simply use a rainbow table - or, in fact, to make the needed rainbow table that many times bigger. As an example, if you have tree algorithms which will all be used, in a random order, you in effect have 6 possibilities (123, 132, 213, 231, 312, 321), which means a rainbow table has to be six times bigger.

At the same time, the hash execution time will be three times longer, so generating the rainbow table takes in effect 18 times the original time.

To make a rainbow table attack totally ineffective, you use a salt that big that it is not practical anymore to use a rainbow table (since it would need to long to generate and too much space to store). The Bcrypt algorithm, for example, takes an 128 bit salt input. A rainbow table for just a single password and all possible salts would take $2^{128}$ entries.

A salt alone still does not help against a brute force attack - you can check all realistic passwords in a dictionary for MD5(salt | password) == hash just as fast as MD5(password) == hash.

Here your second idea comes in: Repeated hashing. In your example, you use three hash invocations for each password - this means brute-forcing a single password takes three times the time as brute-forcing it with a single hash function. Three times is not much.

Instead, use a lot larger number of hashes. There are specialized slow hash functions around (like bcrypt), which have a configurable work factor build in - e.g. they take beside the hash and password input a work factor parameter, which says how often is should loop. You then can simply scale this with the hardware progress so your user does not have to wait too long for login, but an attacker still needs very long to crack the password.

Other schemes (like PBKDF2) use a fast hash function (like MD5, SHA-1, SHA-2) a large number of times (something like Hash(password, hash(password, hash(password, ...(password, hash(password, salt))...)))).

Your third idea is using a different hash algorithm depending on the salt.
Using a different salt as input to a hash function has a similar effect to using a different hash function, but is much simpler to implement. Using different algorithms makes your combined algorithm harder to analyze (i.e. harder to guess about its security), and also harder to implement. Also, you are depending on the security of multiple algorithms.

I could think about using different algorithms to secure against cryptanalytic breakthroughs in any of them, but then you should always use all of them, and there is no reason to randomize which algorithm to use.

So, don't do this, use instead an established password hash function like bcrypt, scrypt or PBKDF with an appropriate work factor. (These all include the use of salt.)


This seems to be correct.

I do see one possible attack vector where repetition of the request could be used for DPA attacks on the decryption key. It is basically the plaintext when looking at the decryption using the passphrase. It is also the encryption / decryption key for the subsequent operation using the key. But that's a scenario that is less likely than an attacker holding the smart card and trying to use DPA to retrieve an encryption key.

If you send the password in plaintext then you should of course consider the security of the password before it actually reaches the smart card. DPA attacks are not interesting if the adversary can simply eavesdrop on an unprotected password.


AES is a symmetric cipher — it needs the same key for encryption and decryption. Thus, in order for the code to encrypt anything with AES, it must have the key stored somewhere. Find that key, and you will have completely broken the encryption.

(It's possible that the key isn't stored directly, but is derived from some other data stored in the program code. It's even possible that the key depends on the machine number in some way; this would make it impossible to decrypt the encrypted number without already knowing the real machine number, but for just verifying that the numbers match this would be fine. In any case, as long as you know what inputs the key is calculated from and how, you can repeat the same calculation yourself.)

All that said, I'd really recommend tossing out the code and getting someone more trustworthy to rewrite it for you. You already know that the original author cheated you, obfuscated their code and included at least one hidden booby-trap in it. Do you really want to take the risk of bypassing that trap and using the code, only to find out that the next trap will physically damage your machines? Besides, with only an obfuscated binary, you won't be able to fix the code when (not if!) you find a bug in it, anyway.


For #1, binary is used for a number of reasons. First, XOR is a logical operator, so it only operates on bits. Modern computers store everything as bits, too, so that makes XOR convenient.

As for why the first picture is not in bits, that is because no one uses (or at least should) use substitution ciphers such as the one proposed on modern computers. That substitution cipher is extremely insecure. Those sorts of ciphers were typically seen in the pre-computing age, so showing it with an alphabet instead of in bits makes sense. You could, however, show the same graphic with binary text. You'd first have to break up the binary into groups of values (maybe 4 or 5 bits per group) and show a substitution table for the 4 bit values.

For #2, the key is used to produce the cipher stream. That is not shown in the picture.


"In a good cipher system, each bit of the ciphertext should depend on all bits of the plaintext"

This property is also called the "avalanche effect" and is usually an explicit design guidance when designing novel block ciphers whereby flipping any input bit gives about a 50% chance to also flipping all output bits, ensuring maximal dependence of all outputs bits on all input bits.

The standard (formal) security definition of a block cipher is that of a pseudo-random permutation where an efficient, probabilistic adversary has to distinguish whether they're looking at a fully random permutation (where each unique requests gets a random previously unseed response sampled on request) or at the keyed permutation with an unknown key.

It is widely believed that modern ciphers like AES satisfy the above definition.

Now if not every bit of the output depends on the input, you can find two distinct inputs that give related outputs, something that wouldn't happen for an ideal permutation and allowing an adversary to find out whether they're looking at the non-ideal permutation.

The practical application could for example be a bias in the output where one bit doesn't e.g. depend on the least significant bit of the input. Then when you're using the cipher in counter mode you'd get that bit to be the same twice in a row, leaking information about the plaintext at these points, like with a reused one-time-pad.


No, DES* (which I'll call your "DES modified to use 128 bit keys") would not be as secure as AES; two reasons spring immediately to mind:

Block size; DES* would still have 64 bit blocks; most block cipher modes start to leak information when you get close to the birthday bound; for DES*, that'd be 32Gigabytes, which isn't that long for common use.  In contrast, AES (which has a 128 bit block size) has a birthday bound of circa 300Exabytes
Linear cryptanalysis; DES is known to be weak against linear cryptanalysis; depending on how you map the 128 bit keys to the DES* subkeys, DES* may very well be as well.  Of course, AES is known to be immune to linear cryptanalysis


Can you really insert the text you want in one-time pad?

It is quite simple and stems from the idea that flipping one bit in the ciphertext flips the corresponding bit in the plaintext.

So, say the ciphertext is $1011$ and we know the plaintext is $0101$ (thus the key is $1110$). Say we want a plaintext of $0000$, we just have to change the ciphertext to $1110$ (notice where the bits have been flipped) and we have $1110\oplus 1110=0000$

In that sense you if you can flip any bits you want and you know what the plaintext says and you know what you want the plaintext to say, you flip the right bits in the ciphertext and decryption comes out as you desired.


Found a mistake in a proof about when GGH will decrypt incorrectly

Okay, this was a really stupid mistake by me. I got confused because some sources use notation where $R$ and $B$ have the basis vectors as rows. However Goldreich, Goldwasser and Halevi have the basis vectors as columns so
$$B=RU\implies U=R^{-1}B.$$ Hence the matrix is unimodular and the proof works. Sorry about the inconvience.