Equality checking using additive homomorphic encryption

I'm not sure if I understand what you are asking, so I'll clarify what I am about to answer. We are given two ciphertexts and we want to know if they encrypt the same plaintext or if they encrypt different plaintexts, and we want to do this without revealing anything but this fact.

Then, using the additive homomorphism, it's possible to compute $c=enc(r\cdot (p_1-p_2))$. If $p_1=p_2$ then this is an encryption of 0; else it's an encryption of a random value.

Now, let's consider the setting where one party holds the private key and the other has $c_1,c_2$. Then, the 2nd party can compute the above as I showed and send it to the first party. The first party can then decrypt and see if it is 0 or not. There exist ways for the first party to prove this to the second party efficiently.

I hope that this answers the question.


Is there a difference between $\mathbb{Z}_2^b$, $\text{GF}(2^b)$ and $\text{GF}(2)^b$?

$\mathbf{Z}_2^b$ is the direct product of $b$ copies of $\mathbf{Z}_2$ ($\mathbf{Z}_2 \times\cdots \times \mathbf{Z}_2$, $b$ times). That is, its elements are $b$-tuples of elements of $\mathbf{Z}_2$, with both addition and multiplication defined componentwise. If $b > 1$, it is not a field. In fact it is not even an integral domain, because $(0,1)\times (1,0) = (0,0)$.

$\mathrm{GF}(2^b)$ is the field with $2^b$ elements. Because it is a field, it is not the same thing as $\mathbf{Z}_2^b$ if $b > 1$.

You should know that for any prime $p$, $\mathbf{Z}_p$ is a field with $p$ elements, so it is the same thing as $\mathrm{GF}(p)$.


CAESAR finalists: Lightweight case (Ascon vs ACORN)

Ascon and ACORN both have interesting features. Let's discuss their pros and cons for some properties stated during the CAESAR competition for lightweight AEADs:

Fits into small hardware area and/or small code for 8-bit CPUs

On this point, ACORN is more efficient as its internal state is smaller than the one used by Ascon (293 vs 320 bits). Moreover, thanks to its very compact core function, the code size of ACORN is smaller.

Natural ability to protect against side-channel attacks

Regarding countermeasures against side-channel attacks, both algorithms are efficient. Ascon has been designed with bitslicing in mind, and thus can be easily implemented in a constant time manner. ACORN is also constant time by design as it does not rely on any conditional branch nor look-up tables. Regarding countermeasures against power/electromagnetic side-channels, 1st order threshold implementation can be reached using only three shares for both algorithms. However ACORN seems more efficient in hardware as stated in the paper you mentioned.

Message sizes: usually short (can be under 16 bytes), sometimes longer

This is maybe the main advantage of Ascon over ACORN: it is way more efficient for short messages. This mainly comes from the fact that ACORN is a stream cipher that requires a huge number of steps to initialize its internal state. For instance, this paper reports (page 11) that Ascon outperforms ACORN for small messages (less than 128 bytes with 16 bytes of additional data) on ARM Cortex-M3. Ascon is also very efficient on 64-bit CPUs as by definition, its internal state consists of five 64-bit words. It is an interesting feature for use cases where high end servers have to handle numerous encrypted requests.

