Secondary hash function utility, regarding data destruction? Given that hash functions are inherently irreversible, would they not then be useful in applications where it's desired to overwrite sensitive data? (i.e. Darik’s Boot and Nuke)

Specifically, why should hash functions not be used for data clearing?

Specifically, why should hash functions not be used for data clearing?

I take it you mean that we would overwrite the storage with output produced by feeding its sensitive contents to a hash function.  The problem then is that this output, being a function of the data you're overwriting, therefore provides information about that input.

In particular, it could be used to efficiently test hypotheses about the content of the overwritten data.  This is the same principle as password cracking; just like password hashes allow you to quickly test password guesses, the overwritten disk sectors' contents could perhaps be used to test whether the disk contained or not some specific data before being overwritten.

You may think that this sounds like a very unlikely attack, and you could well be right about that.  But why allow it in the first place?  Particularly when the alternative is simple enough: overwrite with random or pseudorandom data that has no correlation at all to the sensitive contents you're overwriting.

You could argue that they are.  If you use a utility like shred it will over write a disc with pseudo random data which might be generated via a cryptographically secure random number generator.  These are often based around hash functions, using some sort of counter loop.  Boot and Nuke can use the PRNG ISAAC which is a random number generator based on hashing it's output.

You realise that this topic is a can of worms located in the middle of a mine field?  It is very very difficult to destroy data. There are no known 100% reliable means of soft data erasure for SSDs or flash drives.   More details can be found by addressing the good folks at security.SE.


