What is the direct connection between LWE and GapSVP? Learning with Errors Problem (LWE): Given a polynomial number of random noisy linear equations $b_i$ in the form of pairs

$$
 (a_i, \quad b_i = \langle s, a_i \rangle + e_i)
$$
where $a_i \in \mathbb{Z}^n_q$ are uniformly random, $e_i$ is sampled from some noise distribution such that $e_i \ll q$, and  $\langle s, a_i \rangle$ denotes the inner product of $s$ and $a_i$, find the secret vector $s \in \mathbb{Z}^n_q$.

This problem is supposed to rely on the hardness of GapSVP. In Regev's paper, he showed a complicated reduction from GapSVP. Is there a way to see the immediate connection between the two problems? What are $a_i$, $b_i$ and $\langle s, a_i \rangle$ with regards to a lattice?

Thanks!

Taking $n$ LWE samples, the associated vector $\mathbf{b} = (b_1, \dots, b_n)$ can be written as $A\mathbf{s}+\mathbf{e}$ with $A^T = (\mathbf{a}_1 | \dots | \mathbf{a}_n)$ and $\mathbf{e} = (e_1, \dots, e_n)$ a small noise vector. The vector $A\mathbf{s}$ could be interpreted as a lattice point in the lattice $\mathcal{L}(\mathbf{a}_1, \dots, \mathbf{a}_n)$, with unknown coefficients defined by the secret vector $\mathbf{s}$, and $\mathbf{e}$ is small so $\mathbf{b}$ is pretty close to this lattice point. This corresponds to a CVP/BDD-style problem, where you want to find the closest lattice vector to $\mathbf{b}$ in this lattice.

Finally, Kannan's embedding technique shows how to translate CVP instances to (Gap-)SVP instances. Quoting Hanrot, Pujol, and Stehle, at the end of Section 4:

I'm not sure if this is also how Regev reduces GapSVP to LWE, but it's probably the most intuitive way to see how CVP-style problems and SVP-style problems are usually related.


Encrypting structured data (text) with RSA In "Cryptography Engineering" Bruce Schneier wrote:

  ... All of them come down to a single thing: it is very bad  to have
  any kind of structure in the numbers that RSA operates on. The
  solution is to use a function that destroys any available structure.

Few lines lower he mentions PKCS #1 v2.1. As I understood pkcs is about padding. Does it mean that if together with random symmetric key I have some non-random data (file name) I have to xor it with some pseudo-random byte stream before encryption?

p.s. The question is crossposted from https://stackoverflow.com/questions/40194332/encrypting-strucutered-data-text-with-rsa ,  where it was voted out as off-topic since related to cryptography.

I'll assume the question is about RSA encryption of a message consisting of a random symmetric key and non-random data (a filename).

The question's "before encryption" could be referring to before using:

Textbook RSA encryption, that is changing message $m$ to $m^e\bmod N$, where $(N,e)$ is the RSA public key.
PKCS#1 v2.1 RSA encryption, that is with OAEP padding.
Hybrid encryption, which is RSA encryption as most usually practiced: RSA is used to send the secret key of a traditional symmetric cryptosystem.

What is meant by Bruce Schneier's quote is that (1) could be bad; and before applying the transformation in (1), a transformation should be applied to $m$ that makes it much like a random integer somewhat less than $N$, with little other structure.

Yes, that can be achieved with "XOR it with some pseudo-random byte stream", provided that the receiver has a way to recover than pseudo-random byte stream and undo the XOR; and that byte stream has approriate length, so that the result of the XOR is somewhat less than $N$.

In fact, this is part of what OAEP performs, and thus is built in (2). There's a caveat though: the maximum payload in (2) is reduced compared to (1). For example, with a 2048-bit (256-byte) RSA key, (1) could encipher any payload of $256-1=255$ bytes, when OAEP using SHA-256 (a 32-byte hash) limits the payload to a maximum of $256-2*32-2=190$ bytes. In both cases, the ciphertext will be 256 bytes. Thus that works for a moderate symmetric key (e.g. 16 bytes) and a small filename (up to 174 bytes). OAEP decryption will restore the payload's length.

Another option would be (3), which removes any size limit, at the price of a larger ciphertext, and often of leaking the payload's size (here, the filename's length).

Notice that (1) and (2), and many forms of (3), will not insure that what's deciphered is genuine; that's the job of authenticated encryption, which requires something secret on the sender side (beyond the message to send), contrary to RSA encryption.


Secure CSPRNG's for cryptographic keys In reality, it is not practical for ciphers such as stream ciphers and AES to generate keys using a TRNG, so instead they have to use a CSPRNG. As an LFSR can generate pseudo random numbers,so can a LFSR be adapted so it can be used as CSPRNG, and what are the other ways to construct a CSPRNG.

LFSR as such isn't a CSPRNG. There are diverse CSPRNGs, see crypto textbooks, also A. Menezes et al., Handbook of Applied Cryptography (freely available online). I have a code for a CSPRNG based on RSA, see Ex. 5 in s13.zetaboards.com/Crypto/topic/7234475/1/


Is Computational Indistinguishability quantifiable? Is Computational Indistinguishability quantifiable?
I know that the success probability should be negligible, which however seems to be somewhat ambiguous.
Is it possible (and usual) to say that given encryption scheme is said to be something like it is computationally secure with some probability?
I've been using an IND-CPA secure public key crypto so far.

The answer is yes.
Formally, when a scheme is proven secure (relatively to a specific security game), a theorem states that no adversary $\mathcal{A}$ couldn't win the security game except with a probability $f(\lambda, m_1, m_2, \dots)$.
With $f$ a function in $[0; 1]$, $\lambda$ a parameter called the security parameter (in general when $\lambda$ increases $f$ decreases as the efficiency (in time and space) of your protocol) and $m_1, \dots m_n$ which determines (or just upper bound) the power capability of the adversary: For example $m_1$ could be the number of messages seen by the adversary. And $m_2$ could be the number of generic group operation (if we are in the generic group model).
You have first to determine $m_i$ (id est: If your adversary is your nephew, the NSA, your nephew in 2050, the NSA in 3850, etc). Then you choose lambda which verifies:
$f(\lambda, m_1, m_2, \dots) <\frac{1}{2^{128}}$.
Particular case: Some result contain terms like $\texttt{ADV}^P(\lambda)$, with $P$ a well known computational problem (RSA, DH, LWE, etc). Then you have to check in the literature the best known attack to evaluate this term (or more simply which lambda is recommended).


Can sending the same plaintext twice, each encrypted with different key and IV, weaken the encryption? I'm basing code on: https://wiki.openssl.org/index.php/EVP_Authenticated_Encryption_and_Decryption#Authenticated_Encryption_using_GCM_mode

If I send the same plaintext twice, encrypting each with a different key and IV, am I compromising the strength of the encryption?

(Eve would have access to the two ciphertexts of each message, and would know that they were encryptions of the same plaintext.  Eve would not know the keys or IVs used.)