Finally, Ascon is based upon the duplex sponge mode whose security has been analyzed in several papers (e.g., https://keccak.team/files/SpongeDuplex.pdf and https://eprint.iacr.org/2015/541.pdf) while ACORN is based upon a new stream cipher construction. This probably influenced the final decision.


If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG?

$F(s)=G(s)\mathbin\|G(\bar{s})$ is not necessarily a PRG. We'll construct a counterexample.

Assume $H(t)$ is a PRG.

Now define $G(t\mathbin\|0)=H(t)$ and $G(t\mathbin\|1)=H(\bar t)$. The $G(s)$ thus defined is a PRG with input width $|t|+1$. Yet $F(s)=G(s)\mathbin\|G(\bar s)$ is not a PRG, because its two halves are always equal.


Will cryptanalysis always stay a relevant topic?

In the modern cryptologic sense cryptanalysis is the science of breaking concrete constructions. This will stay relevant for as long as we rely on constructions which only satisfy security notions heuristically. We can't come up with a general construction that is a Pseudo-Random Permutation for all input lengths, because that would imply $P\neq NP$. Therefore we need heuristic constructions like AES. Additionally this field will stay relevant for as long as we try to come up with new schemes that are ever faster and smaller for some definitions of fast and small.
Furthermore one could argue that side-channel analysis belongs to the general group of cryptanalysis as well and that will remain relavant for as long as we compute cryptographic algorithms on non-ideal hardware.
One may also argue that all these attacks one hears about against TLS, WPA, or SSH also fall under "cryptanalysis". In a sense I agree: While quite a few of them are implementation errors there are also some that aren't. In fact usually these days these protocols have security proofs in a particular communication and adversary model. The point of the attacks is then to find scenarios that aren't covered by the adversary's possibilities in said model, then find an attack that breaks an intuitive security property and argue why this break is (more or less) relevant. Though it is to be expected that this line of research will eventually exhaust all possible oversights in any given class of models. Of course some people also use protocols without proofs and those will always be the target of cryptanalysts (or proof-focused people) for as long as people do this - which may also yield successful attacks despite unbroken building blocks.

I hope this doesn't look like a silly question. In an age where our current cryptography is often impossible to crack when properly implemented and used, would we be able to decipher anything, for example if WWIII were to break out ?

It is currently believed that things like AES are actually secure. However, many governments have their own encryption algorithms, e.g. for highly-classified data. Most of these algorithm descriptions are classified, so only some of that country's researchers can analyse it and so some weaknesses could have been missed. This is of course less of a problem for countries like the USA but more of a problem for smaller countries with less access to enough people who are really good at this sort of cryptanalysis. A similar argument applies to the mechanisms used to transport / negotiate the keys for these algorithms, though probably less strongly. Because of this, it is not impossible for "hostile" encryption schemes to be broken once a description has been acquired - though it is unlikely as the really hard part about this kind of cryptography is getting it fast and secure as opposed to "merely" secure.

Iirc, quantum computers can trivially break RSA, but I don't know about AES.

Quantum computers can break most currently deployed asymmetric cryptography given a sufficient size. They can also give a substantial speed-up (in theory at least) for breaking symmetric schemes, but it is generally believed that this is "fixed" by doubling the key size from 128 to 256 bit (as quantum algorithms half the bitlength of the search space).
This point actually allows us to come back to the first question: It is currently an active effort to come up with as efficient asymmetric cryptographic algorithms as possible that resist quantum computers. As we don't have unconditionally provable secure constructions against quantum computers, we resort to heuristic methods again, which require analysis to see whether they actually stand up against quantum computers.

Also, while talking about quantum things, I think I heard about a paper related to the teleportation of some bits between 2 processors.

This is more of a question for Quantum Computing SE or Physics SE. If you're still looking for an answer on this site, I'll refer you to poncho's answer.


Is X25519 and Ed25519 the same curve?

No. X25519 isn't a curve, it's an Elliptic-Curve Diffie-Hellman (ECDH) protocol using the x coordinate of the curve Curve25519. Ed25519 is an Edwards Digital Signature Algorithm using a curve which is birationally equivalent to Curve25519.
Is X25519 used by ECDSA?

No. It's not a curve, it's an ECDH protocol.
What does the X in X25519 and X448 stand for?

The X coordinate is what's transferred, the Y coordinate doesn't need to be transmitted due to the way these protocols work.
Is the security advantage of EdDSA a result or the Ed25519 curve or the different algorithm it uses than ECDSA?

Both (and somewhat neither). EdDSA's algorithm allows it to use curves that are more secure while being fast (ECDSA could be done using the complete point addition formulas over ANY elliptic curve, but it would be slower for many curves).
Additionally EdDSA is deterministic: there's no need to generate a nonce, and no need to track that a nonce is only used once. On the other hand, signing a message twice with the same key will reveal that the same message was signed.
If ECDSA is used with the 25519 curve is it just as secure as EdDSA?

Maybe. It would depend on how the math is done, and on how the nonce generation is handled.
Is ECDSA considered to be secure as of Oct 2020?

This depends on the particular implementation. It's NIST approved, and can be used securely if implemented well.
Should EdDSA be always used over ECDSA?

Not at this time. Some things will require ECDSA, for example the US government's FIPS 140 compliance doesn't allow EdDSA (yet). Also EdDSA signatures are deterministic (as mentioned above) which might pose problems to some schemes (though it does eliminate the security issues of nonce reuse that ECDSA has).
As kelalaka pointed out there already exist answers to most of these questions here, I've not bothered to link them.


Key-Agreement & Key-Transport for Symmetric Authentication System

For a full symmetric key key transport, the symmetric key is created from a random number generator. This is then signed with the owners static private key and then encrypted with the recipients static public key (key wrapping), and then sent to the recipient. The recipient will receive, decrypt and verify the signature, and the symmetric key is decided on. Whilst a key agreement algorithm like ECDH(E) or DH(E) isn't needed, an asymmetric cipher such as RSA is needed. This is referred to as a KEM system (key management), and requires an asymmetric cipher algorithm for the key wrapping.

For a key agreement or KEX (key exchange), then ECDH(E) or DH(E) is used, where both parties exchange bits of info and then calculate a shared secret, which goes through a HKDF to convert in into the format of a symmetric key.

So even for key wrapping, an asymmetric cipher must be used at some point, so that the key can be securely transported to the recipient, and it's authenticity verifiable.


Downgrade attacks can be detected when the FINISHED messages are exchanged and verified. Of course, the goal of an attacker is to downgrade the security of the handshake, being able to compute the master key. If the attacker computes this key before both clients proceed to verify the FINISHED message, then he's able to spoof it and trick Alice and Bob.

Pointing to your question, that includes the ServerHello message, as the server would check if the messages received by the client match the messages sent by the server. In the case of a downgrade, the server detects that something different has been sent to the client, as there is a missmatch in the verification of the FINISHED message.


Is Lamport-Diffie EUF-CMA secure in the standard model?

Is the Lamport-Diffie signature secure in the standard model?

Technically, no, the Lamport(-Diffie) one-time signature scheme is not EUF-CMA secure, however, also technically "it depends".
Nominally, a signature scheme is typically called "secure" - especially in the public-key world - if for a polynomial number of adverserial interactions with it in the relevant model the advantage of said adversary is still negligible - with the negligibility coming from some security assumption typically.
However, you can easily construct an adversary which performs 2 interactions with the signature scheme in the EUF-CMA model and achieves an advantage of 1 from that. Such an adversary would e.g. query $0^n$ and $1^n$ as messages, revealing all private keys.
Also however, we can still construct a security statement, namely $$\mathbf{Adv}^{\textsf{EUF-CMA}}_{\text{LD-OTS}_F}(\mathcal A;q,n)\leq\begin{cases}\mathbf{Adv}^{\textsf{OWF}}_{F}(\mathcal A';n)&q\leq 1\\1&\text{else}\\\end{cases}$$ where $n$ is the security parameter, $q$ is the number of queries, $\mathcal A'$ is an existentially qualified adversary against the underlying OWF $F$ and $\mathcal A$ is the polynomially-bounded universally qualified adversary. The order of quantifiers is for all $\mathcal A$ exists $\mathcal A'$.


Differential privacy does not help to prevent disclosure of individual records when the user—the doctor, in this case—needs access to the individual records themselves.

Differential privacy is a property of a system for aggregating a collection of records into statistical queries on a data set so that the inclusion or exclusion of an individual record can't change the answers to the statistical queries much.  That way, the answers to the statistical queries—which might be published in a medical journal, or used to study trends—can't reveal much about individual patients.


Can I get successful signature verification with just altering message and signature?

Is there any possibility to make a successful verification with just modifying message and signature, and without modifying public-key ?

One would certainly hope not.  If you can, then you've just shown that the signature algorithm used is broken, and not to be trusted.

For a signature method to be considered secure, then it is required that someone without the private key cannot somehow cobble up a signature to any message that has not be specifically signed by someone else with the private key.  The attacker is allowed access to valid signed messages (and we even allow him to pick the messages to be signed).  If he could take a valid message and signature, and somehow alter the message, and come up with a valid signature, he has just violated the security property of the signature.

Now, you do use SHA-1 as the hash function - what this means is that it is believed to be feasible (nobody has actually done it and published it) to create two messages that has the same SHA-1 hash; if he then gets one signed, then that signature would be a valid signature to the other message.  Because of this, we're urging people to use a stronger hash (such as one of the SHA-2 or SHA-3 hashes).  I bring this up because this is the one known way (assuming that your RSA key is strong) that someone could generate a forgery with what you are doing.


I don't think $h^l$ where l is a float number is a well defined operation in a finite group, regardless of what context you want to use this group for.
A group is a set of elements G with a binary operation $\cdot$ (multiplication) defined, often denoted as (G,$\cdot$) satisfying four properties. You can find more information here: http://mathworld.wolfram.com/Group.html.

Then, exponentiation is defined as repeating multiplication on a group element a certain number of times. For example, $h^n=h\cdot h\cdot h \cdot ... \cdot h$ (repeating $n$ times). So you should be able to see that for example repeating multiplication 3.1415956 times is not well defined.

Specifically, for pairing, G2 is a group over the twist curve. In this group, one operation is defined. Usually, this operation is called point addition. However, in PBC, if you look at the document, it is said that "The addition and multiplication functions perform addition and multiplication operations in rings and fields. For groups of points on an elliptic curve, such as the G1 and G2 groups associated with pairings, both addition and multiplication represent the group operation (and similarly both 0 and 1 represent the identity element). It is recommended that programs choose and one convention and stick with it to avoid confusion." (http://crypto.stanford.edu/pbc/manual/ch04s04.html).

So, the operation you are talking about is not well defined.


What is a u-coordinate within Elliptic Curve Diffie-Hellman using the Montgomery ladder

Montgomery form and ladder

People are typically introduced to elliptic curves in Weierstrass form, namely the points $(x,y)$ that satisfy $y^2 = x^3 + ax + b$. Specifying $a$ and $b$ pick out a particular curve.

There is an alternative representation of elliptic curves, called the Montgomery form:

$Bv^2 = u^3 + Au^2 + u$

Peter Montgomery introduced this form in his 1987 paper. Here, the points are $(u,v)$ pairs and specifying $A$ and $B$ pick out a curve. You can convert from one form to the other. The $u$ here is the u-coordinate you referred to.

Why is this useful?

When doing scalar multiplication on elliptic curves over a field $\mathbb{F}_p$, you have to do a lot of modular divisons / inverses. However, in Montgomery form, $u$ and $v$ are projective coordinates. What this gets you is letting you postpone expensive division operations for as long as possible, giving nice speedups. So think of $u$ as a ratio of two coordinates, similar to (not equal to!) $x/y$.

Very roughly, the Montgomery ladder is doing a "double-and-add" operation on a point in projective space. The input to the ladder is a scale factor $k$ and the u-coordinate, and the output is only the u-coordinate of the scaled point. That's why the Montgomery ladder is called a single-coordinate ladder. If necessary and if you have both $u$ and $v$, you can compute both coordinates of the scaled point, but if you only need the scaled $u$, you get this quickly without having to spend time computing the "baggage" of the other coordinate, like with point compression and decompression.

Point Compression and Decompression

See Section 2.3 for a description of the calculation to do point compression and decompression. The basic idea is it's better to carry one number around than two if you can, so take $(u,v)$ in projective space and combine the two coordinates into a "compressed" value $\tau$ which can later be "decompressed" into $(u,v)$ or $(x,y)$ form. These compression and decompression operations involve taking modular square roots and modular inversion which are expensive. The Montgomery ladder lets you avoid this computation.


What is the likely cause the RSA algorithm gives back plain text in this case?

The question is about the "cycling attack" against RSA. The attack needs to be considered, in principle, for any deterministic asymmetric cipher with the same input and output domain, including RSA (without padding): the attacker repeatedly encrypts the ciphertext, until she obtains the ciphertext again; the last value enciphered is the plaintext.

This is discussed in the paper Are Strong Primes Needed for RSA? by Ronald L. Rivest and Robert D. Silverman. They conclude that it simply does not work in practice: "Cycling attacks are extremely unlikely to be effective as long as the primes used are large. Indeed even probabilistic factoring attacks will succeed much more quickly and with higher probability than cycling attacks".

Hence the answer to the question is in practice: the RSA key is not the product of big-enough random-like primes with proper relation to $e$; or/and the input to the RSA exponentiation is not a random-like integer, but rather crafted with knowledge of the factors of $n$, implying that RSA is used without proper padding. Any of these would be Real Bad.


Yes, however I believe that the reason is a bit subtler than what fgrieu gave.

From your question, I don't believe that you're actually doing standard ECIES, but instead something such as NaCl's cryptobox (which is a variant).

With standard ECIES, to encrypt to the public key $A$, the encryptor selects a random value $r$, and generates the ciphertext:

$$rG, \text{Encrypt}( rA, \text{Message} )$$

In contrast, with Cryptobox, Bob doesn't select a random value, instead, he uses his own private key.  That is, to encrypt to Alice's public key $A$, he will take his private key $b$, and produce [1]:

$$\text{Encrypt}( bA, \text{Message} )$$

This is effectively ECIES (with the $bG$ value implicit; that's Bob's public key).  As Bob's private key is random (independent of Alice's keys), this is secure as long as standard ECIES is secure [2].

However, this raises the question: what if Alice encrypts to herself?  Will that remain secure?  That would not immediately follow from the security of ECIES, as Alice's private key is not a random value independent of Alice's public key.

In this specific case, it turns out to be secure.  Specifically, the problem of "given $G, aG$, compute $(a^2)G$" (which is needed to decrypt Alice's message to herself) is just as hard as the general problem "given $G, aG, bG$, compute $(ab)G$".  That is, given a way to solve one, you can solve the other.

[1]: Actually, I believe Bob includes a nonce to make the encryption nondetermanistic; that's not important for this explination

[2]: Actually, we need to assume that this construction doesn't leak information about Bob's private key, and that ECIES is secure even if you repeat the same random value; that's actually the case.


Determining the secret using the Blakley's scheme?

I don't see any problem with your matrix, it is invertible.

Once you've setup the matrix, you can work out the solution of your system. Just don't forget you are working modulo 87, so:

$$
\begin{aligned}&
\begin{pmatrix}
    7       & 84 & -1  \\
    17       & 5 & -1  \\
    37   & 46 & -1
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} -41 \\ -3 \\ -66 \end{pmatrix}
\pmod{87} \\
\equiv&
\begin{pmatrix}
    7       & 84 & 86  \\
    17       & 5 & 86  \\
    37   & 46 & 86
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} 46 \\ 84 \\ 21\end{pmatrix}
\pmod{87}
\end{aligned}
$$

And for example the inverse of $5 \bmod{87}$ is $35$, so I would multiply $\bmod{87}$ the second row with $35$ to get a $1$ in the second column:
$$\begin{pmatrix}
    7       & 84 & 86  \\
    \color{red}{73}       & \color{red}{1} & \color{red}{52}  \\
    37   & 46 & 86
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} 46 \\ \color{red}{69} \\ 21\end{pmatrix}
\pmod{87}$$