Is it correct to concatenate (pseudo-)random byte values before testing them with the NIST suite or tools like dieharder? Let's assume I have thousands of (pseudo-)random 4-byte values. The values are 4 byte random values which a blackbox device gave me. I got these values by requesting them. In between others might have requested them too (I don't know about that). Now I'd like to test them for randomness. There are tools for this like dieharder or the NIST Statistical Test Suite.

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?

Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before? (Because the test tool wouldn't know that I had 4-byte values in the beginning, once I concatenated them?).

Edit:
The question is meant as a general question. The actual underlying problem is how to examine seed values for randomness, which I obtained via UDS Security Access (see https://en.wikipedia.org/wiki/Unified_Diagnostic_Services#Services $27).

Is it valid to just concatenate the thousands of 4-byte values so that I end up with one very long byte (n * 1000 * 4 byte) stream which I then feed into these tools?
Is it correct that it doesn't matter for the tests how long the individual values (4-byte) were before?

Yes for both. The fact that others may have obtained (and removed) randomness from the source while it was sampled, or/and that the samples are grouped in some particular way for testing, does not prevent from testing what's obtained. And that can not cause a valid test to fail more often, assuming the source's full output is indistinguishable from random (including for said others trying to make the test pass, or fail).
On the other hand, those same facts could make the test become arbitrarily less capable of detecting some faults. As an extreme example, a source that always repeat each byte that it outputs might become indistinguishable from true random if we sub-sample its output, keeping every odd byte.

The actual underlying problem is how to examine seed values for randomness.

Dieharder or the NIST Statistical Test Suite alone can't give any assurance of that. At best, they can indicate a fail with high confidence, which saves from performing further work (beyond checking that the test was correctly performed/works). If they indicate pass, no other firm conclusion can be reached on that basis alone. It is needed to know how the seed values are generated, and that can't be determined by a test of the seed values.

As a proof that these tests can not validate the fitness for cryptographic purposes of a source of unknown build, consider a RNG with:

a real-time clock keeping UTC time in second, initializing 128-bit register at startup after a delay of 1 second
with the register then repeatedly encrypted using AES-256 and a key to produce the next register value, which concatenated 128-bit values form the bulk of the output, queried over a gigabit Ethernet interface.

This source will pass any black-box testing that does not reject a good generator, including tests scrutinizing power-on, as long as the test does not use AES-256 and the correct key.
But this source is disastrous from a cryptographic perspective. Given the key and when the black box was started, its output is predictable. Given the key and a fragment of a sequence, all the rest can be computed. Some party eating bytes from the source in the background can even decide what another party using the source will get!

As pointed by others, many statistical tests, including some of the DieHarder suite, require megabytes of input. The full Dieharder needs gigabytes.
However, in the context of a cryptographic RNG of proper structure, these tests requiring a lot of input are not needed. The tests that make sense are those on the unconditioned (or lightly conditioned) entropy source, used to seed a CSPRNG. The source is validated by tests which purpose is to ensure that it delivers some entropy. The CSPRNG is validated by examination of its design, and Known Answer Tests. Some monitoring in the RNG should detect a fault in the source and in this case prevent output. The combination might be checked by an extra test of the whole thing, but that's meaningful only if there is some assurance, obtained otherwise, that the overall structure really is the source seeding the CSPRNG, and being monitored.

Yes concatenate them, but you'll find that randomness is somewhat of a function of sample size. The more stringent the test wanted, the larger a sample is required.  Your idea of using dieharder is a non starter really, considering that a full un-throttled run (as shown here) can use ~250GB of data. You'll just wind yourself into spaghetti.

You're looking at a ball park figure of say 40KB. That's actually not a very long data set these days.  I suggest that rather than waiting till the end of the world to generate a dieharder test set, you consider ent. It operates ideally with 500KB of data, but will produce a reasonable test with 40KB.  If the numbers look reasonable, there is no cause for alarm.  It will be very difficult indeed for anyone to challenge the randomness of a good 40KB ent test result.  If any of the 5 individual tests fail dismally, be alarmed.

Expect something like this if the black box is good:-

Entropy = 7.995909 bits per byte.

Optimum compression would reduce the size
of this 40000 byte file by 0 percent.

Chi square distribution for 40000 samples is 225.80, and randomly
would exceed this value 90.59 percent of the times.

Arithmetic mean value of data bytes is 127.3208 (127.5 = random).
Monte Carlo value for Pi is 3.129312931 (error 0.39 percent).
Serial correlation coefficient is -0.003441 (totally uncorrelated = 0.0).

As the other answers have said, you can't validate the unpredictability of the numbers without taking the box apart. This is about the best you can hope for.

You may be able to fool ent with quite a concerted effort, but I'm sceptical. The real issue is why would someone be generating engine management data for real vehicles with the aim of fooling ad hoc ent tests?  The would be weird.

Since some people advocate continuing with dieharder in this case, the following is the result of a dieharder run against 40KB of perfectly random IID data from /dev/urandom.  It's totally rubbish and tells you absolutely nothing about the distribution of the sample.  The thing to note though is the rewinds. Just the last test (dab_monobit2) rewound > 6 million times. That suggests     dieharder   inherently requires ~ 240GB of data without it having to regurgitate the same values over and over and over...

# The file file_input_raw was rewound 384 times
   diehard_birthdays|0.00065267|   WEAK
# The file file_input_raw was rewound 10384 times
      diehard_operm5|0.00000000|  FAILED
# The file file_input_raw was rewound 23184 times
  diehard_rank_32x32|0.00000000|  FAILED
# The file file_input_raw was rewound 29184 times
    diehard_rank_6x8|0.00000000|  FAILED
# The file file_input_raw was rewound 31805 times
   diehard_bitstream|0.00000000|  FAILED
# The file file_input_raw was rewound 52777 times
        diehard_opso|0.00000000|  FAILED
# The file file_input_raw was rewound 66758 times
        diehard_oqso|0.00000000|  FAILED
# The file file_input_raw was rewound 73311 times
         diehard_dna|0.00000000|  FAILED
# The file file_input_raw was rewound 73951 times
diehard_count_1s_str|0.00000000|  FAILED
# The file file_input_raw was rewound 86751 times
diehard_count_1s_byt|0.00000000|  FAILED
# The file file_input_raw was rewound 86991 times
 diehard_parking_lot|0.00000000|  FAILED
# The file file_input_raw was rewound 87151 times
    diehard_2dsphere|0.00000000|  FAILED
# The file file_input_raw was rewound 87271 times
    diehard_3dsphere|0.00000000|  FAILED
# The file file_input_raw was rewound 110366 times
     diehard_squeeze|0.00000000|  FAILED
# The file file_input_raw was rewound 110368 times
        diehard_sums|0.00183407|   WEAK
# The file file_input_raw was rewound 111368 times
        diehard_runs|0.00000000|  FAILED
        diehard_runs|0.00000000|  FAILED
# The file file_input_raw was rewound 125325 times
       diehard_craps|0.00000000|  FAILED
       diehard_craps|0.00000000|  FAILED
# The file file_input_raw was rewound 325325 times
 marsaglia_tsang_gcd|0.00000000|  FAILED
 marsaglia_tsang_gcd|0.00000000|  FAILED
# The file file_input_raw was rewound 326325 times
         sts_monobit|0.00000000|  FAILED
# The file file_input_raw was rewound 327325 times
            sts_runs|0.00000000|  FAILED
# The file file_input_raw was rewound 328325 times
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
          sts_serial|0.00000000|  FAILED
# The file file_input_raw was rewound 330325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 334325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 340325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 348325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 358325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 370325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 384325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 400325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 418325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 438325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 460325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 484325 times
         rgb_bitdist|0.00000000|  FAILED
# The file file_input_raw was rewound 486325 times
rgb_minimum_distance|0.00000000|  FAILED
# The file file_input_raw was rewound 489325 times
rgb_minimum_distance|0.00000000|  FAILED
# The file file_input_raw was rewound 493325 times
rgb_minimum_distance|0.00000000|  FAILED
# The file file_input_raw was rewound 498325 times
rgb_minimum_distance|0.00000000|  FAILED
# The file file_input_raw was rewound 500325 times
    rgb_permutations|0.00000000|  FAILED
# The file file_input_raw was rewound 503325 times
    rgb_permutations|0.00000000|  FAILED
# The file file_input_raw was rewound 507325 times
    rgb_permutations|0.00000000|  FAILED
# The file file_input_raw was rewound 512325 times
    rgb_permutations|0.00000000|  FAILED
# The file file_input_raw was rewound 522325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 542325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 572325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 612325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 662325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 722325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 792325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 872325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 962325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1062325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1172325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1292325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1422325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1562325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1712325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 1872325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 2042325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 2222325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 2412325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 2612325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 2822325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 3042325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 3272325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 3512325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 3762325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 4022325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 4292325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 4572325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 4862325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 5162325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 5472325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 5792325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 6122325 times
      rgb_lagged_sum|0.00000000|  FAILED
# The file file_input_raw was rewound 6123325 times
     rgb_kstest_test|0.00000000|  FAILED
# The file file_input_raw was rewound 6138685 times
     dab_bytedistrib|0.00000000|  FAILED
# The file file_input_raw was rewound 6139965 times
             dab_dct|0.00000000|  FAILED
Preparing to run test 207.  ntuple = 0
# The file file_input_raw was rewound 6151212 times
        dab_filltree|0.00000000|  FAILED
        dab_filltree|0.00000000|  FAILED
Preparing to run test 208.  ntuple = 0
# The file file_input_raw was rewound 6154094 times
       dab_filltree2|0.00000000|  FAILED
       dab_filltree2|0.00000000|  FAILED
Preparing to run test 209.  ntuple = 0
# The file file_input_raw was rewound 6160594 times
        dab_monobit2|1.00000000|  FAILED

You find that the full dieharder is best suited to photonic based TRNGs where it's commonly used.


Effective key length of Two-Key Triple-DES What's the effective key length of Two-Key Triple-DES, for some (possibly several) reasonably well-defined and sensible definitions of effective key length, say assuming attack using ample chosen plaintext?

A sensible definition of effective key length (in bits) of a block cipher under some attack assumptions could be: one plus the base-2 logarithm of the number of evaluations of the cipher (for arbitrary key and plaintext) that could have been made for a cost equivalent to the expected cost of recovering the key using the best known attack applicable to said assumptions.

By this definition, for any secure block cipher, effective key length is at most about the number of key bits that can influence the output. Proof sketch: consider brute force key search, and that a block cipher having a cost of evaluation not much larger than a comparison would be insecure.

Two-Key Triple-DES (also known as TDEA Keying option 2) is a 64-bit block cipher with a 16-octet key, of which 112 bits can influence the output, defined by
$$\operatorname{3DES}(K_1\|K_2,P)=\operatorname{DES}(K_1,\operatorname{DES}^{-1}(K_2,\operatorname{DES}(K_1,P)))$$
where $K_1$ and $K_2$ are 8-octet keys, of which 56 bits can influence the output.

NIST has stated that with $2^{40}$ plaintext/ciphertext pairs, the security is at least 80 bits, but gives no upper bound beyond the obvious 112 bits, which is quite a wide margin.

The effective key length of 3DES assuming two or three chosen plaintexts (per the definition proposed) is no more than about 109.5 bits (see proof below); that obviously can only be lower with more (chosen) plaintext/ciphertext pairs.

One of the best known attack is: Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption (in proceedings of Eurocrypt 1990); but it is not easily translated into effective key length, at least for the definition that I propose, for the cost is dominated by memory accesses.

The 109.5 bits upper bound stated is 112, minus $\log_2(3)\approx 1.58$ because the core attack loop only performs a DES thus is about 3 times less costly than a 3DES, minus 1 thanks to the the complementation property, plus a little something for the two comparisons in the core loop.

More in details: 3DES inherit from DES the complementation property:
$$\forall K, \forall P, \operatorname{3DES}(\overline K,\overline P)=\overline{\operatorname{3DES}(K,P)}$$
and that allows a brute force search with maximum cost quite close to $2^{111}$ DES encryptions, that is $\approx2^{111}/3$ 3DES encryptions (and expected cost half that), with two or three chosen plaintexts:

obtain, for some $P$, the ciphertexts $\operatorname{3DES}(K,P)\to C$ and $\operatorname{3DES}(K,\overline P)\to C'$
for each of $2^{55}$ value of $K_1$ with high bit zero

compute $\operatorname{DES}(K_1,P)\to A$, $\operatorname{DES}^{-1}(K_1,C)\to B$, $\operatorname{DES}^{-1}(K_1,\overline{C'})\to B'$
for each of $2^{56}$ value of $K_2$

compute $\operatorname{DES}^{-1}(K_2,A)\to X$; this step dominates the cost
if $X=B$ (implying $\operatorname{3DES}(K_1\|K_2,P)=C$)

if $\operatorname{3DES}(K_1\|K_2,\overline P)=C'$, output $K_1\|K_2$

if $X=B'$ (implying $\operatorname{3DES}(\overline{K_1\|K_2},\overline P)=C'$)

if $\operatorname{3DES}(\overline{K_1\|K_2},P)=C$, output $\overline{K_1\|K_2}$

This is guaranteed to output the right $K$, and (heuristically) will seldom output others for random choice of $K$; and then another plaintext/ciphertext pair allows to rule out a false positive with overwhelming odds. The cost is dominated by $2^{111}$ DES at step (1); $2^{112}$ relatively cheap comparisons at steps (2) and (3), with very occasional false positives costing an expected $3\cdot 2^{48}$ evaluations of DES for their resolution; and the $3\cdot 2^{55}$ DES for computation of $A$, $B$, $B'$.

This attack is impractical: the total effort devoted to bitcoin mining (which is comparable in nature) as of February 2016 would have explored much less than one millionth of the search space for a single attacked key.

Des is 56 bits/key   with 2Des   the key is is 56*2 or 112bits.  It is not multiplicative like 56 * 55

3des is EDE  encrypt with k1, decrypt with k2 and encrypt with k3.  or 3*56 or 168 bits.  Quit often, cypherblock chaining is used with the sicond or third pass.  The cbc makes it even or difficult to guess the encryption keys.Decryption = DED


Cryptography math requirements I know that most of the math related to cryptography is number theory/abstract algebra/probability, but I was wondering if there are some algorithms that make use of other fields of math like real/complex analysis, differential equations or linear algebra?
Also, what is highest level of mathematics required for cryptography?

It would be hard to find a category of mathematics not related in some way to cryptography, here is a list of applied mathematics by subject area. Even very abstract mathematics could be future cryptographic tools waiting to happen:

"A large part of mathematics which becomes useful developed with absolutely no desire to be useful, and in a situation where nobody could possibly know in what area it would become useful; and there were no general indications that it ever would be so. "


Are there any bijective one-way functions not based on number-theoretic hardness assumptions? I'm trying to find a bijective function $y=F(x)$ which should be easy to compute in one direction but hard to compute in the other, where the one-way property is not based on a number theoretic assumption.

The hard direction should be preferably as hard as computing hash preimages, but it could also be that there is only some practical asymmetry (such as taking 1000 times as long to compute one direction than the other).

Poligh-Helmman encryption, LUC encryption and RSA encryption can provide some form of one-wayness since decryption/encryption take very different times, but they are all number theoretic based and require changing the plaintext and ciphertext space to avoid weak plaintexts.

It is not entirely clear what you want, but suppose you need a trapdoor permutation - the function that is easy to invert only if you know a secret parameter - and which is not based on number-theoretic assumptions.

There are two well known families of such schemes: Multivariate Cryptography (MQ) and Code-based cryptosystems (for instance, McEliece cryptosystem).

An MQ scheme typically consists of a low-degree invertible polynomial transformation $S$ (public or secret) and two secret affine transformations $A_1,A_2$. The public key is exposed a polynomial(s) $A_2(S(A_1(x)))$. There are many insecure candidates for the nonlinear layer (see survey in this paper), but it is generally assumed that the HFE cryptosystem with sufficiently large parameters is secure.

The code-based cryptosystems hide the generator of some linear code in a similar manner by multiplying it by properly chosen matrices and expose the public key as a matrix.

Both families produce terribly large public keys up to several megabytes, and are of limited use because of that and the lack of systems that withstood a lot of cryptanalysis (except for the original McEliece proposal).

UPDATE:
You may also want to look at some bijective polynomials suggested in the recent algebraic papers. I do not know if there exist efficient inversion algorithms.

For example:
$\left(X^{2^k}+X+a\right)^{-l}+X$ over $\mathbb{F}_{2^n}$, where $n/\text{GCD}(n,k)$ is odd, $l(2^k+1)\equiv 2^{n/2-1}\pmod{2^n-1}$, Tr$(\delta)=1$ in this 2010 paper

For odd $p$: $\left(X^{p^k}-X+a\right)^{\frac{p^n+1}{2}}+X^{p^k}+X$ over $\mathbb{F}_{p^n}$ in this 2012 paper.

I found that the best way to implement F is by using a T-function.


Relation between key size and PRNG state size Some (supposedly) cryptographically secure PRNGs have an internal state of only 160 bits or less. When the algorithm is otherwise properly designed, that seems like enough to generate a 128 bit key for e.g. AES.

Can the PRNG also be used for the generation of longer keys, e.g. RSA keys with 1024 bits?

My intuition is that it would take (on average) a brute force attack of 2^159 key generations to find the same key, which is probably harder than factoring the 1024 bit key (according to various key length comparisons).

Is there an easier way to crack an RSA key generated using such a PRNG? The OpenSSL PRNG documentation states that an internal state of at least 4096 bits is required to securely generate an RSA-4096 key; that would contradict my intuition.

Your intuition is correct.

While more bits of entropy is better when generating a key, attacking RSA through the key generation process is an independent attack of factoring the modulus, and is predicated on a different computational hardness assumption, search of the keyspace compared to the hidden subgroup problem for finite Abelian groups (for factoring or discrete logarithm.) Factoring at least seems subexponential but superpolynomial, so is significantly easier than search; Many search problems appear to be NP hard, with exponential time complexity in the average case.

The attack on the key generation process depends on the cryptographic strength of the PRNG, and is analogous to attacking a symmetric ciphers in many ways. Since the attacks against PRNG's are so similar to attacks against symmetric ciphers, you can use the guides at keylength for symmetric ciphers as guides to the minimum state for key generation as its entirely appropriate. If you're using RSA for key exchange, and your symmetric key length is smaller than the key length of your PRNG seed, they won't bother attacking the key generation process.

The question does highlight a very important concern about prudent cryptography however, and that is that key generation is highly vulnerable to attack by poor implementation. A cryptographically secure PRNG is essential if using a PRNG for key generation.

To generate an RSA key, you need lots of random bits – more than 4000 for a 4096-bit key (usually more than the key size, since you need to throw away and retest parts if the prime tests fail).

Now, to generate an RSA key, you would love to have the bits being uncorrelated. But if your PRNG has 160 bits of state, you cannot get even 200 uncorrelated entirely random bits out of it. Most of the time, you can get a bit more than the state size safely, but they will obviously not be entirely random, only oh point something random, and not necessarily uncorrelated. The quality of the output of a PRNG is debatable; for example, arc4random(3) is a “stretching RNG” which means that it distributes the entropy in its about 1696 bit of state mostly uniformly across the output (notwithstanding RC4 early keystream bias: the first 3072-plus-some aRC4 output bytes are thrown away), whereas others “exhaust” their full entropy in the first pool-sized read and then are merely pseudo-random (i.e. zero mathematical entropy afterwards); AFAICT the Linux/BSD /dev/urandom device belongs into this category except that reads cause stirs which increase entropy – more, the more consumers are using the RNG at the same time).

So, this is really a “depends” question. It depends on the security level you want (160 bits of state for an 4096-bit RSA key is really a bit few, but might work for an 1024-bit RSA key, but definitely not for an 1024-bit DSA key) and, to some extent, the properties of the RNG chosen. The general answer is: no, you cannot use a n-bit state RNG to generate an RSA key with n or more bits of size.

「Is there an easier way to crack an RSA key generated using such a PRNG?」 – Yes, but the details may or may not be worth it. For an extreme, see the Debian OpenSSL RAND_add fiasco, in which the entire key space was, IIRC, 32768 * 2 possible keys, for each key bit size, making it utterly easy to precompute them all (for a few given key bit sizes).


How do I convert the definition of E-521 into a curve definition a la Bouncy Castle? I am currently trying to create an ECCCurve for E-521. Unfortunately, it is not currently a named curve in the library I am using, so I will have to define it manually.

I am using the definition of the E-521 curve provided here:

E521 is a curve over GF(2^521-1), formula x^2+y^2=1-376014x^2y^2,
basepoint
(1571054894184995387535939749894317568645297350402905821437625
18115230499438118852963259119606760410077267392791511426719338990
5003276673749012051148356041324, 12), order 2^519 -
3375547632585017057891076304187826360719049612140512266186351500
85779108655765, cofactor 4.

The two curve definitions I can choose from are FpCurve and F2mCurve. I'm not sure which one to choose for this. I have looked here. Unfortunately, I don't know how to extrapolate which one to use based just on the knowledge that E-521 is an Edwards curve.

Is an Edwards curve not compatible with the base classes that are defined in the library? Do I need to wait for further development there, or can I risk attempting to implement it myself? The latter is obviously a question I will likely have to answer myself, but some extra information on the risks/other implementations I could examine would be helpful.

Bouncy Castle does not support curves of the Edwards form (such as the one E-521 has). See related question: Elliptic Curves of different forms
Bouncy Castle's FpCurve supports curves of the Weierstrass simple form. You can convert Edwards curves to this form by a series of (complex) calculations. SafeCurves shows you the necessary equations. First convert the Edwards curve to Montgomery form, then to Weierstrass form.
Unfortunately doing this will result in absolutely huge numbers, which - on top of the fact that Edwards curves are computed faster than Weierstrass curves - results in poor performance.

Appendix: Curve forms

Weierstrass: $y^2 = x^3 + ax + b$
Montgomery: $By^2 = x^3 + Ax^2 + x$
Edwards: $x^2 + y^2 = 1 + dx^2y^2$

Edwards Curves can be converted to Montgomery or Weierstrass curves.

The only tricky part is that the point (0, 1) goes to the point at infinity. Here is some haskell that will do it. (Requires arithmoi package for extended gcd)

{-# LANGUAGE NoImplicitPrelude #-}
module E521 (p521, IntModp521, toIntModp521, fromIntModp521,
             d, a_montgomery, b_montgomery, a_weierstrass, b_weierstrass,
             bp, bp_montgomery, bp_weierstrass)
  where

import Data.Ratio (numerator, denominator)
import Math.NumberTheory.GCD (extendedGCD)
import Prelude ( Eq(..), Fractional(..), Num(..), Ord(..), Show(..),
                 Integer,
                 (^), ($), mod, otherwise)

p521 :: Integer
p521 = 2^521 - 1

newtype IntModp521 = IntModp521 Integer deriving (Show, Eq)
toIntModp521 :: Integer -> IntModp521
toIntModp521 x | x < 0     = IntModp521 $ (x `mod` p521) + p521
                   | otherwise = IntModp521 $ (x `mod` p521)
fromIntModp521 (IntModp521 x) = x

instance Num IntModp521 where
  (IntModp521 x) + (IntModp521 y) = IntModp521 $ (x + y) `mod` p521
      (IntModp521 x) * (IntModp521 y) = IntModp521 $ (x * y) `mod` p521
  abs (IntModp521 x) = IntModp521 $ x
  negate (IntModp521 x) = toIntModp521 (-x)
  fromInteger = toIntModp521
  signum (IntModp521 0) = 0
  signum _              = 1

instance Fractional IntModp521 where
  recip (IntModp521 x) = IntModp521 $ middle $ extendedGCD x p521
    where
      middle (a, b, c) = b
  fromRational a = (toIntModp521 (numerator a)) / (toIntModp521 (denominator a))

d :: IntModp521
d = -376014

bp :: (IntModp521, IntModp521)
bp = (x, y)
  where
    x = 1571054894184995387535939749894317568645297350402905821437625181152304994381188529632591196067604100772673927915114267193389905003276673749012051148356041324
    y = 12

a_montgomery :: IntModp521
a_montgomery = 2 * (1 + d) / (1 - d)

b_montgomery :: IntModp521
b_montgomery = 4 / (1 - d)

a_weierstrass :: IntModp521
a_weierstrass = (3 - a_montgomery ^ 2) / (3 * b_montgomery ^ 2)

b_weierstrass :: IntModp521
b_weierstrass = (2 * a_montgomery ^ 3 - 9 * a_montgomery) / (27 * b_montgomery ^ 3)

bp_montgomery = (u, v)
  where
    u = (1 + y) / (1 - y)
    v = u / x
    (x, y) = bp

bp_weierstrass = (u, v)
  where
    u = (x + a_montgomery / 3) / b_montgomery
    v = y / b_montgomery
    (x, y) = bp_montgomery


Can data over a very low bandwidth channel still be encrypted? If you have a very low bandwidth channel, can encryption still be used?

Another way of putting this might be, does encrypting well increase the size of the data significantly?

Are there good encryption techniques that keep the block size the same?

If the sender and recipient can agree on the nonce of every message from existing context, so that the nonce either doesn't need to be transmitted or can be derived from metadata that must be transmitted anyway, then a stream cipher can be used to encrypt with no length expansion.

But the problem here is that you likely don't want just plain encryption, but authenticated encryption (AE), and AE algorithms generally require an authentication tag to be transmitted along with messages, which is an overhead that expands message size.

There do exist however AE algorithms that under limited circumstances could be used to encrypt and authenticate with no length expansion.  One example is the still experimental CAESAR competition candidate AEZ, which claims the following property (from the v5 spec, p. 10):

  Exploitation of domain-specific redundancy. In many contexts, plaintexts have a certain expected structure. This might arise because the message was produced by or for a particular protocol. We intend that if the user checks for the anticipated structure and regards messages as inauthentic if they don’t comply, then this check augments authenticity and correspondingly lessens the need for the nominal redundancy that is inserted by AEZ before enciphering (that is, the extra ABYTES zero bytes).

The following guideline is given for when a very low ABYTES (authentication tag length) value may be safely used (p. 13):

  Applications should not reduce ABYTES to zero or some other small value without ensuring that, combining the ABYTES zero bytes with
  any decryption-verified redundancy, there remain enough total bits $r$ of redundancy that forging each message with probability $2^{−r}$ is alright.

AEZ however is still very much at an experimental, cryptographic competition phase, so if you need a solution today you're just going to have to use a well-established AE scheme, and that will require length expansion.

There is the one time pad (OTP) of course.  A low bandwidth point to point channel is a perfect use case for it. Perfect secrecy and the cipher text is exactly the length of the plain text.  100% efficiency in that it’s bit for bit encryption.

There are some implementation issues (sometimes) with a OTP, but in certain limited point to point communication systems, it’s perfect.  And are these issues for your system anyway? Malleability /authentication isn't always a real problem as long as you keep the key material safe.   However a MAC/HMAC scheme can be appended creating the same degree of integrity/authenticity as any other encryption technique, but with higher secrecy.

If you imagine 1GB of key material exchanged personally (or by trusted courier), that would facilitate ~6 million Twitter messages. In your low bandwidth channel (say 1 bit /s), that’s 31 continuous years worth of nasty secrets. This fact plays into the particular requirements for the initial key exchange; you’ll never have to do it again so can be accomplished at the start of your grand scheme.

There aren’t that many low bandwidth scenarios these days (unless you’re talking to a submerged submarine in another hemisphere), so this is an extreme solution to your extreme problem.


Why is elliptic curve cryptography not widely used, compared to RSA? I recently ran across elliptic curve crypto-systems:

An Introduction to the Theory of Elliptic Curves (Brown University)
Elliptic Curve Cryptography (Wikipedia)
Performance analysis of identity management in the Session Initiation Protocol (SIP) (IEEE)
Overview of Elliptic Curve Cryptosystems. (RSA.com)

It seemed to me to be great alternative to RSA as the de-facto cryptosystems to be used in banking and financial systems and in the public key infrastructure for certificates, but is not used! If someone can explain why this is not done, it would be very helpful. A comparison between traditional RSA and an elliptic curve cryptology would be helpful.

To begin with:

Advantage of RSA:

Well established.

Advantages of elliptic curve:

Shorter keys are as strong as long key for RSA (see the IEEE paper)
Low on CPU consumption.
Low on memory usage.

RSA was there first. That's actually enough for explaining its preeminence. RSA was first published in 1978 and the PKCS#1 standard (which explains exactly how RSA should be used, with unambiguous specification of which byte goes where) has been publicly and freely available since 1993. The idea of using elliptic curves for cryptography came to be in 1985, and relevant standards have existed since the late 1990s. Also, both RSA and elliptic curves have been covered by patents, but the RSA patents have expired in 2000, while some elliptic curve patents are still alive.

One perceived, historical advantage of RSA is that RSA is two algorithms, one for encryption and one for signatures, that could both use the same key and the same core implementation. But this is not a real advantage because it is usually a bad idea to use the same key for both encryption and signatures. Also, you can mathematically use the same private key for ECDH (key exchange) and for ECDSA (signatures), so that's really not an "advantage" of RSA over EC at all.

Another advantage of RSA is that its mathematics are somewhat simpler than those involved for elliptic curves, so many engineers feel that they "understand" RSA more than elliptic curves; again, a fallacious argument, since implementation of cryptographic algorithms is fraught with subtle details and best left to professionals -- and there is no need to understand the internal mathematics of a library to simply use it (we could make this argument semi-valid by pointing out that RSA relies on the hardness of factorization, which has been studied for 2500 years, whereas discrete logarithm on elliptic curves can only sport about 25 years of research).

The only scientifically established advantaged of RSA over elliptic curves cryptography is that public key operations (e.g. signature verification, as opposed to signature generation) are faster with RSA. But public-key operations are rarely a bottleneck, and we are talking about 8000 ECDSA verifications per second, vs 20000 RSA verifications per second.

An additional interoperability issue is that elliptic-curve operations can be made over curves of distinct types, and can be widely optimized if you stick to a specific curve known when the code was written. There is no security issue in using the same curve for many distinct people with distinct key pairs. But it means that most implementations will only support two or three specific curves. NIST has defined 15 standard curves. However, in practice, many implementations only support two of them, P-256 and P-384, because that's what is recommended by NSA (under the name "suite B")(a notorious example is NSS, the cryptography library used by the Firefox Web browser for SSL).

There are two ANSI standards for elliptic curves, X9.62 for signatures (partially redundant with FIPS 186-3, but much more detailed), and X9.63 for asymmetric encryption.

So there is a lot of political push for the adoption of elliptic curves in cryptography, by both academic researchers and institutional organizations. But inertia of the firmly entrenched RSA will take time to defeat. Also, the perceived mathematical complexity, and the potential legal risks related to patents, still hinder wide acceptance of elliptic curves.

(To your list, you can add "key generation time": generating a new key pair for ECDH or ECDSA is widely faster than generating a new RSA key pair.)

You forgot to mention one additional advantage of elliptic curves: the
generation of keys is much faster than with RSA.

In europe, many government smart card solutions are now based on ECC:

The european electronic pass ports
The Austrian card
The German ID card
The new German health insurance card


Alternative sources of random numbers Considering that algorithmic methods for generating unpredictable streams are hard to come by, I've wondered if any of these potential sources are good for making keys, seeds, and the like:

stocks, bonds, and other economic indicators.
weather patterns, temperatures, humidity, stream video of the sky, and other environmental variables.
photos taken by anyone at all.
noise in a room.
traffic patterns.
seismic activity.

Are any of these methods used?

Potentially almost any data input can be used as seed. But in general you don't want to use information that can be trusted to have high entropy and be secret all the time. This rules out stock exchange and the weather for instance, as the stock exchange may be down, and there is not much entropy in a clear blue skye.

Almost all of the sources you mention rely on outside phenomenons, which means you have to trust the source. Moreover, you'll need a trusted path to your source, and the trusted path likely requires a random number generator. So you would get into a chicken/egg situation.

What is usually done is to rely on a local phenomenon and then use highly unpredictive measurements. Local phenomenons can be kept secret and measuring in the extreme will mean that you aren't dependent on large fluctuations. For instance a HDD can be used to inform the system about I/O times, and measuring in nano-seconds will give enough entropy for a few bits of seed.

Of course, you neverk know what kind of system you are going to find. So fortunately it starts to be commonplace to include a random number generator in CPU's. An RNG in the CPU or - for instance - in a TPM is probably the best RNG you can find.

I personally found there is the only true randomness generated by computers. It' simply data corruption.

Everyone hates data corruption because it means nothing to them, and true randomness means nothing as well. I experienced corrupted photo files whose broken pixels obscured the original image randomly.

I recommend making data corruption by executing several threads without lock. It will be absolutely unpredictable and there is no definite pattern. I personally did it in python

To make my idea clear, here is a thread about how threads without lock can easily make data corruption

https://msdn.microsoft.com/en-us/magazine/cc163744.aspx

In this post, it is clear that many threads share the same resource, and computers can easily make mistakes. This is why developers use locks.

and I highly recommend trying to predict the outcome of this script. It is dependent on OS, so just suppose the default is Windows (because it is so widely used)

https://github.com/Hojung-Jeong/Silver-Bullet-Random-Number-Generator/blob/master/propellant.py


Usage of different size chunks during AES encryption/decryption I want to encrypt user's files on our server. For this purpose I decided to use the PHP Mcrypt library. I chose to use the Rijandel-128 algorithm and CBC mode for encryption. Since files are quite large, I decided to encrypt/decrypt files by chunks.

Everything works well when I use one chunk size for encryption and decryption processes. But when I encrypt a file with 8 KB chunk size and try to decrypt it with 4 KB chunk size, file is corrupted.

My question is – is it possible to encrypt and decrypt a file with different chunk sizes? If yes, what are the pitfalls of this process? Right now, I don't understand if there are any bugs in my code or there are some encryption restrictions I'm not aware of.

To see the problem, let's see how I would chain up a single function (call it $AES\,CBC_k(iv, m)$) which only encrypts a single block at a time into something that can encrypt "chunks" of any size.

Let $m=m_1||m_2||m_3||m_4$ be the message I want to encrypt. Each $m_i$ is a single block (in AES it is 128 bits). I want to use $AES\,CBC_k$ to encrypt $m$. The proper way to do this would be to compute:

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(c_2, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Then let $c=c_1||c_2||c_3||c_4$ be the ciphertext. Using this process (note how the iv changes from block to block), we could build another function, say $E_k$ which encrypts messages of any length (actually a multiple of the block size).

To illustrate your problem, let's split $m$ into two chunks: $m_1||m_2$ and $m_3||m_4$ and see what it sounds like you are doing. It sounds like you are calling $E_k(iv, m_1||m_2)$ then $E_k(iv, m_3||m_4)$. This is like doing the following.

$$c_1=AES\,CBC_k(iv, m_1)$$
$$c_2=AES\,CBC_k(c_1, m_2)$$
$$c_3=AES\,CBC_k(iv, m_3)$$
$$c_4=AES\,CBC_k(c_3, m_4)$$

Notice the iv for $c_3$ and compare it with the iv for $c_3$ in the correct operation above.

So, if you really want to encrypt the way you are talking about doing, you would need to use the last block of the previous chunk as the iv for the next chunk. Managing this yourself in code, while do able, is somewhat of a pain. I'm willing to bet there is an encryption library for PHP that can so this for you (on file streams or something so the whole file doesn't have to be in memory).

The real question
So it sounds like your real question is how to encrypt large files in php without having to read the whole thing in to memory. I don't use PHP much, so I can't really comment. I will say don't use the solution here as it was obviously not designed by anyone who knows anything about cryptography. I know in other languages (Java, c#) you can pass in a file stream to be encrypted in most libraries, which probably solves the problem of having to read in all the memory. Not sure if PHP has something like that though.

Update
It looks like php has encryption filters that you could use with stream_filter_append to encrypt streams so that the file doesn't have to be loaded into memory. Then you would have a stream to read from and a stream to write to. Simply read from the input stream and write to the output stream. The encryption happens automatically thanks to the filter.

sure, its not going to be decrypted as you use CBC mode. Once you change the chunk size, therefore you change the IV, as result, you cannot decrypt.


How to securely map messages to points on an elliptic curve I'm implementing a demonstration hybrid cryptosystem in Python (FinCrypt, I know the name is bad) and I'm migrating over from my Weierstrass curve implementation, which was based off of this, to one based on Edward's curves from here.

However, I'm at a loss when it comes to mapping a message onto an element of the elliptic curve, and I noticed that the implementation I'm currently using doesn't require the message to be mapped, at least to my knowledge.

I was wondering three things:

Do I have to map a message, or is it possible to do something like I've already got going with Edward's curves
Is my current implementation of the ElGamal part insecure because it doesn't map messages and instead takes an integer?
If I do have to implement a mapping for security, how would you reccomend I map message values to points, and how should I figure out the maximum message size based on my curve?

If I do have to implement a mapping for security, how would you
  reccomend I map message values to points, and how should I figure out
  the maximum message size based on my curve?

The default strategy for encoding an integer message as curve point is to define a value $k$ smaller than $\log_2 p$ (with $p$ being the field prime), such that for every valid message length $m$, $m+k< \log_2 p$ holds. You would then encode the message as the $m$ high bits of the x coordinate and start counting up on the $k$ low bits until you reach an $x$ that has an $y$ on the curve (which you find using the curve equation). This usually has probability $2^{-k}$ of failing to encode a message. For decoding you simply throw away the $k$ low bits and take the rest as your message.

  Is my current implementation of the ElGamal part insecure because it
  doesn't map messages and instead takes an integer?

Yes, the scheme as given is insecure because you can easily distinguish an encryption of $1$ from an encryption of $2^{1024}$ because the former will be about as long as the curve's prime and the latter will be more than 1024-bit long, which formally breaks the IND-CPA security of the scheme.

Note that in order to use proper ElGamal you need to encode your message as a curve point $M$ and then compute $c_1=[k]\beta+M, c_2=[k]G$ all as operations on the curve. Also note that I'm fairly confident that simply replacing the unbounded integer addition with integer addition $\bmod p$ will not yield security either because curve point coordinates are not uniformly chosen integers (for starters because some $x$ values simply do not occur).

  Do I have to map a message, or is it possible to do something like
  I've already got going with Edward's curves

I see no reason to make any changes to your code, because currently it doesn't actually use ElGamal (see above). If you were to use proper ElGamal, the same strategy that worked for Weierstrass should also work for Edwards (see the first part).

using a kobltiz method we convert a message into an elliptic curve point


Applicability of IBM's projected 50-qubit quantum computer Q to cryptanalysis? IBM announced Q, a project for a 50-qubit universal quantum computer, according to the press realease. Here is more PR spin, and the research sub-page.

What would be the applicability of that to cryptanalysis?

What would be the applicability of that to cryptanalysis?

It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons:

50 Qbits is just not enough to attack any cryptographical problem; to apply either Shor's or Grover's algorithm against any realistic problem, you'll end up needing thousands.
It doesn't appear that they're addressing the decoherence issue.  That is, in a quantum computer, you'll end up getting random perturbations to the running state.  Cryptographical computations take quite a long time (far longer than we can go without expecting such a random event to occur), and are quite sensitive to such perturbations.  What they'll need to do is run error correction logic (which has multiple physical qbits stand for the one logical one, and has logic to detect such a perturbation on one of the physical qbits, and correct it).

Now, I'm not saying that what IBM is trying to build is useless; for one, it would appear that the computations that Chemical modeling requires fits nicely into what they have.

And, while this isn't immediately useful for cryptography, it is another step towards a Real Quantum Computer (where "Real" means "can actually solve an interesting cryptographical problem).

I am not 100% sure if there is a direct use specific to cryptoanalysis. However, if this machine is applied to another discipline, such as machine learning and data science in general, it could have an effect on crypto work. For example, in data science, neural networks can be an effective tool for solving many problems. The issue is that they are painfully slow and is one of those rare cases where throwing more hardware at the problem can be a solution.

So while there may not be a direct link to crypto as we stand right now, who knows what the future may bring.


Why is OTP not vulnerable to brute-force attacks? I saw this question on the book Understanding Cryptography.

  At first glance it seems as though an exhaustive key search is possible against an OTP system. Given is a short message, let’s say 5 ASCII characters represented by 40 bit, which was encrypted using a 40-bit OTP. Explain exactly why an exhaustive key search will not succeed even though sufficient computational resources are available.

It puzzles me because I think that as far as I know that the key has only $40$ bits, I could try all the possible $2^{40}$ keys and XOR them with the ciphertext to recover the message... Is there something that I am missing? How can it not work if we are assuming the attacker has computational power to do the exhaustive search?

Brute force on OTP will give you all sorts of messages which are meaningful and not meaningful.

For example, you have a 4-character encrypted text: weaw. Now brute-forcing will give you all sorts of meaningful and not meaningful messages like:

erwe
hell
road
....

Now, which one was the real message? That would be difficult, rather impossible to guess.

I originally wrote this thinking that it was an answer, but then I realised that it's not strictly related to OTP in itself but rather the ways in which OTP is commonly used in computer security (I have more experience in computer security than in pure cryptography). I'll post it anyway though as it's an interesting consideration when analysing everyday OTP systems e.g. for user authentication (2FA etc.).

OTP keys are often valid for only a limited period of time or number of attempts. After that, the system re-generates the OTP or moves onto the next key in a pre-shared list of keys, leaving the attacker with a finite length of time or number attempts to complete the attack, so the key will almost always change before the attack can be completed.

Nevertheless, in the case of an OTP-encrypted message (e.g. between two spies working together) that has been intercepted, the attacker has an infinite length of time and number of attempts to decrypt it; in situations like this the benefit of OTP is that recovery of one key does not compromise all prior or subsequent messages.


Questions about BCrypt and PBKDF2 I would ask you some questions about users' password storage in a login system.

What algorithm do you suggest me to use? bcrypt or PBKDF2?

I was looking for a way to implement them client-side and i thought this way:

The client computes 10.000 iteractions of user's password with PBKDF2 and username (or email) as SALT and the server will store in the DB the salted SHA-512 digest of the PBKDF2 result.

Is it a good way?
Is client-side key stretching good in general? Does it have some disadvantages compared to the server-side implementation?
Is there a better way to implement PBKDF2 client-side?
And what about bcrypt?
If I use bcrypt server-side, what's the best way to add a pepper?
Adding pepper has some disadvantage?

What's your motivation for slow-hashing on the client-side?

It may well be slower than if performed server side (if you're referring to a browser-based application, and the hashing is done with javascript, then it will certainly be slower, even more so if it's a mobile device)
it doesn't provide any extra security, the credential(s) (password, hash of the password, salt derived from password which will be used for hashing the password, whatever...) will still need to be transmitted to the server - there's no way to avoid that

Keep it simple - you're much less likely to introduce some sort of vulnerability into your system.  The following protocol is pretty standard:

send the client's username/password to the server over TLS/SSL (it's worth the effort, really)
slow-hash the client's password with either Scrypt (preferable), or PBKDF2-SHA256 (at least 100'000 iterations) and a user-specific salt (stored in the DB with the hash)
for each login attempt, compare the output of the above with the hash you have stored in the DB

Note: Bcrypt is fine, some people fetishize it, others prefer PBKDF2 because it's more 'standard' (and it's output length is configurable).  Scrypt is the state-of-the-art, although it's less widely used, and can be more complicated to implement.

