Shamir's Secret Share Over the Reals What about using Shamir's secret share over the real numbers leaks information? I know there is a problem with random number generation, and someone suggested it leaks the parity of the polynomial, but I can't see very many other problems.

It's simply not secure.  Sure, it "works", in the sense that you can generate shares and reconstruct the secret from a sufficient number of them, but the essential security property of Shamir's secret sharing — namely, that knowing less than the required threshold number of shares reveals no information about the secret — does not hold.

Since it's easier to understand why this is the case if you actually see it happen, let me give an example.  To keep the example simple, let's assume that you're sharing the secret $S \in \mathbb R$ among two people, and want to require both of those two shares to reconstruct it.

So, since the reconstruction threshold is two, you need to choose one random number $a_1 \in \mathbb R$ and evaluate the polynomial $p(x) = S + r x$ at two non-zero points $x_1, x_2 \in \mathbb R \setminus \{0\}$.  The shares are then $y_1 = p(x_1) = S + rx_1$ and $y_2 = p(x_2) = S + rx_2$, and the secret can be reconstructed from them by linearly interpolating between the points $(x_1,y_1)$ and $(x_2,y_2)$ and taking the constant term of the resulting interpolation polynomial.

Now, so far so good.  But let's say that I know $y_1$ but not $y_2$.  Then, if I guess a value for the secret $S$, I can calculate the unique random value $r = (y_1-S)/x_1$ that gives me the share $y_1$, assuming that $S$ has the value I guessed.

Now, let's say (again for simplicity) that I'm sure that either $S = S_1$ or $S = S_2$ for some specific values $S_1$ and $S_2$.  Thus, I know that $r$ equals either $r_1 = (y_1-S_1)/x_1$ or $r_2 = (y_1-S_2)/x_1$.

Furthermore, let's say that, a priori, I believe that $S = S_1$ with probability $\mathrm{Pr}[S = S_1] = p_0$, and thus $S = S_2$ with probability $1-p_0$.
Now, using Bayes' rule, I can calculate the conditional probability $p^*$ that $S = S_1$ given that I have the share $y_1$ as:

$$\begin{aligned}
p^*
&= \mathrm{Pr}[S = S_1 \mid y_1]
= \frac{\mathrm{Pr}[y_1 \mid S = S_1]}{\mathrm{Pr}[y_1]} \mathrm{Pr}[S = S_1] \\
&= \frac{\mathrm{Pr}[r = r_1]}{\mathrm{Pr}[y_1]} p_0
= \frac{\pi(r_1)}{\mathrm{Pr}[y_1]} p_0\\
\end{aligned}$$

where $\pi(r)$ denotes the probability that you picked the random number $r$, and the denominator $\mathrm{Pr}[y_1] =$ $\pi(r_1)\, p_0 +$ $\pi(r_2)\, (1-p_0)$ is just a normalization constant that ensures that the conditional probabilities $\mathrm{Pr}[S = S_1 \mid y_1]$ and $\mathrm{Pr}[S = S_2 \mid y_1]$ sum to one.

Now, in general, $p^* = p_0$ if and only if the probability distribution $\pi$ is uniform, i.e. if every random number $r$ is equally likely to be picked.  In this case, knowing $y_1$ gives me no additional information about $S$.  When Shamir's secret sharing is implemented over a finite field, this is (or should be, if the implementation is correct) the case.

Conversely, if the probability distribution $\pi$ is not uniform (i.e. if some values of $r$ are more likely to be picked than others), then I can learn some information about $S$ just by knowing my own share $y_1$.  In particular, if $\pi$ is not uniform, then there will always be some pairs of possible secrets $S_1$ and $S_2$ such that $\pi(r_1) \ne \pi(r_2)$, and so $p^* \ne p_0$.

OK, you say, so just make $\pi$ uniform, then.  The problem, however, is that there is no uniform distribution over the real numbers, so any choice of random numbers necessarily leaks some information about the secret.

That issue — the need to pick uniform random numbers over the field we're working in — is the real reason why Shamir's secret sharing requires a finite field.


Key space size when either of two public keys are valid for authentication? If for authentication a user can own either A OR B public key instead of just one specific key is that equivalent to halving the key space. i.e. it it theoretically twice as easy to brute force and only equivalent to a 128 bit key?

Yes, having two valid keys in effect halves the size of the keyspace — from 2256 to 2255 possible keys per each valid one.

Not to 2128 keys, which is what a 128-bit keylength would get you.

Remember that the number of possible keys grows exponentially with the number of bits per key.  (Adding one bit doubles the size of the keyspace, since the added bit has two possible values: 0 or 1.)
A 256-bit keyspace has 2256 possible keys, which is a huge number.  Even if you had literally billions of valid keys instead of just one, it wouldn't make finding one of them by brute force any less impossible.


Zero Knowledge auth schemes with weak secret In Zero Knowledge auth schemes the public DH factor of each peer is encrypted with a potentially weak pre-shared secret and the resulting ciphertexts are exchanged over an insecure channel. Why is no attack on the weak secret possible?

I mean the messages can be sniffed and with an offline dictionary attack or simply bruteforce it should be possible to reveal the secret.