As mentioned, since the matrix has an invertible determinant $\bmod{87}$, the matrix is invertible, so if there is a solution (don't worry, there is one), you can find it using Gaussian Elimination, I think you should try it too, until you obtain in the end a system of the form:
$$
\begin{pmatrix}
    1   & 0 & 0  \\
    0   & 1 & 0  \\
    0   & 0 & 1
\end{pmatrix}
\begin{pmatrix} x_{0} \\ y_{0} \\ z_{0} \end{pmatrix}
\equiv
\begin{pmatrix} ?? \\ ?? \\ ??\end{pmatrix}
\pmod{87}
$$

PS: Note that the rank's theorem for a matrix does not exist in a commutative ring.


Why is DDH not hard over $\mathbb{Z}^*_p$?

If the DDH is hard in a group $G$ with generator $g$, then it is hard to decide given $(g,g^a,g^b,g^c)$ whether $ab\equiv c\pmod{ord(G)}$.
If you take as $G$ the group $Z_p^*$ of order $p-1$ with $p$ being prime, then you will have $(p-1)/2$ elements being quadratic residues ($QR$) and the other half being non-quadratic residues ($QNR$).
Now, we know that $QR\cdot QR = QR$, $QNR\cdot QNR = NQR$ and $QR \cdot QNR = QR$, where the $\cdot$ operator has the effect $g^a \cdot g^b = g^{ab}$. These identities hold trivially as a QR would be of the form $g^{2k}$ where $k\in \mathbb{Z}$, and so $g^{2k} \cdot g^b = g^{2(kb)}$ which is a QR.
So given a tuple $(g,g^a,g^b,g^c)$, we can check for $g^a$, $g^b$ and $g^c$ whether they are $QR$ or $QNR$, i.e., compute their Legendre symbol.
Note that if this is a valid DDH tuple then you can write it as $(g^a,g^b,g^{ab})$ and if you encounter the cases $(QR,QR,QNR)$, $(QNR,QR,NQR)$, $(QR,QNR,NQR)$ or $(QNR,QNR,QR)$ then it cannot be the case that $ab\equiv c\pmod{p}$, which gives you a distinguisher for the DDH.
More formally, the DDH problem is only hard if for $x, y, z \in G$ we have
$$
|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)|\leq \text{negl}(l)
$$
An adversary $\mathcal{A}$ can adopt the following tactic: check if for the provided $g^a, g^b, g^c$ the above QR/NQR identities hold. If they do, then output $1$. Otherwise, output $0$.
Note that $P(g^x = QR) = 1/2$ for a random $x\in G$. Hence, according to the above identities, the probability of $g^{ab}$ being QR is $3/4$ (which is also the probability of either $g^a$ or $g^b$ being QR). The probabilities above then become:
$$
\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^{xy}) = 1) = 1
$$
$$
\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^x, g^y, g^z) = 1) = \frac{3}{4}\times\frac{1}{2} + \frac{1}{4}\times\frac{1}{2} = \frac{1}{2}
$$
as a valid DH tuple will always obey the QR/NQR identities. Meanwhile, if $z \neq xy$, then the adversary outputs $1$ if by chance the tuple agrees with the identities (so the probability is [prob that either $g^a$ or $g^b$ is QR AND $g^c$ is QR] OR [the same thing with NQR]).
Hence, $|\mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^c) = 1) - \mathbb{P}(\mathcal{A}(\mathbb{G}, q, g, g^a, g^b, g^{ab}) = 1)| = \frac{1}{2} \nleq \text{negl}(l)$ so the problem is not hard, formally.
If you choose $p$ to be a safe-prime, i.e., of the form $p=2q+1$ with $q$ also prime, however, and you work in the prime order $q$ subgroup, the DDH is hard (then you work in the subgroup of quadratic residues and you will no longer have the above approach to construct a distinguisher)!
An algebraic group commonly used in application of the Diffie-Hellman problem are Schnorr Groups. These are subgroups of $\mathbb{Z}_p^*$ and have the form $G_S = \{h^r \text{ mod } p\ |\ h \in \mathbb{Z}_p^*\}$ where $p=rq + 1$ and $p,q$ are primes. It then follows that the order of the group is $q = (p-1)/r$.
Note that in this case $p,q$ are necessarily odd (aside from the trivial case of $q=2$), which means that $r=2s$ for some $s\in \mathbb{N}$ (ie $r$ is even). This means that all elements are quadratic residuals in $\mathbb{Z}_p^*$ and hence the above distinguisher would not be applicable.
Moreover, a similar attack on DDH can be constructed for cubic, quartic, etc. residuals. Formally, you can construct such a distinguisher for any $k$th residual given $k$ divides the group order. The group order for $\mathbb{Z}_p^*$ where $p=rq+1$, as outlined above, is $p-1 = rq$. Hence, we need to check for $r$th residuals (which don't give any discrimination power as all elements of the subgroup $G_S$ are $r$th residuals) and for $q$ residuals (which aren't useful as that only includes $1$ due to $q$ being prime).
Schnorr groups are selected such that $p\gg q$, resulting in $r$ being big and having a lot of prime factors, making any sort of $k$th residual attack have negligible chances of success for reasons outlined above. Though $k$th residual attacks for large $k$s quickly stop giving any noticeable discrimination power.
But the DDH is not the hardness assumption underlying Diffie-Hellman key exchange, but it relies on the CDHP, i.e., given $(g,g^a,g^b)$ compute $g^{ab}$, which is hard in $Z_p^*$ for appropriate choice of $p$. This is the problem an eavesdropper is faced when it intercepts $g^a$ and $g^b$ to compute the common key $g^{ab}$. Note that an eavesdropper against Diffie-Hellman key exchange will hopefully never see an DDH tuple $(g^a,g^b,g^{ab})$ as otherwise this would mean that the parties would send the exchanged key $g^{ab}$ in clear over the wire, and this would not be a good idea ;)


Why is it better to add and double points on an elliptic curve using projective space?

Is there any specific reason why we want to express points of the elliptic curve in projective space? Does it make adding two points or doubling a point easier?

Because it is a lot more efficient.

If you take a look at the operations involved in performing an elliptic curve operation on a prime curve, they are:

Modular addition and subtraction
Modular multiplication
Modular inversion, that is, given $a$, find $b$ such that $a \cdot b \equiv 1 \pmod p$

It turns out that modular addition and subtraction is fast, modular multiplication is somewhat slower, and modular inverse is dreadfully slow.

And, if we do everything using affine coordinates, it turns out that we need to do a modular inversion for every point addition or doubling.

In contrast, if we do things using projective coordinates, it turns out that we don't need to compute any inverses at all (we do increase the number of modular additions and multiplications we need, however the time involved there is much less than doing a single modular inversion, and so it is a win).

Now, at the end, we'll need to convert back to affine coordinates; that involves a single modular inversion; however when we do a point multiplication, that means that we replaced several hundred modular inversions with just one - a definite win.


I believe that the meaning is "compute the $2n$-bit value $a[j]*b[0] + C$, and then assign the top $n$ bits to $C$ and the bottom $n$ bits into $S$


How to check that you got the right key when brute forcing an encryption?

First, you do not break RSA through brute force. RSA is an asymmetric encryption algorithm, with a public/private key pair. The public key has a strong internal structure, and unravelling it yields access to the private key (basically, the main component of the public key is the modulus, which is a big composite integer, and the private key is equivalent to the knowledge of the prime factors of the modulus). This can be done a lot more efficiently than trying out possible private keys; in fact, trying prime factors one at a time is a method known as trial division, and is about the least efficient of all integer factorization methods.

The bottom-line is that the attacker perfectly knows when he has found the private key, and he does not need to see any encrypted text for that.

Now let's suppose that you are not talking about RSA encryption, but a symmetric encryption algorithm such as AES. In that case, your question makes more sense, because:

In a symmetric encryption algorithm, there is no public key to work with, so the attack must proceed from some intercepted ciphertexts.
In symmetric encryption algorithms (at least the "secure" ones), the best known attack method is, indeed, brute force. Brute force is the generic method that necessarily works (at least in theory -- in practice we use keys that are large enough to make it totally infeasible); an encryption algorithm is said to be secure if no better attack method is known.

Enigma uses as input and output sequences of latin letters -- the 26 letters from 'A' to 'Z'. Modern encryption systems work on bits and octets, i.e. "binary data". If you cascade AES with Enigma, then you need some conventional representations of letters into bits, e.g. ASCII. You would, for example, map each letter of the Enigma output into an 8-bit byte, to be used as input to AES. Since 26 is not a power of two, it is unavoidable that this mapping will have "holes": there necessarily are some sequences of bits that could be a valid AES input, but are not possible as an encoded Enigma output.

This thus yields a valid strategy for our attacker: for each possible AES key, decrypt the AES layer, and see if the result is a valid encoded Enigma output. If not, the AES key is wrong, and proceed with the next one. If you used ASCII encoding, then a 16-byte output from AES decryption is a valid Enigma output encoding only with probability 1 in 7803076729492126.75 (approximatively). This comes from the fact that there are 25616 possible sequences of 16 bytes, but only 2616 possible sequences of 16 uppercase letters. This is an awful lot of power of recognition of bad keys by the attacker. If the attacker has access to two encrypted blocks (32 bytes, corresponding to 32 characters of Enigma output), then he will be able to pinpoint the single AES key that "makes sense". In all of this, the attacker never has to even begin to consider how he will break through the Enigma.

Of course, the above is quite artificial. You may imagine cascading algorithms that live in the same world; e.g. two symmetric encryption algorithms that both work over bits.

Cascading algorithms is a method of construction of bigger encryption algorithms. It is not a very good one, though. For instance, suppose that you cascade AES with another block cipher such as Serpent; or maybe you use two AES instances with two keys chosen independently. The hope may be to thereby produce a synthetic block cipher that will have twice the key length. But it does not deliver all these promises: the double-encryption method falls prey to the Meet-in-the-Middle attack (not to be confused with the unrelated Man-in-the-Middle attack). This schema may be enlightening:

So, by cascading two algorithms, you double the operational cost, but you do not get your money worth in security increase. To really get extra security, you must go to triple-encryption. This is why Triple-DES is triple-DES, not double-DES: the latter would not be substantially stronger than simple-DES.

It still is much simpler not to use weak algorithms at all. If you cascade AES with anything else, then either the "anything else" is completely useless, because the AES is already strong enough to defeat brute force attacks; or you use the AES really poorly and that is what you should fix first.


The attack on 3 rounds is deterministic. It is extended to 4 rounds in a probabilistic manner, which is the normal way of carrying out differential cryptanalysis, see for example Heys' tutorial on linear and differential cryptanalysis which is easy to find online and uses a simple toy cipher to explain these concepts.

Basically, given enough input output pairs, one can use the fact that those differences will statistically dominate. Scan through a set of subkey bit patterns and declare the subkey bit pattern which leads to the most biased output difference distribution as the correct key bit pattern.


What is a purpose of reducing lattice basis?

Lattice Reductions in Lattice Crypto

Well to start off, lattice reductions are of interest in the context of lattice crypto because, as already stated in other answers, they allow us to find short vectors in a lattice, which relates to SVP (finding the shortest vector in a lattice).

We care about solving SVP because it is believed that there may be a security reduction from Ring Learning With Errors (RLWE) to SVP. So if we can solve SVP (via some technique e.g. lattice reduction) we may be able to break schemes based on RLWE e.g. these homomorphic encryption and key exchange schemes.

It should be noted that reduction techniques such as LLL do not allow us to solve SVP efficiently for lattices in a high dimension and as such they are not effective for breaking these schemes.

Lattice Reductions in Number Theoretic Crypto

But there's also an application to "classical" number theoretic crypto. I'll explain one (of several) possible applications. Suppose we want to attack (EC)DSA where nonces are generated with biased bits. It turns out we can use a lattice reduction to recover the private signing key.

If we can get enough message/signature pairs that all used nonces with the same bias then we can actually write a system of equations (with each equation corresponding to a message/signature pair) that can be interpreted as a lattice (just like how you can might use an augmented matrix in linear algebra to represent a system of equations).