EDIT

After further consideration, and better understanding exactly what you're asking (I think), I'm going to say yes: what you're proposing is fine, provided certain conditions are met.  The issue that @StephenTouset pointed out is valid, and has to be avoided.  However, if I understand your question correctly, then you're already mitigating that weakness.  Consider the following:

Client slow-hashes password with PBKDF2 or Scrypt (use of email address or username as salt is questionable - email addresses change and usernames could be used in dictionary attacks).  This initial slow-hashing mitigates dictionary attacks, and offloads the heavy work from the server to the client
Client submits the output of the slow-hash (256 bits) to the server (over TLS/SSL), where it is then hashed once with SHA-256 (no salt necessary) and compared with the hash stored in the database.

Should the database be compromised, an attacker would still need to brute-force the hash of a 256-bit value (the client-side slow-hash output) to verify a correct guess at the password, pretty much rendering the hashes stored in the database useless to an attacker.

I think the theory is fine.  In practise, I think it's a bit messy and maybe unwarranted (your comment mentioned up to 1000 login attempts per second, are you really anticipating up to 86 million logins per day??).  Only you can decide whether you can justify it.

Bcrypt is slow, since it uses Blowfish (and insecure, due to the fact that it has 64-bit block, though it could be extended to 128-bit block [which I will call Blow128]) I would recommend PBKDF2. Taking the SHA-512 hash of the PBKDF2 result is bad, because chaining two hash functions (even though PBKDF2 is not a hash function) For the other questions, I would consider editing the question so I could answer it fully.

