PRFs / hash functions with a parameter amount of 'hot' bits? Does there exist a cryptographically secure hash function (or keyed PRF) that can take, as a parameter, the number of 'hot bits' in the output? And if so, what is the name? The goal here is to produce a cryptographically-secure pseudorandom bitmask with a fixed number of bits in the mask.
E.g. $\text{some_magic_hash}(x; 12)$ should produce a bitstring with exactly 12 positive bits.

I will answer the question for PRFs, I don't know whether it's possible to securely hash into the respective set.
So, what is it we are actually trying to achieve here? We want to create a family of pseudorandom functions with the co-domain of all bit-strings of a certain length $\ell$ of Hamming weight $w$. I.e., the set
$$Y_{\ell,w}=\bigl\{y\in \{0,1\} \mid \mathsf{hw}(x) = w\bigr\}.$$
I will actually answer a more general question.
Theorem.
Let $Y$ be a set and let $\mathcal{S}$ be an efficient (i.e. PPT) algorithm that samples uniformly from $Y$. We denote by $y := \mathcal{S}(r)$ the output of $\mathcal{S}$ when sampling with random coins $r$. There exists a family of pseudorandom functions with co-domain $Y$, if a regular family of pseudorandom functions (i.e. with co-domain $\{0,1\}^n$ exists.
Proof. Let $p$ be a polynomial that bounds the runtime of $\mathcal{S}$.
Let $F : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^{p(n)}$ be a family of PRFs.¹
We construct a family of PRFs $G \{0,1\}^n \times \{0,1\}^n \to Y$ as $G(x) := \mathcal{S}(F(x))$.
We can show that $G$ is a PRF using a trivial reduction to the security of $F$. Let $A$ be an arbitrary PPT distinguisher for $G$. We construct a distinguisher $B$ for $F$ as follows.
Upon input the security parameter $1^n$ and given access to an oracle, $B$ invokes $A(1^n)$. Whenever $A$ queries its oracle with input $x$, $B$ forwards $x$ to its own oracle, receiving $y$ as a response and returns $\mathcal{S}(y)$ to $A$.
Eventually $A$ will outputs bit $b$, which $B$ will also output.
If $B$ has access to an oracle implementing a truly random function $f$, then its responses to $A$ are by definition of $\mathcal{S}$ uniformly distributed and thus, $B$ is perfectly simulating a random function $g : \{0,1\}^n \to Y$ in this case. If, on the other hand, $B$ has access to an oracle implementing $F(k,\cdot)$, then it's perfectly simulating $G(k,\cdot)$.
Thus, $B$ distinguishes $F$ from a random function with the same advantage as $A$ distinguishes $G$ from a random function. Since $F$ is a PRF, the advantage of $A$ must thus be negligible and $G$ is therefore also a PRF. $\tag*{$\square$}$
What remains to show, is that $Y_{\ell,w}$ can be uniformly sampled in strict polynomial time. Sadly, this is not the case.² The straightforward way of sampling uniformly from $Y_{\ell,w}$, is to sample $w$ unique indices $i_1,\dots,i_w \in \{0,\dots,\ell-1\}$ and returning the bitstring representing $$\sum_{j=1}^w 2^{i_j}$$ in big-endian.
The issue with this strategy is that it involves successively sampling uniform integers between $0$ and $\ell-j$ for $j = 1,\dots,w+1$. That's however not possible in strict polynomial time using binary random coins, unless $\ell-j$ is a power of $2$. We can however do two things:

We can sample uniformly in expected polynomial time using rejection sampling. However, this means our reduction above now no longer runs in strict polynomial time, so we would need to deal with that, which gets ugly very quickly.
We can sample arbitrarily close to uniform in strict polynomial time. This works by sampling an integer $I$ between $0$ and $2^a \gg \ell$ and setting $i=I \bmod \ell$. In this case, even in the uniform case, $\mathsf{S}$ does not sample uniformly. However, it samples statistically arbitrarily close to uniform, which allows the above proof to still go through.

¹ Note that PRFs with co-domain $\{0,1\}^n$ and $\{0,1\}^{p(n)}$ are existentially equivalent for any polynomial $p$.
² I have no proof for this right now, but I would be very surpised if there exists some strategy to do this.


Feedback requested on a method of posting a message without revealing the author So I was thinking about variations on the Dining Cryptographers problem - In some cases, it's useful to be able to post a message without revealing the source, but with the additional constraint of not revealing the entire group to one another.

For instance -
Let's say you have 20 members in a ring.
Each single member knows the person to their left, and the person to their right, but none of them know the entire layout of the party.

An individual in this group wants to share a message, without revealing to the rest of the group that they are the original author.

Suppose each member were to generate a random string of the same length.
This string must be GREATER than the size of the message to be shared.

Starting with one arbitrary member, each member would then talk to their neighbor in turn.
Member1 would share his secret with Member2. [1]
Member2 would then XOR the secrets together, and tell this XORed result to Member3.
Member3 would then XOR his secret against this shared-message, and then pass it to Member4, and so on.

Each Member would XOR their own secret against the shared-message before passing it along.

At some point during this arrangement, the ring would pass to the member who intends to post.
This member would then XOR the shared-message against both his secret, as well as the Message to post.
He would then pass the shared-message as normal.

After the message made it all the way around, Member20 would pass it back to Member1.
Member1 would then XOR by his key again, effectively removing it.
He'd then pass the message to Member2, would would remove his key, then pass Member3, etc.

By the time it returned to Member20, and he removed his key from the set, only the secret message would remain.

There's a simple demonstration in Python

import random

# Create our initial string, and encode it to a series of bits.
# Pad the bits to be at exactly 1K.
initial = "This is the song that never ends - It just goes on and on my friends."
bytestr = initial.encode('utf-8')
intstr = int.from_bytes(bytestr,byteorder='big')
needed_bits = 1024 - intstr.bit_length()
padded_bitstr = intstr << needed_bits

working_str = 0
secret_machine = random.randrange(0,20)

# Create 20 virtual nodes, and give them each a random number.
nodes = []
for i in range(0,20):
    rnd = random.SystemRandom().getrandbits(1024)
    node = {}
    node['randombits'] = rnd
    working_str = working_str ^ rnd
    if i == secret_machine:
        working_str = working_str ^ padded_bitstr
    nodes.append(node)

# Optionally shuffle.
random.shuffle(nodes)

for node in nodes:
    working_str = working_str ^ node['randombits']

# Convert back to string
unpadded_str = working_str >> needed_bits
reformed = unpadded_str.to_bytes(int(unpadded_str.bit_length()/8)+1,byteorder='big').decode('utf-8')

print(reformed)
print(reformed == initial)

[1] - To avoid Member2 checking to see if Member1 was the poster, Member1 should use 2 secret keys, but only share 1.
Essentially treating himself as 2 virtual members. But that's

So a fundamental property of  multi-party anonymous systems is you are only anonymous out of the number of honest participants in the system. If the Stasi control everyone else at the dinner table and know they didn't send the message, then they know you did no matter what protocol you use.

In your case with this ring topology, because only your two adjacent neighbors  in the group know about you and therefore you only interact with them, they only need to be malicious. Specifically, if the member's before and after you collude by cutting you out of the real network and putting you in one that just involves the two of them, then they will know you sent the message when you complete the protocol and remove your key.


Is it possible to recover an AES encrypted file that was decrypted with incorrect key/password? I am new to cryptography and have been experimenting with AES to encrypt files. I was testing some code I found online which allows the user to enter the directory of the files that they went to encrypt/decrypt, the program then asks for the user to input the “password” or “key” to be used for the encryption/decryption.

My problem is that I accidently inputted the wrong password/key when I was trying to decrypt the file, and as I hadn’t added a way for the program to detect incorrect passwords it tried to decrypt the file and so I was left with a file that was still in an encrypted/corrupted state.

I am wondering if it is possible to recover the original encrypted file. I now know the correct password that I should have first used to decrypt the file as well as the incorrect password that was used.

I have found another page where a user had a similar problem here Repair AES-128 decrypted file however this user did not specify that they knew the “correct” password that would have worked for the decryption, whereas I do.

The encryption function used in the script used a random IV as well as AES mode CBC.

Any help appreciated thanks

Note: This is answer version 2. I hastily answered the question incorrectly before.

It's not possible without brute forcing the IV. While encryption is reversible, encryption is generally one-to-many operation and decryption a many-to-one operation. This is because using the same key pair IV accross multiple messages can compromise security. For example if you send the same message twice then a one-to-one deterministic algorithm would leak the fact that you said the same thing twice. The part of the IV in any encryption algorithm that cannot be reused is called a "nonce" for number-used-only-once.

One way to generate distinct nonce values is to start with zero and increment by one every time you encrypt. If at some point you forget the counter you have to rekey. You could recover data in this case.

A random nonce is a memoryless way to prevent reuse. It needs to have enough entropy to prevent the same random value being generated twice. (Large enough to prevent birthday collisions.) This means a random IV is too long to brute force if you lose it.

However if you knew the IV and key, you could reverse CBC encryption. If it's deleted and unpredictable you cannot. CBC mode is deterministic and invertible for a given/known key/IV pair. It has the property $E_{K,IV}^{-1}(E_{K,IV}(M))$ = M (normal operation). Where $E$ is encryption and $E^{-1}$ is decryption. Additionally $E_{K,IV}(E_{K,IV}^{-1}(M)) = M$. It's not something you would normally do, but you could do it to recover the ciphertext file.

I assume you encrypted plaintext, deleted the original file, then wrote the ciphertext to disk. Then in the decryption process you encrypted with the wrong key, deleted the ciphertext (that included your IV), then wrote the wrong plaintext to disk. That process would mean you lost the IV because the random IV is only stored in the ciphertext file.

When you use encryption you should also use message authentication. You check if the MAC tag attached to a message is correct before trying to use decrypted data. Using authentication would have prevented your mistake.


Given generator $g$ with prime order $k$ in $\bmod P$. Does increasing $P = 2 \cdot c \cdot k +1$ decrease security? Increasing $g$ increase security? An adversary wants to find $a$ in

$$m \equiv  g^a \bmod P$$

He knows prime $P = 2 \cdot c \cdot k +1$ with it's primes $c,k$, value $m$ and $g$. And he also knows that $g$ only has an order of $k$, so:
$$g^k \equiv 1  \bmod P$$

Question:
If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$ only factor $c$ gets increased) does this decrease the security?

