An older copy of P1363 Public Key Cryptography was used below. In may (or may not) reflect the current state of affairs.

It also uses Bernstein's RSA signatures and Rabin–Williams signatures: the state of the art.

  Do tweaked roots violate P1363? What I might be really asking is, does an exponent of 2 run afoul of P1363, but I'm not sure at the moment.

No. The requirements IEEE places on them in 8.1.3.2 RW key pairs is:

  An RW public key consists of a modulus n, which is the product of two
  odd positive prime integers p and q, such that p ≡⁄ q (mod 8), and an
  even public exponent e (2 ≤ e < n), which is an integer relatively
  prime to (p – 1)(q – 1)/4. [Note that these conditions imply that p ≡
  q ≡ 3 (mod 4); moreover, one of the primes is congruent to 3 (mod 8)
  and the other is congruent to 7 (mod 8).]

So IEEE requirements are witness to tweaked roots.

  If I load a private key generated by another library and it does not satisfy the conditions on p and q, then what are the remaining options? Is it principal roots and Jacobi?

If its satisfies IEEE requirements, then one prime ⊂ 3 + 8Z, and the other prime ⊂ 7 + 8Z.

If I relax requirements to those surveyed by Bernstein, then I only need to satisfy p, q ⊂ 3 + 4Z. In this case, the efficiency of tweaked roots is lost and it looks like Jacobi is needed.

While its not readily apparent, Jacobi is needed for the blinding that gets applied. Its not strictly required for the mathematics, but it is needed for the cryptography. You can see an example of it in practice in Sidorov's Breaking the Rabin-Williams digital signature system...:

do
{
    r.Randomize(rng, Integer::One(), m_n - Integer::One());
    rInv = modn.MultiplicativeInverse(r);
}
while (rInv.IsZero() || (Jacobi(r % m_p, m_p) == -1) || (Jacobi(r % m_q, m_q) == -1));


How to communicate authentication tag for GCM?

I currently manually append the "tag" property to the ciphertext, is this the correct method of authentication?

That is a perfectly acceptable method. In the end, there needs to be some protocol which tells the other party where the ciphertext is and where the authentication tag is. In your case, the other party knows that the last 128 bits of the message contains the authentication tag.


How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

In the question you said that $a^x\equiv b\ (mod\  p)$ and $P,Q\in E(\mathbb{F}_p)$. In general case, the number of elliptic curve points $\#E(\mathbb{F}_p)$ is not equal to $p$. So these two groups are not isomorphic and your question is wrong.

If $\#E(\mathbb{F}_p)=p$ the curve is called anomalous and we can find the map $\psi :  E(\mathbb{F}_p) \to \mathbb{Z}_p$ in polynomial time. In this state, $a=\psi(P),b=\psi(Q)$ and $x=d$.

The main idea behind Pollard’s rho algorithm is to find distinct pairs $(c' , d' )$ and
$(c'' , d'' )$ of integers modulo $n$ such that $c' P + d' Q = c'' P + d'' Q$. So $(c' − c'' ) = (d'' − d' )d \pmod n$. Hence $d$ can be obtained by computing
$$d = (c' − c'' )(d'' − d' )^{ −1} \pmod n.$$

For more details you can see page $156,168$ of "Guide to elliptic curve cryptography", Hankerson, ....


Why do we keep designing new static s boxes?

There are simply a long list of properties for S-boxes that are relevant, see for example these questions:

Desirable S-box properties
S-box design criteria and random sboxes

In addition people have been trying to design S-boxes that are fast to implement in hardware or in software or which can be masked efficiently. For example the Midori S-box is designed to be especially energy efficient.

The search space for S-boxes is actually quite big as well; for 4-bit S-boxes (pretty small) there are $16! \approx 2^{44}$ possibilities.

This might be a nice read: Cryptographic Analysis of All 4×4-Bit S-Boxes


linear cryptanalysis: how are the subkey bits removed from the linear approximation?

So after re-reading a few times it becomes clear. The key bits are static, so they won't change the probabilities.

Now suppose that $\sum_K = 0$, then the equation in (5) will be true, with probability $\frac{15}{32}$ since it is the same equation.

Suppose now that $\sum_K = 1$, the equation in (5) is now the inverse, and it will thus happen with probability $1-(15/32).$


How can I instantiate a generalized hash function?

Can you please explain me what this notation means?

Of course, $f:A\times B\times C\rightarrow D$ is fancy mathematican's language for saying: "a function f, that takes an element from A, B and C (in this order) and maps this to an element of D" (arbitrarily extend this explanation to as many arguments as you wish).

In this particular instance, the authors of these papers didn't actually care about which hash function should be used as long as it fulfills the usual properties of a hash and maps from the right set(s) to the right set, as the situation requires. For example if you want to derive a key from a shared Diffie-Hellman secret (which is an integer in $\mathbb F_p$ and nothing else) you formally need a hash function $H:\mathbb F_p\rightarrow \{0,1\}^l$, where $l$ is the desired length of the derived secret. The fact that you usually do this by hashing the binary representation of the integer doesn't matter for theoreticans.

  How I can actually instantiate such a hash function?

First, I'll discuss the case where you only have one argument from the set of binary strings, then this will be adapted to arbitrary sets for the arguments and finally will extend this result to multiple arguments.

Assume you want to instantiate $H_3:\{0,1\}^*\rightarrow \{0,1\}^l$. For this you take your favorite n-bit hash function $H$ (e.g. SHA-256, SHA-512, SHA3-512, SHA3-256, Skein-512-512, Blake2b-512, ...). Now you use a key derivaton function, such as HKDF to construct an arbitrary hash or KDF2, which just hashes the input and with a counter that increments as long as you need more bits (your zero-based counter will be $\lceil\frac{l}{n} \rceil-1$ at the end).

The next step is to turn this into a hash function that outputs an arbitrary number (from the finite field): $H_1:\{0,1\}^*\rightarrow \mathbb F_p$. To do this you take the generic hash function we just constructed and reduce the output $\bmod p$ and you're done, $l\geq \lceil \log_2(p)\rceil$ in this case. This will be good enough for most uses. If you strongly require a uniform distribution, pick $k\geq 2\cdot \lceil \log_2(p)\rceil$.
Note that if you want to hash into $\mathbb Z_n^*$ with $n$ being composite, then you can in theory get values that are not in this set (like $p$ or $q$ if $n=pq$), but the chance of this happening are negligible if $n$ is sufficiently large.

Expanding on that: If you have a domain (the set you map into), that cannot be trivially converted from a bit-string (like integers) or where membership criteria or non-trivial, you can build a deterministic hash function, that will increase a counter each time the result is not an element. For $\mathbb Z_n^*$ for example this would be $\gcd(r,n)=1$ for membership (given that $r$ is your hash output).

