Side Channel Analysis (CorrPA), comparison between HW-results and measured power traces I think I have missed something very fundamental.

I am trying to understand the step in DPA where you compare your hypothetical power consumptions with your measured ones.
The Matrix H with Matrix T.

Matrix T is of size D x T, where D is the number of data blocks and T is the number of measured points in one power trace. This implies that an element value in this matrix T can be of 0.58W (just an example).

If I use Hamming Weight, as power model, I will end up with a real number.
E.g., 0110 0111 = 5 (dimensionless). How can this number correlate with the power traces that are in Watts? (e.g., If I use Pearsons).

You should use the value you found (in watt). Try to have a look at this  file, it's really well explained in my opinion. If you look for page 21 for instance, you'll see that the plaintext produces a certain waveform; then, after the hypotesis and the S-Box output, the correlation is clearly done with the power model obtained and the value of the traces (page 23)


Choosing between simple Hash and HKDF to derive the second key used for MAC I have an encrypt function that takes a single encryption key and encrypts data but also incorporates an HMAC. So I need to derive a second key from the encryption key to use it for HMAC.

You recommend using a simple hash like sha256 or HKDF for driving the second key and why?

Which one is better and why?

But I am not stringent about these details, and if simple hash has no serious flaw I will use it because it seems much simpler.

The HKDF paper answers this question at length.  Section 8 in particular seems to be the most relevant.

But perhaps you may find that the explanations are very technical.  To help you out a little bit, the general flavor is this: the security of nearly all modern cryptographic algorithms is conjectural—we don't have unconditional proof that they are actually secure, but rather arguments in forms like this:

Heuristic: "A lot of really good cryptanalysts tried to break the algorithm, but haven't succeeded."
Conditional proof: "If you can break this algorithm, then you can break this simpler building block that we believe is secure."

The difference between your proposed uses of SHA-256 and HKDF comes down to HKDF being more careful and pessimistic.  We don't have proof that HKDF is more secure than SHA-256 in your application, but the arguments for HKDF's security are better than those for SHA-256 because they rely on fewer and/or weaker untested premises than your use of plain SHA-256 would.

But it's also entirely possible that simple SHA-256 would be secure in this application.  Do you want to bet on it?  (Lots of systems do, so far successfully.)

So applying this to your comment here:

  But I am not stringent about these details, and if simple hash has no serious flaw I will use it because it seems much simpler.

...the thing to remark is that you're looking at the issue backwards—you're proposing to use the simple hash unless somebody can prove to you that it's insecure (which it might not be!).  But the way cryptographers look at it is that you shouldn't use the hash function unless you can articulate some good (even if inconclusive) reason why it's secure (e.g., by conjecturing that SHA-256 behaves similarly to a random oracle).


Unable to implement Client and Server Side Hashing (Validation problem) I'm trying to implement hashing on both client and server Sides for my web/mobile Application.

On the client side, I implemented the slow hashing algorithm (bcrypt)
On the server side, I tried to use a fast hashing algorithm (MD5)

Here's what I did:

The user enters the password in my app.
The password is hashed on the client side using bcrypt (slow hashing algorithm).
The password hash travels via SSL to the server.
On the server side I use MD5 (fast hashing algorithm).

The problem here is: on the client side, as I mentioned already, I'm using bcrypt (with a random salt). So, every time the resulting hash is a different one.

Further hashing the resulting hash from the client ends up with a different one on the server side, since MD5 (without salt) produces a different server hash for different client hash.

So users are not able to log in.

How can I solve my problem? Which algorithm would be better suited for my problem here?

In my answer, I'll largely reproduce / use what is written in "Method to Protect Passwords in Databases for Web Applications" by Scott Contini, you definitely should read at least section 4 for the actual guidance and the whole paper for the background and the whys.

The paper has a more distinguished approach than you, but in principle does the same. The problem with the salt is solved by storing a per-user salt in the database and upon request hash(username||domain||per-user-salt) is computed by the server and served to the client as the salt.

Now for the procedure as outlined in section 4:

Store the username, $H(s)$ and $v$ in your database upon registration / password change. $v$ is said per-user salt (which should be 128-bit random and regenerated upon password change), $H(s)$ is the fast hash of the slow hash.
The salt is as described above. Additionally store a system-level secret $\sigma$ of the same properties as $v$, regenerate it occasionally.
The client (the app) gets the username from the user (or from its storage). It now sends a request with said username to the server.
The server looks the user up. If the user does not exist, $\sigma$ replaces $v$ in the salt computation. The salt and the (system-wide) parameters of the slow hash are sent.
The client now computes the slow hash using the password and the given parameters and sends the hash.
The server hashes the received result. The user is accepted if and only if the user exists in the database (you may make a new query here) and the hashes (from the DB and the computation) match.

Oh and you may want to use a more modern hash-function than MD5 here, because if it comes out that you use MD5 people (who have heard that "MD5 is broken") will come to you and complain about why you use a broken hash function. This might cost you users, because not everybody is going to care about the (correct) explanation that the "broken-ness" of MD5 doesn't matter in this particular case. So rather use a PR-friendly hash function like SHA-256.


Making attacks on password hashes less economical Perhaps an abstract question on complexity given the trade offs between memory vs runtime, I was wondering if it's possible to constrain only either extremes approaches to be optimally efficient, thus making attacks on hashes less economical.

Background

I attended a seminar on recent publication, Scrypt is Maximally Memory-Hard 1, where the authors focus on scrypt, a simple candidate Memory-hard function (MHF) designed by Percival, and described in RFC 7914.

From the abstract:

  We prove that scrypt is optimally memory hard, i.e., its cumulative memory complexity (cmc) in the parallel random oracle model is $\Omega(n^2 \cdot w)$, where $w$ and $n$ are the output length and number of invocations of the underlying hash function, respectively.

Additionally in the introduction:

  In this work, in Section 5, we also prove an optimal $\Omega(n^2 \cdot w)$ lower bound on the parallel cumulative pebbling complexity for a game which abstracts the evaluation of scrypt: we consider a path of length $n$, and an adversary must pebble $n$ randomly chosen nodes on this graph, where the ith challenge node is only revealed once the node of challenge $i − 1$ is pebbled. This already gives an optimal $\Omega(n^2 \cdot w)$ lower bound on $cc_{mem}$ for scrypt for adversaries who are only allowed to store entire labels, but not any functions thereof.

From my understanding, it would be possible for an adversary to formulate a strategy that is a suitable compromise between memory and runtime complexity, e.g. where pebbles for $X_0, X_1, \dots , X_{n−1}$ are stored for only the even $i$, thus halving the worst case memory usage, while also having the worst case runtime, but yet leaving the total memory·time cost the same as before.

Question

For a single system, I'd say hardware cost is nonlinear with respect to CPU performance or size of onboard memory, i.e components representing the extreme of either spectrum may be exponentially more expensive. Thus to lessen the rate of return or increase the necessary capital investment an attacker would expect, we might like to mitigate the usability of midrange hardware that would otherwise be the most economical to use.

To visualize my rudimentary thoughts, I've included a crude graph below, where x and y axis are memory and time usage. The volume of the orange rectangle intersecting the purple line at the green point represents the total memory·time cost for any configuration, e.g. if you had sufficient memory one could compute the hash in $\frac{1}{2}$ time units. I was wondering if a problem could be formulated such make the memory·time cost follow the red curve instead, thus pushing an adversary further towards hardware extremes to achieve optimal memory·time costs while to the detriment of hardware cost.

  https://www.desmos.com/calculator/rpjseuy0sj

Perhaps there are studies some of you may know that touch on optimal efficient outcomes from an economic standpoint, i.e. considering hardware investment, operational costs, expected return per solution. I guess this sounds like a miners optimization problem when working with crypto currencies that require proof of work, but I'm slightly more interested in the economics the motivate attackers or scammers.

@misc{cryptoeprint:2016:989,
author = {Jo\"el Alwen and Binyi Chen and Krzysztof Pietrzak and Leonid Reyzin and Stefano Tessaro},
title = {Scrypt is Maximally Memory-Hard},
howpublished = {Cryptology ePrint Archive, Report 2016/989},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/989}},
}

Basically

Are there any functions that render a linear combination of memory or runtime approaches less efficient than committing solely to either a memory or compute speed optimizations, thus always making midrange hardware unsuitable for profitable attacks?

I had been thinking of this question for quite a time, but without a satisfying answer: it seemed to be a problem that had never really been considered in the literature (at least, not in the theoretical cryptography community).

Incidentally, I was just checking the ePrint archive this morning, and stumbled upon this paper which was added today to the archive, which focuses exactly on your question. It introduces a new complexity measure that accounts for the fact that time-memory trade-off do not scale linearly with respect to the hardware cost. I've not read it in details yet (I plan to), but the authors are among the leading researchers on memory-hard functions (subsets of the authors developed the theoretical model for analyzing MHFs, described the best known attacks on Argon and Balloon, gave new constructions, and proved the maximal memory hardness of Scrypt). It should be worth reading.


Recovering a secret that has been blinded several times I'm analyzing a protocol that, during one of the steps, sends a blinded secret. Let's denote the secret $x \in \mathbb Z_p^*$ (for $p$ prime) and the blinded secret $y$, so that $y = r\cdot x \bmod p$, where $r$ is a blinding factor randomly sampled from $\mathbb Z_p^*$. We can assume that the blinding factors won't repeat.

Several runs of the protocol would produce several $y_i$ values, with the same fixed secret $x$:

$$y_1 = r_1 \cdot x  \bmod p$$
$$y_2 = r_2 \cdot x  \bmod p$$
$$...$$
$$y_n = r_n \cdot x  \bmod p$$

Knowing only the $y_i$ values, what would be the best algorithm to retrieve $x$?

If all we know are the blinded values $y_i$ (and the modulus $p$), and if the blinding factors $r_i$ are indeed sampled randomly from the multiplicative group modulo $p$, I don't see any way to recover the secret $x$.

This is because, for any list of blinded values $y_i$ and any candidate $x$ value, we can compute a unique list of blinding values $r_i \equiv y_i \cdot x^{-1} \pmod p$ that, when multiplied by $x$ modulo $p$, will yield exactly those blinded values.  Given that the $r_i$ values are chosen randomly, this particular list of blinding values is exactly as likely as any other.  Thus, this blinding scheme appears to be unconditionally secure.

(Also, the knowledge that the $r_i$ values cannot repeat won't help, since all it implies is that the $y_i$ values won't repeat either.  If we did observe repeated $y_i$ values for the same secret $x$, we would know that the corresponding $r_i$ values must be the same, but would still gain no further knowledge about $x$.)


