Tls protocols: is the simple diffie hellman key exchange still used these days?

In TLS, Diffie-Hellman (non-EC) can be used in TLS_DH_* ciphersuites ("static DH"), and in TLS_DHE_* ciphersuites ("ephemeral DH").

Static DH occurs when the server's certificate contains a public DH key. This never gained traction; historically, the US federal government promoted use of DH for key exchange because, at that time, RSA was still patented. However, nobody in practice does that anymore, except maybe in some old, hidden systems in some US federal organizations, and not for general public consumption.

Ephemeral DH is quite widely supported. For instance, my own Web server uses the default SSL configuration of Apache+mod_ssl on Ubuntu 16.04, and offers the following protocol versions and cipher suites:

  TLSv1.0:
     server selection: uses client preferences
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA
  TLSv1.1: idem
  TLSv1.2:
     server selection: uses client preferences
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_128_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_AES_256_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_128_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_CBC_SHA256
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_CBC_SHA256
     3-- (key:  RSA)  RSA_WITH_CAMELLIA_256_CBC_SHA
     3f- (key:  RSA)  DHE_RSA_WITH_CAMELLIA_256_CBC_SHA
     3-- (key:  RSA)  RSA_WITH_AES_128_GCM_SHA256
     3-- (key:  RSA)  RSA_WITH_AES_256_GCM_SHA384
     3f- (key:  RSA)  DHE_RSA_WITH_AES_128_GCM_SHA256
     3f- (key:  RSA)  DHE_RSA_WITH_AES_256_GCM_SHA384
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_CBC_SHA256
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_CBC_SHA384
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_128_GCM_SHA256
     3f- (key:  RSA)  ECDHE_RSA_WITH_AES_256_GCM_SHA384

As you can see, there are quite a lot of DHE suites here. The server's certificate contains a public RSA key, so all the DHE suites are tagged DHE_RSA, which means: "the server sends DH parameters, signed with its RSA key".

Now, that the server offers DHE ciphersuites does not mean that they actually get used. As shown above, my server follows the client preferences, i.e. uses the first ciphersuite it knows of among the list sent by the client, during the initial TLS handshake. Thus, if the client supports DHE and ECDHE ciphersuites, but sends the ECDHE suites first, then the server will choose one of these ECDHE suites.

Moreover, modern Web browsers tend to drop DHE support. On my machine (a macOS Sierra laptop), I have three up-to-date browsers (Chrome, Firefox and Safari), and none of them offers DHE cipher suite support (all happily negotiate ECDHE_RSA if the server supports it, but fall back to plain RSA key exchange if the server does not support ECDHE). In that sense, DHE ciphersuites are an obsolescent feature. Take care that not all TLS is about Web browsers talking to Web servers; there are a lot of applications that also use TLS, and do not necessarily follow the browser trends. Moreover, modern Web browsers are automatically updated, so they are always "cutting edge", while servers and applications can lag for quite some time (many years even). Still, it can be expected that TLS libraries slowly deprecate DHE ciphersuites, or possibly drop support altogether, since ECDHE ciphersuites are more efficient (my own TLS library, for instance, supports ECDH and ECDHE but never supported DH or DHE).

Summary: DHE ciphersuites still work on a number of existing servers, but don't see much usage in practice when clients are Web browsers, and support is expected to dwindle and disappear over time. As you say, indeed, DHE was replaced by ECDHE.


Does a cryptosystem provide unconditional security if and only if it provides perfect secrecy?

Yes, in context of encryption the two terms have the same meaning, i.e. even an unbounded adversary cannot succeed in breaking the secrecy of the scheme.

Note that there may be other primitives which also provide unconditional security with respect to some other notions, such as information theoretically secure message authentication codes with respect to unforgeability.


Since the RSA problem is assumed hard, we do not know and can't find the factorization of $n$.
We know (from standard RSA) that $m=c^{\left(e^{-1}\bmod\varphi(n)\right)}\bmod n$ fulfills the requirement $c\equiv m^e\pmod n$, but we do not know how to compute $m$ without some extra info or oracle.

Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Yes, but I have no better argument than: among integers $c>1$ independent of $n$, only exact $e^\text{th}$ powers are known to make it easy to solve the RSA problem for arbitrary $n$ too large to factor and odd $e>1$ making $(n,e)$ a valid RSA public key. In addition, there in no such $c$ in the interval $[2,2^e)$,  which with $e=65537$ as in a comment by the OP includes about all commonly used values of $n$, thus of $c$.
Solving $c\equiv m^e\pmod n$ for small $c$ is not necessarily hard for other $c$ and whenever $n$ is hard to factor. Proof by counterexample: $c=2$, $e=65537$, $n=(3^{65537}-2)/29$. I can't factor that $n$, yet it's easy to find the solution $m=3$.
More formally: I'm about as confident about the hardness of the RSA problem than I am about that problem restricted to small $c>1$, provided that $c$ is not a power of $e$, and that factors of $n$ are random distinct primes large enough to make factoring $n$ unfeasible. Yet I'd be quite surprised if we could prove the hardness of that restricted RSA problem on the basis of the hardness of the normal RSA problem.


What is an example of elgamal homomorphic double encryption?

You are looking for commutative encryption rather than homomorphic encryption. Also Elgamal is probabilistic, which means in each encryption a fresh randomness is added to the ciphertext, which means if the same plaintext is encrypted twice, the ciphertexts will be different.

For a deterministic commutative encryption scheme, you can use RSA encryption (SRA in your comment).


Why is it said that if we have a duplicate ciphertext block it can leak our information?

The exact information leaked depends on the mode of operation that is in use.
The simplest case is ECB, where a duplicate ciphertext block means that the corresponding plaintext blocks are also equal.

For the CBC mode, when two ciphertext block are equal, i.e. $C_i=C_j$, we know that there was equality before applying the block cipher. This in turn implies:$$C_{i-1}\oplus P_i=C_{j-1}\oplus P_j.$$
Equivalently, you are learning that $P_{i}\oplus P_j=C_{i-1}\oplus C_{j-1}$.

EDIT The equality comes from the fact that in CBC mode, $C_i=E_K(C_{i-1}\oplus P_i)$ where $E_K$ denotes the block cipher in use.


Can we estimate the amount of entropy required to generate an RSA key?

Is there some measure of the total amount of entropy bits needed to make a single 4096 bit RSA key?

Well, there are two relevant attacks against RSA:

The attacker uses NFS to factor the modulus
The attacker scans through the possible entropy inputs that possibly generated the public key, and for each such input, generates the corresponding RSA public key, and see if that's the one he's looking for.

The first attack is estimated to take circa $O(2^{160})$ time; while the second attack will take circa $O(2^k)$ time if we use $k$ bits of entropy, hence if we use $k=160$ bits of entropy, the second attack is no easier for the attacker than the first (which doesn't depend on how much entropy we collect).  Note that this rather crude analysis ignores some significant constant factors (the algorithm to turn an entropy sample into an RSA public key isn't cheap); however for this question, it should be good enough.

In addition, if we use our 160 bits of entropy to seed a good CSPRNG, and use the CSPRNG output to generate the actual bits used by the prime searching algorithm, that means that there is no easier entropy-based attack.

So, 160 bits are sufficient, and significantly fewer entropy bits will cut into the security of the RSA key.

Now, that's what is possible; I don't know the algorithm that GPG uses to search for RSA public keys - they may use significantly more.


Encrypting more than ~64GiB with AES-GCM - Integrity

The nonce is included in the computation of the tag.

If the nonce is incremented after each message, chunks cannot be reordered or duplicated. If the third message is expected to have been encrypted with nonce 3, the tag verification is not going to pass if a message encrypted with nonce 2 is provided instead.

One thing you need to detect, though, is when the last message has been received. It can be achieved by reserving a bit of the nonce to indicate this, as in the STREAM construction.

If the nonce is effectively a chunk index, the key can only be used once, as you don't want a (key, nonce) pair to repeat, especially with different messages.

So, you either need to use unique keys, or reserve part of the nonce as an IV (or message -not chunk- index), and the rest as a chunk index.

Individual chunks should have a reasonable size, if only because you don't want to download, store and verify 64 GB to finally discard everything due to a tag that doesn't verify. 16 KB and 64 KB are common sizes.

And, especially with AES-GCM, you may also want to frequently do key rotation.

If this is an option, just use TLS that will take care of all these things.

If you don't want to use TLS, but AES-GCM is not mandatory, a construction such as xchacha20-poly1305 is easier to use safely with large messages.

If you don't want to use TLS, and want to use AES-GCM, use the STREAM construction.

If you don't want to use TLS, AES-GCM is not a requirement, and you don't want to write the code, use libsodium's secretstream construction.

For more practical details on this topic, see Encrypting a set of related messages
.


Examples of protocols that are insecure when run concurrently

Consider the function $f : \{L,R\} \times \{ U,D \} \to \{0,1,2\}$ defined by the following table:

$$
   \begin{array}{c|cc}
      f & L & R \\
      \hline
      U & 0 & 0 \\
      D & 1 & 2
   \end{array}
$$

Let's say Alice has input from $\{L,R\}$ (she chooses a column) and Bob has input from $\{U,D\}$ (he chooses a row).

A simple protocol for $f$ is as follows:

Bob announces his input in the clear. If his input is $U$, then parties can halt, as they know the output must be 0.
If Bob's input is $D$, then Alice announces her input in the clear. With both inputs known, the parties can compute the output.

This protocol is secure against active adversaries in a standalone security model, but it is insecure when three instances are executed concurrently.

Imagine the following scenario:

Bob is honest and chooses one of the instances to have input $U$ and the other two to have input $D$. There are three such combinations ($UDD, DUD, DDU$) and he chooses with uniform probability.
Alice is corrupt. She wins the game if she can cause the 3 instances to have all distinct outputs. It's not hard to see that she can only win by using different inputs in the two instances where Bob chooses input $D$.

If parties have access to 3 parallel instances of ideal $f$, then it is easy to see that Alice can only win with probability 1/3. In this setting, Alice's choice of input is independent of Bob's. There must be (at least) two $f$-instances where Alice uses the same input, and with probability 1/3 those will both be ones where Bob uses input $D$.

But in the presence of concurrent protocol instances, it is easy for Alice to win with probability 1. The protocols can be run in lockstep, and Alice just waits for the first protocol message in each instance. Then she can send appropriate (different) protocol messages in the instances that proceed to step #2.

Since Alice can influence the protocol in some way that she cannot influence ideal instances of $f$, the protocol is insecure in this setting.

This example is a bit simplified. I assumed that the ideal calls to $f$ were done in parallel. But it is not hard to adapt this kind of example to different requirements on the ideal world.