We can then actually perform a lattice reduction (e.g. LLL) on this system of equations. If we have sufficient message/signature pairs then with high probability one of the entries in the reduced basis will be the private signing key. The details of this attack can be found in this paper.

For more information on lattice reductions in this context I'd encourage you to look at the paper Lattice Reduction: a Toolbox for the
Cryptanalyst.


How to renew keys for a statically-encrypted database

Some remarks:

a 16 byte IV is required by CBC, but you may not require a 128 bit unique value for your protocol
CBC relies on an IV that is indistinguishable from random to an attacker, fixing bits in the IV is not a good idea
CBC requires a padding mechanism, unless you can use ciphertext stealing

Now a few calculations reveal that if you rely on the non-repeating counter, that you need an number of 8 bytes to have enough precision (584 years should be enough). Store just this number. You can create a good IV from this number by pre-pending the number with zero's and performing a single block encrypt (in the black box of course).

Now you have got 8 bytes left. I would suggest you use these for the key indicator (make it one byte instead of 1 bit, to avoid key management issues later on). You could use the additional 7 bytes for storing an authentication tag, so that nobody can change the ciphertext (and thus the PAN) unnoticed.

Finally note that the "default" padding mode for CBC mode of operation, PKCS#7 padding mode, will use 1 to 16 additional bytes of overhead. This is overhead you can sorely miss on size constrained systems, especially since it can be avoided without penalties on the security of the protocol. Look up ciphertext stealing, or go with another mode of operation that does not require padding.

This answer is provided as is. I remain convinced that you should hire a consultant that has experience protecting credit card related data.


Difference between one-way encryption, Transparent data encryption (TDE) and data encryption

You are right that "one-way" thing is hash function, and in fact, it's not encryption at all! Password hashing is different from data/file hashing in that data/file hashing algorithms like SHA-256 are deterministic and (supposedly) efficient; whereas password hashing is in practice non-deterministic so as to deter various types of precomputation attacks.

The difference you'll encounter with transparent data encryption and data encryption, is that TDE don't need you to rewrite your application to enjoy the benefit brought by encryption, where as data encryption on its own, requires processing data using cipher functions. Hence the name "transparent" data encryption.

That's all you have to know for now, you're welcome to learn more if you can get your head around it.


Digital signatures in SSL/TLS-like protocols

So what you are doing here are two Diffie-Hellman key exchanges in parallel – one with the server's static Diffie-Hellman key pair $(x,y)$ and the client's ephemeral key pair $(a,A)$ to calculate $k = k'$, and one with completely ephemeral keys to calculate the actual pre_master_secret. $k$ is only used as a MAC key to authenticate the server's exchange message.

  Presume the client $C$ and server $S$ share a set of parameters defining
  a group $G$, suitable for Diffie Hellman, and that $C$ already has the
  public key $y≡g^x∈G$ of the server.

This second condition is not realistic in many circumstances – i.e. not for the normal WWW usage, where you often want to connect to a server you don't know beforehand.

In this case we would then use the same way as now – deliver the server's public key $y$ together with a certificate (chain) which proves that the key belongs actually to the server we want to connect to.
To check these certificates, the client would need to implement a signature verification algorithm anyways. The existing DH_DSS and DH_RSS key exchange types work just this way, by the way, for their static Diffie-Hellman key (but there is just one exchange, not two).

Then, how could we fit this into the TLS handshake protocol?
We have these messages sent by the participants:

  Client                                               Server

  ClientHello                  -------->
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               <--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     -------->
                                           [ChangeCipherSpec]
                               <--------             Finished
  Application Data             <------->     Application Data

The ClientHello message doesn't really have space for the messages $A$ and $V$ to be sent – even less since at this point the cipher suite isn't even selected.
We could put something in the Extensions part, but I think this is not what they were made for.

The server's next bunch of messages has the selection of the Cipher Suite (including the key exchange protocol) in the ServerHello, so from here one the server can send related messages. So here we would send the server's static public DH key $y$ in the Certificate message (inside a certificate).

The client would then send in its ClientKeyExchange its two public keys $A$ and $V$.

We now see the problem: There is no more place for the next message from the server where he would send $U$ and $H$, since the Finished messages are more or less only a MAC of the handshake messages with the master secret as a key, and the client's Finished is even sent before the server one's (and already encrypted with the negotiated keys).

But if we look again more detailed, we see that actually $U$ is not depending on anything what the client sent us, so the server can send it already in the first step, in the ServerKeyExchange message, just after $y$ and its certificate.

Sending $H$ (the MAC for $U$ using $k$ as a key) is not really necessary, as the Finished message from the server side has a similar function. What would be necessary instead would be to incorporate $k$ (i.e. the server's certified DH key pair) somehow into the pre_master_secret. Simple concatenation of $V^u = U^v$ and $k = k'$ should do here (the master secret is then derived using a PRF, including the random values from the Hello messages).

So the final key exchange protocol would look like this (omitting the stuff which is not relevant for the actual key exchange, like ClientHello, ServerHello, ServerHelloDone):

$S$:

send $y = g^x$ (with certificates) in Certificate,
send $U = g^u$ in ServerKeyExchange.

$C$:

check certificates for $y$,
send $A = g^a$, $V = g^v$ in ClientKeyExchange,
calculate $P = y^a||U^v$, $M = PRF(P, …)$ (this is the master secret),
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_C = PRF(M, C, …)$ in Finished.

$S$:

calculate $P' = A^x||V^u$, $M' = PRF(P, …)$, $F_C' = PRF(M', C, …)$,
check $F_C \stackrel{?}= F_C'$,
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_S' = PRF(M', S, …)$ in Finished.

$C$:

calculate $F_S = PRF(M, S, …)$
check $F_S \stackrel?= F_S'$.
Start sending application data.

This actually is a hybrid between the DH_anon and the DH_* key exchange types. And if the server's public key is already known to the client, we can omit the Certificate message and/or the certificate checking.

  Is there any other reason to use a digital signature in the
  Server Key Exchange message, than the order of the protocol
  steps being put there because it wouldn't matter much for
  DHE_RSA how it is done (digital signature in Server Key Exchange
  or an extra key transport message sent by the client earlier)?

The DHE_RSA and DHE_DSS key exchange protocol needs a signature in the Server Key Exchange message, since there is no other way for the client to verify that the message (and the public DH key) actually comes from the right server. In the DH_RSA and DH_DSS key exchange protocols, instead the (static) public key is contained in the server's certificate (which itself also contains a signature, but usually one created long before).

In our new protocol (i.e. my variant of your protocol), we don't need a signature, and still succeeded to fit it into the TLS handshake order.


Finding a $Z$ is easy. This condition is fulfilled for all $Z>n/2$, and most of the smaller values of $Z$ too. There are only a few values fulfilling the condition for $Y$, and since this is almost the negation of the condition for $Y$, most numbers will fulfill it.

When looking at the condition for $Y$, you can model $Y^d \mod N$ as a random number between 0 and $N$.
This leads to a success chance of approximately $ 1/Y $.

Thus a good strategy for finding a $Y$ is starting with $ Y = 2 $ and incrementing by one on each attempt, i.e. trying 2, 3, 4,... This should find a number fulfilling $ (Y^d \mod N) \cdot Y < N $ quite quickly.

Total chance of finding an $ Y \le n$ is:

$1-\Pi^n_{i=2}(1-1/i) = $

$1 - \frac{(n-1)!}{n!} = $

$ 1- 1/n $

Which quickly converges to 1


The question's bytestring 2a 86 48 86 f7 0d 01 01 01 is the Value field of an ASN.1 BER/DER TLV with type 6, which is the Object IDentifier for an RSA key (the Type and Length just before are coded as 06 09, and won't be further discussed).
In order to parse that Value bytestring, we first separate the bytes into blocks ending after each byte in which the high-order bit is clear (in other words: blocks end after a byte in range 00h to 7fh). Then we paste together the low-order 7 bits of the bytes (in big-endian/reading order); so that
_____2a|_____86_____48|_____86_____f7_____0d|_____01|_____01|_____01   becomes
0101010|00001101001000|000011011101110001101|0000001|0000001|0000001
We then interpret each block of bits as coding a non-negative integer in big-endian binary. The question's example now comes out as the six integers: 42 840 113549 1 1 1
There's a special case for the first integer: it was built as $z=40x+y$, with $x$ encoding the top-level authority that assigned $y$. Integer $x$ is always one of $0$ (for ccitt), $1$ (for iso) or $2$ (for joint-iso-ccitt), and if $x<2$ then $y<40$.
We thus replace the first integer $z$ by $x=\min(\lfloor z/40\rfloor,2)$ and $y=z-40x$.
Note: when $x=2$, $y$ can be arbitrarily large. Assigned $y$ include 40 (exercising the $\min$ rule), 48 (requiring coding $z$ over more than one byte), and 999 (with $y\ge2^8$), which might not be correctly handled by some existing software.
The question's example now comes out as the seven integers: 1 2 840 113549 1 1 1
One practice is to format these integers in decimal without a leading 0 digit (with the exception of the integer zero represented as 0), separated by dots, as in
1.2.840.113549.1.1.1
or sometimes enclosed in braces with separating spaces, as in
{1 2 840 113549 1 1 1}
or sometimes (as shown by the OID Repository)
{iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}
or in OID-IRI notation
/ISO/Member-Body/840/113549/1/1/1
The careful reader will notice that per the above conventions, different bytestrings can decode to the same OID; however the rule in crypto (for OIDs at least) is to stick to the unique DER encoding, such that (in the bitstring with the Value field of an OID) a byte 80h can only follow a byte which high-order bit is set (otherwise the 80h would encode leading zeroes of an integer, and must be suppressed).

Daniel Marschall's Study about OID encoding and size limitations was most useful in making the above (hopefully) correct; it also confirmed my intuition that OID decoding practices are chaotic. Microsoft has an explanation on OID format, which I found initially useful even though it turns out to be dangerously lacking.
The normative references for OID encoding are somewhere in IUT-T X.680 through X.695 Information Technology - Abstract Syntax Notation One (ASN.1) & ASN.1 encoding rules. They are also in its free ancestors IUT-T X.209:1988 Specification of Basic Encoding Rules for Abstract Syntax Notation One (ASN.1) in section 22 Encoding of an object identifier value, with definitions in IUT-T X.208:1988 Specification of Abstract Syntax Notation One (ASN.1) in section 28 Notation for the object identifier type and annexes B, C and D.


What are the security effects of reusing a public RSA key to encrypt large data by blocks?

