Formal definition of collision resistance for hash function In my cryptography class, the professor said that collision resistance for a fixed hash function is not a "precise" definition. The reason is since a fixed hash function is a single instance of a computational problem it can't be hard(at least for a somewhat precise and complete definition of collision resistant). Note that it is not said that we know solutions for a fixed hash function. However, the definition seems to make more sense for a family of hash function. So this is more of a theoretical question than "in practice".

How would you explain this differently?

To define collision-resistance for a fixed hash function $H$, it probably looks like this:

CR: There is no efficient attacker (i.e., with polynomial computational resources) that can find two messages $m_0\neq m_1$ such that $H(m_0)=H(m_1)$ with non-negligible probability.

However, this is problematic because such an attacker may indeed exist but we just cannot find it easily. From the pigeonhole principle, we know for sure that there are two colliding messages for $H$. So, there exists a very efficient attacker who can simply output these two messages and break the above security.

To deal with this issue, one may attempt to rephrase CR as "It's hard to construct an attacker...". But then you got stuck on defining "hard to construct" formally, while in practice this is OK.

So, an easy fix is to introduce a large key space $K$ such that it's hard for any efficient attacker to output colliding messages for a randomly-chosen hash function $H_k$ (where $k\gets K$). Note that even if the attacker is given all colliding messages for all keys, it cannot "digest" them easily compared to the case with a fixed hash function because storing all colliding messages requires exponentially-large space (linear to the size of the key space) while the attacker has only polynomial computational resources.


Can anyone tell me the name of this cipher please? Can anyone tell me the name of this cipher please?
I know it's a simple substitution cipher, I just don't know the name of it.

Cipher Key:

help

Cipher alphabet:

a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
h|e|l|p|a|b|c|d|f|g|i|j|k|m|n|o|q|r|s|t|u|v|w|x|y|z

Text:

this is a test

Cipher text:

tdfs fs h tast

I think I have found the answer: a Caesar variant, a "Mixed Alphabet" substitution cipher.
Does it have a specific name?

It's called a keyword cipher.  See this question for some ways to break it.


Building a 4-bit S-box with a 4-uniform DDT I am looking for a 4-bit S-box which has only 4s in its difference distribution table (except the top left corner) but I was not able to find one in the literature.
Has such an S-box been already published? If not, is it theoretically possible to reach this property? If so, how to proceed?

Yes. All $4\times4$ bit S-boxes have been classified. It is possible to reach a maximum differential of 4 as well as optimum nonlinearity.
SERPENT used optimal $4\times 4$ S-boxes with respect to differential cryptanalysis. So does PRESENT, to the best of my knowledge.
Some links

2011 - Markku-Juhani O. Saarinen, Cryptographic Analysis of All 4 × 4-Bit S-Boxes

2015 - Zhang et.al., A New Classification of 4-bit Optimal S-boxes and its Application to PRESENT, RECTANGLE and SPONGENT

SAGE is a good way to learn about and experiment with S-boxes.

Sage: S-Boxes and Their Algebraic Representations

Edit: None of the optimal Sboxes' representatives from Saarinen have the property of all 4's you want. I have no time, but I believe it can be proved using Theorem 1

in Blondeau-Nyberg which originally appeared in Eurocrypt 94  Chabaud-Vaudenay that such a DDT pattern would yield weak S-boxes against linear cryptanalysis. Here $n=m=4,$  $cor_x(a\cdot x \oplus b\cdot F(x))$ is the correlation bias of the corresponding linear characteristic, and $P[\delta \stackrel{F}{\rightarrow} \Delta]$ is the diferential probability.


Allow everyone to decrypt a message, but don't allow anyone to encrypt it I would like to create a software that will be installed on multiple clients. I would like to broadcast an encrypted message to all of those clients. Each client should be able to decrypt the message and react to it. However, noone should be able to create such a message that could be decrypted by those clients.

So, I would like to be the only entity that is able to create the encrypted message. At the same time I would like everyone to be able to decrypt the message I have created. I would also like the message to be sent in encrypted form, so digital signature alone won't suffice.

Is it possible with assymetric cryptography, i.e. RSA or ECC?

I know some people encrypt with private keys and decrypt with public keys, but lots of sources specify this approach as insecure/invalid. So, I would like to know what's the proper, secure and valid approach?

Update: edited to provide more context information, because maybe my generalization was confusing. It's not about the network, but rather I'm trying to think of some software registration key scheme. I would have multiple clients. When someone buys a key, I would send this person an encrypted registration info. His copy of the software would read this encrypted key info, decrypt it, and store on the disk in decrypted form. I would like to prevent converting this decrypted form into encrypted form again to prevent registration key from being stolen by some malicious software. The key would be useless in decrypted form because the software wouldn't accept decrypted key; it would accept only encrypted keys.

This is a scenario where your description would be much improved if you explicitly considered the following questions, which you should always ask in cryptography:

Who are the "honest" parties? (See at the bottom for an explanation of the scare quotes.)
Who are the adversaries?

In particular, you've not taken enough care to describe who the adversaries are.  The first obvious thing we can imagine is that there are third parties—neither your software nor its clients, both of whom would count as "honest parties"—that would eavesdrop on the broadcast and would like to know its plaintext.  If that's the model, then a simple solution would be:

All the messages are encrypted with a symmetric algorithm whose key is shared by the broadcaster and all the clients;
The broadcaster signs every broadcast with its own asymmetric keypair, and all clients verify the signature on every broadcast.

But there's a problem with this way of looking at it: should the clients really be modeled as "honest" parties, or are they actually a type of adversary?  Encryption only protects message confidentiality if the recipient is an honest party, who keeps the keys and plaintexts secret.

The problem with your scenario then is that you're disclosing information to another party and expecting them not to disclose it to anybody else.  That works if and only if the other party is "honest," and it could easily fail if the other party is an adversary.

Note that in cryptography, "honest party" is not a moral term.  It's a party to some protocol who can be counted on to execute it faithfully.  While an adversary is a party that cannot be counted on to follow the rules.


Which symmetric cipher is best for studying? I would like to study a modern symmetric cipher (I have never studied a cipher before) and I was wondering which would be the best cipher for studying purposes of the following: AES (Rijndael), Blowfish, Twofish, Threefish or Serpent. Basically I am asking which of those ciphers is the most simple to study.

First, it is important to learn the basics behind all symmetric ciphers. You can get this from Handbook of Applied Cryptography, see Chapter 7, especially 7.1, 7.2, 7.3. If you understand those three sections, you will be off on the right foot.

From there, I would suggest just diving right into AES. It isn't that terribly difficult (yes, there are easier ciphers, but the "market penetration" of AES is so great that it is worth the added effort). There should be some good videos online, plus look at this question, the comments, and answer.

From there, I recommend the book "The Design of Rijndael". It was written by the inventors of Rijndael and has some very useful information on why they designed pieces the way they did.

Finally, I recommend using this site as much as possible to help clarify things. If there is something you don't understand as you are learning all this, search on here to see if it has already been answered. Then, if not, ask a specific question on this site.


Same message space for different public exponents What is the weakness, if there is any, of using the same message space for different public exponents (assuming e changes everytime)?

Imagine I have a message space [0,n] where n is a 1024 bit number and several public exponents of 1024 bit each as well, does that somehow have an impact on my RSA system?

Edit: assume I don't have access to n in this scenario (unless "message space" refers to n. However, in this case we assume that the given message space is a composite number with > 6 prime factors)

The RSA system in the question uses

a common modulus $n$ shared by multiple public exponents $e$
message space $[0,n)$
a 1024-bit mosulus $n$ with > 6 prime factors

This leads to security issues:

Given a private exponent $d$, matching $e$, and $n$, it is possible to factor $n$ (see answers to this). Then, because of 1, it is trivial to find the private exponents for all other $e$, and decipher all cryptograms. This is a disaster if any of the various $d$ falls in the hand of an adversary (including if the various $d$ are held by persons with diverging interests).
Message space $[0,n)$ of 2 strongly suggests textbook RSA, where encryption of $m$ in the message space is as $c\gets m^e\bmod n$. This is unsafe, in particular because a guess of $m$ can be trivially verified from $c$, $n$, and $e$, which all are assumed available to attackers. That's a disasters for a coin throw, the name of person on the class roll, a credit card number... Proper RSA encryption use random encryption padding, e.g. as in RSAES-OAEP of PKCS#1v2.2, with typically a reduced message space.
If 1 is combined with textbook RSA, and the same message is sent encrypted under multiple $e$, it can be deciphered without knowing any $d$ or the factorization of $n$ (see this).
The 1024-bit key size of 3, although seriously obsolete, would remain extremely hard to attack with 2 or 3 factors of about equal size. But with at least 7 factors, one must be 147-bit or less, and ECM can pull it out with little effort.


Birthday Attack with probability of 1 According to Wikipedia,

$n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}$

Let n(p; H) be the smallest number of values we have to choose, such that the probability for finding a collision is at least p. What if I wants my probability to be 1? In this case, $p = 1$ and $\frac{1}{1-1}$ is undefined. May I know how to find minimum number of values required to get a collision with the probability of 1 using the formula above?

