TL;DR at the bottom.

The general ideas of timing attacks are the following:

Secret data has influence on timing of software
Attacker measures timing
Attacker computes influence$^{-1}$ to obtain secret data

A Basic weakness: if( secret )

The base of an exploitable code sensitive to a timing attack looks like this:

if(secret)
{
  do_A();
}
else
{
  do_B();
}

The idea is that the time to compute A is different to the time to compute B. Thus knowing this difference, you can compute back the secret.

Let us have a look at the following code which is closer to a real world code.
This is the core operation in RSA decryption: $a^d \bmod n$ with secret key $d$:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can see that you have a if section which depend on the secret (exp[i] >> j) & 1. If the value of the secret is 1 then you will execute r = ((uint64)a*r) % mod. If the value of the secret is 0 you will execute nothing. Thus you have a difference in the time of the execution depending on the secret.

Let us improve this code a bit:

typedef unsigned long long uint64;
typedef uint32_t uint32;

/* This really wants to be done with long integers */
uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1, t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      if((exp[i] >> j) & 1)
        r = ((uint64)a*r) % mod;
      else
        t = ((uint64)a*r) % mod;
    }
  }
  return r;
}

In this code you can think that because we do the same thing on both branch of the if statement that depend on the secret (exp[i] >> j) & 1:

1 assignment.
1 multiplication
1 modulo operation

The time to execute either branch will be the same, Right ?

Well... No. Because... t is a dead variable and the compiler will certainly notice it and will optimize the code. "This variable is useless, get rid of it!". The compiled code will therefore be the same as the one from before where you had your timing vulnerability.

But even if we force the compiler to not optimize the code, it is still not constant time :

modern CPUs have branch prediction.
and instruction cache.

Therefore we need to get rid of this branching weakness.

Removing the branches

How do we remove the branching of something like this:

if (s)
  r = do_A()
else
  r = do_B()

We replace it by something like this:

r = s * do_A() + (1 - s) * do_B()

Because we want fast code, we can expand s to all-one/all-zero mask and use XOR instead of addition, AND instead of multiplication.

So moving back to our Square-and-multiply:

uint32 modexp(uint32 a, uint32 mod, const unsigned char exp[4]) {
  int i,j;
  uint32 r = 1,t;

  for(i=3;i>=0;i--) {
    for(j=7;j>=0;j--) {
      r = ((uint64)r*r) % mod;
      t = ((uint64)a*r) % mod;
      cmov(&r, &t, (exp[i] >> j) & 1);
    }
  }
  return r;
}

where cmov (as conditionnal move) is an assembler instruction of same name (which doesn't use any prediction) or is defined as the following:

/* decision bit b has to be either 0 or 1 */
void cmov(uint32 *r, const uint32 *a, uint32 b)
{
  uint32 t;
  b = -b; /* Now b is either 0 or 0xffffffff */
  t = (*r ^ *a) & b;
  *r ^= t;
}

Another weakness: table[secret]

The idea is the following, the cache of your processor contains your table. And because everything in the cache is accessible within the same timeframe your secret is safe.

address  | content
------------------
0x0001   |    8
0x0002   |    7
0x0003   |    6
0x0004   |    5
0x0005   |    4
0x0006   |    3
0x0007   |    2
0x0008   |    1

That is true... if you only have this code running. However you always have other code running at the same time on your CPU, therefore some parts of your table will be as following:

address  | content
------------------
0x0001   |    8
0x0002   |   XXX
0x0003   |   XXX
0x0004   |    5
0x0005   |   XXX
0x0006   |    3
0x0007   |    2
0x0008   |    1

And we assume that the attacker has control over which part of the cache is corrupted. Therefore if secret is 0x0001 then you will have an immediate response from the cache. However, if the secret is 0x0002, the cache is invalid. Therefore the CPU will have to reload the value from the stack / memory. This takes a longer time, because we have a timing difference... We have a possible timing attack.

The counter measures are quite complex and I won't elaborate on them.

References

A big part of this answer is from this slides: Timing Attacks and Countermeasures by Peter Schwabe at the Crypto Summer School 2016 - Croatia.

Some interesting readings:

Osvik, Shamir, Tromer, 2006:
Cache Attacks and Countermeasures: the Case of AES.
http://eprint.iacr.org/2005/271/

AlFardan, Paterson, 2013: Lucky Thirteen: Breaking the TLS and DTLS Record Protocols.
http://www.isg.rhul.ac.uk/tls/Lucky13.html

Yarom, Falkner, 2014: FLUSH + RELOAD: a High Resolution, Low Noise, L3 Cache Side-Channel Attack.
http://eprint.iacr.org/2013/448/

Benger, van de Pol, Smart, Yarom, 2014: “Ooh Aah... Just a Little Bit”: A small amount of side channel can go a long way.
http://eprint.iacr.org/2014/161/

Bernstein, 2005: Cache-timing attacks on AES.
http://cr.yp.to/papers.html#cachetiming

Brickell, 2011: Technologies to Improve Platform Security.
http://www.chesworkshop.org/ches2011/presentations/Invited%201/CHES2011_Invited_1.pdf

Bernstein, Schwabe, 2013: A word of warning.
https://cryptojedi.org/peter/data/chesrump-20130822.pdf
https://cryptojedi.org/peter/data/cacheline.tar.bz2

Yarom, Genkin, Heninger, 2016: CacheBleed: A Timing Attack on OpenSSL Constant Time RSA
https://ssrg.nicta.com.au/projects/TS/cachebleed/

Hamburg, 2009: Accelerating AES with Vector Permute Instructions.
http://mikehamburg.com/papers/vector_aes/vector_aes.pdf

Biham, 1997: “A Fast New DES Implementation in Software.”
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi?1997/CS/CS0891

TL;DR

If you read this and skipped the whole answer, then it means that you definitively don't want to write crypto code.

If you did read the whole answer, then you probably understood why it is a bad idea to write crypto code by yourself given how many ways you can screw up.


Reverse Encryption Algorithm from Decryption code

First of all, the write() function does nothing but decode a single hexadecimal digit into a number from 0 to 15.  You could replace it with:

function write(x) {
    return parseInt(x, 16);
}

Thus, the code:

var diff = write(input[i]);
var firstNum = write(input[i + 1]);

takes two consecutive hex digits from the input string and decodes them.  The expression 16 * diff + firstNum then just multiplies the first digit by 16 and adds it to the second one, giving you an 8-bit number from 0 to 255.  (In fact, since parseInt() can handle multi-digit numbers, you could replace all that code with just parseInt(input.substr(i, 2)).)

Next, the 8-bit number we just decoded is XORed with the value of this long expression:

[31, 126, 188, 168, 210, 3, 208, 219, 229, 149, 187, 222, 17, 31, 59, 100, 131, 62, 163, 81, 115, 154, 2, 220, 166, 30, 112, 192, 48, 172, 174, 119, 249, 5, 251, 41, 46, 148, 43, 210, 35, 42, 231, 145, 16, 6, 10, 28, 228, 49, 103, 248, 151, 109, 19, 20, 151, 243, 12, 193, 152, 126, 83, 235, 27, 109, 66, 96, 179, 88, 11, 189, 30, 187, 23, 172, 93, 109, 239, 247, 123, 105, 55, 98, 117, 175, 114, 212, 146, 136, 38, 115, 124, 39][i / 2]

Scrolling to the end, you can see that it's just a long array literal indexed by i / 2.  Since i counts hex digits from the start of the input and is incremented by 2 per iteration, i / 2 is simply counting the number of bytes output so far.  Thus, each byte of the decoded string is XORed with a different number from this fixed array.

(If the index i / 2 points past the end of the key array, the resulting key byte will be undefined, which gets converted to zero when it's XORed with the decoded byte.  Thus, in effect, for long inputs this code behaves as if the key array was padded with zeros.)

Finally, the resulting 8-bit number is just passed to String.fromCharCode(), which converts it into an ASCII (or ISO Latin 1) character, which then gets appended to the output string.

Thus, this code just decodes the input from hexadecimal into a byte string, and then XORs the bytes with a fixed key.  Now can you reverse it?

Ps. Here's how I'd rewrite the decoder:

var key = [31, 126, 188, 168, 210, 3, 208, 219, 229, 149, 187, 222, 17, 31, 59, 100, 131, 62, 163, 81, 115, 154, 2, 220, 166, 30, 112, 192, 48, 172, 174, 119, 249, 5, 251, 41, 46, 148, 43, 210, 35, 42, 231, 145, 16, 6, 10, 28, 228, 49, 103, 248, 151, 109, 19, 20, 151, 243, 12, 193, 152, 126, 83, 235, 27, 109, 66, 96, 179, 88, 11, 189, 30, 187, 23, 172, 93, 109, 239, 247, 123, 105, 55, 98, 117, 175, 114, 212, 146, 136, 38, 115, 124, 39];

function decode(hex) {
    var len = hex.length / 2, bytes = [];

    // decode input hex string into array of bytes:
    for (var i = 0; i < len; i++) {
        bytes[i] = parseInt(hex.substr(2*i, 2), 16);
    }

    // XOR each decoded byte with the corresponding key byte:
    for (var i = 0; i < len; i++) {
        bytes[i] ^= key[i];
    }

    // convert the byte array into a string and return it:
    return String.fromCharCode.apply(null, bytes);
}

You can check that this gives the same results as your original code, but it's hopefully more readable, and also possibly a bit faster (not that speed really matters for such short strings).


Why programming languages don't provide simple encryption methods?

It's not nearly as simple as you imagine. When you encrypt a string, what character set is it in? What characters are permissible in the output? There are too many unusual combinations of code requirements and security requirements for a "one size fits all" to make sense.

But if you think one size does fit all, sit down and write it. It should take you an hour or so. You'll have it forever, can share it with other people, and this problem will be solved. I think you'll find everyone needs it to be a little different and you'll be right back where we are.

Here's a function to set the character set. Here's a function to switch between hex and base64. Here's a function to add padding. Here's a function to add a checksum. Here's a function to set the key in hex. Here's a function to set the key in base64. And so on, and so on, and so on.

Fundamentally, encryption is not easy. Threat models differ. Requirements differ. One simple "this encrypts" interface is much more likely to be used to disastrous results than good ones.

There's also the attractive nuisance issue -- things that are neither easy nor safe probably should not look easy and safe.


Is the commitment $g^u\cdot x$ with $x\in\langle g\rangle$ and $u \gets \mathbb{Z}_n$ hiding and binding?

The scheme is clearly hiding: the value $g^u\cdot x$ distributes uniformly at random when $u$ is.

However, it is not at all binding: for a given commitment $c$, the sender, assuming he can compute inverse of an element in the group, can find many pairs, more accurately, as many as the size of the group, $u,x$ for which $c=g^u\cdot x$.


Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize?

What you're looking for can be done using existing schemes for format preserving encryption (FPE). In general, FPE schemes convert an existing strong algorithm like AES into a block cipher that operates on a set of any size. For instance, FPE can encrypt 15 digit integers to other 15 digit integers (eg for credit card numbers, one of the common reasons for using FPE). Most of these schemes can be easily adapted for the set [0...2^20), usually with no special changes. For further details see this paper or this wikipedia article.

I assume you're aware that any 20 bit block cipher suffers serious intrinsic weaknesses (eg collisions using it in CBC mode) and have a specific reason for needing a 20 bit permutation.


Combining public key signature schemes and private key encryption

I tried to combine both schemes them by signing the message and then encrypting the signature together with the message. But i struggle with proving that such a scheme is CCA-secure.

I believe that the reason you're running into issues proving that is that CCA-secureness of this system doesn't actually follow from the CPA-security of the cipher and the unforgability of the signature.  That is, you could design a CPA-secure cipher that, with unforgable signatures, that the system is not CCA-secure.

Consider a CPA-secure encryption where the attacker can modify the ciphertext in a way such that the decryption of the modified ciphertext might result in the original plaintext, or might not (and whether it does or not would give the attacker information on the secret key).  CPA-secure allows such a vulnerability, as it doesn't consider modified ciphertexts.

It's fairly obvious how a CCA-attacker would break such a system; they would modify the ciphertext, and give it to the decryption oracle.  The decryptor would first recover the signed plaintext; if it was the original signed plaintext, then the signature algorithm would accept it (because it's not a forgery if it's bitwise identical to a previously signed text), and so the decryption oracle would emit the plaintext.

You could place additional constraints on the CPA-encryption to ensure this doesn't happen.  However, a better approach (both from a provability standpoint, and from an implementation standpoint) is to reverse the order of operations; first CPA-encrypt the plaintext, and then sign it.  I believe you'll find that easy to prove CCA-secure.


Lattice reduction question regarding the capability of LLL and BKZ

Yes, if you instantiate the SVP oracle in BKZ using sieving then the cost is exponential in time and memory. (If you instantiate it using enumeration then the cost is $k^{1/8\,k + o(k)}$). The norm of the output vector is expected to be $\delta_k^{d-1} \cdot \operatorname{Vol}(\Lambda)^{1/d}$ with $\delta_k \approx GH(k)^{1/(k-1)}$. Here $\operatorname{Vol}(\Lambda)$ is the volume of the lattice, and $GH(k) \approx \sqrt{k/(2\pi e)}$ is the Gaussian heuristic for a lattice with volume 1. This does not depend on the norm of the input basis.


How does the squeeze function in the NaCl Poly1305 implementation work?

There are two ideas going on here:

Radix 256 arithmetic with delayed carries.
Here we represent an integer $x$ by $x_0 + 2^8 x_1 + 2^{16} x_2 + \dots + 2^{128} x_{16}$.  In canonical form, the digits $x_i$ lie in $\{0,1,2,\dots,255\}$, but in the Poly1305 computation, we delay the propagation of carries as long as we reliably can in order to save computation, so the $x_i$ might be larger, giving multiple possible representations for each integer $x$ in this form.

Poly1305 reduction $2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}} \equiv 5 x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p$.
We are working modulo $p = 2^{130} - 5$, which has $2^{130} - 5 \equiv 0 \pmod p$ and so $2^{130} \equiv 5 \pmod p$.  The idea is that if we have an integer $x$, we can take its 130 low bits $x_{\mathrm{lo}} = x \mathbin\& (2^{130} - 1)$, and the high bits $x_{\mathrm{hi}} = x \mathbin\gg 130$, so that $$x = (x_{\mathrm{hi}} \ll 130) \mathbin| x_{\mathrm{lo}} = 2^{130} x_{\mathrm{hi}} + x_{\mathrm{lo}},$$ and then do a reduction step by computing $$x \equiv 5x_{\mathrm{hi}} + x_{\mathrm{lo}} \pmod p;$$ i.e., shift/multiply/add.