I believe that you are talking about one specific version of EKE, which is one of several known Password authenticated key agreement methods (which is the general category of methods that do a key agreement with the property that someone listening into the exchange can't learn anything, and an attacker that poses as one of the two sides can learn no more from a single exchange than whether a specific password was correct).

Now, with that background, here is the answer to your question.  With DH-based EKE, yes, both sides exchange their $E_k( g^x )$ and $E_k( g^y)$ values, and yes, the attacker can decrypt both values with a potential password, giving $g^x$ and $g^y$ if his guess is correct, and $D_{k'}(E_k(g^x))$ and $D_{k'}(E_k(g^y))$ if his guess is incorrect.  However, EKE uses a special encryption method such that $D_{k'}(E_k(g^x))$ and $D_{k'}(E_k(g^y))$ are also valid public values; possibly $g^z$ and $g^w$, for some $z$ and $w$.  This prevents the attacker from learning anything; he cannot test if a specific $g^x$ and $g^y$ generates the correct shared secret (because the DH problem is hard), and checking if they are valid public value tells him nothing (because they're all valid).  So, while the attacker can make a list of potential decryptions, there's nothing that distinguishes the correct one from all the wrong ones.


Can the person who decrypts a homomorphically encrypted value know what operations were run? I'm looking at the SEAL library but I'm trying to figure out what happens in a certain use case.

For example:

Alice encrypts the number 123456 homomorphically and sends it to Bob.
Bob adds 25 and does 3 left rotations on the value. He then sends it back.
Alice decrypts the value and gets 481123.

Following Step (3), is there a way for Alice to find out what operations Bob ran besides just guessing?

Maybe I'm not just confused about how the noise thing works.

No, not with SEAL at least. The noise is basically a measure of how much uncertainty there is after the operations are performed. Past a certain point there is simply too much and the decryption may be affected by it (the noise does not "round off" correctly), after which decryption may result in incorrect values. Because of this the "noise budget" is used in the library (invariant_noise_budget). Your results can safely be decrypted as long as the noise budget is positive.

It would probably be possible to gather some information about which types and how many operations (for some operations) occurred by analyzing the noise. Certain operations (rotation for example) do not consume the noise budget and would therefore be undetectable by a noise-analysis attack that depends on the amount of noise. Assuming SEAL does not have any huge flaws in it there shouldn't be any attacks that will let an attacker list out exactly which operations occurred.


Why is only one oracle + challenge-response phase sufficient for IND-CPA security? The CRYPTUTOR wiki from UIUC uses the following definition of the IND-CPA game:

  We (privately) choose a key K according to the key generation
  algorithm: K $\gets \mathsf{KeyGen}$.
  We (privately) choose a random bit b $\gets \{0,1\}$.
  Repeatedly do:

  A is allowed (any number of times) to query an oracle that computes the functionality $\mathsf{Enc}_K$.
  Challenge: A outputs two messages, $m_0\, $and $m_1\,$.
  Response: We give A the ciphertext $\mathsf{Enc}_K(m_b)$

  A outputs $b'\,$ (i.e, a guess for our b).

  We say that the advantage of A in this experiment is $\Pr[ b = b' ] - 1/2$.

Later in the Modifications section it is stated as follows:

  Using an application of a hybrid argument, it can be shown that only one "challenge-response" phase is necessary. It does not affect the definition of security to remove the repeating loop (line 3).

I am not able to come up with any hybrid arguments to prove this.

EDIT: I realised that I assumed an IND-CPA game where the adversary has pre- and post-challenge access to the encryption oracle and not only pre-challenge access. I'll edit my answer soon.

I'll give the idea and leave the concrete analysis to you. You want to show that single-query IND-CPA implies multi-query IND-CPA or in other words if there is an adversary against multi-query IND-CPA, then there is also one against single-query IND-CPA.

Assume that you have an adversary $\cal A$ that that wins the multi-query IND-CPA experiment with $q$ challenge queries.

For our argumentation below, we construct an adversary $\cal B$ that uses only one challenge query where $\cal B$ interacts with an single-query IND-CPA challenger $\cal C$ of a symmetric encryption scheme.

The idea is that $\cal B$ chooses an index $i\in [q]$ and proceeds as follows:

Let $\cal B$ initialize the single-query IND-CPA game with a challenger $\cal C$ and:

For all challenge query $(m_0^j,m_1^j)$ with $j<i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_0^j$ and returns the obtained ciphertext to $\cal A$
For the challenge query $(m_0^j,m_1^j)$ with $j=i$, $\cal B$ queries $(m_0^j,m_1^j)$ to the challenge oracle of $\cal C$ and returns whatever $\cal C$ returns
For any challenge query $(m_0^j,m_1^j)$ with $j>i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_1^j$ and returns the obtained ciphertext to $\cal A$

If $\cal A$ outputs its guess $b'$ to $\cal B$, then $\cal B$ forwards $b'$ to $\cal C$

Now, define the $j$'th hybrid $H_j$ to be the version of the multi-query IND-CPA game where the first $j$'th queries are with respect to $m_0^j$ (and all remaining with respect to $m_1^j$). It is clear that in $H_0$ all queries are with respect to $m_1$ and in $H_q$ all queries are with respect to $m_0$. Consequently, a distinguisher between these two extreme hybrids $H_0$ and $H_q$ clearly yields a mutli-query IND-CPA adversary.

If we now assume that there is such an multi-query IND-CPA adversary $\cal A'$ that has non-negligible advantage, then if we move from $H_0$ to $H_q$, there must be an $i, 0\leq i < q$ such that for the neighboring hybrids $H_i$ and $H_{i+1}$ it must hold that their distance must be non-negligible (as the number of queries $q$ is polynomially bounded). Now, you can argue that any distinguisher between two neighboring hybrids yields a distinguisher for the single-query IND-CPA game, by exactly using the adversary $\cal B$ defined above. Finally, you will get that the advantage for an adversary of winning the multi-query IND-CPA experiment is less or equal then $q$ times the advantage of an adversary winning the single-query IND-CPA experiment, i.e., any multi-query adversary with non-negligible advantage yields a single-query adversary with non-negligible advantage (which proves what you want to show).


Probability approximation of no collisions I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text.

The approximation is as follows:

$$P(\text{no collisions}) = \frac{e^{-t(t-1)}}{2 \cdot 2^n}$$

I know that t represents the number of elements but I am confused about the denominator. The text says that $n$ is the output width of $h()$. I don't really understand this. Does this mean that for lets say the Birthday Paradox, $n  = 365$? So the denominator would be $2 \cdot 2^{365}$?

For a hash function with a 128 bit output, n=128. Such a function has $2^{128}$ possible outputs.

For the birthday paradox you have 365 different outputs, i.e. $2^n = 365$ or $n = \log_2 {365} \approx 8.5$.

You'll also find alternative versions of this formula, which omit the 2^ part in the formula: $\frac{e^{-t(t-1)}}{2 \cdot N}$. In that case you'd use $N=365$ for the birthday paradox and $N=2^{128}$ for the 128 bit hash.

If $t$ is small compared to $N=2^n$, the formula can be approximated as:

$$1-\frac{t(t-1)}{2}\frac{1}{
N}=1-\frac{1+2+3+...+(t-1)}{N}=1-(\frac{1}{N}+\frac{2}{N}+\frac{3}{N}+...+\frac{t-1}{N})$$

Which is intuitive, since the first value has no chance of collision, the second can collide with 1 existing value with probability $\frac{1}{N}$, the third can collide with 2 existing values with probability $\frac{2}{N}$, etc.


Detect tampering of data I have the following problem:
There are $n$ users and each users fills in three data points per day, this are three integers between say $-10$ and $10$. I have access to the database and hence I am able to modify this data. However, I want to "sign" the data.

How can this be done in such a way that I am unable to change the data without that this can be detected? The users login, so I do have the md5 hash of their password, could I use this in any way to sign the data?

It should also not be possible preferably that I delete everything, change a couple of values and generate the "checks" again.

The threat: Let me make an analogy to what can be the threat (my case is more abstract). Say that people with a schizophrenia would give every day a number about "how psychotic" they are. On the basis of long-term data there could be made conclusions about "how severe" the case is. The users might claim that there has been messed with the data to make their case look more severe (say because of conflict of interest with pharmaceutical companies).

Yes.  Use append-only logs, or a cryptographic timestamping service.  These approaches are generally designed to solve the problem you mentioned, namely: detecting tampering with data or post-dating of old data.

See the following resources on this site and our sister site, Security.SE:

Techniques for ensuring verifiability of event log files
WORM media types
How are timestamps verified?
On-line cryptographically signed date/time?
Signature and Timestamp for Long Term Document Archival Question
Geographic equivilent of RFC 3161 (X.509 PKI Time-stamp Protocol)

They should cover this topic in great detail.  Enjoy!


Books about stream ciphers I am new to ciphers and for my assignment i have to implement a stream cipher algorithm without libraries (on my own). So my question is: Does anyone know about any GOOD books which have examples and explanation of implementation?

Probably all you need to know about RC4 (at your level) is on the Wikipedia page. There's even code. And then there are all the links to follow for more detail. And two books in Further Reading:-

Paul, Goutam; Subhamoy Maitra (2011). RC4 Stream Cipher and Its Variants. CRC Press. ISBN 9781439831359.
Schneier, Bruce (1995). "Chapter 17 – Other Stream Ciphers and Real Random-Sequence Generators". Applied Cryptography: Protocols, Algorithms, and Source Code in C (2nd ed.). Wiley. ISBN 978-0471117094.

Make sure you acknowledge the Security section on that page.


Estimating the probability of sucess of Pollard's p-1 I'm trying to estimate the probability that Pollard's p-1 factorization in its two-stages variant finds a factor of an RSA modulus product of $k$ random $b$-bit primes, as a function of the bounds $B_1$ and $B_2$ used.

That's about $1-(1-P)^k$, or about $k\,P$ for low $P$, where $P$ is the probability that a $b$-bit prime $p$ has $p-1$ with its largest prime factor less than $B_2$ and its second-largest prime factor less than $B_1$.
My (incorrect) idea was that we must have $P\ge\rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr)\rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr)$ where $\rho$ is Dickman's function [*], on the assumption that $p-1$ behaves like a random even integer, that the probability of the largest prime factor $q$ being less than $B_2$ is about $\rho\Bigl(\frac{b-1}{\log_2(B_2)}\Bigr)$; and then the conditional probability of the second-largest prime factor being less than $B_1$ is about $\rho\Bigl(\frac{\log_2(q)}{\log_2(B_1)}\Bigr)$, which is at least $\rho\Bigl(\frac{\log_2(B_2)}{\log_2(B_1)}\Bigr)$.

Problem is, my estimate is much larger than the one given by gmp-ecm with option -pm1 15e9 [#] which estimates its own probability of success as:

Using B1=15000000000, B2=19849281594647716 (..)
Probability of finding a factor of n digits (assuming one exists):
20      25      30      35      40      45      50      55      60      65
0.84    0.58    0.32    0.15    0.063   0.023   0.0078  0.0024  0.00068 0.00018

For $n=65$ decimal digits, that is $b=216$, I get $P$ at least $0.0028$, which is over 15 times more than ECM's estimate $0.00018$.

What's the cause of that discrepancy?

[*] Dickman's function $\rho$ is defined for $u\in\mathbb R^+$ by
$$\begin{cases}
\rho(u)=1 & \text{if }0\le u\le1\\
\rho(u)=1-\int_1^u\rho(t-1)/t\;dt& \text{if }u>1
\end{cases}$$
As $B$ grows, the probability that a random integer about $B^u$ has all its prime factors less than $B$ converges to $\rho(u)$. Sometime it is considered Dickman's function $F$ defined by $F(\alpha)=\rho(1/\alpha)$. In particular, Richard P. Brent's Some Integer Factorization Algorithms using Elliptic Curves uses $\rho$ for that $F$.

[#] gmp-ecm with option -pm1 implements Peter L. Montgomery and Alexander Kruppa's Improved Stage 2 to P±1 Factoring Algorithms, in proceedings of ANTS 2008. The first parameter is $B_1$. $B_2$ is chosen automatically if not specified as second parameter.

estimate the probability that Pollard's p-1 factorization in its two-stages variant finds a factor of an RSA modulus product of $k$ random $b$-bit primes, as a function of the bounds $B_1$ and $B_2$ used

TLDR: GMP-ECM is fine. Modify it for $b$ bits rather than n decimal digits, and use $k\;P$ where $P$ is the low probability shown.

The way GMP-ECM ecm -v -pm1 coumputes $P$ is described by Alexander Kruppa in section 5.3.3 of his Doctor's thesis, as
$$P=\hat\rho\biggl(\frac{\log(N_\text{eff})}{\log(B_1)},N_\text{eff}\biggr)+\sum_{B_1<q\le B_2\\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N_\text{eff}/q)}{\log(B_1)},N_\text{eff}/q\biggr)/q$$
where
$$\begin{align}\hat\rho(u,x)&=\rho(u)-\gamma\frac{\rho(u-1)}{\log(x)}\\
\gamma&=\lim_{n\to\infty}\biggl(-\log(n)+\sum_{i=1}^n\frac 1 n\biggr)
\approx0.5772156649\\
N_\text{eff}&=N\;e^{-\delta}\\
\delta&=\sum_{q\in\Bbb P}\frac{\log(q)}{(q-1)^2}\approx1.2269688057\\
N&=2^{b-0.5}\text{ is an approximation of the factor}
\end{align}$$

In this, $\displaystyle\hat\rho\biggl(\frac{\log(N)}{\log(B_1)},N\biggr)$ estimates the probability that a random integer near $N$ has all its primes factors at most $B_1$; $\displaystyle\sum_{B_1<q\le B_2\\\quad q\in\Bbb P}\hat\rho\biggl(\frac{\log(N/q)}{\log(B_1)},N/q\biggr)/q$ estimates the probability that a random integer near $N$ has all its primes factors except the largest at most $B_1$ and has that largest factor in $(B_1,B_2]$; and $\delta$ is a correction to account for the fact that a random prime $p$ near $N$ has $p-1$ divisible by small prime $q$ with probability $1/(q-1)$, rather than $1/q$ for a random integer near $N$.

Note: that answer is still missing how to compute the sum for large $B_2$. GMP-ECM uses some indirect method when $q>20000$, which is always for parameters of practical interest in factoring an RSA modulus. For this reason, I make the question a Community Wiki.

As an illustration: ecm -pm1 35e9 uses $B_1=35000000000$, $B_2=81866328103009612$, and a 256-bits random prime is found with $P\approx0.0000119$. A factor is found in a 3-factors RSA 768-bit modulus product of random 256-bit prime factors for about one in 28000 moduli. Testing a moduli costs about 3.5 hour using one core and 48GiB RAM. Most of the RAM is used <25% of that time, so that one 4-core CPU 64GiB machine can test at a rate over one modulus per hour. If an adversary is content with factoring any one in like a thirty thousand such RSA moduli, Polard's p-1 is a plausible strategy to pull a factor (with expected cost 1170 CPU×days), followed by GNFS to factor a 512-bit composite. This beats GNFS alone, and I believe ECM. This is a setup where it makes sense to generate primes in a way that defeats Polard's p-1 and probably Williams's p+1 too.

Thanks to Paul Zimmermann and Alexander Kruppa for their guidance.

  What's the cause of that discrepancy?

Main problem: the question's term $\displaystyle\frac{\log_2(B_2)}{\log_2(B_1)}$ is grossly too high. It was supposed to be a lower bound of the probability that the second-highest factor of a large random integer is less than $B_1$, knowing that the highest factor is less than $B_2$. That was baseless and wrong.


Diffie-Hellman what is the subgroup I am trying to understand the safety precautions regarding the variables used in Diffie-Hellman and I was refered to this post answer Does the generator size matter in Diffie-Hellman?.

  In more details: for DH, we use a subgroup of size q of the integers modulo p (a big prime) with the multiplication as group operation. q should be a prime of length at least 2n bits for a 2n security level (or, at least, q should have a prime divisor of at least 2n bits). Typical parameter sizes are 160 bits for q and 1024 bits for p, or 256 bits for q and 2048 bits for p. The generator g is an element of order q.

What is meant by for DH, we use a subgroup of size q of the integers modulo p I assume the group is the potential congruences of $\mod p$, but what is the subgroup. Since the generator should be a primitive root of p doesn't that mean that the group is $[1,p-1]$? This leads me to believe that $ q = p-1$. However this makes no sense when considering the following sentence q should be a prime of length at least 2n bits for a 2n security level (or, at least, q should have a prime divisor of at least 2n bits). I am not sure what the n variable symbolizes?

Since the generator should be a primitive root of p

Well, here's your misunderstanding; the generator $g$ needn't generate the entire group $\mathbb{Z}^*_p$; instead, it can generate a proper subgroup (and in most cases, we select such a subgroup).

Here's the issue, if $h$ is a factor of the size of the group generated by $g$, then given $g^x \bmod p$, we can compute $h \bmod n$ in $O(\sqrt h)$ time.  If $g$ generates the entire group, well, its size will be $p-1$, which always has a factor of 2 (assuming $p>2$), and so we'd be giving away $x \bmod 2$ for free.

In contrast, if the size of the subgroup is a large prime (which implies that it is not the entire group), then the above observation doesn't give the attacker any advantage; the only factors of the subgroup size are 1 (which doesn't tell the attacker anything) and the large subgroup size itself (which is too large to make $O(\sqrt{h})$ time feasible.


Cracking secret key of a MD5 hash? I have a MD5 hash which is obtained by hashing certain strings appended by a pipe character ( | ). (I know the values of these) A secret key is added as a suffix to this (I don't know the secret key). My question is, is it possible to crack the secret key if the resulting hash and the hash without the secret key is known?

Short answer: No.

Medium-size answer: only brute-force could give you the answer, and that would take as long as the secret part is safe (=long enought)

Long answer: (not so long because it's already said in many good answers at security.stackexchange and here, too. I'll post links later).

Salts are strings appended to another string (passwords) to avoid some leaks and attacks. The salt is know, it doesn't need to be kept secret.

When you say you have a MD5 hash of some know string + secret part, what you are really saying is that you have a hash, you know the salt, and you need to know the password. Knowing all those is not a big deal, it's how hasing salt + password is supposed to work.

So you really have the original problem on "how to know a password if I know the hash?". The special points of your question is that MD5 is used (and is somehow broken, for certain properties), MD5 is too fast to be calculated so many brute-forces attempts can be made per second, and you don't say / know about how many iterations were used.

In the end, you can do some brute-force attack, probably won't be able to use rainbow tables, can use GPUs to speed up the process, but will be doing the old and good brute-force.


What are the advantages of using OFB (Output Feedback Mode)? I have a problem with OFB mode, because I have heard that it is stronger than CFB.

I have a problem with OFB mode, because I have heard that it is stronger than CFB.

On the contrary I would say that CFB is stronger.

OFB means encrypting the IV again and again to produce the keystream. If you end up in a cycle, the keystream will start repeating itself. (This should not be a practical weakness, but why chance it?)

CFB is more like CBC, in that it uses the ciphertext as input to the cipher for the next block. This means it will not enter cycles unless e.g. encrypting a constant plaintext. CFB can also recover from IV reuse if the plaintext it different (which is an advantage even over CTR).

  What are the advantages of using OFB (Output Feedback Mode)?

One advantage OFB does have over CFB is that you can pregenerate the keystream, since it does not depend on the plaintext. However, as the other answer states, encryption with either algorithm is serial and cannot be parallelized. That makes CTR the best choice for performance, since it also allows keystream pregeneration.

Of course, in the real world you should just use an authenticated encryption mode (like GCM) unless you are certain you know what you are doing.


Why cryptsetup default KDF is PBKDF2 and not Argon2(id)? I plan to do a clean install of ArchLinux with Full Disk Encryption (with LUKS) but I'm not sure to understand the default KDF choice (PBKDF2+SHA-256).
I didn't manage to find any pieces of evidence that make PBKDF2 more recommendable than Argon2id. Can someone explain to me ?
In the cryptsetup FAQ, the maintainer says :

5.11 Some people say PBKDF2 is insecure?
There is some discussion that a hash-function should have a "large memory" property, i.e. that it should require a lot of memory to be computed. This serves to prevent attacks using special programmable circuits, like FPGAs, and attacks using graphics cards. PBKDF2 does not need a lot of memory and is vulnerable to these attacks. However, the publication usually referred in these discussions is not very convincing in proving that the presented hash really is "large memory" (that may change, email the FAQ maintainer when it does) and it is of limited usefulness anyways. Attackers that use clusters of normal PCs will not be affected at all by a "large memory" property. For example the US Secret Service is known to use the off-hour time of all the office PCs of the Treasury for password breaking. The Treasury has about 110'000 employees. Assuming every one has an office PC, that is significant computing power, all of it with plenty of memory for computing "large memory" hashes. Bot-net operators also have all the memory they want. The only protection against a resourceful attacker is a high-entropy passphrase, see items 5.9 and 5.10.

Is this point still valid? Can "memory-hard" KDF like Argon2id really "limit" the 2 examples above?
Even if the FAQ is still right, are there any downsides (security wise) of using Argon2id instead of PBKDF2?
PS : Not a native speaker. Sorry for possible language oddities.

The default version of LUKS simply does not support Argon2 because, unlike PBKDF2, it requires more parameters than the current header format is designed to store. The newer version, LUKS2, may not be default on your system, but it does support Argon2. This is just a matter of software support.

See also https://gitlab.com/cryptsetup/cryptsetup/blob/master/docs/on-disk-format-luks2.pdf


Can we run a probabilistic function on ciphertext with Functional Encryption (or Attribute Based Encryption)? In the definition of functional encryption ($FE$):

$FE.Setup(1^k)$ takes as input the security parameter $1^k$ and outputs a master public key $fmpk$ and a master secret key $fmsk$.

$FE.KeyGen(fmsk, f)$ takes as input the master secret key $fmsk$ and a function $f$ and outputs a key $sk_f$.

$FE.Enc(fmpk,x)$ takes as input the master public key $fmpk$ and an input $x$ and outputs a ciphertext $c$.

$FE.Dec(sk_f,c)$ takes as input a key $fsk_f$ and a ciphertext $c$ and outputs a value $f(x)$.

Suppose that Alice runs $FE.Setup(1^k)$ and $FE.KeyGen(fmsk, f)$ where $f$ is a probabilistic function. Then she sends $sk_f$ and $fmpk$ to Bob.

Bob runs $FE.Enc(fmk,x)$ and $FE.Dec(sk_f,c)$ to get $f(x)$.

Is this possible? I mean as $f$ is probabilistic, it has to access Bob's randomness pool.

Bob can provide a faked pool. How can one guarantee the privacy of $f$?

There are ways to prevent Bob from having complete control over the randomness pool.  You could use some form of verified randomness, where your function $f$ checks that the random string is signed before executing.  This would work using, for instance, the NIST randomness beacon.  You could also contain within $f$ a PRNG, so Bob does not need to provide all the randomness but only a seed (which could actually be signed and provided by Alice or another trusted party).  But in the end, there is no way to guarantee statefullness between function calls, so nothing stops Bob from providing the same randomness to $f$ every time.  This is a fundamental issue I believe.


Quoting the SSH protocol:

  "Note that the 'packet_length' field is also encrypted, and processing it requires special care when sending or receiving packets."

Generally ciphers process bytes from left to right. This means that the packet length can be available before the encryption is ended (or before all the information is received, for that matter).

This is a horrible protocol decision because it means you have to interleave between the packet decoding and decryption layer, and you will get the message length before it is authenticated. Still, it is practically doable.

There is probably one advantage: you can add more padding to avoid some side channel attacks that use the length of the send packages. However, this advantage is hard to use, because you'd now also have to mix the application and encryption code.

Note that the other sizes - such as MAC length - are determined by the protocol and protocol configuration during the handshake.


Proving correctness of a decryption of a homomorphically summed ciphertext? I would like to take some additively homomorphic cryptosystem - don't care much which one for now - and encrypt a series of numbers with it. I would then like to (in public) take these numbers, add them together, decrypt the sum and convince everyone that I did it correctly.

This may seem pointless because I myself encrypted those numbers to begin with, but I'm thinking about voting applications where in reality the party who encrypted the numbers is not the same as the party decrypting the sum, and the numbers being summed/decrypted are all on a public bulletin board.

I know voting is a well studied problem in the literature, but so far none of the papers I've read have been doing it in quite the same way I'm interested in, so I see this as a good opportunity to go exploring.

So far I understand that with a regular Paillier encryption, to prove a correct decryption you can just reveal the randomness, however this does not work if you have added together ciphertexts. Exponential ElGamal would probably work for my use case, but I'm not sure if it lets me do what I need either ... plus I'm uncertain how fast a normal computer can actually brute force discrete log in a message space of say a few hundred million possibilities. I know it's perfectly possible but there's a gap between "possible" and "fast enough to be usable" and I'm unclear how to calculate this out short of just implementing it myself and trying it empirically.

For exponential ElGamal this is quite easy if all singe ciphertexts are public (you mentioned they are on a public bulletin board). Lets call $(c_1,c_2)=(g^my^r,g^r)$ the ciphertext corresponding to the sum $m$ of all single encrypted messages after your homomorphic summing (with $y=g^x$ being the public key). The decrypting party simply provides a non-interactive proof of knowledge (signature of knowledge - $SoK$) of the private key $x$ (denoted $\alpha$ below), i.e.,: $$\pi \gets SoK\{(\alpha): c_1=g^mc_2^\alpha ~~\land~~y=c_2^\alpha \}$$
along with $m$ (this $SoK$ can be efficiently realised by converting the respective sigma-protocol to a non-interactive proof using Fiat-Shamir). Everybody can now check if homomorphically adding all ciphertexts yields $(c_1,c_2)$ and taking $(c_1,c_2)$ as well as $m$ and $y$ the proof $\pi$ verifies. If all this works out, then everybody will be convinced that the decrypting party behaves honest.

If you have a few million possibilities you can either use a pre-computed lookup table, brute force or by using some suitable, more sophisticated method to compute discrete logarithms, like Pollards lambda method (since you know where to search). Whats more suitable for you depends on your setting, i.e., how resource constrained are your entities, group setting, etc.

You may use a similar approach for any other additively homomorphic encryption scheme (such as Paillier).


Is BBS used for generation of keys for any modern cryptosystem? Is there any (current) cryptosystem or digital signature or cryptographic primitive that uses the BBS PRG in order to generate its secret keys?

I don't know of any implementations that use BBS.  I hope no important system is using BBS.  BBS is a poor choice for practical use.  The only benefit it has is that it comes with some security proofs -- but it turns out that those proofs are useless for all practical instantiations of BBS (for realistic parameter settings), so they're pretty much irrelevant in practice.  See Blum Blum Shub vs. AES-CTR or other CSPRNGs for details.


Is there any strong enough pen-and-paper or mind cipher? Some ciphers are talked about at “Is there a secure cryptosystem that can be performed mentally?”, but (at the time of writing) I don't see an answer.

Are they strong enough, or are non-computer ciphers more or less just a toy and one should abandon using them for practical purposes?

"Strong enough" is a broad term. Some things that you need to keep in mind are entropy size and cryptanalysis. "Strong ciphers" are ciphers that have shown to have enough entropy to withstand practical attacks over time from public scrutiny.

With that said, the Solitaire cipher has a keyspace of roughly 238 bits. By comparison, many SSL keys on the internet are 128 bit AES. Distributed.net is currently working on cracking a 72 bit key, via brute force, at a pace of about 300 billion keys per second, and they have well over 100 years before the keyspace is fully exhausted.

So, for the Solitaire cipher to not be taken seriously, it needs to show practical weaknesses outside of brute force searching. So far, the only weakness that has been demonstrated is that the output has a bias of 22.5:1 rather than 26:1 pure random output would have. This isn't severe enough to mount a practical attack.

As such, until other attacks are made known, to Solitaire cipher is a "strong" hand cipher, that doesn't have NSA influence, can be used without incriminating tools and is easy to learn and remember.


Hash function and indifferentiability What are the properties derived from the fact that a hash function is indifferentiable from a random oracle?

The concept of indistinguishability from random is one of the most important in cryptography. Not only for hash functions, but for most cryptographic primitives, if not all.

Generally speaking, its importance relies on the fact that something which is not indistinguishable from random might be leaking some private information. Thus an attack might be derived from such a distinguisher.
On the other hand, something that is indistinguishable from random surely is not leaking any private information.

Regarding the special case of hash functions, you must have in mind that many security proofs for cryptographic protocols assume the use of a random oracle during some step of the protocol. In practice, hash functions are used for this purpose. However, as you might know, hash functions are not exactly equivalent to random oracle. But if we can show that they are indistinguishable from each other, then the intended security proof would hold as if a random oracle was used.

Note: As e-sushi mentioned, I am pretty sure there are plenty of material on the web regarding this topic. Please, for the good of the community, make a research before asking here. (Y)


Would XDES be more secure than 3DES, where X is a number > 3? Would XDES be more secure than 3DES, where X is a number  > 3?
Like 10DES... If so why aren't we using it?

Would XDES be more secure than 3DES, where $X > 3$ ?

Yes. This answer about if 4DES / 5DES is possible illustrates it quite well.

It would however make more sense, if you really want to make it more secure, to have $n$-DES, where $n = 2k-1 \space | \space k \in \mathbb{N}$, or in simple terms: $n$-DES, where $n$ is an odd number.

This comes from the Meet-in-the-middle attack (MITM attack).

Example:

DES has a keylength of $2^{56}$. Double DES only has a keylength of $2^{57} (= 2 \times 2^{56})$. Only by using 3DES you start to really improve the security from single-DES: $2^{56} \times 2^{56} + 2^{56} \approx 2^{112}$.

  Why aren't we using XDES with large X?

Because of AES. It's not feasible to have MITM-attack on AES.

Using XDES instead of AES would have more drawbacks than benefits, especially from a computational view.


If I concatenate two colliding SHA-256 messages with the same prefix and suffix, will the resulting hash output still collide with each other? So let's say that there are two messages, $x_1$ and $x_2$, which hash to the same output. In other words, these two messages collide with each other:

$$\operatorname{SHA256}(x_1)=\operatorname{SHA256}(x_2)$$

Questions:

Now, let's say I append identical prefixes and/or suffixes to both $x_1$ and $x_2$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Now, will $\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ as well?
Considering another slightly different scenario here - a partial collision rather than a full collision.

Let's say $\operatorname{SHA256}(x_1)$ collides with $\operatorname{SHA256}(x_2)$ in the first 80 bits.

Now, if I add identical prefixes and suffixes to $x_1$ and $x_2$:

$$\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)\text{ and }\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$$

Will  $\operatorname{SHA256}(p\mathbin\|x_1\mathbin\|s)$ still collide with  $\operatorname{SHA256}(p\mathbin\|x_2\mathbin\|s)$ in the first 80 bits as well?

The Generic Collision attack

Finding a collision with the generic collision attack for SHA256 requires $2^{128}$ computations with %50 probability of success. This bound is given by the birthday attack. There is no attack on SHA256 better than a generic collision attack yet practical. Assume that you have luckily found one; $$\operatorname{SHA256}(x_1) = \operatorname{SHA256}(x_2)$$

The SHA256 padding

Let's remember the SHA256 padding that uses 512 block size with the message length added to the end with 64-bit. NIST 180-4 page 13

  Suppose that the length of the message, $M$, is $\ell$ bits. Append the bit $1$ to the end of the message, followed by $k$ zero bits, where $k$ is the smallest, non-negative solution to the equation $$ \ell - 1 - k \equiv 448 \pmod{512}.$$
  Then append the 64-bit block that is equal to the number $\ell$ expressed
  using a binary representation.

back to your questions;

  Now, will $\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)=\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ as well?