To get a collision with probability 1, you need to hash $H+1$ distinct values.  You can see that because it is possible that if you hash only $H$ values, each one might happen to hash to a unique hash output; if any reasonable sized hash function, this is extremely unlikely, but it does have a nonzero probability to happen.  On the other hand, if we hash $H+1$ distinct values, we know (by the pigeon hole principle (because there are only $H$ hash outputs), that two of the inputs must hash to the same output.


Is GPG symmetric encryption only based on a passphrase? Is the symmetric key derived for AES only dependent on the passphrase?
Is it possible to generate the encryption key such that it is based on my primary GPG private key and temporary passphrase? In this case, the attacker would have to know the passphrase as well as my GPG key to decrypt the text.

In GPG the symmetric key used to encrypt data is generated randomly.  That key is then wrapped (encrypted) using a public key or multiple public keys and anyone with any of those private keys can then unwrap (decrypt) the symmetric key and decrypt the data.  Typically, private keys are protected with passwords.  So yes, under normal circumstances, an attacker would need a copy of your encrypted private key and knowledge of your password in order to decrypt data sent to you.
Notice I said "multiple public keys" above.  So, anyone who's public key was included can decrypt the data so if multiple people are included in then any of them can decrypt the data and the compromise of any of their private keys or passwords would result in that encrypt data being compromised as well.


Deprecation of RSA-SHA-1 in DKIM keys? I recently noticed that OpenDKIM on my mail server is objecting to DKIM signatures from a client, saying their key is insecure. It may be that that's due to lack of secure DNS (confirmation anyone?) but I also noticed that the signing algorithm is shown as a=rsa-sha1, and with the move to “Deprecate SHA-1” in other contexts, I'm wondering: how urgent this is for DKIM?

It is now feasible to brute-force SHA-1 hashes. Am I correct in thinking that this would need to be done for each message an attacker wished to forge the signature for, without being able to re-use that work for the next message?

It may be that that's due to lack of secure DNS (confirmation anyone?)

So it turned out to likely be a warning about lack of DNS security.

  I also noticed that the signing algorithm is shown as a=rsa-sha1, and with the move to “Deprecate SHA-1” in other contexts, I'm wondering: how urgent this is for DKIM?

Not very urgent. Current attacks only put a dent in SHA-1 collision resistance, which requires generating a large number of messages to find a pair with equal hash values. That is only a concern whenever the attacker can both predict the data to be signed and influence some of it.

Typically, with DKIM an attacker can't get such a message signed. If you send an arbitrary message that gets signed by the domain, the attacker would need a second preimage attack to forge a change. The second preimage resistance of SHA-1 is still close enough to the expected $2^{160}$ to be completely unbreakable with current attacks.

There may be special cases where a collision attack could be possible, like if the attacker has access to an email account on a domain, but the messages are screened for spam before being sent. Then they could look for a pair of messages where one is innocent, the other spam; send the legitimate message; and copy the signature to the spam message. In this case the attacker would have to predict any header fields and the like that DKIM signs, so feasibility would depend on the setup.

Even if a collision attack was possible, it would take quite a lot of computational effort ($2^{61}$ or so).

  Am I correct in thinking that this would need to be done for each message an attacker wished to forge the signature for, without being able to re-use that work for the next message?

Finding multiple collisions is not that much harder than finding one. A generic preimage attack also becomes easier the more target messages you have. So the attacker could probably share some work if an attack was possible in the first place. However, it's not a key recovery attack, so every new forgery would need more work, yes.


Explaining weakness of Dual EC DRBG to wider audience? I have an audience of senior (non-technical) executives and senior technical people who are taking the backdoor in Dual_EC_DRBG and considering it as a weakness of Elliptic curves in general. I can take a max of about 10 mins in my presentation to address this issue - no more.

How can I explain the weakness in the EC_DUAL_DRBG to such an audience via Mathematical intuition (rather than hardcore math proofs)?
How do I establish the distinction between weakness in Dual EC DRBG from any weaknesses in EC in general (especially the NSA's Suite B EC curves - ironic, eh?). To me the weakness in Dual EC DRBG is clear (well, after the fact) with selection of the constant curve point. But the NIST EC curves also have constants although of a much different nature (the large prime modulo). Controlling paranoia is ... not easy.

Please note that the non-technical folks are very intelligent - just not security experts. So I'd like to respect that without dumbing it down too much.

I wouldn't try to explain the mathematics of the backdoor.  Just explain that the NSA hid a secret backdoor in there.

Instead, I would suggest focusing on the history and the context.  For instance, you could explain about Crypto.AG, how they spiked their RNG to help the NSA spy on their customers.  You could explain how random number generators are a classic weak point in cryptography, because of the RNG has been backdoored, whoever knows the backdoor can recover all your keys.  You could also explain how this is very hard to detect: since RNGs are supposed to output random-looking bits, if it's actually pseudorandom bits that the NSA can predict but no one else can (if the bits are actually coming from a PRNG that the NSA knows the seed to, but no one else does), this is very difficult to detect through black-box testing or through inspection of the supposedly  random bits.

If you wanted, you could explain that back in 2006, cryptographers discovered the mathematical structure that would allow a backdoor but shied away from making any accusations, because, hey, surely the NSA wouldn't do that -- that would be so egregious a breach, that it seemed hard to imagine it actually contained a backdoor.  And now things are changed: it appears that what seemed unimaginable, is in fact reality.  So, you could explain how this is an eye-opener for the cryptographic community and how it will change the way we think about government standards and system design for the future.

You could then explain the impact.  You could explain how the impact is believed to be relatively minor, because most people heeded Bruce Schneier's warning from 2007 and didn't use Dual_EC_DRBG.  However, you could explain that at least one major crypto library (RSA's BSAFE) does use it, for reasons that are unclear, so this might have an unknown impact on an unknown number of deployed products.  You could explain how this backdoor is likely to only allow the NSA to decrypt traffic, not anyone else.  And finally, you could explain what the biggest impact is: the potential for loss of trust in cryptographic standards and in American companies.  I'm not sure that we've seen the general public lose trust yet -- I think people still trust Google and Apple and Amazon to have their back -- but if that ever happened, that might be hard to recover from.

I see that you want to explain the mathematics.  OK, here is an explanation.  I'm going to attack a simplified version of Dual_EC_DRBG, but the simplification doesn't change any of the essence of the attack.

The algorithm specification specifies an elliptic curve, which is basically just a finite cyclic (and thus Abelian) group $G$.  The algorithm also specifies two group elements $P,Q$.  It doesn't say how they were chosen; all we know is that they were chosen by an employee of the NSA.  In the simplified algorithm, the state of the PRNG at time $t$ is some integer $s$.  To run the PRNG forward one step, we do the following:

We compute $sP$ (recall we use additive group notation; this is the same as $P^s$, if you prefer multiplicative notation), convert this to an integer, and call it $r$.
We compute $rP$, convert it to an integer, and call it $s'$ (this will become the new state in the next step).
We compute $rQ$ and output it as this step's output from the PRNG.  (OK, technically, we convert it to a bitstring in a particular way, but you can ignore that.)

Now here's the observation: we're pretty much guaranteed that $P=eQ$ for some integer $e$.  We don't know what $e$ is, and it's hard for us to find it (that requires solving the discrete log problem on an elliptic curve, so this is presumably hard).  However, since the NSA chose the values $P,Q$, it could have chosen them by picking $Q$ randomly, picking $e$ randomly, and setting $P=eQ$.  In particular, the NSA could have chosen them so that they know $e$.

And here the number $e$ is a backdoor that lets you break the PRNG.  Suppose the NSA can observe one output from the PRNG, namely, $rQ$.  They can multiply this by $e$, to get $erQ$.  Now notice that $erQ = r(eQ) = rP = s'$.  So, they can infer what the next state of the PRNG will be.  This means they learn the state of your PRNG!  That's really bad -- after observing just one output from the PRNG, they can predict all future outputs from the PRNG with almost no work.  This is just about as bad a break of the PRNG as could possibly happen.

Of course, only people who know $e$ can break the PRNG.  So this is a special kind of backdoor: the NSA presumably knows how to break Dual_EC_DRBG, but it's very unlikely that anyone else knows how to break it.  Even though we know now the backdoor exists, it's very hard to recover the secret backdoor $e$, because that requires solving a discrete log problem.

Hmm.  Maybe that's still too complicated, because it requires understanding additive groups and a little bit about elliptic curves and... ugh.  OK.  So, let me share with you an analogous: a PRNG that is just like Dual_EC_PRNG, except that it uses integers, instead of elliptic curves.  In particular, everything will be conceptually basically the same -- the backdoor will be the same, the PRNG will be the same -- this will just be easier to understand without any background in elliptic curve cryptography.  Hopefully this will give the intuition better.

The PRNG. The algorithm specifies a prime number $p$, and two integers $g,h$ that are both less than $p$.  The algorithm tells you that the state of the PRNG at each point in time is some number $s$ that satisfies $1\le s < p$.  To step the PRNG forward by one iteration, you set $r = g^s \bmod p$, $s' = g^r \bmod p$, update the state to $s'$, and output $t = h^r \bmod p$.
The backdoor. The backdoor is a secret number $e$ such that $g=h^e \bmod p$.  The NSA, who created the algorithm specification, chose $g,h$ by picking $h$ randomly, picking $e$ randomly, setting $g=h^e \bmod p$, and then publishing $g,h,p$ (but keeping $e$ secret, since $e$ is the backdoor).
Breaking the PRNG. Here's how the NSA can break this PRNG.  Suppose they observe one output $t$ from the PRNG.  They compute $t^e \bmod p$.  Notice that

$$t^e = (h^r)^e = h^{re} = (h^e)^r = g^r = s' \pmod p.$$

This means they were able to compute $s'$, the next state of the PRNG.  So, after observing just one output from the PRNG, they can infer the next state of the PRNG and thereby predict what all future outputs from the PRNG will be.

For instance, suppose you generate a random IV using this generator (and send it in the clear), then generate a session key using this generator, then encrypt stuff under that session key.  The NSA (who is eavesdropping on your communication and thus can see the IV) knows that the IV was output from this PRNG and can use their backdoor to infer the state of the PRNG and predict its future outputs -- and thus they can predict your session key and decrypt all your subsequent traffic.  You've been owned!

I hope this gives the intuition.  The problem with Dual_EC_DRBG is exactly the same as the problem with this hypothetical PRNG that I just described.  Hopefully this is simple enough to follow: if you understand how Diffie-Hellman works, you can understand why this is broken.


What does GHASH really do? I try to understand the GCM-MODE used in TLS.
The problem I have had is described below.

1:textbook describes how GHASH works:

2:
I get some debuginfo from openssl code that contain enc_key(32 bytes) and ADD(13 bytes).

I try to simulate the GCM MUL by coding like this:

static unsigned char buf[16]={0};
static unsigned char ctr[16]={0};
static unsigned char ectr[16];

static int poly[]={128, 7, 2, 1, 0, -1};
BN_GF2m_arr2poly(poly, p);

AES_set_encrypt_key(gcm_key, 256, &ghash_key);//gcm_key is derived from debug info
AES_encrypt(ctr, ectr, &ghash_key);

BN_bin2bn(ectr, 16, k);//construct K
memcpy(buf, gcm_add, sizeof(gcm_add));//gcm_add is a 13 bytes data derived form debug info
BN_bin2bn(buf, 16, a);//construct ADD
BN_GF2m_mod_mul(r, a, k, p, bnctx);//compute  (add · K) as first part of computing tag

But the result r is different from the result in openssl code(The code use GCM_MUL).
I confirm that the gcm_add and gcm_key are correct and even the ectr encrypted by gcm_key is also correct compared to debug info from code.

The problem is probably in the usage of BN_bin2bn to construct K (H in the picture) and ADD. GCM specifies that a 16-byte buffer should be transformed into a binary polynomial in little-endian format, but in each byte, it considers the bits in reversed order. Yes, it's confusing. So for example:

The byte array 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 represents the polynomial $1$ (e.g. with a poly = {0} when using BN_GF2m_arr2poly
The byte array 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 represents the polynomial $z^7$ (poly = {7})
The byte array 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 represents the polynomial $z^{127}$ (poly = {127})

So, before using BN_bin2bn, you need to reverse the bytes, and then reverse the bits in each byte. Maybe there is something already implemented in OpenSSL, but I didn't check it.


Regarding Lattice atttacks on ECDSA with a portion of known bits of the nonce k I am new in the field of cryptography, and I am having some troubles understanding a concept regarding the lattice dimension needed in the attack on ECDSA using several messages with L known bits of each nonce.
In the paper "Recovering Secrets from Prefix-Dependant Leakage"

In Section 5 "Application to ECDSA", the authors stated that if we have a group of size n, and we are able to know k bits of the nonce of each signature,
then the number of messages that we need (which is also the dimension of the lattice) is given by:
d = n / (k - c),
where c = log2(sqrt(πe/2)).

I am not understanding where did they get this relation from, neither where did the constant c come from.
I have read many papers but couldn't really identify the origin.

I could be really thankful for your help.
Thank you!

The constant is derived from the so-called Gaussian Heuristic, which is used to predict the expected length of the shortest vector of a random lattice. For the attack to work, one must ensure that the special vector that he is looking for will be the shortest, so that it can be found. We therefore compare the length of that to-be-found vector with the expected length of the shortest lattice vector.


Can any message be decrypted using a given ciphertext and an appropriate key? Does the following proposition hold for any deterministic, symmetric cryptosystem $(\mathcal{M}, \mathcal{C}, \mathcal{K}, Enc, Dec)$?
$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$
My reasoning until now is that this should be equivalent to
$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$
And if this was false, the opposite must hold:
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$
Since all messages $M \in \mathcal{M}$ and keys $K \in \mathcal{K}$ can be used to create ciphertexts in $\mathcal{C}$, this would mean that there exist messages $M_1, M_2, M_1 \ne M_2$ which, given a key $K$, are encrypted to $Enc_K(M_1)=Enc_K(M_2)=C$, which defies the required injectivity of $Enc$. Therefore, the proposition must be true. Is it?

Your question is unclear and your mathematical expressions are not equivalent.
Given a key and a potential ciphertext, is there a corresponding plaintext?
In other words, can decryption fail?
For authenticated decryption, the answer is an obvious yes: almost all ciphertexts are invalid. You need to know the secret key to produce a valid ciphertext. Without knowing the key, with very high probability, you can't generate a ciphertext that includes a valid authentication tag.
For unauthenticated decryption, it depends. A stream cipher has no invalid ciphertexts: you just xor the stream with the ciphertext and you get a plaintext. CBC-with-padding has invalid ciphertexts with common padding modes. Also, for CBC, not all bit-strings are valid ciphertexts regardless of padding: only bit-strings that consist of a whole number of blocks have a chance of being valid.
An encryption scheme where an adversary can generate ciphertexts with a probability of validity that is neither 1 nor infinitesimal is problematic because it opens the way to padding oracle attacks.

If all bit-strings are valid ciphertexts, as with stream ciphers, then forging ciphertexts is trivial and won't provide the adversary with any useful information.
More generally, if the set of possible ciphertexts that's independent of the key, the adversary can't learn anything by forging ciphertexts because using a forged ciphertext won't reveal any secret information.
If there's no way to forge a valid ciphertext with non-negligible probability without knowing the key, as with authenticated encryption, then an adversary can't learn anything by forging ciphertexts because the only information the adversary will get is “no, you didn't manage to forge a valid ciphertext”.
In between, there is a very dangerous spot where forging ciphertexts can reveal information. The details vary depending on the exact algorithm, but the general principle is that the adversary captures known ciphertext, tweaks it, sends it to a key holder and observes whether the recipient determines that the ciphertext is valid or not. Repeating this with different tweaks may allow the adversary to decrypt the ciphertext.

Given a potential ciphertext and a plaintext, is there a key that turns this ciphertext into this plaintext?
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
A scheme where for any plaintext-ciphertext pair, there exists a matching key, is either a one-time pad or a deviation from it that I think only adds useless complexity.
Given a potential ciphertext, is there a key that makes it valid?
This question is only meaningful for schemes where the space of valid ciphertexts depends on the key.
In general, no: for any practical scheme, the space of keys is a lot smaller than the space of messages.
Your formalizations

$$\forall C \in \mathcal{C}: |\{M'| \exists K \in \mathcal{K}: Enc_K(M') = C\}| = |\mathcal{M}|$$
My reasoning until now is that this should be equivalent to
$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$

Not quite: if the second proposition is true, that means that every plaintext-ciphertext pair has a corresponding key. But even if this is true, there could be plaintext-ciphertext that are matches by multiple keys. This doesn't happen in realistic message encryption scenarios, but it can happen in some cryptographic schemes where the encryption is only a part of a bigger whole, for example a voting or commitment protocol.

$$\forall C \in \mathcal{C}~ \forall M \in \mathcal{M}~ \exists K \in \mathcal{K}: Enc_K(M) = C$$
And if this was false, the opposite must hold:
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \not \exists K \in \mathcal{K}: Enc_K(M)=C$$

i.e.
$$\exists C \in \mathcal{C}~ \exists M \in \mathcal{M}~ \forall K \in \mathcal{K}: Enc_K(M) \ne C$$
Or in plain English, there exists a plaintext-ciphertext pair which no key matches. As we saw above, this is true of most encryption schemes.

Since all messages $M \in \mathcal{M}$ and keys $K \in \mathcal{K}$ can be used to create ciphertexts in $\mathcal{C}$, this would mean that there exist messages $M_1, M_2, M_1 \ne M_2$ which, given a key $K$, are encrypted to $Enc_K(M_1)=Enc_K(M_2)=C$, which defies the required injectivity of $Enc$. Therefore, the proposition must be true. Is it?

I don't see what reasoning led you from the statements above to this last paragraph. You changed from having a fixed plaintext and a fixed ciphertext and varying the key, to having a fixed ciphertext and key and varying the plaintext. Since the decryption function exists, $Enc_K$ (i.e. $M \mapsto Enc_K(M)$) is injective for every $K$. But $K \mapsto Enc_K(M)$ for a given $M$ does not need to be injective (though it usually is unless the message space is limited to very short messages).


Why is GCM only usable for ciphers with a 128-bit block size? All block cipher modes of operation that I understand are generic schemes. They are not restricted by key size or block size. So why is GCM restricted to 128-bit block size?

The field polynomial used for GHASH limits most definitions to 128-bit block size. That does not mean you could not define it for other sizes – the proposal defined it for 64-bit as well (pdf, see Appendix A) even if NIST did not standardize that.

However, defining it for arbitrary block sizes would be more difficult. You would need to define a deterministic method for constructing the polynomial and the changes that entails (see the document above). Since 64-bit block ciphers are usually considered too small these days anyway and no larger block sizes are in common use, there is no need to do that.


DES and using the S-Box 1 Can someone please check my work and correct me if I am wrong, I am just starting to learn about DES. I am trying to solve the following problem:

  Show that S1(x1) XOR S1 (x2) != S1(x1 XOR x2).
   x1 = 000000, x2 = 000001

So, we get S1(x1) first: 00 is our row, and 0000 is our column which is (0,0) and in the S1 Box table is the value 14. 14 in binary is 1110.

Now we get S1(x2): 01 is our row, and 0000 is our column which is (1,0) and in the S1 Box table is the value 0. In binary, it's 0000.

Now we XOR the two outputs:

    1110
XOR 0000
  = 0001

Thus, S1(x1) XOR S1(x2) = 0001.

Now we XOR X1 and X2 first:

     0000000
 XOR 0000001
  =  1111110

Now we lookup our output in the S1 table: Our row is 10, and our column is 1111 which is (2,15) and in the S1 Box Table is the value 08 which is 1000.

Thus, 0001 != 1000. Is that correct? (And in case it isn’t, where did I take a wrong turn?)

Your XOR equations are wrong.
You wrote:

    1110
XOR 0000
  = 0001

But it's not how the XOR works. 1 xor 0 = 1, and in your example it somehow turns into 0 wich is an error. Reference the xor table: https://en.wikipedia.org/wiki/Exclusive_or

So, the correct answer for S1(x1) XOR S1(x2) is:

    1110
XOR 0000
  = 1110

and for x1 xor x2:

    0000000
XOR 0000001
  = 0000001


Is CTR more secure than CBC? In cryptography, a block cipher mode of operation is an algorithm that uses a block cipher to provide information security such as confidentiality or authenticity. A block cipher by itself is only suitable for the secure cryptographic transformation (encryption or decryption) of one fixed-length group of bits called a block. A mode of operation describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block.
Most modes require a unique binary sequence, often called an initialization vector (IV), for each encryption operation. The IV has to be non-repeating and, for some modes, random as well. The initialization vector is used to ensure distinct ciphertexts are produced even when the same plaintext is encrypted multiple times independently with the same key.[6] Block ciphers may be capable of operating on more than one block size, but during transformation the block size is always fixed. Block cipher modes operate on whole blocks and require that the last part of the data be padded to a full block if it is smaller than the current block size. There are, however, modes that do not require padding because they effectively use a block cipher as a stream cipher.
Historically, encryption modes have been studied extensively in regard to their error propagation properties under various scenarios of data modification. Later development regarded integrity protection as an entirely separate cryptographic goal. Some modern modes of operation combine confidentiality and authenticity in an efficient way, and are known as authenticated encryption modes.

Neither mode provides authentication, so in that sense they are both not very secure. CBC has more error propagation obviously, but as the last paragraph of the quote in the question states, error propagation is mostly ignored by now.
CBC requires an unpredictable IV (for the attacker), while CTR mode just requires a nonce. However CBC fails less dramatically if the IV is repeated or when too many data packets are encrypted.
CBC is vulnerable against padding oracle attacks in the correct setting, which makes the mode more vulnerable (if you count padding as part of the mode). However, both are vulnerable against plaintext oracles, and CTR mode then allows each bit to be changed individually, which is just as dangerous in my opinion.
So in the end, which one is more secure depends on how the mode is used. Both can be used to create a secure system by providing confidentiality. CTR has more practical benefits in the end (parallelism, nonce), which is likely why it is ending up as underlying encryption scheme for authenticated modes such as CCM, GCM and EAX.


Symmetry between a public and a private key I know that the private and public key in assymetric cryptography are different and the public is used for encryption while the private for decryption. My question is if they are symmetrical to each other in a mathematical way? They must be because the one is inverting what is done by the other.

The public key and private key are related, but that does not mean that they have to be symmetric, and normally they are not. For instance with a public/private key in RSA, the public exponent is normally a small value, while the private exponent has a larger value. They can have the same properties though - making them symmetric in that sense - but this is not common.

As for EC public and private keys, these have different properties. One is actually a vector and the other a point. So there is no symmetry there.

What is common is that the public and private key share some properties. For RSA keys this is the modulus, and with EC keys the domain parameters should be equal for the algorithms to work.

I don't think it is wise to think of a public and private key to be symmetric, even though both keys are part of the same mathematical framework.


Help me about Advanced Encryption Standard (AES) Suppose $E_k$$(a, b, c)$ is encryption of values $a, b$ and $c$ with key $k$ through encryption algorithm AES (AES-128) and each $a, b$ and $c$ are 300 bits integer values.

Also Suppose this algorithm in my question situation work in CBC mode.

If $V_1= E_k(a, b, c)$ and $V_2= E_k(c, a, b)$, my questions is:  are the two values $V_1$ and $V_2$ equal or not?

I'm going to assume that the comma $,$ operator used in your question means 'concatenate' (normally written $a||b||c$). Moreover, I'm assuming that $a,b,c$ are distinct.

In that case, With incredibly high probability, No: $V_1$ and $V_2$ will not be equal.

Think of it this way: if they were equal, then what would $D_k(V_1)$ be? Supposing $V_1=V_2$, we have:
$$a||b||c=D_k(E_k(a||b||c))=D_k(V_1)=D_k(V_2)=D_k(E_k(b||a||c))=b||a||c$$

That is, we would have to deduce that $a||b=b||a$ and thus $a=b$.


Unique decoding Radius in Reed Solomon Codes In one of the coding theory books I read the unique decoding radius for Reed Solomon codes is $\frac{1-\rho}{2}$. Precisely, if the relative distance be less than these amount so the receiver is able to reconstruct the noisy received code-word uniquely. While for bigger amount of relative distance there are other code-words that are closer to the received code-word instead of the original code-word.

How this bound is calculated?

Let the linear block code $C$ with the minimum distance of $d_{min}$ which this amount is either odd or even so for each integer $t$ we can define the below inequality:
\begin{equation}
2t+1 \leq d_{min} \leq 2t+2
\end{equation}
Suppose $W$ is all code-words in code $C$ except $V$ which is the original code-word along with the channel and $r$ is the received code-word. Therefore, the below inequality according to one of the famous Lemma is satisfied.
\begin{equation}
d(V,r)+d(r,W) \geq d(V,W)
\end{equation}
Since $V$, $W$ $\in$ $C$,
\begin{equation}
d(V,W) \geq d_{min} \geq 2t+1
\end{equation}
Now, suppose the number of error between $V$ and $r$ is $l$ i.e. $d(V,r)=l$.
So
\begin{equation}
d(r,w) \geq 2t+1-l
\end{equation}
If $l$ $\leq$ $t$ then
\begin{equation}
d(r,w) \geq t
\end{equation}

In other words, if the number of errors between the transmitted and the received code-words be less than $t$ so the code-word $V$ is the closest code-word to $r$ than all other code-words in code $C$. i.e.
\begin{equation}
d(V,r) < \frac{d_{min}-1}{2}
\end{equation}

We can generalize this bound for all linear block codes such as Reed Solomon codes. The $d_{min}$ for RS codes is $n-k+1$ so we can conclude:
\begin{equation}
d(V,r) < \frac{n-k+1-1}{2}=n\frac{1-\frac{k}{n}}{2}
\end{equation}
So
\begin{equation}
\delta < \frac{1-\rho}{2}
\end{equation}

It is exactly the bound for the RS codes to obtain uniquely the original code-word.


Does having an SHA256 hash compromise PBKDF2 secrecy? If I have a password pwd, and I hash it with SHA256 and send it to a server for authentication (server will apply bcrypt for storage), and then I use PBKDF2-SHA256 with a large number of iterations to derive a key for decrypting user data, does the fact that the server knows the original SHA256 hash or the bcrypt hash allow it to derive the original pwd or the decryption key?

Another way to phrase the question: see below pseudocode

CLIENT:
hash1 := SHA256(email + pwd)
> send hash1 to server

SERVER:
hash2 := bcrypt(hash1)
if hash2 == stored expected value; send data and salt back to client

CLIENT
key := pbkdf2(email + pwd, salt, ...)
AES.decrypt(data, key)

In my scenario, the SERVER is a third party. If, say, the server went rogue and tried to steal all of the users' data, would the server be able to do so easily, knowing about the contents of hash1 and salt?

  P.S.: Does 5 million iterations somehow weaken PBKDF2 (hash cycles, etc.)?

If the party that controls the server also controls the client application then the server will always be able to retrieve the password. In that sense protecting against the server only works if very strict auditing is taking place, and then only maybe.

If the server receives a hash over the password then it can of course perform a (augmented) dictionary attack against the hash. When multiple hashes are collected then rainbow tables will also be an option. All the additional protection delivered by bcrypt of PBKDF2 will be null and void.

So yes, if the password could be found with an attack, and then PBKDF2 can be performed using the found password in your scheme. Very strong password will still offer protection against the server, of course.

PS No, the more iterations the better for PBKDF2. Cycles only occur after many more iterations, and are nothing to worry about here.


Why does AES use a Binary Field? The key idea in AES is the use of matrix multiplication and the corresponding inverse (as opposed to Fiestel).  But the algorithm does that using a GF instead of simple modular arithmetic.

Is there any obvious reason to not use simple modular arithmetic?

(Just curious.)

Well, there would be two possible ways to use modular arithmetic:

You could do the arithmetic modulo $2^n$.  However, that has some nasty properties (not all elements have multiplicative inverses, higher order bits do not affect lower order ones), and while you could get around these issues, it would require significant changes to AES.
You could do the arithmetic modulo a prime $p$.  That avoids the above issues, however the issue here is that our plaintext and ciphertext blocks are even sets of bits; elements modulo a prime $p$ are not (except for $p=2$, which doesn't sound interesting).  Hence, you'd need to add some special logic to handle that.

By using $GF(2^8)$, they avoid all the above issues; all nonzero elements have inverses, in a multiplication (or inverse), every input bit potentially affects every output bit, and a part of a block fits nicely in a field element.


AES Encryption With PBKDF2 KDF in pycrypto I am a bit new to encryption and I've seen a lot of recommendations to use a KDF for encryption and decryption. I'm a bit confused since I've been trying to encrypt the data using PBKDF2 algorithm and salt is generated using get_random_bytes, but when I try to decrypt the data I try to derive a new key using a new salt, this throws off my decryption. When I make the salt something constant for example b'salt' decryption works as expected but if I try to regenerate the salt and then regenerate the key the decryption doesn't work. My question is, should I be using the same salt for key derivation for encryption and decryption? Also if encryption happens on a server and decryption happens on the client, doesn't sending the salt over the network make using a KDF pointless? Where am I going wrong?

As a quick aside, something newer like Argon2, the 2015 password hashing competition winner, is better than PBKDF2. Using a Key Derivation Function (KDF) and the same key to encrypt many messages (for example) isn't particularly secure. There are also methods of exchanging keys like Diffie-Hellman Key Exchange, although they may not be applicable in certain use-cases.

From re-reading your question, it seems you think a KDF is a function that allows you to keep a shared secret key and generate (with random salt) the same derived key.  In which case the salt would have no effect whatsoever.
Note that PBKDF2 is built from a hash function.  In the case of pycrypto it is using HMAC-SHA512.  As such, the salt needs to be the same in order for the derived key to be the same.
When you are generating a new salt, you are generating a different hashed key.  That is exactly why salt is used. Actually, for deriving Multiple Keys can be risky with PBDKF2, once your password is found the two keys are gone. You can use PBKDF2 to generate a key and then use KDF.
The purpose of the salt is to prevent against pre-computed attacks on the hash (eg. Rainbow-table).  See more here.
Sending the salt over the network strengthens the KDF. As a simple example (I am the attacker):
Without a salt
I download a file with a list of all hashes for likely n character passwords.  I watch traffic and match many transmitted digests with my downloaded file.  I required internet, significant storage space, and network hacking skills.
With a salt
I cannot download (or generate) a file with all likely passwords as every password has too many possible hashes.  I watch traffic, and must generate a new hash file for every salt I see.

As you can see (hopefully), the salt makes it far more difficult to pre-compute anything before you see the salt.


Cryptography in wireless medium How do I implement asymmetric key algorithm into wireless medium using NS 2.35?

For example: node $A$ is a sender and $B$ is a receiver. Now, $A$ is sending a packet using $B$s public key (encryption) and $B$ decrypts that packet using its private key .

My question is: how to produce the key into that wireless node and do the privacy stuff? Is it possible at all? If, are there any books or materials regarding this?

Firstly:

RSA is computationally complex algorithm and should not be used to encrypt large data. RSA keys can be created with trusted third party. But is the system is in house then you can generate few keys through following technique shown here.

However, it is not recommended to use static set of keys for RSA (as there are security trade offs for reusing the keys).

Secondly:

You can use nested algorithms to get work done as shown below:

say $data = packet$;

$$E = AES_{ENC}(K, data) \\
K' = RSA_{ENC}(PubK, K)$$

and then share the encrypted key publicly.

You can use AES with some popular working modes like CBC-MAC, CTR, CCM etc. to achieve decent security with less computational complexity (now you can encrypt more data in less time)

And RSA will make sure the public key(of underlying AES) is secure.

On the other end:

$$K = RSA_{DEC}(PubK, K') \\
packet = AES_{DEC}(K, data)$$

Finally, Implementing it efficiently in NS2.35 is out of scope for this forum.


Observation:

An individual 1-byte pearson hash behaves like an 8 bit block cipher, encrypting the initial state using the message as key. This means that given a fixed message, each possible initial state produces a different output. This implies that a combined hash will never contain duplicate bytes.

Without this property a hash would forget about the initial state after about 1.5 kB and the combined hash would consist of identical bytes, degrading its quality to that of a single byte hash.

Never producing identical bytes is a trivial distinguishing attack, but in exchange you get a hash that doesn't produce a lot of collisions by accident.

Meet-in-the-middle attack to find pre-images:

Since the mapping between previous and next state is bijective and efficiently computable, a meet-in-the-middle attack, can find pre-images of an n bit hash in $2^{n/2}$ time, similar to how 2DES can be broken by a meet-in-the-middle attack. This is feasible for 64 bit hashes. The sponge construction used in SHA-3 suffers from a similar attack, which is why the capacity needs to be at least twice the desired pre-image size.

Pre-image attack by finding a fixed point:

The message we're targetting is called $m_0$. We're searching for a suffix $m$ such that $h(m_0)=h(m_0||m)$. This is a second pre-image on $m_0$ using that $m$ preserves the state.

We start with $n$ short messages, which we'll call the alphabet. There are $n^2$ different 2-symbol combinations, of which a fraction of $1/256$ will preserve the initial byte. We try to find about $n$ fixed points, so we need $n\approx 256$ (slightly larger $n$ might be required in practice, to compensate for random deviations).

Once we have enough fixed-points for the first output byte, we extend to two output bytes. For this, we look at sequences which consist of two one-byte fixed-points. All of these combinations are one-byte fixed-points as well, and $1/256$ of them are two-byte fixed points.

Repeating this procedure 8 times, produces an $m$ that preserves the full state. Since each iteration doubles the message length, we'll end up with a message that's 256 times the length of or short single-symbol messages (which consists of one or two bytes each).

For a 128 bit Pearson hash this produces a relatively long message ($2^{16}$ symbols or 100-200kB). You can start with $n\approx 256^2$, fixing two bytes of the hash at the same time, which increases the cost to $\approx 2^{32}$ hashes, which is still feasible. In exchange for the higher runtime, it reduces the message length back to 256 symbols or 500-1000 bytes.

As poncho pointed out, this attack can easily be adapted to first pre-images.

A quick and dirty implementation of this attack is available at: https://gist.github.com/CodesInChaos/4a399a26b98221155a92

My code naively enumerates all $n^2$ combinations and filters out the approximately $n$ that produce the desired result. Running the hash function in reverse to execute a meet-in-the-middle attack, it's possible to reduce these $n^2$ hash computations down to about $n$ hash computations. This optimization doubles the length of the hash you can break with a given cost and message size. So breaking 128 bit hash should have a cost of about $2^{16}$ hashes and breaking a 256 bit hash about $2^{32}$ hashes, where each message is about 1 kB.

Concerning your "improved" version:

The second pre-image attack above works without any changes to the attack code. Just replace the hash function with the "improved" version.


How does the attacker include input before compression and encryption in CRIME? I have read this article about the CRIME attack against TLS and SPDY. The article says that:

  What is not yet clear is how the attacker is including their input in the source material before it gets compressed and encrypted.

And this is my question: How does the attacker include their input before compression and encryption?

Also, I have the feeling that this is an inconsistency: If the attacker can insert their input before compression and encryption in TLS, isn't it necessary that the attacker is the real client itself?

Please explain what I am missing here in order to understand the CRIME attack.

Malicious JavaScript could trigger calls against any SSL server. Although this JavaScript is not able to actually read the cookie for that server directly, the browser will send that cookie through the SSL tunnel.

The JavaScript will then alter the URL, keeping the server but changing the path or request parameters. In that way it can inject data before compression and try to identify parts of the cookie.


ANSI X9.31 standards for generating random numbers The NIST-Recommended Random Number Generator Based on ANSI X9.31 Appendix A.2.4
Using the 3-Key Triple DES and AES Algorithms has 3DES being used three times for each 64-bit block of random data desired, e.g.

$I = ede_K (DT)$, $R = ede_K(I \oplus V)$ and a new $V$ is generated by $V = ede_K(R \oplus I)$.

OpenSSL seems to be using 3DES in ECB mode (fips_rand.c).

My question is...  if you have a cipher running in CTR mode could you just encrypt a string of null bytes as long as desired instead of doing three different encryption rounds on each block?

Also, what is the recommended format for DT? Normally timestamps are 32-bits, not 64-bits.

If you're asking why the X9.31 rng was designed the way it was, rather than some other way, I'm not certain if anyone other than the original authors could say.  The core design dates back to at least 1985 (it was included in X9.17), and it originally used DES (and was later upgraded to use 3DES).  I suspect that the original authors would not have been confident in using DES in counter mode.

As for the DT format, well, the requirement in X9.31 is that the value is distinct everytime you generate a block.  It's there to make sure that the RNG doesn't fall into a short cycle, and so it wouldn't be horrible if DT changed only occasionally (e.g. if you generated 256 values with the same DT, the probability that the cipher runs into a cycle during those 256 values is about $2^{-56}$).  A secondary reason is to feed a slight amount of additional entropy into the RNG -- it doesn't do that all that well, though.  As long as you abide by that, any format works.  In your case, it's easy enough to abide by both the spirit and the letter of the law; formulate a DT where the top 32 bits are the Timestamp you get from the system, and the lower 32 bits is just a counter which is incremented everytime you generate a block.  That way, the DT value changes everytime (because the lower 32 bits always change), and you feed the slight amount of entropy from the current data/time.

As for OpenSSL, well, it appears to be an implementation of the X9.31 (using 2-key 3DES; that is what X9.31 originally asked for, however the NIST document you gave now specifies 3-key 3DES).

Also, if you need a secure RNG, I would suggest you look at these RNGs, especially the CTR_DRBG (whose base idea is just an block cipher in counter mode just like you suggested).


What is an elliptic curve cofactor? As the title says, I have some doubts about the term "cofactor" used to describe elliptic curves.

AFAIK, it's a factor of the curve order, but why is it explicitly specified in some parameter lists then?

How does it apply to the curve point addition / etc. algorithms?

In cryptography, an elliptic curve is a group which has a given size $n$. We normally work in a subgroup of prime order $r$, where $r$ divides $n$. The "cofactor" is $h = n/r$.

For every point $P$ on the curve, the point $hP$ is either the "point at infinity", or it has order $r$; i.e., when taking a point, multiplying it by the cofactor necessarily yields a point in the subgroup of prime order $r$.

The cofactor matters inasmuch as it is not equal to $1$:

When the cofactor is $1$, then the subgroup is the whole curve. Any non-zero point is a generator. Any incoming point $(x,y)$ that fulfills the curve equation is part of the subgroup. Everything is fine.
When the cofactor is not $1$, then the subgroup of prime order is a strict subset of the curve. When considering a point, verifying that the curve coordinates match the curve equation is not sufficient to guarantee that the point is on the appropriate subgroup. Moreover, there will be points whose order is not a multiple of $r$. This is what happens, for instance, with Curve25519, which has a cofactor of $8$. Such curves require some extra care in the protocol that uses them. For instance, when doing a Diffie-Hellman key exchange over Curve25519, the Diffie-Hellman private keys must be chosen as multiples of 8 (which is expressed as: "set the three least significant bits to zero"); this ensures that the points will be in the proper subgroup.


What are the required security properties for salts? I was recently thinking about password hashing (maybe caused by the PHC progression).

I started to think a little more about it and got stuck at this question:

What security properties do password-hashing related salts actually need?

I think they need to be globally unique (that's how I usually construct them). This means the same salt should never be used twice - by anyone. This would mean I'd had to choose my salt to be collision resistant resulting in 512-bit length and a CSPRNG for generation.

Is this overkill or are shorter and less defensive solutions also secure? (this is basically the same question as the bolded)

If you need to make assumptions regarding the schemes, standard schemes (without pepper) should be assumed, like bcrypt, scrypt, Argon2, PBKDF2.

512 bits is overkill for even global uniqueness. 256 bits should be enough, with a good random number generator: even if every person on earth generated one every nanosecond, it would take a million million years to reach the birthday bound.

However, I agree that global uniqueness is a good idea. If anyone anywhere uses the same salt and password hash (or other salt-using algorithm), an attacker could theoretically attack those in less time than otherwise.

If you had a unique application-specific pepper (additional salt that is shared by all users), you could safely use salts that are only locally unique, for example outputs from a counter. This might in some cases be useful for saving space.


What is the purpose of pre master secret in SSL/TLS? I studied about SSL/TLS and learned that client and server must share keys below.

common key for encryption
common key for generating message authentication code

Then, in SSL/TLS, a client doesn't send these keys to server directly, but it sends pre master secret and generates keys from it.
This is why?

The point of a premaster secret is to provide greater consistency between TLS cipher suites. While RSA cipher suites involve the client sending a random 48-byte premaster secret directly to the server, other suites do more complex things to generate the secret, and end up with a secret that might have some structure to it. For instance, (EC)DH suites use (elliptic curve) Diffie-Hellman to negotiate the secret; the output of this can be longer or shorter than 48 bytes, and it might potentially be poorly distributed (which could be bad). For PSKs, it's even worse - the premaster secret basically is the PSK. For various reasons, it's nice to have the master secret be some consistent format; it lets you separate the key-exchange side from the encryption side. Likewise, it's nice to have the master key be pseudorandom.

While you could require key exchange mechanisms to output the master secret directly meeting specific requirements, just about every key exchange system would do it the same way anyway (i.e. pass the negotiated value through the TLS PRF). Since most key exchange methods result in a shared secret that needs some transformation, and that transformation works well for basically every key exchange method, they just put it in the TLS spec for all methods to use.


Formula for E(m) of the Atbash Cipher I'm studying mathematical cryptography and have been asked to find the encryption function for the Atbash cipher I know that it means a=z, b=y, c=x and so on but putting it into a formula has me a bit stuck. I already know affine ciphers version of the atbash is $ -(x+1) mod m $

Any help would be greatly appreciated!
Thanks

The math goes: add the integer assigned to a, the integer assigned to z, and from that constant (which can be pre-computed) subtract the integer assigned to the letter to encode; that gives the integer assigned to the encoded letter.

This works for a to z and encodings with consecurive letters of the alphabet assigned consecutive integer values (including ASCII; assigning 0 to a and 25 to z; assigning 1 to a and 26 to z). Usual associativity and commutativity rules for addition in $\mathbb Z$ are enough to prove that a is encoded to z, and vice versa. The rest follows by uh, intuition? Or induction if we really strive for rigor.

In C, that gives

char Atbash(char x) {
  return ('a'+'z')-x;
}


Extension of a password hashing algorithm using Fibonacci I am right now taking a class named Applied Cryptography and our final project is to create a password hashing method using at least one existing algorithm and then add additional steps to make it harder to decrypt.

I am using SHA1 in a Console Application in c#.

The user input is hashed using SHA-1. For each byte of the resulting hash I compute the Fibonacci series of the byte value as int, and append it to a string, if it is positive. If it is not, I append 0.

The result of the Fibonacci computation is hashed using SHA-1 once more.

This is my code so far

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace Proyecto
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = Console.ReadLine();
            StringBuilder fibo = new StringBuilder();
            string result1, result2;
            result1 = GetSHA1(str);
            for (int i = 0; i < GetSHA1(str).Length; i++) fibo.Append((Fibonacci(result1[i]) > 0) ? Fibonacci(result1[i]) : 0);
            result2 = GetSHA1(fibo.ToString());
            Console.WriteLine(result1);
            Console.WriteLine(fibo);
            Console.WriteLine(result2);
            Console.ReadLine();
        }

        public static int Fibonacci(int n)
        {
            int a = 0;
            int b = 1;
            // In N steps compute Fibonacci sequence iteratively.
            for (int i = 0; i < n; i++)
            {
                int temp = a;
                a = b;
                b = temp + b;
            }
            return a;
        }

        public static string GetSHA1(string str)
        {
            SHA1 sha1 = SHA1Managed.Create();
            ASCIIEncoding encoding = new ASCIIEncoding();
            byte[] stream = null;
            StringBuilder sb = new StringBuilder();
            stream = sha1.ComputeHash(encoding.GetBytes(str));
            for (int i = 0; i < stream.Length; i++) sb.AppendFormat("{0:x2}", stream[i]);
            return sb.ToString();
        }
    }
}

I want to know if the additional Fibonacci round improves the strength of the function as a password hashing function, and if not, if you can give me some suggestions.

Ignore the integer overflow issue I mentioned in a comment, for a moment.

I don't see how this adds any security.

For all $n>2$, the function you are calling Fibonacci is one-to-one, and since $n<256$, you could easily build a lookup table without much memory to invert the function.

Therefore, to break this, all one has to do is invert the Fibonacci related stuff (not too hard), then attempt to break the SHA-1 hash. So, it isn't much harder than just breaking the SHA-1 hash by itself.

  if not, if you can give me some suggestions

Well, that would just take all the fun out of your class, now wouldn't it. That said, look into functions like PBKDF2 and bcrypt to see how they make things harder.

The integer overflow issue could make it harder to invert the function. Though, likely not in a cryptographically secure manner. But to really say no, it doesn't add security, I'd have to check how the integer overflow problem manifests itself.


Which Fully Homomorphic Encryption schemes are fastest? I want to know which one Fully homomorphic encryption schemes are the best in terms of time to encrypt & decrypt or compare between them ?(Preferred valid link)

Encryption and decryption are usually the least problematic operations, in terms of performance, in FHE schemes.

The main software library I know for FHE is HElib, which is regularly maintained and been around for a while now.
There are several different papers about various benchmarks of HElib.
The most recent one I could find was HEtest: A Homomorphic Encryption Testing Framework. In Section 6.7 you find their encryption and decryption benchmarks. They state 33 ms for encryption and up to 5 seconds for decryption.

Very recently, there appeared a new library $\Lambda \circ \lambda$ (code can be found here).
In Section E.2.2 they provide some performance results for a Somewhat Homomorphic Encryption (SHE) scheme, which allow you to evaluate circuits of a fixed depth.
If I read the table (Figure 10) correct, then their encryption needs around 371 ms and their decryption 2.3 ms.


Using Hadamard Form of a Matrix in the Block Cipher Definition: A matrix A of size $2^n$ is a  Hadamard matrix, if has the following form
$$
A=
\left(
\begin{array}{cc}
U & V \\
V & U
\end{array}
\right)_{2^n\times 2^n}\, ,
$$
where $U$ and $V$ are also Hadamard matrices.

Example:  A Hadamard matrix A of size $2^2$ is as follows
$$
A= \left( \begin {array}{cccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}}
\\ a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}}
\\ a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}}
\\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}\end {array}
 \right)\, ,