Are additional PGP subkeys still needed for smartcards? After having purchased a USB GnuPG smartcard, I visited the manufacturer's website. A tutorial by the FSFE was mentioned there as the preferred way of setting up the smartcard.

However, this tutorial seems to be a bit outdated as the output of gpg --gen-key doesn't offer the option to create a "RSA + RSA"-keypair:

Please select what kind of key you want:
  (1) DSA and Elgamal (default)
  (2) DSA (sign only)
  (5) RSA (sign only)

The author chooses the first option and continues by generating two RSA subkeys of the DSA key. These two subkeys (one for signing, the second for encrypting) are then transferred to the smartcard. The Elgamal key is deleted, unused.

So my questions here – as an owner of a keypair consisting of two RSA keys, default in GnuPG for quite a long time – are: Do I really need to generate new subkeys for the smartcard? Or is this measure included in the tutorial for historical reasons (as smartcards seem to only support storing RSA keys)?

I don't know if, from the security point of view, there are reasons against putting your "master" key on a smartcard. But even if, wouldn't it be enough to generate one second subkey for signing instead of two new subkeys?

Or is this measure included in the tutorial for historical reasons (as
  smartcards seem to only support storing RSA keys)?

While it is true that most (all?) OpenPGP compliant smart cards only support RSA, the likely reason for generating the keys in the tutorial was to show you how to generate keys and / or push them onto the card which is useful information in by itself.

  I don't know if, from the security point of view, there are reasons
  against putting your "master" key on a smartcard.

There's nothing technically stopping you from putting your master key on your smart card. However when you lose the card, this master key, which has all sorts of hard-worked-for trust signatures is now gone. This certainly isn't something you want to risk usually (which is why better HSMs offer a way to backup keys). So you usually generate the master key in software, store it away safely and redundantly and maybe push a copy onto the card.

  Do I really need to generate new subkeys for the smartcard?

No. While it's strongly advisable from a security standpoint to only have your keys on your card (so they're actually protected by the hardware and not by the software storage or the hardware) it is not mandatory.
Let's just assume that you have a software key shared between a mobile device and a computer. Let's further assume the mobile device is running iOS which is fairly good security-wise and the computer is running Windows 7 (which is less good security-wise). If you push your keys off the Windows PC an attacker would have to compromise your locked-down mobile device or the card which is both harder than compromising your Windows installation, so there you've gained some security.

  But even if, wouldn't it be enough to generate one second subkey for
  signing instead of two new subkeys?

The interesting property of master keys is not that they can sign (S) stuff, but rather that they can certify (C) other keys to be belonging to you which as far as I know is exclusive to the master key in a set of keys.


Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows the generator polynomial $g(x)$, and also, if one can obtain a parity check matrix $H$ of the form $XYZ$, where

$ X = \left( \begin{array}{cccc}
g_t & 0 & \dots & 0 \\
g_{t-1} & g_t & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
g_1 & g_2 & \dots & g_t \\
\end{array}\right) $

$ Y = \left( \begin{array}{cccc}
1 & 1 & \dots & 1 \\
l_1 & l_2 & \dots & l_n \\
l_1^2 & l_2^2 & \dots & l_n^2 \\
\vdots & \vdots & \ddots & \vdots \\
l_1^{t-1} & l_2^{t-1} & \dots & l_n^{t-1} \\
\end{array}\right) $

$ Z = \left( \begin{array}{cccc}
\frac{1}{g(l_1)} & & & \\
 & \frac{1}{g(l_2)} & & \\
 & & \ddots & \\
& & & \frac{1}{g(l_n)} \\
\end{array}\right) $

as in the paper by Engelbert, Overbeck and Schmidt (1, 2), since here we are able to recover a multiple of the matrix $X$ and so a multiple of g(x) which generates the same code. My question is, is it possible to efficiently decode the code whenever one knows ANY generator matrix or ANY parity check matrix for the binary irreducible Goppa code?

Also, on p.15, Sec. 3.1 of the Engelbert et al. paper an attacker is assumed to know a generator matrix $SG'$ for the Goppa code and a corresponding systematic check matrix $H'$. The attacker is then assumed to be able to recover matrices P an M such that $M^{-1}H'P^{-1}=H$ where $H=XYZ$ is of the above form (and thus, decode the code). Why is this assumption feasible? How would an attacker know at all when $H=XYZ$? Also, why should H generate the same subspace as H'?

Finally, the section 3.1 of the paper claims that if in a McEliece system with public code generator matrix $G=SG'P$ the matrix $P$ is revealed, then it is possible to recover $g(x)$. How? The only way I can think of it is that if $c$ is a codeword in a code generated by $SG'P$ then $cP^{-1}$ is a codeword in a Goppa code generated by $SG'$ and so the syndrome $S_{cP^{-1}}(x)=\sum (cP^{-1})_i/(X-\gamma_i)$ which the attacker can calculate is congruent to zero modulo $g(x)$. Is this a way to obtain $g(x)$?

If one knows $\gamma_1,\cdots,\gamma_n$ and $g(x)$ then for any $n$-long binary vector $V$ one can form the polynomial
$$v(x):=\prod_{i:V\cdot e_i} (x-\gamma_i)$$
and the syndrome polynomial $s(x)=v'(x)/v(x)\pmod{g(x)}$. This is all the information required by Paterson's decoding algorithm, independent of the basis used for the generator matrix and/or parity check matrix.
Section 3.1 should be read as an argument of the importance of keeping $M$ and $P$ secret as they are essentially the private key. It should be a very unreasonable assumption that the attacker can obtain these as this would break the system.
The recovery of $g(x)$ starts off as pretty much as you describe. For $V$ any codeword, compute the corresponding $v'(x)$ which we know is a multiple of $g(x)$. If we do this for two codewords, we can take the GCD which must also be a multiple of $g(x)$. After a handful of GCDs we have almost certainly recovered $g(x)$.
Note that that there is a equivalence between Goppa codes where columns are relabelled according to a linear function and $g(x)$ undergoes the corresponding linear change of variable. Recovering the columns labels of any equivalent code would also allow decoding.


Which homomorphic encryption scheme has the same size of plaintext space and ciphertext space? I want to pre-compute the result for all possible ciphertext of a homomorphic encryption. Is it acheivable?

Is there a fully homomorphic encryption scheme that has the same size of plaintext space and ciphertext space?

Is there a fully homomorphic encryption scheme that has the same size of plaintext space and ciphertext space?

As far as I know, none have this property and it makes sense when you think about it.

IF the plaintext and ciphertext spaces are the same size, you cannot achieve semantic security. A good example of this is RSA. In order to achieve semantic security in RSA, we shrink the plaintext space so that we can add random padding.

Semantic security is very important, especially when we are talking public key encryption. W/O it, an attacker can simply use the public key to encrypt guesses of ciphertexts and then compare with the ciphertext of interest to figure out the plaintext. FHE applications would be especially vulnerable to these sorts of attacks as we are likely not encrypting random values, but are encrypting values with some meaning (salaries, votes, etc) so that we can compute on these values.

  I want to pre-compute the result for all possible ciphertext of a homomorphic encryption. Is it achievable?

I am not exactly sure what you mean here, but I doubt it is achievable. The ciphertext spaces in modern public-key systems are huge ($2^{2048}$ for 2048 bit RSA for example). Precomputing all of that would take more storage space than you can even dream about having. For a comparison, the estimated number of atoms in the observable universe is $10^{82}\approx 2^{272}$. So even if you could store one pre-computation per atom, it would take more atoms than what we can even observe in the universe to store your table.

Now, for this example I used RSA. FHE ciphers today have larger ciphertext space than even RSA.


factorization of an integer $N$ that is in special format Suppose $p_0$ and $q_0$ are known prime numbers and define $p_i$ and $q_i$ as follows:

$$p_{i+1} = next\_prime(p_i^2 + q_i^2), \qquad i \ge 0$$ and

$$q_{i+1} = next\_prime(2p_iq_i), \qquad i \ge 0$$ and
$$N_{i+1} = p_{i+1}q_{i+1}, \qquad i \ge 0$$

I want to know is there efficient algorithm to factor $N_{i}$? What happen when the $p_0$ and $q_0$ be unknown? So can we factor an integer $N_1$ for example for unknown $p_0$ and $q_0$?

If $p_0$ and $q_0$ are known then so are $p_i$ and $q_i$ by iterating.

To factor $N$, do the following:

$(p,q) \gets (p_0,q_0)$
while ($p \nmid N$) do $(p,q) \gets (next\_prime(p^2+q^2), next\_prime(2pq))$
Return $(p,q)$


Zero knowledge proofs in practice What are the practical problems of using zero knowledge proofs, for instance in the field of authentication?

Currently, there are very few practical barriers to deploying zero-knowledge proofs. They've been deployed in everything from anonymous credentials to cryptocurrencies to privacy-preserving survey systems. Very fast academic systems have been developed which use zero-knowledge proofs for privacy-preserving distributed machine learning. This last example hasn't been deployed yet, but clearly is fast and scalable enough to be used in practice.


Use of the master key in Delerablée's Identity-based Broadcast Encryption I'm reading “Identity-Based Broadcast Encryption with
Constant Size Ciphertexts and Private Keys” by Cécile Delerablée.

On page 207, the encryption process needs $\gamma$ which is part of the master key.
This does not make sense to me.

I want to know whether I read this thesis wrongly or not.
Can anybody give me a opinion?

That value can be computed with the data you have in the public key. You just need to use the fact: $$ h^{\gamma} \times h^{H(ID)} = h^{\gamma + H(ID)}. $$

Note that in the public key you have all the $h^{\gamma^i}$ you need for the computation.

The notation used in the paper is there to keep the notation easy and clear.

If you want to compute the correct value you could compute the product:
$$\pi = \prod_{i=1}^s (\gamma + H(ID_i))$$ considering $\gamma$ as unknown and later compute $h^\pi$ making the needed substitutions.


PRP, PRF and modular arithmetic Are there any arithmetic or mathematical functions that can be used as PRPs or PRFs ?  Since, Conventional block ciphers like AES are that are proven to be good PRPs are not based on mathematics but on other principles like confusion and diffusion etc.

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. –  xagawa

  @xagawa Yes, I want that :-) –  Dingo13

I list the PRFs based on the number-theoretical assumptions.
They are ``arithmetic or mathematical function.''
You can use the Feistel network to obtain (S)PRPs from PRFs in theory.

