Estimating bits of entropy I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy.

What I'm having a hard time finding is any particular literature which describes how to go from those tests to actual bits of entropy in the byte stream.

How do you go from p value of a byte stream (say a 100 MB long) to bits of entropy?

Updated:

As mentioned below, you can't estimate entropy of the output (not possible), but only by understanding the physics of the underlying process that generates the entropy.

Entropy is a function of the distribution. That is, the process used to generate a byte stream is what has entropy, not the byte stream itself. If I give you the bits 1011, that could have anywhere from 0 to 4 bits of entropy; you have no way of knowing that value.

Here is the definition of Shannon entropy. Let $X$ be a random variable that takes on the values $x_1,x_2,x_3,\dots,x_n$. Then the Shannon entropy is defined as

$$H(X) = -\sum_{i=1}^{n} \operatorname{Pr}[x_i] \cdot \log_2\left(\operatorname{Pr}[x_i]\right)$$

where $\operatorname{Pr}[\cdot]$ represents probability. Note that the definition is a function of a random variable (i.e., a distribution), not a particular value!

So what is the entropy in a single flip of a coin? Let $F$ be a random variable representing such. There are two events, heads and tails, each with probability $0.5$. So, the Shannon entropy of $F$ is:

$$H(F) = -(0.5\cdot\log_2 0.5 + 0.5\cdot\log_2 0.5) = -(-0.5 + -0.5) = 1.$$

Thus, $F$ has exactly one bit of entropy, what we expected.

So, to find how much entropy is present in a byte stream, you need to know how the byte stream is generated and the entropy of any inputs (in the case of PRNGs). Recall that a deterministic algorithm cannot add entropy to an input, only take it away, so the entropy of all inputs to a deterministic algorithm is the maximum entropy possible in the output.

If you're using a hardware RNG, then you need to know the probabilities associated with the data it gives you, else you cannot formally find the Shannon entropy (though you could give it a lower bound if you know the probabilities of some, but not all, events).

But note that in any case, you are dependent on the knowledge of the distribution associated with the byte stream. You can do statistical tests, like you mention, to verify that the output "looks random" (from a certain perspective). But you'll never be able to say any more than "it looks pretty uniformly distributed to me!". You'll never be able to look at a bitstream without knowing the distribution and say "there are X bits of entropy here."

I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy.

Those statistical tests are intended to verify that a RNG is producing independent and uniformly distributed random numbers.  That's all.  Whilst some suite tests may produce an entropy estimate, that is not their primary purpose. (Eg. First line of the basic ent test.)  They are for producing a estimate of likelihood (p value) that the test sequence is of good quality. You can only tell that the sequence is bad if there's a run of p = 0.00000 (SP 800-22) or a heap of FAILs (Dieharder).

There is NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation.  It seemingly attempts to measure entropy but has massive issues if the data sample is not uniformly distributed.  So inapplicable to natural data. And it also has severe programming errors resulting in estimates like 21 bits /byte.

  What I'm having a hard time finding is any particular literature which describes how to go from those tests to actual bits of entropy in the byte stream.

I'm not aware of any either. The lack of discourse suggests that this is not an active field.  The closest I've seen is the discussion
 Estimated entropy per bit given P-value of a statistical test, and number of bits tested? on this site.  I think that the accepted answer is unproven for the reasons in my answer.

Revisiting this idea, I'm now fairly convinced that it's impossible.  One can't compare the  asymptotic nature of Chi, Gauss and t-distributions that produce the p values, to the 0 - 100% linear degrees of entropy within a sequence. And some tests such as car parking in Diehard(er) are not even defined algebraically, but rather by past computer simulation. The tests behave chaotically at the edges.

  As mentioned below, you can't estimate entropy of the output (not possible), but only by understanding the physics of the underlying process that generates the entropy.

This is false.  It's not just possible, it's done all the time.   The very nature of all statistical science based on population sampling, ergodic data sources, NIST's 800-90B and most other branches of science unequivocally prove that you can.  You simply need a sufficiently large output sample for one's intended test suite as p(randomness) ~ f(sample size).

As for understanding the physics, non trivial RNGs are 50/50.  You can produce a reasonable entropy model of a photon interference based TRNG. You have very little chance accurately modelling a simple Zener diode, other than to say it's kinda log normal with  correlation. Or the balls in the National Lottery's tumbling machine cylinder thingie.

To date, I've only found the "top 1" best ways of practically estimating natural entropy.  Compression.  I now use cmix, one of the strongest compressors in the world.  Just compress the file, divide by two for safety and hey presto, your entropy estimate.  Not perfect, but I'm unaware of any other direct technique that works on all natural sample distributions.


Length of encryption password aes-256-cbc I'm encrypting a file with sensitive information with

cat secret | openssl aes-256-cbc -a -salt > secret.enc

I am choosing a random encryption password with openssl rand -base64 32 | head -c [password-length]

Is there any standard, how long it should be? Given the password length, how long would it take to crack and view the contents of the file?

I have read this article, but it seems it supposes that you use a password size of 256 bits.

Edit: I found this picture, which pretty much answers my question. Is it reliable?

https://www.inetsolution.com/blog/june-2012/complex-passwords-harder-to-crack,-but-it-may-not

AES supports three key lengths. They are 128, 192 and 256 bits long. You chose to use the 256 bit algorithm that operates in CBC mode. It's a correct choice.

Now all you need is:

key - 256 bits long
initialization vector - 128 bits long

You can generate them using the command I found here:

openssl enc -aes-256-cbc -k secret -P -md sha1

where the "secret" is your password.

I suggest not using a truly random key and IV, because you have to save them somewhere, and adversary can just read it from your hard drive. It's much better to use a long and complicated password that he has to read from a post-it-note glued to your monitor, and derive the key and IV from it.

As for security, let me put it this way. If I wanted to crack 256 bits long key and 128 bit long IV on my work laptop, I would probably be around a fifth of way done when the universe would collapse. It's much simpler to use rubber-hose cryptanalysis in this case.

EDIT:

Just for you to know you shouldn't use password as a key directly. You need to derive a key from a password. The command I pasted does exactly that. About the security of the password you already answered yourself. 9 characters is the absolute minimum (if there is at least one uppercase letter, one lowercase letter, one number and one symbol). But I strongly suggest using a passphrase instead of a password. They are vulnerable to dictionary hacking, but if you use enough words a dictionary hack also takes years to complete.

There are over a milion words in the English language.

If we use only lowercase letters in our four word passphrase, the dictionary hack has to do in the worst case $1000000^{4} = 10^{24}$ searches. In comparison, there are around 100 characters on the keyboard. A password of 12 of those characters will be cracked in less than $100^{12} = 10^{24}$ searches.

This mean that "singing retracted eleventh elephant" is an equivalent of a 12 character password, and also it's much easier to remember. And if we use a comma somewhere, uppercase letter, or use a word from a different language it gets much safer.

A collection of passwords and passphrases with a total of 100 characters results in a search space of 5.98 x 10^197.  By comparison, there are roughly 10^80 atoms in the known universe.

If you want to super-secure your encrypted files, encrypt them first with Blowfish 448, then again with AES-256, both times using a different random password combined with a different long passphrase.

By encrypting it first with Blowfish, you're also randomizing the data, which makes even correctly decrypted AES-256 files appear as if they're still encrypted. Thus, no program or human can tell if a password guess was decrypted or not.

In this sense, you don't need a super-strong password for the Blowfish layer.  A simple passphrase like "There ain't always nothing about Makia ain't what I swimmmingly done know." provides more than enough "security" for this randomizing layer.  That's a keyspace of 6.06 x 10^142 in and of itself.  Combined, you're looking at a level of complication on the order of 10^340.

In summary:

Encrypt with Blowfish 448 using a relatively simple passphrase mixed with a random password.
Encrypt with AES-256 using a different relatively simple passphrase mixed with a different random password.

Ensure that neither passphrases nor passwords will ever appear in any dictionary or body of literary work.


Is it safe to use XOR to encrypt data key using master key I am implementing a hierarchical key system with a randomly generated master key and many randomly generated data keys that should be encrypted using the master key. I am wondering what the best way to encrypt the data keys using the master key is. I am thinking that if I XOR the master key with the data key, that should be simple and safe. Is it? I couldn't find any documentation on this.

XORing a master key (presumably a long term key) with data is a very dangerous idea. If any data key is leaked, then the master key may be easily calculated, thus leaking all keys. ($m$ for the master key, $d_x$ for all data keys)
$$c_x = d_x \oplus m$$
then somehow $d_4$ is leaked
$$m = d_4 \oplus c_4$$
$$d_x = c_x \oplus m$$
You'd be better off applying a block cipher (like AES) instead. One of the main properties of block ciphers is that given the plaintext and ciphertext, it is infeasible to generate the key.
$$c_x = E_m(d_x)$$
then again $d_4$ is leaked (who keeps doing that..) yet $m$ is still hidden.

If done right, XOR can be used to encrypt data. One way to do this, is to generate a pseudo-random key-stream using your master key and XOR the key-stream, which needs to be as long as the data, with the data.

The key-stream can be generated using a block-cipher like AES.

This is how AES-CTR (Counter) Mode works.


Can I encrypt data with multiple keys and decrypt with one? Can I encrypt data with multiple keys and decrypt with one? To be clear, I am not saying encrypt a file, decrypt it, then encrypt it again with a different key. I want to encrypt it, then encrypt it again, then again, maybe even again. I want to know whether I can use only one key to decrypt. The key can change though, it doesn't have to be the same key (in fact it shouldn't be).

I need a smart way to update the key to the new key, depending on how many times the data was encrypted. Also, the only way to get the new key is to have the old key... Is this possible? Is there an encryption algorithm that can be stacked multiple times and be decrypted by one key (and can I create that key)? Either this can already be done, or I am crazy--remember, I'm new to this...

Previously handled comments on StackOverflow:

  "What's the point of encrypting multiple times? Properly encrypted data is indistinguishable from random noise."

I'm not trying to make it more secure by doing this...

  "Do you want to perform E(k_n, msg) once with one of many possible keys then E(k_d,ciphertext) to get the ciphertext? Or do you want to perform E(k_1, E(k2, ... E(k_n,msg) ... ) ) as the encryption?