Why this? If $P \rightarrow \infty $ it would be the normal logarithm which is easy to compute compared to discrete version.

The smaller the better (for same $k$)? Any boundary for best security?

Discrete Log is hard because it is always reduced to a number from $0$ to $P-1$.
 Is security bound to the number of multiplications of generator $g$ needed until over $P$ again? The less the better?

Question part 2:
Would be a higher value for $g$ increase security? (best would be $(P-1)/2$?)
Or to be more certain would a higher smallest group element $\not=1$ increase security?

If now the prime value $P$ gets increased for constant $k$ (order of $g$ still $k$) does this decrease the security?

No, for random choice of $g$ among $g$ with large constant order $k$.

  Why this? If $P \rightarrow \infty$ it would be the normal logarithm ..

When $P$ grows, $g$ also grows. So we never reach the threshold where $g^a<P$. Thus we can not use the normal logarithm.

  The smaller the better (for same $k$)?

Uh, no, on the contrary! The above says that larger $P$ does not decrease security. Correspondingly, larger $P$ tends to increase security. However, very large $P$ does not much increase security, because the best known algorithms we have for the discrete logarithm for fixed $k$ and large $P$ perform a number of modular multiplications modulo $P$ that is a function¹ of $k$ only, and the time necessary for a multiplication modulo $P$ grows relatively slowly with $P$: in the order of $O(\log^2 P)$ for the simplest and common methods².

  Any boundary for best security?

Only a lower boundary, and that's a nontrivial subject. The short answer might be: at least $2^{4095}$ (that is $P$ of $2^{12}$ bits) with $P$ not chosen close to the power of an integer.

