We can obtain "absolutely perfect CONFIDENTIALITY" using the one-time pad. Is there such a thing as "absolutely perfect INTEGRITY"? The OTP (one-time pad) gives us perfect secrecy. This is the very best confidentiality available in this universe. (Although it does require large keys, which is beside the point of this question).

The problem is such encryption does not attain integrity. So my question is, is there such a thing as perfect integrity?

Yes, there is the one-time MAC.  This is a scheme which ensures that an adversary (even one with infinite computational resources) has a negligible chance of altering the message or forging a fake message without detection.

Edit to add: Mikero's comment and the other answer demonstrate that we need to be clear about what we mean by "perfect" integrity.  "Perfection" is a rather nebulous term, so  I will provide a rigorous definition as I understand it, and contrast it with a similar definition for "perfect" confidentiality.  Hopefully, even if you disagree with my definitions you will be able to see why I think one-time MAC can provide "perfect" integrity (as I define it).

Perfect integrity and perfect confidentiality can both be defined in terms of games.  Let's do the confidentiality game first:

Confidentiality Game:

You have a Challenger, an Adversary, and an encryption scheme (e.g. a block cipher using a Mode of Operation, or a stream cipher, or the OTP).  The Challenger and Adversary agree upon a length limit $\ell$, which is the total length of all messages that will be encrypted by the Challenger during the game.  The Challenger selects a key from the defined key-space of the encryption scheme uniformly at random (e.g. for AES-128 it would select a 128 bit string from all such strings, and for a OTP it would select a string of length $\ell$ from all such strings).

There are two phases to the game - first a query phase, and then a challenge phase.  In the query phase, the Adversary can submit chosen plaintext queries to the Challenger, who encrypts them using the scheme and the selected key, and presents the resulting ciphertexts to the Adversary.

During the challenge phase, the Adversary selects two messages that are of equal length, $m_0$ and $m_1$, and submits them to the Challenger.  Note that the total length of all the queries added to the length of $m_0$ must not exceed $\ell$.  The Challenger selects a single bit $b$ uniformly at random, encrypts $m_b$, and presents the resulting ciphertext to the Adversary.  The Adversary outputs a single bit $a$ which is its guess as to the value of $b$.  If $a=b$ then the Adversary wins the game, otherwise it loses.

An encryption scheme provides $\ell$-wise perfect confidentiality if and only if there is no Adversary (not even a computationally unbounded Adversary) who can win this game with probability greater than 0.5.  Note that a one-time pad provides perfect confidentiality in this sense.

Integrity Game:

You have a Challenger, an Adversary, and a MAC scheme.  The Challenger and Adversary agree upon a total number of messages $n$ that the Challenger will authenticate during the game, as well as $\ell$ the total length of those messages, and a tag length $\tau$ (e.g. they can agree that the MAC tags will all be 64 bits long).  The Challenger selects a key from the defined key-space of the MAC scheme uniformly at random.

As before, there is a query phase and a challenge phase.  During the query phase, the Adversary can submit up to $n-1$ messages to be authenticated to the Challenger, who generates the corresponding MAC tags for those messages and presents them to the Adversary.  During the challenge phase, the Adversary outputs a message $M$ (which cannot be the same as any message submitted during the query phase) and a tag $T$.  The total length of the queries and $M$ cannot exceed $\ell$.  The Challenger generates the MAC for $M$, and if that MAC is identical to $T$ then the Adversary wins the game, otherwise it loses.

A MAC scheme provides $(n,\ell,\tau)$-wise perfect integrity if and only if there is no Adversary (not even a computationally unbounded Adversary) who can win this game with probability greater than $1/2^{\tau}$.  Note that a one-time MAC provides perfect integrity in this sense.


What size of initialization vector (IV) is needed for AES encryption? What size of initialization vector (IV) is needed for AES encryption?
I am using either CBC or CFB modes.

Knowing that AES is a sysmmetrical block-cipher algorithm with a 128-bit block size, I think the answer for IV is still 16 bytes or 128 bits for AES 128, 192 and 256.

Reading this stackoverflow Q&A it seems as if the size of the IV is the size of the block which is always 128 bit (= 16 bytes) in AES, even if the keysize is larger than the block size. Is that correct?

For both CBC mode and CFB mode, the initialization vector is the size of a block, which for AES is 16 bytes = 128 bits.  For CFB mode, the IV must never be reused for different messages under the same key; for CBC mode, the IV must never be reused for different messages under the same key, and must be unpredictable in advance by an attacker.  Using successive integers as the IV is fine for CFB but not fine for CBC.

Beware: The Wikipedia articles are currently (2017-08-11) full of archaic drivel about self-synchronizing ciphers and error propagation and other fortunately forgotten relics of the dark ages of crypto engineering from a bygone century.  I cite them only for the easily accessible statements of equations relating plaintext and ciphertext and their associated diagrams.

All that said, could I interest you in an authenticated encryption scheme instead, such as NaCl crypto_secretbox_xsalsa20poly1305?  Or, if you find yourself reaching for the letters ‘AES’ and ‘CBC’, you're probably lost in a vat of acronym soup and you may need help navigating crypto protocols more than you need help picking the right parameter sizes for a confusing crypto API that asks you to choose mode and then specify IV.


What is the probability of the first half of a hash output being identical to the first half of another hash output? Let's say for example that I encrypt a password with some hash function and receive a 256-bit hash value in return. What are the chances that the first 128-bits (half) of this value are identical to the first 128-bits of another hash output?

If you're feeling generous, what are the chances that the first 64-bits (1/4) of the output are identical to the first 64-bits of another output?

Let's say for example that I encrypt a password with some hash function and receive a 256-bit hash in return.

You cannot encrypt a password using a hash function, you can only create a hash value as the name implies.

  What are the chances that the first 128-bits (half) of this key are identical to the first 128-bits of another key?

The hash value can be used as a key, but usually you'd use a KDF for that. Hash functions can be used as KDF, but you're better off using a real KDF such as HKDF.

Obviously if the amount of possible "key" or "password" input is (next to) infinite then the amount of "keys" that map to a certain hash value is infinite as well. The same goes of course for the first 128 bits of the output.

The trick is that finding this particular input is hard as hashes are one-way. Basically you'd have to iterate over all possible inputs to find the hash, and iterating over that large an amount is (completely) infeasible.

Once you've chosen a key / password then you would have to perform a pre-image attack. In that case the hash is secure then you'd simply have a chance of $1 \over 2^n$ that another key / password hashes to the same value, where $n$ is the output size. So that's $1 \over 2^{128}$ for 128 bits of output and $1 \over 2^{64}$ for 64 bit of output.

If you just generate a large number of passwords then the chances of collisions between the set of hashes grows as well. In that case you have to assume that the birthday attack applies. The security then depends on the amount of hashes. For very large lists you should use 128 bits of output (giving about $2^{64}$ bits security for $2^{64}$ outputs).


Commitment to a polynomial $A(x) \bmod B(x) = C(x)$ and $A(x) \bmod D(x) = E(x)$:

A dealer knows $A(x)$ polynomial, which is a secret. He distributes $C(x)$ and $E(x)$ privately to $X$ and $Y$, respectively. $B(x)$ and $D(x)$ are public. $X$ and $Y$ want to know that $C(x)$ and $E(x)$ is the result of $A(x) \bmod B(x)$ and $A(x) \bmod D(x)$, respectively, without getting to know $A(x)$.

Is it possible to the dealer to commmit to $A(x)$ to prove that this is the polynomial being used in both expressions?

My solution is based on Pedersen commitments; in this scheme, we work in a prime-sized ($p$) subfield of some group, perhaps $\mathbb{Z}_{kp+1}$, so some prime $kp+1$; where both $p$ and $kp+1$ are large enough to make the discrete log problem intractible.  We have two generators of this subgroup $g$ and $h$, and it is important that no one knows the discrete log of $h$ base $g$.

A commitment in this scheme to a value $x_i$ is the value $g^{x_i} h^{r_i}$ for a random value $r_i$; if you want to open the commitment, you reveal $x_i, r_i$.

One of the things that is interesting about this scheme is that it makes it easy to prove linear relationships; for example, if we have committed to $n$ $x_i$ values, issuing the commitments $c_i = g^{x_i} h^{r_i}$, and want to issue a proof that $\sum a_i x_i = b$ for some public constants $a$ and $b$, all we need to do is to proof that we know the value $y$ such that $\prod (c_i)^{a_i}\cdot g^{-b} = h^y$ - the left side can be computed by the verifier, and so a simple Schnorr proof suffices (and, assuming that the prover remembers all the $r_i$ values he used, he can easily compute $y$)

And, I'll assume that the polynomials $B(x), D(x)$ have a known maximum degree $n$; the polynomials $A(x), A'(x)$ have a known maximum degree $m$ (which may be larger).

With this tool in our toolbox (and with the above assumption), it becomes easy.  To commit to $A(x)$, you publish Pedersen commitments to each coefficient individually (and similarly with $A'(x)$ - there is no need to use the same $r_i$ values unless you decide to make the relationship between $A(x), A'(x)$ obvious at the start)