The latter, except I don't want to do encrypt with all keys all at once. I want E(k_1, msg) ... some time ... E(k_2, encrypted_msg) ... and so on, but I want to know if I can decrypt with one key after however many encryptions (and how to get that key).

  "Consider: 'I really want a smart way to update the key to the new key'."

Yes. And, of course, the encrypted file will change during the process.

Here is a candidate system, based on an ordinary message cipher $\mathcal E_\kappa(p)$ and $\mathcal D_\kappa(c)$ so that $\mathcal D_\kappa(\mathcal E_\kappa(p)) = p$ and $\mathcal E_\kappa(p)$ is indistinguishable from uniform random noise to anyone who doesn't know $\kappa$.

Let $k_i$ be the $i^\mathit{th}$ encryption key, let ${E^i}_{k_i}(x)$ be the $i^\mathit{th}$ encryption function, let $k$ be the decryption key, and let $D_k(x)$ be the decryption function.  We want to define $E^i$ and $D$ so that $$D_k({E^{n-1}}_{k_{n-1}}(\cdots({E^1}_{k_1}({E^0}_{k_0}(x)))\cdots) = x,$$ but otherwise we want all the intermediate ciphertexts, ${E^i}_{k_i}(\cdots({E^0}_{k_0}(x))\cdots)$, to be indistinguishable from uniform random noise to an adversary who does not know $k$ or the $k_i$.

To this end, define

\begin{align*}
  {E^0}_{k_0}(x) &= \mathcal E_{k_0}(x), \\
  {E^i}_{k_i}(x) &= x, &&\text{for $i > 0$.}
\end{align*}

Decryption is easy: the decryption key is simply $k_0$, and $D_k(x) = \mathcal D_k(x)$.

If this doesn't satisfy your needs, you will need to be more specific about what your needs are so that they meaningfully exclude this system.  ‘Meaningfully exclude’ implies that you have to give some reason related to your application why this won't work, rather than just say you don't like it and the $E^i$ functions have to actually do something.

In particular, it will be helpful for you to identify who changes the key and why.  Are you the sender and recipient, and are you changing your password because it got compromised and surgically removing all traces of the previous key derived from it and ciphertexts encrypted with it from all storage systems everywhere?  Are there multiple parties involved, like members of an organization who have split administrative functions to avoid unilateral power to doctor records?  What are you or they all trying to accomplish?  What is the adversary you hypothesize able to do to manipulate the resources they are trying to accomplish it with?  What do you want to make sure the adversary can't do?

You could do this with one-time pads. Simply XOR the new pad into both the ciphertext and the decryption key each time.


Making a cipher non-malleable using a plaintext transform? NOTE: By malleable/non-malleable, I mean the ability/or not to change a byte/block of the ciphertext and have it change only that byte/block of the plaintext.
I understand that we use authentication (via HMAC/UMAC/etc.) to verify integrity. However, where authentication is not possible (perhaps in a case where one has a very limited environment on storage/CPU power), can we transform the plaintext before encryption?
Using several "rounds" of a move-to-front transform that reverses the plaintext after each iteration does exactly that. Once the plaintext is over 1kb (or so), you only need a few rounds. This creates a sort of avalanche effect' so that tampering in any place affects a large amount of the plaintext.
My MTF transform uses an index of possible bytes (0-255). Each "round" consists of an MTF transform, resetting the index, reversal of the plaintext, and another MTF transform.
Running some tests suggests that with two rounds of my MTF for random 256-byte inputs, flipping any bit will, on average, change over 50% of decoded bits. For a 512-byte input, the average is 53%. For a (barely tested) 1024-byte input, the average (and lowest) number of bits changed is over 50% for any flipped bit.
The outliers (minimum number of bits changed) are linear for small enough inputs. For a 512-byte (or less) input, the lowest number of bits changed is always achieved by flipping the first bit (further right) of the first input byte. Additionally flipping any bits at the end of a small input always results in a greater than 50% change, but not at the beginning. These undesirable effects seem to disappear with a 1024-byte input, although testing this takes me too long (about 2 minutes per input!) to make any useful statement.
The main problem with this approach is that it takes too long. I am using a small notebook with Intel Atom CPU Z3735 @ 1.33GHz. One KB takes around 0.034 seconds to encode. To encrypt a KB using ChaCha takes around half this time.
NOTE: The transform function is completely known (per Kerckhoff's principle). It is completely dependent on the plaintext. The function does absolutely nothing except add non-malleability to the plaintext and thus ciphertext. It works before ANY cipher, and not with.
UPDATE: I've updated the transform function, altering the indexes used for the transform rounds, reducing the rounds to 2, and adding a running sum of data input to the process. It is now quicker than ChaCha and achieves non-malleability at 512 bytes of input, without any bias (within limits of my testing). It adds a nonce on encoding that it removes on decoding. The code is here if anyone wants to have a look.
I'm aware I could make the code faster, but I still think there must be some standard approaches to the overall problem. The only modern, similar thing I've found relates to an all-or-nothing transform, which Rivest discusses here. It seems strange that the idea (assuming Rivest is correct about added security) didn't really catch on.
My questions:

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?
Does anyone know a potentially quicker way to transform plaintext (completely independent of the cipher) and make it (potentially) non-malleable?

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?

There is one existing idea which is currently used in some RSA implementations that could be tweaked slightly to fit the requirements of Russian copulation.  I will briefly describe below, and then mention a potential additional benefit of such a 'transform'.
OAEP
Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption.
The algorithm takes the form of a Feistel network which uses a pair of random oracles $G$ and $H$ to process the plaintext prior to asymmetric encryption. When combined with any secure trapdoor one-way permutation $f$, this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack

As using OAEP as an all-or-nothing transform would require processing in blocks (with padding) and potentially some extra tweaking to design it for the purposes of non-malleability.

Finally, it is not necessarily be the case that using such a transform function would only provide the benefit of non-malleability.  As per the Ron Rivest's paper All-or-nothing encryption and the package transform

We present a new mode of encryption for block ciphers, which we call all-or-nothing encryption. This mode has the interesting defining property that one must decrypt the entire ciphertext before one can determine even one message block. This means that brute-force searches against all-or-nothing encryption are slowed down by a factor equal to the number of blocks in the ciphertext. We give a specific way of implementing all-or-nothing encryption using a “package transform≓ as a pre-processing step to an ordinary encryption mode. A package transform followed by ordinary codebook encryption also has the interesting property that it is very efficiently implemented in parallel. All-or-nothing encryption can also provide protection against chosen-plaintext and related-message attacks.

Below I will give an example of how we can use OAEP as inspiration.  It can obviously be improved upon (and I could probably use a variant of ChaCha QR).  My code is here and may well be easier to read than my explanation below.
This CAN be done in a single-pass, and it is significantly quicker than my previous function which looked up/sliced/rearranged arrays, and processed byte-by-byte.
First, I took an unbalanced Feistel cipher and set it up (with 10 double rounds). It is made up of 8 blocks of 32 bits.
The blocks are XORed with fixed circular rotations of other blocks, and shift position after each double round.  In each double round, most blocks are affected in some way by most other blocks.  For example, block0 (in one double-round) is affected by Blocks 1,2,4,5 & 7.  Odd blocks are affected by one less, eg. Block 1 is affected by Blocks 2,3,4 & 5.
After 10 double rounds, this achieves good (over 50%) diffusion in output blocks 0,3,5 & 6.  In the other "bad" blocks it is around 56%.
We will process input data in 128 bit chunks, using the "good" blocks of the Feistel and the "bad" blocks of the Feistel will be the state/capacity which is initialised with random data and saved with the final encoding.  Thus allowing us to decode (backwards), and the initial randomness providing a nonce.
Finally, we add a 128 bit "counter" into the Feistel.  This keeps a XOR of all the data blocks processed (and begins on 0).  This doesn't need to be saved, but does require slightly more computation for decoding as we need to "count" all the blocks before we begin the decoding process.
As we decode in reverse, it is obvious that the last data block affects any of the previous data blocks (due to the saved state).  And as the "count" of previous data blocks affects the last data block, we have all bits affecting all bits.
It would require padding the input, but it's incredibly quick. 1KB is processed in <0.003 seconds on my rubbish machine.  It's actually too quick for my rubbish testing and often registers 0 at lower amounts.
The problem I can see is that it generates differing diffusion levels depending on the size of input.  If the input is 128 bits, the average number of bits changed for any bit flipped is around 75%.  For 1024 it is around 57%.  For 3072 it is around 53%. For 4096 it is still around 52.5%. At 1KB it is around 52%
I have not found a single bit that could be flipped that didn't cause over 50% of bits to change for any input size.

Maybe im not getting something. The avalanche effect, known state, no added cryptographic security, 50% bits flipped if one bit is flipped, simpler and faster than ChaCha20... It seems you are describing a pseudo random number generator, a simple one. Why not to use it? It fits all of your requirements.
See here, (page 18 & 23 in particular, and a bit further), which shows exactly the same requirement in pictures. This is the fastest PRNG algorithm that has good avalanche effect and long period.
About 10 operations per word (32bit, 64bit) that your machine can operate on, unlike proper cryptography that needs dozens or even hundreds operations on a single byte.
Re-seed the PRNG with data on every step to spread the changes further than one block. Use two passes, one forward and one backward, to make every bit affect every other bit, to the left and to the right of itself.
For example, initial seed is 42 (public), first data chunk in plaintext is "D". PCG uses seed 42, makes output 948. Then you make 948 XOR "D" to get first block of ciphertext. Reseed the PCG with the data from last data plaintext block "D" and PCG last state 948, instead of just 42. To decode you repeat the process, as XOR cancels out. Take the 42 as PCG seed, get 948 as output, make 948 XOR ciphertext (948 XOR "D"), get the initial data chunk "D", and now you can make the next seed to decode second symbol, from D and 948. When you will make a backward pass, you will also need a public seed, otherwise you wont know how to decode, because second pass will override the first one. With two public seeds (they can be the same) you can treat each pass as a separate process.
Previous PCG state and data can be mixed with addition, XOR or other functions. Avoid multiplication to not to introduce too many zeros in PCG state. That is, PCG seed equals to PCG old output (+ or XOR) current plaintext chunk.
This page gives some code examples for PCG:
You can use any PRNG for this role, but check the paper that shows why exactly you should not use each of others available PRNGs. In particular slow avalanche time and patterns.


Quoting the SSH protocol:

  "Note that the 'packet_length' field is also encrypted, and processing it requires special care when sending or receiving packets."

Generally ciphers process bytes from left to right. This means that the packet length can be available before the encryption is ended (or before all the information is received, for that matter).

This is a horrible protocol decision because it means you have to interleave between the packet decoding and decryption layer, and you will get the message length before it is authenticated. Still, it is practically doable.

There is probably one advantage: you can add more padding to avoid some side channel attacks that use the length of the send packages. However, this advantage is hard to use, because you'd now also have to mix the application and encryption code.

Note that the other sizes - such as MAC length - are determined by the protocol and protocol configuration during the handshake.

I think your problem solution is in TCP header. With reference to TCP header, there is a field called 'HLen' which means header-length. By stripping off this header the whole remaining bits are the SSH package (i mean header and data). SSH can decrypt this whole package of bits and then starts reading the decrypted packet according to SSH semantics.
SSH semantics says: first 4 bytes are the Packet-length. The 5th byte is the padding length ... So on


Does Encryption add difficulties to File Recovery? Seems Yes. People always tell us, it is very hard (or almost impossible) to recover an encrypted hard disk.

But after a second thought. I think this is not true.

Given that we know the KEY, and the method/algorithm of decryption, the decryption(key, encrypted_data) should be no different from plain text.

For example,

We mistakenly deleted a file. We have to examine the bits on the hard disk, identify the start and end positions of the file, and un-delete it. Of course the bits on the hard disk looks meaningless. However after decrypted, it appears no different from an ordinary hard disk.
Bad sector happens to the hard disk. For those error bits, those bits are lost, no matter encrypted or not. (Of course you can guess those bits and recover them.) For the rest intact parts of the hard disk, we can still decrypt those files as normal.

However there are some concerns that I am not clear about.

As some (or most) disk encryption algorithms are chaining previous and next sectors. Will this lead to whole hard disk not recoverable with just one error bit?
Consider the "bad sector example" above. If an error bit falls on an JPEG file. With a normal hard disk, we can still view the image, with display error on certain parts only. However with an encrypted hard disk, will encryption leads to whole image not viewable?

All-in-all, given that we know the KEY, and the decryption algorithm, does Encryption still add difficulties to File Recovery?

It depends on the circumstances, whether encryption will cause difficulty while recovering files. If you have your physical drive damaged then chances of recovering the data in the first place (encrypted or not) are bleak depending upon the extend of damage.
First let's think of this hypothetical situation when using file system level crypto on the contents (files) of a drive: If I have an algorithm (that does not use chaining) that uses encryption  with authentication to encrypt the contents of a drive. Say, my drive got physically damaged, but the damage was to a small extend. It so happend that the "error bits" were on a JPEG image. If I decrypt that content from my hard drive, my software would give me an error stating that, the file / content has been damaged and its integrity can never be trusted and would refuse to decrypt it. But If I know the algorithm and the key and I make a custom software to decrypt the contents of the file no matter what, I might get a decrypted JPEG that may be partially viewable/cluttered at some places. But still in essence the data is tampered and the whole purpose of "authentication" has been compromised!
But the above situation is practical if we are using file system level encryption/ decryption and that is why it is more recommended to use it than FDE (full disk encryption), at least you can view parts of the image / file.  But still the algorithm itself opens up difficulties
if I used AES CBC with HMAC to encrypt my file then the block where the error bit occurs, the decryption becomes cluttered and meaningless, and also alters the output of the decryption of the adjacent block but if I used a stream cipher like XChaCha20-Poly1305 the error byte will be meaningless, but I get the rest and in both cases the authentication tags will not match as a result of the errors in the data in the first place.
Secondly, if I used chaining algorithms AES CBC to do FDE full disk encryption, then the error propagates, from the block where the error occurs and also affects the bytes of the next block getting decrypted . It is mostly due to the fact that the encryption function themselves have an avalanche effect when their input bits are changed giving totally different outputs !
At most if you use chaining you loose blocksize*2 bytes of data for blocksize bytes error in a block. For AES this block size is 16 bytes.
Therefore it depends on the algorithm that you use and also the circumstances in which they are applied.
In practice we use AES XTS as the defacto standard for full disk encryption:
See:
Disk encryption theory

AES XTS

Hope you understand what I wanted to convey...


Differential privacy definition Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between these distributions is multiplicative, i.e.

$\left| \frac{Pr[A(D) \in S]}{Pr[A(D') \in S]} \right| \leq e^\epsilon$

I have difficulty in understanding this choice of this multiplicative distance measure, as opposed to the standard distance (statistical difference) as in cryptography (indistinguishability), i.e.

$|Pr[A(D) \in S] - Pr[A(D') \in S]| \leq neg(.)$

The paper "Calibrating Noise to Sensitivity in Private Data Analysis" by Dwork et al. put forth two reasons for using the multiplicative distance:

It is more stringent, since if one probability is 0, the other must also be 0 (which is not guaranteed when using standard measure of statistical difference). This, I understand.
The leakage (distance between the distributions) must be non-negligible for the utility of the mechanism. This I really struggle to understand. Could anyone give an simple example to illustrate this, please?

I can't give an example illustrating why leakage must be non-negligible for the utility of the mechanism, but I can give a proof of why leakage must be non-negligible for the utility of the mechanism.

Let $\;\; U \: = \: \left\{\langle D,D'\rangle : D,D' \text{ differ in one element}\right\} \;\;\;$.

By the triangle inequality, for all $D$ and $D'$, for all $S$,

$|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|$
$\leq$
number_of_elements $\cdot \operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\}$

If number_of_elements is polynomial and $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})\:$ is negligible, then

for all $D$ and $D'$, for all $S$, $\:|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|\:$ is negligible.

If number_of_elements is polynomial and

$\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible, then $A$ is statistically close to being independent of $D$.

Therefore, if $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible then the mechanism is not useful.

Differential privacy has been "invented" for a completely different use case scenario than indistinguishability for data privacy. The scenario is that you outsource your data into an untrusted party with that amount of noise that when the untrusted party applies some operations on data , individual data privacy is protected but the aggregate operation is in clear revealed to the server (That is utility). And differential privacy asks for no inference with respect to the existence or no of a specific data record if you know the result of the aggregate function.


Explanation of openssl ciphersuites I'm looking for a detailed explanation of the ciphersuites available in openssl.

openssl already offers the ciphers command which can be used to output, for example, the following:

$ openssl ciphers -v "HIGH,-SHA,-AES256"
DH-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=DSS  Enc=AESGCM(128) Mac=AEAD
DH-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=RSA  Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-SHA256   TLSv1.2 Kx=DH       Au=RSA  Enc=AES(128)  Mac=SHA256
DHE-DSS-AES128-SHA256   TLSv1.2 Kx=DH       Au=DSS  Enc=AES(128)  Mac=SHA256
DH-RSA-AES128-SHA256    TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AES(128)  Mac=SHA256
DH-DSS-AES128-SHA256    TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AES(128)  Mac=SHA256
ADH-AES128-GCM-SHA256   TLSv1.2 Kx=DH       Au=None Enc=AESGCM(128) Mac=AEAD
ADH-AES128-SHA256       TLSv1.2 Kx=DH       Au=None Enc=AES(128)  Mac=SHA256
AES128-GCM-SHA256       TLSv1.2 Kx=RSA      Au=RSA  Enc=AESGCM(128) Mac=AEAD
AES128-SHA256           TLSv1.2 Kx=RSA      Au=RSA  Enc=AES(128)  Mac=SHA256

It seems that ADH stands for "Anonymous Diffie-Hellman" but also implies specific groups and bit sizes.

I am interested in detailed explanations of what all the abbreviations are and generally which of these ciphersuites are considered secure.

Specifically:

What is ADH? Where is it standardized?
The listed MAC algorithms are hash functions. Is it using HMAC?
What does "Au" mean?

What is ADH? Where is it standardized?

ADH stands for Anonymous Diffie-Hellman, ie unauthenticated Diffie-Hellman, also called "opportunistic encryption". It has been part of the SSL/TLS standards at least since SSLv3. It was also extended to ECDHE in RFC4492.

  The listed MAC algorithms are hash functions. Is it using HMAC?

Yes indeed.

  What does "Au" mean?

It most likely means something like Authentication mechanism. This clearly covers with the given ciphersuites as ADH suites have none there, RSA key-transport and DHE+RSA suites have RSA there (server authenticated via RSA signature), DHE+DSS suites have DSS there (server authenticated via DSA) and suites using static DH ones have DH there (server authenticated via his static DH public key).

Au = Authentication
Kx = Key Exchange
Enc = Encrypt
Mac = Message Authentication Code

For further details, see the OpenSSL documentation about ciphers.


NIZK proof for Order-preserving encryption Suppose a cipher c=Enc(K,m), where Enc() is the order-preserving encryption scheme. Can NIZK be used to prove that c does indeed encrypt m? The Schnorr NIZK is based on discrete logarithms equality. I don't know if it can be used for order-preserving encryption.

Thank you!

You cannot prove that a ciphertext (produced by an order-preserving encryption scheme) encrypts a particularly plaintext in zero-knowledge, because verification of such a proof would necessarily leak the plaintext.

Perhaps you want to instead prove that the ciphertext is well-formed (i.e., produced by the scheme)? This is possible in the context of site's definition of [OPE][1], namely, a method of encrypting data so that it's possible to make efficient inequality comparisons on the encrypted items without decrypting them, since El Gamal conforms to this definition (see [plaintext equality tests][2]), and NIZK proof systems can be used to prove various properties about El Gamal ciphertexts.

EDIT. The comments note that:

I assumed (possibly incorrectly) that the message was not to be revealed, and
The site's definition of OPE is incomplete.

I've proposed an edit to the site's definition of OPE. This answer only applies to the original definition.


Complexity class of an idealised version of Bitcoin's proof-of-work (hashcash)? To formulate this question precisely, I will define an idealized hypothetical "perfect" hash function $H(n)$ which has nice scalability properties, and will formulate a problem PERFECT HASHCASH in terms of that, understanding that practical considerations may end up yielding only an approximation of this ideal.

To keep it simple, we will say that our hash function $H(n)$ takes as input a single natural number $n$. Then we say that $H(n)$ is a perfect hash function iff:

$H:\mathbb N \to \{0,1\}^\infty$; That is, $H$ maps each natural number to an infinite binary sequence, and which the time complexity to compute any initial segment $s$ is polynomial in the size of $n$ and $s$, (making it a sponge function).
For any initial segment of length $d$, the set of all natural numbers $n$ such that $H(n)$ shares that initial segment has natural density $2^{-d}$.

The first thing formalizes the scalability of our function, and the second thing formalizes the idea that we want all hashes to appear roughly "equally often" as an output. Other than that, our perfect hash function is a black box, and we don't care much about exactly how it works, so long as it meets the above properties, as well as the usual desiderata applying to hash functions (easy to compute, hard to invert, hard to find collisions, etc).

Predicated on the assumption that a perfect hash function exists, we can now define the problem PERFECT HASHCASH as follows: PERFECT HASHCASH takes as input a perfect hash function $H$, a natural number $n$, and the zero vector $0^d$ of length $d$, which can be thought of as a unary representation of $d$. A solution to PERFECT HASHCASH consists of an $n$ and $d$ such that $H(n)$ starts with $0^d$.

Given those inputs, it is clear that PERFECT HASHCASH is in the complexity class TFNP, since this is a function problem and a solution is guaranteed to exist.

Can we also identify PERFECT HASHCASH as a member of any complexity class finer than TFNP?

Could it perhaps be in PPP? PPA? PPAD? Something else?

For background, see Complexity class on Wikipedia.

Bitcoin's proof-of-work problem is solved in constant time, since there is no asymptotics. Complexity classes are irrelevant here.


How long would it take to brute force an AES-128 key? How long would it take to crack a AES-128 key using the most advanced technology currently available? The hardware can be anything, be it a high-performance CPU, GPU or even FPGA?

I wrote a similar answer in the past, where the assumption was half the key is known. Since then, the bitcoin hashrate almost tripled (it's used in the estimation, as below). The estimation for half the known key would therefore be $~3.6$ seconds.

But to brute force a $128$ bit key, we get this estimate:

Let's assume we can test as many keys as the current hashrate of the bitcoin network. There special purpose hardware is used and it's for SHA-256, this makes it not directly usable, but it should be close. That means we could test approximately $5 \cdot 10^{18} \approx 2^{62.117}$ encryptions per second. Regarding the type of hardware: For some years now bitcoins are mined mostly with ASICs, which are faster and more efficient than all of those options you listed. That's special purpose hardware, which can't be programmed to do anything else - but it's the best we can do for speed.

That means, for the full key we need $\approx 2^{128} / 2^{62.117} = 2^{65.883}$ seconds. This is approximately:

$68 \cdot 10^{18}$ seconds
$18.9 \cdot 10^{15}$ hours
$2.158 \cdot 10^{12}$ years. Written as integer: $2,158,000,000,000$

Since that number is still slightly hard to grasp, this is the age of the universe: $13.799 \cdot 10^9 = 13,799,000,000$

So a rough estimation would be $156.4$ times the age of the universe for testing all keys. You can divide that number by $2$ to get the average time to find the correct key.

Related question: How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

I didn't understand the most answers here. I my view, exascale computing will be able, to easily crack 128 bit keys in near future. And in fact, 128 bit stands for random generated 16 byte masterkeys, with an security margin of 16^16 (a-f, 0-9). That masterkey is always used to encrypt the data, and is also encrypted by the user password.

That means: 16^16/10^18 (exascale computer) = 0,3 seconds to test all possibilities to find the masterkey (without delays/iterations), without any user password. So only 256 bit keys with 32 byte are secure enough, to protect our data for the next decades. An 512 or 1024 bit cipher would be even better, to have no problems for the next xxx hundred years. I didn't like that "secure enough for xx years".


How secure is ChaCha20? I want to implement a stream cipher to encrypt very sensitive data in my Python code. I heard about the ChaCha20 algorithm and the
PyCryptodome library
, but how secure is it ?

Aumasson et al. Showed that ChaCha6  can be attacked with time complexity $2^{139}$ and ChaCha7 with $2^{248}$.
Shi et al. gave an attack based on second-order differential with $2^{136}$ for ChaCha6 and $2^{246.5}$ for ChaCha7.
Maitra, chosen IV cryptoanalysis and the time complexity of the attack showed that it can be reduced to $2^{239}$ for ChaCha7.
Choudhuri and Maitra concluded ChaCha12 are
sufficient for 256-bit keys against differential cryptanalysis using a hybrid model of non-linear round functions and linear approximation...

\begin{array} {|l|l|}
\hline
Attack & Evaluation \\
\hline
\text{Differential Analysis }      &                    \text{No attack found}\\
\text{Rotational Cryptanalysis}     &                   \text{No attack found}\\
\text{Boomerang Attack}        &                        \text{No attack found}  \\
\text{Linear Cryptanalysis}      &                      \text{No attack found}\\
\text{Distinguishing Attack}     &                      \text{No attack found}\\
\text{Guess and Determine Analysis}       &             \text{No attack found}\\
\text{Time-Memory-Data Tradeoff Attack }   &            \text{Protected}\\
\text{Practically ChaCha Algebraic Attack}   &          \text{No attack found} \\
\text{Attacks on Initialization Process}    &           \text{No attack found}\\
\text{Single Power Analysis }           &               \text{Protected}\\
\text{Practically Difference Power Analysis }    &      \text{Protected Practically}\\
\text{Cache Timing Attack}         &                    \text{No attack found}\\
\text{Fault Injection Analysis }   &                    \text{Protected Practically}\\
\hline
\end{array}
The above table and results come from KDDI Research, Inc

simple power attack; though the rotation is vulnerable to power attack, they propose masking as a countermeasure.
differential power analysis; they demonstrated that adversary can get all keys except $k_1$ which can be found in $2^{32}$, proposed masking as a countermeasure.
Fault Injection Attack; they claim that the initial matrix $X$ or
matrix $X^{(20)}$ will be output if injection is performed on the addition.

A countermeasure against this sort of attacks is to separate variables; that is, distinct variables store the inputs and output of the addition. Consider an addition $z \leftarrow x+y$. The addition returns the initial value of variable z even if the addition is skipped. Thus, the adversary can get neither the value of variables $x$ and $y$. Algorithm 9 shows the implementation using countermeasure based on variable separation.
We should note that variable separation in source-code level does not work

They include all attacks upto 2017 in their document. I couldn't find one in 2018.

ChaCha20 is a "primitive", in other words it's just one component of a secure cryptographic system (and PyCryptodome is a collection of primitives). So in a way, and from the perspective of a programmer, it's not secure at all. It's dangerous to use something so low-level.

In order to implement a secure crypto system, you need more than just encryption. Go with something like Cryptography or PyNaCl - they have already done all the work for you.


Mathematical formula for switching the key for OTP? Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key? The new key must be as random and secure as the original key.

Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key?

No.
(Please keep reading…)

A single mathematical formula won’t cut it. That’s where cryptographic algorithms come in. There are more than a hand full of cryptographically secure pseudo-random number generators, stream ciphers, et al which could be used to create a cryptographically secure key… but when having to fall back on those, you might as well simply use them in the first place and drop your one-time-pad idea.

In fact, I’m wondering a bit: What research have you done? I’m asking because you seem to have skipped some of the important parts of what defines OTP.

Per definition, OTP requires the “key“ to be…

a truly random one-time pad value,
generated and exchanged in a secure way.
at least as long as the message, and
only to be used once.

Related to Point 1: Please note that it says “truly random” and not “pseudorandom”. Fact is that no mathematical function by itself can be truly random. Meaning: if you would use a math function (for example: a multiply-with-carry construction) it would definitely not satisfy the definition of OTP.

In a best case scenario, you would be dealing with a CSPRNG or a stream-cipher alike solution. As you probably know, those do exist and indeed provide cryptographically secure randomness (to some extend), but when thinking along that path you really have to ask yourself if you really want to use a car to ride a horse.

Instead of trying to make a square wheel round, it would be more constructive to revalidate your idea and check on already existing stream ciphers and/or cryptographically secure pseudo-number generators. A simple “it looks random so it must be secure” thing definitely won’t be able to handle the job! In case of doubt, look at the numerous PRNGs which have been cryptographically broken (and practically destroyed by cryptanalysis within the blink of an eye).

Related to Point 2 up to Point 4: That “exchanged in a secure way” is important because OTP can only be as secure as the key exchange procedure, which tends to be a problem when messages or data packages size up to a few megabyte or even gigabytes*.

Surely that’s where your question rooted. Yet, trying to find a way around the problem via a math function is neither OTP. nor cryptographically secure.

Last but not least…

  The new key must be as random and secure as the original key.

I wonder how you are planning to compare that. See, a truly random source is unpredicable. Same goes for things like cryptographically secure random number generators (assuming they’re not flawed or broken in some way).

Wrapping it up:

If you really want to stick with OTP, you’ll have no other choice (thanks to its definition) than to use a truly random, cryptographically secure source.

If that’s not available, you could fall back on something like a CSPRNG, or a stream-cipher alike construction (for example: HMAC-based). As said: a simple “mathematical formula” won’t do it. Only a cryptographic algorithm would come near the term “truly random”.

As an alternative: if you want something that’s both cryptographically secure and practical to use (which you indicate to be your main issue), you should definitely look beyond OTP. For example: stream ciphers like Salsa/Chacha. In the broadest sense, stream ciphers ”simulate” the one-time-pad idea. Using them you wouldn’t need to think about working around OTP annoyances.

Also, I think it is worth noting that there’s nothing wrong using good, well-vetted block cipher like AES/Rijndael.

(Funny enough, you could even use a block cipher like AES to create a CSPRNG construction which you could then abuse to create your one-time pad values. But that’ld be overkill since AES does a good job when it comes to encrypting data – which makes considdering OTP pretty superfluous.)

I would like to address two aspects of your question, however, before I do, I must briefly mention "Multiple Use Pads" (MUP rather than OTP). MUPs are similar to OTPs except that, they may be reused in a digital environment, and are practical and efficient - meaning they don't have to be a truly (perfectly) random byte array.

"The new key must be as random and secure as the original key". as e-sushi pointed out, the concept of a truly random OTP that is computer generated is unrealistic. That said, my approach and research has focused on "re-use" so that it isn't necessary to obtain additional MUPs; if a new OTP is needed for each new message (as it was with paper and pen: see Venona project), then OTPs will never be practical and secure. This goes to the second aspect or your question that I would like to address below.
"Mathematical formula". Allow me to begin by saying that I see math more as a 'pattern' based vision that uses discipline and appropriate skills to generate algebraically based expressions (known as formulae). Not all patterns can be confined to an algebraic platform. I have seen many attempts at using formulae, such as generating the OTPs with a smaller key. Bottom line, a smaller generator effectively results in, not a true OTP, but a much smaller "key" (generator) that can be broken/discovered.

  Bottom line: gain the advantage of "unlimited key sizes" without the
  need to generate a perfectly random byte array, and without the
  vulnerability associated with key reuse.

Note: I am new to this site, and have just become aware that I must cite that I am the founder of CORAcsi and the developer of MUPs.


Yarrow and weak cryptographic keys on macOS Given that macOS uses Yarrow as a PRNG, and Yarrow is only capable of 160 bit outputs (/dev/random on macOS is actually Yarrow) are keys generated on macOS weaker than Linux?

Even BSD has switched to Fortuna.

Is this is big gaping hole in Modern macOS security?

https://en.m.wikipedia.org/wiki/Yarrow_algorithm

EDIT:

I have looked through the source and it seems as if they switched to a DRBG NIST generator?

https://opensource.apple.com/source/xnu/xnu-4903.221.2/osfmk/corecrypto/ccdbrg/src/ccdrbg_nisthmac.c.auto.html

There are very few references to Yarrow in the 10.14 XNU code compared with older versions of the Kernel, but 10.14 still contains this string in key.c :

/* Our PRNG is based on Yarrow and doesn't need to be seeded */
That said if you looked at older XNU Yarrow is littered everywhere.

Source code for XNU:

Lots of Yarrow references in XNU 2782 - macOS 10.11

Very few Yarrow references in XNU 4903 - macOS 10.14

So, are Apple still using Yarrow?

Update: Apple are using Fortuna.

A 160-bit seed is plenty for a cryptographically-secure PRNG. We are not going to be able to count to 2160 any time soon, so there is no need to worry that this is a "gaping hole". While in theory Linux's random driver may have a larger keyspace, it's not going to make a difference in real life. Fortuna does have advantages over Yarrow, but a larger key size is not what's important. What really matters is resistance to side-channel attacks and adequate entropy collection at boot time.

By default, Yarrow-160 actually uses 3DES in counter mode to generate the random output, which gives it approximately 112 bits of security. Fortuna uses any other block cipher in counter mode, but typically 128-bit AES. The Linux randomness driver uses ChaCha20. It starts out with 320 bits of secret material (a 256-bit key and a 64-bit nonce). Each reseed updates the 256-bit key. So yes, Linux has a larger keyspace. No, this doesn't matter in practice. Yarrow, Fortuna, and Linux's CRNG are all secure.

Whilst the estimation of input entropy is regarded as conservative (as is Linux's), not blocking means that information theoretic secure output cannot be achieved.  So any key or keys generated in an (output length) > (input entropy) situation can theoretically be inverted/predicted. It is not mathematically impossible, only computationally difficult (at present). Tomorrow or the day after it may become possible.
We can't predict the future, but one consequence of macOS is that it cannot be used to generate a one time pad.  Therefore macOS keys can be viewed as being less secure than /dev/random Linux keys in this (rare) use case. That means it's one small crack, rather than a gaping hole, and exists irrespective of the 160 bit key space.

Above excepted, given side channel attacks and side of side channel attacks, I suggest that there is no holistic security difference between a 256 bit key and a 160 bit key (the problems with SHA1/3DES aside).  Mathematically $2^{256} > 2^{160}$. But given all current and future side channels, I can't see a practical real world difference when trying to preserve a secret.

Holistic security: security in the whole given all aspects of a political, economic, social and technological analysis (PEST). E.g. What's the difference between key sizes when Australia has now outlawed unbreakable encryption? E.g. Why brute force a key when a key logger/camera is less costly to install?  E.g. Or hack the phone rather than the  $n$ bit app?


additive ElGamal encryption algorithm I'm performing ElGamal encryption algorithm and using the additive homomorphic property so the product of two ciphertexts is the encryption of the sum of the plaintexts.

The problem is that I need to return the original plaintext sum values.
How could I get them using decryption?
Is there an algorithm I can follow, given that I have both the private and public keys?

I have tried to decrypt it, but it returns the value $((g^{x+y}) \bmod P)$ where $p$ is prime, $g$ is a generator, and $x$ and $y$ are the plaintext which I need to know.

$x+y$ is usually a very large number.

Normal El Gamal is multiplicatively homomorphic: $E(x) E(y) = E(xy)$.

If you want to make it additively homomorphic, you fix some generator $g$; then you transform the integer $x$ to the group element $g^x$ before encrypting with El Gamal.  With this transformation, $E(g^x) E(g^y) = E(g^x g^y) = E(g^{x+y})$, so now you have an additive homomorphic property.

To decrypt, you need to be able to take the discrete logarithm.  This can be done efficiently if the value $x+y$ is known to be "not too large".

For a bit more of an overview of this approach to making El Gamal additively homomorphic, see the following question: Can Elgamal be made additively homomorphic and how could it be used for E-voting?.  Then, check out Why is the discrete log problem easy when the exponent comes from a binomial distribution? for details of specifically how to do the decryption, and how small the messages need to be to ensure you can decrypt in a reasonable amount of time.
In the future I encourage you to use the search function to check whether the question has been asked before.

If $x+y$ is usually so large that the above methods don't work, then you'll need a different cryptosystem; simple El Gamal isn't gonna work for you.  The Paillier cryptosystem might be a good choice.

You can use El Gamal over elliptic curves.

Your current understanding of El Gamal is carried over to EC El Gamal, with the following alterations to the implementation of El Gamal encryption & decryption:

1) You calculate over elliptic curves (mildly complicated & out of scope).

2) Group operation is now addition instead of multiplication: powers become scalar multiplications (over EC), multiplications become additions (over EC).

With this modified El Gamal, you can use shorter key lengths as typical of elliptic curves.
The resulting scheme is also "plainly" additively homomorphic in the same way that plain El Gamal is multiplicatively homomorphic -- no need to solve DLP.


Encryption algorithm that produces dummy output on incorrect passwords Background:
  I've been thinking about using encryption in the context of backing up files to untrusted locations (to the point of making the file publicly and widely distributed for practically failsafe backup).

  The problem is, once a file is publicly available, it will forever remain so. And in 20 years, when computing power is unpredictably faster, AES256 bit encryption might be practically useless - and my private backup file readable to all.

I was thinking, as a deterrent to brute force attacks on encryption, what if when the wrong password was tried the algorithm returned dummy data that would require human examination to assert that the data is not what the attacker is looking for.

Example:

I encrypt the plain text (say, an account number) '123456789' with the password 'pass'.

Attacker attempts to brute force the encryption and tries the password 'a'.

The result is '987654321'.

Now, how is the attacker to know that this is not the value I encrypted, and that the password I used was 'a'? Additionally, even if the attacker guesses the password 'pass', how are they to know that '123456789' is the correct value?

This of course is a simple example and most people encrypt somewhat recognizable artifacts; human language text, files recognizable by headers, etc. So this idea could be expanded to not just scramble data upon output, but also to include a variety of generated 'dummy' artifacts (common file formats, samples of language text, etc) not necessarily included in the core algorithm (the dummy data could be user defined). The dummy data output on incorrect passwords could then possibly include valid JPEG files, WORD files, PNG files, and samples of valid text from a variety of languages.

The result would make the encrypted file very hard to brute force without either a huge amount of computing and human power, or specific knowledge of what is encrypted.

Are there any algorithms out there that work like this? Are there any flaws in the idea itself?

Yes, this is possible (conditionally). It sounds like you want Format Preserving Encryption. FPE works by encrypting from an arbitrary domain $X$ onto $X$. Consequentially, if plaintext $M \in X$ is encrypted to ciphertext $C \in X$, any decryption of $C$ - even with the wrong key - will yield a decrypted message inside of $X$. Thus an attacker doesn't know anything from a decrypted ciphertext if he only knows the original format of the valid plaintexts. All decrypted ciphertexts look like valid plaintexts to him.

For example, your domain might be "all ASCII strings of length 7", or "a NULL-terminated string of numbers with length less than 10", or some credit-card number format. All plaintexts, ciphertexts, and wrong-key decrypted ciphertexts will be in that domain. From your example, you might have a domain of 9 ASCII numeral digits.

(In case it's not obvious: The way an attack typically works is that the attackers are decrypting a ciphertext onto a plaintext message space $Y$, but they know something about the original plaintext that limits the potential domain to some set $Z$ strictly contained within $Y$ (that is, $Z \subset Y$). On a typical cipher we encrypt $\{0,1\}^n \rightarrow \{0,1\}^m$ (one binary string to another), but it's rare that all plaintexts could actually be any binary value, generally they are only a strict subset of the input domain. So we assume the attacker knows which plaintext formats are valid, and they just check decrypted plaintexts against this smaller domain. FPE addresses that issue by only allowing encryption and decryption from and to domains that are valid plaintexts. The attacker will never be able to look at a decrypted value and conclude that it is an invalid plaintext. Eg, if they are decrypting a credit-card number, they have an idea of what a valid decrypted CC will look like, but with an FPE algorithm all decrypted messages will look like a valid CC.)

Note that this won't mitigate the problem if the attacker knows some part of the original plaintext that does not apply to all valid plaintexts. FPE mitigates attacks where the attacker just knows the original message space for all valid messges, but it's possible they know something about the specific message on hand that doesn't apply to other messages. (For example, they may know that the 3rd digit is an 8 for the plaintext in question, but not necessarily an 8 for all plaintexts.) In this case they would have a smaller domain to check decrypted messages against and their original attack will still help them to some extent.

An FPE algorithm can be implemented from an existing block cipher. There are different schemes for turning a block cipher into an FPE, depending on your domain size and such. Some of the constructions are relatively simple given the block cipher and a function that decides whether a raw block cipher output is inside of the desired domain. The Wikipedia page linked to above contains descriptions of some.

As for your example: I think that it's rare to see FPE applied to very large domains, like image files. It's usually only applied to small domains, things like credit-card numbers in databases. I don't think I've seen it used in a case where the domain was larger than a couple block cipher blocks. (But whether you can use FPE efficiently on very large domains is a different question.)

It's certainly possible to design an encryption algorithm so it's possible to identify a "correct" decryption.  For example the algorithm could append a hash to each block before the actual encryption, and check the hash after decryption.

However, I think this would actually make the overall system less secure.  One of the problems a brute force attack has is to determine if the decrypted text is correct (and therefore it's task is done).  Adding a categorical check makes this trivial.


Is there an English translation of Vigeneré's "Traicté des Chiffres"? I Googled Vigeneré's "Traicté des Chiffres": no English translations,  not even a reference to one. Perhaps someone's Google-wu is better than mine; I can't find it.

I'm slogging my way through a PDF of the 1586 edition of "Traicté Des Chiffres, ou Secretes Manieres D'escrire" by Blaise de Vigenere. The language is early Modern French and doesn't translate easily in Google Translate (the words for 'right' and 'left' back then were droict and gaulche, etc).

I'd love to read it in English. Is an English translation available?

There is neither a „modern” French edition, nor an English translation, contemporary or modern. Time to learn some contemporary French. What's the use of attempting cryptoanalysis if you can't manage the historic version of a quite common language, in this case early modern French? Your approach works like the Traicté on its own linguistic grounds, not on yours.


How is a public key actually used to encrypt something? One thing cryptography articles never seem to explain is how the message actually gets encrypted. You get this long-winded lecture on number theory which ends with, Ta Da! and we have a public and private key. Then, they never explain the process of exactly how some 100,000 byte word document gets encrypted using the public key.

Other times the explanations seem downright misleading. For example, in my book Cryptography (by Meyer and Matyas) it says for RSA the ciphertext is the plain text to the power of key. How do you exponentiate a word document? I don't get it.

Rick Demer already wrote the answer in the very first comment, but without explanation: Hybrid encryption.

But since you asked for a real practical example to encrypt your word document, this is how: Your file is on your disc, and it is 100,000 byte large. You can then do:

First, you start up a random number generator. Preferably you should either have true randomness or at least a cryptographically secure RNG.
Let the RNG generate a random 256 bit number.
Start up your AES 256 engine/program/hardware module, and choose the appropriate mode of operation like CBC. Use the random number as key.
Use AES to encrypt the entire content of the file.
Get your public key or generate private/public key, depending on what you want to do.
Encrypt the random number (used as symmetric key) with your asymmetric encryption scheme. In the case of RSA, do not just use the textbook variant but RSA-OAEP or a similar padding scheme.
Create a new file: Put relevant information in the file header (whatever you want to be accessible without decryption). In the data of the file, write down the encrypted random number (it was encrypted with the public key), and then you just add the entire encrypted file-content (encrypted with AES).
Optional: You can add delimeters inside your file to make it easier to see where the key ends and where the ciphertext starts. If you want you can also note down which algorithms you actually used to encrypt this specific file.

AES can obviously be replaced with any other symmetric cipher, you can also pick a different mode of operation or use a specific asymmetic encryption scheme to encrypt the random key. If you do so, putting it into the file might help if you ever forget which file was encrypted with which algorithm.

Note on using asymmetric encryption directly

It is also possible to use for instance RSA directly on your $100,000$ byte document. If your RSA key is $1240$ bit long, then you can split your document into $800$ blocks with each block having $1000$ bit (or e.g. $650$ blocks of $\approx 1231$ bits, whatever suits you). Then you can apply RSA directly to each block and be done with it. The problem is that this is extremely slow. The ratio of processed bits per second is magnitudes lower for asymmetric encryption than for symmetric encryption. And then you have the problem, that RSA shouldn't be used in the textbook variant and RSA-OAEP increases the length.

One thing cryptography articles never seem to explain is how the message actually gets encrypted.

Either you're reading really bad articles or you're missing a step.  Try reading better articles and follow along very carefully.

  Then, they never explain the process of exactly how some 100,000 byte word document gets encrypted using the public key.

You break up the document into blocks of a particular byte size. Treat each block as a series of bits. That's a number. Feed the number into the crypto algorithm, get a number back out. That's also a series of bits. Now you have turned a series of plaintext blocks into a series of encrypted blocks.

  Other times the explanations seem downright misleading. For example, in my book Cryptography (by Meyer and Matyas) it says for RSA the ciphertext is the plain text to the power of key. How do you exponentiate a word document?

If you really want to see how it works in practice then I encourage you to read the source code. For example, download the source code for BouncyCastle and take a look at the GetInputBlockSize, GetOutputBlockSize, ConvertInput, ConvertOutput and ProcessBlock methods in the RSACoreEngine.cs file. This is only 150 lines of pretty easy-to-follow code but it answers all your questions.

As others have mentioned, it is often impractical to use public key crypto on large documents because the math is slow. Usually what you do is choose a symmetric cryptosystem, choose a random key in that cryptosystem, encrypt the document in that cryptosystem, encrypt the symmetric key using the public key. Now the document cannot be decrypted without the symmetric key, and the symmetric key cannot be decryped without the private key.


Private Information Retrieval and Writing at the same time possible? Are there any (possibly multiserver) private information retrieval (PIR) schemes that support private reads and writes (so called PIR Writing) at the same time, while having sublinear (in the database size) communication overhead?
The most recent, very efficient, PIR scheme I could find is the one based on distributed point functions, but it seems to only support one operation at a time. That is, I can either outsource a database, where I have private reads or I can outsource a database, where I have private writes, but not both on one database. Preferably I am looking for something that is not based on heavy tools like FHE.

Here's a single-server one: https://link.springer.com/content/pdf/10.1007%2F978-3-642-13708-2_26.pdf

Obviously the data would need to be encrypted, otherwise it will be obvious what was changed, and the PIR-write protocol needs to somehow re-randomize the ciphertexts that were not modified.

Check out the four-server ORAM scheme in this work (link attached).
The scheme does not use any complex data structure, but rather stores the data in a secret-shared and replicated plain array. It uses distributed point functions for both PIR and PIR-write, at the same time.

  The core idea behind the scheme is to apply DPFs not only for PIR, but also
  for a variant of PIR-write. PIR-write, (a variant of which was first investigated
  in [OS97]) is a cryptographic primitive that is the analog of PIR for a write-only,
  rather than read-only, database. We use DPFs to construct a simple two-server
  PIR-write where every server holds an additive share of the data. Our PIR-write
  protocol is limited in the sense that the client can only modify an existing record
  by some difference of his specification (rather than specifying the new value to
  be written). However, if the client has the ability to read the record in a private
  manner, then this limitation becomes irrelevant.
  We combine the read-only PIR and the write-only PIR-write primitives to
  obtain a four-server ORAM scheme that enables both private reads and writes.
  In the setup, the client generates two additive shares of the initial data, X0
  , X1
  s.t. X = X0 ⊕ X1
  , and replicates each of the shares. Each of the four shares
  obtained is given to one of the servers. For a private read, the client retrieve each
  of the shares X0
  , X1
  , using the DPF-based PIR protocol, with the two servers
  that hold the share. For a private write, the proposed PIR-write protocol is
  invoked with pairs of servers holding different shares of the data

https://arxiv.org/abs/1802.05145


Is this a correct way of use symmetric encryption? If I want to encrypt some block of text in AES, but at the time of decryption I don't have a way to check if the symmetric key is the correct one. So I:

Generate a randomKey, and use that to encrypt the text.
Encrypt the randomKey plus its hash using the user provided Key.
Save everything to a file.

Encryption

var userKey;
var plainText;

var randomKey256 = generateHexString(256);
var hash256 = sha(randomKey256);
var signature512 = concat(randomKey256, hash256);
var header = AES256_encrypt(signature512, userKey);

var cipher = AES256_encrypt(plainText, randomKey256);

var encryptedFile = concat(header, cipher);

Decryption

var userKey;
var encryptedFile;

//split encryptedFile in header|dataCipher
var header = encryptedData.substring(0,512);
var dataCipher = encryptedData.substring(512, null);

var signature512 = AES256_decrypt(header, userKey);

//split signature512 in RandomKey|Hash
var randomKey256 = signature512.substring(0,256);
var hash256 = signature512.substring(256,256);

if(SHA(randomKey256)==hash256){
    //valid key

    var plainText = AES256_decrypt(dataCipher, randomKey256);
}
else{
    //invalid user key
}

Obviously this is not real code. I understand that I will not be implementing my own security. I'm assuming that the whole thing would be encrypted in a safe environment. The user key is NOT going to be transmitted or stored anywhere.

What you did seems fine for verifying the key is correct.

However, unless AES256_encrypt uses an authenticated mode of encryption (in which case the whole exercise would be unnecessary), there is nothing that prevents an attacker from modifying the message. And depending on the mode of encryption used, that can even compromise the privacy of the message.

It would be best to use authentication. For example, you could calculate an HMAC over the data. That immediately proves that the HMAC key is correct if the message authenticates. To prove the AES key is correct as well you can derive them both from the same base key, e.g. a = HMAC(k, 'auth'), e = HMAC(k, 'enc') and then use key a for an HMAC over the ciphertext and e for AES encryption.

For the symmetric key crypto, generally speaking, you must provide the secret key to the other end for decryption. The same random keys can be generated at the receiver end, if you use same function with same parameters.

I am also a bit confused, since you have also used "signature" word in your program. Are you talking about the encryption or the signature? Note, the generation of signatures are different than encryption.


How does the cyclic attack on RSA work? I am trying to get the idea of cyclic attacks againts assymetric RSA encryption.
Taken from Handbook of applied cryptography .

Let $k$ be a positive integer such that $$c^{(e^{k})} = c\mod n  \tag{1}.$$
There for
$k-1$ it holds that $$c^{(e^{k-1})} = m \mod n  \tag 2$$ where $m$ is the message for encryption $n$ is the modulus and $c$ is the ciphertext.

I can't understand why equation (2) must hold?

We start with the definition of textbook RSA encryption: $c = m^e \bmod n$. From your first equation

$$c^{e^k} = c \pmod{n},$$ we have that if $c^{e^k} = c \pmod{n}$, then $e^k = 1 \pmod{\phi(n)}$ (Euler's theorem). Dividing both sides by $e$, we get

$$e^{k-1} = e^{-1} \pmod{\phi(n)}.$$

By definition, $d = e^{-1} \pmod{\phi(n)}$. Thus, $$c^{e^{k-1}} = c^d = m \pmod{n}.$$

Choose two prime numbers, p=3; q=7.

n=p*q = 21
Phi(p, q) = (p-1)*(q-1) = 12
Choose number e, so that it could be prime && less than Phi(p,q), i.e.: 3, 5, 7, 11. (Example e=5)
Now {e, n} my public key
We need to calculate number d, so that (d*e) % Phi(p,q) = 1, i.e. (5*d) % 12 = 1, d might be 17
for example.
{d, n} = private key
Lets suppose friends message is number 19; P=19.
{e, n} = {5, 21} ==> 19^e%n => 10; E=10
Your friend sends E to you
You receive message E=10
{d, n} = {17, 21}
E^d%n = 19


Storing RSA private key Currently I'm developing an application where users generate their own pair RSA keys in order to achieve a secure communication with my server. Also clients are able to communicate directly, sending signatures (proving authentication, as PGP does), therefore I cannot use Diffie-Hellman for this scheme.

Indeed, I'm aware of some techniques of storage of private keys. I thought on enciphering them with AES-256 asking the user an alternative password since using their personal/client password could be a risk if my server gets compromised and the attacker counts with clients private key's ciphertext somehow.

I was thinking about https://en.wikipedia.org/wiki/Zeroisation. Just decipher the ciphered private key and delete it from memory when not needed. Also I read some info about TPM, but I'm afraid this only concerns cryptographically secure hardware equipment and other devices based on vendor's signature verification before booting (maybe I'm not right with it).

I would want to know which is the "best way" for storing private keys in the clients computer, because I cannot store them in my server.

I am currently hoping to find an answer to a similar problem, but maybe I can share some ideas. I would say that your problem is more standard than mine, and therefore it has the benefit that the existent options are relatively standard. However, my own question made me realize that key storage is an information security problem, as opposed to a cryptographic problem. With this, I mean that there is no provable best approach, but there are techniques and good practices that could help to mitigate risks, given some threat model.

Said threat model is, in fact, the most critical aspect to determine what is relevant. There are some approaches in terms of good practices, but they should be considered more as suggestions than as a checklist or a perfect answer.

One aspect that seems to be relatively agreed upon is that the encryption should happen within an environment separated from the normal processor (i.e. TPM, HSM, smart cards). I haven't looked into TPMs, but the other two seem to be the standard way to go.

Now, if additional hardware is out of the table, I can see that your approach makes sense in general. I would worry for the way in which each copy of the key is handled (encrypted and unencrypted, in RAM and in disk, in active usage and in backup), and the way in which the password is used for encryption. In particular, the less the key exists in plaintext, the better.

But mind the threat model. Knowing what you are concerned about is key to know whether your defenses are actually defending you.

@kub0x Initially I thought about using AES-256 to protect the private keys in my app, but then you have to worry about protecting its key password. Camouflaging the private key was my next thought. But the camouflaging algorithm would itself be entropy-reducing meaning less-secure. What if someone found out the algorithm? Finally, I settled on using a crypto library’s implementation of ECC (Elliptic Curve Cryptography) and ECDH (Elliptic Curve Diffie Hellman) operations.


Which one these alternatives using authentication and encryption will solve this multiple-user database problem? Which one these alternatives using authentication and encryption will solve this multiple-user database problem?

I'm trying to understand the field of cryptography, so I've started reading a textbook on the subject.

An exercise at the end of a chapter of authenticity asks the following:

I've got a strong feeling that the second alternative is not safe under the security policy / threat-model, but I'm not sure.

Can someone help me justify this, or give an argument on which one of the two alternatives fails?

The first one looks more complicated, but it is wrong. What you should see is that a man in the middle attack by user $B$ can replace it by $E_{pk_D}(R), S_{sk_B}(E_{pk_D}(R)), B$. Now the server will happily verify the signature, decrypt the request, and return the data to $B$ instead of $A$.

This is why in general you cannot trust that available data was only signed by one entity, and this is why in general we use sign-then-encrypt for asymmetric schemes while we tend to use encrypt-then-mac for symmetric schemes. You would not have trouble if you'd only accept signatures from one entity or from fully trusted entities, but that's clearly not the case here.

It seems that you do want to be given the answer and not just hints, so I will do that. But I'll go step by step so that you can stop reading if you want to finish by yourself.

It seems to me that both solutions satisfy the first requirement consisting in authenticity. Breaking this property would consist in changing the content of $R$ to fool $A$ (this would rather be integrity it's more or less linked) or to change the secret key to yours so that the answer is readable by you. And this should be done such that $D$ still sees the query as legitimate.

For both solutions I don't see how it could be done, so it seems secure to me.

However one of the two solutions fails at the second requirement which is about privacy. The attack I see has a trick which may be why you are stuck.

The trick is: you don't read what was the query from intercepting it, but you can test if the query you intercepted was this or that.

Indeed you do not need $A$'s secret to compute $E_{pk_D}(R)$ which is sent "as is" in the first solution. So you can make a bet on what is $R$ and compute $E_{pk_D}(R)$. If your result is what was in the query, you got the query. Else you still learned what the query is not, which is still harmful for the security of the scheme.

Important: this happens because RSA is deterministic, but in real world we would use RSA with OAEP (named RSAES-OAEP, part of PKCS1 standard) with which I think (?) both solutions would be secure.

Answer: the first solution is not secure.

This notion is captured by the notion of Chosen-Plaintext Attack (CPA) which models a situation where the adversary can encrypt whatever message he wants. It is obviously the case for the first solution in which anyone can compute $E_{pk_D}(R)$.
The game for testing if a scheme is secure under the CPA model (more precisely here if it achieves IND-CPA) is:

adversary can encrypt whatever message he wants (or have it encrypted by an Oracle)
adversary gives two messages of its choice
one of the two messages is chosen at random, encrypted, and given to the adversary
adversary must guess which one of the two was encrypted.


What is the diffrence between Feistel networks and SPN? I recently read about the concept of Feistel Networks and Substitution Permutation Networks but what is exactly the difference between the two ?

In a Feistel networks (from the German IBM cryptographer Horst Feistel), the input is divided into two blocks ($L_0$ and $R_0$) which interact with each other. Main example is DES.

basic construction:

In a SPN (Substitution Permutation Network), the input is divided into multiple small blocks, applied to a S-box (substitution), then the bits positions are mixed (permutation). The key addition may occur before or after these two operations.

Present block cipher:

From Wikipedia:

Although a Feistel network that uses S-boxes (such as DES) is quite similar to SP networks, there are some differences that make either this or that more applicable in certain situations. For a given amount of confusion and diffusion, an SP network has more "inherent parallelism"1 and so — given a CPU with many execution units — can be computed faster than a Feistel network.[2] CPUs with few execution units — such as most smart cards — cannot take advantage of this inherent parallelism. Also SP ciphers require S-boxes to be invertible (to perform decryption); Feistel inner functions have no such restriction and can be constructed as one-way functions.


Number of keys for a monoalphabetic cipher My teacher stated that…

  The number of possible keys (E) in a monoalphabetic cipher is $26$!

My thinking:

  Every letter in the alphabet can be $25$ different letters hence it the  number of possible keys should be $26^{25}$.

What is wrong with my way of thinking, and how did she come to a conclusion of “$26!$”?

Your teacher is right, and here's why:

What happens if you encrypt A with G and B with G? You can't decipher it, because you have no idea if the G in the ciphertext was an A or a B.

So…

For the plaintext letter A you can use the ciphertext letter A, B, C, … , X, Y, or Z. ($26$ possible letters.)
For B you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A. ($25$ possible letters.)
For C you can use A, B, C, … , X, Y, or Z, but not the letter you did use for A or B. ($24$ possible letters.)
...
For Z you can only use the remaining letter. ($1$ possible letter.)

The whole number of possible keys is $26\times25\times24\times [...] \times2\times1 = 26!$ (The exclamation mark denotes the factorial of a number.)

if s={ a,b,c}

for this , possible combinations {abc,acb,bac,bca,cab,cba} so its 3!
same way its 26!


Is there a technique to confirm that a given large integer value is a product of two primes? Given a list of 2048 bit integer values in which one or few 2048 bit integer values
may be product of two prime numbers and other values may be just 2048 bit odd integers numbers.

My question is -
Is there a way / technique (apart from brute-force) to confirm that a given 2048 bit integer value is product of two prime numbers or not?

Is there any pattern in an integer value which is not product of two prime numbers?

No, there is no known test that we can run on a 2048 bit composite number that would indicate whether it was the product of two primes, or whether it was the product of more than two primes.

About the closest we can get is a zero knowledge proof; we know how someone (who does know the factorization) can run an interactive proof with us that can demonstrate to us that there are only two prime factors (and not reveal anything else).  However, that does not appear what you're asking for.

Calculate square root of your allegedly combined number (cn)
lookup prime number (pn) that is closest to it
lookup precomputed primorial (pp) for that prime number (pn)
calculate greatest common divisor of (pp) and (cn)
If the result is 1, the number (cn) is not combined and a prime number itself

Question is only where to get primorials for such high numbers, maybe ask the NSA ;)


What makes AES look like an ideal cipher? There are 2128! permutations on 128-bit inputs. AES supports a maximum key length of 256 bits, therefore offers at most 2256 permutations. The total number of 128-bit permutations is much larger than what offered by AES, which means AES actually only explores a very tiny portion of the permutation space.

Questions:

Given AES doesn't support > 256-bit key length, what makes people believe AES (or any "good" cipher currently being used) would look similar to the ideal cipher that chooses a 128-bit permutation randomly? Put it another way, what makes people believe AES is better than another cipher with 256-bit key length which can give 2256 different permutations?
Is it possible to develop an ideal cipher with enough key length which runs encryption and decryption in polynomial time? The key length would be at least log((2128)!). My poor math gives a result somewhat close to 128*(2128). So I guess the answer to this question would be no. But it strengthens Question 1 by giving an idea how insufficient AES key length is: The ideal cipher requires an exponentially larger key length.

AES is not an ideal cipher, nor is it intended to be an ideal cipher. AES is meant to be a practical cipher that offers a strength close to the key size. That means it is computationally infeasible to find the key even if given the plaintext and the ciphertext. AES - when correctly used with a strong mode of operation - produces ciphertext is indistinguishable from random if the adversary can choose the plaintext input to the cipher themselves (IND-CPA).

The next question is why people think that AES is better than other ciphers with the same key size. Cryptographers generally don't really think that. There are other ciphers that may have better characteristics when it comes to protection against side channel attacks. Other ciphers have a larger % of rounds to spare when it comes to protection against certain attacks. Or they may have a larger block size, or they do not have a clear mathematical structure etc. etc.

AES has been studied a lot, and few attacks have come close to breaking AES. It is relatively fast compared with other block ciphers, and it has a serviceable key and block size. The algorithm is well understood, and there are many hardware implementations of AES, including newer x64 and ARM CPUs. So it is standardized, popular, well understood, but not necessarily the most secure cipher. It doesn't need to be, for most situations it is secure enough.

When you are talking about implementing an ideal cipher you seem to go over the key requirements of a one time pad. The one time pad requires a key the same size as the plaintext / ciphertext. Moreover, you won't be able to distinguish a good key from a bad key for a single block. But what happens if you have multiple blocks to compare? With each block a specific key becomes more likely. As such, it makes very little sense to try and create an ideal block cipher.

The ideal cipher is mainly a theoretical construction, useful in proofs. But beware that inserting an actual block cipher in place of an idealized block cipher may not result in a secure construction. For instance, a hash function could well be secure when constructed using an ideal cipher, while it could be vulnerable with AES-256 due to related key attacks.

There is a perfect cipher – one-time pad (OTP). In many cases, it is not much practical because of the key size requirements.

AES is rather some imperfect but practical cipher.

Having a that allows all the permutations for 128-bit blocks would be neither perfect nor practical:

The key size is obviously impractical and infeasible. Even copying such key would probably take longer than exhaustive search of AES-128…
Maybe the cipher would be perfect under some assumptions for encrypting a tiny 128-bit message. But then, you need to encrypt some larger message (which is quite common; 128 bits are not enough even for SMS…), so you lose the theoretical perfection.
Using larger blocks would obviously require larger keys.
Using smaller blocks would compromise security sooner than it would make the key size practical. There are known attacks for 64-bit block ciphers (see https://sweet32.info/ ), but still, a constant-size key that can describe any of those (2^64)! permutations is too large.


Does selectively generating keypairs with particular public-key hash prefix weaken the security? I'd like to embed 8-bits of information by selecting only keypairs where a hash of the public key begins with those 8-bits.  (The expected number of keypairs that will need to be generated is 256, so there is a little extra work required.)
The goal is to be able to determine the source of a keypair, to aid debugging in a distributed system.
Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?  (Assume that the hashing function is irreversible.)
If so, how?

Does selecting only keypairs, where a hash of the public key has a particular property, weaken security?

No, if the hash used is independent of the public key cryptosystem. Then the selection of private keys made is equivalent to a random selection, and can't harm security. That's even provable.
In theory you'd have to use separate hashes for this selection and other uses. That can be implemented with separate prefixes for multiple uses of the same hash. In practice, if hashing data starting with the public key is nowhere to be found (e.g. because the public key is only hashed as part of a certificate with a non-empty prefix), one is likely OK with just selection from the hash of the public key, as in the question.

No !!! But more good use a offline generators without internet connection and adding small salt for get addition randomness in private key.


Could a collection of data be engineered to encrypt predictably using standard encryption algorithms? Thinking about the rather new problem of Cryptolocker and other crypto-randomware, huge amounts of damage are being caused by malicious actors simply using modern encryption algorithms to encrypt a drive. But this presents an interesting question, and the hint of a possible solution:

Could a collection of data be engineered such that when it is encrypted using a given encryption algorithm, say RSA, patterns in the encryption reveal details that could be used to discover the keys, or at least greatly narrow the search space?

What you're describing is a chosen-plaintext attack.  In this scenario the attacker (you, in this case) creates a specific plaintext for the cryptosystem to encrypt, in an attempt to manipulate it in specific way...In your scenario, to get it to give up information about the key.   Chosen plaintext attacks should not be possible in a semantically secure cryptosystem.  If they are possible, the system is broken, and should not be used.

So, to directly answer your question, no, this should not be possible, and certainly is not generically possible.   There may be specific implementations of crypto-ransomware that are flawed in a way that would make this possible, but you would have to specifically target an attack for that specific system, and it would be useless against any other, including another system flawed in even a slightly different way.

This is a brilliant idea, but I don't know of a way to make it viable.

Presumably, you're thinking you could do something like have a file named "my_photo_1.jpg" where it's been specially constructed so if the first bit of the key is a "1", the encrypted file contains some data revealing that key bit, "my_photo_2.jpg" is structured so that it reveals another key bit, etc.  These are called "chosen plaintext attacks".

So that leaves hope for a vulnerability in the encryption algorithm used by the extortionist.  Unfortunately for your idea, if the extortionist is using AES, the best chosen plaintext attack published so far is an improved variant of the Square attack, which works on reduced (seven) round variants of AES.  Cryptographers study reduced-round variants in order to search for weaknesses in algorithms, but real world applications of AES follow the published standard and use 16 rounds.  While the knowledge gained from reduced-round variants is helpful, they can't be applied in practice to solve this problem.  Yet.

Chosen plaintext attacks are normally not very practical against a real-world adversary, because most traditional adversaries aren't likely to encrypt a bunch of random messages that might weaken their cyphers.  But in this case, where the encryption is hostile and you control all the plaintext, it's a perfect application.  This might spur further research into this field.

--

Unfortunately, this can't work for RSA as you suggest.  RSA uses two different keys, a public and a private key, and only the public key is distributed with the malware.  (The private key is kept confidential on the extortionist's servers, to be sent to the victim only after the ransom is paid.)  RSA is used only to encrypt the random number used as the key to the symmetric algorithm, which is used to encrypt the files.  Chosen plaintext encrypted with the public key doesn't reveal anything about the private key.


secretKey ⊕ (secretKey ≪ 1), is randomness lost? A truly random secret key is run through a cipher

secretKey ⊕ (secretKey  ≪ 1)

is randomness lost? As in, is the computational cost to guess the ciphertext from secretKey ⊕ (secretKey << 1) lower than the cost to guess secretKey?

While bmm6o's answer is correct, I want to give another angle onto things.

The function / transformation you described is linear! Specifically, it is a linear function over the vector space $\mathbb F_2^n$ if you consider $n$-bit inputs. Now this means, that you can apply all the tricks you learned in linear algebra to this transformation, which is characterized by the following matrix for $n=4$ (assuming $\ll$ denotes cyclic shift instead of logical shift):

\begin{equation}
\begin{pmatrix}
x_1'\\x_2'\\x_3'\\x_4'
\end{pmatrix}
=
\begin{pmatrix}
1&0&0&1\\
1&1&0&0\\
0&1&1&0\\
0&0&1&1
\end{pmatrix}
\cdot
\begin{pmatrix}
x_1\\x_2\\x_3\\x_4
\end{pmatrix}
\end{equation}

If $\ll$ denotes logical shift (i.e. fill up on the right with 0 instead of what was pushed out), then simply replace the top-right $1$ with $0$.

As it turns out, if you have the top-right $1$, the determinant of the matrix is $0$ which also means, the transformation is not a permutation, as there's no unique inverse function!

However, if we use the version with a logical shift instead, we always get a determinant of $1$ and thus the confirmation that this indeed describes a permutation (and if we want to, we can also invert it).

To see the above assertions, let's call the matrix $A$ and the value of the top-right bit $b$. Note $A-I$ is the companion matrix to the polynomial $x^n-b$, which means the characteristic polynomial of $A-I$ is $x^n-b$. Now the characteristic polynomial of a matrix $B$ is equal to $\det(B-xI)$, which in our case is $\det((A-I)-xI)=\det(A-(x+1)I)$ which for $x=-1$ yields $\det(A)=(-1)^n-b$, however in $\mathbb F_2$, $-1$ is equal to $1$, meaning $\det(A)=1-b$, which implies that the key transformation is invertible (and thus entropy-preserving) iff a logical instead of a cyclical shift is used for all values sizes of the input and output! Credit goes to Will Jagy for the inspiration (and for a shorter, but more mathy explanation).

If by 'truly random secret key' you mean a sequence of random bits; and if you then XOR (exclusive or) those random bits with an equal amount of cipertext that was derived somehow from that secret key, I would say the result is also random.

This appears to be an example of a One Time Pad, where the ciphertext is the message and the 'truly random secret key' is the key.  Given a random key the same length as the message, the output of a OTP is indistinguishable from a random value.


Retrieve message from rsa ciphertext based on some conditions Assume:

$x = m^{e-1}\bmod n$
$y = m^{d-1}\bmod n$

Here $m$ is a message, $e$ is the public exponent, $d$ is the private key and $n$ is the modulus of an RSA key pair.
Now if I know $e=65537$, $x$, $y$, and $n$, can I retrieve the message $m$?

let \begin{equation}
x*y=m^{e+d-2} \mod n \qquad (1)
\end{equation}
\begin{equation}
m(x+y)=(m^{e}+m^{d}) \mod n \qquad (2)
\end{equation}taking $log_m $ for each from (2) side with respect to $\mod n$, we will have
\begin{equation}
log_mm(x+y)=log_m(m^{e}+m^{d}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)=log_m(m^{e})+log_m(1+\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge log_m(m^{e})+log_m(\frac{m^d} {m^e}) \mod n \qquad
\end{equation}
\begin{equation}
1+log_m(x+y)\ge e+d-e \mod n \qquad
\end{equation}
\begin{equation}
d\simeq  1+log_m(x+y)\qquad (3)
\end{equation}
substitute $(3)$ in $(1)$
\begin{equation}
x*y=m^{e+(1+log_m(x+y))-2} \mod n \qquad
\end{equation}
\begin{equation}
x*y=m^{e-1}m^{log_m(x+y)} \mod n \qquad
\end{equation}
\begin{equation}
m^{e-1}=(x+y)^{-1}(x*y) \mod n \qquad
\end{equation}