$$
Where $a_i$, $0\leq i \leq 3$ are from any arbitrary field.

Consider B is a $2^n\times 2^n$ matrix such that the $(i,j)$the entry of B, denoted B$[i,j]$, is defined by B$[i,j]=a_{i \oplus j}$ where $i,j \in \{0,1,\cdots , 2^{n}-1\}$ and $i \oplus j$ means Xor between two numbers $i$ and $j$(for example $2 \oplus 3=1$ since $10 \oplus 11=01$).

Example: A matrix B of size $2^3$ is
$$
B=
 \left( \begin {array}{cccccccc} a_{{0}}&a_{{1}}&a_{{2}}&a_{{3}}&a_{{4
}}&a_{{5}}&a_{{6}}&a_{{7}}\\ a_{{1}}&a_{{0}}&a_{{3}}
&a_{{2}}&a_{{5}}&a_{{4}}&a_{{7}}&a_{{6}}\\ a_{{2}}&a
_{{3}}&a_{{0}}&a_{{1}}&a_{{6}}&a_{{7}}&a_{{4}}&a_{{5}}
\\ a_{{3}}&a_{{2}}&a_{{1}}&a_{{0}}&a_{{7}}&a_{{6}}&a
_{{5}}&a_{{4}}\\ a_{{4}}&a_{{5}}&a_{{6}}&a_{{7}}&a_{
{0}}&a_{{1}}&a_{{2}}&a_{{3}}\\ a_{{5}}&a_{{4}}&a_{{7
}}&a_{{6}}&a_{{1}}&a_{{0}}&a_{{3}}&a_{{2}}\\a_{{6}}
&a_{{7}}&a_{{4}}&a_{{5}}&a_{{2}}&a_{{3}}&a_{{0}}&a_{{1}}
\\ a_{{7}}&a_{{6}}&a_{{5}}&a_{{4}}&a_{{3}}&a_{{2}}&a
_{{1}}&a_{{0}}\end {array} \right)=a_{i \oplus j}\qquad
0\leq i,j \leq 7 \, .
$$

