Can you help me understand multiplication of points when using Curve25519? I'm going through the below snippet of code which does multiplication of point over the curve Curve25519:

bits256 curve25519(bits256 mysecret,bits256 basepoint)
{

    bits320 bp,x,z;
    mysecret.bytes[0] &= 0xf8,
    mysecret.bytes[31] &= 0x7f,
    mysecret.bytes[31] |= 0x40;
    bp = fexpand(basepoint);
    cmult(&x,&z,mysecret,bp);
    return(fcontract(fmul(x,crecip(z))));
}

Here I didn't understand why the few bits are set and few bits are cleared in the mysecret.
Can't I perform multiplication of any point over the curve?
Is there any restriction on it?

Is curve multiplication is commutative over curve25519?

Can you help me understand multiplication of points when using Curve25519?

The Curve25519 paper gives you some hints about this. In Section3, it says:

  Responsibilities of the user. The legitimate users are assumed to generate independent uniform
  random secret keys. A user can, for example, generate 32 uniform
  random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the
  last byte, and set bit 6 of the last byte.

Curve25519 lets you use as secret key any 32-byte sequence that fulfills this restrictions. Although in principle multiplication assumes that you introduce a valid secret key fulfilling all these conditions, the code you mention tries to enforce this on its own. Note that it doesn't perform a validation check on the secret key, but directly modify it in case it didn't comply.
So, clearing bits 0, 1, and 2 of the first byte is this line of code:

mysecret.bytes[0] &= 0xf8

Clearing bit 7 of the last byte is this one:

mysecret.bytes[31] &= 0x7f,

And setting bit 6 of the last one is the next line:

mysecret.bytes[31] |= 0x40;

With respect to your last question, I think there may be a misunderstanding. In the comments, you seem to be asking about commutativity of Curve25519 (i.e., $ab == ba$), rather than associativity. Remember that you are performing scalar multiplication. That is, the multiplication of a scalar $x$ by a base point $G$. In this case, the scalar is the secret key. Therefore, it doesn't make sense to think of commutativity.


Is it an overkill to add external integrity check to the AES-GCM encoding? There is a java library for android which implements integrity checking to predefined encrypting mode(which can be found here).

  Short class description from author page to avoid further questions about code.

  Algorithm & Mode: AES 128, CBC, and PKCS5 padding. We use a 128 bit key size for its widespread support and because it’s not clear that
  256 is stronger. We would have picked GCM for its built-in integrity
  checking, but that’s only available since Android Jelly Bean, which
  leaves out about 1/4 of active Android devices
  IV Handling: We securely generate a random IV before each encryption.
  Key generation: Random or pasword-based.
  Integrity: We’ve also added more-or-less transparent integrity checking in the form of a SHA 256 MAC with a constant-time equality
  check. This is in the form of a “combined key” where 128 bits of the
  key are used for encryption and 256 bits are used for integrity, then
  the keys are kept together.

As stated before, it's possible to use AES-GCM, which already have built-in integrity checking.

So, the question is: Are there any (dis)advantages of adding external integrity check to AES-GCM (in theory, or practically)?

To sum up already mentioned comments:

  Disadvantages:

  loosing the speed advantage of AES-GCM;
  performance/space use and extra complexity(i don't think that complexity is the case, as library is fairly simple);
  human factor:

  "Crypto is tricky: it’s hard to tell that the gibberish that’s being printed is not good crypto, and it’s hard to tell that the code example you picked up from {put any source name here you like} has serious flaws."

  Advantages:

  HMAC-SHA256 has stronger authentication than GCM(in-depth explanation here), among other things not leaking the key in case of nonce reuse

Thank you for your answers.

Theoretically, there is no issue adding some kind of MAC on top of authenticated encryption's builtin. However, in practice there might be subtle flaws with composing the particular primitives you're using, or you may make an implementation flaw that renders them both vulnerable to a side-channel attack that didn't exist previously. Ultimately, it's best to stay away from getting creative with protocol design - just use the best-known implementation of the best-known primitive for the job.


How do attacks on WEP work? There is an abundance of tools and tutorials on how to break WEP encryption. However, I fail to find a nice resource that gives a clear break-down of why the attacks are possible. For example, I know that one of the attacks relies on fake authentication. I however fail to understand how this works because whenever an entity tries to authenticate, the AP will give it a challenge which it will not be able to answer correctly; meaning the fake authentication will be fruitless. How does the adversary gain from this fruitless authentication?

I also read that a short IV means that after a large number of packets, keys will begin to repeat. This kind of makes sense to me -- but I still dont have an understanding of how one might exploit this fact to retrieve the key. What precisely is the implication of IVs beginning to repeat after a certain  number of messages?

Then there is the weakness with the message checksum -- that a modification in the message comes with a predictable change in the checksum. How does one exploit this to break the key? Insights into the mechanisms of these attacks will be so helpful.

Part of the problem you're having is that there are multiple distinct vulnerabilities in WEP, and you're getting confused by the sheer number.  For example:

  I still don't have an understanding of how one might exploit [repeating IVs] to retrieve the key

Answer: those are two separate vulnerabilities.

The shortness of the IV space is an obvious vulnerability; the keystream used to encrypt the packet is a deterministic function of the IV and the key; if we see two different packets encrypted with the IV, we can immediately reconstruct the xor of the plaintexts (by xor'ing the ciphertexts); depending on the plaintexts, this can often allow us to deduce what the plaintext was.

However, this observation doesn't allow us to recover the key.  The key recovery attacks rely instead on the details of how WEP creates the RC4 key (by concatinating the 3 byte IV with the 5 or 13 byte key), and how RC4 processes that key into the initial permutation, and then how it uses that permutation to generate the initial key stream bytes.  It turns out that, depending on what the IV is (which the attacker can see), the first byte of the key stream may be correlated to one of the key bytes - by observing enough of these first bytes (which the attacker can deduce, as the first byte of the WEP plaintext is fixed), the attacker can deduce the key.

  How does one exploit [the weaknesses with the message checksum] to break the key?

That's a third vulnerability, and it can't directly be used to recover the key (unless a cleverly modified message can confuse the receiver into revealing it somehow).

This weakness is simply the observations that a) the message tag is a publicly computable linear function of the plaintext, and b) by flipping a bit of the ciphertext, we also flip the corresponding bit of the decrypted plaintext.  Hence, we can flip an arbitrary bit of the plaintext, and then compute which bits of the tag would be flipped and flip those as well; what this means is that if we know/guess one plaintext message, we can modify it into anything we feel like (possibly restricted to the same length; I'm not sure how we could modify that).

Since this works independent of what the key is, it doesn't help us to recover the key.


How to construct a circuit in zkSNARK I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is:

using a circuit to represent a problem,
generate an R1CS from the circuit,
transform R1CS to QAP and then we can run zk-snark

For the first part, is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?
Besides, how to flatten a problem into a circuit, by programming or using mathematical methods?

is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?

Problem should be in NP class. NP problems are problems that there exists an (efficient) algorithm that can decide or prove in polynomial time that is w a witness for the statement s (their statements) or it isn't. Many of zkSNARKs are based on circuit satisfiability problem. Circuit satisfiability is a NP-complete problem. There are two types of circuits: boolean and arithmetic circuits that can be converted to each other. Roughly speaking, we can design circuits for all algorithms (ex. SHA-256) that we can run on our computer. The below picture is a simple boolean circuit consist of wires and logic gates (AND, OR and NOT). In a zkSNARK system based on this simple circuit, prover want to convince the verifier that he knows the inputs ($x_1$ = 1, $x_2$ = 1, $x_3$= 0) that for this inputs the output of circuit is true, in another words, he knows the inputs that satisfy this circuit.

how to flatten a problem into a circuit, by programming or using mathematical methods?

After converting a NP problem to a (boolean or arithmetic) circuit, you should convert this circuit to a SNARK-friendly format like R1CS. There are some compilers that you can write your problem in a high-level programming language in them and compile the problem to R1CS format, for example, you can use ZoKrates, a toolbox for zkSNARKs on Ethereum or you can use libsnark's gadget libraries.


Do storage encryption systems care about size of data? I was studying about Psuedorandom functions and their use as encryption functions. One of the things that I read was "birthday bound" or "birthday attack".

When encryption is used for something like disk encryption, the amount of data being encrypted can be very large and over time be large enough to launch a birthday attack. Do storage encryption systems care about it? Or is it not big of a deal? Or is my assumption of data size being a problem, wrong?

It's common for encryption algorithm specs to specify a hard limit of how much data you should encrypt with the same key.  For example, consider the AES-XTS encryption algorithm, which was designed specifically for full-disk encryption:

The IEEE specification recommends that the length of a "data unit" (e.g., disk sector or block) encrypted with a single key should not exceed $2^{20}$ AES blocks.
The NIST recommendation upgrades this to a hard requirement.

Since each AES block is 16 bytes, and $2^{20}$ bytes is 1 MiB, that's a limit of 16 MiB ($2^{24}$ bytes) per data unit.  You need $2^{44}$ such data units to hit the $2^{64}$-block birthday bound, but 1 TiB ($2^{40}$ bytes) is only $2^{40} \div 2^{24} = 2^{16}$ times the size of the 16 GiB maximum data unit.  So disks don't appear to be big enough yet to hit this limit.

But note that this limit is per encryption key.  If you use multiple encryption keys then you get to reset the limit for each key that you use.  It's already common to use individual keys for each disk volume, and some filesystems (e.g, Apple's APFS) already support per-file encryption keys.


What does pseudo pre-image of a hash function mean? So finding a pre-image means given the hash value, one tries to find a message that gives this value using the function's standard IV. What about pseudo-preimage?

The pseudo-preimage is the problem of finding $(IV, M)$ given $t$ such that $H(IV, M) = t\ $.


