$G'(x)$ is not a PRG.

I am posting a formalized version of @fgrieu 's example.

Given $H(x)$ PRG we build $G(x)$:

$$G(x) = x_1\mathbin\|H(x_2\mathbin\|\ldots\mathbin\|x_n)$$

$G(x)$ is a PRG:

The expansion requirement is easily shown.

We show that for all $D$ there exists a negligible function $neg$ such that:
$$|\Pr(D(r)=1) - \Pr(D(G(x))=1)| < neg(n)$$

Let $D'$ be an identifier for $G(x)$, we shall build an identifier $D$ for $H(x)$:

$D(w):$

Generate a random bit $b$
Run $D'$ on $b\mathbin\|w$
Return 1 if and only if $D'$ returned 1.

Analysis:

Let $r$ be a uniformly drawn binary string:

$$\Pr(D(r)=1)=\Pr(D'(b\mathbin\|r)=1) = \Pr(D'(r')=1)$$
Where r' is also a uniformly drawn binary string.

$$\Pr(D(H(x))=1)=\Pr(D'(b\mathbin\| H(x))=1)=\Pr(D'(G(b\mathbin\| x))=1)=\Pr(D'(G(x'))=1)$$

Since we assume $H(x)$ is a PRG, there exists a negligible function such that:

$$|\Pr(D(r)=1) - \Pr(D(H(x))=1)| < neg(n)$$
Subtitute the above:
$$|\Pr(D'(r')=1) - \Pr(D'(G(x'))=1)| < neg(n)$$

This proves that $G(x)$ is a PRG.

Now we show $G'(x)$ as defined below is not a PRG:
$$G'(x) = G(x) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$ where $\ell(|x|) = |G(x)|$

Substitute our $G(x)$:
$$G'(x) = (x_1 \mathbin\| H(x)) \oplus (x \mathbin\| 0^{\ell(|x|)-|x|})$$
$$G'(x)=0||(H(x)\oplus(x_2\mathbin\| x_3\mathbin\| \ldots\mathbin\|x_n\mathbin\| 0^{\ell(|x|)-|x|})$$

As shown $G'(x)$ will always start with a 0, so we can build an identifier $T$ that will output 1 if the first bit is 0.

