Prefix property for variable length pseudo-random generators

Recall that Katz-Lindell defines a variable output-length pseudorandom generator as a deterministic polynomial time algorithm G with three properties:

Let $s$ a string and $n>0$ an integer. Then $G(s,1^n)$ outputs a string of length $n$
For all $s,n,n'$ with $n<n'$, the string $G(s,1^n)$ is a prefix of $G(s,1^{n'})$
Define $G_{\ell}:=G(s,1^{\ell(|s|)})$. Then for every polynomial $\ell(\cdot)$ it holds that $G_{\ell}$ is a pseudorandom generator with expansion factor $\ell$.

(I have changed some $\ell$s to $n$s to avoid variable collision).

The second condition is necessary because, without it, this definition does not say anything about the output of $G(s,1^n)$ in the case where $|s|>n$. This is because Katz-Lindell defines a pseudorandom generator (on page 70) to have an $\textit{expansion}$ property-- the output of a pseudorandom generator is longer than the seed--so the above property 3 doesn't (by itself) tell us anything about the case where $|s|>n$.

This is a problem because (as defined on page 63) the first step of the eavesdropping indistinguishability experiment is that "The adversary $\mathcal{A}$ is given input $1^n$, and outputs a pair of messages $m_0,m_1$ of the same length."

The seed used in encryption is of length $n$, so the adversary could choose messages of length less than $n$. Then the messages would be encrypted with the output of $G(k,1^{|m_0|})$ which, as mentioned above, is not guaranteed to be pseudorandom without property 2.

However, it is an easy lemma to prove that a truncation of a pseudorandom string is also pseudorandom. This, together with properties 2 and 3, gives us that all outputs of a variable output-length pseudorandom generator are pseudorandom, and the security proof goes through as normal.


Design of MixColumn Transformation in AES

Because:

These numbers in the matrix form a Maximum Distance Separable matrix; that is, one where, if you change some bytes of the input, then the total number of bytes of input changed PLUS the total number of bytes of output changed will always be at least 5 (e.g. if you change 2 bytes of input, then you'll always change at least 3 bytes of the output).  This property is crucial for the security proof against differential and linear cryptanalysis.
These numbers make the encryption direction cheap; to compute the transform of the column $(A, B, C, D)$, you compute $2 \times A, 2 \times B, 2 \times C, 2 \times D)$, and then do a bunch of byte-wise xor's.
These numbers make the decryption direction moderately cheap, to compute the inverse transform of the column $(A, B, C, D)$, you compute $2 \times A, 4 \times A, 8 \times A, 2 \times B,$ $4 \times B, ..., 8 \times D$ (doable with 12 doublings), and then do a bunch of byte-wise xor's.


During CBC mode decryption, each ciphertext block is first decrypted with the block cipher, and then the first decrypted block is XORed with the IV, while later blocks are XORed with the previous ciphertext block:

Thus, the first block of plaintext is computed as: $$P_1 = IV \oplus D_K(C_1).$$

Equivalently, we may solve this equation for $IV$ to obtain: $$IV = P_1 \oplus D_K(C_1).$$

This means that, for any ciphertext and key, it's always possible to choose the IV so that the first block will decrypt to any plaintext we want.

This also implies that CBC mode is trivially malleable: an attacker who can modify the encrypted message can flip arbitrary bits in the first block of the plaintext simply by flipping the corresponding bits of the IV.  In particular, if the attacker can guess the original first block of plaintext, they can rewrite it to say whatever they want without knowing the key.  (A similar attack is possible for later blocks, but it tends to randomly scramble the previous block of plaintext.)

Such malleability is a general feature of CBC and all other non-authenticating cipher modes.  To protect against it, it is necessary to verify the integrity of the ciphertext using a MAC, or to use a combined authenticated encryption mode.


What are the current limitations (and capabilities) of Functional Encryption used for access control?

In functional encryption, the function don't apply on access policy. In FE the receiver obtain the function of message. Attribute Based Encryption for arithmetic circuits may help you. Fully key hommomorphic encryption for ABE for arithmetic circuits from Boneh et. al presented to this problem. Although the FE is the general of ABE.


Here's the issue; the size of the multiplicative group is $p-1$; if $p>2$, then $p-1$ is even.

What this means is that we can divide the group into two equal sized halves, the "even" elements (which happen to be the values $x$ which have a solution to the equation $y^2 \equiv x \bmod p$, known as quadratic residues), and the "odd" elements (which happen to be the values for which the equation has no such solution, known as quadratic nonresidues).  Computing the Legendre symbol is an efficient way of determining which half a particular element falls into.

Here's why this is important: $g^{ab}$ will be a quadratic nonresidue if (and only if) both $g^a$ and $g^b$ are quadratic nonresidues.  Hence, given $g^a$, $g^b$ and a group element $h$, an attacker can determine the Legendre symbol on all three values, and see which half $g^{ab}$ would be expected to fall in; if it falls in one half, and $h$ is in the other, the attacker knows that $h \ne g^{ab}$ (and for a random group element $h$, this is expected to happen half the time).

We typically get around this by redefining the group; we limit ourselves to the subgroup of quadratic residues (and so $h$ isn't allowed to be a random group element, they're allowed only to be in the "even" half); hence this trick doesn't work.  This does mean that $g$ cannot generate the entire group (as we cannot allow it to generate the "odd" elements), however we can find an element that generates the entire "even" subgroup (in fact, if we select $p$ to be a safe prime, that is, $(p-1)/2$ is also prime, then any element in the even subgroup, other than 1, will generate the entire even subgroup).


After reading the comments on your original post, I thought I'd give you an example for exponentiating by $e$. Take for example the case $e=2^{16}+1$. Then, to calculate $x^e$ we use $16$ squaring operations and one multiply. This is because
$$x^{2^{16}+1}=x \cdot x^{2^{16}} = x\cdot x^{\underbrace{2\cdot 2 \cdots 2}} =x\cdot ((x^2)^2)\cdots)^ 2$$
(where the brace contains sixteen $2$'s).

So, we use repeated squaring to calculate $x^{2^{16}}$, then having done so can simply multiply by $x$ once to find $x^e$.

If we think about the binary expansion of $e$, this techinque can be generalised to give [relatively] efficient exponentiation to any power. For example, how to we take an element to the power $e=41$? Well, first writing $e$ in terms of powers of two (ie in binary), we see that $e=32+8+1=2^5+2^3+2^0$ and thus $e=101001$. So, to evaluate this we simply initialise our answer as $1$ and set $y=x$ ($y$ will store $x^{2^i}$ as $i$ increases), then work from right to left along the binary expansion of $e$. If the digit is $1$, then we multiply by $y$. Then, we square $y$ and move on to the next digit.

The reason $e$ is chosen to be a value like $2^{16}+1$ or $3=2^1+1$ are that they each only require one multiplication. Looking back at my rather poor explanation above, we see that we have to square $x$ for each 'place' in the binary expansion of $e$, and we have to multiply our running value once for each $1$ in the binary expansion of $e$. So, if $e$ is $n$ bits long (ie $n=\lfloor\log_2(e)\rfloor+1$) we require $n-1$ squaring oparations and at most $n$ multiplications (or $n-1$ if we start our multiplication with the first value power of $x$ encountered rather than initialising with $1$ as in my example).

As mentioned by other comments, it is hard to know how many multiplications/squarings will be required to decrypt, since to do so requires knowing the binary expansion of $d$. That said, we can be pretty confident that $d$ is very unlikely to have anywhere near as nicer expansion as $e$ did with these choices, suggesting decrypting will require rather more work than encryption.


To generate an IV securely for CBC mode, there are two obvious ways to do it (and both are cited by NIST):

For each packet, select a nonce (the IPSec sequence number, padded out to 64 bits, works fine), encrypt that in ECB mode, and then use resulting ciphertext block as the IV.  An equivalent way to do that is to take your 64 bit nonce, prepend that to the  byte plaintext, encrypt the plaintext (and the 64 bit nonce) with a fixed IV, and then transmit the first 64 bits of the ciphertext (not including the fixed IV you used) as the IV, and the rest of the ciphertext as the ciphertext body.  It turns out this is equivalent to the first method because of how CBC mode works internally.
For call a random number generator to select a 64 bit IV, and use that.  The text from NIST you cite says the rng has to be FIPS-approved; actually, unless you care about FIPS compliance, any unpredictable rng should work; I don't expect any problems /dev/random

Personally, I suspect you'll find the first option is easier.

The other thing you ought to consider is integrity; there's a surprising amount of mischief someone can cause by modifying the ciphertext, and then having someone attempt to decrypt it.  Now, IPSec has an answer to that (including a MAC along with the ciphertext; if someone modifies the ciphertext, the MAC will fail); are you including that?

BTW: the RFC you cite (RFC1851) is rather out-of-date, and won't interoperate with modern versions of IPSec; at the very least, modern versions will expect the padding to have a specific pattern.  That doesn't matter if you're implementing both sides of the protocol; however if the other side is a non-ancient IPSec implementation, look at RFC2406 and RFC2451


DES key expansion: why are these two descriptions different?

I'm not going to look up the DES key schedule such, but the connection between your two sequences

$$( a_i ) = ( 1, 2, 4, 6, 8, 10, 12, 14, 15, 17, 19, 21, 23, 25, 27, 28 )$$

and

$$( b_i ) = ( 1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1 )$$

is obvious: $b_i = a_i - a_{i - 1}$ (with $a_0$ taken to be 0).

That is, the second sequence gives the difference between successive elements of the first sequence.

Edit: OK, I did look it up, see link above.  Basically, the first sequence gives the number of bits by which the halves of the original key need to be rotated to obtain the $i$-th subkey, whereas the second sequence gives the number of bits by which the halves of the previous subkey need to be rotated to obtain the next one.  That's all there is to it.


How to forge signatures in the Schnorr scheme if $r=g^k$ is eliminated?

I suppose that you address the question to a signature scheme, in which the signature is  still the pair $(r,s)$ with $r=g^k \bmod p$ as the exponentiated nonce and
$$s = H(m)\cdot x + k \mod q,$$
where $h = H(m)$ depends solely on the message $m$ being signed.
Here $x$ denotes the secret signing key and $q$ the order of the generator $g$ of a prime subgroup of $\mathbb Z_p^*$.
Creating a valid pair $(r,s)$ for an arbitrary message is done follows:

choose any value for $s$,
determine $r$ directly by the verification equation $$g^s = y^h \cdot r \mod p,$$ where $y=g^x$ is the public verification key, and not via its logarithm $k$. This yields $r = g^s\cdot y^{-h}\bmod p$.

This attack is the same as for Schnorr's identification protocol once one knows the verifier's challenge in advance, and shows (at least to me) how careful one has to be with cryptographic protocols: naivly, one is led to think it is impossible to forge a signature without knowing the components of the linear functional, i.e. the coefficients $x$ and $k$.


Is it necessary to have a certificate when we use TLS

If the TLS communication is properly secured then a middle attack is not practically possible. Properly secured includes authentication of the server in order to make sure that one is talking  to (and exchanging the keys with) the expected server and not to some man in the middle attacker. There are various ways to authenticate the server, like certificates or pre-shared keys (PSK). Certificates within a public key infrastructure are the most used method though since they scale best with large setups (like the internet).


Why has SSL v3 not yet been upgraded to a higher version with stronger principles, what are the dependencies and issues to do so?

TLS 1.0 is in effect SSL 3.1. If you need more details about the history and why it is called TLS 1.0 instead of SSL 3.1 read Wikipedia.


What is Quantum Cryptography?

Today's "normal" cryptography relies mostly on mathematical principles. For example RSA is based on the practical difficulty of the factorization of the product of two large prime numbers, the so-called "factoring problem".

Quantum cryptography (quote from Wikipedia):

  Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks.

So instead of relying only on mathematical principles, quantum cryptography relies more on quantum mechanical properties (physics). Some of these properties include:

The uncertainty principle
Quantum superposision
Quantum entanglement

  How secure are data that encrypted with Quantum Cryptography methods?

Quantum cryptographic tasks (often incorrectly called quantum cryptography) are theoretically 100% secure, even against quantum-computers.

The method described in your question is Quantum key distribution (QKD). QKD has provable security based on information theory, and forward secrecy. This is based on the No-cloning theorem, which states that it is impossible to create an identical copy of an arbitrary unknown quantum state.

  If Quantum Computing becomes practical and is mass-produced, will we be facing with next-generation of cybersecurity?

Not necessarily. I personally think that quantum computers won't fully replace classical computers, because quantum computers only outperform classical computers in certain areas (i.e. large-scale simulations).

But if quantum computers were available they would break some of today's cryptography used on classical computers, i.e. RSA or Diffie-Hellman. We would then have to switch to post-quantum cryptographic algorithms like Supersingular isogeny key exchange. So ultimately, I think, we would just switch to quantum-resistant algrorithms and go on with our lives.

EDIT: This answer provides some additional information.


What is the difference between signatures and VRF?

First, you need more than just a signature, because a VRF produces both an output and a proof.  To an observer, the output is uniformly distributed unless the observer also has the proof, which can be used to verify the output.

With a signature scheme and a random oracle $H$, you could use a signature $s$ on a message $m$ as a proof and $h = H(s)$ as an output: then the output $h$ is uniformly distributed if you don't know the proof, but knowing the proof $s$ you can (a) verify that $s$ is a signature on $m$, and (b) verify that $h = H(s)$.

However, that's not enough, because signature schemes do not usually guarantee uniqueness of the signature.  ECDSA signatures are malleable: if $(x(R), s)$ is an ECDSA signature, then so is $(x(-R), -s) = (x(R), -s)$.  EdDSA signatures, of the form $(R, s)$ instead, hash $R$ together with the message so it can't be changed any more than the message can, but $(R, s + \ell)$ makes another valid signature if encodable, where $\ell$ is the order of the standard base point.

Further, ECDSA and EdDSA are built out of a non-interactive zero-knowledge proof protocol that is necessarily randomized, and the signer can choose any per-signature secret randomization they want without the verifier noticing.  Standard EdDSA prescribes a particular deterministic pseudorandomization so that the signer doesn't accidentally leak the private key when signing two different messages even if they don't have a source of entropy at signing time, but verifiers can't tell if a signer uses a nonstandard randomization.  Similarly, the widely deployed RSASSA-PSS signature scheme is randomized, so it doesn't provide uniqueness either.

That said, we can still use the RSA primitive to make a VRF if we pick a deterministic RSA signature scheme such as RSA-FDH with a fixed full-domain hash.  This is what the IETF Internet-Draft draft-goldbe-vrf, currently under discussion at the CFRG, does for RSA-FDH-VRF.

We can also adapt elliptic curve signatures such as EdDSA to make a VRF, with a little more work.  I won't go into the details, but draft-goldbe-vrf has one construction called EC-VRF, and Open Whisper Systems (creators of Signal) developed another called VXEdDSA.

Further reading:

VRFs were first introduced to the literature in Silvio Micali, Michael Rabin, and Salil Vadhan, ‘Verifiable Random Functions’, Proceedings of the IEEE 54th Annual Symposium on Foundations of Computer Science, 1999.
VRFs were recently presented to the IETF for standardization, by Sharon Goldberg, Dimitrios Papadopoulos, and Jan Včelák, ‘draft-goldbe-vrf-01: Verifiable Random Functions (VRF)’, Presentation at CFRG@IETF'99, Prague, July 2017.
Sharon Goldberg's group at Boston University has an ongoing practical VRF project with some references.
Some details of the constructions, and an application to DNSSEC for verifiable negative responses thwarting zone enumeration, are analyzed in Dimitrios Papadopoulos, Duane Wessels, Shumon Huque, Moni Naor, Jan Včelák, Leonid Rezyin, and Sharon Goldberg, ‘Making NSEC5 Practical for DNSSEC’, IACR Cryptology ePrint Archive: Report 2017/099.
A dialogue in five parts summarizing a use case of VRFs for DNSSEC to authenticate negative answers without enabling zone enumeration or risking forgery in the face of online nameserver compromise.

P.S.  Fun fact: RSA signatures aren't uniformly distributed even if you don't know the public key.  Since every signature will involve an integer below the modulus $n$, with enough signatures one can solve the German tank problem to deanonymize signers in practice.  Of course, you could do rejection sampling to force them below $2^{\lfloor\lg n\rfloor}$.


Significance of 3mod4 in squares and square roots mod n?

If $p \equiv 3 \pmod{4}$ then $p + 1$ is divisible by 4. If we want to take the square root of $a$ mod $p$ then:

$$\left ( \pm a^{\frac{p + 1}{4}} \right)^2 \equiv a^{\frac{p + 1}{2}} \equiv a^{\frac{p - 1 + 2}{2}} \equiv a^{\frac{p - 1}{2} + 1} \equiv a^{\frac{p - 1}{2}} \cdot a \pmod{p}$$

But since $a$ was chosen to be a quadratic residue (otherwise it has no square roots) it follows that:
$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$
And hence the two square roots of $a$ modulo $p$ can in this case be very easily computed as:
$$\pm a^{\frac{p + 1}{4}}$$
Unlike the case for $p \equiv 1 \pmod{4}$ which requires more work to find the square roots of $a$ mod $p$. It is still possible, of course, just a bit more involved (e.g. see the Tonelli-Shanks algorithm).

So that could be one possibility. Another possibility is to observe that $p \equiv 3 \pmod{4}$ simply means that $p - 1$ is only divided once by 2, which might be a requirement or a desirable attribute in many contexts.


A hash functin based on XOR and matrix multiplication

First note that the following holds:

$$h(a)=K\cdot a+K'\cdot \bar a=K\cdot a+K'\cdot(a+1^n)=\underbrace{(K+K')}_M\cdot a+\underbrace{K'\cdot 1^n}_c=M\cdot a+c$$

Also note that $h(a)=M\cdot a$ is an universal hash function for $n$-bit input and $m$-bit output, as $\Pr\left[h(x)=h(y)\right]=2^{-m}$ with the randomness being over the choice of $M$. Clearly in this case $M=K+K'$ both of which are random matrices so this clearly holds. Now note that adding $c$ is essentially just a permutation over the bit values which doesn't change the collision properties, so it preserves the universality.

Also note that the first observation means that given $n+1$ chosen input-output pairs you can fully recover a description of $h$ and recover all information that you could from $Ma$ about $a$ when given $h(a)$. The strategy to the recovery would be to request $0^n$ and get $c$ this way. Then request $0^n$ with the $i$-th bit set for all $n$ values of $i$ to learn all the columns / rows of the $M$ matrix.


Hardware AES: can we have a decryption implementation only?

In practice, AES encryption mostly use CTR mode or some authenticated encryption, and in these the block cipher itself is only used for encryption. There is thus often no need to implement AES decryption in hardware.

We can always remove features from hardware circuitry. Implementing only the AES encryption sizably reduce the hardware cost (compared to also implementing decryption), but implementing only decryption saves much less (especially for cost-optimized rather than speed-optimized designs), because:

Decryption requires (as does encryption) forward-computing the round keys, and (specific to decryption) either storing them or walking backward. Therefore the relatively large saving possible for round keys computation by omitting said storage or capability to walk backward has no equivalent when omitting encryption.
The S-box used for encryption and the (inverse) one used for decryption are different, and there's sizable saving possible by omitting the decryption one. However the two are not needed simultaneously; it is feasible to share some gates between the two; and even in speed-optimized implementations where that's not done, it might still be possible to reduce to almost nothing the power consumption (and associated costs) of the inactive S-Box.
The MixColumns step for decryption is significantly more complex than the one for encryption, and it is feasible to share a lot of gates between the two, so that omitting encryption capability won't necessarily save much there.


With the current computers this would not take so much time. There is a high chance that reading / writing the files or sending the files over the network will take more time. If you've got trash like the McAfee virusscanner installed on either PC then that will take much more time as it will try and scan the files in the zip file at lower than 1 MiB/s.

Passwords are generally not very strong, while encryption using a hybrid cryptosystem such as PGP using an RSA public key is very strong. The password based encryption (PBE) is made worse as you're using SHA-256 instead of a password based key derivation function (or PBKDF). So an additional encryption would indeed not be a bad idea. In general you could do without the password encryption, but not without the PGP encryption the way you write it down. Note that the PGP encryption is also protecting the file names; it could be that the file names are sensitive too.

Even when using PGP you should check if you're not vulnerable against Bleichenbacher attacks, padding oracle attacks. This would mainly a problem if you automate the decryption when the files are received. Protection should also be in placed to disallow changes of the plaintext, for instance by signing the .zip file.

So I don't think you're over encrypting, rather the opposite. That said, performing encryption right once makes more sense than performing it badly twice.


Why equation Y^2=X^3 +AX+B can't work with finte field of charateristic 2?

In $GF(2^n)$, $y+y = 0$ for all $y$. These elements are not integers; using something like “2” to denote a field element is merely a convention, and, as you demonstrate, a confusing one. In this case, $2y$ means $y+y$, not the product in the field of $y$ with the element conventionally represented by “2”.


TLS 1.2 Cipher Suites With AES-GCM – What data (if any) is passed to the AES-GCM cipher as the Additional Authentication Data?

Actually section 6.2.3.3 of RFC 5246 talks about the associated data:

  The additional authenticated data, which we denote as
  additional_data, is defined as follows:

additional_data = seq_num + TLSCompressed.type +
                    TLSCompressed.version + TLSCompressed.length;

  where "+" denotes concatenation.

So the sequence number, the packet version, the packet type and the packet length are passed as associated data to the cipher.

So why is exactly this data authenticated?

The sequence number: Authenticating this helps prevent re-ordering and replay attacks and binds the sequence number to the data packet.
The protocol version: Authenticating this ensures that if you can't downgrade the protocol version (eg to SSLv3) to exploit weaknesses and learn something about the content of the current packet.
The packet type: I suppose this blocks you from re-using a handshake packet for an application traffic packet (which may have independent sequence number streams)
The packet length: This blocks you from silently chopping some data off somewhere, but is mostly here because it's public data and authenticating it doesn't really hurt.


Security of AES in CTR mode with fixed nonce (but different key)

Yes, if you use a different key for each message, then it's secure, and it's not a problem if you use a public (or fixed) nonce.

One example where this comes up is the Integrated Encryption Scheme, which uses a symmetric system to encrypt the actual message, and which internally generates a key that will be used only for that message.  Note that in IES, you'll also need to implement integrity protection as well (e.g. a MAC)


How to explain indistinguishability obfuscation (iO) to my grandmother?

iO removes all metadata from the program.


What is the approximate effort to break one additional round of a primitive?

Think of breaking through rounds as doing ballistics tests to see how deep a projectile can get into a defensive barrier. Breaking through the first layer or two is easy, but each subsequent layer becomes increasingly harder to penetrate. It would be impossible to ask exactly how difficult it is without knowing both the projectile and the defensive material. All you can say is that each layer makes it less and less likely that anything will get through. Breaking an iterated cipher is exactly like that, but with more math.

  Generally and with no particular primitive in mind, what is the scale of the effort to break one more round?

There is no way to answer this without knowing the particular primitive you are talking about. In some cases, for a cipher with a small number of very complex rounds, extending an attack to another round may be a truly monumental effort and the discovery may be significant. For a cipher with a huge number of simple rounds, breaking one more may be just a matter of revisiting the original attack. In general, it's easier to extend an attack one more round for ciphers with a large number of simple rounds than with a few complex ones. This is why people tend to refer to broken rounds only in the context of the number of total rounds. Finding an attack that breaks 9 rounds is a big deal for a cipher with 10 rounds, but is not a big deal at all for a cipher with 72 rounds. That's why security margin is given as a percent.

  In short, is breaking each additional round as easy or harder than the previous one?

Each round introduces more confusion and diffusion. With the exception of a few rare types of attacks which do not depend on the number of rounds (like slide attacks), following e.g. a differential trail or linear hull through more rounds may not be possible without using completely new techniques in the attack. In general, each additional round is significantly harder to break than the last.


Are all binary-additive stream ciphers reciprocal?

Since additive stream ciphers are involutions, i.e.,
$$
E_K(\cdot)=D_K(\cdot)
$$
for all possible keys $K$,
they are also reciprocal.


HMAC does it matter if I chose the cipher text or the plain text as the message?

Yes, it does matter. A MAC should always be over the ciphertext, not the plaintext.

HMAC(key, ciphertext) = Hash((DerivedKey xor OuterPad) || Hash((DerivedKey xor InnerPad) || Ciphertext))

Where || denotes concatenation.
OuterPad is a one-hash-block long hexidecimal constant 0x5C5C...5C.
InnerPad is a one-hash-block long hexidecimal constant 0x3636...36.

Of course you should use an existing implementation of HMAC instead of trying to make your own, but if your library is just concatenating values and then hashing them it's not HMAC, and you should use a different library (assuming the library actually calls it HMAC).

There are other MACs than just HMAC, such as SHA-3's KMAC or Poly1305. They also should only be applied to the ciphertext. Your library may be using one of these. I happen to like the libsodium library. It uses Poly1305 for its MAC. It also includes a design that makes it hard to misuse: it's impossible to use a symmetric cipher without properly applying a MAC, so you don't have to worry about the answer to this question. You just call the appropriate crypto_secretbox function!

The following question and answers give reasoning for Encrypt-Then-MAC being optimal: Should we MAC-then-encrypt or encrypt-then-MAC?


Is use of pre-shared key for sharing session key in symmetric key cryptography vulnerable to MITM?

An obvious, but not serious weakness, is that numbers R1 and R2 will be sent in plain text. This means that MITM is able to modify R1 or R2 so that Alice or Bob will always fail at authentication, although they have a legal key K.

I have one suggestion how you can improve this protocol. Just because in the last step of the protocol, Bob only sends encrypted S, MITM can wait while previous steps will be completed successfully, and then send some old message K(S_old), where S_old is an old session key, which was compromised. To avoid such danger, add number R2 to Bob’s last response K(S,R2).


Are well designed crypographic codes unbreakable? (NOT ciphers)

The answer is "irrelevant", because of a wrong assumption about security.

Today, ciphertext only attacks are not considered any more for real security, because it is much too weak. Known plaintext attacks are the very least to be considered, and that breaks any construction of codes or obscure languages. The reason for this is simple: Laymen might only see the ciphertext/encoded text. But specialists will find ways to get additional information to enable known plaintext or chosen plaintext attacks (for symmetric encryption. Asymmetric has a different playing field)

This is very similar to the argument "security through obscurity", as it is still practiced quite often. Sure, on the first glance it seems a good idea not to give an attacker information about your system. And then later you realize: If that is the only security mechanism, you're screwed when he finds out anyway.

Edit:

In order to avoid further discussions, the answer to

  Are there any ways to crack or even crypto-analyze secret languages only using raw text written in that secret language?

is "No". Under these assumptions (no knowledge about the code), you can't break a single encoded message.

Second question:

  If the answer is no, why isn't this used in modern computer cryptography?

Because your reasoning stops being valid after the first message send or if your assumption is no longer true. Multiple messages start showing correlations, which make single words translatable, then often used statements, then sentences, ...

Additionally, today's cryptography does not consider "ciphertext only" attacks to be a useful argument any more. If you present a new symmetric cipher which is only secure against such attacks, it gets labeled "not secure". Today at the very least, security must hold against known plaintext attacks. And at that point, no classical code can withstand.

Finally, you said in the comments "Codes are just ciphers with a very large key that always gets reused.". This is just wrong. Codes are not ciphers. The two are quite distinct and have their own properties. If anything, you could argue that ciphers are codes, extended with real security. Surely not the other way around.


Best suitable column type for openssl $tag,$iv,$key,$encrypted?

One can store all of the information as $$IV\mathbin\|encryptedData\mathbin\|tag$$ as concatenated in a blog object (though there is a limit for the size of a column).
But not the key!

The key must never be stored with the data itself. This simply a bad way for security since there is no need to store the data as encrypted beacuse if an attacker can access the database we can assume that the data is not encrypted at all. One need to store the key elsewhere like HSM or drive from a password with a KDF.

As it is well-known for AES-GCM that one need to use an IV and Key pair only once. If a pair occurs twice the confidentiality is lost. The crib-dragging technique removes the messages but not the key. The attacker will x-or the two or more encrypted messages to the x-or of the messages
$$C_1 = M_1 \oplus keystream$$
$$C_2 = M_2 \oplus keystream$$ then
$$M_1 \oplus M_2 = C_1 \oplus C_2$$ and a passive attacker has the access $C_1 \oplus C_2$ since they are listening the channel. Now, they need to execute crib-dragging and that can be automated.

A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads

Only the key stream of CTR mode of operation is revealed. AES-CTR secure against the key finding, actually more formally it is CPA secure. (The GCM forgery is another case Even a single AES-GCM nonce reuse can be catastrophic.).
To mitigate this one needs to check the IV reuse, assuming there is only one key, then using a single column for the IV is a good choice. Querying the database for the existing of the IV can prevent the issue and faster than storing all in one column.
Actually, one can use the unique rowID for the IV for the GCM if data is not updated. This is like the counter mode suggested by the NIST.
There is one big issue here, though. If one updates a row and if an attacker observed the row before and after the update then the IV reuse occurs here.  In this case, one need to generate the IV independent of the rowID and this is better since the data may be fixed today but not tomorrow.


Challenging Question for the Build a Secure MAC with Special Properties

Here is a construction that appears to meet all your criteria:

We will assume that:

$k \ge 2^{n+1}$
$MAC'_k(a | b)$ is a standard deterministic MAC (e.g. HMAC) of the string $(a | b)$

Then,

$\mathsf{Gen}$ generates a random $MAC'$ key

$\mathsf{Mac}$ is defined as $\mathsf{MAC}_k(a_1, a_2) = (t_1, t_2)$ where $t_1 = a_1 + MAC'_k( a_1, a_2)$, $t_2 = a_2 + MAC'_k(a_1, a_2)$

Within $\mathsf{Verify}$, we have:

$g(K, a_i) = (K, a_i)$

$f((K, a_i), (t_1, t_2))$ defined as:

If $0 \le t_2 + a_i - t_1 < 2^n$ and $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$, then the result is $0, \mathsf{Success}$
If $0 \le t_1 + a_i - t_2 < 2^n$ and $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$, then the result is $0, \mathsf{Success}$
The result is $1, a_i$ otherwise.

Showing that most of the conditions hold is straight-forward; showing that this resists forgery is slightly involved.  To start, the MAC will declare success only if both sides have either $MAC'_k( a_i, t_2 + a_i - t_1 ) = t_1 - a_i$ or $MAC'_k( t_1 + a_i - t_2, a_i) = t_2 - a_i$ (because the MAC of the pair $(a, a)$ is forbidden.

Now, if the two sides satisfy opposite relations (say, $a_1$ satisfies the first, and $a_2$ satisfies the second, then simple algebra gives us:

$$t_1 - a_1 = t_2 - a_2 = MAC'_k( a_1, a_2 )$$

That is, to generate this forgery, the attacker must successfully predict $MAC'_k( a_1, a_2 )$.

Alternatively, if the two sides satisfy the same relation, for example, both sides satisfy the first, namely we have both:

$$MAC'_k( a_1, t_2 + a_1 - t_1 ) = t_1 - a_1$$

$$MAC'_k( a_2, t_2 + a_2 - t_1 ) = t_1 - a_2$$

This implies that the attacker has found two MAC inputs with the relation:

$MAC'_k( a + \delta, b + \delta ) = MAC'(a, b) + \delta$

This is not believed to be feasible without knowing the MAC key.


Since your key is non repeating, you're essentially talking about one-time-pad, not a vigenere cipher.

There are two problems with what you propose:

The key is natural language. This means that the key acts like a second use of the pad. This is enough to recover the plaintext with few mistakes.

The one-time-pad doesn't just require a long enough key, the key must also be perfectly random.
The shared text is public knowledge, and thus presumably known to the attacker. So the attacker could simply test every text in their library against your ciphertext. This is quite feasible using computers, even for huge libraries.


Is it safe to reuse a ECDSA nonce for two signatures if the public keys are different?

Suppose you have two message signature pairs and following values are then public i.e. known to you -

The public keys: $Q_1 (= x_1G)$, $Q_2 (= x_2G)$
The messages and their hashes: $m_1$, $m_2$, $H(m_1)$, $H(m_2)$
The signatures: $(r_1, s_1)$, ($r_2, s_2$)

The following are unknown -

The private keys: $x_1$, $x_2$
The nonce: $k$

The following relations are known as well -

$s_1 = k^{-1}(H(m_1) + r_1x_1)$
$s_2 = k^{-1}(H(m_2) + r_2x_2)$

Note that we have two equations in three unknowns. In order to solve these we'll need to eliminate at least one unknown so that we can write one equation in terms of only one unknown and substitute that into the other equation (resulting in an equation with one unknown which can be solved via basic algebra).

The trick employed when $k$ is used with the same $x$ (i.e. $x_1 = x_2$) is that it eliminate two unknowns ($x_1$ and $x_2$) which yields an equation that is easily solved.

So how do we approach this when $x_1 \ne x_2$? The only way I see is to try to divide $s_1$ by $s_2$ to eliminate $k^{-1}$. Eliminating $x_1$ or $x_2$ seems like it would require index calculus, and that would mean solving ECDLP, which would violate the security assumptions ECDSA is predicated on.

So let's see what $\frac{s_1}{s_2}$ yields -

$$\frac{s_1}{s_2} = \frac{k^{-1}(H(m_1) + r_1x_1)}{k^{-1}(H(m_2) + r_2x_2)}$$
$$\frac{s_1}{s_2} = \frac{H(m_1) + r_1x_1}{H(m_2) + r_2x_2}$$
$$\frac{s_1(H(m_2) + r_2x_2)}{s_2} = H(m_1) + r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{s_2}  = r_1x_1$$
$$\frac{s_1(H(m_2) + r_2x_2) - s_2H(m_1)}{r_1s_2} = x_1$$

Note that we can now remove $x_1$ from the equation defining $s_1$ and we are left with a system of two equations in two variables, which can be solved via linear algebra as long as they are not linearly dependent.

(From here on I'll be using $h_n = H(m_n)$ for the sake of brevity)

$$s_1 = k^{-1}(h_1 + r_1\frac{s_1(h_2 + r_2x_2) - s_2h_1}{r_1s_2})$$
$$k = s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2})$$

Then doing some more substitution -

$$s_2 = k^{-1}(h_2 + r_2x_2)$$
$$k = s_2^{-1}(h_2 + r_2x_2)$$
$$s_1^{-1}(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_2^{-1}(h_2 + r_2x_2)$$
$$s_2(h_1 + \frac{s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$s_2(\frac{h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1}{s_2}) = s_1(h_2 + r_2x_2)$$
$$(h_1s_2 + s_1(h_2 + r_2x_2) - s_2h_1) = s_1(h_2 + r_2x_2)$$
$$s_1(h_2 + r_2x_2) = s_1(h_2 + r_2x_2)$$

So we're left with a tautology... why? Because substituting for $x_1$ into the first equation essentially left us with two instances of the same equation, just with some extra terms and terms on different sides of the equation. This means we can't solve the system. Or more precisely, that the system we have has infinitely many solutions. A simple way to see this is to consider a simpler system -

$$x = 2y$$
$$2x = 4y$$

You could substitute for $x$ in the second equation but it won't do you any good.

In conclusion, it would appear that nonce reuse with different key pairs does not allow recovery of any secret material. While far from a full or rigorous proof the above should convince you that it at least does not fall victim to an attack that uses the same approach as the nonce reused with the same key setting. In any case, if you have the choice I would advise to avoid this scenario, there are plenty of good ways to generate nonces out there. RFC 6979 is a good place to start.


What are the constraints on using GCM with a tag size of 96 and 128 bits?

I don't understand where the formula $q^2 \ell^2 2^{-142} + q^2 \ell^3 2^{-147}$ came from.  The power of $\ell$ seems too high; the fractions $2^{-142}$ and $2^{-147}$ seem awfully small; the citation is to an unpublished draft of the original security analysis that is no longer available; the final draft does not seem to support it.

First, let's assume you use sequential 96-bit nonces.  (The story is much more complicated if you have to worry about nonce collisions, and the original authors got it wrong.)  The usual approach to security analysis comes by composing two standard theorems:

Forgery probability of a Carter–Wegman universal hashing authenticator: after $f$ forgeries of messages up to $\ell$ blocks long with an authenticator tag of length $\tau$, the forgery probability is bounded by $$\frac{f \ell}{2^\tau}.$$

The forgery probability bound grows linearly with the number and length of forgery attempts, and drops exponentially in the tag length.

This is the main reason why it is more dangerous to truncate tags of universal hashing MACs like GHASH and Poly1305 than to truncate, say, CBC-MAC tags or HMAC tags, for which the analogous term $f/2^\tau$, not $f\ell/2^\tau$.
Distinguisher advantage from substituting a uniform random $b$-bit permutation for a uniform random $b$-bit function, used to derive the one-time authenticator key for each nonce (PRF/PRP switching lemma): if a random algorithm $A$ (say a forger) making $q$ queries has probability $\Pr[A(f)]$ of success on an oracle for a uniform random function $f$, then its success probability on an oracle for a uniform random permutation $\pi$ is bounded by $$\Pr[A(\pi)] \leq \Pr[A(f)] + \frac{q(q - 1)}{2\cdot 2^b} < \Pr[A(f)] + \frac{q^2}{2^b},$$ or more tightly $\Pr[A(\pi)] \leq \delta\cdot\Pr[A(f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.

The forgery probability bound grows quadratically with the number of blocks fed to the oracle (in forgery attempts or encryption queries), and drops exponentially in the block length.

Add in the distinguisher advantage against AES, and note that $q = 1 + (n + f) \cdot (1 + \ell)$ since there's one AES call to derive the GHASH key, one AES call per message to derive the GHASH mask, and one AES call per block.  The result is a bound of $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \frac{(1 + (n + f)\cdot(1 + \ell))^2}{2^b} + \frac{f \ell}{2^\tau}$$ on the forgery probability, or more tightly, $$\operatorname{Adv}^{\operatorname{PRP}}_{\operatorname{AES}} + \biggl(1 - \frac{(n + f) \cdot (1 + \ell)}{2^b}\biggr)^{\frac{-(1 + (n + f)\cdot(1 + \ell))}{2}} \cdot \frac{f \ell}{2^\tau}.$$

What does this mean for specific volumes of data that your application might process?  First, always assume the adversary can attempt more forgeries than the legitimate users will handle data—legitimate users use only as much bandwidth as their needs require, while forgers will saturate the remaining bandwidth attempting forgeries.

Let's consider three different regimes for the volume of data your application can process: a single block-message, an IP packet-sized message, and a megabyte of data per message.  We'll consider the tighter bound.

\begin{equation}
\begin{array}{llll}
\text{max bytes} &
\text{messages} &
\text{forgeries} &
\tau=128 &
96 &
64 &
32 \\
\hline
\text{one block: $16$}
  & 1 & 1 & 2^{-127} & 2^{-95} & 2^{-63} & 2^{-31} \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{16} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{16} & 2^{16} & 2^{-104} & 2^{-72} & 2^{-40} & 2^{-8} \\
 & 2^{16} & 2^{24} & 2^{-96} & 2^{-64} & 2^{-32} & 0.6 \\
 & 2^{16} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\
 & 2^{16} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{16} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{32} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{32} & 2^{32} & 2^{-88} & 2^{-56} & 2^{-24} & (?) \\
 & 2^{32} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{32} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
 & 2^{32} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\
\hline
\text{IP packet: $2^{11}$}
 & 2^{48} & 1 & 2^{-120} & 2^{-88} & 2^{-56} & 2^{-24} \\
 & 2^{48} & 2^{48} & 2^{-72} & 2^{-40} & 2^{-8} & (?) \\
 & 2^{48} & 2^{56} & 2^{-64} & 2^{-32} & 0.6 & (?) \\
 & 2^{48} & 2^{60} & 2^{-14} & (?) & (?) & (?) \\
\hline
\text{megabyte: $2^{20}$}
 & 2^{32} & 1 & 2^{-111} & 2^{-79} & 2^{-47} & 2^{-15} \\
 & 2^{32} & 2^{32} & 2^{-79} & 2^{-47} & 2^{-15} & (?) \\
 & 2^{32} & 2^{40} & 2^{-71} & 2^{-39} & 2^{-7} & (?) \\
 & 2^{32} & 2^{48} & 2^{-63} & 2^{-31} & (?) & (?) \\
 & 2^{32} & 2^{50} & 2^{-50} & 2^{-18} & (?) & (?) \\
 & 2^{32} & 2^{51} & 2^{-14} & (?) & (?) & (?) \\
 & 2^{32} & 2^{52} & (?) & (?) & (?) & (?) \\
\end{array}
\end{equation}

Entries labeled (?) have no bound at all on forgery by the above analysis.  Note that rotating keys doesn't help: the forger's attempts at forgery for the first key are independent of the forger's attempts at forgery for the second key.  Very small tags provide almost no security for even a modest number, tens of thousands, of modestly sized packets.

To put these forgery probabilities into perspective, the Bitcoin network rolls a 1 on a $2^{64}$-sided die about once a second.

Exercise for the reader: Compute the forgery probability bounds for the volumes of data in NIST's table, and assess how sensible they are.

WARNING 1: There may be fenceposts in the above analysis and errors in the calculation of the table entries.  For better confidence, trust anonymous reviewers at meatspace crypto conferences rather than pseudonymous strangers at internet crypto forums, and/or double-check the calculations yourself.

WARNING 2: Did you remember to use sequential 96-bit nonces?  You forgot, didn't you?  Go back and use sequential 96-bit nonces, or switch to crypto_secretbox_xsalsa20poly1305 which is faster and safer in software and allows random nonces and has better bounds than the above even with random nonces.


How would I go about solving this cipher?

"I suspect it's some sort of cipher where each symbol represents one specific letter."

If your assumption is true then I would recommend frequency analysis, even though this cipher text is rather short.


Methods of making ASIC/GPU resistant encryption?

As pointed in this comment, using a huge random key for a sound block cipher is an excellent defense to resist ASIC/GPU attacks. Each bit added doubles the effort required. If an adversary was able to build $10^{12}$ ASICs each capable of testing $10^{12}$ keys per second, odds of finding a 128-bit key by brute force running that for a decade are less than one in $10^6$. Thus 128 bits of key are good enough to resist ASIC/GPU attacks in the foreseeable future if you discount the possibility that quantum computers will become useful cryptanalytic tools; make it 256 bits if you account for that or a number of other questionable possibilities. Use this as key for a cipher without a backdoor, on a platform with no exploitable side channel: confidentiality problem solved (but neither integrity or anonymity). Fine, but:

Generating a true random secret key is non-trivial; and it is impossible to distinguish from its output that some allegedly true random generator is bad (that's for many incompetently designed/implemented generators, and any competently rigged one).
In many applications, both sides must agree on the secret key (Public Key cryptography can help that, but I won't touch key establishment or distribution here).
Real platforms have side channels, accidental or deliberate.
Typical users have great pain remembering even a 80-bit random key (roughly equivalent to learning three 8-digits phone numbers, not including prefix).

The last issue is often dealt with exclusively by key stretching (also known as password-hashing, or Password-Based Key Derivation Function; you know when a field is immature when its name has not even settled). A PBKDF turns a weak passphrase into a wider key, using as many iterations as practical of some appropriate transformation. This is when (and only when for a proper system, with the possible exception of PK crypto as used in key establishment or distribution) ASICs/FPGAs/GPUs should be a threat.

The current state of art in key-stretching is scrypt. In order to reduce the speedup obtainable at a given cost by using ASICs/FPGAs/GPUs, scrypt strives to make best use of resources available by the legitimate key stretcher with a modern CPU:

considerable memory;
multiple cores;
fast operations (addition, xor, and fixed rotations) so that software performance is not too bad.

How to improve on that is the subject of active research, and the ongoing Password Hashing Competition.


Why are leaf nodes hashed in merkle tree?

Merkle Tree is based on hashing to the root to provide an efficient digital signature. If the leaves just contain a single data then the parents cannot contain the hash of both children and the combined hash in a simple node design. This can complicate the structure and programming so that the last parents must contain the hash of their children and their combined hashes, too.
You can design like that, however, it will not simple as the Merkle tree. For example, as pointed on the patent, you can design a Merkle tree  trinary tree too.
This is rather an efficiency issue, not a security issue if the hash chain still has the countermeasure to prevent the second pre-image attack with the prefixes.


If RSA Signature is not Decryption, why is it not advisable to use same keys for enc/dec and sig/ver?

The advice to use different key pairs is not because there is a risk of exposing your key, just that enc/dec and sign/ver often have a different security level, or can become so in future.

E.g. If you are using signed and encrypted email for your job, it's not unreasonable for the company to have a copy of the decryption key so that they can read the emails sent to you (as a representative of the company). Where as there is no legitimate reason for the company to impersonate you, so there is no reason to provide them your signing key.

Even if this doesn't occur now, you may need to change this retrospectively. E.g. Even if a company doesn't keep a copy of the decryption key proactively, they may ask for it when you leave. If you've kept the keys separate there isn't really a problem with this (as long as you use separate keys for work and personal purposes), but you wouldn't want to hand over a key that could also be used for signing as that would allow you to be impersonated.

Similar situations can crop up in most contexts. E.g. I may want to make provisions for my heirs to decrypt my personal communication when I die, but would not want to enable them to impersonate me. By keeping the keys separate I can make provisions to release my decryption key on my death, but ensure the signing key dies with me.


AES-NI is just a fast way for the processor to execute the calculations of AES. Normally the computer has to calculate every single step of the AES key schedule and the rounds as a single instruction: Substitute it with the S-boxes, shift the rows, mix the columns, XOR the round key. This is called a software implementation. Every instruction has to be done in software from the program.

Using the AES instruction set the program can do a whole round in a single instruction. There are several different instructions to do this: New instructions, Wikipedia.
The instructions will be executed on hardware level, in the transistors of the processor. Without the whole other things a processor normally does to execute a program the encryption and decryption are much more efficient. This is called a hardware implementation. As far as I know, every block cipher is more efficient in hardware than in software. Some more, some not so much. "More efficient" means faster, less energy-consuming or both.

Yes, AES-CBC encryption still has to be done sequentially. AES-NI can only help with one encryption or decryption, but it still greatly increases the speed, because the encryption or decryption is the slowest part of CBC mode. (For the sake of completeness: You can use AES-NI for every encryption mode, not only CBC.)


With AES-GCM, may I use multiple tags per key?

I thought I'd update this with what I learned designing my ASIC.  I found the literature and terminology very ambiguous, even McGrew & Viega's paper on GCM.  Thanks to Poncho and others for their answers.  Here are some notes from my code:

************************* Nonce Format *****************************

|<--            Counter Block (CB) (128 bits)                   -->|
|<--            Nonce (96 bits)                   -->|
                                  |<-  Invoc Cntr  ->|
                      Salt[56:63] |<-->|
+-----------------+---------------+------------------+-------------+
|   salt[0:31]    |  salt[32:55]  |       SEQ        |   Blk Ctr   |
+-----------------+---------------+------------------+-------------+
|<--    32      -><--    24     -><-      40       -><-   32     ->|

Salt:  64-bit value used to form the nonce.  This is unique to each
       key.  It should be true-random but need not be secret.
       RFC-4106 recommends that only salt[0:31] be used and that
       salt[32:63] be left at 32'b0.  salt[56:63] will be XORed
       with the leftmost 8 bits of SEQ.
SEQ:   Extended sequence number, aka invocation counter.  This is
       called the IV (Initial Vector) in RFC-4106.  This normally
       starts at 0 with a new key and increments every frm.
Blk Ctr:  This starts at 32'd2 on every frame and increments for
       every 128-bit block of cryptext.
-------------------------------------------------------------------

In my case, I start with a key/salt pair, which should be updated every 8 hours. (I generate a new tag every ~6$\mu$s, and the NIST recommends not using more than $2^{32}$ tags per key.)

Much of the terminology (e.g., "IV") is ambiguous.  The terms I use are not completely standardized.  There is a unique "nonce" for each "frame", where each frame has a tag.  The nonce format is shown above.  The "salt" is normally 32 bits but can be up to 64 bits.  It changes when the key does.

When the key/salt changes, the 40-bit sequence counter SEQ is reset to 0.  SEQ increments for every "frame", each of which is terminated with a tag.  In my case, "frames" have about 20e3 128-bit AES blocks.  SEQ should not exceed $2^{32}$ to prevent tag forging.

The 32-bit block counter starts at 2 at the beginning of each "frame".  It increments for each 128-bit block up to about 20e3 and then resets for the next frame (after a tag is generated).

I don't have to worry about collisions because only one chip is encrypting with a given key, so there will be no nonce reuse.


Does MD5 hash have quasi commutative property?

No it does not. There are only a few cryptographically strong functions that have that quality out there. lattice based methods are promising.


Would RSA-encrypting a private key for itself constitute a vulnerability?

If there is a vulnerability in encrypting a RSA private key with the corresponding public key, when the private key is password-protected, then it mechanically implies a vulnerability in the password-based protection scheme: if an attacker gets a copy of the password-encrypted key (without the password), he can encrypt it with the public key himself; so an attack on the result (RSA encryption of the password-protected private key, leading to a private key compromise) is readily turned into an attack on the password-based encryption.

Without password encryption, things are a bit less clear. Consider the following hypothetical RSA-like cryptosystem:

$n = pq$ is the public modulus, with public exponent $e$;
private key is $p$ (knowing $p$, $n$ and $e$ is sufficient to recompute the private exponent $d$);
encryption uses no padding (message $m$ is encrypted by computing $m^e \mod n$ directly).

Then the encryption of the private key yields $p^e \mod n$, an integer which is a multiple of $p$ (it is equal to $p^e-kpq$ for some integer $k$) but not of $q$. Therefore, a simple GCD between that value and $n$ reveals $p$.

Now, the real RSA has padding, and, more importantly (here), when used in GnuPG, is an hybrid encryption scheme: what RSA actually processes is a random value, from which is derived a symmetric encryption key, which is then used to encrypt the actual data. For RSA-encryption of the (unprotected) private key to be a vulnerability, it would require the symmetric encryption to somehow transport unscathed algebraic properties from the private key structure to the modular exponentiation. This is highly improbable and my gut feeling is that there is no problem here. But still, no formal proof.

Why would you want to do that, anyway ? To do anything with an encrypted message, you have to know the decryption key -- and if you already know the decryption key, why would you care about obtaining it again from the decryption ?


Of course you can use Elliptic Curve cryptography to do public key encryption, that is, a method with a public key and a private key; anyone with the public key can encrypt, but only someone with the private key can decrypt.

One way would be to use the Integrated Encryption System.  It's does most everything for you (allowing the encryption of arbitrary sized plaintext efficiently, and throws in an integrity check as well).

However, in your case, I do see two potential pitfalls:

If all you got is some software that verifies an ECDSA signature, I don't know how that could be used to generate ECIES ciphertexts - or any other type of ciphertext.  Something that verifies a signature may only produce one bit of output ("it verified" or "it didn't"); it does not need to export any of its internal computations.  On the other hand, if you do have something that does a 'point multiplication' - and you don't mind putting together everything else ECIES needs to run - this may not be an issue for you.
I also wouldn't recommend you use their existing ECDSA keys with that scheme; it doesn't look like it should cause any weaknesses. I  mean that I don't believe that an attacker could send them a 'ciphertext' that, if they decrypt it and reveal the plaintext, that it would enable the attacker to generate an ECDSA forgery; I don't believe that someone could ask for a specific message to be signed, and use that signature to decrypt an ECIES-encrypted message); it however still makes me nervous.  Good crypto hygiene says to use a key for only one purpose (unless there's a proof somewhere that it is safe for both uses).

Instead, if possible, I would suggest that the devices create a separate encryption key; generating EC public/private key pairs are cheap.


For each message position or role, such as a different time in a conversation or a different field in a database, you must use a distinct nonce, sometimes also called IV.

It doesn't matter what the content of the message is: in your database, you might store the same record content in two different places, in which case if you use the same nonce an adversary can tell that the two places contain the same content.  Worse, if you use the same nonce for two different places and two different message contents, an adversary can learn something about both messages or use information about one of them to learn information about another.

Your obligations in the AES-OFB security contract are simple:

You must pick the key $k$ uniformly at random and keep it secret.
For each distinct message position that you encrypt with the same key $k$, and each time if you can reuse message positions, you must use a distinct nonce.

Both the sender and recipient must share $k$ and, for each message position, the nonce in that position.  You can make the nonce for each message position public and transmit it alongside the ciphertext, or you can make it a function of where the message is, such as a message sequence number in a conversation or a record number in a database.  Note that if you ever reuse a message position, e.g. by overwriting a field in a database, then the nonce must also change from the first time you use it to the second time you use it; otherwise an adversary with two snapshots of the database can learn information about the old message and the new message from the two ciphertexts.

In exchange, AES-OFB guarantees that for up to a terabyte of data (240 bytes) under a single key, an adversary with read-only access to your database won't learn anything about the content of what you have encrypted, with the adversary's distinguishing advantage bounded by about $2^{-64}$.

Out of scope:

an adversary with write access to your database;
an adversary impersonating the database on the network;
concealing access patterns of your database;
concealing the lengths of the messages in your database;
etc.

If write access might ever be relevant—and it often can be in ways you didn't think of—then you must also use authenticated encryption: for example, AES-GCM, or NaCl crypto_secretbox_xsalsa20poly1305.  If you're not sure, err on the side of using authenticated encryption.

If access patterns and message lengths must be concealed, you have to think carefully about how to engineer your application.  Beware that compression makes the message lengths a function of the message content, which can cause lengths to reveal information about content!

In the special case where it is safe for an adversary to learn when two distinct message places hold the same message content, you can use a nonce-misuse-resistant authenticated encryption scheme such as AES-SIV or AES-GCM-SIV, which is usually constructed out of a nonce-based authenticated encryption like AES-GCM with the internal nonce chosen to be a pseudorandom function of the message and the caller-specified nonce, at the cost of some performance.

But although the concept has been formalized for some time, nonce-misuse-resistant authenticated encryption schemes are not widespread yet, and the CAESAR competition muddied the waters by not making NMR AEAD a distinct goal from AEAD, and the IETF barged ahead with adopting AES-GCM-SIV, and it's a bit of a mess.  Sorry!  In any case, it's safer if you can uniquely label all your message positions by a short string of bits (96 bits for AES-GCM, 192 bits for crypto_secretbox_xsalsa20poly1305) and never worry about it again.


Mathematical explaination of file encryption for multiple persons with multiple keys

What PGP (like pretty much any software that can do bulk data encryption with public keys) does is hybrid encryption.  Basically, it generates a random key for a symmetric cipher (e.g. AES), encrypts the file with that randomly generated key, and then encrypts the random key with the recipient's public key and attaches it to the encrypted file.  When decrypting, it first uses the recipient's private key to decrypt the encrypted symmetric key attached to the file, and then uses that symmetric key to decrypt the actual content of the file.

Wikipedia's article on PGP has a nice diagram illustrating this process:

Diagram from Wikimedia Commons, by "xaedes & jfreax & Acdx"; used under the CC By-SA 3.0 license.

One of the main reasons why hybrid encryption is so widely used is that symmetric ciphers like AES tend to be much (as in, hundreds or thousands of times) faster than asymmetric ciphers like RSA in encrypting large amounts of data.  But it also has a number of other convenient features — including, notably, that it's very easy to extend the process to allow for multiple recipients, simply by making multiple copies of the random symmetric key, encrypting each one with a different recipient's public key, and attaching all of these encrypted keys to the message.  The recipient then just needs to locate the correct encrypted key (e.g. based on attached metadata, or even just by trying them all until they find one that decrypts into something sensible and consistent), decrypt it and then proceed to decrypt the data with it.


Secure communication protocol for equality test

Equality of single bits is the XNOR function. There is no unconditionally secure protocol for XNOR in the presence of malicious adversaries. We prove this in:

  HK Maji, M Prabhakaran, M Rosulek: Complexity of Multiparty Computation Problems: The Case of 2-Party Symmetric Secure Function Evaluation, TCC 2009.

There is a simple protocol secure against semi-honest adversaries, but keep in mind that if you know your input bit, you know whether your bit is equal to the other guy's bit, then you know the other guy's bit. So the secure protocol is "just tell the other guy your input."

On the other hand, equality of strings 2 bits or longer does not even have a protocol secure against semi-honest adversaries. This follows from an old characterization of Kushilevitz: the function is not "decomposable".

  E Kushilevitz: Privacy and Communication Complexity. FOCS 1989

You can get equality test if you assume an ideal oblivious transfer. This is not unreasonable since you can get oblivious transfer from physical assumptions (like noisy channels). The private equality test described in this paper is pretty straight-forward, and unconditionally secure against semi-honest adversaries assuming an ideal oblivious transfer:

  B Pinkas, T Schneider, M Zohner: Faster Private Set Intersection Based
  on OT Extension, Usenix 2014


Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates

You will have a weistrass equation of the form:

$Y^2 = aX^3..$

Where x is the only unknown variable on the right hand side. Insert a random X value in to the right hand side. Then evaluate the right hand side. This would need to be done modulo whatever prime you are using.

You will end up with an equation of the form:

$Y^2 = K$ where K is your evaluated right hand side.

This number K is either a Quadratic Residue or it is not. You can check this using the Legendre symbol.

If it is, then you can perform the sqrt of K modulo your prime to get the value for $+Y, -Y$

How you do the sqrt depends on what algorithm you decide to use, you can use Tonelli-Shanks which is a more generic square root algorithm


Can double-encrypting be easier to break then either algorithm on its own?

Can double-encrypting (with either the same or separate algorithms) weaken security?

If you do not assume that the algorithms and keys are independent, then it certainly can.

The example of ROT13 from the other answer illustrates the point even if it is not real encryption. Similarly, a synchronous stream cipher applied twice with the same key will undo itself. Something like that could be possible with other kinds of ciphers, e.g. you could have block cipher such that $E_k = D_{k'}$ if you choose the keys wrong, or you could define AES' where the encrypt and decrypt directions are switched. A combination of these would be secure with independent keys but not necessarily otherwise.

If you assume keys are independent, the result can still be weaker compared to the stronger of the two algorithms. For example, assume you have CBC encryption that is vulnerable to a padding oracle attack. Even if you add a secure stream cipher on top, the padding oracle attack still exists. With some of those assumptions you can say that the combination is no weaker than the first cipher (pdf).


First, a PRF is a keyed function, meanwhile a hash function is usually keyless.  So, a hash function cannot be a PRF.

Second, a secure PRF can be swapped with a uniform random function without detection, and the best way to find a collision of a uniform random function is the birthday attack.  So, if the PRF has superpolynomially large codomain, then it would be collision-resistant, since the birthday attack would take more than polynomial-time.


Definition of Short Authentication String

The Short Authentication String (SAS) is used in various protocols, but in short, SAS is produced to transfer a long authentication tag into a smaller so that the two users can verbally verify. For example;

In Diffie-Hellman key Exchange, there is always a risk of Man-in-the-Middle attack. To ensure that there is no attacker in the first session, that there are no shared secrets yet, a SAS can be used. After verbal communication, if the values don't match then Man-in-the-Middle attack is detected.

Some Protocols that uses SAS;

ZRTP: Media Path Key Agreement for Unicast Secure RTP
Short Authentication Strings for TLS
Device Pairing Using Short Authentication Strings


How to supply the GCM authentication tag to the OpenSSL command line tools?

Here's a NodeJS AES-GCM module. Or alternatively, you can use the OpenSSL library to write your own GCM decryption code, here's a quick tutorial.

The OpenSSL utility has historically not supported GCM encryption/decryption via command line parameters, likely due to the auth tag issue. I don't think that anything has changed since then, so you may want to take another approach.


How to compute accumulated values in bilinear map accumulators

In your setting this is assumed to be hard. It is exactly the task of producing a forgery for message $s$ of the weakly secure Boneh-Boyen signature scheme (Sec. 3.1) under public key $g^{e_1}$ (note that the scheme is presented in the asymmetric setting but can equally be instantiated in the symmetric setting under the $q$-SDH assumption).

In other words, if you can do this, you can break the $1$-SDH problem.


What should the nonce value be for client-side encryption?

The library uses XChaCha20Poly1305 and that requires a nonce of 192-bit (24-byte). It is an extension of ChaCha20Poly1305 to increase the nonce size, ChaCha20 had 96-bit nonces. There is no standard for it, only a draft in ietf.org
The nonce is an acronym for 'number used once'. The crucial point is that one must never use the (Key, nonce) pair again. We call it nonce-misuse. If it occurs, the confidentiality is lost as the attacker can use the crib-dragging technique to reveal the two plaintexts. There is even an automated approach to solve it:

A Natural Language Approach to Automated Cryptanalysis of Two-time Pads by Mason et al

Or for detailed examples see the answer of this question;

Taking advantage of one-time pad key reuse?

For 192-bit nonces, random nonce generation is safe, since as per birthday paradox you would need to encrypt $2^{96}$ messages under the same key to hit the same nonce again with 50% probability, so you should encrypt way less messages to ensure that this probability is negligible. Keep in mind that you need to use a good random number generator like /dev/urandom. You can still use counter-based nonces if you want.

I am not sure what this value should be. Ideally, the user could recover this encrypted data with their key alone.

The nonce does not need to be secret and can be saved together with the file without being encrypted. This is not insecurity, only the key is secret. The nonce helps to use a key securely for more than once. It is secure as long as a (key, nonce) pair never occurs twice.

However, in order to decrypt any data, the nonce is also required.

That is completely normal since the decryption is the reverse of the encryption with the same key and nonce. XChaCha20Poly1305 generates a stream and we use it to x-or the plaintext. In order to regenerate the stream we need to use the same inputs.

Hard-coding some nonce in the application feels odd, but if I randomly generate a nonce, the user will be required to remember this nonce along with their provided key in order to recover the encrypted data.

Hard-coding a nonce is not acceptable as then it would be used more than once. There is no problem with rememebering the nonce, it is secure. Save it in a file like $$nonce\mathbin\|encryptedFile\|tag.$$
Note 1: The XChaCha20Poly1305 is an Authenticated Encryption, that will provide you confidentiality, integrity, and authentication if correctly used. Incorrect tags must not be ignored during the decryption. If the tag doesn't match, throw an error.

Encryption
$$(c,tag)= XChaCha20Poly1305Enc(key,nonce,message)$$

Decryption
$$(m|\perp) = XChaCha20Poly1305Dec(key,nonce,c)$$
where $\perp$ (\perp) is the halt if the tag mismatch.

Note 2: There were a recent question about Is it dangerous to encrypt lots of small files with the same key?. One can use the similar idea to generate different keys for each file, too.
A final note: if you encrypt and update data multiple times with the same key and nonce this also can cause nonce-misuse and some part of the new and old version of the file may lose confidentiality. Therefore, for every update use a new nonce and encrypt the file again.


In English, are there any words which encrypt to other words under the Caesar Cipher?

Actually, we have a four-way (that is, four words that will can be converted into any of the others with the right shift).  These words are:

ax, by, he, if

Other two letter words are:

am <-> my
at <-> pi
do <-> it
hi <-> no

We also have

the <-> max

I didn't do a systematic search for words over two letters; there certainly do appear that they are moderately plentiful

I've done a more systematic search over longer words; ignoring extremely obscure words, the best I found were

abjurer <-> nowhere
inkier <-> purply
fusion <-> layout
manful <-> thumbs
primero <-> sulphur
steeds <-> tuffet

(OK, 'tuffet' missed by 'obscure' criteria; I still liked it).

So, yes, there certainly are words can be be encoded into other words


Does GCM need to incorporate the length of the associate data and the length of the ciphertext to be secure?

Well, if the lengths were not included, then an attacker could modify the ciphertexts (or the AAD), and still have something that would be accepted by the receiver.

Here are some of the obvious ways an attacker could do this:

He could add (or remove) trailing 0 bits (or bytes); as long as the number blocks remains constant, this would not change the tag.  Of course, this is because GCM uses an all-0 padding at the AAD and ciphertext; as designed, that's safe (because of the length block)
He could prepend a block of all 0's to the AAD (and if there is no AAD, he could do that to the ciphertext); because the polynomial that GHASH computes start with the 0 value, an initial 0 value would still result in a 0 (and thus not change the tag)
He could migrate part of the AAD to the ciphertext (or versa-visa); for example, if the AAD consists of blocks $AAD_1, AAD_2$, he could make the AAD the single block $AAD_1$, and prepend the block $AAD_2$ to the ciphertext.  Again, without the length block, this would be undetected.

Of course, it would be fairly easy to tweak how GCM worked internally so that the first two methods wouldn't work (use a padding method other than all-0's, start the polynomial with the value $H$ rather than 0); however the third attack would be harder to mitigate.


generate RSA public key having public modulus and exponent

i got this, it's not with openssl, but python

e = 0x10001
N = 0x1234214....

words = open("words.txt").read().split()

for w in words:
     ww = int(w.encode("hex"), 16)
     print pow(ww, e, N)


Slow hash algorithm that does not require salt?

You can use any common slow hash construction that takes a salt with a constant salt. This includes scrypt, bcrypt and PBKDF2.

You obviously lose the benefit of the salt. Since the purpose of a salt is preventing multi-target attacks, now an attacker can attack all hashes at the same time. I'd use at least a salt that's unique for your application, so an attacker can't attack your application at the same time as others.

Personally I'd go with scrypt, since it strengthens the most for a given derivation time limit, but you can use bcrypt or PBKDF2 if you prefer older/more popular constructions.


How much extra information is in an RSA public key?

Firstly the length of an RSA key is the length of the modulus and an RSA public key consists of an exponent and a modulus, so there is a couple of bytes there.

Secondly depending on how you created and/or transmit the key it may be wrapped in a SubjectPublicKeyInfo block. It's defined as (RFC 3280):

 SubjectPublicKeyInfo ::= SEQUENCE {
   algorithm AlgorithmIdentifier,
   subjectPublicKey BIT STRING }

 AlgorithmIdentifier ::= SEQUENCE {
   algorithm OBJECT IDENTIFIER,
   parameters ANY DEFINED BY algorithm OPTIONAL }

and is basically a way of telling a receiver what algorithm the public key uses and any additional info that may be of use (probably nothing for RSA keys). So there is possibly a few extra bytes there.

If you're interested in this stuff you can look into ASN1 definitions which describe the structure in which keys and certificates (and many other things) should be passed around. If you want a quick look you can use:

openssl asn1parse -in key.prv -inform pem

to see what is in the file but in short, depending on the encoding I wouldn't make assumptions on the data size.


Using Diffie-Hellman secret key to encrypt/decrypt data?

I read that the secret needs to be fed through a "Key based key derivation function" (KBKDF), but as I understand that gives you a hash which then you won't be able to dehash... so how does the other program can decrypt the message?

The encryptor sends the DH shared secret through the KDF, which gives him a key, which he uses as (for example) an AES key, and uses that AES key to encrypt his data.

The decryptor sends the same DH shared secret through the KDF, which gives him the same key, which he uses as an AES key, and uses that AES key to decrypt his data.

There's no need to 'invert' the KDF; both sides use it in the forward direction


Blake2 vs md5 for checksum / file integrity

Yes, you should choose BLAKE2 instead of MD5.  Any of the BLAKE2 variants—BLAKE2s, BLAKE2b, BLAKE2sp, BLAKE2bp—is an improvement over MD5, even if you just use them for 128-bit digest sizes like MD5, although it is generally better to use at least 256-bit digests.  BLAKE2b is a good default; BLAKE2s is slower on 64-bit systems but friendlier to 32-bit systems; BLAKE2sp and BLAKE2bp are optimized for systems with large vector units or multiple cores to parallelize hashing long messages.

So go and rip out MD5, and put in BLAKE2 instead, and you'll almost certainly be be better off.

You've ripped out MD5?  Good!  But we should also talk about what you're trying to do with it in the first place, because while BLAKE2 is not worse than MD5, there are things neither MD5 nor BLAKE2 nor anything with the same shape—a fixed hash function—can do no matter how good they are at what they do do.

So, when you say ‘checksum’ and ‘file integrity’, what are you trying to do?  Here are some possibilities:

You're trying to detect random errors with a very simple distribution, like independent errors, or burst errors.

In this case, while BLAKE2 is not worse than MD5, you might be better off with something designed to be a checksum like a CRC rather than something designed to be a random function like BLAKE2 and MD5:

A CRC polynomial with a factor of $x + 1$ is guaranteed to detect all errors of odd parity.
An $n$-bit CRC with a nonzero $x$ term is guaranteed to detect $n$-bit burst errors.
Various other errors can be guaranteed detected by a judicious choice of generating polynomial; see the standard Koopman–Chakravarty reference (preprint, paywall-free) for more details.

This is relevant when there is no adversary involved.
You're having a conversation with someone with whom you share a secret $k$, and you want to prevent anyone else from forging messages.

In this case, you actually need a message authentication code, or MAC, which has the property that nobody who knows the key can find the MAC for any message except ones they've already seen by asking you politely to give it to them.

BLAKE2 has a built-in MAC: you can specify a key, and it magically turns into a MAC.  There are other alternatives, like HMAC-SHA256, or even HMAC-MD5 (which is to the best of our knowledge still secure up to well below $2^{64}$ messages, but you should consider switching away just so that you don't have MD5 in your code at all).
You're publishing statements that you want anyone in the world to be able to verify, but nobody to be able to forge.

In this case, you actually need signatures, which are like MACs except there are separate keys for signing (private key) and verifying (public key).  In principle BLAKE2 could be used in a signature scheme, but in practice I haven't seen any, and any good signature scheme for practical use will come with predetermined choices for any hash functions, like Ed25519 uses SHA-512 and Ed448 uses SHAKE256.

Of course, anyone who wants to verify a message needs to know the public verification key a priori: if they got it on the same channel as the signed message, the adversary could have replaced the whole thing—but at least the recipient will have the public key for next time, so the adversary would have to replace the whole thing on every day the recipient tries to fetch the public key and/or signed message.
You're publishing a manifest of files in a distribution, like a software package repository, and the manifest is published on a different channel—known to be unforgeable, e.g. because you got it over SSH or HTTPS from a good server—from the software packages themselves—e.g., because you download them over HTTP from a sketchy CDN.

In this case, BLAKE2 is a good choice!  If you used MD5, you might be in trouble.  But you should also be sure that there actually is a qualitative difference in security between the channel on which you transmit the manifests and the channel on which you transmit the files; if an adversary can modify both at the same time, the hashes accomplish nothing.
You're using a hash as a key in a content-addressed storage scheme, like Tahoe-LAFS.

In this case, BLAKE2 is a good choice!  If you used MD5, you would definitely be in trouble.


Diffie-Hellman insecure on addition modulo $n$

With addition and $\mathbb{Z}_n$, each party chooses a secret $x$ and sends $xg \pmod n$ over the wire, for an agreed upon generator $g$. Division by $g$ modulo $n$ is easily computable, and reveals $x$.

In other words, a prerequisite for DH to be secure is that the equivalent to discrete logarithm is hard in the chosen group. With $\mathbb{Z}_n$ and addition, discrete logarithm becomes totally easy.


Pseudorandom number generation predictability

Take (hypothetical) seeded deterministic PRNG algorithm Gen1. If you use Gen1 to produce a stream, and I use Gen1 with the same seed, I will get an identical stream. As per Wikipedia's definition, a PRNG is deterministic.

Now consider another hypothetical seeded deterministic PRNG Gen2, which uses a different algorithm than Gen1. If I use Gen2 with the same seed as before, there is no reason to expect the same stream to result.


Given $g^a, g^b, g^c, g^{1/b}$, is it hard to distinguish $e(g, g)^{abc}$ from a random value?

Your problem seems to be at least as hard as the 2-weak Bilinear Diffie-Hellman Inversion Problem (2-wBDHI problem):

  Given $g, g^x, g^{x^2}, g^y \in \mathbb G$, and $T \in \mathbb G_T$ to determine whether or not $T = e(g,g)^{x^3 y}$.

Proof: We first need to define an equivalent version of your problem, where we take some generator $h$ so $g = h^b$. Your original problem is to take input $(g,g^a, g^b, g^c, g^{1/b}, Q)$ and decide whether $Q = e(g,g)^{abc}$ or not. After substituting $g = h^b$, we have that the new problem is to take $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and decide if $Q = e(h,h)^{b^3 ac}$.

So, assume you have a solver $S$ for the new problem.  Then we can solve the 2-wDBDHI problem as follows:

Input to 2-wDBDHI is a tuple $(g,g^x,g^{x^2},g^y,T)$.
Sample a random element $z \in \mathbb Z_q^*$.
Call $S$ with input $(g^x,g^y,g^{x^2},g^{x^2 z},g,T^z)$, which will output Yes when $T^z= e(g,g)^{x^3 y z}$, and No otherwise.
Output the result from the last step.

Recall that solver $S$ takes input $(h^b, h^{ab}, h^{b^2}, h^{bc}, h, Q)$ and determines whether the following equation holds:
\begin{align}Q = e(h,h)^{b^3 ac}\end{align}
Take the substitutions $h=g$, $a = y/x$, $b = x$, $c = xz$, and $Q = T^z$, so:
\begin{align}T^z = e(g,g)^{x^3 (y/x) xz} = e(g,g)^{x^3 yz}\end{align}
It is clear that when this equation holds, then $T = e(g,g)^{x^3 y}$ holds too, and vice versa, so this algorithm is a solver for the 2-wBDHI problem.

According to the ECRYPT II report - D.MAYA.6
Final Report on Main Computational Assumptions in
Cryptography, the best known algorithm for 2-wBDHI is to solve DLP in $\mathbb G$, so you can say that your problem is hard.

Note: My previous answer didn't answer your question, since the strong-DDH is not hard when using pairing groups... I was merely stating that your problem is at least as hard as an easy problem (duh!)


What kind of analysis can I perform on my implementation of Salsa20 and Rabbit ciphers?

ChaCha20 and Salsa20 are both considered secure ciphers and so looking at the keystream will get you nowhere.  What you can do is analyze your implementation:

It should run in exactly constant time regardless of inputs.
There should be no data-dependent branches or array lookups


Are there some well-known crypto APIs that leak information?

The classic one that I can think of off the top of my head, that also happened relatively recently and posed a pretty widespread threat, was the Heartbleed bug.  It was a big security vulnerability that would reveal authentication info in one of the most common ways communication gets encrypted over the internet, SSL/TLS.  Most computers were affected, if I recall correctly, except coincidentally Macs, because they happened to use a different library to handle SSL/TLS.


Key length requirement in a simple XOR implementation

This cipher system is the original Vernam cipher.
(In the original Vernam cipher, the key was stored on a loop of paper tape that repeated over and over).

Like all practical encryption systems, the Vernam cipher has a secret key that it uses over and over.

ciphertext[i] = plaintext[i] bit_xor key[ i % keylength ]

This cipher can be seen as a variant of the Vigenère cipher, and has the same security.

Anyone with the secret key can decrypt a ciphertext message to recover bit-for-bit the original plaintext (no matter what the keylength is) with:

plaintext[i] = ciphertext[i] bit_xor key[ i % keylength ]

  Though the cipher is easy to understand and implement, for three
  centuries it resisted all attempts to break it; this earned it the
  description le chiffre indéchiffrable (French for 'the indecipherable
  cipher'). ...
  Kasiski entirely broke the cipher and published the technique ...
  In 1863 Friedrich Kasiski was the first to publish a
  successful general attack on the Vigenère cipher.

-- Wikipedia: Vigenère cipher

The people at the Cipher Exchange say the Vigenère cipher can be solved by pencil and paper methods with enough ciphertext -- ciphertext 15 times the length of the key.
The same techniques can be used to break this cipher, given the same amount of ciphertext.
(Some of those techniques are mentioned at "
What is the limit of plaintext required to break the Vigenère encryption?
").


What are monotonic and non monotonic access structures in ABE ?

My understanding of this is as follows:

Monotonic access structure: if $\mathbb{A}$ is a set of attributes satisfying an access structure $T$, then any $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ also satisfies $T$. For example, consider $T = A \cap B$, then both $\mathbb{A}=\{A,B\}$ and $\mathbb{A}'=\{A,B,C\}$ satisfy $T$.
Non-monotonic access structure: there exists $\mathbb{A}'$ such that $\mathbb{A} \subset \mathbb{A}'$ and $\mathbb{A}'$ does not satisfy $T$. For example, consider $T = A \cap \neg C$. Then in the previous example, only $\mathbb{A}$ satisfies $T$.


Not a complete answer, just trying to shed some of your doubts.

  I've noticed the point tripling algorithm (algorithm 6) was already described in a different paper. Nevertheless, the SIKE paper uses a slightly different algorithm for calculating [3]P.

Although the official dates may indicate that the SIKE spec was published after the Faz-Hernández, López, Ochoa-Jiménez, Rodríguez-Henríquez paper (let's call it FLOR), the two were really being written about at the same time, so it's completely possible that we missed some optimizations.

As far as I can remember (speaking only for myself), the Montgomery ladder algorithm in FLOR had been previously presented at a conference, so we included it in the spec, but we did not know about the tripling formula at the moment of writing.

  I've quickly checked - it seems to me that both algorithms give different result (am I wrong?).

I haven't checked, but it is completely possible that the two formulas give different, projectively equivalent, coordinates.

  Any idea why the algorithm from SIKE spec is preferred over the algorithm from the other paper. Is it somehow faster?

Probably not faster, since FLOR explicitly say their formula is. However you have to follow the spec if you want to implement SIKE. It is important for the KEM that algorithm isogen returns exactly what's expected from the spec, and not something that is only projectively equivalent; so you cannot replace another formula inside the algorithm, unless the output is equal.

If it is confirmed that the FLOR formula is the best available formula, we may  update the spec at the next round of the NIST competition.


Probability for success of exhaustive search on PRF keys

Let $q$ be the number of queries made by the attacker.
Consider that the view of $\mathcal{A}$ in the experiment is equivalent to their view in a modified experiment, where the oracle is restricted to the domain $\{1,\dots,q\}$.

Now consider, that in this modified experiment, there are exactly $2^q$ functions of the form $R : \{1,\dots,q\} \to \{0,1\}$.
If we sample one of those functions uniformly at random, what is the chance that one of the keys of the PRF will "hit" this function? Well, we can't say exactly, but we can give an upper bound. There are $2^n$ keys, which means at most, if each each of those keys hits a different function, $2^n$ functions can be hit.
This mean the probability of one of the keys hitting our uniformly sampled function is upper bounded by $$\frac{\# \text{ of keys}}{\# \text{ of functions}} = \frac{2^n}{2^q} = 2^{n-q}.$$

This means, we have
$$\Pr[\mathcal{A}^{R(\cdot)}=1] \leq 2^{n-q}$$

and also (by definition)
$$\Pr[\mathcal{A}^{F_k(\cdot)}=1] = 1.$$

Therefore
$$\left|\Pr\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq 1-2^{n-q}.$$

Now we need to choose a value for $q$ that makes this attack successful. If you plug in you suggested value of $q=n$, you'll notice, that we get $$1-2^{n-n}=1-2^0=1-1=0,$$
which is unfortunate.
We notice that as soon as we choose something a bit larger, say $q=n+1$ , we have a successful attack by standard definitions of PRFs:
$$1-2^{n-(n+1)}=1-2^{-1}=1-\frac{1}{2}=\frac{1}{2}$$
which is non-negligible.

However, we like to go for attacks that are successful with overwhelming probability and we like to go for simple easily recognizable negligible functions.
So we choose $q=2n$ and get
$$1-2^{n-2n}=1-2^{-n}$$
which is easy to read and readily recognizable as an overwhelming probability.


Do I understand HMAC-SHA-xxx and HMAC-SHA-xxx-yyy correctly?

HMAC-SHA-xxx has an output length of xxx bits

That's right, the output of the HMAC function is identical to the output of the hash by default. This is obvious if you take the design of HMAC in consideration.

  HMAC-SHA-xxx-yyy has an output length of yyy bits

Certainly. It has been defined that way in the venerable RFC 2104 - HMAC: Keyed-Hashing for Message Authentication, section 5: Truncated output.

Not many implementations will allow you to specify the output size, so you may have to truncate yourself. Beware that it is best to perform a time-constant compare when verifying a HMAC value if you have to perform the truncation instead.

Using a standardized, truncated version of SHA-2 would be an option if truncation of the hash is not available (e.g. SHA-224 is already a truncated version of SHA-256). It has the disadvantage that the inner security of the hash is lowered together with the output size.

  If I have a function that generates HMAC-SHA-xxx output, then I can create a function that generates HMAC-SHA-xxx-yyy output simply by returning the first yyy bytes of HMAC-SHA-xxx output.

Yes, you'd use the leftmost bits / bytes. yyy would be in bits, so you'd have to devide by 8 (and I would only allow multiples of 8 for yyy).

Beware that the authors of the RFC talk about "recommend" and "propose" in section 5, so the implementation of HMAC-<hash>-yyy seems strictly optional.


Is there a relation between passive/active attacks and IND-CPA/IND-CCA?

IND-CPA and IND-CCA are formal security models. "Active" and "passive" are informal descriptive terms.
"Passive" usually refers to an adversary who simply observes a system under its normal operation by honest users. "Active" refers to an adversary who "interferes" in some way, causing situations that cannot arise under honest usage, usually by providing "unexpected" or "impossible" cryptographic data.
CPA is a "passive" attack since the adversary just observes honestly generated ciphertexts. The adversary chooses the plaintexts, but that is not considered an "active" attack -- plaintexts themselves are not cryptographic, and the encryption algorithm is still applied honestly to those plaintexts.
CCA is an "active" attack since the adversary can cause maliciously generated ciphertexts to be decrypted. This is something that can never happen under the normal operations of a system by honest users.
The paper that you reference considers itself a "passive" attack because it only involves decrypting ciphertexts that are the result of honestly running (an adversarially chosen sequence of) the encryption scheme's algorithms.


Malicious Model and Arbitrary selecting inputs on MPC and PSI

In general, such attacks are "allowed" in the malicious model. This is due to the fact that secure computation guarantees that the process of computation reveals nothing. A secure protocol should behave like an ideal model where a trusted party computes the result. Now, in some cases, this is a problem. However, in practice, in many cases it is OK.

Consider the case of PSI: in practice, the length of the inputs is known to both parties. Thus, it may not be possible for one party to input the entire universe (which may also be huge). Having said this, this is possible if a protocol is used that depends on the entire universe (e.g., PSI by running secure computation via a circuit that computes over vectors of bits, so that the $i$th bit of a party's vector equals 1 if and only if it has the $i$th element of the universe in its input). Formally, the definition of the functionality should express the size of the input and therefore make this clear. However, in reality, this detail is often overlooked in papers.

In short, this is a real issue and if you want to use MPC you need to understand the ramification of "maliciously chosen inputs".


Can the passphrase of a PGP key be deduced from an old backup?

I'm assuming Bob uses the standard format, OpenPGP aka RFC4880, to store his private key in a private keyfile.

If the adversary Eve somehow obtains Bob's private keyfile, and the passphrase on that keyfile is so short and weak that the adversary breaks it with a dictionary attack or brute force, then -- Things are very bad for Bob.

Bob's best choice of action here is to generate a fresh new second private key, tell everyone (possibly by using messages signed by his original private key) to use the new public key and revoke his earlier key.
(Yet how will people be able to tell that these messages really came from Bob?
Perhaps those messages are actually from Eve, forged to appear as if they came from Bob,
telling everyone to use a public key corresponding to a private key known only to Eve.
All they can be sure of is that the original key has been compromised and should be revoked).

However, in this scenario Bob inexplicably keeps using his original private key, but re-encrypts it using a good passphrase.

Then Eve somehow obtains Bob's new private keyfile, including the original private key (which she somehow guesses is the same as the private key she extracted from the earlier keyfile) encrypted by Bob's new good passphrase.

  Will Eve be able to deduce other secret information, decrypt other things encrypted with Bob's /new/ passphrase, or perhaps even deduce the passphrase itself?

Unlikely.

You are describing a known-plaintext attack: Eve has an encrypted text (the new private keyfile encrypted with the new passphrase) and the corresponding plaintext (the private keys extracted from the old keyfile), and is trying to use that to reveal further secret information.

The standard OpenPGP format encrypts the private keys with (a key formed from a hashed version of) the passphrase using one of several algorithms listed in RFC4880 section 9.2. "Symmetric-Key Algorithms", typically AES.

Known-plaintext attacks were well-known when those algorithms were written.
All of those algorithms were specifically designed to be resistant to known-plaintext attacks.
They are designed such that even after a Eve obtains hundreds of plaintext+ciphertext pairs, all the ciphertext encrypted using the same "good" passphrase, it is practically impossible for Eve to recover that passphrase or decrypt any other message.


How to construct a strong Fiat-Shamir in zero-knowledge proof?

Quick remarks:

the Fiat-Shamir transform is implemented with a standard hash function (e.g. SHA-256 or SHA-3). Random oracles do not exist in the real world: it is only in the security analysis that the real hash function is modeled as a random oracle to get heuristic guarantees about its real-world security.
In most $\Sigma$-protocols (Schnorr included), the prover first generate a commitment (in Schnorr, this is something like $g^r$). Fiat-Shamir is then used to generate the verifier challenge non interactively by hashing something the prover has. Strong and weak Fiat-Shamir usually refer to the following alternatives: either the prover hashes only the commitment (e.g. $g^r$, this is the weak Fiat-Shamir - avoid it) or she hashes both the commitment and the statement (e.g. $(g^r || g^x)$ if you use Schnorr to prove knowledge of the discrete logarithm of $g^x$, this is the strong Fiat-Shamir - use it).

As for why these differences matters: in some scenarios (typically, when the prover can choose the statement adaptively in the larger context where the zero-knowledge proof is used), the weak Fiat-Shamir transform is provably insecure. This is discussed for example in this paper.