Edit:

I recommend Bcrypt, even though PBKDF2 is another choice. Still SHA-512 of PBKDF2 would be bad, because $H_{1}(H_{2}(X))$ is bad (despite the fact that PBKDF2 is not a hash function). Besides, what I thought is slow hashing was nothing. The main goal of hash functions are they be fast but secure. So basically I was against the hash functions. By slow hashing you might mean moderate slow hashing, because you don't want a digital signature algorithm to take a week, to process a 1 MB PDF.


Why develop Edward curve formulas that deviate from unification? Edward curves were considered initially because they provide a unified formula for both doubling and addition, thus having inherent side-channel resistance. But a lot of work has been done recently involving construction of a different class of addition and doubling formula (e.g. differential addition formula, w-coordinate formula), particularly concerning efficiency of these formulas in terms of the number of field multiplications/squarings. Thus, the point of unification becomes invalid.

Please can anybody explain/cite some relevant papers which address this issue?

Edwards curves can be implemented using a unified formula for addition and doubling; i.e., one can implement addition such that
$$\mathrm{dbl}(P)=\mathrm{add}(P,P).$$
Performance wise it is however more efficient to consider both functions separately, since the doubling can be implemented more efficiently than the addition.

Depending on the representation and the formulas, the unification property will be preserved or not. For instance, in "Twisted Edwards curves" by Berstein et al., there is a formula for $\mathrm{add}(P,Q)$ and a faster one for $\mathrm{dbl}(P)$, but the above property still holds. In "Twisted Edwards curves revisited" by Hisil et al., there are also two separate formulas, but the above property doesn't hold anymore.

