Why is writing your own encryption discouraged? Say I want to write an encryption algorithm to communicate between me and my friend for this private use. How is that bad?

E.g. I can take the word Hello and encrypt it with a simple algorithm – for example –  take each letter and multiply its value by 2 and add 13 so that it becomes completely unreadable.

Is writing a private encryption that stays between two people discouraged or not? What's wrong with it?

Your question, MikeAzo's comment, and your reply practically could not be a better example of Schneier's Law in practice. Schneier stated:

Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break.

To answer your reply

How can you break it if I send you this "QTCPIGXKUXTGG" ciphertext encrypted by a merely a simple algorithm which you have no idea about how it was encrypted?

Because even though we might not know exactly what your secret algorithm is, the first thing an attacker is going to reach for are common tools to attack substitution ciphers or polyalphabetic ciphers. Given even a few sentences of ciphertext is likely enough to fully recover every plaintext.
The fact that you don't know how to break it is irrelevant. It's trivial to create a cipher that you yourself can't break, but it's another thing entirely to create a cipher that others can't break. And the odds that you are capable of doing it when you're not aware of even the most basic attacks against ciphers hundreds of years old — not to mention modern concepts like indistinguishability under different attack models — puts you at an insurmountable disadvantage compared to ciphers designed by researchers with decades of experience in the field who are building off of modern notions of security and the discarded remains of thousands of failed ciphers that came before.
As an example, even if your cipher is somehow secure against a ciphertext-only attack (it's not), is it secure if I can trick you into encrypting a message of my choosing? What if I can trick you into decrypting a message of my choosing? What if I know part of or all of the plaintext for a particular encrypted message you've sent? What if you encrypt multiple messages with the same key? What if I can do any or all of these things hundreds or even millions of times in a row? These are all situations that are extremely common in the real world, and under which modern ciphers remain completely secure.
I'll leave you with another Schneier classic, Memo to the Amateur Cipher Designer:

A cryptographer friend tells the story of an amateur who kept bothering him with the cipher he invented. The cryptographer would break the cipher, the amateur would make a change to "fix" it, and the cryptographer would break it again. This exchange went on a few times until the cryptographer became fed up. When the amateur visited him to hear what the cryptographer thought, the cryptographer put three envelopes face down on the table. "In each of these envelopes is an attack against your cipher. Take one and read it. Don't come back until you've discovered the other two attacks." The amateur was never heard from again.

So here's your first envelope: given a paragraph or two of ciphertext, your cipher will fail to language-based frequency analysis.
Let me know when you've figured out the other two attacks.
Edit: The comment about indistinguishability under different attack models is one reason why most "decipher this message crypto challenges" are completely bunk. They often simply give an attacker some ciphertext, ask them to decipher it, and declare victory when nobody produces the plaintext after some amount of time. Unfortunately that's not how crypto works in the real world; attackers have many more tricks up their sleeve in practice. They can trick computers into encrypting data of their choosing, they can trick computers into decrypting data of their choosing, and they can usually even do these things thousands, millions, or billions of times. Moxie's post shows how even the most terrible, horribly-designed, and obviously insecure ciphers can be effectively impervious when you restrict an attacker to a single ciphertext-only attack, which aren't representative of attackers' capabilities against ciphers as they're actually deployed in practice.

Obscurity can offer some security, but its usefulness is very limited.  Among other things:

It is difficulty to quantify how much security it offers.  Since human beings make very bad random number generators, it's hard for someone who comes up with a seemingly-original idea to know how likely it is that someone else would think of it.
Although it is not difficult to come up with an algorithm which will be secure under the right conditions, maintaining those conditions is difficult.  The algorithm and all plaintexts must be forever kept secret from anyone who wouldn't be trusted with the content of all messages that have ever been sent using it.  Further, the total volume of ciphertext available must be kept fairly small, but it's difficult to quantify how small.
The only way to compartmentalize risk is to use cryptographically-independent algorithms for every different kind of message whose disclosure shouldn't affect any others.  Devising truly independent algorithms is difficult for reason #1 above, and most approaches that rely upon security through obscurity fail to properly compartmentalize risk as a result.

Although things like DES, AES, etc. are often described as "algorithms", it would perhaps be more useful to think of them as "algorithm generators".  If one has a good source of 256-bit random numbers that have essentially zero probability of matching anything else anywhere in the universe, then "use AES with this number I just generated" can be used as an encryption algorithm which is cryptographically independent from any other algorithm that has ever existed.  Consequently, it's much easier to compartmentalize risk using such approaches than by devising one's own encryption schemes.


For any hash value, is there an infinite number of inputs that hash to it? Bruce Schneier writes (back in 2005) in a post on cryptanalysis of SHA-1:

  SHA-1 produces a 160-bit hash. That is, every message hashes down
      to a 160-bit number. Given that there are an infinite number of
      messages that hash to each possible value, there are an infinite
      number of possible collisions.

How do we know that there is an infinite number of messages that hash to each possible value?
Is this known to be true for other hash algorithms than SHA-1?

As rightly pointed by Henrick Hellström and Otus, FIPS 186-4 defines SHA-1 with a maximum message length of $2^{64}-1$ bits, hence it is certain that no 160-bit value is the hash of an infinite number of messages. In the following, unless otherwise stated, I assume that we modify the definition of SHA-1 to allow for an infinite number of messages, by removing the length limitation and taking the message length modulo $2^{64}$.

It is not known, in the mathematical sense of that, that there is an infinite number of messages that hash to each possible value; that's both if we define possible value as one of the $2^{160}$ bitstrings of size 160 bits; or even if we define it as one of the (conceivably less than) $2^{160}$ bitstrings such that there exists a message that hashes to that value.

However, we expect that each of the $2^{160}$ bitstrings is the result of hashing an infinite number of messages.

Given the structure of SHA-1 (a Merkle-Damgård hash), this would follow from the plausible conjecture that modifying two consecutive message blocks except for the last 72 bits (of padding and length) is enough to reach any desired value. Or more precisely: that for any $I$ and $K$ of 160 bits, and any suffix $S$ of 72 bits, there exists $A$ of 512 bits and $B$ of 440 bits, such that $\mathcal F(\mathcal F(I,A),B\|S)=K$, where $\mathcal F$ is the compression function of SHA-1 (with first argument the 160-bit hash state, and second argument the 512-bit block input). This conjecture allows to explicitly construct $2^{160n}$ messages of $1024n+952$ bits hashing to any value $K$ (for $n=0$ we set $I$ to the initialization constants of SHA-1, and $S$ to $\text{0x80}$ followed by the length $952$ over 64 bits; we proceed by induction, postfixing previous messages with the former $S$, and setting the new $S$ to $\text{0x80}$ followed by $(1024n+952)\bmod2^{128}$ over 64 bits).

That conjecture seems extremely plausible is we model $\mathcal F$ as a random function of its inputs; or if we model the cipher that it uses internally as an ideal cipher, followed by addition modulo $2^{32}$ of each of the 5 words of input and output (an even better model of what SHA-1 is). The argument goes like: it is likely that for any 160-bit intermediary $J$ we can find $B$ allowing to reach any $K$ as $\mathcal F(J,B\|L)$, for we have $2^{440}$ choices of $B$ and only $2^{160}$ values of $K$ to cover, with the square of the later number much larger than the former. Even if there was some exceptions because $\mathcal F$ or its internal cipher is too regular, we have a large (arguably full or next to full) choice of $J$ by varying $A$, and that will help fully covering the possible $K$. Note: I fell more confident about this argument with belt and suspenders than I would be with a single round of $\mathcal F$.

Back to the actual definition of SHA-1 with limited input length, the above plausible conjecture would imply that more than $2^{(2^{61})}$ messages hash to any given value. That's practically infinite for all but a mathematician.

A hash function as described in wiki is "A  hash function is any function that can be used to map data of arbitrary size to data of fixed size".

Hence what given inputs of a varying length there can be an infinite number of messages.

Now following the Pigeon Hole Principle where given a set of messages M that a hash function maps to a set of hash values S where M > S there will be inevitably collisions.

Hence given this properties we can say there will be X number of messages that results in multiple occurrence of hash value Y. And finally yes this holds true for all hash algorithms to a certain degree (There are other set of hash algorithms such as perfect hash algorithms that are designed where X = Y)


Brute force against computational security One-time pad is secure under brute force with respect to either of the definitions
\begin{align}
\Pr[M = m] &= \Pr[M = m | C = c]\\
\Pr[C = c | M = m_0] &= \Pr[C = c | M = m_1]
\end{align}

basically because the key and message spaces are the same, and $\oplus$ is closed under these spaces.

Given the argument above, I don't understand precisely how computationally secure schemes are compromised under brute force. In particular, how would any of the two equations above be violated given the scheme $$\mathsf{Enc}(m, k) = m \oplus G(k),$$ where $G$ is a pseudorandom generator.

For a (fixed-length) cipher to meet your first condition, it needs to be the case that it's no easier to guess the plaintext if you have the ciphertext than it is to guess the plaintext without the ciphertext. Now, suppose I send a random 1024-bit string XORed with $G(k)$ for some 128-bit $k$ and computationally secure $G$. The probability that my message is $0\ldots0$ is exactly $2^{-1024}$. I encrypt my message with a 128-bit key selected uniformly at random from the space of 128-bit keys to get $c$. Now suppose you intercept $c$. You know it's encrypted with some key $k$; you know there are $2^{128}$ such keys. That means that there are only $2^{128}$ possible decryptions -- at most 1 per key. This is why the keyspace of a perfectly secure scheme must be at least as big as the message space: knowing the ciphertext means that the number of possible messages is reduced to the number of possible keys, and if there are fewer keys than messages we've eliminated a lot of messages. That means that knowing "this ciphertext can decrypt to $m$" tells us that it's much more likely to be $m$ than we had suspected beforehand.

If $K=k$, then $M=c\oplus G(k)$. So, $$\Pr[M=c \oplus G(k)|C=c] \ge \Pr[K=k]=2^{-128}\ne 2^{-1024}$$ for any $k$. Suppose, for instance, that you try $k=1\ldots1$ and find that $c\oplus G(k)=0\ldots0$. You now know that $$\Pr[M=0\ldots0|C=c]\ge\Pr[K=1\ldots1]=2^{-128}\ne 2^{-1024}=\Pr[M=0\ldots0]$$ after a very quick computation (just one evaluation of $G$). That means that even with a computationally secure cipher, given $c$ an attacker can easily find a message $m$ such that $\Pr[M=m|C=c]\ge 2^{|k|}$ -- specifically, $\mathsf{Dec}(c,0...0)$. And that violates $\Pr[M=m|C=c]=\Pr[M=m]$ in a single evaluation of $\mathsf{Dec}$.

Since this question topic is about OTP and random number generator let me add my RNG class description as an answer here. It may be of use for you...

There are 2 main classes of RNGs (Random Number Generators): Deterministic and Non-Deterministic.

Deterministic RNGs are:

PRNG (Pseudo Random Number Generator)

CSPRNG (Cryptographically Secure Pseudo Random Number Generator)

Non-Deterministic RNGs are:

CSRNG (Cryptographically Secure Random Number Generator), not to be confused with CSPRNG!

TRNG (True Random Number Generator)

PRNGs are useful for generating good random numbers for any application (e.g. lotteries) except for OTP keys and encryption where PRNGs are useless and not recommended, because a) the attacker only requires the seed (init vector, usually a single 32-bit longint or 64-bit integer number) to generate the whole sequence of random numbers and b) only if the attacker knows a sequence of generated random numbers he can mathematically compute the next random numbers for that sequence or even derive the seed number from them!

