Why encoding 8 characters using 8-bit ASCII results in 800-bit message?

That is not correct, 8 ASCII characters is 8-bytes times 8-bits per byte which is 64-bits.

The question seems to be: Encoding 100 characters using 8-bit ASCII results in an 800-bit message.

That is 100 ASCII characters is 100-bytes times 8-bits per byte is 800-bits.
What padding means?
Since block based encryption with a block mode such as ECB or CBC means that the input must a  multiple of the block size because the data is processed one block at a time and partial blocks can not be processed.
What last sentence means? (difficult to understand)
Basically answered above.
See Padding (cryptography)
and especially: PKCS#5.

Note: ASCII is one 8-bit byte per character—only.


Encrypt or decrypt using the private key, and decrypt using the public key?

What you want is called a signature scheme. This will enforce the separation concerning the right to write. If you need confidentiality as well, you can combine this with traditional symmetric or public-key encryption.

So how does this work with signatures? Whenever somebody from Group B writes the data, they remove the old signature and apply a new one. Now anybody from Group A or B can verify that the file has not been modified since it was last edited (by a member of group B). Of course, members from group A won't be able to sign the file, because their public signature keys won't be added to the central list of trusted signature keys. Alternatively one could also use something called a ring signature which also guarantees anonymity of the original writer (or a group signature if attributation is wanted).


I think you can just generate all the plaintexts but one randomly, and make the last one the XOR of the key and the other plaintexts. To recover the key, one must recover all the plaintexts and XOR them. Even every plaintext but one gives you no information about the key.


What are the capabilities of passive and active adversaries?

It depends on the situation. In crypto, we tend to think of a passive adversary (Eve) as someone who can listen to all communications sent between two parties (Alice and Bob).  So, you create a security goal based on the "power" of your adversary. If all that Eve is doing is listening in on communications, Alice and Bob need to ensure that Eve cannot understand whatever she reads. In the real world, this is a very real threat. For example, suppose we are both sitting in a cafe with public WiFi. If I control the network or actively sniff for packets (something like Wireshark), I can read all of your communications with the website you are talking to/browsing. So, the natural goal is to prevent me from understanding what you are communicating. The natural answer is strong encryption.
An important question is,  "how strong is strong enough?" The answer is complicated and has given way to several varying degrees of strength. Most security models are described as a game between you and the adversary. One such model is chosen plain-text attack.  That is, suppose the adversary Eve is given oracle access to a black box decryption algorithm. That is, she can ask for the encryption of $m_1,...,m_k$ for some reasonable number of $k$ to get cipher texts $c_1,...,c_k.$. The adversary then picks two messages $m_0^*,m_1^*$ and is given the encryption of one of the two messages chosen uniformly at random $c_b$ where $b\in\{0,1\}$. If the adversary can correctly guess if $b=0$ or $b=1$ with greater than $1/2$ probability, then the adversary wins.
Now suppose Eve is allowed to change messages in transit. That is, suppose you are logging on to the Bank of America, and you ow me \$100. If I am Mallory (the name given to an active adversary), I can flip some bits of the message in transit and hope that my changes make the amount larger. Or worse, I could throw out your message and inject my own! Now you went from paying me \$100 to \$1000. We, of course, want to prevent this.
This is where message authentication codes come into play. We want to be able to "sign" our messages so that others can be sure that they came from us and not from Mallory. In practice, if I see you sending messages, you want this signature which is a part of the message (commonly called a tag for symmetric algorithms) to be what is called existentially unforgeable. That is, even if you intercept a bunch of my messages, and see a bunch of tags, you will never be able to produce a valid message and tag pair. The model is normally described as an adversary unable to distinguish between an algorithm that rejects every single message and tag combo and one that actually uses the message authentication code. Combining these two protocols, in the theoretical world, you get authenticated encryption where you are sure that not only is it Alice's message, but even Mallory cannot read it. If Mallory tries to alter it, the message will be rejected.
In practice, many things can go wrong. Just because I write a theoretically secure cipher on a blackboard does not mean there is nothing an adversary can do! Software engineers are famous for shooting themselves in the foot, and there is always an issue of backward comparability. You could write entire books on how difficult it is to implement crypto. That is because our models pretend computers are back boxes--it turns out that they are not.  There are documented attacks on just about every cipher you can think of that make use of sounds computers make, the time it takes to execute, and power consumed by the computer. You can also perform protocol downgrade attacks that force victims to use broken crypto (basically every attack on TLS that has been written about in the last few years uses this sort of attack). The short answer for this is modeling real worlds attacks is an extremely daunting task.


Effective key length of Two-Key Triple-DES

Des is 56 bits/key   with 2Des   the key is is 56*2 or 112bits.  It is not multiplicative like 56 * 55

3des is EDE  encrypt with k1, decrypt with k2 and encrypt with k3.  or 3*56 or 168 bits.  Quit often, cypherblock chaining is used with the sicond or third pass.  The cbc makes it even or difficult to guess the encryption keys.Decryption = DED


Does it matter if IV is used as the first block of data before the encryption and then some fixed value is used for the actual IV?

Actually, that turns out that it's sometimes a useful way of implementing CBC mode (at least, with the understanding that you don't send the value you have labeled 'Initialization Vector', but instead the first cipherblock you generate will be sent to the decryptor as the CBC mode IV, and the rest of the cipherblocks will be sent to the ciphertext.

It is easy to see that if the decryptor uses the standard CBC decryption process with the provided IV and ciphertext, he'll get the plaintext.

So, why is this useful?  Well, one requirement for CBC mode is that the IV be unpredictable (specifically, unpredictable to someone who doesn't know the key; if they know the key, they don't need to predict IVs to verify potential plaintext blocks).  With the standard CBC mode implementation, you are given the responsibility of generating unpredictable values, which is not especially cheap.

However, with your construction, it turns out that we no longer require that the first block (that is, the one you labeled 'Initialization Vector') be unpredictable; it is sufficient that it just be unique - after it passes through the AES function, it'll become unpredictable.  Hence, it is sufficient that it can be a counter, which is a lot cheaper than an unpredictable value.

However, you'll say, you perform another CBC mode block (which involves another AES block operation); doesn't that increase the cost?  Well, sometimes, it doesn't - specifically, if you have some encryption hardware that performs a CBC mode encryption as a primitive, then the cost for encryption one additional block is usually fairly minimal (and certainly a lot cheaper than a side operation to generate an unpredictable value).

So, if you are in this specific scenario, yes, it can be a nice optimization.


Minimal size of share in Shamir's Sharing Scheme

As listed by Shamir, the first property is:

(1) The size of each piece does not exceed the size of the original data.

Here's what he means; there's a public value $p$; the original data is encoded as a value between 0 and $p-1$.  In addition, the secret portion of each share ('piece')  is a value between 0 and $p-1$, hence the size of each piece does not exceed the size of the original data.

What Shamir meant is that the scheme doesn't expand the share size beyond the size of the representation of the secret.  It can be shown that if the share size is smaller than the representation of the secret, then someone with $k-1$ shares (where $k$ is the threshold) can deduce some information about the secret (at the very least, some values which the secret cannot be).  Hence, Shamir's method is optimal in this sense.


