I think it is now valid to answer this question as this course is likely to be over.

First observer how CTR-mode works:
$C_1=E_K(IV)\oplus P_1$

As you can see, there's a linear relation between the plaintext and the ciphertext. You now use $C_1$ (observed) and $P_1$ (known). You want to make $C'_1$ decrypt to $P_1'$. To obtain this you first construct $\Delta P=P_1\oplus P_1'$. Now you induce $\Delta P$ into the $C_1$, yielding $C_1'=C_1 \oplus \Delta P=C_1\oplus P_1' \oplus P_1=E_K(IV)\oplus P'_1 \oplus P_1 \oplus P_1=E_K(IV)\oplus P'_1$, meaning the plaintext is as desired.

Now observe how CBC-decryption works. $P_1=D_K(C_1)\oplus IV$. By applying the same $\Delta P$ as above to the $IV$, you reach the desired effect: $IV'=IV\oplus \Delta P \Rightarrow P'_1=D_K(C_1)\oplus IV \oplus \Delta P=P_1\oplus \Delta P$. As $\Delta P$ is constructed such that the message body is changed in the desired way, the desired change is done upon decryption.


Is it ok to send part of digital signature if we have bandwidth constraints?

No, it is generally not OK to send only part of the signature, because then it can no longer be checked; that's unless we remove only very little of the signature; or unless the term signature is used for what really is a symmetric Message Authentication Code (in which case shortening only reduces the security, perhaps acceptably).

For any signature scheme, we can remove a few bits of the signature, say $k$, and define a verification scheme that accepts the signature if any of the possible $2^k$ original signatures matching the truncated signature is acceptable. The risk of forgery is increased by at most $2^k$ but might remain acceptable. The work to verify the signature is increased by at most $2^k$ (including not at all, if we count a deterministic secret-key MAC as a signature scheme, for it is just as easy to verify a truncated such MAC as it is to verify the original MAC).

When there's a single bit to trim from an RSA signature (as is often the case when a signature is enciphered using a different modulus having the same number of bits as the modulus used in the signature), there's a standard trick avoiding a doubling of the verifier's work: if the RSA signature is $S$, send $\widetilde S=\min(S,N-S)$, which saves 1 bits, and let the verifier compute $V={\widetilde S}^e\bmod N$; either $V$ or $N-V$ is the normal padded message representative, the right one being determinable by some characteristic of the padded message representative, like being even or having its few high bits clear.

When there are bandwidth constraints, more radical options are:

Giving up public verification and using a deterministic secret-key MAC, which is king in term of compactness.
Using a signature scheme allowing message recovery, such that (at least some of) the message is embedded in the signature, saving bandwidth. The standard such RSA schemes are defined by ISO/IEC 9796-2 free partial preview, which allows for example to convey any $b$-byte message as a cryptogram of $\min(256, b+22)$ bytes, when using 2048-bit RSA keys and SHA-1 (but beware that scheme 1, common in the Smart Card industry, could be vulnerable to attack in a chosen-message setup, and has no proven security reduction in other setups).
Using schemes designed for short signatures with appendix, such a BLS; unfortunately, this is relatively new, and no international standard has emerged, or even is in the work AFAIK.


Can two people with different one time pads securely exchange a message like this?

The general scheme is called Three-pass protocol and works for all commutative ciphers. It is secure for some of them, but xor (and modular addition) are insecure choices.

Your scheme:

A->B: $c_1 = m \oplus a$

B->A: $c_2 = c_1 \oplus b$

A->B: $c_3 = c_2 \oplus a$

B computes $m = c_3 \oplus b$

an attacker sees all of $c_1$, $c_2$ and $c_3$. So they can compute:

$c_1 \oplus c_2 \oplus c_3 = (m \oplus a) \oplus c_2 \oplus (c_2 \oplus a) = m$

and thus recovers the message.


Using a block cipher with timestamp instead of counter

A timestamp in the message won't fix the problem with ECB mode. ECB mode uses the same key for each block, so you will leak the fact that blocks are the same within the same message, and if you use the same key static key for every update, between different messages as well.

Consider a higher level library such as libsodium or spiped from tarsnap to avoid worrying about these details.


This is essentially a (bad) stream cipher. It has multiple problems:

You might hit a cycle much sooner than you'd want.
It's not parallelizable - this is a large performance issue on modern CPU's compared to algorithms that parallelize well.
The key is only inserted at one point of the stream, meaning if an enemy knows only one block of plaintext it can XOR it out to retrieve the internal state of the cipher compromising all further blocks.
There is no nonce, meaning that every cipherstream will be the same.

(5.)  Padding plaintext is not necessary in a stream cipher - you can simply discard the unneeded bits from the cipherstream.

However, the answer to the question in your title (What prevents continued hashing of a key from being used as a cipher when xored with plaintext?), is nothing. For example the ChaCha stream cipher works by repeatably hashing the key, nonce and an increasing counter for each block. Note that the hash function ChaCha uses is very specialized - it doesn't compress or is collision resistant, and as result can be much faster than "regular" hash functions that have much more stringent requirements.


Cryptographically secure hash function vulnerable to length extension attacks both to front and to back?

I think here it helps to examine the nature of length extension attacks, which have to do with the fact that practical hash functions are iterative.  They break up their input into a sequence of fixed-size blocks, and process each block successively, using the state produced by processing the previous block as an input into the processing of its successor.

Length extensions weaknesses exist because some hash functions are (mis?)designed so that their output reveals their state after processing the final block, and that allows the attacker to shortcut the computation of the hash result for messages whose block sequence extends that of the original.

One straightforward observation is that there while the most practical way to build such a hash function would be to process blocks in the same order they occur in the input message, there is no theoretical requirement to do so.  You could write a hash function that works exactly like SHA-256 but processes messages in reverse order.  It would be impractical because you would need to buffer whole messages in memory or in disk before you can hash them.

The fact that hash functions are vulnerable to length extensions at the end of a message but not at the beginning is just an artifact of that practical decision to process messages from start to end.


What do they mean when saying that a certain value should be “super-logarithmic”?

The term super-logarithmic in the paper you cite has nothing to do with the notion of a super-logarithm in Wikipedia. Rather, the intention is simply a function that is asymptotically larger than the $\log$ function. Formally, $f$ is super-logarithmic if $f(n)=\omega(\log n)$. The formal definition of "little-omega" appears in the Wikipedia entry on big-O notation.


Why does the prover in an interactive proof run in exponential time with the space of the computation?

The whole point of verifiable computation is to allow the verifier to verify that the computation was performed correctly without performing the computation himself. Since as usual we associate "polynomial-time" with "efficiently computable", if the computation takes poly time there is no point in using verifiable computation, since the verifier can just as well perform the computation himself.

In proof systems in general, if the verifier can determine by himself the truth of the statement in question, there is no need for a prover at all.


Should I include the ciphertext length in an AAD when using Chacha20+Poly1205 AEAD?

It is not necessary; ChaCha20+Poly1305 already includes the length of the ciphertext into the data which is MACed (and hence stirs it into the tag), hence you don't need to.  If someone appends or truncates ciphertext data, they'd change the data the MAC is computed over, and so the tag would not verify.

We can see the pseudocode (in section 2.8.1 of the RFC) which includes the ciphertext length in this line:

    mac_data |= num_to_4_le_bytes(ciphertext.length)
    tag = poly1305_mac(mac_data, otk)

Now, it won't hurt things if you decide to include the length into the AAD; however that's something that the designers have already thought of, and so you don't need to.


When a client connects to a SSL/TLS encrypted server it hashes the certificate, right?

The certificate isn't a secret. If all that's needed to impersonate a server was the certificate, everybody who ever connected to that server (which doesn't reject connections!) would be able to impersonate him.

What instead happens is the following:
The server sends a piece of data (the certificate) which binds a public key to a domain and potentially a company. This binding is done by a trusted CA and enforced with a signature which the client can verify.

In the next step one of two things happen:

The client encrypts the so-called pre-master secret with the public key from the certificate (which he knows belongs to the legitimate owner of the domain) OR
The server signs another (fresh) (DH) public key  which the client can verify was known to the legitimate owner of the domain. Now the client responds with his (fresh) (DH) public key.

Now there's a piece of information that only the legitimate owner of the private key associated to the certificate can know: Either the pre-master secret OR the private (DH) key. No matter which information is shared, now a "master-secret" is generated which cannot be pre-calculated because it includes randomness from both the server and the client. To finally verify both parties share the same master-secret (which is only possible if the server actually knew the private key from the certificate) they both exchange "secret-key-signatures" over all previous handshake messages and thus assure each other that they know the secret key. The identity of the server is thus confirmed (and not earlier than this).


generate a hash and validate if subset of string belong to that hash

In case hash is shorter than strings that are hashed it is not possible.
Suppose there is such algorithm $isSubstring(x, h)$ that tells if a string $x$ is a substring of a string $S$ whose hash is $h$.
If hash is shorter than message, then there are at least 2 different strings $A$ and $B$ that both produce the same hash $H$:
$hash(A) = hash(B) = H$
Sinse $A$ is a substring of itself, it holds
$isSubstring(A, hash(A)) = isSubstring(A, H) = true$
Sinse $B$ is a substring of itself, it holds
$isSubstring(B, hash(B)) = isSubstring(B, H) = true$
Then:
$isSubstring(B, hash(A)) = isSubstring(B, H) = true$
This means, $B$ is substring of $A$.
Also:
$isSubstring(A, hash(B)) = isSubstring(A, H) = true$
This means, $A$ is substring of $B$.
Thus, $B$ is substring of $A$ and $A$ is substring of $B$. This is only possible if $A$ and $B$ are equal. But we choose $A$ and $B$ that are not equal. This means that the assumption that such function exists is wrong.


In elliptic curve cryptography, how is "A dot A" computed?

You are correct that a line through a single point can intersect the curve in many other points. But you don't choose just any line. You choose the tangent through $A$. And that line will intersect the curve in exactly one point (which usually isn't, but may actually be $A$).

It is an interesting and useful exercise to actually do these computations with the formulae. Choose an elliptic curve, choose a point (not with $y$-coordinate $0$), find the curve's tangent line, then compute the remaining intersection point. (This is easy. You have two equations $Y^2 = X^3 + aX + B$ and $Y=\alpha X + \beta$. Eliminating $Y$, you get a cubic equation in $X$ and you know a double zero, namely the $x$-coordinate of the point you are trying to double.)


Can the original message be retrieved from a public/private key signature?

When I sign a message (which has potentialy low entropy) using a
  private key and i send it without the original message, can the
  original message be retrieved from the Signaturen?

It depends.
If you use a signature scheme with appendix it will be impossible to recover the message using other ways than brute-force (so the answer would be "yes" for low-entropy). This is the usual case for most signature schemes (like RSASSA-PSS and ECDSA). If you use a signature scheme with message recovery (quite rare, like ISO/IEC 9796-2) you can indeed recover the message.

  I want to prove over an unsecure channel that i know a secret password
  without revealing it

