Interpretation of advanced composition theorem of differential privacy In "The Algorithmic Foundations of Differential Privacy" book, Advanced Decomposition Theorem (Thm 3.20) is stated as follows:

For all "$\epsilon, \delta, \delta' \geq 0$, the class of
($\epsilon,\delta$)-differentially private mechanisms satisfies
($\epsilon',k\delta+\delta'$)-differential privacy under $k$-fold
adaptive composition for:
$\epsilon'=\sqrt{2k\ln{(1/\delta')}}\epsilon +k\epsilon(\exp(\epsilon)-1)$

I have two questions related to this theorem:

If the all private mechanism of interest are $(\epsilon,0)$-differentially private, and in my understanding $\delta'$ is a tuning parameter, can't we have $\delta'=0$? Isn't that theorem a better composition than the basic decomposition in which $\epsilon$'s and $\delta$'s adds up? In the basic decomposition theorem, if all the mechanisms are $(\epsilon,0)$-differentially private, then we can have $(k\epsilon,0)$-differentially private composition.
On page 52 of the same book (just after Example 3.7), it is said that:

So how many queries can we answer with non-trivial accuracy? On a
database of size $n$ let us say the accuracy is non-trivial if the
error is of order $o(n)$. Theorem 3.20 says that for fixed values of
$\epsilon$ and $\delta$, it is possible to answer close to $n^2$
counting queries with non-trivial accuracy. Similarly, one can answer
close to n queries while still having noise $o(\sqrt{n})$ — that is,
noise less than the sampling error.

I didn't understand how Theorem 3.20 says that. How do we measure the error here, and how the theorem is used to conclude this?

Consider the composition of $k$ algorithms each of which is $(\varepsilon,0)$-differentially private. We want to calculate parameters $\varepsilon'$ and $\delta'$ such that that the composition of these algorithms satisfies $(\varepsilon',\delta')$-differential privacy.

The comparison is between advanced composition
$$\varepsilon' = \sqrt{2k\log(1/\delta)}\varepsilon + k \varepsilon (e^\varepsilon-1)$$ and basic composition $$\varepsilon' = k \varepsilon$$.

There is no way to say that one of these expressions is universally better than the other, as it depends on the parameter settings. However, we can argue that for some realistic parameter settings the first is better than the second.

What do I mean by realistic parameter settings? Let's say that the number of queries is fairly large (e.g., $k = 10^5$) and the final privacy parameters are not too big (e.g., $\varepsilon' = 1$ and $\delta'=10^{-6}$).

Then for basic composition we need $\varepsilon = \varepsilon'/k = 10^{-5}$.
For advanced composition the calculation is a bit messier, but we can calculate that $\varepsilon=58 \times 10^{-5}$ suffices. In other words, advanced composition saves a factor of $58$ over basic composition. The improvement becomes more dramatic as $k$ increases.