The long answer includes that security against classical computers (not hypothetical quantum computers usable for cryptanalysis per e.g. Shor's algorithm) is believed to be limited by several possible attacks:

the Number Field Sieve, which efficiency is governed mostly by $P$, and which general form the General Number Field Sieve (the only form likely to be applicable to $P$ not chosen close to the power of an integer, a situation where the Special Number Field Sieve shines) is believed to require a $P$ in the order of at least $2^{11}$ to $2^{13}$ bits for security.
Pollard's rho, which efficiency is governed mostly by $k$, requiring a $k$ in the order of at least $2^8$ to $2^9$ bits for security.
Pohlig–Hellman (and possibly other algorithms) depending on the factorization of $k$, that do not work as well as Pollard's rho when $k$ is prime.

  Would be a higher value for $g$ increase security?

Not much. The influence of $g$ on security is usually neglected for the aforementioned three algorithm. I doubt it can exceed $\mathcal O(\log g)$ (which can be approached in Baby-step/Giant-step). Also, I know no way to select a very small $g$ with order $k$ and $\log_2(k)\ll\log_2(P)$, much less for prime $k$, which is desirable for various reasons including blocking Pohlig–Hellman.

  Or to be more certain would a higher smallest group element $\ne 1$ increase security?

Not that we know. Also I know no way to insure that for large parameters.

What we are discussing is a Schnorr group. There are well established methods to generate these, including from a public seed so as to tame suspicion of weak parameters. See FIPS 186-4, appendix A (which uses $p,q$ where the question and answer use $P,k$).

¹ That function is at most about $\alpha k^2$ for a constant $\alpha$ in the order of $2$ depending on a variety of details. But that's immaterial to the reasoning in the paragraph with this note.

² The cost can get down to $O(\log^{1.585\ldots}P)$ with Karatsuba which sometime is used; $O(\log P\;\log\log P\;\log\log\log P)$ with Schönhage-Strassen which could be of interest for insanely large $P$, and $O(\log P\;\log\log P)$ with Harvey-Hoeven (a bleeding edge result which seems unlikely to have practical application).


How can one securely generate an asymmetric key pair from a short passphrase? Background info:
I am planning on making a filehost with which one can encrypt and upload files. To protect the data against any form of hacking, I'd like not to know the encryption key ($K$) used for a file, so the user will have to asymmetrically encrypt $K$ and send it as well. The reason for this double encryption is that you can still share (individual!) files with other accounts by encrypting $K$ with the public keys of those users, too.

My problem is: How can a user can get a public and private key without the server saving/knowing the private key and without the user having to remember a passphrase of 250 hex characters?

Question:
Is there a way to derive a key pair from a password, like PBKDF-2 does for symmetric encryption?
Suggestions on rearranging the cryptographic steps in an easier way are welcome, too.

Alternatively:
It is also possible to encrypt the private key with a PBKDF-applied password and store it on the server, but I'd like to keep things 'simple'. ;)

Note: At this point I don't care if it requires RSA, ECC or an obscure cryptography scheme.

The best you can hope for is the following:

You derive the password into a "big enough" (e.g. 128 bits) secret key $K$ with a Key Derivation Function like PBKDF2. There are some details to be aware of (see below).
You use the secret key $K$ as seed for a Pseudorandom Number Generator. The PRNG is deterministic (same seed implies same output sequence) and produces random bits.
You use the PRNG in the key pair generation algorithm for whatever asymmetric algorithm you want to use. This step is cheap and simple for discrete-logarithm based algorithms like DSA, ElGamal, Diffie-Hellman, and their elliptic-curve variants, provided that the group parameters are known in advance (e.g. it is hardcoded in all relevant pieces of software that you are doing ECDSA / ECDH with the standard P-256 elliptic curve defined by NIST). For RSA, this is less cheap and simple, because the key generation process entails generating random integers until primes are reached. This is still doable.

Since this procedure is deterministic (for a given source password), you can run it again every time you need the private key.

Now the trouble with passwords is that they are from the relatively small and non-uniform space of "things which fit in the mind of an average user". They are vulnerable to exhaustive search, which, for passwords, is traditionally named dictionary attack. There are three generic ways to cope with that problem:

Do not let the attacker learn any piece of data which allows him to verify a password guess. In the usual context of storing password hashes in a server for user authentication, this means that you do not want attackers to be able to read the database; this is why Unix-like systems have switched to shadow passwords about 15 years ago. You still want to store hashed passwords, and use the two other protections, because illicit read-only access does happen in the real world.
Use a configurably slow key derivation function. This makes dictionary attacks proportionally slower -- but also normal usage slower, by the same factor. This is why KDF such as PBKDF2 or bcrypt include an iteration count. You want to raise that count up to the highest value which is still tolerable for your users.
Use a salt to prevent attack parallelism. Parallelism is about attacking N passwords (not necessarily simultaneously) for less than N times the cost of attacking one (precomputed tables are a kind of parallelism). The salt is a public piece of data which acts as a variation to the KDF; this is equivalent to saying that there are many distinct KDF, and the salt says which one you use.

In your scenario, you do not have the first protection: the resulting public key is, by nature, public, and thus can serve for offline dictionary attacks. The attacker just has to try possible passwords until he finds the same public key. That's intrinsic to what you want to achieve.

The third protection (the salt) could also prove difficult. The salt needs not be secret, but it still must have some level of integrity. Wherever the salt is stored, the user who wants to recompute his private key must be reasonably assured that he is using the right salt (otherwise he will compute the wrong private key). Depending on the usage scenario, it may or may not be easy to have such a storage space. A partial solution is to use the user name as salt (presumably, the user will be able to remember his own name); as salts go, user names are less than ideal, because:

two users on two distinct server installations (using the same software) may have the same name;
when a user changes his password, he does not change his name;

and this breaks the "unicity" property that the salt tries to achieve. Still, the user name as salt is much better than no salt at all (better yet, use the user's email address as salt: users remember their own address, and email addresses are, by nature, unique worldwide). If you do not use any salt at all, then two distinct users on the same system, who happen to choose the same password, will end up with the same key pair, and simply listing the public keys will show it immediately.

Note: deriving the private key from the password means that when the user changes his password, he also changes his private key. Chances are that this is a problem. This is one of the reasons why you could prefer an indirect system, where a totally normal key pair is stored somewhere, symmetrically encrypted with a password-derived key. Thus, when the password is changed, you just decrypt the key with the old password, and encrypt again with the new password. But this requires an available storage area. This model is directly supported by, e.g., GnuPG.


Show that if a fixed key MAC is not collision resistant then the MAC function is not computation resistant for every key K I'm really having some trouble with this one.

Let $H$ be a MAC function. For every key $K$ we can create an unkeyed hash function (i.e.an MDC) by using $H$ to hash messages with the fixed key $K$. We denote this unkeyed hash
function by $H_K.$ (Note that every key $K$ gives a different hash function $H_K$. Therefore, we can
create a large family of MDC functions from a single MAC function, one for each key).

Show that if $H_K$ is not collision resistant, then $H$ is not computation resistant for every key $K$.

Make your argument as clear as possible.

By my read of the question, I don't see why this is even correct. It does depend on how one interprets that "H is not computation resistant for every key K". I assume that this just means that $H$ is not computation resistant for a randomly chosen key $K$. Otherwise, I'm not sure what it would mean.

According to this understanding, I don't see why the statement is true. From here on, I will use the term "a secure MAC" rather than "computation resistant", since this is more standard terminology.

Now, the straightforward way you would try to prove this is to find a collision in $H_K$ and use this to break the MAC. However, the fact that $H_K$ is not collision resistant for a fixed $K$ means that when you are given the function description, you can find a collision. However, this doesn't mean that you can also do it when you are not given the function description. To be very concrete, define $H_K$ as follows. Parse $K$ into a key for a PRF and into the description of a group where the discrete log is assumed to be hard, along with a generator $g$ and random value $a$ and value $h=g^a$. The function works by first hashing the message using $hash(x_1\|x_2)=g^{x_1}\cdot h^{x_2}$ (using Merkle-Damgård based on this compression function, you get a full-blown hash function) and then applying the PRF. Now, if you know the value $a$, then it's easy to find collisions. Thus, $H_K$ is not collision resistant for any fixed key, since in the fixed-key setting you know $K$. However, in the standard MAC setting where you don't know $K$ and so don't know $a$, this will be a secure MAC (under the assumption that the discrete log problem is hard in this group).

So, I must be misreading the question somewhere. Either there is something in the quantifiers with the "for every key $K$" that I am misreading, or the intention of what a fixed-keyed hash function is is different to what I understand. Or there's an error in the question...

In any case, I wrote this out in detail since I think it has value.


Possible to know who is the owner of a message encrypted with RSA public key Given the scenario in which I want to send 10 messages either to Stalio or Olio. I encrypt these messages with their respective public keys using textbook RSA, before sending the messages to their recipients.

Can an attacker - by knowing only the public keys of Stalio and Olio and the 10 cipher texts - tell which of those messages is addressed to who?

Yes, an attacker may be able to distinguish which message is send to which recipient, but it depends on the message.

Imagine the following setting: the moduli of the keys of Stalio and Olio differ (this is a requirement for RSA). The public key is set to a well known constant, say the fourth number of Fermat, 65537. Textbook RSA encryption of the number 1 will result in 1. Not very secure - you can immediately see that the encrypted number must be 1. As the ciphertext is identical regardless of the modulus, you cannot distinguish between one recipient or the other.

Now imagine encrypting a number in such a way that it wraps around for one modulus, but not for the other. In that case you can clearly distinguish that it was encrypted using the smaller or the larger modulus. As the modulus identifies the key and therefore the recipient, you can see for which recipient the message was encrypted.

Textbook RSA is not safe for general use, you need to use a padding scheme such as PKCS#1 OAEP to be secure. Moral of the story: use cryptographically secure padding for RSA (I guess we can add this one to the list, although traffic analysis is already in).


Are there any signature algorithms with pseudorandom signatures? As the title says.  My reference point for the "pseudorandom ciphertext" concept is this paper by Möller, which introduces a public-key encryption algorithm with this property.  I want to know the analogue for cryptographic signatures; forgive me if this is discoverable somehow via Google, since it is quite hard to get the search engine to understand that "pseudorandom signature" doesn't refer to the random value used in many signature algorithms.

A valid signature $\sigma$ satisfies the very special property that $\textsf{Ver}(vk,m,\sigma)=1$, whereas a random value $\tilde \sigma$ will surely not satisfy this property. So a signature simply cannot be indistinguishable from random if $vk$ and $m$ are known. And if you consider $vk$ or $m$ to be secret, then you are leaving the standard realm of signatures. The paper mentioned above by Maeher does exactly this.


Certificate signature with SHA-1 and RSA: where do 1888 bits come from? Plenty of X.509 Certificates use "PKCS#1 SHA1 with RSA encryption" as the Certificate Signature Algorithm for generating a 2048-bit signature. The SHA-1 hash function generates a hash value of 160 bits, but where do the other 1888 bits from the 2048-bit output come from?

Are they another a hash value or are they just padding?

Can someone briefly answer this question. If you also can provide me a source or a website to read more about it since I've been trying to find an answer of this one but I haven't gotten a good resource to explain this issue.

I think you don't quite understand how RSA signatures work (and why they are the size they are).

When generating an RSA signature, we follow a two-step process:

We take that hash of the message we're signing, and convert (and pad) it into an integer $M$ which is between 0 and $N$ (where $N$ is a large integer that specified by the RSA key)
We use the RSA private key, and convert $M$ into a signature $S$, which is also an integer betwen 0 and $N$

The resulting integer value $S$ is the signature.

From this description, it should be obvious that $S$ is essentially the same size as $N$.  So, how big is $N$?

Well, for the RSA keys that you use, it is 2048 bits long (which, in the context of RSA, means that it is an integer between $2^{2047}$ and $2^{2048}-1$).

Hence, the RSA signatures you see are 2048 bits long, not because someone decided to pad out the hash an extra 1888 bits, but instead when they generated the RSA key, they decided to make that key 2048 bits long.  They didn't add 1888 bits to the hash because they thought 1888 was a nice number; instead, they extended the hash to 2048 bits because whoever generated the RSA key thought 2048 was a nice number.

Now, you might ask: why did they pick a key of that size?  Well, more than anything else, because that's a round number.  You can generate RSA keys of just about any size (however, too small keys can be broken, and too large keys just waste time), and practically speaking, there's little difference between an RSA key of 2048 bits and one of 2000 bits.  However, 2048 bits is what everyone expects nowadays, and so that's what everyone uses.

You asked for a reference about how the RSA padding process works; the one that immediately comes to mind is PKCS #1, which explains exactly how to generate RSA signatures (using several different padding methods).


How many degrees of freedom up my sleeve? Now that we know how the MD2 S-box was constructed, I find myself wondering how good a nothing up my sleeve number it really is. It is derived from $\pi$, but not in a very obvious way, even in retrospect.

How would you estimate the number of possible $\pi$-derived S-boxes that are no more complex or suspicious than the actual one is?

For example, "unique bytes of pi starting from the 96723th digit in base 256" is (arguably) simpler, but more suspicious. On the other hand, a longer description/algorithm would count as more complex.

Or more generally: how would you appraise how binding a nothing up my sleeve number is?

Actually, given that the MD2 S-box needs to be a permutation, using a Fisher–Yates shuffle does seem a fairly obvious choice to me.  (It's pretty much the standard algorithm for generating a uniformly chosen random permutation.)  The rand() function used to convert the digits of $\pi$ into a random number from a given interval looks complicated, but is also a fairly standard method.  (IIRC, it's essentially the same as what's described in Fisher and Yates' original book from 1938.)

That said, you asked about the number of degrees of freedom available, so let me try to count the various plausible choices one might've made in generating the permutation:

The first obvious choice is the base in which $\pi$ is expressed.  The Rivest code uses base 10 digits, but since we're using a computer, at least the bases 2, 16 and 256 would've made sense (and using base-256 would've even allowed the rand() function to be simplified).  That's four choices, or two bits of freedom.
Also, using only the fractional part of $\pi$ (i.e. skipping the first digit) would've probably been a plausible choice.  That's one bit of freedom.  One might've even been able to justify the use of $\tau = 2\pi$, or its fractional part, for another bit of freedom.
Obviously, there are plenty of other "obvious" irrational constants besides $\pi$ that could've been chosen.  This excellent paper by D.J. Bernstein et al., mentioned by Seth in the comments above, lists 17 such constants: $\pi$, $e$, $\gamma$, $\sqrt2$, $\sqrt3$, $\sqrt5$, $\sqrt7$, $\log(2)$, $\varphi = (1+\sqrt5)/2$, $\zeta(3)$, $\zeta(5)$, $\sin(1)$, $\sin(2)$, $\cos(1)$, $\cos(2)$, $\tan(1)$ and $\tan(2)$.  (Adding $\tau$ makes it 18.)  Each of those has a reciprocal, and either the original constant or the reciprocal has a non-zero integer part that can be dropped, multiplying the number of possible constants by three, for a total of $18 \times 3 = 54$ possible choices, or $\log_2 54 \approx 5.8$ bits of freedom (including the two bits from the previous bullet point).
The Fisher–Yates shuffle has an "inside-out" version, which produces a different permutation for the same input.  Also, either of the variants could be started from either the top or the bottom end of the array, yielding different results.  That's two more bits of freedom.
The rejection sampling used in rand() could've been avoided by expressing $\pi$ in a mixed-radix system (with the base increasing or decreasing by one for each digit).  Such a choice (which essentially amounts to a form of arithmetic decoding) could've been justified by the fact that it minimizes the amount of input "randomness" required to generate the needed pseudorandom digits.  As there are at least two reasonably natural ways to do this (increasing or decreasing radix), we can increase the possible bases from four to six, giving us an extra 0.6 bits of freedom.

Putting all of these choices together, we have $4 \times 54 \times 6 = 1296$ reasonably plausible combinations to choose from, giving us at least $\log_2 1296 \approx 10.3$ bits of freedom.

Of course, if that's not enough, there are various other methods we could try, such as "accidentally" implementing Sattolo's algorithm or one of the many other subtly biased (but still pretty convincingly random) variants of the Durstenfeld–Knuth–Fisher–Yates shuffle.

We might even be able to appeal to tradition and use Fisher and Yates' original algorithm instead of the Durstenfeld variant, perhaps combined with simple rejection sampling for the first half (as originally suggested by Fisher and Yates), or perhaps the algorithm by C.R. Rao described in later editions of their book.  Or we could even just go with pure rejection sampling (i.e. take the base-256 digits of $\pi$ and discard duplicates), or maybe some variant of the sort-by-pseudorandom-key method of generating permutations (which should allow plenty of freedom in how to generate the keys).


Is it safer to encrypt twice with RSA? I wonder if it's safer to encrypt a plain text with RSA twice than it is to encrypt it just once. It should make a big difference if you assume that the two private keys are different, and that the only way used to crack it is brute force. I submitted these theories to my teacher, but he claims that a double encryption doesn't make it any safer. I didn't follow his arguments entirely, so I decided to ask here.

So, if I encrypt a message with one key once, and the encrypt the resulting cipher text once more with a different key, does this make the encryption simpler?

EDIT:
My teacher said that "it doesn't get safer with a double encryption, at least not if n is the same and e is different.". This is the part I don't follow, since you'd still need both p and q to derive the two different private keys that this would produce. I have made a few calculations and I do not quite understand. Why would the particular statement my teacher sent me mean that it doesn't get safer?

Well, think about it this way. If breaking one encryption with brute force will take longer than the lifetime of the universe, are you any safer with an encryption scheme that will take twice the lifetime of the universe? No. The first encryption cannot be broken. Adding a second encryption just adds computation overhead with no real benefit.

Think about it this way, if it is estimated to take 500 years for a prisoner to chew through the bars on his prison cell to escape, is the public any safer if we add a second set of bars so that it will take 1000 years to chew through the two sets before the prisoner can escape? Not really.

UPDATE
Given the update in the question, I thought I'd update.

So, you fix an $n$ and choose $e_1$ and $e_2$ as public exponents and compute $d_1$ and $d_2$ as the private exponents.

To encrypt, you are proposing $(m^{e_1})^{e_2}\bmod{n}$ and wondering why this is not stronger than just $m^{e_1}\bmod{n}$ in a brute-force attack[*].

So, you haven't given detail as to what the "brute-force" attack is, so let's look at two options.

Factoring $n$. If I factor $n$ using a brute-force attack, I then use the factorization to compute $d_1$ and $d_2$. Computing both $d_1$ and $d_2$ is not much more than just computing $d_1$ since you broke the factorization.
Instead of factoring $n$, what if you try to brute force $d_1$ and $d_2$. Recall that $d_i$ is chosen such that $e_i d_i\equiv 1\bmod{\varphi(n)}$. Furthermore, $(m^{e_1})^{e_2}=m^{e_1e_2}$. Raise that to $d_1d_2$ and you get $m$ back. Therefore, you really need to bruteforce $d_1d_2$ instead of $d_1$ and then $d_2$ (or vice-versa). If you assume each of the $d$s are $l$ bits, brute forcing $d_1$ then $d_2$ would be like brute forcing $l^2$ bits. Brute forcing $d_1d_2$ on the other hand is $2l$ bits. One could argue that this is harder, but asymptotically it isn't.
Brute force only $d_1$ then factor. It turns out if you know $d_1$ you can easily factor $n$ then use the factorization to compute $d_2$. (This comes from @CodesInChaos comment).

Any other brute force options you had in mind?

[*] My description of double encrypted RSA here is assuming textbook RSA. For padded RSA (which is what you find in the real world), points 1 and 3 are still valid, 2 however is not.


Using ChaCha20 on very short messages with high packet loss I'm building a low power wireless network and need to transmit very small packets at regular intervals (10 bytes every minute or so). In order to secure the communications I'm considering using Chacha20 and a pre-shared key.

The problem I have is communicating the IV. I could just broadcast it at the start of each message, but that results in almost doubling the message length and therefor the power usage during transmission.

I considered agreeing upon a method of calculating the IV (i.e. using the transmitter address as a nonce and a simple transmitted packet counter) but this gets risky if messages are dropped for any reason.

Before I go down the path of defining an ad hoc method of solving this issue I thought I'd ask and see if anyone has solved it previously and what recommendations you all had.

My fall back method is to use the address to generate a nonce, then use a packet counter and transmit only the lowest order byte. This adds only a single byte to the message length and allows me to theoretically miss 255 messages and still 'resync' packet counters. Not as robust as I'd like but better than anything else I've come up with myself.

If I remember correctly, ChaCha doesn't need an unpredictable IV, so a simple counter will do. (Combined with sender id if you have multiple senders using the same key.) If you had a totally lossless link, you wouldn't need to send the counter value at all.

But as some packets can be lost, you need to send at least part of the counter. The least significant 8 bits should do fine against random packet loss, just make sure to increment the next bits when overflowing the sent part, so you don't end up repeating the same 256 IV values. Even if each packet had an independent 90 % chance of being lost, the odds of losing 250 packets in a row would be less than $10^{-11}$.

Non-independent packet loss would be another thing, but with one message per minute, you'd need to lose four hours worth of packets in a row to lose synchronisation. Might happen if there's a power-out at the receiver during the night but the transmitter keeps sending.

Speaking of power-outs, your transmitters would need to have some persistent storage for the counter so that it doesn't reset in case the device loses power. A real-time clock as a counter would also do, as @otus commented.

Also note that you don't seem to have any authentication for the messages, so you're only protected against passive attackers.


Unable to understand the concept of a 1-bit PRF In his lecture on building Block Ciphers from PRGS, Dan Boneh says this

Let’s start by finding out if we can build PRF from a PRG?
Let $G:\ K \to K^2$ be a secure PRG
Define 1-bit PRF $F:\ K \times \{0,1\} \to K$ as $F(k, x\in\{0,1\}) = G(k)[x]$
$\quad F$: if $0$ choose $G(k)[0]$, if $1$, choose $G(k)[1]$

I am unable to understand what is a 1-bit PRF. A PRG takes only the seed as input. So what is the $\{0,1\}$ in $F:\ K \times \{0,1\} \to K$ - considering that $K$ is the key/seed of the PRG.
And what does $G(k)[x]$ in $F(k, x\in\{0,1\}) = G(k)[x]$ mean?

what is a 1-bit PRF?

That would usually be a PRF with a 1-bit output, but the rest of the text clarifies it is meant a 1-bit input.

what is the $\{0,1\}$ in $F:\ K \times \{0,1\} \to K$ ?

It is the set with two elements $0$ and $1$. This also is the set of the possible values of the second/right/normal/non-key component of the input of the PRF $F$.
Note: a Pseudo Random Function Family (confusingly abbreviated PRF just like a Pseudo Random Function) has two inputs (equivalently: an input consisting of an ordered pair). The first (the left component of the pair) is the key, and the second (the right one) is the normal/non-key input (which is the single input of any particular member of the Pseudo Random Function Family). The member of the Pseudo Random Function Family corresponding to key $k$ is often noted $F_k$. By that notation $F_k(x)=F(k,x)=F((k,x))$. Here, $F_k:\ \{0,1\}\to K$ (that's a particular Pseudo Random Function for a certain key $k$), since $F:\ K \times \{0,1\} \to K$ (that's the whole Pseudo Random Function Family).

what does $G(k)[x]$ in $F(k, x\in\{0,1\}) = G(k)[x]$ mean?

The PRG $G$ takes an input $k$ and produces an output $G(k)$ consisting of two parts of the same width as $k$, as apparent in $G:\ K \to K^2$. This is the same as  $G:\ K \to K\times K$. That is, the output of $G$ is an ordered pair of bitstrings, assimilated to a bitstring twice as wide as $k$, that we split in two parts as wide as $k$, each from the same set $K$ as $k$ is from.
$G(k)[x]$ is the first or the second component/part of the output of $G(k)$, according to $x$ being $0$ or $1$. It's also the output of $F$ for input $(k,x)$ where $k$ is the PRF's key, and $x$ is the PRF's second/right/normal/non-key input, which is a single bit.

What exactly is $x$?

It's a bit. It's not an input of the PRG $G$. It selects among the two halves of the output of the PRG $G$ for input $k$, that is $G(k)$. We can think of $[x]$ as we'd do for [x] in a computer language with indexes.


What are the main weaknesses of a Playfair cipher, if any? What are the main weaknesses of a Playfair cipher, if any?

I know that they depend on none of the letters missing, but that is an easy fix if a letter gets dropped. Besides that, are there any other problems with it?

It's a quite a weak cipher, being better than a simple substitution cipher by only using digraphs instead of monographs.

An interesting weakness is the fact that a digraph in the ciphertext (AB) and it's reverse (BA) will have corresponding plaintexts like UR and RU (and also ciphertext UR and RU will correspond to plaintext AB and BA, i.e. the substitution is self-inverse).
That can easily be exploited with the aid of frequency analysis, if the language of the plaintext is known.

Will chaining Playfair with a substitution cipher help?
Nope... The (monoalphabetic) substitution cipher will act (almost completely) transparent against the frequency attack. Eventually, the Playfair cipher is a digraph substitution cipher itself. (But it will make the resulting cipher not self-inverse anymore.)

Well, polyalphabetic ciphers are a whole different case of course. It's still a play-toy for today's computers, but it'd completely render the text unbreakable in that era. But then again, we needed machines like Enigma to properly and acceptably implement it. The German Enigma, if I'm not mistaken, implemented a polyalphabetic cipher.


How is encryption using XOR represented? I know this is a dumb question and i probably have a fundamental misunderstanding of encryption, but when we want to encrypt, let's say a word like ''Hello'' for example, which is represented at binary level as 01001000 01100101 01101100 01101100 01101111 we XOR it with a key which also has a binary representation. The output of which is the encrypted text.

How is this process actually translated to a something like a shift cipher? Does XOR = addition? What about when we used some other cipher or algorithm to encrypt? Is XOR still used? What mathematical operator does XOR represent?

This answer assumes it was meant stream cipher, not shift cipher (because the later, also known as Caesar's cipher, has nothing to do with XOR; but that assumption turned out wrong).

In a stream cipher, a keystream generator is initialized with a secret key, and a (typically random) Initialization Vector (which will be transmitted to the receiver in clear). From that, the keystream generator deterministically produces the keystream, that is a sequence of random-looking bits as long as the plaintext is, here $5\times8=40$ bits, say
10111100 01110110 00100010 01100000 01101001
This keystream is combined by (bitwise) XOR with the (binary form of the) plaintext
01001000 01100101 01101100 01101100 01101111
yielding the ciphertext
11110100 00010011 01001110 00001100 00000110

For each bit, XOR (often noted $\oplus$ ) can be defined by this truth table
$$\begin{array}{cc|c}
k & p & c=k\oplus p \\
\hline
0&0&0\\
0&1&1\\
1&0&1\\
0&0&0
\end{array}$$
and that's the same table as addition modulo 2. In yet another equivalent definition, the output is 0 when the inputs are equal, 1 when they are different.

Somewhat, the IV and ciphertext reach the receiver (typically thru a public channel e.g. radio). The receiver rebuilds the keystream from the IV and secret key (conveyed secretly and separately), using the same deterministic keystream generator. The keystream is then combined by bitwise XOR with the ciphertext, and that rebuilds the (binary form of the) plaintext, since $p=k\oplus c$.

In computer practice, the plaintext, keystream and ciphertext could be handled as octets (8 bits) or wider chunks, and combined with bitwise XOR over an entire octet/chunk. The C, C++, Java, Go.. languages have an operator ^ doing just that. Beware however that at least keystream and ciphertext octets/chunks can take any value, and that might require special care (for example, C strings are not directly usable for keystream and ciphertext).

The keystream generator and resulting stream cpiher tend to share the same name. Cryptographic literature is ripe with excellent ones, including ChaCha, or a block cipher such as AES enciphering a counter initialized with the IV, yielding AES-CTR.


AES sbox security issue - power analysis attack? I was wondering about whether the usage of a precomputed sbox (kind of a lookup table) could be a serious security issue when using AES.

I am new to power analysis attacks, so it is hard to understand for me why / why not the sbox which is used in AES could be a possibility for attackers to find out the key.

If yes, what would be an alternative? I could compute the sbox values on the flight but would that be an advantage?

Note: I don't care about performance, just about security.

I was wondering about whether the usage of a precomputed sbox (kind of a lookup table) could be a serious security issue when using AES.

Well, that rather depends on the type of side channel attacks you are interested in protected against.

You specifically mention Power Analysis (SPA and DPA) type attacks; the first obvious question would be: could those attacks actually be performed by the type of adversary you are trying to protect?  After all, to perform those attacks, the attacker needs to make extremely precise (and extremely high resolution) measurements of the current drawn by the circuit; is this a realistic scenario?

Sometimes it isn't.  If we're talking about crypto that'll be used in a Web server in a physically secure location, there's no way an attacker could get physical access (and if he could, there are far more damaging attacks an attacker could do).  On the other hand, if we're talking about crypto on a Smart Card (where the power is externally supplied, potentially by the attacker), then power analysis attacks are quite realistic.

And, if we really do need to protect against such invasive attacks, we need to worry about a lot more than just how the sbox is computed.  If you're running on a general CPU, then what an attacker with that level of access might be able to do is directly monitor the memory bus (and just read the keys are they are being read from memory); to prevent that level of attack, we generally need the entire crypto circuit be in a special enclave that the attacker can't break in (for example, epoxy-encapsulated).

And, power analysis attacks can allow the attacker to deduce the settings of various gates; in the standard AES implementation, the first thing you do is xor the plaintext with 128 bits of the key; if the attacker can read those first 128 bits, he gets 128 bits of the key (and with AES-128, that's all of it).  Because of this, when we do a DPA-resistant implementation, we implement a blinded or threshold implementation (where we stir in some randomness at the start of the operation; this randomness doesn't affect the final result, however it does affect how the intermediate values are represented, where each logical bit is spread over several physical bits (so that the setting of any internal bit, or any set of k bits, are uncorrelated to the logical operation being performed).  Now, this doesn't actually stop all DPA attacks; we hope it makes it sufficiently difficult that the attacker won't be able to collect enough data samples (e.g. encryptions based on the same key) to actually deduce anything.

Now, table lookups don't work well in this blinded/threshold scenario, and so (to answer the question you originally asked) we tend to compute things on the fly.


Strong RNG for encryption/authentation algo I saw in the market several hardware options for creating strong RNG to produce strong KEYS:

HSM
TPM internal TRNG
Intel RDSEED (TRNG)/RDRAND

My questions are;

What is the strength/entropy difference between them? (using intel RDSEED is much lower cost than buying an HSM)
Why feeding TRNG seed (like RDSEED) into the PRNG mechanism (RDRAND)? doesn't that lower its strength?
Cant I use RDSEED for creating a key (using KDF) without RDRAND?

RDRAND/RDSEED is the focus of all three of your questions here.  If you're looking for truly random numbers (as indicated by the trng tag),   it's probably worth realising that there is substantial anecdotal and circumstantial evidence that RDRAND/RDSEED isn't a TRNG.  Have a look at my analysis from another question, specifically item 10. That indicates that it's not just me spouting weirdo conspiracy theories.

Since my analysis discourages the cheap Intel approach, you're left with TPMs and HSMs. Clearly a HSM costs waay more than a TPM.  You could argue that a HSM might be more secure/reliable as they tend to be build to international standards like FIPS and commonly accepted in security scenarios.

The entropies should be identical at 8 bits/byte, but I also offer this warning.  How do you know? Computational indistinguishability means that you can't differentiate even a simple construct like $E_k(pepper||time)$ from a truly random sequence. And both hardware are designed tamper resistant, which means that you can't personally audit them. So similarly, look at this TPM criticism.

It's a tough choice as a lot of what applies to my RDRAND/RDSEED thesis also applies to TPMs and HSMs.

As for the remaining two parts:-

Yes, feeding a PRNG from a TRNG seed does lower the mathematical strength of the output. A caveat though is that as long as you create your 128/256 bits of initial Kolmogorov randomness, it should be sufficient for most cryptographic purposes. It just means that the output entropy is no longer truly random. Those 128/256 bits remain a constant no matter the output length. Till you re-seed. This is what occurs inside *nix's \dev\urandom, just using other entropy sources.
RDSEED's raison d'être is key creation and seeding.  If you believe that the output entropy is real, then all you have to do is acquire it.  You get it in batches of 16 - 64 bits via registers. It's a bit dry, but instructions are here.  No KDF is required as it should be truly random at 8 bits/byte and therefore perfectly secure. A KDF is indicated when going from a password to a key.


Are there any known inverse hash lookups for the zero string? Just wondering, are there any known inverse hashes / hash lookups in common hashes (md5, sha1, sha2, etc.) for the zero string hash value? (i.e. bytes 0x00 00 00 00 00 ...)

Or more specifically, for a 128bit hash (like MD5 or SHA1):

HASH(x) = 0x00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

Obviously it would take reverse hash lookup, or a rainbow table...

The 2-pass Snefru hash of the one-block message

79F6A75E 0397C368 F60C88DE 3133A55E 6D00251C 8ED3567B
CA49F82B A32E5DC4 8F86E479 DD3FF4D6 14DD88C1 A2322E00

is all zeros[1].

However, no other major hash function (and it's debatable whether 2-pass Snefru counts as major) with advertised collision and preimage resistance has ever had its preimage resistance broken[2] (archived), not even MD5[3].  If anyone found a preimage of zero under MD5, SHA-1, SHA-2, SHA-3, BLAKE2, etc., it would be quite astonishing.


Why is SRP considered to be resistant to MITM attack? Why is SRP considered to be resistant to MITM attack? Documentation says

  A man-in-the-middle attack, which requires an attacker to fool both
  sides of a legitimate conversation, cannot be carried out by an
  attacker who does not know Carol's password. An attacker who does not
  know x cannot fool Steve into thinking he is talking to Carol, so at
  least one half of the deception fails. If the attacker doesn't know v
  either, he is in worse shape, because he also can't fool Carol into
  believing that she is communicating with Steve.

But let's assume Carol, Steve and MITM have salt, generator and safe prime. And imagine the Carol trying to log in, but MITM stands between Carol and Steve.

1) Carol sends A, but MITM takes it and sends to Steve.

2) Steve responds to MITM with B. MITM sends it back to Carol.

3) Both Carol and Steve create a common key(K).

4) Carol sends Steve h(K,s1), where h is a one way hash function and s1 is some salt that was given to Carol by Steve. MITM takes it and sends it to Steve.

5) Steve checks it and say "Hello Carol, nice to meet you".

So MITM can log to the server by sending requests back and forth.

As has already been commented:

The fact that you can intercept and relay all messages does not actually constitute an attack on the protocol because you do not know the shared key afterwards. If the protocol partners encrypt their traffic with that key you cannot eavesdrop on it.

If this was an attack on the protocol none of the network hardware that is commonly used would be allowed to work because forwarding messages is exactly what it does.

Indeed, that means that participating in the protocol by relaying messages does not suffice for authentication.

Edit: It would be like thinking that all of your letters have been sent by the mail man. ;)