From the DDH assumption

The Naor-Reingold Pseudorandom Function is a PRF based on the DDH assumption.
Let $\mathbb{G}$ be a finite group of order prime $q$ with a generator $g$,
on which the DDH problem is hard.
Let $\{0,1\}^\ell$ be a domain.
The function is defined as
$$\mathrm{PRF_{NR}}(k, x) = g^{a_0 \prod_{i=1}^{\ell} a_i^{x_i}},$$
where $k = (a_0,a_1\dots,a_{\ell}) \in \mathbb{Z}_q^{\ell}$.
For the proof, see the original article in J. ACM.

Lewko and Waters generalized the NR PRFs in CCS 2009 (and ePrint 2009/486).
Their PRFs are based on the decisional linear assumption (and its weaker variants).

Most efficient one

Under stronger assumptions such as the DHI assumption,
 we have a cute PRF, say,
the Dodis-Yampolskiy PRF proposed as
Verifiable Random Function (VRF).

Let $\{0,1\}^{\ell}$ be the domain of PRF.
Suppose that $2^{\ell}$ is a polynoimal of the security parameter.
The DY PRF is defined on a symmetric bilinear group as follows:
$$\mathrm{PRF}_{DY}(k,x) = e(g,g)^{1/(x+k)},$$
where $k \in \mathbb{Z}_q$.

From the factoring assumption

This is a classical result obtained by a combining the Blum-Blum-Shub PRG and the Goldreich-Goldwasser-Micali PRF from any PRG.
Naor, Reingold, and Rosen improved efficiency of factoring-based PRFs.
See the original article available at ECCC TR 2001-064,

From the hardness of lattice problems

Nowadays, the lattice problems are often employed to construct cryptogrphic primitives.
You can find the PRFs from lattices in
Banerjee, Peikert, and Rosen (EUROCRYPT 2012),
Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013),
and Banerjee and Peikert (ePrint 2014/074).


Hardwired secret key in public / private key encryption I am new to cryptography and I need to know some details about the hardwired keys.

Taking as an example the paper "Multi-Input Functional Encryption", a key is hardwired in the description of the key generation scheme.

Is this technique related to encryption schemes or it is a form of circuit construction?

“Hardwiring” an input into a (say, Boolean) circuit usually means taking a circuit $C$ with two inputs $x\in\{0,1\}^n$, $y\in\{0,1\}^m$ and then fixing the inputs corresponding to $y$. This gives the circuit $C_y$ that for every $x$ returns $C(x,y)$ [AB]. Thus, hardwiring is more about circuits and has nothing to do with encryption schemes.

In the example of multi-input functional encryption, the circuit $\mathsf{G}_f$ can be seen as a function that takes a master secret key and $n$ ciphertexts as input. By hardwiring a particular $\mathsf{MSK}$, you are fixing the first input to the circuit $\mathsf{G}_f$ to this $\mathsf{MSK}$.

[AB]: Arora and Barak. Computational Complexity: A Modern Approach.


Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501.
To summarize, assume we have a matrix $G$ where, on input $b$,  we can efficiently find $(s,e)$ such that $s^TG+e^T=b^T$. Then for an invertible $H$, and a random $\overline{A}$, we produce a matrix $A$ by
$$ A = [\overline{A} | HG - \overline{A}R]$$
for some random $R$. This has the property that $A\begin{pmatrix} R\\ I\end{pmatrix} = HG$.
Then the LWE inversion for $A$ is given as follows: We start with some $b$. We first compute $\hat{b}^T = b^T\begin{pmatrix} R\\ I\end{pmatrix}$. Then we find $(\hat{s},\hat{e})$ such that $\hat{s}^TG+\hat{e}^T=\hat{b}T$. Then we let $s^T = \hat{s}^TH^{-1}$ and $e^T = b^T - s^TA$ be the LWE sample $(s,e)$ satisfying $s^TA+e^T = b^T$ with $e$ small.
It's clear to me that by the definition of $e^T$, $s^TA+e^T=b^T$ holds. In fact that would work for any $s$. So the hard part is to show that $e$ is small, and that's what I can't figure out.
One thing I can show is that
$$\begin{align}
e^T\begin{pmatrix} R \\ I\end{pmatrix} = & b^T\begin{pmatrix} R \\ I \end{pmatrix} - s^TA\begin{pmatrix} R \\ I\end{pmatrix}\\
= & \hat{b}^T - \hat{s}^TH^{-1}HG\\
=& \hat{b}^T - \hat{s}^TG\\
= & \hat{b}^T - \hat{b}^T + \hat{e}^T\\
= & \hat{e}^T
\end{align}$$
So if $R$ were invertible and diagonalizable, I could argue that $e^T$ must be small in terms of the smallest singular value of $R$ and the size of $\hat{e}^T$. However, that doesn't seem to be the approach of the paper, which focuses instead on the largest singular value of $R$. Their proof of Theorem 5.4 doesn't make sense to me: I don't understand what they are trying to prove, and why they are not showing that $e$ is small.

We are given some $b^t = s^t A + e^t$ for $A$ of the above form and short $e$, and wish to recover $s$ (which will immediately give us $e$ as well). If $e$ is short enough, then $\hat{b}^t = (s^t H) G + \hat{e}$ for some sufficiently short $\hat{e}$. (This is where we use the bound on the expansion, or top singular value, of $R$.) Therefore, the LWE inverter for $G$ will recover $s^t H$ (and $\hat{e}$), from which the original $s$ can be recovered via $H^{-1}$.
It’s very important that $e$ is short enough to ensure that $\hat{e}$ is short enough. If the latter is too long, then the LWE inverter for $G$ might return the wrong answer for $s^t H$, leading to a wrong $s$ and thereby a wrong, probably very long $e$.


Cyclic Groups Other than $\mathbb{Z}^*_n$ or Elliptic Curves I see two types of cyclic groups are most commonly used in cryptography:

modulo multiplicative group of integers with prime order
elliptic curves

Are there any other cyclic groups used in cryptography?

The multiplicative group $\mathbb{F}_{2^n}^{\ast}$ (which is cyclic) is used in defining LFSR sequences and nonlinearly filtered sequences typically as building blocks of stream ciphers.

This group is part of the picture for block ciphers; most prominently, the field $\mathbb{F}_{2^n}$ is used (for $n=8$) for defining the AES. Boolean functions and vector boolean functions defined over $\mathbb{F}_{2^n}$ also appear.


How to generate whitebox AES decryption algorithm and code, with existing WB-AES encryption code? I can find several whitebox AES 128 implementations on Github, such as wbaes-1, wbaes-2, wbaes-3, etc. All of them are developed based on WB AES encryption. Ideally, most implementations include two parts:

(1). Table_Generator.c  (or .cpp, .h ...). Input: 16-byte key; Output: a big lookup table (e.g., table.h), where the key information is already hidden in this lookup table

(2). AES_Encrypt.c. Input: plain text & table generated from (1); Output: cipher text

But I need decryption implementation as well.

First, let me confirm one basic question:

Encryption table & decryption table are generated separately, using one same key (e.g., 16 byte key for AES128)? Correct? which means there are two table generation algorithms (and hence two separate lookup tables) - one encryption, one for decryption.

Then, the main questions:

What are the important steps to modify an WB encryption project into
a WB decryption project?
Is there any WB AES decryption implementation for me to read?

Encryption table & decryption table are generated separately, using one same key (e.g., 16 byte key for AES128)? Correct? which means there are two table generation algorithms (and hence two separate lookup tables) - one encryption, one for decryption.

yes, this is correct. you need two different sets of tables to implement the encryption and the decryption algorithm. Both set are generated using, of course, the same secret AES key.

  What are the important steps to modify an WB encryption project into a WB decryption project?

To implement the AES decryption, one should undo all operation one-by-one doing the inverse: you could, therefore, rewrite the table generator algorithm following this logic and then writing the corresponding decryption function where the round structure is inversed.
Otherwise one can notice that decryption can be implemented using the same round structure as encryption but with a slightly modified key schedule (and the operations replaced by their inverses).
I suggest using this second way to implement decryption, as you only need to change the key schedule function and the rest of the implementation stays the same.

EDIT: more details are available on the AES standard publication at Section 5.3.5 where the Equivalent Inverse Cipher is described.

  Is there any WB AES decryption implementation for me to read?

if I remember correctly, the following implementation contains both encryption and decryption direction.
You can also read the very good tutorial by James A. Muir (pdf)


Could a larger block size increase the security of the block cipher? I want to know if a larger block size increase the security of the block cipher?

TL;DR: a larger block size won't help to make the block cipher itself more secure, but it can be used to make the schemes using the block cipher more secure.

The block size basically determines the number of possible permutations: the possible ways to combine all the possible plaintext blocks with the possible ciphertext blocks. The number of permutations grows much faster per bit of the block size than the number of possible keys from the key size. In that sense it is unlikely that a larger block size will do much for the security of the cipher.

Modes of operation however do rely on the block size for other purposes. For instance, the counter size of AES-CTR is defined to be the same size as the input block size. That counter usually consists of a random nonce and a counter part, for instance 64 bits for the nonce and 64 bits for the counter. However 64 bits is not that much for a nonce; as the birthday problem applies you can only encrypt about $2^{32}$ ciphertext before the counter could repeat. Now this isn't a huge problem, but it would be avoided with a block size of 256 bits (or, indeed a tweak, or both).

Specific constructions could also require a larger block size. For instance a hash function generally relies on large state. To go from one large state to another a block cipher could be used. Obviously it would need to have a large state and a large block size itself. There are other ways to do this with a cipher with a smaller block size but it won't be as efficient.


Collision-resistance of $H\Bigl(\bigl(H(m_1\mathbin\| 1)\oplus H(m_2\mathbin\|2)\oplus\dots\oplus H(m_n\mathbin\|n)\bigr)\mathbin\|n\Bigr)$? In this answer and discussion, it is considered a distributable hash

$$\tilde H(m)\ =\ H\Bigl(\bigl(H(m_1\mathbin\| 1)\oplus H(m_2\mathbin\|2)\oplus\dots\oplus H(m_n\mathbin\|n)\bigr)\mathbin\|n\Bigr)$$

where the $m_i$ are $n$ segments (say of fixed size) of message $m$, and $H$ is a cryptographic hash (say of $b$-bit and assumed secure in the ROM).

What can we say about the collision-resistance of $\tilde H$ as a function of $b$ ?

What can we say about the collision-resistance of $\tilde H$ as a function of $b$ ?