$$|\Pr(T(r)=1) - \Pr(T(G'(x))=1)| = |1/2 - 1| = 1/2$$ which is not negligible, hence $G'(x)$ is not a PRG.


TLS_DH_RSA_* cipher, how can static DH use an RSA certificate?

Look at TLS 1.0 Section 7.4.2, DH_RSA means a DH certificate which itself is signed using RSA by a CA.

The server has a static (long term) DH keypair. The public is included in a certificate and signed by a CA using RSA.

In the handshake, the server sends the certificate which includes the server's static DH public, signed by CA using RSA.

The client verifies the cert chain using RSA like normal, generates an ephemeral DH keypair, performs DH computation against the server's static DH public, computes shared premaster secret. The client sends the client's ephemeral DH public in the ClientKeyExchange.

The server receives the ClientKeyExchange, performs a single DH computation, and computes the same shared premaster secret.

There is no asymmetric encryption or online asymmetric digital signature operation in the handshake - only the DH operation.

This is historic, right? You're not going to use it, right?


Is multi-byte mapping to one byte a viable encryption technique?

You seem to be describing a homophonic substitution cipher, except on bytes instead of letters.  Such a cipher is slightly better (i.e. harder to break) than a simple substitution cipher, but not by much.

To analyze the security of your cipher in more detail, one would need to know how the encryption map is chosen (e.g. is it derived from a key somehow), how many possible encryptions each plaintext byte has and how the encryption of each plaintext byte is chosen.  Still, even without knowing the details, most ciphers of this type tend to be vulnerable to some pretty simple attacks if the attacker can collect enough ciphertext (and possibly corresponding plaintext) to analyze.

For example, if the encryption of each plaintext byte is chosen randomly from among the possible alternatives, this implies that each of the encryptions of a given plaintext byte occurs with the same average frequency.  If the attacker can collect enough ciphertext, they can determine which pairs of bytes occur with approximately the same frequency in the ciphertext, and guess that those are probably alternative encryptions of the same plaintext byte.  (How much is enough depends strongly on what the plaintext is, but a megabyte or two should be plenty for most kinds of data.)  Having done that, they can then attack the cipher using basic frequency analysis, just like one would attack a simple non-homophonic substitution cipher.

Also, if the attacker has access to some ciphertext and to the corresponding plaintext, they can simply compile a partial decryption table by comparing them.  With this method, even a few dozen kilobytes or less may be enough to get a reasonably good coverage of the possible encryptions of most common plaintext bytes.  Armed with such a partial encryption table, the attacker may then be able to partially decrypt other ciphertexts and to use those partial decryptions to guess the plaintext bytes corresponding to other ciphertext byte pairs and thereby extend their table further.

Basically, a cipher like this could be quite a challenging puzzle for an amateur cryptanalyst to break.  You shouldn't rely on it for any real security, though, especially not if you want to encrypt more than very small amounts of data.


Padding Oracle Attack with AES-128-CTR and MAC

Finding the message size knowing the padding size

With CTR mode the length of the ciphertext is the same as the length of the plaintext, because what you do is XORing bit-by-bit the message with the keystream.

So the length of the second component of C minus the padding length and MAC length is the length of the message.

Quick Python example:

import os

# https://cryptography.io
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes, hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

backend = default_backend()

M = os.urandom(200//8)
MAC_KEY = os.urandom(hashes.SHA256.digest_size)
PAD = bytes([0x02,0x02])
AES_KEY = os.urandom(32)
IV = os.urandom(16)

h = hmac.HMAC(MAC_KEY, hashes.SHA256(), backend=default_backend())
h.update(M + IV + PAD)
# truncated to 40 bits = 5 bytes
MAC = h.finalize()[:5]

cipher = Cipher(algorithms.AES(AES_KEY), modes.CTR(IV), backend=backend)
encryptor = cipher.encryptor()
C = (IV, encryptor.update(M + MAC + PAD) + encryptor.finalize())

print('length of message: %i bits' % (8*(len(C[1]) - len(PAD) - len(MAC))))
# out: length of message: 200 bits

Finding the padding size using the oracle

EDIT: added this question from comment of OP.

Another property of CTR mode is that
flipping a bit in the ciphertext flips the corresponding bit in the plaintext.

So if you flip say the last bit of C[1] you will modify the padding and get a "padding error";
while if you flip a bit that correspond to MAC you get a "MAC error".

As a result if flipping the i-th bit gives you a "MAC error"
while flipping the i+1-th bit gives you a "padding error"
then the padding starts at bit i+1 and you gets the padding length and its value.

Continuing my Python example:

class PaddingError(Exception):
    pass

class MacError(Exception):
    pass

def oracle(ctxt):
    decryptor = cipher.decryptor()
    ptxt = decryptor.update(ctxt) + decryptor.finalize()
    m = ptxt[:25]
    mac = ptxt[25:30]
    pad = ptxt[30:]

    # i'm cheating
    if pad != PAD:
        return PaddingError
    elif mac != MAC:
        return MacError
    elif m != M:
        return 'Message was modified'
    else:
        return 'OK'

def flip(x, i):
    "returns x with its i-th bit flipped (starts at 0)"
    mask = 2**(7-(i%8))
    return bytes([ x[j]^mask if j==(i//8) else x[j] for j in range(len(x)) ])

oracle(flip(C[1], len(C[1])*8-16))
# out: PaddingError

oracle(flip(C[1], len(C[1])*8-17))
# out: MacError

Finding the last byte of the MAC

EDIT added from another comment of OP

When you know the padding length, you know where is the last byte of the MAC, and because of the CTR mode you are able to modify it by XORing it against some byte of your choice.

So you pick a random byte and you XOR it against the last byte of the MAC, and you send the result to the oracle.

Normally you should get a "MAC error", but if the modified MAC byte ends up being the same as the PAD bytes (for instance 0x02 in your example) you should get a "Padding error" instead.

Let B be the byte you used to get this "Padding error", we now know that:

MAC[-1] ^ B = 0x02

(where ^ denotes bit-wise XOR as in Python)

Thus:

MAC[-1] = 0x02 ^ B


Decrypt RSA ciphertext with two middle bits leak

This appears to be homework, and so I won't tell your outright; I will give you a hint.

Suppose you compute:

$$c_1 = c \times 2^e \bmod n$$

How are the decryptions of $c$ and $c_1$ related?

Suppose we compute a long series of:

$$c_i = c \times (2^i)^e \bmod n$$

What does the middle two bits of $c_i$ tell us?


Hide message length in symmetric key cryptography

Yes, you can pad the message. As long as you can retrieve the location of the message inside the padded plaintext then you can hide the exact message length.

Note that statistical methods can still be applied; you will have to always create a message size of $N$ if you want to full hide the length of messages of $0$ to $N$ in length - excluding normal padding that may be required for block modes of encryption. Obviously, you still leak the information that the message is lower than $N$. But that cannot be avoided; an encrypted message of size $N$ cannot be created for all messages larger than $N$.

Just adding a padding of random length may not be good enough as you will still leak some data about the message size if you average things out. This paper by Cihangir Tezcan and Serge Vaudenay makes it clear that providing random padding cannot practically hide enough information when a minimum amount of security is required. It still depends on the use case if random (sized) padding is sufficient for a use case, but it should be avoided.

There are several ways of padding that are independent of the message contents, that allow for deterministic unpadding:

include (prefix) the message length with the size, then use any kind of padding behind the message up to the size N of the input plaintext, note that you must be able to parse the length encoding (having a single ASN.1 / DER encoded structure is a special case of this);
perform bit padding, putting a single bit valued 1 and then add zero's untile you reach size N (or, for byte oriented protocols, use a byte valued 0x80 or 0x01 depending on the bit order within the bytes - usually big endian / 0x80 is used);
end the padding with a padding length indicator, retrieve it and remove the bytes (possibly validating the intermediate bytes, depending on the scheme).

The advantage of using the length of the message is that you can skip decryption of the last part of the ciphertext. But note that this doesn't work for authenticated encryption with one authentication tag, and that not decrypting the last part may leak the size of the plaintext through side channel attacks.

The disadvantage of bit padding is that you may need to go all of the decrypted bytes until you find the set bit (or the byte with the single bit set), starting at the end of the decrypted bytes.

Note that you'd need at least one bit or byte for the bit padding method or space enough to store the length encoding. It is impossible to create a deterministic unpadding method where the size of the message M is identical to N and the message itself cannot be used to determine the size.


What implementation properties of a hash function prevent safe truncation?

You really should never be truncating a hash.  Really you're talking about the difference between traditional hashing algorithms and cryptographic hashing algorithms.  A cryptographic hash algorithm has to not be predictable, while a traditional hash algorithm doesn't have that concern.  You aren't guaranteed perfect random distribution, so really you shouldn't ever be truncating a hash in any situation.

Could you specify a situation where people "feel comfortable truncating a SHA2 hash"?  I don't know what you're referring to.


Homomorphism with subtraction for Pedersen Commitment

You used the wrong modulus when verifying the result.

Note that although the computation is modulo $p$, i.e. you compute $g^xh^r \bmod p$, the exponents $x,r$ are in $Z_q$. And so the operations among the exponents are modulo $q$. That means, after the homomorphic operation, you get a commitment of $x_1-x_2 \bmod q$, not $x_1-x_2 \bmod p$ .


Can you decrypt all messages if a private key is obtained of one of the two entities in asymmetric encryption?

If they both use public key encryption to encrypt messages (think e-mail + GPG for example) than obtaining Alice's private key would allow you to decrypt only messages sent to her from Bob. To decrypt messages sent to Bob you need his private key. This of course assumes that there were no plain-text copies of messages in the same place where attacker obtained Alice's private key.

In case they use some chat-like protocol (e2e encrypted messenger) and they use their private keys to set some session keys things are different. When Eve has Alice's private key she can read all messages sent in either direction after she obtained key and potentially all past messages (again, in either direction) if protocol used has no forward secrecy


Why does OpenSSL append extra bytes when encrypting with aes-128-ecb?

First, your use of 'echo' gets you:

~ % echo 'Attack at dawn!!' | hexdump -C
00000000  41 74 74 61 63 6b 20 61  74 20 64 61 77 6e 21 21  |Attack at dawn!!|
00000010  0a                                                |.|
00000011

Note that there are 17 bytes there, not 16. echo adds a newline character. To stop that, use the -n flag:

~ % echo -n 'Attack at dawn!!' | hexdump -C
00000000  41 74 74 61 63 6b 20 61  74 20 64 61 77 6e 21 21  |Attack at dawn!!|
00000010

If you use the -v flag with openssl enc, it will tell you how many bytes were read:

~ % echo 'Attack at dawn!!' | openssl enc -v -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt -out out.bin
bytes read   :      17
bytes written:      32

So that would have been an indicator of something being wrong. The echo problem isn't the only one, though; we still have two blocks of output despite only having one block of input:

~ % echo -n 'Attack at dawn!!' | openssl enc -v -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt | hexdump -C
bytes read   :      16
bytes written:      32
00000000  37 96 93 88 4e 25 f0 0f  6e 8a aa 43 df 4d b5 41  |7...N%..n..C.M.A|
00000010  8e 64 ce 87 3f 17 4d bb  24 23 fc d8 14 58 0e 15  |.d..?.M.$#...X..|
00000020

The second issue is that OpenSSL uses PKCS#7 padding to ensure there are full blocks. In this padding scheme, padding is always applied. So, in the case of a full input block, another full block of 0x10 bytes will be added as padding, which means you'll have two blocks of output (which is what you see above).

The -nopad option for openssl enc disables padding (but it will throw an error if your input isn't a multiple of the block size):

~ % echo -n 'Attack at dawn!!' | openssl enc -aes-128-ecb -K 6162636465666768696a6b6c6d6e6f70 -nosalt -nopad | hexdump -C
00000000  37 96 93 88 4e 25 f0 0f  6e 8a aa 43 df 4d b5 41  |7...N%..n..C.M.A|
00000010


Which Diffie-Hellman Groups does TLS 1.3 support? And should we use TLS 1.3 as a guide?

(1) I'm curious whether the following 10 different DH Groups are the only groups that TLS 1.3 supports,

Yes, in the sense that TLS 1.3 only allows groups that are explicitly declared as supported in 1.3. This currently includes not only the groups from RFC 8446, but possibly more recent RFC as well, such as Brainpool curves from RFC 8734.
The TLS supported groups registry lists all the groups, but unfortunately it doesn't distinguish between protocol versions (you have to chase this information down in the RFC given as references). The “recommended” column is specifically about TLS 1.3, but it is neither a minimum supported set nor a maximum safe set (you can have good interoperability even without the full “recommended” set, and the non-recommended set includes both acceptable things such as FFDH and bad things such as 160-bit elliptic curves).

(2) and as such, are they the only ones that we should be using?

You certainly shouldn't be using other groups in TLS 1.3 since they wouldn't comply with the protocol. Your software isn't likely to support other groups in TLS 1.3 anyway.

(2) To elaborate on my second query: Given that TLS 1.3 was developed over years by experts, and that it only supports certain cypher mechanisms - can we take that to mean that these are the only mechanisms that should be used?

No: it's ok to use other mechanisms in older versions of the protocol. Not every mechanism that is safe to use made it into TLS 1.3. Some mechanisms that are safe but don't have any practical advantage (faster, smaller code, smaller message size, etc.) didn't make it into TLS 1.3. One of the goals of TLS 1.3 was to reduce the complexity of the protocol, which means fewer choices.
With TLS ≤1.2, you need to balance security (as in: risk of implementation bugs, known protocol weaknesses, or yet undiscovered protocol weaknesses) with interoperability. (This is true with TLS 1.3 as well, but 1.3 hasn't been along for long enough to have interoperability problems when it goes through at all.) Due to the number of existing options and the diversity of the existing software, there's no single right answer for where to put the balance.

Some discussion into what curves should be used has already taken place here, which mentions that secp256r1 and secp384r1 are best.

That discussion was in the context of TLS 1.2, which didn't support the same curves. There's no reason to reject any of the curves supported in TLS 1.3 except maybe secp521r1, which is susceptible to implementation weaknesses. (As the name hints, secp521r1 involves 521-bit numbers – and yes, it's 521 and not 512. Because this is slightly larger than a multiple of 64, there's a non-negligible chance that certain intermediate numbers will have the most significant word be 0, and insufficiently protected implementations might leak that fact when the number is multiplied because the multiplication will be slightly faster. This leak can be enough to allow an attacker to reconstruct the private key with a moderate number of connection attempts.) Curve25519 is perfectly fine and arguably preferable to secp curves because it's easier to implement securely. Back in 2015 it was not commonly supported in TLS, but in 2021 it's a standard part of TLS 1.3. Curve448 is slower and has no particular advantage (barring yet unkown weaknesses in other curves), but it's ok to use it.
For finite-field Diffie Hellman, don't use groups smaller than 2048 bits. Older versions of TLS allow custom groups, and there's no consensus on whether to make use of that. On the one hand, using standard groups might allow an attacker with sufficient computing power (read: NSA) to precompute a very large number of values which then makes attacks feasible. On the other hand, generating good custom groups is slow and hard, and doing that risks creating vulnerabilities that are easier to exploit, such as letting a man-in-the-middle persuade the participants to use a weak group. This is why TLS 1.3 mandates the use of known good groups.


Reasoning about WebCrypto ECDSA choices: P-256/384/521, SHA-1/256/384/512?

Don't use SHA-1.

There's unlikely to be a substantive difference between the other choices, as far as you're concerned, except performance:

SHA-256 is might be cheaper on 32-bit CPUs; SHA-384 and SHA-512 are cheaper on 64-bit CPUs.
NIST P-256 is likely to be cheaper than NIST P-384 which is likely to be cheaper than NIST P-521.

All of these choices provide at least a 128-bit security level.

ECDSA is generally dangerous, of course, because implementations tend to require an entropy source when making signatures, with a catastrophic failure mode, unless you can positively confirm that your implementation uses RFC 6979 deterministic signatures.


Probabilistic polynomial time algorithms in MAC's

From my understanding, a probabilistic polynomial time algorithm is
  one that runs in polynomial time, and returns a probability.

Sadly, no. A probabilistic polynomial time algorithm is an algorithm that runs in polynomial time and may use (true) randomness to produce (possibly) non-deterministic results.
The "probabilistic" in the name comes from the fact that one can only predict certain outcomes with a certain probability. For example an algorithm that takes no input and simulates a coin-flip, would be such a probabilistic algorithm, as it's not sure (before evaluation) what the outcome will be, either head or tail?

In the concrete situation, only the key-generating algorithm must be probabilisitc (i.e. use randomness).
The tag-generating algorithm may use randomness but may also decide not to, HMAC for example is deterministic, while other MACs may not be. In either case, saying they are "probabilistic" doesn't hurt and gives the algorithms more freedom.
The verification algorithm on the other hand, must be fully-deterministic as you always want the right answer to the question "is this tag valid in this context?". However, it's still a probabilistic algorithm that just happens to never use the randomness it is allowed to use.


How would you find the Blinding factor R in RSA blind signature algorithm?

You don't “find” the blinding factor. It is picked randomly before starting the computation. The whole point of blinding is to use a random value in the computation and to perform the computation in such a way that this random value affects intermediate values but not the final result.


How many 12 bit integers output are required to reverse the Mersenne Twister?

How many of these outputs do i need to predict the future sequence?

Well, to recover the RNG state, you need to observe 19968 bits of output (which translates into state); by seeing 12 bits at a time, you'll see enough after 1665 outputs.

One question you might have is: the 12 bits might not come from consecutive Mersenne Twister outputs, so we won't be able to trivial reconstruct the 624 word state.  This is true; however Mersenne Twister is completely linear in GF(2); hence we can describe the 19968 bit initial state as a linear function of the observed output states, and (with enough linear equations), solve for the initial state.  This is obviously more work than the trivial 'here's one intermediate 624-word state'; however it is practical.

The other thing to note is this estimate assumed that the initial state was completely unknown.  If it is partially known (e.g. the initial state was 256 bits of unknown values, followed by a known pattern), this reduces the number of outputs that are needed (because those known initial state bits give us free equations)


Computing inverse of BN256 G2 point in golang x/crypto/bn256 library

Actually, computing an inverse of a point (that is, the inverse of X is the point Y such that X+Y is the identity) is quite easy.

For a curve in Weierstrass format with characteristic > 3 (which bn256 is), the inverse of the point (x, y) is the point (x, -y).  That is, you compute the negation of the y coordinate (which, in this case, is modulo $p$ the characteristic of the curve, as it's a prime curve).

BTW: you stated that you "don't have the time right now ... to learn the basics"; if you want to do anything with Elliptic Curves, I would suggest you take the time (the basics shouldn't take several semesters...)


What advantages does Keccak/SHA-3 have over BLAKE2?

(Disclosure: I'm one of the authors of BLAKE2, but not BLAKE.)

Here are the slides from a presentation I gave at Applied Cryptography and Network Security 2013 about this. (Note: the performance numbers in those slides are obsolete — BLAKE2 is even faster now than it was then.)

The slides include quotes from NIST's 3rd-round Report on the SHA-3 Competition which show some of the advantages and disadvantages of BLAKE (not BLAKE2) compared to Keccak, in NIST's opinion.

Here's a blog post I wrote to accompany the slides.

The main reason that NIST gave was that BLAKE was more similar to SHA-2 than Keccak was. When the SHA-3 contest was designed, the whole point of it was to provide a new hash function that would be ready in case SHA-2 got broken, so it made sense to require the winner to be different from SHA-2. However now, with almost a decade more of research and SHA-2 looking no weaker, a hash function being similar to SHA-2 doesn't seem bad, and might even be good.

There was another reason that NIST gave that I omitted from the slides, which was that Keccak is more efficient in ASIC implementation.

That reason may be more important if you are a large organization, like the U.S. military or U.S. government, who is going have special hardware built for your project, but more flexible/general-purpose performance is more important to me. (See Adam Langley's blog post on this topic.)

Besides, everything is fast in hardware! See this catalog of hardware implementations of secure hash functions. ASIC implementations of BLAKE can process about 12.5 GB/s, compared to Keccak, which can process about 44 GB/s. An ASIC implementation of BLAKE2 would be probably about 40% faster than a similar implementation of BLAKE, i.e. around 17.5 GB/s.

But even 12.5 GB/s seems more than sufficient for most uses of a secure hash function.


Most of these algorithms (i.e. the block ciphers DES, Triple DES, AES, Blowfish) are normally only working on a fixed block size, and take approximately the same time independently of input, thus they are $O(1)$.

If you put them into a mode of operation to encrypt longer messages, you usually get an $O(m)$ complexity, where $m$ is the message size, as you have $O(m)$ blocks of data to encrypt.

(One could design modes of operations with different complexity, but they have to touch at least each input bit once to be reversible, thus $O(m)$ is a minimum. Also, with $O(m)$ block cipher calls you can do enough to make it secure, so there is no point of making it slower.)

Two more notes to specific ciphers:

Yes, Triple-DES usually needs thrice the computing power as DES, but this then becomes $O(1)$ or $O(m)$, too.
Blowfish is known for its quite slow key schedule (which takes as long as encrypting about 4 KB of data), but this is still $O(1)$.

Thus, $O$-notation is not really an interesting thing to look at in block ciphers.

It gets a bit more interesting when we look at algorithms with a varying input size. For the asymmetric algorithm RSA, we have the public (and private) key modulus $n$, and its size $k = [\log_2 n]$ in bits can be considered a security parameter. (The private exponent $d$ is of similar size, while the public exponent $e$ is usually some small number like $3$ or $65537 = 2^{16}+1$.) The message size is then limited by $O(k)$, too.

Encryption and decryption are both modular exponentiations of plaintext or ciphertext modulo $n$, with the respective exponents. With the square-and-multiply algorithm, encryption needs $O(1)$, decryption $O(k)$ multiplications and a similar number of modular reductions, each of $k$-bit or $2k$-bit numbers ... which means about $O(k^2)$ or $O(k^3)$ elementary operations (with a quite small factor, as you use the word size build into your processor).

Decryption can be sped up by storing the factors of $n$, but this still gives only a constant factor, I think (i.e. it reduces the $k$ in the formulas).

RSA also uses one of various padding schemes, but this should be in O(k) and thus not contribute to the complexity.


Collision resistant functions - definition

Let the range $Y$ of the function $f$ have size $N$ A collision resistant function cannot be better than an ideal function which maps uniformly into $Y$ since collision probability is minimized by the uniform distribution. Thus, given $(x_0,f(x_0))$ the number $k$ of random points $x_i\neq x_0$ that must be tried before the probability that $f(x_i)=f(x_0)$ is significant, say at least $1/2$ is $k\approx \sqrt{\ln 2 N}$ by the birthday paradox.

If necessary see @fgrieu's detailed post on the mathematics of the birthday paradox here.


Shamir's Secret Sharing of modular inverse

I'm assuming $q$ is prime.

Note that $k^{-1}\equiv k^{q-2}\bmod{q}$.

We can compute $k^{q-2}\bmod{q}$ via a multiparty computation protocol such as the one outlined in this paper ($\S3.1)$. Or, since $q$ is likely a public parameter, you can even do the simple square-and-multiply algorithm (for example, VIFF provides this capability).

You might also be able to compute the modular inverse via the extended euclidean algorithm implemented using general MPC techniques. The reason I say might is that the extended euclidean algorithm does have a conditional branch in it. While this is technically not a problem for MPC, it could leak information in the real world that you wouldn't want to leak.


In the example you mentioned, you must have an honest verifier, because a dishonest verifier would be able to extract the witness (see).
It is important to remark that there are transformations from honest to dishonest protocols, therefore studying honest protocols makes sense in practice. You may find this useful.


Is there any more information on this RSA backdoor?

Actually, if the RSA key generation is malicious, there are even more subtle ways that can someone can leak the key.

The cleverest way I've seen works like this (assuming that we're generating an RSA-1024 key; for RSA-2048, we just use a larger curve):

The attacker generates an EC public/private key pair; using a 192 bit curve for RSA-1024 is good.  He keeps the EC private key secret; he'll install the EC public key into the program below.
To generate a key, the program selects a random 192 bit seed $R$.
It uses that seed to see a process that selects a random 512 bit prime $P$.
It encrypts the seed $R$ using the EC public value (perhaps using EC-ElGamal), resulting in a 384 bit value $E$.
It then selects a 512 bit prime $Q$ with the constraint that $Q \equiv P^{-1}(2E+1) \pmod{2^{385}}$
The product $PQ$ is the RSA modulus (and the rest of the RSA key pair is generated normally)

Then, the attacker can easily factor this RSA key (by extracting $E$ directly from the bit pattern of the RSA modulus, using the EC private key to decrypt it resulting in $R$, and then using R to recover $P$.  And, no one without the EC private key has any advantage to factor this, even if they know the exact procedure used to generate the RSA key; both $P$ and $Q$ were chosen fairly, and the additional constraints on $Q$ do not help the attacker at all.

The moral of this story: if the attacker can control your RSA key generation process, you may have no security.


Definition 3.1 : Let $\pi_S:\{0,1\}^m\rightarrow \{0,1\}^n$ be a S-box. Consider an (ordered) pair of bitstrings of length $m$, say $(x,x^*)$. We say that input XOR  of the S-box is $x\oplus x^*$ and the output XOR is $\pi_S(x)\oplus\pi_S(x^*)$.
Now, the point of confusion is how can the output of the S-box be separated as $\pi_S(x)\oplus\pi_S(x^*)$ when the input is $x\oplus x^*$?

The crux of your question is above. Differential cryptanalysis is a chosen plaintext attack.
The attacker presents the Sbox (more generally the full cipher) with two sets of chosen plaintexts with a chosen difference $d$
$\{u_i: 1\leq i \leq N\},\quad \{u_i\oplus d: 1\leq i \leq N\}$
and computes the set of output distributions corresponding to this input difference
$\{\pi_S(u_i)\oplus \pi_S(u_i\oplus d):1\leq i \leq N\}.$


I have never met this, but it can still be analyzed in the framework of Linear Feedback Shift Registers, and is unsafe as a key stream generator.

I'll assume that $2^{\mathtt L-1}\le \mathtt{TAPS}<2^\mathtt L$. The operation state = tick(state) then is the normal operation for a Fibonacci LFSR with the binary polynomial $Q(x)$ of degree $\mathtt L$ defined by the bits set in the integer $2\cdot\mathtt{TAPS}+1$.

The addition of state = state ^ (1<<k[i%C]) turns that into a different beast, in particular the state now includes $\mathtt i\pmod{\mathtt C}$, sort of extending the state from $\mathtt L$ bits to $\mathtt L+\log_2\mathtt C$ bits.

However, the transformation corresponding to $\mathtt C$ steps leaves $\mathtt i\bmod \mathtt C$ unchanged, and is a linear transformation of $\mathtt{state}$. For moderate $\mathtt C\cdot\mathtt L$, blindly applying a good tool based on the Berlekamp–Massey algorithm on known output will allow prediction of the rest, without any description of the system.

Update: At step $\mathtt i$, $\mathtt{state_i}$ has bits sets as per the coefficients of the remainder of the division by polynomial some appropriate reduction using $Q(x)$ (defined above) of the sum of two polynomials:

$x^\mathtt i\cdot S(x)$ where $S(x)$ corresponds to bits set in $\mathtt{state_0}$, as would be the case for a normal LFSR;
$\sum_{\mathtt j=0}^{\mathtt i-1}x^{\mathtt{k[}\mathtt j\bmod\mathtt{C]}+\mathtt i-1-\mathtt j}$, corresponding to the effect of state = state ^ (1<<k[i%C]).

To answer an additional question: in general, $\mathtt{k[]}$ can not be reconstructed from $(\mathtt{TAPS}, \mathtt L, \mathtt C, \mathtt{state_0})$ and a single $(\mathtt i, \mathtt{state_i})$. When $\mathtt C>\mathtt L$ an amount-of-information argument shows that we do not have enough input. And even for $\mathtt C\le \mathtt L$ there can often be several solutions.


(How) Is DDH generally broken in groups of composite order?

The claim is completely false.

The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few years later to prime order curves. More generally, relying on composite order elliptic curves is actually the standard approach in various subfields of pairing-based cryptography when a feasibility result must be established (see e.g. this IBE), since it is usually much simpler to get feasibility results there. The choice of prime-order elliptic curves is not motivated by security, but by efficiency, since a composite-order modulus must be huge in general.

Even outside of elliptic curves, DDH can be fine over a composite order group - for example, one of my paper proves, in the appendix, that DDH holds over the subgroup of $\mathbb{Z}^*_n$ of elements whose Jacobi symbol is one, which is a composite order group, assuming that DDH holds over the subgroups of squares of both $\mathbb{Z}^*_p$ and $\mathbb{Z}^*_q$ ($q$ and $p$ are the prime factors of $n$) together with the quadratic residuosity assumption. This is one of many examples, it is in fact very easy to build many composite order groups in which DDH holds, assuming DDH in prime-order subgroups of this group.

I have no idea why this claim was made in your lecture; the only things that comes to mind is that if the modulus contains small factors, then there is a straightforward CRT attack where you project onto the small groups. For example, DDH does not hold over $\mathbb{Z}^*_p$ itself, since it's a group of even order, so you can project a DDH instance to a subgroup isomorphic to $\{-1,+1\}$ (this is equivalent to distinguishing by computing the Legendre symbol, as you correctly observe).


How robust is discrete logarithm in $GF(2^n)$?

Discrete logarithms in $\mathbb{F}_{p}$  share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function Field Sieve.

So, extrapolating from the factoring records, we can handwave that a discrete log in $\mathbb{F}_{2^{1021}}$ is an order of magnitude easier than a discrete log modulo a 768-bit general prime, and about the same as modulo a pseudo-Mersenne prime $2^{1021} - c$.

As to whether composite degree extension fields are easier to solve, maybe. It is possible to represent the same composite field in a number of ways (usually known as tower of fields), and it is possible that some representations allow for faster breaks than others. Here's a quote from Andrew Odlyzko's 1985 paper Discrete logarithms and their cryptographic significance:

  In fact, these ﬁelds may be very weak because of the possibility of moving between the ﬁeld and its subﬁelds.

However, there is no data on significant asymptotic advantages of composite degree over prime degree (if there was, pairing-based schemes would be toast, as embedding degrees are by and large composite).

One shouldn't also forget to check the smoothness of $p^n-1$, to avoid embarrassing Pohlig-Hellman breaks.

May 2013 Update

It seems that composite degree is indeed weaker than prime degree. The recent results of Göloğlu et al and Joux attack fields $\mathbb{F}_{2^n}$, for composite $n$, much faster than the function field sieve referred above. See this question for more information.


When it is safe to reuse IV? (or not using at all)

It is safe to reuse AES-CTR IV (or not use one at all) in some theoretical situations, including when all except one plaintext are uniformly random and independently chosen. However, that's unsafe in most practical situations, including when an adversary knows the general nature of the plaintext (or guess it among several standard use cases), and there are a number of ciphertexts. Don't reuse IV, at least with the same key.

For any block cipher in CTR mode, it is typically extremely dangerous to reuse the same key and IV (even if secret). That's because the encryption ends up to be XOR with a fixed keystream (a bitstring) dependent on key and IV. Even though the keystream is initialy secret and indistinguishable from random (for an adversary not knowing the key), the keystream can be recovered (and all ciphertext deciphered) under many plausible assumptions, including:

Adversary knows one plaintext.
Adversary knows the ith bit of the ith plaintext.
Adversary knows some general characteristic about the plaintext; and there are a enough ciphertexts.

The first and arguably second bullets are excluded by the question, but the third applies to nearly all practical use cases except super-encryption of already enciphered data, when there are enough ciphertexts.

The crudest, but still sometime effective method to find the keystream is to determine the expected mean value of the ith bit of plaintext (which is a function of the kind of plaintext and of i, independently of the actual plaintext, which is unknown). If that deviates enough from 1/2 in either direction (as it does for many practical kinds of plaintext), and enough ciphertext is available, comparing this expected mean to the actual mean for the ith bit in the ciphertext will often reveal the ith bit of the keystream (it is expected that the means are on the same side of 1/2 for a keystream bit of 0, and on different sides for 1).

Inter-bit dependencies in the plaintext allows much faster recovery of the keystream. If plaintext is known to be English text in ASCII, a handful of ciphertexts will typically allow to recover nearly all of the keystream. Even if the plaintext was email addresses, there is enough redundancy in that to allow to find the keystream from a few hundreds ciphertexts.

If database entries are never modified and have a key index that wont vary, a common and safe solution to the problem of IV choice and availability for decryption is to use as initial counter value the index shifted left by a constant large enough that the counter values will not overlap from one database entry to the next. For AES-CTR, that shift count constant can be as small as the number of bits in the maximum plaintext size in octets, minus 4. For 64 gigaoctet of maximum plaintext size, shifting left by 32 over 128 bits is fine. We can thus append 4 zero octets on both sides of an 8-octet binary representation of the index (without having to care about endianness, unless that's mixed) to set the initial counter value (which, depending on implementations details, may or may not be the IV; actually, many implementations with an IV less than 16-octet internally append zeroes on the appropriate side).

While other modes of operation (like CBC) significantly mitigate the danger of IV reuse, that's still extremely dangerous in some scenarios.


Can rainbow tables find the preimage of a hash?

The only way to find the preimage of a hash value is to guess. There is no better way than trying all possible inputs by brute force until you find a match. This property is a design goal for cryptographic hash functions (preimage resistance).

A rainbow table doesn't help finding preimages, as such. Rather, it's a tool that helps you reuse somebody else's brute force work. If a rainbow table contains 1 trillion entries, then you can use it to find the preimage of any of those 1 trillion hash values in a short time. But the maker of this table had to make the 1 trillion hash computations. The reason rainbow tables are (occasionally) useful is that once the table has been built (a high one-time cost), you can make as many queries as you want (very low cost per query). It is useful if you have reason to believe that the preimage is among the 1 trillion in the table — if the preimage isn't one of these then all the rainbow table will tell you is that it definitely isn't one of these. See Crunge's answer on Security Stack Exchange for a very nice explanation of how rainbow tables work.

In practice looking up a hash value on Google is a low-effort way to find some simple preimages. When that doesn't work, it tends to suggests that tying to invert the hash won't be the easiest method of solving your problem.

Looking for the hash value in your question turns up a partial copy of a homework assignment which mentions “You should use the tools provided in the file, but are not limited to them.” Said file was not included in that copy of the assignment, but it should be in yours. What you need to do to solve the assignment is, presumably, to figure out how the provided tools work.


Deciphering text encrypted with a changing cipher

It's insecure because the algorithm you described has essentially no key. You just have to try 25 different offsets for the first character, then run the algorithm and see if plaintext comes out.

Have a look at Kerckhoff's Principle, and try to understand why there needs to be a secret key in addition to an algorithm.


What is the difference between 'completeness' and 'soundness' in ZKP?

The two notions are not specific to ZK, so it is in fact better to try to understand it in the context of general proof systems.

Soundness: the proof system is truthful, so whatever it proves, it is true.

Completeness: the proof system is comprehensive, so it can prove all true statements.

You can have completeness without soundness: if the proof system proves everything including falsity, obviously it is complete but not sound.

You can have soundness without completeness: if the proof system proves nothing, obviously it is sound (after all, it never proves any falsity), but not complete.


Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?

Asymmetric encryption requires some mathematical structure (to enable the magic of asymmetry), and some of that structure is readily apparent to anybody. For instance, with RSA, the encrypted messages are numbers modulo $n$ (the modulus, from the public key), and thus in the range $0$ to $n-1$. This implies that values for the first byte will be quite biased (RSA uses big-endian encoding, so the first byte is the most significant byte). For anything with elliptic curves, this is even easier, since the usual representation of a curve point will be a pair of coordinates $(X,Y)$ in a finite field, matching the curve equation. Random noise has almost zero chance of producing values which will match the curve equation.

It is normally assumed that everybody knows which algorithm was used and with what encryption key (this is a public key and we mean it). The algorithm exists as software in many places (on every machine which uses that application, as source code on the developers' systems, ...) so it seems quite hard to conceal that information anyway. Asymmetric encryption algorithms are thus designed so that this is not a problem.

In particular, asymmetric encryption includes random data. Indeed, since the public key is public, an attacker could try to guess the plaintext by encrypting potential plaintexts until one matches the actual ciphertext. The random data defeats that: even if he has guessed the right plaintext, the attacker will get something different and will not know that he has guessed correctly.

Note that in practice, an asymmetric encryption algorithm has a lot of overhead (computational cost, enlarged ciphertext...) so nobody encrypts a large file with that; instead, we encrypt a random symmetric key (aka "a bunch of random bytes") with the asymmetric encryption algorithm, and then we use that symmetric key to actually encrypt the file with a fast and lean symmetric encryption algorithm like the AES -- and that will give you a sequence of bytes indistinguishable from random noise.


Is SHA-256 OK to use for key derivation for a key that is never persisted?

In Key derivation functions, you enter a secret that is your password, salt, and the number of iterations.

$$key = \operatorname{KDF}(\text{passowrd}, \text{salt}, \text{iterations})$$

The salt is a countermeasure against the rainbow table attacks. The salt also increases the entropy of the produced key. Since the attackers cannot use a rainbow table, they have to use execute password search, the most popular is hashcat where it can utilize GPU's cores. This where the number if iterations become important. If a fast key derivation is used then the password search will be very fast. Think about the usual 10000 iterations vs 1.

In your case, you even didn't mention the salt. Without the salt, a SHA-256 rainbow table can easily find the password if it exists in the table.

As mentioned in the comments, by F.Grieu; The modern Key derivation functions has more parameters. For example; Argon2 has also memorySizeKB and parallelism parameters as a countermeasure against GPU and ASIC based passwords search attacks. Without these parameters, the GPUs and ASICs can search the passwords massively in parallel process.

An 8x Nvidia GTX 1080 can calcaulte 2865.2 MH/s SHA-256 hashes.

You should use the Scrypt or Argon2, the winner of Password Hashing Competition.


Well, there seem to be some restrictions you have:

numbers are 32 bit integers
(several) GB of total data
expansion factor matters

Well, standard ElGamal is probably already close to the best you can get. Maybe ElGamal over elliptic curves would work, which have shorter representations at similar security levels (but then the operations on points are homomorphic, and the function from integers to points will most likely not preserve this property). But in general, it's not going to be any better: Trapdoor functions need this kind of size for each element. And if the original element is just 32 bit, there is this kind of expansion.


Do very short values make a peppered hash less secure?

The assumption seems to be that the adversary wants to confirm a guess of $\mathtt{value}$ given $\mathtt{hash}=\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, for unknown random secret $\mathtt{pepper}$. This is an ad-hoc PRF of $\mathtt{value}$ with symmetric key $\mathtt{pepper}$.

No, the small size/entropy in $\mathtt{value}$ is not an issue. Neither is having a million of millions of $\mathtt{value}$ (or/and of leaked $\mathtt{hash}$ ). Without a successful and complete guess of $\mathtt{pepper}$, as far as we know, the adversary can't learn anything about $\mathtt{value}$ from its $\mathtt{hash}$ (beyond two $\mathtt{value}$ being identical with practical certainty when their $\mathtt{hash}$ is, something that additional random public salt would fix, see Maarten Bodewes's answer). Main theoretical weakness is the relatively small size of $\mathtt{pepper}$ (here 80-bit), which should be 128-bit or more by modern standards. Of course, there's the issue of keeping $\mathtt{pepper}$ secret, and other implementation issues (but the classic timing side channel of memcmp does not matter).

The best known generic attack is essentially brute force. For each guess of $\mathtt{value}$, it enumerates $\mathtt{pepper}$, computes $\operatorname{SHA-256}(\mathtt{value}\mathbin\|\mathtt{pepper})$, and compares to the given $\mathtt{hash}$ (or the full list of theses). If there are several guesses of $\mathtt{value}$ with different likelihood, it pays to try the guesses from most to least likely. If $\mathtt{value}$ was long (so that $\mathtt{value}\mathbin\|\mathtt{pepper}$ exceeds the 64-byte block size of the SHA-256 internals), it would pay to cache the intermediate values that do not vary with each $\mathtt{pepper}$.

Note: we'd have better academic security assurance if we used HMAC-SHA-256 rather than this ad-hoc PRF. See M. Bellare: New Proofs for NMAC and HMAC: Security without Collision-Resistance, in Journal or Cryptology, 2015, originally in proceedings of Crypto 2006.


Why would anyone choose 3DES over AES in software?

In my opinion, there are no reason to choose 3DES over AES, ever.

Especially if it is in software, since 3DES performances have always been terrible. Furthermore, most CPUs ship with AES accelerators nowadays, which means that AES is even faster.

But, sadly, change management is hard, certain smart card or hardware module do not support AES, but support 3DES... so if you can avoid changing your hardware, you might just keep going with 3DES, as it is not practically broken.

Also, most software development team do not have a cryptography enthusiast / a cryptographer and might just be continuing to use the good old algorithm they are used to, or that their system is based on. Not necessarily a good reason, but change is hard, especially when it comes to software, so most of the time, people prefer to avoid any change that would prevent backwards compatibility or any other such things.

Notice that nowadays, you can still find two-key 3DES out there, for these exact same reasons!

On the theoretical side, 3DES features 64 bits blocks, thus it is not suited for today high throughput data transfer protocols, since it could lead to block collisions, while AES is safe on that side with its 128 bits blocks.

On that topic, I refer you to one of my answers for more details on whether or not 3DES is safe.


Is modulus a prime number important for non-symmetric cryptology?

Yes, such a group is useful. In particular, when $N= p\cdot q$ where $p,q$ are both strong primes (i.e. $p=2p'+1,q=2q'+1$ where $p',q'$ are also prime numbers).

Discrete logarithm in the prime order cyclic groups (order-$p'$ and order-$q'$) is believed to be hard. Such a group is called a group with hidden order.

A few examples of application: Fujisaki and Okamoto used this group to construct a commitment scheme. It has also been used in constructing a zero-knowledge proof of an integer falls within an interval (range proof).

Note that security does not hold for any arbitrary $N$ (even if it has only two large prime factors), see this paper.


RSA Certificate Owner and Issuer line meanings?

CN is common name, OU is orginizational unit, O = organization.

So we could have CN="John Johnson", OU="Sales", O="Acme Corp." or something like that.

http://docs.oracle.com/javase/1.4.2/docs/tooldocs/windows/keytool.html only mentions these, but I've seen Email as well.


Under what conditions is broadcast possible? (Cryptographically, and in the model of Maurer 2006)

This is a somewhat standard method for generalizing results based on threshold adversaries. Let $n$ be the number of parties and let $\mathcal{C} \subseteq 2^{[n]}$ denote the family of subsets that the adversary can corrupt. For example, in the case of honest majority, $\mathcal{C} = \{ C \subseteq [n] : |C| < n/2 \}$.

$\mathcal{C}$ has the Q2 property if no two corruptible sets $A, B \in \mathcal{C}$ satisfy $A \cup B = [n]$. In Maurer's notation, $[n] \not\in \mathcal{C} \sqcup \mathcal{C}$.
$\mathcal{C}$ has the Q3 property if no three corruptible sets $A, B,C \in \mathcal{C}$ satisfy $A \cup B \cup C = [n]$. In Maurer's notation, $[n] \not\in \mathcal{C} \sqcup \mathcal{C} \sqcup \mathcal{C}$.

Generally speaking, classical results that require honest majority will generalize to any Q2 corruption pattern. Results that require honest two-thirds majority generalize to Q3.

I think the first appearance of this generalization is in Complete Characterization of Adversaries
Tolerable in Secure Multi-Party Computation by Hirt & Maurer. It's generalized even farther in MPC vs. SFE: Perfect Security in a Unified Corruption Model by
Beerliova-Trubiniova et al. They consider an adversary that can corrupt any $S \in \mathcal{P}$ passively, or corrupt any $S \in \mathcal{A}$ actively, or corrupt any $S \in \mathcal{F}$ in a fail-stop way. These results are harder to state in a stackexchange answer.

Regarding the question about broadcast, the actual tight bound depends very heavily on the model (poly-time vs information-theoretic, [im]perfect security, PKI setup). Also agreement, consensus, and broadcast are all slightly different. But in general, information-theoretic broadcast with no setup requires honest 2/3rds majority (Q3 corruptions).


memcmp() is not constant-time. The property called "constant-time" does not mean (confusingly) that every runs in a constant amount of time; an algorithm implementation is said to be "constant-time" if it does not leak information about secret data through timing-based side channels.

In the case of memcmp(), the leak is simple: memcmp() looks at bytes in increasing address order, and stops at the first index where bytes differ. Thus, the execution time, and the memory access pattern, if observed by attackers, may reveal how many bytes are identical. If the attacker can repeat the experiment with various purported "HMAC" values, he can use that leak to learn the complete true HMAC value, which can be a very bad thing in some contexts.

For more on the subject, see this page in BearSSL documentation.


Using RSA keys for Broadcast Encryption?

The Broadcast encryption scheme you link to uses elliptic curve groups based on the bilinear map (bilinear pairing). RSA is not elliptic curve based.

  Is there a way to mitigate the fact that we need to maintain two private keys per each user (one from RSA and one from Broadcast Encryption) ?

This is not trivially possible. You would have to devise a scheme that combines those two primitives.

The only scheme I know of that combines RSA with bilinear pairing is Comparison-based encryption for fine-grained access control in clouds by Zhu et al. (DOI: 10.1145/2133601.2133614)

You might want to check that to see if you can salvage some of that, but I doubt that you will be successful.

Why integrating them is not a good idea in your case:

If your users already have their RSA private keys, then those RSA private keys are not linked in mathematically aside from following the same key generation process. In order to get the ciphertext size improvement of broadcast encryption (BE), you'd need to find some hidden property between all of the RSA private keys just by looking at the RSA public keys of your users. For that, you will either have to break RSA (not an easy feat) or you need to ask the users for their RSA private keys. If you ask for RSA private keys, you might as well just replace them with the BE private keys and skip the integration.


Why do we use pseudo random PRNG in cryptographic applications instead of true random number TRNG

Expanding small shared secrets

In many cryptographic systems, it's necessary for the two honest parties to have a shared secret between them such that:

The attacker cannot easily guess it.
It's large enough to protect a large volume of data.

For example, the one-time pad tells us that if two parties have a shared secret at least as large as the message, that is sufficient to communicate the message confidentially.

But the fatal problem then is, how do the parties manage to establish such large shared secrets?  And the practical solution is to:

Establish a small shared secret instead of a large one—say, 128 random bits—as the key.
Use a secure, deterministic PRNG to expand the key into a long, pseudorandom bit stream that's guaranteed to be the same on both sides.

This is for example how stream ciphers work.

Engineering challenges of TRNGs

How do you build a true random number generator so that it's:

Correct: Is the output actually random?  I.e., no bit of the output must be predictable from any other.  How do you prove this?  There are physical processes that science says are truly random, but does your machine introduce some predictable measurement errors into the system, and does your TRNG reliably remove these?
Reliable: Doesn't fail often, and when it does you can tell it did.
Auditable: The users can actually verify for themselves that it is correct and reliable.
Performant: Produces random bits at a sufficiently fast rate.
Efficient: Doesn't use lots of power.
Affordable: Doesn't cost a lot of money.

It's not easy at all!  Cryptographically secure PRNGs are better in nearly all categories.  Their only downside is that by definition they cannot truly random—but given a slow TRNG to provide seeds for the secure PRNG, that's a theoretical, not a practical downside.

Some of the techniques used in true RNGs are actually quite educational about the value of PRNGs.  For example, one common technique in TRNGs is to XOR the TRNG's output with that of a PRNG.  The reason for this is that way if the TRNG's true random components fail silently or are just not correct, the pseudorandom data mixed into the output can serve as a backup to keep the security level above a certain baseline.

That's an example of using a PRNG to address the engineering challenges of building a TRNG.

Cost effectiveness

The cheapest secure solution for most applications is to use a slow source of true random data to periodically seed a secure PRNG.  By allowing that source of true randomness to be very slow (produce random bits at a low rate), it makes all the engineering challenges easier.  By using noise from peripherals that the computer already has (e.g., keyboard, mouse and network timings), it reduces the cost even more, and makes it easier for third parties to audit than a custom, proprietary device would.

The resulting system is not truly random, but it just needs to be good enough, not theoretically perfect.


Is there a cryptosystem which allows slicing and concatenating strings without decryption?

Unless you add further restrictions, it is possible to achieve what you are asking for, using a totally trivial construction. For example, the encrypt algorithm can output ciphertexts of the form "normal ciphertext: $c$". The concat algorithm can output ciphertexts of the form "concatenation of $c_1$ and $c_2$". To be clear, I am proposing that ciphertexts in this scheme literally start with the strings "normal ciphertext", and "concatenation of", etc. The decrypt algorithm can just parse and do the right thing for ciphertext of these different forms.

I'm sure this is not what you want. So if you don't want to trivialize the question, then you will need to add some other kind of requirement. For example:

The output of $\textsf{concat}(\textsf{Enc}_k(m_1), \textsf{Enc}_k(m_2))$ is indistinguishable from the output of $\textsf{Enc}_k(m_1 \| m_2)$.
Even with knowledge of $k$, the output of $\textsf{slice}(\textsf{Enc}_k(m), i, j)$ doesn't leak any information about $m$[$:i$] or $m$[$j:$].

There could be several reasonable ways to define away the trivial solution.

I'll also point out that this property is clearly incompatible with CCA security. The best you can hope for is CPA security.

CTR-mode encryption supports slicing, at least at the block level. If $(iv, c_1, c_2, \ldots, c_n)$ is a CTR-mode encryption of $m_1, \ldots, m_n$, then $(iv+i-1, c_i, \ldots, c_j)$ is a CTR-mode encryption of $m_i, \ldots, m_j$.

Most (all?) block cipher modes support truncation at the end, but not necessarily arbitrary slicing.

The best approach for allowing concatenation that I can think of is to just independently encrypt each block. I can't think of any approach that preserves the the additive ciphertext expansion of a typical block cipher mode.


Which encodings have |encoding key| >> |decoding key|?

Generate a random 2048-bit RSA key.
Generate a random RC4 key.
Seed an RC4 engine with the key generated in step 2. Throw away the first 128 bytes. Output 10MB of data from the RC4 engine (XOR with 0 or don't XOR at all).
E consists of the corresponding public key to the private key generated in step 1 and the first 10MB of data from the RC4 engine in step 3.
D consists of the RSA public key and the RC4 key.
Encryption proceeds by XORing the data to be encrypted (padded to a multiple of 10MB) with the 10MB RC4 output and then encrypting that with the RSA public key.
Decryption proceeds by regenerating the 10MB of RC4 data from the seed and reversing the encryption process.

There are numerous variations on this scheme. The idea is to make the 10MB pseudo-random (so the decryptors don't have to store it) and don't give anyone else the key needed to generate it, so they have to store the full 10MB. (You could also just pad the data up to 10MB and XOR the final output with the 10MB of data. Same idea.)


Uniformly distributed secure floating point numbers in [0,1)

For most purposes, the following trivial method should be adequate:

Generate a random  $n$-bit integer (i.e. a uniformly distributed random integer between $0$ and $2^n-1$ inclusive).
Cast the random integer into a float and multiply it by $2^{-n}$ to scale it to the interval $[0,1)$.

There's some leeway in choosing the number of bits $n$, but a generally reasonable choice is the significand precision $n_p$ of your floating-point format (e.g. 53 bits for IEEE 754 double-precision floats).  In particular, this is the highest number of bits for which the distribution of the resulting floats will actually have the full $n$ bits of entropy — or, in other words, the highest number of bits for which step 2 above is fully reversible.  If $n > n_p$, the conversion to float will map some pairs of integers to the same floats, resulting in an output distribution with less than $n$ (but still more than $n_p$) bits of entropy.

Regardless of the value of $n$ chosen, the distribution of the floats generated using this method will be "approximately uniform", in the sense that, for any $0 \le a < b < 1$, the probability of the output falling in the subinterval $[a,b)$ will differ from $b - a$ by at most $\max(2^{-n}, 2^{-n_p})$.  For $n \le n_p$, it will also be uniform in the sense that each float value that can be generated by this method is generated with the same probability ($2^{-n}$).

However, the floats generated using this method will not be uniform in the sense that each possible float within $[0,1)$ would be equally likely to be generated.  In fact, this holds for any random float generation method that is approximately uniform in the sense described above, simply because the density of representable floating point values is itself not uniform — there are far more floats in the interval $[0,\frac12)$ than in $[\frac12, 1)$.  Thus, it's fundamentally impossible to generate random floats that would be uniformly distributed in both of these senses.

In any case, it's important to realize that a random float in $[0,1)$ is not the same thing as a uniformly distributed random real number in $[0,1)$: the latter distribution has infinite entropy, whereas the entropy of any actual distribution of floats representable on a computer is inevitably finite.  While it's sometimes (I would even say most of the time, at least outside crypto) fine to substitute one for the other, it's important to keep the difference in mind when analyzing the security of algorithms that, conceptually, assume access to uniformly distributed real numbers.


Symmetric cipher speed (AES vs Camellia vs Twofish)

Just use AES. It's hardware-accelerated and implementations have had ages to have flaws discovered and patched. More strongly, just use GPG to encrypt data at rest and just use TLS (>= 1.2, with appropriate AEAD ciphers) for data in motion. "If you're typing the letters A-E-S into your code, you're doing it wrong."

Anything you build yourself is infinitely more likely to be broken as a result of your design choices than by your choice of cipher.


How to use the hardcoded server's public key to register a client application?

Can you please describe your functional requirements in more detail, i.e. what are  you trying to solve? That will ensure that you get most appropriate advice.

What do you care to achieve?

server to authenticate the client making the reservation?
a way for the client to send its driver license in a confidential manner?
client to authenticate the server before it sends its driver license?
ability to revoke and renew a compromised server key?
other?

Having a well defined number of functional requirements will let you laser-focus on determining what crypto primitives you should consider for meeting those functional requirements.

Encrypting the driver's license data with the server's RSA public key, in theory gives you confidentiality of the driver's license data since only the server private key may decrypt the driver license. In practice, the robustness of the confidentiality is a function of quality of your source of randomness, length of the RSA key, what padding is used, server-side protection of the private key, malleability of the client app since someone can hack your client app and replace the public key with their own public key, etc. In other words, take extra care with your implementation.


Best practise for encryption in a password manager

If the key is derived from the password there is no reason to store it anywhere.
The main problem in your outline is not the cryptography.
You are explicitly writing the passwords to disk. This is a really bad idea. The deletion may not happen at all, e.g powe failure. Even if it does on a modern hard drive it is really hard to overwrite data it won't actually be written to the same place and thus traces of previous data may remain.
A secure implementation will not only avoid writing to disk it would explicitly request from the OS to not swap out the sensitive memory parts. The OS may allow you to do this for only a small piece of memory. If the password DB is large decrypting the whole thing may be problematic and you should consider only decrypting the part you want but that causes a behaviour change you may or not want.
You may want an authentication if you worry about someone mangling your db.
You didn't mention IV selection, needs to be from a strong random source and replaced everytime you change anything and need to reencrypt.


Can I use an ECDH Shared Secret from the same Private / Public Key Pair?

No, it's not a problem.

What you've found is known as the square computational diffie-hellman problem(SCDH) and it can be shown that this is equivalent to the computational diffie-hellman problem(CDH).

For completeness:
SCDH:
Given $g$ (your $G$) and $g^x$ (your $Q$), find $g^{x^2}$ (your $d_A^2G$).

It is shown here that this problem is as hard as the traditional diffie-hellman problem (below):
CDH:
Given $g,g^x,g^y$ find $g^{xy}$.


One-time pad encryption - how does the receiving side decrypt the message?

The one-time pad requires pre-shared key. Usually, one of the two parties generates the keystream, writes into a paper or CD/DVD, or USB, etc.. and sends the keystream to the other party in a secure way. The secure way is not encryption, it is using some men to carry it to the target. After the transmission, they can use the key to decipher.

Wikipedia lists historical uses of the one-time pad. One case is very important; the Venona Project. At some point, the Russians had reused some part of the key. So, the question is how one notices this? The USA and British Code-breakers always tried the crib-dragging and one day was successful!

Some of The Crib Draggin answers in CryptoSO;

Taking advantage of one-time pad key reuse?
How does one attack a two-time pad (i.e. one-time pad with key reuse)?
Little problem with Vernam Cipher

And, an article: A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads


Relationship between source and output entropy

Qualified no.  There is no relationship between source entropy and the output entropy from a TRNG other than you can't output more entropy than you put in.  The actual source entropy rate can vary vastly.  Clearly the TRNG output entropy has to be 100%, 1 bit /bit or however you measure it.  Otherwise it wouldn't be a TRNG with a statistically flat output.

I like to talk in percentages, with 100% being absolute true randomness.  A physical source can produce entropy at any rate from 0 - 100%.  I can't imagine a physical source that can naturally produce 100% though. I have built two generators that produce entropy at the rates of 85% and 1.9%.  An experimental third outputs at a very very approximate 0.1%.

It's all to do with what happens to the source entropy once you've digitised it.  I think of entropy extraction as a distillation process akin to whiskey production.  The distillation process is a euphemism for lossy compression of the source entropy.  This might be a (non) cryptographic hash, matrix multiplication or just some simple bit folding.  Most TRNG devices use custom extraction techniques anyway.

If you start with 85% mash, you only need to refine /compress the mash /entropy by 17% to get 100% pure stuff.  Similarly the compression /refinement needs to be 52 fold for the 1.9% mash.  So 52 fold compression would result in a 100% rate of entropy.  But then consider that you might continue compression /refinement, so in the end you've compressed the 1.9% source entropy 100 fold.  Or 200 fold.  You still get 100% output entropy and the numbers are exactly just as random.  This is why there is no particular relationship between the source entropy and the output of a TRNG.


Using AES for smaller blocks in a Feistel network

In a Feistel network you can use ANY function and it will be invertible. Of course, in order to get security you need the function to fulfill some property. One of the main reasons to use a Feistel network is to get a pseudorandom permutation. For this to work, you need 3 or 4 rounds of Feistel with a pseudorandom function (with tweaks or independent keys at each round). Now, truncated AES is a pseudorandom function (and a very efficient one) so this is a good idea. You can pad with zeroes as you said, but you MUST also add the round number into the padding (this is the "tweak"), or alternatively use a different key in each round. The latter option is much less efficient since you need to run the AES key schedule multiple times. The use of the round function essentially guarantees a "computationally independent" pseudorandom function in each round (and so essentially the same as using a different key in each round).

In order to see that it works, just draw it and trace the decryption. The magic of Feistel is that you don't need to invert the round function in order to decrypt.


Just for simplicity lets assume that your short period "password" was just XORed with plaintext. So we have encryption procedure like:

for(int i = 0; i < plaintext_len; i++){
   ciphertext[i] = plaintext[i] ^ password[i % password_len];
}

When you shift your ciphertext by password_len and XOR it with original ciphertext, you'll cancel out your password and get XOR of original plaintext and shifted version of plaintext.

ciphertext[i] ^ ciphertext[i + password_len] =
plaintext[i] ^ password[i % password_len] ^ plaintext[i + password_len] + password[ (i + password_len) % password_len] =
plaintext[i] ^ plaintext[i + password_len]

Note that if you have a 0 char in the result, than the corresponding symbols in plaintexts are equal. The probability of such event for natural text is far from uniform and depends on plaintext language (for English it's 0,0644). If the period guess is wrong, the probability that a particular character in the result is 0 equals $1/m$ where $m$ is the number of symbols in your alphabet, for English it's about 0,03856.

So, you've got the rule how to decide on whether period guess is correct or wrong - just shift ciphertext, XOR it with original one, calculate the frequency of zeroes. If it's close to 0,0644 - your guess is likely to be correct, it it's close to 0,03856 - your guess is hardly correct.


How can I break REDSHIRT / REDSHIRT2 encryption?

I'm not going to explain this but after looking at redshirt.c; the core part of the program is that after skipping the header (which is "REDSHIRT" (9 bytes includes an ending null byte)), it has a loop which does:

int j;
j = (j & 0x7F) + (~j & 0x80);

Which, if you don't recognize it, maps 128-255 to 0-127 and 0-127 to 128-255. (I think this might be the same as swapping the nibbles of a byte.) and is the same as j = (j + 128) % 256.


Multiplication encryption with a small number

The most basic security is "Indistinguishability in the presence of an eavesdropper". This is based on a simple experiment. An adversary $A$ sends two messages $m_0$, $m_1$ to a challenger $C$. The challenger encrypts one of the messages (randomly chosen, say  $C$ chooses $b \in \{0,1\}$ uniform random and encrypts $c_b = Enc(m_b)$). The ciphertext is then send to $A$. The adversary now has to find out, which message was encrypted and sends $b'=0$ or $b'=1$ to $C$. If $b = b'$ we say $A$ wins.
Now we look at your Encryption: $A$ knows $Enc(x)$ and $x$. With the extended euclidean algorithm $A$ can compute $y$ and therefore can distinguish $c_b$. So $A$ wins the experiment and the Encryption system does not even provide the most basic concept of security.


Triple DES as cryptographic hash function

It is not a secure hash. For example, it is easy to find collisions and second preimages for your hash function if the input is allowed to be longer than 24 bytes, because only the first three 64-bit blocks affect the output.

Additionally, it should not even work with a typical DES implementation. DES keys are 56 bits, encoded as 64-bit values where 8 bits are for parity. Arbitrary inputs will not produce a well formatted key.


It computed the squareroot modulo $2^{255} - 19$

A normal (that is, computed in the field of the reals) squareroot of 39420360 would be that value $Q$ such that $Q^2 = 39420360$, where the squaring operation is done as multiplication within $\mathbb{R}$

What Sage did is the equivalent operation within the field $GF(2^{255}-19)$.
That is, it found a value $Q$ such that $Q^2 = 39420360$ when computed in that field, or equivalently, $Q^2 \equiv 39420360 \pmod{2^{255}-19}$.

Because such a $Q$ is an integer between 0 and $2^{255}-19$ (all elements of $GF(2^{255}-19)$ are), it's not surprising it's a large value.


Using public key cryptography with multiple recipients

You did not specify the details of your method to analyze, however, the usual method is not purely based on the encryption with public-key cryptography, rather a hybrid cryptosystem, where the symmetric key is transferred with the public key cryptography and the key is used in the symmetric key cryptography.
With RSA
Let's say we want to send the message $m$ to $n$ parties each have $pub_i$ and $prv_i$ keys (use RSA with OAEP).
Now, generate a uniform random AES256 key $k$ and encrypt the message with AES-GCM,
$$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$
Now encrypt the $k$ for each person $$\bar k = \operatorname{RSA-OAEP-Enc}(pub_i,k)$$ and send each user $(\bar k, c, IV, tag)$. Now each user can individually get the key $k$ and decrypt the message.
The weakness is that an observer can see that you have sent the same message to all. To mitigate this, if necessary, use a different IVs per user. Note that this will increase the encryption time.
Other candidates
RSA-KEM
The above was direct usage of the RSA. Normally one can go for RSA-KEM (in short below, full detail here)

Generate a random $r \in [1,n-1]$ and use HKDF to derive a key.
Encrypt the message with AES-GCM by using the derived key
send the $r$ with textbook-RSA together with the $(c,tag)$

NaCL
NaCl has existing solutions for this; the authenticated encryption
Integrated Encryption Scheme (IES)
Integrated Encryption Scheme (IES) has multiplicative and an elliptic curve version, too.
In the Elliptic curve version ECIES, first, there are agreements on

the elliptic curve parameters $(q,n,b,G,n,h)$
Key Derivation Function (KDF)
Message authentication code like HMAC-SHA256 ( or directly use AES-GCM or ChaCha20-Poly1305)
each user has $x_i$ as private key and the public key $P_i = [x_i]G$

Then the message can be sent as

The sender generates a random integer $r \in [1,n-1]$ and set $R = [r]G$

Let $P=(x(P),y(P)) = [r]P_i$ and make sure that $P \neq \mathcal{O}$

Let $S = x(P)$

Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$

Encrypt with AES-GCM or ChaCha20Poly1305.
$$(c,tag) = \operatorname{AES-GCM-Enc}(k,IV,m)$$

Send $(R,c,IV,tag)$

On the decryption side

Calculate $P = [x_i]R$ due to $$P = [x_i]R=[x_i r]G =[r x_i] G = [r]P_i $$ as prepared
Let $S = x(P)$
Derive the encryption AES256 key$$k = \operatorname{HKDF}(S)$$
Decrypt $$(m,\perp) = \operatorname{AES-GCM-Dec}(k,IV,c,tag)$$Never accept an incorrect tag, halt $(\perp)$?

WhatsApp
WhatsApp uses a similar idea.

Note: If possible, I would go for the NaCL


Are the asymmetric roles of the two keys in the elliptical curves the same (as for RSA)? Can they be interchanged indifferently?

In both RSA and usual¹ Elliptic Curve Cryptography (ECC), there is a public key and a private key, forming a matching pair. In signature, the private key is used for signature generation, and the matching public key is used for signature verification. In (usually, hybrid) encryption, the public key is used for encryption, and the matching private key is used for decryption. This dual role with exchange of usage order of the public and private key applies to RSA and ECC alike.
In RSA, it is additionally mathematically possible to exchange the values of the public and private exponents $e$ and $d$. It is thus possible to exchange the values of the public and private keys when expressed as pairs of integers $(N,e)$ and $(N,d)$. Such exchange of values is almost never done in RSA practice².
Such exchange of values is not possible in ECC. That's because an ECC private key is an integer $d$ in $[0,n)$ where $n$ is the order of the generator $G$ of the Elliptic Curve, and the public key is $Q=dG=\underbrace{G+G\cdots+G}_{d\text{ times}}$ where $+$ is the point addition operation of the Elliptic Curve group. The private and public keys are different mathematical objects, which values can't be meaningfully exchanged.

With ECC, given the private key, it is possible to deduce (calculate) the corresponding public key, unlike RSA.

Yes, under appropriate hypothesis: having the RSA private key in a non-standard format, and with an unusually large public exponent $e$.
In ECC, given the Elliptic Curve group³ and the private key $d$, it is a basic operation to find the public key: just compute $Q\gets dG$.
In RSA, when given the private key, it is not always possible to compute the matching public key. Specifically, when the private key is given in the form $(N,d)$, and the public exponent $e$ of the public key $(N,e)$ is a large random secret, finding $e$ is hard. However, finding $e$ is trivial when it is part of the private key, e.g. because the private key is in the recommended RSA private-key format in PKCS#1v2: $(N,e,d,p,q,d_p,d_q,q_\text{inv})$. And finding $e$ is easy when $e$ is below some threshold, e.g. $e<2^{256}$, which also is usual.

¹ As codified e.g. by SEC1.
² Such exchange is insecure if one of the public/private exponents $e$ and $d$ is less than $2^{256}$, which is common for performance reasons. Exchanging public and private key is secure only if the first chosen among public/private exponents $e$ and $d$ is selected at random in a much larger set, or if both are secret, negating the benefits of public-key cryptography.
³ Usually a public parameter, e.g. secp256k1 for anything Bitcoin. Common ECC groups are codified in SEC2.


What is hardened SHA-1, how does it work and how much protection does it offer?

Hardened SHA-1 detects collisions built of a certain form, If someone were to find a collision using brute-force birthday attack (currently not feasible) the detection would not work.

The vectors are specific small differences which may help to convert a near collision into a full collision.

The details are in the paper: https://marc-stevens.nl/research/papers/C13-S.pdf

This will detect an attack which has a similar construction to the attack performed. Future cryptanalysis may however lead to other forms of attack. It is worth mentioning  any hash function that is may be vulnerable to new kinds of attacks though. SHA-3 may also be vulnerable to attacks that are yet unknown.

Hardened SHA-1 tries to be identical to SHA-1 almost all the time with a probability of differing in honest usage of less than $2^{-90}$. Yet it should be resilient to attacks by detecting them and changing the output to something that differs.

SHA-1 has been collision free until very recently. Hardened SHA-1 should be secure in this regard; much more secure then SHA-1. It is obviously better than thoroughly broken options such as MD5.

Hardened SHA-1 tries to be backwards compatible with SHA-1. If you don't need this backward compatibility don't use it, use SHA-3 or SHA-2, even if you have to truncate to 160 bits.


What are the advantages of TOTP over HOTP?

One of the advantages is purely on the human side of security. From RFC 6238's abstract:

  The
     HOTP algorithm specifies an event-based OTP algorithm, where the
     moving factor is an event counter.  The present work bases the moving
     factor on a time value.  A time-based variant of the OTP algorithm
     provides short-lived OTP values, which are desirable for enhanced
     security.

(Emphasis mine.)

The TOTP passwords are short-lived, they only apply for a given amount of human time. HOTP passwords are potentially longer lived, they apply for an unknown amount of human time.

The reference to "enhanced security" is referencing (at least) two areas: The value of a compromised key, and ability to attack one.

First, should a current HOTP password be compromised it will potentially be valid for a "long time". Ensuring frequent use of the HOTP in human time is not a part of the HOTP design, so it is unknown how long the current HOTP password will be valid for and we have to assume the worst case, namely, that it will be a "long" time. This allows the attacker to use a compromised password at their leisure. But should the current TOTP be compromised, it will not be useful for very long because in one TOTP time increment it will be invalidated. Of course, in theory the attacker could grab and use the password in negligible time, but it does prevent a practical human aspect. For example, someone who gets a look at your current Paypal key (which rotates every 30 seconds, IIRC) can't go home and try to use it later, they would have to lunge for a computer in the moment. Someone who compromises they key may not realize it until after the key has expired. Etc.

Second, if you are attacking a key, your work is potentially invalidated or set back every time increment of the TOTP because the target has moved. Perhaps an attacker has discovered an attack against an OTP scheme that allows them to predict the next password only if they have some number of the last 10 passwords, but it takes about 2 hours of computing time to do so. If the OTP changes every minute, their attack is pretty much useless. Brute-force attacks are inhibited as well, because the next password is chosen the same distribution each time; it is possible to brute-force exhaust the password space and not find the password. TOTP doesn't eliminate those sorts of attacks, but hopefully it limits which ones have the ability to be effective.


How are data science and cryptography related?

If by data science, you mean "machine learning and cie", there is some recent works that made the link between these two hot topics :

For example, some people are trying to do data analysis on encrypted data : https://eprint.iacr.org/2017/1114


What procedure to use to verify a raw public key (TLS ECDHE_EDCSA ciphersuite)?

It is outside the scope of TLS and must be arranged out of band.

Raw public keys come without any signatures and cannot be verified without additional knowledge. Section 1 of the RFC mentions a few ways how they might be verified in some situations. They all amount to receiving the public key through some other authenticated channel.

  The TLS client can obtain the TLS server public key from a DNSSEC-
    secured resource record using DNS-Based Authentication of Named
    Entities (DANE) [RFC6698].
  The TLS client or server public key is obtained from a [PKIX]
    certificate chain from a Lightweight Directory Access Protocol
    [LDAP] server or web page.
  The TLS client and server public key is provisioned into the
    operating system firmware image and updated via software updates.


How can scrypt be improved to counter GPU mining

I believe scrypt is designed to be scaled to be both memory hard and cpu hard by explicit design.

As a result, most implementations of scrypt will require you to input a desired cpu difficulty as well as a desired memory difficulty. On a gpu, where each core has very little memory, it would be trivial to see that, unless gpus gain a great deal of memory in the near future, you can crank the memory difficulty up to the point where it will be barely tolerable for a cpu let alone a memory-light gpu core.

Simply, scrypt doesn't need to be improved, it just needs to be utilized in a manner that will achieve the desired results. Even if you look now, you will see that scrypt is doing a superb job at preventing a serious rise of hashing rate with the advent of the ability to use gpus as the rate is currently measured in kh/s per second rather than mh/s on the same devices.


32 Bytes (+16 for the tag)
Let data be your data, let || denote concatenation and let pkD be the "data's public key" (that is a Curve25519 public key which has exactly 32 bytes) and tag be the Poly-1305 authentication tag (16 bytes long).
Because pkD and tag have a fixed size, you don't need to encode their lengths and you can literally store this as pkD||data||tag. For decoding, you just grab the first 32 bytes as the data's public key and the last 16 bytes as the authentication tag.
Encryption would go like this:

Run a standard Diffie-Hellman key agreement against the recipient's public key. The public key you would normally send over the wire is pkD and will be stored for decryption.
Feed the shared secret into a key-based key derivation function to get an IV, a key for the symmetric cipher and a key for the MAC.
Encrypt the data using the symmetric keying material and append the authentication tag.
Delete all keys and the data.

If it is not of concern that an attacker can flip bits in targeted attacks with bit-level accuracy (that is, he can modify any known plaintext-ciphertext pairs to say whatever he wants), then you can omit the authentication algorithm and the MAC tag.


I don't care about replay attacks. What should I do with the nonce in nacl?

Nonces must be unique but are not secret. Typically you send it alongside the ciphertext as a prefix. Note that with the asymmetric box, you must not use a nonce that you used in one direction in the opposite direction, since both directions use the same shared symmetric key.

Reusing a nonce is a fatal mistake. It completely breaks the MAC and it leaks the xor of the two plaintexts. This leak is quite severe, if for example both texts are natural language this allows recovery of most words of the messages.

Using a counter or a random value of at least 128 bits are common approaches to generate nonces.


Is it considered insecure in an HOTP implementation to publicly provide the next counter?

RFC 4226, section 7.5 defines two shared key generation schemes: deterministic and random.  I would suggest that you use the deterministic scheme, which only requires the server to store a single "master key":

  "Deterministic Generation

  A possible strategy is to derive the shared secrets from a master
   secret.  The master secret will be stored at the server only.  A
   tamper-resistant device MUST be used to store the master key and
   derive the shared secrets from the master key and some public
   information.  The main benefit would be to avoid the exposure of the
   shared secrets at any time and also avoid specific requirements on
   storage, since the shared secrets could be generated on-demand when
   needed at provisioning and validation time."

Addendum: To also avoid storing a separate counter value for each client, you could still use a shared counter for all clients as you suggest, at least as long as the intended purpose of the server is such that it's unlikely for more than one legitimate client to attempt to authenticate simultaneously.

However, simply sending a counter value to the client and having the client reply with the corresponding one-time password could allow an attacker masquerading as the server to send an artificially high counter value to the client and store the response for later use.  (If the client enforces the monotonicity of counter values, this could also render the client temporarily unable to authenticate until the server's counter catches up with the bogus counter value sent by the attacker.)

One way to avoid this attack, and eliminate the extra round-trip to request the counter, would be to use a timestamp as the counter, something like this:

When the user want to authenticate, the server sends to the server the current timestamp $T$, its client ID $i$ and the one-time password $P = HOTP(K_i,T)$, where $K_i$ is the client's HOTP key.
On receiving an authentication request $(T,i,P)$, the server checks that:

$i$ is a valid and non-revoked client ID;
$T$ is a valid timestamp, and is not too far in the past or the future;
$T$ is greater than the timestamp $T'$ for the previous successful authentication; and
$P = HOTP(K_i,T)$, where $K_i$ is the client key derived from the client ID $i$ and the master key $MK$.

If all these checks pass, the client is allowed access.

Thus, the server only needs to store the master key $MK$, the last successful authentication timestamp $T'$, and possibly list of revoked client IDs.  (This ability to revoke access for compromised clients is one of the main advantages of not sharing keys between clients.)

The valid time window allows for some degree of clock skew between the clients and the server, and should be set to reflect a balance between that and security requirement.

An attacker intercepting the authentication request in this protocol can't really do much: if they pass the request on to the server, the password they just captured becomes useless (and if the client and server encrypt any further communications with their shared secret $K_i$, the attacker can't even eavesdrop on it); if they don't, the client will know something went wrong, and in any case the password will still expire after the limited time window passes (and possibly sooner, if the client tries to reauthenticate and succeeds).

(Obviously, the protocol also needs to protect against brute force attacks, either by implementing request rate throttling as recommended in the HOTP spec, and/or by making the password long enough.  Indeed, if the password need not be human-enterable, one could just as well — and, indeed, preferably — use the full non-truncated HMAC output as the one-time password.)


Is succinct verification of an arbitrary data transformation theoretically possible? Is it feasible? How?

Terminology: "public-coin" means the verifier does not need to keep any of its

randomness secret, and "private-coin" means "not necessarily public coin".

By IP = PSPACE, the correctness of operations can be interactively verified by a public-coin verifier whose runtime scales with the amount of space used for the transformation.

Such protocols can be modified so that additionally the verifier only needs an amount

of space that is logarithmic in the amount of space used for the transformation,

at the cost of becoming private-coin and the resulting protocol's number

being something like the square of the original protocol's number of rounds.

This paragraph is about protocols which emphasize the verifier using very little space.

Theorem 1 of Interactive Proofs for Muggles gives such a protocol in which the

verifier is public-coin.  These two papers apparently give up [public-coin]ness (at least

my search didn't find any reference to the property) in return for more efficiency gains.

I do not know of any way to combine the IP=PSPACE results with

the low-space results or even achieve any tradeoff between them.

  Although you only asked about proofs, you mentioned SNARKs,

  so the rest of this answer is about arguments rather than proofs.

By this paper, collision-resistant hash families are enough for all T with a public-coin

verifier and a constant number of rounds.  By this paper, fully-homomorphic encryption

is enough for all T with a private-coin verifier and 4 messages (2 in each direction).

Theorem 2 of Interactive Proofs for Muggles claims that a PIR scheme with bounded communication is enough for uniform low-depth T with a private-count verifier and

2 messages (1 in each direction).  However, as far as I can see, they also need

the PIR scheme to be 2-message (which all current candidates I'm aware of are).

This paper's results are similar to the previous paragraph.  Based on the title,

I imagine that SNARKs for C is the most practical candidate SNARK scheme.


Ephemeral Diffie-Hellman in a symmetric crypto context

The key exchange should also be authenticated. $\:$ GCM mode would mostly do that;

however, you should authenticate an indication of which message is for Diffie-Hellman.

(For example, you could use associated_data = 1 for the Diffie-Hellman messages and associated_data  =  0 || application's_associated_data for application-level messages.)


How is the order of a point calculated for elliptic curves over GF(p)

The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. The complexity of this method is in order ${\log^4 p}$. Using SEA you can easily compute the order of group, then with binary multiplication method you can compute the order of arbitrary points. For the meaning of "good"(and another questions), you should read about attacks against elliptic curves.

For more details you can see "Guide to Elliptic
Curve Cryptography, Darrel Hankerson, Alfred Menezes, Scott Vanstone" which is easy and complete book.


Let $T$ be an optimum prefix code tree, and let $b$ and $c$ be two siblings at the maximum depth of the tree (must exist because $T$ is full). Assume without loss of generality that $f (b) \le f(c)$ and $f(x) \le f(y)$ (if this is not true, then rename these characters). Since $x$ and $y$ have the two smallest frequencies it follows that $f(x) \le f(b)$ (they may be equal) and $f(y) \le f(c)$ (may be equal). Because $b$ and $c$ are at the deepest level of the tree we know that $d(b) \ge d(x)$ and $d(c) \ge d(y)$.
Now switch the positions of $x$ and $b$ in the tree resulting in a different tree $T′$ and see how the cost changes. Since $T$ is optimum,

$$\begin{align}
B(T) &\le B(T′) \\
&= B(T) − f(x)d(x) − f(b)d(b) + f(x)d(b) + f(b)d(x) \\
&= B(T) − (f(b) − f(x))(d(b) − d(x)) \\
&\le B(T)
\end{align}$$

Therefore, $B(T′) = B(T)$, that is, $T′$ is an optimum tree. By switching $y$ with $c$ we get a new tree $T ′′$ which by a similar argument is optimum. The final tree $T′′$ satisfies the statement of the claim.


How to securely map messages to points on an elliptic curve

If I do have to implement a mapping for security, how would you
  reccomend I map message values to points, and how should I figure out
  the maximum message size based on my curve?

The default strategy for encoding an integer message as curve point is to define a value $k$ smaller than $\log_2 p$ (with $p$ being the field prime), such that for every valid message length $m$, $m+k< \log_2 p$ holds. You would then encode the message as the $m$ high bits of the x coordinate and start counting up on the $k$ low bits until you reach an $x$ that has an $y$ on the curve (which you find using the curve equation). This usually has probability $2^{-k}$ of failing to encode a message. For decoding you simply throw away the $k$ low bits and take the rest as your message.

  Is my current implementation of the ElGamal part insecure because it
  doesn't map messages and instead takes an integer?

Yes, the scheme as given is insecure because you can easily distinguish an encryption of $1$ from an encryption of $2^{1024}$ because the former will be about as long as the curve's prime and the latter will be more than 1024-bit long, which formally breaks the IND-CPA security of the scheme.

Note that in order to use proper ElGamal you need to encode your message as a curve point $M$ and then compute $c_1=[k]\beta+M, c_2=[k]G$ all as operations on the curve. Also note that I'm fairly confident that simply replacing the unbounded integer addition with integer addition $\bmod p$ will not yield security either because curve point coordinates are not uniformly chosen integers (for starters because some $x$ values simply do not occur).

  Do I have to map a message, or is it possible to do something like
  I've already got going with Edward's curves

I see no reason to make any changes to your code, because currently it doesn't actually use ElGamal (see above). If you were to use proper ElGamal, the same strategy that worked for Weierstrass should also work for Edwards (see the first part).