key specifications for x25519 - need two clarifications please Am implementing x25519 (in 64 bit and 512 bit assembly) following the specifications in RFC 7748 (and its errata list !).

Need two clarifications please.

The private key is randomly generated 32 byte string with MSB set to 0 and MSB-1 set to 1, and, last 3 bits set to zero. Now, once a random 256 key has been generated, it is made compliant to these specified requirements, and the corresponding public key has been computed. The clarification being sought is : does the private key remain this 32 byte string after the MSB/MSB-1 is set ? Does this imply that the actual count of universe of random private keys is restricted to 2^251 (256 - MSB - [MSB-1] - 3 LSB - all these bits are fixed) ? If an external user were to specify a key that is not compliant with this requirement, and the software modifies it to become complaint, does the external user specified private key needs to be updated with this post compliant string ?
Most implementers (e.g. Michael Dull (apologies for not being able to type the umlaut in the surname) et. al. in paper "High speed Curve25519...") have mentioned that the last inversion  step (Z^(p-2)) requires 254 squaring steps and 11 multiplications. I understand the 254 squaring steps, but am not sure what algorithm is used to restrict the count of multiplications to such a small number. If this is not a state secret, can I be directed towards the actual algorithm that generates the inversion mod p-2 with (just) 11 multiplications ?