Asymptotically, if we think of $\varepsilon'$ and $\delta'$ fixed but $k$ becoming larger, we see that basic composition requires $\varepsilon \approx 1/k$, while advanced composition requires $\varepsilon \approx 1/\sqrt{k}$. (I'm dropping all non-relevant terms and constants here.) This is the advantage of advanced composition.


Why do MD5 and SHA-3 use different padding schemes? What is the rationale for the difference between MD5 and SHA-3 padding schemes?

MD5 appends 10* and then the 64-bit message length in bits.
SHA-3 appends 10*1.

Why do they use different padding schemes?  MD5 is based on the Merkle-Damgard construction, while SHA-3 is based on the sponge construction—is this relevant?

From the Keccak Team:

  When a padding rule is used with particular properties, one can securely instantiate sponge functions with different rates with the same fixed-length permutation. The simplest padding rule satisfying these properties is called the multi-rate padding: it appends a single 1-bit, then a variable number of zeroes and finally another 1-bit.

So the goal was to make a padding construct that worked with all variations of Keccak, including those that became standardized as SHA-3. The approach keeps those variants prefix-free and as simple and similar as possible to aid cryptanalysis.

The length of the input is included implicitly in the state of Keccak based on the number of calls to the permutation and the padding value. Encoding the input length simply  isn’t needed in Keccak, so it was omitted.


Is equal length of primes in Paillier cryptosystem is mandate for security reasons? In continuation to this question about length of primes , I am in doubt about the restriction on length of primes itself .

In Paillier  cryptosystem , equal length of primes are used .

My doubt is whether this restriction is to ensure the following condition only

$$\gcd(pq,(p-1)(q-1))=1$$

or , there are another security reasons that makes the equal length condition mandate .

I mean, in cryptosystems like RSA, approximately equal length primes are generally preferred for security reasons , If the length is more than specified value, then cryptosystem is not secure.

Is it the same case in paillier cryptosysyem too or not ?

No, exactly equal length of primes $p$ and $q$ is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that $p$ and $q$ are prime, $N=p q$ is hard to factor, and $\gcd(p q,(p-1)(q-1))=1$.

The requirement that $p$ and $q$ are of exactly equal size is usually made in the Pailler cryptosystem because this requirement

implies that $p<2q<4p$, which implies $\gcd(p q,(p-1)(q-1))=1$, which is a must for the Pailler cryptosystem to work;
is customary in RSA, and thus is an easily met condition, and unobjectionable from a security standpoint;
is a consequence of stronger conditions mandated by FIPS 186-4 and the earlier ANSI X9.31 RSA key generation standards, which both require $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for integer $k$ at least 512 (and further constrained, including to be a multiple of 64), because it simplifies implementations of RSA, including using the CRT method; and similar implementation considerations apply to the Pailler cryptosystem.

More precisely, on security:

even though imposing that $p$ and $q$ are of exactly equal size does reduce the choices for $N$, and thus helps at least some factorization algorithms (notably Fermat's and derivatives), it would be a surprise if such algorithms could be extended to factor with odds $\epsilon$ and expected cost lower than $\epsilon\min(p,q)^u$ operations, where $u\approx2/5$ in our wildest dreams, and even $u\approx1/2$ is hard to reach; thus such algorithms are not to fear in the first place, for they do not have odds worth consideration to factor products of two randomly-generated primes of approximately equal size if that size makes factorization by GNFS hard enough; says $N$ at least 768-bit (the current academic record), thus $\min(p,q)$ at least 350-bit, making $\min(p,q)^{2/5}$ at least 140-bit.
on the contrary, that $p$ and $q$ are of exactly equal size slightly increases the expected time to factor $N$ by the sub-exponential ECM for a given size of $N$, and does not lower the expected cost of any other sub-exponential algorithm that we know; thus can be regarded as more beneficial than not from a security standpoint.


Is Encrypt(m||k2, k1) secure authenticated encryption? I don't fully understand the need for MAC algorithms to authenticate encrypted messages. As I understand, the standard is to send something like
$\mathrm{E}(m,k) \| \mathrm{MAC}(m,k)$ where $E$ is an error-propagating block cipher, $k$ is an encryption key.

Would it not be easier simply to send
$\mathrm{E}(m\|s,k)$ where $s$ is a salt shared across the system? After decryption, the receiving user can simply check that the last $\mathrm{len}(s)$ bytes of the message match $s$ to check its authenticity.

Would it not be easier simply to send $E(m||s,k)$ where s is a salt shared across the system?

Yes, that would be simpler; however, that would not (in general) be secure.

The assumption you are making is that if someone modifies the ciphertext in any way, then the last few bits of the resulting plaintext must also be modified.  This is often not the case:

If we are using CTR mode, then someone modifying byte $i$ of the ciphertext will cause byte $i$ of the plaintext to be modified, without any other changes.  So, the attacker can avoid this protection by simply limiting his changes to the first part ($len(m)$) of the ciphertext
If we are using CBC mode, then someone modifying block $i$ of the ciphertext will cause blocks $i$ and $i+1$ of the plaintext to be modified; assuming that attacker does not modify that last two blocks of the ciphertext, his modifications will be undetected.


Worst-Case hardness of lattice problems I just started work on lattice-based cryptography and I could not understand the concept of worst-case to average-case reduction.
We generally say,
Average Case Hardness: Random instance of a problem is hard to solve.
Worst-Case Hardness: Hard to solve every instance of the problem (even if most instances are easy)
So far, so good
But I could not establish the relationship between lattices and worst-case hardness concept. Let's say our problem is "Shortest Vector Problem (SVP)". I know it is a hard problem and we can prove the security of lattice-based cryptosystems based on hardness of this -or other related problems- problem.
My question is: What is the instances of this problem? Lattices? Given bases? or shortest vector of that lattice? Firstly, I thought "worst" related with "shortest vector" but I was wrong. Could you explain this?

An instance of the (approximate) Shortest Vector Problem is simply a basis of some lattice. The desired output is any (approximately) shortest nonzero vector of that lattice. To solve this problem in the worst case, an algorithm must produce the desired output given any basis of any arbitrary lattice. (Other lattice problems have similar instances, usually including a basis and sometimes other information, like an arbitrary target point in the case of the Closest Vector Problem.)


Which values are used for an elgamal cryptosystem public key? I know that – within the elgamal cryptosystem – the values of $a$ and $b$ are public. But which values are used to create public keys?

Let $p$ be a prime such that the Discrete Logarithm problem in $({\mathbb Z_p}^*,.)$ is infeasible, and let $\alpha \in {\mathbb Z_p}^*$ be a primitive element.

$$\beta =\alpha^a \bmod p$$

The values $p,\alpha , \beta$ are the public key, and $a$ is a private key. For a secret random number $k$ encryption and decryption are as follow:

$\operatorname{Enc}(x,k)=(\alpha^k \bmod p,x\beta^k \bmod p)$
$\operatorname{Dec}(y_1,y_2)=y_2\cdot{({y_1}^a)}^{-1}\bmod p$


Signing an integer, which may be increased I have a 64 bit integer. It has some sort of signature so that one can be sure it is valid.

Anyone may increase the integer, update the signature, and remove all trace of the old signature. But it is not permitted to reduce the integer.

Many updates are permitted.

Is there a scheme such that, given $n$ and publicly verifiable signature $S(n)$, we can calculate $n+x$ and $S(n+x)$ but only if $x>0$?

Yes, this is possible.  Here's one simple scheme:

The scheme.  We fix an upper bound $B$ for the maximum allowed value of the counter.  Let $H$ be a cryptographic hash function and $\text{Sig}(\cdot)$ be an ordinary signature scheme (e.g., a RSA signature).  Use $H^k(x)$ to the $k$-fold iteration of $H$ on $x$, e.g., $H^2(x)=H(H(x))$.  The signature $S(n)$ on counter value $n$ is a tuple $(n,x,y,\text{Sig}(y))$ that passes the following verification check.

Signature verification. The signature $(n,x,y,s)$ is valid if $H^{B-n}(x)=y$ and if $s$ is a valid signature on $y$.

Signing. Note that the signer can create an initial signature $S(0)$ by choosing $x_0$ randomly, letting $y=H^B(x_0)$, and signing $y$ to get $S(0)=(0,x_0,y,\text{Sig}(y))$.

Incrementing. Also, given a signature $S(n)=(n,x,y,\text{Sig}(y))$ on counter value $n$, anyone can increment $n$ to get a signature on $n+1$ as follows: $S(n+1)=(n+1,H(x),y,\text{Sig}(y))$.

Performance. Creating a signature takes up to $B$ iterative hashes and one ordinary signature.  Verifying a signature $S(n)$ takes $B-n$ iterative hashes and one ordinary signature verification.  Therefore, this scheme is only efficient if the bound $B$ can be kept relatively small.

Here are two small improvements on the simple scheme above:

A trick to speed up signature verification.  If you want to speed up signature verification, at least for small values of the counter, then you could use the following trick.  Let's assume for convenience that $B$ is a power of two.  The signer creates the initial signature $S(0)$ as

$$S(0) = (0,x,H^1(x),\text{Sig}(1,H^1(x)),H^2(x),\text{Sig}(2,H^2(x)),H^4(x),\text{Sig}(4,H^4(x)),\dots,H^{2^i}(x),\text{Sig}(2^i,H^{2^i}(x)),\dots,H^B(x),\text{Sig}(B,H^B(x))).$$

In other words, the initial signature $S(0)$ can be written in the form

$$S(0) = (0,x,y_0,\text{Sig}(1,y_0),y_1,\text{Sig}(2,y_1),\dots,y_i,\text{Sig}(2^i,y_i),\dots),$$

where $y_i=H^{2^i}(x)$.

Notice that, as a special case, a verifier can verify the signature $S(0)$ with just one hash application: hash $x$ once to get $H^1(x)$, then check its signature.  For larger values of $n$, signature verification will require more iterated hash computations, but not $B-n$ iterated hashes.

To increment the counter, you increment the $n$ part (as before), hash the $x$ part (as before), and throw away any $y_i$ parts where $2^i \le n$ and the corresponding signatures.

Consequently, the signature on $n$ now becomes

$$S(n) = (n,x,y_i,\text{Sig}(2^i,y_i),y_{i+1},\text{Sig}(2^{i+1},y_{i+1}),\dots),$$

where $i=\lfloor \lg n \rfloor + 1$.

With this trick, verifying a signature $S(n)$ now can be done in $O(n)$ time: it requires up to $n$ iterated hashes and one ordinary signature verification.  Note that signature verification is not constant time; as the counter gets larger, verification gets slower.  This trick does increase the length of the signature by a $\lg B$ factor.  One can trade off the length of the signature against the speed of verification, to a certain extent.

A trick to speed up signature creation. If you want to speed up signature creation, the following variant may be useful.  However, this variant does not speed up signature verification, so this variant probably won't be very useful on its own in practice.  The signer can select a RSA modulus $N$ (whose factorization is kept secret), and use the hash function $H$ given by $H(x)=x^2 \bmod N$.  Note that this is a one-way function.  However, it has the special property that there's a shortcut that allows the signer to compute $H^B(x)$ with much less effort than iteratively hashing $B$ times: namely, $H^B(x) = x^{2^B} = x^k \bmod N$ where $k=2^B \bmod \varphi(N)$ and $\varphi(N)$ is Euler's totient function applied to $N$.  The signer knows the factorization of $N$, so can compute $\varphi(N)$ and then compute $k$ using modular exponentiation mod $\varphi(N)$.  This is the shortcut; however, only the signer can use this shortcut, because no one else knows the factorization of $N$.  This shortcut can be used to efficiently create an initial signature $S(0)$.

Of course, you can combine both tricks into a single scheme, if you want to speed up both signature verification and signature creation.

Related work. You might also be interested in the following papers:

Cryptographic Counters and Applications to Electronic Voting.
Jonathan Katz, Steven Myers, Rafail Ostrovsky.  EUROCRYPT 2001.

A Cryptocounter Based on the Paillier PKCS.
Adam L. Young and Moti M. Yung.
Advances in Cryptovirology, Chapter 6.


Are there ANY text strings that will generate the same SHA-512 Hash output? Are there ANY text strings that will generate the same SHA-512 Hash output? Please provide an example, and how you came to that conclusion.

I've tried thousands of variations, including ".." vs. "." and "..." vs "..,". I believe it IS possible, I just don't know HOW I can find those 2 magic text strings.

This is trivially true via the pigeonhole principle. SHA-2/512 has $2^{512}$ possible outputs, but $2^{2^{128}} - 1$ possible inputs. Trying $2^{512}+1$ unique inputs is sufficient to produce at least one collision.

That said, SHA-2/512 is designed to be collision resistant, which implies that it should be hard to find two inputs that hash to the same value. Finding a way to quickly create such a collision would be considered a catastrophic break in the algorithm.

Today it is considered unfeasible to even find one SHA-512 collision - none have been found so far. There have been efforts to find a collision for SHA-1 though (notably the IAIK "SHA-1-Collison Search Graz Project"); it is thought that the SHA-1 algorithm is sufficiently broken to find one. These attacks don't translate to SHA-512 because of the increased complexity of the algorithm and the higher output size of the hash.


HMAC tag to verify the key (verification in the reverse direction) A quick question. Are there any problems with the following HMAC use-case:

We have two entities ($A$ and $B$), both of them have a secret ($A$ has $S_0$ and $B$ has $S_1$)

$A$ generates a random value $r$ and calculates the following tag: $t=HMAC(S_0,r)$
$A$ then sends $(r,t)$ to $B$.
$B$ calculates $t' = HMAC(r,S_1)$.

If the comparison $t' = t$ is true, does that imply that $S_0 = S_1$?

We are flipping the HMAC use-case around, instead of checking the authenticity of our message $r$, we are implying the reverse. And because HMAC is provable bound to the pre-image properties of the underlying hash, if the hash is secure, so is this use-cause (I did not write any formal reasoning or so, but my feeling is that if this is not true, then the security of the HMAC is not true).

Note that this is not true for encryption functions (mac then encrypt). CCA2 and ciphertext indistinguishability rule this use-case out (encryption is no authentication). But HMAC is an authentication scheme.

I just thought of this, so maybe I'm looking over something trivial.

Thanks!

It looks fine; whether you use the secret $S_0, S_1$ as the HMAC key, or whether you use the random value $r$ as the HMAC key; if $t' = t$, it implies that either $S_0 = S_1$, or we found a collision in the underlying hash function.

I would personally suggest you use $S_0, S_1$ as the key.  With HMAC, it doesn't really matter; however if we extend this to other Message Authenticate Codes, it does.  For example, if we were to use this idea to CMAC, well, if we're given the values $CMAC_r(S_0)$ and $r$, we can compute two plausible values of $S_0$ if it's at most 16 bytes long.  Using the secret values $S_0, S_1$ as the key prevents this; instead, you'll be relying on the security properties of the MAC.

One last note: this scheme also has a problem if $S_0, S_1$ has low entropy (that is, they appear in a dictionary that the attacker might have); in that case, an attacker can go through his dictionary, and check for matches.  If this is a concern, you'll see some type of password authenticated key exchange; they handle this case better (but they are also rather more complicated to implement)


estimate of time required to crack sha512crypt password with JtR + OpenCL OK, I have a shadow file with a password that I know, it is 4 letters followed by two numbers. Using John The Ripper with OpenCL support, on a laptop with AMD Radeon Mobility graphics, how long would it take to brute-force it? What speed should I expect?

The simplest and obvious solution is to just do it. JTR (or any decent password cracker) will show a realtime ETC and this is much better than speculating endlessly about hardware specifications.

But if you must, read on...

This is highly dependent on the number of iterations you used for the KDF. But you can calculate it easily. Suppose selecting one candidate and running it through sha512crypt takes time $t$.

Now there are 52 "letters" in the alphabet (I assume case matters) and 10 "numbers". So there are, in total, $52^4 \cdot 10^2 = 731161600$ candidates for your password.

Thus, on a single core, you will need $731161600 t$ units of time in the worst case to find your password. On average, it will take $\frac{731161600}{2} t$ units of time.

Now if you have $k$ different cores to work with, you will on average find the password after:

$$\frac{731161600}{2} \frac{t}{k} ~ ~ ~ ~ (\text{units of time} ~ t)$$

Let's plug in some numbers. A mainstream GPU has quite a lot of independent execution units, so let's say $k = 256$, a reasonable number. On the CPU, let's say you set up your KDF properly and it takes 0.1 seconds to compute it on the CPU. The GPU cores are slower individually, so let $t = 0.25 ~ \text{s}$.

$$\text{Average time to crack} = \frac{731161600}{2} \frac{0.25 ~ \text{s}}{256} = 357000 ~ \text{s}$$

Which comes out at around four days on average. In the worst case, it will take eight days.

Select $t$ and $k$ accordingly (I suspect in your case, your $k$ will be lower since you have a laptop graphics card, but your $t$ may also be lower). On specialized hardware, it would be faster, of course.

If worst comes to worst, you can always loan a few heavy-duty servers (or ask friends) and increase your $k$ value considerably, which can speed up the process quite a bit.

tl;dr it depends on how fast your GPU is, and how you configured your sha512crypt KDF. And if you have any additional information on the password (is the first letter a vowel, are the four letters a word, etc..) you can use this to set up rules in JTR to reduce the number of possible candidates.


Looking for encryption algorithm not subject to known-plaintext attack with IV reuse I've encountered an interesting problem where we can basically say the following:

We need to encrypt messages, but we have no room to store IVs. We can synthesize IVs; however an attacker would be able to observe different blocks encrypted with the same IV.
We can detect message tampering directly. That is, we don't have to care about somebody injecting blocks to change plaintext. They will be caught.
Large amounts of plaintext are known to any would-be attacker.

Are there any known block cipher secure against data-reading attacks with these constraints?

The problem comes in disk atomicity. 4096 bytes can be written atomically, 4096 + N bytes cannot be. Using simple sequential IVs was my plan, but someone seeing the disk twice would be able to exploit that.

Well, your requirements sound pretty much like standard disk encryption ones.

Assuming you can assign IDs (0,1,2...) to each 4kiB sector implicitely.In this case you could simply use XTS-mode of encryption using AES.
You'd then iterate through the 4kiB block using the inner counter and iterate through all sectors using the outer counter.

This should give you best possible security, as the same plaintexts are mapped to different ciphertexts (because of the counters) and there's no keystream to break.

I hope this is a solution to your problem.


If and why is it bad to scrypt a bcrypted password? This has been already brought up on security SE, but very sadly, this particular interesting issue got watered down in a far broader question.

If and why is it bad to use the following hashing algorithm to store passwords?

scrypt(bcrypt(password + salt))

The standard argument to questions like this, reiterated over and over on Cryptography.SE, Security.SE, and many other places in the Internet (1, 2, 3, 4, 5, 6, 7, 8 and many others) is as follows:

  You should use well-known, well-tested, public algorithms prepared by the world's best of the best cryptographers ONLY. You should use well-known, well-tested, public implementations of these algorithms ONLY. Home-brewing ANYTHING, however slight, is a Bad Thing ™, because frankly you are not competent enough to do this.

By this line of argumentation it is wrong to use scrypt(bcrypt(password + salt)) only because there is no such primitive provided out-of-the box by Oh Esteemed Experts. They only provide scrypt itself, or bcrypt itself, so we must stick to either; but joining them is a home-brew addition, so doing this is Evil.

This kind of argumentation besides, what are the particular evils of scrypting a bcrypted password? In this particular case, there are interesting arguments FOR doing this. Let me present a few arguments and counter-arguments

The primary argument for using this hash:

  Additionally, if someone figures out a more intelligent way to guess the original plaintext for one hashing algorithm, they probably won't simultaneously have a faster way for the other algorithm. Say people legitimately thought ROT13 was a good hashing mechanism. If I used ROT13(bcrypt(x)), wouldn't I still be better off when people 'cracked' ROT13?

Counter-argument, which I don't find very convincing:

  Another potential issue with combining bcrypt and scrypt like this is that there has been very little study into how the two interact. As such, we don't know if there are any weird cases that can cause problems. As a more obvious example, take the one time pad. We compute c=m^k for some message m and some equally long perfectly random key k, and we get perfect security. So let's do it twice, for even more security! That gives us c=m^k^k... oh, wait, that just gives us m. So because we didn't take the time to properly understand how the internals of the system worked, we ended up with a real security vulnerability. Obviously it's more complicated in the case of KDFs, but the same principle applies.

Counter-counter argument that seems to destroy the above one:

  You're doing it wrong. The bcrypt(scrypt(x)) stuff is ok while xor(xor(x,k),k) isn't because an extra bcrypt is something an attacker could do, too.

And also:

  I still don't see why the scrypt(bcrypt(x)) thing could be a problem. If the two interact weirdly, just using bcrypt doesn't make it more secure- an attacker can simply scrypt() what you've bcrypt()'d.

Counter-argument, which I don't find very convincing, because how many lines of code would this be?

  The primary issue is that you have to introduce more code to parse the encoded output of scrypt / bcrypt so that the salt and round count can be stored separately.

The only counter-argument that seems valid to my laymen eye, but still fails to invalidate the primary argument for this cipher:

  Using scrypt and bcrypt together has the problem that they both take time to run - you'll probably wind up halving the number of rounds on each to compensate for having to run both, which is more likely to be insecure than a "full" scrypt on top of a "full" bcrypt is.

So for the last time: Is it bad or good to do scrypt(bcrypt(password+salt)) and why exactly?

The combined strength of two key stretching algorithms is not greater than the sum of its parts. It is at best equal to the sum of its parts.

If you budget $x$ amount of CPU time to password stretching then you have to decide, do you give 100% of $x$ to scrypt? 100% to bcrypt? 50-50?

You can't give both 100% of $x$ to both scrypt and bcrypt because that's the same as doing a 50-50 split with double your initial time budget.

There is one important detail to scrypt that makes it better than bcrypt and PBKDF2. And that is that it is designed to use a lot of RAM. Storage with random access is hard to implement on ASICs in such a way that gives password crackers a significant advantage of the password-defender. The RAM use makes it hard to speed up cracking with GPUs as well.

Scrypt has a cost parameter. If you decrease it then it decreases both the amount of time that it uses and the amount of memory it uses. Bcrypt can be cracked faster than scrypt when scrypt is allowed high memory usage (and an equal amount of password-defender CPU time). So, when you take time (and thus memory) away from scrypt to give to bcrypt, you're letting a password cracker perform more guesses using less of their own resources.


NIST Diffie-Hellman prime: how was it picked? Where did it come from? According to this Matasano Crypto challenge, the NIST "likes" the following prime modulus, which appears to be expressed in hexadecimal:

  ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff

I have a few questions about it:

Is this number specified anywhere? I tried Googling it, both in decimal and in hexadecimal, hoping to find it somewhere, maybe in a NIST document, but I couldn't find it anywhere.
Why was this particular number picked? I know that Diffie-Hellman requires a prime modulus, and it should be big enough to prevent certain factoring attacks, and it should also be a safe prime, also to prevent certain factoring attacks, but there are lots of numbers with these properties. Was that number chosen somewhat arbitrarily, or were there any other criteria used to pick it?
Is this number used for anything other than Diffie-Hellman, like maybe RSA or elliptic curve algorithms?

Is this number specified anywhere?

It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC).  However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular.

  Why was this particular number picked?

Well, it's a safe prime; in addition, the leading 64 bits and the trailing 64 bits are all 1's; this makes certain operations somewhat more efficient.

The middle bits are (mostly) from the binary expansion of $\pi$; this was done to demonstrate that this number wasn't chosen with a secret weakness in mind; making this a 'nothing-up-my-sleeve' number.

The procedure used to select this number was created by Richard Schroeppel; the earliest reference I have for that is this RFC, appendix E

  Is this number used for anything other than Diffie-Hellman?

Not to my knowledge; as a well-known prime, it's not suitable for RSA, and it's too large to be really useful for elliptic curves.  And, as it doesn't have a moderate sized subgroup, it doesn't work well for DSA (as the signatures would be far larger than required).  It'd work for El Gamal and IES, however those are really Diffie-Hellman being reused in a public key encryption context.


Elliptic curve scalar point multiplication I need to compute ecc multiplication with this values : $ P=(1,3)\space ; \space k=2 \space ; \space a=24 \space ; \space b= 13 \space ;\space p=29 $ which means $y^{2}=x^{3}+24x+13 \space$. as far as I know in such situation one should compute values using this formula :

$
\lambda= \frac{3x^{2}+a}{2y}
$

$
x_r=\lambda^2 - 2x
$

$
y_r=\lambda(x-x_r) - y
$

when I calculate equation I end up $R=(18.25 , 6.375)$ where true answer of this shoud be $R=(11,10)$ (this site proves it : http://www.christelbach.com/eccalculator.aspx). please help me to find my calculation mistake.

  note : just if you are interested I'm using this matlab code :

   temp=(3*(x1^2)+a)/(2*y1);
   x3=mod(temp^2-x1-x2,n);
   y3=mod((x1-x3)*temp-y1,n);

For adding, subtracting, and multiplying modulo 29, you can just do the operation in the integers and take it modulo 29 (as you're already doing). To find $a/b$, however, you need to use the extended Euclidean algorithm to find the inverse of $b$ modulo 29, then compute $a \cdot b^{-1}$. This StackOverflow post has pseudocode for the extended Euclidean algorithm. Your mistake is trying to use ordinary division to compute temp.

Multiply $3x^2 + a$ by the inverse of $2y$ to compute temp in your code and you should be good, at least if your goal is to multiply $P$ by 2. If you want to add distinct points, you need to compute $\lambda$ with a different formula, but the rest is the same; if you want to multiply by something other than 2, you should implement something akin to exponentiation by squaring.


How to define the statistical distance between two functions? The statistical difference between two families of distributions of random variables:

  Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, the statistical difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as
  $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}} ( l )= \frac{1}{2}\sum_{s} \left\vert \Pr[X_{l} = s] - \Pr[Y_{l} = s] \right\vert$$

The computational difference between two families of distributions of random variables:

  Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as
  $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}}_{A} ( l )=\left\vert \Pr[s \leftarrow X_{l} : A \left( 1^{l}, s \right) = 1] - \Pr[s \leftarrow Y_{l} : A \left( 1^{l}, s \right) = 1] \right\vert$$