The big picture is that a standalone-secure protocol can leak some information early in the protocol, with the reasoning that this information is something that could be deduced from the output anyway (like Bob's input in this case). But in the presence of concurrent composition, and correlated inputs between different instances, this kind of leakage can be unsafe.


Attacking hashed password by timing attack and other means

Let's make things slightly more abstract at first.

The attacker knows $n$ salts $s_i$. Passwords have $e$ bits of entropy and are hashed to $h_i = H(s_i, p_i)$. The attacker can calculate $2^c$ hashes $H(s_i, p)$ per second and can query some kind of an oracle $2^q$ times per second for the prefix length shared by $H(s_i, p)$ and the target $h_i$.

Simplest would be if the shared prefix length was known to the bit. In that case when the attacker knows the first $b$ bits of $h_i$, they can look for a $p$ for which $H(s_i, p)$ starts with those $b$ bits ($2^b$ work) and by querying the server would find an expected 2 more bits of $h_i$. Thus, finding the $e$-bit entropy password would take about $2^{e-1}$ hashing work and $e/2$ queries on average.

If the length is known with byte accuracy, the attacker would need to query up to 255 times to go from knowing $b$ bytes to knowing (usually) one more. The hashing work would remain the same at $2^{e-1}$, but about $128(e/8) = 16e$ queries would be required. With $w$-bit words, the number of queries required would be about $2^{w-1}e/w$.

So, in cracking those $n$ passwords, the attacker would spend $n2^{e-1-c}$ seconds hashing and $ne2^{w-1-q}/w$ seconds querying. With your numbers of $n=16$, $c=40$, $q=10$ and assuming $w=8$, cracking even 70-bit passwords would require less than half a minute of queries total, which means it is negligible compared to hashing time for anything remotely secure and the attack is effectively offline. Only with $w = 32$ and larger does it start to matter – each password would require a month or two of queries at that point.

With prefix queries at byte accuracy and 44-bit passwords, the attacker would require 8 seconds of hashing and less than a second of queries to crack all 16 passwords. They might be limited by network latency and need several extra seconds due to that.


Encrypt a message with hash function, shared symmetric key, but no cipher

There is a simpler way: implement a stream cipher using the hash function, and use that to encrypt the plaintext.

Probably the most used stream mode is counter (CTR) mode, which is normally defined for block ciphers. CTR mode works equally well with a PRF (MAC) as with a PRP (block cipher). It only uses the function as a one-way function; with a block cipher either the encrypt or decrypt direction (of the block cipher) is used.

The CTR mode for HMAC can be implemented as follows: $C_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus M_i$ where:

$C$ is the ciphertext;
$i$ designates the block;
$k$ is the key;
$nonce$ is a value that is changed for every ciphertext computation;
$I2OS$ is a conversion method to convert an integer to a binary encoding and
$M$ is the message to encrypt.

$I2OS$ is configured using a static size of - in this case - 4 bytes. The blocks have the same size as the hash output. For the last block only the leftmost bytes can be used.

The $nonce$ or IV could be a random value that sent with each ciphertext. In principle it can have any value as long as it is unique. It forms the counter value together with the encoded value of $i$.

Decryption is of course identical: $M_i = HMAC(k, {nonce} | {I2OS}(i, 4)) \oplus C_i$

Your scheme may work: basically you can perform $T=HMAC(K, K_{pub})$ and send $K_{pub}|T$. Then the receiver party knows that the public key is indeed from the sender, and they can use it to encrypt.

However:

this still needs an encryption primitive, i.e. a cipher;
this is an online protocol rather than direct encryption;
this is probably not what was meant, as the split of the message $M$ into blocks indicates.


Plenty of ciphers come out of the USA from government research or selection competitions. AES and DES are examples.

Indeed, the US is known from some crypto-related competitions that were/are open to anyone and they surely will do ample of government research related to cryptology, but you need to be sure that you differ between “they selected it” and “they created it”. There is a big difference!
For example: what we now call AES was selected through an open competition by the USA, but the cipher design that became AES was not created by the USA.

  Are there any public ciphers produced by other states, China or Iran for example? Do you really think they trust AES?

Of course there are other countries and states that are known to be the origin of different ciphers, but listing them all would be a bit too broad. Instead, I’ll give you a quick heads-up:

Also, on page 3 of "The Design of Rijndael: AES – The Advanced Encryption Standard." by Joan Daemen and Vincent Rijmen (the creators of Rijndael – also known as AES), you can find a neat table that shows a list of the 15 AES candidates that were accepted for the first evaluation round, including their country of origin.

For your convenience, here are those 15 candidates:

CAST-256
submitted by Entrust (company), from Canada
Crypton
submitted by Future Systems (company), from Republic of Korea
DEAL
submitted by Outerbridge, Knudsen (researchers), from USA & Denmark
DFC
submitted by ENS-CNRS (researchers), from France
E2
submitted by NTT (company), from Japan
Frog
submitted by TecApro (company), from Costa Rica
HPC
submitted by Schroeppel (researcher), from USA
LOKI97
submitted by Brown et al. (researchers), from Australia
Magenta
submitted by Deutsche Telekom (company), from Germany
Mars
submitted by IBM (company), from USA
RC6
submitted by RSA (company), from USA
Rijndael
submitted by Daemen and Rijmen (researchers), from Belgium
SAFER+
submitted by Cylink (company), from USA
Serpent
submitted by Anderson, Biham, Knudsen (researchers), from United Kingdom & Israel & Denmark
TwoFish
submitted by Counterpane (company), from USA

From the 15 candidates that made it into the first evaluation round of the AES competition, only 5,5 originated in the USA. That’s a mere $36 \frac{2}{3}\%$ percent of US ciphers in their own cipher competition.

Wrapping it up:

AES is far from being a US government baby. Instead, cipher that won the AES competition (Rijndael) was born in the land of friendly people, “french” fries and tasty beer: Belgium!

Now, being a half-Belgian I may be a bit biased… but I honestly have a hard time trying to imagine why anyone would suspect a Belgian cipher design, just because it also happens to be used by the US government. Instead, that merely indicates that the cipher design is that good, that even the USA uses it to protect its valuable information and big parts of their national security.
A lot of ciphers were (and are) created outside of the USA. Yet, not all ciphers that are created are published; and if they are, they rarely gain attention due to missing publicity and/or popularity. That is one of many reasons why those competitions are interesting for cipher designers.

As said, listing all ciphers from all countries would be too broad, but the above list of “AES round 1 candidates” already shows Australia, Belgium, Canada, Costa Rica, Denmark, France, Germany, Israel, Japan, Republic of Korea, United Kingdom, and the USA.

That should be ample to understand ciphers are not a US-only thing and that the US is not as dominant in crypto as you think. In the end, even AES is non-US. They adopted a Belgian cipher to their standards, but they didn’t create it. If you really want to suspect someone for having whatever kind of dominance in the field of symmetric crypto, I can’t stop you. But if you take a good look at the origins of individual ciphers, you’ll notice they come from all over the world… and currently, your main suspect would be Belgium  due to AES (aka Rijndael) and SHA-3 (aka Keccak).


How were one-time pads and keys historically generated?

Your interesting questions deserve to be answered more thoroughly, but here goes:

According to a highly classified document written in 1947 and finally declassified in 2013, the Germans started using a one-time pad system for diplomatic traffic in 1925. This system (GEE) used a one-time pad of digits to encrypt codes by modulo addition. To be clear, these codes, from a large codebook, stood for names, numbers, grammatical features of German, dates, places, objects, etc. GEE traffic was first intercepted in 1934.  That was good for the Allies because World War II in Europe was around the corner, and keys for the GEE system were being generated by a complex mechanical device that was not cryptographically secure.

The German additive generator of wheels and switches had weaknesses that were brilliantly exploited by American analysts:  the phases, cycles, potential overlaps, and limits of the keys became apparent after an exhaustive analysis of captured GEE one-time pads. By March 1, 1945, the U.S. was breaking GEE traffic because the German machine did not create truly random numbers--the Americans soon made a mirror machine based on key periodicity, other weaknesses, etc.
The released document (PDF) says that the GEE keys

…could be predicted in full upon partial recovery through cribs and superimposition to give a new kind of overlap.

Breaking GEE allowed the U.S. access into German diplomatic traffic at the end of the war, especially their dealings with Japan. (See the intriguing reference to uranium in one pre-August 6, 1945 transmission.)
Interestingly, the document says that the Germans could have easily defeated cryptanalysis by changing the set-up of the 240 wheels in the machine, but they never did!  The Germans produced enormous amounts of key material without altering the basic set-up of the device. This led to "ample homogeneous material" being created.

During the Cold War, the Soviets were known to generate one-time pads by having rooms full of typists peck away "randomly."  That's not genuinely random, but still formidable because such results are--as another writer said--from different people and can be muddled further.  For those who disparage one-time pads, consider this:  the NSA refers to the day when the Soviets started using one-time pads in "...all high-level Soviet communications, including the mainline military, air force, and navy nets" for radio traffic--October 29, 1948--as Black Friday, which immediately "...ravaged the cryptologic landscape...".  (See page 19 of The National Cryptologic School's "On Watch", 9-86) Nevertheless, there are instances in which critical key weaknesses helped cryptanalysts exploit key misuse during the Cold War.

Early U.S. efforts to generate random numbers and marry those to plaintext (Telektypton, 1933) depended on a typist and keyboard, a natural but faulty way to think about the problem.  Importantly, the Telekrypton had other weaknesses, such as a looped keystream.  What is so interesting about Telekrypton is that it was widely used, highly regarded, and deeply flawed. After World War II, the idea of using noise for entropy in key generation was made and used by British Intelligence. The man who figured this out retired from GCHQ in the 1980's.  The generator based on his ideas has been regarded as the first to generate truly random keys.


Algorithm for anonymous but associated communications from a set of verified communicants?

You are describing linkable ring signatures. Here's a paper from ICCSA that goes into the model and proposes some schemes.


One obvious thing that it is vulnerable to a known plaintext attack that truncates the known message.