Thanks for your attention and time.

About your first question, yes, the set of private keys is restricted to those $2^{251}$ values that are always a multiple of $8$ and that's security by design:

By making sure the input scalar of the scalar multiplication algorithm is a $255$-bit value will the algorithm specified in the RFC will always perform 254 loops and each of those loops will perform the exact same operations (one addition, one doubling): it's a simple protection against simple side-channel analysis
To prevent against the invalid point attack (Bob giving to Alice a point of low order on another curve), only the $x$-coordinate is used, so the point belongs either to the curve or its quadratic twist. The only points of low order on those curves have order $2$, $4$ or $8$, so if Bob submits one of those, Alice will always get $0$ (representing the infinity point in the X25519 function) as an output of the key-exchange and detect that it is invalid. Invalid point attack and small subgroup attack are prevented.

You might want to read the original papers on it: Curve25519:new Diffie-Hellman speed records and Can we avoid tests for zero in fast elliptic-curve arithmetic?

About your second question, it is just fast exponentiation. Look at the binary decomposition of $p-2 = 2^{255} - 19 - 2$. Or look at some already written code (most of Curve25519 implementation come from the same reference).


Understanding the wide trail design strategy I am trying to understand the wide trail design strategy. I have read the paper (paywall-free preprint) which describes it from the point of view of AES. From what I understand, it is a technique to increase diffusion in a particular way to resist differential and linear cryptanalysis. My background is in information security but not cryptography, so my understanding of some of the more math-heavy descriptions is limited. Can anyone explain the basics of the wide trail design strategy, and why and how it works?