This notion can be used to define the PRGs.

The computational difference between two families of distributions of functions:

  Let $\mathrm{\mathbf{F}} = \{ F_{l} \}_{l}$ and $\mathrm{\mathbf{G}} = \{ G_{l} \}_{l}$ be two families of distributions of functions, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$ is defined as
  $$d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}}_{A} ( l )= \left\vert \Pr[f \leftarrow F_{l} : A^{f(\cdot)} \left( 1^{l} \right) = 1] - \Pr[g \leftarrow G_{l} : A^{g(\cdot)} \left( 1^{l} \right) = 1] \right\vert$$

This notion can be used to define the PRFs.

I am thinking that there should be a definition about the statistical difference between two families of distributions of functions. (It is denoted as $d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}} ( l )$).

There is a possible way:

For every input $x \in \{\ 0,1 \,\}^{*}$, let $F_{l} \left( x \right)$ denotes the distribution of $f(x)$ where $f \leftarrow F_{l}$.
Maybe one can use
$d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$
to define the statistical difference between $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$, where $\mathrm{\mathbf{F}}(x) = \{ F_{l}(x) \}_{l}$ and $\mathrm{\mathbf{G}}(x) = \{ G_{l}(x) \}_{l}$.

However, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ depends on both $x$ and $l$.
Thus, there exists a problem, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ may not be consistency for $x$. If I define
$$d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (l)
=\sup_{x \in \{\, 0,1 \,\}^{*}} d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)
=\sup_{x \in \{\, 0,1 \,\}^{*}}\frac{1}{2}\sum_{s} \left\vert \Pr[F_{l}(x) = s] - \Pr[G_{l}(x) = s] \right\vert$$
Then $d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (\cdot)$ may be not negligible even if for every $x$, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$ is negligible.

It can be seen that statistical difference is equivalent to computational difference if a PPT algorithm is replaced by a computationally unbounded one, i.e. an arbitrary function. For distributions of random variables, if $A(1^l,s)=1$ when $\Pr[X_l=s]>\Pr[Y_l=s]$ and $A(1^l,s)=0$ otherwise, then $d_A^{\mathbf X,\mathbf Y}(l)=d^{\mathbf X,\mathbf Y}(l)$, and this is the maximum for any $A$.

For functions, a similar argument can be used: a computationally unbounded algorithm can return $1$ on an arbitrary subset of functions, so it seems that the best choice would be to return $1$ for such $f$ that $\Pr[F_l=f]>\Pr[G_l=f]$. Then,
$$d^{\mathbf F,\mathbf G}(l)=d_A^{\mathbf F,\mathbf G}(l)=\frac12\sum\limits_f\lvert\Pr[F_l=f]-\Pr[G_l=f]\rvert.$$
Here, the sum is taken over all possible functions. This sum well-defined, because all summands are nonnegative.


Generalizing a CBC-MAC collision with a common final message block I found this question from a textbook but I don't really understand what it is asking:

Suppose $c$ is $1$ block long, $a$ and $b$ are strings that are a multiple of the block length, and $\text{CBC-MAC}(a||c) = \text{CBC-MAC}(b||c)$. An ideal block cipher is used in $\text{CBC-MAC}$.

Explain for which most general class of messages $d$,
$\text{CBC-MAC}(a||d) = \text{CBC-MAC}(b||d)$.

