Isn't the point of "Prime and Prejudice" that primality tests that are perfectly adequate for RSA key generation are inadequate to verify the primality of adversarial inputs, in protocols like negotiated DHE or whatnot?
2,790 karma · joined November 14, 2011
The usual reference for this is Brilhart et al. [1], which deals with polynomial representations in arbitrary bases, as opposed to strictly base 2, as is the case here.
FFT multiplication is basically a residue number system product on polynomials. Evaluating a polynomial p(x) at a point w_i is the same as computing p(x) modulo (x - w_i), where w_i here is one of the nth roots of unity. So the FFT computes p(x) mod (x - w_0), p(x) mod (x - w_1), ..., multiplies each residue individually, and the inverse FFT recovers the result modulo (x - w_0)(x - w_1)...(x - w_{n-1}) = x^n - 1.
More generally, I think the distinction between a "block-based stream cipher" and a block cipher (or permutation) mode is the degree to which you abstract away the block cipher. Personally I wouldn't put them together. Counter mode completely abstracts away the cipher, assuming it is an idealized pseudorandom function; sponge-based modes also abstract away the permutation as ideal in most cases; stream ciphers usually do not do this, and use weaker (but still sometimes block-based) primitives to generate output. There are, for example, sponge modes that use very few rounds past the initialization, which makes them more streamy than spongy. So their cryptanalysis is often different.
The scary thing here is not so much the error in the proof, which does not have many repercussions beyond OCB2, but that it went 14 years without being discovered. This despite the OCB2 paper, which introduced XEX, being highly influential. Every time something like this happens, confidence on the security of all "provably secure" schemes is undermined.
The definition of authenticated encryption is, essentially, indistinguishability of the ciphertext plus MAC security of the tag. You're right, the tag does not need to be indistinguishable from random, but in the majority of the cases it is anyway.
One significant difference between these non-cryptographic generators and cryptographic ciphers is that of latency---generators often optimize for latency, whereas ciphers optimize for throughput. By taking a cipher and a sufficiently large buffer, you can have low latency as well, at the cost of some memory.
For comparison, consider MORUS, AEGIS, and Tiaoxin, three unbroken contestants of the CAESAR competition. MORUS uses only AND, XOR, and bitwise rotation, and achieves somewhere between 0.5 and 0.66 cycles per byte on current x86 chips. AEGIS and Tiaoxin use the AES round, and where AES-NI is available, performs at between 0.15 to 0.25 cycles per byte. The claim somewhere above is that PCG can do 0.25 cycles per byte (or 4 words per cycle) when going all out with AVX-512; that's only hard to beat if you've not been paying attention.
You could probably achieve the same result (assuming you want to avoid adc instructions, for some reason) by using setc r8 plus shr r8, 1 to get the carry back.
The disassembly for the Rust output of `u256_full_mul` at the end is also terrible, and it looks like the output of a debug build. There's no reason an optimizing compiler should be outputting `pushfd` and `popfd` in performant code. The benchmarked loop does not have those instructions.
inc [rdi+rbx]
You also see the same behavior, according to Agner, on SHR/SHL m, i, which may or may not alter some flags depending on shift amounts, and strangely on NOT m, which explicitly does not alter the flags in any situation. This latter one makes little sense.
And yes, if you do mov r, m / add r, 1 / mov m, r instead of add m, 1 no such fusion happens. This is specific to CISCy instructions that do more than one thing at the same time.
[1] https://software.intel.com/sites/products/documentation/docl...
[2] https://software.intel.com/sites/products/documentation/docl...
This is not exactly what happens. A read-modify-write instruction in general results in 2 fused uops, one for the read+op, the other for the address generation+write.
In the specific case of INC, you still have 3 fused uops for unclear reasons---possibly because INC only partially changes the flags. Replacing the expression by ADD [memory], 1 results on the expected 2 fused ops.
- Dan Page published [1] in 2002, describing an attack on DES exploiting cache timings. In 2003, he published [2] describing countermeasures to this class of attacks.
- Concurrently, a Japanese team also attacked DES (and MISTY1) with cache timing [3, 4].
- Dan Bernstein published the first version of his AES cache timing attack in late 2004 [5].
[1] https://eprint.iacr.org/2002/169
[2] https://doi.org/10.1016/S1363-4127(03)00104-3
[3] https://link.springer.com/chapter/10.1007/978-3-540-45238-6_...
[4] https://web.archive.org/web/20060906064630/http://web.engr.o...
The reason is that std::swap(v1, v2) must never invalidate existing iterators and/or references to elements into either vector, which the optimization would clearly break.
std::string is the type you may be thinking of, where the standard does make a special exception to enable the SSO.
mov rcx, 400000000-1
up:
nop
nop
nop
add [counter], rcx
nop
nop
nop
dec rcx
nop
nop
nop
jnz up
ret
No, the legacy decoder is virtually unused. This loop was designed to take advantage of the rules of the DSB. If you have the LSD enabled I don't quite know what the effect is.
EDIT: Sorry, just realized I screwed up translating AT&T to Intel---add rcx, [counter] should clearly be add [counter], rcx.
> It may be that the maximum difference is whether we get a 4 cycle turnaround on the store-load forwarding versus a 5 cycle.
This is my guess as well, though I have nothing to show for it. It's actually possible to bring it down to 400000000 uops by delaying the loop even further with the same technique, but it won't speed anything up. The 4-cycles-per-iteration barrier seems insurmountable, which makes sense.
In any case, I have to admit being wrong; port 6 has nothing to do with it, though the general principle of stalling the frontend to prevent the backend being overloaded still holds. For example, here's how to get the speedup without any change in control flow:
mov rcx, 400000000-1
align 32
nop
up:
align 32
add rcx, [counter]
align 32
dec rcx
align 32
jnz up
ret
As to why this actually makes things faster, I don't know. There are many more stalls owing to the reservation station being full in the tight loop:
1,348,491,506 resource_stalls_any
1,694,613,980 uops_issued_stall_cycles
759,763,767 uops_executed_stall_cycles
994,974,421 uops_retired_stall_cycles
109,300,935 resource_stalls_any
120,303,318 uops_issued_stall_cycles
164,322,430 uops_executed_stall_cycles
15,834,456 uops_retired_stall_cycles
756,686,062 uops_dispatched_port_port_0
782,579,771 uops_dispatched_port_port_1
279,387,822 uops_dispatched_port_port_2
314,214,218 uops_dispatched_port_port_3
1,994,313,938 uops_dispatched_port_port_4
807,514,909 uops_dispatched_port_port_5
1,050,884,205 uops_dispatched_port_port_6
209,316,457 uops_dispatched_port_port_7
640,957,968 uops_dispatched_port_port_0
637,621,266 uops_dispatched_port_port_1
399,224,647 uops_dispatched_port_port_2
400,205,411 uops_dispatched_port_port_3
1,610,294,604 uops_dispatched_port_port_4
643,780,748 uops_dispatched_port_port_5
848,142,785 uops_dispatched_port_port_6
470,700 uops_dispatched_port_port_7
CALL, RET, and JNE all share the same execution port (6 in Skylake), so it seems plausible that the added pressure in this port prevents speculative execution from continuing with the loop at the same rate as the tight loop. If you look at the execution port breakdowns of each loop, port 6 dominates in the call loop, whereas the tight loop is bottlenecked at port 4 (the port where stores go).
By delivering fewer uops per cycle, the pressure on the backend is eased. But this is a delicate balance. If you add another call, the loop becomes much slower than the tight loop.
You can get a similar effect by replacing `__asm__("call foo")` with
__asm__("jmp 1f\n1:\n");
__asm__("jmp 1f\n1:\n");