Then, to send $C(x)$ to X (along with a proof that $C(x) = A(x) \bmod B(x)$), well, we have $A(x) = B(x)K(x) + C(x)$ for some polynomial $K(x)$; so you would give $m-n+1$ Pedersen commitments for the coefficients of $K$.  Then, the above equation can be viewed as a series of linear equations between $A(x)$ and $K(x)$ (and the public to X polynomials $B(x), C(x)$.  So, we just issue $m+1$ proofs that each individual coefficient of $B(x)K(x) + C(x)$ matches $A(x)$.

The last step is to issue a proof that $A(x) = A'(x)$; that is easily done, as that is just another linear relationship, and so the same tool can do it.

QED


How to make a message into a polynomial on NTRU encryption? How to make a message into a polynomial on NTRU encryption? for example how we can conver 'hello world' to polynomial...
i have read the converting operation on IEEE Std 1363.1- 2008, but i can't understand the process without example, can anyone show for the small example?

According to Wikipedia:

  Alice, who wants to send a secret message to Bob, puts her message in the form of a polynomial m with coefficients {-1,0,1}. In modern applications of the encryption, the message polynomial can be translated in a binary or ternary representation.

So, lets say you have a message encoded in base 2 as 101101, you'd set the polynomial to $1+0x+1x^2+1x^3+0x^4+1x^5=1+x^2+x^3+x^5$. That then is your message to encrypt. Technically you could encode a message in ternary and do the same thing. Then you'd have coefficients in $\{-1,0,1\}$. There is no reduction in security by encoding in binary, however, and only having coefficients in $\{0,1\}$.

Now, moving that to your string. First encode your string in base 2 (you can do this how you want), then construct your polynomial. If you have more bits than the degree of the NTRU polynomial, you'll have to split up the message into blocks. I'm sure you know about the standard warnings with using public key encryption for large messages. Unless you have a really, really good reason you shouldn't do it. Encrypt a random key with the public key cipher and encrypt the plaintext with the random key.


How is session key generated for TLS? I would like to understand better what happens during establishment of SSL/TLS secure connection.

The Client wants to establish a connection - ClientHello
The server answers with a ServerHello. This includes a randomly generated number and a server certificate
The client creates a "pre master secret" and sends it encrypted to the server using its public key.
Both parties create a session key from random number and pre master secret.

The question:

Is this the same as Diffie-Hellman key agreement? During DH key agreement both parties send a random key to the partner from which the session key is finally generated. DH is (in principle) completely symmetric. Why is the random number from the client called "pre-master-secret" and from the server just "random number"?

No, this is not the same thing as Diffie-Hellman key agreement.

What happens here is that the server authenticates itself by being able to RSA decrypt the pre-master-secret. If the server is able to do that it is possible to perform (H)MAC operations using the derived session key.

A problem with this scheme is that the encrypted pre-master secret can be stored by the attacker - together with the rest of the TLS session. The attacker can then try and find the private key value. Once that is found all the data of that particular session and all other sessions protected with the private key can be decrypted.

DHE_ and ECDHE_ ciphersuites work differently. The key pairs are generated on the fly; i.e. the key pairs are ephemeral (the E in DHE). Both client and server establish a session key. The server (or the client and server) then authenticate by performing signature-generation (for authentication). This has the advantage that each session needs to be attacked separately. This is known as (perfect) forward secrecy.

The server's random is a value that does not need to be protected. It is used as derivation data for generating the master_secret from the pre_master_secret. If it wasn't present then the key would not be dependent on a random source of the server. This is a problem if the client's random number generator is not secure (enough). The pre-master secret on the other hand needs to be kept secret.

Note that the server cannot send an encrypted value to the client as the client is not authenticated at that time.


Computationaly hard detokenization algorithm for credit card numbers I am designing a vault that tokenizes credit card numbers (a plaintext that consists of 16 decimal digits), with the following requirements:

Given some plaintext, the vault returns an index.
   If the plaintext does not exist it returns a new index.
   If it does exist it returns the same index it had returned before for that plaintext.
The vault allows detokenization (given index return the plaintext),
   however this is quite rare (once a month) and involves authentication procedure.
The vault stores the plaintext encrypted using an algorithm so that detokenization
   of one index is computationally possible but hard.
   Let the costs of detokenization be X per entry.
An attacker that got access to the vault should find it too computationally expensive
   to detokenize the entire vault.
A variation: the attacker may have access to a limited list of (index, plaintext)
   pairs that they injected into the vault before they compromised it.
   Let the length of this list be Y.

What is the encryption algorithm that should be used for this use case? Can it be designed so that X is configurable (given Y=0)? Can detokenizing the entire vault be computationally hard regardless of Y, or must we assume Y = 0?

Edit:

I've modified the original question. Instead of tokenizing a 6 decimal digit plaintext, the question is now about tokenizing a 16 decimal digit credit card number.

Both a legitimate user and a very skilled attacker has access to partial credit card numbers. A partial credit card number consists of the first 6 plaintext digits, the last 4 plaintext digits, and the index received from the vault. In order to find the remaining middle 6 digits the legitimate user would authenticate and detokenize, while the skilled attacker would have three options:

Perform a limited number of tokenizing operations without compromizing the vault.
Compromise the vault and perform 50,000 tokenizing operations per plaintext.
Compromise the vault and perform one detokenization per plaintext.

Additional information:

Many credit cards share the same first 6 digits.
Werther the plaintext is the complete 16 digits number or only the middle 6 digit number is part of the design.
The index length is part of the design
Once the vault is compromised the attacker has access to the vault storage/memory which contains everything except one-time keys that were properly erased. The same attacker has also compromised the detokenizer's private key stored elsewhere if there are such keys.

Edit 2:

Removed the requirement that the index is random. It just need not to be some hash of the plaintext to avoid brute forcing the index without compromizing the vault.
Changed brute force tokenization per plaintext from 100,000 to 50,000
Obviously the plaintext could be encrypted with a public key, and assume that only the authorized detokenizer has the private key. Alas, if a skilled attacker has enough resources to compromise the vault (by hacking into the vault machine) , the attacker has enough resources to compromise the private key (by hacking into the machine containing the private key).
 Assuming the hack is discovered in timely fashion, the cards would be canceled before the hacker sold the Cards in the black market.
 For that purpose, the detokenization of the entire vault must be so hard that it would delay the attacker for a long time, or would require vast amounts of compute resource to make it non-economical in the first place.
It is expected to make the tokenization computationally hard - so 50,000 tokenization operations per credit card number would be non-economical or would take too long (configurable)
It is expected to make the detokenization computationally harder than 1 and less than 50,000 tokenization operations (configurable).

I am assuming that the vault shall store arbitrary-length messages and associate with each message a token consisting of six decimal digits. Otherwise, as has been noted (see below), the problem is probably either impossible or trivial.

I interpret your requirements to mean that the detokenization algorithm is also available to an attacker that has gotten access to the vault, which means that the cost of detokenizing the entire vault is at most $nX$, where $n$ is the number of items stored in the vault and $X$ is the cost of detokenizing one index.

This means that the best you can do is to balance your $X$ such that $X$ is feasible, but $nX$ is economically infeasible. (Note that $n$ is very small, so it seems unlikely that $X$ cost can be feasible for you, but $nX$ cost infeasible for an attacker.)

(Note that if the vault's detokenization algorithm is not available to the attacker, your problem has a very simple solution using deterministic public key encryption: Encrypt the message using the detokenizer's public key. If you already have the ciphertext, you're done. Otherwise, pick a fresh index and store the index-ciphertext pair. The detokenizer simply decrypts the ciphertext. This is the best you can do unless the vault's tokenization algorithm also isn't available to the attacker, in which case everything is trivial.)

The system consists of an interactive algorithm $V$ and an algorithm $D$. The correctness requirement can then be stated as follows:

We can send $m$ to $V$, in which case $V$ responds with an integer $i$. As long as $V$ has been sent less than $10^6$ distinct messages, the following requirement is satisfied: For any $m'$ previously sent to $V$ to which $V$ replied with $i'$, then $i=i'$ if and only if $m=m'$.
We can send $i$ to $V$, in which case $V$ responds with $z$ or $\bot$. The response satisfies the following requirement: If $V$ previously replied with $i$ when sent message $m$, then $D$ will output $m$ on input of $z$, using expected time $X$.
We can send compromise to $V$, in which case $V$ responds with any secret keys it may have and a list $(i_1, z_1), (i_2, z_2), \dots, (i_n, z_n)$. If $V$ was sent the messages $m_1, m_2, \dots, m_k$ with replies $j_1,j_2, \dots, j_k$, then $k=n$, $i_1=j_1$, ..., $i_n=j_n$, and $D(z_i) = m_1$, $D(z_2) = m_2$, ..., $D(z_n) = m_n$.

The security requirement is the following:

If $V$ has been sent $n$ distinct messages, of which $k$ have been sent by the attacker (or can be predicted with reasonable effort) and the remaining $n-k$ are unpredictable to the attacker, then no adversary sending compromise to $V$ can recover the remaining $n-k$ messages with expected cost significantly smaller than $(n-k)X$.

The following scheme seems to satisfy these requirements. We need

a hash function $H$ (modeled as a random oracle),
a deterministic one-time symmetric encryption scheme $(\mathcal{E}, \mathcal{D})$, and
a large family of groups $\mathcal{G}$ such that we can efficiently sample a group $G$, a generator $g$ and a verifiably random element $y$ in the subgroup generated by $g$, such that $(G,g)$ are suitable for ElGamal encryption, and the best algorithm for computing logarithms smaller than $T$ in $G$ requires expected cost $\sqrt{T}$. (All reasonable assumptions.)

The interactive algorithm $V$ stores a list of tuples $(i, c, G, g, y, x, w)$:

On input of $m$ to $V$, let $K = H(m)$ and $c = \mathcal{E}(K,m)$. If $(i,c,-,-,-,-,-)$ is stored, respond with $i$ and stop. Otherwise sample fresh $i$. Sample $G$ from $\mathcal{G}$ as well as $g,y$, then choose random $r < X^2$. Compute $x = g^r$, $w=y^r K$. Store $(i, c, G, g, y, x, w)$.
On input of $i$ to $V$, if $(i, c, x, w)$ is stored, respond with $z = (c, G, g, y, x, w)$.
On input of compromise, respond with the entire list of tuples.

The algorithm $D$ on input of $(c, G, g, y, x, w)$ does:

Compute the discrete logarithm of $x$ to the base $g$. (Expected cost $X$.)
Compute $K = w y^{-r}$.
Compute $m = \mathcal{D}(K, c)$.
(Optional) Verify that $H(m) = K$.

This scheme is correct, and a five-minute analysis suggests that it also satisfies the security requirement. The only minor subtlety in the scheme is that every entry must have a fresh group, otherwise algorithms for computing many discrete logarithms in one group could allow the adversary to decrypt with expected time smaller than $(n-k)X$.

I would not actually use this scheme without a proper security analysis.

A few minor notes: The families of groups can be either based on finite fields or elliptic curves, where the latter would probably involve point counting and therefore be moderately expensive. In either case, naïve ElGamal is probably not the right scheme to use, some variant of DHIES or ECIES or something would be better.

You can make tokenization cost $T$ work as follows: Let $K' = H(m)$. Use $K'$ to generate an elliptic curve of prime order $\approx T^2$ and two verifiably random points $P$ and $Q$ on the curve. Compute the discrete logarithm $U = \log_P Q$. Then let $K = H(m,U)$. Another (simpler) option (as was pointed out in another answer) is to simply use an expensive hash function such as PBKDF2 or scrypt with appropriate parameters.


Should I use RSA encryption since RSA is said to be broken by NSA? I am developing a simple web app that uses asymmetric encryption, but I am not sure whether to chose RSA for the reasons mentioned above.

What are your suggestions? Also if I decided to go with RSA what is the recommended Key Size ?

Also, someone in the comment area mentioned using libraries made by others, but did not say which libraries should I use?

This question has many problems in the way it was asked, and clearly did not come after doing some investigation. However, since this seems to be a misconception that is spreading widely, I will relate to it.

It is not true that the "crypto community" (whoever that is) believes that the NSA can break RSA. In fact, if Snowden taught us anything, it is that the NSA is using many techniques to bypass RSA in TLS and elsewhere (stealing private keys, utilizing implementation bugs, and more), but are not breaking RSA. If they could break RSA then this wouldn't be necessary and would be the easiest route to take.

Now, it may very well be that the NSA has some advantages in factoring over the academic and open crypto community. This makes a lot of sense for two reasons:

We share everything that we discover with them (by publishing papers), and they share nothing about what they discover with us
They have absurd computing power that they can utilize

Having said the above, I do not think that they can do much more than the rest of us. What's my basis for this belief? Nothing except that many very strong academic minds have also worked on this, and the Snowden revelations about what they are doing.

This possibly justifies the move to RSA-2048 (instead of settling on RSA-1536). I am very skeptical that the NSA can go beyond RSA-1024 by much. However, I think that it is a good idea to use RSA-2048 because I strongly believe that this is way beyond their power, again for the reasons stated above.


Unforgeability proof of partially blind signature (schnorr signature based) I read a representative paper about partially blind signature.

Abe and Okamoto - "provably secure partially blind signature".

They suggested a partially blind signature scheme based on Schnorr signature.

But I cannot understand the proof of Lemma 2 that the scheme is unforgeable.

Below image is part of the proof process. (p.281)

${M}$ is a machine constructed by a forger ${U^*}$, y is public key where ${y=g^x}$, ${F, H}$ is random oracles, and ${Info}$ means message.

Why ${M}$ outputs a valid signature with probability at least ${1-e^{-1}}$? (highlighted part)

Thanks.

If the probability (over random choice of the random tape $\rho$ and the random oracle $\mathcal{H}$) of a particular trial being successful is at least $\mu'$, then the probability that $1/\mu'$ independent trials* are unsuccessful is at most $(1-\mu')^{1/\mu'}$ --- this expression converges to $1/e$. The claim follows.

*Here, independence refers to the choice of $\rho$ and $\mathcal{H}$.


Why are vectors approximately orthogonal after Gaussian lattice reduction? In "An Introduction to Mathematical Cryptography"'s section on lattice reduction algorithms, the authors describe Gaussian lattice reduction and claim:

  ... the angle $\theta$ between $v1$ and $v2$ satisfies $\left| cos \theta \right| \leq \frac{\lvert v1 \rvert}{2\lvert v2 \rvert}$, so in particular $ \frac{\pi}{3} \leq \theta \leq \frac{2\pi}{3}$.

Where $v1$ and $v2$ are the output of the Gaussian lattice reduction algorithm and $\lvert v1 \rvert \leq \lvert v2 \rvert $. This result seems very close to a few trigonometric identities but I don't see why this is true in every case. Can someone shine some light on why this guarantees the reduced vectors share an angle in that range?

When the algorithm ends, $m = 0$, which means that

$$\left| \frac{v_1v_2}{||v_1||^2} \right| \le \frac{1}{2}$$

otherwise, the nearest integer would not be zero (and $m$ would be different from zero).

Now, you just use the well-known cosine similarity: since both vectors are non-zero (because they belong to a basis of the lattice), we have that  $v_1 v_2 = || v_1 || || v_2 || \cos \theta$.

Combining those two expressions, we get

$$\left| \frac{v_1v_2}{||v_1||^2} \right| = \left| \frac{|| v_1 || || v_2 || \cos \theta}{||v_1||^2} \right| = \left| \frac{|| v_2 || \cos \theta}{||v_1||} \right| =  \frac{|| v_2 || \left| \cos \theta \right|}{||v_1||}  \le  \frac{1}{2} $$

which gives us $\left| \cos \theta \right| \le \frac{||v_1||}{2||v_2||}$, the expected inequality.

-- EDIT

As galvatron commented, the inequality involving the angle $\theta$ is obtained simply by using the fact that $||v_1|| \le ||v_2||$, which together with the first inequality, gives you $| \cos \theta | \le \frac{||v_2||}{2||v_2||} = \frac{1}{2}$. Therefore, $- \frac{1}{2} \le \cos \theta \le \frac{1}{2}$.

But $\cos \theta$ equals $\frac{1}{2}$ when $\theta = \frac{\pi}{2}$ and equals $-\frac{1}{2}$ when $\theta = \frac{2\pi}{3}$.


Three-Pass Protocol number theory I've got a homework problem that I'm having a hard time understanding. It's for the Three-Pass Protocol, and we are given p, the three messages, and are told that the original plain text is one of two values.

The professor says we can use number theory to look at any of the three messages and determine which of the two original plain texts is correct, but I'm not seeing how. We covered the intruder in the middle attack, but since we can't send our own message that can't be the right action to take.

Could anybody point me in the right direction?

I suspect that the professor is thinking of Quadratic Residuosity.  A value $x$ is a quadratic residue (modulo $p$) if there exists a $y$ such that $y^2 \equiv x \pmod p$.

This is important, because:

For any value $x$ (and prime $p$), it's easy to determine whether it's a quadratic residue or not.
If $e$ is relative prime to $p-1$, then $x^e$ is a quadratic residue iff $x$ is.

Now, if we have two plaintext messages, one of which is a quadratic residue, and one is not, can you see how the above observerations can be used to distinguish the two messages from any message in the 3-pass exchange?


ElGamal Threshold Cryptosystem Suppose we have a threshold ElGamal cryptosystem $(t, n)$ over an Elliptic Curve $E_p$, $p$ being a large prime, with the following parameters:

$G$ is a generator point of $E_p$ with order $q$
A dealer chooses a polynomial $f(x) = s + a_1x+...+a_{t-1}x \in Z_q[x]$  and $s \in Z_q$ is the secret key of the cryptosystem.
$Y = sG$ is the public key.
The dealer computes and distributes the secret private share $s_i$ to $P_i$ as $f(i)$, $i \in 1,2...n$.
With Lagrange interpolation, $s = \sum_{i=1}^ts_i\prod_{j=1}^t\frac{j}{j-i}$, $i \neq j$.
A ciphertext $(C1, C2) = (rG, M+rY)$, $r \in Z_q$, can be decrypted as $$M=-(\sum_{j=1}^tb_js_jC1) + C2$$ with $b_j = \prod_{j=1}^t\frac{j}{j-i}$, $i \neq j$.

My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$?

$b_js_j$ can be $>q$ because it is not a field element but the number of times $C1$ is summed, right?

My question is: since $s$ is an element in $Z_q$, shouldn't $b_js_j$ be also calculated $\mod q$?

Doesn't really matter - the results come out the same either way.

We know that the order of $C1$ is $q$, and so we have $x C1 = (x+q)C1$ for any $x$.  Hence, we have $b_js_j C1 = (b_js_j \bmod q) C1$

In practice, we generally want to reduce $b_js_j$ mod $q$ for performance reasons (or because our point multiplication routines might not handle multipliers significantly larger than $q$); however the math works out the same in either case.


How to meter and limit number of files encrypted? First my apologies if this isn't the right forum for this but here's my problem :

I have a black box that takes an input file and produces an output file.
I want to sell this black box to a customer but I want to meter/limit the number of files the customer can use with this box. A counter would not be fair to the customer since they might use the box multiple times with the same input file.
I could request the customer to send me the input file every time and I can encrypt it so that the black box would only work with my encryption. The problem with this is that the customer may not want to give me the input file.
I could ask the customer to generate some sort of key based on each input file; I can then generate another key for the black box and send it to the customer to use. This seems like a workable solution and I would guess this kind of scheme has a known name and has been studied before.

Encryption is not my area (I'm into building black boxes) so I would appreciate if someone can point me to the right terminology to use to search for this kind of metering scheme.

I believe the concept you're looking for is a cryptographical hash.  This is a function that takes a (potentially) long input, produces a short (fixed length) output, and for which it is impractical to find two different inputs that generate the same output.  It is a fixed function; anyone (including your customer) can generate a hash for any input.

How it would work is:

The customer would generate the hash of their file, and send it to you
You would take this hash, and generate a key (or signature) for that hash, and send it to the black box
The black box would take the signature and the file, compute the hash of the file, and verify that the hash corresponds to the signature.  If so, it'll go ahead and process the file (and produce the output).

One common cryptographical hash function is SHA-256; it has an output which is 256 bits (64 hex digits long); it needs to be that long to avoid attacks where someone computes a long series of hashes, and looks for two different inputs that happen to generate the same hash.

Alternatively, if the limit on the number of times that a black box can be used isn't too large, the black box could just compute and store the hashes of the input files itself.  In this case, if the customer submits an input twice, the black box will compute the same hash value, see that it's already on its list, and realize that it's recomputing an input.


Understanding token security I am having some problems, cryptographically speaking, digesting this information. There is a table that seems to say that tokens provide "end to end security" (I suppose we understand different things by that).

But my main issue is with this:

  Tokenization also helps protect your online shopping activities. You buy a coffee table on Ikea.com, for example. If IKEA has tokenized the card numbers that it keeps on file, your information is safe even if it gets hacked (which it hasn’t). The retailer may never actually see or store the credit card number, so if someone weasels into the system (like in the Home Depot breach, for example), all the criminal can see is the randomly generated tokens.

I understand the benefits of tokens, because they are pseudo-random, they can be changed periodically (so the old ones will not work) and they do not disclose identifiable information. However, it seems to me that whoever owns the token can perform the same activities as the legitimate owner. So it is an "anomisation" of PANs, not a security measure against forbidden use. If someone hacks Ikea.com and gets the tokens, he/she could use them to buy a coffe from somewhere else in the same conditions as the actual PAN could be used. In this case, the benefit is that the token can be easily renovated without having to change the PAN.

(1) Am I missing something? What is the real security provided by tokens in this case?

(2) Are tokens generated by PRFs? If a PRP is considered "secure" (so it cannot be distinguised from a "secure" PRF and its outputs look like random strings) can PRPs be used to create PRFs to generate tokens? For example, a cipher block with random keys used to generate tokens.

(3) Additionally, tokens that are 128 bits long and are never changed will operate correctly (in probability) up to $2^{64}$ generated tokens, after which we can expect the system to fail? (due to collisions)

(1) Am I missing something? What is the real security provided by tokens in this case?

Suppose you shop at Home Despot and IKING and they store payment information.  Suppose Home Despot is breached and evil Freedonian hackers steal all the stored payment information.  What can we do?

If Home Despot was storing your long-term credit card information, then you have to get a new credit card.  Worse, so do the eight million other people who used it.  And until you get a new credit card, you can't buy a new longcouch at IKING—but until the breach is discovered, the pirates who breached Home Despot can!
If Home Despot was merely storing a per-site pseudorandom function of your payment information, then:

only Home Despot has to get a new thing (in their case, a new security department)—you and the eight million other schmucks who shopped there can keep your credit cards
presumably the Home Despot tokens work only at Home Despot, so the pirates are unable to refurnish their living quarters with new longcouches from IKING on your shilling

  (2) Are tokens generated by PRFs? If a PRP is considered "secure" (so it cannot be distinguised from a "secure" PRF and its outputs look like random strings) can PRPs be used to create PRFs to generate tokens? For example, a cipher block with random keys used to generate tokens.

As long as you see well under $2^{b/2}$ input/output pairs for a PRP, a PRP is a good PRF.  Of course, if the key gets leaked, all bets are off.  For a keyed hash like HMAC-SHA256, which has PRF security and a little more, at least if a key gets leaked an adversary is limited to brute force search to find the input (like a credit card number) that might have gone into it to yield an output they found stored in a database.  So, while a PRP is a pretty good PRF, there are qualitative differences that might lead you to want to choose something with stronger security like HMAC-SHA256 or keyed BLAKE2 or KMAC128 instead.

  (3) Additionally, tokens that are 128 bits long and are never changed will operate correctly (in probability) up to $2^{64}$ generated tokens, after which we can expect the system to fail? (due to collisions)

It's unclear to me exactly how the tokens are used and I'm too lazy to read beyond the page you linked.  But suppose it works as follows—a scheme I just pulled out of my cloaca on the spot:

Home Despot is assigned a secret key $k$ known only to Squipe, Silicon Valley's hottest new payment processor.
When Evelyn T. Shopster enters her credit card information at Home Despot's web site using Squipe's gooey webplet, Squipe stores Evelyn's name and credit card number, and computes for Home Despot the token $t = \operatorname{HMAC-SHA256/128}_k(m)$ where $m$ is the message: The bearer of this token is authorized to charge the credit card of Evelyn T. Shopster.  (Here $\operatorname{HMAC-SHA256/128}$ is the 128-bit truncation of HMAC-SHA256.)
When Home Despot wants to charge the card, it sends the charge amount, Evelyn's name, and $t$ to Squipe.
On receipt of a charge request with token $t$ and name name, Squipe computes $\operatorname{HMAC-SHA256/128}_k(m')$ on the message $m'$ computed by The bearer of this token is authorized to charge the credit card of ${name}., and checks (in constant time!) whether the result is the same as $t$.

In this protocol, it doesn't matter if there is a collision between tokens, because one token cannot be used for another user; for any particular user you might try to abuse a token for, there's still only about a $1/2^{128}$ chance that it will work.

On the other hand, there are cases in which collisions could matter—for example, $2^{64}$ queries to an oracle for HMAC-MD5 under a secret key can lead to forgery with high probability.  (This isn't because MD5 is broken—only MD5's collision resistance is broken; the same attack applies to HMAC with any 128-bit hash.)


How much is slower GCM AES-128 than one of the stream chipher eSTREAM? Evaluate the speed of the algorithm GCM AES-128 and compare it whith speed of one of the stream chipher in eSTREAM. Can someone give such an assessment?

eBACS, as given by CodesInChaos, is a great resource, and it provides much more data than I could hope to give in this answer. However, the page is not explicit about whether or not AES-NI was used — looking at the results, it doesn't seem so.

For an extremely shallow analysis, but allowing us to know for-sure about hardware acceleration, we can use the command-line tool gnutls-cli, which uses GnuTLS to benchmark some ciphers. Some sample output:

[reid@reid-pc] ~ % gnutls-cli --benchmark-ciphers
Checking ciphers, payload size: 16384
     SALSA20-256-SHA1 0.30 GB/sec
     AES-128-CBC-SHA1 0.33 GB/sec
     AES-128-CBC-SHA256 0.21 GB/sec
     AES-128-GCM 1.34 GB/sec
            SHA1 0.56 GB/sec
          SHA256 0.29 GB/sec
          SHA512 0.44 GB/sec
        3DES-CBC 26.96 MB/sec
     AES-128-CBC 0.75 GB/sec
     ARCFOUR-128 0.51 GB/sec
     SALSA20-256 0.64 GB/sec

So, on my system (which has an Intel i5 Ivy Bridge and thus the AES-NI instruction set), AES-GCM processes data at about 1.34 GB/sec while Salsa20-256 with HMAC-SHA1 only manages 0.30 GB/sec.

However, it's thanks to the aforementioned AES-NI instruction set that AES-GCM fares so well. gnutls-cli has another argument to turn off hardware acceleration:

[reid@reid-pc] ~ % gnutls-cli --benchmark-soft-ciphers
Checking ciphers, payload size: 16384
     SALSA20-256-SHA1 0.30 GB/sec
     AES-128-CBC-SHA1 175.29 MB/sec
     AES-128-CBC-SHA256 136.43 MB/sec
     AES-128-GCM 169.09 MB/sec
            SHA1 0.57 GB/sec
          SHA256 0.29 GB/sec
          SHA512 0.44 GB/sec
        3DES-CBC 26.97 MB/sec
     AES-128-CBC 0.25 GB/sec
     ARCFOUR-128 0.51 GB/sec
     SALSA20-256 0.64 GB/sec

Note here that Salsa20-256 with HMAC-SHA1 outperforms AES-GCM. So, if your requirements allow you to use the AES-NI instruction set (e.g. the near-latest Intel chips), then AES-GCM is definitely the way to go. On the other hand, if your specs are more modest, you may want Salsa20-256 with HMAC-SHA1.

Another benchmarking tool is openssl speed, but it doesn't support Salsa20. Running a benchmark on AES-GCM with openssl speed -evp aes-128-gcm, I get about 1.33 GB/sec, similar to GnuTLS.


Public Key Encryption using ECDHE and AES-GCM Using a text book example, Alice and Bob want to communicate securely using encrypted messages over an insecure channel (the Internet). Alice and Bob have decided to use ECDH (using  ephemeral keys generated per session) and start off by each generating a public/private key pair using Curve P-256 - using SHA1PRNG  for randomness. Alice sends Bob her public key and Bob generates a secret key using Alice's public key and his private key. Alice does the same using Bob's public key and her private one.

Eve who is potentially sitting in the middle isn't able to solve the discrete logarithm problem that EC requires so isn't able to compute the secret key. If Eve was actually sitting in the middle at the right time she could have sent Alice and Bob her public key instead. I'm not sure if ECDSA plays a part here, but I have assumed that Alice and Bob would verify they are talking to each other by comparing a fingerprint of their public key through another method. Alice and Bob now have the same 256 bit secret key that they can use for symmetric AES-GCM encryption.

Question 1 - AES-128 requires a 128 bit key and AES-256 recommends a stronger ECDH Curve than P-256 - this means the secret key generated by ECDH is always going to be longer than the encryption algorithm requires. I assume the recommended approach is to use a KDF function like HKDF, but what is the security implication of taking an SHA-256 hash and using it directly for AES-256 or truncating it for AES-128 (Alice and Bob are using Java which doesn't have a native implementation of HKDF and I don't think it is a good idea to try and write your own).

Using an approved method they manage to both derive the same 128 bit encryption key. Alice starts by sending a message to Bob - she generates a 96 bit random IV (she confirms she will never use the same IV with the same key again). She specifies an Authentication Tag length of 128 bits and encrypts the message (she doesn't include any additional authenticated data). She prefixes the IV to the ciphertext and sends to Bob. Bob then recovers the IV and decrypts the message - he knows the message hasn't been modified otherwise the Authentication Tag would be incorrect.

Question 2 - What advantage does ECDSA provide in this scenario or am I mixing things up? Assuming Alice and Bob have verified the public key fingerprints belong to each other, only Bob is in possession of his private key (stored in memory for the duration of the session) - Eve is unable to encrypt a message using the correct secret key because she doesn't have the required private key? For Alice to be able to decrypt the message it must have been encrypted by Bob.

I assume the recommended approach is to use a KDF function like HKDF, but what is the security implication of taking an SHA-256 hash and using it directly for AES-256 or truncating it for AES-128 (Alice and Bob are using Java which doesn't have a native implementation of HKDF and I don't think it is a good idea to try and write your own).

HKDF(-Expand) is easy to implement if you have access to HMAC, since for short keys it is just HMAC(s, 0x01) with s the shared secret; an optional context string can be prepended to the 1-byte. However, just a hash is fine as well.

  What advantage does ECDSA provide in this scenario or am I mixing things up?

If you only need to guarantee privacy and authenticity, there is no need for adding ECDSA into the mix. AES-GCM with the shared secret from the ECDH-exchange is sufficient. However, there are two other scenarios that may make ECDSA useful here:

First, ECDSA is one way for Alice and Bob to authenticate the ephemeral keys used in the key exchange, like you suggest in the comment. If they already know each other's ECDSA keys, they can use them to sign and verify the ephemeral keys.
If they require non-repudiation, they can use ECDSA to sign the messages before encryption. With only ECDH and AES-GCM there is no way to prove if Alice or Bob wrote a particular message, since either can encrypt under the same shared key. A signature would allow Alice to prove to others that Bob said something. (Whether you want non-repudiation or want to avoid it depends on the use case.)


Where can I get the correct and precise algorithms for elliptic curve cryptography? I have been asked to implement cryptographic operations using elliptic curves. I would like to get precise algorithms for various processes like key generation, digital signature and verification. I found this link, but I just want confirmation on the algorithms provided there are correct or not. I would also like to know if there is any standard site for this topic whose information are authentic and can be trusted.

Standards for Efficient Cryptography Group has published SEC1: Elliptic Curve Cryptography (pdf) about elliptic curve algorithms. If it does not explain the mathematics well enough for your purposes, there is also Fundamental Elliptic Curve Cryptography Algorithms (RFC 6090, from IETF) you could look at.

There are a lot of issues you can run into, so hopefully this is an exercise of some kind, rather than someone expecting you to write production code from scratch. For production code I would recommend using existing libraries.


Perfect Forward Secrecy in PGP/asynchronous email Looking at the RFC for PGP email/asynchronous chat with PFS here https://tools.ietf.org/html/draft-brown-pgp-pfs-03 can anyone tell me why the following scheme is no good?

Alice and Bob retrieve each others long-term public keys. When Alice sends the first email to Bob, she encrypts her message with Bob's long-term public key, generates a one time public key and signs it with her long-term private key and includes it in her email to Bob. Bob receives the email from Alice, and when replying, uses Alice's one-time public key to encrypt his message, and also includes his reply email a one-time public key signed with his long-term private key. etc etc. Of course, one-time public/private keys are deleted once they're used to decrypt a message, just as ephemeral Diffie-Hellman keys are deleted in something like ECDHE.

This provides PFS for Bob, and basically PFS for Alice (excluding the first message of Alice).

Why is this scheme not widely-used in PGP? Is it just because key generation takes a few moments? Or that, Alice having multiple communication partners (that might take forever to reply) means storing multiple one-time private keys? (This can of course be mitigated by making the one-time private keys expire after a short time, eg., one week like with Pond).

Thoughts welcome.

(by the way, I'm not really suggesting this as a revolutionary scheme. I'm genuinely trying to understand asynchronous messaging better, and destroying this basic PGP scheme would be helpful in my understanding).

Keeping a complete history of messages/keys

Perfect forward secrecy is great to protect "stream kind" of messages, but that does not really fit what OpenPGP is (mostly) used for. Often, OpenPGP messages are sent and read from different machines, at different times, in different order. While OTR (offering perfect forward secrecy) does not rely on external mailboxes (like IMAP servers) holding messages for long periods of times, mails often are kept a long period of time, and you might want to store them in their original, encrypted form. Perfect forward secrecy does require to have a unique store of a message (or at least key) history, something OpenPGP does not require. And storing such a history would again partially counterfeit the benefits of perfect forward secrecy, anyway.

Perfect forward secrecy might simply have been too young

Finally, OpenPGP had its first revisions pretty much at the same time perfect forward secrecy was discussed first. A likely (additional) reason is perfect forward secrecy wasn't on Phil Zimmerman's scope at all at that time.


Which one is fastest? Karatsuba or Montgomery multiplication? Is there any complexity analysis between Karatsuba and Montgomery multiplication algorithms? It seems that Karatsuba is more general in the sense that is not modulo tuned while Montgomery it is. Does a also a hybrid model using Karasuba and Montogomery exists?

Summary: Montgomery only aims at modest (if any) speedup compared to classic algorithms; it is popular for other reasons. Karatsuba allows large speedups for very large parameters, but the threshold where it becomes beneficial is often not reached in cryptographic applications. The techniques can be used together.

Montgomery arithmetic is used for modular multiplication and exponentiation, a common operation in cryptography (RSA, some Elliptic Curve Cryptography systems). At the cost of some pre- and post-computation (of mostly negligible cost when the exponent is big enough to be secret), it simplifies the modular reduction steps, specifically with two benefits:

It avoids possible mis-estimation of the quotient, which in classical algorithms leads to a special case; this is beneficial from the standpoint of side channel leakage (e.g. timing attacks); and by the peace of mind it gives (the classical quotient estimation and its special case are hard to get right and test fully).
The Montgomery equivalent of quotient estimation is performed based on the low-order bits of the value to be reduced (rather than high-order), and that eases implementation of multiplication and modular reduction interleaved in the same scan of a temporary result (that interleaving technique in turn limits the width of numbers manipulated to about the size of the modulus, and reduces the number of memory accesses, compared to naively computing a full product then reducing it).

However Montgomery arithmetic leaves the cost mostly unchanged compared to a comparably good implementation using classical algorithms, accounting for both elementary multiplications and memory accesses. Modular exponentiation with $n$-bit numbers including exponent remains of cost $\mathcal O(n^3)$. More precisely, for both Montgomery and classical algorithms using $w$-bit words, interleaved multiplication and reduction, and basic scanning of random exponent: $\approx{3\over w^2}n^3$ multiply-and-accumulate with double-width result, and $\approx{6\over w^2}n^3$ memory accesses (${3\over4}$ reads, ${1\over4}$ writes).

Karatsuba multiplication is a divide-and-conquer algorithm for (non-modular) multiplication, which for $n$-bit integers reduces cost from the $\mathcal O(n^2)$ for classical multiplication to $\mathcal O(n^{\log_2 3})$, that is $\mathcal O(n^{1.58\dots})$.

Applied to modular exponentiation with $n$-bit numbers including exponent, the cost goes from $\mathcal O(n^3)$ to $\mathcal O(n^{1+\log_2 3})$, that is $\mathcal O(n^{2.58\dots})$. One of several methods for getting the benefits of Karatsuba multiplication during modular reduction is pre-computing the (non-modular) inverse of the modulus to slightly more than $n$ bits, which can be done at cost $\mathcal O(n^2)$ (thus negligible as far as $\mathcal O$ is concerned) with classical algorithms.

Karatsuba multiplication is beneficial only past some threshold for $n$. That threshold vary considerably depending on an awful lot of things. In a hardware multiplier optimized for low power, Karatsuba pays for modest $n$. In the GNU MP Bignum Library, there used to be a default KARATSUBA_THRESHOLD as high as 32 for non-modular multiplication (that is, Karatsuba was used when $n\ge32w$ with typically $w=32$); the optimal threshold for modular exponentiation tending to be significantly higher. On modern CPUs, Karatsuba in software tends to be non-beneficial for things like ECDSA over P-256 ($n=256$, $w=32$ or $w=64$), but conceivably useful for much wider modulus as used in RSA.

Karatsuba multiplication can be used together with Montgomery reduction. A good way to do so is by using big segments of arguments upon which Karatsuba multiplication is used. That could be the case for example in an implementation using Montgomery in the overall algorithm, with wide words and a wide multiplier (possibly hardware) using Karatsuba. Sometime Karatsuba is used for multiplication, followed by a separate reduction step using Montgomery; in which case the overall savings allowed by Karatsuba is less than $2$, irrespective of $n$.

I suggest Modern Computer Arithmetic for more details; or the classic but still useful Handbook of Applied Cryptography, especially chapter 14.


brute force attack on KDF vs KEY if we believe 256bit keys are secure in AES against any brute force attack, is that possible we use a KDF (convert user's weak entered password in truecrypt into a fixed AES key) with too much round and cycle to make a weak password (with All ASCII printable characters) secure as a true binary 256bit random key ? assume we want KDF proccesing don't take more than a few seconds on general today computers, how to compute relation btw KDF cycles and key's Entropy ? (what's possible length of an KDFed ASCII password which is secure as a 256 bit key ?)

There are two forms of entropy here at work. First there is "uncertainty" entropy from the user password which is typically very low (on the order of 20 to 40 bits for most passwords out there). And then, there's "computational" entropy, which is artificially obtained by forcing an attacker to do work to calculate keys.

Essentially, if you run your KDF for $k$ iterations, you'll add about $\log_2(k)$ bits of computational entropy.

This doesn't take into account the fact that not all KDF's are equal, it is just an asymptotic observation.

So, yes, theoretically, you can transform a weak password of, say, 20 bits of entropy, into a very strong 256-bit key with roughly 256 bits of entropy, but you'd need $2^{256 - 20} = 2^{236}$ KDF iterations... at this point it may be more beneficial for the attacker to try a different approach. I mean, putting aside the fact that nobody is going to wait around to compute your KDF - the iteration count has to be low enough so that normal users can't feel it but attackers can (say, half a second per KDF invocation).

Also, what do you mean by a "KDFed ASCII password"? In general, the output of a KDF is used directly into a cipher or message authentication code, not as a new password. But, given that there's 96 ASCII printable characters (I think) then each character has a maximum entropy of $\log_2(96) \approx 6.58$ bits.

So to obtain 256 bits of entropy you'll need at least $256 / 6.58 \approx 39$ characters in your password.


Why does HMAC use two different keys? Suppose $H$ is a hash function; why is $$H(k\mathbin\|H(k\mathbin\|m))$$ not secure?

See this HMAC definition. In there, indeed two keys are used and the mac algorithm is $$H(k_1\mathbin\|H(k_2\mathbin\|m)).$$ Why don't we use $$H(k\mathbin\|H(k\mathbin\|m)),$$ which has only one key?

Alas, there is no simple satisfactory answer to this question.  What I can offer is a very strong property that $m \mapsto H\bigl(k \mathbin\| H(k \mathbin\| m)\bigr)$ fails to achieve; a more pedestrian property which even HMAC may or may not achieve but is typically asked to achieve; a reason not to worry about it for any new systems; and some historical background that went into making this mess.

Random oracle indifferentiability.  The construction fails to achieve a very strong property, which is convenient for reasoning, but is perhaps stronger than needed for most protocols.  Let $H$ be a uniform random function.  For any $k$, define $F_k(m) := H(k \mathbin\| m)$; obviously $F_k$ too is a uniform random function for any $k$.  There are protocols that are secure when instantiated using $F_k$, but are trivially insecure when instantiated using ${F_k}^2$, where ${F_k}^2(m) := F_k(F_k(m))$.  (Of course, you could fix it by using $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$—a single bit distinction between the inner and outer hashes.)

This doesn't mean that the protocols are useful in the real world, although they can be contrived[1]—it just means there are counterexamples to the proposition one might hope for that any protocol which is secure when instantiated with $F_k$ is also secure when instantiated with ${F_k}^2$.

Note that the protocols may also fail to be secure with $F_k$ when $H = \operatorname{SHA-256}$, because of the usual length extension attacks on SHA-256. The counterexamples shown in [1] demonstrate that even if $F_k$ had no other attacks like length extension attacks, the mere substitution of ${F_k}^2$ for $F_k$ could cause a secure protocol to become insecure.  In contrast, as long as the key is two bits shorter than a block, the HMAC construction is shown indifferentiable in [1].  Of course, so is the much simpler $H(k \mathbin\| 1 \mathbin\| H(k \mathbin\| 0 \mathbin\| m))$.

Pseudorandomness.  We considered any fixed key $k$ above, known to an attacker.  But the usual security conjecture for HMAC is merely pseudorandomness, where $k$ is secret—this is enough to make HMAC a secure MAC that resists forgery (up to a modest number of messages authenticated[2]), and enough to securely derive secret subkeys from a secret master key using HMAC as in HKDF.  Specifically, we conjecture that if $k$ is a uniform random key, then it is hard to tell $\operatorname{HMAC-\!}H_k$ apart from a uniform random function.

As it turns out, the security story traced over the decades in the literature for the pseudorandomness of HMAC for a Merkle–Damgård iterated hash function like MD5 is extremely complicated!  In 1996, Bellare, Canetti, and Krawczyk first tried to address it[3] (actually, just the weaker MAC security, not the stronger PRF security) for a double-key variant called NMAC, under the assumption that the underlying compression function is a PRF and is collision-resistant; they then conjectured that deriving two keys from one by ipad and opad oughta be good enough.

For MD5 and SHA-1, the assumption of collision resistance turned out to be unrealistic.  In 2006, Bellare revisited the question without assuming collision resistance[4], but with a very complex proof and non-tight bounds that make it unclear concretely how many messages are safe to authenticate with HMAC.  They also addressed the security of HMAC's key derivation, but only by assuming that the compression function resists a certain class of related-key attacks—which essentially boils down to assuming the compression function is designed to make HMAC's key derivation secure.

The question was revisited again in 2013 by Koblitz and Menezes[5], and in 2014 by Gaẑi, Pietrzak, and Rybár[6], which incited an academic spat[7][8][9] over the definitions and assumptions that are reasonable for the underlying compression function to give a reasonable security bound for reasonable confidence in the security of HMAC.

The conclusion is that so far, after a quarter century of analysis, nobody has found evidence that HMAC should fail to achieve reasonable PRF security for all reasonable hash functions you might instantiate it with—but the ‘provable security’ framework provides meager confidence with very loose bounds about the PRF-security of HMAC in terms of the PRF-security of the underlying compression function.  What does this say about $H(k \mathbin\| H(k \mathbin\| m))$ instead, or $H(k \mathbin\| 0^b \mathbin\| H(k \mathbin\| 1^b \mathbin\| m))$?  Who knows!

The bright side.
Today, ‘hash functions’ like BLAKE2 and SHA-3 are designed so that the prefix construction $H(k \mathbin\| m)$ makes a secure PRF, and come with built-in PRF modes, keyed BLAKE2 or KMAC, with a theorem relating the security of the PRF to the primitive.  So there is essentially no reason to worry about HMAC for any new designs like BLAKE2 or SHA-3.

Historical background.

Kaliski and Robshaw first proposed $H(k \mathbin\| H(k \mathbin\| m))$ in 1995 for IPsec[10], along with $H(k_1 \mathbin\| H(k_2 \mathbin\| m))$ and $H(k \mathbin\| m \mathbin\| k)$, the last of which is sometimes known as ‘envelope MAC’.  They picked MD5 because it was new and exciting at the time, and chose these structures to thwart length extension attacks on MD5, and included heuristic security conjectures for the compositions.  These heuristics led them to consider deriving $k_i = H(k \mathbin\| i)$ for the two-key case, but they didn't propose it.

Curiously, they were unconcerned with collision attacks on MD5, whose first hints of practicality came the very next year[11], but they were concerned with preimage attacks that might reveal $k$ given $H(k \mathbin\| H(m))$—which is still infeasible today, which should indicate the level of rigor that went into these proposals.
Shortly afterward in 1995, Preneel and van Oorschot described specific attacks on $H(k \mathbin\| H(k \mathbin\| m))$ and other constructions[12], where $H$ is an iterated Merkle–Damgård construction.  The attacks don't mean the construction is completely insecure, per se—it just indicated that the cost is less than an ideal MAC.

The crux of what they observed is that if a MAC is constructed by $g(f(\cdots f(f(iv, m_1), m_2)\cdots, m_n))$ for random functions $f$ and $g$, it's collisions in $f$ that spell trouble because they can be extended into collisions of longer messages.*  The worst cases are when $g$ is a permutation, which means collisions in $H$ are guaranteed to imply collisions in $f$ which you can turn into many other collisions.

The paper is written in an older style that is a little unfamiliar to the modern norms of cryptography literature.  It is phrased as a collection of examples of attacks on the MAC, with cost analyses, rather than as bounds on success probabilities of all possible cost-limited attacks.  It concludes with a somewhat baroque construction MDx-MAC that heuristically seems to avoid the attacks.

I won't go into details, but MDx-MAC involves deriving multiple subkeys with ‘envelope MAC’, swapping out the underlying hash function's initialization vectors, changing the constants inside the compression function, etc.—not a very satisfying way to compose a MAC out of a primitive like MD5.
Later in 1996, Bellare, Canetti, and Krawczyk proposed HMAC[13] as we know it today in, e.g., RFC 2104, and offered a preliminary analysis[14] by way of an intermediate two-key construction $\operatorname{NMAC-}\!H_{k_1,k_2}(m) := H_{k_1}(H_{k_2}(m))$.  They showed, loosely, that if $H_{k_1}$ is a secure MAC of short messages, and $H_{k_2}$ is collision-resistant (under the somewhat obscure term ‘weakly collision-resistant’; the corresponding ‘strongly collision-resistant’ means ‘second-preimage-resistant’), then $\operatorname{NMAC-}\!H$ is a secure MAC of long messages, by setting a bound on the forgery probability of $\operatorname{NMAC-}\!H$ in terms of the forgery probability of $H_{k_2}$ and the collision probability of $H_{k_2}$.

Note that the double-length key does not imply double-security of NMAC; it just means NMAC needs twice the key material to attain the security attained by an ideal MAC with a single-length key.  One could imagine instantiating NMAC by taking MD5, and using $k_1$ and $k_2$ instead of the standard initialization vector.  But Bellare et al. figured that people wouldn't want to modify the existing MD5 code they had, so they suggested another approach: use $H((k_1 \oplus \mathrm{opad}) \mathbin\| H((k_2 \oplus \mathrm{ipad}) \mathbin\| m))$.  However, they only heuristically conjectured the security of HMAC in relation to NMAC.

* This idea can be taken on its face to suggest a construction for MACs: pick a universal hash family $f_{k_1}$ which merely has low collision probabilities (but from which two outputs, if revealed directly, might trivially determine $k_1$ and enable finding collisions, like Poly1305); pick a short-input, short-output pseudorandom function family $g_{k_2}$ to conceal the output; and use $g_{k_2}(f_{k_1}(m))$.  Universal hash families have the advantage that can be extremely cheap to evaluate, e.g. by dot products or Horner's rule in a finite field.  (It might even be safe to use $k_1 = k_2$, but I don't know!)  Though Preneel and van Oorschot's ideas might have suggested this structure, it attained no practical significance to my knowledge until the development of AES-GCM-SIV decades later[15], by Shay Gueron and our own Yehuda Lindell.


NewHope and NIST's Post-quantum standardization Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules.

Is being a ring-based KEM contributed to their elimination?
In this case, is there any recent development in cryptanalysis on ideal lattices that can pose danger in the future?
Even if this is the case, isn't Falcon also a ring-based signature scheme? I am confused by this.

From Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process

3.12 NewHope
NewHope is a KEM based on the presumed hardness of the RLWE problem. At its core is Regev’s original idea for public-key encryption from plain LWE but specialized to a power-of-2 cyclotomic ring structure, enabling smaller ciphertext and key sizes as well as fast computations via NTT. CCA security is achieved by a standard flavor of Fujisaki-Okamoto transform and is supported by proofs in the classical and quantum random oracle models. Among all LWE-based lattice submissions, NewHope (and other RLWE schemes) can be viewed as the most structured, with MLWE being an intermediately structured case and plain LWE being the least structured
case. As a result of this structure, the scheme has very strong performance for nearly all applications.
In a technical sense, the security of NewHope is never better than that of KYBER. A recent paper gives a highly parameterizable, essentially linear-time reduction from RLWE to MLWE
. If that reduction is specialized to the case of NewHope, one finds the following: the reduction takes RLWE instances and outputs an MLWE instance; it is modulus-preserving; it is “almost” sample-preserving; it is error distribution-preserving; and it translates the ring dimension for RLWE into the product of ring-dimension times module-rank for MLWE. As
such, any attack against an underlying MLWE instance implies a bstantially similar-cost attack against NewHope’s underlying RLWE instance. There are a few minor caveats. However, NIST does not expect that these issues will substantially change the relative concrete security situation of NewHope and an MLWE scheme (like KYBER) that is indicated by the presence of such a tight and efficient reduction.
Further, NIST observed that the CoreSVP strength estimates of NewHope and KYBER are substantially comparable, and KYBER was slightly more efficient in most benchmarks [1] <a href="https://csrc.nist.gov/CSRC/media/Presentations/pqm4-testing-and-benchmarking-nist-pqc-on-arm-cort/images-media/kannwischer-session-9-paper-pqc2019.pdf" rel="nofollow noreferrer" title="pqm4: Testing and Benchmarking NIST PQC
on ARM Cortex-M4">[2]. Specifically because of the relaxation in algebraic structure, KYBER naturally supports a category 3 security strength parameter set, whereas NewHope does not.
Despite the numerous strengths of the NewHope KEM proposal, NIST developed a slight but clear preference for KYBER and for low-rank MLWE schemes over RLWE schemes for the KEM application setting. Therefore, NIST did not select NewHope to continue into the third round (Bolds and links are mine, except the recent paper link that was original)

Like the AES selection, the performance is an important metric when the cipher suites are close to each other or passing the required bounds.
For the categories see this answer, or the NIST original page on Post-Quantum Cryptography: Security (Evaluation Criteria)


Does the GCM authentication tag need to be protected? I am just learning about the GCM mode of AES and I'd like to start using it in my software.  However, I have a question about its use.  As I understand it the output of a GCM encryption operation is the ciphertext plus an "authentication tag."  I know that the key needs to be guarded from discovery, but does this authentication tag need to be protected like the key does?  Or, would it be safe to prepend the ciphertext with the tag and IV and then send that whole blob through unprotected channels?

The GCM authentication tag doesn't need to be encrypted. Just attach it to the ciphertext in the clear.

A very quick intuitive justification:

It's an authentication tag derived from the ciphertext, it doesn't contain any sensitive information itself.
The security of the GCM model assumes the tag is left in the open. (The GCM spec, SP 800-38D, shows the auth tag output in the clear, see section 7.1.)


Blake2: truncate 512-bit hash is safer than 256-bit by Config? I need to calculate 256-bit hash in my code, using BLAKE2.

I know I can set BLAKE2 to generate itself a 256-bits hash for any data but I´m curious to know what can be safer and faster:

1- Create the 256-bit using Blake2Config module; or
 2- Truncate the normal 512-bit result getting the leftmost 32 bytes (256 bits).

In a first time, I guess getting the leftmost 32 bytes can be safer and not so slower than get 256-bits from Blake directly.

Am I wrong?
Thanks for any comments.

You should always use config options to select the output size of a hash function.

If you need a standard output size (e.g. 224, 256, 384, 512 bit) use the recommended parameter set.
This mainly applies to standards like SHA-3, where if you use SHA-3-256 you'll get a different (more standard output) than with "Keccak-256", SHA-3-512/256 and SHAKE128-256, which all use something called "domain seperation" (i.e. append a specific byte sequence to the input to get different hashes).

The reason for the first statement is the following:
The config option is always equally good as / better than the manual truncation. In worst case (e.g. SHAKE) it's just simple truncation of an infinitely long key stream and thereby exhibits the same security properties as manual truncation. In best case (e.g. Skein) the selected output size will influence the output, i.e. Skein-256-256 will give a completely different output for a message $m$ than  Skein-256-255 will. Obviously this is more secure (and usually not less fast) as it will guarantee you that $Trunc(H_{d}(m),t)\neq H_t(m)$ which may be a desirable property (although rarely needed).

Blake2 corresponds to the second case (i.e. the digest size affects the output). The requested digest size is used as the initial internal chaining value (right after the IV) along with a static constant and the MAC-key (if used). And thereby it affects the hash as much as the IV does which means Blake2b-32 will be vastly different from Blake2b-64 for the same message. This can be found in RFC 7693 on page 4 (variable name) and page 9 (usage of hash size).


Are there any Javascript CSPRNGs? I'm writing some software that requires the use of a CSPRNG with javascript for use in the browser and I'm wondering what libraries are available. Crypto-js doesn't seem to have a CSPRNG I can directly call (unless I missed it?). I've looked through the Stanford crypto js library, but I'm uncertain how much analysis this code has gotten. http://bitwiseshiftleft.github.io/sjcl/doc/symbols/sjcl.random.html

They appear to be implementing Schneier's Fortuna: http://sourceforge.net/projects/fortunaprng/

I've also seen https://www.clipperz.com/open_source/javascript_crypto_library/.

My question is there a well vetted crypto js library that has a well designed CSPRNG that generates values independently of some browser support? Or with a standard all modern browsers implement? And where is the entropy source? I'm used to crypto with languages like java and C++, not this fragmented world.

I would try to avoid doing any cryptography using javascript… but that's just my personal opinion.

Anyway, if you really want to walk the Javascript path, you could skip the libraries and take a look at the window.crypto.getRandomValues() function, as long as you can live with the fact that it's an experimental API and not yet supported in all browsers… it should work on current versions of Firefox and Chrome though.

And for Opera, there's Math.Random() which has been implemented as a CSRNG. But you should be aware that Math.Random will only be a CSRNG in Opera (only in Opera, not any other browser!!!), and that the function will only return 53 bits of entropy on each call.

Besides that, I don't know of any further CSRNGs being available in Javascript, or in Javascript libraries.

EDIT

Some stuff that might help you find solutions to your quest:

"Symmetric Cryptography in Javascript - Stanford Crypto Group" mentions (among other things) entropy-collection for crypto-purposes,
and some sites out there (like https://www.grc.com/r&d/js.htm ) practically show entropy-collection for crypto-purposes using somewhat similar solutions as mentioned in the above paper.


Efficient arithmetic Hash function Modern hash functions are considered to be efficient to calculate by boolean circuits (i.e their implementation are using bits- operations).

I'm looking for a cryptographic hash function, that can be efficient calculate by arithmetic circuits (i.e they use OR and AND gates (or $+$ and $\cdot$ gates) and work over $\operatorname{GF}(q)$.

After bit of search, I found MASH-1 and MASH-2 constructions, but they seem to include the $\text{xor}$ function that I'm trying to eliminate.

You could try Ajtai's hash function:

What is Ajtai's hash function?
Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given by
$H(\vec{m}) = A\vec{m} \mod q$

If you're not comfortable with linear algebra (and perhaps lattices too) it might be more challenging to implement than something like SHA256.
As for the efficiency, that depends on your definition of "efficient". I doubt it will compete with something like SHA256/SHA512/BLAKE2 for speed; But to be fair, few algorithms will beat BLAKE2.
Note
You will need to take extra care to ensure that the implementation functions in constant time. With bitwise operations, this is significantly easier to accomplish, which is one motivation to use them.


Looking for cipher that uses one ciphertext I'm new to Cryptography so please free to edit my question for clarity and add the appropriate tag.

I'm trying to research if the following is possible. Suppose

John has a message that he encrypts to share with more than one
recipients.
The message is different, i.e. it's unique to the recipients
(though the recipients don't know that).
The recipients must each be given a unique password so as not be
able to decrypt each others message.

Questions (sorry for more than one question, but they're related):

What approach should I take? Links to references or further reading
will be appreciated
Is the one encryption with different decryption the wrong approach to
achieve goal 3? What approaches would you suggest?

The objective are two fold:

allow a teacher to easily (hence 1 ciphertext) encrypt "answers to exam questions" (text and
binary data e.g. images) to distribute to selected students. Reason
for not allowing anyone outside of the selected students is to
prevent students who haven't taken the exam to know the answer thus
allowing reuse of the exam questions.
allow students to see teacher's comments and feedback specific to that students' attempted answers. Since students answered differently, the students need not share the same password and are discouraged from using the same password. This also helps teacher track which students leaked answers to future students.

Thanks

Update: I've bought Bruce Schneier's book to learn up on terminology and concepts so I won't be at a loss with terms like ciphertext.

There are several systems that sound vaguely similar to your description.
Would either one (or both) of the following systems work for you?
If not, what exactly about systems is unsuitable for your application?

deniable encryption

You give a unique key to each of a bunch of people.

You think up a unique plaintext message intended for one and only one person.

Later, you publicly publish some huge encrypted file (one ciphertext).

Each person uses their own unique key to extract their own unique plaintext message from that file.

It's not possible for any one person (as long as everyone keeps their own key secret), or even several of the intended recipients working together, to find out if there are any other messages in the huge encrypted file, much less exactly how many messages there are or what exactly the other plaintext messages say.

deniable encryption

File intended for several recipients

Each person has a unique key.
(Typically each person has their own private key, generates a public key from it, and each person publishes the public key or gives you their public key some other way).

You think up a plaintext message you want to send to some, but not all, of those people.

You make up a completely new one-time symmetric key that no one else could possibly know.
You encrypt the plaintext message with this new key, making one large file.
You encrypt and re-encrypt the one-time key multiple times, each time with the key (typically the public key) of one of the intended recipients.
You end up with lots of short files, one for each intended recipient,
and one large file that is the same for everyone.
The standard OpenPGP system archives that large file and all the corresponding short files together into one slightly larger file.

Then you publish that slightly larger file (one ciphertext).

Each person uses their own unique key to extract the one-time symmetric key, and then uses that key to decode the large file.

Then every one of the intended recipients knows there is one and only one message in the large encrypted file, and they all know they are all reading exactly the same message as all the other intended recipients.

It's pretty obvious how many intended recipients there are for a file in OpenPGP format, even to people who are not a intended recipient.
But there are work-arounds to camouflage exactly how many (other) recipients there are, even to someone that is a intended recipient and can decode the file into readable plaintext.

" Hash decrypts key, key decrypts cipher... why? "

" https://security.stackexchange.com/questions/8245/gpg-file-size-with-multiple-recipients "

Information leakage from the ecryptfs filesystem

" How can two different passphrases unlock the same content? "


cp-abe public key, access structure I have three questions regarding CP-ABE:

1) Is it correct to assume that in this scheme there is only one public key? Private keys are generated based on one's attributes that I do understand, by the authority.

Previously I thought I would be able to generate one's public key based on one's attribute (identity ID for example) and encrypt data with one's public key which I generated based on recipient's ID. But now I see it was wrong thinking, you need to encrypt data with a public key, which is only one throughout the lifetime of the system, and the encryption mechanism just takes into account the values of attributes which you've specified. Is that correct?

2) If above holds true and there is only one global public key based on a global secret then I assume there's no way for message originator to sign his message under this scheme. So that a recipient could verify that the message originator is really the one in possession of a given attribute (such as Id). I'm thinking of ways of implementing authentication under this scheme.

3) If one encrypts a message under specific access structure parameter values are these values in plaintext? I mean if one encrypts a message under attribute ID value '11' is everyone else able to see who the recipient actually is? I mean are they able to read the value '11'.

1) Is it correct to assume that in this scheme there is only one public key? Private keys are generated based on one's attributes that I do understand, by the authority.

No, each attribute is a public key. When you are encrypting a message, you form the access policy using the public keys of the various attributes needed from your policy.

  2) If above holds true and there is only one global public key based on a global secret then I assume there's no way for message originator to sign his message under this scheme. So that a recipient could verify that the message originator is really the one in possession of a given attribute (such as Id). I'm thinking of ways of implementing authentication under this scheme.

The above does not hold true, but I wanted to comment. Researchers have developed other primitives for attribute based signing. There has also been research published on attribute based signcryption, which combines the two.

  3) If one encrypts a message under specific access structure parameter values are these values in plaintext? I mean if one encrypts a message under attribute ID value '11' is everyone else able to see who the recipient actually is? I mean are they able to read the value '11'.

Under the original constructs, the access policy was public. So if you got a hold of a ciphertext and the policy, you could determine what attributes are necessary for decryption. Since then, researchers have developed methods to allow you to hide or keep private certain attributes in an access policy.


Would XOR'ing two Argon2 keys add extra security? When a user registers on the app, they need to provide a password they create and we provide them with a randomly generated passphrase (e.g. Apple Cat Ladder Fire). We then use Libsodium's crypto_pwhash() to generate a key for both the user's password and the generated passphrase.

Since most users will use a low entropy password, the goal was to combine it with a higher entropy source to derive a master key using the crypto_kdf_derive_from_key() function. This master key only exists to wrap/unwrap the user's private key.

I was wondering if XOR'ing these two keys actually has any benefit or am I chasing my own tail?

I also added the XOR function I wrote in Kotlin (There isn't a native implementation that I'm aware of) to see if I'm actually XOR'ing the keys properly.

fun xorKeys(keyOne:ByteArray, keyTwo:ByteArray): ByteArray {
    // Check to make sure both keys are the same size
    if (keyOne.size != keyTwo.size)
        throw Throwable("Key sizes don't match")

    // Create a new key handle
    var newKey = ByteArray(keyOne.size)

    // XOR individual bytes
    for (i in keyOne.indices) {
        newKey[i] = keyOne[i] xor keyTwo[i]
    }

    // Return the new key
    return newKey
}

That sounds convoluted.

The server-generated passphrase is essentially an extension to the client password. So you may just concatenate both (with a proper delimiter, or with their respective sizes being included) and hash the whole thing.

Also, from a usability perspective, the passphrase is inconvenient (and useless when using a password manager). You may use the user's email address as an extension instead.


Multiple NTRU public keys for the same private key? An NTRU public key is generated essentially by multiplying the inverse of a polynomial $f$ by a polynomial $g$. The polynomial $f$ is the private key; $g$ is discarded.

My question is: Is it insecure to hand out multiple public keys for the same private key, i.e. using the same $f$ but different $g$'s?

According to current knowledge, handing out multiple public keys (with independent numerators) for the same private key $f$ is not insecure, as long as the parameters are instantiated appropriately.  There is some small loss in concrete security, but nothing like an efficient attack is known.

The standard NTRU lattice for just one public key $h$ is \begin{equation} L_h = \{ (u,v) : u \cdot h = v \pmod{q} \}, \end{equation} and $(f,g) \in L_h$ is a lattice vector that is "unusually short" relative to what the Gaussian heuristic predicts for a "random" $2n$-dimensional lattice having the same determinant $q^n$ as $L_h$.  Essentially, this gap controls how hard it is to find the secret key using lattice reduction (smaller gap means harder to break).

With multiple public keys $h_i = g_i \cdot f^{-1} \pmod{q}$ that share a private key $f$, we can define a similar lattice
\begin{equation} L = \{ (u, v_1, \ldots, v_t) : u \cdot h_i = v_i \pmod{q} \}.
\end{equation}
This $(t+1)n$-dimensional lattice has determinant $q^{tn}$, so the Gaussian heuristic predicts a minimum distance of $\approx q^{t/(t+1)}$, yet
 $(f,g_1, g_2, \ldots, g_t)$ is an "unusually short" lattice vector in $L$.  The gap is typically larger than in the single-key case, making it concretely somewhat easier to find the secret key.  But as long as the gap is not huge (e.g., polynomial in $n$) and the dimension is large enough, algorithms like LLL/BKZ won't be able to find the secret key in any feasible amount of time.

Another reason is that, informally, from one public key $h$ we can generate many public keys $h_i$ having the same secret key, by multiplying $h$ by random small $g_i$.  The resulting public keys won't be distributed like "true" keys, nor will they be independent, but this at least give some intuition why it's hard to find the secret key from many public keys.

It's worth remarking that there's a close similarity here to LWE, where one can get an unbounded number of noisy random inner products with a secret vectors, and the number of such samples does not have a major effect on hardness (though it does have some).


order of elliptic curve divisible by prime Why order "u" of an elliptic curve "E" defined over a finite field "GF (q)" (u = | E / GF (q) |) must be divisible by a large prime number r to be appropriate for cryptographic purposes?

You want to work in a large subgroup of prime order because you want that for the ECDLP in the subgroup you are working in the generic bounds for solving the ECDLP (only square root attacks) apply and thus the security parameter can be chosen accordingly.

If you would work in the entire group the ECDLP is attackable by algorithms such as Pohlig-Hellman, Pollards' $\rho$ method or the babystep-giantstep algorithm. Additionally one avoids curves (such as supersingular ones) that are susceptible to the MOV and SSSA attack (such that you can even use subexponential algorithms).


Diffie-Hellman based password challenge response scheme A very commonly used (examples: HTTP digest auth/CHAP/Kerberos) authentication scheme is something that looks like:

Setup.

Client and server both know a password $p$.

Authentication.

Server sends a random challenge $\alpha$.
Client computes $r = \text{KDF}(p || \alpha)$ and sends $r$ to the server.
Server computes $r' = \text{KDF}(p || \alpha)$ and checks $r' \overset{?}{=} r$.

This scheme is also described in other questions (example).
Now this scheme has the disadvantage that the server needs to know the plaintext password. Could we make a public-key-based scheme for challenge response authentication?

For example, we could use elliptic curve arithmetic:

Setup.

Client has a secret password $p$ (with reasonable entropy) and from this derives a key  $k$ using a hash function.
The client computes $[k]P = Q_k$ and the server will store this value as the user's public key.

Authentication.

Server sends a random challenge $Q_\alpha = [\alpha]P$.
Client computes $Q_s = [k]Q_\alpha$ and sends $Q_s$ to the server.
The server computes $Q_s' = [\alpha]Q_k$ and checks $Q_s' \overset{?}{=} Q_s$.

Does this scheme work? Why would most systems use HMAC-based scheme instead?

First off, what you are trying to construct here is called an augmented or asymmetric password-based key exchange (aPAKE). As for your concrete construction:

  Does this scheme work?

Yes, it will be functionally correct.

Does it actually achieve the security guarantees of an aPAKE scheme? No, an attacker can look at the transcript, see $Q_s=[k]Q_a$ and knows both $Q_s$ and $Q_a$ and thus can just off-line brute-force the password.

The first (symmetric) scheme you mentioned suffers from the same problem.

  Could we make a public-key-based scheme for challenge response
  authentication?

This is what aPAKE schemes do, the most notable protocols are:

the Secure Remote Password Protocol (SRP), mostly because it was first to be standardized in RFC 2945.
OPAQUE which is the current state-of-the-art when it comes to (simple) aPAKEs.
If you also want to assume an auxilliary 2nd device for the user, OpTFA is the state-of-the-art.
If the user "only" has a device capable of running an (EC)DH key agreement (like a smartcard), then PTR-PAKE is the best you can get.

Example implementations (in C) of OPAQUE and PTR-PAKE can be found in libsphinx.


Attack on AES-CBC with small pool of IV Let's assume that for encryption with AES in CBC mode we have $IV\in \{0\}^{113}||\{0,1\}^{15}$.

I know that if we can predict next IV with 100% probability there is attack that completely breaks encryption. Then if we randomly choose IV as prediction, we have $\frac{1}{2^{15}}$ probability of correctly guessing next vector.

Is there a better CCA or CPA for this weak IV? How many queries on average and at most would it take?

If the goal is to distinguish the encryptor from random, the obvious thing to do is to ask for $\sqrt{2^{15}}$ encryptions of the same plaintext.  Assuming that each encryption uses one of the $2^{15}$ allowed IVs randomly, then with good probability, two separate encryptions will use the same IV (and thus result in the exact same ciphertext).  This is rather better than the $\frac{1}{2^{15}}$ result you get from trying to predict the IV.

Now, if you want something better than a distinguishing attack, well, consider this attack model: the attacker has a ciphertext block $C$ where he has partial information about the corresponding plaintext $P$, namely, he knows the initial 113 bits, and has no information about the remaining 15.  The attacker wishes to recover the remaining 15 bits, and is able to inject chosen plaintext, and is able to see in the ciphertext the IV that the encryptor selected.

What the attacker can do is inject a series of chosen plaintexts with the first 113 bits being the plaintext $P$ he knows, and the last 15 bits being 0 (arbitrary works, 0 makes it a bit easier to explain).  The encryptor will select a random IV; if the random IV he selects happens to have the exact same last 15 bits as the unknown plaintext, then the resulting initial ciphertext block will be the challenge ciphertext block $C$ (and so, by examining the IV that the encryptor used, the attacker now knows the value $P$).

For each submitted plaintext, there's a probability $2^{-15}$ of the random IV being 'right', and so this takes an expected $2^{15}$ plaintext queries to succeed.

In contrast, in this attack model, if we assume that the attacker can predict the entire IV, he could recover the plaintext with an expected $2^{15}/2$ queries, and so the attacker not knowing the last 13 bits only reduces the efficiency by a factor of 2.


Encrypting AES in ECB mode I'm fairly new to cryptography and am starting to understand this weird art of Mathematics and theory. One thing I am trying to understand and do is encrypting a plaintext into ciphertext using AES in ECB mode. For example, I want to encrypt the following plaintext: "Lucozade".

Would be great if someone could help me out with this as I am not sure how to integrate AES in ECB mode.

Here are some things to keep in mind

AES encrypts bytes, not characters. So you have to transform your plaintext into bytes. How are you going to do that?
In AES, a block is 128 bits. That is 16 bytes. If your plaintext is only 8 characters long, and each character is encoded as 1 byte, you are short 8 bytes. You can add some padding (a 1 followed by all 0's, something like that).
ECB mode is insecure (except maybe in some very specific use cases). That being said since you are only encrypting less than 1 block, and you are just doing it to try to learn AES, you shouldn't even really be concerned with a mode-of-encryption at this point. Just focus on AES running on a single block.

Without more information on where you are getting stuck, there isn't much more help I can give.


ECDSA Signature R|S to ASN1 DER Encoding question I am trying to test my understanding on ECDSA Signature r|s to ASN.1 DER Encoding for NIST P-256. I have r|s and when I convert this into ASN.1 DER in Java. I get following format:

0x30|b1|0x02|b2|r|0x02|b3|s
b1 = Length of remaining data
b2 = Length of r
b3 = Length of s

For example, suppose:

r|s = b2b31575f8536b284410d01217f688be3a9faf4ba0ba3a9093f983e40d630ec722a7a25b01403cff0d00b3b853d230f8e96ff832b15d4ccc75203cb65896a2d5

Breakdown ASN.1 DER signature format 0x30|b1|0x02|b2|r|0x02|b3|s:

3045022100B2B31575F8536B284410D01217F688BE3A9FAF4BA0BA3A9093F983E40D630EC7022022A7A25B01403CFF0D00B3B853D230F8E96FF832B15D4CCC75203CB65896A2D5

My question is - will I be getting this format always or will there be a chance that r and s could be converted and to make length of curve?

The ASN.1 DER format is deterministic; i.e. there is only a single sequence of bytes that validly encodes given $r$ and $s$ values. Mind the details, though: the encodings of $r$ and $s$ are minimal-sized signed big-endian. Since $r$ and $s$ are positive values, this means that the top bit of the first byte of each encoding must be zero. In your example, the top byte of $r$ is 0xB2, whose top bit is a 1, so an extra 0x00 byte is added, while the top byte of $s$ is 0x22, whose top bit is a 0, so no extra 0x00 byte here.

However, there are some buggy implementations that produce wrong encodings in some cases (e.g. not including a leading 0x00 byte where necessary, or adding an unnecessary leading 0x00 byte). Thus, ECDSA signature verifiers are often a bit lenient in what they accept.

The ECDSA standards (ANSI X9.62, FIPS 186-4) don't define an ECDSA signature as a sequence of bytes, but as a pair of values $(r,s)$. Encoding of signatures is considered to be out of scope; the protocol that uses ECDSA signatures is responsible for defining which encoding will be used. Different protocols used different conventions. In practice, you will encounter two main encodings for ECDSA signatures:

The ASN.1 DER format, described above. It's the one used in X.509 certificates and related protocols.
The "raw" format in which $r$ and $s$ are merely concatenated. In that format, $r$ and $s$ must first be represented as sequences of bytes with some convention (usually big-endian), possibly with some extra padding bytes (of value 0x00) so that both $r$ and $s$ encodings have the same size. The "same size" requirement is important because verifiers must know where to split. OpenPGP uses the "raw" format.