You are correct, anyone can use it without asking for permission or paying anybody.  The RSA patent US 4,405,829 expired in 2000, and the RSA algorithm was never patented anywhere else (because the rest of the world won't allow you to patent something that has already been published; the US gives you a year).


How often does RSA-OAEP have a leading zero?

Your description of the protocol is rather confused. You seem to jump between a key and an encryption output. It isn't clear whether you're worried about the key generation process, or an encryption operation that happens with this key.

I assume that you're talking about RSA with a 128-byte key, not 128-bit — 128 bits was already insecure when RSA was invented, whereas 1024 bits (128 bytes) is still publicly unbroken but worryingly small nonetheless and deprecated by all major key size recommendations.

An n-bit RSA key (where n is a multiple of 8, which is almost always the case in practice) should usually have a most significant bit that's set, i.e. a most significant byte that's larger than 128. Some systems generate a key that's actually one bit short because they multiply two n/2-bit primes and the result can be anywhere between $2^{2\lfloor (n-1)/2\rfloor}$ and $2^{2\lceil (n-1)/2\rceil}$; that's acceptable, and results in a most significant byte that's between 64 and 128. If the key is supposedly n-bit but is sometimes a whole byte short (8 bits short), that indicates something wrong about the generation process.

RSA-OAEP applies the RSA exponentiation operation to a number which, when written out with the most significant byte first, has 0 as the first byte value and every other byte xor-masked by a pseudorandom string. A xor mask by a pseudorandom string is itself pseudorandom. That is, the number looks like this in hexadecimal: 00rrrrrr…rr where the r digits are pseudorandom. This is only an intermediate value however, so it isn't clear to me why it would be relevant.

The output of RSA encryption is a number modulo $n$ where $n$ is the RSA modulus. That number can be anywhere between $1$ and $n$ in a way that's indistinguishable from uniformly random (or at least pretty close) if you don't have the private key. That means that the most significant byte is biased (in particular, larger values are impossible), and it's 0 more than 1/256 of the time.


Bleichenbacher's Attack on high public exponent RSA keys?

Some attacks on some ad-hoc RSA encryption or signature padding, or/and their defective implementation, including several attacks due to Daniel Bleichenbacher, require an RSA public exponents $e$ of small value.

The limit has to do with some part of the padding (including a hash of $h$ bits), raised to the $e^\text{th}$ power, not being much wider than the public modulus $N$ of $n$ bits. It follows that $e\gg n/h$ block these attacks (but far from all attacks on ad-hoc RSA padding). There is no relation to $e$ being prime.

In RSA, ad-hoc padding should thus be avoided in favor of padding with reducibility to the RSA problem (like RSAES-OAEP, RSASSA-PSS, ISO/IEC 9796-2 mode 2 or 3), or schemes that do not need padding (like RSA-KEM). Security authorities recommend that for new applications, and $e\ge65537$ everywhere; see this for more.

Digression: Why 65537?

Using prime RSA public exponent $e$ is customary: it makes drawing randomly seeded primes $p$ with $\gcd(p-1,e)=1$ (as required in RSA) easier and less subject to implementation goofs.

Using $e$ of the form $2^k+1$ is customary: raising to such $e^\text{th}$ power reduces to squaring $k$ times, then multiplying once by the original number (including for operations modulo $N$ as in RSA).

Primes of the form $2^k+1$ are thus customary. They demonstrably all are with $k$ a power of two, and known as Fermat primes. With $h\ge128$ and $n\le16384$ in most practical uses of RSA, using for $e$ the fifth (and largest known or practically usable) Fermat prime $F_4=2^{(2^4)}+1=65537$ is always very much on the safe side w.r.t. matching $e\gg n/h$.


Functions that are only second-preimage resistant?

Take a function $H:\mathbb S\to\{0,1\}^k$ where $\mathbb S$ is a large finite subset of $\{0,1\}^*$, such that $H$ "compress data" [however this is defined], and $H$ is [conjectured] collision-resistant [thus second-preimage-resistant] and first-preimage-resistant; e.g., SHA-512, for $k=512$. Let $«0»$ and $«1»$ be two public distinct elements of $\mathbb S$. Define $H':\mathbb S\to\{0,1\}^k$ by
$$H'(M)= \begin{cases}H(«1»)&\text{if }M\text{ is }«0»\\H(M)&\text{otherwise}\end{cases}$$

This $H'$ is compressing, and not collision-resistant [argument: $H'(«0»)=H'(«1»)$]. However $H'$ remains preimage-resistant, both first and second [argument: preimage resistance is defined for random message, thus the minor change we made to $H$ in order to build $H'$ does not matter, for odds that a random choice of message hits $«0»$ or $«1»$ are negligible].

Hence $H'$ is second-preimage resistant, but not collision resistant. Which answers the question by the affirmative [I'm reading "without satisfying the others" as "not (satisfying the others)"].

Note: I conjecture without proof that the answer is negative when reading "without satisfying any of the others".

Informal definitions: a function $F$ is

collision-resistant when a [computationally bounded] adversary can't exhibit any $(a,b)$ with $a\ne b$ and $F(a)=F(b)$;
first-preimage-resistant when, given $f$ determined as $F(a)$ for an unknown random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $F(b)=f$;
second-preimage-resistant when, given a random $a$, a [computationally bounded] adversary can't [with sizable odds] exhibit any $b$ with $a\ne b$ and $F(a)=F(b)$.

Note: these definitions are a compromise between simplicity and precision, but lacking about what random $a$, sizable odds and computationally bounded means. However they can be made formal by making $F$ a parameterized function family; and adding some appropriate parameterized upper bound for the size of that random $a$ when the input domain $\mathbb S$ is unbounded.


In zkSNARKS, does R1CS require every step of the calculation, or just statements which confirm the calculation was performed correctly?

This is already explained in the linked Buterin blogpost. Essentially what you are trying to achieve here, ie. implementing a MOD "gate" in a zkSNARK is simply cannot be done efficiently. This is because that MOD is not supported in finite cyclic group arithmetic. If there is an efficient MOD gate, then by applying the Chinese Remainder Theorem, one could also break the Discrete Logarithm problem over said finite group.

More precisely, given  $g^x$, if there is an efficient MOD gate, then it means that you can obtain $x \pmod{p_{0}}$ and $x \pmod{p_{1}}$ efficiently  - for two arbitrarily chosen primes $p_{0},p_{1}$ - from $g^x$. Then by applying the Chinese Remainder Theorem, it is trivial to get $x$, hence Discrete Logarithm Problem could be solved efficiently.

Note: in your second approach, namely creating MOD gate with the following constraints:
$$x = d*y + m \land
m < y$$
would also require a single MOD, since a malicious prover could make $d*y$ overflow modulo the field modulus. This needs to be checked in the circuit, otherwise a false remainder could be proven correct.


What you are reading is a description of how CCM is performed within the "Cryptographic Element Device. The block names are from the CCM description by NIST.

A more clear description is the following:

N = Nonce(12)

# this implements CBC(key, IV, 79 | NONCE | 01 | 00 00 | LL LL | DATA)
# taking only the last block (AES / CBC-MAC)

IV = 00000000000000000000000000000000 # presumed, it's logical

B0 = 79 | NONCE | 01 | 00 00
B'0 = CBC(key, IV, B0)

B1 = XOR(B'0, LL LL | DATA)
B'1 = CBC(key, IV, B1)

N2 = Nonce(12) # it may be that N2 should be identical to N1, look into spec

# this implements CTR(key, A0, B'1)

A0 = 01 | N | 01 | 0000 # this is the initial counter for CTR mode
A'0 = CTR(key, A0, 00000000000000000000000000000000)
R = XOR(A'0, B'1)

This is a block by block description on how CCM mode is performed internally when up to 14 bytes of data are just MAC'ed - not encrypted. You could use it to mimic the implementation if you're just given AES-CBC and AES-CTR or indeed just AES. On a normal computer you'd just use an existing library that contains CCM.


To which game-based security definition is Perfect Secrecy equivalent?

Perfect secrecy corresponds to semantic security. Or rather, semantic security is an adaption of perfect security for computationally limited adversaries, but a variant of the same definition also works for unlimited adversaries.

In other words, consider a game between an adversary and a simulator. The simulator chooses its key material. The adversary may submit messages and get their encryption in return. He then chooses a distribution over plaintext messages (all of equal length) and a binary predicate $f$, such that the probability that $f(m)=0$ is $1/2$. The simulator chooses a message according to the distribution, encrypts it and sends the challenge to the adversary. The adversary must now determine $f$. His advantage is the difference between his probability of guessing $f(m)$ correctly and $1/2$.

You need to be a bit careful with your encryption oracle and challenge ciphertext encryption, so that key material is only used to encrypt once. Once that it done, it is clear, as you say, that the encryption oracle doesn't help an adversary.

With a small amount of work, it now follows from perfect secrecy that any adversary in this game will have advantage exactly $1$. Also, if any unlimited adversary has advantage exactly $1$, it must follow that you have perfect security.

Note that if you try to adapt chosen ciphertext attacks, no reasonable definition will result in the one-time pad being secure, since it isn't secure against these attacks.


Is cryptographic function used in MAC/HMAC public knowledge?

is information about hash function in this structure a security vulnerability? Is hashing function public knowledge?

According to Kerckhoffs' principle  the adversary is allowed to know everything about the system except the key, and that includes the algorithm itself. Shannon formulated this as "the enemy knows the system".

Assuming that the system is respecting Kerckhoffs' principle, then your question is actually an assumption in the security analysis. But this depends on what kind of analysis was done for the actual system in question.

If we're looking just at the usage of any of the commonly used, state-of-the-art cryptographic functions (e.g. SHA256), then this is not a problem: The knowledge of the algorithm itself is not a vulnerability. Security is based on the key being secret and nothing else.


Is there an asymmetric encryption that works in a reverse way of RSA (encrypt using private key and decrypt using public key)?

The need you describe is called DRM, and to implement it you don't need asymmetric encryption - DRM typically uses symmetric encryption where the server encrypts the data using a symmetric key specific to the receiving client.

All that said, once the protected data is decrypted there is no technical way to prevent it from re-distribution. You can, at most, use legal means to deter unauthorized re-distribution. That holds true even if you were a multi-billion $$$ corporation such as Sony or other media behemoth.

The closest you can get to DRM protection on the technical side is to have the server transmit the data only after the client proves that it is genuine, and to have that in turn possible (to some extent) only if the client is hardware-based and non-rootable - e.g., a book reader, set-top box, game console, etc., depending on the media type.


Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

Given some PRG $G : \{0,1\}^n \to \{0,1\}^m$ with $m > n+1$, define $G' : \{0,1\}^{n+1} \to \{0,1\}^m$ like this:

$$
\begin{align}
G'(0\|x) & = G(x) \\
G'(1\|x) & = G(x)
\end{align}
$$

Lemma: If $G$ is a PRG, so is $G'$.

Proof: Let $s \in \{0,1\}^{n+1}$ be a randomly chosen seed, and let $s' \in \{0,1\}^{n}$ be its suffix (with the first bit of $s$ removed), which is also distributed uniformly at random. Since $G$ is a PRG, then $G(s')$ has a pseudorandom distribution. And since $G'(s) = G(s')$, so does $G'(s)$ have a pseudorandom distribution. So then, since $G'(s)$ is pseudorandom for random $s$, $G'$ is a PRG.

Theorem: $F_k(x) = G'(k \oplus x)$ is not a PRF.

Proof: Because of the definitions of $F$ and $G'$, we see that for all $k$ and $s$, $F_k(0\|s) = F_k(1\|s)$. Given oracle access to an $f$ that's either $F_k$ or a random function, we have the following distinguisher:

Pick an arbitrary $s$;
Query the oracle for $x_0 = f(0\|s)$;
Query the oracle for $x_1 = f(1\|s)$;
If $x_0 = x_1$, then output $1$, otherwise output $0$.

If $f$ is a random function, this outputs $1$ with probability $2^{-m}$.  But if $f$ is $F_k$, then it outputs $1$ with probability $1$.

So, there exists a choice of PRG for which your proposed construction is not a PRF.


ElGamal cipher decryption (reposted not from guest account)

You need to further specify your question. The Diffie-Hellmann Key Exchange Protocol is used to establish a secret key over a public channel. After the protocol run, both Alice and Bob have the same key $k_{ab}=A^b=B^a=g^{ab}$.

The El-Gamal system is based on asymmetric cryptography and therefore public keys and secret keys are required. Since the El-Gamal ciphertext consists of two parts $c=(c_1,c_2)$ your description of the decryption function seems to be mixed up. Have a look at the decryption formula of El-Gamal and try to calculate it step by step to understand how the cipher works.


In A5/1 stream cipher, why are the specific bits in each register chosen for the majority rule and for the XORing step?

Welcome to crypto.stackexchange. Your second question could be easily answered by a simple search on this site, or elsewhere, but anyway, here goes:

Firstly, A5/1 is well-broken, the non-uniform clocking ends up not helping much, and lots of different initial states merge as the clock ticks--look at the Wikipedia page for A5/1 for a long list of papers with attacks. Now, onto your questions:

Question 1: The majority rule bit positions are not so crucial, as long as they are not from a bit which is being fed back, or from the output bit. Also your observation in the comments: "if you used the same index for all registers, you would get a loop where all the registers shift each time" is incorrect in general. Depending on loading and feedback same any 3-tuple of bits can end up in the majority positions.

Question 2: The LFSRs used are primitive, their tap positions correspond to primitive polynomials, and give the maximum possible output sequence period of $2^L-1,$ if $L$ is the length of the LFSR, a so called maximal length sequence. So the tap positions are crucial. For more on LFSRs and periods, see, for example, the following question which asks what happens when you have non primitive LFSRs.

With the three LFSRs in A5/1 having relatively prime lengths $19,22,23$, (thus relatively prime periods) the internal state of the cipher has possible size $(2^{19}-1)(2^{22}-1)(2^{23}-1)$ instead of being much smaller. Of course due to irregular clocking not all states need be visited.


why a group used in cipher based on DLP must be Abelian group?

What you are asking is in some sense a tautology. In any group $G$, Abelian or not, the subgroup generated by an element $g \in G$ is Abelian. (Recall: the subgroup generated by $g$ is:
$
\langle g\rangle := \{g^0, g^1, g^2....\}
$
).