I suggest you give SRP a try for this.
It's specifically designed to combine password authentication with key-agreement (and thereby prove of knowledge of password).

  Could a man in the middle who does not know the original message
  create a signature using a different private key which would look like
  he knew the original message?

A signer needs to know the message in order to be able to sign it. If you can create a signature that is valid without letting the signer ever see the message, you have successfully broken the standard definition of security for this scheme.


Is there a recommendation or standard for using SCRYPT as an unbounded length KDF and not a fixed length authentication hash?

The signature for scrypt, straight from the source:

/**
 * crypto_scrypt(passwd, passwdlen, salt, saltlen, N, r, p, buf, buflen):
 * Compute scrypt(passwd[0 .. passwdlen - 1], salt[0 .. saltlen - 1], N, r,
 * p, buflen) and write the result into buf.  The parameters r, p, and buflen
 * must satisfy r * p < 2^30 and buflen <= (2^32 - 1) * 32.  The parameter N
 * must be a power of 2 greater than 1.
 *
 * Return 0 on success; or -1 on error.
 */
int crypto_scrypt(const uint8_t *, size_t, const uint8_t *, size_t, uint64_t,
    uint32_t, uint32_t, uint8_t *, size_t);

The last argument (buflen) is the output size.  You just give it the value you want (and that satisfies the requirements in the comment).

Given how simple this answer is, I would guess there's some missing context.  Maybe you are using a third-party library that reimplements scrypt or links to the original, but does not provide this parameter for the caller to specify.  In that case, well, then you have some options:

Use a different library that provides the full range of options;
Try to get the library patched to support the full range of options;
Use a key-based key derivation function like HKDF-expand to expand the short scrypt output your library provides.


Cryptographic notation in X3DH Key Agreement Protocol

The $DH(PK_1, PK_2)$ function is doing the usual elliptic curve Diffie-Hellman algorithm. The secret keys involved are implicit here; of course you cannot compute the shared secret key without them!  Notice that they omit the explicit use of the secret key in the $Sig(PK,M)$ function even though it too requires a secret key.
Yes, the $F$ value is used for domain separation. The input key material is the shared secret key from the ECDH function. Part of the point of an HKDF is to make the output key material appropriately pseudorandom for cryptographic use, and the ECDH shared secret needs this transformation. Finally, the HKDF info allows you to generate multiple keys with the same key material; see the comments here for more.


2 party AND computation under passive perfect security

The intuition behind the proof is as follows. Since the output of AND equals 0 when party P2 has input 0, then the transcript is distributed identically when P1 has input 0 and when P2 has input 1. Likewise, in the opposite direction. Thus, the set of possible transcripts when P1 has 1 and P2 has 0 equals the set of possible transcripts when both have 0, and the set of possible transcripts when P1 has 0 and P2 has 1 equals the set of possible transcripts when both have 0.

In the proof, they further show that the intersection of the set of transcripts as above is a subset of the set of transcripts when both parties have 1 (just by the definition of how the transcripts are defined).

As a result, the set of transcripts when both parties have 0 is a subset of the set of transcripts when both parties have 1.