TRNGs are unique and very useful for encryption, because they are not required to work with seeds or random IV (Initialisation Vectors)! A TRNG usually produces an infinite stream of random numbers (bits or bytes for that matter) which are generated not by software but by some outside random source.

The outside random source can be anything from radioactive decay, atmospheric noise, white, brown or pink noise from a TV set, static interference from hardware components (such as USB or computer chips) or in the simplest way from keystrokes pressed by a human source, as presented in my topic True Random Number Generator by Milliseconds per keystroke (TRNG-Kms). The same can be done with mouse movements to generate truly non-determinstic numbers. "Non-deterministic" means truly random! And it does not require seeds or other intialisation vectors as mentioned.


State of the art RSA key generation I would like to know if there is an algorithm to generate a RSA key at the state of the art of the present cryptanalysis.

Beside the key lenght I know there are some weakness in the choice of prime numbers that could help an attacker to factor the modulus $N$.

The standard key generation, as far as I know, generate a random number of the right lenght, tries to factorise it dividing it by small factors (say $\leq 10000$) and then one or more primality test (as Fermat and Miller-Rabin) until the confidence level is high enough.

But what about risks that $p-1, q-1$ are with small factors?

There is consensus that it is safe to use random primes $p$ and $q$ when generating 2048-bit (or wider) RSA public moduli which two prime factors $p$ and $q$ are about half the key size. That is sanctioned by FIPS 186-4, appendix B.3; specifically, wording in B.3.1 item A:

  Using methods 1 and 2 [yielding provable (1) and probable (2) random primes],
  $p$ and $q$ with lengths of 1024 or 1536 bits may be generated;
  $p$ and $q$ with lengths of 512 bits shall not be generated using these methods.
  Instead, $p$ and $q$ with lengths of 512 bits shall be generated using the
  conditions based on auxiliary primes.

Even though FIPS 186-4 requires (in the second part of this quote) that $p-1$, $q-1$, $p+1$, $q+1$ have at least one known large prime factor when generating a 1024-bit key which two prime factors $p$ and $q$ are 512-bit, many regard this as an unnecessary complication.

The rationale about requiring that $p-1$ (and $q-1$) has at least one large factor is to insure resistance against Pollard's p-1 factoring. The standard rationale that such precautions become pointless past a certain size is that we have factoring algorithms (including GNFS and ECM) with a much better asymptotic run time; that becomes rigorous (thus true) if we add: for any fixed odds of success [Pretty much the same applies to requiring that $p+1$ (and $q+1$) has at least one large factor, which would be in order to guard against Williams' p+1 factoring; and when we do not need to guard against Pollard's p-1, we do not need to guard against Williams' p+1, thus I disregard the later].

Determining quantitatively when we can dispense of precautions against Pollard's p-1 is not trivial!