I think the unification property looks great in a paper as it makes the description cleaner; however one does not necessarily need it in practice. Some examples:

Example 1: "Scalar multiplication (based on Exponentation by squaring)". When the factor is lower than the order of the group, you know that the next doubling is always higher than the accumulated value, so that an addition will always take place between two different points.
Example 2: "Addition of random points". The order of the group is in general so large, that the probabilty that two randomly chosen points are equal is negligible.

So in many situations the absence of the unification property does not seem to be an issue. It will of course depend on what precisely you are doing with the curve.

Without knowing what recent work you refer to, I can state that one of the prime benefits of the Edwards curves is the unified adding / doubling, and their completeness -- i.e., no exceptional points. Hence no branching decisions to provide clues to side channel snooping. And also, fewer places to screw up the implementation.


Why does Openssh use only SHA1 for signing and verifying of digital signatures? I am learning SSH protocol. With my current understanding of SSH protocol, I think that message digest algorithms for using in digital signature should be derived from Key Exchange. But Openssh implementation uses only SHA1 for signing and verifying of digital signatures. SHA1 is hard coded in these two functions, ssh_dss_sign() and ssh_dss_verify().

I am wondering, does all the implementations of use SHA1 as hash algorithm for signing and verifying digital signatures.  And why don't we use SHA-256 as it's better than SHA1?