The proof proceeds by arguing that the intersection between these sets of transcript actually has to be empty (since you can't output both 0 and 1). However, I actually think that the proof is already complete when they show that $T(1,0) \cap T(0,1) \subset T(1,1)$. In order to see this, let $t\in T(1,0)$; by what we have stated now it also follows that $t\in T(1,1)$. Since P1's output is determined by its input and transcript, it follows that it outputs the same bit in both cases. This contradicts correctness.

(I emailed with both Ivan Damgård and Jesper Nielsen on this; so thanks to them for them help.)


Looking for a secure PRNG that I can implement in hardware

First, you should not write your own CSPRNG - there are plenty of well vetted ones from which you may pick.

Second, your text and your pseudo code do not match (rotate key or rotate the seed).

Third, as I understand this algorithm it doesn't even give good randomness properties.  For example:

Main> let seed = `0x82398eeaf74239 : [64]
Main> let key =  `0x8732754279249  : [64]
Main> let out = take `{256} (prng key seed)
Main> out
0x5555555555555555555555555555555555555555555555555555555555555555


Why can't ransomware practically use RSA to encrypt all files?

RSA is really very slow compared with symmetric ciphers.
You can check this yourself running e.g. openssl benchmark:

openssl speed rsa

On my machine (and with openssl 1.1.1a) I get

Doing 2048 bits public rsa's for 10s: 330640 2048 bits public RSA's in 10.00s

so we can do ~33k encryptions per second and the size of the encrypted block is less than the modulus, so less than 256 bytes. If the attacker wanted to encrypt 1GB file, it would take about 2 minutes.
On the other hand,

openssl speed aes

shows that AES-CBC can encrypt ~300MB per second

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes  16384 bytes
aes-128 cbc      94234.08k   136019.99k   137980.25k   304759.81k   304166.23k   315654.14k

so the same 1GB file would be encrypted in 3 seconds.

For the attackers, speed is important, since the faster the files are encrypted, the less likely the process will be interrupted.


In TLS 1.3, all messages after ServerHello are encrypted. This encryption happens before EncryptedExtensions is sent. The traffic keys protect the record layer payload; they transform TLSPlaintext structs into TLSCiphertext structs.

During the handshake, the following messages are transmitted:

Client $\rightarrow$ Server: ClientHello (generate client nonce)
Client $\rightarrow$ Server: ClientKeyShare (generate ephemeral Diffie-Hellman parameter $X = g^x$)
Server $\rightarrow$ Client: ServerHello (generate server nonce)
Server $\rightarrow$ Client: ServerKeyShare (generate ephemeral Diffie-Hellman parameter $Y = g^y$)

At this point, both Client and Server can calculate the pre-master secret $g^{xy}$, and this is part of what goes into a PRF to derive a handshake master secret (HMS). Then you derive a handshake secret traffic key $t_{hs}$, which depends on HMS and the nonces.

The EncryptedExtensions message is the first one sent after $t_{hs}$ is generated. This and the rest of the handshake messages (like ClientCertificateVerify, ServerFinshed, etc.) are encrypted with $t_{hs}$. See how the keys are computed here.

You can see sample handshake traces here. (Since TLS 1.3 is still in draft form, this will be obsoleted soon.)


node-jose only supports RSA OAEP with SHA-1 and no MGF1 or RSA OAEP with SHA-256 and no MGF1

That's extremely unlikely since OAEP does need to use a Mask Generation Function, and there is only one defined: MGF1. So maybe it doesn't specify it explicitly, but it really must support it to be called OAEP.

  But I'm wondering about RSA OAEP SHA-1. Nimbus JOSE deprecated it, is it discouraged to use it? Has it been proven vulnerable?

No. Best to compare MGF1 with an expanding key derivation function probably. For this kind of use SHA-1 is still secure, even though the relatively small output size doesn't help. It certainly doesn't depend on the collision resistance.

However, I've had plenty of entities asking to deprecate SHA-1 in its entirety. The problem is that it is a huge red flag for auditors, who then have to look if the use of the hash is secure. And, to be honest, many auditors wouldn't know how to qualify if it is secure or not, so they see it as an avoidable risk. Which, to be honest, it probably is.

  But perhaps I'm going around this all wrong?

I don't know, it seems that Apple supports RSA for encryption if I look at the description here.


Secure Remote Protocol - Are these 2 equations equivalent?

Well, the bottom line is that it is equivalent.

The intermediate mod's do not modify the value of the expression; this is because all the arithmetic done by the expression (except for the calculation of the exponent (a + u * x)) is done modulo N; it is always safe to do intermediate reductions.

And, in this case, it's actually necessary; g^x is quite a huge number, and you really have to compute it modulo N, the actual value is just too big.

As for why B+ and N- instead of B-, well, it is likely that the modular exponentiation primitive that the programmer used wasn't able to handle negative bases.  By reducing the value of k * g^x modulo N (which is safe, as above), that value is always less than N; and so N - (k * g^x % N) is always positive, and so is B + (N - (k * g^x % N)).  Also note that this modification is also safe, because for all $A$, $B$, $N$, we have:

$A - B = A + N - B = A + (N - B) \mod N$

I would note that there are some further reductions that could have been done:

The exponent could have been computed modulo (N-1), as in (a + u*x) % (N-1).  This is a safe reduction because N is prime (and Fermat's Little Theorem); this would speed up the second modular exponentiation operation by giving it a smaller exponent.  Note that the modular exponentiation primitive cannot do it (it couldn't assume N is prime).
When computing (B + (N - ((k * (g^x % N)) % N)), they could have done a final % N to it; this might speed up the second modular exponentiation operation (by giving it a smaller base).  However, unlike the above operation, the code that computes the modular exponentiation might do that already (because that is always safe, whether or not N is prime).


Does there exist a cryptographic algorithm for comparing 2 encrypted strings

The simplest solution appears to be to:

eliminate the requirement to use two different keys

it will probably be impossible otherwise

use a randomized homomorphic encryption algorithm that can compute XOR

XOR computes differences, while you technically want equality; You could invert the output with a NOT gate to obtain the result of CMP (comparison), or you could simply check for a null string which would indicate equality.

With this solution, Alice would encrypt both messages under one key using a randomized homomorphic encryption algorithm.

Bob would compute XOR on the two ciphertexts and return the result to Alice.

Alice would then decrypt the ciphertext to obtain the result of the XOR of the two plaintexts, which indicates whether or not the two were different. This can be changed to indicate whether the two plaintexts were equivalent by inverting the result with a NOT gate, or simply checking for a null string.

If XOR was computed on the ciphertexts and $s_1$ and $s_2$ are equivalent, then the output will be a null string of 0s.

I mention CMP because it technically computes what you want (equality), while XOR computes the inverse of what you want (difference). They are effectively both the same, and you will likely want to find a cipher that offers XOR as one that offers CMP will probably not be directly available.

Ciphers for computing XOR

You could use the Paillier cryptosystem; It technically computes the addition of ciphertexts, but the least significant bit of addition happens to be equivalent to XOR. You would need to encode your message one-bit per ciphertext, which would probably take up a decent amount of space.

There is also the cipher from Fully Homomorphic Encryption Over The Integers; It also stores 1 bit per plaintext, but it relies on the hardness of the AGCD problem, which may not be as secure as we would like.


Rogue CA Certificate MD5 Collision Control

The reason for this is because it is impossible to generate an MD5 for just any $y$, where $y$ is the output of any $x$ that isn't pre-computed. MD5 is broken but it is not completely broken. Using the common terms, MD5 is broken with regards to collision attacks, but not broken with regards to pre-image attacks.

So your assumption that "Both methods require the "to be signed" portion of the certificate to be known" is not strong enough; a block (or two) in the to-be-signed portion should be pre-computed.

The to be signed portion is usually send to the CA in a certificate request. The CA uses the information in the certificate request and creates and signs the certificate that contains the information from the certificate request. This is usually automated, so if you can get past some filters you will be send the resulting certificate. At this point you can create a certificate that contains different information by altering the pre-computed block to create the correct MD5. Because the MD5 hash doesn't change the signature remains valid.

So the attack that's most potent is to pre-generate a certificate request for *.kzs8wf.com and a certain crafted public key forming the pre-computed block. You then receive the resulting certificate and then modify it to a *.google.com certificate with an re-calculated public key forming the altered pre-computed block.


Using PBKDF2 twice with different argument order

Is it subject to some class of attacks or is it just a really bad crypto nightmare which is only subject to brute-force attacks?

You are calculating PBKDF2 twice, which takes twice as long. An attacker doing a brute force or dictionary attack only needs to calculate one of them to verify his guesses.

That means you are making attacks twice as easy as they would be if you used PBKDF2 only once with twice the iterations, then used e.g. HKDF to quickly derive two keys.

Actually, if you use 128-bit keys and SHA-256 in PBKDF2, you can just split the output.

  More specifically: a is used as key to retrieve user data from the DB (thus, a is sent to server), data is returned and partially encrypted. You need b to decrypt what you get.

If $a$ is sent in the clear, an eavesdropper can use it for a brute force or dictionary attack, which would also find $b$. 2000 iterations of PBKDF2 doesn't make a password invulnerable to such attacks, although it obviously helps.

  Let's say that an attacker gets access to the database where these hashes are stored. What kind of attacks could he perpetrate?

Brute force and dictionary attacks, probably no easier than if only $b$ was known, but like I wrote above, twice as easy as if a better key derivation system was used.

Like the other answer mentions, if someone used their username as a password, that would be immediately visible as $a=b$, so no searching would be needed. However, that would be one of the first guesses in any case, so it probably isn't a big deal.


Designing a simple challenge-response symmetric mutual authentication protocol

You probably want to use HMAC instead of any hash function.
I will use the notation $H(K, x)$ to denote a keyed MAC.
Your simple protocol version seems to allow a reflection attack.
First the adversary $A$ initiates a session with $B$:
$A \to B$: $\mathrm{id}_A$, $n_A$
$B \to A$: $\mathrm{id}_B$, $n_B$, $H(K, n_A)$
Then $A$ initiates a second session with the nonce $n_B$:
$A \to B$: $\mathrm{id}_A$, $n_B$
$B \to A$: $\mathrm{id}_B$, $n_B'$, $H(K, n_B)$
Now $A$ sends $H(K, n_B)$ to Bob in the first session:
$A \to B$: $H(K, n_B)$
You always want to include the message number, and additionally, who is sending the message and who is receiving the message. You also want to authenticate every piece of that information.


Is it possible to safely implement the Signal Protocol (X3DH) without using XEdDSA

It turns out this is possible and has been implemented in the libolm library of Matrix.

The solution adopted in this library is to generate a signing key for each
user. This is an Ed25519 keypair, which is used to calculate a signature on
an object including both the public Ed25519 signing key and the public
Curve25519 identity key. It is then the public Ed25519 signing key which is
used as the device fingerprint which Alice and Bob verify with each other.
By verifying the signatures on the key object, Alice and Bob then get the same
level of assurance about the ownership of the Curve25519 identity keys as if
they had compared those directly.

Reference: https://gitlab.matrix.org/matrix-org/olm/blob/master/docs/signing.md


Yes $P_2$ can generate $\pi' \gets (\{ \exists r' \mid X' = X^{r'} \}, r)$, which proves that he knows $r$ that is the Dlog of $X'$. Since $r$ is chosen by him and $X$ is public, he can do this just as any normal DLOG proofs.

However, $P_2$ cannot generate $\pi'' \gets (\{ \exists xr' \mid X' = g^{xr'} \}, xr)$, which I guess is what you actually want. This would require $P_2$ to know $xr$, instead of just $r$.


Reversing decryption function involving XORs and bit rotations?

I'll demonstrate a "brute" way of doing it; should work for any XOR-rot system. Please note that indices are $\bmod 32$.

You basically write your equation in 32-vector and matrix notation:

$$
\bar{y} = M\bar{x} \oplus \bar{n},
$$ or in Einstein notation (which, in my opinion, can make stuff more readable)
$$
y_i=M_{ij}x^j \oplus n_i,
$$ where the sum goes from $i=1\dots32$.

Now, the magic part (to solve the rotation) lies in finding the $32\times32$ matrix $M_{ij}$:

$$
M_{ij}=\delta_{ij}\oplus\delta_{(i+3),j}\oplus\delta_{(i-7),j},
$$ where $\delta_{ij}$ is the Kronecker delta symbol (the unit matrix):

$$
\delta_{ij} =
    \begin{cases}
            1, &         \text{if } i=j,\\
            0, &         \text{if } i\neq j.
    \end{cases}
$$
Now your problem is reduced to inverting $M_{ij}$ (which is a one-time static thing), and calculating

$$
\bar{x}=M^{-1}(\bar{y}+\bar{n})
$$


Would using two keys for Salsa20 or ChaCha increase security?

Would using the keys (as in two passes with a key each) increase
  security for Salsa20 or ChaCha stream ciphers increase security?

More or less.
It wouldn't increase the difficulty of brute-force by a lot (one bit to be precise) due to the infamous meat-in-the-middle-attack if you would use the same keylength, if you used different ones the effective keylength would be the higher of the two lengths.

What it would do though, is to increase the cryptanalytic security of the construction. Ie an attacker would have to successfully break both ciphers with cryptanalysis which is indeed more unlikely than him breaking one.

Is it worth it? No. The extra keybit is not that valueable and it's already a matter of "meh, can't break" anyways even with a single cipher. Regarding the cryptanalytic defense, neither ChaCha nor Salsa have been broken, but these ciphers are quite similar so you don't get the advantage you would get from two ciphers with radically different designs.


Seeking special-use fingerprinting/hashing algorithm

For cryptographic hash functions we usually want to avoid collisions as much as possible (and even more we want to avoid any way to get from the output back to the preimage).

So what you want certainly is not a cryptographic hash function, but something else.

On the first look, something like a CRC (cyclic redundancy check) could fit your bill. These have the property that they reduce arbitrary-length messages to fixed-length checksums ($n$ bit for a CRC-$n$), and given a $n$-bit checksum and a prefix of a string with only $n$ bits missing, it requires just some linear algebra to compute the exactly one postfix missing. (You can have other parts missing instead, but then the computation is a bit more complicated.)

So assuming your datablocks are $m$ bit, we have the functions
$$\def\Z{\mathbb Z}\def\invC{\operatorname{inv}\!CRC} CRC : \Z_2^m \to \Z_2^n,$$
$$ \invC : \Z_2^{m-n} \times \Z_2^n \to \Z_2^m, $$
where $\invC(x,y)$ has $x$ as the first $m-n$ bits, and $CRC(\invC(x,y)) = y$.

I'm not sure if this fits your bill - you could have $y$ as key and $x$ as index, or the other way around.


What does a vertical bar mean in this context?

The meaning of that $\ \vert\ $ in this context is divides (as in evenly divides, or is a divisor of), and that's a standard usage of this sign. The quote should be read as:

let $p=311$ and $r=31$, which divides $(p-1)$. Let $g=169$…

In other words: $r$ is a divisor of $p-1$. Or, exists integer $q$ with $r\times q=p-1$. Or, $((p-1)\bmod r)=0$, also writable as $p-1\bmod r=0$ or $p-1\equiv0\pmod r$ or $p\equiv1\pmod r$. In many common programing languages, (p-1)%r == 0. That's because $31$ (evenly) divides $311-1$, since $31\times10=310$.
That was correctly guessed by Aman Grewal in comment, but as noted, proximity with the assignment makes the notation confusing. Elision of the implied which is something I would try to avoid.

The end of the sentence says «Let $g=169$, which has order $r$». Does that mean that $g$ is really 169%31?

No. The term order is used in its meaning in group theory. In this context, it means that when we repeatedly multiply $1$ by $g$, reducing modulo $p$ after each multiplication, we'll first get back to $1$ after performing $r$ multiplications. That's related to $r\,\vert\,(p-1)$, because the order of any element in a finite group is a divisor of the order of the group, that is the number of elements in the group. Here the group is the multiplicative group modulo $p$, noted $\mathbb Z_p^*$ or $(\mathbb Z/p\mathbb Z)^\times$, which has $p-1$ elements since $p$ is prime. The powers of $g$ form a subgroup of order $r$, called a Schnorr group.


Is there are a metric based on collisions to compare bad hash functions?

There are a few standard quantities related to families of hash functions $H_k\colon \{0,1\}^m \to \{0,1\}^h$ for a uniform random key $k$.  You might call them metrics.  They came to prominence in Carter and Wegman's research program on universal hash families (paywall-free), though their first use in cryptography for one-time authenticators, by Gilbert, MacWilliams, and Sloane (paywall-free), predated the Carter–Wegman program by several years.

An upper bound on $\Pr[H_k(x) = u]$ for any $x \in \{0,1\}^m$ and $u \in \{0,1\}^h$.  If it is $1/2^h$, then we say the family is equidistributed.
An upper bound on $\Pr[H_k(x) = H_k(y)]$ for any distinct $x, y \in \{0,1\}^m$.  For example, if it's at most $1/2^h$, we say the family is universal; if it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost universal.  The quantity $\Pr[H_k(x) = H_k(y)]$ is sometimes called the collision probability.
An upper bound on $\Pr[H_k(x) \oplus H_k(y) = u]$ for any distinct $x, y, \in \{0,1\}^m$ and any $u \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost xor-universal.
An upper bound on $\Pr[H_k(x) = u, H_k(y) = v]$ for any distinct $x, y \in \{0,1\}^m$ and any $u, v \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^{2h})$, we say it's $\varepsilon$-almost strongly universal or $\varepsilon$-almost pairwise independent.
An upper bound on $\Pr[H_k(x_1) = u_1, \dots, H_k(x_n) = u_n]$ for any distinct $x_i \in \{0,1\}^m$ and any $u_i \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^{nh})$, we say it's $\varepsilon$-almost $n$-independent or $n$-universal.

There are standard provable examples of functions attaining optimal or near-optimal values of the above bounds.  In cryptography, these bounds are relevant to one-time authenticators such as Poly1305 and GHASH, which are based on equidistributed $\varepsilon$-almost xor-universal hash families for $\varepsilon \approx \lceil m/128\rceil/2^{128}$, as well as to other applications such as hash tables with non-adaptive adversaries.  The quantity $\Pr[H_k(m') = a' \mathrel| H_k(m) = a]$ for $m' \ne m$ is sometimes called the forgery probability.

An $n$-independent hash family has the property that the probability of a collision $H_k(x) = H_k(y)$ for distinct $x, y \in S$ in a subset $S \subseteq \{0,1\}^m$ of $n$ elements is $$1 - \frac{2^h!}{(2^h)^n (2^h - n)!} \approx 1 - e^{-n^2/2^{h + 1}}.$$  However, the key must be enormous to guarantee this.  Further, none of these bounds guarantees anything about the difficulty of deliberately computing a collision knowing the key.

What you are probably getting at is not collision probabilities for unknown keys, but rather the collision resistance of a hash family:

An upper bound on $\Pr[x \ne y, H_k(x) = H_k(y)]$ where $(x, y) = A(k)$ and $A$ is any random algorithm.  If this negligible when the expected cost of $A$ is below $\sqrt{2^h} = 2^{h/2}$, we say the family is collision-resistant.

In particular, if $B_t(f)$ is a random algorithm that applies the birthday paradox to $t$ uniform random inputs to $f\colon \{0,1\}^m \to \{0,1\}^h$ as an oracle and returns a collision if there is one (for example, using van Oorschot and Wiener's parallel collision search machine), then for any equidistributed $f$, $$\Pr[x \ne y, f(x) = f(y)] = 1 - \frac{2^h!}{(2^h)^t (2^h - t)!} \approx 1 - e^{-t^2/2^{h + 1}},$$ where $(x, y) = B_t(f)$.  When $t^2 \lll 2^h$, so that $t \lll \sqrt{2^h} = 2^{h/2}$, this is negligible in $h$.  The best generic attack on $H_k$ with cost $t$ is $A(k) = B_t(H_k)$; if there is no known attack better than this we say that $H_k$ is collision-resistant.

We don't know how to prove this for all random algorithms $A$, however, so this property can only be conjectured of hash families for which we haven't figured out a cheaper collision search algorithm.  For example, we are quite confident that Poly1305 or GHASH is not collision-resistant; it is trivial to compute two-block collisions under any key with one field multiplication and one field addition.  We conjecture that keyed BLAKE2 is collision-resistant because nobody has figured out how to make it collide.

It is of little use to empirically study collision resistance by sampling outputs of a generic hash function.  If you try to use the generic birthday algorithm on Poly1305 or GHASH, it won't do much better than it will on keyed BLAKE2.  But it doesn't take a genius of a cryptanalyst to immediately recognize there is a trivial algorithm to find Poly1305 and GHASH collisions, given the key, much faster than the generic birthday algorithm.  The best we can do is to empirically study it by sampling algorithms for finding collisions—asking a lot of smart cryptanalysts to try to think of them.  So far, empirically, nobody has thought of a way to find collisions in keyed BLAKE2.

Since sampling outputs is not useful for studying collision resistance, when studying simplified versions of hash families, we don't normally study a progression of truncated output sizes. Rather, we structure the hash family to iterate some internal scrambling function for a variable number of rounds, and study a progression of numbers of rounds.  For example, the best known collision attacks on reduced-round versions of BLAKE apply only to 5 rounds, which is why the BLAKE2 designers felt comfortable recommending only 10 rounds.

Loosely, we sometimes also pick a fixed hash function such as SHA3-256, and say that it is collision-resistant if nobody has found a way to compute a collision under that fixed hash function.  Of course, if $h \leq m$, we are guaranteed that a collision exists, so there must exist a trivial random algorithm of negligible cost to compute it: namely an algorithm that simply returns the collision without doing any computation.

So there's no nice way to formalize this, but in practice, it seems to be hard.  Twenty years ago, it was conjectured that SHA-1 was collision-resistant in this loose sense, until someone figured out a way to compute SHA-1 collisions at lower cost than the generic attack in 2004, and then someone published an actual collision last year.  Today, it is still conjectured that SHA-256 is still collision-resistant in this loose sense.


Is there a single-use signature scheme, where a second use of the private key discloses it to the world?

Trivial solution: generate a random $k$ as part of the private key and include $r$ as part of the public key.

The verifier uses $r$ from public key, so the signer must use the same $k$ for every valid signature. The signer could create multiple related public keys and reuse $D_A$, but then, they might as well just create multiple key-pairs in the first place.


Which encryption is recommended for own messenger

TLS, without a doubt. Note that TLS does not imply HTTP, so you can use it with whatever TCP protocol you have.

For UDP you can use DTLS, which I believe forces the use of CTR mode to combat packet loss.


Do parts of a hash carry the properties of the entire hash?

Yes, starting from a appropriately good hash or MAC, removing output bits demonstrably does not weaken it beyond the limit imposed by the number of remaining bits, with regards to collision-resistance and preimage-resistance, and other useful properties (such as impossibility to guess anything on the output without knowledge of the input). Put simply, if a standard hash is entirely unbroken, its restriction is unbroken.

More precisely, one appropriately good condition is secure in the Random Oracle Model. For a MAC, it is also enough that without the key, no attacker could harness enough computing power to distinguish the function from a random function with odds better than 50%, given access to an unlimited supply of $(input,output)$ pairs with $input$ iteratively chosen. For a Merkle–Damgård hash like $SHA256$ there are additional technicalities [we replace the key with the constants in the definition of the hash, and posit that they have been chosen at random; also we must make an exception for the length-extension property: from the length of a message $M$, it is trivial to construct extensions $E$ so that $H(M||E)$ is efficiently computed from $H(M)$ without knowledge of $M$].

Proof: If a function is secure in the Random Oracle Model or/and computationally indistinguishable from a random function, then a restriction with less output bit is also secure in the Random Oracle Model or/and computationally indistinguishable, because removing bits deprives an attacker of information and can only increase the difficulty of a distinguisher. Being secure in the Random Oracle Model or/and computationally indistinguishable implies collision-resistance and preimage-resistance within the limits of the number of bits in the output, both for the original function and its restriction.

It is not appropriately good that breaking collision-resistance or/and preimage-resistance of the original hash or MAC is computationally hard. For example consider $H(M) = C||SHA256(M)$ for some 256-bit constant $C$. This 512-bit hash is at least as collision-resistant and preimage-resistant as $SHA256$, which is rock solid. Yet a restriction to its left 256 bits is the constant $C$, and offers no security at all.


Thanks to the help of @kelalaka i found a solution.
The idea
My exploit was based on the fact (I don't really know if it's always true) that if $r \cdot mo < n$ the oracle won't print anything, otherwise it will print some number, which unfortunate is not $r \cdot mo$.
So, $\lfloor \frac{n}{mo} \rfloor^e \cdot (mo^e \mod n)$ would produce no answer ($\lfloor \frac{n}{mo} \rfloor \cdot mo < n$) while $\lfloor \frac{n}{mo} + 1\rfloor^e \cdot (mo^e \mod n)$ would produce an answer, even if uncorrect.
The solution
First I choose a number $r$ smaller than the original message $mo$. Then, until the oracle responds i keep sending $r\cdot 2^i$ increasing $i$ by $1$ each step.
When the oracle respond it means that I found a number $s = r\cdot 2^{i-1}$ such that

$s < mo$
$2s > mo$

Let $k:=\frac{s}{2}$. I iterate the following process until $k > 0$:

I send $s+k$.

If the oracle responds it means $s+k > mo,$ so I assign $k:=\lfloor k/2 \rfloor$
If the oracle doesn't respond it means $s+k < mo,$ so I assign $s:=s+k$

In the end $s$ should be exactly $mo$.
The "algorithm" (it's a bit confused, I'm sorry) I proposed should get $mo$ in $O(\log_2 n)$ so it's tractable.


The Denning-Sacco protocol is a key transport protocol designed for use over an insecure network. It adds timestamps to the Needham–Schroeder protocol to prevent replay attacks. Rishav Bhowmick, "Denning Sacco Protocol", summarizes the protocol as:

$A \rightarrow S: A,B$
$S \rightarrow A: E(K_{as}: B, K_{ab}, T, E(K_{bs}: A, K_{ab}, T))$
$A \rightarrow B: E(K_{bs}: A, K_{ab}, T)$

The entire point of the protocol is that $A$ and $B$ both need to know a shared secret key ( $K_{ab}$ ), but they don't already have a shared secret key at the beginning of the process – typically because key management is more convenient for Bob to remember and keep secret a single secret key shared between Bob and the central server ( $K_{bs}$ ) rather than a hundred secret keys shared between Bob and the hundred people Bob needs to communicate with.

It certainly would be faster and easier to A to generate a key and send it directly to Bob (skipping steps 1 and 2), but that would be insecure.
After Alice generates a key, there seems to be only 2 ways Alice can send that key directly to Bob:

Send the key Kab encrypted with some other key $Kold$ – perhaps something like $A \rightarrow B: E(Kold_{ab}: K_{ab}, T, etc.)$ – but why? If Alice and Bob already had a shared secret key $Kold_{ab}$, then there's little point to using DS to send another key, and if they don't, then Bob has no way of decrypting that message.
Send the key Kab in $plaintext: A \rightarrow B: K_{ab}$. This allows everyone listening to hear the key $K_{ab}$ and decrypt all the messages between $A$ and $B$ encrypted with that key, and it allows active attackers to inject messages of their choice encrypted with that key that might trick Alice or Bob into thinking the message came from the other.


Definition of cryptographic advantage vs. probability of success

Advantage and success probability are just words. Their meaning is in practice decided by how the speakers of the language use the words. You have observed that people use the terms advantage and probability in this way. One could probably argue that this is confusing or illogical or something like that, but such is language.

About dividing by two: remember, the advantage is just a number, and numbers can be divided by two and compared to other numbers. Sometimes, we are able to prove that one number is larger than the difference of two other numbers.

(As for the equation you mention, I think two terms are "advantages" and one term is a "probability".)


Does Java SunJCE Provider use AES for encrypting nonce in Poly1305?

If we look into the source code of the JDK 11 where this feature was introduced, we can see it is based on RFC 7539, not on RFC 8439. However, a quick look showed that they may be compatible none-the-less.

although the Poly1305 MAC is defined using AES, the AEAD cipher is not;
the AEAD construction is defined in section 2.8 and points to 2.6: Generating the Poly1305 Key Using ChaCha20.

So the nonce is taken directly as a parameter, and it is not generated by the application at all. However, the Poly1305 key is generated from this nonce. Note that a MAC does not require an IV or nonce otherwise, only a key. For Poly1305 that key needs to be unique, which is why it is calculated from the nonce used by the ChaCha20-Poly1305 AEAD cipher.

So the authentication tag is protected using a ChaCha20 block encrypt rather than AES:

    authenticator = new Poly1305();

    // Derive the Poly1305 key from the starting state
    byte[] serializedKey = new byte[KEYSTREAM_SIZE];
    chaCha20Block(startState, 0, serializedKey);

    authenticator.engineInit(new SecretKeySpec(serializedKey, 0, 32,
            authAlgName), null);

In other words, the ChaCha20Cipher class which implements the  ChaCha20-Poly1305 AEAD cipher (using the Poly1305 authenticator class) doesn't mention or reference the AES or any other block cipher.

Note that I've previously mentioned in a deleted answer that stream ciphers can generally not be used to perform this kind of key derivation from the nonce. This is correct; however, ChaCha20 operates on blocks underneath, which makes these kinds of operation possible none-the-less.

What was correct in the deleted answer is that the block encrypt for creating the key for Poly1305 is performed only once, so any speed difference between block ciphers to derive the key is inconsequential for larger messages. Only the Poly1305 calculation is performed over the whole message - that's the whole idea of these fast MAC implementations that enable "1.5 pass authenticated ciphers".


Deterministic Authenticated Encryption with AES-OFB and HMAC

Does this design provide deterministic authenticated encryption?

This provides reasonable security as long as you limit the total volume of data encrypted to well below $2^{64}$ bytes.

Details.
The SIV theorem[1], roughly, is that if $F_{k_1}$ is a $t$-bit PRF, with PRF distinguisher advantage bounded by $\varepsilon_F$, and if $E_{k_2}$ is a randomized cipher, with CPA distinguisher advantage bounded by $\varepsilon_E$, then $$m \mapsto F_{k_1}(m) \mathbin\| E_{k_2}(F_{k_1}(m), m)$$ with decryption $$t \mathbin\| c \mapsto \begin{cases} m, & \text{if $F_{k_1}(m) = t$;} \\ \bot, & \text{otherwise,} \end{cases} \quad \text{where $m = E_{k_2}^{-1}(t, c)$,}$$ is a deterministic authenticated cipher with distinguisher/forgery advantage bounded by $\varepsilon_F + \varepsilon_E + q^2/2^t$ for any adversary making at most $q$ queries to $E$ or $F$.

Under standard conjectures about SHA-512, the PRF advantage of a $q$-query cost-limited adversary against a 128-bit truncation of HMAC-SHA512 with a 512-bit key is bounded by about $q/2^{128}$.
Under standard conjectures about AES, the IND-CPA advantage of a $q$-query cost-limited adversary against AES-OFB with a 256-bit key and messages up to $\ell$ blocks long is bounded by

$q^2 \ell^2/2^{128}$, if the IVs are unique, and therefore
$q^2/2^{128} + q^2 \ell^2/2^{128}$, if the IVs are chosen uniformly at random, as SIV hypothesizes.

Summing up, the adversary's advantage is bounded by about $$\frac{q}{2^{128}} + \frac{q^2 \ell^2}{2^{128}} + \frac{q^2}{2^{128}} + \frac{q^2}{2^{128}} = \frac{q + 2 q^2 + q^2 \ell^2}{2^{128}}.$$

I say ‘about’, because this excludes the probability of guessing $k_1$ and $k_2$, which, if they are 256 bits, is minuscule in comparison even in a multi-target attack on $2^{64}$ users; and this excludes the probability of an internal collision in HMAC-SHA512, which is also minuscule in comparison.  The dominating term $q^2 \ell^2$ is the total number of blocks encrypted.  Hence: keep the total volume of data encrypted well below $2^{64}$ bytes.  A limit of a few gigabytes should be fine.

The real SIV, as presented in the paper and standardized with CTR mode, also handles associated data with a custom tuple PRF construction, instantiated with AES.  The custom tuple PRF doesn't matter if you don't have associated data, and the instantiation with a PRP like AES instead of a PRF like HMAC actually hurts security a little (by the standard PRP/PRF switching lemma).

  Is there a better design that would allow searching on the encrypted data?

This looks to me like the easiest secure option with the tools you have at hand.

You could derive a fresh AES key for each message, and cut it down from 64 bytes of key material to 32 bytes of key material, but there's a cost—switching AES keys is more expensive than switching AES-OFB IVs, and you'd have to call HMAC-SHA512 twice or something—and there's no benefit to security unless you expand the tag from 128 bits to 192 or 256 bits.

You didn't ask, but you perhaps should have asked:

  Are there any implementation pitfalls to be aware of?

Make sure that you do not touch the unauthenticated plaintext except to compute the authenticator until after you have verified it.  Unauthenticated data is pure evil—don't touch it!
Make sure that you don't use PKCS7 padding or anything.  Make sure that the AES-OFB decryption cannot fail, because failure of the decryption distinct from failure of the authentication might leak information about the plaintext in a padding oracle attack like BEAST.
Make sure to write test vectors in another language to cross-check and perform self-tests.

Finally, encrypted database search is a goldmine for attackers even if they can't see the content of the encrypted field[2] (popular exposition).  Caveat data hoarder!


If the checksums (MD5 or SHA...)

First things first: there is a BIG difference between a checksum (aka “cyclic redundancy checks” like CRC32) and a hash (aka “cryptographically secure hash functions” like MD5 and the SHA families).

The biggest difference between checksums and hashes is that checksums are neither build, nor meant to be cryptographically secure. (Checksums are mainly used for error detection; eg after file transfers.) To get a better understanding of the different categorisations, you might want to take a look at Wikipedia: List of hash functions.

Anyway, let’s get to the core of your question…

  Is Checksum to file back decoding possible?

No, that’s not possible. Neither a checksum, nor a cryptographically secure hash enables you to rebuild the data it was created from. The reason is simple: both hashes as well as checksums are one-way functions. They “compress” the information down to a level that makes it infeasable to revert them.

In fact, you could almost compare them to lossy compression algorithms which compress information beyond the point of recoverability, but in a way that even a single bit change of the original file will result in a completely changed hash or checksum.

Especially when talking about cryptograhically secure hash functions like SHA2, SHA3, et al (MD5 is regarded not to be so secure anymore in all cases), you should note that an ideal hash function has three main properties:

It is extremely easy to calculate a hash for any given data.
It is extremely computationally difficult to calculate the data which was used to create a specific hash.
It is extremely unlikely that two slightly different messages will have the same hash.

Here, “extremely difficult” practically tends to boil down a situation where “brute-force” is your only chance. So, the receiver of your 700 MB video file would need to create several thousands of versions of 700 MB files using random data, then hash that data and only if the hash fits your hash, the receiver would be sure to have a copy of the file you hashed.

Simpler said:

Creating a checksum or hash is very much different from a regular data-compression algorithm like ZIP/deflate. If you test things yourself, you’ll quickly notice that even the best file-compression program will not be able to shrink your 700 MB video file down to a few hundred bytes… for a good reason. Those programs need enough data to reconstruct the original file. A hash or checksum doesn’t offer any such “decompression” functionality as it isn’t meant to do that in the first place (see emphasised point of above property list).

Both hashes and checksums produce a (let’s just call it) “unique summary describing the data”, but they do not hold, contain, or are able to reproduce the original data.


What exactly could be accomplished with a backdoor in Dual_EC_DRBG?

State update takes $s$ to $x(sP)$, so you would have to compute d.log.s to run the state backwards.


plaintext decrypted form a cipher text using key = 3 in Caesar Cipher and that plain text with the following ciphertext to get the key

Take original plain text as " PLEASEEECUSEMYDEARAUNTSALLY", note that I've ignored the 'X', so that rail fence with key(row depth) = 4 cipher text will be "PEMALLEEEYRUALESCSDANSYAUET" now using Caesar cipher with k=4 on this new text.
${C= (P+k)mod26}$ , you will get cipher as $${"TIQEPPIBICVYEPIWGWHERWCEYIX"}$$

Here we take row wise so P --> T, E-->I, M-->Q, A-->E, L-->P,
in second row L-->P,E-->I and so on...


Function to derive an integer from a given password

If you have access to a PBKDF2 implementation, I'd just take a 8 byte output of PBKDF2. Whether that's a Little Endian or Big Endian value doesn't matter so long as you're consistent.

Since PBKDF2 has good spread, a 64-bit capture from it gets a 50% chance of collision around the 5.1 billionth different input, still down at 1% around 600 million.  (See the table on Birthday Attack.)


IPsec : transmission of Initialization Vector

Yes, the initialization vector is transmitted in the clear as first part of the ESP payload data (see RFC 4303, section 2, and the RFCs that define the use of specific algorithm with ESP, e.g. RFC 3602, section 3 for AES-CBC, or RFC 4106, section 3 for AES-GCM).

The security of the encryption and integrity protection does not depend on the IV being kept secret. Its primary use is that of a nonce to ensure encrypting the same data with the same key does not result in the same ciphertext.

Some algorithms require that the IV is random/unpredictable (e.g. AES-CBC) but in many modern combined mode algorithms (e.g. AES-GCM or ChaCha20/Poly1305) it just must not repeat and can simply be a counter.

Under certain conditions it might not even be necessary to transmit the IV, for instance, because it can be derived from other information, like the sequence number in ESP. Therefore, there is currently an internet draft under discussion that proposes to omit the IV for certain algorithms (e.g. AES-GCM) and instead just use the (extended) sequence number, which is what's generally already used anyway, it's just transmitted twice in each message.


When was the RSA 64-bit key introduced into internet encryption?

The RSA paper from 1977 recommends the following on page 9:

  We  recommend  using  100-digit  (decimal)  prime numbers p and q, so
  that n has 200 digits.

200 digits is 663 bits, which would have been pretty strong in 1977. Due to the US government instituting export controls on cryptography in the early 1990s, 512 bit RSA became widely implemented as it was the maximum allowed for export.  I can't find any examples of keys smaller than 512 bits being used in practice, other than in the RSA factoring challenge.


The idea in [1] (disregarding reception errors) is to first remove the impact of the message. This is done by computing the syndrome

$\qquad\qquad\mathbf{H} \mathbf{v} = \mathbf{H} (\mathbf{m} \oplus \mathbf{k}) = \mathbf{H}\mathbf{k}$.

In the case of a ${1}/{5}$ repetition code, this could correspond to adding even number of (bold) codeword symbols together (since it is a repetition code they should be equal, right?), forming linear equations containing only keystream bits. Then, by exhaustively trying all $2^{16}$ starting states, it is possible to mount an attack (for each starting state) consisting of Guassian elimination, solving for the session key.

I found a reference implemenation at [2], which you might want to check out.

[1] http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf

[2] http://www.npag.fr/project-a52hacktool


Industry standard recommendations for memory usage defaults for a password hashing function?

If it's for a single user workload (e.g. passphrase to key derivation for encryption / cold storage of private key, local login): explore the largest that's unlikely to cause disk paging or equivalent (including memory compression) on any of the targeted platforms, divide by 2 just in case, and round down to the nearest size parameterizable.
For servers workloads, one wants to comfortably fit the largest fast cache (e.g. L3 if present, or L2) to conserve energy and CPU power; thus: take that cache size, divide by the physical number of threads sharing it (often twice the number of physical CPUs, and rarely more), divide by 2 so that some cache is left, and round down to the nearest size parameterizable. For multi-thread password hashing, that's assuming some parametrization or lock insures there's never more threads password-hashing than there are physical number of threads.
If I had to throw a reasonable number without knowing context, I'd make it 128kiB to err on the functional side (at the expense of not making use of the DRAM on many platforms, thus making security less than it could). I do NOT claim this is an industry standard in any way.
Reasons to choose less: avoid becoming intolerably slow and energy hungry on more platforms.
Reasons to choose more: increase the investment and to a degree operating cost for attackers.


If you don't get the expected result, then you are doing it wrong; most probably, use wrong mode of operation and/or wrong padding. You can get the expected result with openssl as

openssl enc -e -des-ecb -in plain.txt -out cipher1.txt -nopad -K 0101010101010101 -iv 0
openssl enc -e -des-ecb -in cipher1.txt -out cipher2.txt -nopad -K 0101010101010101 -iv 0

plain.txt file size should be multiple of 8 (8 bytes is DES block size), and plain.txt and cipher2.txt files should be identical.


basic question regarding two-time pad attack

This is not the two-time pad attack this is the malleability of the OTP or any stream cipher. Malleability means that the active attacker can change the ciphertext into another ciphertext that can be decrypted without any error during the decryption. That is why we need integrity and authentication.
How it works; you sent $m\oplus k$ on the communication channel, the active attacker captures (and probably stops, too) and modifies the ciphertext with $p$ then the message is $m \oplus k \oplus p$, when the receiver decrypted with key $k$ they will get the modified message $m \oplus p$. This can be very dangerous if the message is known or the format of it known. For example, the attacker can turn Attack at the noon! to Attack at the moon!
For the last equation;
$$m \oplus p \neq (m \oplus k) \oplus p$$
This is what we expected except $k=0$.


What is this EC key derivation method called?

Common terms for this include hierarchical key derivation, hierarchical deterministic keys, and key blinding.  It is sometimes called ‘hierarchical’ because you can repeatedly derive subkeys $Q = [k_1]G + P$, $R = [k_2]G + Q$, etc., and the process is a deterministic function of the tags $k_1$ and $k_2$ and the initial point $P$.  It is sometimes called ‘blinding’ because knowledge of $Q = [k]G + P$ and the standard base point $G$ without the blinding $k$ gives no information about $P$.

You can find practical examples in Bitcoin's BIP32 and related protocols, in the Tor v3 onion service protocol, and in the PrivacyPass protocol.

The two common variants are additive and multiplicative blinding: $[k]G + P$ vs. $[k]P$, both of which are invertible, by $Q - [k]G$ or $[k^{-1} \bmod n]Q$ where $n$ is the order of the group.  The additive variant has the advantage that it always uses fixed-base scalar multiplication, and only a single curve addition, which may or may not make a difference in your protocol.

The analogues in the finite field setting are, of course, $G^k\cdot P$ and $P^k$ with inverses $Q/G^k$ and $Q^{k^{-1} \bmod n}$, but while you'll see this notation in the PrivacyPass paper nobody verbalizes talk of this because while we can say ‘multiplicative’, who can bring themselves to verbalize ‘exponentiative’ without getting distracted wondering whether the word even exists?


Is it acceptable to use a HMAC-SHA256 hash as a secp256k1 private key?

If your secret material (you call this my secret so I'll use that name) is chosen with sufficient min-entropy, then yes this scheme is acceptable. my secret, however, must be in itself sufficiently hard to guess; it becomes effectively a password cracking problem. As such, I would suggest my secret be a randomly generated keyfile, or at least a really secure password.
It's worth noting that if my secret is found, this system completely fails. So guard my secret very well. Be wary of keyloggers, shoulder surfers, malware, people nearby who happen to have a parabolic microphone (I'm not kidding), suspicious power outlets (also not kidding), and any number of other attack vectors.
Also, the benefit of a randomly generated key is, in the event of a compromise, you only need to change the key that gets compromised (or keys if multiple get compromised). In your deterministic case you have a single point of failure for the entire system, which according to Happy Quinn is not good (let's see if you can guess what I'm referencing).


Linear Approximation and Linear Probability of Camellia Sbox

Let $LP$ be the linear probability (also called "correlation potential"), $Cor$ be the correlation coefficient and $\epsilon$ be the bias of a linear approximation. Then

$LP = Cor^2 = (2\times \epsilon)^2$.

So, if $\epsilon=2^{-4}$, then $LP = ({2\times 2^{-4}})^2=2^{-6}$.

[1] Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Mathematical Cryptology 1(3), 221–242 (2007). DOI 10.1515/JMC.2007.011. URL http://jda.noekeon.org/JDA_VRI_Stat_2007.pdf


Potential vulnerability in DH key selection - am I understanding this right?

If an implementation uses a poor PRNG, there will always be vulnerabilities in that implementation. However, if you replace Random for a cryptographically secure PRNG, the method you describe for generating private exponents is fine. In such case the timings will only reveal information about:

The public modulus $p$, which may be presumed to be known already, and
The discarded values.

A CSPRNG will output values that are indistinguishable from uniform and therefore computationally unrelated. Hence, learning information about the values that are discarded, will not reveal any information about the value that is eventually selected.


Trial divisions before Miller-Rabin checks?

Update: the formula actually on page 165 in chapter 4 of the HAC is: $t=\lceil{1\over2}\cdot\lg n\rceil$, where $\lg$ is the base-2 logarithm; that is $t=\lceil{1\over2}\cdot k\rceil$; and that crude estimate asks for 512 Miller-Rabin tests for 1024-bit primes, not 5 or 6 tests as stated in the question based on the erroneous $t=\lceil{1\over2}\cdot\lg k\rceil$, or 3 tests as in Table 4.4. That crude formula $t=\lceil{1\over2}\cdot\lg n\rceil$ is based on the fact that a MR round has odds at most $1\over4$ to let a composite pass, is usable in practice with often acceptable speed penalty, but is way overkill for primes of size suitable for cryptographic keys.

The authoritative academic reference on the number of Miller-Rabin tests is this paper: Ivan Damgård, Peter Landrock, and Card Pomerance, Average Case Error Estimates for the Strong Probable Prime Test, Mathematics of Computation, v. 61, No, 203, pp. 177-194, 1993. That's reference [300] in the HAC, and used to derive their Table 4.4.

The authoritative normative reference, which also cites the previous paper, is FIPS 186-4 appendix F.1, with even more down-to-earth prescriptions in the context of generating FIPS 186-4 RSA keys in tables C.2 and C.3, reproduced at the end of this answer.

All the references above consider that $n$ being tested is a random odd integer of specified bit size. Using trial division by small odd primes combined with Miller-Rabin slightly increases the confidence we can have that the number tested is prime compared to MR alone, but that is usually neglected. The main reason to perform such trial division is as a speedup: most of the integers tested are going to be composite, we want to rule them out as fast as possible, and early trial division achieves that.

As an example suitable in many cases of cryptographic interest on modern desktop CPUs: in order to test if some large random odd $n$ is prime, noticing that $k=3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29$ is less than $2^{32}$, we can compute $r=n\bmod k$ efficiently using hardware 64-bit by 32-bit division; then skip Miller-Rabin if $\gcd(r,k)\ne1$. That leaves only ${{2\cdot4\cdot6\cdot10\cdot12\cdot16\cdot18\cdot22\cdot28}\over{3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29}}<{1\over3}$ of candidates to be tested by MR, and thus speeds up things by a factor of over 3 on many platforms (including most where MR is slow). We can do more trial division, but with severely diminishing returns (the speed-up is by a factor at most 1.14 for division by $31\cdot37\cdot41\cdot43\cdot47$). The above technique with $k=2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$ is easy to code efficiently on most 32-bit embedded CPUs, already gives a speedup of about 2.5, and might be good enough. Experiment can be used to determine the optimum; trial division by the first 2047 odd primes will be beyond that point if there's a half-decent modexp.

Note: it is notoriously hard to validate primality-testing code, especially in a black-box setup. MR is popular because it is simple thus relatively easy to proofread, but caution! With large parameters, it is almost impossible to ever reach the second MR test, at least if the witness used is random! We can easily craft test cases that pass trial division, but ideally these should also be Carmichael numbers if we want a chance to catch some improper MR variations, and I do not know if the extensive literature on generation of large Carmichael numbers provides that.

In practice, in the context of RSA, one can do (very) little trial division, following by a number of MR tests according to the following table:

In this table, error probability (like $2^{-80}$ in the first box) is for the guaranteed residual odds of accepting a composite for any of the 6 (pseudo)primes involved in the RSA key generation process: $p$, $q$, and shorter intermediary primes $p_1$, $p_2$, $q_1$, $q_2$ such that $p\equiv1\pmod{p_1}$, $p\equiv-1\pmod{p_2}$, $q\equiv1\pmod{q_1}$, $q\equiv-1\pmod{q_2}$.


What are preimage resistance and collision resistance, and how can the lack thereof be exploited?

Preimage resistance is about the most basic property of a hash function which can be thought. It means:

  For a given $h$ in the output space of the hash function, it is hard to find any message $x$  with $H(x) = h$.

(Note that the it is hard here and in the next definitions is not formally defined, but can be formalized by looking at families of hash functions with a security parameter $n$ (often the hash output size), and saying »hard = there is no polynomial $P$ so this can be done in time $P(n)$ for all functions of the family«. For practical uses, we are often only looking at a single hash function, and are content with »hard = takes more time/costs than any hypothetical attacker can invest«, preferably with some estimation of the work to be done.)

A function with this property is also called one-way function (though this term is also used for non-hash functions with this property, like asymmetric encryption primitives).

A related property is the second preimage resistance:

  For a given message $x_1$ it is hard to find a second message $x_2 \neq x_1$ with $H(x_1) = H(x_2)$.

A function without preimage resistance is usually also not second preimage resistant: Given a message $x_1$, calculate $h := H(x_1)$ and then get a preimage $x_2$ from $h$, then we usually have $x_1 \neq x_2$ and $H(x_1) = H(x_2)$. (The exception to the "usually" would be when the function is (for the space of interesting messages) essentially injective, and the preimage finder would always return the only interesting preimage. Such a function would be second-preimage and collision resistant, but still a quite bad hash function. As normally the space of interesting messages is much larger than the hash space, this doesn't arise in practice.)

Collision resistance is an even harder property, which we still want for most usages of hash functions:

  It is hard to find a pair of messages $x_1 \neq x_2$ with $H(x_1) = H(x_2)$.

Of course, from a (second) preimage attack we also get a collision attack. The other direction doesn't work as easily, though some collision attacks on broken hash functions seem to be extensible to be almost as useful as second preimage attacks (i.e. we find collisions where most parts of the message can be arbitrarily fixed by the attacker).

Also, there is the generic birthday attack on hash functions (which even works for random oracles), which needs $O(\sqrt N)$ tries to have a good probability to hit a duplicate, where $N$ is the size of the output space of the function, where a similar generic brute-force attack on the second-preimage and preimage resistance needs about $O(N)$ queries (which is not feasible for the output sizes of all hash functions used in practice).

I know of no practical preimage attack for the usual hash functions (please add them in other answers, or as comments), while for example for MD5 the collision-resistance is about totally broken, and SHA-1 is starting to show cracks (in 2017, a research team from Google produced two colliding documents).

How can one exploit the lack? This strongly depends  on the use of the hash function in a higher-level protocol (or algorithm build on top of it). In some protocols only the other properties are used directly, but as said, missing preimage  resistance always also leads to missing second-preimage and collision resistance. For example, in signature schemes we usually hash the message first, and a (second) preimage attack allows to create a second message with the same hash as the first one, i.e. where the same signature fits.

An example where the preimage resistance itself is needed is the hashing of a password, or usually a password together with a salt known to the attacker. (Actually here the message space is often small that searching it becomes feasible to brute-force search it with a common fast hash function, which is why one uses slow hash functions for password hashing.)


Calculate private key from public key and r

The short answer is that it doesn't work.
Bitcoin uses ECDSA signatures. An ECDSA signature is comprised of two numbers $r$ and $s$.
It is impossible to recover the private key given only a signature made with this private key and the public key.
The security of ECDSA hinges on a secret value used during the signature process, usually written $k$: this value must be fully random and must be kept secret (it's thrown away after calculating the signature). It is possible to recover the private key given two signatures and the public key if the two signatures were made in a buggy way that uses the same value of $k$. More generally, even if exactly the same value of $k$ is not repeated, if there are biases in the generation of $k$, it may be possible to recover the private key given enough signatures.
Another way to break the security of ECDSA can be to observe the signature process and exploits flaws in the implementation of ECDSA, such as side channels. Breaks of cryptographic algorithms are extremely rare, but breaks of cryptographic implementations are common.
None of this is happening in the video. This video does not show any kind of cryptographic or security flaw.
The video shows someone copy a bunch of values which they say is a “private key”, then take an ECDSA signature, pass it to a program that they don't understand, and get out a value which they claim is a “private key”. There is no information about what that program does.
Whoever made this video is taking a long time just to convert between hexadecimal and decimal notation, which is a trivial detail that can be handled in a fraction of a line in Python. They clearly don't know the first thing about Python, otherwise they'd be able to modify the script to use a more convenient input/output format.
This video has zero technical interest or novelty. Given that it's cryptocurrency-related, it's probably part of a scam. The author is presumably trying to convince naive people that they know something the audience doesn't, but given how incompetent the author is, they're really aiming for the bottom of the barrel. Which is the best target when you're trying to scam people.


Why is the Pedersen commitment perfectly hiding?

When I was asked if even an unbounded adversary can learn anything, I thought that such adversary can iteratively try possible values of $r,s$ until he finds such values that satisfy $C = g_1^s g_2^r$ (I was apparently wrong of course). Why isn't that correct?

Because there are lots of different $r, s$ pairs that satisify the solution.  In particular, for every possible $s$ value, there's exactly one corresponding $r$ value that satisfies $C = g_1^s g_2^r$.  Hence, an exhaustive search will not eliminate any possible $s$ values (or make any one more likely); hence, the adversary gets no information about $s$ from the value of $C$.

How this works may be easier to understand if we map this to an easier-to-understand group; if we select an arbitrary subgroup generator $g$, and have $g^a = g_1$, $g^b = g_2$, and $g^c = C$ (as $C$ must also be in the subgroup), the relation is $g^c = g^{as} g^{br}$ or $c = as + br \bmod q$.  We can rearrange this to $b^{-1}(c - as) = r$ (assuming $b \ne 0$; this cannot happen as $g_2$ was specified to be a generator), and so we can see that for a specific $s$ value, this gives us the unique $r$ value that satisfies the relation.

More precisely, the paragraph above (and in particular the equation $b^{-1}(c - as) = r$) shows us that for every value $s$ there is a unique value $r$ such that $C=g_1^s g_2^r$.

BTW: this is the same reason that One Time Pad is perfectly hiding.


During padding oracle attack (CBC), how is first byte of plaintext block is obtained?

Does PKCS#5 allow you to pad 16 bytes with 0x10 value?

No, but that's because PKCS#5 only specifies padding for DES, and that has an 8 byte block size. Even PKCS#5 itself refers to PKCS#7 when it comes to padding AES. More information about the differences here.

Now for the real answer. PKCS#7 padding, which is identical to PKCS#5 but allows any block size, requires 16 times the 0x10 byte value as padding:

  For such algorithms, the method shall be to pad the input at the
  trailing end with $k - (l \bmod k)$ octets all having value
  $k - (l \bmod k)$, where $l$ is the length of the input.

Here $k$ is the block size of the block cipher in bytes, for instance AES with a block size of 16 bytes. Now obviously if $l$ is a multiple of 16 then then a full block of padding is added (as $l \bmod k$ would evalulate to zero and therefore only $k$, i.e. 16 would be left).

The reason for this is simple: imagine that a plaintext message that is a multiple of the block size ends with a valid padding pattern. Then the unpadding would remove that part of the message. By always performing padding the unpadding can be performed regardless of the contents and size of the message (i.e. allowing any message to be decrypted correctly).


Using HKDF to derive symmetric keys from a hybrid public-key encryption scheme

Fix an RSA modulus $n$.  Here's a way you can send a message $m$ so that only someone who knows the secret factorization of $n$ can read it.

Pick an integer $1 < x < n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = \operatorname{HKDF-Extract}(\underline x)$, where $\underline x$ is the little-endian bit encoding of the integer $x$.  Note that $\underline x$ itself is not a uniform random bit string: if interpreted as an integer, it is always below $n$.  Thus it is unfit to satisfy the security contracts requiring a uniform random key.
Compute $k_\mathrm{enc} = \operatorname{HKDF-Expand}(k, 512, \text{‘Cocowalla's app: encryption key’})$.  $k_\mathrm{enc}$ is conjectured to be indistinguishable from a uniform random bit string to an adversary who doesn't know $x$.  As such it is fit to satisfy security contracts requiring a uniform random key.
Compute $k_\mathrm{mac} = \operatorname{HKDF-Expand}(k, 256, \text{‘Cocowalla's app: authentication key’})$.
Compute $c = m \oplus (\operatorname{Threefish512}_{\,k_\mathrm{enc}}(0) \mathbin\Vert \operatorname{Threefish512}_{\,k_\mathrm{enc}}(1) \mathbin\Vert \cdots)$, the encryption of $m$ with a one-time pad generated by Threefish-512 in CTR mode.*
Compute $t = \operatorname{Poly1305}_{k_\mathrm{mac}}(c)$, the authentication tag for $c$.
Transmit $(y, c, t)$.

The recipient who knows the factors $p$ and $q$ of $n$ can solve $3d \equiv 1 \pmod{(p - 1)(q - 1)}$ and recover $x = y^d \bmod n$, since $y^d \equiv (x^3)^d \equiv x^{3d} \equiv x^1 \equiv x \pmod n$; then they can derive $k$, etc., as before.

In archaic crypto literature,† this is called ‘hybrid’ because we don't use the RSA trapdoor permutation $x \mapsto x^3 \bmod n$ to encrypt the message; rather we use it as a public-key KEM to conceal a secret element $x$ of $\mathbb Z/n\mathbb Z$, and derive from $x$ keys for a symmetric-key cryptosystem—specifically, a DEM, a data encapsulation mechanism.  Thus it is a ‘hybrid’ of public-key and symmetric-key cryptography.

* This is not actually how I would recommend doing it: I would rather recommend NaCl crypto_secretbox_xsalsa20poly1305 with a single key.  But this illustrated using HKDF-Expand to generate multiple keys of different sizes with different info strings.

† The designation of ‘hybrid’ today is archaic because modern cryptographers recognize it was foolish all along to shoehorn structured messages like ‘Help!  I'm trapped in an RSA ring.’ or ‘The Magic Words are Squeamish Ossifrage’ into elements of $\mathbb Z/n\mathbb Z$.  In fact, for hysterical raisins, we still do approximately this: pick $k \in \{0,1\}^{256}$ uniformly at random, and then shoehorn it with an array of hash functions into an approximately uniform random element of $\mathbb Z/n\mathbb Z$, with a byzantine construction called OAEP.  For hysterical raisins most protocols deployed in practice use OAEP, or its even worse predecessors.  The much simpler scheme above is called RSA-KEM.


Why is recipient hashed in this Sign/Encrypt/Sign proposal?

I don't fully understand the notation in that link you posted, but as far as hashing the public key instead of signing it directly, some public keys are pretty long, making signing expensive. Public keys for RSA can be 4096 bits, which is too long for most signing schemes. Hashing the public key allows it to be signed more efficiently without losing security.


How can bit slicing be constant time, when Mix Columns is in the cipher

You can (and should) do the reduction in constant time using masking.  That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction:

if ((result >> 8) & 1) {
    /* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */
    result ^= 0x11b;
}

you can simply do:

result ^= 0x11b * ((result >> 8) & 1);

(where your compiler may optimize the multiplication by a constant into a series of bit operations, if it's more efficient on your CPU architecture).

This can then be trivially bitsliced, e.g. like this:

/* bit0 .. bit7 store the 8 bits of the result(s), bit8 is the overflow bit */
bit0 ^= bit8;
bit1 ^= bit8;
bit3 ^= bit8;
bit4 ^= bit8;


Is there a message size limit with elliptic-curve-based public-key encryption?

Is there a limit?

Depends on what ECC encryption algorithm you're talking about.  ECC really means 'lets use elliptic curves to do cryptography', there are several ways to do that to do public key encryption.

If you use EC-ElGamal (which is just ElGamal translated to use Elliptic Curves), you're pretty much limited to the group size; you're encoding a EC point, and so you're limited to the number of EC points there are.

On the other hand, if you're using ECIES, there is no effective limit.  That's because you're not really encrypting the message with the curve itself; instead, you're using ECC to transport a one-use symmetric key, and then using that symmetric key to encrypt the message (and so the only size limitation would be the limit of whatever the symmetric algorithm you're using has).


Side channel attack - execution time depends on the size of the key

Execution time of my algorithm/code depends on the size of the key. Is this a disqualifying problem?

No, because the key size is not considered a secret.
But having execution time depend on the bit size of the integer coded by the key would be something different. It would be a problem, more or less minor depending on the size we are talking about and algorithm/key generation method. For example, in RSA, that's typically not a serious issue for any of the integers defining the private key $p$, $q$, $d$, $d_p$, $d_q$, $q_\text{inv}$, because it's so unlikely that the bit size of these integers is significantly reduced compared to its maximum; and regarding $p$ and $q$, their bit size as an integer is customarily fixed to exactly half the bit size of $n=p\,q$.
What could be a serious side-channel issue would be that execution time depends on some secret data, like the key value, or plaintext in an encryption algorithm. The worse is when execution time depends on a combination of the key value and varying information known or under control of adversaries (e.g. key and ciphertext; or key and hash of signed data). That's ideal ground for a side-channel attack. That could well be the case if multiplication time depends on the value multiplied. That's a common and hard-to-avoid issue, see this.


Is full Homomorphic encryption quantum resistant?

Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach.  All three are based on hard problems that are not susceptible to Shor's algorithm.


Zero-knowledge proof for multiplication in the exponent

If the generators were the same, then this would be a standard Diffie-Hellman tuple sigma protocol. In order to see this, note that a Diffie-Hellman tuple is defined to be $(c_1,c_2,c_3)$ such that $c_1 = g^a$, $c_2 = g^b$ and $c_3 = g^{ab}$. Setting $a=y$ and $b = x/y$, we have that $ab = x$. Thus, all you need to prove is that $(c_2,c_3,c_1)$ is a Diffie-Hellman tuple.
However, given that they are not the same, the above isn't correct. The first thing to notice about this language with different generators is that it is actually trivial. That is, it is always possible to solve and find $x,y$ that fulfil the equations. Thus, such a proof would only be interesting as a proof of knowledge (as such, one should refer to the relation and not the language, and $g_1,g_2,g_3$ must of course be part of the public statement).
Beyond that, I don't think it's trivial. I have played around a bit for a few minutes and the naive things one could do won't work. However, from experience, sigma protocols typically aren't that hard to build, and this looks like something that should work. But it may be hard and require research. I am leaving this partial answer here, even though it isn't correct, in order to be of some help regarding finding the direction.


Logjam: "composite order subgroups" explained for TLS developers and system admins?

A safe prime is a prime number $p$ for which $(p-1)/2$ is also prime. The order of an element $g$ of the group $\mathbf{Z}^*_p$ (the integers modulo $p$, excluding 0) is the smallest integer $n$ such that $g^n\equiv 1\pmod{p}$; this is always a factor of $p-1$. The orders of the subgroups of the group generated by $g$ are the factors of the order of $g$; what's important for security is that at least one of the prime factors of the order of $g$ is large (for safe primes, if the order of $g$ isn't 1 or 2 then it has a prime factor of $(p-1)/2$, which is large). If you pick a prime that's not a safe prime, you need to make sure the order of $g$ is a multiple of at least one large prime; it's also important to try to make sure it's not a multiple of many small primes, and/or to pick a large exponent.

You can find good safe primes in RFC 3526. You could also generate your own; just try a lot of large odd numbers and check if both $p$ and $(p-1)/2$ are prime. You then pick $g$ such that $g^2\not\equiv 1\pmod{p}$, and you're good (since that means the order of $g$ is a multiple of $(p-1)/2$). With a safe prime, the worst that happens is that the last bit of your exponent leaks, which isn't a big deal with decent-sized exponents (so you don't even need to pick too big an exponent to be secure).

The following is more detailed background on why this is important. I tried to explain the math behind it in a way you could follow without prior background, but am not sure how well I did so.

Group theory

Diffie-Hellman key exchange is done in a group, which is a set of elements and an operation that has a bunch of nice properties. In Diffie-Hellman, this group is the integers modulo a prime $p$, excluding any multiples of $p$ (so, the numbers between $1$ and $p-1$ are the elements of the group), with the operation being multiplication. A group has a set of elements associated with it; if there's a subset of those elements that is a group under the same operation, this is called a subgroup.

Diffie-Hellman more specifically happens in the subgroup generated by the generator $g$, meaning the smallest subgroup containing $g$. This subgroup consists of everything that can be written as $g\times g\times\cdots\times g$ (or $g^n$). The order of this subgroup (also called the order of $g$) is the number of elements in the subgroup, which is equal to the smallest $n$ where $g^n\equiv 1 \pmod{p}$ (once you get to 1, you start repeating yourself). The order of this subgroup is always a factor of the order of the main group (which for Diffie-Hellman is always $p-1$); this is true for all groups and subgroups.

Lastly, a number theory fact: If the order of $g$ is $r$, then $g^x\equiv g^y\pmod{p}$ if and only if $x\equiv y\pmod{r}$. This means that brute-forcing $e\equiv g^x$ just requires trying all values of $x$ between 0 and $r-1$.

Composite orders

A composite order subgroup is what it sounds like: the order of the subgroup generated by $g$ is not a prime number. In this case, if you have $e=g^x\pmod{p}$ and are trying to find $x$, you can break the problem up into solving the discrete log problem on smaller subgroups.

Suppose, for instance, that the order of $g$ is 220. Then $e^{44}\equiv (g^x)^{44}\equiv (g^{44})^x\pmod{p}$. The order of $g^{44}$ is $220/44=5$ (because $(g^{44})^5=g^{220}\equiv 1$). So, any $y$ for which $(g^{44})^y\equiv e^{44}$ is congruent to $x$ modulo 5. We can solve the discrete log problem on this order-5 subgroup to find the remainder of $x$ modulo 5. Likewise, we can find $x$ mod 11 by solving discrete log on an order-11 subgroup. Because the order of $g$ is a multiple of $2^2$, we need to essentially solve two order-2 discrete log problems: the first to get $x$ mod 2, then using that we solve another one to get $x$ mod 4.

Once you have the value of $x$ modulo all powers of all prime factors of the order of $g$, the Chinese remainder theorem says that you have enough info to uniquely determine the value of $x$ modulo the product of those powers of primes (i.e. modulo the order of $g$). It's actually extremely quick to do so (this is incidentally also the basis of an attack on textbook RSA with multiple recipients, in which you get $m^e$ modulo a lot of different values and can compute the real $m^e$). So, instead of having to solve discrete log on a 220-element group, you solved it on an 11-element group, two 2-element groups, and a 5-element group.

Also, as the order of $g$ is a factor of the order of the group, factoring the order of the group (i.e. $p-1$) lets you attack any generator in that group. That means that an attacker can do work in advance that lets them attack any use of Diffie-Hellman with a given value of $p$.

Mitigation

The solution to this is to make sure that one of the prime factors of the order of $g$ is very large; your strength is essentially the strength given by the size of the largest prime factor of the order of $g$, so you want to maximize that. The easiest way to do this is to pick a safe prime -- one for which $(p-1)/2$ is also prime. With a safe prime, the order of any element (which, remember, has to divide $p-1$) is either 1, 2, $(p-1)/2$, or $p-1$. It's easy to check that your generator doesn't have order $1$ or $2$, and if it doesn't then its order has a large prime factor ($(p-1)/2$).

If things aren't safe primes, you can still have secure choices of $g$ if you have a large prime factor in the order of $g$. However, all small factors of the order of $g$ leak some information about your exponent; if you have lots of small factors and pick a smallish exponent (which is normally perfectly fine), you can end up leaking lots of information about your exponent. Safe primes mean there's at most one small factor of the order of $g$, so you don't leak much information without having to try lots of possible values of $g$ to get one without many small factors or with a large factor.


I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field?

They have equivalent security; however the nice thing about $GF(2^8)$ is that everything ends up to be an integral number of byte.  We could use (say) $GF(257)$, however when the shares will end up being slightly larger than 1 byte, and so if we encode a secret that's an random set of bytes, the shares end up using a bit more space.

If we used a trinary computer, we'd probably end using something like $GF(3^6)$, because that would be an even number of trits.

  with GF(256), you end up writing a ton more code

Not that much; most computer languages support $GF(256)$ addition as a standard operator, and multiplication/division can be done with two tables, and a few lines of code.

Compare this to the logic required to do modular division.

As for "far less intuitive", well, that depends on your experience with finite fields; I find it perfectly intuitive.


How does fully homomorphic encryption compare to partially homomorphic encryption in terms of security?

In short: They can not be compared, because those cryptosystems are vastly different constructions for different goals.

Taking a step back, usually the security of a cryptosystem is defined with a security parameter $\lambda$, and the security then is described as "... is less than a negligible function $f(\lambda)$ ...", so we can say that e.g. ElGamal with $\lambda = 10$ is less secure than ElGamal with $\lambda = 12$.

But as soon as looking at different constructions, this gets tricky, because they don't compare to the same negligible function any more. Also, they are just upper bounds and there is no statement possible like "it has exactly security $23$".

If you want to combine security with other aspects like runtime, then you run into other issues. Some cryptosystems have fast key generation, others have fast encryption or decryption, etc. There's just one rule of thumb: Quite surely any FHE construction is much, much slower than traditional PKE systems when aiming at similar levels of security. Also, if you consider runtime of a system and include this in your comparison, then you have to keep in mind you are comparing implementations and not the scheme itself.


Is a one-time pad secure if the encryption method is not?

OTP requires a completely random key. That's next to impossible, and human genes are certainly not completely random. This is why OTP's are mainly theoretical constructs.

XOR is the normal way of encrypting using an OTP. XOR is not weak encryption if the key stream is strong. And if the key stream is perfectly secure then XOR encryption is completely secure (for confidentiality anyway).

And no, the messages do not matter. A secure cipher should be secure against known plaintext attacks. That is, different messages or other parts of the message should remain confidential even if part of the message is known.

It's good that you're not offended, because it certainly is a horrible idea.


Point addition in NaCl/libsodium (Curve25519)

Recent versions of libsodium have crypto_core_ed25519_add() and more: https://download.libsodium.org/doc/advanced/point-arithmetic


How can I remove my personal data from my PGP public key?

You cannot remove all UIDs, but you can create one which does not link to your identity and remove all others.

Backup your .gnupg folder (for unix systems, for Windows wherever your key is stored)!
Start editing your key:

$ gpg --edit-key 47AB515A

Create an anonymous UID:

gpg> adduid
Real name: Anonymous
Email address:
Comment:
You selected this USER-ID:
    "Anonymous"

Now we're ready to delete all others, but need to know which to remove:

gpg> list

pub  2048R/DEADBEEF  created: 2013-07-28  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
sub  2048R/DEADDA7A  created: 2013-07-28  expires: never       usage: E
[ultimate] (1)  Foo Bar <foo.bar@example.net>
[ unknown] (2). Anonymous

Every UID has a number (in parentheses).
Select all UIDs you want to remove (probably all but the newly created one):

gpg> uid 1

And repeat as needed. All selected UIDs will have a star in their record:

[ultimate] (1)* Foo Bar <foo.bar@example.net>

Delete all selected UIDs:

gpg> deluid

Save and exit:

gpg> save

This removes all personal information from your key - including all signatures (each is bound to an UID), so your "stripped down" key will lose all trust.

You will be able to use it like before; usually every OpenPGP encryption container contains your key ID which does not change, neither does your pass phrase.

If you did not publish your key yet, nobody will be able to find out who you are based on your OpenPGP key. As the key ID stays the same, an already published key can be looked up on the keyservers, they will not delete your UIDs but combine all they ever saw. You can never remove a published key or parts of it from the keyservers.

Caveat: The sender now must select which key to encrypt to as his client cannot automatically assign a key to your email address any more (well, you deleted it).