Proof of encrypted content I would like to create a server that would verify a public/private key pair where the private key is encrypted with a key unknown to the server.

The server should reject the keypair if the encrypted content is not the private key belonging to the public key.

Is there a way to cryptographically prove that the content of the encrypted data is the correct private key without the server having any way of decrypting the key?

A signature using the private key, sent along the keypair, to be verified with the public key is not enough since the client could send correctly signed garbage data instead of the private key and the signature would still be valid .

Can this be done?

In general, there is a way: you can prove the statement you sketch using zero-knowledge proofs. Due to [1] we know that zero-knowledge proofs for any language in NP exist. Let us write down what you want to prove as an NP language $L$. Therefore let $\sf (sk, pk)$ be the key pair, consisting of a secret key $\sf sk$ and a public key $\sf pk$, and let $\sf pk'$ be the public encryption key (corresponding to some secret decryption key $\sf sk'$) used to encrypt $\sf sk$ so that $C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)$, i.e., the ciphertext $C$ contains an encryption of $\sf sk$ under public encryption key $\sf pk'$ and $\rho$ denotes the randomness used upon encryption. In addition we may assume without loss of generality that there exists an efficient algorithm $\sf VKey$ which takes as input a key pair $\sf (sk, pk)$, and outputs $1$ whenever $\sf sk$ is the key corresponding to $\sf pk$ and $0$ otherwise. Now we can write down $L$ as follows:
$$
L = \{ ({\sf pk'}, C, {\sf pk}) ~|~ \exists~({\sf sk}, \rho) : {\sf VKey}({\sf sk},{\sf pk}) = 1 ~\land~ C = {\sf Enc}({\sf pk'}, {\sf sk};~\rho)\},
$$
Clearly, if we know $({\sf sk}, \rho)$ corresponding to a tuple $({\sf pk'}, C, {\sf pk})$ we can efficiently verify membership in $L$. Therefore $L$ is indeed an NP language.

Efficient instantiations?

Regarding efficient instantiations one needs to be careful, as the most efficient approach no longer allows to obtain $\sf sk$ upon decryption but only $\sf pk$. In particular, assume that we have some group $\mathbb{G}$ of prime order $p$ generated by $g$ where we assume the decisional Diffie-Hellman assumption to hold. Now assume we use some scheme where the $\sf sk$ is a random element in $\mathbb{Z}_p$ and the corresponding public key is its "image" in the group with respect to $g$, i.e., ${\sf pk} = g^{\sf sk}$. Additionally assume that we choose to use exponential ElGamal in $\mathbb{G}$ as encryption scheme, (i.e., ${\sf Enc}({\sf pk}', {\sf sk}) := (g^r, {\sf pk}'^r \cdot g^{\sf sk})$ for some uniformly random $r$ in $\mathbb{Z}_p)$. Now, one may observe that we can no longer efficiently obtain $\sf sk$ upon decryption but only $\sf pk$. However, if your use case does not require to be able to recover $\sf sk$ upon decryption the aformentioned instantiation is very efficient: one can make use of $\Sigma$-protocols (see, e.g., [2]).

If your use case also requires to be able to efficiently recover $\sf sk$ upon decryption, you will require more costly zero knowledge proofs: for example encrypting a bit-wise representation of the key and proving the statement with respect to this bit-wise representation of the key, or to use Paillier as an encryption scheme, which however may require zero-knowledge proofs over groups of different orders (see e.g., [3]).

Instantiations using a symmetric encryption scheme?

In case you want to use a symmetric encryption scheme things will get a lot more expensive as this would require to prove statements over general circuits and also to somehow make the link to the algebraic setting where the keypair $({\sf sk}, {\sf pk})$ lives in. You could have a look at this paper [4] to find out more about how this could be instantiated.

Also note that, in contrast to asymmetric encryption schemes, symmetric encryption schemes are typically not binding. Thus such an instantiation will require some additional measures to ensure that the encryption key you use to prove the statement is indeed the key it should be.

Bottomline

I think that using an asymmetric encryption scheme will be preferable in practice - if your use case allows it at all. Even if one might have to do ZK proofs over groups of different orders this will be much more efficient and much simpler to implement compared to using a symmetric encryption scheme.

References

[1] http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

[2] http://www.cs.au.dk/~ivan/Sigma.pdf

[3] https://pdfs.semanticscholar.org/ad71/f5dcef871bdfaad01be9da6d378b010b36d4.pdf

[4] https://eprint.iacr.org/2016/583.pdf


Is there a crypto function that would take 1 second to run? Short version of the question: what if we encrypt or decrypt by running SHA-256 one million times repeatedly, beginning with the initial "phrase" or "object", so that the operation can take 1 second, won't take prevent hacker's brute-force attempts?

Details:
If the system has an encrypt and decrypt system that would first SHA-256 "abcde" first, and then SHA-256 on that result, for 1 million times, to see if the result matches with the stored encrypted-one-million-time token, then the hacker can try the system beginning with "aaaa" but not practical to try it until "zzzz", even if the password is just 4 characters long (such as a password for the PC or Mac).
I think one way hackers try to hack into a computer or system is that they just try most popular passwords or just passwords starting with a to z, aa to zz, ..., aaaa to zzzz.
So then, if the crypto function is designed to take at least 1 second to finish, won't that stop that brute-force attempt?
Otherwise, the hacker can try 500,000 possibility per second, and it doesn't take much effort.  Some system actually stops for 1 second between attempt (such as Unix login prompt), but it doesn't stop it if it is not through some UI interface for that 1 second delay.

The are already many solutions for this. See for instance Argon2, Lyra2, scrypt.
They allow you to tune the number of iterations so that it takes needed time on particular device (CPU, GPU) to compute a hash.


What does the running transcript hash in RFC-8446: TLS 1.3 do? From RFC8446:
In general, implementations can implement the transcript by keeping a
running transcript hash value based on the negotiated hash.  Note,
however, that subsequent post-handshake authentications do not
include each other, just the messages through the end of the main
handshake.
Could someone explain what it means by by keeping a
running transcript hash value ?
I want to implement TLS1.3 on a microcontroller where RAM is limited. For example if I have to calculate HMAC of a message 1000 bytes long, is it possible to calculate first a HMAC of first half of the message, delete the fist half of the message and calculate the final HMAC from the first HMAC and the remaining half of the message ?

What's keeping a running transcript hash value ?

It means keeping the internal state of the hash in-between processing pieces of the message hashed. Virtually all hashes are designed to make this easy, for the benefit of devices with limited RAM. They can hash large messages piece by piece, with a three-function interface Start/Hash/Finalize allowing to repeat the Hash step as needed, passing a piece of the message at each call.
Such implementations of SHA-256 keep a state that comprises:

the hash so far (32 bytes)
the input buffer (64 bytes) holding 0 to 511 bits of input data not hashed yet
the length so far (8 bytes), which also encodes how much data was hashed (multiple of 512 bit) plus how much data is in the input buffer.

is it possible to calculate first a HMAC of first half of the message, delete the fist half of the message and calculate the final HMAC from the first HMAC and the remaining half of the message ?

Essentially yes, except that what's calculated first is not "a HMAC of first half of the message". Computing $\operatorname{HMAC}(K,(M_0\mathbin\|M_1),\ell)$ with $\operatorname{SHA-256}$ when $M_0$ and $M_1$ are available sequentially can go:

Check $0\le\ell\le64$ (the output length, here assumed in bytes)
if $K$ is more than 64 bytes, then $B\gets\operatorname{SHA-256}(K)$, else $B\gets K$
expand $B$ to 64 bytes by appending zeroes
$B\gets B\oplus\mathsf{3636\ldots3636_h}$ (the ipad constant, over 64 bytes)
Perform the first hash

Start
Hash $B$
Hash $M_0$
Hash $M_1$
Finalize the hash, yielding $H_1$

$B\gets B\oplus\mathsf{6A6A\ldots6A6A_h}$ (the XOR of the ipad and opad constants, over 64 bytes)
Perform the second hash

Start
Hash $B$
Hash $H_1$
Finalize the hash, yielding $H_2$

Truncate $H_2$ to length $\ell$ as needed to obtain the final result.

Between steps 3 and 4 of the first hash, it is needed a state of only about 168 bytes of data, including 104 bytes for the the hash state, and 64 bytes for $B$.
For SHA-512, we need to change the 64 to 128, and the RAM needed doubles.


All generators for modulo p so I have to find all generators for modulo p. And I thought: isn't there are rule for it? As far as I remember, every number from {1,...,p-1} is a generator because p is a prime. Is that true? Or am I mistaken? What is the rule called?

Or how else do you find generator elements quickly? Do you really have to take each and every element and modulo it with p and figuring out if it returns all numbers n for 0 > n < p-1?

This is not true. In particular, consider $4\in (\mathbb{Z}/5\mathbb{Z})^\times$. We have that $4^2 = 16\equiv 1\bmod 5$, so $\langle 4\rangle = \{1, 4\}$ is not the full group.

The theorem you mention is known as Fermat's little theorem, and it states:

  $\forall x\in (\mathbb{Z}/p\mathbb{Z})^\times$, $x^{p-1}\equiv 1\bmod p$

As you mention, all elements satisfy this. Generators are distinguished in that they satisfy this, but for all $k < p-1$ they satisfy $g^k\not\equiv 1\bmod p$ (so $p-1$ is the "smallest exponent" such that $g^{p-1}\equiv 1\bmod p$). As a hint, you don't need to check all $k < p-1$ (and you can in fact check a single $k < p-1$ which will work in all cases).


How can we add real values using GF field? In GF($2^4$) usinfg primitive polynomial g(x) = $x^4 + x^3 +1$,
2+3 = 1 since 010 + 011 = 001,

2 + 2 = 0

Is there any encoding to get 2 + 3 = 5 and 2 + 2 = 4 in GF.

As stated by CodesInChaos in comment, what's asked can't be done with the same $+$ operation for the binary field $\operatorname{GF}(2^4)$ and the desired $+$ operation for common integers. Proof: in $\operatorname{GF}(2^4)$, $a+a=b+b$ for any $a$ and $b$, and that does not hold for any useful subset of integers.

However, we can map the elements of $\operatorname{GF}(2^4)$ less zero (0000) to $\{0,1,2\dots,13,14\}=\mathbb Z_{15}$, with multiplication in $\operatorname{GF}(2^4)$ mapping to addition modulo $15$ in $\mathbb Z_{15}$ . We take any generator $g$ of $\operatorname{GF}(2^4)$, e.g. 0010; map 0001 to $0$,  $g=$0010 to $1$, $g^2=$0100 to $2$, $g^3$=1000 to $3$, $g^4$=1001 to $4$, and more generally $g^n$ to $n$.

Now, the operation in $\mathbb Z_{15}$ defined by getting back to $\operatorname{GF}(2^4)$ per the inverse of the above mapping on both arguments, multiplying the results in $\operatorname{GF}(2^4)$ , and getting to $\mathbb Z_{15}$ again by applying said mapping, is simply addition modulo $15$, and thus works as asked for small non-negative integer values.

Analogy: we can perform addition in the set $\mathbb R$ (the reals) as $x+y=\log(e^x\times e^y)$.


How to determine if $\{n \cdot g^a \mod P\}$ and $\{m \cdot g^a \mod P\}$ generate the same sets? (set size < $P-1$) given some examples $k_{n_i},k_{m_i}$ out  of each value set:
$k_{n_i} \in \{n \cdot g^a \mod P\, \forall a \in \mathbb{N}<P\}=G_m$
$k_{m_i} \in \{m \cdot g^a \mod P, \forall a \in \mathbb{N}<P\}=G_n$

Each set has size of $S$ which is a prime and known. Value $P$ is also a prime with $P = 2 \cdot S \cdot f+1$. Factor $f$ is (product of) prime(s) which is known as well. The Generator $g$ is known too. For a given $k$ the factors $n,m$ and related exponent $a$ is unknown.

As shown here for each $k$ multiple value pairs $(n,a)$ can be computed very fast (pick an $a$ and compute $n=kg^{-a} \mod P$). That means those sets can be equal with $n\not=m$.
Now is there a way to check if they generate the same sets (without computing all combinations?)

$G_n = G_m$ iff $n^S \equiv m^S \pmod P$

Proof:

If $n^S \not\equiv m^S \pmod P$, then $\forall e \in G_n : e^S = n^S$ (as $e^S = n^S \cdot (g^a)^s = n^S$); and similarly $\forall f \in G_m : f^S = m^S$.  Hence $\forall e \in G_n, f \in G_m: e \ne f$, and hence $G_n \ne G_m$ (and actually the two sets are disjoint).

Other direction (needed because we're asserting equivalence):

If $n^S \equiv m^S \pmod P$, then $(nm^{-1})^S = 1$, that is $nm^{-1}$ is in the subgroup generated by $g$, that is, $g^c = nm^{-1}$ for some integer $c$.

Then, for any member $e \in G_n$, we have $e = n \cdot g^a$ (for some $a$); we have $n \cdot g^a = n \cdot g^{-c} \cdot g^{a+c} = n \cdot n^{-1}m \cdot g^{a+c} = m \cdot g^{a+c}$, and hence $e \in G_m$.  Similarly, we can show that all elements $f \in G_m$ are also in $G_n$ and hence $G_n = G_m$

Extra credit for the reader: find the step where I implicitly assumed that $P$ was prime...


Should I be concerned about padding oracle attacks if the lifespan of my key is ~1 minute? I'm using 4096-bit RSA to encrypt a 256-bit AES key generated client-side.  The RSA ciphertext is then sent to the server, and the server decrypts the RSA ciphertext to acquire the AES key.  Information is then exchanged between the server and client using the AES key in CBC mode.

I generate a unique IV using a secure RNG for each message and send it with the AES ciphertext.

I am aware of three weaknesses to this system so far:

An attacker gains access to a client system and manages to adjust the RSA public key.  As far as I am concerned, if an attacker has access to a client system, I have bigger problems to deal with anyway.
Anyone can communicate with my server provided they have my RSA public key.  Again, not too worried about this, as a password is required to be sent to the server before it will perform any operations on behalf of the client.  If a password is leaked, once more, I have bigger problems to deal with.
A Padding Oracle attack due to my use of CBC Cipher Mode, so:

The exchange of keys and commands between client and server will last, at most, around 1 minute.  Normally this time period is far less.  Since the AES key that is used exists for such a short period of time, and given that it is not stored anywhere other than in memory, is it possible for a padding oracle attack to crack the key?

A Padding Oracle attack due to my use of CBC Cipher Mode

CBC in and of itself does not directly result in a padding oracle. It is when you abuse the padding after decryption to decide whether or not decryption was successful and then communicate (maybe not even directly) the results of that padding check.

Based on your comment that

  The connection is terminated and the key discarded as soon as decryption fails.

it sounds like you are likely using a padding check to determine whether or not decryption has failed. If that is incorrect let me know.

Should you be worried about this?

Definitely. The fact that your keys are short lived perhaps makes it so that the current incarnation of your software is not exploitable (I'm not convinced that it isn't exploitable), but it is vulnerable at the very least. What happens when you are no longer available (say left the company this code is written for or stop working on the open source project this code is written for) and someone else changes the keying requirements. They may very easily change them in such a way that the software is now exploitable since the vulnerability has persisted.

In our world, it is much better to just fix the problem and not let it turn into something that can be exploited down the road.

How can you fix it?

The best approach is to use message authentication codes. I suggest you read Should we MAC then encrypt or encrypt then MAC. Basically, you can either switch to an authenticated encryption mode (look at your crypto library to see what is supported) or add a MAC after encrypting with CBC using HMAC. Please read Why can't I use the same key for encryption and MAC? while you are at it.


Why do wireless keyboards only use 128-bit AES? Why not 256? I've looked for 256-bit AES encrypted wireless keyboards, and apparently they don't exist. Can anybody explain why this is from a cryptographic point of view?

Why wouldn't they just opt-in to the highest standard of encryption, instead of settling for the runner-up? Is there any cryptographic (or closely related) reason why industrial producers might have decided to use AES-128 instead of AES-256?

AES-256 isn't "better" than AES-128 in any practical sense. A crack of AES-128 will almost certainly bring down AES-256 anyway, and there's no practical difference between 128-bit keys and 256-bit keys — nobody will crack a 128-bit key in the future of humanity as a species.

On the other hand, AES-256 likely requires more power draw than AES-128 for this piece of hardware. I'll take an extra hour of battery life over a meaningless difference in security. Hell, I'd take an extra five minutes of battery life.


Galois Field multiplication instead of Diffie Hellmans discrete logarithm I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I understand that it is somewhat easy to factorize if one omits the division by an irreducible polynomial.

I cannot find any comparison for the hardness of

multiplicative inverse in GF(2^n) mod (some irreducible polynomial)
Diffie Hellman using exponents of g^x mod p
elliptic curves

Only for the last two I was able to find some comparison which favors elliptic curves over the discrete logarithm problem as the key length is about 1/12 as opposed to Diffie Hellman for the same security.

The inverse is easy, it can be done by the extended Euclidean algorithm, thus polynomial in complexity compared to the others which are exponential.


Secret modular exponentiation with chosen modulus Let $e$ be a secret value and $n$ a public 2048-bit RSA modulus.
Consider the RSA encryption under the key $(e, n)$ with unknown $e$.

The goal is to decrypt a given ciphertext $c=m^e \pmod{n}$ to recover $m$.

The adversary is assumed to have oracle access to:

the encryption function $x\mapsto x^e\pmod{n}$ for chosen $x$.
the function $x\mapsto x^e\pmod{n'}$ for chosen $x$ and $n'$.

Is it possible to recover the following values

$m$ ?
$e$ ?
$d = e^{-1}\pmod{\varphi(n)}$ ?

Is it possible to recover the following values
$\cdot$ e

Yes, using the oracle access 2.
He can pick values $x$ and $n'$ which have small orders (and computing such values for arbitrary orders can be done efficiently [1]).  If he selects a value $x, n'$ such that $x$ has order $q$ and learn $x^e \bmod n'$, he can recover the value $e \bmod q$ in $O(\sqrt q)$ time.
So, he learns $e \bmod q_1$, $e \bmod q_2$, …, $e \bmod q_n$ are a large number of distinct small primes $q_1, q_2, …, q_n$; he then can compute the value $e \bmod q_1q_2...q_n$; if the number of small primes is sufficient, this is the value $e$

$\cdot$ m
$\cdot$ d

No; oracle 2 is of no further use (as we have recovered all the secrets it holds), and oracle 1 is the standard RSA oracle; neither the plaintext nor the private key is recoverable.
[1] Here is an efficient way to generate a pair $x, n'$ such that $x$ has order $q$

Find a prime of the form $n' = qs + 1$, for some integer $s$, and which is the size you're looking form.

Select an arbitrary value $r$, and compute $x = r^s \bmod n'$

If $x = 1$ or $x = 0$, go back to step2

[Needed only if $q$ is not prime] for every prime factor $t$ of $q$, verify that $x^{q/t} \ne 1 \pmod {n'}$; if $x^{q/t} = 1 \pmod{n'}$ for any prime factor $t$, then go back to step 2.

TA-DA!  You're done; the order of $x$ modulo $n'$ is $q$; that is, $x^q = 1 \bmod{n'}$ and $x^i \ne 1 \bmod{n'}$ for all $i \in [1,...,q-1]$


What is meant by encrypting/decrypting a known plaintext/ciphertext with every possible key in meet-in-the-middle? I am working on the Meet-in-the-middle attack on 2DES and I have got some questions I am not sure about. I read several websites/articles about it so I have got an idea of what it is and how it works. However, I do not fully understand what is meant by every possible key.

Let me give an example:

I have a known plaintext, which I encrypt with 2DES - My key only has 20 effective bits of the 64 bits. So, the 20 bits are set as the high order and the rest is padded with zeros (have skipped over all parity bits). This gives me a ciphertext, which is encrypted twice with two different keys. So, when I want to perform a MITM attack on it, I have to encrypt the known plaintext with every possible key (= 2^20) and store the results i.e. the intermediate cipher and the key used in a, let's say, a HashMap where the input is  - The Hash key is not an integer.

Next, I have to decrypt the known ciphertext with every possible key and find a match between the decrypted cipher text and one of the encrypted plaintexts in the HashMap.

What confuses me here is what is meant by "every possible key"? Are 2^20 keys generated with random 20 bits (in my case)? If so, this would result in collisions.

Your question has given to you only 20-bit key space so, you can achieve it. As mentioned earlier, even storing one full table is not an easy job and accessing $2^{56}$,too, although we know that Titan can reach $2^{62}$ around one hour, it is a supercomputer. Your task simply says that your key will be in the format in binary case as:

xxxxxxxpxxxxxxxpxxxxxx0p0000000p0000000p0000000p0000000p0000000p

so you have to iterate for x's from

0000000p0000000p0000000p0000000p0000000p0000000p0000000p0000000p

to

1111111p1111111p1111110p0000000p0000000p0000000p0000000p0000000p

and store them in a table T1 ( or hash map). (There are 64-bit over there). The p represents the parity bits.

From Wikipedia:

  Initially, 56 bits of the key are selected from the initial 64 by Permuted Choice 1 (PC-1)—the remaining eight bits are either discarded or used as parity check bits

In the next step, use the same iteration for the decryption and look for the result in T1.


What is the key derivation function used in GnuPG, and how long may its input be? I am currently working with GnuPG on a new project of mine. It would be very useful to know two things for that, which are not described in the manual:

What is the maximum input size of a symmetric key in GnuPG?
What key derivation function does GnuPG use?

What is the maximum input size of a symmetric key for GnuPG?

The key size of the symmetric key is defined by the cipher and is derived from a passphrase using OpenPGP's string to key function. The standard does not define a maximum input length, and I'm not aware of a limitation in GnuPG (but did not look up in the source code). Be aware that providing a passphrase as input to the string to key function longer than the symmetric key (ie., having more entropy than the symmetric key) does not increase security any more.

  What key derivation function does GnuPG use?

OpenPGP calls the key derivation function "string to key function", which is defined in RFC 4880, OpenPGP, String-to-Key (S2K) Specifiers. It boils down to applying a hash function on the passphrase and optionally a salt, usually those get concatenated for a number of iterations to increase the workload for brute force attacks.


How to generate new LWE samples Assume we are given a small fixed number of LWE samples with secret $s$ and error $e$, where the error distribution is taken so that the LWE problem is hard.

My question: How can one further generate LWE samples (with the same secret $s$), given the LWE samples.

It was briefly noted in [Reg10] (Sec2. "Other implications") that there exists such a procedure, however I was not able to find an explicit explanation (or in the references they suggested).

[Remark] It wouldn't be surprising that we can further generate LWE samples on our own, since the hardness of the LWE problem does not depend on the number of samples (when the error distribution is Gaussian).

The basic idea is to take random (Gaussian) integer combinations of the given LWE samples, and add a little "smoothing" noise.  This will result in new samples which are statistically close to LWE samples with the same secret, but with a somewhat wider error distribution (by a factor of $\tilde{O}(\sqrt{n})$ for typical parameters). This is essentially Regev's classical BDD-to-LWE reduction on the special family of Ajtai lattices.

More precisely, given LWE samples grouped as $(\mathbf{A} \in \mathbb{Z}_q^{n \times m}, \mathbf{b}^t = \mathbf{s}^t \mathbf{A} + \mathbf{e}^t)$ where $m \approx n \log q$, generate a new sample as $(\mathbf{a}' = \mathbf{A} \cdot \mathbf{r} \in \mathbb{Z}_q^n, b' = \mathbf{b}^t \cdot \mathbf{r} + \tilde{e} \in \mathbb{Z}_q)$, where $\mathbf{r} \in \mathbb{Z}^m$ and $\tilde{e} \in \mathbb{Z}$ have discrete Gaussian distributions of appropriate parameters.  One can show that with high probability over the choice of the original $(\mathbf{A}, \mathbf{b})$, the distribution of $\mathbf{a}'$ is nearly uniform.  Moreover, conditioned on any fixed choice of $\mathbf{a}'$, the distribution of $\mathbf{e}^t \cdot \mathbf{r} + \tilde{e}$ (which is the "error" term in the output sample) is close to a discrete Gaussian.

This procedure is sketched in Gentry-Peikert-Vaikuntanathan, "Trapdoors for Hard Lattices..." (for the tight security proof of the IBE), and is done more formally in Applebaum-Cash-Peikert-Sahai, "Fast Cryptographic Primitives..." (as the encryption algorithm for the KDM-secure public-key scheme).


How are IVs used in association with RSA Encryption? How are IVs used in association with RSA Encryption?

Can someone explain why we use them in this RSA context?

IV is not commonly used in RSA Encryption.

Do you mean:

AES Encryption? AES Encryption in some modes, for instance CBC or CFB uses IV (Initial Vector), which is (often) unpredictable value that never repeats for the same key. It is fairly common to generate IV randomly
Random padding in RSA Encryption? There are several padding mechanisms defined for RSA Encryption, including e.g. PKCS#1v1.5 padding and OAEP. In RSA encryption, parts of the padding commonly are random, just like some IV's used for symmetric encryption.

In case you are thinking of RSA Encryption padding where IV is actually used, please, provide name of the padding scheme in the question.


Honest Verifier Zero-Knowledge Game for Sigma Protocols I am looking for how an adversary to special HVZK would work. In Boneh and Shoup's book (BonehShoup) they have Attack Game 20.4 for special cHVZK.
Here, the adversary produces a pair (x,y) (witness and statement) and sends it to their challenger, who either uses P and V or Sim to produce the transcript.

Can I modify this game in the following ways?

Can the adversary generate the challenge?
Can I have the adversary ask on polynomially many challenges instead of just one? Why is he limited to a single output here?

This question requires clarifications regarding the definition of special computational Honest-Verifier-Zero-Knowledge (Special cHVZK) as introduced in the linked material by Boneh and Shoup:

  Can the adversary generate the challenge c of the transcript in Special cHVZK?

No, because this is meant to be a definition for a version of honest-verifier zero-knowledge, therefore challenges must be uniformly random and cannot be chosen by the adversary.

  Can the adversary ask the transcript for polynomially many challenge instead of just one?

Well, that is the definition. If you allow the adversary to ask transcripts of polynomially many challenges, then it is easy to see that you will end up with an equivalent definition. So in theory, you could allow the adversary to ask the transcript of polynomially-many challenges.


Physical analogue for MACs What would be a good analogue with which to describe Message Authentication Codes to a person who has little to no understanding of cryptography?

For instance, a vault is a reasonable analogue for symmetric authenticated encryption: anyone with the key can open the vault and inspect, alter, or replace the contents. Without the key, you can't know or manipulate what's inside. Similarly, a royal wax seal is an okay one for digital signatures: anyone can validate that a message originated from the person with that particular stamp with assurances that the message hasn't been altered since the envelope was sealed.

Is there a good physical example of something with similar semantics to MACs?

Just thinking out loud here:

Take a picture of the contents of a box.
Put these pictures in a safe.
Ship box and safe together, lock with key of sender.
Receiver unlocks safe, compares pictures with contents of box.

The safe and keys are already common for symmetric encryption too.


Why is the complexity of RSA-1024 80 bit and not 86 bit? Why is the complexity of RSA-1024 80 bit and not 86.76611925028119 bit?

  Here is the complexity for the GNFS (pulled from the linked Wikipedia
  article):

  $$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$

  where $n$ is a number to factor. Evaluating the above expression at
  $2^b$ is a rough approximation of the the time needed to factor a
  $b$-bit integer. Here's a table showing the bit-length of the
  evaluation at $2^{1024},2^{2048},\dots$:

Strength  RSA modulus size   Complexity bit-length
  80        1024              86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

Security strength of RSA in relation with the modulus size

PS: Why is there an 'o(1)' in the formula? And why does it say RSA modolus size? Shouldn't it be RSA key size instead?

Presumably, it's because they rounded it down to a nice round number of bits.  Nobody's going to use an 86.76611925028119 bit key in practice, but an 80-bit key is plausible.

Besides, the 86.whatever bit symmetric key length is only approximate, anyway: even using the GNFS, implementation details could easily swing it several bits either way, and of course, if someone finds a better algorithm to attack RSA then all bets are off.  All we can really say with any confidence is that, using the best algorithms publicly known today, cracking a 1024-bit RSA key is about as hard as cracking an 80 to 90 bit symmetric (e.g. AES) key.  Which is a pretty wide margin (adding 10 bits to the symmetric key length makes it about 1000 times harder to crack), but that just reflects how hard it is to estimate these things.

Actually, I think Reid already answered the first part of your question pretty well in his comment, so let me just quote him here:

  "First, directly evaluating asymptotic expressions is quite imprecise. But more importantly, the NIST is an administrative organization, and their purpose in that table was to define a set of key sizes for various primitives that give a specific level of security. The intent is that you might decide 112 bits of security is enough for your application, then use the key sizes/algorithms suggested in the table. So they picked commonly-used key sizes that were slightly above the desired security level. The extra margin also gives you a bit of leeway in terms of Moore's law."

As for your other questions, the $o(1)$ in the complexity formula for GNFS that you quoted is little-o notation.  Basically, it means that there's an unknown term there that tends to zero as $n$ tends to infinity.  Of course, the little-o notation, on its own, doesn't really tell us anything about how big the unknown term might be for any given finite value of $n$, but in practice, we may generally assume it to be negligible.

(Actually, the $o(1)$ term doesn't seem to appear in the reference cited by the Wikipedia article for the formula.  It might just be a mistake in Wikipedia.  Looking at the edit history of the article, it seems to have been inserted in this edit, which removed an earlier $O(\cdot)$ from around the entire expression.)

As for why it says "modulus size" instead of "key size", you're right that those two terms are often used interchangeably for RSA.  However, technically, an RSA key consists of two parts: the modulus $n = pq$ (which is common to the public and private keys) and either the public exponent $e$ or the private exponent $d \equiv e^{-1} \bmod n$.  Using the word "modulus" instead of "key" makes it clear that we don't want to include the length of those exponents (since they don't affect the difficulty of factoring the modulus) in the number, even though they're technically part of the key.


OpenSSL RSA same plaintext but different ciphertext how OpenSSL RSA work ?

I generate public (n,e) and private key (n,d) then I encypted a file by :

openssl rsautl -encrypt -in plaintextFile -inkey privkey.pem -out cipher00

let's note the result C

and I tried to decrypt it by doing C^d (modulo n) but it doesn't work.

I think this is because OpenSSL adds some random value to my plaintext before the encryption. If I run the previous command once again on the same plaintext I have a different ciphertext.

How can I remove this random during the decryption?

The "normal", unmodified RSA (called textbook RSA) is susceptible to some attacks. We need to change it slightly to avoid this problems. The question Definition of Textbook RSA and the Wikipedia lists some possible attacks. In practice a special padding algorithm is used, like the Optimal asymmetric encryption padding (OAEP). The documentation of the RSA_public_encrypt function in OpenSSL shows the possible padding algorithm which can be used.

So yes, OpenSSL adds some random information to the plaintext. Without this, RSA would be deterministic: The same ciphertext would reveal that the plaintext was also identical. If you want to decrypt the ciphertext, then you have to either use OpenSSL again, or remove the padding manually.


Is it possible to weaken a bitcoin private key by “using” it elsewhere? What are the increased possibilities (if any) of being able to crack a private key given the following:

The associated bitcoin (ECDSA Secp256k1-based) public key is known.
The private key has been used to generate a public key from a different ECDSA curve and that public key is also known.
It is known that the two public keys are derived from the same private key.
It is known which ECDSA curves were used to generate the public keys.
It is known which ECDSA curve was used to generate which public key.

Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

EDIT: I should have pointed out that the conditions are ANDed, I.e. All conditions are known. Sorry, I should have been clearer the first time.

I'll start with the last point and use the notation for ECDSA from the wikipedia article.

  Does it make any more difference if there is data that is known to have been signed by the private key and the signature(s) are known and the raw data is known?

When using a digital signature scheme, the parameters (used group, e.g., elliptic curve group) as well as the public key,
signatures and all corresponding messages are public knowledge and a secure digital signatures scheme needs to be
even secure if the adversary is allowed to obtain signatures for arbitrary messages of its choice (ECDSA is secure
against such existential forgeries under adaptively chosen message attacks if the used hash function is collision resistant - AFIK the proof is in the generic
group model, but should still give enough evidence that it is secure).

In ECDSA your private key $d_A$ is an integer from $Z_q^*$, i.e., from the set of integers $\{1,\ldots,p-1\}$, where $q$ is the order of your elliptic curve group and
your public key is a point $Q_A=d_A\cdot G$ on the curve where $G$ is a generator of your elliptic curve group and part of the public
parameters.

The problem you are focused when you want to extract the private key $d_A$ from a given public key $Q_A$ is the elliptic curve discrete logarithm problem (ECDLP). Consequently,
ECDSA must be used with an elliptic curve group where the ECDLP is hard enough (also excluding curves that allow efficient pairings to reduce the ECDLP to the DLP in a related field (MOV attack). But this
is not the case if you use standardized curves such as SEC or NIST curves).

Observe also, that when you want to extract the private key from a given
signature you also have to break the ECDLP for point $kG$.

So for your question you have different public keys $d_A\cdot G_1, \ldots d_A\cdot G_n$ on $n$ different curves, where the public keys share the same private key
$d_A$. Additionally, you may know corresponding message-signatures pairs.

Then, to recover the private key you can use either the public key or the signatures you have
available on every curve separately, as you cannot do arithmetic between points on different curves. Even if it happens that there are efficient mappings between the curves, then you could simply take a single public key (e.g., of someone else) and map it to all the other curves and this attack would then also apply to a "single public key setting". Consequently, you rely on the strength of the ECDLP on the weakest of your
$n$ used curves and from my point of view the most efficient way to recover the private key in this scenario is to attack the ECDLP on the weakest of the used curves.

In general, when using ECDSA it is far more dangerous to re-use the randomness $k$ when producing signatures on
the same curve, as two signatures for different messages with same $k$ allows to recover the private key instantaneously as it happened to Sony back in 2011.


Can Web Cryptography API's native key object be reverse engineered in any way? I do understand that the security of web cryptography API comes from how it encapsulates the key object natively and disallows its access from JavaScript context unless exported.

However I would like to go further, this security model is only secure if the hacker cannot reverse engineer the browser binary itself to somehow figure out the key. I've been looking for a source on how the technology is actually implemented by browsers internally.

Is there a guarantee that a malicious actor cannot break into a browser and extract out keys "natively" instead? Are the keys stored encrypted internally somehow?

The Web Crypto API isn't intended to stop users from getting their own keys, or guaranteeing that to web pages. The Web Crypto API allows web pages to create and use private keys that the web page (and future versions of the web page) can not access; the API is about protecting web pages' keys from themselves.


Is PKCS#7 padding generated with a pseudo-random-number generator okay? Let's take this PHP code. We use libsodium and libsodium-php.
You have $text, $senderPrivateKey, $recipientPublicKey and a $nonce. The latter was obviously created like this by just using Sodium:

$nonce = \Sodium\randombytes_buf($size);

Now this is the code which adds PKCS#7 padding:

/* determine random amount of PKCS7 padding */
$padBytes = mt_rand(1, 255);

/* append padding */
$textBytes .= str_repeat(chr($padBytes), $padBytes);

Afterwards this is encrypted using \Sodium\crypto_box_keypair_from_secretkey_and_publickey and \Sodium\crypto_box.

So is it okay to use mt_rand here? I mean in the PHP documentation it is discouraged to use this for any "cryptographic purposes". However here it is only used for choosing a ("random") character and the length of the padding.

So is this secure? Would using openssl_random_pseudo_bytes(), random_bytes (in PHP 7) or libsodiums \Sodium\randombytes_buf (like it is used for the nonce) be more secure?
And is this a correct implementation of PKCS#7? Especially as the same variable is used for the length and the character of the padding.

Edit: As there was some confusing here some more information: Actually this implementation is only supposed to hide the file size (especially for short pieces of data) a bit to prevent an attacker from guessing the plain-text message. This is implemented in some open-source libraries related to Threema and here is an issue about this.
So basically in the Threema client a cryptographically secure RNG is used where in this example here a unsecure PRNG is used.
And this is what this question is about: Is it less secure to use a PRNG here?

If the intent of the padding is to make a passive attacker learn only a range instead of the exact message length, do not use real_len + rand(max_padlen).
It is more efficient to make the length of the padded message a multiple of a given block size instead.

If your protocol has enough latitude to allow large variations of the padding length, you can use a randomized length, but watch out for replay attacks. If for a given question, the same response is always sent, the question can be sent multiple times, so that the actual response length can be eventually inferred.
In order to mitigate this, the padding length should always be the same for a given question. A simple PRF can be used to achieve this.


Are there any MGF1 and OS2IP functions available in C? I need  MGF1 and OS2IP functions, as defined in the PKCS #1 v2.1: RSA Cryptography Standard.

Is there anything available in OpenSSL, or any other open C library?

You can find MGF1 in OpenSSL. Source file "crypto/rsa/rsa_oaep.c" has a function called "PKCS1_MGF1" that implements MGF1. The function signature is:

int PKCS1_MGF1(unsigned char *mask, long len, const unsigned char *seed, long seedlen, const EVP_MD *dgst)

See the wrapper function "MGF1" defined right below it for a more general case of using it.

As for OS2IP, I don't see an explicit method for converting to/from it in OpenSSL, presumably because the integers start and end in that format, so they never convert them.

OS2IP and I2OSP are a pair of straight-forward methods of encoding and decoding a large number to an octet string. The idea for OS2IP is that you simply represent the integer in big endian byte order. How you would use OS2IP to encode an integer depends entirely on how the integer is original represented before conversion.

The bottom line for OS2IP/I2OSP is that it's more a function of your original integer than a function of RSA. Find a way to convert the original integer to/from a big endian byte string, either by using a "toBigEndian" / "fromBigEndian" type function for your original integer or by making one manually. I don't think you'll find a generic method anywhere.

To do it manually: If you understand how the original integer format works, you can manually convert bytes to/from the original format and the octet string. If you can do multiplication, division, addition, and subtraction on the original integer, you can just calculate the octet stream manually with a few lines of code and a loop using the OS2IP description.


What are the properties of error vector used in symmetric McEliece cryptosystem? In the symmetric version of McEliece cryptosystem, we are adding intentional error vector during encryption. During decryption, first, we cancel the effect of error vector and then multiply the obtained term with the inverse of G matrix to retrieve the plaintext. In some papers, it is mentioned that weight of error vector has to be half of codeword length. So in this case, what is the relation between the error correcting capability of code used and weight of intentional error vector?

The weight of the synthetic error vector is $n/2$ where $n$ is the block length, this corresponds to maximum entropy error patterns, with independent probability of error $1/2$ for each bit.

The error correcting capability of the code should be much lower for good security.

In the original proposal, $n=1024$ and $t=50$ so this should give you some idea. There is a very readable paper here about this cryptosystem. Look for papers by Sendrier, for updated information on parameters and attacks.


proof of correctness Ring-LWE cryptosystem I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme.

The encryption goes as follows:

given a message $m \in R_2 $ and sampling a secret key $s$ from a distribution $\chi$, one samples $a$ from $R_q$ and $e \leftarrow \chi$, the ciphertext $c$ is a pair such that $c = ( c_0,c_1) = (a, as+2e+m)$.

To decrypt:

given $c=(c_0,c_1)$ one computes $c_0 + c_1s ~~mod~2$

Can someone please try and help me with that?

thanks in advance.

I think your proof of correctness may be hampered by the fact that you are setting the ciphertext to $(c_0, c_1) = (a, as + 2e + m)$ when in fact the paper you cite sets the ciphertext to $(c_0, c_1) = (as + 2e + m, -a)$. You correctly state that decryption is then computed as $c_0 + c_1s \text{ (mod } 2)$. This reduces to $(as + 2e + m) + (-a)s \text{ (mod } 2)$, and you can then eliminate some terms ($as$ and $-as$) to get $2e + m \text{ (mod } 2)$. We note that $2e \equiv 0 \text{ (mod } 2)$ hence we are left with $m \text{ (mod } 2)$ and since $m \in R_2$ we have $m \text{ (mod } 2) = m$.


Properties provided by GCM In the introduction of NIST Special Publication 800-38D is said that:

  GCM provides assurance of the confidentiality of data using a variation of the Counter mode of operation  for  encryption. GCM  provides  assurance  of  the  authenticity  of  the  confidential  data  (up to about 64 gigabytes per invocation) using a universal hash function that is defined over a binary  Galois  (i.e.,  finite)  field.    GCM  can  also  provide  authentication  assurance  for  additional data (of practically unlimited length per invocation) that is not encrypted.

As a block cipher GCM guarantees the confidentiality of data, but what does it mean that it assures its authenticity?
And what is exactly the authentication assurance for the unencrypted additional data?

I believe that data authenticity may correspond to its integrity, i.e. the absence of tamperings, while I'm not sure of the meaning of the authentication for the additional data.

Authenticity of the data assures that the data in question was created or modified by an authorized party (a key holder). Without authenticity, anyone could present an arbitrary block of data as a valid ciphertext. Though it is overwhelmingly likely that decrypting such a block will result in a garbage plaintext, it can still disrupt the application that is attempting to use the data. This is different from integrity, in that integrity assures you that a given piece of data has not been modified (either by an unauthorized party or by more mundane sources of data corruption such as bad hardware/line noise/cosmic rays/etc).

  So the authentication of the additional data corresponds only to the property that it is received in the same condition that it was sent out, without modifications?

Technically, integrity is what guarantees that the data was received in the same condition as it was sent out. Authenticity assures that the data originated from an authorized party.

Integrity can be seen as a subset of Authenticity. For example, you can obtain integrity by hashing a message. This does not provide authenticity though. For that, you require a MAC.


Why does Signal repeatedly hash the secure passphrase? Background: I'm working on creating a small program to extract my messages from Signal's newly-added (beta) encrypted backup feature.

In the Signal codebase for their Android app, I noticed that instead of just hashing both the salt and passphrase once, they repeatedly hash it 250,000 times.

MessageDigest digest = MessageDigest.getInstance("SHA-512");
byte[]        input  = passphrase.replace(" ", "").getBytes();
byte[]        hash   = input;

if (salt != null) digest.update(salt);

for (int i=0;i<250000;i++) {
    if (i % 1000 == 0) { EventBus.getDefault().post(new BackupEvent(BackupEvent.Type.PROGRESS, 0)); }
    digest.update(hash);
    hash = digest.digest(input);
}

return ByteUtil.trim(hash, 32);

(Source code can be found here)

I don't understand what benefits this offers over something that conceptually does:

sha512sum(sha512sum(concat(salt, passphrase)))

Am I correct in assuming that this does not add any extra security? Why exactly has this been done?

Additional Information:

The password for the backup is generated here and is 30 bytes long and then set contextually on line 37 of that file. This code was added in the commit 22 days ago, when encrypted backup was added and is currently only visible in the beta version of the app.

Cryptographic hashes are designed to be fast and collision resistant. It turns out that when hashing passwords, it is more secure to have a slow hash function. One way to make a fast hash function slow is to iterate it. Like is done here.

Think about it this way. If an attacker is able to compute a million hash calculations in a second, if you only ran your password through the hash function once, they would be able to attempt a million guesses each second. On the other hand, if you iterate the hash function 250,000 times, now the attacker can only make 4 guesses a second. That is a pretty substantial reduction and increases the amount of work the attacker has to do. If users were really good at choosing passwords, this might not matter, but the fact of the matter is that users are not good at choosing good passwords. Making the hash function slow helps in that regard.

In the case of Signal, it looks like encrypted backups is a beta-feature. Looking at one screenshot, it appears that the backup key is not user chosen. It is likely (haven't dug through the code) a 30 digit random number. That means it has about 100 bits of entropy at best. My guess is that the designers still wanted a slow hash function for the reasons listed above, even though the passphrase was not user chosen. Making it slow is a good trade-off for having less entropy. They could have made the random number longer to get more entropy (256 bits maybe), but that would have made the backup key that the user has to store much longer.


Is it possible to decrypt the entire message with one half of the key in this example? In this scheme, a 256 bit key is split into two 128 bit sub-keys. Message blocks are 256 bits and are also split into two sub-blocks. Before encryption, each sub-block is xor'd with it's partner and then xor'd with the opposite sub-key, in order to link the entire key to both blocks.

From the example below:

sub_aes_key1 = a
sub_aes_key2 = b
sub_block_1  = w
sub_block_2  = x
ciphertxt_1  = y = aes(message= sub_block_1 ^ sub_block_2 ^ sub_key_2, key = sub_key_1)
ciphertxt_2  = z = aes(message= sub_block_2 ^ sub_block_1 ^ sub_key_1, key = sub_key_2)

Essentially, the crux of my question is whether or not the hypothetical Susan, who somehow aquired one half of the key, would be able to infer the rest of the text. I'd also like to know if there are any other obvious vulnerabilities to this variant if you can see them.

  Pseudocode example

function func_1(a, b):
 encrypt message "a" with key "b"

function func_2(a, b)
 decrypt message "a" with key "b"

John knows:
a, b = 255, 100
c, d =  83,  97
w, x =  86, 205      (b XOR c XOR d), (a XOR c XOR d) #
y, z =  44, 196      func_1(w, a),      func_1(x, b)

Susan knows:
a, b = ___, 100
c, d = ___, ___
w, x = ___, 205      ???,               func_2(z, b)
y, z =  44, 196

a = c ^ d ^ x   =   ___ ^ ___ ^ 205
d = a ^ c ^ x   =   ___ ^ ___ ^ 205
c = b ^ d ^ w   =   100 ^ ___ ^ ___
w = b ^ c ^ d   =   100 ^ ___ ^ ___

There are two major problems with this method.

The first problem is that Susan is likely to be able to recover significant amount of data from a series of such blocks.

For example, if Susan knows $subkey_1$, then she could recover the value $subblock_1 \oplus subblock_2 \oplus subkey_2$; if a single block is encrypted with this key, she can't deduce anything from this (as she has no information about $subkey_2$; however if multiple blocks are encrypted with the same key, then she can exclusive or the values, obtaining the value $subblock_1 \oplus subblock_2 \oplus subblock_3 \oplus subblock_4$; if she has a guess about the encrypted data, this is likely to reveal more.

The second problem is that someone with the entire key is unable to uniquely decrypt.

Here's why: someone with the encrypt key could decrypt $ciphertxt_1$ to compute $subblock_1 \oplus subblock_2 \oplus subkey_2$, and thus recover $subblock_1 \oplus subblock_2$

And, they could decrypt $ciphertxt_2$ to recover $subblock_2 \oplus subblock_1$

At this point, they have the value $subblock_1 \oplus subblock_2$, howqever without any further information, they cannot recover either the values $subblock_1$ or the value $subblock_2$.  Yes, if the decryptor had some side information about either of those values, he could determine the other; however we generally don't assume that the legitimate decryptor has such side information.

Hence, this method makes things possible for the attacker, and not possible for the legimate user.


Need for secure hash function for a bloom filter I'm creating a bloom filter.

The purpose of bloom filters is to tell the enquirer whether a value is either definitely not in the set, or is possibly in the set.

The only attack vector I can think of is:

  An attacker has two versions of the bloom filter, the first version containing a set of values and the second version containing that set plus one additional value.

  Could the attacker get any information about the newly added value from the (up to 20) hash-derived bits that are set in the second version and clear in the first version?

Are there other attack vectors?

Is there any benefit to using a cryptographically secure hash function when calculating (20) hashes of the value, which are used to set bits in the bloom filter?

In particular, with a non-cryptographic hash function, does prefixing the value with the byte values 0-19, before hashing, to create the 20 hashes, create any form of weakness?

Are there other attack vectors?

This will very much depend on the application and how the attacker interacts with the bloom filter.

Let's say you are using a bloom filter to whitelist applications that are allowed to run on your system. The system computes a hash of an application before it is executed and checks it against the bloom filter. If it is in the whitelisted "set", then then application runs. If not, then the application is terminated.

Users can submit applications to the system administrator to have them whitelisted. The administrator does some manual analysis of the application before adding it to the whitelist to ensure it is good software (let's just pretend that the administrator can do this with complete accuracy).

The administrator can set the size of the bloom filter and the number of hashes to get an arbitrarily low false positive rate.

If a non-cryptographic hash function is used, e.g., CRC32. It is not unreasonable to assume that the probabilistic analysis that the administrator uses to determine the parameters of the bloom filter are incorrect.

This could manifest itself in a few particular ways.

If the attacker cannot get a benign application of his choosing approved but does know some number of already approved applications, the attacker can likely construct a malicious application that will be guaranteed to be in the set.
If the attacker can get a benign application approved, it is not unreasonable to assume that an attacker could come up with 2 programs, 1 benign and 1 malicious that would have the same hash values. By getting the benign one in the set, the malicious one is now also in the set.

Both of these scenarios would be much harder (i.e., computationally infeasible) if a cryptographically secure hash function is used, as opposed to a non-cryptographic function (like CRC32).


Why is public-key encryption so much less efficient than secret-key encryption? I'm currently reading Cryptography Engineering. After giving a high level explanation of the difference between secret-key encryption and public-key encryption, the book says:

  So why do we bother with secret-key encryption if public-key encryption is so much easier? Because public-key encryption is much less efficient, by several orders of magnitude.

That statement really surprised me, and its not explained which leads me to believe I didn't understand the high level explanation as well as I thought.

Why is public-key encryption so much less efficient then secret-key encryption?

There are three efficiency issues to discuss here: CPU, network bandwidth, and functionalities.

The "moral" reason of public key encryption being slower than private key encryption is that it must realize a qualitatively harder feature: to be able to publish the encryption key without revealing the decryption key. This requires heavier mathematics, compared to symmetric encryption which is "just" making a big tangle of bits. Most known asymmetric encryption systems seem to achieve the needed security, but at some relatively heavy computational cost. Note that the McEliece cryptosystem and NTRUEncrypt achieve asymmetric encryption and decryption at high speed (much higher than, say, RSA or El Gamal over elliptic curves). There is no proof that asymmetric encryption must really be harder, computationally-wise, than symmetric encryption, but the contrary would still be mildly surprising.

Another efficiency issue with asymmetric encryption is network bandwidth. This one is an absolute limitation. Public key encryption is public: anybody, including the attacker, can use the public key to encrypt arbitrary messages. This means that if the encryption is deterministic, then the attacker can run an exhaustive search on the encrypted data (i.e. encrypting potential messages until one matches). The data which is encrypted is still "useful data": it has structure, it is subject to such a search. Therefore, an asymmetric encryption scheme must include extra randomness. This, in turn, necessarily implies a data size increase. For instance, with RSA as described by PKCS#1, with a 1024-bit key, you can encrypt a data element only up to 117 bytes, yielding a 128-byte value. Therefore, if you were to encrypt a big file with "only RSA", you would end up with an encrypted message about 9% bigger than the plaintext: that's 900 extra megabytes for a 10 GB message. On the other hand, symmetric encryption only incurs a constant size overhead (say, at most +32 bytes for AES-CBC, including room for the initial value). There are many contexts where network bandwidth is a scarcer resource than CPU.

Finally, there are key exchange algorithms, which are like asymmetric encryption except that you do not get to choose the "message" you send: the sender and receiver do end up with a shared secret, but that value is mostly "randomly selected". Diffie-Hellman is the most well-known key exchange algorithm. To do "asymmetric encryption" with a key exchange algorithm involves using the "shared secret" as key in a symmetric encryption algorithm.


Bundling hash into the initialization vector? Given the need to transmit relatively short messages (a few dozens of bytes max), how unsecure would the following bundling of a hash in the initialization vector be?

(A) = 64 bits of cryptographic random
(B) = cryptographic hash of A concatenated with original Message

Then concatenate (A) with 64 bits of (B), and use that as IV for an AES CTR mode encryption.

This weakens the IV randomness to allow bundling the hash in it, and attempts to hide information the unencrypted hash in the IV could leak.

The key used for AES is itself changed every time, it is a HMAC of (secret + message counter).

This is a terminally bad idea: much of the confidentiality of the message $M$ is lost, because $A$ and 64 bits of $B=H(A\|M)$ are available in clear. So if $M$ is enumerable (a password, a name, a Social Security Number) among say $2^{48}$, it can be found by a cheap offline attack with little odds of false positive ($2^{-16}$), totally irrespective of the AES cryptography.


How are non-text files encrypted? I thought encryption algorithms (like AES) are used to encrypt texts. So, how are files or folders (containing pictures, videos, etc.) encrypted? What is it that encryption algorithms exactly encrypt?

Encryption algorithms encrypt bits. All digital media (text, pictures, videos, etc) is stored as bits at the lowest level, therefore, they can all be encrypted.


Is there a big RSA Data Set Is there a big dataset containing RSA public $(n,e)$ and private keys $d$ and primes $p,q$ where $n = p.q$ ?

No.  You can generate such a dataset for yourself by generating lots of RSA keypairs yourself.  Therefore, there's no need for such a dataset (and no reason why anyone would publish one).


Which block cipher parameters should be kept secret? Which of the parameters of a block cipher (e.g., algorithm name, mode of operation, IV (if any), key length) are essential to keep secret?

In you opinion which of the parameters of a block cipher (e.g., algorithm name, mode of operation, IV (if any), key length) are essential to keep secret?

I believe that it is essential that you keep the key secret.

If there is any other aspect of the cipher that you must keep secret (that is, you become insecure if it is revealed), then your cipher is 'broken'.

We can assume that the attacker can learn any long term aspect of your cipher implementation, such as the cipher name, mode of operation, key length.  There are a number of possible ways they might learn it, such as an employee accidentally (or deliberately) leaking it, or if the attacker just obtains your implementation and dissects it.  Hence, for security, we want to depend solely on something that we update routinely (such as the key).  If the attacker learns the key, that limits the damage (as they can decrypt the traffic encrypted with that key, but nothing after we update the key).  This idea is referred to as Kerckhoff's principle.

Now, you list the IV; that is typically updated constantly.  On the other hand, we generally use it to refer to information that need not be secret.  If it does have to be secret, then it really is part of the key, and should be considered that way.


How to create the right Blowfish padding? I use the OpenSSL library for Blowfish encryption in ecb mode.
The message are encrypted, but with the wrong padding, because of it I have a problems with decryption. What am I doing wrong?

I checked with:

http://sladex.org/blowfish.js/

and java.

It should be:
Kl9SMj1A42I48uWYTeBuD9rERDGhuvbbp07+4QwPhtk=

I get it:
Kl9SMj1A42I48uWYTeBuD9rERDGhuvbbLUwFXarEOq39/f39

#include <iostream>
#include <string>
#include "Base64.h"
#include <openssl/blowfish.h>

int main()
{
    // blowfish key
    const char *key = "topsecret";
    const unsigned char* in = (const unsigned char*)"hello world how are you today";

    BF_KEY bfKey;
    BF_set_key(&bfKey, strlen(key), (const unsigned char*)key);

    size_t InSize = strlen((char*)in) + 1;
    size_t OutSize = ((InSize + 7) / 8) * 8;

    unsigned char *out = (unsigned char *)malloc(OutSize);
    unsigned char *outnext = out;

    //Encryption
    while (InSize >= 8) {
        BF_ecb_encrypt(in, outnext, &bfKey, BF_ENCRYPT);
        in += 8;
        outnext += 8;
        InSize -= 8;
    }
    if (InSize > 0) {  // Cope with non-octal length
        unsigned char buf8[8];
        memcpy(buf8, in, InSize);
        for (int i = InSize; i < 8; i++) {
            buf8[i] = ((int)'0');
        }
        BF_ecb_encrypt(buf8, outnext, &bfKey, BF_ENCRYPT);
    }

    std::cout << Base64::base64_encode(out, strlen((char *)out)) << std::endl;

    std::cin.get();

    return 0;
}

Base64:

http://pastebin.com/DvLt3MPg

I use the OpenSSL library for Blowfish encryption in ecb mode. [...] What am I doing wrong?

You're using ECB mode and no authentication.

But as for the question itself.

Your input length is 29+1 bytes, which should get padded to 32 bytes, which should be ceil(32/3*4) = ceil(42.67) = 43 characters when base64-encoded, plus one = to round up to four. The output from the site you linked to seems to be of that length, but the output from your code looks like 48 characters, or 36 bytes. Extra bytes appear to show up from somewhere.

The output is made using this call to base64_encode:

unsigned char *out = (unsigned char *)malloc(OutSize);
base64_encode(out, strlen((char *)out))

The length is determined with strlen. But is the data in the out buffer terminated with a zero byte? I don't see that terminator anywhere, so it may be that strlen and hence base64_encode read past the buffer.
Check what the strlen output is, compared to OutSize.

In any case, the output from the cipher might contain zero bytes too, so I don't think you should be using strlen here at all.

Also, the padding you are using destroys the length of the plaintext. That is, foobar and foobar0 pad to the same string, foobar00 and there's no way to tell them apart. You may want to consider some other method of padding. (Basically, encode the length of the padding in the padding itself, which means you may need to pad a full block.)


Can you help me understand hash-preserving encryption? I have rather simplistic understanding of cryptography, so I have to beg a pardon in advance if the question has internal contradictions.

Imagine data $A$ with a hash $hashA$. This data is encrypted with private key $K$ to get data $E$ and the hash of the encrypted data is $hashE$.

Are there encryption method and hashing method, which will allow to verify, given $hashA$, $hashE$ and $K$, that $hashE$ is indeed a hash of “A encrypted with K”?
How secure could that algorithm be against attempted forgeries, i.e. someone having access to $A$ creating $E$ and $K$, so that $hashA$, $hashE$ and $K$ are correct in sense of $1$, but $E$ is not “A encrypted with K”?

Clearly the identity hash $(hash(x)=x)$ works, but I'm more interested in hashes which are significantly smaller than the original data.

A generic construction could be something like this:

$\def\Enc{\operatorname{Enc}}$ Take a simple hash function $H$ and encryption function $\Enc_K$.

Then define $E = (\Enc_K(H(A)), \Enc_K(A))$ as the encryption, $hashA(A) = H(A)$ and $hashE(x,y) = x$.

Then we have $hashE(E) = \Enc_K(H(A))$, which of course is easy to check against $H(A)$, given $K$.

Of course, this in no way satisfies your unforgability requirement: Only someone with access to both $E$ and $K$ can check if the hash part of $E$ matches the rest of it.


The formulas actually work.
You just have to keep in mind to make computation in the field of intergers modulo $2^{255}-19$ and that there are actually two square roots, you need to use the right one if you want to have the expected result.

You can test the following SAGE code

gf=GF(2^255-19)
X_P = gf(15112221349535400772501151409588531511454012693041857206046113283949847762202)
Y_P = gf(46316835694926478169428394003475163141307993866256225615783033603165251855960)
u = (1+Y_P)/(1-Y_P)
v = gf(-486664).sqrt()*u/X_P,-(gf(-486664).sqrt())*u/X_P
print u
print v

on the Sage Cell server.


Encrypting a partially known plain text I'm about to implement my very first crypto system probably using AES128. (still trying to figure which mode to use)

Is there a weakness in encrypting a plain text of which 50% is known by the attacker? Will an attacker be able to decrypt the unknown 50%.

Let me explain. In my project I need to encrypt dictionaries (list of key/value). I suppose that all the keys are known to the attacker (by reverse engineering), as such an attacker knows more or less half of the plain text. Would that make the encryption of the values weaker?

For what I have understood of chosen plain text attacks, knowing a part of the plain text should not be a problem. But the approval of someone smarter than me would relieve me from anxiety.

Thanks

No, partially known plain text won't help an adversary guessing what's unknown, when using AES-128 in any of its usual secure mode, such as the common CTR with random IV (caution: it might help when using ECB, or doing other goofs)

That extends to any modern cipher, and the more general (and often realistic) assumption that the adversary can choose part of the plaintext. All modern ciphers are designed with the explicit goal that the adversary can't tell anything about plaintext that it is not already known. This formalizes as IND-CPA, or IND-CCA1 (depending on what's assumed about what the adversary can do).

Addition: to some degree, a little known plaintext helps brute force attacks (aiming at finding the key by enumeration of the possible keys, which then allows full decryption), and attacks on implementations. However, AES-128 is currently very safe against brute force, thus this threat can be discounted. In the first paragraph, I have silently made the following assumptions:

The key was chosen at random, and is initially fully unknown to an adversary.
We discount the distant possibility of quantum computers usable for cryptanalysis.
The implementation is not attacked by side channels (timing attack, DPA..).


Are zero knowledge proofs alternative private key encryption? Are they the alternative to private keys. If I understand correctly, because of the increasing computational power in today's world, zero knowledge proofs are more safe than private keys ?
Are these two things connected in the way I understood it, or is my understanding a bit off?

I'm not sure about what you mean for "more safe". A probable link between these notions exists when we consider a context/application: suppose we need a secure identification scheme; the adversary is listening to the channel between the identifier and the identity-server. By considering this context, we can say that an identification scheme based on a zero-knowledge proof withstands adversary attacks: eavesdrop, man-in-the-middle, replay, etc.
In this given context, an identification scheme based on private keys will fail: a secure channel is always a prerequisite to exchange private keys. Even if the private key is unconditionally unbreakable for any computational power: the adversary can tap it if no private channel exists.


Epsilon Perfect Secrecy: Size of Key Space I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds

$\Pr[M=m\mathrel|C=c]\leq (1+\epsilon)\Pr[M=m]$

Then the problem asks us to prove that $|K|\geq \frac{1}{1+\epsilon}|M|$ where $K,M$ are the key and message spaces, respectively. I believe this problem is essentially the same as problem 2.12 in "Introduction to Modern Cryptography".

I have read the proof for Shannon Secrecy's key space limitation (which says $|K| \geq |M|$). I don't really see how this is connected to that proof, and I can't find any other way to approach. Can someone please give me a few hints?

Choose a uniform distribution over the message space $M$. Suppose we observe a ciphertext $c$. Let $M_c = \{ m | \exists k. dec_k(c) = m \}$ be a set of all messages that could have been encrypted to $c$.
Choose a message $m \in M_c$ for which $\Pr[m|c] \geq \frac{1}{|K|}$ (such message exists, because the set $M_c$ has at most $|K|$ elements). Without knowing $c$, the probability of $m$ being chosen is $\Pr[m] = \frac{1}{|M|}$. Thus, we conclude that $\frac{1}{|K|} \leq \Pr[m|c] \leq (1+\epsilon)\Pr[m] = (1+\epsilon)\frac{1}{|M|}$, from which your desired inequality follows.


If you XOR a random input with a biased input, the output is random - why? Ive seen in an answer to this question here :

https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes/5889288#5889288

that If you XOR a random input with a biased input, the output is random .

What is the reason for that ?
Is there a formal proof ?

thx

Let $X, Y \in \{0,1\}$ be random variables, with $\Pr[X = 0] = \Pr[X = 1] = 1/2$ and any distribution on $Y$ as long as $Y$ is independent of $X$ so that $$\Pr[Y = y \mathrel| X = x] = \Pr[Y = y]$$ for any fixed bits $x, y \in \{0,1\}$.  What is the distribution on $X \oplus Y$?  Let $b \in \{0,1\}$ be a fixed bit.  Then

\begin{align*}
  \Pr[X \oplus Y = b]
    &= \Pr[X \oplus Y = b \mathrel| X = 0]\cdot\Pr[X = 0] \\
      &\quad\quad + \Pr[X \oplus Y = b \mathrel| X = 1]\cdot\Pr[X = 1] \\
    &= \Pr[0 \oplus Y = b \mathrel| X = 0]\cdot(1/2) \\
      &\quad\quad + \Pr[1 \oplus Y = b \mathrel| X = 1]\cdot(1/2) \\
    &= \Pr[Y = b \mathrel| X = 0]\cdot(1/2) \\
      &\quad\quad + \Pr[Y = b \oplus 1 \mathrel| X = 1]\cdot(1/2) \\
    &= \Pr[Y = b]\cdot(1/2) + \Pr[Y = b \oplus 1]\cdot(1/2) \\
    &= (\Pr[Y = b] + \Pr[Y = b \oplus 1])\cdot(1/2) \\
    &= 1/2,
\end{align*}

the last equality arising because $b$ and $b \oplus 1$ are the only two possible values that $Y$ can take on, so $\Pr[Y = b] + \Pr[Y = b \oplus 1] = 1$.


ECC - ElGamal with Montgomery or Edwards type curves (curve25519, ed25519) - possible? I know the usual way of using getting shared secrets for encryption with ECC is DH, however, this only works with two keypairs of exactly the same kind, for example two curve25519- or two p256-keypairs.

With ElGamal, one can get a symmetric key for a recipients public key no matter which kind of key they are using themselves.
This works great if users don't have the same kinds of keys, and it doesn't use the same shared secret each time. This behaviour makes development and use of an application using ECC for encryption much easier and probably even is more secure (as the shared secret is different each time), so I'd prefer using ElGamal if possible.

However, it only seems to work for Short type curves - NIST, SECG, brainpool and so on. (My javascript implementation (1) is based on SJCL's implementation, but uses "elliptic" as a library, which supports Short, Montgomery and Edwards curves, while SJCL and JSBN only know Short.)

I don't really get this, as the logic behind ElGamal is really simple:

public_key = curve_param_G * secret_key
tag = curve_param_G * random_secret
key = public_key * random_secret = curve_param_G * secret_key * random_secret
key = tag*secret_key = curve_param_G * random_secret * secret_key

The implementation of multiplication for Montgomery and Edwards curves seems to be different from the multiplication function of Short curves. Still, shouldn't it work?

Is there any change to make ElGamal work with Montgomery curves like curve25519, or Edwards type curves like ed25519, and is it just implementations fault?
Or is there any reason this actually isn't possible?

Reasearching on this topic doesn't bring much detailed information(, unless you get the exact math behind Montgomery and Edwards curves, which I don't at the moment, I'm just using the elliptic library for a simple app).

Thank you for your answers :)

(1) Some pseudocode (simplified):

Get a symmetric key for a known public key (to get a symmetric key only the recipient will be able to find out knowing a public key):

ec = curveobject(curve_the_pubkey_is_on);
secret = random_secret_key();
tag = ec.g.mul(secret); // pass along with the message
key = public_key.mul(secret); // use for symmetric encryption

Get a symmetric key for a known tag (to get the symmetric key knowing the tag
and own private key):

key = tag.mul(private_key); // can decrypt message with

ElGamal works for any group. What is badly specified is the glue between the protocols (some network packets) and the exact implementation variants in the math library.

C25519 use arithmetic over Montgomery curves.

Ed25519 use arithmetic over twisted Edwards curves.

Huff curves implementations can be "faster", but there are not in the repository of curves types http://www.hyperelliptic.org/EFD

Implementations over MIST binary curves can be "faster" than integer curves. http://rt.openssl.org/Ticket/Display.html?id=3117 and even immensely faster than many implementations of c25519.

So you have a plethora of curves available to you. they are all equivalently secure related to "modulus size". Speed, constant time, inter-operability, conformance to standards, and bugs, depend on the library choices and implementation details.

Points from one specific curve (e.g. NIST B283) cannot be used directly in the arithmetic a different curve (e.g. Ed25519).

You have to go to DJ Bernstein original paper for the reasons of his choice for these curves. ECDH can benefit of XZ coordinates and montgomery ladder, assuming the protocol would not require that you transfer the Y coordinate between Bob and Alice. If you need Y coordinate, then c25519 and its XZ ladder is not much of an improvement.
EDDSA can benefit of the coordinate system for twisted edwards curves which has a strongly unified point addition which does not requires the implementor to specifically care about P+Q, P+3Q, P-Q, P+P .....

EC encryption, EC decryption, EC-ELGAMAL works with all of these curves. All you need is a standardization of the type of data exchanged between bob and alice. As far as I know, there is nothing approved in the RFCs and NIST standards, where lobbying and who'swho dictates the changes and approvals.


Using HKDF to derive symmetric keys from a hybrid public-key encryption scheme RFC 5869 describes HMAC-based Extract-and-Expand Key Derivation Function (HKDF). In section 4, entitled "Applications of HKDF", it states that one of the intended uses is:

derivation of symmetric keys from a hybrid public-key encryption
scheme

However, it doesn't expand on the meaning of this. Can anyone explain how HKDF can be used in this manner?

Fix an RSA modulus $n$.  Here's a way you can send a message $m$ so that only someone who knows the secret factorization of $n$ can read it.

Pick an integer $1 < x < n$ uniformly at random.
Compute $y = x^3 \bmod n$.
Compute $k = \operatorname{HKDF-Extract}(\underline x)$, where $\underline x$ is the little-endian bit encoding of the integer $x$.  Note that $\underline x$ itself is not a uniform random bit string: if interpreted as an integer, it is always below $n$.  Thus it is unfit to satisfy the security contracts requiring a uniform random key.
Compute $k_\mathrm{enc} = \operatorname{HKDF-Expand}(k, 512, \text{‘Cocowalla's app: encryption key’})$.  $k_\mathrm{enc}$ is conjectured to be indistinguishable from a uniform random bit string to an adversary who doesn't know $x$.  As such it is fit to satisfy security contracts requiring a uniform random key.
Compute $k_\mathrm{mac} = \operatorname{HKDF-Expand}(k, 256, \text{‘Cocowalla's app: authentication key’})$.
Compute $c = m \oplus (\operatorname{Threefish512}_{\,k_\mathrm{enc}}(0) \mathbin\Vert \operatorname{Threefish512}_{\,k_\mathrm{enc}}(1) \mathbin\Vert \cdots)$, the encryption of $m$ with a one-time pad generated by Threefish-512 in CTR mode.*
Compute $t = \operatorname{Poly1305}_{k_\mathrm{mac}}(c)$, the authentication tag for $c$.
Transmit $(y, c, t)$.

The recipient who knows the factors $p$ and $q$ of $n$ can solve $3d \equiv 1 \pmod{(p - 1)(q - 1)}$ and recover $x = y^d \bmod n$, since $y^d \equiv (x^3)^d \equiv x^{3d} \equiv x^1 \equiv x \pmod n$; then they can derive $k$, etc., as before.

In archaic crypto literature,† this is called ‘hybrid’ because we don't use the RSA trapdoor permutation $x \mapsto x^3 \bmod n$ to encrypt the message; rather we use it as a public-key KEM to conceal a secret element $x$ of $\mathbb Z/n\mathbb Z$, and derive from $x$ keys for a symmetric-key cryptosystem—specifically, a DEM, a data encapsulation mechanism.  Thus it is a ‘hybrid’ of public-key and symmetric-key cryptography.

* This is not actually how I would recommend doing it: I would rather recommend NaCl crypto_secretbox_xsalsa20poly1305 with a single key.  But this illustrated using HKDF-Expand to generate multiple keys of different sizes with different info strings.

† The designation of ‘hybrid’ today is archaic because modern cryptographers recognize it was foolish all along to shoehorn structured messages like ‘Help!  I'm trapped in an RSA ring.’ or ‘The Magic Words are Squeamish Ossifrage’ into elements of $\mathbb Z/n\mathbb Z$.  In fact, for hysterical raisins, we still do approximately this: pick $k \in \{0,1\}^{256}$ uniformly at random, and then shoehorn it with an array of hash functions into an approximately uniform random element of $\mathbb Z/n\mathbb Z$, with a byzantine construction called OAEP.  For hysterical raisins most protocols deployed in practice use OAEP, or its even worse predecessors.  The much simpler scheme above is called RSA-KEM.


Why does it make sense to use min-entropy for measuring cryptographic random data? Comments on Cryptographic Entropy Measurement seems to challenge the heart of NIST SP 800-90B, which proposes min-entropy as a conservative measure of entropy produced by hardware source.

[The idea of using min-entropy] has been taken to heart in the NIST SP 800-90 documents, using the most conservative measure, min-entropy. While this may make sense for cryptographic random data, it makes no sense when measuring entropy in raw random data. [section 1, page 2]

Why does it make sense to use min-entropy for measuring cryptographic random data?  I would have thought it was the other way around --- sensible for measuring raw random data, not cryptographic random data --- because entropy is produced in raw random data; cryptographic random data is processed random data, which cannot increase entropy, only possibly reduce it.

The central limit theorem does not hold and confidence intervals are
not well defined for [min-entropy].  If minimum entropy does not
satisfy the requirements set out by either Shannon or Rényi, why is it
used as the foundation for measuring entropy in cryptographic
applications? [section 3.1.1, page 6]

Does min-entropy satisfy the properties of an entropy measuring function laid out by Shannon?  If not, why is it being used for measuring entropy?
Update. @kodlu, the properties an entropy function $I(p)$, where $p$ is the probability of a certain event $s$ should have are:

$I(p) \ge 0$
$I(p_1, p_2) = I(p_1) + I(p_2)$ for independent events.
$I(p)$ is a continuous function of $p$.

Ignore NIST. It has more important legally binding agendas to debate outside of this forum. Use common sense.

Does min-entropy satisfy the properties of an entropy measuring function laid out by Shannon? If not, why is it being used for measuring entropy?

No. $H_{\infty}$ is to Shannon entropy as is JPEG to BMP. Shannon was interested in encoding all the data in the transmission channel.  $H_{\infty}$ is lossy and the original data cannot be retrieved in it's entirety. $H_{\infty}$ is used before transmission.

entropy is produced in raw random data

Yes. So measure it. You will have a lot more luck if you can prove the data to be IID.
It boils down to this:-

You need to separate information entropy from cryptographic entropy.
We want true random bits.
We get them via some generic form of hardware processing.
Current mathematical thinking revolves around the left over hash lemma which dictates the eventual output bias.
The thinking is predicated on $H_{\infty}$.
Thus $H_{\infty}$.


How much stronger is RSA-2048 compared to RSA-1024? How much stronger is RSA-2048 compared to RSA-1024? It is hard to imagine very big numbers. So what would be your way to explain the difference to someone who doesn't know much about cryptography?

You can use the complexity of the GNFS, the fastest known general-purpose factoring algorithm, to estimate the strength (in bits) of an RSA key size.

Referencing the table linked above, a 1024-bit key has approximately 80 bits of strength, while a 2048-bit key has approximately 112 bits. Thus, it takes approximately 2112/280 = 232 times as long to factor a 2048-bit key. In other words, it takes around four billion times longer to factor a 2048-bit key.

Thus, if you were able to magically factor a 1024-bit key in 10 seconds (which is totally unrealistic in every way possible, I may add), then it would take around 1,200 years to factor a 2048-bit key (note: this is not adjusted for Moore's law). Of course, it took around two years and a massive collaborative effort just to factor a 768-bit key, so factoring a 1024-bit key takes far, far longer than 10 seconds. But this is just to demonstrate the point: 2048-bit keys are much more secure.

If you do want to adjust for Moore's law and the ever-faster pace of computing, you can use this approximation by fgrieu. If you solve the equation for when a 2048-bit key is expected to be factored (keeping in mind that this is a rough approximation), you arrive at the year... 2048. So somewhere around 2040-2050, if that linear approximation holds true, we expect 2048-bit keys to be feasibly factored. In comparison, you can see that the 1024-bit key is expected to be factorable sometime around 2015-2020.


Centralized storing of private RSA key I working on multiuser project, where users can share data. The data that users upload to the server will be encrypted before it leaves the client with a symmetric cipher, and then the symmentric key is encrypted with a public RSA algorithm to those who the data is ment for (Basic PGP). In this way I can guarantee that unauthorised users don't get access to the data, even if they are able to gain root access to the server.

The question is how should I handle the private RSA keys. By using public-key cryptography the user is very much «locked» to that one devices that contains the private key. But let assume that user wants to switch between smartphone, laptop and desktop. Is it secure to encrypt the private key with symmetric cipher and use PBKDF2 to iterate the password before I upload the private key to a centralized server?

Or is there a better way to share private keys between multiple devices?

Technically, yes, it can be secure.

However you are worried about a server compromise. And the consequence of such a compromise would be that the user's private keys can get subject to attack by brute-force and / or dictionary attacks which usually doesn't end well because users tends to pick bad passwords. While you can make this harder using Argon2d (don't use PBKDF2) it's still not impossible for an attacker to even recover a moderately difficult password.

You see the problem now. Because of this I'd suggest leaving the user the choice to sync their encrypted private key to your cloud, to their own cloud service provider, to one of their other devices or don't sync it at all and give them a short explanation.

  This will synchronize your private decryption key to our cloud. If you
  lose this key you will no longer be able to access your encrypted
  messages. By synchronizing we can also ensure you can use this key
  from your phone and your laptop. However note that if we get
  compromised there's a risk that an attacker can recover your password
  and the key if you're not 100% confident in it. If you don't
  synchronize there's no risk of a server compromise leaking information
  about your messages or key.


Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics? I work on ethereum and other blockchain technologies. And seeing that quantum pc's are someday going to see the light I have some questions / doubts.

I was wondering if hash functions are strong enough to hold up against quantum computers (that in the future will be reality I think seeing things like IBM-Q)

Obviously, cryptosystems like ElGamal, RSA or other cryptosystems based on modular exponentiation and the impossibility of solving the discrete logarithm will fail against quantum adversaries because (as I understood) once the period of the multiplicative body generator (for DSA) or the additive body (ECDSA) is found, you can polarize the qbits in order to extract the solution (obviously I'm not an expert so I don't know if I'm right)

I read this post but I was hoping for a bit more of an insight to understand better all of this in-depth.

So my question: How well do hash functions hold up against adversaries with (large-scale) quantum computers?

This depends on what kind of hash function you mean and what kind of security you want.

Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, has forgery probability for messages of $L$ bytes bounded by $8\lceil L/16\rceil/2^{106}$.  This means that an adversary, given $(m, a)$ where $a = \operatorname{Poly1305}_k(m)$ for a uniform random choice of $k$ unknown to the adversary, has probability at most $8\lceil L/16\rceil/2^{106}$ of forging a pair $(m', a')$ where $m \ne m'$.

This forgery probability is independent of any bounds on the attacker's computational costs, so a quantum adversary has no advantage over a classical adversary to forge universal hash authenticators without knowing the key.  However, while the collision probability of Poly1305 as a universal hash family is negligible, an adversary who knows the key can trivially find collisions: Poly1305 is not collision-resistant—more on the distinction between collision probability and collision resistance.
SHA-256 is conjectured to be collision-resistant.  This means, loosely, that it is hard to find a pair of distinct messages $m \ne m'$ such that $\operatorname{SHA256}(m) = \operatorname{SHA256}(m')$.  There is actually no formalization of this concept, only of keyed collision-resistant hash families because, by a simple technique of counting pigeons and holes, we know that collisions exist in SHA-256, so any trivial algorithm that is hard-coded to print one will succeed with essentially zero cost.  We just don't know those algorithms, so the best we can do is generic collision search.

The state of the art in classical generic collision search, the van Oorschot–Wiener algorithm, is actually cheaper than any of the proposed quantum algorithms for generic collision search.  There may be breakthroughs in generic quantum collision search algorithms, or someone may find specialized cryptanalysis of SHA-256 that works only on quantum computers (e.g., see below about exotic constructions).  But in the current state of the public literature, classical collision searches already appear cheaper than any known quantum collision searches would be even in the unbelievable scenario that qubit operations became as cheap as bit operations.
HMAC-SHA256 is conjectured to be a pseudorandom function family, sometimes loosely called a ‘keyed hash’.  You might use these to make bearer tokens that passed as HTTP cookies in a web application, e.g. $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ where $m$ is the message ‘the bearer of this token is allowed to write cat pictures to the database between 2018-05-18 and 2018-05-25’ and $k$ is a uniform random secret key known only to the application server.

For an adversary to forge bearer tokens, their best known strategy given current cryptanalysis of HMAC-SHA256 is to recover $k$ by a generic preimage search on the function $k \mapsto \operatorname{HMAC-SHA256}_k(m)$ for a known message $m$.  Actually the adversary might have $t_0 = \operatorname{HMAC-SHA256}_{k_0}(m)$, $t_1 = \operatorname{HMAC-SHA256}_{k_1}(m)$, etc., for many different services handing out bearer tokens, and is happy to recover one of the uniform random secret keys $k_i$.

The same applies to, e.g., ciphertexts with one-time pads generated by the Salsa20 hash function (which is emphatically not collision-resistant), or AES ciphertexts with the function $k \mapsto \operatorname{AES256}_k(0)$; although AES is a pseudorandom permutation family, the best generic attack is essentially the same.

The state of the art in classical generic preimage search to find any one of $n$ keys among $2^b$ possibilities with probability $p$ is Oechslin's rainbow tables on a parallel machine, with the computational cost of about $p\cdot 2^b/n$ evaluations of the hash if parallelized at least $q \geq n^2$ ways in the time for $p \cdot 2^b/nq \leq p \cdot 2^b/n^3$  evaluations of the hash.

The state of the art in quantum generic preimage search is Grover's algorithm, which for a single-target attack can find one key among $2^b$ possibilities with high probability $p$ with the computational cost of about $2^{b/2}\sqrt{p}$ evaluations of the hash in quantum superposition on a quantum computer.  This would be a stunning improvement if qubit operations were ever made as cheap as bit operations.

Grover's algorithm can be parallelized by running many quantum computers on different parts of the search space, but the time advantage of parallelizing Grover's is modest: parallelized $k$ ways, it runs in the time of about $2^{b/2} \sqrt{p/k}$ evaluations of the hash in quantum superposition on a single quantum computer: an array of $k$ quantum computers gives only a factor of $\sqrt{k}$ time improvement over than a single quantum computer.  The parallel Grover machine can also be modified to find a preimage for any one of $n \ll k$ targets in the time of $2^{b/2} \sqrt{p/n^{1/2}k}$ quantum evaluations of the hash, at the total cost of $2^{b/2} \sqrt{p/n^{1/2}}$ including communication costs—only a very modest factor of $n^{1/4}$ improvement in cost over a single target.

The bounds on single-target parallel Grover are proven to be optimal for a generic quantum algorithm, so unless something about the structure of HMAC-SHA256 lends itself to better specialized quantum cryptanalysis, in our current model of quantum computers these costs will not get better (but see below about exotic constructions).  It seems unlikely that multi-target parallel Grover variants can cost much less than $2^{b/2} \sqrt{p/n}$, if the $2^{b/2} \sqrt{p/n^{1/2}}$ figure including communication costs is not already optimal.
SHA-256 is conjectured to be preimage-resistant.  There is actually, again, no formalization of fixed preimage-resistant hash functions, only keyed preimage-resistant hash families (our own potato's summary), but the intuitive idea is that if you're challenged with a hash $h$, it should be hard for you to find a message $m$ such that $m = \operatorname{SHA256}(m)$.

If $h$ is 8a798890fe93817163b10b5f7bd2ca4d25d84c52739a645a889c173eee7d9d3d, and you know that $m$ was drawn from one of the strings ‘yes’ or ‘no’, then it is easy to find $m$.  This is a generic preimage search too, but it is worth mentioning as qualitatively different from the case of HMAC-SHA256 with a uniform random key because the input space is small and highly structured.

Still, the adversary's best known strategy for finding a message $m$ given a hash $h$ is essentially the same as the adversary's best known strategy for finding a key $k$ given a bearer token $t = m \mathbin\Vert \operatorname{HMAC-SHA256}_k(m)$ and a known message $m$: generic preimage search with parallel rainbow tables or Grover's algorithm.  Just remember that highly structured messages or messages drawn from nonuniform distributions—especially, e.g., human-chosen passwords—may make the adversary's job substantially easier.
Exotic constructions with specialized cryptanalysis.  These applications of Grover's algorithm and generic search strategies apply to any hash function without knowledge of its structure beyond how to evaluate it.  Nobody has found anything in the structures of SHA-256, Salsa20, BLAKE2, etc., that would admit faster quantum cryptanalysis.  Universal hash families like Poly1305 and GHASH have forgery and collision probabilities that are independent of the attacker's computational budget, so neither a thousand suns nor a real live quantum computer would change them.  But here are some examples of constructions that do have quantum-vulnerable structure:

Collision search.  If $n$ is a public 2048-bit product of two uniform random 1024-bit primes $p$ and $q$, then for uniform random $y \in (\mathbb Z/n\mathbb Z)^\times$ the function $H\colon x \mapsto y^x \bmod n$ of 2048-bit integers to 2048-bit integers is collision-resistant as long as the RSA problem is hard.  But on a quantum computer, Shor's algorithm can find the order $k$ of $y$ modulo $n$ at modest cost in qubit operations, and then trivially compute the collisions $y^0 \equiv y^k \pmod n$, $y^1 \equiv y^{k + 1} \pmod n$, etc.  Similar considerations apply to other factoring-based collision-resistant hash families like VSH.

(Shor's algorithm can also factor $n$ at modest cost in qubit operations, at which point it is trivial to find collisions because the order $k$ always divides $\operatorname{lcm}(p - 1, q - 1)$.)
Preimage search.  If $p$ is the 2048-bit prime modulus of RFC 3526 Group #14 and $g$ is any primitive root modulo $p$, the function $H\colon x \mapsto g^x \bmod p$ is preimage-resistant as long as the finite-field discrete log problem problem in $\mathbb Z/p\mathbb Z$ is hard: finding a preimage is exactly solving the finite-field discrete log problem in a group where it is conjectured to be hard.  But given $h = g^x$, if we can find a period $(\delta, \gamma)$ of the function $f\colon (a, b) \mapsto g^a h^{-b} = g^{a - b x}$ then we have $$g^{a - b x} = g^{a + \delta - (b + \gamma) x}$$ for all $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma x \pmod q$ and thus $x \equiv \delta \gamma^{-1} \pmod q$ where $q$ is the order of $g$.  Again, on a quantum computer Shor's algorithm can find such a period and thereby compute the discrete log $x$ of $y$ with base $g$.

These constructions are of only theoretical interest because they are costlier for legitimate users, they provide no additional security against classical adversaries with current knowledge of cryptanalysis, and they would be much cheaper for quantum adversaries to attack.