If $len(p)$ is a multiple of the 512 then the result of $\operatorname{SHA256} (p\mathbin\|x_1) = \operatorname{SHA256} (p\mathbin\|x_2)$ will be same, this is like an extension attack on $p$. Otherwise the you have $1/2^{256}$ probability to hit the collision with one try.

What about the suffix $s$. This is not like the length extension attack since we have to consider the padding of $x_1$ and $x_2$ in $\operatorname{SHA256}(x_1)$ and $\operatorname{SHA256}(x_2)$, repectively. If one choose $s$'s beginning as the padding of $x_1$ and $x_2$ then it can be extension attack as long as the $len(x_1) = len(x_2)$. Otherwise, the collision is random collision.

As a result; the combination $(p\mathbin\|x_i\mathbin\|s)$ requires so much condition about the $p,x_1,x_2,s$ to have the collision with $1/2^{256}$ probability to hit the collision with one try.

In short, NO.

  Will $\operatorname{SHA256} (p\mathbin\|x_1\mathbin\|s)$ still collide with  $\operatorname{SHA256} (p\mathbin\|x_2\mathbin\|s)$ in the first 80 bits as well?

No. Even you have the collision the value will be different.


Can one have an authentic, but repudiable, message without a previously shared secret? Bob wants to send a message to Alice, such that Alice can be sure that the message came from Bob, but can't prove it to anyone else.