I assume that by

  I want one side to do the encrypting but is unable to decrypt the data

you meant a general "encrypting only" party, since if you are talking about a specific piece of data, it does not make sense to disallow the encrypting party from decrypting that data since that party had the data already in the clear.

If that is the case, then your goal might be achieved by first encrypting the data with a symmetric algorithm like AES, which can do big data rather efficiently, and then encrypt the symmetric key/PW with the RSA algorithm. That way, only the other party, who has the private key for the RSA algorithm, can decrypt the RSA-protected symmetric key and then proceed to decrypt the big data.


Do I have to know RSA padding scheme in advance when verifying signature with EVP_Verify*?

For this answer I'll be focussing on solely on RSA (the RSA tag is present, so I'll suppose that this question is just about RSA). It is also the most likely signature scheme that requires padding, I suppose.

TL;DR: you don't just need to know the padding scheme in advance, but also the other configuration options to be used, such as data hash method and MGF1 (configured with it's own hash), salt and label for PSS.

Yes, the padding scheme is something that needs to be known in advance during verification and of course signature generation. There is no easy way of verifying which padding scheme is used from within most signature schemes without first performing modular exponentiation yourself, after all.

If you'd allow both PKCS#1 v1.5 padding for signature generation and PSS during verification (and rely on the verification result to be true for either one of them) then your verification may fail if a successful attack is launched on either one of the two schemes. Besides that, it would require you to perform the signature generation twice.

The same goes for hash functions, where the acceptance of a hash from a weaker hash function may lead to insecurities. Even if these kind of insecurities are not directly visible or possible, in general the security proofs of the algorithms generally do now allow the key to be used for different schemes.

Sometimes there are indications that using keys for different schemes is problematic. E.g. for PSS the following can be found in PKCS#1 v2.2:

  This encoding method is parameterized by the choice of hash function,
     mask generation function, and salt length. These options should be
     fixed for a given RSA key, except that the salt length can be
     variable (see [JONSSON] for discussion).

Similarly, the withdrawn ISO 9796 specifications for signatures giving message recovery make it explicit that the configuration options need to be known in advance. It contains a section with three options in that respect:

  Use of the signature schemes specified in this standard requires the selection of a collision-resistant hash-function h. There shall be a binding between the signature mechanism and the hash-function in use. Without such a binding, an adversary might claim the use of a weak hash-function (and not the actual one) and therebyforge a signature.NOTE 1There are various ways to accomplish this binding. The following options are listed in order of increasing risk.

  Require a particular hash-function when using a particular signature mechanism. The verification process shallexclusively use that particular hash-function. ISO/IEC 14888-3 gives an example of this option where the DSAmechanism requires the use of Dedicated Hash-function 3 from ISO/IEC 10118-3 (otherwise known as SHA-1).
  Allow a set of hash-functions and explicitly indicate the hash-function in use in the certificate domain parameters.Inside the certificate domain, the verification process shall exclusively use the hash-function indicated in the certificate.Outside the certificate domain, there is a risk arising from certification authorities (CAs) that may not adhere to theuserís policy. If, for example, an external CA creates a certificate permitting other hash-functions, then signatureforgery problems may arise. In such a case a misled verifier may be in dispute with the CA that produced the othercertificate.
  Allow a set of hash-functions and indicate the hash-function in use by some other method, e.g., an indication in themessage or a bilateral agreement. The verification process shall exclusively use the hash-function indicated by theother method. However, there is a risk that an adversary may forge a signature using another hash-function.

I've included this mainly to show that when it comes to calling signature verification methods that the configuration options of the signature functions need to be known in advance. It makes sense that the signature algorithm itself and padding method should then also be known in advance.

For debugging or reverse engineering the methods used, it makes sense to perform modular exponentiation first. For PKCS#1 v1.5 padding the padding bytes will be immediately identifiable. If it just looks like random data then you are most likely dealing with a PSS signature scheme. Generally you can distinguish various initial and trailing bytes of the padding method as well. Unfortunately many different padding methods have been used in the past, more than you might imagine.


Why should one prefer Salsa20 over ChaCha?

I agree that conservatism is the likely reason for the choice in McBits.

ChaCha was published while eSTREAM was still running. Salsa20/12 is now in the final eSTREAM portfolio. Even in the XSalsa paper on constructing a larger nonce, Bernstein makes no mention of ChaCha.

  So what are the reasons to prefer Salsa20 over ChaCha?

Wanting to use a standardized algorithm is one reason. Choosing the more exhaustively studied algorithm is another good one.

If you have your tinfoil hat on, you might also prefer to avoid any tweaks in the absence of real breaks. After all, tweaking the cipher would be an opportunity to introduce new back doors.


How hard is the following q-Strong Diffie-Hellman problem?

So I found that [1][2] shows that the hard assumption of the following problem holds in generic bilinear groups.

  $\ell$-BDHE problem: given $(h, g, g^{\alpha}, g^{(\alpha^2)}, \dots, g^{(\alpha^\ell)}, g^{(\alpha^{\ell+2})}, \dots, g^{(\alpha^{2\ell})}) \in \mathbb{G}^{2\ell+1}$, output $e(g,h)^{(\alpha^{\ell+1})} \in \mathbb{G}_T$.

And it is trivial to see that $\ell$-BDHE can be reduced to the problem described in the question.

However, I am still wonder whether there is a better reduction without introducing bilinear pairing.

Update: It seems that [3] uses the same technique as the one in the above to prove the hardness.

[1] Hierarchical Identity Based Encryption with Constant Size Ciphertext

[2] Collusion Resistant Broadcast Encryption With Short Ciphertexts and Private Keys

[3] An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials


I'd say the key thing that you need to spell out to answer this question is this:

What information does the attacker have?

This ties to one of the basic concepts of cryptography, called Kerckhoffs's principle: "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."  (I recommend you read that page and take its lessons to heart, along with the security through obscurity entry as well.)

So if we apply Kerckhoffs's principle to your proposal, we would assume that:

The attacker knows that your password is the hash of some secret word that you choose, but not which word;
The attacker knows which hash function you used to hash this word, and how to compute this hash function.

Then we trivially conclude that this isn't any safer than just using the word as the password.  And since "dog" is a very common word in the English language, it's an obvious one for an automated attacker to try.

I'd say that in your question you are doing something that most laypersons do when they propose password rules or schemes like this one: you're assuming that the attacker won't know or guess the rule you're using to generate your password.  But:

You just told your idea to the whole Internet.
Even if you hadn't, there's a good chance that an attacker might think of the same idea.

So really, the best passwords are random passwords, because there's no rule that an attacker can use to predict them.

EDIT: Funnily enough, a few days before this question, Duo Labs published a security analysis of OEM PC software updaters (press release; PDF report), that contains this gem (p. 16):

  Unfortunately, the encryption utilized is RC4 with the pre-shared key “e8fded24af79202d7da48adefe4a3a04”, which is the MD5 hash for “Asus Live Update.” As this layer of encryption boils down to simple obfuscation that can be dealt with on the fly, it provides no security value.

This is almost perfectly analogous to the question's proposal:

Pick a secret passphrase ("Asus Live Update");
Hash it with a standard hash function;
Use the resulting hash value as an encryption key.

And yet the researchers, just from seeing the hashed value, managed to guess the passphrase and the hash function used to obfuscate it.  So there we have it, a documented real-life failure of the strategy.


Algorithm for Boneh and Durfee attack on RSA

Our goal is to find a root $(x_0,y_0)$ in $\mathbb{Z}_e$ of the polynomial $f(x,y) = x(A+y)-1$. Finding roots of a polynomial in any $\mathbb{Z}_n$ isn't an easy job, in order to solve the problem Coppersmith had the idea to reduce to problem to finding a root $(x_0,y_0)$ over $\mathbb{Q}$ of some other polynomial $f'$ related to $f$.

About Coppersmith method

His technique relies on building a lattice $\mathcal{L}$ whose entries are coefficients of some polynomials (x and y shifts) having the same root $(x_0,y_0)$ as $f$. Thanks to this property, every linear combination of x and y shifts will be solved by $(x_0,y_0)$. Once $\mathcal{L}$ is built, it can be reduced using LLL algorithm (the same matrix is represented in a different basis, computationally easier to manage due to small coefficients) and from that get two polynomials $g_1,g_2$ (as linear combinations of $\mathcal{L}$ elements) such that $g_1(x_0,y_0) = g_2(x_0,y_0) = 0$.

Why x and y shifts?

First of all, let's define what a shift is. Those are derived from different powers of $x$, $y$, $f$ and $e$. $g_{i,\phi}$ and $h_{j,\phi}$ are respectively $x$ and $y$ shifts:

$$g_{i,\phi}(x,y)=x^i f^{\phi} e^{m-\phi}$$
$$h_{j,\phi}(x,y)=y^j f^{\phi} e^{m-\phi}$$

Where $\phi \in (0,m)$, $i \in (0,m-\phi)$ and $j \in (0,t)$. Once $m$ is defined, it's easy to compute the set of shifts. Indeed, $m$ is the maximum degree of $x$ in shifts, whereas $t+m$ is the maximum degree of $y$.

That's all we needed: a bunch of polynomials (up to a certain degree) having the same root as $f$.


From your equations, one can write:
\begin{eqnarray*}
x + a_1 &=& \frac{1}{y_1} \mod \phi(n) \\
x + a_2 &=& \frac{1}{y_2} \mod \phi(n) \\
\end{eqnarray*}
and thus:
\begin{eqnarray*}
a_1 - a_2 &=& \frac{1}{y_1} - \frac{1}{y_2} \mod \phi(n) \\
\end{eqnarray*}
which leads to:
\begin{eqnarray*}
(a_1 - a_2) y_1 y_2 - y_2 + y_1 &=& 0 \mod \phi(n) \\
\end{eqnarray*}

Therefore, one can compute $f = (a_1 - a_2) y_1 y_2 - y_2 + y_1$, and the equation above tells you that $f$ is a multiple of $\phi(n)$. At that point, you can take a random prime integer $e$ which is relatively prime to $f$ (take a random prime $e$, compute the GCD with $f$; if it is distinct from $1$, start again with a new random prime). This value $e$ will be "an RSA public exponent". You can then compute $d = e^{-1} \bmod f$, i.e. the corresponding "RSA private exponent".

