pbsd

Being offline does not ensure security against unverified plaintext. Imagine a colossal implementation fuckup (e.g., using strncmp to verify tags, ala Nintendo), or perhaps a hardware glitch flipping the verification bit to always return true. Ideally, i.e. with a robust AE scheme, you would hope that an altered ciphertext would result in random plaintext, but in SIV this is not the case.

Alas, there are no standardized robust schemes, with AEZ making it to the CAESAR final portfolio being the most likely scenario of that happening.

Kevin Igoe has been gone from the CFRG since mid-2015.

Probably not, I don't know. There's a better paper from a couple of years ago [1], which even manage to include code [2]. One of the attacks on NORX [3] was essentially exploiting a bigger-than-expected invariant subspace, it might be easier to get the gist of it that way.

By the way, I have the feeling that these attacks are more the consequence of these sort of designs becoming more popular than any particular breakthrough in cryptanalysis. For example, the symmetry properties of the AES round were already well known long ago, but it wasn't until people started taking the AES round and building primitives out of it without adding symmetry-breaking constants that this became a problem.

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

[2] http://invariant-space.gforge.inria.fr/

[3] http://dx.doi.org/10.13154/tosc.v2017.i1.156-174

One thing that tends to get overlooked in these discussions is what being 'a decade ahead' really means. Suppose you go back to 2007. What ciphers are you able to break now that you couldn't then?

In the past decade, I can think of 2 sort of new general cryptanalytic attacks: invariant subspace attacks, and the division property. The division property didn't really break anything; it claimed a full break of MYSTY1 with complexity 2^70, in case you happen to have the entire codebook already. It doesn't work well mostly for the same reason cube attacks haven't: most cipher designers know how dangerous a low algebraic degree can be.

The invariant subspace attack has been more successful, mainly in the lightweight space, mostly because it exploits the symmetries that tend to make a design smaller and elegant. But once again, against vetted ciphers it has not done so well.

So let's posit the NSA does have another couple of attacks in hand we don't know about. Chances are they're not going to be very useful. Do they specifically affect SIMON and/or SPECK? It would require an intersection of conditions that seems very implausible, and it seems tricky to have it affect both designs at the same time without being noticeable. But I guess we'll know in 2027.

In another note, if I was going to make a cipher with a hidden weakness to dupe the world into using, I probably wouldn't go with a block cipher---literally the most heavily analyzed kind of primitive in the public sphere. I would probably go with a stream cipher, or a stream-like dedicated authenticated cipher, whose security is much less studied than block ciphers, and can still be used in most places a block cipher would be.

This curl function actually came up in conversation with someone about a month ago. We figured that there was no way the core transformation was secure, and that was about the extent of our interest in it.

(Generalized) Feistel networks have to be neither balanced nor over bits (see, e.g., [1]), so you could conceivably devise a 'perfect' permutation for any particular resolution.

For example, with 320x200, you'd do something like (completely untested)

    for (var i = 0; i < 8; i++) {
        l = input / 320;
        r = input % 320;
        var nl = r;
        var F = (r * 356357 + i * 1234567) % 200;
        r = (l + F) % 200;
        l = nl;
        input = 200*l + r;
    }

which is not exactly fast or anything, but covers your domain perfectly.

[1] https://eprint.iacr.org/2010/301

I don't think it was the NSA either, but do note that Juniper itself had originally Q set to a different value than the recommended one, and then _that_ value was modified.

We can agree on that. But now I am completely lost as to what your original point was...

u8 gets promoted to signed int before the shift. That he only used unsigned types is irrelevant.

There's no sign-extension involved. Let's say the input is (uint8_t)128. This gets promoted to (int)128, which is then shifted 24 bits to the left. If the input was (int8_t)128, it would get sign-extended into (int)-128, but that is not the case here.

With 32-bit ints, this operation will result in 0x80000000, shifting a bit into the sign bit, which constitutes an overflow (and undefined behavior). Think about it in terms of multiplication: you're multiplying a positive integer by 2^24, and it turns out negative!