The two ideas are done simultaneously.  I recommend that you try to work through it yourself from those two ideas, but—spoiler alert!—here's the full gory details if you're still completely stuck:

static void squeeze(unsigned h[17])

On entry, $h$ represents an integer $x$ in radix 256, with digits that may exceed 255 because of delayed carries, as long as they have some bound $B$ so the carries aren't too excessive.
$x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[16] < B$
First, we propagate all the delayed carries and bound each digit by the radix up to 128 bits:
u = 0;
for (j = 0; j < 16; j++)

Loop invariants:
$x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[j] < 256 \\
h[j + 1], \dots, h[16] < B$

    { u += h[j]; h[j] = u & 255; u >>= 8; }

Now $h[0], \dots, h[15]$ are reduced, leaving us with $h[16]$ and a 128-bit carry.  We'll go two bits further to get a 130-bit carry:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u) \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < B$
u += h[16]; h[16] = u & 3;

Now note that $2^{130} \equiv 5 \pmod p$.  So—after we shift $u \gg 2$ below—when we have
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 2^{130} u \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
we can reduce $x = h[0] + \dots + 2^{130} u \equiv h[0] + \dots + 5 u \pmod p$.
u = 5 * (u >> 2);

Now we can add $5 u$ starting at the first digit, and propagate the carries:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] + 5 u \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
for (j = 0;j < 16;++j)

Loop invariants:
$x = h[0] + 2^8 h[1] + \dots + 2^{8j} (h[j] + u) + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$

    { u += h[j]; h[j] = u & 255; u >>= 8; }

Now we have a 128-bit carry again, but there's plenty of room because $h[16]$ is only two bits at this point, from the above h[16] = (u & 3).
$x = h[0] + 2^8 h[1] + \dots + 2^{128} (h[16] + u)
h[0], h[1], \dots, h[15] < 256 \\
h[16] < 4$
u += h[16]; h[16] = u;

Finally, $h$ again represents an integer in radix 256, with digits that are bounded by the radix:
$x = h[0] + 2^8 h[1] + \dots + 2^{128} h[16] \\
h[0], h[1], \dots, h[16] < 256$
However, it is not necessarily the least representative modulo $p$.  For that, we need to freeze; squeeze just propagates a batch of delayed carries and does a single reduction step so there's room for more arithmetic.
(Figuring out what $B$ is and setting corresponding bounds on the carry $u$ in each step left as an exercise for the reader.)

Also, if I would want to change the radix here, say from 2^8 bits to 2^16, would that require me to change the above mentioned fragments? I would need to change al the 8's to 16, and the 255's to 2^16-1, but would that be it?

The array $h$ represents the integer $x = h[0] + 2^8 h[1] + 2^{16} h[2] + \dots + 2^{128} h[16]$ on entry, and $x - (2^{130} - 5) k$ for some $k \geq 0$ on exit after the reduction step where we replace $2^{130} u$ by $5 u$.  (Casting out $2^{130} - 5$'s.)
If you want to change the radix, say from $2^8$ to $2^{17}$, then the array $h$ will instead represent $x = h[0] + 2^{17} h[1] + 2^{34} h[2] + \dots + 2^{119} h[7] + 2^{136} h[8]$.  The goal is to compute the same reduction, $x - (2^{130} - 5) k$ for some $k \geq 0$, but finding multiples of $2^{130}$ to replace by multiples of $5$ for the reduction step will happen at a different digit position, $h[i]$, and a different bit position within that digit or carry, $u \gg j$.
It is an easy exercise to find these positions.  For a simpler exercise, you could try writing arithmetic modulo $2^{31} - 1$ in radix $2^8$, in which you can easily exhaustively test a reduction step for correctness.  I recommend that you carry out this exercise rather than asking pseudonymous strangers on the internet to spoon-feed you answers!


Optimal bandwidth cost for Oblivious RAM

See Theorem 6, page 38-39..

Also, this lower bound ignores any ability of the "RAM" to perform computation. Typically, there are two application scenarios for ORAM:

1) A literal processor communicating along a literal CPU bus to a literal stick of RAM

2) A client communicating over the internet to a cloud server

In the latter case, it makes sense for the cloud server to provide computational resources to 'speed up' the oblivious simulation. Two works have shown how to achieve $O(1)$ bandwidth overhead (pushing the $\Omega(log(N))$ requisite overhead onto the server's computation instead):

1) http://eprint.iacr.org/2014/153.pdf

2) http://eprint.iacr.org/2015/005.pdf

Also, very recent work based on program obfuscation allows you to implement a "one-shot ORAM," i.e. ORAM with a single round of communication and asymptotically succinct space/time for the server:

1) http://eprint.iacr.org/2015/388.pdf

2) http://eprint.iacr.org/2015/406.pdf


What is the difference between honest verifier zero knowledge and zero knowledge?

The intuition behind Zero Knowledge is that the Verfifier should not learn something about the secret. That means, that the communication between the Prover and the Verifier ("Transcript") must not reveal any information about the secret. So, there must exist a Simulator, not knowing the secret, that can falsify the transcript between Prover and Verifier. A "real" transcript and a transcript falsified by a Simulator must be indistinguishable. Thus, "simulate" means that the Simulator simulates the communication between a Prover and a Verifier.

Honest Verifier ZK means, that we can expect that the Verifier behaves honestly according to the specified protocol. That is, he does what the protocol specifies. In "normal" ZK, the Verifier can be malicious.
Example: The Graph 3-Color protocol [1]. An honest Verifier chooses a random edge (as the protocol says). A malicious Verifier may choose every time the same edge.

[1] http://www.cs.cornell.edu/courses/cs6830/2011fa/scribes/lecture18.pdf


Why Rabin fingerprints assumes data is prefixed with a "1" bit?

I think that it was to make sure that the leading zeroes in the data to hash are taken into account during the hash. Without the '1' prefix value, those leading zeroes would make the fingerprint stay to zero.

Without the '1' prefix, the following 2 list of bytes would have the same fingerprint:

[42, 5, 3]

[0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 5, 3]


First off, I am sorry to hear about your circumstances. Unfortunately, the virus that you caught seems to be CryptoWall 3.0 or at least a variation of it. Therefore I am bringing bad news. As stated here it is not possible to decrypt or recover the files without paying these [insert swearword].

This is mainly through the nature of the encryption algorithm used, as the key used to decrypt your files is only known to the creators/distributors of the virus.

For the future, make sure to have backups of all your data on a drive that is not connected to your computer and most importantly NEVER click on links or open attachments from E-Mails when you can't 100% verify the senders integrity.


Which encryption algorithm is sensitive to an attacker having access to it?

I am curious which security algorithms are sensitive to an attacker being able to encrypt whatever they choose to (and see the result).

No algorithm would be considered secure if they could be broken under that assumption.

Also, is there a known guide (or a googleable name) of this property of crypto algorithms?

There's a couple of different names (based on some fairly subtle distinctions); the most common is probably "IND-CPA", which stands for "indistinguishable from random against chosen plaintext attacks", that is, even if the attacker was allowed to submit large number of plaintexts of their choosing and get them encrypted, they still would be unable to obtain any information about the encryption method (it'd still look "random")