My question: Why the matrix B=$(a_{i \oplus j})$, $0\leq i,j \leq 2^{n}-1$, is an $2^n\times 2^n$ Hadamard matrix?

My Try: I can proof it by induction on $n$, but I would like to see its proof with other method.

Background: When entries of a Hadamard matrix come from the finite field $GF(2^q)$ and be an MDS matrix, then the Hadamard matrix can be used in the diffusion layer of block cipher such as Khazad block cipher

This is evident. Let $B$ be a $2^n \times 2^n$ matrix. We have:

  $$a_{i\oplus (j+2^{n-1})}=a_{(2^{n-1}+i)\oplus j},a_{i\oplus j}=a_{(2^{n-1}+i)\oplus (2^{n-1}+j)}.$$

So, $B$ has the following form and therefore is a Hadamard matrix as follows
$$B=
\left(
\begin{array}{cc}
U & V \\
V & U
\end{array}
\right)_{2^n\times 2^n}\, $$


Security of RSA with $\gcd(pq, (p-1)(q-1))\ne 1$ The Congress of ThéOùÇa enacted that civilian use of any public-key encryption system is authorized on the territory of ThéOùÇa, subject to meeting certain security requirements published by the Ministry of Defense. The essence of these is:

  ..must operate per the internationally recognized RSAES-OAEP algorithm and relevant requirements in PKCS#1 V2.2, with a 2048-bit public modulus $n$ product of two primes $p$ and $q$. In order to ensure separation of key domains with the Pailler cryptosystem used for national defense purposes, the key generator shall be such that $p$ and $q$ also meet the requirement $\gcd(pq, (p-1)(q-1))\ne 1$. Demonstration of conformance to that requirement shall be by submitting the mathematical description of the key generation method to the Ministry of Defense of ThéOùÇa.

