Cryptography's random number problem? Sophie Chen at Wired Magazine;

  quantum mechanics could solve cryptography's random number problem

Such machine already exist, but it's too huge and not so fast in order to use it all the time.

Anyway, can it solve the problems connected to randomization and security or it will be still vulnerable?

The title of this article is complete hype. Tip: when a journalist says “X could solve Y”, read “X probably won't solve Y”. Much of the content of the article is hype too.

Cryptography has a random number problem, but the problem is not producing random numbers, and the proposal in this article wouldn't be useful to produce random numbers anyway.

Cryptography does need random numbers for many things. The problem of obtaining random numbers can be divided into three parts: generating sufficient entropy for security, generating a sufficient quantity and quality random numbers for the applications, and actually bringing the random data where it's needed. The first problem is solvable, the second is solved, the third one is where the difficulty is.

To generate random numbers, it's necessary to have a source of non-determinism. A deterministic computer, by definition, is incapable of producing anything random. But there is no need for any expensive machine using quantum mechanics. Classical mechanics or cheap applications of quantum mechanics are good enough in practice. Your PC has a random number generator, if it isn't an antique. Your phone probably has one too, if it's a not-too-old smartphone. If your credit card has a chip, it has a hardware random generator. You can find microcontrollers that cost a few cents (I'm talking bulk prices here) that have a built-in RNG. Many devices lack one (your home router might not have one), but at current prices it's a supply chain and requirements problem, not a cost problem. If you can control how a device is designed, there's no excuse not to include a hardware random generator.

A hardware random generator gives you entropy, but it isn't directly usable for cryptography. It usually has limited bandwidth and biases (no measurement apparatus is perfect). Fortunately, turning an entropy source into a cryptography-grade random generator is a solved problem. All you need to do is to use the entropy source to seed a pseudorandom generator. Any cryptography library has one or more PRNG available.

The real problem with random numbers in practice is getting all the software out there to use them correctly. This is a difficult problem to solve because every piece of software needs to get things right: properly relay the data, don't leave a copy lying around. The operating system driver needs to get it right, the system installer needs to get it right, all the layers of software libraries need to get it right, and the application needs to use the libraries properly. Proper use of randomness is near-impossible to test, so bugs are difficult to detect. Common problems include developers using non-cryptographic random generators when they need cryptographic ones (don't use rand anywhere near cryptographic code!), using a cryptographic PRNG that is not seeded properly (always use your OS's randomness source such as /dev/urandom or CryptGenRandom), using non-random inputs to functions where random input was needed, and systems where the entropy source is not configured properly.

So when the article says

  Eventually, it would be great if they shrank the setup to fit on a chip, says Bierhorst: a random number generator in every laptop, so that nobody ever uses those algorithm-based numbers for encryption again.

that's attacking the part of the problem that doesn't need new technology. The reason people use “algorithm-based numbers for encryption” is that either their device lacks a generator which can be built cheaply using current technology, or that there's a problem in the software. This new machine would not help with either part of the problem.

As for the proposed application of a “randomness beacon”, it's a plausible one, but it's of limited use and difficult to put to practice. A randomness beacon, as the article explains, is useless for most cryptographic applications since it wouldn't be secret. It's useful as an impartial arbiter, for example to assign auditors to auditees, but that can be done with any source of randomness. The fact that the machine itself is more difficult to “hack” than a PC with RDRAND is not all that useful, because the hacking could be done in the reporting and logging system.

Well, I don't think that it can eliminate vulnerability cause it's still new technology that encounter many bugs.
Both the secret-key and public-key methods of cryptology have unique flaws. Oddly enough, quantum physics can be used to either solve or expand these flaws.

The problem with public-key cryptology is that it's based on the staggering size of the numbers created by the combination of the key and the algorithm used to encode the message.


How would I make a decoder agnostic steganographic file? I would like to make a steganographic file that can be decoded on multi-platforms, now & 20 years from now.

I don't want to do so with software that may be out of date when the message decode is attempted.

How would I do this?

I will assume you're referring to steganography in images.

The most important thing would be to use a color space that is likely to be recognizable 20 years in the future. For this, sRGB is a good candidate. It was created more than 20 years ago, in 1996, and it is still the most popular color space in use. It's safe to bet that, in 20 years, it will not be forgotten. You can use traditional LSB steganography to encode information. As long as the color space is preserved, it should be compatible with whatever future software you are using (or compatible software that is easy to find).


Is there a kind of OS entropy pool on Windows systems? I am wondering if Windows provides an equivalent of /dev/urandom from linux ? Or any kind of system entropy pool ?

So far as I know, Windows does not (but you never know, it has an endless series of APIs so anything is possible). However, Intel hardware does. The Microsoft C/C++ compiler (and the Intel compiler) has intrinsics for obtaining a hardware generated random value. That value is obtained by running two circuits backwards so that are unstable. They generate a ton of very random bits which are then cleaned up. Intel has some white papers on it. I don't know if AMD processors have the same thing. I don't have either the name of the functions or the white paper handy, but you can find them with a web search (or, for the functions, look in the header files).


How would a side channel attack be carried out in a real life situation? How would a timing attack against AES be carried out in a real situation? You could not guess the key from the processor's power usage after the plaintext is encrypted, right? And what would you need for this scenario? How long would it take? And if side channel leakage is really such a big deal, why is AES still used for the encryption of classified data?

In hardware, most of the implementations for AES are constant time. My experience is that the current is generally too far into the noise floor to get any real data out; however, I've attacked my AES implementation and a commercial hardware implementation as well with success.  In any software implementation of AES (or ones that I know), I can HALT the system, and dump the core via JTAG and get the keys.

To do a power attack on system, it helps if you know something about the system, but the math you are looking at on a per transistor basis is

$$I_{f,r} =I_{thn}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_g-V_{thn}\right)\right)- \left(V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

$$I_{f,r} =I_{thp}\ln^2 \left[1+ e^{\left[{\left(\kappa \left(V_b -V_g+V_{thp}\right)\right)- \left(V_{b}-V_{s,d}\right)}\right]/\left({2 U_{T}}\right)}  \right]$$

for the N and P FETs respectively.  This model is called the compact EKV model, and if you push through the Taylor expansion, you'll get the subvt and abovevt currents.  Generally, you will see the nFETs to be stronger than the pFETs, which lets you get a feel for what the bit states of the system are.  Having said that, on 14nm SOI (this process is wonderful), my pFETs and nFETs are identical, except for a difference in threshold mismatch.  If you drive the voltage down to get the systems running in subthreshold and control the clock, you can get a really good picture of the circuits.  Once you know the circuits, you can then get the keys.

I use a Keithley 2000 DMM and Keithley 6485 picoammeter that are controlled through MATLAB and I can pretty much get anything I want out of the little black boxes.  (I also have a copper box to isolate noise)

Well, for example you could have 'encrypted' data normally being sent from a client to a server and the server had a list of known 'pre-shared-keys' for all its clients.  Then one day someone comes along and sends it a random buffer.  The server goes through its list of keys attempting to decrypt the random buffer to no avail.  Based on the time it took to decrypt, you could determine how many clients the server had been serving.  Decryption is a computationally expensive task, and there's all kind of things you can do with just how much time it took.

Edit: For example, AES-256 takes 14 rounds.  Multiply that by 36 pre-shared keys and an adversary can very accurately detect what you are doing.

Another recent vulnerability was a web app that was using strcmp() to compare a password from a user-supplied buffer... The way strcmp() works is it compares characters one at a time until there's a mismatch in a character.  So the attackers timed the response over many millions of attempts and character-by-character determined the password. The solution here would be to hash the password and compare the hash.


Guidelines for cryptographic key generation I was wondering whether you know can point me to some general (basic) principles/guidelines one should follow for generating cryptographic keys? I have looked at NIST 800-133, but was hoping for some principles a bit more general and less technical.

Specifically I’m thinking of asymmetric key pair for use of RSA and symmetric key for use of HMAC. For example, I assume that the key should have some randomness to it.

Thank you.

As for the randomness it is simply sufficient to have a cryptographically secure PRNG to generate the HMAC key and RSA key pair. You should make sure that the PRNG is a well known algorithm and well seeded, and you should perform self tests during startup. Having a malfunctioning or incorrectly seeded PRNG is one of the most common reason for vulnerable keys.

The HMAC key simply consists of random bits. You can directly use the output of your random number generator.
The RSA key pair generator requires a random input to find the random primes of half the key size. This generator will likely use a high number of random bits.

With regards to key lengths take a look at keylength.com.

Make sure your hash algorithm used within the HMAC construction is of the same size as the key size.
It is strongly recommended to only choose 8-bit multiples for the RSA key size in order to reduce compatibility issues.

RSA-specific notes:

It is best to choose a public exponent in advance, 0x010001 (65537), the fourth prime of Fermat is a popular - and often the default - choice.
Key sizes of the form $2^x$ or possibly $2^x + 2^{x-1}$ are highly recommended (e.g. 2.048, 3.072, 4.096, 8.192, 16.384 bit keys).
There is technically no need to go for ANSI X9.31 key generation (now practically replaced by FIPS 186-4 with appendix B.3); however, if a private key must run on yet unspecified hardware (as long-term root keys should), it is prudent to use primes with $2^{(n-1)/2}<p<2^{n/2}$ where $n$ is the public modulus size (one of the requirements of these standards).
RSA private keys should contain CRT parameters so as to make it straightforward to speed up RSA private key operations.
Beware that an RSA private exponent may be smaller in size - even in bytes - compared to the modulus, this is no reason to worry (unless it is much smaller).
Beware that RSA key generation can take a long time compared to other cryptosystems, including asymmetric; and this time varies widely and without firm upper bound from one key to another. This is a classic issue for mass production of devices with internal key generation, or when defining a maximum delay for supervising software.

For optimum assurance you should use a FIPS or Common Criteria validated software and hardware component (HSM, smart card) for key generation, key storage and key usage. Beware that computer memory may not always be secure. Key generation is the easy part, correct key management is much harder.

Efficient RSA key generation algorithms can be found in http://dx.doi.org/10.1007/11894063_13


Question regarding multiple SHA-256 rounds on a Bitcoin Brain Wallet passphrase… I am attempting to come up with a way of memorizing a seed that could lead to any number of brain wallets for bitcoin.  I need multiple wallets because a) I don't want all my eggs in one basket, and b) I want to be able to import small amounts from time to time.