Hence, you can probably take your favourite DLP-based encryption scheme and implement it in $G$, without dealing with the fact that it is not Abelian. Indeed, the only fact you need is the existence of a subgroup $G_1$ with large prime order $p$.

For example, consider a large prime $p$ and the corresponding  Dihedral group $D_p$. It is one of the simplest examples for a non-Abelian group, and it has a subgroup of order $p$. Let $g$ be random element of order $p$ (that is easy to verify, since elements in $D_p$ are either of order $p$ or 2). Now, you define El-Gamal encryption as usual:

Secret key is $x \in \mathbb{Z}_p^*$ to your choice, public key is $(D_p, p, g, h = g^x)$. We encrypt a message $m \in D_p$ by choosing a random $y\in \mathbb{Z}_p^*$ and computing
$$
m \mapsto (c_1, c_2) = (g^y, m \cdot h^y),
$$
and decrypt by computing
$$
(c_1, c_2) \mapsto c_2 \cdot c_1^{-x}.
$$

Note that in an Abelian group, we could also decrypt by multiplying in a different order:
$$
(c_1, c_2) \mapsto  c_1^{-x} \cdot c_2,
$$
but, well, who cares - just remember to multiply in the right order.

An interesting question in my opinion, is what can be gained by considering an underlying group that is not Abelian. Indeed, if the presentation of the group if complicated, perhaps DLP is harder. This is the case with elliptic curve based cryptography: the groups considered are cyclic as usual, but the presentation of the group is far more complicated than $\mathbb{Z}_p$, leading to better security against DLP.


How can I prove ownership of hardware wallet?

What you need to do is find some document that associates you with the virtual or hardware wallet. The most obvious way is the receipt you used to purchase the physical wallet. If you didn't keep the receipt, the company you bought it from may be willing and able to help you.


Is $f\colon x\mapsto g(x+1)$ necessarily a pseudorandom function?

The general way to answer questions like this in the affirmative (i.e. prove that some transformation of a certain type of thing gives you another of that type of thing) is to assume that your transformed version doesn't have the property you need, and use that to prove that the original also doesn't have that property. Then if the original does have the property we want, so must the transformed version.

So, assume $f$ isn't a PRF. That means that there's an efficient algorithm with a function as its input that can reliably tell whether you gave it $f$ or gave it a random function as input, by evaluating its input at a bunch of points. You can modify this algorithm to tell $g$ apart from a random function -- because $f(x)=g(x+1)$, just tweak the algorithm so that every time it evaluates the function you had passed it at $x$, it instead evaluates it at $x+1$. If you run this algorithm with $g$ as input, it acts exactly like your original algorithm did with $f$ as input. If you pass it a random function as input, the random function is still random. So, this new algorithm can tell $g$ apart from a random function, and $g$ isn't a PRF.

Because any distinguisher for $f$ can be tweaked to make a distinguisher for $g$, it means that $g$ can only be a PRF if $f$ is, so if $g$ is a PRF then $f$ is a PRF. This kind of argument is extremely useful when building cryptographic functions using primitives; it even works when the properties of the underlying primitive and your construction are different (you show that an attack on property A of your construction lets you attack property B of the underlying primitive).


Is it safe to XOR-combine hashes by rotating them first?

First of all, if the order is not important then rotating a hash value depending on the order before using it would of course be counter-intuitive. Now the hash of a specific element is fully dependent on the order.

Generally I would not advice XOR-ing hashes.
Single rotation won't work especially if you combine multiple hashes - as you've indicated it would be easy to find a collision where two hashes cancel each other out. But you've already covered this.
XOR-ing would also make collisions easier to calculate, because the XOR of two hash values can also create a collision. Of course this won't change the order of finding a collision, but a XOR is still significantly faster than calculating a hash.
I could also imagine a scheme where you XOR (rotated) hashes that have a similar highest bit set. I think this could quickly create hashes that have the initial bits set to all zero. You could also XOR hashes that have a small Hamming distance. Either of these methods would create a set of hashes that have more than a normal amount of bits set to zero. It seems likely that these have less collision resistance than the initial hash. The fact that you can also use rotated hashes for this would make it even easier to create such attacks.

Instead you could think of sorting the hashes before you hash them (using a binary compare). That way you get a unique hash for a unique set where the order is ignored, even if it can contain identical elements. The disadvantage is that you cannot calculate a new hash value by adding a hash value after the final hash calculation is performed.


Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas.

The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure:

Preparation phase: find a adequate representation of the desired structure and choose a smoothness basis, i.e. a set of small elements.
Phase I: Find many multiplicative relations between elements of the smoothness basis. Simple example: $2\cdot 3 = -1 \pmod{7}$. You need more equations than the number of smoothness basis elements.
Formally taking logarithm of all multiplicative relations, we get linear relations between logarithms of small elements.
Phase II: Perform linear algebra. Here the details vary between Dlogs and factoring. For Dlogs, finding a non-zero kernel element modulo the group order directly gives the logarithms of the small elements. For factoring, you search instead for a kernel element in the transposed system modulo 2. This correspong to finding a product of the initial relation where all elements will appear with an even exponent.
Phase III: Conclude the computation. For Dlogs, this is the individual logarithm phase. For factoring, we extract from the above linear relation two elements whose squares are equal, say $A^2\equiv B^2\pmod{N}$, with probability $1/2$, the gcd of $A-B$ and $N$ yields a non-trivial factor of $N$. If it does not work, try another relation.

The Wiedemann algorithm is an iterative method for the linear algebra phase. Usually, when working modulo $2$, block Wiedemann is used. This method allows to compute many relations (as many as the block size), after computing a sequence of matrix by vector block product. The reason for using this approach (or Lanczos method) for solving the system is that it is much faster and much more efficient in terms of memory than Gaussian elimination for the large linear systems that are involved.

With NFS, some of the details become mathematically quite involved. For this reason, I will just add a few more points.

Preparation phase: $N$ is represented by finding two polynomials $f$ and $g$ of relatively small degrees and small coefficients with a common root $R$ modulo $N$. Most of the time, one of the two polynomials is linear. On the linear side, the smoothness basis contains small prime numbers. On the other side (algebraic side), the smoothness basis contains degree one ideals of small norm.
Multiplicative relations generation. Take an element $a+bX$ and send it to $a+bR$ on the linear side and to the ideal generated by $a+b\alpha$ ($\alpha$ a complex root of the polynomial defining the algebraic side). If both side completely factor into elements of the smoothness basis, you get a relation.
Linear algebra and square root. This becomes more difficult than in the general case, because to get a relation $A^2=B^2$ it is not only necessary to have even exponent on the ideal side, you also need to make sure that the resulting value is a principal ideal. This is done by adding multiplicative characters in the relation matrix before the linear algebra step.

Hope that helps.


NTRUEncrypt - Choose the initial random polynomial

So long the GCD of f(1) with p and with q is 1, f will have an inverse with high probability. (f(1) = f evaluated at 1, i.e. the sum of the coefficients of f).

If you take f to be binary with df 1s, then take df to be relatively prime to p and q.

If you take f to be trinary and it has df 1s and df-1 -1s, then f(1) = 1 and this will satisfy the GCD requirement identically.

If you take f to be of form 1 + pF, f(1) is 1 mod p and satisfies that requirement identically. For the GCD requirement mod q, either pick F to be trinary with equal +1s and -1s (so f(1) = 1) or pick F to be binary such that 1 + p*F(1) is relatively prime to q.

"High probability" above means that the probability of not having an inverse goes down rapidly as both q and N increase. I've posted toy examples on Stack Overflow (http://stackoverflow.com/questions/2754444/meet-in-the-middle-atack-on-an-ntru-private-key) and when I generated them I came up with invertible keys on the first attempt for N = 11, q = 29.


Certificate public key keyexchange, Which key exchange is used in browsers?

The RSA encryption algorithm implies two types of keys: a public key and a private key. The public key is composed from the public exponent $e$ and modulus $n$. The private key is composed from the private exponent $d$ and modulus $n$. The relationship between them is $(e,d)\ ≡\ 1\ (mod\ φ(n))$. To encrypt, you rise the plaintext to the power $e$ and to decrypt you rise the ciphertext to the power $d$ (both operations are done modulo $n$). More detalis here. The traffic between you and StackExchange is encrypted under the TLS protocol. The TLS protocol uses a hybrid encryption scheme. That is, you first generate a random key, say K, that you'll encrypt with RSA using the public key of StackExchange. The StackExchange will decrypt the key K using its private key.
From now on you will both use a symmetric algorithm (AES 256) to encrypt your data. The encryption key for this symmetric algorithm will be the K key, which you previously encrypted using RSA. More detils about TLS here.


Security of ChaCha compared to AES and Serpent

This answer has 2 parts, the 1st on "quantifying" the security of unbroken ciphers, the 2nd on the choice of ciphers for different usage scenarios.

If (on a scale of 1 to 10) AES is 5 and Serpent is 10, what would ChaCha be?

First, you have to quantify their security in order for the scores to be meaningful. The quantification must have a basis, such as "security margin" mentioned in the comments.
This answer does not intend to provide concrete values for the scores or detailed formula, but provide a outline on how it might be calculated.
With "security margin" as quantification metric, we can proceed as follow: Most ciphers operate iteratively in rounds, each round increases the diffusion and confusion of the input - the amount diffusion and confusion obtained in each rounds are usually an order of magnitudes great, so the quantification should be an index rather than a factor.
With these in mind, we can look at

$r$ the number of rounds each cipher has,

$r_a$ the number of rounds attacked, and

$w$ the time-space-query (optionally success probability) tradeoff required for the attack. This is measured in security-in-bits murdered by the attack, divided by bit length of the key.

We get a rough score for the index of security margin of the cipher:
$$ r \over {r_a \cdot \log(w + 1)} $$
Because we're considering both the threat and the feasibility of attacks, multiple attacks must be considered for a given cipher to find its final actual minimum score.

I'm looking for ...

This question asks for security at rest of data in the cloud, but others seeing the title of this question may look for something slightly different.
ChaCha is notable for its inclusion as "stand-by cipher" in TLS, as such, the reasoning led to such decision is worth analyzing. We'll reference https://tools.ietf.org/html/draft-mcgrew-standby-cipher-00 for this purpose.
The first thing to consider, is, how easy is it to change the cipher?

For internet transport protocols, changing cipher is as easy as re-connecting to the server and negotiate a new cipher. The biggest burdon is on library implementations to add the support for that cipher.

For data at rest (in cloud, or offline), it'll be easy for new data to be encrypted with the new cipher. For existing data, we'll have to "trans-cipher" them by first decrypting them with the old cipher and re-encrypting them with the new one - this is a long and slow process with possibility of unexpected failures.

For hardware devices, changing the cipher will often be impractical without replacing the hardware in entirety.

