Signature to prove of ownership of arbitrary sized data I am familiar with public key signatures, but I was wondering if there is a method to accomplish the following.

Suppose I publish a file (say a PDF article) on a peer to peer network. How can I generate some sort of public key or signature which will allow one peer to prove to another peer that they have a copy of this file? Something like a signature that treats the full data as a private key, and for which I can put the public key on e.g. my website.

The best method I can come up with is using a hash of the file as the private key in a standard signature scheme. However this is suboptimal because a peer might not actually have a copy of the file anyore, it might just have stored the hash but deleted the file itself.

I am looking for a method that I can wrap up in some challenge-response scheme that allows a peer to prove that they have access to a full copy of the file that belongs to a particular public key.

Proofs of Storage (PoS) are challenge-response protocols that allow a client to verify that a server is truthfully storing a file. See this paper from Ateniese, Kamara and Katz for an example of PoS.

The basic idea is explained in this quote from that paper:

  Viewing the file $\vec f$ as an $n$-dimensional vector, the client
  begins by tagging each element of $\vec f$ and then sending both $\vec f$ and the vector of tags $\vec t$ to the server. To verify that the
  server is storing the entire file, the client sends a random challenge
  vector $\vec c$ and  the server returns $\mu =\sum_i c_i f_i$ along
  with a tag $\tau$, computed using $\vec f$,$\vec t$, and $\vec c$,
  which is supposed to authenticate this value.

The key aspect here is defining

how the client (or more correctly, the one who uploads the file) create tags $\vec t$,
how the server computes response tag $\tau$,
(and perhaps more importantly), how the server's response can be verified publicly.

I don't have time at the moment to explain the details of these aspects (they are a little bit complicated...I will try to do it later). In any case, it is important to remark that in order to verify a response in the proposal of Ateniese, Kamara and Katz, one does not need the original file. This is a public-key setting, and the private key is only used for tagging the file at the beginning. After that, everything is done using the public key (both the proof of storage and its verification).

There are similar proposals, such as Proofs of Retrievability (PoR) and Provable Data Possession (PDP).


Encryption using blinded key I was wondering whether there are any "blinded" encryption schemas, such as the following:
We encrypt message $m$ using $f(k)$, where $f()$ is some blinding function and $c = \text{Enc}(f(k), m)$, while the decryption works as $m' = \text{Dec}(k, c)$ and $m' = m$.
One possible option is, of course, public-key encryption schemas, but I was thinking about more efficient (in terms of performance) symmetric key encryption schemas which have this property.