Difficulty deciphering the RSA algorithm

You have two problems. The first is that you tried encrypting a value which is too large. If you are doing all your math mod n you have no hope of ever getting a result larger than n.

The second is in tthe implementation. You seem to be working in an environment which treats large numbers as floating points (JavaScript? ) and are not using efficient modular exponentiation.
https://en.m.wikipedia.org/wiki/Modular_exponentiation

24^27 is a fairly large number. It doesn't fit in a normal int or long variable. So you need to either have a special big integer to handle such large numbers. Or Preferably avoid them in the first place by applying the moduls in intermediate steps while calculating the power operation, preventing the nunbers you are handling from getting out of hand.(In full size implementations you need both).


Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard?

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in real cryptographic applications. Later the reduction has been tightened.

The whole progress in researches shows that although there is no full proof for the equivalence but there are some evidences which lead to the believe that there might not be any groups in which computational Diffie-Hellman is easy but discrete logarithm problem is hard.


Is it possible to find the product of two numbers without knowing the two numbers?

In the way you setup the problem the answer is No.

As Charlie can perform $C(A(1),B(b))$.


Stateless user-generated one-time passwords

What you are asking for is demonstratively impossible.

Say you only have some initial shared state, for instance a shared secret key and some values. Now you are asking to disallow a previously used authentication; however without additional state, there is no way that you can even detect that a previous authentication has happened.

So you need some kind of state, even if it is just a simple counter, for instance to identify which one-time-passwords have been used.


I disagree with the @RickyDemer.  The concept of a strong PRF has specific technical meaning and is distinct from a PRF.  This can be verified, say, in the Katz-Lindell textbook or by searching for the terms and looking at the lecture notes and papers that turn up.  An important case where this distinction comes up is with 3-round versus 4-round Feistel networks.  It is also a common exercise to build a PRF that is not a strong PRF.

There is a little variation on usage, as some theoretical crypto papers will only say "PRF" when they mean "strong PRF", but the vast majority distinguish between the terms.


What is the best way to share a shared secret key over HTTPS to be used for HMAC authentication?

HTTPS itself does not do encryption, it simply relies on SSL/TLS in order to implement some level of security to your communications. The problem lies with the choice of underlying algorithm - SSL 2.0 is already considered insecure due to flaws. Similar (less critical) attacks have also been discovered for SSL 3.0/TLS 1.0 so you can only fully trust HTTPS if you know what the server AND client (browser) use behind the curtains.

Generally, the approach for communicating a secret key (read ANY secret key) assumes an effort of asymmetric cryptography (see RSA, for example). So your client would connect and send his (temporarily generated, if you must) public key and receive the secret key encrypted with this. The message can now only be decrypted by his private key which never appears in HTTPS traffic and is, mathematically, hard to figure out. This is, for the most part, the way HTTPS works.

Normally I would advise against reimplementing any sort of crypto but, if you have no control over the SSL/TLS versions the server advertises, I would go for an encrypted secret key exchange inside the session and leave the rest of the traffic as is. Just remember NOT to implement the primitives yourself - any language out there has a number of functions and libraries dedicated to this, including higher-level primitives for simply encrypting a message with little options.

It all depends on your skill and on the security you want to impose inside the system.


How is SPHINCS Hash-based signature "stateless"?

I don't have Goldreich in front of me, however it would appear that he is discussing something rather different from a Merkle tree (at least, as it appears in a hash based signature method).

In those Merkle trees, the trees are built bottom-up, not top-down.  That is, the top nodes don't define the values that the child nodes hold; instead, the top node value is a (oneway) function of the child nodes.  In addition, the value that a node has is potentially public (that is, we don't mind if someone learns it); there is no secret component to it.  The only secrets are the private keys to the one time (or few time) signatures at the bottom of each Merkle tree.

As for the difference between stateful and stateless based based signature methods:

Stateful schemes have a Merkle tree (or tree of trees) with a number of one-time signatures at the bottom; each one-time signature can be used (you guessed it) once; hence the signer needs to keep track of which ones he has used; that is, when he uses a one-time signature to sign a message, he must update his state.
Stateless schemes (such as Sphincs) has a large tree-of-trees; but at the bottom, they have a number of few time signatures (Sphincs uses HORST); each such few time signature can sign several messages.  So, when Sphincs signs a message, the signer picks a random few-time-signature, uses that to sign the message, and then authenticates that through the Merkle trees up to the root (which is the public key).  Since we are using a few-time signature, we don't mind if we pick the same few-time signature multiple times on occasion; the few time signature scheme can handle it.  And, since we don't need to update any state when generating a signature, this is considered "stateless".


There is not much reason behind this particular number, but I think that the AES cipher stands as an example. By the time of its selection as AES, Rijndael-128 had 7 out of its 10 rounds broken, though for the 7-round attack it was not clear then if it is better than the exhaustive search. So the security margin was about 30% that time. Now, as the attacks have de-facto advanced by 1 round only (the biclique attacks have only a small constant advantage factor), it is understood that the security margin was well chosen and it made sense to have it 30%.


How to determine the security in bits of a scheme?

There isn't a single formal standard, because different types of cryptosystems have different attack strategies and cost models.  For each type of cryptosystem, there usually is a standard notion of adversarial advantage: we posit a game the adversary might play, with an idealized version of the cryptosystem, or with a practical realization of the cryptosystem, and the adversary's advantage is how much more probable they are at winning the game with the real cryptosystem than with the idealized cryptosystem.

You can read more how to work with adversarial advantage in Mihir Bellare and Phil Rogaway's book, which goes into far more detail than there is space in the margin of this stackexchange note to fit.  But here's a quick overview of a few examples of the variety of adversarial advantage notions you'll encounter:

With symmetric-key authenticated encryption, the adversary is given a chance to play with devices that encrypt chosen messages and decrypt chosen ciphertexts, called oracles, and they win if either they can distinguish a random string from the ciphertext of a random message, or if they can forge a ciphertext they did not obtain from the encryption oracle that the decryption oracle accepts.  This probability is usually studied as a function of the number of queries the adversary makes to the encryption and decryption oracles, how long the messages can be, etc.

The standard attack strategy is to guess the unknown key correctly and try decryption or forgery with that, but specific constructions might admit strategies with better advantage; any AE scheme worth its salt will come with a theorem about the adversary's advantage in terms of the conjectured advantage of some primitive, like a pseudorandom function family such as ChaCha.
One-time authenticators.  The adversary is just given a single message and valid authentication tag and a verification oracle, and they win if they can produce a single valid authentication tag for another message after some number of attempts.  The forgery probability is usually a function of the maximum message length accepted by the verification oracle and the number of queries to the verification oracle.  The standard attack strategy is to make up an authentication tag uniformly at random, and the forgery probability is $2^{-t}$ if its length is $t$ bits.
Diffie–Hellman key agreement schemes.  The adversary is given a set of public keys $a_i \cdot \xi$ for unknown $a_i$ in some group $G$ and for a standard $\xi$ in some set $S$ with a group action of $G$ on $S$; a set of oracles for computing $\zeta \mapsto a_i \cdot \zeta$ for any attacker-chosen $\zeta \in S$ and each unknown $a_i$; and a set of one-way functions $H((a_i + a_j) \cdot \xi)$ of shared secret $(a_i + a_j) \cdot \xi$ values.  The adversary's goal is to compute any one of the shared secret $(a_i + a_j) \cdot \xi$ values.

The standard attack strategies are more complicated, and references for details in the elliptic curve setting can be found at, e.g., SafeCurves; in the finite field setting, index calculus dominates.  There are qualitative differences for the elliptic curve setting and the finite field setting: for the elliptic curve setting, attacking every one of a batch of targets with Pollard's rho is cheaper than attacking an individual target; for the finite field setting, there's a high precomputation cost for index calculus, after which attacking an individual target is cheap.

How does all this translate into security levels?  We take a concrete estimate of the costs of the best known attack in a sensible cost model, and consider the expected cost of an attack with nonnegligible probability of success, and then usually round to a nice power of two.  For example:

The forgery probability of Poly1305 for a single message of up to $16\ell$ bytes is $8\ell/2^{106}$, e.g. $2^{-97}$ for messages of up to a kilobyte or $2^{-87}$ for messages of up to a megabyte which presumably cost a thousand times as much to attempt as kilobyte-long messages.  We loosely round this to a $2^{128}$ security level since (a) it is well below $2^{-100}$ per block and (b) it depends on the bandwidth of the legitimate user and not on the offline costs an attacker can afford spend.
The expected cost before computing a single Curve25519 discrete logarithm is about $2^{125}$ elliptic curve additions—offline, so not dependent on the legitimate user's bandwidth.  We loosely round this to a $2^{128}$ security level because one elliptic curve addition takes a lot more than eight bit operations.

There is some confusion among some cryptographers about what the best standard attacks are; some disagreement about what cost model to use, how to formalize the costs of precomputation, and how to figure batch attacks into security notions; some uncertainty about how to address loose bounds reducing the security of a composition to the security of its primitives; and so on.

Every now and then spats flare up between academics who have frank exchanges of feelings about these subjects.  Sometimes this is reserved to the review processes of academic publications; sometimes it comes out in position papers and letters to the editor (1, 2); sometimes it is in preprints back and forth; sometimes it is on Twitter.  Whether they ever resolve their differences on the street outside the conference venue is a question I leave to the philosophers.


TL;DR: the official $2^{80}$-something theoretical security of 2-Key Triple DES w.r.t. key search¹ is still practically good enough in most of its many uses in 2020; but security authorities rightly do not condone it in new applications.

"3DES when $K_1=K_3$" is formally known as TDEA keying option 2 in FIPS 46-3 or 2TDEA or 2-Key Triple DES. It is still very common in current (2020) commercial applications, including Smart Cards, and its security is thus an important practical concern.
It's vulnerability to key search depends on many things, the most decisive being:

both components $K_1$ and $K_2$ of the key have been chosen independently and uniformly at random (we assume that, and thus disregard attacks on key derivation);
how many matching plaintext/ciphertext pairs are available for the attack;
whether it is targeted a single key $(K_1,K_2)$, or any of many such key (and then how many, and if the available plaintext/ciphertext pairs share a common block).

