Can anyone tell me why he starts searching for specific instructions that change their size when you add a specific...

I saw that couple of days ago, the biggest issue is Intel x86 cpus ignoring the 66 suffix, while amd and all disassemblers and virtual machines do not. You can construct a sequence of bytes that will do different things on the real machine and on vm (because vm thinks the instruction is 4 bytes while it really is 6, the next instruction will start at the wrong address). He found lots and lots of "undocumented" opcodes, and while I'm sure there are some hidden opcodes, I think most of the ones he found are not intentional ones. Each bit in an opcode means something, it's possible to construct a byte that will do something in the cup that wasn't planned. They try to detect illegal opcodes, but I guess it doesn't detect all possibilities.

You can see such thing on the 6502 cpu. There all opcodes are one byte, so you have 256 possible ones, but only about 100 of them were documented. The other ones either freeze the cpu or do something usefull. For example
Lda, load value to register a
Ldx, load value to register x
Lax, undocumented, load value to register a and x

Sta, store a to memory
Stx, store to to memory
Sax, undocumented, store a and x to memory (effectively andind a and x and storing the result)

I was finding it strange I didn't get a single mean message so far.
What I was interested in is specifically why he reduces the search space by finding the bytes that change the length of the instruction. I don't get why these are the relevant ones to keep for the search space.

Because there are bytes that for the actual opcode and then there are the argument opcodes if you will. For example E8 00 00 00 00 is mov eax, 0x00000000. The last 4 bytes are just a value that you put into the eax, changing them doesn't make for a new instruction. So he thought, ok, if I change this one byte and the size changes, then obviously this is a completely different opcode.

He's trying to use CPU behavior to reduce the search space he has to iterate through. The CPU is a black box (for all intents and purposes) you can never get inside of, with inputs and outputs dependent on those inputs, and a sheet of paper which is a (((promise))) of what behavior to expect. Basically he's trying to see where the (((promise))) is inconsistent from the reality of the chip's behavior.

There's almost no fucking doubt that there are undocumented instructions there because the NSA wants them there. If there ever was a "back-door me" undocumented function, I'd think [hope] NSA was smart enough to at least require some sort of "port knocking" scheme or equivalent to activate (so as not to be discovered by an instruction set scanner). Maybe that Die and Catch Fire instruction at the end in the undisclosed CPU is the effect of activating the instruction without the right knock sequence first, or it takes an argument which is a security key.

No, it's certainly a black box in every case, not only is it susceptible to change via unpredictable fabrication error, but it's also a proprietary design implementing proprietary instructions that were designed on proprietary instruments, and last but not least, it was all implemented using proprietary methods.

We desperately need home silicon fabbing.

You won't get that on the level required to make a modern cpu for a long time. Besides, modern cpus, or any cpu for that matter, are extremely complex. There's few people that could do a cup from scratch.

Intel's documentation states that an instruction is, at most, 15 bytes long. That 120 bits. Trying every combination of possible 120 bit instructions would take centuries. However, we know that 0x90 is a NOP and that if the first byte is 0x90, then that is one instruction, and the other 14 bytes will be decoded as an entirely different instruction: we can remove them from the search space. If the first two bytes are 0x6690, it is also a NOP, and the other 13 bytes are a different instruction: we can remove them from the search space. Using this, he reduces the search space for instructions from 2 ^ 120 (256 ^ 15) to a more reasonable 100 million possible bit patterns that represent instructions. He uses knowledge of the operation of the cpu to reduce the number of possible instructions. The point of finding length changes is to determine how much of the 15 byte window isn't in the search space.

And that, street shitter, is why he dedicates a good portion of his talk to reducing the search space for all possible instruction that the processor can have.

BS. The problem with the NSA wanting things in the processor is that, in general, the NSA doesn't want to pony up the money to put them there. Intel/AMD have a little bit of leeway when the government asks for something: "We aren't doing that for free, and if you think we are, then we can leave the country." Remember that about the US government: it does not want to pay for the kind of collusion it would like to have with its own industries.

Most undocumented instructions are: instructions for manufacturer testing, shit that they never actually got working correctly, DLC (instructions that their partners pay to learn about), or bugs in the processor. That f00f bug he found was probably bug in the processor.

The real problem with modern x86 processors is that they are RISC machines programmed to run only one program: an emulator for the x86 ISA. As such, the processors themselves suffer from the same kinds of software bugs that more well known software that emulates x86 suffer from (QEMU, Bochs, DOSBox, etc).

That freeze opcode is definitely a bug and it works only on some not common cpu. Heres some more detail about the 0xF00F bug from the first Intel Pentium

F00F Bug
Affects: Intel i586 series (Pentium 1, Pentium MMX, Pentium Overdrive, Pentium MMX Overdrive)
This bug is caused by executing LOCK CMPXCHG8B eax (F0 0F C7 C8) By containing two opcode errors, an unallowed lock and a non-memory target, together with trying to cache the results, it confuses the cpu to enter a deadlock state, locking up the entire computer involved.
To fix this bug, the IDT entry containing the invalid opcode should be marked as uncacheable or writethrough to eliminate one necessary factor, or by marking the same page as not-writable which further confuses the processor, this time into the pagefault handler instead of into a deadlock. If paging is to be left disabled, the only workaround is to disable the cpu's caches, which is far from efficient. Further discussion of various solutions is presented here.
We can check, if the processor is Pentium through the CPUID instruction. Calling it with EAX=1 will return the CPU signature in EAX. We can extract the Family Number from the CPU signature and compare it with 5, because the Pentium belongs to Family 5.

Makes sense, thanks.

Sorry to upset your autism.

Are you sure about this? Where would they go, China, Russia, the Philippines? I don't see how they would be better alternatives. Not to mention that I doubt it would be too much of a burden for intel to make some ops that fuck with privilege levels in exchange for some mutual back scratching from the US gov.