Would it be a requirement that, given $f(k)$ and $c$, it is hard to rederive $m$?
If so, then what you are effectively asking for is a public key encryption system; your public key is $f(k)$, and your private key is $k$.
Such a method can be constructed from any public key encryption algorithm (but isn't any more efficient than the underlying pk algorithm).
If not, then it is easy; here is one construction:

Let $f(k)$ be a randomized function $f(k) = r || \text{hash}( r, k )$.
To encrypt, you compute $\text{Enc}(f(k), m) = r || \text{AES}( \text{hash}(r, k), m )$.
To decrypt, you compute $\text{Dec}(k, (r || c)) = \text{AES}^{-1}( \text{hash}(r, k), c )$


Why perfectly secrecy needs the key space to be as large as the message space? Why perfectly secrecy needs the key space to be as large as the message space?

I think the definition (1)

$\Pr[M=m\mathrel|C=c]= Pr[M=m]$
still holds.

Let $M(c)$ be the set of messages that can be decrypted from $c$. We know that  $|M(c)| \leq |K| < |M|$ where $K$ and $M$ are the key and message space, and we can infer that some message, say $m'$ can never be the plaintext of $c$, but how does that violate the definition (1) ?

how does that violate the definition (1) ?

Let's assume $|K|<|M|$. Then there exist $c\in C$ and $m\in M$ such that for all $k\in K$, you cannot get $c=E_k(m)$ ($c$ encrypts $m$ under the key $k$).

Now expand the conditional probability of your definition (1):
$$\Pr[M=m|C=c]=\frac{\Pr[M=m\;\&\;C=c]}{\Pr[C=c]}$$
but since $|K|<|M|$, we already have a pair $(m,c)$ that you cannot get under any encryption key, therefore $\Pr[M=m\;\&\;C=c]=0$. Your definition is violated.

You could get to the same conclusion by using entropy -- to get perfect secrecy (i.e. no information about the plaintext is yielded from the ciphertext), entropy of the key space must be at least as big as the message space entropy.


Why is multiplication uncommon in cryptographic primitives? Modern computers (which crypto programs are usually run on) have a 64-bit multiply, and it only takes one cycle. It's pretty decent mixing at next to no cost.

For block ciphers:

  Multiplication by a constant is nonlinear (when combined with other mixing operations), provides diffusion in one direction (easily amended with a rotate), is bijective (necessarily), and is as fast in both directions (with precomputed inverse).

For hashes:

  With no need to efficiently reverse the permutation, it is safe to use polynomials (ones that aren't linear). They provide even better mixing and can mix more than one value at a time. If bijectivity is not important, the full 128-bit multiply result can be used, for example by xor-ing the low and high words. Otherwise, rotates should be in there somewhere so the high bits can affect the low bits. It is somewhat costly, but still less costly than what would provide equivalently good mixing with only "lower level" operations. Simple example: a^=(b&~c)<<<7 can be replaced with a+=(b*~c)<<<7, which imposes no extra cost and mixes better most of the time.

I'm sure there's other potential uses for multiply, but those are the first two I came up with.

So, why is multiplication uncommon in cryptographic primitives? Sure, AES and SHA3 are designed to be hardware friendly, but what about all the others? Especially the ones designed for software implementations.

RC6 uses a multiply, though not for the usual purposes, "usual" meaning "like every other block cipher".

There's at least 5 reasons why multiply is not more often used in symmetric ciphers and hashes:

For use as mixer, multiplication requires more hardware/energy/time than other hardware constructs of comparable cryptographic interest. This is an argument mostly for hardware implementations, but many ciphers (and a few hashes) are designed so as to be fast in hardware (that was the explicit implementation target for DES, and an explicit target for AES, which often is in hardware nowadays).
It is far from universal (and used to be uncommon) that wide multiplication is single-cycle, and the number of cycle(s) listed might not be the end of the story; often there is latency, and that cost extra cycles if the result is used for the next few instructions (for x64 otus pointed this source, the same applies to some ARM).

Worst there is often timing dependency on one operand (opening an avenue for timing attacks), and no way to control which operand from the comfort of a high-level language (other than by forcing some high-order bits in both operands). For example, the common 32-bit ARM Cortex M3 has UMULL (32x32->64-bit result) documented as requiring 3 to 5 cycles, with

  early termination depending on the size of the source values.

Multiplication only does bit mixing to the left: if $C=A\;B$ then bit $C_j$ is independent of bits $A_i$ and $B_i$ for any $i>j$. Fixing this requires computing the product with more precision than its operand (and some post-processing), which might not be fast/easy in high-level language.
Multiplication by a constant is linear, and ciphers require non-linearity. While some derivatives of multiplication (like squaring) are not linear, multiplication as the sole source of non-linearity could open to algebraic attacks.
As pointed in  comment, when truncating the result of a multiplication (effectively working modulo some power of two), $F_A: B\mapsto F_A(B)=A\;B\bmod 2^k$ is a bijection only for odd $A$, and can loose a lot of entropy for other $A$, which is undesirable in a normal mixer.

The only widely used cipher I can name that heavily uses multiplication other than by constant is IDEA, where it is followed by modular reduction modulo the prime $2^{16}+1$, in order to fix issues 3 and 5.

Multiplication is in wide use in asymmetric cryptography: RSA, DSA, Elliptic Curve cryptography over a prime field..


Proof for exponentiation in modular arithmetic If  $e$ is a natural number, then this is true:

$$m^e \bmod\ n = (m\bmod\ n)^e\bmod\ n$$

This is often used when encrypting, especially with RSA, since one can avoid directly calculating $m^e$, which can be a very big number.

However, I haven't been able to find any documentation/proof for this conjecture, can anyone give a source or explain it?

That is not a conjecture, that is basic number theory and follows from the fact that

$$(ab)\textrm{ mod } n = \big((a\textrm{ mod } n)\cdot(b\textrm{ mod } n)\big)\textrm{ mod } n$$

Write $a=k_an+r_a$ and $b=k_bn+r_b$ and thus $a \textrm{ mod }  n = r_a$ and $b \textrm{ mod }  n = r_b$. Plugging into the left hand side will give you:

\begin{align}\big((k_an+r_a)(k_bn+r_b)\big)\textrm{ mod }  n &= \big((k_a k_b  n + k_a r_b+ k_br_a  )n + (r_a   r_b)\big)\textrm{ mod }  n \\ &= (r_a  r_b)\textrm{ mod }  n\end{align}

The last step is because any multiple of $n$ clearly yields a zero remainder when divided by $n$.

Plug into the right hand side gives you $(r_a r_b ) \textrm{ mod }  n$. This shows the equality which is what you're looking for.

Viewing the exponentiation $m^e \textrm{ mod } n$ as $(m \cdot \ldots \cdot m) \mod n$ (multiplying $m$ with itself $e-1$ times), then you have what you are looking for.


Differential and Linear trail propagation in Noekeon In the Noekeon Cipher Specification they write the following :

  The propagation through Lambda is denoted by $(a \rightarrow A)$, also called a
  step. Because of the linearity of Lambda it is fully deterministic:
  both for LC and DC patterns, we have: $A = \operatorname{Lambda}(a)$. The fact that the
  relation is the same for LC and DC is thanks to the fact that the
  Lambda is an orthogonal function. If represented in a matrix, its
  inverse is its transpose.

I'm having a hard time understanding why the orthogonality of Lambda affects the relation with regards to selection patterns (LC).

Why does the orthogonality of Lambda make it so that the relationship is the same as for DC ? How would the selection pattern propagate through the linear layer if Lambda was not orthogonal ?

This is due to the duality between linear and differential trails.
Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience.
In general, a nonzero differential $\Delta_1 \to \Delta_2$ over $L$ must satisfy

$$\Delta_2 = L\,\Delta_1.$$

A nonzero linear approximation $u_1 \to u_2$, however, must satisfy

$$u_2 = L^{-\top}\,u_1$$

An elementary way to see this is to observe that $u_1^\top x = u_2^\top (Lx)$ is equivalent to $u_1^\top x = (L^\top\,u_2)^\top x$. This holds for all $x \in \mathbb{F}_2^n$ whenever $u_2 = L^{-\top}\,u_1$, and otherwise for half (some hyperplane) the $x$.

If $L$ is orthogonal, then $L^{-T} = L$. So then we have both $\Delta_2 = L\Delta_1$ and $u_2 = L u_1$.


Rivest's ring signatures with hashes instead of symmetric encryption While studying ring signatures, I obviously stumbled on the Wikipedia article about ring signatures. It includes a piece of Python code to demonstrate "How to leak a secret" ring signatures.

Remarkably, they do not use a symmetric encryption function ($E_k$, as in "How to leak a secret"), but a hash function ($\mathcal{H}$). Indeed, the encryption function does not need to be invertible, if we close the ring of the signature at the very last (take $v^\prime$ random, $m$ is the hashed plaintext):

\begin{align*}
\mathcal{H'}(x) &= \mathcal{H}(x\mathbin\Vert m)\\
v&=\mathcal{H'}(y_{r} \oplus \mathcal{H'}(y_{r-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(v'))))\quad r-s\enspace\text{times}\\
h&=\mathcal{H'}(y_{s-1} \oplus \mathcal{H'}(y_{s-2} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(y_1 \oplus v))))
\end{align*}

now notice that
$$
v'=y_s \oplus h \quad\Leftrightarrow\quad y_s=v'\oplus h\\
x_s=g_s^{-1}(y_s)
$$

which "closes" the ring.

What are the security implications here? I can't seem to find literature describing this substitution.

There are two immediate implications.

Now, does it break in practical terms?  Not obviously, but our confidence in the security of the ring signature scheme cannot be understood entirely by studying the security of the underlying ordinary signature scheme—there may be an attack against the ring signature scheme even if the underlying ordinary signature scheme is secure, so there are more targets for cryptanalysis, meaning you can't save work by focusing on one primitive.

The two implications are for two different security properties:

Anonymity of the signer.

The Rivest–Shamir–Tauman scheme guarantees the anonymity of the signer even against an adversary of unbounded computational capacity without even relying on $h$ to be a random oracle.  The proof of this depends on the invertibility of everything involved so that there's a pigeon in every hole and exactly one pigeon to each hole: for every $k$ and $v$, there are exactly $(2^b)^{r - 1}$ possible values of $(y_1, y_2, \dots, y_r)$ satisfying the ring signature equation, all equiprobable if the $x_i$ are drawn uniformly at random.

If you replace the PRP $E_k$ by a PRF $H_k$, then this proof no longer holes: the distribution on solutions may be nonuniform.  Is it so nonuniform you could unmask the dirty traitor and prosecute them under the Espionage Act and pillory them on Fox News?  Maybe, maybe not (although you could doubtless find someone else to pillory on Fox News, such as a nonbinary vulture just trying to use the bathroom, and ratings would go up just the same).
Reduction of security of ring signatures to security of underlying ordinary signatures against forgery.

The proof demonstrates how to build an algorithm to forge ordinary signatures given an algorithm to forge ring signatures.  The algorithm again relies on the reversibility of the encryption function, but it's got more details than I can fit in this feathery head today, so I can't say whether you could adapt the reduction (maybe with a wider tightness gap) to work with the hashing version.

Of course, as you may have observed, $2^b$ must be larger than all the moduli, and there aren't all that many 2048-bit block ciphers lying around.  (1024-bit, yes: Threefish.  But you also don't want to rely on RSA-1024.)  So in practical terms, you don't want to use this scheme anyway!  Fortunately, there is a pretty substantial literature on ring signature schemes in the past fifteen years since the RST paper came out.  I leave it as an exercise for the reader to study newer developments in ring signatures.


Can you construct a key agreement system from public-key-encryption system? Can you construct a key agreement system from public-key-encryption system? If so, how?

What about vice versa?

Yes, you can create a key agreement system from a public key encryption system. Or at least you can create a key establishment scheme using RSA. The term "key agreement" is often used for schemes that are explicitly used for Diffie-Hellman (DH) type of key establishment where the keys are calculated rather than distributed.

The RSA based ciphersuites have been part of TLS up to version 1.2. In this scheme the RSA public key of the server is used to encrypt a random generated on the client. This random is decrypted at the server using the RSA private key and can then be used to derive the session keys from the established secret.

This is a very simple scheme, but it does have some drawbacks because RSA key pair generation is slow and may require a lot of random data. As such it is commonly not used to generate ephemeral (i.e. temporary) key pairs, as it commonly done for DH.

Because of this, the RSA key pair of the server is the static key associated with the certificate of the server. This means that this key must be usable for decryption, while it is really there to perform authentication (signature generation). Generally we try to use the private key for one type of purpose.
If the private key ever leaks then all stored TLS sessions generated with this key can be decrypted with it. In other words: it doesn't provide forward secrecy.

Because of above, the RSA based key establishment has been dropped from TLS 1.3.

And yes, you can also use DH-style key agreement to perform encryption / decryption. IES and - for Elliptic Curve cryptosystems - ECIES is probably the most well known scheme. Simply said, the sender creates a temporary key pair (which is quite fast for DH and ECDH) and uses the private key of it to derive a secret key together with the trusted public key of the receiver. It then sends the temporary / data public key together with the ciphertext to the receiver. The receiver can use this public key together with its own private key to establish the same secret key and decrypt the ciphertext.

As derivation and encryption with a secret key is always required, IES is by definition a hybrid cryptosystem: it mixes the asymmetric DH key agreement with symmetric encryption with the secret key.

Notes:

Personally I use the term "key establishment" in favor of "key exchange" for the establishment of secret keys because it more clearly includes key agreement - where the keys are not distributed by value. Both terms are commonly used to mean the same though.
IES is a description of a scheme rather than a specific protocol; it is not clearly specified how the public key and ciphertext are combined, nor should you take it for granted on how the secret key is used to encrypt the data.
DH is only one form of key agreement: I'm not sure you can answer the question: "can you construct a public key encryption system from a key agreement system" in the generic form. I guess it depends on the key agreement scheme used.


Decode & Verify Base64urlUInt-encoded RS256 Public Key from Google According to Google, to access the id_token it sends along with Access Tokens (for accessing their API), you must first validate the token using the RS256 Public Key available from this page. The public key responses look like this:

  {
   "kty": "RSA",
   "alg": "RS256",
   "use": "sig",
   "kid": "8c9eb968f73744eaed421e48010142bce51a067f",
   "n": "uweJ3hFY9wqZ6ZG-iSNhQwHtKCGl8G_jcQgGPjOrS-Rum3dyDjicqkAyfS8XDn480KD_TZ5m-lqBjqfimePu2_cH4URDPIwsqSzJI2_piEhaqnXRptIe5YB5imAL6iETKaOPjw284Fc7EdHK-ekHMn3AXjsy9AIErwAVw4-4ZXXwHbyQXJy1DyUB4ZzxiEvw_qkQmLdltmrNkLOw-Xh-C9UkTZ9NA58bYPBnxLwnAu_ggw_g_-hCAs6OvXZbAfFHhIGBLyjtdDLVrfXo1112QREB9d5sEds0bKZtJcD9afl4E7Ht6G-g3jNP2clAu6-6B-cIe4-j8Ph1uJDPkAmDfw",
   "e": "AQAB"
},

According to Google & RFC Specification 7518, this is a Base64urlUInt-encoded RS256 Public key. The "n" parameter is the modulus, and the "e" parameter is the exponent. The rest are simply for verifying the algorithm itself, not pertaining to use of the Public Key for decryption/vaidation.

My Issue stems from the fact that this is not, from what I've read online, a standard RS256 Public Key. When trying to verify my IDtoken, it spits back ValueError: Could not deserialize key data. (The technology isn't important, but I'm using the pyJWT module in python). I know the problem isn't with the ID token, because if I skip validation I don't have a problem. This of course isn't suitable for a production environment.

I've tried converting it to regular Base64 by replacing '-' and '_' with '+' & '/', respectively, along with adding '=' for padding. I even tried prefixing the '-----BEGIN PUBLIC KEY-----\n' string & appending the similar string at the end, but to no avail. I also tried appending the "AQAB" exponent to the end of the modulus, again without any success.

I've also tried playing around with other public keys generated online & those work fine. Even if I purposefully mistype them, I get a error stating it simply couldn't validate the token, instead of spitting back a weird ValueError.

So my question stands; Is there something wrong with the "public key" modulus/exponent Google is giving me, or in how I'm using/converting it? Am I missing steps? Any help is greatly appreciated as I'm new to this topic. Thanks in advance!!

Both values are unsigned, big endian values, encoded as base-64-url. Basically that means that there is no sign bit and that the most significant bit is all the way to the left (bit B_7 - zero based indexing - on byte index zero). So you first need to base-64-url decode the values and then convert them to a big number. Finally, you need to combine both big numbers to form the public key, by providing the numbers as modulus $n$ and exponent $e$.

If you cannot combine the numbers to a public key you may need to encode the public key as PKCS#1 public key or SubjectPublicKeyInfo, which is an X.509 structure. For both these operations you either need to create the encoding yourself (which is pretty hard) or you need to have access and understand how to use an ASN.1 library.

You may want to have a look at the RSA public key interface in the "hazmat" cryptography package, with load_rsa_public_numbers and public_bytes(encoding, format) with PEM and SubjectPublicKeyInfo.


Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity Suppose you have a function $f$ that takes a dataset $D$ as input and returns an output in $\mathbb{R}^d$.
If this function has $L^2$-sensitivity $\Delta$, then the analytical Gaussian mechanism (Theorem 8 in this paper) says that if you add Gaussian noise of variance $\sigma^2$ to each coordinate of result, with:
$$ \Phi\left(\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right)-e^\varepsilon\Phi\left(-\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right) \le \delta$$
where $\Phi$ is the Gaussian CDF, then you obtain an $(\varepsilon,\delta)$-differentially private mechanism.
Now, suppose that there is a finer way of describing the sensitivity of $f$. Rather than only knowing a bound on the maximum $L^2$ norm of $f(D_1)-f(D_2)$ for neighboring $D_1$ and $D_2$, we have a per-coordinate sensitivity bound: we know that the first coordinate of $f(D_1)-f(D_2)$ is always below $\Delta_1$ (in absolute value), the second below $\Delta_2$, etc., and $\Delta_d$ bounds the sensitivity along the $d$-th coordinate.
In this case, intuitively, adding the same magnitude of noise along each coordinate doesn't seem like the best solution. For example, if $\Delta_1$ is much smaller than the other per-coordinate sensitivities, then we will likely add too much noise to the first coordinate for it to be useful. Thus my question: is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?
I know I could be using Laplace noise instead, but then the per-coordinate noise magnitude grows in $O(d)$ instead of $O(\sqrt{d})$ (unless $d$ is sufficiently big to use the Advanced Composition Theorem, but that only makes a big difference for large values of $d$), so I'm interested in a Gaussian noise formula hoping that it will work well for not-too-high values of $d$ (say, $5<d<50$).

I haven't read your full question, but the answer to:

Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?

and (implicitly)

Can the noise scale better than $O(d)$ for $d$-dimensional output?

Then the answer is yes.
The following should be able to be easily adapated for essentially any mechanism $\mathcal{M}$, but I'll focus on the case that the mechanism is adding independent mean-zero Gaussian noise, as this is your case.
Moreover, this argument should work provided that the sensitivity is "homogenous" in a certain sense --- in particular, any sensitivity defined with respect to a norm should work, so any $\ell_p$ sensitivity (for $p\geq 1$ I think).
Throughout this, I will write $\vec{\Delta} = (\Delta_1,\dots, \Delta_d)$ to be a vector of the per-coordinate sensitivities of $f(x)$.
I will write the $i$th coordinate of $f(x)$ as $f(x)_i$.
I will also write $\mathsf{diag}(\vec{\Delta})$ to denote the $d\times d$ diagonal matrix with $(i, i)$ entry $\Delta_i$.
The idea here is to transform $f(x)$ as follows:
$$g(x) = \mathsf{diag}(\vec{\Delta})^{-1}f(x)$$
If you compute the $\ell_2$sensitivity of $g(x)$, you get that:
\begin{align*}
\Delta_2(g) &= \max_{x, y} \lVert g(x) - g(y)\rVert\\
&= \max_{x, y}\lVert \mathsf{diag}(\vec{\Delta})^{-1} (f(x)- f(y))\rVert\\
&= \max_{x, y}\sqrt{\sum_{i\in[d]} \left(\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\
&\leq \sqrt{\sum_{i\in[d]} \left(\max_{x, y}\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\
&\leq \sqrt{\sum_{i\in[d]} \left(\frac{\Delta_i}{\Delta_i}\right)^2}\\
& = \sqrt{d}
\end{align*}
So, we have that $\Delta_2(g)\leq \sqrt{d}$.
I'm pretty sure this should extend in a straightforward way to give you that $\Delta_p(g) \leq \sqrt[p]{d}$, which would explain why you can only get the upper bound of $O(d)$ for the $\ell_1$ sensitivity.
Anyway, now we can just apply (essentially any) differentially private mechanism to $g(x)$.
In particular, the Gaussian mechanism states that:
$$h(x) = g(x) + \mathcal{N}^d(0, 2\ln(1.25/\delta)n/\epsilon^2)$$
Is $(\epsilon, \delta)$ differentially private.
For what follows, recall that differential privacy is closed under post-processing, so "we're done" on the topic of privacy.
$h(x)$ has the undesirable property that $\mathbb{E}[h(x)] = \mathbb{E}[g(x)] + 0 = \mathbb{E}[\mathsf{diag}(\vec{\Delta})^{-1}f(x)] \neq f(x)$, so we have (potentially significantly) biased the output of your function.
Fortunately, we can fix this by having our output be $\mathsf{diag}(\vec{\Delta})h(x)$ (which you can quickly check leads to an unbiased output).
In total, the mechanism which outputs:
$$f(x) + \mathcal{N}\left(0, \frac{2\ln(1.25/\delta)n}{\epsilon^2}\mathsf{diag}(\vec{\Delta})^2\right)$$
Is therefore $(\epsilon, \delta)$ differentially private.
This is what you would expect --- if you have sensitivities which are different in each coordinate, then instead of "spherical" Gaussian noise, one should use ellipsoidal Gaussian noise "matched" to each coordinate, which is precisely what the mechanism does when you write it all out.
Note that the gaussian noise is no longer the product of $d$ i.i.d. gaussians (but still has quite simple covariance structure).


What is a pre-shared key in TLS/SSL and why does master key is not used instead of session key? i have understood  the SSL handshake flow .The confusion are -

What is the pre-shared key here ? Is it the pre-master key or it is the random number that is generated by server and client.?

2.I get it that the session key is used to maintain the session but how does it      so that in TLS/SSL
how master key is different than session key

What is the pre-shared key here ? Is it the pre-master key or it is the random number that is generated by server and client.?

Neither. In SSL/TLS 'Pre-Shared Key' (PSK) is a specific type of key-exchange different from the common RSA or DHE/ECDHE key-exchanges, and practically never used on the public net. (There are similar, but not identical, PSK options in some other protocols like IPsec.)
The premaster secret is not called a key and not used as a key, although it has some key-like properties. It is secret, and it is shared, but it is shared during the handshake and not before, so it is not pre-shared. The premaster secret and the two 'random' values are used to derive the master secret, and the master secret with the 'random' values again is used to derive the working or session keys and IVs, plural, see next.

get it that the session key is used to maintain the session but how does it so that in TLS/SSL
how master key is different than session key

There is not one session key; there are at least two and usually four or six if you count the IVs (or nonces) handled as keys. See What is the purpose of four different secrets shared by client and server in SSL/TLS? and rfc5246 (or previous versions) sections 8.1 6.3 and 5


What are the quantum relations of four-particle GHZ states? How to represent a four particle GHZ states in quantum cryptography and what is the relation between them?

$\newcommand\ket[1]{\left|#1\right>}$
Since you ask about 4-particle GHZ state, I’ll assume you’re familiar with the more usual 3-particle GHZ state.

The 4-particle GHZ state is $(\ket{0000}+\ket{1111})/\sqrt2$. Like the 3-particle GHZ state, loosing a single particle transforms this state to a mere classical mixture of $000$ and $111$.
The relation between the particles can be expressed by the stabilizer group generated by :
$$\begin{gather}
XXXX\\ZZII\\IZZI \\ IIZZ.
\end{gather}$$
This group contains

the  6 permutations of $ZZII$, meaning, that if you measure any two particle in the $Z$ direction, you will obtain the same result
$XXXX$ : meaning that if you measure all particle in the $X$ direction, you will have an even number of them in each direction (i.e. all in the same direction, or two in one direction, 2 in the other, but never 3 in one direction and 1 in the other)
$YYYY$ : meaning that if you measure all particle in the $Y$ direction, you will have an even number of them in each direction.
$ZZZZ$ : meaning that if you measure all particle in the $Z$ direction, you will have an even number of them in each direction. (This is consistent with 1.)
the 6 permutations of $-XXYY$ : if you measure two particle in the $X$ direction, and two in the $Y$ direction, you will have an odd number of $-1$ results.

I thought combining 2,3, and 5 leads to a contradiction similar to the GHZ paradox, but I didn’t manage to find the correct combination, except that measuring any of the qubit the in $X$ or $Y$ direction project the 3 others in a 3-particle GHZ state.


Is non-adaptive CPA strictly weaker than standard CPA security? Today during a cryptography lecture an interesting question came up: Whether non-adaptive CPA security is equivalent to adaptive (FtG / LOR) CPA security.

Now for a short description of what this CPA1 / non-adaptive definition means:

The challenger generates a key $k\gets \operatorname{Gen}(1^n)$
The stateful adversary $\mathcal A$ is initially run on $1^n$ with access to $\operatorname{Enc}_k(\cdot)$ and outputs two equal-length messages $(m_0,m_1)$
A bit $b$ is chosen uniformly at random and $c_b=\operatorname{Enc}_k(m_b)$ is computed
The adversary $\mathcal A$ is resumed / run on $c_b$ and $1^n$ but not given access to $\operatorname{Enc}_k$ and has to output a bit $b'$
$\mathcal A$ wins iff $b=b'$

You may recognize this definition to be the standard Find-Then-Guess CPA definition with access to the encryption oracle removed after the challenge messages are output. So the adversary can use the encryption oracle to find the challenge messages but can't use it on any function of the challenge ciphertext.

So:
Is there an encryption scheme that is CPA1 but not CPA secure?

Intuitively it feels like this definition is weaker because encryption queries cannot depend on the challenge ciphertext but I currently see no way to exploit this such that CPA1 security is still preserved.

I know this is true for CCA because we know NM-CCA1 $\implies$ IND-CCA1 and IND-CCA2 $\implies$ NM-CCA2 but NM-CCA1 $\implies$ NM-CCA2 doesn't hold.
I also know that CPA1 security is stronger than eavesdropping security because deterministic schemes can be broken by querying the encryption oracle before the challenge query.

Edit. Except for CPA1 (defined by the OP), "CPA" below refers to multi-challenge CPA, where the adversary always submits two messages and receive the encryption of either the first or the second messages. It's equivalent to the usual one-challenge multi-query CPA.

CPA1 is equivalent to CPA. Consider real-or-random CPA (RRCPA), where the adversary adaptively chooses messages and receive either encryptions of the chosen messages or encryptions of random messages. It is routine to see that CPA is tightly equivalent to RRCPA. Lastly, RRCPA reduces to CPA1 via a standard hybrid argument, as the encryption of random messages can be queried before the challenge. The proof is not tight, though.

In more detail, let $\mathcal{A}$ be an adversary against RRCPA, we construct $\mathcal{B}$ against CPA1. Let $Q$ be a polynomial that upper-bounds the number of challenges $\mathcal{A}$ makes. $\mathcal{B}$ does the following:

Sample $i\gets[Q]$ and launch $\mathcal{A}$.
For the first ${(i-1)}$ challenges $m_1,\dots,m_{i-1}$ that $\mathcal{A}$ makes, query the encryption oracle to obtain the correct ciphertexts $c_1,\dots,c_{i-1}$ and use them as the response to $\mathcal{A}$.
Sample ${Q-(i-1)}$ random messages $m_i',\dots,m_Q'$ and query the encryption oracle to get the ciphertexts $c_{i+1},\dots,c_Q$ (without $c_i$).
When $\mathcal{A}$ makes the $i$th challenge $m_i$, submit $m_i,m_i'$ to the CPA1 challenger and gets back a ciphertext $c_i$. Use it to respond to $\mathcal{A}$.
For the other challenges from $\mathcal{A}$, use $c_{i+1},\dots,c_Q$ as the responses.

Let $H_i$ be the hybrid of RRCPA such that the first $i$ challenges are real and the other are random, and $G_b$ the CPA1 experiments.
Clearly, $\mathcal{A}$ is in $H_{i-1+b}$ if $\mathcal{B}$ is in $G_b$ and chooses $i$ at the beginning.
Averaging over $i$ shows that the advantage of $\mathcal{B}$ is $1/Q$ that of $\mathcal{A}$.
This finishes the reduction.


The small key-search circuit for brute-force of Bernstein I'm trying to understand Understanding brute force by Bernstein. I couldn't understand how the described machine can brute force the AES.

  The attacker builds a very small key-search circuit. The key-search circuit has
  three inputs: a 12-byte string $\beta$, a 4-byte integer $n$, and a 16-byte string $s$. The key-search circuit has one output: a 16-byte string $Z(\beta, n, s)$ defined recursively by $Z(\beta, 0, s) = s$ and $Z(\beta, n + 1, s) = Z(\beta, n, H(s \oplus (\beta, n))$.

The crucial part is not just the definition of $Z$, which is a random walk in possible keys.  It's also how you use it, on the next page:

Search for $Z(\beta, 2^{23}, r_j)$ among $Z(\beta, 0, H(k_i)),$ $Z(\beta, 1, H(k_i)),$ $Z(\beta, 2, H(k_i)),$ $\dots,$ $Z(\beta, 2^{23} - 1, H(k_i))$.
If you find that $Z(\beta, 2^{23}, r_j) = Z(\beta, \ell, H(k_i))$, then you have a candidate trail to follow!
In this case, start over computing $Z(\beta, 2^{23}, r_j)$, but only go $2^{23} - \ell - 1$ steps until the state $(\beta, \ell + 1, s)$ rather than all the way down to $(\beta, 0, s')$.
If $H(s \oplus (\beta, \ell)) = H(k_i)$, you've found a candidate for $k_i$, namely $s \oplus (\beta, \ell)$.

One way to look at it is as follows: The function $H$ (e.g., $k \mapsto \operatorname{AES}_k(18238)$) represents a directed graph where each node $k$ has exactly one successor $H(k)$.  Imagine the graph as a network of rivers on a terrain.  They're not all connected, but they flow in only one direction.

You're teleported onto a node in the middle of a river, and you're trying to find the node just behind you, but you can't look there.
You shoot out a scattershot of cheap drones.  They will record the node where they landed, and then flow down the river exactly $2^{23}$ steps before stopping and embedding themselves in the river bed.
You go to sleep for the night.  In the morning, you trawl down the river looking for a drone.  If you find one after $\ell$ steps, you go to the point where it started and move forward by $2^{23} - \ell - 1$ steps, and see if the next one is the node you were sitting on at the beginning.

Of course, the drone you find could have come down a different tributary of the river, so you might have to retry with another drone.

This is the rough idea: the model breaks down because rivers are never cyclic, and the advantage comes either from (a) precomputing where the drones landed (as in precomputed rainbow tables) so that you can save effort by reusing them for many trawlings, or (b) simultaneously trawling and shooting out drones in parallel, and then searching for a collision by sorting the nodes where the drones landed together with the nodes you trawled through.


Can future Bitcoin hashes be considered a good source to generate random numbers? There are a lot of miners trying to calculate the next valid SHA-256 hash using random strings, so can I consider that generated hashes have good randomness? How can I prove it?

For example, use the bitcoin hash as a entropy or seed to generate random numbers. How would you solve this problem? What algorithm would you use to generate random numbers with the bitcoin hash as a input seed? but the algorithm should be secure and have a good entropy

As Bonneau et al. showed a Bitcoin block header has high min-entropy, approximately 68 bits. So, in theory you could extract randomness for your protocol or application from Bitcoin block headers, but bear in mind that blockchain's entropy is malleable as shown by Pierrot et al.

For example, if you run a lottery whose randomness is extracted from the Bitcoin blockchain, a miner could interfere with this randomness by withholding blocks whose entropy is not profitable for her. She might want to do this, if she is participating in the lottery and the prize of the lottery is larger than the block reward.

To deter such an attack you might want to use verifiable delay functions(VDF). VDFs make impossible to learn the randomness derived from the block before some time-out (say 1 hour), since it requires sequential work to compute, therefore massive parallelization does not help here. Furthermore once the output of the VDF function is calculated it is easy to verify the computation given a small proof. By applying VDFs even the miner does not know the output of the VDF before the time-out. Therefore there would be no more financial incentive for the miner not to publish her block, since she would forfeit her block reward.


What type of encryption is this homebrew "encyption algorithm"? ${}$ Background:
Quite a long time ago (somewhere 1998) I thought I was really clever and invented my own encryption/decryption code. Looking through old code I rediscovered my old algorithm. (No, it was never used in any production environment.)

I'm wondering what type of encryption my naive self invented back then. I'm guessing it is a polyalphabetic substitution cipher, but I'm not really sure?

My Questions:

What type of algorithm is this?
How weak is it against modern day cryptanalysis and what methods would be used to break it?

What the code below does:
The algorithm encrypts and decrypts based on a set 64 alphabets. Each alphabet consists of the same 64 characters in random order; each character is included exactly once per alphabet. This set of alphabets is effectively the key for the algorithm.

To start, the plaintext is base64 encoded. Then each individual character, in the base64 encoded plaintext, is substituted by a character from one of the alphabets. The first characters is (always) picked form the first alphabet, for subsequent characters the alphabet is selected based on the index-number of the substituted value of the character preceding it. So, it 'encrypts' one character at the time and, if one character in the ciphertext changes, the decryption will (most likely) be garbled from that point on.

The code also adds base64 style padding to the ciphertext, in an attempt to be 'even more secure' by passing of the ciphertext like regular base64 encoded data.

The Algorithm:

Encryption is being carried out over letters from a 64-element alphabet in the following mode:

$$C_0=F_0(P_0)\quad C_i=F_{C_{i-1}}(P_i)$$

Where $F:\mathbb Z_{64}\times \mathbb Z_{64}\to\mathbb Z_{64}$ represents 64 different, random, fixed permutations forming the key.

Reference PHP-Code can be found in the revision history.

What type of algorithm is this?

The best capturing for this algorithm that I can see would be as "mode of operation for a tweakable block cipher" with the tweakable block cipher being the one that has keyspace size $(64!)^{64}\approx 2^{18943}$ and in its current representation uses (at least) $64^2\cdot 6=24576$ bits for key representation. The tweak size is 64 as is the message and ciphertext space. Key decoding then works by partitioning the key into 64 equal-sized strings and then using each string to identify one permutation over 64 elements. Encryption works by selecting the permutation indicated in the tweak and applying it.

Using the notation $E^{\text{Tweak}}_{\text{Key}}(\text{PlaintextLetter})$ the mode is then $$C_0=E_K^0(P_0)\quad C_i=E^{C_{i-1}}_K(P_i)$$ for a given plaintext sequence $P_i$ and the corresponding ciphertext sequence $C_i$ and the key $K$.

  How weak is it against modern day cryptanalysis and what methods would be used to break it?

This construction has four main problems for modern cryptography:

Ridiculous keysize (for symmetric cryptography). It takes 2.3kB to represent the key, normally our keys use 32 bytes which is plenty (because you can't search $2^{256}$ fully).
Small block size. This is a problem in and of itself as an attacker can just build a dictionary of the input-output pairs by making a sufficient number of block cipher queries (this is part of the reason why modern block ciphers use 128 instead of 6 bit blocks).
Deterministic Encryption. The given encryption scheme cannot be CPA secure, because it is deterministic. That is an attacker can recognize whether two encryptions yield the same value. Even worse, this scheme has the same issue as CBC (the best one could hope for in online deterministic encryption), namely it leaks prefixes. If I encrypt abcde and then encrypt abcgh under the same key, the attacker can see that the messages were equal up to abc.
Lack of authentication. In theory one could think about fixing the previous point by forcing $P_0$ to be a random value (that's what CBC does). In this case this construction might be secure against CPA attackers. But of course it still isn't secure against the most standard adversary model in modern cryptography: CCA secure, that is attackers who also get to ask for decryptions (with one exception input). To break CCA security when given a challenge ciphertext of one of two possible plaintexts an attacker would simply change the last ciphertext letter and ask for the decryption and use the first few letters to determine what plaintext was encrypted.

Also if you don't understand something in this answer, please just ask (in the comments) and don't be frightened if you think "it should be obvious" or something like that.


Signal protocol, how is Signed PreKey created? I am getting confused with what exactly is the nature of the Signed Prekey (SPK) used in signal protocol.
I understand what it is used for, but I think the confusion stems from its name.
Is it just the normal key-pair whose public part will get signed and sent to the server as a part of the "key bundle"?

Which means, THAT exact SPK that we send in the bundle as well is just a random public key, and is in no way signed or modified by the IdentityKey itself.

To conclude:

Based on my understanding, this SPK could also be named "Key that WILL get signed but IS NOT signed"
Or is there a previous key, lets call it just "PreKey" that gets signed by IdentityKey and thats how we get Signed PreKey?

I sound like a crazy person to myself and it's really hard to even formulate this question. I've read technical paper on signal's website and also whitepapers of signal implementation in WhatsApp but still I'm getting confused how is this SPK obtained?

Hope this doesn't look like non-sense.
Thanks

Signed Prekey is one of the long-term prekeys which is used in X3DH. The public component of Signed Prekey is signed by the Identity private key and sent to the Key Distribution Server as part of key bundle. To make sure that the server doesn't tamper with key bundle, Signed Prekey is signed by the Identity key and Identity key is verified using out of band authentication with the help of safety numbers at some time in future.

One-time prekeys are disposable and deleted from the server every time a contact requests public key bundle from the server. Unlike one-time prekeys, Signed Prekey is not disposable but it is not permanent either. Signed Prekey gets expired in 48 hours and needs to be updated by the client whereas Identity key is permanent until app reinstall or change in device.

X3DH can still be initialised without one-time prekey if all the one-time prekeys are used up which can rarely happen. State of one-time prekeys are checked every 12 hours and if approximately 2/3 of 100 one-time prekeys are used up, they are replenished again. Expiry time of Signed Prekey can be extended to reuse it in future X3DH. The purpose of Signed PreKey is to provide some protection if no one time pre key was given, if a device was taken after the interval the initial shared secret still couldn't be calculated.


What is meant by "KDF2" vs "PBKDF2"? I see many references to KDF2 here, but all links are broken and Wikipedia does not have an entry for KDF2.  Is KDF2 a specific standard for Key Derivation without a password?

Ultimately, I am trying to make sense of why KDF2 is listed as PRNG for Crypto++ on Wikipedia.

KDF2 is a KDF defined in ISO 18033.  You can find a draft of that spec here.  See section 6.2.3.

As to why it's listed as a PRNG, remember that a KDF relies on a pseudo random function (PRF), so it's output needs to be random.


Are there encryption schemes that can be performed using an adding machine? There's been a lot of talk about encryption that can be done by hand, but what if the user is allowed an adding machine?

Let's say addition, subtraction, multiplication, and division are easy. Memory (i.e. the user writing things down) is possible but undesirable. Are there any good encryption algorithms that can be performed like this?

That means you have a turing machine, using a small memory is ok, but wasting memory is not desirable (as usual).

You can do all known encryption algorithms with that.


Constructing Bent functions of 8 variables I have gone through many literature on bent functions but could not find even a simple examples of creating bent functions. One theorem say like this       If $f(x)$ and $g(x)$ are two bent functions of $V_n$ and $V_m$ them $f(x) \oplus g(x)$ gives bent function of $V_{m+n}$. Can i get any example of creating bent function on V8 by xoring bent function on $V_6$ and $V_2$?   Basically if $V_6$ is having vars $x_1$ to $x_6$ and $V_2$ from $x_1$ to $x_2$ then how we will have function on $V_8$ having $x_1$ to $x_8$.
Any reference to document which generates bent function with example will be helpful to me.

You cited the theorem wrong. It is:
If $f(x)$ and $g(y)$ are bent, then $f(x) + g(y)$ is bent. The difference is, that the functions are not on the same variables. Otherwise you could use $f(x) = g(x)$, and then you get $f(x) + f(x) = 0$, which clearly isn't bent.

By applying above theorem multiple times, this should be bent:
$f(x_1,\dots,x_8) := x_1 x_2 + x_3 x_4 + x_5 x_6 + x_7 x_8$

I would suggest studying this presentation by Sihem Mesnager, where sections 5 adresses direct constructions and section 6 adresses secondary constructions (built from other bent functions):

Slide 30 has explicit direct constructions
Slide 42 ff. has the above theorem and other constructions from bent functions. Interesting: Slide 44 has a constructions of three bent functions over the same variables.


Cryptoanalysis using Frequency Analysis I have read some documents to decrypt ciphertext without a key using Frequency analysis. here are my questions:

If the most occurring Char is not 'E' then how do we start?
Let's say I have  this ciphertext

MLD BLF PMLD GSV TZNV SLD GL KOZB RG. TVG
    IVZWB ULI HRNROZI KILYOVNH RM BLFI VCZNH.
    XSVVIH.

Here is its decrypted text: now you know the game how to play it. Get ready for similar problems in your exams. cheers

can someone please help me to sort this out, here most occurring is 'L' but it is not 'E'. 'L' is 'o' here ... I am very confused.

This is a monoalphabetic substitution cipher - the same letter in the plaintext will always be represented as a identical letter in the ciphertext (for example the plaintext-letter "E" is always a "V" in the ciphertext).

Frequency analysis works better the longer the text is. For very short texts (as yours) it can be very difficult to have an exact representation of the frequency analysis. If the most occuring letter is not "E", then you can move on to the second-most common letter (which would be the letter "T")
Other / similar techniques:

Double-letter-words: Another technique you could try is to find all the words that have repeating letters, for your example that would be the last word "cheers". I think that in the English language the most common double-letter-words have 2 "L" in them, like "kill". But again this would fail, since here the double-letter-word is "cheers".

Word-frequency-analysis: You can also do a frequency analysis for whole words instead of single letters. Again, for the English language, this would be the word "the". For a long text you would expect that the word "the" would show up most often.

As you can see most of these common techniques would fail for your cipher-text. So the best technique you can use is brute-force.


Are ephemeral keys symmetric or asymmetric? My question is: Are ephemeral keys symmetric or asymmetric?

If symmetric, can ephemeral keys be created based on a (UserID || nonce)?

I think it is more common to explicitly name asymmetric key pairs ephemeral or static because it matters more on a generic, lower level algorithm description.

During key establishment, it matters a lot if keys are ephemeral or not. For instance, if you'd use static-static key agreement, then the agreed-upon key will always be the same, unless you explicitly mix in a random value. Only if the key is static will it also be able to provide entity authentication. Hence these schemes are described in a generic way of e.g. NIST Special Publication 800-56A
Revision 3: Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography which contains the following definition:

  A key pair, consisting of a public key (i.e., an ephemeral public key) and a private key (i.e., an ephemeral private key) that is intended for a very short period of use. The key pair is ordinarily used in exactly one transaction of a cryptographic scheme. Contrast with a static key pair.

If the terms are commonly used for DH keys within key agreement, then it is more likely that this will seep through to higher level protocol specifications such as TLS as well.

The main thing about ephemeral keys and ephemeral key pairs is that they are not pre-established, they are only established when required, and then discarded. This can be true for both asymmetric and symmetric keys. This of course also means that public keys cannot be trusted in advance. Pre-established keys / key pairs are also called static keys / key pairs.

Commonly you would expect ephemeral keys to be destroyed after a single use - storing them on persistent media is not expected.

Typical ephemeral keys are keys that are tied to a session in TLS. In there the E in DHE and ECDHE is used to denote ephemeral Diffie-Hellman authentication. Within TLS the client (EC)DH key pair is always ephemeral, so that one does not contribute to the E being present or not within the TLS cipher suite. Commonly however, the server's key pair is also ephemeral, so you get ephemeral-ephemeral key agreement to establish the symmetric master key and session keys. This scheme does not authenticate the server by itself.

Rather uncommonly, the server may use a trusted, static DH key pair where the public key is embedded in a certificate and the private key stored in the server. This is called ephemeral-static DH key agreement. In that case the DH key agreement will also authenticate the server.

Sometimes the ephemeral DH keys are also cached in memory for multiple sessions. This is more or less cheating; it's a dangerous performance hack (deriving key pairs is relatively expensive operation), which will have security related consequences.

The symmetric session keys in TLS are probably ephemeral keys. They are not called that way because well, they are already called session keys as they encrypt and/or authenticate the data in the session. As Dave commented, the master key may or may not be ephemeral, it depends on the protocol. However, these keys are used over multiple messages, so they are less ephemeral than an ephemeral DH key, which is only used for one key establishment.

Finally, ephemeral is a word, and the common meaning of words is written down in dictionaries (which pretend, in their arrogance, to define them). Let's take a look at the Merriam-Webster definition:

  Definition of ephemeral

  lasting a very short time, e.g. ephemeral pleasures
  lasting one day only, e.g. an ephemeral fever

When using these terms it is always a good idea to not deviate too much from the original meaning. However, it is of course possible that - for instance - a TLS session lasts longer than a day.

As for your question:

  If symmetric, can ephemeral keys be created based on a UserID or nonce?

It would be strange to create an ephemeral key from just a UserID, because that would always result in the same key. In that case the key value would not be called ephemeral. You can certainly create an ephemeral key from a nonce or combination of UserID and nonce, presuming that the nonce itself is ephemeral.

Neither of UserID or nonce sounds like a secret value, so you would not get any security properties from such a key. You can however use a static key, the user ID and (ephemeral) nonce to derive an ephemeral key:

$$\tilde{K}_{user} = \operatorname{KDF}(K_{master}, \mathit{UserID} \mathbin \| \mathit{nonce})$$

Note that the tilde above the ephemeral key is one way of showing that it might be ephemeral - different documents may use different notations and a tilde does not always mean ephemeral.


MAC size: Should MAC be shorter than cipher block size? Many sources claim that (if possible) a length of MAC should be as long as possible. So it should have the same size as size of the block of used cipher.

However there is the following note in Bouncy Castle source codes (CMac.java):

  "Note: the size of the MAC must be at least 24 bits (FIPS Publication 81), or 16 bits if being used as a data authenticator (FIPS
  Publication 113), and in general should be less than the size of the
  block cipher as it reduces the chance of an exhaustive attack (see
  Handbook of Applied Cryptography)."

Should MAC really be shorter, and if so, what is the "sweet spot"?

Or is that true only under some special circumstances?

Or is that true only under some special circumstances?

This statement is based off of Remark 9.60 of the Handbook of Applied Cryptography (PDF of chapter 9) which reads as when talking about the strongly related CBC-MAC:

  Remark (truncated MAC outputs) Exhaustive attack may, depending on the unicity distance of the MAC, be precluded
  (information-theoretically) by using less than $n$ bits of the final
  output as the m-bit MAC. (This must be traded off against an increase
  in the probability of randomly guessing the MAC: $2^{−m}$.) For $m =
 32$ and $E = \operatorname{DES}$, an exhaustive attack reduces the key
  space to about $2^{24}$ possibilities. However, even for $m < n$, a
  second text-MAC pair almost certainly determines a unique MAC key.

So the idea behind this remark seems to be: If you are given only a single message-tag pair, and you truncate the tag, you cannot possibly find the the right key that produced this tag, because many keys will produce this truncated tag. However as you see more message-tag pairs, this advantage fades away as there are lesser and lesser keys producing the right tags on all these pairs. Also note that assuming you filter the entire keyspace for the first tag to get candidates for the second run, you have to perform $2^k$ operations and will get significantly less than $2^k$ keys in return on which another brute-force attack should take negligible time as the time is dominated by the primary brute-force and that stays true for truncated and non-truncated MACs.

TL;DR: Truncating tags in this case can make brute-force a little bit harder, but it's a case of "infeasible" versus "infeasible", so rather don't truncate and enjoy the ideal anti-forgery probability.


What are the number of output bits of the internal function F used in BPS algorithm? In the BPS specification document it says

  We denote by f the number of output bits of the internal function F

What is this if the internal function is AES? Would it be the block size (e.g. 128)?

Yes, in BPS, if the internal function $F$ is a block cipher, then $f$ is its block width, thus 128 for AES (for all key width variants). That's clear enough in the paragraph quoted in the question:

  We denote by $f$ the number of output bits of the internal function $F$. (...)
  If $F$ is a $f$-bit block cipher (...)
  We denote by $F_K(x)$ the application of the block cipher $E$ with the key $K$ on the plaintext $x$ ($F_K(x)=E_K(x)$), (...)


Yao's theorem for the uniform case Yao's theorem says that for a distribution, next bit unpredictability is equivalent to pseudo-randomness. This link proves Yao's theorem, but the proof relies on non-uniform probabilistic polynomial time algorithms. Is there a proof of Yao's theorem that instead only uses uniform probabilistic polynomial time algorithms?

At the end of Section 2 of the lecture notes that you cite, it explicitly states "We note that an analogue of this result holds for uniform distinguishers and predictors, provided that we change the definition of next-bit predictor to involve a random choice of $i \leftarrow R [n]$ instead of a fixed value of $i$, and change the time bounds in the conclusions to be $t − O(n)$ rather than $t − O(1)$ and $t$ (we can’t do tricks like in the final paragraph of the proof). In contrast to the multiple-sample indistinguishability result from last time, this result does not need $X$ to be efficiently samplable for the uniform version."


RSA encryption input range - plaintexts that map to ciphertexts? According to the wiki article on the RSA encryption function, the valid range of input $m$ is $0 \leq m \lt n$. However I have found that the following values of $m$ always return themselves when encrypted:

$0$
$1$
$n - 1$
$n - 2$

Have I implemented the algorithm incorrectly or am I misreading the wiki article?

Yes, this is textbook RSA, so by definition:

$0^e \equiv 0 \pmod{n}$

$1^e \equiv 1 \pmod{n}$

$(n - 1)^e \equiv (-1)^e \equiv -1 \equiv n - 1 \pmod{n}$

(since $e$ must be odd as $\varphi{(n)}$ is even and thus $2$ has no modular inverse modulo $\varphi{(n)}$)

This is (obviously) bad since an observer can immediately deduce the plaintext for those messages even without knowing the decryption exponent, but normally you use padding in real life RSA which makes those kind of inputs essentially impossible.

However you are wrong for $n - 2$. It does not necessarily encrypt to itself. How did you get that? You must be making some mistake in your implementation, or perhaps got lucky with a few small inputs.

Counterexample, $n = 377$, $e = 17$ ($d = 257$, $\varphi{(377)} = 336$):

$(n - 2)^e \equiv 375^{17} \equiv 124 \pmod{377}$

Are you sure you are calculating $e$ right?


I need to know number of encryption/decryption operations? If i want to break quadruple DES (say EDED), what is complexity? Like for EDE, it is O(2^112).

I'm not sure you understand the purpose of EDE. EDE only specifies the order of operations of the DES primitive in 3DES is Encrypt-Decrypt-Encrypt. It does not specify the amount of key material. That's determined by the key option.

In 3DES, key option 1 uses three independent keys for a total of 168 bits, meaning a brute force attack requires 2^168 attempts. Note that in this case using EDE results in the same amount of work and protection as EEE would.

Key option 2 uses two keys for a total of 112 bits, or 2^112 attempts. They are used in a 1-2-1 pattern, helping protect against a meet-in-the-middle attack.

Key option 3 means the same 56-bit key is used for all three DES operations - the EDE causes the second pass to decrypt the first pass, yielding the plaintext to be reencrypted by the third pass. It's backwards compatible with single DES. This is the reason EDE was created, to serve old 56-bit applications back when they were trying to upgrade from DES.

So that's why EDED doesn't actually make much sense. There is no backwards compatibility it would preserve, so EEEE would be a less complex choice. However, going forward with the idea that 4DES is a decision someone would make over AES-256 (which would probably be a bad idea), I would assume they would do so with four independent keys, for a total strength of 224 bits, or 2^224 attempts.

Note that all these answers are excluding any benefits in performance gained by cryptanalysis of the algorithms.


Usage of twists at pairing-based cryptography First of all I would like to understand how twists are used in pairings. The 2nd step is, how to use them to improve the calculation speed?

Say $E'(\mathbb F_{p^2})$ is a twist of $E(\mathbb F_p)$.

I just thought about choosing $m_1,m_2\in (0,\lfloor \sqrt{\operatorname{ord}(E)} \rfloor)$ randomly, define $m=m_1+m_2\cdot \lambda$ and performing $mP=m_1P+ m_2\psi(P)$, where $P\in E$ and $\psi:\ E\to E'$. My main thought about this technique is, to reduce the size of the integers $m$ and performing two scalar multiplications in different groups, if this might be a speed-up. But then we should have $\psi(P)=\lambda P$ for any, maybe large $\lambda$. If this idea was already mentioned before, could someone link me a paper or any other source?

Feel free to edit this post, if necessary, and add tags. :)

Edit1:
To make the explanation (maybe) a bit easier, consider $E:\ y^2=x^3+x$ and the twist $E':\ y^2=x^3+2^{1/4}x$ over $\mathbb F_p$ and $\mathbb F_{p^2}$ with the embedding degree $k=16$.

Edit2: If I remember well, we should consider a type-2 pairing, where $G_1\neq G_2$ and $\psi:\ G_1\to G_2$ is efficient, but $G_2\to G_1$ is not efficient. I guess this holds in our situation, since $\newcommand\F{\mathbb F}\F_{p^2}=\F_p[x]/(X^2-2)$ for $p\equiv \pm3\pmod 8$.

I'm not sure I understood your question, but... twists are used to improve performance. In your example, without twists, $G_2$ is $E(\mathbb{F}_{p^{16}})$. With a quartic twist, you can use $E'(\mathbb{F}_{p^{4}})$, which is much more efficient (the reason for this is that the homomorphism $\Psi$ maps the point coordinates to sparse elements of $\mathbb{F}_{p^{16}}$, i.e. with a lot of zero coefficients, which can be multiplied much faster by ignoring the internal multiplications by zero).

The splitting of the scalar $m$ into $m_1, m_2$ is known as "GLV method". While it is used to speed up point multiplications, as far as I know it can't be applied directly to the pairing computation. But it can be used for pairing-based schemes that use point multiplication along with the pairing computation.


AES in Counter mode for 64 bit input I was reading how AES can be used for 64 bit data. Than i came to this answer :Is it possible to implement AES with a 64-bit I/O block size?

The answer here is given that by running AES in counter stream mode 64 bit plain text produce the 64 bit cipher text. But i can't under this point when 128 bit cipher text produced by AES block cipher is XOR with 64 bit plain text. How it produce 64 bit output?

The idea of a counter stream mode of AES is to generate an random stream of bits by chunk of 128 bits but you are not forced to use all the 128 bits of it.

To encrypt the process is the following, considering $m$ the 64 bits message :

Generate $s = AES(Key, Nounce)$
Notice that $s$ is 128 bits long so $s = s_1 || s_2$ where $s_1$ and $s_2$ are 64 bits long.
$c = m \oplus s_1$ and drop $s_2$ (useless)

To decrypt the process is the same:

Generate $s = AES(Key, Nounce) = s_1 || s_2$ where $s_1$ and $s_2$ are 64 bits long.
$m = c \oplus s_1$

Even though I provided you an answer from a Crypto point of view, I consider this question as off-topic as it feels more like it requires a code answer rather than a Crypto answer (more math oriented).


Is there a well known way of splitting a piece of information so that the information is only recoverable if all the pieces are together? By "splitting", I mean turning one chunk of information into more than one chunk. The new chunks do not necessarily have to be of a smaller size. I imagine the use of this could be something similar to the nuclear launch protocol, where two people with separate keys must be present.

Unfortunately, this is one of those hard-to-google questions. Google always returns results about splitting a file into smaller pieces for easier file transfer, which is unrelated.

A simple protocol I came up with for this is to XOR the data with random values. For example, to split a plaintext $p$ into 3 chunks, you generate two random values $r_1$ and $r_2$. You then save $r_1$, $r_2$, and $r_1 \oplus r_2 \oplus p$ as your pieces.

Is there a better known algorithm like this?

What you are describing is called secret sharing schemes.

The scheme you outline is sometime called XOR-sharing (or additive secret sharing more generally). It is a very used scheme as a sub protocol in more advanced cryptographic protocols (such as secure computation protocols). This scheme has perfect security. It is also very fast because it only requires XOR. So from those perspectives it is a good secret sharing scheme.

However, secret sharing schemes comes in many flavors with different properties, so it's not possible to say if there are better schemes. There certainly are more advanced schemes. But whether they are better depends entirely on the application.

For example, a weakness of XOR-sharing is that you need all the pieces of the secret in order to reconstruct the secret. Schemes exists where you can pick a parameter $t$, called the threshold, so that any group of size $t + 1$ pieces is enough to reconstruct the secret. These types of secret sharing are called threshold secret sharing schemes. The most well known scheme of this type is called Shamir secret sharing, which is based on polynomials over finite fields.


How does the key size in supersingular isogeny schemes relate to their security level? I'm looking at the De Feo, Jao, and Plût 2014 paper:

Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies.

My understanding of section 3.2 Key Exchange, is that Alice's private key is the isogeny $\phi_A : E \rightarrow E_A$, which can be represented by 2 integers; private key: $(m_A, n_A)$.

Her public key consists of the curve $E_A$, represented by the polynomials $a,b$ from its Weierstrass equation $E_A: y^2 = x^3 + ax + b$, and the images of the two torsion bases $P_B, Q_B$ under her private isogeny, which appear to be 2 complex points each = 8 integers. Public key: $(E_A, \phi_A(P_B), \phi_A(Q_B) )$. So my fuzzy understanding thinks that the public key should contain around 10 - 16 pieces of information, depending on how those polynomials are represented.

In the experimental section, section 7, there's a table comparing runtimes of the key exchange algorithm for key sizes of 512 bits, 768 bits, and 1024 bits.

My question: Where do those key sizes come from? Do they ever state the bit widths of the different components of the public key, and which one(s) they are varying to change the key size? Better yet, did I miss an analysis of the relationship between the key size and the security level of the system?

Those numbers for the key sizes come from the bit length of the prime chosen for the finite field $F_p$.  To clarify, there are no complex numbers used at all.  The elliptic curve is over a quadratic extension of $F_p$, i.e. $K = F_{p^2}$, and a root $i$ of $x^2+1$ is chosen, so that elements of $K$ can be represented as uniquely as elements of $F_p \oplus i\cdot F_p$, i.e. $a+ib$ for $a,b\in F_p$.  If $p$ is $N$ bits long, then general elements of $K$ are $2N$ bits long.  Points $(x,y)$ on the elliptic curve $E$ have $x,y \in K$, so they are then $2\cdot2N = 4N$ bits long.  The coefficients of $E$ are also elements of $K$, so they're also $2N$ bits long.

The public key consists of the two $K$ coefficients to express the elliptic curve $E_A$ (so $4N$ bits), and the two points in $E_A$, $\phi_A(P_B)$ and $\phi_A(Q_B)$, which are each $4N$ bits long.  The total length of the public key is then $12N$ bits.  However, it is possible to compress this, as you can see in Costello-Longa-Naehrig, where they get this down to $6N$ with some clever techniques. Later work improves this to about $3.5N$ while reducing the computational effort at the same time.

The relationship between key size and security level is covered in section 5.1.  So far, the best classical attack is $O(\sqrt[4]{p})$, so $N/4$ bits of classical security, and the best quantum attack is $O(\sqrt[6]{p})$, so $N/6$ bits of quantum security.  That's why the 768-bit p has 768/6 = 128 bits of quantum security.  I really recommend reading Costello-Longa-Naehrig, as some of the details are made more explicit.


How do i approach file encryption using encrypt-then-mac? I'm programming a cryptographic application that encrypts files, locked with the password the user supplies. It's not intended to be used in production. It's a project for me to learn more about encryption.

I have programmed the encryption part already, it's in C# and i'm using CBC as cipher mode.

I want to add authentication to my encryption and i plan on doing that by using CBC + HMAC(SHA256). I know that i have to HMAC the IV + Ciphertext. And yes i know BouncyCastle has an API that offers GCM(which is probably preferred over using CBC + HMAC), but the API's barely have any documentation and i read that CBC + HMAC is probably just as secure if done correctly. KeePass(Keepass) uses it too.

However i'm not sure how to go about generating keys for the HMAC and the encryption itself. If i understand correctly it's always best-practice to use different keys for different operations (and rightly so).
I'm currently encrypting the file content with a key that is generated by deriving a 256 bit key with the PKBDF2 algorithm(which takes a salt and does 10.000 iterations), but i need a key for the HMAC too. What is the best way to go about generating a key?

If you notice any mistakes and/or misconceptions in this post please tell me.

Derive a 256-bit master key from your password using a password-based key derivation function like scrypt or argon2.

(Don't use PBKDF2 if you can use newer better alternatives that take advantage of memory, not just time, to drive up the adversary's costs.)
Derive subkeys for each purpose using HKDF-SHA256 with a distinct info parameter.

You can feed this master key to HKDF-Expand as the initial keying material (IKM) with some additional salt, but that step isn't necessary if the master key is already derived by a salted PBKDF; you can also use this master key directly with HKDF-Extract as the pseudorandom key (PRK).
Generate known-answer test vectors for the scheme you think you're implementing, using another tool (e.g., write it in C with OpenSSL), so that you can do a self-test when you run your C# program to confirm that it's doing the same computation.
Consider copying the behavior of the scrypt file encryption tool, which has a simple file format and makes it easy to generate test vectors and confirm you're interoperating with another implementation of a good, secure protocol.


AES Affine Transformation Polynom Representation I have been reading on the polynomial representation of the AES Sbox in the PDF “Essential Algebraic Structure Within the AES” by Murphy and Robshaw (www.isg.rhul.ac.uk/~sean/crypto.pdf) on page 7, that the affine transformation can be represented as $f(a) = \sum^7_{k=0} \lambda_ka^{2^k}$ where $(\lambda_0, \lambda_1, \lambda_2, \lambda_3, \lambda_4, \lambda_5, \lambda_6, \lambda_7)$ = (0x05, 0x09, 0xf9, 0x25, 0xf4, 0x01, 0xb5, 0x8f). Can me anybody tell how to compute this values $\lambda_0,\ldots,\lambda_7$ from the Matrix $L_A$ on page 7?

Best regards

One way to derive the values $\lambda_0, \lambda_1, ..., \lambda_7$ would be to formulate the eight simultaneous equations in GF(256):

$$\lambda_7 01^{128} + \lambda_6 01^{64} + \lambda_5 01^{32} + \lambda_4 01^{16} + \lambda_3 01^{8} + \lambda_2 01^{4} + \lambda_1 01^{2}  + \lambda_0 01^{1}  = Aff(01)$$
$$\lambda_7 02^{128} + \lambda_6 02^{64} + \lambda_5 02^{32} + \lambda_4 02^{16} + \lambda_3 02^{8} + \lambda_2 02^{4} + \lambda_1 02^{2}  + \lambda_0 02^{1}  = Aff(02)$$
$$\lambda_7 04^{128} + \lambda_6 04^{64} + \lambda_5 04^{32} + \lambda_4 04^{16} + \lambda_3 04^{8} + \lambda_2 04^{4} + \lambda_1 04^{2}  + \lambda_0 04^{1}  = Aff(04)$$
$$...$$
$$\lambda_7 80^{128} + \lambda_6 80^{64} + \lambda_5 80^{32} + \lambda_4 80^{16} + \lambda_3 80^{8} + \lambda_2 80^{4} + \lambda_1 80^{2}  + \lambda_0 80^{1}  = Aff(80)$$

(where $Aff$ is the affine transform, not counting the addition of the constant), and 80 is the GF(256) element represented by the bit pattern '10000000')

and solve this set of 8 linear equations in $\lambda_0, \lambda_1, ..., \lambda_7$

Both sides of these equations are linear; that is $(x^{2^k} + y^{2^k}) = (x+y)^{2^k}$ and $Aff(x) + Aff(y) = Aff(x+y)$, and so if find such a set $\lambda_0, \lambda_1, ..., \lambda_7$, that set will hold for a sum of any subset of (01, 02, 04, ..., 80); since that's the entire field $GF(256)$, we have:

$$\lambda_7 x^{128} + \lambda_6 x^{64} + \lambda_5 x^{32} + \lambda_4 x^{16} + \lambda_3 x^{8} + \lambda_2 x^{4} + \lambda_1 x^{2}  + \lambda_0 x^{1}  = Aff(x)$$

for all $x$.


Size and usage of lookup table in cryptographic schemes I would like to understand the typical size of a lookup table for software implementations of a cryptographic scheme.

What size is considered reasonable?
What make them (in)efficient?
Are there heuristics to determine (without implementing anything) if a table will become interesting?

This is a very / too generic question:

  Q1: What size is considered reasonable?

Any size that fits easily in the CPU cache(s) of the target platform. Otherwise it depends on the memory requirements for the algorithm in general.

  Q2: What make them (in)efficient?

If the CPU data cache needs to be refreshed continuously then they may slow down the algorithm and, if you're unlucky, leak side channel information as well.

  Q3: Are there heuristics to determine (without implementing anything) if a table will become interesting?

Probably not as it depends a lot on specifics of the underlying platform.

In general lookup tables are used to speedup calculations, so as long as the resulting implementation is faster, you're in business.

But note that there may be security implications when using them, all depending on what is being implemented.


521-bit ECC keys are the same strength as RSA 15,360-bit keys 521 bit ECC uses key sizes 7.5 times smaller than the RSA standard while offering encryption that is magnitudes more secure. An RSA 2048-bit key's secure enough for banking, but a 521-bit ECC key is the equivalent of a 15,360-bit RSA key.

I read it on SKYECC - Explaining 521-bit ECC Encryption From the Ground Up.
Can anyone give me an independent answer and opinion on the claims made here
This messaging apps claims to be the most secure

Is there a really much difference between 128bits 256bit and 512bits as it comes to security implemented in messaging apps or is t more important the way it has been implemented?

When it comes to asymmetric cryptosystems like RSA and ECC, security in bits is not the figure quoted in bits for key size (which itself has no universal relationship with the number of bits in the actual form taken by either the public or private key, which I won't further discuss in this answer).

Oversimplifying, and sticking to attacks using classical computers (because quantum computers usable for cryptanalysis are only an uncertain possibility for a remote future)

$n$-bit security means that $2^n$ operations of some kind are believed needed on a classical computer to attack the system from ciphertext or other intercepted data. 96-bit security seems practically secure today (even 80-bit was never broken in a public attack), and each additional bit doubles the difficulty, making 128-bit safe for perhaps one or more decades, depending on one's wilderness of imagination. Anything above is for long-term security, or as a margin for attacks not envisioned in evaluation of the security level.
With ECC, $n$-bit security requires a curve on a finite field which elements need at least about $2n$ bits for their representation, and that $2n$-bit field size is usually what's quoted as size or key size. Thus 256-bit ECC gives at most about 128-bit security, 521-bit ECC gives at most about 260-bit security, rounded to 256-bit because that's a common symmetric key size.
With RSA, the public modulus size as found in (or derivable from) the public key is what's quoted as size, or key size (like, 2048-bit or 15360-bit). Its relationship to security level is more complex than in ECC. NIST SP 800-57 Pt 1 gives these very rough figures, which indeed tell (bottom line, leftmost and two rightmost columns) that 256-bit security is roughly obtained for 15360-bit RSA or 521-bit ECC.

  Is there a really much difference between 128bits 256bit and 512bits as it comes to security implemented in messaging apps or is t more important the way it has been implemented?

For data becoming of no value after less than a decade, there is not really much difference between 128-bit security and higher grades (but in the unlikely case that in the above "128bit" was an ECC field size, or if any of "128bits 256bit and 512bits" was an RSA modulus size, these numbers would be too low for decent security).

For key sizes giving decent security level (with the limit perhaps somewhere between 72 to 112-bit security these days depending on a variety of factors), what matters most to security of a messaging apps is who can get at the keys and ancillary data (like, most importantly, who communicates with who), what's done with the crypto, and the quality of the implementation.


Is a RSA-signature of some identifying data a safe way to implement a license key? I have this idea of implementing a license key:

After the user downloads the program, he connects to a website and sends his Windows product ID.
The website, then, sends this back to him with a signature using a private RSA key.
The program, then, checks, using a public key, whether it is really signed by the private key, and stores this message it got.

Now, every time the program starts, it retrieves this message, and checks it in the way mentioned in 3., comparing that with the windows product ID retrieved from the operating system.

This is done using 1024 bit numbers.
I can't encode anything with the private key using what the computer language (C#) offers. (I don't want to implement my own algorithm – I don't know enough about encryption.)

Is the Windows product key long enough for this? It's something like 12345-abc-1234567-12345. (Get it by right-clicking on “my-computer”, and clicking “properties”.)

I apologize for my non-cryptographer way of asking. Here are the questions:

a) Is encrypting a small number by a large key safe?

b) Is signing a message (as opposed to encrypting it) safe?

That is not a bad method of doing a license key; an attacker would certainly be unable to generate a signature that would validate with his computer's window product key.

On the other hand, this approach may be overkill. The easiest way to attack this system would be to modify the program to skip (or ignore) the signature validation; hackers have both the experience and the tooling to do this fairly easily.  I don't believe that there are any easily implemented license key approaches that make that attack more difficult; however, there are certainly other approaches that would be easier to implement.

Since you asked for cryptographical advice, here is some:

If you do use this approach, you might as well make sure you get the details correct; you use a known-good padding scheme (say one of the ones listed in PKCS #1).
You ask whether the window product key is long enough.  The answer is "Yes, it is".  Actually, the length of what you sign is not important to the security of the signature method; it just needs to be long enough to be unique.


Calculate if a digital signature is valid In the book An Introduction to Mathematical Cryptography, it mentions a section on digital signatures and a theoretical example. I am having difficulty understanding the book and I was wondering if someone could better explain how you would be able to deduce if a signature is valid rather than finding what the signature is.

For example, $N = 1562501$ and the public key is $e = 87953$, the document $m = 161153$, and the signature is $d = 870099$. Is there a technique to find if it's a valid signature?

Basically RSA signatures work just like encryption but with the keys exchanged.
If somebody tells you $m^{sk}$ you can easily test if
$$
(m^{sk})^{pk} \equiv m\ (mod\ N)
$$
but you cannot calculate $m^{sk}$ yourself.

The problem/trick is the usual, exponentiation is easy but logarithm is hard.

(I like using $sk$/$pk$ for secret-/public-key rather than $d$/$e$ for decryption-/encryption-key as it makes more sense for signatures.)


Is RSA in a ECB-like-mode safe for bulk encryption? Let's say I would like to communicate with my friend using asymmetric/public-key encryption, e.g. RSA.

(Note: I do realize that in practice this is done through an intermediate symmetric key, but this question assumes we only use asymmetric encryption.)

Say I try to do this: I slice up my data into 2n-byte blocks (padding with zeros [edit: padding appropriately] if necessary), append the block index to the block (to prevent the same plaintext from turning into the same ciphertext), then use my friend's public key to encrypt each block separately.

Is this a secure scheme, or does the fact that I'm re-using the key make it susceptible to some kind of attack? If so, is it used in practice in any existing algorithms? If not, is there any way to make it safe, aside from using a symmetric key?

Well, reusing a key isn't a problem; after all, RSA keys are generally used many times.

However, if you fix the padding, there does exist one other potential problem; message malleability.

To example, suppose Alice sends two messages to Bob, $X_1, X_2$ and $Y_1, Y_2$.  To send these, Alice actually sends:

$E(X_1), E(X_2)$

$E(Y_1), E(Y_2)$

Now, Eve can't modify each individual block (RSA with proper padding prevents that); what she can do is mix-and-match blocks, as so:

$E(X_1), E(Y_2)$

This would decrypt at $X_1, Y_2$, which might not be what Alice and Bob whats.

If you are silly enough to use RSA encryption in this manner, you do need something that binds the blocks together (or alternatively does some sort of integrity checking on the entire message).

As for whether people ever do this in practice, well, no they don't -- not because of security, but because it's so inefficient; using the RSA algorithm to communicate a symmetric key, and using that symmetric key to encrypt the message is far more efficient.


How can I generate large prime numbers for RSA? What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption?

I'm aware that I can find any number of articles on the Internet that explain how the RSA algorithm works to encrypt and decrypt messages, but I can't seem to find any article that explains the algorithm used to generate the p and q large and distinct prime numbers that are used in that algorithm.

The standard way to generate big prime numbers is to take a preselected random number of the desired length, apply a Fermat test (best with the base $2$ as it can be optimized for speed) and then to apply a certain number of Miller-Rabin tests (depending on the length and the allowed error rate like $2^{-100}$) to get a number which is very probably a prime number.

The preselection is done either by test divisions by small prime numbers (up to few hundreds) or by sieving out primes up to 10,000 - 1,000,000 considering many prime candidates of the form $b+2i$ ($b$ big, $i$ up to few thousands).

The deterministic prime number test by AKS is to my knowledge not yet used as it is slower and as the likeliness that an calculation error caused by the hardware is higher than $2^{-100}$.

Most smart cards offer a coprocessor for modular arithmetic with moduli from 1024 up to few thousand bits. The manufacturers often provide also libraries for RSA and RSA key generation using the coprocessor.


RSA: Given two very large prime $p,q$ and $n=p\;q$, how to quickly find $e$ such that $\gcd(\varphi(n),e)=1$? I can imagine that finding $p,q,n$ are easy, but my text book also says the $e$ can be found rapidly, so how does modern RSA find this $e$?

Normall practice is to pick public exponent as a small prime(preferably with few set bits in binary representstion). If the public exponent is prime we only need to verify it doesn't devide $\phi(n)$.


Is a subset of a random set still random? Suppose you have an infinite list of random bytes, and you select the first N bytes that correspond to printable ASCII characters. Is this list of N bytes still as secure (e.g. for the purpose of a crypto secret or salt) as accepting all of the bytes (printable ASCII or otherwise)?

I am basically asking whether this code has any cryptographical weakness:

https://github.com/opscode/cookbooks/blob/master/openssl/libraries/secure_password.rb#L26

(Assuming that the output of OpenSSL::Random.random_bytes(1) is indeed random.)

Already answered here: https://stackoverflow.com/questions/471157/is-a-subset-of-a-random-sequence-also-random , take a look at all the answers.

But, saying in other words:

If you have a list of random bytes, any selection you make in that list will be random as well, according to your selection criteria.

Examples:

if you choose every 3rd element, you'll end up with another random
list;
if you pick up all the elements that are smaller than any
value, you'll end up with a list with random elements smaller than
your criteria;
if you choose to pick up the first 10 elements, you
have 10 random values;
... and so on.


Given a collision in a MAC function, is it possible to work out how the MAC function works and generate valid MAC values for any message? So given you can find a collision for any MAC value, would this be viable without knowing the key.
Even if you couldn't figure out how that MAC function works, could you find valid MAC values for a message without needing to know how it works.
If so how would you go about doing this.

No you would generally not be able to do this. If you find a collision without a key then it's just an indication that the output size is too small. Quite often the MAC depends on a block cipher or hash function. The latter is one-way by definition, the former is one-way unless you know the key.
It's of course a different proposition if you find a MAC collision because you found a weakness in the algorithm or the establishment of the secret key. If an attacker found a weakness it is very likely that the attacker already knows the algorithm. And yeah, if an attacker know the key the game is over. Finding another collision might still be tricky if the output size is large enough, depending on the algorithm used.
"could you find valid MAC values for a message without needing to know how it works". No, with the possible exception that length extension attacks may work, e.g. for CBC-MAC and CMAC. This would require the full output of the calculation though, so chances are that you will not find a collision for a cipher with a large enough block size (e.g. AES instead of DES).


How do you find the inverse degree of a hash function? I am trying to learn cryptanalysis on the Keccak hash function. One of the papers on zero sum distinguishers talks about Keccak having inverse degree of 3.

I am unable to figure this out: how do you get an inverse degree of 3? For example one of the permutations Chi in Keccak does the multiplication in GF(2). So I would guess that means the image transformation for Keccak has degree 2, but am unable to figure out how they derive degree 3 for preimage or inverse or going backwards.

If someone can point me to a resource, that would be of great help, since I am unable to find one.

Trying to express the inverse of the non-linear Chi fonction of Keccak as a multivariate polynomial of the bits of the state will yield a degree 3 polynomial.

How to derive such inverse is explained in section 6.6.2 of Joan Daemen PhD thesis as stated page 15 of http://keccak.noekeon.org/Keccak-reference-3.0.pdf


Long passwords and Bcrypt I need to store passwords for a web application, and was looking at Bcrypt for a possible solution. After some research, it appears only the first 72 bytes influence the final hash output. While it is possible for the application to limit input to 72 characters, this hurts users with password managers that produce very long passwords.

While it is well known that hash1(hash2(x)) only serves to increase collisions, there doesn't seem to be much information about the implications of using bcrypt(hash1(x)), as indicated by this answer.

First idea

If the password p is p > 72 bytes, SHA512 [64 bytes] the password and then Bcrypt the hash.

Possible cons:

hashing a hash
the input to Bcrypt is only ever as big as the output of the hash function (64 bytes)

Second idea

If the password p is p > 72 bytes, calculate the hash with (pseudo-code):

bcrypt(p[0:8] + sha512(p))

This Bcrypt's the concatenation of the first 8 bytes of the password (which is 72 - 64, where 64 is the bytes of the SHA512 hash) with the SHA512 [64 bytes] digest of the entire password. By this, the Bcrypt function hashes an entire 72 bytes, instead of just 64 like with the plain old SHA512 [64 bytes] hash.

Probable pros:

full 72 bytes are Bcrypt'ed
does not Bcrypt just a hash; this may make it so that if a collision is found in the SHA512 [64 bytes] hash, there are still a leftover of 8 bytes of entropy needed to crack the password

Possible cons:

still involves partially hashing a hash

I'm under the impression that the second idea is the best and most secure way to go, but I'm not sure if that, at all, decreases security for passwords > 72 bytes in length. I'm asking if there are any obvious (or non-obvious) security implications with choosing this method.

A password manager that produces 16-character passwords is sufficient for most cases. Users who go for 100-byte passwords are usually overly-paranoid, since the actual security benefit is outweighed by the inconvenience. Therefore, limiting a password to 72 characters, while in theory reducing the number of possible passwords, is still very reasonable.

That said, hashing a hash is a bad idea if the hashes are related. sha512(sha512(password)) is more prone to collisions than sha512(password). However, bcrypt (being built with blowfish) is different enough from sha512 that this doesn't apply (not to mention bcrypt is salted). While you're still reducing a user's password from 72+ bytes to 64 bytes, the expected entropy of a user password is orders of magnitude less than 512 bits. It is safe to assume that sha512(password), while technically shorter than password, has much entropy as the original password.

Your second idea seems to be reusing a part of the password, so I don't see much of an increase in security. The entropy from p[0:8] will be spread out with sha512 sufficiently enough already.


Terminology for secret sharing? To my understanding, there are two "approaches" to t out of n threshold encryption. In both of them, n shares are given to different shareholders, and at least t of them must agree to "proceed". "Proceed" can take two different meanings: either the shares are the input to derive a secret that can be used to perform a traditional decryption (e.g. Shamir) or the shareholders produce a partial encryption that can be put together to generate the decryption (e.g. Damgård-Jurik).

I have found the first scenario to be known as secret sharing, but I am looking for a term to describe the second approach unambiguously. Does such term exist?

I believe there is strong enough precedence for using the term threshold decryption for the second.

The abstract of this paper states:

  A threshold decryption scheme is a multi-party public key cryptosystem that allows any sufficiently large subset of participants to decrypt a ciphertext, but disallows the decryption otherwise.

Sounds to me like what you are talking about. A search for "threshold decryption" turns up plenty of hits too.


Simulation of Chosen Plaintext Attack on CBC, Predictable IV with OpenSSL I would like to simulate the CBC IV attack where the IV is predictable.
It's described in the answer to this question:
chosen plaintext attack on CBC, predictable iv

(Only "Yes" and "No" are valid messages and the attacker knows this)

I am using 128-bit AES, CBC mode. Everything is in hex

Key: 00112233445566778899aabbccddeeff
IV1: 12121212121212121212121212121212
Msg: Yes
Ciphertext: 030a 6eac 2641 e072 bd51 0d84 fb87 08da

I have encrypted the message like this:

printf "Yes" > yes
openssl enc -aes-128-cbc -e -in yes -out yes.aes -K 00112233445566778899aabbccddeeff -iv 12121212121212121212121212121212

The next IV (IV2) is going to be:

12121212121212121212121212121213

When an attacker knows this, it can calculate

IV1 XOR IV2 XOR "Yes"

and submit it to be encrypted with the next IV. If the ciphertexts match, then the attacker knows that the first message was in fact "Yes"

In my example the XOR calculation results to 59 65 72 which is in ASCII:

Yer

(calculated with http://xor.pw)

Now let's encrypt this and check if the ciphertexts match:

printf "Yer" > yer
openssl enc -aes-128-cbc -e -in yer -out yer.aes -K 00112233445566778899aabbccddeeff -iv 12121212121212121212121212121213

But now I get this as the ciphertext:

4378 8d70 de54 d287 8f64 1c8d ec40 de91

I was expecting it to be the same ciphertext as the one for the original "Yes"

I can't find my error. The attack should be correct, so I guess I am using OpenSSL incorrectly?

Okay, I solved it.

First of all, I do not need to worry about the padding as I only care for the first block (I know that the message is either Yes or No and therefore never longer than one block) and I can just discard the added block. In reality I probably won't be able to persuade the encryption oracle to use -nopad anyway :)
These are the values that I used

Key:              0011 2233 4455 6677 8899 aabb ccdd eeff

Original Message: Yes || padding
                  5965 730d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0d
Original IV:      1212 1212 1212 1212 1212 1212 1212 1212
Message XOR IV:   4b77 611f 1f1f 1f1f 1f1f 1f1f 1f1f 1f1f

Encrypted Message:
                  030a 6eac 2641 e072 bd51 0d84 fb87 08da  -- Actual Message
                  25ff efd9 b2ca 90f9 9c57 7006 0e53 2437  -- this is just padding

Next IV will be:  1212 1212 1212 1212 1212 1212 1212 1213
Message:          5965 730d 0d0d 0d0d 0d0d 0d0d 0d0d 0d0c -- last byte changed!
Message XOR IV:   4b77 611f 1f1f 1f1f 1f1f 1f1f 1f1f 1f1f
                  -- has to be the same as for the original message: check :)

Encrypted Message:
                  030a 6eac 2641 e072 bd51 0d84 fb87 08da -- Message
                  25ff efd9 b2ca 90f9 9c57 7006 0e53 2437 -- this is just padding

We see that the first block of the ciphertexts match (also all following blocks as it is deterministic). Therefore the original message must have been "Yes". We do not need to care about the padding.


RCON for AES 192 and 256 This is question about how many RCON values are used in AES 192 and 256.
I read the NIST Publication introducing AES and in Appendix A.2 and A.3 (Key Expansion for 192 and 256-bit keys), only $rcon_1$ to $rcon_8$ were used for 192 bits and upto $rcon_7$ for 256 bits. My question is how can only 7 or 8 values of $rcon$ be used when we have more rounds in AES 192 and 256.
To my understanding, $rcon$ is used every round so should't we have more $rcon$ values (owing to the increased no. of rounds in  AES192 and 256) instead of less?

You have 10, 12, and 14 rounds respectively; however, they are not linear increments depending on the key schedule.  For AES-192, you have 8 different values and you have 7 values for AES-256.  The RCON value only changes with every round for AES-128.
The RCON value (in hardware) is generated by a register that is 8-bits and increments every round. It wraps around with the count, and left alone for encryption, you'd get:
0: 00000001
1: 00000010
2: 00000100
3: 00001000
4: 00010000
5: 00100000
6: 01000000
7: 10000000
8: 00011011
9: 00110110
10: 01101100
11: 11011000
12: 10101011
13: 01001101
14: 10011010

This is not what you'll actually use, but it's necessary to have a complete discussion.  In the above list, for AES-128, you'd start at round 0, and the final round, 9 (the 10th round), you will have 0x36.
For AES-192 and AES-256, you end up skipping constants due to the key schedule.  For AES-192:
0: 00000001
1: 00000001
2: 00000001
3: 00000010
4: 00000100
5: 00000100
6: 00001000
7: 00010000
8: 00010000
9: 00100000
10: 01000000
11: 01000000
12: 10000000

For AES-256:
0: 00000001
1: 00000001
2: 00000001
3: 00000001
4: 00000010
5: 00000010
6: 00000100
7: 00000100
8: 00001000
9: 00001000
10: 00010000
11: 00010000
12: 00100000
13: 00100000
14: 01000000

You can implement this in many ways. The naive approach that you'd have in class, but is easy to follow (also, FPGAs would do this generally):

The way that I generally do it (note, this is encryption, you move tap 4 for decryption):

The clock control increments the value.