Given a pair of public/private exponents $(d,e)$, one can factor the modulus $n$, using the method described here (a more formal reference is Dan Boneh's Twenty Years of Attacks on the RSA Cryptosystem). Once $n$ is factored, you then compute $phi(n)$, at which point you can recover $x = y_1^{-1} - a_1 \bmod \phi(n)$.


Application of cryptographic hash functions which do not require collision resistance property

The two cases for stored files/programs;

On your files/programs
In this case it is the secondary pre-image attack that is given an input $m$ and a hash value $h =Hash(m)$ find another input $\bar m$ such that $m \neq m'$ and $h = Hash(m')$. As long as the hash value $h$ is not under the control of the attackers, they need to find the second input. In this case, we don't need the collision attack that is

Collision attack is finding two inputs $a$ and $b$ with $a\neq b$ such that $Hash(a) = Hash(b)$. To have collision resistance, finding such a pair must not be lower than $\mathcal{O}(2^{n/2})$ for hash functions with $n$ bit output size for any probabilistic polynomial-time adversaries. The bound comes from the birthday attack on the hash functions.

If the attackers can control the hash value, it may be possible to use to their advantage. To prevent this we need to use a keyed hash like HMAC, KMAC.

Third-party files/programs
If you accept the files/programs from the third parties, the classic attack that uses collision of two or more files/programs works as in Luis Casillas's answer and addressed well in Squeamish Ossifrage answer with good, bad, and sneaky versions. Therefore a collision resistance is required. You can mitigate this with HMAC.

Collision resistance is not necessary all the time.

A good example is the HMAC  expanded as either keyed-hash message authentication code or hash-based message authentication code). HMAC is a PRF under the sole assumption that the compression function is a PRF [1] proved by Mihir Bellare in 2006. A PRF doesn't need to have collision resistance. And, usually, we instantiate the HMAC with good hash functions like HMAC-SHA256 or, HMAC-SHA3-256.

Another example is password hashing, although we don't use standard cryptographic hash functions since they are fast and not memory-hard functions - Scrypt, PBKDF2, or Argon2 is preferred -  they are still considered hash functions. In password hashing, the pre-image and secondary pre-image attacks are considered to be important. The collisions are not applicable in password hashing.


Quoting SEJPM's (now removed) comments:

For the convenience of any answerer, I've rendered the graph and answerers may use it (and any derivatives) at their will. If required I can also provide vector graphic versions of it.

In this case one could argue that A issued both bob's and alice's cert indirectly and thus either party seems to trust A to certify CAs and thus they trust each other's cert. (But this doesn't really sound convincing to me -> no answer)

Thanks to @SEJPM for adding the graph. With what you stated you were give, it would not be possible for Bob to verify Alice's certificate.


What are the current known weaknesses/attacks on quantum key distribution?

The Attack you mentioned (PNS) is a "hardware attack" it depends on how you physically distribute the qubits.

The only "protocol attack" (known for the BB84) is the "intercept & resend" that can be applied on every hardware you use and can be performed very easily(but Eve is easy to detect if the key is, at least, 72 bit long).

Another attack that can be performed is the man-in-the-middle, but this is not related to the protocol but to the total absence of authentication in the BB84.

This answer is focused on the BB84 protocol because of every protocol have different points of strength and weakness so "QKD in general" is a bit vague... i hope this can help you.


Is there an intuitive explanation as to why only the private key can decrypt a message encrypted with the public key?

The basic explanation is that you need both keys to make a complete encryption/decryption cycle.

Basically the encryption works with modulo arithmetic so that

$$c=m^a \mod n$$

and

$$m=c^b \mod n$$

where $a$ and $b$ are the public and private key of the algorithm. $m$ is the plain text message and $c$ s the ciphertext.

The most important thing about the formulas is

$$m=(m^a)^b \mod n = (m^b)^a \mod n$$

For this to work $a$, $b$ and $n$ must follow certain restrictions.

This is the basic idea behind RSA and other asymmetric encyption systems whereas you can make the operations more complex/different but the basic idea that using two different keys to complete the encryption/decryption cycle.


Selecting bijective functions for permutations

It depends.  There is no single answer, and no single recipe that works for all block ciphers.  The permutation is chosen to work well with the rest of the block cipher design.  Therefore, this question can't be answered in general.  A  question like "Why did cipher X use Y as its permutation?" would be more meaningful and more answerable.

For instance, some ciphers use a permutation to diffuse the bits, or to resist some kinds of attacks (e.g., algebraic attacks).  As CodesInChaos says, often one chooses a permutation that is as fast as possible and just barely good enough to meet the other requirements.


Is there a way to project one elliptic-curve element to a subgroup with certain size?

Is there a way to do something like this for elliptic curves?

Of course; if we have an elliptic curve with order $q = a \cdot b$, then we can make an element $H$ into the subgroup of order $a$ by computing $H_a = (q/a)H$.  And, we have $a H_a = 0$ (the neutral element) precisely as requested.

Now, we typically don't use elliptic curves with an order with two large prime factors; they are usually selected with an order $q = hr$, where $h$ is a small integer (most often 1, 4 or 8) and $r$ is a large prime.  We do this because that makes the ECDLP problem as hard as possible; with your order $q = a \cdot b$, you could compute discrete logs in time $\sqrt{ \max( a, b ) }$, and so we'd have to use a larger elliptic curve that we would otherwise need.


Proof that Niederreiter Cryptosystem is correct

To prove the correctness of an encryption scheme (not necessarily Niederreiter), you have to prove that for a honestly generated key pair, any honestly generated ciphertext decrypts correctly.

Formally, let $(pk, sk) \leftarrow KeyGen(1^\lambda)$ be the public and private key pair, and let $m$ be uniformally random in the (finite) plaintext space, and denote by $c \leftarrow Encrypt(pk, m)$ an encryption of message $m$ (pseudo-random in the ciphertext space) under the public key $pk$. Then you have to show that $Decrypt(sk, c) == m$ with overwhelming probability, meaning that either the decryption always succeeds if all steps were executed honestly, or it fails with probability negligible in the security parameter $\lambda$.

For instance, you prove the correctness of textbook RSA by showing that $(m^e)^d == m \bmod n$ for honestly generated $n=pq$, $\varphi(n)=(p-1)(q-1)$, $e$ coprime with $\varphi(n)$ and $d = e^{-1} \bmod \varphi(n)$.


gpg --gen-random quality level: is higher "better"?

This is a really hard question to answer. The definitive answer can only be found in the source code of gpg. However I can still answer your question using a mail I found (from 2013, details may have changed).

  Is 2 "better" (i.e. more random) than 0?

Yes, 2 is "better" than 0 and 1.
As per the linked mail the quality level determines the number of bytes being read from /dev/urandom and /dev/random for answering the query.

As it appears in the mail 0 and 1 are actually the same (this may have changed by now) and gpg will just answer your query with the requested amount of fresh bytes from /dev/urandom.

2 however is different. It uses /dev/random, meaning you have higher guarantees concerning the quality and entropy of the output (as you may have to wait some time, if this trade-off is actually worth it is another question). And more importantly it requests significantly more bytes from /dev/random than you query, namely nearly 19x as many and post-processes them somehow. So the entropy of the result is high even if /dev/random doesn't provide you with high-quality random bytes.


Algorithm complexity: $\mathcal O(n\cdot m)$ vs. $\mathcal O(max(n,m)^2)$

This type of $\mathcal{O}$ usage specific to the problem to indicate some other factor plays a role;

in Bucket sort $\mathcal{O}(n \cdot k)$, $k$ is the number of buckets
in Counting sort $\mathcal{O}(k+n)$, $k$ is the range of the inputs.

In the voting case; the $m$ represents the casted ballots, $n$ represent the candidates, and $m \gg n$.

Using $\mathcal{O}(m^2)$ may hide some important factors especially when comparing different algorithms for the same system.
When the candidates are very small, the algorithm will behave like linear. Using $\mathcal{O}(m^2)$ will hide this.

Prefer to use   $\mathcal{O}(n \cdot m)$.


What's causing the poor randomness in this program: the LCG, or the program logic itself?

Let's say I choose $m = 8192$, $a = 4801$, and $c = 83$. By looking at the value of $x$, I can learn quite a lot about the value of $y$: for any $x$, there are only about nine or ten possible subsequent $y$s, and they're very unevenly distributed.

With a LCG every $L_1$ has a single possible $L_2$, and for a maximal period the reverse is also true. With your formula each $x$ corresponds to about $m/52$ possible $L_1$, and thus $m/52$ possible $L_2$.

The form of the $L_1$ for a given $x$ is $L_1 = x + 52n$, for some $n$. Thus the $L_2$ for a given $x$ is:

$$L_2 = (52an + ax + c) \mod m$$

What you wish is for different values of $n$ to give different $L_2$, i.e. for it to be a decent LCG where $a' = 52a$ and $c' = ax + c$. Substitute $a$ and you get $a' = 3892 = 2^2 \cdot 7 \cdot 139$. For maximal period $a'-1 = 3891 = 3 \cdot 1297$ would have to be divisible by 4 (due to $m$ being), which it is not, so this will give very poor results, as you observe.

If you fixed this, e.g. by choosing another value for $m$, you would also need to consider a condition for $c'$ and how the subsequent modular reductions and addition of $x$ affect it. Also, reducing a random number from the range $0 \le x < m$ modulo 52 will always be biased towards the small numbers unless $m$ is a multiple of 52.


implementing GCM with dev/urandom for a nonce

If you are following NIST recommendations and you use a 96 bit NONCE (12 bytes), then you should be fine using a random NONCE generated by /dev/urandom. It should provide sufficient entropy for your needs.

But you'll be better off using the deterministic construction for the NONCE. It requires the NONCE to be composed of a 32 bit "fixed field" and a 64 bit counter. You can use a sequence number for your fixed field or a randomly generated string as recommended by the standard specification. As such you'll be able to do at most 264 opertions with the same key/NONCE. But then you have a hard limit on the number of operations you can process from the underlying CTR mode of operation to 232 - 2.

Another data point in your decision might be the recommendations in Nonce-Disrespecting Adversaries: Practical Forgery Attacks on GCM in TLS:

  We conclude that an attack on an implementation using random nonces is unlikely, but it cannot be definetly excluded. For safety reasons random nonces should be avoided and a counter should be used.

I have summarized some more considerations on how to use AES-GCM correctly in a blog post.


How can AES + cycle walking be used as an FPE?

The general construction to encrypt (inputs of less than 128 bits) with cycle-walking is:

# IN, OUT are 128-bit unsigned integers in the range 0..MAX
OUT = AES(K, IN)
while OUT > MAX do OUT = AES(K, OUT)
return OUT