Expanding this approach to arbitrary input sets is straightforward. You basically just convert the set-element in question into a its bit-representation (which you'll have anyways in all practical applications) and then hash this as describe above.

The multi-argument case is a little more interesting. You use the prefix-free pairing function of your choice to combine the bit representation into a large binary string. If all but one of your inputs are fixed-length, simple concatenation will do here. Otherwise you may be able to construct collisions by appropriately choosing the inputs, for example (01,1) and (0,11) would result in the same string after concatenation, yielding an undesirable collision. Another possible construction for this would be to pre-hash each argument independently and concatenating the (fixed-length) outputs for final hashing.


Which is the fastest way to find a member of a subgroup with known size modulo prime $P$, with know factorization of $P-1$?->$x$ with $x^s \mod P = 1$

Is that the best/fastest way to go?

Well, unless you give some criteria, whether it's the best is unanswerable.  However, it might not be the fastest; you could just note that $k = f_2 \cdot f_3 \cdot … \cdot f_i$ and skip the baby-step-giant-step algorithm entirely.

In addition, if all you want is a random element of the subgroup, you don't need to find a generator.  Instead, all you need to do is select a random value $r \in [1, P-1]$, and compute $x = r^k \bmod P$ (using the above definition of $k$); if $x \ne 1$ (true with probability $1 - 1/s$), that's what you're looking for.

BTW: why do you think you need $x$ to be a prime?


How do I construct variable length input (VIL) in a block cipher mode?

In the document Five Confidentiality Modes, in section 5.2 it says:

  For the ECB and CBC modes, the total number of bits in the plaintext
  must be a multiple of the  block size, $b$; in other words, for some
  positive integer $n$, the total number of bits in the plaintext  must be
  $nb$

...

  For the CFB mode, the total number of bits in the plaintext must be a
  multiple of a parameter,  denoted $s$, that does not exceed the block
  size; in other words, for some positive integer $n$, the  total number
  of bits in the message must be $ns$

...

  For the OFB and CTR modes, the plaintext need not be a multiple of the
  block size. Let $n$ and $u$  denote the unique pair of positive integers
  such that the total number of bits in the message is  $(n-1)b+u$, where
  $1≤ u≤ b$.

So we can see that for three of the five confidentiality modes, ECB, CBC and CFB respectively, some sort of plaintext padding scheme is called for. But for two of five modes, OFB and CTR respectively, no such padding scheme is needed. However you still operate on 128 bit blocks of data in these modes.

In OFB and CTR modes, if you have a single message that is shorter than the block size, you still encrypt 128 bit blocks of data, but you may not use all 128 bits since you are XORing your plaintext with the cipher output, so you only end up with the number of bits in your smaller message.

See Message lengths with AES CTR mode?


RSA public key exponent generation confusion

Usually the public exponent is first chosen. Often it is the fifth prime of Fermat (e.g. -f4 for openssl), 65537. It's the fifth number as the index starts with 0.

This number in binary is:

0000 0000 0000 0000 0001 0000 0000 0000 0001

Fermat primes are primes with just 2 bits set. 3, 5, 17, 257 and 65537 are the only known Fermat primes. Because only two bits are set the exponentiation is relatively fast compared to other exponents.

After the choice of public exponent the primes $p$ and $q$ are chosen in such a way that they comply with the chosen public key. To be precise, this means that $p - 1$ and $q - 1$ need to be relative prime to $e$. This is slightly different than most text book methods of generating an RSA key pair where $p$ and $q$ are chosen first.

Smaller and much larger exponents may be vulnerable to some kind of attacks. Usually other properties for which the keys are used - mainly padding - cause these attacks to be impossible. Cryptographers and standardization institutes however like to play it safe, so current implementations almost unanimously choose the fourth prime of Fermat as public exponent.

Choosing a high valued public exponent will hurt performance because higher values will take more time during the modular exponentiation used for encryption and verification. In the worst case the exponentiation is as slow or even slower than the private key operation. If $e$ is randomized then it is usually 16, 32 or 64 bit value at most (e.g. original implementations of PGP). Some implementations (.NET) only accept small public exponents.


Discrete logarithm modulo a smooth number

Does the factorization of N somehow help me?

It sure does.

  I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it.

You're real close; you do recombine them using the Chinese Remainder Theorem; however the modulus you use aren't the prime factors, but one less (unless a prime factor is repeated; that gets handled slightly differently).

I suspect the easiest way to explain this might be to write up an example; suppose we have $N = p\cdot q\cdot r$, where $p$, $q$ and $r$ are the distinct prime factors, and we want to solve:

$$a = b^x \pmod{N}$$

So, what we do is to find the three values $y$, $z$ and $w$ with:

$$a = b^y \pmod{p}$$
$$a = b^z \pmod{q}$$
$$a = b^w \pmod{r}$$

and then use the CRT to find the $x$ with:

$$x = y \pmod{p-1}$$
$$x = z \pmod{q-1}$$
$$x = w \pmod{r-1}$$

We do it modulo $p-1$, and not modulo $p$, because $p-1$ is the order of the group $Z^*_p$

Note that there might not be any such $x$ (because $p-1$, $q-1$ and $r-1$ are not relatively prime); if that is the case, then original equation is unsolvable.

If there is a repeated factor (for sample, $p^k$ is a factor of $N$), you do the same, however when you use the CRT, you do that one modulo $p^{k-1}(p-1)$


In RSA, how does the CPU deal with this huge modulus (8192 bits)?

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic.  The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school.

The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, from "0" to "9", where each digit alone represents a different small number below 10, and where placing a digit to the left of another digit multiplies its value by 10.

Assuming you didn't totally sleep through grade school, you probably remember having to memorize the addition and multiplication tables for single-digit numbers: 1 + 1 = 2, 7 + 7 = 14, 6 × 4 = 24, and so on.  Those are the basic "atomic" operations for base-10 arithmetic, and once you know how to do them, you can combine them to calculate things with larger numbers.

(You don't have to have the basic operations all perfectly memorized, of course; if you, say, forget what 7 × 6 is, but still remember that 6 × 6 = 36, you can just count six more numbers up from that to end up at 42.  And even if you were to forget what e.g. 7 + 7 is, you could, say, count on your fingers to arrive at 14.  It just turns out that, for us humans, memorizing those basic single-digit operations — i.e. implementing them with the human equivalent of a look-up table — makes arithmetic a lot faster than working them out from first principles every time.  For computers, the tradeoff may be different.)

For example, depending on how math was taught at your school, you may remember writing down an addition problem on paper something like this:

Exercise: 12345 + 67890 = ______

             <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
             <-- result

and the working it out digit by digit, from right to left.  Here, you'd start with 5 + 0 = 5 (with no carry):

       0     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
        5    <-- result

and then proceed to 4 + 9 = 13 (i.e. write down 3, carry 1):

      10     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
       35    <-- result

and then 1 + 3 + 8 = 4 + 8 = 12 (i.e. write down 2, carry 1), and so on all the way to:

    1110     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
    80235    <-- result

You may have also learned similar pencil-and-paper algorithms for other elementary arithmetic operations, like subtraction, multiplication and even long division (which can also be used for modular reduction).  The important thing to realize is that all these calculation methods are based on rules for manipulating strings of digits, and on simple arithmetic operations on single digits.  As long as you can do the basic single-digit operations, and know the algorithm for combining them together, you can do arithmetic on paper with numbers as large as you want (or need) to!

So how do computers do it, then?  They could of course use exactly the same decimal arithmetic rules as we do, but that would be pretty inefficient.  A typical CPU already has fast circuitry to add or multiply together any two 32 or 64 bit (and possibly even larger) numbers with a single machine code instruction, so it makes a lot more sense to treat 32 or 64 bit arithmetic as the basic building block.

Thus, a typical computer implementation of bignum arithmetic effectively works with "digits" that are 32 or 64 bit integers, and represents larger numbers as strings of those smaller integers.  The algorithms used are very similar to those we'd use for pencil-and-paper calculation, except that instead of base 10, a computer is far more likely to use base 232 or 264.

For example, let's calculate the sum of two random 128-bit numbers (written in hexadecimal for convenience):

Exercise: 3d96d3e9d019665051ecf94e4c0c697b +
          a80314053a779df7464ea2feebf771be = ______

A modern CPU might be able to calculate that directly, but let's assume that we only have a 32-bit CPU available.  Fortunately, we can break up our numbers into 32-bit chunks and use the same addition algorithm we used before:

                                         <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                                         <-- result

So first, we need to calculate 4c0c697b + ebf771be, which our CPU easily tells us is 13803db39 (i.e. 32-bit result 3803db39, plus carry 1):

                             1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                               3803db39  <-- result

Next we ask our CPU to calculate 51ecf94e + 464ea2fe, and to increment the result by one because of the carry, which yields 983b9c4d (and no carry for the next position):

                    0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                      983b9c4d 3803db39  <-- result

We can then proceed with the remaining two 32-bit additions in the same way, getting d0196650 + 3a779df7 = 10a910447 (i.e. 0a910447 and carry 1) and 3d96d3e9 + a8031405 + 1 = e599e7ef:

  0        1        0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
    e599e7ef 0a910447 983b9c4d 3803db39  <-- result

And there we have our result!

I used addition for this simple example, but similar algorithms can be used for other arithmetic operations, including exponentiation and modular reduction (which one would normally combine into a single modular exponentiation algorithm, since it's much more efficient to do them together rather that to first exponentiate and then reduce).

Also note that the arithmetic algorithms used for cryptography tend to be somewhat specialized, since in crypto it's often important to avoid timing attacks and other types of side-channel attacks by making sure that the algorithm takes the same amount of time to run (and consumes roughly the same amount of power, etc.) regardless of what the numbers being added (or multiplied or raised to a power, etc.) are.


Prove that you have the data when hash is public

It's indeed a genuine concern.

How to fight this?

Well, once client had provided the SHA256 hash of the file (to quickly index the file on the server), your server then provide a random one-time key and ask the client to hash the file again with HMAC and the key. Since the key is one-time and random, adversaries have little chance at guessing the key and forging a MAC tag of a file that they only knows the hash of.

It wouldn't be safer to make HMAC key public, as it's equivalent to regular hashing with custom initialization vector.

== Some side notes ==
Browsers nowadays have WebCrypto APIs, which provide the functionalities of hashing and HMAC, but using them in a web page requires the secure HTTPS connection. Also, these APIs don't work on File/Blobs, they work on ArrayBuffers, which for large files could be memory intensive.


CAPTCHA like mechanisms : Impact on confidentiality of Info

What kind of 'confidentiality' are we looking with such mechanisms? Simply put we have a text which is confidential to a machine. There is no key exchange involved.

I'd put this down as a kind of obfuscation for machines. That is, unless you take all the knowledge of the world as key.

  Are their any tangible gains in using such a method and then enciphering the text through a deterministic crypto function (RSA, DES, etc.)

No, because you first would have to establish trust for a public key or share an (authenticated) secret. Besides that, it is unclear what this would defend against.

Using TLS could be beneficial, although not strictly necessary. The attack vectors probably do not include man in the middle or even eavesdropping. Basically it's just a challenge response protocol. I could see how eavesdropping lots of challenges/responses could make it possible to build up a table though.

  Any references in this regards?

Nope, sorry.


How will be cipher selected when client is running on version TLS 1.3 and server is running on TLS 1.2?

If the client is only supporting TLS 1.3  or only TLS 1.3 ciphers the SSL handshake will fail. Otherwise the cipher will be selected as it is usually done with TLS 1.2: the client shows which ciphers it supports in the ClientHello and the server will pick the one which a) is supported by the server and b) fits the type of certificate of the server (i.e. authentication RSA or ECDSA). If there is no common cipher the handshake will fail.


security parameter in lattice cryptography

A similar question could be asked about RSA --- why use 2048-bit RSA, and not 80-bit RSA?

The answer of course is due to cryptanalytic estimates. In particular, one estimates how difficult the underlying problem is (for factoring, it's roughly $\exp(O(\sqrt[3]{n}))$, and then sets the security parameter such that it takes $\approx 2^{80}$ bit operations to break.

For LWE-based schemes, Albrecht et al. have created the LWE-estimator. This is both a summary of state-of-the-art (at the time, in 2015) attacks on lattice schemes, along with a Sage module (which has been updated since then) that allows you to plug in the parameters of your scheme, and it will estimate the concrete security level.

These estimates are of course just estimates, and its an active area of research to try to get better estimates of the concrete security of lattice-based cryptography. But parameters themselves are chosen such that, when state of the art attacks are applied, it takes $2^{80}$ (or $2^{100}$ or $2^{112}$) bit operations to break the scheme.


if I already know what large portions of the encrypted text says when decrypted (..can it be used..) to decrypt the file?

No, beyond validating a candidate key. With modern ciphers, knowing large portions of the plaintext does not help decipher the rest. They are designed to be immune to Known Plaintext Attack, and even to Choosen Plaintext Attack. And as far as we know, AES-128 in CBC mode (as prescribed in the XML encryption standard) achieves that goal well.


IEEE P1619/XTS, inconsistent reference implementation and test vectors

From §5.1 ‘Data units and tweaks’, p. 4:

  Each data unit is assigned a tweak value which is a non-negative integer. The tweak values are assigned consecutively, starting from an arbitrary non-negative integer.  When encrypting tweak value using AES, the tweak is first converted into a little-endian byte array.  For example, tweak value 123456789A16 corresponds to byte array 9a16, 7816, 5616, 3416, 1216.

The test vectors appear to be written as byte arrays, not as integers (which in English are written big-endian), so where it says

  Data unit sequence number 9a78563412

on p. 23, that presumably means the integer 0x123456789a, i.e. 78187493530 in decimal.


Sure they can, it's called the socialist millionaires problem. The most common solution is to use Yao's protocol: Alice sends a garbled circuit of the equality function to Bob, and then Alice use oblivious transfers to send the keys necessary for the evaluation of the circuit to Bob. Another option is to rely on additively homomorphic IND-CPA encryption: Alice sends an encryption $E(a)$ of her input $a$, Bob computes $E(r\cdot (a-b))$ from this ciphertext, using his input $b$ and a uniformly random value (over the plaintext space of the scheme) $r$. Alice decrypts and outputs yes if the result is 0, and no otherwise. As the scheme is IND-CPA, Bob learns nothing on Alice's input (the protocol is therefore computationally private for Alice); because of the random coin $r$, the decrypted value statistically masks $b$ when $a \neq b$ (the protocol is therefore statistically private for Bob).


Why does lattice KEX not require sampling with high precision?

The way and the purpose in which gaussians are used in key exchange and digital signatures is completely different.

In public key encryption (and key exchange), we need computational-indistinguishablilty of (A,As+e) when A is a random matrix (over some ring) and (s,e) are vectors over that same ring with small coefficients.  To get the tightest security reduction based on worst-case hard problems, s and e should be gaussian, and this is why it is sometimes (falsely) believed that s and e should be gaussians for security.  In reality, they don't need to be -- the distinguishability problem seems to be just as hard in practice when s and e are "simpler-to-sample" distributions such as uniform or binomial.

In digital signatures (using the Fiat-Shamir transform), the signature is computed as z=Sc+y, where S is a secret matrix of small coefficients, c is a challenge vector (with very small coefficients) and y is some vector that is chosen during signing.  For security, one needs that z has small coefficients and is independent of the secret key S.  For z to have small coefficients, y needs to have small coefficients.  In order for z to be independent of S, we need to use rejection sampling so that the distribution of y "masks" the shift by Sc.  If we don't use high-enough precision here, then we may not get the distribution of z that is statistically independent of S, which will be disastrous for security.

In some recent papers, it was shown that the way to get the shortest possible z requires taking y to be a discrete gaussian, and so you need to be able to sample discrete gaussians with a high precision.  It should be mentioned that you can also create digital signatures by simply using the uniform distribution, but thy will be slightly longer.

For hash-and-sign signatures, it's again the same high-level idea as for Fiat-Shamir ones.   You want to make sure that the signature is independent of the secret key. The most efficient way we know how to create such signatures is to have them come from the discrete gaussian distribution.


Break RSA given $N, e$ and lower half of $d$

If $e$ is small, and if you have $n/4$ least significant bits of $d$, then you can factorize $N$. The attack runs in time polynomial in $e, n$. You can have a look at Boneh Durfee Frankel attack Section 3. So, if $e$ is only 65537, then the attack is certainly feasible.


Is the openssl implementation of ECDH missing something?

There are two reasons:

Reason one is that the ECDH shared secret is not equidistributed; not all values are possible.  In particular, and $x$ that is not a possible solution to the elliptic curve equation cannot happen at all.

Things that use the shared secret (such as AES) are generally assumed to have uniform keys; that is, all keys are possible (and are equiprobable); this isn't possible when using the ECDH shared secret directly.

In practice, it probably doesn't matter; it's hard to conceive of an attack that becomes practical because half of the possible $x$ coordinates are impossible.

Reason two is that not all bits of the ECDH shared secret are actually independent.  If the part of the shared secret bits start going into the $y$ coordinate, then if the attacker somehow gets the $x$ coordinate bits, he gets the $y$ coordinate bits for free (well, one of two possibilities).

We try to avoid revealing some of the bits of the key; however having some bits imply others isn't what we want.  A proper KDF (key derivation function) avoids this possibility.

Note: reason two doesn't apply to all elliptic curves; for example, with Curve25519, we don't explicitly compute the $y$ value, hence that's not available as part of the shared secret.  However, it is present for other curves.


The 9 lives of Bleichenbacher's CAT, it puts another scratch again

How does the new attack work at top level?

In short

They used BEAST-like Man in the Browser attack by using Cache-like attacks to perform a downgrade attack against any TLS connection to a vulnerable server. With this, they showed the feasibility of using  Cache-like attacks.

More detailed

Even over the years, numerous mitigation techniques are deployed against the padding oracle attacks, they showed that some implementations are still vulnerable to various microarchitectural side channels. They target PKCS #1 v1.5 implementations that leak information via microarchitectural side channels.

Their attacker requires 3 capabilities:

Side channel capability: attacker must be able to execute code on the victim machine to mount microarchitectural side channel attack. They used Flush+Reload attack.
Privileged Network Position Capability: The attacker must be in the man-in-the middle position so that padding oracle attack with the private key can be exploited. The attacker downgrades the communication to TLS 1.2 RSA key exchange with Jager et. al.'s attack and used BEAST method.
Decryption Capability: The attacker needs an ability to start decryption of ciphertext chosen by him on the target system. They utilized Bleichenbacher and Manger’s Attack attack.

A concrete scenario of the attack:

A physical device shared between a TLS server and the attacker's virtual machine. This requires a determined adversary.
Second and third can be achieved by the controlling a node between the server and client

Note: Manger’s Attack that requires $\log_2(N)$ perfect Oracle queries. Bleichenbacher's attack requires millions of Oracle calls but can tolerate false negatives. They mounted an improved Manger’s Attack's attack with only 6144 queries due to an error.

Although the timeout of the browser limits the attack, they were able to parallelize the attack by using TLS servers that share the same public key certificate.

  Which TLS implementations are affected?

They tested the following implementations:

OpenSSL
Amazon s2n
MbedTLS
Apple CoreTLS
Mozilla NSS
WolfSSL
GnuTLS
BearSSL
BoringSSL

All, except the BearSSL and BoringSSL are affected by their attack.

  How one can mitigate from the attack?

Keep the system up-to-date: don't support different versions.
The backward compatibility is the main issue of this attack. TLS 1.3 security doesn't help you if your server can be downgraded to an earlier version.
Deprecate the RSA key-exchange.
Certificate Separation: Don't use the same key for signing and RSA-key exchange.
Constant-Time Code and Safe API as in BearSLL and BoringSSL API.
Using Large RSA Keys. The attack requires $\approx \log N$ oracle calls. Use larger keys $>2048$-bits to make the attack less practical.
Reduce the TLS Handshake Timeouts in order to make MitM attack harder.
Use BearSSL or BoringSSL

Note: The 30-second timeout in Firefox can be extended see Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. by Adrian et. al.

Note 2: There is a related question in SecuirtySO about effected cipher suites.


Open-source usb TRNG and US standards - Help choosing

If you fish around in your pocket, you can probably find one that costs 0.25 USD.

All it takes to use one of these gizmos is a little patience, a bit of hand-eye coordination, and some confidence that there aren't any surveillance cameras watching you, which you need anyway because you just typed in your password under them to decrypt your laptop's disk.

Once you've warmed it up by flipping it 256 times—or 512 times, just to be on the paranoid side, in case the entropy is ever so slightly below 1 bit per flip—you can get gigabits per second by using the outcome as the seed for an AES-CTR or ChaCha stream.

(You could even drive the cost down to 0.01 USD if you have the extra dexterity, but when the 0.25 USD option will still leave room in your budget for three or four nice dinners including booze, I figure the extra trouble of flipping a penny instead of a quarter isn't worth the 0.24 USD.)


What is the point of hash = (prime * hash + b) % 100

Distributing objects among buckets of a hash map

This looks like an (old) textbook algorithm for allocating elements in a hash map or hash table. Other than the last line, which doesn't really make sense, it would be used calculate which hash map 'bucket' to use for putting/getting this item, as you need to calculate a simple, cheap and fast (so, generally not a cryptographic hash, but a few multiplications) code that would be an integer in the range from 0 to length of the map backing array (probably 100 in this case) that preferably is different for nonidentical similar objects to reduce the number of collisions.

A textbook example from Algorithms 4th ed by Sedgewick&Wayne, the similarity should be obvious:

int hash = 0;
for (int i = 0; i < s.length(); i++)
    hash = (R * hash + s.charAt(i)) % M;

This has nothing to do with cryptography, though. Nowadays many standard libraries try to use a cryptographically unpredictable algorithm for hashmap hashes to prevent a risk of DoS attacks by data engineered to induce worst case performance, but this example is not one of these.


KeeLoq showing that decryption is indeed the inverse of encryption?

It is difficult to find a complete specification, so I'm going by the Wikipedia article you linked.

These images (public domain, from Wikipedia) describe one round of the encryption/decryption algorithm, with 528 rounds in total. At the start, the plaintext is put into the 32-bit shift register, and at the end the ciphertext is taken out of it (for decryption, the other way around).

In each round, actually only one bit of data is actually changed (the new bit with number 31 for encryption, 0 for decryption), the other bits are only shifted around.

If we number all the bits in the "data queue" over time by $L_0 \dots L_{559}$, with
bit $j$ before round $i$ being $L_{i+j}$, $L_{i+32}$ is the new bit 31 after round $i$, and we can describe the encryption algorithm as follows (from the text to Figure 1 (page 9) in Periodic ciphers with small blocks and cryptanalysis of KeeLoq, which features a similar image):

  Initialize with the plaintext: $L_{31}, \dots, L_0 := P_{31}, \ldots, P_0$.
  For $i = 0, \ldots, 528 − 1$ do
  $$L_{i+32} := k_{i\ \bmod\ 64} ⊕ L_i ⊕ L_{i+16} ⊕ NLF(L_{i+31}, L_{i+26}, L_{i+20}, L_{i+9} , L_{i+1})$$
  The ciphertext is $C_{31}, \ldots, C_0 := L_{528+31}, \ldots, L_{528} $

The decryption is similar, but here we number the rounds from 528 to 1, and the bits over time as bit $j$ before round $i$ is $L_{i+j}$. $L_{i-1}$ is the output of round $i$.

  Initialize with the ciphertext: $L_{528+31}, \dots, L_{528} := P_{31}, \ldots, P_0$.
  For $i = 528, \ldots, 1$ do
  $$L_{i-1} := k_{i-1\ \bmod\ 64} ⊕ L_{i+31} ⊕ L_{i+15} ⊕ NLF(L_{i+30}, L_{i+25}, L_{i+19}, L_{i+8} , L_{i+0})$$
  The plaintext is $P_{31}, \ldots, P_0 := L_{31}, \ldots, L_{0} $

Now all that stays to show is that both equations
$$L_{i-1} = k_{i-1\ \bmod\ 64} ⊕ L_{i+31} ⊕ L_{i+15} ⊕ NLF(L_{i+30}, L_{i+25}, L_{i+19}, L_{i+8} , L_{i+0})$$
and
 $$L_{i+32} = k_{i\ \bmod\ 64} ⊕ L_i ⊕ L_{i+16} ⊕ NLF(L_{i+31}, L_{i+26}, L_{i+20}, L_{i+9} , L_{i+1})$$
are indeed equivalent. (This is a simple index-shift, and reordering some terms.)


Does secp256k1 have any known weaknesses?

secp256k1 fails the following SafeCurves criteria, but it doesn't matter for Bitcoin's use of secp256k1:

CM field discriminant.
secp256k1 is a Koblitz curve that admits a fast endomorphism for speeding up scalar multiplications.  There is no particular vulnerability here: the same speedup you get in computing with secp256k1, an adversary gets in trying to break it, but that won't, in itself, render an infeasible attack feasible.  (This is what the ‘few bits weaker security’ refers to.)

SafeCurves conservatively rejects this because it is an additional structure that could be the foundation of future breakthroughs in cryptanalysis, but nobody has made that breakthrough and we have little reason to suspect it's going to happen sooner than any other unpredictable cryptanalytic breakthroughs.
Ladders.
secp256k1 does not admit the fast Montgomery ladder to compute $x$-restricted scalar multiplication in constant time; it does admit the much slower Brier–Joye ladder.

Of course, you can compute fast scalar multiplication in variable time, which exposes you to timing side-channel attacks.  This creates a conflict between fast implementations—everyone notices when things run slowly—and secure implementations—which nobody notices until their money is gone.  The SafeCurves criteria reject such conflicts that encourage performance or security, in favor of designs that encourage performance and security.

This is relevant mainly for applications doing Diffie–Hellman, but Bitcoin itself does not use secp256k1 for Diffie–Hellman, though Lightning does; Bitcoin itself uses secp256k1 only for ECDSA signatures.  (Conceivably, it would also be relevant for applications using exotic signature schemes like qDSA, but Bitcoin is not one of those.)
Completeness.
secp256k1 does not admit the fast complete Edwards formulas to compute elliptic curve addition in constant time; it does admit the much slower complete Weierstrass formulas to compute elliptic curve addition in constant time.

Of course, you can compute fast incomplete addition in variable time with conditionals, which exposes you to timing side-channel attacks; or you could compute fast incomplete addition in constant time with carefully chosen arithmetic that has the same effect as conditionals, which takes more effort to design and audit.  This creates a conflict between fast implementations, secure implementations, and easy implementations, which SafeCurves criteria avoid.

Fortunately, it seems that pretty much everyone who matters in the cryptocurrency world has recognized that this particular kind of security (as opposed to, e.g., economic security from equitable wealth distribution) is important, and now uses libsecp256k1 to very carefully compute secp256k1 curve arithmetic in constant time at a reasonable speed. So this poses more of a danger for the victims of novice implementors in novel scams; as long as you use libsecp256k1 and don't try to rewrite it at home, this doesn't pose a security problem.


why do we take computational distinguishability over ensembles

Why not just define it over two distributions $X$ and $Y$?

Because this is an asymptotic definition (using a negligible function explicitly).
If you were to only consider two fixed distributions, there would be no scaling with the security parameter (and thus the involved lengths) possible. This is why we use ensembles, parametrized by the value of the security parameter $n$.


MySQL/MariaDB AES_ENCRYPT() - ECB mode, IV, Padding Oracle Attack Question

No
No
If the attacker doesn't steal the key, they can't create their own padding oracle.
As long as the key is not stolen, no mitigation is required.

Your threat model for "someone [having] stolen the database contents" seems very weak: if you make a query containing the decryption key, the key bytes themselves will likely persist in memory long after the query has been executed. See this recent paper for a discussion of realistic threat models for database compromise. (Full disclosure: I am a co-author of the paper.)


PQ Key Exchange based on Elliptic Curve Isogenies

The Supersingular Elliptic Curve Isogeny Key Exchange that you refer to was first published in 2011 by DeFeo, Jao, and Plut.  It builds on but is quite distinct from earlier work by Rostovetsev and Stolbunov in 2006.  As a Post Quantum/Quantum Safe replacement for Elliptic Curve Diffie-Hellman (ECDH) it has several good properties:

The number of bits that need to be exchanged over the communications channel is roughly the same as a normal Diffie-Hellman key exchange.  Not as small as an ECDH but not nearly as large as in other Post Quantum schemes like McEliece or NTRU.
It uses the very well studied mathematics of elliptic curves rather than the more recently accepted lattice approaches to secure cryptography.  If you look in the literature you will see that lattice cryptography has been prone to insecurity in the past.
It offers forward secrecy, just like Diffie-Hellman and ECDH.  McEliece and NTRU need to add an additional exchange to provide forward secrecy.
It uses elliptic curve arithmetic in a finite field which has been widely implementd.
Most importantly, it has withstood 4 years of academic analysis.  Two notable papers which are relevant to the security of this key exchange are:

Computing Isogenies between Supersingular Elliptic Curves over Fp by Delfs and Galbraith
    http://arxiv.org/pdf/1310.7789v1.pdf

A Quantum Algorithm for Computing Isogenies between Supersingular Elliptic Curves by Biasse, Jao and Sankar
    http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

Both papers support the basic security of the Supersingular Isogeny Key exchange though it should be noted that one of the authors (Jao) is also one of the inventors of the key exchange.

There seem to be no patents on the key exchange.

However there is a shortcoming:

Computing Isogenies of Supersingular Elliptic curves and composing these isogenies is computationally harder than other post quantum schemes being considered like McEliece, NTRU, or the Ring-LWE schemes.

In the paper which presented the key exchange, the authors present algorithms which require over 100ms of computation on a 2.5GHz computer for each side of the exchange. Half of that can be done offline but it is worth noting.  There has been further work by Shumow and Shumow and Moody on creating more efficient computational models.  Both the original inventors of the key exchange and Shumow have posted their code online.  It is a good bet that if people became more interested in actually using this key exchange, there could be some significant improvements in computation like Dan Bernstein and Tanja Lange have done for standard Elliptic curve cryptography.  A coding contest for the fastest Elliptic Curve Isogeny computations for 768-bit supersingular curves would be an good way to test the performance limits.

Does that answer your question?


Decrypting without using the private key

If $(G,q)$ are public authentic parameters and Alice publishes $(h,R,S)$, then if Alice later publishes $r$, Bob needs to check if $g^r=R$, which fixes $r$. Consequently, when computing $\log_g S/h^r$ also fixes $h$ and the exponent of $S$ is fixed. Changing $m$ to $m'$ would require to solve $m+rx\equiv m'+r'x \pmod{q}$ for $r'$. However, since $r$ is fixed in $R$, this does not work out without changing $R$ to $R'\neq R$ and same argument for $x$ which would change $h$ to $h'\neq h$ (but this can be detected).

But why should Alice not give $(r,m)$ to Bob and Bob runs $Enc(m,h,r)$ again and checking whether the computed result matches $(R,S)$ previously published by Alice? This would also be more efficient as you avoid computing $\log_g S/h^r$.


RC4 seems to be an option in the SSH1 and SSH2 protocols, so yes, it is still in use as cipher. AES seems to be preferred in most configurations, but "arcfour" is still often used as fallback.

WPA and WPA2 may also use RC4 instead of AES, using TKIP. Again, this protocol was introduced to replace the broken WEP protocol while still relying on the faster RC4 protocol. So it's still often used as fallback in case WPA2 with AES is unavailable, e.g. on older hardware without hardware AES support.


In general, unless the OWP also happens to be a trapdoor permutation, there is no way to efficiently evaluate the inverse. So, no.


Can a digital signature scheme also be an encryption scheme?

In that case, could you say that a signature scheme and an encryption scheme represent the same thing?

I don't see how.  With a signature scheme, the public operation can return just a single bit (either "the signature verified" or "it didn't").  It's not at all clear how you could efficiently use a function that returns a single bit as a part of an encryption operation.

Now, there are certainly cryptographical primitives - such as modular exponentiation within RSA - that can be used as a primitive within either a public key encryption or a signature scheme; however there are also signature schemes that cannot be used to do encryption, and so generically, the two classes of schemes cannot be identical.


Why is SubtleCrypto API generating different signature for same data?

Now the problem I am facing is the signature produced by the API is
  different for the same private key and data, which should never be the
  case.

Actually in cryptography we don't require our signature schemes to be deterministic. It can even be harmful if you consider things like fault attacks (example attack PDF). Additionally you are using ECDSA which has only "recently" seen a deterministic variant in RFC 6979 and for which most standards (still?) mandate the non-deterministic variant (eg FIPS 186).

Additionally more often than not if you want to do something with deterministic signatures you are looking for a different primitive and probably should describe the problem and not the problem of "the" fix.

If you really don't want a deterministic signature scheme supported by the API you linked to, you can use RSASSA-PKCS1-v1_5 which is an older, still secure deterministic RSA-based signature scheme.


Is it true the longer the key length is the more secure the encryption?

No. Key length does put an upper bound on security, because it determines the complexity of brute force iteration of the key space or factoring, discrete log, etc. for some asymmetric algorithms. However, once you have a long enough key to make brute force attacks impossible, there is no benefit to a longer key alone, you must have a stronger algorithm in general (e.g. more rounds, larger state or block size) to benefit.

For some asymmetric systems, like RSA, it may seem that you can just increase the numbers and call it a day. However, RSA security rests on the encryption and signature algorithms which probably use symmetric encryption and hash functions that have a constant security, limiting that of the whole algorithm.

As a practical example, RC4 allows up to 2048-bit keys but has biases in the initial keystream no matter which size you use. Meanwhile, many ciphers with 128-bit keys are thought to be secure, like AES-128 or HC-128.

  what stopping us from using a very lengthy key?

Diminishing returns, performance costs and increasing complexity.

The effect of key length on performance is most readily apparent in something like RSA, where modular exponentiation takes about $O(n^{k})$ time for $n$-bit numbers ($k > 2$ depends on the algorithm). Longer keys usually mean longer key schedules, which may be more difficult to analyze, require more constants and code, etc. adding to complexity.


How is QKD (Quantum Key Distribution) advantageous over McEliece/AES?

Because it's the Holy Grail of cryptography.
To be specific, it's not unbreakable as the layman's literature suggests. It's that a quantum transmission of key material cannot be intercepted without the sending/receiving parties noticing. It is the Observer Effect in physics and a fundamental part of the Universes. Knowing that you're being spied upon in many ways gives you the advantage.
And if you can securely transmit a lot of key material, you can then use one time pad (OTP) techniques for the encryption.  And OTPs are provably secure via information theory. McEliece/AES being limited key length based ciphers are not.  Just because the academic community can't break McEliece or AES, doesn't mean that they haven't already been by state actors, or will be tomorrow by Alexander Verykleverkov in his university dorm room. Perhaps Shor's 3rd improved algorithm might work against McEliece. The point I'm labouring is that you can prove photon interception/OTP security now, but not McEliece/AES. All we have is an absence of evidence for them.

The only reason I can discern is that there is some possibility that a yet-to-be-discovered algorithm may weaken McEliece or AES.

You've answered your own question :-)  Israel can keep defence-related documents sealed for 70 years.  The UK had 50. Their transmission may have been intercepted or copied and stored. You cannot guarantee that they won't be teaching McEliece/AES breaking in high schools by 2091.
That's why there is a market for QKDNs. See all the interest in this older answer, and ponder the quotation at it's end. It's incredibly alluring, and if you want one, buy one of these:-

It's a node for commercial QKDNs. Cerberis from ID Quantique.


Is it possible to derive a public key from another public key without knowing a private key (Ed25519)?

Yes! You can use the ephemeral key derivation mechanism that is for example used in Monero (they call it stealth keys there).

Consider public key $A=aG$, with private key $a$. Then, a derived key can be generated, parametrised by the random scalar $r$:

$$A'=H_s(rA)G+A$$

and the party that knows $a$ can use the public parameter $R=rG$ to compute their ephemeral private key $a'=H_s(aR)+a$. You can for example store $R$ with your signature.

Note 1: We add $A$ resp. $a$ to the public resp. private key to ensure that the party that derives a key cannot compute the private key.

Note 2: This derivation is basically a Diffie-Hellman key exchange with a random ephemeral key $R$.

Note 3: $R$ can also be used to "check" whether the user has access to this specific key. He just needs to check whether $A'=H_s(aR)+A$ holds.


The MD construction uses a compression function $C$ ($F$ in the figures) such that it has two inputs.
$$h_i = C(h_{i-1},m_i)$$

and the first $h_{-1} = IV$ and the last $H = h_{2^k-1}$ is the hash  value.

The compression function can use a block cipher, where the message to the block cipher is the previous hash value and the key is the message. $h_i = E_{m}(h_{i-1})$
The first description of using a block cipher for compression function exists in Merkle's thesis on page 11. This construction is totally insecure since the existent block cipher directly chained and it can be shown that it has $\mathcal{O}(2^{n/2})$ second-preimage resistance instead of $\mathcal{O}(2^{n})$.
We don't want related key attacks as exist in some of the block-ciphers like AES and DES. This doesn't create a problem for encryption since the keys are chosen uniform randomly, however, the related keys can be used to attack the hash function. This is discussed extensively by Mannik and Preenel
We want large inputs due to the collision attacks on the compression functions [1] and therefore more rounds to process. So designers create a new block cipher for MD constructions instead of using existing ones. For SHA-1 it is called SHACAL and for SHA-2 it is called SHACAL-2.
The dividing value depends on the compression function, MD5, SHA-1, and SHA256 uses 512-bit message blocks, SHA512 is using 1024-bit message blocks. The messages are padded to be multiple of the block size with the message size is encoded at the end.
For example SHA-512 padding on NIST FIPS 180-4

Suppose that the length of the message, $M$, is $\ell$
bits.  Append the bit 1 to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation
$$\ell + 1 + k \equiv  896 \bmod 1024$$ Then append the 128-bit block that is equal to the number $\ell$ expressed using a binary representation

Formalize for arbitrary block size $b$ and $d$-bit encoded message size ( 64 for SHA-1 and SHA256, 128 for SHA512.
$$\ell + 1 + k \equiv  b-d \bmod b$$
So the design criteria are having a block cipher with many rounds, SHACAL has 80, SHA-256 has 64, and SHA512 has 80 rounds while keeping the round function simple.
And the block cipher is used as Davies–Meyer to create a one-way compression function.
For example, the math for SHA256 is

$\operatorname{Ch}(E,F,G) = (E \land F) \oplus (\neg E \land G)$
$\operatorname{Ma}(A,B,C) = (A \land B) \oplus (A \land C) \oplus (B \land C)$
$\Sigma_0(A) = (A\!\ggg\!2) \oplus (A\!\ggg\!13) \oplus (A\!\ggg\!22)$
$\Sigma_1(E) = (E\!\ggg\!6) \oplus (E\!\ggg\!11) \oplus (E\!\ggg\!25)$

The bitwise rotation uses different constants for SHA-512. The given numbers are for SHA-256.
The red $\boxplus$ mean $ c = a + b \mod 2^{32}$, i.e. modulo addition.
As we can see, simple operations that CPUs can handle, light round function, with a little degraded unbalanced Feistel structure.
And we learned from the Tiny Encryption algorithm that, even simple rounds can be secure after 32 rounds.


What encryption types are illegal in the U.S.A

Effectively none.  Some ciphers are patented so you won't find them in OpenSSL.

In 1995 Bill Clinton signed an Executive Order 13026 that transferred control of encryption from the department in charge of munitions export to the commerce department.  Since then there has been a period of liberalization where now the only true restrictions are on exporting to countries under embargo.

You are free to write software that uses any key length to protect the messages.


Why is this a fix to Bleichenbacher's attack?

Why does this prevent the attack? Why doesn't the attacker just infer that the connection failed because of the bad padding? Why else could the connection fail?

Well, the connection may fail because the host decrypted a valid pre-master secret, and it wasn't the pre-master secret that we expect.

That is, when the attacker injects his encrypted message, one of two things can happen:

The server attempts to decrypt the message, and finds that the padding is invalid
The server decrypts the message, and finds a value there.

The information that the attacker needs to know is whether (1) or (2) happened; if he can determine that, then he knows whether the padding looked correct or not.

Now, with the attack, if (2) happens, then the attacker has no idea what the value would be.  Hence, if we react to (1) in a way that mimics the behavior in (2), we prevent the attacker from learning that.


Depth of the SHA-256 collision search knowing partial input and final hashes

Yes, but please note that the question/answers you are pointing to are about partial collisions on the output, not partial input. Finding a full hash collision is not computationally feasible for hash functions that are considered secure, such as SHA-256.


Viability of an "Unconventional" Hashing Scheme?

It is too likely the input mutation reduces the search space too much as most people will input heavily lossy mutations. I know better. 99% of people don't know better.

Even the simple case of {"at"->"@", "what"->"#"} which I see as the kind of thing people will be loading, is a bad idea.


Are there reference implementations of ECQV implicit certificates?

For the sake of moving this question off of the "unanswered" list, the answer seems to be no. I spent time looking as implicit certificates are relevant to a project we are beginning to work on.

SECG, which has the draft standard for ECQV, does have a future project for test implementations of their standardized primitives/protocols.

They have a mailing list, but I have not subscribed. You could ask there.


Salts, how does the script know what the salt is?

The salt has two main purposes as I understand it.

To ensure that two users who choose the same password, get different password hashes.

Say the CEO, and the janitor, choose the same password. Without a salt, they'd both get the same hash. This means that an attacker who managed to download the password file, could instantly see that the CEO, and the janitor, have the same password (whatever that is). So instead of putting a keylogger on the CEOs laptop, he'd just beat the password out of the janitor! Or if the janitor was the attacker, he'd instantly see that his own password, was also the CEO's - so he could log in as the CEO, without having to try multiple passwords and risk a system alert.

With a salt, the two hashes are completely different, and no attacker can possibly know that several users have the same password. Salting the passwords also ensures that users who choose the same password on different systems, get different hashes on each of those systems.

For (1), the only actual requirement, as far as I can see, is that the salt is different for different users - because even the slightest change in salt+password, will cause an enormous change in the hash thereof. So you could just use an increasing number 1, 2, 3 etc. It needn't be large, random, or secret - just different for different users.

However, in practice, when you're storing the password for a new user, you don't necessarily want to scan the other users' salts, to check you pick a different value; and you sure don't know what salts were used on other systems! So a common approach is to "take a chance", and just pick a big random number, hoping that the resultant number hasn't been picked before. The bigger the number, the less chance it has been picked before.
To reduce the chance of password cracking using rainbow tables.

Say an attacker pre-computes the hashes of a million common passwords, and stores those in a table. So the table has a million (password, hash) entries. (These are commonly called rainbow tables.) Then, when he downloads a password file, he just looks-up each of the hashes, from that file, in that table. If hash value 1234567890 matches table entry ("letmein", 1234567890), he now knows that password "letmein" will produce that hash - voila! The table takes time to generate, and space to store. But once done, it will instantly crack those million passwords - if they are unsalted.

But say each password is salted with one of (say) 1000 different values - perhaps just a number from 1 to 1000. Now the attacker has to pre-compute each password 1000 times - once for each possible salt. So the table is now a thousand times larger. Clearly, if the salt is large enough, this makes the table infeasible - it takes too long to generate, and is too large to store.

For (2), the requirement is, as I understand it, that the salt has many different potential values, and is unpredictable. If the salt doesn't have many different potential values, the table is still feasible. And if the salt is predictable, the attacker just generate a rainbow table for the predictable values, and hopes for the best!

So to meet both (1) and (2), you just pick a large random number for the salt. As I understand it, 32 BYTE salts are coinsidered the go these days.

Using the DATE as a salt is a very very bad idea. That wouldn't even achieve benefit (1) - let alone benefit (2). If I saw code that used the date for a salt, I'd not trust that code for any security related functions of any description - the author has no idea what he's doing.


Username and Password: How does it work?

"Will they just scrap all the previously negotiated keys and switch to TLS-PSK with

Password-Authenticated Key Agreement or Password-Based Key Derivation?"

No.

"What will happen next?"

"Could you please describe how client and server use username and password?"

"What are the steps and algorithms used in this?"

The server will look up the username's salt, hash the password with it, and then compare

the result to the stored password has.  If they are equal, then authentication succeeds,

else authentication fails.  The algorithms used in this are PBKDF2,bcrypt,scrypt.


Convergent Encryption: integrity and authenticity

If you use the hash as a known key, then you do not need any additional authentication to ensure plaintext integrity. An attacker cannot find another plaintext with that hash value unless the hash is broken.
However, there are two problems with that:

Like MAC-then-encrypt the hash only ensures authenticity of the plaintext, not of the ciphertext. This leaves it possible for an attacker to use chosen ciphertext attacks and CBC implementations may be vulnerable to the padding oracle attack.

Typically in convergent encryption you have a longer term secret key that is used to encrypt many plaintexts, and the hash that is used as key for one plaintext gets encrypted for the long term key.
Unless the hash/key is encrypted with authenticated encryption, a chosen plaintext attack could allow an attacker to halve the hash space to 128 bits, for which collisions could be found. I.e. you probably want to ensure the authenticity of the encrypted hash, if you use this setup.

Thus, I would recommend using authenticated encryption the whole way through. If you are concerned about space usage, you can shave off some by getting rid of the IV. One-time keys can be used with zero IV.


How to store encrypted solutions of a find location game?

There is the idea of a fuzzy vault, a coding theory based idea first proposed by Juels,
developed for biometric applications, it warrants a look.

Start at Wikipedia. These notes below are excellent:

https://wiki.cse.buffalo.edu/cse545/content/fuzzy-vault


What consequences do the plaintext space size has on the performances in the BGV scheme?

A helpful resource to assess which ring-based FHE scheme (like BGV) would work best for you, see here: https://eprint.iacr.org/2015/889

In this paper they compare four schemes: BGV, FV, NTRU, and YASHE.

The reason I point you there is that one major factor in the performance of these schemes is the value of p. If a large p is used, BGV outperforms the rest. If a small p is used, YASHE wins, but not by too much. The other main factor is the L parameter.

The metric they use to compare them is the ciphertext size, which is crude but gives a rough estimate as to the computational time needed.


In general, you cannot prove lack of knowledge, because even if you did know something you shouldn't, you can always pretend that you don't know it and carry out the proof as if you didn't know it.

For your specific example, consider how the prover would know $x_0$.  Did you tell them what it is?  If so, that proves nothing, since they would then know $x_0$ even if they had also learned $x_1$ from somewhere else.

Conversely, if your function $f$ is collision resistant without the trapdoor, but is not injective (i.e. potential collisions do exist), then it must also be preimage resistant.  Thus, finding $x_0$ from $y = f(x_0)$ is (at least) as hard as finding $x_1$.  Thus, paradoxically, the prover exhibiting $x_0$ would in fact be evidence that they can find preimages for $f$, and thus can probably find $x_1$ as well.


Computational Complexity Of Breaking Information Theoretic Security

Here's an simpler but analogous problem that may illustrate what's going on:

Given that $X=Y+Z$ and $Y=5$, compute $X$.

The problem isn't that the answer is difficult to compute, the problem is that there isn't enough information there to give you any idea (any information about) what the answer is. That's what's meant by information-theoretic security.
(Note: what I've given above isn't actually an example of SSS, and if you actually try to apply statistical information theory to it, you'll run into trouble because the integers are infinite. If you're really worried about the latter issue, assume we're doing arithmetic modulo some integer $>5$)


How does $g^{x^2} \bmod p$ help you find $x$?

It is not known that knowing $g^{x^2}$ would help in any meaningful way to solve the discrete logarithm problem.
What you are describing can be generalized to asking whether in a group $\mathbb{G}$ giving an attacker $$(g, g^x,g^{x^2},\dots,g^{x^q})$$ for some $q$ and a uniformly chosen $x \in |\mathbb{G}|$ makes it feasible to recover $x$.
It is generally assumed that this is not the case. In fact the assumption that recovering $x$ remains hard is called the $q$-strong discrete logarithm ($q$-SDL) assumption and has been used before. [GOR11] Similarly, the bilinear variant is also assumed to be hard. [FS20]
While the $q$-SDL assumption itself is not used very often, it is actually implied by a variety of much more commonly used variants of $q$-strong Diffie Hellman assumptions. [TS10]

[GOR11] Vipul Goyal, Adam O'Neill, and Vanishree Rao. "Correlated-Input Secure Hash Functions". TCC 2011
[FS20] Nils Fleischhacker and Mark Simkin. "Robust Property-Preserving Hash Functions for Hamming Distance and More". Cryptology ePrint Archive, Report 2020/1301, 2020
[TS10] Naoki Tanaka and Taiichi Saito, "On the $q$-Strong Diffie-Hellman Problem". Cryptology ePrint Archive, Report 2010/215, 2010


What is proactive secret sharing scheme?

Proactive secret sharing schemes are typically used for multi-party computation variously referred to as "Secure computation" or simply MPC that arose from the work of Yao and Goldreich, Micali and Wigderson (GMW) in the 80s.
MPC's require secrets to be shared among multiple parties, and some of these parties may be controlled by an adversary that is in the most general setting able to deviate from the specified protocol in a "byzantine" manner. As a concrete case, in the GMW protocol with $n$ parties, in order for the $i$th party to share its bit $b_{i} \in \{0,1\}$ with the other $n - 1$ parties, she generates $n - 1$ i.i.d uniformly random bits and sends one of the generated bits to each of the parties. She then sets her share of $b_{i}$ such that the sum of her share and the other $n - 1$ bits mod 2 gives back the original bit $b_{i}$. This sharing scheme is "perfectly" secure since there is no complexity assumption.
In the classic MPC model, it is assumed that the parties controlled by the adversary are determined beforehand and remain fixed during the course. This is sometimes called static corruption.

In the early 90s, Ostrovsky and Yung ("How to Withstand Mobile Virus Attacks", In PODC, pages 51–59) described settings where the adversary is allowed to control a varying number of parties throughout the computation and corrupt additional parties that may have been intact at the onset of the protocol. This is typically called dynamic corruption, and protos that are able to remain secure in this setting are sometimes called proactively secure. In this model, "proactive" security property stems primarily from the fact that secrets shared among the parties are periodically re-randomized through a sharing scheme, called a proactively secure secret sharing scheme (PSS).

I should note that the original Ostrovsky and Yung paper from 1991 does not explicitly use the term proactive secret sharing, but this term is used in a 2014 rework of the '91 paper ("How to withstand mobile virus attacks, revisited" by Baron, El-Defrawey, Lampkins and Ostrovsky [BELO14]). The "Block-Redistribute" aspect of the protocol forms the core part of the PSS scheme in the [BELO14] MPC, but it's presented as a specification rather than a formal definition. As such, I have not found a succinct formal definition for "proactive secret sharing". What you may ask for, on the other hand, is a definition of what it means for a MPC to be proactively secure rather than strictly a definition of the term "proactive secret sharing". If that's the case, the definitions in [BELO14] sec. 2.1 " The Proactive Model under the UC Framework" are helpful.


lookup encrypted text by clear text without decryption

Query with SELECT

AES with ECB mode can be used as long as the vouchers codes are unique. ECB mode gives you the same results when the key and plaintext are same.
Another solution is continuing to use AES-GCM to save your vouchers codes. To have the equality on the SELECT statement, use a secure hash function e.g. choose from the SHA3 family. With negligible probability, you will have a collision. If you have a collision store the values, you will be famous. In any case, you will decrypt the AES-GSM after the match of the hash values.

Attacks

As I said in the comment you attack is very broad; I will give answer for single cases;

System admins: If you don't trust them, this is a serious issue. They can query everything, even you deploy an HSM. They can insert, delete, etc. Keeping a query log of the Database may help you investigate. Also, there are works as RSA Beehive's that can detect the behavioral change of the users of the system that will can block action. They claimed that "we can prevent the Snowden."
Attackers: For the database attack, see the next. If the attacker access the application servers they will be same as a malicious system administrator, probably, a short time.
DB data breach: Since the clear vouchers are not in the database, We expect that by the collision-free and the security of AES-GCM the database will be untouched. However, if the database attacker is also an active attacker, you may need some integrity into your rows and even some chaining link for the columns. A simple one as in blow;

r_i  = |data_1|... |data_k| h_i   = hash(data_1,...,data_k)| sign(h)|
r_i+1 =|data_1|....|data_k| h_i+1 = hash(data_1,...,data_k)| sign(h_i+1||h_i|)|


Linear Recurrence, keystreams, and periods

Yes, all combinations of 0,1 of length 4. Interpret $(0,1,0,1)$ (as an example) as $z_0 = 0, z_1 = 1, z_2 = 0, z_3 = 1$. Then $z_4$ is given by the sum of these 4, so $z_4 = 0$ (as we work mod 2), so the sequence becomes $(0,1,0,1,0)$. Then $z_5 = z_4 + z_3 + z_2 + z_1 = 0$ mod 2, again, so we have $(0,1,0,1,0,0)$, etc. You go on till you find that the last 4 sequence elements are $(0,1,0,1)$ again, and then you know the period (you're back where you started): the number of steps (i.e. new sequence elements computed) taken to get there.

And this you do for all these 16 start inputs. You'll find $(0,0,0,0)$ as a start pretty boring...


Is any group of bits in a SHA-1 hash more/less unique than another?

Yes in a sense in terms of the Hamming weight/Hamming distance. This relates to how the changes of one bit or series of bits affect others. While there is also an avalanche effect counteracting many n string bits attacks, Hamming dictates some attacks to be more successful on certain n bit strings and thus certain n bit strings more vulnerable to exploits:

http://people.csail.mit.edu/yiqun/SHA1AttackProceedingVersion.pdf

http://www.sciencedirect.com/science/article/pii/S0166218X02005887


Steganography Decryption From Completely Black Image

GIF images use look-up tables to store colours. If two entries in a table contain the same colour, then the pixels assigned to these colour values will be indistinguishable.

For example, here is a one-bit-per-pixel GIF image. It started out as a black and white image, but I edited the colour table so that the white pixels also appear black:

You can retrieve the message by restoring the colour table in a graphics editor like Gimp (Colors → Map → Set Color Map) or by editing the data directly (change bytes 13, 14 and 15 of the file from 000000 to ffffff).

Other possible approaches include storing information in a comment field, or appending it to the end of the GIF data. In animated GIFs, the delay time between frames (in hundredths of a second) is represented by an unsigned 16-bit value, so it's possible to create an image that freezes on an empty frame for almost 11 minutes (655.35 seconds).

(By the way, encryption and steganography are two different things. If your image contains encrypted data, then finding this data is only the first step.)


Multiplication by 2 modulo 26 is indeed not a permutation.  For example, $$2 \times 13 = 26 \equiv 0 = 2 \times 0 \pmod{26}.$$

The necessary and sufficient criterion for the affine map $x \mapsto ax + b$ to be a permutation of the integers modulo $m$ is that the multiplicative constant $a$ and the modulus $m$ must be coprime; that is, their greatest common divisor must be 1.

If this is the case, then we can find the modular multiplicative inverse $a^{-1}$ of $a$ modulo $m$ and use that to define the inverse map $x \mapsto a^{-1}(x-b)$.  It's easy to verify, based on the fact that $a^{-1} a \equiv 1 \pmod m$, that the composition of these two maps (in either order) yields the identity map $x  \mapsto x$, which is sufficient to show that these maps must be bijective.

Conversely, if $a$ and $m$ share a common divisor $g > 1$, then the map $x  \mapsto ax + b$ cannot be a bijection.  In particular, both $0$ and $m/g$ will be mapped to the same element $b$ by this map.


Why AES 256 GCM is more preferred by email service providers / banks over the fast and efficient ChaCha20 - Poly1305?

AES-GCM is standardized by National Institute of Standards and Technology, the institution that drives standards for U.S. Federal agencies.

In some situations (think banking, government, large corporations) FIPS certification is desired and in order to pass FIPS certification you need to use approved algorithms.
When you check FIPS 140-2 Annex A, you see that AES-GCM is one of the approved 'security functions'. ChaCha20 Poly1305 is not.

Another reason is that ChaCha20/Poly1305 is a relatively newer design. AFAIK, it has been accepted as an IETF standard in 2015 RFC7539 while AES-GCM is a standard since 2007 (NIST SP800-38D).

Moreover, AES has been around since 2000 and this means there is a lot of IP designs that have dedicated AES accelerators which make AES-GCM very efficient.

When it comes to security, AES is a very solid cipher and I would probably prefer it over Chacha20, but on the other hand GCM mode is very brittle and prone to implementation errors (think IV abuse) and it may be considered less desirable in some implementation-related scenarios.


How do AES and DES ensure data integrity?

Answer to your question title: they don't.

Answer to your inline question: yes (or something similar to it).

Longer answer:

Both DES and AES are examples of block ciphers, and block ciphers do not have any inherent integrity protection. Thus, in order to also ensure integrity you would need to add something more, for example a message authentication code (MAC) or a digital signature.

However, note that you would probably never want to combine DES and AES directly with, say, a MAC. Instead, you would want to use DES and AES in a dedicated mode-of-operation that provides both confidentiality and integrity for you (which together is called authenticated encryption).


AES 5-round Square attack, how to choose plaintexts?

In statistical attacks (such as square), if we can reduce the key space, it will be considered successful. Here, as you pointed, there are false-positives and they should be considered as correct key candidates. But the point is that the distinguisher has removed some incorrect keys and has reduced the key search space. After finding candidates for the correct key, you should do exhaustive search among them or try other attacks to even reduce the key space further!
Here, choosing the plaintexts does not have that much effect on the false positive, since different keys will change the chosen set differently.


Attack on RSA when I know $e$, ciphertexts $c_1, c_2$ of the same message $m$ with 2 coprime modules?

The problem seems like a variant of Håstad's broadcast attack, except that is usually stated with $e$ ciphertexts, when here there is $2<e$ ciphertexts.

We know $m^e$ modulo $n_1$ and modulo $n_2$ (that's the givens $c_1$ and $c_2$), thus we can compute $m^e\bmod(n_1\,n_2)=y$ using the Chinese Remainder Theorem, per $y\gets(n_2^{-1}(c_1-c_2)\bmod n_1)\,n_2+c_2$

If we are lucky enough that $m<\left\lfloor\sqrt[e]{n_1\,n_2}\right\rfloor$ (roughly, $m$ of bit size less than $1/e$ of the sum of the bit sizes of the moduli), then $y$ will be exactly the $e^\text{th}$ power of some integer $x$, we can get that $x$, and it will be $m$.

If not, we can try, for incremental $i$, if any of the $y_i=i\,c_1\,c_2+y$ is exactly an $e^\text{th}$ power; that slightly extends the attack.

Note: none of this is RSA as correctly practiced. What's raised to the power $e$ modulo $n$ should not be the message, but a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.


Speed up modular exponentation with fixed base and modulus

One obvious way is to precompute values $a^{k_1} \bmod N$, $a^{k_2} \bmod N$, ...,$a^{k_i} \bmod N$, and (depending on the value of $x$) multiply together the appropriate elements.

To take a simple example, if we precompute $a^1 \bmod N, a^2 \bmod N, a^4 \bmod N, ... a^{2^k} \bmod N$, and (based on the value of $x$ in binary, multiply the appropriate elements together); this gives a method which takes an average of $1/2 log_2 N$ multiplies, which is an obvious improvement over what you can do without any precomputation.

The paper gives a slightly more aggressive example (treating $x$ as a base 16 rather than a base 2 number).

However, you can do even better: see this paper for a survey of the various possibilities.

One note: if you are performing operations on an Elliptic Curve (that is, doing a point addition rather than a modular multiplication), then the operation of computing the inverse of an element is cheap; even though the cited paper doesn't cover that case, that can be used to reduce the number of operations even further.


What if AES-128 key / text length is more or less than 16 characters

AES is not a method of encrypting messages with passwords.  It is a pseudorandom permutation family, which is not designed to be used directly by applications.  Rather, a PRP is a very specific technical concept that cryptographers use to design methods of encrypting messages, called authenticated ciphers, like AES-GCM—and that cryptographers could use to derive keys from passwords, though usually we use other password-based key derivation functions like PBKDF2-SHA256 or scrypt or argon2id that don't involve AES.

For example, you could use scrypt to derive a 256-bit key $k$ from your password, and then encrypt your message $m$ using the authenticated cipher AES-GCM under the key $k$—or the even better authenticated cipher crypto_secretbox_xsalsa20poly1305 from NaCl which doesn't involve AES at all.

Don't use the letters A-E-S directly in your application; use an authenticated cipher.  The keywords above should lead you to plenty of followup reading material.


Besides binary, decimal, hex, oct, are there encryption algorithms based on exotic/other numbering systems?

There's FF1 and FF3, which are Format Preserving Encryption methods that can use an arbitrary base internally.  This can be useful, for example, if you are encrypting a fixed length alphanumeric field, it would make sense to use base 36 (radix=36) or base 62 (if upper and lower cases are distinguished).


What does "Inverting the RSA function is as hard as factoring" mean (a rigorous explanation or intuitive will do)?

We are dealing here with two assumptions and we always refer to $N=pq$ the product of two $n$ bit primes $p$ and $q$. The one is factoring and the second is the so called RSA assumption which is a formalization of "inverting the RSA function is hard".

These two assumption can be described as follows:

Factoring assumption: There exists no probabilistic polynomial-time algorithm
that, given an RSA modulus $N$, finds a non-trivial factor of $N$ with non-negligible probability in $n$.

RSA assumption: There exists no probabilistic polynomial-time algorithm
that, given the pair $(N,e)$ with $N$ being an RSA modulus and $e > 2$ with $\gcd(e,\varphi(N)) = 1$ and an element $y$ chosen uniformly at random from $Z_N^*$, computes $x\in Z_N^*$ such that $x^e\equiv y \pmod{N}$ with non-negligible probability in $n$.

Now you ask

  I was reading that a current open problem is if inverting the RSA function is as hard as factoring

Yes, this means that it is an open question whether these two things are equally hard. In a formal language this means whether a solver for the first problem yields a solver for the second and vice versa.

Now, it is quite obvious that when one has an efficient algorithm $\cal A$ that breaks the factoring assumption, this implies an efficient algorithm $\cal B$ that breaks the RSA assumption. Basically, if $\cal A$ outputs a non-trivial factor of $N$, say $p$, then $\cal B$ can efficiently comptue $q$ and thus knows $p$ and $q$ which allows to efficiently compute $\varphi(N)$ and futher to efficiently compute $d$ such that $e\cdot d \equiv \pmod{}\varphi(N)$ (e.g., using extended euclid) and outputs $y^d \mod N$.

Consequently, if the RSA assumption holds then the factoring assumption holds or equivalent if the factoring assumption does not hold, then the RSA assumption does not hold. However, it is not known whether the converse is true, i.e., if the factoring assumption holds then the RSA assumption holds or equivalent if the RSA assumption does not hold then the factoring assumption does not hold.

Latter would require to show that an efficient algorithm $\cal B'$ that breaks the RSA assumption implies an efficient algorithm $\cal A'$ to break the factoring assumption.  But as you said, this is an open problem.

If one could establish the latter result, then we would know that the RSA problem and the factoring problem are equally hard.


You can use pin sketch. Consider the set of number [0,1,2,3,4,5,6,7]. The presence of a number can represent the presence of a 1 at that bit position in an 8 bit number.

E.G.

[0,2,4,6] == 10101010 == 0x55

[0,1,2,3] == 11110000 == 0xF0

Extend to a useful size (like 2040 bits which maps nicely to a BCH code) and you are comparing sets that have on average 1020 unique values, each showing the positions of the ones.


Can a self-signed certificate's signature algorithm be changed?

Yes, you can do this, but you would need to change the OID for the signature generation algorithm as well. This may require some more advanced ASN.1 decoding and re-encoding. This is very likely more problematic than the calculation of the signature.

Obviously the fingerprint of the certificate will change as well (as that is just over the binary encoding of the certificate). So beware of this if the certificate is placed in a trust store.


What's the internal state size and output range of mrg32k3a?

The answer is based on the given period construction from your link.

You have to store the two modulus

$m_1 = 2^{32} − 209 = 4294967087$ and
$m_2 = 2^{32} − 22853 = 4294944443,$

and the internal states are;

$s_{1,n} = \{x_{1,n},x_{1,n+1}, x_{1,n+1} \}$ and
$s_{2,n} = \{x_{2,n},x_{2,n+1}, x_{2,n+1} \}$.

The $z_n = (x_{1,n}- x_{2,n}) \bmod m_1$, evolves with this $x_{1,n}$ and $x_{2,n}$ where each requrrence relation for  $x_{1,n}$ and $x_{2,n}$ is taken module $m_1$ and $m_2$, respectively;

$$x_{1,n} = (1403580 \times x_{1,n-2} - 810728 \times x_{1,n-3} ) \bmod m_1,$$
$$x_{2,n} = (527612 \times x_{2,n-2} -1370589 \times x_{2,n-3} ) \bmod m_2$$

Therefore you need to store 3 moduli $m_1$ and 3 moduli $m_2$ internal states.

The $m_1$ and $m_2$ is very close to $2^{32}$, so we can say that you need;

6 unsigned 32-bit integers for the internal states.
For the modulus, you will also need 2 unsigned 32-bit integers.

the range is $m_1$ since the $z_n$ is taken $\mod m_1$.

Yes; the state for all practical purposes is $8 \cdot 32=256$-bit.


Encrypting 8 times with 8-bit key beneficial?

For a meet-in-the-middle attack with known plaintext, you break all $K_i$ at the same time. The goal is to split the work into multiple sides, trading off some exponential work for some exponential space and some linear work.

Split the encryption and decryption sides evenly. You need $(2^8)^4 \times 2 = 2^{33}$ block cipher calls, because you need 4 layers of $2^8$ encryption calls and 4 layers of $2^8$ decryption calls. (The work for both sides combines linearly, rather than exponentially, which is where the power of MITM lies.) When a match in the middle is found (the more known plaintext the better, since false positives are possible), you retrieve the key that was used to generate the mid-state matches from both sides, combine the two halves, and get the full $K$.

There's a shortcut for that analysis: Double-layering a cipher using different keys attempts to build a key of length $2n$, but an MITM attack can reduce it back to an effective key length of $n+1$. So for the question at hand, pretend we actually had a cipher with a 32-bit key (it iterates the original cipher 4 times internally) and that hypothetical cipher itself was iterated twice. We take the hypothetical 32-bit key, double it to a 64-bit key, then MITM reduces it to a 33-bit key.

A work factor of $2^{33}$ to recover all of $K$ is much less than the attempted strength of $2^{64}$. At almost half the length, it's a break.

(Side note: Splitting the work in the middle of the layers is the most efficient, but, for fun, you could split it elsewhere. Consider doing the MITM split at, say, $K_1$ and $K_2$. It would require $(2^8)^6 + (2^8)^2 = 2^{48} + 2^{16}$ calls to the block cipher, as you need 6 layers of $2^8$ encryptions, and 2 layers of $2^8$ decryptions. To conceptualize how MITM works, it may help to think of brute-force as a special-case MITM with 0 rounds on one of the sides, resulting in $(2^8)^8 + 0 = 2^{64}$ work, which is the full key space.)

That uses just one encryption/decryption split, also known as one-dimensional MITM. For ciphers layered more than twice, there are multi-dimensional MITM attacks, which apply an encryption and decryption split at each layer. It's more complicated, but it enhances the attack even more.


One Time Password generation algorithm to ensure data/transaction integrity?

What you're imagining is impossible to be secure.

Basically what you're describing is a message authentication system where a message is MAC'ed and only the MAC is matched against the actual MAC, but it isn't checked whether the message actually generates this MAC, so an attacker could just fake the transaction details and leave the MAC be and the user would enter the MAC and thus accept the transaction.

Now I'm gonna tell you how many banks here in Germany solved the problem.
This assumes you've issued a card with a chip to every customer and keep track of all cards.
If the user wants to make a transaction, he uses his browser to fill in the data. Then the browser takes him to a page where he is either presented with an optical code (not unlike a QR code, but also using time-based patterns) or some data.
The user has to either scan the code or enter the data, into a physically separate device in which the user plugged the card. The data consists of the amount and the last few digits of the recipients account number. Now the device passes this data to the card which basically just performs HOTP but also incorporates the values for amount and recipient in the calculations. This is done after the user verified the correctness of the transaction on the built-in display. Now he's presented with a short code which he has to enter into the browser. The server confirms the calculations and initiates the transaction.

In a more mathyy way, the OTP would look like this:

$$\text{OTP}=\operatorname{BytesToCode}(\operatorname{HMAC-SHA256}_{\text{Card-Server-Key}}(\text{amount}||\text{recipient}||\text{counter}))$$


Randomness of Decision Learning With Error Problem

As Peikert has commented (and my first answer was not dealing with this issue carefully), the LWE problem asks you to distinguish between
$(\vec a, \langle \vec a, \vec s \rangle + e \mod q) \in \mathbb{Z}_q^{n+1}$
and $\vec u \in \mathbb{Z}_q^{n+1}$ (with each entry of $\vec u$ sampled uniformly from $\mathbb{Z}_q$) given many samples.

This is why the LWE problem is usually defined with a parameter $m$, which represents the number of samples
$(\vec a_i, \langle \vec a_i, \vec s \rangle + e_i \mod q)$
that you can get. Notice that all the samples use the same fixed secret $\vec s$.

The problem says nothing about how you are going to distinguish those two distributions. Given many samples, if you run an statistical test or some clever algorithm using lattices, it does not matter, as long as you can tell to which distribution those samples belong.

And about $b_i := \langle \vec a_i, \vec s \rangle + e_i \mod q$ being distributed uniformly on $\mathbb{Z}_q$, indeed, if you have a single sample, then that is the case, but again, if you have several samples, say, $m$,
then, the distribution of $(a_i, b_i)_{i=1}^m$ can possibly be distinguished from the uniform over $\mathbb{Z}_q^{n+1}$.
In particular, if you can recover $\vec s$, then you can simply compute $b_i - \langle \vec a_i, \vec s \rangle \mod q$ to get $e_i$, which are all small, thus, not uniformly distributed.

A final note, in your question you say "From what i understand a and e are both randomly sampled from uniform distribution", but actually, only $\vec a$ is uniformly chosen from $\mathbb{Z}_q$, the noise term $e$ usually follows a distribution that is likely to sample values much smaller than $q$ (like a Gaussian distribution with parameter approx. $\sqrt n$).


Here, I think BLOB is meant to be interpreted as binary large object, and it refers to the 128 bytes of data that differ between the two files but which produce the same MD5 hash output.  Those are the two parts of the files that differ between the two programs but which yield the same MD5 partial result.

So look at it this way.  You start out hashing each file at the beginning and compute the interim hash value through the prefix.  Obviously both hashes will, at this point, be the same because the prefixes in both files are the same.

Now a new interim hash result is computed using the above mentioned result so far and the new chunk of data, the portion they refer to as BlobA and BlobB.  These data chunks differ but were constructed to yield the same MD5 output.  So after these middle sections are hashed, the partial hash for each file is still identical.

The hash process then continues on each file through the suffix, which like the prefix, is identical for both files.  So the output (final) MD5 hash will be the same.  At this point, my understanding of the passage you quoted is that if you have 2 files that hash to the same MD5 value, you can now append anything you like to the end of those files (as long as it is the same data for both files) and the MD5 hash will change for both files in exactly the same way, so they will continue to have identical hashes one to the other.


We consider the following cases.

Somewhat Homomorphic Schemes(SHS), Fully H.S. (FHS) and Partially Homomorphic Schemes (i.e. homomorphic with respect one operation, either addition or multiplication). RSA belongs to the third case, which is multiplicative homomorphic and is fast.
Remark that, the textbook-RSA is multiplicative homomorphic and  so insecure, since we do not use a secure padding scheme.
A secure cryptosystem in this class is the Pallier's additive homomorphic cryptosystem.

SHS support both operations, addition and multiplication but up to some level. In these systems, beyond some level, the noise to the ciphertext increases so much as a result the decryption is not correct.
There are many SHS such as, the family based on the Learning With Errors problem. These systems are slow because they use large keys in order to get the necessary security.

FHS start with a SHS (all SHS are noisy encryption schemes). The construction of Gentry, found a way to refresh the ciphertext in order to decrease the noise (bootstrapping). The reason that make them slow is the bootstrapping step. It applies an operation to ciphertext called ${\tt Recrypt}$, which increases the complexity of the system but also manages to control the noise. So allows as many operation we want and the decryption will be correct. I suggest you to read the original paper of Gentry for the case of FHE. Also see this post.


Construct a specific length-doubling pseudorandom generator from a length-doubling pseudorandom

Define $\forall s\in \{0,1\}^{n} \ : H(s)=G(s)\oplus G(0^n)\implies H(0^n)=G(0^n)\oplus G(0^n)=0^{2n}$
now, we'll prove by contradiction that $H$ is indeed a pseudo-random generator.
assuming that it's not we get that there exist an adversary D (PPT algo) such that for every polynomial p(n):
$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$
Now, define the adversary $D'(v):=v\oplus G(0^n)$ for the PRG "$G$", and we're almost done:
$|Pr_{s\leftarrow\{0,1\}^n}[D'(G(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D'(r)=1]|=$
$|Pr_{s\leftarrow\{0,1\}^n}[D(G(s)\oplus G(0^n))=1]-Pr_{r\leftarrow\{0,1\}^n}[D((r)\oplus G(0^n)=1]|=$
$|Pr_{s\leftarrow\{0,1\}^n}[D(H(s))=1]-Pr_{r\leftarrow\{0,1\}^n}[D(r)=1]|>1/p(n)$
$\blacksquare$


What are the advantages and disadvantages of Merkle signatures over Lamport signatures?

why would someone use Merkle signatures when they have a perfectly fine one-time signature already?

Because Merkle signatures are not one-time.  Instead, you can use a private key to sign a number of messages. There is a finite limit, however that limit is potentially large.


How can I improve a password generation scheme based on a shared secret and URL?

password = sha1 ( mainPassword . domainName . number )
  Is this secure enough?

Answer is no. Let me explain. The only part that is really unknown in the above is mainPassword. The rest can easily be guessed by a hacker. If your original password is weak (not many characters, no digits, no specials characters), the number of combinations to test is small enough for brute force attack (i.e., testing them all). sha1 is not going to help. You are also vulnerable to collision attacks (google it for more information).

You need to learn about salting and stretching. Use a sufficiently large random number too when you salt-and-strech. Make sure you stretch with enough rounds. Salt and stretch only works if the mainPassword is good enough in the first place.

  could he find easily one of my other password?

If you use a random when salting and stretching, it makes it much harder to guess another password from a known password.

  When one of my password is compromised, I just increment the number. Is it enough?

Absolutely not. It is very easy for the hacker to increase the number too. You really need to use salt-and-strechting with another random number.

  sha1( sha1( ... sha1( str ) ... ))

Not helping when used like that (again, learn about salting and stretching). If you are uncomfortable with SHA1, use SHA256 (or SHA512) as the hash function.

EDIT

  How to keep secret the salt in an open source project? The only other
  way is to make the user choose the salt which seems to be exactly the
  to ask for a longer password. Am I wrong?

Hiding the salt is not absolutely necessary. You could also include a timestamp in the salt-and-stretching. It would require you to perform extra rounds on the server side with the timestamp. If the timestamp is too old, refuse the log on.

EDIT2

To be complete. You can implement something like that:

User picks a password.
A = any public random;
FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with user pwd
Store hash on server.
Logon -> Server picks a new large random R and sends it to client with authentication
Let t = current time;
User verifies authentication for received R.
User computes FOR 1 TO 1000 (or more) hash = SHA( A || hash ); with entered pwd
Then, FOR 1 TO 1000 (or more) hash = SHA( R || SHA( hash || t) );
Send hash, R, t to server
Server check t is ok (for replay)
Server computes FOR 1 TO 1000 (or more) SHA( R || SHA( stored_hash || t) );
Server checks computed against received, and eventually validates logon.

It will kill many attack venues, but it is impossible to eliminate them all.

EDIT II

Sorry, there is an issue with step 8 (and 11), this step needs to be performed 1000 times (i.e., or whatever the number of salt-and-stretch iteration you need) too, or it does not make sense to iterate 1000 in step 7 in the first place.