pbsd

The 2^64 attack there is for 128-bit ECC, which is not hypothesis---it's a standard Pollard rho attack. That is, the entire purpose of rho is to find a "key collision" aP + bQ = cP + dQ, from which we can immediately derive the secret key.

The point there is that batching helps the attacker finding the first AES key by a factor of m, m being the number of keys being attacked, but it doesn't really help finding the first ECC key---although it does help with the cost of finding the second, third, etc a bit. So for example, the effective multi-key security of AES-128, given 2^32 different keys (read: sessions), is 2^96.

See for example [1] for a formalization of multi-key security in the symmetric encryption setting.

[1] https://eprint.iacr.org/2015/101

> but everyone was happy with it.

For what it's worth, that worst-of-all-worlds solution was what made me give up on Rust back on 0.9, and I haven't really missed it since.

Grover's algorithm does not help much against collisions; Brassard-Hoyer-Tapp (which does use Grover internally) does (at ~2^85 time), but requires a large (also ~2^85) amount of quantum storage. Basically: generate ~2^85 random strings and respective hashes, then use Grover to find one new preimage in ~2^85 (instead of classical ~2^170) time.

In practice classical rho collision-finding is more resource-efficient: replace the crazy ~2^85 storage by ~2^85 small memoryless computing units, and find a collision in 2^128 / 2^85 ~ 2^43 time. Or match the quantum time with only ~2^43 computing units, and negligible storage.

0F 1A and 0F 1B have recently become memory bound verification instructions, as part of MPX. So really, only 0F 1F is likely to be long-term safe to use as a multibyte NOP.

Likewise, after Pentium 4 REP NOP (F3 90) became PAUSE, the spinlock waiting hint instruction, so one needs to be careful about prefixes with the old NOP as well.

Well, I suppose you could cite Miller and Koblitz on that (mostly Miller). This was the mid-80s, when progress in index-calculus algorithms was in full force. So they introduce elliptic curves, and basically say 'look, this problem seems to be immune to these classes of algorithms, which seem to be getting better all the time, so let's use it instead'. With some important caveats discovered in the meantime, they have been right so far.

I think progress against RSA is more likely, unless Shor happens first and kills everyone. I also hope to see a O(n^2) matrix multiplication algorithm within my lifetime. My point was not to defend RSA, but to point out that Cohn's argument could be reused for most of our current primitives.

The argument laid out by Cohn also works against elliptic curves: the discrete log is not NP-hard either, and if anything even less people have tried to attack it than factorization (according to Cohn, subexponential factorization only happened in the 1970s, after centuries of trying; elliptic curves are not that old). Some lattice problems, on the other hand, are known to be NP-hard. What does this tell us about their worthiness as cryptographic problems? Not a lot.

Some extra context: here's Maurer [1, §4], in 1991, describing the same property exploited here, on a generic class of CBC-like functions. Also, Knudsen [2, §4.4] on his 1994 PhD thesis. I believe Schneier et al.'s 'Practical Cryptography' also mentioned this. The Sweet32 paper only mentions papers from 2011 and 2012, so one might be mislead to believe this was something relatively new.

[1] https://dx.doi.org/10.1007/3-540-46416-6_39

[2] http://dx.doi.org/10.7146/dpb.v23i485.6978

I don't think it's an oversight; the implementation calls `checked_add` and `checked_mul` explicitly -- https://github.com/rust-lang/rust/blob/1744c46e47434d8c0b63a...

GNU confirmed as Equation Group: https://godbolt.org/g/EDvrn2. Wait, MSVC does this too---they're all in cahoots!

    $LL8@f:
    ; Line 4
        mov ecx, DWORD PTR [edx+eax*4-4]
        sub ecx, 1640531527             ; 61c88647H
        mov DWORD PTR [edx+eax*4], ecx
        inc eax
        cmp eax, 44                 ; 0000002cH
        jl  SHORT $LL8@f

Flipping the sign of addends is a common compiler transformation, likely there to optimize for code size in some cases. Unless that code looks weird enough that it _had_ to be coded by hand, that constant switch doesn't mean much of anything.

AES-NI uses the XMM register bank, but not necessarily any vector execution unit. Furthermore, it only uses the lower 128 bits of vector registers, whereas the linked document is referring to instructions that use the upper lanes as well, i.e. YMM or ZMM registers.

  We can demonstrate more forcibly that any such statement would be unjustified.
  For suppose we could be sure of finding such laws if they existed. Then given
  a discrete-state machine it should certainly be possible to discover by
  observation sufficient about it to predict its future behaviour, and this
  within a reasonable time, say a thousand years. But this does not seem to be
  the case. I have set up on the Manchester computer a small programme using
  only 1,000 units of storage, whereby the machine supplied with one sixteen-
  figure number replies with another within two seconds. I would defy anyone to
  learn from these replies sufficient about the programme to be able to predict
  any replies to untried values.