Study case 1: single key, little plaintext
With two or three plaintext/ciphertext pairs enciphered under a single key, the best attack I know is brute force², with expected success probability $\approx2^{-112}\,n$ after work² totally dominated by $n$ DES encryptions with incremental keys.
By October 2020, the sizable fraction of the global resources devoted to bitcoin mining is reportedly achieving $144\cdot10^{18}\,\text{SHA256d}/s$, where one SHA256d is two SHA-256 compressions, each doing 64 rounds on a 256-bit state. DES does 16 rounds on a 64-bit state, so I'll count $2\,\frac{64}{16}\,\frac{256}{64}=2^5$ DES for one SHA256d, which gets us to $2^{\approx97}$ DES/year. Thus after a year, the probability of success is $2^{\approx-15}$ or ≈0.003%.
Conclusion: there are few applications where this attack should get a rational decision maker bothered for the near future.
Study case 2: many keys, little chosen plaintext for each
On another extreme, if $m=2^{28}$ (270 million) Smart Cards have been issued with random keys, and adversaries having infected card loading devices managed to obtain ciphertext blocks for the same two or three plaintext blocks encrypted under each key, then they can mount a multi-target attack. It finds an expected $\approx2^{-112}\,n\,m$ keys after work² dominated by $2\,n$ DES operations and $n$ searches of a 64-bit result among a table of $m$ values using roughly $64\,m\,$bits for the portion that needs to be high speed.
Compared to the previous attack, the number of DES operations for a certain probability is reduced by a factor of $m/2$ (down to complexity of $2^{85}$ DES operations), and the bottleneck becomes search.
I can vaguely imagine an IC where a 2GiB table fits, subdivided into $\approx2^{8}$ sub-tables each searched at $2^{28}\,$Hz (3.7ns latency). Throw $2^{24}$ (17 million) such ICs at the task and after a year ($2^{\approx25}\,$s ), it's expected to find $2^{\approx8+28+24+25+28-112}\approx2$ keys, and the probability of getting a least one is high.
Further increasing $m$ may reduce the cost, but much slower than proportionally. With foreseeable technology, it seems the sweet spot is when the table to search fits one IC, and when we increase $m$ we must use a denser memory technology, thus slower for the best technologies available at a given time.
Conclusion: recovery of a few of the many keys can't be summarily dismissed as impossible for well-founded adversaries that design, build and operate custom ASICs. But in a system with the capacity to blacklist cards, that's most likely an acceptable risk.
Study case 3: single key, much plaintext
Here, "much" means up to $2^{\approx32}$ blocks ($32\,$GiB). Even approaching that threshold is not advisable for any 64-bit block cipher anyway. Attacks combining a lot of RAM (like textbook Meet-in-the-Middle for 2DES) and iterated collision search (the practical variant of MitM for 2DES, wich uses little RAM and can be bade "embarrassingly parallel") can reduce the number of DES operations considerably compared to case 1. The standard reference is Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990).
Circa 2012 I tried to determine if that attack had become feasible. My tentative conclusion was that a then unreasonable amount of RAM was needed to get below $2^{90}$ DES operations, even if we ignore a lot of costs, including for communication between the RAM nodes.
This is reexamined by Chris J. Mitchell, On the Security of 2-Key Triple DES (in IEEE Transactions on Information Theory, 2016 and arXiv, 2016). It brings an improvement: for chosen plaintext, using the DES complementation property halves the cost. As in van Oorschot and Wiener, more plaintext does not help much, and the bottleneck is the cost of memory and accesses to it (much like in 2).
My opinion is that this attack still remains (2020) extremely hypothetical, harder than that of case 2 with current technology; but we would have to analyses factors beyond RAM availability (like energy for their operation, and communication costs as tentatively explored in this) to conclusively repel the attack as infeasible in the next 5 years for well-funded adversaries; and I know no such analysis.
Study case 4: many keys, significant plaintext for each
That could be the situation e.g. in a VPN that changes session key regularly, and only limited known plaintext is available for each key.
The above Mitchell reference argues that the total amount of ciphertext necessary for a given probability of finding at least one of the many keys at a given cost is largely independent of how many keys are targeted. As far as I see, we're back to case 3 and it's hardness if we follow Mitchell, and case 2 if we do not.

I did not consider cryptanalytic attacks like linear or differential cryptanalysis, because I've not found that they are applicable to 3DES, even with 2 keys; but that's far from a proof that they are not!

Official status
NIST has deprecated use of DES including all keying variants of 3DES/TDEA. It still mentions that 2TDEA used to offer 80-bit security. The superseded SP 800-57 Part 1 Rev. 4 gave more details:

Determining the security strength of an algorithm can be nontrivial. (..) For 2TDEA, if exhaustion were the best attack, then the strength of 2TDEA would be 56 × 2 = 112 bits. This appears to be the case if the attacker has only a few matched plain and cipher pairs. However, the security strength of 2TDEA decreases as the number of matched plaintext/ciphertext pairs increases. If the attacker can obtain approximately $2^{40}$ such pairs and has sufficient memory and computational power, then 2TDEA can provide an estimated maximum security strength of about 80 bits; if the attacker has $2^{56}$ plaintext/ciphertext pairs, with significantly more memory and computational power, then the estimated maximum security strength would be about 56 bits.

An official French regulation (Référentiel Général de Sécurité version 2.0, annexe B1) explicitly recommends against 2-key TDES for use envisioned after 2020, with mention of insufficient block size and vulnerability to known-plaintext attack of complexity $2^{80}$ (resp. $2^{100}\,$) for $2^{40}$ (resp. $2^{20}\,$) plaintext/ciphertext pairs.  Their $2^{80}$ something is roughly in line with Mitchell's conclusions.
NIST's measure of complexity appears to be DES encryptions, and I guess the same for the French source. Neither gives a reference to the attacks considered.

¹ as opposed to key extraction from physical devices holding keys, thru the like of exploitation of implementation errors, fault injection, micro-probing, DPA, DFA…; and attacks on the mode of operation that do not target key recovery, perhaps by exploiting the 64-bit block size.

² That "embarrassingly parallel" attack can go:

obtain two distinct plaintext/ciphertext pairs $P_0/C_0$ and $P_1/C_1$
for each of $2^{56}$ keys $K_1$

compute $A=E(K_1,P_0)$ and $B=D(K_1,C_0)$
for each of $2^{56}$ keys $K_2$

if $E(K_2,B)=A$ (occurs for one computation out of $\approx2^{64}$ )

if $E(K_2,D(K_1,C_1))=E(K_1,P_1)$, output $(K_1,K_2)$

The first output (if any) is most likely the key, with a probability of the contrary $\approx2^{-16}$ on plausible heuristic grounds.


Picking a nonce in the context of CCM (CTR with CBC-MAC) mode

Yes, if the client and the server use the same key to encrypt their messages (instead of having separate keys for client-to-server and server-to-client communication), then you need to ensure that they cannot ever use the same nonce.

One way to do that would be to, say, let the client use only even nonce values, and let the server use only odd nonce values.  Of course, other ways of partitioning the nonce space are equally possible.


Requiring a "supervisor" key pair and a "user" key pair to decrypt multiple-recipient messages

Have you considered using Shamir's Secret Sharing algorithm?

First, Bob encrypts the message with a symmetric algorithm.  Then, he divides the secret key into four parts using SSA such that it requires three parts to decrypt (a $(3,4)$ threshold).  Bob then distributes one part each to Alice and Mark, and two parts to Jim.

When Alice wants to decrypt, she needs has to have both of Jim's parts plus her part.  If Mark wants to decrypt, he similarly needs both of Jim's parts plus his part.

Alice and Mark cannot collude to cut Jim out of the middle, because they have only two parts between them, and decryption requires three.  And because Jim has only two parts himself, he cannot decrypt the message unless Alice or Mark shares their part it with him.

Finally, Jim can withhold his parts from anyone he no longer trusts.


I need to encrypt an ASCII string [a-zA-Z0-9:] to an ASCII [a-zA-Z0-9]
  string of the same length.

The pigeonhole principle can be used to explain why it is not possible to encrypt every 15-character string from some set of sixty-three characters into an encrypted 15-character string from a set of sixty-two characters.

  I need to encrypt an ASCII string [a-zA-Z0-9:] to an ASCII [a-zA-Z0-9]
  string; it's OK if the encrypted string is slightly longer.

There are a huge variety of ways to do this.
Off the top of my head, I might consider:

replace each ":" in the plaintext with "_"
decode the plaintext string from "base64url" encoding into a series of octets (which probably include some unprintable octets)
encrypt the series of octets using practically any implementation of practically any encryption algorithm, using the secret key that you have (somehow) distributed.
encode the ciphertext octets using any "base32" encoding.
The result is ciphertext that only uses 32 printable ASCII characters, but is slightly longer -- six-fifths the size of the original text if you pick a "length preserving" algorithms, somewhat longer if you pick an algorithm like salted AES encryption with an authentication code.

  I need to encrypt an ASCII string [ A-Za-z0-9-_ ]
  to an ASCII [ A-Za-z0-9-_ ]
  string of the same length.

Forcing the ciphertext to be exactly the same length as the plaintext makes a system less secure than one that has room for an initialization vector, an authentication code, etc.

Ah, the "base64url" character set.
With a character set that is a power of 2,
you can use pretty much any implementation of any "length preserving" algorithm, including the Vernam XOR one-time-pad cipher you mentioned and the Vernam modular addition one-time pad.

To encode a string using a Vernam XOR one-time pad, pull a fresh never-been-used page from your one-time pad.
For each character in your message: decode the character into a 6-bit number 0..63,
XOR that character with the corresponding 6 bits from your one-time pad,
then encode the resulting number (which will also be in the range 0..63),
to the corresponding character in the 64-character set.
Then eat or burn that page from your one-time pad, forcing you to use a different page for your next message.
Other encryption algorithms don't require you to consume your secret key, and so are often easier in practice.

  I need to encrypt an ASCII string [A-Za-z0-9] to an ASCII [A-Za-z0-9]
  string of the same length. I need all these characters in the plaintext, and I can't use any other characters or punctuation in the ciphertext.

Forcing the ciphertext to be exactly the same length as the plaintext makes a system less secure than one that has room for an initialization vector, an authentication code, etc.

Ah, format-preserving encryption with a 62-character set.
Most encryption algorithms -- including Vernam XOR -- don't work with such a restriction.
However, a few stream ciphers including modular addition one-time pad can handle such a character set.

To encode a string using a Vernam modular addition one-time pad, pull a fresh never-been-used page from your one-time pad (or generate the next derived block from your stream cipher).
If your keyblock has been generated by throwing a pair of dice or flipping an array of 6 coins, cross out and ignore any values of 62 or greater,
so we have values 0..61 of equal probability.

For each character in your message: decode the character into a number 0..61,
add that character to the corresponding number 0..61 from your derived block --
subtracting 62 if the result is too big, so the final result is in the range 0..61.
Then encode the final result to the corresponding character in the 62-character set.
Then eat or burn that page from your one-time pad, forcing you to use a different page for your next message.
Other encryption algorithms don't require you to consume your secret key, and so are often easier in practice.

(The GROMARK and Gronsfeld ciphers resemble Vernam modular addition, except using a smaller range of values of 0..9 rather than 0..25 or 0..61, and so are less secure but much easier to use).

(The ROT13 cipher is even easier to use, but provides practically no cryptographic security).