Can a public-key encryption system lawfully usable by civilians on the territory of ThéOùÇa be secure? If yes, give a possible submission to the Ministry of Defense (English is spoken in ThéOùÇa). In either case, make a cryptographically convincing argument.

Thanks to Poncho for spotting a big mistake in my transcription of the Official Journal of ThéOùÇa, now fixed.

This is not homework. If you wonder, inspiration was that recent question.

Okay, I came up with this, it's not a complete answer and the attack presented is pretty weak without a follow-up algorithm for breaking a somewhat unbalanced modulus but let me know if you spot any flaws or have any ideas to improve it...

If $n = pq$ with $p, q$ prime and $\gcd(pq, (p - 1)(q - 1)) = r > 1$ then clearly $r = p$ or $r = q$. Now obviously $q - 1$ cannot divide $p$ and so we must have $p$ divides $q - 1$, without loss of generality. Thus:
$$q - 1 = kp ~ ~ ~ \text{for some} ~ k > 1$$
Now suppose that $k$ is $B$-powersmooth for small $B$, then we have $M = \alpha k$ for $M$ a suitable product of prime powers up to $B$, some $\alpha$ and so for any $a$ we have:
$$a^{Mn} \equiv a^{Mpq} \equiv a^{(\alpha k p)q} \equiv a^{\alpha(q - 1)q} \equiv 1 \pmod{q}$$
And so in general we find that:
$$\gcd(a^{Mn} - 1, n) = q$$
Therefore in order for $n$ to be usable in the context of RSA, $k$ should not be smooth. Realistically we will be able to try $B$ up to $2^{80}$ or so (you won't be factoring the 2048-bit modulus through general purpose algorithms anyway) which means $k \approx 2^{81}$ and a special key generation technique needs to be used, probably involving letting $2rp = q - 1$ for large prime $r$ with $k = 2r$.

And since $k$ is large, that means $q/p \approx 2^{81}$ so the modulus is unbalanced. Perhaps this enables polynomial-time factorization of the 2048-bit modulus via existing methods which rely on particularly poor selection of $p$ and $q$, or perhaps the scheme is secure with careful selection of $k$. Further work is needed to determine which conclusion is the right one (but I am less and less confident in this scheme).


Encrypting a broadcast message decryptable by a subset of receivers I wasn't certain how to title this request/problem, but here goes:
I'm A, and I want to send a message that is received by B, C, D.
Each receiving entity here is part of some set of domains D1, D2, D3:
B: {D1, D2}
C: {D2}
D: {D3}

How do I encrypt a message with a single key that I, A send to B, C, D such that it can only be decrypted by receivers in a given domain subset (e.g Msg(D1,D3) = B and D can decrypt the message)?
Assume it is possible to convey to A, B, C and D some security material ahead of time before having to send the message.

Perhaps Attribute-based Encryption is what you are looking for.
From the two schemes (KP-ABE, CP-ABE), CP-ABE can solve your problem. You can set the attributes of each identity according to their domain set and encrypt the file with policy using OR. The example you have given, Msg(D1,D3) can use (D1 OR D3) as a policy to encrypt.
For more detailed information on the mathematics behind the scheme, you can read this paper. Also, there is an opensource implementation available too Zeutro's OpenABE if you are interested.


How to perform Multiplicative Inverse Modulo in IDEA How to perform the Multiplicative Inverse Modulo in International Data Encryption Algorithm? I don't understand on how to perform it…

For example, let's say I have a value of cf80 and the value that is appearing to me is this 3080. This is the thing that I've done based on my understanding:

answer = 53120 % 65537
53120(integer value of 3080) = 3080

When I convert the result in hexadecimal, the value is 3080 but the correct result should be 9194.

Well, the multiplicative inverse of $a$ is defined to be that value $b$ for which $a \times b = 1$, where $\times$ is the multiplication operation in the field/ring/group in question.

Because we're talking about the group of multiplication modulo 65537, that means that the problem is, given $a$, find $b$ such that $ab \bmod 65537 = 1$.

Now, the % operator is C doesn't do it.  The classical way is to use the Extended Euclidean algorithm, where the two inputs to the algorithm is $a$ and $65537$; and have it find a solution to the equation $ax + 65537y = GCD(a, 65537) = 1$; the value $x$ is the multiplicative inverse you're looking for.

Of course, since there are only 65536 possible inverses, another possibility is simply have a table of the 65536 possible inverses, and just do a lookup.  In that case, you can use the Extended Euclidean algorithm to build the table.

Oh, and as a reminder; idea interprets the 0000 bit pattern as the value 65536 as far as multiplication is concerned (as the value 0 doesn't have an inverse).


AES GCM SIV implementation I have a library which implements AES GCM algorithm. However, as you know even a single nonce reuse can have catastrophic results.
As we can't guarantee a unique IV every time, I would like to run the SIV (Synthetic Initialization Vector) on the nonce every time.
I want to implement the SIV outside of the AES GCM. As, I am not a fan of mathematics, I really find it hard to understand the AES-GCM-SIV spec.
However, I can't find any sample implementation of the SIV anywhere. Can you please kindly help me in understanding and in implementation of SIV?

It sounds like you're thinking of AES-GCM-SIV as "AES-GCM with an SIV layer on top."  It's not.  Rather, AES-GCM-SIV is a separate encryption mode build out of similar (but not identical) components as AES-GCM, and where the components are combined in a different way.  While AES-GCM-SIV is in some ways similar to AES-GCM, you can't actually implement AES-GCM-SIV as a wrapper on top of an existing library that implements AES-GCM.
What makes things a bit confusing is that there is also something called the generic
"SIV construction" that allows a nonce-misuse-resistant authenticated encryption mode to be constructed out of any conventional (non-authenticated) encryption mode meeting certain technical criteria plus any pseurodandom function (PRF) on the plaintext space.  For example, AES-SIV (RFC 5297) is an instance of the SIV construction with AES-CTR as the encryption mode and CMAC* (a multi-input variant of CMAC) as the pseudorandom function, while AES-GCM-SIV is essentially an instance of the SIV construction with (again) AES-CTR as the encryption mode and POLYVAL (a variant of the AES-GCM pseudorandom function GHASH) as the PRF.
But that doesn't mean that you can just take an AES-GCM implementation and use it to implement AES-GCM-SIV, at least not without first pulling it apart into its component parts.  And even then, the components of the two schemes (as standardized in their respective RFCs) differ in some details (like byte order; see RFC 8452 appendix A), so you can't just reuse the parts without modification, either.
Technically, I believe you could implement AES-GCM-SIV on top of GHASH and AES-CTR, if your crypto library exposes both of those directly.  However, that would require implementing POLYVAL on top of GHASH, which, while technically possible, is somewhat awkward and inefficient due different byte orders used by the two hashes.


Zero-knowledge integer comparison This question is a follow up to the question I asked here. Basically, the protocol I described  has a flaw (as pointed out in this answer), and I am trying to figure out how to address it. The setup is:

Alice has a secret value $a$ to which she's publicly committed by sharing $A=a∗G+X_a$, where $X_a$ is her public key
She calculates a new value $a' = a - c$
And then  publicly commits to $C = c *G$ and to $A′=a'∗G+X_a$

An independent observer can check that the math was done correctly by verifying that $A=A′+C$. However, this doesn't quite work because Alice can underflow $a$ and the verification would still pass.

One way to address it that I can think of is for Alice to prove that $a > c$ (or that $a' < a)$, but I'm not sure how this can be done without revealing $a$ or $c$.

Edit2: removed a potential approach because it doesn't seem to work.

Statement $a > c$
could be proved as $a - c - 1 = b_1^2 + b_2^2 + b_3^2 + b_4^2$.
According to Lagrange theorem,
a 4-tuple of integers exists for any non-negative integer such that it equals to the sum of squares.
This kind of proof was suggested by Helger Lipmaa (On diophantine complexity and statistical zero-knowledge arguments. ASIACRYPT 2003).
Proving statements about integers (not finite field elements) committed with Okamoto-Fujisaki commitment scheme, is doable
with a group of order hidden from Prover.

Scenario described previously looks somewhat like a Zcash JoinSplit (section 1.2 High-level Overview).


Is there more than one public key for a private key? Does deriving the public key from an RSA private key always yield the same result? And if so, does this generally apply to all asymmetric cryptosystems?

Does deriving the public key from an RSA private key always yield the same result?

Well, if $e$ is the correct public exponent, then any value of the form $e + k \cdot \text{lcm}(p-1, q-1)$ (for any integer $k$) is also a correct public exponent (in the sense that it would function equivalently when used with the same modulus).

Of course, we usually select $e$ to be small; the alternative public exponents are huge (and hence much slower).  In addition, publishing two different public exponents of that form would allow someone to efficiently factor the modulus, and hence taking advantage of it might not be that great of an idea...

  And if so, does this generally apply to all asymmetric cryptosystems?

Not in general.  Another example where it doesn't apply would be NTRU; the private key is a polynomial $F$ (that meets certain properties); the public key is another polynomial $pF^{-1}G$ (where $G$ is a sparse polynomial); we can select a different $G$ and obtain a different public key that works equivalently.


How does the random oracle model simplify proofs versus using the standard model? If I use the standard model, then the proof must rely on mathematical assumptions.

Will this security proof, generally be longer/more complex?

Is there an example where the random oracle has been used to prove security, then removed to shows this?

Yes, there are examples where the random oracle model has been first used, then removed, Yes, the proof becomes, in the end, much (much) more complex. But in fact, simplicity of the proof is not the reason why we initially prove security in the ROM. The main reason is that we don't even know what security property our hash function must satisfy!

Intuitively, a random oracle models an idealized hash function that would satisfy all the security properties you can dream of. So, consider a protocol that uses a hash function $H$. It is often the case in cryptography that this protocol seems secure, in the sense that we do not know how to break it. However, to prove that it is secure, we need a security reduction: an efficient reduction from the existence of an adversary that breaks the protocol to the existence of an algorithm that contradicts some security property of our hash function.

But then the question becomes: which security property? Do we want $k$-wise independence? one-wayness? Collision-resistance? Multi-collision-resistance? Output intractability? Correlation intractability? Correlation robustness? Extractable collision resistance?

All the properties I list above are actually security properties of hash functions which have been used in security proofs of various cryptographic construction. But there are many more. Dozen of them, at least.

Because of the hardness of finding the right security notion, cryptographers usually like to argue security in the random oracle model. If you can do so, intuitively, this guarantees that we are likely to be able, someday, to prove the security of our protocol under some assumption about our hash function. If you fail, it might simply mean that your protocol is insecure - so that's a nice sanity check. Proofs in the ROM are usually very simple: the adversary sees nothing at all about the function, it's behavior is perfectly random, so you can just count the information accumulated by the adversary about the random oracle, and compute the exact probability that he finds some specific information. You have also access, in the proof, to all the queries made by the adversary to the oracle - and you can even manipulate the oracle if you like.

  Is there an example where the random oracle has been used to prove security, then removed to shows this?

Many. Here are a few such examples:

Oblivious transfer extension is a core cryptographic primitive in the area of secure computation, which allows to achieve much more efficient protocols by transforming a small number of "oblivious transfers" into a much larger number, using only a few hashes for each new oblivious transfer generated. An efficient OT extension protocol was first given in this paper. The security is proven in the ROM, but it can also be proven assuming that the hash function statisfies correlation robustness, a property which they introduce in the same paper.
The free-XOR trick is a method to improve the efficiency of garbled circuits, also a core primitive in secure computation. It was first introduced here and proven secure in the ROM, and later proven secure in the standard model in this paper by replacing the hash by a special symmetric encryption secure against a certain type of related-key attacks.
The Fiat-Shamir transform is, arguably, one of the most famous applications of the ROM. It allows to transform interactive zero-knowledge protocols into non-interactive zero-knowledge protocols. Proving security of non-interactive protocols obtained through the Fiat-Shamir heuristic has been a major open problem for more than 3 decades, one which attracted a lot of attention from the cryptographic community. The first results in this respect were mainly negative, proving the uninstantiability of the Fiat-Shamir transform in the standard model, for some class of protocols. However, things have changed recently: it has been shown that a large class of interactive protocol can be made non interactive with the Fiat-Shamir transform, if the hash function satisfies correlation intractability for an appropriate class of samplers. Then, hash functions satisfying correlation intractability for important class of samples have been constructed from various assumptions, culminating with a very recent construction of such hash functions from the LWE assumption, which finally solved the long standing open problem of constructing non-interactive zero-knowledge proofs from LWE.
Other situations include building point function obfuscation with auxiliary inputs, or very strong forms of leakage resilient pseudorandom generators, both known in the ROM, but which were only recently obtained in a beautiful paper with a security analysis in the standard model.
RSA-OAEP has been analyzed and proven IND-CPA secure in the standard model here, under the $\phi$-hiding assumption, and assuming that the underlying hash function was $k$-wise independent. It was previously only known to be secure under the RSA assumption when modeling the hash function as a random oracle.

This is just a sample of the things that come directly to my mind, there are many more.


Is BLS signature scheme strongly unforgeable? I would like to know if BLS signature scheme is strongly unforgeable under adaptive chosen message attack. If it is not, is it possible to modify the BLS scheme in order to reach this property ?

Thank you in advance.

BLS signatures are computed by hashing the message $m$ from the message space $\mathcal{M}$ to a source group of a bilinear pairing $e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$ using a hash function $H: \mathcal{M} \to \mathbb{G}$ and exponentiating $h$ with the secret key $x$, i.e., a signature $\sigma$ is of the form $$\sigma := H(m)^x.$$

The hash function maps each message to a uniquely determined value (there could be multiple messages which are mapped to the same value), and $x$ is fixed by the public key $g^x$. This means that BLS signatures are even unique. That is there is only one signature for each message. This is an even stronger property than unforgeability, i.e., every existentially unforgeable and unique signature scheme is also strongly existentially unforgeable.

For more details, one could refer to Hovav Shacham's PhD Thesis (one of the inventors of BLS signatures). He also argues that he does not further consider strong unforgeability, as the schemes presented in his thesis (including BLS signatures) are all unique (cf. Page 19 before Definition 3.2.1).


Why a bulk encryption key and frequently used key needs to have a shorter lifetime? In NIST standard (NIST SP800-57), the bulk data encryption key and other key material that is used frequently have a short lifetime. As quoted from (Sec. 5.3.6, point 6.b.):

The originator-usage period recommended for the encryption of large volumes of data over a short period of time (e.g., for link encryption) is on the order of a day or a week. An encryption key used to encrypt smaller volumes of data might have an originator-usage period of up to two years.

Also, more generically, in Sec. 5.3.1. Factors Affecting Crypto periods, it stated in fifth entry:

The volume of data flow or the number of transactions;

I do understand that, intuitively, the more a key is used for an operation, the more "information" about that key in this operation is revealed. But I can't figure out a more concrete rationale behind it. Since such consideration is for rather generic (does not seems to be based on the property of a specific key type). I wonder if there is any generic / theoretical framework describing how using a key reduces the "reliability" of its secrecy?

Most symmetric encryption techniques use an $\text{IV}$. An important characteristic is that the $\{key, IV\}$ pair must never be reused.
The $\text{IV}$ is randomly generated for every use, and some cipher modes (eg: GCM) break it down into one part for the nonce, one part for the counter. eg: for a 128 bit $\text{IV}$, the nonce is 96 bits, the counter is the remaining 32 bits.
The counter usually starts at $0$ for every data and is incremented for each block. So we only care about the nonce.
Given a 96 bit nonce, the birthday paradox tells us that the probability of nonce reuse after $2^{32}$ uses is approximately $2^{-32}$. The $2^{32}$ reuse probability is recommended by NIST.
To reach $2^{32}$ uses in a week, we need to perform approximately $7000$ operations per second. This is not an outrageous number, link-level encryption can easily handle this.
So with heavy usage of a symmetric key, we want to make sure we limit the number of uses to something well below the probability of nonce reuse. Taking safety margins into account for the above example, we might pick one day as a reasonable lifetime.


Differential Privacy: why $\delta$ negligible on the row numbers? The definition of differential privacy says that an algorithm  $M$ is $(\epsilon,\delta)$-differentially private if

$$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$

where $D,D'$ differ by one row and $\delta$ is  $\text{negligible}$ in the number of database rows, so $\delta< \frac{1}{p(n)}$ with $n$ being the number of database rows; why do we take $n$ as parameter for this negligible function?

$\varepsilon$-differential privacy is absolute: for any pair of databases, you cannot gain more than a small amount of probabilistic information about a single individual. When you add or remove an individual in your database, all possible outputs of your algorithm can appear with similar probability.

By contrast, $(\varepsilon,\delta)$-differential privacy allows this process to fail sometimes: you can have an output that happens with $\delta>0$ probability if the individual is present, and never happens otherwise. If you're super unlucky and this output comes out of your algorithm, an attacker can know that the individual in question is in the set.

Now, how often does that happen? How many users in the dataset are at risk? Well, each user has a $\delta$ probability that this might happen to them. So on average, this will happen $\delta \cdot n$ times (expected value of a binomial law of parameters $(n,\delta)$).

You want $\delta \cdot n$ to be small, because you don't want to leave any user at risk. If $\delta=\frac{1}{100\cdot n}$, you can say "with 99% probability, this bad scenario doesn't happen". But if delta is not a negligible function in $n$, then on average, your algorithm will leave some users at risk when $n$ grows.


Does the nonce really have to be hashed as part of the challenge in a Schnorr signature? From this article: https://tlu.tarilabs.com/cryptography/digital_signatures/introduction_schnorr_signatures.html#why-do-we-need-the-nonce

The article states that the challenge e = H(P || m) is insecure, and that e = H(R || P || m) should be used instead. The signature is s = k * e, where k is the private key.

My question is: what if we used the insecure challenge e = H(P || m) and made the nonce part of the signature like so: s = r + (k * e)? Would that still be secure, or is there a way to extract the private key with this approach?

I've tried to adapt the Rust code example to see if the secret key could still be extracted from the public information with this adapted signature scheme, but it looks like it's still not possible:

extern crate libsecp256k1_rs as secp256k1;

use secp256k1::{SecretKey, PublicKey, thread_rng, Message};
use secp256k1::schnorr::{ Challenge};

// This one tests that adding r/R makes key extraction impossible
#[allow(non_snake_case)]
fn main() {
    // Create a random private key
    let mut rng = thread_rng();
    let r = SecretKey::random(&mut rng);
    println!("My private random value is: {}", r);

    let R = PublicKey::from_secret_key(&r);

    let k = SecretKey::random(&mut rng);
    println!("My private key: {}", k);

    let P = PublicKey::from_secret_key(&k);

    // Challenge, e = H(P || m)
    let m = Message::hash(b"Meet me at 12").unwrap();
    let e = Challenge::new(&[&P, &m]).as_scalar().unwrap();

    // Signature (with nonce)
    let s = r + (e * k);

    // Verify the signature
    assert_eq!(PublicKey::from_secret_key(&s), R + (e*P));
    println!("Signature is valid!");

    let hacked = s * e.inv();
    assert_eq!(k, hacked);  // fails
    println!("Hacked key:     {}", k)
}

A signature under a public key $P$ is a pair $(R,s)$ such that $[s]G = R + [e]P$, where $G$ is the standard base point, and $e$ is the challenge.

If $e = H(P, m)$ doesn't involve $R$, then I can just pick $s$ arbitrarily and compute $R = [s]G - [e]P$ to forge any signature I want.

The motivation for the Schnorr signature scheme is the Schnorr identification protocol, whereby a prover named Peggy aims to convince a verifier named Victor that she knows the secret $k$ such that $P = [k]G$—that is, $\log_G P$, the discrete log of $P$.  The dialogue goes something like this:

  VICTOR (given $P$): Hey Peggy, do you know $\log_G P$?

  PEGGY (chooses $r$ uniformly at random, computes $R = [r]G$): Yes, but I can't tell you directly.  Instead, here's another point I know the discrete log of: $R$.

  VICTOR (chooses $e$ uniformly at random): OK.  Can you tell me what $\log_G R + e \log_G P$ is?

  PEGGY (computes $s := r + e k$): Why, yes, in fact—it's $s$.

  VICTOR (confirms $[s]G \stackrel?= R + [e]P$): whoa…OK, I guess maybe you do know $\log_G P$.

This protocol is guaranteed not to leak $k$ as long as Peggy chooses $r$ and Victor chooses $e$ independently and uniformly at random each time—in other words, it's an honest-verifier zero-knowledge protocol.

This protocol is convincing to Victor because, if you think of Peggy as a machine (typical of a man like Victor to do in a patriarchal society!), and you suspend the computation in the middle and run it forward with two different challenges $e$ and $e'$, then the resulting values $s$ and $s'$ lead to recovery of $k$ by $(s - s')/(e - e')$, so unless Peggy just got astonishingly lucky for one run (we work with a space of possibilities for $e$ so large that this is not plausible), she must know $k$.

On the other hand, if Peggy doesn't choose $R$ until she already knows what the challenge is, she could just choose $s$ arbitrarily and then derive $R := [s]G - [e]P$.  That's why it's crucial that she commit to $R$ by sharing it with Victor first.

We turn this protocol into a signature scheme by the Fiat–Shamir heuristic: We simulate the challenge that Victor would have chosen, by a random oracle; then instead of an interaction, we get a noninteractive receipt that Peggy can compute on her own, and that anyone in the world can verify later on requiring no further interaction with Peggy.  For the Fiat–Shamir heuristic to work, though, we have to pass in everything Peggy would have committed to Victor so far in the protocol.  That means, in this case, that we have to pass in $R$ and whatever message $m$ Peggy wants to attest to.

You're not the first person to wonder about this!  This trick—forgetting to hash in $R$ along with everything else—was used recently by the Swiss election authority to fail to convince cryptographers that their newfangled electronic voting system is verifiable—along with some other tricks—despite reams of paper on cryptidigitation to prove their software correct.  Also the New South Wales election authority, with the same software, despite being alerted to the problem at the same time.


Why isn't Rabin-Williams cryptosystem widely used? I think we all know RSA. And of course we also know DJB (a.k.a. Daniel J. Bernstein).

Now some already have noticed that he has an opinion towards cryptographic questions.

In his 2008 paper ("RSA signatures and Rabin–Williams signatures:
the state of the art" by Bernstein) on state-of-the-art signature schemes he documents the "evolution" of RSA and I get the impression he's advertising the usage of the rabin-williams (RW) cryptosystem with the optimizations mentioned in the paper.

Now (finally) my question:
As Rabin-Williams seems to have so many advantages over RSA (smaller keys, smaller signatures, faster verification, ...) why isn't it in widespread use and everyone still uses "old" RSA?

This seems a bit odd as the latest optimizations are dated as of 2003 (!) which is ten years ago and I think there's also the proof that square-root is equally hard as factoring and I think RW even reduces to FACTORING.

At first I want to cite Lindell and Katz book:

  A "plain Rabin" encryption scheme, constructed in a manner analogous to plain RSA encryption, is vulnerable to a chosen-ciphertext attack that enables an adversary to learn the entire private key. Although plain RSA is not CCA-secure either, known chosen-ciphertext attacks on plain RSA are less damaging since they recover the message but not the private key. Perhaps the existence of such an attack on "plain Rabin" influenced cryptographers, early on, to reject the use of Rabin encryption entirely.

For RSA and Rabin systems encryption/decryption and signing/verification are similar, so I guess the Rabin digital signature system was rejected due to the same reasons as in the encryption case. But if you look at the IEEE or ANSI standards, you'll find that both RW and RSA systems are standardized. I also think, the RSA scheme became more popular as Rivest, Shamir and Adelman set up the "RSA Data Security" company, so they had more opportunities to implement their system in their security solutions and bring these solutions to customers.

Anyway, the reasons are more "historical" than "technical" and now it's easy to securely implement both signature systems. Nowadays cryptographers have been paying their attention to elliptic curves as the systems based on them usually provide the same or higher level of security, but are more effective in a number of applications. So it's unlikely that Rabin's system will have a second chance agaist RSA though it will be used in applications where the fast signature verification is the main requirement.