This is possibly one of the first examples of a pseudorandom function as we understand the term today. I would love to know what Turing's function was, and how breakable it would be with today's techniques.

For the sake of pedantry, SHA-512 eats 1024 bits, resp. 512 bits for SHA-256, at a time. It's the chaining variables that are of those lengths.

I think even Intel is confused about their own extensions at this point. The E7 and E5 Xeons are Haswell systems that slightly speed up SHA-256 and 512 with the introduced BMI2 RORX instruction.

As far as I know there are no SHA extensions before Goldmont, as mrb said, and in Cannonlake for non-low-power chips.

SHA-512 should be much faster than SHA-256 on AVX2-capable processors. Go's implementation is subpar; try OpenSSL instead. On Skylake, SHA-512 is about as fast as MD5 now -- https://bench.cr.yp.to/results-hash.html#amd64-skylake

You can still freely access global variables inside lambdas, with or without captures.

That may be the case, but whatever the Clang frontend sends to C2 does produce better code than the Microsoft frontend. It probably already folds the stores at the frontend level, instead of leaving it to the backend to figure out.

Well, the Go implementation of P-256 is meant to be constant-time, even if we don't get a hard guarantee that the compiler won't screw that up somewhere somehow. On the other hand, the generic implementation of the other curves is almost comically vulnerable to timing attacks---compare [1] to [2].

[1] https://github.com/golang/go/blob/master/src/crypto/elliptic...

[2] https://github.com/golang/go/blob/master/src/crypto/elliptic...

The hybrid ciphersuite idea comes from [1, Section 5.2], though you could also chalk it up to common sense. I don't think the blog spells out how it's done.

[1] https://eprint.iacr.org/2014/599

Along these lines, it has been argued that the ancient Greeks could have discovered Lucas-Lehmer with their contemporary technology: https://infoscience.epfl.ch/record/215073/files/MGFinal.pdf

Your survey refers twice, in page 8, to Mike Hamburg as Hamburger. Got a chuckle out of me, but you should probably fix that.

You can think of it as a magic trick. The magician is convincing you the he's computing a totally legit action X, all the while abusing your trust (or your cognitive biases) to perform action Y instead right under your nose.

In this case, the abuse is to have you believe the modulus---which defines the core mathematical structure you're working on---is a prime, when it is not. Once you manage to sell this, and clearly not everyone checks the primality of their moduli, the rest become implementation details.

I'm pretty sure a simple while loop is better than either:

  size_t strlen(const char * s) {
    size_t index = 0;
    while(s[index] != 0) {
      index += 1;
    }
    return index;
  }

There's this well-known identity [1] a + b = (a ^ b) + ((a & b) << 1). This is essentially how a parallel ripple carry adder works. So (a + b) / 2 = (a + b) >> 1 = ((a ^ b) >> 1) + (a & b).

[1] http://www.inwap.com/pdp10/hbaker/hakmem/boolean.html#item23

There's a recent family of AES-based designs, explicitly exploiting AES-NI, that would make a good starting point for fast secure PRNGs: https://eprint.iacr.org/2016/299.

While some of NaCl's kernels are written using qhasm, qhasm itself is not part of the build process of NaCl. This means that those functions cannot be ran on, say, Windows, because the calling convention (and the assembly syntax) is different. qhasm also does not have programming capabilities, so one would need a lot of code duplication to write an SSE2, SSSE3, AVX2, etc variant of the same function. While OpenSSL's perlasm is an abomination, it does produce "portable" assembly output, and there is no obvious superior option to accomplish that. This is something sorely missing from our collective toolchains.

The most notable thing is the lack of assumptions. You don't have to assume anything other than the min-entropy of the sources. With a hash function, you generally need to assume that the hash function is a good extractor, instead of showing that it is one. Instead, what we have here is an extractor built up from first principles.

Also, note that you need at least two independent sources. This is because with a single source you just can't have a good extractor for any imperfect source. For example, imagine you are using a hash function to extract one uniform bit from an n-bit input. If the input source is the set of all n-bit strings such that H(x) = 0, which has pretty high min-entropy, you end up with a 'randomness extractor' that is just a constant function. This is highly contrived, but that is what you have to work with when you say "any" in theorem statements.

To fix this, you need at least two sources, where one source 'keys' the other, and therefore as long as the sources aren't working together (i.e., they are independent), there is nothing they can do to sabotage our randomness extraction. The inner product is a simple example of an extractor that works as long as each source has at least n/2 min-entropy. I have no idea what the construction of this new paper looks like, but it's an improvement on this min-entropy required. However, since this improvement is asymptotic, it's unclear whether it is any useful at all for realistic ranges of length and min-entropy.

In reality, this is entirely irrelevant for practical purposes. The work-horse tools of randomness extraction in practice are hash functions, block ciphers, and universal hashes, so this new paper is interesting from a theoretical point of view only. Yet another example of university PR departments being insultingly misleading in their press releases.