pbsd

17 ms·

61.
by pbsd 4y ago
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 * 0x
62.
by pbsd 4y ago
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 o
63.
by pbsd 4y ago
I think you're referring to Mike Hearn's https://moderncrypto.org/mail-archive/messaging/2014/000780....
64.
by pbsd 4y ago
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
65.
by pbsd 4y ago
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
66.
by pbsd 4y ago
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 (Willo
67.
by pbsd 4y ago
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.
68.
by pbsd 4y ago
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 estab
69.
by pbsd 4y ago
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
70.
by pbsd 4y ago
You could also do `1|!((x|-x)>>30)`
71.
by pbsd 4y ago
Entries #13, #36, #37, #38, #39 on the current list are Azure clusters. #52 is an EC2 cluster.
72.
by pbsd 4y ago
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
73.
by pbsd 5y ago
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)&#x2
74.
by pbsd 5y ago
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
75.
by pbsd 5y ago
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 a
76.
by pbsd 5y ago
SHA-256 is not a permutation; the expected cycle length is ~2^128. It's how collisions are (generically) found.
77.
by pbsd 5y ago
Fortuna was analyzed (and generalized) in https://eprint.iacr.org/2014/167 . It's a solid design.
78.
by pbsd 5y ago
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
79.
by pbsd 5y ago
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 ot
80.
by pbsd 5y ago
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
81.
by pbsd 5y ago
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
82.
by pbsd 5y ago
Correct, the truncated versions of SHA2 are secure against length extension.
83.
by pbsd 5y ago
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.
84.
by pbsd 5y ago
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;
85.
by pbsd 5y ago
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
86.
by pbsd 5y ago
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.
87.
by pbsd 5y ago
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.
88.
by pbsd 5y ago
If you insist, you could calculate the log2 as something like x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; return popcount(x-1); but there isn't really
89.
by pbsd 5y ago
llvm-mca is highly unreliable when it comes to AVX-512. It thinks 3 512-bit vpaddd, vpsubd can be run per cycle. Adjusting for that you get 622 cycles instead of 528.
90.
by pbsd 5y ago
On Skylake-SP's AVX-512, instructions that previously were dispatched to port 0 or 1 get instead dispatched to ports 0 _and_ 1. So instructions like vpsrlq get zero net speedup from switching to AVX-512 from AVX2. Instructions that pre

More ›