The 2nd thing, is balance of diversity of paradigm, verses the burdon of supporting multiple algorithms.
The linked IETF draft set out explicitly, that, the stand-by cipher should have a different design than AES. This way, non-generic attacks that're applicable to AES will not be applicable to the new stand-by cipher (and a 2nd stand-by cipher may be sought when such attack to AES is found).
The linked IETF draft also set out, that, in order to lighten the burdon of implementations, only 1 stand-by cipher is to be selected. A clever stratagy for prosumers would be to encrypt files of different importance using different ciphers (and keys of different strength), but this have to be balanced with availability of support of new ciphers in older softwares. Otherwise, most-needed files encrypted with newer algorithms may not be readable using older softwares.


Attribute Authentication in Attribute Based Encryption (ABE)

If you take a look at the KP-ABE paper or the first paper proposing the idea of ABE you can see that the set of attributes one claims to have is not authenticated.

In fact there is a setup phase during which one will take the attributes one wants to publicly disclose, and will generate a discrete logarithm public key, so to say, for each of those attributes and a key generation phase during which the same "authority" will generate private keys for each of those attributes.
One can then publish the set of attributes, the "set of attributes' public keys", as well as a randomly chosen integer $y$. And those publicly disclosed keys can then be used to encrypt data for a subset of those attributes, by whoever wishes to do so.

Now, the magic of ABE is that when you decide to encrypt for a given subset of attributes, only the persons owning all of the corresponding attributes' private keys (generated at the key generation phase by the "authority") can then combine this subset of keys in order to decrypt that ciphertext.
The persons who do possess all of these attributes' private keys can then perform the so called decryption phase, which will the bilinear map $e$ used to "stitch together" the plaintext only if the ciphertexts was addressed to the given subset of attributes out of all the attributes' keys one may possess.

However the way one distributes the attributes and their corresponding private keys created during "setup" to individuals for them to perform "key generation", is not taken into account by the scheme itself and should obviously be done in a secure, authenticated way which deals appropriate attributes to each individuals.

So, the "authority" generating the public keys and the private keys must effectively assign the attributes' private keys to the people who "own" those attributes, but the ABE schemes themselves do not take care of this practical aspect of the problem.


How to find the inverse of a polynomial in NTRU-PKCS

Disclaimer: I'm not familiar with NTRU, and not in my comfort zon. Hence the many edits.

The problem asked can be summarized as: given $n$, $q$ coprime to prime $p$, and for $0\le i<n$ the coefficients $f_i\in\{-1,0,1\}$ of $F=\displaystyle\sum_{0\le i<n}f_i$, find the $n$ coefficients $q_i$ of $F_q$ and $p_i$ of $F_p$ such that, with polynomial multiplication performed modulo $x^n-1$, $F\cdot F_q\equiv1\pmod q$ and $F\cdot F_p\equiv1\pmod p$, or determine that's impossible.