Given the importance of the wide-trail strategy in modern symmetric-key cryptography, this question really deserves an answer (and a much better score). Since nobody else has tried, I'll give a brief summary and some context. Hopefully this will help you understand the paper by Daemen and Rijmen (paywal-free preprint) better.

Since the (public) discovery of differential and linear cryptanalysis, an active research area within symmetric-key cryptography has been dedicated to bounding the probability of differentials and the correlation of linear approximations in practical constructions. The goal of this line of work is to prove (or heuristically argue) the security of a construction against linear and differential cryptanalysis. The most successful approach to this end is the wide-trail strategy.

Differential and Linear Cryptanalysis

This is not the right place to explain differential and linear cryptanalysis (you can find introductions elsewhere), but some notation has to be introduced for the remainder of this post. Recall that differential cryptanalysis studies the propagation of differences $\Delta_0 \to \Delta_r$. Such differentials have an associated probability that I shall denote by $p(\Delta_0, \Delta_r)$. Linear cryptanalysis considers linear approximations which are described by a pair of masks $(u_0, u_r)$. They have an associated correlation $c(u_0, u_r)$, which is twice the bias.

In practice, one does not find differentials but rather differential characteristics, i.e. sequences of input and output differences of parts of the cipher that are easier to understand (typically, the round functon). So a differential characteristic may be defined as a tuple $(\Delta_0, \Delta_1 \ldots, \Delta_r)$. Similarly, one has linear trails in linear cryptanalysis and these are sequences of input and output masks $(u_0, u_1, \ldots, u_r)$.
In some cases, the probability of a differential and the correlation of a linear approximation can be estimated as follows:

$$p(\Delta_0, \Delta_r) \approx \prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i)$$
$$c(u_0, u_r) \approx \prod_{i = 1}^r c(u_{i-1}, u_i),$$

where the choice of intermediate differences/masks is understood to be the optimal one.

I must stress again that these are approximations, and in many cases these are not valid. For example, it is clear that one often needs to take into account multiple characteristics or trails. In fact, there is an entire branch of research dedicated to refining the above estimates in both the differential and linear settings. I will not go in to these matters as they are (mostly) outside of the scope of your question.

In the remainder of this post, I will focus on heuristic security arguments that are based on showing that all characteristics have small probability, and all trails have a small correlation. I will also not really discuss how small "small" should be (this is based on cost estimates of differential/linear attacks).

Bounds on Characteristics and Trails

From here on, assume we are dealing with an SPN (but the argument will apply to several other constructions too). Suppose the round function consists of a nonlinear S-box layer, a linear layer and a key addition.

Suppose the nonlinear layer consists of $m$ S-boxes which are applied in parallel. The S-boxes have some maximum differential probability $p_{max}$ and a maximum absolute correlation $c_{max}$. By this I mean the maximum over all non-zero input differences and non-zero masks. This is important because a zero input difference always yields a zero output difference and similarly for linear approximations (assume we are dealing with permutations).

So clearly, we have the upper bounds

$$\prod_{i = 1}^r p(\Delta_{i-1}, \Delta_i) \le (p_{max})^{n_D}$$
$$\left|\prod_{i = 1}^r c(u_{i-1}, u_i)\right| \le (c_{max})^{n_L}.$$

Here, the number $n_D$ is equal to the number of S-boxes in the characteristic with non-zero input difference. We call this differentially active S-boxes.
Similarly, $n_L$ is the number of linearly active S-boxes in the trail.

Role of the Nonlinear Layer

A lot of early work focused on the choice of the nonlinear layer. That is, one attempts to minimize the quantities  $p_{max}$ and $c_{max}$. Of course, one still needs to have some sort of bound on $n_D$ and $n_L$, but that is not the main concern in this line of work. For example, this 1995 paper by Nyberg and Knudsen (paywall-free preprint) uses a DES-like structure and then discusses how to choose the nonlinear function to minimize $p_{max}$. Do note that their security argument is stronger than what I describe here, as they consider (in more modern terminology) the EDP (expected differential probability) rather than individual characteristics.

Because efficiency tends to impose limits  on the size of the S-boxes that can be used in a construction, $p_{max}$ and $c_{max}$ cannot be made very small. The natural conclusion is that we need to increase $n_D$ and $n_L$ somehow. This will be the role of the linear layer.

Role of the Linear Layer

Recall that the S-box layer consists of $m$ S-boxes which are applied in parallel. So it makes sense to split the differences and masks into $m$ parts: $\Delta_i = \Delta_i^{(1)} \| \Delta_i^{(2)} \| \cdots \| \Delta_i^{(m)}$ and $u_i = u_i^{(1)} \| u_i^{(2)} \| \cdots \| u_i^{(m)}$. Let us denote the number of nonzero $\Delta^{(j)}$ in $\Delta = \Delta^{(1)} \| \cdots \| \Delta^{(m)}$ by $\mathrm{wt}(\Delta)$ and likewise for $\mathrm{wt}(u)$.

The set of $j$ such that $\Delta^{(j)} \neq 0$ is often called the activity pattern of $\Delta$. One has a similar definition for masks.

The number of active S-boxes $n_D$ and $n_L$ in a characteristic/trail can then be expressed as
$$n_D = \sum_{i = 0}^{r-1} \mathrm{wt}(\Delta_i),$$
$$n_L = \sum_{i = 1}^r \mathrm{wt}(u_i).$$

Remember that one wants to maximize $n_D$ and $n_L$, so the weights $\mathrm{wt}(\Delta_i)$ and $\mathrm{wt}(\Delta_i)$ should be made large.
This can be done using the linear layer, because the linear layer restricts which transitions $\Delta_i \to \Delta_{i + 1}$ and $u_i \to u_{i + 1}$ are possible. That is, if the S-box layer has differential $\Delta_i \to \Delta_i^\ast$ with nonzero probability, then $\Delta_{i + 1} = L(\Delta_i^\ast)$ for a linear layer $L$. Without the DDT of the S-boxes, we don't really know what $\Delta_i^\ast$ is, but we do know that it has the same activity pattern and in particular the same weight. So we can optimize $L$ independently of the S-boxes by maximizing the quantity

$$\mathcal B_D(L) = \min_{\Delta \neq 0} [\mathrm{wt}(\Delta) + \mathrm{wt}(L(\Delta))]$$

This quantity, called the branch number, was introduced by Daemen in  his PhD thesis. Later, $\mathcal B_D$ was called the differential branch number in contrast with the linear branch number defined below.

