pbsd

That appears to be a direct C++ translation of item 175 from HAKMEM [1]. This does not require a division and can be done much faster, see section 1.24 of [2].

[1] http://www.inwap.com/pdp10/hbaker/hakmem/hacks.html#item175

[2] https://jjj.de/fxt/fxtpage.html#fxtbook

The first one is already explained, a^b + 2*(a&b) is computing the sum and carry in parallel, and then adding them up.

The second formula is more elaborate, and makes heavy use of the above identity:

      2*(a|b)-(a^b)
    = 2*((a&b)^a^b)-(a^b) (express boolean or in terms of and and xor)
    = 2*(a&b) ^ 2*(a^b) - (a^b)
    = 2*(a&b) + 2*(a^b) - (a^b) (there can't be carries, so xor equals addition in this case)
    = 2*(a^b) + 4*(a&b) - 2*(a&b) - (a^b)
    = 2*((a^b) + 2*(a&b)) - 2*(a&b) - (a^b)
    = 2*(a+b) - (a+b)
    = a+b.

Yeah, I was wrong. Mixed up the signed and unsigned cases.

This has nothing to do with undefined behavior. Switch the code to unsigned integers, where overflow is perfectly defined as wrapping, and the result is exactly the same.

The compiler, to avoid the division, compares x * 0x1ff with 512 * 0xffff instead of x * 0x1ff / 0xffff with 512. This comparison is obviously bunk, since it doesn't take the uppermost bits of the multiplication into account. But so is the original comparison!

You see the same thing happen in Rust -- https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.

You can do the same thing with modular exponentiation, i.e. Pocklington's primality proving, but that requires finding a large factor of N-1, which is not easy in general.

With elliptic curves you get as many shots at finding a group order with a large factor as you want, since if you fail the current attempt you can simply try another curve with a different order. So you can keep trying until you find a curve that has an easy to find large group order factor which, as it turns out, happens in probabilistic polynomial time.

I think you're referring to Mike Hearn's https://moderncrypto.org/mail-archive/messaging/2014/000780....

vpmullq is not that useful; in bignum code you also want the upper part of the product, and there is no corresponding vpmulhq instruction to get that.

On the other hand, vpmadd52luq and vpmadd52huq do give you access to the lower and upper parts of a 52x52->104 bit product, and those instructions perform well in the Intel chips, 3x faster than vpmullq.

Golden Cove has the same sizes as Willow Cove, though different geometry (10 vs 20-way L2, for example). However, Golden Cove's L3 has incredibly high latency compared to predecessors, which might be what makes it work by forcing data to stay in the superqueue longer.

It bugs me that they classify Alder Lake as being Sunny Cove. It is not. The code name for Alder Lake is Golden Cove / Gracemont for performance/efficiency cores.

In fact it is quite strange that the attack skips Tiger Lake (Willow Cove), which changes almost nothing from Sunny Cove besides L2 and L3 cache sizes, but shows up again in Alder Lake (which has two types of cores: does the attack work on both efficiency and performance cores?)

That's just how RSA works, via Fermat's little theorem: e * d_q mod (q-1) = 1, so m^(e * d_q) mod q = m^1 mod q = m.

There is nothing left to add because m_2 is already the correct value:

- If m is also < p, then (m_1 - m_2) is obviously 0, and so will be h.

- If m >= p, then m must be of the form m_1 + k * p for some k. But we've already established that m = m_2, so m_1 - m_2 = (m - k * p) - m_2 = -k * p = 0 mod p. Thus h = 0.

So regardless of the value of qinv, we get m verbatim if it's less than q. d_p and d_q are d mod (p-1) and d mod (q-1) respectively.

Here, this Sage script is short enough that it all fits in a comment. I guess 624 bits and recover the remaining 400 with Coppersmith; this is fast enough to run in a few seconds.

    def oracle(c, d, p, q, qinv):
        m_1 = power_mod(c, d % (p-1), p)
        m_2 = power_mod(c, d % (q-1), q)
        h = (m_1 - m_2)*qinv % p
        m = m_2 + h * m_1
        return (m >> (211*8)) != 0 # check if sid != 0

    # Setup
    p = random_prime(2^1024, lbound=2^1023+2^1022)
    q = random_prime(2^1024, lbound=2^1023+2^1022)
    n = p*q
    e = 65537
    d = inverse_mod(e, (p-1)*(q-1))
    qinv = inverse_mod(q, p) + randint(0, 2^128) # random error block inserted in the least significant 128 bits

    msb_q = 0
    for bit in reversed(range(400, 1024)):
        # if m < q, we are within range
        if not oracle(power_mod(msb_q + 2^bit, e, n), d, p, q, qinv):
            msb_q += 2^bit

    # Find a small root of msb_q  + x modulo a divisor of n of size ~n^(1/2)
    P.<x> = Zmod(n)[]
    f = msb_q + x
    [lsb_q] = f.small_roots(beta=0.49, epsilon=1/32)
    # Check we've reached the correct solution
    assert(q == msb_q + lsb_q)

Look at how RSA CRT decryption works:

    m_1 = c^d_p mod p
    m_2 = c^d_q mod q
    h = (m_1 - m_2)*q^-1 mod p
    m = m_2 + h * m_1

If m < q, m_2 = m and there is nothing left to add. But if m >= q, there needs to be something to add, and this something will very likely be wrong and kind of random, because q^-1 mod p is wrong. The distinguisher between the two cases hinges on the upper bits of the decryption result being (non-)0. So for this attack to work all you have to do is change any part of q^-1; it doesn't really matter much what the change is.

Now you have a binary search oracle for q, from which you can iteratively obtain the most significant bits of q, one guess at a time (e.g., try m = 2^1024 first, then (2^1024 or 0) + 2^1023, etc). Once you have half of the most significant bits of q, you can use the Coppersmith method [1] to find a small root of f(x) = msb(q) + x modulo a divisor of n and thus recover the rest of q.

In reality doing exactly 512 iterations of guessing plus Coppersmith is pretty costly; if possible, guessing a few more bits will make the Coppersmith step much faster.

[1] https://en.wikipedia.org/wiki/Coppersmith_method

You could also do `1|!((x|-x)>>30)`

Entries #13, #36, #37, #38, #39 on the current list are Azure clusters. #52 is an EC2 cluster.

I'm not sure how that could be the case. Dan was among the first to push the notion of post-quantum cryptography, along with Johannes Buchmann and his research group at Darmstadt (which credit him in [1] with the coining of the notion of "post-quantum cryptography"). Both organized the first PQCrypto conference in 2006, and edited the first book on post-quantum crypto.

[1] https://eprint.iacr.org/2004/297

Each new output value i can collide with output 1, 2, ..., i-1. So the collision probability of iteration i is (i-1)/2^256. Adding all of the iterations up you have 1/2^256 + 2/2^256 + ... + (i-1)/2^256 = 0.5 i (i-1)/2^256 which approaches 1/2 as you get to 2^128.

In reality you use some variant of Rho which does not store every previous value but uses something like Floyd's cycle detection or distinguished points and requires minimal storage, at the cost of some extra hash computations but still on the order of 2^128.

There's no real way to connect the compression function to any kind of mathematical model that would help here, other than modeling it as random. Provability is out the window.

So what you do is assume it behaves like a random function until proven otherwise, by _some_ property that deviates from this model. (This is not even the case for SHA-256, since neither the hash nor the compression function can be modeled as random oracles (due to length extension and the Davies-Meyer structure), but we can conveniently forget that for the duration of this thread.)

There _are_ some hash functions based on number-theoretic problems where you could reason about such things, but none of those are in common use since they are usually slow and/or require an output unstructured transformation anyway to turn them into proper, rather than just collision-resistant, hash functions.

A hash function aims to replicate the properties of a truly random function.

The probability that a random function does _not_ output 0 given some specific input block is (1 - 1/2^n). Taking each of the possible 2^b input values into account this means that 0 is not an output for any input with probability (1 - 1/2^n)^(2^b) ~ e^(-2^(b-n)).

For SHA-256 with n = 256 and b = 512 (one can treat the compression function as a 768 to 256 bit random function, but we can stick to the worst-case single-block message case here) we have that the probability of 0 _being_ an output for a single-block message is 1-e^(-256) which effectively means it exists, but the probability never quite reaches 1.

SHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.

Fortuna was analyzed (and generalized) in https://eprint.iacr.org/2014/167. It's a solid design.

That might have been ICL065 [1], whose fix was disabling register move elimination at the renaming stage. The timing matches.

[1] https://cdrdv2.intel.com/v1/dl/getContent/341079

1/135 cycles per byte on Skylake is just plain impossible, even if the hash consisted of simply one xor per 32 bytes of input.

The lower bound for CLHASH would be the cost of one carryless multiplication per 16 bytes of input, or in other words 1/16 ~ 0.0625 cycles per byte, since you can only issue one such multiplication per cycle.

Any boolean function can be represented as a polynomial over the integers modulo 2 (that is, its algebraic normal form).

Modulo 2, AND is multiplication and XOR is addition. We also have the useful properties 1+1=0, x+x=0, and x^2 = x. Thus:

    NAND(0, 0) = 0*0 + 1 = 1

    NAND(x, y) = x*y + 1

    AND(x, y) = NAND(NAND(x, y), NAND(x, y)) = (x*y + 1)*(x*y + 1) + 1 = x*y + x*y + x*y + 1 + 1 = x*y

    XOR(x, y) = NAND(NAND(x, NAND(x, y)), NAND(y, NAND(x, y))) = (x * (x*y + 1) + 1) * (y * (x*y + 1) + 1) + 1 = (x*y + x + 1) * (x*y + y + 1) + 1 = x*y + x*y + x*y + x*y + x*y + x + x*y + y + 1 + 1 = x + y

Since both AND and XOR can be obtained from NAND, any polynomial can be constructed. It also becomes obvious that you can't get x*y from x+y and vice-versa, so neither XOR nor AND can be universal gates on their own.

NOR's algebraic form is x*y + x + y + 1, from which you can similarly derive AND and XOR. XNOR is x + y + 1, from which AND cannot be obtained.

There is also more/different functionality (e.g., designing a permutation or a tweakable blockcipher instead of a plain blockcipher, or a hash based on those), or better analyzability---making primitives that are simpler to "prove" (or make an argument for) secure against some classes of attacks.

And these days there are also the primitives purposefully designed to run in blockchain....whatever it is, using large GF(p) or GF(2^n) field operations as components. This mostly falls under the "more limited hardware" umbrella.

Correct, the truncated versions of SHA2 are secure against length extension.

The compression function in a hash function has nothing to do with the general data compression that TLS got rid of; it's a component of the hash that takes n bits and outputs less than n bits in an as unstructured manner as possible.

When the integer is expected to be dense, you have the corresponding trick

    size_t count = sizeof(x) * 8;
    while(x != -1) {
        x |= x+1;
        --count;
    }
    return count;

That sounds like a decent primitive to accelerate arbitrary bit permutations in software. It's known as GRP in, e.g., [1].

[1] http://palms.ee.princeton.edu/PALMSopen/shi00bit.pdf

Yeah that is true. Also you could still stick with xor and shift/rotate, but make the shifts data-dependent. That would make it nonlinear (technically a multiplication), but analysis is generally more difficult.

Strictly speaking, shift and xor alone will not net you a secure cipher, seeing that those are both linear GF(2) operations. You would need something else in the mix to generate some nonlinearity, like integer addition, multiplication, etc.

But on the subject of extremely simple constructions, you can compose many random permutations of a particular form---state[i] = state[i] xor F(state[j], state[k]), where state[i] is the ith bit of the state and F is a randomly chosen boolean function--- and obtain something asymptotically secure [1].

[1] https://arxiv.org/abs/math/0411098