pbsd

The first version of the X9.62-1998 standard, where these curves first showed up, only had P-192, P-256, and the prime192v{1,2,3} and prime239v{1,2,3} curves. These also happen to be the curves with the earliest timestamps (along with P-384 and P-521). It also contained 163-bit curves, but none of those correspond to the later B-163 curve.

So yeah, it seems plausible P-224 and the B-* curves were generated at a later date.

That is mentioned in a years old post: https://saweis.net/posts/nist-curve-seed-origins.html

An old version of binutils [1] explains what DDS means:

    How to encode VEX.vvvv:
    0: VEX.vvvv must be 1111b.
    1: VEX.NDS.  Register-only source is encoded in VEX.vvvv where
       the content of source registers will be preserved.
       VEX.DDS.  The second register operand is encoded in VEX.vvvv
       where the content of first source register will be overwritten
       by the result.
       VEX.NDD2.  The second destination register operand is encoded in
       VEX.vvvv for instructions with 2 destination register operands.
       For assembler, there are no difference between VEX.NDS, VEX.DDS
       and VEX.NDD2.
    2. VEX.NDD.  Register destination is encoded in VEX.vvvv for
    instructions with 1 destination register operand.
    3. VEX.LWP.  Register destination is encoded in VEX.vvvv and one
       of the operands can access a memory location.

[1] https://sourceware.org/git/?p=binutils-gdb.git;a=commitdiff;...

The cycle count for RDTSC is ~25 cycles on Skylake-era microarchitectures. The 49 number shown in the OP seems off.

I mean, he's comparing 2024 Zen 5 and M4 against two generations behind 2022 Intel Raptor Lake. The Lion Cove should be roughly on par with the M4 on this test.

Because the function is not quite correct. It should be

    return n ? (1u  + popcount(n & n - 1u)) : 0u;

which both Clang and GCC promptly optimize to a single popcnt.

You're talking past each other. The timing attack was in the PAKE protocol itself, which involved hashing sensitive input into an elliptic curve point using the hunt-and-peck method, whose running time is very dependent on the input. The choice of curve here is irrelevant.

This can be translated to the discrete domain pretty easily, just like the NTT. Pick a sufficiently large prime with order 15k, say, p = 2^61-1. 37 generates the whole multiplicative group, and 37^((2^61-2)/3) and 37^((2^61-2)/5) are appropriate roots of unity. Putting it all together yields

    f(n) = 5226577487551039623 + 1537228672809129301*(1669582390241348315^n + 636260618972345635^n) + 3689348814741910322*(725554454131936870^n + 194643636704778390^n + 1781303817082419751^n + 1910184110508252890^n) mod (2^61-1).

This involves 6 exponentiations by n with constant bases. Because in fizzbuzz the inputs are sequential, one can further precompute c^(2^i) and c^(-2^i) and, having c^n, one can go to c^(n+1) in average 2 modular multiplications by multiplying the appropriate powers c^(+-2^i) corresponding to the flipped bits.

No, the generated code seems to be mostly the same as the manual version: https://gcc.godbolt.org/z/aK8orbKE8

The main difference there seems to be that GCC treats the if() as unlikely to be taken while the for() as likely.

The SIKE comparison is not particularly inconsistent since Bernstein has been banging the drum that structured lattices may not be as secure as thought for years now.

Currently the best attacks on NTRU, Kyber, etc, are essentially the same generic attacks that work for something like Frodo, which works on unstructured lattices. And while the resistance of unstructured attacks is pretty well studied at this point, it is not unreasonable to suspect that the algebraic structure in the more efficient lattice schemes can lead to more efficient attacks. How efficient? Who knows.

I thought this was gonna be about the actual Scream stream cipher: https://eprint.iacr.org/2002/019

Cimino's Heaven's Gate (1980) is usually pointed as the movie that caused the "no animals were harmed" disclaimer to be added to subsequent movies.

Vector ALU instruction latencies are understandably listed as 2 and higher, but this is not strictly the case. From AMD's Zen 5 optimization manual [1], we have

    The floating point schedulers have a slow region, in the oldest entries of a scheduler and only when the scheduler is full. If an operation is in the slow region and it is dependent on a 1-cycle latency operation, it will see a 1 cycle latency penalty.
    There is no penalty for operations in the slow region that depend on longer latency operations or loads.
    There is no penalty for any operations in the fast region.
    To write a latency test that does not see this penalty, the test needs to keep the FP schedulers from filling up.
    The latency test could interleave NOPs to prevent the scheduler from filling up.

Basically, short vector code sequences that don't fill up the scheduler will have better latency.

[1] https://www.amd.com/content/dam/amd/en/documents/processor-t...

>Even after the static variable has been initialised, the overhead of accessing it is still considerable: a function call to __cxa_guard_acquire(), plus atomic_load_explicit(&__b_guard, memory_order::acquire) in __cxa_guard_acquire().

No. The lock calls are only done during initialization, in case two threads run the initialization concurrently while the guard variable is 0. Once the variable is initialized, this will always be skipped by "je .L3".

The Pentium 4 had branch hints in the form of taken/not taken prefixes. They were not found to be useful and basically ignored in every subsequent Intel microarchitecture, until Redwood Cove brought back the branch taken prefix in 2023.

This circuit [1] puts it at <=135k bit operations. Bitcoin uses SHA-256, not SHA-1.

[1] https://nigelsmart.github.io/MPC-Circuits/sha256.txt

Karatsuba is definitely faster than schoolbook multiplication at practical sizes. You presumably mean Strassen.