Similar ideas apply for linear cryptanalysis: the linear layer restricts which mask activity pattern transitions are possible. If $L$ is invertible (let's assume this for simplicity), then $u_{i + 1} = L^{-\top}(u_i)$ where $\top$ denotes the transpose. Hence, the linear branch number for an invertible $L$ is defined as
$$ \mathcal B_L(L) = \mathcal B_D(L^{-\top}) = \mathcal B_D{(L^\top)}.$$
Note that one can also define the linear branch number of a noninvertible map.

So we want to maximize $\mathcal B_D$ and $\mathcal B_L$. In his PhD thesis, Rijmen related the branch number to coding theory. I will not go into details here, but this leads to the use of MDS codes to obtain $L$. The first cipher to use these ideas was probably SHARK by Rijmen et al. In practice, the entire linear layer $L$ is usually not an MDS matrix. Instead, one combines a column-wise MDS linear layer with a cellwise permutation that ensures diffusion between columns.

Wide trail strategy

The wide trail strategy is the design strategy that you get when you combine the ideas above (I have made several simplifications though.) Quoting from the paper:

  The reasoning above suggests two possible mechanisms to eliminate
  low-weight trails:

  Choose S-boxes with high minimum differential and correlation weight.
  Design the round transformation such a way that there are no relevant trails with low bundle weight.

The first part is the role of the S-boxes, the second part relates to the linear layer (in principle one can also consider nonlinear diffusion layers, but this goes out of scope). An important difference between the wide trail strategy and earlier/other approaches (for example Nyberg and Knudsen) is the emphasis on the linear layer:

  Instead  of  spending  most  of  the  resources  on  large  S-boxes,
  the  wide  trail strategy aims at designing the round
  transformation(s) such that there are no  trails  with  a  low  bundle
  weight.  In  ciphers  designed  by  the  wide  trail strategy, a
  relatively large amount of resources is spent in the linear step to
  provide high multiple-round diffusion.

An immediate bound on the probability of characteristics over two rounds of such a cipher is $(p_{max})^{\mathcal B_D}$ and the absolute correlation of 2-round trails is upper bounded by $(c_{max})^{\mathcal B_L}$. Better bounds can usually be obtained for 4 rounds (here the effect of the cellwise permutation becomes relevant). I will not go into the details.

The wide-trail strategy led to the block ciphers SHARK, Square and ultimately Rijndael (which became the AES). After the AES competition, many other ciphers where designed based on (or at least inspired by) the wide-trail approach.

Beyond Wide Trails

Despite the length of this post, I have only described the very basics.

New techniques (e.g. based on SAT and MILP solvers) have been developed to compute the number of active S-boxes. Research has not ended, but it's really not feasible to try and give an overview of developments here.

Bounding characteristics and trails is not enough, because it only leads to heuristic security arguments. One can for instance try to compute the MEDP (maximum expected differential probability) and MELP (maximum expected linear potential) for a block cipher. Such calculations typically rely on the assumption that round keys are independent.
There are examples of designs that were broken (using linear/differential attacks) despite good heuristic arguments for their security against these attacks.


Can ECDSA signature signing and verification process replaces password hashed based login system? ECDSA or DSA in general was to sign a message or data using private key and verify it using public key, if the attacker/imposter doesn't have the private key then they couldn't sign the message properly.
If ECDSA private key was kept private, can the signature verification of ECDSA be used for user to login into a system ? Rather than a password hashed based login approach ?

Yes, this is secure provided the message to be signed is unique on each login to prevent replay attacks.  Usually that's done with either a random challenge or the signature over a shared secret.
In fact, SSH does this already with ECDSA keys: the two sides agree on a shared secret, which is hashed, and the client signs the hashed secret and some other data to verify that it's allowed to log in.  MariaDB also does a similar thing by deriving an Ed25519 key (which isn't exactly ECDSA, but is similar) and using that to sign a random challenge (although it doesn't necessarily derive this key in a secure way).
Similarly, most FIDO2 and WebAuthn two-factor authentication devices, such as YubiKeys, use this approach.  You could also use TLS client certs that are ECDSA, which is another approach used in some environments.
This could be used for any type of login, including websites, but it is less common there because people don't expect to carry a key around with them everywhere and frequently log into websites from different computers, so it's practically inconvenient.  But ignoring the practical problems, this is secure if implemented correctly.


finding second pseudo preimage faster than brute force As far as I know finding second preimage of a hash function is almost as hard as finding preimage. But I want to know that is there any way to finding second pseudo preimage faster than brute force? I mean ,for example, in MD5 for a given $h$ (hash) we have  $MD5(IV_1 , P_1) = h $.is there any way to find $(IV_2 , P_2)$ such that $$  MD5(IV_2 , P_2) = MD5(IV_1 , P_1) = h$$ in time complexity less than $2^{128}$?
Also if the answer of question is YES please tell me that if I change the $IV$ , is it possible to modify $P$ to get same hash  in time complexity less than $2^{128}$?

For MD5, it is only known for the first (pseudo) preimage it is given by Yu Sasaki and Kazumaro Aoki in 2009

Finding Preimages in Full MD5 Faster than Exhaustive Search

In this paper, we present the first cryptographic preimage attack on the full MD5 hash function. This attack, with a complexity of $2^{116.9}$, generates a pseudo-preimage of MD5 and, with a complexity of $2^{123.4}$, generates a preimage of MD5.

In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$, In the second preimage attack we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.
If we can execute a pre-image attack, then we may carry it into a secondary pre-image attack. First, execute a pre-image attack, if we find $y \neq x$ than we are done. If not, continue the search. If brute-forcing, just continue, if a special attack, change the parameters and/or continue to find another.
A similar idea can work for the pseudo secondary preimage attack, too. I've not seen an example on MD5. Usually, the first pseudo preimage attack is extended to secondary pre-image attack. Like done on Gost hash function
A (Second) Preimage Attack on the GOST Hash Function
Note: pseudo-preimage is also called free-start target attack.


Format of NONCE in Initialization Vector (IV) When we talk about a Number used ONCE (NONCE) in Initialization Vector (IV), is it required to use numbers only? Is is possible to use letters or special characters?

No. In the context of the Initialization Vector of a cipher operated in some mode, the most significant property of a cryptographic nonce is that it is not reused. It often matters that it is random and unpredictable (e.g. with CBC). It is immaterial that it represents a number or anything else under some particular encoding.

If an IV is chosen at random, it would be bad to restrict it to represent a number (say, restricting each byte to be a digit according to ASCII), in particular because it would dramatically increases the odds of reusing the same IV.


Use of the IV for the CBC Block Cipher in TLS1.2 I'm struggling to understand at what point a message is encrypted when looking at RFC 5246. The spec gives the generic block cipher in section 6.2.3.2 as:

struct {
    opaque IV[SecurityParameters.record_iv_length];
    block-ciphered struct {
        opaque content[TLSCompressed.length];
        opaque MAC[SecurityParameters.mac_length];
        uint8 padding[GenericBlockCipher.padding_length];
        uint8 padding_length;
    };
} GenericBlockCipher;

So my question is, does the IV get encrypted or not, and does the IV affect the padding?

No the IV doesn't get encrypted. The IV is a random vector to make sure that the ciphertext is not identical for identical plaintext. This would leak information to any eavesdropper. It needs to be unique - and in the case of CBC, indistinguishable from random to the eavesdropper ("unpredictable") - but not confidential.

As the IV is separate from the ciphertext, it does not affect the padding. However, the RFC has this information:

  The padding length MUST be such that the total size of the
        GenericBlockCipher structure is a multiple of the cipher's block
        length.

The IV is included in this structure. This is still correct as the IV is specified as being exactly the same size as the block size (for CBC):

  the IV length is of length
        SecurityParameters.record_iv_length, which is equal to the
        SecurityParameters.block_size.


Post processing of AAD and len A||C in a hardware AES GCM implementation I'm new to GCM and I need to implement it in hardware, using FPGA.
The data bus is 640 bits, so I will use 5 adder/multiplier blocks in parallel.
The message size and AAD size are constant.
My design have a particularity that AAD and Len A||C are available only at the end of message and I don't kow how to process it.

A little example:
message = 5 x 640 bits.

cycle 1: process 640 bits (add/multiply)
cycle 2: process 640 bits (add/multiply)
cycle 3: process 640 bits (add/multiply)
cycle 4: process 640 bits (add/multiply)
cycle 5: process 640 bits (add/multiply) and xor all results
cycle 6: process AAD
cycle 7: process Len A||C

After cycle 5 I have a 128 bits vector with all the messages added/multiplied and results xored.
So, how can I process AAD and Len A||C in this scenario?

Thanks
Rodolfo

BouncyCastle (for Java) has code that performs the AAD processing anywhere in the stream. It does however require modular exponentiation and additional multiplication. GCM mode officially requires the AAD to be processed before the plaintext, but as stated, there is a way around that. I've asked for an explanation here

Len A||C is only required at the end of the processing anyway, so that should not pose a problem.


Update to "Cryptographic Right Answers" I'm a big fan of Colin Percival's "Cryptographic Right Answers" post.

This was written in 2009, which is a long time ago in Internet years.

Is the advice still valid or, if not, can someone point me to more up-to-date information?

For the clearly cryptographic recommendations:

AES CTR + MAC: still good advice, though AES-GCM is a good alternative. His recommendation of 256-bit keys clashes with Schneier's (also 2009) recommendation of 128-bit due to the weaker 256-bit key schedule. Neither choice is broken, however.
HMAC-SHA-256 as MAC: still good advice. While SHA-3 has been published, it has not yet seen as much use and SHA-2 remains unbroken.
256-bit random UIDs: 256-bits is not going to risk collisions, like ever.
PBKDF2 or scrypt: still fine. Although PHC chose Argon2 as a possible successor, it does not have much uptake yet.
RSAES-OAEP: I am torn here. It is a secure choice for public key encryption, but like he says it is easy to get wrong. A good elliptic curve would be as secure, faster, and ECC keys are much smaller. Not bad advice.
RSASSA-PSS: unlike the above, this is fairly simple. However, signature size is also large compared to ECC. Secure, but not always the Right Answer, as he says.
Diffie-Hellman on group #14. Still good advice.

So none of it is bad advice even after seven years.


Given this protocol, can you find some weakness? 1) A->B  A||B||{Na}Kab
2) B->A  {Na+1,Nb}Kab
3) A->B  {Nb+1}Kab
4) B->A  {K'ab,N'b}Kab

