Proving von Neumann extractor correct Von Neumann extractor works as follows:

  Suppose $C$ is a biased coin, with $p = P[C = 1] > P[C = 0]$ and let $b_1b_2\ldots$ be sequence of results by independent coin tosses. For $i \ge 0$ one observes $b_{2i}b_{2i+1}$. If the two bits differ then one takes $b_i'$ to be the first bit. Otherwise,one takes $b_i' = \epsilon$ the empty word.

I would like to prove that in the sequence $b_1'b_2'\ldots$, bits are uniformly distributed. This would show that this mechanism is a real randomness extractor.

My approach

I applied the total law of probability in this way (please let me know how can I properly write this equation in latex):

$P[b_i' = 1] = P[b_{2i}b_{2i+1} = 01] P[b_i'= 1 : b_{2i}b_{2i+1} = 01] +$

$P[b_{2i}b_{2i+1} = 10] P[b_i'= 1 : b_{2i}b_{2i+1} = 10] +$

$P[b_{2i}b_{2i+1} \neq 01,10] P[b_i'= 1 : b_{2i}b_{2i+1} \neq 01,10] = p (1-p)$

The result is the same for $P[b_i' = 0]$.

However, then $p$ cannot be arbitrary right? Because I would need $2p(1-p) = 1$. Otherwise I have to compute the probability of $b_i' = \epsilon$, but this does not make sense because the $\epsilon$ won't appear in the final string.

How can I formally finish this situation?

What you need to show is that the output bits are i.i.d. and uniform.

Given there is an output bit, clearly the probability that you output a zero is the same as the probability that you output a one, namely $p(1-p)$ as you indicated. So uniformity is settled.

These bits are also independent since they depend on disjoint subsequences of the input stream, which is itself assumed to be i.i.d, though non uniform.

So all you still need to prove is that bits are output at some nonzero  rate. This rate is $2p(1-p)$ per two input bits and is positive provided $p \in (0,1)$ which is the case of a non degenerate source.


What is the correct way to implement PBKDF2 + AES CBC + HMAC? I've been doing a lot of reading on the proper way to implement AES CBC mode with HMAC authentication. I've seen many explanations, however, I've had a hard time finding an actual real example (with code) on all steps including key derivation, encryption, and decryption. My application uses PBKDF2 for key derivation. Here is what I have so far:

Derive Keys

Generate 256 bits of "key material" with KDF

key_material = pbkdf2(user_password, salt, iterations, size:256, alg:sha256)

Split key material in half yielding x2 128 bit keys for encryption and signing

enc_key = key_material.split(0, 127)
mac_key = key_material.split(128, 255)

Encrypt

Generate 128 bit initialization vector

iv = secureRandomBits(128)

Do AES encrypt

cipher = aesEncrypt(plaintext, iv, mode:cbc, key:enc_key)

Compute MAC with concatenated IV and cipher bits

mac = hmac(iv + cipher, alg:sha256, key:mac_key)

Store resulting values to server (considered unsecure storage)

storeValuesToServer(cipher, iv, mac)

Decrypt

Fetch data from storage

cipher, iv, mac = getValuesFromServer()

Recompute mac

new_mac = hmac(iv + cipher, alg:sha256, key:mac_key)

Compare macs

if(mac != new_mac)
  throw 'Failed MAC check!'

Do AES decrypt

plaintext = aesDecrypt(cipher, iv, mode:cbc, key:enc_key)

Questions

Does this look correct? Main concerns here are:

Have I derived the keys correctly, splitting them in half based on the output of the KDF?
Am I computing the HMAC correctly by combining the iv + cipher. Does it matter if I had done cipher + iv instead?

You'll find there's a lot of splitting hairs regarding this topic, especially key derivation. But yes, your pseudocode is fine, although you may want to revise (0, 128) => (0, 127) and (129, 256) => (128, 255) ... (correct me if I'm wrong?). Also, you might want to implement a constant-time comparison function for verifying the mac.

  Have I derived the keys correctly, splitting them in half based on the
  output of the KDF?

This is fine. Some people would disagree. See here here and here for more in-depth discussion.

  Am I computing the HMAC correctly by combining the iv + cipher. Does
  it matter if I had done cipher + iv instead?

Yes, you're computing the HMAC correctly. No, the order of cipher + iv does not matter at all. If it's available to you, you might want to consider a mode like GCM, which takes care of encryption and authentication for you with a single key.


ElGamal cipher decryption (reposted not from guest account) My sincerest apologies for having to repost this but I can't edit or post a comment from the previous one I asked with a guest account.

I'm learning about the Diffie-Hellman and ElGamal ciphers, but I'm really struggling trying to decipher the exercise my lecturer has given me.

The information I've been given (all in decimals) is

g

p

a (Alice private key)

A (Alice public key)

B (Bob public key)

C (ciphertext)

I've tried calculating a shared secret S = B^a mod p then inversing it and multiplying that by C as my lecturer described in the lecture but it doesn't work. Is that wrong and if yes what am I supposed to do??

I used this tool to perform the inverse operation (inverseMod(a,b))
http://www.mobilefish.com/services/big_number_equation/big_number_equation.php

You need to further specify your question. The Diffie-Hellmann Key Exchange Protocol is used to establish a secret key over a public channel. After the protocol run, both Alice and Bob have the same key $k_{ab}=A^b=B^a=g^{ab}$.

The El-Gamal system is based on asymmetric cryptography and therefore public keys and secret keys are required. Since the El-Gamal ciphertext consists of two parts $c=(c_1,c_2)$ your description of the decryption function seems to be mixed up. Have a look at the decryption formula of El-Gamal and try to calculate it step by step to understand how the cipher works.


Is Bouncycastle RSA+OAEP implementation vulnerable to Manger’s attack? I have written a code to encrypt a plaintext as below. Here I am using bouncycastle crypto provider and referring to the RSA+OAEP for that.

public static void main(String [] args) throws Exception {
    Security.insertProviderAt(new BouncyCastleProvider(), 1);
    String ciphertext = Base64.encode(encrypt(plaintext));
    String recoveredPlaintext = decrypt(Base64.decode(ciphertext));
}

private static byte [] encrypt(String plaintext) throws Exception {
    KeyStore keyStore = getKeyStore();
    Certificate[] certs = keyStore.getCertificateChain("oaep");
    Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPwithSHA1andMGF1Padding","BC");
    cipher.init(Cipher.ENCRYPT_MODE, certs[0].getPublicKey());
    return cipher.doFinal(plaintext.getBytes());
}

private static String decrypt(byte [] ciphertext) throws Exception {
    KeyStore keyStore = getKeyStore();
    PrivateKey privateKey = (PrivateKey) keyStore.getKey("oaep",
            "oaep".toCharArray());
    Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPwithSHA1andMGF1Padding","BC");
    cipher.init(Cipher.DECRYPT_MODE, privateKey);
    byte[] cipherbyte=cipher.doFinal(ciphertext);
    return new String(cipherbyte);
}

When I am googling I stumbled upon this blog post; which says that the RSA+OAEP is vulnerable to “Manger’s attack”.

I wanted to know whether my code is effected with this vulnerability, if so how can I check that?
There are several PKCS#1 versions. Which version's implementation has been used in the bouncycastle and how can I get to know the exact version (2.0,2.1,2.2) of PKCS# 1?

Bouncy Castle Java releases 1.60 and FIPS 1.0.1 (and former) have precisely the issue exploited in Manger's attack: an exception occurs when a ciphertext $c$ is submitted such that $c^d\bmod N$, expressed as a bytetring as wide as $N$, does not start with a 0x00 byte; and then the rest of the decryption process does not occur, leading to markedly faster execution. If an adversary can iteratively submit a few thousands messages for decryption and detect the exception or the faster execution, s/he can decipher a ciphertext, or make a signature. The private key itself does not leak.

Pre-release version 1.61b03 (available here, also on GitHub) has a fix that removes the unwanted exception, and reduces timing variation by orders of magnitude. If it remains vulnerable, that could only be with precise and repeated timing by an attacker.

Manger's attack and countermeasures in later editions of PKCS#1v2

The attack is exposed in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001). It exploits an RSA decryption system that leaks a little information about $y=x^d\bmod N$ for $x$ repeatedly chosen by an attacker.

The applied part of the attack focuses on the leak of if $y<2^{8k-8}$ with $N$ of $8k-7$ to $8k$ bit; or equivalently: does $y$ start with a 0x00 byte when expressed as a big-endian bytestring of $k$ bytes, as it should in RSAES-OAEP padding:

In PKCS#1 v2 7.1.2 (Decryption operation) step 4, that 0x00 is verified thru the use of "length $k-1$" in:

  Convert the message representative $m$ to an encoded message $\text{EM}$ of length $k-1$ octets: $\text{EM}=\text{I2OSP}(m,k-1)$
  If I2OSP outputs "integer too large," then output "decryption error" and stop.

PKCS#1v2 has a note stating that the above "decryption error" must be identical to one that can occur on failure of another redundancy check made after OAEP's masking is undone.

Manger observed that not all implementations do this properly; and those that do as instructed take less time when that test fails (due to the stop, the rest of the rest of the procedure is not performed, saving time), thus timing can reveal the desired bit of information.

This is addressed in PKCS#1 v2.1 (and PKCS#1 v2.2, identical in this regard) by using $\text{I2OSP}(m,k)$ without the $-1$, which outputs an extra additional byte $Y$ and never triggers an error. $Y$ is tested in the end, together with other redundancy criteria applying to the message after OAEP unmasking.

  If there is no octet with hexadecimal value 0x01 to separate $\text{PS}$ from $M$, if $\text{lHash}$ does not equal $\text{lHash’}$, or if $Y$ is nonzero, output "decryption error" and stop.
  Note. Care must be taken to ensure that an opponent cannot distinguish the different error conditions in (the above), whether by error message or timing, or, more generally, learn partial information about the encoded message EM. Otherwise an opponent may be able to obtain useful information about the decryption of the ciphertext, leading to a chosen-ciphertext attack such as the one observed by Manger.

All versions of RSAES-OAEP in PKCS#1v2.0, 2.1 and 2.2 are interoperable, and the procedures described lead to identical results, except that their timing variation is less likely to leak information in 2.1 and later.

Bouncy Castle's code

In Bouncy Castle's version 1.60 (current when the question was asked and this answer first drafted) the code specific to RSAES-OAPEP decryption is decodeBlock in OAEPEncoding.java. That contains

    byte[]  data = engine.processBlock(in, inOff, inLen);
    byte[]  block = new byte[engine.getOutputBlockSize()];
    // as we may have zeros in our leading bytes for the block we produced
    // on encryption, we need to make sure our decrypted block comes back
    // the same size.
    System.arraycopy(data, 0, block, block.length - data.length, data.length);

The definition of engine is such that processBlock returns data with leading zero bytes suppressed, and getOutputBlockSize returns $k-1$ when $N$ is $k$-byte. It follows that block.length - data.length is $-1$ when $(c^d\bmod N)\ge2^{8k-8}$, and then System.arraycopy makes an ArrayIndexOutOfBoundsException not locally caught nor listed in those that the caller is invited to expect, and that the rest of the function is not executed.


Mixing Entropy Sources by XOR? Assume that I have two sources of entropy (say, a hardware RNG and a CSPRNG) and that the two sources are independent (do not know anything about the internal state of the other RNG).  Can I mix them by XORing blocks safely?  If one of the two has been compromised/subverted, is there any way it can reduce the total entropy of the other source?

The answer here seems to imply this is possible, but does not specifically address the case of one of the two being subverted.

I'm aware of entropy mixing via hashes, but I'm wondering about something with less overhead.

(In case anyone's wondering, I'm not actually implementing an entropy pool, just settling a debate at work.)

If one source remains uncompromised plus statistically random on all bits, and both sources remain independent, then a xor of both sources together can also be  considered uncompromised plus statistically random for all bits.

Basic proof:

Label the the results two RNGs $X$ and $Y$, consider bits $X_n$, $Y_n$ and $Z_n = X_n \oplus Y_n$

Assume each value of $X$ remains uncompromised, such that $p(X_n=1) = 0.5$, and that each value of $Y$ is compromised so that $p(Y_n=1) = w$, the following holds assuming $X$ and $Y$ are independent:

$p(Z_n=1) = p(X_n=1) * p(Y_n=0) + p(X_n=0) * p(Y_n=1)$

$ = 0.5 * (1.0-w) + 0.5 * w$

$ = 0.5$

In other words, each bit of $Z$ retains the same probabilities and qualities of $X$, if $X$ is from a good RNG, then $Y$ can then be anything at all (provided it is independent of X). This holds even if $p(Y_n=1)$ is not independent of $p(Y_m=1)$, because whatever distribution you provide for $Y$, it just cancels out as above.

Knowing the exact value of $Y$ is just a special case of the above where $p(Y_n=1)$ is either 0 or 1 for each $n$. It doesn't grant any knowledge about $Z$, because each bit of $Z$ remains independent from each other bit of $Z$ and an attacker still only knows $p(Z_n=1) = 0.5$

Using a secure hash-based mixing method might allow you to relax the requirement for independence between the RNGs.

Entropy mixing with secure hashes can also be used to flatten distributions from sources which are not flat e.g. event timing data. You generally don't have that problem when the sources you are considering are well-written RNGs in the first place.


RSA-KEM: minimal number of random bits I've already asked a few - as yet officially unanswered - questions about RSA-KEM with regards to the input secret encrypted using the public key here and (less on topic for this question) here.

CodesInChaos already commented in the first question linked to. It seems logical that having the most significant bit set to zero during generation of the random value $z$ to not impact security all that much.

Still, the use of random number generators for large amounts of data can be a draw back of the mode of operation, especially when they are required to generate  4096 bits of randomness for a single RSA operation. This could be an issue if said random number generator is slow or if insufficient entropy is available to the random number generator.

My related questions are:

Can we reduce the amount of input keying material to the KDF further without reducing the security of the RSA operation? If yes, by how much?
If yes, is there a good distribution of random bits required (half to the left, half to the right?)
If no, could we use a one-way primitive such as a XOF or indeed MGF-1 after retrieving the required number of bits for secure key derivation, and feed that to RSA-KEM?

Or should I just run away and use RSA OAEP instead if I run into situations where a fast DRBG is not available?

Theoretical concern.
The standard security reduction of RSA-KEM to the RSA problem relies on the ability of the decryption oracle to handle most of the input space.  If you don't feed all the bits into the KDF, or if you treat some inputs equivalently, you may shoot yourself in the foot, like failure to verify lHash in OAEP.

Practical concern.
If you don't generate all of the bits of the element $x \in \mathbb Z/n\mathbb Z$ from which you derive a key $k = H(x)$, even if you spread them out so that the standard real number cube root attack doesn't work on exponent $e = 3$, you may nevertheless be walking headfirst into the Franklin–Reiter related-message attack, which applies even to exponent $e = 65537$ that everyone quietly accepts without the PTSD over $e = 3$ left from the dark ages of cryptography engineering in the '90s.

Performance concern.
It costs at best about 20k cycles on a modern AMD CPU to compute $x^3 \bmod n$ for 2048-bit $n$—the faster half of RSA with the fastest exponent; any other exponent is slower (except perhaps in Rabin territory), and decryption is much slower.  It costs at worst about 1k cycles to generate 2048 bits with Salsa20 using naive C code, and that's about the easiest option, not the cheapest option.

OAEP also needs to generate about $\lg n$ bits of data, but usually with a much more expensive PRNG (‘MGF’), such as SHA-256.  Under what circumstances could the generation of $x$ be a bottleneck, but not the MGF computation of OAEP?


Faster discrete Gaussian sampling Our goal is find a faster discrete Gaussian sampling to solve $"SVP"$ problem in lattice:

A lattice is discrete subgroup of $R^n$ such that define as below:

let $\{b_1,\cdots ,b_n\}$ be a basis in $R^n$. Then $L:=\{a_1b_1+\cdots+a_nb_n | a_i \in Z\}$ is a lattice.

Shortest vector problem in $L$ is:

$SVP(L)$ = shortest non-zero $y\in L$.

This is a $NP-hard$ problem to solve. The best algorithm to improve approximation of this problem mentioned by "Discrete Gaussian Sampling". In this method, the TIME and SPACE computed $2^{n+ o(n)}$. What is the faster  discrete Gaussian sampling?

Asymptotically, the fastest provable algorithm for SVP is based on discrete Gaussian sampling, achieving both time and space complexity $2^{n + o(n)}$ in dimension $n$. This algorithm finds a way to obtain samples from a discrete Gaussian on the lattice with a very narrow standard deviation, so that most of the probability mass is concentrated on short lattice vectors, and the probability mass on shortest vectors is sufficiently large that $2^{n + o(n)}$ samples from this distrubition suffice to find one shortest vector. The time to generate even a single sample from such a discrete Gaussian with small standard deviation is however already $2^{n + o(n)}$.

As for algorithms for "discrete Gaussian sampling", there are two different topics to consider here:

A discrete Gaussian with a large standard deviation is very "flat", has a lot of probability mass concentrated around vectors with huge norms, and therefore it turns out to be quite easy to sample from these distributions by first running LLL reduction and then running some polynomial-time sampling algorithm. These discrete Gaussians are commonly used in lattice-based cryptography, e.g. to sample a noise vector in Learning With Errors.
A discrete Gaussian with a small standard deviation is very narrow, has most of the mass concentrated around short lattice vectors, and therefore accurately sampling from these distributions (without some kind of trapdoor information about the lattice) is known to be hard.

What defines "small" and "large" above is related to what is commonly called the "smoothing parameter" (see e.g. here). Sampling "above smoothing" is usually considered "easy" while sampling "below smoothing" is "hard", if you have say an LLL-reduced basis of a lattice.

Note that in "practice", the DGS algorithm for SVP is much worse than enumeration-based approaches (see e.g. here), lattice sieving algorithms (see e.g. here), and BKZ-enumeration hybrids like random sampling reduction. Heuristics for instance suggest you can solve SVP in time and space less than $2^{0.3n + o(n)}$ with sieving, and in practice sieving has been used to solve SVP challenges in dimensions as high as 155.


Use partial hash to verify entire hash I've had an idea about storing parts of SHA256 hashes and I'd like to find out how secure it is, or how much less secure it is than storing the entire hash.

For example, users can share this list of truncated hashes and each user only stores one of the entire hashes, they only need to store they're own hash, and when someone gives them a hash they don't recognize they can check it against my list.

If I have some hashes like this:

CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB
3E23E8160039594A33894F6564E1B1348BBD7A0088D42C4ACB73EEAED59C009D
2E7D2C03A9507AE265ECF5B5356885A53393A2029D241394997265A1A25AEFC6
etc ...

Instead of storing all 256 bits of each hash, I'd like to store random chunks of each hash. The first step is to add a number to the end of the hash.

CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB(4)
3E23E8160039594A33894F6564E1B1348BBD7A0088D42C4ACB73EEAED59C009D(7)
2E7D2C03A9507AE265ECF5B5356885A53393A2029D241394997265A1A25AEFC6(9)

And now instead of storing the entire hash, I store two bytes from each hash. The first byte is byte 4 for the first hash, 7 for the second etc ... using the number I added to the end of the hash.

The first number is the 4th byte.
The second number is (first number + half size of the entire hash) % (size of the entire hash).

So based on my first hash above:

CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB(4)
byte1 = 4th byte = 12
byte2 = (4 + 32/2) % 32 = 20th byte = F8

So instead of storing:

CA978112CA1BBDCAFAC231B39A23DC4DA786EFF8147C4E72B9807785AFEE48BB(4)

I could store:

12F8(4)

So now I have my hash and if I want to compare it against the list I just check the 4th and 20th bytes equal 12 and F8, respectively.

I don't know anything about Cryptography really, so I'm wondering if this idea already exists, if it's secure and if there's a way prove mathematically how secure only storing 8 bits of the 256bit hash is as opposed to storing the entire thing.

Thanks!

If I understood correctly, instead of storing the full hash value, you just store 2-byte. As always, we assume that the attacker has the random chunk information, too.

It will be very easy to find a collision since your truncated hash contains only $2$-byte $= 16$-bit. By the birthday attack on hash functions, the attacker only needs to try $\sqrt{2^{16}}= 2^8 = 256$ different files to has a collision with 50% probability.

You can also see this questions and answers for truncated hash values;

What are the consequences of removing a single byte from a sha256 hash?
Is truncating a SHA512 hash to the first 160 bits as secure as using SHA1?


In CBC mode of encryption, what happen if the IV is changed when it arrives at the receiver end? What will happen if the Initialiazation Vector (IV), i.e, the initial randomness fed in to
the first block arrives mangled at receiver end? How will this affect the decryption? Will the receiver be
abl to decrypt all blocks correctly? Or none? Or some?

For the first block, assuming the noise in the IV is not much, it may be possible to recover part of the plaintext. Say, only one bit of the IV is flipped. In this case, all but one bit (of the first block of) plaintext can be recovered, as the with usual notations $C=E_K(P\oplus IV \oplus e)$, $e$ is a vector of small Hamming weight. By decrypting $C$, Bob gets $P\oplus IV \oplus e$. By the perceived knowledge of $IV$ all but those bits are affected by $e$ can be recovered (but you need to know which bits of the IV are vulernable, otherwise, the plaintext is lost).
For all the subsequent blocks, it will not be possible anymore. Even if $e$ is Hamming weight $1$, assuming the cipher is strong enough, it will make the first block of ciphertext look totally random. When this is fed to the next block, it will produce completely off ciphertext blocks.


Is more ECDHE or RSA currently recommended? Lately I have seen that many websites warn us of changing RSA for ECDH, and that the latter is much better if we use its "ephemeral" form or better known as ECDHE.

So is ECDHE recommended to use more over other algorithms today?

It is not fully clear what you are talking about - "many websites warn us" is a bit too short on detail. But usually this topic comes up when talking about TLS (as used in HTTPS) and here comparing RSA and ECDHE  means to compare the different methods of key exchange offered by TLS. Note that key exchange is not encryption  - it is instead the method to determine the common key which is later used for encryption.

And yes, ECDHE is clearly the preferred key exchange since it provides forward secrecy which can greatly limit the impact of a successful attack. With forward secrecy an attacker cannot decrypt previously sniffed traffic while without forward secrecy this might be possible. For more details see What guarantees does perfect forward secrecy make with respect to compromise of a private key? and Wikipedia:Forward secrecy.


how to let other people respond to emails only decrypt-able with my private key First of all I have to say it's a homework question but since I have no one to consult with, I ended up here :)

Suppose a case in which you are the manager of a company and all employees encrypt their messages with your public key and send them to you.You can decrypt them with your private key and read them.

Now suppose you're leaving for a vacation and want your secretary to be able to read the emails but you don't want her to have your private key.

How would you go at solving this issue?

Any hint or suggestion is greatly appreciated :)

You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator $A$ gives a special re-encryption key $rk_{A \rightarrow B}$ to the proxy; this key makes the transformation from $A$ to $B$ possible. So, besides defining traditional encryption and decryption functions, a proxy re-encryption scheme also defines a re-encryption function for executing the transformation.

Your example is one of the traditional use cases of proxy re-encryption. See for instance the introduction of this paper from Ateniese et al. In this case, the manager $A$ creates a re-encryption key $rk_{A \rightarrow B}$  for her secretary $B$, and handles this re-encryption key to the email server. The server simply has to re-encrypt all encrypted emails under the public key of $A$ to encrypted emails under the public key of $B$.

Udpate: For the sake of clarity, I provide here an example of Proxy Re-Encryption scheme. The following is one of the simplest schemes, proposed by Blaze, Bleumer and Strauss in 1998. It is based on the ElGamal encryption scheme. Besides to the usual primitives for key generation, encryption and decryption, the scheme has a re-encryption key generation function and a re-encryption function:

$KeyGen() = (pk = g^x, sk = x)$, for random $x$.

$Enc(pk = g^x,m) = (pk^r, m\cdot g^r) = (g^{xr}, m\cdot g^r)$, for random $r$

$Dec(sk = x, c = (c_1, c_2)) = c_2 / c_1^\frac{1}{sk}$

$ReKeyGen(sk_1 = x, sk_2 = y ) = sk_2 / sk_1 = y / x$

$ReEnc(rk = y/x, c = (c_1, c_2)) = (c_1^{rk}, c_2) = (g^{yr}, m\cdot g^r)$

Note that this scheme is what the proxy re-encryption literature calls "interactive", that is, the re-encryption key generation needs both secret keys as inputs. This is an undesired property, but I preferred to show this scheme because of its simplicity. There are however plenty of non-interactive proxy re-encryption schemes (the re-encryption key is generated from the secret key of the delegator and the public key of the delegatee) such as the ones from Ateniese et al. (see link above).


Semantic Security and Equal Message Length in the Context of Public Key Cryptography A lot of definitions for semantic security make use an experiment $\text{Exp}$ which is performed between a challenger $\mathcal{C}$ and an adversary $\mathcal{A}$ that begins as follows:

$\mathcal{C}$ generates a random key w.r.t. the considered cryptosystem and a given security parameter. $\mathcal{A}$ selects two messages $m_0$ and $m_1$ of the same bit length (i.e., $|m_0| = |m_1|$) and sends $m_0$ and $m_1$ to the adversary (and so on).

Now, assume that the considered cryptosystem is a public key cryptosystem. In $\text{Exp}$, $\mathcal{C}$ randomly chooses a public/private key pair $(sk,pk)$. Assume that the public key $pk$ is given to $\mathcal{A}$. Let $\mathbb{P}$ be the message space determined by $pk$.

The question is whether—for the given setting—$\text{Exp}$ remains valid if $\mathcal{A}$ chooses arbitrary plaintexts $m_0$, $m_1$ from $\mathbb{P}$ or, otherwise, is it still necessary that $|m_0| = |m_1|$ for $m_0,m_1 \in \mathbb{P}$ holds?

There are two styles of definition that deal with the issue of message "length" in different ways.

One style considers an encryption algorithm that is capable of encrypting bit strings of arbitrary length.  Such an algorithm cannot completely hide the message length, for information-theoretic reasons.  (Padding short messages to conceal their lengths doesn't overcome the problem; however much padding the algorithm uses, there are always longer messages that cannot fit into the same total length.)  Therefore, in this context a definition of security should require that the adversary produce two messages of the same bit length.

A second style considers an encryption algorithm that is only well defined for messages that come from some finite "message space," which may depend on the security parameter or even the public key.  For such algorithms, there's no inherent problem with message length, because all valid messages have a bounded "length" (or representation).  In this context, the security definition need not require that the adversary's messages are of equal length; it should only require that the messages are both valid, i.e., that they belong to the message space.  (If one message was invalid, the adversary could easily distinguish the two experiments because encryption fails in one and succeeds in the other.)

There are many examples of encryption schemes that fit into the second framework.  Symmetric encryption of fixed-length messages using a (fixed output length) PRF is one.  "Algebraic" cryptosystems like ElGamal or RSA, where the message space is some finite group $G$ or $\mathbb{Z}_n^*$ (respectively), are another.  Systems like Goldwasser-Micali, where the message space is just $\{0,1\}$, are further examples.


Pseudo-Hadamard transform, most significant bit For clarification: The Pseudo-Hadamard transformation is a reversible transformation of a bit string that provides cryptographic diffusion.
Splitting a bit string (with bit length of $2n$) into two equally large bit strings $a$ and $b$ with size $n$:

\begin{align}
a' &= a + b & \pmod{2^n}\\
b' &= a + 2b& \pmod{2^n}
\end{align}
Reverse:
\begin{align}
b &=b' - a' & \pmod{2^n}\\
a &= 2a' - b' & \pmod{2^n}
\end{align}

(Source: Wikipedia: Pseudo-Hadamard transform)

What about the most significant bit (the most right bit) of $b$ in $b'$? Multiplication with $2$ and $\mod{2^n}$ cut this off. We lose any possible diffusion of this bit in $b$. That can't be good. Especially SAFER K and SAFER SK are heavily relying on the pseudo-hadamard transformation, see SAFER at Wikipedia.

My first question:
How does this affect the whole security of a cypher with this transformation? Is there a know attack on SAFER which exploits this characteristic?

My second question:
How can we fix this? Is there any public solution for this problem? Maybe we can replace the multiplication? I did try something with a left rotation of 1, but that combination doesn't work. Either this doesn't work in general, or I just don't know the "other secret key" to reverse the transformation with rotation instead of multiplication:

\begin{align}
a' &= a + b & \pmod{2^n}\\
b' &= a + rotL(b, 1)& \pmod{2^n}
\end{align}

Reverse:  (Warning, wrong equation)
\begin{align}
b &= b' - a' & \pmod{2^n}\\
a &= rotL(a', 1) - b' & \pmod{2^n}
\end{align}

The Pseudo-Hadamard Transform on $n$-bit integers $a$ and $b$ is defined as

$$\begin{align}
a^\prime &= a + b &\pmod {2^n}\\
b^\prime &= a + 2b &\pmod {2^n}
\end{align}$$

It is true that the most significant bit (MSB) of $b^\prime$ does not depend on the MSB of $b$. Whether or not this is a problem depends on exactly how it is used in the cipher. While I'm not aware of whether or not this makes any attacks possible on SAFER, Twofish, which also uses the PHT, considers this to be a non-issue. While the MSB is indeed lost, the reduction of security is insignificant, and any measures used to preserve the bit are not worth the performance impacts. From section 7.8 of the Twofish paper:

  The two outputs of the $g$ functions ($T_0$ and $T_1$) are then combined using a PHT so that both of them will affect both 32-bit Feistel XOR quantities. The half of the PHT involving the quantity $T_0 + 2T_1$ will lose the most significant bit of $T_1$ due to the multiply by two. This bit could be regained using some extra operations, but the software performance would be significantly decreased, with very little apparent cryptographic benefit. In general, the most significant byte of this PHT output will still have a non-zero output difference with probability $254/255$ over all 1-bit input differences.


Can you use the same key to provide a signature and a MAC? Apologies if this is a stupid question, but I'd be grateful if someone could provide an answer. I'm assuming that you need to use different keys to provide these functions, is that correct?

The usual meaning of signature (in cryptography) is this:

Bob has a pair of keys, a public and a private one. The public one is known to Alice, too. (And to any possible attackers, too.)
Bob wants to send a message to Alice.
Bob does some operation with the message and his private key (he signs the message), and obtains a signature.
Bob sends message and signature to Alice.
Alice does some operation with message, signature and the public key and can verify these fit together, i.e. that the message really was signed by Bob.

The usual meaning of a MAC (message authentication code) is this:

Bob and Alice have a shared secret key.
Bob wants to send a message to Alice.
Bob does some operation with the message and the secret key, and obtains a MAC.
Bob sends message and MAC to Alice.
Alice does some operation with message, MAC and the secret key and can verify these fit together, i.e. that the message really was sent by Bob. (Actually, as she knows the key, too, she can only verify that "the message was sent by Bob or Alice", and has to know by some other means that this was not her own message.)

How could they use the same key to produce a MAC and a signature? We could use one of the signature keys for the MAC:

If this would be Bob's private key, Alice would need to know it too for verification, and then it wouldn't be private anymore. (And Bob would be able to forge Alice's signatures, too.)
If they used the public key, then anyone knowing it would be able to forge the MAC.

Both are not good ideas, normally.

There might be a way to do something similar, though. For example, if both Alice and Bob have a key pair, they might be able to calculate a shared secret from both (e.g. using the Diffie-Hellman key exchange if these are discrete-log-type key pairs), and use this shared result for a MAC. At the same time, Bob might use his private key to sign the message.


Do Cryptographic Hashing Algorithms operate only on Integers? Do all the Cryptographic hashing algorithms operate only on integers (32 bit or 64 bit)? Is there any operation performed on Floating Point Numbers as well?

The reason I ask this is because I read here that there are no floating point calculations performed in hashing algorithms and hence FLOPS do not matter:

http://www.golubev.com/about_cpu_and_gpu_2_en.htm

Mostly yes: usual cryptographic operations, including hashes, are defined using operations on integers and bit vectors, not Floating Point Numbers.

I think the  main reason is that in cryptography, we need different computers (e.g. the one that hashes a file to protect its integrity, and the one that verifies the integrity) to get the exact same result, and that is hard to ascertain for Floating Point operations.

Historically, computers used different format and precision for representing Floating Point numbers, and that would cause huge portability problems.

Nowadays virtually every recent CPU with FP support (which is only a tiny fraction of the CPUs manufactured) can use at least one of the 32-bit, 64-bit or 128-bit format of IEEE 754, so this is slightly less a concern than it was. But still, many computer languages and dialects give no way to precisely control rounding, or to efficiently convert arbitrary information as found in a generic file into FP format and back. It remains a mess to even get exactly the same result for FP addition on two machines programmed in different languages. Further, I would not bet that the same program using 128-bit arithmetic allays gives the same result on two different x86 PCs with built-in FPU when even multiplication is involved, much less division (maybe some designs differ by one LSbit in some edge case). Notoriously the result for transcendentals (e.g. $\sin$) differ.

There are a few uses of FP in the implementation of some cryptographic algorithms, or even hashes. I have seen an implementation of MD5 using 80-bit FP for accumulating the length of the input, to workaround the lack of 64-bit integer variables. It is not unusual that an implementation of multiple-precison integer arithmetic uses FP, more or less extensively.

An example where FP is put to heavy use in something reminiscent of a hash is Poly1305-AES for generic computers with IEEE floating point; that's a message authentication code which can be turned into a hash by making the key a public constant. Notice the caveat that it will not work on x86 computers running Linux, because GCC (at least, historically) did not support the required FP format.


Just how insecure are VeraCrypt containers encrypted with short passwords? When I create a VeraCrypt file container using the GUI, it displays a warning whenever I type in a password under a given number of characters. I was wondering just how insecure, in practical terms, such a method of encryption really is.

To give a concrete example, suppose:

I have a 4 GB VeraCrypt-generated container on a USB drive.
The password for said container consists of 9 lower case letters, from the standard English 26 letter alphabet.
Within said container are a dozen or so files, ranging from a few bytes to a few hundred megabytes in size.
The USB drive in question falls into the hands of a party hostile to me.
Other than the contents of the USB drive described above, this hostile party has no knowledge of how the container is encrypted.

How much trouble will that hostile party have in decrypting my container? Could an intelligent and motivated, but otherwise quite ordinary, programmer with a mid-range laptop do it, or would he have to call in the CIA, etc?

9 lower case letters with standard English alphabet make around 40-bit direct search this is very low password entropy. This is quite achievable even you use high iteration numbers like 200000 iterations for the HMAC-SHA-256. 200000 makes $\approx 2^{18}$ so in total $\approx 2^{58}$

Even public laboratories in the USA, like Oak Ridge Summit,  can achieve this;

The super computer Summit can reach $\approx 2^{63}$ SHA-1 hashes around one hour, $\approx 2^{72}$ hashes in one year.

Actually there are two recommendations for you

Use diceware based passwords. EFF has a very decent page about this. This is a very good method to generate strong passwords that one can easily remember. With 8 words one can reach the 96 bits password entropy. A small list;

7 words have 80 bits
8 words have 96 bits
9 words have 128 bits password entropy.

Use the hidden volume in VeraCrypt. The hidden volume is created under a VeraCrypt volume that is indistinguishable from the free space of VeraCrypt volume since the free space in VeraCrypt is random, not zero, or FF. Keep in mind that, you must use a different password for this hidden volume.

An important aspect of the hidden volume is the plausible deniability. One can give the key of the outer VeraCrypt volume as honesty and keep the hidden volume key for themself. Since the hidden volume is indistinguishable from the free space it is not noticeable.

Note that as pointed by Mark, a forensic analysis can reveal the hidden volume. It is not perfect yet.


Why is ECIES complex? Wouldn't encrypting a message with AES, then encrypting the (randomly generated) AES key and IV with the EC public key suffice?

What attack vectors does ECIES protect against, that an AES-then-EC-encrypt wouldn't?

Wouldn't encrypting a message with AES, then encrypting the (randomly
  generated) AES key and IV with the EC public key suffice?

Yes it would suffice and is what is usually done. However for this to work you'd have to have a way to reliably convert a random integer to a curve point and back which isn't trivially possible. And even if you could reliably encode the key to be a curve point you may be vulnerable to some attacks using collision properties resulting in a much smaller security margin than expected, much like encrypting "small" values with RSA.

This is why ECIES randomly chooses a curve point, encrypts this one and uses the secret point to derive keys.

  What attack vectors does ECIES protect against, that an AES-then-EC-encrypt wouldn't?

ECIES provides chosen ciphertext security meaning it provides security against most known attacks. Simple AES-then-EC-encrypt may not be secure against such attacks if you don't do authentication of the plaintext. If you'd use something like AES-GCM with the above mechanism to encapsulate the keys you're pretty much at ECIES although ECIES uses its KDF to derive the keystream and uses HMAC to authenticate the ciphertext.


PRF from hash function? Let $G=\langle g \rangle$ be a cyclic group of prime order $Q$. Let $H_1:\{0,1\}^*\to G$ be a hash function. Is the following a family of PRF for $s \in \mathbb{Z}_Q^*$?

$$f_s(x)=(H_1(x))^s$$

Or equivalently, let $H_2:\{0,1\}^*\to \mathbb{Z}^*_Q$ be a hash function,

$$f_s(x)=(g^{H_2(x)})^s$$

Intuitively it is in ROM, but can somebody prove it?

The first construction is a well-known PRF in the random oracle model, with security from DDH. I can't find a good reference right now where this construction is explicitly framed as a PRF, but I will update if I find it.

Edit: this is the PRF that is implicit in private set intersection protocols dating back to:
Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986
Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

The second construction is insecure. If I know $f_s(x)$, then I can raise this value to the $H_2(y)/H_2(x)$ power (inversion is mod $Q$) and this tells me $f_s(y)$. So I can easily distinguish $f_s(y)$ from random.
BTW, in the random oracle model, $f_s(x) = H(s,x)$ is a PRF, as is $f_s(x) = g^{H(s,x)}$.


Is there an encryption/decryption algorithm that can give two different outputs? The recent revelations that airport staff can detain travellers in an interrogation room and force them to give over passwords to encrypted-HDD laptops under threat of jail time has made me think about some sort of dual password encryption/decryption mechanism.

For example:

Password 1 decrypts all the data as usual.
Password 2 decrypts most of the data, leaving a portion looking like random 0's and 1's.

I think it has to work at the algorithm level, and not rely on software, because the HDD could be removed from the laptop and then any software protection is useless.

My question is, are there any algorithms that can give two different (but similar) results depending on which key is used?

It looks like you might be interested in applying
 Deniable Encryption.

The general idea of this kind of encryption is that you can decrypt the data to produce a different (but still plausible) plaintext. In this way, the airport staff or whoever is asking you to decrypt the data, would by no means differentiate between the real plaintext and the alternative one.
I suggest to have a look a this paper.


Am I understanding AES key padding correctly? I’ld like to ensure I understand AES key padding correctly…

Is the initial AES key (expanded to the key schedule) byte padded if less than e.g. 16 bytes?
Is there a safe way of determining if decryption was successful (meaning: that the correct key has been used
)?

AES by definition takes 16, 24 or 32 bytes as key, and nothing else. If you have a different size input use some kind of KDF to transform it to the correct length.

If that input is a password this step is even more important. You should a key strengthening construction, such as PBKDF2 with sufficient iterations and a salt.
If you use authenticated encryption, the verification of the authentication tag will fail if the key is incorrect. It's strongly recommended to use authenticated encryption. Not only will it tell you that the key is correct, it'll also prevent a variety of active attacks, such as padding oracles.

You can either use an authenticated mode, such as AES-GCM, or normal AES followed by HMAC (Encrypt then MAC).


Hard-core bits from RSA assumption I am trying to understand better the hard-core bit property from the RSA assumption. The paper by Håstad and Nåslund shows that every single bit is hard-core. By the result itself, two or more bits can be correlated, but marginally a single bit is pseudorandom.
Is it possible to extend the result to the parity of an arbitrary non-empty subset of bits? That is, for every non-empty subset $S$, is the parity of $x_S$ hard-core given $(e,N,x^e\mod N)$? If not, then what property $S$ has to hold to conclude the parity of $x_S$ is pseudorandom?

Here is a partial result:

Assume that we have a way, given $x^e \bmod N$, to derive the parity of $x_S$.  We further assume that $2 > N / 2^k > 1.5$ for some integer $k$, that is, the two msbits of $N$ is set (if the second msbit is clear, then a similar procedure will work, using the second msbit of $x$).

Then, to get a bit with a correlation to the msbit of $x$, we first derive the parity $x_S$.  Then, we compute $x^e \cdot 2^e = (2x)^e$, and then the parity of $2x_S$.

We then guess that the msbit is a 0 if $x_S = 2x_S$, and 1 if they differ.

Now, if the value $2x < N$, that is, if the doubling does not cause an overflow, then the parity $x_S$ will be the same as the parity of $2x_S$; if $2x > N$, then the doubling is really the computation $2x - N$, and the parity of that value will be uncorrelated with the parity of $x$.

Now, if the msbit of $x$ is a 0, that is, if $x < 2^k$, then the doubling will cause an overflow with probability $1 - N / 2^{k+1} < 0.25$, and hence our procedure will guess '0' over 75% of the time.  If the msbit is a 1, the doubling will always cause an overflow, and so our procedure will guess '1' 50 % of the time.

This gives a way to get the msbit in a probabilistic manner; the cited results show how that can be used to derive everything.

Note that this result is weaker than the original; we assumed that we have a error-free way of determining the parity of $x$; however the original result covered weakly probabilistic methods.  It might sound like this could easily be adapted to cover weakly probabilistic methods as well, however it is possible that the errors in determining the parities of $x_S$ and $2x_S$ might be correlated (which would invalidate this argument unless the errors were constrained to be fairly small)


hash functions preimage and second collision resistance A hash function H is secure in terms of pre-image resis-tance. Does this imply that H has second pre-image (aka weak collision) resistance?

No, the implication is wrong.
Pre-image resistance means that it is not possible to calculate a pre-image from the image alone.
But this does not exclude the existence of an algorithm, which calculates a second pre-image, given the image and the first pre-image.


Is SHA related to AES or TLS in any way I have been reading about SHA-2 family and I found a lot of in depth details, but I am confused about how it is related to TLS and AES. TLS encrypts data between server and client, but does it make use of SHA and for what, like what kind of data?

SHA is related to AES in that they are both US government standards. They are not similar algorithmically.

SHA and AES are cryptographic primitives, TLS is a protocol. As the name describes SHA is a family of hash algorithms. AES is a block cipher. TLS uses many encryption algorithms, including AES in various modes, and several hash algorithms, including those in the SHA family. TLS may also use encryption algorithms not based on a block cipher, such as RC4.

TLS uses hash algorithms in order to provide message authenticity when the encryption algorithm does not provide authenticated encryption, via HMAC. SHA may also be used during client-server key exchange to compute the shared master secret, as a component of some PRF, generally also HMAC. TLS encrypts passwords in transit between client and server using the selected encryption algorithm, which could be AES.

SHA is also used in server certificates in order to verify their authenticity so a TLS connection is not created to an imposter. Verification is apparently not implemented well in a wide variety of systems.

I would suggest reading RFC 5246 in order to get a better idea of how TLS operates.


How to solve the system of linear equations to recover original file using "Erasure Coding"? Following article explains a simplified version of Erasure Coding:

Link to the article

  here is the recipe:

  Take a file of size M.
  Split the file into k chunks, each of the same size M/k.
  Now, apply the (n, k) code on these k chunks to get n chunks, each of the same size M/k.
  Now the effective size is nM/k. Thus the file is expanded n/k times. We need n to be greater than or equal to k, so n/k is at least 1. If n equals k, you have just split the file and there is no coding performed.
  Any k chunks out of the n chunks can be used to get back the file.

  So this also means that the code can tolerate upto (n - k) erasures.
  The following figure shows this recipe being followed for a (4, 2)
  code.

  Without really wondering how do actually add files, the following
  example illustrates one particular case of designing a (4, 2) code.

  Lets say you have four computers (aka nodes) that you can use to store
  files. Instead of putting all the eggs in the same basket, you will want to
  spread it out and in this case, store the file twice by doing
  something like this:

  where X1 is the first block of file A and X2 the second. Another way
  is to store the coded blocks:

  Now if you lose nodes 1 and 3, in the case when you store uncoded
  blocks, X1 is lost permanently, so the file A gets corrupted. Whereas
  in the case when you store coded blocks, even when those two nodes
  fail, it is possible to recover X1 and X2 and thus A from A2 and A4.
  This is because A2 = X2 and A4 = X1 + 2*X2. So one can solve these
  equations and get back X1 and X2! Neat, isn’t it?

And my question is related to the last sentence:

How to solve these equations and get back X1 and X2 ?

We have two equations:

(1) A2 = X2
(2) A4 = X1 + 2*X2

AFAIK: We are able to solve an equation, if the number of equations is equal or more than the number of unknown variables.

Based on this:

Which ones are know and which ones are unknown in two above equations? A2 and A4 are unknown? Or X1 and X2 are unknown ?
If X1 and X2 are known, then we are able to find A4 and A2 even by a single equation.so, we do not need two!
If X1 and X2 are unknown, then they will be found based on A2 and A4. In this case, how is it feasible to recover the original file by two coded values A2 and A4 ?

How to solve this system of linear equations ?

It is NOT clear to me which one is known and which one is unknown:

A2 and A4 are unknown?

Or

X1 and X2 are unknown?

The original data are $X_1$ and $X_2$.  The shares are

\begin{align*}
  A_1 &= X_1, \\
  A_2 &= X_2, \\
  A_3 &= X_1 + X_2 \\
  A_4 &= X_1 + 2 X_2.
\end{align*}

You store the shares $A_1$, $A_2$, $A_3$, and $A_4$ on disk, or over the internet and through the hills on someone else's disk, or buried in a tree somewhere for safekeeping.  If a forest fire takes out the tree and someone else's house is washed away in a flood (or, if a malicious storage server tries to modify one of the shares and you detect it because you're using cryptography and throw that modified share away), but you still have two of the four shares, say $A_2$ and $A_4$, you can recover

\begin{align*}
  X_2 &= A_2, \\
  X_1 &= A_4 - 2 A_2,
\end{align*}

and get your original file $X_1 \mathbin\| X_2$ back.


What does the expression $1^n$ mean as a function argument? In a paper about predicate encryption or attribute based encryption, the setup function is mentioned with the $setup(1^n)$ or $setup(1^l)$. I want to know what is meant here.

Is it multiples of ones or representing something else?
Also, why is this used here?

If you got an expression that resembles $\{1\}^n$ (or $1^n$) at a place in a surrounding expression where you would expect an $n$-bit bit string to be, the $\{1\}^n$ expression means a string of $n$ bits each with the bit value $1$.

Conversely, $\{0\}^n$ means a string of $n$ zero valued bits, and $\{0,1\}^n$ just means any bit string of length $n$.

In the paper you mentioned, it looks like $n$ plays double duty: it both determines the set of attributes/predicates, and it is the security parameter. In this case the authors don't seem to use this notation to indicate that the setup is polynomial in the binary logarithm of the key space, but rather that it is polynomial in the maximum number of independent predicates.

The concepts Predicate and Attribute are related in such way that each entity $k$ (that might or might not have rights to decrypt a given cipher text) is associated with some set of predicates $F_k = \{f_i\}$ and the cipher text is associated with an Attribute $I$, and entity $k$ will be able to decrypt the cipher text if and only if $f_i(I)=1$ for some predicate $f_i \in F_k$ the entity has been assigned. The attribute was set as parameter when the plain text was encrypted to produce the cipher text.

The $Setup$ function defined in the referenced paper generates a master public key $PK$ and a master secret key $SK$. The master secret key is then passed to the $GenKey$ function that generates a secret key $SK_f$ for each predicate $f$

Although not written out explicitly, I suppose the argument of the Setup function could be interpreted as the union of the unhidden attributes of the cipher texts that the master secret key (generated by setup), will decrypt. With $n$ predicates, there are $2^n$ possible valid attribute value classes (there might be more than one value that instantiates each attribute), meaning that the set of attributes is isomorphic to $\{0,1\}^n$. One might in such case define the isomorphism $\phi$ such that the master attribute $I_M = \phi(1^n)$ equals the attribute such that $f_k(I_M) = 1$ for all predicates $f_k, 0 \le k \lt n$.

So how does this relate to the specific definitions in the referenced paper?

For starters, the set of attributes $\Sigma = \mathbb Z^n_N$ is a vector set with $N^n$ different values. However, the difference between $N^n$ and $2^n$ is due to there being $(N-1)^{n-k}$ different values in $\Sigma$ that all correspond to the same selection of $k$ predicates. Think of it like this:

Let $X$ be an $n\times n$ matrix over $\mathbb Z_N$, where each row corresponds to a predicate vector. Let $Y$ be an $n$ element column matrix corresponding to an attribute $I$. Let $XY = Z$. Now, since matrix multiplication of a row on the left with a column on the right corresponds to a dot vector multiplication, for each element $z_i$ in the $Z$ column matrix, $f_i(I) = 0 \iff z_i = 0$. On the other hand, if $f_i(I) \neq 0$, then $z_i$ might be any non-zero value in $\mathbb Z_N$, and there are $N-1$ such values.


Desirable Property of Block Sub-Keys What is the more desirable for a block cipher's sub-keys ?

Given two blocks ciphers, letting all other properties be equal (they have the same strength), the only difference between them is that:

one generates a unique set of sub-keys for each key,
while the other generates a set of of pseudo random subkeys.

In other words for each different possible key, the fist cipher always generates a unique subkey set that only that key can, while the second has the possibility (however small) that it could generate a subkey set that another key might also generate.

Focus on this property itself:  assume everything else about the cipher and key derivation process are of sufficiently high quality.

What you call Block Sub-Keys, is called key schedule.

The first thing you need to know, is that this sub-key generation needs to be deterministic (else how would you be able to decrypt the cipher text).

Thus you are considering two cases:

a simple key schedule to generate the sub-keys.
a Pseudo Random Generator (or more usually a Hash function) to generate the sub-keys.

In the first case you have:
$$F(K) = K_1,\\
F(K_1) = K_2,\\
F(K_2) = K_3,\\
...$$

In the second case you have:
$$H(K) = K1 || K_2 || K_3 || ... $$
where $H$ is a eXtendable-Output Functions (XOF) such as SHAKE and $||$ is the string concatenation.

In the first case you have a sort of key dependence (from $K_1$ you can deduce $K_2$, but luckily not the other way around) while on the second case each sub keys are independent (you can't deduce $K_2$ from $K_1$).

From this point of view, surely the second approach looks the safest however, one must also consider speed and memory consumption.
Generating a long stream of bits in order to have the sub-keys takes time. If you were to compare the time spend on encrypting the data provided a set of sub-key and the time to generate the set of sub-keys, with this solution the slowest one would probably be the sub-key generation. And this is not something desirable if you want to have a usable cipher. Also the second methods requires to generate all the sub-keys at the initialization of the algorithm. This requires some memory...

To sum up, I'll point you to this two answers:

What are the requirements of a key schedule?
Does the key schedule function need to be a one-way function?


Hardness of elliptic curve discrete logarithm problem? I have just started to study Elliptic curve cryptography. I have a question: In elliptic curves in Fp (such as prime256v1 curve) I just learned that the discrete logarithm problem is, "finding k, where Q=kG and G and Q are known, is hard" (k is big integer and G is generator)

I'm curious if the below sentence is still correct?

"finding x or y or z is hard, where P0=xG, P1=xyG and P2=xyzG and P0, P1, P2 and G (also generator) are known"

I think there is too much information. Is this still hard?

This depends a bit on your group structure because P0, P1, P2 could lie in small subgroups but if you avoid that you are still trying to solve a hard discrete logarithm problem.


Zero Knowledge Proof extended Schnorr - average secrets I am trying to compute and an overall average number of given secrets from inside the commitments.
I have the following set-up:

Three commitments;

$C_{1}(id, num, r) = g_{1}^{id} g_{2}^{num}  g_{3}^{r}$,

$C_{2}(id, num, r) = g_{1}^{id} g_{2}^{num}  g_{3}^{r}$,

$C_{3}(id, num, r) = g_{1}^{id} g_{2}^{num}  g_{3}^{r}$. In this we have secret parameters $id$, $num$ and $r$ (random opening). Also for each commitment $id$ and $num$ are different.

So my question is how can I prove to someone what the overall average of nums is without revealing the individual num/s?

Secondly, how could the ids be hidden as along with secrets and still only prove the average?

I tried adding another commitment and just having a linear relation between secrets $num$. However I have a feeling it is not the correct way of dealing with it.

Here is a protocol that seems to fit your requirements: Let P be a prover and V be a verifier. $g_1,g_2,g_3$ are all generators of a group of order $p$ in which the discrete logarithm cannot be solved efficiently (note: you don't need Diffie-Hellman to be hard, discrete log is sufficient). (I assume that neither P nor V know the discrete log of $g_i$ in base $g_j$ for $i \neq j$).

Both players know three group elements $C_1,C_2,C_3$. First, P sends a value $a$ to V, which is the sum of the $num_i$ (this is perfectly equivalent to giving the average). Now, P intends to prove to V that he knows $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$.

Note: it is important to remark that this can only be a proof of knowledge of such values, and not a proof of their existence, as for any triple $(C_1,C_2,C_3)$, there exist many values satisfying your requirements.

Protocol:

P picks nine random exponents $(x_i,y_i,z_i)_{i\leq 3}$, with the constraint that $y_1+y_2+y_3 = 0 \bmod p$, and sends $(R_i)_{i\leq 3} = (g_1^{x_i}g_2^{y_i}g_3^{z_i})_{i\leq 3}$ to V.
V sends a random challenge $e \leq p$ to P.
P sends $(u_i)_{i\leq 3} = (e\cdot id_i + x_i \bmod p)_{i\leq 3}$, $(v_i)_{i\leq 3} = (e\cdot num_i + y_i \bmod p)_{i\leq 3}$, and $(w_i)_{i\leq 3} = (e\cdot r_i + z_i \bmod p)_{i\leq 3}$.
V checks that $C_i^{e} R_i = g_1^{u_i}g_2^{v_i}g_3^{w_i}$ for every $i \leq 3$, and that $v_1+v_2+v_3 = a\cdot e \bmod p$. He accepts if all the checks pass.

This is an honest-verifier zero-knowledge proof of knowledge of $(id_i, num_i,r_i)_{i\leq 3}$ such that $C_i = g_1^{id_i}g_2^{num_i}g_3^{r_i}$ for $i\leq 3$, and $a = num_1 + num_2 + num_3$ (hence, assuming the verifier behaves honestly, it reveals nothing about all those values, except that this statement is true). The average value is then just $a/3$. The protocol can be enhanced into a truly zero-knowledge protocol (which remains zero-knowledge even if the verifier is dishonest) using classical techniques (for example, by letting V send an extractable commitment of $e$ before the first flow of the protocol). It can also be made more efficient regarding communication, using batch techniques.

This is a quite classical example of a zero-knowledge proof of knowledge of discrete logarithms in multiple basis, satisfying some relations. The fact that the protocol is correct is easy to see from its description (if the prover is honest, then the proof is accepted). Proving that it is sound (the prover cannot cheat and make the proof pass without knowing such values) requires the use of a technique called rewinding (to show that if the proof pass, some simulator could extract the values by interacting with the prover, which shows that the prover know those values). Proving that it is (honest-verifier) zero-knowledge is done by showing that if the prover knows $e$ in advance , he can pass the proof even without knowing such values. However, writing the full proof formally would be a bit extensive here. Such proofs require to be already quite familiar with zero-knowledge proofs.


PRF and pairwise independent hash function I'm confused with the concepts of pairwise independent hash function and pseudorandom function. They seem identical to me.

A family of hash functions $H=\{ h:U \to [m] \}$ is $k$-independent if for any $k$ distinct keys $(x_1, \dots, x_k) \in U^k$ and any $k$ hash codes (not necessarily distinct) $(y_1, \dots, y_k) \in [m]^k$, we have:

\begin{equation}\Pr_{h \in H} \left[ h(x_1)=y_1 \land \cdots \land h(x_k)=y_k \right] = m^{-k}\end{equation}

This definition is equivalent to the following two conditions:

for any fixed $x\in U$, as $h$ is drawn randomly from $H$, $h(x)$ is uniformly distributed in [m].
for any fixed, distinct keys $x_1, \dots, x_k \in U$, as $h$ is drawn randomly from $H$, $h(x_1), \dots, h(x_k)$ are independent random variables.

These properties are exactly the properties of a PRF, aren't they? So what is the difference between these two definitions?

You are right; these are the properties of a PRF. In fact, a $k$-wise independent hash function has exactly the same distribution as a truly random function, as long as you only see up to $k$ points. This is the difference: a pseudorandom function has to be indistinguishable from random for any polynomial number of samples viewed. This is both weaker and stronger than $k$-wise independence: a PRF is only computationally indistinguishable from random (weaker), but maintains this property for any polynomial number of samples.

Note also that $k$-wise independent hash functions become very inefficient when you look at large $k$. So typically they are very useful when you only need pairwise independence or a small $k$.


Proof of shared secret through key derivation Alice gives a random key $K$ (e.g. 32 bytes long) to Bob through a secure channel.

Bob want to prove to Alice through an unsecured channel that he knows the key.

Is it secure for Bob to send $s||KDF(s||K)$ −with $s$ a random tag, say 8 bytes long− ? It seems Alice can recompute $KDF(s||K)$ and compare. Nobody can deduce K from the message.
Provided tags are one time use only, and Alice keeps track of which have already been used, how many different proofs could Bob send before an observer could potentially figure out K ?
Is there a way to improve that function ? Any specific key word, name of algorithm or protocol about that topic ?

Edit : I understand HMAC is the function I am looking for. Is it safe to use it for that purpose ? Can an observer learn anything about the key from many HMAC ?

HMAC nor a KDF is needed here. As long as you always use a constant size key and "tag" (generally called a nonce, as in number-used-once) you can simply use a secure hash function, like SHA-256.

My suggestion is to drop keeping track of the tags sent so far - this administration is bound to fail at some point. Instead, generate a 32 byte random number. This reduces the chance of collision to a neglegible amount.

So if you use my proposed scheme:

Alice sends a 32-byte random number $n$ to Bob.
Bob replies with $H(K || n)$.
Alice checks the result.

Then an eavesdropper or even a MITM attacker will never learn $K$ faster than bruteforce.


Why was AES CBC removed in TLS 1.3? I don't quite understand why AES CBC was removed in TLS1.3.
From what I know CBC is the most secure Mode of operation for the AES block cipher (if you can say it like that).
It only needs a TRND IV and has not been broken. If you pair it with a decent HMAC I guess It's at least as secure and AES-GCM.
So why is AES-GCM preferred and the CBC support was removed?

Short: CBC mode in context of TLS protocol has had security issues, and would have had to be reworked.

AES-CBC mode combined with decent HMAC can be as secure as AES-GCM. However, combining the cipher and MAC securely has been in practice found to be much easier said than done. Also, padding that is required by AES-CBC mode complicates things.

In particular, within the history of the SSL and TLS protocols, there is a long history of security vulnerabilities resulting from misuse of CBC mode or within combination of CBC and MAC, such as BEAST and Lucky13.

After the Lucky13 attack (a timing oracle caused by MAC-then-encrypt), it was thought that TLS should change ordering of the operations. Changing order of the operations would have affected the backwards compatibility with previous implementations so it was after all thought that it is more practical to switch to authenticated encryption only.

In addition to security aspects, there are some other practical benefits of AES-GCM over AES-CBC and HMAC:

On most platforms with hardware acceleration or AES-NI instructions, AES-GCM is many times faster than AES-CBC with HMAC. This is because AES-GCM is designed to be more parallelizable.
Generation of random bits is relatively slow. This is also where AES-GCM excels. Random bits are more seldomly needed than with AES-CBC (in TLS 1.1+.)
AES-GCM in average does not extend the size of the message as much as equivalent combination of AES-CBC, HMAC and padding.


Data Encryption Standard (DES) S-Boxes I read that the S-boxes introduce the much needed nonlinear behavior to DES. Can someone give me a lay mans explanation of why the effect of the S-boxes is said to be non-linear?

If you take an Sbox and two different inputs $x_1,x_2$ (binary vectors of length 6) the exclusive or ("sum") of the two inputs is does not propagate to the output. So
$$S(x_1)\oplus S(x_2) \neq S(x_1\oplus x_2)$$
in general. This means that there is no shortcut allowing one to predict outputs "bit by bit" and build efficient search tables, by just considering the list of outputs

$S(100000),S(010000),S(001000),S(000100),S(000010),S(000001)$$

and obtaining

$$S(a_1~a_2~a_3~a_4~a_5~a_6)=a_1 S(100000)+a_2 S(010000)+\cdots+a_6 S(000001).$$

by linearity. This would lead to very efficient attacks when applied to all 8 Sboxes.


What is modulo switching, in a nutshell? Coupled with the terms bootstrapping and relinearization, the term modulo switching appears a lot in the FHE literature. What is it and how does it relate to the other two?

The basic idea:
In homomorphic encryption schemes, the ciphertexts are noisy and we want to refrain the noise from growing too fast as we operate homomorphically. So the idea here is to multiply a ciphertext $c$ defined over $\mathbb{Z}_{q_0}$ by $q_1 / q_0$ so that the noise term is also multiplied. Then, by setting $q_1 < q_0$, we go from a noise term $e$ to a smaller noise approximately equal to $\frac{e q_1}{ q_0}$.
Furthermore, the ciphertext we obtain is then defined over $\mathbb{Z}_{q_1}$.
What is the advantage of doing this?
Let's say that fresh ciphertexts have noise term bounded by $B$ and that one homomorphic multiplication increases the noise to (approx.) $B^2$.
Then, two multiplications gives us $(B^2)^2 = B^{4}$, three gives us
$(B^4)^2 = B^8$... A sequence of $L$ multiplications increases the noise to $B^{2^L}$.
Because the final noise must be smaller than the modulus $q$, the bit length of $q$ must be bigger than $\log B^{2^L} = \Theta(2^L)$, that is, exponential in the circuit depth.
Now, imagine that we have $q_L := B^{L+1}$, $q_{L-1} := B^{L}$, $q_{L-2} := B^{L-1}$, ..., $q_{0} := B$. Then, $q_{i-1} / q_{i} = 1/B$.
Now, the first multiplication increases the noise close to $B^2$, but multiplying by $q_L / q_{L-1}$ scales it down to $B$ again.
Then, the second product increases the noise to $B^2$ and multiplying by $q_{L-1} / q_{L-2}$ (modulus switching) reduces the noise to $B$ again.
Proceeding like this, after $L$ multiplications, we have a ciphertext defined over $\mathbb Z_{q_0}$ with noise smaller than $B$, which can be correctly decrypted.
Now, the bit length of the modulus we need to use is $\log q_L = \Theta(L)$, that is, linear in the circuit depth instead of exponential!
But how the modulus switching is really done?
Of course, we can't simply multiply $c$ by $q_0 / q_1$, because we will not obtain a valid ciphertext, thus, each scheme has it is own way of getting a valid ciphertext out of $c\cdot q_0 / q_1$, but this is basically done by rounding.
For instance, let's say that we have the following LWE ciphertext with secret key $\vec s$ and noise term $e$:
$$
\vec c = (\vec a, \, \underbrace{\vec a\cdot \vec s + e + m \cdot q_0/2}_{b}) \in \mathbb{Z}_{q_0}^{n+1}.
$$
Then, over the integers, we have $b = \vec a\cdot \vec s + e + m \cdot q_0/2 + uq_0$
for some integer $u$.
Since the rounding function satisfies $\lceil x \rfloor = x + \epsilon$ with $-1/2 \le \epsilon \le 1/2$,
it is clear that
$$
b' := \lceil b \cdot q_1 / q_0 \rfloor
= \vec a\cdot\vec s \cdot q_1 / q_0 + e \cdot q_1 / q_0 + m\cdot q_1 / 2 + \epsilon + uq_1 \in \mathbb{Z}.
$$
Using this trick again, we define
$\vec a' := \lceil \vec a \cdot q_1 / q_0 \rfloor = \vec a \cdot q_1 / q_0 + \vec \epsilon$, with rounding applied entry-wise, and obtain
$$
b'= \vec a' \vec s -\underbrace{ \vec \epsilon \vec s+ e \cdot q_1 / q_0 + \epsilon}_{e'} + m\cdot q_1 / 2 + uq_1 \in \mathbb{Z}.
$$
Finally, reducing $b'$ modulo $q_1$ removes the term $uq_1$.
Moreover, assuming that $||\vec s||$ is small, we see that the new noise $e'$ is close to original noise $e$ scaled by $q_1/q_0$.
Therefore,
$$\lceil \vec c \cdot q_1 / q_0 \rfloor \bmod q_1 = (\vec a', \, \vec a' \vec s + e' + mq_1/2) \in \mathbb{Z}_{q_1}^{n+1}$$
is a valid ciphertext of the same message, under the same key, but with smaller noise and with respect to a smaller modulus $q_1$.


What does SSL use? RSA? El-Gamal? Elliptic curves? I'm not sure what SSL uses to share the symmetric key to both end users, i.e. at the beginning of the communication. Is it RSA? Or El-Gamal? Or something else?

Well, what SSL uses to negotiate the symmetric keys depends on the ciphersuite that both sides agree upon.  By far, the most common method is that the client picks a random value (the premaster secret), and encrypts it with the server's RSA public key.  However, it is not that unusual for the ciphersuite to specify that the client and the server agree upon a premaster secret using the Diffie-Hellman algorithm (or the Elliptic Curve version), with the DH exchange generally (but not always) being protected via some sort of signature operation.

El-Gamal isn't generally used; in fact, I don't believe that there's a standard ciphersuite that specifies it.


AES encryption using a Diffie-Hellman question this is something that has always nagged at me and I've wanted to know the answer to.

Does AES create it's own shared secret symmetrical key after the DH process has completed?

I'm not as familiar with it as i am with know the process of say SSL (RSA,AES) where the public key encrypts the AES symmetrical key and then sends it across and host 2 decrypts with the private key and now knows the shared secret key.

With DH, I've always had conflicting answers, some say if you create a 1024 bit DH key then AES creates the 128 bit symmetrical key and passes it across, i don't feel like this is the case (i'm happy to be corrected either way). Some have also said that the key from DH is the key that AES uses for it's encryption. My question would be then isn't it just using a 1024 bit pub/pri key exchange to encrypt and decrypt data, or is it something in the middle?

Thanks for the help

Does AES create it's own shared secret symmetrical key after the DH process has completed?

No. AES uses the key that is produced by the Diffie-Hellman key agreement, possibly after key derivation using a KDF or PRF.

  With DH, I've always had conflicting answers, some say if you create a 1024 bit DH key then AES creates the 128 bit symmetrical key and passes it across, i don't feel like this is the case (i'm happy to be corrected either way). Some have also said that the key from DH is the key that AES uses for it's encryption. My question would be then isn't it just using a 1024 bit public/private key exchange to encrypt and decrypt data, or is it something in the middle?

Diffie-Hellman is an asymmetric key agreement protocol. It requires two Diffie-Hellman key pairs (generated using a secure random and the Diffie-Hellman key generation procedure). Either of these key pairs can be ephemeral (i.e. used once or just a few times) or static (persistent, part of a DH certificate). After the public keys are exchanged the Diffie-Hellman calculation is performed and a shared secret is produced - this is the base value from which the shared (AES) keys can be derived.

The shared secret is large and not fully random. So generally it is run through a key derivation function or KDF to calculate the keys from the shared secret. TLS/SSL calls this the pseudo random function or PRF - a more generic term. For older versions (1.0 and 1.1) the TLS PRF internally uses a combination of MD5 and SHA1 (doubled in the HMAC construction, which is further doubled); 1.2 uses SHA256 (in double HMAC) for the pre-existing cipher suites (which specify MD5 or SHA-meaning-SHA1 for HMAC on data records) but newly-defined suites can name a different hash for the PRF and some do use SHA384, in conjunction with AES-256 for encryption.

Besides the master secret the KDF also uses the identity of the client / server and a label to derive keys. In the end you should have a total of two or four keys: two if authenticated encryption such as GCM is used and four if the authentication (HMAC) is performed separately from encryption.
In 1.0 the KDF also derives two initial IVs for CBC suites (which was associated with a flaw, since fixed) and in 1.2 the KDF can also derive two partial IVs for GCM or CCM suites.

One of these keys are used to encrypt and possibly authenticate the messages from the client to the server and one for the messages in the other direction. It depends on the cipher suite if AES is used for encryption or not.

For TLS 1.3 the use of ephemeral keys is required (DHE or ECDHE). Authenticated encryption (an AEAD cipher) is required as well, so only two keys need to be produced for regular data encryption, although 1.3 also derives several more keys used during the handshake and optionally for special purposes. If RSA or ECDSA is used then it is only to authenticate the client / server; neither RSA or ECDSA will directly be involved in the key agreement.


Why a Unitary Matrix in Quantum Cryptography? I've read that in Quantum circuits the matrix that encodes the transformation has to be unitary. I understand that it must preserve the norm of the resulting qubit, but what is the intuition behind it?

Short (unhelpful?) answer: the transformation are unitary, because quantum physics says all transformations on quantum states are unitary. So your question boils down to “Why are unitaries the only allowed transformations?”.

For two reasons:

Quantum mechanics restricts the allowed transformation on quantum states to  be linear, transforming the vector $|ψ\rangle$ to $V|ψ\rangle$, where V is a matrix. I have no obvious intuition on why the transformation have to be linear$^\dagger$, except that

it gives an elegant and simple mathematical theory;
attempts at constructing nonlinear quantum mechanics have all lead to problematic consequences, e.g. in causality.

Once you accept the linearity of the transformation $V$, the unitarity comes from the conservation of the norm of  $|φ\rangle$, since this norm corresponds to the sum of probabilities of the different measurement results, which is therefore $1$. We have then, for all $|φ\rangle$,
\begin{align*}
\langle φ|φ \rangle &=1 & \langle φ|V^\dagger V|φ\rangle=1.
\end{align*}
Since it is true for all $|φ\rangle$, it implies that the eigenvalues of the Hermitian operator $V^\dagger V$ are all $1$, that is $ V^\dagger V=\mathbb I$: in words, $V$ is unitary. Another (maybe mor intuitive) explanation of this is that unitaries are the only matrices preserving the the scalar products $\langle φ|ψ\rangle$, which measures the distinguisability of states $|φ\rangle$ and $|\psi\rangle$.

$\dagger$: if anyone knows an intuitive explanation of the linearity of QM, I’d love to read it!


First block as initialization vector in the CBC-MAC A fixed-length CBC-MAC uses zero block as IV (initialization vector) to prevent from changing the first block.

i.e. tag $t$ = $F(m_x \oplus ... F(m_3 \oplus F(m_2 \oplus F(m_1)))...)$

My question is, if the first block is used as IV, then is it secure (unforgeable), and why?
(not for encryption/confidentiality, and just for authentication)

i.e. tag $t$ = $F(m_x \oplus ... F(m_4 \oplus F(m_3 \oplus F(m_1 \oplus m_2)))...)$

Thank you.

My question is, if the first block is used as IV, then is it secure (unforgeable), and why?

Suppose with this scheme, you have the MAC for the message $[m_1, m_2, m_3]$.  Could someone without the key compute the MAC for the message $[m_2, m_1, m_3]$?


How to calculate the entropy for a fixed length random passwords which has restrictions on the type of characters used If we have a set amount of usable characters, but no other restrictions on the potential characters in a completely random fixed length password, we can easily calculate the entropy by doing:
$\log_2(c^{n})$
or
$\log_2(c)*n$
with $c$ being the number of possible characters, and $n$ being the length of the password.
However, when there are restrictions being set on the contents of the random password, this obviously lowers the entropy.

For example, if you have $94$ usable characters, of which $10$ are digits, $26$ are lower case letters, $26$ are upper case letters, and $32$ are special characters.
If there are no other restrictions, this gives us
$\log_2(94^{10}) = 65.5$
which means $65.5$ bits of entropy.

Now, if we have $94$ usable characters and the following restrictions are set:

1 character must be an uppercase letter ($26$ options)
1 character must be a lowercase character ($26$ options)
1 character must be a digit ($10$ options)
1 character must be a special charater ($32$ options)

How do you calculate the entropy for a truly random fixed length password with these restrictions in mind?

It looks like the formula you're using is $\log_2(\textrm{number of possible passwords})$.
You don't explicitly mention a length, so I'll assume 10.
So with those restrictions, let's calculate the number of possible passwords.
Without any restrictions, the total number of possible passwords is $94^{10}$.
Let's count the number of invalid passwords.
$(94-26)^{10}$ don't contain an uppercase letter. $(94-26)^{10}$ don't contain a lowercase letter. $(94-32)^{10}$ don't contain a special character. $(94-10)^{10}$ don't contain a digit.
There's overlap in those. For example, $(94-52)^{10}$ contain neither uppercase nor lowercase letters.
Number of invalid passwords = $(94-26)^{10} + (94-26)^{10} + (94-32)^{10} + (94-10)^{10} - \left((94-52)^{10} + (94-58)^{10} + (94-36)^{10} +(94-58)^{10} + (94-36)^{10} + (94-42)^{10}\right) + \left(26^{10} + 26^{10} + 32^{10} + 10^{10}\right)$
This yields $64.81$ bits.

Sanity check:
Ignoring order, The restrictions give $26 \cdot 26 \cdot 10 \cdot 32 \cdot 94^{6}$ possible number of passwords. That's one uppercase, one lowercase, one digit, one special character, and the remaining 6 can be anything. Taking the $\log_2$ of this yields $57.05$ bits.
This is a lower bound. The $65.5$ you mention in the question provides an upper bound. The answer lies inside the bounds as expected.


What is the name of this kind of protocol There is a communication protocol that I believe creates the equivalent of a one time pad, with the downside that the secret message must be transferred multiple times.  The protocol is so simple that I imagine that it has a name but I can't find a protocol which matches its description.

Assumptions:

A client C wants to send a password P of L bytes to a Server S.
A function Z(P,M) exists whereby both P and M are L bytes and

Z(P,M)= P[i] xor M[i]; for all i < L

Thus the protocol would work as follows:

C generates a random string of L bytes called CM. C sends to S: Q0 where Q0=Z(P,CM)
S generates a random string of L bytes called SM. S sends to C: Q1 where Q1=Z(Q0,SM)
C reapplies the CM mask to Q1. C sends to S Q2 where Q2=Z(Q1,CM).
S reapplies the SM mask to Q2. Q gets P from P=Z(Q2,SM)

The protocol is taking advantage of the fact that the xor operation is both associative and commutative.

The name I would use for this protocol is "broken".

It is insecure.  An eavesdropper gets to observe $Q_0 = P \oplus CM$, $Q_1 = Q_0 \oplus SM = P \oplus CM \oplus SM$, and $Q_2 = Q_1 \oplus CM = P \oplus SM$.   Notice that we have the relation
$$Q_0 \oplus Q_1 \oplus Q_2 = (P \oplus CM) \oplus (P \oplus CM \oplus SM) \oplus (P \oplus SM) = P.$$
Therefore, an eavesdropper who xor's the three messages he observes can recover the message $P$.  In other words, this protocol is completely insecure.

If I recall correctly, I believe that an early version of the Bluetooth specification used this algorithm for key exchange.  Fortunately, the error was caught and fixed.

You may be thinking of the three-pass protocol for key exchange.  It is basically the same concept as what you have, but using something other than xor.  With xor, this is insecure, but if you replace xor with an appropriate other operation, you can get something secure.  The most well-known instantiation is to replace xor with Pohlig-Hellman exponentiation-based encryption.  In that scheme, we set $Q_0 = P^c \pmod{p}$, $Q_1 = Q_0^s \pmod{p}$, $Q_2 = Q_1^{c^{-1}} \pmod{p}$, and then S can compute $P = Q_2^{s^{-1}} \pmod{p}$, where everything is done modulo a large prime $p$.  However, the three-pass protocol has no advantages over standard public-key key-exchange systems, so it is rarely (if ever) used.  For instance, its security is roughly equivalent to the security of Diffie-Hellman key-exchange, so it has no clear advantages over Diffie-Hellman or RSA.


Significance of Extended Euclidean Algorithm in Cryptography I'm currently reading Paul Garrett's book "Making, Breaking Codes", where he goes through the standard textbook implementations of different crypto-systems (RSA, Elgamal etc).

When he talks about the different attacks that can be performed on these systems, he often uses the extended euclidean algorithm on different numbers to perform these attacks.

For example, when talking about an RSA attack where an actor sends the same cipher text to two different people with the exponent $e$ changed, he talks about how you can calculate the $\mathrm{Ciphertext}^{-1} \mod n$ (along with other operations) to find the plain text message. I understand that using the extended Euclidean algorithm will give you an $a$ and $b$ such that $ax + by = 1$, however I'm unclear as to how this can help one solve different problems in cryptography.

How does finding this $ax + by = 1$ help in the solution to different cryptographic problems?

The significance of the EEA is that it gives an efficient way to compute modular inverses. Since computing modular inverses is an extremely common task in practical cryptography (among many others, you need it to derive the decryption exponent of an RSA keypair from the encryption exponent), the fact that it can be performed efficiently, as demonstrated by the existence of the EEA, is fundamental. If it couldn't, many of the cryptographic schemes in use today just wouldn't work.


Why this example about pseudorandom generators is performed like that? Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With pseudorandom number generators (PRNGs) they could proceed as follows.

They both seed a PRNG with the shared secret $s$.
Bob picks sends Alice some random number $i \in \mathbb{N}$.
Alice proves she knows the share secret by responding with the $i$-th random number generated by the PRNG.

I am wondering why Bob sends a random number $i$ instead of just $1$. Then Alice just sends $G(s)$ (where $G(\cdot)$ is the PRNG) to Bob. Only Alice and Bob should have access to the secret $s$, and hence this should also work. In the above example, Alice and Bob should both have to compute $G(s)$ $i$ times, making it much more inefficient.
Which is the difference between what I am proposing and the original example? Aren't them both equally secure?

Bob sends random number so they can use their shared secret for authentication process many times.


Attack on a Feistel Cipher given the key and half of the ciphertext Consider a classical Feistel Cipher, with the round functions given and the keys used in the ciphering process.

Is it possible to reconstruct the original data if half of the ciphered text is given? Furthermore, is it possible to reconstruct the original data if less than half of the ciphered text is given?

What would be the complexity of these tasks?

Example:
Suppose that we have a text that "makes sense" (e.g. it belongs to a dictionary or some set $S$). Let's say that "Salsifis" is ciphered into "abcdefgh". Suppose that "efgh" is revealed as well as the keys. Can "Salsifis" be reconstructed other than using an exhaustive search?

In a block cipher (SPN of Feistel), we want each of the plaintext bits affects the ciphertext bits. In other terms, if you write down the boolean function of the ciphertext bits $c_i$, we expect that the function contains all of the plaintext bits and the key bits;

$$C_i:\{p_0,\ldots,p_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$c_i=C_i(p_0,\ldots,p_l,k_0,\ldots,k_n)$$with $l$-bit block cipher, $n$-bit key size, and $C_i$ is a boolean funtion and $c_i$ is the i-th bit of the ciphertext.

Similarly, one can write boolean functions for the plaintext bits;

$$P_i:\{c_0,\ldots,c_l\} \times \{k_0,\ldots,k_n\} \mapsto \{0,1\}$$ $$p_i=P_i(c_0,\ldots,c_l,k_0,\ldots,k_n)$$

One-bit missing case

In this case, each of the boolean functions $P_i$ will have a free variable, the missing bit. By avalanche property, we expect that being 1 or zero will affect the half of the bits randomly. So you will have an almost completely different plaintext if you set this variable 1 or 0. If you have a pre-knowledge about the plaintext, like the language or structure, you may able to decide which one is correct.

More than one bit is missing

In this case, the missing variables will behave much more complicated. One, however,  can still try guessing the bits and check the plaintext properties to verify.

The complexity

As one can see, all is nothing but brute-force. So the complexities are $2^m$ where the $m$ is the number of missing bits. And remember, brute-force can only be successful if you have some information about the plaintext, as in RSA challenge.

** update: a simple test case for one-bit change in DES.**

key        : $\texttt{0e1f35bbaf37a86b}$

Ciphertext : $\texttt{0123456789ABCDEF}$

Plaintext  : $\texttt{0d738d5e43fbd5fe}$

Ciphertext : $\texttt{1123456789ABCDEF}$

Plaintext  : $\texttt{bd85b2e02bb056df}$

The difference between two plaintexts with one-bit change;

$\texttt{b0f63fbe684b8321}$, and in binary;

1011000011110110001111111011111001101000010010111000001100100001

which has 33 1's


Is there a crypto system doing sqrt during encryption? This is a theoretical question to solve an argument with a friend..

Is there a working cryptographic system that do square root operations during the encryption process?

"Working" means that it is really implemented, and not just an academic research.

Hint: I suspect that it is not possible as computer hardware has floating point limitations as it is based on binary, causing infinitely small numbers to truncate, hence doing sqrt during encryption loses information, and cannot be undone during the decryption.

Please help me win the bet :)

I'm not aware of any cipher which uses square root as a primitive operation, and I suspect that none exist. Cipher designers tend to prefer a large number of simple operations to a lesser number of complex ones. The most complex operation used in practice is multiplication, and even that is not extremely common. The most complex mathematical operations I know of used in a cipher are exponentiation and logarithms. From a quote by James Massey on the use of complex functions:

  I have many times used the discrete exponential or the discrete logarithm as nonlinear cryptographic functions and they have never let me down.

There is no reason why a square root operation would need to return a floating point value (for example, in 8-bit integer arithmetic, $\sqrt50=7$, though it's likely that taking the fractional part of the square root would be more beneficial for causing diffusion and promoting nonlinearity), so it is possible to use, technically. It's perfectly possible to return an integer and still achieve diffusion. I have a few guesses as to why no cipher uses square roots as a cryptographic mixing operation:

It's difficult to write a fast constant time implementation, which is necessary to avoid side-channels.
The nonlinear properties it provides are not well-researched compared to other operations.
It is a complex and slow function, and cryptographers often prefer many simple and fast functions.
Unless done in a finite field, it is impossible to reverse the operation (which is often useful).

If you loosen your requirements, then the Rabin cryptosystem may fit the bill. It's an asymmetric cipher and is very similar to RSA, but with the public exponent fixed to $2$. This means that decryption involves computing modular square roots. It's very possible that there is other asymmetric cryptography which makes use of square root operations, but I can't think of any off the top of my head.

If you can expand your requirements to any $n^\text{th}$-root operations, then the broken KN-Cipher from 1995 may be relevant. Its round function is based on the cube root operation in $\operatorname{GF}(2^{33})$. Computing cube roots is also a simpler and faster process than computing square roots.


ed ≡ 1 modλ(n) stuck Given $p = nq$, $n \not\equiv q$, and
$\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \bmod \lambda(n)$?
My idea was to show it using the $k$ exponent, but I got stuck.
So:

From Fermat's Little Theorem we know, that
 $$ m^p = m \bmod p $$
 $ m^{\lambda(n)} = 1 \bmod n$ (Carmichael theorem)

$$\forall m, m^k \equiv 1 \bmod n$$
 so I add $k$:
 $$m^{\lambda(n) \cdot k} \equiv 1 \bmod n$$

In other words:  $$m^{kλ(n)+1} \equiv m \bmod n$$
 $$ed = k\lambda(n)+1$$ so:
 $$m^{ed} = m \bmod n$$
How then do I show that $ed \equiv 1 \bmod \lambda(n)$?

Given $n=pq$ and $\forall m: m ≡ m^{ed} \bmod n$, how can we show that $ed \equiv 1 \pmod {\lambda(n)}$?

Well, the most straightforward approach is first to show that we must have both:

$$ed \equiv 1 \pmod{p-1}$$

$$ed \equiv 1 \pmod{q-1}$$

We can combine these equivalancies into one, using the Chinese Remainder Theorem; however as $p-1$ and $q-1$ are not relatively prime, we get:

$$ed \equiv 1 \pmod{\text{lcm}(p-1, q-1)}$$

This turns out to be a necessary and sufficient condition.  Sometimes, we denote $\lambda(pq) = \text{lcm}(p-1, q-1)$; you'll sometimes see this formulation.


Why a "Next Header" field is part of ESP trailer? Please explain are there any reason under the hood to place "Next Header" field in ESP trailer instead of ESP Header ?

Well, in IPsec transport mode, the 'Next Header' gives the protocol type of the encrypted packet (e.g. TCP, UDP, etc), and hence is considered confidential, as we don't want the adversary to know the type of traffic.  The ESP Header is not encrypted, and hence we cannot put the 'Next Header' field there.

In AH, privacy is not a concern (everything is visible), and hence they do put the 'Next Header' field in the AH header.


What is the advantage of digital signatures over message authentication codes? Studying for CISSP these choices seemed limited:

  What is the advantage of digital signatures over message authentication codes?

  Digital Signature provides integrity verification while message authentication code does not
  Digital Signature provides confidentiality while message authentication code does not
  Digital Signatures provide authenticity while message authentication code does not
  Digital Signatures works faster than message authentication codes

Using the following chart as a reference, I'm leaning towards #2, but none of the choices really fit properly…

Cryptographic primitive | Hash |    MAC    | Digital
Security Goal           |      |           | signature
------------------------+------+-----------+-------------
Integrity               |  Yes |    Yes    |   Yes
Authentication          |  No  |    Yes    |   Yes
Non-repudiation         |  No  |    No     |   Yes
------------------------+------+-----------+-------------
Kind of keys            | none | symmetric | asymmetric
                        |      |    keys   |    keys

Hopefully an expert here can clarify.

If this requires a single answer among 1/2/3/4 (rather than none), I would select 3, by the following reasoning:

  Digital Signature provides confidentiality while message authentication code can not

We can summarily exclude this, since a Digital Signature simply does not provide confidentiality.

  Digital Signatures works faster than message authentication codes

We can exclude this (slightly fixed) statement: Digital Signature is often annoyingly slower than MAC (an exception is long messages with the signature's hash supported by hardware and the MAC in software; but then we can hash then make a MAC of the hash to regain most of the speed). Digital Signatures also has larger minimum size overhead for equivalent resistance to brute force.

  Digital Signatures provide authenticity while message authentication code cannot

Authenticity is commonly defined as only a user authorized to author or modify a message can do so. In some use cases, a MAC can provide authenticity (e.g. if the MAC key is kept secret, including unknown to users that verify integrity, by using Smart Cards to verify signed messages); but if we understand "while" as including in some setups where, the statement makes sense: the (only) advantage of Digital Signature over MAC is that verification is possible with only public keys; and that provides authenticity in many setups where a MAC does not (e.g. verification using a computer that adversaries can fully analyze).

  Digital Signature provides integrity verification while message authentication code can not

Integrity is commonly defined as resisting accidental alterations, or the stronger resisting deliberate modifications by outsiders. Digital Signature and MAC both insure this. Other definitions similar to that of authenticity are sometime used, but if we have to choose between 1 and 3, we must pick 3.