We can treat the problem for $F_q$. The same method will apply for $F_p$. Alternatively, since $q$ and $p$ are coprime, we can find $H$ with $F\cdot H\equiv1\pmod{(p\,q)}$ and if it exists reduce its coefficient modulo $q$ and $p$ to find the $q_i$ and $p_i$ (but if there's no $H$, we could only conclude that at least one of $F_q$ or $F_p$ does not exist).

One conceptually simple method is to see the problem as a system of $n$ linear equations in $\Bbb Z_q$, with $n$ unknowns $q_i$, obtained by using the question's definition for the equivalent equation $F_q\cdot F\equiv1\pmod q$:
$$\forall k\in[0,n-1),\quad \sum_{0\le i<n}q_i\,f_{(k-i\bmod n)}\equiv\begin{cases}1&\text{if }k=0\\0&\text{otherwise}\end{cases}\pmod q$$
and use Gaussian elimination.
If we use the question's $F=1+x^3-x^4-x^5$ for $n=7$, that linear system goes$$
q_0-q_2-q_3+q_4\equiv1\pmod q\\
q_1-q_3-q_4+q_5\equiv0\pmod q\\
q_2-q_4-q_5+q_6\equiv0\pmod q\\
q_3-q_5-q_6+q_0\equiv0\pmod q\\
q_4-q_6-q_0+q_1\equiv0\pmod q\\
q_5-q_0-q_1+q_2\equiv0\pmod q\\
q_6-q_1-q_2+q_3\equiv0\pmod q$$
that is, by realigning$$\begin{matrix}
+q_0&    &-q_2&-q_3&+q_4&    &    &\equiv1\pmod q\\
    &+q_1&    &-q_3&-q_4&+q_5&    &\equiv0\pmod q\\
    &    &+q_2&    &-q_4&-q_5&+q_6&\equiv0\pmod q\\
+q_0&    &    &+q_3&    &-q_5&-q_6&\equiv0\pmod q\\
-q_0&+q_1&    &    &+q_4&    &-q_6&\equiv0\pmod q\\
-q_0&-q_1&+q_2&    &    &+q_5&    &\equiv0\pmod q\\
    &-q_1&-q_2&+q_3&    &    &+q_6&\equiv0\pmod q\end{matrix}$$
The matrix of coefficients is circulant, and its last line has the coefficients of $F$ in reverse order.

This one happens to have no solution except for $q=1$: if we sum all the lines we get $0\equiv1\pmod q$. Mere generally, except for $q=1$, there can't be a solution when $0=\sum f_i$ as in the example.

While we could in general solve the system (or find that it has no solution) by Gaussian elimination and careful application of arithmmetic in $\Bbb Z_q$, that has cost $\mathcal O(n^3\,\log q\,\log\log q)$ and uses $\mathcal O(n^2\,\log q)$ memory. And while there are better methods for a circulant matrix, I won't go further into that.

Better methods to solve this problem are derived from the Extended Euclidean Algorithm, which given $A$ and $B$ in a principal ring, finds $U$ and $V$ in that ring with $A\cdot U+B\cdot V=G$, where $G$ is the Greatest Common Divisor of $A$ and $B$. As a byproduct that gives the modular inverse $U$ of $A$ modulo $B\ne0$, or tells that it does not exist when $G\ne1$.

That algorithm finds the inverse in particular in these rings:

The ring $\Bbb Z_q$ (the integers), where for non-negative $a$ and $b$ it can go:

If $b=0$, output "$a$ has no inverse modulo $b$" and stop.
$c\gets a$, $d\gets b$, $u\gets0$ and $v\gets1$.
Repeat

If $c=0$, output "$a$ has no inverse modulo $b$" and stop.
If $c=1$, output "the inverse of $a$ modulo $b$ is $v$" and stop.
Perform Euclidean division of $d$ by $c$ yielding quotient $z$ and remainder $r$ with $0\le r<c$.
$d\gets r$ and $u\gets u+z\cdot v$.
If $d=0$, output "$a$ has no inverse modulo $b$" and stop.
If $d=1$, output "the inverse of $a$ modulo $b$ is $b-v$" and stop.
Perform Euclidean division of $c$ by $d$ yielding quotient $z$ and remainder $r$ with $0\le r<d$.
$c\gets r$ and $v\gets v+z\cdot u$

The ring of polynomials with coefficients in the field $\Bbb Q$ (the rationals), where it can go:

If $B=0$, output "$A$ has no inverse modulo $B$" and stop.
$C\gets A$, $D\gets B$, $U\gets0$ and $V\gets1$.
Repeat

If $C=0$, output "$A$ has no inverse modulo $B$" and stop.
If $C$ has degree $0$ (that is, has only term $c_0$), output "the inverse of $A$ modulo $B$ is $(1/c_0)\,V$" and stop.
Perform polynomial division of $D$ by $C$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $C$.
$D\gets R$ and $U\gets U+Z\cdot V$.
If $D=0$, output "$A$ has no inverse modulo $B$" and stop.
If $D$ has degree $0$ (that is, has only term $d_0$), output "the inverse of $A$ modulo $B$ is $(-1/d_0)\,V$" and stop.
Perform polynomial division of $C$ by $D$ yielding quotient $Z$ and remainder $R$ of degree less than the degree of $D$.
$C\gets R$ and $V\gets V+Z\cdot U$.

The ring of polynomials with coefficients in a finite field $\Bbb Z_p$ for prime $p$: same as above, except that when a coefficient $\displaystyle\frac st$ is obtained, we replace it with the integer $0$ when $s=0$, or otherwise with the integer $(t/\gcd(s,t))^{-1}\,(s/\gcd(s,t))\bmod q$.

The later is exactly what we need for $F_p$: we feed $A=F$ and $B=x^n-1$ to the algorithm, and it computes $F_p=A^{-1}\bmod B$ (or tells that is does not exists).

However, for a composite $q$, it can appear $\displaystyle\frac st$ that can no be brought back in $\Bbb Z_q$ because $\gcd(t,q)\ne1$.

I'm not sure about:

If we can conclude that when we hit the problem, we can stop and conclude that $F$ is not invertible.
If we can compute the inverse in the ring of polynomials with coefficients in the field $\Bbb Q$, and reduce in the end. I think we could find that $F$ is not invertible, but it really is invertible modulo $q$.

When $q$ is the product of distinct primes, we can get around that by finding the inverse modulus each prime dividing $q$, and using the Chinese Remainder Theorem to work back the coefficients of the inverse modulo $q$. We do not need to know the factorization of $q$ in advance: when we hit the problem, the GCD gives us a (perhaps partial) factorization of $q$. However I'm not sure of what to do when $q$ is divisible by a square of a prime.

Under work: further straighten that, example.

For a full-blown, faster method, see Joseph H. Silverman, Almost Inverses and Fast NTRU Key Creation, NTRU Technical Report #014, 1999.


How to calculate time taken by encryption?

The speed depends a lot  on the exact model of the processor, and on the software. New(-ish) processors with hardware support for AES are much faster than older processors without it (AES-NI in x86 processors) and an optimized implementation might be quite different from a generic one, especially if the latter doesn't even use the hardware support...

For older processors (without hardware support), some speed tests can be found here. The best numbers for Core 2 family processors were around 12 clock cycles per byte for CTR mode, which would make for about 230 MB/s at 2.8 GHz. For newer processors with AES-NI support, some numbers here, ranging from 600 MB/s to 1500 MB/s per core for CBC mode and 700 MB/s to 2600 MB/s for GCM mode with processors from 2010 to 2015 (with various clock speeds).

(A quick and dirty test with the OpenSSL command line tool on a low-end Xeon processor from around 2012 gave figures in the same ballpark as in the previous link.)

Note that if you care about speed, it seems you shouldn't be using CBC mode. For many processors on the list (as well as the one I tested on), AES-128-GCM is quite a bit faster than AES-128-CBC. And that's without any authentication in addition to CBC encryption. I assume the reason is that CBC encryption is inherently linear: encrypting a block requires the ciphertext of the previous block. This will limit the number of parallel operations the processor can do. For the same reason, multiple cores will not help in encrypting a single, long, chain. The authentication part of GCM encryption is also fast, because there's special hardware support for that, too. (the CLMUL instructions)


All Diffie-Hellman (including EC) uses two keypairs and produces one shared secret. The colors in the wikipedia article are only a metaphor; the actual process for original DH, now retronymed 'integer' or 'finite-field' DH if necessary to distinguish, uses a sufficiently large generated subgroup of the multiplicative group of integers modulo a prime (in current practice, a 2048-bit prime), while Elliptic-Curve DH (ECDH) uses an elliptic curve satisfying certain criteria, or to be precise the group generated on the curve by a base point.

Ephemeral is only(!) about timing. DH requires the parties each have a keypair (private and public key) at the time of the key agreement operation (for TLS, the handshake that creates a session). It cares nothing about how long before the operation these keys were created, or how long after the operation they are retained. You can create one DH keypair and use it all your life assuming it is strong enough and you keep it secure, or you can create a new keypair every millisecond, and the DH algorithms (integer or EC) work exactly the same either way.

However, in practice to use a keypair longer than a few minutes or hours at most you normally need to store it somewhere, because computers occasionally fail or must be shutdown for various reasons. There is always some risk a stored keypair can be compromised, although a wide variety of methods can be and are used to try to prevent compromise.

Ephemeral mode of (EC)DH does not store the keypairs and thus avoids this risk. They are created (at each end) immediately before doing the key agreement and discarded (securely!) immediately after. This provides Perfect Forward Secrecy, or just Forward Secrecy. Unless you have a bug like Heartbleed, or other side channel such as shared-VM interaction, that allows an adversary to get that information during the brief period it is in memory.

Yes ephemeral DH and ECDH are used in TLS, including but not limited to DHE-RSA and ECDSA-RSA which are authenticated (signed) with RSA as @SEJPM noted, instead of ephemeral RSA, mostly because generating RSA keys is more costly and in particular usually too costly to do at session initiation, while it is very practical to generate RSA keys used on a long-term basis (typically a year or more) for authentication.


With sufficient randomness, is XOR an acceptable mechanism for encrypting?

It's important to make the distinction between ciphers which use XOR
internally as a component operation (which is nearly all of them),
and 'ciphers' which just XOR the plaintext with a secret. If the key
is the same length as the plaintext, then it's a one time pad, so in
some sense, yes, with "sufficient randomness" you can safely encrypt with XOR.
The problem with this is that it only applies if the key is
exactly as long as the plaintext, and is perfectly uniform random.
If it's not, then you've basically created a Vigenere
cipher, which
can be trivially broken. It's interesting, and unfortunate, how
the 'provable security' of the OTP fools people into thinking
they can just take a little shortcut or two and still get
something safe.

Typically, people who implement simple XOR ciphers compound their
mistake by using hard-coded keys, in which case a single known
plaintext/ciphertext pair is sufficient to decrypt anything.
That's probably mostly because if you were some kind of prebuild
crypto toolkit, it would be easier to just use AES along with your
RSA key management, etc, versus using a decent key distribution
scheme and then using XOR with your safely shared keys.


Sure, there are many ways. For instance, if you need to enter key manually, you may even prefer to split text representation into groups of 4 or more characters.

But I'd suggest you choose between SSH2 (RFC 4716) and OpenSSH format. Both use Base64 for key representation. Both have an advantage that they are supported by standard tools like ssh-keygen.

If you have multiple keys and want to more reliably distinguish them, I'd suggest SSH2 (RFC 4716), because it provides slightly better possibilities to comment.


How does GPG verify succesful decryption?

This is hidden well in RFC 4880, the OpenPGP message format specification.

Section 5.7 explains how message data is encrypted. (I'm using the values for a 16-byte block cipher like AES.)

A random block of data is created: $p_{1} \dots p_{16}$
The last two bytes of this block are repeated: $(p_{17}, p_{18}) := (p_{15}, p_{16})$.

These 18 bytes (in case of AES or another similar block cipher) are encrypted in CFB mode (with a zero initialization vector), i.e. $(c_{1} \dots c_{16}) = E_K(0, \dots 0) \oplus (p_{1} \dots p_{16})$, and $(c_{17}, c_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (p_{17}, p_{18})$.

When decrypting, we just have to decrypt these 18 bytes $c_1 \dots c_{18}$ (i.e. we calculate $p_1 \dots p_{16} = E_K(0) \oplus (c_{1} \dots c_{16})$, $(p_{17}, p_{18}) = \text{first 2 bytes of}(E_K(c_{1} \dots c_{16})) \oplus (c_{17}, c_{18})$) and check $p_{15} = p_{17}$ and $p_{16} = p_{18}$. If these are not the same, we throw the "bad key" error message.

Of course, this is only a heuristic check: One in each $2^{16}$ keys will still look right.

If you need a more certain check of the right key, use either a digital signature (in the encrypted package), or use a "Symmetrically Encrypted Integrity Protected Data Packet" (section 5.13) instead of a plain encrypted packet.


Proof possession of private key in libsodium

If you are going to public the same message with a signature multiple times, it is vulnerable to a replay attack. This is where another party basically copies your message and signature and can re-publish it at any time, implying that they own the key. To counter this, add a small piece of information to the message before signing, say a counter or random number that is unique per signature published.

As for trusting signing keys, a trusted party ie a Certificate Authority or a PKI must be used so that any data received from them is trusted. So when Alice publishes a message and a signature, the CA tells people Alice's static public key, this is trusted, and then everyone can safely verify the fact that Alice does indeed own the private key she claims to own.


What prevents ProtonMail from sending me the wrong public keys?

ProtonMail has a support page about this topic.

ProtonMail does not transparently solve this problem. By default, the client has no way to know if the server has provided the correct public key, it just implicitly trust keys sent by the server. Therefore, by default the client has no way to protect against man in the middle attacks from the ProtonMail server.

However There is an option to turn on manual trusting of keys, "Settings > Security > Address Verification (optional) > Prompt to trust keys". In this case, when encountering an unknown public key, the ProtonMail client will notify the user that the key is not trusted, and prompt them to "pin" the key. Keys must be pinned, per contact. Messages to contacts without pinned keys will be sent using keys from the ProtonMail server.

A pinned key is stored locally the client, and (presumably) encrypted and sent to the server, so it can be used from other devices when decrypted with the user's password. The client will always use the pinned key to encrypt messages for the corresponding address, and it will display an error if a message received from that address isn't signed with the correct key. It up to the user to verify that the key is correct, like in normal PGP.


If the KEM is only CPA-secure, then the resulting scheme might not be CCA-secure. For example, consider a CPA-secure KEM that ignores the last bit of its ciphertext. Then it is possible to modify a KEM ciphertext in a way that doesn't affect its payload, which is enough to break CCA security of the hybrid scheme.

If the KEM and DEM are both CCA-secure, then the overall hybrid scheme is also CCA-secure. This is proved formally in Section 7 of:

  Cramer, Shoup: Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack

However, it is possible to have a CCA-secure hybrid encryption scheme where the KEM is (slightly) weaker than CCA secure. This was first demonstrated in:

  Kurosawa, Desmedt: A New Paradigm of Hybrid Encryption Scheme

The weakened KEM security definition and composition theorem for hybrid encryption were formalized/generalized in:

  Hofheinz, Kiltz: Secure Hybrid Encryption from Weakened Key Encapsulation


How to communicate by email with forward secrecy and deniability?

OTR can provide forward secrecy because both partners create fresh ephemeral (one-time-use) keys, which are discarded afterwards, so they can't be recovered by later attackers.

The long-term public keys are only used to authenticate them, to avoid any man-in-the-middle attack.

For offline communication like e-mails this is not easily possible, since the receiver can't contribute an ephemeral key, as already mentioned by CodesInChaos.

If you can live without the forward-secrecy (only the other three properties), you can use long-term Diffie-Hellman keys, do an offline DH-exchange with them and derive from the result (preferably with some salt-like entropy input so not each mail has the same) symmetric keys for both encryption and MAC. The receiver then knows that you and her are the only ones which knew the DH result, and thus the encryption and MAC keys, so only one of you both can have sent this. But she also could have created the message herself, so you have deniability, too. Thanks to CodesInChaos for the comment.

If you can beforehand (maybe over an OTR-chat) consent with your partner about a symmetric key, you can simply use symmetric encryption and a MAC in your email, and get the encryption, authentication and deniability (the receiver could have created the same message, as she knew the same key). If both partners delete the symmetric key after the sending/receiving of the message, it is also forward-secret. But it still is not really an offline communication as the online key exchange is needed.

Of course, we could stretch a protocol like OTR over a message exchange by email. But then both mail clients (or some other software which handles the protocol) would have to store crypto status between the individual messages, which also harms the "perfect forward secrecy", since this status could be potentially recovered. (You could switch the key with each message, and discard old ones as soon as you receive the next key from your partner, and send a new message after any important message to limit the time keys have to be hold in storage.)

The paper you linked in section 6 ("EMAIL") mentions this possibility, as well as a "Ring signature", which provides slightly smaller guarantees.


Including the next random One Time Pad as part of the encoded message?

Is the fact that the next OTP is included at a known location in every encoded message a factor that will allow decryption of the messages given a few encrypted messages? Or will it be as secure as a normal OTP?

Yes, that's a big problem.

You're practically transporting the (next) OTP you're adding at the end of your ciphertext in the open. Differently put: you're sharing the (next) secret unprotected and in plain sight of any potential attacker.

This is especially true when assuming we – as we usually do – respect Kerckhoffs’ principles. The attacker would know that you’re adding the next OTP to the end of the current ciphertext, and can therefore extract the next secret easily.

Even when we wouldn’t respect Kerckhoffs’ principles and keep your construction secret, it wouldn’t be too hard for an attacker who intercepted merely 2 transmissions to grasp what you’re doing… which includes that the attacker also gains the bonus of being able to simply decrypt that 2nd intercepted message, and also gaining knowledge of the next OTP you’re going to use for transmission number 3. That’s definitely not what you want…

OTP security claims

You’re somewhat violating the definition of OTP (points 2, 3, and maybe 4):

  Per definition, OTP requires the “key“ to be…

  a truly random one-time pad value,
  generated and exchanged in a secure way.
  at least as long as the message, and
  only to be used once.

I’ll leave it up to personal opinion if your idea aditionally violates point 4, as that depends a bit on the individual point of view. While others might disagree, I personally see something which might be interpreted as reuse.

In the end, that doesn’t reall matter because violating points 2 and 3 is already more than enough to say that the usual OTP security claims are in no way applicable when looking at your construction.

Other problems related to your construction

Please note we’re not yet talking about potential authentication issues – for example: you need to think about an attacker intercepting your messages, modifying them, and then forwarding them without you being able to detect the modification. In most scenarios, this is disastrous. Fact is, OTP itself doesn’t handle authentication by nature… that’s where MACs come in.

TL;DR:

Never, ever share/transmit a secret (here: next key) in an unprotected manner.
Always think about authentication, because simply encrypting something doesn’t mean it’s safe from being forged. You should – at least – be able to detect message forgery.

EDIT

This edit include the comments posted to this answer, to make the answer more complete and to safeguard the infos contained so they don't vanish when comments get cleaned up (aka deleted).

  OP: Hi e-sushi, thx for your detailed answer. I think perhaps you're misunderstanding. I'm not including the next OTP at the end of the cypher text, but as part of the cypher text. So basically I'm doing what Daniel described: "...  padding the ends of messages with random data, encrypting (message + random), then decrypting and collecting the random data at the end, and using this later as another one time pad ...". The first pad will be exchanged in a secure way of course and all subsequent "compressed" pads will be the same length as the message. Yep, will still get to MAC thx :-)

  ME: Same problem… as you're including the next OTP with the current message. So, xorring the 2nd half of message 1 with the first half of message 2 will reveal the key you included in message 1… which allows decryption of the first half of message 2.

  ME: In the end, you’re having a chicken-and-egg problem (better pidgeon hole problem) there. OTP key should be 100% length of plaintext. So, you can’t add plaintext to your “next OTP“ as that would not be OTP anymore. The only solution is that you do bit fiddling which would overlap and boils down to a double-XOR… $(m \oplus nextOTP)  \oplus currentOTP)$. There’s no way to create an OTP  going $(m | nextOTP) \oplus currentOTP$ because $nextOTP$ and $currentOTP$ MUST have the same length. Otherwise you wouldn’t be able to transmit that next OTP. Even in an optimal case, each transmission would halve the space available to transmit the next key material.

  OP: Aha, okay I see, so it's leads to the same problem as re-use of an OTP. Oh well, I thought maybe it was a nice way to get new pads distributed. Never role one's own encryption, lol. The best is just to include info of where to get the next pad in the message, or use a book, or some stream of random data seeded with a random key perhaps.

  ME: @Sci Yep, which is why I mentioned that “ While others might disagree, I personally see something which might be interpreted as reuse.“ in my answer. ;) Indeed, including a hint (on the location where to find the next OTP) in your plaintext message seems more logic as it voids the issue. Related to adding a MAC to the whole thing just to make it safer and more complete – simplest would probably be a HMAC (hash-based MAC). Please see Should we MAC-then-encrypt or encrypt-then-MAC?. It's not difficult to add but you need to do it correctly.

EDIT 2

Last but not least, @tylo's comment completes it:

  I think this answer has most of the essentials, but there is one misconception, which is not adressed yet: Due to the Kolomogorov complexity a real one-time-pad can not be compressed on average. And using a "compressible OTP" would not be truly random and uniform.


NIST Diffie-Hellman prime: how was it picked? Where did it come from?

Is this number specified anywhere?

It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC).  However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular.

  Why was this particular number picked?