For what it's worth, the size-prefixed jcc/call binutils bug had already been fixed a couple of years ago: https://sourceware.org/bugzilla/show_bug.cgi?id=18386

For what it's worth, I just went back to an earlier version (10240) of win32kbase.sys, and the search is indeed a lot simpler...it's essentially a flat linear table search (to be clear, it's still iterating through every GDI object), much friendlier to the CPU than the structure traversing that happens now. Could very well be the culprit.

Yeah, it's proportional to the total number of GDI objects. Approximately:

  DWORD HmgNextOwned(DWORD index, DWORD pid, HANDLE * handle) {
    GDI_TABLE_ENTRY entry;
    GreAcquireHmgrSemaphore();
    // GetNextEntryIndex is inlined in reality, this is the main loop you see in the disassembly
    while(index = gpHandleManager->GetNextEntryIndex(index, &entry)) { 
      if(entry.Type != 0 && ((pid & 0xFFFFFFFD) ^ entry.ProcessId) & 0xFFFFFFFE) == 0) {
        *handle = index | (entry.Upper << 16);
        break;
      }
    }
    GreReleaseHmgrSemaphore();
    return index;
  }

Best information I could find on the relevant structures is [1], which gives an idea of what you're traversing. I don't know why this is designed this way; it does seem suboptimal.

[1] https://cvr-data.blogspot.com/2016/11/windows-10-anniversary...

HmgNextOwned doesn't do, by itself, all that much. There is some mild pointer-chasing, but not too horrible. All it does is to go through the global GDI handle table and look for handles owned by the terminating process. It is used loosely as

    DWORD index = 0;
    while(true) {
      SOME_GDI_OBJECT_TYPE obj;
      index = HmgNextOwned(index, pid, &obj);
      if(index == 0) break; // done / nothing found
      // ... do some clean up of the object here
    }

The thing is, this loop is executed 6 (12, if counting the instances inlined into NtGdiCloseProcess) times when terminating a process, for various object types, and for each call of HmgNextOwned it will lock and unlock the handle manager lock.

The typical way you'd solve that would be to take

    [K * pi      1 0 0]
    [K * e       0 1 0]
    [K * sqrt(2) 0 0 1]
    [K * 194.927424491 0 0 0]

for some large-ish K, say 2^20, and look for a short(est) vector of this lattice. Basically you're minimizing the norm of (a * pi + b * e + c * sqrt(2) + d * 194.927424491, a, b, c) while giving the majority of the weight to the first component, which you hope to be near 0.

According to the Logjam paper, the 1024-bit individual logarithm would cost around 30 (parallelizable) core-days once the group precomputation is over with. Unless they're being exceedingly stingy with their hardware, 30 core-days (less than a day in a single powerful workstation) would already be 'file a ticket' levels of easy.

(Note that the time reported in this newer paper is calendar time---it's still 10 core-days, so quite comparable to the non-special variant.)

I didn't realize that was in there, but yes.

The more important point to take away from this paper is not that 1024-bit is already considered broken, so this doesn't matter. It's that the cost of 2048-bit DH---which is used and recommended today, and will stick around forever---has roughly the cost of 1024-bit DH when coupled with a special polynomial.

    sage: p=2^255-19
    sage: sqrt(GF(p)(-486664))
    6853475219497561581579357271197624642482790079785650197046958215289687604742

The formula in Wikipedia is not wrong, but note that it maps E_{a,d} to M_{A, B} with B = 4/(a - d) = -486664. curve25519, and pretty much every Montgomery curve, is defined with B = 1, so you need some extra twisting to get there.

Your conversion between Edwards and Montgomery is not quite correct. I suspect that is why you're getting different results (though I didn't really go over the whole thing). RFC 7748 does include the correct conversion routines in page 4: ((1+y)/(1-y), sqrt(-486664) * ((1+y)/(1-y))/x) to go from ed25519 to x25519, and (sqrt(-486664) * u/v, (u-1)/(u+1)) to go back. So with some luck, you're only missing 2 multiplications by a constant.