Why does openssl BN_generate_prime return only a fraction of the safe primes within the given bit range? I went into prime generation issues the last week and eventually calculated 10^7 primes using erik tews safeprimegen python wrapper for openssl.
(https://github.com/eriktews/gensafeprime) (System: MacOS 10.8.4 / openSSL 0.9.8x)

10^7 openssl BN_generate_prime(32) -> 32bit safe primes
-> safeprimes.txt

Then i used R to get some information on this data:

  1343370 (13.4%) unique primes (within the 10^7 gathered numbers)

  2^32 < 3221226167 < 1343370 safe primes < 4294967087 <
  2^32

  (range of p is roughly : 2^31 *1.5 < s-p < 2^32 -209 (second half of the 32bit range)

For comparison i did generate all 32bit primes using a prime sieve algorithm.

2*31 < p < 2*32

  total 98182656 primes thereof 3059799 safe primes

  safe primes in range of openssl output:
  3221226167 < 1506677 safe primes < 4294967087

  openssl safe primes  /   safe primes in range:
  1343370 / 1506677  -> ~ 89.1 % of safe primes in range

(I did repeat this for 31bit safe prime generation and got almost the same proportions.)

Findings:

the openSSL output covered only about half of all safe primes in the given
range (2^32 -> 3059799)
also within the range of the returns only 90% of the safe primes available where reported

I would be interested to understand why openSSL safe prime return is restricted in such way and if this is considered an optimal result having in mind the crypto functions included in the library that rely on the safe prime generator.

The smallest safe prime you got from OpenSSL was 3221226167 = 0xC00002B7.  The largest was 4294967087 = 0xFFFFFF2F.  This makes me hypothesize that OpenSSL is setting the two high bits to one, and choosing the rest of the bits randomly.  If that is accurate, that would explain the range of primes you did.

As far as why you found many more safe primes in the range between 0xC0000000 and 0xFFFFFFFF, I don't have a good explanation for that.  I would have predicted that your experiment with OpenSSL should turn up approximately 96.2% of all safe primes in that range.  I don't know why you only saw 89.1% of the safe primes in that range.  Is it possible that OpenSSL has a slightly different definition of safe prime than what you were using in your exhaustive prime sieve?

Oh, why 96.2%, you ask?  It has to do with the coupon collector's problem.  If you have $n$ different objects, and you randomly draw $n$ times (sampling with replacement), you don't expect to observe all possible objects.  Instead, some objects will have been chosen multiple times, and some will have been chosen only a few times.  In your case, there are apparently 3059799 different safe primes (objects).  You draw $10^7$ times (with replacement).  What fraction of safe primes will be missed?  Well, let's fix a single safe prime.  The probability that it is missed on any one draw is $1-1/3059799$.  The draws are independent, so the probability that it is missed on all of the draws is $(1-1/3059799)^{10^7}$, which is approximately $0.038$.  In other words, we'd expect that a $0.038$ fraction of safe primes will never have been output by OpenSSL, in your experiment, assuming OpenSSL samples uniformly at random from all possible safe primes.  This corresponds to covering 96.2% of the safe primes during the $10^7$ draws you did.

Another possible explanation for your observed data is that maybe OpenSSL does not choose uniformly at random from all possible safe primes in that range; maybe some safe primes are slightly more likely to be chosen than others.  For instance, one possible method for generating a prime number at random is to select an integer $m$ at random, test if it is prime; if not, test $m+1$ for primality; if that's not prime, test $m+2$; and so on, continuing until you find a number that is prime.  This procedure does not generate the uniform distribution on primes of a certain size: primes that are preceeded by a large gap (a long stretch of composite numbers) will be more likely to be drawn than others, and primes $p$ where $p-2$ is also prime will be less likely to be chosen.  It is possible that OpenSSL is using some sort of random prime generation strategy like this.  If it is, then this affects the coupon collector's calculation, and we'd expect to see somewhat more repeats.  So, your observed numbers are consistent with this hypothesis.  If this is how OpenSSL is generating primes, it is a deviation from the uniform distribution on safe primes, but this deviation is not believed to cause any security problems.  The number of possible safe primes is still ginormous (the entropy of the distribution is still plenty large), so there's no known way to take advantage of any non-uniformity that results.

This gives you some hypotheses and potential explanations you could test further.  An authoritative answer might require spelunking through the OpenSSL code (which is not much fun at all!).


Implementing secret reconstruction in Shamir's Secret Sharing I am trying to implement Shamir's secret sharing in C++.
I have got the generation of shares working.

However, I am very confused with the reconstruction of shares. I get the part on how three users can reconstruct the secret. But what if there are more than 3 users needed to reconstruct the secret? How do I implement the formula then?

Any help would be appreciated.

Suppose $s_0, s_1, s_2, \ldots, s_{k-1}$ are
elements from the finite field you are working in, where $s_0$ is the secret
to be shared, and the $s_i, i > 0$ are randomly chosen nonzero elements of
the field. Then, the polynomial used to construct the shares is
$$S(x) = s_0 + s_1x + s_2x^2+ \cdots + s_{k-1}x^{k-1}$$ and the shares
themselves are $y_i = S(x_i), 1 \leq i \leq n$ where the $x_i$ are
$n$ distinct nonzero elements of the field. Note that $n$ must be at least as
large as $k$, and that the polynomial $S(z)$ can be recovered
from any $k$ of these $n$ shares. This is commonly done using
Lagrange interpolation as has been already pointed out in the other
answers.  Assuming without loss of generality that $y_1, y_2, \ldots, y_k$
are the shares available for reconstruction, $S(x)$ is a weighted
sum (or linear combination) of $k$ different
polynomials $g_i(x)$.  We have
$$\begin{align}
S(x) &= \sum_{i=1}^k y_i \cdot g_i(x)\\
&=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{x-x_j}{x_i-x_j}\\
&= y_1 \frac{(x-x_2)(x-x_3)\cdots(x-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)}
+ y_2 \frac{(x-x_1)(x-x_3)\cdots(x-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\
&\qquad
+y_3 \frac{(x-x_1)(x-x_2)(x-x_4)\cdots(x-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)}
+\cdots\\
&\qquad
+y_k \frac{(x-x_1)(x-x_2)\cdots(x-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})}
\end{align}$$
Notice that each $y_i$ is being multiplied by the polynomial
$$g_i(x) = \frac{1}{c_i}(x-x_1)(x-x_2)\cdots(x-x_{i-1})(x-x_{i+1})\cdots(x-x_k)$$
which has as factors all terms of the form $(x-x_j)$ except $(x-x_i)$, and
the constant $c_i$ is given by
$$c_i = (x_i-x_1)(x_i-x_2)\cdots(x_i-x_{i-1})(x_i-x_{i+1})\cdots(x_i-x_k).
\tag{1}$$
In other words, $g_i(x_i)=1$ and $g_i(x_j)=0$ for all $j \neq i$.

So there is a lot of calculation required, and care must be exercised
when writing the computer program that carries out these calculations.
But note that we really don't need to compute the entire polynomial
$S(z)$  since all we want to find is the secret $s_0 = S(0)$. This
saves us a fair amount of work because we have
$$\begin{align}
S(0) &= \sum_{i=1}^k y_i \cdot g_i(0)\\
&=\sum_{i=1}^k y_i \prod_{j=1, j\neq i}^k\frac{-x_j}{x_i-x_j}\\
&= y_1 \frac{(-x_2)(-x_3)\cdots(-x_k)}{(x_1-x_2)(x_1-x_3)\cdots(x_1-x_k)}
+ y_2 \frac{(-x_1)(-x_3)\cdots(-x_k)}{(x_2-x_1)(x_2-x_3)\cdots(x_2-x_k)}\\
&\qquad
+y_3 \frac{(-x_1)(x-x_2)(-x_4)\cdots(-x_k)}{(x_3-x_1)(x_3-x_2)(x_3-x_4)\cdots(x_3-x_k)}
+\cdots\\
&\qquad
+y_k \frac{(-x_1)(-x_2)\cdots(-x_{k-1})}{(x_k-x_1)(x_k-x_2)\cdots(x_k-x_{k-1})}\\
&=  \sum_{i=1}^k y_i \cdot (-1)^k\frac{x_1x_2x_3\cdots x_k}{x_i\cdot c_i}\\
s_0 &= (-1)^k (x_1x_2x_3\cdots x_k) \sum_{i=1}^k \frac{y_i}{x_i\cdot c_i}
\end{align}$$
So now the task seems a little easier. We need to
compute $x_1x_2x_3\cdots x_k$ only once using $k-1$ multiplications,
each $c_i$ has to be calculated separately and needs $k-1$ subtractions
and $k-2$ multiplications. We multiply $c_i$ by $x_i$ and then
do the division $y_i/(x_i\cdot c_i)$.  The hard part in all this is thus writing
the code for computing each $c_i$.  And of course we must remember that
all this is using finite-field arithmetic so that we must use operations
or subroutine calls as described in the answer by Ilmari Karonen.


specific scenario question relating to using NACL crypto_box in a protocol Scenario 1: SenderA sends message1 to ReceiverB

message1 is encrypted using NACL crypto_box using SenderA secret key and ReceiverB public key.

we understand that the NACL crypto_box authenticator proves to ReceiverB that message1 originated from SenderA.

we understand that ReceiverB cannot prove to a third party that message1 originated from SenderA because ReceiverB could have calculated the same authenticator. For our purposes this is a good thing.

Scenario 2:

AttackerA steals ReceiverB secret key and is also able to stage a man in the middle attack

We understand that AttackerA can now read all messages addressed to ReceiverB. We also understand that AttackerA can now impersonate ReceiverB and send out messages as ReceiverB. We accept that this may happen and we can manage the consequences.

What we cannot manage and must remain valid is that ReceiverB can always prove that any message received from SenderA (intercepted by AttackerA or not) has indeed originated from SenderA. Is there anyway that AttackerA can change an existing message from SenderA and still make it appear to ReceiverB as a valid message from SenderA?

Thank you

Yes, the attacker does have the ability to make messages to appear to be from SenderA. In the end, the crypto_box functionality relies on a MAC, not a signature. That means that it depends on a shared secret key, rather than a private key for message authenticity. As explicitly stated by the protocol, this allows any message to be signed if you possess just one of the private keys. Because in that case you can calculate the shared secret key and - of course - any MAC generated by the shared secret key.

If you require that messages are authentic even if the key of the receiver is lost then you need to use a signature as well. Generally you would then have to use sign-then-encrypt to create a secure protocol, especially if you consider that private keys may get known by the attacker(s) of the system. Obviously the public keys need to be trusted in any scenario.


What is a nonce-respecting adversary? The NORX8 paper says

  It is assumed that adversaries are nonce-respecting.

What is a nonce-respecting adversary?

We call an adversary A nonce-respecting if it never repeats a nonce

Source: Nonce-Based Symmetric Encryption

This is defined in the context of the IND-CPA game.


Why would you want to keep the Initialization Vectors Public? So I was researching Initialization Vectors (IV) and even took a look at this thread... What is the main difference between a key, an IV and a nonce? ,but I was hoping that I could get some clarity.
Everyone keeps saying they IVs need to be public because the recipient of a cryptographic message will need to first decrypt the cipher text with the cryptographic key, and then the recipient must have the IV to derive the original plaintext message... so whats the point of having the IV public if its there to increase confidentiality.. like if a threat-actor has the key then they can grab the plaintext straight up..
Please let me know if I am completely off.

@kelalaka's comment answers this very succinctly, but in the event that a slightly more in-depth explanation helps, here's my stab at it.

The initialization vector is to encryption as a salt is to salted-hashing/key-derivation.  It ensures that if in a given protocol the same values are used multiple times, a different initialization vector can allow the output to still appear random instead of repeating.
With salted hashing (or key derivation) you are using a known deterministic process to generate an output values.  The salt adds additional entropy to help ensure the result is apparently random.  If the same values is hashed twice without a salt, the hash is the same.  When a unique salt is added to each we help ensure that the outputs are different. Even if the output is coincidentally the same (usually extremely unlikely), we introduce doubt that even if the outputs are the same that the original input was the same.
Encryption needs to be reversible and as a result the algorithms are similarly deterministic.  And in many protocols keys are re-used to encrypt many messages.  In the event that the message is encrypted twice with the same key, we risk revealing that fact by producing the same output.  To avoid this, we include the initialization vector.  When a unique initialization vector is used for each message we again help ensure that the outputs are different.  And again even if the outputs are the same, the fact that a different initialization vector was used makes it extremely unlikely that the original message is the same.
Finally, it's also important to note that the fact that IV is tied to a given act of encryption means that it is not always practical to agree to one ahead of time as you would for a key.  In addition, if the key is still secret, getting it to the recipient is all that matters, as that is what you are relying on to keep your encrypted data safe.  So transmitting it publicly isn't a problem.  It's effectively just a parameter of the algorithm you used to encrypt the message.


Is it necessary to stretch/derive an AES key when I already have enough bytes from a 'cryptographically secure RNG'? I'm using AES-CBC-256 with PKCS#7 compatible padding. I already have 32 bytes that come from a 'cryptographically secure random number generator'. In this scenario, does it make sense to use PBKDF2 to derive the key eventually used for encryption/decryption?

My scenario is that I need to port old code to a new stack. It all works fine, but I haven't yet implemented key derivation. In the old lib, the input is 32 random bytes + 32 bytes salt (all generated using https://www.cryptopp.com/docs/ref/class_auto_seeded_random_pool.html for the initial random bytes), which is treated as 'password', and PBKDF2 with 65536 iterations is used to derive the final key.

I thought PBKDF2 is supposed to derive a bigger secret from a short user password, but here it is used to derive a 32 byte secret from 2 * 32 byte blocks.

I get my 32 bytes from what is considered a 'cryptographically secure random number generator', which would mean I already have enough entropy. Do I need to derive the key? Does is add any security?

You're right. Unless the software is doing something very peculiar, which should be very apparent when reading the code and documentation, and I can't imagine what it could be, the salt generation and the application of PBKDF2 are unnecessary.

If you have 32 bytes from a cryptographically secure random generator, you can use these 32 bytes as an AES-256 key. A CSRNG is as good as it gets: it's uniformly random and non-guessable.

You would use a (“plain”, non-stretching) key derivation to obtain a key deterministically from some inputs which are not necessarily uniformly random, but have sufficient entropy. A typical case that requires a key derivation step is the output of a Diffie-Hellman key exchange algorithm: it needs to be deterministic so that both parties calculate the same secret key, and you can't use the output of the DH computation directly because it's a number with some mathematical properties and so it isn't uniformly distributed. Another case that requires key derivation is when you have some secret material of limited length (but enough so that it can't be found by brute force: at least 128 bits), and you want to construct multiple keys whose total length is more than the secret material.

A CSRNG takes an entropy source as input and applies a pseudorandom computation (CSPRNG: cryptographically secure pseudo-random number generator) to produce random output. A key derivation function (KDF) takes input and applies a pseudorandom computation to produce pseudorandom output. A CSPRNG and a key derivation function have fairly similar security properties: as long as the adversary doesn't see the secret input, even if the adversary sees part of the output, they can't figure out anything about the part of the output that wasn't given to them. It wouldn't make sense to just chain them. It can make sense to chain them in combination with some third thing, for example using a CSRNG to generate a public salt and a KDF to combine this public salt with a secret key to generate another secret key, or using a KDF to generate a seed for a CSRNG which then gets used by a subsystem that doesn't have access to the original KDF anymore.

A stretching key derivation function (such as PBKDF2) is useful when the input has low entropy. “Low entropy” means that the input is plausibly guessable through brute force. A CSRNG output has maximal entropy for its length, and 128 bits (16 bytes) is enough to put it well outside the realm of brute force guesses. (Quantum cryptanalysis might raise the bar to 256 bits in the future.) Key stretching is used for secrets that are short enough to be memorable, typically passwords or passphrases. The only reason why you'd need to apply key stretching to the output of a CSRNG is if this output was deliberately kept short to be memorized as a password (presumably in a form encoded suitably for humans, such as a string of printable characters or a list of words).

Taking 64 bytes from a CSRNG and passing them through PBKDF2 doesn't make any sense. Just use the CSRNG output as a key. The use of PBKDF2 isn't a direct security risk, but it hurts performance and it increases the attack surface. Beware that if the current software does this, it indicates that the authors didn't understand what they were doing and there may be other problems that are actually security flaws.


What's the consequence of having a short IV? Is one mode better in that case? I've read lots about null-length IVs being bad for most modes. In a scenario where passing a 128-bit IV along with each message isn't feasible, how would generating the IV from a smaller passed-along value impact the strength of security?

Each user will have their own symmetric key that does get re-generated periodically (maybe only hundreds or thousands of messages for each key, each message maybe hundreds or rarely thousands of bytes). If I randomly generate 16 or 20 bits, hash that using SHA-256 and use the first 128 bits as an IV, how does that impact the overall security?  Is it now in effect 16 or 20 bits?

Would adding additional information – that both the server and the user know – into the hash help?  Are there modes that would be better than others for this scenario?  I've read about Synthetic Initialization Vector (SIV) mode being resistant even if there's no IV, however from what I understand it generates a tag of the block size which defeats my purpose. Can’t I send the tag and still encrypt, while only losing authentication?

The point of the IV is to prevent the same (key,IV) from ever being used for two different messages in practice. This is an absolute requirement for stream ciphers or block cipher modes such as CTR that are effectively stream ciphers, because re-using the same (key,IV) pair lets an eavesdropper trivially obtain the XOR of two plaintext messages, which means they are effectively decrypted. Other modes behave somewhat differently, but the IV requirements for a mode are generally non-negotiable, and security is broken if they are not followed.

With a smaller IV, the chances of using the same (key,IV) go up dramatically. Hashing a low-bit value as you suggest does not fix this problem at all, as there are only 65k IVs possible with a 16 bit counter.

If your application cannot handle transport of at least 96 extra bits with each message, you should exchange an "IV seed" at the start of your protocol, then each side can use that as the state for a CSPRNG and generate the IV for each packet on its own. Using something like HASH-DRBG is probably simplest, you start with your IV seed, concatenate a counter with value N, hash and use the output as the IV for packet number N.
Making this scheme tolerate packet loss while never ever repeating (key,IV) is left as an exercise for the reader; see the ChaCha TLS draft RFC as an example of how packet sequence numbers are used to generate IVs.
http://tools.ietf.org/html/draft-mavrogiannopoulos-chacha-tls-02


Zero Knowledge Police Check I’m curious if there’s a zero-knowledge protocol for the following. Suppose a Passer-by is stopped by a Vigilante who has a list of wanted criminals. Can the Passer-by prove he has a valid ID and he’s not on the list without disclosing his identity?

Assume the ID is a bunch of data signed by an authority in some way, anticipating just such a situation (this authority values liberty very much). Vigilantes must do no better than chance to distinguish between non-wanted Passers-by after arbitrarily many rounds of the protocol.

It’s also interesting if this is possible without the Passer-by learning the contents of the list.

Yes, you can certainly construct this with zero-knowledge proofs of knowledge, some one-way function $OW$ (lets say bijective for simplicity), and a signature schemes $\Sigma$.

A simple protocol

Citizens choose a random preimage $x$ of the one-way function. Their secret key is $x$, their public key is $y = OW(x)$.
Citizens also store a state-issued signature $\sigma$ on $y$.
You can prove arbitrary NP statements in zero-knowledge, i.e. statements of the form "I know $a,b,c$ such that [poly-time checkable statement about $a,b,c$]".
So assume the citizen is approached with a list of $y_1,\dots,y_n$ of wanted criminals' public keys.
Both parties can then set up a zero-knowledge proof in which the citizen proves

  "I know $x,y,\sigma$ such that $y = OW(x)$, and $\sigma$ is a valid
  signature on $y$, and $y\notin \{y_1,\dots,y_n\}$".

Zero-knowledge guarantees that the vigilante does not learn the values of $x,y,\sigma$. The proof of knowledge property guarantees that the citizen can only make the vigilante accept if he actually knows $x,y,\sigma$ with these properties. This (kinda) prevents a person on the list from winning the proof - they need some honest/unlisted person's secret $x$ and their signature $\sigma$, which only the honest person knows.

Drawbacks

In practice, this simple scheme has limited applicability because wanted persons only need to convince any unlisted person to give them a copy of their $x,\sigma$. If they have that, they can easily pass the police check.
The underlying problem is that while physical IDs are (ideally) hard to copy, a digital identity is just a bunch of bits that is easily duplicated and handed over to another person.
You can probably make all of this more elaborate and give each person a trusted device that stores $x,\sigma$ in an unclonable way. But as soon as you have that, the zero-knowledge protocol becomes somewhat overkill - the police could just ask the trusted device whether it sees its identity on the list.

Hiding the list

In the scheme listed above, the list contains no identifying information about the listed people (just a random value). You can however recognize values you have already seen before (e.g., friends). You could hide the list, for example, as follows:

Assume for concreteness that the one-way function maps an integer $x$ to $OW(x) = g^x$ for some fixed $g$ in some prime-order group $\mathbb{G}$ where decisional Diffie-Hellman is hard.
The signature stuff stays the same and the list is comprised of the criminals' public keys $g^{x_1},\dots,g^{x_n}$.
Before showing the list to the citizen, the vigilante now randomizes the list to look random:

The vigilante chooses a random $r\leftarrow\mathbb{Z}_p$.
He then hands $h = g^r$ and $h^{x_1},\dots,h^{x_n}$ to the citizen.
Under the decisional Diffie-Hellman assumption, the elements $h^{x_i}$ are indistinguishable from random group elements. [1]
The citizen can still prove in a zero-knowledge proof of knowledge that he knows $x,y,\sigma$ such that $y = g^x$, $\sigma$ is a signature on $y$, and $h^x \notin \{h^{x_1},\dots h^{x_n}\}$.

[1]: of course, this only holds if the secret key $x_i$ of the entry is unknown to the citizen. Necessarily, each citizen must be able to recognize himself on the list. It's just all other entries that now look random.


Extending pseudorandom generator by one bit using exclusive-or of previous bits Is it possible to have a pseudorandom generator that extends its output by 1 bit by simply appending the exclusive-or of all the previous bits?

I know the output of a pseudorandom generator is indistinguishable from random, so would the appended bit still retain its pseudorandom property? Or is this not pseudorandom because the last bit is deterministic?

This allows for an easy distinguishing attack: Let $R\colon\;\{0,1\}^n\to\{0,1\}^m$ denote a pseudo-random generator, that is, if $x$ and $y$ are uniformly distributed random variables in $\{0,1\}^n$ resp. $\{0,1\}^m$, there is no polynomial-time algorithm that distinguishes $R(x)$ from $y$ with non-negligible probability.

Let $R'\colon\;\{0,1\}^n\to\{0,1\}^{m+1}$ denote the generator whose output is extended as specified in the question. An attacker, given a black box $z$ that contains either $R'(x)$ (for $x$ uniformly random in $\{0,1\}^n$) or $y$ (uniformly random in $\{0,1\}^{m+1}$), may then calculate the parity (exclusive or) of $z$'s first $m$ bits and compare it to the last bit of $z$. If they match, the attacker guesses that $z$ is $R'(x)$, else he guesses that $z$ is $y$.

It is fairly obvious that, using this strategy, the attacker always guesses correctly when given $R'(x)$. In the other case, when given $y$, the strategy has a success probability of exactly $\frac12$, since the last bit of a random bit string is also random and may thus with equal probabilities either match (in which case the attacker guesses wrong) or mismatch (in which case the attacker guesses right) the parity.

Therefore, the attacker has a success probability of $$\frac12\cdot1+\frac12\cdot\frac12=\frac34$$
in distinguishing $R'$ from random, which is non-neglibly greater than $\frac12$.

A less direct argument is: If the extension described in the question was possible, one could iterate the construction multiple times without losing the pseudo-randomness property. However, after the first such extension, the parity of the output is always zero, hence all further appended bits are zero. Clearly, a generator whose output always ends in a string of zeroes is not pseudo-random.


Verifiable Encryption of a Pedersen Commitment Can the Verifiable Encryption of a Discrete Logarithm scheme of the paper https://www.shoup.net/papers/verenc.pdf (page 19) be used to verify that a ciphertext encrypts the same value committed in a Pedersen Commitment?

Yes. Say the message is $m$ and the commitment is $C$ such that $C = g^mh^r$. Since you can use verifiable encryption to prove that a given ciphertext encrypts $m$ in relation $g^m = y$ where $g$ and $y$ are also public knowledge, using the Schnorr protocol you can prove that the $m$ in relation $g^m = y$ is same as the $m$ in $C$


Is AES solvable by reducing to SAT? Consider a known plaintext attack on AES — just so we have an actual system of equalities that we can feed to a SAT solver.

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key?

After reading through these set of slides, I assume the answer is yes, but that it is computationally even more costly than brute force, making it impractical.

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key?

Almost yes. It will produce some correct key — there might be more than one.

(It should quite plausibly be unique given "enough" plaintext-ciphertext samples, but this need not be the case in general.)

Generally, computing the key in a known-plaintext scenario is in $\mathbf{NP}$, hence can by definition be reduced to any $\mathbf{NP}$-complete problem such as $\mathrm{SAT}$. If this is done correctly, solving the $\mathrm{SAT}$ instance is bound to produce a correct key — but fortunately, doing so is not at all practical to the best of our current knowledge.

(If it turned out that $\mathbf P=\mathbf{NP}$, this would potentially change that picture a bit, but in that case we are doomed anyway.)

Therefore the short answer is: Yes, but it doesn't help.


Is security of zk-SNARKS related to the size of the arithmetic circuit they evaluate? In the context of zk-SNARKS, we are given an arithmetic circuit $C$, public outputs $y_1, \ldots, y_n = \mathbf{y}$ and some public inputs $x_1, \ldots, x_ℓ$. The prover wants to prove knowledge of some extra secret inputs $s_1, \ldots, s_m$ such that if one were to evaluate the circuit $C$ on inputs $x_1…,x_ℓ,s_1,…,s_m$ the result would be $\mathbf{y}$.

In some application like in HALO, the recursion property depends on the size of the arithmetic circuit being evaluated. However it does not seem to be related to the security of the scheme, fixed at roughly 128bits. If so, given a certain security level $\lambda$, can one create a zk-SNARK with any circuit size? (granted that the circuit does verify the "valid assignments" we want provers to have)

I think there is not necessarily immediate relationship between security of zk-SNARKs and the size of the arithmetic circuit. Mostly the security of zk-SNARKs depends on your security parameter, your cryptographic assumptions and what kind of security properties you want to achieve. In contrast, the size of the arithmetic circuit is more related to the efficiency of zk-SNARKs, such as prover/verifier running time and proof size. For sure sometimes if you need some stronger security property, for example, you want to achieve universal and updatable CRS, this would lead to a larger arithmetic circuit


Different ways of building a ChaCha20-based RNG Let's say you're building RNG with ChaCha20 and the fast key erasure technique.  There seem to be a few ways to do it.

The reference implementation in the SUPERCOP benchmarking toolkit looks like this:

#define KEYBYTES 32
#define OUTPUTBYTES 736

int crypto_rng_chacha20(
        unsigned char *r, /* random output */
        unsigned char *n, /* new key */
  const unsigned char *g  /* old key */
)
{
  unsigned char x[KEYBYTES + OUTPUTBYTES];
  crypto_stream_chacha20(x,sizeof x,nonce,g);
  memcpy(n,x,KEYBYTES);
  memcpy(r,x + KEYBYTES,OUTPUTBYTES);
  return 0;
}

How often should I replace the key?  The SUPERCOP implementation replaces the 32-byte key every 768 bytes.
What about the nonce and counter?  The SUPERCOP implementation sets the nonce to zero and resets the counter to zero every time the key is replaced.  What about treating the nonce/counter similar to the key and periodically replacing them with ChaCha20 output?  (Except for a few counter bits that we need to crank to get 768 bytes of output.)
The SUPERCOP implementation replaces the key with the first 32 byte of the 768-byte sequence.  Can I use the last 32 bytes instead?  That would allow my implementation to keep less state.
What about replacing the key incrementally?  For example, instead of fully replacing the key with the first 32 bytes of every 768, what if I used the first 4 bytes of every 96 and incrementally replaced the key?

Note: I'm asking this question primarily to get a deeper understanding of how things work.  In practice, I'd just copy the SUPERCOP implementation.

How often should I replace the key?  The SUPERCOP implementation replaces the 32-byte key every 768 bytes.

It's a latency/throughput tradeoff.  Generating a longer batch of output raises the maximum latency of any query to the PRNG but also increases the throughput by using proportionally more CPU cycles for generating data and fewer for generating intermediate keys.  Pick the rate that serves your needs.  Maybe you should replace it after every 32-byte output so the latency is guaranteed to be bounded by a single ChaCha call.  Maybe you should replace it after every kilobyte of output to get better throughput.  Or just use 768 bytes like SUPERCOP.

  What about the nonce and counter?  The SUPERCOP implementation sets the nonce to zero and resets the counter to zero every time the key is replaced.  What about treating the nonce/counter similar to the key and periodically replacing them with ChaCha20 output?  (Except for a few counter bits that we need to crank to get 768 bytes of output.)

Additional implementation complexity for no security benefit.

  The SUPERCOP implementation replaces the key with the first 32 byte of the 768-byte sequence.  Can I use the last 32 bytes instead?  That would allow my implementation to keep less state.

Yes, but your results won't be compatible with SUPERCOP which may matter if you ever care about reproducibility or interoperability.

  What about replacing the key incrementally?  For example, instead of fully replacing the key with the first 32 bytes of every 768, what if I used the first 4 bytes of every 96 and incrementally replaced the key?

No.  Bad.  Do not.  My head hurts.


What does the "description of group $G$" includes? I was reading here:second discrete log meaning in the solution and also here:key generation, first point where the say given $G$ (or its description). My question is what does this description includes?

For example here he is making the differentiation that in Elliptic Curves this group description makes it harder to solve the discrete log problem.
Is it because for example in RSA the group elements are known beforeh and so their group description is just all numbers mod n while in the EC the group elements are not known and you are only given the EC parameters (i am not sure about the last one)?

My question is what does this description includes?

The information that describes what elements are in the group, and how to perform the group operation.  In a $\mathbb{Z}_n^*$ group, the value $n$ may be sufficient, for an Elliptic Curve group, that'd include the curve equation (e.g. for Weierstrass curves, the values $a$, and $b$ in the equation $y^2 = x^3 + ax + b$), and the finite field the group is defined over.  Actually, in practice, we typically don't generate curves on the fly; it is far more typical to say "I'm using P256" or "I'm using Curve25519".

  Is it because for example in RSA the group elements are known before

No, it's because that the group $\mathbb{Z}_n^*$ has additional properties that generic groups don't have, and an attacker can exploit these properties to make solving the discrete log problem faster.

One such property is that fact that we can construct a modest-sized list of elements $p_0, p_1, ..., p_i \in \mathbb{Z}_n^*$ such that, given a random element of $x \in \mathbb{Z}_n$, we have a nontrivial probability of being able to quickly find the values $e_0, e_1, ..., e_i$ such that $x = p_0^{e_0} \cdot p_1^{e_1} \cdot ... \cdot p_n^{e_i}$; we don't know how to do that with a generic group, and it turns out to be useful in the discrete log problem.

And, in case you're wondering what that quick algorithm is, well, we set $p_0, p_1, ..., p_i$ to the first $i+1$ primes, and given $x$, we treat it as an integer (rather than an element of $\mathbb{Z}_n^*$) and do a quick factorization on it, using an algorithm that is designed to be find small factors (and if it fails because of a large factor, we can detect that quickly).  A nontrivial fraction of $x$ turn out to be smooth, and hence this works sufficiently often.


Is the RSA signature attack from Desmedt and Odlyzko practical? I would like to understand how the attack from the Desmedt and Odlyzko on RSA signatures (and subsequents works) can be made practical. This attack describes a way to forge the signature on a new message using Gauss elimination. The problem is that a message is hashed before the private exponent is applied, so maybe I have missed something... Why is this attack practical?

Thank you.

TL;DR: Yes, on narrow or some ad-hoc deterministic RSA padding, which must not be used.

The Desmedt and Odlyzko attack on RSA signatures [DO1985] assumes a deterministic RSA signature scheme with appendix that, for RSA key $(N,e,d)$, signs messages $M$ with signature $S=(H(M))^d\bmod N$ for some public function $H$ with $H(M)<2^k$ and $k\ll\log_2(N)$, and verifies alleged signature $S$ by checking that $S^e\bmod N$ matches $H(M)$. The attack is computationally feasible for $H$ a $k$-bit cryptographic hash, up to at least $k=200$ [CNST2016], and I believe $k=256$, perhaps more. The size of $N$ and $e$ are almost immaterial.

The attack computes the signature of a message $M_0$ chosen by the adversary from the signature of many other messages $M_i$ chosen by the adversary, and the public key $(N,e)$. All theses messages must obey one constraint: be smooth; that is, have all their prime factors below a "smoothness" bound (except perhaps for one of two larger prime factors shared with other $M_{i'}$, $i'\ne i$ (these large prime and two large primes variants of the attack parallel similar variants in MPQS, see [LM1990] as used in the landmark [AGLL1994] ).

The basic attack combs many messages $M$ to find these such that $H(M)$ has all its primes factors below bound $B$, and forms a large sparse matrix with one line for each such $M_i$, one column for each prime $p_j$ below $B$, the multiplicity of prime $p_j$ in $H(M_i)$ at the intersection $c_{i,j}$, and significantly more lines than columns.

By Gaussian elimination or a method to the same effect, it is found coefficients $u_i\in\mathbb Z$ for each line, such that $\forall j,\;0=\displaystyle\sum_{i\ge0}u_i\,c_{i,j}$, and $u_0=-1$. It follows that $\displaystyle\prod_{u_i<0}H(M_i)^{-u_i}\;=\;\prod_{u_i>0}H(M_i)^{u_i}$, and thus $H(M_0)\equiv\displaystyle\prod_{u_i\ne0,\,i>0}H(M_i)^{u_i}\pmod N$.

By raising the later to the power $d$, it comes that the signature $S_0$ of $M_0$ can be obtained from the signatures $S_i$ of some of the other $M_i$, as
$$S_0\equiv\prod_{(u_i\bmod e)\ne0,\,i>0}S_i^{u_i}\;\;\prod_{(u_i\bmod e)=0,\,u_i\ne0}H(M_i)^{u_i/e}\pmod N$$

The Gaussian elimination can be directed to reduce the number of $S_i$ needed at the expense of needing more smooths; and that's easier for small $e$.

The attack is an existential forgery, but could be entirely practical if narrow deterministic RSA signature padding was used (contrary to all serious security guidelines). Consider an hypothetical automatic file timestamping server that upon receiving a file hashes it using SHA-384, then produces and signs using $S=(\operatorname{SHA-256}(M))^d\bmod N$ a message $M$ of the form:

At 2017-09-21 09:12Z I received a file which SHA-384 hash in base64 is RpzByokphjFifbPgFhR2vFnqbHvqA283Ud8sN0ic61fxd5hyQdXo3VofgkrSb0fz

The adversary wants a certain file backward time-stamped. S/he:

Searches suitable past dates and/or equally useful variations of that file such that the message $M_0$ that the server would have generated for that (variation of that) file has smooth SHA-256.
Generates many small files / future dates pairs such that the resulting $M_i$ have smooth SHA-256.
Conducts the Gaussian-elimination-on-steroids part of the Desmedt and Odlyzko attack, which yields a subset of the original $M_i$ she needs signed.
Obtains their signature by asking for a time-stamp of the appropriate small files at the beginning of the appropriate minute.
Succeeds! The signature for $M_0$ can be computed from the signatures obtained at the previous step, and authenticates $M_0$ as a backward time-stamp that the server has not and would not have produced.

Note: The attack does not require computing any hash preimage or finding any collision: all the $M_i$ including $M_0$ are determined from the file and date they are related to, then hashed using SHA-256, then this hash is tested for smoothness.

The attack requires relatively few computations of SHA-384, but many computations of SHA-256 and fast ways to test if they are smooth (smooths are rare). Most of the computational effort is there, I believe.

The attack is thwarted if either:

The hash is wide, ideally as wide as $N$ is; this is the exact strategy of RSA-FDH, is also used by RSASSA-PSS, and (in a bastardized and occasionally failing way) by ad-hoc RSA signature schemes.
The signer inserts something unpredictable into what it sign; this is the strategy of probabilistic signature schemes like RSASSA-PSS and ISO/IEC 9796-2 scheme 2, and their de-randomized variants. This is also used by some responsible Certification Authorities, which generate a random or otherwise unpredictable certificate serial number when using ad-hoc RSA padding like RSASSA-PKCS1-v1_5, or less than ideal hashes like SHA-1.

The Desmedt and Odlyzko attack [DO1985] is a sub-component of other attacks on wide deterministic RSA signature padding, including the first break [CHJ1999] of the (withdrawn) ISO/IEC 9796:1991, and the break [CNST2016] of ISO/IEC 9796-2 scheme 1 (aka 1997).

References:

[DO1985]: Yvo Desmedt and Andrew M. Odlyzko; A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes, in proceedings of Crypto 1985.
[LM1990]: Arjen K. Lenstra, Mark S. Manasse; Factoring with two large primes, in proceedings of EuroCrypt 1990.
[AGLL1994]: Derek Atkins, Michael Graff, Arjen K. Lenstra, Paul C. Leyland; The magic words are squeamish ossifrage, in proceedings of AsiaCrypt 1994.
[CHJ1999]: Don Coppersmith, Shai Halevi, Charanjit Jutla; ISO 9796-1 and the new forgery strategy, circulated as an IEEE P1363 Research Contribution, 1999.
[CNST2016]: Jean-Sebastien Coron, David Naccache, Mehdi Tibouchi, Ralf-Philipp Weinmann: Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures in Journal of Cryptology, 2016 (first version in proceedings of Crypto 2009); section 3 makes a modern exposition of the Desmedt and Odlyzko attack applied to RSA signature.


Composing two one-way functions such that the result is not a one-way function Is it possible to have two distinct one-way functions (called, say, $h$ and $g$) such that their composition $h \circ g = [\, x \mapsto h(g(x)) \,]$ is not one-way?

The function $f$ introduced by Maeher in this answer to a related question should also do the job here (as both $g$ and $h$).  For convenience, let me quote that answer here:

Assume that a one-way function $h$ exists where in- and output length are the same. We call this length $n/2$. I.e. we have a one-way function $$h : \{0,1\}^{n/2} \to \{0,1\}^{n/2}.$$
From this function, we now construct a new function
$$f : \{0,1\}^{n} \to \{0,1\}^{n}$$ as follows:
$$f(x_1\Vert x_2) = 0^{n/2}\Vert h(x_1),$$
where $|x_1|=|x_2|=n/2$.

As shown in Maeher's answer, $f$ is one-way if $h$ is.  However, $f(f(x)) = 0^{n/2}\Vert h(0^{n/2})$ is constant, independently of $x$ (except for its length $n$), and thus finding pre-images is trivial.


Why do we need password in a server which uses TLS? Suppose a server uses TLS to protect communication between us and the server.

I observe that in the TLS handshake protocol, password is not mentioned anywhere.

Then why do we need to have a password? What is its purpose?

So that the server knows who you are.

After all, TLS protects the communication; however anyone can initiate a TLS connection to the server (unless the server insists that client authentication must be used; they rarely do).

So, if the server needs to make any decision based on who the client is, it needs to find that out itself; TLS usually won't provide client credentials.


Why are some key stretching methods better than others? I'm trying to understand why some key stretching methods are better than others.
The wikipedia article presents 3 different key stretching methods:

  A collision prone simple key stretching method:

key = hash(password)
for 1 to 65536 do
key = hash(key)

  A better simple key stretching method. ("+" denotes the operation of concatenation):

key = ""
for 1 to 65536 do
key = hash(key + password)

  Even better method with a salt:

key = ""
for 1 to 65536 do
key = hash(key + password + salt)

So, I was wondering why #1 is the weakest of the 3 while #3 is the strongest. My understanding is the following :

The problem with #1

A != B // 2 messages
hash(A) = hash(B) // It's possible in theory
hahs(hash(A)) = hash(hash(B)) // Same thing again…

So, it is easier to find 2 hash that gives the same end result, because if at any time in the hash chain they get the same result that result will not change afterward.

How #2 solves it :

A != B
hash(A) = hash(B)
hash(hash(A) + A) != hash(hash(B) + B)

Since only the last hash matter instead of every hash, we are less likely to get a collision.

The problem with #2

It is still vulnerable to rainbow table attack. That's why we need to use a salt like in #3.

Now… Is there a problem with #3, and/or what makes password hashing like PBKDF2 and bCrypt better key stretching methods than #3?

On the non technical side, the main reason for choosing PBKDF2 or BCrypt is that they're commonly used. This means they have seen more analysis, reducing the risk of a dumb mistake and it's easier to defend them when somebody questions your choice.

What I dislike about your third variant is that it does not separate the different inputs. This isn't an issue if both key and salt have fixed length, but it's ugly. PBKDF2 has similar ugly but not practically relevant properties.

PBKDF2 has pretty similar properties to your third scheme. It has the additional feature of a variable output size, but it's so badly designed that this is more of a pitfall than an advantage. But you could always combine HDKF-Extract with your scheme if you need long outputs.

Bcrypt on the other hand has an advantage over both your scheme and PBKDF2 (used with common hashes like SHA-2): It's not friendly to GPUs. If you can afford 100ms of hashing on your CPU, the cost of a GPU based password cracker computing a hash is higher for Bcrypt than for PBKDF2. When an attacker uses an ASIC or FPGA, the advantage of bcrypt is smaller and you should consider using scrypt instead.

I also think that the need for including the password on each iteration of the hash (which you pointed out as a flaw in the first scheme) is often exaggerated. Even with a short hash like MD5 exploiting this is infeasible and becomes completely ridiculous once you use a 256 bit hash like SHA-256.


Should the signature be prefix or postfix to the message in the sign-then-encrypt scheme? Let's assume we have a message $M$ and it's signature $S$ and that $|$ is
the concatenation operator.

Should we encrypt $S|M$ or $M|S$?

Does it even matter?

Secure encryption does not care about how the data is ordered.

With the typical single use symmetric keys that hybrid encryption uses, I cannot think of a way it could matter one way or the other. With key reuse (if you used symmetric encryption on signed data), there are some cases where having the "randomness" from the signature in the first blocks might help, but that would mostly be papering over security holes.

In practice, having it at the end may be preferable if it allows for a streaming interface where the data gets encrypted and maybe even sent before all data is ready to be signed.


IV/Nonce in CTR&GCM mode of operation We know reusing IV can compromise our secrecy. I have some questions aiming to clarify the use of an IV/Nonce in CTR/GCM:

Is it OK to use the same key for encrypting plain-texts in authenticated encryption (GCM) and confidential only encryption (CTR) if we use a random IV to encrypt each plain-text? How many time we can reuse the same key in this way?
What's different between "IV" and "nonce" in CTR or GCM mode? (I know there is a counter within the algorithm, but there is some IV before the counter to encrypt each block. From Wikipedia, I thought the correct term was IV+counter instead of saying nonce?)
What is the right way to generate the IV for CTR or GCM modes? Should we use a TRNG or CSPRNG? Some comments imply the nonce shouldn't be random - why is this?

IV (initial value or initialization vector) is a vague term that describes some kind of starting value for a mode of operation that is known to both parties, and generally sent in the clear with the encrypted data (and known to the attacker)

IVs in many modes of operation have specific requirements to that mode. In some modes the requirement is that is unpredictable and (with high probability) not reused. For those modes the easiest method for IV generation is a CSPRNG, with this method IV reuse can occur due to the nature of random numbers. For CTR and derivatives, the IV must be a nonce, which is a very specific type of value, and is commonly referred to us such for these modes, as to prevent confusion regarding the requirements. NIST uses both names in the GCM spec document, but is clear on the requirements.

A different way of generating IVs that are unpredictable and also unique is to encrypt a counter value with a different key. These are the length of the block size.

A nonce (number used only once) must NEVER be reused with the same key (hence the name), since it is the plaintext input to the block cipher. Modes that use a nonce rather than a random number include OFB, CTR, and CFB. CTR has no requirement for nonce unpredictability. The nonce for CTR is generally a sequential message counter starting at 1. This also allows easy verification in some applications that a message is not received multiple times (replay attacks). The block counter is for the blocks within each message. If the nonce were chosen randomly, the probability of overlap increases with each encrypted block; this is not a problem if a record of each nonce was kept and verified to ensure it was not reused.

CTR mode generally uses a 96-bit nonce, leaving 32 remaining bits for the block counter. This gives 64GiB of output blocks per nonce before the nonce must be incremented, which is enough for the majority of uses. The secure limit on output for CTR is the secure limit for block cipher output with a given key, which for AES is a maximum of $2^{128/2}$ blocks.

The other requirement for nonces specific to GCM is that it is not all 0 bits, as that is used for GHASH, and using it can possibly allow forgeries of all authentication tags. This value is essentially the IV to the GHASH function, which is unique to each key/block cipher combination.

When used with GHASH in GCM, CTR mode has a more limited secure output, and this depends both on the size of the nonce as well as the size of the authentication tag. The smaller the tag, the fewer messages can be transmitted before attacks become successful. Additionally, using different tag lengths with the same key can lead to a loss of security. See Authentication weaknesses in GCM for details on attacks on short nonces. For GCM The maximum plaintext length is $2^{39} - 256$ bits for a given nonce.

I do not see any problem with using the same key in GCM and CTR, as long as there is no nonce overlap, and you stay within the safe block limit for AES, as well as the safe limit for the GCM authentication tag generation with a single key, and never encrypt an all 0 input. The GCM special publication (800-38D) from NIST regarding key and nonce generation however does specify that the key shall only be used with GCM and no other mode, I would be inclined to follow this advice.


Md compliment padding What padding algorithms are there that are MD-compliment so two different inputs don't pad to the same thing? Which would cause a collision in a hash function.

There are at least two different criteria for message encoding into fixed-size blocks:

no input has its encoding equal to the encoding of any other input;
no input has its encoding at the tail end of the encoding of any other input.

Criterion 1 is often used together with block ciphers for encryption or Message Authentication Codes. Usual padding techniques meeting it:

Bit padding, also known as ISO/IEC 9797-1 Padding Method 2. We append a single 1 bit to the message, then just as many 0 (possibly none) until filling a block.
Various forms of byte padding, applicable to messages already formatted as bytes (octets); most often, if the message is $n$-byte and a block is $b$-byte, it is added $p=n-(n\bmod b)$ byte(s) (thus $0<p\le b$), the last of which having value $p$; there are various conventions for the other added bytes: $0$ (ANSI X.923), $p$ (PKCS#7), random, or just unspecified.

Criterion 2 is stronger than criterion 1. It is sometime used for hashing, especially by iterating a one-way compression function, where this criteria strengthens the hash against some attacks (see this answer). A common implementation is:

Append a single 1 bit to the message (this step is customary, but has no justification AFAIK).
Append just as many 0 (possibly none) until there remains exactly $s$ unused bits in the message, for some fixed parameters $s$ (the message must have size less than $2^s$ bits); common choices are $s=64$ (MD5, SHA-1, SHA-256) and $s=128$ (SHA-512).
Append $s$ bits (thus filling the last block) coding the length of the message in bit (before padding), under some prescribed endianness convention; MD5 uses little-endian, SHA-1 and SHA-2 use big-endian.

I fail to track the original reference for criterion 2 (much less its common realization); it does not seem to be quite this way in: Ivan Bjerre Damgård, A Design Principle for Hash Functions, in proceedings of Crypto 1989; nor in its reference: Ralph C. Merkle, One Way Hash Functions and DES, in proceedings of Crypto 1989.


Why don't we have 256-bit security level digital signature schemes (in common use)? Recently (2016) I've been researching on post-quantum digital signature schemes, and read about BLISS, BLZZRD, REBLISS schemes. What I've noticed about them is that they lack a parameter set for 256-bit security level.

I went to the Wikipedia page on NSA Suite B and learned that CNSSP-15 require only 384-bit curve for digital signature. And then I clicked on this link in the reference section at the bottom of the page, and found out only ECDSA-with-SHA{256,386} required for the profile.

It baffles me. Why is 192-bit security sufficient (upper-limit if you will) for digital signatures when we have 256-bit variant of AES? And what reference backs this up?

The trivial answer is that there doesn't exist any relevant security threats that entail a requirement for long term authentication. There do however exist relevant security threats that warrant long term confidentiality.

Assume you have a document and need to prove its authenticity. If you apply a digital signature to the document, but the digital signature scheme you use is later broken, it might still be possible for you to later reestablish the authenticity of the document using other means. For instance, there might be external witnesses that can vouch for the authenticity, the document might be recorded in multiple locations, making forgeries reasonably unlikely, etc.

However, if you encrypt the document for confidentiality and the encryption scheme is broken, there is no way for you to ever reestablish reasonable confidentiality guarantees. If the document is no longer confidential, re-encrypting it obviously won't restore confidentiality.


Fast Symmetric Encryption Algorithms: My Options Basically, the question above...

I'm trying to implement encryption on the server, and I have another webserver that I can share a secret key with via TLS/SSL/HTTPS, so I do not really need asymmetric encryption.

There are many many different algorithms, but I'm looking for one that has balanced encryption and decryption performance since I'm gonna do both on the server...performance-wise, what are my options?

Thank you.

AES-GCM can be used as it provide Authenticated Encryption, no need to separately calculate MAC as the same same algorithm does that in parallel.This is hardware efficient.

For software you can use ChaCha(which is a Salsa variant stream cipher) along with Poly1305 , this combination also provide AEAD.


RSA smaller number work-out-by-hand not working - I think I made a mistake I tried out the paper/pencil explanation @ http://sergematovic.tripod.com/rsa1.html, and it seemed to make sense just fine until I came to decryption. Here is what I worked out:

Key Creation:

Choose two different prime numbers p and k:

p = 23
k = 29

Find n by calculating p * q:

n = 23 * 29
n = 667

Find z by calculating (p - 1) * (q - 1):

z = (23 - 1) * (29 - 1)
z = 22 * 28
z = 616

Pick a number k that is coprime to z:

616 % 2 != 0
616 % 3  = 0
k = 3

The public key consists of n and k:

Public Key:
n = 667
k = 3

Find a number j where (k * j) % z = 1:

(3 * 411) % 616 = 1
j = 411

(The work for this one is a bit long, so work: http://sprunge.us/HeXg, code: http://sprunge.us/YDFF?c, command: ./tiny-RSA-j-finder 3 616)

j is the secret key:

Private Key:
j = 411

Encryption:

Public key from earlier:

Public Key:
n = 667
k = 3

Choose a number p to encrypt (with the obvious requirement that it be smaller than the modulus n):

p = 13

Find the encrypted result E by calculating E = (p ^ k) % n:

(13 ^ 7) % 667 = 492
E = 492

(Again, work is long, so work: http://sprunge.us/DBFF, code: http://sprunge.us/TRdC?c, command: ./tiny-RSA-modexp 13 7 667)

Decryption:

Public Key:

Public Key:
n = 667
k = 3

Private Key:

Private Key:
j = 411

Encrypted Result:

Encrypted Integer:
E = 492

Recover the integer p by calculating p = (E ^ j) % n

(492 ^ 411) % 667 = 144
p = 144

(Same modexp algorithm, same code, work: http://sprunge.us/NiAi, command: ./tiny-RSA-modexp 492 411 667)

?:

Now here is the issue: I input 13 as p and recovered 144 instead. At first I thought I had messed up the modexp part, but I got the same results when using the University of Minnesota modexp calc @ http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html.

So did I mess up somewhere, were the original instructions wrong, and/or something else?

And more importantly, if I messed up, where did I mess up and which instruction(s) is/are wrong if the instructions were wrong?

Any help is appreciated.

PS: Yes I understand that the keysize is waaaaaaay to small to be secure IRL, however I just wanted to learn how the algorithm works.

At the encryption step, you wrote:

Public Key:
n = 667
k = 3

Input:
p = 13

Encrypted Integer:
E = (p ^ k) % n

And then mistakenly calculated:

(13 ^ 7) % 667 = 492
______^_____________

If you calculate it right using k = 3, you will get E = 196 which correctly decrypts to 13.

(as expected)


How to understand why an algorithm uses additive or multiplicative homomorphic If we take the example of LWE (Learning With Errors) how does one know if it's homomorphic by addition or multiplication?

The Why question has a deep answer since it is deep research! The How question is a lot easier. To check that how an encryption scheme is homomorphic look at the general homomorphism;
Let $f:A\to B$ be a map that preserve the structures.
$$f(x \cdot y) = F(x)\cdot f(y)$$ then we say $f$ is homomorphism ( in a very simple terms).
This is a bit different in FHE settings since schemes are semantically secure ( most of them) so the comparison cannot be made on the range ( encrypted message space) so you need to decrypt to see that.
To check the addition ( or any operation that FHE ( or partial FHE) uses) take two different inputs $x_1 \neq x_2$ and apply the rule where $\mathcal{E}$ stands for FHE encryption and $\mathcal{D}$ stands for FHE decryption.
$$\mathcal{E}(x_1 + x_2) = \mathcal{E}x_2) \boxplus \mathcal{E}(x_1),$$ we cannot check this, so we need decryption.
$$x_1 + x_2 = \mathcal{D}\left(\mathcal{E}(x_2) \boxplus \mathcal{E}(x_2)\right)$$
As done for addition this can be done for any operation. Why $\boxplus$ instead of $+$, the operation on the encrypted messages doesn't need to be an addition for addition.
So the general rule, let $\oplus$ be the operation that you want to test its homomorphism. Then
$$x \oplus y = \mathcal{D}\left(\mathcal{E}(x) \boxplus \mathcal{E}(y)\right)$$ where $\boxplus$ can be equal to $\oplus$  or not.
For example in Goldwasser–Micali cryptosystem
\begin{align}
\mathcal{E}(b_1)\cdot \mathcal{E}(b_2) &= x^{b_1} r_1^2 x^{b_2} r_2^2 \;\bmod\; n \\[6pt]
&= x^{b_1+b_2} (r_1r_2)^2 \;\bmod\; n \\[6pt]
&= \mathcal{E}(b_1 \oplus b_2).
\end{align}
the multiplication of the ciphertext is equal to the X-OR of the plaintext this is mostly used in fingerprint validation on encrypted data.
In the Paillier cryptosystem
\begin{align}
\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= (g^{m_1} r_1^n)(g^{m_2} r_2^n) \;\bmod\; n^2 \\[6pt]
&= g^{m_1 + m_2} (r_1r_2)^n \;\bmod\; n^2 \\[6pt]
&= \mathcal{E}(m_1 + m_2).
\end{align}
As we can see the multiplication of the ciphertext is equal to addition of the plaintext. This is used for the aggregation of the data, especially in databases.
The ( textbook) RSA cryptosystem  on the other hand
\begin{align}
\mathcal{E}(m_1) \cdot \mathcal{E}(m_2) &= m_1^e m_2^e \;\bmod\; n \\[6pt]
&= (m_1 m_2)^e \;\bmod\; n \\[6pt]
&= \mathcal{E}(m_1 \cdot m_2)
\end{align}
uses the same operation on both plaintexts and ciphertexts.


GCM mode of operation with long-term keys Regarding GCM, NIST specifies the following:

  The total number of invocations of the authenticated encryption function shall not exceed $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with the given key.

In another thread on this forum, @Lery suggests deriving session keys from the long-term key using a key-derivation function (KDF) by computing $k_s = \mathrm{KDF}(k,r)$. Here, $k$ is the long-term key, and $r$ is a random nonce generated per GCM usage. $k_s$ is the key used for GCM.

This makes sense from a security standpoint, but to increase performance, I'd like to investigate whether computing the session key as $k_s = k \oplus r$ poses any threat to the security of GCM.

You can assume that the value of $r$ is appended to the ciphertext, but is not encrypted. So, anyone seeing the ciphertext can easily deduce the value of $r$.

The adversary is said to attack this scheme if he can break the properties often associated with authenticated encrypted: IND-CCA security, or unforgeability.

There are two parts to AES-GCM: AES and GHASH.  This can completely ruin the security of both of them.  AES is not designed to resist related-key attacks, so you're in hot water already if you derive multiple keys like this.  Not only does GHASH not resist related-key attacks, but it has a particularly simple structure that illustrates how bad things can get if you make this mistake.

GHASH authenticates a series of messages $m_1, m_2, \dots, m_\ell$ with a long-term key $k$ and a per-message key $s_i$ by $m_i \mapsto \operatorname{GHASH}_k(m_i) + s_i$.  Note that xor, $\oplus$, is just addition in the field $\operatorname{GF}(2^{128})$ that GHASH works in, and for a single-block message, $\operatorname{GHASH}_k(m_i) = m_i \cdot k$ is just multiplication, so the authenticator is simply $m_i \cdot k + s$.

Suppose the sender authenticates a (say) one-block message $m_0$ under $k$ with $r_0$ and a one-block message $m_1$ under $k$ with $r_1$.  That is, suppose you use $k \oplus r_0$ instead of $k$ for one purpose and $k \oplus r_1$ instead of $k$ in another purpose.  Then the adversary learns the authenticators $a_0 = m_0 \cdot (k + r_0) + s$ and $a_1 = m_1 \cdot (k + r_1) + s$.  By the advanced cryptanalytic technique of subtraction, the adversary will find $$a_0 - a_1 = (m_0 - m_1) k + m_0 r_0 - m_1 r_1$$ which they can easily solve for $k$ and forge messages under any nonce $r_i$ of their choice with wild abandon.


$m ∈ Z_n \backslash Z^*_n$, RSA works but not secure If you happen happen to have a message $m ∈ Z_n \backslash Z^*_n$, RSA works but not secure. How likely is it going to happen? $|n|=1024$ bits $|p| = 512$ bits $|q| = 512$ bits.

We know that $|\mathbb{Z}_n| = p\cdot q$ and that $|\mathbb{Z}_n^*| = (p-1)(q-1)$.

So $|\mathbb{Z}_n \backslash \mathbb{Z}^*_n| = (pq) - (p-1)(q-1) = pq - pq + p + q - 1 = p + q -1$. That number is approximately $2^{513}$ given your example prime sizes.

So, out of approximately $2^{1024}$ choices for messages $m$, quite a few are bad. That said, finding one of those is equivalent to factoring. The fastest known method for finding one of these bad messages is to first factor the modulus. Then you can trivially find one.

With just random guessing, each message is equally likely, so has a probability of $\frac{1}{2^{1024}}$, so the probability of finding one of these bad messages is $\frac{2^{513}}{2^{1024}} = \frac{1}{2^{511}}$.


Can passwords be stored securely so that a similarity comparison can be made? On the Pro Webmasters StackExchange site, someone asked a question about a webapp (in this case cPanel) that refused to allow a password change because it was too similar to a previous password. I suggested that the app might be storing hashes of portions of the password.

I was going to ask whether, assuming that an app is storing hashes of portions of a password (i.e. substrings of the full password string), would doing so be less secure than just storing a single hash, but after typing out the question, I realize that it definitely would be less secure. In the most extreme case, i.e. storing a 'hash' of ever character in the full password string, an attacker could trivially recover the original password.

Is there a way to store a password securely that still allows similarity comparisons to be made?

Storing passwords in such a way as to allow comparison against portions of the hashed password is by definition less secure than traditional cryptographic hashing. As a rule, this is simply never done.

On the other hand, you could safely make comparisons of portions of your new password (for which you necessarily have the plain text) against the entirety of an old hash, and such comparisons are done today by some existing software.

To address your original point, to the best of my knowledge, cPanel does not do what you suggest. It has the option of storing certain kinds of passwords reversably encrypted for use with digest authentication, but this is not the default. All other password storage is done through the underlying product's default hashing mechanism (be it MySQL's hashing, shadow file, etc).

The discussion may have confused cPanel with Plesk, which until very recently stored all passwords in plain text in a MySQL database. Yes, really.


Proving that a function is not a OWF (One-way-function) I was trying to prove that a given function is not a one way function and I was not sure how to do it because maybe I had unclear what a one way function was (OWF).

The definition that I have for a OWF is the following:

Easy to compute for all inputs: for all PPT A (probabilistic polynomial time algorithms), A(x) = f(x) $\forall x$

But hard to invert:

$$Pr[B(1^k, f(x)) = x' \ s.t. \ f(x) = f(x')] < neg(k)$$

for all probabilistic polynomial time adversaries.

However, the part that I was unclear about is, if EVERY f(x) has to be hard to invert, or if its ok for it to be easy to invert say for only and only two values (say f(x) and f($\neg x$) ). I guess I was a little confused about the "invertibility" part of the definition. Is there a problem if its easy to invert for some inputs?

Thanks in advance!

To prove that a function is not a OWF, you can exhibit an inversion algorithm and show that your inversion algorithm succeeds in inverting the OWF with non-negligible probability.  In other words, if we randomly choose $x$, compute $f(x)$, feed $f(x)$ to your inversion algorithm, and let $x'$ denote the output of your algorithm, then you need to show that $\Pr[f(x')=f(x)]$ is non-negligible.  Thus, this is average-case hardness, averaging over all possible inputs to the OWF.


What is difference among eavesdropper attack, multiple message attack and CPA attack? What is/are difference(s) among eavesdropper attack, multiple message attack and CPA attack
in context of symmetric key encryption?

I only know that in eavesdropper attack there is an adversary which can send only 2 msgs to challanger and adversary has to distinguish between these in order to win the game but in multi. msg. attack & CPA, it can 2 msg vectors of same length and adversary has to distinguish between these in order to win the game.

If we try to make an equivalent to these terms in intuitive cryptography (before its formalization into games became the norm)

In an eavesdropper attack, the assumption is that an adversary only intercepts a single ciphertext for any given key (and, perhaps, knows the plaintext except for a small portion).
In a multiple messages attack, the assumption is that an adversary intercepts multiple ciphertexts enciphered under the same key (and, perhaps, knows the corresponding plaintexts except for a small part of one); that happens in practice, where keys are reused.
In a Chosen Plaintext Attack, the assumption is as above, plus an adversary can obtain ciphertext for any plaintext submitted (typically: iteratively; that is, the adversary can submit a new message on the basis of ciphertext obtained earlier); that models an attacker dropping a message in an embassy's letterbox, hoping that it will be sent enciphered to the Department of State for analysis.

Different games model that in the current approach of cryptography. Theses games are typically designed for worst-case scenario, and a typical game for said eavesdropper attack is as follows (and summarized in the question):

the adversary chooses any two distinct plaintexts (yet that game is not intended to model Chosen Plaintext Attack; that choice is here to demonstrate that whatever knowledge the adversary may have of the message space won't help);
the challenger chooses a key at random, enciphers one of the two messages chosen at random, and gives the ciphertext;
the adversary bets on which of the two plaintexts was enciphered.

If an (algorithm (with cost polynomial to the number of bits in the key size) for an) adversary exists that succeeds with odds in excess of 50% (by some fixed $\epsilon>0$), the encryption is broken. This model is realistic (and I would say the only such one) for a relatively practical situation: enciphering the result of a referendum, using a key dedicated to that sole purpose.

There are different, more complex games that model the other attacks.


What do the magic numbers 0x5c and 0x36 in the opad/ipad calc in HMAC do? Wikipedia lists the following pseudocode for HMAC:

function hmac (key, message)
    if (length(key) > blocksize) then
        key = hash(key) // keys longer than blocksize are shortened
    end if
    if (length(key) < blocksize) then
        // keys shorter than blocksize are zero-padded ('∥' is concatenation)
        key = key ∥ [0x00 * (blocksize - length(key))]
    end if

    // Where blocksize is that of the underlying hash function
    o_key_pad = [0x5c * blocksize] ⊕ key
    // Where ⊕ is exclusive or (XOR)
    i_key_pad = [0x36 * blocksize] ⊕ key

    // Where '∥' is concatenation
    return hash(o_key_pad ∥ hash(i_key_pad ∥ message))
end function

Why are they there?  How were they chosen?

It seems to me that  $hash(key + hash(message))$ (where + is concatenation) would suffice.

Obviously I'm missing something.  What is it?

Those "magic numbers" are related to the security proof behind the HMAC construction.

In their Crypto'96 paper, Bellare, Canetti and Krawczyk first prove that $\mathrm{NMAC}_{(k_1, k_2)}(x) = F_{k_2}(F_{k_1}(x))$ forms a secure MAC ("message authentication code") provided $F_k(\cdot)$ is an iterated and keyed compression function enjoying some good security properties and $k_1$ and $k_2$ are statistically independent keys. NMAC could be instantiated by common iterated hash functions, such as SHA-256, but one should be able to replace the IV by the key, which is not possible with standard implementations.

To avoid this practical problem, the authors have defined another mechanism, named HMAC. Given a single key $k$ as well as an iterated hash function $H(\cdot)$ built out of a compression function $f(\cdot)$, they first derive two keys $k_1 = f(k \oplus \mathtt{opad})$ and $k_2 = f(k \oplus \mathtt{ipad})$ out of $k$ and define $\mathrm{HMAC}_k(x) = \mathrm{NMAC}_{(k_1, k_2)}(x)$. Thus, the constants $\mathtt{ipad}$ and $\mathtt{opad}$ are just meant to be different, such that the inputs $k \oplus \mathtt{opad}$ and $k \oplus \mathtt{ipad}$ to the compression function are different. Their values have been arbitrarily chosen by the HMAC designers, and any pair $(\mathtt{opad}, \mathtt{ipad})$ could have been selected, as long as $\mathtt{opad} \neq \mathtt{ipad}$.


How long to wait to feed hashing using SHA 256? I have a source which generates secrets at $8-10 bits $ per second. I need to use this secret to feed another generator every second. I am wondering how long should I wait while I am concatenating 8 bits every second and then use longer bits as input to hash.

I have two options:

Use 8 bit that I get every second, hash it and send to next level every second.
Wait for say 10 seconds then hash the final say 100 bit. In between for 9 seconds keep sending hashed value of previous 100 bit using public informations.

Which one is more secure?
I am using HKDF for hashing.

You should aggregate bits until you have enough seed bits to start your DRBG using an initial seed. Your seed should contain at least 128 bits of entropy (the amount of uncertainty to an attacker).

Then you could either add the bits as additional seed when you get it or you could first aggregate some entropy. With only an update rate of about 8 bits per second you might as well directly add the entropy to your DRBG.

To create the same pseudorandom bit stream on both sides you should:

make sure you got the same algorithm on both sides;
configure the DRBG identically on both sides;
update your entropy at exactly the same time;
request data from the DRBG using the same methods and parameters.

Note that HKDF is not a pseudo random number generator (PRNG) or deterministic random bit generator (DRBG, same thing). It may be a pseudo random function but that's not the same.

HKDF turns an already secure key into more key material, possibly given additional information. HKDF / HMAC could be used to build a deterministic random bit generator. If you want to do that then you need to create a paper and prove it is correct.

I would recommend having a look at NIST SP 800-90A (revision 1) and pick a DRBG from there.


Problem with Fiat-shamir on poly-round interactive protocol? I have read in many places that Fiat Shamir technique is used to convert constant round interactive protocols to non-interactive arguments. What would be the problem in applying Fiat Shamir to poly-round protocols?

Yes, there are examples of non-constant round interactive protocols that are unsound when the Fiat-Shamir transform is applied even in the random-oracle model. Note that for constant-round protocols soundness in the random oracle model was proved by Pointcheval and Stern [PS00] -- that is, any constant round interactive protocol (that has negligible soundness error) is also sound when the Fiat-Shamir transform is applied to it given the hash function is modelled as a random oracle.

One simple counter-example is to consider the sequential composition, say $n$ times, of a constant-round protocol that has constant soundness error. By amplification theorem, the resultant protocol has negligible soundness error --- inverse-exponential in $n$ to be precise ---  but the Fiat-Shamir transformed protocol is totally insecure as argued next. Since the soundness error is constant a malicious prover can basically sample (in constant-many attempts in expectation) "favourable" messages for each round and with high probability come up with a cheating proof: see this lecture (around 11 minutes) by Ron Rothblum for more details.

[PS00] Pointcheval and Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.


How to create and validate potential grids when attacking a Playfair cipher? First up: I am not asking you to decypher anything. This question is about attacking a Playfair cipher; more specifically – how to create potential grids when doing so.

I'm currently working on a message in playfair cipher text. The issue is there is no grid, and only potential crib is attack. I was told there is a key used, but we have to discover it.

What I‘ve tried (and been able to do)

After using frequency analysis, I managed to find that QK appears to be the letters th since it is the most common diagraph. I found that C and V are most common letters in the ciphertext after the letters QK.

iagraphs that follow QK

VE - CQ - AH - RQ - VM - BC - BP - VU - SG - SH - CF - UV - UY - SZ - SQ - VQ - FH - AE - RZ

QK - VE = 1
QK - CQ = 4
QK - AH = 1
QK - RQ = 2
QK - VM = 1
QK - BC = 1
QK - BP = 2
QK - VU = 1
QK - SG = 1
QK - SH = 2
QK - CF = 1
QK - UV = 1
QK - UY = 1
QK - SZ = 1
QK - SQ = 1
QK - VQ = 1
QK - FH = 1
QK - AE = 1
QK - RZ = 1

Most common after QK: CQ

ciphertext:

QKVEPTQDEURAQKCQFCQGNWKWQARIVTVQQADVGHQKCQQHFMUQUHGBNWPMPFQKAHMSDHPRRB
ZRSMYKVXVRVUQWPZPFBPFHDZZUUWUVLWSPKQPMHVKMVTBPACWYQKRQMVWLQKVMSFNQQANW
KDMKMVRADPGEEVVYQHYVKZYMGBUEYVDQTIPLVUVYPZRPOYWKRASHUVUYEVLDSEOKMKHDUM
SUIZSEXKMVQKBCHUXQMVTKOYISCMKXQKBPHCPXIMGWVRVUQADECMGBYOESUVGEQANWNKCF
KXFHFLMTOYSGSNQKVURQOYKNOPSHAHDWQHUMMVKBKBYKAHDWQKCQQDEGESSLSMEVCQQCKT
QKSGQDRIMVRHOPRHOYWKUZSPKZULQLVURQRQRHHDWKAHVYQKSHVZHNSZKFQHSDVQQATPHU
XYQLCQQDESKIVWQAIGKZRNALCEVQQAKIBPYOGSWXGEKBQCESSLSMEVQKRQDEMVRZVUASKF
TIDMQHQVRVSWBVQDKXOVDCNWPMYOWXGEDHUVCFTIPBQKCFZUUHQLCQQKUVRZBKQKUYGSKF
UQVRVUTIHUBSILRABKQKSHFHOGWVGZPXBVUVZRBIVUQLCQOYQDRPOPSHVZHNSZSEXCUVCH
BPCIVXIMDEGMPFSNQKSZELBVEVUYVYAHPMPFCBMCFSPUEPBTVOBPASRVSWQKBPCYQHWOVC
RAOPKBXWQKSQLSMIFZPWPONWHRLRMVSHVZHNVQQAEDBIIVFHCWQAUSHFQDXGMSVEFHCWQA
WVCGGBDCFTGOARKXEGLFBSVYQKVQQAQLMKAQSFRZVEVYQHWXUHMTDCNWKWQADSAHYKFHOG
QKCQVYFNCNMPHRLRMVSHVZHNAHXCMSVYQKFHQKAEMBIZVEGMGMLPRQTIPLVURYGEESNYKI
EVCWMIVQQAFCQXVUVEOVUVFDBKGBARKFVQVOQADZVUOGFHHSIKHRBPVYAHLMSHEDKOOGDH
PWOVWLQKRZOVPOUYVYQAMSUFWYYVCIMCIXSZGBWXGEKXCBVWQAVIVXQHDUOGFHHNFHZPCE
UHMCBVOXQRTMRNFCNWNMVEKMVFPZPFFHLRZCPBPFSMAPXKMTZDBUVMVTRYMVWLQDEM

I'm pretty sure uv/vu is er/re. But I am asking myself if one of these could be e…

Question

I am having trouble figuring out how to get the right idea to help create a potential grid that would lead to the deciphering the text. How can/should I create and validate potential grids when attacking a Playfair cipher, based on what I’ve got so far?

(In case of doubt: I am looking for a “how to”. This is not a “decypher this” question.)

Both your suspicions are correct, BTW. (I solved it, and know the key-word).

You have a crib, namely ATTACK, with a typical pattern: two digrams that are each other's reverse, which means that (if we assume that the crib starts at an even position) the cipher text should also have the pattern "abba". I see a CQQC pattern and you note that CQ is frequent after TH, so that fits nicely with CQ = AT, to give THAT.

The text starts with QK = TH, so the next letter could be E (as A would probably be followed by T), so V is one of the letters that E can encipher to, so it must be in the same row (probably) or the same column as E (same column means also that they are next to each other, so same row is more likely). This also fits with your UV/VU supposition. It then follows that E,V,U are all in the same row (or column, less likely). And this row is then in the keyword (by how keyword squares are made: E is far away in the alphabet from U and V).

So from this we already get quite a few ideas on how letters are positioned relative to each other, and at the end of the square we expect some almost alphabetic sequences, like WXYZ (minus letters that go into the keyword), etc.

Fill in some letters (write a program) and guess more letters. If my ATTA guess was OK, you also get CK that becomes KT, which gives us info: overlapping crypto/plain means same row or same column. Etc. etc.

Have fun puzzling it out.


Is this pairing-based signature scheme secure? There are a number of signature schemes on small domains based on bilinear pairings which do not use random oracles. Examples are the Boneh-Boyen schemes and an interesting one from Okamoto which allows for blind, and partially blind signatures.
However all of them use some variant of the Strong Diffie Hellman assumption which (roughly) asks to compute $e(g,g)^{1/x}$ from $(g, g^x, g^{x^2}, \ldots, g^{x^q})$.
The signature scheme I have in mind is this:
Public information: $g_1 \in \mathbb{G}_1, g_2 \in \mathbb{G}_2$, bilinear pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$
Signer secret: $x_1, x_2 \in \mathbb{Z}_p^*$
Signer public: $A=e(g_1, g_2)^{x_1}$, $B=e(g_1, g_2)^{x_2}$
The signature algorithm takes an element of $m \in \mathbb{Z}_p^*$
and computes $\sigma(m) = g_1^{x_1m+x_2}$.
The verification algorithm checks that $e(\sigma(m), g_2) = A^m B$
Forgery seems to require computing $g^{m'x_1+x_2}$ from $(g^{m_1x_1+x_2}, g^{m_2x_1+x_2}, \ldots, g^{m_nx_1+x_2})$ where $m' \neq m_i$.
Is this scheme secure and if so is it used anywhere?

The proposed digital signature scheme is not secure! More precisely, it is not existentially unforgeable under an adaptive chosen-message attack.
Let's consider the following efficient adversary $\mathcal{A}$: it queries the $\mathsf{Sign}_{sk}(\cdot)$ oracle for the digital signatures on $m_1,m_2$, where $m_2:=m_1+1$. The received signatures are $\sigma_1=g_1^{x_1m_1+x_2}$ and $\sigma_2=g_1^{x_1m_2+x_2}$. Now, $\mathcal{A}$ computes $\frac{\sigma_2}{\sigma_1}=\frac{g_1^{x_1m_2+x_2}}{g_1^{x_1m_1+x_2}}=g_1^{x_1(m_2-m_1)}=g_1^{x_1}$. Once $g_1^{x_1}$ is recovered, $\mathcal{A}$ can also compute $g_1^{x_2}=\frac{\sigma_1}{(g_1^{x_1})^{m_1}}$.
The knowledge of these $2$ points ($g_1^{x_1}$ and $g_1^{x_2}$) enables now $\mathcal{A}$ to forge signatures on any message of their choice. Namely, given any message $m$, $g_1^{x_1}$ and $g_1^{x_2}$, the valid signature on $m$ can be computed as $\sigma=(g_1^{x_1})^{m}g_1^{x_2}=g_1^{x_1m+x_2}$. The adversary $\mathcal{A}$ outputs $(m,\sigma)$ as a valid forgery and wins the security game.
This means, that the adversary can win the existential unforgeability security game with probability $1$ already after $2$ signature queries.