What is the best way to sign a message using RSA? I was preparing for competitive exam, and I came across this question. I had a lot of discussion with my friends before I resorted to posting it here and I wanted myself to be clear on this.

Let $M$ be a confidential email that Alice wants to send to Bob,  $K_B$ be Bob’s encryption public key, and  $K_A^{-1}$ be Alice’s private key for signing. Which of the following options would be the best choice for protecting confidential emails?

(A) Send $E_{K_{B}}(M),Sign_{K_A^{-1}}(K_B)$

(B) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(M)$

(C) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(E_{K_B}(M))$

(D) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(K_{A}^{+1}(M))$

I marked (B), but correct answer is given to be (C).

I understand the first part, that we are encrypting the message with Bob’s public key, but my understanding says, that we sign the message using Alice’s private key and send it to Bob along with the encrypted message.

But seems like option (C) says that along encrypted message, Alice should sign the encrypted message and then should send this signature along with the encrypted message to Bob.

My query is as per option (C), Why are we signing the whole encrypted message instead of the original message as shown in (B).

Option A signs the public key rather than the message. As the goal is to authenticate the message, the signature over the public key is useless for this purpose.

Option B signs the message. It however has the disadvantage that it is possible for an adversary to guess the message and verify the correctness of the guess. As such, it doesn't provide full confidentiality. It may also be vulnerable against oracle attacks unless a IND_CCA2 secure cipher is used; it could be that the receiver leaks information when trying to decrypt unauthenticated ciphertext.

Option C signs the encrypted ciphertext. It doesn't provide any authenticity of the message for email encryption because somebody can simply strip off and replace the signature. It would only provide authenticity if Bob only expects signatures of Alice, and disregards any other public keys that can be used to verify the message. This is however commonly not the case for person-to-person mail encryption.

Option D is clearly some mumbo jumbo to have a fourth option. As the operation $K_{A}^{+1}(M)$ doesn't make any kind of sense even with regards to the notation, it is probably best to ignore it.

Option B is an encrypt-and-sign scheme, option C is an encrypt-then-sign scheme.

Generally we use a (missing) sign-then-encrypt scheme where we send $E_{K_B}(M, \text{Sign}_{K_{A}^{-1}}(M))$. Obviously sign-then-encrypt should be used with care as well; it does require a IND_CCA2 secure cipher just like option B. Note that I've left out some kind of encoding function to merge the message with the signature.

Now that you know the terms you can look up Q/A and discussions such as the one here. Note that we often need to include additional information in the scheme for it to be secure in a practical sense; protocol design is however a separate topic.

EDIT: Come to think of it, it is also possible to replace the signature for option B, so that would make option C marginally better.


Security of permutation cipher I would like to understand how secure the permutation cipher is.

I would specifically like to understand the following concrete setup: If the alphabet is $L = \{0,1,\dots , 255\}$ and $\sigma_1, \sigma_2, \dots, \sigma_n $ are permutations on $L$, then we can create a cipher by encrypting the first character in the plaintext by $\sigma_1(\sigma_2(\dots \sigma_n(a_1)))$. Then we can (like with the Enigma machine) rotate $\sigma_1$. That is if for example
$$
\sigma_1 = \pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 55 & 140 & 7 & \dots & 34 & 82}
$$
we rotate so that $\sigma_1$ become
$$
\pmatrix{0 & 1 & 2 & \dots & 254 & 255 \\ 140 & 7 & &\dots & 82 & 55}
$$
When we have rotated $\sigma_1$ 255 times we rotate $\sigma_2$.

This means that the key basically consists of the permutations $\sigma_1, \dots, \sigma_n$.

My general questions is: How secure is this cipher? I understand that the security will depend on $n$, so if the question is too hard to answer, I would be OK with assuming that $n$ is "large enough". I also understand that this will depend on whether or not one reuses the same key several times, so

Another question is: How does the security depend on whether or not one reuses a key?

(By large enough one could just choose $n$ so that $255^n$ is greater than the size of the cipher text.)

(${\tiny\text{ I am not trying to roll my own crypto. I promise never to use this for anything serious besides trying to learn}}$)

How secure is this cipher?

At first glance, not very.  It would appear to be vulnerable to a ciphertext-only attack, for example, the attacker can recover the plaintext given a ciphertext of about 10k (actually, he probably can deal with less), even assuming that all the attacker initially knows is that the plaintext is "ASCII English", and he has no initial knowledge of the $(\sigma_1, \sigma_2, ..., \sigma_n)$ permutations.

Since you're learning, I won't spell out the details.  Here is how I started with:

"ASCII English" is approximately 20% spaces; that is, 20% of the plaintext is the exact same byte value.
Within a single generation (where "generation" means "within 255 consecutive times we shift only $\sigma_1$), $\sigma_2(\sigma_3(...\sigma_n(P))...)$ will be a fixed permutation; hence the result of that will be the same value 20% of the time.

How can we use that to attempt to reconstruct $\sigma_1$ (up to a circular shift)?  How can we correlate data from different generations (hint: it's easier if we just assume that the $\sigma_2(\sigma_3(...\sigma_n(P))...)$ permutations from different generations are independent)?  Once we've reconstructed $\sigma_1$, how can we immediately recover the plaintext?


"Batched affine" short-Weierstrass elliptic-curve additions In https://safecurves.cr.yp.to/rho.html Bernstein talks about fastest possible rho method that uses "batched affine" additions and requires only 5 multiplications mod p, 1 squaring mod p and some small "extra" work that is negligible. Affine means conventional (X,Y) coordinates, no projective coordinates. How is it possible to do group operations on elliptic curve with so little computation and without doing inverse? What exactly he means by "batched affine"?

The affine addition formula for short Weierstrass curves is usually given by
$$
\begin{align}
\lambda &= \frac{y_2 - y_1}{x_2 - x_1} \\
x_3 &= \lambda^2 - x_1 - x_2 \\
y_3 &= \lambda(x_1 - x_3) - y_1 \\
\end{align}.
$$
This gives us 1 inversion, 2 multiplications, 1 squaring, and a few field additions.
The trick here, when adding many points in parallel, is to use the so-called Montgomery trick (thus called because it was popularized in Montgomery's 1987 paper), which trades $n$ inversions by $3n$ multiplications and a single field inversion.
Here follows a simple description of the algorithm from Modern Computer Arithmetic:

So in reality you are still performing an inverse, but it is amortized among many simultaneous additions; for large enough numbers its cost becomes negligible.


Using XMSS with Blake2 Since XMSS only requires a 2nd preimage resistant hash function, is using Blake2 in XMSS possible? It is not in standard, but Blake2 seems to be faster than SHA256

It's definitely possible, but the standard needs some amendment to make it formal.
It's interesting to know that, KangarooTwelve is even faster, but nonetheless, not yet formallized.
Also that NIST intends approve SHAKE XOFs as MGF in RSA in FIPS 186-5, but not yet included in PKCS#1


Does having a known plaintext prefix weaken AES256? I plan on storing data, encrypted with AES256, where the first dozen bytes are known plaintext.  ('Hello World!' for example.)

Does having this known plaintext prefix weaken AES256?

I do not care about modifications being made to the ciphertext, which result in modifications to the decrypted plaintext.

I do care about an attacker being able to decrypt any plaintext beyond the known plaintext prefix.

I expect to use counter mode, as random access is required.  Does GCM have any advantage?

AES-256 has sustained 15 years of cryptanalysis, and it can be stated that no knowledge of some plaintext bytes would help to reveal the other bytes no matter what mode of operation (CBC, CTR, etc.) is used.

AES-GCM is an authenticated encryption scheme that allows a key holder to detect any modification that has been done to the ciphertext. If you do not care about such modifications (which are easy in the Counter mode), then you do not have to use GCM. However, if you can use it, I would definitely recommend doing so.


Considerations on using a single long-term key for file encryption I'm thinking about designing my own container file format that allows me to store a file in it along with, say, a thumbnail or other metadata. Some of these files are confidential and therefore must be encrypted. Basically, my goal is to achieve confidentiality, authenticity, and integrity for my file containers. But, with possibly millions of containers and only a single long-term secret (i.e. master key file), how can I do that properly?

I suppose what I'm looking for is AEAD (AD = the file header) for which I can, e.g., use AES-256-CBC + HMAC-SHA256 or AES-256-GCM.

The issue I'm held up with is the IV/nonce. Since there is only a single long-term secret in my design, I understand that I must ensure the uniqueness of the IV/nonce for each container with either one of the methods mentioned above.

Is it sufficient to use a simple sequence number for each container and place it in the (authenticated) file header?
Should I split the IV/nonce in a fixed and a sequential part (mentioned in RFC5116)?
Different approach?

I was also thinking about using an HKDF to derive key material for each container from the master secret and a GUID associated with each file container. I would then store the GUID in the plain file header. But then again I could simply use the GUID as IV/nonce. Is there a benefit in creating individual key material for each container?

Update

Individual keys for each container seem like the way to go. However, simply using a master secret to encrypt the container key does not solve the IV problem. Please take a look at the following proposal:

File header

$H: Plaintext\ file\ header$
$G: GUID\ associated\ with\ the\ payload\ (included\ in\ H)$

Payload

$P: Plaintext$
$C: Ciphertext$
$IV_p: Payload\ IV$
$K_p: Payload\ key$

$C = AES(IV_p, K_p, P)$

User keys and MACs

$S_i: A\ secret\ stored\ in\ a\ file$
$IV_i: IV\ for\ slot\ i$
$K_i: Key\ for\ slot\ i$
$K_{M_i}: HMAC\ secret\ for\ slot\ i$
$M_i: HMAC\ for\ slot\ i$
$K_{P_i}: Payload\ key\ material\ encrypted\ with\ K_i$

$(IV_i, K_i, K_{M_i}) = HKDF(G, S_i)$
$K_{P_i} = AES(IV_i, K_i, IV_p\ ||\ K_p)$
$M_i = HMAC(K_{M_i}, H\ ||\ C\ ||\ K_{P_i})$

Container file format

$H\ ||\ C\ ||\ (K_{P_i}, M_i)$

With this design, I

use a HKDF to derive as much key material from the keyfile as I need (solving the IV problem)
can later on add or remove as many user keys as I want
can detect tampering via the HMAC associated with each user key
do not need to store a hash of the container key (like LUKS does) because the HMAC guarantees the integrity of the decrypted key

Would you consider this a sound design?

Is it sufficient to use a simple sequence number for each container and place it in the (authenticated) file header?

Yes, but making sure it is unique may be trickier than you think. Storing a counter is both error prone and it may hamper performance as well. What if you lose the .lock file (or similar) containing the number?

  Should I split the IV/nonce in a fixed and a sequential part (mentioned in RFC5116)?

If you want to, as long is it stays unique. This part of the standard seems particularly important if you've got multiple devices that each have their unique fixed ID. In that case the fixed ID can prevent the devices with coming up with the same nonce.

Personally I don't think you should use the same key in the first place. I don't consider RFC 5116 a strong standard and I would certainly not use it to draw cryptographic ideas from. Especially the part where the authentication tag is part of the ciphertext feels completely backwards to me (as it removes the online properties of AES-CTR that is used for most authenticated modes of encryption).

  Different approach?

Usually a symmetric key is generated for each file, which can then be wrapped by the master key. The advantage is that you can decrypt the data key and add other keys that may retrieve the data key. You may also be able to roll over to a new key that way. In other words, it simplifies key management. That kind of key management is harder to accomplish when using a KDF.

  But then again I could simply use the GUID as IV/nonce. Is there a benefit in creating individual key material for each container?

Yes, you'd be less vulnerable against catastrophic failure if the nonce ever repeats.

Be warned that you may want to protect against files being swapped as well.


Is brainpoolP512r1 safe? I'm using brainpoolP512r1 elliptic curve for DSA and DH in my application. Recently I've found out on this website that brainpoolP256t1 and brainpoolP384t1 aren't secure. Unfortunately my curve wasn't mentioned.

When I'm using brainpool, my public keys encoded in base64 have around 210 chars, but for curve25519, they expand into 410 chars which causes a few problems. How can I verify if brainpoolP512r1 is safe?

Recently I've found out on this website that brainpoolP256t1 and brainpoolP384t1 aren't secure.

Actually, that website doesn't say that, it says they aren't safe, where their definition of "safe" means it meets all of a series of requirements.

If you go through the table they give, brainpoolP384t1 fails the safe requirements at three points:

ladder; there is a fairly simple algorithm for doing point multiplication for certain curves; this algorithm is moderately fast, and also tends to be resistant to timing and cache-based side channel attacks (but not DPA-style attacks); that algorithm as listed doesn't work for brainpoolP384t1 (actually, it does, it's just a bit more complicated).  One can certainly make the case for simplicity; however just because a curve doesn't implement it as easily as others doesn't necessarily mean that the curve can't be implemented securely.
complete; does the curve allow the implementation of a point addition algorithm that works without branches in all cases (point doubling, adding the neutral element); brainpoolP384t1 does not (at least, not without complicating the algorithm).  However, some point multiplication algorithms don't require unified addition/doubling algorithms and avoid the neutral element; again, simplicity is a good goal, however just because a curve doesn't allow this specific simplification doesn't mean that it's not secure.
indistinguishability; is the representation of a point distinguishable from random; for brainpoolP384t1, it is.  On the other hand, unless you're implementing a PAKE, that's usually not important (and even with PAKE, there are ways around it), and a curve can not implement this, and still be considered secure.

I believe that brainpoolP512r1 has the same properties, and so this page needn't be considered evidence that it isn't secure.

As for whether it is secure, well, the best I can say is "there's no known cryptanalytic result suggesting that it is not" (which is ultimately the best we can say about most cryptographic algorithms).

  When I'm using brainpool, my public keys encoded in base64 have around 210 chars, but for curve25519, they expand into 410 chars which causes a few problems.

Now, that sounds odd; a curve25519 ECDH and EdDSA (you can't use standard ECDSA with curve25519, at least, not with the ladder algorithm) have public keys of 43 bytes (Base64 encoded); it sounds like you're doing something wrong here.


Verifying authentication by just using the root of a Merkle tree Let's say I've a Merkle tree where leaves are the hashes of some data that needs to be authenticated. Can I verify the whole of them by just using the hash of the root of Merkle tree? If yes, how?

If you need to verify all the data, you are going to have to recompute the entire tree, and compare your root with the root you were given. The power of the Merkle tree comes into effect when you only need to verify a subset of the data.


Diffie-Hellman: Calculating the private key from the public key with Java I have the task to calculate the private key from the given public key and have the hint that the secret exponent lies in the range from $-2^{31} < e < 2^{31}$.

To find the exponent I calculate a public key and compare it to the given key.
$$k_{pub} = 2^{e} \bmod {prime}$$ I start with $e = -2^{31}$ and then iterate my way up until I should find the $e$ where my calculated key equals the given public key. The problem is that it takes really long (about 20 days, if I calculated correctly).
Is there a way to make it faster?

import java.math.BigInteger;

public class task {

        public static void main (String[] args) throws java.lang.Exception
        {

            BigInteger prime                = new BigInteger("FFF....FFF", 16);
            BigInteger BobPublicKey         = new BigInteger("b54.....da6", 16);

             BigInteger tmp = new BigInteger("0");

             BigInteger j = new BigInteger(new Integer(Integer.MIN_VALUE).toString());
             System.out.print("Starting to guess Bobs secret: \n" + j + "\n");

             while ( !(tmp.compareTo(BobPublicKey) == 0)){
                 tmp = BigInteger.valueOf(2).modPow(j, prime);
                 j = j.add(BigInteger.valueOf(1));
                 System.out.print(j + "\n");
             }

             //correct for counting 1 too far in while loop after the actual e was found
             j = j.add(BigInteger.valueOf(-1));

             System.out.print("Bobs secret was: " + j + "\n");

        }
 }

There are several obvious ways to optimize the search.

The easiest approach would be to take advantage of the identity $g^e \cdot g = g^{e+1}$.  That is, if we have already computed $g^e$, and verified that it is not the value we're looking for, then to step to $g^{e+1}$, we don't compute $g^{e+1}$ from scratch; instead, we take the $g^e$ value we have, and multiply it by $g$ (modulo $p$), and that's the next value to check.

And, because you have $g=2$, this can be done as easily as adding $g^e$ to itself, and then subtracting $p$ if needed.

A more difficult (but ultimately more rewarding) optimization is to implement the 'bigstep/littlestep' algorithm.  This takes the equation $g^x = g^{ak+b}$ (for $k = 2^{16}$ and $-2^{-15} \le a < 2^{15}$, $0 \le b < 2^{16}$), and rewrites it as $g^x g^{-ak} = g^b$; we then create a list of the $2^{16}$ possible $g^x g^{-ak}$ values, and the $2^{16}$ possible $g^b$ values, and search for a match (which can be done in $O(n \log n)$ time using a fast sorting algorithm); this match gives us the $a, b$ values, which immediately gives us $x$.  This is obviously a lot more work; however doing this will allow you to find a match by doing around $2^{17}$ modular multiplications; this is a large gain over the previous optimization.


Construction of division polynomials I'm trying to understand the construction of the division polynomials used in Schoof's algorithm. I firstly followed this report of Charlap and Robbins.

I stuck with the definition of the leading term p11.

I'm also reading this book, which does the construction also in characteristic 2. However I have the same problem here.

I'm not able to use the definition in order to computer the leading coefficient of a rational function. However the construction of division polynomials needs me to compute the leading coefficients of the rational function which multiplies a point by m.

Can anybody give me an explicit example of how to compute the leading coefficient?

Leading coefficient of a rational function was defined at 5.3
on page 11 of Report 31
as another function (multiplied by (x/y)^d for some d)
evaluated at identity.

Handling the case of point at identity was explained at top of page 8,
namely multiplying numerator and denominator by y^d and x^d
to make them of the same degree,
resulting in another rational function that is finite and not zero at identity.

Degree of a polynomial of canonical form was defined at 3.6 on page 5;
reduction to this form was explained after definition 3.1 on page 3.

Evaluating a rational function at identity is explained at definition 3.9 page on 5
as the ratio of leading terms of numerator and denominator.

I would expect reduction to canonical form to be a likely reason of confusion.

UPD: For explicit example, let's take a look at Proposition 7.6, leading coefficient of $g_n(x)$ evaluated at identity, with $(g(P), h(P))$ defined at the start of Section 7 "Multiplication by $n$" and $g(P)$ depending only on $x$-coordinate of the point (Exercise 7.5). It was proved by induction on page 23. Corollary 7.7 is likely of major interest for such a question.


Windows 8/Server 2012: Passes FIPS-140-2 despite failing AES-GCM for IV != 96 bits long? Background

Microsoft certifies Windows 7/8 as well as Server 2008 R2 and 2012 to be FIPS-140-2 compliant. Actually they certify just a small crypto core, bcrypt.dll (the library, which is unrelated to bcrypt, the key derivation function). Microsoft's FIPS-140-2 architecture is detailed here. Also, their FIPS-140-2 AES certificate on NIST's listing is certificate #2216, in detail here. You can see in the listing that AES in GCM mode was tested with comments IV Lengths Tested: ( 8 , 1024 ) , 96BitIV_Supported , GMAC_Supported. I do see other vendors also having an additional flag/comment OtherIVLen_Supported in their FIPS AES certificate that MSFT's own FIPS certificate lacks.

Issue

We tested bcrypt.dll for AES in GCM mode with the test vectors found in the AES GCM paper (hosted on NIST). We found that Windows' bcrypt.dll throws an error (NT_STATUS = An invalid parameter was passed to a service or function.) when using IVs that are NOT 96 bits. So basically the test vectors 5, 11, 17 and 6, 12, 18 fail as those two groups use IVs of size 64 bits and 480 bits respectively. The results are

Question

I know that IV size != 96bits means additional processing but how can they clear certification despite failing IV sizes of 64 and 480 bits? Or is IV at 96 bits the only required IV length needed for passing?

The answer is, yes, you can get FIPS certification even if you don't implement every approved cryptographical primitive, or if you don't implement every possible option of those primitives.

When you undergo FIPS testing, they ask you to fill out an "information form" that asks for the details of what cryptography you claim to implement.  These includes questions about which primitives you implement (e.g. whether you do GCM or not).  If you do claim to support GCM, you then have to claim what portions of GCM you implement.  For example, you can claim to support GCM encryption but not decryption, or support 128 bit and 256 bit keys, but not 192 bits (for example).  As for the IV, you can claim support for 96 bits, or you can claim support for a range of IV sizes (anywhere between 0 and 1024 bits, multiples of 8 please).

Hence, when Microsoft applied for FIPS validation of their component, they claimed support for only 96 bit IVs.

However, that's not immediately obvious from the summary that NIST lists in the certificate listing (which is copied directly from the Information Form, and lists exactly what restrictions the certified implementation has).  For this implementation, they list under GCM:

  IV Lengths Tested: ( 8 , 1024 )

which would, to a naive reader, appear to state that Microsoft claimed support for IV's of length in the range 8 to 1024, and that NIST tested them, however, that's not the case.  NIST has a separate flag 'OtherIVLen_Supported'; unless that is claimed, you really get support only for 96 bits.  That flag is not mentioned under the Microsoft entry, hence Microsoft doesn't claim to support those IV lengths.

Exactly how NIST expects you to know this (if you're not familiar with the internals of the NIST information form), I have no idea.  The OtherIVLen_Supported flag is not even mentioned in the 'Legend for Description Field' header.


Calculation of failure probability in basic Ring-LWE-DH key agreement This is the basic unauthenticated Ring-LWE-based Diffie-Hellman key exchange, based on Peikert's Ring-LWE KEM: (from BCNS15)

Alice and Bob have shared public polynomial $a$ randomly drawn from $R_q = \mathbb{Z}_q[x]/(x^n+1)$, and a known error distribution $\chi$ with standard deviation $\sigma$
Alice generates random small secret polynomials $s_A, e_A \in R_q$ according to distribution $\chi$, calculates $b_A = a \cdot s_A + e_A$ and sends it to Bob
Bob generates random small secret polynomials $s_B, e_B \in R_q$ according to distribution $\chi$, calculates $b_B = a \cdot s_B + e_B$ and sends it to Alice
Alice calculates $k_A = s_A \cdot b_B = a \cdot s_A \cdot s_B + s_A \cdot e_B$
Bob calculates $k_B = s_B \cdot b_A = a \cdot s_A \cdot s_B + s_B \cdot e_A$

$k_A$ and $k_B$ are approximately equal except for the error terms. So, Alice and Bob use a reconciliation function rec(.) such that rec($k_A$) = rec($k_B$) = $K$ is the common shared secret.

The basic reconciliation scheme (from BCNS15) rounds each coefficient of the polynomial to 0 or $q/2$, and $q/2$ is treated as 1, so that $K$ is an $n$-bit string. BCNS15 says that this scheme has a failure probability of $1/2^{10}$. How is this calculated?

Here is the general approach I have been trying:

For successful key exchange, we must have $|k_A[i] - k_B[i]| < \delta$ for $i \in \{0, 1, \cdots, n-1\}$, where $k_A[i]$ and $k_B[i]$ denote the $i$-th coefficient of polynomials $k_A$ and $k_B$ respectively and $\delta$ is the error tolerance of the reconciliation scheme
In this case, $k_A - k_B = s_A \cdot e_B - s_B \cdot e_A$ and $\delta = q/4$
Let $p$ be the probability that $|k_A[i] - k_B[i]| > \delta$ for some $i$, that is, the probability of error in decoding any one bit of $K$. Then, the total failure probability is $1 - (1 - p)^n \approx np$ for small $p$
Let the error distribution $\chi$ have a support $[-t\sigma, +t\sigma]$, where $t$ is a factor determined by the precision of the sampler implementation. Then, the maximum possible absolute value of any coefficient of $s_A \cdot e_B$ or $s_B \cdot e_A$ is $nt^2\sigma^2$, so we must have $2nt^2\sigma^2 < q/4$ or $q > 8nt^2\sigma^2$

One concrete solution is to explicitly compute the distribution of each coefficients. In this particular ring, and if the distribution of the coefficients of e and s are symmetric, this ca just be computed as an 2n-fold convolution of the distribution of products of coefficients. An example (with some complication due to rounding) is available here:

https://github.com/pq-crystals/security-estimates/blob/master/Kyber_failure.py

More mathematical approaches (which may give somewhat looser bound) involve studying moment-generating function. This can be nicely abstracted away using the theory of sub-gaussian random variables.


What does (06) in "CRL Signing (06)" mean? In "Certificate details -> key usage -> CRL Signing (06)", what does "(06)" in "CRL Signing (06)" mean?

The Key Usage field is represented as a bit string, where each bit represents one of the options, so that multiple options can be set. The value 6 it's just the constant of the bit position that identifies "CRL Signing". From RFC 5280:

KeyUsage ::= BIT STRING {
     digitalSignature        (0),
     nonRepudiation          (1),  -- recent editions of X.509 have
                                -- renamed this bit to contentCommitment
     keyEncipherment         (2),
     dataEncipherment        (3),
     keyAgreement            (4),
     keyCertSign             (5),
     cRLSign                 (6),
     encipherOnly            (7),
     decipherOnly            (8) }


Is it safe to prefix the a key with a known value? Almost every encryption algorithm is based on a secret key. I wonder when the algorithm is considered safe, does that also imply that I can prefix (or suffix) the key with a known value, as long as the unique part is of sufficient size? Just disregarding the fact wether would be wise in the first place.

Generally, the actual key for most cryptographic algorithms is a fixed length bitstring (or something more complicated, like a tuple of appropriately chosen large numbers).  Thus, if you just take a valid key and add a prefix to it, it will no longer be a valid key at all.

(There are a few notable exceptions, such as HMAC, which can use any octet string as a key.  But those are definitely the exceptions to the norm.)

So what if your un-prefixed key was shorter than the algorithm needs (but still long enough to resist brute force guessing), and you choose the prefix so that it pads the key to the needed length?  Well, clearly you could do that, but depending on the specific algorithm you're using, it might not be a good idea, for several reasons:

Even if the algorithm is specified to just take a bitstring of a certain length as its key, that doesn't necessarily mean that every part of the key contributes equally to the security of the algorithm.  For example, some authenticated encryption schemes (such as, notably, SIV) take a key which is split into two halves, one of which is used to authenticate the message, and the other to encrypt it.

Thus, for instance, SIV-AES-128 takes a 256-bit key; if you were to construct one by padding a 128-bit key with a known 128-bit suffix, your messages would be perfectly well authenticated, but totally trivial to decrypt.  (Using a known prefix would compromise the authentication part instead, but due to details of the SIV design, that seems a bit trickier to exploit.  At least it would make it trivial for an attacker to verify if they guessed the plaintext of a message correctly.)
Even if all the key bits are supposed to contribute equally to the security of the algorithm, that's not guaranteed to hold in practice.  Many otherwise secure and well-regarded ciphers can be vulnerable to related-key attacks (including AES, although the published attacks against it are, so far, mostly of academic relevance).  Such attacks are outside the scope of many commonly used security definitions, and thus may receive less cryptanalytic attention than usual.

Instead, the proper way to expand a too short (or otherwise unsuitably formatted) secret value into a proper-sized key is to run it through a key-derivation function.  There are plenty such functions to choose from, but (for applications that do not require key stretching) I personally rather like HKDF (RFC 5896) for its flexibility.


SHA-256 hash of null input? What is the SHA-256 hash if the input is null, i.e. an empty bitstring? (Not the hash of 0 or "0".)

The result of SHA-256 of an empty string is:

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Accordingly to this and this


CCA on PKCS#5 using error feedback My question is about attacking PKCS#5 with CCA using the error feedback.
What we learnt in class about PKCS#5:

CBC requires padding to whole block boundary PKCS#5: standard padding

If last plaintext block has 1 byte: pad with $\texttt{07}$ bytes
If last plaintext block has 2 bytes: pad with $\texttt{06}$ bytes
If last plaintext block has 7 bytes: pad with $\texttt{01}$ byte
If last plaintext block has 8 bytes: pad with another block (8 bytes)    of $\texttt{08}$.

And:

Decryption process: Apply 'regular' CBC-mode decryption Check padding:

If padding Ok, remove and return plaintext
If incorrect, abort with error

Up until now I understand everything. But the last part, describing a CCA attack on PKCS#5 with feedback, is what I can not understand:

Let $(c_1,...,c_8)=F_k(p_1,...,p_8)$ be some ciphertexts.
To find last byte $p_8$: Check which prev block gives Ok decryption
Let $x_8$ be the last byte of a block $X$ giving Ok padding
With high probability, $x_8 \oplus p_8 = \texttt{01}$...

And that's it.
First, I don't get where the IND-test is involved here.
In the test, attacker sends two messages $m_1$,$m_2$ and receives $c'$ which is an encryption of one of them, and has to distinguish which one exactly using the chosen-ciphertext capability, but here we just use the error result, as if the test is ignored.
Now, let's see if I understand that correctly:
$c_1$,...,$c_8$ are the bytes of some ciphertext block we wish to decrypt.
It says that in order to find out $p_8$ we find last block which gives ok on padding - let's assume we found one... this block looks like this: $c'=(c'_1,...,c'_8)$, and I know that the plaintext of $c'$ ends with $\texttt{01}$, or $\texttt{02},\texttt{02}$, etc.. until $\texttt{08},...\texttt{08}$ (8 times).
And now we denote the last byte (decrypted as plaintext) as $x_8$.
Why would $x_8 \oplus p_8$ be $\texttt{01}$ with high probability?
It would be great if someone could enlighten me up, I'm also open for other explanations instead the one I described here.
P.S. Read that question, seems related but I still can't understand how to deduce an answer about my question.
Can you explain Bleichenbacher's CCA attack on PKCS#1 v1.5?

Ok, suppose that we have a ciphertext $(c_1, c_2, ..., c_8)$ that we wish to decrypt.

What we start off with is to make a guess for $p_8$, which is the decryption of the last byte of the block.  Suppose that we guess that it is 0x07; we then need to validate that guess.

What we do is create a two block message; the second block is the challenge ciphertext block $(c_1, c_2, ..., c_8)$; the first block has 7 random bytes; followed by $0x07 \oplus 0x01 = 0x06$.  We then send it to the Oracle for decryption.

Let us recall when CBC mode decryption is; it is $P_i = C_{i-1} \oplus D_k( C_i )$.  In the specific case of the last block, what the decryption process will do is first internally decrypt the last ciphertext block $(c_1, c_2, ..., c_8)$, and get the plaintext block $(p_1, p_2, ..., p_8)$; it'll then exclusive or that with the previous ciphertext block; the last byte of that result will be $p_8 \oplus 0x06$ (because we made the last byte of the next-to-last-block 0x06).

Now, if our guess was correct; that is $p_8 = 0x07$, the result of this exclusive-or is $0x07 \oplus 0x06 = 0x01$; a last block with the last byte of 0x01 is valid padding, and so the message will be accepted.

On the other hand, if our guess was not correct, then the result of this exclusive-or is something other than 0x01.  Now, it's possible that the result will also look like a valid padding (for example, the last three bytes might be 0x03 0x03 0x03), however that would also involve other bytes (which we set randomly), and so that's unlikely.

So, to actually perform this attack, we would make guesses at $p_8$, and send out ciphertexts to test those guesses.  And, once we have determined the likely value of $p_8$, we can start guessing $p_7$ (which works just the same way, except we're targetting the $0x02$ $0x02$ final pattern).

BTW: the Bliechenbacker CCA attack is actually unrelated.


Same 64-bit preimage resistance security for SipHash and SHA-512/64? If I have to chose a 64 bit preimage resistant hash function; will there be any difference in security between

SipHash and
SHA-512/64 (SHA-512 truncated to 64 bits)?

How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?

SipHash doesn't claim to be a secure hash function. Only a secure MAC. So if you try to use it as a hash function, with a constant, public key, you are on your own.

SHA-512/64 should be a "secure" 64-bit hash, which is of course not enough for a truly secure hash, since it only has 32-bit collision resistance. However, since you only desire preimage resistance, it may have its uses.

  How long will it take an attacker to find a 64 bit preimage (e.g., minutes, weeks or years)?

That depends on the attacker's computational power, of course. With a typical desktop CPU you can calculate around $2^{20}$ to $2^{25}$ SHA-512 hashes per second. So a brute force preimage search would take maybe $2^{40}$ seconds, or tens of thousands of years. GPUs could reduce that by a large factor, but it would still likely be centuries.

However, the whole bitcoin userbase is currently (as of early 2016) hashing over $2^{60}$ hashes per second, and even taking into account a small additional factor from SHA-512 vs. SHA-256, you'd be inverting the hash in less than a minute at that rate.

If you want something that takes longer to invert, you should use a password-hashing function, like scrypt with sufficiently large parameters.


How can I determine if a hash function is secure? I'm doing an exam in computer security and I encountered this problem which I'm unsure of how to attack properly. Should I get down and dirty with the Hash function on paper or is there a more general approach to making these kinds of security judgments?

The question is as follows:

Let $M = B_1, ...,B_n$ be a message consisting of $n$ blocks of 512-bits. Let $H$ be the function $H(M)=(((B_1+B_2) \oplus B_3)+B_4 \oplus B_5)...B_n$, where $+$ is the addition modulo $2^{512}$ and $\oplus$ is bitwise XOR. Is $H$ a secure Hash Function?

For each requirement:

preimage resistance (or one-wayness)
second preimage resistance (or weak collision resistance)
collision resistance (or strong collision resistance)

motivate if it holds or disprove it.

Let $D$ be the set of all possible messages with $n \leq 4$ (ie. all messages smaller than 2 Megabits). Does $H$ produce more collisions than SHA-256 for messages in $D$?

The best way to approach problems like this is to start by assuming that a simple solution exists.  That assumption might be wrong, of course, but:

since this is a textbook problem, it probably does have a relatively simple solution that you should be able to figure out based on what you've learned, and
even if that wasn't the case, you should still at least try to look for simple solutions before spending time on anything more complicated.

Thus, you should assume that, on one hand, if your hash function doesn't satisfy one of the three security properties the question asks about, then there should be a fairly simple example where that property is violated.  On the other hand, if it does satisfy them, then there should be some fairly straightforward way to prove that conclusively, or at least to reduce it to some widely held assumption (e.g. "if someone can break this hash, then they can also break SHA-256").

With that in mind, let's take a closer look at your hash function.  It's specified as taking a sequence of $n$ input blocks, which are combined according to a particular expression involving addition (modulo $2^{512}$) and bitwise XOR:

$$H(B_1, \dots, B_n) = ((((B_1 + B_2) \oplus B_3) + B_4) \oplus B_5) + \dots$$

How do we simplify that?  Well, the fewer blocks there are, the simpler the expression gets.  So let's start by considering the simplest possible case, i.e. $n=1$.  With just a single block of input, your hash function looks like this:

$$H(B_1) = B_1$$

Now, consider the three security properties you've been asked about, and see if you can come up with single-block counterexamples:

preimage resistance: if given a value $X$, can you find a single-block message $M = B_1$ such that $H(M) = X$?
second preimage resistance: if given a single-block message $M = B_1$, can you find another single-block message $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?
collision resistance: can you find any two single-block messages $M = B_1$ and $M' = B_1' \ne B_1$ such that $H(M) = H(M')$?

Hopefully, you should be able to answer "yes" to at least one of the three questions above.  (I won't spoil which one.)  In fact, with a little bit more thought, you should be able to figure out that, for single-block messages, the answer to the other two questions is definitely "no".

However, we're not done yet.  What if we consider messages consisting of two blocks?  Then the hash function will look like this:

$$H(B_1, B_2) = B_1 + B_2$$

where $+$, of course, denotes addition modulo $2^{512}$.  With that in mind, let's consider the three questions again.  (Of course, you don't need to reconsider the one for which you already found a single-block counterexample above.)

preimage resistance: if given a 512-bit value $X$, can you find a two-block message $M = (B_1, B_2)$ such that $H(M) = X$?
second preimage resistance: if given a two-block message $M = (B_1, B_2)$, can you find another two-block message $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?
collision resistance: can you find any pair of two-block messages $M = (B_1, B_2)$ and $M' = (B_1', B_2') \ne M$ such that $H(M) = H(M')$?

If, after considering the two-block case, your answer to some of those three questions was still "no", then it might be time to start considering whether the way you arrived at the "no" answer for the one- and two-block cases could be generalized to any number of blocks.  Or you could decide to spend some time considering the three block case, if you think that the answer might be "yes" in that case.

But in fact, in this case, that should not be necessary; just considering the one- and two-block cases should be enough to give a definitive answer to all three questions for this hash.

Ps. As for the extra question about the number of collisions at the end, first note that the question (or your transcription of it) clearly has some typos: four 512-bit blocks work out to 2048 bits or 2 kilobits, not 2 megabits!

In any case, we of course don't know exactly how many collisions SHA-256 has on that set of inputs, since the input space is too large to count them by brute force, and any method of determining the exact number significantly faster than by brute force would require breaking SHA-256, or at least come worryingly close to it.

However, you should be able to come up with a lower bound on the number of collisions SHA-256 or any other hash with a 256-bit output size can have for that input space, just using simple arithmetic.  (The generalized pigeonhole principle may be useful here.)  And your hash function $H$ is simple enough that you can count the exact number of collisions it will have on the input space $D$, and compare that with the lower bound.

In fact, just for a yes/no answer, you don't really even need to calculate the actual number of collisions.  All you really need to do is consider how close to the theoretical lower bound for a 512-bit hash your function $H$ gets, and then consider how making the hash output longer / shorter affects the lower bound.

(Also, yes, the result you'll get may seem counterintuitive.  What it really demonstrated is simply that the total number of collisions doesn't necessarily correlate with the difficulty of actually finding one.)


In Microsoft Password Monitor implementation using HME how do they perform ComputeMatch Function? https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/
In this they mention

The server then evaluates a matching function on the encrypted credential, obtaining a result (True or False) encrypted under the same client key. The matching function operation looks like this: computeMatch(Enc(k), D).

How exactly do they perform it? As far as I can understand client data would be encrypted by their own private key and database will be encrypted using server's private key. So since keys mismatch they wouldn't be able to perform HME computations right? What am I missing here?

Let the client have public and private keys $k_{pub}, k_{prv}$ of a secure FHE (Fully Homomorphic Encryption). Now clients want to check that their password $pwd$ is on the breach list or not.
As stated on the MS site, to prevent the user from querying dictionary attacks on the server, they use hash $H$ of the form Oblivious Pseudo-Random Function (OPRF). The client calculates $h(pwd)$ then uses their public key and encrypts as $ = E(k_{pub},h(pwd))$. Now the client sends the $(c,k_{pub})$ to the server.
Now, the server, for each breached password $p_i$ calculates $c_i = E(h(p_i), k_{pub})$. Using the FHE equality circuit $C$ they compare each breached password's hash and the user's to get the result. Note that this result is encrypted and only the client can decrypt it. Now instead of sending each value to the user, they execute OR operation on the result to get only one value $v$.
The value $v$ sent back to the user and the user decrypt the single bit $b \stackrel{?}{=} D(k_{prv},v)$. If the $b=0$ mean not in the breach list, if $b=1$ mean it is on the breach list.
###Client
c = FHE_encrypt(k_pub, h(pwd)
send c to the server

###server
### Encrypt each password on the list
for each p in breachedList

    c[i] = FHE_Encrypt(k_pub, p)

###Calcualte the equality of the ciphertext
for i in sizeof breachedList

    eq[i] = FHE_Equality_Circuit(k_pub, c[i], c)

v = E(k_prv, 0)

###Combine the results to reduce the bandwidth
###Not to reduce the dep a binary tree calculation must be preferred.
for i in sizeof breachedList

    v = FHE_OR_Circuit(k_pub, v, eq[i])

return v

###
Client
b = FHE_Decrypt(k_prv,v)
if b = 1
   print ( "Change your password immediaately, it is on the breach list")
else
   print ( "Your password is not on the breach list")


Trying to understand textbook exercise question regrading RSA I am preparing for the final exam in my Data Security class so I am trying to read and understand the textbook's exercise questions. Any hint would be great.

Question (Exercise 9.14 of textbook):

Observation:
Similar to $RSA$ decryption that $e.d = 1$, we to find some number $r$ such that $E*r = 1$ so that $(m^E)^r \ (mod \ N) = m$. But what should that $r$ be? Any hint would be great.

I will assume that Alice uses $D' = E^{-1}(\varphi(N) - 1)$ with $E^{-1}$ the inverse of $E$ modulo $\lambda(N)$.
The question uses a very specific definition of $D'$, which requires the assumption that $E$ divides $\varphi(N) - 1$. But since such an $E$ is necessarily coprime to $\varphi(N)$, it is a special case of the more general definition of $D'$ provided above.

So we must find some number $E'$ such that
$$E' E^{-1}(\varphi(N) - 1) \equiv 1 \pmod {\lambda(N)}$$
Now note that $E' = -E$ is a solution because $\varphi(N) \equiv 0 \pmod{\lambda(N)}$, so we have

$$m^{-ED'} \equiv 1 \pmod N$$.

So given $c = m^{E}$, compute $c^{-D'}$ to obtain $m$ again. Either you first take the inverse, or you just use $\lambda(N) - D'$ as the exponent.


how are variable key sizes produced? I am current learning the internal working of several Symmetric key Cryptographic algorithms, and came across DES and AES.

  DES takes in input a 64 bit key and AES-128 takes in input a 128 bit key

My question is, since the user provides these algorithms inputs of variable size (or bits), then how is it able to upscale/downscale it to lower bits in order to feed it to the algorithm. Does it uses KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?

By decreasing I mean, If the User Inputs a key = APPLE PIES, and gives it as an input to DES. Then how is DES able to convert this (80 bit) key into a 64 bit one?

Does it use KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?
...how is DES able to convert this (80 bit) key into a 64 bit one?

AES and DES do not perform this task. The specification states that AES uses two sequence of 128 bits as input.
"key" means "cryptographically strong bits".
Something like APPLE PIES is a password rather than a key.

how is it able to upscale/downscale it to lower bits in order to feed it to the algorithm. Does it uses KDF (key Derivation function)? If yes, then is the KDF capable of decreasing the size of bits too?

The key derivation process may involve multiple invocations and iterations to generate output larger then the output size of the hash function, and the application may truncate keys down to the correct size when necessary.
How to derive a key from a password
This question has already been asked: see this answer.
A KDF is used to turn a password into a suitable key, but this is a separate process that is not performed  by the AES/DES algorithms.


Is F' a pseudorandom function when F is composed with G, a pseudorandom generator? If $F$ is a pseudorandom function, is $F'$ also a pseudorandom function in the following:
$$
F'_k(x)=F_k(G(x)) \space \space \text,
$$
where $G$ is $a$ pseudorandom generator?

Also, does the other directions holds (i.e $F'_k(x)=G(F_k(x))$)?

Certainly yes.
Proof
A pseudorandom function must produce pseudorandom output for any given input. So, any seed value will provide a pseudorandom output. However, this might not work if the function has a limited input domain (list of possible inputs) causing incompatibility with the two functions. In your case, $F$ should be able to process the input provided by $G$, and vice-versa for the second case.
Proof of concept
Let $F$ be a hash function, say SHA-3, and $G$ be AES-CTR, Then:
Case 1, $F'_k(x)=F_k(G(x))$: AES-CTR would generate a pseudorandom sequence which would be hashed by SHA-3, and, needless to mention, cryptographic hash functions are supposed to produce strong pseudorandom output, regardless of what the input is.
Case 2, $F'_k(x)=G(F_k(x))$: The hash digest of $x$ produced by SHA-3 will be used as a seed for AES-CTR, and, once again, block ciphers are also meant to produce strong pseudorandom output regardless of the input.
Verdict
Both the implementations suggested in the Proof of Concept section explain how $F'$ acts as a pseudorandom function. It is important to know that the security and quality of pseudorandomness is highly dependent on the outer function, $F$ in case 1, and $G$ in case 2, as it's output is what determines the required. The underlying function will only work as an internal state generator, where the state could have been anything, not necessarily pseudorandom.
So, building a PRNG by chaining two different PRNGs (as you did in your post) will surely work out.


Meet-in-the-Middle attack on 3DES How can I apply the Meet-in-the-Middle attack to the 3DES algorithm, and why does the literature say that 3DES is more secure than DES?

The meet-in-the-middle attack on ciphers like $C=E^2_K(P)=E_{K1}(E_{K2}(P))$ works as follows.

Let's assume you're given a known-plaintext pair $(P_1,C_1)$ and a known-plaintext pair $(P_2,C_2)$
You now build a list (by brute-force) containing the pairs $(I,K1)$ for every possible value of $K1$ ($2^{56}$ for DES) with $I=E_{K1}(P_1)$.
Constructing this list takes you $2^n$ blocks of storage with $n$ being the keysize.
You now simply call the decryption function $D_{K2}(C)$ until you obtain a value of $I$ you already stored in your table. If you find this one, which takes you at most $2^n$ operations, you simply counter-check with your second pair, using the relation: $C_2=E_{K1}(E_{K2}(P_2))$. If this holds, you can be pretty sure to have found the correct key. As you have to perform $2^n$ operations to obtain the table and $2^n$ operations to find the correct key you need $2^n+2^n=2*2^n=2^{n+1}$ operations and $2^n$ storage.

Let's see, how can I use that on 3DES (3-key)?
For the meet-in-the-middle attack to work, it is not required for the $E_K()$ to be the same. So you simply define the second one to be $E_{K2}=D_{K2}(E_{K3}(P))$. Then, in the first paragraph you'll need $2^{56}$ operations to construct the table containing $2^{56}$ entries. Now you simply perform the third paragraph of the above attack and need another $2^n$ operations with $n$ being 112 in this case as it is a double-application of DES which can't be attacked by meet-in-the-middle by itself as it is part of such an attack. The attack thus requires $2^{56}+2^{112}\approx 2^{112}$ operations and $2^{56}$ storage.

Now, how's the relation with 3DES (2-key)?
3DES is defined as $C=E_{K1}(D_{K2}(E_{K1}(P)))$. You can't apply the above attack to 3DES, as you now have three encryption / decryption operations.
The best attack to 3DES is due to van Oorschot and Wiener and goes as follows.

Guess the first intermediate value, $a$.
Tabulate, for each possible value of $K1$, the second intermediate value, $b$, when the first intermediate value is $a$ using known plaintext $b=D_{K1}(C)$, for all $p$ given plaintext-ciphertext pairs.
Look up, for each possible $K2$, elements with a matching second intermediate value, b: $b=E_{K2}(a)$.
The probability of a match is $p/{2^m}$ with $m$ being the block size.

The whole attacks requires $2^{n+m}/p$ time and $p$ storage.

(the attacks can also be found in Schneier's Applied Cryptography)

Why is 3DES more secure than DES?
Because the keyspace is larger. 3DES has a keyspace with 112-bits in size whereas DES has only $2^{56}$ keys, which is brute-force-able.


How can I process data within a cloud securely? I'm new to programming and I'm getting ready to design a proof of concept for an app that I'm thinking of building. Problem is I'm a complete noob to cryptography and need a little nudge to point me in the right direction.

I would like to design a method by which data sent to my application on a cloud server is processed securely.

Here is a scenario:
1. Company A publishes XML file on their server and makes it available via SFTP.
2. A process on Cloud Server uses SFTP to fetch the data from Company A's server.
3. Cloud Server parses the XML based on a defined format, but it must do so securely so that even the server admin cannot see the processed data.
4. Cloud Server rebundles the parsed XML data into emails that are transmitted via SSL to Company B.

Step 3 is what I need some help with. SFTP and SSL are good enough for the pull and transmit side of things. I'm just wondering how to secure the XML such that my app can do what it needs to do given the right keys - but I don't want to know the keys. The keys would need to be known only by Company A (publisher) and the recipient (Company B). And if there was a problem, Company B could login to Cloud Server via a web page and view their data unencrypted given they have their key.

I've seen businesses in the email archiving and file storing space that can blindly encrypt data so that they cannot ever view your data. (Proofpoint, SecureSend are examples) If you lose your key, they cannot decrypt your data. I'm thinking my process would use something similar.

Would anyone know the method or process that can do this? Thank you.

In general this seems not possible. To process the data, you need to have it in plaintext, and if you have it in plaintext an admin might read it.

However, if your processing needs to read only some parts of the XML (e.g. tag names), you could encrypt all other parts (e.g. field values, attributes). Information might still leak through the unencrypted parts.


How can I repeatedly prove I have data another has seen without sending the data and without the other storing the data? I would like to know if this is theoretically possible, or impossible, and if possible, if there is any algorithm/protocol to accomplish this...

I want another entity, lets call them the Auditor, to be able to see a piece of data, store something smaller that's derived from that data (I might not know what it is), and then I want to be able to prove to the Auditor repeatedly that I still have that piece of data without having to send the data itself.

If we relax the last requirement I could just send the data every time and the Auditor could verify the hash.
If we relax the 'repeatedly' requirement the Auditor could store a salted hash without telling me the salt, and then later give me the salt and ask for the salted hash back, but that only works one time since afterwards I could just remember the salted hash, throw away the data, and still fool the Auditor.
If we relax the 'derived' requirement the Auditor could store its own copy of the data and do a simple challenge-response protocol.
... but I haven't been able to figure out how to do it without relaxing any of these requirements.

THANKS!

I will just add few comments to the excellent answer and links provided by PulpSpy above which might help you getting the more correct paper from the pool of thousands of paper written in this area, both by theoreticians and practitioners.

If you want to have a proof that prove the possession of any bit of the data file, then the paper of Atienese et al. cited by PulpSpy doesn't work (they work for more practial scenario and are very fast). Naor and Ruthblum, actually, gave the protocol in The Complexity of Online Memory Checking for proving data possession at any granularity. They called it memory checkers. They also relaxed the notion of memory checkers to prove the result for something called authenticator, which can be seen in the same vein as the definition of Proof of Data Possession and Proof of Retrievability, first defined by Juels and Karlinski in Pors: proofs of retrievability for large files. Incidentally, both the papers came in the same conference, presented one after the other. The work of Atienese et al. was later shown to possess the stronger notion of Proof of Retrievability by Waters and Shacham in Compact Proof of Retrievability.

The literature for this problem is very old and Naor and Ruthblum has a very detailed literature survey in their paper. You may find the reference therein quiet useful. For recent works, there has been quiet a few works on this area.


Is there a good reason not to mention that ECC is weaker than RSA on a quantum computer? In most papers and other documents I see people are considering an ECC key of 256 bits equivalent to an RSA key of 3072 bits, which is true on a classical computer. But the amount of qubits required to crack RSA keys are estimated to be 2•bits while ECC is roughly 6•bits, which would make 256 bit ECC weaker than 1024 bit RSA.

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

Source: https://security.stackexchange.com/a/96880

Is there a good reason to leave out that ECC is weaker than RSA on a quantum computer when writing a paper that involves comparing RSA to ECC? E.g. you want to promote the use of ECC over RSA.

I mainly see two reasons against comparing the quantum attack cost of RSA and ECC:

If your threat model includes (large) quantum computers, you should neither promote RSA nor ECC : they both scale badly against them, and any argument about which is stronger or weaker is marginal.
Since quantum computers large enough to be useful do not exist as of today (2017), it is to soon to compare precisely the two schemes, since the quantum computer’s architecture (as in “Von Neuman architecture”, not x86 vs PowerPC) is far from settled. Many different theoretical models exists (circuit model, measurement based quantum computers, Clifford computation with magic states, etc.), different universal sets of gates and fault-tolerant architectures are proposed, and work on quantum compilers is only starting. For a theoretician, this in “not really important because all these models are polynomially equivalent”, put this might easily reduce (or increase) the gap between ECC and RSA.


Offline session key agreement protocol Is there any implemented solution to agree on a session key in offline way.

I can exchange some keys before being offline but I need both sides to create the session key offline.

I need implemented and secure solutions.

Given the information in the question and in the comments, this is pretty straightforward:

Online phase: Use any common key agreement protocol, e.g. Diffie-Hellmann key exchange to generate a shared secret.
Offline phase: Use a proper key derivation function on the shared secret and a nonce - one nonce for each key you need to generate. A counter would also work.

  I need implemented and secure solutions.

Both functionalities should be included in various cryptographic libraries.

For the security it is necessary to make sure that the shared secret is stored securely. But that's basic key management.

For the security proof you could argue that the KDF is actually a PRF or use the properties of one-way functions. A proof by contradiction should only take a few lines.


How to crack Vigenere ciphertext if multiple keys of coprime length are used? I came across the idea of using multiple Vigenere keys of coprime lengths here.  The idea is, what if you use multiple keys, whose lengths are all co-prime?  Then your effective key length would be the product of the length of all keys since they never line up with each other until that point.

It would be fantastic for key management since with keys of lengths 29, 31, and 37, your effective key length would be over 33,000!  You could reuse them for many messages as long as you keep track of effective key length usage.

How would one go about cracking such a ciphertext, when its length is shorter than the product of N keys, whose lengths are all co-prime?

I posted this same question on Reddit here and got this apparent solution, but it's too vague for me to follow since the author didn't have the time to go into more detail.

Turns out the way you break it is by using the Kullback Test.


RSA Timing Attack and Prevention through blinding I am kind of confused regarding timing attacks on RSA.
I do understand that the attack exploits the fact that the modular exponentiation (square and multiply) has key dependent branching. That is, if bit $k$ of $x$ is $1$ then the duration of the exponentiation takes longer than if the bit is $0$.

But how is the execution also dependent on the message (the inputs)?

The proposed solution of Kocher is "blinding" by a adding a random value to the message. Hence, the execution time can not be correlated to the input anymore, but how does this help? Isn't the execution still slower if the exponent bit is $1$?

Thanks in advance!

But how is the execution also dependent on the message (the inputs)?

Actually, there are (at least) two potential timing attacks.

One is as you suggest; the timing (at least, for this simple exponentiation algorithm) is related to the hamming weight of the secret exponents. However, as you have observed, the secret exponents aren't dependent on the ciphertext.

However, there is a second potential timing variation that the attacker might attempt to exploit.  Suppose that you compute an intermediate value $C^{k} \bmod N$, and that value just happens to be unusually small.  Then, depending on the bignum library you use, it is possible that the next operation (especially if it is square, possibly if it is a multiply) will go unexpectedly fast, and that timing variation would tell you if $k$ was an intermediate exponent (which gives you a number of bits of the secret exponent).

Now, in practice, it doesn't work that well; it's hard to compute $C$ values where $C^k \bmod N$ is small (and it becomes even harder if the implementation uses CRT, there you'd need values where $C^k \bmod p, q$ are small.

So, what you end up doing is passing in random $C$ values, looking for values that are processed unexpectedly fast, and deducing things from that.

  The proposed solution of Kocher is "blinding" by a adding a random value to the message.

I'm pretty sure you misunderstood.  For one, adding a random value to the message gives an unrelated result.

If Paul proposed anything (he has proposed a number of things; I don't remember hearing these specifically from him), he may have suggested one of the following two things:

Multiplying a random value to the message.  That is, select a random value $r$, compute $r^e \bmod n$ and $r^{-1} \bmod n$; then multiple $c' = (r^e \bmod n) \cdot c$; perform the RSA operation on $c'$ resulting in $t' = RSA_{private}(c')$, and then compute the final $t = t' \cdot (r^{-1} \bmod n)$.  The RSA operation is done on an equidistributed value, and hence there aren't any message-based side channel leaks there
Add a random value to the exponent.  That is, (and I'll assume you're doing CRT here) select a random value $r$, and compute $t_p = (c \bmod p)^{d_p + r(p-1)} \bmod p$ (and similarly for $q$).  Except for a couple of the lower order bits, the exponent you use are randomized (and that could be covered by always selecting $p \equiv q \equiv 3 \pmod 4$)

On the other hand, Paul would never suggest either of the above as the sole protection for a badly leaking modular exponentiation routine.  Using power analysis (invented by Paul), you could obtain the exponent from a single trace; this would foil either of these countermeasures.


What good is a hash accompanying a program? After studying at length about weaknesses in SHA2, length extension attacks, forged signatures, etc. I have to ask why groups like Gnu provide hashes on their program texts?

As long as the public knows how the hashes were generated, a forger could substitute his own malicious code and cook up a totally valid hash for it, so that it would look legitimate.

So it appears that this is "security theater" which looks serious, but has really no way of assuring anything meaningful.

Well, if you can assume that the website hasn't been hacked, then providing a SHA2 hash of a program would allow you do make sure you downloaded (from anywhere on the internet) a good version of the software.

You are right, however, that since the method is publicly known, if someone can replace the binary on the site, they can also replace the hash on the site.

This is why a number of sites now publish PGP signatures of their software, instead of a simple hash. Now an attacker would have to forge the signature, which is computationally infeasible. This assumes that you know the valid public key. How do you get the public key? Well, that is another can of worms.


Prime number theorem - RSA I am having trouble understanding the prime number theorem.

As part of some revision for an exam, I am trying to answer the following questions (but seeing as I don't understand the concept of the prime number theorem, I'm not doing too well):

Question 1:

What is the proportion of numbers that are prime up to 1,000,000?

Question 2:

If we use prime numbers of size 1536 bits to generate an RSA modulus of 3072 bits, what is the proportion of numbers of size 1536 bits that are prime numbers?

I understand that using 1536 bits means that is it pretty much computationally infeasible to stage a brute force attack on an RSA key, but I don't understand why. In our lectures, we are given an example of $ln (2^{512}) = 355$ which means that 1 in every 355 numbers of size 512 bits is a prime. But I'm not really sure how to translate that to help with the two aforementioned questions.

Can anyone please shed some light and explain the answers to those questions?

Apply your formula, perhaps simplified as $\ln(2^x)={x} \ln(2)$, so for 1536-bit numbers about one in $1536 \ln(2)$ are prime. In the case of $1{,}000{,}000=2^{20}$ (approx.) the number of primes is about one in $20 \ln(2)$.


First preimage resistance check So I have $H: \{0,1\}^* \rightarrow\{0,1\}^n$ a hash function resistant to the second preimage and to collisions. Let there be a function $H' : \{0,1\}^* \rightarrow \{0,1\}^{n+1}$ with the following properties:

$$H'(x) = \{0||x\; \text{if}\; x∈\{0,1\}^n;\quad 1||H(x) \text{ otherwise}\}$$

Is $H'$ preimage resistant $∀ x$ ?

I know that I have to find an $x$ for which this property fails, but I cannot think of one, could you please help me and explain how to demonstrate this?

Preimage resistance is usually defined not for all the inputs, but for all the outputs, since what you are trying to model is the inability to, given any output $y$, obtain an input $x$ such that $H(x) = y$.

I'm not going to solve the problem for you since you may be able to do it by yourself. Just try to think of the patterns in the output and if this can be related to some input.


Pseudo code for CTR mode encryption I am following a document here about CTR mode of encryption. I have some point uncleared.
At the part 1 Review of Counter-Mode Encryption.
Operation.

  To encrypt using CTR-mode encryption, one starts with a plaintext  M
  (an arbitrary bit string), a key K, and a counter ctr , where ctr is
  an n-bit string.  Let C be the XOR (excusive-or) of M and the first
  |M| bits of the pad  EK(ctr) || EK(ctr+1) || EK(ctr+2)... The
  ciphertext is(ctr,C), or more generally, C together with something
  adequate to recover ctr.

  To decrypt ciphertext (ctr;C) compute the plaintext M as the XOR  of C
  and the first |C| bits of the pad  EK(ctr) || EK(ctr+1) ||
  EK(ctr+2)...

  Therefore, decryption is the same as encryption with M and C
  interchanged

As I think, the pseudo code will be:

selectFirst(pad, plainText M){
    int n = length(M);
    return n first element of pad
    return firstElements(pad, n);
}

void ctr(){
    string M;
    key[16] K;
    n-bit-string ctr;
    pad = EK(ctr) || EK(ctr+1) || EK(ctr+2)...
    firstM = selectFirst(pad, M);
    C = xor(M, firstM);
}

EK (x) is encrypt x (using some algorithm such as AES) with key K.
But I don't understand:

  what is ctr + 1, ctr+2...?
  Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?
  Is CTR mode one-time execution and not using loop?

what is ctr + 1, ctr+2...?

ctr is the first 128-bit input value processed by the block cipher, ctr+1 is this number incremented by 1, and so forth. In practice, ctr is generally a combination of a 96-bit nonce and a 32-bit incrementing counter.

  Is EK(ctr) || EK(ctr+1) || EK(ctr+2)... an 'OR' operation? and what is its result?

No, || refers to concatenation in this example.

  Is CTR mode one-time execution and not using loop?

No, CTR mode implementations almost always use a loop, and process in increments of a multiple of the block size.


Cracking vigenere of non-text cleartext I've begun a course in crypto on coursera and the first homework was writing a vigenere(xor) cracker. It works, which was a rush :) but it makes one core assumption, one has encrypted a natural language text that the script can use frequency analysis on. Therefore doesn't work if one encrypted an image or a compressed file. How does one do it if frequency analysis isn't an option?

AFAIK vigenere cipher is a plain subsitution algorithm with arbitrary key length, destroying statistical patterns (f.e. of natural languages) but not conducting any transposition.

Btw. a classic approach to crack a vigenere cipher is the Kasiki-Test (https://en.wikipedia.org/wiki/Kasiski_examination) which might give you information reagrding the key length.

If you try to decrypt a file format (jpeg, gif, zip etc.) you actually know at least the first bytes (fileheader) as they are defined by convention:
f.e. a zip file always starts with 0x04034b50 (https://en.wikipedia.org/wiki/Zip_%28file_format%29) which gives you the first 4 bytes for your decryption table.


Is this simple memory-hard function good? I'm trying to come up with a simple memory-hard function for a proof-of-work system to protect against spam. Is the one below secure?

For a message M, append a random number R. Repeat until you find R1, R2 such that sha256(M++R1) and sha256(M++R2) share at least d binary digits. R1, R2 is the proof of work, which is sent along with the message. Replace sha256 with any cryptographic hash function you'd like.

I'm assuming this function is memory-hard since you'd want to store all R and their corresponding hash to increase the likelyhood of a match. If you don't store them all, you decrease the probability of a match, which saves memory, but requires more cpu time on average. Also, only storing a part of a hash, like the first half of each hash, should save memory but decrease the probability of a match by orders of magnitude.

Is there an obvious flaw in this algorithm? Is this a known algorithm? Is there a standard algorithm that is roughly as simple to implement?

TL;DR: No, this is not memory-hard and may not even be as computationally intense as you would have thought.

Suppose we have a hash function $H:\{0,1\}^*\to\{0,1\}^n$, for example SHA-256. Now we can construct $H':\{0,1\}^*\to\{0,1\}^n:m\mapsto H(M\parallel m)$ for some fixed, pre-defined message $M$ and where $\parallel$ denotes concatenation. Note how $H'$ is a normal hash function.

Now the task is to find $r_1\neq r_2$ such that $\Delta (H'(r_1),H'(r_2))\leq n-d$ for some work-factor $d$ with $\Delta(\cdot,\cdot)$ denoting the Hamming-Distance. If you have such $r_1,r_2$, this is called a near-collision with a difference of $k:=n-d$.

Now note that for $d=n$ this equals having to find a collision on $H'$, which can be done in time $2^{n/2}$ with negliglible memory. The algorithms for this are Floyd's cycle finding (to see that it can actually be done with negligible memory) and Pollard-$\rho$ (which is state-of-the-art and descriptions can be found in this PDF by Bernstein, even though it mostly talks about how classical collision finding is better than quantum-based). Also see Section 9.7 of the Handbook of Applied Cryptography (PDF).

Now the first obvious optimization one can make is to only consider the first $d$ bits of $H'$ and try to find a collision on them, ie try to find a collision on $H'':\{0,1\}^*\to\{0,1\}^d$ where $H''(m)$ is the first $d$-bits of $H'(m)$. Now we can do the proof-of-work with $2^{d/2}$ instead of $2^{n/2}$ operations and without memory.

Now if we wanted to optimize for time a bit more, we could notice that essentially all bits of $H'$ are independent random variables that take the values $0,1$ with 50% probability each and pretty much independently of each other. So we basically get $d/2$ for free! Furthermore we can apply the math of Binomial-Disitributions to get an estimate for the required amount of samples for 2nd-pre-images. The details of this are explained in this answer, but the TL;DR is $l:=\frac{2^n}{\sum_{i=0}^k\binom{n}{i}}$ messages are needed for a 2nd-pre-image for a fixed message and and $\sqrt l$ messages for a "simple" near-collision. Of course this requires the storage you hoped for, but it's probably less than expected. The complexity $\sqrt l$ is actually proven as Lemma 1 in the second paper below.

Now if we want to leave the land of "simple" strategies to this, there is academic research on how to find such near-collisions with "Using Random Error Correcting Codes in Near-Collision Attacks on Generic Hash-Functions" by Inna Polak and Adi Shamir seeming to be the newest contribution (which also uses a bit of memory) and "Memoryless Near-Collisions via Coding Theory" by Mario Lamberger, Florian Mendel, Vincent Rijmen and Koen Simoens (PDF) being a somewhat older one. Complexities for the algorithms of these papers are hard to estimate, but it's brought up that $n=160,k=33,d=127$ was carried out with a single PC.


Why is RSA secure if I can solve the equations for it using a math solver? To factorize N = p * q with p < q e (p-2) mod 9 = 0, there are a set of equations. These equations can be put into any popular math solver, in order to gain access to the primes p and q. For instance, the prime components of the public key N = 209 can be solved as follows:

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n+2*(p-2)),(h+1)/3=(k+1)/6 ,p^2+n*p=209,
                            h+1+k+1=(209-4-2*n+2*(p-2)),h,X,n,k

->

h = (2 (-209 + 99 p + 2 p^2))/(3 p)

[(h+1)^2]*[(2*h+2)^2/2-1] = X*(209-4-2*n),(h+1)/3=(k+1)/6 ,p^2+n*p=209,
                            h+1+k+1=(209-4-2*n),h,X,n,k

->

h=(2 (-209 + 101 p + p^2))/(3 p)

(2 (-209 + 99 p + 2 p^2))/(3 p)-(2 (-209 + 101 p + p^2))/(3 p)=6

->

p=11

This shows that p = 11. By simple division, it can be determined that q = 19.

It seems to me as if this approach is somewhat obvious, and I'd like to know how RSA is still considered secure if I can do these calculations in a math solver?

The RSA problem, which is the underlying problem that makes RSA cryptographically secure, is currently considered as an unsolved problem. There exists no known algorithm to efficiently compute P, given the public key (N, e) and the ciphertext  C ≡ Pe (mod N).

But who cares about theory, right? You claim to have a solution, then try it! Here is an RSA public key:

    -----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEApjP/ml4yt/iLr3Kzt7yv
H+7zEdnJ04xCTeW+Vx9CBRQukRdkVoMYntP6RHx6mZSeMKTXtOt87LHVxOoNi2Bf
efoQAxB1ehXW4h8F1tnmSruKt87U9YDe0W8Z9GOC63vq5eu95zqDvWQ6s42P4Gga
eZGXD6RKaw6TcYqfl7MWR6I21lOgFUKojNb0+LD4wdaES1L7pOlbCLstaQO91Dea
3HyD1h+NKEDrVT2goVnTbsF9AZf8xHmEHhWAZNRpsskiXlG6PKdlzuBbt1q+5b4J
0Kimw01mwgKt/2k4LkPa6PaM2PoiXisfDeaRLFV5F3INokhwaYNTolzEaz7y+Tyr
OhBwrcvMK+/1iMPzNgSk0qsnObX0+fn9e/RZvzxz8hdlWqVGVb4sswWt+bJnn1Bv
zZ58Q+NlQG7kQb58i+zHuBqvbunbMWT9osmbS4W+PVKG0nGrusRlTc3lY10HfoPE
hX3r1L4rYQUO1wdukkdfKOL0lcITu1A8Wv6olFpQna8u/hIW0dY0qdqiHO/kSLjJ
zCJNX/hzx3Cy1oUSrEaIjs5Lv6Nuu0r2mFwS6f8kgg5rXPI97homStro8bmwQQF8
EcyPlq9OXS2Ide/F6IxY/HzkpOlbwzoSsqyjoJCC9mwd+67ItShKUQdx/1c4aZme
6+9s50KyK5Pna5dVi+CVrEkCAwEAAQ==
-----END PUBLIC KEY-----

Here is a ciphertext, encrypted with said public key and encoded in base64:

mFrcsgt06GQ8xAK60D5iMBMc/oDTj/MwvG/obnS6pDl3svhlde4aOfkAIUPlawfl2uDYuX2TD3VB
L5iJYCDRsCoGcxbnQ1kS6Q2zXevBzs33RQg5sanXVt8Jic+OWWVPPwN3JPDuS3Ot4ljgs8eB7LTR
hvmeyVMfT6iue3AMU+B1EOnMpij5I9HQs6eUGO29ROU6WJk7PFYIY6M0FrTVyYXHoSwl+zukQzdu
kYPcj0ST4NsjR93h7drPeyo7y/LVI5mCIp+kPD2SXH1BAzxGAcZLA85MZFHypbqiU+7eO4iBmYPD
BJDU02PiTyB6YGFrsQFZWeVeycdniuCfbQeaGH6eb4qZxHsNhosCEdyxQRF8c4Nh2+q8LwqrPwid
kKcoEqh4/HbBqgXQ/UXLTvUCucowDtW4sDFlT1nsup3Tod0xd3Ea3hEf9qZJnVKe/puHxEB6cwf1
5SbEBBRBCusJ8o6MhmWa2U14dBuO4J+YDJiCiL6PMJ2sCjeTEsKdegx0O82Bvs4sMbbTFZUb/T0u
oC1P0o4MHAFHwNkl85rkgih2d15lyOSsYiZ6TEQ41EE7wckIV/48rjL1JoXIFsxVDsuihXhSOpR4
/LKhXv0OdkrPOeZpjPwNq9eo/DgiCTVwtxWYxvk5UKT+64fefqpyqwM9YOqWEQfJkeh/niVlsrc=

Of course, since you have the public key, you can make as many ciphertexts as you want with it. I just thought I'd include a little message for you when you are done.

Good luck!


Why does TLS 1.3 AES cipher require both a server and client traffic key/iv? During the TLS 1.3 handshake using the cipher suite TLS_AES_128_GCM_SHA256 a server and client traffic key/iv will be derived using HKDF based on the shared secret, see rfc8446 #7.1
Why is it necessary to derive the key/iv for both the server and client instead of a single key/iv for encryption and decryption?

Why is it necessary to derive the key/iv for both the server and client instead of a single key/iv for encryption and decryption?

Of course, it's not necessary for TLS 1.3 to be designed that way, however that's the way they decided to do it.
As for why, well, for all the encryption modes supported in TLS 1.3, it is necessary for security to never encrypt two different records with the same key/nonce combination.  With the current record design, the encryptor selects the nonce; hence, if two different encryptors (the client and the server) had the same key and selected the same nonce, well, things would be broken.
Now, they could have partitioned the nonce space; for example, tell the servers "you always encrypt with a nonce that starts with a "0" bit" and clients "you always encrypt with a nonce that starts with a "1" bit"; that would work, however they declined to do so.


For the LTV-FHE scheme, after how many additions should modulus switching be used? From the LTV-FHE paper I find out that after every multiplication there must be a modulus switch to mitigate the noise in the resulting ciphertext, besides relinearization.

But, assuming the ciphertexts to be summed are the result of many operations and we have consumed many levels of the moduli ladder, that means that the room for noise is smaller. ( The assumption that the room for noise is getting smaller may be wrong, I haven't found any proof yet, is my personal observation.)

So, if we evaluate homomorphically many additions of ciphertexts like those aforementioned, should we use modulus switching to cut the noise before wrap around ?

First of all, I want to clarify that there is no relinearization involved in ciphertext multiplication.

Second, as discussed in the BGV paper, its not the ratio of noise to modulus size that matters but the absolute magnitude of noise is important and we should bring down the noise magnitude after each multiplication.

And finally comparing homomorphic addition to multiplication, the noise growth in multiplication is exponential whereas the noise growth in addition is atmost a single bit. Therefore we can perform multiple additions but not multiplications. Theoretically, you can compute a bound for maximum number of additions or multiplication before the noise wraps around the modulus, rendering the decryption unsuccessful.

I hope this helps you.


Would using a one-time pad multiple times with some conditions be safe? I understand why |one-time pad|=|message| using a normal one-time pad, but I don't understand why for perfect secrecy it must alway be that |key|>|all messages exchanged|.

What if, for example, I had |one-time pad|=n*|message| with n>1 and then used it for (for example) 2n messages with a random starting point (itself encoded at some point in the message with a 'normal' one-time pad which given it's a single number could be simply be the first part of the original OTP)?

I'm pretty sure there must be something that doesn't work, because if this was still perfectly secret then a one-time pad could be used to generate infinite one-time pads which would be useful but impossible (wouldn't everybody be using it?). So, where does the perfect encryption of the one-time pad end?

For perfect secrecy of any cryptosystem, it must hold that |key|≥|all messages exchanged|.

Proof by contraposition: assume |key|<|all messages exchanged|, and there exists a deterministic decryption procedure of all ciphertext exchanged and key to all messages exchanged. Knowing all messages exchanged, an infinitely powerful adversary can exclude some value of messages exchanged as impossible, violating perfect secrecy; all s/he has to do is apply said procedure to decipher the given all ciphertext exchanged with all the possible values of key, and rule out as impossible any value of all messages exchanged not obtained for any value of key. The hypothesis |key|<|all messages exchanged| implies there will exist at least one impossible value, by a counting argument.

In the case of the repeated OTP in the question, there exists attacks that can be performed by an adversary with very limited computing ability, and enough knowledge about the plaintext.

For example, assume that all the messages are long, random, and known entirely except for an unknown bit in the middle of the last message. It becomes likely and easy to find most of the key, and the starting point for all messages, and from that the single unknown plaintext bit.

There are more clever attacks that work with less hypothesis on the plaintext (like: it is mostly English words), and remain feasible in practice if there is enough ciphertext.


Can you decrypt all messages if a private key is obtained of one of the two entities in asymmetric encryption? Given a context where Alice sends messages to Bob and vice versa. There is an intruder, Carol, that has obtained the private key of Alice. She also obtained both public keys.

Can Carol decrypt all messages or only the ones that are sent from Bob to Alice?

If Carol can decrypt all messages:
How can she do this?
Are there algorithms where Carol couldn't decrypt all messages if she obtained only one private key?

If they both use public key encryption to encrypt messages (think e-mail + GPG for example) than obtaining Alice's private key would allow you to decrypt only messages sent to her from Bob. To decrypt messages sent to Bob you need his private key. This of course assumes that there were no plain-text copies of messages in the same place where attacker obtained Alice's private key.

In case they use some chat-like protocol (e2e encrypted messenger) and they use their private keys to set some session keys things are different. When Eve has Alice's private key she can read all messages sent in either direction after she obtained key and potentially all past messages (again, in either direction) if protocol used has no forward secrecy


In OTP you have $C=K\oplus{M}$. If the key is the same $C1=K\oplus M1$ and $C2=K\oplus M2$,  => $C1 \oplus C2$ = $K\oplus M1 \oplus K\oplus M2$ = $M1 \oplus M2$  If you have the same ciphertext, that means that the same message was encrypted. E.g. messages 4,6,7,11 have the same first 6 symbols.


How is the One Time Pad (OTP) perfectly secure? The Wikipedia entry on One Time Pads (OTPs) states that if this cipher is used properly; ie, the keys are truly random and each part of the key is independent of every other part, it's uncrackable, and yields perfect secrecy, i.e., $H(M|C) = H(M)$.

It gives an example saying that a cryptanalysis on a plaintext "HELLO" will yield all plaintexts like "HELLO", "LATER", with equal probabilities.

Now, consider some OTP encrypted data that I know are English sentences. With infinite computational power, I generate all plaintexts. Now, becasuse each word of the sentence is related to nearby words, I can at the very least narrow down the list of possibilities (I don't know the combinatorics of cramming English sentences into M letters), which does not equal perfect secrecy (entropy $H(M)$ appears to have decreased!).

In short, OTP guarantees $H(M|C) = H(M)$, but my question is that $H(M)$ will be reduced by knowledge of the plaintext, so how is prefect secrecy being ensured?

You've actually been trapped by the mindset that OTP will hide all information about the underlying plaintext.

This is not true as you have observed.

The definition of perfect secrecy, given in Introduction to Modern Cryptography by Katz-Lindell, reads like this:

  Definition 2.3 An encryption scheme $(\text{Gen, Enc, Dec})$ with message space $\mathcal M$ is perfectly secret if for every
  probability distribution over $\mathcal M$, every message
  $m\in\mathcal M$, and every ciphertext $c\in \mathcal C$ for which
  $\Pr[C=c]>0$:

  $$\Pr[M=m\mid C=c]=\Pr[M=m]$$

In other words, if you have the ciphertext at hand, you won't learn anything new that you didn't already know about the plaintext.

The OTP satisfies this (proved in "Introduction to Modern Cryptography") and thereby is perfectly secret as an encryption scheme. In short it first shows that $\Pr[C=c\mid M=m']=2^{-l}$, then uses this to show that $\Pr[C=c]=2^{-l}$ and concludes via $\Pr[M=m\mid C=c]=Pr[M=m]$ (using Bayes' theorem).


Secure "table-look-up" operation I am thinking about this problem:

The server has a two-column table $T=\{c_1,c_2\}$. A user has a query $q$ that is sent to server. The server find an item $x$ in the first column satisfying $x=q$ and return the item $y$ in the second column to the user ($x$ and $y$ are in the same row).

The requirements are that:

server should not learn $q$.
user should not learn other items besides $y$.

The above scenario is quite similar to those in Oblivious Transfer or Private Information Retrieval. However, there is a slight difference (to my understanding). The user does not know which item he wants to retrieve in advance. The index of the item to be retrieved is obtained by comparison with the items in the first column.

So, my questions are

how to modify OT or PIR protocols to fit with this situation?
What's the most efficient OT or PIR protocol (in terms of communication efficiency) to deal with this situation?
Are there any other ideas besides OT or PIR?

Thanks.

Kolesnikov & Kumaresan defined a primitive called "string select OT" which basically covers your setting but with a database of 2 items. Sender has $x^1, y^1, x^2, y^2$. Receiver has $x^*$. If $x^* = x^i$ then the receiver learns the corresponding $y^i$.

I think a generalization of their protocol would work, at the cost of $n$ 1-out-of-2 string OTs where $n$ is the number of bits in the $x$ values.

Parties do $n$ instances of string OTs on random strings $(m_0^1, m_1^1), (m_0^2, m_0^2), \ldots$ The receiver uses the bits of $x^*$ as his choice bits.
For an $n$-bit value $x$, sender defines $K_x = H( \bigoplus_i m_{x[i]}^i )$ where $H$ is a random oracle. The thing inside $H$ is the XOR of the things that the receiver would get if his choice bits were $x$. (the hash is there to kill the correlations among the different $K_x$ values)
For every $(x^i, y^i)$ in the database, sender sends gives $\textsf{Enc}(K_{x^i}, y^i)$. (assume it is an authenticated encryption, so you know when you have successfully decrypted)
Receiver can decrypt exactly one of these ciphertexts, and learn $y^i$.

  Vladimir Kolesnikov, Ranjit Kumaresan: Improved Secure Two-Party Computation via Information-Theoretic Garbled Circuits. SCN 2012: 205-221

edit: Here is another approach, using ideas from one of my papers. The paper only needs this functionality for database of size 2, but I think it would generalize as well. (we refer to this subprotocol as PFE of a universal hash function).

Parties do an MPC where receiver inputs $x^*$, sender inputs randomly chosen $a$ and $b$ from a large field. Receiver learns $ax^* + b$. Think of this as evaluating a private a 2-universal hash function. It has the property that even given $ax^*+b$, any other $ax'+b$ value is uniformly distributed.
Sender sends $\textsf{Enc}( H(ax^i+b), y_i)$ for each $(x^i, y^i)$ pair in the database. Receiver can decrypt exactly one of them.

  Zhangxiang Hu, Payman Mohassel, Mike Rosulek:
  Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost. CRYPTO (2) 2015: 150-169


What do we gain from hashing the length in Merkle–Damgård? Assuming our fixed compression function $h$ works for inputs of length $i(n)$ and output strings of length $o(n)$, if $2o(n) < i(n)$, why do we need to calculate $h(z_B||L)$ where L is the input's length instead of just concatenating $z_B ||L$? What do we gain from hashing the length?

I am making the assumption you are asking why not just append the length to the output of the hash, the question is not quite clear on that. Take a very simple example of SHA-1 modified to do what I think you are asking. The results here are fake, but the example stands.

If we hash a byte stream of 0xFE25B6A1C8, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000028.

If we hash a byte stream of 0xFE25B6A1C800, we may receive the digest a9993e364706816aba3e25717850c26c9cd0d89d0000000000000030.

It should be clear that this is not a desirable property.

The same property applies to other inputs where there are trailing 0 bits within the same compression function call and the same total number of compression calls, the bits have no effect on the hash function without the length because of how they are used to generate the message word array.


Is the result of HMAC-sha256 distinguishable from random noise? Is if the result of HMAC-sha256 distinguishable from random noise?

If so, given:

a collection of 1000 keys, and
1000 messages of random noise, 100 signed by each of only 10 of those keys

Can any clue be found as to which messages were signed by which of the 1000 keys.

edit:

Assuming 4KB messages, indistinguishable from random noise, and 32 byte keys, also indistinguishable from random noise.

If the keys and messages are known, yes, you can distinguish which were used - because you can test them all. If not, then this is "sligtly harder" (= not really possible with big enough values). Anything of the further answer will assume that the attacker doesn't know the keys or the messages.

The definition of HMAC looks like this: $HMAC(K, m) = H(K \oplus opad || H((K \oplus ipad) || m))$ with $k$ as the key and $m$ as the message. $opad$ and $ipad$ are constant, different values while $H()$ is the used hash function - in your case SHA-256. We can see that the end result is the output of a hash function. If there's nothing special happening with the key or the message inside the function, than all security features about the hash should also hold for HMAC. Finding the original message (while having the output of the hash function) should be hard - that's called preimage resistance. As long as the keys and messages were long enough, it shouldn't be possible (with non-ignorable probability) to find the orignal message in a reasonable time. Good hash functions should also be not distinguishable from truly random output, so this should also be no problem.

Even if you have every message HMAC-hashed with every key it is still not possible to say which HMACs were calculated with the same key / with the same message. The attacker will only see $1\,000\,000$ random looking bit strings ($1000$ keys times $1000$ messages) and have no clue what to do with them.

As soon as there are patterns in the keys or messages, it will be easier to attack the hashes. $80$ bit of entropy (from message and key together) should be enough to ward of any brute force attack. No hash is secure if the messages are small enough.

The document Keying hash functions for message authentication has more informations and the security proofs for HMAC. You can read there why it should be not really possible to find the used messages and key in your scheme - if they are big enough.


Alice and Bob's crush Suppose Alice and Bob both want to determine whether the other has a crush on him/her, but they only wish to share the information if the crush is mutual. Is there a cryptographic protocol that makes this possible without using trusted third parties? It is safe to assume that they will not lie during their "encrypted announcement" to the other.

Covert two-party/multi-party computation provides exactly what you're looking for.  The two-party case was introduced by von Ahn, Hopper, and Langford, and a more formal definition and multi-party protocol was given by Chandran, Goyal, Ostrovsky and Sahai.

Covert secure computation even hides whether or not the parties participated in the computation at all, unless the result of the computation determines that it should be revealed.  For Alice and Bob, their inputs would be one bit each, indicating whether each is romantically interested in the other, and the function to be computed on these bits is AND.  If the function output is 1, then that fact is revealed to both of them and they live happily ever after.  Otherwise, they don't even learn whether the other even played the protocol.  So if Bob likes Alice but not vice-versa, Alice won't even learn that Bob participated at all, thus saving him from eternal embarrassment in her presence.

The von Ahn et al paper gives many more applications of the concept, e.g., two undercover spies from allied countries who may want to collaborate.


Deniability and Prekey Security in X3DH Key Agreement Protocol Can someone please explain the below paragraphs from The X3DH Key Agreement Protocol?

1st paragraph: What is deniability and how does it work here?

  Deniability

  X3DH doesn't give either Alice or Bob a publishable cryptographic
  proof of the contents of their communication or the fact that they
  communicated.

  Like in the OTR protocol [6], in some cases a third party that has
  compromised legitimate private keys from Alice or Bob could be
  provided a communication transcript that appears to be between Alice
  and Bob and that can only have been created by some other party that
  also has access to legitimate private keys from Alice or Bob (i.e.
  Alice or Bob themselves, or someone else who has compromised their
  private keys).

  If either party is collaborating with a third party during protocol
  execution, they will be able to provide proof of their communication
  to such a third party. This limitation on "online" deniability appears
  to be intrinsic to the asynchronous setting.

2nd paragraph: How would this passive attack work?

  Compromise of prekey private keys may enable attacks that extend into
  the future, such as passive calculation of SK values, and
  impersonation of arbitrary other parties to the compromised party
  ("key-compromise impersonation"). These attacks are possible until the
  compromised party replaces his compromised prekeys on the server (in
  the case of passive attack); or deletes his compromised signed
  prekey's private key (in the case of key-compromise impersonation).

Deniability

Let's say that Eve notices that Alice and Bob are having a secure communication. Later on, Eve shows up to Alice's home and demands that Alice turn over all of her private keys so that Eve can expose their conversation. Alice and Bob want to ensure that their previous communications remain private.

If Alice encrypted a message $m_1$ into ciphertext $c = E(m_1,r)$, where $r$ is some random input (perhaps a shared secret), then Alice may want to deny she sent $m_1$ and instead claim that she encrypted another message $m_2$ such that $c = E(m_2,r')$, where $r'$ is some other random input. If $E$ has this property, it's called deniable. Unless Eve has telepathic superpowers, she can't trust Alice at all, since she could've turned over $m_2$ and $r'$ instead of $m_1$ and $r$. In fact, this protects Alice's data from even herself in the future! (How could Eve trust anything Alice decrypted?)

(Of course, if Alice for some reason has to hand over $m_1$ and $r$, there is no hope. I took the example from this paper.)

X3DH doesn't allow Alice and Bob to prove that they had a particular conversation; their messages are deniable. But: if Eve forces Alice and Bob to hand over private keys, Eve can generate conversations that appear to have come from Alice and Bob.

Compromise of Prekeys

Recall the formulas used to derive the secret key from the prekeys:

DH1 = DH(IK_A, SPK_B)
DH2 = DH(EK_A, IK_B)
DH3 = DH(EK_A, SPK_B)
SK = KDF(DH1 || DH2 || DH3)

If I have access to the prekeys, I can try to calculate DH1,DH2, and DH3 (although I think this is hard without the ephemeral and identity keys) and carry out key-compromise impersonation attacks; see this informal overview. Basically, I can compute the shared secret if I have a secret key SK and impersonate someone in a conversation. This is why the protocol suggests periodically uploading prekeys to the server, since these attacks are invalidated (the secret key depends on the prekey).