Is there any specific reason for doing so..? If yes, could someone please provide some references.

Thanks in advance.

Because the RFC says so.

  Signing and verifying using this key format is done according to the
    Digital Signature Standard [FIPS-186-2] using the SHA-1 hash
    [FIPS-180-2].

It says the same for RSA half a page down.

Apparently the signature algorithm is a defined part of the public key method's specification, rather than being negotiated separately like the MAC algorithm is.

At a guess, SHA-1 was considered good enough at the time SSH 2 was being written almost a decade ago (the RFCs were published in 2006), and no one wants to bother changing it now.

Notice that ECDSA keys, published in RFC 5656 in 2009, use SHA-2:

  Signing and verifying is done using the Elliptic Curve Digital
     Signature Algorithm (ECDSA).  ECDSA is specified in [SEC1].  The
     message hashing algorithm MUST be from the SHA2 family of hash
     functions [FIPS-180-3] and is chosen according to the curve size as
     specified in Section 6.2.1.

You can see it in action in ssh_ecdsa_sign() in ssh-ecdsa.c and key_ec_nid_to_hash_alg() in key.c.

(I'm not an expert on SSH, so please take this answer with a grain of salt.)

Even though the ciphers have -sha1, these are actually HMAC which are keyed hashing.  HMAC-SHA1 is fine and accepted even in FIPS, even though SHA-1 is no longer accepted in FIPS.


Asymmetric algorithm for one time signing of small cleartext I want to generate a key pair such that the private key can be used once to sign a small message (1024 bytes) at some indeterminate point in the future and the public key can be used to verify that signature, what can I do to get better security than a regular asymmetric algorithm (e.g. RSA)?

The use case is allowing a user to "revoke" data by bundling the public key with the data. The user can then publish a revocation message (which can also contain some arbitrary but short message) with the private key.

And, do these requirements make any of the post-quantum algorithms especially suitable?

One algorithm that is especially suited to one-use key pars is lamport signatures. Like many (all?) other signature functions, lamport signatures first hash the message to get it down to a size that is more reasonable to sign.

For this use case, if you are willing to have $n^{2}$-bit signatures and $2n^{2}$-bit keys (public and private), you can sign a $n$-bit (or less) message with only a one-way function, by skipping the hash message step and just signing the message directly.

This is nice, because the security of all hash functions and many other algorithms relies on one-way functions. Using such a simple algorithm also removes most attack vectors (the remaining one is the one-way function, which is still an attack vector with most (all?) complex signature schemes).

There are various ways to reduce the sizes required.

What do you mean by better security? RSA was proved to be as difficult as prime factorisation and is thus one of the best understood public key cryptosystems. Also, since its widely used their implementations have withstood years of attacks. Since you are going for a one-time usage of the keys, speed is not of importance (or is it?). If you can handle the key size requirements of RSA, I don't see you can do better.

Edit: @Ricky-Demer has a very good approach of taking a hash function $f$ together with some private data $s$ and publish the value $p:=f(s)$ for everyone to see. If you ever need to send your revoke message, you can bundle this message $m$ together with $s$: $(m,s)$. Everyone will now be able to use $f$ to compare $f(s)$ to $p$ and check that the one sending the message was indeed the (only) one who was in posession of $s$.
Of course, after you have done this, everyone else in the world is able to forge revocation messages $(m',s$).


How is PBKDF2 so much better than normal Hashing or even using HMAC I do not know how the Key Length extension attack works. So if we leave that aside for once, and say just about usual brute-force attack on the hash, I don't really know how is PBKDF2 so much better than usual hashing.

Mathematically I know that PBKDF2 is so better against rainbow table attacks and also slow to recreate, but as computing power is moving up in the world, how it's still keeping its integrity?

For an HMAC we use a salt, also we can do the same for an usual hash.

So, SHA256('Hello'), is easily rainbow tabled. So if I prepend a salt, it's a little bit better, like SHA256(salt+msg), but Salts are usually kept in DB as clear text, so if some hacker is able to crack that salt, he can manually append the salt and perform the same operation.

Now in HMAC, -> H(key(opad) + h(salt + key(ipad))) is mathematically secure, but one can easily brute-force all possible password by running it through an HMAC operation (if he knows the salt), and he gets the key. A bit slower, but possible, and in pbkdf2, this whole process is looped maybe a million times even, with that much mathematical complexity, yet, if one gets the salt. He could simply run a big list of passwords with through another pbkdf2 function, and maybe very slow, but still possible, right?

So what's the use of this much complex algorithms by hashing and hashing with previous results of HMAC and so on, if it's still very much prone to a slower bruteforce?

The point is not to make the attack infeasible time-wise. Computational resources (usually, area*time, which is roughly a measure of the monetary cost) needed for the attack is the only thing you can hope to increase here.

As you observed, it is always possible to parallelize brute-force search of passwords, so the best you can do is increase the computational effort it takes to check a single password. Sure, even if checking one password required 10 seconds, the attacker could always put millions of ASICs in parallel and bruteforce everything in 10 seconds. To put it differently: the adversary can always get the password using little time, but this requires a lot of area (i.e., number of parallel computing units used simultaneously). Essentially, the adversary is forced to always invest a large quantity of area $\times$ time.

The point is that doing so will cost a lot of money to the adversary: it is usually considered that area $\times$ time is a decent (rough) approximation of monetary cost of the attack. So the hope is to make this attack less interesting money-wise.

A further note: the quantity area $\times$ time does in fact not perfectly measure monetary cost, as experiments with modern ASICs have shown. However, a lot of research has been devoted to find much better measures that map more closely to monetary cost (e.g. 1, 2). There are a bunch of satisfying candidates, and several constructions of hash functions which provably maximize this measure for the adversary. PBKDF2 does not seem to be the best one out there - but it is an old, well-established alternative which, experimentally, does not perform too bad with respect to the monetary cost it incurs to the adversary.

So what's the use of this much complex algorithms by hashing and hashing with previous results of HMAC and so on, if it's still very much prone to a slower bruteforce?

We often use KDFs to hardening the process to generate encryption keys (and authentication digests too) from somehow possible simple and guessable customer's / client's passwords. When we use random / noise bits possibly derived from some key agreement protocol or issued as an HTTPS API Key, HMAC suffices here. Note that both PBKDF2 and HMAC take a salt for private integrity verification as well.

So, this problem is regarded as how much noise we have from the input message to compute a hash image. A human readable password is easy to break with brute force due the use of simple/plain characters. KDFs let us tune execution parameters for this digest algorithm, making infeasible to find second preimages from known digests with fast dedicated hardwares such as FPGAs and ASICs by embedding a huge memory & some time consumption on the algorithm (or at least, KDFs try to race against ever more powerful hardwares produced).

Such security concerns are important if you or your clients have too much skin in the game to lose. Think in a core banking service or a healthcare startup, here you want to encrypt all data with KDFs on encryption keys to be a good mitigation in the case of data breaches. The attacker can always regard your API as an external/online Oracle and spoof IPs to bypass rate-limits, all the time costs here will be latency, bandwidth and endpoint processing during login brute force, so KDFs also help to reduce the vector attack here.


Is Threefish the only cipher with 1024 bits of security? Threefish has up to a massive 1024 bits of security.  Is it the only cipher with such overkill security?

If we are talking about symmetric encryption, the PAGES block cipher based on Speck support key size 1024 bits and PAGES+/PAGES— variants support key sizes up to 2048 bits. However, I have not seen any independent cryptanalysis of these, so I can't recommend them. If we talk about the ciphers which have some cryptanalysis available, the Kalyna block cipher supports up to 512-bit keys.

Nope. Besides old RC4, you can use RSA directly as your cipher at arbitrarily large bitness. We normally don't because its too slow.


semantic security of RSA variant I am thinking of a variant of RSA.
I know that RSA itself is not semantically secure as it is "deterministic". I have a "randomized" variant of RSA in mind.

Suppose that the public key is $<e,n>$. To encrypt a plaintext $p$, this variant first randomly choose a value $v$, and output the ciphertext as:
$$E(p)=<v,(v+p)^e \text{ mod }n>$$
The ciphertext consists of 2 parts, the value of $v$ in clear, and the ciphertext of $(v+p) \text{ mod }n$ computed using the original RSA.

Is this variant of RSA semantically secure? How do I prove it?

No it's not.

As a reminer: Semantic security is equivalent to IND-CPA. Semantic security is less commonly used, because most of the time proofs are less intuitive and more difficult.

In the IND-CPA game, the attacker chooses two messages $m_0,m_1$ and sends them to the challenger. The challenger chooses a bit $b$, and sends $Enc(m_b)$ to the attacker. The attacker wins if he can guess $b$ correctly. And we consider the encryption scheme secure, if the advantage of the attacker compared to random guessing is negligible.

So, let's play the CPA game with this variant:

The attacker chooses $m_0$ and $m_1$ arbitrary (but not equal)
He gets back $Enc(m_b)$. In your scheme that would be some value $v$ and $(v+m)^e \mod n$.
Since he knows both $m_0$ and $m_1$, he can check both possibilities by calculating both $(m_0 + v)^e$ and $(m_1 + v)^e$. Comparing that with the challenge, he immediately knows $b$
The attacker wins.

If you want to have an IND-CPA RSA variant, there is RSA-OAEP. In the random oracle model and with the RSA assumption, this is proven to be IND-CCA2, which is much stronger than IND-CPA.

If you intercept the message <v,c> and instead transmit <v+x, c> it will decrypt to p-x.
So this doesn't seem secure.

Edit: Just to clarify, I was a bit sloppy here.
What I was going for is the fact that malleability precludes IND-CCA2. But the question was actually about semantic security and there are in fact semantically secure malleable schemes. (See Wikipedia)

So while the statement "doesn't seem secure" is technically correct for the most widespread definition of "secure" for PKE schemes I did not answer the question at all. Sorry.


Memory hard key derivation (password hash) using AES encryption I am restricted on a certain environment involving PHP and am currently unable to implement new memory hard hashes such as scrypt (and I am not trying to compete with the likes of scrypt).

My current key derivation is simply an iteration of HMAC (password + salt). But it seems that using AES or other encryption ciphers, one could construct a fairly simple, memory-hard key derivation function using build-in PHP capabilities such as HMAC and AES encryption (assuming PHP is compiled with openssl support).

Pseudocode is:

salt = random (any length between 512bit and several MB)
M[0] = HMAC (sha512, password, salt)

for i=1 to N
    hash = HMAC (sha512, M[i-1], M[0] + i)
    M[i] = AES-128-CBC (iv = substr(hash,0,128), key = substr(hash,128,128), data = salt + hash) // substr lengths in bit

result = M[N]

for i=0 to N
    result = HMAC (SHA512, result XOR M[i], M[N-i])

Because of the second for loop, the entire matrix M needs to be present in memory, which would hopefully make it memory hard. Then one could configure salt size versus N to see what gives the desired results of memory usage and cpu usage within a reasonable amount of time.

I would appear to me that AES related-key attacks are not an issue in this scheme also because of the second for loop which hashes all matrix elements. The purpose of using AES is to obtain a larger randomized text for each array element than a 512 bit hash output would be. Since iv and key are unique and are related only through HMAC hashing, this use of AES would also appear to be secure. Even so, I appreciate your input. Creating one's own crypto is not encouraged, which I understand. Even if I do not end up using this, your feedback would really help me improve my understanding of these matters.

Also, I wonder whether the length of the salt affects the security of the function? I.e. if the salt were to be very long, say several MB, would that make it less safe than if the salt was short such as 512 bit (less reliance of encryption, more HMAC hashes)?

EDIT:

For theoretical purposes and NOT in order to create my own cryptography, based on the comments of otus, it appears that in principle, higher memory-hardness is achieved by a more intense shuffling of the matrix.

Therefore, one could e.g. generate a matrix of a size rounds * x, which is then hashed rounds times, but each hash made up of XOR-ring x*2 matrix values. The example below (PHP code) shows it for x=4 (^ is the PHP XOR operator):

for ($i = 1; $i <= $rounds; $i++) {

    $result = hash_hmac ('sha512',
                $result . ($matrix[$i] ^ $matrix[($rounds+$i)] ^ $matrix[($rounds*2+$i)] ^ $matrix[($rounds*3+$i)]),
                ($matrix[($rounds-$i)] ^ $matrix[($rounds*2-$i)] ^ $matrix[($rounds*3-$i)] ^ $matrix[($rounds*4-$i)]));

}

For 8 rounds, a matrix size 8*4 = 32 would be created, and then hashed with XOR combinations in the loop shown. The output below shows, which matrix index values (the $i in $matrix[$i]) would be combined in each HMAC round:

Computing 1 ^ 15 ^ 17 ^ 31 AND 7 ^ 9 ^ 23 ^ 25
Computing 2 ^ 14 ^ 18 ^ 30 AND 6 ^ 10 ^ 22 ^ 26
Computing 3 ^ 13 ^ 19 ^ 29 AND 5 ^ 11 ^ 21 ^ 27
Computing 4 ^ 12 ^ 20 ^ 28 AND 4 ^ 12 ^ 20 ^ 28
Computing 5 ^ 11 ^ 21 ^ 27 AND 3 ^ 13 ^ 19 ^ 29
Computing 6 ^ 10 ^ 22 ^ 26 AND 2 ^ 14 ^ 18 ^ 30
Computing 7 ^ 9 ^ 23 ^ 25 AND 1 ^ 15 ^ 17 ^ 31
Computing 8 ^ 8 ^ 24 ^ 24 AND 0 ^ 16 ^ 16 ^ 32

One concern there is the question of whether that many XOR operations would create a lot of of collisions and thus somehow security, even though each result is HMAC hashed. It would be interesting to get people's comments on that, with the reasons behind it.

Your key derivation function is not particularly memory hard.

The second loop walks the array in order, so an optimized implementation which an attacker would use can avoid the whole array, keeping only some elements in memory at a time.

For example, you can halve the memory use by only storing the second half of M initially. Then for the first N/2 iterations of the loop you only need to calculate the i'th element from the i-1'th. Then you would recalculate the first half of M instead and continue as earlier. You need about twice the computation for half the memory use, and can extend the tradeoff further. This is much worse (better for the attacker) than scrypt's tradeoffs.

If you use a salt length longer than 512 bits, the attacker can reduce the size of M[i] by only storing the hash value at that iteration during the first loop. They can then derive the whole value when needed in the result loop because it only depends on the hash and salt. This means a memory savings factor of salt length/512 bits for a computational overhead of less than 3x (since they need to recompute the AES twice in the second loop, but none of the hashing needs to be repeated).

There is probably a way to fix these, but the main issue is that you are rolling your own algorithm. Normally algorithms need to face years of cryptanalysis before they are trusted, at least unless they have a security proof reducing them to something already known/believed to be secure.

Instead, you should if at all possible use an existing algorithm, preferably an existing implementation because there are things that can go wrong implementing one yourself. If you want memory hardness, scrypt is the most accepted and widely available algorithm (tradeoffs exist, but they are expensive), though Argon2 which recently won a competition for password hashing algorithms might be an option soon (you will not find implementations for most languages yet).

It's normally the best advice to use something proven and well established, such as scrypt or PBKDF2.  You say you can't use scrypt, but you could use PBKDF2 and make it run long enough until you feel secure.  So you decide that every time you need the password, it must take n seconds on the current system.  You store the number of rounds along with the salt.  This becomes self-tuning, as the CPU gets faster you'll update to a larger number of rounds when the password is changed.  (And obviously you can also set a configurable minimum number of rounds, in case you want to jack it up despite how long it would (or, more likely, would not) otherwise take.)


Quick scan which data (hmac/fernet) can be decrypted with a key? I am designing a secure vault, which stores tens of thousands of encrypted messages and authenticated with Fernet/HMAC, A user query the vault with a key, could I use some kind of index to tell if the key can be used to decrypt any of the stored messages?

Or do I have to try decrypt them one by one?

Found a stupidly simple solution: Create an index of md5(key).

Alternatively, replace md5 with hash method of your choice.

That design is essentially the reverse of brutal-forcing a cipher key: you are brutal-forcing a key with messages, the time required grows linearly to the size of the vault.

You really should devise a more efficient seeking method.


Why does nobody use (or break) the Camellia Cipher? If Camellia is of equivalent security and speed to AES, concerns arise.

First of all, assuming the above, why is Camellia so rarely used in practice?
Why aren't there any breaks in Camellia? Does that mean that Camellia is currently more secure than AES, or is this a result of the lack of research on the cryptanalysis of the cipher?

There are a variety of reasons why AES is more widely used:

AES is a standard.
AES has been vetted by cryptanalysts more extensively than Camellia.  As a result, we can have greater confidence in the security of AES than in Camellia.  Therefore, on the merits, there may be good reasons to choose AES over Camellia.
AES is a government standard (FIPS).  Government procurements may be required to comply with applicable government standards.  Therefore, when selling to the government, AES may be required; if so, Camellia isn't an acceptable substitute.
AES is a industry standard.  No one will get fired for using AES. If (say) Apple uses AES, and AES gets broken, the newspaper headline won't be about Apple; it'll be about flaws in something everyone is using. On the other hand, if Apple uses Camellia and Camellia gets broken, the newspaper headline will be about why Apple took it upon themselves to deviate from industry standard practice and how that led to a security breach in their systems.  Therefore, aside from its merits, there's an incentive to choose the industry standard.
Camellia is patented.  AES is unpatented and free for all to use, without patent encumbrances.  Regardless of what licenses might be available, many people are a bit wary about any patented algorithm, due to uncertainty, IP risks, etc.  If the unencumbered version is every bit as good, it's easier to use the unencumbered version.  Also, it is possible that some open source crypto library developers may be less likely to implement Camellia, because of the potential patent situation or because of the reduced demand to the above factors, so standard crypto libraries are less likely to Camellia.  Similarly, many standards bodies have a bias against patent-encumbered algorithms, when there are alternatives that are every bit as good; therefore, some standards bodies may be less likely to use Camellia when they standardize on network protocols that require crypto.
AES is entrenched.  AES is a brand name that is widely known and recognized.  Also, AES is good enough.  Camellia is newer, and the benefits of Camellia are unclear or not as well known.  (In many contexts, Camellia has no obvious advantages, so a developer might not see any reason to adopt it instead of AES, if they already know and trust AES and consider AES adequate for their needs.)  There's no shortage of other block ciphers out there that could be considered, but if AES is good enough, there's not much incentive to use them.

Maybe Camellia might get more popular after its patents did expire for good. It is "japanese-make" and the fareastern browser and server environments are widely using it. This is because Japanese people still live in a mind policy like "only japanese things are reliable or can be trusted" (umm... which isn't the case actually seen from more neutral standpoint, regarding "people" or "makers" because they are finally humans as well with all imperfections given to the human race) OR if its authors expicitely (officially and permanently!) step back and keep distant from any further claims including possible future fees or renewals of their patents in this algorithm. (and yes put it under opensource or the gnu terms after patent expiration - means making the source officially public to allow further vetting and maybe improval by the public audience and expertise). And making it a defined standard finally as well. Why only having one blockcipher standard (AES)?  Ah, yes there is still another standard: ChaCha20 - which is made for streams.B


Any practical uses of machine learning for cryptography? I am about to go study for my masters in machine learning, data mining and high performance computing, but have recently become very interested in cryptography after taking Dan Boneh's Cryptography course on coursera.com.

I was wondering if there are any practical applications for machine learning in cryptography? A quick google search didn't seem to reveal much for me so i was wondering if someone here knows something.

My first impression would be that machine learning techniques could be used to learn the inverse function for some cipher and passphrase given enough plaintext/ciphertext pairs, but i am not sure how capable things like neural networks are at learning functions which are not linearly separable.

I would personally be very surprised if machine learning was of any use in a known plaintext attack.

We design our ciphers to look a lot like random functions; you give the black box an input, and an output spits out.  You give it a second input (possibly the same input in the case of nondetermanistic encryption), and a second output spits out.  What we try to achieve is that no one can determine whether the black box was our cipher (with an unknown key), or whether it's just spitting out random outputs.

Now, we assume that the attacker has the complete design of our input (apart from the 'key'); in a successful cipher, he still cannot determine it.  In fact, we design things so that the attacker can submit inputs of his own choosing; he still cannot determine whether he's giving inputs to the cipher or a random function.

Now, what machine learning would be trying to do is essentially this, except that you would be ignoring the design (because there's no way to give the design to the machine learning process), and you are limited to a known plaintext attack (because your machine learner has no way to generate the chosen inputs).  In addition, your machine learner would also not have the best asset a cryptanalyst has (which is his cleverness; programs aren't good at 'clever').

Now, I don't know enough about machine learning to say that it can't be used elsewhere (or that a clever cryptanalysis couldn't use a machine learning program to help with his cryptanalysis); however it certainly sounds to me that machine learning would not be enough to do the entire cryptanalysis job.

Machine learning and decision tree models are being used and improved everyday to break ciphers.

Quantum computing coupled with machine learning is nowadays one of the most sophisticated tools for decryption.


What is the strength and attack vectors of this simple scheme? Let's say that Alice wants to communicate some secret value $S$ to Bob through a public channel in a way that other people don't know what the value was.

To do this, Alice publishes that secret value to the public channel, along with $N-1$ other values, making a list $L$ which has $N$ items in it.

Before this communication, Alice and Bob agreed that the value Alice wanted to communicate to Bob would be $L_M$ where $M \in [0,N)$.

How secure is this scheme?  What attack vectors could be used on it? Also, does this technique have a name?

Some thoughts of my own:

The security of the scheme seems to relate to the size of $N$.  Larger $N$ values seem more secure.
It seems like if you didn't choose the other values of the list carefully, that it could be seen statistically that "one data point doesn't fit with the others" which could make the actual value cared about stick out more obviously.
One idea to make the value fit in completely could be that if the secret value $S$ could be represented in $B$ bits, that maybe the list $L$ could be a random shuffle of all values $[0,2^B)$, but if someone knew that, they could know that the number was probably on the higher side of the values so this may be too naive.
Agreeing on $M$ in advance has the usual key generation / key sharing / key storing problems and attack vectors.  I'm not interested in that part of the problem.

Short answer: Sorry, no, unfortunately your concept is neither a secure, practical nor efficient crypto scheme.

Slightly longer answer: To illustrate the impractically of your scheme, let's assume you are sending a completely random bit string $S$ of length $B$. In such case, in order to preserve perfect secrecy, you will at least have to send a list $L$ containing all possible values $[0..2^B)$ in random order, except for $S$ which is fixed at position $M$, where $M$ is the secret key you share with the recipient.

Now, if $M$ is selected completely at random from all possible values, it will also be a random element from $[0..2^B)$ and consequently be exactly as long, and contain as much entropy as, the message $S$ you want to sent.

The cipher text $L$ on the other hand, will be exponentially longer than the plain text message $S$. This is bad, because it means that your effort of sending the message securely, will be exactly as great as the effort you want your adversary to suffer trying to brute force guessing the key or the plain text.

Furthermore, if the plain text $S$ is not completely random, securely executing your scheme gets more complicated, but the conclusion doesn't change. If you maximize security, your effort of encoding and sending the plain text will be no less than the effort you want your adversary to suffer trying to break your scheme.

Reviewing crypto-protocols is in general off-topic here, and there has actually been a lot of discussion about it recently. If the voting keeps its trend, it's likely to become an official closing reason around May.

In general, I believe this answer in Sec.SE is amazingly accurate at explaining why building crypto constructions out of thin air is a bad idea. Recently there was another discussion in the same direction that could be also interesting to check.

The point is: don't reinvent the wheel. There is a lot of concepts that can fit your objective and have been widely tested. My first thought was Diffie-Hellman key exchange, but then I realized that a lot of scenarios can fit, including normal symmetric and asymmetric encryption.

There are things that are immediately apparent in your description, starting by the fact that you need to transfer $N$ items to get one value, and the idea that if they can agree on $M$ securely they could agree on $N$ also using the same channel, but then again: don't try to build with sticks when concrete is an option.


What goals is homomorphic encryption aiming to solve? As I understand from this article about homomorphic encryption, it
mainly aims to enhance the security of cloud computing. We should be able to encrypt data and send it to the cloud. After it is send, we should be able to make computation on the encrypted data and the result of this computation is an encrypted data too. If we decrypt the result of our computation, then we should get back the plain text version of the result.

The question is, why we assume it enhances the cloud computing? We could just encrypt data, send it to cloud. When we need to make computation, query these data to our computers and decrypt it, make computation, then send it back to the cloud if needed.

Homomorphic encryption in and of itself solves the problem of computation on encrypted data. For example, if I give you only the encryptions of $a$ and $b$ ($E(a),E(b)$) can you compute $E(ab)$ and $E(a+b)$. That is the problem that fully homomorphic encryption (FHE) solves. There are also partially homomorphic encryption methods that allow you to only compute one operation (e.g., Paillier and Elgamal).

Cloud computing is "the use of computing resources (hardware and software) that are delivered as a service over a network (typically the Internet)." So, you push your data to the cloud then tell the cloud what computation to perform. The cloud computes the result and sends the answer back to you. The benefit of FHE when applied to the cloud is that all of this can take place without the cloud learning your data. You upload encrypted data, the cloud performs the comptuations on that data, returns the result. That said, it appears that FHE alone is not sufficient for privacy-preserving cloud computing.

Of related interest, I'd suggest you look at In what ways does Full or Partial Homomorphic Encryption benefit the cloud?

Also the cloud is not trusted. The cloud might acts maliciously so this is the reason you encrypt with a symmetric key cipher your data before uploading them. Still fully homomoprhic encryption as far as we know costs a lot and there are practical solutions only for specific operations on data


Why do some people believe that humans are "bad at" generating random numbers/characters like this? I'm not even sure if they are serious, but I've heard many times that some people refuse to not only trust their computer to generate a random string (which is understandable) but also don't trust themselves to do it. So, instead of simply typing/writing down:
fcC540dfdK45xslLDdfd7dDL92

And then randomly changing a few of those to other ones a few seconds later, such as one in the beginning, one in the middle and one in the end, they use dice which they roll again and again to generate random numbers, which are then treated as "truly random" and thus "truly secure".
Why would a dice roll be "more random" than simply coming up with a sequence in your head, and then changing some of them?
I simply don't believe that this could possibly be "not secure". Why the need to do the very tedious dice rolling? It feels like a ritual that they go through, based not on logic and reason, but on some sort of delusion that their brain is going to generate the same sequence as others who guess it, or a computer, even though they also change some of them after the phrase is "done".
I don't understand this. Is there anything that speaks for this practice as being "more random"/"more secure"?

In short, it is more than a belief: there is strong evidence that humans are not good entropy sources. There is a test for this

Man vs. Machine. Or, why Man is not a Particularly Good Source of Entropy.

Try to win!
So we don't rely on whether generating a random number from the mind or random keyboard typings and mouse movements that seem like a monkey playing on the computer from outsiders. We rely on good entropy sources like the /dev/urandom. That kind of sources comes from good research.
Some researches on supporting this;

1972, W. A. Wagenaar, Generation of random sequences by human subjects: a critical survey of the literature

1997, Brugger, P., Variables that influence the generation of random sequences: An update. Perceptual and Motor Skills

2005, Persaud, N, Humans can consciously generate random number sequences: A possible test for artificial intelligence. Medical hypotheses, 65(2), 211-21

2012, Schulz et. al, Analysing Humanly Generated Random Number Sequences: A Pattern-Based Approach

2012, Williams and  Griffiths Why Are People Bad at Detecting Randomness? A Statistical Argument

2014, Towse et. al, Not all numbers are equal: preferences and biases among children and adults when generating random sequences

Other online tests;

not so random with the collected results.

I suppose the problem is not that a human would generate a biased random number. Computers also use biased random sources, but as long as there is entropy in them, they could be hashed into a shorter random enough number. However bad humans are, what humans think of obviously has entropy in it.
The problem is, humans are bad at memorizing true random numbers, and doesn't have an internal hash mechanism (at least there isn't one humans are known to be able to feel and make use of). If they hash mechanically, it would take much time and need to memorize more numbers. Everyone would be lazy and choose to just use a computer. The rest of people who don't feel lazy are the ones who don't know how biased they are and how to make random numbers correctly. What they could get in average is to be expected.


Is it safe for the ChaCha8 nonce to be deterministic? ChaCha8 takes a 8 byte nonce (or IV) that should not be the same twice for the same key. Generating this nonce randomly makes me very very nervous for collisions.

Is it safe to generate this nonce deterministically?

For example the first 6 bytes could be the number of milliseconds since the Unix epoch, with the last 2 bytes being an unsigned counter wrapping around. This will prevent any collisions from happening for 9000 years if no more than 65535 streams get encrypted in a millisecond (things get more complicated if the same encryption key is being used by multiple machines/threads, but let's ignore that for now).

Yes, it is safe. The only requirement for the nonce in Salsa/Chacha is to be unique; being predictable is not an issue, so a counter is fine.

Like CodesInChaos indicated, I believe extending XSalsa20 to XChaCha20 would also work if you want to a larger nonce, but have nothing concrete so will leave the details to him/her.

Looking at the reference implementation, it looks like the IV is 64 bytes, not 8. In ECRYPT_ivsetup, it's a pointer to uint8_t, which is then treated as a pair of quartets (e.g., 8) of 8-byte values.