Well, it's a safe prime; in addition, the leading 64 bits and the trailing 64 bits are all 1's; this makes certain operations somewhat more efficient.

The middle bits are (mostly) from the binary expansion of $\pi$; this was done to demonstrate that this number wasn't chosen with a secret weakness in mind; making this a 'nothing-up-my-sleeve' number.

The procedure used to select this number was created by Richard Schroeppel; the earliest reference I have for that is this RFC, appendix E

  Is this number used for anything other than Diffie-Hellman?

Not to my knowledge; as a well-known prime, it's not suitable for RSA, and it's too large to be really useful for elliptic curves.  And, as it doesn't have a moderate sized subgroup, it doesn't work well for DSA (as the signatures would be far larger than required).  It'd work for El Gamal and IES, however those are really Diffie-Hellman being reused in a public key encryption context.


Transferring Encrypted One-time pad over the internet

No, encrypting the key with another cipher (AES) reduces the security of OTP to the security provided by this cipher (AES) or by the security measurement used to protect the encrypted key.

First of all, another requirement for OTP to be 100% secure is, that the key is chosen from random.

Example:

Assume Alice and Bob share a secret AES-Key $K_{shared}$. Alice generates a new, random key $K_{OPT}$ and encrypts it using AES: $C = Enc_{K_{shared}}(K_{OPT})$.
Alice sends the encrypted key $C$ over to Bob (lets ignore the
problem of authentication etc. for the moment).
Eve intercepts the message. In order to retrieve $K_{OPT}$, Eve has to decrypt the message $C$. This takes only as much effort as it takes to break the cipher based on the key $K_{shared}$.

The encrypted $K_{shared}$ is supposed to look like gibberish, but only to the extend, that a cipher(AES) is able to achieve.

If you are actually looking into exchanging a OPT key without meeting take a look into Quantum Key Exchange: https://en.wikipedia.org/wiki/Quantum_key_distribution
But thats more like the art of black magic than cryptography ;)


Computationally expensive key derivation whose difficulty is asymmetric

The immediately obvious way to do this is to use RSA in a large-public-exponent format.

That is, the server selects an RSA modulus, and a large public exponent (say, $e = 2^{2^{30}}+1$) [1]; if the RSA primes are safe primes, this practically eliminates the possibility that $e$ is not relative prime to either $p-1$ or $q-1$.  The server would internally compute the CRT parameters (which are the same size as for normal RSA with the same modulus size, and the large $e$ value does not complicate this computation), and publish the public parameters (the modulus and the large $e$ in some compressed format; e.g. if it's always in the form $2^{2^x}+1$, we might just denote $x$).  We would also select a good RSA encryption padding method, such as OEAP.

Then, we have $\mathcal{F}_C(Y) = \text{Depad}( Y^e )$ (where $\text{Depad}$ is the procedure for removing the RSA padding); to compute $Y$, the server would take $K$, randomly pad it, and then perform the RSA private transform.

The client would need to perform $O( \log e )$ modular multiplications to compute $\mathcal{F}_C$; by selecting $e$ sufficiently large, we can make this as expensive as we like.  And, while the inverse computation of $\mathcal{F}_S$ isn't exceptionally cheap (it's about as expensive as generating an RSA signature or doing an RSA public key decryption), it isn't that bad (and we could reduce the cost somewhat if we used multiprime RSA).  And, if the server had some RSA acceleration hardware (which is not rare), this can be even cheaper.

Obviously, this is not the normal use of RSA, either as a public key encryption method, or as a signature method.  It is still a valid use of the concept.

[1]: Note: I'm using $e$ to describe the public exponent we give to the client, not the cost factor (as the question used it).


The lack of a generic security reduction for MAC-then-encrypt is basically only for pathological cases where an encryption scheme admits modifications to the ciphertext that don't affect the plaintext, like AES-CTR with an extra bit of key stream appended to the message on encryption and ignored on decryption.

So is your AES-CMAC-then-AES scheme or an AES-GCM variant secure?

AES-CMAC-then-AES.
What you described is a deterministic nonceless authenticated encryption scheme.  As such, it can't conceal repeated messages, but otherwise it provides confidentiality and authentication, as long as you reject invalid MAC tags before even thinking about the data.  Finding a way to reject replayed messages is your responsibility.

AES-GCM.
AES-GCM is a deterministic nonce-based authenticated encryption scheme.  That is, AES-GCM is a different kind of cryptosystem from AES-CMAC-then-AES.  If you can provide a 96-bit nonce for each message, e.g. a message sequence number, then it provides about the same security.*

AES-GCM is also quirky about nonce sizes: With a nonce size other than 96 bits, AES-GCM's security diminishes, because of the low but nonnegligible probability of collision in the internal 96-bit nonce derivation.  And, of course, with a repeated nonce, AES-GCM's security vanishes.

But for the scenario you described, both more complex than you need!

(CAVEAT LECTOR: This is not a peer-reviewed academic journal of cryptographic designs.  This is a pseudonymous stranger on the internet blathering crypto at you.)

You could use $C = \operatorname{AES}_k(D \mathbin\Vert 0^{64})$, and reject decryption if the message does not end with 64 zero bits.