That it is effectively nonexistent; it is easy to generate collisions (and second preimages).

You can generate a second preimage by selecting two blocks $m'_i, m''_i$ to correspond to each original block $m_i$; you compute $H(m'_i \mathbin\| i), H(m''_i \mathbin\| i)$, and then use linear algebra (e.g. Gaussian Elimination) to see which combination of $m'_i, m''_i$ all xor the same as the original sequence of $m_i$; that combination hashes to the same value.  As long as the original message is at least $b$ blocks long (that is, $n \ge b$), such a combination exists with good probability.

Once you can create second preimages, you can generate collisions by picking a message and generating a second preimage for it.


Uniqueness of checksums using DES-MAC encryption? I'm in an Intro to Computer Security class, and one concept I'm having trouble understanding is how two different files could produce the same checksum. How would you produce the same checksum given two different files? So far, through reading the book, I found mention of something called the "pidgeonhole principle" that seems to indicate this is possible, but I'm not sure how.

Think of it this way:

How many possible files are there?
How many possible checksums are there?

If the number of possible files is larger than the number of possible checksums, then there must be at least two files with the same checksum.

This is one of the things known as the "pigeon-hole principle"; the idea is that if you are placing pigeons in pigeon holes, and there are more pigeons than holes, then some hole somewhere will have two pigeons.

Now, if you go on further, you'll find that, if you know the MAC key, it's actually quite easy, with DES-MAC, to produce two files with the same checksum (or, for that matter, a file with a specific checksum).  However, you're not quite ready for that.


How should one handle the identity value and other "obviously" weak secret random values? In RSA, ECDSA, ElGamal and quite a few other schemes, using a secret (random) value equal to 1 might not provide any form of security, while still being mathematically sound.

For RSA, ECDSA or ElGamal, the secret random value might typically be the secret exponent, for example. Or for ElGamal and ECDSA, it might be the ephemeral secret we need to encrypt or sign (the infamous $k$ for ECDSA).

Arguably this holds for secret values smaller than 80 bits, as it might otherwise well be attacked using a brute force search attack.

The same might hold for secret values whose secrecy is crucial to the security of the scheme at hand, such as the ephemeral $k$ used in ECDSA signatures, although specific scheme might have specific guidelines depending on their specific requirements.

In order to avoid such obvious problems, are there any kind of (official or standard) recommendations regarding the rejection of "bad" random values based on certain criteria?

Or more broadly, in the same way that we have recommendations for the group size or the way to generate large primes (see keylength.com), do we have some kind of guidelines for the generation of the "secret random values" we have in cryptographic software. (For instance, I do not see any kind of "sanity checks" being performed on the $k$ values generated for ECDSA as per FIPS 186-4, even though it is crucial for $k$ values to be unbiased. The only "standard" that I'm aware of that specify how the secret random value should be generated, and it only covers the specific case of the generation $k$, is the RFC6979 and is using derandomization, like the standard for EdDSA (RFC8032). But this is not always possible for secret values.)

Is this documented in some other NIST document, or in some RFC?

PS: notice this question is assuming randomness is difficult for implementation, and that as such it might be best to have "fail-safes" in place in a way to have defense in depth.

In RSA, ECDSA, ElGamal and quite a few other schemes, using a secret (random) value equal to 1 might not provide any form of security, while still being mathematically sound.

One could argue that the exponent '1' doesn't have any security (because it's easy to compute the discrete log of $1G$); on the other hand, you could equally argue that the value $z = 8827773752...7876547109$ equally does not provide any security, because an attacker could easily compute $zG$ and if he sees that, he knows the discrete log.

  Arguably this holds for secret values smaller than 80 bits, as it might otherwise well be attacked using a brute force search attack.

This is true, if the attacker knows apriori that the secret value was smaller than 80 bits.  Actually, if the attacker knows that, he can find the discrete log with $O(2^{40})$ effort, which is doable by private individuals with access to somewhat more than average computational resources.

On the other hand, taking a random $kG$ value, and making that guess will succeed (assuming a 256 bit curve) with probability circa $2^{-176}$.  In addition, this doesn't only apply only to secrets smaller than 80 bits; if the attacker guesses that the top 176 bits are the value $z$ (above), then he can compute $kG - (z2^{80})G$; if his guess is correct, that'll be in the range $0G$ to $2^{80}G$, and so the brute force effort will succeed (and with the same success probability).

Hence, it is hard to say that a point that happens to be in the range $1G … 2^{80}G$ is any weaker than a point that happens to be in the range $(z2^{80}+1)G … (z2^{80}+2^{80})G$ (and all points are in such a range, for some value of $z$).

  do we have some kind of guidelines for the generation of the "secret random values" we have in cryptographic software.

Why, yes, yes we do.  You pointed out the sections in FIPS 186-4 where they make recommendations (mandates, actually, we're talking about FIPS here) on how to generate such random values.

  even though it is crucial for $k$ values to be unbiased.

And these recommendations accomplish precisely that.  They do assume that the approved RBG that is used generates indistinguishable-from-random bit patterns; as far as we know, the approved ones do precisely this.

You appear to be asking for some tests that reject certain values (such as 1); such a test would introduce a bias (if possibly a tiny one); such a bias is precisely what we're trying to avoid...


What is the size of codomain of a function $G(x) = F^A(x) \oplus F^B(x)$, where $F(x) = \text{Keccak-}f[1600](x)$? Assuming that $m$ is a multiset of bitstrings where all bitstrings have the same length, let $D(m)$ denote the number of distinct elements in $m$. That is, $D(m)$ is equal to the dimension of $m$. For example, if $$m = \{00, 10, 11, 10, 11\},$$ then $D(m)=3$.

Let $F(x) = \text{Keccak-}f[1600](x)$, the block permutation function of SHA-3 (for $64$-bit words). We can define the following notation: $$\begin{array}{l}
{F^0(x)} = x,\\
{F^1(x)} = F(x),\\
{F^2(x)} = F(F(x)),\\
{F^3(x)} = F(F(F(x))),\\
\ldots
\end{array}$$

Assuming that $A$ and $B$ are two different natural numbers greater than or equal to $0$, let $G_{A, B}(x)$ denote a function defined as $$G_{A, B}(x) = F^A(x) \oplus F^B(x),$$

where $x$ denotes a $1600$-bit input and $\oplus$ denotes an XOR operation.

Assuming that $L = 2^{1600}$, let $S_i$ denote an $i$-th bitstring from a set of all possible $1600$-bit inputs:
$$\begin{array}{l}
S_1 = 0^{1600},\\
S_2 = 0^{1599}1,\\
\ldots,\\
S_{L-1} = 1^{1599}0,\\
S_L = 1^{1600}.\\
\end{array}$$

Let $A$ and $B$ denote two arbitrarily large, but different natural numbers (one of them is allowed to be equal to $0$). For example, $$A = 0, B = 1$$ or $$A = 2^{3456789}, B = 9^{876543210}$$ are valid pairs.

Then

$$\begin{array}{l}
S_{A, B}[i] = G_{A, B}(S_i),\\
C_{A, B} = \{S_{A, B}[1], S_{A, B}[2], \ldots, S_{A, B}[L-1], S_{A, B}[L]\}.\\
\end{array}$$

The question: can we assume that $D(C_{A, B})$ is expected to be approximately equal to $$(1-1/e) \times 2^{1600} = 10^{481} \times 2,810560755\ldots$$ for all (or almost all) pairs of $A$ and $B$?

Let $\pi$ and $\sigma$ be two independent uniform random permutations, and $f$ a uniform random function.  The best advantage of any $q$-query algorithm to distinguish $\pi + \sigma$ from $f$ is bounded by $(q/2^n)^{1.5}$[1].  In this case, the expected fraction of distinct outputs of $\pi + \sigma$ can't be too far from the expected fraction of distinct outputs from $f$, which is $1 - e^{-1} \approx 63\%$.

What about $\sigma = \pi^2$, or $\sigma = \pi^k$ for $k > 2$?  Then $\pi$ and $\sigma$ are not independent.  Nevertheless, it would be rather surprising if this situation were substantially different.

What about $\pi^{2^{3456789}} + \pi^{2^{987654321}}$ instead of $\pi + \pi^2$?  This is the same as $\pi + \pi^{2^{987654321 - 3456789}}$.  It's not clear why you would be worried about uncomputably large exponents like this unless you were flailing around without principle trying to make a design that looks complicated.


DES and Feistel Cipher I have a question that I have not found the answers to in many books.

Does the expansion permutation have to map values to the same space?
For example, in DES, 32 bits are expanded into 48 bits via an expansion permutation where the values are shuffled around but do not change.

Consider the following expansion function for 4 bits into 6 bits

$e[{a_0}{a_1}{a_2}{a_3}]={a_0}{a_0}{a_1}{a_2}{a_3}{a_3}$

Is this a legal permutation? or is it not cause it can map to new values in which we didn't posses before, for example 1001 can be mapped into a new value 110011 that didn't exist before.

I understand the encryption would encrypt regardless, but is using that permutation allows for us to reverse the encryption by running the keys in reverse?

A "permutation", by definition, must have the same domain and range, i.e., the same possible inputs and possible outputs. You can look at it as either as a bijective function from some domain onto the same domain, or as a reordering of that domain.  Any reordering of things may also be referred to as a "permutation".

The DES "expansion permutation" is called a permutation, because it rearranges bits, but it is not a permutation at all, because it copies bits as well.

The purpose of the expansion permutation is to make sure the S-boxes have overlapping keys... for some arcane reason.  It's part of providing "confusion and diffusion", and it has nothing to do with ensuring that the encryption can be reversed.

It is the Feistel structure itself that ensures that the encryption is reversible no matter what the Feistel function $f$ is.  That gives the designers of encryption algorithms lots of leeway to do whatever they want without having to worry about using only reversible operations.

Mapping $(A,B)$ onto $(A \oplus f(B),B)$ is easily reversed just by doing it again:
$$(A \oplus f(B),B) -> (A\oplus f(B) \oplus f(B),B) = (A,B)$$

where $\oplus$ is the XOR operation.

Since DES is encryption is essentially a sequence of Feistel rounds, it can be decrypted by performing the same Feistel operations in reverse order.


Short padding + known prefix RSA attack Suppose I have a message in the form of:

$m = \text{prefix} \mathbin\| \text{secret} \mathbin\| \text{padding}$

We have:

$e=3$
$n$
$n_\text{padding}$ (length of the random padding, <$1/4$ of $m$)
$\text{prefix}$, which is small, only 5 bytes

Is there a way to recover the message with these parameters? I thought about using a variant of Coppersmith but didn't come across anything satisfactory that seemed to work using what I have.

So after some more help and an extensive reboot of my math skills, I found the answer. The information that I overlooked but is crucial to have is the total length of the message. Moreover, we also need a second message with slightly changed parameters. This thus presupposes that an attacker has access to at least 2 known ciphertexts with known prefix and that both ciphertexts only differ by the prefix (known) and padding (unknown).

Following the above we end up with:

$c_1$ = $(prefix_1 + secret + padding_1)^e mod \ n$
$c_2$ = $(prefix_2 + secret + padding_2)^e mod \ n$

Now, without the prefix change this would be a simple case of Coppersmith's short pad attack. But the prefix requires some changes. This is where the length comes in handy: if we know the prefix change (e.g. a 0 byte becomes a 1 byte), and we know the total length, we can find the additional delta between the 2 ciphertexts (i.e. the delta besides from the padding), since we know which bits changed and can then add/substract $2^i$ for all changed $bit_i$

Example: if

$prefix_1$ = 'hello\x00'

$prefix_2$ =   'hello\x01'

and the total message length (including secret and padding) is 100, we know that the 94th byte changed from 0 to 1. In bits, it means the 752nd bit changed from 0 to 1, hence adding $2^{752}$.

From here we can pick up the Coppersmith attack whereby the second polynomial needs to incorporate the difference:

$g_2(x,y) = (x+y+\Delta)^e - c_2$

The rest follows the classic attack. Now once we have $y$, we can use the Franklin-Reiter related message attack with the small exception that we need to also add the $\Delta$ we calculated from the prefix.

I realize this might have gone beyond the scope of my answer but I thought it was an interesting twist on existing exploits that could help someone out in the future :)