In page 10, should the ring R be GF(2)[X]/(X^32-1) and the map p be from {0,1}^{32} to R?

Interestingly enough, the Square attack (otherwise more generally known as integral cryptanalysis) is much more powerful than regular linear or differential cryptanalysis when applied to the AES.

Antoine Joux was on the side of classical cryptanalysis on a 2014 bet. This was right after the small-characteristic discrete log advances, so that might no longer be the bet if it was made today.

https://x.com/hashbreaker/status/494867301435318273

Jasmin is something like this. It is essentially a high-level assembler, will handle register allocation (but not spills) for you, has some basic control flow primitives that map 1-to-1 to assembly instructions. There is also an optional formal verification component to prove some function is equivalent to its reference , is side-channel free, etc.

[1] https://github.com/jasmin-lang/jasmin/wiki

It goes way back; check the work of the likes of Thorsten Holz or Christof Paar. TU Graz is another one.

Trying some perf events confirms that there is no extra inserted uop. Going back to the SHLX R[i], R[i], RCX loop, we have:

No anomaly:

     2,190,954,207      cpu_core/cycles:u/                                                      ( +-  0.14% )
     4,412,790,656      cpu_core/uops_issued.any:u/                                             ( +-  0.11% )
        39,386,389      cpu_core/exe_activity.1_ports_util:u/                                        ( +- 11.57% )
     2,121,401,346      cpu_core/exe_activity.2_ports_util:u/                                        ( +-  0.11% )
         6,015,432      cpu_core/exe_activity.exe_bound_0_ports:u/                                        ( +-  8.87% )
       593,599,670      cpu_core/uops_retired.stalls:u/                                         ( +-  0.85% )

Anomaly:

     4,357,567,336      cpu_core/cycles:u/                                                      ( +-  0.15% )
     4,448,899,140      cpu_core/uops_issued.any:u/                                             ( +-  0.26% )
     2,107,051,688      cpu_core/exe_activity.1_ports_util:u/                                        ( +-  0.14% )
     1,106,699,503      cpu_core/exe_activity.2_ports_util:u/                                        ( +-  0.13% )
     1,129,497,409      cpu_core/exe_activity.exe_bound_0_ports:u/                                        ( +-  0.42% )
     2,502,226,997      cpu_core/uops_retired.stalls:u/                                         ( +-  0.38% )

Noise from the surrounding code aside, we see the same number of uops issued. However in the anomaly case, ~1/4th of the cycles are spent with no uops being executed, 1/2 are spent with only 1 uop being executed, and around 1/4 of the cycles have 2 uops being executed. I expected 0 and 2 being 50/50, consistently with there being one cycle stall, but if the uops are desynched and issued one cycle apart it would also explain the 1 being so prominent.

To confirm this I add an LFENCE at the start of each loop iteration to serialize the pipeline and try to ensure that each SHLX pair is issued in the same cycle. And it works:

     4,581,269,346      cpu_core/cycles:u/                                                      ( +-  0.10% )
     4,556,347,404      cpu_core/uops_issued.any:u/                                             ( +-  0.12% )
       133,363,872      cpu_core/exe_activity.1_ports_util:u/                                        ( +-  7.73% )
     2,082,838,530      cpu_core/exe_activity.2_ports_util:u/                                        ( +-  0.24% )
     2,165,817,614      cpu_core/exe_activity.exe_bound_0_ports:u/                                        ( +-  0.06% )
     3,090,362,239      cpu_core/uops_retired.stalls:u/                                         ( +-  0.16% )

Now the uops are split between 0 and 2 executed per cycle, as theorized.

Interleaving CQO and SHLX results in ~1.33 throughput with the anomaly, ~2.0 without. This ratio is more or less constant whether it's 1:1 or 2:2 or 4:4 or 8:8 (with 1:1 it's slightly lower at ~1.28).

This may or may not be consistent with one CQO uop being executed once a cycle as expected, and one SHLX uop taking a a spot (stalling for one cycle?) for 2 cycles, resulting in a runtime of (x/2 * 1 + x/2 * 2)/2 ~ x/1.33 cycles.

Same framework but instead of, say, SHLX RAX, RAX, RCX I do SHLX R[i], R[i], RCX for 8 consecutive registers. Yes, it still does go to both ports.

While the observation has previously focused on latency it also affects throughput: whereas you could run 2 independent shifts per cycle before, each shift going to either p0 or p6, this effects lowers this to a single shift per cycle.

Besides the shifts and rotations BZHI and BEXTR are also affected. While they are not a shift per se, it makes sense that it would be implemented with the same circuitry (e.g., BZHI is dst = arg1 & ~(-1 << arg2)). BEXTR in particular goes from 2 to 6 cycle latency!

Another thing I'm noticing is that the affected instructions are all p06 ops. You can alternatively implement rotation using SHLD r,r,c but this is a p1 operation and I have not seen any slowdown from this issue.

An interesting data point is that Kahn's The codebreakers, from 1967, uses "encipher" everywhere except for various US goverment agency quotes, which use "encrypt."

Normal for loops can't really make that work, they're too general, but range for loops plausibly could. Something like

    for(auto&& e : range) {
        std::print("{}" e);
        join {
            std::print(", ");
        }
    }

where join {} is effectively syntax sugar for if(std::next(__first) != __last) {}.

The fmt library makes this sort of task easier by providing the join adaptor; this example would become

    fmt::print("{}", fmt::join(range, ", "));

Yes, that is correct.

AVX-512 allows arbitrary shuffles, e.g., shuffle the 64 bytes in zmm0 with indices from zmm1 into zmm2. Simple shuffles like unpacks etc aren't really an issue.