Let's say I came up with a passphrase, and assume it's long enough to be secure.  If I was to concatenate a value at the end of the phrase, and increment this each time, it could lead to an infinite amount of brainwallets, ie.

SHA256(passphrase.'1')
SHA256(passphrase.'2') etc...

The only disadvantage I see with this approach is that if somebody, at some point in the future was to stumble upon the seed to the private key (keylogger, brute force etc.), it would be trivial to access all the other wallets.

So I was considering using two rounds of SHA256 instead, but adding a second phrase to the hash value of the first round, like this -

SHA256(SHA256(passphrase.'1').'second phrase')
SHA256(SHA256(passphrase.'2').'second phrase')

I would the use the resulting hash as the input to the brain wallet.

This would mean concatenating ASCII text to the hex of the first SHA256 operation.  The reason that I don't want to use the actual numeric value is that I need something that can be done easily over a unix command line (I'm not sure how to do 256-bit math operations).  I don't want any custom software involved because there's not that much room in my brain. This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets.

I'm worried that if I use the ASCII text to generate a second key, I'm somehow compromising the SHA256 process and making everything less secure.

Is there reason for me to be worried or is my approach secure?

This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets.

By Kerckhoffs's principle, you should assume that the adversary already knows the algorithm, and the only thing unknown are the secret keys – in your case, the passphrases.

Therefore, the adversary by definition knows that you are generating the brain wallet passphrases by $w_i = h( h(k_1 || i) || k_2)$ (where $h(x)$ is something like $Hex(SHA2(ASCII(x)))$. So the only things your attacker has to "reverse-engineer" are the two passphrases $k_1$ and $k_2$.

For now, SHA-2 is assumed to be preimage-resistant, which means that the best way of finding $k_1$ and $k_2$ is to simply guess them and see if the result matches any captured output (or, if there is no captured output, see if the result helps unlocking any of your wallets).

Generating different $w_i$ with the same passphrases does not significantly help the attacker to break it, but if he breaks one, also all the others are broken. The encoding (hex, ascii, anything else) doesn't matter for the security, too.

If your two passphrases are good (i.e. having more than 100 bits of entropy together), an attacker has little chance of successing with this brute-force.

If your passphrase is bad (and this includes all passwords with less than 10 characters, or longer ones which can be found in dictionaries), your derivation can be brute-forced easily. Also, if other users are using your scheme too, and by chance have the same password, they'll have the same $w_i$s, which might be usable by an attacker.

Your scheme could be made better by using a slow password hash, and including a salt input which is unique to you, like your email address. The output of this slow hash you can then process with the counter to get the actual $w_i$.

If the attacker has a key-logger and captures your passwords, everything is already lost.


One Time Pad Key Distribution For multiple OTP keys, why not do this:

Key = Hash[(EC)DH Shared Secret + Counter]

The counter will increase per message, and the output of the hash will be random for each new unique input into it. What are the problems or weaknesses with this design??

EDIT:
For clarification: both parties will have the shared secret from an ECDH exchange, random numbers from Pythons os.urandom for generating the ECC key

This principle is commonplace, it is a key derivation from a shared secret. The academic thing to do is to use a Key Derivation Function or a MAC where hash of a concatenation is used, perhaps
$$\operatorname{HMAC-Hash}\;[\;\text{Key}=\text{(EC)DH Shared Secret},\,\text{Message}=\text{Counter}\;]$$

We call the output a derived key, and it can be a one-use key.

I would not call it a One Time Pad key, even if it is used only once to mask some payload with XOR, because the usual assumption is that a One Time Pad (key) is truly random, and this is only pseudo-random.

The main problem is that it's not truly random, and therefore unsuitable for a real-by-definition one time pad. Addressing your comment which forms the crux:-

  The shared secret will be calculated from keys that were generated using pythons os.urandom function, and whilst not truly random, they are unseeded and generated from many different sources that are unpredictable.

Rewriting your formula, you have an iteration as $  k' = \text{HMAC}[  seed || c ]   $. Even without maths we can see that it's not truly random, as I just wrote it down algebraically. No matter how $seed$ is generated, it becomes fixed when incorporated into your formula.  You are then simply incrementing counter $c$. And as for "each new unique input": Unique yes, but entirely predictable.

As $c$ increments, the cumulative output will become longer than the program that created it.  That breaks the fundamental definition of Kolmogorov randomness, and breaks the perfect secrecy paradigm of the one time pad.

When ever you describe the output of a OTP generating process, it must be longer, not shorter, than the pad itself. Even if only by a teensy-weensy little bit, like a print statement or full stop. It's another way of saying that you can't write down a OPT in algebraic terms. What you have is a mutually agreed upon pseudo random generator.

The Wikipedia article on Kolmogorov complexity is pretty good.


Losing entropy after re-hashing a hash Suppose you have a string AAA that was hashed with SHA1 to produce 606ec6e9bd8a8ff2ad14e5fade3f264471e82251.

If I rehash 606ec6e9bd8a8ff2ad14e5fade3f264471e82251 10x times with the same SHA1 algorithm, would the entropy keep on decreasing?

If so, would it ever reach a dangerous level to a point where AAA could be recovered?

P.S: SHA1 was just an example. Ideally, I'd use BLAKE2b or a SHA3 candidate.

Let's assume your actual input/output has entropy (which it doesn't for a given string or output hash value).

  If I rehash 606ec6e9bd8a8ff2ad14e5fade3f264471e82251 10x times with the same SHA1 algorithm, would the entropy keep on decreasing?

Yes, but by ever so tiny amount. Hashes are designed so that every bit is dependent on all the bits of the input. Hashes do get into so called cycles after iterating quite a few times, showing that entropy can and does decrease. It is however unlikely to influence practical situations.

The initial hash will of course extract the entropy into a maximum of slightly less than 160 bits.

  If so, would it ever reach a dangerous level to a point where AAA could be recovered?

That's of course nonsense statement; the amount of entropy doesn't influence the one-way-function property of a cryptographic hash function at all.

Let's take an extreme and assume that, after a while, all many messages will generate the same hash (a next to impossible situation in itself). Then the (Shannon) entropy will be lowered. So in this situation it becomes more likely to generate this iterated hash by trying out different messages.

However, if you try and revert it you will find many messages instead of one, and it is impossible to detect which one is the original input message. So if anything, you've just made the function harder to reverse.

As example: I've "hashed" all bits of a fully random message into a single bit by XOR-ing them together. Entropy is hugely decreased to a single bit worth of it. Which message did I use to create this one bit of entropy, even if you (get to) know it is 0 or 1?


Is there a way to make RC4 (ARCFOUR) secure, or is it completely broken? I need a method to authenticate a process with another in order to establish interprocess communication between them, to prevent malicious processes from trying to hook onto the system. Currently I just send a password in plaintext between the two processes and the host process just performs a string comparison with its copy of the password, and will disconnect the connecting process if they don't match. It was fine when I was limited to connecting each process on localhost, but obviously this is not secure if someone just happens to have access to a network between each process and could sniff the packets. Do note that I only care about encryption for the password exchange and I don't really need it to secure the communication.

So basically I need a encryption algorithm that doesn't need to protect its contents well but does need to protect its key, and needs to be as fast as possible with minimal RAM usage and I/O overhead. Yes, data exchange is more CPU-bound than I/O bound since the two processes will be doing loads of calculations and they most likely will be connecting through localhost. Now, I came across RC4, which has a throughput of over twice that of AES-128, but it is evident that it has some weaknesses and I have a lot of questions about how to implement it in a secure way.

Well first question - it's in the title. Is RC4 completely broken and should be avoided? I hear a lot of "it is secure if properly used" and then a lot of "use of RC4 is discouraged."

I was planning to keep the plaintext password on both processes and have them SHA-224 hashed, and concatenate the hash with a 32-bit IV as a 256-bit key for RC4. Are there any security risks with this approach? Perhaps I could then hash the concatenated IV and hashed password with SHA-256? I'm well aware that WEP was cracked because it used a 24-bit IV, but a 32-bit IV has over four billion more unique values. Should I avoid incrementing the IV after each packet like WEP?

And when it comes to RC4-drop[n], what is a reasonable value for n? 256, 512, 768 bytes? How would you implement drop n on a library whose only public operation is encrypting a byte array - pass a byte array of length n after the engine is initialized with the key? Would that mean you would have to basically process n empty bytes after every time you change the IV (which happens after every packet)?

Sources: http://www.rsa.com/rsalabs/node.asp?id=2009

EDIT: after reading all these excellent responses, I realized how ignorant I sounded about the whole subject. I had no experience with cryptography before this day, and I only was able to read about RC4's risks from the limited Google results that I could barely follow. thank you to everyone who has been patient with me!

Correct me if I'm wrong, but I believe a better solution is to either use AES (which is not slower because re-keying RC4 after each packet is expensive) or an universal message authentication code. I can easily work with AES, but my understanding of MAC is a bit shaky. An IV is only secure if the update sequence is randomized and unpredictable, meaning I would have to send a 128 bit IV for every message that is sent, which can add a 400% overhead to the short, 4 byte packets that are commonly sent by my application. HMAC can add more than twice that amount if SHA-256 is used. I am going to have to investigate this matter further.

A few observations:

RC4 suffers from related key attacks. This means your idea of concatenating a 224 bit key and a 32 bit IV is not a good idea. You should rather use $\operatorname{SHA-256}(Key\mathbin\|IV)$
Remember that a (Key, IV) pair must not be reused, ever.
A 32 bit IV can work if it's a counter, but IMO such a scheme is unnecessarily fragile. I'd rather generate a new, random 128 bit value for each encryption.
Even with dropping, RC4 is still a bit biased. This can allow password recovery if an attacker can observe a few billion communications.
You don't protect data integrity. For example an attacker might keep the encrypted password intact, but change the rest of the message. I don't understand your problem well enough to know if that's a problem.
There might be replay attacks, where an attacker repeats an earlier message fully or in part.
Your assumption that RC4 is faster than other ciphers isn't necessarily true. On many modern systems AES is really fast. There are also other modern stream ciphers, such as Salsa20 which are fast and much stronger than RC4.
RC4 has costly initialization. So its only fast if you need to initialize it rarely. In particular if you reinitialize for each packet, its performance will certainly drop below AES.
Do you really need a cipher in the first place? You might be better off with a MAC. It seems like you're interested in authentication, not confidentiality. Universal MACs can be really fast.
User Passwords often have low entropy, so you need to strengthen them before using them as a key. Strengthening them is computationally expensive, and is done using KDFs, like scrypt or PBKDF2.
Consider using a high entropy key instead of a password.
If you use a constant key hardcoded into an executable, those executables may never run on untrusted machines. Else an attacker could simply extract the key out of the executable.

In short:

The weaknesses in your protocol are likely much more severe than the weaknesses in RC4.
There is little reason to use RC4 in a new protocol. There are fast and strong alternatives.

My answer provides some sort of fix to the original RC4 construction, and provides an answer to the OP better than just criticisms of RC4 without solutions.  I call it RC4U.

THEORY

The original RC4 suffers two forms of weakness in it's pseudo random key stream.  They are long term and short term biases.

The short term bias reflects the inadequacies of populating the state array from the key.  RC4U eliminates the original KSA part totally.  The state is generated directly from any key by a fully extended 8 bit Pearson hash producing a 256 byte derangement.  This derangement becomes the state.  My replacement should not be amenable to the development of Finney states.

Long term biases are extremely small.  They are equivalent to biases seen in any decimal expansion of pi, and there is no practical attack using this vector.  However, RC4U eliminates long term biases by appending a Von Neumann extractor directly after the PRGA component. The resultant output is therefore a bit stream, rather than a byte stream.  Byte reassembly is required to use the output as a cipher.

PROS

No short term bias
No long term bias
Any key of any length
No padding required for key
Likely that there are no Finney states
Extremely simple to understand
Extremely low resource requirements, suitable for Arduino /PIC
Perhaps much faster than Arduino AES /ChaCha library

CONS

Heath Robinson health working
Requires a fixed 256 byte derangement array in the code
Much slower than vanilla RC4
Poor reputation
Probably poor choice of name

This may be home brew crypto but we all know that high reputation members write it anyway.  It is proven to work out to 40GB of output, and theory suggests it working further still.


NIST 800-90B /Non-IID track - min-entropy result > 8 for 8-bit symbol I'm conducting an analyisis of noise sources based on the NIST 800-90B Non-IID track.
Accordingly, I applied the non-iidmain.py script on a datarecord, which delivered the following output:

reading 1000000 bytes of data
Read in file ../some_data_rec.bin, 1000000 bytes long.
Dataset: 1000000 8-bit symbols, 256 symbols in alphabet.
Output symbol values: min = 0, max = 255

Running entropic statistic estimates:
- Most Common Value Estimate: p(max) = 0.00424421, min-entropy = 7.88029
- Collision Estimate: p(max) = 0.0119504, min-entropy = 6.3868
- Markov Estimate (map 6 bits): p(max) = 9.06705e-222, min-entropy = 5.73662
- Compression Estimate: p(max) = 0.00790364, min-entropy = 6.98327
- t-Tuple Estimate: p(max) = 0.006, min-entropy = 7.38082
- LRS Estimate: p(max) = 0.00389867, min-entropy = 8.0028
....

What I am wondering is the output for the LRS Estimate which delivers a min-entropy of 8.0028.
The symbols in alphabet are defined at 256 i.e. one byte.
So how is it possible a single symbol at one byte/8 bit is able to deliver more entropy than it is able to describe?
I expected the maximum entropy value for one byte should be 8 bit?

There are three separate reasonable questions here.

What does LRS Estimate mean?
Does the software compute it correctly?
Are stupid entropy estimation tools like this useful for your goal?

The setting is that we hypothesize specific families of generating processes for the data that came out of a black box.  The families of generating processes are all quite simple-minded.  For example:

A gremlin in the black box rolls a 256-sided die with unknown face probabilities $p_i$ independently for each octet in the string.
A gremlin in the black box emits outputs from unknown states by a hidden Markov model with unknown emission probabilities $e_i$ and transition probabilities $t_{ij}$.

Each of these models has a certain measure of min-entropy that is determined by the choices of parameters, such as the $p_i$.  The NIST tool, like any other entropy estimation tool, estimates the min-entropy by fitting parameters and evaluating or estimating an upper bound on the min-entropy in the specific case of the model with the parameters it fit.  Obviously 8.0028 is an upper bound on the min-entropy of an octet.  How do we get there?

To address (1), what the LRS Estimate means, the LRS estimator posits a generating process something like this:

A gremlin inside the black box has a hat with $d$ strings of varying lengths on it, the $i^{\mathit{th}}$ string having $n_i$ copies.  It shuffles the hat and draws a string out to add to the output; then it repeats.

The estimator works by guessing a few strings that might be in the hat based on repeating and nonrepeating contiguous substrings in the data, and uses the frequency of those strings as an estimate for the probability that they will occur.  (The complete details of the computation are in NIST SP800 90A, §6.3.6.)  From those probabilities it yields an estimate of the min-entropy using the standard $-\max_i \log p_i$ formula.

It doesn't consider all contiguous substrings in the output (there is a combinatorial explosion of them), so it ignores some of the probability space and thus slightly underestimates the probability of each substring it does consider, which has the effect of slightly overestimating the min-entropy—which would explain why it seems to produce an entropy rate of just over eight bits per octet.

Now, to address (2), does the software implement it correctly?  That's a question for codereviews.se, and maybe for stats.se if you want to make sure that the posited model and the estimator for the probabilities is sensible and what was intended by NIST.

Finally, to address (3), whether this is useful for your goal, the answer is not very.  It will detect certain families of patterns in your data, if those patterns appear.  High estimates like the LRS Estimate in your sample are not useful: they just mean that this particular pattern didn't appear.  Low estimates suggest that someone at NIST who wasn't even thinking about your particular noise source could predict its output with pretty good chances of success.  That's usually bad sign.  So don't worry about the slightly >8-bits-per-octet estimate for LRS: worry about the ~5-bits-per-octet estimate with a Markov model!  Does your device alternate between internal states with somewhat more predictable emission probabilities?

What you really need to do is study the physics of the object in question from an adversary's perspective, and try to find the best way to predict the output knowing how your particular noise source works.  Then compute the entropy of that model.  If it's higher than all of the NIST estimates, either you had a lucky sample or someone at NIST who doesn't even know what you're working on was better at studying your noise source than you are.

I feel your pain.  Have a look at How to interpret the entropy results for a NIST test file?.  This question was terribly received (-3 votes) yet no convincing anwer was offered as to the aberrations in entropy for the  $ \pi $ file.

The test suite clearly presents it's output in bits/byte. I got Longest Reapeated Substring Test Estimate = 8.5665  and   had to scratch my head. Clearly this is impossible. And it poorly compares with Compression Test Estimate = 0.0828647.  That is two orders of magnitude out.  The spelling mistake is also worrisome.

The assessment formulae in  Recommendation for the Entropy Sources Used for Random Bit Generation are probably good, but I can only conclude that this software is pants.  Was an [assert] statement too much to ask?  Other than the acronym NIST appearing in the title, there is no guarantee that the tools work reliably.  The software specifically states that there is none. You'll also find that the C++ implementations give wholly different values from the Python ones.  The entropy must not be Pythonic.

I conclude that this software is unreliable, and therefore unsafe for cryptographic use.  If you study many papers on entropy generation and true random number generators, you will be hard pressed to find a single instance of this software being used.  I've not found any references.
 That's strong anecdotal evidence against it.  I've deleted it and will be using strong compression tools for entropy measurement instead.  They're ideally suited to finding correlations as that's their raison d'être

PS. I also asked Do the NIST tools on GitHub measure entropy reliably? but no one was interested.

PPS. Have a look at my answer to How to interpret the entropy results for a NIST test file?  In the papers and links, you'll find references to entropy rates of 11 and even 21 bits/byte.  The Markov model likes to output 21 when it gets confused.  This just shows that no rigour was used in the code implementation. The clear conclusion of independent findings on 90B is that they are wholly unreliable and grossly inappropriate for real world entropy.


Does this guarantee a unique 32 bit Hash? I came across some source code that loosely does the below in order to achieve a 32 bit hash.

The input string is passed through MD5 to get 16 bytes Hash (as usual). Then the 16 bytes are split into 4 byte words . Each of these words are $\oplus$ with each other in order to get a final 4 byte word, this is considered as a 32 bit hash.

The application does not really care about security in sense of pre-image resistance etc. but all it wants is Collision Resistance.

So, does the above guarantee no collisions (any better than birthday-bound)? Of course it depends on the input string's entropy etc., but given that we don't know before hand what possible strings could be passed as input: how do we analyze such scheme for collisions?

As far as I understand, the scheme is:

$$MD5(x) = a_1||a_2||a_3||a_4 \, \, \Longrightarrow \, \, H(x) = a_1 \oplus a_2 \oplus a_3 \oplus a_4,$$