The most secure hand cipher in 2020 I found this thread from 2011:
Is there a secure cryptosystem that can be performed mentally?
Are there new secure hand or pen-and-paper ciphers in 2020? (I know, that hand ciphers are not as secured as digital ciphers).

Are there new secure hand or pen-and-paper ciphers in 2020?

Not that I know for the modern definition of "cipher", which implies a short key reusable for multiple messages. It's difficult to make such cipher convenient and secure.
The closest match in the open literature may be Bruce Schneier's Solitaire, aka Pontifex. It's a stream cipher (barely) doable by hand with a deck of cards, but theoretically broken in the modern meaning of that: a sizable bias in the keystream was found by Paul Crowley (circa 1999). And there's further Analysis of Solitaire by Daniel Shiu, arXiv (2019). Yet according to Schneier's assessment of Solitaire in light of that:

for the short message lengths you’re likely to use a manual cipher for, it’s still secure and will likely remain secure.

Note: Shiu has outlined proposed modifications to improve Solitaire, but they make it even less practical.
If we relax what a cipher is, we can use the One Time Pad: it is very doable by hand and remains secure as long as the pad remains confidential and not reused. If the encryption is error-free and the plaintext natural language, humans doing decryption can manage to recover from their own errors or small alterations in ciphertext. Tamper-evident opaque envelopes provides some protection of the pad against xerox copy during transfer. Some paper allows dissolving used pages in hot water.
Problem is that carrying a sheet of paper with random characters, such as the pad, could get one a bullet in the head, or worse. So we might want to use an ordinary-looking book as a substitute. Say, the starting page number, line, and offset are chosen at random with the additional condition that no material in the book gets reused, and is coded in the first characters. Alphabetical characters starting from there are grouped by blocks of 5, only the last character in such block is used, and the sum modulo 26 of 6 such characters yields the pad character, near uniformly random and independent of others. Nowadays it's economical to print a single copy of a book, and plausible randomized variants of an existing novel can be AI-generated, so that computer-assisted cryptanalysis will fail even if it tries the original as the pad, and the printing will pass casual scrutiny by an observer. Legal draft have an advantage over novels: adversaries fall asleep.


Why Rejewski advanced three position for the right rotor in the second set of rotors in the Cyclometer he devised? In this article about decryption of Enigma(p.259), author says that

  the second set of rotors was stepped three positions beyond the groundsetting

in the Cyclometer Rejewski devised. I would like to know why did he advanced 3 positions for the right rotor in the second set of rotors instead of 1 or 2 positions for the same.

To understand why it was done so, it's necessary to understand what the cyclometer was. And to understand that, we need to get through a bit of encryption procedures for Enigma, as well as steps used to break that encryption.

The procedure for encrypting with Enigma was (simplified):

Set the machine to specific daily setting
Generate a random, 3 letter, key (say RFV)
Encrypt this key using the initial settings, twice
Set the machine to generated key and encrypt the rest
Prepend the encrypted key to the message

Because of this, the 1st letter of ciphertext and the 4th one were in fact the same cleartext letter, but encrypted with different settings (as the machine rotated rotors each letter). So were 2nd and 5th as well as 3rd and 6th.

The Rejewski's method worked by gathering a lot of messages from radio interception, and generating permutations from those. E.g. say you intercept 3 messages, with initial 6 letters of:

pkpjxi
jxixtm
xtmrcy

Than you have partial permutations of

p -> j -> x -> r -> ... (by taking 1st and 4th letter)
k -> x -> t -> c -> ... (by taking 2nd and 5th letter)
p -> i -> m -> y -> ... (by taking 3rd and 6th letter)

Those permutations were unique (or at least almost unique) for each possible initial setting of the machine. So, by recovering the permutations from the intercepted messages and looking them up in catalogue, one could recover (with some more tricks that are out of scope of this question) recover the daily keys, and thus all messages.

Now, after you recover the permutations from daily messages, you need the catalogue to look them up. This is where the cyclometer comes up. It wasn't a decryption tool, it was a tool to facilitate creating the catalogue. As you see, the permutations alternate between the same letter encrypted at first and fourth position (let's forget the other sets for brevity). One could encrypt with all possible settings and get the permutations from that, but cyclometer simplified that - it was two rotor sets, interconnected in a way that whatever you pressed was encrypted via first set, fed to the second set for encryption, than back to the first set and so on, until there was a cycle. As the Enigma advances the rotor after encrypting each letter, and the second rotor set in cyclometer mimics machine operation at 4th letter, the rotors in the second set had to be advanced by 3 characters.


Homomorphic encryption diagram and trouble about a paper I'm reading a paper based on Homomorphic Encryption: “Fully Homomorphic Encryption over the Integers: From Theory to Practice” (PDF).
Now, I need a diagram of this algorithm if possible with all the operation that the sender of cyber text do.
I'm reading the text and I encountered some problems:

Given several multiples $q_ip$ of $p$.

What is $q_i$?

$c = q p + 2r + m$.

When noise is raised/introduced in the system?

The author starts talking about multiples of $p$, because he wants to talk about the problem of find a $gcd$ (great common divisor) of a list of numbers (in this case, the $gcd$ is the secret $p$). He is somehow trying to make you understand why we cannot encrypt the binary messages $m \in \{0, 1\}$ by simply adding them to $q_i p$.

It means it would be insecure to use $qp + m$ as an encryption of a bit $m$, because encrypting a lot of bits $m_1, m_2, ..., m_N$ as $q_1p + m_1, q_2p + m_2, ..., q_Np + m_N$ would give the attacker a chance to recover the secret key $p$ from this list of encrypted values.

Therefore, to guarantee the security of the encryption process, we add a small noise. And to guarantee that the decryption will work, we chose this noise to be even, this is why we pick a small value $r$ and use $qp + 2r + m$ as the encryption of $m$.

Thus, the noise is introduced on the encryption. But, when we add or multiply two ciphertexts, we generate a third ciphertext whose noise is bigger than the noise of those two, so, we may say that the noise is also introduced when we operate over the ciphertexts.

And answering your comment: no, the sender does not choose the value of $2r$. It must be a random value. The only thing known is the interval in which the values of $r$ are sampled from and that interval is defined by the parameters that the sender chooses for the scheme (of course, following the restrictions that those parameters must respect).


What's the reason why CBC-MAC shouldn't use IV or random IV? I searched the answer but I'm not sure if I understood exactly, and have some other questions.

I understood that the reason for CBC-MAC not to have random IV is if CBC-MAC has a random IV, the attacker can change the P1 block, making the tag arbitrary, so the CBC-MAC scheme can be insecure. Am I right?

1-1. Attacker can make the tag arbitrary not depending on the IV because of the property of encryption blocks. Then why we should not use IV or should use all-zero IV?
If we use random IV, then a sender and receiver must share a IV before the receiver receives the tag and it is inefficient, so we don't have to use random IV. Did I understand right?
Are there any other attacks that can made if we use random IV?

I understood that the reason for CBC-MAC not to have random IV is if CBC-MAC has a random IV, the attacker can change the P1 block, making the tag arbitrary, so the CBC-MAC scheme can be insecure. Am I right?

If you assume that the attacker can know the first block of the message and can control the IV then it is easy to see that you can create an identical authentication tag for multiple IV / initial message block pairs. If the input of the first block encrypt and the following blocks are identical, then the authentication tag will repeat.

This won't work for the other blocks as the cipher will change the bits of the next vector independently of the change. An attacker doesn't gain much by being able to change 50% of the of the input of the cipher randomly.

  1-1. Attacker can make the tag arbitrary not depending on the IV because of the property of encryption blocks. Then why we should not use IV or should use all-zero IV?

I don't think the statement in the first sentence of the question is correct. The attacker should not be able to create a valid authentication tag, because the attacker does not know/control the key.

It's however unclear what you mean with encryption block property.

  If we use random IV, then a sender and receiver must share a IV before the receiver receives the tag and it is inefficient, so we don't have to use random IV. Did I understand right?

No. For CBC encryption the IV needs to be unpredictable to the attacker. There are however schemes such as encrypting a counter to generate an unpredictable IV without actually including it with the ciphertext.

As indicated, we don't use a random IV for CBC-MAC. CBC-MAC relies on CBC mode of operation but it doesn't use it for providing confidentiality. So the security requirements of the IV being unpredictable are not applicable to CBC-MAC.

  Are there any other attacks that can made if we use random IV?

I don't directly seen any.

After completely loosing integrity / authentication of a full block of the message, I guess we don't need any others.

Notes:

CBC requires an IV, so lets call this an all-zero IV (any other constant IV would have the same result, a zero IV is just easier to implement);
beware that CBC-MAC should only be used for messages with known-length and preferably a 128 bit (or higher) block cipher, use CMAC, HMAC or an authenticated cipher instead.