I don't understand how can $CBC-MAC(a||c) = CBC-MAC(b||c)$ unless $a = b$?

CBC-MAC is calculated by iterating a block cipher in CBC mode over the blocks of the message, using a start value of 0 - i.e. $CBC{-}MAC(a)$ is actually $CBC{-}MAC(0,a)$.

Since the first part of the messages (i.e. $a$,$b$) in your example have sizes that are multiples of the block length, the $CBC{-}MAC$ of each of them creates a chaining value that can be used as the input to $CBC{-}MAC$ of the second part of the message ($c$,any $d$)

For your example:

$CBC{-}MAC(a||c)$
$= CBC{-}MAC(0, a||c)$
$= CBC{-}MAC(CBC{-}MAC(0, a), c)$

So $CBC{-}MAC(a||c) = CBC{-}MAC(b||c)$ when $a = b$, but more generally when $CBC{-}MAC(a) = CBC{-}MAC(b)$

When this is true, it's easy to see that $CBC{-}MAC(a||d) = CBC{-}MAC(b||d)$ for all $d$.
i.e. once a collision is found with $CBC{-}MAC$ for two messages $a,b$ whose lengths are multiples of the block size, then the $CBC-MAC$ of $a||d,b||d$ will also be equal for all $d$.

I'm not sure why the exercise focuses on this property (except to illustrate what's obvious from the CBC basis of the design).


Connections between Instance Hiding and Fully Homomorphic Encryption Another approach taken by researchers for carrying out computations over encrypted data is Instance Hiding.

In brief, If a user wants to outsource the computation of a function for a particular input x (instance). She transforms the input x to an encrypted input y (thus hides it) in such a way that the server cannot infer x from y and sends to the server. The server computes the function on y and returns the result. (References below).

This is also called Encrypting Problem Instances. The functions that allow such transformations are called encryptable functions. These techniques argue that encryptabality is property of a function and not all functions can be encryptable.

If this is the case, it may contradict some results of Fully Homomorphic Encryption.
FHE tries to evaluate functions on encrypted inputs much generically.

Edit : in FHE, We transform the inputs (encrypt) them to cipher text which is then fed to say a function "add" carried out by server. Here add is generic function, does this mean add is encryptable function ?

I guess the catch is making assumptions on transformations

What is the catch here ? anybody ?

Refer :Abadi, Martin, Joan Feigenbaum, and Joe Kilian. "On hiding information from an oracle." Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 1987.

Here's what's common in both scenarios: Alice holds $x$ and wants to compute $f(x)$. A server Bob will help with the computation. Alice doesn't want Bob to learn $x$, so she sends some encoding of $x$ that hides $x$. Bob does some work and sends back a result from which Alice can infer $f(x)$.

The two settings differ on: (1) how Bob is allowed to help Alice with the computation, (2) what kind of guarantee Alice has about the privacy of her data $x$.

In the setting of the Abadi-Feigenbaum-Kilian paper, Bob must evaluate $f$ itself on the stuff that Alice sends to him. He is not allowed to compute some other thing related to $f$. This is quite a severe restriction! Also, this setting demands unconditional privacy against Bob.

In the setting of FHE, Bob doesn't literally perform the computation $f$ on what Alice sends him; rather, he performs the ``homomorphic evaluation of $f$ on a ciphertext.'' Also, Alice gets a privacy guarantee that is only computational.


Text partially decrypted regardless of IV I'm trying to work out which AES cipher is best to use.  I'm working with the OpenSSL ruby gem.

While testing the various options I noticed that most of the ciphers result in partial or even full decryption regardless of the IV value.

I'm just wondering if this is something I should be concerned about, or even if it is a bug that the gem maintainers should be aware of.

Eg: CBC, CFB8, CFB1, CFB, CBC-HMAC-SHA256, and CBC-HMAC-SHA1, only the first 16 bytes remain encrypted.

Eg: ECB allows full decryption regardless of IV

This is the ruby code I've used for testing.

ciphers = [
    'AES-256-CBC', 'AES-256-CTR', 'AES-256-XTS',
    'AES-256-OFB', 'AES-256-OCB', 'AES-256-ECB',
    'AES-256-CFB8', 'AES-256-CFB1', 'AES-256-CFB',
    'AES-256-CBC-HMAC-SHA256', 'AES-256-CBC-HMAC-SHA1',
  ]

def encrypt(plain_text, pwd, salt, cipher_name)
  cipher = OpenSSL::Cipher.new(cipher_name)
  cipher.encrypt
  cipher.random_iv # purposefully set to random
  cipher.key = OpenSSL::PKCS5.pbkdf2_hmac(pwd, salt, 20000, cipher.key_len, OpenSSL::Digest::SHA256.new)
  encrypted = cipher.update(plain_text)
  encrypted << cipher.final
end

def decrypt(encrypted, pwd, salt, cipher_name)
  cipher = OpenSSL::Cipher.new(cipher_name)
  cipher.decrypt
  cipher.random_iv # purposefully set to random
  cipher.key = OpenSSL::PKCS5.pbkdf2_hmac(pwd, salt, 20000, cipher.key_len, OpenSSL::Digest::SHA256.new)
  decrypted = cipher.update(encrypted)
  decrypted << cipher.final
end

ciphers.each do |cipher_name|
  pwd = 'some hopefully not to easily guessable password'
  salt = OpenSSL::Random.random_bytes(16)
  plain_text = "Spicy jalapeno tail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui."
  begin
    puts
    puts '== %s ==' % cipher_name
    encrypted = encrypt(plain_text, pwd, salt, cipher_name)
    puts decrypt(encrypted, pwd, salt, cipher_name)
  rescue => e
    puts e.message
  end
end

For those without ruby, this is the output of the above code:

== AES-256-CBC ==
��l�~��u@�=o� ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CTR ==
/&  q]$���{�YhwH�X*�N���.p�E�̕;�� 3|t�L
                                          v�'�﬉�T�KCأ���y�X���ՎR`/��]d`L�WI�"�?P���Ǖ�B|E�u5������Zq����LϠ�4

== AES-256-XTS ==
^��:ok
@6�4^O�cNJ��'�  C/ ���V�(�)k5��)��S
                                  ^�3���4�r��A���q�=����p�^�d3;�    �.U˕|k�U/�ʝ��y��qd�/���7HΒ����l�e

== AES-256-OFB ==
iH�"�=�tL�eG��Z~o
��moӦQ!��<z��vր2}�#6�
���%�oM��XI#y�t���($���"~

== AES-256-OCB ==

== AES-256-ECB ==
Spicy jalapeno tail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CFB8 ==
�xYa���ShR�
          ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CFB1 ==
+��g~ᲆ$e�
        ��ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CFB ==
���=�?)�2�96`�2�ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CBC-HMAC-SHA256 ==
_?��?���p��}ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

== AES-256-CBC-HMAC-SHA1 ==
[˲��H"`��.qv�ail ribeye dolore ut. Pork belly ut porchetta culpa aliquip brisket shank est. Pastrami ribeye porchetta cow qui.

You are actually not talking about "ciphers" but about "modes of operations".

ECB mode does not use the IV so its value is ignored when using that mode. It's a great example of reason why do we even use modes of operation. (ECB is the fastest mode of operation, but it's the least secure one) This is an .bmp image encrypted using ECB. (and then converted to .jpeg)

As you can see you can easily deduce what was on the original. Using a different mode of operation (CBC) it's usually much harder.

Now the image is indistinguishable from noise, but there is still some info that can leak. If someone encrypts the same image twice the ciphertext will be identical in both cases.

And this i the reason for random IV. Even if the image is identical, the different IV will cause the ciphertext to be completely different. This is useful for example when encrypting passwords. Two identical passwords should not be stored as two identical ciphertexts.

In conclusion the IV is not made for preventing decryption of the ciphertext. That's the job of the key. Random IV is used to prevent leaking of "metadata" when adversary can see only raw ciphertexts.

In most of the modes of operation (like CBC) the "current" block is obscured by connecting it somehow (usually by XOR) with previous blocks ciphertext.

This leaves the first block which has no predecessor with no obfuscation. This is where the IV comes into play. We add a fake "previous block" into the ciphertext. (IV is usually prepended to ciphertext and is immediately visible to adversary) When deciphering we actually use the IV only for that first block. To decipher any other block all you need is the key and previous ciphertext (which is also visible to the adversary)

When no IV is provided then the first block is getting decrypted into $Plaintext \oplus IV$, and since this block is usually predictable (like first characters of file header) this usually allows pretty easily to guess the IV.


C# implementation of curve25519 to ed25519 conversions WRT the selected answer here:
Can curve25519 keys be used with ed25519 keys?

Is there any c# implementation of this or equivalent?

Thanks.

In a Ref10 based implementation, the conversion should look something like this:

public static void EdwardsToMontgomeryX(out FieldElement montgomeryX, ref FieldElement edwardsY, ref FieldElement edwardsZ)
{
    // montgomeryX = (edwardsZ + edwardsY) / (edwardsZ - edwardsY)
    FieldElement tempX, tempZ;
    FieldOperations.fe_add(out tempX, ref edwardsZ, ref edwardsY);
    FieldOperations.fe_sub(out tempZ, ref edwardsZ, ref edwardsY);
    FieldOperations.fe_invert(out tempZ, ref tempZ);
    FieldOperations.fe_mul(out montgomeryX, ref tempX, ref tempZ);
}