with $a_i$ 4-byte/32-bit words.

Obviously you can't guarantee a unique 32-bit hash from an unbounded domain, due to the pidgeonhole principle. Neither can you make finding collisions infeasible, since $2^{16}$ MD5 invocations takes a few seconds if that.

If MD5 was an ideal 128-bit hash, it wouldn't matter whether you take the first 4 bytes, XOR the 32-bit words or anything else. All of them would be ideal 32-bit hashes. However, it isn't and you can find collisions in about $2^{33}$ operations. That doesn't directly lead to an attack on this, because it's slower than brute force, but it's possible it could be extended. There's a chance the XOR could make such an attack slightly harder or easier than truncation, but it really doesn't matter with a 32-bit hash since brute force is sufficient.

Assuming you don't let an attacker control the inputs (since that would be totally broken), the question isn't about the collision resistance, but pseudorandomness of MD5. MD5 is still thought to behave like a PRF in the sense that if the input strings are chosen "randomly", the output is uniformly random as well. (Which is why HMAC-MD5 is secure.) XOR doesn't affect that, so you should have the 32-bit hash behave like a PRF as well.

So, with inputs that aren't under the attacker's control, you should see collisions at the birthday bound. No sooner or later, other than what variance you expect with a 32-bit hash. However, there's no real benefit to the XOR, so you might as well just use the first 4-byte word.

Use something more collision resistant like SHA... I can't find any hashes that are completely collision proof, but sha at least decreases the collisions...


How useful is NIST's Randomness Beacon for cryptographic use? NIST have just launched a new service called the NSANIST Randomness Beacon. It has been met with some initial skepticism. Perhaps the cryptography community would have used it before June 2013 when NIST had a trusted reputation. At first I thought it was a mistimed April Fool's joke, however it actually appears to be an ongoing serious project.

I am intrigued as to the potential uses of this randomness beacon and serious cryptographic applications that this service could legitimately provide, given that this service is potentially hostile and probably under adversarial control. I am assuming that using it for private cryptographic keys is out of the question.

I'll quote a few things from the specification in the Uses section that raised an eyebrow for me:

  First, the Beacon-generated numbers cannot be predicted before they are published. Second, the public, time-bound, and authenticated nature of the Beacon allows a user application to prove to anybody that it used truly random numbers not known before a certain point in time.

However this feature can not be true because:

  The Beacon will broadcast full-entropy bit-strings in blocks of 512 bits every 60 seconds.

So while normal users won't be able to predict the random numbers, in that 60 second window someone with a privileged access inside the NIST (or NSA) could easily have access to the next random bit-string a full 60 seconds before it has been "published". If this adversary with insider access were to become one of the regular users of an application using this beacon they would have knowledge of random numbers before other users providing a significant advantage depending on the type of application.

Given this information, what actual safe, fair and useful cryptographic uses could this potentially compromised beacon provide?

I would characterize the service as similar to a trusted time-stamping service. Except they do not do the time-stamping, but just provide the "key". This allows a user to decide what do to with it, such as using it as a private key to sign something, or an HMAC key, proving the signature is "not older" than the timestamp. If the signature is published to a verifiable record, it can then be proven to be "not newer" than the date of the record. If the gap is short enough, the applications for a signature or hash with a provable time period of creation are numerous. It can also be used an an additional input to a two factor authentication system (I think this is the most useful).

Other sources of true randomness are available, but having one for free is better if you do not need to use it for a cryptographic purpose. Having a way to prove or audit your random source is beneficial from a business or political perspective, as in the examples for the Unpredictable Sampling application link.

Other non cryptographic uses of random values could be used to prevent bias for things like "random screenings" of airline passengers, jury selection, and collection of census data. I doubt this will be implemented, but one can hope.

Service Security

We can make three types of assumptions from a subterfuge perspective.

The numbers are truly random, but are provided to the NSA in
advance (or are simply delayed for public view).
The historical record can be modified by the NSA or NIST, since
they have access to the private key.
The numbers are not truly random.

Not being random is something that would need an audit or some kind of analysis to prove. I doubt they are not random, but that does not mean that a non random value could be used for say, a single output.

The 2nd is unlikely to occur, since acceptance of the service would only be likely if you could verify the record from other parties, which one does trust to have been unmodified. Also since the output is based on the prior outputs, the entire chain would need to be tampered with.

The 1st is much more likely, the outputs could be delayed for a substantial amount of time, even days, and you would not know unless the entropy source can be audited by a trusted party. Since the signature is generated using a known future time code plus the current and prior values, it is trivial do to this without detection. Seeds could potentially be chosen at random and tested to give an output with a specific bias, but a massive amount would probably need to be tested to give appropriate output, at significant cost to the attacker (each requires an RSA sign and a hash, and the guarantee that the one specific value will be used by the target).

Given this, one would probably use these numbers only for uses where that would be highly unlikely to occur. Most applications would fall into that category. Anyone who needs these type of numbers for a use that is likely to be manipulated by an intelligence agency would just build their own entropy generator, which is not too difficult. If nobody is using the service for something the NSA would want to tamper with, the NSA wont tamper with it, it is simply too expensive and there would be no gain.

The only concerns I have from a cryptographic perspective are how the numbers are actually generated. The page does say that the output is full entropy and the output is 512-bits. It may be safe to assume that the "Seed Value" is actually the hashed output of the entropy source/DRBG, as the XML schema file says the "Output Value" is the SHA-512 hash of the signature, which I have verified to be the case. This means the output value is computationally infeasible to predict without all the input values AND the private key.

The specifics of the seed number are not listed, one can only assume that the samples are passed through SHA-512 to give this, but the size of the sample is not listed. Since the Beacon page specifically lists compliance with SP800-90, the entropy sample should be at least 888 bits, but there is nothing to confirm that, and no detail on the actual method of output generation, such as the DRBG used (very very important), and the reseeding interval.

Other Security Concerns

At this point I will assume the service is still in beta prototype, as their XML schema file references values that are not given, such as randomValue and previousHashValue, which are most likely supposed to be the seed value and previous output.

The other unknown is how the signature is generated, since there must be someway to verify it, but no public key or any detail at all regarding the type of signature is listed. It is a 2048 bit value, so RSA is quite likely, possibly even generated by the same private key for their SSL traffic. I would hope that is not the case, when the key expires later this year, it may be difficult to verify previous outputs, as the old public key would need to be found.

Also, the page is encrypted using CBC mode using TLS 1.0, which means the connection is potentially vulnerable to tampering by a 3rd party while in transit. This type of service should be as invulnerable to tampering as possible with current technology and standards, and is not. This is not a problem with the service itself, just in how the service is accessed. The page accesses an XML formatted entry using AJAX on the same server, secured with the same protocol and key.

Acceptance is also dependent on public trust in the security of SHA-512, the methods used to measure the unpredictability of quantum behavior, and the methods described in SP800-90A for turning those measurements into random bits. SP800-90A is the publication that describes Dual EC DRBG....

Updates to the service as of March 2018

As mentioned above, the private key for their SSL traffic expired in 2014, at that point they got a new cert, and have since posted the specific certificate used to sign beacon data. That cert (2048-bit RSA, SHA256 hash) was valid for 3 years, and expired May 7th 2017. It is downloadable for verification of prior data, and they list the new public key used to sign current beacon data, but it is not a certificate and thus not signed with a root cert.

The new public key is 2048-bit RSA with 65537 as the exponent, same as in the previous certificate.

Their SSL traffic is now secured with TLS 1.2, the specific ciphersuite used is TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA. That cert has a 1 year validity, and is also 2048-bit RSA.

Their schema has been updated, and no longer references randomValue or previousHashValue. The XML records from the beacon match the schema correctly.

The service is still listed as a prototype, and they note that a new version of the beacon is in development, however there have been no updates since the last page edit on May 13th 2014.

Updates to the service as of October 2019

In June 2018, the service officially left prototype status and entered beta, using the "new version" I referenced earlier, which is now referred to as version 2.0. The new XML Schema file is fairly well documented. It appears the new beacon went online July 23rd 2018.

I was able to determine that the certificate used to sign the beacon output changed on pulse 502025, which occurred on August 16th 2019. The status of the pulse correctly specify a gap in the beacon output occurred (it was 3 minutes), with a code of 6 for certificate change, although this code is not listed in the XML Schema file. The prior certificate actually expired on January 11th 2019 and was used for an additional 7 months 5 days.

The current and prior certificates are easily obtainable from the service interface. Both were issued by DigiCert Global CA G2. The new public key is 4096-bit RSA with 65537 as the exponent.

Their SSL traffic is still secured with TLS 1.2 on my system, the specific ciphersuite used is now TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384. That cert has a 1 year validity (expiring November), and is still 2048-bit RSA. It is also issued by DigiCert, but is a common web server certificate for 14 separate NIST subdomains, including NVD and CSRC.

In May of 2019, they published a draft reference for randomness beacons, of which the version 2.0 service is an implementation of, as Internal Report 8213. This is an extremely detailed report of the design and implementation of the beacon system, and includes a security analysis with multiple threat assessments.

There are a few important changes with version 2.0 that are worth mentioning, the first is that they now have published block diagrams of how the system works, make note that although RNG3 is listed as quantum, the beacon project website specifies "We may soon integrate in the NIST Beacon a PML-developed quantum RNG (identified in the figure as #3) based on photon detection", implying that RNG3 is not currently active:

The next important change is how the hash chains are built, and the addition of the skip list. I have not verified the complete operation of the skip list, but it would appear to use the 1st hour/day/month/year as the anchor point for a hash chain, so it is much faster to audit the current beacon to the start of the chain, which could be years long.