What security do Cryptographic Sponges offer against generic quantum attacks? In the face of non-quantum attacker, Keccak[r=1088,c=512] with 512 bits of output provides:

Collision resistance up to $2^{256}$ operations
Preimage resistance up to $2^{256}$ operations
Second preimage resistance up to $2^{256}$ operations

In general however, using quantum computing, specifically Grover's Algorithm, hash functions can be attacked more efficiently. Daniel J. Bernstein wrote about quantum attacks against all the second round SHA-3 candidates. However, in that paper, all the attacks against Keccak variants are against truncated hashes with an internal capacity of twice the hash length, for example Keccak[r=1152,c=448] with 224 bits of output.

My question is, if the full 512 bit hash output length of Keccak[r=1088,c=512] is used, does this provide security up to $2^{256}$ operations against quantum attackers using Grover's algorithm, or is security limited to half of the preimage strength, that is, only $2^{128}$ operations?

Unless Keccak has structural weaknesses that I am not aware of, the answer is surprisingly neither 128 nor 256!
Gilles Brassard, Peter Høyer, and Alain Tapp describe a sort of quantum birthday attack in their paper "Quantum Cryptanalysis of Hash and Claw-Free Functions" that effectively works by creating a table of size $\sqrt[3]{2^b}$ (versus the $\sqrt{2^b}$ for the classic birthday attack) and then utilizes Grover's algorithm to find a collision.
While the classic birthday attack thus requires ${\mathcal O}\left(\sqrt{2^b}\right)$ time and memory, the quantum birthday attack only requires ${\mathcal O}\left(\sqrt[3]{2^b}\right)$ time and memory.
This means that to provide a $b$ bit security level against quantum adversaries, a hash function must provide at least a $3b$ bit output.
In your case of 512-bit Keccak, your security level would be $170\frac{2}{3}$.


BEAST attack confusion I understand that BEAST is a CPA using javascript injected onto the browser's webpage. Apparently the thing that BEAST exploits is the fact that the IVs are predictable. What I'm confused about is why this is a problem when IVs are public anyway?

i'm looking at the first answer here:
How can Cipher Block Chaining (CBC) in SSL be attacked? Aren't $IV_1$ and $IV_2$ public in TLS 1.2 as well? So why isn't BEAST allowed there? Is it because, when the malicious javascript encrypts messages for you, it uses a new, random IV each time (but not in TLS 1.0 or lower)? But doesn't this mean that BEAST will only verify you guessed a message correctly with quite low probability, and you only get one attempt for each message (because the IV keeps changing, even though it's predictable)?

Aren't $IV_1$ and $IV_2$ public in TLS 1.2 as well?

$IV_1$ certainly is (as that's just the ciphertext block in front of the block we're attacking); however the IV that the TLS 1.2 sender will use for the next message ($IV_2$) is not.  In fact, the sender might not know it yet, as it might not have not picked it yet.

  But doesn't this mean that BEAST will only verify you guessed a message correctly with quite low probability?

Actually, if you guess all 128 bits of the block correctly, it will tell you.  If you say "what's the probability that we can guess all 128 bits?", well, we can make it significantly better than $2^{-128}$.  Another thing that BEAST does is it maneuvers the cookie under attack so that the plaintext block that we're trying to guess consists of:

KNOWNCOOKIENAM=?

where it knows the first 15 bytes of the plaintext; all it needs to guess is the last byte of the plaintext (which is the first byte of the cookie under attack).  Then, we need to check at worse 256 possibilities for that unknown byte (actually, less, because not all byte values are possible).  Yes, each attack requires a new message; however messages are pretty cheap.

Then, if it finds out that the first byte is X, then it remaneuvers the cookie, and then it attacks a block that consists of:

NOWNCOOKIENAM=X?

where ? is the second byte of the cookie.

That's the insight of BEAST; not only does TLS 1.0 allow us to verify guessed plaintext blocks with a CPA attack, but also by playing games with cookies, we can make plaintext blocks guessable.


Is this algorithm demonstrating "proof of work" Is this algorithm demonstrating proof of work? This is a algorithm where a "token" is combined with a time stamp and then a cryptographic hash is generated from the combination, next the objective is to find a token whose hash will collide with N digits of the timestamp+token hash.

This operation is computationally intensive and requires work by the client. The resulting token is time sensitive and expires. This could possibly be used to deter a denial of service attack. or other brute force attacks.

What is this algorithm called? Is something similar in use? is it a demonstration of "proof of work"?

Here is a demonstration of the algorithm in python.

import hashlib
import time
import os
import base64

# Number of digits that should collide
dificulty = 4
my_token = "nTDKIHbBus1O5cyebXQfFw=="
the_time = str(int(time.time()))
temporary_token = the_time+my_token

hash_stamp = hashlib.sha256(temporary_token).hexdigest()
collison_to_find = hash_stamp[:dificulty]
the_hash = ""

# Find a hash where the first N digits collide
while the_hash[:dificulty] != collison_to_find:
    # Generate a random token
    access_token = base64.b64encode(os.urandom(16))
    the_hash = hashlib.sha256(access_token).hexdigest()

print "temporary_token: ", temporary_token
print "access_token: ", access_token

This is the output

temorary_token:  1387573427nTDKIHbBus1O5cyebXQfFw==
access_token:  UwwSWGw14GK262rVPLPSOQ==

the first 4 digits of the token's hash will collide.

6095e4f38cd5f8e4581531fc29910614ecc54b8359ea8640bc5967d60ae1b043

609549c931eac0934d1fbb49d0dca7f2e4a621832251a8d786e60936a8761f41

In anticipation of this question being migrated.....

there is no need for the client-side to hammer /urandom. The odds of any subsequent random byte stream hashing to the same prefix are the same (actually worse) as the odds of any simple incrementing value.... i.e. you may as well change the urandom reference to just something++
A sophisticated client-side 'attacker' who knows the number of significant digit matches would be easily able to compute a rainbow-table of tokens that match the incoming digits. This ranbow-table will not take much longer to generate than the actual proof-of-work you require, and would be almost instantaneous to query.

All this process does is make legitimate access harder, and nefarious access fast.... ;-)


Does brute force attack use the program that created the ciphertext? I've read several articles about brute force cryptanalytic attacks, but none explicitly say what algorithm is being run for each attempt, nor what criteria is used to declare an attempt a success or a failure. If one is to try every possible every possible key value, what is one feeding those keys into? A brute force attack on a block of ciphertext implies that the cryptanalyst treats the cipher as a black box. Does the cryptanalyst have the block box and are they able to drive the black box?

Say, for example, that someone uses a GUI application that takes a file and a password as input and produces an encrypted file as output. The intended use would be for the receiver to use the encrypted file and the password to get the cleartext file as output. Is this same GUI application somehow driven by the cryptanalyst's brute force application to try every possible password? Most GUI programs are not fast enough to run billions of times in a reasonable period. Add to that the fact that most encryption is compute-intensive and can be made slower to prevent such an attack.

Brute force attacks are usually implemented in custom hardware or software for maximum performance.

Obviously the method of encryption must be determined before the attack can be implemented. The encryption method can be determined in several ways:

It's publicly available e.g. open source code, or open specification
It's secret and gets leaked by someone with access to insider information
It's reverse-engineered e.g by diassembling the application


Using scrypt to generate key + IV/nonce together Is there any security issue in using scrypt for Key + IV/nonce generation? In other words, can I safely use only a salt for scrypt and derive the nonce along with the key?

For example:

I have data I want to encrypt using password and AES in EAX mode. I want to use scrypt key derivation function to make a key from entered password. So I will need a salt for scrypt and a nonce for EAX. Both values need to be stored somewhere and it seems to be quite redundant. So instead I generate 384 bits of output using scrypt and use the first 256 bits as key and last 128 bits as nonce for EAX.

Yes, this is secure, even though scrypt uses PBKDF2 inside. PBKDF2 has the issue that it the work factor is required $n$ times where $n$ is the number hash outputs concatenated to create the final PBKDF2 output. That means that if you can check the validity of PBKDF2 using only the initial bits (in your case used for the key if the hash was SHA-256, for instance) that you have less of an advantage over an attacker. Basically your initial advantage is divided by $n$.

In scrypt however the final output calculated using a single iteration of PBKDF2, basically turning PBKDF2 into a KBKDF (key based key derivation function) where the calculation of the salt is used as the work factor. As the output size only relies on this single iteration the attacker would not gain an advantage.

That all said, it may make more sense to use a true KBKDF - such as HKDF-expand - to calculate two separate components (key and nonce) from the output of scrypt. In that case the OtherInfo part of the KBKDF (the derivation data) can be just an ASCII representation of the string "key" and "nonce".

So say that p = 1 and MFLen = hLen = dkLen = 32 bytes (output length of SHA-256), then perform:

m = scrypt(Passphrase, Salt, N)
k = HKDF-expand(m, "key", 32)
nonce = HKDF-expand(m, "nonce", 16)

Note that a KBKDF such as HKDF does not contain a work factor; i.e. all the time is still spend in the call to scrypt, not in the calls to HKDF.


Is it feasible to design a crypto scheme for centralised reporting of anonymized data? I would like to find out if it is feasible to design a cryptographic scheme that would allow several "reporting parties" to independently transfer information to the same centralised "authority", under the following constraints:

The "authority" should not receive the "original information" or be
able to infer the "original information", but it should receive
"derived information".
Without knowing the "original information", the "authority" should be
able to verify that "derived information" from two or more
"reporting parties" originates from the same "original information".
The number of "reporting parties" should be dynamic. Reporting parties
cannot work together and do not know if other "reporting parties" have
transmitted the same "original information" in a derived form.
BONUS: Two or more "reporting parties" should not be able to verify
that "derived information" from two or more "reporting
parties" originate from the same "original information".

The "original data" is arbitrarily short (e.g. significantly less than 40 bits).

I have a hunch that the first two constraints would somehow require hashing, random numbers and perhaps public-private keys, while the last constraint would definitely involve public-private keys... but have no idea as to how to design such a scheme or even if it would be feasible, given short data.

I can provide the exact use case if someone's interested; teaser: EU's MiFIR and Investor Privacy :)

Ok, here's what I got:

Someone selects two large primes $p$ and $q$ such that $n = 2pq + 1$ is prime, and $pq$ is large enough to make factorization infeasible; they select a value $g$ with order $p$ in $Z^*_n$ and a value $h$ with order $q$ in $Z^*_n$ (e.g. select a random $s$ in the range $[2, n-2]$ and set $g = s^{2q} \bmod n$ and $h = s^{2p} \bmod n$ and verify that neither $g$ nor $h$ are 1).  Someone (and it need not be the same someone) also selects a symmetric encryption key $k$.
The authority gets the values $q, n$ (and optionally the values $g, h, p$; the authority doesn't need them, but it wouldn't hurt security), the authority does not get $k$. Each "reporting party" gets the values $g, h, n, k$.
For a reporting party to convert original information $i$ into derived information, he first deterministically encrypts $i$ with the key $k$ (forming $E_k(i)$), selects a random value $r$, and computes $d = g^{E_k(i)}h^r \bmod n$, which is the derived information, which he can send to the authority.
For the authority to compare two derived information $d_1, d_2$ to see if they correspond to the same original one, he computes $(d_1 d_2^{-1})^q \bmod n$, if that is 1, then the original information is the same.

This works because $d_1 = g^{E_k(i_1)}h^{r_1}$ and $d_2 = g^{E_k(i_2)}h^{r_2}$, hence $(d_1 d_2^{-1})^q = (g^{E_k(i_1)}h^{r_1} \cdot g^{-E_k(i_2)}h^{-r_2})^q = (g^q)^{E_k(i_1) - E_k(i_2)}$, which is 1 if $E_k(i_1) = E_k(i_2)$, that is, if $i_1 = i_2$

As for your requirements:

1) The authority does not directly receive original information

2) The authority can compare two different derived information; it cannot otherwise reconstruct the original information; that is because of the symmetric key $k$; given $g^{E_k(i)}$, the attacker might be able to recover $E_k(i)$ (actually, he couldn't, however if the $E$ function was public without a secret $k$, he could, given the short range of possible $i$ values), however because he doesn't know $k$, that's as far as he could go.

3) Reporting parties are dynamic; all reporting parties are given the same information, and so adding more is not an issue; they cannot determine if other parties have contributed the same information; because they don't know the orders of $g$ and $h$, they cannot determine this.

4) Two or more parties cannot collaborate to subvert the system; because all reporting parties get the same information, two parties don't have any more power than one.