This protocol is used to refresh a symmetric session key.

EDIT:

A and B are the IDs of users A and B.
Na, Nb, N'b are nonces (pseudorandom values).
Kab is the old session key.
K'ab is the new session key.
|| means concatenation.

An attacker is only able to do man-in-the-middle.
Every message is encrypted with Kab

One weakness with this protocol is that the compromise of a past symmetric key, which can often be assumed over some sufficiently large period of time, compromises all keys and messages sent after the time that key was first used.

edit:

If any $K_{ab}$ is compromised, a man in the middle attacker can resend message 4 corresponding to the compromised $K_{ab}$ and it will be accepted by $A$. The attacker can then impersonate $B$ communicating using the compromised key.


How can I find the original message of two encrypted (Vernam Cipher) text without the key Can I get the steps or the solution if possible?

You know that the two ciphertext you are given are formed as
$$C_1 = S_1 \oplus R\\C_2 = S_2 \oplus R$$ with the same $R$ in both cases.
So you can get rid of $R$ by calculating $$C^\ast = C_1 \oplus C_2 = S_1 \oplus S_2$$
Then you know that there are only two words, $111$ and $0000$. Thus, in $C^\ast$ $1$ can only occur if one sentence contains $A$ while the other contains $B$.
From there, since the two words have different lengths, you should be able to determine candidate sentences.


When do I need to renew keys for Salsa20 or HMAC? I currently have a system which uses two keys sourced from a single key subjected to HKDF. One key is used in the Salsa20 stream cipher and the other is used for a SHA-2 based HMAC.

Given that the stream cipher (Salsa20) is being used for a persistent stream lasting a long time (perhaps hours) with frequent data exchange, is key renewal required (where the key used for the cipher is renegotiated)?

Furthermore, is there a defined period of time in which this key renewal should take place? I read this question here and found that stream ciphers like RC4 and Salsa20 have a period, but is there any security vulnerability in letting their internal counters rollover?

The same questions apply for the SHA-2 HMAC: should the key for the HMAC be replaced after some period of time? Or is the act of replacing the key itself a security vulnerability.

I can provide code if that would be helpful.

Salsa20 has essentially no limits on its own for data volume: it can be used for up to $2^{64}$ messages of up to $2^{70}$ bytes apiece.  You could use it in a nonstandard way for, say, more messages if they're each smaller, by carving up the input to the PRF differently, as long as the total volume of data is below $2^{134}$ bytes.  You certainly can't exhaust this volume or even this many messages in a few hours.  There's no reason to complicate a protocol with key rotation just to limit the number of bytes or messages encrypted under a Salsa20 key.

But you may want to deliberately erase a conversation.  For that to be effective, you must be able to erase the key that can decrypt a transcript of the ciphertext over the network.  How often you do that depends on your protocol: for example, with modern messengers, key erasure happens after every message, while with TLS, it typically happens after a TLS session completes (though there have been a raft of historical mistakes in the design and implementation of TLS session resumption failing to erase keys).


Which data to share in CTR mode? Suppose I've got two clients $A$ and $B$. Client $A$ encrypts data in CTR (Counter) mode to get a ciphertext. What information will client $B$ have to receive from $A$ to decrypt the ciphertext? Just the “key”, “IV” (nonce), and “counter start value”?

As you specified in the question, the key, nonce, and initial counter value are what is required in addition to the ciphertext and algorithm used.

However, it is best practice to have the initial counter always be 0. Common standards place no specific restrictions on the size of the nonce unless it is used in an authenticated encryption mode, but it is generally 96-bits, leaving 32-bits for the counter. A 32-bit counter allows 64 GiB of data to be encrypted per nonce using a 128-bit block cipher. A 32-bit 0-start counter is also more simple for software implementations. If you expect to send more than 64 GiB in a single message, you will need to reevaluate the counter size.

If you plan on having both the clients encrypt data with the same key, care must be taken so that there is no nonce overlap. 2 ways of doing this are prenegotiating a client to only use even or odd nonces, or having one of the clients use only nonces with the high bit set to 1.


Questions about William's p+1 First off, if you're doing William's p+1 test, then also doing Pollard's p-1 is redundant, since the p+1 test covers both cases, right?

Second, why is the recurrence $V_{n+1} = aV_n - V_{n-1}$ used? Using $V_{n+1} = V_n + bV_{n-1}$ instead would give you a provable $\frac{1}{2}$ chance of getting a quadratic nonresidue for each choice of $b$. But no reference I've ever seen uses this variation.

Note: this is only an attempt at answering the first part of the question, asking if William's p+1 factorization method is redundant with Pollard's p-1, on the basis of how the algorithms are used in practice.

Pollard's p-1 (resp. William's p+1) factorization method is efficient to find a factor of $n$ if any of the factors $p$ of $n$ is such that $p-1$ (resp. $p+1$) has no prime factor above some moderate bound $B$. An improvement puts a bound $B_2$ for the highest prime factor of $p-1$ (resp. $p+1$), and another bound $B_1\ll B_2$ for the other factors.

The original paper on Williams's p+1 also presents Pollard's p-1.

Pollard's p-1 factorization is used in some recent factorization efforts with bounds up to $B_1≈2^{40}$ and $B_2≈2^{50}$; if unsuccessful, that's sometime followed by William's p+1 with slightly lower bounds, before gearing-in ECM.

If we construct a 1024-bit integer $n=p⋅q$, with $p+1=p_0⋅c_0$, $q+1=q_0⋅c_1$, $p−1=p_1⋅p_2⋅p_3⋅⋅⋅p_{11}⋅p_{12}⋅c_2$; $p$, $q$, $p_j$, $q_0$ primes; $p$ 415-bit, $q$ 610-bit, $p_0$ and $q_0$ at least 200-bit, other $p_j$ 32-bit; then it is likely amenable to Pollard's p-1 factorization (because $p-1$ has no factor wider than 32-bit), but I see no reason why I can't tell if it would be amenable to William's p+1 factorization (because both $p+1$ and $q+1$ have a high prime factor).

One such integer (also in this pastebin) is $n =$ 170008213545910965886460576572090982063408798024984543559001546422534644045470603998698706971810963093964580198788881904271608774213396896678573575267676754780622889919559692654436815810637860509009977667589657189496387034548011094365919416175990986348895410113935005204972304311894659720336969894022598750477

Another similarly constructed integer of 448 bits, factorisable with Pollard's p-1 setup with $B_1=4000$, $B_2=10000$, is $n =$
726286104974888320831459714524497735770165786243885681724247623636059281197969465033496277725004244158329276076523947799294094896411843


Difference between Identity-based encryption and multiple key-pairs of public key encryption? What is the difference between Identity-based encryption and multiple key-pairs of public key encryption scheme??

Suppose trusted key generator generates a bunch of public and private key pairs $(k_{\texttt{public}}^{(1)}, k_{\texttt{private}}^{(1)}), (k_{\texttt{public}}^{(2)}, k_{\texttt{private}}^{(2)}),...,(k_{\texttt{public}}^{(m)}, k_{\texttt{private}}^{(m)})$
, each of pairs is distributed to each of $m$-parties and all the public keys are public (any one can know it).

In this case, what's the potential difference of ID-based encryption and this instantiation?
Both of them can do the same task where everyone can encrypts its data using one of the public keys such that only the corresponding private key owner can get the data.

What is the difference between Identity-based encryption and multiple key-pairs of public key encryption scheme?

It's all about the public key.  You state, with your public-key based system:

  … and all the public keys are public (any one can know it).

But if Alice wants to send Bob a message, how does she learn his public key?  After all, any such public key is a long random looking bitstring.  Now, there are possible ways:

The trusted key generator could just send everyone's public key to everyone else (as you stated), but that really has serious scalability problems
Alice could look it up in a public directory of everyone's public keys (but that still has scalability problems, but less bad ones than the previous idea)
Bob could put his public key in a certificate, and so when Alice wants to send Bob an encrypted message, she asks him for his certificate first (but that requires Bob to be able to interact with Alice when she wants to send the encrypted message).

In contrast, with IBE, the public key could be anything; Bob's public key could be, for example, "bob@example.com"; and so if Alice knows Bob's email address (which she may need to send the message anyways, she then knows his public key).


Generating a key to use with AES I'm going paperless, and I want to encrypt the documents that I scan. I'd like to use CommonCrypto to perform AES-XTS encryption on each file. I'm a software engineer, and I like the idea of being able to write my own wrapper around the library. However, I am not a crypto expert by any means. If I understand IVs and salting correctly, is it possible to use one long passphrase to generate a unique encryption key for each file? Also, is this general approach a good idea, or should I go in a different direction?

Yes, the principle to use a common password and a unique salt per file with a key derivation function is a good and acceptable practice, as you generate the salt randomly and with the right size. The uniqueness of the salt guarantees a different password per file (actually one password per salt, so: do not reuse a salt, use a csprng).

You forgot to mention (or to design) how you're are going to protect the cipher integrity. XTS mode does not provide this property, you should add a message authentication code (MAC) as HMAC.

It would be probably better and simpler to switch to another mode which provides confidentiality and integrity as GCM or OCB. The second reason for switching from XTS that is that mode is designed to be used in Full Disk Encryption context and encrypt disk sectors and not a whole file. some other reasons.

Don't forget to store the salt with the ciphertext and protect its integrity, too.