Now instead of going back half a million hashes to go back a year, you simply go back to the start of the hour, then back by hours to the start of the day, and so on until the chain is verified back to the first minute of the first hour of the first day of the year, with a maximum of 124 verifications to go back to the beginning of the current year.

So to verify pulse 502025 (Aug 16th 2019, 14:14 Z) against the start of the month pulse of 479573, you skip back 15 minutes to 502013, then in 14 skips of an hour (60 pulses) back to 501173, then in 15 skips of a day (1440 pulses) to 479573, for a total of 44 verifications, compared to 22453 without the skip list feature.

The final point of note is that this is not the only implementation of the version 2.0 beacon technology, there are services run by the University of Chile and government of Brazil. In addition to a hardware RNG, the Chilean beacon uses entropy sources gathered from seismic measurements in Chile, a stream from a local radio station, a selection of Twitter posts, and data from the Ethereum blockchain. Brazil actually runs multiple beacons, including their primary which uses a photonic quantum TRNG, as well as a combination beacon which also includes the outputs of the Chilean and NIST beacons as sources of entropy. The output of the Chilean beacon is also one of several inputs to Cloudflare's own beacon, which is not based on the NIST design or API.

At this point, the design seems sound, and if they fix the cert issues and get RNG3 active (maybe it already is), this and others like it do appear to have many uses, although cryptographic use may not be one of them, except as an additional source of entropy and not as a primary source.

To express it mathematically, $ usefulness(NIST Randomness Beacon)  \approx 0 $.

This is a screen shot as of 14/4/2018 00:19 UTC+0100. Sorry it's rather large, but that's necessary.

I don't know how long it's been frozen as I can't tell what timezone the server's on, but it's at least the 30 minutes I've been typing this. It's actually yesterday for me.   That's >30 beacon bongs, pings or whatever they call it. Taken in combination with the certificate debacle, I   would be very hesitant to build a legal time stamping service based around this. I wouldn't want my business credibility to be dependent on a duck's plaything.

I fully appreciate the work in progress status, but Google's Gmail was in beta for half a decade and pretty usable for most of that time. This service relies on continuity. Randomness and reliability cannot be separated here.  This reliability issue is clearly in addition to those cryptographic ones in the other answers.

To further undermine credibility, it's down again as of this edit.  This time the entire block chain has disappeared so nothing can be verified.


Would using a one-time pad multiple times with some conditions be safe? I understand why |one-time pad|=|message| using a normal one-time pad, but I don't understand why for perfect secrecy it must alway be that |key|>|all messages exchanged|.