AES is going to permute your 128-bit input into a seemingly-random 128-bit output. About $1/2$ of the time the top bit of the output will be 0.  About $1/4$ of the time the top 2 bits will both be 0.  About $1/(2^n)$ of the time the top n bits will all be zero.

The construction above keeps looping until your output is coincidentally in the desired range.  This is non-deterministic: it could happen on the first iteration, or on the billionth.  Statistically it is likely to happen, on average, around iteration $2^{128}/{MAX}$.

If your MAX is close to $2^{128}$ then cycle walking can produce an efficient FPE solution.  But if your MAX is small - say a 9 digit account number ($MAX = 10^9$, which is close to $2^{30}$) then you can expect $2^{98}$ iterations to perform one FPE encryption.  That's harder than brute-forcing 2-key TDES, and clearly in the territory of 'prohibitive'.


Are the following asymmetric encryption schemes equivalent?

Generally, you should try to keep to standard practices unless the situation prevents you to do otherwise. That would mean that sign-then-encrypt should probably be used using two different key pairs.

Public keys are designed to be public and you should keep that in mind. Even if your scheme is secure, the system may not be. Public key operations could for instance leak the public key through side channel attacks. There is no need to protect the key after all. Key stores may not be available to store the key securely or at the right access level. Maybe you want to replace the software implementation with a hardware module that securely stores the private key - public keys won't be protected by such hardware.

An advantage of sign-then-encrypt is that you could decrypt the backup, then check the correctness of the signature afterwards. This allows you to store the backup decrypted somewhere without losing integrity. It also allows you to re-encrypt the package using a different key / scheme if that's required. Or to sign using a more fine-grained structure where parts of the backup are protected separately. In other words, using a separate signing key will give you a lot more flexibility.


Suppose you want to obtain the signature $s = m^d \bmod n$ on a chosen message $m$.  Here is that attack.

You ask the signer to sign a random message $m_1$ and obtain the corresponding signature $s_1 = m_1^d \bmod n$;
You compute message $m_2 := m\cdot m_1^{-1} \bmod n$ and ask the signer to sign message $m_2$; you obtain the signature $s_2 = m_2^d \bmod n$.

From the pairs $(m_1,s_1)$ and $(m_2,s_2)$, the signature $s$ on chosen message $m$ can be recovered as $s = s_1 \cdot s_2 \bmod n$.

To see it, observe that $s \equiv s_1 \cdot s_2 \equiv m_1^d \cdot m_2^d \equiv m_1^d \cdot (m\cdot m_1^{-1})^d \equiv m_1^d \cdot m^d \cdot m_1^{-d} \equiv m^d \pmod n$.

Note that you could obtain the signature on message $m$ by only asking one signature to the signer.  Indeed, you can construct the pair $(m_1,s_1)$ in Step 1 above by yourself as follows: choose a random $s_1$ modulo $n$ and define $m_1 = s_1^e \bmod n$ (where $e$ is the public verification exponent).  We then have $m_1^d \equiv s_1 \pmod n$ as required.


What's the `ticket_age_add` and `obfuscated_ticket_age ` used for in TLS 1.3

The point of these parameters is to encode the time since the ticket was issued.  This time is necessary so that a server can bound its risk of 0-RTT replay to a moderately narrow window.  The main problem with 0-RTT is the potential for a ClientHello and subsequent 0-RTT data to be captured and replayed.

If a client's 0-RTT ClientHello is replayed, having the time since the ticket was issued allows the server to reject 0-RTT quickly when the time is too far different from its own expectations.  This limits the time over which a ClientHello can be replayed, making other anti-replay techniques more feasible.  For instance, a server might remember every ClientHello it receives over a short interval, though more efficient mechanisms are definitely possible.

When a server receives a ClientHello with 0-RTT it can use the obfuscated_ticket_age to determine how old the ticket is from the client perspective.  The server compares this with its own view of the ticket age - it remembers the time it issued the ticket and the value of ticket_age_add and can use those values to recover both its own view of elapsed time and that of the client.  (A server might also remember an estimate of the round trip time between it and a client to allow for transit delays in its assessment.)

If the two times differ by too much, the server can reject 0-RTT quickly and efficiently.  The server needs to allow a little slack for things like relative clock drift, errors in its estimation of the round trip time, and retransmission delays from the transport protocol.  Values like 5 to 10 seconds either side are expected.

The ticket_age_add field is a simple form of encryption, equivalent to a one time pad.  ticket_age_add is a random value (or hard-to-guess pseudorandom value) that is added to the elapsed time from the client.  This encryption ensures that the client doesn't expose the time since the ticket was issued to anyone but the server.  If this wasn't obscured in some way, passive observers might use the time to link this connection attempt with a previous connection.  This value is added to the actual time that has elapsed (modulo 232) to get obfuscated_ticket_age.


No the mode would not be more secure (than what?).

I guess this is not vulnerable to:

padding oracle attack because it is basically counter mode

That's not correct. As the input of a block cipher is always a full block, you would need to pad the plaintext. Therefore you would likely be vulnerable to padding oracle attacks; they are not avoided by the mode itself.

stream cipher attack, because it isn't just simply XOR-d

Although you would not be vulnerable to a many-time-pad if the nonce is repeated, you would of course still leak information on each block of ciphertext that is identical, at the same location. That's slightly worse than e.g. CBC mode, where a change in plaintext would change all next ciphertext blocks if the IV is ever repeated.

malleability, because XOR-ing something on the ciphertext changes the entire plaintext

It doesn't, it just changes on block of plaintext at the same block offset. You would still be malleable if you would change the entire plaintext by the way (imagine encrypting a single bit, 0 for false or 1 for true!). So you need to expand your ciphertext - usually with an authentication tag - to avoid malleability. This is not a description of an authenticated cipher.

A significant disadvantage is that it needs a new key expansion for every element of the keystream.

Correct. And because you are using a lot of keys, you may run into trouble with regards on how the key space needs to be treated for a specific cipher. You would definitely worry about keys repeating simply due to the birthday paradox.

Are there any more advantages to this architecture?

Not that I see, it adds an additional round that introduces problems, while solving none; counter mode is already considered secure. With double the additional rounds + a key schedule per block it is rather expensive for what it tries to achieve.

Any further disadvantages?

I don't think we need more disadvantages, but I'll show some for learning purposes.
One disadvantage is that your key and block size need to be identical. So using e.g. AES-256 is not possible (even if it would be advisable because you may not want to use a cipher that is vulnerable against related key attacks, even if those are mostly theoretical in nature).
You would lose the pre-computation benefits of counter mode, where you can cache the key stream. You can still do that of course, but the last block encrypt / decrypt can only be performed once the plaintext is available.


What threat does this model pose to current cryptography?

Do you mean "what threat does their algorithm run on a quantum simulator pose to cryptography"?

If so, the answer is "none".  Yes, there exist Quantum Simulators (which run on classical computers), that can run Quantum Algorithms. However simulating $n$ entangled states requires $O(2^n)$ memory and time, and so a Quantum Algorithm that runs in polynomial time on a real Quantum Computer would make the simulator take exponential time; we already can factor faster than that on a classical computer.

These simulators are useful in studying what a real (that is, reliable) Quantum Computer could do, once it is built; they are not particularly useful in actually solving problems.

On the other hand, if the question is "they have a new Quantum Algorithm for factoring; what threat does that pose, once we have a real Quantum Computer?"

The answer to that is "not much more than what is known now".  We already have Shor's algorithm, which can factor in polynomial time.  Their algorithm might run faster (or with less qubits or other resources), and hence be somewhat more practical. However with Shor's algorithm, anything that relies on the difficulty of factoring is assumed to be already broken - this algorithm would (at best) make it a bit more broken.

As an aside, of the commonly used public key cryptosystems, only RSA and Pallier rely on the difficulty of factorization.  Shor's algorithm also addresses the discrete log problems (and so also covers DH and ECC); they don't mention whether their new algorithm can be used to attack those problems.


They call this a transposition cipher.  Bits commonly have more semantic meaning assembled into characters and numbers, so you may be performing  fractionation specifically.  Also, in cryptography we'd use a CSPRNG for the shuffle rather than a plain RNG for invertability reasons detailed in the link.     Frequency analysis means that it's fairly easy to break though.  Stuff to think about then.

It's a lot to take in, and there are very subtle nuances that mean creating a cipher from scratch is pretty tough. It's better to stick to library functions/ standardised methods /primitives in non scholarly uses.   Hi!


How Alice and Bob agree on which of the two beam splitters bases (Horizontal-Vertical and Right-Left) correspond to which of the classical bits (1 and 0) ? How do Alice and Bob agree on when actual transmission starts, when it is time to send/receive a photon taking note of event ?

Alice and Bob operate according to an agreed-upon protocol, which can define what binary value is assigned to what is physically made or observed, perhaps as follows:

Image source: UNS Nice (France), Department of Physics
There remains to agree on conventions in physical orientation, in particular what's rectilinear and what's diagonal (the optical link can rotate things); and the sequencing of sending photons and moving polarizer in-between.
Sequencing can be using an agreed-upon amount of time between photon emission, with the move of polarizer occurring in-between. Both that sequencing and the orientation can be determined by having Alice conventionally sending a repeating pattern before start of transmission, which allows Bob to calibrate it's receiving gear and reach synchronization (in particular rotate polarizer at a moment when that won't prevent detection of photons). The start of actual transmission can be determined by an agreed-upon and detectable change in the sequence, e.g. start right after
|/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\||/−\|−\|/−
The beginning has period 5 and allows to find what's what. The last 5 photons are rotated compared to the continuation of the sequence, which provides a robust indication of start to Bob having reached synchronization.

Once Bob has measured all of the photons sent by Alice, he would record the list of the beam splitters bases he used to measure those photons and send this list to Alice to check Bob's bases against hers. If Alice finds a match she would tell Bob to use the received qubit state as part of the key. Otherwise she will tell him to discard it. Right?

Yes. Note that the transmission of binary information from Bob to Alice, and back, occurs over a classical (non-quantum) public channel which authenticity typically is insured by conventional information-theoretic cryptography using an agreed-upon one-time-use shared key (see section B.3 in that answer) That key can be renewed by sparing a fraction of what's established by a step of Quantum Key Distribution, in order to secure the next one.

How would Alice detect that there was an eavesdropper Eve and warn Bob ?