This attack is quite simple; suppose the attacker knows a message $(P_1, P_2, ..., P_n)$ and the corresponding ciphertext $(C_1, C_2, ..., C_n, T)$ (using some IV; we don't care what it is).

Here is how the attacker can generate a ciphertext that would decrypt and validate to $(P_1, P_2, ..., P_k)$ for a $k$ of his choosing.

First of all, he can truncate the ciphertext $(C_1, C_2, ..., C_k)$; that will obviously decrypt into the message he wants; all he needs to do is compute the corresponding tag so that it would validate.

He can do this because we already knows that $C_{k+1} = E(C_k) \oplus P_{k+1}$; this is how CFB mode works.  Because of this, he can then compute the tag:

$T' = C_{k+1} \oplus P_1 \oplus P_2 \oplus ... \oplus P_k \oplus P_{k+1} = E(C_k) \oplus P_1 \oplus P_2 \oplus ... \oplus P_k$

And there, his job is done...


Parallelized Pollard's Rho algorithm for ECDLP + Jacobian coordinates

The bad news is that projective coordinates do not work with Pollard's Rho like you want it to. Rho needs an unambiguous point representation to find meaningful collisions, and in projective coordinates each point can have up to $p-1$ valid distinct representations.

The good news is that, sticking to affine coordinates, you can avoid most of the cost of the inversions by performing a bunch of them in parallel, and trading $N$ inversions by $1$ inversion plus $3N-3$ multiplications. This is the so-called Montgomery trick (Section 2.5.1), and is the most common approach in ECDLP Rho implementations.


Prove that if we redefine the key space, we can assume Gen chooses a key uniformly

Sorry for the late answer, I got busy...

So, you know that $\mathsf{Gen}$ is a probabilistic algorithm. What's a probabilistic algorithm? It's an algorithm which, during its execution, can make some random choices, which can be modeled as coin tosses. In programming terms, the algorithm can use a special coin-tossing function, which returns $0$ or $1$ each with probability $1/2$. The random tape is where the machine will write down the result of its coin tosses (or equivalently, where an external coin-tossing device will write the result of the tosses for the machine to read them). Because the results of the coin tosses are uniformy distributed, the contents of the random tape will be uniformly distributed as well and you can use that as your key.

Consider for example a cryptosystem with $\mathcal{K} = \{0,1\}$, and $\mathsf{Gen}$ as follows (in Python-like pseudocode):

def Gen():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    if coin1 == 0:
        return 0
    elif coin2 == 0:
        return 0
    else:
        return 1

It is clear that the key is not chosen uniformly: $0$ is chosen with probability $3/4$. Now, consider a cryptosystem with $\mathcal{K}' = \{(0,0),(0,1),(1,0),(1,1)\}$ and $\mathsf{Gen}'$ as follows:

def Gen'():
    coin1 = toss_a_coin()
    coin2 = toss_a_coin()
    return (coin1, coin2)

Now the key is chosen uniformly. Define encryption and decryption with the keys $(0,0)$, $(0,1)$ and $(1,0)$ to be the same as with the key $0$ in the previous system (whatever that is), and encryption/decryption with the key $(1,1)$ to be the same as with the key $1$. It is clear that you get essentially the same cryptosystem, but with the key chosen uniformly.


As pointed by the question, in SRP an attacker knowing the verifier can impersonate the server. That's not against the security objectives of SRP.

To carry the attack, the attacker also needs to know the salt, but it is public and can be obtained from the server. With both verifier and salt, the attacker then behaves with respect to the client just as the server does.

The problem of authenticating the server can be solved by https and a server certificate, inasmuch as you trust certificates (certificates only checked by a common web browsers/OS should be only marginally trusted: governmental and other well-founded adversaries can easily obtain a forged certificate with any CN field they wish, and certificate chain, that pass this test). It is still reasonable to use SRP on top of https with a server certificate: at least, if the certificate is subverted, the password does not leak, and the user can't be impersonated to the server (the main goal of SRP), contrary to what would happen with the password sent over https.


What is the main difference between Unique signature and Verifiable Random Function?

A signature scheme has the following two functions for a key pair $(k, K)$:

$\sigma = \operatorname{Sign}_k(m)$
$\mathit{valid?} = \operatorname{Verify}_K(m, \sigma)$

A VRF has slightly more:

$(\sigma, x) = \operatorname{VRF}_k(m)$
$\mathit{valid?} = \operatorname{Verify}_K(m, \sigma, x)$

Without knowledge of the public key $K$ and the signature $\sigma$, the VRF output $x$ appears to be an independent uniform random bit string for each distinct $m$.  That is why it is a verifiably pseudorandom function: except for verifiability, it appears to have independent uniform random outputs.

In contrast, for example, RSA-based signatures typically have a per-key distribution that is distinctive enough to deanonymize signers in practice (popular exposition; actually this was RSA-based ciphertexts but the principle is the same).  While EdDSA signatures do not have a distinctive per-key distribution, they easily distinguished from uniform random bit strings because they encode $(R, s)$ where $R$ is a point on the curve (only about half of such bit strings will be so) and $s$ is an integer below the order of the curve (which is often substantially less than the number of bit strings of the same length).

If there is exactly one $\sigma$ for each $m$ under any particular public key $K$, then we can devise a VRF with the help of a uniform random function $H$ as follows:

$\operatorname{VRF}_k(m) := (\sigma, H(\sigma))$, where $\sigma = \operatorname{Sign}_k(m)$
$\operatorname{Verify}_K(m, \sigma, x) := (\operatorname{Verify}_K(m, \sigma) \mathrel{\text{and}} x \stackrel?= H(\sigma))$

Choosing, e.g., $H = \operatorname{SHA-256}$ makes a practical VRF that is secure against $H$-generic adversaries, or ‘secure in the random oracle model’, because without knowledge of the unique $\sigma$ for any particular $m$, $H(\sigma)$ is a uniform random bit string independent of anything else you can compute.

(More on signatures vs. VRFs with references.)


The output of any modern hash is binary. Not all byte values however map to (printable) characters. So what you are looking at is a textual representation of the hash, using an encoding such as hexadecimals (e.g. for sha256sum) or base 64.

You are mentioning the value 16, so lets presume that the output is in hexadecimals. In that case each of the characters 0-9 together with A-F (in upper- or lowercase) is expected with a probability of precisely $1\over{16}$, given that the observer doesn't have any information on the input.

If the input can be guessed and verified then the chance of guessing the output is a perfect 1: the attacker can simply perform the hash calculation himself to calculate the output. You would have to perform HMAC instead of the hash function and keep the key secret.

Depending on your requirements you are probably better off using a known secure PRNG (or DRBG) and seed it using the input.


Homogenous vs heterogeneous unbalanced Feistel networks?

There is no “generally definable” security trade-off, unless there’s something wrong with one of the algorithms itself… and if, that could be proven easier in the case of homogenous UFNs.
Using homogenous UFNs makes security proofs easier as they are easier to analyze while heterogenous UFNs tend to make cryptanalysis (and security proofs) more problematic. This can be a valid argument to choose a homogenous over a heterogeneous UFN.


Security level of DSA when $q$ is a 224 bit prime?

What is the security level of DSA algorithm when q is a 224 bit prime?

About 112-bit, at most. More precisely, there's an attack recovering the private key from the public key, by solving a Discrete Logarithm Problem, costing roughly $2^{113}$ modular multiplications, and little else: the attack can be efficiently distributed and requires little memory. See Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Is it always a simple rule that the security level is the bit length of $q$ divided by two ?

No. That rule applies unless there's another weakness:

The public prime $p$ is too small (or of a special form facilitating attack). As a rule of thumb, size (and requirement to not be too close to an exact power) are comparable to that of $n$ in RSA for the desired security level, in order to resist index calculus and GNFS variants. That would make about 2048-bit a minimum. See KeyLength.com for more precise advice on size.
The random generator used for signing has an exploitable weakness.
The private key leaks, e.g. by power analysis or timing attack.


RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring comparatively little computing effort. It is beneficial from a computational perspective because (assuming $p$ and $q$ have the same bit size, or nearly so)

we can compute $y_p=x^d\bmod p$ as $y_p={(x\bmod p)}^d\bmod p$; this computation multiplies numbers half as wide as $x^d\bmod N$ would do, hence requires (asymptotically) 4 times less elementary operations when using standard multiplication algorithms; so total computational effort can be reduced by a factor of (near) 2;
it is easy to run the two sub-calculations in parallel, so elapsed time can be reduced by a further factor of (near) 2.

So, in RSA with CRT, we do not have to compute $d_p=d\bmod(p-1)$ and $d_q=d\bmod(p-1)$ as stated in the question; we can do it for additional savings, as explained below.

One form of Fermat's Little Theorem states that if integer $x$ is not a multiple of prime $p$, then $x^{p-1}\equiv1\pmod p$. If we set $d_p=d\bmod(p-1)$, or more generally chose any $d_p\equiv d\pmod{(p-1)}$, then by definition $d=k\cdot(p-1)+d_p$ for some integer $k$, thus
$$x^d\equiv x^{k\cdot(p-1)+d_p}\equiv(x^{p-1})^k\cdot x^{d_p}\equiv1^k\cdot x^{d_p}\equiv x^{d_p}\pmod p$$
Noticing that the above equation also holds when $x$ is a multiple of $p$ provided that $d>0$ and $d_p>0$, we can thus compute $y_p=x^d\bmod p$ as $y_p=x^{d_p}\bmod p$, or rather $y_p={(x\bmod p)}^{d_p}\bmod p$. The reduced exponent $d_p$ is less wide than $d$ by a factor of (nearly) 2, with about that saving in computational effort and time (combinable with the aforementioned savings).

Note: It may turn out that $d_p=k\cdot(p-1)+(d\bmod(p-1))$ for some $k$ (possibly negative) with small $|k|$ would be a more efficient choice than $d_p=d\bmod(p-1)$. That's typically only a tiny extra saving; exactly when will depend on the particular exponentiation algorithm used, and for negative $k$ on the cost of computing a modular inverse $\pmod p$.

Note: RSA CRT also has drawbacks, e.g. different vulnerability to fault injection and side-channel attacks.

As to why $d_p=d\bmod p$ does not work: there is no reason that it would, and experiment with small values proves that it does not in the general case.


Are there any authoritative definitions of "key stretching"?

In my practice (Smart Cards, often using DES and increasingly AES)

Key Expansion is often used to designate production of subkeys in a block cipher. This process is often a mere bit extraction, as part of the algorithm's Key Schedule.
Key Diversification is, almost exclusively, the process of producing a device key from its serial number (or other identifier) and a master key. This transformation must be such that compromise of the key of some devices does not compromise the master key, or the key of other devices.
Key Derivation is a general term for producing a key from another key. It is often used for Key Diversification, or the process of expanding one key to several keys of different function (e.g. a confidentiality key for CBC encryption, and an integrity key for CBC-MAC), or the process of obtaining a session key from a long-term key. The term Key Derivation tends to imply that the derived key does not leak from the original key (as illustrated in Key Diversification).

Further, I would understand Key Strengthening or Key Hardening (exclusively), or Key Stretching (less specifically) as a purposely compute-intensive transformation of a key, effectively increasing its resistance to brute force search by a parameterizable factor, e.g. in PBKDF2 or Scrypt. Key Stretching is attested in this meaning, as stated in the question. But I have also seen Key Stretching used for the process of obtaining several keys from a single one, without intend to slowdown a brute force search.

And I would understand Key Salting as the ages-old process of adding (public or mildly secret) salt to a key (of low-entropy such as a password), so that at least identical keys do not degenerate into identical cryptograms, without indication of the deliberate introduction of a compute-intensive transformation as in Key Strengthening.

I am not an authority, English is my second language, and I have somewhat changed my mind on the usual meaning of Key Stretching.


Does it matter if I publish only publish good or bad MD5 hashes after recovering from a hack?

Does it matter?  Yes: there's a qualitative difference in the types of attacks that would break your system.  The elephant in the room, of course, is MD5, but let's examine the qualitative difference between the attacks first.

It is almost useless to publish the bad hashes, because as an adversary I could just distribute different versions to everyone.  A million downloads?  A million different ISO images, uniquely tailored with a special brand of malice.

What about publishing the good hashes?  This is what you should do anyway, but you're restricted to MD5.  How can I break this?

I'm an evil developer, and I play the long game.

I make three versions of a software package:

the good one does what it is advertised to do which is something useful
the bad one does something harmful noisily, like uploading credit card data to a bad place
the sneaky one does something harmful quietly, like slowly making your screen look blurrier and blurrier over the course of a month, or silently disabling disk encryption

There's a sneaky catch: the good one and the sneaky one collide under MD5, but the bad one does not.
I publish the good package under my name, and the curators closely scrutinize it to audit the code and confirm it does what it claims.  (Yeah, right!)
I hire someone, who lives in a closet under the stairs in the Ecuadorian embassy with nothing but his cat and his colossal narcissism to entertain himself, to break into the package servers and upload the bad package on one distribution server, and the sneaky package on all the other ones.
Someone notices the network traffic from credit card uploads and raises an alarm.  The curators publish the good package's hash for everyone to verify their systems.
Everyone freaks out and stampedes to upgrade the software simultaneously.

Now everyone has the sneaky software, and if they check the MD5 hash they will rest assured that it's the good package's hash.

You could say this is convoluted.  True, it is convoluted: I wouldn't try to pull this plan off, but that's in part because I'm not really evil.  Evil people who are dedicated will use a convoluted plan if it works.  A single NUL byte buffer overflow can, through a convoluted series of steps, be turned into remote code execution.

So what do you do?  In your rush to rectify the poisoned ISO image, you could commission a careful multinational study of the technical capabilities of everyone on the planet who might be your adversary, and determine their risk aversion, technical sophistication, logistical planning, and chutzpah to see whether they would be capable of pulling off any attack in this class.

But that might cost a pretty penny and it might take a bit of time.

Fortunately, there's a much cheaper way to get a high degree of confidence that you thwart any plan of this sort, without having to study how convoluted the adversary's actions might have to be and whether that level of convolution is feasible.

Don't do something stupid like using MD5.  Use a modern collision-resistant hash that isn't broken instead, like SHA-256, or SHAKE128, or BLAKE2b.

If you absolutely must use MD5 and MD5 alone, you could publish $(r, \operatorname{MD5}(r \mathbin\| n \mathbin\| m))$ where $r$ is chosen uniformly at random independently for each file (maybe as the HMAC-MD5 of $m$ under a secret key), $n$ is the name of the file including the version (encoded prefix-free, maybe with a length delimiter), and $m$ is the content of the file.  (Of course, if the adversary knows or can predict $r$ before they choose $m$, then it's back to the same issue as standard MD5.)  But chances are, it'll be much easier for you and your users if you just use a non-broken hash.  SHA-256 has been available for a decade and a half.


How to securely use Elgamal encryption in libgcrypt?

I took the world's shortest look at the code, so please don't hold me to any of this. But it seems that the implementation is textbook. You provide a block of data, it gets encoded to an integer in the range 1,...,p-1 and then encrypted using standard Elgamal without padding.

There's does not seem** to be an encoding to the subgroup of quadratic residues, and this implementation is /not/ CCA secure. These probably aren't going to kill you if you're encrypting a large random key, but they're definitely not the right way to encrypt.

Rather than hacking Elgamal, I'd say you're better off encrypting with RSA-OAEP.

In the long term, libgcrypt should implement a secure KEM/DEM for Elgamal encryption. DHAES would be a great example. Alternatively the authors should give a proper (non-textbook) Elgamal implementation with a group encoding and protections against adaptive-chosen ciphertext attacks.

(Elgamal seems to be the forgotten primitive. pycrypto has the exact same problems. Nobody loves Elgamal, which is too bad because it's a great encryption scheme.)

** A footnote: I didn't look deeply into the encoding function (below), so I admit I could be wrong about this point. But I don't see anything obvious. Here's the code:

init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, gcry_pk_get_nbits (s_pkey));
  rc = sexp_data_to_mpi (s_data, &data, &ctx);


$\alpha^{2^{m} + 1}$ is a generator of $\operatorname{GF}(2^m)$?

Since you haven't heard of splitting fields, here is an argument based on more elementary group theory.

Let $G$ denote a cyclic group. Then, it is easy to show (or you might already know it) that if $\alpha \in G$ is an element of order $n$ (we write $\mathsf{ord}(\alpha)=n$ to denote this), then
$$\mathsf{ord}(\alpha^k)= \frac{\mathsf{ord}(\alpha)}{\gcd(\mathsf{ord}(\alpha),k)} = \frac{n}{\gcd(n,k)}.$$
Choose $G = \text{GF}(2^{2m})^*$ whose generator $\alpha$ is of order $n = 2^{2m}-1$, observe that $2^{2m}-1 = (2^m-1)(2^m+1)$, and deduce that
$$\mathsf{ord}(\alpha^{2^{m}+1}) = \frac{2^{2m}-1}{\gcd(2^{2m}-1,2^{m}+1)} = \frac{(2^m-1)(2^m+1)}{2^{m}+1}
= 2^m-1.$$
Thus, $\alpha^{2^{m}+1}$ generates the unique cyclic subgroup (of order $2^m-1$) of $\text{GF}(2^{2m})^*$ which itself is of order $2^{2m}-1$. Now, $\text{GF}(2^{m})$ is a subfield of $\text{GF}(2^{2m})$ and so this subgroup must be $\text{GF}(2^{m})^*$.


Where are the DH parameters in a Server Exchange Message?

From the screenshot:

EC Diffie-Hellman Server Params
Curve Type: named_curve
Named Curve: secp256r1
Pubkey: ...
Signature: ...

This tells us the following: You used a key exchange with ECDHE. They key exchange used P-256 (the elliptic curve, aka secp256r1) and the given value describes the public ECDH key and the signature on this value.

The paramters you are looking for are hard-coded for P-256 and documented in several places (for example in this PDF). The $g^e\bmod p$ you're looking for is the Pubkey which is mentioned in the screenshot.


Verifying dealer parameters in 1-2 oblivious transfer

There are many proof systems achieving this goal, i.e. Alice can prove to Bob, that her public parameters were chosen in a "right way". What does "right way" mean?

Typically, what we want for public parameters $(N,e)$ is that the map $x\rightarrow x^e$ over $\mathbb{Z}^{*}_{N}$ defines a permutation to deter certain attacks, for example the attack mentioned in OP's question. The state of the art for such a proof system is proposed by Goldberg et al. It is a non-interactive Honest-Verifier Zero-knowledge proof system allowing one to certify that public RSA parameters were generated in a non-adversarial manner without leaking any information about the factors of $N$. Such a certification contains $\lambda/\log_{2} e'$ group elements from $\mathbb{Z}^{*}_{N}$, where $\lambda$ is the bit-security one wants for the soundness of the certificate proof and $e'$ is the smallest prime which divides the public exponent $e$. In a typical parameter setting, where $e=e'=65537$, with $\lambda=128$, the proof consists of $9$ integers from $\mathbb{Z}^{*}_{N}$ and also proof generation and verification is super lightweight. For more details, see the paper linked above.

There are also many proof systems allowing one to prove that an integer is a product of two primes. This is quite an old paper by van de Graaf and Peralta but might suffice for your needs. One could even prove more about a semiprime! For instance one could prove that a (committed) number is a product of two safe primes due to Camenisch and Michels. Additionally, one could prove that a number is a product of two primes AND also a Blum-integer. Lastly, there is an efficient, non-interactive, statistical zero-knowledge proof system for quasi-safe prime products by Gennaro, Micciancio and Rabin.


What encryption shoud I use for single char encryption?

There is no minimal message size. Even an empty message can be securely encrypted, i.e. the ciphertext is indistinguishable from a different encrypted message, as long as the encryption key remains secret.

Can you describe exactly what are want to achieve?

Where will the secret key come from?

Even though minor optimizations are possible with very short messages (in particular, short tags may become acceptable), you should use traditional constructions. ChaCha20-Poly1305 and AES-GCM, in particular, don't require padding, and work with short messages just as well as with long messages.

Edit: since your use case is a key logger, you probably don't need to encrypt individual characters. Buffer them up to a reasonable size (maybe 1KB), and encrypt the buffer once it's full or when the application terminates.


Your fault attack scenario correspond to this paper :

A Differential Attack Technique Against SPN Structures with Application to AES and KHAZAD (Piret & Quisquater - CHES 2003)

This paper describe how to retrieve four bytes of the last round key with at least two pairs of ciphertext/faultytext.

Each pair of ciphertext $C$ and faultytext $C^*$ could be written as $C^* = C \oplus E$, where $E$ contains 4 bytes $\neq 0$.

For more details, the attack consists on several steps :

Compute a list $L$ of 4x255 possible differences after the MixColumns of Round 9
Guess 4 parts of $K_{10}$
Compute $d = SB^{-1} (C \oplus K_{10}) \oplus SB^{-1} (C^* \oplus K_{10})$
If $d$ in $L$, add guessed $K$ in a list of possible candidates of $K_{10}$
Repeat for each pair, considering only guessed $K$ in the list of possible candidates, if $d$ is not in $L$ for the new pair, remove the candidate.
Repeat until the list of possible candidates is reduced to one.


A 2-pass authenticated cipher is a mode of operation that uses two full (block) cipher operations for each byte in the message. There is also a mode of operation, OCB mode, which uses a single pass to provide both message confidentiality and message integrity / authentication (it has been encumbered by IP-rights issues, so it isn't used that much).

A 1.5 authenticated cipher of course doesn't perform the encryption or authentication operation for every other byte. It simply uses an authentication algorithm that - when implemented right on the right hardware - is considered faster than the block cipher. Hence the 1.5 pass which should be read as one full pass of the block cipher + one pass - counted as 0.5 - for the faster authentication operation.

As an example GCM requires one block cipher operation and one 128-bit multiplication in the Galois field per each block (128 bit) of encrypted and authenticated data. 128-bit multiplication in the Galois field can be considerably faster than an AES block encrypt. Poly1305 has the same function as GMAC which specifies the Galois field multiplication within GCM.

Both GMAC and Poly1305 require post pre- and post processing. So for smaller messages the difference between a 1.5 and a 2 pass authenticated cipher may be less pronounced (depending as well on how much pre- and post processing the 2-pass cipher requires).

Please do not directly view the 0.5 as a performance indication. It depends on the algorithm and implementation what the speed differences are with 1-pass and 2-pass ciphers. it's just an indication that it should not be considered another full pass when it comes to the expected speed.


Deterministic Encryption - Generating IV from password key

From my understanding of your question, what you want is to hide the name of the file, while enable syncing. You don't actually need encryption per se, since the real name of the file could be encrypted together with the entire file (probabilistically). As such, a potential solution is to just HMAC the file name and use that as the value for syncing. No IV or encryption is needed.
If you want to be able to invert this (if that's important), then you should use something like AES-SIV or AES-GCM-SIV (with fixed IV=0; in general, this isn't recommended but if these are really your constraints then this works). This will ensure that two files with parts of the name the same won't be discovered. You can of course do this also by deriving an IV and encrypting as you say, but that's more complicated and not standard. As such, it's not recommended.
My recommendation would be HMAC on the name for syncing, and regular probabilistic encryption on the name and full file.


How large should a Diffie-Hellman p be if the messages are encrypted?

How large should $p$ be if the Diffie-Hellman exchange is encrypted?  Well, that rather depends on:

How much do you trust the encryption key not to be recovered?
Why are you doing a Diffie-Hellman in the first place?

If you can trust that the encryption key will never be recovered by anyone other than the sender and the receiver, then it doesn't really matter how large of a Diffie-Hellman modulus you use.  On the other hand, you don't need to do Diffie-Hellman at all, you could have one side pick a random value, and send that, encrypted by the key that we trust.

However, if you can't assume that the encryption key may not be compromised, then it would appear that you would have the same requirements on the DH parameters that we have on unencrypted exchanges; which (with the current hardware and DLOG algorithms) is that $p$ be at least 1024 bits, and that $g$ has an order that's a prime at least 256 bits long.

BTW: you asked about the size of $g$; its actual size isn't important.  What's important is its order, that is, the smallest $x>0$ for which $g^x = 1 \bmod p$.  This order $x$ should be a large prime value.  Small values of $g$ can achieve this; in particular, if $(p-1)/2$ is also prime and $p = 7 \bmod 8$, then $g=2$ will always have a large prime order (and, in fact, in such a modulus, you can show that if someone can solve the computational DH problem with $g=2$, then they can solve it in that modulus for any value of $g$ with a polynomial number of queries).

Lastly, you mentioned that you were doing this for a password protocol.  If so, I would strongly urge you not to encrypt the DH value with a password-derived key, but instead use a protocol with PAKE properties (such as SRP or EKE.  One of the properties is that someone who passively watches the protocol messages can't learn anything about what password might be used.  In contrast, if you just encrypt a DH exchange with the password as the key, what someone might try is to decrypt your messages with his guess at a password, and see if the message makes sense.  Even if you don't include any protocol bits in the encrypted message for him to check, what he might try is to see if the decrypted DH value is within the group that you're using to do DH (and if it's not, he has just learned that his guess at a password is not it, and can be removed from his list).  The existing PAKE protocols avoid that sort of possibility.  In EKE, they actually do encrypt the DH value with a password derived key; they are just careful not to leak any information about the password when they do it.


It just leaks information about the blocks with the same IV.

Specifically, if the two messages encrypted with the same IV started with blocks $M_0$ and $M'_0$, then the attacker learns the value $M_0 \oplus M'_0$ (and if those where the same, then the attacker also learns the corresponding xor with the second block, etc)

However, the attacker learns nothing about the key, or about any message that wasn't encrypted with a shared IV.


Probabalistic Polynomial-time Algorithms & One-way functions

A probabilistic algorithm uses random numbers to define the next step it should do (google for instance "Monte Carlo Algorithm").
"Random coin tosses" merely says that the random numbers are equally distributed.
The algorithm A will use the random numbers only internally, it will not output any random number.
But A's output will depend on those random numbers.
Therefore, it will output a correct pre-image only with a certain probability.


Why are zk-SNARKs possible, in layman's terms

When you have eliminated the impossible, whatever remains, however improbable, must be the truth. (Sherlock Holmes)

If I find you in my dorm room and the door and windows are intact, I can only conclude that you somehow learned the entry code, because I do not know of any other way by which you could have entered my room without breaking the door or windows.

A ZK-SNARK for a function $f$ is similar: if you present a proof for the result $1$ which can pass the verification procedure, it necessarily means that you must know an $x$ such that $f(x) = 1$. This is because we do not know of any (efficient) way to generate such a proof if you do not know such a value $x$. In fact, we have a proof that being able to do this would imply being able to solve certain mathematical problems which are believed to be hard (you can think of factoring integers, although the problems used to construct SNARKs are more complicated). So when you say

  Intuitively it seems like there would be plenty of ways for the client to alter the program code in order to produce output which could be used to fake their identity.

... there may or may not be, but we do not know of any and we consider it very unlikely (i.e., impossible, for all practical purposes).


Is it possible to match encrypted documents using user-defined search terms?

Yes.  If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries.

There is a rich research literature on this topic.  The buzzword is "search on encrypted data".  I'll point you to a few sample papers in this space.  Do a literature search, and you should be able to find many more for yourself.

CryptDB: Protecting Confidentiality with Encrypted Query Processing, Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan.  SOSP 2011.  See also the CryptDB web page.
Secure Indexes, Eu-Jin Goh.
Practical Techniques for Searches on Encrypted Data, Dawn Xiaodong Song, David Wagner, and Adrian Perrig.  IEEE Security & Privacy 2000.
Public key encryption with keyword search, Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, Giuseppe Persiano. EUROCRYPT 2004.
Designing Secure Indexes for Encrypted Databases, Erez Shmueli, Ronen Waisenberg, Yuval Elovici, and Ehud Gudes. Database Security 2005.
How to Search on Encrypted Data, Eu-Jin Goh.  Slides.
Private Searching On Streaming Data, Rafail Ostrovsky and William E. Skeith III.  CRYPTO 2005.
New Constructions and Applications for Private Stream Search (Extended Abstract), John Bethencourt, Dawn Song, and Brent Waters.  IEEE Security & Privacy 2006.
Secure Ranked Keyword Search over Encrypted Cloud Data, Cong Wang, Ning Cao, Jin Li, Kui Ren, and Wenjing Lou.  ICDCS 2010.
Enabling Efficient Fuzzy Keyword Search over Encrypted Data in Cloud Computing, Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, and Wenjing Lou.
New Security Models and Provably-Secure Schemes for Basic Query Support in Outsourced Databases Amanatidis, Boldyreva, O'Neill. 2007
Privacy Preserving Keyword Searches on Remote Encrypted Data Chang and Mitzenmacher. 2005
Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries Cash et al. in CRYPTO 2013
Multi-key Searchable Encryption Popa and Zeldovich. 2013.
Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions Curtmola et al. 2006

The best scheme for your situation will depend upon your application requirements.  If you have a read-mostly database (updates are rarer than searches), then I would suggest a scheme based upon encrypted indexes.  If you need to make modifications frequently, or if searching is relatively rare, the other schemes might be preferable.


Why is a one-time MAC secure for MAC-then-encrypt with randomized-CTR but not randomized-CBC?

How can we use one-time-MAC without negotiating the different keys for each message?

If you use a universal hashing one-time MAC, and you encrypt it with CTR mode, effectively you are creating a Carter–Wegman–Shoup MAC:

Carter and Wegman showed[1] that if $r, s_0, s_1, \dots$ are independent uniform random and $H_r$ is a universal hash with bounded difference probability $\Pr[H_r(x) - H_r(y) = \delta] < \varepsilon$ for all $x \ne y$ and $\delta$, then the forgery probability for the authenticator $m_i \mapsto H_r(m_i) + s_i$ is bounded by $\varepsilon$.
Shoup suggested[2] deriving $s_i = E_k(i)$ for a block cipher $E$, which is essentially what you get with MAC-then-encrypt in CTR mode.  Since $E_k$ is a permutation you run up against the birthday bound, of course, just like any use of a block cipher in CTR mode.

  What is wrong with randomized-CBC that doesn't allow us to use with one-time MAC?

Offhand, I am not sure!  If the one-time MAC is a universal hash with bounded collision probability $\Pr[H_r(x) = H_r(y)] < \varepsilon$ for all $x \ne y$, then this intuitively sounds like it ought to be a secure construction, because $m \mapsto F_k(H_r(m))$ is a secure long-input, short-output PRF if $F_k$ is a secure short-input, short-output PRF and $H_r$ has bounded collision probability[3].  That's not exactly the scenario we have here, because there is not one fixed family $F_k$—if we encrypt $m \mathbin \| H_r(m)$, we get $$E_k(\mathit{iv} \oplus m) \mathbin\| E_k(E_k(\mathit{iv} \oplus m) \oplus H_r(m)),$$ so $m$ figures in twice, but it's pretty close, so intuitively it seems like this should be secure.

Of course, it's not clear that the mere security of a one-time MAC—a bound on forgery probability after a single attempt—implies any of this even with CTR: I'm assuming bounds on collision or difference probabilities, specifically.  Maybe you could ask Dan Boneh what he meant.

There is also a danger of padding oracles with CBC in MAC-then-encrypt or MAC-and-encrypt, because CBC works on sequences of blocks rather than sequences of bits, which is why it is hard to get right: practical realizations like TLS and SSH had mistakes for years that leaked plaintexts via padding oracles.


You can very easily Base64-decode a string.
SHA-1 was designed to prevent people from inverting it. It approximates a one-way function.

See here for more. If it could be simply inverted, it would provide no information security.

Your only feasible option is brute-force search.


How do I apply differential cryptanalysis to a block cipher?

Basically it's analysis of a cryptographic cypher by the means of finding a relationship between the difference in the input data and the output data.
Ideally, the slightest difference in input data (cleartext), even a single bit, should produce a completely different cypthertext. However, if the cypher is not well-designed, a correlation between the two resulting cyphertext might be observed. This correlation in turn might be exploited to find out the key.
This, obviously requires a chosen-cleartext-attack; which means the attacker should have access to the encryption mechanism, and thus use it to encrypt any number of cleartexts he or she choses. Therefore, this kind of attack is generally applied against temper-proof hardware which one could use but not get hands on the key itself.

As per AES, see this excerpt from the Wikipedia article on differential cryptanalysis:

  For example, if a differential of 1 => 1 (implying a difference in the
  LSB of the input leads to a output difference in the LSB) occurs with
  probability of 4/256 (possible with the non-linear function in the AES
  cipher for instance) then for only 4 values (or 2 pairs) of inputs is
  that differential possible. Suppose we have a non-linear function
  where the key is XOR'ed before evaluation and the values that allow
  the differential are {2,3} and {4,5}. If the attacker sends in the
  values of {6, 7} and observes the correct output difference it means
  the key is either 6 xor K = 2 or 6 xor K = 4, meaning the key is
  either K = {2,4}.
  In essence, for an n-bit non-linear function one would ideally seek as
  close to 2-(n-1) as possible to achieve differential uniformity. When
  this happens, the differential attack requires as much work to
  determine the key as simply brute forcing the key.

Here are a few links for warming up:

A simplified AES algorithm and its linear and differential cryptanalyses
Impossible differential cryptanalysis of Mini-AES
Low Complexity Differential Cryptanalysis and Fault Analysis of AES

And here are a couple of better articles on the subject:

A Tutorial on Linear and Differential Cryptanalysis
A stochastic model for differential side channel cryptanalysis

Not top quality links, and especially not as practice-oriented as you seem to be looking for, but I think these last two could give you a bit of grip on the subject.


Is the key safe if attacker know the encrypted and decrypted message?

For any proper encryption algorithm, it is safe. The type of vulnerability you are describing is a key recovery attack or a forgery attack involving known plaintext-ciphertext pairs. Only very insecure ciphers are vulnerable to that attack, and strong, modern ones like AES are not.


Safe elliptic curve point addition using projective coordinates: How do I tell if the points are the same?

The routine you link to is already performing that check (lines 15-17): it returns $(0,0,0)$ when $S$ and $T$ are equal, and the caller is expected to handle this by calling the doubling routine.

The equality verification is performed by checking whether
$$X_1Z_2^2 - X_2Z_1^2 = 0$$
$$Y_1Z_2^3 - Y_2Z_1^3 = 0$$

It is easy to see that, since $x = X/Z^2$ and $y = Y/Z^3$, the above equations only hold when the points are equal. Indeed, if neither point is at infinity,
$$
X_1/Z_2^2 - X_2/Z_1^2 = \frac{X_1Z_1^2-X_2Z_2^2}{(Z_1Z_2)^2},
$$
$$
Y_1/Z_2^3 - Y_2/Z_1^3 = \frac{Y_1Z_1^3-Y_2Z_2^3}{(Z_1Z_2)^3}.
$$

We can safely ignore the denominator, since the result is $0$ if and only if the numerator is $0$.

While this implementation is correct, I would not call it safe; timing or power usage information could be used to learn a secret key. This is a good overview of what can happen, and the available options to counter it.


Size of Fresh Ciphertext's Noise in FHE over the integers

Let's look at the ciphertext:

$ c \leftarrow m + 2r + 2 \sum\limits_{i \in S} x_i \bmod x_0 = m + 2r + 2\sum\limits_{i \in S} (pq_i + r_i) + k(pq_0 + r_0) $ for some $k$.

When we do modular reduction by $p$, what remains is $ m + 2r + 2\sum\limits_{i \in S} r_i + k r_0 $. This (without $m$) is called the noise - as long as it doesn't wrap around $\bmod p$, decryption will succeed. So the term $ 2r + 2\sum\limits_{i \in S} r_i + k r_0 $ is what they are referring to with "noise".

I do understand your confusion though - while $2r$ does seem to have the longest bitlength $\rho' + 2$, I'm not clear on why $2\sum\limits_{i \in S} r_i $ can't exceed this, as we have up to $\tau$ terms that we are adding.

Sorry I couldn't answer your question in full!


In this notation, $f^k(x)$ means "apply $f$ $k$ times in succession".  For example, $f^3(x)$ is defined to be $f(f(f(x)))$.

Because of this definition $f^a(f^b(x)) = f^{a+b}(x)$ holds trivially (even though we known nothing else about $f$), as the the left side means "do $f$ $b$ times, and then do it $a$ times", while the right means "do $f$ $a+b$ times".

$f(x) = x+1$ is not a counterexample.  In this case, we have the simplification $f^k(x) = x+k$ (for example, $f^3(x) = f(f(f(x))) = (((x + 1) + 1) + 1) = x+3$, and so $f^{2^w-1-b_i}(f^{b_i}(x)) = 2^w - 1 - b_i + (b_i + x) = 2^w-1 + x = f^{2^w-1}(x)$


What are the pros and cons of SIP media encryption types SRTP, ZRTP, and DTLS?

I hope to keep this as simple as I can. I'll begin with some terms:

To establish any kind of SIP call, you first need to talk to the SIP server and well, initialize a session.
The call itself happens over a media stream, which may or may not be encrypted and may or may not be proxied by the SIP server depending on what was negotiated and the presence or absence of NAT.

The terms in your dashboard are actually confusing, as you'll see. To secure that media stream you need to exchange a key of some kind and work out if you trust each other and SRTP does not specify how to do this.

One way and the way I have seen used most often is SDES. I suspect what your interface is describing as "SRTP" is in fact "SIP and negotiating keys with SDES and encrypting with SRTP".

Needless to say, to exchange a key using this (simple) mechanism you absolutely have to be talking SIPS (or SIP over TLS). If you are not, or any part of the SIP chain is not, you are in trouble. You are likewise exposed to all drawbacks of TLS in establishing trust (you are reliant on PKI, which you may or may not regard as a good thing).

DTLS is actually DTLS-SRTP. This is another way to negotiate keys but rather than use an extension to SIP to do it, SIP simply indicates the media stream uses DTLS-SRTP and key negotiation happens in the media stream. Key negotiation happens as in TLS and thus relies on PKI.

ZRTP is the same idea and also happens in the media stream, except that rather than rely on TLS for the establishment of keys, Diffie-Hellman key agreement takes place and key verification is done by verifying "fingerprints" in the form of short strings. You can think of this as the voice equivalent of OTR.

Now let us introduce a major gotcha in SRTP - there is a NULL cipher which can be negotiated for "no crypto please" much like the NULL cipher in TLS.

Which to use then. On initial setup, all require you to trust your SIP server to negotiate the call successfully. Thereafter ZRTP will detect any MITM, whereas DTLS versus SDES will not. Of the the other two I would say that DTLS is more secure, since theoretically with key pinning and trust-on-first-use, you could achieve a similar guarantee to ZRTP (and the question of "which is better" becomes "do you trust certificate authorities". You could also potentially use a private PKI with DTLS). In addition, with DTLS, an attacker must compromise both the SIP server to redirect the SRTP stream and provide certificates the peers trust; this may or may not be easy. SDES as described exchanges keys via SIP, which must be entirely trusted.

I would generally say that ZRTP > DTLS > SDES given expected implementations, but the devil is in the detail. For example, can you key pin? Does your software tell you if the NULL cipher is in use? Can you configure your software not to negotiate it?

However, things get more complicated when realities arise. With many VOIP providers you are reliant on their SIP proxies to establish your communication and they may not negotiate the protocol you want. Moreover, media streams can be proxied especially if you are behind NAT and some VOIP software may not understand ZRTP. To this end FreeSwitch has a dedicated option for ZRTP passthru.

So to summarize, it really depends on what is available and what you can negotiate. However, all three result in your media stream being protected by SRTP, which uses AES in counter mode, with truncated HMACSHA1 in Encrypt-then-Mac mode over the packet header including index. The gotcha is that integrity protection might not be used. With the least truncated HMAC for integrity protection I think this would count as "not terrible" but also perhaps not the best.

In short, I would say that:

ZRTP may be the best choice for small environments or maybe even large ones if the verification step is taken seriously.
DTLS-SRTP may be a good choice if you configure all devices to trust only a well controlled CA you own. This however means calling out is difficult. If you generally trust CAs, this is a good choice.
SRTP+SDES requires you definitely trust the SIP server, but if you do then this is OK.

In all cases you need to be sure you are talking to the correct SIP server and doing so securely, especially and critically for the first communication.


RIPEMD versus SHA-x, what are the main pros and cons?

Initially there was MD4, then MD5; MD5 was designed later, but both were published as open standards simultaneously. MD5 had been designed because of suspected weaknesses in MD4 (which were very real !). So MD5 was the first (and, at that time, believed secure) efficient hash function with a public, readable specification. MD5 was immediately widely popular.

The original RIPEMD was structured as a variation on MD4; actually two MD4 instances in parallel, exchanging data elements at some places. RIPEMD was somewhat less efficient than MD5. Also, since it is based on MD4, there were some concerns that it shared some of the weaknesses of MD4 (Wang published collisions on the original RIPEMD in 2004). Last but not least, there is no public freely available specification for the original RIPEMD (it was published in a scientific congress but the article is not available for free "on the Web"; when I implemented RIPEMD for sphlib, I had to obtain a copy from Antoon Bosselaers, one of the function authors). So RIPEMD had only limited success.

NIST saw MD5 and concluded that there were things which did not please them in it; notably the 128-bit output, which was bound to become "fragile" with regards to the continuous increase in computational performance of computers. So they designed "SHA" with a 160-bit output, soon amended into SHA-1 (the older SHA being colloquially renamed "SHA-0"). Being backed by the US federal government is a strong incentive, and the NIST did things well, with a clear and free specification, with detailed test vectors. So SHA-1 was a success.

The authors of RIPEMD saw the same problems in MD5 than NIST, and reacted with the design of RIPEMD-160 (and a reduced version RIPEMD-128). RIPEMD-160 appears to be quite robust. However, it appeared after SHA-1, and is slower than SHA-1, so it had only limited success. The most notable usage of RIPEMD-160 is within PGP, which was designed as a gesture of defiance against governmental agencies in general, so using preferring RIPEMD-160 over SHA-1 made sense for that.

Since then the leading role of NIST in the definition of hash functions (and other cryptographic primitives) has only strengthened, so SHA-2 were rather promptly adopted, while competing hash functions (such as RIPEMD-256, the 256-bit version of RIPEMD-160, or also Tiger or Whirlpool) found their way only in niche products.

Summary: for commercial adoption, there are huge bonus for functions which arrived first, and for functions promoted by standardization bodies such as NIST.

As for the question of whether using RIPEMD-160 or RIPEMD-256 is a good idea:

RIPEMD-160 received a reasonable share of exposure and analysis, and seems robust. But its output length is a bit too small with regards to current fashions (if you use encryption with 128-bit keys, you should, for coherency, aim at hash functions with 256-bit output), and the performance is not fantastic. The usual recommendation is to stick with SHA-256, which is "the standard" and for which more optimized implementations are available.
RIPEMD-256 is a relatively recent and obscure design, i.e. it did not receive as much attention as the SHA-*, so caution is advised.

So my recommendation is: use SHA-256. You will probably not get into actual security issues by using RIPEMD-160 or RIPEMD-256, but you would have, at least, to justify your non-standard choice.


How hard would it be for a signing party to link blind messages to later revealed un-blinded versions, by keeping a log of blinded messages that they sign.

Assuming that the $r$ values are chosen uniformly from the values $[1, N-1]$ relatively prime to $N$ (and kept secret, for example, zeroized after use), and none of the $m$ values are relatively prime to $N$, then it's impossible to link them later (and this does not rely on a computational assumption, but an informational one).

For any such array of possible messages $m_1, m_2, ... m_n$ in any order, and blinded messages $m'_1, m'_2, ..., m'_n$, there is a unique set of values $r_1, r_2, ..., r_n$ with $m'_i \equiv m_ir_i^e$.  No set of values $r_1, r_2, ..., r_n$ are any more probably than any other, hence the server gets no information whether $m_1$ corresponds to $m'_1$ or $m'_2$ (or, for that matter, whether it was one of the values signed at all)

  It does however specify that an attacker could possibly use a blinded signature to get signatures for something different than what was signed

What the Wikipedia article is worrying about is that the attacker can do other things with the 'blinded signature' facility other than signing messages.  For example, if the RSA key is also used to encrypt messages, then the attacker could ask for a 'blinded signature', but instead decrypt a message.  This blinded signature method really is an oracle to the RSA private operation, and there is no easy way to limit it to only generating signatures.

  Wouldn't (signing a hash) break the unlinkability?

Yes (unless you do a lot of work with zero knowledge proofs).  This simple blinded signature scheme relies on the idea that the server gets no information on the message being signed; once you give it some, things start being linkable.  This could be worked around, however it's probably be easiest to use this RSA key for nothing other than signatures (and so there's nothing an attacker can do with the RSA oracle, other than generating signatures).


Is encrypted e-mail sent over TLS 1.3 a form of "forward secrecy" (similar to something like Signal)?

Forward secrecy is a confusing term that should be abandoned, especially the meaningless but value-loaded variant ‘perfect forward secrecy’.  It is especially confusing because it is often associated with any protocol that does ephemeral DH key agreement, like TLS—even if, as in TLS<1.3 session resumption, the keys capable of decrypting transcripts of past sessions are deliberately kept around for long periods of time.  Instead, you should ask: Who has the data, who has the decryption keys, and when can the decryption keys be erased?

Suppose Alice decides she wants to send a message to Bob, and types it into her laptop.

Let's look at the flow of data in email.

Alice's laptop sends the message to Alice's MTA outgoing.oohay.com over the internet, encrypted.

The decryption keys between Alice's laptop and Alice's MTA outgoing.oohay.com can be erased after this step, but now outgoing.oohay.com necessarily has a plaintext copy of the message.

outgoing.oohay.com sends the message to Bob's MTA incoming.oogleborg.com over the internet, encrypted.

The decryption keys between outgoing.oohay.com and incoming.oogleborg.com can be erased after this step, but now incoming.oogleborg.com necessarily has a plaintext copy of the message.

A couple days later, after Bob gets back from vacation, he logs into his workstation and downloads the message from incoming.oogleborg.com over the internet, encrypted.

The decryption keys between Bob's workstation and incoming.oogleborg.com can be erased after this step, but erasing the keys for the TLS sessions doesn't help with the plaintext copies that were left on Oohay and Oogleborg's servers!

If Alice's message is an OpenPGP-encrypted message, then you also need to answer: When does Bob erase all copies of his decryption key?  If it's not before Bob's laptop is compromised, then even if Bob has deleted old email messages, an adversary can use Bob's decryption key to decrypt ciphertexts of old email messages.

In contrast, here's the flow in Signal.

Alice's laptop encrypts the message and some ratcheting administrivia using her current key for Bob, and sends it to the Google mothership for distribution.

The Google mothership necessarily has a ciphertext copy of the message, and needs no keys.
Alice can now turn her ratchet and erase the key that would allow decryption of the ciphertext stored on the Google mothership.
After this point, if Alice has followed the protocol, only Bob has the key to decrypt the ciphertext or any way to derive it.

A couple days later, after Bob gets back from vacation, he logs into his workstation and downloads the ciphertext from the Google mothership.

If the ratcheting administrivia shows the messages are in order, Bob can now turn his ratchet and erase the key that would allow decryption of the ciphertext stored on the Google mothership.  (If the messages were delivered out of order, Bob has to hang onto the decryption key for a little longer.)
After this point, if Alice and Bob have followed the protocol, nobody has the key to decrypt the ciphertext or any way to derive it.

If Bob decides to delete old Signal messages (e.g., with ‘disappearing messages’, which are, of course, voluntary requests for the peer to respect, and which it is good etiquette to respect), then future compromise of Bob's workstation still isn't enough to decrypt ciphertexts of old Signal messages.

Could Bob rapidly rotate his OpenPGP encryption key pairs to achieve a similar effect?  Yes—if he erases them that's enough to prevent decryption of past ciphertexts.  But there's no OpenPGP tooling to do this automatically, and OpenPGP is enough of a pain to deal with without rolling keys over every Thursday that approximately nobody wants to deal with it, and there's certainly nothing in the protocol to automatically roll keys over after every message while also handling reasonable out-of-order delivery.

That's because OpenPGP was—from a modern perspective with the benefit of hindsight—designed as a toy for early '90s crypto nerds to spend all their time reconfiguring their email clients to handle, mashing ‘signature’ and ‘encryption’ together like LEGO bricks, rather than a protocol to facilitate human interaction like Signal with security goals studied in the cryptography literature.

To be fair to the early PGP designers, a good deal of crucial cryptography literature was evolving concurrently with the development of PGP during the '90s—but even when confronted with basic cryptographic problems in the protocol for humans, the designers abdicated responsibility for addressing them in 2001.  Despite contemporary literature on exactly how to address it, to this day OpenPGP doesn't support public-key authenticated encryption.  OpenPGP didn't even achieve what has for two decades been the cryptographic standard security notion of public-key encryption until 2018 when EFAIL persuaded the OpenPGP world to begrudgingly make the MDC mandatory—a decade and a half after being alerted to problems with the MDC in 2002.


$x^{1/y}$ is the $y$th root of $x$, i.e., the element $w$ that satisfies $w^y =x$.

If $x$ generates a group of prime order $q$, it can be shown that this element $w$ is unique and equals $x^z$ where $z$ is the inverse of $y$ modulo $q$. (One way to show this is to use the fact that $x^a = x^b$ if and only if $a \equiv b \pmod q$.)


Best practices: AES-GCM parameter (initialization-vector, ...) transport

Are both approaches fine?

Both are fine.  The entire point of GCM is that the ciphertext (and nonce and ciphertext) is protected, and so any method of transporting them is fine.

I do want to add one note: what the 'associated data' is typically used for is binding a ciphertext to a context.  For example, if you're encrypting database records, one thing you want to prevent is someone taking the ciphertext in one field, and copying it to another.  The associated data is designed to protect against that; if the associated data may be the record key, then the attacker can't do that; the record that the ciphertext is copied to would have a different key, and so the decryption would fail.

Because of this, the associated data typically has meaning to the application; depending on what you're protecting with GCM, what you have may be fine (e.g. if the application knows to look into the associated data you provided to verify the context), or it might not be.

  Is there a better way?

Cryptographically, you're fine, as I said.  As for whether there's a method that would work better (faster, cheaper) for what you're doing, well, you're actually more qualified to say than we are...


Is it OK to use a hash of the key as nonce for AES GCM?

I assume you mean AES-GCM.

Nonces must be unique for any use of a key. Given that $n = H(k)$ is constant for constant key $k$, this implies that such a nonce may only be used once, ever. Nonce reuse is particularly catastrophic in GCM mode (as with any other CTR-based mode), as it causes the keystream to be identical.

Essentially, you wind up with two (or more) ciphertexts $C_0 = K \oplus P_0$, $C_1 = K \oplus P_1$. An attacker can trivially compute

$$
\begin{align}
C_0 \oplus C_1 &= K \oplus P_0 \oplus K \oplus P_1\\
&= P_0 \oplus P_1 \oplus K \oplus K\\
&= P_0 \oplus P_1 \oplus 0\\
&= P_0 \oplus P_1
\end{align}
$$

If an attacker can control the contents of any plaintext, it's trivially game over. Even in the event that an attacker can't, knowing the XOR of two plaintexts is almost inevitably enough to reconstruct the originals.

In general, nonces and IVs for any mode must be unique for any given key. In CTR-based modes, uniqueness is the only constraint placed on the nonce. Other modes may have more stringent requirements; for example, CBC requires IVs to be unpredictable by an attacker. Failure to follow these requirements can result in a complete break of the  of the cipher.


Note the obvious: for Elgamal signature generation you must share parameters between users. If I (re-)read Elgamal encryption then it seems to me that parameter $p$ or $q$ (the safe prime) need to be shared in advance as well. Even though the generation of safe primes may be time consuming, you don't need to do this for each signature generation or decryption - the parameters may be static.

As for the key size, the key size of the prime must be about as large as those for RSA and DH keys. This is because the security is related to the hardness of the Diffie-Hellman problem. This means that you may look up the sizes on sites like keylength.com and look for the sizes required for "Discrete Logarithm" or the sources, for instance of NIST (US) or ECRYPT II (Europe), it references.

So there is no need to use primes that have additional properties over those required for Elgamal signature generation or encryption. Any generation of large primes will take large amounts of time compared to encryption/decryption. If you want efficiency then you can share (named) parameters.


What are the possible security issues when exporting a plaintext database to a file like this?

I'll start with the usual reminder: Please don't roll your own crypto, chances are you're getting it wrong.

For password databases, KDBX (KeePass' format) usually is a good example which you strongly should consider using. For an analysis of some format, also see "On The Security of Password Manager Database Formats" by Gasti and Rasmussen (PDF).

For understandability I'll quickly re-iterate your format more formally:

Header: $IV || \text{Salt} || E_{K,IV}(R||H(R)||0^{128})$
Data pairs: $\text{UsernameLength}||\text{Username}|| \text{PasswordLength} || E_{K,IV}(\text{password})$

where $E_{K,IV}$ denotes PKCS#7 padded AES-128-CBC encryption using the key $K$ and the IV $IV$ where $K$ is derived from $\text{MasterPassword}$ and $\text{Salt}$ as $K=H(\text{Salt}||r||\text{MasterPassword})$. The password is considered valid if the last header entry yields a consistent decryption. $R$ denotes a 256-bit random string and $r$ an 8-bit random string.

I'll start the answer with security issues of the format as stated and will conclude with potential security issues based on the information not given. The complete analysis is based on the recap I gave above, which is based on the comments given on InformationSecurity.SE, on the information from the question and the information given in the comments of this answer.

The first and potentially most devestating point: IV re-use. The scheme is re-using the IV for all encryptions which allows an attacker to detect the shared prefix between passwords. The mitigation is simple: Either use a well-established storage format, use a random IV for each encryption or encrypt the whole bulk data (including lengths and user names) in one go.

The second most interesting issue is that the lack of integrity protection. There is no authentication of the data, if an attacker changes any part of the ciphertext and the padding remains intact, the user won't notice that anything changed. This allows an attacker to run a denial-of-service attack on the user by cleverly introducing malicious changes into the plaintext, resulting in complains (caused by frustration of not being able to log-in) that your storage format is garbage, because the data won't be keepen and it could be leveraged to a scenario where the attacker can learn the password, by causing the user to reset his on a specific account and if the attacker broke the e-mail account he would know the new password without the user even suspecting an attacker sniffed the password. The mitigation is relatively simple: Use a well-established standard or use authenticated encryption (such as AES-GCM) paired with a proper alarming error message upon decryption failure like "this data has been maliciously corrupted".

The third security issue is the explicit length leaking. This scheme leaks the length of every single password, allowing an attacker to choose which to brute-force first and thereby easing up the attackers work significantly. The mitigation is again simple: Either use a well-established standard or do the encryption in one go over the entire data, so an attacker can't identify the exact lengths and where passwords start and end.

The last issue I could identify is that the username is leaked. This allows an attacker to potentially identify where the user is registered and run spear phishing attacks and / or brute-force attacks on the user. Additionally it may help an attacker to identify the user in leaked password dumps and use the file to recover possible password re-uses of this password (just try all sites you could identify with the otherwise leaked password and the given username). The mitigation is the same as for the previous point: Use a well-established standard or run the encryption over the entire data.

The scheme uses AES-CBC, which is completely unauthenticated which allows for many advanced attacks as detailed above, so the recommendation is to use authenticated encryption modes like AES-GCM, AES-OCB, AES-EAX or AES-CCM, which will take care of the authentication for you and use strong ciphers (e.g. AES).

The scheme uses very weak password based key-derivation, which requires up to 257 hashes and 4 AES encryptions to verify a password guess. This is extremely weak and allows for fast brute-force attacks on the master password, which is bad as many users will chose a weak password which requires few tries which will require a short amount of time, as 257 hashes and 4 AES encryptions are basically "nothing" to slow down a sophisticated attacker. The mitigation is clear as usual: Use a well-established format or use a strong PBDKF like Argon2, bcrypt or scrypt.

The header you're specifying lacks a mean to store parameters for password based key derivation. This implies that the scheme is vulnerable to simple progress of technology. To demonstrate the issue, simply look at TrueCrypt. It uses 1000 or 2000 iterations of a hash function for password based key derivation, which was fine a decade ago. The file format specification didn't allow for variable iterations and thus TrueCrypt is still using this low iteration count, resulting in minimal defense against password brute-force attacks. The mitigation is clear: Use a well-established scheme or store the parameters in your header.


Why does side-channel security focus on “shielding” rather than “jamming”?

Physically speaking, the crucial quantity is the signal to noise ratio: if a little bit of signal comes out on a given channel but also a whole lot of random noise, and you have no a-priori way of telling them apart, then extraction of the secret becomes exponentially inefficient.

Actually, it becomes quadratically inefficient.

For example, if you have a signal to noise ratio of 1::1000 (1000 times more noise than signal), then it takes approximately $1000^2 = 1000000$ samples to extract the noise.

Given that:

1000 times more noise than signal is quite a lot
1,000,000 samples is quite doable in some scenarios
The implementer would have to be quite careful to make sure that the signal cannot be extracted from the noise in some simple manner

That this approach is generally seen as mostly unworkable (and doesn't immediately address cache-based side channels).

In contrast, just designing the code to be constant time/memory access is, for the majority of primitives we're interested in, isn't that infeasible, and so that's the direction we tend to go.

In contrast, you appear to also be worrying about DPA style attacks, where the attack listens into the electronics (power draw, emitted EMF, etc).  Well, we can't actually design gates that literally don't change power dissipation and don't generate EMF while switching, and so in that scenario, the strategy changes.  When we do worry about that, the typical strategy is to include randomness, but not randomly (as you appear to be suggesting); adding randomness randomly would leave open the question of whether there is some nontrivial correlation present.  Instead, we either:

Use some mathematical property of the primitive we're using that allows us to include randomness without modifying the answer.  As a simple example, to do modexp (where the exponent is secret) over a prime modulus, we may rely on:

$$A^B \bmod P = A^{B+R(P-1)} \bmod P$$

where $R$ is a random value we pick for this computation.

Use threshold logic; where each logical bit of the computation is expressed as a function (often XOR) of $N$ physical bits, and each physical bit (actually, each set of $N-1$ physical bits) is uncorrelated to the logic bit; we use randomness to translate each logical bit into the actual set of physical bits to represent it.

The first strategy is often used for public key cryptosystems (which often have the internal symmetries we need); the second is usually used for symmetric systems (this strategy is significantly more expensive, however we don't have a cheaper alternative)


This has been answered on the PQC forum. The question was asked by El Hassane Laaji:

  Hello NTRU team

  Can you say me, why you didn't keep the NTRUencrypt-1024 release, is it because of > speed performance or security performance.

  Best regards.

The reply came from John Schanck:

  Thanks for your question. To clarify for others, the "NTRUencrypt-1024"
  parameter set was proposed in the first round NTRUEncrypt submission for
  use with the ss-ntru-pke and ss-ntru-kem schemes. I'll split your question
  into two parts:

  Why didn't we recommend ss-ntru?
  Why didn't we recommend an NTRU variant that uses Z[x]/(x^1024 + 1)?

  Regarding ss-ntru:

  At a fixed security level, NTRU and LWE schemes have a trade-off
  triangle between

  the correctness of the decryption procedure,
  the width of the coefficient distributions,
  the compactness of public keys and ciphertexts.

  The second round NTRU team wanted a compact scheme with a correct
  decryption procedure. The coefficient distribution used in ss-ntru
  is not compatible with that goal.

  Regarding Z[x]/(x^1024 + 1):

  It's not clear to us that there's a real need for an NTRU parameter set
  with such a large n. The largest n that we recommend is 821.

  Best,
  John (on behalf of the NTRU team)


Security of Deterministic Encryption Scheme

You might be limiting yourself at the wrong aspect there.

Your goal is the ability to search on ciphertext; and you just look at deterministic encryption in your set of tools.

In order to use DE securely, the messagespace HAS TO contain enough entropy in order to protect from brute-force search. The only way to solve this is adding entropy at random either in the encryption process and/or the message (e.g. extend message by a couple of random bits at the start).

But what you actually want is "Searchable Encryption", google scholar will help you out. For example Abdalla et al. published "Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions" and Boneh et al. published "Public Key Encryption with Keyword Search". However, I don't know if there are any implementations of these schemes, and probably they are quite huge: PEKS based on IBE, which is based on pairings in elliptic curves.


AEAD (for AES128-GCM): is it necessary to add a zero-length AAD?

AES-GCM does not support ‘no AAD’ as distinct from ‘zero-length AAD’.  See NIST SP800-38D for details of how it works internally: the AAD is padded with zeros so it is a multiple of 128 bits long, and the length is hashed in at the end.  If the AAD is zero-length, then zero bits of padding are added and no time is spent hashing any AAD or AAD padding.

  Let $u = 128\cdot\lceil\operatorname{len}(C)/128\rceil - \operatorname{len}(C)$ and let $v = 128\cdot\lceil\operatorname{len}(A)/128\rceil - \operatorname{len}(A)$.
  Define a block, $S$, as follows: $$S = \operatorname{GHASH}_H(A \mathbin\| \mathtt 0^v \mathbin\| C \mathbin\| \mathtt 0^u \mathbin\| [\operatorname{len}(A)]_{64} \mathbin\| [\operatorname{len}(C)]_{64}).$$

  …

  In Steps 4 and 5, the AAD and the ciphertext are each appended with the minimum number of ‘$\mathtt 0$’ bits, possibly none, so that the bit lengths of the resulting strings are multiples of the block size.

  —NIST SP800-90A, §7.1 ‘Algorithm for the Authenticated Encryption Function’, p. 15 (emphasis added)

Note that if the AAD $A$ is empty, then $\operatorname{len}(A) = \lceil0/128\rceil = 0$, so $\lceil\operatorname{len}(A)/128\rceil = 0$, and thus the number of ‘$\mathtt 0$’ bits appended is $$v = 128\cdot\lceil\operatorname{len}(A)/128\rceil - \operatorname{len}(A) = 128\cdot0 - 0 = 0.$$  In other words, if $A$ is empty, then the prefix $A \mathbin\| \mathtt 0^v$ is also empty.

But it is a good intuition to wonder whether ‘no AAD’ and ‘zero-length AAD’ are distinct!  There are many applications that do make such distinctions, often to the advantage of adversaries or at least to the frustration of legitimate users.


Is creating an OTP of a key to some data a secure secret sharing scheme?

Since you mention one time pads, I'll deal with one time pad (OTP) secret splitting rather than more complex schemes.  In this case, you don't fragment the key into pieces, you create additional keys exactly the same length and then chuck the original key away.  The only way to recreate the original key is to XOR all of the generated keys back together.  There is a good tutorial here.  You should be able to fathom the method from this extract:-

Taking these bullets one at a time:-

All the new keys are equally important.  You cannot reassemble the original key without all of the new keys.  One missing key will give you nothing.
Further to point 1, no there isn't anything that they can do.  Each original key character still has a certainty of 1/256 if you've used bytes.  Clearly if the key was only one byte long this would afford no security against a brute force attack.  So use a long key, or a key derivation function, but that draws away from the spiritual purity of the OTP.
You would probably use one single one time pad to spilt the original key.  You wouldn't be creating additional keys.  If your OTP generator equipment produces true randomness, the existence of additional OTPs will not create any mathematical vulnerabilities.  You do of course need to keep the many new keys safe as they are all required. That might be an issue in itself.  There are more complex key splitting techniques that don't require a OTP and can split a secret that then only require a subset of the keys to recombine the original.  You might consider this more secure in some circumstances (if some agents were to be eliminated by the enemy).