What exactly is the problem? Converting between Montgomery and twisted Edwards is well documented by now, for example in [3, Theorem 3.2] or RFC 7748. The descriptions in, e.g., [1, §3.2] or [2, §4.3] for the Montgomery y-recovery trick are pretty straightforward.

[1] https://link.springer.com/chapter/10.1007/3-540-44709-1_12

[2] https://eprint.iacr.org/2017/212

[3] https://eprint.iacr.org/2008/013

I haven't seen a description of it anywhere that I can think of. The driver lives in C:\Windows\system32\mcupdate_{genuineintel,authenticamd}.dll. All it does is detect which CPU it's running on, and load the appropriate microcode.

Loading the microcode is straightforward---all you need to do is put a few values in the appropriate MSRs. This is described in the Intel manuals, Volume 3. The microcode itself is embedded in the above DLLs, as a big binary table. The latest entry I see is 20150812 for the Intel 0x40651, aka Haswell.

The loop needs to be short because the loopback buffer is only active in loops of 64 or fewer entries (usually fewer real instructions, something like 40 or so). Moreover, Skylake introduced one loopback buffer per thread, instead of the previous loopback buffer shared between both threads.

My guess is that is where the bug is; the behavior for partial register access stalls---insert one extraneous uop to combine, e.g., ah with rax---is unchanged since Sandy Bridge.

Windows does have a microcode update driver, as you would expect, so it can fix this.

However, looking at the microcode update driver on an updated Windows 10 as of right now, I don't see a recent enough microcode version to fix it. The latest updates appear to be from 2015.

Almost certainly not the former, no. At best the code would be "supplementary material", which reviewers are not required to go over.

For what it's worth, BLAKE2 has the original number of rounds of BLAKE: 12 and 10. It was increased to 16 and 14 before the 3rd round of the competition, because BLAKE was fast enough that increasing the round numbers like this would still make it sufficient fast---and, indeed, the faster function in the 3rd round still---and the most conservative function of the bunch.

Keccak began with 18 rounds. It increased to 24 rounds on the 2nd round after some largely irrelevant distinguishers were found. You can see that K12 is cutting it really close, as the 256-bit variant adds two rounds for added safety, in addition to the reduced control over the state with the larger capacity.

I can imagine ~12-round Keccak being "broken" in my lifetime, as well as ~8-round BLAKE2. I cannot imagine the full version of either being ever broken.

That's a criticism I'm entirely on board with, and is not limited to linear algebra libraries. HTTP client libraries are worse, there's not a single good one.

std::valarray does not have multidimensional support at all. In fact, std::valarray is a relatively abandoned part of the standard library. You'll have to go with one of the 3rd party libraries for better support.

My point was not so much that valarray is awesome, but that articles like this one tend to fight a very strawman version of C++, even when just sticking to strictly standard components.

Not to mention all of that array behavior is available on the standard C++ library with std::valarray<T>, e.g., https://godbolt.org/g/JBSvuH. There was talk of a more thorough standard multi-dimensional array type, but I have no idea what's the status on that.

That won't help much; you can zero the entire final state easily, e.g., with the message IV0 IV1 IV2 IV3 (or by xoring the latest diffuse() output back into the state), in which case you get diffuse(0) = 0 and with your finalization function you still get easy collisions.

The operating mode of this hash is broken by default. The author calls it Merkle-Damgard, but that is not what it is. Merkle-Damgard uses a compression function, whereas what we have here is more like a sponge with full state absorption (you can pretend F(IV ^ m) is a compression function, but it is trivially susceptible to collisions F(IV ^ m) = F(m ^ IV)). Meaning, without a secret IV and some sort of truncation there's no way this mode can be secure, even with an ideal diffuse() function.