public static void MontgomeryXToEdwards(out FieldElement edwardsY, ref FieldElement montgomeryX, ref FieldElement montgomeryZ)
{
    // edwardsY = (montgomeryX - montgomeryZ) / (montgomeryX + montgomeryZ)
    FieldElement tempY, tempZ;
    FieldOperations.fe_sub(out tempY, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_add(out tempZ, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_invert(out tempZ, ref tempZ);
    FieldOperations.fe_mul(out edwardsY, ref tempY, ref tempZ);
}

public static void EdwardsToMontgomery(ArraySegment<byte> montgomery, ArraySegment<byte> edwards)
{
    FieldElement edwardsY, edwardsZ, montgomeryX;
    FieldOperations.fe_frombytes(out edwardsY, edwards.Array, edwards.Offset);
    FieldOperations.fe_1(out edwardsZ);
    EdwardsToMontgomeryX(out montgomeryX, ref edwardsY, ref edwardsZ);
    FieldOperations.fe_tobytes(montgomery.Array, montgomery.Offset, ref montgomeryX);
    montgomery.Array[montgomery.Offset + 31] |= (byte)(edwards.Array[edwards.Offset + 31] & 0x80);// copy sign
}

public static void MontgomeryToEdwards(ArraySegment<byte> edwards, ArraySegment<byte> montgomery)
{
    FieldElement montgomeryX, montgomeryZ, edwardsY;
    FieldOperations.fe_frombytes(out montgomeryX, montgomery.Array, montgomery.Offset);
    FieldOperations.fe_1(out montgomeryZ);
    MontgomeryXToEdwards(out edwardsY, ref montgomeryX, ref montgomeryZ);
    FieldOperations.fe_tobytes(edwards.Array, edwards.Offset, ref edwardsY);
    edwards.Array[edwards.Offset + 31] |= (byte)(montgomery.Array[montgomery.Offset + 31] & 0x80);// copy sign
}

You should be able to use these together with my implementation at github.com/CodesInChaos/Chaos.NaCl. If all you need is crypto_box_beforenm except with a Ed25519 format key, you can simply use the existing Ed25519.KeyExchange method.

A few warnings:

I'm planning some breaking API changes
I'm not happy yet with the test coverage yet, so be careful
The Montogomery form Curve25519 functions don't ignore the last bit of the public key.

This means that you must manually mask out that bit via publicKey[31] &= 0x7F before passing it to MontgomeryCurve25519.KeyExchange. I will change this property with the next update of the library.
The key exchange functions hash their output, matching crypto_box_beforenm.


How does a salt get chosen? I feel like I am missing some information regarding salting.  How does one choose the salt? If you reuse the same salt for all passwords, can it just be figured out and then used in conjunction with normal brute-forcing.  And what are the common ways to generate the salt?

Salt is not secret. This is the open part of the encrypted data. It should be open to decrypt the data.

Reusing the salt is not good. The whole purpose of salt is to prevent usage of rainbow table. If an attacker has descrypted one text, it should not be easy to use it for other texts. Where as if you reuse the same salt for many texts, it may make sense for the attacker to create a rainbow table because he can then decrypt your multiple texts via the same rainbow table.

To your question, how salt is chosen: As @Swashbuckler said, it should be random. Important: Not once random, but it should be randomly generated for each your text or password.


Python. RSA common modulus attack problem I have:

N = /*500 decimal numbers*/

E1 = 3740453

E2 = 4226171

M^E1 = /*500 decimal numbers*/

M^E2 = /*500 decimal numbers*/

I must use RSA common modulus attack on it.

Using gmpy2.gcdext() i have:

a = 624366
b = -552607

So E1*a+E2*b == 1 is True.

Now i need to know M. For this i must to do follow things:

M = ((M^E1)^a) * ((M^E2)^b) #Just a formula...

In python 2.7 i do like that:

M = pow(ME1,a) * pow(ME2, b) #Where ME1 = M^E1, and ME2 = M^E2

And i have a problem here!
Function pow() can't work with negative "b".

How can i calculate last expression ?

I have solved this problem. @fgrieu  was right! Thanks for him and other!

Calculating modular inverse

if a < 0:
    _, eM1, __ = gmpy2.gcdext(eM1, N)
elif b < 0:
    _, eM2, __ = gmpy2.gcdext(eM2, N)

Calculating source message M

M1 = pow(eM1, abs(a), N) #I just realized, that always i need to use modulus pow(a,b,n)
M2 = pow(eM2, abs(b), N) #In this way all calculations are really fast!
M = (M1 * M2) % N # And final multiplication uses modulus same as previous expression


Difference between encryption and decryption for Feistel Cipher I have read that the only difference between enc and dec of a Feistel Cipher is the order of the subkeys. But on the following figure, the harves block are also inverted, no?

I don't understand why it doesn't count as a difference... To me, take the R block or the L block into the XOR has not the same effect.

You need to have another look at the picture. The output of the encryption process actually denotes $R_{n+1}$ on the left side and $L_{n+1}$ on the right side. And the input to the decryption function has the exact same order, so you don't have to swap anything manually, they are just 'labeled wrong'.

The reason here is that the last round is actually not exactly like the ones before, because it does not contain swapping the two halves. A more obvious way to express this would have been to do one final step like $L_{out} = R_{n+1}$, etc. and then start on the decryption with Left/Right labeling.

Also, I don't understand what they want to indicate by the green and red arrows. The coloring in both sides is either inconsistent or simply wrong. It also indicates that $n$ is an even number.


Homomorphic Encryption Notation Question What does the following notation mean in a homomorphic encryption scheme?

ENC(x;r)

What does x and r refer to?

x is the plaintext and r is the randomness.


Time cost of security reduction The following theorem is the description of one-more unforgeability in the paper lattice based blind signatures. I want to ask if the time $t^{'}$ is an exponential time since the $q_{H}$ and  $q_{Sign}$ are about $2^{60}$. If the time $t^{'}$ is an exponential time then the adversary acturally cannot solve the hard problem, namely there is no contradiction exist.

Theorem 3.8 (One-more unforgeability. Let $\text{Sign}$ be the signature oracle. Let $T_{\text{Sign}}$ and $T_\text{H}$ be the cost functions for simulating the oracles $\text{Sign}$ and $\text{H}$, and let $c \lt 1$ be the probability for a restart in the protocol. $\text{BS}$ is $(t, q_\text{Sign}, q_\text{H}, \delta)$-one-more unforgeable if $\text{com}$ is $(t', \delta / 2)$-binding and $Col(\mathcal{H}(\mathcal{R}, m), D)$ is $(t', \delta / 2)$-hard with $t' = t + q_{\text{H}}^{q_\text{Sign}}(q_\text{Sign}T_\text{Sign} + q_\text{H}T_\text{H})$ and non-negligible $\delta'$ if $\delta$ is non-negligible.

Even if $q_H$ and $q_{Sign}$ are $\mathsf{poly}(n)$, the security guarantees turn out meaningless since the loss is exponential in $q_{Sign}$. As the author points out in the paragraph (Page 18) following the proof of the theorem, $q_{Sign}$ has to be restricted to $o(n)$ so that security can be based on sub-exponential hardness of the underlying lattice problem.


Homomorphic Encryption for Deep Learning I'm interested in the two following processes:

Perform deep learning on homomorphic encrypted data

Perform deep learning predictions with a homomorphic encrypted model on unencrypted data. By this, I mean encrypting weights of a deep learning model, sending them to the data owner, and performing an encrypted prediction. The owner of the data will return me the encrypted prediction. See, for instance, this blog post for an example with logistic regression.
I'm wondering if it's possible to do deep learning (with many hidden layers) with PHE (partially homomorphic encryption, e.g., Paillier) or if I need a FHE (fully homomorphic encryption).

References are welcome!

There are very few (somewhat practical) results about homomorphic deep learning currently. As a good starting point, you might want to have a look at this recent paper from my former colleagues, and references therein. It focuses on optimizing lattice-based somewhat homomorphic encryption schemes, for evaluating deep neural networks.


Is there an asymetric encryption whos output size is quite equal to the input size I want to send a verifiable chunk of data (around 16 bytes) by simply encrypting it with a private RSA key, providing the public key in the source code for the verification. This was my initial thought. (I now know that this is not the same as signing the data, but this does not matter now.)
I tried RSA and ECC to determine that the length of the output data relies on the length of the keys. For this small amount of data, even the much smaller ECC keys produce a heavy amount of data overhead. So the question is: Are there any asymmetric encodings that don't have so much overhead, or is this per se impossible with asymmetric encryption/signing?
I found the possible solution of using message authentication codes. Still, I don't like that I have to provide the security with the software, which is (if I understand correctly) the case for every symmetric encryption. But maybe I'm wrong, and this is not such a big issue?

For ECC you are probably better off just using ECDSA or, if you're adventurous, the BLS signature scheme. ECDSA has a signature size / overhead of 4x the security strength (say 128 bit), or two times the key size (a 256 bit curve). BLS has a signature size / overhead of about three times the security strength (say 128 bit) or once the key size - it requires a larger key size of 381 bits to reach 128 bit security. So that's about 64 bytes for ECDSA (for a flat encoding without ASN.1 / DER overhead) and 48 bytes for BLS (currently the minimum recommended).

For RSA, see signatures giving (partial) message recovery. For message recovery schemes you will get at least 34 bytes of overhead (assuming SHA-256) - but that doesn't matter much because the minimal signature size is at least the same size as the RSA key size. A rather small key size of 2048 bits will therefore already give you 256 bytes for a signature that contains all the data.

Using a HMAC is only OK if you trust the other systems that get the key to keep the key secure & play fair (and there is of course the issue of establishing the key in the first place).

For many common runtimes / generic cryptography libs I'd only expect to find ECDSA and HMAC implementations.


what is SALSA20 Nonce and its requirements what is the source of nonce in SALSA20 algorithm.
basically who provides the value of nonce in SALSA20 algorithm

The treatment of nonces is the same for most stream ciphers, they only differ in length. In the case of Salsa20 the nonce is 64 bits, and there is a related cipher XSalsa20 which extends the nonce to 192 bits.

The caller/application provides the nonce. Typically the protocol or file format you're implementing specifies how to treat the nonce.

The essential property you need to ensure is that you never reuse a (key,nonce) pair.

Sometimes you use a counter, for example the message number in a network protocol. This counter can be used to prevent replay attacks.
Sometimes you use a random value which is convenient when you want to avoid state. But that requires XSalsa20 not Salsa20, since to be likely unique a random value should have 128 bits and Salsa20 only has a 64 bit nonce.

An addition warning if you're using the asymmetric box function: Both directions (A->B and B->A) generate the same XSalsa20 key so a nonce used in one direction must not be reused in the other direction. Typically that's achieved by either using different keys for both directions or by use non overlapping nonce spaces.


Why do we add error in the definition of LWE? One of the various equivalent definitions of the LWE problem is the following:
Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (usually a discrete Gaussian distribution) and $s$ a secret vector from $\mathbb{Z}_q^n$.
We denote $\mathcal{L}_{s,\chi}$ the probability distribution over $\mathbb{Z}_q^n \times \mathbb{Z}_q$ obtained by choosing $a \in \mathbb{Z}_q^n$ uniformly at random, choosing $e$ uniformly at random from $\chi$ and considering it in $\mathbb{Z}_q$, and calculating $(a,b=(\langle a,s\rangle + e)) \in \mathbb{Z}_q^n \times \mathbb{Z}_q$.
The Search Learning With Errors is to recover $s$ from samples $(a,b)$ obtained from $\mathcal{L}_{s,\chi}$.
My questions is why do we add the error $e$? I suppose that it is for security reasons. In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?
Since adding some error $e$ is a central block in a lot of lattice-based constructions, this could be a more general question. What is the point of adding this error?

In that case, how we would be able to obtain $s$ from $(a,b=(\langle a,s\rangle))$?

The operation $\langle a,s\rangle$ is a matrix multiplication, that is, completely linear, and hence Gaussian elimination allows us to recover $s$ efficiently.


How to implement oblivious transfer where probability of the receiver getting secret is exactly 1 out of 4? As we know that oblivious transfer is done with probability of 1 out of 2. But how to implement it with probability of 1 out of 3 or 1 out of 4??

I'll try to answer both your original question, and your question in the comment section.

The original definition of oblivious transfer is the following: a sender holds a message $m$ and interacts with the receiver. The receiver gets to know $m$ with probability $1/2$, without the sender being able to know whether the receiver learned $m$ or not. i'll call it "Rabin OT" to distinguish from the other definition.

Nowadays, the definition of oblivious transfer which is universally used is the following:
The sender S holds two messages $m_0$ and $m_1$
The receiver holds a selection bit $b \in \{0,1\}$
At the end of the oblivious transfer, the receiver learns $m_b$ (and does not learn anything about $m_{1-b}$) and the sender learns nothing (and in particular nothing about $b$).

This"classical" oblivious transfer easily allows to implement the Rabin OT: the sender holds $m$, picks a bit $x$ at random and sets $m_x \gets m$ and $m_{1-x} \gets r$ for a uniformly random value $r$. The receiver picks his selection bit $b$ at random. Then they perform a classical oblivious transfer; with probability $1/2$, the receiver learns $m$, else he learns a random $r$ (hence nothing). More generally, if you have a $1$-out-of-$N$ OT (where the sender holds $m_1, \cdots, m_N$ and the receiver an integer $i$ between $1$ and $N$ and gets to learn $m_i$), you can easily implement a Rabin OT with probability $1/N$.

Now, there are several ways to answer your question. If you are asking whether $1$-out-of-$2$ oblivious transfer can be used to implement other kinds of oblivious transfers, the answer is yes, as $1$-out-of-$2$ oblivious transfer can be used to implement any kind of two party functionalities (more formally, it implies general two-party computation, in the honest-but-curious model - but that's just to be a bit formal in my statement). But in practice, you will probabily not want to construct a $1$-out-of-$3$ oblivious transfer directly by calling "in black box" a $1$-out-of-$2$ oblivious transfer.

However, most known constructions of $1$-out-of-$2$ OTs do easily extend to $1$-out-of-$N$ OTs (see for example "Efficient Oblivious Transfer Protocols" by Naor and Pinkas).

Here is an example of such a protocol (taken from the article of Naor and Pinkas) :

We fix a group $\mathbb{G}$ in which the DDH problem is hard. Let $g$ be a generator of $\mathbb{G}$. We also have access to a hash function $H()$ which is seen as a random oracle.

The sender has an input $M_0, \cdots, M_{N-1}$. He picks random group elements $C_1, \cdots, C_{N-1}$, a random exponent $r$, and computes $g^r$. He sends $C_1, \cdots, C_{N-1}, g^r$ to the receiver.

The receiver has a selection integer $j \in \{0, \cdots, N-1\}$; he picks a random exponent $k$ and sets pk$_j \gets g^k$. If $k \neq 0$, the receiver also computes pk$_0 \gets C_j/\text{pk}_j$. He sends pk$_0$ to the sender.

The sender computes $\text{pk}_0^r$ and for $i=1$ to $N-1$, $\text{pk}_i^r = C_i^r/\text{pk}_0^r$. Then, he picks a random $R$ and sends for all $i$ the value $E_i \gets H(\text{pk}_i^r,R,i) \oplus M_i$ ($\oplus$ is the xor) to the receiver, together with $R$.

As he knows $k$, the receiver can compute $(g^r)^k = \text{pk}_j^r$, hence he can compute $H(\text{pk}_j^r,R,j)$ by himself, and therefore recover $M_j$. One can show that if $H()$ acts as a random oracle and the DDH assumption holds, he cannot learn anything else on the other inputs of the sender.


Do companies like CipherCloud really have the option to use homomorphic encryption? I was reading How is CipherCloud doing homomorphic encryption? and was wondering:

Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)? Furthermore, can it be done without requiring that the third party SaaS app be modified?

I believe is not completely possible because of the use of “Top n” functions (e.g. customer charts) and the common use of the SQL distinct keyword.

For example, suppose the application uses the top 10 customers (global sales) this month. For the DB query it would imply something like select top 10 customerField from sales order by orderTotalField desc. Issue here is that 2+ different customerFields can be the same customer if we use HE, and that would result in incorrect values, maybe not even 10 different customers.

Let me elaborate a little more: HE Database has a table with 3 fields customerName, dailySales and date. John is the customer with most sales but has, say, 8 HE equivalent values. The application ask for the top ten sales, by customer, by year. The query is then, Select cutomerName, sum(dailySales), Year(date) from datatable group by customerName, Year(date) order by Sum(dailySales) descending. As you see, the database needs to group in this case depending on sales for each customerName, and will fail for this example. Hope I'm clear here to establish the problem with HE in first instance.

What do you think, do they have a choice? If so, please elaborate :)

Is there a technically feasible way for companies like CipherCloud to use homomorphic encryption (HE) while preserving full functionality in a third party SaaS app (e.g. Salesforce)?

Fully homomorphic encryption can theoretically1 compute any function. Therefore, if a computer can perform a task on plaintexts, then fully homomorphic encryption could theoretically be used to perform that exact same task on ciphertexts.

It seems like your doubt stems from an equality check. From your example, you seem to believe that because there are say two rows in the database that belong to the same user, that FHE would not be able to combine the sales amounts of those two rows. In other words, how would FHE know that the two encrypted customerName values are the same?

The answer is, the FHE computation wouldn't need to know that the two customerName values are the same. Instead, it would compute an encrypted bit. If they are the same, the encrypted bit encrypts 1, else it encrypts 0. This is a very feasible computation with FHE. Once it knows that bit, it would sum in the bit times the dailySales value. Thus, if the bit is 1, the dailySales value is added in. If the bit is 0, the dailySales value is not added in (since 0 times anything is 0).

Thus, given your table, say you want to know the top 1 customer. Presumably you have a table of encrypted customerName values. For each encrypted customerName value, you'd step through every entry in the sales table, computing the bit for that row, then adding in the bit times the dailySales value for that row. You'd save the result along with the customerName value. Once you've done that for every possible customerName, you'd use FHE to find the one with the largest encrypted sum, and return that to the user. The user could then decrypt the values and learn who was the top customer.

This is a good example of how, yes, FHE allows you to compute any function, but the method of doing it sometimes requires some tricks.

  Furthermore, can it be done without requiring that the third party SaaS app be modified?

In general I would expect that the answer is no, w/o modification it could not be done. There are maybe a few corner/special cases where it could possibly.

For example, if dailySales value in the database is an int32, then an encrypted version will definitely not fit in the int32 slot. In which case the DB would have to be modified. If, however, the DB had originally been setup to store everything as, say, an unlimited size string, then FHE encrypted values could be encoded as a string (pick your favorite method) then stored that way.

The client software would either have to do the encryption itself, or a proxy could be used. So in that sense, the client would likely have to be modified (at least to point to the proxy). Let's assume you use a proxy. The client sends the entry to the proxy, the proxy encrypts it and submits it to the SaaS app.

The proxy would also have to be smart enough to translate queries. For example a query for the top customer would not be able to be run directly on the SaaS app. Instead the proxy would have to translate it into a query for the entire table, then run the process I described previously.

The proxy would only know the customer's public key, so the proxy couldn't return the plaintext answer. The customer would receive an encrypted answer to the query which it would have to decrypt.

I imagine this would be the process that would have to be done.

Note, the client doesn't really have to send FHE encrypted values to the proxy. The client could encrypt the values with AES, then send the AES key encrypted with the FHE public key. The proxy uses that encrypted key to homomorphically decrypt the values. The output is the user's values encrypted with FHE. Using this technique, the client would have to do very little FHE encrypting.

1. I say theoretically as FHE is still not practical today.


How to find q in a corrupted ECDSA signauture I'm doing exam papers for a crypto exam and I've been given a corrupted ECDSA signature. I'm asked to check if the signature is valid (which I know how to do), however, the q value is corrupted and so I can't actually check the signature. Any ideas on how i'd find the value of q?

Curve, E = y^2 = x^3 + 2x + 2

Field size, p = 17

q = 1~ (where tilda stands for the corrupted value)

Base Point, P = (5, 1)

Public key, y = (0, 6)

h(M) = 26

(r, s) = (9, 17)

First note that this is essentially the same problem as if you just generated the curve parameters and now wanted to find out the order, so we can use the same strategies as for that case here:

Ask a tool like sagemath: EllipticCurve(GF(17),[2,2]).cardinality() which constructs an elliptic curve over $\mathbb F_{17}$ with $a=2,b=2$ and finds out its cardinality which is $q=19$. This is the easisest way.
Calculate it yourself using Schoof's algorithm. Of course this is an $\mathcal O(\log^5 p)$ algorithm, so it will be quite tiresome to execute by hand, especially for small values. But for large curves it is the way to go.
Guess it using the Hasse-Bound. Essentially you want to solve the discrete logarithm $q\cdot P=\mathcal O$ (with $\mathcal O$ being the additive neutral element). Now you can use standard discrete-logarithm finding techniques, such as plain brute-force or BSGS to find it and also use the constrain that the Hasse-Bound gives you: $|p+1-q|\leq 2\sqrt p$, so $q\in[p+1-2\sqrt p, p+1+2\sqrt p]$ or in your concrete case: $q\in [17+1-2\cdot 5,17+1+2\cdot 5]=[8,28]$. So you would e.g. start with $8P$ and check if that's $\mathcal O$ and if not proceed to $8P+P=9P$ until you find the index that yields you $\mathcal O$ which is the order of $P$ (and in this case also the order of the curve because the curve order is prime).


Does side-channel attacks offer any difficulty to Stinson's concept of `provable security'? Here's a quote from Douglas Stinson:

  “[i]f a cryptosystem can be ‘broken’ in some specific way, then it
  would be possible to efficiently solve some well-studied problem that
  is thought to be difficult. For example, it may be possible to prove a
  statement of the type “a given cryptosystem is secure if a given
  integer n cannot be factored.” [...] [B]ut it must be understood that
  this approach only provides a proof of security relative to some other
  problem, not an absolute proof of security. This is a similar
  situation to proving that a problem is NP-complete [...].”

Source: Stinson, D. R. (2006). Cryptography, Theory and Practice. Chapman
and Hall, CRC, 3rd edition. Chapter 2, section 2.1, page 45.

Say there is a proof that a cryptosystem $X$ satisfies Stinson's definition.  An attacker builds a method to break $X$ by side-channel attacks.  Does that offer any trouble to the definition or to my proof?  Or would you say side-channel attacks have nothing to do with provable security?

Say there is a proof that a cryptosystem X satisfies Stinson's definition. An attacker builds a method to break X by side-channel attacks. Does that offer any trouble to the definition or to my proof?

Not generally: The proof covers the algorithm, and side channel attacks target the implementation.

If someone threatens to hurt you unless (or until) you give them your private key, that doesn't violate the provable security claim of the algorithm.

The algorithm is an abstract idea, and the provable security guarantee would indicate that no other abstract idea (algorithm) could violate the security without providing a solution to another abstract problem.

  Or would you say side-channel attacks have nothing to do with provable security?

More or less, yes; You can't have provable security against rubber hose cryptanalysis, you can't provide security if the attacker is watching over your shoulder as you perform the algorithm with pencil and paper, you can't have security if your program prints it's state at every step of the way to a log file the adversary has access to, etc.

Basically

Proofs rest on assumptions (even if they're not stated explicitly). If you violate those assumptions, then you can skirt around the guarantees provided by the proof.

This is one reason why provably secure algorithms would ideally be combined with side channel resistant techniques (e.g. constant time code, blinding, etc) and formally verified implementations.


Verify the discrete log of ECDSA is in range Is it possible to verify the discrete log in elliptic curve is within range without uncovering it? I need to verify that $x$ is within $1$, $2^{64}$ for $xG=P$.

If you give an attacker $G$ and $P := xG$ with $0<x<2^{64}$ then she can calculate a table with $2^{32}$ entries $yG$ for $0\le y<2^{32}$. Finding for any $0\le z<2^{32}$ the value $P-(z\cdot 2^{32}\cdot G)$ in the table yields $x = y + z\cdot 2^{32}$. Space complexity is $2^{32}$ entries and time complexity $\le\log_2(2^{32})\cdot 2^{32}$.

That's why user679128 uses a blinding scalar $b$.


Designing of Password Authenticated Key Exchange (PAKE) Schemes? I am started working in post quantum cryptography(lattice based cryptography) specifically in Password Authenticated Key Exchange (PAKE). I come across many PAKE key exchange scheme (like this one) that do not take in consideration the registration process and login process. These schemes simply assumes that two parties are sharing some secret password of low entropy  and based on that they will generate common session key. So, my question regarding PAKE techniques are

  What is the scope of PAKE schemes? Is Registration or Login process should not be considered while designing the PAKE key Exchange schemes?

The definition of PAKE just suggests that one or more parties are exchanging keys with knowledge of a shared password that authenticates the exchanged key. There are definitely use-cases of PAKEs that extend beyond, say, a web application authentication process that requires registration. For example, there could exist two or more embedded systems with shared passwords built into the firmware during manufacturing but these systems want to exchange fresh keys for communication. There are PAKEs that do cover registration (e.g. SRP), but the "definition" of a PAKE does not really require a specification for a registration process.

Personally, I think PAKE authors should specify a password bootstrapping process, if possible! It could prevent implementors from rolling-their-own protocol extensions.


Data switching on one time pad and Data leakage Assume all the values and operations defined over $\mathbb{F}_p$.
For the sake of simplicity assume all the values are non-zero. Let $(-r)$ denote additive inverse of value $r$.

We have one fixed value $a$. we compute $v_1=a+r_1$ and $v_2=(-r_1)+r_2$, where $r_i$ are picked uniformly at random from the field.

We give $v_1$ and $v_2$ to a semi-honest adversary and ask him to do:

$v_1+v_2=a+r_2$

Question: Given $v_1$ and $v_2$ can the adversary learn anything about $a$ in above scenario (when it performs modular addition operation)?

This is just a blown up version of the OTP.

$v_1$ is basically just the normal OTP: To decrypt, it is enough to know $r_1$

And then you give the adversary just another random value: If $r_2$ is drawn uniformly and $r_1$ is fixed, $v_2$ has the very same distribution as $r_2$ itself. Essentially, you are using another OTP to encrypt the key of the first OTP (the minus sign does not change anything)

So in the end, if you transmit both $v_1$ and $v_2$, you just doubled the size of the message. And you have doubled the key size, and key management is the major drawback of OTP. Decryption is possible with knowledge of either $r_1$ (directly) or $r_2$ (indirectly, getting $r_1$ from $v_2$).

This construction can easily be turned into an attacker on OTP and vice versa, so the security is basically the same. But this is only true if you actually use OTP with true random keys. In a stream cipher construction (which people wrongfully call OTP sometimes), the situation might be entirely different, and from intuition I would say it would weaken the security.


"SHA-256" vs "any 256 bits of SHA-512", which is more secure? In terms of security strength, Is there any difference in using the SHA-256 algorithm vs using any random 256 bits of the output of the SHA-512 algorithm?

Similarly, what is the security difference between using SHA-224 and using any random 224 bits of the SHA-256 output?

SHA-512 truncated to 256 bits is as safe as SHA-256 as far as we know. The NIST did basically that with SHA-512/256 introduced March 2012 in FIPS 180-4 (because it is faster than SHA-256 when implemented in software on many 64-bit CPUs). SHA-224 is just as safe as using 224 bits of SHA-256, because that's basically how SHA-224 is constructed. What bits are kept (provided that's fixed) is immaterial to security, but for compliance to NIST specification, the left bits shall be kept.

As stated in this other answer, in the general case of a hash function only assumed to be collision-resistant or preimage-resistant, restricting its output can make it entirely insecure. A trivial example is the 512-bit function obtained by appending 256 zeros to the output of SHA-256, which is both collision-resistant and preimage-resistant, but trivially insecure when restricted to its 256 right bits.
The stated design goal of SHA-2 functions are preimage-resistance and collision-resistance: "The hash algorithms specified in this Standard are called secure because, for a given algorithm, it is computationally infeasible 1) to find a message that corresponds to a given message digest, or 2) to find two different messages that produce the same message digest". Therefore, truncation of SHA-2 functions is not playing by the book.
Update: FIPS 180-4, which defines SHA-2 functions SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 and SHA-512/256, explicitly endorses truncation in its section 7: "Some application may require a hash function with a message digest length different than those provided by the hash functions in this Standard. In such cases, a truncated message digest may be used, whereby a hash function with a larger message digest length is applied to the data to be hashed, and the resulting message digest is truncated by selecting an appropriate number of the leftmost bits".
Truncation of SHA-2 functions is safe as far as we know. That's the very principle used to construct SHA-224 from a slight variant of SHA-256, as well as SHA-384, SHA-512/224, and SHA-512/256 from a slight variant of SHA-512 (the variant being to change the internal initialization vector, in order to avoid that the output of one function reveals bits of the output of another one).
The reason why SHA-2 functions can be safely truncated is that these functions have another unstated design goal, that they reach as far as we know, which is: being computationally indistinguishable from a random function, except for having the length-extension property¹ and being that particular function. That strong property is necessary to be able to use the hash with confidence in proofs of protocols made in the Random Oracle Model, and implies collision-resistance and preimage-resistance (the reverse is not true). Truncation (by keeping any fixed subset of their output bits) of a function indistinguishable from a random function also is indistinguishable from a random function (proof sketch: any hypothetical distinguisher for the truncated function is easily converted into a distinguisher for the original function, with the same effort and advantage).
The principle can be extended to any size; e.g. SHA-512 truncated to 128 bits is, as far as we know, as fine a 128-bit hash as can be (regardless of which bits we keep), and unquestionably much preferable security-wise to MD5 (another 128-bit hash, which collision resistance is badly broken). However, collision for an $n$-bit hash can be found in about $2^{(n/2)+0.33}$ hashes, little memory, and efficient parallelization (see Parallel Collision Search with Cryptanalytic Applications). Hence for 80-bit level security (which has sometime been considered an absolute minimum in the early 2000s, and is to be considered insufficient nowadays absent argument of the contrary), when collision resistance is necessary, we should keep at least 160 bits; and when only preimage-resistance is necessary, we should keep at least 80 bits.

¹ The length-extension property is that given the bitstring $H(m)$, the bit length $\ell$ of bitstring $m$ (but not $m$ itself), and any bitstring $s$, it's possible to efficiently compute $H(m\mathbin\|r_\ell\mathbin\|s)$ where $r_\ell$ is a short, efficiently computed bitstring depending only on $\ell$. Truncation of many bits removes the length-extension property. As noted in this other answer, the length-extension property is an undesired artifact, and the basis of attacks in some contexts; and SHA-512 truncated to 256 bits is safe in such contexts, when as SHA-256 is not.


Is it possible to encrypt data points but still be able to select the ones "near" a given value? We have an application where we would like to store "encrypted" data points (as in, not being able to know the original - plaintext - data just by looking at the stored - encrypted - version of it) but still be able to ask the running system for all data points up to a certain distance from a given point. We don't want to decrypt the whole dataset and compute distances on plaintext data, of course. On the other hand, we don't even need a way to actually decrypt data and get back at the original data points.

Practical monodimensional example:

let A=2, B=5, C=8 (numbers are our "plaintext", letters are just identifiers)
we store encrypted versions of the data, so if you stole our persistent storage you know we have three points A, B, C but you can't know they actually have values 2, 5, 8
we want to ask the system for "all data points up to a distance of 3 starting from an origin point = 6" and the answer should be [B, C]
we won't ever need to be able to go back from A,B,C to 2,5,8
ideally this should be possible to extend to n dimensions, or at least two or three dimensions

About the purpose: improve security of our system in case of any successful attack. We don't need to actually know that data (as long as we can compute which data points are inside a maximum distance from a given, known point) but it's also not a problem if we do know them. What we're trying to improve on is what data an attacker would have access to if he ever succeed in compromising our systems (either getting copies of data at rest on persistent storage - a simple disk encryption would take care of that - or by getting access to an actually running system).

Speed is not a problem, we're not in an hurry. We want to minimize as much as possible the cleartext we have on the running system.
Ideally: receive data, encrypt and store it, forget about cleartext and do not need to see it again to compute its distance from a center point.

Is there any technique that allows that? Is it even theoretically  possible?

No, a cryptosystem can't do what's asked.

Proof: if one can precisely answer queries of the form "how many data points up to a distance of $3$ starting from an origin point = $n$" (a subset of what's wanted) for any value of $n$ with $|n|\le m+3$, and each point has integer value $v$ with $|v|\le m$, then one can find exactly the value of all the points in the set with at most $2m+1$ queries (with $n$ going from $m+3$ down to $-m+3$, each revealing if $v=n-3$ belongs to the set).

Thus in order to make the problem in the question tractable, one must use much larger integers (so that the necessary number of queries or work becomes infeasible), or/and heavily limit the number of queries an adversary can make, or/and introduce some fuzziness in the answers, or/and (as pointed by otus in comment) introduce the notion that some of the query is sent somewhat "enciphered" to the holder of the database. And it might well be that no practical system is possible.


Weird exam question about RSA and Chunksize I'm studing RSA theory, and I've a question about an exercise of an exam of the past year...

The image below is a question for past year's exam. Is a True/False answer.

A and B for me are clear. A is True, whereas B is False.

But the problem comes with C and D. The bit representative of a 1357 modulus is 10.4 bits. Theoretically I would say that the Input blocksize (m) should be small than n (modulus). So 10 bit chunksize as input should be correct, as 11 bit input is exceeds 10.4 bit and the input cannot be larger than the modulus (two different values will give the same encrypted result)

But the problem is the output. As the modulus is 10.4 the output is required to be 11 bit... because c= m^e mod n being m=10bit but n=10.4 bit will result in (at least) C=10.4 bit (should be coded as 11 bit)

So the problem arises at the decryption... makes no sense to decrypt 11 bit, that should be splitted to 10 bit + 1bit+padding... and this, for me doesn't give the original result.

As I've always understood that Input and Output sizes MUST be equal.

On the exam I would anser T F but C and D I would leave them in blank.

Any of you have a different interpretation of this situation?

Thanks in advanced!

Here's how I would interpret these two questions:

(C): if we are restricted to encrypting plaintexts that are bitvectors of a specific length, is 10 bits the largest bitvector Alice can encode (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?

(D): if we are restricted to encoding ciphertexts as bitvectors of a specific length, is 11 bits the smallest bitvector Alice can produce (using Bob's public key), without causing any decryption failures when Bob needs to decrypt?


best padding scheme for RSA So i came across three padding scheme for RSA: PKCS1, PSS and OAEP.
My intention here is to encrypt a file using AES key. then, encrypt the AES key with
the RSA key and save the encrypted AES key along with the encrypted file.
My question is which one of the padding schemes above best suits my purpose.
Needless to say security is top priority for me and using compromised algorithm is off the table.
Thanks in advance

PKCS#1 contains 4 padding schemes, of which only 2 are suitable for encryption, but only of small data blocks (like up to hundred bytes): the modern RSAES-OAEP, and the obsolete RSAES-PKCS1-v1_5 (which drawbacks include being harder to guard against decryption oracle attacks on the padding). PSS, aka RSASSA-PSS, is strictly for signature.
For comfortable security, AES-GCM-SIV with a random 256-bit key encrypted per RSA-4096 using RSAES-OAEP with SHA-512 and MGF1 using SHA-512, would tick all the boxes (on crypto algorithm choices, ignoring implementation isssues) except resistance to hypothetical quantum computers usable for cryptanalysis. The modern baseline would be RSA-2048 using RSAES-OAEP with SHA-256 and MGF1 using SHA-256.


How does Naver Line PC client obtain private key for end-to-end encryption (letter-sealing)? When I download Naver Line PC client onto my PC, a six-digit number will be shown on the PC client for me to enter the number into my Line app on my mobile phone for decrypting the old and new messages. Once I do so, I can receive and send messages to any other endpoints.

How does Naver Line send my private key stored on my phone to the PC client?

Converting a lengthy comment exchange to an answer:

  How does Naver Line send my private key stored on my phone to the PC client?

LINE has provided a technical whitepaper which described how message end-to-end encryption was done.  https://scdn.line-apps.com/stf/linecorp/en/csr/line-encryption-whitepaper-ver1.0.pdf  Since that whitepaper provides technical details about the communication protocols and encryption algorithms integrated into LINE’s messaging and VoIP platform, and since repeating what they wrote in their whitepaper doesn't make sense, I just have to ask: What information within that PDF didn't you understand? Why doesn't their own information satisfy your needs?

  The whitepaper does not explain how the PC client obtains the private key from the mobile device. Please suggest if you find it in the whitepaper

What you describe in your Q (a code that shows on PC which you have to enter on mobile) is verifying your identity on the PC version of LINE.

Your PC version then gets all the needed data via their servers. As the PDF explains on page 11 (4.2.1) In order to be able to send encrypted messages, each LINE client application generates a Letter Sealing ECDH key pair, and saves it securely in the application’s private storage….

So, your PC doesn't simply get your mobile keys and use those — it uses it's own keys to securely exchange data (incl. what's needed to decrypt other encrypted messages).

Since your question describes the authentication/authorisation process of setting up a new client device, and since the "keys" part you ask about is described in their PDF, it's pretty unclear to me what exactly you're asking since everything you mention is already be covered by their whitepaper (as well as their website, which contains the same infos using layman's terminology).

  Are you saying that the the private key on my phone is not private as Line can retrieve it for purposes or Line keeps my private key on Line server for their future use. This is not E2EE from my point of view and contradicts to the information on whitepaper on page 16.

No, I'm saying that they use your individual device's keys to securely exchange secrets from device to device (… as the whitepaper explains).

Mobile = keypair 1, PC = keypair 2, etc. Using those public key encryption keys, it's very well possible to exchange secrets (like private keys) between your devices in a secure E2E manner. In case of doubt, read up on how public key encryption works.

  Line PC could sync previous messages from mobile device even when the mobile is offline. It can’t be done by using different keys

Because those encrypted messages are stored on their servers.

Note that while you enter the PC authorisation/authentication code (they call it "verification code") into mobile, you not only authorize your PC but are also online — which is a perfect time to sync keys between devices, so that you can read your older messages on your new device.

Once this initial key sync is done (should take not more than a few KBs, so it's done in a few secs while you're authorizing your new device), you are able to read all old messages on your new device even when all your other devices are offline from that moment on.

Actually, that's similar to how 99.999% of the secure E2E messaging apps do it when they offer multi-device access to old/stored encrypted messages stored on a 3rd-party server.

Besides all that, of should be noted you're asking about (what they call) "Letter Sealing", which  uses unique, user-specific encryption keys which allow users to safely and securely send messages to one another. Their user-account specific keys are more restricted (according to their website) which is one of the reasons their help center mentions Can I use the same account on more than one device? With the smartphone version of LINE, the same account cannot be used on multiple devices. Only one phone number or email address can be used to verify one account per device. If you register the same phone number on a different device, the account on your previous device will automatically be deleted and you will no longer be able to use it. You can use the same account on the PC and iPad versions of LINE by logging in with the same email address.

Now, please don't get me wrong, but it may be advisable for you to read up on how public key encryption generally works, before diving into things which might be hard to grasp when not knowing which practical solutions public key encryption can offer in alike scenarios.

Nota Bene: This answer is solely based on the PDF documentation and website information which has been made available to the general public by the specific messaging service provider. The answer is not meant to indicate or imply a full-fledged assessment of theoretical and/or practical security. The answer should therefore not be interpreted or referred to as such a security assessment.


SPI security of FE1 scheme I have a question about security of FE1(Page 16-18) in paper "format preserving encryption". Can anyone explain me, why we are allowed to replace PRF with random function in security proof? And also, why is game $G_0$  the same as game $SPI_1$ (explained in page 6) and is game $G_1$  the same as game $SPI_0$?

why we are allowed to replace PRF with random function in security proof?

That's just how security proofs for these kinds of Feistel schemes work - you say something about the cipher when the round function is a truly random function, then you argue that because a PRF is indistinguishable from a random function for a computational adversary, the security proof still holds when your round function is a PRF. I think they use this technique in the original Luby-Rackoff paper, too.


How to break a columnar transposition cipher? I'm currently studying for a cryptography exam. I've been given ciphertext that has been encrypted by a columnar transposition cipher. I've been given no shift key length or key word, the only thing I know is that only 2 columns have been shifted.

How can I determine the key? Or better yet, is there another way to decipher the ciphertext?

(Although your question is for a long time ago) Transposition ciphers don't change the frequency of letters in their ciphertexts. So, you can implement a frequency attack. For decryption by this you only need the table of frequency of English letters and your ciphertext.
(Your encryption scheme here is a Columnar transposition with a key that all its letters are in order except 2 of them.)


Understanding Hash function notations I am implementing a Certificateless Cryptography Algorithm by referencing the paper An Efficient Certificateless Encryption for Secure Data Sharing in Public Clouds. In this paper on page no. 4 during setup phase they have mentioned to choose hash functions (in my case it's SHA-256). But some of the notations are confusing me.

  Choose Cryptographic Hash functions :

  $H_1 : \{0,1\}^* \times Z_p^*  {\rightarrow} Z_q^*\\ H_2 : \{0,1\}^*
 \times Z_p^* \times Z_p^* {\rightarrow} Z_q^*\\ H_3 : \{0,1\}^* {\rightarrow}
Z_q^*\\ H_4 : Z_p^* {\rightarrow} \{0,1\}^{n + k_0}\\ H_5 : Z_p^*
 {\rightarrow} \{0,1\}^{n + k_0}\\ H_6 : Z_p^* \times \{0,1\}^{n + k_0}
 \times Z_p^* {\rightarrow} Z_q^* $

  where $n$, $k_0$ are the bit-length of a plaintext and a random bit
  string, respectively.

Can any one please explain me how do I interpret above hash functions. I have one more doubts in this algorithm,

Correct me if I am wrong
 $x$$H_1$ $(ID_A,w_0)$ means $x \times H_1(ID_A) \oplus H_1(w_0)$ where $x \in Z_q^*$

Or it has another meaning?

So let's start with the hash functions:

$$H_n:A\times B\times C \rightarrow D$$ is the mathematican's notion for a function called $H_n$ that takes arguments from the sets $A,B,C$ (in this order) and maps it to $D$, where $B,C$ are optional. You're facing three types of sets for this:

$\{0,1\}^*$ is the set of binary bit-strings of arbitrary size, e.g. any data that can be represented as a sequence of bits
$\{0,1\}^{n+k_0}$ is the set of binary bit-strings of length $n+k_0$, e.g. any data that is exactly $n+k_0$ bits long.
$\mathbb Z_q^*$ and $\mathbb Z^*_p$ are the sets of all natural numbers smaller than $q$ and $p$ respectively.

The tricky part is instantiating these functions now. You can instantiante them using KDF2 (combined with optional concatenation) and / or using HKDF or HMAC which can all be based off SHA-256.

The input is quite simple: You just feed the data (in the appropriate representation) into the KDFs and you're done.
The binary output is also simple: The KDFs can produce arbitrary-sized outputs and you truncate what is too much (they usually run in some sort of CTR-mode internally).
The really tricky part is converting the binary hash string to an integer. The best you can do is to generate a string a little bit longer (a few bits) than what is needed for the modular reduction and then apply the modular reduction (e.g. $\bmod q$) to the converted integers. This should give a "good-enough" distribution

  Correct me if I am wrong $x$$H_1$ $(ID_A,w_0)$ means $x \times
 H_1(ID_A) \oplus H_1(w_0)$ where $x \in Z_q^*$

No, you're supposed to take it literally. You call $H_1(ID_A,w_0)$ and multiply the result (which is in $\mathbb Z^*_q$ by definition) with $x$ which is also chosen from $\mathbb Z^*_q$, e.g. $x\times H_1(ID_A,w_0) \bmod q$.


DES F function never injective? Now i know that the F function doesn't have to be injective, but is it NEVER injective? or is it possible to have an injective F function?

There is nothing that stops a Feistel cipher from having injective Sboxes.

One could remove the $32$ to $48$ bit expansion map $E$ in the DES $F-$function and have an injective Sbox layer made up of $4\times4$ Sboxes and thus an injective $F-$ function for a modified DES. It would need round keys of $32$ bits and thus use less randomness and be weaker.

Also, there are many Feistel and generalized Feistel ciphers out there, including AES finalists MARS and RC5. Studying them may help you understand $F-$ function design better.