There's a line of thought that if parameters make us safe enough from ECM, we are also safe from Pollard's p-1. This argument is wrong (which does not preclude that it leads to correct conclusions), at least when we consider generation of many keys in a context where an adversary would be content with factoring any of $k$ keys, rather than a certain key (e.g. the adversary's objective is to pass some signature check, and she knows many public key certificates of entities that can emit valid signatures, which is common in machine-to-machine applications). Counter-argument: Pollard's p-1 is better than ECM from the standpoint of the ratio $\text{odds to factor}\over\text{computing effort}$ for low computing effort when factoring random integers (for this reason, in GMP-ECM, a significant time is spent in Pollard's p-1, with great success); that extends (with comparable advantage) to factoring integers that are product of random primes of specified size; and that ratio is what matters as long a the number $k$ of keys does not become the limiting factor.
There's a line of thought that GNFS is so much better than ECM that it transcends any advantage Pollard's p-1 may have over ECM for parameters of cryptographic interest. That argument works (past some point depending on the previous consideration) for RSA modulus $N$ with two prime factors of about equal size. But it does not apply when $N$ has one factor $p$ much smaller than half of $N$, which is the case in multi-prime RSA (see PKCS#1), and unbalanced RSA as in RSAP and SPAKE/ALIKE, which e.g. consider a 1248-bit $N$ with a 352-bit $p$, expected to provide 80-bit security [for some definition of that; these parameters are supposed to balance GNFS and ECM].

Generation of prime numbers is just madness by crypto gurus. My guess is that no prime will be strong enough, or safe enough if you follow all the recommendations.

not be close to a power p = k^j + r   with |r| small
p-1/2  must have a large factor
((p-1/2)-1)/2  must have a large factor
(p+1)/2  must have a large factor

avoid p = k*q + r   with |r| small

not be at the end or the start of a large prime gap,
i.e.  p - r and p + s with |r| and |s| small are also acceptable primes

and of course, p - q > |r|  with r at least a certain amount of bits
(this implies the trap p != q for which RSA does not work)

make sure p is not a pseudoprime.
do not forget that miller-rabin tests work only if gcd(base, p) == 1 and base != p
when running multiple miller-rabin tests, make sure the different basis
are co-prime, else a pseudoprime could escape with an unacceptable
high probability.

ensure log2(p*q) == log2(n) by ensuring log2(p*p) == log2(q*q) == log2(n)

and so on, and so on. All the recommendations do have some ground. They might not be all necessary. Some famous recommendations apply to unpractical attacks.

All known practical failures are related to weak randomness, or protocol failures, or implementation bugs exposing the computer memory and possibly key material.

Simple advice : Just follow the standard blindly. Document that you follow the standard strictly. If there is a weakness, it will be published, you will know it, corrections will be published and you know how to detect and fix the problem.

If the standard suggest that it is secure to use primes made from randomness from an approved generator, as suggested in the other answer, then this is the state of the art.


Need 32-bit mixing function that has perfect avalanche between octets for my hobby tinkering project, I need a mixing function that takes 32-bit input and has 32-bit output (and will, most likely, run in a 32-bit C environment) and the following property (independent of endianness, i.e. it’s enough to only look at either big endian or little endian (or pdp endian) systems):

union u {
    uint32_t u32;
    uint8_t u8[4];
} ival, oval, ival2, oval2;
int x;

ival.u32 = /* some unsigned 32-bit value */;
oval.u32 = ƒ(ival.u32);

x = /* some value ∈ { 0, 1, 2, 3 } */;
ival2.u32 = ival.u32;
ival2.u8[x] ^= /* some nonzero octet */;
/* ival2 = ival where exactly one input octet differs */
oval2.u32 = ƒ(ival2.u32);
assert(oval2.u8[0] ≠ oval.u8[0]); /* first output octet differs */
assert(oval2.u8[1] ≠ oval.u8[1]); /* second output octet differs */
assert(oval2.u8[2] ≠ oval.u8[2]); /* third output octet differs */
assert(oval2.u8[3] ≠ oval.u8[3]); /* fourth output octet differs */

That is, I need a function where, when you change one of the octets in the input, all four octets of the output differ.

Since this is a 32-bit to 32-bit mapping, it can be a perfect mixing function (bijective, not one-way); this would be extremely beneficial because I could then replace the Final function of a 32-bit (nōn-cryptographic) hash (based on Jenkins’ one-at-a-time but tweaked) I’m using in the same context with it, too, and it would not lose any fractional bits of entropy from the input.

Of course I could do this “the simple way” with lookup tables, but the idea is to have this in only a few lines of code (that is, few machine instructions), either completely algorithmic, or with only, say, up to 256 bytes of read-only data. I bet there’s something like this already around. (My target CPUs are, for now, i486, sparc v8, 32-bit MIPS, but I’d want it in portable code, not assembly; C is just fine as long as it uses only unsigned integers, since I’ll most likely need to implement it in C.)

Please only include code snippets if they are true Public Domain (e.g. government work) or I can reuse them under the MIT Licence, the MirOS Licence, or the BSD Licence, or in a language not C with a permission for me to “rewrite the same algorithm” in C (while not copying a line of code); otherwise, please only include algorithmic descriptions that are enough for me to write C code from it. And nothing that’s legally dangerous or questionable of course ☺

My strength is coding, not mathematics (I already had to prove the bijectivity of the Finish function of my modified Jenkins-OAAT empirically, i.e. by trying all possible 2³² combinations), that’s why I thought to ask here. (No homework or commercial stuff, just trying to improve the world, in the context of the BSD Unix operating systems, and Open Source.)

At first glance, the MixColumn step from AES (actually, a single column of that transform) sounds like precisely what you're looking for.  It is invertable (AES depends on that), and it does have the property that if one input octet changes, then all four output octets are guaranteed to change.

Most commonly, it's done by table lookup; however there's no reason it couldn't be done by inline code (and that inline code ought to fit in 256 bytes).

There is such a function, called qht(), in some of my work.
For the whole context, see:
ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/

Here's the central bit of code & comment:

/*
Quasi-Hadamard transform
My own invention

Goal is to mix a 32-bit object
so that each output bit depends
on every input bit

Underlying primitive is IDEA
multiplication which mixes
a pair of 16-bit objects

This is analogous to the
pseudo-Hadamard transform
(PHT) originally from the
SAFER cipher, later in
Twofish and others

Conceptually, a two-way PHT
on a,b is:

x = a + b
y = a + 2b
a = x
b = y

This is reversible; it loses
no information. Each output
word depends on both inputs.

A PHT can be implemented as

a += b
b += a

which is faster and avoids
using intermediate variables

QHT is the same thing using
IDEA multiplication instead
of addition, calculating a*b
and a*b^2 instead of a+b and
a+2b

IDEA multiplication operates
on 16-bit chunks and makes
every output bit depend on
all input bits. Therefore
QHT is close to an ideal
mixer for 32-bit words.
*/

u32 qht(u32 x)
{
    u32 a, b ;
    a = x >> 16 ;       // high 16 bits
    b = x & 0xffff ;    // low 16
    a = idea(a,b) ;     // a *= b
    b = idea(a,b) ;     // b *= a
    return( (a<<16) | b) ;
}


Ring-LWE in other fields Can someone please tell me why in R-LWE we always make use of Cyclotomic fields, and specially those with degree equals to a power of $2$?
Can we use another fields without losing in hardness of the problem?
What about Quadratic fields for example?
Thank you!

We don’t always use power-of-two cyclotomics for RLWE. Many cryptosystems use other cyclotomics, or subfields thereof, or even other fields altogether. For example, many FHE schemes use non-two-power cyclotomics for “packing” and SIMD operations on plaintexts.
However, it is simplest to properly define and use RLWE over two-power cyclotomics, in large part because one can easily avoid using the “codifferent” (fractional) ideal $R^\vee$. (Other associated operations, like the NTT/CRT algorithm, are simpler in the two-power case as well.) So, this is probably why people tend to stick with two-power cyclotomics for RLWE.
The use of fields other than two-power cyclotomics can be justified by theory. The original LPR’10 paper proved the hardness of search-RLWE over any number field (not just cyclotomics), based on the conjectured quantum hardness of worst-case approximate-SVP on ideal lattices in that same number field. It also proved the hardness of decision-RLWE, assuming the hardness of search, for any cyclotomic number field (whether two-power or not); it turns out that this proof also works just as well for arbitrary Galois number fields, e.g., multiquadratics. Later, Peikert—Regev—Stephens-Davidowitz’17 directly proved the hardness of decision-RLWE over any number field (whether Galois or not), based on the same assumption as in the first sentence of this paragraph.
As for whether we can use quadratic fields, all of the above applies equally well for them, but the dimension is so small that worst-case SVP is easy—even on arbitrary lattices, not just ideal lattices. Similarly, RLWE over a quadratic field is trivially easy (except possibly if one used an enormous modulus, but this is not typical).

Power of 2 is explained in ePrint 2012/235:

the results from [LPR10] do not directly imply that the above problem is hard based on the worstcase hardness of lattice problems, except in the one case when $f(X) = X^n+1$ for $n$ a power of $2$, and thus most papers that use the Ring-LWE problem only use this one specific ring. The reason for this limitation is that the problem statement in [LPR10] requires $w$ to be in the dual ring of $R$ (which is a fractional ideal) and for the distribution of the noise to be a spherical Gaussian in the embedding representation of $R$. And it is only in the case that $R = \mathbb{Z}[X]/(X^n + 1)$ that the dual ring is simply a scaling of $R$ (thus, one can simply multiply by the scaling and end up in $R$) and the embedding is just a rigid rotation and a scaling (thus the spherical Gaussian distribution is not affected by the transformation). For all other cyclotomic polynomials, while it is possible to transform the problem that was proved hard in [LPR10] to the one described above, the transformation between the polynomial and embedding representations involves multiplication by a skewed matrix, and the dual of $R$ is a (possibly very) skewed fractional ideal of $R$. Therefore there is no obvious way to generate the noise directly in the ring $R$, nor work entirely in the ring $R$ without utilizing a transformation that can substantially increase the magnitude of the error polynomials.

Multiquadratic (and hence quadratic) fields are not used because there is a quasi-polynomial attack, which is much too long to describe here. For details see this 55-page paper.


Variant of the Decisional Bilinear Diffie Hellman problem I am working on a cryptographic scheme and I need to rely on the following problem, which I have nicknamed the "Hybrid Decisional Bilinear Diffie Hellman (hDBDH)" problem:

  Let $e: \mathbb G_1 \times \mathbb G_1 \rightarrow \mathbb G_T$ be an efficient bilinear pairing. Given the tuple $(g,g^x,e(g,g)^y,Q)$ as input, the problem is to decide whether $Q = e(g,g)^{xy}$

First, has this problem already been defined? Now, I want to prove that this problem is equivalent to the DBDH problem. I have the feeling that they are equivalent, but so far I only have that $DBDH \leq hDBDH$:

  Proof: From a hDBDH solver, we can construct a DBDH solver in the following way:

  Input: DBDH tuple = $(g, g^a, g^b, g^c, Q)$

  Output: Return $hDBDH_{\mathsf{solver}}(g,g^a,e(g^b,g^c),Q)$

Now I want to prove the other direction. Any ideas of how a DBDH oracle could be used to solve the hDBDH problem? Any ideas of why it is not possible?

Your problem is stronger than the DBDH problem because any oracle that responds to your query can also respond to DBDH. I think that you must try to reduce this problem to DDH. This means an input $(e(g,g),P=e(g,g)^x,R=e(g,g)^y,Q)$ and the decision whether $Q=e(g,g)^{xy}$.

Given $(g,g^x,e(g,g)^y,Q)$, let $Q' = Q/e(g,g)^y$. Give $(g,g,g,g^x,Q')$ to the DBDH oracle. It will decides whether $Q'$ is random or equal to $e(g,g)^x$. If $Q'$ is random, guess $Q$ random, otherwise guess $e(g,g)^{xy}$.

So they are equivalent, I would reckon.


Would it be possible to create a game where one would need to decrypt a simple encryption? This might sound pretty weird, but I was thinking of a game a person could play alone with a pen and paper.

I got this idea where the person would write a random four letter string on a paper, and would have to decode it. There would be a mean to verify if the person is getting closer to the goal or not. So, I decided to ask here.

Do you think it would be possible to create a simple game where one would have to decrypt a simple string (a bit like the BitCoin miners do, I guess?), where there would be a logical next step from every point during the decryption and where it would be possible to verify if the contemplated logical next step brings the player closer to the solution or not.

Similar Question: Toy encryption system that provides "hints"

Interesting, but not-quite-it option: Vigenère cipher (Wikipedia article)

Caesar cipher? Its a simple substitution cipher where you can solve with just a pen and paper.

Encryption is done by shifting each plaintext letter, x by n places the alphabet or mathematically, ENCRYPT(x) = (x + n) mod 26. Similarly, the decryption will be the reverse, DECRYPT(x) = (x - n) mod 26. (see wiki http://en.wikipedia.org/wiki/Caesar_cipher#Example)

So, you get a friend to pick a random n and compute the encryption for a randomly chosen four letter string (using free online calculators like http://online-calculators.appspot.com/caesar_ext/). You should not know both n and the plaintext. But the plaintext should be some english word or equivalent in order for it to make sense when you decrypt.

Then, you start the decryption process by trying out all possible values of n until the decrypted plaintext is make sense. If your first two/three decrypted alphabets is not an valid word, that means your chosen n value is wrong and you should try another n.

I'm guessing "No" for good encryption/hash algorithms where being even one bit off key or cycle results in garblygoop.

If this is just for the fun of the game, hash the garblygoop after each step and append that hash.

foo
fooGarbly = encrypt(foo|fooHash)
fooGarblyGarbly = encrypt(fooGarbly|fooGarblyHash)
fooGarblyGarblyGarbly = encrypt(fooGarblyGarbly|fooGarblyGarblyHash)

Each step would be best as a single stage of some non-impossibly-large possibility, like an XOR with a single byte.

I mean I assume the idea is to have this game be fun, so positive re-enforcement within our lifetime?

So a stage that could take to long to complete, like a permutation of a base64 alphabet could result in people just getting frustrated and quitting. (for good reason)


How do hashes really ensure uniqueness? This might seem an impractical and unnecessary conversation, but I feel it's something I need to clarify. Especially, as I just got my first developer job in a blockchain startup.

So hashes are said to generate the same thing for any information it sees, and it's only a one-way interaction.

As far as I understand, hashes are just long alphanumeric strings. If one computes hashes across all documents, keys, information, files, etc, over and over again- it's simply a matter of time until the same combination comes up again for different information (applying it across all possible contexts)? This might be an impractical test given size and possibility, yes, but is it this that makes hashes powerful, that it's practically impossible to recreate a hash that for any foreseeable endeavor it's fine, or is there some element that I'm missing that reduces even that extremely low probability to zero?
Is there any design constraint that prevents a very powerful computer to back-calculate the original data from a hash? Or is it simply that the design is so complex that it's simply a futile exercise to dream of such a large computer required for this task?
What's stopping a hacker or malicious middle man to hack open the software program or library that creates this "hash" and then use that library to create hashes of his/her own or mislabel some target company's hash with his/her own pointing to their version of the file? Especially since many applications, languages, and developers use hashing independently. Whichever is most weakly secured, we can use that to take on the rest?

Any resources are also appreciated.

The simple answer is that hashes don't ensure uniqueness. Very broadly, hashes behave like "deterministic random numbers" – deterministic in the sense that hashing the same data always gives the same answer; random in the sense that the value of the hash is basically unpredictable without actually computing it. And sufficiently unpredictable that, for a good cryptographic hash, we don't know any way of finding a string with a particular hash, except for trial and error.

In particular, cryptographic hash values are close enough to truly random that the birthday paradox applies. That is, if there are $k$ different values the hash can take and they're all equally likely, you have to hash roughly $\sqrt{k}$ documents before the probability of finding two with the same hash is greater than a half.  So, if you're using a 256-bit hash, you'd need to look at about $\sqrt{2^{256}}=2^{128}\approx 3\times 10^{38}$ documents to even have a 50/50 chance of finding two with the same hash. For comparison, that's about 200 documents for every nanogram of mass in the Earth.

Hashes, as you have observed, are not guaranteed to be unique for every input - they can't be, as they are of finite size, with potentially infinite inputs. They only "group" inputs into outputs (in the context of using hashes in data structures, this is sometimes referred to as a bucket). This is still useful.

By way of example, a very simple hashing function might be "given a non-empty, single-byte-character string input, use the first byte as the hash". Consider the properties of such a function:

Works for infinitely many arbitrary inputs (a string of any length).
There are at most 256 different output hashes (aka. buckets).
It is impossible to reconstruct the input, from only looking at the output. No matter how powerful your computer, it simply can't be done!

Even a very simple hashing function like this might be useful for some purposes (very simple dictionary data structures perhaps) - a comparison between two inputs can check their hashes, and trivially reject the possibility that they are the same 255 times out of 256. This could make a data structure using it quite a lot faster. But, if two inputs resulted in the same hash (known as a "collision"), the whole of each input would need to be compared, to see whether they are really the same or not.

Of course, such a simple hash function would be useless for hashing something like a password (and pretty poor for data structures too). A good hash function would have additional properties:

Sufficiently many output buckets for the task at hand. (For a data structure or file system hash, where collisions slow things down a little bit but are otherwise harmless, this might be 2^32 or much less. For a password, where collisions could breach security, this might be more like 2^512 or more!).
Even distribution between buckets. (Taking the first byte would probably put almost all strings in the same few dozen buckets - "A", "B", etc. - leaving 200 or so buckets empty).
The whole of the input should contribute to the hash. (Not just the first byte!)
On average, changing a single bit in the input changes half the bits in the output.

And depending on the purpose to which the hash will be put, there will be other considerations too:

Execution speed; slow fixed-time hashing functions can help defeat timing attacks in secure applications, but fast hashing functions are more performant if the hash is being used in a data structure for example.
Secure applications may want to add a random "salt" to the input before calculating the hash, to prevent looking up the input from a list of known outputs; that's somewhat out of scope for this question though.

The important thing to understand is that a hash does not guarantee uniqueness - it only assigns a confidence level to whether inputs are the same or not. This could be fairly weak (for file systems or data structures with a 32-bit hash) or very strong indeed (for passwords with a cryptographically secure 512-bit hash).


Pseudorandom number generator for which it is impossible to deduce the seed I'm looking for an RNG that in the case that an attacker would get all or part (most likely part) of the pseudorandom data, there will be no way for them to deduce the original seed more efficiently than brute force.

Which RNG's would comply with my requirements?

Random number generation is the generation of a sequence of numbers or
  symbols that cannot be reasonably predicted better than by a random
  chance... Source: Wikipedia

It follows that "an attacker [with] all or part" of the sequence cannot "predict any non-given [part of the sequence] better than guessing," as hinted in a comment, so guessing is the best an adversary can do.

The original question mentions pseudorandom data and an original seed, without relation to RNGs, so perhaps the question is missing something and I'm answering the wrong question.

Start with a seed, S.
The first block of data is SHA-3(S).
Each block from then on out is SHA-3 of the S xored with the previous block.


Why can't we reverse hashes? First off, I know hashes are 1 way. There are an infinite number of inputs that can result in the same hash output. Why can't we take a hash and convert it to an equivalent string that can be hashed back to the original hash output?

eg:

string: "Hello World"
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

unhash: "rtjwwm689phrw96kvo48rm64unc8oetb5kmrjiuh7h8huhi6dde5n5"
        (a real string that gives the same hash as "Hello World")
hashed: a591a6d40bf420404a011733cfb7b190d62c65bf0bcda32b57b277d9ad9f146e

...

Take a simple mathematical operation like addition. Addition takes 2 inputs and produces 1 output (the sum of the two inputs). If you know the 2 inputs, the output is easy to calculate - and there's only one answer.
321 + 607 = 928
But if you only know the output, how do you know what the two inputs are?
928 = 119 + 809
928 = 680 + 248
928 = 1 + 927
...

Now you might think that it doesn't matter - if the two inputs sum to the correct value, then they must be correct. But no.
What happens in a real hash function is that hundreds of one-way operations take place sequentially and the results from earlier operations are used in later operations. So when you try to reverse it (and guess the two inputs in a later stage), the only way to tell if the numbers you are guessing are correct is to work all the way back through the hash algorithm.
If you start guessing numbers (in the later stages) wrong, you'll end up with an inconsistency in the earlier stages (like 2 + 2 = 53). And you can't solve it by trial and error, because there are simply too many combinations to guess (more than atoms in the known universe, etc)
In summary, hashing algorithms are specifically designed to perform lots of one-way operations in order to end up with a result that cannot be calculated backwards.
Update
Since this question seems to have attracted some attention, I thought I'd list a few more of the features hashing algorithms
use and how they help to make it non-reversible. (As above, these are basic explanations and if you really want to understand, Wikipedia is your friend).

Bit dependency: A hash algorithm is designed to ensure that each bit of the output is dependent upon every bit in the input. This prevents anyone from splitting the algorithm up and trying to reverse calculate an input from each bit of the output hash separately.
In order to solve just one output bit, you have to know the entire input. In other words, when reversing a hash, it's all or nothing.

Avalanching: Related to bit dependency, a change in a single bit in the input (from 0 to 1 or vice-versa) is designed to
result in a huge change in the internal state of the algorithm and of the final hash value. Since the output changes so dramatically with each input bit change, this stops people from building up relationships between inputs and outputs (or parts thereof).

Non-linearity: Hashing algorithms always contain non-linear operations - this prevents people from using linear algebra techniques
to "solve" the input from a given output. Note the addition example I use above is a linear operation; building a hash algorithm using
just addition operators is a really bad idea! In reality, hashing algorithms use many combinations of linear and non-linear operations.

All of this adds up to a situation where the easiest way of finding a matching hash is just to guess a different input, hash it and see if it matches.
Lastly, if you really want to know how hard reversing a hash is, there's no better substitute than just trying it out for yourself.
All good hashing algorithms are openly published and you can find plenty of code samples. Take one and try to code a version that reverses each step; you'll quickly discover why it's so hard.

Clarification: The question has a flawed assumption. I mistakenly though in addressing the details of that flaw my answer was making that obvious. Just to make it really clear:

YOU CAN REVERSE SOME HASHES!!! BEING ONE-WAY IS NOT A REQUIREMENT OR CONCERN OF HASH FUNCTIONS!!! AND EVEN FOR THE SUBSET OF CRYPTOGRAPHIC HASHES IT ISN'T 100% GUARANTEED IRREVERSIBLE!

You mileage will vary depending on circumstances, but given the right circumstances you can reverse any hash with relative ease (the key in cryptography is denying the person trying to reverse your hashes sufficient information to do so).
Clarification - The question possibly was talking about cryptographic hashes, but did not say so. Just like all dogs are animals, but not all animals are dogs, cryptographic hashes are a subset of hashes, and there are many hashes in general use that are not appropriate to use as cryptographic hashes.

I can think in my head of a number of ways of making a useful hash function that would not be hard to reverse. You could also use the private/public ssh key pairs to make a hash that is reversible if you have the other key, but not otherwise.

The original answer goes on to explain what "hash function" really means (and being one way / irreversible is not a requirement for a hash function):

Hash in computer science was originally used for "Hash" tables and was concerned with distributing a non uniformly spread input set across a limited output set for efficient indexing. They are generally simplistic for fast execution, and are typically not cryptographically strong.

(A moderately dumb hash function can be as simple as taking the input as a number and getting the modulus of it using a prime number - this means all of the input bits affect the output result, but one possible input value is simply the hash as a bit string with zero padding on the left out to a byte boundary).

wikipedia has a useful short article: https://en.wikipedia.org/wiki/Cryptographic_hash_function

  A cryptographic hash function is a special class of hash function that has certain properties which make it suitable for use in cryptography.

Useful reading - it goes into more detail of the reversibility of hash functions intended to be hard to reverse. (Nothing is irreversible given sufficient time and processing power - you could just iterate through all possibilities - you just try and make the effort harder then its worth doing)

see also https://security.stackexchange.com/questions/63052/reversible-hash-function "Is there any reversible hash function?"


Decrypting small integers under RSA Let $(n,e)$ be an RSA public key. Suppose $c = m^e \pmod n$, where $c>1$ is a very small integer. For concreteness, say $c=2$ or $c=4$.

  Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Since the RSA problem is assumed hard, we do not know and can't find the factorization of $n$.
We know (from standard RSA) that $m=c^{\left(e^{-1}\bmod\varphi(n)\right)}\bmod n$ fulfills the requirement $c\equiv m^e\pmod n$, but we do not know how to compute $m$ without some extra info or oracle.

Is it hard to find $m$ under the RSA assumption (or any of its variants)?

Yes, but I have no better argument than: among integers $c>1$ independent of $n$, only exact $e^\text{th}$ powers are known to make it easy to solve the RSA problem for arbitrary $n$ too large to factor and odd $e>1$ making $(n,e)$ a valid RSA public key. In addition, there in no such $c$ in the interval $[2,2^e)$,  which with $e=65537$ as in a comment by the OP includes about all commonly used values of $n$, thus of $c$.
Solving $c\equiv m^e\pmod n$ for small $c$ is not necessarily hard for other $c$ and whenever $n$ is hard to factor. Proof by counterexample: $c=2$, $e=65537$, $n=(3^{65537}-2)/29$. I can't factor that $n$, yet it's easy to find the solution $m=3$.
More formally: I'm about as confident about the hardness of the RSA problem than I am about that problem restricted to small $c>1$, provided that $c$ is not a power of $e$, and that factors of $n$ are random distinct primes large enough to make factoring $n$ unfeasible. Yet I'd be quite surprised if we could prove the hardness of that restricted RSA problem on the basis of the hardness of the normal RSA problem.

Yes, you can do it and it is not difficult at all (the difficulty aka slowness increases as n increases). You must know, however, that all this becomes impractical with the rsa keys used in practice, all I am about to describe you is for pure educational purposes and you can test it with low numerical values.

You're actually solving:

$$ m ^ e \equiv c \pmod n $$

Where you know $ e, c, n $.

I will explain all the steps supposing that you already have solid knowledge.

First factorize $ n $, you will have two prime numbers $ p $ and $ q $ (see RSA key generation), now calculate:

$$
\phi (n) = (p - 1) (q - 1)
$$

Now you need to verify the invertibility of your $ c $ by verifying that:

$$
\gcd (c, n) = 1
$$
$$
\gcd(\phi(n), e) = 1
$$

If both are true, you have to find $ d $, the modular multiplicative inverse of $ e \pmod {\phi (n)} $. The modular multiplicative inverse can be found with the Extended Euclidean algorithm, it's an integer such that:

$$ c \cdot d \equiv 1 \pmod {\phi (n)} $$

Now all the solutions looks like this:
$ S = [c^d]_n  = \{ c^d +k  \cdot n, k \in \Bbb Z \}$
At this point what I recommend is to find a canonical representative for your solution class.

I'll show you an example about the canonical representative. Suppose that our set of solutions is:
$ S = [25^{11}]_{62} $

And $ 25^{11} = 2,3842 \cdot 10 ^ {15} $ and it's not very convenient to work on it.
After various calculations we verify that:
$$
[25 ^ 3]_{62} = [15625]_{62} = [62 \cdot 252 + 1]_{62} = [62]_{62} \cdot [252]_{62} + [1]_{62} = [1]_{62}
$$
So:
$$
[25^{11}]_{62} = [25^{3 \cdot 3 + 2}]_{62} = [25^3]^3_{62} \cdot [25 ^ 2]_{62} = [1]_{62} \cdot [625]_{62} = [5]_{62}
$$

Of course $ [5]_{62} $ is more comfortable to handle than $ [25^{11}]_{62} $


Is a book cipher provably secure? I've seen ciphers (usually in spy drama shows) that involve taking a book and writing down an index to individual characters. Essentially it's a keyed substitution cipher, where the key is the name and exact edition number of the book.

Example:

Imagine a book that has 500 pages, with approximately 60 lines per page and 80 characters per line. We might write 238:4:64 to specify that we're on the 238th page, 4th line, 64th character. A five character message might be encrypted into 114:25:22 374:41:46 182:17:62 63:53:8 50:8:18.

Without knowing what the book is, I would imagine this is provably secure as long as the person encrypting never re-used an index. Am I correct in this assumption?

For fun, you could try this out:  12:9:3 183:15:7 238:14:11 310:9:38 194:11:17 7:1:1

I'm using a page:line:character format, ignoring titles, spaces and punctuation. The book is Charles Darwin's On The Origin of Species, 6th edition.

N.B: I'm not trying to get you to crack this, just adding it because it nicely demonstrates the way this works :)

Using the book as a key is relatively similar to one-time pad, insofar as the book can be considered as a random stream of characters. But that's true only to some extent: a book consists of words, with meaning, which implies that characters which may appear at position 321:42:35 are not uncorrelated with characters which appear at positions 321:42:34 and 321:42:36. Therefore, merely not reusing exact index values is not sufficient; you should refrain from using two index values from the same word. This reduces the lifetime of a given book as a cipher key.

Another problem is in the "random choice". When you want to encrypt a letter, you must choose one of the index values in the book which correspond to that letter. Human beings are very bad at making random choices in their head. But non-random choices can exhibit biases. So the encryption process is important, and not completely described. An unbiased process would have you use dice to select at random the page, line and column; and if that does not correspond to your target letter, try again. That's tedious.

Also, in order to avoid reusing a given index, you must keep a list of the index places you have used, e.g. by marking the already used letters in the book. The book then ceases to be an inconspicuous object: instead of a brain-only key ("use this book"), you have a physical key ("use this, I mean that specific printed instance, book").

And, of course, anybody who has scanned millions of book and extracted the text into searchable computer structures, can easily try all existing books in a few minutes, and report a hit when the decryption result appears to look like meaningful words. So you are at the mercy of Google (and of whoever acquires Google's services).

Create your own "book".
Write a program that fills out pages of
cells, divided into columns and rows, with
randomly generated letters.   Then print out
600 such pages. This "book" becomes your key that the
NSA does not have a copy of....


Why does the recommended key size between symmetric and asymmetric encryption differ greatly? In various articles it is mentioned that for secure communications, the recommended key sizes are 128-bit key size for symmetric encryption (which makes it $2^{128}$ possible keys?) and 2048-bit key size for asymmetric encryption ($2^{2048}$ possible keys?).

Why do they differ so greatly? It seems like I am missing a very big part of the equation.

Symmetric encryption and asymmetric encryption algorithms are built upon vastly different mathematical constructs.

In typical symmetric encryption algorithms, the key is quite literally just a random number in $\left[0 .. 2^n\right]$, where $n$ is the key length. The strength of the key is based upon its resistance to brute-force attacks, where an attacker would need to perform an attack with complexity $O\left(2^n\right)$ to correctly guess the key.

Asymmetric algorithms, on the other hand, use a different kind of key. For example, an RSA modulus is of the form $m = pq$, where $m$ is the modulus, and $p$ and $q$ are two large, distinct, randomly-chosen prime numbers of roughly equal sizes. The strength of the key is based upon the modulus' resistance to factorization into its prime components. An attacker using a general field number sieve would need to conduct an attack with complexity $O\left(\exp\left(\left(\left(\frac{64}{9} + o\left(1\right)\right) \cdot n\right)^\frac{1}{3}\left(\log n\right)^\frac{2}{3}\right)\right)$ to factor the modulus (and thus break the private key), given a modulus of bit-length $n$.

To add to what was said above, with most symmetric cryptography, you simply can not guess the key - or can't know that you did*.  That's because EVERY possible arrangement of N bits is a perfectly legal key, meaning every possible plaintext block will come up.
You try one key and it decrypts to "1".  Another key decrypts to "0".  With another key, it decrypts as "a". Which is the right key?  You have no way of knowing.
Contrast public key crypto such as RSA or DH - when you've factored the number, you know that you have done so - you can know that you've discovered the right key.
ALL possible plaintexts will come up if the key size is the same as the block size.  If the key is shorter, still you'll get a huge number of possible plaintexts - generally every key decrypts to some plaintext.  Which makes it nearly impossible to know which is the right plaintext.

Re-using a symmetric algorithm in any particular block mode may or may not reveal any information.  Here I speak of just the cryptographic primitive itself.


Are there any standards of multi-prime RSA key generation? FIPS 186-3 specifies a method to generate DSA parameters.

Is there anything similar (official standard or widely-accepted recommendation) that shows how to generate the primes for multi-prime RSA?

Multi-prime RSA (also known as RSA-MP) is supported by PKCS#1v2. This standard supports a public key $(n,e)$ where the modulus $n$ is the product of $u≥2$ distinct odd primes: $n=\prod_{i=1}^u{r_i}$, with $1<e<n$ and $\gcd(r_i-1,e)=1$ (implying $e$ odd). The private exponent $d$ is such that $1<d<n$, and $e⋅d≡1\pmod{\operatorname{lcm}_{i=1}^u(r_i-1)}$. No other requirement on $(n,e,d)$ is given by PKCS#1v2. RSA-MP is $u>2$. Make $u=2$, $p=r_1$, $q=r_2$, and you are back to RSA in PKCS#1v1.

I know no standard about generation of RSA-MP key. However, for advice on the question of the bit size of $n$ and the number of factors $u$, one recommendable paper is Unbelievable Security: Matching AES security using public key systems, by Arjen K. Lenstra. See in particular the synthetic table giving $u:⌈\log_2\min(r_i)⌉$ for a given security level (in bits, with 2K3DES 95-bit), on a given year (with that parameter accounting for the author's evaluation of improvements on the algorithms, but not Moore's law), and according to two models.

Corrected: Following that size advice even at the 2K3DES level (for any entry starting Y2010), adding about $32/u$ bits per year to account for Moore's law (previously forgot that!), and choosing primes of one key randomly, my opinion is there's no need to worry about factorization attacks on that key till the Y2030 limit of that table. Notice that my endorsement assume that an adversary has no significant interest in factoring a single random key among extremely many.

I also like the short and graphical Multi-prime RSA trade offs, although it is restricted to 2048-bit modulus.

The main things to consider regarding $\log_2n$, $\log_2r_i$, and $u$, are:

$n$ should be large enough that GNFS factorization is not to fear. Considerations are just the same for regular RSA and RSA-MP, since the multiplicity $u$ of factors, or their size $\log_2r_i$, does not influence the expected run time of GNFS; only $\log_2n$ matters.
Each $r_i$ should be large enough that $n$ is safe from factorization by known algorithms primarily influenced by the size of a factor extracted (rather than the size of the composite to factor), in particular ECM (among such algorithms, ECM is the most likely to factor one particular key). In regular RSA, it is customary to choose the two primes of equal (or nearly equal) size: this makes it overwhelmingly likely that GNFS subsumes all other known factorization algorithms, including ECM, by a large factor. However, that does not hold for RSA-MP; and while finding one $r_i$ does not by itself make it possible to forge signatures or decipher, it must still be considered a fatal disaster, for GNFS can then tackle the factorization of the composite $n/r_i$ at greatly reduced cost. Therefore, it is customary to choose the minimum size of a factor based on estimation of the running time of ECM (considered a function of $\log_2r_i$, often ignoring the relatively marginal influence of $\log_2n$).
Then the best choice of $u$ is ${\log_2n}\over{\log_2r_i}$, rounded in some direction.

For this, I trust the aforementioned Unbelievable Security.

Details on the choice should take into account that typically $⌈\log_2n⌉$ is prescribed, in which case we'll probably use $\log_2r_i\approx ⌈\log_2n⌉/u$; if not, there is often little or no performance cost in rounding up $⌈\log_2r_i⌉$ up to the next multiple of a word size, like 32 or 64 bits, then use $log_2n\approx ⌈\log_2r_i⌉⋅u$.

It is customary that key generation standards for RSA key pairs add extra requirements in addition to those in PKCS#1v2. FIPS 186-3, a widely accepted standard, has the following requirements in section B.3.1; I'm trying my best to give the rationale:

The public exponent $e$ shall verify $2^{16}<e<2^{256}$. The lower bound is here because some attacks on poor RSA-based schemes are often easier when $e$ is small; the higher bound is for interoperability of public-key operations.
The bit size of $n$, $nlen=⌈\log_2n⌉$, should be 1024, 2048, or 3072 (note: in appendix B.3.1 of FIPS 186-3, the are references to 1024-bit, 2048-bit and 3072-bit primes; that shall be understood as the bit size of $n$, although that is composite). The limited choice maximize the critical interoperability of public keys; the lower bound also enforces a baseline security (according to NIST Special Publication 800-131A, for signature generation, 1024-bit is acceptable through 2010, deprecated from 2011 through 2013, and disallowed after 2013); the lack of 4096-bit or more is seen by some as an indication that ECDSA is the way to go.
The prime factors $p$, $q$ of $n$ shall be in range $[2^{(nlen-1)/2},2^{nlen/2}]$; this is primarily to ease interoperability of private keys across implementation.
$|p–q|>2^{nlen/2–100}$; this is a legacy of ANSI X9.31, where AFAIK it was introduced as a simple way to repel the rhetorical argument "but even Pierre de Fermat knew a factorization algorithm that could defeat RSA".
Primes $p$ and $q$ shall be chosen at random using the same algorithm (with $e$ an input), chosen among a few approved algorithms, falling into two main categories (random primes, and random primes with condition, with subdivisions depending on if the primes are probable or provable primes). This avoids poor algorithms, prevents optimizations of $d$, $dP$, $dQ$ giving questionable security, and eases validation of implementation, even allowing Known Answer Tests.
These approved algorithms are such that for $p$ of 512-bit, $p-1$ (resp. $p+1$) shall have a prime factor $p_1$ (resp. $p_2$) of more than 100 bits; same for $q$; if a similar condition is used (that's optional) for $p$ of 1024-bit (resp. 1536-bit), that should be more than 140 (resp. 170) bits. These requirements are intended to give insurance against Pollard's $p-1$ and William's $p+1$ factoring algorithm.
These approved algorithms come with a maximum size of the primes $p_1$ and $p_2$ discussed in (6.) AFAIK this just precludes choosing these primes $p_1$ and $p_2$ so big that the choice of primes $p$ is reduced to a point where this becomes an issue.

If I had to propose an adaptation of FIPS 186-3 for generating RSA-MP keys, it could be:

Unchanged (though personally I would choose $e=2^{16}+1$; and if you ask, I'd ease the lower bound to $e=3$, with no security impact when good schemes are used; but  that's independent of RSA-MP).
$nlen=⌈\log_2n⌉$ among 1024, 2048 or 3072 for full interoperability with FIPS-based signature verification devices; or changed to $1024≤nlen≤16384$ with $nlen≡0\pmod{64}$ on condition of agreement with potential signature verifiers, for more flexibility and future-openness. Recommendations on $nlen$ and $u$ based on the Unbelievable Security reference above, although with $u≤nlen/512$ no matter what.
Adapted to $2^{64⋅⌊(nlen/64+i−1)/u⌋-1/u}<r_i<2^{64⋅⌊(nlen/64+i−1)/u⌋}$. This ensures $⌈\log_2r_i⌉≡0\pmod{64}$, $⌈\log_2\prod_{i=1}^u{r_i}⌉=nlen$, and at most two different $⌈\log_2r_i⌉$.
Replaced by a test that any two $r_i$ differ in at least one of their 100 high-order bits (more in order to catch faults than for fear of Fermat factoring).
Kept for algorithms in the "random primes with condition" categories, with only the parameters of the approved algorithms adapted; see justification in (6.) below.
Kept, with the requirement that $⌈\log_2p_1⌉$ and $⌈\log_2p_2⌉$ are more than $60+5⋅⌈\log_2p⌉/64$. This linearly scales the value 100 and 140 in FIPS 186-3, and removes the option to ignore that for $⌈\log_2p⌉>1024$ by using an algorithm in the "random prime" category. My opinion is that this requirement makes sense in the context of RSA-MP: a rational adversary content with factoring any of many modulus (rather than factoring a particular modulus) should not start to use ECM on one or a few modulus; but rather should first try Pollard's p-1 on all the modulus, as the ECM strategy has a markedly lesser chance of success for a given effort (argument: Pollard's p-1 is used with great benefit by state-of-the-art factoring programs such as gmp-ecm; also see this related answer).
Kept; this really is just not changing the approved algorithms.

If you consider the security of an RSA key to be the ease of factoring (there are other considerations), then you should pretty obviously make them the same size.

You can think of a conventional N-bit key to be composed of two primes, but you can also look at it the other way -- that you take two primes that are $M_1$ and $M_2$ bits long and produce a key that is $M_1 + M_2$ bits long.

It's pretty obvious that you want the primes to be reasonably close in size and having them be the same bit-length long is just good practice. If they were lopsided, then it would be easier to factor the number.

We can extend that to say that you want multi-prime RSA, you want them all to be approximately the same size, as well. Take the example of a 2048-bit RSA key that consists of two 1000-bit primes and a 48-bit prime. It is straightforward to just declare this key to have the same strength as a 2000-bit two-prime key because it's easy to factor out the 48-bit prime. If you told people you had done that, they'd say that you had thrown away 48 bits.

If you create a two-prime RSA key with lopsided primes and tell people, they will get rightfully irritated. One could argue that the major reason for a multi-prime RSA key at all is to have a long key with shortened security. I believe that this is the reason you typically don't see them. It's hard to know what problem you're solving other than making the crypto weaker.


Is it required to use a random IV for AES-CBC with random key per message? I'm developing a program to encrypt and decrypt a file with AES-256/CBC in Java. And I want it to be safe enough. In my case, I generated random AES key for each file to encrypt and decrypt them.

My question is if it is necessary to generate a random IV for encrypt/decrypt or it is already secure enough with a random AES key and fixed IV.

You can use a null IV for all files ONLY if each file will be encrypted with a unique key. If you want to reuse the key, it's safer use a random IV for each file.

The issue is reusing the IV with the same key, when you do that, you reveal which files have the same first bytes. When you use a different key for each file, you don't have this problem.

No, you can't use a fixed IV, the IV needs to be unpredicatable.  There are two good answers why this is the case here.


Is there really no use for MD5 anymore? I read an article about password schemes that makes two seemingly conflicting claims:

MD5 is broken; it’s too slow to use as a general purpose hash; etc
The problem is that MD5 is fast

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents.  There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.
However, I was under the impression that MD5 still can be used as a non-cryptgraphic hash function:

Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.
Finding duplicate files.  By MD5-summing all files in a directory structure it's easy to find identical hashes.  The seemingly identical files can then be compared in full to check if they are really identical.  Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5. (In a way, this would be creating a rainbow table where all the files are the dictionary)

There are checksums of course, but from my experience, the likelihood of finding two different files with the same MD5 hash is very low as long as we can rule out foul play.
When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash.  But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"?  Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.

There is no published preimage attack on MD5 that is cheaper than a generic attack on any 128-bit hash function.  But you shouldn't rely on that alone when making security decisions, because cryptography is tricky and adversaries are clever and resourceful and can find ways around it!

  Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.

The question of whether to publish known-good vs. known-bad hashes after a compromise is addressed elsewhere—in brief, there's not much that publishing known-bad hashes accomplishes, and according to the citation, Linux Mint published known-good, not known-bad, hashes.  So what security do you get from known-good MD5 hashes?

There are two issues here:

If you got the MD5 hash from the same source as the ISO image, there's nothing that would prevent an adversary from replacing both the MD5 hash and the ISO image.

To prevent this, you and the Linux Mint curators need two channels: one for the hashes which can't be compromised (but need only have very low bandwidth), and another for the ISO image (which needs high bandwidth) on which you can then use the MD5 hash in an attempt to detect compromise.

There's another way to prevent this: Instead of using the uncompromised channel for the hash of every ISO image over and over again as time goes on—which means more and more opportunities for an attacker to subvert it—use it once initially for a public key, which is then used to sign the ISO images; then there's only one opportunity for an attacker to subvert the public key channel.
Even if you got the MD5 hash from a known-good source, collision attacks may still be a vector in cases like this.  Consider the following scenario:

I am an evil developer.  I write two software packages, whose distributions collide under MD5.  One of the packages is benign and will survive review and audit.  The other one will surreptitiously replace your family photo album by erotic photographs of sushi.
The Linux Mint curators carefully scrutinize and audit everything they publish in their package repository and publish the MD5 hashes of what they have audited in a public place that I can't compromise.
The Linux Mint curators cavalierly administer the package distributions in their package repository, under the false impression that the published MD5 hashes will protect users.

In this scenario, I can replace the benign package by the erotic sushi package, pass the MD5 verification with flying colors, and give you a nasty—and luscious—surprise when you try to look up photos of that old hiking trip you took your kids on.

  Finding duplicate files.  By MD5-summing all files in a directory structure it's easy to find identical hashes.  The seemingly identical files can then be compared in full to check if they are really identical.  Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5.

When I put my benign software package and my erotic sushi package, which collide under MD5, in your directory, your duplicate-detection script will initially think they are duplicates.  In this case, you absolutely must compare the files in full.  But there are much better ways to do this!

If you use SHA-512, you can safely skip the comparison step.  Same if you use BLAKE2b, which can be even faster than MD5.
You could even use MD5 safely for this if you use it as HMAC-MD5 under a uniform random key, and safely skip the comparison step.  HMAC-MD5 does not seem to be broken, as a pseudorandom function family—so it's probably fine for security, up to the birthday bound, but there are better faster PRFs like keyed BLAKE2 that won't raise any auditors' eyebrows.
Even better, you can choose a random key and hash the files with a universal hash under the key, like Poly1305.  This is many times faster than MD5 or BLAKE2b, and the probability of a collision between any two files is less than $1/2^{100}$, so the probability of collision among $n$ files is less than $\binom n 2 2^{-100}$ and thus you can still safely skip the comparison step until you have quadrillions of files.
You could also just use a cheap checksum like a CRC with a fixed polynomial.  This will be the fastest of the options—far and away faster than MD5—but unlike the previous options you still absolutely must compare the files in full.

So, is MD5 safe for finding candidate duplicates to verify, if you subsequently compare the files bit by bit in full?  Yes.  So is the constant zero function.

  (In a way, this would be creating a rainbow table where all the files are the dictionary)

This is not a rainbow table.  A rainbow table is a specific technique for precomputing a random walk over a space of, say, passwords, via, say, MD5 hashes, in a way that can find MD5 preimages for hashes that aren't necessarily in your table with fewer trial hash evaluations than a naive search.  (It can also be done in parallel with the search to not only speed it up but reduce the price/performance ratio.)  It is not simply a list of precomputed hashes on a dictionary of inputs.

(The blog post by tptacek in 2007 that you cited, and the blog post by Jeff Atwood that it was a response to, both misrepresent what rainbow tables are.  tptacek claims in 2019 that he DGAF about rainbow tables, perhaps because modern password hashes thwart them by the mere use of salts.  But password search under a fixed, unsalted hash function is only one application of the idea, for which the term was popularized.  Rainbow tables are relevant to any preimage search as noted in the original paper, such as AES keys given known plaintext/ciphertext pairs.  And it's not just a trivial time/memory tradeoff—a rainbow table preimage search can reduce price/performance ratio if parallelized.  This is why, for instance, AES-128 should not be construed to give ‘128-bit security’.)

  When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash.  But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"?  Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I don't know what tptacek meant—you could email and ask—but if I had to guess, I would guess this meant it's awfully slow for things like hash tables, where you would truncate MD5 to a few bits to determine an index into an array of buckets or an open-addressing array.

One of the things not mentioned here, is that the attraction of hashing algorithms, (like programming languages etc) is ubiquity. The 'reason' for using MD5 is:

everyone knows about it
it's implemented for pretty much every combination of architectures, OSs, programming languages etc
it's limitations are well understood.

This is important both from a practicality and security point of view.
It reasonable to expect someone to be able to handle it (practicality) and it helps devs audit the process and not skip steps because they are 'tricky' (security).

All that said, SHA is catching up and I think in time MD5 will die out, and when it does so, it will be quite quickly. Because its only a self-fulfilling-prophecy that it is popular in the first place, as there are normally better choices.

However, in the intervening time, that its widely adopted may well be a good reason in it own right to use MD5 (within it's limits).


Given a hash function; assuming domain % codomain = 0 and uniform collision distribution; how is entropy lost by collisions (not output truncation)? Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective. It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection, and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy. Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

In both cases, is it not preserving the entropy of the input up to the bit length of the output? Which is log2(4) to cover the 4 elements of the codomain.

Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective.

You seem to be using the standard technical term ‘uniform distribution’ in a confusing way.  Normally the uniform distribution on a finite set $A$ means the probability distribution $P$ with $P(x) = 1/\#A$ for all $x \in A$, where $\#A$ is the number of elements in $A$.

But you haven't mentioned a probability distribution so far; you seem to be abusing the term ‘uniform distribution’ to mean a function $f\colon A \to B$ with the following property: There is a single number $n$ such that for every $y \in B$, the number of elements in the domain mapped to $y$ is $\#f^{-1}(y) = n$.  (One might call such a function ‘balanced’, particularly if it's a boolean function—i.e., a function defined on bits whose output is a single bit—but this nomenclature is not standard like ‘uniform distribution’ is in probability theory.)

  It is widely agreed that randomly selecting a domain element results in log2(4) = 2 bits of entropy in the selection,

When you say ‘randomly selecting’, that doesn't specify what probability distribution you're randomly selecting by.  But if the entropy of the selection is log2(4), then clearly you mean the uniform distribution on the domain.  I recommend you specify a distribution whenever you talk about a random selection.

  and that because of being injective, the output of said function input this selection will also contain 2 bits of entropy.

Yes, if $f$ is injective then $H[f(X)] = H[X]$ for all random variables $X$ with any probability distribution, including the uniform distribution.

  If we double our domain element count to 8, then a random selection will have log2(8) = 3 bits of entropy.

Again, only if the random selection is uniformly distributed over the whole domain.

  Because of pigeonhole principle there are collisions, but we defined a uniform distribution, so each of the 4 codomain elements has two domain elements mapped to it.

Yes, if by ‘uniform distribution’ you mean a function that has the same number of preimages $\#f^{-1}(y) \subseteq A$ for any element $y \in B$ in the image.

  In the second case, clearly the 3 bits of entropy of the input can't be preserved in the output, but why would fewer than two bits of entropy be preserved? Isn't it still just equiprobably selecting an element from the codomain, given the lack of bias as defined by the uniform distribution of collisions?

Let's take a concrete example.

Define $f(x) = x \bmod 4$ on $\{0,1,2,\dotsc,15\}$.  You can easily confirm that $f$ has the property you called ‘uniform distribution’—every element of the image $\{0,1,2,3\}$ has exactly four preimages.  That is, under $f$, the following sets of inputs obviously collide:

$\{0,4,8,12\}$
$\{1,5,9,13\}$
$\{2,6,10,14\}$
$\{3,7,11,15\}$

Consider the following two probability distributions on the domain of $f$:

$P(x) = 1/4$ for $x \in \{0,1,2,3\}$, and zero otherwise.
$Q(x) = 1/4$ for $x \in \{0,4,8,12\}$, and zero otherwise.

Clearly $P$ and $Q$ have the same entropy—2 bits.  What is the effect of $f$ on the entropy?

Let $X \sim P$.  Then $f(X)$ has four possible outcomes each with equal probability 1/4, so the entropy is the same: $H[f(X)] = H[X] = 2\,\mathrm{bits}$.
Let $X \sim Q$.  Then $f(X) = 0$ with probability 1.  So $H[f(X)] = 0$.

Obviously neither $P$ nor $Q$ is the uniform distribution on the domain of $f$.  If we define $U$ to be that distribution—that is, $U(x) = 1/16$ for each $x \in \{0,1,2,\dotsc,15\}$, and draw $X \sim U$—then sure, $H[f(X)] = 2\,\mathrm{bits}$, the maximum possible.

Assuming our domain and codomain both have 4 elements, the uniform distribution of inputs to outputs means the function is injective.

No. This is not a cryptographic hash (what I call a pseudo random function).  Simplistically: Hash -> avalanche effect -> bin collisions ->  37% rate -> non injective -> codomain =/= domain.

You may be over thinking this.  NIST considers a thingie called "The narrowest internal width".  That means irrespective of what happens at the input, only the inner width matters.  Call it the throat size. Or, any size bucket leaks at the same rate if the hole is the same size. The inner width is usually what's output. An $n$ width cryptographic hash function can only output $ 2^n (1- \frac{1}{e})  $ unique values. The input domain is irrelevant because it must pass through the $n$ bit wide throat.

So if you conservatively round 37% to 50%, one bit of entropy disappears in a puff of XORs.

Remember 'A' in my previous diagram. It cannot be output due to collisions.


What is the point of digital signatures if confidentiality is violated? Lets say we use RSA as the signature method.

Alice wants to send a message to Bob and uses RSA signing. For that she signs her message with her private key. But everybody could now have access to her message if one just decrypts the signature with Alice's public key.

What is the point of digital signatures if confidentiality is violated?

Digital signatures are not designed for confidentiality. For the simplest counterexample to the implicit conclusion that there is no point to digital signatures without confidentiality, consider the use of PGP signatures. People may sign a message that they send to a public mailing list, allowing others to verify that they indeed said that and not an imposter pretending to be them.
Also, you seem to be misunderstanding how digital signatures work. It is not encryption that you decrypt to verify. A digital signature is a mathematical operation on a hash of the message that you verify is valid for the message. You don't recover the message itself from the signature.

To provide some additional context for the information provided in the other answers.

It is true that RSA is used to encrypt / decrypt information

However:

In almost all real-world cases RSA is not used to encrypt a large message being exchanged but rather just used to encrypt the hash of the message (this is signing / creating a signature for the message)

As other answers point out, this makes it possible for the receiver to know with certainty that the message has not been tampered with by some intermediary.

The steps are (a bit simplified for illustration purposes):

Alice creates message for Bob
Alice creates a hash for the message
Alice encrypts the hash value using her private key - this 'encrypted hash value' is the signature for the message
Alice sends the message, in clear text, plus the signature (encrypted hash value) to Bob
Bob creates a hash for the message (using the same hash algorithm as Alice used in step 2)
Bob decrypts the encrypted hash value provided by Alice, using Alice's public key
Bob compares his hash value for the message (from step 5) with the decrypted hash value (from step 6)

If the two hash values compared in step 7 are the same, Bob knows with certainty that the signature was created by Alice (since only she has access to her private key) and that the message he received was exactly how Alice authored it, i.e. no one has made changes to the message.

On the topic of confidentiality, encrypting the message itself is almost always done using an encryption algorithm other than RSA (since RSA is slow and optimized for encrypting small information sets). This can be accomplished many different ways but one option is to add to the steps:

Alice creates message for Bob
Alice encrypts the message using a symmetric key encryption algorithm using key of her choosing that only she knows
Alice encrypts the symmetric key using Bob's public key and adds it to the end of the message
Alice creates a hash for the message
Alice encrypts the hash value using her private key - this 'encrypted hash value' is the signature for the message
Alice sends the encrypted message, plus the signature (encrypted hash value) to Bob
Bob creates a hash for the message (using the same hash algorithm as Alice used in step 4)
Bob decrypts the encrypted hash value provided by Alice, using Alice's public key
Bob compares his hash value for the message (from step 7) with the decrypted hash value (from step 8)
If the hashes match, Bob takes the encrypted symmetric key value from the end of the message and decrypts it using his secret key
Bob decrypts the encrypted message using the same symmetric encryption algorithm Alice used in step 2, using the symmetric key value from step 10

With these steps Bob knows Alice authored the message and only he is able to decrypt it since the symmetric key used to encrypt the message was encrypted using his public key. I.e. only Bob is able to get the symmetric key value since only he has access to his private key.


Entropy of system data - use all and hash, or trim least significant bits? I'm working on a background entropy collector for key generation that monitors hardware and produces an entropy pool.

Here's my list of sources:

Mouse position
Keyboard timings (i.e. time between keystrokes)
Network

Bytes sent
Bytes received
Datagrams sent
Datagrams received

Processor (per CPU)

Interrupts/sec
Queued DPCs/sec
C3 Transitions/sec

Memory

Page Faults/sec
Transition Faults/sec

Disk

Write bytes/sec
Read bytes/sec

Process (total)

IO Read Bytes/sec
IO Write Bytes/sec
IO Other Bytes/sec
Page Faults/sec

USB

Interrupt Bytes/sec
Controller PCI Interrupts/sec

Time taken to fetch all of the above data (measured using QueryPerformanceCounter)

These stats are collected once every 330ms. At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool, giving me roughly 200 bytes per second.

The pool is initially populated by the hash of a single timestamp value indicating the system boot time. When the pool reaches 64KB, I xor with the oldest 64-byte block. This is somewhat warned against in another question, but I don't foresee a problem because the pool is very large and the reasoning for removing old data is size. Keys are generated by computing a cryptographic hash of the entire entropy pool.

This seems reasonable, but I wonder whether SHA512 is overkill. Would I be better off extracting the least significant bits of each statistic into a bitstream? If so, how many? Are there any other issues with my approach?

What you are doing sounds a lot like what the /dev/random and /dev/urandom or the PRNGD on many systems already do:
those systems take an arbitrary large sequence of numbers (from a true hardware random number generator if available, or else from environmental noise such as keystroke timing)
and feed it into a CSPRNG.
The CSPRNG internally maintains an "entropy pool",
and thoroughly "mixes" the pool whenever it produces a new output value.
The output is made available via /dev/random and /dev/urandom .

Have you considered possibly using the /dev/random or PRNGD already running and available on your system?
Have you considered possibly downloading the source code to some CSPRNG that has already been written, tested, debugged, and checked for security flaws, rather than writing your own from scratch?

At the moment, I'm just globbing all the data into an array of around 100 bytes. I then hash the array using SHA512, to add a total of 64 bytes to the entropy pool
Would I be better off extracting the least significant bits of each statistic into a bitstream?

Rather than collecting a batch of data, hashing it, and then feeding that into the CSPRNG,
it's better to simply feed the batch of data directly onto the CSPRNG.
(The CSPRNG already handles the "hashing" stuff internally).
At best, your hash operation preserves whatever entropy exists in the source data;
at worst, it is unnecessarily throwing away some of that entropy.
SHA512 is an excellent hash function, so hashing the incoming data with SHA512 is OK but unnecessary.
(The idea of "XOR all the collected bits" seems to throw away too much entropy).
The high-order bits of most of those statistics have very little usable entropy -- however, assuming the CSPRNG is properly written, that doesn't hurt anything.
A properly written CSPRNG is just as secure even when one of the inputs doesn't have any entropy -- such as an input that is always "000000000000000...".
If, hypothetically, you are forced to cut back on the number of inputs to your CSPRNG in order for some reason,
you would want to preserve as much entropy as possibly by cutting out such zero-entropy (all-zeroes) and low-entropy (high-order bits of these other stats) before cutting out higher-entropy sources.

When the pool reaches 64KB...

Wow. That many bits in the entropy pool is overkill in our universe.

Keys are generated by computing a cryptographic hash of the entire entropy pool.

Yes, that's how most CSPRNG produce their output values.

FreeBSD and AIX implement /dev/random using the Yarrow algorithm
OpenBSD implements /dev/random using an algorithm based on RC4 (is this the same as ISAAC ?)
Fortuna
My understanding is that many other CSPRNG implementations have a way to feed in more bits of entropy.

(I'm re-using a lightly edited of a previous answer I wrote,
PRNG taking advantage of very large seed
)

I would avoid the approach. While at first it looks like you're collector the most diverse entropy, most "sources" you use tend to create repeatable or sequentially alike data. This is underlined by the fact that you're collecting the stats at fixed intervals.

If your goal is to create real entropy for key generation you should be aware of the security implications as it's bound to happens that frequently, not enough entropy is introduced into your hash and your hash is bound to reduce itself to a smaller group of colliding hashes.

The question if SHA512 is overkill underlines the issues with your approach, as a hash can only be as safe as the entropy the sources provide. Since your hash is only represents the final result of your data, it wraps it up to a bit-length to something smaller, and therefore more predictable.

You might as well simply XOR all the "collected bits" when incoming, and achieve a better randomness than hashing the aggregate data into a hashed result with whatever algorithm.

My 2 cents: poll the data at random intervals, and poll random pieces from the incoming data, XOR-ing multiple sources randomly too (and not all at the same time). Finally, cut a fixed piece of bits from a random position and store that. This approach is not only faster, but also produces less predictable and more random data. If implemented correctly, this would enable streaming encryption/decryption due to it's speed. Hashing can - even when modern computers are really fast - waste valuable time that - when it's summed up to the time lost per day, week or month - something you would want to avoid whenever possible. After all, in cryptography and everywhere else: every microsecond counts.


Why hash or salt when signing? EDIT: Just wondering why was this question closed as a duplicate of a question asked almost 2 years after this one...
I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV.
Why is that needed?

A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this:

  Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA signature" (without a hash and any padding), you now have a message $m$ with a fitting signature $s$.

With a hash, the signature checking equation is $H(m) \equiv s^e \mod n$ instead of $m \equiv s^e \mod n$, and this does not allow to create a message $m$ fitting to an arbitrary signature $s$ (assuming the hash function is preimage-resistant). Beware however that it is remains possible to create working $(m,s)$ pairs given the capability to obtain the signatures $s_j$ of chosen messages $m_j\ne m$, using an attack devised by Desmedt and Odlyzko (see section 3 of this paper).

(The padding scheme normally present in signatures serves the same purpose, and is designed to also resist chosen-messages attacks.)

Salts add an additional level of security.

All your passwords are hashed and saved in your database using some algorithm or the other. This hash is generated the way and is uniform for all your users (assuming they all have the same password). By using a salt you will basically be giving different users with the same password different hashes.

And that means that if the attacker figures out how to get your plaintext password by creating a rainbow table. He wont just magically have everyone elses password as well. He's goign to have to generate a rainbow table for every user individually.

Note: I am no expert. But I did take a class on security once and that's what I remember from it. Hopefully this answers your que


Is it possible to verify a clearsigned message with a short public key (fingerprints)? For practical reasons, I'd like people to be able to post clearsigned messages with their public key fingerprints (8E570D9F7F70256595769E49F9BC5BCAD7E18635) for the system to check. However, the libraries I see all seem to require a full public key certificate to do verification. Is there a way to do it with just fingerprints?

No, it isn't possible to use a fingerprint as a key to verify signatures.

The PGP fingerprint is a hash of the public key material, see RFC 4880 section 12.2; it doesn't actually contain the public key, and as such it is not correct to speak of a fingerprint as a “short public key” as you did in your question—it is more like a unique key identifier.

A hash function maps an arbitrary-length input to a fixed-length output. One of the requirements for a cryptographic hash function is preimage resistance, i.e. given an output hash, it is difficult to find the input value to the hash. In this case, the input value to the hash would be the public key that was put into the hash. More to the point, the hash function that is used to generate the fingerprint effectively “loses” the public key information that you need to verify signatures.

Considering the size of the public key data, just trying potential public keys by brute force until you re-create a fingerprint to re-discover the public key information at runtime will also not work because it is too computationally expensive.

You can look it up in a keyserver - that would be secure, as long as you have a sufficiently long fingerprint.


Can we use fixed Beaver's multiplication triples many times? In the secure computation based on GMW and SPDZ style approaches, we use multiplication triples to gain efficient online computation time.

Can a same triples be used multiple times?
Is there any need to update the triples?

If you reuse the same multiplication triples, then you leak information about the secret shared values that you multiply.

Let's recall how the multiplication works in Beaver's protocol for secure evaluation of arithmetic circuits. Protocols like the ones from the SPDZ family follow Beaver's blueprint and "just" add some additional magic on top for getting active security. Let's focus on the simple approach of Beaver, since you will already run into problems there, when you reuse multiplication triples:

Assume you have a secret shared values $[x]$ and $[y]$, where the notation $[x]$ means that $x = \sum^n_{i=1}x_i$ and party $P_i$ has share $x_i$.
Let $[a],[b],[c]$ with $c = a \cdot b$ be a secret shared multiplication triple.

To multiply $[x]$ and $[y]$ you compute $[z]$, where $z = x \cdot y$, as follows:

Each party computes $$[d] := [x] - [a] = [x-a]$$ and publishes its share thereof (thus revealing $d$)
Each party computes $$[e] := [y] - [b] = [y-b]$$ and publishes its share thereof (thus revealing $e$)
All parties locally compute $$[z] = [c] + [x]\cdot e + [y] \cdot d - e \cdot d$$ (Note that when we want to add or subtract a public value like $e \cdot d$ to a secret shared value, then only one of the parties adds the public value to its shares.)

Now if you were to reuse the same multiplication triple $[a],[b],[c]$ in another multiplication of some other secret values $[u]$ and $[v]$, then you would reveal $$d' = u - a$$ and $$e' = v - b$$

From this information, a honest-but-curious party could now compute
$$ d - d' = (x-a) - (u-a) = x - u$$
This is clearly bad, since it directly reveals the difference between two secret values $x$ and $u$. The same, with $e$ and $e'$, obviously also works to compute the difference $y - v$.

For this reason it is crucial for the security of the protocol that you use every multiplication triple at most once!

There is a problem with this explanation.

At stage 3 you write:
"  3. All parties locally compute [z]=[c]+[x]⋅e+[y]⋅d−e⋅d  "

You mean that:

z_1 = c_1 + x_1 * e + y_1 * d - e*d

...

z_n = c_n +x_n * e + y_n * d - e*d

When you compute the sum of all shares you want z=xy. However,

z_1+...+z_n = c + x * e + y * d - n * ed = c + x(y-b) + y*(x-a) -n*(x-a)*(y-b) =

= c + xy -xb +xy -ya -n*(xy-ay-xb+ab).

For n different than 1, this is not what you want.