Now, a reporting party and the authority could collaborate to recover another reporting party's original information; this is actually inherent in the problem, and so is not an issue (at least as far as I'm concerned; you may consider it a deal-breaker, in which case you need to rethink the problem).  You could make it somewhat more difficult by replacing an invertible encryption function $E$ with a keyed hash $H$ (and assume that two different inputs just don't collide); however given the small range of the original information, it won't help that much...


Galois Field ($2^{16}$) for encryption in place of $GF(2^8)$ in AES AES algorithm is using $GF(2^8)$ Galois Field. What if we use $GF(2^{16})$ in place of $GF(2^8)$? Will this improve the algorithm or not?

The result would not be AES, but Rijndael  a generalization of Rijndael. The Rijndael originally was proposed with 1 block size (128 bits) and 5 key sizes (from 128 to 256 is jumps of 32 bits). In the standardization to become AES, only 3 were selected (jumps of 64 bits).

What makes block size to be 128? Each of the internal operations does its contribution. The wordsize is 8 bits (That's why the Galois Field has this size), and there are 4 columns and 4 rows. That makes $4*4*8 = 128$. The key sizes difference comes from the number of columns. Each extra column, as it has 4 rows, adds 32 bits. The AES adds 2 columns for each increment.

It is possible to play with this parameters, but you'll have to study individually to each of the Rijndael's operations what this change mean. Imho, the Pseudo Random generator (PRG) of the key expansion, I think will still be, at least, as valid as it is. The subBytes operation would experiment a size explosion that may affect the performance. Perhaps shiftRows and mixColumns would be the less affected. And don't forget how many rounds would be a good number.

As a summary, would this improve the algorithm? It can, if it comes with the appropriate adjustment of the other parameters. But then, if you implement it, you'll be away of the standard.


Security proof for CBC as a prefix-free PRF I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-free adversaries (see Section 6.4.1).

The methodology of the proof is to replace the PRF $E_K: \mathcal{X} \rightarrow \mathcal{X}$ with a function $f:\mathcal{X} \rightarrow \mathcal{X} $, that is chosen uniformly from random from set of all functions $f \stackrel{\$}{\leftarrow} \text{Funs}_{x,x}$:

The crux is then to calculate an adversary's ability to distinguish this $\text{CBC-}f$ construction from a random choice out of $\text{Funs}_{mx,x}$ (the set of all functions $\mathcal{X}^{\leq m_\text{max}}\rightarrow \mathcal{X}$ with $1\leq m \leq m_\text{max} $). For this, a rooted tree is used, where each query represents a path in this tree. The goal is to find the probability, that two inputs for $f$ collide (CBC chain value $\oplus$ some $X_i$ collides with some other CBC chain value $\oplus$ some $X_j$). This is where the prefix-freeness comes into play, because it ensures, that the message blocks are statistically independent from the CBC chain values and hence two inputs for $f$ collide with probability $1/|\mathcal{X}|$.

Last but not least my question: Why do we have to consider internal collisions too? Why is it not sufficient to only consider collisions on the last $f$ invocation for every query? How can a prefix-free adversary know, if there was an internal collision, when he only sees $Y$?

The answer is in the last sentence of the proof: "Once we have established that there are no collisions of these types, it will follow that all values associated with non-root nodes are random and independent, and this holds in particular for the values associated with the leaves, which represent the outputs of FCBC seen by the adversary."

To explain: we are only interested in the leaves which is the last invocation. However, the way to prove it is by proving it for all invocations. This seems quite natural because once there is an internal collision, the question of whether or not this leads to a final collision depends on the query contents, and this is unknown.


salt usage for hashed password storage - design consideration This is part of my academic assignment and hence to ensure no one feels i'm asking for the answer. I've given my opinion.

Hashing is mathematical one way function that takes arbitrary length data and converts it to a fixed length output. Important thing is exactly similar text (data) when hashed with same algorithm (MD or SHA  or any other) will always give same output. This brings an important challenge when storing sensitive data using hashing such as passwords - because same passwords when hashed and stored
using same algorithm will generate same hash. Hence salting is recommended to counter “rainbow tables” which is the brute force for hashing.

There is one more attack to keep in mind which is the birthday paradox but because we’re referring to password / passphrase as compared to a lengthy data-set / document hence birthday paradox is out of the question and so are collisions (questions assumes a strong hashing algorithm).

Here is the question:

  You are asked to implement the password storage for a system in which users are authenticated using password logins. You have to implement the storage without using a random number generator, and therefore cannot implement exactly the same salted storage as described in the lectures. There are at least three alternative ways to implement the table:

1. Method S1: use the constant “SA” as the salt for each entry in the table.

Constant salt is the weak link. One may argue that length of the salt is also a security weakness. But the fact that SALT is constant throughout the table.
It will lead to frequency analysis – password: 123456 with salt SA will always give same output across the table.
So I wouldn’t use it.

2. Method S2: for each entry, use the hash of the first two characters of the password as the salt.

password: 123456 will be hashed as hash (salt(password)) = hash(12(123456))

This is more secure from the perspective that SALT isn't constant. (as option 1)
However, password: 123456 with salt (12) as per the rule, will lead to same hash.
This will lead to frequency analysis as similar passwords in the DB will always be stored as same hash.

3. Method S3: use the number 0 as the salt for the first entry, and define the salt of each other entry as the hash of the previous entry.

Thus, the salt is 0 for the first entry, hash(0) for the second entry, hash(hash(0)) for the third entry, etc.

This is what I assess to be same as block cipher in CBC mode.
On the looks of it 0 may seem as a weak "SALT" but it acts as an IV here.
Similar passwords will never be as similar hashes. Hence frequency analysis is difficult.
It also makes it difficult to rainbow table (brute force) an entry individually and you will need entire table to get the plaintext as opposed to other designs wherein once you know the logic you can get plaintext passwords in the table.

- I would use this design. As question expects me to design security and not integrity of the data. CDC is prone to integrity failure as if one entry gets corrupt all subsequent entries will be corrupt.

Kindly give me your thoughts.

The main purpose of a Salt is for identical passwords to be hashed differently. Options 1 and 2 fail at this, they modify the hash function slightly but in the end do not add a Salt in any meaningful sense.
Rainbow tables still work, naive identification of identical passwords work, brute forcing all password simultaneously work.

Options 1 and 2 add no security over unsalted passwords, except perhaps a negligible slowdown in hash computation.

Option 3 provides real security, it prevents all 3 attack methods I mentioned earlier. If the Salt is saved with the password it would not be fragile, and corruption won't propagate. Nor would deleting an entry be an issue.

Essentially the basic premise of the problem lacking a random number generator is problematic when you have both storage and hash. If you have a hash function, building a good PRNG is trivial. An external entropy source is nice, but hardly required, even hashing the numbers 1,2,3,... would be reasonable for the purpose of producing salts(far better than options 1 or 2) despite predictability.

Clearly option 3.


Given a hash function how to find all/some inputs that hash to 0? Say I have a simple hash function where $x$ is a sequence of integers:

$$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$

where $a_1,a_2,a_3,...,a_n$ is the coefficient known.

n can be any number less than 256.

How to find 2 different inputs that hashes to 0 in particular?

I guess I understand how to make them hash to some random hash, but hash to a particular value, 0, seems like I need to solve linear equation?

and the complexity would be exponential in terms of the size of the ouput sequence?

Select $x=(x_1,...,x_{n-1})$ at random and then compute:

  $$x_n=({a_n}^{-1}\cdot(0-\sum_{i=1}^{n-1}a_i\cdot x_i)) \bmod N$$

Now, select $x'=(x_1',...,x_{n-2}',x_n')$ at random and then compute:

  $$x_{n-1}'=({a_{n-1}}^{-1}\cdot(0-a_n\cdot x_n'-\sum_{i=1}^{n-2}a_i\cdot x_i')) \bmod N$$

Now we have  $h(x)=h(x')=0$.

Note that this question was a special case ($k=0$) of your question at here


Zero-knowledge proof for Paillier parameters For RSA one can give a non-interactive zero-knowledge proof that RSA with parameters $(e,N)$ form a permutation and a proof of knowledge of the associated RSA secret key. For example, such a proof can be given using Poupard and Stern. I was wondering whether there exists a similar proof for Paillier. In a sense that to prove that the parameters are valid, and that one posses the associated Paillier secret key. Any ideas?

The Poupard-Stern protocol proves knowledge of the factorization. Knowing the secret key in the Paillier encryption scheme is equivalent to knowing the factorization, hence the exact same protocol can be used to prove knowledge of the Paillier secret key.

The second part of your question, proving that the parameter $N$ is well-formed, is much, much harder. It has been studied, for example in this paper, but remains quite inefficient, since one must prove that committed numbers are prime, which is done by demonstrating in zero-knowledge that they pass all steps of a probabilistic primality test (each such step involving exponentiations, hence each such proof requires proving exponential relations between committed value, which is again relatively inefficient).


MPC protocols in plain/CRS/PKI models I have seen that in MPC multiple models in different dimensions can be envisioned, like asynchronous vs synchronous networks, access to broadcast channels, and so on. However, a particularly interesting dimension is whether point-wise private and authenticated channels are available. In this direction, I have seen papers using the terms plain model, CRS model, or PKI model. I would like to understand what these models actually mean.
My concrete questions are the following:

I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).
I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.
If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?

I understand that the CRS model refers to a setting where a common reference string is provided to all parties. How can this help in computation? (any pointer to a concrete protocol that uses such setup would be welcome).

One typical approach is that the parties will treat the CRS as the public key of an encryption scheme, and encrypt their inputs under this key. They can prove things about this ciphertext in zero-knowledge for the rest of the protocol. This overall approach is useful because the simulator can generate the CRS to be a public key for which it knows the corresponding secret key, and therefore decrypt the parties' encryptions of their inputs. An example of this approach is in Canetti et al.

Beyond this, CRS is a fundamental part of the syntax for non-interactive ZK (NIZK). If the simulator generates the CRS with a trapdoor, they can generate proofs of false statements. But without the trapdoor, only proofs of true statements can be generated.

Another cute and totally different approach for a CRS is from Peikert et al. They construct oblivious transfer protocols in the CRS model. The CRS can be of two different flavors. If the CRS is of one flavor (think of a Diffie-Hellman triple $g^a, g^b, g^{ab}$) then the protocol can be proven information-theoretically secure against the receiver. If the CRS is of the other flavor (think of a random triple $g^a, g^b, g^c$) then the protocol can be proven information-theoretically secure against the sender. The fact that the two CRS flavors are indistinguishable means that the protocol actually gives (computational) security against both parties.

  I assume that the plain model is just the lack of any setup like a CRS. Does this mean that not even secure channels are assumed? I can't think of a protocol for more than 2 parties that works in this setting. Again, pointers would be welcome.

If you have authentic channels, then you can get secure channels using standard public-key encryption. So it is standard to just assume secure point-to-point channels. The bigger challenges are: (1) how to get broadcast from point-to-point channels; (2) what happens when you don't assume even authentic channels?

(1) is relatively standard. There is very little work on (2), but one paper I know of is Barak et al. Basically, without authentication it is inevitable that the adversary can partition the honest parties into disjoint and isolated groups, that each perform their own separate computation.

  If a public-key infrastructure (PKI) is assumed, what is it used for? Establishing secure channels?

You can bootstrap privacy from nothing (using key agreement), but you can't bootstrap authenticity from nothing. PKI is the root of trust for authenticity.


What are the coordinates of a generator point? I'm browsing through Curve25519 code, the generator point of it is $G=9$.

I would like to know how can I get $x$ and $y$ coordinates of this generator point. Is there any standard way of representing x and y as a single scalar value apart from $x$ over $z$ notation?

Elliptic curves live on a plane, each point having two coordinates. However, all points on a curve must fulfill the curve equation, which allows recomputing (most of) one coordinate from the other.

Let's see what it does for Curve25519. I am using notations from RFC 7748, as explained in sections 3 and 4.1. The two coordinates are then called $u$ and $v$, and the curve equation is:
$$ v^2 = u^3 + Au^2 + u $$
for constant $A = 486662$. Everything is computed modulo $p = 2^{255}-19$.

The generator point has coordinate $u_P = 9$. From the equation, we know that its other coordinate $v_P$ is then such that:
$$ v_P^2 = u_P^3 + Au_P^2 + u_P = 39420360 $$
Modulo $p$, that value has exactly two square roots, which can be computed with the Tonelli-Shanks algorithm; the values are:

v1 = 147816194475895447910205935684099868872 \
     64606134616475288964881837755586237401

v2 = 431144251710685529207648989359339670393 \
     70386198203806730763910166200978582548

Thus, when you say "$u = 9$", you narrow the choice down to exactly two points, $(9, v_1)$ and $(9, v_2)$. Conventionally, the first one is the actual generator.

As a further twist: it so happens that which of these two points you choose as generator does not matter, at least for the intended usage of that curve, i.e. to support Diffie-Hellman. Indeed, the two points $P_1 = (9,v_1)$ and $P_2 = (9,v_2)$ are such that $P_1 = -P_2$ (they have the same $u$ coordinate, and opposite $v$ coordinates). When doing Diffie-Hellman, the involves parties do the following:

Charles chooses a random secret $c$ and sends point $cP$.
Denise chooses a random secret $d$ and sends point $dP$.
Both compute $c(dP) = d(cP) = cdP$.
The shared secret is, conventionally, the $u$ coordinate of the latter point $cdP$.

Now, if Charles chooses $P_1$ but Denise works with $P_2$ has generator, Charles computes point $cdP_2$, while Denise makes $cdP_1$. But since $P_1 = -P_2$, we have $cdP_1 = -cdP_2$, and both points $cdP_1$ and $cdP_2$ have the same $u$ coordinate. Charles and Denise then end up with the same shared secret. Therefore, the exact choice between $P_1$ and $P_2$ does not matter.

This is the reason why the Montgomery ladder algorithm does not actually bother with the $v$ coordinate. All computations are done using $u$ only. Conceptually, when you do things with $u$, you are doing things with two points $(u,v)$ and $(u,-v)$ which are somehow mirror of each other. Since you keep only the $u$ coordinate at the end, the $v$ coordinate can remain implicit throughout.


Are there any zero knowledge protocols which do not rely on a Group? To me (new), it seems that a lot of cryptography relies on group theory.

Are there any zero knowledge protocols which do not rely on a group?

Are there any zero knowledge protocols which do not rely on a group?

It depends on your definition of "relying on a group". If you mean "doesn't rely on a group-based assumption like DDH, CDH or DLog or variants thereof", then yes. If you mean "doesn't use a group at some point" then no, because such a protocol would be unimplementable because the most basic operations of a processor and the most commonly used ones in cryptography like XOR and addition form groups.

Assuming the former case the detailed answer is that in theory zero-knowledge proofs only rely on the existence of One-Way-Functions - which can be heuristically instantiated e.g. with appropriate modes of AES. If you want to read the details of this, the relevant paper is "Everything Provable is provable in Zero-Knowledge" from CRYPTO '88.

The core idea of this is though that you take a protocol from IP and transform it so that the verifier only sends randomness (Arthur-Merlin-Protocol). Then the prover commits to the correct responses for that specific randomness input (which requires OWFs) and this is iterated until all specified prover messages are through. Then the prover performs an NP zero knowledge proof that if the verifier were to see the openings to the commitments along with the generated randomness, they would accept the interaction. This works using the actual prover responses as witnesses and exploiting the final verification being a deterministic polynomial time function.

The NP-ZK proof itself is a proof that you know a solution to the graph 3-coloring problem (which is NP-complete and thus you can reduce every problem in NP to it). The basic idea is that the prover has a 3-coloring of the graph and for each protocol run picks a new random permutation of the colors and commits to the coloring of all nodes. Then the verifier requests a random edge, the prover opens the commitment for the connected nodes and the commitments and the difference in color is verified. This is iterated until the verifier is satisfied.


Finding flaw in cryptographic protocol If you find a flaw or bug for example in Linux kernel you can create an issue in GitHub, or if you can solve it you can contribute.
How about Finding a flaw in cryptographic protocol?!

How can you report it or flag an issue?
If you can fix it, is it possible to contribute?

If you find a flaw or bug for example in Linux kernel you can create an issue in GitHub, or if you can solve it you can contribute.
  How about Finding a flaw in cryptographic protocol?!

A protocol is slightly different than a concrete implementation of a piece of software like the linux kernel on GitHub. It is closer to a specification that may be followed by many different implementations.

  How can you report it or flag an issue?
  If you can fix it, is it possible to contribute?

This depends on whether the protocol is something that is deployed and in use, e.g. TLS, or is a protocol that has merely been proposed academically.

If it is a theoretical academic protocol, you would create a paper discussing the attack or relevant shortcomings of the protocol and publish it as appropriate.

If the protocol in question is actually in use in the real world, then you would find who the authors of the protocol are and email them privately. Exactly who you email might vary depending on circumstances: Companies, individual implementors, and standards bodies might all be relevant. Try looking for white papers/RFCs/working groups/etc to locate the appropriate people to contact.

Be sure to include the email:

A thorough description of exactly what the problem is
Who is affected
How serious the problem is
How long the problem has been present
An implementation of the attack (a.k.a proof of concept)
Recommendations for how to fix the problem

Vulnerability reporting and disclosure can have multiple, orthogonal approaches and vendor responses may vary. If it is a widely used protocol like TLS your approach and response may very well be different from some random individuals project on GitHub.

Oh, and apparently it's trendy to create a branding campaign for the vulnerability, including a name, logo, and website. Whether or not this is a good practice is debated.


Backdoorable hash function in password database I want to use a (preferably established) hash function that is backdoorable in a password database. I want to do so because I need password escrow (being able to get the cleartext back. I want to generate some form of a private/public keypair on a secure server (airgapped, physical security). I then want to send the public key to the authentication server, and use a hashing algorithm that is reversible (I know that you can't normally reverse hashes) if you know the private key. If I ever need to read the passwords in the database, I copy the passwords and decrypt them with my private key.

The disadvantages are obvious: single point of failure, and in case of a non-established function, maybe a backdoor in my backdoor. (Oh, the irony)

What hash function should I use? Are there any established hash functions that will do this?

You can simply handle password verification on login and escrow independently:

Store a salted password hash (e.g. bcrypt) together with its salt. You can use this to verify logins, just like what you'd use if you had no escrow.
Also store the password encrypted with asymmetric encryption (e.g. RSA-OAEP, ECIES).

Since these are randomized, they are not vulnerable to attacks where the attacker guesses a password and checks if the encryption matches the ciphertext.

You might need to add some padding, to avoid leaking the length of the password.

The Makwa password hash has a built-in backdoor, but since this problem can be solved generically, I don't consider that a good reason for using Makwa over another hash.