p.s.:
Isn't a SSID typically 32 characters?


I'm considering switching to ECDSA, would this require less space with the same level of encryption?

The answer to that question is yes, both ECDSA signatures and public keys are much smaller than RSA signatures and public keys of similar security levels.  If you compare a 192-bit ECDSA curve compared to a 1k RSA key (which are roughly the same security level; the 192-bit ECDSA curve is probably a bit stronger); then the RSA signature and public key can be expressed in 128 bytes each (assuming that you'll willing to use a space-saving format for the public key, rather than using the standard PKCS format); the ECDSA signature would be 48 bytes, and the public key would be 25 bytes.

As you increase the required security level, the advantage tilts even more radically towards ECDSA; that's because you have to increase the RSA modulus size far faster than the ECDSA curve size to increase the security level.

  And is the verification performance in the same range as RSA?

Well, no, ECDSA signature verification is slower than RSA (for reasonable security levels).  That is the one place that RSA shines; you can verify RSA signatures rather faster than you can verify an ECDSA signature.  According to this web page, on their test environment, 2k RSA signature verification took 0.16msec, while 256-bit ECDSA signature verification took 8.53msec (see the page for the details on the platform they were testing it).  Now to be fair, this isn't quite an apples-to-apples comparison (256-bit ECDSA is probably a bit stronger than 2k RSA), but even if the difference isn't quite 50x, RSA is still faster.

I do have one question, though.  You mention that you are including the RSA public key along with the signed message.  Does that mean that the verifier uses that public key to verify the message?  If so, how do you know that someone who wants to forge a message won't just provide his own public key along with the signature (signed using his private key)?  That is, how does the receiver know that the public key he sees in the message is the one that was sent?


Does the generator size matter in Diffie-Hellman?

The security of Diffie-Hellman depends upon the group in which DH is used, but not upon which generator is used for this group. See note 3.53 (chapter 3, page 103) of the Handbook of Applied Cryptography.

In more details: for DH, we use a subgroup of size $q$ of the integers modulo $p$ (a big prime) with the multiplication as group operation. $q$ should be a prime of length at least $2n$ bits for a $2^n$ security level (or, at least, $q$ should have a prime divisor of at least $2n$ bits). Typical parameter sizes are 160 bits for $q$ and 1024 bits for $p$, or 256 bits for $q$ and 2048 bits for $p$. The generator $g$ is an element of order $q$.

When $p$ is a "safe prime", this means that $\frac{(p-1)}{2}$ is also prime. We then define $q = \frac{(p-1)}{2}$. In that situation, the order of any non-zero $g \bmod p$ (except 1 and $p-1$) is either $q$ or $2q$, hence every $g$ between $2$ and $p-2$ (inclusive) is a fine DH generator and ensures optimal security. Therefore it is customary to select a $g$ which makes computations easier, usually $g = 2$ or $g = 3$.

Another way to define a DH group is inherited from what is done with DSS (a signature algorithm which also works in that kind of group): we first select a prime $q$ of appropriate size (e.g. 160 bits), then we look for $p$ by setting $p = qr+1$ for random values of $r$ of the right size (so that $p$ has the size we need), until we hit a prime $p$. This allows the use of a smaller $q$, thus smaller DH exponents and faster computations; on the other hand, we cannot choose the generator as freely in that case, because there are only $q-1$ generators of a subgroup of order $q$ modulo $p$. So we take a random value $s$ and compute $g = s^{(p-1)/q} \bmod p$. This yields an appropriate generator, but not a small one such as $2$ or $3$.

Why wouldn't everyone use the obvious $2$ or $3$ rather than 256-bit numbers?

A modular exponentiation uses a "square and multiply" algorithm. Using $2$ as generator simplifies the multiplies, but not the squarings, which represent the wide majority of the computation (especially when using window-based optimizations). Using $g=2$ is neat but does not imply that much of a performance enhancement.

Window-based optimization groups multiplications. Basically, you precompute $g^2, g^3 \dots g^{15}$; then, you do the squarings and you multiply with one of the precomputed values only once every four squarings. This is with a 4-bit window, you can have bigger windows; there are possible savings on the window building too. This is why the squarings use more than $\frac{2}{3}$ of the total CPU cost, closer to 80 or 85%. This leaves relatively little to optimize with $g=2$.

Most probably, someone had at some point a fuzzy feeling of a 256-bit number being "more secure" in some unspecified way. I have not seen that personally. Several protocols (e.g. IKE, used for IPsec) use the "Oakley groups" from RFC 2412 (Appendix E) which have $g=2$.


Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations

A possibility is that algorithm A is randomized, but at least one of the following holds

the source of randomness used is poor (e.g. tends to repeat), and using several sets of hash functions fixes that, merely by introducing more of the randomness necessary for accurate results (whatever that means) of the overall procedure.
there is no randomness fed into the input of at least one of the hash functions in a set, therefore changing that hash function adds some of the beneficial randomness.


what is the public information in Elliptic curve cryptosystems

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous).

Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in $\mathbb{F}_p$ and the operations will be made using points on a curve. Then $a$ and $b$ (or the equivalents is uses different notation) is also public and also the equation used. About the generator point $\langle G\rangle$, you can think like public it is in DLP over finite fields.

About the order of the cyclic subgroup of points where the ECDLP is defined is public ($ord(G)=n$), together with the cofactor $h$ (that shall be very small number and both primes, with relation $h \lll n$), and the product of them is the number of points of the curve.

The only thing secret is the secret key, often labelled as $d$, where the public key is $P=d[G]$.


How to put the hash of a PDF file in the PDF file?

You cannot push the hash of a file 'in' the file, as newly modified file will have a different new hash....

As said, it seems that you are asking a way to solve this equation H(∗∗a∗∗∗)=a


Expected Polynomial time Simulator in Interactive ZKP

Simulator does not have access to random bits of Verifier. Expected polynomial time means expected value (expectation from probability theory) of running time is polynomial in problem size. Simulator is a kind of replacement of Prover, exchanging messages in exactly the same way.

Introducing your own definitions is ok, but you will be proving probably another statement (different protocol property) with your definition.


How Multiplication Table is generated for GF(2^2) field

$\mathrm{GF}(2^2)$ is the finite field of 4 elements, and has minimal polynomial $x^2+x+1$. Throughout this question I will use $ab$ to denote $ax+b$ (ie $10=1*x+0$) - this is standard notation when considering finite fields over $\mathbb F_2$ since it aligns with how we consider bits in bytes.

As you have already seen, addition is done by bitwise xor:
$ab+cd := ab\oplus cd$

For multiplication, we do standard polynomial multiplication, but then must reduce by the minimal polynomial. That is, we use the identity that $x^2=x+1$. So:

$$\begin{aligned}
 ab\cdot cd
   &= (a*x+b)(c*x+d)