No, it would not compromise the strength of the encryption (assuming that you didn't use a key that the attacker could guess).

We can take it much further; you could give the attacker a billion encrypted messages, all being encryptions of the same plaintext.  It wouldn't matter if you told the attacker what IVs you used (or AADs, should you decide to use them), or if you used the same keys or different ones.  As long as:

You didn't pick a key that the attacker could guess; for example, you picked the keys randomly
You didn't reuse a (key, IV) pair (which in this specific case would matter if the two messages had different AADs, but it's always a good thing to remember when you're using GCM)

Then the security of the system is not weakened; the attacker would have no information (other than length) of the encrypted message, nor could he generate (with nontrivial probability) another encrypted message that would be accepted by the decryption process.


How to perform homomorphic multiplication in ElGamal? How can I compute homomorphic multiplication in ElGamal? That is: Given two ciphertexts $(R_1,c_1)$ and $(R_2,c_2)$ corresponding to plaintexts $m_1$ and $m_2$ under some public key; how can I compute a ciphertext $(R,c)$ that is an encryption of $m_1\cdot m_2$ under that same public key?

Assume we are working in a cyclic group $G$ with generator $g$ and let $A$ denote the public key in use.

From the definition of ElGamal encryption, we have $R_i = g^{r_i}$ and $c_i=A^{r_i}\cdot m_i$, where $r_i$ is some random number, for $i\in\{1,2\}$. Hence, with $R:=R_1\cdot R_2$ and $c:=c_1\cdot c_2$ (where $\cdot$ denotes $G$'s operation), we have obtained
$$ R = g^{r_1}\cdot g^{r_2} = g^{r_1+r_2} $$
and
$$ c = A^{r_1}m_1\cdot A^{r_2}m_2 = A^{r_1+r_2}\cdot m_1m_2 \text, $$
so $(R,c)$ is precisely an encryption of the message $m_1\cdot m_2$.


Questions about the ideal cipher model I've read that we can study the security of modes of operation by assuming the use of an ideal block cipher. I've also seen a paper suggesting that the ideal cipher model could be something else than an ideal block cipher.

Are there protocols relying on an encryption mode and whose the proofs have been done by assuming that this encryption mode is ideal, that is, we don't consider an ideal block cipher, but rather an ideal encryption scheme ?

Finally, what could be an ideal cipher with respect to an encryption scheme ? For a block cipher, this is a random permutation (we have an elf wich fills a table step by step to describe this random permutation). What would this elf do in the case of an ideal encryption scheme ?

The ideal cipher model is a way of modeling of block cipher (i.e. a keyed permutation family) which is very close to the modelization of a hash function by a random oracle. In fact, these two models are even equivalent (see http://arxiv.org/abs/1011.1264).

Recall that a random oracle is a "magic box" with for any new input outputs a purely random value (for repeated inputs, the oracle just repeats itself). A ideal cipher behave similarly given a new input pair (K,x), the ideal cipher outputs a random value y, with a small caveat: instead of being chosen at random for a fixed set, y is chosen among the values which have not yet been used for the key K.

Ideal ciphers can appear in security proofs to show that a mode of operation is secure with a "perfect" blockcipher. In particular, when working in the ideal cipher model, you implicitely assume that your blockcipher is secure against related-key attacks.

However, as with the random oracle model, it is possible to construct cryptographic primitives (albeit artificial ones), which are secure in the ideal cipher model and insecure when instantiated with any real blockcipher. For this reason, proofs in the regular security model (where the blockcipher keyed with a random key is indistinguishable from a random permutation) are considered to be much more representative of real-life security.

If you are interested by proofs in the ideal models (RO or ideal cipher), look for papers about indifferentiability.


Could someone please elaborate on how $(c^d \bmod n) \bmod p = c^d \bmod p$, given that $n = pq$, where $p$ and $q$ are prime numbers? I'm following this (Chinese Remainder Theorem and RSA) post, but I don't understand how
$(c^d \bmod n) \bmod p = c^d \bmod p$.
Being told that it's because $n=pq$ is not enough for me to understand.
Could someone please elaborate on that to help me fully understand what's going on here?
Any input would be GREATLY appreciated!

Well, lets see if we can go through it from the basics.
$x \bmod y$ is the unique integer $x + \ell y$ that satisfies $0 \le x + \ell y < y$, for some integer $\ell$ (which might be positive, negative or zero)  I will skip the parts that prove that, if $x, y$ are both integers and $y > 0$, then there exists such an $\ell$ and it is, in fact, unique.
Now, when we have $(x \bmod pq) \bmod p$, we can replace the inner $(x \bmod pq)$ with $x + \ell_1 pq$, we get $x + \ell_1 pq \bmod p$.  This in turn becomes $x + \ell_1 pq + \ell_2 p$.  We further note that $\ell_4 = \ell_1 q + \ell_2$ is an integer (which we will denote at $\ell_4$) [1], and so we have:
$$(x \bmod pq) \bmod p = x + \ell_4 p$$
On the other side, $x \bmod p$ is the same as $x + \ell_3 p$, that is,
$$x \bmod p = x + \ell_3 p$$
So, on one side, we have $x + \ell_4 p$, which is a value between 0 and $p-1$.
On the other side, we have $x + \ell_3 p$, which is also a value between 0 and $p-1$.
Since both $\ell_3$ and $\ell_4$ are integers, these must be the same, and hence the original values $(x \bmod pq) \bmod p$ and $x \bmod p$ must also be the same.
Then, replace $x$ with $c^d$ and $pq$ with $n$, and there you go...
[1]: BTW: this is the step where we assume that $p$ is a factor of $n$ if that is not true, then relation will not hold in general.


How to express a coin flip based random generator mathematically? I would like to know how to express a coin flip based random generator mathematically.

I have recently started Dan Boneh's Cryptography 1 and in the slides a pseudo random generator G, which outputs n-bit sequences, is defined as $G:K \rightarrow \left\{0,1\right\}^n$.

So following this I have come up with this for a coin flip:
$$
G(n) = \left\{0,1\right\}^n
$$

The idea is that n is the number of tosses and the function G will output n-bit length random numbers. The latter part with curly braces and the exponent $\left\{0,1\right\}^n$ is something I have not come across before. Is this a notation that's only used in cryptography?

Formal definitions are definitely a weak point for me so I don't know if I'm way off. Or if there's some better way to express this. Or if I'm approaching this completely wrong.

Boneh's definition of a pseudorandom generator stipulates that a PRG is a mathematical function—a mapping from an input domain to an output codomain such that the choice of argument value uniquely determines the result.  In recent programming parlance, this is what people often call a pure function, like in pure functional programming languages (e.g. Haskell)—one whose results depend exclusively on the value of its arguments, and not on the state of the program.

Coin flips clearly do not fit under that definition, because they're non-deterministic—calling the coin-flip "function" (really an imperative programming routine) twice with the same argument is supposed not to always produce the same result.  So a sequence of coin flips is not a PRG.

Mathematically, the concept we'd use to model coin flips is random variables.  The outcome of a coin flip is a random variable.  The outcome of a sequence of coin flips can also be seen as a random variable: you can describe the former as an experiment that repeatedly takes samples of the outcomes of single coin flips.


Extractability for Simulator in Malicious Model It is sometimes required while proving the security of a protocol in the malicious setting that the simulator is able to extract the witness set of the adversary, who tends to be the prover of possessing some knowledge, in the ZKP step of the protocol.

I was having issues understanding how the simulator would be able to extract the witness set without the discretion of the adversary?
If the simulator is able to do so, wouldn't that defeat the purpose that the ZKP is zero knowledge, at least to the simulator?
I also read that the witness extraction by simulator doesn't necessarily have to be probabilistic polynomial time. Can someone please elaborate on this?

Let me try. First, one thing needs to be clear: simulation and real execution are two different things. The simulator can learn something does not mean a verifier in real execution can learn the same thing. Thus the fact that a simulator can extract knowledge does not affect the protocol’s zero-knowledge property (which is about the verifier in the real execution).

Why the simulator (or more accurately the knowledge extractor) can extract the knowledge but the verifier cannot? This is because the simulator has some special ability that the parties in the real world don’t have. One example is “rewinding”: the knowledge extractor can rewind the adversary to a previous state. If you are familiar with the Schnorr protocol, you should know rewinding is used to extract knowledge there. But can a real verifier rewind the prover? No.

Then why the knowledge extractor is given such an ability? It is for the sake of writing security proofs. A secure proof of knowledge protocol means that If the prover convinces the verifier, then it must know and use the witness in the protocol. This is hard to prove in fact. So we allow a knowledge extractor with extra ability to help us so that if the witness is used, the knowledge extractor can extract it from the transcript. Thus if the witness can be extracted, we can be certain the witness is used and  the protocol is proof of knowledge.


How to determine the security in bits of a scheme? This may be a stupid question. But how would we determine the security bit of a crypto scheme?

For example, SHA2-256 offers 128 bit security due to birthday paradox, so do they measure the security bit by calculating $\log_2$ of best-known attack?

However, some scheme is defined as $(t,\epsilon)$-secure. how should we determine the security bit? some people define the security as $\log_2(t/\epsilon)$? but should it be inconsistent as $(t,\epsilon)$ can vary.

is there a standard way of measuring the security bit of a scheme?

There isn't a single formal standard, because different types of cryptosystems have different attack strategies and cost models.  For each type of cryptosystem, there usually is a standard notion of adversarial advantage: we posit a game the adversary might play, with an idealized version of the cryptosystem, or with a practical realization of the cryptosystem, and the adversary's advantage is how much more probable they are at winning the game with the real cryptosystem than with the idealized cryptosystem.

You can read more how to work with adversarial advantage in Mihir Bellare and Phil Rogaway's book, which goes into far more detail than there is space in the margin of this stackexchange note to fit.  But here's a quick overview of a few examples of the variety of adversarial advantage notions you'll encounter:

With symmetric-key authenticated encryption, the adversary is given a chance to play with devices that encrypt chosen messages and decrypt chosen ciphertexts, called oracles, and they win if either they can distinguish a random string from the ciphertext of a random message, or if they can forge a ciphertext they did not obtain from the encryption oracle that the decryption oracle accepts.  This probability is usually studied as a function of the number of queries the adversary makes to the encryption and decryption oracles, how long the messages can be, etc.

The standard attack strategy is to guess the unknown key correctly and try decryption or forgery with that, but specific constructions might admit strategies with better advantage; any AE scheme worth its salt will come with a theorem about the adversary's advantage in terms of the conjectured advantage of some primitive, like a pseudorandom function family such as ChaCha.
One-time authenticators.  The adversary is just given a single message and valid authentication tag and a verification oracle, and they win if they can produce a single valid authentication tag for another message after some number of attempts.  The forgery probability is usually a function of the maximum message length accepted by the verification oracle and the number of queries to the verification oracle.  The standard attack strategy is to make up an authentication tag uniformly at random, and the forgery probability is $2^{-t}$ if its length is $t$ bits.
Diffie–Hellman key agreement schemes.  The adversary is given a set of public keys $a_i \cdot \xi$ for unknown $a_i$ in some group $G$ and for a standard $\xi$ in some set $S$ with a group action of $G$ on $S$; a set of oracles for computing $\zeta \mapsto a_i \cdot \zeta$ for any attacker-chosen $\zeta \in S$ and each unknown $a_i$; and a set of one-way functions $H((a_i + a_j) \cdot \xi)$ of shared secret $(a_i + a_j) \cdot \xi$ values.  The adversary's goal is to compute any one of the shared secret $(a_i + a_j) \cdot \xi$ values.

The standard attack strategies are more complicated, and references for details in the elliptic curve setting can be found at, e.g., SafeCurves; in the finite field setting, index calculus dominates.  There are qualitative differences for the elliptic curve setting and the finite field setting: for the elliptic curve setting, attacking every one of a batch of targets with Pollard's rho is cheaper than attacking an individual target; for the finite field setting, there's a high precomputation cost for index calculus, after which attacking an individual target is cheap.

How does all this translate into security levels?  We take a concrete estimate of the costs of the best known attack in a sensible cost model, and consider the expected cost of an attack with nonnegligible probability of success, and then usually round to a nice power of two.  For example:

The forgery probability of Poly1305 for a single message of up to $16\ell$ bytes is $8\ell/2^{106}$, e.g. $2^{-97}$ for messages of up to a kilobyte or $2^{-87}$ for messages of up to a megabyte which presumably cost a thousand times as much to attempt as kilobyte-long messages.  We loosely round this to a $2^{128}$ security level since (a) it is well below $2^{-100}$ per block and (b) it depends on the bandwidth of the legitimate user and not on the offline costs an attacker can afford spend.
The expected cost before computing a single Curve25519 discrete logarithm is about $2^{125}$ elliptic curve additions—offline, so not dependent on the legitimate user's bandwidth.  We loosely round this to a $2^{128}$ security level because one elliptic curve addition takes a lot more than eight bit operations.

There is some confusion among some cryptographers about what the best standard attacks are; some disagreement about what cost model to use, how to formalize the costs of precomputation, and how to figure batch attacks into security notions; some uncertainty about how to address loose bounds reducing the security of a composition to the security of its primitives; and so on.

Every now and then spats flare up between academics who have frank exchanges of feelings about these subjects.  Sometimes this is reserved to the review processes of academic publications; sometimes it comes out in position papers and letters to the editor (1, 2); sometimes it is in preprints back and forth; sometimes it is on Twitter.  Whether they ever resolve their differences on the street outside the conference venue is a question I leave to the philosophers.


Security of seed from a dictionary How do you calculate the total amount of combinations in the standard 12-word seed from a 2048 word dictionary?

$log_2(2048^{12})$ which equals $2^{132}$? Is this the right way?

And what is the "minimum" sort of recommended combinations for the next 5-10 years, $2^{110}$? $2^{100}$?

The total number of possible 12-word "seeds" is $2048^{12}$ as you already noticed.

The entropy of such a seed is $\log_2{(2048^{12})} = \log_2{((2^{11})^{12})} = \log_2{(2^{132})} = 132$ bits.

Therefore, remembering such a 12-word seed is equivalent to remembering a 132-bit key.

If you want to play it safe, pick a seed with 256 bits of entropy or with 24 words. (Because $\log_2{2^{11\lambda}} \ge 256 \Rightarrow \lambda > 23.3.)$


What's the difference beteween SIDH and SIKE? I'm a semi newbie in crypto (I've had that uni course of discrete math that includes basic cryptography principles) and wanted to go a bit further in isogeny graphs.

I have downloaded the C implementation of SIDH/SIKE from the Microsoft Github page and can't understand the difference between the two. However, most of the resources I find online are either sketchy youtube videos or unreadable academic papers using terms I am unfamiliar with. Any resources/ideas would be appreciated.

SIDH is a form of post-quantum Diffie–Hellman key exchange with a non-abelian structure using isogenies. It stands for Supersingular Isogeny Diffie–Hellman. SIKE is the name of the specific submission given to NIST for standardization with a set of specific, fixed parameters. It stands for Supersingular Isogeny Key Encapsulation. SIKE is SIDH, but not all SIDH parameters are SIKE.
From their official website, SIKE is standardized in two forms: SIKE.PKE, an asymmetric encryption algorithm, and SIKE.KEM, a key encapsulation mechanism. They both support four parameter sets: SIKEp434, SIKEp503, SIKEp610, and SIKEp751. SIDH is just an algorithm and doesn't standardize any parameters. You could say SIDH is to SIKE as ECDH is to (the public key part of) ECIES.


Is clientside encryption to hide data from server safe when using SSL? I want to clarify right off that bat that I am using the SSL/TLS protocol on top of this, so I am NOT trying to implement my own protocol to send data securely. I simply want the server to be unable to read user data.

I'm trying to implement a web application that stores sensitive data. I was thinking about using some public key derivation function to generate two keys from a master password, the first key is sent to the server for verification, and the second key is kept in the browser, and is used for symmetric encryption/decryption, like AES.

The server sends the encrypted information, and JavaScript is used to decrypt that data with the second key.

I've read a lot of sources saying that clientside encryption, especially in-browser with JavaScript is very insecure, but I fail to see what insecurities this method could possibly have.

I really want to cover all my bases, so I just wanted to know if this method is still secure, and if it isn't, what I should do instead.

Client-side encryption can prevent a passive eavesdropper on the server's memory—like Heartbleed—from seeing the client's secrets.  But, if you might be concerned about any more serious compromise of the server, who delivers to the client the JavaScript code that performs encryption?


Is following MAC schemes formed by MAC schemes secure? Given two MAC schemes $\prod_1 = (keyGen_1, S_1, V_1)$ and $\prod_2=(keyGen_2, S_2, V_2)$.

$\prod_3$ runs $keyGen$ from $\prod_1$ and $\prod_2$, respectively, to obtain $(k_1, k_2)$. $\prod_3$, where $S_3 = ((k_1,k_2), (m_1,m_2))$ then runs $S_1(k_1,m_1)\rightarrow t_1$ and  $S_2(k_2,m_2)\rightarrow t_2$. And obtain $t_3 := t_1||t_2$. Would $\prod_3$ be a secure MAC?

And the follow up is when $t_3:= t_1 \oplus t_2 $, would this also be a secure MAC?

My guess is that the concatenation is secure because attackers would have no way of knowing how $t_1$ and $t_2$ is generated. For the second one, my intuition tells me that adversary can somehow swap the messages and produce a valid (m,t) pair?

In the first case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_3, m_4)$ to query the adversary $A$.

$t_1||t_2 = A(m_1, m_2)$

$t_3||t_4 = A(m_3, m_4)$

The forged MAC would be $t_1||t_4: Verify(t_1||t_4, (m_1, m_4)) \rightarrow Accept$.

In the second case, $\Pi_3$ is not secure.

We can use $(m_1, m_2)$ and $(m_1, m_3)$ to query the adversary $A$.

$t = t_1 \oplus t_2 = A(m_1, m_2)$

$t' = t_1 \oplus t_3 = A(m_1, m_3)$

$t_f = t \oplus t' = t_2 \oplus t_3$

The forged MAC would be $t_f: Verify(t_f, (m_2, m_3)) \rightarrow Accept$.

Another way to break the scheme is to reverse the message pair. $Verify(t, (m_2, m_1)) \rightarrow Accept$.


AES-GCM cipher - Nonce vs IV I am using a Python library called PyCryptodome, which offers the following API for AES-GCM ciphers:

https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html

As you see, IV is not applicable for GCM ciphers.

There are some C++ libraries that expect the user to specify the IV rather than the nonce.

Let's say that I get a message encrypted with a C++ library that uses a 16 bit IV. Later on, I want to decode this message using a Python library. Given that I know the key and the IV that was used, will I be able to properly decipher the message when I specify the nonce to be the IV?

The term for the parameter to AES-GCM that must be unique from message to message for any single key is sometimes called ‘nonce’ and sometimes called ‘IV’.

The security contract for AES-GCM requires that only that this never be repeated, and so it is appropriate to call it a nonce, meaning number used once.
In contrast, for, e.g., AES-CBC, there is a parameter for a 128-bit string that must be unpredictable in advance to an adversary, and which is usually called an initialization vector.

That's the distinction that PyCryptodome is getting at when it distinguishes the ‘nonce’ and the ‘IV’—although it says ‘IV’ for AES-CFB and AES-OFB too when really they just take a nonce.  However, in some other APIs, the corresponding parameter is always just called IV.  To be confident, you should draft some code using two different libraries—like one of the C++ libraries you have in mind—and make sure they can interoperate, and include known-answer tests with fixed keys, nonces, and messages, as test cases in your code.

Caveat: AES-GCM is best with a 96-bit (12-byte) nonce chosen sequentially as a message sequence number.  If you use a 128-bit (16-byte) nonce—as the PyCryptodome documentation wrongly recommends—it is as if you had chosen a 96-bit nonce at random, which means, because of the danger of a nonce collision, that there is a much smaller limit on the number of messages than if you had chosen a 96-bit nonce sequentially.


Can you help me understand the Common Modulus Attack in a Lucas Group? I'm trying to decrypt a message that is encrypted using a LUC encryption scheme and running into roadblocks. I know that with RSA if Alice and Bob use the same public modulus but different encryption exponents, with $\gcd(n_A,n_B)=1$ then you can find the plaintext $M$.

I'm provided $R$ (public modulus), $n_A$ (Alices public encryption exponent), $n_B$ (Bob's public encryption exponent. I am also provide two lists of packets that contain the same message sent from a third user, Carol, to both Alice and Bob. Lets call the first packet with the same message $c_{1A}=(x_A,y_A)$ (Alices packet), and $c_{1B}=(x_B,y_B)$ (Bob's packet). I assumed that I could then use the extended euclidean algorithm to find $r$ and $s$ such that $rn_A+sn_B=1$, which I did. Then shouldn't I be able to find the plain text by, $(x_A)^{-r}(x_B)^{s} \mod{R} = M$ where $x_A$ and $x_B$ are the ciphertext?

This is where I am running into problems.  Do I need to perform this operation in the Lucas group?  As it stands all of my values are scalar.

Just find the modular multiplicative inverse $x_C$ of $x_A$ using the extended Euclidean algorithm:

$$(x_A)^{-r}\equiv(x_C)^{|r|}\mod{R}$$

and

$$x_Ax_C \equiv 1\mod{R}$$

Then, once you have $x_C$, you'll be able to compute:

$$(x_C)^{|r|}(x_B)^{s}\mod{R} \equiv M$$

http://en.wikipedia.org/wiki/Modular_exponentiation


Solid summary of what encryption remains strong after recent events Following the recent government hacking (and subsequent news and fallout), I'm wondering what crypto-systems remain strong (and why) and what crypto-systems were exploited too heavily to be reliable. I'm wondering what will remain strong for the foreseeable future and why these systems were not affected (while the others presumably were).

I tried to find the information on the following and many other pages, but they were not very helpful in this case…

http://en.wikipedia.org/wiki/NSA_encryption_systems
http://en.wikipedia.org/wiki/NSA_cryptography

Perhaps someone can help me understand this.

We don't know what NSA (or any other spy agency--the US isn't the only country with code breakers) has broken.  Other than Dual EC DRBG, we are left with everyone making their best guess, just like before.  The NIST elliptic curves and the SHA2 hashes and DSA all came from NSA, but that seems to be the only real reason to suspect anything bad about them.  Neither AES nor SHA3/Keccak have anything at all to do with NSA.


How secure is it to use password as AES key? I am developing a steganography app where user encrypt any file into an audio file. The user can enter a password to protect the hidden data. The same password is converted as a 256 bit key and the hidden data is encrypted using AES. I was wondering, how secure is using password as the AES key?

Passwords are commonly used for both authentication and encryption. Sometimes this is done securely. "Commonly" is an interesting word here, because passwords are commonly turned into encryption keys in ways that do not follow good security practices, and also passwords commonly do not have enough entropy to be suitable for generating encryption keys.

Generally the term "x is only as good as y" would apply to encryption keys and passwords, such as "key is only as good as password", but the method used to convert the password into the key is more important for the majority of password choices. If you were using a long string of random characters, even MD5 could be acceptable... but you probably are using a shorter password built from real words and phrases. Let me be clear that MD5 is not acceptable to convert passwords into keys.

A 'Password Based Key Derivation Function' (PBKDF) is what is needed to convert your password into a suitable encryption key. There is debate over the specific features and properties a PBKDF should have, but its purpose is to compensate for the poor entropy of commonly chosen passwords, among other things, such as properties of the cryptographic primitives that PBKDFs are built from.

Cryptographic hash functions and block ciphers are commonly used to build PBKDFs, and they do an excellent job, but they are extremely fast and use minimal resources such as memory and cpu cores, which can be a profound advantage to an attacker. Thus a PBKDF is mainly used to slow it down, usually by iterating the primitive thousands or even millions of times. More modern PBKDFs also consume larger amounts of memory, and some may only operate quickly (for verification) by using multiple cores. A 'salt' is used as an input to the PBKDF to prevent the same password from generating the same key unintentionally when used in different situations or by different users. The salt is stored where the password would be processed in order to get the correct key.

Best practice is to use a PBKDF to generate a 'key encryption key' (KEK), then a full entropy random key is used to encrypt the data, and the KEK is used to encrypt that key. That way a password change does not require reencryption of all the data, just the key. The KEK is never stored, only used to encrypt and decrypt the data key. The encrypted data key and PBKDF salt are stored with the encrypted data.

You may not have control over the password a user enters, but you do have control over how it is processed into a key, and you may be able to make recommendations to your users as to good password choices. Attacks only get better, passwords should be as long as possible while still being memorable. Estimating password entropy is difficult, so the PBKDF is extremely important to preventing it from being cracked. If you can accurately estimate entropy you may be able to warn a user that their password may be insufficient.

You should be very open with your users about how you convert their password into a key, it is "common" for secrecy of the method to be associated with extremely bad security practices, and more and more people are starting to realize it (due to an ongoing string of hacks and stolen password databases with lots of press coverage). Additionally, if an individual that understands cryptography can be confident in the security it provides, they may be inclined to recommend the product. I certainly would be.

Note that security is only as strong as the weakest link. If you are using an excellent PBKDF but have poor programming leaking key material into virtual memory, the product is not secure. Do not rely on good cryptographic components to do the work of security for you, it is more complex and difficult than that. It is an entire system. Sorry for the long answer.


Is using SHA256 to extract entropy from a p-rand nonce a good way to create keying material? Using $SHA256(N)$, where $N$ is 64 bytes of output from the Microsoft Windows CryptGenRandom function. Are there any known vulnerabilities with using this method to create key material? Should $N$ be more than the SHA256 block size of 64 bytes? Aligning to block size means 2 passes through the (internal) hashing function, (block and finalize), is this enough?

CryptGenRandom is supposed to produce cryptographically strong random numbers, so you shouldn't need to process it before using as a key.

However, if you want to treat it as of suspect quality, I would go with SP 800-90B recommendations: assume it has entropy at least half the bits, so request double what you need. Then run it through HMAC with a suitable hash function.


How to use AES correctly in BPS Format Preserving Encryption I have several questions on using AES 128bit in the BPS format preserving encryption

Which modes are acceptable?  (Should the block cipher used at each round be deterministic (ECB) or probabilistic (CBC, CTR etc)

What IV to set?  Can I set it to the constant zero?

AES is directly used as a block cipher without a mode of operation in BC / BPS.

This would be identical to ECB mode for one block or CBC mode for one block and a zero IV in the case that the block cipher itself is not directly available. In that case you should not pad or remove a full block of padding if padding cannot be avoided. CTR of one block with a zero IV/nonce would also work.

But basically the answer to "what modes are acceptable" is: none. In that case the IV is also not applicable. The tweak can be seen as a specific kind of IV. Likewise you could see BC itself as a mode of operation for the block cipher.


Why does Salsa20 algorithm require incrementing word[8] and word[9] after producing cipher text message I'm trying to get understanding of Salsa20 algorithm. There is an official specification from Daniel J. Bernstein at link. Everything in spec is clear and I could write an implementation on Swift.

But I met Salsa20 cipher algorithm implemented by other developers Crypto and TLS for C++11 , Salsa20 written on Python
The developers perform some operations with words at positions 8 and 9 after generating ciphertext message:

I didn't saw these operations in the original Salsa20 spec. What do these increments mean?

This code only increments word 9 when word 8 is zero. Just like when counting you increment the next digit whenever the previous digit is zero, going from 9 to 10.

This is equivalent to having a 64-bit counter and putting the lower half into word 8 and the upper half into word 9.


Who verifies the trust of certificate authorities? Background

I am a novice in the field of cryptography and cyber-security, and while studying asymmetric-key encryption, I learned about the potential of a man-in-the-middle attack.

To mitigate this threat, people came up with certificate authorities that essentially "vouches" for the trust of 3rd parties by supplying you their respective public keys signed with the CA's own private keys.

Question

Here is where I am getting confused.

Can't we just use the same logic to intercept and compromise the transfer of information between the user and the CA (certificate authority)?

If the Certificate authority vouches for the Generic Website to ensure trust and safety, who vouches for the Certificate authority?

Maarten Bodewes answer is correct but I think the heart of your question is a major hurdle people face in understanding certificates and CAs.  I think it's worth elaborating on the part of how this works that I think you are missing.

As stated in Maarten's answer, your computer/browser has been preconfigured with a set of trusted CAs.  If you are running Windows you can see what these are by running certmgr.msc (you must type the entire name in search).  In that application, you will see a number of folders.  One of these is named "Trusted Root Certification Authorities".  If you expand "Certificates" under that folder, you will see a long list of certificates for various CAs.

When you go to a website and you get a 'trusted' lock icon, that means that the certificate they are presenting has a parentage that includes a certificate in this store.  I'm oversimplifying slightly here but this is the core idea.  For example, if I look at the certificates at google.com, the grandparent certificate has the friendly name of "Google Trust Services - GlobalSign Root CA-R2".  I look at my store and I see that exact certificate which I can verify by looking at the 'thumbprint'.

So the reason that no one can MiTM the root certificates is that you are not going out to the CA to get your trusted CAs, you already have them on your machine.  If you browse a website with a CA cert that don't have in your trusted CA store, your browser should throw a lot of warnings at you that the site is not trusted.

I hope this helps.  A side note is that this should also help you to understand how much risk there is in importing a new trusted root certificate.  For example, let's say you are doing some experimentation and generate your own 'CA' certificate.  You import this as a trusted CA and voilà! You now can sign certificates that your browser trusts.  But consider what could then happen if someone else gets access to the private key you generated for that root CA.  They now can create a certificate for any  website and unless you check the cert chain on each site you go to, you could become subject to a MiTM attack.


Trapdoor and RSA (Schneier) Disclaimer: I'm new to cryptography.

Background: From Applied Cryptography (Bruce Schneier), page 30 of 2nd edition

  A trapdoor one-way function is a special type of one-way function, one with a secret trapdoor. It is easy to compute in one direction and hard to compute in the other direction. But, if you know the secret, you can easily compute the function in the other direction. That is, it is easy to compute $f(x)$
  given $x$, and hard to compute $x$ given $f(x)$. However, there is some secret information, $y$, such that given $f(x)$ and $y$ it is easy to compute $x$.

Question: From a high level (i.e., more formally), is the following correct?

m = message
i = input (e.g., public key)
t = trapdoor (e.g., private key)
h = one-way hash
f(m,i) = h
f(h,t) = m

Edit: Please see Schneier's use of a "one-way hash" on page 38 of the same reference:

  (..) Alice signs the hash of the document. In this protocol, both the one-way hash function and the digital signature algorithm are agreed upon beforehand.

  Alice produces a one-way hash of a document.
  Alice encrypts the hash with her private key, thereby signing the document.
  Alice sends the document and the signed hash to Bob.
  Bob produces a one-way hash of the document that Alice sent. He then,
  using the digital signature algorithm, decrypts the signed hash with Alice’s
  public key. If the signed hash matches the hash he generated, the signature
  is valid.

Edit 2: Update, based on suggested answers:

x = message
i = input (e.g., public key)
t = trapdoor (e.g., private key)
h = one-way hash
f(x) = h
g(h,t) = x

No, neither of the two blocks of 6 equalities in the current version of the question are correctly describing either a trapdoor one-way function (first citation); or its use for public-key encryption; or signature of a message using a one-way hash and RSA (second citation).

The two citations are only distantly related. In particular, the "one-way hash" in the second citation is not a "trapdoor one-way function" as defined in the first citation.

We'll be illustrating the vocabulary in the first, then the second citation, in the context of RSA only; in each case, giving formulas as attempted in the question.

Assume a public/private RSA key pair has been established. The public key is $(N,e)$, and as its name implies is assumed known to everyone.

In the first citation:

The "trapdoor one-way function" is the function $f$ that transforms $x$ into $f(x)=(x^e\bmod N)$; we'll note $c=f(x)$.
"the secret" (also "some secret information"), is the private key $(N,d)$, which is noted $y$ (or equivalently: anything which knowledge allows factorization of $N$).
Knowledge of the private key $y=(N,d)$ allows computing an $x$ from $c$, such that $c=f(x)$; that can be done as $x=g(c)=(c^d\bmod N)$; it turns out that if $c$ was established by choosing $x$ with $0\le x<N$ and computing $c=f(x)$, then computing $g(c)$ always give $x$.
Doing the same without "the secret" is believed intractable, for random choice of $c$, or for $c$ chosen as $c=f(x)$ for random choice of $x$ assumed secret.
"the secret trapdoor" (function) is the function $g$; notice that $g(f(x))=x$ if $0\le x<N$; and $f(g(c))=c$ if $0\le c<N$.

In textbook RSA public key encryption, $f$ is the encryption function, and $g$ is the decryption function. Encryption is public, while decryption requires knowledge of the secret trapdoor $y$.

The notation used in the question's equations uses a function with two arguments and derives both $f$ and $g$ from that. That is done by defining the RSA function as accepting as second argument the key (a pair of integers), as follows:

$i=(N,e)\;\;$ (the public key)
$y=(N,d)\;\;$ (the private key, unlocking the trapdoor)
$r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
$x=\text{message}\;\;$ (the plaintext)
$c=r(x,i)=f(x)\;\;$ (the ciphertext per textbook RSA public-key encryption)
$x=r(c,y)=g(c)\;\;$ (the deciphered plaintext)

Note: this only illustrates textbook RSA public-key encryption, which is extremely insecure in many practical situation (e.g. $x$ is unknown, but known to belong to a known set, such as $\{\text{head},\text{tail}\}$, or a class roll). This is avoided in actual uses of RSA for encryption.

In the second citation, which describes signing a (possibly large) message using textbook RSA and a one-way hash function:

"the one-way hash function" is a one-way function, noted $H$, which has no relation to RSA, and is assumed to not be a trapdoor one-way function in the sense of the first citation; rather, $H$ could be something like SHA-512.
"document" is a message $m$, expressed as a bitstring (including, a file).
"the hash of the document" (also "a one-way hash of a document" of step 1) is the result of applying $H$ to $m$, noted $h=H(m)$; that $h$ is assimilated to an integer, and $0\le h<N$ holds.
In step 2, "Alice encrypts the hash with her private key" is poor terminology for: Alice applies the secret trapdoor function $g$ (as in our analysis of the first citation) to $h$; that yields $s=g(h)$.
In step 3, "the signed hash" is that same $s=g(h)$.
In step 4:

Bob computes "a one-way hash of the document that Alice sent"; that will be $h$ as originally computed by Alice if and only if the document that Bob received is exactly $m$ as Alice has processed it; the only if part is because $H$ is one-way (or, depending on threat model, collision-resistant).
(Bob) "decrypts the signed hash with Alice’s public key" is poor terminology for: Bob applies the trapdoor one-way function $f$ (as in our analysis of the first citation) to $s$ that it received from Alice, giving $f(s)$; in the absence of alteration of $s$, that will be $f(g(h))$, that is $h$ as originally computed by Alice.
Bob will consider that the document he received is as signed by Alice when these two computations of $h$ give the same result.

Again sticking to the notation in the question

$i=(N,e)\;\;$ (Alice's public key)
$y=(N,d)\;\;$ (Alice's private key, unlocking the trapdoor, known only to Alice)
$r(z,(N,k))=(z^k\bmod N)\;\;$ ($r$ is the RSA function, $z$ and $k$ are variables)
$m=\text{message}\;\;$ (the message to sign, approved by Alice)
$h=H(m)\;\;$ (the hash of the message as computed by Alice)
$s=r(h,y)=g(h)\;\;$ (the signature as computed by Alice)
$(m,s)\;\;$ (the signed message that Alice sends)
$(\tilde m,\tilde s)\;\;$ (the alleged signed message that Bob receives)
$\tilde h=H(\tilde m)\;\;$ (the hash of the alleged message as computed by Bob)
$\widehat h=r(\tilde s,i)=f(\tilde s)\;\;$ (the hash computed by Bob from the alleged signature)
Bob accepts $\tilde m$ as genuine and signed by Alice if and only if $\tilde h=\widehat h$.

Signing is by applying the secret trapdoor function, and can be performed by Alice only; anyone knowing Alice's public key can perform the verification that Bob does.

Note: this only illustrates textbook RSA signature with hash, which has known security limitations; notably, if the width of $h$ was small enough (e.g. 256 bit as if SHA-256 is used for $H$), and Alice signs many messages specially crafted by Carol, then Carol can forge another message and its signature, even though Alice never signed that other message. This is avoided in actual uses of RSA for signature.


Could affine transformation mod 2^128 be a side-channel attack problem DFC cipher uses affine transformations mod $2^{64}+13$. Soon after DFC's publication, Ian Harvey raised the concern that reduction modulo a 65-bit number was beyond the native capabilities of most platforms, and that careful implementation would be required to protect against side-channel attacks, especially timing attacks.
Consider a cipher which is using affine transformations mod $2^{128}$. Is it still (it was 20 years ago) a problem to implement it securely? Will affine transformations mod $2^{64}$ make a big difference?

I do not know of this cipher; however, if you explicitly calculate everything, ie: do not use arrays or lookup tables, you are not susceptible to timing attacks.  Basically, you treat the mathematics like you are on hardware, using only base logic, and it's quite slow, but it's safe because it takes equal time to calculate every value.
Having said that, you basically could not easily calculate something that large in this manner.  $2^{64}$ is a huge number, and 64-bits quickly explodes into something large in the world of logic gates.


Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used? Consider the RSA accumulator scheme with random oracle as proposed by Barić and Pfitzmann, with the random oracle replaced by a secure hash function $H$ as follows.

For a set $S$, the accumulator value is computed as $acc(S) = x^{\prod_{s \in S} h(s)} \mod N$, where $h(s)$ computes prime representatives by appending $l$ suitable bits to $H(s)$: $h(s) = 2^l H(s) + d$ (using a large enough fixed $l$, and $d$ chosen such that $h(s)$ becomes prime).

Can someone with knowledge of the factorisation of the RSA modulus efficiently compute two distinct sets of elements $S, S'$ that evaluate to the same accumulator value?

While this variant of the RSA accumulator scheme is not universally collision-free because it allows forging of membership proofs for arbitrary elements with knowledge of the factorisation, I can't think of a way how to compute a complete set of elements that evaluates to a particular accumulator value, or to find two sets that evaluate to the same value without computing a preimage of $H$. However I also couldn't find a proof that it is not feasible.

If you are the one to pick $x$ and $N$, finding collisions and second preimages is feasible (and it would appear to be possible while not jeopardizing the security of the system).

Here is one possible approach:

Search for a set of $n$ preimages $s_0, s_1, ..., s_{n-1}$ such that:

$\prod h(s_i) -1 = k r$, for a prime $r$ between, say, 256 and 512 bits.  This can be done by selecting a set such that the product is about the right size, and checking if the value is a large prime times a smooth number.
Then, select $p = k'r + 1$ and $q = k''r + 1$, both primes of the appropriate size (at least 1024 bits each), and set $N = pq$
Then, select $x$ such that the order of $x$ mod $p$ is $r$ and the order mod $q$ is $r$

Publish $N$ and $x$ as the system parameters.

Then, when someone has an accumulation of the set $t_0, t_1, …, t_m$, you can display a second accumulation $t_0, t_1, …, t_m, s_0, s_1, …, s_{n-1}$, which hashes to the same value.

That's because $h(s_0)h(s_1)...h(s_{n-1}) \equiv 1 \pmod r$, and $r$ is the order of $x$, and hence $x^{h(s_0)h(s_1)...h(s_{n-1})} \equiv 1 \pmod N$

Furthermore, I believe that:

The knowledge of the special form of $N$ (not counting the exact value of $r$) and the knowledge of $x$ does not make $N$ easier to factor
It appears infeasible, given $N$ and $x$, to determine whether this is being done.


Is Paillier cryptosystem commutative? Is Paillier cryptosystem commutative?

If not, how can we construct an oblivious decryption protocol based on Paillier?

No, Paillier is not commutative.

Your proposal for doing oblivious decryption is almost correct. Multiplication in the ciphertext domain is addition in the plaintext domain, so $E(pk, m+r) = E(pk, m) \cdot E(pk, r)$. Given $m+r$ in a finite group, Bob cannot figure out $m$ as long as $r$ is only ever used once.


GMAC vs HMAC in message forgery and bandwidth Saarinen in his work GCM, GHASH and Weak Keys says that:

  The GHASH algorithm belongs to a widely studied class of Wegman-Carter
  polynomial universal hashes. The security bounds known (this and this) for these algorithms indicate that a $n$-bit tag will give $2^{−n/2}$ security against forgery.

  It can be argued that universal hashes sacrifice some communication bandwidth for convenience as traditional hash-based MACs are designed to reach the information theoretic $2^{−n}$ bound against message forgery.

What is the convenience of universal hashes provides?
How much GHASH increase on the communication?.
Why one should not use an information theoretic bound HMAC instead should use a lesser one?
Since GHASH provides at most $2^{64}$ security against forgery in TLS 1.3, and that is standard that cannot be changed, are there any other suites that provide information theoretical security against forgery.

note: He also says that

  In this paper we give further evidence that this is not only the security lower bound but an upper bound as well. (for universal hashes )

Saarinen in his work GCM, GHASH and Weak Keys says that;

This paper is not very clear and has led many people into regrettable confusion about universal hashing authenticators.

The paper—both the manuscript you cited and the conference paper at FSE 2012—contains misleading claims and misattribution of ideas; describes attacks that apply only beyond the bounds of safe usage in standard security advertisements; and proposes a remedy that neither raises the forgery probability nor addresses any practical concerns, in security or performance, of GCM.

The paper doesn't identify the three main realistic shortcomings of GCM: the danger of truncating tags because of the $O(\ell/2^n)$ term in the forgery probability instead of $O(1/2^n)$ for $n$-bit tags on messages of length up to $\ell$; the quadratic term in forgery probability arising from the use of a block cipher (it is misattributed to universal hashing); and the prohibitive cost to constant-time GHASH evaluation (as well as AES evaluation) in software, which invites leaking secrets through timing.

    The GHASH algorithm belongs to a widely studied class of Wegman-Carter
    polynomial universal hashes. The security bounds known (this and this) for these algorithms indicate that a $n$-bit tag will give $2^{−n/2}$ security against forgery.

    It can be argued that universal hashes sacrifice some communication bandwidth for convenience as traditional hash-based MACs are designed to reach the information theoretic $2^{−n}$ bound against message forgery.

These statements are both misleading at best, and simply false if taken literally on their faces.

Neither universal hashes[1] (paywall-free: (a), (b)) nor the Carter–Wegman method of authenticating multiple messages[2] (paywall-free) gives a quadratic term in forgery probabilities, or ‘$2^{-n/2}$ security’, phrasing which is too glib to distinguish offline computation afforded by an attacker from online forgeries limited by your application's bandwidth[3], and which obscures the intermediate block size vs. the possibly truncated tag size.  It is the use of a permutation like AES—or DES, as originally suggested by Shoup[4]—that causes quadratic terms to appear: use functions instead of permutations, and the quadratic terms vanish.

Universal hashes can actually attain the optimal bound $2^{-n}$ on forgery probability for an $n$-bit tag.  Indeed, the very first authenticator in history of Gilbert, MacWilliams, and Sloane in 1974[5] (paywall-free), published before the concept of universal hashing was named by Carter and Wegman in 1979, attains this forgery bound—by using a key as long as the message.

Carter and Wegman's innovations[2] were to compress the key to a constant size at a linear cost in forgery probability, and to extend the authenticator to multiple messages by encrypting each authenticator with one-time pad to conceal the structure of the universal hash.  Shoup's contribution in 1996[4] was to use DES on a per-message nonce to generate the pad, and proved that if the sender sends no more than $\sqrt{2^n\!/\ell\,}$ messages of length $\ell$ then the forger's success probability after $f$ attempts is bounded by $2 f \ell/2^n$ (Theorem 2).

Details.

GHASH is a family of functions $H_r\colon \{0,1\}^* \to \operatorname{GF}(2^{128})$ for $r \in \operatorname{GF}(2^{128})$ defined on a bit string $m$ by interpreting it, suitably padded, as a sequence $(m_1, m_2, \ldots, m_\ell)$ of elements of $\operatorname{GF}(2^{128})$, and giving $$H_r(m) = m_1 r^\ell + m_2 r^{\ell - 1} + \dots + m_\ell r.$$  In other words, we interpret a message $m$ as a polynomial of degree $\ell$ with zero constant term, and evaluate it at the point $r$.  (GHASH is one of several polynomial evaluation hashes in cryptography; Poly1305 is another popular one, over the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$.)

GHASH is a universal hash family, or, more precisely, GHASH has difference probability $\Pr[H_r(x) - H_r(y) = \delta]$ bounded by $\ell/2^{128}$ for any $\delta$ and any messages $x$ and $y$ of up to $\ell$ blocks.  Proof: The solutions in $r$ to $H_r(x) - H_r(y) = \delta$ are the roots of the polynomial $x(r) - y(r) - \delta$ in $r$.  This polynomial has degree at most $\ell$, so it has at most $\ell$ roots among $2^{128}$ possible values in $\operatorname{GF}(2^{128})$.

The one-time authenticator $m \mapsto H_r(m) + s$ for independent uniform random $r, s \in \operatorname{GF}(2^{128})$ on messages of up to $\ell$ blocks has forgery probability bounded by $\ell/2^{128}$.  Proof: For any $m \ne m'$, $a$, and $a'$, and for independent uniform random $r, s$,

\begin{align}
  \Pr&[H_r(m') + s = a' \mid H_r(m) + s = a] \\
  &= \Pr[H_r(m') + a - H_r(m) = a'] \\
  &= \Pr[H_r(m') - H_r(m) = a' - a] \\
  &\leq \ell/2^{128}.
\end{align}

A forger who attempts up to $f$ forgeries can't have better probability of success at a single forgery among all the attempts than $f \ell/2^{128}$.  Notice that there's no quadratic term here.  Only the bound on difference probabilities, and independence of $r$ and $s$, figured into this analysis—you could use any other hash family with bounded difference probabilities to prove a similar forgery probability bound.  For example, the one-time authenticator $m \mapsto m_1 r_1 + m_2 r_2 + \dots + m_\ell r_\ell + s$ with the message-length key $r = (r_1, r_2, \ldots, r_\ell)$ would give a bound of $f/2^{128}$, with no factor of $\ell$.

To authenticate many messages, Carter and Wegman suggested[2] using a uniform random key $r$ with independent uniform random $s_1, s_2, \dots, s_q$ to authenticate each of up to $q$ messages $m_i$ with $m_i \mapsto H_r(m_i) + s_i$.  They proved the forgery probability is still $f \ell/2^{128}$.  Notice that there is still no quadratic term in the forgery probability $f \ell/2^{128}$ of Carter and Wegman's method, and it is even independent of the number $q$ of messages sent.

The quadratic term arose when Shoup opted[4] to generate $s_i$ by the permutation $\operatorname{DES}_k(i)$.  The standard lemma about substituting a permutation for a function adds $q'(q' - 1)/2^{n - 1}$ to the forgery probability bound, where $q'$ is the number of calls to the permutation, which in AES-GCM is $1 + (1 + \ell) (q + f)$.  There are somewhat better bounds[6][7], but the point is that there is a quadratic cost to using a permutation like DES or AES.

More recent schemes like NaCl crypto_secretbox_xsalsa20poly1305 do away with the permutation and the Carter–Wegman method and instead simply generate $r$ and $s$ independently by a PRF for each message, as suggested by Lange[8].  But let's come back to GHASH and GCM.

  What is the convenience of universal hashes provides?

Universal hashes can be extremely cheap to evaluate—much cheaper than block ciphers, pseudorandom functions, and especially collision-resistant hashes.  There is no inherent limit to the parallelism attainable in evaluating polynomials by precomputing $(r, r^2, \dots, r^t)$ if you can perform $t$ simultaneous multiplications in your vector unit.  GHASH in particular is difficult in software because it is defined in terms of a binary field, with a kind of weird bit ordering[9], but there are other universal hashes friendlier to software, like Poly1305, which can run in under one cycle per byte in software.

  How much GHASH increase on the communication?.

GCM/GMAC adds a 128-bit tag.  Because the forgery probability is $O(\ell/2^n)$ rather than $O(1/2^n)$, you should avoid truncating the tag much[10].  For example, if you accept messages of up to 16 MB or $2^{20}$ blocks, then the forgery probability for a single 32-bit tag is $2^{-12}$ rather than $2^{-32}$ as you might hope.  Note that truncating the tag does not affect the quadratic term $O(q^2\!/2^b)$ arising from the use of a $b$-bit permutation instead of a $b$-bit function: the block size and tag size costs scale separately.

  Why one should not use an information theoretic bound HMAC instead should use a lesser one?

Mu.

The bound above is information-theoretic.  There is a corresponding information-theoretic bound for the HMAC model $$m \mapsto f\bigl((k \oplus \mathrm{opad}) \mathbin\| f((k \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$$ with a uniform random function $f$, or for a Merkle–Damgård hash $f$ with a uniform random compression function, and it involves the collision probability of $m \mapsto f((k \oplus \mathrm{ipad}) \mathbin\| m)$.

But you need to choose an actual $f$ to make a practical system.  Universal hashing gives us strong guarantees with extremely cheap options; with HMAC we typically use conjecturally collision-resistant functions like SHA-256, which are orders of magnitude more expensive to compute for conjectured security that we don't even care about in this application (collision resistance).

But let's suppose you chose a comparable function to use with a 256-bit key giving a 128-bit tag, maybe one without collision resistance: MD5.  As it happens, HMAC-MD5 doesn't provide much security after $2^{64}$ messages either[11].  Oops.

(The fact that MD5's collision resistance is broken is irrelevant here; what's relevant is the 128-bit hash size.  The same generic attack on HMAC works when $f$ is a random oracle, which by definition is collision-resistant.)

There is an advantage to HMAC-MD5 over, e.g., AES-GMAC (which is AES-GCM with an empty ciphertext) or Poly1305-AES (another Carter–Wegman–Shoup MAC with AES): HMAC-MD5 doesn't need a nonce, whereas AES-GMAC and Poly1305-AES do; and HMAC-MD5 works not just as a MAC but as a long-input short-output PRF, whereas GMAC and Poly1305-AES don't.  But you can also fashion a good, fast, nonceless long-input short-output PRF out of a universal hash and a short-input short-output PRF[12].  For example, AES-GCM-SIV does just that (and fixes the bit ordering in GHASH too).

  Since GHASH provides at most $2^{64}$ security against forgery in TLS 1.3, and that is standard that cannot be changed, are there any other suites that provide information theoretical security against forgery.

You can use ChaCha20-Poly1305.  This avoids the quadratic cost in forgery probability of using a block cipher, and it doesn't present a conflict between speed and security in software implementations.

The CCM cipher suites all have the same disadvantage as GCM of $O(q^2\!/2^b)$ in the forgery probability from using a permutation instead of a function of $b$ bits, and they require $\ell$ AES calls rather than 1 AES call per message just for authentication.  The advantage they have over GCM is $O(1/2^n)$ instead of $O(\ell/2^n)$ in the forgery probability, and some hardware has dedicated AES circuits that might run faster than software to evaluate ChaCha20 or Poly1305.


Cryptsetup | Given Enough Passphrase Entropy, Is It Necessary To Use a High Iteration Count? Let's assume that, for creating a LUKS volume, I generate a random, 40 character passphrase that includes numbers, symbols, and upper and lower case letters, using the pwgen utility.

Given that the passphrase contains roughly 256 bits of entropy, if I use aes-xts-plain as my cipher, a 512 bit key, and sha512 for the hash, then would it be necessary (worth any reasonable gain) to also use a high iteration count -- say, 1 million, for the sake of example?

If you are certain that the passphrase contains enough entropy, then iteration is not needed. The iteration is only required when the entropy is low. The only way to preclude brute force search through a small search space is to make each guess take a prohibitively long amount of time. This is why the iteration count is recommended to be high: To ensure that nobody can guess more then a small number of passwords per second.

If the passphrase contains 256 bits of entropy, then it does not matter how fast the hash can be computed - the search space is simply too large for anyone to search through, regardless of how fast they can look.


Is SHA-256 a one way permutation when restricting the domain to {0,1}^256? Suppose we consider the space of $\lbrace 0,1 \rbrace^{256}$ as the domain and SHA-256 as our hash function.  Does SHA-256 become a one way permutation?

Has anyone tried to prove this? Or can it be shown that SHA-256 has more than one cycle under the given constraints?

There's been similar questions before but the answer is probably no with very high probability.

You can imagine a hash as being a little box with a dwarf in it. You give him a message and the first thing he does is looks for the message in his book. If he finds it, he gives you the n-bit string he wrote in his book.

If it's not in his book, he rolls some dice to create a random n-bit string. He then writes in his book both your message and the random string he just rolled. He then hands you the random n-bit string. If you pass him the same message again, he gives you back the same n-bit string.

Now we have a mental model of a hash, let's ask what happens when we start querying this construction.

Suppose we start counting from zero to $2^{256}$. We write the output of the hash of the counter in a table next to the counter that generated it. How many entries will it take before the probability is greater than 50% that an evaluation of hash(x) will hit an item already in the list?

Well each time the dwarf encounters a value not in his list, he rolls his dice. The value that comes out of those rolls might well collide with an item already in the list. The birthday paradox tells us that it will happen after approximately $\sqrt{2^{256}}$ queries.

That's about 0% of the hash space. This is why we can say with a good degree of confidence that no hash is a permutation.


Importance of random number generation in Schnorr's signature In Schnorr's digital signature protocol (https://en.wikipedia.org/wiki/Schnorr_signature), the signing process (as described in wikipedia) requires the generation of a random bit $r$. I am wondering how necessary it is for this bit to in fact be randomly generated.  For example, what if I generate my ith $r$ as $Q(i)$ for some degree $k$ polynomial $Q$. Would the signing protocol still be secure?

Note that the signature is $(s,e)$ where $s=k-xe$. If you can learn $k$ since it is predictable, then you can learn the secret signing key by computing $x = (s-k)/e$. Note that even without a concrete attack, the proof of security completely breaks down if the value $k$ is not chosen randomly.

Having said this, it is possible to change the scheme to be deterministic by including a random key $K$ for a PRF as part of the secret key and then generating the randomness needed to sign $M$ by computing $PRF_K(M)$. This actually is a good idea especially for DSA/ECDSA since repeating randomness there is a disaster
The proof that this is good in general is not difficult (a reduction to the PRF).


HMAC_DRBG Generate Process: requesting N bytes at once different from requesting N bytes in total? Am I correct in assuming that HMAC_DRBG would return different results if I, e.g. first request 4 bytes followed by a request of another 4 bytes instead of asking for 8 bytes at once?

It seems that in NIST SP800-90A chapter 10.1.2.5: Generating Pseudorandom Bits Using HMAC_DRBG first the K and V values are changed, then the requested number of bits is generated (changing just V), and then the K and V values are changed again. Besides that, leftover bits get chucked away as well.

Isn't it a strange property for a DRNG to return different value if DRNG(4) || DRNG(4) != DRNG(8) if the DRNG is not reseeded in between? Do other DRNG's have the same kind of property?

Yes, you are reading this right. The requests for random value from NIST 800-90 drbgs perturbed the state.  If this is a problem you can add a layer that optionally buffers values and always makes constant size requests.


Proof that any key exchange protocol is vulnerable to MitM attacks in the absence of shared information or trust Today I realised that every key exchange protocol I know, without a priori any shared information or trust relations (i.e. any ability to sign anything), is utterly broken by an active man in the middle attack.

I asked a professor of mine today whether there a proof of this in a formal setting and he said "yes, it's something information theoretic but I can't quite remember what..."

I looked in (what I believe to be) the relevant chapters of a couple of textbooks I have to hand, and done some google-ing and turned up nothing. I was wondering if someone could point me in the direction of either a paper or a text book containing such a proof. Thanks!

It has nothing to do with information theoretic. You just need to construct an adversary and argue that it works. In this case, the adversary is simple. Let $A$ and $B$ be parties with no secret information. An adversary $C$ playing man-in-the-middle interacts with $A$ pretending to be $B$, and interacts with $B$ pretending to be $A$. At the end, $C$ establishes a separate channel with $A$ and with $B$. Then, any message sent by is decrypted by $C$ (using the key generated with $A$) and then re-encrypted (using the key generated with $B$) and sent to $B$. Likewise, in the other direction.

Since there is no initial secret, $A$ and $B$ see exactly the same thing as they would see in a key exchange that is not under attack. However, $C$ learns everything communicated.

The difference between this and a full proof is minimal.


Calculate multiplication of a cipher matrix and a plain matrix There is a matrix $A$ that we don't want to be revealed, and there is a matrix $B$ that is known. Is there any way to calculate $A \times B$ without revealing $A$?
$A$ can be encrypted. But we don't want anyone to know it, but we want anyone to be able to calculate the multiplication of it to another matrix.
Is there anyway to do such a thing?

Yes there is. It is called functional encryption for inner product (IPFE), and there are many schemes for that, with different features in terms of underlying assumption (typically DDH, DCR, or LWE), security (IND-CPA, IND-CCA, static or adaptive, etc) and compactness.
An IPFE has four algorithms:

$\mathsf{Setup}$ generates a public encryption key $\mathsf{pk}$ and a master secret key $\mathsf{msk}$
$\mathsf{Enc}$ takes as input a fixed-length message vector $\vec m$, and outputs a ciphertext $c$
$\mathsf{KeyDer}$ takes as input a linear function $f$, the master secret key $\mathsf{msk}$, and outputs a functional secret key $\mathsf{sk}_f$
$\mathsf{Decrypt}$ takes as input a functional secret key $\mathsf{sk}_f$, a ciphertext $c$, and outputs $f(\vec m)$, where $\vec m$ is the message encrypted in $c$.

In your case, the linear function $f$ would be the function $f_B: A \mapsto A\times B$.
IPFE was first defined in this paper, where it was also constructed from a variety of standard assumptions. Since this work, there has been many follow ups, achieving stronger security notions, or more features.
In your context: the matrix $A$ would be encrypted with $\mathsf{Enc}$, and the dealer would reveal the secret key $\mathsf{sk}_B$ associated to the function $f_B: A \mapsto A \times B$. This would allow anyone to obtain $A\times B$ from any ciphertext encrypting a matrix $A$.
Of course, usual safeguards apply: if your matrix $B$ is invertible, this would just reveal $A$ in clear, so $B$ better be a highly compressing, or very low rank matrix, if you want this process to preserve some security.


Is that simple additive homomorphic scheme secure? I am doing a little cryptography research and stuck with question.

Suppose $\bar m$ is a vector of 64-bit numbers. And i want to have an additive homomorphic encryption over them. I choose large (2048 bit) prime $n$, large not prime $s$ and vector $\bar r$ of large random numbers, with size of vector equal to vector $\bar m$. Finaly, encryption function $Enc$ looks like that:
$$Enc(m_i) = (r_i,m_i+r_i\cdot s\mod n)$$
where $Enc$ yields an ordered pair of numbers.
So the number $n$ with encrypted vector $c=Enc(m)$ goes to the opponent, but $s$ keeps secret.

Sum of an encrypted values is just sum of pairs (all operations are modulo $n$):
$$Sum(c_i,c_j) = (c_i.first+c_j.first,c_i.second+c_j.second)$$
$$or$$
$$(a,b)+(c,d)=(a+c,b+d)$$
where $c_i.first$ is the first element of pair $c_i$ and $c_i.second$ is the second.

Decryption looks like that:
$$Dec(c_i) = c_i.second - c_i.first\cdot s$$

Intuitively, i think, that this scheme is vulnerable, but i can't see why. I will be glad to have a hint to understanding this problem.

Many thanks in advance to your great community!
(sorry for any grammar mistakes, English is not my native language)

It is not semantically secure. If the adversary asks for the encryption of message $0$ then it gets $r_i,r_i*s$, so it recovers the secret key $s$ and breaks the security game.


Private key not used in a signature scheme I'm trying to understand the following signature scheme (Camenisch-Lysanskaya):

Key generation:
$n = pq$ special RSA modulus, $a, b, c \in QR_n$. $PK = (n, a, b, c), SK = p$.

Signing algorithm:

$m$ message.
$e$ random prime number (with some for this question unimportant length restriction).
$s$ random number with very big length (unimportant for my question).
Compute $v^e \equiv a^m b^s c \bmod n$. Output $(e,s,v)$.

Verification algorithm: Check that $v^e \equiv a^m b^s c \bmod n$ and check the length restriction of $e$.

I don't see why this is a valid signing algorithm. The secret key is not used for signing (or calculating $e$ or $s$). So everyone could make a signature like this and not just the one who created the public key.

Edit: If I understand it right, it's all about the hard computation of a $v$ and $e$ if you just have $a^m b^s c$. But how does it help there to know the factorization of $n$?

Compute $v^e \equiv a^m b^s c \pmod n$. Output $(e,s,v)$.

This should perhaps read:

Solve $v^e \equiv a^m b^s c \pmod n$ for $v$.  Output $(e,s,v)$.

If you can solve $v^e \equiv u \pmod n$ for $v$ without using $p$ in general, you have found a major breakthrough in cryptanalysis!


How to find which padding method is used in block cipher (AES) encyption? I have a cipher text which is encrypted using AES-128 Algorithm.
I want to know the following things to decrypt the cipher.

IV (Initialization Vector)
Padding Method
Encryption Key

How do I find the padding method used in the encryption?

In general, you cannot, because padding makes sure the plaintext can always be recovered, so any valid padding method produces equally valid plaintext. For instance, suppose the last (decrypted) block is, in hexadecimal notation:

01:02:03:04:05:06:07:08:09:0A:0B:0C:0D:FF:00:00

The "natural" interpretation is that the padding method here might be "add an FF byte, then pad the rest with zeroes". But it could equally well have been "put the message at the end, insert an FF byte before, then pad with random non-FF bytes at the beginning", so that the message is in fact 00:00. Or it could have been "append a 05 byte, then pad with non-05 bytes", giving the message 01:02:03:04. You would rightly argue that the last two padding methods are unusual, but they are admissible.

In short, if you know absolutely nothing about the plaintext and do not make assumptions about possible padding methods, then you simply cannot know for sure which padding method was used. In other words, you cannot decrypt your message reliably without knowing the padding method. You can come up with a padding method that will literally produce any message you want (an easy way is to add a constant xor operation beforehand, though this is stretching the definition of "padding method").

However, in practice, there are only a handful of block cipher padding methods used in the real world, and they are easy to recognize - bit padding, which consists of adding a "1" bit (usually, a 0x80 byte for byte-oriented implementations) and padding with zero bits, PKCS #7, which adds N bytes of value N where N is the number of padding bytes required (from 1 to a whole block's worth, up to a maximum of 255 bytes), X.923 byte padding, and a few variants.

If you know features of your plaintext, it gets even easier, as you might be able to work out the end of the plaintext without needing to consult the padding. For instance, the plaintext could have a length record at the start indicating how long it is, in which case you can just read that and skip the padding entirely (assuming it is a standard padding method, of course). It might include a terminating character or symbol, the last block might not matter (if it carries redundancy data), etc, etc...

Or you can just try each one and see if what you get makes sense. That works, too.

This is assuming you only have the ciphertext, the ability to decrypt it (but not strip off the padding), and no metadata. Usually implementations will either hardcode the padding method used in their software (meaning if you know where your ciphertext comes from, you can look up the padding method there) or output it along with the ciphertext and IV in order to allow the receiver to actually decrypt the message properly, in which case it is given to you.

And, of course, if you have only the ciphertext and not even the IV or decryption key, then the answer is, of course, that you cannot know. Because if you could, then it would mean that features of the plaintext are not properly hidden by the encryption scheme used, meaning that scheme is (very) broken.


What is the ideal cipher model? What is the ideal cipher model?
What assumptions does it make about a block cipher?
How does it relate to assuming that my block cipher is a pseudo-random permutation (PRP)?
When is the ideal cipher model appropriate to use?
How do I tell whether a particular block cipher can reasonably be modelled using the ideal cipher model?

When cryptographers create algorithms, they usually provide some argument that the algorithm is secure. They need to start the argument with some set of assumptions. For example, the in public-key cryptography, they may begin with the assumption that factoring large numbers is hard.

Many algorithms use use a block cipher as a building block. The arguments that these algorithms are secure need to make some (mathematical) assumption about the block cipher in question in order to get started. Normally, the assumption goes something like this: "If the encryption key is chosen at random, then an attacker who does not know the key cannot distinguish between the block cipher and a truly random permutation, even using a chosen-plaintext attack." (This is an informal statement of the pseudo-random permutation [PRP] assumption.)

But the PRP assumption isn't always applicable. Sometimes block ciphers are used in ways where the key is either not random or not secret (we'll see an example in a bit). In these cases, we need to make some other assumption about the block cipher's security properties.

What is the ideal cipher model?
This is where the ideal cipher model comes into play. In the ideal cipher model, we just pretend the block cipher is a random permutation for every key. Furthermore, we treat these permutations as independent. We assume that if an attacker wants to know what happens when a block is encrypted under a given key, he has to go to the work of computing it himself. He can't infer anything about the output by encrypting other blocks, or the same block under a different key.  (Exception: Given a fixed key, no two inputs will produce the same output. So the attacker can rule out that possibility, but that's it.)

Example: the Davies-Meyer Compression function. Some hash functions, such as MD5, SHA-1, and SHA-2, are examples of Merkle-Damgard constructions. Let's say we'd like to find an argument that Merkle-Damgard constructions are collision-resistant. They look like this (IV is a constant, and Hash is the output):

The function $f$ above is a compression function. Now, it's possible to show that if $f$ is secure, then so is the hash function. But we can go a bit deeper using the ideal cipher model. For MD5, SHA-1, and SHA-2, $f$ is built out of a block cipher $E$ using a so-called Davies-Meyer construction (each of these three hash functions uses a different block cipher):

$f(\mathrm{M}, H) = E_{M}(H) \oplus H,$

where $M$ is the message block and $H$ is other input (the chaining value). So $M$ is being used as the key, but if someone is trying to find a collision for MD5, then each message block $M$ is under his control. It is neither random nor secret. So we can't use the PRP assumption.

But we can model $E$ as an ideal cipher. Using this assumption, we can show, for example, that no one could find a collision for MD5 or SHA2 without doing an insane amount of work (or getting really, really, lucky).

But wait! We can find collisions for MD5! So what went wrong? Well, the ideal cipher model is just a heuristic. Block ciphers must be describable using simple algorithms --- we can't generate and store random tables listing every output under every key, these tables would be huge. This makes it inevitable that there's some mathematical relationship between different outputs and different keys.

When is it appropriate to use the ideal cipher model? Because the ideal cipher model is a heuristic way of modeling block ciphers, rather than an assumption that could plausibly be true in a technical sense, it should be avoided whenever possible. But sometimes, notably in hash functions that don't have a random secret key, it's our only option.

How do I tell when a block cipher can reasonably be modeled using the ideal cipher model? It's better to ask if the block cipher is being used in a way that requires the ideal cipher model (as opposed to a PRP assumption). Next, look at how the block cipher is being used. In MD5 and SHA1, SHA2, for example, the block cipher is buried inside of the compression function, and the attacker doesn't have complete control over the inputs to this function. Since the attacker is a couple steps removed from the actual block cipher, using the ideal cipher model becomes a bit more reasonable because it may be harder for the attacker to exploit the block cipher's weaknesses. Ultimately, the best test is the test of time.

That being said, certain common ways of constructing block ciphers have been proven to result in constructions that are indifferentiable from an ideal cipher... but these proofs make heuristic assumptions about the internals of the block cipher. So although these proofs are interesting from an academic perspective, it's not clear how much they contribute to trusting a real-world block cipher in the ideal cipher model.


Is multiplicative secret sharing secure? I suggested mulitiplicative secret sharing in an answer to another question, but noted that I wasn't sure if it was even secure and was hoping someone would comment on the security. Since no one did, I thought I'd ask it as a separate question.

Fix a multiplicative group, say $\mathbb{Z}_p^*$.

To share $s$ with $k$ parties such that all $k$ are required to reconstruct $s$, we choose $s_1,s_2,\dots,s_{k-1}\in\mathbb{Z}_p^*$ at random and set $s_k=s*(s_1*s_2*\dots*s_{k-1})^{-1}$. Thus, $s=s_1*s_2*\dots*s_{k}$.

What is the security of this secret sharing method? Is it information-theoretic? In other words, if fewer than $k$ parties get to gether they should (either for a computationally bounded or possibly an unbounded adversary) learn no additional information about $s$.

Assuming that $p$ is prime, then you are in a cyclic group. Consequently, this is identical to considering the shares $s_i$ as "exponents" of a generator $g$ of $Z_p^*$.

Now we can write: $s_1 = g^{s'_1}, \ldots,s_{k}=g^{s'_{k}}$ and $s=\prod_{i=1}^{k} s_i$

Or we can view this as: $s = g^{\sum_{i=1}^{k} s'_i}$.

Consequently it looks like a perfect (= information theoretically secure) additive secret sharing scheme "in the exponent" to me.


Should we sign-then-encrypt, or encrypt-then-sign? We regularly want to send messages that are both (a) encrypted, so passive attackers can't discover the plaintext of the message, and (b) signed with a private-key digital signature, so active attackers can't trick Alice into thinking that some message came from Bob when really the message is some (accidental or malicious) modification of a real message Bob sent or a message that was forged out of whole cloth by an attacker.
Is it better to (a) generate the digital signature from the (hashed) plaintext, and then encrypt a file containing both the plaintext message and the digital signature?
Or is it better to (b) encrypt the message first, and then generate a digital signature from the (hashed) encrypted file?
Or (c) combine encryption and public-key digital signatures in some other way?
A closely related earlier question ( Should we MAC-then-encrypt or encrypt-then-MAC? )
seems to focus on symmetric-key MAC authentication.
As Robert I. Jr. asked earlier,
Do the same issues with (symmetric-key) MAC-then-encrypt apply to (public-key) sign-then-encrypt?

Assuming you are asking about public-key signatures + public-key encryption:

Short answer: I recommend sign-then-encrypt, but prepend the recipient's name to the message first.

Long answer: When Alice wants to send an authenticated message to Bob, she should sign and encrypt the message. In particular, she prepends Bob's name to the message, signs this using her private key, appends her signature to the message, encrypts the whole thing under Bob's public key, and sends the resulting ciphertext to Bob. Bob can decrypt, verify the signature, and confirm that this indeed came from Alice (or someone she shared her private key with).  Make sure you use an IND-CCA2-secure public-key encryption scheme and a UF-CMA-secure public-key signature scheme (i.e., one that is secure against existential forgery attack).

Justification: The reason to do this is to defeat some subtle attacks.  These attacks are not necessarily a problem in all scenarios, but it's best to harden the approach as much as possible.  A complete explanation would take more space than is available here, but see below for a sketch of the reasoning.

For a detailed analysis about whether to sign first or encrypt first, the following is a good resource: Defective Sign & Encrypt in S/MIME, PKCS#7, MOSS, PEM, PGP, and XML.

I don't recommend encrypt-then-sign. It could work, but it has some subtle pitfalls in some contexts, because the signature does not prove that the sender was aware of the context of the plaintext. For instance, suppose Alice's SSH client sends the message "Dear SSH server, please append my public key to /root/.ssh/authorized_keys -- and you can know that I am authorized because I know the root password is lk23jas0" (encrypted then signed with Alice's public key), and the SSH server acts on it if the root password is correct. Then Eve can eavesdrop, capture this message, strip off Alice's signature, sign the ciphertext with Eve's own key, and send it to the SSH server, obtaining root-level access even though Eve didn't know the root password.


Ensuring integrity in a multi-user secret vault Assume you have a vault containing secrets. Each one is encrypted for at least one authorized recipient using some public key crypto (one file per secret). Each authorzied recipient can decrypt all of those secrets. This implies that each recipient can also add additional recipients by decrypting all secrets and encrypting them again for the previous recipients and additionally the new one.

(The details of the encryption don't really matter here, for simplicity sake assume PGP/GnuPG is used.)

While this approach works well for authentication and confidentially, we have a problem with integrity. Malroy could easily add a malicious secret (i.e. a specially crafted phishing link) by encrypting this secret for all the indented recipients.

We could solve this by signing each secret or some kind of digest over the vault, but then we have to figure out who is authorized to sign a secret or the hash? How can we protect the integrity of our vault while still maintaining the ability to add recipients (authorized user)?

Malroy could easily add a malicious secret (i.e. a specially crafted phishing link) by encrypting this secret for all the indented recipients.

Asssume Mallory is also a regular user of the vault. Then if Mallory deposits any malicious information by himself (regardless if it is original or tries to fake some other content), that is impossible to prevent (and doesn't fall under the purview of integrity).

Integrity means, that Mallory can't just change the information placed by Alice - and everyone still thinks the information was put there by Alice. And to achieve that goal it is enough using digital signatures. And of course, everyone can only sign his own secrets.

About the adding of recipients: You said you didn't care about the encryption method, but that actually does matter. Usually you would use hybrid encryption for this kind of storage:

Encrypt the data itself with a symmetric cipher and a random key (one for each file).
Encrypt that key with the public keys of the recipients and send it to them (or make otherwise available).

So adding new recipients is simply encrypting the random key with their public key. And to get the integrity:

Alice signs the encrypted data (symmetric encryption with random key, without the encryption of that key under some public key - that would be user-dependent) with her own signing key.

You have the assumption that every user has a pair of private/public key for encryption, and users know the public keys of others (to make information available). It's not that much of a stretch to also have a signing and verification key for each user.


How is ZKPP better than signing nonces? I am trying to understand the use case for zero knowledge password proofs.

Clearly, it is not ideal for a remote server to store a password hash. Then

I need to upload the password to the server for verification. The server knows my password.
I need to rely on SSL so that people can't eavesdrop the password.
If anyone hacks the server, they can do a dictionary attack against my password.

But what does ZKPP buy us vs uploading a public key to the server. Then, when I want to log into the server, the server generates a nonce, and I sign it with my private key?

That involves storing my private key on my machine. Someone could steal this. So it is common to encrypt the private key with a password. The password might be weak, so someone could perform a dictionary attack to try to decrypt the private key.

Is this the kind of attack that ZKPP is suppose to stop?

The difference is that when using ZKPP, the user's input is the password; while using public key on the server to authenticate, the user's input is her private key. There are two problems I can see:

When using the public key, the user have to copy the private key to the device she uses. This could be quite inconvenient.
The private key needs to be protected. If the private key is encrypted by a password, then an offline brute-force/dictionary attack is possible (by testing decryption with the public key). ZKPP should allow only on-line attacks.

In many systems that use public key for user authentication, the user's private key is often stored in a tamper-proof/evident device, e.g. smart card or hardware token. This can solve partially the problems mentioned above.


Encryption strength when using a PBKDF Suppose:

$m$ is a positive integer.
$n=2 \times m$.
$H: \{0,1\}^{*} \rightarrow \{0,1\}^n$.
$p$ is a password.
$s$ is a salt.
$K=\{0,1\}^n$ is the derived key.
$PBKDF(p,s)$ derives a key from $p$ and $s$ using $H$ in some manner.
$K=PBKDF(p,s)$.

Given the birthday paradox, is the key strength here $m$-bit or $n$-bit?

Actually, the strength of the derived key is likely to be limited by the strength of the password; for example, if the user selects the password "password", well, that's likely be to within the first couple that an attacker checks.

However, if we assume that the password is stronger than what most people select, then the next limiting factor is $n$.  The birthday paradox doesn't help the attacker; he's not looking for two different passwords that derive the same key.  Instead, he's trying to find a password that generates the derived key; a guess at the password has a probability $2^{-n}$ of mapping to the right value (remember, we assumed above that the probability of him happening to guess the original password is even smaller), and so that's the probability per guess of him being able to break the system.