Is there a way to prove equality of plaintext that was encrypted using different public keys? Imagine if Alice encrypts message to Bob (using public key $P_{bob}$) and then Bob encrypts the same message to Carol (using $P_{carol}$). Is there a way for Bob to prove that:

$P_{carol}$ was indeed used
Message is still the same that Alice passed to Bob.

Note1: Both ciphertexts and public keys are visible for everybody who needs to verify this proof.
Note2: Public keys and messages are new for every encryption so deterministic encryption is ok, but public key cryptography has to be used

It looks similar to this topic, but there only one public key is used:
Is there a public key semantically secure cryptosystem for which one can prove in zero knowledge the equivalence of two plaintexts? (comments from D.W and tylo are very helpful)

Obvious thought that comes to mind is to use commutative encryption, so everybody will be able to check whether $E_{bob}(E_{carol}(M)) == E_{carol}(E_{bob}(M))$ having $E_{carol}(M)$ and $E_{bob}(M)$ and access to $P_{bob}$ and $P_{carol}$. But then only deterministic encryption would work ($E_{bob}$ is encryption using $P_{bob}$).
The other solution that comes to my mind is using ZKP for DH 4-tuple if homomorphic encryption is used (for example El-Gamal - non-interactive proof is described here). So there is a way to prove that ($g$, $h$, $g^r$, $h^r$) is DH 4-tuple (where $h$ is public key, $r$ - random number, $g$ - generator of the group). In our case ciphertexts correspondent to message $M$ are $c_1=(g^{r_1}, M*P_{bob}^{r_1})$ and $c_2=(g^{r_2}, M*P_{carol}^{r_2})$.
If to consider that $r_1=r_2=r$ (i.e. Alice also told Bob $r_1$) we can divide $c_1$ to $c_2$ and receive $(\frac{P_{bob}}{P_{carol}})^r$. Since everybody knows $P_{bob}$ and $P_{carol}$, Bob is able to create ZKP that $(g, (\frac{P_{bob}}{P_{carol}})$, $g^r$, $(\frac{P_{bob}}{P_{carol}})^r)$ is DH 4-tuple. In this way he can proof both statements (I believe :) ) Non interactive proof can be made. Having $c_1$ and $c_2$ Bob does:

selects random $r_3$
calculates $u=g^{r_3}$ and $v=(\frac{P_{bob}}{P_{carol}})^{r_3
}$
Calculates hash $d = H(u || v) $
Calculates $z=d*r+r_3$
Publishes $(u, v, z)$

Everybody is able to verify the proof $(u, v, z)$ doing:

Calculating $d = H(u || v)$
checking that $g^z == (g^r)^d * u$
$(\frac{P_{bob}}{P_{carol}})^z ==({\frac{c_1}{c_2}})^d * v $

Are there any other methods?

Here is an answer to your question using a zero knowledge proof in the case of Elgamal encryption. The biggest difference between this solution and your own is that Alice does not need to tell Bob the value of $r_1$ anymore. This makes the zero knowledge proof more complicated.

Setting the scene:

Let $\mathbf{G}$ be the group of prime order $p$ in which the Elgamal encryption is taking place. Let $(g_1,h_1)$ be Bob's public key, and $s_1$ be Bob's private key, so that $g_1 = h_1^{s_1}$. Let $(g_2,h_2)$ be Carol's public key.

Let $(c_1,d_1) = (mg_1^{r_1},h_1^{r_1})$ be the ciphertext that Bob receives from Alice. Bob doesn't know $r_1$, but he does know that the decrypted message is $m = c_1 d_1^{-s_1}$.

Let $(c_2,d_2) = (mg_2^{r_2},h_2^{r_2})$ be the ciphertext that Bob sends to Carol.

Bob will use a zero knowledge proof to prove the following without leaking any information about $s_1$ and $r_2$:

-$s_1$ is the secret key corresponding to $g_1,h_1$

-$d_2 = h_2^{r_2}$, meaning that $r_2$ is the randomness used for $(c_2,d_2)$

-$c_2 = c_1 d_1^{-s_1} g_2^{r_2}$, meaning that the message obtained by decrypting $(c_1,d_1)$ with $s_1$ is the same as that encrypted in $(c_2,d_2)$

The Zero Knowledge Proof

Proof Statement: $(c_1,d_1),(c_2,d_2),g_1,h_1,g_2,h_2$

Bob picks $b_1,b_2$ uniformly at random from $\mathbb{Z}_p$. Bob computes $G_1 = h_1^{b_1}$, $G_2 = h_2^{b_2}$, $G_3 = d_1^{b_1} g_2^{-b_2}$

Bob computes a hash $x = h(proof statement || G_1 || G_2 || G_3)$ (I think it is necessary to include the statement in your original example too, but need to check).

Bob computes $\bar{s}_1 = s_1 x + b_1$ and $\bar{r}_2 = r_2 x + b_2$.

Bob publishes $(G_1,G_2,G_3,\bar{s}_1,\bar{r}_2)$.

Verification:

To verify, first compute $x = h(proof statement || G_1 || G_2 || G_3)$.

Check that $h_1^{\bar{s}_1} = g_1^x G_1$ (shows $\bar{s}_1$ is a randomised version of Bob's public key)

Check that $h_2^{\bar{r}_2}=d_2^x G_2$ (shows $\bar{r}_2$ is the randomness used in $(c_2,d_2)$)

Check that $c_2^x c_1^{-x} d_1^{\bar{s}_1} g_2^{-\bar{r}_2} = G_3$ (shows that the messages in both ciphertexts are the same)

Security Proof Sketch:

I'll sketch a proof that the underlying interactive ZKP where the verifier picks random $x$ from $\mathbb{Z}_p$ is secure, and then rely on the well-known fact that replacing this with the hash to get the above gives a secure NIZK protocol will full zero knowledge.

(Completeness) It's easy to see that an honest prover will always convince the verifier by substituting the honestly computed values of $\bar{s}_1,\bar{r}_2,G_1,G_2,G_3,x$ into the verification equations.

(Special Soundness) For the same $G_1,G_2,G_3$, if the prover could produce acceptable proofs with $\bar{s}_1,\bar{r}_2$ and $\bar{s}'_1,\bar{r}'_2$, for two different values $x,x'$, then we could extract Bob's secret key (and hence the message), and the randomness used in the second ciphertext. From the first verification equation, we can compute $s_1,b_1$, the discrete logs of $g_1,G_1$ with respect to $h_1$, such that $\bar{s}_1 = s_1 x + b_1$ and similarly for $\bar{s}'_1$. From the second equation, we can compute $r_2,b_2$, the discrete logs of $d_2,G_2$ with respect to $h_2$, such that $\bar{r}_2 = r_2 x + b_2$, and similarly for $\bar{r}'_2$. Substituting into the third verification equation, we have $\left( c_2 c_1^{-1} d_1^{s_1} g_2^{-r_2} \right)^x d_1^{b_1} g_2^{-b_2} = G_3$. This is a polynomial (in group elements) which is satisfied for two different values $x$ and $x'$, so all coefficients must be equal to the group identity. Taking the coefficient of $x$, we have that $c_2 = c_1 d_1^{-s_1} g_2^{r_2}$. In other words, the decryption of the first ciphertext, when encrypted, gives the second ciphertext.

(Special Honest Verifier Zero Knowledge) Given $x$, the simulator can pick $\bar{s}_1,\bar{r}_2$ uniformly at random from $\mathbb{Z}_p$, and then compute $G_1,G_2,G_3$ using the verification equations.


Is my implementation of a PRG at least intuitively secure? I've devised a PRG using Bezier curves , constructed with Bernstein polynomials, and I was wondering if you guys could help me with some suggestions or constructive criticism.

Basicly I take a random set of 2d points(seed), used as control points for a number of concataned Bezier curves, this makes up my space. The generated space of the curves is alot greater than the set of initial points. When I wish to generate binary output I go through the space, and because of the formula using Bernstein polynomials, each point of the curve is generated with a number of decimals, from wich I extract the raw binary and concatenate a result. It would seem that the binary of the decimals behind the x,y of each point don't give away any indication of the curve.

I keep an index to know how far along the space I've traveled so I don't use the same data again. The original points that will generate the space are random.

I've tested the output with sts. from NIST and it passed everything, but I was told that is hardly enough for a viable PRG. Then I got redirected to stackexchange :)

Any thoughts?

ps: do you guys know any other tests for a prg?

PRNGs are a difficult and hot topic.

Some tests can be found here: What tests can I do to ensure my PRNG is working correctly?

But they do not tell you (or others) if your PRNG is really secure. A PRNG must be build in a way, that a third party is not able to "calculate" former or upcoming PRNG output based on some random data from the PRNG.


Using a hash (like SHA-256) vs AES as the source for pseudo-random values in Feistel network? This question is in relation to Wikipedia article on Format Preserving Encryption

It says the following

  It is also possible to make a FPE algorithm using a Feistel network. A Feistel network needs a source of pseudo-random values for the
  sub-keys for each round, and the output of the AES algorithm can be
  used as these pseudo-random values.

However I was taking a look at an implementation of FPE (Botan Crypto library).   It is based on the scheme FE1 from the paper "Format-Preserving Encryption" by Bellare, Rogaway, et al

In the implementation I think it is using the SHA-256 hash to generate the pseudo-random values.

How does this compare (with respect to security) to the alternative of using the AES algorithm to generate the pseudo-random values?

Are both equally valid methods?

A Feistel network is a way of constructing an invertible permutation from a (possibly non-invertible) function. If the function used is pseudorandom and has a large domain, then 3-4 rounds yields a pseudorandom permutation (3 rounds suffice if the adversary can only ask "compute" queries, and 4 rounds are needed if the adversary can ask "invert" queries). This is the famous Luby-Rackoff result. In the format-preserving constructions, more rounds are needed since the domain of the function can be small and this means that collisions are likely, etc.

In any case, these constructions can use ANY pseudorandom function. Thus, AES truncated to the appropriate output length is fine. HMAC is also very reasonably considered a pseudorandom function. Is plain SHA256 a pseudorandom function? Well, it depends exactly on what you do. If you compute $F_K(x) = SHA256(K || x)$ then this is certainly not pseudorandom due to extension attacks (given $F_K(x)$ it is possible to compute $F_K(x||y)$ for some $y$). However, if you know that you are only using a fixed length, or you encode that length, then it's a reasonable assumption. Personally, I prefer the HMAC assumption if you wish to base yourself on a hash function. However, I think that AES is the best choice (it's also much faster...).


Pseudo random generator vs block encryption, which is faster? If one wishes to encrypt one can either use a pseudo random generator to generate a long sequence and then xor it with plaintext, similarly he can use the seed as key to encrypt the plaintext using block encryption.
If encryption is not of paramount concern, which runs faster, pseudo random generator or block encryption?

I would highly appreciate if there is some survey or report on the running time comparisons.