What if, for example, I had |one-time pad|=n*|message| with n>1 and then used it for (for example) 2n messages with a random starting point (itself encoded at some point in the message with a 'normal' one-time pad which given it's a single number could be simply be the first part of the original OTP)?

I'm pretty sure there must be something that doesn't work, because if this was still perfectly secret then a one-time pad could be used to generate infinite one-time pads which would be useful but impossible (wouldn't everybody be using it?). So, where does the perfect encryption of the one-time pad end?

For perfect secrecy of any cryptosystem, it must hold that |key|≥|all messages exchanged|.

Proof by contraposition: assume |key|<|all messages exchanged|, and there exists a deterministic decryption procedure of all ciphertext exchanged and key to all messages exchanged. Knowing all messages exchanged, an infinitely powerful adversary can exclude some value of messages exchanged as impossible, violating perfect secrecy; all s/he has to do is apply said procedure to decipher the given all ciphertext exchanged with all the possible values of key, and rule out as impossible any value of all messages exchanged not obtained for any value of key. The hypothesis |key|<|all messages exchanged| implies there will exist at least one impossible value, by a counting argument.

In the case of the repeated OTP in the question, there exists attacks that can be performed by an adversary with very limited computing ability, and enough knowledge about the plaintext.

For example, assume that all the messages are long, random, and known entirely except for an unknown bit in the middle of the last message. It becomes likely and easy to find most of the key, and the starting point for all messages, and from that the single unknown plaintext bit.

There are more clever attacks that work with less hypothesis on the plaintext (like: it is mostly English words), and remain feasible in practice if there is enough ciphertext.

If we violate the 1-time rule by a single re-use, the resulting effective key is half the length of the plaintext, and no more random than plaintext hashed against plaintext is. The cryptanalyst can XOR the 2 encrypted strings together, and thereby get the same result that XORing the 2 plaintext strings together would produce.

Example:

P: 01000001,01000010 (plaintext string -- dec 65,66 -- ASCII A,B)
K: 11101100,11101100 (repeated random string -- dec 236,236 -- ASCII ∞,∞)
P ⊕ K =
E: 10101101,10101110 (encrypted string -- dec 173,174 ASCII ¡,«)

E1 (E 1st ½): 10101101 (dec 65 ASCII ¡)
E2 (E 2nd ½): 10101110 (dec 66 ASCII «)
E1 ⊕ E2 = R: 00000011 (dec 3 -- ASCII Bell)

P1 (P 1st ½): 01000001 (dec 65 -- ASCII A)
P2 (P 2nd ½): 01000010 (dec 66 -- ASCII B)
P1 ⊕ P2 = R: 00000011 (dec 3 -- ASCII Bell)

It's no longer an unbreakable cipher.


Two mutually untrusted parties want to exchange data: how to ensure each one gets the data it needs? I am trying to come up with what could maybe be a novel algorithm for an application I am writing. Client A has a file fA. Client B has file fB. Each party is untrustworthy and will try to rip off the other party. Client A wants the fB and client B wants fA.

How can I make an algorithm were it is not possible for them to screw the other player.

For example:
    A encrypts fA and send the file to B.
    B encrypts fB and sends it to A.

Now, both A and B have an encrypted version of the file they want.
How can they both share the decryption key at the same time... or what?

Is this even possible? This is breaking my mind.

Since each client will try to rip the other party, Client A cannot send the file fA to client B and expect client B to send back its file. If client A sends it first "with no guarantees", client B will simply run off with the file.

In real life a person holds the pot in one hand, the other holds the cash in the other. They both trade each hand at the same time. The guy with the cash now ends up with the pot and vice versa. How can I do something similar with computer bits. (client A and B are on a network at different locations).

EDIT: Please note that each party has a hash of the file they are supposed to get. Therefore, the parties cannot send a junk file to the other guy whit-out him knowing. A trusted third party will provide the hash.

It can be done, but the algorithm is a bit complex and the hashes have to be specially constructed. The basic idea is this:

What you need is a way for each party to give the other a verifiable "clue" that reduces the search space for the possible file, say by a factor of 10. As soon as one party stops giving clues, the other stops giving clues as well. So a deceiver can, at worse, give you one fewer clue than you have given him.

That means you may have to do 10 times as much computation as he does to recover the file, but that's not enough to make the task possible for him but impossible for you.

One way to do this is to encode the file such that every byte is needed to recover any byte of it (for example, you can do this with no waste of bytes using an erasure code). Then you can make the hash actually include four hashes. One is of the entire encoded file. The next is of the file with the last two bytes missing. The next is of the file with the next three bytes missing. The last is of the file with the next four bytes missing.

You can then exchange all but the last 10 bytes of the file with the other side and validate this by hash. Then you can exchange the next four bytes and validate. Then the next three, and so on through the four rounds. At worse, a deceiver leaves you with 256 times more work to do than he has. So if he needs the file within a day, at worse you get the file within 256 days.

You can switch to nibbles and make this 16 instead of 256 at the cost of more hashes and more exchanges.

Usually a combination and public-private keys (RSA) works. But your constraints are so strict, I don't think any solution would work. At the end of the day A can send any junk file instead of fA and there is no way B can know it. Somehow if it is possible for B to know what A has sent is in fact fA then probably I can come up with something.

EDIT: I take that back. Even if you can verify the authenticity of the file, it is probably not possible to solve your problem.

If you synchronously exchange keys:

Let us assume you exchange keys simultaneously at an instant. Even then, since you can take back key you sent, it is not possible to assure no fraud at each end
If it is not possible to exchange keys simultaneously, ..... then forgetaboutit!

So the only solution is escrow.


Applications of machine learning in classical ciphers? Machine learning is definitely applicable in analyzing simple shift ciphers like Caesar and affine ciphers, as well as substitution ciphers like Vigenère, but is it possible for machine learning to solve problems involving more complex ciphers such as Hill ciphers, where characters are mixed up and ruin frequency analysis?

A cryptanalyst finds the right key for decryption, while a machine learning model finds a suitable solution in a large space of possible solutions. With enough data, the machine learning model could find a good solution. How much data is needed to reliably use machine learning for breaking complex ciphers such that it's less work than brute-force search could be a challenge.


In a group, is it hard to calculate the base $g$ given $g^a$ and $a$? Discrete logarithm, that is: calculate $a$ given $g$ and $g^a$, is assumed to be a hard problem in some groups.

Is it also hard to calculate $g$ given $g^a$ and $a$?

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$.

However, there are cases for which it's hard: for example, when $n=pq$ is the product of two unknown primes $p,q$ and $g\in\mathbb Z/n\mathbb Z$, then the task is equivalent to decrypting the RSA ciphertext $g^a$ with respect to the public key $(n,a)$, which is generally assumed to be hard.

If you know $a$, you also know $\frac{1}{a}$ then $g=(g^a)^{\frac{1}{a}}$.

Now, answering the question for solving $X^r - a = 0$, when $r \mid (p-1)$. If my analysis is correct, if $r\mid (p-1)$, the square root algorithm can easily be adapted depending on the form of prime $p$.

If $p=2rq + 2r -1$, this is a deterministic case: let $$y_0=a^{\frac{p+1}{2 \times r}} \quad \Longrightarrow \quad y_0^r=\left(\frac{a}{p}\right) \times a$$

Then if $a \in QR(p)$, a particular solution is $y_0=a^{\frac{p+1}{2 \times r}}$ otherwise there is no solution!

If $p$ in other form: a particular solution can be calculated by a probabilistic algorithm, and is too complicated to expose here.

By the way, when a particular solution is calculated, all the $r$ roots are conjugate to each other, and are of the form $y_i =\mu_i \times y_0 \;\cdots \; \mu_i$ is one of the $r$ $r$th roots of Unity.

I emphasize that the cryptographic protocol should appropriately specify the conditions for the uniqueness in the solution of a given protocol, and in this case, we can use abusive notation like $\frac{1}{a}$.

And there should always be a method for selecting the appropriate solution.
The algorithm I mentioned here can be proved with the background given in Henri Cohen's book, a former professor in the Maths Dpt of BDX.


Does watching Youtube generate entrophy Does watching videos (either online videos such as off youtube or saved locally) generate enough (if any) entropy to create secure encryption keys? I understand that some activities such as memory usage, disk access, network utilization, using the mouse and keyboard, etc... generate entropy under Linux. What I don't know is if using the CPU and GPU also generates entropy? I also don't know if this is the same under Windows.

It does, but it's practically impossible to evaluate how much: just a tiny little bit, or enough for security?
A PC is an extremely complex thing, and it's practically impossible to know its exact state at a precise moment in time, even having observed its external behavior (user actions, network packets…) very precisely. Even knowing the exact state of the CPU alone is very difficult: it's very difficult to build a cycle-accurate simulator for the CPU of a modern PC or smartphone, much more difficult than building a simulator that implements all the operations but not their precise timing. Furthermore such complex chips have multiple clocks, and there is some unavoidable manufacturing imprecision that causes a drift between those clocks (CPU jitter), which is the basis of HAVEGE.
The problem with relying solely on the entropy from jitter (within the CPU and between peripherals) is that it's unreliable. Depending on the system configuration, on how much activity there is, on the ambient temperature, there may be more or less jitter. The entropy from user input is unreliable because the user may be somewhat predictable and may be observable. The entropy from network input is suspect because an adversary may be able to obtain it (e.g. if they control your Internet access because you're in a cybercafé or because they breached your router's 5-year old unpatched firmware).
All of these methods have the problem that shortly after boot, no or little entropy has had time to accumulate; a way to counter this is to save entropy from past runs in a file, and load that at boot time. This way, there may be a lack of entropy during the system installation, but as soon as the system has accumulated enough entropy for security, it keeps that entropy forever.
Operating systems like Linux and Windows mix all the entropy sources inside the kernel and expose it through system calls or similar methods (modern interfaces: getrandom(), BCryptGenRandom(); deprecated interfaces: /dev/urandom, CryptGenRandom()). The entropy you get from those system interfaces is more reliable than anything you could cobble up on your own, and is at least as trustworthy since it's coming from the operating system kernel which you have to trust anyway.
Fortunately modern systems, at least in the PC/smartphone range, have a built-in hardware random generator that is actually designed to produce entropy. The system mixes in all the entropy from various sources, which (barring bugs in the entropy mixing) gives you entropy that's at least as strong as the strongest source. While sources such as user activity and disk jitter are mixed in, it doesn't matter if they don't provide enough entropy, since the hardware RNG is sufficient on its own.

Or course it does. That's the foundational basis of /dev/random.
I'm not going to repeat what's already well documented. Please read Documentation and Analysis of the Linux Random Number Generator.
What's not really spelt out is where the entropy comes from. It comes from quantization noise. It's the attempt of digital systems to accurately model analogue events. There is also the Observer Effect which is a principal concept in physics. If you measure it, you change it.
The two conflate so that sampling you shoving your mouse about at a resolution of 4 GHz, or 250 trillionth of one second means that good entropy is generated. CPU, GPU, Tablet, mobile phone or washing machine are all the same.
Stick a randomness extractor on the output, and so come your secure encryption keys.


If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy? If one were to create a SHA256 hash using 256 coin flips converted to hex (which, as I understand it, is as "entro-phized" as one can capture in SHA256) then take that hash as a string, combine that with a hash of the word "cat" and hash the resulting 512 character string, would the resulting hash from that exercise be any less random than our "perfect" hash we began with?

My thinking is the final string would capture the same amount as the original randomness as what we started with because the "extra" entropy can not be captured and is lost. Is this the case and am I thinking about this correctly? Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

Thanks to anyone who can help explain this a little better.

A deterministic function $f(X)$ of a random variable $X$ never has greater entropy than the original random variable $X$.

(Side note: If you're not familiar with the technical terms random variable and expectation, or the definition of entropy in terms of them, I recommend you read up on some elementary probability theory first—the rest of this post will not make sense without these keywords!  In the sequel, ‘entropy’ can be taken to mean Shannon entropy or min-entropy—both work, and coincide on uniform distributions, but cryptography works primarily in min-entropy.  See this answer for a brief discussion of what entropy means from a crypto perspective.)

At best, if $X$ is a random $k$-bit string with uniform distribution and thus $k$ bits of entropy, the maximum possible, and if $f\colon \{0,1\}^k \to \{0,1\}^k$ is a permutation (a.k.a. bijection), then $f(X)$ also has $k$ bits of entropy.  If $f$ is not a permutation, then $f(X)$ has strictly less than $k$ bits of entropy—although perhaps not much less.

In this case, $f$ is SHA-256, which we might model by a uniform random choice of map $F\colon \{0,1\}^k \to \{0,1\}^k$.  There are almost certainly fewer than $2^k$ distinct outputs, because very few such possible values of $F$ are permutations.  Specifically, fix an output $y \in \{0,1\}^k$; for each input $x \in \{0,1\}^k$, we have $\Pr[F(x) = y] = 1/2^k$, and $F(x)$ is an independent random variable for every $x$, so
\begin{align*}
  \Pr&[\exists x. F(x) = y]
     = 1 - \Pr[\forall x. F(x) \ne y] \\
    &= 1 - \Pr[F(0) \ne y]\,\Pr[F(1) \ne y]\cdots\Pr[F(2^k - 1) \ne y] \\
    &= 1 - (1 - 1/2^k)^{2^k}.
\end{align*}
which, by linearity of expectations, is also the expected fraction of distinct outputs.  As $k \to \infty$, this converges to $1 - e^{-1} \approx 0.632$.

Thus, over a uniform random choice of $F$, the expected entropy of $F(X)$, or $\mathbb E_F\bigl[H[F(X)]\bigr]$, is about one bit less than the entropy of $X$, or $H[X]$, where $H$ is the entropy operator.

What about iterating SHA-256?  Do we lose a bit of entropy every time, so that $\operatorname{SHA-256}^{256}$ has zero entropy?  No.  If we independently chose another function $G\colon \{0,1\}^k \to \{0,1\}^k$, then over a uniform random choice of $F$ and $G$, the expected entropy of $F(G(X))$ might be about two bits less than the entropy of $X$.  But that's a bad model for iterating SHA-256, because we are restricted to the case $F = G$, in which case $F$ and $G$ are as far from independent as possible.

Rather, there's a good chance that for any fixed function $F$, there are many cycles on which $F$ is a permutation, and restricted to which $F$ thus preserves entropy.  There's usually one main big cycle, which lends itself to a drawing of a giant hairy rho: $\rho$.  In the limit as $\ell \to \infty$, $F^\ell(X)$ maps $X$ to an independent uniform random point on one of the cycles, the choice of cycle being weighted by the number of points on and leading to that cycle.

But in practical terms for cryptography engineering?  Usually we treat $\operatorname{SHA-256}(X)$ as a uniform random variable independent of everything else in the system (except where length extension attacks might be relevant) with entropy equal to that of $X$, or 256, whichever is smaller.

So this is what you're proposing:-

Cutting through your question to the crux:-

Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

There are two scenarios that have simple answers.

This is a one off and you never repeat the hashing with "Cat".  Then the entropy will be 256 bits plus a few from the other hash input.  You are correct in that the entropy can never go down.  It can however go up in non linear increments.  If the binary sequence representing "Cat" happens to appear in the left hand 256 bits, the overall entropy will only go up very slightly as the frequency component of those letters will just be incremented.  Think of it as compressing "CatCatCat...".  It's just another cat :-) So output =~ 262 bits.
If you constantly repeat this hashing with new coin tosses, and keep the cat in there, the entropy calculation will ignore it and you'll be left with just the random bits from the left hand side.  This is termed a bit fixing source, and is a common occurrence in true random number generators. If you were using JPEG generation as an entropy source, the file headers and other JPEG artefacts would be your cats. Output = 256 bits in this case.

There is also a more complex scenario that I won't go into (unless pressed) concerning the actual entropy content of a randomness extractor /hash function.  No one really knows the answer to this one though, and output < 262 bits.
So in conclusion, yes it can go up but certainly doesn't go down.


In RSA, how does the CPU deal with this huge modulus (8192 bits)? Whilst I understand how the RSA algorithm works, I don't understand how the CPU operates when it needs to use the mod function with a huge number $n$, for example.

$n = 8192$ bits;
$c = m^e \mod n$;

In essence my question is how does the CPU deal with this huge modulus?

It (or rather, the software running on it) will use arbitrary-precision ("bignum") arithmetic.  The way this works is basically the same way in which you (probably) learned to do arithmetic on paper at school.

The arithmetic taught to us humans at school is base-10 arithmetic — that is, we represent numbers as strings made up of ten different digits, from "0" to "9", where each digit alone represents a different small number below 10, and where placing a digit to the left of another digit multiplies its value by 10.

Assuming you didn't totally sleep through grade school, you probably remember having to memorize the addition and multiplication tables for single-digit numbers: 1 + 1 = 2, 7 + 7 = 14, 6 × 4 = 24, and so on.  Those are the basic "atomic" operations for base-10 arithmetic, and once you know how to do them, you can combine them to calculate things with larger numbers.

(You don't have to have the basic operations all perfectly memorized, of course; if you, say, forget what 7 × 6 is, but still remember that 6 × 6 = 36, you can just count six more numbers up from that to end up at 42.  And even if you were to forget what e.g. 7 + 7 is, you could, say, count on your fingers to arrive at 14.  It just turns out that, for us humans, memorizing those basic single-digit operations — i.e. implementing them with the human equivalent of a look-up table — makes arithmetic a lot faster than working them out from first principles every time.  For computers, the tradeoff may be different.)

For example, depending on how math was taught at your school, you may remember writing down an addition problem on paper something like this:

Exercise: 12345 + 67890 = ______

             <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
             <-- result

and the working it out digit by digit, from right to left.  Here, you'd start with 5 + 0 = 5 (with no carry):

       0     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
        5    <-- result

and then proceed to 4 + 9 = 13 (i.e. write down 3, carry 1):

      10     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
       35    <-- result

and then 1 + 3 + 8 = 4 + 8 = 12 (i.e. write down 2, carry 1), and so on all the way to:

    1110     <-- carries
    12345    <-- first number
  + 67890    <-- second number
  -------
    80235    <-- result

You may have also learned similar pencil-and-paper algorithms for other elementary arithmetic operations, like subtraction, multiplication and even long division (which can also be used for modular reduction).  The important thing to realize is that all these calculation methods are based on rules for manipulating strings of digits, and on simple arithmetic operations on single digits.  As long as you can do the basic single-digit operations, and know the algorithm for combining them together, you can do arithmetic on paper with numbers as large as you want (or need) to!

So how do computers do it, then?  They could of course use exactly the same decimal arithmetic rules as we do, but that would be pretty inefficient.  A typical CPU already has fast circuitry to add or multiply together any two 32 or 64 bit (and possibly even larger) numbers with a single machine code instruction, so it makes a lot more sense to treat 32 or 64 bit arithmetic as the basic building block.

Thus, a typical computer implementation of bignum arithmetic effectively works with "digits" that are 32 or 64 bit integers, and represents larger numbers as strings of those smaller integers.  The algorithms used are very similar to those we'd use for pencil-and-paper calculation, except that instead of base 10, a computer is far more likely to use base 232 or 264.

For example, let's calculate the sum of two random 128-bit numbers (written in hexadecimal for convenience):

Exercise: 3d96d3e9d019665051ecf94e4c0c697b +
          a80314053a779df7464ea2feebf771be = ______

A modern CPU might be able to calculate that directly, but let's assume that we only have a 32-bit CPU available.  Fortunately, we can break up our numbers into 32-bit chunks and use the same addition algorithm we used before:

                                         <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                                         <-- result

So first, we need to calculate 4c0c697b + ebf771be, which our CPU easily tells us is 13803db39 (i.e. 32-bit result 3803db39, plus carry 1):

                             1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                               3803db39  <-- result

Next we ask our CPU to calculate 51ecf94e + 464ea2fe, and to increment the result by one because of the carry, which yields 983b9c4d (and no carry for the next position):

                    0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
                      983b9c4d 3803db39  <-- result

We can then proceed with the remaining two 32-bit additions in the same way, getting d0196650 + 3a779df7 = 10a910447 (i.e. 0a910447 and carry 1) and 3d96d3e9 + a8031405 + 1 = e599e7ef:

  0        1        0        1           <-- carries
    3d96d3e9 d0196650 51ecf94e 4c0c697b  <-- first number
  + a8031405 3a779df7 464ea2fe ebf771be  <-- second number
  -------------------------------------
    e599e7ef 0a910447 983b9c4d 3803db39  <-- result

And there we have our result!

I used addition for this simple example, but similar algorithms can be used for other arithmetic operations, including exponentiation and modular reduction (which one would normally combine into a single modular exponentiation algorithm, since it's much more efficient to do them together rather that to first exponentiate and then reduce).

Also note that the arithmetic algorithms used for cryptography tend to be somewhat specialized, since in crypto it's often important to avoid timing attacks and other types of side-channel attacks by making sure that the algorithm takes the same amount of time to run (and consumes roughly the same amount of power, etc.) regardless of what the numbers being added (or multiplied or raised to a power, etc.) are.

One important aspect to keep in mind, which I do not see in the other answers, is that in binary modulus 8192 is very easy, as 8192 is simply 2^13.

If you take modulus in "normal" base 10, you'd call %100 simple. 1237659%100=59. You simply cut off everything before the last 2 digits.

In binary, the same is true for %8192, or, written in binary, 10000000000000. You simply take your number, for instance 1001100001000010111000100010001001, and only use the last 13 digits, and get 0100010001001.

Edit:

Excuse me. Just after posting this answer, I read through your question again, and realized it's %8192bit, or ~1*10^2466. Though my "answer" is still true, it has far from any notable impact.


One time pad in CBC mode? I have been searching about if it is more secure to use CBC mode in OTP but I can't find anywhere where people have sad that it is more secure.

Question: Is CBC mode in OTP more secure?

Because I have been reading articles like "https://stackoverflow.com/questions/22212407/how-to-alter-cbc-encrypted-text-to-change-the-message" and I have been wondering if it makes OTP more secure on that attack.

For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

BUT if you have it in CBC mode does it make it safer from this kind of attacks? (Known-plaintext-attacks and chosen-plaintext-attacks).

For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

What you are describing is what happens if an attacker introduces changes in the ciphertext by a man-in-the-middle attack. This kind of attack is not protected against by OTP. OTP only provides for confidentiality, not integrity and authenticity. To add integrity and authenticity you need to add a message authentication code or MAC to the ciphertext.

Unfortunately MAC's won't provide perfect integrity or authenticity. In practice this doesn't matter much as - for instance - HMAC is pretty secure. It cannot be proven secure just like OTP however. Ciphers such as AES have the same properties; they are rather secure, but they cannot be proven secure. Generally they are considered secure enough and they are much more practical than OTPs.

OTP doesn't propagate errors introduced to the ciphertext. CBC does propagate errors. If you could reliably detect such errors then you would have integrity protection. This is however not the case:

CBC error propagation is localized to the current block and a single bit of the next block;
CBC decryption always succeeds, you just get incorrect plaintext;
if the plaintext is a padded message then the padding may trigger padding errors, but it may also - by chance - create a valid padding scheme;
if the plaintext is a padded message then plaintext/padding oracle attacks may apply, destroying not just the integrity but also the confidentiality (leaving you with no protection whatsoever).

Nowadays we don't care about error propagation all that much; we apply a (H)MAC over the IV and ciphertext or we apply an authenticated mode of operation (an AEAD cipher) such as GCM. In that case the verification of the authentication tag will fail if any changes are made to the IV, ciphertext or authentication tag.

The CBC mode of operation is defined for keyed block ciphers. OTP however isn't a block cipher, so CBC cannot be directly applied to it. In CBC the block cipher is executed for each block of plaintext. As you should never reuse the key for a one time pad, CBC can not be made applicable to OTP.

Perfect secrecy is a security concept mathematically proved to be true for the one-time pad by Shannon in 1949.

One-time pad is offering perfect secrecy if used with these three properties :

The key space (number of possible keys) is greater than the number of possible plaintexts
The key is truly random : each key of the key space has the same probability to be chose
The key has to be used only once (this is not two-time pad ;) )

Respecting these properties, you don't need to add any cryptographic mechanism (like CBC) to one-time pad.


Lattice-based cryptography prone to side channel attack? Is lattice-based cryptography still prone to side channel attacks? What are some mitigation strategies, if any?

my understanding is that Supersingular isogeny Diffie-Hellman (SIDH) is fully protected against timing and cache attacks as all operations on secret data run in constant time. That was my own experience.


Can ECDH be used for authentication? Is it safe to use ECDH for challenge-response authentication, with server key being ephemeral?

The goal is that server does not store sensitive data (hashes) and allow clients to use additional security if needed (for example generate and store their key in a smartcard and skip key derivation).

Client derives private key from the password, using a strong hash algorithm (similar to bitcoin address generators using passwords)
Server generates a key and sends its (ephemeral) public key and a challenge string
Client must reply with the challenge, encrypted with the shared key
Server checks if decrypting response yields the challenge

Assumptions

A secure channel is already established
Server has the client's public key stored

Here’s a link that shows how to implement ECDH with long term public keys and ephemeral shared keys. You could just add this authentication after the TLS handshake as it’s own layer. Think about the openID protocol.  You can publish the keys at a well-known-endpoint,  it’s not necessary to wrap them in a certificate.

First off, generating an asymmetric key pair is an expensive operation. As you might know, it is done once (usually while creating a certificate signing request) and used for multiple sessions. Web servers usually use it for a year (check the expiry date of say google.com's certificate)

Servers are typically designed to handle multiple requests from clients and one of the metrics of the quality of the server is to see how much it scales to burst client requests.

If you're talking about one asymmetric key pair per client, it's a huge ask, let alone one key pair per session. Apart from computation power, you need to consider the entropy concerns too. i.e., is my server capable of generating enough high quality randomness to cater all key pair generations?

Having said all this, let's assume you're infact using ephemeral assymetric key pairs. Thing is, you can use them for challenge-response verification as well! Which is what most of the standard protocols do. Once the certificates are exchanged and their signatures are verified, the proof of possession of private key is done using challenge response. To prove A has the right private key, B will encrypt a random string using A's public key and send it to A. A decrypts that using it's private key and sends back the random string in plain text which B verifies. Same thing is done with roles exchanged to prove B has the right private key of its key pair.

If you really want to do the authentication part using ECDH, you can't because

ECDH has a random component in it hence cannot be mapped to a static password.
Any two parties can derive a symmetric key using ECDH. There is no way to tell if you're exchanging keys with the right guy. The authenticity of the keyex parties must be ensured before the keyex is initiated.

Therefore, I would say No, ECDH will not serve your requirement of "server not holding the client's password but still is able to authenticate client".


XOR Encryption with bcrypt password de-biasing Objective:  To have a very simple to verify, but very secure small message encryption.

Idea:  Message ⊕ bcrypt( Password).  We remove password biases with bcrypt and then XOR resulting key with the Message.

Implementation.

Limitation: Only messages up to 320 characters long are supported.

10 bcrypt salt values are hard coded:

Salt1 =  $2a$12$geKv/Jdb2zSGEtnn3AuXXe
Salt2 =  $2a$12$h1V42zCLf/F5F7RbueVuZe
Salt3 =  $2a$12$UTX8OMvg1CI3/pnbT0F5Mu
. . . . . . .
Salt10 =  $2a$12$Yq9Vo0yefk6zJlEvJmBf6O

Suppose we have

Message=My safe code is 29540323, my bank card pin is 6926

Password= 32GateKeepers

The message is 50 characters long. bcrypt produces keys 32 characters long. So we need 2 keys to match message length:

Key1 = bcrypt(Password, Salt1) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUO

Key2 = bcrypt(Password, Salt2) = emTDJsUVCLFE3Jm8Cjx2S2/WmXEVrrU.

Key (50 characters) = e8.4zyJT9m9R/KX./Kd2juSHn25IqGUOemTDJsUVCLFE3Jm8Cj

Code = Message ⊕ Key = 40,65,14,71,27,31,47,116,90,2,93,55,15,34,43,14,29,114,81,6,90,70,97,123,66,18,88,48,81,37,52,33,14,77,55,37,56,23,117,38,42,34,102,44,64,106,91,1,113,92

Question: Is bcrypt de-biasing good enough to use in XOR encryption?

Specific Problem: Attacker knows that the same password was hashed with ten known salts for longer messages.

Specific Question: If the attacker has 10 hashes of the same password with 10 known salts. Given the nature of hashes, does this weaken the password?

Any time you perform more than one evaluation of a password-hashing algorithm where it is a legitimate option to perform it only once you are doing something wrong. Here is why:

If one hash evaluation costs $C$, then 10 hashes with with the same cost-parameter will costs $10 \times C$.
Hashes can be evaluated by a cracker with a cost per candidate-password proportional to $C$. (Probably a lot less than C since they can build or buy systems optimized for and dedicated to password cracking.)
Given $x = H(\text{salt}, \text{password})$, one can guess a candidate password $p$ and compare $x$ to $y = H(\text{salt}, p)$.

If $x \neq y$ then $\text{password}$ is not $p$.
If $\text{password}$ is not $p$ then $x = y$ with only $1 / N$ probability where $N$ is the size of a hash's image set. *

Given knowledge of some $n$-bit long subset of one hash output's bits, a cracker can similarly evaluate the hash of one candidate password with a cost $\le C$ with a $2^{-n}$ false positive rate.

If the adversary knows one character of plaintext (8 bits), then out every 256 candidate passwords, 255 candidates can be eliminated with work proportional to $C$. Only 1 out of every 256 will need two or more hash function evaluations to check for false positives.
Because each 32 byte block can be tested independently, the password cracker will rarely have to do proportional to $10 \times C$ work but the legitimate password-holder will always do $10 \times C$ work,
The cracker has a significant advantage over the honest party compared to an alternate method: Use a single password hash evaluation (a password based key derivation function) to calculate  one key and use that key with a typical symmetric key message encryption algorithm.

One can put key derivation functions (which you can think of as hash functions used to deterministically generate keys) into two categories: password-based KDFs and key-based KDFs.

"Password hashes" (or "slow hash algorithms" as non-experts sometimes say) are used to describe password-based functions that "stretch" passwords. Passwords are usually low entropy (that is they're relatively predictable) and so password hashes and PB-KDFs are designed to be artificially slow for both legitimate parties and password crackers to evaluate with the hope that it makes password cracking less "profitiable".

Standard or "fast" hash algorithms are not necessarily insecure just because they are fast. If passwords were as unpredictable as a 128 bit key then password bases could just store SHA-2 hashes of passwords (preferably still salted for off-topic reasons) with no loss to security.

The right way to do things is to increase your password hashing algorithm's cost parameter by a factor of ten. You're doing the same amount of work, $$1 \times (10 \times C) = 10 \times (1 \times C)$$ so your CPU-time budget doesn't increase. On the other hand, the adversary, with only one slower hash function to crack, now needs to always do proportional to $10 \times C$ work instead of just $C$ work.

If you need more key material than a PB-KDF can give you without multiplying the amount of work you need to do, then derive just one master key from the PB-KDF and feed the derived key to a KB-KDF. You can derive many keys from a key-based key derivation function much faster than the run time of a password hashing function.

If for some reason you must use only hash algorithms instead of a stream cipher, then do
$$K_M = bcrypt_{10 \times C}^\text{**}(\text{salt}, \text{password})$$
$$K_i = \text{SHA-512}(K_M \| i \| \text{nonce})$$
$$\text{ciphertext}_i = \text{plaintext}_i \oplus K_{i + 1}$$

And send
$$\text{ciphertext} \| \text{HMAC-SHA-512}(K_0, \text{ciphertext})$$
because you need message authentication in addition to message secrecy.

In my previous cost analysis I treated the key-stream computation as if it were zero. If you choose a large $C$ then this is a reasonable assumption. Otherwise assume little $c$ is the cost of a "fast" hash. You CPU cost is $10 \times C + 13 \times c$. (Since HMAC is 2 more hashes and you derive one more key for HMAC.) And the adversary's cost is $10 \times C + c$. But both are approxmately $10 \times C$.

For your specific proposal, assuming you're using ASCII encoding of plaintext, you can easily infer 32 bits of every full 32 byte block because no standard ASCII character has a byte value with the most significant bit set.

For other types of plaintext it won't necessarily be so trivial, but you should assume that there are some other ways to guess at plaintext. If there is uncertainty then the adversary could just compare more plaintext-guesses to the same hash evaluation. You get more false positives obviously, but this doesn't prevent cracking. False positives can be distinguished from true positives by evaluating a hash with each salt then looking at the decryption to see if it makes sense. (Check if it contains real dictionary words, or do statistical tests comparing it to reasonable plaintext.)

* Assuming the hash function is unbiased, which is reasonable for good password hash algorithms and many common not-good ones. (SHA-1 and MD5 included among other bad ones.) For the plain-old password hashing use case (not your use) false positives (which are so improbable that it's safe to say they won't happen) are just as good as true positives.

** Use Argon2d if an optimized implementation is available instead of bcrypt. bcrypt is fine if it has an optimized implementation. Same for PB-KDF2 and balloon hashing.  (Don't request PB-KDF2 output length that is too long.) You can use scrypt as well if there is an optimized implementation and if you can give it a large CPU and RAM allowance. ... I'm beginning to see that people hear the "Use ___ instead of ___ for password hashing" advice that's beginning to reach a larger audience now and are taking away the cargo-cult-like idea that it means "Always substitute [password hashing function] for [normal hash algorithm or encryption algorithm]". That's wrong. Only use password hashing functions for password storage and for derivation of a master key.

Edit: Argon2d. not Argon2i.

Is BCrypt de-biasing good enough to use in XOR encryption?

With extreme narrow mindedness, the technical answer is yes it is.  It will produce a uniformly distributed random output can can be used in a short stream cipher. All decent password stretching /key derivation functions can as they use cryptographic primitives like HMACs or parts of them like Blowfish. So yes.

Rather than jump into a technical analysis of your scheme, I'd say that overall this is a very unorthodox method to secure short messages.  You're taking on the role of Frankenstein creating a stream cipher monster out of parts that were never intended to be put together.  Yes, it might be alive, but it's also horrible.

Consider that BCrypt output is alphanumeric rather than binary so you'll have to perform modular xorations(?). And longer messages require more keys.  Kerckhoffs's principle warns tin foil wearing types that all the salts will be known, so they become irrelevant to the overall security context. And your final cipher text will be malleable as all un authenticated ciphers are.  This might not be an issue in your case though.

There are common encryption methods based on stream ciphers than will automatically generate a pseudo random stream for subsequent xor. Or block ciphers.  It doesn't really matter internally does it?

  We remove Password biases with BCrypt and then XOR resulting Key with the Message.

You have to think very carefully.  What are you creating? Password text biases are automatically resolved in standard symmetric key methods. There is even original Blowfish if you like, and that's with 400+ bit keys. Debiasing is definately not BCrypt's raison d'être. If anything, debiasing is straying into areas of entropy and it's extraction.

I'm a huge fan of rolling your own simple encyptions but I think that in this case you need to find some flaming torches, organise the villagers and kill this thing.

  If the attacker has 10 hashes of the same password with 10 known salts. Given the nature of hashes, does this weaken the password?

This actually forms a good question, but might be better spun off as a separate one. This will encourage answers unbridled with the odd cryptographic monster baggage.


Elliptic Curve - X Coordinate I am currently working on a Koblitz curve. I have found the curve has two matching groups based on the base curve point and N-1 point. My question is as follows: Is there an algorithm to determine how many X coordinates are the same in an elliptic curve? This will tell me how many groups are inside the entire curve based on its parameters given.

As per the Hasse's theorem the total number of points can be computed for both the Finite field curve and binary field curve

For the Finite Field , the number of points on E(F p) is denoted by #E(F p). The Hasse
Theorem states that:
p+1-2√p≤ E(F p) ≤p+1+2√p.

For the Binary field, The number of points on E(F2^m)() is denoted by #E(F2^m). The Hasse Theorem states that:
2^m+1-2√2^m≤#E(F2^m) ≤2^m+1+2√2^m.

For Every x co-ordinate there are 2 Y co-ordinates.
Hence the number of X co-ordinates can be deduced as per the calculation of Hasse's theorem points/2.