If I understand right, this means that the same message could have possibly also been constructed by Alice, but not by Eve (who can observe, change, remove and inject messages).

The usual solution would be a MAC using a shared secret, but suppose there is no such shared secret (for example, as Bob and Alice didn't communicate before).

We can provide, however, a public-key infrastructure of some kind, so Alice and Bob know (or can obtain securely) each other's public keys. (Maybe multiple keys per owner, if needed.)

Is it possible to create some (non-interactive, i.e. single-message) protocol such that the following conditions are fulfilled?

Bob can construct a message using only his private key (maybe also his public one) and Alice's public key.
Alice can use her private key (maybe also her public one) and Bob's public key to verify that this message is from Bob.
Eve, who knows neither Bob's nor Alice's private key, can't construct a message which will pass Alice's check.
Alice can construct the same message using her private key (maybe also her public one) and Bob's public key.

What kind of primitives are needed here?

I don't require Bob's message to be encrypted, but your protocol might do so, if this is easier to realize. I only care about the authentication & repudiation part.

(If these conditions are not sufficient or not necessary for authentication without non-repudiation, please point this out, too.)

(This question is inspired by Can I use PGP to sign a message without providing cryptographic non-repudation?, which asks for a solution of a similar problem using OpenPGP and signatures, but doesn't actually specify the requirements. This one is wider and more on a theoretical level.)

There's an obvious solution using DH: Alice has a private key $a$ and a public key $g^a$; Bob has a private key $b$ and a public key $g^b$.

When Bob sends a message, he computes the shared secret value $(g^a)^b$, converts that into a MAC key (possibly using a nonce to prevent key reuse), computes the MAC of the message, and sends the message and the MAC (and any nonce) to Alice.

When Alice receives the message, she computes the shared secret value $(g^b)^a$, converts that into a MAC key, and verifies the MAC.

Now, Eve cannot modify the message, because she doesn't know the MAC key, because she can't solve the DH problem based on the public keys $g^a$ and $g^b$.

Alice can validate that the message was sent by Bob.  However, she can't prove it to anyone else, even if she were willing to expose her private key, because she is just as able to generate that message as Bob was.


Why we need to use a modulus in public cryptography? I know that in public cryptography we use asymmetric keys (public and private) for encryption and decryption. But we also use a modulus which fixes the ciphertext length. Isn't that a disadvantage?
Please, can you explain why we use the modulus?

The DH, ECDH and RSA problems require modular operations. They are fundamental in the problem space that they operate in (where problem is a mathematical term). Please go through an introduction of number theory for cryptography to understand why - or take it for granted if you don't want to delve that deep.

Besides that, performing exponentiation on large numbers is definitely more troublesome without modulus than with a modulus. Imagine raising a number of, say 2048 bits to the power of a private exponent of 2048 bits. The resulting number would have a value of about $2^{{2048}^{2^{2048}}}$. Now I don't know about you, but I'm pretty sure that number is too big to handle. Modular arithmetic is much more efficient than non-modular arithmetic as well; you can easily get a feel for this yourself, what's the last digit of $2459 \times 9823$ or $9823^4$?

Finally, we don't need to have an asymmetric primitive such as RSA to handle large plaintext/ciphertext; we can use symmetric primitives for that, creating a hybrid cryptosystem. For instance we can use a cryptographic hash (such as SHA-256 or SHA-512) to create signatures together with RSA-PSS. And we can use a symmetric cipher together with RSA-OAEP or RSA-KEM to create a secure cryptosystem. That way we can handle larger plaintexts / ciphertexts without having to deal with the size limitations of asymmetric primitives.


In ISO/IEC 9796-2 (signature with message recovery), why are some message representatives bigger than the modulus? I have implemented signature scheme 2 from ISO/IEC 9796-2 in C using OpenSSL for the underlying crypto operations.

To generate the message representative (F in the standard), I just call PKCS1_MGF1() (defined here), and then XOR that to the data to be signed, excluding the hash and the trailer, as the standard says.

Then, I get that blob and run it through RSA_private_encrypt(), setting the padding flag to RSA_NO_PADDING (docs here).

It turns out that, for some inputs, the resulting message representative is bigger than the modulus when converted to a number, which causes RSA_private_encrypt() to fail.

NOTE: the message representative is computed according to the standard, it is always 128 bytes in length (just like the modulus), and it matches the samples provided in Appendix E, so I presume there are no bugs in the way I generate F.

My key is a 1024-bit RSA private key generated with openssl genrsa, with e = 65537, which is an odd number. To the best of my understanding, given that e is odd (which the standard calls v, but they're otherwise the same thing) I can use the "alternative signature production function" (defined in Appendix B.6), which is, well, basically textbook RSA.

Is there anything I have misunderstood that is causing this issue?

If my implementation is correct, then how could I deal with these Fs that are bigger than the modulus?

ISO/IEC 9796-2 is a digital signature scheme giving message recovery. That is: able to embed some of the message in the signature, thus lowering communication or/and storage requirements. There are a lot of options:

Total recovery is when the message is fully embedded in the fixed-size signature; this limits the message size to a certain capacity. This opposes to Partial recovery were the message size exceeds the capacity: the recoverable part $M_1$ of the message (up to capacity) is embedded in the signature, and the (non-empty) non-recoverable part $M_2$ must somewhat be made available to the verifier independently from the signature (often: along).
There are 3 schemes:

#1 is the original, simplest, but is at least theoretically broken in a chosen-messages setup. It is used in in EMV, Passport, and Digital Tachograph.
#2 is inspired by RSASSA-PSS, and uses random salt and MGF1.
#3 is simply #2 with no salt.

The hash used for signature. A common choice for 1024-bit modulus would have been SHA-1, but both are obsolete. A modern choice is SHA-256.
If that hash is assumed known by the parties (Trailer field option 1) or encoded in the message representative trailer (rare: the motivation for ISO/IEC 9796-2 is compact signed messages, so the overhead of explicitly encoding the hash is unwelcome, plus that's not a good idea from security and simplicity standpoints).
For schemes #2 and #3: which hash is used for MFG1. Two popular choices are SHA-1, and the same hash as in as the signature.
Salt size for scheme #2. The more salt, the simpler/stronger the security argument, but the lesser the capacity.
Odd or even public verification exponent $v$, that is RSA or Rabin. $v=2$ provides the fastest standardized signature verification around.
Use of "Alternative" signature (RSASP1 and RSAVP1 in PKCS#1, basically big-endian textbook RSA with left-padding with zeroes up to a fixed size), or non-alternative which saves one bit in the signature (I have only seen that with even public exponent, and in test vectors).
Modulus size: many implementations restrict to modulus a multiple of 8 bits, or a larger power of two.
Message alignment: the standard supports any size, but many implementations restrict to bytes.

When using byte-aligned message, $k$-bit modulus (multiple of 8), $L_h$-bit hash (multiple of 8), salt size $L_s$ (multiple of 8, possibly 0), Trailer field option 1, the capacity is $k-L_h-L_s-16$ bits.

There are variations in usage:

How the data to be signed is split in recoverable and non-recoverable parts of the message: the standard defines that the recoverable part of the message is at the beginning, but sometime it is desirable that the start of the payload data is readable before signature verification (e.g. because it includes a key index), therefore the recoverable part of the message sometime is gathered from the end of the payload data.
Signature before or after the non-recoverable message in signed data.
Tolerating use of partial message recovery mode when the message size is exactly the capacity.
Perhaps, tolerating a recoverable message $M_1$ shorter than the capacity including with a non-empty non-recoverable message $M_2$.

  It turns out that, for some inputs, the resulting message representative is bigger than the modulus when converted to a number.

That's a clear indication that the message representative is not computed correctly.

  To generate the message representative ($F$ in the standard), I just call PKCS1_MGF1() and then XOR that to the data to be signed, excluding the hash and the trailer, as the standard says.

Based on that oversimplified description, the problem likely is that the output of MFG1 is considered to be bytes, when the standard wants it one bit less than a multiple of 8 (when everything is byte-aligned). You want to zero the first/left bit of what MFG1 produces before the XOR, or equivalently zero the high-order bit of the message representative after the XOR. That won't lose message data, since that bit is part (or on the left of) the header.

  I can use the "alternative signature production function"

Yes. That's by far the most common when public exponent is odd.


Why is it necessary a prime factor recovery for a RSA Key-Pair Validation (in case of fix public exponens)? In NIST 800-56B publishing, this is done with the $(p, q) = RecoverPrimeFactors (n, e, d)$ function. I don't understand why is necessary if $p$ and $q$ are known during in generation. In my opinion, validation without the RecoverPrimeFactors function checks the required criteria.

I don't understand why is necessary if $p$ and $q$ are known during in generation.

Because rsakpv1-basic may be run by something that's not the key generation process; it is there to allow this second party entity to validate things.
We generally keep $p$ and $q$ in the private key (along with the other CRT parameters); 800-56B is apparently envisioning scenarios where we don't.


ElGamal with elliptic curves I It is very interesting to see @tylo's answer on ElGamal with elliptic curves.  Instead of mapping the message to the elliptic curve point it just reduces an elliptic curve point to its $x$ coodrinate. The scheme now becomes like this:

function $x^P$ denotes the $x$ coordinate of a point.

Encryption: choose random $k\in F_q$ , then calculate $C=kP$ and $c=x^{kY}$. The ciphertext is the point $C$ and the product $c\cdot m \bmod{q}$.

Decryption: From a point $C$ and a value $d$ calculate $c'=x^{xC}$. Retrieve the message with $m=d/c' \bmod{q}$.

Could anyone please clarify if the above scheme is additive homomorphic even if we set the ciphetext to be $c+m \bmod{q}$.

As @tylo says, projecting the point to the $x$ coordinate does not give you a homomorphism. So
this version is not useful if you want to have additively homomorphic ElGamal.

However, you could use the "exponential" version of standard ElGamal on elliptic
curves, i.e., instead of encrypting a message $m$ somehow mapped to a point $M$ on the curve (using an injective efficiently invertible encoding), to encrypt a message $m$ straightforwardly mapped as $M=m\cdot P$ to a point on the curve where $P$ is your generator and $m$ an integer in the order
of the group. This will give you an additive homomorphic encryption
scheme. However, as discussed below, this encoding is not efficiently invertible.

Let $P$ be the generator of your elliptic curve group of prime order $q$ and $Y=xP$ be your
public key ($x$ the private key). Then given two ciphertexts for messages $m_1,m_2\in Z_q$:

$C_1=(k_1P,m_1P+k_1Y)$ and $C_2=(k_2P,m_2P+k_2Y)$, then by componentwise point addition you receive

$$C=((k_1+k_2)P,(m_1+m_2)P+(k_1+k_2)Y)$$ which is a valid ciphertext for message $m_1+m_2 \mod q$.

You can decrypt $C$, but this obviously gives you $M=(m_1+m_2)P$ and in order to recover
$m_1+m_2 \mod q$, you have to compute $\log_P M$, i.e., you have to compute discrete logarithms after
encryption. If your messages $m_i$ come from a small set, this, however, is quite efficiently feasible. However,
this clearly depends on your application, i.e., which values from which range the $m_i$'s can take.


RSA - PKCS#1 padding - overall correction of algorithm From PKCS#1, page 24:

After we create the EM byte string and convert it to an integer, we then encrypt that integer with RSAEP (page 10) to get the ciphertext (as an integer).

My question arrives from the fact that RSAEP demands the input ($m$) to be less than the modulus ($n$).

My question is simple - how are we guaranteed that the integer representation of EM is in fact less than $n$?

Since that 15th bit (starting from the MSB) is $1$ (because the second byte (starting from the MSB) is 0x02), we know that m (the integer representation of EM) must be larger than $2^{8k-15+1}$ (where $k$ is the number of bytes in EM).

So overall, we know that $m\geq 2^{8k-14}$.

What stops $n$ (the modulus) from being less than $2^{8k-14}$?

I don't see a reason why $n$'s first 2 bytes can't be $0$, and the $k-2$ bytes that are left would be 1. In this case, $n=2^{8(k-2)+1}-1 = 2^{8k-15}-1$, and we can clearly see that
$m \geq 2^{8k-14} > 2^{8k-15}-1 = n.$

i.e. $m > n$.

What am I getting wrong here?

P.S. I hope I managed to make my question clear. Please ask me if I didn't explain myself well enough.

The case that the (encoded) message may be too long for proper encryption has already been envisioned and mitigated by the designers of the specification of the padding scheme.

First note, that $k$ in fact denotes the length of the modulus $n$ - in bytes. This length is always accurate, so if $k=256$ the modulus has a bitlength somewhere in $[2041;2048]$ or otherwise $k<256$ if the modulus was shorter.

So let's consider what can happen regarding the length issue.
If you choose the length of your message $mLen$ to be larger than the modulus, step one of the specification tells you to output "message too long". Theoretically you could apply the rest of the scheme if your message was three bytes shorter than the modulus, but it allows only for 11 bytes shorter to allow the random string $PS$ to take at least 64-bits length.

And finally let's consider how long $EM$ is. If you convert EM to an integer you'll get $k-1 = EM$ as the first byte is zeroed out. To make things sure even the second most significant byte is nearly completely zeroed out (except for the bit #15 you correctly identified). But as the modulus is guaranteed to be of accurate length, you'll never get this equation not to hold: $$n>2^{8(k-1)}>2^{8k-14}>EM > 2^{8k-15}$$


Proving an encrypted message contains (but does not 100% consist of) a plain-text message? I have keypair (u,r), and two pieces of data, X and Y.

I reveal X publicly but keep Y secret. Y has high entropy.

I then concatenate X and Y, into Z.

I encrypt Z, into "encrypt(Z,u) = Q". r is needed to decrypt Q back into Z.

Later, (when it doesn't matter), r will be revealed and everyone will decrypt Q into Z. At that point, everyone will know that, all along, Q "contained" X. Can I prove that Q contains X before r is revealed (including interactive zero-knowledge proofs)?

A fundamental theorem of cryptography (Goldreich, Micali and Wigderson 1986) states that any NP statement can be proven in zero knowledge. So, the answer is yes. For any polynomial-time combination of $X$ and $Y$ into $Z$, it is possible to prove that $Q$ contains $X$ in zero knowledge.

Note that the general zero knowledge will not be practically efficient since it requires a Karp reduction. However, depending on the combination and the public-key scheme, it may be possible to do this very efficiently. El Gamal specifically is very amenable to efficient zero knowledge, but it depends on the combination you mean.


Using a RSA signature to confirm the sender of a physical letter? (1) Alice wants to send Bob a physical letter.
(2) Alice also wants Bob to be confident that she sent the letter and not an imposter.
(3) Alice is confident that a potential imposter will not be able to intercept any letter she sends.
(4) Alice has previously in-person provided Bob a RSA Public key.
Can Alice use a RSA Signature to confirm she sent the letter?
What is the best approach Alice can take, that makes such verification as easy as possible for Bob?

A QR code can hold a bit over 2kiB. That's plenty for a short letter and a signature. If more is needed, use more than one QR code, and number them for ease of use.


AES-CTR vulnerability to cryptographic oracle I am new to cryptographic issues and from what I googled so far I could not retrieve the information I need.

Consider the use of AES-128 in CTR mode.
Let M be the set of possible plaintexts, for example M can be all the bytes sequences of a length lesser or equal than a specific integer n.
Let K be the private key and SK the symmetric ciphering/deciphering function.
Given an IV i and a plaintext p, we have (I see the initial counter value as an IV there) :

  c = SK(p,i)

And symmetrically :

  p = SK(c,i)

If an attacker has access to an oracle O that can perform the decryption, given a specific ciphertext :

  ∀m, i ∈ M, O(m) = SK(m, i), where i is an arbitrary IV, fed by the attacker

In other words, the attacker has access to a system that can encrypt/decrypt data using the private key K, which he wants to break (obviously, only the oracle system knows the key, the attacker can only use the system to encrypt/decrypt messages).

I would like to know to what leaks about the plaintext and/or the private key this kind of oracle can lead.
Are these leaks critical ?

EDIT :

The counter is made according to the RFC3686 pattern :
$(NONCE|CNT)$.
The $CNT$ part of the counter is 8-byte long and the counter is incremented once every 16 bytes.
A given $NONCE$, which is also 8-byte long, is never used twice.
Finally, $n$ can be from a few kilobytes to a few megabytes. But since an overflow will occur only if $n \geq 2^{128}$, there is no overflow.
The attacker has access to both the ciphertext and the counter scheme used to build it (the NONCE + the pure counter value). With the oracle, he can obviously decrypt the ciphertexts he intercepted. To sum up, here is what the attacker knows :

The ciphertexts
The counter scheme used to generate the ciphertexts
The corresponding plaintexts (because he can feed the oracle with the good (ciphertext, counter scheme) couple)

In general, CTR mode is not secure against chosen-ciphertext attacks.  (The same goes for the other classic block cipher modes of operation too; to get security against chosen-ciphertext attacks, you need authenticated encryption.)

In your stated attack scenario, the attacker can obviously use the decryption oracle to decrypt any ciphertexts they intercept, which (assuming there are indeed no limitations on the attacker's access to the decryption oracle) is as good as having the key.  Since this is kind of a boring scenario (the attacker always wins and there's nothing we can do about it), I'll assume that there are at least some messages that the attacker would like to decrypt, but for which they cannot directly query the decryption oracle.

For example, the attacker might only have access to the decryption oracle up to some time limit ("lunchtime attack"), but would like to decrypt messages intercepted after this time limit.  Unfortunately, with CTR mode (or any synchronous stream cipher), the attacker can still do this if they can predict (with reasonable accuracy) the nonces used for future messages: for each likely future nonce, they can ask for the decryption of a message consisting of a long sequence of null bytes using that nonce.  This will give them the raw keystream corresponding to that nonce, which they can then save for later, allowing them to decrypt any future message encrypted using that nonce.

Making the nonces unpredictable thwarts this particular attack, but still does not provide full IND-CCA2 security since the cipher remains malleable.  To make CTR mode non-malleable, you'll need to combine it with a message authentication code using the encrypt-then-MAC construction (i.e. first encrypt the message using CTR mode, then calculate the MAC for the IV + ciphertext).

Note that including the IV in the MAC calculation is essential; if you don't, the attacker can just intercept any legitimate message, change its IV, submit it to the decryption oracle and XOR the returned plaintext with the ciphertext to get the keystream for that IV.


How many hash collision will exist where the digest is a pre-image? This question follows on from the question Circular hash collision where digest is pre-image: Could hash(a) = b, hash(b)=c, then hash(c)=a?

The question was answered but the issue of the number of collisions was also raised. I have moved my answer to this query as a separate question. The other question begins:

For any SHA-family of algorithms (including Keccak) except for SHA1, would it be theoretically possible for there to exist a pre-image a whose hash digest b is the pre-image to the hash digest c which is the pre-image to a thus completing a circle (i.e. circular hash or collision of pre-image a with the digest a)?

${{hash(A)\to B}}$, ${{hash(B)\to C}}$ , ${{hash(C)\to A}}$

The answer to this is yes. My question is, how many such collisions would typically exist?

The expected number of 3-cycles in a random function on a large domain is $1/3$. More generally, for a random function on a set of size $n$, the expected number of cycles of length $\ell$ is asymptotically equivalent to $1/\ell$ as $n \to \infty$.

This result, along with a general approach to the combinatorical properties of random functions, can be found in the paper Random Mapping Statistics by Flajolet and Odlyzko (likely, the result has been derived elsewhere using different methods too).

Let me sketch how this result is obtained. Recall that the functional graph of a mapping is a set of components, each of which consists of a cycle to which trees are connected.

Let $t(z)$ be the exponential generating function for the number of (rooted) trees. It can be shown that (this is known as Cayley's formula)

$$t(z) = \sum_{n = 1}^\infty \frac{n^{n - 1}}{n!} z^n.$$

Since components are cycles of trees, the generating function for the number of components is

$$\log\left(\frac{1}{1-t(z)}\right).$$

Also, the generating function for the number of functional graphs would then be the exponential of the above. In order to count the number of cycles of length $\ell$, one can construct a bivariate generating function for the number of functional graphs in which the second variable "marks" $\ell$-cycles. That is, instead of the above generating function for the number of components, we define

$$\log\left(\frac{1}{1-t(z)}\right) + (u- 1)\frac{t(z)^\ell}{\ell}.$$

That is, the term (in the Taylor series in the variable $t(z)$) corresponding to cycles of length $\ell$ is multiplied by the marker variable $u$. The desired bivariate generating function at the level of the functional graph is then

$$\xi(z, u) = \exp\left(\log\left(\frac{1}{1-t(z)}\right) + (u- 1)\frac{t(z)^\ell}{\ell}\right).$$

One can see that the generating function for the sum of number of cycles of length $\ell$ over all functional graphs of fixed size can then be computed as

$$\Xi(z) = \frac{\partial\xi(z, u)}{\partial u}\Bigg|_{u = 1} = \frac{z^\ell}{\ell(1 - t(z))}.$$

It remains to determine the Maclaurin series coefficients of the above, at least for terms of very high order. This is possible by singularity analysis. We use the fact (by Proposition 1 in the paper of Flajolet and Odlyzko) that (as $z \to 1/e$)

$$1 - t(z) \sim \sqrt{2(1 - ez)}.$$

Hence,

$$\Xi(z) \sim \frac{z^\ell}{\ell\sqrt{2(1 - ez)}}.$$

The singularity analysis technique (Theorem 1 in Flajolet and Odlyzko) then shows that (with $\Xi_n / n!$ the coefficient of order $n$)

$$\Xi_n \overset{\star_1}{\sim} e^n\,\frac{n!}{\sqrt{2}\ell}\,\frac{\sqrt{n}}{n\Gamma(1/2)} \sim \frac{e^n n!}{\ell\sqrt{2\pi n}} \overset{\star_2}{\sim} \frac{n^n}{\ell},$$

where $\star_1$ is the actual singularity analysis and $\star_2$ follows from Stirling's approximation $n! \sim \sqrt{2\pi n}\, n^n/e^n$. In order to obtain the expected value of the number of $\ell$-cycles of a random function on a set of size $n$, it suffices to divide by the number of such functions ($n^n$): $\Xi_n \sim 1/\ell$.


Universal reencryption for signatures Universal reencryption is an interesting encryption primitive.  Attempts to build signatures schemes or protocols with authentication incorporating it have frequently failed though.

A plausible application of a signature scheme employing universal reencryption might be:

Alice's software obtains a blind signed credential from a signing authority, perhaps stating her age.  Alice wishes to use this credential with multiple websites, but obviously using the same signature on multiple websites violates the browser's cross origin policy because a typical signature depends upon a nonce that could be used to track Alice.  A signature scheme based upon reencryption might allow Alice to mutate the nonce embedded in the signature.

There is an easy solution to this problem if the signing authority simply gives Alice thousands of single use blind singed tokens and keeps her stocked up, but that entails some logistical complications.

It'd be lovely if Alice could just use the same signature over and over, mutating it each time through universal reencryption or similar.  Are there any signature schemes that support anonymizing the signature like this?

If we have a signature scheme with deterministic verifier and a non-interactive protocol which is [co-non-malleable as an argument of knowledge] and statistically witness-indistinguishable, then we can get a fully non-interactive version of what you want by letting "mutate" be

"run that protocol's prover on", and letting "verify" be "run that protocol's verifier on".

If the protocol is only in the CRS model but has the property that

statistical witness-indistinguishability holds for all possible outputs of the CRS generator, then assuming the existence of a compatible private key would be enough leave the CRS model

by letting the "CRS" be part of the public key, since the signer would store enough about the generator's randomness to let one verify that the "CRS" is a possible output of the generator.  Section 8.3 gives such a protocol.  Given a statistically hiding commitment scheme,

this paper's proof of Theorem 4 lets "assuming the existence of a compatible private key"

be replaced with "letting the signing phase be interactive".


how can I test quality of sbox? I have 11 sboxes, I want to test them and find the best one. How can I do that, I found several criterions for that but I could not understand.

I'd advise the result of Daemen and Rijmen on the matter called the wide-trail design strategy that has been used to construct the current AES.
Shortly you want s-boxes that have:

High algebraic degree

If you have the ANF of the Boolean function induced by your permutation which is a polynomial $\mathbb{F}_2[x_0,...,x_{n-1}]/(x_0^2 - x_0,..., x_{n-1}^2 - x_{n-1})$ then the algebraic degree is the number of variables in the largest product term of the function’s ANF having a non-zero coefficient.

Balancedness

Let $F$ be a function from $\mathbb{F}_n^2$ into $\mathbb{F}_n^2$. $F$ is balanced if it takes every value of the range exactly once.

High Nonlinearity

The aggregated nonlinearity of your S-box is the minimum nonlinearity of all of it's component functions which you can get with the Walsh-Hadamard transform

Low Differential uniformity

Define the difference distribution of any a function with respect to $a$ and $b$ elements from $\mathbb{F}_2^n$ as $DF(a,b) = \{x∈F_2^n:F(x)⊕F(x⊕a) =b\}.$
Then the differential uniformity is the maximum value got with this function using any pair of $a$ and $b$.

High differential branch number

this is calculated by $min_{x\neq y}wt(x⊕y) +wt(F(x)⊕F(y))$ where $wt$ is the hamming weight.

Note that these are still a subset of all tricks used in literature used to argue about s-boxes but the wide-trail strategy is currently still a good pivot point.
There are very useful tools in the SageMath library to easily check these properties: http://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html


Random Function size I am new to cryptography. I have question regarding the size of the set of random functions. I found the text from "Introduction to modern cryptography" by Katz and Lindell, in another thread which also relates to my question: Difference between Pseudorandom Function vs randomly chosen function

The text from "Introduction to modern cryptography" by Katz and Lindell (chapter 3.5.1) from the thread:

  Since the notion of choosing a function at random is less familiar
  than the notion of choosing a string at random, it is worth spending a
  bit more time on this idea. From a mathematical point of view, we can
  consider the set $\text{Func}_n$  of all functions mapping $n$ -bit strings to $n$
  -bit strings; this set is finite (as we will see in a moment), and so randomly selecting a function mapping $n$ -bit strings to $n$ -bit strings
  corresponds exactly to choosing an element uniformly at random from
  this set.

  How large is the set $\text{Func}_n$ ? A function $f$  is exactly specified by
  its value on each point in its domain; in fact, we can view any
  function (over a finite domain) as a large look-up table that stores
  $f(x)$  in the row of the table labeled by $x$ . For $f \in\text{Func}_n$ , the
  look-up table for $f$   has $2^n$   rows (one for each point of the
  domain $\{0,1\}^n$  ) and each row contains an $n$ -bit string (since the
  range of $f$   is ${0,1}^n$  ). Any such table can thus be represented
  using exactly $n\cdot 2^n$   bits.

  Moreover, the functions in $\text{Func}_n$  are in one-to-one correspondence
  with look-up tables of this form; meaning that they are in one-to-one
  correspondence with all strings of length $n\cdot 2^n$.

  We conclude that the size of $\text{Func}_n$  is $2^{(n\cdot 2^n)}$. ...

Assume $n = 2$

Than we have following mapping

00 00
01 01
10 10
11 11

00 11
01 00
10 01
11 10

00 10
01 11
10 00
11 01

00 01
01 10
10 11
11 00

if we rearrange so that each each row of $f(x)$ corresponds to each $x$. i.e. concatenating we will have following rows.

00 01 10 11
11 00 01 10
10 11 00 01
01 10 11 00

Each row will contain $n\cdot2^n$ bits. i.e. our case $2\cdot2^2 = 8$.
And according to my estimate(perhaps incorrect) total number of bits will be $2^n\cdot n\cdot2^n = n\cdot2^{2\cdot n} = 32$.

While text states the size is $2^{n\cdot2^n}$ i.e. $256$?
Could you please help me to find what I missed in my assumptions and where is my mistake?

Yo are taking only the one-to-one functions, while there are a lot of other functions, to name a few:

00 00
01 00
10 00
11 00

00 01
01 01
10 01
11 01

00 00
01 00
10 01
11 01

as you already mentioned, each table can be represented with $n*2^n$ bits, i.e. strings from the set: $\{0,1\}^{n*2^n}$, each string from this set defines one function from $Func_n$, so the number of such functions is the size of the above set $=2^{n*2^n}$


Why is DSA falling out of favor? Windows abandoned DSA rather than extend it to support > 1024 bits; but otherwise I cannot find a reason why DSA would be less desirable. I see in SSH the disabling it by default with a completely unsubstantiated claim that it is inherently weaker. But on the other hand GPG says that DSA is well-regarded.

My understanding is both the prime factorization problem and the discreet logarithm problems must hold for RSA to hold but only the discreet logarithm problem must hold for DSA to hold.

One disadvantage of DSA as conventionally implemented is that the key can be compromised if signatures are created on machines with poor random number generators.

In the wake of the Debian openssl fiasco this meant that any DSA key that had been used in an openssh client on an affected machine was potentially compromised. With RSA keys only keys generated on machines with the bad random number generator were affected (and were dealt with by a blacklist).


AugPake implementation Doubt K computation try to implement the AugPake protocol in java using BigInteger.

I am having some difficulty computing $K=Y^z \mod p$ because $z$ is always $0$, for $z={1\over x+(w*r)} \mod q$. Being a ratio between $1$ and a very large number $z$ will be always zero using the BigInteger.

Can help me to understand how to compute $z$? Maybe I misunderstood some of the document.

Thanks for your reponse.

To compute Z i use the extended Euclidean algorithm:
ax + qy = gdc(a,b)

Thanks a lot

This is not ordinary real-valued division.

The computation you are looking at is done in the field $\mathbb F_q$ instead of $\mathbb R$, that is $1/x$ actually is the modular multiplicative inverse of $x\bmod q$.


Improving efficiency of an "encryption" algorithm based on a chaotic map I've implemented an "encryption" algorithm that uses the deterministic chaos of an extended logistic map:

$x_{n+1}= r_n \cdot x_n \cdot (1-x_n)$

$y_{n+1} =
     \begin{cases}
       \text{$x_n+y_n$} &\text{if $x_n+y_n<1$}\\
       \text{$x_n+y_n-1$} &\text{if $x_n+y_n\ge 1$}\\
     \end{cases}$

$r_{n+1} = 3.57 + \left(0.23\cdot\sqrt{x^2+y^2}\right)$

The data is first chunked into $256\cdot64$ bits which I visualise as "squares". The initial values of $x,y,r$ are determined per-chunk by sampling bytes in a SHA-256 hashed key-data pair mixed with a hash of the index of the data chunk. I then map $x,y$ values from the range of the unit square to specific bits in the chunk and flip those bits iteratively, $(256\cdot64)^2$ times per chunk.

I am now looking to increase the performance of this algorithm, and I had an idea to apply some kind of chaotic "surface" to each chunk, sensitive to initial values. I would then only need to compute the value of this surface once per bit with a single function to spread the chaos over each chunk.

Having browsed Wikipedia's list of chaotic maps, I couldn't really seem to find anything that fit what I had in mind. Are there any known functions that might yield a good result?

Edit: After suggestions that chaos theory isn't possible to make secure, I wanted to find out whether other algorithms exist that use chaos theory. Apparently there is a large quantity of literature on this topic, especially focused on image encryption. Could someone explain the main sources of insecurity in a chaos theory based encryption algorithm?

If you already use a proper cryptographic primitive such as SHA, why would you use the "almost snake oil" chaotic encryption mechanism?

It is impossible to prove any security properties for such maps beyond "passes randomness tests" since distributional guarantees are impossible to provide, unlike traditional cryptosystems.

Thus they offer no security advantage over traditional cryptosystems.


How is the hash for a file calculated? Is the file just read bit by bit to calculate the hash with those values or is there more to it?

Are there any resources to read a bit more about file hashing?

Hash functions operate on blocks like SHA-256 has 512-bit input block. In SHA-256, your data $m$ is divided into 512-bits blocks $m_1,\ldots,m_n$ where each entered into the hash function. The final block, $m_n$ is padded as

$$k=(447−l) \bmod 512$$ where data size is $l$ and $k$ is the number of zeros following the 1 after $m$ and finally the message size in 64 bits. The message size can also 128 which allows larger files to be hashed. So the input to SHA-256 is

$$m\|1\|0\ldots0\|\text{size_of(m)}.$$

Each other hash function defined in a similar way, an example from FRC4634

  The hash functions specified herein are used to compute a message
     digest for a message or data file that is provided as input.  The
     message or data file should be considered to be a bit string.  The
     length of the message is the number of bits in the message (the empty
     message has length 0).  If the number of bits in a message is a
     multiple of 8, for compactness we can represent the message in hex.
     The purpose of message padding is to make the total length of a
     padded message a multiple of 512 for SHA-224 and SHA-256 or a
     multiple of 1024 for SHA-384 and SHA-512.

Note: The 64-bit (or 128-bit) message size also determines the maximum input size for a SHA-256 hash.


Encrypting user data with their password? I had an idea once that all of the user data (including the username) could be encrypted with the user's password. Obviously, most sites would store different data, so using the same password and username would not make the same output in the database. For extra security, you might use a salt. A table in a database might look something like this:

Username    User data (normally encrypted with password, but put in plaintext for demonstration)
johndoe     {"username":"johndoe","latestSearch":"funny cat videos"...}

Would this work, are there better ways to do it, or does this have flaws?

There are a number of considerations here, I'll try to lay them out one at a time for ease of following:

What must the site do with the data?

Oftentimes, we ask web sites to do things on our behalf when we are not actually visiting them.  For example, I may want crypto.SE to email me when there are responses to this post.  The site could not do that without access to my email address, preferences, and the list of which posts I've subscribed to.

Either the site does not ever need to access a user's data (or at least not when the user is not logged in, if we want to do some session management as part of our scheme)...or the benefit of encrypting each user's data with a different key is negated by the fact that the keys need to be stored near the data.

What do you mean exactly by "encrypt the data with the password"?

When an infosec professional says "encrypt foo with bar", we literally mean that bar is being used as the key for an encryption algorithm that will turn foo into encrypted-foo.  When it comes to user-supplied passwords, this is universally a bad idea.  Most users choose terrible passwords.  Even a good password policy might get you a passphrase of 20 characters or so with a digit or uppercase thrown in as a gimmee...at best.  That isn't very much entropy in the grand scheme of things (even less when 42 of your users pick their favorite bands' names or family pets).

OTOH, what one might do to combat the lack of entropy is to use the password to encrypt a decent, randomly-generated encryption key, which is in turn used on the data.  That's much less terrible.  Not perfect (what encryption is perfect?), but markedly less terrible.

As a free bonus, the use-password-to-encrypt-key method helps with the fact that yes, stupid users will recycle passwords, and their accounts on various sites where they have recycled passwords will inevitably have some duplicate content that can be matched up should that ever be relevant to an attacker.

Why are we doing this again?

You ask "Would this work?", but you never actually defined what the problem was that you were trying to solve.  This is one of the first things I advise you un-learn on your path to getting good at crypto and/or infosec in general.  ALWAYS define a goal, a use case, or some sane description of what you mean to accomplish in the first place.  Failing to correctly and adequately define the problem before solving it is how a massively large fraction of screwups happen, in infosec and elsewhere.

"Would this work?" as a proxy for "could I actually code and run something like this?" ->  Yes, you could.  I wouldn't advise it, but it would work.

"Would this work?" as a proxy for "Would this make my database's data less likely to be stolen if my database fell off of a truck?" -> Probably not.  Granted, most DBs sit unencrypted on disk, but they do that for a reason: they're always unencrypted, or the keys stored nearby, when in use.  Also, for your option of directly encrypting data with user-supplied passwords as the key, the likely weakness of the passwords makes offline attacks on most of that data trivial.

"Would this work?" as a proxy for "Would it be a good idea to implement this in a production system?" -> Absolutely not.  The argument that this scheme provides added protection is weak, but the complexity it would introduce into the web application software is significant.  Even if the encryption scheme were somehow useful (which I'm not buying so far), the added complexity is almost certain to result in vulnerabilities of a magnitude greater than the increase from the encryption.

I may be off base, of course...

I did presume some things from your very light specification... I presumed that you are talking about encrypting data at rest in a publicly accessible web application's database.

Related things

I'm not trying to kill all of your aspirations here, just to introduce the harsh reality.  The good news is that you are kinda-sorta dancing around something that IS a viable concept:

In something that's not a webapp, where the service provider doesn't need access to users' data (e.g. a backup service), it IS wise for users to store their data with keys that they (the users) control.  Furthermore, those keys should not be shared with the provider, who's just acting as a warehouse at that point.  This is, in fact, how every responsible cloud backup provider behaves.


If the input text and output text in DES are the same what is the value of the key? If some 64-bit message block (e.g. $M = \text{“12345678”}$) was encoded in DES using one key and the encoded message had the same value (i.e. $E_k(M) = \text{“12345678”}$), would it be possible to determine the DES key based on that?

I'm not aware of such DES key which $E_k(M)=M$

DES has 4 Weak Keys which allows $E_k(E_k(M))=M$

i.e. if you encrypt the encrypted message, you get as result the original message.

  page 159-160

Keys before parities drop (64 bits) | Actual key (56 bits)
0101 0101 0101 0101                   0000000 0000000
1F1F 1F1F 0E0E 0E0E                   0000000 FFFFFFF
E0E0 E0E0 F1F1 F1F1                   FFFFFFF 0000000
FEFE FEFE FEFE FEFE                   FFFFFFF FFFFFFF

  Example 6.8 Let us try the first weak key in Table 6.18 to encrypt a
  block two times. After two encryptions with the same key the original
  plaintext block is created. Note that we have used the encryption
  algorithm two times, not one encryption followed by another
  decryption.

Key: 0x0101010101010101
Plaintext: 0x1234567887654321 Ciphertext: 0x814FE938589154F7

Key: 0x0101010101010101
Plaintext: 0x814FE938589154F7 Ciphertext: 0x1234567887654321


The existence of partial homomorphic additive encryption with bit-wise XOR operation According to  Protocol A that was presented in Section 3.1  paper entitled "Some Efficient Solutions to Yao’s Millionaire Problem" (2013). [1]

In that protocol they used an assumption that there is an encryption function that has the homomorphism property with respect to both additions (over some finite field) and bitwise XOR operations.

Can someone please send a reference to scheme that uphold the requirements?

My current candidate is to combine the answer in [2] and micali-goldwaser encryption [3].

But I don't know how (and if it possible) the scheme could work  and overcome:
(1) $N$ in GM  cannot be a $Z_{2^q}$ as it's a multiplication of two primes.
and
(2) Is it possible to work with 2-complement binary representation ( To perform the subtraction operation).

[1]- https://arxiv.org/pdf/1310.8063v1.pdf

[2]- Homomorphic encryption based on XOR

[3]- https://en.wikipedia.org/wiki/Goldwasser%E2%80%93Micali_cryptosystem

Assuming the finite field is of odd characteristic (that is, $GF(p^k)$ for some prime $p > 2$, then such an encryption operation would be FHE; and would be much bigger news than just only solving the Millionaire problem.

With such an encryption method, given $E(a)$, $E(b)$ and a constant $c$, we can compute $E(c)$,$E(a \oplus b)$, $E(a + b)$ and $E(c \times a) = E(\underbrace{a + a + ... + a}_{\text{c times}})$ (where the addition and multiplication are within $GF(p^k)$,   If we can't compute $E(c)$ directly, we can just place $E(c)$ within the public key (assuming that the range of possible $c$'s is limited).

So, assuming $a, b$ are restricted to $\{0, 1\}$, we can compute the NAND operation $E(\overline{a \wedge b}) = E( 1 \oplus (k \times ((a + b) \oplus a \oplus b)))\ $ for the constant $k = 2^{-1} \pmod p$.  It is straightfoward to see that this function gives $E(1)$ if either of $a, b$ is 0, and $E(0)$ otherwise.

With this encrypted NAND function, we can construct any circuit.


Should I authenticate memory data which was loaded from authenticated disk file? Encrypted fields are loaded from disk file to process memory only after file's HMAC validation is successful. Data is still encrypted in memory and will be decrypted later, on demand, when it needs to be displayed to the user (cipher is initialized on process start). The system also allows user to add new data which will be encrypted to memory and later saved to disk. CBC mode is used.

Besides file's HMAC, does adding HMAC to each encrypted field and validating it before decryption makes sense? Or in other words, should I authenticate memory data which was loaded from authenticated disk file? The goal is to make make the app as secure as possible and minimize possibilities of tampering.

[D]oes adding HMAC to each encrypted field and validating it before decryption makes sense?

No. Since you authenticate the data once, you can trust that it is the same as was originally encrypted and authenticated. That is, authenticating the ciphertext also authenticates the plaintext.

  The goal is to make make the app as secure as possible and minimize possibilities of tampering.

This may sound like a good goal, but it is really not. A good goal would be to have specific security objectives and types of attacks you want to prevent. For example, you should consider what kind of security you would expect in the case that an attacker 1) was able to read the disk image or 2) was able to write arbitrary data on disk.


ElGamal: Multiplicative cyclic group and key generation Here on the ElGamal wikipedia page http://en.wikipedia.org/wiki/ElGamal_encryption

  Alice generates an efficient description of a multiplicative cyclic group G, of order q, with generator g.

How is this done?  What are some of the properties here?

I'm not sure what level of explanation you are looking for, but from the very basics, subgroups work like this.

Consider concretely the example of working $\mod{p}$ where $p=11$. Next we have to find a generator $g$. Initially, any number $\{0,\ldots,n-1\}$ (or $\mathbb{Z}_p$ for short) is a candidate.

Below is a chart showing each $g$ value as a row, each $a$ value as a column, and the expression $g^a \mod{11}$ evaluated for each $g$ and $a$.

$
\begin{array}{c|ccccccccccc}
 g \backslash a & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline
 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
 2 & 1 & 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\
 3 & 1 & 3 & 9 & 5 & 4 & 1 & 3 & 9 & 5 & 4 & 1 \\
 4 & 1 & 4 & 5 & 9 & 3 & 1 & 4 & 5 & 9 & 3 & 1 \\
 5 & 1 & 5 & 3 & 4 & 9 & 1 & 5 & 3 & 4 & 9 & 1 \\
 6 & 1 & 6 & 3 & 7 & 9 & 10 & 5 & 8 & 4 & 2 & 1 \\
 7 & 1 & 7 & 5 & 2 & 3 & 10 & 4 & 6 & 9 & 8 & 1 \\
 8 & 1 & 8 & 9 & 6 & 4 & 10 & 3 & 2 & 5 & 7 & 1 \\
 9 & 1 & 9 & 4 & 3 & 5 & 1 & 9 & 4 & 3 & 5 & 1 \\
 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1 & 10 & 1
\end{array}
$

Property 1: for each row (except the first), the numbers eventually reach $1$ and then repeat.

The first generator, $0$, is degenerate. We usually exclude it from consideration. $\mathbb{Z}_p$ without $0$ is denoted $\mathbb{Z}^*_p$.

The next generator, $1$, only generates the number $1$.

The next generator, $2$, generates $\{1,2,4,8,5,10,9,7,3,6\}$, which if you sort turns out to be each 10 elements of $\mathbb Z_p^*$.

The next generator, $3$, generates $\{1,3,9,5,4\}$.

Generators $6,7,8$ generate the same group as $2$ (just in a different order). Generators $4,5,9$ generate the same group as $3$. Generator $10$ generates $\{1,10\}$.

There are a lot of properties contained in this chart but the relevant one is to consider the order (number of elements) in each possible group. We saw generators with $1$, $2$, $5$ and $10$ elements. These numbers are not coincidental. Property 2: they are the factors of $p-1$ which is $10$ when $p=11$. This holds true for any $p$ that is prime.

Each of these smaller groups are called "subgroups" of $\mathbb{Z}^*_p$. Take the group generated by $3$: $\{1,3,9,5,4\}$. If you take any element of this group and multiply it by any other element $\bmod 11$, the result will always be one of the elements of this group. This means it is closed under multiplication or a "multiplicative subgroup." Property 3: If $p$ is prime, each subgroup will be multiplicative.

For the security of Elgamal, we essentially want both $p$ and the order of the subgroup $q$ to be large primes. This means $q$ should divide $p-1$. In the example $p=11$ and $q=5$. It is typical to set $p=2q+1$ (that is $(p-1)=2q$). For things other than Elgamal (like DSA), we might use $p=\alpha q+1$ for some $\alpha$ larger than 2 (e.g., so that $p$ will be 1024 bits and $q$ will be 160 bits). For $p=2q+1$, there will be subgroups of order $p-1$, $q$, $2$ and $1$ (the factors of $p-1$). Most generators will either have order $p-1$ (generating $\mathbb{Z}^*_p$) or $q$ (generating a group we call $\mathbb{G}_q$).

How do we find $\mathbb{G}_q$?

Find a $p$ that will have $\mathbb{G}_q$: we choose a random prime $q$, compute $p=2q+1$, repeat until $p$ is prime.
Find a $g$ that will generate $\mathbb{G}_q$ and not $\mathbb{Z}^*_p$ (or any other subgroup). Since groups end with $1$ and then repeat, we test if $g^q \mod{p}$ is equal to $1$. If it is, we have very likely found a generator of $\mathbb{G}_q$ (and very unlikely found something of order $1$ or $2$; we can check that $g^2$ is not equal to $1$).
The description of the group is $\langle g,q,p \rangle$ (you could compute $q$ from $p$ to save space in the description).

One final thing: look at the column with $a=2$. These are the quadratic residues of $\mathbb{Z}_p^*$. Property 4: When $p=2q+1$, they are the exact same group as $\mathbb{G}_q$. This means, by using $\mathbb{G}_q$, you don't have to worry about an adversary testing if certain numbers are quadratic residues or not (see @Jalaj's answer).


How to encrypt sensitive files in a business application? Is it needed? I'm currently working on a business Java application, and we store sensitive files related to our users. What is the appropriate approach to store them securely?

Is it viable to encrypt/decrypt all the files in the business logic, and then store them in the filesystem? Then what the key could be? If I derive a key from the file uploader's password, other, authorized people won't be able to decrypt the file.

Or it would be better if we would concentrate on the infrastructure's security, because it is not frequent to encrypt files for a business application?

Or it would be better if we would concentrate on the infrastructure's security, because it is not frequent to encrypt files for a business application?

If an attacker gains access to your server he can just steal, modify or delete all kind of data. This is not a desired consequence to suffer if someone breaks your security. Specially if the sensitive data is in plaintext.

For example, in the case you store files, the attacker can modify them to alter their functionality to install malware in the user's computer.

  If I derive a key from the file uploader's password, other, authorized people won't be able to decrypt the file.

In your scheme, every user will have two keys, one for encryption and the other for providing integrity and authentication via MAC. This is done applying a key derivation function to a Master Key. In the case your server get compromised and the user's data gets modified, the legitimate user will notice the modification since tags are not equal.


Encrypting the relationship between two database tables I'm not a cryptography expert myself, and know enough to know that I shouldn't design my own crypto schemes, so I thought I'd seek advice here.

In an application, let's say we have two database tables: Lawyers and Clients. There exists a many-to-many relationship between these two models, so a Lawyer can have many Clients and a Client can have many Lawyers. As is typical in relational databases, there is a Join Table containing pointers to rows in each table in order to define the relationships between them.

The columns for the Join Table might look like this:

id | client_id | lawyer_id

Now let's say that in our security model, information about lawyers and information about clients are not considered privileged information on their own, so there's no need to encrypt them in any way. However, information about the relationship between Lawyers and Clients is privileged information that we would like to protect in the event an attacker gains access to the database.

Does there exist a common encryption scheme that securely encrypts client_id and lawyer_id without rendering the Join Table useless?

Provided that any user, who is supposed to have access to any relationship, may be granted access to all relationships, one solution would be to use a SQL engine that supports table level access control through table encryption, and encrypt the Join Table. In such case a decently implemented symmetric encryption scheme would be sufficient.

An attacker who gains physical access to the database files, will need the key for the Join table to be able to extract information from it. Conversely, if the attacker gains guest access to the database through the SQL interface, privilege elevation would be required to gain Join Table access.

However, such solutions are not sufficient e.g. in scenarios where any client is supposed to be able to run a query for his or her own lawyers, or conversely, where some lawyers are not allowed to run queries for any clients but their own. In such case, a trivial solution would be to encrypt each record separately, using a symmetric encryption scheme under a randomly generated content encryption key that, in turn, is encrypted using e.g. RSA-OAEP and the public RSA key of each user that is supposed to have access to the record, with the RSA cipher texts being stored in a fourth table. Such schemes would require the join process to be implemented to run locally (since the process would need access to the RSA private key).

Another alternative altogether would be to use Predicate Encryption, but such schemes are arguably very far from "common"-