\\ &= (a * c)x^2+(a* d + b * c)x + b*d
\\ &= (a* d + b * c +  a * c) x + [b*d +  a * c]
\end{aligned}$$
Now, as discussed above + is xor (denoted $\oplus$), and the hint given by your book is that multiplication of the coefficients is the same as an AND operation (which I'll denote with $\&$):

$$\begin{aligned}
 ab\cdot cd
   &= (a\&d \oplus b\&c \oplus  a\&c) x \oplus [b\&d \oplus  a\&c]
\\ &= [a\&d \oplus b\&c \oplus  a\&c][b\&d \oplus  a\&c]
\end{aligned}$$


Advantages using Diffie-Hellman or ElGamal

Diffie Hellman

Diffie Hellman is a key exchange protocol. It is an interactive protocol with the aim that two parties can compute a common secret which can then be used to derive a secret key typically used for some symmetric encryption scheme.

I take the notation from the link above and this means we have a group $\mathbb{Z}_p^*$ for prime $p$ generated by $g$. Party $A$ chooses random $a\in \mathbb{Z}_p^*$ and sends $g^a$ to $B$ and $B$ chooses random $b\in \mathbb{Z}_p^*$ and sends $g^b$ to $A$ and both compute $g^{ab}$ as their common DH key.

Plain (unauthenticated) Diffie Hellman is known to be susceptible to person-in-the-middle attacks and this can be circumvented (as for instance done in TLS) by authenticating Diffie Hellman
either

by including the static Diffie Hellman paramters $(p,g,g^b)$ of one party (the server in TLS) into a certificate which is signed by a trusted authority (where the static parameters stay the same for all key exchanges) or
by requiring the server to sign the ephemeral Diffie-Hellman key, i.e., $g^b$ where $b$ is chosen randomly for every new interaction, sent to the other party (the client). Thereby, the public verification key corresponding to the signing key is put into a certificate which is signed by a trusted authority.

Using a static DH key is in principle very similar to how ElGamal works, but ElGamal encryption is non-interactive.

 ElGamal Encryption

ElGamal encryption in contrast to DH is a public key encryption scheme and may be seen as a non-interactive DH key exchange where the public key of $B$ is $g^b$ and the computed DH key $g^{ab}$ is used as a one-time-pad to encrypt a message $m\in \mathbb{Z}_p^*$ which is a group element of the respective group used, typically the encryption operation is defined as multiplying the message with the DH key, or xoring the message with a hash of the DH key.

The ciphertext is then a tuple $(c_1,c_2)$ consisiting of the message encrypted with the DH key $m\cdot g^{ab}$ and the part $g^a$ of the DH key computed by the encrypting party. But the entire process is conducted by one party, i.e., the party encrypting the message. This party then sends the tuple $(c_1,c_2)=(g^a,m\cdot g^{ab})$ to the receiver $B$.

In a practical setting, ElGamal encryption does not really give a benefit when using it as an encryption scheme as it is, since it does only support message of size of elements of the group being used and parameters must be chosen carefully in order to obtain IND-CPA security (holds always in elliptic curves but you have to choose a suitable subgroup of $\mathbb{Z}_p^*$ to obtain it). However,
 it can be turned into a hybrid encryption scheme. But when one wants to use such a hybrid encryption scheme IES/ECIES is a better choice. ElGamal encryption, when the paramters are chosen in the right way achieves the weaker notion of indistinguishability under chosen plaintext attacks (IND-CPA), where IES/ECIES achieves stronger security, namely indistinguishability under chosen ciphertext attacks (IND-CCA).

ElGamal still has some benefits, which however, are more interesting when using ElGamal encryption as a building block for "larger" cryptographic protocols. For instance:

It is a homomorphic encryption scheme which allows multiplying plaintext hidden inside of ciphertexts and when
using the homomorphic property with an encryption of the identity element $1$ of the group allows to publicly re-randomize ElGamal ciphertexts, i.e., obtain new ciphertexts for the same message which
are unlinkable to the original ciphertexts. Using exponential ElGamal obtained from ElGamal by encoding the message $m$ as $g^m$, i.e., as exponent of the generator $g$, ElGamal can also be made additively homomorphic for polynomial sized message spaces (since decrypting involves computing discrete logarithms).
There are efficient honest-verifier zero-knowledge proofs of knowledge to prove properties of ElGamal ciphertexts without revealing the plaintext, e.g., equality of plaintexts.
ElGamal can be used to construct a threshold cryptosystem, i.e., there are $n$ parties holding shares of the secret decryption key and a ciphertext can only be decrypted if at least $k$ of these $n$ parties are involved in the decryption process but fewer then $t$ parties will fail in decrypting.

DH or ElGamal

  For what kind of usage should we prefer using Diffie Hellman in order to exchange keys instead of Elgmal, and most important why should we use one or the other ?

That heavily depends on your application scenario. For instance, are sender and receiver on line or not? Do you want to simply encrypt data for confidential storage or communicate with some other guy? One feature that can be achieved for confidential communication  when exchanging keys using a key exchange protocol such as DH is forward secrecy, which you will not have when using asymmetric encryption and sending encrypted messages under a fixed ElGamal/IES/ECIES public key to a receiver.


Is FFT for power-of-two cyclotomic rings possible if q is not 1 modulo 2n?

Yes, in a way. When $q \neq 1 \mod 2n$ the ring $R_q$ is not fullt splitting (into polynomials of degree one). However, it might be splitting into several smaller polynomials of degree larger than one. Let $n > d > 1$ be powers of two such that $q$ is a prime and $q \equiv 1 + 2d \mod 4d$, then $X^n + 1$ splits into $d$ irreducible polynomials of the form $X^{n/d} + r_i$ modulo $q$ where $0 < r_i < q$ (see Corollary 1.2 in https://eprint.iacr.org/2017/523.pdf). Then you can use FFT to compute multiplication in $d$ levels, and then do it manually in the end. This can be as fast as full FFT (see e.g. https://eprint.iacr.org/2020/1397.pdf).


What does approved one-way function mean?

They are talking about NIST approved one-way-functions, which they list thereafter (HMAC,  KMAC etc.). They approve those because they are thought to be one-way functions by the cryptographic community (which - for NIST - includes the NSA).

The cryptographic community believes that they are one-way because they conform to an algorithm design that is thought to provide a one-way function. Of course, there also need to be no known attacks that compromise the function (much).

Note that usually the function can be proven to be one way if the underlying primitive - usually a block cipher, hash or sponge- can be proven to be secure. However, it can be shown that it is impossible to prove that.


How to break RSA signature on XOR of hashed blocks

To sign a message $M = m_1 \ldots m_n$, you calculate $h(M) = h(m_1) \oplus \ldots \oplus h(m_n)$ then $S(M) = \textsf{RSASSA}(h(M))$ where $\textsf{RSASSA}$ is some RSA-based signature mechanism. $h$ is presumably a cryptographic hash function. You're looking for a weakness of this signing method.

Start small. Given $M = m_1 m_2$, can you think of another message $M'$ such that $S(M) = S(M')$? (Note that a weakness could be more complicated than this. For example, it could be impossible to find two messages with the same signature, but possible to derive the signature of $M'$ from the signature of $M$. However, in this case, it is possible to forge another message with the same signature.)

   $S(m_1 m_2) = \textsf{RSASSA}(h(m_1) \oplus h(m_2)) = \textsf{RSASSA}(h(m_2) \oplus h(m_1)) = S(m_2 m_1)$

Follow-up exercise (easy): given an arbitrary message $M = m_1 \ldots m_n$, find a longer message with the same signature. Hint:

   Above I used the fact that $\oplus$ is commutative. What other algebraic properties does $\oplus$ have?

The normal way to sign a message $m_1 \ldots m_n$ is of course $\textsf{RSASSA}(h(m_1 \ldots m_n))$. If you also want to be able to verify the signature of one part independently, one solution is to build a hash tree and sign the root hash. A two-level hash tree would be $h(h(m_1) \ldots h(m_n))$. If you transmit the signature $\textsf{RSASSA}(h(h(m_1) \ldots h(m_n)))$ as well as the list of individual hashes $(h(m_1), \ldots, h(m_n))$ then it's possible to verify the signature of any of the individual $m_i$. Signatures are larger than hashes and more expensive to compute, so this can save resources compared so signing each $m_i$ independently.


Does the server signs message body after ssl handshake?

..., is the message body (when my computer decrypts it) signed by server's public key or not?

It's not signed. The "message body" (i.e. application data) is only protected by a HMAC. This HMAC relies on a shared secret known both to client and server created together with the encryption key based on the pre-master secret generated during the key exchange. Given that client and server have both the same key for encryption and the sane secret for HMAC the client might create any encrypted application data itself. This means it is impossible for some third party to figure out if the application data in some packet capture originated from the server or was faked by the client.


How to prove identity in this peculiar case

I think it is the "trust problem" which requires web of trust and therefore is impossible to solve strictly. However it can be in essence solved in a way. Alice first publishes a summary of the book under the name of Alyssa and spreads the word as much as possible. The summary specifies a timeframe under which any identity X can claim to be writing a book with the matching summary. If X exists then Alyssa continues to publicly engage with him/her until sufficient difference arises in the actual specifics of the book. After this period Alice shares her book with Bob. Then if Bob publishes the same book but under the name Bobby the trust would be weak since Bobby didn't spoke up when Alyssa published the summary. The emphasized parts are the weak aspects of this mechanism but can be enough for certain trust threshold.


Correct. Essentially the issue is that you sign a hash of the document, so any other document with the same hash you have also signed.

However, you should not really mix terminology like "decrypts the signature". Signatures are "verified". Even in the case of RSA where the basic operation is similar to decryption, the verification involves other things like different padding that must be checked.


Deduce modulus N from public exponent and encrypted data

Given a message $M$, define the corresponding RSA ciphertext as $C = M^e \bmod N$.  We assume that the value of $N$ is kept secret.  However, the attacker is given oracle access to the encryption: on input a chosen message $M$, the attacker gets backs $C = M^e \bmod N$.

Question: How is possible for an attacker to recover the value of $N$?

Easy case (small exponent) Suppose the exponent $e$ is small (e.g., $e=3$) and known to the attacker.  Then, as detailed by yyyyyyy, given two ciphertexts $C_1 = M_1^e \bmod N$ and $C_2 = M_2^e \bmod N$, the value of $N$ can be obtained from $\gcd(M_1^e - C_1, M_2^e - C_2)$.
General case  Consider now the case where $e$ is large.  The attacker chooses two messages $M_1$ and $M_2$ and forms the messages $M_1' = M_1^2$ and $M_2' = M_2^2$.  The attacker asks for the corresponding ciphertexts and gets $C_i = M_i^e \bmod N$ and $C_i' = M_i'^e \bmod N$(for $i \in \{1,2\}$).  Since $M_1' = M_1^2$, it follows that $C_1' \equiv C_1^2 \pmod N$ and thus $(C_1^2 - C_1')$ is a multiple of $N$.  Similarly, $(C_2^2 - C_2')$ is a multiple of $N$.  As a consequence, $N$ can be recovered from $\gcd(C_1^2 - C_1', C_2^2 - C_2')$.

Remark 1  Note that the attacker does not need to know the value of $e$ to mount the second attack (general case).

Remark 2 Define $\tilde{N} := \gcd(C_1^2 - C_1', C_2^2 - C_2')$.
It might be the case that $\tilde{N}$ is not exactly equal to $N$.  The above description only implies that $\tilde{N}$ is a multiple of $N$.  However, knowing that $N$ is the product of large primes, it can be recovered from $\tilde{N}$ by removing extra small factors.  Yet, another option is to choose more messages and compute $N$ from $\gcd(C_1^2 - C_1', C_2^2 - C_2', C_3^2 - C_3', \dots)$.

Remark 3  There are several possible variants for the second attack.


If I have the unencrypted text and the encrypted text, can I calculate the key?

It depends completely on the encryption algorithm in use - for some little examples have a look below the horizontal rule.

In general, this is called a Known Plaintext Attack. The attacker has access to a message $m$ and its encryption $c=E_k(m)^{[1]}$.
The stronger form of this attack is a Chosen Plaintext Attack (CPA), where the attacker gets to choose $m$ and have it encrypted for him.

Assuming you've observed at least one character, if the encryption is a caeser Cipher then yes: it would be sufficient to recover the key. This is because you can take the difference between the first character of the plaintext and ciphertext to find the key.

However, even with the Vigenère Cipher, which is a slight 'improvement' on the Caeser Cipher, this might not be sufficient. If the key is longer than the plaintext/ciphertext pair you have observed, then you will not learn anything about the latter part of the key.
Similar examples come from thinking simply in terms of information: if you only witness $b$ bits of output, no matter how useful they are you can only learn at most $b$ bits of the key$^{[2]}$. Thus if the key $k>b$ bits long, there is no way $b$ bits of output can be sufficient to discern it.

Notes:

Where $E_k(m)$ is the encryption of $m$ under key $k$.
I assume here that the key is in some sense minimal. That is, the bits of the key are randomly set, and we have no information about the form the key takes. For example, if we know the key is either $0000$ or $1111$, then even though the key is $4$ bits long, it is determinable from $1$ bit.


How is formal analysis of the strength of a round achieved?

diehard is not the answer you're looking for. diehard is a randomness testing tool. It looks at a sample of ~10MB and checks if that sample is  independent and uniformly distributed (IID).  It uses simple statistics not implicit cryptographic experience.  The output is essentially a binary output in that if some p values = 0.00000 or 1.00000 then the sample is not sufficiently IID.  The sequence of p's that you'd get for a sample unequivocally known to be IID is  somewhat a matter of interpretation, feelings and guesswork.   dieharder, it's successor makes this binary choice much more explicit in outputting PASS, WEAK or FAILs.

You could easily produce a 10MB sample from the first round of a Feistel network such as DES. It would probably fail with a series of 0's after the decimal point.  As the round count increases, the p values would start to look reasonable, but not increase any further.  You would learn little of security from this exercise other than that the output is IID. So is 10MB of RC4 when analysed with diehard.

Don't be surprised that key expansion inside some of these primitives is weak.  AES is weakish.  Key expansion is only a part of the entire primitive and their security comes from a sum of the parts.

PS. Colourful language is great, but in this particular instance categorising key expansion algorithms as ridiculous skews the question somewhat.  I think that analysts call them weak, rather than ridiculous.  "Ridiculous" would transfer all the security responsibilities to the main part of the primitive, and imply that any old expansion like ROT13 could be used.


Determining if Server/Client's TLS configuration is Vulnerable to SLOTH

It doesn't seem that openssl is capable of doing this itself, especially against servers that don't advertise RSA-MD5 support but will still accept it (e.g. OpenSSL pre-1.0.1e).
But see https://securitypitfalls.wordpress.com/2016/01/06/testing-for-sloth/ which appears to provide a handcrafted TLS1.2 client that will test for the broken behaviour.  I haven't tested it personally yet, but it looks like exactly the sort of tool that I was looking for to perform exactly the testing you describe.

Thus, to test properly if a server is vulnerable against this attack, we need a client that is misbehaving.
For easy writing of such test cases I have been working on the tlsfuzzer. Just released version of it was extended to be able test servers for vulnerability against the SLOTH attack (to be more precise, just the client impersonation attack – the most severe of the described ones).


Can I publish the accumulator trapdoor and still keep it secure?

I guess you are missing something.

If you know that the accumulator value is $a=v^{\prod_i x_i} \bmod n$ to a set of values $x_i$ and you know the factorization of $n$, then it is easy to for any arbitrary $y$ relatively prime to $n$ (in RSA accumulators you accumulate primes) a value $k$ such that $y\cdot k \equiv 1 \pmod{\varphi(n)}$ as the value $\varphi(n)$ is public. So anyone can pretend that any arbitrary value $y$ has been accumulated using $a^k$ as the membership witness and note that the verification $a\equiv (a^k)^y \bmod n$ holds.  I guess that you would not like to have that "feature".

So either you make the factorization not public (use a trusted setup) or if this is not possible you can go with trapdoor free RSA accumulators (basically by computing an RSA modulus in a way that the factorization is unknown to anybody).


Three-party protocol for multiplication with output privacy

First, I'll assume that parties' inputs come from a multiplicative group. If they're in a ring and you also want multiplication by zero, then things get harder. In that case, the protocol you describe is not secure even in the semi-honest case.

The protocol you describe is already secure in the malicious case.  $X$ gives random $b$ to $Z$ and $bx$ to $Y$. $Y$ gives $(bx)y$ to $Z$, who computes $b^{-1}(bxy)$.

If $X$ is corrupt, he sends some $b$ to $Z$ and $c$ to $Y$. This achieves the same effect on the honest parties as running honestly with input $b^{-1} c$ in the ideal world, so it's simulatable / not an attack.
If $Y$ is corrupt, she gets $c = bx$ from $X$ and gives $d$ to $Z$. The message $c$ from $X$ is distributed uniformly, so this message is simulatable without knowing $X$'s input. Furthermore, $Y$'s behavior achieves the same effect on the honest parties as running honestly with input $d c^{-1}$, so it is simulatable / not an attack.
If $Z$ is corrupt, there's nothing he can do, since all he does is receive messages.
If $Z$ is corrupt and colludes with one of $\{X,Y\}$, then in the ideal world they can deduce the honest party's input in its entirety. So there is nothing to hide.
If $X$ and $Y$ collude, then $X$ sends $b$ to $Z$ and $Y$ sends $d$ to $Z$. This achieves the same effect on the honest party as them running honestly with inputs $1$ and $b^{-1} d$.


Computations in extended finite field p^2

Generally, an element of $\mathbf F_{p^2}$ can be represented as $a+bu$ with $a,b \in \mathbf F_p$ and $u$ a root of an irreducible polynomial of degree $2$ over $\mathbf F_p$. If this polyomial is $X^2+1$, then we have $u^2 = -1$, and in that case it is customary to denote it by $i$ (in an analogy with complex numbers). There is nothing that mandates the use of the polynomial $X^2+1$, however. In your case, PARI/GP uses the polynomial returned by ffinit(821^2), which is the polynomial $X^2+X+1$. Thus the relation to use in your computations is $u^2 = -(u+1)$, and not $u^2 = -1$.

Now, can you force PARI/GP to use the polynomial $X^2+1$? Yes, but remember that the polynomial must be irreducible, and $X^2+1$ is irreducible over $\mathbf F_p$ if and only if $p \equiv 3 \pmod 4$ (prove this!). So it will not work modulo $821$, but would work for example modulo $823$. You do it by providing the polynomial, instead of just the order, to ffgen: u = ffgen(Mod(1,823)*u^2 + Mod(1,823), 'u).

Also, although in this case the primitive $3$rd root of unity $z$ equals $u$, note that it is not true in general.


Who calculates the private exponent $d$ in RSA?

In RSA, the owner of the private key calculates $d$, unless otherwise stated.

In public key cryptography, including RSA:

The public key allows to encipher or/and verify signature.
The private key allows to decipher or/and sign.
Unless otherwise stated it is assumed that the owner/holder of the private key has generated both that private key and the public key, and does not reveal the private key.
In practice, some device (computer, HSM, Smart Card..) and code does that task, perhaps under supervision of some person not the holder/owner of the private key (which might be a computer, sometime not the one used for the generation); this is typically ignored in cryptography, and considered part of computer security.
Unless otherwise stated it is assumed that, somewhat, all public keys get known to all, without alteration or impersonation of who their owner is.
In practice, this is often done using digital certificates.


How likely is it that AES-256 is crackable within 100 years (2120)?

I want to know if AES-256 will be safe throughout our life time.

No one knows that.  Here is what we do know:

A brute force search (by conventional computers) will be totally impossible.  This can be shown by a power analysis of the minimal amount of power used per step (the minimal amount of power to change a state is $kT$, where $k$ is Boltzman's constant circa $1.38 \cdot 10^{-16} \text{ erg/}^\circ\text{K}$, and $T$ is the temperature in Kelvin.  If we assume a computer that's running at cosmic background radiation temperature ($3.2 ^\circ K$), the minimal energy to step a counter though $2^{256}$ keys would be about $5 \cdot 10^{61}$ ergs; the annual output of the Sun is about $1.21 \cdot 10^{41}$ ergs, so unless you can harness a considerably larger output than our Sun within 100 years, this is impossible
A Grover's search (by a Quantum Computer) will also be impossible.  In theory, Grover's could find a 256 bit key in $O(2^{128})$ steps (which is far more achievable than the $2^{256}$ steps in the previous paragraph), it turns out that, to achieve this "low" amount of computation, Grover's search would require $O(2^{128})$ sequential AES evaluations (where you can't start the next until the previous one has completed).  If we assume that our Quantum Computer can't compute an AES function in less than a femtosecond ($10^{-15}$ seconds [1]), then this would take $10^{16}$ years, rather longer than your 100 year deadline.  To meet your deadline of 100 years, you would need to split up the key space into $2^{94}$ parts, and give each part to one of a total of $2^{94}$ Quantum Computers (each one performing AES operations at this completely unrealistic speed).
Cryptographical advancement (that allows an attacker to recover the plaintext without trying all possible keys); this is an open question.  I personally don't expect a total break; that is, something that, given a reasonable amount of ciphertext (and possibly some known plaintext), will allow them to decrypt; I wouldn't be that shocked if someone in the next hundred years found a theoretical break (e.g. $O(2^{150})$ effort given vast mounds of chosen plaintext).  However, this is what people are worried about (as it is easy to see that the other two break methods are totally infeasible).

[1]: For reference, a femtosecond is approximately the time it takes light to travel 0.3 microns; this implies that our AES evaluation engine must be considerably smaller than your average bacteria...


Is there a crypto system doing sqrt during encryption?

I'm not aware of any cipher which uses square root as a primitive operation, and I suspect that none exist. Cipher designers tend to prefer a large number of simple operations to a lesser number of complex ones. The most complex operation used in practice is multiplication, and even that is not extremely common. The most complex mathematical operations I know of used in a cipher are exponentiation and logarithms. From a quote by James Massey on the use of complex functions:

  I have many times used the discrete exponential or the discrete logarithm as nonlinear cryptographic functions and they have never let me down.

There is no reason why a square root operation would need to return a floating point value (for example, in 8-bit integer arithmetic, $\sqrt50=7$, though it's likely that taking the fractional part of the square root would be more beneficial for causing diffusion and promoting nonlinearity), so it is possible to use, technically. It's perfectly possible to return an integer and still achieve diffusion. I have a few guesses as to why no cipher uses square roots as a cryptographic mixing operation:

It's difficult to write a fast constant time implementation, which is necessary to avoid side-channels.
The nonlinear properties it provides are not well-researched compared to other operations.
It is a complex and slow function, and cryptographers often prefer many simple and fast functions.
Unless done in a finite field, it is impossible to reverse the operation (which is often useful).

If you loosen your requirements, then the Rabin cryptosystem may fit the bill. It's an asymmetric cipher and is very similar to RSA, but with the public exponent fixed to $2$. This means that decryption involves computing modular square roots. It's very possible that there is other asymmetric cryptography which makes use of square root operations, but I can't think of any off the top of my head.

If you can expand your requirements to any $n^\text{th}$-root operations, then the broken KN-Cipher from 1995 may be relevant. Its round function is based on the cube root operation in $\operatorname{GF}(2^{33})$. Computing cube roots is also a simpler and faster process than computing square roots.


Using HMAC with AES modes that do NOT require padding

If I understand correctly, your input to HMAC is the ciphertext $c$, padded with null bytes (to a multiple of 16 bytes):
    # pad to a multiple of 16 bytes
    if self._len_ct & 0x0F:
       self._auth.update(bytes(16 - (self._len_ct & 0x0F)))

As a concrete example, suppose the ciphertext is $c=$ deadbeef00, then you will compute the HMAC tag as $t = $ HMAC(deadbeef0000...00), 16 bytes. But this is also a valid HMAC tag for different ciphertexts $c'=$ deadbeef as well as $c' =$ deadbeef000000 etc. I hope you can see why this breaks the authenticated encryption security property.
I'm not sure why you are padding/encoding the HMAC input in this way, but my guess is you are trying to "serialize" both the ciphertext and associated data into a single string that is given to HMAC.  This is a common pitfall for authentication: you want to authenticate a pair of things $(x,y)$, and so you authenticate the string $x \| y$. But many pairs $(x',y')$ get mapped to the same string  $x\|y$ (think of cases where the length of $x$, $y$ are variable)! In order to properly authenticate, you need an unambiguous encoding of the pair $(x,y)$ into a string. One good way would be to somehow include the length of $x$ as part of this encoding.
edit: also you never seem to use self._cipher?


In general, if you draw a sample at random from a distribution $D$, and you apply a statistical test for the null hypothesis $D$ yielding a $p$-value, and you print the $p$-value, rounded to, say, a multiple of 0.05, it is as if you rolled a fair d20 to pick among the possible results.  (For finer granularity, roll a die with more sides.)  That's all that a $p$-value is.

One might hope that the test was designed so that if you sampled from a different distribution $D'$ instead of $D$, an alternative hypothesis, it is as if you rolled a d20 with a weight on one of the faces so that it comes up <0.05 most of the time.  Then if you raise an alarm whenever $p < 0.05$, there's a 5% false alarm rate in your test of the null hypothesis, and a high true alarm rate when there's a problem and you're actually sampling from $D'$.

In the statistics literature, the false alarm rate for a test like this is confusingly called the ‘significance level’; the true alarm rate is called the ‘statistical power’.  The false alarm rate depends only on the null hypothesis $D$, not on $D'$, while the statistical power depends only on the alternative hypothesis $D'$.  A poorly designed test might behave identically on $D$ and $D'$, in which case an alarm means nothing at all about $D'$ even if your ‘significance level’ is 0.05.  (An exceptionally poorly designed test might even have a lower alarm rate under $D'$.)

Typical ‘randomness tests’ like dieharder and the NIST SP 800-22 suite* are collections of statistical tests for a null hypothesis of the uniform random distribution $D$ on bit strings.  They have high statistical power to detect very simple-minded alternative hypotheses like strings of IID bits with 1/4 chance of 0 and 3/4 chance of 1.  They do not have high statistical power to detect alternative hypotheses like strings of $\operatorname{AES256}_k(0) \mathbin\| \operatorname{AES256}_k(1) \mathbin\| \cdots$ for uniform random key $k$.

What really matters in cryptography is how you got your sample.  There are two options:

You got your sample by measuring a physical process like counting ionizing events in a Geiger–Müller tube.  In this case, you should have a specific probabilistic physical model in mind with fancy words like Poisson process: to measure the cryptographic value of this process you need to study the physics and engineering of the process to determine a lower bound on its min-entropy by finding the best way to reliably predict what the output is with the help of teams of trained physicists and engineers.

The NIST tests cannot help you here: they don't know anything about Geiger–Müller tubes.
You got your sample by computing a difficult-to-invert function on a small random input.  In this case, the difficult-to-invert function, like AES-256, should be well-studied by teams of trained cryptographers around the world publishing papers with fancy words like differential cryptanalysis to get confidence that it really is difficult to invert.

The NIST tests cannot help you here: they don't know anything about cryptanalysis techniques.

So what can the NIST tests do?  Not much, really.  They might give you hints about particular nonuniformities in the distribution that lead you to ideas about (1) or (2), that's all.

But, if you want cookie-cutter answers to questions…

  What should be taken for ./assess and How many bitstreams? in this test?

Pass the number of bits in your stream to ./assess.  Specify 1 bit stream.

  In the final Analysis report, what p-values should be there to pass this test?

Always use p < 0.05, unless it's a two-tailed test in which case use $p < 0.025$ or $p > 0.975$.  Beware of green jelly beans.

* Other tools like ent and the NIST SP 800-90B suite fit parameters to model families and compute or estimate the entropy of the resulting models.  Many of the concepts are the same, and likewise these tools are too dumb to know anything about your physical process in (1) or your difficult-to-invert function in (2).


Concatenating a hash function for generating one hash for multiple files

Assuming the hash is collision-resistant (which SHA-256 is believed to be), the proposed practice of hashing the concatenation of a sorted list of hash of files is demonstrably secure against collision (argument: a collision in the final result implies a collision in the last step or/and for some file); so is the practice of hierarchically hashing a binary tree. There's no meaningful difference in security (arguably, accidental collision is more likely in the later; but that's immaterial).

Notice that the proposed practice will give the same hash if files are reordered (which clearly is intentional), or if the content of two files is exchanged while they keep their name (which could be a serious security issue: two packages with the same hash, and the same filenames, can do entirely different things when run).


Attack of an RSA signature scheme using PKCS#1 v1.5 encryption padding

There's an easy attack against public keys with $e=3$.

Here's how it works; the attacker selects an arbitrary message $M$ that hashes to an odd value $H$ (or, more generally, a $H$ of the form $k8^n$ for odd $k$).  Since half of the potential messages hash this way, this is not a severe limitation to the attacker.

Then, the attacker looks for a perfect cube between $2\times2^{1008}$ and $3\times 2^{1008}$ and whose lower 136 bits are $0x00 || H$, that is, a cube $C$ between $2\cdot 2^{1008}$ and $3\cdot 2^{1008}$ and for which $C \equiv H\  (\bmod\  2^{168})$.  Such a cube is easy to find, just compute $x = \sqrt[3]{H} (\bmod \ 2^{168})$ (with the $H$ of the form we selected, such a value always exists), and then select a value $X$ in the range $\sqrt[3]{2\cdot 2^{1008}}$ to $\sqrt[3]{3\cdot 2^{1008}}$ with $X \equiv x\  (\bmod\ 2^{168})$; $C = X^3$ is such a cube.

The value $X$ is be a valid signature for the message that hashes to $H$; the verifier will compute $X^3 \bmod N$ (which will be precisely $X^3$, and then verify that the first two bytes are $0x00$ $0x02$, and that the right hand bytes are $0x00$ $H$.

This attack can be generalized (for this key size) to $e=5$, and can be extended to handle the case where the verifier also checks to see if there are any zero pads in the random pad.


One way of doing this is using a Format Preserving Encryption method.

This is a symmetric encryption method that is designed to convert (potentially) small messages into encrypted messages of exactly the same size.  For example, it may take strings of 13 decimal digits, and encrypt them into strings of 13 decimal digits.

One such method would be the FF3 method from NIST SP 800-38G; if you set radix=10, then it can encrypt a string of 13 digits, giving you a string of 13 digits (which is exactly what you want).

Here is how you would use it in your example: you would take your $N=10$ digit number, and extend it to $M=13$ digits by appending 3 0's.  Then, you'd hand your string of 13 digits (and the key) to the FPE algorithm to encrypt, and it'll give you another string of 13 digits; that's your ciphertext.  Decryption is the the opposite; FPE decryption of the 13 digits, and then strip off the last three 0's (and, if they're not 0, then the ciphertext was invalid)

There are existing techniques for encrypting messages that can't be expressed in an even number of radix digits; however since your messages can, there's no reason to involve those.

All three methods in 800-38G can handle radix=10; I suggest FF3 because the pseudocode listed for FF1 in the NIST draft is wrong (their decryption code isn't an exact inverse of their encryption code; yes, NIST knows this), and FF2 has known (academic) weaknesses.


What would be the most effective way to brute force a 16 char AES key?

Based on the comments, it sounds like you know all the requirements/restrictions on the key. One thing that is not clear is if you have a good way of determining if a trial decryption resulted in the proper plaintext. This is usually not a difficult requirement as most data has some structure you could look for. Another important piece of information you are missing (at least as the question is posed) is what mode was used for encryption.

Once you have a plan for both of the items listed above, a dictionary attack is the best you can hope to do as brute forcing the entire keyspace is infeasible. The process is going to be long, but is fairly straight forward. Pick a few words that are less than 17 characters long together. Pad with punctuation to make it 16 characters. Decrypt. Test to see if decryption resulted in the correct plaintext. If not, repeat. You'll want a methodical way to pick words so you don't repeat, but that isn't hard.


What exactly means to sample from the set of congruence classes?

Sometimes we use to write $a \leftarrow_R \mathbb{Z}_n$ to denote that we are sampling an element from $\mathbb{Z}_n$. But, what exactly means to perform such a sampling?

When we talked about $\mathbb{Z}_n$ we usually consider the least residue system modulo $n$ that is the integers $\{0,1,\ldots,n-1\}$
When we write $a \stackrel r\gets \mathbb{Z}_n$ we usually mean possibly probabilistic process assignment, there are other variants.
When sampling uniformly one should be careful about the random source, simple taking modulus is dangerous and can be biased, discarding is required. Consider your random number generates random numbers in the range $[0,15]$ and you want to sample for $\mathbb Z_{13}$ than taking $\mod 13$ can create a bias since the 13 will map to 0, the 14 will map 1, and 15 will map to 2. Therefore their sampling is more than others, $2/16$ instead of $1/16$. Just discard the numbers $>12$ and get a new random number.
One can use outside of the least residue system like

asked for RSA recently that $e > \varphi(n)$ that will still represent an $e' = e  \bmod \varphi(n) $, or
one can get the private key $k$ in ECC longer than the order $n$ of the base point $G$. It is still useless since $[k]G = [k \bmod n]G$

But the devil in details;  sampling outside may carry some unintended side effects. Always check according to the context!
A further question;

Are we restricted to the least residue system?
Like the adversaries who can do whatever they want that suits their advantage, we can use it, too.

For example, to speed up the gcd we can allow negative remainders.
One may skip a modular reduction step that will cause the number not in the range $[0,n-1]$ and probably higher, Omura '90. In the end, the result must be in the least residue.

In some context, we require the residue as $(n/2,n/2]$ because it forms a ball around the origin and can help to better understand.

For instance, when we want to use ElGamal we write $g^x$, but what we are actually writing? $g^x$ or $g^{[x]_q}$.

First one, since we sample from $[2,q-1]$. When $g^{[x]_q}$ is written it means that the $[x]_q$ can be any of $x+kq$ wher $k \in \mathbb Z - \{0\}$.


A message - strange as it may sound - cannot be encrypted by a block cipher. A block cipher is a deterministic keyed permutation. As it is deterministic, it cannot be a CPA secure cipher: identical messages will result in identical ciphertext, leaking information about the message. This is why ECB mode encryption, which consists of block encrypting subsequent blocks of the message, is insecure. A secure mode of operation - CBC, CTR etc. - and an IV are required to turn block ciphers into secure ciphers.

As there is no way of distinguishing the message from random data the cipher doesn't need to be that secure. It is however still required to use a mode of operation and an IV if the block size is small. Otherwise the block cipher must be relatively large (˜256 bits for large messages) so that repetition of blocks in the plaintext cannot be detected.

If there is even a hint of information on the message (a header or the parity bits of a DES key, a slow starting PRNG, a PRNG started with too little entropy in the seed, a non-secure PRNG etc. etc.) then these kind of schemes will fail spectacularly. The scheme would be brittle to the extreme; if anything breaks or if any info leaks it will crumble. Obviously an attacker should certainly not be allowed to control the plaintext, so the scheme would not be CPA secure.

So yeah, you could reduce the number of rounds or even use a repeated XOR cipher. But the risk of leaking info would be huge.


Whether hash function of two values $h(a,b)=h(b,a)$ are same?

Starting from a normal hash function of $n$ bits $h:\{0,1\}^*\to\{0,1\}^n$, define
$$h(a,b)=h(\;\min(h(a),h(b))\;\|\;\max(h(a),h(b))\;)$$
where $\|$ denotes concatenation of bitstrings, and order of bitstrings for $\min$ and $\max$ is lexicographic.

Trivially, $h(a,b)=h(b,a)$. First premimage resistance is kept. Other security properties (collision resistance, second preimage resistance, security in the Random Oracle Model) need adaptations, but follow from that of the one-argument $h$.

For some uses (including some Proof of Work protocols; see this for more), as well as making proofs stronger/easier, we might need a different inner and outer hash; like
$$h(a,b)=h(\;\;\text{‘1’}\;\|\;\min(h(\text{‘0’}\|a),h(\text{‘0’}\|b))\;\|\;\max(h(\text{‘0’}\|a),h(\text{‘0’}\|b))\;)$$