Dedicated stream ciphers typically are, or at least can be, somewhat faster than constructions based on block ciphers.  (If they weren't, there would be no point in using them, since a block cipher can do everything a dedicated stream cipher can.)  What you gain in speed (and possibly code size), however, you lose in versatility:

A block cipher (in CTR / OFB mode) can be used to build a stream cipher.  There is no simple way to construct a block cipher out of a stream cipher.
Block ciphers can also be used to construct many other useful cryptographic tools, such as MACs and hash functions.  Stream ciphers are typically only good for encrypting streams of data.
In particular, a single block cipher can be used to construct a fully IND-CCA2 secure authenticated encryption scheme.  Stream ciphers do not generally include authentication, and thus cannot protect data from tampering.
Several block cipher modes of operation (most notably CTR mode, but also CBC and CFB to a limited extent) have the useful properties of parallelizability and seekability — that is, the en/decryption of different parts of the data can be done in parallel, and it's possible to start decryption from any point in the data stream.

Because of their versatility, block ciphers like AES are also popular candidates for fast hardware implementation.  If you have a fast block cipher implemented in hardware, there's a good chance that it'll be faster than any dedicated stream cipher you could implement in software.

All that said, some of the fastest dedicated stream ciphers can be very fast, both in hardware and in software, and many are also designed to be very compact in terms of code/circuit size.  If you really only need stream encryption (or random number generation), a dedicated stream cipher may be more efficient than a block cipher.

See also: Difference between stream cipher and block cipher


What are the properties of secure Elliptic Curves? I have heard about the standard elliptic curves called NIST curves. What are the properties of such cryptographically secure elliptic curves?
Are they standardized according to certain protocols? Also, does the attacker get any huge benefits from knowing which curve was used?

For typical protocols like Diffie–Hellman key agreement and Schnorr-type signature,* SafeCurves surveys the modern security criteria for elliptic curve choice.  In these protocols, the adversary is assumed to know the choice of curve; the security comes from criteria of the curve, not of secrecy of the curve.†

The basic criterion is that computing ‘discrete logs’—that is, given a scalar multiple $[n]P = P + \dots + P$ of a known point $P$ on the curve by a secret integer $n$, computing $n$—costs well above $2^{100}$ curve additions.  But there are many other criteria, like twist security, that are not as obvious to an untrained observer, and were not considered in the design of historical standard curves like NIST P-224.

Certain criteria are not about secure vs. insecure curves per se, but rather about fast and secure vs. fast or secure implementations: for example, NIST P-256 does not admit the Montgomery ladder, which is a fast way to compute $x$-restricted scalar multiplication in constant time.  In NIST P-256, you can compute scalar multiplication fast, or in constant time, but not both—so it is tempting to sacrifice security in pursuit of performance when implementing NIST P-256 or choosing an implementation of it, whereas with Curve25519 you can attain both simultaneously using the Montgomery ladder and there is no temptation to sacrifice security that way.

Some of the criteria are relevant to some protocols but not others, for instance because DH key agreement is subject to active attacks that are not relevant in the security model of signatures.  Fortunately, some curves satisfy all the criteria, such as Curve25519, Ed448-Goldilocks, and E-521.  The first two of those are standardized in RFC 7748, which also prescribes a rigid procedure for selecting a curve for a given prime field satisfying all the security criteria and optimizing performance by certain easy heuristics—a procedure which, incidentally, also generates E-521.‡

* SafeCurves does not address more exotic applications like pairing-based cryptography, which necessarily use a different class of curves.

† In the various proposed post-quantum isogeny-based cryptosystems, choices of curves are secret positions in an isogeny graph of curves, but this is a rather different scenario from what is usually known as elliptic curve cryptography today, and as such seems unlikely to be relevant to your question.

‡ The IETF chose to endorse Ed448-Goldilocks rather than E-521 because Ed448-Goldilocks performs better, and even though the theoretical attack costs on E-521 are higher than on Ed448-Goldilocks, the two both have a meaninglessly high ‘security level’ that only serves as a hedge against minor cryptanalytic advances, not to raise actual costs on what is an impossibly expensive attack to begin with.


Can a Password be Derived from a AES key? This thought randomly popped into my head and I have not been able to find a clear, defined answer for it. Given an AES key, lets say an AES-256 key which is derived from a user password, is there any way to analyze the key and reverse engineer the password used to generate the key?

I understand if the key has been revealed and is known to an attacker they already have what they need, but this is a theoretical. Alternatively, a hacker may leverage a weakly protected system, stealing the key for a particular user from that system, reverse engineer the password then hope the user used the same password on a more secure system that the hackers primary goal is to access that.

I apologize if this is an obvious question, I am a software developer trying to break into the security field and attempting to develop my understanding of cryptographic principles.

Thanks!

Given an AES key, lets say an AES-256 key which is derived from a user password, is there any way to analyze the key and reverse engineer the password used to generate the key?

This is really the same problem as password cracking, where the simple strategy of trying statistically likely passwords at very high speed with specialized, massively parallel hardware (e.g., GPUs) has proven to be very fruitful.  This doesn't involve any sort of cryptanalytic attack to reverse the key derivation function, rather just relying on (a) the predictability of real-world passwords and (b) the fitness of GPUs for this sort of task.

If you're not familiar with this topic, this article and the enclosed video are a good primer.


Is RSA key size the size of private key exponent? I have implemented a key pair generation scheme for RSA algorithm. I have taken the length of private key exponent as RSA key size, but then I've got to know that RSA key size is the size of the modulus $n$. Is it wrong to take RSA key size as the size of the private key exponent?

To generate a private key of 1024 bits, I increase the size of private key exponent regardless the modulus $n$.

No, the RSA key size is not the size of the private key exponent. It is customarily the number of bits in the public modulus (which is known as $N$). In other words, the key size is the integer $k$ such that $2^{k-1}\le N<2^k$.

In most implementations (and all implementations conforming to PKCS#1), a private exponent $d$ has size in bits at most the key size $k$, and typically is few bits smaller. Notice that the private exponent is not uniquely defined.

The smallest private exponent is $d=e^{-1}\bmod\lambda(N)$. It is always less than $\lambda(N)$, where $\lambda()$ is Carmichael's function, with $\lambda(N)=\operatorname{lcm}(p-1,q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. The smallest private exponent always has size in bits strictly less than the key size $k$, and typically is a few bits smaller.

Sometime, a private exponent is computed as $d=e^{-1}\bmod\varphi(N)$, where $\varphi()$ is Euler's function, with $\varphi(N)=(p-1)\cdot(q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. That particular $d$ has size in bits at most the key size $k$, often is a few bits smaller, and often is a few bits larger than the smallest private exponent.

Yet other methods to define a private exponent give no maximum for $d$, and only require that $d\equiv e^{-1}\pmod{\lambda(N)}$ (which is the necessary and sufficient condition for $d$ to work), or $d\equiv e^{-1}\pmod{\varphi(N)}$.


How can I prove that a function F isn't a pseudo random function? Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a pseudorandom function. If yes, prove it; if not, show an attack.
$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(1 ∥ x) \tag{a}$$
and
$$F'_k(x) = F_k(0 ∥ x) ∥ F_k(x ∥ 1) \tag{b}$$

I don't want the solution: I want to understand how I can solve this type of exercise.

your title asks "How to prove that a function F isn't a pseudo random function", in your question case (b) is not PRF which is easy to prove. function $F'$ is PRF if for all PPT distingushers $D$, success probability of $D$ distinguishing $F'$ from random function be negligible. So for proving that function $F'$ is not PRF it suffices to construct one distinguisher (which queries to its oracle and look for non-random patterns) with non-negligible success probability.

In contrast case (a) here is PRF, which is harder to proof. for proving function $F'$ is PRF as @fkraiem mentioned suppose $F'$ is not PRF and $D'$ is distinguisher for $F'$ then construct an algorithm $A$ which breaks some assumption (Distingush $F$ from random function here breaks assumption of $F$ being PRF).


why do we take computational distinguishability over ensembles In the Cornell lecture notes, computational indistinguishability is defined as

Definition 69.4 (Computational Indistinguishability). Let $\{X_n\}_n$
and $\{Y_n\}_n$ be ensembles where $X_n$,$Y_n$ are distributions over $\{0, 1\}^{l(n)}$ for some polynomial $l(·)$. We say that $\{X_n\}_n$
and $\{Y_n\}_n$ are computationally indistinguishable
if for all non-uniform p.p.t. $D$ (called the “distinguisher”), there
exists a negligible function $e(·)$ such that $∀n ∈ N$

$Pr[t ← X_n, D(t) = 1] − Pr[t ← Y_n, D(t) = 1] < e(n)$
My question is, why do we need ensembles of distribution? Why not just define it over two distributions $X$ and $Y
$?

Why not just define it over two distributions $X$ and $Y$?

Because this is an asymptotic definition (using a negligible function explicitly).
If you were to only consider two fixed distributions, there would be no scaling with the security parameter (and thus the involved lengths) possible. This is why we use ensembles, parametrized by the value of the security parameter $n$.


Encoding multiple fields with same AES key and vector? I'd like some advice on cryptography best practices. I need to store on my web app the users' credentials (login & password) for 3rd-party sites.

I'm using AES-256 with random key and initialization vector (provided by the Net 4.5 framework, if that's relevant), and store the encrypted data in completely different system than the key and vector.
Along with the encrypted data record there's the id of the key/vector record in the other system. My question is, is it OK to use the same key and vector to encrypt the login and the password, which are encrypted and stored separately? Or that's a vulnerability and I absolutely need specific key/vector for each?

Speaking in broad strokes, reuse of the key is fine - reuse of the IV: not fine.  From wikipedia: "Properties of an IV depend on the cryptographic scheme used. A basic requirement is uniqueness, which means that no IV may be reused under the same key".  You also need to decide on a mode of operation, as different modes will dictate different requirements for the IV/nonce.


Random salt and PBKDF2 key Suppose I wrote a function $$(salt,IV ) = \text{keyIVGenerator}(passwd)$$ which generates a random salt of size 32-bytes and a random Initialisation Vector (IV) of size 16-bytes. Then, use a  Key Derivation Function (KDF) like PBKDF2 to generate a key of length 32 bytes (dkLen=32).
$$key = PBKDF2(password, salt, deLen)$$
I created a function  $$ c = encryption(key,data,IV)$$, assume that padding of data (using aes CBC) is correctly done and logic is right.
When I ask the user for encryption and data, I pass the password to the function $keyIVGenerator(passwd)$ to get the $IV,key$, and $passwd$ them to the $encryption(key,data,iv)$ along with data. The encryption works.
And now suppose I have to decrypt the data I will need to pass the same key as generated by PBKDF2 for encryption to decrypt my data. The iv was prepended to the ciphertext.
But what about the salt.
If I pass the password requested from the user to $keyIVGenerator(passwd)$ it will generate a new key with the new random salt, hence the data won't be decrypted.
Am I supposed to prepended my salt to the ciphertext too? Should I keep a database of salts?
How do I generate the same key from PBKDF2?

Yes, generally the salt is prefixed to the ciphertext.
In principle you always generate a new key for each salt, so you might not need the IV. I would however use the output of PBKDF2 to create a randomized IV and key just to be sure (e.g. using SHA-512 and then use the leftmost 32 for the key and the next 16 bytes for the IV).
It is also possible to use HKDF on the output of PBKDF2 to split off both the data key and IV from the generated intermediate key (that's more neat, but also harder to implement).

Notes:

It would be a good idea to use an authenticated mode such as GCM. In that case the IV should be 12 bytes.
dkLen is specified to be in bits, not bytes - at least in the standard. Key sizes generally are.
A salt of 16 bytes is generally plenty, but 32 bytes is OK too (it should still fit in a single block of even SHA-256, so it will likely not influence the work factor created by the hash function and iteration count).


Prove that shares can reveal a seceret key. in a secret sharing scheme I am trying to build a cryptographic system that has several components and ran into a problem with a secret sharing scheme.

Let $v$ be a value we are interested committing to.
I generate a commitment $P = aG + vH$ where $a\in \mathbb{Z}_q$ , $G$ and $H$ are generators of that group (Pedersen commitment scheme, if given $a$ someone can derive the value $v$).

Now lets assume I want to break $a$ (lets call it the blinding key) to $n$ shares using  shamir secret sharing scheme where $k$ shares can produce $a$ ($k,n$ sharing scheme).
so if $P$ is publicly known, is there a way where players who received a share can verify that the share they got actually produce $a$ without uncovering $a$? meaning that they know the combined shares can generate the blinding key.

I know that there exist a scheme for verifying that all shares are derived from the same polynomial (Paul Feldman's scheme) but what can prevent  the possibility of an adversary calculating and distributing shares derived from some randomly generated and unrelated polynomial (where the secret is $c\neq a$)?

The obvious way to do this is to do a secret derivation on committed values, and have the dealer show that derived committed value is the same as the value he originally committed to.

For this, I'll assume that the secret sharing scheme is over the prime field $GF(q)$.

The dealer publishes the commitment $P$, and remembers the commitment value $v$.

And, when the dealer generates the share $i$ (for participant $i$), it generates the share id (which we'll assume is $i$), actual share value $a_i$ (which is the value of the secret polynomial evaluated at the share id $i$) and a commitment value $v_i$.  It then gives the values $a_i, v_i$ to share holder $i$ secretly, and publishes the commitment $P_i = a_iG + v_iH$, as well as the share id $i$.  The dealer also remembers all the $v_i$ values.  When a shareholder gets his share, he can verify that his public commitment is consistent with the secret values he got.

Then, we select $k$ participants (you've already proved that the shareholders hold a consistent secret, and so it doesn't matter which set we pick).

Then, the actual secret value is $a = f_1a_1 + f_2a_2 + ... + f_ka_k \bmod q$, for some publicly computable values $f_1, f_2, ..., f_k$ (which depends on the actual set of shares).  Hence someone, possibly the dealer, computes the value:

$$Q = f_1P_1 + f_2P_2 + ... + f_kP_k - P$$

which everyone can verify, as all the parameters are public.

The dealer can express this as:

$$Q = \sum f_i(a_iG + v_iH) \ - (aG + vH) = (\sum f_ia_i - a)G + (\sum f_iv_i - v)H$$

Where the dealer knows the values $f_i, v_i, v$.  Hence, if $a = f_1a_1 + f_2a_2 + ... + f_ka_k$, then the dealer can generate a ZKP that he knows the discrete log of $Q$ to the base $H$; if not, then he cannot generate such a proof (because, if it knew that discrete log, it could (assuming it also remembered $a, a_i$) compute the discrete log of $G$ to the base $H$, which we assume was a hard problem.


How close to pure math is cryptographic theory? I'm an undergraduate math student, and I'm thinking about topics for an undergraduate thesis. I have an interest in topological spaces and number theory, but I'm having trouble identifying a relationship between those and cryptographic theory. In On Post-Modern Cryptography, Goldreich talks a lot about rigorous analysis. But it's still not giving me a clear understanding of what type of math a person doing research in theory does in general. Is cryptographic research in the same line as formal mathematical proof? Is there a need for abstract mathematics in modern cryptography? I can program, but application is not really my interest and it would take too long in my degree to add a formal computer science aspect.

Is cryptographic research in the same line as formal mathematical
  proof?

Not always, but the large area of provable security is. Provable security is (essentially) the task of formally proving theorems about crypto, which will in general be of the form "if this mathematical hypothesis is true, then this cryptographic primitive is secure against a given type of attack". Each time a new primitive is suggested to address some security requirement, it comes with proofs of theorems providing hindsights regarding the security of the scheme (though that's not always the case, especially with papers from the early days of crypto). An important part of cryptography is also about analyzing and implementing cryptographic protocols and primitives, but that does not mean all cryptographers do also implement crypto. In many labs, 95% of the work will involve essentially pen-and-paper analysis - although even the most theoretical works sometimes lead to result that one might want to implement, if only to see how efficient it is.

  Is there a need for abstract mathematics in modern cryptography?

Yes and no. A knowledge of the formalism in some area of abstract mathematics can help a lot into understanding and studying crypto, but in most cases, you will not need a deep knowledge of the most advanced results in abstract mathematics. For example, most results you would learn from an advanced math course about elliptic curves would be outside the scope of the background needed to understand elliptic-curve-based cryptography. Similarly, you would not need extremely advanced courses on algebra to understand the notions used in crypto (essentially, standard algebra results on finite fields and additive groups suffice for many things, plus some more crypto-related algebra result).

However, as is common in theoretical computer science, mathematics often show up unexpectedly when studying some problems, and relatively deep mathematical results can prove useful in the analysis of some cryptographic primitives. The first example that comes out of my head is this recent paper from ePrint (the crypto archive) which establishes lower bounds for a primitive known as order-revealing encryption (an encryption scheme that does not hide the result of the comparison between encrypted messages), and relies on (an extension of) a theorem of Erdös on tournament graphs.

The high level bit is: studying math is a very pertinent choice if you're planning to do theoretical crypto later, because being at ease with mathematical formalisms will make you way more comfortable than many with crypto. It is widely acknowledged in crypto that the field would benefit from having more mathematicians studying this area. However, do not expect your knowledge of advanced math results to be crucial to your work in crypto on a daily basis, and theoretical crypto in itself remains a science with its own formalisms and practices that you would have to study if you want to work in the field.


Will rehashing an SHA256 hash continually, eventually produce every possible value? So let's say you had infinite time and energy. You have a hashed string of some sort. Because you have infinite time and energy, you can produce a collision(or the original value) easily enough. But, there is a problem. The hashed string was hashed an unknown amount of times. (ie, it may have been produced by sha256(sha256("foobar")) or by sha256(sha256(sha256(sha256("foobar"))))).

You were given a hint by your adversary though. They give you (say) 10 strings, of which one is the initial value that is hashed.

Is it possible to determine with absolute certainty that you chose the correct string? Is it possible that hashing "foobar" recursively an infinite amount of times will eventually yield any arbitrary hash value?

Although my question is about SHA256, I'd be equally curious of other hash algorithms as well

Is it possible that hashing "foobar" recursively an infinite amount of times will eventually yield any arbitrary hash value?

I very much doubt it. A simple demonstration of this logic can be done through the birthday paradox. Suppose we log each successive recursive SHA-256 on "foobar" in a table. We can ask ourselves what the probability is that our next recursion will collide with any item already in the table?

Assuming SHA-256 behaves as a random function the probability will exceed 50% just after we've tried approximately $2^{128}$ recursions. However, since we know that SHA-256 is not actually a random function, as soon as a collision is found it will then fall in to a cycle. Thus, approximately 0% of the total hash value space will be covered.

The string "Foobar" would need to be a special case where each hash value is visited exactly once. I believe this property is called being a "generator" but I'm happy to be corrected on that point.

  Although my question is about SHA256, I'd be equally curious of other hash algorithms as well

I'd expect that this analysis would apply to any secure cryptographic hash.


RSA Signature Verification Implementation on Cortex M0 I have to implement RSA Signature Verification procedure (RSA-2048) on a Cortex M0 based MCU. My budget is 15kB Flash and 2-4kB Flash RAM.

Is it even possible to do RSA on a low end MCU based on Cortex M0?

As pointed by CodesInChaos, you'll need to know the padding used; depending on application that could be RSASSA-PKCS1-V1_5, or RSASSA-PSS, or some of the three schemes of ISO/IEC 9796-2, etc.. Hashing, and padding check, are a significant part of the code.

In any case, yes, it is possible to implement RSA-2048 signature verification on a Cortex-M0 based MCU, with much less than 15 kB code and 2 kB RAM. That's extremely ample even including hashing, and padding check.

With tight coding we are talking 2 to 5 kB code (depending on hash and padding, including code for RSA and SHA-1, SHA-256 or even SHA-512) and at most 1.4 kB RAM (temporarily used in stack or heap, not dedicated) including public key and signature (assumed already properly aligned bytes).

To give an order of magnitude of the speed achievable: for $e=65537$, a simple but good implementation of the RSA public function is dominated by a core loop executed about $17\cdot(2048/32)^2$ times, comprising 8 MULS, 3 memory reads, 1 memory write, and like 16 other single-cycle operations; thus, on a 40 MHz CPU running without code wait states, like 70 ms with single-cycle MULS (or 500 ms with the 32-cycle MULS of some Cortex-M0 variants).

Speed (and code density) will also depend on

using assembly in the critical loops, rather than C which typically generates sub-optimal code for RSA arithmetic (notably, because C only has a tortuous idiom for carry propagation);
not using Montgomery arithmetic, which introduces complexities hardly justifiable for RSA signature verification and common (low) public exponents $e$;
value of public exponent; $e=3$ can be like 8 times faster than $e=65537$ (for short messages);
size of what's signed (influencing hash time);
care of programming; this is not easy!

An archetypal implementation of modular exponentiation $Y\gets X^e\bmod N$, geared for RSA signature verification with typical parameters including moderate public exponent $e>0$, optimized for low RAM footprint, code simplicity, and speed, can uses left-to-right binary exponentiation at the top level:

$Y\gets X$
set $j$ to the number of bits in $e$, that is $\lceil\log_2(e+1)\rceil$
while $j>0$

$Y\gets Y\cdot Y\bmod N$
$j\gets j-1$
if bit $j$ in the binary representation of $e$ is set, that is if $\lfloor e/2^j\rfloor\bmod 2\ne0$

$Y\gets X\cdot Y\bmod N$

This requires 2 modular multiplications for $e=3$, and 17 for $e=65537$.

In an implementation optimized for size (and simplicity) we'll have a single piece of code to perform $Y\gets X\cdot Y\bmod N$, and we'll replace argument $x$ by $Y$ when performing $Y\gets Y\cdot Y\bmod N$. Our modular multiplication will use more or less clever variants of the ‘classical’ algorithms commonly used by hand in decimal, only using base $2^w$ instead of base 10, where $w$ is some convenient word width. We note $n$ the number of $w$-bit words in $N$. Execution time will be $\mathcal O(n^2)$. On Cortex-M0 we'll probably use $w=32$ (or $w=16$ which would give simpler and shorter code, with only moderate speed penalty for the Cortex-M0 variant with 32-cyle MULS, but much more in proportion for the variant with single-cycle MULS).

The simplest option for modular multiplication is algorithm 14.28 in the Handbook of Applied Cryptography, which performs multiplication (using multiplication per algorithm 14.12) followed by modular reduction (using Euclidean division per algorithm 14.20 ignoring the quotient, or Barrett reduction per algorithm 14.42). This is has some drawbacks, though:

each modular multiplication requires $\mathcal o(2n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops for the multiplication, and modular reduction requires as many; when other algorithms reduce that to a total of $\mathcal o(3n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops (the same asymptotic cost as a good implementation of the equivalent of modular multiplication in Montgomery arithmetic);
the intermediary result is twice as wide as $N$, which consumes some RAM;
the index in this intermediary result is not the same as the index in other operands, thus we have two indexes to maintain.

These three drawbacks can be avoided without using Montgomery arithmetic (which requires pre and post computations that increase code size, and have significant speed penalty for low $e$), as follows.

For any integer $Z$, we note $Z_j$ the $j$th digit of $Z$ in base $2^w$, that is
$$Z_j=\left\lfloor{Z\bmod 2^{(j+1)\cdot w}\over2^{j\cdot w}}\right\rfloor$$
so that
$$0\le Z<2^{k\cdot w}\implies Z=\sum_{0\le j<k}Z_j\cdot2^{j\cdot w}$$
$N_0$ is odd since $N$ is odd, and $N_{n-1}>0$ since $n$ words are required to write $N$. We define (and precompute early, e.g. as a preliminary of exponentiation) $M_j=2^w-N_j-1$ for $0<j<n$ and $M_0=2^w-N_0$, corresponding to $M=2^{n\cdot w}-N$; and
$$H=\min\left(\left\lfloor{2^{5\cdot w}\over N_{n-1}\cdot2^{2\cdot w}+N_{n-2}\cdot2^w+N_{n-3}}\right\rfloor,2^{3\cdot w}-1\right)$$
as the corresponding $H_2$, $H_1$, $H_0$, which will help in quotient estimation.

The general sketch of modular multiplication goes:

$T\gets Y_{n-1}\cdot X$ over $n+1$ digits, using a loop scanning the $X_j$ and $T_j$ by increasing index;
for $i=n-2$ downto $0$ (a loop invariant being that $T<N\cdot2^w$)

find an approximation $q$ of the next quotient chunk $\left\lfloor{T\cdot2^w+Y_i\cdot X\over N\cdot2^w}\right\rfloor$, erring up by at most $1$ by excess, and with $0\le q\le2^w$ (which it turns out is possible using a constant number of multiplications and additions involving $T_n$, $T_{n-1}$, $T_{n-2}$, $X_{n-1}$, $X_{n-2}$, $Y_i$, $H_2$, $H_1$, $H_0$);
$T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, over $n+1$ digits and an extra one $t$ for what would have been $T_{n+1}$, using a loop scanning the $X_j$, $M_j$ and $T_j$ by increasing index; most of the time is spent in this single loop with $q\ne2^w$ (the special case $q=2^w$ must be detected and handled separately, but is faster than the general case);
if $t<q$ (which is rare and will thus consume negligible time), then $q$ was one higher than it should have been:

$T\gets T-M$, using a loop scanning the $M_j$ and $T_j$ by increasing index;

$Y\gets T\bmod N$ (one way to do this is as an extra iteration of the above, with a virtual $y_{-1}=0$, and mapping the $T_{j+1}$ of the result to $Y_j$).

The essential thing is that we manage to perform multiplication and modular reduction in the same loop doing $T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, with the quotient digit $q$ on a single word, using operations with fair native support (word multiplications and additions with carry; that's even though each full $32\times32\to64$ multiplication will require four MULS). As often in crypto, and especially crypto implementation, the devil is in the details.

Doing signature generation with appropriate speed and security is much more difficult. That's going to be like 50 times slower than signature verification with $e=65537$, using the CRT and regular two-factors RSA (and otherwise comparable code for the two modular exponentiations). The code will be significantly larger (though still feasible within the code and RAM budget). For some padding schemes including RSASSA-PSS and ISO/IEC 9796-2 scheme 2, a TRNG with some strength will be required, making the code's interfaces much more complex. Most importantly, it will be practically impossible to hide the required secret key from a JTAG debugger or the like, and even quite hard to safeguard it from timing and other side-channel attacks.


Why is encryption slower than decryption in elliptic curve cryptography (ECC)? While performing encryption using public key and decryption using the private key, I am always finding that encryption takes more time than decryption in elliptic curve cryptography (ECC). It's the same for signing and verifying. The key is 60 bytes.

Is this the normal behavior or I am using the wrong implementation of ECC?

If this behavior is normal then what is the reason behind it?
Thanks in advance.

It appears that the public-key anonymous encryption scheme in question is ECIES.  ECIES encryption requires generating a single-use key pair and doing a DH key agreement with it, while ECIES decryption only requires doing a DH key agreement and so should cost considerably less than encryption.

Specifically, the sender knows the recipient's public key, $A$, a point on an elliptic curve.  The sender picks an ephemeral secret scalar $t$ and computes $T := [t]G$, where $G$ is the standard base point on the curve; then the sender computes $k := H([t]A)$ and uses $k$ as the key for a symmetric authenticated cipher.  Finally, the sender sends $T$ alongside the authenticated ciphertext.  This operation requires computing two scalar multiplications: $[t]G$ and $[t]A$.

The recipient knows the secret scalar $a$ such that $A = [a]G$, and can recover $$H([a]T) = H([a][t]G) = H([a\cdot t]G) = H([t\cdot a]G) = H([t][a]G) = H([t]A) = k,$$ with which they can then decrypt the authenticated ciphertext.  This operation requires computing only one scalar multiplication: $[a]T$.

So it is to be expected that the encryption operation would cost more than the decryption operation.  In a naive implementation—and I would not be surprised if libgcrypt, as the software you cited uses, is naive—encryption will cost approximately twice as much as decryption.  It could be made faster in a less naive implementation by using a precomputed table for the fixed-base $t \mapsto [t]G$ computation, but encryption will still be slower than decryption.

The signature scheme in this library is probably ECDSA.  Making a signature with ECDSA costs one fixed-base scalar multiplication, while verifying a signature costs one double-base scalar multiplication, so verification should cost a little less than twice what signing costs.

Specifically, the verification equation for a signature $(r, s)$ on a message $m$ under a public key $A$ is $$r \equiv x\bigl([H(m) \cdot s^{-1}] G + [r \cdot s^{-1}] A\bigr) \pmod n,$$ which requires computing $s^{-1}$, the scalars $H(m) \cdot s^{-1}$ and $r \cdot s^{-1}$, and the double-base scalar multiplication $[\alpha] G + [\beta] A$ where $G$ is the standard base point of order $n$.

The signer, who knows the secret $a$ such that $A = [a]G$, picks a scalar $k$ uniformly at random, computes $r = x([k]G)$, and then solves $k \equiv H(m) \cdot s^{-1} + r \cdot s^{-1}$ for $s$ with one inversion and two multiplications modulo $n$.

That said, ECDSA is about the stupidest elliptic curve signature scheme around—it was designed as it was in order to deliberately avoid patents that have long since expired on more sensible schemes.  You should use Ed25519 instead.


Are skeleton keys possible for ECCDSA? As alluded to here (split-key vanity addresses for bitcoin), ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public keys $P=P_1+P_2$. Thus, given a key pair it is trivial to construct all public keys that are integer multiples of that public key $P_n \equiv n\cdot P \pmod N$. Does this mean there is a skeleton key with public key $1$ that could derive all keys? Or at least "low numbers" that can be used to crack public keys that are very "composite"? Of course since it is infeasible to obtain the secret key to any given public key that's probably pure theory, but one worth much more to invest in than a single specific target...

ECCDSA-keys can be merged such that the sum of two private keys $S=S_1+S_2$ yields a public key which is the sum of the respective public keys $P=P_1+P_2$.

This is true, however it doesn't mean what you think it means; the $+$ operators in the two equations are two different operations.
The first one is simple addition (modulo the order of the elliptic curve group).  However, the second is elliptic curve addition, which is not at all addition modulo some number.

Thus, given a key pair it is trivial to construct all public keys that are integer multiples of that public key $P_n \equiv n\cdot P \pmod N$.

Nope; one can certainly compute $P_n = n \cdot P$, where $\cdot$ is elliptic curve multiplication, that is, short hand for $n$ copies of the point $P$ added together, however the actual values of $P_n$ are 'unpredictable' in the sense that, if you have a target point $Q$, it is a hard problem to find an $n$ such that $Q = P_n = n \cdot P$ (or rather, we hope that's a hard problem; if it isn't, all elliptic curve cryptography falls apart).

Does this mean there is a skeleton key with public key $1$ that could derive all keys?

No, or at least, we hope not.  If there is an elliptic curve point $1$ for which solving $Q = n \cdot 1$ was an easy problem, at least solvable a nontrivial part of the time (and not easy in the sense that "it hardly ever exists"), then again, all elliptic curve cryptography falls apart (and we don't need to know the private key corresponding to $1$).

Of course since it is infeasible to obtain the secret key to any given public key that's probably pure theory, but one worth much more to invest in than a single specific target...

Actually, it can be proven that the problem "given this large number $k$ of public keys, find one public key (and we don't care which one)" is not anymore difficult (that is, no more than an addition $O(k)$ work effort) then the problem "given this public key, find the private key".


Using YubiKey to store a PIN-protected secret for disk encryption I want to store a secret on YubiKey and use it for disk encryption. It's crucial that it be PIN protected. There are a limited number of PIN tries, and after three attempts the YubiKey would be blocked (self-destructed).

All the solutions I have found (like this one) are based on a HMAC-challenge-response YubiKey application which calculates SHA1-HMAC from the password and mixes the hash to/with the password. It protects against brute-force attack but not against rubber-hose cryptanalysis (waterboarding, etc.).

The problem is HMAC-chal./resp. is not PIN protected, and it seems YubiKey can't store a PIN-protected secret directly.

I found and implemented two solutions based on PIV.

I generate a new RSA 2048-bit key on the secret slot, use the key to encrypt a random secret and store the encrypted secret in the PIV-slot as an object. (certificate is usually stored there).
I have constant encrypted data ("constant data" means actually hardcoded "const char * data = {....3,5,87... }"). I generate a new RSA 2048-bit key on the selected slot. To obtain the secret, I just decrypt the constant data. I could sign the data and use the signature as the secret, but YubiKey mixes some random data into the signature, so it's not deterministic and can't be used.

To make it more secure, I could even drop the public key, so even the public variables of the key become unknown.

I'm convinced (1) is as secure as YubiKey is, but I'm not sure about (2). I like (2) much more than (1) since it doesn't use the objects for something which they are not supposed to be used for.

Is it OK to use RSA this way? Has anybody thought about similar YubiKey usage?

Using 1) along with enabling and forcing the admin pin and potentially card pin.  You can the force touchauth which would force pin to unlock the yubikey and then continue as mentioned in 1)


What exactly is a "garbled circuit"? There are plenty of questions here about the details and how-to's of "garbled circuits", but I have not seen anything that defines what garbled circuits are.

What exactly is a garbled circuit? What are they intended to be used for? What are their limitations?

The tag for garbled circuits just says that they are used in secure multiparty computation. However, this answer states that they're only appropriate for two-party computation?

This question seeks the definition of a "circuit". What is the difference between a circuit and a garbled circuit?

A circuit is just a way to represent a computation. There is nothing specifically cryptographic about a circuit. It just means a straight-line computation (no looping or flow-control constructs) consisting of just operations on bits, like AND, OR, NOT.

A garbled circuit is a way to "encrypt a computation" that reveals only the output of the computation, but reveals nothing about the inputs or any intermediate values. We use the term "circuit" because garbled circuits work by taking the computation you care about, expressed as a circuit, and then doing some cryptographic stuff for each operation (AND, OR, NOT) in the circuit.

If we want to be a little more precise, a "garbling scheme" consists of:

(Garble) A way to convert a (plain) circuit $C$ into a garbled circuit $\widehat C$.
(Encode) A way to convert any (plain) input $x$ for the circuit into a garbled input $\widehat x$. You need the secret randomness that was used to garble the circuit to encode $x$ into $\widehat x$.
(Evaluate) A way to take a garbled circuit $\widehat C$ and garbled input $\widehat x$ and compute the circuit output $C(x)$. Anyone can do this, you don't have to know $x$ or the secret randomness inside $\widehat C$ to evaluate and learn $C(x)$.

I'm simplifying a little bit here. But the main idea of security is that $\widehat C$ and $\widehat x$ together leak no more information than $C(x)$. In particular, they reveal nothing about $x$, yet they allow the computation $C(x)$ to be done (obliviously). This is what I mean by "encrypting a computation".

The main application for garbled circuits is secure two-party computation. Imagine that Alice has private input $x$ and Bob has private input $y$. They agree on some function $f$ and agree that they both want to learn $f(x,y)$, but don't want their opponent to learn anything more than $f(x,y)$. To achieve this, they can do the following (this is Yao's classical protocol):

The parties agree on a way to express $f$ as a (plain) circuit. Alice garbles the circuit $f \mapsto \widehat f$. She sends $\widehat f$ to Bob as well as her own "garbled input" $\widehat x$.
Alice knows how to encode any input for $f$ into a "garbled" input, but only Bob knows his private input $y$. So the parties arrange for Bob to pick up a garbled version $\widehat y$ without Alice learning what $y$ was. This can be done with a primitive called oblivious transfer.
Now Bob has the garbled circuit $\widehat f$, and a garbled input $\widehat x, \widehat y$ for that circuit. He can then run the evaluation procedure and learn $f(x,y)$. He can reveal $f(x,y)$ to Alice.

We can argue that the protocol reveals no more than $f(x,y)$ in the following way:

Alice doesn't see anything other than the final answer $f(x,y)$ in this protocol (the security of oblivious transfer ensures that she learns nothing in step 2).
Even though Bob sees $\widehat f$, $\widehat x$ and $\widehat y$, the security of garbled circuits ensures that these values don't reveal anything beyond $f(x,y)$.

This approach works when Alice & Bob are semi-honest (i.e., they follow the protocol as instructed). But when Alice is malicious she can garble some other function $f'$ instead of the $f$ that they agreed upon. So other things need to be added to the protocol to prevent this from happening, when we want security against malicious adversaries.

Reference material:

The Yao Construction and its Proof Of Security
 (video), Yehuda Lindell
A Proof of Yao's Protocol for Secure Two-Party Computation, Yehuda Lindell & Benny Pinkas
Foundations of Garbled Circuits, Mihir Bellare, Viet Tung Hoang, Phillip Rogaway
A Brief History of Practical Garbled Circuit Optimizations, a video of mine. The first several slides cover the "classical" construction of garbled circuits.


UKS attack on KEA protocol I'm trying to understand the UKS attack on KEA protocol.

This is described in this paper: Security Analysis of KEA Authenticated Key Exchange Protocol

So to summarize:

KEA protocol:

UKS attack on KEA:

"$\mathbb{M}$ registers a public key $g^a$ of some
honest party $\mathbb{A}$ as $\mathbb{M}$'s own public key. Then $\mathbb{M}$ intercepts a key-exchange session between $\mathbb{A}$ and some other honest party $\mathbb{B}$ and at the same time starts a session between $\mathbb{M}$ and $\mathbb{B}$. Now $\mathbb{M}$ forwards ephemeral public key $g^x$ from $\mathbb{A}$ to $\mathbb{B}$ and
ephemeral public key $g^y$ from $\mathbb{B}$ to $\mathbb{A}$. Since $\mathbb{M}$ has the same public key as $\mathbb{A}$,
both $\mathbb{A}$ and $\mathbb{B}$ will compute identical session keys, however they participate in
two different key-exchange sessions. $\mathbb{B}$ participates in a session with $\mathbb{M}$ while $\mathbb{A}$
participates in a session with $\mathbb{B}$. Finally, $\mathbb{M}$ reveals a session key of one of the sessions and announces the other session as a test session. Given a challenge key, $\mathbb{M}$ compares it to the revealed key. If they are the same, $\mathbb{M}$ decides that the
challenge is a correct key for the test session and if different, $\mathbb{M}$ decides that the challenge key was chosen at random. The demonstrated attack breaks AKE security against a weak adversary (who can only reveal session keys)."

The thing that I don't understand in the attack description above, is the notion of "challenge key". It is said that the attacker $\mathbb{M}$ reveals a session key of one of the sessions, and then pick a challenge key to guess the key of the test session. But, I thought the key is the same in the two sessions so I don't understand what $\mathbb{M}$ want to guess? Secrets $a$ and $b$?

I think I am missing something, if someone could describe me in detail the attack it would be very nice. Thank you in advance.

Some background on formal key-exchange models

The goal of a key-exchange (KE) is to establish a session key between two parties. Naively, we could say that a KE is secure if no adversary will be able to figure out the session key (in full) established between two honest parties. However, in formal security models we take this a bit further and insist that the adversary should learn nothing about the session key, i.e., the adversary should not be able to glean any partial information about the session key from observing (and possibly interfering with) the KE.

This is formally captured by challenging the adversary on a target session of its choice. The challenge consists of first flipping a secret bit $b$ . If $b$ comes up as 0, then we return the actual session key to the adversary, while if it comes up as 1, then we return a randomly drawn key of the same length (completely independent of the KE). Now the adversary is supposed to guess which key he was given: real or random? If he cannot guess which key he was given with much better probability than $1/2 $, then we say that the KE is secure. This "game" is completely artificial of course, but it nicely covers the idea that the adversary should learn nothing about the key, and is an example of the kind of "over-provisioning" present in formal security models.

In addition, we also allow the adversary to reveal the session keys of sessions unrelated to the target session (if we allowed the session key of the target session to be revealed, then the "game" above would ofc be completely trivial to win). What unrelated means can be quite technical to formulate, but intuitively it means that if $A$ and $B$ runs a KE between them, then this is unrelated to the KE session $A$ established with $C$ for instance, (or $B$ with $C$, or $D$ with $E$, etc...). Thus, if the attacker picks the $A \longleftrightarrow B$ exchange as its target, then it should still be allowed to reveal the session key from the $A \longleftrightarrow  C$ exchange. If the KE is secure, then learning the session key from the $A \longleftrightarrow  C$ exchange should not help the attacker learn anything about the session key in the $A \longleftrightarrow B$ exchange.

The UKS attack

In the UKS attack, there are two formally (in the sense of the security model) unrelated KE sessions: $A \longleftrightarrow B$ and $M \longleftrightarrow B$. This allows the adversary to reveal the session key from one, and still pick the other as its target session.

  But, I thought the key is the same in the two sessions...

And this is exactly where the attack comes from! In practice these two exchanges are not unrelated at all, so when the adversary reveals the session key from, say, the $M \longleftrightarrow B$ session, then it also knows the session key of the $A \longleftrightarrow B$ session.
From the point of view of the formal security model, the $A \longleftrightarrow B$ session is still a considered a valid target, so $M$ can trivially win the game (i.e., guess the value of the secret bit $b$).


plain textbook RSA signature with a fixed format input We have an old system using the following algorithm related to authentication:

input: a fixed format integer (hex): <user-id>0000f000<device-id>

user-id: 4 bytes
device-id: 4 bytes

algorithm: textbook RSA 2048, sign with (N, d).

and assumes that an attacker can request limited times (5 times per account per day) with arbitrary device-ids, or try with different user-ids.

Update

sign with (N, d), not (d, e), already updated above;
the background is, logged-in users can apply for usage of a device, if the device is not in use, the user will get a QR code containing the info of the signature. The device will check it (user-id and device-id), if succeeded, the device will unlock automatically.

Question: is it possible that an attacker without login can generate a QR code to unlock any device (device-id is right on the device, and is a random number each time)?

by the way, the device does not deserve much cost. We consider it is not safe when there is an easily-adopted hacking method. And also ignore the case that one can remember the corresponding QR code.

That signature system is insecure assuming that the adversary

can obtain a few signatures for <user-id> and <device-id> which s/he can choose (with perhaps <user-id> constrained, e.g. in a list),
is deemed to succeed if creating a valid signature for some <user-id> for which s/he was not given signature (perhaps with some constraint) and <device-id> s/he can choose,
knows the public key $(N,e)$.

In a simple form of the attack, the adversary restricts to suitably smooth values of $m_i=$<user-id>0000f000<device-id>, and finds a set of these $m_i$ and associated $k_i\in\mathbb Z$ (with $k_0=1$, $k_i\ne0$) such that
$$1=\prod m_i^{k_i}$$
which, when there are enough smooth $m_i$, essentially reduces to solving a system of linear equations (obtained by considering the multiplicity of each prime factor of each smooth $m_i$). It is then easy to compute the signature $s_0$ for $m_0$ from the signatures $s_i$ for other $m_i$, as
$$s_0=\prod_{i>0}s_i^{-k_i}\bmod N$$

Improvements replace the constraint $k_0=1$ with $\gcd(k_0,e)=1$, and exploit very low $e$ like $e=3$, by noticing that a signature can still be forged if the linear equations on multiplicities are satisfied modulo $e$.

How hard the attack is depends primarily on the width of the $m_i$ (here modest with at most 96 bits, perhaps 65 or 48 with enough freedom <user-id>) and on the maximum number of signatures that can be obtained; on the freedom there is on the choice of <user-id>; and to some degree on $e$. Critically, the size of $N$ is immaterial.

The attack is often designated the Desmedt and Odlyzko attack, with reference  to Y. Desmedt and A. M. Odlyzko: A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985. A modern re-exposition is in section 3 of Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi and Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures (in proceedings of Crypto 2009
then Journal of Cryptology, 2016).

Exhibiting actual values of <user-id> and <device-id> allowing the attack is an interesting exercise.


I hashed my bag and in it I put... "Is there a hash for unordered items?" (By items I mean hashable objects.) As an example (with obviously way too short hashes for readability), say I packed my bag and in it I put

a shovel (hashed to S)
a bucket (hashed to B)
a towel  (hashed to T)
a random number (hashed to R)

Now friends of mine (who packed their bag too) and I agree on a game of multiple rounds, and each round consists of the following steps:

someone to be picked at random suggests something that might happen (e.g. going to the swimming pool, hitchhiking, Alien invasion) and what item(s) we might need then
everyone who doesn't have a mentioned item in their bag has to pay a small prize equally shared among those with the item in their bag; this is done for each mentioned item
additional items may be added to each ones bag

Would the game last only one round, we could simply open our bags and confirm the items' presence, but for multiple rounds the person to pick the next hypothetical event would of course choose something for which they'd probably gain the most due to knowing what everyone had in their bags (and maybe guessing the additions). Therefore, the round actually starts with

we'll tell each other something (a hash) and confirm that

and for confirmation, I propose to use a hash H with the following properties:

H can take an arbitrary amount of inputs such as H(shovel) = S, H(shovel, bucket) = E
H is commutative, i.e. H(A,B) = H(B, A)
H is chainable, i.e. H(H(A,B),C) = H(H(A), H(B), C)

(if calling H a hash is still adequate).

With such a hash, we'd simply share the entire bag's hash, and for a given item I we'd have H(bag) = H(I, bag without I), i.e. by providing the remainder's hash there's proof of the item's presence in a bag without requiring to unpack it (that's also why the random number is added, otherwise everyone could figure out when one's bag is fully revealed).

So, long story short, does such a "hash" exist?

Of course, we could simply alphabetically sort our items and use a hash-chain, but for the question's sake let's assume sorting is beyond our capabilities ;)

You could use a hash tree for this purpose. It wouldn't have the properties of your "hash", exactly, but it would work for the game.

Use a secret key to derive individual keys for the leaves, e.g. $k_i = H(k, i)$. Have each leaf be a keyed hash of an item in the bag, $h_i = H(k_i, v_i)$.

Then produce a normal hash tree by hashing two leaf values, then pairs of those values, etc. until you get the root, which you publish. You could add any number of dummy leaves (random values) and make the leaves exist at different depths to hide the number of items in the bag.

To show something was in your bag, you'd reveal the leaf key for that item, as well as all the internal sibling hashes up to the root. That would not reveal any other items, since their leaf keys would be secret.


Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)? Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the paper is here: https://eprint.iacr.org/2016/930.pdf.

I understand how the OT-based PSI works,  and how the OPRF is used for PSI, but I’m confused in understanding how the OPRF is implicitly used in the OT-based PSI. And also in the paper's proposed protocol, I can’t see the difference (in the computational cost) in case we use only OPRF for the PSI and in case of evaluating OPRF via OT.

From what I understand in their protocol (s+b) OPRFS will be used, and from my understanding if we just used OPRF for PSI we will use almost the same number of OPRFs instances, it’ll be depending on the number of inputs. So what’s the difference?

Construction of an "Oblivious Pseudo-Random Generator" from Oblivious Transfer

I will try to explain Section 4.3 of the paper you refer to [1].
Personally this other paper [2], which builds upon the protocol of [1],
helped me a lot.

Here is the basic idea:

the sender and the receiver agree on hash functions $ h_i $
the sender creates an array $ G $ filled with random values
for each element $ x $ of its set $ X $,
the sender XOR together the items of $ G $ which index are obtained by hashing $ y $ with the hash functions:

$$ m_{P_1}[j] = \bigoplus_i G[h_i(x_j)] $$

the sender sends these values (called "summary values" in [2]) to the receiver
The receiver, for each element $ y $ in its set $ Y $,
will use OT to retrieve the cells of $ G $ corresponding to $ x $,
so that he is able to compute the "summary values" for his own elements:

$$ m_{P_2}[j] = \bigoplus_i G[h_i(y_j)] $$

the receiver compares the summary values he got with the summary values he received
to find out the intersection, that is $ y_i \in X $ if and only if $ \exists j, ~ m_{P_1}[j] = m_{P_2}[i] $.

The use of OT extensions is simply an optimization because $ G $ is quite large
and "standard OT" is expensive.
They also use another optimization made possible by the fact that $ G $ is filled with random,
which simply put allows you not to pay for items of $ G $ you do not use.

Now where is the Oblivious Pseudo-Random Generator here?
First note that this is not an Oblivious Pseudo-Random Function,
it's a Generator.
An OPRF must compute a well-defined, efficiently computable function.
For instance in this paper [3] building an OPRF,
the function is the Dodis-Yampolskiy Pseudo-Random Function:

$$ f_k(x) = g^{1/(k+x)} \text{in group $<g>$ of composite order $n$} $$

In the case of [1] and [2] we are not evaluating a "function" per se
but just "spitting out" random values, which matches the definition given in [1] of a "OPRG".
Actually the first time I saw the term "Oblivious Pseudo-Random Generator" was in [1]
and the way they define it (second text block of Section 4.3) makes me think that
they are the first to use this notion.

Maybe this is what confused you ?
Because you can also build a PSI protocol using an OPRF (see [4]),
but it is not what they are doing in Section 4.3 of [1].


What is the difference between Columnar and Grid Transposition? Can someone explain with examples. Furthermore, is a key required to crack the ciphers?

Both the columnar and and the grid transposition ciphers are certain types of transposition ciphers. Both ciphers normally require a key for enciphering / deciphering. However, you can say that these ciphers, in their simple form can be easily cracked by brute-force.

Columnar Transposition

In a columnar transposition cipher you write the message out in rows of a fixed length. Then you read out column by column, where the columns are chosen in a scrambled order. Normally the key defines the width of the rows and moreover the "scramble" part in column permutation. Take the ciphertext "Thisisaciphertextthatneedstobecracked" and the key "ZEBRAS" for example. "ZEBRAS" defines the permutation in regard to the alphabetical order of the letters, which is "6 3 2 4 1 5" here.

1 2 3 4 5 6                              6 3 2 4 1 5
T h i s i s                              T h i s i s
a c i p h e                              a c i p h e
r t e x t t  --> using key "ZEBRAS" -->  r t e x t t
h a t n e e                              h a t n e e
d s t o b e                              d s t o b e
c r a c k e                              c r a c k e
d X X X X X                              d X X X X X

You get your ciphertext by reading your columns with your new indices, i.e. "ihtebkx iiettax hctasrx spxnocx seteeex Tarhdcd".

Grid Transposition

The grid transposition cipher is similar to the columnar transposition cipher. The difference here is that you introduce row indices in addition to column indices. You first create a grid that can fit all of the letters of your ciphertext and again, fill the extra spaces with X. Take the ciphertext "hiwhatsup" and the key "BAZYFG" for example. Again the key defines the columnar permutation, but also the row permutation. "BAZ" is for the columns and would map to "2 1 3" and "YFG" is for the rows and would map to "3 1 2".

  1 2 3                                   2 1 3
1 b e s                                 3 e d s
2 t c o     --> using key "BAZYFG" -->  1 e b s
3 d e s                                 2 c t o


How safe is XOR with multiple independent but non random keys? I will approach the question from practical side. All the examples are not  real, but for illustration purpose only.

I have a message, the secret Bitcoin key, which I want to store safely.

MESSAGE = KwjwmREseNZmZ8yeNKrurN6qPuh9FhrLAefYa2nTLafLkGmWW9ta

To do this I come up with 4 keys which look independent,  somewhat private, and can be recovered.

Key 1 is a set of last words from page 100 and up in my favorite book to match the message length:

KEY1 = help knows the at sortes state the citizens color science costs unfairness

Key 2  is the Merkle Root from Bitcoin blockchain block number 121047, which could be my 2 kids' birthdays 121 and 047 (for the day number within year easily available at blockchain.info)

KEY2= 1b28458e4191e60f4553357cb7b54a9cc15ea0a27e8f5df27dab6d3aab3d3be4

Key 3 is the name of the file of my main wedding photograph, stored in my albums, mail, and shared with friends.

KEY3= IMG_20170511_144510.jpg

Key4 is another Bitcoin address generated solely for the purpose of being a key, two copies will be stored in home safe and safety deposit box in the bank

KEY4= L1jkNAKpG1hu7omtYW6fFFDGw1AaYrdkiUr4NpBANziKVHdZgx8v

The keys are not re-used anywhere. KEY3 is replicated to match the length of the message. The message and all keys are XORed (byte by byte) to get the secure code.

The question is:  How safe is the resulting code?  Can I store it online? Can security hold if 1 or 2 keys (but no more)  are compromised?

I understand that there might be no correct answer, but would appreciate any thoughts  if I miss some vulnerabilities.  Should I have more keys? What kind of keys would help? Can I mix in more plain text keys?

If you ask why not to use a password with good encryption, it is trickier for me to verify the program doing the encryption, while doing XOR is trivial in HTML with few lines of JavaScript on any old offline smart phone (to be destroyed afterwards), and will be trivial in the future.

Thanks.

PS. I can try to figure out how to post the HTML doing the job if anyone is interested.

How safe is the resulting code? Can I store it online?

Very unsafe. No matter how you come up with these keys (passphrases, really), it will have extreme biases. These biases are going to be enough to make some pretty good guesses about your plaintext. This is what makes RC4 insecure in the WEP protocol, and RC4's biases are comparatively minor.

This also has the problem that passwords in general have, which is that you as a human can't accurately remember complex passwords. You'll have to either write them all down (in which case they can be discovered) or use some scheme which actually lowers their strength (your keys 1 through 3).

  Can security hold if 1 or 2 keys (but no more) are compromised?

For every key that is discovered, the biases of the other keys become more apparent. If 2 keys are discovered (particularly keys 2 and 4) it becomes pretty much a puzzle you find in a newspaper to solve.

My advice is to stick to known algorithms. If you need to encrypt something with a password, use something like bcrypt to expand your password into a high-entropy key, then use that key to encrypt with something like AES in a good mode like CTR.


Is standardizing a modified AES a good idea? "Recently" the Ukraine standardized a new block cipher Kalyna, which according to the abstract of"A New Encryption Standard of Ukraine:
The Kalyna Block Cipher" by Oliynykov et al. (warning: the paper contains a lot of test-vectors) is basically a modified version of AES.

The high-level changes (to Rijndael) were described as "four new S-boxes, new pre- and post-whitening, a new larger MDS-matrix and a new key schedule".

What was the (likely main) reason to not standardize Rijndael or AES?

As a "bonus" / side question:
What was the (most likely) design rationale behind the changes being made to Rijndael?

The most likely rationale to change the AES design is political. It's a NIST standard, designed in Western Europe.

It's a bad idea! How much scrutiny has it received? Almost none. How much will it receive? Almost none. Bad idea.


Elliptic Curve - X Coordinate I am currently working on a Koblitz curve. I have found the curve has two matching groups based on the base curve point and N-1 point. My question is as follows: Is there an algorithm to determine how many X coordinates are the same in an elliptic curve? This will tell me how many groups are inside the entire curve based on its parameters given.

As per the Hasse's theorem the total number of points can be computed for both the Finite field curve and binary field curve

For the Finite Field , the number of points on E(F p) is denoted by #E(F p). The Hasse
Theorem states that:
p+1-2√p≤ E(F p) ≤p+1+2√p.

For the Binary field, The number of points on E(F2^m)() is denoted by #E(F2^m). The Hasse Theorem states that:
2^m+1-2√2^m≤#E(F2^m) ≤2^m+1+2√2^m.

For Every x co-ordinate there are 2 Y co-ordinates.
Hence the number of X co-ordinates can be deduced as per the calculation of Hasse's theorem points/2.


Breaking RSA using known root Sorry in advance if this question is silly.
Suppose we want to break RSA, that is find the message $m$ s.t. $c \equiv m^e \pmod n$
Now suppose we know an $x$ s.t. $c \equiv x^e \pmod n$. Could we use that information to somehow find $m$?

Breaking an instance of (textbook) RSA encryption is: given $(n,e)$ and $c$, finding $m$ such that $c\equiv m^e\pmod n$ (meaning by definition: $n$ divides $m^e-c\ $), and $0\le m<n$.

For proper establishment of $(n,e)$, there is a single such $m$ for each integer $c$.

If we are additionally (or instead of $c$) given an integer $x$ such that $c\equiv x^e\pmod n$ (meaning by definition: $n$ divides $x^e-c\ $), then we can compute the desired $m$ as $x\bmod n$. That is the uniquely defined $m$ such that $n$ divides $x-m$ and $0\le m<n$.

For non-negative $x$, we can compute $x\bmod n$ as the remainder of the Euclidean division of $x$ by $n$. For negative $x$, we can use that $x\bmod n$ is $(n-1)-((-x-1)\bmod n)$, where $(-x-1)\bmod n$ is computed as the remainder of the Euclidean division of $-x-1$ by $n$.


Does revealing shares of the result reveals shares of the inputs? Suppose Alive and Bob have shares of two polynomials $P,Q$, say, Alice knows $P_A,Q_A$, Bob knows $P_B,Q_B$ s.t. $P=P_A+P_B$ and $Q=Q_A+Q_B$. They perform some operation $f$ over the shared values, to obtain shares of $f(P,Q)$.

If they reveal the shares of $f(P,Q)$, will this give hints on their individual shares of $P,Q$?

I am supposing that one cannot deduce $P$ or $Q$ with the knowledge of $f(P,Q)$. I just want Alice and Bob to know $f(P,Q)$ without leaking shares.

It depends on how you make shares out of a polynomial. Consider for example Shamir secret sharing, using which a party can share a secret $s \in F$ (where $F$ is a finite field) with $n$ parties by doing the following:

Construct a polynomial $f(x) = s + a_1x+a_2x^2+\dots + a_nx^t$, for some $t$, where $a_i \in_R F$ for all $1 \leq i \leq n$.
Send the value of $f(i)$ to party $P_i$ for all $1 \leq i \leq n$.

The above mentioned secret sharing scheme is linear and it further allows us to perform multiplication of shared values as well. When using Shamir secret sharing for evaluating an arithmetic circuit securely, we release the shares of the final output in public, from which the final output can be constructed. The proof for the fact as to why the shares donot leak anything more than the described output can be found in the Chapter 3 of the textbook titled "Secure Multiparty Computation and Secret Sharing".


What is the difference between key size and block size (for AES)? We are working on AES and want to develop a website which should provide an encryption facility but we are not understanding the difference between key and the block size. More appropriately what does a 128, 192 and 256 bit key mean?

The key size is simply the amount of bits in the key. With AES, like most modern block ciphers, the key size directly relates to the strength of the key / algorithm. The higher the stronger. Since all bits are used, there are $2^{\mathit{klen}}$ possible keys, taking $2^{\frac{\mathit{klen}}{2}}$ operations to brute force on average.
For AES the internal key schedule and the number of rounds are different for each key size. Due to the difference in key schedule there are related key attacks on AES-256 but not on AES-128 or AES-192. The number of rounds is 10, 12 or 14 for the 128, 192 and 256 bit key size respectively. The overall algorithm behind the AES cipher remains the same.

The block size is simply the amount of bits or bytes that can be transformed by the block cipher. It is the input and output size of the keyed block cipher. This transformation is called a keyed permutation as each plaintext has a corresponding ciphertext (and vice versa) for a specific key. For AES the block size is 128 bits or 16 bytes. So a plaintext from the set of $2^{128}$ possible plaintext is permuted to a single ciphertext from the set of $2^{128}$ possible ciphertext.
It is also a pseudo-random permutation or PRP as there is no link between the plaintext and the ciphertext. To be more precise the ciphertext block is indistinguishable from random as long as the key is unknown to any observer. Of course it is only pseudo random as the same plaintext will always permute to the same ciphertext, as long as the key doesn't change.

The number of permutations of a block cipher (i.e. all the possible ways that plaintext blocks can be mapped 1:1 to the ciphertext blocks) rises much faster per bit of the block size than the amount of keys per bit specifying the key size. With a block size of 128 bits the key size can grow to unreasonable sizes without having to worry about duplicate permutations.

Notes

the key size and block size are not directly related to each other - it is possible to create a block cipher for any key size and block size;
AES is a subset of Rijndael, which is the winner of the AES contest by NIST. Rijndael allows key and block sizes of 128, 160, 192, 224, and 256 bits (32 bit increments);
a block cipher is not a generic cipher, a mode of operation is required to use the block cipher to protect confidentiality;
although the block size is not directly related to the security of the block cipher itself, it does affect the security of the mode of operation that the block cipher is used in;
the related key attacks on AES-256 are only of influence if a large number of related keys are generated, for instance when AES is used to create a secure hash function - the use of AES-256 remains secure when used for a particular mode of operation to obtain confidentiality or within a MAC to obtain message authentication and integrity;
AES-256 can be used to provide protection against analysis of the block cipher with a (fully functional, large state) quantum computer - AES-128 provided plenty of protection against the currently known attacks without QC;
AES-192 doesn't make too much sense as it is not as fast as AES-128 while not providing the very large key size of AES-256 to provide the highest security strength or full protection against QC;
AES-192 is tricky to use because the key size is not a multiple of the block size, this makes it hard to use AES-192 in protocols where keys need to be encrypted or when the output of the cipher needs to be used as key.


Key Check Value standard practice for asymmetric cryptography? I'm looking for a standard, or sound industry practice, for the equivalent of a Key Check Value, applied to the private key of a public key algorithm, like ECDSA.

For DES or 3DES keys, practice (as worded e.g. in EMV Card Personalization Specification) is:

  6.1.5 Key Check Value
  Purpose: The data is used to prove that a card/processor has access to a
  specific DES key value.
  Format: Binary, 3 bytes
  Contents: The three leftmost bytes of the result of encrypting eight bytes of zeros by the DES key concerned.

Notice that the above definition is slightly wrong: the KCV as defined does not prove anything beyond knowledge of the KCV. The actual purpose (and the one I'm interested about) is to guard against a wrong value of the key, either accidental, or deliberate from one participant in a scheme where the key is rebuilt from shared secrets (for simplicity, assume that's by XOR of the components, and that at least one participant does not cheat).

PKCS10 looks like relevant industry practice for private keys.

See "Note 2" at page 4,
Certification Request Syntax Specification - RFC 2986:
The signature on the certification request prevents an entity from requesting a certificate with another party's public key.

That is, soneone requesting a certificate on a public key demonstrates his knowledge of corresponding private key by producing a signature verifiable with the public key from PKCS10 request.

Another technique could be found at Join protocol,
Direct Anonymous Attestation
for Trusted Platform Module chip.
It could be considered a proof that TPM "has access" to "keys" $f_0$ and $f_1$.


Are keys generated by the user or block cipher algorithms themselves? We know block cipher algorithms. In the block cipher algorithms, Key Scheduling is the one crucial part. I see that in some simulation programs of the AES,DES,TripleDES encryption algorithms. In those, some programs are asking for the key dynamically or statically.
Now this time, I need to know clearly how to generate the key in symmetric key encryption.
I mean "is key given by user? or is key ready by default in encryption?"

Key generation and key scheduling are different things. The key scheduling is part of the cipher, the key generation generally isn't.

Symmetric keys should be indistinguishable from random, so often they are the product of a secure random number generator. There are other ways as well, such as derivation from a password using a Password Based Key Derivation Function or as the result of a key agreement algorithm, possibly followed by a Key Based KDF.

DES and triple DES are a bit special as the keys are normally augmented with parity bits that are ignored in the actual cipher. So there may be routines that calculate or verify these parity bits. Those routines are however commonly not considered part of the cipher itself and modern libraries may forgo the parity calculation altogether.


Unforgeability and type of adversary When trying to prove the security of an asymmetric signature, for instance, for existential (or strong) unforgeability against chosen messages attack, do we need to consider the signer as a possible adversary?

No, the signer is per definition in possession of the secret signing key and thus can always produce signatures for any message of his choice.

Consequently, a notion of unforgeability is not meaningful with respect to the signer. For a signature scheme one requires unforgeability for parties who are not in possession of the secret signing key but only the public verification key.

You may also look at this answer for a more detailed discussion on attacks and attack models for digital signature schemes.


How to calculate key size of a security algorithm? There are lots of security algorithms. One of the way to measure security of a cryptography algorithm is to find out its key size. There are many key size of a single algorithm.

ECC (Elliptic Curve Cryptography) has 163, 256, 384, 512 etc.
RSA has 1024, 3072, 7680, 15360. I found this from here

but how can I calculate key size of an algorithm? How a single algorithm has different key size?
I am building an simple cryptographic algorithm but I don't know how to calculate key size of my algorithm.
My algorithm is to change a letter of a plain text by a code suppose
a=2H, b=3C, c=8S ......, z=6D

If the plain text is "cb" then cipher text will be "8S3C". So what will the key size of this algorithm be? How can I calculate it?

There are lots of security algorithms. One of the way to measure security of a cryptography algorithm is to find out its key size. There are many key size of a single algorithm. But how can I calculate key size of an algorithm? How a single algorithm has different key size?

There is no standardized method that can help you with that. The best way to figure out the key sizes that are applicable is to lookup the standards that the algorithm should comply to. Furthermore, implementations may restrict those sizes further. If you are unlucky they may even expand the possible sizes of the input / output parameters (including the key size).

Lets take a look:

RSA: any key size will do (starting with a ridiculously low minimum), but usually the key size should be a multiple of 8 bits and possibly of a specific size or higher (e.g. > 1024 bits);
DH: the key size consists of two numbers, of which the size of the group is most important for security - specifying the key size is hard;
AES: AES has key sizes 128, 192 and 256 bits and the number of rounds changes for the different key sizes. AES is a subset of Rijndael which has key sizes 128, 160, 192, 224 and 256. The .NET classes that implement Rijndael only support the AES key sizes (but more block sizes);
Blowfish has a configurable key size of 32 bits up to 448 bits with steps of 8 its;
3DES has key sizes of 128 bit or 192 bit total, but the actual key size without parity bits is 112 and 168 bits respectively. The actual effective security is about 63-80 and 112 bits respectively.

This clearly shows you that key size is a tricky subject.

  My algorithm is to change a letter of a plain text by a code suppose a=2H, b=3C, c=8S ......, z=6D

The key size is what you define as the key size. You could define the string 2H3C8S ...... 6D as your key, given you a total key space of $10^{26}$ (for the digit in the code) times $26^{26}$ (for the letter in the code). Then the key size in bits is then $\log^2({10^{26} \times 26^{26}})$ or 20902 bits (!). Obviously the actual key size is somewhat smaller as you should not repeat codes (just like the parity bits for DES are not counted).

The effective key size is of course about zero as this is not a secure modern cipher.


Why can't we use the IDEA's decryption rule for decrypting a block on CTR mode? Suppose that a block is ciphered with IDEA using CTR mode operation. To get
 the original message, why can't we use the cyphered rule?

CTR uses only a block cipher's forward algorithm, not its inverse. Both sender and recipient compute $N_? = E_K(nonce || counter)$ for each block. Then the plaintext is XORed with $N$ to get ciphertext. The recipient XORs ciphertext with $N$ to get plaintext.

$C_i = E_K(nonce || i) \oplus P_i$

$P_i = E_K(nonce || i) \oplus C_i$

Note: XOR is it's own inverse. $A \oplus B \oplus B = A$


NIST test suite with biased PRNG Is there a straightforward way to employ NIST Statistical Test Suite for testing a biased generator (e.g. with 0.6 probability of 1)? By straightforward way I mean one not requiring nontrivial code modification.

Please note that official test suite is long unmaintained and known to be buggy, not fully consistent with its documentation etc. There are some reimplementations (I can recommend the reimplementation made by David Johnston in Python, but maybe some other is even better) which should be probably the way to go.
AFAIK the tests mostly just try to verify that input numbers used in given way give mostly results in given range expected for truly random numbers. You could possibly use exactly the same tests, just put in another expected ranges of results, as for biased generator the expected ranges are different. That's simple modification from programmer's viewpoint, but actually computing (or just measuring from simulations?) what are the new proper ranges could turn out to be a considerable (math?) work.
And of course, the crucial question is why do you want to actually use the test suite and why do you consider the tests chosen by NIST to be the ones that should be used to evaluate the generator. The consensus today is probably that "universal" test suites are of limited use when it comes to cryptographic RNG, as any of them can check just limited amount of possible non-random patterns. The tests included in the batteries are just trying to cover most common non-randomness, so you can effortlessly prove many badly designed generators to be indeed bad. Once you are trying something more, like proving some generator to be actually good, or trying to understand some generator better, the situation is different. You should already know something non-universal about your generator (like that it is biased and at least some hypothesis why it is biased) and  you should probably design your own tests based on your knowledge and check NIST suite just for inspiration.


What is the difference between different corona tracing protocols? At

https://corona-tracing.org/  and
https://www.cryptool.org/en/cto-highlights/corona-tracing

an easy to understand way was presented how such contact tracing apps work from a cryptographical point of view as it lets users simulate the process.

The "Background" tab at the 2nd webpage describes the differences in the two protocols DP-3T (European approach) and Exposure Notification (Google/Apple) in more details.

Q1: As I understand, the difference is marginal from a cryptographical point of view.
Is this really true?

Q2: The 2nd webpage is the first page I saw containing a detailed comparison of the two protocols. Are there other sources for a detailed comparison too (again I am asking only for the cryptographical aspects of the protocols)?

I'm not aware of websites providing a detailed comparison. Note, in particular, that DP-3T is not one, but three different proposals, and the Google-Apple system is an API specifying structural requirements for a contact tracing app, rather than a full-fledged application.

However, the DP-3T white paper is fairly detailed and explains in a very readable way how each of the three proposals work. It can be found here :https://github.com/DP-3T/documents/blob/master/DP3T%20White%20Paper.pdf.

As for the main differences between DP-3T and Apple-Google: DP-3T already provides an in-depth comparison between their three proposals in the white paper. Out of the three, the hybrid design is very close in spirit to the Apple Google proposal. To my knowledge, there are essentially two main differences between the Apple-Google proposal and DP-3T's hybrid design:

Both require to upload and publicly reveal session keys, from which several ephemeral IDs are derived, corresponding to some fixed time-period. However, the hybrid design allows a variable duration for the session key, and recommends 2 to 4 hours, while the Apple-Google recommends a 24 hours window. To explain why this matters:
1) the smaller the window, the larger the amount of material each user must download on a daily basis (numbers are given on the white paper and depend on the number of daily new cases).
2) however, a user is traceable for the time of the window, in the following sense: if two users have been in contact with the same user with the same time period, they both know the same session key from which the ephemeral IDs broadcasted during this period have been generated, hence they both know that they have been in contact with the same infected user. Of course, the smaller the time window, the less of a real concern this is. Hence, the choice of the time window is a tradeoff between efficiency and traceability.
DP-3T allows to redact your upload. This means that it gives you the opportunity, when you are infected, to not upload some of your session keys. This is useful for example if you've been on a one-to-one job interview for two hours: you might want to not upload the session key corresponding to those two hours, since the interviewer might have turned on his phone during this period alone and therefore learn whether you are infected, breaking anonymity. The Apple-Google app does not allow for this.

Otherwise, the exact choice of cryptographic primitives might differ very slightly for generating the ephemeral ideas (and hashing, for the variants that involve hashing), but honestly it does not matter, all use standard and well-established cryptographic primitives in a correct way.


Is the KDF pbkdf2 included in the openssl suite? I'm trying to encrypt a file using DES in CBC mode but when I try to specify the key derivation function it tells me my command is wrong. It only fails when I try specify the KDF and works when I don't. This is the command i'm trying to use - openssl enc -des-cbc -pbkdf2 -in test.txt -out test.bin -pass pass:test

This command is taken directly from my reference so why does it not pick up the KDF? Is it because i'm using the wrong version of openssl (LibreSSL 2.6.4) or do I have to manually add pbkdf2? If so how do I?

LibreSSL enc docs: https://man.openbsd.org/openssl.1#ENC

OpenSSL enc docs for version 1.1.1 : https://www.openssl.org/docs/man1.1.1/man1/enc.html

Both support pbkdf2. I am kinda surprised LibreSSL still supports DES, I would not support it. Can you paste the exact error you're getting?

Edit:

The changelog of libressl says pbkdf2 support was added in version 2.9.1 (latest current version).

Comparing the openssl 1.1.1 man page above with the openssl 1.1.0 enc man page, I see pbkdf2 support was added in version 1.1.1 (latest current stable version).

You're trying to use a very new feature.


Quantum complexity of LWE As per my understanding, LWE is quantum secure because there is no known quantum algorithm to solve LWE in polynomial time. Due to the reductions given by Regev et al., if there is any algorithm that solves LWE in polynomial time, it will imply that one can solve worst-case lattice problems easily.

My question is: if someone discovers a poly-LWE solver tomorrow, what will be its implication on complexity theory? Is there any analog in classical complexity theory to the quantum setting? To elaborate further, we don't know yet where the factorization problem belongs in complexity classes. So, even if someone discovers a poly-fact algorithm tomorrow, it won't affect our current understanding of complexity classes.

Does this mean we can expect that a poly-fact algorithm is possible which will be true for LWE problems too?

We already know that $P$ $ \subseteq $ $BPP$ $\subseteq $ $BQP$. So, since the problems involved in the reductions are "hard", at first glance, such a LWE solver might have some impact on the following famous questions:

Is $P$ equal to $NP$?
Is $NP$ contained in $BQP$ ?

But analyzing it more carefully, we see that the first one is not really related to that setting, because, by Regev's results, given a quantum algorithm to LWE, we have a quantum algorithm to the lattice problems. But both $P$ and $NP$ are defined with respect to "classical" algorithms.

The second question makes more sense because because at least it involves quantum algorithms: if we had a quantum polynomial-time algorithm for LWE and some $NP$-Hard problem that reduces to LWE, then we would have a quantum polynomial-time algorithm for any $NP$ problem (therefore, $NP$ would be a subset of $BQP$).

However, the detail now is that the lattice problems involved in Regev's quantum reduction are not known to be NP-Hard.

That occurs because, roughly speaking, Regev's reduction states that a quantum solver for LWE with parameters $n$, $q$, and $\alpha$, where $0 < \alpha < 1$, gives us a quantum solver for the approximate GapSVP and SIVP over lattices of dimension $n$ with approximation factor $\gamma \approx \frac{n}{\alpha} $.

So, even if the LWE solver worked for $\alpha$ arbitrarily close to $1$, the approximation factor would still be greater than $n$. But we are far away from proving that those lattice problems are NP-Hard for linear approximation factors. And there are even negative results for the hardness of those approximate problems for $\gamma \ge \sqrt{n}$.

Therefore, with the current reductions we know, a quantum polynomial-time algorithm for LWE would (obviously) put LWE inside $BQP$, but would not impact questions 1 and 2.

Of course, from a practical point of view, that is a huge breakthrough.  On one hand those approximate versions of the lattice problems are not known to be NP-Hard, on the other hand, we don't know efficient algorithms to solve them.