For uniform random permutation $\pi\colon \{0,1\}^{128} \to \{0,1\}^{128}$, the adversary's chance of guessing a ciphertext $C'$ for which $\pi(C')$ has 64 trailing zero bits in one try is $2^{-64}$, which is the best you could hope for with an 8-byte authenticator anyway.

Obviously, $\operatorname{AES}_k^{-1}$ for uniform random $k \in \{0,1\}^{128}$ or $k \in \{0,1\}^{256}$ is not exactly a uniform random choice of permutation, but the attacker's advantage knowing $\pi = \operatorname{AES}_k^{-1}$ for some key $k$ is negligible: even in their worst case when $D$ is uniform, they have a far better chance of guessing $D$ or forging $C'$ than of guessing $k$.

* The short messages are critical here because the attacker's forgery probability is about $2^{-\tau}$ for CMAC but $\ell \cdot 2^{-\tau}$ for GCM, for $\tau$-bit tags and up to $128\ell$-bit messages, when the tag size $\tau$ is much smaller than the cipher block size 128.

Specifically, let $n$ be the block size in bits; $\tau$, the tag size in bits; $\ell$, the maximum message length in $n$-bit blocks; $q$, the number of oracle queries; and $f$, the number of forgery attempts.  Assume a uniform random permutation; $\operatorname{AES}_k$ is a good enough approximation.  For CMAC, the attacker's forgery probability is bounded by $$O(q \ell^2) 2^{-n} + 1 - \operatorname{Binom}(0; f, 2^{-\tau}) = O(q \ell^2) 2^{-n} + 1 - (1 - 2^{-\tau})^f,$$ which, for $f \lll 2^\tau$, is approximately $O(q \ell^2) 2^{-n} + f 2^{-\tau}$.  For GCM, the attacker's forgery probability is bounded by $$1 - \operatorname{Binom}(0; f, \ell 2^{-\tau}) = 1 - (1 - \ell 2^{-\tau})^f \approx f \ell 2^{-\tau}.$$

If $\tau$ is, say, 32, and you authenticate messages of up to 64 KB, CMAC limits the forger's success to about one in four billion, while GCM limits the forger's success to about one in four thousand.


ZKP of the validity of a decryption key without revealing the message in public

You could solve the problem using a kind of cryptographic commitment, but it requires an additional message from Bob.

(I'm assuming $k$ is a symmetric key from the context of your post)

Alice picks another message, $m_2$, and posts $E_k(m_2)$ and $Hash(m_2)$, using a cryptographic hash function like SHA-256 or what you.

Once Bob gets $k$, he uses it to find $m_2$, and then reveals it. Anyone can check the validity of his $m_2$ by hashing it and checking against Alice's commitment.

Nothing is learned about $m$ unless the symmetric cipher itself leaks information.


Solitaire by Bruce schneier is probably your best bet.  It has a few issues but it will work well for most things.  It ends up having a small bias, but it takes about 15 seconds per character after the initial key stream has been generated.

It is not nearly as widely studied a field as most people are assumed to be able to get a computer or other computation device.  The only other one I can think of is VIC.  It is based on a lagged Fibonacci generator which is a bit of a different place to start from. See this other answer for more details on that cipher.

I'd strongly suggest looking long and hard at Solitaire. It has really a cool design.


Calculation of failure probability in basic Ring-LWE-DH key agreement

One concrete solution is to explicitly compute the distribution of each coefficients. In this particular ring, and if the distribution of the coefficients of e and s are symmetric, this ca just be computed as an 2n-fold convolution of the distribution of products of coefficients. An example (with some complication due to rounding) is available here:

https://github.com/pq-crystals/security-estimates/blob/master/Kyber_failure.py

More mathematical approaches (which may give somewhat looser bound) involve studying moment-generating function. This can be nicely abstracted away using the theory of sub-gaussian random variables.


Straightforward method for hampering frequency analysis on deterministic encryption

Such a scheme would have two effects against an attacker trying to analyze the frequency of words and word combinations:

They would need more samples to differentiate between two tokens at the same level of confidence.
For two different tokens with similar frequency they would no longer know that the words differ.

The first means you are making the problem like that of breaking a smaller data set. Larger collections of ciphertext are still breakable. You could correct for this by making the number of different IVs depend on the total plaintext size to be encrypted, but then you make searches even slower.

The second may even be more of a problem for an attacker. The less likely options can occur at almost the same frequency – e.g. in letters there is a significant difference between the frequency of 'e' and 't', but 'j' and 'x' are almost equally uncommon. That means even if you can deduce one token from context, you've only solved e.g. one twentieth part of the problem.

Are these insurmountable problems? No. The fix may patch some leaks, but the encryption remains much less secure than non-deterministic, semantically secure encryption.

Trying to extend your tweak, it might be better to use a non-uniform distribution for the different IVs. For example, illustrating only two IVs with letters, if the probability was $\frac{1}{3}$ for one and $\frac{2}{3}$ for the other, the frequency of 'e' with the first IV would become about equal to that of 'n' with the other.

Again, I emphasize that you should only encrypt information like this if you are OK with an attacker learning nontrivial facts about the plaintext.


How does Diffie-Hellman apply to strings?

No, DH does not apply to strings. However, what you are likely trying to achieve is to perform Diffie-Hellman with authentication. For that you can use a PAKE protocol, which stands for Password Authenticated Key Exchange (Wikipedia obviously made a bit of a mess of the naming, Password-Authenticated Key Agreement would be PAKA, not PAKE).

In such protocols DH is performed and the password authentication is part of the protocol; if the password is not correct then either the protocol exits early or the shared secret is not computed to the correct value, which means that subsequent authentication will fail.


How can one break a monoalphbetic substitution chipher at pseudorandom text?

One problem with a mono-alphabetic substitution cipher is that an attacker would gain a lot of information if (s)he gets just one plain-cipher pair. Given few plain-cipher pairs, the attacker can probably break your full cipher.

You wrote that (at least part of) the encrypted data is a surrogate key. These keys should have all the same format (like 32-bit or 64-bit number) and should be better encrypted with a block-cipher for the required block size (see also the 2nd link in Paŭlo 3rd comment to your question).

If you have also data of different size (which seems to be the case), you should consider taking a family of block ciphers such that you have a (different) block cipher for each byte-length and encrypt the data with the block cipher according to its bytelength.


Why is a public key insufficient to decrypt a message?

But couldn't a third party ... reverse those steps?

Simply said - no, it is impossible to reverse those steps. (this is true under certain conditions, how the keys are generated, etc.)

Why not? One of reasons is that RSA uses modular arithmetic. All operations are done using some modulo. If you know that $X mod A = B$, can you find the X? There are unlimited solutions: X = B, X = A + B, X = 2A + B, X = 3A + B, etc. In the reality it is more complex, like $X^{C} mod A = B$. We can say that such operation is not (easily) reversible.

For further reading see the link suggested by @kelalaka. When you have then further questions, welcome.


Generate random number which should depend on key

Any Pseudo Random Number Generator using a Linear Congruential Generator, and no cryptography, is going to be unsafe, or at the very least unsatisfactory, per the criteria in our FAQ. Likely, a skilled adversary would be able to predict future output from some amount of past output with moderate work; at best, that won't happen, but there will be no sound argument that it is not possible. There are many more or less difficult to read papers making that point. A recent question, another there, further illustrate this. If the more secure requirement is to be taken any seriously, it is best to forget the LCG entirely, and use cryptography.

There should be three steps in a secure "Random Number Generator depending on a key" producing an output sequence uniformly distributed on the integers in $[1…100]$:

Stretching of the initial key. The purpose is to make brute force search of the key infeasible, or at least costly. That is superfluous if the key is already both wide enough (say 120 bit or more; 256 is aplenty) and chosen uniformly at random; in almost any other case, including when a human is expected to remember (or worse choose) the key, a deliberately slow transformation of that input is highly recommended. In many cases (notably: the combination of multiple users and use of password), the initial key should be salted while stretched. The standard building block for these functions is a Password-Based Key Derivation Function. A common one is PBKDF2; Bcrypt is much safer; the current state of the art is Scrypt.
A Cryptographically Secure Pseudo Random Number Generator, or equivalently the Keystream Generator of a secure Stream Cipher. We'll feed it the (possibly stretched) key (in the input named seed or key), and then it will output on demand practically any number of random-looking bits that we may want. The design of that cryptographic primitive strives to make that output computationally indistinguishable from random by an adversary not knowing the seed. There are a plethora of CSPRNG and Stream Ciphers to choose among, and the best choice depends on context. If it must be fast on any modern CPU, Salsa20 comes to mind.
Post-conditioning to obtain outputs uniformly distributed on the desired output interval $[u…v]$, here $[1…100]$. One simple suitable technique (slightly wasteful, but that does not matter since the CSPRNG is likely fast) is to:

Find the lowest integer $w$ such that $2^w\ge v-u+1$; here that is $w=7$, since $128\ge100$.
Obtain $w$ bits using the CSPRNG, forming an integer $r$ in range $[0…2^w-1]$, until $r<v-u+1$ (otherwise, discard $r$ and repeat this step).
Output $u+r$, and proceed to the previous step as needed to obtain more output.

If being simple and based on a LCG is important, and being secure is pointless as long as the output is good enough to pass some simple statistical test, the following procedure builds a LCG and post-condition its output (I assume the range $[u…v]$ has width no more than about $2^{16}$).

Choose $m=2^{64}$ (or a convenient higher power of $2$), $a=3141592621$, $c=1$ (this conforms to more detailed advice in TAOCP Volume 2, section 3.6; except that I kept $a$ unchanged, rather than taking the risk to scale it with $m$); the C or C++ type unsigned long long, if available, is suitable for implicit reduction modulo some appropriate implementation-dependent $m$.
Find $w$ from the interval $[u…v]$ as above (here $w=7$ for $[1…100]$).
Set $X$ to the key truncated to the bit width of $m$ (Repeat: security is out of scope! But still, it does not harm to feed other key bits in $c$, as long as it is forced to be odd).
Set $X$ to $a⋅X+c\bmod m$; in C that's X = a*X+c;.
Form $r$ in range $[0…2^w-1]$ from the $w$ high bits of $X$; in C that's r = X>>(W-w); where W is the bit width of the unsigned integer type chosen for X, and $m=2^{\mathtt W}$.
If $r\ge v-u+1$, proceed to step 4.
Output $u+r$, and proceed to step 4 as needed to obtain more output.


Probably it's possible because they are using a deterministic pseudorandom random number generator (PRNG) to generate these values, as a deterministic function of some seed, which is remembered by the holder of the private key.


Is this an error in the Pinocchio Protocol paper

The first part of the question is answered in the comments. Regarding the second part, yes, indeed, you are right! It's a typo in the Pinocchio paper, Section 2.3. Protocol 1., you also linked. The problem is that the left hand side of the verification equation enumaretes the I/O related coefficients twice in the left wire polynomial, V, therefore $g^{v_0}.g^{v_{io}}.g^{v_{mid}(s)}$ should be instead of $g^{v_0}.g^{v_{io}}.g^{v(s)}$ in the first argument of the first pairing.

However, in the original version of the protocol, see the end of Section 3.1., this typo error is not present.


What is meant by $\tilde\Omega(\lambda^4)$?

As you probably know $f(\lambda)=O(\lambda^4)$ means that $|f|$ asymptotically upper bounded by some constant times $\lambda^4$. The notation $f(\lambda)=\Omega(\lambda^4)$ corresponds to an asymptotic lower-bound.

Now, the $\tilde O$ and $\tilde \Omega$ are closely related notations, where we not only ignore constants but also values which are polynomial in the logarithm of the argument.

So in your quotation, $\tilde\Omega(\lambda^4)$ refers to a function $f(\lambda)$ which is asymptotically lower bounded by something of the form $K \log(\lambda)^c \lambda^4$, where $K$ and $c$ are some non-specified constants. [I am ignoring the absolute value of $f$ from the definition, since it clear in your context that $f$ takes positive values.]


This question has nothing to do with AES; instead, it has to do with an encoding that someone picked for this example (and the fact that you have questions about it indicates that it wasn't a great choice by whoever came up with the example).

The encoding is simple; we translate the letters 'A' through 'Z' to the integers 0 to 25, which is in hexidecimal the values 00 through 1A.

M is the 12th letter after A, and hence it is translated into the integer 12, which is 0C in hex.


What does it mean for an adversary to run in PPT?

An algorithm being probabilistic means that it is allowed to "throw coins", and use the results of the coin throws in its computations. This is reasonable because a realistic adversary has access to certain pseudo-randomness sources (such as the C rand() function). Of course, a probabilistic algorithm is not required to use its randomness source (i.e., throw coins), but even if it were, it could just ignore the results.


Decisional Diffie-Hellman assumption vs decisional bilinear Diffie-Hellman assumption

I don't know if it can helps. But actually, you can win the DDH game if you are using pairings.

Suppose you are given $X = g^x$ and $Y = g^y$, you can apply $e(X,Y) = e(g,g)^{xy}$.

Given $Z$, your goal is to know if $(X,Y,Z)$ is a DDH triplet.

You can test, using useful properties of pairings, if $e(g,Z) = e(X,Y)$ and so you can distinguish from a random element.

So I think that's why we consider 3 numbers to distinguish.

You can also think about Key-exchange Diffie-Hellman and Joux "Tripartie DH" as described in this PDF.


Protocol to generate Client Certificates at the start of a SSL session automatically?

I suspect that you may wish to read the current Internet draft on TLS Origin-Bound Certificates and note the organisation of the authors at the bottom.


Can i XOR an array of bytes with an equal length key securely

If i have say 64 bytes, can i XOR those bytes with another 64 random bytes, and have two new arrays, where both are needed to reconstruct the first?

This is known as XOR secret sharing or in the case of two splits also known as a the (binary) One-Time-Pad.

Indeed if for every execution of the split-up operation a new independent random string is used then always both (/all) shared parts are needed for reconstruction. Any less number of shares / parts leaks no information about the shared message except for the length and what was already known anyways.

Note though that this provides no protection against tampering, i.e. if somebody flips a bit in either share and the other(s) doesn't then the reconstructed message will have the bit flip without a strong cryptographic guarantee of this being noticed.

Also note that security breaks down horribly if the same randomness is used with two different messages. Of course if you re-use randomness for the same message then an adversary can notice that.


How can I validate generated session keys in SRP-6a protocol

Nimbus or Thinbus are two popular SRP implementations in Java and Javascript compute the proof of password as you describe H(A|B|S) where you can supply your own hash functions such as SHA1 or SHA256 or stronger.

The actual protocol design document states H(H(N) xor H(g), H(I), s, A, B, K) where K=H(S) so that expands to H(H(N) xor H(g)|H(I)|s|A|B|H(S)). The longer approach includes N, g, s which is the safe prime, it's generator and I the user identity and s the users salt. Those are not secret. The secret is S and adding more bits into the hash is done to protect leaking information about that secret. The secret is also the only component which is derived from the password if you are talking to an attacking server so needs to be well hashed. So both approaches involve A which is the secure random chosen by the client to conceal the secret.

In the protocol design document the server then responds with H(A|p|K) which expands to H(A|p|H(S)). The p is the value used to check the client holds the password which has already computed to check the client.

Once again all the proofs, including the server proof, include A which is the random chosen by the client. If that is a secure random it provides protection against a fake server attacker which may be supplying a not random B and a bad salt as part of an attack.

So why would Nimbus and Thinbus go with H(A|B|S) rather than the more complex password proof using more bits from the public values? (Nimbus will actually let you plugin your own proof function but that is the default). The original SRP RFC was using SHA1 which is now considered weak one can see why it might throw more bytes into the hash and also double hash the S to better protect it. With Nimbus and Thinbus the recommended hash function is SHA256 or higher. So the random numbers used to generate A and B will be that many bits. The choice of a more secure hash algorithm and larger random numbers is considered enough to protect from leaking information about S which may leak information about the password.


How to get the keyword from a keyword cipher?

Let's start by considering which cipher letters should correspond to the most common letters E and T.  According to your frequency analysis, the most likely candidates are O, K, T and maybe D and N.

Now, E is the fifth letter of the alphabet, so unless your keyword is very short, it's going to encrypt to some letter in the keyword (and if the keyword is very short, E would likely encrypt to A or B, which doesn't seem likely in this case).  So let's ignore E for now.

However, T is the twentieth letter in the alphabet, so unless your keyword has twenty or more (unique!) letters, T will encrypt to one of the "left-over" letters.  Thus, the encryption of T will tell you how many letters in the range T to Z the keyword contains.

So let's consider the possibilities.  We can rule out T encrypting to K entirely — that would require the keyword to contain nine letters in the range T to Z, but there are only seven letters in that range!  The same goes for D, and N, while barely possible, doesn't seem plausible either.  Even O, at four positions before T in the alphabet, seems rather unlikely, given that most of the letters after T in the alphabet are fairly uncommon. So my guess would be that T — and thus also every letter after it in the alphabet — encrypts to itself.  Looking at your letter frequencies, that seems plausible.

That leaves O and K as plausible encryptions for E; the other one of those then probably stands for A, which would mean that both of them occur in the keyword (and, in particular, that one of them is the first letter in the keyword).  Alternatively, K might stand for O, and D or N for A.

What about P, Q, R and S, then?  Well, there's no way Q encrypts to itself — the frequency of Q in English pretty much never exceeds that of U.  However, Q (nominal freq. 0.095) might well encrypt to P (ciphertext freq. 0.161); it certainly doesn't encrypt to Z, F or X, which are the only less frequent letters in the ciphertext than P.  That means that one of Q, R and S must occur in the key; the ciphertext frequency of S (3.617) is far enough from its nominal frequency (6.327) that we might guess that it's in the key, which would give us the following partial cipher table:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
????????????????PQRTUVWXYZ    key letters: S, (O/K)

We might also guess that P (nominal freq. 1.929) encrypts to M (ciphertext freq. 1.688) – it certainly can't encrypt to N (freq. 8.039) or O (freq. 10.772), unless your message is about peppy popping pepper pips or something.  Could O (n.f. 7.507) then encrypt to L (c.f. 3.617)?  Maybe, but K (c.f. 10.611) seems more likely.

That would  mean that E encrypts to O and that L and N also occur in the key.  Which plaintext letters could they stand for?  Well, looking at the frequency table, N might stand for A and L for C or D.  That gives us the following partial cipher table:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
N???O?????????KMPQRTUVWXYZ    key letters: L, S

Presumably, L and S stand for C and D in either order, but it's hard to tell from the frequencies which.  What letter could stand for B, then?  Well, E looks like a plausible choice — the frequencies are pretty close, and E is common enough to be likely to appear in the keyword.  Guessing that L might stand for C, that makes the cipher table look like this:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
NELSO?????????KMPQRTUVWXYZ

Could the keyword be NELSO(N)?  If so, A would stand for F, B for G and so on:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
NELSOABCDFGHIJKMPQRTUVWXYZ

Looking at the frequencies, I see no obvious mismatches, so I'm going to guess that that's the solution.  Of course, examining the actual ciphertext could either confirm or refute this, but based on the frequencies alone it looks plausible.


One time pads are used in many low bandwidth situations.  However, they suffer from a fundamental problem of key distribution.  It's hard to transmit 1GB of key information.

One time pads are most effective in situations where the trust communication channels are highly asymmetric.  If you can hand deliver your OTP to an individual, positively confirm their identity, and then hand the pad over, then OTP can be quite effective.  In times of war, where you can be physically provided your key material before you travel into the hostile area, this pattern can be very powerful.  In more symmetric situations, transferring the key material securely can be just as difficult as transmitting the material itself!  These symmetric situations are more common on the internet.


Does mixing two derived keys make a stronger key? And if so, how would I mix?

This answer is part answer, part comment requesting refinement of the language in the question.

There is an assumption in the question that is not necessarily valid.

  Using just a single KDF seems out of question to me if you really need secure and hard to attack keys

There is a counter example to the intuition that using more functions will make it more difficult: Suppose you are allotted 1 second of time per evaluation of the key derivation function. If you use scrypt for .5 seconds and then bcrypt for the next .5 seconds (or vice versa), your key derivation function uses less memory then just using scrypt for the entire 1 second. So if memory hardness was the goal, then mixing two functions does not necessarily improve security. Which leads to the next point:

  So if I use two derivation functions, one that is known to be secure but a bit weak and one that is very strong but not (yet) known to be secure, wouldn't this lead to better keys than just relying on one method?

First, there is a contradiction: What exactly is a method that is known to be secure, but is weak? How can we know it's strong if we do not know it is secure? If "strength" is somehow separate from "security", your definitions for the two terms would be appreciated.

Secondly, you have to define "better" keys: better in regards to what?

  How would I mix the two keys? What would be a good, secure method for that

You have to define "secure": Combining hash functions is not trivial.

If you can assume that at least one of the outputs is psuedorandom, then there is little reason not to use the simplest method possible, namely, XOR. The output of $x \oplus y$ is at least as random as the more random of the two (otherwise a OTP would not work).

Unless for some reason, you want order to matter, then you could use a non-commutative operation such as concatenation and hashing. Unless you have an explicit reason for needing the properties of some other mixer, it is probably best to use the simplest tool for the job.


To answer your specific questions:

  From reading around I understand that ... encrypting a counter and use that as the IV is OK,
     is that true?

For CBC mode, that is absolutely true, as long as the key that you use to encrypt the counter is secret (that is, not known to any possible adversary).

  Should I start in random number?

Actually, that's a matter of taste; you could start with 0 if you wished.

If you use a known counter, the attacker would learn the encryption of (for example)  [0], [1], [2], etc.  This isn't much of a problem with CBC mode; whenever you encrypt known plaintext, the attacker gets several more known plaintext/ciphertext pairs.  This helps the attacker only if in the future, the CBC mode happens to use the exact same plaintext (to generate the exact same ciphertext), with AES, you have $2^{128}$ possible plaintext/ciphertext pairs; accidentally reusing one is improbable (and so adding a few more because you encrypt a few known counters isn't going to be harmful.

Now, if it's convenient to start at a random number, well, that doesn't hurt anything.  However, I wouldn't do it unless it was easy.

  After how many uses should I use a new random IV?

There's no requirement to ever reseed your counter.  You'd run into problems if you encrypt more than $2^{64}$ messages or so; however CBC mode will already run into problems in that case (and you wouldn't be able to encrypt that many messages in a reasonable amount of time anyways).

  Can I use the same key for generating the IV and encrypting the message?

Not only can you, you're better off if you use the same key.  Remember where I said the key you encrypt the counter should be "not known to any possible adversary"?  Well, we already have such a key; the key you use to encrypt the message.  After all, if an adversary does have that key, he can read the message already; any weakness stemming from the IV being predictable is irrelevant.  Hence, by using the same key to do both, we reduce the number of secrets we need to keep from an adversary.

One small caveat: if you reuse the key in this way, the attacker shouldn't be allowed to choose or control the counter.  It would be fine to use a counter that starts at 0, or a counter with a random starting point (where the starting point is generated using RandomNumberGenerator) as you suggested.


How did this group discover m wasn't random?

Per the notation of the wiki article, all signatures produced with the same random k would lead to the same value r which is published as part of the signature.


Why Distance-128 relation in Plain texts is reflected in Cipher texts

The short answer to your question is because RC4 is a stream cipher.

Try comparing the xors of the two plaintexts and the two ciphertexts... Better still, replace the second ciphertext with \x00...\x00 and then look what happens.

A stream cipher works by taking a secret input (the key) and turning it into a long stream of pseudo-random data (the stream). This output stream is the xor'd with the plaintext to produce the ciphertext. To decrypt, we again generate the stream, but this time by xoring it with the ciphertext we retrieve the plaintext.

One of the biggest issues with using xor is that bit's flipped in the plaintext translate into bit's flipped in it's ciphertext.