The determination that there was no foul play is made by some highly technical "secret-key reconciliation" and "privacy amplification" protocol (running over classical channels authenticated as in 2 and allowing Bob to positively confirm success to Alice, or/and vice versa). Complex but conventional error-detection and correction techniques are involved. Basically, if the error rate of the quantum channel is sufficiently low, Eve can't have learned enough of it to compromise the confidentiality of the key obtained thru this protocol. See sections B.1 and B.2 of said answer for more.

Where does Heisenberg's uncertainty principle comes into action in QKD?

This  principle asserts that a photon's polarizations according to diagonal and rectilinear directions can't be both determined by an observer. That prevents Eve from reliably determining the state of Alice's photon and sending an exact copy to Bob: in her attempt at that Eve is bound to make at least 50% error for the polarization she could not observe, that is 25% error overall at the bit level, and that's detectable per the protocol of 3).


Updating a Merkle hash tree is trivial.  For instance, if you want to update a leaf, then you update it and then update every node on the path from it to the root.  If you have a particular operation on the tree in mind, the necessary updates follow immediately from the kind of update you want to do.  It's all very straightforward.  There's no reason to expect people to publish papers about this topic in general: it seems too obvious to count as novel, publishable research.

If you are worried about ensuring that the tree remains balanced or that the height remains logarithmic in the number of nodes, you can use any of the standard schemes for balanced binary trees: e.g., AVL trees, red-black trees, splay trees, 2-3 trees, and so on.  You can use any of them with a Merkle tree.  The balanced binary tree data structure describes how you modify the tree on each operation.  The Merkle tree structure adds extra hashes.

Note that there are many standard schemes for balanced binary trees that ensure that all of the basic operations can be done in $O(\lg n)$ time, and ensure that the height of the tree is always bounded by $O(\lg n)$.  Take any of those schemes; it is easy to see that updating all of the Merkle hashes can be done in $O((\lg n)^2)$ time (for each node that is touched, you might potentially need to update the hashes in it and all nodes on the path from it to the root; because of the bound on the height, this means changing at most $O(\lg n)$ hashes per node that is touched).  For many of those schemes, if you analyze them more closely, you find that updating all of the Merkle hashes can in fact be done in $O(\lg n)$ time (because the nodes they touch are all closely related, say, are all on the path from some leaf to the root, or something close to that).

Therefore, you can combine standard balanced binary tree data structures with Merkle hashing to get a Merkle hash tree that can be efficiently updated.  Again, no reason to expect this to lead to lots of publications in the literature: it is combining two standard ideas, and so not terribly novel and thus not likely to lead to lots of publishable papers.

Based on the comments, I realize there is something else I should explain.  In most applications, the exact shape or structure of the Merkle tree is unimportant.  For most applications, all that matters is the set of values that are in the leaves of the tree, and that the height be not too large (say, $O(\lg n)$, where $n$ is the number of leaves).  For those applications, balanced binary tree data structures are fine.

For instance, a typical use of a Merkle tree is as an authenticated set dictionary structure: a data structure that holds a set of values.  The order in which those values appear in the internal data structure doesn't matter; all that matters is, for each possible value, whether it is present in the set or not.  Thus, there is no requirement for the values in the leaves to appear in any particular order -- you can store them in any order you like, and an insert operation can add a new value anywhere in the tree.

More generally, we could imagine some application that cares about the set of values in the leaves and additionally requires they be ordered in some order (say, the values are in increasing order, if you traverse the leaves in left-to-right order).  This too can be accommodated with balanced binary trees.  Notice that such an application still doesn't care about the exact shape or height of the tree, as long as the leaves are in proper order and the height is $O(\lg n)$.

Now if hypothetically we had some application where the exact shape of the binary tree was essential, and each insert operation had absolutely no freedom or flexibility about the shape of the modified tree, then that'd be a different situation.  In that case, standard balanced binary tree data structures would be inapplicable, because they fundamentally need some flexibility in the allowable shapes of the tree.  However, this kind of requirement seems to be extremely rare in practice, and it's not clear what the motivation for it would be.  Therefore, you shouldn't be surprised if there aren't many, or any, published papers that address this odd variant of the problem.

From your comments, it sounds like you are imposing a requirement that is stronger than it needs to be.  It sounds like you are implicitly assuming that the Merkle tree needs to be fully packed at all times, i.e., that it's height needs to be exactly $\lg n$ at all times (plus or minus 1), where $n$ is the number of leaves.  However, there's no need to impose this restriction.  For practical applications, a slightly weaker condition is perfectly adequate: if we can guarantee that at all times the height of the Merkle tree will be $\le 2 \lg n$, that is perfectly sufficient.

And this weaker condition is what allows operations to be efficient.  If you look at standard balanced binary tree data structures, they ensure that the height of the tree is $O(\lg n)$ at all times (or some similar invariant).  This provides a degree of flexibility regarding the shape of the tree: it doesn't have to be fully packed.  This relaxation is what allows balanced binary tree data structures to be efficient (including to efficiently implement the insert-at-front operation you mentioned).  In practical applications there's no reason why we need the Merkle tree to have height exactly $\lg n$; height $2 \lg n$ is just about as good.

Of course, if you have a special application where you need some stricter requirement -- such as that the tree be fully packed, or that it has to have some specific shape at all points -- then standard solutions using standard balanced binary tree data structures might not suffice.  However, that's an unusual requirement whose motivation is unclear, so don't be surprised if there haven't been many, or any, published papers on that variant of the problem.

Hopefully this answers your question about why there haven't been many papers in the cryptographic literature on the topics you mentioned.  The short answer: addressing those problems is straightforward using standard computer science ideas, in the cases that seem to come up in practice, so not publishable (and any remaining variants don't seem to have an obvious practical motivation, so there's no reason why anyone would publish on those remaining variants).


What's the meaning of 160 bit Curve in Elliptic curve?

It's the size of the field, as the other answers explain. It affects the size of keys and signatures (which can be equal to the number or e.g. double it), as well as security and performance.

  Why they don't say 100 bit curve?

100-bit curves are too small.

It's also a convention. Other cryptographic primitives, like hash functions or symmetric ciphers, can have any bit length we want and powers of two are chosen for performance. So we want elliptic curves that match (or are close) to pair with them in a protocol, so we don't waste performance on security beyond the weakest link.

There's also the performance of the elliptic curve algorithm itself. It is useful to have the bit length be a multiple of a large enough power of two, like 64 bits, because computers deal with numbers of 32-bits or 64-bits. This isn't always the case though (e.g. P-521) if there happens to be a very juicy prime ($2^{521}-1$) that is easy to work with.

(As an aside, we do sometimes approximate something as e.g. 100-bit security if we don't care about the exact number but only a minimum. For example, a 256-bit elliptic curve that has a prime smaller than $2^{256}$ – e.g. P-256 – has only approximately 128-bit security so might as well call it 100-bit. Especially after you add a signature algorithm that also relies on a hash function, perhaps losing another bit of security to collisions.)


Difference between Zero Knowledge Proof and Challenge Response Protocol

They're just different things. A protocol may be challenge-response or not, and zero-knowledge or not; all four combinations are possible.

Plain password authentication is not challenge-response and not zero-knowledge.

The manual-lookup copy protection in old games is challenge-response and not zero-knowledge. Another example would be CAPTCHA.

Non-interactive zero-knowledge proofs are zero-knowledge and not challenge-response. Ex: Where's wally?

Colour Blind friend problem is an example for Zero-Knowledge Proof & Challenge-Response, both.

(Wikipedia says that plain password authentication is challenge-response because "tell me the password" is a challenge, and Modal Nest's answer says the same thing. By that definition I suppose any proof is necessarily challenge-response, because "prove it" is a challenge. But I think that definition is too broad and makes the term "challenge-response" largely useless. I'd limit it to protocols in which the prover has to do a nontrivial amount of work after getting the challenge, and can't just return a canned response.)


Are all homomorphic encryption schemes not CCA secure?

By definition, homomorphic encryption cannot be CCA secure. Therefore when using homomorphic encryption, care must be taken to prevent chosen-ciphertext attacks in the constructed system. Sometimes this requires proving in zero knowledge that certain actions were followed correctly, for example.

If you want to learn a bit more about what can be said about the CCA security of homomorphic encryption, see this paper (On CCA-Secure Somewhat Homomorphic Encryption).


How to securely combine multiple sources of entropy?

If your keys, taken together, have sufficient entropy to support your desired security level, then HKDF (paper) is a conservative solution here, because it assumes that the input keying material to the HKDF-extract might not be uniformly distributed.

The most conservative way of using it in your case would be to supply the concatenation of your keys as the IKM ("input keying material") parameter to HKDF-extract, and do not use the optional salt.  Then either use the PRK result directly, or as a further input to the HKDF-expand function.

A less conservative way of using it, if you are confident your inputs are indistinguishable from uniform random and mutually independent, would be to skip the HKDF-extract function supply the concatenated input directly to HKDF-expand.


Three problems here:

The online tool used expects a 24-byte (48 hex-character) key; thus you should enter E6F1081FEA4C402CC192B65DE367EC3EE6F1081FEA4C402C as the key, duplicating the first 8 bytes; this is the customary way to extend a two-block triple DES key of 16 bytes to a three-block triple DES key of 24 bytes.
You gave 16 bytes (32 hex chars) as input, which is twice as many bytes as required; this doesn't affect the computation of the KCV though.
The KCV value is supposed to be the first 3 bytes (6 hex chars) of the result, not 4 bytes (8 hex chars).

When this is fixed, the KCV 212cf9 is correctly obtained using the tool.

Note: it is a bad idea to use an online tool in order to check a real key, just like it is a bad idea to use an online RNG to generate a real key.


Implementing a web app where the server cannot decrypt its own data?

all those concerns have been studied a lot and still are. I'll try to give some keywords for them.

  a web app that stores all data on the server in a way that the server can't decrypt the data even if it wanted to.

Solution for this is User-side encryption. That's why, forget about the server chosing the encryption key himself.

It's quite well spread already. Problems happen when the server is supposed to do something with the data, since he's unable to read it. To tackle this there is a lot of efforts being put in homomorphic encryption, with wich you can manipulate encrypted data without the need (and the possibility) of decrypting it.

When the Server "Has to add data by himself" it works to use public key mechanism, but you cannot have a proof that he did not keep a copy of it, so this falls back to protecting the data against an external attacker (someone who steals the hard disk for instance), disk encryption should do the job and is available almost everywhere.

About the way of logging in without revealing the password, it seems that it called Zero-Knowledge Password Policy Checks (ZKPPC). See this recent paper about it: http://eprint.iacr.org/2014/242